[FuncAttrs] Infer noreturn

[aeubanks]

Summary

A function is noreturn if all blocks terminating with a ReturnInst
contain a call to a noreturn function. Skip looking at naked functions
since there may be asm that returns.

This can be further refined in the future by checking unreachable blocks
and taking into account recursion. It looks like the attributor pass
does this, but that is not yet enabled by default.

This seems to help with code size under the new PM since PruneEH does
not run under the new PM, missing opportunities to mark some functions
noreturn, which in turn doesn't allow simplifycfg to clean up dead code.
https://bugs.llvm.org/show_bug.cgi?id=46858.

[madhur13490]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

1400

I think you can actually avoid this variable. You can declare "FoundNoReturnCall" outside the loops and define it in each iteration of the outer loop. If (!FoundNoReturnCall) in outer loop then break and if (FoundNoReturnCall) outside the loop then F->setDoesNotReturn(). CanReturn is acting as an accumulator here but if you declare FoundNoReturnCall outside the loop then it can act for the same purpose.

1409–1411

Can combine them to one condition in some helper function and call it here. This will be more readable and maintenable

[aeubanks]

factor out determining if instruction returns

[aeubanks]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

1400

I'm not following, could you post the code?
This is basically an all(any()) where the all means "every basic block must" and the any means "any instruction in the block doesn't return". I believe you need two variables for all(any()).

[aeubanks]

make some variable names clearer

[madhur13490]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

1400

Ah! I misremembered noreturn as any(any). But I guess you can still do it with one variable if you have unsetDoesNotReturn in llvm::Function. Something like below,

bool Changed = false;
   F->setDoesNotReturn();
   for (BasicBlock &BB : *F) {
     if (!isa<ReturnInst>(BB.getTerminator()))
       continue;
     bool BasicBlockCanReachReturn = true;
     for (Instruction &I : BB) {
       if (instructionDoesNotReturn(I)) {
         BasicBlockCanReachReturn = false;
         break;
       }
     }
     if (BasicBlockCanReachReturn) {
       F->unsetDoesNotReturn();
       Changed = true;
       break;
     }
   }

The method is not currently present but I see no reason for ignoring it. I see removeFnAttr being use to one can add such method. More generally, there can be methods like changeNoReturnAttrib(bool) which changes the state to the input bool; if changeNoReturnAttrib(true) then it adds the attribute, if changeNoReturnAttrib(false) it remove the attribute - of course after checking redundancy.

However, I think we can continue for now.

[rnk]

lgtm

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

1415–1430

This is code golf, but there is this code style rule here to consider:
https://llvm.org/docs/CodingStandards.html#turn-predicate-loops-into-predicate-functions

This code could be:

// A BB can only return if it ends in ReturnInst and does not contain any calls to noreturn functions.
static bool canBasicBlockReturn(const BasicBlock &BB) {
  if (isa<ReturnInst>(BB.getTerminator()))
    return llvm::none_of(BB, instructionDoesNotReturn);
  return false;
}

...

if (llvm::none_of(F, canBasicBlockReturn)) {
  Changed = true;
  F->setDoesNotReturn();
}

Feel free to implement or disregard.

[aeubanks]

clean up code

[sanwou01]

Hi folks, I'm afraid an 8% regression in h264ref (SPEC INT 2006) bisects to this patch. This in on AArch64 with -flto on a Neoverse-N1 based system, but I wouldn't be surprised if this showed up elsewhere too.

How do people feel about reverting the patch while we investigate the regression? To start with, I'll try to find out why this has caused the drop in performance: it doesn't seem immediately obvious to me.

[aeubanks]

In D93946#2492918, @sanwou01 wrote:

Hi folks, I'm afraid an 8% regression in h264ref (SPEC INT 2006) bisects to this patch. This in on AArch64 with -flto on a Neoverse-N1 based system, but I wouldn't be surprised if this showed up elsewhere too.

How do people feel about reverting the patch while we investigate the regression? To start with, I'll try to find out why this has caused the drop in performance: it doesn't seem immediately obvious to me.

I really can't see this change causing performance regressions. It only infers more precise function attributes. Could you do some initial investigation or come up with a repro? Maybe an optimization remark that doesn't fire after this change?

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

1400

To clarify, when you say

However, I think we can continue for now.

do you mean the current patch looks good or that

[jdoerfert]

In D93946#2493440, @aeubanks wrote:

In D93946#2492918, @sanwou01 wrote:

Hi folks, I'm afraid an 8% regression in h264ref (SPEC INT 2006) bisects to this patch. This in on AArch64 with -flto on a Neoverse-N1 based system, but I wouldn't be surprised if this showed up elsewhere too.

How do people feel about reverting the patch while we investigate the regression? To start with, I'll try to find out why this has caused the drop in performance: it doesn't seem immediately obvious to me.

I really can't see this change causing performance regressions. It only infers more precise function attributes. Could you do some initial investigation or come up with a repro? Maybe an optimization remark that doesn't fire after this change?

FWIW, I have seen similar things in the past. Better information leads to regressions because of heuristics firing later on. The "bug" is somewhere else and only exposed.

[sanwou01]

In D93946#2493440, @aeubanks wrote:

Could you do some initial investigation or come up with a repro? Maybe an optimization remark that doesn't fire after this change?

Yes, I will do an initial investigation, hopefully resulting in a reproducer. It is always a bit of a challenge with LTO benchmarks, but the regression is large enough that it should be easy to spot.

[markus]

Not terribly important but isn't

A function is noreturn if all blocks terminating with a ReturnInst contain a call to a noreturn function.

slightly in conflict with the Lint pass containing the following "Unusual" warning?

void Lint::visitReturnInst(ReturnInst &I) {
  Function *F = I.getParent()->getParent();
  Assert(!F->doesNotReturn(),
         "Unusual: Return statement in function with noreturn attribute", &I);

  if (Value *V = I.getReturnValue()) {
    Value *Obj = findValue(V, /*OffsetOk=*/true);
    Assert(!isa<AllocaInst>(Obj), "Unusual: Returning alloca value", &I);
  }
}

Well I guess "Unusual" is not really a warning but still it kind of indicates that something is off. So maybe that Lint printout should be removed or updated somehow?

[jdoerfert]

In D93946#2495693, @markus wrote:

Not terribly important but isn't

A function is noreturn if all blocks terminating with a ReturnInst contain a call to a noreturn function.

slightly in conflict with the Lint pass containing the following "Unusual" warning?

FWIW, that is not an accurate definition of noreturn since we have endless loops and the calles might not always
be noreturn but just for the parameters passed.

void Lint::visitReturnInst(ReturnInst &I) {
  Function *F = I.getParent()->getParent();
  Assert(!F->doesNotReturn(),
         "Unusual: Return statement in function with noreturn attribute", &I);

  if (Value *V = I.getReturnValue()) {
    Value *Obj = findValue(V, /*OffsetOk=*/true);
    Assert(!isa<AllocaInst>(Obj), "Unusual: Returning alloca value", &I);
  }
}

Well I guess "Unusual" is not really a warning but still it kind of indicates that something is off. So maybe that Lint printout should be removed or updated somehow?

I'd leave the warning if we replace all ReturnInst with unreachable. Otherwise it is "unusual".

[sanwou01]

In D93946#2493599, @sanwou01 wrote:

In D93946#2493440, @aeubanks wrote:

Could you do some initial investigation or come up with a repro? Maybe an optimization remark that doesn't fire after this change?

Yes, I will do an initial investigation, hopefully resulting in a reproducer. It is always a bit of a challenge with LTO benchmarks, but the regression is large enough that it should be easy to spot.

This appears to be a (very painful) second order effect that is causing an increase in branch misses in one of the loops in h264ref. There is no codegen difference in the area, only a slight change in alignment. So nothing to do with this patch really, just bad luck.

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) {
   // Every call was to a non-recursive function other than this function, and
   // we have no indirect recursion as the SCC size is one. This function cannot
   // recurse.
   F->setDoesNotRecurse();
   ++NumNoRecurse;
   return true;
 }
 
+static bool instructionDoesNotReturn(Instruction &I) {
+  if (auto *CB = dyn_cast<CallBase>(&I)) {
+    Function *Callee = CB->getCalledFunction();
+    return Callee && Callee->doesNotReturn();
+  }
+  return false;
+}
+
+// A basic block can only return if it terminates with a ReturnInst and does not
+// contain calls to noreturn functions.
+static bool basicBlockCanReturn(BasicBlock &BB) {
+  if (!isa<ReturnInst>(BB.getTerminator()))
+    return false;
+  return none_of(BB, instructionDoesNotReturn);
+}
+
+// Set the noreturn function attribute if possible.
+static bool addNoReturnAttrs(const SCCNodeSet &SCCNodes) {
+  bool Changed = false;
+
+  for (Function *F : SCCNodes) {
+    if (!F || !F->hasExactDefinition() || F->hasFnAttribute(Attribute::Naked) ||
+        F->doesNotReturn())
+      continue;
+
+    // The function can return if any basic blocks can return.
+    // FIXME: this doesn't handle recursion or unreachable blocks.
+    if (none_of(*F, basicBlockCanReturn)) {
+      F->setDoesNotReturn();
+      Changed = true;
+    }
+  }
+
+  return Changed;
+}
+
 static SCCNodesResult createSCCNodeSet(ArrayRef<Function *> Functions) {
   SCCNodesResult Res;
   Res.HasUnknownCall = false;
   for (Function *F : Functions) {
     if (!F || F->hasOptNone() || F->hasFnAttribute(Attribute::Naked)) {
       // Treat any function we're trying not to optimize as if it were an
       // indirect call and omit it from the node set used below.
       Res.HasUnknownCall = true;
       continue;
     }
     // Track whether any functions in this SCC have an unknown call edge.
     // Note: if this is ever a performance hit, we can common it with
static bool deriveAttrsInPostOrder(ArrayRef<Function *> Functions,
   // Bail if the SCC only contains optnone functions.
   if (Nodes.SCCNodes.empty())
     return Changed;
 
   Changed |= addArgumentReturnedAttrs(Nodes.SCCNodes);
   Changed |= addReadAttrs(Nodes.SCCNodes, AARGetter);
   Changed |= addArgumentAttrs(Nodes.SCCNodes);
   Changed |= inferConvergent(Nodes.SCCNodes);
+  Changed |= addNoReturnAttrs(Nodes.SCCNodes);
 
   // If we have no external nodes participating in the SCC, we can deduce some
   // more precise attributes as well.
   if (!Nodes.HasUnknownCall) {
     Changed |= addNoAliasAttrs(Nodes.SCCNodes);
     Changed |= addNonNullAttrs(Nodes.SCCNodes);
     Changed |= inferAttrsFromFunctionBodies(Nodes.SCCNodes);
     Changed |= addNoRecurseAttrs(Nodes.SCCNodes);

llvm/test/Transforms/FunctionAttrs/noreturn.ll

+; RUN: opt < %s -passes='function-attrs' -S | FileCheck %s
+
+declare i32 @f()
+
+; CHECK: Function Attrs: noreturn
+; CHECK-NEXT: @noreturn()
+declare i32 @noreturn() noreturn
+
+; CHECK: Function Attrs: noreturn
+; CHECK-NEXT: @caller()
+define i32 @caller() {
+  %c = call i32 @noreturn()
+  ret i32 %c
+}
+
+; CHECK: Function Attrs: noreturn
+; CHECK-NEXT: @caller2()
+define i32 @caller2() {
+  %c = call i32 @caller()
+  ret i32 %c
+}
+
+; CHECK: Function Attrs: noreturn
+; CHECK-NEXT: @caller3()
+define i32 @caller3() {
+entry:
+  br label %end
+end:
+  %c = call i32 @noreturn()
+  ret i32 %c
+}
+
+; CHECK-NOT: Function Attrs: {{.*}}noreturn
+; CHECK: define i32 @caller4()
+define i32 @caller4() {
+entry:
+  br label %end
+end:
+  %c = call i32 @f()
+  ret i32 %c
+}
+
+; CHECK-NOT: Function Attrs: {{.*}}noreturn
+; CHECK: @caller5()
+; We currently don't handle unreachable blocks.
+define i32 @caller5() {
+entry:
+  %c = call i32 @noreturn()
+  ret i32 %c
+unreach:
+  %d = call i32 @f()
+  ret i32 %d
+}
+
+; CHECK-NOT: Function Attrs: {{.*}}noreturn
+; CHECK: @caller6()
+define i32 @caller6() naked {
+  %c = call i32 @noreturn()
+  ret i32 %c
+}
+
+; CHECK: Function Attrs: {{.*}}noreturn
+; CHECK-NEXT: @alreadynoreturn()
+define i32 @alreadynoreturn() noreturn {
+  unreachable
+}

llvm/test/Transforms/PruneEH/simplenoreturntest.ll

 ; RUN: opt < %s -prune-eh -S -enable-new-pm=0 | not grep "ret i32"
+; RUN: opt < %s -passes='function-attrs,function(simplifycfg)' -S | not grep "ret i32"
 
 declare void @noreturn() noreturn
 
 define i32 @caller() {
   call void @noreturn()
   ret i32 17
 }
 
 define i32 @caller2() {
   %T = call i32 @caller()
   ret i32 %T
 }