X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FRegAllocPBQP.h;h=6046e46547b207a71db1462436609b9276c33355;hb=579cebfb15c5f80cc8bbc7d51da9f7827424125a;hp=3d242f1bebe1549f0e80809fc7aef976e856041e;hpb=96fc0d298c2ae67f8d68de6ffcf068f2c7162346;p=oota-llvm.git

diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h
index 3d242f1bebe..6046e46547b 100644
--- a/include/llvm/CodeGen/RegAllocPBQP.h
+++ b/include/llvm/CodeGen/RegAllocPBQP.h
@@ -17,12 +17,15 @@
 #define LLVM_CODEGEN_REGALLOCPBQP_H
 
 #include "llvm/CodeGen/MachineFunctionPass.h"
-#include "llvm/CodeGen/PBQPRAConstraint.h"
 #include "llvm/CodeGen/PBQP/CostAllocator.h"
 #include "llvm/CodeGen/PBQP/ReductionRules.h"
+#include "llvm/CodeGen/PBQPRAConstraint.h"
 #include "llvm/Support/ErrorHandling.h"
 
 namespace llvm {
+
+class raw_ostream;
+
 namespace PBQP {
 namespace RegAlloc {
 
@@ -62,52 +65,227 @@ public:
     delete[] ColCounts;
   }
 
-  ~MatrixMetadata() {
-    delete[] UnsafeRows;
-    delete[] UnsafeCols;
-  }
-
   unsigned getWorstRow() const { return WorstRow; }
   unsigned getWorstCol() const { return WorstCol; }
-  const bool* getUnsafeRows() const { return UnsafeRows; }
-  const bool* getUnsafeCols() const { return UnsafeCols; }
+  const bool* getUnsafeRows() const { return UnsafeRows.get(); }
+  const bool* getUnsafeCols() const { return UnsafeCols.get(); }
 
 private:
   unsigned WorstRow, WorstCol;
-  bool* UnsafeRows;
-  bool* UnsafeCols;
+  std::unique_ptr<bool[]> UnsafeRows;
+  std::unique_ptr<bool[]> UnsafeCols;
+};
+
+/// \brief Holds a vector of the allowed physical regs for a vreg.
+class AllowedRegVector {
+  friend hash_code hash_value(const AllowedRegVector &);
+public:
+
+  AllowedRegVector() : NumOpts(0), Opts(nullptr) {}
+
+  AllowedRegVector(const std::vector<unsigned> &OptVec)
+    : NumOpts(OptVec.size()), Opts(new unsigned[NumOpts]) {
+    std::copy(OptVec.begin(), OptVec.end(), Opts.get());
+  }
+
+  AllowedRegVector(const AllowedRegVector &Other)
+    : NumOpts(Other.NumOpts), Opts(new unsigned[NumOpts]) {
+    std::copy(Other.Opts.get(), Other.Opts.get() + NumOpts, Opts.get());
+  }
+
+  AllowedRegVector(AllowedRegVector &&Other)
+    : NumOpts(std::move(Other.NumOpts)), Opts(std::move(Other.Opts)) {}
+
+  AllowedRegVector& operator=(const AllowedRegVector &Other) {
+    NumOpts = Other.NumOpts;
+    Opts.reset(new unsigned[NumOpts]);
+    std::copy(Other.Opts.get(), Other.Opts.get() + NumOpts, Opts.get());
+    return *this;
+  }
+
+  AllowedRegVector& operator=(AllowedRegVector &&Other) {
+    NumOpts = std::move(Other.NumOpts);
+    Opts = std::move(Other.Opts);
+    return *this;
+  }
+
+  unsigned size() const { return NumOpts; }
+  unsigned operator[](size_t I) const { return Opts[I]; }
+
+  bool operator==(const AllowedRegVector &Other) const {
+    if (NumOpts != Other.NumOpts)
+      return false;
+    return std::equal(Opts.get(), Opts.get() + NumOpts, Other.Opts.get());
+  }
+
+  bool operator!=(const AllowedRegVector &Other) const {
+    return !(*this == Other);
+  }
+
+private:
+  unsigned NumOpts;
+  std::unique_ptr<unsigned[]> Opts;
+};
+
+inline hash_code hash_value(const AllowedRegVector &OptRegs) {
+  unsigned *OStart = OptRegs.Opts.get();
+  unsigned *OEnd = OptRegs.Opts.get() + OptRegs.NumOpts;
+  return hash_combine(OptRegs.NumOpts,
+                      hash_combine_range(OStart, OEnd));
+}
+
+/// \brief Holds graph-level metadata relevent to PBQP RA problems.
+class GraphMetadata {
+private:
+  typedef ValuePool<AllowedRegVector> AllowedRegVecPool;
+public:
+
+  typedef AllowedRegVecPool::PoolRef AllowedRegVecRef;
+
+  GraphMetadata(MachineFunction &MF,
+                LiveIntervals &LIS,
+                MachineBlockFrequencyInfo &MBFI)
+    : MF(MF), LIS(LIS), MBFI(MBFI) {}
+
+  MachineFunction &MF;
+  LiveIntervals &LIS;
+  MachineBlockFrequencyInfo &MBFI;
+
+  void setNodeIdForVReg(unsigned VReg, GraphBase::NodeId NId) {
+    VRegToNodeId[VReg] = NId;
+  }
+
+  GraphBase::NodeId getNodeIdForVReg(unsigned VReg) const {
+    auto VRegItr = VRegToNodeId.find(VReg);
+    if (VRegItr == VRegToNodeId.end())
+      return GraphBase::invalidNodeId();
+    return VRegItr->second;
+  }
+
+  void eraseNodeIdForVReg(unsigned VReg) {
+    VRegToNodeId.erase(VReg);
+  }
+
+  AllowedRegVecRef getAllowedRegs(AllowedRegVector Allowed) {
+    return AllowedRegVecs.getValue(std::move(Allowed));
+  }
+
+private:
+  DenseMap<unsigned, GraphBase::NodeId> VRegToNodeId;
+  AllowedRegVecPool AllowedRegVecs;
 };
 
+/// \brief Holds solver state and other metadata relevant to each PBQP RA node.
 class NodeMetadata {
 public:
-  typedef std::vector<unsigned> OptionToRegMap;
+  typedef RegAlloc::AllowedRegVector AllowedRegVector;
+
+  // The node's reduction state. The order in this enum is important,
+  // as it is assumed nodes can only progress up (i.e. towards being
+  // optimally reducible) when reducing the graph.
+  typedef enum {
+    Unprocessed,
+    NotProvablyAllocatable,
+    ConservativelyAllocatable,
+    OptimallyReducible
+  } ReductionState;
+
+  NodeMetadata()
+    : RS(Unprocessed), NumOpts(0), DeniedOpts(0), OptUnsafeEdges(nullptr),
+      VReg(0)
+#ifndef NDEBUG
+      , everConservativelyAllocatable(false)
+#endif
+      {}
+
+  // FIXME: Re-implementing default behavior to work around MSVC. Remove once
+  // MSVC synthesizes move constructors properly.
+  NodeMetadata(const NodeMetadata &Other)
+    : RS(Other.RS), NumOpts(Other.NumOpts), DeniedOpts(Other.DeniedOpts),
+      OptUnsafeEdges(new unsigned[NumOpts]), VReg(Other.VReg),
+      AllowedRegs(Other.AllowedRegs)
+#ifndef NDEBUG
+      , everConservativelyAllocatable(Other.everConservativelyAllocatable)
+#endif
+  {
+    if (NumOpts > 0) {
+      std::copy(&Other.OptUnsafeEdges[0], &Other.OptUnsafeEdges[NumOpts],
+                &OptUnsafeEdges[0]);
+    }
+  }
 
-  typedef enum { Unprocessed,
-                 OptimallyReducible,
-                 ConservativelyAllocatable,
-                 NotProvablyAllocatable } ReductionState;
+  // FIXME: Re-implementing default behavior to work around MSVC. Remove once
+  // MSVC synthesizes move constructors properly.
+  NodeMetadata(NodeMetadata &&Other)
+    : RS(Other.RS), NumOpts(Other.NumOpts), DeniedOpts(Other.DeniedOpts),
+      OptUnsafeEdges(std::move(Other.OptUnsafeEdges)), VReg(Other.VReg),
+      AllowedRegs(std::move(Other.AllowedRegs))
+#ifndef NDEBUG
+      , everConservativelyAllocatable(Other.everConservativelyAllocatable)
+#endif
+  {}
+
+  // FIXME: Re-implementing default behavior to work around MSVC. Remove once
+  // MSVC synthesizes move constructors properly.
+  NodeMetadata& operator=(const NodeMetadata &Other) {
+    RS = Other.RS;
+    NumOpts = Other.NumOpts;
+    DeniedOpts = Other.DeniedOpts;
+    OptUnsafeEdges.reset(new unsigned[NumOpts]);
+    std::copy(Other.OptUnsafeEdges.get(), Other.OptUnsafeEdges.get() + NumOpts,
+              OptUnsafeEdges.get());
+    VReg = Other.VReg;
+    AllowedRegs = Other.AllowedRegs;
+#ifndef NDEBUG
+    everConservativelyAllocatable = Other.everConservativelyAllocatable;
+#endif
+    return *this;
+  }
 
-  NodeMetadata() : RS(Unprocessed), DeniedOpts(0), OptUnsafeEdges(nullptr){}
-  ~NodeMetadata() { delete[] OptUnsafeEdges; }
+  // FIXME: Re-implementing default behavior to work around MSVC. Remove once
+  // MSVC synthesizes move constructors properly.
+  NodeMetadata& operator=(NodeMetadata &&Other) {
+    RS = Other.RS;
+    NumOpts = Other.NumOpts;
+    DeniedOpts = Other.DeniedOpts;
+    OptUnsafeEdges = std::move(Other.OptUnsafeEdges);
+    VReg = Other.VReg;
+    AllowedRegs = std::move(Other.AllowedRegs);
+#ifndef NDEBUG
+    everConservativelyAllocatable = Other.everConservativelyAllocatable;
+#endif
+    return *this;
+  }
 
   void setVReg(unsigned VReg) { this->VReg = VReg; }
   unsigned getVReg() const { return VReg; }
 
-  void setOptionRegs(OptionToRegMap OptionRegs) {
-    this->OptionRegs = std::move(OptionRegs);
+  void setAllowedRegs(GraphMetadata::AllowedRegVecRef AllowedRegs) {
+    this->AllowedRegs = std::move(AllowedRegs);
   }
-  const OptionToRegMap& getOptionRegs() const { return OptionRegs; }
+  const AllowedRegVector& getAllowedRegs() const { return *AllowedRegs; }
 
   void setup(const Vector& Costs) {
     NumOpts = Costs.getLength() - 1;
-    OptUnsafeEdges = new unsigned[NumOpts]();
+    OptUnsafeEdges = std::unique_ptr<unsigned[]>(new unsigned[NumOpts]());
   }
 
   ReductionState getReductionState() const { return RS; }
-  void setReductionState(ReductionState RS) { this->RS = RS; }
+  void setReductionState(ReductionState RS) {
+    assert(RS >= this->RS && "A node's reduction state can not be downgraded");
+    this->RS = RS;
+
+#ifndef NDEBUG
+    // Remember this state to assert later that a non-infinite register
+    // option was available.
+    if (RS == ConservativelyAllocatable)
+      everConservativelyAllocatable = true;
+#endif
+  }
+
 
   void handleAddEdge(const MatrixMetadata& MD, bool Transpose) {
-    DeniedOpts += Transpose ? MD.getWorstCol() : MD.getWorstRow();
+    DeniedOpts += Transpose ? MD.getWorstRow() : MD.getWorstCol();
     const bool* UnsafeOpts =
       Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
     for (unsigned i = 0; i < NumOpts; ++i)
@@ -115,7 +293,7 @@ public:
   }
 
   void handleRemoveEdge(const MatrixMetadata& MD, bool Transpose) {
-    DeniedOpts -= Transpose ? MD.getWorstCol() : MD.getWorstRow();
+    DeniedOpts -= Transpose ? MD.getWorstRow() : MD.getWorstCol();
     const bool* UnsafeOpts =
       Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
     for (unsigned i = 0; i < NumOpts; ++i)
@@ -124,17 +302,27 @@ public:
 
   bool isConservativelyAllocatable() const {
     return (DeniedOpts < NumOpts) ||
-      (std::find(OptUnsafeEdges, OptUnsafeEdges + NumOpts, 0) !=
-       OptUnsafeEdges + NumOpts);
+      (std::find(&OptUnsafeEdges[0], &OptUnsafeEdges[NumOpts], 0) !=
+       &OptUnsafeEdges[NumOpts]);
+  }
+
+#ifndef NDEBUG
+  bool wasConservativelyAllocatable() const {
+    return everConservativelyAllocatable;
   }
+#endif
 
 private:
   ReductionState RS;
   unsigned NumOpts;
   unsigned DeniedOpts;
-  unsigned* OptUnsafeEdges;
+  std::unique_ptr<unsigned[]> OptUnsafeEdges;
   unsigned VReg;
-  OptionToRegMap OptionRegs;
+  GraphMetadata::AllowedRegVecRef AllowedRegs;
+
+#ifndef NDEBUG
+  bool everConservativelyAllocatable;
+#endif
 };
 
 class RegAllocSolverImpl {
@@ -151,38 +339,8 @@ public:
   typedef GraphBase::EdgeId EdgeId;
 
   typedef RegAlloc::NodeMetadata NodeMetadata;
-
   struct EdgeMetadata { };
-
-  class GraphMetadata {
-  public:
-    GraphMetadata(MachineFunction &MF,
-                  LiveIntervals &LIS,
-                  MachineBlockFrequencyInfo &MBFI)
-      : MF(MF), LIS(LIS), MBFI(MBFI) {}
-
-    MachineFunction &MF;
-    LiveIntervals &LIS;
-    MachineBlockFrequencyInfo &MBFI;
-
-    void setNodeIdForVReg(unsigned VReg, GraphBase::NodeId NId) {
-      VRegToNodeId[VReg] = NId;
-    }
-
-    GraphBase::NodeId getNodeIdForVReg(unsigned VReg) const {
-      auto VRegItr = VRegToNodeId.find(VReg);
-      if (VRegItr == VRegToNodeId.end())
-        return GraphBase::invalidNodeId();
-      return VRegItr->second;
-    }
-
-    void eraseNodeIdForVReg(unsigned VReg) {
-      VRegToNodeId.erase(VReg);
-    }
-
-  private:
-    DenseMap<unsigned, NodeId> VRegToNodeId;
-  };
+  typedef RegAlloc::GraphMetadata GraphMetadata;
 
   typedef PBQP::Graph<RegAllocSolverImpl> Graph;
 
@@ -198,6 +356,8 @@ public:
   }
 
   void handleAddNode(NodeId NId) {
+    assert(G.getNodeCosts(NId).getLength() > 1 &&
+           "PBQP Graph should not contain single or zero-option nodes");
     G.getNodeMetadata(NId).setup(G.getNodeCosts(NId));
   }
   void handleRemoveNode(NodeId NId) {}
@@ -217,15 +377,7 @@ public:
     NodeMetadata& NMd = G.getNodeMetadata(NId);
     const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
     NMd.handleRemoveEdge(MMd, NId == G.getEdgeNode2Id(EId));
-    if (G.getNodeDegree(NId) == 3) {
-      // This node is becoming optimally reducible.
-      moveToOptimallyReducibleNodes(NId);
-    } else if (NMd.getReductionState() ==
-               NodeMetadata::NotProvablyAllocatable &&
-               NMd.isConservativelyAllocatable()) {
-      // This node just became conservatively allocatable.
-      moveToConservativelyAllocatableNodes(NId);
-    }
+    promote(NId, NMd);
   }
 
   void handleReconnectEdge(EdgeId EId, NodeId NId) {
@@ -234,20 +386,44 @@ public:
     NMd.handleAddEdge(MMd, NId == G.getEdgeNode2Id(EId));
   }
 
-  void handleSetEdgeCosts(EdgeId EId, const Matrix& NewCosts) {
-    handleRemoveEdge(EId);
-
+  void handleUpdateCosts(EdgeId EId, const Matrix& NewCosts) {
     NodeId N1Id = G.getEdgeNode1Id(EId);
     NodeId N2Id = G.getEdgeNode2Id(EId);
     NodeMetadata& N1Md = G.getNodeMetadata(N1Id);
     NodeMetadata& N2Md = G.getNodeMetadata(N2Id);
+    bool Transpose = N1Id != G.getEdgeNode1Id(EId);
+
+    // Metadata are computed incrementally. First, update them
+    // by removing the old cost.
+    const MatrixMetadata& OldMMd = G.getEdgeCosts(EId).getMetadata();
+    N1Md.handleRemoveEdge(OldMMd, Transpose);
+    N2Md.handleRemoveEdge(OldMMd, !Transpose);
+
+    // And update now the metadata with the new cost.
     const MatrixMetadata& MMd = NewCosts.getMetadata();
-    N1Md.handleAddEdge(MMd, N1Id != G.getEdgeNode1Id(EId));
-    N2Md.handleAddEdge(MMd, N2Id != G.getEdgeNode1Id(EId));
+    N1Md.handleAddEdge(MMd, Transpose);
+    N2Md.handleAddEdge(MMd, !Transpose);
+
+    // As the metadata may have changed with the update, the nodes may have
+    // become ConservativelyAllocatable or OptimallyReducible.
+    promote(N1Id, N1Md);
+    promote(N2Id, N2Md);
   }
 
 private:
 
+  void promote(NodeId NId, NodeMetadata& NMd) {
+    if (G.getNodeDegree(NId) == 3) {
+      // This node is becoming optimally reducible.
+      moveToOptimallyReducibleNodes(NId);
+    } else if (NMd.getReductionState() ==
+               NodeMetadata::NotProvablyAllocatable &&
+               NMd.isConservativelyAllocatable()) {
+      // This node just became conservatively allocatable.
+      moveToConservativelyAllocatableNodes(NId);
+    }
+  }
+
   void removeFromCurrentSet(NodeId NId) {
     switch (G.getNodeMetadata(NId).getReductionState()) {
     case NodeMetadata::Unprocessed: break;
@@ -368,8 +544,10 @@ private:
   public:
     SpillCostComparator(const Graph& G) : G(G) {}
     bool operator()(NodeId N1Id, NodeId N2Id) {
-      PBQPNum N1SC = G.getNodeCosts(N1Id)[0] / G.getNodeDegree(N1Id);
-      PBQPNum N2SC = G.getNodeCosts(N2Id)[0] / G.getNodeDegree(N2Id);
+      PBQPNum N1SC = G.getNodeCosts(N1Id)[0];
+      PBQPNum N2SC = G.getNodeCosts(N2Id)[0];
+      if (N1SC == N2SC)
+        return G.getNodeDegree(N1Id) < G.getNodeDegree(N2Id);
       return N1SC < N2SC;
     }
   private:
@@ -388,6 +566,17 @@ private:
   typedef PBQP::Graph<RegAllocSolverImpl> BaseT;
 public:
   PBQPRAGraph(GraphMetadata Metadata) : BaseT(Metadata) {}
+
+  /// @brief Dump this graph to dbgs().
+  void dump() const;
+
+  /// @brief Dump this graph to an output stream.
+  /// @param OS Output stream to print on.
+  void dump(raw_ostream &OS) const;
+
+  /// @brief Print a representation of this graph in DOT format.
+  /// @param OS Output stream to print on.
+  void printDot(raw_ostream &OS) const;
 };
 
 inline Solution solve(PBQPRAGraph& G) {