Computed goto

[BeniBela]

Does fpc has anything like a computed goto for fast switch statements like C?

[Fungus]

You can use labels:

Code: Pascal  [Select][+][-]

1. program test;
2. label MYLABEL;
3. begin
4.   MYLABEL:
5.   //Do something forever
6.   goto MYLABEL;
7. end;

[Thaddy]

The case statement is equivalent to switch in about 99% of all cases. There are small differences that can be mitigated. The generated code is about as efficient as in other languages. Differences are often compiler dependent in the sense that some compilers for a given language outperform other compilers.

In the case of a case statement: design with care and use continue to evaluate the rest of a case loop. Doesn't work..

[marcov]

It is a bit strange since most embedded compilers convert not very dense switch statements with consecutive values to jumptables anyway.

The one where I first noticed this was a GCC derived one even.

So the gain of this is not speed, but not having to manually configure the optimization compiler. (or maybe his architectures backend doesn't do jumptables).

Anyway, if you want the compiler to generate jumptables for case statements, work on the  compiler's optimization to generate jumptables, this kind of abusing already dodgy functionality is not the way:

• taking the address of labels is not clean and complicates can confuse optimization
• the fall through switch of C is ugly to begin with
• the order is fixed by the numerical values of the opcodes

The last one requires some explanation; one of the known disadvantages of jumptables is that the order is fixed by the order of the numeric opcode-values. On architectures where the relative jump is more optimal AND short you want the most used opcodes first, so that they use the cheap branch instruction to jump back, and the more rarely used ones at the end can use abs jumps.

BUT then you don't want the compiler to reorder your switch/case :-)

[Thaddy]

BUT then you don't want the compiler to reorder your switch/case :-)

That's what the late Bob Zale did in TurboBasic and PowerBasic.
That's what Delphi claims as an optimization...by default...

And if I understood correctly that is also what FPC does or wants (since many years) and hence that the continue is not allowed? Ordering a case loop is normal.
I know of evil ways to circumvent it.... Ok, it is almost Halloween,....

[skalogryz]

Speaking of Halloween 

Trick or Treat!

Code: Pascal  [Select][+][-]

1. program project1;
2. {$mode delphi}
3.  
4. procedure GotoAddr(p: Pointer); nostackframe;assembler;
5. asm
6.   pop ecx;
7.   jmp p;
8. end;
9.  
10. procedure Test;
11. label
12.   a1, a2;
13. var
14.   p1,p2: Pointer;
15.   i : integer;
16.   k : integer;
17. begin
18.   i:=1;
19.   k:=0;
20.   p1:=@a1;
21.   p2:=@a2;
22.   a1:
23.   i:=2;
24.   writeln(i);
25.   a2:
26.   i:=3;
27.   writeln(i);
28.   if k=0 then begin
29.     inc(k);
30.     GotoAddr(p1);
31.   end;
32.   writeln(PtrUInt(p1));
33.   writeln(PtrUInt(p2));
34. end;
35.  
36.  
37. begin
38.   test;
39. end.
40.  

works fine for fpc 2.6.4

[skalogryz]

so lets implement the VM from the article

Code: Pascal  [Select][+][-]

1. program project1;
2. {$mode delphi}
3.  
4. procedure GotoAddr(p: Pointer); nostackframe;assembler;
5. asm
6.   pop ecx;
7.   jmp p;
8. end;
9.  
10. function interp_cgoto(code: PChar; initval: integer): integer;
11. { The indices of labels in the dispatch_table are the relevant opcodes }
12. label
13.   do_halt, do_inc, do_dec, do_mul2, do_div2, do_add7, do_neg;
14. var
15.   pc: integer;
16.   vl: integer;
17.   dispatch_table: array [0..6] of pointer;
18.  
19.   procedure dispatch; inline;
20.   var
21.     p : integer;
22.   begin
23.     p:=pc;
24.     inc(pc);
25.     GotoAddr(dispatch_table[byte(code[p])]);
26.   end;
27.  
28. begin
29.   pc:=0;
30.   vl:=initval;
31.  
32.   dispatch_table[0]:=@do_halt;
33.   dispatch_table[1]:=@do_inc;
34.   dispatch_table[2]:=@do_dec;
35.   dispatch_table[3]:=@do_mul2;
36.   dispatch_table[4]:=@do_div2;
37.   dispatch_table[5]:=@do_add7;
38.   dispatch_table[6]:=@do_neg;
39.  
40.   DISPATCH();
41.   while true do begin
42.     do_halt: begin
43.       Result:=vl;
44.       Exit;
45.     end;
46.  
47.     do_inc:
48.       inc(vl);
49.       DISPATCH();
50.     do_dec:
51.       vl:=vl - 1;
52.       DISPATCH();
53.  
54.     do_mul2:
55.       vl := vl * 2;
56.       DISPATCH();
57.  
58.     do_div2:
59.       vl := vl div 2;
60.       DISPATCH();
61.  
62.     do_add7:
63.       vl := vl + 7;
64.       DISPATCH();
65.  
66.     do_neg:
67.       vl := -vl;
68.       DISPATCH();
69.   end;
70. end;
71.  
72. function interp_cgoto_str(const code: string; initval: integer): integer;
73. begin
74.   if code='' then Result:=initval
75.   else begin
76.     Result:=interp_cgoto(@code[1], initval);
77.   end;
78. end;
79.  
80. const
81.   OP_HALT    = #$00;
82.   OP_INC     = #$01;
83.   OP_DEC     = #$02;
84.   OP_MUL2    = #$03;
85.   OP_DIV2    = #$04;
86.   OP_ADD7    = #$05;
87.   OP_NEG     = #$06;
88.  
89. var
90.   res : integer;
91.  
92. begin
93.   res:=interp_cgoto_str( OP_NEG + OP_MUL2 + OP_INC + OP_ADD7 + OP_HALT, -1 );
94.   writeln(res); // should result with 10
95. end.
96.  

and I don't want to make any benchmarks

[howardpc]

Code: Pascal  [Select][+][-]

1. asm
2.   pop ecx;
3. end;

gives Error: Asm: [pop reg32] invalid combination of opcode and operands
on 64-bit Linux

What would be the 64-bit equivalent ... or is some other compiler directive or setting required?

[Fungus]

gives Error: Asm: [pop reg32] invalid combination of opcode and operands
on 64-bit Linux

What would be the 64-bit equivalent ... or is some other compiler directive or setting required?

Code: Pascal  [Select][+][-]

1. pop rcx;

[skalogryz]

gives Error: Asm: [pop reg32] invalid combination of opcode and operands
on 64-bit Linux

What would be the 64-bit equivalent ... or is some other compiler directive or setting required?

Code: Pascal  [Select][+][-]

1. pop rcx;

Well, there's the chance you'll break it, since RCX is the first parameter passed for x64 calling-convention.
(Thus you actually erase the address you want to jump to, with the returning address. So the code will work as if no GotoAddr is called).
(RCX for x64 is like EAX for x86 delphi's(FPC) fast call)

So I'd recommend to try

Code: [Select]

pop rdx
instead.

Note, I wrote this code only to show that "fpc has something like that".
If you ask me, I'd strongly oppose to such kind of practice.

Any low-level "jumps" should be taken care by the compiler and not by the code... unless you're writing a low level code (i.e. a driver or something).

[Fungus]

LOL that would explain why some of my assembly code refuses to work in 64bit

[BeniBela]

Well, there's the chance you'll break it, since RCX is the first parameter passed for x64 calling-convention.
(Thus you actually erase the address you want to jump to, with the returning address. So the code will work as if no GotoAddr is called).
(RCX for x64 is like EAX for x86 delphi's(FPC) fast call)

Actually the address is in rdi.

Althought it worked without that line. It messes up rsp, but it seems only rbp is used and in the end it moves rdp to rsp.

Note, I wrote this code only to show that "fpc has something like that".

It shows assembly has it, not fpc.

But GotoAddr is not inlined. It is a call/pop/jmp, when it should be a jmp.

Any low-level "jumps" should be taken care by the compiler and not by the code... unless you're writing a low level code (i.e. a driver or something).

I write an interpreter.

If I would use assembly, I could write just as well write a compiler.

[skalogryz]

It shows assembly has it, not fpc.

It shows that pascal allows to return an address of a label, which is the most important feature needed to implement the "computed goto"

[Thaddy]

It shows assembly has it, not fpc.

It shows that pascal allows to return an address of a label, which is the most important feature needed to implement the "computed goto"

Correct.
and Benibela:
Yeah, way out of tune... It also doesn't work for arm,,,,

What's the problem writing an interpreter btw? Everybody can do that or has done that at any given point in time. You are a bit late given your background....

[BeniBela]

Perhaps the best solution is   a macro:

Code: [Select]

{$define dispatch:=p := dispatch_table[byte(code[p])]; inc(pc); asm jmp p; end }


What's the problem writing an interpreter btw? Everybody can do that or has done that at any given point in time. You are a bit late given your background....

An interpreter is where this matters, when every instruction moves through that case statement, even if it is only becomes 1% faster.

I have finished the interpreter with a virtual method call for each expression. Now I am trying to make it faster. Turns out, a case statement with multiple cases is much slower than a virtual method call. Without computed goto, it could not become faster