Combine allocas

src/IceCfg.cpp

 //===- subzero/src/IceCfg.cpp - Control flow graph implementation ---------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 183 matching lines @@
       addCallToProfileSummary();
     }
     dump("Profiled CFG");
   }
 
   // Create the Hi and Lo variables where a split was needed
   for (Variable *Var : Variables)
     if (auto *Var64On32 = llvm::dyn_cast<Variable64On32>(Var))
       Var64On32->initHiLo(this);
 
-  processAllocas();
-
   // The set of translation passes and their order are determined by the
   // target.
   getTarget()->translate();
 
   dump("Final output");
   if (getFocusedTiming())
     getContext()->dumpTimers();
 }
 
 void Cfg::computeInOutEdges() {
@@ skipping 228 matching lines @@
   swapNodes(Shuffled);
 
   dump("After basic block shuffling");
 }
 
 void Cfg::doArgLowering() {
   TimerMarker T(TimerStack::TT_doArgLowering, this);
   getTarget()->lowerArguments();
 }
 
-void Cfg::sortAllocas(CfgVector<Inst *> &Allocas, InstList &Insts,
-                      bool IsKnownFrameOffset) {
+void Cfg::sortAndCombineAllocas(CfgVector<Inst *> &Allocas,
+                                uint32_t CombinedAlignment, InstList &Insts,
+                                AllocaBaseVariableType BaseVariableType) {
   if (Allocas.empty())
     return;
-  // Sort by decreasing alignment.  This does not really matter at the moment,
-  // but will allow compacting stack allocation when we fuse to one alloca.
+  // Sort by decreasing alignment.
   std::sort(Allocas.begin(), Allocas.end(), [](Inst *I1, Inst *I2) {
     auto *A1 = llvm::dyn_cast<InstAlloca>(I1);
     auto *A2 = llvm::dyn_cast<InstAlloca>(I2);
     return A1->getAlignInBytes() > A2->getAlignInBytes();
   });
+  // Process the allocas in order of decreasing stack alignment.  This allows
+  // us to pack less-aligned pieces after more-aligned ones, resulting in less
+  // stack growth.  It also allows there to be at most one stack alignment "and"
+  // instruction for a whole list of allocas.
+  uint32_t CurrentOffset = 0;
+  CfgVector<int32_t> Offsets;
   for (Inst *Instr : Allocas) {
     auto *Alloca = llvm::cast<InstAlloca>(Instr);
-    // Move the alloca to its sorted position.
-    InstAlloca *NewAlloca =
-        InstAlloca::create(this, Alloca->getSizeInBytes(),
-                           Alloca->getAlignInBytes(), Alloca->getDest());
-    if (IsKnownFrameOffset)
-      NewAlloca->setKnownFrameOffset();
-    Insts.push_front(NewAlloca);
+    // Adjust the size of the allocation up to the next multiple of the
+    // object's alignment.
+    uint32_t Alignment = std::max(Alloca->getAlignInBytes(), 1u);
+    auto *ConstSize =
+        llvm::dyn_cast<ConstantInteger32>(Alloca->getSizeInBytes());
+    uint32_t Size = Utils::applyAlignment(ConstSize->getValue(), Alignment);
+    if (BaseVariableType == BVT_FramePointer) {
+      // Addressing is relative to the frame pointer.  Subtract the offset after
+      // adding the size of the alloca, because it grows downwards from the
+      // frame pointer.
+      Offsets.push_back(-(CurrentOffset + Size));
+    } else {
+      // Addressing is relative to the stack pointer or to a user pointer.  Add
+      // the offset before adding the size of the object, because it grows
+      // upwards from the stack pointer.
+      Offsets.push_back(CurrentOffset);
+    }
+    // Update the running offset of the fused alloca region.
+    CurrentOffset += Size;
+  }
+  // Round the offset up to the alignment granularity to use as the size.
+  uint32_t TotalSize = Utils::applyAlignment(CurrentOffset, CombinedAlignment);
+  // Ensure every alloca was assigned an offset.
+  assert(Allocas.size() == Offsets.size());
+  Variable *BaseVariable = makeVariable(IceType_i32);
+  Variable *AllocaDest = BaseVariable;
+  // Emit one addition for each alloca after the first.
+  for (size_t i = 0; i < Allocas.size(); ++i) {
+    auto *Alloca = llvm::cast<InstAlloca>(Allocas[i]);
+    switch (BaseVariableType) {
+    case BVT_FramePointer:
+    case BVT_UserPointer: {
+      // Emit a new addition operation to replace the alloca.
+      Operand *AllocaOffset = Ctx->getConstantInt32(Offsets[i]);
+      InstArithmetic *Add =
+          InstArithmetic::create(this, InstArithmetic::Add, Alloca->getDest(),
+                                 BaseVariable, AllocaOffset);
+      Insts.push_front(Add);
+    } break;
+    case BVT_StackPointer: {
+      // Emit a fake definition of the rematerializable variable.
+      Variable *Dest = Alloca->getDest();
+      InstFakeDef *Def = InstFakeDef::create(this, Dest);
+      Dest->setRematerializable(getTarget()->getStackReg(), Offsets[i]);
+      Insts.push_front(Def);
+    } break;
+    }
     Alloca->setDeleted();
   }
+  Operand *AllocaSize = Ctx->getConstantInt32(TotalSize);
+  switch (BaseVariableType) {
+  case BVT_FramePointer: {
+    // Adjust the return of the alloca to the top of the returned region.
+    AllocaDest = makeVariable(IceType_i32);
+    InstArithmetic *Add = InstArithmetic::create(
+        this, InstArithmetic::Add, BaseVariable, AllocaDest, AllocaSize);
+    Insts.push_front(Add);
+  } break;
+  case BVT_StackPointer: {
+    // Emit a fake use to keep the Alloca live.
+    InstFakeUse *Use = InstFakeUse::create(this, AllocaDest);
+    Insts.push_front(Use);
+  } break;
+  case BVT_UserPointer:
+    break;
+  }
+  // And insert the fused alloca.
+  InstAlloca *CombinedAlloca =
+      InstAlloca::create(this, AllocaSize, CombinedAlignment, AllocaDest);
+  CombinedAlloca->setKnownFrameOffset();
+  Insts.push_front(CombinedAlloca);
 }
 
-void Cfg::processAllocas() {
+void Cfg::processAllocas(bool SortAndCombine) {
   const uint32_t StackAlignment = getTarget()->getStackAlignment();
   CfgNode *EntryNode = getEntryNode();
+  // LLVM enforces power of 2 alignment.
+  assert(llvm::isPowerOf2_32(StackAlignment));
+  // Determine if there are large alignment allocations in the entry block or
+  // dynamic allocations (variable size in the entry block).
+  bool HasLargeAlignment = false;
+  bool HasDynamicAllocation = false;
+  for (Inst &Instr : EntryNode->getInsts()) {
+    if (auto *Alloca = llvm::dyn_cast<InstAlloca>(&Instr)) {
+      uint32_t AlignmentParam = Alloca->getAlignInBytes();
+      if (AlignmentParam > StackAlignment)
+        HasLargeAlignment = true;
+      if (llvm::isa<Constant>(Alloca->getSizeInBytes()))
+        Alloca->setKnownFrameOffset();
+      else
+        HasDynamicAllocation = true;
+    }
+  }
+  // Don't do the heavyweight sorting and layout for low optimization levels.
+  if (!SortAndCombine)
+    return;
+  // Any alloca outside the entry block is a dynamic allocation.
+  for (CfgNode *Node : Nodes) {
+    if (Node == EntryNode)
+      continue;
+    for (Inst &Instr : Node->getInsts()) {
+      if (llvm::isa<InstAlloca>(&Instr)) {
+        // Allocations outside the entry block require a frame pointer.
+        HasDynamicAllocation = true;
+        break;
+      }
+    }
+    if (HasDynamicAllocation)
+      break;
+  }
+  // Mark the target as requiring a frame pointer.
+  if (HasLargeAlignment || HasDynamicAllocation)
+    getTarget()->setHasFramePointer();
+  // Collect the Allocas into the two vectors.
   // Allocas in the entry block that have constant size and alignment less
   // than or equal to the function's stack alignment.
   CfgVector<Inst *> FixedAllocas;
   // Allocas in the entry block that have constant size and alignment greater
   // than the function's stack alignment.
   CfgVector<Inst *> AlignedAllocas;
-  // LLVM enforces power of 2 alignment.
-  assert(llvm::isPowerOf2_32(StackAlignment));
-  // Collect the Allocas into the two vectors.
-  bool RequiresFramePointer = false;
+  // Maximum alignment used for the dynamic/aligned allocas.
+  uint32_t MaxAlignment = StackAlignment;
   for (Inst &Instr : EntryNode->getInsts()) {
     if (auto *Alloca = llvm::dyn_cast<InstAlloca>(&Instr)) {
-      if (!llvm::isa<Constant>(Alloca->getSizeInBytes())) {
-        // Variable-sized allocations require a frame pointer.
-        RequiresFramePointer = true;
+      if (!llvm::isa<Constant>(Alloca->getSizeInBytes()))
         continue;
-      }
       uint32_t AlignmentParam = Alloca->getAlignInBytes();
       // For default align=0, set it to the real value 1, to avoid any
       // bit-manipulation problems below.
       AlignmentParam = std::max(AlignmentParam, 1u);
       assert(llvm::isPowerOf2_32(AlignmentParam));
-      if (AlignmentParam > StackAlignment) {
-        // Allocations aligned more than the stack require a frame pointer.
-        RequiresFramePointer = true;
+      if (HasDynamicAllocation && AlignmentParam > StackAlignment) {
+        // If we have both dynamic allocations and large stack alignments,
+        // high-alignment allocations are pulled out with their own base.
         AlignedAllocas.push_back(Alloca);
-      } else
+      } else {
         FixedAllocas.push_back(Alloca);
+      }
+      MaxAlignment = std::max(AlignmentParam, MaxAlignment);
     }
   }
-  // Look for alloca instructions in other blocks
-  for (CfgNode *Node : Nodes) {
-    if (Node == EntryNode)
-      continue;
-    for (Inst &Instr : Node->getInsts()) {
-      if (llvm::isa<InstAlloca>(&Instr)) {
-        // Allocations outside the entry block require a frame pointer.
-        RequiresFramePointer = true;
-        break;
-      }
-    }
-    if (RequiresFramePointer)
-      break;
-  }
-  // Mark the target as requiring a frame pointer.
-  if (RequiresFramePointer)
-    getTarget()->setHasFramePointer();
   // Add instructions to the head of the entry block in reverse order.
   InstList &Insts = getEntryNode()->getInsts();
-  // Fixed, large alignment alloca addresses do not have known offset.
-  sortAllocas(AlignedAllocas, Insts, false);
-  // Fixed, small alignment alloca addresses have known offset.
-  sortAllocas(FixedAllocas, Insts, true);
+  if (HasDynamicAllocation && HasLargeAlignment) {
+    // We are using a frame pointer, but fixed large-alignment alloca addresses,
+    // do not have a known offset from either the stack or frame pointer.
+    // They grow up from a user pointer from an alloca.
+    sortAndCombineAllocas(AlignedAllocas, MaxAlignment, Insts, BVT_UserPointer);
+  }
+  // Otherwise, fixed size allocas are always addressed relative to the stack
+  // unless there are dynamic allocas.
+  // TODO(sehr): re-enable frame pointer and decrementing addressing.
+  AllocaBaseVariableType BasePointerType =
+      (HasDynamicAllocation ? BVT_UserPointer : BVT_StackPointer);
+  sortAndCombineAllocas(FixedAllocas, MaxAlignment, Insts, BasePointerType);
 }
 
 void Cfg::doAddressOpt() {
   TimerMarker T(TimerStack::TT_doAddressOpt, this);
   for (CfgNode *Node : Nodes)
     Node->doAddressOpt();
 }
 
 void Cfg::doNopInsertion() {
   if (!Ctx->getFlags().shouldDoNopInsertion())
@@ skipping 351 matching lines @@
     }
   }
   // Print each basic block
   for (CfgNode *Node : Nodes)
     Node->dump(this);
   if (isVerbose(IceV_Instructions))
     Str << "}\n";
 }
 
 } // end of namespace Ice