Merge pull request #28 from sunfishcode/incoming

The alloca coloring patch

1 files changed, 74 insertions, 69 deletions

diff --git a/lib/Target/JSBackend/JSBackend.cpp b/lib/Target/JSBackend/JSBackend.cpp
index f1a6aa59ee..92d562a1df 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;
@@ -140,13 +139,16 @@ namespace {
 
     bool UsesSIMD;
     int InvokeState; // cycles between 0, 1 after preInvoke, 2 after call, 0 again after postInvoke. hackish, no argument there.
+    CodeGenOpt::Level OptLevel;
     DataLayout *DL;
 
     #include "CallHandlers.h"
 
   public:
     static char ID;
-    explicit JSWriter(formatted_raw_ostream &o) : ModulePass(ID), Out(o), UniqueNum(0), UsesSIMD(false), InvokeState(0) {}
+    JSWriter(formatted_raw_ostream &o, CodeGenOpt::Level OptLevel)
+      : ModulePass(ID), Out(o), UniqueNum(0), UsesSIMD(false), InvokeState(0),
+        OptLevel(OptLevel) {}
 
     virtual const char *getPassName() const { return "JavaScript backend"; }
 
@@ -431,6 +433,10 @@ static inline char halfCharToHex(unsigned char half) {
 }
 
 static inline void sanitizeGlobal(std::string& str) {
+  // Global names are prefixed with "_" to prevent them from colliding with
+  // names of things in normal JS.
+  str = "_" + str;
+
   // functions and globals should already be in C-style format,
   // in addition to . for llvm intrinsics and possibly $ and so forth.
   // There is a risk of collisions here, we just lower all these
@@ -444,6 +450,10 @@ static inline void sanitizeGlobal(std::string& str) {
 }
 
 static inline void sanitizeLocal(std::string& str) {
+  // Local names are prefixed with "$" to prevent them from colliding with
+  // global names.
+  str = "$" + str;
+
   // We need to convert every string that is not a valid JS identifier into
   // a valid one, without collisions - we cannot turn "x.a" into "x_a" while
   // also leaving "x_a" as is, for example.
@@ -565,18 +575,29 @@ 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()) {
-    if (isa<Function>(val) || isa<Constant>(val)) {
-      name = std::string("_") + val->getName().str();
-      sanitizeGlobal(name);
-    } else {
-      name = std::string("$") + val->getName().str();
-      sanitizeLocal(name);
-    }
+    name = val->getName().str();
+  } else {
+    name = utostr(UniqueNum++);
+  }
+
+  if (isa<Constant>(val)) {
+    sanitizeGlobal(name);
   } else {
-    name = "u$" + utostr(UniqueNum++);
+    sanitizeLocal(name);
   }
+
   return ValueNames[val] = name;
 }
 
@@ -1368,22 +1389,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);
@@ -1775,8 +1805,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
@@ -1815,59 +1845,24 @@ void JSWriter::processConstants() {
 void JSWriter::printFunction(const Function *F) {
   ValueNames.clear();
 
-  // Ensure all arguments and locals are named (we assume used values need names, which might be false if the optimizer did not run)
-  unsigned Next = 1;
-  for (Function::const_arg_iterator AI = F->arg_begin(), AE = F->arg_end();
-       AI != AE; ++AI) {
-    if (!AI->hasName() && !AI->use_empty()) {
-      ValueNames[AI] = "$" + utostr(Next++);
-    }
-  }
-  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 (!II->hasName() && !II->use_empty()) {
-        ValueNames[II] = "$" + utostr(Next++);
-      }
-    }
-  }
-
   // Prepare and analyze function
 
   UsedVars.clear();
   UniqueNum = 0;
-  calculateNativizedVars(F);
 
-  StackAllocs.clear();
-  TotalStackAllocs = 0;
+  // When optimizing, the regular optimizer (mem2reg, SROA, GVN, and others)
+  // will have already taken all the opportunities for nativization.
+  if (OptLevel == CodeGenOpt::None)
+    calculateNativizedVars(F);
 
-  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;
-  }
+  // Do alloca coloring at -O1 and higher.
+  Allocas.analyze(*F, *DL, OptLevel != CodeGenOpt::None);
 
   // Emit the function
 
   std::string Name = F->getName();
   sanitizeGlobal(Name);
-  Out << "function _" << Name << "(";
+  Out << "function " << Name << "(";
   for (Function::const_arg_iterator AI = F->arg_begin(), AE = F->arg_end();
        AI != AE; ++AI) {
     if (AI != F->arg_begin()) Out << ",";
@@ -1884,6 +1879,8 @@ void JSWriter::printFunction(const Function *F) {
   printFunctionBody(F);
   Out << "}";
   nl(Out);
+
+  Allocas.clear();
 }
 
 void JSWriter::printModuleBody() {
@@ -2346,8 +2343,16 @@ bool JSTargetMachine::addPassesToEmitFile(PassManagerBase &PM,
   assert(FileType == TargetMachine::CGFT_AssemblyFile);
 
   PM.add(createExpandI64Pass());
-  PM.add(createSimplifyAllocasPass());
-  PM.add(new JSWriter(o));
+
+  CodeGenOpt::Level OptLevel = getOptLevel();
+
+  // When optimizing, there shouldn't be any opportunities for SimplifyAllocas
+  // because the regular optimizer should have taken them all (GVN, and possibly
+  // also SROA).
+  if (OptLevel == CodeGenOpt::None)
+    PM.add(createSimplifyAllocasPass());
+
+  PM.add(new JSWriter(o, OptLevel));
 
   return false;
 }