[LLVMdev] Understanding SelectionDAG construction

ankur deshwal a.s.deshwal at gmail.com
Wed Jun 8 04:55:01 CDT 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
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
lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp file. The intent of this pass
is to expose as much low-level, target-specific details to the SelectionDAG
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
#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,
    at <llvm_src_dir>/lib/CodeGen/LLVMTargetMachine.cpp:341
#6  0x08872753 in llvm::LLVMTargetMachine::addPassesToEmitFile
(this=0x8db5f10, PM=..., Out=..., FileType=CGFT_AssemblyFile,
    DisableVerify=false) at
#7  0x0852789d in main (argc=2, argv=0xbfffe974) at

what above snapshots suggest is
 LLVMTargetMachine::addPassesToEmitFile (lib/CodeGen/LLVMTargetMachine.cpp)
 ---calls--->  llvm::LLVMTargetMachine::addCommonCodeGenPasses
 ---calls--->  X86TargetMachine::addInstSelector
 ---calls--->  llvm::createX86ISelDag (lib/Target/X86/X86ISelDAGToDAG.cpp)
 ---calls--->  X86DAGToDAGISel::X86DAGToDAGISel
(lib/Target/X86/X86ISelDAGToDAG.cpp )
 ---calls--->  llvm::SelectionDAGISel::SelectionDAGISel
 ---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)),
  DAGSize(0) {

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
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");
348       PM.add(createExpandISelPseudosPass());
352       if (OptLevel != CodeGenOpt::None)
353         PM.add(createOptimizePHIsPass());
357       PM.add(createLocalStackSlotAllocationPass());
359       if (OptLevel != CodeGenOpt::None) {
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,
    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,
    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
#7  0x08be1e29 in llvm::PassManager::run (this=0xbfffe814, M=...) at
#8  0x08527910 in main (argc=2, argv=0xbfffe974) at

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
 FuncInfo->set(Fn, *MF);
305 SDB->init(GFI, *AA);
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);
--> 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
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
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

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.cs.uiuc.edu/pipermail/llvmdev/attachments/20110608/5f505133/attachment.html 

More information about the LLVMdev mailing list