[Attributor] Deduce "no-recurse" function attribute

[jdoerfert]

Summary

Deduce the "no-recurse" function attribute through "backward-reasoning".
Thus, if no call site in the function may cause recursion, the function
does not recurse. Note that "backward-reasoning" is the only reasoning
the Attributor performs right now.

Impact on the statistics (-stats) for LLVM-TS + Spec2006, totaling
almost 80% more localized globals (probably due to the intrinsic
white list used).

CHANGED: attributor                   NumAttributesManifested                  612 ->      14331 ( +2241.667%)
CHANGED: attributor                   NumAttributesValidFixpoint             26069 ->      39788 (   +52.626%)
  ADDED: attributor                   NumFnNoRecurse                           n/a ->      13719
CHANGED: functionattrs                NumNoRecurse                           61932 ->      49305 (   -20.388%)
CHANGED: globalopt                    NumLocalized                              37 ->         66 (   +78.378%)

Note: Missing "no-recurse" deduction compared to functionattrs is completely, or at least in large parts, due to a bug in the existing code, see: https://llvm.org/PR41336

Possible improvements:

• Perform "forward-reasoning": If all call sites are in no-recurse functions then the function must be no-recurse.
• Eliminate dead call sites: Similar to the preliminary reasoning in the no-return abstract attribute we can ignore dead call sites.

[jdoerfert]

Rebase

[jdoerfert]

Typo

[jdoerfert]

Update tests

[efriedma]

Is it actually correct to derive norecurse like this?

Suppose I have two functions:

void f(int x) { if (x) { g(); } }
void g() { f(0); }

As far as I can tell, it would be correct to mark g() norecurse. And if g() is marked norecurse, we'll mark f() norecurse, which is wrong.

Granted, this is being sort of pedantic with the definition in LangRef, which says the function "does not call itself". It might make sense to redefine norecurse to mean the function doesn't call "any function currently on the stack", instead of just itself.

[jdoerfert]

In D60074#1531809, @efriedma wrote:

Is it actually correct to derive norecurse like this?

Suppose I have two functions:

void f(int x) { if (x) { g(); } }
void g() { f(0); }

As far as I can tell, it would be correct to mark g() norecurse. And if g() is marked norecurse, we'll mark f() norecurse, which is wrong.

We should/do not mark g as norecurse in this example. At least not if f is externally visible.

Granted, this is being sort of pedantic with the definition in LangRef, which says the function "does not call itself". It might make sense to redefine norecurse to mean the function doesn't call "any function currently on the stack", instead of just itself.

What we did before and with this patch is derive norecurse only if no call to a recursive function is contained. So in contrast to other attributes we actually do not look at the optimistic/assumed state of called functions.

[nicholas]

In D60074#1531819, @jdoerfert wrote:

In D60074#1531809, @efriedma wrote:

Is it actually correct to derive norecurse like this?

Suppose I have two functions:

void f(int x) { if (x) { g(); } }
void g() { f(0); }

As far as I can tell, it would be correct to mark g() norecurse. And if g() is marked norecurse, we'll mark f() norecurse, which is wrong.

We should/do not mark g as norecurse in this example. At least not if f is externally visible.

Could you explain a little further? I don't see how changing whether f is externally visible changes whether it's OK to mark g with norecurse. Here's my thinking. If f is externally visible that means it can be called from external code, and we have to make the worst-case assumption about the call stack, but in this case we know that g can't be on the call stack since g doesn't call any external functions. Is that right?

I think Eli's question can be considered in two parts. The first is about what LangRef permits, not what the Attributor pass will deduce. Is it legal to mark g with norecurse? If it is, some other user of LLVM, perhaps a user of LLVM as a library, may mark it norecurse themselves which would be correct/truthful/not a bug yet. The second part of Eli's question, is that if the first part is right and g has been annotated with norecurse before the Attributor runs, won't it mark f as norecurse, and that would be an incorrect deduction on the Attributor's part?

Granted, this is being sort of pedantic with the definition in LangRef, which says the function "does not call itself". It might make sense to redefine norecurse to mean the function doesn't call "any function currently on the stack", instead of just itself.

The LangRef says "down any possible call path" which might be an attempt to make g not legal to be marked with norecurse. I think the wording is unclear, is it a "possible path" to have g -> f -> g or not? Statically both g -> f and f -> g calls are present, but we can also statically prove that the g -> f -> g route combination is impossible. I think LangRef's wording should focus on forbidding the function from occurring more than once on the call stack, and remove the wording about possible paths. The net result of that change would permit marking of g as norecurse.

I'm not sure the proposed "does not call any function currently on the stack" is right either. Consider a call stack of A -> B -> C -> B. If this is the call stack that is generated every time (there is no other caller of B or C and this happens for all calls to A) it would be true that A and C are norecurse and B is not. With the proposed definition, c could not be marked norecurse. I haven't considered whether it's useful for optimization to think of C as being norecurse.

If the above scenario were real, it would require that B has a branch that determines whether a call is made, splitting the function into a part that may recurse and a part that may not. Some day, we may want to pursue norecurse at the instruction level with the semantic of "after this instruction is executed, it is not executed again by any direct or indirect callee until the return of the instruction parent's function on the call stack" (awkward wording so as to not forbid loops within the function). Offhand I think this would also work to represent the result of inlining a norecurse callee into a non-norecurse caller. (Again, I haven't considered whether this information is useful for any optimization.)

What we did before and with this patch is derive norecurse only if no call to a recursive function is contained. So in contrast to other attributes we actually do not look at the optimistic/assumed state of called functions.

I think the right fix is to extend it to derive norecurse only if no call to a recursive function or a function in the same SCC (even if marked norecurse) is contained. That would allow the attributor to avoid marking f as norecurse even if g were marked norecurse.

llvm/lib/Transforms/IPO/Attributor.cpp

299

LLVM hosts the mailing list archives on lists.llvm.org. I think the "official" link would be https://lists.llvm.org/pipermail/llvm-dev/2017-June/113714.html

(I think I understand the problem here is that the discussion continued over multiple months and llvm's official archives are generated split per month. If that's the reason behind linking to nabble, I think it's worth a bug report on bugs.llvm.org , and I won't comment again about whether it's a link to lists.llvm.org or nabble.com -- though I'm rather unhappy that nabble has misconfigured HTTPS.)

[jdoerfert]

Thanks for the extensive comment!

In D60074#1532046, @nicholas wrote:

In D60074#1531819, @jdoerfert wrote:

In D60074#1531809, @efriedma wrote:

Is it actually correct to derive norecurse like this?

Suppose I have two functions:

void f(int x) { if (x) { g(); } }
void g() { f(0); }

As far as I can tell, it would be correct to mark g() norecurse. And if g() is marked norecurse, we'll mark f() norecurse, which is wrong.

We should/do not mark g as norecurse in this example. At least not if f is externally visible.

Could you explain a little further? I don't see how changing whether f is externally visible changes whether it's OK to mark g with norecurse. Here's my thinking. If f is externally visible that means it can be called from external code, and we have to make the worst-case assumption about the call stack, but in this case we know that g can't be on the call stack since g doesn't call any external functions. Is that right?

I should have explained this better from the beginning. At the moment, for better or worse, we derive norecurse only if the function does not call a recursive function. I did not want to change this behavior in this patch but I'm willing to investigate if we should. Now, in the example above, f is recursive as it calls g which calls f. And g is recursive as it calls f which was recursive. My internal comment was following this logic: If f was internal, we could (conceptually) eliminate the call of g after IPSCCP and thereby making both functions non-recursive.

I think Eli's question can be considered in two parts. The first is about what LangRef permits, not what the Attributor pass will deduce. Is it legal to mark g with norecurse? If it is, some other user of LLVM, perhaps a user of LLVM as a library, may mark it norecurse themselves which would be correct/truthful/not a bug yet.

Regarding the example, the way I read the LangRef g could be norecurse but f not. Now I'm happy to make that deduction (in a subsequent patch?) but I'll have to check if it breaks existing assumptions.

The second part of Eli's question, is that if the first part is right and g has been annotated with norecurse before the Attributor runs, won't it mark f as norecurse, and that would be an incorrect deduction on the Attributor's part?

As I mentioned above, the Attributor preserves the current behavior (minus the bug we have) and it would not annotate either function as norecurse.

Granted, this is being sort of pedantic with the definition in LangRef, which says the function "does not call itself". It might make sense to redefine norecurse to mean the function doesn't call "any function currently on the stack", instead of just itself.

The LangRef says "down any possible call path" which might be an attempt to make g not legal to be marked with norecurse. I think the wording is unclear, is it a "possible path" to have g -> f -> g or not? Statically both g -> f and f -> g calls are present, but we can also statically prove that the g -> f -> g route combination is impossible. I think LangRef's wording should focus on forbidding the function from occurring more than once on the call stack, and remove the wording about possible paths. The net result of that change would permit marking of g as norecurse.

I'm not sure the proposed "does not call any function currently on the stack" is right either. Consider a call stack of A -> B -> C -> B. If this is the call stack that is generated every time (there is no other caller of B or C and this happens for all calls to A) it would be true that A and C are norecurse and B is not. With the proposed definition, c could not be marked norecurse. I haven't considered whether it's useful for optimization to think of C as being norecurse.

I think the LangRef allows g to be norecurse right now.

If the above scenario were real, it would require that B has a branch that determines whether a call is made, splitting the function into a part that may recurse and a part that may not. Some day, we may want to pursue norecurse at the instruction level with the semantic of "after this instruction is executed, it is not executed again by any direct or indirect callee until the return of the instruction parent's function on the call stack" (awkward wording so as to not forbid loops within the function). Offhand I think this would also work to represent the result of inlining a norecurse callee into a non-norecurse caller. (Again, I haven't considered whether this information is useful for any optimization.)

This is something we might want to discuss separately ;). Though, I'd be happy to look into it if we have a use case :)

What we did before and with this patch is derive norecurse only if no call to a recursive function is contained. So in contrast to other attributes we actually do not look at the optimistic/assumed state of called functions.

I think the right fix is to extend it to derive norecurse only if no call to a recursive function or a function in the same SCC (even if marked norecurse) is contained. That would allow the attributor to avoid marking f as norecurse even if g were marked norecurse.

If we derive what the LangRef says right now, the best solution is norecurse for g and nothing for f. I don't think we need to change the wording. (Maybe I'm missing something here.)

[efriedma]

In terms of the correctness of this patch, I'm specifically concerned that this patch has no equivalent to the SCCNodes.size() != 1 check in FunctionAttrs, so it will derive norecurse in cases where FunctionAttrs would not. For example:

define void @f(i32 %x)  {
entry:
  %x.addr = alloca i32, align 4
  store i32 %x, i32* %x.addr, align 4
  %0 = load i32, i32* %x.addr, align 4
  %tobool = icmp ne i32 %0, 0
  br i1 %tobool, label %if.then, label %if.end

if.then:
  call void @g() norecurse
  br label %if.end

if.end:
  ret void
}

define void @g() norecurse {
entry:
  call void @f(i32 0)
  ret void
}

[jdoerfert]

You have good points. I'll plan to do the following:

• Abandon this patch
• Come up with a patch that actually looks at called functions and SCCs
• Add your test case to the norecuse.ll file to make sure it works.

[nicholas]

In D60074#1533285, @jdoerfert wrote:

Thanks for the extensive comment!

In D60074#1532046, @nicholas wrote:

In D60074#1531819, @jdoerfert wrote:

In D60074#1531809, @efriedma wrote:

Is it actually correct to derive norecurse like this?

Suppose I have two functions:

void f(int x) { if (x) { g(); } }
void g() { f(0); }

As far as I can tell, it would be correct to mark g() norecurse. And if g() is marked norecurse, we'll mark f() norecurse, which is wrong.

We should/do not mark g as norecurse in this example. At least not if f is externally visible.

Could you explain a little further? I don't see how changing whether f is externally visible changes whether it's OK to mark g with norecurse. Here's my thinking. If f is externally visible that means it can be called from external code, and we have to make the worst-case assumption about the call stack, but in this case we know that g can't be on the call stack since g doesn't call any external functions. Is that right?

I should have explained this better from the beginning. At the moment, for better or worse, we derive norecurse only if the function does not call a recursive function. I did not want to change this behavior in this patch but I'm willing to investigate if we should. Now, in the example above, f is recursive as it calls g which calls f. And g is recursive as it calls f which was recursive. My internal comment was following this logic: If f was internal, we could (conceptually) eliminate the call of g after IPSCCP and thereby making both functions non-recursive.

Ah, through other optimizations. Got it!

What we did before and with this patch is derive norecurse only if no call to a recursive function is contained. So in contrast to other attributes we actually do not look at the optimistic/assumed state of called functions.

I think the right fix is to extend it to derive norecurse only if no call to a recursive function or a function in the same SCC (even if marked norecurse) is contained. That would allow the attributor to avoid marking f as norecurse even if g were marked norecurse.

If we derive what the LangRef says right now, the best solution is norecurse for g and nothing for f. I don't think we need to change the wording. (Maybe I'm missing something here.)

I'm just referring to the words "down any possible call path" in the LangRef because I don't know what to do with that. The sentence starts by saying that norecurse means that the function may not call itself, which I think I understand, but then it adds "down any possible call path" and I don't know what that adds, removes, or changes. My best guess is that those words are an implementation detail of the optimizer, because the optimizer looks at all possible call paths when deducing norecurse. (For example noreturn "indicates that the function never returns normally." If it said "indicates that the function never returns normally down any path" I'd be left wondering what corner case of noreturn semantics I'm missing!) I'm suggesting a wording like "This function attribute indicates that the function does not occur twice on the call stack. This produces undefined behaviour if the function ever calls itself directly or indirectly." (LangRef doesn't define what a call stack is, though it uses the notion in the definition of landingpad and catchpad and I think it's fair to expect readers to be familiar.) Anyways, doesn't need to be changed in this patch.

llvm/lib/Transforms/IPO/Attributor.cpp

 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/InstIterator.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "attributor"
 
 STATISTIC(NumFnWithExactDefinition,
           "Number of function with exact definitions");
 STATISTIC(NumFnWithoutExactDefinition,
           "Number of function without exact definitions");
 STATISTIC(NumAttributesTimedOut,
           "Number of abstract attributes timed out before fixpoint");
 STATISTIC(NumAttributesValidFixpoint,
           "Number of abstract attributes in a valid fixpoint state");
 STATISTIC(NumAttributesManifested,
           "Number of abstract attributes manifested in IR");
 
+STATISTIC(NumFnNoRecurse, "Number of functions marked norecurse");
+
 // TODO: Determine a good default value.
 //
 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
 // (when run with the first 5 abstract attributes). The results also indicate
 // that we never reach 32 iterations but always find a fixpoint sooner.
 //
 // This will become more evolved once we perform two interleaved fixpoint
 // iterations: bottom-up and top-down.

 /// Helper to adjust the statistics.
 static void bookkeeping(AbstractAttribute::ManifestPosition MP,
                         const Attribute &Attr) {
   if (!AreStatisticsEnabled())
     return;
 
   if (!Attr.isEnumAttribute())
     return;
-  //switch (Attr.getKindAsEnum()) {
-  //default:
-  //  return;
-  //}
+  switch (Attr.getKindAsEnum()) {
+  case Attribute::NoRecurse:
+    NumFnNoRecurse++;
+    return;
+  default:
+    return;
+  }
 }
 
 /// Helper to identify the correct offset into an attribute list.
 static unsigned getAttrIndex(AbstractAttribute::ManifestPosition MP,
                              unsigned ArgNo = 0) {
   switch (MP) {
   case AbstractAttribute::MP_ARGUMENT:
   case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
if (isa<Instruction>(V))
     return *cast<Instruction>(V).getFunction();
   llvm_unreachable("No scope for anchored value found!");
 }
 
 const Function &AbstractAttribute::getAnchorScope() const {
   return const_cast<AbstractAttribute *>(this)->getAnchorScope();
 }
 
+/// ------------------------ No-Recurse Attributes ----------------------------
+
+struct AANoRecurseFunction : public AbstractAttribute, BooleanState {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AANoRecurseFunction(Function &F, InformationCache &InfoCache)
+      : AbstractAttribute(F, InfoCache) {}
+
+  /// See AbstractAttribute::getState()
+  ///{
+  AbstractState &getState() override { return *this; }
+  const AbstractState &getState() const override { return *this; }
+  ///}
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_FUNCTION;
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  virtual ChangeStatus updateImpl(Attributor &A) override;
+
+  /// See AbstractState::getAsStr().
+  const std::string getAsStr() const override {
+    return getAssumed() ? "norecurse" : "may-recurse";
+  }
+
+  /// See AbstractAttribute::getAttrKind()
+  virtual Attribute::AttrKind getAttrKind() const override { return ID; }
+
+  /// The identifier used by the Attributor for this class of attributes.
+  static constexpr Attribute::AttrKind ID = Attribute::NoRecurse;
+};
+
+ChangeStatus AANoRecurseFunction::updateImpl(Attributor &A) {
+  Function &Fn = getAnchorScope();
+
+  // The map from instruction opcodes to those instructions in the function.
+  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(Fn);
+
+  // Check all "call-like" opcodes. If any call site was found without the
+  // no-recurse attribute, assume recursion through that call site.
+  for (unsigned Opcode :
+       {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
+        (unsigned)Instruction::Call}) {
+    for (Instruction *I : OpcodeInstMap[Opcode]) {
+      // TODO: This should not be done here but at the intrinsic side!
+      //       See also: https://bugs.llvm.org/show_bug.cgi?id=34696
+      //       and:
+      //       http://llvm.1065342.n5.nabble.com/llvm-dev-Is-every-intrinsic-norecurse-td109617.html
+      if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+        switch (II->getIntrinsicID()) {
+        case Intrinsic::annotation:
+        case Intrinsic::assume:
+        case Intrinsic::cos:
+        case Intrinsic::dbg_addr:
+        case Intrinsic::dbg_label:
+        case Intrinsic::dbg_declare:
+        case Intrinsic::dbg_value:
+        case Intrinsic::donothing:
+        case Intrinsic::exp:
+        case Intrinsic::exp2:
+        case Intrinsic::expect:
+        case Intrinsic::fabs:
+        case Intrinsic::floor:
+        case Intrinsic::log:
+        case Intrinsic::log10:
+        case Intrinsic::log2:
+        case Intrinsic::lifetime_start:
+        case Intrinsic::lifetime_end:
+        case Intrinsic::memset:
+        case Intrinsic::memcpy:
+        case Intrinsic::memmove:
+        case Intrinsic::pow:
+        case Intrinsic::powi:
+        case Intrinsic::sin:
+        case Intrinsic::sqrt:
+          continue;
+        default:
+          break;
+        }
+      }
+
+      ImmutableCallSite ICS(I);
+      assert(ICS && "Found an instruction with call base opcode that did not "
+                    "result in a call site");
+
+      if (ICS.hasFnAttr(getAttrKind()))
+        continue;
+
+      indicatePessimisticFixpoint();
+      return ChangeStatus::CHANGED;
+    }
+  }
+
+  // This attribute does not rely on other attributes as of now. Consequently,
+  // there is no need to update the state again.
+  indicateOptimisticFixpoint();
+  return ChangeStatus::UNCHANGED;
+}
+
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
 
 ChangeStatus Attributor::run() {
   // Initialize all abstract attributes.
   for (AbstractAttribute *AA : AllAbstractAttributes)
     AA->initialize(*this);
ChangeStatus Attributor::run() {
 
   return ManifestChange;
 }
 
 void Attributor::identifyDefaultAbstractAttributes(
     Function &F, InformationCache &InfoCache,
     DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist) {
 
+  // Every function might be "no-recurse".
+  registerAA(*new AANoRecurseFunction(F, InfoCache));
+
   // Walk all instructions to find more attribute opportunities and also
   // interesting instructions that might be queried by abstract attributes
   // during their initialization or update.
   auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
   auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
 
   for (Instruction &I : instructions(&F)) {
     bool IsInterestingOpcode = false;
 
     // To allow easy access to all instructions in a function with a given
     // opcode we store them in the InfoCache. As not all opcodes are interesting
     // to concrete attributes we only cache the ones that are as identified in
     // the following switch.
     // Note: There are no concrete attributes now so this is initially empty.
-    //switch (I.getOpcode()) {
-    //default:
-    //  break;
-    //}
+    switch (I.getOpcode()) {
+    default:
+      // The below list of "call-lile" opcodes has to be kept in sync with
+      // CallBase/CallSite and with the abstract attributes using the
+      // "Attributor::getOpcodeInstMapForFunction(...)" functionality. To verify
+      // at least the former property we provide an assertion here that should
+      // immediatly fire once the below list of switch cases is out of sync with
+      // the call site/base implementation.
+      assert((!ImmutableCallSite(&I)) && (!isa<CallBase>(&I)) &&
+             "New call site/base instruction type needs to be known in the "
+             "attributor!");
+      break;
+    case Instruction::Invoke:
+    case Instruction::CallBr:
+    case Instruction::Call:
+      // Call-like instructions are interesting for AANoRecurseFunction.
+      IsInterestingOpcode = true;
+      break;
+    }
     if (IsInterestingOpcode)
       InstOpcodeMap[I.getOpcode()].push_back(&I);
     if (I.mayReadOrWriteMemory())
       ReadOrWriteInsts.push_back(&I);
   }
 }
 
 /// Helpers to ease debugging through output streams and print calls.

llvm/test/Transforms/FunctionAttrs/norecurse.ll

 define internal void @o() {
   %a = call i32 @called_by_norecurse_indirectly()
   ret void
 }
 define void @p() norecurse {
   call void @o()
   ret void
 }
+
+; FIXME: This test exposes a bug: https://llvm.org/PR41336
+; CHECK: Function Attrs: norecurse
+; CHECK-NEXT: define i32 @leaf_redefinable()
+define linkonce_odr i32 @leaf_redefinable() {
+  ret i32 1
+}