[DAG] Reassociate Add with Or

[dmgreen]

Summary

We already have reassociation code for Adds and Ors separately in DAG combiner, this adds it for the combination of the two where Ors act like Adds. It reassociates (add (or (x, c), y) -> (add (add (x, y), c)) where we know that the Ors operands have no common bits set, and the Or has one use.

[RKSimon]

Makes sense to me - adding some Hexagon + SystemZ reviewer coverage

[uweigand]

Makes sense to me as well. The SystemZ changes are fine.

[spatel]

LGTM.
I'm not sure if we have x86 tests that mimic the ARM diffs here, but I tried those locally, and I see no difference (probably because we have all of those patterns covered in pre-ISEL or ISEL logic that forms LEA).

[dmgreen]

Thanks

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitADDLike(SDNode *N) {
 
   if (SDValue NewSel = foldBinOpIntoSelect(N))
     return NewSel;
 
   // reassociate add
   if (!reassociationCanBreakAddressingModePattern(ISD::ADD, DL, N0, N1)) {
     if (SDValue RADD = reassociateOps(ISD::ADD, DL, N0, N1, N->getFlags()))
       return RADD;
+
+    // Reassociate (add (or x, c), y) -> (add add(x, y), c)) if (or x, c) is
+    // equivalent to (add x, c).
+    auto ReassociateAddOr = [&](SDValue N0, SDValue N1) {
+      if (N0.getOpcode() == ISD::OR && N0.hasOneUse() &&
+          isConstantOrConstantVector(N0.getOperand(1), /* NoOpaque */ true) &&
+          DAG.haveNoCommonBitsSet(N0.getOperand(0), N0.getOperand(1))) {
+        return DAG.getNode(ISD::ADD, DL, VT,
+                           DAG.getNode(ISD::ADD, DL, VT, N1, N0.getOperand(0)),
+                           N0.getOperand(1));
+      }
+      return SDValue();
+    };
+    if (SDValue Add = ReassociateAddOr(N0, N1))
+      return Add;
+    if (SDValue Add = ReassociateAddOr(N1, N0))
+      return Add;
   }
   // fold ((0-A) + B) -> B-A
   if (N0.getOpcode() == ISD::SUB && isNullOrNullSplat(N0.getOperand(0)))
     return DAG.getNode(ISD::SUB, DL, VT, N1, N0.getOperand(1));
 
   // fold (A + (0-B)) -> A-B
   if (N1.getOpcode() == ISD::SUB && isNullOrNullSplat(N1.getOperand(0)))
     return DAG.getNode(ISD::SUB, DL, VT, N0, N1.getOperand(1));

llvm/test/CodeGen/ARM/add-like-or.ll

; CHECK-A-NEXT:    bx lr
   %res = or i32 %int, 854
   ret i32 %res
 }
 
 define i32 @oradd(i32 %i, i32 %y) {
 ; CHECK-T1-LABEL: oradd:
 ; CHECK-T1:       @ %bb.0: @ %entry
 ; CHECK-T1-NEXT:    lsls r0, r0, #1
+; CHECK-T1-NEXT:    adds r0, r1, r0
 ; CHECK-T1-NEXT:    adds r0, r0, #1
-; CHECK-T1-NEXT:    adds r0, r0, r1
 ; CHECK-T1-NEXT:    bx lr
 ;
 ; CHECK-T2-LABEL: oradd:
 ; CHECK-T2:       @ %bb.0: @ %entry
-; CHECK-T2-NEXT:    lsls r0, r0, #1
+; CHECK-T2-NEXT:    add.w r0, r1, r0, lsl #1
 ; CHECK-T2-NEXT:    adds r0, #1
-; CHECK-T2-NEXT:    add r0, r1
 ; CHECK-T2-NEXT:    bx lr
 ;
 ; CHECK-A-LABEL: oradd:
 ; CHECK-A:       @ %bb.0: @ %entry
-; CHECK-A-NEXT:    mov r2, #1
-; CHECK-A-NEXT:    orr r0, r2, r0, lsl #1
-; CHECK-A-NEXT:    add r0, r0, r1
+; CHECK-A-NEXT:    add r0, r1, r0, lsl #1
+; CHECK-A-NEXT:    add r0, r0, #1
 ; CHECK-A-NEXT:    bx lr
 entry:
   %mul = shl i32 %i, 1
   %or = or i32 %mul, 1
   %add = add i32 %or, %y
   ret i32 %add
 }
 
 define i32 @orgep(i32 %i, i32* %x, i32* %y) {
 ; CHECK-T1-LABEL: orgep:
 ; CHECK-T1:       @ %bb.0: @ %entry
 ; CHECK-T1-NEXT:    lsls r0, r0, #3
-; CHECK-T1-NEXT:    adds r0, r0, #4
-; CHECK-T1-NEXT:    ldr r0, [r1, r0]
+; CHECK-T1-NEXT:    adds r0, r1, r0
+; CHECK-T1-NEXT:    ldr r0, [r0, #4]
 ; CHECK-T1-NEXT:    bx lr
 ;
 ; CHECK-T2-LABEL: orgep:
 ; CHECK-T2:       @ %bb.0: @ %entry
-; CHECK-T2-NEXT:    lsls r0, r0, #3
-; CHECK-T2-NEXT:    adds r0, #4
-; CHECK-T2-NEXT:    ldr r0, [r1, r0]
+; CHECK-T2-NEXT:    add.w r0, r1, r0, lsl #3
+; CHECK-T2-NEXT:    ldr r0, [r0, #4]
 ; CHECK-T2-NEXT:    bx lr
 ;
 ; CHECK-A-LABEL: orgep:
 ; CHECK-A:       @ %bb.0: @ %entry
-; CHECK-A-NEXT:    mov r2, #4
-; CHECK-A-NEXT:    orr r0, r2, r0, lsl #3
-; CHECK-A-NEXT:    ldr r0, [r1, r0]
+; CHECK-A-NEXT:    add r0, r1, r0, lsl #3
+; CHECK-A-NEXT:    ldr r0, [r0, #4]
 ; CHECK-A-NEXT:    bx lr
 entry:
   %mul = shl i32 %i, 1
   %add = or i32 %mul, 1
   %arrayidx = getelementptr inbounds i32, i32* %x, i32 %add
   %0 = load i32, i32* %arrayidx, align 8
   ret i32 %0
 }
 
 define i32 @orgeps(i32 %i, i32* %x, i32* %y) {
 ; CHECK-T1-LABEL: orgeps:
 ; CHECK-T1:       @ %bb.0: @ %entry
 ; CHECK-T1-NEXT:    lsls r0, r0, #3
-; CHECK-T1-NEXT:    adds r2, r0, #4
-; CHECK-T1-NEXT:    ldr r2, [r1, r2]
-; CHECK-T1-NEXT:    adds r0, r0, r1
+; CHECK-T1-NEXT:    adds r0, r1, r0
+; CHECK-T1-NEXT:    ldr r1, [r0, #4]
 ; CHECK-T1-NEXT:    ldr r0, [r0, #8]
-; CHECK-T1-NEXT:    adds r0, r0, r2
+; CHECK-T1-NEXT:    adds r0, r0, r1
 ; CHECK-T1-NEXT:    bx lr
 ;
 ; CHECK-T2-LABEL: orgeps:
 ; CHECK-T2:       @ %bb.0: @ %entry
-; CHECK-T2-NEXT:    lsls r2, r0, #3
 ; CHECK-T2-NEXT:    add.w r0, r1, r0, lsl #3
-; CHECK-T2-NEXT:    adds r2, #4
-; CHECK-T2-NEXT:    ldr r0, [r0, #8]
-; CHECK-T2-NEXT:    ldr r2, [r1, r2]
-; CHECK-T2-NEXT:    add r0, r2
+; CHECK-T2-NEXT:    ldrd r0, r1, [r0, #4]
+; CHECK-T2-NEXT:    add r0, r1
 ; CHECK-T2-NEXT:    bx lr
 ;
 ; CHECK-A-LABEL: orgeps:
 ; CHECK-A:       @ %bb.0: @ %entry
-; CHECK-A-NEXT:    mov r2, #4
-; CHECK-A-NEXT:    orr r2, r2, r0, lsl #3
 ; CHECK-A-NEXT:    add r0, r1, r0, lsl #3
-; CHECK-A-NEXT:    ldr r2, [r1, r2]
-; CHECK-A-NEXT:    ldr r0, [r0, #8]
-; CHECK-A-NEXT:    add r0, r0, r2
+; CHECK-A-NEXT:    ldrd r0, r1, [r0, #4]
+; CHECK-A-NEXT:    add r0, r1, r0
 ; CHECK-A-NEXT:    bx lr
 entry:
   %mul = shl i32 %i, 1
   %add = or i32 %mul, 1
   %arrayidx = getelementptr inbounds i32, i32* %x, i32 %add
   %0 = load i32, i32* %arrayidx, align 8
   %add2 = add i32 %mul, 2
   %arrayidx3 = getelementptr inbounds i32, i32* %x, i32 %add2

llvm/test/CodeGen/Hexagon/isel-global-offset-alignment.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -march=hexagon < %s | FileCheck %s
 
 ; This should compile without errors, and the offsets with respect to the
 ; beginning of the global "array" don't need to be multiples of 8.
 
 target datalayout = "e-m:e-p:32:32:32-a:0-n16:32-i64:64:64-i32:32:32-i16:16:16-i1:8:8-f32:32:32-f64:64:64-v32:32:32-v64:64:64-v512:512:512-v1024:1024:1024-v2048:2048:2048"
 target triple = "hexagon"
 
 @array = external global [1000000 x i16], align 8
 
 define void @fred(i1 %x) #0 {
 ; CHECK-LABEL: fred:
 ; CHECK:       // %bb.0: // %b0
 ; CHECK-NEXT:    {
 ; CHECK-NEXT:     p0 = tstbit(r0,#0)
+; CHECK-NEXT:     if (!p0.new) r2 = #1024
+; CHECK-NEXT:     if (p0.new) r2 = #0
 ; CHECK-NEXT:     r5:4 = combine(#0,#0)
-; CHECK-NEXT:     if (p0.new) r2 = #2
-; CHECK-NEXT:     if (!p0.new) r2 = #1026
 ; CHECK-NEXT:    }
 ; CHECK-NEXT:    {
-; CHECK-NEXT:     memd(r2+##array+182) = r5:4
-; CHECK-NEXT:     memd(r2+##array+174) = r5:4
+; CHECK-NEXT:     memd(r2+##array+184) = r5:4
+; CHECK-NEXT:     memd(r2+##array+176) = r5:4
 ; CHECK-NEXT:    }
 ; CHECK-NEXT:    {
 ; CHECK-NEXT:     jumpr r31
 ; CHECK-NEXT:    }
 b0:
   br i1 %x, label %b3, label %b1
 
 b1:                                               ; preds = %b0

llvm/test/CodeGen/SystemZ/addr-01.ll

; CHECK-NEXT:    br %r14
   ret void
 }
 
 ; An address with an index and a displacement added using OR.
 define void @f6(i64 %addr, i64 %index) {
 ; CHECK-LABEL: f6:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    nill %r2, 65528
-; CHECK-NEXT:    lb %r0, 6(%r3,%r2)
+; CHECK-NEXT:    lb %r0, 6(%r2,%r3)
 ; CHECK-NEXT:    br %r14
   %aligned = and i64 %addr, -8
   %or = or i64 %aligned, 6
   %add = add i64 %or, %index
   %ptr = inttoptr i64 %add to i8 *
   %a = load volatile i8, i8 *%ptr
   ret void
 }

llvm/test/CodeGen/SystemZ/addr-02.ll

; CHECK-NEXT:    br %r14
   ret void
 }
 
 ; An address with an index and a displacement added using OR.
 define void @f6(i64 %addr, i64 %index, i8 **%dst) {
 ; CHECK-LABEL: f6:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    nill %r2, 65528
-; CHECK-NEXT:    lb %r0, 6(%r3,%r2)
-; CHECK-NEXT:    la %r0, 6(%r3,%r2)
+; CHECK-NEXT:    lb %r0, 6(%r2,%r3)
+; CHECK-NEXT:    la %r0, 6(%r2,%r3)
 ; CHECK-NEXT:    stg %r0, 0(%r4)
 ; CHECK-NEXT:    br %r14
   %aligned = and i64 %addr, -8
   %or = or i64 %aligned, 6
   %add = add i64 %or, %index
   %ptr = inttoptr i64 %add to i8 *
   %a = load volatile i8, i8 *%ptr
   store volatile i8 *%ptr, i8 **%dst