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