The_Fuzion_Intermediate_Representation.pdf

Fuzion is a new language targeting safety-critical systems by building on few but powerful concepts and enabling static analysis of applications to verify their correctness. The Fuzion Intermediate Representation (FUIR) plays a key role in providing a basis for static analysis tools as well as interpreters and code generators that produce runnable programs.

FUIR has a number of aspects that are different from most other intermediate representations: Code is grouped into Fuzion features that are a common abstraction for functions, classes, types, etc. There are only 10 commands used in FUIR, calls to intrinsic features are used for operations not present as explicit commands. There is no support for loop or conditional jumps, recursion is used instead. The usual distinction between stack frames and heap instances does not exist in the FUIR.

This work-in-progress paper will give a quick overview of the Fuzion language and explain the aspects of the FUIR in more detail before presenting the impact it has on the tools processing the FUIR code.

1. The Fuzion Intermediate Representation
An IR for static analysis for safety-critical systems

Fridtjof Siebert, Michael Lill
Tokiwa Software GmbH
VMIL’24, October 20, 2024, Pasadena, CA, USA

2. VMIL’24: The Fuzion Intermediate Representation2/33
Overview
➡ Fuzion quick intro
➡ Safety-Critical Aspects
➡ Toolchain and Static Analysis
➡ The Fuzion IR
➡ Status

3. VMIL’24: The Fuzion Intermediate Representation3/33
Overview
➡ Fuzion quick intro
➡ Safety-Critical Aspects ➡ Toolchain and Static Analysis ➡ The Fuzion IR ➡ Status

4. VMIL’24: The Fuzion Intermediate Representation4/33
Fuzion Intro
➡ One concept: a feature
➡ - generalization of class / method /
➡ - function / etc.
➡ - may be nested
➡ statically typed
➡ polymorphic: union types, parametric types, inheritance
➡ pure using effects
hello_world ! io.out =>
io.out.println "hello!"
hello_world

5. VMIL’24: The Fuzion Intermediate Representation5/33
Overview
➡ Fuzion quick intro
➡ Safety-Critical Aspects ➡ Toolchain and Static Analysis ➡ The Fuzion IR ➡ Status

6. VMIL’24: The Fuzion Intermediate Representation6/33
Safety-Critical Aspects
➡ Formal Guidelines (DO178C, IEC61508, ISO26262, etc.)
➡ Rigorous Verification and Validation
➡ Determinism
- bounded worst-case execution time
- real-time GC or static memory management
- no probabilistic algorithms
➡ Fuzion: simple IR enables tool support

7. VMIL’24: The Fuzion Intermediate Representation7/33
Overview
➡ Fuzion quick intro
➡ Safety-Critical Aspects
➡ Toolchain and Static Analysis ➡ The Fuzion IR ➡ Status

8. VMIL’24: The Fuzion Intermediate Representation8/33
Fuzion Toolchain and Static Analysis
Fuzion
source
Front
end
Middle
end
Fuzion
IR
Analyzer
Optimizer
JVM
backend
.class
.c
Fuzion
module
C
backend
Inter-
preter
JVM

9. VMIL’24: The Fuzion Intermediate Representation9/33
Fuzion Toolchain and Static Analysis
Fuzion
source
Front
end
Middle
end
Fuzion
IR
Analyzer
Optimizer
JVM
backend
.class
.c
Fuzion
module
C
backend
Inter-
preter
JVM

10. VMIL’24: The Fuzion Intermediate Representation10/33
Fuzion Toolchain and Static Analysis
Fuzion
source
Front
end
Middle
end
Fuzion
IR
Analyzer
Optimizer
JVM
backend
.class
.c
Fuzion
module
C
backend
Inter-
preter
JVM
Static analysis for Modules
➡local correctness
➡supply chain security

11. VMIL’24: The Fuzion Intermediate Representation11/33
Fuzion Toolchain and Static Analysis
Fuzion
source
Front
end
Middle
end
Fuzion
IR
Analyzer
Optimizer
JVM
backend
.class
.c
Fuzion
module
C
backend
Inter-
preter
JVM

12. VMIL’24: The Fuzion Intermediate Representation12/33
Fuzion Toolchain and Static Analysis
Fuzion
source
Front
end
Middle
end
Fuzion
IR
Analyzer
Optimizer
JVM
backend
.class
.c
Fuzion
module
C
backend
Inter-
preter
JVM
Create whole program
➡monomorphization
➡dead-code removal
➡...

13. VMIL’24: The Fuzion Intermediate Representation13/33
Fuzion Toolchain and Static Analysis
Fuzion
source
Front
end
Middle
end
Fuzion
IR
Analyzer
Optimizer
JVM
backend
.class
.c
Fuzion
module
C
backend
Inter-
preter
JVM

14. VMIL’24: The Fuzion Intermediate Representation14/33
Fuzion Toolchain and Static Analysis
Fuzion
source
Front
end
Middle
end
Fuzion
IR
Analyzer
Optimizer
JVM
backend
.class
.c
Fuzion
module
C
backend
Inter-
preter
JVM
Whole program analysis
➡no run-time errors
➡specialization
➡escape analysis /
stack allocation
➡instrumentation, test
generation, etc.
➡...

15. VMIL’24: The Fuzion Intermediate Representation15/33
Fuzion Toolchain and Static Analysis
Fuzion
source
Front
end
Middle
end
Fuzion
IR
Analyzer
Optimizer
JVM
backend
.class
.c
Fuzion
module
C
backend
Inter-
preter
JVM

16. VMIL’24: The Fuzion Intermediate Representation16/33
Overview
➡ Fuzion quick intro
➡ Safety-Critical Aspects ➡ Toolchain and Static Analysis
➡ The Fuzion IR ➡ Status

17. VMIL’24: The Fuzion Intermediate Representation17/33
The Fuzion IR

18. VMIL’24: The Fuzion Intermediate Representation18/33
The Fuzion IR: Runtime Features
➡ Set of runtime features

19. VMIL’24: The Fuzion Intermediate Representation19/33
The Fuzion IR: Runtime Features
➡ Set of runtime features of the kinds
➡ - routine
➡ - abstract
➡ - field
➡ - choice
➡ - intrinsic
➡ - native

20. VMIL’24: The Fuzion Intermediate Representation20/33
The Fuzion IR: Runtime Features
➡ Set of runtime features of the kinds
➡ - routinetype
➡ - abstract
➡ - field
➡ - choicetype
➡ - intrinsic
➡ - native

21. VMIL’24: The Fuzion Intermediate Representation21/33
The Fuzion IR: Runtime Features
➡ Set of runtime features of the kinds
➡ - routinetypecallable
➡ - abstract callable
➡ - field callable
➡ - choicetype
➡ - intrinsic callable
➡ - native callable

22. VMIL’24: The Fuzion Intermediate Representation22/33
The Fuzion IR: Runtime Features
➡ Set of runtime features of the kinds
➡ - routinetypecallablehas code
➡ - abstract callable
➡ - field callable
➡ - choicetype
➡ - intrinsic callable
➡ - native callable

23. VMIL’24: The Fuzion Intermediate Representation23/33
The Fuzion IR: Code

24. VMIL’24: The Fuzion Intermediate Representation24/33
The Fuzion IR: Code
➡ Stack machine

25. VMIL’24: The Fuzion Intermediate Representation25/33
The Fuzion IR: Code
➡ Stack machine
➡ Only 10 commands
➡ - Call
➡ - Assign
➡ - Tag / Match
➡ - Box, Env, Current, Const, Pop, Comment

26. VMIL’24: The Fuzion Intermediate Representation26/33
The Fuzion IR: Code
➡ Stack machine
➡ Only 10 commands
➡ - Call
➡ - Assign
➡ - Tag / Match
➡ - Box, Env, Current, Const, Pop, Comment

27. VMIL’24: The Fuzion Intermediate Representation27/33
The Fuzion IR: Code
➡ Stack machine
➡ Only 10 commands
➡ - Call
➡ - Assign
➡ - Tag / Match
➡ - Box, Env, Current, Const, Pop, Comment

28. VMIL’24: The Fuzion Intermediate Representation28/33
The Fuzion IR: Code
➡ Stack machine
➡ Only 10 commands
➡ - Call
➡ - Assign
➡ - Tag / Match
➡ - Box, Env, Current, Const, Pop, Comment

29. VMIL’24: The Fuzion Intermediate Representation29/33
The Fuzion IR: Code
➡ Stack machine
➡ Only 10 commands
➡ - Call
➡ - Assign
➡ - Tag / Match
➡ - Box, Env, Current, Const, Pop, Comment

30. VMIL’24: The Fuzion Intermediate Representation30/33
The Fuzion IR: Code
➡ Stack machine
➡ Only 10 commands
➡ - Call
➡ - Assign
➡ - Tag / Match
➡ - Box, Env, Current, Const, Pop, Comment
➡ Intrinsics for arithmetic, runtime system, etc.

31. VMIL’24: The Fuzion Intermediate Representation31/33
Overview
➡ Fuzion quick intro
➡ Safety-Critical Aspects ➡ Toolchain and Static Analysis ➡ The Fuzion IR
➡ Status

32. VMIL’24: The Fuzion Intermediate Representation32/33
Fuzion: Status
Fuzion still under development
➡ language definition stabilizing
➡ base library work in progress
➡ current implementation providing JVM and C backends
➡ basic analysis tools available
➡ greencode.ai project starting now

33. VMIL’24: The Fuzion Intermediate Representation33/33
Thank you. Any questions?
Please follow and stay informed
➡ https://github.com/tokiwa-software/fuzion
➡ https://fuzion-lang.dev
➡ @FuzionLang
➡ @[email protected]