Improve virtual frame base register allocation heuristics.

  1. Allocate them in the entry block of the function to enable function-wide
     re-use. The instructions to create them should be re-materializable, so
     there shouldn't be additional cost compared to creating them local
     to the basic blocks where they are used.
  2. Collect all of the frame index references for the function and sort them
     by the local offset referenced. Iterate over the sorted list to
     allocate the virtual base registers. This enables creation of base
     registers optimized for positive-offset access of frame references.
     (Note: This may be appropriate to later be a target hook to do the
     sorting in a target appropriate manner. For now it's done here for
     simplicity.)



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

1 files changed, 109 insertions, 73 deletions

diff --git a/lib/CodeGen/LocalStackSlotAllocation.cpp b/lib/CodeGen/LocalStackSlotAllocation.cpp
index 8bb802fa16..7e366f0cee 100644
--- a/lib/CodeGen/LocalStackSlotAllocation.cpp
+++ b/lib/CodeGen/LocalStackSlotAllocation.cpp
@@ -24,6 +24,7 @@
 #include "llvm/Pass.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
@@ -42,6 +43,18 @@ STATISTIC(NumBaseRegisters, "Number of virtual frame base registers allocated");
 STATISTIC(NumReplacements, "Number of frame indices references replaced");
 
 namespace {
+  class FrameRef {
+    MachineBasicBlock::iterator MI; // Instr referencing the frame
+    int64_t LocalOffset;            // Local offset of the frame idx referenced
+  public:
+    FrameRef(MachineBasicBlock::iterator I, int64_t Offset) :
+      MI(I), LocalOffset(Offset) {}
+    bool operator<(const FrameRef &RHS) const {
+      return LocalOffset < RHS.LocalOffset;
+    }
+    MachineBasicBlock::iterator getMachineInstr() { return MI; }
+  };
+
   class LocalStackSlotPass: public MachineFunctionPass {
     SmallVector<int64_t,16> LocalOffsets;
 
@@ -217,22 +230,24 @@ bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) {
   const TargetFrameInfo &TFI = *Fn.getTarget().getFrameInfo();
   bool StackGrowsDown =
     TFI.getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown;
+  MachineBasicBlock::iterator InsertionPt = Fn.begin()->begin();
 
-  for (MachineFunction::iterator BB = Fn.begin(),
-         E = Fn.end(); BB != E; ++BB) {
-    // A base register definition is a register+offset pair.
-    SmallVector<std::pair<unsigned, int64_t>, 8> BaseRegisters;
+  // Collect all of the instructions in the block that reference
+  // a frame index. Also store the frame index referenced to ease later
+  // lookup. (For any insn that has more than one FI reference, we arbitrarily
+  // choose the first one).
+  SmallVector<FrameRef, 64> FrameReferenceInsns;
+  // A base register definition is a register+offset pair.
+  SmallVector<std::pair<unsigned, int64_t>, 8> BaseRegisters;
 
+
+  for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
       MachineInstr *MI = I;
       // Debug value instructions can't be out of range, so they don't need
       // any updates.
-      // FIXME: When we extend this stuff to handle functions with both
-      // VLAs and dynamic realignment, we should update the debug values
-      // to reference the new base pointer when possible.
       if (MI->isDebugValue())
         continue;
-
       // For now, allocate the base register(s) within the basic block
       // where they're used, and don't try to keep them around outside
       // of that. It may be beneficial to try sharing them more broadly
@@ -243,73 +258,94 @@ bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) {
         // Consider replacing all frame index operands that reference
         // an object allocated in the local block.
         if (MI->getOperand(i).isFI()) {
-          int FrameIdx = MI->getOperand(i).getIndex();
-
           // Don't try this with values not in the local block.
-          if (!MFI->isObjectPreAllocated(FrameIdx))
-            continue;
-
-          DEBUG(dbgs() << "Considering: " << *MI);
-          if (TRI->needsFrameBaseReg(MI, LocalOffsets[FrameIdx])) {
-            unsigned BaseReg = 0;
-            int64_t Offset = 0;
-            int64_t FrameSizeAdjust = StackGrowsDown ? MFI->getLocalFrameSize()
-              : 0;
-
-            DEBUG(dbgs() << "  Replacing FI in: " << *MI);
-
-            // If we have a suitable base register available, use it; otherwise
-            // create a new one. Note that any offset encoded in the
-            // instruction itself will be taken into account by the target,
-            // so we don't have to adjust for it here when reusing a base
-            // register.
-            std::pair<unsigned, int64_t> RegOffset;
-            if (lookupCandidateBaseReg(BaseRegisters, RegOffset,
-                                       FrameSizeAdjust,
-                                       LocalOffsets[FrameIdx],
-                                       MI, TRI)) {
-              DEBUG(dbgs() << "  Reusing base register " <<
-                    RegOffset.first << "\n");
-              // We found a register to reuse.
-              BaseReg = RegOffset.first;
-              Offset = FrameSizeAdjust + LocalOffsets[FrameIdx] -
-                RegOffset.second;
-            } else {
-              // No previously defined register was in range, so create a
-              // new one.
-              int64_t InstrOffset = TRI->getFrameIndexInstrOffset(MI, i);
-              const TargetRegisterClass *RC = TRI->getPointerRegClass();
-              BaseReg = Fn.getRegInfo().createVirtualRegister(RC);
-
-              DEBUG(dbgs() << "  Materializing base register " << BaseReg <<
-                    " at frame local offset " <<
-                    LocalOffsets[FrameIdx] + InstrOffset << "\n");
-              // Tell the target to insert the instruction to initialize
-              // the base register.
-              TRI->materializeFrameBaseRegister(I, BaseReg, FrameIdx,
-                                                InstrOffset);
-
-              // The base register already includes any offset specified
-              // by the instruction, so account for that so it doesn't get
-              // applied twice.
-              Offset = -InstrOffset;
-
-              int64_t BaseOffset = FrameSizeAdjust + LocalOffsets[FrameIdx] +
-                InstrOffset;
-              BaseRegisters.push_back(
-                std::pair<unsigned, int64_t>(BaseReg, BaseOffset));
-              ++NumBaseRegisters;
-              UsedBaseReg = true;
-            }
-            assert(BaseReg != 0 && "Unable to allocate virtual base register!");
-
-            // Modify the instruction to use the new base register rather
-            // than the frame index operand.
-            TRI->resolveFrameIndex(I, BaseReg, Offset);
-            DEBUG(dbgs() << "Resolved: " << *MI);
-
-            ++NumReplacements;
+          if (!MFI->isObjectPreAllocated(MI->getOperand(i).getIndex()))
+            break;
+          FrameReferenceInsns.
+            push_back(FrameRef(MI, LocalOffsets[MI->getOperand(i).getIndex()]));
+          break;
+        }
+      }
+    }
+  }
+  // Sort the frame references by local offset
+  array_pod_sort(FrameReferenceInsns.begin(), FrameReferenceInsns.end());
+
+
+  // Loop throught the frame references and allocate for them as necessary
+  for (int ref = 0, e = FrameReferenceInsns.size(); ref < e ; ++ref) {
+    MachineBasicBlock::iterator I =
+      FrameReferenceInsns[ref].getMachineInstr();
+    MachineInstr *MI = I;
+    for (unsigned idx = 0, e = MI->getNumOperands(); idx != e; ++idx) {
+      // Consider replacing all frame index operands that reference
+      // an object allocated in the local block.
+      if (MI->getOperand(idx).isFI()) {
+        int FrameIdx = MI->getOperand(idx).getIndex();
+
+        assert(MFI->isObjectPreAllocated(FrameIdx) &&
+               "Only pre-allocated locals expected!");
+
+        DEBUG(dbgs() << "Considering: " << *MI);
+        if (TRI->needsFrameBaseReg(MI, LocalOffsets[FrameIdx])) {
+          unsigned BaseReg = 0;
+          int64_t Offset = 0;
+          int64_t FrameSizeAdjust =
+            StackGrowsDown ? MFI->getLocalFrameSize() : 0;
+
+          DEBUG(dbgs() << "  Replacing FI in: " << *MI);
+
+          // If we have a suitable base register available, use it; otherwise
+          // create a new one. Note that any offset encoded in the
+          // instruction itself will be taken into account by the target,
+          // so we don't have to adjust for it here when reusing a base
+          // register.
+          std::pair<unsigned, int64_t> RegOffset;
+          if (lookupCandidateBaseReg(BaseRegisters, RegOffset,
+                                     FrameSizeAdjust,
+                                     LocalOffsets[FrameIdx],
+                                     MI, TRI)) {
+            DEBUG(dbgs() << "  Reusing base register " <<
+                  RegOffset.first << "\n");
+            // We found a register to reuse.
+            BaseReg = RegOffset.first;
+            Offset = FrameSizeAdjust + LocalOffsets[FrameIdx] -
+              RegOffset.second;
+          } else {
+            // No previously defined register was in range, so create a
+            // new one.
+            int64_t InstrOffset = TRI->getFrameIndexInstrOffset(MI, idx);
+            const TargetRegisterClass *RC = TRI->getPointerRegClass();
+            BaseReg = Fn.getRegInfo().createVirtualRegister(RC);
+
+            DEBUG(dbgs() << "  Materializing base register " << BaseReg <<
+                  " at frame local offset " <<
+                  LocalOffsets[FrameIdx] + InstrOffset << "\n");
+            // Tell the target to insert the instruction to initialize
+            // the base register.
+            TRI->materializeFrameBaseRegister(InsertionPt, BaseReg,
+                                              FrameIdx, InstrOffset);
+
+            // The base register already includes any offset specified
+            // by the instruction, so account for that so it doesn't get
+            // applied twice.
+            Offset = -InstrOffset;
+
+            int64_t BaseOffset = FrameSizeAdjust + LocalOffsets[FrameIdx] +
+              InstrOffset;
+            BaseRegisters.push_back(
+              std::pair<unsigned, int64_t>(BaseReg, BaseOffset));
+            ++NumBaseRegisters;
+            UsedBaseReg = true;
           }
+          assert(BaseReg != 0 && "Unable to allocate virtual base register!");
+
+          // Modify the instruction to use the new base register rather
+          // than the frame index operand.
+          TRI->resolveFrameIndex(I, BaseReg, Offset);
+          DEBUG(dbgs() << "Resolved: " << *MI);
+
+          ++NumReplacements;
         }
       }
     }