[SOLVED] Poor optimization of constant folding
lazarus / 64-FPC development

----------------------------------------------------------------------
lagprogramming · 2023-09-27 08:53

According to FPC's Programmer's guide:
Quote11.1.1
Constant folding
In Free Pascal, if the operand(s) of an operator are constants, they
will be evaluated at compile time.
Example
x:=1+2+3+6+5;
will generate the same code as
x:=17;So, I thought arithmetic operations of constants are computed at
compile time.
The following program should be self explanatory.
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i program
ConstantFoldingOptimization;{$OPTIMIZATION LEVEL3}function
Foo(a:integer):integer;begin  result:=-a*2;  {negl %edi   leal
(%edi,%edi,1),%eax}end; function Bar(a:integer):integer;begin 
result:=a*(-2);  {movl  %edi,%eax   imull $-2,%eax}end; function
Baz(a:integer):integer;begin  result:=a*(-2)*(-1)*(-1)*(-1)*(-1)*(3); 
{movl %edi,%eax  imull $-2,%eax  negl  %eax  negl  %eax  negl  %eax 
negl  %eax}end; function Wow(a:integer):integer;begin 
result:=a*(-2)*(-1)*(-1)*(-1)*(-1)*(3);  {movl %edi,%eax  imull
$-2,%eax  negl  %eax  negl  %eax  negl  %eax  negl  %eax  leal 
(%eax,%eax,2),%eax}end; var  z:integer;begin  z:=paramcount; 
writeln(Foo(z));  writeln(Bar(z));  writeln(Baz(z)); 
writeln(Wow(z));end.If constant folding optimization has been disabled
temporarily, I have to say that it takes quite some time to enable it
again.
Maybe this optimization is not disabled, maybe it's just incomplete.

----------------------------------------------------------------------
Fibonacci · 2023-09-27 09:06

Its computed at compile time only if whole expression is constant

Code: ASM  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i # [5]
result:=a*(-2)*(-1)*(-1)*(-1)*(-1)*(3);        imull   $-2,%eax      
negl    %eax        negl    %eax        negl    %eax        negl   
%eax        leal    (%eax,%eax,2),%eax
Code: ASM  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i # [5]
result := (-1)*(-1)*(-1)*(-1)*(3);        movl    $3,%edx# [6] result
:= a*(-2)*result;        imull   $-2,%eax        imull   %edx,%eax

----------------------------------------------------------------------
runewalsh · 2023-09-27 09:42

Reported here. Until the fix in mid-2030s, you can force the folding
with parentheses:

Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i
result:=a*((-2)*(-1)*(-1)*(-1)*(-1)*(3));

----------------------------------------------------------------------
Fibonacci · 2023-09-27 09:49

Quote from: runewalsh on September 27, 2023, 11:42:56 amUntil the fix
in mid-2030s

----------------------------------------------------------------------
440bx · 2023-09-27 09:53

Quote from: runewalsh on September 27, 2023, 11:42:56 am Until the fix
in mid-2030s, you can force the folding with parentheses:

Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i
result:=a*((-2)*(-1)*(-1)*(-1)*(-1)*(3));or better yet, calculate the
value of the constant along with a comment as to how it was calculated
(if necessary for clarity)

----------------------------------------------------------------------
runewalsh · 2023-09-27 10:02

Quote from: 440bx on September 27, 2023, 11:53:55 amcalculate the
value of the constant along with a comment

Better to declare a const if you are that distrustful of folding.

----------------------------------------------------------------------
lagprogramming · 2023-09-28 10:44

Quote from: 440bx on September 27, 2023, 11:53:55 amQuote from:
runewalsh on September 27, 2023, 11:42:56 am Until the fix in
mid-2030s, you can force the folding with parentheses:

Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i
result:=a*((-2)*(-1)*(-1)*(-1)*(-1)*(3));or better yet, calculate the
value of the constant along with a comment as to how it was calculated
(if necessary for clarity)
@runewalsh
Additional parenthesis is a nice trick.

@440bx
 Reminds me of the following lines in LCL's customdrawnwinapi.inc
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i
//lFontSize:= MulDiv(lFontSize,72,ftFont.DPI); // convert points to
pixelslFontSize := Round(ftFont.TextHeight(Str) * 0.75);// ToDo: Find
out why this 75% factor works Most likely a developer precomputed that
0.75 constant value and other developers could not trace the
arithmetic to source.
Fpgui has:
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i function
TFPGUIWinAPIFont.GetFontSize: integer;begin  Result:=(-FFontHeight *
72) div 96;end;72/96=0.75

----------------------------------------------------------------------
Thaddy · 2023-09-28 13:48

declaring as inline, provided all elements are constant..

----------------------------------------------------------------------
ccrause · 2023-09-28 15:04

Quote from: Fibonacci on September 27, 2023, 11:06:49 amIts computed
at compile time only if whole expression is constant
The simplification of constant folding happens in taddnode.simplify
(at least the initial simplification).  Here the left and right nodes
of an operator are inspected to check if both are constant and of the
same type, then the folding is applied. Since this simplification only
looks at the immediate left and right nodes of the operand,
opportunities farther away is not visible. 
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i   b := 10; 
a := -1 * b * -1;With -O2 or lower the following code is generated:
Code: ASM  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i # [9] a :=
-1 * b *  -1;        movslq  %esi,%rbx        negq    %rbx       
negq    %rbx   With -O3 or higher:
Code: ASM  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i # [9] a :=
-1 * b *  -1;        movl    $10,%esi   So there is another
optimization that can further simplify the expression, although the
following example doesn't fold at -O4:
Code: ASM  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i # [15] a :=
b * -1 * -1;        movslq  %edi,%rbx        negq    %rbx        negq 
  %rbx
A workaround is to create sub expressions that can be folded before
taddnode.simplify is called:
Code: ASM  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i # [18] a :=
b * (-1 * -1);        movslq  %esi,%rsi
One could perhaps expand the scope of the simplification to search one
node wider (deeper?) to cover the above case, but that will then fail
to fold the following example:
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i a = -1 * b
* -1 * b * -1;Note: this example does get simplified all the way to a
constant value at -O3.

I think the current situation where seemingly obvious opportunities
for constant folding are missed is caused by the fairly simplistic
heuristics used by the compiler.  Perhaps someone can come up with a
tweak to this heuristic that covers more situations without incurring
a significant speed penalty.

----------------------------------------------------------------------
440bx · 2023-09-28 17:18

I doubt what I am going to mention can be applied to FPC without
significant effort.  The solution to a large number of expression
optimization problems, including constant folding, is to evaluate the
expression _symbolically_. 

This not only coalesces all constants (such as the above examples) but
allows for the recognition of common algebraic patterns that can be
substituted for equivalent but simpler (read faster) patterns.

A little bit of Mathematica in the compiler

----------------------------------------------------------------------
Warfley · 2023-09-28 22:13

Doing something like this is not as easy as one may think. Whe you as
a human look at "x * 2 * 3 * 4" you probably see a (singular) chain of
multiplications, basically one variable and then some tail thats
multiplied onwards. But for the compiler * is a left associative
binary operation. So the compiler sees "(((x*2)*3)*4)".
This is then parsed into the following binary tree:
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i         * 
    / \      *   4     / \    *   3   / \  x   2For the compiler every
single * node is a non constant node, because the left side of the
multiplication is always a subtree containing a variable. To be able
to reckognize that it is equivalent to one variable multipled with a
constant subtree, this tree must be transformed into a right
associative tree:
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i    *  / \ x
  *    / \   2   *      / \     3   4
The operations here are pretty simple, as it's a simple tree invert,
but there are more complex trees:
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i x * (2 * y)
* 3     *    / \   *   3  / \ x   *    / \   2   y
Of course there are options to make this easier, e.g. you could use a
flattend n-ary tree to reason over it, which makes it much, as you can
then simply remove the non constant subtrees. While this works for
such trivial examples, as soon as you have mixed multiplication and
addition this won't work anymore.
Then you would need to normalize your formular, by repeatedly applying
the distributive law. But this is in exp-space (and exp-time). E.g.
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i   (a * 2) +
(b * 3) + (c * 4)= (a + b + c) * (2 + b + c) * (a + 3 + c) * (2 + 3 +
c) * (a + b + 4) * (2 + b + 4) * (a + 3 + 4) * (2 + 3 + 4)So a sum of
x terms consisting of products of n factors you will get x^n terms in
when normalizing using the distributive law (in this case 2^3=8). And
all of this just to find a single constant subexpression that is not
worth optimizing away because it blows this formular up so much
So what would happen for complex arithmetic expressions is, you would
hit compile, then your FPC freezes for quite some time and then crash
because it ran out of memory.

Of course there are heuristics and other things, for example GCC
compiles the following non trivial expression:
Code: C  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i int
compute(int num) {    return 1 + (num * 3) + (4 * 5);}Into the single
instruction:
Code: ASM  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i lea    
eax, [rdi+21+rdi*2]But this comes at a cost, and that cost is that C
compilation is really really slow. Compiling FPC with FPC takes a
minute or so. Compiling GCC with GCC takes around 6 hours.

The FPC is a very fast compiler compared to many C compilers like
Clang or GCC. But the reason is not because the FPC is so much better
optimized, but because it simply does much less stuff. And this sort
of optimization is the sort of stuff FPC does not do compared to it's
C counterparts

----------------------------------------------------------------------
Fibonacci · 2023-09-29 02:11

Quote from: Warfley on September 29, 2023, 12:13:25 amCompiling GCC
with GCC takes around 6 hours.

What

----------------------------------------------------------------------
circular · 2023-09-29 03:46

Sometimes, deep optimizations might give a different result. Consider
an obvious example:
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i result :=
(a div 3) * 3; It is clear here that simplifying to a would remove the
effect aligning to a multiple of 3. Obviously, the compiler would not
optimize in this case. But sometimes the effect can be more subtle.

For example, with range of values can be reached in intermediate
values or the result is different due to the precision of floating
point values. Such optimization could be depend on a compiler option
for backward compatibility.

Putting things that can be optimized inside brackets or in a constant
is a tradeoff to say where the compiler can simplify.

----------------------------------------------------------------------
Leledumbo · 2023-09-29 05:02

Quote from: Fibonacci on September 29, 2023, 04:11:46 amQuote from:
Warfley on September 29, 2023, 12:13:25 amCompiling GCC with GCC takes
around 6 hours.

What
The full source package indeed takes around that long even with a
powerful CPU, a lot of fast RAM and NVMe SSD. The language, the
compiler and the build system all contribute to its slow build time.
However, if you just want to build the C and C++ part, it "only" takes
30-40 minutes, standard libraries included. Of course that number
still looks pale compared to bootstrapping both fpc and lazarus that
takes less than 5 minutes on my machine (I add -O3 to my build script,
so it's already a voor).

----------------------------------------------------------------------
440bx · 2023-09-29 06:00

Quote from: Leledumbo on September 29, 2023, 07:02:04 amThe full
source package indeed takes around that long even with a powerful CPU,
a lot of fast RAM and NVMe SSD.
I've wondered for quite some time how long it takes to do a full build
of Windows 10 or 11.  That's 25 million+ lines of code, even on a
really fast machine, it must be a rather "noticeable" amount of time.

----------------------------------------------------------------------
dsiders · 2023-09-29 06:26

Quote from: 440bx on September 29, 2023, 08:00:38 amQuote from:
Leledumbo on September 29, 2023, 07:02:04 amThe full source package
indeed takes around that long even with a powerful CPU, a lot of fast
RAM and NVMe SSD.
I've wondered for quite some time how long it takes to do a full build
of Windows 10 or 11.  That's 25 million+ lines of code, even on a
really fast machine, it must be a rather "noticeable" amount of time.

I saw this some time ago:

> How long does it take to compile Windows?
>> Ales Holecek, vice president for development in Windows team said
that it takes about 16 hours to build Windows 10.
>> And that it's built automatically every day during the night.
>> Oct 2008

----------------------------------------------------------------------
marcov · 2023-09-29 07:04

Quote from: Warfley on September 29, 2023, 12:13:25 amCompiling FPC
with FPC takes a minute or so. Compiling GCC with GCC takes around 6
hours.

IIRC Sub minute for the whole FPC repo on a Ryzen 5700X on linux. A
few seconds over a minute for windows.

But that includes RTL, packages and textmode IDE

p.s. my buildscript does skip the WPO optimization cycle.

----------------------------------------------------------------------
440bx · 2023-09-29 08:29

Quote from: dsiders on September 29, 2023, 08:26:59 am>> Ales Holecek,
vice president for development in Windows team said that it takes
about 16 hours to build Windows 10.
>> And that it's built automatically every day during the night.
>> Oct 2008
Thanks dsiders. 

16 hours... what a drag!  I'm guessing that includes all the
utilities, e.g, explorer.exe, IE/Edge, some of .net, etc, along with
the O/S proper.  IOW, everything that goes into "c:\windows" and
possibly a few things that go into "c:\program files".

I guess he didn't mention the hardware specs.

----------------------------------------------------------------------
dsiders · 2023-09-29 15:02

Quote from: 440bx on September 29, 2023, 10:29:57 amQuote from:
dsiders on September 29, 2023, 08:26:59 am>> Ales Holecek, vice
president for development in Windows team said that it takes about 16
hours to build Windows 10.
>> And that it's built automatically every day during the night.
>> Oct 2008
Thanks dsiders. 

16 hours... what a drag!  I'm guessing that includes all the
utilities, e.g, explorer.exe, IE/Edge, some of .net, etc, along with
the O/S proper.  IOW, everything that goes into "c:\windows" and
possibly a few things that go into "c:\program files".

I guess he didn't mention the hardware specs.

That was the entire response. It's also the *only* response I've seen
from a M$ employee.

----------------------------------------------------------------------
Warfley · 2023-09-29 16:02

C and C++ is very slow to compile full projects, which is why
buildsystems like make only compile changed files and include the
linker.

For example when I last worked on a large C++ project, compiling all
the project including the whole dependency chains (which included
building LLVM) would take 30 minutes on my PC with 32 gigs of RAM and
a 1. gen threadripper. On my Macbook air at the time it would take
multiple hours.
But once compiled only changed files need to be re-compiled, so as
long as you don't touch the headers, everything compiles in a minute
or so.

When people talk about the build times like MS with 16 hours, those
are the nightly clean builds. Of course during development you will
just compile deltas, and probably also always work on smaller tests
rather than always building the full system.

That said, I know of some game companies that write games in C++,
which always compile during their lunch breaks, to be able to test all
the new features they built in the morning then later in the
afternoon.

Some of this long compilation time is due to the C language design,
e.g. the usage of header files means as soon as you change one byte of
a header, you must recompile all files that include that header, while
Pascal with it's unit and ppu system is much better optimized (I think
since C++ got modules this should work similarly, but haven't used C++
for a while now). Thats why pretty much no other language uses the
include file system from C but most go with a namespace/module system
like Pascal Units.

But a very big factor is, as I said previously, simply that the C and
C++ compilers do more stuff under the hood.
So yes, C compilers are very slow, but a big reason for this is,
because they do a lot more things. Not all of those things the C
compiler does make sense in all situations, e.g. I would argue that
wasting whole hours of your day due to waiting compilation may not be
worth some additional optimizations you get.
C is made for kernel development and C++ is used for things like
browsers and low level applications. There you need all bit of
optimization you can get. But honestly, I'm not sure if that is really
worth it for pascal.

Many optimization problems are NP complete or even in non NP exp-time
(well optimization as a concept in general are not even computable in
the first place, only a few narrowly defined specific optimization
patterns can be implemented), so there is no way to make them very
fast. So not having them may be the better option when you aren't
building time critical software

----------------------------------------------------------------------
440bx · 2023-09-29 16:55

At least for me, compilation speed changes the way I program.

With Delphi and FPC, I do a full build every few lines of code,
sometimes as few as 1 or 2 lines, build, place a breakpoint on the new
code and execute under the debugger.  By the time I'm done, the amount
of testing left to do is often relatively small.  This is because,
even a 75,000 line program takes less than half a second to build
(and, by today's standards, my machine is slow - 2.8Ghz, 10+ year old
quad core)

When using C, it's a different ballgame, compiling 75,000 lines takes
more than 5 seconds and that's already enough to break the smooth flow
of edit/build/test.  Even a make in C usually takes longer than a full
build of the same (ported) project in FPC/Delphi.

One thing that should be stated is that, during development, it really
doesn't make much sense to build with deep optimizations since that
gets in the way of debugging (a debugger is an excellent
testing/verification tool.)

----------------------------------------------------------------------
Martin_fr · 2023-10-04 11:54

"Plugin" discussion moved:
https://forum.lazarus.freepascal.org/index.php/topic,64791.0.html

----------------------------------------------------------------------
runewalsh · 2023-11-12 21:38

Quote from: runewalsh on September 27, 2023, 11:42:56 amUntil the fix
in mid-2030s

I’m a pessimist on purpose so bug fixes can be pleasant surprises.