Hi all,

as we have discovered in 0033576 and 0033614, there is a bug somewhere in the loop unroll optimization pass that only appears in complex enough code. The problem is, it doesn't happen in the single testsuite test, and the observable crashes in Lazarus are caused by memory corruption at some point unrelated to the crash, so it's hard to debug (at least on Windows, without rr...).

I have one other project that has sporadic crashes with -OoLOOPUNROLL (I wish I had figured that out back then), but that is about as difficult as Lazarus, where it's at least 100% reproducible.

Does anyone have more complete test cases, or maybe smaller affected projects?

How big is the project? Normally, the number of unrolled loops is reasonable small so comparing the generated assembler with and without unrolling should be feasible.

I think I found something, see below. Answering the question first ;-)

Florian Klämpfl wrote

How big is the project? Normally, the number of unrolled loops is reasonable small so comparing the generated assembler with and without unrolling should be feasible.According to cloc, 40kLOC, 10kLOC of which are DSP code, not counting packages

that are not in the source repo. With the very spurious crashes, not the best test case...

I did, however, do the insane thing and diff Lazarus (or rather, IDAs output). There are a lot of unrolled loops in the LCL alone, but the code reordering for the first 15% or so that I checked looks fine. {Off-Topic: could parts of that variable rewriting be used for more aggressive inlining?}

Some more testing with Lazarus and -gt has shown that at some variables are uninitialized with -Ooloopunroll. There is a fairly common case where removing the variable is not good:
-------------
for Result:= alow to ahigh do

  if Something(Result) then exit;

-------------
If that gets unrolled, Result is undefined, and whatever it gets assigned to receives the random content of r/eax.

I'm 90% sure that global variables and the Result variable are *not* supposed to be undefined after the loop (in contrast to Delphi-compatible locals), but can't seem to find a reference for that. This pattern is used all over the place, so somebody else must have thought so too? Grepping for "for result:=" over the FPC source tree gives 10 matches, Lazarus has over 100 results.

Test case:
-------------
{$Optimization LOOPUNROLL}

var
  i : integer;
  s : single;
function tfun: integer;
begin
  for Result:=1 to 10 do
    s:=s+1;
end;
begin
  s:=0.0;
  for i:=1 to 2 do
    s:=s+1;
  if i  2 then
    halt(1);
  i:= tfun();
  if i  10 then
    halt(2);
  if s  12 then
    halt(3);
  writeln('ok');
end.
-------------

I would very much expect that to be the main cause of the observed crashes.

Thanks for the analysis!

There are a lot of unrolled loops in the LCL alone, but the code reordering for the first 15% or so that I checked looks fine. {Off-Topic: could parts of that variable rewriting be used for more aggressive inlining?}

No. Inlining does variable rewriting. If something is not inlined, there are other reasons.

ISO7185: "After a for-statement is executed, other than being left by a goto-statement, the control-variable shall be undefined"

http://docwiki.embarcadero.com/RADStudio/Tokyo/en/Declarations_and_Statements_(Delphi)#For_Statements: "After the for statement terminates (provided this was not forced by a Break or an Exit procedure), the value of counter is undefined."

So this shall not be unrolled, but is still error prone, if Result is not set after the regular end of the for loop.

This might get unrolled, Result as result is undefined after the loop.

Same documentation for FPC, <https://www.freepascal.org/docs-html/ref/refsu58.html>

But, someone clearly explicitly thought otherwise at some point: <https://svn.freepascal.org/cgi-bin/viewvc.cgi/trunk/compiler/aasmcnst.pas?view=markup#l860> That warning is only "wrong" if Result is well-defined after exiting the loop.

So this shall not be unrolled, but is still error prone, if Result is not set after the regular end of the for loop.

Am I doing something wrong, or does FPC not emit a warning when a loop variable is read after the loop? Delphi has a warning, and does indeed display it for the test case. There is no indication anything might be wrong from FPC?

This kind of code is used even more than "that other thing", makes me wonder if it's a good idea to break this at O3...

Martok wrote

If that gets unrolled, Result is undefined, and whatever it gets assigned to receives the random content of r/eax.

<snip>

Grepping for "for result:=" over the FPC source tree gives 10 matches, Lazarus has over 100 results.

Can you report that to the bugtracker of Lazarus?

Bart

Martok wrote

Same documentation for FPC, <https://www.freepascal.org/docs-html/ref/refsu58.html> But, someone clearly explicitly thought otherwise at some point:

Sometime ago, fpc behaved strange in case of for loops and dfa, so it might have been that the compiler even didn't recognize that result is always initialized in the body or whatever.

No, still on my todo list.

This kind of code is used even more than "that other thing", makes me wonder if it's a good idea to break this at O3...

-O3 probably "breaks" a lot of code which exploits the limits of a language-

What I've gathered is that with the following routine:

 function DoSomething: Integer;
 begin
   for Result:=alow to ahigh do
    if Something(Result) then exit;
 end;

The issue occurs if "Something(Result)" always returns False and the for-loop exits normally.  While some languages and compilers will consistently set Result to "ahigh + 1" after the last cycle, this is not the case with Free Pascal, hence Result is undefined and the last value of R/EAX (which may or may not be False from the last call to "Something") becomes the function return.

I'm not certain, but at the very least, if the variable used in the for-loop is still live afterwards (that is, it's read from before being written to again), a compiler warning should be thrown.  If this already happens, then it might need to be modified to handle Result as a special case.

Gareth aka. Kit

Can you report that to the bugtracker of Lazarus?

Sure. Done as https://bugs.freepascal.org/view.php?id=33753

Martok

Florian Klämpfl wrote

-O3 probably "breaks" a lot of code which exploits the limits of a language-

True.

I do wonder if it would be good to create some sort of collection of things that are undefined in the core language and how different compilers and dialects handle them. It's been 28 years, there's probably consensus on some out there. Could be useful as a guide for porting code as well.

Martok

[...]

Apparently this mail thread confuses some users:
report https://bugs.freepascal.org/view.php?id=33753:

To avoid misunderstandings:
The above clearly says, that using break/goto/exit is safe:

  for Result:=low to high do
    if Something(Result) then exit;
  for Result:=low to high do
    if Something(Result) then break;
  Something(Result);

OTOH this is not safe:

Mattias

In our previous episode, Mattias Gaertner said:

Well, well, clearly. One could interpret it that it says that the for statement terminates naturally if not forced by break or exit. It doesn't say what happens with break or exit.

The fact that this exception is not documented with an example makes it very ambiguous IMHO.

Sometimes I feel that FPC developers are more lawyers than programmers.

The fact that this exception is not documented with an example makes it very ambiguous IMHO.

Your very own documentation isn't ambiguous at all, though: https://www.freepascal.org/docs-html/ref/refsu58.html#x164-18600013.2.4 [^]

Citation: "If the loop was terminated prematurely with an exception or a break statement, the loop variable retains the value it had when the loop was exited."

Ondrej

If the value of counter is undefined no matter what, then you would not bother writing the exception in the brackets, wouldn't you?

The fact that this exception is not documented with an example makes it very ambiguous IMHO.

I found a dozen places in the VCL using this.
For Result:=...do if ... then exit;

Mattias

Lawyers or not, well-defined behaviour can only be a good thing for a language.  As for those code snippets in the VCL and the like, unless we want to change the rule so that the for-loop counter has a distinct value afterwards, Result should be explicitly set after the for loop (presumably people want "High + 1").

What's the easiest solution to this? Change the code or change the rule?

Gareth aka. Kit
 

On Fri 18/05/18 12:46 , Mattias Gaertner sent:

[...] > > "After the for statement terminates (provided this was not forced by

a Break or an Exit procedure), the value of counter is undefined."

[...] Well, well, clearly. One could interpret it that it says that the for statement terminates naturally if not forced by break or exit. It

doesn't

say what happens with break or exit.

If the value of counter is undefined no matter what, then you would not bother writing the exception in the brackets, wouldn't you?

The fact that this exception is not documented with an example makes it

very

ambiguous IMHO.

 I found a dozen places in the VCL using this.
 For Result:=...do if ... then exit;

Mattias

That looks sensible. Sorry to waste your time on this.  I'm glad it states the for-loop variable will be left undefined - that's good enough documentation for me.

I wouldn't call it a quick fix... more of fixing an oversight, since I can see the trick of using Result as the for-counter being very easily overlooked.  Of course, the perfect fix is only counting "exitn" if the for-loop counter is Result.  One to test for later.

Gareth aka. Kit

On Fri 18/05/18 14:40 , Martok sent:

Citation: "If the loop was terminated prematurely with an exception or a break statement, the loop variable retains the value it had when the loop was exited."

As a quick fix, not unrolling loops left with exit at least fixes this specific
situation. This still leaves exceptions raised, but IIRC the handlers don't
restore context anyways, we might be okay?

diff --git a/compiler/optloop.pas b/compiler/optloop.pas index 46039ffc5a..dc714ea2cc 100644
--- a/compiler/optloop.pas
+++ b/compiler/optloop.pas
@@ -76,7 +76,7 @@ unit optloop;

 function checkbreakcontinue(var n:tnode; arg: pointer): foreachnoderesult;
 begin
 - if n.nodetype in [breakn,continuen] then
 + if n.nodetype in [breakn,continuen,exitn] then
 result:=fen_norecurse_true
 else
 result:=fen_false;

I'll be running this on today's snapshot, see if anything else remains.

J. Gareth Moreton wrote

What's the easiest solution to this? Change the code or change the rule?

Follow consensus. There's little point in ignoring 30 years of language development, just because nobody started an ISO committee.

In this case: """After a for-statement is executed, other than being left by a goto-statement, the control-variable shall be undefined""" Break/continue/exit wasn't even invented then!

Borland extended this, hence the VCL samples mentioned.

But that is a discussion I have wasted a lot of time on once already, no intention to do that again.

Citation: "If the loop was terminated prematurely with an exception or a break statement, the loop variable retains the value it had when the loop was exited."

As a quick fix, not unrolling loops left with exit at least fixes this specific situation. This still leaves exceptions raised, but IIRC the handlers don't restore context anyways, we might be okay?

diff --git a/compiler/optloop.pas b/compiler/optloop.pas index 46039ffc5a..dc714ea2cc 100644
--- a/compiler/optloop.pas
+++ b/compiler/optloop.pas
@@ -76,7 +76,7 @@ unit optloop;

     function checkbreakcontinue(var n:tnode; arg: pointer): foreachnoderesult;
       begin
-        if n.nodetype in [breakn,continuen] then
+        if n.nodetype in [breakn,continuen,exitn] then
           result:=fen_norecurse_true
         else
           result:=fen_false;

I'll be running this on today's snapshot, see if anything else remains.

Apologies, I meant it was undefined if the loop exits normally, but retains its current value if terminated prematurely.  Ah well!

Admittedly I do like concrete rules, and any situations where something is undefined is explicitly stated.  Hopefully we can put this one to bed now!  Back to more exciting research and ventures.

Gareth aka. Kit

On Fri 18/05/18 15:33 , Martok sent:

Sorry to waste your time on this.

Don't worry, I like investigating this stuff. I don't like the rule-lawyering
that usually follows ;-)

I'm glad it states the for-loop variable will be left undefined - that's

good enough documentation for me.
It is *not* undefined when the loop is left with break or exit, that's the

point. The ISO is not a very good reference for modern-ish Pascal.

Sorry to waste your time on this.

Don't worry, I like investigating this stuff. I don't like the rule-lawyering that usually follows ;-)

I'm glad it states the for-loop variable will be left undefined - that's good enough documentation for me.

It is *not* undefined when the loop is left with break or exit, that's the point. The ISO is not a very good reference for modern-ish Pascal.

"
I think based on both documented and observed behaviour, the following definition would be appropriate:

The for-loop variable is undefined after the loop if the loop ran to completion. It retains its last value if the loop exited in a controlled way (goto, break, exit, ?) before running to completion. "

I'm happy with that, although it might be best to simply say (goto, break etc.) since it's hard to be completely exhaustive (since there's raise and continue as well), and let's just hope that someone doesn't call a function that then performs a long jump to a completely different routine!

For purposes of compiler optimisation, I would argue that, internally, 'exit' is only necessary to check if the for-loop variable is Result, but that's just nit-picking.  I'm in two minds with 'raise' because it's not always easy to determine where the exception is raised (e.g. in a subroutine called by the for-loop, or triggered by an interrupt signal such as a segmentation fault), and I wouldn't call it exiting the loop in a controlled way.

Gareth aka. Kit.

Martok schrieb am Fr., 18. Mai 2018, 15:40:

Maybe it should also check for goto and at least explicit raise statements?

Regards,
Sven

It is *not* undefined when the loop is left with break or exit, that's the point. The ISO is not a very good reference for modern- ish Pascal.

I think based on both documented and observed behaviour, the following definition would be appropriate:

The for-loop variable is undefined after the loop if the loop ran to completion. It retains its last value if the loop exited in a controlled way (goto, break, exit, ?) before running to completion.

The ISO standard basically listed all known "controlled" ways to exit the loop before it ran to completion. It's just that in the meantime other flow control methods have been added.

In our previous episode, Mattias Gaertner said:

I would not try to interpret an ambiguous line, and look for alternate sources of info.

Seems that those are there, so that is case closed, and the only possible outcome is to try to disable certain optimizations for FOR statements that have multiple exit points or adapt the optimizations.

To keep in annoying detail mode:

   for result:=0 to 3 do
     if x(result) then
       exit(result)

...is yet another case since the exit(result) could be taken as an explicit assignment of the loopvar to an location outside the loop, after which the loopvar scope ends.

Sven Barth wrote

Maybe it should also check for goto and at least explicit raise statements?

That'd be adding goton and raisen to the check, right?

For now, just checking exit seems to be enough to get rid all of the easily testable Lazarus crashes. The "Optimized IDE" profile is usable again. I'll post the patch to the bug tracker, as we seem to have decided it is not a hack ;-)

It is a yet another case of what?

AFAICS the above code throws a compiler error: Illegal assignment to for-loop variable "$result" - and that is correct because you assign a value to a loop variable within a loop.

BTW. it's the same as:
function Test: Integer;
begin
   for Result := 1 to 10 do
     Exit(5);
end;

gives a compiler error as well, since you assign 5 to loop variable within a loop.

The Exit; (without argument) doesn't assign anything - it should just exit the current function without touching any of the variables.

Ondrej

[...] The for-loop variable is undefined after the loop if the loop ran to completion. It retains its last value if the loop exited in a controlled way (goto, break, exit, ?) before running to completion.

You forgot the case where the loop was not entered:

for i:=2 to 1 do ;

i is now undefined.

Same for

for i in emptyset do ;

Mattias

Both are cases of "the loop run to completion". Just because "completion" resulted in zero executions of the loop contents doesn't change that.

Thorsten Engler wrote

The for-loop variable is undefined after the loop if the loop ran to completion. It retains its last value if the loop exited in a controlled way (goto, break, exit, ?) before running to completion.

speaking from the peanut gallery, FWIW, i like that verbiage... it is straight forward and clear to understand...

I added raise, exit, goto and label as well.

To make it unambiguous: the value of the counter variable of a for-loop is well-defined after interrupting the for-loop using exit or break, also in FPC.

Jonas

Florian Klämpfl wrote

I added raise, exit, goto and label as well.

Oh, label, right.

I'd say #0033614 can be resolved as "fixed in 39083" and #0033753 as "no change required" then.

Well there is still something left:

program LoopUnrollTest;
procedure Test;
var
   I: Integer;
   procedure Test2;
   begin
     Writeln(I);
   end;
begin
   for I := 1 to 10 do
     Test2;
end;
begin
   Test;
end.

Ondrej

Unless I'm missing something, that could be unrolled without any problems.  The only problem that could occur is if Test2 raises an exception (which, as the name implies, is an exceptional situation) or it jumps outside of the procedure, which can only realistically occur in some compiler optimisations (e.g. CALL [routine]; RET is optimised to JMP [routine]).  Exit is not a problem here because it will simply exit Test2 and stay within the for-loop.

Gareth aka. Kit

change

required" then.

Well there is still something left:

 program LoopUnrollTest;
 procedure Test;
 var
   I: Integer;
   procedure Test2;
   begin
     Writeln(I);
   end;
 begin
   for I := 1 to 10 do
     Test2;
 end;
 begin
   Test;
 end.

Ondrej

In that example, I would logically expect an infinite loop.  Realistically, I'm not sure, because you're literally trying to trick the compiler with a construct like that (which all testers should do!) - that one could be fun to test!

Gareth aka. Kit

On Mon 21/05/18 19:43 , Florian Klämpfl sent:

"no change

What do you expect? That it just works? If yes, what about

 program LoopUnrollTest;
 procedure Test;
 var
 I: Integer;
 procedure Test2;
 begin
 Writeln(I);
 I:=1;
 end;
 begin
 for I := 1 to 10 do
 Test2;
 end;
 begin
 Test;
 end.

?

What do you expect? That it just works? If yes, what about

program LoopUnrollTest;
procedure Test;
var
  I: Integer;
  procedure Test2;
  begin
    Writeln(I);
    I:=1;
  end;
begin
  for I := 1 to 10 do
    Test2;
end;
begin
  Test;
end.

?

Florian Klämpfl wrote

What do you expect?

That it writes a sequence from 1 to 10 to console. Instead, it writes 10 times "-1431655766".

That it just works?

Please define what you understand with "it just works". (If you agree with me on the sequence from 1 to 10, my answer is yes.)

In this (your) case I don't expect anything - it is one of FPC's favorites "undefined behaviour" because as documented, it is not allowed to change the loop variable value within a for loop.

In my case (without the I:=1 assignment) I don't change the loop
variable value - it is absolutely valid to read from it.

Ondrej

Ondrej Pokorny wrote

Well there is still something left:

You are right, variables don't correctly get captured (or rather, don't get captured at all). This is not good.
Dirty fix: only unroll loops over local variables when there are no nested procs. But that probably prohibits most useful cases as well...

I'd say that closures + AST-level inlining + some dead store eliminations would fix a lot of issues that currently have special case handling.

Ondrej Pokorny wrote

In this (your) case I don't expect anything - it is one of FPC's favorites "undefined behaviour" because as documented, it is not allowed to change the loop variable value within a for loop.

Yes, just asking :)

In my case (without the I:=1 assignment) I don't change the loop variable value - it is absolutely valid to read from it.

I have fixed this.

Very good, thank you!

Ondrej