Propagate preferences (#19429)

* Propagate preferences

Instead of selecting a single relatedInterval for preferencing,
follow the chain of relatedIntervals (preferenced intervals).

Change when preferences are propagated to the relatedInterval;
do it in allocateRegisters, so that we can update it when we see a last use.

Also tune when and how intervals are preferenced, including allowing multiple
uses on an RMW node to have the target as their preference.

Fixes #11463
Contributes to #16359

1 files changed, 93 insertions, 65 deletions

diff --git a/src/jit/lsra.cpp b/src/jit/lsra.cpp
index d92e884389..ac5b749521 100644
--- a/src/jit/lsra.cpp
+++ b/src/jit/lsra.cpp
@@ -2236,17 +2236,22 @@ void LinearScan::dumpVarRefPositions(const char* title)
 
         for (unsigned i = 0; i < compiler->lvaCount; i++)
         {
-            printf("--- V%02u\n", i);
+            printf("--- V%02u", i);
 
             LclVarDsc* varDsc = compiler->lvaTable + i;
             if (varDsc->lvIsRegCandidate())
             {
                 Interval* interval = getIntervalForLocalVar(varDsc->lvVarIndex);
+                printf("  (Interval %d)\n", interval->intervalIndex);
                 for (RefPosition* ref = interval->firstRefPosition; ref != nullptr; ref = ref->nextRefPosition)
                 {
                     ref->dump();
                 }
             }
+            else
+            {
+                printf("\n");
+            }
         }
         printf("\n");
     }
@@ -2668,61 +2673,84 @@ regNumber LinearScan::tryAllocateFreeReg(Interval* currentInterval, RefPosition*
     {
         preferences = candidates;
     }
-    regMaskTP relatedPreferences = RBM_NONE;
 
 #ifdef DEBUG
     candidates = stressLimitRegs(refPosition, candidates);
 #endif
     assert(candidates != RBM_NONE);
 
-    // If the related interval has no further references, it is possible that it is a source of the
-    // node that produces this interval.  However, we don't want to use the relatedInterval for preferencing
-    // if its next reference is not a new definition (as it either is or will become live).
     Interval* relatedInterval = currentInterval->relatedInterval;
-    if (relatedInterval != nullptr)
+    if (currentInterval->isSpecialPutArg)
+    {
+        // This is not actually a preference, it's merely to track the lclVar that this
+        // "specialPutArg" is using.
+        relatedInterval = nullptr;
+    }
+    Interval* nextRelatedInterval  = relatedInterval;
+    Interval* finalRelatedInterval = relatedInterval;
+    Interval* rangeEndInterval     = relatedInterval;
+    regMaskTP relatedPreferences   = (relatedInterval == nullptr) ? RBM_NONE : relatedInterval->getCurrentPreferences();
+    LsraLocation rangeEndLocation  = refPosition->getRangeEndLocation();
+    bool         preferCalleeSave  = currentInterval->preferCalleeSave;
+    bool         avoidByteRegs     = false;
+#ifdef _TARGET_X86_
+    if ((relatedPreferences & ~RBM_BYTE_REGS) != RBM_NONE)
     {
-        RefPosition* nextRelatedRefPosition = relatedInterval->getNextRefPosition();
-        if (nextRelatedRefPosition != nullptr)
-        {
-            // Don't use the relatedInterval for preferencing if its next reference is not a new definition,
-            // or if it is only related because they are multi-reg targets of the same node.
-            if (!RefTypeIsDef(nextRelatedRefPosition->refType))
-            {
-                relatedInterval = nullptr;
-            }
-            // Is the relatedInterval not assigned and simply a copy to another relatedInterval?
-            else if ((relatedInterval->assignedReg == nullptr) && (relatedInterval->relatedInterval != nullptr) &&
-                     (nextRelatedRefPosition->nextRefPosition != nullptr) &&
-                     (nextRelatedRefPosition->nextRefPosition->nextRefPosition == nullptr) &&
-                     (nextRelatedRefPosition->nextRefPosition->nodeLocation <
-                      relatedInterval->relatedInterval->getNextRefLocation()))
-            {
-                // The current relatedInterval has only two remaining RefPositions, both of which
-                // occur prior to the next RefPosition for its relatedInterval.
-                // It is likely a copy.
-                relatedInterval = relatedInterval->relatedInterval;
-            }
-        }
+        avoidByteRegs = true;
     }
+#endif
 
-    if (relatedInterval != nullptr)
+    // Follow the chain of related intervals, as long as:
+    // - The next reference is a def. We don't want to use the relatedInterval for preferencing if its next reference
+    //   is not a new definition (as it either is or will become live).
+    // - The next (def) reference is downstream. Otherwise we could iterate indefinitely because the preferences can be
+    // circular.
+    // - The intersection of preferenced registers is non-empty.
+    //
+    while (nextRelatedInterval != nullptr)
     {
-        // If the related interval already has an assigned register, then use that
-        // as the related preference.  We'll take the related
-        // interval preferences into account in the loop over all the registers.
+        RefPosition* nextRelatedRefPosition = nextRelatedInterval->getNextRefPosition();
 
-        if (relatedInterval->assignedReg != nullptr)
+        // Only use the relatedInterval for preferencing if the related interval's next reference
+        // is a new definition.
+        if ((nextRelatedRefPosition != nullptr) && RefTypeIsDef(nextRelatedRefPosition->refType))
         {
-            relatedPreferences = genRegMask(relatedInterval->assignedReg->regNum);
+            finalRelatedInterval = nextRelatedInterval;
+            nextRelatedInterval  = nullptr;
+
+            // First, get the preferences for this interval
+            regMaskTP thisRelatedPreferences = finalRelatedInterval->getCurrentPreferences();
+            // Now, determine if they are compatible and update the relatedPreferences that we'll consider.
+            regMaskTP newRelatedPreferences = thisRelatedPreferences & relatedPreferences;
+            if (newRelatedPreferences != RBM_NONE && (!avoidByteRegs || thisRelatedPreferences != RBM_BYTE_REGS))
+            {
+                bool thisIsSingleReg = isSingleRegister(newRelatedPreferences);
+                if (!thisIsSingleReg || (finalRelatedInterval->isLocalVar &&
+                                         getRegisterRecord(genRegNumFromMask(newRelatedPreferences))->isFree()))
+                {
+                    relatedPreferences = newRelatedPreferences;
+                    // If this Interval has a downstream def without a single-register preference, continue to iterate.
+                    if (nextRelatedRefPosition->nodeLocation > rangeEndLocation)
+                    {
+                        preferCalleeSave    = (preferCalleeSave || finalRelatedInterval->preferCalleeSave);
+                        rangeEndLocation    = nextRelatedRefPosition->getRangeEndLocation();
+                        rangeEndInterval    = finalRelatedInterval;
+                        nextRelatedInterval = finalRelatedInterval->relatedInterval;
+                    }
+                }
+            }
         }
         else
         {
-            relatedPreferences = relatedInterval->registerPreferences;
+            if (nextRelatedInterval == relatedInterval)
+            {
+                relatedInterval    = nullptr;
+                relatedPreferences = RBM_NONE;
+            }
+            nextRelatedInterval = nullptr;
         }
     }
 
-    bool preferCalleeSave = currentInterval->preferCalleeSave;
-
     // For floating point, we want to be less aggressive about using callee-save registers.
     // So in that case, we just need to ensure that the current RefPosition is covered.
     RefPosition* rangeEndRefPosition;
@@ -2730,27 +2758,27 @@ regNumber LinearScan::tryAllocateFreeReg(Interval* currentInterval, RefPosition*
     if (useFloatReg(currentInterval->registerType))
     {
         rangeEndRefPosition = refPosition;
+        preferCalleeSave    = currentInterval->preferCalleeSave;
     }
     else
     {
-        rangeEndRefPosition = currentInterval->lastRefPosition;
-        // If we have a relatedInterval that is not currently occupying a register,
-        // and whose lifetime begins after this one ends,
+        rangeEndRefPosition = refPosition->getRangeEndRef();
+        // If we have a chain of related intervals, and a finalRelatedInterval that
+        // is not currently occupying a register, and whose lifetime begins after this one,
         // we want to try to select a register that will cover its lifetime.
-        if ((relatedInterval != nullptr) && (relatedInterval->assignedReg == nullptr) &&
-            (relatedInterval->getNextRefLocation() >= rangeEndRefPosition->nodeLocation))
+        if ((rangeEndInterval != nullptr) && (rangeEndInterval->assignedReg == nullptr) &&
+            (rangeEndInterval->getNextRefLocation() >= rangeEndRefPosition->nodeLocation))
         {
-            lastRefPosition  = relatedInterval->lastRefPosition;
-            preferCalleeSave = relatedInterval->preferCalleeSave;
+            lastRefPosition = rangeEndInterval->lastRefPosition;
         }
     }
 
     // If this has a delayed use (due to being used in a rmw position of a
     // non-commutative operator), its endLocation is delayed until the "def"
     // position, which is one location past the use (getRefEndLocation() takes care of this).
-    LsraLocation rangeEndLocation = rangeEndRefPosition->getRefEndLocation();
-    LsraLocation lastLocation     = lastRefPosition->getRefEndLocation();
-    regNumber    prevReg          = REG_NA;
+    rangeEndLocation          = rangeEndRefPosition->getRefEndLocation();
+    LsraLocation lastLocation = lastRefPosition->getRefEndLocation();
+    regNumber    prevReg      = REG_NA;
 
     if (currentInterval->assignedReg)
     {
@@ -2911,7 +2939,7 @@ regNumber LinearScan::tryAllocateFreeReg(Interval* currentInterval, RefPosition*
         // are "local last uses" of the Interval - otherwise the liveRange would interfere with the reg.
         if (nextPhysRefLocation == rangeEndLocation && rangeEndRefPosition->isFixedRefOfReg(regNum))
         {
-            INDEBUG(dumpLsraAllocationEvent(LSRA_EVENT_INCREMENT_RANGE_END, currentInterval, regNum));
+            INDEBUG(dumpLsraAllocationEvent(LSRA_EVENT_INCREMENT_RANGE_END, currentInterval));
             nextPhysRefLocation++;
         }
 
@@ -2923,7 +2951,7 @@ regNumber LinearScan::tryAllocateFreeReg(Interval* currentInterval, RefPosition*
                 score |= COVERS;
             }
         }
-        if (relatedInterval != nullptr && (candidateBit & relatedPreferences) != RBM_NONE)
+        if ((candidateBit & relatedPreferences) != RBM_NONE)
         {
             score |= RELATED_PREFERENCE;
             if (nextPhysRefLocation > relatedInterval->lastRefPosition->nodeLocation)
@@ -3033,10 +3061,6 @@ regNumber LinearScan::tryAllocateFreeReg(Interval* currentInterval, RefPosition*
         foundReg                        = availablePhysRegInterval->regNum;
         regMaskTP foundRegMask          = genRegMask(foundReg);
         refPosition->registerAssignment = foundRegMask;
-        if (relatedInterval != nullptr)
-        {
-            relatedInterval->updateRegisterPreferences(foundRegMask);
-        }
     }
 
     return foundReg;
@@ -5689,6 +5713,14 @@ void LinearScan::allocateRegisters()
                 {
                     currentInterval->isActive = false;
                 }
+
+                // Update the register preferences for the relatedInterval, if this is 'preferencedToDef'.
+                // Don't propagate to subsequent relatedIntervals; that will happen as they are allocated, and we
+                // don't know yet whether the register will be retained.
+                if (currentInterval->relatedInterval != nullptr)
+                {
+                    currentInterval->relatedInterval->updateRegisterPreferences(assignedRegBit);
+                }
             }
 
             lastAllocatedRefPosition = currentRefPosition;
@@ -8609,7 +8641,6 @@ void Interval::dump()
     {
         printf(" RelatedInterval ");
         relatedInterval->microDump();
-        printf("[%p]", dspPtr(relatedInterval));
     }
 
     printf("\n");
@@ -8633,16 +8664,16 @@ void Interval::tinyDump()
 // print out extremely concise representation
 void Interval::microDump()
 {
+    if (isLocalVar)
+    {
+        printf("<V%02u/L%u>", varNum, intervalIndex);
+        return;
+    }
     char intervalTypeChar = 'I';
     if (isInternal)
     {
         intervalTypeChar = 'T';
     }
-    else if (isLocalVar)
-    {
-        intervalTypeChar = 'L';
-    }
-
     printf("<%c%u>", intervalTypeChar, intervalIndex);
 }
 
@@ -9282,10 +9313,6 @@ void LinearScan::dumpLsraAllocationEvent(LsraDumpEvent event,
             }
             printf("Restr %-4s ", getRegName(reg));
             dumpRegRecords();
-            if (activeRefPosition != nullptr)
-            {
-                printf(emptyRefPositionFormat, "");
-            }
             break;
 
         // Done with GC Kills
@@ -9650,8 +9677,9 @@ void LinearScan::dumpRefPositionShort(RefPosition* refPosition, BasicBlock* curr
         if (block == nullptr)
         {
             printf(regNameFormat, "END");
-            printf("               ");
-            printf(regNameFormat, "");
+            printf("        ");
+            // We still need to print this refposition.
+            lastPrintedRefPosition = nullptr;
         }
         else
         {