[RFC] Defining Infinite Loops

Hello everyone,

The topic of whether or not LLVM allows for infinite loops has come up a lot recently (several times this week already). Regarding motivation, there are two important facts:

1. Some languages, such as Java, have well-defined infinite loops. See:

      Chapter 17. Threads and Locks

    and:

      Chapter 17. Threads and Locks

    and, as a community, it seems to be important for us to support such languages. That means that we must have a way, at the IR level, to support and model infinite loops.

  2. Other languages, such a C and C++, allow us to assume that otherwise-side-effect-free loops terminate, specifically, for C++, 1.10p27 says:

     The implementation may assume that any thread will eventually do one of the following:
       - terminate
       - make a call to a library I/O function
       - access or modify a volatile object, or
       - perform a synchronization operation or an atomic operation
  
     [Note: This is intended to allow compiler transformations such as removal of empty loops, even
      when termination cannot be proven. — end note ]

     and taking advantage of these guarantees is part of providing a high-quality optimizer for C/C++ programs.

And this leaves us somewhat in a bind. To provide a high-quality C/C++ optimizer, we want to take advantage of this guarantee, but we can't do so in a generic sense without harming our ability to serve as a compiler for other languages.

In 2010, Nick proposed to add a 'halting' attribute that could be added to functions to indicate that they would not execute indefinitely (http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html). At the time that the patch was proposed, there were infrastructure problems with inferring the attribute for functions with loops (related to using function-level analysis passes from a CGSCC pass), but hopefully those will be fixed with the new pass manager. Regardless, however, such inference is much more powerful if it can take advantage of the guarantees that C/C++ provide.

Thus, while I would eventually like a 'halting' attribute, or some variant of that (including, for example, the lack of calls to longjmp), I think that a first step is to provide an attribute that Clang, and other frontends, can add when producing IR from sources where the language provides C/C++-like guarantees on loop termination. This attribute would indicate that the function will not execute indefinitely without producing some externally-observable side effect (calling an external function or executing a volatile/atomic memory access). I could name this attribute 'finite', but bikeshedding is welcome.

With such an attribute in place, we would be able to clarify our overall position on infinite loops, be in a stronger position to infer more specific function properties (like halting), and can put in place generally-correct fixes to outstanding bugs (PR24078, for example). I know there are some Clang users who want it to optimize while honoring infinite loops, and I think adding this attribute helps them as well (assuming we'd provide some non-default option to prevent Clang from adding it). Thoughts?

Thanks again,
Hal

FWIW, I’m very much in favor of having a firm and clear answer to these questions.

I also agree that it is an absolute requirement that LLVM have some mechanism for supporting both languages with defined behavior for infinite loops and a language requirement that all loops terminate.

However, I’d like to float an alternative approach. I’ve not spent a lot of time thinking about it, so I’m not sure its actually better. I’m wondering if you’ve already thought about it.

What if we have an @llvm.noop.sideeffect() or some such which doesn’t read or write memory in any way, but which a frontend can place inside a loop body to mark that its execution (perhaps infinitely) is in-and-of-itself a side effect of the program. We could then teach loop unrolling or the few other things that would care to collapse multiple ones into a single one, and not count them towards anything.

I know an intrinsic is kind of awkward for this, but it seems like the least bad way we have to annotate a loop in a fully generic way. I’d somewhat like this to be a property of the loop and not of the function. And it really needs to be truly generic, handling unnatural CFGs and even recursion-loops. My only idea for how to accomplish that is an intrinsic to mark the dynamic path which if executed infinitely can’t be eliminated.

As for why I’m particularly interested in this being a property of the loop, consider if you were to have a mixture of Java and C++ code, all compiled to LLVM. How do you inline between them?

Anyways, I’ve not spent a lot of time thinking about what this might break for languages that allow infinite loops. Maybe it doesn’t work as well as I’d hope.

-Chandler

From: "Chandler Carruth" <chandlerc@google.com>
To: "Hal Finkel" <hfinkel@anl.gov>, "LLVM Dev" <llvmdev@cs.uiuc.edu>
Sent: Thursday, July 16, 2015 1:00:05 AM
Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops

FWIW, I'm very much in favor of having a firm and clear answer to
these questions.

I also agree that it is an absolute requirement that LLVM have *some*
mechanism for supporting both languages with defined behavior for
infinite loops and a language requirement that all loops terminate.

However, I'd like to float an alternative approach. I've not spent a
lot of time thinking about it, so I'm not sure its actually better.
I'm wondering if you've already thought about it.

What if we have an @llvm.noop.sideeffect() or some such which doesn't
read or write memory in any way, but which a frontend can place
inside a loop body to mark that its execution (perhaps infinitely)
is in-and-of-itself a side effect of the program. We could then
teach loop unrolling or the few other things that would care to
collapse multiple ones into a single one, and not count them towards
anything.

I know an intrinsic is kind of awkward for this, but it seems like
the least bad way we have to annotate a loop in a fully generic way.
I'd somewhat like this to be a property of the *loop* and not of the
function. And it really needs to be truly generic, handling
unnatural CFGs and even recursion-loops. My only idea for how to
accomplish that is an intrinsic to mark the dynamic path which if
executed infinitely can't be eliminated.

My largest concern is that the frontend would need to add these things all over the place, not just before the loop backedges. For one thing, if the language has gotos, where should they be inserted? Before every branch will be conservatively correct, but I'm worried that will unnecessarily block optimizations. They'd also be needed at the entry to every function. On the other hand, maybe if we added an optimization that removed these things along any control-flow path that already had any other side effect, it might not be too bad?

As for why I'm particularly interested in this being a property of
the loop, consider if you were to have a mixture of Java and C++
code, all compiled to LLVM. How do you inline between them?

You add the attribute to the caller. FWIW, I suspect I might care a lot about this particular case (because I believe that Fortran has defined behavior for infinite loops).

-Hal

From: “Chandler Carruth” <chandlerc@google.com>
To: “Hal Finkel” <hfinkel@anl.gov>, “LLVM Dev” <llvmdev@cs.uiuc.edu>
Sent: Thursday, July 16, 2015 1:00:05 AM
Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops

FWIW, I’m very much in favor of having a firm and clear answer to
these questions.

I also agree that it is an absolute requirement that LLVM have some
mechanism for supporting both languages with defined behavior for
infinite loops and a language requirement that all loops terminate.

However, I’d like to float an alternative approach. I’ve not spent a
lot of time thinking about it, so I’m not sure its actually better.
I’m wondering if you’ve already thought about it.

What if we have an @llvm.noop.sideeffect() or some such which doesn’t
read or write memory in any way, but which a frontend can place
inside a loop body to mark that its execution (perhaps infinitely)
is in-and-of-itself a side effect of the program. We could then
teach loop unrolling or the few other things that would care to
collapse multiple ones into a single one, and not count them towards
anything.

I know an intrinsic is kind of awkward for this, but it seems like
the least bad way we have to annotate a loop in a fully generic way.
I’d somewhat like this to be a property of the loop and not of the
function. And it really needs to be truly generic, handling
unnatural CFGs and even recursion-loops. My only idea for how to
accomplish that is an intrinsic to mark the dynamic path which if
executed infinitely can’t be eliminated.

My largest concern is that the frontend would need to add these things all over the place, not just before the loop backedges. For one thing, if the language has gotos, where should they be inserted?

The target of every goto.

For computed goto, very label whose address is taken.

This at least doesn’t seem that bad to me.

Before every branch will be conservatively correct, but I’m worried that will unnecessarily block optimizations. They’d also be needed at the entry to every function.

Only external, address taken, or internal-and-recursively-called functions. All of which we already have some blockers to optimization, so this part i’m not worried about.

On the other hand, maybe if we added an optimization that removed these things along any control-flow path that already had any other side effect, it might not be too bad?

Absolutely, much like lower-expect, we’d need to make sure that easy cases were folded quickly in the optimizer so this didn’t get out of hand.

As for why I’m particularly interested in this being a property of
the loop, consider if you were to have a mixture of Java and C++
code, all compiled to LLVM. How do you inline between them?

You add the attribute to the caller.

This has the really unfortunate side effect of pessimizing code during cross language optimizations.

FWIW, I suspect I might care a lot about this particular case (because I believe that Fortran has defined behavior for infinite loops).

Yea, you could argue that C does too, which is one reason why I’m so interested in this being done really well even in an LTO situation.

I think it would be really useful to not have this cross between adjacent loops after inlining when they come from different source languages, and it would be nice for it to not apply to nested loops when those nested loops were inlined from a language without this guarantee.

But I’m still not convinced that the noise of the intrinsic is definitely worth it. I come from the background of the C++ rules’ rationale, and so I naturally see the languages that define this as giving up optimizations and so wanting to localize the impact of that… Not sure that’s actually the right perspective though. ;]

Hello everyone,

The topic of whether or not LLVM allows for infinite loops has come up a lot recently (several times this week already). Regarding motivation, there are two important facts:

1. Some languages, such as Java, have well-defined infinite loops. See:

      Chapter 17. Threads and Locks

    and:

      Chapter 17. Threads and Locks

    and, as a community, it seems to be important for us to support such languages. That means that we must have a way, at the IR level, to support and model infinite loops.

  2. Other languages, such a C and C++, allow us to assume that otherwise-side-effect-free loops terminate, specifically, for C++, 1.10p27 says:

     The implementation may assume that any thread will eventually do one of the following:
       - terminate
       - make a call to a library I/O function
       - access or modify a volatile object, or
       - perform a synchronization operation or an atomic operation

     [Note: This is intended to allow compiler transformations such as removal of empty loops, even
      when termination cannot be proven. — end note ]

     and taking advantage of these guarantees is part of providing a high-quality optimizer for C/C++ programs.

And this leaves us somewhat in a bind. To provide a high-quality C/C++ optimizer, we want to take advantage of this guarantee, but we can't do so in a generic sense without harming our ability to serve as a compiler for other languages.

+1

In 2010, Nick proposed to add a 'halting' attribute that could be added to functions to indicate that they would not execute indefinitely (http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html). At the time that the patch was proposed, there were infrastructure problems with inferring the attribute for functions with loops (related to using function-level analysis passes from a CGSCC pass), but hopefully those will be fixed with the new pass manager. Regardless, however, such inference is much more powerful if it can take advantage of the guarantees that C/C++ provide.

Thus, while I would eventually like a 'halting' attribute, or some variant of that (including, for example, the lack of calls to longjmp), I think that a first step is to provide an attribute that Clang, and other frontends, can add when producing IR from sources where the language provides C/C++-like guarantees on loop termination. This attribute would indicate that the function will not execute indefinitely without producing some externally-observable side effect (calling an external function or executing a volatile/atomic memory access). I could name this attribute 'finite', but bikeshedding is welcome.

I'd call this "productive" (inspired from terminology used to describe
co-inductive data types) with the connotation that a "productive"
function cannot loop indefinitely without producing side effects
(volatile reads/writes, IO etc.).

-- Sanjoy

FWIW, I'm very much in favor of having a firm and clear answer to these
questions.

I also agree that it is an absolute requirement that LLVM have *some*
mechanism for supporting both languages with defined behavior for infinite
loops and a language requirement that all loops terminate.

However, I'd like to float an alternative approach. I've not spent a lot of
time thinking about it, so I'm not sure its actually better. I'm wondering
if you've already thought about it.

What if we have an @llvm.noop.sideeffect() or some such which doesn't read
or write memory in any way, but which a frontend can place inside a loop
body to mark that its execution (perhaps infinitely) is in-and-of-itself a
side effect of the program. We could then teach loop unrolling or the few
other things that would care to collapse multiple ones into a single one,
and not count them towards anything.

I know an intrinsic is kind of awkward for this, but it seems like the least
bad way we have to annotate a loop in a fully generic way. I'd somewhat like
this to be a property of the *loop* and not of the function. And it really
needs to be truly generic, handling unnatural CFGs and even recursion-loops.
My only idea for how to accomplish that is an intrinsic to mark the dynamic
path which if executed infinitely can't be eliminated.

I read this as: "the optimizer may legally remove only a finite number
of @llvm.noop.sideeffect calls from the program trace". It gets
really interesting here since for typical managed language
implementations, application threads have to "poll for safepoints"
(check if there is a pending request to halt from the GC). As of now
we insert these polls late (after most of the interesting
target-independent optimizations have run), but if we were to change
our strategy to insert these polls early and wanted LLVM to optimize
these, the optimization rules would be similar: "the optimizer may not
introduce an unbounded wait between two polls (i.e. it is okay to
remove polls for a provably finite loop, but an infinite loop must
keep them)" [1]. So a @llvm.noop.sideeffect-like concept may be
generally useful in LLVM.

However, I don't think we can get away with just @llvm.noop.sideeffect
-- a function level attribute is required to know when it is okay to
DCE calls to readnone/readonly functions.

As for why I'm particularly interested in this being a property of the loop,
consider if you were to have a mixture of Java and C++ code, all compiled to
LLVM. How do you inline between them?

TBQH, I'd be okay losing some performance in this case. And we can
always be aggressive about upgrading non-productive [2] functions to
productive if they only call productive functions and have no infinite
loops.

[1]: there are quality of implementation issues on how frequently an
application thread checks for a pending safepoint request

[2]: using the definition for "productive" == "this function produces some
output (volatile load/store, IO, etc.) in a finite amount of time"

-- Sanjoy

From: "Sanjoy Das" <sanjoy@playingwithpointers.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "LLVM Dev" <llvmdev@cs.uiuc.edu>, "Nick Lewycky" <nicholas@mxc.ca>, "Philip Reames" <listmail@philipreames.com>,
"David Majnemer" <david.majnemer@gmail.com>, "chandlerc" <chandlerc@gmail.com>
Sent: Thursday, July 16, 2015 3:28:47 AM
Subject: Re: [RFC] Defining Infinite Loops

> Hello everyone,
>
> The topic of whether or not LLVM allows for infinite loops has come
> up a lot recently (several times this week already). Regarding
> motivation, there are two important facts:
>
> 1. Some languages, such as Java, have well-defined infinite loops.
> See:
>
> Chapter 17. Threads and Locks
>
> and:
>
> Chapter 17. Threads and Locks
>
> and, as a community, it seems to be important for us to support
> such languages. That means that we must have a way, at the IR
> level, to support and model infinite loops.
>
> 2. Other languages, such a C and C++, allow us to assume that
> otherwise-side-effect-free loops terminate, specifically, for
> C++, 1.10p27 says:
>
> The implementation may assume that any thread will eventually
> do one of the following:
> - terminate
> - make a call to a library I/O function
> - access or modify a volatile object, or
> - perform a synchronization operation or an atomic operation
>
> [Note: This is intended to allow compiler transformations such
> as removal of empty loops, even
> when termination cannot be proven. — end note ]
>
> and taking advantage of these guarantees is part of providing
> a high-quality optimizer for C/C++ programs.
>
> And this leaves us somewhat in a bind. To provide a high-quality
> C/C++ optimizer, we want to take advantage of this guarantee, but
> we can't do so in a generic sense without harming our ability to
> serve as a compiler for other languages.

+1

>
> In 2010, Nick proposed to add a 'halting' attribute that could be
> added to functions to indicate that they would not execute
> indefinitely
> (http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html).
> At the time that the patch was proposed, there were infrastructure
> problems with inferring the attribute for functions with loops
> (related to using function-level analysis passes from a CGSCC
> pass), but hopefully those will be fixed with the new pass
> manager. Regardless, however, such inference is much more powerful
> if it can take advantage of the guarantees that C/C++ provide.
>
> Thus, while I would eventually like a 'halting' attribute, or some
> variant of that (including, for example, the lack of calls to
> longjmp), I think that a first step is to provide an attribute
> that Clang, and other frontends, can add when producing IR from
> sources where the language provides C/C++-like guarantees on loop
> termination. This attribute would indicate that the function will
> not execute indefinitely without producing some
> externally-observable side effect (calling an external function or
> executing a volatile/atomic memory access). I could name this
> attribute 'finite', but bikeshedding is welcome.

I'd call this "productive" (inspired from terminology used to
describe
co-inductive data types) with the connotation that a "productive"
function cannot loop indefinitely without producing side effects
(volatile reads/writes, IO etc.).

I like this term better than "finite."

Thanks again,
Hal

From: "Sanjoy Das" <sanjoy@playingwithpointers.com>
To: "Chandler Carruth" <chandlerc@google.com>
Cc: "Hal Finkel" <hfinkel@anl.gov>, "LLVM Dev" <llvmdev@cs.uiuc.edu>
Sent: Thursday, July 16, 2015 3:52:09 AM
Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops

> FWIW, I'm very much in favor of having a firm and clear answer to
> these
> questions.
>
> I also agree that it is an absolute requirement that LLVM have
> *some*
> mechanism for supporting both languages with defined behavior for
> infinite
> loops and a language requirement that all loops terminate.
>
> However, I'd like to float an alternative approach. I've not spent
> a lot of
> time thinking about it, so I'm not sure its actually better. I'm
> wondering
> if you've already thought about it.
>
> What if we have an @llvm.noop.sideeffect() or some such which
> doesn't read
> or write memory in any way, but which a frontend can place inside a
> loop
> body to mark that its execution (perhaps infinitely) is
> in-and-of-itself a
> side effect of the program. We could then teach loop unrolling or
> the few
> other things that would care to collapse multiple ones into a
> single one,
> and not count them towards anything.
>
> I know an intrinsic is kind of awkward for this, but it seems like
> the least
> bad way we have to annotate a loop in a fully generic way. I'd
> somewhat like
> this to be a property of the *loop* and not of the function. And it
> really
> needs to be truly generic, handling unnatural CFGs and even
> recursion-loops.
> My only idea for how to accomplish that is an intrinsic to mark the
> dynamic
> path which if executed infinitely can't be eliminated.

I read this as: "the optimizer may legally remove only a finite
number
of @llvm.noop.sideeffect calls from the program trace". It gets
really interesting here since for typical managed language
implementations, application threads have to "poll for safepoints"
(check if there is a pending request to halt from the GC). As of now
we insert these polls late (after most of the interesting
target-independent optimizations have run), but if we were to change
our strategy to insert these polls early and wanted LLVM to optimize
these, the optimization rules would be similar: "the optimizer may
not
introduce an unbounded wait between two polls (i.e. it is okay to
remove polls for a provably finite loop, but an infinite loop must
keep them)" [1]. So a @llvm.noop.sideeffect-like concept may be
generally useful in LLVM.

However, I don't think we can get away with just
@llvm.noop.sideeffect
-- a function level attribute is required to know when it is okay to
DCE calls to readnone/readonly functions.

I think you're right, in a sense, but to DCE calls, we need something stronger. Specifically, we need the kind of 'halting' attribute that Nick proposed. Because we need to know that the function really will return normally within some finite time. Thus, having a scheme such as this, or the 'productive' attribute, helps with inferring the 'halting' attribute, but is not a replacement for it.

> As for why I'm particularly interested in this being a property of
> the loop,
> consider if you were to have a mixture of Java and C++ code, all
> compiled to
> LLVM. How do you inline between them?

TBQH, I'd be okay losing some performance in this case. And we can
always be aggressive about upgrading non-productive [2] functions to
productive if they only call productive functions and have no
infinite
loops.

The other question is: Does having this intrinsic make it easier to program correct IR transformations. I'm leaning toward yes (because we need to check loops for side effects anyway), and thus I'm slightly in favor of this intrinsic. Thoughts?

-Hal

From: "Chandler Carruth" <chandlerc@google.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "LLVM Dev" <llvmdev@cs.uiuc.edu>
Sent: Thursday, July 16, 2015 2:33:21 AM
Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops

> From: "Chandler Carruth" < chandlerc@google.com >
> To: "Hal Finkel" < hfinkel@anl.gov >, "LLVM Dev" <
> llvmdev@cs.uiuc.edu >
> Sent: Thursday, July 16, 2015 1:00:05 AM
> Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops
>
>
> FWIW, I'm very much in favor of having a firm and clear answer to
> these questions.
>
> I also agree that it is an absolute requirement that LLVM have
> *some*
> mechanism for supporting both languages with defined behavior for
> infinite loops and a language requirement that all loops terminate.
>
>
> However, I'd like to float an alternative approach. I've not spent
> a
> lot of time thinking about it, so I'm not sure its actually better.
> I'm wondering if you've already thought about it.
>
>
> What if we have an @llvm.noop.sideeffect() or some such which
> doesn't
> read or write memory in any way, but which a frontend can place
> inside a loop body to mark that its execution (perhaps infinitely)
> is in-and-of-itself a side effect of the program. We could then
> teach loop unrolling or the few other things that would care to
> collapse multiple ones into a single one, and not count them
> towards
> anything.
>
>
> I know an intrinsic is kind of awkward for this, but it seems like
> the least bad way we have to annotate a loop in a fully generic
> way.
> I'd somewhat like this to be a property of the *loop* and not of
> the
> function. And it really needs to be truly generic, handling
> unnatural CFGs and even recursion-loops. My only idea for how to
> accomplish that is an intrinsic to mark the dynamic path which if
> executed infinitely can't be eliminated.

My largest concern is that the frontend would need to add these
things all over the place, not just before the loop backedges. For
one thing, if the language has gotos, where should they be inserted?

The target of every goto.

For computed goto, very label whose address is taken.

This at least doesn't seem that bad to me.

Before every branch will be conservatively correct, but I'm worried
that will unnecessarily block optimizations. They'd also be needed
at the entry to every function.

Only external, address taken, or internal-and-recursively-called
functions. All of which we already have some blockers to
optimization, so this part i'm not worried about.

On the other hand, maybe if we added an optimization that removed
these things along any control-flow path that already had any other
side effect, it might not be too bad?

Absolutely, much like lower-expect, we'd need to make sure that easy
cases were folded quickly in the optimizer so this didn't get out of
hand.

>
>
> As for why I'm particularly interested in this being a property of
> the loop, consider if you were to have a mixture of Java and C++
> code, all compiled to LLVM. How do you inline between them?
>

You add the attribute to the caller.

This has the really unfortunate side effect of pessimizing code
during cross language optimizations.

FWIW, I suspect I might care a lot about this particular case
(because I believe that Fortran has defined behavior for infinite
loops).

Yea, you could argue that C does too, which is one reason why I'm so
interested in this being done really well even in an LTO situation.

I think it would be really useful to not have this cross between
adjacent loops after inlining when they come from different source
languages, and it would be nice for it to not apply to nested loops
when those nested loops were inlined from a language without this
guarantee.

But I'm still not convinced that the noise of the intrinsic is
*definitely* worth it. I come from the background of the C++ rules'
rationale, and so I naturally see the languages that define this as
giving up optimizations and so wanting to localize the impact of
that... Not sure that's actually the right perspective though. ;]

I'm leaning toward agreeing with you, primarily because I think it will more-naturally fit into the optimizer than the attribute. We need to check loops for side effects anyway (if we otherwise default to C++-like rules), and so this intrinsic will do the right thing without any special logic.

-Hal

I’m curious why are you proposing an attribute to mark functions that will terminate instead of an attribute to mark functions that may not terminate? I.e. why isn’t the “default” the C/C++ behavior and introducing an opt-out for other languages?
(I haven’t thought too much about it)

Thanks,

From: "Mehdi Amini" <mehdi.amini@apple.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "LLVM Dev" <llvmdev@cs.uiuc.edu>
Sent: Thursday, July 16, 2015 3:04:44 PM
Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops

>
> Hello everyone,
>
> The topic of whether or not LLVM allows for infinite loops has come
> up a lot recently (several times this week already). Regarding
> motivation, there are two important facts:
>
> 1. Some languages, such as Java, have well-defined infinite loops.
> See:
>
> Chapter 17. Threads and Locks
>
> and:
>
> Chapter 17. Threads and Locks
>
> and, as a community, it seems to be important for us to support
> such languages. That means that we must have a way, at the IR
> level, to support and model infinite loops.
>
> 2. Other languages, such a C and C++, allow us to assume that
> otherwise-side-effect-free loops terminate, specifically, for
> C++, 1.10p27 says:
>
> The implementation may assume that any thread will eventually
> do one of the following:
> - terminate
> - make a call to a library I/O function
> - access or modify a volatile object, or
> - perform a synchronization operation or an atomic operation
>
> [Note: This is intended to allow compiler transformations such
> as removal of empty loops, even
> when termination cannot be proven. — end note ]
>
> and taking advantage of these guarantees is part of providing a
> high-quality optimizer for C/C++ programs.
>
> And this leaves us somewhat in a bind. To provide a high-quality
> C/C++ optimizer, we want to take advantage of this guarantee, but
> we can't do so in a generic sense without harming our ability to
> serve as a compiler for other languages.
>
> In 2010, Nick proposed to add a 'halting' attribute that could be
> added to functions to indicate that they would not execute
> indefinitely
> (http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html).
> At the time that the patch was proposed, there were infrastructure
> problems with inferring the attribute for functions with loops
> (related to using function-level analysis passes from a CGSCC
> pass), but hopefully those will be fixed with the new pass
> manager. Regardless, however, such inference is much more powerful
> if it can take advantage of the guarantees that C/C++ provide.
>
> Thus, while I would eventually like a 'halting' attribute, or some
> variant of that (including, for example, the lack of calls to
> longjmp), I think that a first step is to provide an attribute
> that Clang, and other frontends, can add when producing IR from
> sources where the language provides C/C++-like guarantees on loop
> termination. This attribute would indicate that the function will
> not execute indefinitely without producing some
> externally-observable side effect (calling an external function or
> executing a volatile/atomic memory access). I could name this
> attribute 'finite', but bikeshedding is welcome.

I’m curious why are you proposing an attribute to mark functions that
will terminate instead of an attribute to mark functions that may
not terminate? I.e. why isn’t the “default” the C/C++ behavior and
introducing an opt-out for other languages?
(I haven’t thought too much about it)

I have no particular preference. Chandler's follow-up proposal effectively does this.

-Hal

From: "Sanjoy Das" <sanjoy@playingwithpointers.com>
To: "Chandler Carruth" <chandlerc@google.com>
Cc: "Hal Finkel" <hfinkel@anl.gov>, "LLVM Dev" <llvmdev@cs.uiuc.edu>
Sent: Thursday, July 16, 2015 3:52:09 AM
Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops

> FWIW, I'm very much in favor of having a firm and clear answer to
> these
> questions.
>
> I also agree that it is an absolute requirement that LLVM have
> *some*
> mechanism for supporting both languages with defined behavior for
> infinite
> loops and a language requirement that all loops terminate.
>
> However, I'd like to float an alternative approach. I've not spent
> a lot of
> time thinking about it, so I'm not sure its actually better. I'm
> wondering
> if you've already thought about it.
>
> What if we have an @llvm.noop.sideeffect() or some such which
> doesn't read
> or write memory in any way, but which a frontend can place inside a
> loop
> body to mark that its execution (perhaps infinitely) is
> in-and-of-itself a
> side effect of the program. We could then teach loop unrolling or
> the few
> other things that would care to collapse multiple ones into a
> single one,
> and not count them towards anything.
>
> I know an intrinsic is kind of awkward for this, but it seems like
> the least
> bad way we have to annotate a loop in a fully generic way. I'd
> somewhat like
> this to be a property of the *loop* and not of the function. And it
> really
> needs to be truly generic, handling unnatural CFGs and even
> recursion-loops.
> My only idea for how to accomplish that is an intrinsic to mark the
> dynamic
> path which if executed infinitely can't be eliminated.

I read this as: "the optimizer may legally remove only a finite
number
of @llvm.noop.sideeffect calls from the program trace". It gets
really interesting here since for typical managed language
implementations, application threads have to "poll for safepoints"
(check if there is a pending request to halt from the GC). As of now
we insert these polls late (after most of the interesting
target-independent optimizations have run), but if we were to change
our strategy to insert these polls early and wanted LLVM to optimize
these, the optimization rules would be similar: "the optimizer may
not
introduce an unbounded wait between two polls (i.e. it is okay to
remove polls for a provably finite loop, but an infinite loop must
keep them)" [1]. So a @llvm.noop.sideeffect-like concept may be
generally useful in LLVM.

However, I don't think we can get away with just
@llvm.noop.sideeffect
-- a function level attribute is required to know when it is okay to
DCE calls to readnone/readonly functions.

I think you're right, in a sense, but to DCE calls, we need something stronger. Specifically, we need the kind of 'halting' attribute that Nick proposed. Because we need to know that the function really will return normally within some finite time. Thus, having a scheme such as this, or the 'productive' attribute, helps with inferring the 'halting' attribute, but is not a replacement for it.

I think "productive + readonly" and "productive + readnone" can be
inferred to be "halting". In practice, the third case ("productive +
readwrite") cannot be removed most (all?) of the times anyway.

From: "Sanjoy Das" <sanjoy@playingwithpointers.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "LLVM Dev" <llvmdev@cs.uiuc.edu>, "Chandler Carruth" <chandlerc@google.com>
Sent: Thursday, July 16, 2015 3:14:27 PM
Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops

>> From: "Sanjoy Das" <sanjoy@playingwithpointers.com>
>> To: "Chandler Carruth" <chandlerc@google.com>
>> Cc: "Hal Finkel" <hfinkel@anl.gov>, "LLVM Dev"
>> <llvmdev@cs.uiuc.edu>
>> Sent: Thursday, July 16, 2015 3:52:09 AM
>> Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops
>>
>> > FWIW, I'm very much in favor of having a firm and clear answer
>> > to
>> > these
>> > questions.
>> >
>> > I also agree that it is an absolute requirement that LLVM have
>> > *some*
>> > mechanism for supporting both languages with defined behavior
>> > for
>> > infinite
>> > loops and a language requirement that all loops terminate.
>> >
>> > However, I'd like to float an alternative approach. I've not
>> > spent
>> > a lot of
>> > time thinking about it, so I'm not sure its actually better. I'm
>> > wondering
>> > if you've already thought about it.
>> >
>> > What if we have an @llvm.noop.sideeffect() or some such which
>> > doesn't read
>> > or write memory in any way, but which a frontend can place
>> > inside a
>> > loop
>> > body to mark that its execution (perhaps infinitely) is
>> > in-and-of-itself a
>> > side effect of the program. We could then teach loop unrolling
>> > or
>> > the few
>> > other things that would care to collapse multiple ones into a
>> > single one,
>> > and not count them towards anything.
>> >
>> > I know an intrinsic is kind of awkward for this, but it seems
>> > like
>> > the least
>> > bad way we have to annotate a loop in a fully generic way. I'd
>> > somewhat like
>> > this to be a property of the *loop* and not of the function. And
>> > it
>> > really
>> > needs to be truly generic, handling unnatural CFGs and even
>> > recursion-loops.
>> > My only idea for how to accomplish that is an intrinsic to mark
>> > the
>> > dynamic
>> > path which if executed infinitely can't be eliminated.
>>
>> I read this as: "the optimizer may legally remove only a finite
>> number
>> of @llvm.noop.sideeffect calls from the program trace". It gets
>> really interesting here since for typical managed language
>> implementations, application threads have to "poll for safepoints"
>> (check if there is a pending request to halt from the GC). As of
>> now
>> we insert these polls late (after most of the interesting
>> target-independent optimizations have run), but if we were to
>> change
>> our strategy to insert these polls early and wanted LLVM to
>> optimize
>> these, the optimization rules would be similar: "the optimizer may
>> not
>> introduce an unbounded wait between two polls (i.e. it is okay to
>> remove polls for a provably finite loop, but an infinite loop must
>> keep them)" [1]. So a @llvm.noop.sideeffect-like concept may be
>> generally useful in LLVM.
>>
>> However, I don't think we can get away with just
>> @llvm.noop.sideeffect
>> -- a function level attribute is required to know when it is okay
>> to
>> DCE calls to readnone/readonly functions.
>
> I think you're right, in a sense, but to DCE calls, we need
> something stronger. Specifically, we need the kind of 'halting'
> attribute that Nick proposed. Because we need to know that the
> function really will return normally within some finite time.
> Thus, having a scheme such as this, or the 'productive' attribute,
> helps with inferring the 'halting' attribute, but is not a
> replacement for it.

I think "productive + readonly" and "productive + readnone" can be
inferred to be "halting". In practice, the third case ("productive +
readwrite") cannot be removed most (all?) of the times anyway.

Yes, but there are other cases, like heap-to-stack conversion, where we need halting information on readwrite calls.

-Hal

So, GCC tried this, and it was a bit awkward.
(The intrinsic was called builtin_maybe_infinite_loop).
It was so awkward it never made it into a release

This in part because it had to be duplicated properly in a lot of
places to preserve the semantic, and it meant, for example, you
couldn't just do CFG updates without also sometimes having to copy
this intrinsic

(I supposed the counter argument is you could just not touch the CFG,
but even things like critical edge splitting might require moving
them, IIRC)

On the other hand, without loop metadata that is guaranteed kept up to
date (and attached to non-natural loops as well), i don't know that
you have a better option.

Mehdi Amini wrote:

Hello everyone,

The topic of whether or not LLVM allows for infinite loops has come up a lot recently (several times this week already). Regarding motivation, there are two important facts:

1. Some languages, such as Java, have well-defined infinite loops. See:

      Chapter 17. Threads and Locks

    and:

      Chapter 17. Threads and Locks

    and, as a community, it seems to be important for us to support such languages. That means that we must have a way, at the IR level, to support and model infinite loops.

  2. Other languages, such a C and C++, allow us to assume that otherwise-side-effect-free loops terminate, specifically, for C++, 1.10p27 says:

     The implementation may assume that any thread will eventually do one of the following:
       - terminate
       - make a call to a library I/O function
       - access or modify a volatile object, or
       - perform a synchronization operation or an atomic operation

     [Note: This is intended to allow compiler transformations such as removal of empty loops, even
      when termination cannot be proven. — end note ]

     and taking advantage of these guarantees is part of providing a high-quality optimizer for C/C++ programs.

And this leaves us somewhat in a bind. To provide a high-quality C/C++ optimizer, we want to take advantage of this guarantee, but we can't do so in a generic sense without harming our ability to serve as a compiler for other languages.

In 2010, Nick proposed to add a 'halting' attribute that could be added to functions to indicate that they would not execute indefinitely (http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html). At the time that the patch was proposed, there were infrastructure problems with inferring the attribute for functions with loops (related to using function-level analysis passes from a CGSCC pass), but hopefully those will be fixed with the new pass manager. Regardless, however, such inference is much more powerful if it can take advantage of the guarantees that C/C++ provide.

Thus, while I would eventually like a 'halting' attribute, or some variant of that (including, for example, the lack of calls to longjmp), I think that a first step is to provide an attribute that Clang, and other frontends, can add when producing IR from sources where the language provides C/C++-like guarantees on loop termination. This attribute would indicate that the function will not execute indefinitely without producing some externally-observable side effect (calling an external function or executing a volatile/atomic memory access). I could name this attribute 'finite', but bikeshedding is welcome.

I’m curious why are you proposing an attribute to mark functions that will terminate instead of an attribute to mark functions that may not terminate? I.e. why isn’t the “default” the C/C++ behavior and introducing an opt-out for other languages?
(I haven’t thought too much about it)

LLVM is not just a C or C++ compiler. You have to assume the worst for each function unless you know better. In this case that leads to not knowing whether an unannotated function may or may not terminate while one with an attribute on it is known to follow some guarantees.

The downside is that we'll put attributes on lots of functions in the common case. I think this is less of a concern.

Nick

FWIW, this is why I first started thinking along these lines. I’m increasingly thinking that if this approach works it will make the implementation of testing for this more natural in the optimizer. Simple things like instruction predicates will “just work”, etc.

I’m really interested in the downsides. You mentioned a few potential ones, but seem to be happy with my responses. I wonder, are there others?

That's what I was wondering too.

C++:

void foo() {
   for (unsigned i = 0; i < 3; ++i)
     java_infinite_loop();
}

Java:

public void java_infinite_loop() {
   while (true)
     ;
}

Once we inline, we get something like

void foo() {
   for (i = 0; i < 3; ++i) // marked as terminating
     while (true) // marked as infinite
       ;
}

Is this program ill-formed? If not, how would we resolve the conflicting information?

On the other hand, how much is there to gain by exploiting the C++'s assumption? Or to put it another way, what would be lose in practice if we were to ignore it?

-Krzysztof

I’m really not a fan of this approach. I think it could be made to work, but I suspect we’d run into a lot of quality of implementation issues if we went down this route. We’d have to teach many places in the optimizer to merge or split such calls. Consider simple things like tail commoning, if-then-else hoisting, or the like. In each of these, we’d need code to recognize having the intrinsic on one path, but not the other, and then still perform the optimization. Think the various debug intrinsics, but worse. I worry about the interactions with memory aliasing and hoisting rules. We don’t currently have the notion of a non-memory side effect in LLVM. To prevent this intrinsic from being DCE’d we’d likely need to mark it as writing to some known location. Given the number of places in the optimizer which give up when encountering any write (EarlyCSE for one), that would be problematic for optimization effectiveness. The other approach would be to teach LLVM about non-memory side effects. I think this is solvable, but a large investment. In practice, most of the contributors to LLVM care about C++. I worry we’d end up in a situation where languages which need infinite loops would become second class citizens and that a large number of optimizations wouldn’t apply to them in practice. This is by far my biggest worry. Now, I’m certainly biased, but I’d much rather see a scheme where a quality of implementation issue effects the performance of C++. These are far more likely to be actually fixed. :slight_smile: Earlier in this thread, the idea of using metadata on loops was mentioned. Chandler’s point about generic handling for recursive loops is a good one, but in general, a metadata annotation of finiteness seems like a better starting point. What if we introduced a piece of branch (really, control transfer instruction) metadata (not loop) called “productive” (to steal Sanjoy’s term) whose semantics are such that it can be assumed to only execute a finite number of times between productive actions (volatile, synchronization, io, etc…). We then tag all branches emitted by Clang with this metadata. This gives us the benefit of the loop metadata in that a single tagged backedge branch implies a productive loop, but allows productive recursive functions to be converted into productive loops in a natural way. The function attribute “productive” now has an easy inference rule in that if all branches in the function are productive and all callees are productive, so is the function. This would seem to allow us to perform DSE, LICM, and related optimizations without trouble. Inlining now has a reasonable definition where you can inline between languages w/the semantics of each language preserved. One cool thing here is that the set of operations which are “productive” could actually be encoded in the metadata. This could potentially support other languages than C++ w.r.t. the “no infinite loops except when” type rules. Thoughts? Philip p.s. The current implementation of readonly is correct w.r.t. C++ rules only because we designate all atomic, volatile, or fencing operations as read/write. One thing we might end up with out of this discussion is the possibility of talking about functions which are readonly, but involved in synchronization. That seems like it might be useful for optimizing concurrent C++ programs in interesting ways. It would require a separate notion of a synchronization side effect independent of read/write though. This seems related, but slightly orthogonal to the assumptions about finiteness of loops.

"productive" (to steal Sanjoy's term)

Just to make it clear: this isn't something I came up with. It is
used (perhaps not extensively) in describing co-inductive data
structures. Insofar I understand the concept, it roughly means that
to get to a finite number of "things" (external actions, in our case)
you only have to execute a finite number of steps.

What if we introduced a piece of branch (really, control transfer
instruction) metadata (not loop) called "productive" (to steal Sanjoy's
term) whose semantics are such that it can be assumed to only execute a
finite number of times between productive actions (volatile,
synchronization, io, etc..). We then tag *all* branches emitted by Clang
with this metadata. This gives us the benefit of the loop metadata in that a
single tagged backedge branch implies a productive loop, but allows
productive recursive functions to be converted into productive loops in a
natural way.

I think this is a good idea. However, I'll suggest one modification:
our specification of a "productive" control transfer should be that
only a finite number of *productive control transfers* can run between
productive actions (volatile write, IO etc.). This is subtly
different from stating that any one productive control transfer
executes only a finite number of times between productive actions.

While discussing offline we decided that these were equivalent (and
theoretically they are), but this second definition lets simple local
CFG manipulation be more aggressive. For instance, say you wish to
split an edge or a basic block. With your definition, marking the
newly inserted branches as productive would involve proving that the
new branch is not part of an existing (well defined) infinite loop,
since inserting a productive branch in an otherwise well-defined
infinite loop will introduce UB. However, if we go with this second
definition, we can (aggressively) mark the newly inserted branches as
productive, as long as they themselves do not introduce a cycle.

Another way of phrasing my suggestion is that any infinite "loop" that
does not do (IO / volatile memory access / atomic operations) has to
have at least one non-productive control transfer. A "loop" in this
definition has to be general enough to encompass all possible control
flow transfer mechanisms (so mutual recursion will have to count as
"loop"ing, for whatever definition we come up for a loop).

The only thing that bugs me about this notion of "productivity" (both
your idea and mine) is that, going by the Java spec, it isn't that a
thread stalled in an infinite loop is not performing any actions; but
the stalling is itself an "external" action (similar to writing to a
socket or program termination). It would be nice if it were possible
to precisely capture that.

-- Sanjoy

From: "Philip Reames" <listmail@philipreames.com>
To: "Chandler Carruth" <chandlerc@google.com>, "Hal Finkel"
<hfinkel@anl.gov>
Cc: "LLVM Dev" <llvmdev@cs.uiuc.edu>
Sent: Friday, July 17, 2015 7:06:33 PM
Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops

>

> > > From: "Chandler Carruth" < chandlerc@google.com >
>

> > > To: "Hal Finkel" < hfinkel@anl.gov >
>

> > > Cc: "LLVM Dev" < llvmdev@cs.uiuc.edu >
>

> > > Sent: Thursday, July 16, 2015 2:33:21 AM
>

> > > Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops
>

> > >
>

> > >
>

> > >
>

> > >
>

>

> > >
>

> > >
>

>

> > > > From: "Chandler Carruth" < chandlerc@google.com >
>

> > > > To: "Hal Finkel" < hfinkel@anl.gov >, "LLVM Dev" <
>

> > > > llvmdev@cs.uiuc.edu >
>

> > > > Sent: Thursday, July 16, 2015 1:00:05 AM
>

> > > > Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops
>

> > > >
>

> > > >
>

> > > > FWIW, I'm very much in favor of having a firm and clear
> > > > answer
> > > > to
>

> > > > these questions.
>

> > > >
>

> > > > I also agree that it is an absolute requirement that LLVM
> > > > have
>

> > > > *some*
>

> > > > mechanism for supporting both languages with defined behavior
> > > > for
>

> > > > infinite loops and a language requirement that all loops
> > > > terminate.
>

> > > >
>

> > > >
>

> > > > However, I'd like to float an alternative approach. I've not
> > > > spent
>

> > > > a
>

> > > > lot of time thinking about it, so I'm not sure its actually
> > > > better.
>

> > > > I'm wondering if you've already thought about it.
>

> > > >
>

> > > >
>

> > > > What if we have an @llvm.noop.sideeffect() or some such which
>

> > > > doesn't
>

> > > > read or write memory in any way, but which a frontend can
> > > > place
>

> > > > inside a loop body to mark that its execution (perhaps
> > > > infinitely)
>

> > > > is in-and-of-itself a side effect of the program. We could
> > > > then
>

> > > > teach loop unrolling or the few other things that would care
> > > > to
>

> > > > collapse multiple ones into a single one, and not count them
>

> > > > towards
>

> > > > anything.
>

> > > >
>

> > > >
>

> > > > I know an intrinsic is kind of awkward for this, but it seems
> > > > like
>

> > > > the least bad way we have to annotate a loop in a fully
> > > > generic
>

> > > > way.
>

> > > > I'd somewhat like this to be a property of the *loop* and not
> > > > of
>

> > > > the
>

> > > > function. And it really needs to be truly generic, handling
>

> > > > unnatural CFGs and even recursion-loops. My only idea for how
> > > > to
>

> > > > accomplish that is an intrinsic to mark the dynamic path
> > > > which
> > > > if
>

> > > > executed infinitely can't be eliminated.
>

> > >
>

> > > My largest concern is that the frontend would need to add these
>

> > > things all over the place, not just before the loop backedges.
> > > For
>

> > > one thing, if the language has gotos, where should they be
> > > inserted?
>

> > >
>

> > >
>

> > > The target of every goto.
>

> > >
>

> > >
>

> > > For computed goto, very label whose address is taken.
>

> > >
>

> > >
>

> > > This at least doesn't seem that bad to me.
>

> > >
>

> > >
>

> > > Before every branch will be conservatively correct, but I'm
> > > worried
>

> > > that will unnecessarily block optimizations. They'd also be
> > > needed
>

> > > at the entry to every function.
>

> > >
>

> > >
>

> > > Only external, address taken, or
> > > internal-and-recursively-called
>

> > > functions. All of which we already have some blockers to
>

> > > optimization, so this part i'm not worried about.
>

> > >
>

> > >
>

> > > On the other hand, maybe if we added an optimization that
> > > removed
>

> > > these things along any control-flow path that already had any
> > > other
>

> > > side effect, it might not be too bad?
>

> > >
>

> > >
>

> > >
>

> > > Absolutely, much like lower-expect, we'd need to make sure that
> > > easy
>

> > > cases were folded quickly in the optimizer so this didn't get
> > > out
> > > of
>

> > > hand.
>

> > >
>

> > >
>

> > >
>

> > > >
>

> > > >
>

> > > > As for why I'm particularly interested in this being a
> > > > property
> > > > of
>

> > > > the loop, consider if you were to have a mixture of Java and
> > > > C++
>

> > > > code, all compiled to LLVM. How do you inline between them?
>

> > > >
>

> > >
>

> > > You add the attribute to the caller.
>

> > >
>

> > >
>

> > > This has the really unfortunate side effect of pessimizing code
>

> > > during cross language optimizations.
>

> > >
>

> > >
>

> > > FWIW, I suspect I might care a lot about this particular case
>

> > > (because I believe that Fortran has defined behavior for
> > > infinite
>

> > > loops).
>

> > >
>

> > >
>

> > >
>

> > > Yea, you could argue that C does too, which is one reason why
> > > I'm
> > > so
>

> > > interested in this being done really well even in an LTO
> > > situation.
>

> > >
>

> > >
>

> > > I think it would be really useful to not have this cross
> > > between
>

> > > adjacent loops after inlining when they come from different
> > > source
>

> > > languages, and it would be nice for it to not apply to nested
> > > loops
>

> > > when those nested loops were inlined from a language without
> > > this
>

> > > guarantee.
>

> > >
>

> > >
>

> > > But I'm still not convinced that the noise of the intrinsic is
>

> > > *definitely* worth it. I come from the background of the C++
> > > rules'
>

> > > rationale, and so I naturally see the languages that define
> > > this
> > > as
>

> > > giving up optimizations and so wanting to localize the impact
> > > of
>

> > > that... Not sure that's actually the right perspective though.
> > > ;]
>

> > >
>

> > I'm leaning toward agreeing with you, primarily because I think
> > it
> > will more-naturally fit into the optimizer than the attribute. We
> > need to check loops for side effects anyway (if we otherwise
> > default
> > to C++-like rules), and so this intrinsic will do the right thing
> > without any special logic.
>

> FWIW, this is why I first started thinking along these lines. I'm
> increasingly thinking that if this approach works it will make the
> implementation of testing for this more natural in the optimizer.
> Simple things like instruction predicates will "just work", etc.

> I'm really interested in the downsides. You mentioned a few
> potential
> ones, but seem to be happy with my responses. I wonder, are there
> others?

I'm really not a fan of this approach. I think it could be made to
work, but I suspect we'd run into a lot of quality of implementation
issues if we went down this route.

We'd have to teach many places in the optimizer to merge or split
such calls. Consider simple things like tail commoning, if-then-else
hoisting, or the like. In each of these, we'd need code to recognize
having the intrinsic on one path, but not the other, and then still
perform the optimization. Think the various debug intrinsics, but
worse.

I worry about the interactions with memory aliasing and hoisting
rules. We don't currently have the notion of a non-memory side
effect in LLVM. To prevent this intrinsic from being DCE'd we'd
likely need to mark it as writing to some known location.

We'd do the same thing we did with @llvm.assume, for which we have all of the same problems (including those mentioned above, only worse). For @llvm.assume we tag it as writing to an unknown location, but taught BasicAA that is does not alias with any particular location.

Given the number of places in the optimizer which give up when
encountering any write (EarlyCSE for one), that would be problematic
for optimization effectiveness. The other approach would be to teach
LLVM about non-memory side effects. I think this is solvable, but a
large investment.

EarlyCSE has specific code to deal with @llvm.assume as well (four lines of code, but code nevertheless).

In practice, most of the contributors to LLVM care about C++. I worry
we'd end up in a situation where languages which need infinite loops
would become second class citizens and that a large number of
optimizations wouldn't apply to them in practice. This is by far my
biggest worry.

Now, I'm certainly biased, but I'd much rather see a scheme where a
quality of implementation issue effects the performance of C++.
These are far more likely to be actually fixed. :slight_smile:

Earlier in this thread, the idea of using metadata on loops was
mentioned. Chandler's point about generic handling for recursive
loops is a good one, but in general, a metadata annotation of
finiteness seems like a better starting point.

What if we introduced a piece of branch (really, control transfer
instruction) metadata (not loop) called "productive" (to steal
Sanjoy's term) whose semantics are such that it can be assumed to
only execute a finite number of times between productive actions
(volatile, synchronization, io, etc..). We then tag *all* branches
emitted by Clang with this metadata. This gives us the benefit of
the loop metadata in that a single tagged backedge branch implies a
productive loop, but allows productive recursive functions to be
converted into productive loops in a natural way.

I don't see how this helps us with the recursive functions case. If I have this:

void foo() {
bar();
foo();
}

where do I put the metadata? Maybe we could also tag the 'ret' as well?

The function attribute "productive" now has an easy inference rule in
that if all branches in the function are productive and all callees
are productive, so is the function. This would seem to allow us to
perform DSE, LICM, and related optimizations without trouble.

Inlining now has a reasonable definition where you can inline between
languages w/the semantics of each language preserved.

One cool thing here is that the set of operations which are
"productive" could actually be encoded in the metadata. This could
potentially support other languages than C++ w.r.t. the "no infinite
loops except when" type rules.

Thoughts?

I was at first afraid of the number of places that create branch instructions, and updating them all to preserve the metadata when appropriate. However:

$ grep -r 'BranchInst::Create\|CreateBr' lib/Transforms | wc -l
99
$ grep -r 'BranchInst::Create\|CreateBr' lib/Transforms -l | wc -l
33

And so there are only 99 places in 33 files that create branches in lib/Transforms (and I find the numerical coincidence amusing). So this seems potentially doable.

Also, if I'm right and we'd need them on 'ret' as well:

$ grep -r 'ReturnInst::Create\|CreateRet' lib/Transforms | wc -l
33
$ grep -r 'ReturnInst::Create\|CreateRet' lib/Transforms -l | wc -l
11

And now I'm even more amused.

Chandler, what do you think?

-Hal

Philip

p.s. The current implementation of readonly is correct w.r.t. C++
rules only because we designate all atomic, volatile, or fencing
operations as read/write. One thing we might end up with out of this
discussion is the possibility of talking about functions which are
readonly, but involved in synchronization. That seems like it might
be useful for optimizing concurrent C++ programs in interesting
ways. It would require a separate notion of a synchronization side
effect independent of read/write though. This seems related, but
slightly orthogonal to the assumptions about finiteness of loops.

I agree; we do need some notion of side effects other than based on memory dependencies. This, however, is a (hopefully) separate project.

Thanks again,
Hal