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

3 files changed, 332 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;
+}
diff --git a/lib/CodeGen/SelectionDAG/Makefile b/lib/CodeGen/SelectionDAG/Makefile
new file mode 100644
index 0000000000..77fad10f39
--- /dev/null
+++ b/lib/CodeGen/SelectionDAG/Makefile
@@ -0,0 +1,5 @@
+LEVEL = ../../..
+PARALLEL_DIRS =
+LIBRARYNAME = selection
+
+include $(LEVEL)/Makefile.common
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
new file mode 100644
index 0000000000..181abea922
--- /dev/null
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -0,0 +1,105 @@
+//===-- SelectionDAG.cpp - Implement the SelectionDAG* classes ------------===//
+//
+// This file implements the SelectionDAG* classes, which are used to perform
+// DAG-based instruction selection in a target-specific manner.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/SelectionDAG.h"
+#include "llvm/Type.h"
+
+SelectionDAG::~SelectionDAG() {
+  for (unsigned i = 0, e = AllNodes.size(); i != e; ++i)
+    delete AllNodes[i];
+}
+
+
+/// dump - Print out the current Selection DAG...
+void SelectionDAG::dump() const {
+  Root->dump();  // Print from the root...
+}
+
+/// getValueType - Return the ValueType for the specified LLVM type.  This
+/// method works on all scalar LLVM types.
+///
+MVT::ValueType SelectionDAG::getValueType(const Type *Ty) const {
+  switch (Ty->getPrimitiveID()) {
+  case Type::VoidTyID: assert(0 && "Void type object in getValueType!");
+  default: assert(0 && "Unknown type in DAGBuilder!\n");
+  case Type::BoolTyID:    return MVT::i1;
+  case Type::SByteTyID:
+  case Type::UByteTyID:   return MVT::i8;
+  case Type::ShortTyID:
+  case Type::UShortTyID:  return MVT::i16;
+  case Type::IntTyID:
+  case Type::UIntTyID:    return MVT::i32;
+  case Type::LongTyID:
+  case Type::ULongTyID:   return MVT::i64;
+  case Type::FloatTyID:   return MVT::f32;
+  case Type::DoubleTyID:  return MVT::f64;
+  case Type::PointerTyID: return PointerType;
+  }
+}
+
+void SelectionDAGNode::dump() const {
+  // Print out the DAG in post-order
+  std::map<const SelectionDAGNode*, unsigned> NodeIDs;
+  unsigned ID = 0;
+  printit(0, ID, NodeIDs);
+}
+
+void SelectionDAGNode::printit(unsigned Offset, unsigned &LastID,
+                               std::map<const SelectionDAGNode*,
+                                        unsigned> &NodeIDs) const {
+  if (!NodeIDs.count(this)) {
+    // Emit all of the uses first...
+    for (unsigned i = 0, e = Uses.size(); i != e; ++i)
+      Uses[i]->printit(Offset+1, LastID, NodeIDs);
+
+    NodeIDs[this] = LastID++;
+
+    std::cerr << std::string(Offset, ' ') << "#" << LastID-1 << " ";
+  } else {
+    // Node has already been emitted...
+    std::cerr << std::string(Offset, ' ') << "#" << NodeIDs[this] << " ";
+  }
+
+  switch (ValueType) {
+  case MVT::isVoid: std::cerr << "V:"; break;
+  case MVT::i1:   std::cerr << "i1:"; break;
+  case MVT::i8:   std::cerr << "i8:"; break;
+  case MVT::i16:  std::cerr << "i16:"; break;
+  case MVT::i32:  std::cerr << "i32:"; break;
+  case MVT::i64:  std::cerr << "i64:"; break;
+  case MVT::f32:  std::cerr << "f32:"; break;
+  case MVT::f64:  std::cerr << "f64:"; break;
+  default: assert(0 && "Invalid node ValueType!");
+  }
+  switch (NodeType) {
+  case ISD::ChainNode:      std::cerr << "ChainNode"; break;
+  case ISD::BlockChainNode: std::cerr << "BlockChainNode"; break;
+  case ISD::ProtoNode:      std::cerr << "ProtoNode"; break;
+  case ISD::Constant:       std::cerr << "Constant"; break;
+  case ISD::FrameIndex:     std::cerr << "FrameIndex"; break;
+  case ISD::Plus:           std::cerr << "Plus"; break;
+  case ISD::Minus:          std::cerr << "Minus"; break;
+  case ISD::Times:          std::cerr << "Times"; break;
+  case ISD::SDiv:           std::cerr << "SDiv"; break;
+  case ISD::UDiv:           std::cerr << "UDiv"; break;
+  case ISD::SRem:           std::cerr << "SRem"; break;
+  case ISD::URem:           std::cerr << "URem"; break;
+  case ISD::And:            std::cerr << "And"; break;
+  case ISD::Or:             std::cerr << "Or"; break;
+  case ISD::Xor:            std::cerr << "Xor"; break;
+  case ISD::Br:             std::cerr << "Br"; break;
+  case ISD::Switch:         std::cerr << "Switch"; break;
+  case ISD::Ret:            std::cerr << "Ret"; break;
+  case ISD::RetVoid:        std::cerr << "RetVoid"; break;
+  case ISD::Load:           std::cerr << "Load"; break;
+  case ISD::Store:          std::cerr << "Store"; break;
+  case ISD::PHI:            std::cerr << "PHI"; break;
+  case ISD::Call:           std::cerr << "Call"; break;
+  }
+
+  std::cerr << "\n";
+}