<div>Hi everyone, </div>
<div> </div>
<div>Thanks for the help. I did some gdbing and found some code flow which explains the formation of SelectionDAG.</div>
<div> </div>
<div>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.</div>
<div>My appologies if someone finds this post annoying.</div>
<div> </div>
<div>==================================================================================</div>
<div>Building gdb friendly llvm</div>
<div> </div>
<div>../src/configure --prefix=<llvm_install_dir> --disable-optimized --enable-targets=x86</div>
<div>make -j4 VERBOSE=1<br>make install</div>
<div><br>gdb <llvm_install_dir>/bin/llc</div>
<div>==================================================================================</div>
<div> </div>
<div>Initial SelectionDAG Construction - The initial SelectionDAG is naively peephole expanded from the LLVM input by the SelectionDAGLowering class in the </div>
<div>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 </div>
<div>possible.</div>
<div>What I found in comments from svn for llvm-trunk was - Rename SelectionDAGLowering to SelectionDAGBuilder, and rename SelectionDAGBuild.cpp to SelectionDAGBuilder.cpp.</div>
<div>=====================================================================================================</div>
<div>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.</div>
<div>(gdb) break llvm::SelectionDAGBuilder::SelectionDAGBuilder<br>(gdb) r 1.bc</div>
<div>Breakpoint 2, llvm::SelectionDAGBuilder::SelectionDAGBuilder (this=0x8dc6a20, dag=..., funcinfo=..., ol=Default)<br> at <llvm_src_dir>/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h:324<br>324 HasTailCall(false), Context(dag.getContext()) {<br>
(gdb) bt<br>#0 llvm::SelectionDAGBuilder::SelectionDAGBuilder (this=0x8dc6a20, dag=..., funcinfo=..., ol=Default)<br> at <llvm_src_dir>/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h:324<br>#1 0x08775473 in llvm::SelectionDAGISel::SelectionDAGISel (this=0x8dbc818, tm=..., OL=Default)<br>
at <llvm_src_dir>/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:192<br>#2 0x085d3eb0 in (anonymous namespace)::X86DAGToDAGISel::X86DAGToDAGISel (this=0x8dbc818, tm=..., OptLevel=Default)<br> at <llvm_src_dir>/lib/Target/X86/X86ISelDAGToDAG.cpp:162<br>
#3 0x085d3f24 in llvm::createX86ISelDag (TM=..., OptLevel=Default) at <llvm_src_dir>/lib/Target/X86/X86ISelDAGToDAG.cpp:2006<br>#4 0x085bb355 in llvm::X86TargetMachine::addInstSelector (this=0x8db5f10, PM=..., OptLevel=Default)<br>
at <llvm_src_dir>/lib/Target/X86/X86TargetMachine.cpp:200<br>#5 0x08872012 in llvm::LLVMTargetMachine::addCommonCodeGenPasses (this=0x8db5f10, PM=..., OptLevel=Default, DisableVerify=false, <a href="mailto:OutContext=@0xbfffe758">OutContext=@0xbfffe758</a>)<br>
at <llvm_src_dir>/lib/CodeGen/LLVMTargetMachine.cpp:341<br>#6 0x08872753 in llvm::LLVMTargetMachine::addPassesToEmitFile (this=0x8db5f10, PM=..., Out=..., FileType=CGFT_AssemblyFile, OptLevel=Default,<br> DisableVerify=false) at <llvm_src_dir>/lib/CodeGen/LLVMTargetMachine.cpp:125<br>
#7 0x0852789d in main (argc=2, argv=0xbfffe974) at <llvm_src_dir>/tools/llc/llc.cpp:335</div>
<div> </div>
<div>what above snapshots suggest is </div>
<div> LLVMTargetMachine::addPassesToEmitFile (lib/CodeGen/LLVMTargetMachine.cpp)<br> ---calls---> llvm::LLVMTargetMachine::addCommonCodeGenPasses (lib/CodeGen/LLVMTargetMachine.cpp)<br> ---calls---> X86TargetMachine::addInstSelector (lib/Target/X86/X86TargetMachine.cpp)<br>
---calls---> llvm::createX86ISelDag (lib/Target/X86/X86ISelDAGToDAG.cpp)<br> ---calls---> X86DAGToDAGISel::X86DAGToDAGISel (lib/Target/X86/X86ISelDAGToDAG.cpp )<br> ---calls---> llvm::SelectionDAGISel::SelectionDAGISel (lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp)<br>
---calls---> llvm::SelectionDAGBuilder::SelectionDAGBuilder</div>
<div><br>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</div>
<div><br>SelectionDAGISel::SelectionDAGISel(const TargetMachine &tm,<br> CodeGenOpt::Level OL) :<br> MachineFunctionPass(ID), TM(tm), TLI(*tm.getTargetLowering()),<br> FuncInfo(new FunctionLoweringInfo(TLI)),<br>
CurDAG(new SelectionDAG(tm)),<br> SDB(new SelectionDAGBuilder(*CurDAG, *FuncInfo, OL)),<br> GFI(),<br> OptLevel(OL),<br> DAGSize(0) {<br> initializeGCModuleInfoPass(*PassRegistry::getPassRegistry());<br> initializeAliasAnalysisAnalysisGroup(*PassRegistry::getPassRegistry());<br>
}</div>
<div><br>Therefore, SelectionDAGISel constructor creates a new Selection DAG and Calls constructor to SelectionDAGBuilder with this new Slection DAG.</div>
<div>=====================================================================================================</div>
<div>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)</div>
<div>Following dump shows the few passes being added in addCommonCodeGenPasses function</div>
<div>llvm::LLVMTargetMachine::addCommonCodeGenPasses (this=0x8db5f10, PM=..., OptLevel=Default, DisableVerify=false, <a href="mailto:OutContext=@0xbfffe758">OutContext=@0xbfffe758</a>)<br> at <llvm_src_dir>/lib/CodeGen/LLVMTargetMachine.cpp:345<br>
345 printAndVerify(PM, "After Instruction Selection");<br>(gdb)<br>348 PM.add(createExpandISelPseudosPass());<br>(gdb)<br>352 if (OptLevel != CodeGenOpt::None)<br>(gdb)<br>353 PM.add(createOptimizePHIsPass());<br>
(gdb)<br>357 PM.add(createLocalStackSlotAllocationPass());<br>(gdb)<br>359 if (OptLevel != CodeGenOpt::None) {<br>(gdb)<br>364 PM.add(createDeadMachineInstructionElimPass());</div>
<div>=====================================================================================================</div>
<div>Now coming back to SelectionDAGBuilder. Staring at documentation ( Doxygen ) suggests looking at llvm::SelectionDAGBuilder::init function may be helpful.</div>
<div>So setting a breakbpoint there and continuing some staring at code.....</div>
<div>Breakpoint 3, llvm::SelectionDAGBuilder::init (this=0x8dc6a20, gfi=0x0, aa=...)<br> at <llvm_src_dir>/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp:773<br>773 AA = &aa;<br>(gdb) bt<br>#0 llvm::SelectionDAGBuilder::init (this=0x8dc6a20, gfi=0x0, aa=...)<br>
at <llvm_src_dir>/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp:773<br>#1 0x08774518 in llvm::SelectionDAGISel::runOnMachineFunction (this=0x8dbc818, mf=...)<br> at <llvm_src_dir>/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:305<br>
#2 0x0889c2b5 in llvm::MachineFunctionPass::runOnFunction (this=0x8dbc818, F=...)<br> at <llvm_src_dir>/lib/CodeGen/MachineFunctionPass.cpp:33<br>#3 0x08be0d05 in llvm::FPPassManager::runOnFunction (this=0x8dbbfc0, F=...) at <llvm_src_dir>/lib/VMCore/PassManager.cpp:1483<br>
#4 0x08be0ecf in llvm::FPPassManager::runOnModule (this=0x8dbbfc0, M=...) at <llvm_src_dir>/lib/VMCore/PassManager.cpp:1503<br>#5 0x08be09d3 in llvm::MPPassManager::runOnModule (this=0x8db4560, M=...) at <llvm_src_dir>/lib/VMCore/PassManager.cpp:1557<br>
#6 0x08be1dc4 in llvm::PassManagerImpl::run (this=0x8db5778, M=...) at <llvm_src_dir>/lib/VMCore/PassManager.cpp:1638<br>#7 0x08be1e29 in llvm::PassManager::run (this=0xbfffe814, M=...) at <llvm_src_dir>/lib/VMCore/PassManager.cpp:1682<br>
#8 0x08527910 in main (argc=2, argv=0xbfffe974) at <llvm_src_dir>/tools/llc/llc.cpp:341</div>
<div><br>Above backtrace shows that the init function for SelectionDAGBuilder class is called from SelectionDAGISel::runOnMachineFunction function which is an </div>
<div>implementation for pass. This particular implementation must be present around 305 line of lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp. <br>The few lines of code above and below 305 are</div>
<div> CurDAG->init(*MF);<br> FuncInfo->set(Fn, *MF);<br>305 SDB->init(GFI, *AA);<br> SelectAllBasicBlocks(Fn);</div>
<div>This shows init at 305 is followed by function SelectAllBasicBlocks. SelectAllBasicBlocks traverses over all blocks in a function (see below)</div>
<div>--> Traversal Loop starts here </div>
<div> ReversePostOrderTraversal<const Function*> RPOT(&Fn);<br> for (ReversePostOrderTraversal<const Function*>::rpo_iterator<br> I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {<br> const BasicBlock *LLVMBB = *I;<br>
.<br>.<br>.<br> SelectBasicBlock(Inst, BI, HadTailCall);<br>.<br>.<br>.</div>
<div> FinishBasicBlock();<br> FuncInfo->PHINodesToUpdate.clear();<br> }</div>
<div>--> and ends here (above). </div>
<div>In between, function SelectBasicBlock is called which converts and llvm instr of the basic block into selection dag and then applies other phases like </div>
<div>legalization, optimization etc.</div>
<div>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 </div>
<div>signature - void SelectionDAGBuilder::visit(const Instruction &I) and is present in SelectionDAGBuilder.cpp file.<br>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 </div>
<div>this visit function does something very wierd with including file include/llvm/Instruction.def. This is where all the Selection DAG generation happens.</div>
<div><br><br><br> </div>
<div class="gmail_quote">On Mon, Jun 6, 2011 at 6:53 PM, Christoph Erhardt <span dir="ltr"><<a href="mailto:christoph@sicherha.de">christoph@sicherha.de</a>></span> wrote:<br>
<blockquote style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class="gmail_quote">Hi Ankur,<br>
<div class="im"><br>> The flags "-view-sched-dags".. described in the doc doesn't seem to work. (<br>> "llc -help" doesn't list it ).<br></div>as far as I remember, displaying DAGs during compilation is only enabled<br>
in "debug builds" [1] of LLVM. You probably have to re-configure and<br>re-compile LLVM to enable this feature.<br><br>Best regards,<br>Christoph<br><br>[1] <a href="http://llvm.org/docs/GettingStarted.html#compile" target="_blank">http://llvm.org/docs/GettingStarted.html#compile</a><br>
</blockquote></div><br>