Masterball

Masterball, an elaborate Mx* Compiler. Passed all testcases in Online Judge.

Actually, it is a toy compiler for course project. Therefore, many implementations are quite simple and there may be some bugs.

It will compile Mx* language (a language for this project) code to RISC-V 32 Integer assembly.

It is implemented in Java, JDK 11. And the lexer and parser in the FrontEnd are supported by antlr v4 framework.

---

Development:

Language:

Status:

Sub-Project:

---

Usage

run this compiler by

$ java -jar Masterball (...args)

see the help doc by run compiler with -h argument

$ java -jar Masterball -h

Feature

• High Performance. Close to gcc O2 (with some testcases surpass). Average store: 98.45.

  

• Standard LLVM implemented. (validated by llc)

• Elegant Design in many parts.

• Some syntactic sugar implemented. (e.g. for (int i=1; i<=n; i++))

• Errors and Warnings System.

• DarkSword (a LLVM-IR virtual machine with experimenting Just-In-Time compilation.)

Pitfall

• The load part of GVN. The correctness is not sure.
• backend/optim/TRO. May cause too long assembly.
• Induction Variable can do better. (even can calculate 1+2+...+n).
• use simple Liveness Analysis in Alias Analysis may work better. (but actually not too much)

Mx*

Mx* or MxStar is a language designed for this course.

The grammar is defined in AssignmentRequirement

a simple syntax highlight for this language: see hightlight/

Design

• Masterball Architecure

graph TD
A[src: .mx file]
B[ParseTree]
C[AST]
D[IR]
E[optimized IR]
F[Assembly]
G[optimized Assembly]
H[.ast file]
I[.ll file]
J[.ll file]
K[.s file]
A ==FrontEnd:Antlr v4==> B
B ==FrontEnd:ASTBuilder==>C
C ==MiddleEnd:IRBuilder==>D
D ==MiddleEnd:Optimizer==>E
E ==BackEnd:AsmBulder==>F
F ==BackEnd:Optimizer==>G
C ==FrontEnd:ASTPrinter==>H
D ==MiddleEnd:IRPrinter==>I
E ==MiddleEnd:IRPrinter==>J
G ==MiddleEnd:AsmPrinter==>K

Loading

• Optimizer

graph LR
A[IR]
B[IR]
C[IR]
D[IR]
E[IR]
F[IR]
G[IR]
H[IR]
I[IR]
J[IR]
K[IR]
L[IR]
M[IR]
N[optimized IR]
A ==Glo2Loc==> B
B ==Mem2Reg==> C
C ==Func Inliner==> D
D ==CFGSimplifier==> E
E ==GVN==> F
F==SCCP==> G
G==ADCE==> H
H==IVTrans==> I
I==LICM==> J
J==LocalMO==> K
K ==Forced Func Inliner==> D
K ==SSA Destructor==> L
L ==TRO==> M
M ==InstAdapter==> N

Loading

Masterball Project contains three main parts.

• masterball compiler package masterball.compiler
  • core of the project, consists of FrontEnd, MiddleEnd and BackEnd.
  • receive the input stream from console and emit the assembly.
• masterball console package masterball.console
  • provides a simple CLI for the user / online judge.
  • parse the arguments and control the compiler.
  • simple help document and version information.
• masterball log package masterball.debug
  • some debug kits for the developer of this compiler (=me)

Click the following links to read the project design in detail.

• General Design
• Grammar Design
• FrontEnd Design
• MiddleEnd Design
• BackEnd Design
• Register Allocation Algorithm

The optimizations Masterball uses:

• Optimization

TO DO

FrontEnd (Semantic Check)

• .g4
• AST Design
• Scope & Registry
• AST Builder
• Semantic Checker
• Data Oriented Debug

MiddleEnd (IR Builder)

• IR Design (LLVM IR)
• Type, Constant, Inst, Hierarchy
• Skeleton, can generate my first IR
• Type System
• IR Builder (before MEM2REG)
• IR debug (use clang-llvm tools)

BackEnd (ASM)

• SSADestructor (without MEM2REG phi nodes are all simple)
• ASM Design (RISCV-32I)
• Inst, Operand, Hierarchy
• ASMBuilder
• RegisterAlloca (GraphColoring)
• Debug (ok... it will take me a long time)

MiddleEnd (Optimizer)

• Mem2Reg
• SSA Destructor
• CFG Simplifier
• SCCP
• Glo2Loc
• ADCE
• Function Inliner
• Induction Variable Strength Reduction
• GVN or CSE
• LICM
• TCO & TRO
• Local MO
• Inst Adapter
• Unrolling