[Subzero][MIPS32] Implements lowering of alloca instruction

src/IceTargetLoweringMIPS32.cpp

 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// \brief Implements the TargetLoweringMIPS32 class, which consists almost
@@ skipping 145 matching lines @@
   TypeToRegisterSet[IceType_v4f32] = VectorRegisters;
 
   for (size_t i = 0; i < llvm::array_lengthof(TypeToRegisterSet); ++i)
     TypeToRegisterSetUnfiltered[i] = TypeToRegisterSet[i];
 
   filterTypeToRegisterSet(Ctx, RegMIPS32::Reg_NUM, TypeToRegisterSet,
                           llvm::array_lengthof(TypeToRegisterSet),
                           RegMIPS32::getRegName, getRegClassName);
 }
 
+void TargetMIPS32::unsetIfNonLeafFunc() {

[Jim Stichnoth, 2016/06/15 13:41:19]

I think that the ARM target folds this computation into the instruction lowering
pass, instead of making a separate pass.  My experience has been that making a
pass over each instruction, like this one, costs about 1% of the total
translation time.  That's not much, but they can add up, so you might consider
doing similar to ARM after the call lowering code stabilizes.

[Jim Stichnoth, 2016/06/15 13:43:19]

Actually, it just occurred to me that statistically, this pass is much cheaper
than a full pass over instructions because of the early-exit.

[sagar.thakur, 2016/06/16 08:05:54]

This pass is needed because findMaxStackOutArgsSize needs to know whether a
function is a leaf function or a non-leaf function to compute the
MaxOutArgsSizeBytes value. In case of non-leaf function, the mips o32 abi
specifies that a caller must allocate at least 16 bytes of memory as argument
build area which will be used by callee even if arguments passed occupy less
than 16 bytes. Whereas if a function is a leaf function then there's no need to
allocate this memory.

+  for (CfgNode *Node : Func->getNodes()) {
+    for (Inst &Instr : Node->getInsts()) {
+      if (llvm::isa<InstCall>(&Instr)) {
+        // Unset MaybeLeafFunc if call instruction exists.
+        MaybeLeafFunc = false;
+        break;

[Jim Stichnoth, 2016/06/15 13:41:19]

Can you just early-return here, and avoid the break statements?

[sagar.thakur, 2016/06/16 08:05:54]

Done.

+      }
+    }
+    if (!MaybeLeafFunc)
+      break;
+  }
+}
+
+uint32_t TargetMIPS32::getStackAlignment() const {
+  return MIPS32_STACK_ALIGNMENT_BYTES;
+}
+
 void TargetMIPS32::findMaxStackOutArgsSize() {
   // MinNeededOutArgsBytes should be updated if the Target ever creates a
   // high-level InstCall that requires more stack bytes.
-  constexpr size_t MinNeededOutArgsBytes = 16;
+  size_t MinNeededOutArgsBytes = 0;
+  if (!MaybeLeafFunc)
+    MinNeededOutArgsBytes = MIPS32_MAX_GPR_ARG * 4;
   MaxOutArgsSizeBytes = MinNeededOutArgsBytes;
   for (CfgNode *Node : Func->getNodes()) {
     Context.init(Node);
     while (!Context.atEnd()) {
       PostIncrLoweringContext PostIncrement(Context);
       Inst *CurInstr = iteratorToInst(Context.getCur());
       if (auto *Call = llvm::dyn_cast<InstCall>(CurInstr)) {
         SizeT OutArgsSizeBytes = getCallStackArgumentsSizeBytes(Call);
         MaxOutArgsSizeBytes = std::max(MaxOutArgsSizeBytes, OutArgsSizeBytes);
       }
     }
   }
 }
 
 void TargetMIPS32::translateO2() {
   TimerMarker T(TimerStack::TT_O2, Func);
 
   // TODO(stichnot): share passes with X86?
   // https://code.google.com/p/nativeclient/issues/detail?id=4094
   genTargetHelperCalls();
 
+  unsetIfNonLeafFunc();
+
   findMaxStackOutArgsSize();
 
   // Merge Alloca instructions, and lay out the stack.
-  static constexpr bool SortAndCombineAllocas = false;
+  static constexpr bool SortAndCombineAllocas = true;
   Func->processAllocas(SortAndCombineAllocas);
   Func->dump("After Alloca processing");
 
   if (!getFlags().getEnablePhiEdgeSplit()) {
     // Lower Phi instructions.
     Func->placePhiLoads();
     if (Func->hasError())
       return;
     Func->placePhiStores();
     if (Func->hasError())
@@ skipping 79 matching lines @@
     Func->doNopInsertion();
   }
 }
 
 void TargetMIPS32::translateOm1() {
   TimerMarker T(TimerStack::TT_Om1, Func);
 
   // TODO: share passes with X86?
   genTargetHelperCalls();
 
+  unsetIfNonLeafFunc();
+
   findMaxStackOutArgsSize();
 
   // Do not merge Alloca instructions, and lay out the stack.
   static constexpr bool SortAndCombineAllocas = false;
   Func->processAllocas(SortAndCombineAllocas);
   Func->dump("After Alloca processing");
 
   Func->placePhiLoads();
   if (Func->hasError())
     return;
@@ skipping 130 matching lines @@
   // transformation.
   if (auto *Mem = llvm::dyn_cast<OperandMIPS32Mem>(Operand)) {
     return Mem;
   }
 
   // If we didn't do address mode optimization, then we only have a base/offset
   // to work with. MIPS always requires a base register, so just use that to
   // hold the operand.
   auto *Base = llvm::cast<Variable>(legalize(Operand, Legal_Reg));
   return OperandMIPS32Mem::create(
-      Func, Ty, Base,
-      llvm::cast<ConstantInteger32>(Ctx->getConstantZero(IceType_i32)));
+      Func, Ty, Base, llvm::cast<ConstantInteger32>(
+                          Ctx->getConstantInt32(Base->getStackOffset())));
 }
 
 void TargetMIPS32::emitVariable(const Variable *Var) const {
   if (!BuildDefs::dump())
     return;
   Ostream &Str = Ctx->getStrEmit();
   const Type FrameSPTy = IceType_i32;
   if (Var->hasReg()) {
     Str << '$' << getRegName(Var->getRegNum(), Var->getType());
     return;
@@ skipping 345 matching lines @@
   assert(LocalsSlotsAlignmentBytes <= SpillAreaAlignmentBytes);
   uint32_t SpillAreaPaddingBytes = 0;
   uint32_t LocalsSlotsPaddingBytes = 0;
   alignStackSpillAreas(PreservedRegsSizeBytes, SpillAreaAlignmentBytes,
                        GlobalsSize, LocalsSlotsAlignmentBytes,
                        &SpillAreaPaddingBytes, &LocalsSlotsPaddingBytes);
   SpillAreaSizeBytes += SpillAreaPaddingBytes + LocalsSlotsPaddingBytes;
   uint32_t GlobalsAndSubsequentPaddingSize =
       GlobalsSize + LocalsSlotsPaddingBytes;
 
-  if (MaybeLeafFunc)
-    MaxOutArgsSizeBytes = 0;
-
   // Adds the out args space to the stack, and align SP if necessary.
-  uint32_t TotalStackSizeBytes = PreservedRegsSizeBytes + SpillAreaSizeBytes;
-
-  // TODO(sagar.thakur): Combine fixed alloca and maximum out argument size with
-  // TotalStackSizeBytes once lowerAlloca is implemented and leaf function
-  // information is generated by lowerCall.
+  uint32_t TotalStackSizeBytes = PreservedRegsSizeBytes + SpillAreaSizeBytes +
+                                 FixedAllocaSizeBytes + MaxOutArgsSizeBytes;
 
   // Generate "addiu sp, sp, -TotalStackSizeBytes"
   if (TotalStackSizeBytes) {
     // Use the scratch register if needed to legalize the immediate.
     Variable *SP = getPhysicalRegister(RegMIPS32::Reg_SP);
     _addiu(SP, SP, -(TotalStackSizeBytes));
   }
 
   Ctx->statsUpdateFrameBytes(TotalStackSizeBytes);
 
@@ skipping 17 matching lines @@
     Variable *SP = getPhysicalRegister(RegMIPS32::Reg_SP);
     _mov(FP, SP);
     // Keep FP live for late-stage liveness analysis (e.g. asm-verbose mode).
     Context.insert<InstFakeUse>(FP);
   }
 
   // Fill in stack offsets for stack args, and copy args into registers for
   // those that were register-allocated. Args are pushed right to left, so
   // Arg[0] is closest to the stack/frame pointer.
   const VarList &Args = Func->getArgs();
-  size_t InArgsSizeBytes = 0;
+  size_t InArgsSizeBytes = MIPS32_MAX_GPR_ARG * 4;
   TargetMIPS32::CallingConv CC;
   uint32_t ArgNo = 0;
 
   for (Variable *Arg : Args) {
     RegNumT DummyReg;
     const Type Ty = Arg->getType();
     // Skip arguments passed in registers.
     if (CC.argInReg(Ty, ArgNo, &DummyReg)) {
       ArgNo++;
       continue;
@@ skipping 127 matching lines @@
     Registers[RegMIPS32::val] = false;
 
   REGMIPS32_TABLE
 
 #undef X
 
   return Registers;
 }
 
 void TargetMIPS32::lowerAlloca(const InstAlloca *Instr) {
-  UsesFramePointer = true;
   // Conservatively require the stack to be aligned. Some stack adjustment
   // operations implemented below assume that the stack is aligned before the
   // alloca. All the alloca code ensures that the stack alignment is preserved
   // after the alloca. The stack alignment restriction can be relaxed in some
   // cases.
   NeedsStackAlignment = true;
-  UnimplementedLoweringError(this, Instr);
+
+  // For default align=0, set it to the real value 1, to avoid any
+  // bit-manipulation problems below.
+  const uint32_t AlignmentParam = std::max(1u, Instr->getAlignInBytes());
+
+  // LLVM enforces power of 2 alignment.
+  assert(llvm::isPowerOf2_32(AlignmentParam));
+  assert(llvm::isPowerOf2_32(MIPS32_STACK_ALIGNMENT_BYTES));
+
+  const uint32_t Alignment =
+      std::max(AlignmentParam, MIPS32_STACK_ALIGNMENT_BYTES);
+  const bool OverAligned = Alignment > MIPS32_STACK_ALIGNMENT_BYTES;
+  const bool OptM1 = getFlags().getOptLevel() == Opt_m1;
+  const bool AllocaWithKnownOffset = Instr->getKnownFrameOffset();
+  const bool UseFramePointer =
+      hasFramePointer() || OverAligned || !AllocaWithKnownOffset || OptM1;
+
+  if (UseFramePointer)
+    setHasFramePointer();
+
+  Variable *SP = getPhysicalRegister(RegMIPS32::Reg_SP);
+
+  Variable *Dest = Instr->getDest();
+  Operand *TotalSize = Instr->getSizeInBytes();
+
+  if (const auto *ConstantTotalSize =
+          llvm::dyn_cast<ConstantInteger32>(TotalSize)) {
+    const uint32_t Value =
+        Utils::applyAlignment(ConstantTotalSize->getValue(), Alignment);
+    FixedAllocaSizeBytes += Value;
+    // Constant size alloca.
+    if (!UseFramePointer) {
+      // If we don't need a Frame Pointer, this alloca has a known offset to the
+      // stack pointer. We don't need adjust the stack pointer, nor assign any
+      // value to Dest, as Dest is rematerializable.
+      assert(Dest->isRematerializable());
+      Context.insert<InstFakeDef>(Dest);
+      return;
+    }
+  } else {
+    UnimplementedLoweringError(this, Instr);
+    return;
+  }
+
+  // Add enough to the returned address to account for the out args area.
+  if (MaxOutArgsSizeBytes > 0) {
+    Variable *T = makeReg(getPointerType());
+    _addiu(T, SP, MaxOutArgsSizeBytes);
+    _mov(Dest, T);
+  } else {
+    _mov(Dest, SP);
+  }
 }
 
 void TargetMIPS32::lowerInt64Arithmetic(const InstArithmetic *Instr,
                                         Variable *Dest, Operand *Src0,
                                         Operand *Src1) {
   InstArithmetic::OpKind Op = Instr->getOp();
   switch (Op) {
   case InstArithmetic::Add:
   case InstArithmetic::And:
   case InstArithmetic::Or:
@@ skipping 1112 matching lines @@
   Str << "\t.set\t"
       << "nomips16\n";
 }
 
 SmallBitVector TargetMIPS32::TypeToRegisterSet[RCMIPS32_NUM];
 SmallBitVector TargetMIPS32::TypeToRegisterSetUnfiltered[RCMIPS32_NUM];
 SmallBitVector TargetMIPS32::RegisterAliases[RegMIPS32::Reg_NUM];
 
 } // end of namespace MIPS32
 } // end of namespace Ice