[RFC] Implement support for __builtin_memcmp_inline

[avieira]

Summary

Hi all,

This is my initial attempt at implementing a __builtin_memcmp_inline function in LLVM. The motivation is to use it in an optimized LLVM Libc implementation of memcmp whilst still using -ffreestanding and -fno-builtin-memcmp.

I haven't added any tests and I know for a fact this goes completely wrong if your memcmp size is big enough to hit the maximum number of loads, or if you compile for size. I just wanted to bring up this RFC before I start going down the wrong path.

My current thinking is the following:

1. Inline when compiling for size, the use of this builtin should force inlining where possible, regardless of global compilation options. My reasoning here is that if people really don't want to inline due to size considerations, don't use the inline variant of this builtin.
2. I'm split on what to do for when the memcmp size is large enough to hit the maximum number of loads. I think there are three options: a) We ignore the maximum number of loads and just generate a lot of code... (kind of the same strategy with memcpy) b) We use a call to memcmp (and issue a diagnostic saying we did so?) c) Error out I'm not keen on (c), I suspect (a) would probably make the most sense and hope that users of the builtin are sensible?

Let me know if there are any strong opinions on this. Please add other reviewers if you know they would have an interest in this.

Kind regards,
Andre

[efriedma]

The motivation here seems weaker than it was for memcpy. memcmp is much less fundamental to LLVM optimizations. It looks like the primary motivation here is to avoid duplicating the logic in llvm/lib/CodeGen/ExpandMemCmp.cpp ? But really, it isn't very much target-independent logic, and the only target-specific bit is the heuristic for load widths.

I'm split on what to do for when the memcmp size is large enough to hit the maximum number of loads. I think there are three options: a) We ignore the maximum number of loads and just generate a lot of code... (kind of the same strategy with memcpy) b) We use a call to memcmp (and issue a diagnostic saying we did so?) c) Error out I'm not keen on (c), I suspect (a) would probably make the most sense and hope that users of the builtin are sensible?

Or (d) generate a loop. But it would be a bunch of work to implement that, and it's not clear the users of the function would want that. (a) seems reasonable.

llvm/include/llvm/IR/Intrinsics.td

625

memcmp

[gchatelet]

In D105440#2858438, @efriedma wrote:

The motivation here seems weaker than it was for memcpy. memcmp is much less fundamental to LLVM optimizations. It looks like the primary motivation here is to avoid duplicating the logic in llvm/lib/CodeGen/ExpandMemCmp.cpp ? But really, it isn't very much target-independent logic, and the only target-specific bit is the heuristic for load widths.

I'd rather not duplicate logic in llvm/lib/CodeGen/ExpandMemCmp.cpp they may get out of sync.

I'm split on what to do for when the memcmp size is large enough to hit the maximum number of loads. I think there are three options: a) We ignore the maximum number of loads and just generate a lot of code... (kind of the same strategy with memcpy) b) We use a call to memcmp (and issue a diagnostic saying we did so?) c) Error out I'm not keen on (c), I suspect (a) would probably make the most sense and hope that users of the builtin are sensible?

Or (d) generate a loop. But it would be a bunch of work to implement that, and it's not clear the users of the function would want that. (a) seems reasonable.

I concur, (a) is the way to go.
Loop generation is an option but it's much more work and involves spreading the logic between layers, I would prefer not going in that direction if possible.
The goal here is to provide building block to create libc memory functions, it's unlikely that the size is going to be big and it is a requirement that it should never call the libc (or it will stackoverflow (or loop infinitely if tail recursion)).
Also the size has to be statically known so I'd be surprised if someone would want to compare 1KiB of memory this way... and the loop is easy to implement on top of the builtin.

[efriedma]

In D105440#2859993, @gchatelet wrote:

In D105440#2858438, @efriedma wrote:

The motivation here seems weaker than it was for memcpy. memcmp is much less fundamental to LLVM optimizations. It looks like the primary motivation here is to avoid duplicating the logic in llvm/lib/CodeGen/ExpandMemCmp.cpp ? But really, it isn't very much target-independent logic, and the only target-specific bit is the heuristic for load widths.

I'd rather not duplicate logic in llvm/lib/CodeGen/ExpandMemCmp.cpp they may get out of sync.

The problem, from my perspective, is that you'll have to duplicate the logic to some extent anyway. Even if __builtin_memcmp_inline is technically available, that doesn't let you access the underlying heuristics, so you'll need special-case logic for every target anyway.

[gchatelet]

In D105440#2860255, @efriedma wrote:

In D105440#2859993, @gchatelet wrote:

In D105440#2858438, @efriedma wrote:

The motivation here seems weaker than it was for memcpy. memcmp is much less fundamental to LLVM optimizations. It looks like the primary motivation here is to avoid duplicating the logic in llvm/lib/CodeGen/ExpandMemCmp.cpp ? But really, it isn't very much target-independent logic, and the only target-specific bit is the heuristic for load widths.

I'd rather not duplicate logic in llvm/lib/CodeGen/ExpandMemCmp.cpp they may get out of sync.

The problem, from my perspective, is that you'll have to duplicate the logic to some extent anyway.

I see, we'll probably have to extract the shared logic in one or more libraries then.

Even if __builtin_memcmp_inline is technically available, that doesn't let you access the underlying heuristics, so you'll need special-case logic for every target anyway.

Yes indeed, availability of vector extensions could lead to different algorithms so we need to access target specific logic.

[avieira]

In D105440#2861293, @gchatelet wrote:

In D105440#2860255, @efriedma wrote:

In D105440#2859993, @gchatelet wrote:

In D105440#2858438, @efriedma wrote:

The motivation here seems weaker than it was for memcpy. memcmp is much less fundamental to LLVM optimizations. It looks like the primary motivation here is to avoid duplicating the logic in llvm/lib/CodeGen/ExpandMemCmp.cpp ? But really, it isn't very much target-independent logic, and the only target-specific bit is the heuristic for load widths.

I'd rather not duplicate logic in llvm/lib/CodeGen/ExpandMemCmp.cpp they may get out of sync.

The problem, from my perspective, is that you'll have to duplicate the logic to some extent anyway.

I see, we'll probably have to extract the shared logic in one or more libraries then.

I initially benchmarked memcmp using the scalar building blocks and I was seeing better codegen with the builtins. I couldn't quite remember what the differences were so I decided to benchmark the scalar implementations again and they seem to perform fairly similar now, there is a small codechange around size 3, but the codegen actually seems better to me with the scalar implementation. I may have been using an older llvm or an earlier version of the building blocks.

Even if __builtin_memcmp_inline is technically available, that doesn't let you access the underlying heuristics, so you'll need special-case logic for every target anyway.

Yes indeed, availability of vector extensions could lead to different algorithms so we need to access target specific logic.

I am happy to drop this RFC if there are no objections.

[gchatelet]

I initially benchmarked memcmp using the scalar building blocks and I was seeing better codegen with the builtins. I couldn't quite remember what the differences were so I decided to benchmark the scalar implementations again and they seem to perform fairly similar now, there is a small codechange around size 3, but the codegen actually seems better to me with the scalar implementation. I may have been using an older llvm or an earlier version of the building blocks.
I am happy to drop this RFC if there are no objections.

Ok then let's drop it.
I think we still need to improve the state of memcmp in LLVM but let's decouple the two issues.

clang/include/clang/Basic/Builtins.def

 BUILTIN(__builtin_bcmp, "ivC*vC*z", "Fn")
 BUILTIN(__builtin_bcopy, "vv*v*z", "n")
 BUILTIN(__builtin_bzero, "vv*z", "nF")
 BUILTIN(__builtin_fprintf, "iP*cC*.", "Fp:1:")
 BUILTIN(__builtin_free, "vv*", "nF")
 BUILTIN(__builtin_malloc, "v*z", "nF")
 BUILTIN(__builtin_memchr, "v*vC*iz", "nF")
 BUILTIN(__builtin_memcmp, "ivC*vC*z", "nF")
+BUILTIN(__builtin_memcmp_inline, "ivC*vC*Iz", "nF")
 BUILTIN(__builtin_memcpy, "v*v*vC*z", "nF")
 BUILTIN(__builtin_memcpy_inline, "vv*vC*Iz", "nt")
 BUILTIN(__builtin_memmove, "v*v*vC*z", "nF")
 BUILTIN(__builtin_mempcpy, "v*v*vC*z", "nF")
 BUILTIN(__builtin_memset, "v*v*iz", "nF")
 BUILTIN(__builtin_printf, "icC*.", "Fp:0:")
 BUILTIN(__builtin_stpcpy, "c*c*cC*", "nF")
 BUILTIN(__builtin_stpncpy, "c*c*cC*z", "nF")

clang/lib/CodeGen/CGBuilder.h

public:
 
   using CGBuilderBaseTy::CreateMemCpyInline;
   llvm::CallInst *CreateMemCpyInline(Address Dest, Address Src, uint64_t Size) {
     return CreateMemCpyInline(
         Dest.getPointer(), Dest.getAlignment().getAsAlign(), Src.getPointer(),
         Src.getAlignment().getAsAlign(), getInt64(Size));
   }
 
+  using CGBuilderBaseTy::CreateMemCmpInline;
+  llvm::CallInst *CreateMemCmpInline(Address Lhs, Address Rhs, uint64_t Size,
+             llvm::Type *RetType) {
+    return CreateMemCmpInline(
+        Lhs.getPointer(), Rhs.getPointer(), getInt64(Size), RetType);
+  }
+
   using CGBuilderBaseTy::CreateMemMove;
   llvm::CallInst *CreateMemMove(Address Dest, Address Src, llvm::Value *Size,
                                 bool IsVolatile = false) {
     return CreateMemMove(Dest.getPointer(), Dest.getAlignment().getAsAlign(),
                          Src.getPointer(), Src.getAlignment().getAsAlign(),
                          Size, IsVolatile);
   }
 

clang/lib/CodeGen/CGBuiltin.cpp

case Builtin::BI__builtin_memcpy_inline: {
     EmitNonNullArgCheck(RValue::get(Dest.getPointer()), E->getArg(0)->getType(),
                         E->getArg(0)->getExprLoc(), FD, 0);
     EmitNonNullArgCheck(RValue::get(Src.getPointer()), E->getArg(1)->getType(),
                         E->getArg(1)->getExprLoc(), FD, 1);
     Builder.CreateMemCpyInline(Dest, Src, Size);
     return RValue::get(nullptr);
   }
 
+  case Builtin::BI__builtin_memcmp_inline: {
+    Address Lhs = EmitPointerWithAlignment(E->getArg(0));
+    Address Rhs = EmitPointerWithAlignment(E->getArg(1));
+    uint64_t Size =
+        E->getArg(2)->EvaluateKnownConstInt(getContext()).getZExtValue();
+    EmitNonNullArgCheck(RValue::get(Lhs.getPointer()), E->getArg(0)->getType(),
+                        E->getArg(0)->getExprLoc(), FD, 0);
+    EmitNonNullArgCheck(RValue::get(Rhs.getPointer()), E->getArg(1)->getType(),
+                        E->getArg(1)->getExprLoc(), FD, 1);
+    QualType T = E->getType();
+    llvm::IntegerType *RetType =
+        llvm::IntegerType::get(getLLVMContext(), getContext().getTypeSize(T));
+    return RValue::get(Builder.CreateMemCmpInline(Lhs, Rhs, Size, RetType));
+  }
+
   case Builtin::BI__builtin_char_memchr:
     BuiltinID = Builtin::BI__builtin_memchr;
     break;
 
   case Builtin::BI__builtin___memcpy_chk: {
     // fold __builtin_memcpy_chk(x, y, cst1, cst2) to memcpy iff cst1<=cst2.
     Expr::EvalResult SizeResult, DstSizeResult;
     if (!E->getArg(2)->EvaluateAsInt(SizeResult, CGM.getContext()) ||

clang/lib/Sema/SemaChecking.cpp

case Builtin::BI__builtin_memcpy_inline: {
     if (SizeOp->isValueDependent())
       break;
     if (!SizeOp->EvaluateKnownConstInt(Context).isNullValue()) {
       CheckNonNullArgument(*this, TheCall->getArg(0), TheCall->getExprLoc());
       CheckNonNullArgument(*this, TheCall->getArg(1), TheCall->getExprLoc());
     }
     break;
   }
+  case Builtin::BI__builtin_memcmp_inline: {
+    clang::Expr *SizeOp = TheCall->getArg(2);
+    // We warn about comparing`nullptr` pointers when `size` is greater than 0.
+    // When `size` is value dependent we cannot evaluate its value so we bail
+    // out.
+    if (SizeOp->isValueDependent())
+      break;
+    if (!SizeOp->EvaluateKnownConstInt(Context).isNullValue()) {
+      CheckNonNullArgument(*this, TheCall->getArg(0), TheCall->getExprLoc());
+      CheckNonNullArgument(*this, TheCall->getArg(1), TheCall->getExprLoc());
+    }
+    break;
+  }
 #define BUILTIN(ID, TYPE, ATTRS)
 #define ATOMIC_BUILTIN(ID, TYPE, ATTRS) \
   case Builtin::BI##ID: \
     return SemaAtomicOpsOverloaded(TheCallResult, AtomicExpr::AO##ID);
 #include "clang/Basic/Builtins.def"
   case Builtin::BI__annotation:
     if (SemaBuiltinMSVCAnnotation(*this, TheCall))
       return ExprError();

llvm/include/llvm/IR/IRBuilder.h

CallInst *CreateMemCpy(Value *Dst, MaybeAlign DstAlign, Value *Src,
                          MDNode *NoAliasTag = nullptr) {
     return CreateMemTransferInst(Intrinsic::memcpy, Dst, DstAlign, Src,
                                  SrcAlign, Size, isVolatile, TBAATag,
                                  TBAAStructTag, ScopeTag, NoAliasTag);
   }
 
   CallInst *CreateMemCpyInline(Value *Dst, MaybeAlign DstAlign, Value *Src,
                                MaybeAlign SrcAlign, Value *Size);
+  CallInst *CreateMemCmpInline(Value *Lhs, Value *Rhs, Value *Size,
+             Type *RetType);
 
   /// Create and insert an element unordered-atomic memcpy between the
   /// specified pointers.
   ///
   /// DstAlign/SrcAlign are the alignments of the Dst/Src pointers, respectively.
   ///
   /// If the pointers aren't i8*, they will be converted.  If a TBAA tag is
   /// specified, it will be added to the instruction. Likewise with alias.scope

llvm/include/llvm/IR/Intrinsics.td

def int_memcpy_inline
     : Intrinsic<[],
       [llvm_anyptr_ty, llvm_anyptr_ty, llvm_anyint_ty, llvm_i1_ty],
       [IntrArgMemOnly, IntrWillReturn, IntrNoFree,
        NoCapture<ArgIndex<0>>, NoCapture<ArgIndex<1>>,
        NoAlias<ArgIndex<0>>, NoAlias<ArgIndex<1>>,
        WriteOnly<ArgIndex<0>>, ReadOnly<ArgIndex<1>>,
        ImmArg<ArgIndex<2>>, ImmArg<ArgIndex<3>>]>;
 
+// Memcpy semantic that is guaranteed to be inlined.
+// In particular this means that the generated code is not allowed to call any
+// external function.
+// The third argument (specifying the size) must be a constant.
+def int_memcmp_inline
+    : Intrinsic<[llvm_anyint_ty],
+      [llvm_anyptr_ty, llvm_anyptr_ty, llvm_anyint_ty],
+      [IntrArgMemOnly, IntrWillReturn, IntrNoFree,
+       NoCapture<ArgIndex<0>>, NoCapture<ArgIndex<1>>,
+       ReadOnly<ArgIndex<0>>, ReadOnly<ArgIndex<1>>,
+       ImmArg<ArgIndex<2>>]>;
+
 def int_memmove : Intrinsic<[],
                             [llvm_anyptr_ty, llvm_anyptr_ty, llvm_anyint_ty,
                              llvm_i1_ty],
                             [IntrArgMemOnly, IntrWillReturn, IntrNoFree,
                              NoCapture<ArgIndex<0>>, NoCapture<ArgIndex<1>>,
                              WriteOnly<ArgIndex<0>>, ReadOnly<ArgIndex<1>>,
                              ImmArg<ArgIndex<3>>]>;
 def int_memset  : Intrinsic<[],

llvm/lib/CodeGen/ExpandMemCmp.cpp

 ///  br label %endblock
 /// endblock:                                         ; preds = %res_block,
 /// %loadbb3
 ///  %phi.res = phi i32 [ %48, %loadbb3 ], [ %11, %res_block ]
 ///  ret i32 %phi.res
 static bool expandMemCmp(CallInst *CI, const TargetTransformInfo *TTI,
                          const TargetLowering *TLI, const DataLayout *DL,
                          ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI,
-                         DomTreeUpdater *DTU) {
+                         DomTreeUpdater *DTU, bool IsInline) {
   NumMemCmpCalls++;
 
   // Early exit from expansion if -Oz.
-  if (CI->getFunction()->hasMinSize())
+  if (!IsInline && CI->getFunction()->hasMinSize())
     return false;
 
   // Early exit from expansion if size is not a constant.
   ConstantInt *SizeCast = dyn_cast<ConstantInt>(CI->getArgOperand(2));
   if (!SizeCast) {
     NumMemCmpNotConstant++;
     return false;
   }
bool ExpandMemCmpPass::runOnBlock(BasicBlock &BB, const TargetLibraryInfo *TLI,
                                   BlockFrequencyInfo *BFI,
                                   DomTreeUpdater *DTU) {
   for (Instruction& I : BB) {
     CallInst *CI = dyn_cast<CallInst>(&I);
     if (!CI) {
       continue;
     }
     LibFunc Func;
-    if (TLI->getLibFunc(*CI, Func) &&
-        (Func == LibFunc_memcmp || Func == LibFunc_bcmp) &&
-        expandMemCmp(CI, TTI, TL, &DL, PSI, BFI, DTU)) {
+    auto *II = dyn_cast<IntrinsicInst>(CI);
+    bool IsInline = II && II->getIntrinsicID() == Intrinsic::memcmp_inline;
+    if (((TLI->getLibFunc(*CI, Func) &&
+          (Func == LibFunc_memcmp || Func == LibFunc_bcmp)) ||
+         IsInline) &&
+        expandMemCmp(CI, TTI, TL, &DL, PSI, BFI, DTU, IsInline)) {
       return true;
     }
   }
   return false;
 }
 
 PreservedAnalyses
 ExpandMemCmpPass::runImpl(Function &F, const TargetLibraryInfo *TLI,

llvm/lib/IR/IRBuilder.cpp

CallInst *IRBuilderBase::CreateMemCpyInline(Value *Dst, MaybeAlign DstAlign,
   if (DstAlign)
     MCI->setDestAlignment(*DstAlign);
   if (SrcAlign)
     MCI->setSourceAlignment(*SrcAlign);
 
   return CI;
 }
 
+CallInst *IRBuilderBase::CreateMemCmpInline(Value *Lhs, Value *Rhs, Value *Size,
+                                            Type *RetType) {
+  Lhs = getCastedInt8PtrValue(Lhs);
+  Rhs = getCastedInt8PtrValue(Rhs);
+
+  Value *Ops[] = {Lhs, Rhs, Size};
+  Type *Tys[] = {RetType, Lhs->getType(), Rhs->getType(), Size->getType()};
+  Function *F = BB->getParent();
+  Module *M = F->getParent();
+  Function *TheFn = Intrinsic::getDeclaration(M, Intrinsic::memcmp_inline, Tys);
+
+  CallInst *CI = createCallHelper(TheFn, Ops, this);
+  return CI;
+}
+
 CallInst *IRBuilderBase::CreateElementUnorderedAtomicMemCpy(
     Value *Dst, Align DstAlign, Value *Src, Align SrcAlign, Value *Size,
     uint32_t ElementSize, MDNode *TBAATag, MDNode *TBAAStructTag,
     MDNode *ScopeTag, MDNode *NoAliasTag) {
   assert(DstAlign >= ElementSize &&
          "Pointer alignment must be at least element size");
   assert(SrcAlign >= ElementSize &&
          "Pointer alignment must be at least element size");

llvm/lib/Transforms/Utils/MemoryOpRemark.cpp

 MemoryOpRemark::~MemoryOpRemark() = default;
 
 bool MemoryOpRemark::canHandle(const Instruction *I, const TargetLibraryInfo &TLI) {
   if (isa<StoreInst>(I))
     return true;
 
   if (auto *II = dyn_cast<IntrinsicInst>(I)) {
     switch (II->getIntrinsicID()) {
+    case Intrinsic::memcmp_inline:
     case Intrinsic::memcpy_inline:
     case Intrinsic::memcpy:
     case Intrinsic::memmove:
     case Intrinsic::memset:
     case Intrinsic::memcpy_element_unordered_atomic:
     case Intrinsic::memmove_element_unordered_atomic:
     case Intrinsic::memset_element_unordered_atomic:
       return true;
void MemoryOpRemark::visitUnknown(const Instruction &I) {
   ORE.emit(*R);
 }
 
 void MemoryOpRemark::visitIntrinsicCall(const IntrinsicInst &II) {
   SmallString<32> CallTo;
   bool Atomic = false;
   bool Inline = false;
   switch (II.getIntrinsicID()) {
+  case Intrinsic::memcmp_inline:
+    CallTo = "memcmp";
+    Inline = true;
+    break;
   case Intrinsic::memcpy_inline:
     CallTo = "memcpy";
     Inline = true;
     break;
   case Intrinsic::memcpy:
     CallTo = "memcpy";
     break;
   case Intrinsic::memmove:
void MemoryOpRemark::visitIntrinsicCall(const IntrinsicInst &II) {
   case Intrinsic::memcpy_element_unordered_atomic:
     visitPtr(II.getOperand(1), /*IsRead=*/true, *R);
     visitPtr(II.getOperand(0), /*IsRead=*/false, *R);
     break;
   case Intrinsic::memset:
   case Intrinsic::memset_element_unordered_atomic:
     visitPtr(II.getOperand(0), /*IsRead=*/false, *R);
     break;
+  case Intrinsic::memcmp_inline:
+    visitPtr(II.getOperand(1), /*IsRead=*/true, *R);
+    visitPtr(II.getOperand(0), /*IsRead=*/true, *R);
+    break;
   }
   inlineVolatileOrAtomicWithExtraArgs(&Inline, Volatile, Atomic, *R);
   ORE.emit(*R);
 }
 
 void MemoryOpRemark::visitCall(const CallInst &CI) {
   Function *F = CI.getCalledFunction();
   if (!F)