[LLVMdev] liveness assertion problem in llc

Fri Sep 21 02:08:28 PDT 2012

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