Subzero. ARM32. Address mode formation.

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 443 matching lines @@
         "Infinite-weight Variable has no register assigned");
   }
   int32_t Offset = Var->getStackOffset();
   int32_t BaseRegNum = Var->getBaseRegNum();
   if (BaseRegNum == Variable::NoRegister) {
     BaseRegNum = getFrameOrStackReg();
     if (!hasFramePointer())
       Offset += getStackAdjustment();
   }
   const Type VarTy = Var->getType();
-  if (!isLegalVariableStackOffset(VarTy, Offset)) {
+  if (!isLegalMemOffset(VarTy, Offset)) {
     llvm::report_fatal_error("Illegal stack offset");
   }
   Str << "[" << getRegName(BaseRegNum, VarTy);
   if (Offset != 0) {
     Str << ", " << getConstantPrefix() << Offset;
   }
   Str << "]";
 }
 
 bool TargetARM32::CallingConv::I64InRegs(std::pair<int32_t, int32_t> *Regs) {
@@ skipping 461 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(Type Ty, int32_t Offset) const {
-  constexpr bool SignExt = false;
-  return OperandARM32Mem::canHoldOffset(Ty, SignExt, Offset);
+bool TargetARM32::isLegalMemOffset(Type Ty, int32_t Offset) const {
+  constexpr bool ZeroExt = false;
+  return OperandARM32Mem::canHoldOffset(Ty, ZeroExt, Offset);
 }
 
-StackVariable *TargetARM32::legalizeVariableSlot(Variable *Var,
-                                                 int32_t StackAdjust,
-                                                 Variable *OrigBaseReg) {
-  int32_t Offset = Var->getStackOffset() + StackAdjust;
+Variable *TargetARM32::newBaseRegister(int32_t OriginalOffset,
+                                       int32_t StackAdjust,
+                                       Variable *OrigBaseReg) {
+  int32_t Offset = OriginalOffset + StackAdjust;
   // 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->setMustNotHaveReg();
-  NewVar->setBaseRegNum(ScratchReg->getRegNum());
-  constexpr int32_t NewOffset = 0;
-  NewVar->setStackOffset(NewOffset);
-  return NewVar;
+  return ScratchReg;
+}
+
+StackVariable *TargetARM32::legalizeStackSlot(Type Ty, int32_t Offset,
+                                              int32_t StackAdjust,
+                                              Variable *OrigBaseReg,
+                                              Variable **NewBaseReg,
+                                              int32_t *NewBaseOffset) {

[Karl, 2015/11/06 21:11:01]

Why not int32_t &NewBaseOffset?

[John, 2015/11/09 22:42:25]

Because the method changes NewBaseOffset inside.

I really dislike non-const references as parameters. They make the code harder
to read -- especially if you're not familiar with it. Several times over I
caught myself trying to find how a variable was being initialized, just to find
out a method was taking that parameter by reference and initializing it.

with this signature, at call site, we have

legalizeStackSlot(..., &NewBaseOffset);

so I at least have an idea that legalizeStackSlot may change that value.

+  if (*NewBaseReg == nullptr) {
+    *NewBaseReg = newBaseRegister(Offset, StackAdjust, OrigBaseReg);
+    *NewBaseOffset = Offset + StackAdjust;
+  }
+
+  int32_t OffsetDiff = Offset + StackAdjust - *NewBaseOffset;
+  if (!isLegalMemOffset(Ty, OffsetDiff)) {
+    *NewBaseReg = newBaseRegister(Offset, StackAdjust, OrigBaseReg);
+    *NewBaseOffset = Offset + StackAdjust;
+    OffsetDiff = 0;
+  }
+
+  StackVariable *NewDest = Func->makeVariable<StackVariable>(Ty);
+  NewDest->setMustNotHaveReg();
+  NewDest->setBaseRegNum((*NewBaseReg)->getRegNum());
+  NewDest->setStackOffset(OffsetDiff);
+  return NewDest;
+}
+
+void TargetARM32::legalizeMovStackAddrImm(InstARM32Mov *MovInstr,
+                                          int32_t StackAdjust,
+                                          Variable *OrigBaseReg,
+                                          Variable **NewBaseReg,
+                                          int32_t *NewBaseOffset) {
+  Variable *Dest = MovInstr->getDest();
+  assert(Dest != nullptr);
+  Type DestTy = Dest->getType();
+  assert(DestTy != IceType_i64);
+
+  Operand *Src = MovInstr->getSrc(0);
+  Type SrcTy = Src->getType();
+  assert(SrcTy != IceType_i64);
+
+  if (MovInstr->isMultiDest() || MovInstr->isMultiSource())
+    return;
+
+  bool Legalized = false;
+  if (!Dest->hasReg()) {
+    assert(llvm::cast<Variable>(Src)->hasReg());
+    const int32_t Offset = Dest->getStackOffset();
+    if (!isLegalMemOffset(DestTy, Offset + StackAdjust)) {
+      Legalized = true;
+      Dest = legalizeStackSlot(DestTy, Offset, StackAdjust, OrigBaseReg,
+                               NewBaseReg, NewBaseOffset);
+    }
+  } else if (auto *Var = llvm::dyn_cast<Variable>(Src)) {
+    if (!Var->hasReg()) {
+      const int32_t Offset = Var->getStackOffset();
+      if (!isLegalMemOffset(SrcTy, Offset + StackAdjust)) {
+        Legalized = true;
+        Src = legalizeStackSlot(SrcTy, Offset, StackAdjust, OrigBaseReg,
+                                NewBaseReg, NewBaseOffset);
+      }
+    }
+  } else if (auto *Mem = llvm::dyn_cast<OperandARM32Mem>(Src)) {
+    if (ConstantInteger32 *OffsetOp = Mem->getOffset()) {
+      const int32_t Offset = OffsetOp->getValue();
+      if (!isLegalMemOffset(SrcTy, Offset + StackAdjust)) {
+        assert(Mem->getBase()->hasReg());
+        assert(Mem->getBase()->getRegNum() == (int)getFrameOrStackReg());

[Jim Stichnoth, 2015/11/08 20:05:51]

int32_t for consistency

[John, 2015/11/09 22:42:24]

Done.

+        Legalized = true;
+        Src = legalizeStackSlot(SrcTy, Offset, StackAdjust, OrigBaseReg,
+                                NewBaseReg, NewBaseOffset);
+      }
+    }
+  }
+
+  if (Legalized) {
+    _mov(Dest, Src);
+    MovInstr->setDeleted();
+  }
 }
 
 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.
   // TODO(jpp): this is not safe -- loads and stores of q registers can't have
   // offsets.
-  if (isLegalVariableStackOffset(IceType_v4i32, SpillAreaSizeBytes))
+  if (isLegalMemOffset(IceType_v4i32, 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;
+    Variable *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.
-      bool MayNeedOffsetRewrite = false;
+      // The Lowering ensures that ldr and str always have legal Mem operands.
+      // The only other instruction that may access memory is mov.
       if (auto *MovInstr = llvm::dyn_cast<InstARM32Mov>(CurInstr)) {
-        MayNeedOffsetRewrite =
-            !MovInstr->isMultiDest() && !MovInstr->isMultiSource();
-      }
-
-      if (!MayNeedOffsetRewrite) {
-        continue;
-      }
-
-      assert(Dest != nullptr);
-      Type DestTy = Dest->getType();
-      assert(DestTy != IceType_i64);
-      if (!Dest->hasReg()) {
-        int32_t Offset = Dest->getStackOffset();
-        Offset += StackAdjust;
-        if (!isLegalVariableStackOffset(DestTy, Offset)) {
-          if (NewBaseReg) {
-            int32_t OffsetDiff = Offset - NewBaseOffset;
-            if (isLegalVariableStackOffset(DestTy, OffsetDiff)) {
-              StackVariable *NewDest =
-                  Func->makeVariable<StackVariable>(stackSlotType());
-              NewDest->setMustNotHaveReg();
-              NewDest->setBaseRegNum(NewBaseReg->getBaseRegNum());
-              NewDest->setStackOffset(OffsetDiff);
-              Variable *NewDestVar = NewDest;
-              _mov(NewDestVar, CurInstr->getSrc(0));
-              CurInstr->setDeleted();
-              continue;
-            }
-          }
-          StackVariable *LegalDest =
-              legalizeVariableSlot(Dest, StackAdjust, OrigBaseReg);
-          assert(LegalDest != Dest);
-          Variable *LegalDestVar = LegalDest;
-          _mov(LegalDestVar, CurInstr->getSrc(0));
-          CurInstr->setDeleted();
-          NewBaseReg = LegalDest;
-          NewBaseOffset = Offset;
-          continue;
-        }
-      }
-      assert(CurInstr->getSrcSize() == 1);
-      Variable *Var = llvm::dyn_cast<Variable>(CurInstr->getSrc(0));
-      if (Var && !Var->hasReg()) {
-        Type VarTy = Var->getType();
-        int32_t Offset = Var->getStackOffset();
-        Offset += StackAdjust;
-        if (!isLegalVariableStackOffset(VarTy, Offset)) {
-          if (NewBaseReg) {
-            int32_t OffsetDiff = Offset - NewBaseOffset;
-            if (isLegalVariableStackOffset(VarTy, OffsetDiff)) {
-              StackVariable *NewVar =
-                  Func->makeVariable<StackVariable>(stackSlotType());
-              NewVar->setMustNotHaveReg();
-              NewVar->setBaseRegNum(NewBaseReg->getBaseRegNum());
-              NewVar->setStackOffset(OffsetDiff);
-              _mov(Dest, NewVar);
-              CurInstr->setDeleted();
-              continue;
-            }
-          }
-          StackVariable *LegalVar =
-              legalizeVariableSlot(Var, StackAdjust, OrigBaseReg);
-          assert(LegalVar != Var);
-          _mov(Dest, LegalVar);
-          CurInstr->setDeleted();
-          NewBaseReg = LegalVar;
-          NewBaseOffset = Offset;
-          continue;
-        }
+        legalizeMovStackAddrImm(MovInstr, StackAdjust, OrigBaseReg, &NewBaseReg,
+                                &NewBaseOffset);
       }
     }
   }
 }
 
 Operand *TargetARM32::loOperand(Operand *Operand) {
   assert(Operand->getType() == IceType_i64);
   if (Operand->getType() != IceType_i64)
     return Operand;
   if (auto *Var64On32 = llvm::dyn_cast<Variable64On32>(Operand))
@@ skipping 44 matching lines @@
       lowerArithmetic(InstArithmetic::create(Func, InstArithmetic::Add, NewBase,
                                              Base, Four));
       return OperandARM32Mem::create(Func, SplitType, NewBase, Mem->getIndex(),
                                      Mem->getShiftOp(), Mem->getShiftAmt(),
                                      Mem->getAddrMode());
     } else {
       Variable *Base = Mem->getBase();
       ConstantInteger32 *Offset = Mem->getOffset();
       assert(!Utils::WouldOverflowAdd(Offset->getValue(), 4));
       int32_t NextOffsetVal = Offset->getValue() + 4;
-      const bool SignExt = false;
-      if (!OperandARM32Mem::canHoldOffset(SplitType, SignExt, NextOffsetVal)) {
+      const bool ZeroExt = false;

[Karl, 2015/11/06 21:11:01]

constexpr?

[John, 2015/11/09 22:42:25]

Done.

+      if (!OperandARM32Mem::canHoldOffset(SplitType, ZeroExt, NextOffsetVal)) {
         // We have to make a temp variable and add 4 to either Base or Offset.
         // If we add 4 to Offset, this will convert a non-RegReg addressing
         // mode into a RegReg addressing mode. Since NaCl sandboxing disallows
         // RegReg addressing modes, prefer adding to base and replacing
         // instead. Thus we leave the old offset alone.
         Constant *Four = Ctx->getConstantInt32(4);
         Variable *NewBase = Func->makeVariable(Base->getType());
         lowerArithmetic(InstArithmetic::create(Func, InstArithmetic::Add,
                                                NewBase, Base, Four));
         Base = NewBase;
@@ skipping 626 matching lines @@
   if (Instr->isUnconditional()) {
     _br(Instr->getTargetUnconditional());
     return;
   }
   Operand *Cond = Instr->getCondition();
 
   CondARM32::Cond BrCondTrue0 = CondARM32::NE;
   CondARM32::Cond BrCondTrue1 = CondARM32::kNone;
   CondARM32::Cond BrCondFalse = CondARM32::kNone;
   if (!_mov_i1_to_flags(Cond, &BrCondTrue0, &BrCondTrue1, &BrCondFalse)) {
-    // "Cond" was not fold.
+    // "Cond" was not folded.
     Type Ty = Cond->getType();
     Variable *Src0R = legalizeToReg(Cond);
     assert(Ty == IceType_i1);
     if (Ty != IceType_i32)
       _uxt(Src0R, Src0R);
     Constant *_0 = Ctx->getConstantZero(IceType_i32);
     _cmp(Src0R, _0);
     BrCondTrue0 = CondARM32::NE;
   }
 
@@ skipping 1535 matching lines @@
   Type Ty = Load->getDest()->getType();
   Operand *Src0 = formMemoryOperand(Load->getSourceAddress(), Ty);
   Variable *DestLoad = Load->getDest();
 
   // TODO(jvoung): handled folding opportunities. Sign and zero extension can
   // be folded into a load.
   InstAssign *Assign = InstAssign::create(Func, DestLoad, Src0);
   lowerAssign(Assign);
 }
 
-void TargetARM32::doAddressOptLoad() {}
+namespace {
+void dumpAddressOpt(const Cfg *Func, const Variable *Base, int32_t Offset,
+                    const Variable *OffsetReg, int16_t OffsetRegShamt,

[Jim Stichnoth, 2015/11/08 20:05:51]

tiny nit - OffsetRegShAmt ?
(here and below)

[John, 2015/11/09 22:42:24]

Done.

+                    const Inst *Reason) {
+  if (!BuildDefs::dump())
+    return;
+  if (!Func->isVerbose(IceV_AddrOpt))
+    return;
+  OstreamLocker _(Func->getContext());
+  Ostream &Str = Func->getContext()->getStrDump();
+  Str << "Instruction: ";
+  Reason->dumpDecorated(Func);
+  Str << "  results in Base=";
+  if (Base)
+    Base->dump(Func);
+  else
+    Str << "<null>";
+  Str << ", OffsetReg=";
+  if (OffsetReg)
+    OffsetReg->dump(Func);
+  else
+    Str << "<null>";
+  Str << ", Shift=" << OffsetRegShamt << ", Offset=" << Offset << "\n";
+}
+
+bool matchAssign(const VariablesMetadata *VMetadata, Variable **Var,
+                 int32_t *Offset, const Inst **Reason) {
+  // Var originates from Var=SrcVar ==> set Var:=SrcVar
+  if (*Var == nullptr)
+    return false;
+  const Inst *VarAssign = VMetadata->getSingleDefinition(*Var);
+  if (!VarAssign)
+    return false;
+  assert(!VMetadata->isMultiDef(*Var));
+  if (!llvm::isa<InstAssign>(VarAssign))
+    return false;
+
+  Operand *SrcOp = VarAssign->getSrc(0);
+  assert(SrcOp);

[Jim Stichnoth, 2015/11/08 20:05:50]

This assert is a relic of the early days when maybe it was possible for getSrc()
to return nullptr, or maybe the infrastructure wasn't as solid, who knows. 
These days it's just not possible so I would just remove the assert.

[John, 2015/11/09 22:42:25]

Done.

+  if (auto *SrcVar = llvm::dyn_cast<Variable>(SrcOp)) {
+    if (!VMetadata->isMultiDef(SrcVar) ||
+        // TODO: ensure SrcVar stays single-BB
+        false) {
+      return false;
+      *Var = SrcVar;

[Jim Stichnoth, 2015/11/08 20:05:51]

this statement is unreachable

[John, 2015/11/09 22:42:24]

Done.

+    } else if (auto *Const = llvm::dyn_cast<ConstantInteger32>(SrcOp)) {

[Jim Stichnoth, 2015/11/08 20:05:51]

Don't use "else if" if the previous branch is really supposed to always return.

[John, 2015/11/09 22:42:24]

N/A.

+      if (false)
+        return false;

[Jim Stichnoth, 2015/11/08 20:05:51]

Why not return true?
:)

[John, 2015/11/09 22:42:24]

I really don't know how high I was here.

+      int32_t MoreOffset = Const->getValue();
+      int32_t NewOffset = MoreOffset + *Offset;
+      if (Utils::WouldOverflowAdd(*Offset, MoreOffset))
+        return false;
+      *Var = nullptr;
+      *Offset += NewOffset;
+    }
+
+    *Reason = VarAssign;
+    return true;
+  }
+
+  return false;
+}
+
+bool isAddOrSub(const Inst *Inst, InstArithmetic::OpKind *Kind) {
+  if (auto *Arith = llvm::dyn_cast_or_null<const InstArithmetic>(Inst)) {

[Jim Stichnoth, 2015/11/08 20:05:51]

Can you just use dyn_cast?  It looks like Inst can never be nullptr.

Also, I like your earlier idea of using Instr instead of Inst for the variable
name.

[John, 2015/11/09 22:42:24]

Done.

+    switch (Arith->getOp()) {
+    default:
+      return false;
+    case InstArithmetic::Add:
+    case InstArithmetic::Sub:
+      *Kind = Arith->getOp();
+      return true;
+    }
+  }
+  return false;
+}
+
+bool matchCombinedBaseIndex(const VariablesMetadata *VMetadata, Variable **Base,
+                            Variable **OffsetReg, int32_t OffsetRegShamt,
+                            const Inst **Reason) {
+  // OffsetReg==nullptr && Base is Base=Var1+Var2 ==>
+  //   set Base=Var1, OffsetReg=Var2, Shift=0
+  if (*Base == nullptr)
+    return false;
+  if (*OffsetReg != nullptr)
+    return false;
+  assert(OffsetRegShamt == 0);
+  const Inst *BaseInst = VMetadata->getSingleDefinition(*Base);
+  if (BaseInst == nullptr)
+    return false;
+  assert(!VMetadata->isMultiDef(*Base));
+  if (BaseInst->getSrcSize() < 2)
+    return false;
+  auto *Var1 = llvm::dyn_cast<Variable>(BaseInst->getSrc(0));
+  if (!Var1)
+    return false;
+  if (VMetadata->isMultiDef(Var1))
+    return false;
+  auto *Var2 = llvm::dyn_cast<Variable>(BaseInst->getSrc(1));
+  if (!Var2)
+    return false;
+  if (VMetadata->isMultiDef(Var2))
+    return false;
+  InstArithmetic::OpKind _;
+  if (!isAddOrSub(BaseInst, &_) ||
+      // TODO: ensure Var1 and Var2 stay single-BB
+      false)
+    return false;
+  *Base = Var1;
+  *OffsetReg = Var2;
+  // OffsetRegShamt is already 0.
+  *Reason = BaseInst;
+  return true;
+}
+
+bool matchShiftedOffsetReg(const VariablesMetadata *VMetadata,
+                           Variable **OffsetReg, OperandARM32::ShiftKind *Kind,
+                           int32_t *OffsetRegShamt, const Inst **Reason) {
+  // OffsetReg is OffsetReg=Var*Const && log2(Const)+Shift<=32 ==>
+  //   OffsetReg=Var, Shift+=log2(Const)
+  // OffsetReg is OffsetReg=Var<<Const && Const+Shift<=32 ==>
+  //   OffsetReg=Var, Shift+=Const
+  // OffsetReg is OffsetReg=Var>>Const && Const-Shift>=-32 ==>
+  //   OffsetReg=Var, Shift-=Const
+  OperandARM32::ShiftKind NewShiftKind = OperandARM32::kNoShift;
+  if (*OffsetReg == nullptr)
+    return false;
+  auto *IndexInst = VMetadata->getSingleDefinition(*OffsetReg);
+  if (IndexInst == nullptr)
+    return false;
+  assert(!VMetadata->isMultiDef(*OffsetReg));
+  if (IndexInst->getSrcSize() < 2)
+    return false;
+  auto *ArithInst = llvm::dyn_cast<InstArithmetic>(IndexInst);
+  if (ArithInst == nullptr)
+    return false;
+  auto *Var = llvm::dyn_cast<Variable>(ArithInst->getSrc(0));
+  if (Var == nullptr)
+    return false;
+  auto *Const = llvm::dyn_cast<ConstantInteger32>(ArithInst->getSrc(1));
+  if (Const == nullptr) {
+    assert(!llvm::isa<ConstantInteger32>(ArithInst->getSrc(0)));
+    return false;
+  }
+  if (VMetadata->isMultiDef(Var) || Const->getType() != IceType_i32)
+    return false;
+
+  uint32_t NewShamt = -1;
+  switch (ArithInst->getOp()) {
+  default:
+    return false;
+  case InstArithmetic::Shl: {
+    NewShiftKind = OperandARM32::LSL;
+    NewShamt = Const->getValue();
+    if (NewShamt > 31)
+      return false;
+  } break;
+  case InstArithmetic::Lshr: {
+    NewShiftKind = OperandARM32::LSR;
+    NewShamt = Const->getValue();
+    if (NewShamt > 31)
+      return false;
+  } break;
+  case InstArithmetic::Ashr: {
+    NewShiftKind = OperandARM32::ASR;
+    NewShamt = Const->getValue();
+    if (NewShamt > 31)
+      return false;
+  } break;
+  case InstArithmetic::Udiv:
+  case InstArithmetic::Mul: {
+    const uint32_t UnsignedConst = Const->getValue();
+    NewShamt = llvm::findFirstSet(UnsignedConst);
+    if (NewShamt != llvm::findLastSet(UnsignedConst)) {
+      // First bit set is not the same as the last bit set, so Const is not
+      // a power of 2.
+      return false;
+    }
+    NewShiftKind = ArithInst->getOp() == InstArithmetic::Udiv
+                       ? OperandARM32::LSR
+                       : OperandARM32::LSL;
+  } break;
+  }
+  // Allowed "transitions":
+  //   kNoShift -> * iff NewShamt < 31
+  //   LSL -> LSL    iff NewShamt + OffsetRegShamt < 31
+  //   LSR -> LSR    iff NewShamt + OffsetRegShamt < 31
+  //   ASR -> ASR    iff NewShamt + OffsetRegShamt < 31
+  if (*Kind != OperandARM32::kNoShift && *Kind != NewShiftKind) {
+    return false;
+  }
+  const int32_t NewOffsetRegShamt = *OffsetRegShamt + NewShamt;
+  if (NewOffsetRegShamt > 31)
+    return false;
+  *OffsetReg = Var;
+  *OffsetRegShamt = NewOffsetRegShamt;
+  *Kind = NewShiftKind;
+  *Reason = IndexInst;
+  return true;
+}
+
+bool matchOffsetBase(const VariablesMetadata *VMetadata, Variable **Base,
+                     int32_t *Offset, const Inst **Reason) {
+  // Base is Base=Var+Const || Base is Base=Const+Var ==>
+  //   set Base=Var, Offset+=Const
+  // Base is Base=Var-Const ==>
+  //   set Base=Var, Offset-=Const
+  if (*Base == nullptr)
+    return false;
+  const Inst *BaseInst = VMetadata->getSingleDefinition(*Base);
+  if (BaseInst == nullptr) {
+    return false;
+  }
+  assert(!VMetadata->isMultiDef(*Base));
+
+  auto *ArithInst = llvm::dyn_cast<const InstArithmetic>(BaseInst);
+  if (ArithInst == nullptr)
+    return false;
+  InstArithmetic::OpKind Kind;
+  if (!isAddOrSub(ArithInst, &Kind))
+    return false;
+  bool IsAdd = Kind == InstArithmetic::Add;
+  Operand *Src0 = ArithInst->getSrc(0);
+  Operand *Src1 = ArithInst->getSrc(1);
+  auto *Var0 = llvm::dyn_cast<Variable>(Src0);
+  auto *Var1 = llvm::dyn_cast<Variable>(Src1);
+  auto *Const0 = llvm::dyn_cast<ConstantInteger32>(Src0);
+  auto *Const1 = llvm::dyn_cast<ConstantInteger32>(Src1);
+  Variable *NewBase = nullptr;
+  int32_t NewOffset = *Offset;
+
+  if (Var0 == nullptr && Const0 == nullptr) {
+    assert(llvm::isa<ConstantRelocatable>(Src0));
+    return false;
+  }
+
+  if (Var1 == nullptr && Const1 == nullptr) {
+    assert(llvm::isa<ConstantRelocatable>(Src1));
+    return false;
+  }
+
+  if (Var0 && Var1)
+    // TODO(jpp): merge base/index splitting into here.
+    return false;
+  if (!IsAdd && Var1)
+    return false;
+  if (Var0)
+    NewBase = Var0;
+  else if (Var1)
+    NewBase = Var1;
+  // Compute the updated constant offset.
+  if (Const0) {
+    int32_t MoreOffset = IsAdd ? Const0->getValue() : -Const0->getValue();
+    if (Utils::WouldOverflowAdd(NewOffset, MoreOffset))
+      return false;
+    NewOffset += MoreOffset;
+  }
+  if (Const1) {
+    int32_t MoreOffset = IsAdd ? Const1->getValue() : -Const1->getValue();
+    if (Utils::WouldOverflowAdd(NewOffset, MoreOffset))
+      return false;
+    NewOffset += MoreOffset;
+  }
+
+  // Update the computed address parameters once we are sure optimization
+  // is valid.
+  *Base = NewBase;
+  *Offset = NewOffset;
+  *Reason = BaseInst;
+  return true;
+}
+} // end of anonymous namespace
+
+// ARM32 address modes:
+//  ld/st i[8|16|32]: [reg], [reg +/- imm12], [pc +/- imm12],
+//                    [reg +/- reg << shamt5]
+//  ld/st f[32|64]  : [reg], [reg +/- imm8] , [pc +/- imm8]
+//  ld/st vectors   : [reg]
+//
+// For now, we don't handle address modes with Relocatables.
+namespace {
+// MemTraits contains per-type valid address mode information.
+#define X(tag, elementty, int_width, vec_width, sbits, ubits, rraddr, shaddr)  \
+  static_assert(!(shaddr) || rraddr, "Check ICETYPEARM32_TABLE::" #tag);
+ICETYPEARM32_TABLE
+#undef X
+
+static const struct {
+  int32_t ValidImmMask;
+  bool CanHaveImm;
+  bool CanHaveIndex;
+  bool CanHaveShiftedIndex;
+} MemTraits[] = {
+#define X(tag, elementty, int_width, vec_width, sbits, ubits, rraddr, shaddr)  \
+  { (1 << ubits) - 1, (ubits) > 0, rraddr, shaddr, }                           \
+  ,
+    ICETYPEARM32_TABLE
+#undef X
+};
+static constexpr SizeT MemTraitsSize = llvm::array_lengthof(MemTraits);
+} // end of anonymous namespace
+
+OperandARM32Mem *TargetARM32::formAddressingMode(Type Ty, Cfg *Func,
+                                                 const Inst *LdSt,
+                                                 Operand *Base) {
+  assert(Base != nullptr);
+  int32_t OffsetImm = 0;
+  Variable *OffsetReg = nullptr;
+  int32_t OffsetRegShamt = 0;
+  OperandARM32::ShiftKind ShiftKind = OperandARM32::kNoShift;
+
+  Func->resetCurrentNode();
+  if (Func->isVerbose(IceV_AddrOpt)) {
+    OstreamLocker L(Func->getContext());

[Jim Stichnoth, 2015/11/08 20:05:51]

Earlier you used "OstreamLocker _(...);"

[John, 2015/11/09 22:42:24]

Changes everywhere.

+    Ostream &Str = Func->getContext()->getStrDump();
+    Str << "\nAddress mode formation:\t";
+    LdSt->dumpDecorated(Func);
+  }
+
+  if (isVectorType(Ty))
+    // vector loads and stores do not allow offsets, and only support the
+    // "[reg]" addressing mode (the other supported modes are write back.)
+    return nullptr;
+
+  auto *BaseVar = llvm::dyn_cast<Variable>(Base);
+  if (BaseVar == nullptr)
+    return nullptr;
+
+  assert(Ty < MemTraitsSize);
+  auto *TypeTraits = &MemTraits[Ty];
+  const bool CanHaveIndex = TypeTraits->CanHaveIndex;
+  const bool CanHaveShiftedIndex = TypeTraits->CanHaveShiftedIndex;
+  const bool CanHaveImm = TypeTraits->CanHaveImm;
+  const int32_t ValidImmMask = TypeTraits->ValidImmMask;
+  assert(!CanHaveImm || ValidImmMask >= 0);
+
+  const VariablesMetadata *VMetadata = Func->getVMetadata();
+  const Inst *Reason = nullptr;
+
+  do {
+    if (Reason != nullptr) {
+      dumpAddressOpt(Func, BaseVar, OffsetImm, OffsetReg, OffsetRegShamt,
+                     Reason);
+      Reason = nullptr;
+    }
+
+    if (matchAssign(VMetadata, &BaseVar, &OffsetImm, &Reason)) {
+      continue;
+    }
+
+    if (CanHaveIndex &&
+        matchAssign(VMetadata, &OffsetReg, &OffsetImm, &Reason)) {
+      continue;
+    }
+
+    if (CanHaveIndex && matchCombinedBaseIndex(VMetadata, &BaseVar, &OffsetReg,
+                                               OffsetRegShamt, &Reason)) {
+      continue;
+    }
+
+    if (CanHaveShiftedIndex) {
+      if (matchShiftedOffsetReg(VMetadata, &OffsetReg, &ShiftKind,
+                                &OffsetRegShamt, &Reason)) {
+        continue;
+      }
+
+      if ((OffsetRegShamt == 0) &&
+          matchShiftedOffsetReg(VMetadata, &BaseVar, &ShiftKind,
+                                &OffsetRegShamt, &Reason)) {
+        std::swap(BaseVar, OffsetReg);
+        continue;
+      }
+    }
+
+    if (matchOffsetBase(VMetadata, &BaseVar, &OffsetImm, &Reason)) {
+      continue;
+    }
+  } while (Reason);
+
+  if (BaseVar == nullptr) {
+    // [OffsetReg{, LSL Shamt}{, #OffsetImm}] is not legal in ARM, so we have to
+    // legalize the addressing mode to [BaseReg, OffsetReg{, LSL Shamt}].
+    // Instead of a zeroed BaseReg, we initialize it with OffsetImm:
+    //
+    // [OffsetReg{, LSL Shamt}{, #OffsetImm}] ->
+    //     mov BaseReg, #OffsetImm
+    //     use of [BaseReg, OffsetReg{, LSL Shamt}]
+    //
+    static constexpr Type PointerType = IceType_i32;
+    BaseVar = makeReg(PointerType);
+    Context.insert(
+        InstAssign::create(Func, BaseVar, Ctx->getConstantInt32(OffsetImm)));
+    OffsetImm = 0;
+  } else if (OffsetImm != 0) {
+    // ARM Ldr/Str instructions have limited range immediates. The formation
+    // loop above materialized an Immediate carelessly, so we ensure the
+    // generated offset is sane.
+    const int32_t PositiveOffset = OffsetImm > 0 ? OffsetImm : -OffsetImm;
+    const InstArithmetic::OpKind Op =
+        OffsetImm > 0 ? InstArithmetic::Add : InstArithmetic::Sub;
+
+    if (!CanHaveImm || !isLegalMemOffset(Ty, OffsetImm) ||
+        OffsetReg != nullptr) {
+      if (OffsetReg == nullptr) {
+        // We formed a [Base, #const] addressing mode which is not encodable in
+        // ARM. There is little point in forming an address mode now if we don't
+        // have an offset. Effectively, we would end up with something like
+        //
+        // [Base, #const] -> add T, Base, #const
+        //                   use of [T]
+        //
+        // Which is exactly what we already have. So we just bite the bullet
+        // here and don't form any address mode.
+        return nullptr;
+      }
+      // We formed [Base, Offset {, LSL Amnt}, #const]. Oops. Legalize it to
+      //
+      // [Base, Offset, {LSL amount}, #const] ->
+      //      add T, Base, #const
+      //      use of [T, Offset {, LSL amount}]
+      static constexpr Type PointerType = IceType_i32;

[Jim Stichnoth, 2015/11/08 20:05:51]

Can you use the existing getPointerType() instead?

[John, 2015/11/09 22:42:24]

Then it is no longer a constexpr. :(

[Jim Stichnoth, 2015/11/09 22:47:49]

Then why did you subsequently change it to "const"?

[John, 2015/11/09 22:52:30]

Done.

+      Variable *T = makeReg(PointerType);
+      Context.insert(InstArithmetic::create(
+          Func, Op, T, BaseVar, Ctx->getConstantInt32(PositiveOffset)));
+      BaseVar = T;
+      OffsetImm = 0;
+    }
+  }
+
+  assert(BaseVar != nullptr);
+  assert(OffsetImm == 0 || OffsetReg == nullptr);
+  assert(OffsetReg == nullptr || CanHaveIndex);
+  assert(OffsetImm < 0 ? (ValidImmMask & -OffsetImm) == -OffsetImm
+                       : (ValidImmMask & OffsetImm) == OffsetImm);
+
+  if (OffsetReg != nullptr) {
+    return OperandARM32Mem::create(Func, Ty, BaseVar, OffsetReg, ShiftKind,
+                                   OffsetRegShamt);
+  }
+
+  return OperandARM32Mem::create(
+      Func, Ty, BaseVar,
+      llvm::cast<ConstantInteger32>(Ctx->getConstantInt32(OffsetImm)));
+}
+
+void TargetARM32::doAddressOptLoad() {
+  Inst *Instr = Context.getCur();
+  assert(llvm::isa<InstLoad>(Instr));
+  Variable *Dest = Instr->getDest();
+  Operand *Addr = Instr->getSrc(0);
+  if (OperandARM32Mem *Mem =
+          formAddressingMode(Dest->getType(), Func, Instr, Addr)) {
+    Instr->setDeleted();
+    Context.insert(InstLoad::create(Func, Dest, Mem));
+  }
+}
 
 void TargetARM32::randomlyInsertNop(float Probability,
                                     RandomNumberGenerator &RNG) {
   RandomNumberGeneratorWrapper RNGW(RNG);
   if (RNGW.getTrueWithProbability(Probability)) {
     UnimplementedError(Func->getContext()->getFlags());
   }
 }
 
 void TargetARM32::lowerPhi(const InstPhi * /*Inst*/) {
@@ skipping 180 matching lines @@
     Variable *ValueHi = legalizeToReg(hiOperand(Value));
     Variable *ValueLo = legalizeToReg(loOperand(Value));
     _str(ValueHi, llvm::cast<OperandARM32Mem>(hiOperand(NewAddr)));
     _str(ValueLo, llvm::cast<OperandARM32Mem>(loOperand(NewAddr)));
   } else {
     Variable *ValueR = legalizeToReg(Value);
     _str(ValueR, NewAddr);
   }
 }
 
-void TargetARM32::doAddressOptStore() {}
+void TargetARM32::doAddressOptStore() {
+  Inst *Instr = Context.getCur();
+  assert(llvm::isa<InstStore>(Instr));
+  Operand *Src = Instr->getSrc(0);
+  Operand *Addr = Instr->getSrc(1);
+  if (OperandARM32Mem *Mem =
+          formAddressingMode(Src->getType(), Func, Instr, Addr)) {
+    Instr->setDeleted();
+    Context.insert(InstStore::create(Func, Src, Mem));
+  }
+}
 
 void TargetARM32::lowerSwitch(const InstSwitch *Inst) {
   // This implements the most naive possible lowering.
   // cmp a,val[0]; jeq label[0]; cmp a,val[1]; jeq label[1]; ... jmp default
   Operand *Src0 = Inst->getComparison();
   SizeT NumCases = Inst->getNumCases();
   if (Src0->getType() == IceType_i64) {
     Src0 = legalizeUndef(Src0);
     Variable *Src0Lo = legalizeToReg(loOperand(Src0));
     Variable *Src0Hi = legalizeToReg(hiOperand(Src0));
@@ skipping 76 matching lines @@
         }
       }
     }
   }
 
   // Go through the various types of operands: OperandARM32Mem,
   // OperandARM32Flex, Constant, and Variable. Given the above assertion, if
   // type of operand is not legal (e.g., OperandARM32Mem and !Legal_Mem), we
   // can always copy to a register.
   if (auto *Mem = llvm::dyn_cast<OperandARM32Mem>(From)) {
-    static const struct {
-      bool CanHaveOffset;
-      bool CanHaveIndex;
-    } MemTraits[] = {
-#define X(tag, elementty, int_width, vec_width, sbits, ubits, rraddr)          \
-  { (ubits) > 0, rraddr }                                                      \
-  ,
-        ICETYPEARM32_TABLE
-#undef X
-    };
     // Before doing anything with a Mem operand, we need to ensure that the
     // Base and Index components are in physical registers.
     Variable *Base = Mem->getBase();
     Variable *Index = Mem->getIndex();
     ConstantInteger32 *Offset = Mem->getOffset();
     assert(Index == nullptr || Offset == nullptr);
     Variable *RegBase = nullptr;
     Variable *RegIndex = nullptr;
-    if (Base) {
-      RegBase = legalizeToReg(Base);
-    }
+    assert(Base);
+    RegBase = legalizeToReg(Base);
+    bool InvalidImm = false;
+    assert(Ty < MemTraitsSize);
     if (Index) {
+      assert(Offset == nullptr);
+      assert(MemTraits[Ty].CanHaveIndex);
       RegIndex = legalizeToReg(Index);
-      if (!MemTraits[Ty].CanHaveIndex) {
-        Variable *T = makeReg(IceType_i32, getReservedTmpReg());
-        _add(T, RegBase, RegIndex);
-        RegBase = T;
-        RegIndex = nullptr;
-      }
     }
     if (Offset && Offset->getValue() != 0) {
-      static constexpr bool SignExt = false;
-      if (!MemTraits[Ty].CanHaveOffset ||
-          !OperandARM32Mem::canHoldOffset(Ty, SignExt, Offset->getValue())) {
-        Variable *T = legalizeToReg(Offset, getReservedTmpReg());
-        _add(T, T, RegBase);
-        RegBase = T;
-        Offset = llvm::cast<ConstantInteger32>(Ctx->getConstantInt32(0));
+      assert(Index == nullptr);
+      static constexpr bool ZeroExt = false;
+      assert(MemTraits[Ty].CanHaveImm);
+      if (!OperandARM32Mem::canHoldOffset(Ty, ZeroExt, Offset->getValue())) {
+        assert(RegBase->hasReg() &&

[Jim Stichnoth, 2015/11/08 20:05:51]

Two separate asserts for better precision when it fails.

[John, 2015/11/09 22:42:24]

Done.

+               RegBase->getRegNum() == (int)getFrameOrStackReg());
+        // We are a bit more lenient with invalid immediate when accessing the
+        // stack here, and then rely on legalizeStackSlots() to fix things as
+        // appropriate.
+        InvalidImm = true;
       }
     }
 
     // Create a new operand if there was a change.
     if (Base != RegBase || Index != RegIndex) {
       // There is only a reg +/- reg or reg + imm form.
       // Figure out which to re-create.
-      if (RegBase && RegIndex) {
+      if (RegIndex) {
         Mem = OperandARM32Mem::create(Func, Ty, RegBase, RegIndex,
                                       Mem->getShiftOp(), Mem->getShiftAmt(),
                                       Mem->getAddrMode());
       } else {
         Mem = OperandARM32Mem::create(Func, Ty, RegBase, Offset,
                                       Mem->getAddrMode());
       }
     }
     if (Allowed & Legal_Mem) {
       From = Mem;
     } else {
       Variable *Reg = makeReg(Ty, RegNum);
-      _ldr(Reg, Mem);
+      if (InvalidImm) {
+        // If Mem has an invalid immediate, we legalize it to a Reg using mov
+        // instead of ldr because legalizeStackSlots() will later kick in and
+        // fix the immediate for us.
+        _mov(Reg, Mem);
+      } else {
+        _ldr(Reg, Mem);
+      }
+
       From = Reg;
     }
     return From;
   }
 
   if (auto *Flex = llvm::dyn_cast<OperandARM32Flex>(From)) {
     if (!(Allowed & Legal_Flex)) {
       if (auto *FlexReg = llvm::dyn_cast<OperandARM32FlexReg>(Flex)) {
         if (FlexReg->getShiftOp() == OperandARM32::kNoShift) {
           From = FlexReg->getReg();
@@ skipping 52 matching lines @@
       Variable *Reg = makeReg(Ty, RegNum);
       _movw(Reg, C);
       _movt(Reg, C);
       return Reg;
     } else {
       assert(isScalarFloatingType(Ty));
       // Load floats/doubles from literal pool.
       // TODO(jvoung): Allow certain immediates to be encoded directly in an
       // operand. See Table A7-18 of the ARM manual: "Floating-point modified
       // immediate constants". Or, for 32-bit floating point numbers, just
-      // encode the raw bits into a movw/movt pair to GPR, and vmov to an SREG,
+      // encode the raw bits into a movw/movt pair to GPR, and vmov to an SREG
       // instead of using a movw/movt pair to get the const-pool address then
       // loading to SREG.
       std::string Buffer;
       llvm::raw_string_ostream StrBuf(Buffer);
       llvm::cast<Constant>(From)->emitPoolLabel(StrBuf, Ctx);
       llvm::cast<Constant>(From)->setShouldBePooled(true);
       Constant *Offset = Ctx->getConstantSym(0, StrBuf.str(), true);
       Variable *BaseReg = makeReg(getPointerType());
       _movw(BaseReg, Offset);
       _movt(BaseReg, Offset);
@@ skipping 49 matching lines @@
 }
 
 OperandARM32Mem *TargetARM32::formMemoryOperand(Operand *Operand, Type Ty) {
   OperandARM32Mem *Mem = llvm::dyn_cast<OperandARM32Mem>(Operand);
   // It may be the case that address mode optimization already creates an
   // OperandARM32Mem, so in that case it wouldn't need another level of
   // transformation.
   if (Mem) {
     return llvm::cast<OperandARM32Mem>(legalize(Mem));
   }
-  // If we didn't do address mode optimization, then we only have a base/offset
-  // to work with. ARM always requires a base register, so just use that to
-  // hold the operand.
+  // If we didn't do address mode optimization, then we only have a
+  // base/offset to work with. ARM always requires a base register, so
+  // just use that to hold the operand.
   Variable *Base = legalizeToReg(Operand);
   return OperandARM32Mem::create(
       Func, Ty, Base,
       llvm::cast<ConstantInteger32>(Ctx->getConstantZero(IceType_i32)));
 }
 
 Variable64On32 *TargetARM32::makeI64RegPair() {
   Variable64On32 *Reg =
       llvm::cast<Variable64On32>(Func->makeVariable(IceType_i64));
   Reg->setMustHaveReg();
@@ skipping 380 matching lines @@
   // 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";
 }
 
 llvm::SmallBitVector TargetARM32::TypeToRegisterSet[IceType_NUM];
 llvm::SmallBitVector TargetARM32::RegisterAliases[RegARM32::Reg_NUM];
 llvm::SmallBitVector TargetARM32::ScratchRegs;
 
 } // end of namespace Ice