Thread overview
Optimizing away empty loop with step
Jul 31
Johan
Aug 02
Kagamin
July 30

DMD fails to optimize away an empty for loop with an increment of 1. GDC and LDC both succeed.

However, the results are more interesting if you make the step variable:

void fun(int a, int b, int step)
{
    for (int i = a; i < b; i += step) {
    }
}

The above code (valid C and D) compiles to an empty function with clang and gcc:

https://godbolt.org/z/PnffvhecM

However, all three D compilers fail to optimize away the loop:

https://d.godbolt.org/z/r3MEGzoh1

Is the frontend doing something to prevent the loop from being optimized away as in C?

My first guess was that the compiler refused to optimize it away because it couldn't prove that the loop will ever exit. But, the C compilers don't seem to have an issue with that.

My second guess was that the C compilers were happy with optimizing it away because signed integer overflow is undefined in C. But, changing the type to unsigned didn't make a difference.

https://godbolt.org/z/hMb83ne9d

July 30
On 30 Jul 2021, at 10:58, Vladimir Panteleev via digitalmars-d-ldc wrote:
> My second guess was that the C compilers were happy with optimizing it away because signed integer overflow is undefined in C. But, changing the type to unsigned didn't make a difference.

LLVM/Clang 10 didn't optimise it away for me with everything made unsigned. Clang trunk on Godbolt does, but that's because it makes use of the fact that infinite loops are UB in C (as encoded in the `mustprogress` function attribute).

 — David
July 30

On Friday, 30 July 2021 at 09:58:01 UTC, Vladimir Panteleev wrote:

>

DMD fails to optimize away an empty for loop with an increment of 1. GDC and LDC both succeed.

However, the results are more interesting if you make the step variable:

void fun(int a, int b, int step)
{
    for (int i = a; i < b; i += step) {
    }
}

The above code (valid C and D) compiles to an empty function with clang and gcc:

https://godbolt.org/z/PnffvhecM

However, all three D compilers fail to optimize away the loop:

https://d.godbolt.org/z/r3MEGzoh1

Is the frontend doing something to prevent the loop from being optimized away as in C?

You can look at C-style IR dump using the GDC Tree/RTL output option.

https://d.godbolt.org/z/eM8Pv91eT

As you can see, the loop construct that GDC uses is treated as a while (1) { } statement.

You can reproduce this in Clang by rewriting the for loop into a while loop.

https://godbolt.org/z/hWePhqesq

GCC is still unaffected, but looking at the generated code, they opt to instead implement both loops with labels and goto expressions.

July 30

On Friday, 30 July 2021 at 10:21:37 UTC, Iain Buclaw wrote:

>

On Friday, 30 July 2021 at 09:58:01 UTC, Vladimir Panteleev wrote:

>

DMD fails to optimize away an empty for loop with an increment of 1. GDC and LDC both succeed.

However, the results are more interesting if you make the step variable:

void fun(int a, int b, int step)
{
    for (int i = a; i < b; i += step) {
    }
}

The above code (valid C and D) compiles to an empty function with clang and gcc:

https://godbolt.org/z/PnffvhecM

However, all three D compilers fail to optimize away the loop:

https://d.godbolt.org/z/r3MEGzoh1

Is the frontend doing something to prevent the loop from being optimized away as in C?

GCC is still unaffected, but looking at the generated code, they opt to instead implement both loops with labels and goto expressions.

On digging around further, C doesn't optimize away this kind of loop.

The actual compiler option that controls this is -ffinite-loops.

Assume that a loop with an exit will eventually take the exit and not loop indefinitely. This allows the compiler to remove loops that otherwise have no side-effects, not considering eventual endless looping as such.

This option is enabled by default at -O2 for C++ with -std=c++11 or higher.

You can add this to the GDC compiler window to observe the optimization, or add -fno-finite-loops to the G++ compiler window for the inverse.

July 31
On Friday, 30 July 2021 at 10:09:55 UTC, David Nadlinger wrote:
> On 30 Jul 2021, at 10:58, Vladimir Panteleev via digitalmars-d-ldc wrote:
>> My second guess was that the C compilers were happy with optimizing it away because signed integer overflow is undefined in C. But, changing the type to unsigned didn't make a difference.
>
> LLVM/Clang 10 didn't optimise it away for me with everything made unsigned. Clang trunk on Godbolt does, but that's because it makes use of the fact that infinite loops are UB in C (as encoded in the `mustprogress` function attribute).

Adding that attribute to the function indeed works, but requires LLVM 12:

https://d.godbolt.org/z/1Yb7YnP7e

-Johan

July 31

On Friday, 30 July 2021 at 22:23:08 UTC, Iain Buclaw wrote:

>

The actual compiler option that controls this is -ffinite-loops.

Assume that a loop with an exit will eventually take the exit and not loop indefinitely. This allows the compiler to remove loops that otherwise have no side-effects, not considering eventual endless looping as such.

This option is enabled by default at -O2 for C++ with -std=c++11 or higher.

You can add this to the GDC compiler window to observe the optimization, or add -fno-finite-loops to the G++ compiler window for the inverse.

I see, thanks for looking into it.

I wonder if there's a way to tell the compiler (using portable D) that it can assume that the loop will not be infinite. moon-child on IRC pointed out that this loop can be infinite in many cases, e.g. if b is uint.max and for any even value of step (i.e. i cannot take any value that is >= b).

(Maybe something like __builtin_reachable after the loop?)

August 02

If step==0 the loop is infinite.

August 02

On Monday, 2 August 2021 at 11:09:26 UTC, Kagamin wrote:

>

If step==0 the loop is infinite.

Yes, but not iff.