search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
28.62k stars 11.83k forks source link

Infinite loop in Shrink Wrapping #25197

Closed llvmbot closed 9 years ago

llvmbot commented 9 years ago
Bugzilla Link 24823
Resolution FIXED
Resolved on Sep 15, 2015 13:52
Version trunk
OS Linux
Attachments ll file that exposes an infinite loop in shrink wrapping code
Reporter LLVM Bugzilla Contributor
CC @hfinkel,@qcolombet

Extended Description

There is an infinite loop at compile time, in the shrink wrapping code when compiling the attached test case. The problem appears at -O3, -O2 compiled fine (I did not try other options). I can reproduce the hang with simply: llc shrink.ll

The traceback from GDB contains:

(gdb) where

​0 0x0000000011c45eb0 in llvm::DenseMapBase<llvm::DenseMap<llvm::MachineBasicBlock, std::unique_ptr<llvm::DomTreeNodeBase, std::default_delete<llvm::DomTreeNodeBase > >, llvm::DenseMapInfo<llvm::MachineBasicBlock>, llvm::detail::DenseMapPair<llvm::MachineBasicBlock, std::unique_ptr<llvm::DomTreeNodeBase, std::default_delete<llvm::DomTreeNodeBase > > > >, llvm::MachineBasicBlock, std::unique_ptr<llvm::DomTreeNodeBase, std::default_delete<llvm::DomTreeNodeBase > >, llvm::DenseMapInfo<llvm::MachineBasicBlock>, llvm::detail::DenseMapPair<llvm::MachineBasicBlock, std::unique_ptr<llvm::DomTreeNodeBase, std::default_delete<llvm::DomTreeNodeBase > > > >::LookupBucketFor<llvm::MachineBasicBlock*> (

this=0x100208d0030, Val=@0x3fffd4805f80: 0x10020ab9678, FoundBucket=@0x3fffd4805f48: 0x10020aa42e8) at /home/kbarton/llvm/src/dev.git/include/llvm/ADT/DenseMap.h:471

​1 0x0000000011c40314 in llvm::DenseMapBase<llvm::DenseMap<llvm::MachineBasicBlock, std::unique_ptr<llvm::DomTreeNodeBase, std::default_delete<llvm::DomTreeNodeBase > >, llvm::DenseMapInfo<llvm::MachineBasicBlock>, llvm::detail::DenseMapPair<llvm::MachineBasicBlock, std::unique_ptr<llvm::DomTreeNodeBase, std::default_delete<llvm::DomTreeNodeBase > > > >, llvm::MachineBasicBlock, std::unique_ptr<llvm::DomTreeNodeBase, std::default_delete<llvm::DomTreeNodeBase > >, llvm::DenseMapInfo<llvm::MachineBasicBlock>, llvm::detail::DenseMapPair<llvm::MachineBasicBlock, std::unique_ptr<llvm::DomTreeNodeBase, std::default_delete<llvm::DomTreeNodeBase > > > >::find (this=0x100208d0030, Val=@0x3fffd4805f80: 0x10020ab9678)

at /home/kbarton/llvm/src/dev.git/include/llvm/ADT/DenseMap.h:132

​2 0x0000000011c3d4e8 in llvm::DominatorTreeBase::getNode (this=0x100208d0010, BB=0x10020ab9678) at /home/kbarton/llvm/src/dev.git/include/llvm/Support/GenericDomTree.h:377

​3 0x0000000011c3f198 in llvm::DominatorTreeBase::dominates (this=0x100208d0010, A=0x10020ab9678, B=0x10020ab9518) at /home/kbarton/llvm/src/dev.git/include/llvm/Support/GenericDomTree.h:759

​4 0x0000000010c7ecd0 in llvm::MachinePostDominatorTree::dominates (this=0x100208ada80, A=0x10020ab9678, B=0x10020ab9518) at /home/kbarton/llvm/src/dev.git/include/llvm/CodeGen/MachinePostDominators.h:62

​5 0x0000000011e00aa8 in (anonymous namespace)::ShrinkWrap::updateSaveRestorePoints (this=0x100208adb20, MBB=...) at /home/kbarton/llvm/src/dev.git/lib/CodeGen/ShrinkWrap.cpp:285

​6 0x0000000011e00df8 in (anonymous namespace)::ShrinkWrap::runOnMachineFunction (this=0x100208adb20, MF=...) at /home/kbarton/llvm/src/dev.git/lib/CodeGen/ShrinkWrap.cpp:345

​7 0x0000000011c68130 in llvm::MachineFunctionPass::runOnFunction (this=0x100208adb20, F=...) at /home/kbarton/llvm/src/dev.git/lib/CodeGen/MachineFunctionPass.cpp:43

​8 0x00000000121fcdac in llvm::FPPassManager::runOnFunction (this=0x100208c5170, F=...) at /home/kbarton/llvm/src/dev.git/lib/IR/LegacyPassManager.cpp:1528

​9 0x00000000121fd010 in llvm::FPPassManager::runOnModule (this=0x100208c5170, M=...) at /home/kbarton/llvm/src/dev.git/lib/IR/LegacyPassManager.cpp:1549

​10 0x00000000121fd59c in (anonymous namespace)::MPPassManager::runOnModule (this=0x100208ad5b0, M=...) at /home/kbarton/llvm/src/dev.git/lib/IR/LegacyPassManager.cpp:1605

​11 0x00000000121fdf34 in llvm::legacy::PassManagerImpl::run (this=0x100208ad170, M=...) at /home/kbarton/llvm/src/dev.git/lib/IR/LegacyPassManager.cpp:1708

​12 0x00000000121fe310 in llvm::legacy::PassManager::run (this=0x3fffd4806610, M=...) at /home/kbarton/llvm/src/dev.git/lib/IR/LegacyPassManager.cpp:1739

​13 0x00000000108bb9b4 in compileModule (argv=0x3fffd4806e78, Context=...) at /home/kbarton/llvm/src/dev.git/tools/llc/llc.cpp:381

​14 0x00000000108ba5e4 in main (argc=2, argv=0x3fffd4806e78) at /home/kbarton/llvm/src/dev.git/tools/llc/llc.cpp:204

qcolombet commented 9 years ago

Actually that was easy enough to come up with a test case from scratch. Test case added in Committed revision 247713.

qcolombet commented 9 years ago

I've committed the fix in: Committed revision 247710.

Kit, fell free to add the reduced test case or let me know and I'll work on it. Thanks for catching this!

qcolombet commented 9 years ago

Fix Yep, that is the problem. Attached a patch that fixes it.

The patch can be optimized to look for a post dominator quickly, but I leave that for a follow-up commit.

Kit, could you try to reduce the test case and add FileCheck lines? If not, let me know and I'll look into it.

llvmbot commented 9 years ago

Ah, that makes sense. The original complainant mentioned that the program was generated by csmith, so the presence of infinite loops in the source is quite possible.

qcolombet commented 9 years ago

That seems to be same problem were the input program has an infinite loop and we do not detect that properly.

llvmbot commented 9 years ago

I forgot to specify in the comments that this is occurring on powerpc64le.