[Inliner] Handle convergence control when inlining a call

[sameerds]

Summary

When a convergencectrl token is passed to a convergent call, and the called
function in turn calls the entry intrinsic, the intrinsic is now now replaced
with the convergencectrl token.

The spec requires the following check:

A call from function F to function G can be inlined only if:
- at least one of F or G does not make any convergent calls, or,
- both F and G make the same kind of convergent calls: controlled or
  uncontrolled.

But this change does not implement this complete check. A proper implemenation
require a whole new analysis that identifies convergence in every function. For
now, we skip that and just do a cursory check for the entry intrinsic. The
underlying assumption is that in a compiler flow that fully implements
convergence control tokens, there is no mixing of controlled and uncontrolled
convergent operations in the whole program.

This is a reboot of the original change D85606 by
Nicolai Haehnle <[e-mail]>.

[arsenm]

llvm/lib/Analysis/ConvergenceControlUsage.cpp

34 ↗

(On Diff #529543)

Don't think you need has_value()

llvm/test/Transforms/Inline/convergence-inline.ll

3

Pre-commit test with baseline checks

102

Don't use branch on undef

107

Add indirect with convergence bundle call? Also a recursive call?

109

Test where a convergent call is passed as an argument to a call that also has a convergence token

[sameerds]

• rebase
• add more tests

[sameerds]

llvm/test/Transforms/Inline/convergence-inline.ll

3

I didn't understand. Without the changes to the inliner, the IR after inlining will fail the verifier in most cases. What would be the value of having such a test?

[nhaehnle]

The proliferation of the ConvergenceControlUsage makes me a bit uncomfortable. It adds the overhead of an additional iteration over entire functions every time a function is inlined or perhaps the inlining is even attempted. And the only thing we get in exchange is a safety check against mixing controlled and uncontrolled convergent operations. Is it really worth it? I'd expect that in general, a compiler either always emits controlled or always emits uncontrolled operations, which means this isn't actually a scenario we need to worry about too much.

llvm/lib/Transforms/Utils/InlineFunction.cpp

2289–2298

This looks like it's making an assumption that the convergence.entry is the very first instruction. Do we really want to enforce that? Definitely needs a verifier check in that case...

[sameerds]

• rebase
• eliminate ConvergenceControlUsage

[sameerds]

In D152431#4433182, @nhaehnle wrote:

The proliferation of the ConvergenceControlUsage makes me a bit uncomfortable. It adds the overhead of an additional iteration over entire functions every time a function is inlined or perhaps the inlining is even attempted. And the only thing we get in exchange is a safety check against mixing controlled and uncontrolled convergent operations. Is it really worth it? I'd expect that in general, a compiler either always emits controlled or always emits uncontrolled operations, which means this isn't actually a scenario we need to worry about too much.

Agreed. I've removed that analysis and replaced it with a simple check that requires a token operand when the called function contains the entry intrinsic. This is clearly incomplete, but a useful check to have. See comments in InlineFunction.cpp and also in the review description.

Just a thought: Eventually, if we do want to disallow inlining in the presence of both kinds of convergence, we could repurpose the convergent attribute by first making all functions convergent by default. Then we can say that uncontrolled convergent calls are only allowed in a function with the "legacy" convergent attribute. The same function cannot contain controlled convergent calls, including the entry intrinsic.

llvm/lib/Transforms/Utils/InlineFunction.cpp

2289–2298

Yes. We enforce it in D147116.

[nhaehnle]

Thanks, I like this much more :)

llvm/lib/Transforms/Utils/InlineFunction.cpp

2289–2298

Okay thanks, I missed that the first time around.

This needs a little more thought on the various getFirstWhatever methods in BasicBlock though. My main immediate concern is with IRBuilder::setInsertPointPastAllocas, which uses BasicBlock::getFirstNonPHIOrDbgOrAlloca. We'd want this to set the insert point past the entry/loop intrinsic and any allocas.

I wouldn't be surprised if some of the other helpers there should also be adjusted -- for example, getFirstInsertionPt -- but that is less clear to me.

[sameerds]

• rebase

[sameerds]

llvm/lib/Transforms/Utils/InlineFunction.cpp

2289–2298

Sure. We want to incorporate the rules for these intrinsics in all the convenient places, we can do that as a follow-up, right? This change solely focuses on inlining of function calls.

llvm/lib/Transforms/Utils/InlineFunction.cpp

llvm::InlineResult llvm::InlineFunction(CallBase &CB, InlineFunctionInfo &IFI,
 
   Function *CalledFunc = CB.getCalledFunction();
   if (!CalledFunc ||               // Can't inline external function or indirect
       CalledFunc->isDeclaration()) // call!
     return InlineResult::failure("external or indirect");
 
   // The inliner does not know how to inline through calls with operand bundles
   // in general ...
+  Value *ConvergenceControlToken = nullptr;
   if (CB.hasOperandBundles()) {
     for (int i = 0, e = CB.getNumOperandBundles(); i != e; ++i) {
-      uint32_t Tag = CB.getOperandBundleAt(i).getTagID();
+      auto OBUse = CB.getOperandBundleAt(i);
+      uint32_t Tag = OBUse.getTagID();
       // ... but it knows how to inline through "deopt" operand bundles ...
       if (Tag == LLVMContext::OB_deopt)
         continue;
       // ... and "funclet" operand bundles.
       if (Tag == LLVMContext::OB_funclet)
         continue;
       if (Tag == LLVMContext::OB_clang_arc_attachedcall)
         continue;
       if (Tag == LLVMContext::OB_kcfi)
         continue;
+      if (Tag == LLVMContext::OB_convergencectrl) {
+        ConvergenceControlToken = OBUse.Inputs[0].get();
+        continue;
+      }
 
       return InlineResult::failure("unsupported operand bundle");
     }
   }
 
+  // FIXME: The check below is redundant and incomplete. According to spec, if a
+  // convergent call is missing a token, then the caller is using uncontrolled
+  // convergence. If the callee has an entry intrinsic, then the callee is using
+  // controlled convergence, and the call cannot be inlined. A proper
+  // implemenation of this check requires a whole new analysis that identifies
+  // convergence in every function. For now, we skip that and just do this one
+  // cursory check. The underlying assumption is that in a compiler flow that
+  // fully implements convergence control tokens, there is no mixing of
+  // controlled and uncontrolled convergent operations in the whole program.
+  if (CB.isConvergent()) {
+    auto *I = CalledFunc->getEntryBlock().getFirstNonPHI();
+    if (auto *IntrinsicCall = dyn_cast<IntrinsicInst>(I)) {
+      if (IntrinsicCall->getIntrinsicID() ==
+          Intrinsic::experimental_convergence_entry) {
+        if (!ConvergenceControlToken) {
+          return InlineResult::failure(
+              "convergent call needs convergencectrl operand");
+        }
+      }
+    }
+  }
+
   // If the call to the callee cannot throw, set the 'nounwind' flag on any
   // calls that we inline.
   bool MarkNoUnwind = CB.doesNotThrow();
 
   BasicBlock *OrigBB = CB.getParent();
   Function *Caller = OrigBB->getParent();
 
   // Do not inline strictfp function into non-strictfp one. It would require
Function::iterator FirstNewBlock;
     if (IFI.GetAssumptionCache)
       for (BasicBlock &NewBlock :
            make_range(FirstNewBlock->getIterator(), Caller->end()))
         for (Instruction &I : NewBlock)
           if (auto *II = dyn_cast<AssumeInst>(&I))
             IFI.GetAssumptionCache(*Caller).registerAssumption(II);
   }
 
+  if (ConvergenceControlToken) {
+    auto *I = FirstNewBlock->getFirstNonPHI();
+    if (auto *IntrinsicCall = dyn_cast<IntrinsicInst>(I)) {
+      if (IntrinsicCall->getIntrinsicID() ==
+          Intrinsic::experimental_convergence_entry) {
+        IntrinsicCall->replaceAllUsesWith(ConvergenceControlToken);
+        IntrinsicCall->eraseFromParent();
+      }
+    }
+  }
+
   // If there are any alloca instructions in the block that used to be the entry
   // block for the callee, move them to the entry block of the caller.  First
   // calculate which instruction they should be inserted before.  We insert the
   // instructions at the end of the current alloca list.
   {
     BasicBlock::iterator InsertPoint = Caller->begin()->begin();
     for (BasicBlock::iterator I = FirstNewBlock->begin(),
          E = FirstNewBlock->end(); I != E; ) {

llvm/test/Transforms/Inline/convergence-inline.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes='cgscc(inline)' -S %s | FileCheck %s
+
+define void @nonconvergent_callee() alwaysinline {
+; CHECK-LABEL: @nonconvergent_callee(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOKEN:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f(i32 0) [ "convergencectrl"(token [[TOKEN]]) ]
+; CHECK-NEXT:    ret void
+;
+entry:
+  %token = call token @llvm.experimental.convergence.anchor()
+  call void @f(i32 0) [ "convergencectrl"(token %token) ]
+  ret void
+}
+
+define void @convergent_callee(i32 %v) convergent alwaysinline {
+; CHECK-LABEL: @convergent_callee(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOKEN:%.*]] = call token @llvm.experimental.convergence.entry()
+; CHECK-NEXT:    call void @f(i32 [[V:%.*]]) [ "convergencectrl"(token [[TOKEN]]) ]
+; CHECK-NEXT:    ret void
+;
+entry:
+  %token = call token @llvm.experimental.convergence.entry()
+  call void @f(i32 %v) [ "convergencectrl"(token %token) ]
+  ret void
+}
+
+define void @test_nonconvergent() {
+; CHECK-LABEL: @test_nonconvergent(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOKEN_I:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f(i32 0) [ "convergencectrl"(token [[TOKEN_I]]) ]
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void @nonconvergent_callee()
+  ret void
+}
+
+define void @test_convergent_basic(i1 %cond) {
+; CHECK-LABEL: @test_convergent_basic(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOKEN:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[THEN:%.*]], label [[END:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    call void @f(i32 0) [ "convergencectrl"(token [[TOKEN]]) ]
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %token = call token @llvm.experimental.convergence.anchor()
+  br i1 %cond, label %then, label %end
+
+then:
+  call void @convergent_callee(i32 0) [ "convergencectrl"(token %token) ]
+  br label %end
+
+end:
+  ret void
+}
+
+define void @test_convergent_no_token(i1 %cond) convergent {
+; CHECK-LABEL: @test_convergent_no_token(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @convergent_callee(i32 0)
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void @convergent_callee(i32 0)
+  ret void
+}
+
+define void @test_convergent_multiple() convergent {
+; CHECK-LABEL: @test_convergent_multiple(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOKEN:%.*]] = call token @llvm.experimental.convergence.entry()
+; CHECK-NEXT:    call void @f(i32 0) [ "convergencectrl"(token [[TOKEN]]) ]
+; CHECK-NEXT:    call void @f(i32 1) [ "convergencectrl"(token [[TOKEN]]) ]
+; CHECK-NEXT:    call void @f(i32 2) [ "convergencectrl"(token [[TOKEN]]) ]
+; CHECK-NEXT:    ret void
+;
+entry:
+  %token = call token @llvm.experimental.convergence.entry()
+  call void @convergent_callee(i32 0) [ "convergencectrl"(token %token) ]
+  call void @convergent_callee(i32 1) [ "convergencectrl"(token %token) ]
+  call void @convergent_callee(i32 2) [ "convergencectrl"(token %token) ]
+  ret void
+}
+
+define void @test_convergent_loop(i1 %cond) {
+; CHECK-LABEL: @test_convergent_loop(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOKEN:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[HDR:%.*]], label [[END:%.*]]
+; CHECK:       hdr:
+; CHECK-NEXT:    [[TOK_LOOP:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOKEN]]) ]
+; CHECK-NEXT:    call void @f(i32 0) [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    br i1 [[COND]], label [[HDR]], label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %token = call token @llvm.experimental.convergence.anchor()
+  br i1 %cond, label %hdr, label %end
+
+hdr:
+  %tok.loop = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %token) ]
+  call void @convergent_callee(i32 0) [ "convergencectrl"(token %tok.loop) ]
+  br i1 %cond, label %hdr, label %end
+
+end:
+  ret void
+}
+
+define void @make_indirect_call(ptr %f, i32 %x) convergent alwaysinline {
+; CHECK-LABEL: @make_indirect_call(
+; CHECK-NEXT:    [[TOKEN:%.*]] = call token @llvm.experimental.convergence.entry()
+; CHECK-NEXT:    call void [[F:%.*]](i32 [[X:%.*]]) #[[ATTR2:[0-9]+]] [ "convergencectrl"(token [[TOKEN]]) ]
+; CHECK-NEXT:    ret void
+;
+  %token = call token @llvm.experimental.convergence.entry()
+  call void %f(i32 %x) convergent [ "convergencectrl"(token %token) ]
+  ret void
+}
+
+define void @test_indirect_call() convergent {
+; CHECK-LABEL: @test_indirect_call(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOKEN:%.*]] = call token @llvm.experimental.convergence.entry()
+; CHECK-NEXT:    call void @f(i32 0) [ "convergencectrl"(token [[TOKEN]]) ]
+; CHECK-NEXT:    ret void
+;
+entry:
+  %token = call token @llvm.experimental.convergence.entry()
+  call void @make_indirect_call(ptr @convergent_callee, i32 0) [ "convergencectrl"(token %token) ]
+  ret void
+}
+
+define void @recurse() convergent alwaysinline {
+; CHECK-LABEL: @recurse(
+; CHECK-NEXT:    [[TOKEN:%.*]] = call token @llvm.experimental.convergence.entry()
+; CHECK-NEXT:    call void @recurse() [ "convergencectrl"(token [[TOKEN]]) ]
+; CHECK-NEXT:    ret void
+;
+  %token = call token @llvm.experimental.convergence.entry()
+  call void @recurse() [ "convergencectrl"(token %token) ]
+  ret void
+}
+
+define void @test_recursive_call() convergent {
+; CHECK-LABEL: @test_recursive_call(
+; CHECK-NEXT:    [[TOKEN:%.*]] = call token @llvm.experimental.convergence.entry()
+; CHECK-NEXT:    call void @recurse() [ "convergencectrl"(token [[TOKEN]]) ]
+; CHECK-NEXT:    ret void
+;
+  %token = call token @llvm.experimental.convergence.entry()
+  call void @recurse() [ "convergencectrl"(token %token) ]
+  ret void
+}
+
+define i32 @outer_g(i32 %x) convergent alwaysinline {
+; CHECK-LABEL: @outer_g(
+; CHECK-NEXT:    [[TOKEN:%.*]] = call token @llvm.experimental.convergence.entry()
+; CHECK-NEXT:    [[Y:%.*]] = call i32 @g(i32 [[X:%.*]]) [ "convergencectrl"(token [[TOKEN]]) ]
+; CHECK-NEXT:    ret i32 [[Y]]
+;
+  %token = call token @llvm.experimental.convergence.entry()
+  %y = call i32 @g(i32 %x) [ "convergencectrl"(token %token) ]
+  ret i32 %y
+}
+
+define void @test_two_calls() convergent {
+; CHECK-LABEL: @test_two_calls(
+; CHECK-NEXT:    [[TOKEN:%.*]] = call token @llvm.experimental.convergence.entry()
+; CHECK-NEXT:    [[Y_I:%.*]] = call i32 @g(i32 23) [ "convergencectrl"(token [[TOKEN]]) ]
+; CHECK-NEXT:    call void @f(i32 [[Y_I]]) [ "convergencectrl"(token [[TOKEN]]) ]
+; CHECK-NEXT:    ret void
+;
+  %token = call token @llvm.experimental.convergence.entry()
+  %x = call i32 @outer_g(i32 23) [ "convergencectrl"(token %token) ]
+  call void @convergent_callee(i32 %x) [ "convergencectrl"(token %token) ]
+  ret void
+}
+
+declare void @f(i32) convergent
+declare i32 @g(i32) convergent
+
+declare token @llvm.experimental.convergence.entry()
+declare token @llvm.experimental.convergence.anchor()
+declare token @llvm.experimental.convergence.loop()