ARM: Add a postRA pass to legalize stack offsets. Greedy approach (reserve IP).

src/IceTargetLoweringARM32.cpp

 //===- subzero/src/IceTargetLoweringARM32.cpp - ARM32 lowering ------------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 267 matching lines @@
     Func->advancedPhiLowering();
     Func->dump("After advanced Phi lowering");
   }
 
   // Stack frame mapping.
   Func->genFrame();
   if (Func->hasError())
     return;
   Func->dump("After stack frame mapping");
 
+  legalizeStackSlots();
+  if (Func->hasError())
+    return;
+  Func->dump("After legalizeStackSlots");
+
   Func->contractEmptyNodes();
   Func->reorderNodes();
 
   // Branch optimization.  This needs to be done just before code
   // emission.  In particular, no transformations that insert or
   // reorder CfgNodes should be done after branch optimization.  We go
   // ahead and do it before nop insertion to reduce the amount of work
   // needed for searching for opportunities.
   Func->doBranchOpt();
   Func->dump("After branch optimization");
@@ skipping 30 matching lines @@
   regAlloc(RAK_InfOnly);
   if (Func->hasError())
     return;
   Func->dump("After regalloc of infinite-weight variables");
 
   Func->genFrame();
   if (Func->hasError())
     return;
   Func->dump("After stack frame mapping");
 
+  legalizeStackSlots();
+  if (Func->hasError())
+    return;
+  Func->dump("After legalizeStackSlots");
+
   // Nop insertion
   if (Ctx->getFlags().shouldDoNopInsertion()) {
     Func->doNopInsertion();
   }
 }
 
 bool TargetARM32::doBranchOpt(Inst *I, const CfgNode *NextNode) {
   if (InstARM32Br *Br = llvm::dyn_cast<InstARM32Br>(I)) {
     return Br->optimizeBranch(NextNode);
   }
@@ skipping 29 matching lines @@
     // live upon function entry.
     if (RegNum == RegARM32::Reg_sp || RegNum == RegARM32::Reg_lr) {
       Func->addImplicitArg(Reg);
       Reg->setIgnoreLiveness();
     }
   }
   return Reg;
 }
 
 void TargetARM32::emitVariable(const Variable *Var) const {
+  if (!BuildDefs::dump())
+    return;
   Ostream &Str = Ctx->getStrEmit();
   if (Var->hasReg()) {
     Str << getRegName(Var->getRegNum(), Var->getType());
     return;
   }
   if (Var->getWeight().isInf()) {
     llvm::report_fatal_error(
         "Infinite-weight Variable has no register assigned");
   }
   int32_t Offset = Var->getStackOffset();
-  if (!hasFramePointer())
-    Offset += getStackAdjustment();
-  // TODO(jvoung): Handle out of range. Perhaps we need a scratch register
-  // to materialize a larger offset.
-  constexpr bool SignExt = false;
-  if (!OperandARM32Mem::canHoldOffset(Var->getType(), SignExt, Offset)) {
+  int32_t BaseRegNum = Var->getBaseRegNum();
+  if (BaseRegNum == Variable::NoRegister) {
+    BaseRegNum = getFrameOrStackReg();
+    if (!hasFramePointer())
+      Offset += getStackAdjustment();
+  }
+  if (!isLegalVariableStackOffset(Offset)) {
     llvm::report_fatal_error("Illegal stack offset");
   }
-  const Type FrameSPTy = IceType_i32;
-  Str << "[" << getRegName(getFrameOrStackReg(), FrameSPTy);
+  const Type FrameSPTy = stackSlotType();
+  Str << "[" << getRegName(BaseRegNum, FrameSPTy);
   if (Offset != 0) {
     Str << ", " << getConstantPrefix() << Offset;
   }
   Str << "]";
 }
 
 bool TargetARM32::CallingConv::I64InRegs(std::pair<int32_t, int32_t> *Regs) {
   if (NumGPRRegsUsed >= ARM32_MAX_GPR_ARG)
     return false;
   int32_t RegLo, RegHi;
@@ skipping 132 matching lines @@
 
 Type TargetARM32::stackSlotType() { return IceType_i32; }
 
 void TargetARM32::addProlog(CfgNode *Node) {
   // Stack frame layout:
   //
   // +------------------------+
   // | 1. preserved registers |
   // +------------------------+
   // | 2. padding             |
-  // +------------------------+
+  // +------------------------+ <--- FramePointer (if used)
   // | 3. global spill area   |
   // +------------------------+
   // | 4. padding             |
   // +------------------------+
   // | 5. local spill area    |
   // +------------------------+
   // | 6. padding             |
   // +------------------------+
   // | 7. allocas             |
-  // +------------------------+
+  // +------------------------+ <--- StackPointer
   //
   // The following variables record the size in bytes of the given areas:
   //  * PreservedRegsSizeBytes: area 1
   //  * SpillAreaPaddingBytes:  area 2
   //  * GlobalsSize:            area 3
   //  * GlobalsAndSubsequentPaddingSize: areas 3 - 4
   //  * LocalsSpillAreaSize:    area 5
   //  * SpillAreaSizeBytes:     areas 2 - 6
   // Determine stack frame offsets for each Variable without a
   // register assignment.  This can be done as one variable per stack
@@ skipping 94 matching lines @@
 
   // Align SP if necessary.
   if (NeedsStackAlignment) {
     uint32_t StackOffset = PreservedRegsSizeBytes;
     uint32_t StackSize = applyStackAlignment(StackOffset + SpillAreaSizeBytes);
     SpillAreaSizeBytes = StackSize - StackOffset;
   }
 
   // Generate "sub sp, SpillAreaSizeBytes"
   if (SpillAreaSizeBytes) {
-    // Use the IP inter-procedural scratch register if needed to legalize
-    // the immediate.
+    // Use the scratch register if needed to legalize the immediate.
     Operand *SubAmount = legalize(Ctx->getConstantInt32(SpillAreaSizeBytes),
-                                  Legal_Reg | Legal_Flex, RegARM32::Reg_ip);
+                                  Legal_Reg | Legal_Flex, getReservedTmpReg());
     Variable *SP = getPhysicalRegister(RegARM32::Reg_sp);
     _sub(SP, SP, SubAmount);
   }
   Ctx->statsUpdateFrameBytes(SpillAreaSizeBytes);
 
   resetStackAdjustment();
 
   // 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.
@@ skipping 80 matching lines @@
   if (UsesFramePointer) {
     Variable *FP = getPhysicalRegister(RegARM32::Reg_fp);
     // For late-stage liveness analysis (e.g. asm-verbose mode),
     // adding a fake use of SP before the assignment of SP=FP keeps
     // previous SP adjustments from being dead-code eliminated.
     Context.insert(InstFakeUse::create(Func, SP));
     _mov(SP, FP);
   } else {
     // add SP, SpillAreaSizeBytes
     if (SpillAreaSizeBytes) {
-      // Use the IP inter-procedural scratch register if needed to legalize
-      // the immediate. It shouldn't be live at this point.
-      Operand *AddAmount = legalize(Ctx->getConstantInt32(SpillAreaSizeBytes),
-                                    Legal_Reg | Legal_Flex, RegARM32::Reg_ip);
+      // Use the scratch register if needed to legalize the immediate.
+      Operand *AddAmount =
+          legalize(Ctx->getConstantInt32(SpillAreaSizeBytes),
+                   Legal_Reg | Legal_Flex, getReservedTmpReg());
       _add(SP, SP, AddAmount);
     }
   }
 
   // Add pop instructions for preserved registers.
   llvm::SmallBitVector CalleeSaves =
       getRegisterSet(RegSet_CalleeSave, RegSet_None);
   VarList GPRsToRestore;
   GPRsToRestore.reserve(CalleeSaves.size());
   // Consider FP and LR as callee-save / used as needed.
@@ skipping 29 matching lines @@
   Variable *RetValue = nullptr;
   if (RI->getSrcSize())
     RetValue = llvm::cast<Variable>(RI->getSrc(0));
   _bundle_lock();
   _bic(LR, LR, RetMask);
   _ret(LR, RetValue);
   _bundle_unlock();
   RI->setDeleted();
 }
 
+bool TargetARM32::isLegalVariableStackOffset(int32_t Offset) const {
+  constexpr bool SignExt = false;
+  return OperandARM32Mem::canHoldOffset(stackSlotType(), SignExt, Offset);
+}
+
+StackVariable *TargetARM32::legalizeVariableSlot(Variable *Var,
+                                                 Variable *OrigBaseReg) {
+  int32_t Offset = Var->getStackOffset();
+  // Legalize will likely need a movw/movt combination, but if the top
+  // bits are all 0 from negating the offset and subtracting, we could
+  // use that instead.
+  bool ShouldSub = (-Offset & 0xFFFF0000) == 0;
+  if (ShouldSub)
+    Offset = -Offset;
+  Operand *OffsetVal = legalize(Ctx->getConstantInt32(Offset),
+                                Legal_Reg | Legal_Flex, getReservedTmpReg());
+  Variable *ScratchReg = makeReg(IceType_i32, getReservedTmpReg());
+  if (ShouldSub)
+    _sub(ScratchReg, OrigBaseReg, OffsetVal);
+  else
+    _add(ScratchReg, OrigBaseReg, OffsetVal);
+  StackVariable *NewVar = Func->makeVariable<StackVariable>(stackSlotType());
+  NewVar->setWeight(RegWeight::Zero);
+  NewVar->setBaseRegNum(ScratchReg->getRegNum());
+  constexpr int32_t NewOffset = 0;
+  NewVar->setStackOffset(NewOffset);
+  return NewVar;
+}
+
+void TargetARM32::legalizeStackSlots() {
+  // If a stack variable's frame offset doesn't fit, convert from:
+  //   ldr X, OFF[SP]
+  // to:
+  //   movw/movt TMP, OFF_PART
+  //   add TMP, TMP, SP
+  //   ldr X, OFF_MORE[TMP]
+  //
+  // This is safe because we have reserved TMP, and add for ARM does not
+  // clobber the flags register.
+  Func->dump("Before legalizeStackSlots");
+  assert(hasComputedFrame());
+  // Early exit, if SpillAreaSizeBytes is really small.
+  if (isLegalVariableStackOffset(SpillAreaSizeBytes))
+    return;
+  Variable *OrigBaseReg = getPhysicalRegister(getFrameOrStackReg());
+  int32_t StackAdjust = 0;
+  // Do a fairly naive greedy clustering for now.  Pick the first stack slot
+  // that's out of bounds and make a new base reg using the architecture's temp
+  // register. If that works for the next slot, then great. Otherwise, create
+  // a new base register, clobbering the previous base register.  Never share a
+  // base reg across different basic blocks.  This isn't ideal if local and
+  // multi-block variables are far apart and their references are interspersed.
+  // It may help to be more coordinated about assign stack slot numbers
+  // and may help to assign smaller offsets to higher-weight variables
+  // so that they don't depend on this legalization.
+  for (CfgNode *Node : Func->getNodes()) {
+    Context.init(Node);
+    StackVariable *NewBaseReg = nullptr;
+    int32_t NewBaseOffset = 0;
+    while (!Context.atEnd()) {
+      PostIncrLoweringContext PostIncrement(Context);
+      Inst *CurInstr = Context.getCur();
+      Variable *Dest = CurInstr->getDest();
+      // Check if the previous NewBaseReg is clobbered, and reset if needed.
+      if ((Dest && NewBaseReg && Dest->hasReg() &&
+           Dest->getRegNum() == NewBaseReg->getBaseRegNum()) ||
+          llvm::isa<InstFakeKill>(CurInstr)) {
+        NewBaseReg = nullptr;
+        NewBaseOffset = 0;
+      }
+      // The stack adjustment only matters if we are using SP instead of FP.
+      if (!hasFramePointer()) {
+        if (auto *AdjInst = llvm::dyn_cast<InstARM32AdjustStack>(CurInstr)) {
+          StackAdjust += AdjInst->getAmount();
+          NewBaseOffset += AdjInst->getAmount();
+          continue;
+        }
+        if (llvm::isa<InstARM32Call>(CurInstr)) {
+          NewBaseOffset -= StackAdjust;
+          StackAdjust = 0;
+          continue;
+        }
+      }
+      // For now, only Mov instructions can have stack variables.  We need to
+      // know the type of instruction because we currently create a fresh one
+      // to replace Dest/Source, rather than mutate in place.
+      auto *MovInst = llvm::dyn_cast<InstARM32Mov>(CurInstr);
+      if (!MovInst) {
+        continue;
+      }
+      if (!Dest->hasReg()) {
+        int32_t Offset = Dest->getStackOffset();
+        Offset += StackAdjust;
+        if (!isLegalVariableStackOffset(Offset)) {
+          if (NewBaseReg) {
+            int32_t OffsetDiff = Offset - NewBaseOffset;
+            if (isLegalVariableStackOffset(OffsetDiff)) {
+              StackVariable *NewDest =
+                  Func->makeVariable<StackVariable>(stackSlotType());
+              NewDest->setWeight(RegWeight::Zero);
+              NewDest->setBaseRegNum(NewBaseReg->getBaseRegNum());
+              NewDest->setStackOffset(OffsetDiff);
+              Variable *NewDestVar = NewDest;
+              _mov(NewDestVar, MovInst->getSrc(0));
+              MovInst->setDeleted();
+              continue;
+            }
+          }
+          StackVariable *LegalDest = legalizeVariableSlot(Dest, OrigBaseReg);
+          assert(LegalDest != Dest);
+          Variable *LegalDestVar = LegalDest;
+          _mov(LegalDestVar, MovInst->getSrc(0));
+          MovInst->setDeleted();
+          NewBaseReg = LegalDest;
+          NewBaseOffset = Offset;
+          continue;
+        }
+      }
+      assert(MovInst->getSrcSize() == 1);
+      Variable *Var = llvm::dyn_cast<Variable>(MovInst->getSrc(0));
+      if (Var && !Var->hasReg()) {
+        int32_t Offset = Var->getStackOffset();
+        Offset += StackAdjust;
+        if (!isLegalVariableStackOffset(Offset)) {
+          if (NewBaseReg) {
+            int32_t OffsetDiff = Offset - NewBaseOffset;
+            if (isLegalVariableStackOffset(OffsetDiff)) {
+              StackVariable *NewVar =
+                  Func->makeVariable<StackVariable>(stackSlotType());
+              NewVar->setWeight(RegWeight::Zero);
+              NewVar->setBaseRegNum(NewBaseReg->getBaseRegNum());
+              NewVar->setStackOffset(OffsetDiff);
+              _mov(Dest, NewVar);
+              MovInst->setDeleted();
+              continue;
+            }
+          }
+          StackVariable *LegalVar = legalizeVariableSlot(Var, OrigBaseReg);
+          assert(LegalVar != Var);
+          _mov(Dest, LegalVar);
+          MovInst->setDeleted();
+          NewBaseReg = LegalVar;
+          NewBaseOffset = Offset;
+          continue;
+        }
+      }
+    }
+  }
+}
+
 void TargetARM32::split64(Variable *Var) {
   assert(Var->getType() == IceType_i64);
   Variable *Lo = Var->getLo();
   Variable *Hi = Var->getHi();
   if (Lo) {
     assert(Hi);
     return;
   }
   assert(Hi == nullptr);
   Lo = Func->makeVariable(IceType_i32);
@@ skipping 1220 matching lines @@
     Call->addArg(Val);
     lowerCall(Call);
     // The popcount helpers always return 32-bit values, while the intrinsic's
     // signature matches some 64-bit platform's native instructions and
     // expect to fill a 64-bit reg. Thus, clear the upper bits of the dest
     // just in case the user doesn't do that in the IR or doesn't toss the bits
     // via truncate.
     if (Val->getType() == IceType_i64) {
       Variable *DestHi = llvm::cast<Variable>(hiOperand(Dest));
       Constant *Zero = Ctx->getConstantZero(IceType_i32);
-      _mov(DestHi, Zero);
+      Variable *T = nullptr;
+      _mov(T, Zero);
+      _mov(DestHi, T);
     }
     return;
   }
   case Intrinsics::Ctlz: {
     // The "is zero undef" parameter is ignored and we always return
     // a well-defined value.
     Operand *Val = Instr->getArg(0);
     Variable *ValLoR;
     Variable *ValHiR = nullptr;
     if (Val->getType() == IceType_i64) {
@@ skipping 131 matching lines @@
         legalize(Ctx->getConstantInt32(32), Legal_Reg | Legal_Flex);
     _cmp(ValHiR, Zero);
     Variable *T2 = makeReg(IceType_i32);
     _add(T2, T, ThirtyTwo);
     _clz(T2, ValHiR, CondARM32::NE);
     // T2 is actually a source as well when the predicate is not AL
     // (since it may leave T2 alone). We use set_dest_nonkillable to
     // prolong the liveness of T2 as if it was used as a source.
     _set_dest_nonkillable();
     _mov(DestLo, T2);
-    _mov(DestHi, Ctx->getConstantZero(IceType_i32));
+    Variable *T3 = nullptr;
+    _mov(T3, Zero);
+    _mov(DestHi, T3);
     return;
   }
   _mov(Dest, T);
   return;
 }
 
 void TargetARM32::lowerLoad(const InstLoad *Load) {
   // A Load instruction can be treated the same as an Assign
   // instruction, after the source operand is transformed into an
   // OperandARM32Mem operand.
@@ skipping 520 matching lines @@
       << ".eabi_attribute 68, 1   @ Tag_Virtualization_use\n";
   if (CPUFeatures.hasFeature(TargetARM32Features::HWDivArm)) {
     Str << ".eabi_attribute 44, 2   @ Tag_DIV_use\n";
   }
   // Technically R9 is used for TLS with Sandboxing, and we reserve it.
   // However, for compatibility with current NaCl LLVM, don't claim that.
   Str << ".eabi_attribute 14, 3   @ Tag_ABI_PCS_R9_use: Not used\n";
 }
 
 } // end of namespace Ice