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)
+    switch (ArithInst->getOp()) {
+    case InstArithmetic::Add:
+    case InstArithmetic::Sub:
+    case InstArithmetic::Or:
+      break;
+    default:
       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;

[Jim Stichnoth, 2016/06/27 20:33:05]

Use braces around the return statement for consistency.  Generally, I'm OK with:

  if (C)
    A;
  else
    B;

or

  if (C) {
    A;
  } else {
    B;
  }

but not a mismatch of the two styles.

+
+      auto *VarDef =
+          llvm::dyn_cast<InstArithmetic>(VMetadata->getSingleDefinition(Var));
+      if (VarDef == nullptr)
+        return nullptr;
+
+      SizeT ZeroesAvailable = 0;
+      if (VarDef->getOp() == InstArithmetic::Shl) {
+        if (auto *ConstInt =
+                llvm::dyn_cast<ConstantInteger32>(VarDef->getSrc(1))) {
+          ZeroesAvailable = ConstInt->getValue();
+        }
+      } else if (VarDef->getOp() == InstArithmetic::Mul) {
+        SizeT PowerOfTwo = 0;
+        ConstantInteger32 *MultConst =
+            llvm::dyn_cast<ConstantInteger32>(VarDef->getSrc(0));
+        if (llvm::isPowerOf2_32(MultConst->getValue())) {
+          PowerOfTwo += MultConst->getValue();
+        }
+        MultConst = llvm::dyn_cast<ConstantInteger32>(VarDef->getSrc(1));
+        if (llvm::isPowerOf2_32(MultConst->getValue())) {
+          PowerOfTwo += MultConst->getValue();
+        }
+        ZeroesAvailable = llvm::Log2_32(PowerOfTwo) + 1;
+      }
+      SizeT ZeroesNeeded = llvm::Log2_32(Const->getValue()) + 1;
+      if (ZeroesNeeded == 0 || ZeroesNeeded > ZeroesAvailable)
+        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