LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

DAGBuilder.cpp

Go to the documentation of this file.
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