[PATCH] D14227: Add a new attribute: norecurse

[Adding llvm-dev and re-stating the situation for llvm-dev’s benefit]

RFC: A new attribute, “norecurse”.

In some cases, it is possible to demote global variables to local variables. This is possible when the global is only used in one function, and that function is known not to recurse (because if the function recurses, a local variable cannot be equivalent to a global as the global would hold state over the recursive call).

GlobalOpt has this ability already, however it is currently (a) weak and (b) broken.

GlobalOpt has a special case for the function “main”. It assumes that any function called “main” with external linkage is by definition non-recursive. It does this because in C++, main is defined by the standard not to recurse. However, this is not the case in C, so GlobalOpt will happily break C code.

GlobalOpt also currently won’t even attempt to discover functions that don’t recurse - it only checks “main”.

What I’d like to do is improve GlobalOpt to be more aggressive with demoting globals to locals, and to do that I need to teach it which functions are known to be non-recursive. At the same time I’d really like to fix the “main” kludge.

There are three options I see:

  1. Just use an analysis pass to infer non-recursiveness as a property. This can be a simple SCC pass which is queried by GlobalOpt.
  2. Add an attribute, “norecurse”. This would be inferred just like above by FunctionAttrs in the general case, but it also allows frontends to add the attribute if they have specific knowledge - for example “main” in C++ mode.
  3. (1), but use metadata to add the non-recursiveness information in the frontend, to solve the “main” problem.

What I’m suggesting here is (2). I have no real problem implementing (3) instead, and I think it’s something that’s worthwhile discussing. Adding new metadata is very cheap and easy and doesn’t seem to have many downsides as an option.

Hopefully I’ve described the problem and potential solutions well enough - what are peoples’ thoughts? I quite like the attribute solution best, but I’d be happy with anything that moves us forward.

Cheers,

James

From: "James Molloy via llvm-dev" <llvm-dev@lists.llvm.org>
To: "Philip Reames" <listmail@philipreames.com>,
reviews+D14227+public+6a20206dc9791b02@reviews.llvm.org, "James
Molloy" <james.molloy@arm.com>, "manman ren" <manman.ren@gmail.com>,
dexonsmith@apple.com, "mehdi amini" <mehdi.amini@apple.com>, "LLVM
Dev" <llvm-dev@lists.llvm.org>
Cc: "LLVM Commits" <llvm-commits@lists.llvm.org>
Sent: Thursday, November 5, 2015 9:44:45 AM
Subject: Re: [llvm-dev] [PATCH] D14227: Add a new attribute:
norecurse

[Adding llvm-dev and re-stating the situation for llvm-dev's benefit]

RFC: A new attribute, "norecurse".

In some cases, it is possible to demote global variables to local
variables. This is possible when the global is only used in one
function, and that function is known not to recurse (because if the
function recurses, a local variable cannot be equivalent to a global
as the global would hold state over the recursive call).

GlobalOpt has this ability already, however it is currently (a) weak
and (b) broken.

GlobalOpt has a special case for the function "main". It assumes that
any function called "main" with external linkage is by definition
non-recursive. It does this because in C++, main is defined by the
standard not to recurse. However, this is not the case in C, so
GlobalOpt will happily break C code.

GlobalOpt also currently won't even attempt to discover functions
that don't recurse - it only checks "main".

What I'd like to do is improve GlobalOpt to be more aggressive with
demoting globals to locals, and to do that I need to teach it which
functions are known to be non-recursive. At the same time I'd really
like to fix the "main" kludge.

There are three options I see:
1. Just use an analysis pass to infer non-recursiveness as a
property. This can be a simple SCC pass which is queried by
GlobalOpt.
2. Add an attribute, "norecurse". This would be inferred just like
above by FunctionAttrs in the general case, but it also allows
frontends to add the attribute if they have specific knowledge - for
example "main" in C++ mode.
3. (1), but use metadata to add the non-recursiveness information in
the frontend, to solve the "main" problem.

What I'm suggesting here is (2).

+1

This is a very generic property, and I'm happy with the conciseness provided by an attribute.

-Hal

[Adding llvm-dev and re-stating the situation for llvm-dev's benefit]

RFC: A new attribute, "norecurse".

In some cases, it is possible to demote global variables to local variables.
This is possible when the global is only used in one function, and that
function is known not to recurse (because if the function recurses, a local
variable cannot be equivalent to a global as the global would hold state
over the recursive call).

GlobalOpt has this ability already, however it is currently (a) weak and (b)
broken.

GlobalOpt has a special case for the function "main". It assumes that any
function called "main" with external linkage is by definition non-recursive.
It does this because in C++, main is defined by the standard not to recurse.
However, this is not the case in C, so GlobalOpt will happily break C code.

GlobalOpt also currently won't even attempt to discover functions that don't
recurse - it only checks "main".

What I'd like to do is improve GlobalOpt to be more aggressive with demoting
globals to locals, and to do that I need to teach it which functions are
known to be non-recursive. At the same time I'd really like to fix the
"main" kludge.

There are three options I see:
  1. Just use an analysis pass to infer non-recursiveness as a property.
This can be a simple SCC pass which is queried by GlobalOpt.
  2. Add an attribute, "norecurse". This would be inferred just like above
by FunctionAttrs in the general case, but it also allows frontends to add
the attribute if they have specific knowledge - for example "main" in C++
mode.
  3. (1), but use metadata to add the non-recursiveness information in the
frontend, to solve the "main" problem.

What I'm suggesting here is (2). I have no real problem implementing (3)
instead, and I think it's something that's worthwhile discussing. Adding new
metadata is very cheap and easy and doesn't seem to have many downsides as
an option.

Hopefully I've described the problem and potential solutions well enough -
what are peoples' thoughts? I quite like the attribute solution best, but
I'd be happy with anything that moves us forward.

I think (2) is a good solution, but am wondering whether you intend to
expose that attribute to users, or whether it's one that can only be
created implicitly by the compiler?

~Aaron

Hi Aaron,

I think it must necessarily be exposed to users - clang must add it in certain circumstances for example. I don’t think this is particularly different to many other attributes such as nocapture/nounwind, that are exposed to users and can be set by users in exceptional circumstances but are primarily inferred by the midend.

James

Hi Aaron,

I think it must necessarily be exposed to users - clang must add it in
certain circumstances for example. I don't think this is particularly
different to many other attributes such as nocapture/nounwind, that are
exposed to users and can be set by users in exceptional circumstances but
are primarily inferred by the midend.

Sorry, I was unclear. I meant to Clang users as a language-level
attribute (e.g., [[clang::norecurse]]), not LLVM users as an IR-level
attribute.

~Aaron

Ah I see.

I can’t think of a way that would help users in any particular way offhand. I hadn’t considered exposing it to clang users - do you think there is merit in that?

James

Ah I see.

I can't think of a way that would help users in any particular way offhand.
I hadn't considered exposing it to clang users - do you think there is merit
in that?

I would prefer to avoid it, actually. :smiley:

~Aaron

+1

I think (2), an IR-level attribute, makes the most sense.

I agree we should avoid exposing this as a clang attribute (at least to start); I imagine it would be easy to misuse.

Hi,

OK, great, it sounds like people are happy with this. I’ll go ahead and land the patch.

Cheers,

James

The test case that you added in this revision fails on several of the power buildbots (for example, http://lab.llvm.org:8011/builders/clang-ppc64-elf-linux2/builds/20127) and also when I build it locally:

FAIL: Clang :: CodeGenCXX/main-norecurse.cpp (2951 of 27722)
******************** TEST 'Clang :: CodeGenCXX/main-norecurse.cpp' FAILED ********************
Script:

Hi Bill,

Ah, I see, it’s the signext that’s confusing it. I’ve committed a fix in r253055 - let me know if that works for you.

Cheers,

James

That does seem to have cleared it up. Thank you!