[LLVMbugs] [Bug 6019] New: LLVM Creates a Cyclic SelectionDAG

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.org/bugs/show_bug.cgi?id=6019

           Summary: LLVM Creates a Cyclic SelectionDAG
           Product: libraries
           Version: trunk
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Backend: X86
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: greened at obbligato.org
                CC: llvmbugs at cs.uiuc.edu


Created an attachment (id=4043)
 --> (http://llvm.org/bugs/attachment.cgi?id=4043)
Testcase to trigger a topological sort failure

The attached testcase triggers the following assert in llc:

llc:
/ptmp/dag/llvm-project.official/llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:5202:
unsigned int llvm::SelectionDAG::AssignTopologicalOrder(): Assertion `SortedPos
== AllNodes.end() && "Topological sort incomplete!"' failed.
0  llc       0x000000000172e71e
1  llc       0x000000000172ed04
2  libc.so.6 0x00002b15e6b10c10
3  libc.so.6 0x00002b15e6b10b95 gsignal + 53
4  libc.so.6 0x00002b15e6b11f90 abort + 272
5  libc.so.6 0x00002b15e6b0a256 __assert_fail + 246
6  llc       0x000000000126368f llvm::SelectionDAG::AssignTopologicalOrder() +
715
7  llc       0x0000000000bc4dad llvm::SelectionDAGISel::SelectRootInit() + 25
8  llc       0x000000000119c7f3 (anonymous
namespace)::X86DAGToDAGISel::SelectRoot(llvm::SelectionDAG&) + 37
9  llc       0x000000000102ac7f (anonymous
namespace)::X86DAGToDAGISel::InstructionSelect() + 189
10 llc       0x00000000012dc1cb llvm::SelectionDAGISel::CodeGenAndEmitDAG() +
3713
11 llc       0x00000000012ddefa
llvm::SelectionDAGISel::SelectBasicBlock(llvm::BasicBlock*,
llvm::ilist_iterator<llvm::Instruction>,
llvm::ilist_iterator<llvm::Instruction>, bool&) + 686
12 llc       0x00000000012de89f
llvm::SelectionDAGISel::SelectAllBasicBlocks(llvm::Function&,
llvm::MachineFunction&, llvm::MachineModuleInfo*, llvm::DwarfWriter*,
llvm::TargetInstrInfo const&) + 2419
13 llc       0x00000000012df2ab
llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&) + 931
14 llc       0x00000000013ea4f5
llvm::MachineFunctionPass::runOnFunction(llvm::Function&) + 83
15 llc       0x00000000016ac020
llvm::FPPassManager::runOnFunction(llvm::Function&) + 336
16 llc       0x00000000016adbe5
llvm::FunctionPassManagerImpl::run(llvm::Function&) + 79
17 llc       0x00000000016add86 llvm::FunctionPassManager::run(llvm::Function&)
+ 112
18 llc       0x0000000000b2221c main + 3166
19 libc.so.6 0x00002b15e6afe154 __libc_start_main + 244
20 llc       0x0000000000b207a9
Stack dump:
0.      Program arguments:
/ptmp/dag/build.llvm.trunk.official.debug/x86_64-unknown-linux-gnu/Debug/bin/llc
bugpoint-reduced-simplified.bc -f -o bugpoint-reduced-simplified.s
1.      Running pass 'X86 DAG->DAG Instruction Selection' on function
'@numvec_'
Abort

Examination of the SelectionDAG reveals a cyclic graph:

Offending node:
0x1a8fd00: i64 = add 0x1a8cce0, 0x1a6b970Comments: # 
  0x1a8cce0: i64 = shl 0x1a6bae0, 0x1a8e3e0Comments: # 
    0x1a6bae0: i64 = sign_extend 0x1a8de20Comments: # 
      0x1a8de20: i32 = extract_vector_elt 0x1a8db40, 0x1a8dcb0Comments: # 
        0x1a8db40: v4i32 = vector_shuffle 0x1a8fb90, 0x1a6c0a0,
0x1a8d130<3,u,u,u>Comments: # 
          0x1a8fb90: v4i32 = bit_convert 0x1a6bf30Comments: # 
            0x1a6bf30: v2i64,ch = load 0x1a8cfc0, 0x1a6bdc0, 0x1a8fa20
<0x1a431d8:0> alignment=4Comments: # 
              0x1a8cfc0: ch = TokenFactor 0x1a6b690, 0x1a6c210:1Comments: # 
                0x1a6b690: ch = EntryToken Comments: # 
                0x1a6c210: i32,ch = load 0x1a6b690, 0x1a8e550, 0x1a8fa20
<0x1a434f8:0> alignment=4Comments: # 
                  0x1a6b690: ch = EntryToken Comments: # 
                  0x1a8e550: i64 = add 0x1a8fd00, 0x1a8cb70Comments: # 
                    0x1a8fd00: i64 = add 0x1a8cce0, 0x1a6b970Comments: # 
                      0x1a8cce0: i64 = shl 0x1a6bae0, 0x1a8e3e0Comments: # 
                        0x1a6bae0: i64 = sign_extend 0x1a8de20Comments: # 
                          0x1a8de20: i32 = extract_vector_elt 0x1a8db40,
0x1a8dcb0Comments: # 
                            0x1a8db40: v4i32 = vector_shuffle 0x1a8fb90,
0x1a6c0a0, 0x1a8d130<3,u,u,u>Comments: # 
                              0x1a8fb90: v4i32 = bit_convert 0x1a6bf30Comments:
# 
                                0x1a6bf30: v2i64,ch = load 0x1a8cfc0,
0x1a6bdc0, 0x1a8fa20 <0x1a431d8:0> alignment=4Comments: # 
                                  0x1a8cfc0: ch = TokenFactor 0x1a6b690,
0x1a6c210:1Comments: # 
                                    0x1a6b690: ch = EntryToken Comments: # 
                                    0x1a6c210: i32,ch = load 0x1a6b690,
0x1a8e550, 0x1a8fa20 <0x1a434f8:0> alignment=4Comments: # 
                                      0x1a6b690: ch = EntryToken Comments: # 
                                      0x1a8e550: i64 = add 0x1a8fd00,
0x1a8cb70Comments: # 
                                        0x1a8fd00: i64 = add 0x1a8cce0,
0x1a6b970Comments: # 
                                          0x1a8cce0: i64 = shl 0x1a6bae0,
0x1a8e3e0Comments: # 

Note the reuse of 0x1a8e550.  I don't believe that is allowed.  In the final
loop nest of the topological sort code in SelectionDAG.cpp, the iterator I
eventually runs ahead of SortedPos, which is a no-no given that nodes referred
to by I are assumed to be already sorted.  I believe this is due to the cyclic
structure above.


-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.