[LLVMdev] [RFC] Defining Infinite Loops

Hal Finkel hfinkel at anl.gov
Thu Jul 16 00:27:49 PDT 2015

----- 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).


> 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

More information about the llvm-dev mailing list