diff --git a/lib/CodeGen/LocalStackSlotAllocation.cpp b/lib/CodeGen/LocalStackSlotAllocation.cpp
index 8bb802f..7e366f0 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(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 @@
   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 @@
         // 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;
+          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());
 
-          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);
+  // 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();
 
-            // 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);
+        assert(MFI->isObjectPreAllocated(FrameIdx) &&
+               "Only pre-allocated locals expected!");
 
-              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);
+        DEBUG(dbgs() << "Considering: " << *MI);
+        if (TRI->needsFrameBaseReg(MI, LocalOffsets[FrameIdx])) {
+          unsigned BaseReg = 0;
+          int64_t Offset = 0;
+          int64_t FrameSizeAdjust =
+            StackGrowsDown ? MFI->getLocalFrameSize() : 0;
 
-              // The base register already includes any offset specified
-              // by the instruction, so account for that so it doesn't get
-              // applied twice.
-              Offset = -InstrOffset;
+          DEBUG(dbgs() << "  Replacing FI in: " << *MI);
 
-              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!");
+          // 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);
 
-            // Modify the instruction to use the new base register rather
-            // than the frame index operand.
-            TRI->resolveFrameIndex(I, BaseReg, Offset);
-            DEBUG(dbgs() << "Resolved: " << *MI);
+            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);
 
-            ++NumReplacements;
+            // 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;
         }
       }
     }