[SubZero] Implement address optimization for MIPS

src/IceTargetLoweringMIPS32.cpp

Index: src/IceTargetLoweringMIPS32.cpp
diff --git a/src/IceTargetLoweringMIPS32.cpp b/src/IceTargetLoweringMIPS32.cpp
index 7bdf723d3796b4da898c12e1f0a54380a7fbff89..60cf5a3877f39a027d7e51d2b53cbd8997ab528c 100644
--- a/src/IceTargetLoweringMIPS32.cpp
+++ b/src/IceTargetLoweringMIPS32.cpp
@@ -2310,7 +2310,237 @@ void TargetMIPS32::lowerLoad(const InstLoad *Instr) {
   lowerAssign(Assign);
 }
 
-void TargetMIPS32::doAddressOptLoad() { UnimplementedError(getFlags()); }
+namespace {
+void dumpAddressOpt(const Cfg *Func, const Variable *Base, int32_t Offset,
+                    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 << ", Offset=" << Offset << "\n";
+}
+
+bool matchAssign(const VariablesMetadata *VMetadata, const CfgNode *UseNode,
+                 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;
+
+  const CfgNode *DefNode = VMetadata->getSingleDefinitionNode(*Var);
+  const bool IsSingleBB = (DefNode->getIndex() == UseNode->getIndex());

[Jim Stichnoth, 2016/09/09 00:08:22]

Why are you adding this single-block condition?

I'm guessing it's because of this in the ARM code:

  // TODO: ensure SrcVar stays single-BB

which was probably just copied over from the original x86 implementation, very
very early in the Subzero design/implementation.

As I recall, the idea was that maybe we should only pull in source variables
from the same basic block, as a heuristic toward controlling register pressure. 
However, in all our analysis of the spec2k benchmarks, we never really
encountered a problem with this, so the TODO was never addressed.

Now, I can't say for sure that there is no register pressure problem from this,
because those kinds of global register allocation effects are hard to discover
just by staring at the code.

So if my guess is correct, I think we should remove this condition for now, to
make it more similar to the other targets, and consider adding it as a separate
CL (perhaps a CL that does this for all targets).  

[jaydeep.patil, 2016/09/13 06:42:25]

Done.

+  Operand *SrcOp = VarAssign->getSrc(0);
+  bool Optimized = false;
+  if (auto *SrcVar = llvm::dyn_cast<Variable>(SrcOp)) {
+    // Ensure SrcVar stays single-BB
+    if (!VMetadata->isMultiDef(SrcVar) || IsSingleBB == true) {
+      Optimized = true;
+      *Var = SrcVar;
+    } else if (auto *Const = llvm::dyn_cast<ConstantInteger32>(SrcOp)) {
+      int32_t MoreOffset = Const->getValue();
+      int32_t NewOffset = MoreOffset + *Offset;
+      if (Utils::WouldOverflowAdd(*Offset, MoreOffset))
+        return false;
+      *Var = nullptr;
+      *Offset += NewOffset;
+      Optimized = true;
+    }
+  }
+
+  if (Optimized) {
+    *Reason = VarAssign;
+  }
+
+  return Optimized;
+}
+
+bool isAddOrSub(const Inst *Instr, InstArithmetic::OpKind *Kind) {
+  if (const auto *Arith = llvm::dyn_cast<InstArithmetic>(Instr)) {
+    switch (Arith->getOp()) {
+    default:
+      return false;
+    case InstArithmetic::Add:
+    case InstArithmetic::Sub:
+      *Kind = Arith->getOp();
+      return true;
+    }
+  }
+  return false;
+}
+
+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
+
+OperandMIPS32Mem *TargetMIPS32::formAddressingMode(Type Ty, Cfg *Func,
+                                                   const CfgNode *LdStNode,
+                                                   const Inst *LdSt,
+                                                   Operand *Base) {
+  assert(Base != nullptr);
+  int32_t OffsetImm = 0;
+
+  Func->resetCurrentNode();
+  if (Func->isVerbose(IceV_AddrOpt)) {
+    OstreamLocker _(Func->getContext());
+    Ostream &Str = Func->getContext()->getStrDump();
+    Str << "\nAddress mode formation:\t";
+    LdSt->dumpDecorated(Func);
+  }
+
+  if (isVectorType(Ty)) {
+    UnimplementedError(getFlags());
+    return nullptr;
+  }
+
+  auto *BaseVar = llvm::dyn_cast<Variable>(Base);
+  if (BaseVar == nullptr)
+    return nullptr;
+
+  const VariablesMetadata *VMetadata = Func->getVMetadata();
+  const Inst *Reason = nullptr;
+
+  do {
+    if (Reason != nullptr) {
+      dumpAddressOpt(Func, BaseVar, OffsetImm, Reason);
+      Reason = nullptr;
+    }
+
+    if (matchAssign(VMetadata, LdStNode, &BaseVar, &OffsetImm, &Reason)) {
+      continue;
+    }
+
+    if (matchOffsetBase(VMetadata, &BaseVar, &OffsetImm, &Reason)) {
+      continue;
+    }
+  } while (Reason);
+
+  if (BaseVar == nullptr) {
+    // We need base register rather than just OffsetImm. Move the OffsetImm to
+    // BaseVar and form 0(BaseVar) addressing.
+    const Type PointerType = getPointerType();
+    BaseVar = makeReg(PointerType);
+    Context.insert<InstAssign>(BaseVar, Ctx->getConstantInt32(OffsetImm));
+    OffsetImm = 0;
+  } else if (OffsetImm != 0) {
+    // If the OffsetImm is more than signed 16-bit value then add it in the
+    // BaseVar and form 0(BaseVar) addressing.
+    const int32_t PositiveOffset = OffsetImm > 0 ? OffsetImm : -OffsetImm;
+    const InstArithmetic::OpKind Op =
+        OffsetImm > 0 ? InstArithmetic::Add : InstArithmetic::Sub;
+    constexpr bool ZeroExt = false;
+    if (!OperandMIPS32Mem::canHoldOffset(Ty, ZeroExt, OffsetImm)) {
+      const Type PointerType = getPointerType();
+      Variable *T = makeReg(PointerType);
+      Context.insert<InstArithmetic>(Op, T, BaseVar,
+                                     Ctx->getConstantInt32(PositiveOffset));
+      BaseVar = T;
+      OffsetImm = 0;
+    }
+  }
+
+  assert(BaseVar != nullptr);
+  assert(OffsetImm < 0 ? (-OffsetImm & 0x0000ffff) == -OffsetImm
+                       : (OffsetImm & 0x0000ffff) == OffsetImm);
+
+  return OperandMIPS32Mem::create(
+      Func, Ty, BaseVar,
+      llvm::cast<ConstantInteger32>(Ctx->getConstantInt32(OffsetImm)));
+}
+
+void TargetMIPS32::doAddressOptLoad() {
+  Inst *Instr = iteratorToInst(Context.getCur());
+  assert(llvm::isa<InstLoad>(Instr));
+  const CfgNode *LoadNode = Context.getNode();
+  Variable *Dest = Instr->getDest();
+  Operand *Addr = Instr->getSrc(0);
+  if (OperandMIPS32Mem *Mem =
+          formAddressingMode(Dest->getType(), Func, LoadNode, Instr, Addr)) {
+    Instr->setDeleted();
+    Context.insert<InstLoad>(Dest, Mem);
+  }
+}
 
 void TargetMIPS32::randomlyInsertNop(float Probability,
                                      RandomNumberGenerator &RNG) {
@@ -2380,7 +2610,18 @@ void TargetMIPS32::lowerStore(const InstStore *Instr) {
   }
 }
 
-void TargetMIPS32::doAddressOptStore() { UnimplementedError(getFlags()); }
+void TargetMIPS32::doAddressOptStore() {
+  Inst *Instr = iteratorToInst(Context.getCur());
+  assert(llvm::isa<InstStore>(Instr));
+  const CfgNode *StoreNode = Context.getNode();
+  Operand *Src = Instr->getSrc(0);
+  Operand *Addr = Instr->getSrc(1);
+  if (OperandMIPS32Mem *Mem =
+          formAddressingMode(Src->getType(), Func, StoreNode, Instr, Addr)) {
+    Instr->setDeleted();
+    Context.insert<InstStore>(Src, Mem);
+  }
+}
 
 void TargetMIPS32::lowerSwitch(const InstSwitch *Instr) {
   Operand *Src = Instr->getComparison();