[UPDATE] SedaiBasic - SSA pipeline, native AOT/JIT backends, and what changed

[mau.camma]

I posted about SedaiBasic in this forum (https://forum.lazarus.freepascal.org/index.php/topic,72593.msg568516.html) some time ago.
Enough has changed since then that a new thread makes more sense than reviving the old one.

What's new, in short: the interpreter is no longer the only execution mode. There is now a full compilation pipeline, lexer -> parser -> AST -> SSA intermediate representation -> optimization passes (GVN, LICM, algebraic simplification, register allocation via backward dataflow liveness) -> register-based bytecode, and two native backends emitting x86-64 directly with no external assembler or linker. AOT compiles the whole program at load; the JIT compiles loop regions. They can be combined.

The code generator uses typed register banks (int/float/string) resolved statically in SSA, so there is no tagging, boxing or runtime type checking in the hot path. Machine registers are allocated over GPR r9-r15 and xmm2-7.

Where that lands, n-body from the Computer Language Benchmarks Game, 1M iterations, on an old i7-3630QM: bytecode interpreter 9.8s, AOT 0.86s, JIT 0.80s, AOT+JIT 0.77s. CPython 3.14 runs the same program in 16.8s. FreeBASIC -O2 is 0.196s for execution alone and 0.466s including its compilation step; compared over the full pipeline, which is the fair comparison since SedaiBasic compiles at load, the gap is currently under 2x.

Language coverage has also moved: roughly 90% compatibility with BASIC v7, 84% with the FreeBASIC dialect. The graphical console now abstracts over SDL2 (including KMSDRM) and there's a clean-room SID emulator verified against VICE-generated reference audio.

Two FPC-specific findings from the recent work, which may be more useful here than the benchmark table:

Managed types in hot recursive functions are brutal. My SSA value record carried three string fields, and the code generation entry point had several dozen locals. FPC's prologue/epilogue zeroing and RTTI finalization came to roughly 24 µs per call against 0.25 µs of actual work in the function body. Two orders of magnitude of pure frame overhead, invisible to any reasoning about the algorithm, found only by bisection profiling. A fast path with no managed locals cut SSA generation from 16.1ms to 5.2ms on a const-heavy module.

On the other side, the strictness of the type system caught a class of IR construction errors at compile time that would have been silent memory corruption elsewhere. Writing a compiler backend in Pascal turned out to be considerably more comfortable than I expected.

Questions welcome on any part of it, particularly the SSA lowering and register allocation, which is where most of the work went.

Released under GNU GPL v3.

Develop branch: https://github.com/camauri/SedaiBasic2/tree/develop

[440bx]

I haven't looked at it in detail which is something I eventually intend to do but, it looks very interesting, particularly its mixed architectural output (VM and full binary.)

Thank you for sharing.

[BildatBoffin]

nice work 👏

[LemonParty]

A big bunch of technologies used in this project.
Was it hard to implement JIT? And how many lines of code take JIT?
Nice work.

[mau.camma]

Was it hard to implement JIT? And how many lines of code take JIT?

Not many lines, a lot of weeks. And the most expensive lines are the invisible ones. 

[Mike.Cornflake]

This looks fun :-)  Many thanks

[mau.camma]

SedaiBasic compiled to WebAssembly

I'm building a WebAssembly target for SedaiBasic. The compiler emits WASM straight from its own SSA. No external toolchain, no interpreter shipped to the browser.
In the screenshot: the voxel landscape demo, written in BASIC, running inside Firefox.
HTML+JS+WASM is about 32 KB.

It's not perfect, but it's a good start.


Online demo: https://www.sedai.it/demo/voxel_landscape.html

Demo sources: https://github.com/camauri/SedaiBasic2/tree/main/bas/demo

Repository: https://github.com/camauri/SedaiBasic2

[Gigatron]

I'ts really awesome , will try it soon , thank you very much !

[mau.camma]

SedaiBasic vs Python vs Lua — Computer Language Benchmarks Game
(see attached table)

Execution times are in milliseconds, using the best of three runs, with the standard input sizes from the Computer Language Benchmarks Game.

The "tipo" column indicates the dominant data type in the benchmark’s hot loop.

The four central columns are the SedaiBasic2 engines: interpreter, AOT compiler, JIT, and AOT+JIT.
The fastest time in each row is shown in bold.

The last two columns show the ratio between the reference time and SedaiBasic’s best time:
🟢 above 1 means SedaiBasic is faster
🔴 below 1 means SedaiBasic is slower

Python 3 and Lua 5.4 are used as references.
Lua is the official benchmark interpreter, not LuaJIT.

The numbers are what they are.
Some are very good.
Others are definitely not.
But not for long!

[srvaldez]

how to compile SdaiBasic ?
I download the Git repo SedaiBasic2-develop, cd to the extracted folder an issue:
powershell -ExecutionPolicy Bypass -File .\setup.ps1
after accepting the default choices it finally says

Code: [Select]

Free Pascal compilers found on this machine:
  1) FPC 3.2.2    D:\dev3\SedaiBasic2-develop\fpc\3.2.2\bin\x86_64-win64\fpc.exe   [cannot compile - skipped]
  2) FPC 3.3.1    D:\dev3\FPC-unleashed-main\fpc\bin\x86_64-win64\fpc.exe   [cannot compile - skipped]

ERROR: none of them can compile a trivial program.
An install without a usable fpc.cfg is the usual cause.

      [ERROR] Compilation failed

======================================================================

  SETUP FAILED!

  Please check the error messages above.

======================================================================
both fpc compilers work just fine, so what's the problem?

[Thausand]

both fpc compilers work just fine, so what's the problem?

please have tell mau.camma where is locate you fpc 3.2.2 and fpc 3.3.1 (path full). Then may be mau.camma is realize what is mistake in build-script. When have normal fpc installation then script is not find fpc correct. In default build-script is only find fpc in sedai directory and script is demand version number directory and platform directory. That is not work for most person (windows and linux).

[srvaldez]

perhaps the setup failed is that SedaiBasic won't compile as is
if I open SedaiBasicVM.lpr in Lazarus and try to build I get 2 errors in RunTemplate.inc

RunTemplate.inc
JitArrDescCache := nil;
RunTemplate.inc(98,3) Error: Identifier not found "JitArrDescCache"

ArrDescPtr := AcquireArrDescFast(JitArrDescCache);
RunTemplate.inc(265,40) Error: Identifier not found "JitArrDescCache"


if I comment-out those two lines then SedaiBasic builds

[mau.camma]

First of all: I'm sorry for the slow reply. I've been buried in SedaiBasic development and I simply can't keep up with all the social channels and forums in decent time. That's on me, not on you, and thank you both for taking the trouble to report this.

A lot has changed in the project recently. The most significant one for you: the interpreter's hot dispatch loop is now written in C (src/hotdisp.c), compiled separately and linked into the VM. It's worth 27 to 45% wherever it applies, and it's also the direct cause of one of the two problems below.

We're also reworking the setup so that it downloads all the dependencies automatically, GCC included, in an ultra compact build: 18.5 MB instead of the 247 MB of a full MinGW-w64 distribution, because the build only ever needs the compiler proper and never the linker. Updates will land on GitHub as soon as they're ready, and I'll announce them here.

If it's not a problem for you, opening an issue on GitHub will get you a much faster answer than a forum thread. That's where I actually look every day.

Now, the two reports.

---

The JitArrDescCache errors in RunTemplate.inc. That was a real bug, and it's already fixed. Your line numbers (98 and 265) pin your copy to a single commit from 20 August: a variable was declared inside a {$IFDEF HOT_C} block while being used from code outside it. HOT_C is defined by build.ps1 and build.sh (which also compile and link the C file), never by the Lazarus project file, so building from the IDE was exactly the configuration that broke. That's why none of us hit it. It was fixed the next day, so just pull develop again.

One thing worth knowing: building from Lazarus works, but the resulting binary has no C hot loop. build.ps1 on Windows and build.sh on Linux and macOS are the supported paths, because they compile hotdisp.c and link it in.

The "none of them can compile a trivial program" setup failure. The verdict was probably right, and the script was unhelpfully hiding the reason: it was throwing away the compiler's own error message. That's fixed, and it now prints it underneath each [cannot compile - skipped] line.

The usual cause is a missing or unusable fpc.cfg, and the symptom is confusing precisely because the compiler works fine in Lazarus: the IDE supplies its own unit paths and never reads fpc.cfg, while a plain shell invocation does. You can check in ten seconds. Put begin end. in probe.pas and run fpc probe.pas. If you get Fatal: Can't find unit system used by Program, that's it. Generate a config with:

<fpcroot>\bin\x86_64-win64\fpcmkcfg.exe -d basepath=<fpcroot> -o <fpcroot>\bin\x86_64-win64\fpc.cfg

Pull develop first, though, because the script will now tell you directly instead of making you guess.

---

Thanks again to both of you. Reports like these are how the awkward corners get found: the second one had been broken for anyone building outside our own scripts, and we had no way of knowing.

[Thausand]

@mau.camma
I not home and not can use account github for report.

I make try compile sedai basic manual.

This is work when compile sb, sbc and sbd (I not have make work for compile vision sbv because I have need more work for all dependency).

When try compile web (sbw) when use command:

Code: [Select]

fpc \
  -B -Mobjfpc \
  -Xs -XX -O1 \
  -Fu"/repo\*/src" -Fu"units" \
  -FU"units" \
  -FE"bin" \
  -dWEB_MODE \
  -o"sbw" \
  repo/SedaiBasic2-develop/src/SedaiBasicWeb.lpr
command is assume output unit directory (no lib) and dependency is extract directory repo. I not include option for have avx and optimize (not important for make work compile)

then is error:

Code: Bash  [Select][+][-]

1. ...
2. Compiling ./repo/SedaiBasic2-develop/src/SedaiTerminalIO.pas
3. SedaiBytecodeVM.pas(3450,24) Warning: Comparison might be always true due to range of constant and expression
4. SedaiBytecodeVM.pas(3475,24) Warning: Comparison might be always true due to range of constant and expression
5. SedaiBytecodeVM.pas(3481,29) Warning: Comparison might be always true due to range of constant and expression
6. SedaiBytecodeVM.pas(3483,29) Warning: Comparison might be always true due to range of constant and expression
7. SedaiBytecodeVM.pas(3486,30) Warning: Comparison might be always true due to range of constant and expression
8. SedaiBytecodeVM.pas(3518,24) Warning: Comparison might be always true due to range of constant and expression
9. SedaiBytecodeVM.pas(3537,29) Warning: Comparison might be always true due to range of constant and expression
10. SedaiBytecodeVM.pas(3540,29) Warning: Comparison might be always true due to range of constant and expression
11. SedaiBytecodeVM.pas(3543,30) Warning: Comparison might be always true due to range of constant and expression
12. SedaiBytecodeVM.pas(4462,8) Note: Local variable "i" not used
13. SedaiBytecodeVM.pas(5304,80) Warning: Symbol "faHidden" is not portable
14. SedaiBytecodeVM.pas(7543,3) Note: Local variable "i" not used
15. SedaiBytecodeVM.pas(7753,32) Note: Call to subroutine "operator :=(const source:Variant):Int64;" marked as inline is not inlined
16. SedaiBytecodeVM.pas(7754,45) Note: Call to subroutine "operator :=(const source:Variant):Double;" marked as inline is not inlined
17. SedaiBytecodeVM.pas(8537,48) Note: Call to subroutine "operator :=(const source:Int64):Variant;" marked as inline is not inlined
18. SedaiBytecodeVM.pas(8539,43) Note: Call to subroutine "operator :=(const source:Double):Variant;" marked as inline is not inlined
19. SedaiBytecodeVM.pas(8541,51) Note: Call to subroutine "operator :=(const source:AnsiString):Variant;" marked as inline is not inlined
20. SedaiBytecodeVM.pas(8563,40) Note: Call to subroutine "operator :=(const source:Variant):Double;" marked as inline is not inlined
21. SedaiBytecodeVM.pas(8574,41) Note: Call to subroutine "operator :=(const source:Variant):AnsiString;" marked as inline is not inlined
22. SedaiBytecodeVM.pas(9146,10) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
23. SedaiBytecodeVM.pas(9149,10) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
24. SedaiBytecodeVM.pas(9152,10) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
25. SedaiBytecodeVM.pas(9194,10) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
26. SedaiBytecodeVM.pas(9199,10) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
27. SedaiBytecodeVM.pas(9205,12) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
28. SedaiBytecodeVM.pas(9233,10) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
29. SedaiBytecodeVM.pas(9239,10) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
30. SedaiBytecodeVM.pas(9255,17) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
31. SedaiBytecodeVM.pas(9255,67) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
32. SedaiBytecodeVM.pas(9274,12) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
33. SedaiBytecodeVM.pas(9274,59) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
34. SedaiBytecodeVM.pas(9421,12) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
35. SedaiBytecodeVM.pas(9443,10) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
36. SedaiBytecodeVM.pas(9444,10) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
37. SedaiBytecodeVM.pas(9459,10) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
38. SedaiBytecodeVM.pas(9466,10) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
39. SedaiBytecodeVM.pas(9468,12) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
40. SedaiBytecodeVM.pas(9476,10) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
41. SedaiBytecodeVM.pas(9478,12) Note: Call to subroutine "function TBytecodeVM.ArrayBoundsOK(ArrayIdx:LongInt;LinearIdx:LongInt):Boolean;" marked as inline is not inlined
42. SedaiBytecodeVM.pas(9551,23) Warning: Comment level 2 found
43. SedaiBytecodeVM.pas(10318,38) Note: Call to subroutine "function TBytecodeVM.ActiveCtx:TExecutionContext;" marked as inline is not inlined
44. SedaiBytecodeVM.pas(10339,38) Note: Call to subroutine "function TBytecodeVM.ActiveCtx:TExecutionContext;" marked as inline is not inlined
45. SedaiBytecodeVM.pas(11690,71) Warning: Comment level 2 found
46. RunTemplate.inc(935,48) Error: duplicate case label
47. RunTemplate.inc(935,48) Error: duplicate case label
48. SedaiBytecodeVM.pas(13221,24) Warning: Comparison might be always false due to range of constant and expression
49. SedaiBytecodeVM.pas(13530,24) Warning: Comparison might be always true due to range of constant and expression
50. SedaiBytecodeVM.pas(13552,23) Warning: Comparison might be always true due to range of constant and expression
51. SedaiBytecodeVM.pas(16276,25) Warning: Comparison might be always true due to range of constant and expression
52. SedaiBytecodeVM.pas(16296,25) Warning: Comparison might be always true due to range of constant and expression
53. SedaiBytecodeVM.pas(16311,23) Warning: Comparison might be always true due to range of constant and expression
54. SedaiBytecodeVM.pas(16314,11) Warning: unreachable code
55. SedaiBytecodeVM.pas(16360,23) Warning: Comparison might be always true due to range of constant and expression
56. SedaiBytecodeVM.pas(16363,11) Warning: unreachable code
57. SedaiBytecodeVM.pas(16396,23) Warning: Comparison might be always true due to range of constant and expression
58. SedaiBytecodeVM.pas(16399,11) Warning: unreachable code
59. SedaiBytecodeVM.pas(16492,25) Warning: Comparison might be always true due to range of constant and expression
60. SedaiBytecodeVM.pas(16512,25) Warning: Comparison might be always true due to range of constant and expression
61. SedaiBytecodeVM.pas(16528,25) Warning: Comparison might be always true due to range of constant and expression
62. SedaiBytecodeVM.pas(16543,25) Warning: Comparison might be always true due to range of constant and expression
63. SedaiBytecodeVM.pas(16562,23) Warning: Comparison might be always true due to range of constant and expression
64. SedaiBytecodeVM.pas(16572,23) Warning: Comparison might be always true due to range of constant and expression
65. SedaiBytecodeVM.pas(16585,25) Warning: Comparison might be always true due to range of constant and expression
66. SedaiBytecodeVM.pas(16641,25) Warning: Comparison might be always true due to range of constant and expression
67. SedaiBytecodeVM.pas(16659,25) Warning: Comparison might be always true due to range of constant and expression
68. SedaiBytecodeVM.pas(16696,27) Warning: Comparison might be always true due to range of constant and expression
69. SedaiBytecodeVM.pas(16696,89) Warning: unreachable code
70. SedaiBytecodeVM.pas(16710,25) Warning: Comparison might be always true due to range of constant and expression
71. SedaiBytecodeVM.pas(17736) Fatal: There were 2 errors compiling module, stopping
72. Fatal: Compilation aborted
73. Error: ppcx64 returned an error exitcode
74.  

Have note: duplicate case label.

This was work some day ago and is not work now.

[mau.camma]

@Thausand

Thank you for the report.
It was a real bug, and it is fixed now.

What it was. In src/SedaiOpcodeTable.pas the constant DENSE_WEB_BASE was 415. But group 7 (sprites) is 17 slots wide, so it already owns 399..415. The web group therefore started one slot inside the sprite group, and the two ranges in the dispatch case collided — that is your duplicate case label. It only shows with -dWEB_MODE, which is why sb, sbc and sbd all built fine for you.

You are right that it worked before: the constant had been wrong for some time, and nothing noticed, because none of my test nets ever compiled a WEB_MODE build. That is my fault.

What changed. The opcode map is now written as one number per group — its size — and every base is derived by adding them up, so the two branches can no longer drift apart. I also gave sbw a --verify-opcodes option, which self-checks the table and exits 1 if it is wrong:

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

1. sbw --verify-opcodes

And since I had the file open, I closed an old limitation. sbw dates back to when SedaiBasic only had the CLASSIC (Commodore) dialect, so it forced every script through the Commodore rules. I had been meaning to lift that for a while, and this was the occasion. sbw now also supports MODERN (the FreeBASIC-compatible dialect), and it picks the dialect from the source by itself, exactly like sb and sbc: line numbers → CLASSIC, no line numbers → MODERN. The preprocessor (#define, #if, #include, #macro) also runs in .wbas files now.

I measured it: 250 MODERN programs served by sbw, compared against sb on the same source. Before, 224 matched and 15 crashed. Now 238 match and none crash. (The rest are programs printing timings, plus a few that use graphics or joystick keywords, which are excluded from the web build on purpose.)

Also, if a script fails to compile, sbw --verbose now prints the real reason in the log instead of just "Access violation".

Please treat sbw as experimental. It is the least exercised of my targets, and you may still hit problems — if you do, please report them the same way, it helps.

I will keep developing the web side. My goal is for it to become a proper option in place of PHP or Python for this kind of work. It is not there yet, but that is the direction.

The fix is on develop and main (commit 706e56a). Your fpc command line is fine as it is.