SelectionDAG: Reuse bigger sized constants in memset expansion.

[MatzeB]

Summary

When implementing memset's today we often see this pattern:
$x0 = MOV 0xXYXYXYXYXYXYXYXY
store $x0, ...
$w1 = MOV 0xXYXYXYXY
store $w1, ...

We first create a 64bit constant in a 64bit register with all bytes the
same and then create a 32bit constant with all bytes the same in a 32bit
register. In many targets we could just access the lower part of the
64bit register instead.

• Ideally this would be handled by the ConstantHoist pass but it runs too early when memset isn't expanded yet.
• The memset expansion code already had this optimization implemented, however it didn't work as DAGCombiner would fold "trunc(bigconstant)" back to "smallconstant".
• This patch makes the memset expansion mark the constant as Opaque and stop DAGCombiner from constant folding in this situation. (Similar to how ConstantHoisting marks things as Opaque to avoid folding ADD/SUB/etc.)

rdar://44153998

[MatzeB]

• drop accidental reformatting of existing code from the patch.

[MatzeB]

test/CodeGen/X86/pr38771.ll

8

This code changes because ConstantHoisting touches the constants here, and the less aggressive behavior of trunc(OpaqueConstant)" somehow makes DAGCombiner realizes this whole expression being 0 now which it didn't do before. The testcase unfortunately doesn't have enough information to figure out how an equivalent tests would look like that wouldn't constant fold to zero. So this probably has to stay like this...

[jfb]

Nice! LGTM, assuming folks are OK with the llvm.org/pr38771 change.

test/CodeGen/X86/pr38771.ll

8

I expect @craig.topper can chime in on this one.

[craig.topper]

test/CodeGen/X86/pr38771.ll

8

I'm having trouble reducing to a better test case.

The existing test case creates an 'and' while legalizing a srl_parts with an opaque constant for a shift quantity. This failed an assert later in the same legalization. That shift was already sketchy because it used a shift amount that was larger than the bit.

I tried to just make an and with two opaque constant operands. Constant folding in visitAND in DAG combine obeys the opaqueness, but SimplifyDemandedBits called later in visitAND does not. So DAG combine simplifies it when it probably shouldn't.

I'm not very concerned about losing this test case. It's only verifying an assert. There was no code changes associated with it.

[MatzeB]

test/CodeGen/X86/pr38771.ll

8

Thanks for looking into this! I guess I will go ahead and drop the testcase as part of the commit then.

include/llvm/CodeGen/TargetLowering.h

public:
 
   /// Return true if the specified immediate is legal add immediate, that is the
   /// target has add instructions which can add a register with the immediate
   /// without having to materialize the immediate into a register.
   virtual bool isLegalAddImmediate(int64_t) const {
     return true;
   }
 
+  /// Return true if the specified immediate is legal for the value input of a
+  /// store instruction.
+  virtual bool isLegalStoreImmediate(int64_t Value) const {
+    // Default implementation assumes that at least 0 works since it is likely
+    // that a zero register exists or a zero immediate is allowed.
+    return Value == 0;
+  }
+
   /// Return true if it's significantly cheaper to shift a vector by a uniform
   /// scalar than by an amount which will vary across each lane. On x86, for
   /// example, there is a "psllw" instruction for the former case, but no simple
   /// instruction for a general "a << b" operation on vectors.
   virtual bool isVectorShiftByScalarCheap(Type *Ty) const {
     return false;
   }
 

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (findBetterNeighborChains(ST)) {
       // manipulation. Return the original node to not do anything else.
       return SDValue(ST, 0);
     }
     Chain = ST->getChain();
   }
 
   // FIXME: is there such a thing as a truncating indexed store?
   if (ST->isTruncatingStore() && ST->isUnindexed() &&
-      Value.getValueType().isInteger()) {
+      Value.getValueType().isInteger() &&
+      (!isa<ConstantSDNode>(Value) ||
+       !cast<ConstantSDNode>(Value)->isOpaque())) {
     // See if we can simplify the input to this truncstore with knowledge that
     // only the low bits are being used.  For example:
     // "truncstore (or (shl x, 8), y), i8"  -> "truncstore y, i8"
     SDValue Shorter = DAG.GetDemandedBits(
         Value, APInt::getLowBitsSet(Value.getScalarValueSizeInBits(),
                                     ST->getMemoryVT().getScalarSizeInBits()));
     AddToWorklist(Value.getNode());
     if (Shorter.getNode())

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

SDValue SelectionDAG::getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
   // other constants.
   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand)) {
     const APInt &Val = C->getAPIntValue();
     switch (Opcode) {
     default: break;
     case ISD::SIGN_EXTEND:
       return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
                          C->isTargetOpcode(), C->isOpaque());
+    case ISD::TRUNCATE:
+      if (C->isOpaque())
+        break;
+      LLVM_FALLTHROUGH;
     case ISD::ANY_EXTEND:
     case ISD::ZERO_EXTEND:
-    case ISD::TRUNCATE:
       return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
                          C->isTargetOpcode(), C->isOpaque());
     case ISD::UINT_TO_FP:
     case ISD::SINT_TO_FP: {
       APFloat apf(EVTToAPFloatSemantics(VT),
                   APInt::getNullValue(VT.getSizeInBits()));
       (void)apf.convertFromAPInt(Val,
                                  Opcode==ISD::SINT_TO_FP,

 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
                               const SDLoc &dl) {
   assert(!Value.isUndef());
 
   unsigned NumBits = VT.getScalarSizeInBits();
   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
     assert(C->getAPIntValue().getBitWidth() == 8);
     APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
-    if (VT.isInteger())
-      return DAG.getConstant(Val, dl, VT);
+    if (VT.isInteger()) {
+      bool IsOpaque = VT.getSizeInBits() > 64 ||
+          !DAG.getTargetLoweringInfo().isLegalStoreImmediate(C->getSExtValue());
+      return DAG.getConstant(Val, dl, VT, false, IsOpaque);
+    }
     return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
                              VT);
   }
 
   assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
   EVT IntVT = VT.getScalarType();
   if (!IntVT.isInteger())
     IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
if (VTSize > Size) {
       DstOff -= VTSize - Size;
     }
 
     // If this store is smaller than the largest store see whether we can get
     // the smaller value for free with a truncate.
     SDValue Value = MemSetValue;
     if (VT.bitsLT(LargestVT)) {
       if (!LargestVT.isVector() && !VT.isVector() &&
-          TLI.isTruncateFree(LargestVT, VT))
+          TLI.isTruncateFree(LargestVT, VT)) {
         Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
-      else
+      } else {
         Value = getMemsetValue(Src, VT, DAG, dl);
       }
+    }
     assert(Value.getValueType() == VT && "Value with wrong type.");
     SDValue Store = DAG.getStore(
         Chain, dl, Value, DAG.getMemBasePlusOffset(Dst, DstOff, dl),
         DstPtrInfo.getWithOffset(DstOff), Align,
         isVol ? MachineMemOperand::MOVolatile : MachineMemOperand::MONone);
     OutChains.push_back(Store);
     DstOff += VT.getSizeInBits() / 8;
     Size -= VTSize;

lib/Target/X86/X86ISelLowering.h

public:
     bool isLegalICmpImmediate(int64_t Imm) const override;
 
     /// Return true if the specified immediate is legal
     /// add immediate, that is the target has add instructions which can
     /// add a register and the immediate without having to materialize
     /// the immediate into a register.
     bool isLegalAddImmediate(int64_t Imm) const override;
 
+    bool isLegalStoreImmediate(int64_t Imm) const override;
+
     /// Return the cost of the scaling factor used in the addressing
     /// mode represented by AM for this target, for a load/store
     /// of the specified type.
     /// If the AM is supported, the return value must be >= 0.
     /// If the AM is not supported, it returns a negative value.
     int getScalingFactorCost(const DataLayout &DL, const AddrMode &AM, Type *Ty,
                              unsigned AS) const override;
 

lib/Target/X86/X86ISelLowering.cpp

bool X86TargetLowering::isLegalICmpImmediate(int64_t Imm) const {
   return isInt<32>(Imm);
 }
 
 bool X86TargetLowering::isLegalAddImmediate(int64_t Imm) const {
   // Can also use sub to handle negated immediates.
   return isInt<32>(Imm);
 }
 
+bool X86TargetLowering::isLegalStoreImmediate(int64_t Imm) const {
+  return isInt<32>(Imm);
+}
+
 bool X86TargetLowering::isTruncateFree(EVT VT1, EVT VT2) const {
   if (!VT1.isInteger() || !VT2.isInteger())
     return false;
   unsigned NumBits1 = VT1.getSizeInBits();
   unsigned NumBits2 = VT2.getSizeInBits();
   return NumBits1 > NumBits2;
 }
 

test/CodeGen/AArch64/arm64-memset-inline.ll

 ; CHECK-NEXT:  bl something
   %buf = alloca [8 x i8], align 1
   %cast = bitcast [8 x i8]* %buf to i8*
   call void @llvm.memset.p0i8.i32(i8* %cast, i8 -86, i32 8, i1 false)
   call void @something(i8* %cast)
   ret void
 }
 
-; FIXME This could be better: x9 is a superset of w8's bit-pattern.
 define void @memset_12_stack() {
 ; CHECK-LABEL: memset_12_stack:
-; CHECK:       mov w8, #-1431655766
-; CHECK-NEXT:  mov x9, #-6148914691236517206
+; CHECK:       mov x8, #-6148914691236517206
 ; CHECK-NEXT:  mov x0, sp
+; CHECK-NEXT:  str x8, [sp]
 ; CHECK-NEXT:  str w8, [sp, #8]
-; CHECK-NEXT:  str x9, [sp]
 ; CHECK-NEXT:  bl something
   %buf = alloca [12 x i8], align 1
   %cast = bitcast [12 x i8]* %buf to i8*
   call void @llvm.memset.p0i8.i32(i8* %cast, i8 -86, i32 12, i1 false)
   call void @something(i8* %cast)
   ret void
 }
 
 define void @memset_16_stack() {
 ; CHECK-LABEL: memset_16_stack:
 ; CHECK:       mov x8, #-6148914691236517206
 ; CHECK-NEXT:  mov x0, sp
 ; CHECK-NEXT:  stp x8, x30, [sp, #8]
 ; CHECK-NEXT:  str x8, [sp]
 ; CHECK-NEXT:  bl something
   %buf = alloca [16 x i8], align 1
   %cast = bitcast [16 x i8]* %buf to i8*
   call void @llvm.memset.p0i8.i32(i8* %cast, i8 -86, i32 16, i1 false)
   call void @something(i8* %cast)
   ret void
 }
 
-; FIXME This could be better: x9 is a superset of w8's bit-pattern.
 define void @memset_20_stack() {
 ; CHECK-LABEL: memset_20_stack:
-; CHECK:       mov w8, #-1431655766
-; CHECK-NEXT:  mov x9, #-6148914691236517206
+; CHECK:       mov x8, #-6148914691236517206
 ; CHECK-NEXT:  add x0, sp, #8
+; CHECK-NEXT:  stp x8, x8, [sp, #8]
 ; CHECK-NEXT:  str w8, [sp, #24]
-; CHECK-NEXT:  stp x9, x9, [sp, #8]
 ; CHECK-NEXT:  bl something
   %buf = alloca [20 x i8], align 1
   %cast = bitcast [20 x i8]* %buf to i8*
   call void @llvm.memset.p0i8.i32(i8* %cast, i8 -86, i32 20, i1 false)
   call void @something(i8* %cast)
   ret void
 }
 
-; FIXME This could be better: x9 is a superset of w8's bit-pattern.
 define void @memset_26_stack() {
 ; CHECK-LABEL: memset_26_stack:
-; CHECK:       mov w8, #43690
-; CHECK-NEXT:  mov x9, #-6148914691236517206
+; CHECK:       mov x8, #-6148914691236517206
 ; CHECK-NEXT:  mov x0, sp
+; CHECK-NEXT:  stp x8, x8, [sp, #8]
+; CHECK-NEXT:  str x8, [sp]
 ; CHECK-NEXT:  strh w8, [sp, #24]
-; CHECK-NEXT:  stp x9, x9, [sp, #8]
-; CHECK-NEXT:  str x9, [sp]
 ; CHECK-NEXT:  bl something
   %buf = alloca [26 x i8], align 1
   %cast = bitcast [26 x i8]* %buf to i8*
   call void @llvm.memset.p0i8.i32(i8* %cast, i8 -86, i32 26, i1 false)
   call void @something(i8* %cast)
   ret void
 }
 

test/CodeGen/X86/pr38771.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown | FileCheck %s
 
 define void @function() nounwind {
 ; CHECK-LABEL: function:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    movabsq $281474976710656, %rax # imm = 0x1000000000000
-; CHECK-NEXT:    notq %rax
-; CHECK-NEXT:    movl $2147483647, %ecx # imm = 0x7FFFFFFF
-; CHECK-NEXT:    shldq $65, %rax, %rcx
-; CHECK-NEXT:    xorl %eax, %eax
-; CHECK-NEXT:    movb $64, %dl
-; CHECK-NEXT:    testb %dl, %dl
-; CHECK-NEXT:    cmoveq %rcx, %rax
-; CHECK-NEXT:    movq %rax, (%rax)
 ; CHECK-NEXT:    movl $0, (%rax)
+; CHECK-NEXT:    movq $0, (%rax)
 ; CHECK-NEXT:    retq
 entry:
   %B68 = sub i96 39614081257132168796771975167, 281474976710656
   %B49 = or i96 39614081257132168796771975167, 39614081257132168796771975167
   %B33 = lshr i96 %B68, %B68
   store i96 %B33, i96* undef
   ret void
 }