lib/CodeGen/SelectionDAG/DAGBuilder.cpp

   1 //===-- DAGBuilder.cpp - Turn an LLVM BasicBlock into a DAG for selection -===//
   2 //
   3 // This file turns an LLVM BasicBlock into a target independent SelectionDAG in
   4 // preparation for target specific optimizations and instruction selection.
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #include "llvm/CodeGen/SelectionDAG.h"
   9 #include "llvm/Constants.h"
  10 #include "llvm/Function.h"
  11 #include "llvm/Instructions.h"
  12 #include "llvm/Type.h"
  13 #include "llvm/CodeGen/MachineFunction.h"
  14 #include "llvm/Target/TargetMachine.h"
  15 #include "llvm/Support/InstVisitor.h"
  16
  17 struct SelectionDAGBuilder : public InstVisitor<SelectionDAGBuilder> {
  18   // DAG - the current dag we are building.
  19   SelectionDAG &DAG;
  20
  21   // SDTB - The target-specific builder interface, which indicates how to expand
  22   // extremely target-specific aspects of the representation, such as function
  23   // calls and arguments.
  24   SelectionDAGTargetBuilder &SDTB;
  25
  26   // BB - The current machine basic block we are working on.
  27   MachineBasicBlock *BB;
  28
  29   // CurRoot - The root built for the current basic block.
  30   SelectionDAGNode *CurRoot;
  31
  32   SelectionDAGBuilder(SelectionDAG &dag, SelectionDAGTargetBuilder &sdtb)
  33     : DAG(dag), SDTB(sdtb), BB(0), CurRoot(0) {}
  34
  35   void visitBB(BasicBlock &bb);
  36
  37   // Visitation methods for instructions: Create the appropriate DAG nodes for
  38   // the instruction.
  39   void visitAdd(BinaryOperator &BO);
  40   void visitSub(BinaryOperator &BO);
  41   void visitMul(BinaryOperator &BO);
  42
  43   void visitAnd(BinaryOperator &BO);
  44   void visitOr (BinaryOperator &BO);
  45   void visitXor(BinaryOperator &BO);
  46
  47   void visitSetEQ(BinaryOperator &BO);
  48
  49   void visitLoad(LoadInst &LI);
  50   void visitCall(CallInst &CI);
  51
  52   void visitBr(BranchInst &BI);
  53   void visitRet(ReturnInst &RI);
  54
  55   void visitInstruction(Instruction &I) {
  56     std::cerr << "DAGBuilder: Cannot instruction select: " << I;
  57     abort();
  58   }
  59
  60 private:
  61   SelectionDAGNode *getNodeFor(Value *V);
  62   SelectionDAGNode *getNodeFor(Value &V) { return getNodeFor(&V); }
  63
  64   SelectionDAGNode *addSeqNode(SelectionDAGNode *N);
  65 };
  66
  67 /// addSeqNode - The same as addNode, but the node is also included in the
  68 /// sequence nodes for this block.  This method should be called for any
  69 /// instructions which have a specified sequence they must be evaluated in.
  70 ///
  71 SelectionDAGNode *SelectionDAGBuilder::addSeqNode(SelectionDAGNode *N) {
  72   DAG.addNode(N);   // First, add the node to the selection DAG
  73
  74   if (!CurRoot)
  75     CurRoot = N;
  76   else {
  77     // Create and add a new chain node for the existing root and this node...
  78     CurRoot = DAG.addNode(new SelectionDAGNode(ISD::ChainNode, MVT::isVoid,
  79                                                BB, CurRoot, N));
  80   }
  81   return N;
  82 }
  83
  84 /// getNodeFor - This method returns the SelectionDAGNode for the specified LLVM
  85 /// value, creating a node as necessary.
  86 ///
  87 SelectionDAGNode *SelectionDAGBuilder::getNodeFor(Value *V) {
  88   // If we already have the entry, return it.
  89   SelectionDAGNode*& Entry = DAG.ValueMap[V];
  90   if (Entry) return Entry;
  91
  92   // Otherwise, we need to create a node to return now... start by figuring out
  93   // which type the node will be...
  94   MVT::ValueType ValueType = DAG.getValueType(V->getType());
  95
  96   if (Instruction *I = dyn_cast<Instruction>(V))
  97     // Instructions will be filled in later.  For now, just create and return a
  98     // dummy node.
  99     return Entry = new SelectionDAGNode(ISD::ProtoNode, ValueType);
 100
 101   if (Constant *C = dyn_cast<Constant>(V)) {
 102     if (ConstantBool *CB = dyn_cast<ConstantBool>(C)) {
 103       Entry = new SelectionDAGNode(ISD::Constant, ValueType);
 104       Entry->addValue(new ReducedValue_Constant_i1(CB->getValue()));
 105     } else if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) {
 106       Entry = new SelectionDAGNode(ISD::Constant, ValueType);
 107       switch (ValueType) {
 108       case MVT::i8:
 109         Entry->addValue(new ReducedValue_Constant_i8(CI->getRawValue()));
 110         break;
 111       case MVT::i16:
 112         Entry->addValue(new ReducedValue_Constant_i16(CI->getRawValue()));
 113         break;
 114       case MVT::i32:
 115         Entry->addValue(new ReducedValue_Constant_i32(CI->getRawValue()));
 116         break;
 117       case MVT::i64:
 118         Entry->addValue(new ReducedValue_Constant_i64(CI->getRawValue()));
 119         break;
 120       default:
 121         assert(0 && "Invalid ValueType for an integer constant!");
 122       }
 123
 124     } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
 125       Entry = new SelectionDAGNode(ISD::Constant, ValueType);
 126       if (ValueType == MVT::f32)
 127         Entry->addValue(new ReducedValue_Constant_f32(CFP->getValue()));
 128       else
 129         Entry->addValue(new ReducedValue_Constant_f64(CFP->getValue()));
 130     }
 131     if (Entry) return Entry;
 132   } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
 133     Entry = new SelectionDAGNode(ISD::BasicBlock, ValueType);
 134     Entry->addValue(new ReducedValue_BasicBlock_i32(DAG.BlockMap[BB]));
 135     return Entry;
 136   }
 137
 138   std::cerr << "Unhandled LLVM value in DAG Builder!: " << *V << "\n";
 139   abort();
 140   return 0;
 141 }
 142
 143
 144 // visitBB - This method is used to visit a basic block in the program.  It
 145 // manages the CurRoot instance variable so that all of the visit(Instruction)
 146 // methods can be written to assume that there is only one basic block being
 147 // constructed.
 148 //
 149 void SelectionDAGBuilder::visitBB(BasicBlock &bb) {
 150   BB = DAG.BlockMap[&bb];       // Update BB instance var
 151
 152   // Save the current global DAG...
 153   SelectionDAGNode *OldRoot = CurRoot;
 154   CurRoot = 0;
 155
 156   visit(bb.begin(), bb.end());  // Visit all of the instructions...
 157
 158   if (OldRoot) {
 159     if (!CurRoot)
 160       CurRoot = OldRoot;   // This block had no root of its own..
 161     else {
 162       // The previous basic block AND this basic block had roots, insert a
 163       // block chain node now...
 164       CurRoot = DAG.addNode(new SelectionDAGNode(ISD::BlockChainNode,
 165                                                  MVT::isVoid,
 166                                                  BB, OldRoot, CurRoot));
 167     }
 168   }
 169 }
 170
 171 //===----------------------------------------------------------------------===//
 172 //                         ...Visitation Methods...
 173 //===----------------------------------------------------------------------===//
 174
 175 void SelectionDAGBuilder::visitAdd(BinaryOperator &BO) {
 176   getNodeFor(BO)->setNode(ISD::Plus, BB, getNodeFor(BO.getOperand(0)),
 177                           getNodeFor(BO.getOperand(1)));
 178 }
 179 void SelectionDAGBuilder::visitSub(BinaryOperator &BO) {
 180   getNodeFor(BO)->setNode(ISD::Minus, BB, getNodeFor(BO.getOperand(0)),
 181                           getNodeFor(BO.getOperand(1)));
 182 }
 183 void SelectionDAGBuilder::visitMul(BinaryOperator &BO) {
 184   getNodeFor(BO)->setNode(ISD::Times, BB, getNodeFor(BO.getOperand(0)),
 185                           getNodeFor(BO.getOperand(1)));
 186 }
 187
 188 void SelectionDAGBuilder::visitAnd(BinaryOperator &BO) {
 189   getNodeFor(BO)->setNode(ISD::And, BB, getNodeFor(BO.getOperand(0)),
 190                           getNodeFor(BO.getOperand(1)));
 191 }
 192 void SelectionDAGBuilder::visitOr(BinaryOperator &BO) {
 193   getNodeFor(BO)->setNode(ISD::Or, BB, getNodeFor(BO.getOperand(0)),
 194                           getNodeFor(BO.getOperand(1)));
 195 }
 196 void SelectionDAGBuilder::visitXor(BinaryOperator &BO) {
 197   getNodeFor(BO)->setNode(ISD::Xor, BB, getNodeFor(BO.getOperand(0)),
 198                           getNodeFor(BO.getOperand(1)));
 199 }
 200 void SelectionDAGBuilder::visitSetEQ(BinaryOperator &BO) {
 201   getNodeFor(BO)->setNode(ISD::SetEQ, BB, getNodeFor(BO.getOperand(0)),
 202                           getNodeFor(BO.getOperand(1)));
 203 }
 204
 205
 206 void SelectionDAGBuilder::visitRet(ReturnInst &RI) {
 207   if (RI.getNumOperands()) {         // Value return
 208     addSeqNode(new SelectionDAGNode(ISD::Ret, MVT::isVoid, BB,
 209                                     getNodeFor(RI.getOperand(0))));
 210   } else {                           // Void return
 211     addSeqNode(new SelectionDAGNode(ISD::RetVoid, MVT::isVoid, BB));
 212   }
 213 }
 214
 215
 216 void SelectionDAGBuilder::visitBr(BranchInst &BI) {
 217   if (BI.isUnconditional())
 218     addSeqNode(new SelectionDAGNode(ISD::Br, MVT::isVoid, BB,
 219                                     getNodeFor(BI.getOperand(0))));
 220   else
 221     addSeqNode(new SelectionDAGNode(ISD::BrCond, MVT::isVoid, BB,
 222                                     getNodeFor(BI.getCondition()),
 223                                     getNodeFor(BI.getSuccessor(0)),
 224                                     getNodeFor(BI.getSuccessor(1))));
 225 }
 226
 227
 228 void SelectionDAGBuilder::visitLoad(LoadInst &LI) {
 229   // FIXME: this won't prevent reordering of loads!
 230   getNodeFor(LI)->setNode(ISD::Load, BB, getNodeFor(LI.getOperand(0)));
 231 }
 232
 233 void SelectionDAGBuilder::visitCall(CallInst &CI) {
 234   SDTB.expandCall(DAG, CI);
 235 }
 236
 237
 238
 239 // SelectionDAG constructor - Just use the SelectionDAGBuilder to do all of the
 240 // dirty work...
 241 SelectionDAG::SelectionDAG(MachineFunction &f, const TargetMachine &tm,
 242                            SelectionDAGTargetBuilder &SDTB)
 243   : F(f), TM(tm) {
 244
 245   switch (TM.getTargetData().getPointerSize()) {
 246   default: assert(0 && "Unknown pointer size!"); abort();
 247   case 8:  PointerType = MVT::i8; break;
 248   case 16: PointerType = MVT::i16; break;
 249   case 32: PointerType = MVT::i32; break;
 250   case 64: PointerType = MVT::i64; break;
 251   }
 252
 253   // Create all of the machine basic blocks for the function... building the
 254   // BlockMap.  This map is used for PHI node conversion.
 255   const Function &Fn = *F.getFunction();
 256   for (Function::const_iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
 257     F.getBasicBlockList().push_back(BlockMap[I] = new MachineBasicBlock(I));
 258
 259   SDTB.expandArguments(*this);
 260
 261   SelectionDAGBuilder SDB(*this, SDTB);
 262   for (Function::const_iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
 263     SDB.visitBB(const_cast<BasicBlock&>(*I));
 264   Root = SDB.CurRoot;
 265 }