[nfc] Refactor SlotIndex::getInstrDistance to better reflect actual functionality

[aidengrossman]

Summary

This patch refactors SlotIndex::getInstrDistance to
SlotIndex::getApproxInstrDistance to better describe the actual
functionality of this function. This patch also adds in some additional
comments better documenting the assumptions that this function makes to
increase clarity.

Based on discussion on the LLVM Discourse:
https://discourse.llvm.org/t/odd-behavior-in-slotindex-getinstrdistance/64934/5

[aidengrossman]

Minor NFC change to make some of the intricacies of SlotIndex::getInstrDistance more clear so that it's easier for the next person trying to understand it. Based on discussion here.

[MatzeB]

llvm/include/llvm/CodeGen/SlotIndexes.h

223

how about getIndexDiff or getIndexDelta?

[MatzeB]

llvm/include/llvm/CodeGen/SlotIndexes.h

223

oh sorry, ignore me. This seems to be scaled by Slot_Count... guess "Approximate" is fine then.

[MatzeB]

llvm/include/llvm/CodeGen/SlotIndexes.h

219–221

This assumption is also not true after inserting one instruction. You have to insert InstrDist / Slot_Count instructions I believe until you reach the limit (currently 4). And also the 5th insertion would trigger a renumbering making this approximate again...

[aidengrossman]

Updated comment above getApproxInstrDistance to better encapsulate some nuance
in the spacing between SlotIndices.

[aidengrossman]

llvm/include/llvm/CodeGen/SlotIndexes.h

219–221

That's a good point. Thank you.

If I'm understanding everything correctly in insertMachineInstrInMaps, it looks like it will only insert up to (InstrDist / Slot_Count) - 1 instructions before the distance, with the next inserted instruction having a calculated distance of zero and a renumbering being requested. It also looks like the assumption can hold if you insert two instructions in between two normally spaced instructions, and you'll get the correct numbering within those three instructions. I've reworded the statement to talk specifically about the example of calculating the distance between two "normally" (no insertions in between, no renumbering) spaced instructions. Let me know if you think a different statement would better encapsulate some of the nuances and also if my indexing is incorrect.

[foad]

I would prefer to make the comment a bit vaguer, rather than trying to explain exactly what conditions are required to get dense numbering. How about just adding something like: "Note that if there are gaps in the numbering (which there usually are) then this function will return an over-estimate of the true instruction distance."

[aidengrossman]

Make documentation message for getApproxInstrDistance more vague rather
than trying to list out exact conditions.

[aidengrossman]

Thank you very much for the feedback. I've reworded the message to something akin to your example, talking about relevant conditions rather than all the specific examples that could ever possibly exist.

[foad]

Seems fine to me, thanks.

llvm/include/llvm/CodeGen/SlotIndexes.h

 //===- llvm/CodeGen/SlotIndexes.h - Slot indexes representation -*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
public:
     }
 
     /// Return the distance from this index to the given one.
     int distance(SlotIndex other) const {
       return other.getIndex() - getIndex();
     }
 
     /// Return the scaled distance from this index to the given one, where all
-    /// slots on the same instruction have zero distance.
-    int getInstrDistance(SlotIndex other) const {
+    /// slots on the same instruction have zero distance, assuming that the slot
+    /// indices are packed as densely as possible. This assumption is only true
+    /// in practice if an instruction is inserted in between two existing
+    /// instructions. Otherwise, this function will return a value greater than
+    /// the true instruction distance.
+    int getApproxInstrDistance(SlotIndex other) const {
       return (other.listEntry()->getIndex() - listEntry()->getIndex())
         / Slot_Count;
     }
 
     /// isBlock - Returns true if this is a block boundary slot.
     bool isBlock() const { return getSlot() == Slot_Block; }
 
     /// isEarlyClobber - Returns true if this is an early-clobber slot.

llvm/lib/CodeGen/RegAllocGreedy.cpp

 //===- RegAllocGreedy.cpp - greedy register allocator ---------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (Stage == RS_Split) {
     unsigned GlobalBit = 0;
 
     if (Stage == RS_Assign && !ForceGlobal && !LI.empty() &&
         LIS->intervalIsInOneMBB(LI)) {
       // Allocate original local ranges in linear instruction order. Since they
       // are singly defined, this produces optimal coloring in the absence of
       // global interference and other constraints.
       if (!ReverseLocalAssignment)
-        Prio = LI.beginIndex().getInstrDistance(Indexes->getLastIndex());
+        Prio = LI.beginIndex().getApproxInstrDistance(Indexes->getLastIndex());
       else {
         // Allocating bottom up may allow many short LRGs to be assigned first
         // to one of the cheap registers. This could be much faster for very
         // large blocks on targets with many physical registers.
-        Prio = Indexes->getZeroIndex().getInstrDistance(LI.endIndex());
+        Prio = Indexes->getZeroIndex().getApproxInstrDistance(LI.endIndex());
       }
     } else {
       // Allocate global and split ranges in long->short order. Long ranges that
       // don't fit should be spilled (or split) ASAP so they don't create
       // interference.  Mark a bit to prioritize global above local ranges.
       Prio = Size;
       GlobalBit = 1;
     }