Implement an SSA intermediate representation for the Solang compiler

Abstract

Solang is an open-source Solidity compiler written in Rust. It currently generates an intermediate representation in a Control Flow Graph (CFG) for each function in a Solidity contract during compilation. This project aims to implement a lower-level Static Single-Assignment (SSA) intermediate representation between the CFG and the LLVM-IR. The SSA representation will allow further optimizations during compilation, such as liveness analysis and partial redundancy elimination.

Mentor and Mentee

Mentor: Lucas Steuernagel

Mentee: Fanyi Zhao

Fork of official repository for this project: <https://github.com/fanyi-zhao/solang>

Deliverables

• The three-address code format: implement the data structure of the new three-address code format CFG.

• The three-address code format: Implement a text dump function for the new CFG. (+ unit tests)

• The three-address code format: Convert the old CFG into the new CFG of three-address codes. (+ unit tests)

• Implement SSA: insert phi functions into the new CFG. (+ unit tests)

• (Optional) Implement SSA: rename variables to generate SSA format. (+ unit tests)

Milestones

From 15 Sep 2023 to 22 Dec 2023.

Prepare

• 15 Sep 2023 - 20 Sep 2023 Learn Solidity syntax, Solang project structure, and Rust.

Evaluation 1

Due date: October 20th

• 20 Sep 2023 - 29 Sep 2023 The three-address code format: define the data structure of the new three-address code format CFG.
• 02 Oct 2023 - 11 Oct 2023 The three-address code format: Implement a text dump function for the new CFG. (+ unit tests)
• 11 Oct 2023 - 20 Oct 2023 The three-address code format: Convert the old CFG into the new CFG of three-address codes. (+ unit tests)

Evaluation 2 - Midterm

Due date: November 15th

• 26 Oct 2023 - 15 Nov 2023 PR Review & PR fixes.

Evaluation 3

Due date: December 1st

• 16 Nov 2023 - 08 Dec 2023 Implement SSA: insert phi functions into the new CFG. (+ unit tests)

Evaluation 4 - Final

Due date: December 22nd

• 11 Dec 2023 - 22 Dec 2023 PR Review & PR fixes.
• 11 Dec 2023 - 22 Dec 2023 (Optional) Implement SSA: rename variables to generate SSA format. (+ unit tests)

Methodology

Weekly check-ins to report project progress. Chat with Lucas on Discord for questions. Attend daily Solang meetups to report progress and ask questions.

Read the book "SSA-based Compiler Design" for a detailed explanation of all the algorithms required to implement SSA.

SSA-based Compiler Design

SSA-based Compiler Design