Xi Compiler

A compiler for the Xi programming language.

Getting Started

Before you get started, you may want to be running in the VM described below. Once you have that set up, read on!

This repository comes with a spiffy Makefile that can build code, run tests, generate documentation and more. All the libraries you need to build and run code are also packaged with this repository, so make should "just work" right out of the box.

Command	Action
make clean	Removes all the garbage generated by compilation.
make src	Compiles all src and test code.
make test	Executes all JUnit tests in test.
make doc	Generates Javadoc documentation into doc.
make publish	Publishes OCaml code coverage online.
make	Executes all of the above commands.

After you run make src, you can execute our compiler's main executable: xic, which is actually just a dirt simple shell script that invokes the Java runtime on our compiler's compiled .class files.

OCaml dependencies

If you don't want to use the VM, you can also download all the dependencies yourself.

opam install core async ounit ocamlgraph bisect bisect_ppx

Flags

• Miscellaneous
  • --help
  • --report-opts
• Modes
  • --lex: a/b/foo.xi --> a/b/foo.lexed
  • --parse: a/b/foo.xi --> a/b/foo.parsed
  • --typecheck: a/b/foo.xi --> a/b/foo.typed
  • --tcdebug: same as --typecheck
  • --nolower: same as --irgen
  • --lower: same as --irgen
  • --irgen: a/b/foo.xi --> a/b/foo.ir
  • --optir (initial|final): a/b/foo.xi --> a/b/foo_<f>_<phase>.ir
    • lexical and syntactic errors are written to a/b/foo.optir
    • type errors are written to a/b/foo_<phase>.ir
  • --optcfg (initial|final): a/b/foo.xi --> a/b/foo_<f>_<phase>.dot
    • all errors are written to a/b/foo.dot
  • : a/b/foo.xi --> a/b/foo.s
  • --asmdebug: same as
• Options
  • -sourcepath <path> [default: dir where xic run]
    • -sourcepath a/b c/d/foo.xi: a/b/c/d/foo.xi --> c/d/foo._
    • -sourcepath a/b /c/d/foo.xi: a/b/c/d/foo.xi --> /c/d/foo._
  • -libpath <path> [default: dir where xic run]
  • -D <path> (diagnostic files) [default: dir where xic run]
    • -D a/b/ c/d/foo.xi: c/d/foo.xi --> a/b/c/d/foo._
    • -D a/b/ /c/d/foo.xi: c/d/foo.xi --> /c/d/foo._
    • -sourcepath 0/1/ -D a/b/ /c/d/foo.xi: 0/1/c/d/foo.xi --> a/b/c/d/foo._
  • -d <path> (asm files) [default: dir where xic run]
    • same as -D
  • -target linux
  • -O<opt>, -O-no-<opt>, -O

    • -O<opt> and -O-no-<opt> are mutually exclusive. If you set a -O<opt> flag and also a -O-no-<opt>, the compiler will exit with error.

    • If a -O<opt> or -O-no-<opt> flag is set, -O is ignored.

    • Here's a case analysis of all possible flag combinations.

      -O<opt>	-O-no-<opt>	-O	Behavior
      n	n	n	all flags
      n	n	y	no flags
      y	n	_	only -O<opt> flags
      n	y	_	only -O-no-<opt> flags
      y	y	_	error

Optimizations

We support a bunch of optimization flags, but some are aliases for others. For example, cse and pre are aliases. Here is an example of how aliases work.

Flags	PRE performed?
-cf	no
-cf -cse	yes
-cf -pre	yes
-cf -pre -cse	yes
-O-no-cf -O-no-cse	no
-O-no-cf -O-no-pre	no
-O-no-cf -O-no-pre -O-no-cse	no

Here is a list of all the optimizations we support:

Flag	Name	Alias
acf	AST Constant Folding
icf	IR Constant Folding
reg	Register Allocation
mc	Move Coalescing	reg
cp	Constant Propagation
uce	Unreachable Code Elimination	cp
pre	Partial Redundancy Elimination
cse	Common Subexpression Elimination	pre
licm	Loop Invariant Code Motion	pre
is	Good Instruction Selection

Here is how optimization flags interact with different modes:

Mode	Flags Used	Extension
--lex	none	.lexed
--parse	none	.parsed
--typecheck	acf	.typed
--tcdebug	acf	.typeddebug
--nolower	acf, icf	.nolower
--lower	acf, icf, cp, pre	.lower
--irgen	acf, icf	.ir
--optir (initial,final)	acf, icf, cp, pre	.ir
--optcfg (initial,final)	acf, icf, cp, pre	.dot
	all	.s
--asmdebug	all	.s

Here are some examples to wrap your head around things:

Flags	Meaning
--lex	Lex the code
--lex -O<opt>	Lex the code; optimization ignored
--parse	Parse the code
--parse -O<opt>	Parse the code; optimization ignored
--typecheck	Typecheck, then AST constant fold
--typecheck -O	Typecheck; no optimization
--typecheck -Ocp	Typecheck; no optimization
--typecheck -Oacf	Typecheck, then AST constant fold
--tcdebug	Typecheck, AST constant fold, and output AST
--tcdebug -Ocp	Typecheck and output AST; no optimization
--tcdebug -Oacf	Typecheck, AST constant fold, and output AST
--nolower	Generate IR with constant folding, but w/o lowering or block reordering
--nolower -O	Generate IR w/o constant folding, lowering, or block reordering
--nolower -Oacf	Generate IR with AST constant folding but no lowering or block reordering
--nolower -Oicf	Generate IR with IR constant folding but no lowering or block reordering
--nolower -Oacf -Oicf	Generate IR with constant folding but no lowering or block reordering
--lower	Generate IR with all optimizations and lowering, but w/o block reordering
--lower -O	Generate IR w/o optimizations, with lowering, and w/o block reordering
--lower -Oacf -Oicf	Generate IR with constant folding, and lowering, but w/o block reordering
--lower -Oacf -Oicf -Ocp -Opre	Generate IR with all optimizations and lowering, but w/o block reordering
--irgen	Generate IR with constant folding, lowering, and block reordering
--irgen -O	Generate IR w/o constant folding, but with lowering and block reordering
--optir initial -O	Generate IR w/o optimizations, but with lowering and block reordering
--optir initial	Generate IR with AST constant folding, lowering, and block reordering
--optir initial -Oacf -Oicf	Generate IR with AST constant folding, lowering, and block reordering
--optir initial -Oacf -Oicf -Ocp -Opre	Generate IR with AST constant folding, lowering, and block reordering
--optir final -O	Generate IR w/o optimizations, but with lowering and block reordering
--optir final	Generate IR with all optimizations, lowering, and block reordering
--optir final -Oacf -Oicf	Generate IR with constant folding, lowering, and block reordering
--optir final -Oacf -Oicf -Ocp -Opre	Generate IR with all optimizations, lowering, and block reordering
--optcfg ...	Same as --optir
	Generate assembly with all optimizations
-O	Generate assembly with no optimizations
-Oacf -Oicf	Generate assembly with only constant folding
--asmdebug	Generate commented assembly with all optimizations
--asmdebug -O	Generate commented assembly with no optimizations
--asmdebug -Oacf -Oicf	Generate commented assembly with only constant folding

x86-64

rax		RET1
rbx			callee-saved
rcx	ARG4
rdx	ARG3	RET2
rsi	ARG2
rdi	ARG1
rbp			callee-saved
rsp
r8	ARG5
r9	ARG6
r10
r11
r12			callee-saved
r13			callee-saved
r14			callee-saved
r15			callee-saved

Virtual Machine

A virtual machine, managed by vagrant, can be found in the vagrant directory. The virtual machine comes with a standard installation of Java and miscellaneous Java tools to make building the Xi compiler consistent and easy. In this section, we show you how to get started with the VM.

First, make sure you have a recent version of vagrant and VirtualBox installed, then navigate to the vagrant directory and run the following command:

vagrant up

This will launch the virtual machine. Note that running vagrant up may run for quite a while the first time you run it; vagrant has to install the virtual machine image on to your machine. After the virtual machine is up and running, you can connect to it with the following command:

vagrant ssh

Once you've ssh'ed into the virtual machine, run the following commands to install Java 8, Eclipse Mars, eclim, ghp-import, and OCaml.

# make sure to run this in the virtual machine
bash /vagrant/install_java8.sh
source /vagrant/install_ocaml.sh

The installation script sets up a bunch of environment variables in the ~/.bash_path file in the virutal machine. To make sure these variables are exported, add the following to your ~/.bashrc in the virtual machine:

# again, you should be in the virtual machine
# Path
if [ -f ~/.bash_path ]; then
    . ~/.bash_path
fi

After this, run source ~/.bashrc (or start a new terminal) and you should be good to go! Try running java -version; you should get the following output:

> java -version
java version "1.8.0_71"
Java(TM) SE Runtime Environment (build 1.8.0_71-b15)
Java HotSpot(TM) 64-Bit Server VM (build 25.71-b15, mixed mode)

One last thing, if you don't want to install Eclipse or eclim or ghp-import, just comment out the appropriate lines in the install_java8.sh script before you run it.

Resources

• CS 4120 Website
• Xi Language Specification
• Overview Documentation Requirements
• Programming Assignment 1
• Online Javadoc Documentation