[LLVMdev] [RFC] Defining Infinite Loops

[Chandler Carruth]

On Thu, Jul 16, 2015 at 11:08 AM Hal Finkel <hfinkel at anl.gov> wrote:

> ----- Original Message -----
> > From: "Chandler Carruth" <chandlerc at google.com>
> > To: "Hal Finkel" <hfinkel at anl.gov>
> > Cc: "LLVM Dev" <llvmdev at cs.uiuc.edu>
> > Sent: Thursday, July 16, 2015 2:33:21 AM
> > Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops
> >
> >
> >
> >
> > On Thu, Jul 16, 2015 at 12:27 AM Hal Finkel < hfinkel at anl.gov >
> > wrote:
> >
> >
> > ----- Original Message -----
> > > From: "Chandler Carruth" < chandlerc at google.com >
> > > To: "Hal Finkel" < hfinkel at anl.gov >, "LLVM Dev" <
> > > llvmdev at cs.uiuc.edu >
> > > Sent: Thursday, July 16, 2015 1:00:05 AM
> > > Subject: Re: [LLVMdev] [RFC] Defining Infinite Loops
> > >
> > >
> > > 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.
> >
> > My largest concern is that the frontend would need to add these
> > things all over the place, not just before the loop backedges. For
> > one thing, if the language has gotos, where should they be inserted?
> >
> >
> > The target of every goto.
> >
> >
> > For computed goto, very label whose address is taken.
> >
> >
> > This at least doesn't seem that bad to me.
> >
> >
> > Before every branch will be conservatively correct, but I'm worried
> > that will unnecessarily block optimizations. They'd also be needed
> > at the entry to every function.
> >
> >
> > Only external, address taken, or internal-and-recursively-called
> > functions. All of which we already have some blockers to
> > optimization, so this part i'm not worried about.
> >
> >
> > On the other hand, maybe if we added an optimization that removed
> > these things along any control-flow path that already had any other
> > side effect, it might not be too bad?
> >
> >
> >
> > Absolutely, much like lower-expect, we'd need to make sure that easy
> > cases were folded quickly in the optimizer so this didn't get out of
> > hand.
> >
> >
> >
> > >
> > >
> > > 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?
> > >
> >
> > You add the attribute to the caller.
> >
> >
> > This has the really unfortunate side effect of pessimizing code
> > during cross language optimizations.
> >
> >
> > FWIW, I suspect I might care a lot about this particular case
> > (because I believe that Fortran has defined behavior for infinite
> > loops).
> >
> >
> >
> > Yea, you could argue that C does too, which is one reason why I'm so
> > interested in this being done really well even in an LTO situation.
> >
> >
> > I think it would be really useful to not have this cross between
> > adjacent loops after inlining when they come from different source
> > languages, and it would be nice for it to not apply to nested loops
> > when those nested loops were inlined from a language without this
> > guarantee.
> >
> >
> > But I'm still not convinced that the noise of the intrinsic is
> > *definitely* worth it. I come from the background of the C++ rules'
> > rationale, and so I naturally see the languages that define this as
> > giving up optimizations and so wanting to localize the impact of
> > that... Not sure that's actually the right perspective though. ;]
> >
>
> I'm leaning toward agreeing with you, primarily because I think it will
> more-naturally fit into the optimizer than the attribute. We need to check
> loops for side effects anyway (if we otherwise default to C++-like rules),
> and so this intrinsic will do the right thing without any special logic.
>

FWIW, this is why I first started thinking along these lines. I'm
increasingly thinking that if this approach works it will make the
implementation of testing for this more natural in the optimizer. Simple
things like instruction predicates will "just work", etc.

I'm really interested in the downsides. You mentioned a few potential ones,
but seem to be happy with my responses. I wonder, are there others?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150717/ef2c56c5/attachment.html>