Discussion:
Case code pattern
(too old to reply)
Marco Borsari via fpc-devel
2018-08-13 15:20:52 UTC
Permalink
Hello,
I would need a clarification about the way the case statement is
translated into assembler by FPC. When the list of alternatives is
continous, does the compiler generate a jump table? And if yes, there is
some conditions for which a fall-through is performed anyway?
Thank you, Marco Borsari
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo
J. Gareth Moreton
2018-08-13 14:29:49 UTC
Permalink
I haven't explored it too deeply myself, but from what I understand, a
jump table is only generated if there are a large number of branches (over
50).  If it's just a handful of branches, it simply subtracts values from
the input corresponding to the differences between the case labels, and
jumping to the next subtraction if there's a mismatch, or to the else block
if it goes negative.  I'm not sure what it does for strings though.

Gareth aka. Kit

On Mon 13/08/18 16:20 , Marco Borsari via fpc-devel
fpc-***@lists.freepascal.org sent:
Hello,
I would need a clarification about the way the case statement is
translated into assembler by FPC. When the list of alternatives is
continous, does the compiler generate a jump table? And if yes, there is
some conditions for which a fall-through is performed anyway?
Thank you, Marco Borsari
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org [1]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[2]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel



Links:
------
[1] mailto:fpc-***@lists.freepascal.org
[2] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Marco Borsari via fpc-devel
2018-08-13 15:40:33 UTC
Permalink
Post by J. Gareth Moreton
I haven't explored it too deeply myself, but from what I understand, a
jump table is only generated if there are a large number of branches
(over 50). If it's just a handful of branches, it simply subtracts
values from the input corresponding to the differences between the case
labels, and jumping to the next subtraction if there's a mismatch, or to
the else block if it goes negative. I'm not sure what it does for
strings though.
Gareth aka. Kit
I see, I suspected the existence of a threshold value.
I am not interested in strings,
thank you, Marco

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists
Martok
2018-08-14 08:00:29 UTC
Permalink
Hi,
Post by Marco Borsari via fpc-devel
I would need a clarification about the way the case statement is
translated into assembler by FPC. When the list of alternatives is
continous, does the compiler generate a jump table?
What Kit said, but a correction: the threshold is not 50, it is 19. And what is generated is not technically a jump table, but a
typed dispatch table.
--
Regards,
Martok

Ceterum censeo b32079 esse sanandam.

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-de
Marco Borsari via fpc-devel
2018-08-14 09:27:09 UTC
Permalink
Post by Martok
What Kit said, but a correction: the threshold is not 50, it is 19. And what is generated is not technically a jump table, but a
typed dispatch table.
From what I can read from Wikipedia, every compound of the case is
enclosed in
a procedure (or in a function, as you said the table is typed), declared
with
nostackframe, and called by an array of index, right?

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fp
Martok
2018-08-14 10:37:58 UTC
Permalink
Post by Marco Borsari via fpc-devel
From what I can read from Wikipedia, every compound of the case is
enclosed in
a procedure (or in a function, as you said the table is typed), declared
with
nostackframe, and called by an array of index, right?
The blocks are just regular labels. What I meant was the jump array index is considered typed, which allows some optimizations.
This is noteworthy because FPC is the only compiler I could find that does that.


Roughly:
----------------------------------------------------------------------------------------
case x of
0: code;
1: Morecode;
2: EvenMoreCode;
//... assume we have enough case labels to get a jumptable
end;
----------------------------------------------------------------------------------------

Gets translated as if one had written:
----------------------------------------------------------------------------------------
label label0,label1,label2,{...,}afterend;
const table: array [lowestcaselabel..highestcaselabel] of CodePointer = (@label0, @label1, @label2{,...});
if (x<lowestcaselabel) or (x>highestcaselabel) then
goto @afterend;
goto table[x];
label0:
code;
goto afterend;
label1:
Morecode;
goto afterend;
label2:
EvenMoreCode;
{...}
afterend:
----------------------------------------------------------------------------------------

Iff it follows from the strong typing of the array index that the "if" at the start is always false for all defined values of
the type of x, it is omitted.
--
Regards,
Martok

Ceterum censeo b32079 esse sanandam.

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.
Marco Borsari via fpc-devel
2018-08-14 12:33:20 UTC
Permalink
Post by Martok
label label0,label1,label2,{...,}afterend;
if (x<lowestcaselabel) or (x>highestcaselabel) then
goto table[x];
code;
goto afterend;
Morecode;
goto afterend;
EvenMoreCode;
{...}
I did not aware about CodePointer type and its use in conjunction with
the goto, it is very useful, thank you.
But for compatibility with TP, I could need for a plain branch table, I
am writing a new mail in the other list...
Marco
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/

Marco Borsari via fpc-devel
2018-08-14 09:30:00 UTC
Permalink
Il 14/08/2018 10:00, Martok ha scritto:
array of index = array of pointers, sorry
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/
J. Gareth Moreton
2018-08-14 07:01:36 UTC
Permalink
I stand corrected - thanks.

*makes note to research more weird and wondeful things in the compiler!*

Gareth aka. Kit

On Tue 14/08/18 09:00 , Martok ***@martoks-place.de sent:
Hi,
Post by Marco Borsari via fpc-devel
I would need a clarification about the way the case statement is
translated into assembler by FPC. When the list of alternatives is
continous, does the compiler generate a jump table?
What Kit said, but a correction: the threshold is not 50, it is 19. And
what is generated is not technically a jump table, but a
typed dispatch table.

--
Regards,
Martok

Ceterum censeo b32079 esse sanandam.

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org [1]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[2]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel



Links:
------
[1] mailto:fpc-***@lists.freepascal.org
[2] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Loading...