[x86] try harder to match bitwise 'or' into an LEA

The motivation for this patch starts with the epic fail example in PR18007:
https://llvm.org/bugs/show_bug.cgi?id=18007

...unfortunately, this patch makes no difference for that case, but it solves some
simpler cases. We'll get there some day. :)

The current 'or' matching code was using computeKnownBits() via 
isBaseWithConstantOffset() -> MaskedValueIsZero(), but that's an unnecessarily limited use. 
We can do more by copying the logic in ValueTracking's haveNoCommonBitsSet(), so we can 
treat the 'or' as if it was an 'add'.

There's a TODO comment here because we should lift the bit-checking logic into a helper
function, so it's not duplicated in DAGCombiner.

An example of the better LEA matching:

leal (%rdi,%rdi), %eax
andl $1, %esi
orl %esi, %eax

Becomes:

andl $1, %esi
leal (%rsi,%rdi,2), %eax

Differential Revision: http://reviews.llvm.org/D13956

llvm-svn: 252515

1 files changed, 21 insertions, 11 deletions

diff --git a/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp b/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
index c5a1093af12..0cbeda91ccc 100644
--- a/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
+++ b/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
@@ -1338,19 +1338,29 @@ bool X86DAGToDAGISel::matchAddressRecursively(SDValue N, X86ISelAddressMode &AM,
       return false;
     break;
 
-  case ISD::OR:
-    // Handle "X | C" as "X + C" iff X is known to have C bits clear.
-    if (CurDAG->isBaseWithConstantOffset(N)) {
-      X86ISelAddressMode Backup = AM;
-      ConstantSDNode *CN = cast<ConstantSDNode>(N.getOperand(1));
-
-      // Start with the LHS as an addr mode.
-      if (!matchAddressRecursively(N.getOperand(0), AM, Depth+1) &&
-          !foldOffsetIntoAddress(CN->getSExtValue(), AM))
+  case ISD::OR: {
+    // TODO: The bit-checking logic should be put into a helper function and
+    // used by DAGCombiner.
+
+    // We want to look through a transform in InstCombine and DAGCombiner that
+    // turns 'add' into 'or', so we can treat this 'or' exactly like an 'add'.
+    APInt LHSZero, LHSOne;
+    APInt RHSZero, RHSOne;
+    CurDAG->computeKnownBits(N.getOperand(0), LHSZero, LHSOne);
+    CurDAG->computeKnownBits(N.getOperand(1), RHSZero, RHSOne);
+
+    // If we know that there are no common bits set by the operands of this
+    // 'or', it is equivalent to an 'add'. For example:
+    // (or (and x, 1), (shl y, 3)) --> (add (and x, 1), (shl y, 3))
+    // An 'lea' can then be used to match the shift (multiply) and add:
+    // and $1, %esi
+    // lea (%rsi, %rdi, 8), %rax
+    if ((LHSZero | RHSZero).isAllOnesValue())
+      if (!matchAdd(N, AM, Depth))
         return false;
-      AM = Backup;
-    }
+
     break;
+  }
 
   case ISD::AND: {
     // Perform some heroic transforms on an and of a constant-count shift