[SubZero] Implement address optimization for MIPS

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 2292 matching lines @@
 void TargetMIPS32::lowerLoad(const InstLoad *Instr) {
   // A Load instruction can be treated the same as an Assign instruction, after
   // the source operand is transformed into an OperandARM32Mem operand.
   Type Ty = Instr->getDest()->getType();
   Operand *Src0 = formMemoryOperand(Instr->getSourceAddress(), Ty);
   Variable *DestLoad = Instr->getDest();
   auto *Assign = InstAssign::create(Func, DestLoad, Src0);
   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) {
   RandomNumberGeneratorWrapper RNGW(RNG);
   if (RNGW.getTrueWithProbability(Probability)) {
     UnimplementedError(getFlags());
   }
 }
 
 void TargetMIPS32::lowerPhi(const InstPhi * /*Instr*/) {
@@ skipping 49 matching lines @@
     Variable *ValueHi = legalizeToReg(hiOperand(Value));
     Variable *ValueLo = legalizeToReg(loOperand(Value));
     _sw(ValueHi, llvm::cast<OperandMIPS32Mem>(hiOperand(NewAddr)));
     _sw(ValueLo, llvm::cast<OperandMIPS32Mem>(loOperand(NewAddr)));
   } else {
     Variable *ValueR = legalizeToReg(Value);
     _sw(ValueR, NewAddr);
   }
 }
 
-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();
   SizeT NumCases = Instr->getNumCases();
   if (Src->getType() == IceType_i64) {
     Src = legalizeUndef(Src);
     Variable *Src0Lo = legalizeToReg(loOperand(Src));
     Variable *Src0Hi = legalizeToReg(hiOperand(Src));
     for (SizeT I = 0; I < NumCases; ++I) {
       Operand *ValueLo = Ctx->getConstantInt32(Instr->getValue(I));
@@ skipping 335 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