Treat ORs as ADDs for address optimization if operand has enough zero bits on the right

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 5252 matching lines @@
   // 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
   // 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)
+  // Treat Index=Var Or Const as Index=Var + Const
+  //    when Var = Var' << N and log2(Const) <= N
+  // or when Var = (2^M) * (2^N) and log2(Const) <= (M+N)
 
   if (*IndexOrBase == nullptr) {
     return nullptr;
   }
   const Inst *Definition = VMetadata->getSingleDefinition(*IndexOrBase);
   if (Definition == nullptr) {
     return nullptr;
   }
   assert(!VMetadata->isMultiDef(*IndexOrBase));
   if (auto *ArithInst = llvm::dyn_cast<const InstArithmetic>(Definition)) {
     if (ArithInst->getOp() != InstArithmetic::Add &&
-        ArithInst->getOp() != InstArithmetic::Sub)
+        ArithInst->getOp() != InstArithmetic::Sub &&
+        ArithInst->getOp() != InstArithmetic::Or)

[Jim Stichnoth, 2016/06/22 20:01:14]

Once we're up to testing 3 values, I think this should be turned into a switch
statement.

[manasijm, 2016/06/27 18:04:18]

Done.

       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);
+
+    bool IsAdd = false;
+    if (ArithInst->getOp() == InstArithmetic::Or) {
+      Variable *Var = nullptr;
+      ConstantInteger32 *Const = nullptr;
+      if (Var0 && Const1) {
+        Var = Var0;
+        Const = Const1;
+      } else if (Const0 && Var1) {
+        Var = Var1;
+        Const = Const0;
+      } else
+        return nullptr;
+
+      auto *VarDef =
+          llvm::dyn_cast<InstArithmetic>(VMetadata->getSingleDefinition(Var));
+      if (VarDef == nullptr)
+        return nullptr;
+
+      auto uintLog2 = [](uint32_t x) {

[Jim Stichnoth, 2016/06/22 20:01:13]

Can you just use llvm::Log2_32() or similar?

See src/llvm/include/llvm/Support/MathExtras.h

[manasijm, 2016/06/27 18:04:18]

Done.

+        uint8_t result = 0;
+        if (x > 0) do {result++;} while (x >>= 1);
+        return result;
+      };
+
+      SizeT numZeroes = 0;

[Jim Stichnoth, 2016/06/22 20:01:13]

NumZeroes

[manasijm, 2016/06/27 18:04:18]

Done.

+      if (VarDef->getOp() == InstArithmetic::Shl) {
+        if (auto ConstInt =

[Jim Stichnoth, 2016/06/22 20:01:13]

auto *

[manasijm, 2016/06/27 18:04:18]

Done.

+                llvm::dyn_cast<ConstantInteger32>(VarDef->getSrc(1))) {
+          numZeroes = ConstInt->getValue();
+        }
+      } else if (VarDef->getOp() == InstArithmetic::Mul) {
+        ConstantInteger32 *MultConst = nullptr;

[Jim Stichnoth, 2016/06/22 20:01:13]

Combine this and the next line.

[manasijm, 2016/06/27 18:04:18]

Done.

+        MultConst = llvm::dyn_cast<ConstantInteger32>(VarDef->getSrc(0));
+        if (llvm::isPowerOf2_32(MultConst->getValue())) {
+          numZeroes += uintLog2(MultConst->getValue());
+        }
+        MultConst = llvm::dyn_cast<ConstantInteger32>(VarDef->getSrc(1));
+        if (llvm::isPowerOf2_32(MultConst->getValue())) {
+          numZeroes += uintLog2(MultConst->getValue());
+        }
+      }
+      SizeT LogValue = uintLog2(Const->getValue());
+      if (LogValue == 0 || LogValue > numZeroes)
+        return nullptr;
+
+      IsAdd = true; // treat it as an add if the above conditions hold
+    } else {
+      IsAdd = ArithInst->getOp() == InstArithmetic::Add;
+    }
+
     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)
       NewIndexOrBase = Var0;
@@ skipping 19 matching lines @@
       NewOffset += MoreOffset;
     }
     if (Const1) {
       const int32_t MoreOffset =
           IsAdd ? Const1->getValue() : -Const1->getValue();
       if (Utils::WouldOverflowAdd(*Offset + NewOffset, MoreOffset))
         return nullptr;
       NewOffset += MoreOffset;
     }
     if (Utils::WouldOverflowAdd(*Offset, NewOffset << Shift))
-        return nullptr;
+      return nullptr;
     *IndexOrBase = NewIndexOrBase;
     *Offset += (NewOffset << Shift);
     // Shift is always zero if this is called with the base
     *Relocatable = NewRelocatable;
     return Definition;
   }
   return nullptr;
 }
 
 template <typename TypeTraits>
@@ skipping 2629 matching lines @@
         emitGlobal(*Var, SectionSuffix);
       }
     }
   } break;
   }
 }
 } // end of namespace X86NAMESPACE
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICETARGETLOWERINGX86BASEIMPL_H