[LLVMdev] [RFC] Defining Infinite Loops

[Mehdi Amini]

> 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