How is clang able to evaluate loops without getting stuck in an infinite loop?

Question

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?

Answer 1

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.

Answer 2

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. 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.

Answer 3

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.

Answer 4

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

Answer 5

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 6

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 7

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.