Complete rewrite of the SelectionDAG class.

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

1 files changed, 106 insertions, 319 deletions

diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index 796ee13535..ce5deecf38 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -1,4 +1,4 @@
-//===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG Rep. ----*- C++ -*-===//
+//===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===//
 // 
 //                     The LLVM Compiler Infrastructure
 //
@@ -7,364 +7,151 @@
 // 
 //===----------------------------------------------------------------------===//
 // 
-// This file declares the SelectionDAG class, which is used to represent an LLVM
-// function in a low-level representation suitable for instruction selection.
-// This DAG is constructed as the first step of instruction selection in order
-// to allow implementation of machine specific optimizations and code
-// simplifications.
-//
-// The representation used by the SelectionDAG is a target-independent
-// representation, which is loosly modeled after the GCC RTL representation, but
-// is significantly simpler.
+// This file declares the SelectionDAG class, and transitively defines the
+// SDNode class and subclasses.
 //   
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_SELECTIONDAG_H
 #define LLVM_CODEGEN_SELECTIONDAG_H
 
-#include "llvm/CodeGen/ValueTypes.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/CodeGen/SelectionDAGNodes.h"
 #include <map>
-#include <vector>
-#include <cassert>
+#include <string> // FIXME remove eventually, turning map into const char* map.
 
 namespace llvm {
-
-class Value;
-class Type;
-class Instruction;
-class CallInst;
-class BasicBlock;
-class MachineBasicBlock;
-class MachineFunction;
-class TargetMachine;
-class SelectionDAGNode;
-class SelectionDAGBlock;
-class SelectionDAGBuilder;
-class SelectionDAGTargetBuilder;
-
-/// ISD namespace - This namespace contains an enum which represents all of the
-/// SelectionDAG node types and value types.
+  class TargetLowering;
+  class TargetMachine;
+  class MachineFunction;
+
+/// SelectionDAG class - This is used to represent a portion of an LLVM function
+/// in a low-level Data Dependence DAG representation suitable for instruction
+/// selection.  This DAG is constructed as the first step of instruction
+/// selection in order to allow implementation of machine specific optimizations
+/// and code simplifications.
+///
+/// The representation used by the SelectionDAG is a target-independent
+/// representation, which has some similarities to the GCC RTL representation,
+/// but is significantly more simple, powerful, and is a graph form instead of a
+/// linear form.
 ///
-namespace ISD {
-  enum NodeType {
-    // ChainNode nodes are used to sequence operations within a basic block
-    // which cannot be reordered (such as loads, stores, calls, etc).
-    // BlockChainNodes are used to connect the DAG's for different basic blocks
-    // into one big DAG.
-    ChainNode, BlockChainNode,
-
-    // ProtoNodes are nodes that are only half way constructed.
-    ProtoNode,
-
-    // Leaf nodes
-    Constant, FrameIndex, BasicBlock,
-
-    // Simple binary arithmetic operators
-    Plus, Minus, Times, SDiv, UDiv, SRem, URem,
-
-    // Bitwise operators
-    And, Or, Xor,
-
-    // Comparisons
-    SetEQ, SetNE, SetLT, SetLE, SetGT, SetGE,
-
-    // Control flow instructions
-    Br, BrCond, Switch, Ret, RetVoid,
-
-    // Other operators
-    Load, Store, PHI, Call,
-
-    // Unknown operators, of a specified arity
-    Unspec1, Unspec2
-  };
-}
-
 class SelectionDAG {
-  friend class SelectionDAGBuilder;
-  MachineFunction &F;
   const TargetMachine &TM;
-  MVT::ValueType PointerType;    // The ValueType the target uses for pointers
+  MachineFunction &MF;
 
-  // ValueMap - The SelectionDAGNode for each LLVM value in the function.
-  std::map<const Value*, SelectionDAGNode*> ValueMap;
-
-  // BlockMap - The MachineBasicBlock created for each LLVM BasicBlock
-  std::map<const BasicBlock*, MachineBasicBlock*> BlockMap;
-
-  // Root - The root of the entire DAG
-  SelectionDAGNode *Root;
+  // Root - The root of the entire DAG.  EntryNode - The starting token.
+  SDOperand Root, EntryNode;
 
   // AllNodes - All of the nodes in the DAG
-  std::vector<SelectionDAGNode*> AllNodes;
+  std::vector<SDNode*> AllNodes;
+
+  // Maps to auto-CSE operations.
+  std::map<std::pair<unsigned, std::pair<SDOperand, MVT::ValueType> >,
+           SDNode *> UnaryOps;
+  std::map<std::pair<unsigned, std::pair<SDOperand, SDOperand> >,
+           SDNode *> BinaryOps;
+
+  std::map<std::pair<std::pair<SDOperand, SDOperand>, ISD::CondCode>,
+           SetCCSDNode*> SetCCs;
+
+  std::map<std::pair<SDOperand, std::pair<SDOperand, MVT::ValueType> >,
+           SDNode *> Loads;
+
+  std::map<const GlobalValue*, SDNode*> GlobalValues;
+  std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> Constants;
+  std::map<std::pair<double, MVT::ValueType>, SDNode*> ConstantFPs;
+  std::map<int, SDNode*> FrameIndices;
+  std::map<unsigned, SDNode*> ConstantPoolIndices;
+  std::map<MachineBasicBlock *, SDNode*> BBNodes;
+  std::map<std::string, SDNode*> ExternalSymbols;
 public:
-  /// SelectionDAG constructor - Build a SelectionDAG for the specified
-  /// function.  Implemented in DAGBuilder.cpp
-  ///
-  SelectionDAG(MachineFunction &F, const TargetMachine &TM,
-               SelectionDAGTargetBuilder &SDTB);
+  SelectionDAG(const TargetMachine &tm, MachineFunction &mf) : TM(tm), MF(mf) {
+    EntryNode = Root = getNode(ISD::EntryToken, MVT::Other);
+  }
   ~SelectionDAG();
 
-  /// getValueType - Return the ValueType for the specified LLVM type.  This
-  /// method works on all scalar LLVM types.
-  ///
-  MVT::ValueType getValueType(const Type *Ty) const;
-
-  /// getRoot - Return the root of the current SelectionDAG.
-  ///
-  SelectionDAGNode *getRoot() const { return Root; }
+  MachineFunction &getMachineFunction() const { return MF; }
+  const TargetMachine &getTarget() { return TM; }
 
-  /// getMachineFunction - Return the MachineFunction object that this
-  /// SelectionDAG corresponds to.
+  /// getRoot - Return the root tag of the SelectionDAG.
   ///
-  MachineFunction &getMachineFunction() const { return F; }
+  const SDOperand &getRoot() const { return Root; }
 
-  //===--------------------------------------------------------------------===//
-  // Addition and updating methods
-  //
+  /// getEntryNode - Return the token chain corresponding to the entry of the
+  /// function.
+  const SDOperand &getEntryNode() const { return EntryNode; }
 
-  /// addNode - Add the specified node to the SelectionDAG so that it will be
-  /// deleted when the DAG is...
+  /// setRoot - Set the current root tag of the SelectionDAG.
   ///
-  SelectionDAGNode *addNode(SelectionDAGNode *N) {
-    AllNodes.push_back(N);
-    return N;
-  }
+  const SDOperand &setRoot(SDOperand N) { return Root = N; }
 
-  /// addNodeForValue - Add the specified node to the SelectionDAG so that it
-  /// will be deleted when the DAG is... and update the value map to indicate
-  /// that the specified DAG node computes the value.  Note that it is an error
-  /// to specify multiple DAG nodes that compute the same value.
+  /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
+  /// compatible with the target instruction selector, as indicated by the
+  /// TargetLowering object.
   ///
-  SelectionDAGNode *addNodeForValue(SelectionDAGNode *N, const Value *V) {
-    assert(ValueMap.count(V) == 0 && "Value already has a DAG node!");
-    return addNode(ValueMap[V] = N);
+  /// Note that this is an involved process that may invalidate pointers into
+  /// the graph.
+  void Legalize(TargetLowering &TLI);
+
+  SDOperand getConstant(uint64_t Val, MVT::ValueType VT);
+  SDOperand getConstantFP(double Val, MVT::ValueType VT);
+  SDOperand getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT);
+  SDOperand getFrameIndex(int FI, MVT::ValueType VT);
+  SDOperand getConstantPool(unsigned CPIdx, MVT::ValueType VT);
+  SDOperand getBasicBlock(MachineBasicBlock *MBB);
+  SDOperand getExternalSymbol(const char *Sym, MVT::ValueType VT);
+
+  SDOperand getCopyToReg(SDOperand Chain, SDOperand N, unsigned VReg) {
+    // Note: these are auto-CSE'd because the caller doesn't make requests that
+    // could cause duplicates to occur.
+    SDNode *NN = new CopyRegSDNode(Chain, N, VReg);
+    AllNodes.push_back(NN);
+    return SDOperand(NN, 0);
   }
 
-  void dump() const;
-private:
-  void addInstructionToDAG(const Instruction &I, const BasicBlock &BB);
-};
-
-
-/// SelectionDAGReducedValue - During the reducer pass we need the ability to
-/// add an arbitrary (but usually 1 or 0) number of arbitrarily sized values to
-/// the selection DAG.  Because of this, we represent these values as a singly
-/// linked list of values attached to the DAGNode.  We end up putting the
-/// arbitrary state for the value in subclasses of this node.
-///
-/// Note that this class does not have a virtual dtor, this is because we know
-/// that the subclasses will not hold state that needs to be destroyed.
-///
-class SelectionDAGReducedValue {
-  unsigned Code;
-  SelectionDAGReducedValue *Next;
-public:
-  SelectionDAGReducedValue(unsigned C) : Code(C), Next(0) {}
-
-  /// getValueCode - Return the code for this reducer value...
-  ///
-  unsigned getValueCode() const { return Code; }
-  
-  /// getNext - Return the next value in the list
-  ///
-  const SelectionDAGReducedValue *getNext() const { return Next; }
-  void setNext(SelectionDAGReducedValue *N) { Next = N; }
-
-  SelectionDAGReducedValue *getNext() { return Next; }
-};
-
-
-
-/// SelectionDAGNode - Represents one node in the selection DAG.
-///
-class SelectionDAGNode {
-  std::vector<SelectionDAGNode*> Uses;
-  ISD::NodeType  NodeType;
-  MVT::ValueType ValueType;
-  MachineBasicBlock *BB;
-  SelectionDAGReducedValue *ValList;
-
-  /// Costs - Each pair of elements of 'Costs' contains the cost of producing
-  /// the value with the target specific slot number and the production number
-  /// to use to produce it.  A zero value for the production number indicates
-  /// that the cost has not yet been computed.
-  unsigned *Costs;
-public:
-  SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT,
-                   MachineBasicBlock *bb = 0) 
-    : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {}
-
-  SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
-                   SelectionDAGNode *N)
-    : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
-    assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
-    Uses.reserve(1); Uses.push_back(N);
-  }
-  SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
-                   SelectionDAGNode *N1, SelectionDAGNode *N2)
-    : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
-    assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
-    Uses.reserve(2); Uses.push_back(N1); Uses.push_back(N2);
-  }
-  SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
-                   SelectionDAGNode *N1, SelectionDAGNode *N2,
-                   SelectionDAGNode *N3)
-    : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
-    assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
-    Uses.reserve(3); Uses.push_back(N1); Uses.push_back(N2); Uses.push_back(N3);
-  }
-
-  ~SelectionDAGNode() { delete [] Costs; delete ValList; }
-
-  void setNode(ISD::NodeType NT, MachineBasicBlock *bb) {
-    assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
-    NodeType = NT; BB = bb;
-  }
-  void setNode(ISD::NodeType NT, MachineBasicBlock *bb, SelectionDAGNode *N) {
-    assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
-    NodeType = NT; BB = bb; Uses.reserve(1); Uses.push_back(N);
-  }
-  void setNode(ISD::NodeType NT, MachineBasicBlock *bb, 
-               SelectionDAGNode *N1, SelectionDAGNode *N2) {
-    assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
-    NodeType = NT; BB = bb;
-    Uses.reserve(1); Uses.push_back(N1); Uses.push_back(N2);
+  SDOperand getCopyFromReg(unsigned VReg, MVT::ValueType VT) {
+    // Note: These nodes are auto-CSE'd by the caller of this method.
+    SDNode *NN = new CopyRegSDNode(VReg, VT);
+    AllNodes.push_back(NN);
+    return SDOperand(NN, 0);
   }
 
-  //===--------------------------------------------------------------------===//
-  //  Accessors
-  //
-  ISD::NodeType  getNodeType()  const { return NodeType; }
-  MVT::ValueType getValueType() const { return ValueType; }
-  MachineBasicBlock *getBB() const { return BB; }
-
-  SelectionDAGNode *getUse(unsigned Num) {
-    assert(Num < Uses.size() && "Invalid child # of SelectionDAGNode!");
-    return Uses[Num];
-  }
-
-  template<class Type>
-  Type *getValue(unsigned Code) const {
-    SelectionDAGReducedValue *Vals = ValList;
-    while (1) {
-      assert(Vals && "Code does not exist in this list!");
-      if (Vals->getValueCode() == Code)
-        return (Type*)Vals;
-      Vals = Vals->getNext();
-    }
-  }
-
-  template<class Type>
-  Type *hasValue(unsigned Code) const {
-    SelectionDAGReducedValue *Vals = ValList;
-    while (Vals) {
-      if (Vals->getValueCode() == Code)
-        return (Type*)Vals;
-      Vals = Vals->getNext();
-    }
-    return false;
-  }
-
-  void addValue(SelectionDAGReducedValue *New) {
-    assert(New->getNext() == 0);
-    New->setNext(ValList);
-    ValList = New;
+  /// getCall - Note that this destroys the vector of RetVals passed in.
+  ///
+  SDNode *getCall(std::vector<MVT::ValueType> &RetVals, SDOperand Chain,
+                  SDOperand Callee) {
+    SDNode *NN = new SDNode(ISD::CALL, Chain, Callee);
+    NN->setValueTypes(RetVals);
+    AllNodes.push_back(NN);
+    return NN;
   }
 
-  //===--------------------------------------------------------------------===//
-  // Utility methods used by the pattern matching instruction selector
-  //
+  SDOperand getSetCC(ISD::CondCode, SDOperand LHS, SDOperand RHS);
 
-  /// getPatternFor - Return the pattern selected to compute the specified slot,
-  /// or zero if there is no pattern yet.
+  /// getNode - Gets or creates the specified node.
   ///
-  unsigned getPatternFor(unsigned Slot) const {
-    return Costs ? Costs[Slot*2] : 0;
-  }
-
-  /// getCostFor - Return the cost to compute the value corresponding to Slot.
+  SDOperand getNode(unsigned Opcode, MVT::ValueType VT);
+  SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N);
+  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
+                    SDOperand N1, SDOperand N2);
+  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
+                    SDOperand N1, SDOperand N2, SDOperand N3);
+  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
+                    std::vector<SDOperand> &Children);
+
+  /// getLoad - Loads are not normal binary operators: their result type is not
+  /// determined by their operands, and they produce a value AND a token chain.
   ///
-  unsigned getCostFor(unsigned Slot) const {
-    return Costs ? Costs[Slot*2+1] : 0;
-  }
+  SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr);
 
-  /// setPatternCostFor - Sets the pattern and the cost for the specified slot
-  /// to the specified values.  This allocates the Costs vector if necessary, so
-  /// you must specify the maximum number of slots that may be used.
-  ///
-  void setPatternCostFor(unsigned Slot, unsigned Pattern, unsigned Cost,
-                         unsigned NumSlots) {
-    if (Costs == 0) {
-      Costs = new unsigned[NumSlots*2];
-      for (unsigned i = 0; i != NumSlots*2; ++i) Costs[i] = 0;
-    }
-    Costs[Slot*2] = Pattern;
-    Costs[Slot*2+1] = Cost;
+  void replaceAllUsesWith(SDOperand Old, SDOperand New) {
+    assert(Old != New && "RAUW self!");
+    assert(0 && "Unimplemented!");
   }
 
   void dump() const;
-private:
-  void printit(unsigned Offset, unsigned &LastID,
-               std::map<const SelectionDAGNode*, unsigned> &NodeIDs) const;
 };
 
-
-/// SelectionDAGTargetBuilder - This class must be implemented by the target, to
-/// indicate how to perform the extremely target-specific tasks of building DAG
-/// nodes to represent the calling convention used by the target.
-///
-struct SelectionDAGTargetBuilder {
-  /// expandArguments - This method is called once by the SelectionDAG
-  /// construction mechanisms to add DAG nodes for each formal argument to the
-  /// current function.  If any of the incoming arguments lives on the stack,
-  /// this method should also create the stack slots for the arguments as
-  /// necessary.
-  virtual void expandArguments(SelectionDAG &SD) = 0;
-
-  /// expandCall - This method is called once per function call by the
-  /// SelectionDAG construction algorithm.  It must add DAG nodes to the
-  /// SelectionDAG specified to perform that call.
-  virtual void expandCall(SelectionDAG &SD, CallInst &CI) = 0;
-};
-
-namespace ISD {
-  enum {   // Builtin Slot numbers
-    Constant_i1_Slot,
-    Constant_i8_Slot,
-    Constant_i16_Slot,
-    Constant_i32_Slot,
-    Constant_i64_Slot,
-    Constant_f32_Slot,
-    Constant_f64_Slot,
-
-    FrameIndex_i32_Slot,
-    FrameIndex_i64_Slot,
-    BasicBlock_i32_Slot,
-    BasicBlock_i64_Slot,
-    NumBuiltinSlots
-  };
 }
 
-template<typename ValType, unsigned NodeCode>
-struct ReducedValue : public SelectionDAGReducedValue {
-  ReducedValue(const ValType &V) : SelectionDAGReducedValue(NodeCode), Val(V) {}
-  ValType Val;
-};
-
-typedef ReducedValue<int, ISD::FrameIndex_i32_Slot > ReducedValue_FrameIndex_i32;
-typedef ReducedValue<int, ISD::FrameIndex_i64_Slot > ReducedValue_FrameIndex_i64;
-typedef ReducedValue<MachineBasicBlock*, ISD::BasicBlock_i32_Slot > ReducedValue_BasicBlock_i32;
-typedef ReducedValue<MachineBasicBlock*, ISD::BasicBlock_i64_Slot > ReducedValue_BasicBlock_i64;
-
-typedef ReducedValue<bool          , ISD::Constant_i1_Slot > ReducedValue_Constant_i1;
-typedef ReducedValue<unsigned char , ISD::Constant_i8_Slot > ReducedValue_Constant_i8;
-typedef ReducedValue<unsigned short, ISD::Constant_i16_Slot> ReducedValue_Constant_i16;
-typedef ReducedValue<unsigned      , ISD::Constant_i32_Slot> ReducedValue_Constant_i32;
-typedef ReducedValue<uint64_t      , ISD::Constant_i64_Slot> ReducedValue_Constant_i64;
-typedef ReducedValue<float         , ISD::Constant_f32_Slot> ReducedValue_Constant_f32;
-typedef ReducedValue<double        , ISD::Constant_f64_Slot> ReducedValue_Constant_f64;
-
-} // End llvm namespace
-
 #endif