Subzero: Catch addition patterns for Index in Address Optimizer

src/IceTargetLoweringX86BaseImpl.h

 //===- subzero/src/IceTargetLoweringX86BaseImpl.h - x86 lowering -*- C++ -*-==//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 5052 matching lines @@
 
   inline const Inst *matchAssign(Variable **Var,
                                  ConstantRelocatable **Relocatable,
                                  int32_t *Offset);
 
   inline const Inst *matchCombinedBaseIndex(Variable **Base, Variable **Index,
                                             uint16_t *Shift);
 
   inline const Inst *matchShiftedIndex(Variable **Index, uint16_t *Shift);
 
-  inline const Inst *matchOffsetBase(Variable **Base,
-                                     ConstantRelocatable **Relocatable,
-                                     int32_t *Offset);
+  inline const Inst *matchOffsetIndexOrBase(Variable **IndexOrBase,
+                                            const uint16_t Shift,
+                                            ConstantRelocatable **Relocatable,
+                                            int32_t *Offset);
 
 private:
   const Cfg *const Func;
   const VariablesMetadata *const VMetadata;
 
   static bool isAdd(const Inst *Instr) {
     if (auto *Arith = llvm::dyn_cast_or_null<const InstArithmetic>(Instr)) {
       return (Arith->getOp() == InstArithmetic::Add);
     }
     return false;
@@ skipping 163 matching lines @@
             return IndexInst;
           }
         }
         }
       }
     }
   }
   return nullptr;
 }
 
-const Inst *AddressOptimizer::matchOffsetBase(Variable **Base,
-                                              ConstantRelocatable **Relocatable,
-                                              int32_t *Offset) {
+const Inst *AddressOptimizer::matchOffsetIndexOrBase(
+    Variable **IndexOrBase, const uint16_t Shift,
+    ConstantRelocatable **Relocatable, int32_t *Offset) {
   // 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) {
+  // Index is Index=Var+Const ==>
+  //   set Index=Var, Offset+=(Const<<Shift)
+  // Index is Index=Const+Var ==>
+  //   set Index=Var, Offset+=(Const<<Shift)
+  // Index is Index=Var-Const ==>
+  //   set Index=Var, Offset-=(Const<<Shift)
+
+  if (*IndexOrBase == nullptr) {
     return nullptr;
   }
-  const Inst *BaseInst = VMetadata->getSingleDefinition(*Base);
-  if (BaseInst == nullptr) {
+  const Inst *Definition = VMetadata->getSingleDefinition(*IndexOrBase);
+  if (Definition == nullptr) {
     return nullptr;
   }
-  assert(!VMetadata->isMultiDef(*Base));
-  if (auto *ArithInst = llvm::dyn_cast<const InstArithmetic>(BaseInst)) {
+  assert(!VMetadata->isMultiDef(*IndexOrBase));
+  if (auto *ArithInst = llvm::dyn_cast<const InstArithmetic>(Definition)) {
     if (ArithInst->getOp() != InstArithmetic::Add &&
         ArithInst->getOp() != InstArithmetic::Sub)
       return nullptr;
     bool IsAdd = ArithInst->getOp() == 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);
     auto *Reloc0 = llvm::dyn_cast<ConstantRelocatable>(Src0);
     auto *Reloc1 = llvm::dyn_cast<ConstantRelocatable>(Src1);
-    Variable *NewBase = nullptr;
-    int32_t NewOffset = *Offset;
+    Variable *NewIndexOrBase = nullptr;
+    int32_t NewOffset = 0;
     ConstantRelocatable *NewRelocatable = *Relocatable;
     if (Var0 && Var1)
       // TODO(sehr): merge base/index splitting into here.
       return nullptr;
     if (!IsAdd && Var1)
       return nullptr;
     if (Var0)
-      NewBase = Var0;
+      NewIndexOrBase = Var0;
     else if (Var1)
-      NewBase = Var1;
+      NewIndexOrBase = Var1;
     // Don't know how to add/subtract two relocatables.
     if ((*Relocatable && (Reloc0 || Reloc1)) || (Reloc0 && Reloc1))
       return nullptr;
     // Don't know how to subtract a relocatable.
     if (!IsAdd && Reloc1)
       return nullptr;
     // Incorporate ConstantRelocatables.
     if (Reloc0)
       NewRelocatable = Reloc0;
     else if (Reloc1)
       NewRelocatable = Reloc1;
     // Compute the updated constant offset.
     if (Const0) {
       const int32_t MoreOffset =
           IsAdd ? Const0->getValue() : -Const0->getValue();
-      if (Utils::WouldOverflowAdd(NewOffset, MoreOffset))
+      if (Utils::WouldOverflowAdd(*Offset + NewOffset, MoreOffset))
         return nullptr;
       NewOffset += MoreOffset;
     }
     if (Const1) {
       const int32_t MoreOffset =
           IsAdd ? Const1->getValue() : -Const1->getValue();
-      if (Utils::WouldOverflowAdd(NewOffset, MoreOffset))
+      if (Utils::WouldOverflowAdd(*Offset + NewOffset, MoreOffset))
         return nullptr;
       NewOffset += MoreOffset;
     }
-    *Base = NewBase;
-    *Offset = NewOffset;
+    if (Utils::WouldOverflowAdd(*Offset, NewOffset << Shift))
+        return nullptr;
+    *IndexOrBase = NewIndexOrBase;
+    *Offset += (NewOffset << Shift);
+    // Shift is always zero if this is called with the base
     *Relocatable = NewRelocatable;
-    return BaseInst;
+    return Definition;
   }
   return nullptr;
 }
 
 template <typename TypeTraits>
 typename TargetX86Base<TypeTraits>::X86OperandMem *
 TargetX86Base<TypeTraits>::computeAddressOpt(const Inst *Instr, Type MemType,
                                              Operand *Addr) {
   Func->resetCurrentNode();
   if (Func->isVerbose(IceV_AddrOpt)) {
@@ skipping 114 matching lines @@
       if (NewAddr.Shift == 0 &&
           (Reason = AddrOpt.matchShiftedIndex(&NewAddr.Base, &NewAddr.Shift))) {
         std::swap(NewAddr.Base, NewAddr.Index);
         continue;
       }
     }
 
     // Update Offset to reflect additions/subtractions with constants and
     // relocatables.
     // TODO: consider overflow issues with respect to Offset.
-    if (!Skip.OffsetFromBase &&
-        (Reason = AddrOpt.matchOffsetBase(&NewAddr.Base, &NewAddr.Relocatable,
-                                          &NewAddr.Offset))) {
+    if (!Skip.OffsetFromBase && (Reason = AddrOpt.matchOffsetIndexOrBase(
+                                     &NewAddr.Base, /*Shift =*/0,
+                                     &NewAddr.Relocatable, &NewAddr.Offset))) {
       SkipLastFolding = &Skip.OffsetFromBase;
       continue;
     }
-    if (NewAddr.Shift == 0 && !Skip.OffsetFromIndex &&
-        (Reason = AddrOpt.matchOffsetBase(&NewAddr.Index, &NewAddr.Relocatable,
-                                          &NewAddr.Offset))) {
+    if (!Skip.OffsetFromIndex && (Reason = AddrOpt.matchOffsetIndexOrBase(
+                                      &NewAddr.Index, NewAddr.Shift,
+                                      &NewAddr.Relocatable, &NewAddr.Offset))) {
       SkipLastFolding = &Skip.OffsetFromIndex;
       continue;
     }
 
-    // TODO(sehr, stichnot): Handle updates of Index with Shift != 0.
-    // Index is Index=Var+Const ==>
-    //   set Index=Var, Offset+=(Const<<Shift)
-    // Index is Index=Const+Var ==>
-    //   set Index=Var, Offset+=(Const<<Shift)
-    // Index is Index=Var-Const ==>
-    //   set Index=Var, Offset-=(Const<<Shift)
     break;
   } while (Reason);
 
   if (!AddressWasOptimized) {
     return nullptr;
   }
 
   // Undo any addition of RebasePtr.  It will be added back when the mem
   // operand is sandboxed.
   if (NewAddr.Base == RebasePtr) {
@@ skipping 2477 matching lines @@
         emitGlobal(*Var, SectionSuffix);
       }
     }
   } break;
   }
 }
 } // end of namespace X86NAMESPACE
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICETARGETLOWERINGX86BASEIMPL_H