llvm dev - Oct 2017 - Infinite loops with no side effects

Personally, I don't like the side effect intrinsic. It will pollute all the
IR generated by non-C frontends. What most of these frontends really want
is just a switch to disable a targeted set of optimizations.

One thing I like about the function attribute idea is that it's
conservatively correct to discard it when doing cross-language inlining. It
just becomes something that C-family frontends need to remember to add to
enable their special-case language rules, rather than something that non-C
languages need to think about. Similar to the 'access', builtin vs
nonbuiltin discussion happening in parallel, the attribute enables the
optimization, rather than inhibiting it.

On Fri, Oct 27, 2017 at 12:37 PM, Hal Finkel via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
> On 10/27/2017 12:08 AM, Dan Gohman via llvm-dev wrote:
>
> Hello,
>
> This email picks up the thread that to my knowledge was last discussed
> here:
>
> http://lists.llvm.org/pipermail/llvm-dev/2015-July/088103.html
>
> In brief, infinite loops containing no side effects produce undefined
> behavior in C++ (and C in some cases), however in other languages, they
> have fully defined behavior. LLVM's optimizer currently assumes that
> infinite loops eventually terminate in a few places, and will sometimes
> delete them in practice. There is currently no clean way to opt out of this
> behavior from languages where it's not valid.
>
> This is the subject of a long-standing LLVM bug:
>
> https://bugs.llvm.org/show_bug.cgi?id=965
>
> I wrote a patch implementing Chandler's idea from the above thread,
> @llvm.sideeffect, a new intrinsic which is a no-op except that it tells the
> optimizer to behave as if there were side effects present:
>
> https://reviews.llvm.org/D38336
>
> Similar results can be achieved with empty inline asms, however they tend
> to pessimize optimizations. The patch above allows all of the major
> optimizations to work in the presence of @llvm.sideeffect.
>
>
> I think that we should move forward with this approach (as may be obvious
> given that I've okay'd the patch). It's a lightweight solution,
at least on
> LLVM's side of things, and does not prevent other solutions later.
>
>
> One of the concerns raised is that front-ends would have to emit a lot of
> these intrinsics, potentially one in every loop, one in every function (due
> to opportunistic tail-call optimization), and one in front of every label
> reachable by goto or similar, if a front-end can't determine when they
> aren't needed.
>
>
> This is a valid concern, however, I expect that most programs from
> higher-level languages will have well-structured loops, and it will be
> straightforward to emit the intrinsics.
>
> This is indeed a downside. It's mitigated in this patch by making sure
> that the major optimization passes aren't pessimized.
>
> From the alternatives I've read, the most promising alternative is
Reid's
> proposal here:
>
> https://bugs.llvm.org/show_bug.cgi?id=965#c25
>
> to make infinite loops defined by default, and add a "known to be
> productive" attribute to functions. It would be a more complex change,
and
> could potentially require changes in out-of-tree codebases. And it would be
> suboptimal in some cases when cross-language inlining. However, it would
> solve the problem in a much less cluttered way. I'm willing to
implement
> the LLVM portion of this if there's consensus that it's a better
approach.
>
>
> The problem is that it is not a function-level property, it is a per-loop
> property. This is even true in C. In C, we would need to mark loops that
> have source-level-constant controlling conditions, and only those loops,
> and allowed to be infinite. And, so, maybe we could use loop-level
> metadata, but that seems hard to place/preserve for unstructured loops
> (and, arguably, that's more important in C/C++ than in other
languages).
>
>  -Hal
>
>
> Thoughts?
>
> Dan
>
>
>
> _______________________________________________
> LLVM Developers mailing listllvm-dev at
lists.llvm.orghttp://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
> --
> Hal Finkel
> Lead, Compiler Technology and Programming Languages
> Leadership Computing Facility
> Argonne National Laboratory
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171027/27042a33/attachment.html>

On 10/27/2017 02:51 PM, Reid Kleckner wrote:
> Personally, I don't like the side effect intrinsic.
Understood. I also don't like the fact that it will clutter the IR in 
many cases.
> It will pollute all the IR generated by non-C frontends. What most of 
> these frontends really want is just a switch to disable a targeted set 
> of optimizations.
>
> One thing I like about the function attribute idea is that it's 
> conservatively correct to discard it when doing cross-language 
> inlining. It just becomes something that C-family frontends need to 
> remember to add to enable their special-case language rules, rather 
> than something that non-C languages need to think about. Similar to 
> the 'access', builtin vs nonbuiltin discussion happening in
parallel,
> the attribute enables the optimization, rather than inhibiting it.
As I said below, a function attribute is insufficient. It needs to be 
something we can mark per loop. This is needed to correctly model C. The 
sideeffect intrinsic is the best proposal I've seen so far.

  -Hal
>
> On Fri, Oct 27, 2017 at 12:37 PM, Hal Finkel via llvm-dev 
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>
>
>     On 10/27/2017 12:08 AM, Dan Gohman via llvm-dev wrote:
>>     Hello,
>>
>>     This email picks up the thread that to my knowledge was last
>>     discussed here:
>>
>>     http://lists.llvm.org/pipermail/llvm-dev/2015-July/088103.html
>>    
<http://lists.llvm.org/pipermail/llvm-dev/2015-July/088103.html>
>>
>>     In brief, infinite loops containing no side effects produce
>>     undefined behavior in C++ (and C in some cases), however in other
>>     languages, they have fully defined behavior. LLVM's optimizer
>>     currently assumes that infinite loops eventually terminate in a
>>     few places, and will sometimes delete them in practice. There is
>>     currently no clean way to opt out of this behavior from languages
>>     where it's not valid.
>>
>>     This is the subject of a long-standing LLVM bug:
>>
>>     https://bugs.llvm.org/show_bug.cgi?id=965
>>     <https://bugs.llvm.org/show_bug.cgi?id=965>
>>
>>     I wrote a patch implementing Chandler's idea from the above
>>     thread, @llvm.sideeffect, a new intrinsic which is a no-op except
>>     that it tells the optimizer to behave as if there were side
>>     effects present:
>>
>>     https://reviews.llvm.org/D38336
<https://reviews.llvm.org/D38336>
>>
>>     Similar results can be achieved with empty inline asms, however
>>     they tend to pessimize optimizations. The patch above allows all
>>     of the major optimizations to work in the presence of
>>     @llvm.sideeffect.
>
>     I think that we should move forward with this approach (as may be
>     obvious given that I've okay'd the patch). It's a
lightweight
>     solution, at least on LLVM's side of things, and does not prevent
>     other solutions later.
>
>>
>>     One of the concerns raised is that front-ends would have to emit
>>     a lot of these intrinsics, potentially one in every loop, one in
>>     every function (due to opportunistic tail-call optimization), and
>>     one in front of every label reachable by goto or similar, if a
>>     front-end can't determine when they aren't needed.
>
>     This is a valid concern, however, I expect that most programs from
>     higher-level languages will have well-structured loops, and it
>     will be straightforward to emit the intrinsics.
>
>>     This is indeed a downside. It's mitigated in this patch by
making
>>     sure that the major optimization passes aren't pessimized.
>>
>>     From the alternatives I've read, the most promising alternative
>>     is Reid's proposal here:
>>
>>     https://bugs.llvm.org/show_bug.cgi?id=965#c25
>>     <https://bugs.llvm.org/show_bug.cgi?id=965#c25>
>>
>>     to make infinite loops defined by default, and add a "known to
be
>>     productive" attribute to functions. It would be a more complex
>>     change, and could potentially require changes in out-of-tree
>>     codebases. And it would be suboptimal in some cases when
>>     cross-language inlining. However, it would solve the problem in a
>>     much less cluttered way. I'm willing to implement the LLVM
>>     portion of this if there's consensus that it's a better
approach.
>
>     The problem is that it is not a function-level property, it is a
>     per-loop property. This is even true in C. In C, we would need to
>     mark loops that have source-level-constant controlling conditions,
>     and only those loops, and allowed to be infinite. And, so, maybe
>     we could use loop-level metadata, but that seems hard to
>     place/preserve for unstructured loops (and, arguably, that's more
>     important in C/C++ than in other languages).
>
>      -Hal
>
>>
>>     Thoughts?
>>
>>     Dan
>>
>>
>>
>>     _______________________________________________
>>     LLVM Developers mailing list
>>     llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>
>>     http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>     <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>
>     -- 
>     Hal Finkel
>     Lead, Compiler Technology and Programming Languages
>     Leadership Computing Facility
>     Argonne National Laboratory
>
>     _______________________________________________ LLVM Developers
>     mailing list llvm-dev at lists.llvm.org
>     <mailto:llvm-dev at lists.llvm.org>
>     http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>     <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev> 
>
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171027/29de204e/attachment.html>

On Fri, Oct 27, 2017 at 1:08 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> On 10/27/2017 02:51 PM, Reid Kleckner wrote:
>
> Personally, I don't like the side effect intrinsic.
>
>
> Understood. I also don't like the fact that it will clutter the IR in
many
> cases.
>
> It will pollute all the IR generated by non-C frontends. What most of
> these frontends really want is just a switch to disable a targeted set of
> optimizations.
>
> One thing I like about the function attribute idea is that it's
> conservatively correct to discard it when doing cross-language inlining. It
> just becomes something that C-family frontends need to remember to add to
> enable their special-case language rules, rather than something that non-C
> languages need to think about. Similar to the 'access', builtin vs
> nonbuiltin discussion happening in parallel, the attribute enables the
> optimization, rather than inhibiting it.
>
>
> As I said below, a function attribute is insufficient. It needs to be
> something we can mark per loop. This is needed to correctly model C. The
> sideeffect intrinsic is the best proposal I've seen so far.
>
Maybe we should do both? If the intrinsic is a special case, that seems
fine. It's cheap.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171027/fb29ab78/attachment.html>