[LLVMdev] [RFC] Defining Infinite Loops

[Hal Finkel]

----- Original Message -----
> From: "Mehdi Amini" <mehdi.amini at apple.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "LLVM Dev" <llvmdev at cs.uiuc.edu>
> Sent: Thursday, July 16, 2015 3:04:44 PM
> Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops
> 
> 
> > 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)

I have no particular preference. Chandler's follow-up proposal effectively does this.

 -Hal

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

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory