[X86] Memset is lowered to rep stos if MinSize is present

[vdsered]

Summary

X86 does not to account for MinSize when lowering memset which leads to larger code size than it is possible to get, for example, with using rep stos which is already in use in GCC.

This patch must reduce code size for memset when MinSize is used.

Issue with some more details: https://github.com/llvm/llvm-project/issues/51196

[vdsered]

This comment was removed by vdsered.

[spatel]

I don't remember seeing this part of x86 codegen before, so adding some more reviewers. I'm also not sure what is recommended as the best perf x86 asm on recent CPUs. Should we be using this for "optsize" too?

[pengfei]

In D115602#3195463, @spatel wrote:

I don't remember seeing this part of x86 codegen before, so adding some more reviewers. I'm also not sure what is recommended as the best perf x86 asm on recent CPUs. Should we be using this for "optsize" too?

Neither do I. I saw Clang only has the builtin support __builtin_memcpy_inline by D73543. But GCC has the tuning code: https://github.com/gcc-mirror/gcc/commit/a32452a5442cd05040af53787af0d8b537ac77a6
Like the descriptions in GCC patch, this is not all win solution. But for minsize and optsize, this should be good to go. https://godbolt.org/z/4r8zTqfhY

[lebedev.ri]

llvm/include/llvm/CodeGen/SelectionDAGTargetInfo.h

80–92

Why do you need shouldEmitTargetCodeForMemset() if there already is EmitTargetCodeForMemset?

[vdsered]

In D115602#3195463, @spatel wrote:

I don't remember seeing this part of x86 codegen before, so adding some more reviewers. I'm also not sure what is recommended as the best perf x86 asm on recent CPUs. Should we be using this for "optsize" too?

Not sure too, but rep stos seems to be a good choice if we are directly asked for MinSize. I'd not add OptSize here as we will probably sacrifice performance in some cases. At least, I'd not do that in that patch.

1. There is a pull request for dotnet runtime with some similar problem Use xmm for stack prolog zeroing rather than rep stos. Seems like in general rep stos is not the best choice for performance.

2. Intel in their manual "F.8.3.7 Copy and String Copy" say to use specifically only rep stosb for performance or as it is written "Software wishing to have a simple default string copy or store routine that will work well on a range of implementations (including future implementations) should consider using REP MOVSB or REP STOSB on implementations that support Enhanced REP MOVSB and STOSB".

3. On the other hand, I found that AMD says rep stos is in general less efficient, but this is mentioned in only two guides Software Optimization Guide for AMD Family 15h Processors, (see 9.3 Repeated String Instructions) and Software Optimization Guide for AMD64 Processors (this one it too old and probably outdated). Plus, on the contrary to Intel, AMD recommends to use rep stos(b/w/d/q) to improve performance.

To sum up, I'd emit only rep stosb for Intel, if possible, and rep stos(b/w/d) for AMD when MinSize is present for now

Does it seem to be a good solution if we add the comment from @pengfei to this? Waiting for other opinions...

[vdsered]

llvm/include/llvm/CodeGen/SelectionDAGTargetInfo.h

80–92

1. EmitTargetCodeForMemset seems to me to be the best place to generate code specific to MinSize for a target
2. I intended to avoid changing/touching code generation for other backends which do not want to handle cases like MinSize or something similar and I thought of a way to go directly to EmitTargetCodeForMemset
3. I optimize for MinSize when the length is constant and for such a case there is another lowering in getMemsetStores and I need to skip it

So, I created a method to decide whether to go directly to EmitTargetCodeForMemset or not and this method is customizable for each target.

There is probably a better solution, but I don't see a way to do it with less code written. Any suggestions? I can clarify it better in the comments...

[craig.topper]

It doesn't look like the changed tests match the case in the linked issue. Should we have a test for that?

llvm/include/llvm/CodeGen/SelectionDAGTargetInfo.h

 /// SelectionDAG lowering and instruction selection process.
 ///
 class SelectionDAGTargetInfo {
 public:
   explicit SelectionDAGTargetInfo() = default;
   SelectionDAGTargetInfo(const SelectionDAGTargetInfo &) = delete;
   SelectionDAGTargetInfo &operator=(const SelectionDAGTargetInfo &) = delete;
   virtual ~SelectionDAGTargetInfo();
+  // Return true if target-specific code for memset will be better than generic
+  // approach
+  virtual bool shouldEmitTargetCodeForMemset(SelectionDAG &DAG,
+                                             SDValue Size) const {
+    return false;
+  }
 
   /// Emit target-specific code that performs a memcpy.
   /// This can be used by targets to provide code sequences for cases
   /// that don't fit the target's parameters for simple loads/stores and can be
   /// more efficient than using a library call. This function can return a null
   /// SDValue if the target declines to use custom code and a different
   /// lowering strategy should be used.
   ///
public:
   /// lowering strategy should be used.
   virtual SDValue EmitTargetCodeForMemmove(
       SelectionDAG &DAG, const SDLoc &dl, SDValue Chain, SDValue Op1,
       SDValue Op2, SDValue Op3, Align Alignment, bool isVolatile,
       MachinePointerInfo DstPtrInfo, MachinePointerInfo SrcPtrInfo) const {
     return SDValue();
   }
 
   /// Emit target-specific code that performs a memset.
   /// This can be used by targets to provide code sequences for cases
   /// that don't fit the target's parameters for simple stores and can be more
   /// efficient than using a library call. This function can return a null
   /// SDValue if the target declines to use custom code and a different
   /// lowering strategy should be used.
   virtual SDValue EmitTargetCodeForMemset(SelectionDAG &DAG, const SDLoc &dl,
                                           SDValue Chain, SDValue Op1,
                                           SDValue Op2, SDValue Op3,
                                           Align Alignment, bool isVolatile,
                                           MachinePointerInfo DstPtrInfo) const {
     return SDValue();
   }
 
   /// Emit target-specific code that performs a memcmp/bcmp, in cases where that is
   /// faster than a libcall. The first returned SDValue is the result of the
   /// memcmp and the second is the chain. Both SDValues can be null if a normal
   /// libcall should be used.
   virtual std::pair<SDValue, SDValue>
   EmitTargetCodeForMemcmp(SelectionDAG &DAG, const SDLoc &dl, SDValue Chain,
                           SDValue Op1, SDValue Op2, SDValue Op3,

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

 SDValue SelectionDAG::getMemset(SDValue Chain, const SDLoc &dl, SDValue Dst,
                                 SDValue Src, SDValue Size, Align Alignment,
                                 bool isVol, bool isTailCall,
                                 MachinePointerInfo DstPtrInfo,
                                 const AAMDNodes &AAInfo) {
   // Check to see if we should lower the memset to stores first.
   // For cases within the target-specified limits, this is the best choice.
   ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
-  if (ConstantSize) {
+  if (ConstantSize &&
+      !(TSI && TSI->shouldEmitTargetCodeForMemset(*this, Size))) {
     // Memset with size zero? Just return the original chain.
     if (ConstantSize->isZero())
       return Chain;
 
     SDValue Result = getMemsetStores(*this, dl, Chain, Dst, Src,
                                      ConstantSize->getZExtValue(), Alignment,
                                      isVol, DstPtrInfo, AAInfo);
 

llvm/lib/Target/X86/X86SelectionDAGInfo.h

class X86SelectionDAGInfo : public SelectionDAGTargetInfo {
   /// Returns true if it is possible for the base register to conflict with the
   /// given set of clobbers for a memory intrinsic.
   bool isBaseRegConflictPossible(SelectionDAG &DAG,
                                  ArrayRef<MCPhysReg> ClobberSet) const;
 
 public:
   explicit X86SelectionDAGInfo() = default;
 
+  virtual bool shouldEmitTargetCodeForMemset(SelectionDAG &DAG,
+                                             SDValue Size) const override;
+
   SDValue EmitTargetCodeForMemset(SelectionDAG &DAG, const SDLoc &dl,
                                   SDValue Chain, SDValue Dst, SDValue Src,
                                   SDValue Size, Align Alignment,
                                   bool isVolatile,
                                   MachinePointerInfo DstPtrInfo) const override;
 
   SDValue EmitTargetCodeForMemcpy(SelectionDAG &DAG, const SDLoc &dl,
                                   SDValue Chain, SDValue Dst, SDValue Src,

llvm/lib/Target/X86/X86SelectionDAGInfo.cpp

 using namespace llvm;
 
 #define DEBUG_TYPE "x86-selectiondag-info"
 
 static cl::opt<bool>
     UseFSRMForMemcpy("x86-use-fsrm-for-memcpy", cl::Hidden, cl::init(false),
                      cl::desc("Use fast short rep mov in memcpy lowering"));
 
+bool X86SelectionDAGInfo::shouldEmitTargetCodeForMemset(SelectionDAG &DAG,
+                                                        SDValue Size) const {
+  auto *ConstantSize = dyn_cast<ConstantSDNode>(Size);
+
+  if (!ConstantSize)
+    return false;
+
+  // In this case we can replace memset by more simple constructions like
+  // andq $0, (%rdi)
+  if (ConstantSize->getZExtValue() <= 8)
+    return false;
+
+  return DAG.getMachineFunction().getFunction().hasMinSize();
+}
+
 bool X86SelectionDAGInfo::isBaseRegConflictPossible(
     SelectionDAG &DAG, ArrayRef<MCPhysReg> ClobberSet) const {
   // We cannot use TRI->hasBasePointer() until *after* we select all basic
   // blocks.  Legalization may introduce new stack temporaries with large
   // alignment requirements.  Fall back to generic code if there are any
   // dynamic stack adjustments (hopefully rare) and the base pointer would
   // conflict if we had to use it.
   MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo();
const MCPhysReg ClobberSet[] = {X86::RCX, X86::RAX, X86::RDI,
                                   X86::ECX, X86::EAX, X86::EDI};
   assert(!isBaseRegConflictPossible(DAG, ClobberSet));
 #endif
 
   // If to a segment-relative address space, use the default lowering.
   if (DstPtrInfo.getAddrSpace() >= 256)
     return SDValue();
 
+  bool HasMinSize = DAG.getMachineFunction().getFunction().hasMinSize();
+
   // If not DWORD aligned or size is more than the threshold, call the library.
   // The libc version is likely to be faster for these cases. It can use the
   // address value and run time information about the CPU.
-  if (Alignment < Align(4) || !ConstantSize ||
-      ConstantSize->getZExtValue() > Subtarget.getMaxInlineSizeThreshold()) {
+  if (!ConstantSize ||
+      ((Alignment < Align(4) ||
+        ConstantSize->getZExtValue() > Subtarget.getMaxInlineSizeThreshold()) &&
+       !HasMinSize)) {
     // Check to see if there is a specialized entry-point for memory zeroing.
     ConstantSDNode *ValC = dyn_cast<ConstantSDNode>(Val);
 
     if (const char *bzeroName =
             (ValC && ValC->isZero())
                 ? DAG.getTargetLoweringInfo().getLibcallName(RTLIB::BZERO)
                 : nullptr) {
       const TargetLowering &TLI = DAG.getTargetLoweringInfo();
if (!ConstantSize ||
     }
 
     // Otherwise have the target-independent code call memset.
     return SDValue();
   }
 
   uint64_t SizeVal = ConstantSize->getZExtValue();
   SDValue InFlag;
-  EVT AVT;
+  EVT AVT = MVT::i8;
   SDValue Count;
   ConstantSDNode *ValC = dyn_cast<ConstantSDNode>(Val);
   unsigned BytesLeft = 0;
   if (ValC) {
-    unsigned ValReg;
-    uint64_t Val = ValC->getZExtValue() & 255;
+    unsigned ValReg = X86::AL;
+    uint64_t MemsetVal = ValC->getZExtValue() & 255;
 
-    // If the value is a constant, then we can potentially use larger sets.
-    if (Alignment > Align(2)) {
+    if (HasMinSize && SizeVal % 2 != 0) {
+      // Byte aligned
+      AVT = MVT::i8;
+      ValReg = X86::AL;
+      Count = DAG.getIntPtrConstant(SizeVal, dl);
+    } else if (Alignment > Align(2)) { // If the value is a constant, then we
+                                       // can potentially use larger sets.
       // DWORD aligned
       AVT = MVT::i32;
       ValReg = X86::EAX;
-      Val = (Val << 8)  | Val;
-      Val = (Val << 16) | Val;
+      MemsetVal = (MemsetVal << 8) | MemsetVal;
+      MemsetVal = (MemsetVal << 16) | MemsetVal;
       if (Subtarget.is64Bit() && Alignment > Align(8)) { // QWORD aligned
         AVT = MVT::i64;
         ValReg = X86::RAX;
-        Val = (Val << 32) | Val;
+        MemsetVal = (MemsetVal << 32) | MemsetVal;
       }
     } else if (Alignment == Align(2)) {
       // WORD aligned
       AVT = MVT::i16;
       ValReg = X86::AX;
-      Val = (Val << 8) | Val;
+      MemsetVal = (MemsetVal << 8) | MemsetVal;
     } else {
-      // Byte aligned
-      AVT = MVT::i8;
-      ValReg = X86::AL;
       Count = DAG.getIntPtrConstant(SizeVal, dl);
     }
 
     if (AVT.bitsGT(MVT::i8)) {
       unsigned UBytes = AVT.getSizeInBits() / 8;
       Count = DAG.getIntPtrConstant(SizeVal / UBytes, dl);
       BytesLeft = SizeVal % UBytes;
     }
 
-    Chain = DAG.getCopyToReg(Chain, dl, ValReg, DAG.getConstant(Val, dl, AVT),
-                             InFlag);
+    Chain = DAG.getCopyToReg(Chain, dl, ValReg,
+                             DAG.getConstant(MemsetVal, dl, AVT), InFlag);
     InFlag = Chain.getValue(1);
   } else {
     AVT = MVT::i8;
     Count  = DAG.getIntPtrConstant(SizeVal, dl);
     Chain  = DAG.getCopyToReg(Chain, dl, X86::AL, Val, InFlag);
     InFlag = Chain.getValue(1);
   }
 

llvm/test/CodeGen/X86/memset-minsize.ll

entry:
   %0 = bitcast i32* %ptr to i8*
   call void @llvm.memset.p0i8.i32(i8* align 4 %0, i8 0, i32 128, i1 false)
   ret void
 }
 
 define void @medium_memset_to_rep_stos(i32* %ptr) minsize nounwind {
 ; CHECK-LABEL: medium_memset_to_rep_stos:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    pushq %rax
-; CHECK-NEXT:    movl $512, %edx # imm = 0x200
-; CHECK-NEXT:    xorl %esi, %esi
-; CHECK-NEXT:    callq memset@PLT
-; CHECK-NEXT:    popq %rax
+; CHECK-NEXT:    movl $128, %ecx
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    rep;stosl %eax, %es:(%rdi)
 ; CHECK-NEXT:    retq
 entry:
   %0 = bitcast i32* %ptr to i8*
   call void @llvm.memset.p0i8.i32(i8* align 4 %0, i8 0, i32 512, i1 false)
   ret void
 }
 
 define void @large_memset_to_rep_stos(i32* %ptr) minsize nounwind {
 ; CHECK-LABEL: large_memset_to_rep_stos:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    pushq %rax
-; CHECK-NEXT:    movl $4096, %edx # imm = 0x1000
-; CHECK-NEXT:    xorl %esi, %esi
-; CHECK-NEXT:    callq memset@PLT
-; CHECK-NEXT:    popq %rax
+; CHECK-NEXT:    movl $1024, %ecx # imm = 0x400
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    rep;stosl %eax, %es:(%rdi)
 ; CHECK-NEXT:    retq
 entry:
   %0 = bitcast i32* %ptr to i8*
   call void @llvm.memset.p0i8.i32(i8* align 4 %0, i8 0, i32 4096, i1 false)
   ret void
 }
 
 define void @huge_memset_to_rep_stos(i32* %ptr) minsize nounwind {
 ; CHECK-LABEL: huge_memset_to_rep_stos:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    pushq %rax
-; CHECK-NEXT:    movl $8192, %edx # imm = 0x2000
-; CHECK-NEXT:    xorl %esi, %esi
-; CHECK-NEXT:    callq memset@PLT
-; CHECK-NEXT:    popq %rax
+; CHECK-NEXT:    movl $2048, %ecx # imm = 0x800
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    rep;stosl %eax, %es:(%rdi)
 ; CHECK-NEXT:    retq
 entry:
   %0 = bitcast i32* %ptr to i8*
   call void @llvm.memset.p0i8.i32(i8* align 4 %0, i8 0, i32 8192, i1 false)
   ret void
 }
 
 define void @odd_length_memset_to_rep_stos(i32* %ptr) minsize nounwind {
 ; CHECK-LABEL: odd_length_memset_to_rep_stos:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    pushq %rax
-; CHECK-NEXT:    movl $255, %edx
-; CHECK-NEXT:    xorl %esi, %esi
-; CHECK-NEXT:    callq memset@PLT
-; CHECK-NEXT:    popq %rax
+; CHECK-NEXT:    movl $255, %ecx
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    rep;stosb %al, %es:(%rdi)
 ; CHECK-NEXT:    retq
 entry:
   %0 = bitcast i32* %ptr to i8*
   call void @llvm.memset.p0i8.i32(i8* align 4 %0, i8 0, i32 255, i1 false)
   ret void
 }
 
 define void @align_1_memset_to_rep_stos(i8* %ptr) minsize nounwind {
 ; CHECK-LABEL: align_1_memset_to_rep_stos:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    pushq %rax
-; CHECK-NEXT:    movl $256, %edx # imm = 0x100
-; CHECK-NEXT:    xorl %esi, %esi
-; CHECK-NEXT:    callq memset@PLT
-; CHECK-NEXT:    popq %rax
+; CHECK-NEXT:    movl $256, %ecx # imm = 0x100
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    rep;stosb %al, %es:(%rdi)
 ; CHECK-NEXT:    retq
 entry:
   call void @llvm.memset.p0i8.i32(i8* align 1 %ptr, i8 0, i32 256, i1 false)
   ret void
 }
 
 define void @align_2_memset_to_rep_stos(i16* %ptr) minsize nounwind {
 ; CHECK-LABEL: align_2_memset_to_rep_stos:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    pushq %rax
-; CHECK-NEXT:    movl $256, %edx # imm = 0x100
-; CHECK-NEXT:    xorl %esi, %esi
-; CHECK-NEXT:    callq memset@PLT
-; CHECK-NEXT:    popq %rax
+; CHECK-NEXT:    movl $128, %ecx
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    rep;stosw %ax, %es:(%rdi)
 ; CHECK-NEXT:    retq
 entry:
   %0 = bitcast i16* %ptr to i8*
   call void @llvm.memset.p0i8.i32(i8* align 2 %0, i8 0, i32 256, i1 false)
   ret void
 }
 
 define void @align_4_memset_to_rep_stos(i16* %ptr) minsize nounwind {
 ; CHECK-LABEL: align_4_memset_to_rep_stos:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    pushq %rax
-; CHECK-NEXT:    movl $256, %edx # imm = 0x100
-; CHECK-NEXT:    xorl %esi, %esi
-; CHECK-NEXT:    callq memset@PLT
-; CHECK-NEXT:    popq %rax
+; CHECK-NEXT:    pushq $64
+; CHECK-NEXT:    popq %rcx
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    rep;stosl %eax, %es:(%rdi)
 ; CHECK-NEXT:    retq
 entry:
   %0 = bitcast i16* %ptr to i8*
   call void @llvm.memset.p0i8.i32(i8* align 4 %0, i8 0, i32 256, i1 false)
   ret void
 }
 
 define void @align_8_memset_to_rep_stos(i64* %ptr) minsize nounwind {
 ; CHECK-LABEL: align_8_memset_to_rep_stos:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    pushq %rax
-; CHECK-NEXT:    movl $256, %edx # imm = 0x100
-; CHECK-NEXT:    xorl %esi, %esi
-; CHECK-NEXT:    callq memset@PLT
-; CHECK-NEXT:    popq %rax
+; CHECK-NEXT:    pushq $64
+; CHECK-NEXT:    popq %rcx
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    rep;stosl %eax, %es:(%rdi)
 ; CHECK-NEXT:    retq
 entry:
   %0 = bitcast i64* %ptr to i8*
   call void @llvm.memset.p0i8.i32(i8* align 8 %0, i8 0, i32 256, i1 false)
   ret void
 }
 
 declare void @llvm.memset.p0i8.i32(i8* nocapture writeonly, i8, i32, i1)