Hi guys,

So I'm still experimenting and researching with the deep optimiser, and I'm starting to have some successes... until I found a compiler bug!

https://bugs.freepascal.org/view.php?id=33794

What I'm trying to do, and something which I'd like to try out with the regular peephole optimiser at some point, is using a sorted list that maps an assembler command to a handler procedure and using a binary search to find the correct routine.  This will speed up the optimiser from O(n) (i.e. the speed of "case X of") to O(log n) per line of code, where n is the different number of assembler commands it has to deal with, but the compiler produces incorrect code with the algorithm I'm using, and triggers an internal error if -O3 is specified.  A trimmed down sample project is attached with the ticket.

Even if the deep optimiser is an unstable, unusable failure, I found a bug anyway!

Gareth aka. Kit

Yes, you found a bug... in your own code. See my note at the bug report.

Regards,
Sven

FPC knows different means to generate code for case statements (linear list, jump table, jump tree); based on a heuristics the method is chosen. If in case of the assembler optimizer, FPC chooses the wrong approach, this heuristics should be checked, see e.g. compiler/ncgset.pas:1170+:

{ value has been determined on an i7-4770 using a random case with random values if more values are known, this can be handled depending on the target CPU

Testing on a Core 2 Duo E6850 as well as on a Raspi3 showed also, that 64 is a good value }
else if labelcnt>=64 then
genjmptree(labels)
else

  genlinearlist(labels);

The label count if a jmp tree is beneficial, is surprisingly high, probably due to branch prediction which breaks completely havoc in case of a jump tree.

I stand corrected. Sorry to waste your time on that.

Gareth aka. Kit

On Sun 27/05/18 08:31 , Sven Barth via fpc-devel
sent:
Am 27.05.2018 um 02:48 schrieb J. Gareth Moreton:
Hi guys,

So I'm still experimenting and researching with the deep optimiser, and I'm starting to have some successes... until I found a compiler bug!

https://bugs.freepascal.org/view.php?id=33794 [1]

What I'm trying to do, and something which I'd like to try out with the regular peephole optimiser at some point, is using a sorted list that maps an assembler command to a handler procedure and using a binary search to find the correct routine.  This will speed up the optimiser from O(n) (i.e. the speed of "case X of") to O(log n) per line of code, where n is the different number of assembler commands it has to deal with, but the compiler produces incorrect code with the algorithm I'm using, and triggers an internal error if -O3 is specified.  A trimmed down sample project is attached with the ticket.

Even if the deep optimiser is an unstable, unusable failure, I found a bug anyway!

Yes, you found a bug... in your own code. See my note at the bug report.

Regards,
Sven

That's some interesting insight - thanks Florian. Something that might need rigorous timing tests in that case.  I thought about the binary search map since the case statements jump to a procedure call, and I wondered if I could take advantage of that homogenuity.  In the meantime, I found a couple of peephole optimisations that don't rely on tricky code like that in the bug report! I'll submit a patch later, just in case I find a few more.

Gareth aka Kit.

On Sun 27/05/18 13:00 , Florian Klämpfl sent:

J. Gareth Moreton wrote

Hi guys, So I'm still experimenting and researching with the deep optimiser, and

I'm starting to have some

regular peephole optimiser

at some point, is using a sorted list that maps an assembler command to

a handler procedure and

using a binary search to find the correct routine.  This will speed up

the optimiser from O(n) (i.e.

the speed of "case X of") to O(log n) per line of code,

FPC knows different means to generate code for case statements (linear list, jump table, jump tree);
based on a heuristics the method is chosen. If in case of the assembler optimizer, FPC chooses the
wrong approach, this heuristics should be checked, see e.g. compiler/ncgset.pas:1170+:

{ value has been determined on an i7-4770 using a random case with random values
if more values are known, this can be handled depending on the target CPU

Testing on a Core 2 Duo E6850 as well as on a Raspi3 showed also, that 64 is
a good value }
else if labelcnt>=64 then
genjmptree(labels)
else
genlinearlist(labels);

The label count if a jmp tree is beneficial, is surprisingly high, probably due to branch prediction
which breaks completely havoc in case of a jump tree.