www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.ldc - Optimizing away empty loop with step

reply Vladimir Panteleev <thecybershadow.lists gmail.com> writes:
DMD [fails](https://issues.dlang.org/show_bug.cgi?id=22158) 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:

```d
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
Jul 30 2021
next sibling parent reply "David Nadlinger" <code klickverbot.at> writes:
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
Jul 30 2021
parent Johan <j j.nl> writes:
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
Jul 31 2021
prev sibling parent reply Iain Buclaw <ibuclaw gdcproject.org> writes:
On Friday, 30 July 2021 at 09:58:01 UTC, Vladimir Panteleev wrote:

 DMD [fails](https://issues.dlang.org/show_bug.cgi?id=22158) 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:

 ```d
 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.
Jul 30 2021
parent reply Iain Buclaw <ibuclaw gdcproject.org> writes:
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](https://issues.dlang.org/show_bug.cgi?id=22158) 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:

 ```d
 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.
Jul 30 2021
parent reply Vladimir Panteleev <thecybershadow.lists gmail.com> writes:
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?)
Jul 31 2021
parent reply Kagamin <spam here.lot> writes:
If step==0 the loop is infinite.
Aug 02 2021
parent Vladimir Panteleev <thecybershadow.lists gmail.com> writes:
On Monday, 2 August 2021 at 11:09:26 UTC, Kagamin wrote:

 If step==0 the loop is infinite.


Yes, but not iff.
Aug 02 2021