[LLVMdev] [RFC] Defining Infinite Loops

[Hal Finkel]

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