lib/CodeGen/SelectionDAG/DAGBuilder.cpp

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