Backport: [RegisterCoalescer] Avoid retrying high-cost joins for live intervals
https://github.com/llvm/llvm-project/commit/fd9e690cdbeb02832cc36d455bffda9e7e813785

Index: llvm/lib/CodeGen/RegisterCoalescer.cpp
--- llvm/lib/CodeGen/RegisterCoalescer.cpp.orig
+++ llvm/lib/CodeGen/RegisterCoalescer.cpp
@@ -232,21 +232,26 @@ class RegisterCoalescer : private LiveRangeEdit::Deleg
   void setUndefOnPrunedSubRegUses(LiveInterval &LI, Register Reg,
                                   LaneBitmask PrunedLanes);
 
+  /// Result of attempting to coalesce a copy.
+  /// - Joined: the copy was removed or otherwise fully handled.
+  /// - Deferred: retry after other coalescing may make progress.
+  /// - Rejected: do not retry, either because the copy is not a coalescing
+  ///   candidate or because the join was intentionally rejected.
+  enum class JoinResult { Joined, Deferred, Rejected };
+
   /// Attempt to join intervals corresponding to SrcReg/DstReg, which are the
-  /// src/dst of the copy instruction CopyMI.  This returns true if the copy
-  /// was successfully coalesced away. If it is not currently possible to
-  /// coalesce this interval, but it may be possible if other things get
-  /// coalesced, then it returns true by reference in 'Again'.
-  bool joinCopy(MachineInstr *CopyMI, bool &Again,
-                SmallPtrSetImpl<MachineInstr *> &CurrentErasedInstrs);
+  /// src/dst of the copy instruction CopyMI.
+  JoinResult joinCopy(MachineInstr *CopyMI,
+                      SmallPtrSetImpl<MachineInstr *> &CurrentErasedInstrs);
 
-  /// Attempt to join these two intervals.  On failure, this
-  /// returns false.  The output "SrcInt" will not have been modified, so we
-  /// can use this information below to update aliases.
-  bool joinIntervals(CoalescerPair &CP);
+  /// Attempt to join these two intervals.  On failure, the output "SrcInt"
+  /// will not have been modified, so we can use this information below to
+  /// update aliases. Returns Deferred when it may be possible to join later,
+  /// or Rejected when retrying should be avoided.
+  JoinResult joinIntervals(CoalescerPair &CP);
 
-  /// Attempt joining two virtual registers. Return true on success.
-  bool joinVirtRegs(CoalescerPair &CP);
+  /// Attempt joining two virtual registers.
+  JoinResult joinVirtRegs(CoalescerPair &CP);
 
   /// If a live interval has many valnos and is coalesced with other
   /// live intervals many times, we regard such live interval as having
@@ -2054,23 +2059,22 @@ void RegisterCoalescer::setUndefOnPrunedSubRegUses(Liv
   LIS->shrinkToUses(&LI);
 }
 
-bool RegisterCoalescer::joinCopy(
-    MachineInstr *CopyMI, bool &Again,
+RegisterCoalescer::JoinResult RegisterCoalescer::joinCopy(
+    MachineInstr *CopyMI,
     SmallPtrSetImpl<MachineInstr *> &CurrentErasedInstrs) {
-  Again = false;
   LLVM_DEBUG(dbgs() << LIS->getInstructionIndex(*CopyMI) << '\t' << *CopyMI);
 
   CoalescerPair CP(*TRI);
   if (!CP.setRegisters(CopyMI)) {
     LLVM_DEBUG(dbgs() << "\tNot coalescable.\n");
-    return false;
+    return JoinResult::Rejected;
   }
 
   if (CP.getNewRC()) {
     if (RegClassInfo.getNumAllocatableRegs(CP.getNewRC()) == 0) {
       LLVM_DEBUG(dbgs() << "\tNo " << TRI->getRegClassName(CP.getNewRC())
                         << "are available for allocation\n");
-      return false;
+      return JoinResult::Rejected;
     }
 
     auto SrcRC = MRI->getRegClass(CP.getSrcReg());
@@ -2084,7 +2088,7 @@ bool RegisterCoalescer::joinCopy(
     if (!TRI->shouldCoalesce(CopyMI, SrcRC, SrcIdx, DstRC, DstIdx,
                              CP.getNewRC(), *LIS)) {
       LLVM_DEBUG(dbgs() << "\tSubtarget bailed on coalescing.\n");
-      return false;
+      return JoinResult::Rejected;
     }
   }
 
@@ -2095,7 +2099,7 @@ bool RegisterCoalescer::joinCopy(
     LLVM_DEBUG(dbgs() << "\tCopy is dead.\n");
     DeadDefs.push_back(CopyMI);
     eliminateDeadDefs();
-    return true;
+    return JoinResult::Joined;
   }
 
   // Eliminate undefs.
@@ -2103,9 +2107,9 @@ bool RegisterCoalescer::joinCopy(
     // If this is an IMPLICIT_DEF, leave it alone, but don't try to coalesce.
     if (MachineInstr *UndefMI = eliminateUndefCopy(CopyMI)) {
       if (UndefMI->isImplicitDef())
-        return false;
+        return JoinResult::Rejected;
       deleteInstr(CopyMI);
-      return false; // Not coalescable.
+      return JoinResult::Rejected; // Not coalescable.
     }
   }
 
@@ -2153,7 +2157,7 @@ bool RegisterCoalescer::joinCopy(
       LLVM_DEBUG(dbgs() << "\tMerged values:          " << LI << '\n');
     }
     deleteInstr(CopyMI);
-    return true;
+    return JoinResult::Joined;
   }
 
   // Enforce policies.
@@ -2166,10 +2170,10 @@ bool RegisterCoalescer::joinCopy(
       // the copy instead if it is cheap.
       bool IsDefCopy = false;
       if (reMaterializeDef(CP, CopyMI, IsDefCopy))
-        return true;
+        return JoinResult::Joined;
       if (IsDefCopy)
-        Again = true; // May be possible to coalesce later.
-      return false;
+        return JoinResult::Deferred; // May be possible to coalesce later.
+      return JoinResult::Rejected;
     }
   } else {
     // When possible, let DstReg be the larger interval.
@@ -2194,17 +2198,18 @@ bool RegisterCoalescer::joinCopy(
   ShrinkMask = LaneBitmask::getNone();
   ShrinkMainRange = false;
 
-  // Okay, attempt to join these two intervals.  On failure, this returns false.
-  // Otherwise, if one of the intervals being joined is a physreg, this method
-  // always canonicalizes DstInt to be it.  The output "SrcInt" will not have
-  // been modified, so we can use this information below to update aliases.
-  if (!joinIntervals(CP)) {
+  // Okay, attempt to join these two intervals.  If one of the intervals being
+  // joined is a physreg and the join succeeds, this method always canonicalizes
+  // DstInt to be it.  The output "SrcInt" will not have been modified, so we
+  // can use this information below to update aliases.
+  JoinResult Result = joinIntervals(CP);
+  if (Result != JoinResult::Joined) {
     // Coalescing failed.
 
     // Try rematerializing the definition of the source if it is cheap.
     bool IsDefCopy = false;
     if (reMaterializeDef(CP, CopyMI, IsDefCopy))
-      return true;
+      return JoinResult::Joined;
 
     // If we can eliminate the copy without merging the live segments, do so
     // now.
@@ -2222,7 +2227,7 @@ bool RegisterCoalescer::joinCopy(
           LLVM_DEBUG(dbgs() << "\t\tshrunk:   " << DstLI << '\n');
         }
         LLVM_DEBUG(dbgs() << "\tTrivial!\n");
-        return true;
+        return JoinResult::Joined;
       }
     }
 
@@ -2230,12 +2235,16 @@ bool RegisterCoalescer::joinCopy(
     // its predecessor.
     if (!CP.isPartial() && !CP.isPhys())
       if (removePartialRedundancy(CP, *CopyMI))
-        return true;
+        return JoinResult::Joined;
 
     // Otherwise, we are unable to join the intervals.
     LLVM_DEBUG(dbgs() << "\tInterference!\n");
-    Again = true; // May be possible to coalesce later.
-    return false;
+    // A high-cost interval is already too expensive to retry.  Keeping the copy
+    // in WorkList would make every subsequent successful join rescan it again,
+    // which can dominate compile time.
+    if (Result == JoinResult::Deferred)
+      LLVM_DEBUG(dbgs() << "\tWill retry later.\n");
+    return Result;
   }
 
   // Coalescing to a virtual register that is of a sub-register class of the
@@ -2307,7 +2316,7 @@ bool RegisterCoalescer::joinCopy(
   });
 
   ++numJoins;
-  return true;
+  return JoinResult::Joined;
 }
 
 bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) {
@@ -3698,7 +3707,8 @@ bool RegisterCoalescer::isHighCostLiveInterval(LiveInt
   return true;
 }
 
-bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) {
+RegisterCoalescer::JoinResult
+RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) {
   SmallVector<VNInfo *, 16> NewVNInfo;
   LiveInterval &RHS = LIS->getInterval(CP.getSrcReg());
   LiveInterval &LHS = LIS->getInterval(CP.getDstReg());
@@ -3710,17 +3720,24 @@ bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP
 
   LLVM_DEBUG(dbgs() << "\t\tRHS = " << RHS << "\n\t\tLHS = " << LHS << '\n');
 
-  if (isHighCostLiveInterval(LHS) || isHighCostLiveInterval(RHS))
-    return false;
+  if (isHighCostLiveInterval(LHS) || isHighCostLiveInterval(RHS)) {
+    LLVM_DEBUG(dbgs() << "\t\tHigh-cost live interval: RHS valnos="
+                      << RHS.valnos.size() << ", segments=" << RHS.size()
+                      << "; LHS valnos=" << LHS.valnos.size()
+                      << ", segments=" << LHS.size() << '\n');
+    return JoinResult::Rejected;
+  }
 
-  // First compute NewVNInfo and the simple value mappings.
-  // Detect impossible conflicts early.
+  // First compute NewVNInfo and the simple value mappings. Conflicts found
+  // here only reject this attempt; subsequent coalescing may still make the
+  // same copy joinable, so keep it deferred.
   if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals))
-    return false;
+    return JoinResult::Deferred;
 
   // Some conflicts can only be resolved after all values have been mapped.
+  // As above, unresolved conflicts are retryable interference.
   if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals))
-    return false;
+    return JoinResult::Deferred;
 
   // All clear, the live ranges can be merged.
   if (RHS.hasSubRanges() || LHS.hasSubRanges()) {
@@ -3875,11 +3892,14 @@ bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP
     LIS->extendToIndices((LiveRange &)LHS, EndPoints);
   }
 
-  return true;
+  return JoinResult::Joined;
 }
 
-bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) {
-  return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP);
+RegisterCoalescer::JoinResult
+RegisterCoalescer::joinIntervals(CoalescerPair &CP) {
+  if (CP.isPhys())
+    return joinReservedPhysReg(CP) ? JoinResult::Joined : JoinResult::Deferred;
+  return joinVirtRegs(CP);
 }
 
 void RegisterCoalescer::buildVRegToDbgValueMap(MachineFunction &MF) {
@@ -4095,10 +4115,9 @@ bool RegisterCoalescer::copyCoalesceWorkList(
       MI = nullptr;
       continue;
     }
-    bool Again = false;
-    bool Success = joinCopy(MI, Again, CurrentErasedInstrs);
-    Progress |= Success;
-    if (Success || !Again)
+    JoinResult Result = joinCopy(MI, CurrentErasedInstrs);
+    Progress |= Result == JoinResult::Joined;
+    if (Result != JoinResult::Deferred)
       MI = nullptr;
   }
   // Clear instructions not recorded in `ErasedInstrs` but erased.
