[LLVMdev] [RFC] Defining Infinite Loops

[Hal Finkel]

----- Original Message -----
> From: "Sanjoy Das" <sanjoy at playingwithpointers.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "LLVM Dev" <llvmdev at cs.uiuc.edu>, "Chandler Carruth" <chandlerc at google.com>
> Sent: Thursday, July 16, 2015 3:14:27 PM
> Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops
> 
> On Thu, Jul 16, 2015 at 11:07 AM, Hal Finkel <hfinkel at anl.gov> wrote:
> > ----- Original Message -----
> >> From: "Sanjoy Das" <sanjoy at playingwithpointers.com>
> >> To: "Chandler Carruth" <chandlerc at google.com>
> >> Cc: "Hal Finkel" <hfinkel at anl.gov>, "LLVM Dev"
> >> <llvmdev at cs.uiuc.edu>
> >> Sent: Thursday, July 16, 2015 3:52:09 AM
> >> Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops
> >>
> >> On Wed, Jul 15, 2015 at 11:00 PM, Chandler Carruth
> >> <chandlerc at google.com> wrote:
> >> > 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.
> >>
> >> I read this as: "the optimizer may legally remove only a finite
> >> number
> >> of @llvm.noop.sideeffect calls from the program trace".  It gets
> >> really interesting here since for typical managed language
> >> implementations, application threads have to "poll for safepoints"
> >> (check if there is a pending request to halt from the GC).  As of
> >> now
> >> we insert these polls late (after most of the interesting
> >> target-independent optimizations have run), but if we were to
> >> change
> >> our strategy to insert these polls early and wanted LLVM to
> >> optimize
> >> these, the optimization rules would be similar: "the optimizer may
> >> not
> >> introduce an unbounded wait between two polls (i.e. it is okay to
> >> remove polls for a provably finite loop, but an infinite loop must
> >> keep them)" [1].  So a @llvm.noop.sideeffect-like concept may be
> >> generally useful in LLVM.
> >>
> >> However, I don't think we can get away with just
> >> @llvm.noop.sideeffect
> >> -- a function level attribute is required to know when it is okay
> >> to
> >> DCE calls to readnone/readonly functions.
> >
> > I think you're right, in a sense, but to DCE calls, we need
> > something stronger. Specifically, we need the kind of 'halting'
> > attribute that Nick proposed. Because we need to know that the
> > function really will return normally within some finite time.
> > Thus, having a scheme such as this, or the 'productive' attribute,
> > helps with inferring the 'halting' attribute, but is not a
> > replacement for it.
> 
> I think "productive + readonly" and "productive + readnone" can be
> inferred to be "halting".  In practice, the third case ("productive +
> readwrite") cannot be removed most (all?) of the times anyway.

Yes, but there are other cases, like heap-to-stack conversion, where we need halting information on readwrite calls.

 -Hal

> 
> >
> >>
> >> > 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?
> >>
> >> TBQH, I'd be okay losing some performance in this case.  And we
> >> can
> >> always be aggressive about upgrading non-productive [2] functions
> >> to
> >> productive if they only call productive functions and have no
> >> infinite
> >> loops.
> >
> > The other question is: Does having this intrinsic make it easier to
> > program correct IR transformations. I'm leaning toward yes
> > (because we need to check loops for side effects anyway), and thus
> > I'm slightly in favor of this intrinsic. Thoughts?
> >
> >  -Hal
> >
> >>
> >> [1]: there are quality of implementation issues on how frequently
> >> an
> >> application thread checks for a pending safepoint request
> >>
> >> [2]: using the definition for "productive" == "this function
> >> produces
> >> some
> >> output (volatile load/store, IO, etc.) in a finite amount of time"
> >>
> >> -- Sanjoy
> >>
> >
> > --
> > Hal Finkel
> > Assistant Computational Scientist
> > Leadership Computing Facility
> > Argonne National Laboratory
> 

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