Hi Jacob,
At this point, I suspect there is a problem with maintaining liveness
information during branch folding. Here is what I see:
I have a basic block ready for branch optimization, that computes a predicate
p10 on which a conditional branch depends. Notice that this is in the stage with
physical registers.
BB#2: derived from LLVM BB %while.cond.preheader
Live Ins: %R3 %R5
Predecessors according to CFG: BB#0
DBG_VALUE %P0, 0, !"buf"; line no:42
DBG_VALUE %R3, 0, !"count"; line no:42
DBG_VALUE %P0, 0, !"p"; line no:44
%R1<def> = MOV32ri 0, pred:%noreg
%p10<def> = CMPEQI %R3, 0, pred:%noreg; dbg:../src/getbits.c:53:3
JUMP <BB#6>, pred:%p10<kill>
JUMP <BB#3>, pred:%noreg
Successors according to CFG: BB#3 BB#6
Several transformations are performed during branch folding:
1) As part of the branch optimization, the conditional branch is reversed. To do
so, an additional instruction is added to the code that computes the
complementary predicate p387, and this predicate is then used in the reversed
branch. The instruction is built using BuildMI and addReg methods as I do in
other parts of the backend and as worked well before r161463. The resulting
basic block of this step 0 looks like this:
BB#2: derived from LLVM BB %while.cond.preheader
Live Ins: %R3 %R5
Predecessors according to CFG: BB#0
DBG_VALUE %P0, 0, !"buf"; line no:42
DBG_VALUE %R3, 0, !"count"; line no:42
DBG_VALUE %P0, 0, !"p"; line no:44
%R1<def> = MOV32ri 0, pred:%noreg
%p387<def> = CMPNEI %R3, 0, pred:%noreg; dbg:../src/getbits.c:53:3
%p10<def> = CMPEQI %R3, 0, pred:%noreg; dbg:../src/getbits.c:53:3
JUMP <BB#4>, pred:%p387
Successors according to CFG: BB#4 BB#6
I should point out that this newly used register p387 was previously not used or
defined at all in the function at hand, so I guess no use-def chains will have
been computed for it. Until r161462, this posed no problem whatsoever. Also
note that the new jump does not have the <kill> attribute. Might that be a
problem?
Later on during branch optimization, llc decides to further change the branches,
removing and inserting branches. I don't understand the whole decision
process behind this, but specifically this sequence of transformations takes
place:
2) remove branch JUMP <BB#4>, pred:%p387 (works fine)
3) insert branches JUMP <BB#4>, pred:%p387 (with the same code that
inserted an identical instruction in step 1)
JUMP <BB#3>, pred:%noreg
3) try to remove branches, starting with JUMP <BB#4>, pred:%p387 inserted
in step 3).
That is when things go wrong and I get the following assertion (with GDB)
backtrace. (Please note that my RemoveBranch code is nothing special, it looks
exactly the same as the code in the Mips backend. )
llc: /work/llvm/trunk/llvm/lib/CodeGen/MachineRegisterInfo.cpp:162: void
llvm::MachineRegisterInfo::removeRegOperandFromUseList(llvm::MachineOperand*):
Assertion `NextOp->getReg() == MO->getReg() && "Corrupt reg
use/def chain!"' failed.
Program received signal SIGABRT, Aborted.
0xb7fdd424 in __kernel_vsyscall ()
(gdb) bt
#0 0xb7fdd424 in __kernel_vsyscall ()
#1 0xb7cfe1ef in __GI_raise (sig=6) at
../nptl/sysdeps/unix/sysv/linux/raise.c:64
#2 0xb7d01835 in __GI_abort () at abort.c:91
#3 0xb7cf7095 in __assert_fail_base (fmt=0xb7e308b8 "%s%s%s:%u:
%s%sAssertion `%s' failed.\n%n", assertion=0x8e1699c
"NextOp->getReg() == MO->getReg() && \"Corrupt reg
use/def chain!\"",
file=0x8e16760
"/work/llvm/trunk/llvm/lib/CodeGen/MachineRegisterInfo.cpp", line=162,
function=0x8e17d60 "void
llvm::MachineRegisterInfo::removeRegOperandFromUseList(llvm::MachineOperand*)")
at assert.c:94
#4 0xb7cf7147 in __GI___assert_fail (assertion=0x8e1699c
"NextOp->getReg() == MO->getReg() && \"Corrupt reg
use/def chain!\"", file=0x8e16760
"/work/llvm/trunk/llvm/lib/CodeGen/MachineRegisterInfo.cpp", line=162,
function=0x8e17d60 "void
llvm::MachineRegisterInfo::removeRegOperandFromUseList(llvm::MachineOperand*)")
at assert.c:103
#5 0x0884e0e0 in llvm::MachineRegisterInfo::removeRegOperandFromUseList
(this=0x931b0c8, MO=0x9329aac) at
/work/llvm/trunk/llvm/lib/CodeGen/MachineRegisterInfo.cpp:162
#6 0x08823d7f in llvm::MachineInstr::RemoveRegOperandsFromUseLists
(this=0x931b920, MRI=...) at
/work/llvm/trunk/llvm/lib/CodeGen/MachineInstr.cpp:638
#7 0x087f7c64 in
llvm::ilist_traits<llvm::MachineInstr>::removeNodeFromList
(this=0x931b3b4, N=0x931b920) at
/work/llvm/trunk/llvm/lib/CodeGen/MachineBasicBlock.cpp:115
#8 0x0856f3d8 in llvm::iplist<llvm::MachineInstr,
llvm::ilist_traits<llvm::MachineInstr> >::remove (this=0x931b3b4,
IT=...) at /work/llvm/trunk/llvm/include/llvm/ADT/ilist.h:444
#9 0x0856f1e8 in llvm::iplist<llvm::MachineInstr,
llvm::ilist_traits<llvm::MachineInstr> >::erase (this=0x931b3b4,
where=...) at /work/llvm/trunk/llvm/include/llvm/ADT/ilist.h:463
#10 0x0856f22b in llvm::iplist<llvm::MachineInstr,
llvm::ilist_traits<llvm::MachineInstr> >::erase (this=0x931b3b4,
first=..., last=...) at /work/llvm/trunk/llvm/include/llvm/ADT/ilist.h:528
#11 0x0856f077 in llvm::MachineBasicBlock::erase (this=0x931b3ac, I=..., E=...)
at /work/llvm/trunk/llvm/include/llvm/CodeGen/MachineBasicBlock.h:480
#12 0x08593f60 in llvm::ADRESInstrInfo::RemoveBranch (this=0x92cf50c, MBB=...)
at /work/llvm/trunk/llvm/lib/Target/ADRES/ADRESInstrInfo.cpp:364
#13 0x0892d513 in llvm::BranchFolder::OptimizeBlock (this=0xbfffea70,
MBB=0x931bd14) at /work/llvm/trunk/llvm/lib/CodeGen/BranchFolding.cpp:1200
#14 0x0892c565 in llvm::BranchFolder::OptimizeBranches (this=0xbfffea70, MF=...)
at /work/llvm/trunk/llvm/lib/CodeGen/BranchFolding.cpp:972
#15 0x089298c2 in llvm::BranchFolder::OptimizeFunction (this=0xbfffea70, MF=...,
tii=0x92cf50c, tri=0x92cf528, mmi=0x92f1228) at
/work/llvm/trunk/llvm/lib/CodeGen/BranchFolding.cpp:208
#16 0x08929150 in (anonymous namespace)::BranchFolderPass::runOnMachineFunction
(this=0x9309d28, MF=...) at
/work/llvm/trunk/llvm/lib/CodeGen/BranchFolding.cpp:91
#17 0x08820b79 in llvm::MachineFunctionPass::runOnFunction (this=0x9309d28,
F=...) at /work/llvm/trunk/llvm/lib/CodeGen/MachineFunctionPass.cpp:33
#18 0x08b7a49a in llvm::FPPassManager::runOnFunction (this=0x92e5bb8, F=...) at
/work/llvm/trunk/llvm/lib/VMCore/PassManager.cpp:1498
#19 0x08b7a656 in llvm::FPPassManager::runOnModule (this=0x92e5bb8, M=...) at
/work/llvm/trunk/llvm/lib/VMCore/PassManager.cpp:1518
#20 0x08b7a934 in llvm::MPPassManager::runOnModule (this=0x92ce660, M=...) at
/work/llvm/trunk/llvm/lib/VMCore/PassManager.cpp:1572
#21 0x08b7adf8 in llvm::PassManagerImpl::run (this=0x92ce118, M=...) at
/work/llvm/trunk/llvm/lib/VMCore/PassManager.cpp:1655
#22 0x08b7af95 in llvm::PassManager::run (this=0xbfffedc0, M=...) at
/work/llvm/trunk/llvm/lib/VMCore/PassManager.cpp:1684
#23 0x083a44f4 in main (argc=13, argv=0xbfffef44) at
/work/llvm/trunk/llvm/tools/llc/llc.cpp:553
So at this point, I suspect that the problem is that def-use chains are not
maintained well during the branch transformations, and more specifically when
new instructions are added to compute complementary predicates in physical
registers that were not at all used or defined in the function at hand before,
and when these registers are then used. But it is strange that in a sequence
InsertBranch - RemoveBranch - InsertBranch - RemoveBranch all operating on an
identical instruction, the first removal is successful, while the second asserts
... following the commit of r161643
Can you shed some light on this, on where to look further for example?
Thanks a lot,
Bjorn
