Add a new attribute: norecurse

[jmolloy]

Summary

This attribute allows the compiler to assume that the function never recurses into itself, either directly or indirectly (transitively). This can be used among other things to demote global variables to locals.

The norecurse attribute indicates that the function does not call itself either directly or indirectly down any possible call path.

[jmolloy]

test/Bindings/llvm-c/invalid-bitcode.test

3

These invalid bitcode tests were checking an attribute that is now valid.

I've updated the binary bitcode file to use attribute "50" instead - but obviously phab can't show that.

[mehdi_amini]

Patch looks good to me, but it would be nice to have more support for the attribute (or maybe at least wait a little bit for people to be able to object).

include/llvm/IR/Function.h

328

Just a nitpick: I believe we enabled autobrief and we shouldn't add it anymore when unnecessary.

[aaron.ballman]

Why an attribute specifying that recursion does not happen instead of one
specifying that it does? It seems like functions generally do not recurse,
which suggests marking recursion would require less annotations.

~Aaron

[majnemer]

James,

Have you considered what happens with something along the lines of:

void f() {
  g();
}
void g() {
  g();
}

In this case, we can clearly see that f doesn't recurse onto itself but g does.

I am concerned that if we infer norecurse, we will hit cases where transformations along the lines of inlining invalidate the attribute.

[mehdi_amini]

The fact that a transformation may invalidate the attribute seems to me to be independent from wether we infer it or not: the same example you took could come from a specific front-end (or directly a user) adding the attributes. I think we'll have to teach such a transformation that invalidate the attribute to either not perform when the attribute is present, or remove it. Does it makes sense?
Do you foresee a lot of such transformations? Or cases where it would be hard to do?

[llvm-commits]

This should probably be raised on llvm-dev for boarder visibility.

Side question: What optimizations or codegen opportunities does this
enable? i.e. what's the actual use case?

• msg-9172-187.txt162 BDownload

[jmolloy]

I committed this in r252282, with the autobrief change as suggested by Mehdi.

[hfinkel]

(will close)

[hfinkel]

This was committed as r252282

docs/LangRef.rst

``nonlazybind``
     startup time if the function is not called during program startup.
 ``noredzone``
     This attribute indicates that the code generator should not use a
     red zone, even if the target-specific ABI normally permits it.
 ``noreturn``
     This function attribute indicates that the function never returns
     normally. This produces undefined behavior at runtime if the
     function ever does dynamically return.
+``norecurse``
+    This function attribute indicates that the function does not call itself
+    either directly or indirectly down any possible call path. This produces
+    undefined behavior at runtime if the function ever does recurse.
 ``nounwind``
     This function attribute indicates that the function never raises an
     exception. If the function does raise an exception, its runtime
     behavior is undefined. However, functions marked nounwind may still
     trap or generate asynchronous exceptions. Exception handling schemes
     that are recognized by LLVM to handle asynchronous exceptions, such
     as SEH, will still provide their implementation defined semantics.
 ``optnone``

include/llvm/Bitcode/LLVMBitCodes.h

enum AttributeKindCodes {
     ATTR_KIND_NON_NULL = 39,
     ATTR_KIND_JUMP_TABLE = 40,
     ATTR_KIND_DEREFERENCEABLE = 41,
     ATTR_KIND_DEREFERENCEABLE_OR_NULL = 42,
     ATTR_KIND_CONVERGENT = 43,
     ATTR_KIND_SAFESTACK = 44,
     ATTR_KIND_ARGMEMONLY = 45,
     ATTR_KIND_SWIFT_SELF = 46,
-    ATTR_KIND_SWIFT_ERROR = 47
+    ATTR_KIND_SWIFT_ERROR = 47,
+    ATTR_KIND_NO_RECURSE = 48
   };
 
   enum ComdatSelectionKindCodes {
     COMDAT_SELECTION_KIND_ANY = 1,
     COMDAT_SELECTION_KIND_EXACT_MATCH = 2,
     COMDAT_SELECTION_KIND_LARGEST = 3,
     COMDAT_SELECTION_KIND_NO_DUPLICATES = 4,
     COMDAT_SELECTION_KIND_SAME_SIZE = 5,
   };
 
 } // End bitc namespace
 } // End llvm namespace
 
 #endif

include/llvm/IR/Attributes.h

enum AttrKind {
     Naked,                 ///< Naked function
     Nest,                  ///< Nested function static chain
     NoAlias,               ///< Considered to not alias after call
     NoBuiltin,             ///< Callee isn't recognized as a builtin
     NoCapture,             ///< Function creates no aliases of pointer
     NoDuplicate,           ///< Call cannot be duplicated
     NoImplicitFloat,       ///< Disable implicit floating point insts
     NoInline,              ///< inline=never
+    NoRecurse,             ///< The function does not recurse
     NonLazyBind,           ///< Function is called early and/or
                            ///< often, so lazy binding isn't worthwhile
     NonNull,               ///< Pointer is known to be not null
     Dereferenceable,       ///< Pointer is known to be dereferenceable
     DereferenceableOrNull, ///< Pointer is either null or dereferenceable
     NoRedZone,             ///< Disable redzone
     NoReturn,              ///< Mark the function as not returning
     NoUnwind,              ///< Function doesn't unwind stack

include/llvm/IR/Function.h

public:
   bool isConvergent() const {
     return AttributeSets.hasAttribute(AttributeSet::FunctionIndex,
                                       Attribute::Convergent);
   }
   void setConvergent() {
     addFnAttr(Attribute::Convergent);
   }
 
+  /// @brief Determine if the function is known not to recurse, directly or
+  /// indirectly.
+  bool doesNotRecurse() const {
+    return AttributeSets.hasAttribute(AttributeSet::FunctionIndex,
+                                      Attribute::NoRecurse);
+  }
+  void setDoesNotRecurse() {
+    addFnAttr(Attribute::NoRecurse);
+  }  
 
   /// @brief True if the ABI mandates (or the user requested) that this
   /// function be in a unwind table.
   bool hasUWTable() const {
     return AttributeSets.hasAttribute(AttributeSet::FunctionIndex,
                                       Attribute::UWTable);
   }
   void setHasUWTable() {

lib/AsmParser/LLLexer.cpp

#define KEYWORD(STR)                                                           \
   KEYWORD(naked);
   KEYWORD(nest);
   KEYWORD(noalias);
   KEYWORD(nobuiltin);
   KEYWORD(nocapture);
   KEYWORD(noduplicate);
   KEYWORD(noimplicitfloat);
   KEYWORD(noinline);
+  KEYWORD(norecurse);
   KEYWORD(nonlazybind);
   KEYWORD(nonnull);
   KEYWORD(noredzone);
   KEYWORD(noreturn);
   KEYWORD(nounwind);
   KEYWORD(optnone);
   KEYWORD(optsize);
   KEYWORD(readnone);

lib/AsmParser/LLParser.cpp

while (true) {
     case lltok::kw_nobuiltin: B.addAttribute(Attribute::NoBuiltin); break;
     case lltok::kw_noduplicate: B.addAttribute(Attribute::NoDuplicate); break;
     case lltok::kw_noimplicitfloat:
       B.addAttribute(Attribute::NoImplicitFloat); break;
     case lltok::kw_noinline: B.addAttribute(Attribute::NoInline); break;
     case lltok::kw_nonlazybind: B.addAttribute(Attribute::NonLazyBind); break;
     case lltok::kw_noredzone: B.addAttribute(Attribute::NoRedZone); break;
     case lltok::kw_noreturn: B.addAttribute(Attribute::NoReturn); break;
+    case lltok::kw_norecurse: B.addAttribute(Attribute::NoRecurse); break;
     case lltok::kw_nounwind: B.addAttribute(Attribute::NoUnwind); break;
     case lltok::kw_optnone: B.addAttribute(Attribute::OptimizeNone); break;
     case lltok::kw_optsize: B.addAttribute(Attribute::OptimizeForSize); break;
     case lltok::kw_readnone: B.addAttribute(Attribute::ReadNone); break;
     case lltok::kw_readonly: B.addAttribute(Attribute::ReadOnly); break;
     case lltok::kw_returns_twice:
       B.addAttribute(Attribute::ReturnsTwice); break;
     case lltok::kw_ssp: B.addAttribute(Attribute::StackProtect); break;

lib/AsmParser/LLToken.h

enum Kind {
     kw_naked,
     kw_nest,
     kw_noalias,
     kw_nobuiltin,
     kw_nocapture,
     kw_noduplicate,
     kw_noimplicitfloat,
     kw_noinline,
+    kw_norecurse,
     kw_nonlazybind,
     kw_nonnull,
     kw_noredzone,
     kw_noreturn,
     kw_nounwind,
     kw_optnone,
     kw_optsize,
     kw_readnone,

lib/Bitcode/Reader/BitcodeReader.cpp

static Attribute::AttrKind getAttrFromCode(uint64_t Code) {
   case bitc::ATTR_KIND_NO_CAPTURE:
     return Attribute::NoCapture;
   case bitc::ATTR_KIND_NO_DUPLICATE:
     return Attribute::NoDuplicate;
   case bitc::ATTR_KIND_NO_IMPLICIT_FLOAT:
     return Attribute::NoImplicitFloat;
   case bitc::ATTR_KIND_NO_INLINE:
     return Attribute::NoInline;
+  case bitc::ATTR_KIND_NO_RECURSE:
+    return Attribute::NoRecurse;
   case bitc::ATTR_KIND_NON_LAZY_BIND:
     return Attribute::NonLazyBind;
   case bitc::ATTR_KIND_NON_NULL:
     return Attribute::NonNull;
   case bitc::ATTR_KIND_DEREFERENCEABLE:
     return Attribute::Dereferenceable;
   case bitc::ATTR_KIND_DEREFERENCEABLE_OR_NULL:
     return Attribute::DereferenceableOrNull;

lib/Bitcode/Writer/BitcodeWriter.cpp

static uint64_t getAttrKindEncoding(Attribute::AttrKind Kind) {
   case Attribute::NoCapture:
     return bitc::ATTR_KIND_NO_CAPTURE;
   case Attribute::NoDuplicate:
     return bitc::ATTR_KIND_NO_DUPLICATE;
   case Attribute::NoImplicitFloat:
     return bitc::ATTR_KIND_NO_IMPLICIT_FLOAT;
   case Attribute::NoInline:
     return bitc::ATTR_KIND_NO_INLINE;
+  case Attribute::NoRecurse:
+    return bitc::ATTR_KIND_NO_RECURSE;
   case Attribute::NonLazyBind:
     return bitc::ATTR_KIND_NON_LAZY_BIND;
   case Attribute::NonNull:
     return bitc::ATTR_KIND_NON_NULL;
   case Attribute::Dereferenceable:
     return bitc::ATTR_KIND_DEREFERENCEABLE;
   case Attribute::DereferenceableOrNull:
     return bitc::ATTR_KIND_DEREFERENCEABLE_OR_NULL;

lib/IR/Attributes.cpp

std::string Attribute::getAsString(bool InAttrGrp) const {
   if (hasAttribute(Attribute::NonLazyBind))
     return "nonlazybind";
   if (hasAttribute(Attribute::NonNull))
     return "nonnull";
   if (hasAttribute(Attribute::NoRedZone))
     return "noredzone";
   if (hasAttribute(Attribute::NoReturn))
     return "noreturn";
+  if (hasAttribute(Attribute::NoRecurse))
+    return "norecurse";
   if (hasAttribute(Attribute::NoUnwind))
     return "nounwind";
   if (hasAttribute(Attribute::OptimizeNone))
     return "optnone";
   if (hasAttribute(Attribute::OptimizeForSize))
     return "optsize";
   if (hasAttribute(Attribute::ReadNone))
     return "readnone";
uint64_t AttributeImpl::getAttrMask(Attribute::AttrKind Val) {
   case Attribute::Cold:            return 1ULL << 40;
   case Attribute::Builtin:         return 1ULL << 41;
   case Attribute::OptimizeNone:    return 1ULL << 42;
   case Attribute::InAlloca:        return 1ULL << 43;
   case Attribute::NonNull:         return 1ULL << 44;
   case Attribute::JumpTable:       return 1ULL << 45;
   case Attribute::Convergent:      return 1ULL << 46;
   case Attribute::SafeStack:       return 1ULL << 47;
+  case Attribute::NoRecurse:       return 1ULL << 48;
   case Attribute::Dereferenceable:
     llvm_unreachable("dereferenceable attribute not supported in raw format");
     break;
   case Attribute::DereferenceableOrNull:
     llvm_unreachable("dereferenceable_or_null attribute not supported in raw "
                      "format");
     break;
   case Attribute::ArgMemOnly:

lib/IR/Verifier.cpp

if (I->getKindAsEnum() == Attribute::NoReturn ||
         I->getKindAsEnum() == Attribute::MinSize ||
         I->getKindAsEnum() == Attribute::NoDuplicate ||
         I->getKindAsEnum() == Attribute::Builtin ||
         I->getKindAsEnum() == Attribute::NoBuiltin ||
         I->getKindAsEnum() == Attribute::Cold ||
         I->getKindAsEnum() == Attribute::OptimizeNone ||
         I->getKindAsEnum() == Attribute::JumpTable ||
         I->getKindAsEnum() == Attribute::Convergent ||
-        I->getKindAsEnum() == Attribute::ArgMemOnly) {
+        I->getKindAsEnum() == Attribute::ArgMemOnly ||
+        I->getKindAsEnum() == Attribute::NoRecurse) {
       if (!isFunction) {
         CheckFailed("Attribute '" + I->getAsString() +
                     "' only applies to functions!", V);
         return;
       }
     } else if (I->getKindAsEnum() == Attribute::ReadOnly ||
                I->getKindAsEnum() == Attribute::ReadNone) {
       if (Idx == 0) {

test/Bindings/llvm-c/invalid-bitcode.test

 ; RUN: not llvm-c-test --module-dump < %S/Inputs/invalid.ll.bc 2>&1 | FileCheck %s
 
-CHECK: Error parsing bitcode: Unknown attribute kind (48)
+CHECK: Error parsing bitcode: Unknown attribute kind (50)

test/Bitcode/attributes.ll

 }
 
 declare void @nobuiltin()
 
 define void @f34()
 ; CHECK: define void @f34()
 {
         call void @nobuiltin() nobuiltin
-; CHECK: call void @nobuiltin() #27
+; CHECK: call void @nobuiltin() #28
         ret void;
 }
 
 define void @f35() optnone noinline
 ; CHECK: define void @f35() #23
 {
         ret void;
 }
define "string_attribute" void @f45(i32 "string_attribute") {
   ret void
 }
 
 ; CHECK: define "string_attribute_with_value"="value" void @f46(i32 "string_attribute_with_value"="value")
 define "string_attribute_with_value"="value" void @f46(i32 "string_attribute_with_value"="value") {
   ret void
 }
 
+; CHECK: define void @f47() #27
+define void @f47() norecurse {
+  ret void
+}
+
 ; CHECK: attributes #0 = { noreturn }
 ; CHECK: attributes #1 = { nounwind }
 ; CHECK: attributes #2 = { readnone }
 ; CHECK: attributes #3 = { readonly }
 ; CHECK: attributes #4 = { noinline }
 ; CHECK: attributes #5 = { alwaysinline }
 ; CHECK: attributes #6 = { optsize }
 ; CHECK: attributes #7 = { ssp }

 ; CHECK: attributes #19 = { sanitize_memory }
 ; CHECK: attributes #20 = { "cpu"="cortex-a8" }
 ; CHECK: attributes #21 = { sspstrong }
 ; CHECK: attributes #22 = { minsize }
 ; CHECK: attributes #23 = { noinline optnone }
 ; CHECK: attributes #24 = { jumptable }
 ; CHECK: attributes #25 = { convergent }
 ; CHECK: attributes #26 = { argmemonly }
-; CHECK: attributes #27 = { nobuiltin }
+; CHECK: attributes #27 = { norecurse }
+; CHECK: attributes #28 = { nobuiltin }

test/Bitcode/compatibility.ll

 declare void @f.sspstrong() sspstrong
 ; CHECK: declare void @f.sspstrong() #28
 declare void @f.thunk() "thunk"
 ; CHECK: declare void @f.thunk() #29
 declare void @f.uwtable() uwtable
 ; CHECK: declare void @f.uwtable() #30
 declare void @f.kvpair() "cpu"="cortex-a8"
 ; CHECK:declare void @f.kvpair() #31
+declare void @f.norecurse() norecurse
+; CHECK: declare void @f.norecurse() #32
 
 ; Functions -- section
 declare void @f.section() section "80"
 ; CHECK: declare void @f.section() section "80"
 
 ; Functions -- comdat
 define void @f.comdat_any() comdat($comdat.any) {
 ; CHECK: define void @f.comdat_any() comdat($comdat.any)

 ; Functions -- Prologue data
 declare void @f.prologuei32() prologue i32 1684365669
 ; CHECK: declare void @f.prologuei32() prologue i32 1684365669
 declare void @f.prologuearray() prologue [4 x i32] [i32 0, i32 1, i32 2, i32 3]
 ; CHECK: declare void @f.prologuearray() prologue [4 x i32] [i32 0, i32 1, i32 2, i32 3]
 
 ; Functions -- Personality constant
 declare void @llvm.donothing() nounwind readnone
-; CHECK: declare void @llvm.donothing() #32
+; CHECK: declare void @llvm.donothing() #33
 define void @f.no_personality() personality i8 3 {
 ; CHECK: define void @f.no_personality() personality i8 3
   invoke void @llvm.donothing() to label %normal unwind label %exception
 exception:
   %cleanup = landingpad i8 cleanup
   br label %normal
 normal:
   ret void
exit:
   ; CHECK: phi i32 [ %v1, %L1 ], [ %v2, %L2 ], [ %op1, %entry ]
 
   select i1 true, i32 0, i32 1
   ; CHECK: select i1 true, i32 0, i32 1
   select <2 x i1> <i1 true, i1 false>, <2 x i8> <i8 2, i8 3>, <2 x i8> <i8 3, i8 2>
   ; CHECK: select <2 x i1> <i1 true, i1 false>, <2 x i8> <i8 2, i8 3>, <2 x i8> <i8 3, i8 2>
 
   call void @f.nobuiltin() builtin
-  ; CHECK: call void @f.nobuiltin() #36
+  ; CHECK: call void @f.nobuiltin() #37
 
   call fastcc noalias i32* @f.noalias() noinline
   ; CHECK: call fastcc noalias i32* @f.noalias() #12
   tail call ghccc nonnull i32* @f.nonnull() minsize
   ; CHECK: tail call ghccc nonnull i32* @f.nonnull() #7
 
   ret void
 }

 ; CHECK: attributes #24 = { sanitize_memory }
 ; CHECK: attributes #25 = { sanitize_thread }
 ; CHECK: attributes #26 = { ssp }
 ; CHECK: attributes #27 = { sspreq }
 ; CHECK: attributes #28 = { sspstrong }
 ; CHECK: attributes #29 = { "thunk" }
 ; CHECK: attributes #30 = { uwtable }
 ; CHECK: attributes #31 = { "cpu"="cortex-a8" }
-; CHECK: attributes #32 = { nounwind readnone }
-; CHECK: attributes #33 = { nounwind readonly argmemonly }
-; CHECK: attributes #34 = { nounwind argmemonly }
-; CHECK: attributes #35 = { nounwind readonly }
-; CHECK: attributes #36 = { builtin }
+; CHECK: attributes #32 = { norecurse }
+; CHECK: attributes #33 = { nounwind readnone }
+; CHECK: attributes #34 = { nounwind readonly argmemonly }
+; CHECK: attributes #35 = { nounwind argmemonly }
+; CHECK: attributes #36 = { nounwind readonly }
+; CHECK: attributes #37 = { builtin }
 
 ;; Metadata
 
 ; Metadata -- Module flags
 !llvm.module.flags = !{!0, !1, !2, !4, !5, !6}
 ; CHECK: !llvm.module.flags = !{!0, !1, !2, !4, !5, !6}
 
 !0 = !{i32 1, !"mod1", i32 0}

test/Bitcode/invalid.ll

 ; RUN:  not llvm-dis < %s.bc 2>&1 | FileCheck %s
 
-; CHECK: llvm-dis{{(\.EXE|\.exe)?}}: error: Unknown attribute kind (48)
+; CHECK: llvm-dis{{(\.EXE|\.exe)?}}: error: Unknown attribute kind (50)
 
 ; invalid.ll.bc has an invalid attribute number.
 ; The test checks that LLVM reports the error and doesn't access freed memory
 ; in doing so.

test/LTO/X86/invalid.ll

 ; RUN: not llvm-lto %S/Inputs/invalid.ll.bc 2>&1 | FileCheck %s
 
 
-; CHECK: llvm-lto{{.*}}: error loading file '{{.*}}/Inputs/invalid.ll.bc': Unknown attribute kind (48)
+; CHECK: llvm-lto{{.*}}: error loading file '{{.*}}/Inputs/invalid.ll.bc': Unknown attribute kind (50)