EGraph for RISC-V Assembly: Making Optimization More Declarative

Compilers and assemblers usually optimize through hand-written passes: pattern checks, ad hoc rewrites, and a lot of careful bookkeeping to avoid breaking correctness. In this project, I took a different route. I built an e-graph-based optimization module for RISC-V assembly in src/egraph/rvasm.rs, so assembly optimization can be expressed as rules instead of scattered special cases.

At a high level, the module treats assembly as a language that can live inside an equality saturation engine. That means equivalent forms are collected into the same equivalence classes, rewrites are applied until saturation, and the best version is chosen later by cost. The result is a more declarative pipeline: instead of encoding one fixed transformation path, the engine explores many possible forms and lets the extractor pick the best one.

The core design is simple but flexible. The assembly language is represented by two node types: individual instructions and whole program blocks. Instructions carry the original parsed assembly item, while program blocks hold sequences of e-class ids. That structure lets the engine reason about both local instruction-level equivalences and larger block-level composition.

The instruction node also defines the behavior that matters for optimization:

• Structural matching, so equivalent instructions can be recognized.
• A small cost model, so cheaper forms like add-immediate or add can be preferred appropriately.
• Display logic, so extracted results can be rendered back into readable assembly.

This is the foundation that makes the rest of the system work. Once assembly is expressed as a language inside the e-graph, it becomes possible to compare alternative forms without committing to a single rewrite path too early.

The main advantage of using an e-graph is that it keeps all equivalent variants available at once. For assembly, that matters because many optimizations are not strictly linear. A transformation like strength reduction can enable another simplification, and a later rewrite may expose an even better form. Traditional pass pipelines can miss those opportunities depending on pass ordering.

With the e-graph approach, those relationships are represented naturally. The module can explore transformations such as:

• rewriting multiplication by powers of two into shifts,
• simplifying instructions with neutral elements,
• handling conditional rewrites when analysis proves a property,
• generating dynamic rewrites based on matched values.

The module’s tests and demos show this style clearly in src/egraph/tests.rs and src/tests/test_egraph.rs, where the behavior is pinned down with concrete cases like constant folding, congruence merging, and rewrite scheduling.

Bringing the RISC-V Simulator into VS Code

One of the goals of my RiscV toolchain project has always been more than simply generating RISC-V assembly.

I want to build a complete toolchain that makes writing, compiling, and debugging RISC-V programs feel natural. This week, I reached another milestone: my RISC-V simulator can now debug programs directly inside Visual Studio Code.

Seeing breakpoints, registers, and single-step execution inside VS Code is surprisingly satisfying. It makes the project feel much closer to a real development environment.

 

Why a VS Code Debugger?

When developing a compiler, debugging generated assembly is just as important as generating it.

Previously, my workflow looked something like this:

1. Compile C source code.
2. Generate RISC-V assembly.
3. Run the simulator.
4. Print register values.
5. Repeat.

That works for small programs, but it quickly becomes painful as the compiler grows.

Having an interactive debugger completely changes the experience.

Instead of inserting print statements everywhere, I can now:

• set breakpoints
• single-step through instructions
• inspect registers
• follow the execution flow
• verify generated assembly interactively

It dramatically shortens the feedback loop when tracking down compiler bugs.

Using the Debug Adapter Protocol

Rather than inventing my own debugger UI, I decided to integrate with Visual Studio Code's Debug Adapter Protocol (DAP).

This means the extension can take advantage of the debugger interface that developers already know.

Currently the debugger supports:

• launching a RISC-V program
• breakpoints
• stepping through instructions
• viewing all integer registers
• inspecting the current execution point
• displaying the call stack

Because the simulator acts as the debugging backend, every instruction executed is under complete control of the debugger.

Connecting the Pieces

This project has gradually evolved into several independent components that now work together:

C Source

     │

     ▼

 C Compiler

     │

     ▼

RISC-V Assembly

     │

     ▼

Simulator

     │

     ▼

 VS Code Debugger

Each component was originally developed independently.

Connecting them together has been one of the most rewarding parts of the project.

When I hit F5 in VS Code, the debugger launches the simulator, loads the executable, and immediately allows me to step through the generated instructions.

That is a much nicer workflow than running individual command-line tools.

The Screenshot

The screenshot below shows the debugger paused on an instruction.

On the left, VS Code displays the complete register set.

On the right, the current instruction is highlighted while breakpoints are shown directly in the editor.

Watching the register values change after each instruction has already helped me identify several code-generation issues that would have been much harder to diagnose otherwise.

 

RisvV C Compiler Dev Journal - 20260804

72 Test Cases, typedef, and Function Pointers

Today I reached another milestone on my RISC-V C compiler project with Rust. The regression suite has now grown to 72 executable test cases, and this milestone adds support for two important C language features: typedef and function pointers.

I've been following a simple rule throughout this project: every new language feature must come with at least one regression test. This gives me confidence to continue improving the compiler without worrying about breaking functionality that was implemented earlier.

The compiler has gradually evolved from handling simple expressions into supporting a substantial subset of the C language. So far it includes:

• variables and arithmetic expressions

• if, while, and for

• functions and recursion

• pointers and pointer arithmetic

• arrays

• structures

• union

• enum

• typedef

• function pointers

Adding typedef

Although typedef does not introduce a new type, it is an important C language feature that allows programmers to create aliases for existing types.

Supporting typedef required extending the compiler's symbol table and type system so that type aliases could be correctly distinguished from ordinary identifiers and resolved during semantic analysis.

With typedef in place, complex declarations become much easier to read. This is especially important for function pointers, where the original C syntax can quickly become difficult to understand.

For example:

typedef int (*BinOp)(int, int);

is much cleaner than repeatedly writing the full function pointer declaration throughout a program.

Why Function Pointers?

Function pointers are one of the features that make C both flexible and powerful. They enable callbacks, dispatch tables, state machines, and many programming patterns commonly found in embedded software, operating systems, and low-level libraries.

Supporting function pointers required more than just parsing a complicated declaration. The compiler now needs to correctly handle:

• function pointer type resolution

• assignments between functions and function pointer variables

• indirect function calls

• passing function pointers as parameters

• returning function pointers from functions

• function pointers stored inside arrays and structures

Test Case #72

To validate both typedef and function pointer support, I created a regression test that combines several real-world usage patterns into a single program.

The test covers:

• a typedef for a function pointer type

• multiple arithmetic callback functions

• an array of function pointers

• passing function pointers as parameters

• returning a function pointer from another function

• storing function pointers inside a structure

• indirect function calls through variables, arrays, and structure members

The test program defines several operations (add, sub, mul, and negate_via) and exercises different ways of invoking them through function pointers.

The expected final result is 42, which becomes the regression check for the entire feature set.

This type of test is especially valuable because it validates the interaction between multiple compiler components:

• parsing

• type resolution

• semantic analysis

• function call generation

• memory layout handling

• RISC-V code generation

A More Stable Foundation

One thing I've noticed during recent development is that segmentation faults have become much less common.

Earlier in the project, adding a new language feature often exposed issues deep inside the compiler. These problems usually came from assumptions that were valid when the compiler was smaller but became incorrect as more language features were introduced.

Recently, the development process has changed. Most of my effort is now spent adding new capabilities and expanding test coverage rather than debugging compiler crashes.

I believe this is a sign that the compiler framework itself is becoming more stable. The internal architecture, type system, and regression framework are mature enough to support continued growth.

There are still many bugs to discover, but it is encouraging to see the project moving from "building the foundation" toward "expanding capabilities."

Growing the Regression Suite

The compiler now includes 72 executable regression tests, and this number has become more meaningful than simply counting implemented features.

Every bug I fix becomes a permanent regression test.

Every new language feature adds another executable example.

Over time, the regression suite is becoming a living specification of what the compiler supports.

This approach also makes future optimization work safer because I can quickly verify that improvements do not break existing functionality.

What's Next?

With many core C language features now implemented, including struct, union, enum, typedef, and function pointers, the next phase of development will focus on improving compiler maturity in two areas.

The first area is expanding floating-point support. The compiler already has basic floating-point functionality, and the next step is to add more comprehensive regression tests covering more complex scenarios, including floating-point expressions, conversions, function calls, and interactions between integer and floating-point types.

The goal is not only to make floating-point programs compile, but also to build confidence that the generated RISC-V code behaves correctly across a wider range of real-world cases.

The second area is optimization. Up to this point, the primary focus has been correctness, language coverage, and compiler stability. With the framework becoming more mature and the regression suite growing, the next challenge is improving the quality of generated code.

Future optimization work will explore areas such as:

• improving generated instruction sequences

• reducing unnecessary operations

• peephole optimization

• intermediate representation improvements

• exploring more advanced compiler optimization techniques

This marks an important transition for the project: moving from:

"Can the compiler correctly compile C programs?"

toward:

"Can the compiler generate efficient RISC-V code?"

I'm looking forward to this next stage of the journey.