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

src/IceTargetLoweringX86BaseImpl.h

Index: src/IceTargetLoweringX86BaseImpl.h
diff --git a/src/IceTargetLoweringX86BaseImpl.h b/src/IceTargetLoweringX86BaseImpl.h
index 49c929b8a5983393e4ddf02cc910c100cb5c6951..ec2487112d65f9f460e768be4fca53ae4f7d898b 100644
--- a/src/IceTargetLoweringX86BaseImpl.h
+++ b/src/IceTargetLoweringX86BaseImpl.h
@@ -5270,6 +5270,9 @@ const Inst *AddressOptimizer::matchOffsetIndexOrBase(
   //   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;
@@ -5281,9 +5284,10 @@ const Inst *AddressOptimizer::matchOffsetIndexOrBase(
   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);
@@ -5292,6 +5296,57 @@ const Inst *AddressOptimizer::matchOffsetIndexOrBase(
     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;
@@ -5331,7 +5386,7 @@ const Inst *AddressOptimizer::matchOffsetIndexOrBase(
       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