[FunctionAttrs] Calls to libcalls don't cause a function to potentially recurse

[jmolloy]

Summary

If a function calls a library function, that shouldn't be treated as potentially causing a cycle in the CFG. Additionally calls to noreturn functions are norecurse by definition.

[dexonsmith]

Calls to exit() can recurse because of atexit() handlers. The same might be true of other libcalls?

Also, other noreturn functions can recurse; it's a weird path but I don't think it's malformed:

void bar() noreturn;
int foo() {
static bool Return = false;
if (Return) return 5;
Return = true;
bar();
}

void bar() {
sink(foo());
exit();

}

[jmolloy]

Hi Duncan,

Damn, you're right. I didn't even consider atexit handlers. And that noreturn case is true too. I'll abandon this.

Cheers,

James

[dexonsmith]

Yeah, this would have been nice :(. There might be something you can do for certain LLVM intrinsics?

[mehdi_amini]

Like... modifying there tablegen definition to add the norecurse attribute?

lib/Transforms/IPO/FunctionAttrs.cpp

default:
     // Didn't mark any attributes.
     return false;
   }
 
   return true;
 }
 
 static bool addNoRecurseAttrs(const CallGraphSCC &SCC,
+                              const TargetLibraryInfo &TLI,
                               SmallVectorImpl<WeakVH> &Revisit) {
   // Try and identify functions that do not recurse.
 
   // If the SCC contains multiple nodes we know for sure there is recursion.
   if (!SCC.isSingular())
     return false;
 
   const CallGraphNode *CGN = *SCC.begin();
   Function *F = CGN->getFunction();
-  if (!F || F->isDeclaration() || F->doesNotRecurse())
+  if (!F || F->doesNotRecurse())
     return false;
 
-  // If all of the calls in F are identifiable and are to norecurse functions, F
-  // is norecurse. This check also detects self-recursion as F is not currently
-  // marked norecurse, so any called from F to F will not be marked norecurse.
+  // A noreturn function by definition cannot recurse.
+  if (F->doesNotReturn())
+    return setDoesNotRecurse(*F);
+
+  if (F->isDeclaration())
+    return false;
+
+  auto IsLibCall = [&](Function *F) {
+    LibFunc::Func LF;
+    return TLI.getLibFunc(F->getName(), LF) && TLI.has(LF);
+  };
+
+  // If all of the calls in F are identifiable and are to norecurse functions or
+  // are libcalls, F is norecurse. This check also detects self-recursion as F
+  // is not currently marked norecurse, so any called from F to F will not be
+  // marked norecurse.
   if (std::all_of(CGN->begin(), CGN->end(),
-                  [](const CallGraphNode::CallRecord &CR) {
+                  [&](const CallGraphNode::CallRecord &CR) {
                     Function *F = CR.second->getFunction();
-                    return F && F->doesNotRecurse();
+                    return F && (F->doesNotRecurse() || IsLibCall(F));
                   }))
     // Function calls a potentially recursive function.
     return setDoesNotRecurse(*F);
 
   // We know that F is not obviously recursive, but we haven't been able to
   // prove that it doesn't actually recurse. Add it to the Revisit list to try
   // again top-down later.
   Revisit.push_back(F);
bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
   Changed |= addArgumentAttrs(SCCNodes);
 
   // If we have no external nodes participating in the SCC, we can infer some
   // more precise attributes as well.
   if (!ExternalNode) {
     Changed |= addNoAliasAttrs(SCCNodes);
     Changed |= addNonNullAttrs(SCCNodes, *TLI);
   }
-  
-  Changed |= addNoRecurseAttrs(SCC, Revisit);
+  Changed |= addNoRecurseAttrs(SCC, *TLI, Revisit);
   return Changed;
 }
 
 bool FunctionAttrs::doFinalization(CallGraph &CG) {
   bool Changed = false;
   // When iterating over SCCs we visit functions in a bottom-up fashion. Some of
   // the rules we have for identifying norecurse functions work best with a
   // top-down walk, so look again at all the functions we previously marked as
   // worth revisiting, in top-down order.
   for (auto &F : reverse(Revisit))
     if (F)
       Changed |= addNoRecurseAttrsTopDownOnly(cast<Function>((Value*)F));
   return Changed;
 }

test/Transforms/FunctionAttrs/norecurse.ll

 ; RUN: opt < %s -basicaa -functionattrs -S | FileCheck %s
 
+target triple = "x86_64-linux-gnu"
+
 ; CHECK: define i32 @leaf() #0
 define i32 @leaf() {
   ret i32 1
 }
 
 ; CHECK: define i32 @self_rec() #1
 define i32 @self_rec() {
   %a = call i32 @self_rec()
define internal void @o() {
   %a = call i32 @called_by_norecurse_indirectly()
   ret void
 }
 define void @p() norecurse {
   call void @o()
   ret void
 }
 
+; CHECK: define i32 @calls_exit() #2
+define i32 @calls_exit() {
+  call void @exit(i32 2)
+  ret i32 5
+}
+
+declare void @exit(i32) noreturn
+
+; CHECK: define i32 @calls_only_libcalls() #2
+define i32 @calls_only_libcalls() {
+  %a = call double @sin(double 0.0)
+  call void @fclose(i8* null)
+  ret i32 2
+}
+
+declare double @sin(double)
+declare void @fclose(i8*)
+
 ; CHECK: attributes #0 = { norecurse readnone }
 ; CHECK: attributes #1 = { readnone }
+; CHECK: attributes #2 = { norecurse }
 No newline at end of file