Initial checkin of SelectionDAG implementation. This is still rough and

unfinished


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7717 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 222 insertions, 0 deletions

diff --git a/lib/CodeGen/SelectionDAG/DAGBuilder.cpp b/lib/CodeGen/SelectionDAG/DAGBuilder.cpp
new file mode 100644
index 0000000000..aafde8ad66
--- /dev/null
+++ b/lib/CodeGen/SelectionDAG/DAGBuilder.cpp
@@ -0,0 +1,222 @@
+//===-- DAGBuilder.cpp - Turn an LLVM BasicBlock into a DAG for selection -===//
+//
+// This file turns an LLVM BasicBlock into a target independent SelectionDAG in
+// preparation for target specific optimizations and instruction selection.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/SelectionDAG.h"
+#include "llvm/Function.h"
+#include "llvm/Instructions.h"
+#include "llvm/Support/InstVisitor.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Type.h"
+#include "llvm/Constants.h"
+
+struct SelectionDAGBuilder : public InstVisitor<SelectionDAGBuilder> {
+  // DAG - the current dag we are building.
+  SelectionDAG &DAG;
+
+  // BB - The current machine basic block we are working on.
+  MachineBasicBlock *BB;
+
+  // CurRoot - The root built for the current basic block.
+  SelectionDAGNode *CurRoot;
+
+  SelectionDAGBuilder(SelectionDAG &dag) : DAG(dag), BB(0), CurRoot(0) {}
+
+  void visitBB(BasicBlock &bb);
+
+  // Visitation methods for instructions: Create the appropriate DAG nodes for
+  // the instruction.
+  void visitAdd(BinaryOperator &BO);
+  void visitSub(BinaryOperator &BO);
+  void visitMul(BinaryOperator &BO);
+  void visitRet(ReturnInst &RI);
+
+  void visitAnd(BinaryOperator &BO);
+  void visitOr (BinaryOperator &BO);
+  void visitXor(BinaryOperator &BO);
+
+  void visitInstruction(Instruction &I) {
+    std::cerr << "Instruction Selection cannot select: " << I;
+    abort();
+  }
+
+private:
+  SelectionDAGNode *getNodeFor(Value *V);
+  SelectionDAGNode *getNodeFor(Value &V) { return getNodeFor(&V); }
+  
+  SelectionDAGNode *addSeqNode(SelectionDAGNode *N);
+};
+
+/// addSeqNode - The same as addNode, but the node is also included in the
+/// sequence nodes for this block.  This method should be called for any
+/// instructions which have a specified sequence they must be evaluated in.
+///
+SelectionDAGNode *SelectionDAGBuilder::addSeqNode(SelectionDAGNode *N) {
+  DAG.addNode(N);   // First, add the node to the selection DAG
+  
+  if (!CurRoot)
+    CurRoot = N;
+  else {
+    // Create and add a new chain node for the existing root and this node...
+    CurRoot = DAG.addNode(new SelectionDAGNode(ISD::ChainNode, MVT::isVoid,
+                                               BB, CurRoot, N));
+  }
+  return N;
+}
+
+/// getNodeFor - This method returns the SelectionDAGNode for the specified LLVM
+/// value, creating a node as necessary.
+///
+SelectionDAGNode *SelectionDAGBuilder::getNodeFor(Value *V) {
+  // If we already have the entry, return it.
+  SelectionDAGNode*& Entry = DAG.ValueMap[V];
+  if (Entry) return Entry;
+  
+  // Otherwise, we need to create a node to return now... start by figuring out
+  // which type the node will be...
+  MVT::ValueType ValueType = DAG.getValueType(V->getType());
+
+  if (Instruction *I = dyn_cast<Instruction>(V))
+    // Instructions will be filled in later.  For now, just create and return a
+    // dummy node.
+    return Entry = new SelectionDAGNode(ISD::ProtoNode, ValueType);
+
+  if (Constant *C = dyn_cast<Constant>(V)) {
+    if (ConstantBool *CB = dyn_cast<ConstantBool>(C)) {
+      Entry = new SelectionDAGNode(ISD::Constant, ValueType);
+      Entry->addValue(new ReducedValue_Constant_i1(CB->getValue()));
+    } else if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) {
+      Entry = new SelectionDAGNode(ISD::Constant, ValueType);
+      switch (ValueType) {
+      case MVT::i8:
+        Entry->addValue(new ReducedValue_Constant_i8(CI->getRawValue()));
+        break;
+      case MVT::i16:
+        Entry->addValue(new ReducedValue_Constant_i16(CI->getRawValue()));
+        break;
+      case MVT::i32:
+        Entry->addValue(new ReducedValue_Constant_i32(CI->getRawValue()));
+        break;
+      case MVT::i64:
+        Entry->addValue(new ReducedValue_Constant_i64(CI->getRawValue()));
+        break;
+      default:
+        assert(0 && "Invalid ValueType for an integer constant!");
+      }
+
+    } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
+      Entry = new SelectionDAGNode(ISD::Constant, ValueType);
+      if (ValueType == MVT::f32)
+        Entry->addValue(new ReducedValue_Constant_f32(CFP->getValue()));
+      else
+        Entry->addValue(new ReducedValue_Constant_f64(CFP->getValue()));
+    }
+    if (Entry) return Entry;
+  }
+
+  std::cerr << "Unhandled LLVM value in DAG Builder!: " << *V << "\n";
+  abort();
+  return 0;
+}
+
+
+// visitBB - This method is used to visit a basic block in the program.  It
+// manages the CurRoot instance variable so that all of the visit(Instruction)
+// methods can be written to assume that there is only one basic block being
+// constructed.
+//
+void SelectionDAGBuilder::visitBB(BasicBlock &bb) {
+  BB = DAG.BlockMap[&bb];       // Update BB instance var
+  
+  // Save the current global DAG...
+  SelectionDAGNode *OldRoot = CurRoot;
+  CurRoot = 0;
+  
+  visit(bb.begin(), bb.end());  // Visit all of the instructions...
+  
+  if (OldRoot) {
+    if (!CurRoot)
+      CurRoot = OldRoot;   // This block had no root of its own..
+    else {
+      // The previous basic block AND this basic block had roots, insert a
+      // block chain node now...
+        CurRoot = DAG.addNode(new SelectionDAGNode(ISD::BlockChainNode,
+                                                   MVT::isVoid,
+                                                   BB, OldRoot, CurRoot));
+    }
+  }
+}
+
+//===----------------------------------------------------------------------===//
+//                         ...Visitation Methods...
+//===----------------------------------------------------------------------===//
+
+void SelectionDAGBuilder::visitAdd(BinaryOperator &BO) {
+  getNodeFor(BO)->setNode(ISD::Plus, BB, getNodeFor(BO.getOperand(0)),
+                          getNodeFor(BO.getOperand(1)));
+}
+void SelectionDAGBuilder::visitSub(BinaryOperator &BO) {
+  getNodeFor(BO)->setNode(ISD::Minus, BB, getNodeFor(BO.getOperand(0)),
+                          getNodeFor(BO.getOperand(1)));
+}
+void SelectionDAGBuilder::visitMul(BinaryOperator &BO) {
+  getNodeFor(BO)->setNode(ISD::Times, BB, getNodeFor(BO.getOperand(0)),
+                          getNodeFor(BO.getOperand(1)));
+}
+
+void SelectionDAGBuilder::visitAnd(BinaryOperator &BO) {
+  getNodeFor(BO)->setNode(ISD::And, BB, getNodeFor(BO.getOperand(0)),
+                          getNodeFor(BO.getOperand(1)));
+}
+void SelectionDAGBuilder::visitOr(BinaryOperator &BO) {
+  getNodeFor(BO)->setNode(ISD::Or, BB, getNodeFor(BO.getOperand(0)),
+                          getNodeFor(BO.getOperand(1)));
+}
+void SelectionDAGBuilder::visitXor(BinaryOperator &BO) {
+  getNodeFor(BO)->setNode(ISD::Xor, BB, getNodeFor(BO.getOperand(0)),
+                          getNodeFor(BO.getOperand(1)));
+}
+
+void SelectionDAGBuilder::visitRet(ReturnInst &RI) {
+  if (RI.getNumOperands()) {         // Value return
+    addSeqNode(new SelectionDAGNode(ISD::Ret, MVT::isVoid, BB,
+                                    getNodeFor(RI.getOperand(0))));
+  } else {                           // Void return
+    addSeqNode(new SelectionDAGNode(ISD::RetVoid, MVT::isVoid, BB));
+  }
+}
+
+
+
+
+// SelectionDAG constructor - Just use the SeelectionDAGBuilder to do all of the
+// dirty work...
+SelectionDAG::SelectionDAG(MachineFunction &f, const TargetMachine &tm,
+                           SelectionDAGTargetBuilder &SDTB)
+  : F(f), TM(tm) {
+
+  switch (TM.getTargetData().getPointerSize()) {
+  default: assert(0 && "Unknown pointer size!"); abort();
+  case 8:  PointerType = MVT::i8; break;
+  case 16: PointerType = MVT::i16; break;
+  case 32: PointerType = MVT::i32; break;
+  case 64: PointerType = MVT::i64; break;
+  }
+
+  // Create all of the machine basic blocks for the function... building the
+  // BlockMap.  This map is used for PHI node conversion.
+  const Function &Fn = *F.getFunction();
+  for (Function::const_iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
+    F.getBasicBlockList().push_back(BlockMap[I] = new MachineBasicBlock(I));
+
+  SDTB.expandArguments(*this, f);
+
+  SelectionDAGBuilder SDB(*this);
+  for (Function::const_iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
+    SDB.visitBB(const_cast<BasicBlock&>(*I));
+  Root = SDB.CurRoot;
+}