LLVM API Documentation
00001 //===-- DAGBuilder.cpp - Turn an LLVM BasicBlock into a DAG for selection -===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file turns an LLVM BasicBlock into a target-independent SelectionDAG in 00011 // preparation for target-specific optimizations and instruction selection. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "llvm/CodeGen/SelectionDAG.h" 00016 #include "llvm/Constants.h" 00017 #include "llvm/Function.h" 00018 #include "llvm/Instructions.h" 00019 #include "llvm/Type.h" 00020 #include "llvm/CodeGen/MachineFunction.h" 00021 #include "llvm/Target/TargetMachine.h" 00022 #include "llvm/Support/InstVisitor.h" 00023 #include <iostream> 00024 00025 using namespace llvm; 00026 00027 namespace llvm { 00028 struct SelectionDAGBuilder : public InstVisitor<SelectionDAGBuilder> { 00029 // DAG - the current dag we are building. 00030 SelectionDAG &DAG; 00031 00032 // SDTB - The target-specific builder interface, which indicates how to expand 00033 // extremely target-specific aspects of the representation, such as function 00034 // calls and arguments. 00035 SelectionDAGTargetBuilder &SDTB; 00036 00037 // BB - The current machine basic block we are working on. 00038 MachineBasicBlock *BB; 00039 00040 // CurRoot - The root built for the current basic block. 00041 SelectionDAGNode *CurRoot; 00042 00043 SelectionDAGBuilder(SelectionDAG &dag, SelectionDAGTargetBuilder &sdtb) 00044 : DAG(dag), SDTB(sdtb), BB(0), CurRoot(0) {} 00045 00046 void visitBB(BasicBlock &bb); 00047 00048 // Visitation methods for instructions: Create the appropriate DAG nodes for 00049 // the instruction. 00050 void visitAdd(BinaryOperator &BO); 00051 void visitSub(BinaryOperator &BO); 00052 void visitMul(BinaryOperator &BO); 00053 00054 void visitAnd(BinaryOperator &BO); 00055 void visitOr (BinaryOperator &BO); 00056 void visitXor(BinaryOperator &BO); 00057 00058 void visitSetEQ(BinaryOperator &BO); 00059 00060 void visitLoad(LoadInst &LI); 00061 void visitCall(CallInst &CI); 00062 00063 void visitBr(BranchInst &BI); 00064 void visitRet(ReturnInst &RI); 00065 00066 void visitInstruction(Instruction &I) { 00067 std::cerr << "DAGBuilder: Cannot instruction select: " << I; 00068 abort(); 00069 } 00070 00071 private: 00072 SelectionDAGNode *getNodeFor(Value *V); 00073 SelectionDAGNode *getNodeFor(Value &V) { return getNodeFor(&V); } 00074 00075 SelectionDAGNode *addSeqNode(SelectionDAGNode *N); 00076 }; 00077 } // end llvm namespace 00078 00079 /// addSeqNode - The same as addNode, but the node is also included in the 00080 /// sequence nodes for this block. This method should be called for any 00081 /// instructions which have a specified sequence they must be evaluated in. 00082 /// 00083 SelectionDAGNode *SelectionDAGBuilder::addSeqNode(SelectionDAGNode *N) { 00084 DAG.addNode(N); // First, add the node to the selection DAG 00085 00086 if (!CurRoot) 00087 CurRoot = N; 00088 else { 00089 // Create and add a new chain node for the existing root and this node... 00090 CurRoot = DAG.addNode(new SelectionDAGNode(ISD::ChainNode, MVT::isVoid, 00091 BB, CurRoot, N)); 00092 } 00093 return N; 00094 } 00095 00096 /// getNodeFor - This method returns the SelectionDAGNode for the specified LLVM 00097 /// value, creating a node as necessary. 00098 /// 00099 SelectionDAGNode *SelectionDAGBuilder::getNodeFor(Value *V) { 00100 // If we already have the entry, return it. 00101 SelectionDAGNode*& Entry = DAG.ValueMap[V]; 00102 if (Entry) return Entry; 00103 00104 // Otherwise, we need to create a node to return now... start by figuring out 00105 // which type the node will be... 00106 MVT::ValueType ValueType = DAG.getValueType(V->getType()); 00107 00108 if (Instruction *I = dyn_cast<Instruction>(V)) 00109 // Instructions will be filled in later. For now, just create and return a 00110 // dummy node. 00111 return Entry = new SelectionDAGNode(ISD::ProtoNode, ValueType); 00112 00113 if (Constant *C = dyn_cast<Constant>(V)) { 00114 if (ConstantBool *CB = dyn_cast<ConstantBool>(C)) { 00115 Entry = new SelectionDAGNode(ISD::Constant, ValueType); 00116 Entry->addValue(new ReducedValue_Constant_i1(CB->getValue())); 00117 } else if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) { 00118 Entry = new SelectionDAGNode(ISD::Constant, ValueType); 00119 switch (ValueType) { 00120 case MVT::i8: 00121 Entry->addValue(new ReducedValue_Constant_i8(CI->getRawValue())); 00122 break; 00123 case MVT::i16: 00124 Entry->addValue(new ReducedValue_Constant_i16(CI->getRawValue())); 00125 break; 00126 case MVT::i32: 00127 Entry->addValue(new ReducedValue_Constant_i32(CI->getRawValue())); 00128 break; 00129 case MVT::i64: 00130 Entry->addValue(new ReducedValue_Constant_i64(CI->getRawValue())); 00131 break; 00132 default: 00133 assert(0 && "Invalid ValueType for an integer constant!"); 00134 } 00135 00136 } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) { 00137 Entry = new SelectionDAGNode(ISD::Constant, ValueType); 00138 if (ValueType == MVT::f32) 00139 Entry->addValue(new ReducedValue_Constant_f32(CFP->getValue())); 00140 else 00141 Entry->addValue(new ReducedValue_Constant_f64(CFP->getValue())); 00142 } 00143 if (Entry) return Entry; 00144 } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) { 00145 Entry = new SelectionDAGNode(ISD::BasicBlock, ValueType); 00146 Entry->addValue(new ReducedValue_BasicBlock_i32(DAG.BlockMap[BB])); 00147 return Entry; 00148 } 00149 00150 std::cerr << "Unhandled LLVM value in DAG Builder!: " << *V << "\n"; 00151 abort(); 00152 return 0; 00153 } 00154 00155 00156 // visitBB - This method is used to visit a basic block in the program. It 00157 // manages the CurRoot instance variable so that all of the visit(Instruction) 00158 // methods can be written to assume that there is only one basic block being 00159 // constructed. 00160 // 00161 void SelectionDAGBuilder::visitBB(BasicBlock &bb) { 00162 BB = DAG.BlockMap[&bb]; // Update BB instance var 00163 00164 // Save the current global DAG... 00165 SelectionDAGNode *OldRoot = CurRoot; 00166 CurRoot = 0; 00167 00168 visit(bb.begin(), bb.end()); // Visit all of the instructions... 00169 00170 if (OldRoot) { 00171 if (!CurRoot) 00172 CurRoot = OldRoot; // This block had no root of its own.. 00173 else { 00174 // The previous basic block AND this basic block had roots, insert a 00175 // block chain node now... 00176 CurRoot = DAG.addNode(new SelectionDAGNode(ISD::BlockChainNode, 00177 MVT::isVoid, 00178 BB, OldRoot, CurRoot)); 00179 } 00180 } 00181 } 00182 00183 //===----------------------------------------------------------------------===// 00184 // ...Visitation Methods... 00185 //===----------------------------------------------------------------------===// 00186 00187 void SelectionDAGBuilder::visitAdd(BinaryOperator &BO) { 00188 getNodeFor(BO)->setNode(ISD::Plus, BB, getNodeFor(BO.getOperand(0)), 00189 getNodeFor(BO.getOperand(1))); 00190 } 00191 void SelectionDAGBuilder::visitSub(BinaryOperator &BO) { 00192 getNodeFor(BO)->setNode(ISD::Minus, BB, getNodeFor(BO.getOperand(0)), 00193 getNodeFor(BO.getOperand(1))); 00194 } 00195 void SelectionDAGBuilder::visitMul(BinaryOperator &BO) { 00196 getNodeFor(BO)->setNode(ISD::Times, BB, getNodeFor(BO.getOperand(0)), 00197 getNodeFor(BO.getOperand(1))); 00198 } 00199 00200 void SelectionDAGBuilder::visitAnd(BinaryOperator &BO) { 00201 getNodeFor(BO)->setNode(ISD::And, BB, getNodeFor(BO.getOperand(0)), 00202 getNodeFor(BO.getOperand(1))); 00203 } 00204 void SelectionDAGBuilder::visitOr(BinaryOperator &BO) { 00205 getNodeFor(BO)->setNode(ISD::Or, BB, getNodeFor(BO.getOperand(0)), 00206 getNodeFor(BO.getOperand(1))); 00207 } 00208 void SelectionDAGBuilder::visitXor(BinaryOperator &BO) { 00209 getNodeFor(BO)->setNode(ISD::Xor, BB, getNodeFor(BO.getOperand(0)), 00210 getNodeFor(BO.getOperand(1))); 00211 } 00212 void SelectionDAGBuilder::visitSetEQ(BinaryOperator &BO) { 00213 getNodeFor(BO)->setNode(ISD::SetEQ, BB, getNodeFor(BO.getOperand(0)), 00214 getNodeFor(BO.getOperand(1))); 00215 } 00216 00217 00218 void SelectionDAGBuilder::visitRet(ReturnInst &RI) { 00219 if (RI.getNumOperands()) { // Value return 00220 addSeqNode(new SelectionDAGNode(ISD::Ret, MVT::isVoid, BB, 00221 getNodeFor(RI.getOperand(0)))); 00222 } else { // Void return 00223 addSeqNode(new SelectionDAGNode(ISD::RetVoid, MVT::isVoid, BB)); 00224 } 00225 } 00226 00227 00228 void SelectionDAGBuilder::visitBr(BranchInst &BI) { 00229 if (BI.isUnconditional()) 00230 addSeqNode(new SelectionDAGNode(ISD::Br, MVT::isVoid, BB, 00231 getNodeFor(BI.getOperand(0)))); 00232 else 00233 addSeqNode(new SelectionDAGNode(ISD::BrCond, MVT::isVoid, BB, 00234 getNodeFor(BI.getCondition()), 00235 getNodeFor(BI.getSuccessor(0)), 00236 getNodeFor(BI.getSuccessor(1)))); 00237 } 00238 00239 00240 void SelectionDAGBuilder::visitLoad(LoadInst &LI) { 00241 // FIXME: this won't prevent reordering of loads! 00242 getNodeFor(LI)->setNode(ISD::Load, BB, getNodeFor(LI.getOperand(0))); 00243 } 00244 00245 void SelectionDAGBuilder::visitCall(CallInst &CI) { 00246 SDTB.expandCall(DAG, CI); 00247 } 00248 00249 00250 00251 // SelectionDAG constructor - Just use the SelectionDAGBuilder to do all of the 00252 // dirty work... 00253 SelectionDAG::SelectionDAG(MachineFunction &f, const TargetMachine &tm, 00254 SelectionDAGTargetBuilder &SDTB) 00255 : F(f), TM(tm) { 00256 00257 switch (TM.getTargetData().getPointerSize()) { 00258 default: assert(0 && "Unknown pointer size!"); abort(); 00259 case 1: PointerType = MVT::i8; break; 00260 case 2: PointerType = MVT::i16; break; 00261 case 3: PointerType = MVT::i32; break; 00262 case 4: PointerType = MVT::i64; break; 00263 } 00264 00265 // Create all of the machine basic blocks for the function... building the 00266 // BlockMap. This map is used for PHI node conversion. 00267 const Function &Fn = *F.getFunction(); 00268 for (Function::const_iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 00269 F.getBasicBlockList().push_back(BlockMap[I] = new MachineBasicBlock(I)); 00270 00271 SDTB.expandArguments(*this); 00272 00273 SelectionDAGBuilder SDB(*this, SDTB); 00274 for (Function::const_iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 00275 SDB.visitBB(const_cast<BasicBlock&>(*I)); 00276 Root = SDB.CurRoot; 00277 } 00278