[funcattrs] check reachability to improve noreturn

[nickdesaulniers]

Summary

There was a fixme in the code pertaining to attributing functions as
noreturn. By using reachability, if none of the blocks that are
reachable from the entry return, then the function is noreturn.

Previously, the code only checked if any blocks returned. If they're
unreachable, then they don't matter.

This improves codegen for the Linux kernel.

Fixes: https://github.com/ClangBuiltLinux/linux/issues/1563

[nickdesaulniers]

One thing I was curious of; does this recalculate a new DominatorTree for each function?

I noticed some other usages of DominatorTree first would query Pass::getAnalysisIfAvailable<DominatorTreeWrapperPass>()). Should I be doing that, too? (will require plumbing the Pass object through a few static functions, but isn't too bad).

[nikic]

Yes, you'd want to fetch the DominatorTree from the FunctionAnalysisManager. Though as you're only interested in reachability and not actual dominance, you don't actually need a DT here. You can simply walk over the reachable blocks rather than all blocks.

[nickdesaulniers]

In D119571#3315181, @nikic wrote:

Yes, you'd want to fetch the DominatorTree from the FunctionAnalysisManager. Though as you're only interested in reachability and not actual dominance, you don't actually need a DT here. You can simply walk over the reachable blocks rather than all blocks.

Isn't DominatorTree necessary to compute reachability?

[nikic]

In D119571#3315196, @nickdesaulniers wrote:

In D119571#3315181, @nikic wrote:

Yes, you'd want to fetch the DominatorTree from the FunctionAnalysisManager. Though as you're only interested in reachability and not actual dominance, you don't actually need a DT here. You can simply walk over the reachable blocks rather than all blocks.

Isn't DominatorTree necessary to compute reachability?

You can traverse all reachable blocks by adding successors to a worklist and checking a visited set. Or as a very lazy way, iterate over depth_first(F) or breath_first(F), though those provide additional guarantees not strictly needed here (I don't think we have a helper for plain iteration over reachable blocks).

[nickdesaulniers]

• drop DomTree as per @nikic

[xbolva00]

helper for plain iteration over reachable blocks

Maybe it could be useful to create one now?

[nikic]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

1618

I don't think this is possible for a function with a definition?

1629–1631

[nickdesaulniers]

• simplify insert as per @nikic

[nickdesaulniers]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

1626

Probably want to keep the fixme about recursion.

[nickdesaulniers]

• retain modified fixme

[nikic]

LGTM

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

1619

SmallPtrSet, you don't care about iteration order here.

1627–1630

A bit better to avoid pushing to the worklist in the first place.

[nickdesaulniers]

• use SmallPtrSet, avoid push if visited

[nickdesaulniers]

• update description

[rnk]

Do we know which pass introduces unreachable code without cleaning it up? That seems like a missed optimization, possibly a phase ordering issue, or we could tack on a removeUnreachableBlocks to whichever pass is modifying the CFG in the first place.

[nickdesaulniers]

In D119571#3320199, @rnk wrote:

Do we know which pass introduces unreachable code without cleaning it up? That seems like a missed optimization, possibly a phase ordering issue, or we could tack on a removeUnreachableBlocks to whichever pass is modifying the CFG in the first place.

In this particular case, there is no pass introducing an unreachable; the unreachable is explicit in the source.

Because there's no analog for __attribute__((noreturn)) for inline asm, the Linux kernel frequently uses the pattern:

asm ("<instruction that will trap>");
__builtin_unreachable();

[rnk]

In D119571#3320553, @nickdesaulniers wrote:

In D119571#3320199, @rnk wrote:

Do we know which pass introduces unreachable code without cleaning it up? That seems like a missed optimization, possibly a phase ordering issue, or we could tack on a removeUnreachableBlocks to whichever pass is modifying the CFG in the first place.

In this particular case, there is no pass introducing an unreachable; the unreachable is explicit in the source.

It sounds like the phase ordering issue is that functionattrs runs before simplifycfg, and the frontend emits unreachable basic blocks. Of course, simplifycfg also benefits from functionattrs, so it's not trivial to fix. I think this is a known issue, no need to do anything about it now.

[nickdesaulniers]

rnk accepted this revision.

apologies, I had applied this with arc patch, rebased, rebuilt, retested, and pushed before I saw the additional +1; sorry it didn't make it into the commit message, but I appreciate the review!

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

 // 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);
 }
 
+// FIXME: this doesn't handle recursion.
+static bool canReturn(Function &F) {
+  SmallVector<BasicBlock *, 16> Worklist;
+  SmallPtrSet<BasicBlock *, 16> Visited;
+
+  Visited.insert(&F.front());
+  Worklist.push_back(&F.front());
+
+  do {
+    BasicBlock *BB = Worklist.pop_back_val();
+    if (basicBlockCanReturn(*BB))
+      return true;
+    for (BasicBlock *Succ : successors(BB))
+      if (Visited.insert(Succ).second)
+        Worklist.push_back(Succ);
+  } while (!Worklist.empty());
+
+  return false;
+}
+
 // Set the noreturn function attribute if possible.
 static void addNoReturnAttrs(const SCCNodeSet &SCCNodes,
                              SmallSet<Function *, 8> &Changed) {
   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)) {
+    if (!canReturn(*F)) {
       F->setDoesNotReturn();
       Changed.insert(F);
     }
   }
 }
 
 static bool functionWillReturn(const Function &F) {
   // We can infer and propagate function attributes only when we know that the

llvm/test/Transforms/FunctionAttrs/noreturn.ll

 define i32 @caller4() {
 entry:
   br label %end
 end:
   %c = call i32 @f()
   ret i32 %c
 }
 
-; CHECK-NOT: Function Attrs: {{.*}}noreturn
+; CHECK: 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: @coro
 define void @coro() "coroutine.presplit"="1" {
   call token @llvm.coro.id.retcon.once(i32 0, i32 0, i8* null, i8* bitcast(void() *@coro to i8*), i8* null, i8* null)
   call i1 @llvm.coro.end(i8* null, i1 false)
   unreachable
 }
 
 declare token @llvm.coro.id.retcon.once(i32 %size, i32 %align, i8* %buffer, i8* %prototype, i8* %alloc, i8* %free)
-declare i1 @llvm.coro.end(i8*, i1)
+declare i1 @llvm.coro.end(i8*, i1)