[LLVMdev] [RFC] Defining Infinite Loops (original) (raw)

Hal Finkel hfinkel at anl.gov
Thu Jul 16 10:57:31 PDT 2015

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

More information about the llvm-dev mailing list