[LLVMbugs] [Bug 10542] New: Debug information synthesis during RAGreedy run takes a shockingly long time

Sat Jul 30 18:38:58 PDT 2011

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

           Summary: Debug information synthesis during RAGreedy run takes
                    a shockingly long time
           Product: libraries
           Version: trunk
          Platform: PC
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: Register Allocator
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: chandlerc at gmail.com
                CC: llvmbugs at cs.uiuc.edu

This looked initially like an infloop to me, but if you wait long enough, it
actually completes. It's very easy to reproduce this: you hit it when
self-hosting LLVM+Clang in a opt + debug info build.

Specifically, lib/VMCore/Function.cpp takes 6.5 seconds to compile on my system
with -O2. However, with -O2 -g it takes over 5 minutes. When I attach with gdb
I get this:

(gdb) bt
#0  llvm::MachineBasicBlock::SkipPHIsAndLabels (this=<value optimized out>,
I=<value optimized out>) at
/home/chandlerc/src/llvm.git/include/llvm/CodeGen/MachineInstr.h:199
#1  0x0000000000f4c771 in findInsertLocation (this=<value optimized out>,
MBB=<value optimized out>, LocNo=<value optimized out>, LIS=Unhandled dwarf
expression opcode 0xd6
) at /home/chandlerc/src/llvm.git/lib/CodeGen/LiveDebugVariables.cpp:872
#2  (anonymous namespace)::UserValue::insertDebugValue (this=<value optimized
out>, MBB=<value optimized out>, LocNo=<value optimized out>, LIS=Unhandled
dwarf expression opcode 0xd6
) at /home/chandlerc/src/llvm.git/lib/CodeGen/LiveDebugVariables.cpp:892
#3  0x0000000000f4bce2 in llvm::LiveDebugVariables::emitDebugValues
(this=<value optimized out>, VRM=<value optimized out>) at
/home/chandlerc/src/llvm.git/lib/CodeGen/LiveDebugVariables.cpp:934
#4  0x0000000000ea9edb in (anonymous namespace)::RAGreedy::runOnMachineFunction
(this=<value optimized out>, mf=<value optimized out>) at
/home/chandlerc/src/llvm.git/lib/CodeGen/RegAllocGreedy.cpp:1598
#5  0x0000000000e74cbc in llvm::MachineFunctionPass::runOnFunction (this=<value
optimized out>, F=<value optimized out>) at
/home/chandlerc/src/llvm.git/lib/CodeGen/MachineFunctionPass.cpp:33
#6  0x00000000011131ae in llvm::FPPassManager::runOnFunction (this=<value
optimized out>, F=Unhandled dwarf expression opcode 0x0
) at /home/chandlerc/src/llvm.git/lib/VMCore/PassManager.cpp:1513
#7  0x000000000111349b in llvm::FPPassManager::runOnModule (this=<value
optimized out>, M=<value optimized out>) at
/home/chandlerc/src/llvm.git/lib/VMCore/PassManager.cpp:1535
#8  0x00000000011135e2 in llvm::MPPassManager::runOnModule (this=<value
optimized out>, M=Unhandled dwarf expression opcode 0x0
) at /home/chandlerc/src/llvm.git/lib/VMCore/PassManager.cpp:1589
#9  0x0000000001113bc1 in llvm::PassManagerImpl::run (this=<value optimized
out>, M=<value optimized out>) at
/home/chandlerc/src/llvm.git/lib/VMCore/PassManager.cpp:1671
#10 0x000000000111410d in llvm::PassManager::run (this=<value optimized out>,
M=<value optimized out>) at
/home/chandlerc/src/llvm.git/lib/VMCore/PassManager.cpp:1715
#11 0x000000000118d29c in clang::EmitBackendOutput (Diags=<value optimized
out>, CGOpts=<value optimized out>, TOpts=<value optimized out>, LOpts=<value
optimized out>, M=<value optimized out>, Action=<value optimized out>, 
    OS=<value optimized out>) at
/home/chandlerc/src/llvm.git/tools/clang/lib/CodeGen/BackendUtil.cpp:388
#12 0x000000000118b767 in clang::BackendConsumer::HandleTranslationUnit
(this=Unhandled dwarf expression opcode 0x0
) at /home/chandlerc/src/llvm.git/tools/clang/lib/CodeGen/CodeGenAction.cpp:134
#13 0x0000000000732fae in clang::ParseAST (S=<value optimized out>,
PrintStats=<value optimized out>) at
/home/chandlerc/src/llvm.git/tools/clang/lib/Parse/ParseAST.cpp:101
#14 0x000000000118acc1 in clang::CodeGenAction::ExecuteAction (this=Unhandled
dwarf expression opcode 0x0
) at /home/chandlerc/src/llvm.git/tools/clang/lib/CodeGen/CodeGenAction.cpp:347
#15 0x00000000006b2f4b in clang::CompilerInstance::ExecuteAction
(this=Unhandled dwarf expression opcode 0x0
) at
/home/chandlerc/src/llvm.git/tools/clang/lib/Frontend/CompilerInstance.cpp:614
#16 0x00000000006ffb70 in clang::ExecuteCompilerInvocation (Clang=<value
optimized out>) at
/home/chandlerc/src/llvm.git/tools/clang/lib/FrontendTool/ExecuteCompilerInvocation.cpp:171
#17 0x000000000065c4ec in cc1_main (ArgBegin=<value optimized out>,
ArgEnd=Unhandled dwarf expression opcode 0x0
) at /home/chandlerc/src/llvm.git/tools/clang/tools/driver/cc1_main.cpp:159
#18 0x0000000000657e33 in main (argc_=<value optimized out>, argv_=<value
optimized out>) at
/home/chandlerc/src/llvm.git/tools/clang/tools/driver/driver.cpp:353

I've spent some time looking at exactly what's going on with this. If I break
down the backtrace and interrupt the compilation more frequently I observe the
following pattern:

(gdb) bt
#0  llvm::MachineBasicBlock::SkipPHIsAndLabels (this=<value optimized out>,
I=<value optimized out>) at
/home/chandlerc/src/llvm.git/include/llvm/CodeGen/MachineInstr.h:199
#1  0x0000000000f4c771 in findInsertLocation (this=<value optimized out>,
MBB=<value optimized out>, LocNo=<value optimized out>, LIS=Unhandled dwarf
expression opcode 0xd6
) at /home/chandlerc/src/llvm.git/lib/CodeGen/LiveDebugVariables.cpp:872
#2  (anonymous namespace)::UserValue::insertDebugValue (this=<value optimized
out>, MBB=<value optimized out>, LocNo=<value optimized out>, LIS=Unhandled
dwarf expression opcode 0xd6
) at /home/chandlerc/src/llvm.git/lib/CodeGen/LiveDebugVariables.cpp:892

These three frames change on each interruption. the 'this' values tend to cycle
etc if I use an un-optimized build of Clang so I have full debug info.

#3  0x0000000000f4bce2 in llvm::LiveDebugVariables::emitDebugValues
(this=<value optimized out>, VRM=<value optimized out>) at
/home/chandlerc/src/llvm.git/lib/CodeGen/LiveDebugVariables.cpp:934
#4  0x0000000000ea9edb in (anonymous namespace)::RAGreedy::runOnMachineFunction
(this=<value optimized out>, mf=<value optimized out>) at
/home/chandlerc/src/llvm.git/lib/CodeGen/RegAllocGreedy.cpp:1598

These frames (and the rest) tended to remain the same. Not sure if (or how
much) that helps.

I can try to get a reduced test case, but I worry that won't really help
understand the problem any better than just reproducing and looking at why
we're iterating through these value structures soooo many times.

I've attached a preprocessed test case just for convenience. This was extracted
by building LLVM itself in verbose mode, and preprocessing Function.cpp.

-- 
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.