<div dir="ltr">FWIW, I'm very much in favor of having a firm and clear answer to these questions.<div><br>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.</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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?</div><div><br></div><div>Anyways, I've not spent a lot of time thinking about what this might break for languages that allow infinite loops. Maybe it doesn't work as well as I'd hope.</div><div><br></div><div>-Chandler</div></div><br><div class="gmail_quote"><div dir="ltr">On Wed, Jul 15, 2015 at 9:16 PM Hal Finkel <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hello everyone,<br>
<br>
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:<br>
<br>
 1. Some languages, such as Java, have well-defined infinite loops. See:<br>
<br>
      <a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__docs.oracle.com_javase_specs_jls_se7_html_jls-2D17.html-23jls-2D17.4.9&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=brKasFkgQNoVzSFmVHsmHOqa_dm-zI5Xw6lFkKznApM&s=7WA6haULV1ONEVVG219vH_FP_uvbAsE6pIEfiqzWp7I&e=" rel="noreferrer" target="_blank">http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.9</a><br>
<br>
    and:<br>
<br>
      <a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__docs.oracle.com_javase_specs_jls_se7_html_jls-2D17.html-23jls-2D17.4.2&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=brKasFkgQNoVzSFmVHsmHOqa_dm-zI5Xw6lFkKznApM&s=BxSMPTeKeVF2_dMiH3P6ADfxLTi4AmivDtLJrFZNJ9w&e=" rel="noreferrer" target="_blank">http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.2</a><br>
<br>
    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.<br>
<br>
  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:<br>
<br>
     The implementation may assume that any thread will eventually do one of the following:<br>
       - terminate<br>
       - make a call to a library I/O function<br>
       - access or modify a volatile object, or<br>
       - perform a synchronization operation or an atomic operation<br>
<br>
     [Note: This is intended to allow compiler transformations such as removal of empty loops, even<br>
      when termination cannot be proven. — end note ]<br>
<br>
     and taking advantage of these guarantees is part of providing a high-quality optimizer for C/C++ programs.<br>
<br>
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.<br>
<br>
In 2010, Nick proposed to add a 'halting' attribute that could be added to functions to indicate that they would not execute indefinitely (<a href="http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html" rel="noreferrer" target="_blank">http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html</a>). 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.<br>
<br>
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.<br>
<br>
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?<br>
<br>
Thanks again,<br>
Hal<br>
<br>
--<br>
Hal Finkel<br>
Assistant Computational Scientist<br>
Leadership Computing Facility<br>
Argonne National Laboratory<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" rel="noreferrer" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" rel="noreferrer" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</blockquote></div>