<p>I recently saw <a href="https://x.com/SamZaNemesis/status/1820091835651637408" rel="nofollow noreferrer">this tweet</a>.</p>
<p>And for posterity, this is the C++ code:</p>
<pre><code>inline int square( int n )
{
    int k = 0;
    while ( true )
    {
        if( k == n*n )
            return k;
        
        k++;
    }
};

int main()
{
    return square(10);
}
</code></pre>
<p>This gets compiled to:</p>
<pre><code>main:
    mov eax, 100
    ret
</code></pre>
<p>Somehow, clang is able to evaluate this <code>square</code> function, which includes a <code>while (true)</code>.</p>
<p>This is quite surprising to me, because <code>while (true)</code> should be an immediate red flag that the loop may not terminate.</p>
<p>So it seems to imply that either clang has solved the halting problem, or clang can potentially get caught in an infinite loop and never finish compiling.</p>
<p>So, what's going on under-the-hood?</p>

<compilers><c++><static-analysis><loops><inlining>
How is clang able to evaluate loops without getting stuck in an infinite loop?
CC BY-SA 4.0
2024-08-05T20:06:02.957Z
Leaving this as a comment because I don't have a source, but the compiler may assume there is no infinite loop without side effects, since that would be UB in C. Also, `if (a == b) return a;` and `if (a == b) return b;` are pretty obviously equivalent. The compiler is allowed to assume that loop exits, and that return statement is the only way it can exit, so the compiler optimizes the loop to just the return statement.
Bbrk24
CC BY-SA 4.0
2024-08-05T20:06:33.397Z
The simplest thing it might do is evaluate the loop until some fixed number of iterations, and stop trying to optimise if it takes too many iterations. Another possibility is that it doesn't evaluate the loop at all, instead noticing that the only `return` from the function is of the value `k` guarded by the condition `k == n * n`. So if the function ever returns anything then it must return `n * n`, and AFAIK C++ compilers are allowed to assume termination of side-effect-free loops even if they can't prove it.
kaya3
CC BY-SA 4.0
2024-08-05T21:49:07.000Z
"Solving the halting problem" would entail an algorithm which, for *every* possible loop, can determine with perfect accuracy whether it terminates.  There's nothing impossible about an algorithm that is able to detect whether *certain* loops terminate.  In the case of clang, the vast majority of possible looping code cannot be optimized like this, so the halting problem is intact.
Nate Eldredge
CC BY-SA 4.0
2024-08-05T21:51:44.660Z
I mean, surely *you* can sit down and write a proof that this loop terminates, notwithstanding that it is written as `while(true)`.  You can do so in a bounded amount of time, without having to actually simulate the loop.  And nothing stops a compiler from applying the same logic that you did.  But neither of you have solved the halting problem.
Nate Eldredge
CC BY-SA 4.0
2024-08-05T21:59:30.690Z
@kaya3 and Bbrk24: you're correct that C and C++ disallow infinite loops with no side effects (with certain exceptions not relevant here), thus allowing to compilers to assume a side-effect-free loop always terminates, and that would make it easier for the compiler to optimize this into a constant.  However, with both gcc and clang, you can switch off that rule with the flag `-fno-finite-loops`, and both compilers are still able to make the optimization.  https://godbolt.org/z/YhW794ePe.  So that rule is a red herring here.
Nate Eldredge
CC BY-SA 4.0
2024-08-06T16:02:32.003Z
The question doesn't really make sense as, after compilation, it would be obvious that this isn't an infinite loop. It should even result in the same CFG as when moving the condition to while and the return after the loop.
feldentm
CC BY-SA 4.0
2024-08-06T16:43:09.330Z
You can actually use https://godbolt.org/z/84Pf5zhhv to see how LLVM does it, pass-by-pass. This lets you see exactly what transformation each optimizer pass does from the original unoptimized LLVM IR all the way to a slightly odd representation of the machine instructions.
Simon Farnsworth
CC BY-SA 4.0
2024-08-08T11:37:20.107Z
I wondered what would happen if I made the loop so that it doesn't actually hit the the correct value of `k`. E.g. start with `k=0`, iterate `k+=2` and ask for `square(11)`. Here, gcc compiles it into a busyloop, but, clang returns 120, so n*n-1. Curious. https://godbolt.org/z/6hezrM1KK
ilkkachu
CC BY-SA 4.0
2024-09-21T20:52:42.933Z
@ilkkachu: If the correct value is not hit, then `k` increments until it overflows, and signed integer overflow in C and C++ is undefined behavior.  So the behavior of the code in that case can be anything, and the compiler is not required to actually execute all the steps in between.  (If you used `unsigned`, then the overflow is not UB, but the infinite loop with no side effects is still UB as mentioned above, so either behavior is still okay.)
Nate Eldredge
<p>There is a lot of talk about inductive types and inlining here, but the optimisations in the code can be achieved through far simpler methods.</p>
<p>Let's look at the function</p>
<pre class="lang-c prettyprint-override"><code>inline int square( int n )
{
    int k = 0;
    while ( true )
    {
        if( k == n*n )
            return k;
        
        k++;
    }
};
</code></pre>
<p>There is only one way it can ever return - if <code>k == n*n</code>. If that is true, it will return <code>k</code>, so the compiler can transform the code to instead return <code>n*n</code> - this is a simpler expression, as it is constant during the loop (unlike <code>k</code>)</p>
<pre class="lang-c prettyprint-override"><code>inline int square( int n )
{
    int k = 0;
    while ( true )
    {
        if( k == n*n )
            return n*n; //  &lt;-- !!
        
        k++;
    }
};
</code></pre>
<p>Now the compiler is in a different scenario. It knows the value it will return, but not <em>if</em> it will return. Thankfully, it can assume that! When there is a &quot;simple&quot;* loop, it is undefined behaviour for it to run forever. Now the compiler has two key facts:</p>
<ul>
<li>The loop returns <code>n*n</code>, which is constant from the start of the function as <code>n</code> is never changed</li>
<li>The loop must return**</li>
</ul>
<p>Therefore, it can trivially change the function into</p>
<pre class="lang-c prettyprint-override"><code>inline int square( int n )
{
    return n*n;
}
</code></pre>
<p>Now, if infinite loops were not considered undefined, it would have to prove the loop always terminates. It can do that pretty simply using the inductive logic discussed before:</p>
<ul>
<li><code>n*n</code> must always be positive and will be in the range of an <code>int</code></li>
<li><code>k</code> starts at zero and increases through the entire positive range of an int</li>
<li>Therefore, k <em>must</em> equal <code>n*n</code> at some point</li>
<li>With this slightly more complex logic, it can make the same transformation as before</li>
</ul>
<p>The final step of getting the assembly is that it ends up inlining this function and using the constant value provided, but that is less important :)</p>
<p>* &quot;simple&quot; means not doing anything visible to the outside world, such as IO or volatile access.</p>
<p>** In the name of clarity, C compilers will normally not optimise loops in this manner as it is confusing if an infinite loop simply vanishes. Its real logic is likely closer to the second loop optimisation, but it is still perfectly legal for it to do it the first way</p>

CC BY-SA 4.0
2024-08-06T15:21:21.943Z
2024-08-07T08:00:17.520Z
2024-08-07T08:00:17.520Z
John
CC BY-SA 4.0
2024-08-06T22:28:36.457Z
The "undefined behaviour" argument is wrong. Notice that by this logic, the compiler would optimise the code in exactly the same way even if the `k++` line wasn't there, which it obviously doesn't do.
leftaroundabout
CC BY-SA 4.0
2024-08-06T23:52:42.950Z
@leftaroundabout: I believe some compilers do try to recognize cases where there's no loop variable or the loop variable is constant, and as a courtesy to the programmer, may decide not to optimize such loops. But it is still UB to write such a loop unless it terminates, and the compiler would be within its rights to apply the optimization regardless.
Kevin
CC BY-SA 4.0
2024-08-07T07:58:50.977Z
@leftaroundabout it was meant to be "these are the rules the compiler may follow to optimise it", but that may not have been clear. i have added clarification
John
CC BY-SA 4.0
2024-08-07T17:59:25.507Z
How often is the described optimization useful, compared with what would be possible if a compiler were allowed to omit the loop in cases *where the returned value is ignored*, but not in cases where downstream code makes use of a computation performed within the loop?
supercat
CC BY-SA 4.0
2024-08-07T18:10:33.380Z
In almost any other situation where permission to assume X is given, that does not imply permission to assume things that would need to be true in order for X to be true, but rather permission to proceed in a manner which is *agnostic* to whether X is true or not.  In a physics problem, permission to assume that acceleration due to gravity is exactly 9.800 m/s/s does not imply permission to assume that an object isn't located in a place where local acceleration due to gravity is slightly different, but merely to ignore any deviation between actual acceleration and the value given.
supercat
CC BY-SA 4.0
2024-08-08T14:05:35.257Z
@leftaroundabout Actually if you remove `k++` then the compiler goes even further: it knows the only argument which does not cause an infinite loop is `n == 0`. Since it follows that the only argument to `square` that does not cause UB is zero, it goes ahead an and optimizes `square` to simply zero a register and returns. Both GCC and Clang will perform this optimization. https://godbolt.org/z/KhMehrn3x
Jack Lloyd
CC BY-SA 4.0
2024-08-09T13:55:12.193Z
@JackLloyd well, that is certainly curious. On my machine, it always compiles to an unconditional infinite loop, but apparently I was wrong to think that this is what compilers generally will do in practice.
leftaroundabout
<p>This isn't an answer to the question, since it's not about Clang, but we also implemented <a href="https://mercurylang.org/information/doc-release/mercury_ref/Termination-analysis.html" rel="nofollow noreferrer">termination analysis in the Mercury compiler</a>, and also supported a pragma which asserted that a procedure always terminates.</p>
<p>On top of compile-time evaluation, it's useful for goal reordering. In a purely declarative language, this transformation is almost always correct:</p>
<pre><code>p(), q() -&gt; q(), p()
</code></pre>
<p>(i.e. &quot;call <code>p</code> then call <code>q</code>&quot; can be reordered). The only time it isn't correct is if the call to <code>q</code> can infinitely loop.</p>
<p>There are other cases to consider, of course; perhaps <code>p</code> and <code>q</code> can both raise exceptions, say. But if you're designing the language, you can simply rule that raising either exception is valid semantics in this situation.</p>

CC BY-SA 4.0
2024-08-06T04:46:45.300Z
2024-08-06T04:46:45.300Z
Pseudonym
<p>There are two ways a language specification may allow a compiler to avoid having to solve the halting problem to make what should otherwise be simple and useful optimizations:</p>
<ol>
<li><p>The language specification may allow actions to be deferred until their side effects would be observable, and deferred forever (effectively skipped entirely) if their side effects will never be observed, and specify that branches within a section of code has a single exit which is statically reachable from all code within the section need not be regarded as side effects in and of themselves.</p>
</li>
<li><p>The language specification may specify that implementations may behave in arbitrary fashion if a program receives inputs that would cause it to get stuck in a side-effect-free endless loop.</p>
</li>
</ol>
<p>The former approach will allow most of the useful optimizations that would be facilitated by the latter, but allow humans or automatic code validators to reason about program invariants.  The latter approach would make it impossible to prove any invariants without proving that a program will terminate for all possible inputs, but would allow compilers to avoid tough decisions about whether to omit a loop or exploit post-conditions which would be established if the loop were existed, by letting compilers apply both optimizations simultaneously.</p>
<p>IMHO, the second approach is counter-productive for most kinds of tasks, since the only situation in which a compiler could ever improve the performance of correct code would be if either:</p>
<ol>
<li><p>The programmer could prove that the program would terminate for all possible inputs, but a compiler couldn't.</p>
</li>
<li><p>There would be no requirement that a program uphold memory safety or any other invariants for inputs that might cause a program to get stuck in and endless loop.</p>
</li>
</ol>
<p>If a program contained any otherwise-side-effect loops that might fail to terminate, the only way to ensure that any invariants would be upheld would be to add dummy side effects to the loop or add artificial exit conditions, either of which would mean either that a compiler wouldn't be allowed to omit the loop even if it happened to be useless, or that a compiler's entitlement to omit the loop would not depend upon whether endless loops had defined behavior.</p>
<p>As a consequence, while optimizations allowed under the first semantic approach could be usefully employed in correct programs, those allowed under the broader semantics are primarily effective when processing erroneous programs.</p>

CC BY-SA 4.0
2024-08-06T20:09:32.320Z
2024-08-06T20:09:32.320Z
supercat
<p>An optimising compiler could use different strategies.</p>
<p>A straightforward strategy: If you want the compiler to halt in all cases, translate the loop but make sure it halts (for example after one billion iterations or after one second of compiler time). If it halts, the inline call just produces a constant. If it doesn't halt fast enough, call the non-inlined function. This works in all situations.</p>
<p>If you don't require the compiler to halt: I'd have to pull out the &quot;Standard lawyer's handbook&quot;. An infinite loop is undefined behaviour (I think). I'm not sure if undefined behaviour allows bad behaviour in the compiler as well. However, this approach is very unsatisfactory if I write an inline function that will halt after 1,000 years of compile time.</p>
<p>In this specific case, the function will either return k, or it will not return. Again the &quot;Standard lawyer's handbook&quot; will tell us whether returning k unconditionally is legal. However, n*n invokes undefined behaviour for not-very-large n, so we know the function returns k or invokes undefined behaviour, and always returning k is legal.</p>
<p>And in many situations, the compiler can have built-in strategies. For example, even not-very-optimising compilers can easily calculate sums of polynomials with integer coefficients.</p>

CC BY-SA 4.0
2024-08-08T18:22:55.470Z
2024-08-08T18:22:55.470Z
gnasher729
<p>Because this is an optimization Clang does, you can use <a href="https://godbolt.org/z/ahjY3fKvn" rel="noreferrer">godbolt.org</a> to explore it optimization pass by optimization pass. I've turned on the &quot;Optimization Pipeline Viewer&quot;, set the &quot;Options&quot; to include &quot;Dump Full Module&quot;, and changed the &quot;Filters&quot; to &quot;Hide Inconsequential Passes&quot; (so it hides all passes that don't change the IR under consideration). I'm not going to describe all the passes involved to get to the result in question, just the ones that make significant changes to the code.</p>
<p>The first interesting pass is &quot;LICMPass on while.cond&quot;; this detects that <code>n * n</code> is the same on every iteration of the loop, and moves the calculation to before the loop. This makes the LLVM IR analogous to (noting that semantics don't map cleanly because C doesn't have phi nodes):</p>
<pre><code>inline int square( int n )
{
    int k = 0;
    int mul = n * n;
    while ( true )
    {
        if( k == mul )
            return k;
        
        k++;
    }
};
</code></pre>
<p>The next interesting pass is &quot;LoopRotatePass on while.cond&quot;. This rearranges the loop further, to look a little like:</p>
<pre><code>inline int square( int n )
{
    int k = 0;
    int mul = n * n;
    while ( k != mul )
    {
        k++;
    }
    return k;
};
</code></pre>
<p>since it's determined that the only way to escape the loop is for <code>k == mul</code> to be true, and then it immediately returns <code>k</code>. This is the pass that has determined that the loop is not infinite, and it's done so just based on the loop body.</p>
<p>Then, after some more minor passes to prepare the LLVM IR for this optimization to fire, &quot;IndVarSimplifyPass on while.cond&quot; removes the loop, because it can see that <code>k</code> is an induction variable, and changes the code to look like:</p>
<pre><code>inline int square( int n )
{
    while ( false )
    {
    }
    int mul = n * n;
    return mul;
};
</code></pre>
<p>From here, some more passes clean up <code>square</code> to be <code>inline int square( int n ) { return n * n; }</code>; then &quot;InlinerPass on (main)&quot; replaces the call to <code>square</code> in <code>main</code> with <code>(10 * 10)</code> and does constant folding to turn this into a constant <code>100</code>. The remaining significant passes simply convert from LLVM IR to LLVM's internal representation of x86-64 machine code, ready to be output.</p>

CC BY-SA 4.0
2024-08-07T10:05:01.487Z
2024-08-08T08:56:41.327Z
2024-08-08T08:56:41.327Z
Simon Farnsworth
CC BY-SA 4.0
2024-08-07T11:32:41.607Z
Everyone's answers were great, but this one answered my question most closely by stepping through the LLVM optimization passes (I specifically asked for what's going on under-the-hood of clang.)
JBraha
CC BY-SA 4.0
2024-08-09T02:31:30.140Z
I think the second re-arrangement is the critical step... it's the one that illustrates that despite the syntax used, this _isn't_ a `while (true)` loop... it just has the break condition inside the body instead.
Simon Geard
<p>Clang neither solves the halting problem, nor it is <em>evaluating</em> the loop, potentially forever. It is only <em>optimizing</em> the loop once, as part of the compilation process.</p>
<h4>Let's compile the code as an <em>optimizing</em> compiler would</h4>
<p>There are various optimizations intermingled here, so try to make this very simple.</p>
<p>First, <code>square(int n)</code> is called with <code>n = 10</code>. This is important because <code>10</code> is a constant, so the compiler can now create a copy of this function for this specific invocation. This is called <a href="https://llvm.org/devmtg/2021-11/slides/2021-IntroducingFunctionSpecialisationAndCanWeEnableItByDefault.pdf#zoom=150" rel="nofollow noreferrer">function specialization</a>, and is also encouraged by <code>inline</code>. The specialized function is now:</p>
<pre><code>inline int square_10()    // Const parameter removed
{
    int k = 0;
    while ( true )
    {
        if( k == 10*10 )  // Const value replaced
            return k;
        k++;
    }
};
</code></pre>
<p>Here, <code>10*10</code> is trivially optimized to <code>100</code>. There is not much code left (this will be important later).</p>
<p>There is a local variable <code>k</code> initialized to 0, and there is the <code>while(true)</code> loop, with only two statements. One is the <code>if</code>, the other is the local increment of <code>k</code>. From the latter, the compiler can extrapole the range of <code>k</code> as all positive numbers (until it reaches undefined behavior).</p>
<p>The internal compiled code is now approximately represented in memory as:</p>
<pre><code>inline int square_10()
{
    // k = $ALL_POSITIVE_INT (compiler internal state)
    while ( true )
        if( k == 100 )
            return k;
};
</code></pre>
<p>This can also be trivially optimized in two steps. First the <code>if</code> will be eventually true because <code>100</code> is in the range of <code>k</code>, so the <code>return</code> can be reached. And when the <code>return</code> is reached, <code>k</code> is restricted to <code>100</code>.</p>
<p><em>There is no other instructions that change the result,</em> so the only possible effect of this code is optimized to:</p>
<pre><code>inline int square_10()
{
    return 100;
}
</code></pre>
<p>There are no calls for <code>square(int n)</code>, so the &quot;normal&quot; function is never generated. The code is now reduced to an inline function that returns a constant. This is inlined to:</p>
<pre><code>int main()
{
    return 100;
}
</code></pre>
<p>Well, this is fine and dandy, but let's test some assumptions from above.</p>
<h4>Constant argument and multiplication elimination</h4>
<p>You can <a href="https://godbolt.org/z/5Goohs99q" rel="nofollow noreferrer">try replacing</a> <code>10</code> by <code>getchar()</code> from the original example, and you will see the compiler will not optimize the code to a constant anymore.</p>
<p>It will eliminate the loop, but keep the <code>mul</code>, as now the function result literally depends on the function argument: the return is only constant for a constant parameter.</p>
<h4>Range inspection and loop elimination</h4>
<p>You can further <a href="https://godbolt.org/z/5Goohs99q" rel="nofollow noreferrer">further replace</a> <code>k++</code> by <code>k = getchar()</code>, and you will see the compiler will not eliminate the loop (as observed with the jumping around, <code>je</code> and <code>jne</code>).</p>
<p>It also will keep the <code>imul</code> around, as the compiler cannot assume any value of <code>k</code> beyond the initial zero.</p>
<h4>An optimizing compiler only cares for code that cause effects</h4>
<p>Inserting an <code>putchar(0);</code> anywhere inside the <code>while</code> would disable the loop elimination. An <code>putchar(0);</code> before the <code>while</code> generates some additional assembly, and a <code>putchar(0);</code> after the <code>while</code> causes nothing, because it is detected as dead code from the same optimizations above.</p>
<h4>TL:DR;</h4>
<p>A mix of function specialization, constant propagation, constant folding, range inspection, code invariant analysis and dead code elimination can generate these results. There is no evaluation involved.</p>

CC BY-SA 4.0
2024-08-05T20:40:16.107Z
2024-08-07T12:55:28.900Z
2024-08-07T12:55:28.900Z
André L F S Bacci
CC BY-SA 4.0
2024-08-05T22:04:16.310Z
In your `getchar()` example, the compiler still *does* do the optimization that's of interest here, namely replacing the loop with a single multiply instruction.
Nate Eldredge
CC BY-SA 4.0
2024-08-05T22:40:18.137Z
'int k = 0 .. INT_MAX'  'the if is always true because of the range of k, so the return is always reached.'  this is complete and utter nonsense
Moonchild
CC BY-SA 4.0
2024-08-06T09:39:01.580Z
Since infinite loops are UB and there is only a single exit in the loop, the compiler can just assume this exit is reachable and infer the condition to be true.
Falco
CC BY-SA 4.0
2024-08-06T14:22:12.343Z
@Falco not sure how so many answers get it wrong. There is no need to assume anything about infinite loops (in fact, they are not UB in C and the same optimization applies). It's just simple - compiler can assume that `k` always reaches 100 at some point, because it monotonically increases (and integer overflow is UB, but even if `k` was unsigned same deduction could be made due to wraparound).
Dan M.
CC BY-SA 4.0
2024-08-06T19:13:43.810Z
@DanM. some infinite loops are 'ub' in c (howbeit not this one); refer to sec. 6.8.5p6 of [the standard](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf)
Moonchild
CC BY-SA 4.0
2024-08-07T13:55:41.730Z
@Moonchild that's what I'm saying. Many answers go on and on about UB infinite loops, but it has zero relevance for THIS particular example. Also, you are using outdated draft, this loop is not UB even in C++: https://eel.is/c++draft/intro.progress#1
Dan M.
CC BY-SA 4.0
2024-08-07T17:41:50.757Z
The Standard specifies that there are three ways an action may be characterized as UB. 
 It the authors intended that endless loops be "anything can happen" UB, they could have said that side-effect-free loops *shall* terminate.  The use of more verbose and "non-standard" phraseology would seem odd unless they intended to allow some otherwise unsound optimizations of the form hinted at by the footnote without treating the loops as "anything can happen" UB.
supercat
CC BY-SA 4.0
2024-08-07T17:52:17.147Z
@Moonchild: [see comment above]: Treating endless loops as "anything can happen" UB will be counter-productive in cases where code would be required to uphold memory safety invariants for all inputs. Absent such treatment, one could prove that a program would uphold memory safety invariants by proving that no individual action could violate them unless they had already been violated, without having to prove that no inputs could cause a program to get stuck in an endless loop.  Requiring that programmers add otherwise-unnecessary code to loops to uphold memory safety...
supercat
CC BY-SA 4.0
2024-08-07T17:55:50.807Z
...will not only negate any possible optimizations that could only be facilitated by treating endless loops as UB, but also optimizations that could have been facilitated by allowing implementations to *cleanly* omit loops which have no side effects upon which downstream code visibly relies, *nor which the compiler's generated downstream machine code exploits*.
supercat
<p>There are basically two reasons for this: <b>the halting problem is semidecidable</b> (i.e., we can solve it, sometimes), and <b>the C++ standard allows LLVM to cheat</b> and pretend it solved the halting problem even though it didn't</p>
<h1>How to solve the halting problem</h1>
<p>(Note: this section is somewhat handwavy; I might make it more rigorous later, but I think it gives a good intuition as is.)</p>
<p>The halting problem says that we can never make a procedure that takes another procedure and says either 'yes, this halts' or 'no, it doesn't'.  But we don't actually need something like that.  What we want, rather, is a procedure that takes another procedure and says 'yes, this halts' or 'no, it doesn't' <em>or</em> 'this is too complicated; I don't know'.  This is trivially possible (you could just always say 'don't know'), but we would like to have some strategies for giving more useful results.  Follows is one particular strategy that works well:</p>
<p>If we can identify an instance of an inductive data type whose value decreases on every loop iteration, then we can be assured that the loop terminates.  Why?  Because eventually, the inductive data type will 'bottom out'.  At that point, there is no way to decrease it any further.  But in order to proceed to the next loop iteration, we would <em>have</em> to decrease it.  Which means that we must not proceed to the next loop iteration; either at that point or before that point, we must have terminated the loop.</p>
<p>Where's the decreasing quantity here?  First swap out 'int' for 'unsigned'; integers can be defined inductively, but the order gets messed up which makes things more confusing, and there are no negative numbers here anyway.  Naturals are easier to work with and numerical order does what we want.  Now the quantity that decreases on each iteration is n*n - k.  On any given iteration, either this is zero or it is nonzero.  If n*n - k == 0, then n*n == k, and so the loop terminates.  Otherwise, we proceed to the next loop iteration with k increased by 1, and therefore n*n - k decreased by 1.</p>
<p>It's worth re-emphasising the role that the inductive type plays here.  In an immutable language, a linked list is inductive, and therefore iterating over a linked list always terminates.  On the other hand, in a language like C, which is mutable, iterating over a linked list does not necessarily terminate, because the list could have cycles in it.</p>
<h1>How to con standardisers into solving the halting problem for you</h1>
<p>Refer to section intro.progress in <a href="https://www.open-std.org/JTC1/SC22/WG21/docs/papers/2020/n4849.pdf" rel="nofollow noreferrer">the c++ standard</a>.  This effectively says that compilers can simply assume that loops like the one you showed always terminate, and if you write a loop that <em>doesn't</em> terminate, it's your own fault.</p>

CC BY-SA 4.0
2024-08-05T22:33:11.003Z
2024-09-09T12:55:57.083Z
2024-09-09T12:55:57.083Z
Moonchild
CC BY-SA 4.0
2024-08-06T11:27:04.463Z
"in an immutable language, a linked list is inductive, and therefore iterating over a linked list always terminates." - This doesn't necessarily follow - Haskell is an immutable language, and yet iterating over a list doesn't always terminate.
psmears
CC BY-SA 4.0
2024-08-06T17:17:48.737Z
Also, although this isn't how clang does it, another way to partially solve the halting problem is to run the loop for, say, an hour. If it halts, you have your result. If it doesn't halt, or if it does anything with side effects, say you don't know (and in this case, inline the code instead of the result). There's nothing in the standard that says compilers have to be fast.
Steve Jessop
CC BY-SA 4.0
2024-08-06T17:26:14.170Z
By "run the loop" I don't mean compile the unoptimised code to the target architecture and run it there. The compiler could in principle execute the code in some sort of sandbox, perhaps similar to the way that it evaluates static constant expressions, and/or the way it computes templates (which famously can do anything loops can, until they hit the implementation limits). The ability to interrupt programs that don't halt is fundamentally important to those of us who sometimes write code with bugs in it ;-)
Steve Jessop
CC BY-SA 4.0
2024-08-06T18:20:20.253Z
@psmears true, yet a program which iterates over an infinite list could very well terminate due to laziness.  the whole calculus is different when you're lazy
Moonchild
CC BY-SA 4.0
2024-08-06T19:29:12.073Z
Yeah, it's not a problem - just pointing out that even with immutable lists you can potentially get loops (this is possible, in principle, even in a non-lazy language, though I don't know offhand of any that do support it...)
psmears
CC BY-SA 4.0
2024-08-12T11:43:23.670Z
Semidecidability does not mean "we can solve it, sometimes"; what you've summarized and later described amounts to "a non-decidable language can have decidable subsets for which determining whether a string is part of it is decidable." This is important because the statement holds even if you replace "non-decidable" with "non-semidecidable". Arguably, compilers aren't tackling HALT, but ALL.
gnarrithas
CC BY-SA 4.0
2024-09-09T15:53:24.630Z
The "swap to unsigned integers" (third paragraph) is probably the wrong way around. In C++, signed underflow is Undefined Behavior. Unsigned underflow wraps around. That's exactly the cyclical behavior you're worrying about.
MSalters
CC BY-SA 4.0
2024-09-10T12:23:21.283Z
@MSalters no, it is not the wrong way around.  that whole section does not rely on undefined behaviour at all.  it is true that the c++ function unsigned f(unsigned n) { return n - 1; } is not monotonic and is distinct from the decrement function (though it is related).  this is part of the handwaving.  i had rather written everything in ml syntax with pattern-matching destructuring and using N = Z | S N, but anyway the implication is that the compiler will effectively reason about it that way.  but that part is trivial and not so interesting so i didn't bother to say anything about it
Moonchild
# How is clang able to evaluate loops without getting stuck in an infinite loop?
Posted by: username_0 on 2024-08-05
I recently saw this tweet.
And for posterity, this is the C++ code:
inline int square( int n )
{
    int k = 0;
    while ( true )
    {
        if( k == n*n )
            return k;
        
        k++;
    }
};

int main()
{
    return square(10);
}

This gets compiled to:
main:
    mov eax, 100
    ret

Somehow, clang is able to evaluate this square function, which includes a while (true).
This is quite surprising to me, because while (true) should be an immediate red flag that the loop may not terminate.
So it seems to imply that either clang has solved the halting problem, or clang can potentially get caught in an infinite loop and never finish compiling.
So, what's going on under-the-hood?
**Tags:** compilers c++ static-analysis loops inlining
> **Comments:**
> **username_1**: Leaving this as a comment because I don't have a source, but the compiler may assume there is no infinite loop without side effects, since that would be UB in C. Also, `if (a == b) return a;` and `if (a == b) return b;` are pretty obviously equivalent. The compiler is allowed to assume that loop exits, and that return statement is the only way it can exit, so the compiler optimizes the loop to just the return statement.  
> **username_2**: The simplest thing it might do is evaluate the loop until some fixed number of iterations, and stop trying to optimise if it takes too many iterations. Another possibility is that it doesn't evaluate the loop at all, instead noticing that the only `return` from the function is of the value `k` guarded by the condition `k == n * n`. So if the function ever returns anything then it must return `n * n`, and AFAIK C++ compilers are allowed to assume termination of side-effect-free loops even if they can't prove it.  
> **username_3**: "Solving the halting problem" would entail an algorithm which, for *every* possible loop, can determine with perfect accuracy whether it terminates.  There's nothing impossible about an algorithm that is able to detect whether *certain* loops terminate.  In the case of clang, the vast majority of possible looping code cannot be optimized like this, so the halting problem is intact.  
> **username_3**: I mean, surely *you* can sit down and write a proof that this loop terminates, notwithstanding that it is written as `while(true)`.  You can do so in a bounded amount of time, without having to actually simulate the loop.  And nothing stops a compiler from applying the same logic that you did.  But neither of you have solved the halting problem.  
> **username_3**: @kaya3 and Bbrk24: you're correct that C and C++ disallow infinite loops with no side effects (with certain exceptions not relevant here), thus allowing to compilers to assume a side-effect-free loop always terminates, and that would make it easier for the compiler to optimize this into a constant.  However, with both gcc and clang, you can switch off that rule with the flag `-fno-finite-loops`, and both compilers are still able to make the optimization.  https://godbolt.org/z/YhW794ePe.  So that rule is a red herring here.  
> **username_4**: The question doesn't really make sense as, after compilation, it would be obvious that this isn't an infinite loop. It should even result in the same CFG as when moving the condition to while and the return after the loop.  
> **username_5**: You can actually use https://godbolt.org/z/84Pf5zhhv to see how LLVM does it, pass-by-pass. This lets you see exactly what transformation each optimizer pass does from the original unoptimized LLVM IR all the way to a slightly odd representation of the machine instructions.  
> **username_6**: I wondered what would happen if I made the loop so that it doesn't actually hit the the correct value of `k`. E.g. start with `k=0`, iterate `k+=2` and ask for `square(11)`. Here, gcc compiles it into a busyloop, but, clang returns 120, so n*n-1. Curious. https://godbolt.org/z/6hezrM1KK  
> **username_3**: @ilkkachu: If the correct value is not hit, then `k` increments until it overflows, and signed integer overflow in C and C++ is undefined behavior.  So the behavior of the code in that case can be anything, and the compiler is not required to actually execute all the steps in between.  (If you used `unsigned`, then the overflow is not UB, but the infinite loop with no side effects is still UB as mentioned above, so either behavior is still okay.)  
---
## 7 answers
### Answer by username_5 on 2024-08-07. Score: 27 | Accepted answer
Because this is an optimization Clang does, you can use godbolt.org to explore it optimization pass by optimization pass. I've turned on the "Optimization Pipeline Viewer", set the "Options" to include "Dump Full Module", and changed the "Filters" to "Hide Inconsequential Passes" (so it hides all passes that don't change the IR under consideration). I'm not going to describe all the passes involved to get to the result in question, just the ones that make significant changes to the code.
The first interesting pass is "LICMPass on while.cond"; this detects that n * n is the same on every iteration of the loop, and moves the calculation to before the loop. This makes the LLVM IR analogous to (noting that semantics don't map cleanly because C doesn't have phi nodes):
inline int square( int n )
{
    int k = 0;
    int mul = n * n;
    while ( true )
    {
        if( k == mul )
            return k;
        
        k++;
    }
};

The next interesting pass is "LoopRotatePass on while.cond". This rearranges the loop further, to look a little like:
inline int square( int n )
{
    int k = 0;
    int mul = n * n;
    while ( k != mul )
    {
        k++;
    }
    return k;
};

since it's determined that the only way to escape the loop is for k == mul to be true, and then it immediately returns k. This is the pass that has determined that the loop is not infinite, and it's done so just based on the loop body.
Then, after some more minor passes to prepare the LLVM IR for this optimization to fire, "IndVarSimplifyPass on while.cond" removes the loop, because it can see that k is an induction variable, and changes the code to look like:
inline int square( int n )
{
    while ( false )
    {
    }
    int mul = n * n;
    return mul;
};

From here, some more passes clean up square to be inline int square( int n ) { return n * n; }; then "InlinerPass on (main)" replaces the call to square in main with (10 * 10) and does constant folding to turn this into a constant 100. The remaining significant passes simply convert from LLVM IR to LLVM's internal representation of x86-64 machine code, ready to be output.
> **Comments:**
> **username_0** (2024-08-07): Everyone's answers were great, but this one answered my question most closely by stepping through the LLVM optimization passes (I specifically asked for what's going on under-the-hood of clang.)  
> **username_14** (2024-08-09): I think the second re-arrangement is the critical step... it's the one that illustrates that despite the syntax used, this _isn't_ a `while (true)` loop... it just has the break condition inside the body instead.  
---
### Answer by username_16 on 2024-08-05. Score: 15
There are basically two reasons for this: **the halting problem is semidecidable** (i.e., we can solve it, sometimes), and **the C++ standard allows LLVM to cheat** and pretend it solved the halting problem even though it didn't

# How to solve the halting problem

(Note: this section is somewhat handwavy; I might make it more rigorous later, but I think it gives a good intuition as is.)

The halting problem says that we can never make a procedure that takes another procedure and says either 'yes, this halts' or 'no, it doesn't'. But we don't actually need something like that. What we want, rather, is a procedure that takes another procedure and says 'yes, this halts' or 'no, it doesn't' *or* 'this is too complicated; I don't know'. This is trivially possible (you could just always say 'don't know'), but we would like to have some strategies for giving more useful results. Follows is one particular strategy that works well:

If we can identify an instance of an inductive data type whose value decreases on every loop iteration, then we can be assured that the loop terminates. Why? Because eventually, the inductive data type will 'bottom out'. At that point, there is no way to decrease it any further. But in order to proceed to the next loop iteration, we would *have* to decrease it. Which means that we must not proceed to the next loop iteration; either at that point or before that point, we must have terminated the loop.

Where's the decreasing quantity here? First swap out 'int' for 'unsigned'; integers can be defined inductively, but the order gets messed up which makes things more confusing, and there are no negative numbers here anyway. Naturals are easier to work with and numerical order does what we want. Now the quantity that decreases on each iteration is n\*n - k. On any given iteration, either this is zero or it is nonzero. If n\*n - k == 0, then n\*n == k, and so the loop terminates. Otherwise, we proceed to the next loop iteration with k increased by 1, and therefore n\*n - k decreased by 1.

It's worth re-emphasising the role that the inductive type plays here. In an immutable language, a linked list is inductive, and therefore iterating over a linked list always terminates. On the other hand, in a language like C, which is mutable, iterating over a linked list does not necessarily terminate, because the list could have cycles in it.

# How to con standardisers into solving the halting problem for you

Refer to section intro.progress in [the c++ standard](https://www.open-std.org/JTC1/SC22/WG21/docs/papers/2020/n4849.pdf). This effectively says that compilers can simply assume that loops like the one you showed always terminate, and if you write a loop that *doesn't* terminate, it's your own fault.
> **Comments:**
> **username_19** (2024-08-06): "in an immutable language, a linked list is inductive, and therefore iterating over a linked list always terminates." - This doesn't necessarily follow - Haskell is an immutable language, and yet iterating over a list doesn't always terminate.  
> **username_20** (2024-08-06): Also, although this isn't how clang does it, another way to partially solve the halting problem is to run the loop for, say, an hour. If it halts, you have your result. If it doesn't halt, or if it does anything with side effects, say you don't know (and in this case, inline the code instead of the result). There's nothing in the standard that says compilers have to be fast.  
> **username_20** (2024-08-06): By "run the loop" I don't mean compile the unoptimised code to the target architecture and run it there. The compiler could in principle execute the code in some sort of sandbox, perhaps similar to the way that it evaluates static constant expressions, and/or the way it computes templates (which famously can do anything loops can, until they hit the implementation limits). The ability to interrupt programs that don't halt is fundamentally important to those of us who sometimes write code with bugs in it ;-)  
> **username_16** (2024-08-06): @psmears true, yet a program which iterates over an infinite list could very well terminate due to laziness.  the whole calculus is different when you're lazy  
> **username_19** (2024-08-06): Yeah, it's not a problem - just pointing out that even with immutable lists you can potentially get loops (this is possible, in principle, even in a non-lazy language, though I don't know offhand of any that do support it...)  
> **username_21** (2024-08-12): Semidecidability does not mean "we can solve it, sometimes"; what you've summarized and later described amounts to "a non-decidable language can have decidable subsets for which determining whether a string is part of it is decidable." This is important because the statement holds even if you replace "non-decidable" with "non-semidecidable". Arguably, compilers aren't tackling HALT, but ALL.  
> **username_22** (2024-09-09): The "swap to unsigned integers" (third paragraph) is probably the wrong way around. In C++, signed underflow is Undefined Behavior. Unsigned underflow wraps around. That's exactly the cyclical behavior you're worrying about.  
> **username_16** (2024-09-10): @MSalters no, it is not the wrong way around.  that whole section does not rely on undefined behaviour at all.  it is true that the c++ function unsigned f(unsigned n) { return n - 1; } is not monotonic and is distinct from the decrement function (though it is related).  this is part of the handwaving.  i had rather written everything in ml syntax with pattern-matching destructuring and using N = Z | S N, but anyway the implication is that the compiler will effectively reason about it that way.  but that part is trivial and not so interesting so i didn't bother to say anything about it  
---
### Answer by username_15 on 2024-08-05. Score: 10
Clang neither solves the halting problem, nor it is evaluating the loop, potentially forever. It is only optimizing the loop once, as part of the compilation process.
Let's compile the code as an optimizing compiler would
There are various optimizations intermingled here, so try to make this very simple.
First, square(int n) is called with n = 10. This is important because 10 is a constant, so the compiler can now create a copy of this function for this specific invocation. This is called function specialization, and is also encouraged by inline. The specialized function is now:
inline int square_10()    // Const parameter removed
{
    int k = 0;
    while ( true )
    {
        if( k == 10*10 )  // Const value replaced
            return k;
        k++;
    }
};

Here, 10*10 is trivially optimized to 100. There is not much code left (this will be important later).
There is a local variable k initialized to 0, and there is the while(true) loop, with only two statements. One is the if, the other is the local increment of k. From the latter, the compiler can extrapole the range of k as all positive numbers (until it reaches undefined behavior).
The internal compiled code is now approximately represented in memory as:
inline int square_10()
{
    // k = $ALL_POSITIVE_INT (compiler internal state)
    while ( true )
        if( k == 100 )
            return k;
};

This can also be trivially optimized in two steps. First the if will be eventually true because 100 is in the range of k, so the return can be reached. And when the return is reached, k is restricted to 100.
There is no other instructions that change the result, so the only possible effect of this code is optimized to:
inline int square_10()
{
    return 100;
}

There are no calls for square(int n), so the "normal" function is never generated. The code is now reduced to an inline function that returns a constant. This is inlined to:
int main()
{
    return 100;
}

Well, this is fine and dandy, but let's test some assumptions from above.
Constant argument and multiplication elimination
You can try replacing 10 by getchar() from the original example, and you will see the compiler will not optimize the code to a constant anymore.
It will eliminate the loop, but keep the mul, as now the function result literally depends on the function argument: the return is only constant for a constant parameter.
Range inspection and loop elimination
You can further further replace k++ by k = getchar(), and you will see the compiler will not eliminate the loop (as observed with the jumping around, je and jne).
It also will keep the imul around, as the compiler cannot assume any value of k beyond the initial zero.
An optimizing compiler only cares for code that cause effects
Inserting an putchar(0); anywhere inside the while would disable the loop elimination. An putchar(0); before the while generates some additional assembly, and a putchar(0); after the while causes nothing, because it is detected as dead code from the same optimizations above.
TL:DR;
A mix of function specialization, constant propagation, constant folding, range inspection, code invariant analysis and dead code elimination can generate these results. There is no evaluation involved.
> **Comments:**
> **username_3** (2024-08-05): In your `getchar()` example, the compiler still *does* do the optimization that's of interest here, namely replacing the loop with a single multiply instruction.  
> **username_16** (2024-08-05): 'int k = 0 .. INT_MAX'  'the if is always true because of the range of k, so the return is always reached.'  this is complete and utter nonsense  
> **username_17** (2024-08-06): Since infinite loops are UB and there is only a single exit in the loop, the compiler can just assume this exit is reachable and infer the condition to be true.  
> **username_18** (2024-08-06): @Falco not sure how so many answers get it wrong. There is no need to assume anything about infinite loops (in fact, they are not UB in C and the same optimization applies). It's just simple - compiler can assume that `k` always reaches 100 at some point, because it monotonically increases (and integer overflow is UB, but even if `k` was unsigned same deduction could be made due to wraparound).  
> **username_16** (2024-08-06): @DanM. some infinite loops are 'ub' in c (howbeit not this one); refer to sec. 6.8.5p6 of [the standard](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf)  
> **username_18** (2024-08-07): @Moonchild that's what I'm saying. Many answers go on and on about UB infinite loops, but it has zero relevance for THIS particular example. Also, you are using outdated draft, this loop is not UB even in C++: https://eel.is/c++draft/intro.progress#1  
> **username_10** (2024-08-07): The Standard specifies that there are three ways an action may be characterized as UB. 
 It the authors intended that endless loops be "anything can happen" UB, they could have said that side-effect-free loops *shall* terminate.  The use of more verbose and "non-standard" phraseology would seem odd unless they intended to allow some otherwise unsound optimizations of the form hinted at by the footnote without treating the loops as "anything can happen" UB.  
> **username_10** (2024-08-07): @Moonchild: [see comment above]: Treating endless loops as "anything can happen" UB will be counter-productive in cases where code would be required to uphold memory safety invariants for all inputs. Absent such treatment, one could prove that a program would uphold memory safety invariants by proving that no individual action could violate them unless they had already been violated, without having to prove that no inputs could cause a program to get stuck in an endless loop.  Requiring that programmers add otherwise-unnecessary code to loops to uphold memory safety...  
> **username_10** (2024-08-07): ...will not only negate any possible optimizations that could only be facilitated by treating endless loops as UB, but also optimizations that could have been facilitated by allowing implementations to *cleanly* omit loops which have no side effects upon which downstream code visibly relies, *nor which the compiler's generated downstream machine code exploits*.  
---
### Answer by username_7 on 2024-08-06. Score: 8
There is a lot of talk about inductive types and inlining here, but the optimisations in the code can be achieved through far simpler methods.
Let's look at the function
inline int square( int n )
{
    int k = 0;
    while ( true )
    {
        if( k == n*n )
            return k;
        
        k++;
    }
};

There is only one way it can ever return - if k == n*n. If that is true, it will return k, so the compiler can transform the code to instead return n*n - this is a simpler expression, as it is constant during the loop (unlike k)
inline int square( int n )
{
    int k = 0;
    while ( true )
    {
        if( k == n*n )
            return n*n; //  <-- !!
        
        k++;
    }
};

Now the compiler is in a different scenario. It knows the value it will return, but not if it will return. Thankfully, it can assume that! When there is a "simple"* loop, it is undefined behaviour for it to run forever. Now the compiler has two key facts:

The loop returns n*n, which is constant from the start of the function as n is never changed
The loop must return**

Therefore, it can trivially change the function into
inline int square( int n )
{
    return n*n;
}

Now, if infinite loops were not considered undefined, it would have to prove the loop always terminates. It can do that pretty simply using the inductive logic discussed before:

n*n must always be positive and will be in the range of an int
k starts at zero and increases through the entire positive range of an int
Therefore, k must equal n*n at some point
With this slightly more complex logic, it can make the same transformation as before

The final step of getting the assembly is that it ends up inlining this function and using the constant value provided, but that is less important :)
* "simple" means not doing anything visible to the outside world, such as IO or volatile access.
** In the name of clarity, C compilers will normally not optimise loops in this manner as it is confusing if an infinite loop simply vanishes. Its real logic is likely closer to the second loop optimisation, but it is still perfectly legal for it to do it the first way
> **Comments:**
> **username_8** (2024-08-06): The "undefined behaviour" argument is wrong. Notice that by this logic, the compiler would optimise the code in exactly the same way even if the `k++` line wasn't there, which it obviously doesn't do.  
> **username_9** (2024-08-06): @leftaroundabout: I believe some compilers do try to recognize cases where there's no loop variable or the loop variable is constant, and as a courtesy to the programmer, may decide not to optimize such loops. But it is still UB to write such a loop unless it terminates, and the compiler would be within its rights to apply the optimization regardless.  
> **username_7** (2024-08-07): @leftaroundabout it was meant to be "these are the rules the compiler may follow to optimise it", but that may not have been clear. i have added clarification  
> **username_10** (2024-08-07): How often is the described optimization useful, compared with what would be possible if a compiler were allowed to omit the loop in cases *where the returned value is ignored*, but not in cases where downstream code makes use of a computation performed within the loop?  
> **username_10** (2024-08-07): In almost any other situation where permission to assume X is given, that does not imply permission to assume things that would need to be true in order for X to be true, but rather permission to proceed in a manner which is *agnostic* to whether X is true or not.  In a physics problem, permission to assume that acceleration due to gravity is exactly 9.800 m/s/s does not imply permission to assume that an object isn't located in a place where local acceleration due to gravity is slightly different, but merely to ignore any deviation between actual acceleration and the value given.  
> **username_11** (2024-08-08): @leftaroundabout Actually if you remove `k++` then the compiler goes even further: it knows the only argument which does not cause an infinite loop is `n == 0`. Since it follows that the only argument to `square` that does not cause UB is zero, it goes ahead an and optimizes `square` to simply zero a register and returns. Both GCC and Clang will perform this optimization. https://godbolt.org/z/KhMehrn3x  
> **username_8** (2024-08-09): @JackLloyd well, that is certainly curious. On my machine, it always compiles to an unconditional infinite loop, but apparently I was wrong to think that this is what compilers generally will do in practice.  
---
### Answer by username_12 on 2024-08-06. Score: 3
This isn't an answer to the question, since it's not about Clang, but we also implemented termination analysis in the Mercury compiler, and also supported a pragma which asserted that a procedure always terminates.
On top of compile-time evaluation, it's useful for goal reordering. In a purely declarative language, this transformation is almost always correct:
p(), q() -> q(), p()

(i.e. "call p then call q" can be reordered). The only time it isn't correct is if the call to q can infinitely loop.
There are other cases to consider, of course; perhaps p and q can both raise exceptions, say. But if you're designing the language, you can simply rule that raising either exception is valid semantics in this situation.
---
### Answer by username_10 on 2024-08-06. Score: 0
There are two ways a language specification may allow a compiler to avoid having to solve the halting problem to make what should otherwise be simple and useful optimizations:

1. The language specification may allow actions to be deferred until their side effects would be observable, and deferred forever (effectively skipped entirely) if their side effects will never be observed, and specify that branches within a section of code has a single exit which is statically reachable from all code within the section need not be regarded as side effects in and of themselves.
2. The language specification may specify that implementations may behave in arbitrary fashion if a program receives inputs that would cause it to get stuck in a side-effect-free endless loop.

The former approach will allow most of the useful optimizations that would be facilitated by the latter, but allow humans or automatic code validators to reason about program invariants. The latter approach would make it impossible to prove any invariants without proving that a program will terminate for all possible inputs, but would allow compilers to avoid tough decisions about whether to omit a loop or exploit post-conditions which would be established if the loop were existed, by letting compilers apply both optimizations simultaneously.

IMHO, the second approach is counter-productive for most kinds of tasks, since the only situation in which a compiler could ever improve the performance of correct code would be if either:

1. The programmer could prove that the program would terminate for all possible inputs, but a compiler couldn't.
2. There would be no requirement that a program uphold memory safety or any other invariants for inputs that might cause a program to get stuck in and endless loop.

If a program contained any otherwise-side-effect loops that might fail to terminate, the only way to ensure that any invariants would be upheld would be to add dummy side effects to the loop or add artificial exit conditions, either of which would mean either that a compiler wouldn't be allowed to omit the loop even if it happened to be useless, or that a compiler's entitlement to omit the loop would not depend upon whether endless loops had defined behavior.

As a consequence, while optimizations allowed under the first semantic approach could be usefully employed in correct programs, those allowed under the broader semantics are primarily effective when processing erroneous programs.
---
### Answer by username_13 on 2024-08-08. Score: 0
An optimising compiler could use different strategies.

A straightforward strategy: If you want the compiler to halt in all cases, translate the loop but make sure it halts (for example after one billion iterations or after one second of compiler time). If it halts, the inline call just produces a constant. If it doesn't halt fast enough, call the non-inlined function. This works in all situations.

If you don't require the compiler to halt: I'd have to pull out the "Standard lawyer's handbook". An infinite loop is undefined behaviour (I think). I'm not sure if undefined behaviour allows bad behaviour in the compiler as well. However, this approach is very unsatisfactory if I write an inline function that will halt after 1,000 years of compile time.

In this specific case, the function will either return k, or it will not return. Again the "Standard lawyer's handbook" will tell us whether returning k unconditionally is legal. However, n\*n invokes undefined behaviour for not-very-large n, so we know the function returns k or invokes undefined behaviour, and always returning k is legal.

And in many situations, the compiler can have built-in strategies. For example, even not-very-optimising compilers can easily calculate sums of polynomials with integer coefficients.
---
