Introduce AllocaManager, a class for managing allocas.

The AllocaManager performs stack layout for alloca objects. It is capable
of analyzing alloca liveness and sharing space between multiple allocas.

5 files changed, 891 insertions, 40 deletions

diff --git a/lib/Target/JSBackend/AllocaManager.cpp b/lib/Target/JSBackend/AllocaManager.cpp
new file mode 100644
index 0000000000..6c4c49f0d0
--- /dev/null
+++ b/lib/Target/JSBackend/AllocaManager.cpp
@@ -0,0 +1,516 @@
+//===-- AllocaManager.cpp -------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the AllocaManager class.
+//
+// The AllocaManager computes a frame layout, assigning every static alloca an
+// offset. It does alloca liveness analysis in order to reuse stack memory,
+// using lifetime intrinsics.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "allocamanager"
+#include "AllocaManager.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/CFG.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/Timer.h"
+#include "llvm/ADT/Statistic.h"
+using namespace llvm;
+
+STATISTIC(NumAllocas, "Number of allocas eliminated");
+
+// Return the size of the given alloca.
+uint64_t AllocaManager::getSize(const AllocaInst *AI) {
+  assert(AI->isStaticAlloca());
+  return DL->getTypeAllocSize(AI->getAllocatedType()) *
+         cast<ConstantInt>(AI->getArraySize())->getValue().getZExtValue();
+}
+
+// Return the alignment of the given alloca.
+unsigned AllocaManager::getAlignment(const AllocaInst *AI) {
+  assert(AI->isStaticAlloca());
+  return std::max(AI->getAlignment(),
+                  DL->getABITypeAlignment(AI->getAllocatedType()));
+}
+
+AllocaManager::AllocaInfo AllocaManager::getInfo(const AllocaInst *AI) {
+  assert(AI->isStaticAlloca());
+  return AllocaInfo(AI, getSize(AI), getAlignment(AI));
+}
+
+// Given a lifetime_start or lifetime_end intrinsic, determine if it's
+// describing a static alloc memory region suitable for our analysis. If so,
+// return the alloca, otherwise return NULL.
+const AllocaInst *
+AllocaManager::getAllocaFromIntrinsic(const CallInst *CI) {
+  const IntrinsicInst *II = cast<IntrinsicInst>(CI);
+  assert(II->getIntrinsicID() == Intrinsic::lifetime_start ||
+         II->getIntrinsicID() == Intrinsic::lifetime_end);
+
+  // Lifetime intrinsics have a size as their first argument and a pointer as
+  // their second argument.
+  const Value *Size = II->getArgOperand(0);
+  const Value *Ptr = II->getArgOperand(1);
+
+  // Check to see if we can convert the size to a host integer. If we can't,
+  // it's probably not worth worrying about.
+  const ConstantInt *SizeCon = dyn_cast<ConstantInt>(Size);
+  if (!SizeCon) return NULL;
+  const APInt &SizeAP = SizeCon->getValue();
+  if (SizeAP.getActiveBits() > 64) return NULL;
+  uint64_t MarkedSize = SizeAP.getZExtValue();
+
+  // We're only interested if the pointer is a static alloca.
+  const AllocaInst *AI = dyn_cast<AllocaInst>(Ptr->stripPointerCasts());
+  if (!AI || !AI->isStaticAlloca()) return NULL;
+
+  // Make sure the size covers the alloca.
+  if (MarkedSize < getSize(AI)) return NULL;
+
+  return AI;
+}
+
+int AllocaManager::AllocaSort(const void *l, const void *r) {
+  const AllocaInfo *li = static_cast<const AllocaInfo *>(l);
+  const AllocaInfo *ri = static_cast<const AllocaInfo *>(r);
+
+  // Sort by alignment to minimize padding.
+  if (li->getAlignment() > ri->getAlignment()) return -1;
+  if (li->getAlignment() < ri->getAlignment()) return 1;
+
+  // Ensure a stable sort. We can do this because the pointers are
+  // pointing into the same array.
+  if (li > ri) return -1;
+  if (li < ri) return 1;
+
+  return 0;
+}
+
+// Collect allocas
+void AllocaManager::collectMarkedAllocas() {
+  NamedRegionTimer Timer("Collect Marked Allocas", "AllocaManager",
+                         TimePassesIsEnabled);
+
+  // Weird semantics: If an alloca *ever* appears in a lifetime start or end
+  // within the same function, its lifetime begins only at the explicit lifetime
+  // starts and ends only at the explicit lifetime ends and function exit
+  // points. Otherwise, its lifetime begins in the entry block and it is live
+  // everywhere.
+  //
+  // And so, instead of just walking the entry block to find all the static
+  // allocas, we walk the whole body to find the intrinsics so we can find the
+  // set of static allocas referenced in the intrinsics.
+  for (Function::const_iterator FI = F->begin(), FE = F->end();
+       FI != FE; ++FI) {
+    for (BasicBlock::const_iterator BI = FI->begin(), BE = FI->end();
+         BI != BE; ++BI) {
+      const CallInst *CI = dyn_cast<CallInst>(BI);
+      if (!CI) continue;
+
+      const Value *Callee = CI->getCalledValue();
+      if (Callee == LifetimeStart || Callee == LifetimeEnd) {
+        if (const AllocaInst *AI = getAllocaFromIntrinsic(CI)) {
+          Allocas.insert(std::make_pair(AI, 0));
+        }
+      }
+    }
+  }
+
+  // All that said, we still want the intrinsics in the order they appear in the
+  // block, so that we can represent later ones with earlier ones and skip
+  // worrying about dominance, so run through the entry block and index those
+  // allocas which we identified above.
+  AllocasByIndex.reserve(Allocas.size());
+  const BasicBlock *EntryBB = &F->getEntryBlock();
+  for (BasicBlock::const_iterator BI = EntryBB->begin(), BE = EntryBB->end();
+       BI != BE; ++BI) {
+    const AllocaInst *AI = dyn_cast<AllocaInst>(BI);
+    if (!AI || !AI->isStaticAlloca()) continue;
+
+    AllocaMap::iterator I = Allocas.find(AI);
+    if (I != Allocas.end()) {
+      I->second = AllocasByIndex.size();
+      AllocasByIndex.push_back(getInfo(AI));
+    }
+  }
+  assert(AllocasByIndex.size() == Allocas.size());
+}
+
+// Calculate the starting point from which inter-block liveness will be
+// computed.
+void AllocaManager::collectBlocks() {
+  NamedRegionTimer Timer("Collect Blocks", "AllocaManager",
+                         TimePassesIsEnabled);
+
+  size_t AllocaCount = AllocasByIndex.size();
+
+  BitVector Seen(AllocaCount);
+
+  for (Function::const_iterator I = F->begin(), E = F->end(); I != E; ++I) {
+    const BasicBlock *BB = I;
+
+    BlockLifetimeInfo &BLI = BlockLiveness[BB];
+    BLI.Start.resize(AllocaCount);
+    BLI.End.resize(AllocaCount);
+
+    // Track which allocas we've seen. This is used because if a lifetime start
+    // is the first lifetime marker for an alloca in a block, the alloca is
+    // live-in.
+    Seen.reset();
+
+    // Walk the instructions and compute the Start and End sets.
+    for (BasicBlock::const_iterator BI = BB->begin(), BE = BB->end();
+         BI != BE; ++BI) {
+      const CallInst *CI = dyn_cast<CallInst>(BI);
+      if (!CI) continue;
+
+      const Value *Callee = CI->getCalledValue();
+      if (Callee == LifetimeStart) {
+        if (const AllocaInst *AI = getAllocaFromIntrinsic(CI)) {
+          AllocaMap::const_iterator MI = Allocas.find(AI);
+          if (MI != Allocas.end()) {
+            size_t AllocaIndex = MI->second;
+            if (!Seen.test(AllocaIndex)) {
+              BLI.Start.set(AllocaIndex);
+            }
+            BLI.End.reset(AllocaIndex);
+            Seen.set(AllocaIndex);
+          }
+        }
+      } else if (Callee == LifetimeEnd) {
+        if (const AllocaInst *AI = getAllocaFromIntrinsic(CI)) {
+          AllocaMap::const_iterator MI = Allocas.find(AI);
+          if (MI != Allocas.end()) {
+            size_t AllocaIndex = MI->second;
+            BLI.End.set(AllocaIndex);
+            Seen.set(AllocaIndex);
+          }
+        }
+      }
+    }
+
+    // Lifetimes that start in this block and do not end here are live-out.
+    BLI.LiveOut = BLI.Start;
+    BLI.LiveOut.reset(BLI.End);
+    if (BLI.LiveOut.any()) {
+      for (succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB);
+           SI != SE; ++SI) {
+        InterBlockWorklist.insert(*SI);
+      }
+    }
+
+    // Lifetimes that end in this block and do not start here are live-in.
+    // TODO: Is this actually true? What are the semantics of a standalone
+    // lifetime end? See also the code in computeInterBlockLiveness.
+    BLI.LiveIn = BLI.End;
+    BLI.LiveIn.reset(BLI.Start);
+    if (BLI.LiveIn.any()) {
+      for (const_pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
+           PI != PE; ++PI) {
+        InterBlockWorklist.insert(*PI);
+      }
+    }
+  }
+}
+
+// Compute the LiveIn and LiveOut sets for each block in F.
+void AllocaManager::computeInterBlockLiveness() {
+  NamedRegionTimer Timer("Compute inter-block liveness", "AllocaManager",
+                         TimePassesIsEnabled);
+
+  size_t AllocaCount = AllocasByIndex.size();
+
+  BitVector Temp(AllocaCount);
+
+  // This is currently using a very simple-minded bi-directional liveness
+  // propagation algorithm. Numerous opportunities for compile time
+  // speedups here.
+  while (!InterBlockWorklist.empty()) {
+    const BasicBlock *BB = InterBlockWorklist.pop_back_val();
+    BlockLifetimeInfo &BLI = BlockLiveness[BB];
+
+    // Compute the new live-in set.
+    for (const_pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
+         PI != PE; ++PI) {
+      Temp |= BlockLiveness[*PI].LiveOut;
+    }
+
+    // If it contains new live blocks, prepare to propagate them.
+    if (Temp.test(BLI.LiveIn)) {
+      BLI.LiveIn |= Temp;
+      BLI.LiveOut |= Temp;
+      BLI.LiveOut.reset(BLI.End);
+      for (succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB);
+           SI != SE; ++SI) {
+        InterBlockWorklist.insert(*SI);
+      }
+    }
+    Temp.reset();
+
+    // Compute the new live-out set.
+    for (succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB);
+         SI != SE; ++SI) {
+      Temp |= BlockLiveness[*SI].LiveIn;
+    }
+
+    // If it contains new live blocks, prepare to propagate them.
+    if (Temp.test(BLI.LiveOut)) {
+      // TODO: As above, what are the semantics of a standalone lifetime end?
+      BLI.LiveOut |= Temp;
+      BLI.LiveIn |= Temp;
+      BLI.LiveIn.reset(BLI.Start);
+      for (const_pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
+           PI != PE; ++PI) {
+        InterBlockWorklist.insert(*PI);
+      }
+    }
+    Temp.reset();
+  }
+}
+
+// Determine overlapping liveranges within blocks.
+void AllocaManager::computeIntraBlockLiveness() {
+  NamedRegionTimer Timer("Compute intra-block liveness", "AllocaManager",
+                         TimePassesIsEnabled);
+
+  size_t AllocaCount = AllocasByIndex.size();
+
+  BitVector Current(AllocaCount);
+
+  AllocaCompatibility.resize(AllocaCount, BitVector(AllocaCount, true));
+
+  for (Function::const_iterator I = F->begin(), E = F->end(); I != E; ++I) {
+    const BasicBlock *BB = I;
+    const BlockLifetimeInfo &BLI = BlockLiveness[BB];
+
+    Current = BLI.LiveIn;
+
+    for (int i = Current.find_first(); i >= 0; i = Current.find_next(i)) {
+      AllocaCompatibility[i].reset(Current);
+    }
+
+    for (BasicBlock::const_iterator BI = BB->begin(), BE = BB->end();
+         BI != BE; ++BI) {
+      const CallInst *CI = dyn_cast<CallInst>(BI);
+      if (!CI) continue;
+
+      const Value *Callee = CI->getCalledValue();
+      if (Callee == LifetimeStart) {
+        if (const AllocaInst *AI = getAllocaFromIntrinsic(CI)) {
+          size_t AIndex = Allocas[AI];
+          // We conflict with everything else that's currently live.
+          AllocaCompatibility[AIndex].reset(Current);
+          // Everything else that's currently live conflicts with us.
+          for (int i = Current.find_first(); i >= 0; i = Current.find_next(i)) {
+            AllocaCompatibility[i].reset(AIndex);
+          }
+          // We're now live.
+          Current.set(AIndex);
+        }
+      } else if (Callee == LifetimeEnd) {
+        if (const AllocaInst *AI = getAllocaFromIntrinsic(CI)) {
+          size_t AIndex = Allocas[AI];
+          // We're no longer live.
+          Current.reset(AIndex);
+        }
+      }
+    }
+  }
+}
+
+// Decide which allocas will represent which other allocas, and if so what their
+// size and alignment will need to be.
+void AllocaManager::computeRepresentatives() {
+  NamedRegionTimer Timer("Compute Representatives", "AllocaManager",
+                         TimePassesIsEnabled);
+
+  for (size_t i = 0, e = AllocasByIndex.size(); i != e; ++i) {
+    // If we've already represented this alloca with another, don't visit it.
+    if (AllocasByIndex[i].isForwarded()) continue;
+    if (i > size_t(INT_MAX)) continue;
+
+    // Find compatible allocas. This is a simple greedy algorithm.
+    for (int j = int(i); ; ) {
+      assert(j >= int(i));
+      j = AllocaCompatibility[i].find_next(j);
+      assert(j != int(i));
+      if (j < 0) break;
+      if (!AllocaCompatibility[j][i]) continue;
+
+      DEBUG(dbgs() << "Allocas: "
+                      "Representing "
+                   << AllocasByIndex[j].getInst()->getName() << " "
+                      "with "
+                   << AllocasByIndex[i].getInst()->getName() << "\n");
+      ++NumAllocas;
+
+      assert(!AllocasByIndex[j].isForwarded());
+
+      AllocasByIndex[i].mergeSize(AllocasByIndex[j].getSize());
+      AllocasByIndex[i].mergeAlignment(AllocasByIndex[j].getAlignment());
+      AllocasByIndex[j].forward(i);
+
+      AllocaCompatibility[i] &= AllocaCompatibility[j];
+      AllocaCompatibility[j].reset();
+    }
+  }
+}
+
+void AllocaManager::computeFrameOffsets() {
+  NamedRegionTimer Timer("Compute Frame Offsets", "AllocaManager",
+                         TimePassesIsEnabled);
+
+  // Walk through the entry block and collect all the allocas, including the
+  // ones with no lifetime markers that we haven't looked at yet. We walk in
+  // reverse order so that we can set the representative allocas as those that
+  // dominate the others as we go.
+  const BasicBlock *EntryBB = &F->getEntryBlock();
+  for (BasicBlock::const_iterator BI = EntryBB->begin(), BE = EntryBB->end();
+       BI != BE; ++BI) {
+    const AllocaInst *AI = dyn_cast<AllocaInst>(BI);
+    if (!AI || !AI->isStaticAlloca()) continue;
+
+    AllocaMap::const_iterator I = Allocas.find(AI);
+    if (I != Allocas.end()) {
+      // An alloca with lifetime markers. Emit the record we've crafted for it,
+      // if we've chosen to keep it as a representative.
+      const AllocaInfo &Info = AllocasByIndex[I->second];
+      if (!Info.isForwarded()) {
+        SortedAllocas.push_back(Info);
+      }
+    } else {
+      // An alloca with no lifetime markers.
+      SortedAllocas.push_back(getInfo(AI));
+    }
+  }
+
+  // Sort the allocas to hopefully reduce padding.
+  array_pod_sort(SortedAllocas.begin(), SortedAllocas.end(), AllocaSort);
+
+  // Assign stack offsets.
+  uint64_t CurrentOffset = 0;
+  for (SmallVectorImpl<AllocaInfo>::const_iterator I = SortedAllocas.begin(),
+       E = SortedAllocas.end(); I != E; ++I) {
+    const AllocaInfo &Info = *I;
+    uint64_t NewOffset = RoundUpToAlignment(CurrentOffset, Info.getAlignment());
+
+    // For backwards compatibility, align every power-of-two multiple alloca to
+    // its greatest power-of-two factor, up to 8 bytes. In particular, cube2hash
+    // is known to depend on this.
+    // TODO: Consider disabling this and making people fix their code.
+    if (uint64_t Size = Info.getSize()) {
+      uint64_t P2 = uint64_t(1) << CountTrailingZeros_64(Size);
+      unsigned CompatAlign = unsigned(std::min(P2, uint64_t(8)));
+      NewOffset = RoundUpToAlignment(NewOffset, CompatAlign);
+    }
+
+    const AllocaInst *AI = Info.getInst();
+    StaticAllocas[AI] = StaticAllocation(AI, NewOffset);
+
+    CurrentOffset = NewOffset + Info.getSize();
+  }
+
+  // Add allocas that were represented by other allocas to the StaticAllocas map
+  // so that our clients can look them up.
+  for (unsigned i = 0, e = AllocasByIndex.size(); i != e; ++i) {
+    const AllocaInfo &Info = AllocasByIndex[i];
+    if (!Info.isForwarded()) continue;
+    size_t j = Info.getForwardedID();
+    assert(!AllocasByIndex[j].isForwarded());
+
+    StaticAllocaMap::const_iterator I =
+      StaticAllocas.find(AllocasByIndex[j].getInst());
+    assert(I != StaticAllocas.end());
+
+    std::pair<StaticAllocaMap::const_iterator, bool> Pair =
+      StaticAllocas.insert(std::make_pair(AllocasByIndex[i].getInst(),
+                                          I->second));
+    assert(Pair.second); (void)Pair;
+  }
+
+  // Record the final frame size. Keep the stack pointer 16-byte aligned.
+  FrameSize = CurrentOffset;
+  FrameSize = RoundUpToAlignment(FrameSize, 16);
+
+  DEBUG(dbgs() << "Allocas: "
+                  "Statically allocated frame size is " << FrameSize << "\n");
+}
+
+AllocaManager::AllocaManager() {
+}
+
+void AllocaManager::analyze(const Function &Func, const DataLayout &Layout) {
+  NamedRegionTimer Timer("AllocaManager", TimePassesIsEnabled);
+
+  assert(Allocas.empty());
+  assert(AllocasByIndex.empty());
+  assert(AllocaCompatibility.empty());
+  assert(BlockLiveness.empty());
+  assert(StaticAllocas.empty());
+  assert(SortedAllocas.empty());
+
+  DL = &Layout;
+  F = &Func;
+
+  // Get the declarations for the lifetime intrinsics so we can quickly test to
+  // see if they are used at all, and for use later if they are.
+  const Module *M = F->getParent();
+  LifetimeStart = M->getFunction(Intrinsic::getName(Intrinsic::lifetime_start));
+  LifetimeEnd = M->getFunction(Intrinsic::getName(Intrinsic::lifetime_end));
+
+  if ((LifetimeStart && !LifetimeStart->use_empty()) ||
+      (LifetimeEnd   && !LifetimeEnd->use_empty())) {
+
+    collectMarkedAllocas();
+
+    if (!AllocasByIndex.empty()) {
+      DEBUG(dbgs() << "Allocas: "
+                   << AllocasByIndex.size() << " marked allocas found\n");
+
+      collectBlocks();
+      computeInterBlockLiveness();
+      computeIntraBlockLiveness();
+      BlockLiveness.clear();
+
+      computeRepresentatives();
+      AllocaCompatibility.clear();
+    }
+  }
+
+  computeFrameOffsets();
+  SortedAllocas.clear();
+  Allocas.clear();
+  AllocasByIndex.clear();
+}
+
+void AllocaManager::clear() {
+  StaticAllocas.clear();
+}
+
+bool
+AllocaManager::getFrameOffset(const AllocaInst *AI, uint64_t *Offset) const {
+  assert(AI->isStaticAlloca());
+  StaticAllocaMap::const_iterator I = StaticAllocas.find(AI);
+  assert(I != StaticAllocas.end());
+  *Offset = I->second.Offset;
+  return AI == I->second.Representative;
+}
+
+const AllocaInst *
+AllocaManager::getRepresentative(const AllocaInst *AI) const {
+  assert(AI->isStaticAlloca());
+  StaticAllocaMap::const_iterator I = StaticAllocas.find(AI);
+  assert(I != StaticAllocas.end());
+  return I->second.Representative;
+}
diff --git a/lib/Target/JSBackend/AllocaManager.h b/lib/Target/JSBackend/AllocaManager.h
new file mode 100644
index 0000000000..0aafeb4a06
--- /dev/null
+++ b/lib/Target/JSBackend/AllocaManager.h
@@ -0,0 +1,171 @@
+//===-- AllocaManager.h ---------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass declares the AllocaManager class.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef JSBACKEND_ALLOCAMANAGER_H
+#define JSBACKEND_ALLOCAMANAGER_H
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/SetVector.h"
+
+namespace llvm {
+
+class AllocaInst;
+class BasicBlock;
+class CallInst;
+class DataLayout;
+class Function;
+
+/// Compute frame layout for allocas.
+class AllocaManager {
+  const DataLayout *DL;
+  const Function *LifetimeStart;
+  const Function *LifetimeEnd;
+  const Function *F;
+
+  // Per-block lifetime information.
+  struct BlockLifetimeInfo {
+    BitVector Start;
+    BitVector End;
+    BitVector LiveIn;
+    BitVector LiveOut;
+  };
+  typedef DenseMap<const BasicBlock *, BlockLifetimeInfo> LivenessMap;
+  LivenessMap BlockLiveness;
+
+  // Worklist for inter-block liveness analysis.
+  typedef SmallSetVector<const BasicBlock *, 8> InterBlockWorklistVec;
+  InterBlockWorklistVec InterBlockWorklist;
+
+  // Map allocas to their index in AllocasByIndex.
+  typedef DenseMap<const AllocaInst *, size_t> AllocaMap;
+  AllocaMap Allocas;
+
+  // Information about an alloca. Note that the size and alignment may vary
+  // from what's in the actual AllocaInst when an alloca is also representing
+  // another with perhaps greater size and/or alignment needs.
+  //
+  // When an alloca is represented by another, its AllocaInfo is marked as
+  // "forwarded", at which point it no longer holds a size and alignment, but
+  // the index of the representative AllocaInfo.
+  class AllocaInfo {
+    const AllocaInst *Inst;
+    uint64_t Size;
+    unsigned Alignment;
+
+  public:
+    AllocaInfo(const AllocaInst *I, uint64_t S, unsigned A)
+      : Inst(I), Size(S), Alignment(A) {
+      assert(I != NULL);
+      assert(A != 0);
+      assert(!isForwarded());
+    }
+
+    bool isForwarded() const { return Alignment == 0; }
+
+    size_t getForwardedID() const {
+      assert(isForwarded());
+      return static_cast<size_t>(Size);
+    }
+
+    void forward(size_t i) {
+      assert(!isForwarded());
+      Alignment = 0;
+      Size = i;
+      assert(isForwarded());
+      assert(getForwardedID() == i);
+    }
+
+    const AllocaInst *getInst() const { return Inst; }
+
+    uint64_t getSize() const { assert(!isForwarded()); return Size; }
+    unsigned getAlignment() const { assert(!isForwarded()); return Alignment; }
+
+    void mergeSize(uint64_t S) {
+      assert(!isForwarded());
+      Size = std::max(Size, S);
+      assert(!isForwarded());
+    }
+    void mergeAlignment(unsigned A) {
+      assert(A != 0);
+      assert(!isForwarded());
+      Alignment = std::max(Alignment, A);
+      assert(!isForwarded());
+    }
+  };
+  typedef SmallVector<AllocaInfo, 32> AllocaVec;
+  AllocaVec AllocasByIndex;
+
+  // For each alloca, which allocas can it safely represent? Allocas are
+  // identified by AllocasByIndex index.
+  // TODO: Vector-of-vectors isn't the fastest data structure possible here.
+  typedef SmallVector<BitVector, 32> AllocaCompatibilityVec;
+  AllocaCompatibilityVec AllocaCompatibility;
+
+  // This is for allocas that will eventually be sorted.
+  SmallVector<AllocaInfo, 32> SortedAllocas;
+
+  // Static allocation results.
+  struct StaticAllocation {
+    const AllocaInst *Representative;
+    uint64_t Offset;
+    StaticAllocation() {}
+    StaticAllocation(const AllocaInst *A, uint64_t O)
+      : Representative(A), Offset(O) {}
+  };
+  typedef DenseMap<const AllocaInst *, StaticAllocation> StaticAllocaMap;
+  StaticAllocaMap StaticAllocas;
+  uint64_t FrameSize;
+
+  uint64_t getSize(const AllocaInst *AI);
+  unsigned getAlignment(const AllocaInst *AI);
+  AllocaInfo getInfo(const AllocaInst *AI);
+  const AllocaInst *getAllocaFromIntrinsic(const CallInst *CI);
+  static int AllocaSort(const void *l, const void *r);
+
+  void collectMarkedAllocas();
+  void collectBlocks();
+  void computeInterBlockLiveness();
+  void computeIntraBlockLiveness();
+  void computeRepresentatives();
+  void computeFrameOffsets();
+
+public:
+  AllocaManager();
+
+  /// Analyze the given function and prepare for getReplacement queries.
+  void analyze(const Function &Func, const DataLayout &Layout);
+
+  /// Reset all stored state.
+  void clear();
+
+  /// Return the representative alloca for the given alloca. When allocas are
+  /// merged, one is chosen as the representative to stand for the rest.
+  /// References to the alloca should take the form of references to the
+  /// representative.
+  const AllocaInst *getRepresentative(const AllocaInst *AI) const;
+
+  /// Set *offset to the frame offset for the given alloca. Return true if the
+  /// given alloca is representative, meaning that it needs an explicit
+  /// definition in the function entry. Return false if some other alloca
+  /// represents this one.
+  bool getFrameOffset(const AllocaInst *AI, uint64_t *offset) const;
+
+  /// Return the total frame size for all static allocas and associated padding.
+  uint64_t getFrameSize() const { return FrameSize; }
+};
+
+} // namespace llvm
+
+#endif
diff --git a/lib/Target/JSBackend/CMakeLists.txt b/lib/Target/JSBackend/CMakeLists.txt
index a80e23050a..521210e94d 100644
--- a/lib/Target/JSBackend/CMakeLists.txt
+++ b/lib/Target/JSBackend/CMakeLists.txt
@@ -1,4 +1,5 @@
 add_llvm_target(JSBackendCodeGen
+  AllocaManager.cpp
   ExpandI64.cpp
   JSBackend.cpp
   JSTargetMachine.cpp
diff --git a/lib/Target/JSBackend/JSBackend.cpp b/lib/Target/JSBackend/JSBackend.cpp
index 3f1fdd6fb8..b440980010 100644
--- a/lib/Target/JSBackend/JSBackend.cpp
+++ b/lib/Target/JSBackend/JSBackend.cpp
@@ -16,6 +16,7 @@
 
 #include "JSTargetMachine.h"
 #include "MCTargetDesc/JSBackendMCTargetDesc.h"
+#include "AllocaManager.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallString.h"
@@ -103,7 +104,6 @@ namespace {
   typedef std::vector<unsigned char> HeapData;
   typedef std::pair<unsigned, unsigned> Address;
   typedef std::map<std::string, Type::TypeID> VarMap;
-  typedef std::map<const AllocaInst*, unsigned> AllocaIntMap;
   typedef std::map<std::string, Address> GlobalAddressMap;
   typedef std::vector<std::string> FunctionTable;
   typedef std::map<std::string, FunctionTable> FunctionTableMap;
@@ -121,8 +121,7 @@ namespace {
     unsigned UniqueNum;
     ValueMap ValueNames;
     VarMap UsedVars;
-    AllocaIntMap StackAllocs;
-    unsigned TotalStackAllocs;
+    AllocaManager Allocas;
     HeapData GlobalData8;
     HeapData GlobalData32;
     HeapData GlobalData64;
@@ -573,6 +572,16 @@ const std::string &JSWriter::getJSName(const Value* val) {
   if (I != ValueNames.end() && I->first == val)
     return I->second;
 
+  // If this is an alloca we've replaced with another, use the other name.
+  if (const AllocaInst *AI = dyn_cast<AllocaInst>(val)) {
+    if (AI->isStaticAlloca()) {
+      const AllocaInst *Rep = Allocas.getRepresentative(AI);
+      if (Rep != AI) {
+        return getJSName(Rep);
+      }
+    }
+  }
+
   std::string name;
   if (val->hasName()) {
     name = val->getName().str();
@@ -1377,22 +1386,31 @@ void JSWriter::generateExpression(const User *I, raw_string_ostream& Code) {
     break;
   }
   case Instruction::Alloca: {
-    if (NativizedVars.count(I)) {
+    const AllocaInst* AI = cast<AllocaInst>(I);
+
+    if (NativizedVars.count(AI)) {
       // nativized stack variable, we just need a 'var' definition
-      UsedVars[getJSName(I)] = cast<PointerType>(I->getType())->getElementType()->getTypeID();
+      UsedVars[getJSName(AI)] = AI->getType()->getElementType()->getTypeID();
       return;
     }
-    const AllocaInst* AI = cast<AllocaInst>(I);
-    AllocaIntMap::iterator AIMI = StackAllocs.find(AI);
-    if (AIMI != StackAllocs.end()) {
-      // fixed-size allocation that is already taken into account in the big initial allocation
-      if (AIMI->second) {
-        Code << getAssign(AI) << "sp + " << utostr(AIMI->second) << "|0";
-      } else {
-        Code << getAssign(AI) << "sp";
+
+    // Fixed-size entry-block allocations are allocated all at once in the
+    // function prologue.
+    if (AI->isStaticAlloca()) {
+      uint64_t Offset;
+      if (Allocas.getFrameOffset(AI, &Offset)) {
+        if (Offset != 0) {
+          Code << getAssign(AI) << "sp + " << Offset << "|0";
+        } else {
+          Code << getAssign(AI) << "sp";
+        }
+        break;
       }
-      break;
+      // Otherwise, this alloca is being represented by another alloca, so
+      // there's nothing to print.
+      return;
     }
+
     Type *T = AI->getAllocatedType();
     std::string Size;
     uint64_t BaseSize = DL->getTypeAllocSize(T);
@@ -1784,8 +1802,8 @@ void JSWriter::printFunctionBody(const Function *F) {
 
   // Emit stack entry
   Out << " " << getAdHocAssign("sp", Type::getInt32Ty(F->getContext())) << "STACKTOP;";
-  if (TotalStackAllocs) {
-    Out << "\n " << "STACKTOP = STACKTOP + " + utostr(TotalStackAllocs) + "|0;";
+  if (uint64_t FrameSize = Allocas.getFrameSize()) {
+    Out << "\n " "STACKTOP = STACKTOP + " << FrameSize << "|0;";
   }
 
   // Emit (relooped) code
@@ -1829,30 +1847,7 @@ void JSWriter::printFunction(const Function *F) {
   UsedVars.clear();
   UniqueNum = 0;
   calculateNativizedVars(F);
-
-  StackAllocs.clear();
-  TotalStackAllocs = 0;
-
-  for (Function::const_iterator BI = F->begin(), BE = F->end(); BI != BE; ++BI) {
-    for (BasicBlock::const_iterator II = BI->begin(), E = BI->end(); II != E; ++II) {
-      if (const AllocaInst* AI = dyn_cast<AllocaInst>(II)) {
-        Type *T = AI->getAllocatedType();
-        const Value *AS = AI->getArraySize();
-        unsigned BaseSize = DL->getTypeAllocSize(T);
-        if (const ConstantInt *CI = dyn_cast<ConstantInt>(AS)) {
-          // TODO: group by alignment to avoid unnecessary padding
-          unsigned Size = stackAlign(BaseSize * CI->getZExtValue());
-          StackAllocs[AI] = TotalStackAllocs;
-          TotalStackAllocs += Size;
-        }
-      } else {
-        // stop after the first non-alloca - could alter the stack
-        // however, ptrtoints are ok, and the legalizaton passes introduce them
-        if (!isa<PtrToIntInst>(II)) break;
-      }
-    }
-    break;
-  }
+  Allocas.analyze(*F, *DL);
 
   // Emit the function
 
@@ -1875,6 +1870,8 @@ void JSWriter::printFunction(const Function *F) {
   printFunctionBody(F);
   Out << "}";
   nl(Out);
+
+  Allocas.clear();
 }
 
 void JSWriter::printModuleBody() {
diff --git a/test/CodeGen/JS/allocamanager.ll b/test/CodeGen/JS/allocamanager.ll
new file mode 100644
index 0000000000..c2f7c5f53d
--- /dev/null
+++ b/test/CodeGen/JS/allocamanager.ll
@@ -0,0 +1,166 @@
+; RUN: llc -march=js -o - < %s | FileCheck %s
+
+; Basic AllocaManager feature test. Eliminate user variable cupcake in favor of
+; user variable muffin, and combine all the vararg buffers. And align the stack
+; pointer.
+
+; ModuleID = 'test/CodeGen/JS/allocamanager.ll'
+target datalayout = "e-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-p:32:32:32-v128:32:128-n32-S128"
+target triple = "asmjs-unknown-emscripten"
+
+%struct._IO_FILE = type opaque
+
+@stderr = external constant [4 x i8], align 4
+@.str = private unnamed_addr constant [26 x i8] c"hello from %s; argc is %d\00", align 1
+@.str1 = private unnamed_addr constant [33 x i8] c"message from the program: \22%s\22!\0A\00", align 1
+@.str2 = private unnamed_addr constant [38 x i8] c"with argc %d, I, %s, must say goodbye\00", align 1
+@.str3 = private unnamed_addr constant [43 x i8] c"another message from the program: \22%s\22...\0A\00", align 1
+
+; CHECK: function _foo($argc,$argv) {
+; CHECK-NOT: cupcake
+; CHECK: STACKTOP = STACKTOP + 128|0;
+; CHECK-NEXT: vararg_buffer0 =
+; CHECK-NEXT: $muffin =
+; CHECK-NOT: cupcake
+; CHECK: }
+
+; Function Attrs: nounwind
+define void @foo(i32 %argc, i8** %argv) #0 {
+entry:
+  %vararg_buffer0 = alloca <{ i8* }>, align 8
+  %vararg_lifetime_bitcast10 = bitcast <{ i8* }>* %vararg_buffer0 to i8*
+  %vararg_buffer5 = alloca <{ i32, i8* }>, align 8
+  %vararg_lifetime_bitcast6 = bitcast <{ i32, i8* }>* %vararg_buffer5 to i8*
+  %vararg_buffer2 = alloca <{ i8* }>, align 8
+  %vararg_lifetime_bitcast3 = bitcast <{ i8* }>* %vararg_buffer2 to i8*
+  %vararg_buffer1 = alloca <{ i8*, i32 }>, align 8
+  %vararg_lifetime_bitcast = bitcast <{ i8*, i32 }>* %vararg_buffer1 to i8*
+  %muffin = alloca [117 x i8], align 1
+  %cupcake = alloca [119 x i8], align 1
+  %tmp = getelementptr [117 x i8]* %muffin, i32 0, i32 0
+  call void @llvm.lifetime.start(i64 117, i8* %tmp) #0
+  %tmp1 = load i8** %argv, align 4
+  call void @llvm.lifetime.start(i64 8, i8* %vararg_lifetime_bitcast)
+  %vararg_ptr = getelementptr <{ i8*, i32 }>* %vararg_buffer1, i32 0, i32 0
+  store i8* %tmp1, i8** %vararg_ptr, align 4
+  %vararg_ptr1 = getelementptr <{ i8*, i32 }>* %vararg_buffer1, i32 0, i32 1
+  store i32 %argc, i32* %vararg_ptr1, align 4
+  %call = call i32 bitcast (i32 (i8*, i8*, i8*)* @sprintf to i32 (i8*, i8*, <{ i8*, i32 }>*)*)(i8* %tmp, i8* getelementptr inbounds ([26 x i8]* @.str, i32 0, i32 0), <{ i8*, i32 }>* %vararg_buffer1) #0
+  call void @llvm.lifetime.end(i64 8, i8* %vararg_lifetime_bitcast)
+  %tmp2 = load %struct._IO_FILE** bitcast ([4 x i8]* @stderr to %struct._IO_FILE**), align 4
+  call void @llvm.lifetime.start(i64 4, i8* %vararg_lifetime_bitcast3)
+  %vararg_ptr4 = getelementptr <{ i8* }>* %vararg_buffer2, i32 0, i32 0
+  store i8* %tmp, i8** %vararg_ptr4, align 4
+  %call2 = call i32 bitcast (i32 (%struct._IO_FILE*, i8*, i8*)* @fprintf to i32 (%struct._IO_FILE*, i8*, <{ i8* }>*)*)(%struct._IO_FILE* %tmp2, i8* getelementptr inbounds ([33 x i8]* @.str1, i32 0, i32 0), <{ i8* }>* %vararg_buffer2) #0
+  call void @llvm.lifetime.end(i64 4, i8* %vararg_lifetime_bitcast3)
+  call void @llvm.lifetime.end(i64 117, i8* %tmp) #0
+  %tmp3 = getelementptr [119 x i8]* %cupcake, i32 0, i32 0
+  call void @llvm.lifetime.start(i64 119, i8* %tmp3) #0
+  %tmp4 = load i8** %argv, align 4
+  call void @llvm.lifetime.start(i64 8, i8* %vararg_lifetime_bitcast6)
+  %vararg_ptr7 = getelementptr <{ i32, i8* }>* %vararg_buffer5, i32 0, i32 0
+  store i32 %argc, i32* %vararg_ptr7, align 4
+  %vararg_ptr8 = getelementptr <{ i32, i8* }>* %vararg_buffer5, i32 0, i32 1
+  store i8* %tmp4, i8** %vararg_ptr8, align 4
+  %call5 = call i32 bitcast (i32 (i8*, i8*, i8*)* @sprintf to i32 (i8*, i8*, <{ i32, i8* }>*)*)(i8* %tmp3, i8* getelementptr inbounds ([38 x i8]* @.str2, i32 0, i32 0), <{ i32, i8* }>* %vararg_buffer5) #0
+  call void @llvm.lifetime.end(i64 8, i8* %vararg_lifetime_bitcast6)
+  call void @llvm.lifetime.start(i64 4, i8* %vararg_lifetime_bitcast10)
+  %vararg_ptr11 = getelementptr <{ i8* }>* %vararg_buffer0, i32 0, i32 0
+  store i8* %tmp3, i8** %vararg_ptr11, align 4
+  %call7 = call i32 bitcast (i32 (%struct._IO_FILE*, i8*, i8*)* @fprintf to i32 (%struct._IO_FILE*, i8*, <{ i8* }>*)*)(%struct._IO_FILE* %tmp2, i8* getelementptr inbounds ([43 x i8]* @.str3, i32 0, i32 0), <{ i8* }>* %vararg_buffer0) #0
+  call void @llvm.lifetime.end(i64 4, i8* %vararg_lifetime_bitcast10)
+  call void @llvm.lifetime.end(i64 119, i8* %tmp3) #0
+  ret void
+}
+
+; CHECK: function _bar($argc,$argv) {
+; CHECK-NOT: cupcake
+; CHECK: STACKTOP = STACKTOP + 128|0;
+; CHECK-NEXT: vararg_buffer0 =
+; CHECK-NEXT: $muffin =
+; CHECK-NOT: cupcake
+; CHECK: }
+
+; Function Attrs: nounwind
+define void @bar(i32 %argc, i8** %argv) #0 {
+entry:
+  %vararg_buffer0 = alloca <{ i8* }>, align 8
+  %vararg_lifetime_bitcast10 = bitcast <{ i8* }>* %vararg_buffer0 to i8*
+  %vararg_buffer5 = alloca <{ i32, i8* }>, align 8
+  %vararg_lifetime_bitcast6 = bitcast <{ i32, i8* }>* %vararg_buffer5 to i8*
+  %vararg_buffer2 = alloca <{ i8* }>, align 8
+  %vararg_lifetime_bitcast3 = bitcast <{ i8* }>* %vararg_buffer2 to i8*
+  %vararg_buffer1 = alloca <{ i8*, i32 }>, align 8
+  %vararg_lifetime_bitcast = bitcast <{ i8*, i32 }>* %vararg_buffer1 to i8*
+  %muffin = alloca [117 x i8], align 1
+  %cupcake = alloca [119 x i8], align 1
+  %tmp = getelementptr [117 x i8]* %muffin, i32 0, i32 0
+  call void @llvm.lifetime.start(i64 117, i8* %tmp) #0
+  %cmp = icmp eq i32 %argc, 39
+  br i1 %cmp, label %if.end.thread, label %if.end
+
+if.end.thread:                                    ; preds = %entry
+  call void @llvm.lifetime.end(i64 117, i8* %tmp) #0
+  %tmp1 = getelementptr [119 x i8]* %cupcake, i32 0, i32 0
+  call void @llvm.lifetime.start(i64 119, i8* %tmp1) #0
+  %.pre = load %struct._IO_FILE** bitcast ([4 x i8]* @stderr to %struct._IO_FILE**), align 4
+  br label %if.then4
+
+if.end:                                           ; preds = %entry
+  %tmp2 = load i8** %argv, align 4
+  call void @llvm.lifetime.start(i64 8, i8* %vararg_lifetime_bitcast)
+  %vararg_ptr = getelementptr <{ i8*, i32 }>* %vararg_buffer1, i32 0, i32 0
+  store i8* %tmp2, i8** %vararg_ptr, align 4
+  %vararg_ptr1 = getelementptr <{ i8*, i32 }>* %vararg_buffer1, i32 0, i32 1
+  store i32 %argc, i32* %vararg_ptr1, align 4
+  %call = call i32 bitcast (i32 (i8*, i8*, i8*)* @sprintf to i32 (i8*, i8*, <{ i8*, i32 }>*)*)(i8* %tmp, i8* getelementptr inbounds ([26 x i8]* @.str, i32 0, i32 0), <{ i8*, i32 }>* %vararg_buffer1) #0
+  call void @llvm.lifetime.end(i64 8, i8* %vararg_lifetime_bitcast)
+  %tmp3 = load %struct._IO_FILE** bitcast ([4 x i8]* @stderr to %struct._IO_FILE**), align 4
+  call void @llvm.lifetime.start(i64 4, i8* %vararg_lifetime_bitcast3)
+  %vararg_ptr4 = getelementptr <{ i8* }>* %vararg_buffer2, i32 0, i32 0
+  store i8* %tmp, i8** %vararg_ptr4, align 4
+  %call2 = call i32 bitcast (i32 (%struct._IO_FILE*, i8*, i8*)* @fprintf to i32 (%struct._IO_FILE*, i8*, <{ i8* }>*)*)(%struct._IO_FILE* %tmp3, i8* getelementptr inbounds ([33 x i8]* @.str1, i32 0, i32 0), <{ i8* }>* %vararg_buffer2) #0
+  call void @llvm.lifetime.end(i64 4, i8* %vararg_lifetime_bitcast3)
+  call void @llvm.lifetime.end(i64 117, i8* %tmp) #0
+  %tmp4 = getelementptr [119 x i8]* %cupcake, i32 0, i32 0
+  call void @llvm.lifetime.start(i64 119, i8* %tmp4) #0
+  %cmp3 = icmp eq i32 %argc, 45
+  br i1 %cmp3, label %if.end10, label %if.then4
+
+if.then4:                                         ; preds = %if.end, %if.end.thread
+  %tmp5 = phi %struct._IO_FILE* [ %.pre, %if.end.thread ], [ %tmp3, %if.end ]
+  %tmp6 = phi i8* [ %tmp1, %if.end.thread ], [ %tmp4, %if.end ]
+  %tmp7 = load i8** %argv, align 4
+  call void @llvm.lifetime.start(i64 8, i8* %vararg_lifetime_bitcast6)
+  %vararg_ptr7 = getelementptr <{ i32, i8* }>* %vararg_buffer5, i32 0, i32 0
+  store i32 %argc, i32* %vararg_ptr7, align 4
+  %vararg_ptr8 = getelementptr <{ i32, i8* }>* %vararg_buffer5, i32 0, i32 1
+  store i8* %tmp7, i8** %vararg_ptr8, align 4
+  %call7 = call i32 bitcast (i32 (i8*, i8*, i8*)* @sprintf to i32 (i8*, i8*, <{ i32, i8* }>*)*)(i8* %tmp6, i8* getelementptr inbounds ([38 x i8]* @.str2, i32 0, i32 0), <{ i32, i8* }>* %vararg_buffer5) #0
+  call void @llvm.lifetime.end(i64 8, i8* %vararg_lifetime_bitcast6)
+  call void @llvm.lifetime.start(i64 4, i8* %vararg_lifetime_bitcast10)
+  %vararg_ptr11 = getelementptr <{ i8* }>* %vararg_buffer0, i32 0, i32 0
+  store i8* %tmp6, i8** %vararg_ptr11, align 4
+  %call9 = call i32 bitcast (i32 (%struct._IO_FILE*, i8*, i8*)* @fprintf to i32 (%struct._IO_FILE*, i8*, <{ i8* }>*)*)(%struct._IO_FILE* %tmp5, i8* getelementptr inbounds ([43 x i8]* @.str3, i32 0, i32 0), <{ i8* }>* %vararg_buffer0) #0
+  call void @llvm.lifetime.end(i64 4, i8* %vararg_lifetime_bitcast10)
+  br label %if.end10
+
+if.end10:                                         ; preds = %if.then4, %if.end
+  %tmp8 = phi i8* [ %tmp4, %if.end ], [ %tmp6, %if.then4 ]
+  call void @llvm.lifetime.end(i64 119, i8* %tmp8) #0
+  ret void
+}
+
+; Function Attrs: nounwind
+declare i32 @sprintf(i8*, i8*, i8*) #0
+
+; Function Attrs: nounwind
+declare i32 @fprintf(%struct._IO_FILE*, i8*, i8*) #0
+
+; Function Attrs: nounwind
+declare void @llvm.lifetime.start(i64, i8* nocapture) #0
+
+; Function Attrs: nounwind
+declare void @llvm.lifetime.end(i64, i8* nocapture) #0
+
+attributes #0 = { nounwind }