Add nomerge function attribute to supress tail merge optimization in simplifyCFG

[zequanwu]

Summary

We want to add a way to avoid merging identical calls so as to keep the separate debug-information for those calls. There is also an asan usecase where having this attribute would be beneficial to avoid alternative work-arounds.
Here is the link to the feature request: https://bugs.llvm.org/show_bug.cgi?id=42783.
nomerge is different from noline. noinline prevents function from inlining at callsites, but nomerge prevents multiple identical calls from being merged into one.

This patch adds nomerge to disable the optimization in IR level. A followup patch will be needed to let backend understands nomerge and avoid tail merge at backend.

[lebedev.ri]

1. Tests missing
2. Why isn't noinline sufficient, why a whole new attribue?

[lebedev.ri]

+ llvm-commits

[zequanwu]

In D78659#1997528, @lebedev.ri wrote:

1. Tests missing
2. Why isn't noinline sufficient, why a whole new attribue?

1. Test added.
2. We want to avoid merging multiple call sites of same function, but noinline cannot achieve this. For example, we don't want to merge calls in i == 5 and i == 7 cases in the test case.

[asbirlea]

I think that expanding the patch description will help motivate this and clarify the use-cases for which this is useful, and how it differentiates from noinline.
Perhaps include that the attribute aims to avoid merging identical calls so as to keep the separate debug-information for those calls, and that there is an asan usecase where having this attribute would be beneficial to avoid alternative work-arounds.
If you have a link to the feature request for this, include that in the description as well, or include the motivation behind it.

Note there are other LLVM passes (beside SimplifyCFG) that may need to check for this argument to prevent optimizations (e.g. LICM does instruction sinking/hoising, add check ~LICM.cpp:1092?).

Include a comment in the clang/test/CodeGen/attr-nomerge.c test on the expected outcome of the test. Something like:
"The attribute no-merge prevents the 3 bar() calls from being merged into one inside foo. Check that there are still 3 tail calls."

[zequanwu]

Add check in LICM to prevent sink or hoist on nomerge call

[rnk]

In D78659#2003152, @zequanwu wrote:

Add check in LICM to prevent sink or hoist on nomerge call

Does sinking and hoisting remove the debug source location? I assumed that it wouldn't, but now after all the smooth stepping work, maybe it does.

Maybe we should audit for calls to DILocation::getMergedLocation, and use that to guide our changes. It would also be good to build an API that ensures that passes do not use getMergedLocation for instructions marked this way.

---

This also needs to be documented in llvm/docs/LangRef.rst with the other function attributes. Check out Arthur's preallocated patch for an example of that: D74651

clang/include/clang/Basic/AttrDocs.td

356–357 ↗

(On Diff #260039)

I think we need to expand on this. This is user facing documentation visible here:
http://clang.llvm.org/docs/AttributeReference.html

Here's a suggestion:
"Calls to functions marked `nomerge` will not be merged during optimization. This attribute can be used to prevent the optimizer from obscuring the source location of certain calls. For example, it will prevent tail merging otherwise identical code sequences that raise an exception or terminate the program. Tail merging normally reduces the precision of source location information, making stack traces less useful for debugging. This attribute gives the user control over the tradeoff between code size and debug information precision."

[zequanwu]

Split the the original differential to 2 smaller ones. This one add nomerge function attribute in IR level. Another one will add the attribute to let frontend recognize it.

[zequanwu]

Does sinking and hoisting remove the debug source location? I assumed that it wouldn't, but now after all the smooth stepping work, maybe it does.

Yes, both sinking and hoisting in simplifycfg remove the debug source location by Instruction::applyMergedLocation
sinking: https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L1646
hoisting: https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L1338

[zequanwu]

Add test case for preventing hoisting.

[rnk]

This looks pretty close, let's do one more iteration.

llvm/include/llvm/IR/InstrTypes.h

1718

Let's say "call" instead of "invoke". This method appears in the CallBase class. "Invoke" specifically refers to a call in LLVM IR which has an exceptional edge attached to it.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1305

It seems inconsistent that we don't apply the same logic to inline asm here. I think you should modify cannotMerge to return isInlineAsm() || hasFnAttr(...NoMerge), and then remove the isInlineAsm case below.

llvm/test/Transforms/SimplifyCFG/nomerge.ll

9

I would prefer retaining CHECK lines for the basic block labels to make it clear that these calls are all in separate blocks.

35

ditto regarding labels

[rnk]

I think this looks good, but I would like to get a second opinion from Alina (@asbirlea).

[asbirlea]

Thank you for adding this!

Please update first sentence in the description to:

We want to add a way to avoid merging identical calls so as to keep the separate debug-information for those calls. There is also an asan usecase where having this attribute would be beneficial to avoid alternative work-arounds.

[lebedev.ri]

llvm/include/llvm/IR/Attributes.td

106

Elsewhere we seem to be preventing any kind of movement,
not just disabling inlining of such functions if the call is a tailcall.

[zequanwu]

update comment.

[zequanwu]

add nomerge case in CodeExtractor.cpp

[zequanwu]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1305

This changes breaks the test AArch64/arm64-shrink-wrapping.ll because the inlineAsm cannot be deleted. I think we should only check for hasFnAttr(NoMerge) for CB1 and CB2.

[rnk]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1305

Before pushing this patch, I undid the change to cannotMerge so that this stayed the same and the test passed.

llvm/docs/LangRef.rst

``nofree``
     environments where the function might communicate the pointer to another thread
     which then deallocates the memory).
 ``noimplicitfloat``
     This attributes disables implicit floating-point instructions.
 ``noinline``
     This attribute indicates that the inliner should never inline this
     function in any situation. This attribute may not be used together
     with the ``alwaysinline`` attribute.
+``nomerge``
+    This attribute indicates that calls to this function should never be merged
+    during optimization. For example, it will prevent tail merging otherwise
+    identical code sequences that raise an exception or terminate the program.
+    Tail merging normally reduces the precision of source location information,
+    making stack traces less useful for debugging. This attribute gives the
+    user control over the tradeoff between code size and debug information
+    precision.
 ``nonlazybind``
     This attribute suppresses lazy symbol binding for the function. This
     may make calls to the function faster, at the cost of extra program
     startup time if the function is not called during program startup.
 ``noredzone``
     This attribute indicates that the code generator should not use a
     red zone, even if the target-specific ABI normally permits it.
 ``indirect-tls-seg-refs``

llvm/include/llvm/Bitcode/LLVMBitCodes.h

enum AttributeKindCodes {
   ATTR_KIND_SHADOWCALLSTACK = 58,
   ATTR_KIND_SPECULATIVE_LOAD_HARDENING = 59,
   ATTR_KIND_IMMARG = 60,
   ATTR_KIND_WILLRETURN = 61,
   ATTR_KIND_NOFREE = 62,
   ATTR_KIND_NOSYNC = 63,
   ATTR_KIND_SANITIZE_MEMTAG = 64,
   ATTR_KIND_PREALLOCATED = 65,
+  ATTR_KIND_NO_MERGE = 66,
 };
 
 enum ComdatSelectionKindCodes {
   COMDAT_SELECTION_KIND_ANY = 1,
   COMDAT_SELECTION_KIND_EXACT_MATCH = 2,
   COMDAT_SELECTION_KIND_LARGEST = 3,
   COMDAT_SELECTION_KIND_NO_DUPLICATES = 4,
   COMDAT_SELECTION_KIND_SAME_SIZE = 5,

llvm/include/llvm/IR/Attributes.td

 def NoImplicitFloat : EnumAttr<"noimplicitfloat">;
 
 /// inline=never.
 def NoInline : EnumAttr<"noinline">;
 
 /// Function is called early and/or often, so lazy binding isn't worthwhile.
 def NonLazyBind : EnumAttr<"nonlazybind">;
 
+/// Disable merging for call sites
+def NoMerge : EnumAttr<"nomerge">;
+
 /// Pointer is known to be not null.
 def NonNull : EnumAttr<"nonnull">;
 
 /// The function does not recurse.
 def NoRecurse : EnumAttr<"norecurse">;
 
 /// Disable redzone.
 def NoRedZone : EnumAttr<"noredzone">;

llvm/include/llvm/IR/InstrTypes.h

public:
   }
 
   /// Determine if the invoke cannot be duplicated.
   bool cannotDuplicate() const { return hasFnAttr(Attribute::NoDuplicate); }
   void setCannotDuplicate() {
     addAttribute(AttributeList::FunctionIndex, Attribute::NoDuplicate);
   }
 
+  /// Determine if the call cannot be tail merged.
+  bool cannotMerge() const { return hasFnAttr(Attribute::NoMerge); }
+
   /// Determine if the invoke is convergent
   bool isConvergent() const { return hasFnAttr(Attribute::Convergent); }
   void setConvergent() {
     addAttribute(AttributeList::FunctionIndex, Attribute::Convergent);
   }
   void setNotConvergent() {
     removeAttribute(AttributeList::FunctionIndex, Attribute::Convergent);
   }

llvm/lib/AsmParser/LLLexer.cpp

#define KEYWORD(STR)                                                           \
   KEYWORD(nobuiltin);
   KEYWORD(nocapture);
   KEYWORD(noduplicate);
   KEYWORD(nofree);
   KEYWORD(noimplicitfloat);
   KEYWORD(noinline);
   KEYWORD(norecurse);
   KEYWORD(nonlazybind);
+  KEYWORD(nomerge);
   KEYWORD(nonnull);
   KEYWORD(noredzone);
   KEYWORD(noreturn);
   KEYWORD(nosync);
   KEYWORD(nocf_check);
   KEYWORD(nounwind);
   KEYWORD(optforfuzzing);
   KEYWORD(optnone);

llvm/lib/AsmParser/LLParser.cpp

while (true) {
     case lltok::kw_naked: B.addAttribute(Attribute::Naked); break;
     case lltok::kw_nobuiltin: B.addAttribute(Attribute::NoBuiltin); break;
     case lltok::kw_noduplicate: B.addAttribute(Attribute::NoDuplicate); break;
     case lltok::kw_nofree: B.addAttribute(Attribute::NoFree); break;
     case lltok::kw_noimplicitfloat:
       B.addAttribute(Attribute::NoImplicitFloat); break;
     case lltok::kw_noinline: B.addAttribute(Attribute::NoInline); break;
     case lltok::kw_nonlazybind: B.addAttribute(Attribute::NonLazyBind); break;
+    case lltok::kw_nomerge: B.addAttribute(Attribute::NoMerge); break;
     case lltok::kw_noredzone: B.addAttribute(Attribute::NoRedZone); break;
     case lltok::kw_noreturn: B.addAttribute(Attribute::NoReturn); break;
     case lltok::kw_nosync: B.addAttribute(Attribute::NoSync); break;
     case lltok::kw_nocf_check: B.addAttribute(Attribute::NoCfCheck); break;
     case lltok::kw_norecurse: B.addAttribute(Attribute::NoRecurse); break;
     case lltok::kw_nounwind: B.addAttribute(Attribute::NoUnwind); break;
     case lltok::kw_optforfuzzing:
       B.addAttribute(Attribute::OptForFuzzing); break;
while (true) {
     case lltok::kw_jumptable:
     case lltok::kw_minsize:
     case lltok::kw_naked:
     case lltok::kw_nobuiltin:
     case lltok::kw_noduplicate:
     case lltok::kw_noimplicitfloat:
     case lltok::kw_noinline:
     case lltok::kw_nonlazybind:
+    case lltok::kw_nomerge:
     case lltok::kw_noredzone:
     case lltok::kw_noreturn:
     case lltok::kw_nocf_check:
     case lltok::kw_nounwind:
     case lltok::kw_optforfuzzing:
     case lltok::kw_optnone:
     case lltok::kw_optsize:
     case lltok::kw_returns_twice:
while (true) {
     case lltok::kw_jumptable:
     case lltok::kw_minsize:
     case lltok::kw_naked:
     case lltok::kw_nobuiltin:
     case lltok::kw_noduplicate:
     case lltok::kw_noimplicitfloat:
     case lltok::kw_noinline:
     case lltok::kw_nonlazybind:
+    case lltok::kw_nomerge:
     case lltok::kw_noredzone:
     case lltok::kw_noreturn:
     case lltok::kw_nocf_check:
     case lltok::kw_nounwind:
     case lltok::kw_optforfuzzing:
     case lltok::kw_optnone:
     case lltok::kw_optsize:
     case lltok::kw_returns_twice:

llvm/lib/AsmParser/LLToken.h

enum Kind {
   kw_nobuiltin,
   kw_nocapture,
   kw_noduplicate,
   kw_nofree,
   kw_noimplicitfloat,
   kw_noinline,
   kw_norecurse,
   kw_nonlazybind,
+  kw_nomerge,
   kw_nonnull,
   kw_noredzone,
   kw_noreturn,
   kw_nosync,
   kw_nocf_check,
   kw_nounwind,
   kw_optforfuzzing,
   kw_optnone,

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

static Attribute::AttrKind getAttrFromCode(uint64_t Code) {
   case bitc::ATTR_KIND_NOFREE:
     return Attribute::NoFree;
   case bitc::ATTR_KIND_NO_IMPLICIT_FLOAT:
     return Attribute::NoImplicitFloat;
   case bitc::ATTR_KIND_NO_INLINE:
     return Attribute::NoInline;
   case bitc::ATTR_KIND_NO_RECURSE:
     return Attribute::NoRecurse;
+  case bitc::ATTR_KIND_NO_MERGE:
+    return Attribute::NoMerge;
   case bitc::ATTR_KIND_NON_LAZY_BIND:
     return Attribute::NonLazyBind;
   case bitc::ATTR_KIND_NON_NULL:
     return Attribute::NonNull;
   case bitc::ATTR_KIND_DEREFERENCEABLE:
     return Attribute::Dereferenceable;
   case bitc::ATTR_KIND_DEREFERENCEABLE_OR_NULL:
     return Attribute::DereferenceableOrNull;

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

static uint64_t getAttrKindEncoding(Attribute::AttrKind Kind) {
   case Attribute::NoFree:
     return bitc::ATTR_KIND_NOFREE;
   case Attribute::NoImplicitFloat:
     return bitc::ATTR_KIND_NO_IMPLICIT_FLOAT;
   case Attribute::NoInline:
     return bitc::ATTR_KIND_NO_INLINE;
   case Attribute::NoRecurse:
     return bitc::ATTR_KIND_NO_RECURSE;
+  case Attribute::NoMerge:
+    return bitc::ATTR_KIND_NO_MERGE;
   case Attribute::NonLazyBind:
     return bitc::ATTR_KIND_NON_LAZY_BIND;
   case Attribute::NonNull:
     return bitc::ATTR_KIND_NON_NULL;
   case Attribute::Dereferenceable:
     return bitc::ATTR_KIND_DEREFERENCEABLE;
   case Attribute::DereferenceableOrNull:
     return bitc::ATTR_KIND_DEREFERENCEABLE_OR_NULL;

llvm/lib/IR/Attributes.cpp

std::string Attribute::getAsString(bool InAttrGrp) const {
   if (hasAttribute(Attribute::NoFree))
     return "nofree";
   if (hasAttribute(Attribute::NoImplicitFloat))
     return "noimplicitfloat";
   if (hasAttribute(Attribute::NoInline))
     return "noinline";
   if (hasAttribute(Attribute::NonLazyBind))
     return "nonlazybind";
+  if (hasAttribute(Attribute::NoMerge))
+    return "nomerge";
   if (hasAttribute(Attribute::NonNull))
     return "nonnull";
   if (hasAttribute(Attribute::NoRedZone))
     return "noredzone";
   if (hasAttribute(Attribute::NoReturn))
     return "noreturn";
   if (hasAttribute(Attribute::NoSync))
     return "nosync";

llvm/lib/IR/Verifier.cpp

void Verifier::visitModuleFlagCGProfileEntry(const MDOperand &MDO) {
   auto Count = dyn_cast_or_null<ConstantAsMetadata>(Node->getOperand(2));
   Assert(Count && Count->getType()->isIntegerTy(),
          "expected an integer constant", Node->getOperand(2));
 }
 
 /// Return true if this attribute kind only applies to functions.
 static bool isFuncOnlyAttr(Attribute::AttrKind Kind) {
   switch (Kind) {
+  case Attribute::NoMerge:
   case Attribute::NoReturn:
   case Attribute::NoSync:
   case Attribute::WillReturn:
   case Attribute::NoCfCheck:
   case Attribute::NoUnwind:
   case Attribute::NoInline:
   case Attribute::AlwaysInline:
   case Attribute::OptimizeForSize:

llvm/lib/Transforms/Utils/CodeExtractor.cpp

if (Attr.isStringAttribute()) {
       case Attribute::InaccessibleMemOnly:
       case Attribute::InaccessibleMemOrArgMemOnly:
       case Attribute::JumpTable:
       case Attribute::Naked:
       case Attribute::Nest:
       case Attribute::NoAlias:
       case Attribute::NoBuiltin:
       case Attribute::NoCapture:
+      case Attribute::NoMerge:
       case Attribute::NoReturn:
       case Attribute::NoSync:
       case Attribute::None:
       case Attribute::NonNull:
       case Attribute::Preallocated:
       case Attribute::ReadNone:
       case Attribute::ReadOnly:
       case Attribute::Returned:

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

do {
     auto *C2 = dyn_cast<CallInst>(I2);
     if (C1 && C2)
       if (C1->isMustTailCall() != C2->isMustTailCall())
         return Changed;
 
     if (!TTI.isProfitableToHoist(I1) || !TTI.isProfitableToHoist(I2))
       return Changed;
 
+    // If any of the two call sites has nomerge attribute, stop hoisting.
+    if (const auto *CB1 = dyn_cast<CallBase>(I1))
+      if (CB1->cannotMerge())
+        return Changed;
+    if (const auto *CB2 = dyn_cast<CallBase>(I2))
+      if (CB2->cannotMerge())
+        return Changed;
+
     if (isa<DbgInfoIntrinsic>(I1) || isa<DbgInfoIntrinsic>(I2)) {
       assert (isa<DbgInfoIntrinsic>(I1) && isa<DbgInfoIntrinsic>(I2));
       // The debug location is an integral part of a debug info intrinsic
       // and can't be separated from it or replaced.  Instead of attempting
       // to merge locations, simply hoist both copies of the intrinsic.
       BIParent->getInstList().splice(BI->getIterator(),
                                      BB1->getInstList(), I1);
       BIParent->getInstList().splice(BI->getIterator(),
for (auto *I : Insts) {
     // These instructions may change or break semantics if moved.
     if (isa<PHINode>(I) || I->isEHPad() || isa<AllocaInst>(I) ||
         I->getType()->isTokenTy())
       return false;
 
     // Conservatively return false if I is an inline-asm instruction. Sinking
     // and merging inline-asm instructions can potentially create arguments
     // that cannot satisfy the inline-asm constraints.
+    // If the instruction has nomerge attribute, return false.
     if (const auto *C = dyn_cast<CallBase>(I))
-      if (C->isInlineAsm())
+      if (C->isInlineAsm() || C->cannotMerge())
         return false;
 
     // Each instruction must have zero or one use.
     if (HasUse && !I->hasOneUse())
       return false;
     if (!HasUse && !I->user_empty())
       return false;
   }

llvm/test/Transforms/SimplifyCFG/nomerge.ll

+; RUN: opt < %s -O1 -S | FileCheck %s
+
+; The attribute nomerge prevents the 3 bar() calls from being sunk/hoisted into 
+; one inside a function. Check that there are still 3 tail calls.
+
+; Test case for preventing sinking
+; CHECK-LABEL: define void @sink
+; CHECK: if.then:
+; CHECK-NEXT: tail call void @bar()
+; CHECK: if.then2:
+; CHECK-NEXT: tail call void @bar()
+; CHECK: if.end3:
+; CHECK-NEXT: tail call void @bar()
+define void @sink(i32 %i) {
+entry:
+  switch i32 %i, label %if.end3 [
+    i32 5, label %if.then
+    i32 7, label %if.then2
+  ]
+
+if.then:
+  tail call void @bar() #0
+  br label %if.end3
+
+if.then2:
+  tail call void @bar() #0
+  br label %if.end3
+
+if.end3:
+  tail call void @bar() #0
+  ret void
+}
+
+; Test case for preventing hoisting
+; CHECK-LABEL: define void @hoist
+; CHECK: if.then:
+; CHECK-NEXT: tail call void @bar()
+; CHECK: if.then2:
+; CHECK-NEXT: tail call void @bar()
+; CHECK: if.end:
+; CHECK-NEXT: tail call void @bar()
+define void @hoist(i32 %i) {
+entry:
+  %i.addr = alloca i32, align 4
+  store i32 %i, i32* %i.addr, align 4
+  %0 = load i32, i32* %i.addr, align 4
+  %cmp = icmp eq i32 %0, 5
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  tail call void @bar() #1
+  unreachable
+
+if.else:
+  %1 = load i32, i32* %i.addr, align 4
+  %cmp1 = icmp eq i32 %i, 7
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  tail call void @bar() #1
+  unreachable
+
+if.end:
+  tail call void @bar() #1
+  unreachable
+}
+
+declare void @bar()
+
+attributes #0 = { nomerge }
+attributes #1 = { noreturn nomerge }