Add DAG combine for shl + add of constants.

[arsenm]

Summary

Do

(shl (add x, c1), c2) -> (add (shl x, c2), c1 << c2)

This is already done for multiplies, but since multiplies
by powers of two are turned into shifts, we also need
to handle it here. This not happening is interfering with folding
some constant offsets into an addressing mode.

This might want checks for isLegalAddImmediate to avoid
transforming an add of a legal immediate with one that isn't.

[arsenm]

Ping

[arsenm]

Ping

[arsenm]

Ping

[andreadb]

Hi Matt,

I have a couple of comments about your patch (see below).

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4146–4157

If I understand correctly, your rule doesn't try to fold the case where C2 is a build_vector of all ConstantSDNode or Undef. Is this intentional?
If so, then why at line 4151 you check for 'isConstantSplatVector'? I am asking this because you specifically check for N1C; however, (unless I misread the code) N1C is not null only if N1 is a ConstantSDNode.

Also, I noticed that the dag combiner already implements a similar (but less poweful) rule in 'visitADD' at around line 1658 (see also function 'combineShlAddConstant'); the rule is:
// fold (add (shl (add x, c1), c2), ) -> (add (add (shl x, c2), c1<<c2), )

I think that your patch would make that rule redundant. I would do an experiment and see if that is true; in case, I suggest to get rid of it (and also the static function 'combineShlAddConstant').

I hope this helps.
Andrea

[arsenm]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4146–4157

It's sort of hard to follow, but N1C is replaced with the constant splat value under the VT.isVector() at the beginning of the function. I've added a test for vectors in the new version to make sure that works.

The combineShlAddConstant transform actually made the opposite change way back in r33361 / 2007 with the weak justification that it "fixes test/CodeGen/ARM/smul.ll" so I assume there isn't actually a real reason to avoid doing this. I've also removed it in the new version.

[arsenm]

Remove redundant transform in visitADD, add more tests

[andreadb]

Hi Matt,
Thanks for the explanation.
The updated patch LGTM. Thanks!

-Andrea

[arsenm]

r217610

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (N1C && N0.getOpcode() == ISD::SRA && N1 == N0.getOperand(1)) {
     unsigned BitSize = VT.getScalarSizeInBits();
     SDValue HiBitsMask =
       DAG.getConstant(APInt::getHighBitsSet(BitSize,
                                             BitSize - N1C->getZExtValue()), VT);
     return DAG.getNode(ISD::AND, SDLoc(N), VT, N0.getOperand(0),
                        HiBitsMask);
   }
 
+  // fold (shl (add x, c1), c2) -> (add (shl x, c2), c1 << c2)
+  // Variant of version done on multiply, except mul by a power of 2 is turned
+  // into a shift.
+  APInt Val;
+  if (N1C && N0.getOpcode() == ISD::ADD && N0.getNode()->hasOneUse() &&
+      (isConstantSplatVector(N0.getOperand(1).getNode(), Val) ||
+       isa<ConstantSDNode>(N0.getOperand(1)))) {
+    SDValue Shl0 = DAG.getNode(ISD::SHL, SDLoc(N0), VT, N0.getOperand(0), N1);
+    SDValue Shl1 = DAG.getNode(ISD::SHL, SDLoc(N1), VT, N0.getOperand(1), N1);
+    return DAG.getNode(ISD::ADD, SDLoc(N), VT, Shl0, Shl1);
+  }
+
   if (N1C) {
     SDValue NewSHL = visitShiftByConstant(N, N1C);
     if (NewSHL.getNode())
       return NewSHL;
   }
 
   return SDValue();
 }

test/CodeGen/AArch64/arm64-shifted-sext.ll

; CHECK: sbfx w0, [[REG]], #4, #12
   %conv = sext i16 %inc to i32
   %shr = ashr i32 %conv, 4
   ret i32 %shr
 }
 
 define i32 @extendedLeftShiftshortTointBy16(i16 signext %a) nounwind readnone ssp {
 entry:
 ; CHECK-LABEL: extendedLeftShiftshortTointBy16:
-; CHECK: add [[REG:w[0-9]+]], w0, #1
-; CHECK: lsl w0, [[REG]], #16
+; CHECK: lsl [[REG:w[0-9]+]], w0, #16
+; CHECK: add w0, [[REG]], #16, lsl #12
   %inc = add i16 %a, 1
   %conv2 = zext i16 %inc to i32
   %shl = shl nuw i32 %conv2, 16
   ret i32 %shl
 }
 
 define i32 @extendedRightShiftshortTointBy16(i16 signext %a) nounwind readnone ssp {
 entry:

test/CodeGen/R600/shl_add_constant.ll

+; RUN: llc -march=r600 -mcpu=SI -verify-machineinstrs < %s | FileCheck -check-prefix=SI %s
+
+declare i32 @llvm.r600.read.tidig.x() #1
+
+; Test with inline immediate
+
+; FUNC-LABEL: @shl_2_add_9_i32
+; SI: V_LSHLREV_B32_e32  [[REG:v[0-9]+]], 2, {{v[0-9]+}}
+; SI: V_ADD_I32_e32 [[RESULT:v[0-9]+]], 36, [[REG]]
+; SI: BUFFER_STORE_DWORD [[RESULT]]
+; SI: S_ENDPGM
+define void @shl_2_add_9_i32(i32 addrspace(1)* %out, i32 addrspace(1)* %in) #0 {
+  %tid.x = tail call i32 @llvm.r600.read.tidig.x() #1
+  %ptr = getelementptr i32 addrspace(1)* %in, i32 %tid.x
+  %val = load i32 addrspace(1)* %ptr, align 4
+  %add = add i32 %val, 9
+  %result = shl i32 %add, 2
+  store i32 %result, i32 addrspace(1)* %out, align 4
+  ret void
+}
+
+; FUNC-LABEL: @shl_2_add_9_i32_2_add_uses
+; SI-DAG: V_ADD_I32_e32 [[ADDREG:v[0-9]+]], 9, {{v[0-9]+}}
+; SI-DAG: V_LSHLREV_B32_e32 [[SHLREG:v[0-9]+]], 2, {{v[0-9]+}}
+; SI-DAG: BUFFER_STORE_DWORD [[ADDREG]]
+; SI-DAG: BUFFER_STORE_DWORD [[SHLREG]]
+; SI: S_ENDPGM
+define void @shl_2_add_9_i32_2_add_uses(i32 addrspace(1)* %out0, i32 addrspace(1)* %out1, i32 addrspace(1)* %in) #0 {
+  %tid.x = tail call i32 @llvm.r600.read.tidig.x() #1
+  %ptr = getelementptr i32 addrspace(1)* %in, i32 %tid.x
+  %val = load i32 addrspace(1)* %ptr, align 4
+  %add = add i32 %val, 9
+  %result = shl i32 %add, 2
+  store i32 %result, i32 addrspace(1)* %out0, align 4
+  store i32 %add, i32 addrspace(1)* %out1, align 4
+  ret void
+}
+
+; Test with add literal constant
+
+; FUNC-LABEL: @shl_2_add_999_i32
+; SI: V_LSHLREV_B32_e32  [[REG:v[0-9]+]], 2, {{v[0-9]+}}
+; SI: V_ADD_I32_e32 [[RESULT:v[0-9]+]], 0xf9c, [[REG]]
+; SI: BUFFER_STORE_DWORD [[RESULT]]
+; SI: S_ENDPGM
+define void @shl_2_add_999_i32(i32 addrspace(1)* %out, i32 addrspace(1)* %in) #0 {
+  %tid.x = tail call i32 @llvm.r600.read.tidig.x() #1
+  %ptr = getelementptr i32 addrspace(1)* %in, i32 %tid.x
+  %val = load i32 addrspace(1)* %ptr, align 4
+  %shl = add i32 %val, 999
+  %result = shl i32 %shl, 2
+  store i32 %result, i32 addrspace(1)* %out, align 4
+  ret void
+}
+
+attributes #0 = { nounwind }
+attributes #1 = { nounwind readnone }

test/CodeGen/R600/trunc.ll

define void @trunc_load_shl_i64(i32 addrspace(1)* %out, i64 %a) {
   %b = shl i64 %a, 2
   %result = trunc i64 %b to i32
   store i32 %result, i32 addrspace(1)* %out, align 4
   ret void
 }
 
 ; SI-LABEL: @trunc_shl_i64:
 ; SI: S_LOAD_DWORDX2 s{{\[}}[[LO_SREG:[0-9]+]]:{{[0-9]+\]}},
-; SI: S_ADD_I32 s[[LO_ADD:[0-9]+]], s[[LO_SREG]],
-; SI: S_LSHL_B64 s{{\[}}[[LO_SREG2:[0-9]+]]:{{[0-9]+\]}}, s{{\[}}[[LO_ADD]]:{{[0-9]+\]}}, 2
+; SI: S_LSHL_B64 s{{\[}}[[LO_SHL:[0-9]+]]:{{[0-9]+\]}}, s{{\[}}[[LO_SREG]]:{{[0-9]+\]}}, 2
+; SI: S_ADD_I32 s[[LO_SREG2:[0-9]+]], s[[LO_SHL]],
 ; SI: V_MOV_B32_e32 v[[LO_VREG:[0-9]+]], s[[LO_SREG2]]
 ; SI: BUFFER_STORE_DWORD v[[LO_VREG]],
 define void @trunc_shl_i64(i64 addrspace(1)* %out2, i32 addrspace(1)* %out, i64 %a) {
   %aa = add i64 %a, 234 ; Prevent shrinking store.
   %b = shl i64 %aa, 2
   %result = trunc i64 %b to i32
   store i32 %result, i32 addrspace(1)* %out, align 4
   store i64 %b, i64 addrspace(1)* %out2, align 8 ; Prevent reducing ops to 32-bits