[llvm-dev] Infinite loops with no side effects

[Hal Finkel via llvm-dev]

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
>
> 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
> 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/761d6a42/attachment.html>