Move memset value into register

[sepavloff]

Summary

This patch fixes PR5124 (memset inline-code threshold dubiously high).
If memset is expanded inline and the memset value is constant, code generator created sequence of instructions 'mov imm, mem', like:

movl   $0x0,0x4(%esi)
movl   $0x0,0x8(%esi)

With this patch the memset value is put into register and then instructions 'mov reg, mem' are used:

movl   %eax,0x4(%esi)
movl   %eax,0x8(%esi)

It is profitable for both speed and code size, gcc and icc expand memset in this way.

Could you please review the patch?
Thank you.

[bkramer]

Thanks for working on this, it nicely avoids the bloated code of the immediate form of "mov".

The patch essentially looks good to me as is. I'd like to hear a second opinion from Nadav in case I'm missing something.

[sepavloff]

Cosmetical update to the patch
If block size is small, the size of largest move chunk may be smaller than the
natural register width and target may not have resisters of such width. Example
is 32-bit target that does not have 16-bit registers. Avoid allocation such
illegal registers.

[void]

@sepavloff, are you still interested in this patch? I've been going through old bugs...

[sepavloff]

In D1484#3362129, @void wrote:

@sepavloff, are you still interested in this patch? I've been going through old bugs...

No, this patch is outdated.

include/llvm/Target/TargetLowering.h

public:
   /// This function returns the maximum number of store operations permitted
   /// to replace a call to llvm.memmove. The value is set by the target at the
   /// performance threshold for such a replacement. If OptSize is true,
   /// return the limit for functions that have OptSize attribute.
   unsigned getMaxStoresPerMemmove(bool OptSize) const {
     return OptSize ? MaxStoresPerMemmoveOptSize : MaxStoresPerMemmove;
   }
 
+  /// \brief Determine if constant value used in llvm.memset should be placed
+  /// into register.
+  ///
+  /// \param OptSize If True the code generation is optimized for code
+  ///                size, otherwise - for performance.
+  /// \param MemOps  Type of each store operation.
+  /// \return True if moving memset value into a register is profitable.
+  ///
+  /// If llvm.memset is replaced by a series of store operations and the memset
+  /// value is constant, on some platforms the store operations may be
+  /// implemented as moves of immediate operand to memory, or the memset value
+  /// may be stored in a register and then used in moves from register to
+  /// memory. This function determines which way is more profitable.
+  virtual bool putMemsetImmediateToRegister(bool OptSize,
+                                            std::vector<EVT> &MemOps) const {
+    // By default use previous behavior.
+    return false;
+  }
+
   /// \brief Determine if the target supports unaligned memory accesses.
   ///
   /// This function returns true if the target allows unaligned memory accesses.
   /// of the specified type. If true, it also returns whether the unaligned
   /// memory access is "fast" in the second argument by reference. This is used,
   /// for example, in situations where an array copy/move/set is converted to a
   /// sequence of store operations. It's use helps to ensure that such
   /// replacements don't generate code that causes an alignment error (trap) on

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Assembly/Writer.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineConstantPool.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/DebugInfo.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalVariable.h"
for (unsigned i = 0; i < NumMemOps; i++) {
     OutChains.push_back(Store);
     DstOff += VTSize;
   }
 
   return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
                      &OutChains[0], OutChains.size());
 }
 
+/// \brief Lower the call to 'memset' intrinsic function into a series of store
+/// operations.
+///
+/// \param DAG Selection DAG where lowered code is placed.
+/// \param dl Link to corresponding IR location.
+/// \param Chain Control flow dependency.
+/// \param Dst Pointer to destination memory location.
+/// \param Src Value of byte to write into the memory.
+/// \param Size Number of bytes to write.
+/// \param Align Alignment of the destination in bytes.
+/// \param isVol True if destination is volatile.
+/// \param DstPtrInfo IR information on the memory pointer.
+/// \returns New head in the control flow, if lowering was successful, empty
+/// SDValue otherwise.
+///
+/// The function tries to replace 'llvm.memset' intrinsic with several store
+/// operations and value calculation code. This is usually profitable for small
+/// memory size.
 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
                                SDValue Chain, SDValue Dst,
                                SDValue Src, uint64_t Size,
                                unsigned Align, bool isVol,
                                MachinePointerInfo DstPtrInfo) {
   // Turn a memset of undef to nop.
   if (Src.getOpcode() == ISD::UNDEF)
     return Chain;
static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
 
   // Find the largest store and generate the bit pattern for it.
   EVT LargestVT = MemOps[0];
   for (unsigned i = 1; i < NumMemOps; i++)
     if (MemOps[i].bitsGT(LargestVT))
       LargestVT = MemOps[i];
   SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
 
+  // If profitable, put constant memset value in a register.
+  SDValue LongestValueInReg;
+  unsigned ValueReg = 0;
+  if (isa<ConstantSDNode>(MemSetValue) &&
+      TLI.isTypeLegal(LargestVT) &&
+      TLI.putMemsetImmediateToRegister(OptSize, MemOps)) {
+    const TargetLowering *TL = DAG.getTarget().getTargetLowering();
+    const TargetRegisterClass* TRC = TL->getRegClassFor(LargestVT.getSimpleVT());
+    ValueReg = MF.getRegInfo().createVirtualRegister(TRC);
+    Chain = DAG.getCopyToReg(Chain, dl, ValueReg, MemSetValue);
+    LongestValueInReg = DAG.getRegister(ValueReg, LargestVT);
+  } else
+    LongestValueInReg = MemSetValue;
+  SDValue  RegInitialization = Chain;
+
   for (unsigned i = 0; i < NumMemOps; i++) {
     EVT VT = MemOps[i];
     unsigned VTSize = VT.getSizeInBits() / 8;
     if (VTSize > Size) {
       // Issuing an unaligned load / store pair  that overlaps with the previous
       // pair. Adjust the offset accordingly.
       assert(i == NumMemOps-1 && i != 0);
       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;
+    SDValue Value  = LongestValueInReg;
     if (VT.bitsLT(LargestVT)) {
       if (!LargestVT.isVector() && !VT.isVector() &&
-          TLI.isTruncateFree(LargestVT, VT))
-        Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
+          TLI.isTruncateFree(LargestVT, VT)) {
+        if (ValueReg != 0)
+          Value = DAG.getCopyFromReg(RegInitialization, dl, ValueReg, LargestVT);
+        Value = DAG.getNode(ISD::TRUNCATE, dl, VT, Value);
+      }
       else
         Value = getMemsetValue(Src, VT, DAG, dl);
     }
     assert(Value.getValueType() == VT && "Value with wrong type.");
     SDValue Store = DAG.getStore(Chain, dl, Value,
                                  getMemBasePlusOffset(Dst, DstOff, dl, DAG),
                                  DstPtrInfo.getWithOffset(DstOff),
                                  isVol, false, Align);

lib/Target/X86/X86ISelLowering.h

public:
     /// isSafeMemOpType - Returns true if it's safe to use load / store of the
     /// specified type to expand memcpy / memset inline. This is mostly true
     /// for all types except for some special cases. For example, on X86
     /// targets without SSE2 f64 load / store are done with fldl / fstpl which
     /// also does type conversion. Note the specified type doesn't have to be
     /// legal as the hook is used before type legalization.
     virtual bool isSafeMemOpType(MVT VT) const;
 
+    virtual bool putMemsetImmediateToRegister(bool OptSize,
+                                              std::vector<EVT> &MemOps) const;
+
     /// allowsUnalignedMemoryAccesses - Returns true if the target allows
     /// unaligned memory accesses. of the specified type. Returns whether it
     /// is "fast" by reference in the second argument.
     virtual bool allowsUnalignedMemoryAccesses(EVT VT, bool *Fast) const;
 
     /// LowerOperation - Provide custom lowering hooks for some operations.
     ///
     virtual SDValue LowerOperation(SDValue Op, SelectionDAG &DAG) const;

lib/Target/X86/X86ISelLowering.cpp

 bool X86TargetLowering::isSafeMemOpType(MVT VT) const {
   if (VT == MVT::f32)
     return X86ScalarSSEf32;
   else if (VT == MVT::f64)
     return X86ScalarSSEf64;
   return true;
 }
 
+bool X86TargetLowering:: putMemsetImmediateToRegister(bool OptSize,
+                                               std::vector<EVT> &MemOps) const {
+  return MemOps.size() > 1;
+}
+
 bool
 X86TargetLowering::allowsUnalignedMemoryAccesses(EVT VT, bool *Fast) const {
   if (Fast)
     *Fast = Subtarget->isUnalignedMemAccessFast();
   return true;
 }
 
 /// getJumpTableEncoding - Return the entry encoding for a jump table in the

test/CodeGen/X86/memset-sse-stack-realignment.ll

define void @test1(i32 %t) nounwind {
   %tmp1210 = alloca i8, i32 32, align 4
   call void @llvm.memset.p0i8.i64(i8* %tmp1210, i8 0, i64 32, i32 4, i1 false)
   %x = alloca i8, i32 %t
   call void @dummy(i8* %x)
   ret void
 
 ; NOSSE-LABEL: test1:
 ; NOSSE-NOT: and
-; NOSSE: movl $0
+; NOSSE: movl %e{{[a-d]}}x,
 
 ; SSE1-LABEL: test1:
 ; SSE1: andl $-16
 ; SSE1: movl %esp, %esi
 ; SSE1: movaps
 
 ; SSE2-LABEL: test1:
 ; SSE2: andl $-16
define void @test2(i32 %t) nounwind {
   %tmp1210 = alloca i8, i32 16, align 4
   call void @llvm.memset.p0i8.i64(i8* %tmp1210, i8 0, i64 16, i32 4, i1 false)
   %x = alloca i8, i32 %t
   call void @dummy(i8* %x)
   ret void
 
 ; NOSSE-LABEL: test2:
 ; NOSSE-NOT: and
-; NOSSE: movl $0
+; NOSSE: movl %e{{[a-d]}}x,
 
 ; SSE1-LABEL: test2:
 ; SSE1: andl $-16
 ; SSE1: movl %esp, %esi
 ; SSE1: movaps
 
 ; SSE2-LABEL: test2:
 ; SSE2: andl $-16

test/CodeGen/X86/memset.ll

 ; RUN: llc < %s -march=x86 -mcpu=pentium2 -mtriple=i686-apple-darwin8.8.0 | FileCheck %s --check-prefix=X86
 ; RUN: llc < %s -march=x86 -mcpu=pentium3 -mtriple=i686-apple-darwin8.8.0 | FileCheck %s --check-prefix=XMM
 ; RUN: llc < %s -march=x86 -mcpu=bdver1   -mtriple=i686-apple-darwin8.8.0 | FileCheck %s --check-prefix=YMM
 
   %struct.x = type { i16, i16 }
 
 define void @t() nounwind  {
 entry:
   %up_mvd = alloca [8 x %struct.x]    ; <[8 x %struct.x]*> [#uses=2]
   %up_mvd116 = getelementptr [8 x %struct.x]* %up_mvd, i32 0, i32 0    ; <%struct.x*> [#uses=1]
   %tmp110117 = bitcast [8 x %struct.x]* %up_mvd to i8*    ; <i8*> [#uses=1]
 
   call void @llvm.memset.p0i8.i64(i8* %tmp110117, i8 0, i64 32, i32 8, i1 false)
-; X86: movl $0,
-; X86: movl $0,
-; X86: movl $0,
-; X86: movl $0,
-; X86: movl $0,
-; X86: movl $0,
-; X86: movl $0,
-; X86: movl $0,
-; X86-NOT: movl $0,
-; X86: ret
+; X86: movl [[REGISTER:%e[a-d]x]],
+; X86: movl [[REGISTER]],
+; X86: movl [[REGISTER]],
+; X86: movl [[REGISTER]],
+; X86: movl [[REGISTER]],
+; X86: movl [[REGISTER]],
+; X86: movl [[REGISTER]],
+; X86: movl [[REGISTER]],
 
 ; XMM: xorps %xmm{{[0-9]+}}, [[Z:%xmm[0-9]+]]
 ; XMM: movaps [[Z]],
 ; XMM: movaps [[Z]],
 ; XMM-NOT: movaps
 ; XMM: ret
 
 ; YMM: vxorps %ymm{{[0-9]+}}, %ymm{{[0-9]+}}, [[Z:%ymm[0-9]+]]
 ; YMM: vmovaps [[Z]],
 ; YMM-NOT: movaps
 ; YMM: ret
 
   call void @foo( %struct.x* %up_mvd116 ) nounwind 
   ret void
 }
 
 declare void @foo(%struct.x*)
 
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
 
 define void @PR15348(i8* %a) {
 ; Ensure that alignment of '0' in an @llvm.memset intrinsic results in
 ; unaligned loads and stores.
 ; XMM: PR15348
-; XMM: movb $0,
-; XMM: movl $0,
-; XMM: movl $0,
-; XMM: movl $0,
-; XMM: movl $0,
+; XMM: movl [[REGISTER:%e[a-d]x]],
+; XMM: movl [[REGISTER]],
+; XMM: movl [[REGISTER]],
+; XMM: movl [[REGISTER]],
   call void @llvm.memset.p0i8.i64(i8* %a, i8 0, i64 17, i32 0, i1 false)
   ret void
 }

test/CodeGen/X86/tlv-1.ll

 ; RUN: llc < %s -mtriple x86_64-apple-darwin -mcpu=core2 | FileCheck %s
 
 %struct.A = type { [48 x i8], i32, i32, i32 }
 
 @c = external thread_local global %struct.A, align 4
 
 define void @main() nounwind ssp {
 ; CHECK-LABEL: main:
 entry:
   call void @llvm.memset.p0i8.i64(i8* getelementptr inbounds (%struct.A* @c, i32 0, i32 0, i32 0), i8 0, i64 60, i32 1, i1 false)
   unreachable  
   ; CHECK: movq    _c@TLVP(%rip), %rdi
   ; CHECK-NEXT: callq   *(%rdi)
-  ; CHECK-NEXT: movl    $0, 56(%rax)
-  ; CHECK-NEXT: movq    $0, 48(%rax)
+  ; CHECK-NEXT: movl    %e[[REG:[a-d]x]], 56(%rax)
+  ; CHECK-NEXT: movq    %r[[REG]], 48(%rax)
 }
 
 ; rdar://10291355
 define i32 @test() nounwind readonly ssp {
 entry:
 ; CHECK-LABEL: test:
 ; CHECK: movq _a@TLVP(%rip),
 ; CHECK: callq *