Use CFG connectedness as a secondary sort key when deciding the order of copy coalescing.

This means that well connected blocks are copy coalesced before the less connected blocks. Connected blocks are more difficult to
coalesce because intervals are more complicated, so handling them first gives a greater chance of success.

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

diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp
index 7847f8ec20e5de5d3279b0af3f822d3aff454329..58763718f9b5d0c2241dfa69f97be41ae79514d9 100644 (file)
--- a/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -2371,9 +2371,19 @@ namespace {
   struct DepthMBBCompare {
     typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair;
     bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const {
-      if (LHS.first > RHS.first) return true;   // Deeper loops first
-      return LHS.first == RHS.first &&
-        LHS.second->getNumber() < RHS.second->getNumber();
+      // Deeper loops first
+      if (LHS.first != RHS.first)
+        return LHS.first > RHS.first;
+
+      // Prefer blocks that are more connected in the CFG. This takes care of
+      // the most difficult copies first while intervals are short.
+      unsigned cl = LHS.second->pred_size() + LHS.second->succ_size();
+      unsigned cr = RHS.second->pred_size() + RHS.second->succ_size();
+      if (cl != cr)
+        return cl > cr;
+
+      // As a last resort, sort by block number.
+      return LHS.second->getNumber() < RHS.second->getNumber();
     }
   };
 }

diff --git a/test/CodeGen/X86/2009-09-19-SchedCustomLoweringBug.ll b/test/CodeGen/X86/2009-09-19-SchedCustomLoweringBug.ll
index f3cf1d5e70197c56281a4cdaee81aba2ab0d7eec..d372da336769e99353fb54534260f8ecebb93f6d 100644 (file)
--- a/test/CodeGen/X86/2009-09-19-SchedCustomLoweringBug.ll
+++ b/test/CodeGen/X86/2009-09-19-SchedCustomLoweringBug.ll
@@ -10,6 +10,7 @@ entry:
 
 bb:                                               ; preds = %bb1, %entry
 ; CHECK:      addl $1
+; CHECK-NEXT: movl %e
 ; CHECK-NEXT: adcl $0
   %i.0 = phi i64 [ 0, %entry ], [ %0, %bb1 ]      ; <i64> [#uses=1]
   %0 = add nsw i64 %i.0, 1                        ; <i64> [#uses=2]