[LLVMdev] [RFC] Defining Infinite Loops

[Chandler Carruth]

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>