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:
http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.9
and:
http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.2
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
--
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory
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 On Wed, Jul 15, 2015 at 9:16 PM Hal Finkel <hfinkel at anl.gov> 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: > > > http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.9 > > and: > > > http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.2 > > 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 > > -- > Hal Finkel > Assistant Computational Scientist > Leadership Computing Facility > Argonne National Laboratory > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150716/9d9aae15/attachment.html>
----- Original Message -----> From: "Chandler Carruth" <chandlerc at google.com> > To: "Hal Finkel" <hfinkel at anl.gov>, "LLVM Dev" <llvmdev at 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> > 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 > > > On Wed, Jul 15, 2015 at 9:16 PM Hal Finkel < hfinkel at anl.gov > 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: > > http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.9 > > and: > > http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.2 > > 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 > > -- > Hal Finkel > Assistant Computational Scientist > Leadership Computing Facility > Argonne National Laboratory > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
On Wed, Jul 15, 2015 at 9:12 PM, Hal Finkel <hfinkel at anl.gov> 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: > > http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.9 > > and: > > http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.2 > > 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
On Wed, Jul 15, 2015 at 11:00 PM, Chandler Carruth <chandlerc at google.com> wrote:> 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
----- Original Message -----> From: "Sanjoy Das" <sanjoy at playingwithpointers.com> > To: "Hal Finkel" <hfinkel at anl.gov> > Cc: "LLVM Dev" <llvmdev at cs.uiuc.edu>, "Nick Lewycky" <nicholas at mxc.ca>, "Philip Reames" <listmail at philipreames.com>, > "David Majnemer" <david.majnemer at gmail.com>, "chandlerc" <chandlerc at gmail.com> > Sent: Thursday, July 16, 2015 3:28:47 AM > Subject: Re: [RFC] Defining Infinite Loops > > On Wed, Jul 15, 2015 at 9:12 PM, Hal Finkel <hfinkel at anl.gov> 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: > > > > http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.9 > > > > and: > > > > http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.2 > > > > 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> > -- Sanjoy >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
> On Jul 15, 2015, at 9:12 PM, Hal Finkel <hfinkel at anl.gov> 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: > > http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.9 > > and: > > http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.2 > > 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) Thanks, — Mehdi> > 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 > > -- > Hal Finkel > Assistant Computational Scientist > Leadership Computing Facility > Argonne National Laboratory > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
----- Original Message -----> From: "Mehdi Amini" <mehdi.amini at apple.com> > To: "Hal Finkel" <hfinkel at anl.gov> > Cc: "LLVM Dev" <llvmdev at cs.uiuc.edu> > Sent: Thursday, July 16, 2015 3:04:44 PM > Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops > > > > On Jul 15, 2015, at 9:12 PM, Hal Finkel <hfinkel at anl.gov> 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: > > > > http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.9 > > > > and: > > > > http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.2 > > > > 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> > Thanks, > > — > Mehdi > > > > > > 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 > > > > -- > > Hal Finkel > > Assistant Computational Scientist > > Leadership Computing Facility > > Argonne National Laboratory > > > > _______________________________________________ > > LLVM Developers mailing list > > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
On Wed, Jul 15, 2015 at 11:00 PM, Chandler Carruth <chandlerc at google.com> wrote:> 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.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:> >> On Jul 15, 2015, at 9:12 PM, Hal Finkel<hfinkel at anl.gov> 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: >> >> http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.9 >> >> and: >> >> http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.2 >> >> 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> > Thanks, > > — > Mehdi > > >> >> 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 >> >> -- >> Hal Finkel >> Assistant Computational Scientist >> Leadership Computing Facility >> Argonne National Laboratory >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
On 7/16/2015 1:00 AM, Chandler Carruth wrote:> > 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?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 -- Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation