Added an additional PBQP problem builder which adds coalescing costs (both between pairs of virtuals, and between virtuals and physicals).

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

2 files changed, 31 insertions, 3 deletions

diff --git a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
index 18eaf7c0da..47a287ccf2 100644
--- a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
+++ b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
@@ -63,8 +63,12 @@ namespace PBQP {
         SpillCostComparator(HeuristicSolverImpl<Briggs> &s)
           : s(&s), g(&s.getGraph()) {}
         bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
-          PBQPNum cost1 = g->getNodeCosts(n1Itr)[0] / s->getSolverDegree(n1Itr),
-                  cost2 = g->getNodeCosts(n2Itr)[0] / s->getSolverDegree(n2Itr);
+          const PBQP::Vector &cv1 = g->getNodeCosts(n1Itr);
+          const PBQP::Vector &cv2 = g->getNodeCosts(n2Itr);
+
+          PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Itr);
+          PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Itr);
+
           if (cost1 < cost2)
             return true;
           return false;
diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h
index ee3baf36a9..2d9bac6e0d 100644
--- a/include/llvm/CodeGen/RegAllocPBQP.h
+++ b/include/llvm/CodeGen/RegAllocPBQP.h
@@ -27,6 +27,7 @@ namespace llvm {
 
   class LiveInterval;
   class MachineFunction;
+  class MachineLoopInfo;
 
   /// This class wraps up a PBQP instance representing a register allocation
   /// problem, plus the structures necessary to map back from the PBQP solution
@@ -113,7 +114,6 @@ namespace llvm {
 
     typedef std::set<unsigned> RegSet;
  
-
     /// Default constructor.
     PBQPBuilder() {}
 
@@ -125,6 +125,7 @@ namespace llvm {
     virtual std::auto_ptr<PBQPRAProblem> build(
                                               MachineFunction *mf,
                                               const LiveIntervals *lis,
+                                              const MachineLoopInfo *loopInfo,
                                               const RegSet &vregs);
   private:
 
@@ -136,6 +137,29 @@ namespace llvm {
                               const TargetRegisterInfo *tri);
   };
 
+  /// Extended builder which adds coalescing constraints to a problem.
+  class PBQPBuilderWithCoalescing : public PBQPBuilder {
+  public:
+ 
+    /// Build a PBQP instance to represent the register allocation problem for
+    /// the given MachineFunction.
+    virtual std::auto_ptr<PBQPRAProblem> build(
+                                              MachineFunction *mf,
+                                              const LiveIntervals *lis,
+                                              const MachineLoopInfo *loopInfo,
+                                              const RegSet &vregs);   
+
+  private:
+
+    void addPhysRegCoalesce(PBQP::Vector &costVec, unsigned pregOption,
+                            PBQP::PBQPNum benefit);
+
+    void addVirtRegCoalesce(PBQP::Matrix &costMat,
+                            const PBQPRAProblem::AllowedSet &vr1Allowed,
+                            const PBQPRAProblem::AllowedSet &vr2Allowed,
+                            PBQP::PBQPNum benefit);
+  };
+
   ///
   /// PBQP based allocators solve the register allocation problem by mapping
   /// register allocation problems to Partitioned Boolean Quadratic