[SystemZ] Implement orderFrameObjects().

[jonpa]

Summary

By reordering the objects on the stack frame after looking at the users, a better utilization of displacement operands will result. This means less needed Load Address instructions for the loading/storing of those objects.

This is still a work in progress, but the new test case works where an LAY is eliminated.

(Inspired by X86FrameLowering::orderFrameObjects().)

[jonpa]

I have experimented further with the sorting and improved the patch in several ways.

Common code change: Pass (and run) MachineBlockFrequencyInfo from PrologEpilogInserter to orderFrameObjects(). This helps in prioritizing instructions inside loops.

The "first try", which just did one sort by U12Freq (and secondarily by DPairFreq), gave this improvement on SPEC:

lay            :                62128                55002    -7126
la             :               532263               533346    +1083
lghi           :               446000               445758     -242
ldy            :                 3416                 3234     -182
ld             :                98097                98279     +182
std            :                66248                66412     +164
stdy           :                 1227                 1063     -164
...
OPCDIFFS: -6333

To improve on this I worked on an iterative sorting approach like:

1. Sort all objects as if they are all in range.
2. Sort the ones within S20 offset by D12Freq, and add D12Freq objects below U12. (2b. Take extra care with an (U12) overlapping D12Freq object and see if it should remain.)
3. Sort again within S20 for DPairFreq and add below U12 for shortening.
4. Now sort above S20 without D12Freq, since no short displacements are in range.
5. Finally sort the different ranges by alignment.

After all this looked nice I found to my surprise that it was only a slight improvement to the first simple version:

lay            :                62128                54715    -7413
la             :               532263               533630    +1367
...
OPCDIFFS: -6346

The reason became quite clear: There are no frame objects ever out of range for the long displacement, so there could not be any gain by sorting for this. 14334 (sorted) frames were within U12, and then all of the rest (411) where within S20.

I looked into the cases that actually had still improved, and it turned out that these were cases where a big D12Freq object that was not fully within U12 had been moved to let smaller objects closer to SP. In many cases then the offsets used into that big object were small (like 0) and therefore still in range, even though the object was further away from SP.

So I trimmed down my patch again to do the first initial sorting, and also if not all objects fit within U12, "pack" smaller objects below the last object partially within U12. While doing this the bigger object is still kept in range as its max offset is kept track of.

This version (as posted) now gives a slightly better result yet:

lay            :                62128                54005    -8123
la             :               532263               534200    +1937
lghi           :               446000               445756     -244
ldy            :                 3416                 3225     -191
ld             :                98097                98288     +191
stdy           :                 1227                 1056     -171
std            :                66248                66419     +171
...
OPCDIFFS: -6487

Stack size differences:
Byte diff       Count
-72             1
-56             1
-48             2
-40             16
-32             41
-24             96
-16             260
 -8             1141
  0             60788   (This includes the majority of cases that were actually not sorted. IIRC ~15000 had at least two objects and were sorted)
  8             2

This is the best result so far. The code changes seen above all then come from the bigger functions/stacks since if all objects fit within U12, only the stack space savings after sorting by alignment could be the benefit.

The sorting of objects into U12/S20 ranges depends on predicting those ranges accurately. The exact size of the final stack is not easy to predict as it depends on the final order of objects and their alignment requirements. The PrologEpilogInserter pass adds objects in a descending order (starting at highest address), and adds alignments to each object on the way. However, the sorting of the frame objects naturally begins starting from the lowest address, which in this patch is 'BottomMargin'. It includes the outgoing reg save area, the MaxCallFrameSize, and an extra 8 bytes of alignment margin. In addition, each object has its size rounded up to the next multiple of its alignment as a way to simplify. This leads to all 'EstimatedStackSize':es being slightly bigger than the actual final stack adjustments in emitPrologue():

Counts Number of bytes extra
   452 2
  2957 4
   240 6
 11057 8
     5 10
    34 12

(E.g. 11057 stacks were overestimated by 8 bytes).

This is not quite optimal, but the important thing is that it is never underestimated, since the reordering for alignments depends on all objects actually ending up being within the same range as they were in their sorted order. In other words, the most dense object may end up near the U12 range if it has a low alignment value, so it better not end up actually going out of range.

This is checked with assertions in emitPrologue() and eliminateFrameIndex(). The SystemZMachineFunctionInfo is used for these values since orderFrameObjects() is 'const'. These checks could be simplified - for example perhaps a simple thing would be to drop the const from orderFrameObjects() and assert the EstimatedStackSize within SystemZELFFrameLowering.

Typical sizes of the objects (that are actually sorted):

Num     Bytes
  72620 8
  14974 4
   8281 16
   5529 24
   4336 32
   1853 64
    ...

(E.g. 5529 of the sorted objects were 24 bytes big). There were many more sizes, up to 160k.

[jonpa]

llvm/lib/Target/SystemZ/SystemZFrameLowering.cpp

190

The effect of the packing of smaller objects below the bigger one is relatively small. Commenting this out I see:

lay            :                54005                54970     +965
la             :               534200               533379     -821
l              :               178549               178356     -193
ly             :                 3574                 3767     +193
sty            :                 3528                 3663     +135
st             :               122536               122401     -135
ley            :                  369                  410      +41
lde            :                68636                68595      -41
...
OPCDIFFS: 139

212

These checks were useful during experiments, but could perhaps be reduced if the patch is considered more trustworthy...

253

This dumping looks nice to me, but is not really necessary...

386

Perhaps this is also no longer needed...?

531

Maybe it would be possible to first sort the objects and then decide if the slot(s) are needed. I guess however this would typically only be for big functions where that wouldn't matter much..?

[jonpa]

Initial benchmarking shows no real big changes either way, nor any particular difference from using the extra "packing" trick (smaller objects below the last big one).

If we do not care about sorting by alignments (not sure how much that space saving is worth, if anything), we could simplify the patch considerably by just doing one sort for D12Freq and DPairFreq...

[jonpa]

Simplified version which is nearly as good as the full patch, but much less work.

[uweigand]

Agreed that this version looks much more reasonable. A few remaining comments inline.

llvm/lib/Target/SystemZ/SystemZFrameLowering.cpp

165

Why two calls to stable_sort here? It seems this could be done in a single call with an appropriate comparison routine.

llvm/test/CodeGen/SystemZ/stackmap.ll

474 ↗

(On Diff #402099)

This change seems unexpected - do you understand where this is coming from?

[jonpa]

llvm/lib/Target/SystemZ/SystemZFrameLowering.cpp

165

Ah, I guess that's true. For readability I thought it was better to have them separate as the first sort is not relating to anything SystemZ specific.

I guess now that the patch only does one additional sort, it makes sense to merge the two comparators and remove the IE iterator.

llvm/test/CodeGen/SystemZ/stackmap.ll

474 ↗

(On Diff #402099)

hmm - sorry that must have gone undetected as I simplified the patch. The test actually passes with and without this test change. I think I probably needed to modify this when the alignments sorting was done previously. Removed.

[jonpa]

updated per review.

[uweigand]

LGTM, thanks!

llvm/lib/Target/SystemZ/SystemZFrameLowering.h

bool allocateScavengingFrameIndexesNearIncomingSP(
     // stack pointer, which is the opposite of what we want on SystemZ.
     return false;
   }
 
   bool hasReservedCallFrame(const MachineFunction &MF) const override;
   MachineBasicBlock::iterator
   eliminateCallFramePseudoInstr(MachineFunction &MF, MachineBasicBlock &MBB,
                                 MachineBasicBlock::iterator MI) const override;
+  void orderFrameObjects(const MachineFunction &MF,
+                         SmallVectorImpl<int> &ObjectsToAllocate) const override;
 };
 
 class SystemZELFFrameLowering : public SystemZFrameLowering {
   IndexedMap<unsigned> RegSpillOffsets;
 
 public:
   SystemZELFFrameLowering();
 

llvm/lib/Target/SystemZ/SystemZFrameLowering.cpp

case SystemZ::ADJCALLSTACKUP:
     return MBB.erase(MI);
     break;
 
   default:
     llvm_unreachable("Unexpected call frame instruction");
   }
 }
 
+// EXPERIMENTAL
+#include "llvm/Support/CommandLine.h"
+static cl::opt<bool> CHECK_FREE_IDX("check-free-idx", cl::init(false));
+
+namespace {
+struct SZFrameSortingObject {
+  bool IsValid = false;         // true if we care about this Object.
+  uint32_t ObjectIndex = 0;     // Index of Object into MFI list.
+  uint32_t ObjectSize = 0;      // Size of Object in bytes.
+  uint32_t NumD12 = 0;          // Num 12-bit displacement operands.
+  uint32_t NumDPair = 0;        // Num displacements having both variants.
+  uint32_t NumD20 = 0;          // Num 20-bit displacement operands.
+  uint32_t NumNoFreeIdxReg = 0; // Num users without a free index register op.
+};
+
+struct SZFrameSortingComparator {
+  inline bool operator()(const SZFrameSortingObject &A,
+                         const SZFrameSortingObject &B) const {
+    // Favor the highest "density", computed as (Num / ObjectSize). The
+    // comparisons of two such fractions are refactored by multiplying both
+    // sides with A.ObjectSize * B.ObjectSize, in order to eliminate the
+    // (fp) divisions.
+
+    // Place all invalid objects at the end.
+    if (!A.IsValid)
+      return false;
+    if (!B.IsValid)
+      return true;
+
+    // Variable sized objects are not considered.
+    if (!A.ObjectSize || !B.ObjectSize)
+      return A.ObjectSize > B.ObjectSize;
+
+    // Make the best use of 12-bit displacements by putting them first.
+    if (A.NumD12 || B.NumD12) {
+      uint64_t A_D12 = uint64_t(A.NumD12) * uint64_t(B.ObjectSize);
+      uint64_t B_D12 = uint64_t(B.NumD12) * uint64_t(A.ObjectSize);
+      return A_D12 < B_D12;
+    }
+
+    // If all displacements will be in 20-bit range, favor the use of 12-bit
+    // displacements through shortening.
+    if (A.NumDPair || B.NumDPair) {
+      uint64_t A_DPair = uint64_t(A.NumDPair) * uint64_t(B.ObjectSize);
+      uint64_t B_DPair = uint64_t(B.NumDPair) * uint64_t(A.ObjectSize);
+      return A_DPair < B_DPair;
+    }
+
+    // Make the most use of the 20-bit displacement range.
+    if (A.NumD20 || B.NumD20) {
+      // EXPERIMENTAL: If the offset goes out of a 20-bit range, it will cost
+      // 2 instructions if there is not a free index reg. Check if this
+      // matters with CHECK_FREE_IDX (unlikely as it is an immediate load)...
+      unsigned AScore = A.NumD20 + (CHECK_FREE_IDX ? A.NumNoFreeIdxReg : 0);
+      unsigned BScore = B.NumD20 + (CHECK_FREE_IDX ? B.NumNoFreeIdxReg : 0);
+      uint64_t A_D20 = uint64_t(AScore) * uint64_t(B.ObjectSize);
+      uint64_t B_D20 = uint64_t(BScore) * uint64_t(A.ObjectSize);
+      return A_D20 < B_D20;
+    }
+
+    return A.ObjectIndex < B.ObjectIndex;
+  }
+};
+} // namespace
+
+void SystemZFrameLowering::orderFrameObjects(const MachineFunction &MF,
+                               SmallVectorImpl<int> &ObjectsToAllocate) const {
+  const MachineFrameInfo &MFI = MF.getFrameInfo();
+  const SystemZInstrInfo *TII =
+    static_cast<const SystemZInstrInfo *>(MF.getSubtarget().getInstrInfo());
+
+  // Make a vector of sorting objects with all MFI objects and mark those to
+  // be sorted as valid.
+  int64_t TotalSizeToAllocate = 0;
+  if (ObjectsToAllocate.size() <= 1)
+    return;
+  std::vector<SZFrameSortingObject> SortingObjects(MFI.getObjectIndexEnd());
+  for (auto &Obj : ObjectsToAllocate) {
+    SortingObjects[Obj].IsValid = true;
+    SortingObjects[Obj].ObjectIndex = Obj;
+    unsigned Size = MFI.getObjectSize(Obj);
+    SortingObjects[Obj].ObjectSize = Size;
+    TotalSizeToAllocate += Size;
+  }
+
+  bool AllInD20Range = TotalSizeToAllocate <= maxIntN(20);
+
+  // Examine uses for each interesting object and record legal displacements.
+  for (auto &MBB : MF) {
+    for (auto &MI : MBB) {
+      if (MI.isDebugInstr())
+        continue;
+      for (unsigned MOIdx = 0; MOIdx < MI.getNumOperands(); MOIdx++) {
+        const MachineOperand &MO = MI.getOperand(MOIdx);
+        if (!MO.isFI())
+          continue;
+        assert((MI.mayLoad() || MI.mayStore()) && "Expected memory use of FI.");
+        unsigned Opcode = MI.getOpcode();
+        const MCInstrDesc &MCID = TII->get(Opcode);
+        int Index = MO.getIndex();
+        if (Index >= 0 && Index < MFI.getObjectIndexEnd() &&
+            SortingObjects[Index].IsValid) {
+          // Check type of displacement operand.
+          bool HasDisplPair = TII->hasDisplacementPairInsn(Opcode);
+          if (AllInD20Range) {
+            if (HasDisplPair)
+              SortingObjects[Index].NumDPair++;
+            else if (!(MCID.TSFlags & SystemZII::Has20BitOffset))
+              SortingObjects[Index].NumD12++;
+          } else {
+            if ((MCID.TSFlags & SystemZII::Has20BitOffset) || HasDisplPair) {
+              SortingObjects[Index].NumD20++;
+              // Check for a free index register.
+              bool HasIndexReg = MCID.TSFlags & SystemZII::HasIndex;
+              if (!HasIndexReg || MI.getOperand(MOIdx + 2).getReg() != 0)
+                SortingObjects[Index].NumNoFreeIdxReg++;
+            }
+            else
+              SortingObjects[Index].NumD12++;
+          }
+        }
+      }
+    }
+  }
+
+  // Do an initial sorting.
+  llvm::stable_sort(SortingObjects, SZFrameSortingComparator());
+
+  // TODO: Walk through the list and change priority at 4k.
+  // TODO: Try second sort by original offsets into objects.
+
+  // Now modify the original list to represent the final order that
+  // we want.
+  unsigned Idx = 0;
+  for (auto &Obj : SortingObjects) {
+    // All invalid items are sorted at the end, so it's safe to stop.
+    if (!Obj.IsValid)
+      break;
+    ObjectsToAllocate[Idx++] = Obj.ObjectIndex;
+  }
+  assert(Idx == ObjectsToAllocate.size() && "Broken sorting of elements.");
+}
+
 bool SystemZFrameLowering::hasReservedCallFrame(
     const MachineFunction &MF) const {
   // The ELF ABI requires us to allocate 160 bytes of stack space for the
   // callee, with any outgoing stack arguments being placed above that. It
   // seems better to make that area a permanent feature of the frame even if
   // we're using a frame pointer. Similarly, 64-bit XPLINK requires 96 bytes
   // of stack space for the register save area.
   return true;
bool SystemZELFFrameLowering::assignCalleeSavedSpillSlots(
   unsigned LowGPR = 0;
   unsigned HighGPR = SystemZ::R15D;
   int StartSPOffset = SystemZMC::ELFCallFrameSize;
   for (auto &CS : CSI) {
     unsigned Reg = CS.getReg();
     int Offset = getRegSpillOffset(MF, Reg);
     if (Offset) {
       if (SystemZ::GR64BitRegClass.contains(Reg) && StartSPOffset > Offset) {
         LowGPR = Reg;
         StartSPOffset = Offset;
       }
       Offset -= SystemZMC::ELFCallFrameSize;
       int FrameIdx = MFFrame.CreateFixedSpillStackObject(8, Offset);
       CS.setFrameIdx(FrameIdx);
     } else
       CS.setFrameIdx(INT32_MAX);
   }
static void addSavedGPR(MachineBasicBlock &MBB, MachineInstrBuilder &MIB,
   bool IsLive = MBB.isLiveIn(GPR64) || MBB.isLiveIn(GPR32);
   if (!IsLive || !IsImplicit) {
     MIB.addReg(GPR64, getImplRegState(IsImplicit) | getKillRegState(!IsLive));
     if (!IsLive)
       MBB.addLiveIn(GPR64);
   }
 }
 
 bool SystemZELFFrameLowering::spillCalleeSavedRegisters(
     MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
     ArrayRef<CalleeSavedInfo> CSI, const TargetRegisterInfo *TRI) const {
   if (CSI.empty())
     return false;
 
   MachineFunction &MF = *MBB.getParent();
   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
   SystemZMachineFunctionInfo *ZFI = MF.getInfo<SystemZMachineFunctionInfo>();
if (MFFrame.getObjectOffset(I) >= 0) {
       MaxArgOffset = std::max(MaxArgOffset, ArgOffset);
     }
 
   uint64_t MaxReach = StackSize + MaxArgOffset;
   if (!isUInt<12>(MaxReach)) {
     // We may need register scavenging slots if some parts of the frame
     // are outside the reach of an unsigned 12-bit displacement.
     // Create 2 for the case where both addresses in an MVC are
     // out of range.
     RS->addScavengingFrameIndex(MFFrame.CreateStackObject(8, Align(8), false));
     RS->addScavengingFrameIndex(MFFrame.CreateStackObject(8, Align(8), false));
   }
 
   // If R6 is used as an argument register it is still callee saved. If it in
   // this case is not clobbered (and restored) it should never be marked as
   // killed.
   if (MF.front().isLiveIn(SystemZ::R6D) &&

llvm/lib/Target/SystemZ/SystemZInstrInfo.h

public:
 
   // Opcode is the opcode of an instruction that has an address operand,
   // and the caller wants to perform that instruction's operation on an
   // address that has displacement Offset.  Return the opcode of a suitable
   // instruction (which might be Opcode itself) or 0 if no such instruction
   // exists.
   unsigned getOpcodeForOffset(unsigned Opcode, int64_t Offset) const;
 
+  // Return true if Opcode has a mapping in 12 <-> 20 displacements.
+  bool hasDisplacementPairInsn(unsigned Opcode) const;
+
   // If Opcode is a load instruction that has a LOAD AND TEST form,
   // return the opcode for the testing form, otherwise return 0.
   unsigned getLoadAndTest(unsigned Opcode) const;
 
   // Return true if ROTATE AND ... SELECTED BITS can be used to select bits
   // Mask of the R2 operand, given that only the low BitSize bits of Mask are
   // significant.  Set Start and End to the I3 and I4 operands if so.
   bool isRxSBGMask(uint64_t Mask, unsigned BitSize,

llvm/lib/Target/SystemZ/SystemZInstrInfo.cpp

if (isInt<20>(Offset) && isInt<20>(Offset2)) {
 
     // Check whether Opcode allows signed 20-bit displacements.
     if (MCID.TSFlags & SystemZII::Has20BitOffset)
       return Opcode;
   }
   return 0;
 }
 
+bool SystemZInstrInfo::hasDisplacementPairInsn(unsigned Opcode) const {
+  const MCInstrDesc &MCID = get(Opcode);
+  if (MCID.TSFlags & SystemZII::Has20BitOffset)
+    return SystemZ::getDisp12Opcode(Opcode) >= 0;
+  return SystemZ::getDisp20Opcode(Opcode) >= 0;
+}
+
 unsigned SystemZInstrInfo::getLoadAndTest(unsigned Opcode) const {
   switch (Opcode) {
   case SystemZ::L:      return SystemZ::LT;
   case SystemZ::LY:     return SystemZ::LT;
   case SystemZ::LG:     return SystemZ::LTG;
   case SystemZ::LGF:    return SystemZ::LTGF;
   case SystemZ::LR:     return SystemZ::LTR;
   case SystemZ::LGFR:   return SystemZ::LTGFR;

llvm/test/CodeGen/SystemZ/frame-27.mir

+# RUN: llc -mtriple=s390x-linux-gnu -start-before=prologepilog %s -o - \
+# RUN:  -print-after=prologepilog -verify-machineinstrs 2>&1 | FileCheck %s
+# REQUIRES: asserts
+#
+# Test that stack objects are placed in a good way with respect to the
+#  displacement operands of users.
+
+--- |
+  define void @f1() { ret void }
+  define void @f2() { ret void }
+
+...
+# Test that %stack.0 is placed close to its D12 user.
+# CHECK:  # *** IR Dump After Prologue/Epilogue Insertion
+# CHECK:  # Machine code for function f1
+# CHECK:  fi#0: size=16, align=4, at location [SP-4272]
+# CHECK:  fi#1: size=4096, align=2, at location [SP-4256]
+# CHECK:      $r15d = AGHI $r15d(tied-def 0), -4288
+# CHECK-NOT: LAY
+# CHECK:     renamable $f0s = VL32 $r15d, 176, $noreg
+---
+name:            f1
+tracksRegLiveness: true
+stack:
+  - { id: 0, size: 16, alignment: 4 }
+  - { id: 1, size: 4096, alignment: 2 }
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    renamable $f0s = VL32 %stack.0, 0, $noreg
+    Return implicit $f0s
+
+...
+# Test that %stack.1 is placed close to its D12 user.
+# CHECK:  # *** IR Dump After Prologue/Epilogue Insertion
+# CHECK:  # Machine code for function f2
+# CHECK:  fi#0: size=16, align=4, at location [SP-176]
+# CHECK:  fi#1: size=4096, align=2, at location [SP-4272]
+# CHECK:      $r15d = AGHI $r15d(tied-def 0), -4288
+# CHECK-NOT:  LAY
+# CHECK:  renamable $f0s = VL32 $r15d, 176, $noreg
+---
+name:            f2
+tracksRegLiveness: true
+stack:
+  - { id: 0, size: 16, alignment: 4 }
+  - { id: 1, size: 4096, alignment: 2 }
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    renamable $f0s = VL32 %stack.1, 0, $noreg
+    Return implicit $f0s
+
+...