[LLVMdev] Understanding SelectionDAG construction
ankur deshwal
a.s.deshwal at gmail.com
Wed Jun 8 02:55:01 PDT 2011
Hi everyone,
Thanks for the help. I did some gdbing and found some code flow which
explains the formation of SelectionDAG.
I am including few of my steps which helped me understanding the code-flow.
This information is aimed at someone like searching about SelectionDAG and
no clue where to start looking. I hope this will help someone.
My appologies if someone finds this post annoying.
==================================================================================
Building gdb friendly llvm
../src/configure --prefix=<llvm_install_dir> --disable-optimized
--enable-targets=x86
make -j4 VERBOSE=1
make install
gdb <llvm_install_dir>/bin/llc
==================================================================================
Initial SelectionDAG Construction - The initial SelectionDAG is naively
peephole expanded from the LLVM input by the SelectionDAGLowering class in
the
lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp file. The intent of this pass
is to expose as much low-level, target-specific details to the SelectionDAG
as
possible.
What I found in comments from svn for llvm-trunk was - Rename
SelectionDAGLowering to SelectionDAGBuilder, and rename
SelectionDAGBuild.cpp to SelectionDAGBuilder.cpp.
=====================================================================================================
So the SelectionDAGBuilder is the class responsible for "building selection
DAG". To look into how it does this, set the breakpoint at the constructor
of this class.
(gdb) break llvm::SelectionDAGBuilder::SelectionDAGBuilder
(gdb) r 1.bc
Breakpoint 2, llvm::SelectionDAGBuilder::SelectionDAGBuilder
(this=0x8dc6a20, dag=..., funcinfo=..., ol=Default)
at <llvm_src_dir>/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h:324
324 HasTailCall(false), Context(dag.getContext()) {
(gdb) bt
#0 llvm::SelectionDAGBuilder::SelectionDAGBuilder (this=0x8dc6a20, dag=...,
funcinfo=..., ol=Default)
at <llvm_src_dir>/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h:324
#1 0x08775473 in llvm::SelectionDAGISel::SelectionDAGISel (this=0x8dbc818,
tm=..., OL=Default)
at <llvm_src_dir>/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:192
#2 0x085d3eb0 in (anonymous namespace)::X86DAGToDAGISel::X86DAGToDAGISel
(this=0x8dbc818, tm=..., OptLevel=Default)
at <llvm_src_dir>/lib/Target/X86/X86ISelDAGToDAG.cpp:162
#3 0x085d3f24 in llvm::createX86ISelDag (TM=..., OptLevel=Default) at
<llvm_src_dir>/lib/Target/X86/X86ISelDAGToDAG.cpp:2006
#4 0x085bb355 in llvm::X86TargetMachine::addInstSelector (this=0x8db5f10,
PM=..., OptLevel=Default)
at <llvm_src_dir>/lib/Target/X86/X86TargetMachine.cpp:200
#5 0x08872012 in llvm::LLVMTargetMachine::addCommonCodeGenPasses
(this=0x8db5f10, PM=..., OptLevel=Default, DisableVerify=false,
OutContext=@0xbfffe758)
at <llvm_src_dir>/lib/CodeGen/LLVMTargetMachine.cpp:341
#6 0x08872753 in llvm::LLVMTargetMachine::addPassesToEmitFile
(this=0x8db5f10, PM=..., Out=..., FileType=CGFT_AssemblyFile,
OptLevel=Default,
DisableVerify=false) at
<llvm_src_dir>/lib/CodeGen/LLVMTargetMachine.cpp:125
#7 0x0852789d in main (argc=2, argv=0xbfffe974) at
<llvm_src_dir>/tools/llc/llc.cpp:335
what above snapshots suggest is
LLVMTargetMachine::addPassesToEmitFile (lib/CodeGen/LLVMTargetMachine.cpp)
---calls---> llvm::LLVMTargetMachine::addCommonCodeGenPasses
(lib/CodeGen/LLVMTargetMachine.cpp)
---calls---> X86TargetMachine::addInstSelector
(lib/Target/X86/X86TargetMachine.cpp)
---calls---> llvm::createX86ISelDag (lib/Target/X86/X86ISelDAGToDAG.cpp)
---calls---> X86DAGToDAGISel::X86DAGToDAGISel
(lib/Target/X86/X86ISelDAGToDAG.cpp )
---calls---> llvm::SelectionDAGISel::SelectionDAGISel
(lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp)
---calls---> llvm::SelectionDAGBuilder::SelectionDAGBuilder
So looking at where the constructor for SelectionDAGBuilder is called, we
need to look at llvm::SelectionDAGISel::SelectionDAGISel. Here is the
snapshot from this constructor
SelectionDAGISel::SelectionDAGISel(const TargetMachine &tm,
CodeGenOpt::Level OL) :
MachineFunctionPass(ID), TM(tm), TLI(*tm.getTargetLowering()),
FuncInfo(new FunctionLoweringInfo(TLI)),
CurDAG(new SelectionDAG(tm)),
SDB(new SelectionDAGBuilder(*CurDAG, *FuncInfo, OL)),
GFI(),
OptLevel(OL),
DAGSize(0) {
initializeGCModuleInfoPass(*PassRegistry::getPassRegistry());
initializeAliasAnalysisAnalysisGroup(*PassRegistry::getPassRegistry());
}
Therefore, SelectionDAGISel constructor creates a new Selection DAG and
Calls constructor to SelectionDAGBuilder with this new Slection DAG.
=====================================================================================================
After returning from addInstSelector (after all the initializations) to
addCommonCodeGenPasses, different Passes are registered with the Pass
manager. All these passes are added in file
lib/CodeGen/LLVMTargetMachine.cpp to a pass manager and are later run from
main funtion (look for PM.run(mod); in llc.cpp)
Following dump shows the few passes being added in addCommonCodeGenPasses
function
llvm::LLVMTargetMachine::addCommonCodeGenPasses (this=0x8db5f10, PM=...,
OptLevel=Default, DisableVerify=false, OutContext=@0xbfffe758)
at <llvm_src_dir>/lib/CodeGen/LLVMTargetMachine.cpp:345
345 printAndVerify(PM, "After Instruction Selection");
(gdb)
348 PM.add(createExpandISelPseudosPass());
(gdb)
352 if (OptLevel != CodeGenOpt::None)
(gdb)
353 PM.add(createOptimizePHIsPass());
(gdb)
357 PM.add(createLocalStackSlotAllocationPass());
(gdb)
359 if (OptLevel != CodeGenOpt::None) {
(gdb)
364 PM.add(createDeadMachineInstructionElimPass());
=====================================================================================================
Now coming back to SelectionDAGBuilder. Staring at documentation ( Doxygen )
suggests looking at llvm::SelectionDAGBuilder::init function may be helpful.
So setting a breakbpoint there and continuing some staring at code.....
Breakpoint 3, llvm::SelectionDAGBuilder::init (this=0x8dc6a20, gfi=0x0,
aa=...)
at <llvm_src_dir>/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp:773
773 AA = &aa;
(gdb) bt
#0 llvm::SelectionDAGBuilder::init (this=0x8dc6a20, gfi=0x0, aa=...)
at <llvm_src_dir>/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp:773
#1 0x08774518 in llvm::SelectionDAGISel::runOnMachineFunction
(this=0x8dbc818, mf=...)
at <llvm_src_dir>/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:305
#2 0x0889c2b5 in llvm::MachineFunctionPass::runOnFunction (this=0x8dbc818,
F=...)
at <llvm_src_dir>/lib/CodeGen/MachineFunctionPass.cpp:33
#3 0x08be0d05 in llvm::FPPassManager::runOnFunction (this=0x8dbbfc0, F=...)
at <llvm_src_dir>/lib/VMCore/PassManager.cpp:1483
#4 0x08be0ecf in llvm::FPPassManager::runOnModule (this=0x8dbbfc0, M=...)
at <llvm_src_dir>/lib/VMCore/PassManager.cpp:1503
#5 0x08be09d3 in llvm::MPPassManager::runOnModule (this=0x8db4560, M=...)
at <llvm_src_dir>/lib/VMCore/PassManager.cpp:1557
#6 0x08be1dc4 in llvm::PassManagerImpl::run (this=0x8db5778, M=...) at
<llvm_src_dir>/lib/VMCore/PassManager.cpp:1638
#7 0x08be1e29 in llvm::PassManager::run (this=0xbfffe814, M=...) at
<llvm_src_dir>/lib/VMCore/PassManager.cpp:1682
#8 0x08527910 in main (argc=2, argv=0xbfffe974) at
<llvm_src_dir>/tools/llc/llc.cpp:341
Above backtrace shows that the init function for SelectionDAGBuilder class
is called from SelectionDAGISel::runOnMachineFunction function which is an
implementation for pass. This particular implementation must be present
around 305 line of lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp.
The few lines of code above and below 305 are
CurDAG->init(*MF);
FuncInfo->set(Fn, *MF);
305 SDB->init(GFI, *AA);
SelectAllBasicBlocks(Fn);
This shows init at 305 is followed by function SelectAllBasicBlocks.
SelectAllBasicBlocks traverses over all blocks in a function (see below)
--> Traversal Loop starts here
ReversePostOrderTraversal<const Function*> RPOT(&Fn);
for (ReversePostOrderTraversal<const Function*>::rpo_iterator
I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
const BasicBlock *LLVMBB = *I;
.
.
.
SelectBasicBlock(Inst, BI, HadTailCall);
.
.
.
FinishBasicBlock();
FuncInfo->PHINodesToUpdate.clear();
}
--> and ends here (above).
In between, function SelectBasicBlock is called which converts and llvm
instr of the basic block into selection dag and then applies other phases
like
legalization, optimization etc.
Lets look into SelectBasicBlock. It runs an iterator over all instructions
of llvm and calls visit funtion for each. Notice that this visit function
has
signature - void SelectionDAGBuilder::visit(const Instruction &I) and is
present in SelectionDAGBuilder.cpp file.
This calls other visit function which has signature as void
SelectionDAGBuilder::visit(unsigned Opcode, const User &I) and is present in
the same file. Now
this visit function does something very wierd with including file
include/llvm/Instruction.def. This is where all the Selection DAG generation
happens.
On Mon, Jun 6, 2011 at 6:53 PM, Christoph Erhardt <christoph at sicherha.de>wrote:
> Hi Ankur,
>
> > The flags "-view-sched-dags".. described in the doc doesn't seem to work.
> (
> > "llc -help" doesn't list it ).
> as far as I remember, displaying DAGs during compilation is only enabled
> in "debug builds" [1] of LLVM. You probably have to re-configure and
> re-compile LLVM to enable this feature.
>
> Best regards,
> Christoph
>
> [1] http://llvm.org/docs/GettingStarted.html#compile
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110608/5f505133/attachment.html>
More information about the llvm-dev
mailing list