Regular Expressions


I personally do not enjoy front end issues as much as back end. And yet a front to back compiler course starts there. Kind of off putting.

BNF Context Free Grammars Parsing Expression Grammar LL LALR

How do you get good error messages

sy brand paper on how compilter diagnostics could be imporved


List of algorithms - parsing Recursive Descent Earley parser Pratt Parser LL Parser LR Parser packrat allstar

Parser Combinators

String -> [(a,String)] A non deterministic search that consumes a prefix of the input. parsec

Parser Generators

Flex yacc/bison antlr Menhir error handling the new way Sam’s coq stuff

Semantic Actions

Intermediate Representations

SSA SSA bookv mirror of ssa book

compcertssa verified ssa

bril educational IR. ocaml and rust bindings.


See LLVM section




ILang Tiramisu MLIR Halide TVM BYOC bring your own codegen

esolang VM - C compiler to simple virtual machine for compiling to esolangs



Dataflow analysis Must/May and intersection vs union. Least fixed point vs greatest


Wikiepedia list of compiler optimizations

Loop invariant code motion - aka hoisting. Move stuff that doesn’t change out of the loop

instruction level parallelism Alex Aiken Utpal Banerjee Arun Kejariwal Alexandru Nicolau

Reassociate to lessen tree height - less dependencies Expand expressions with care - less dependencies

Polyhedral model Foundations of Fine Grain Parallelism. Recurrence equations. Analyze them granulairty

Polyhedral Compilation as a Design Pattern for Compilers PLISS

isl and presburger arithmetic. A relative of omega?

liveness analysis for ssa form program

  • See note on Linker

Profile Guided Optimization (PGO)

Code Gen



diversification make many versions of binary to make code reuse attacks harder. disunison

Toy Program:

If you do liveness analysis ahead of time, it really does become graph coloring, with an edge between every temporary that is live at the same time.

You cannot do liveness ahead of time if you integrate instruction scheduling with allocation. It needs to be internalized.

If you do SSA ahead of time, you have more flexibility to change colors/register at overwrite points

How to communicate to minizinc:

  • Serialized files or C bindings
  • Parameters or constraints. In some sense, you a writing a constraint interpreter over the parameters. Why not cut out the middleman? 1: less clear what the structure is. 2. It forces your hand with the bundling of different pieces. Many things need to be bundled into the insn predicate unless you reify the insn predicate to a variable, in which case you are rebuilding the parameter version.
enum reg_t = {R0, R1, R2};
enum temp_t = {T0, T1, T2, T3};
int MAXID = 2;
set of int : id = {0..MAXID};

predicate insn(operation_t : id, list of temp_t : lhs, string : opcode, list of temp_t : rhs) = 

% since we don't record the gen kill sets we need to do this in here.
constraint forall(t in temp_t)(    %, i in id)(
  if (t in rhs) % in gen set
    live[t, i] = true;
  elseif (t in lhs) % not in gen set, in kill set
    live[t,i] = false;
  else % propagate
    live[t,i] <- live[t, i + 1]

constraint forall(t in temp_t)( live[t, MAXID] = false);

  insn(0, [T1], "mov", [T0]) /\
  insn(1, [T2], "mov", [T0, T1]) /\
  insn(2, [T3], "mov", [T0, T1]) /\

array[temp_t, id] of var bool : live;
array[temp_t] of var reg_t : reg;
% if we're not in ssa, maybe 
% array[temp_t, id] of var reg_t; 
% since register can change as reuse site.


Instruction Selection

Subgraph isomorphism problem VF2 algorithm Very similar to “technology mapping” in the vlsi community.

type aexpr = Mul Add

Macro expansion

  • procede bottom up Maximal Munch

Instruction selection is taking a program and figuriing out which instructions can be used to implement this. Typically this leaves behind still some problems to solve, in particular register allocation and instruction scheduling. Presumably, everything in the program needs to be done. We have some notion of correspondence between the program representation and the available instructions. The exact nature of this correspondence depends on how we represent our program.

  • Sequence
  • Tree - One representation of a program might be as a syntax tree, say (x + (y * z)).
  • DAG - consider (x + y) * (x + y). Really we want to note common shared computation and not recompute x+ y twice. DAGs and the technique of hash consing can be useful here.
  • Tree-like DAGS
  • CFG - A different representation might be to separate out blocks and control edges between them. Blocks consist of a sequence of statements.

If the statements are purely for assignment, assignment can be inlined. The block is nearly purely functional in some sense. It can be compressed into a functional form like the DAG or Tree by inlining. The block could also itself be considered as a graph, as there is often more then one equivalent way of sequencing the instructions.

The simplest case to consider is that of the tree. We can enumerate patterns in the tree that we know how to implement using instructions. The relationship between tree patterns and instructions can be many-to-many. We should understand how to implement every node in the tree (?a + ?b), (?a * ?b) with a pattern consisting of a sequence of instructions for completeness (ability to compile any tree). We also should try to figure out the tree patterns that correspond to a single assembly instruction like load reg [reg+n] because these will often be efficient and desirable.

There are two distinct and often separable problems here:

  1. Find pattern matches
  2. Pick which matches to actually use aka pattern selection

A direct approach to describing patterns is to develop a datatype of patterns. This datatype will be basically the datatype of your AST with holes. This is clearly duplication and becomes painful the more constructors your language has, but whatever.

type ast = Add of ast * ast | Var of string
type ast_pat = Hole of string | PAdd of ast_pat * ast_pat | PVar of string

pmatch : ast_pat -> ast -> (string * ast) list option

Alternatively, we can note that the main point of a pattern is to pattern match and use a church-ish/finalish representation

type ast_pat' = ast -> (string * ast) list option
let convert_pat' : ast_pat -> ast_pat' = pmatch
type var = string
type stmt = Ass of var * expr
type expr = Add of var * var | Var of var

type blk = stmt list

let inline : blk -> (var * ast) list
type insn = Mov of reg * reg | Add of reg * reg | Add2 of reg * reg * reg

A novelty of the Blindell et al work is the notion of universal function (UF) graph. There is both the functinal repsentation of data values, but also cfg is represented as opaque nodes. The correspondence of where values are defined and where computations happen is left up to the constraint solver.

What is the input language? Is it a pure expression langage? A side effectful imperative language? We can convert between these.

I have directly gone to effectful assembly from pure expression language above.

I understand enough to have many questions. What is the input language over which one is pattern matching. Perhaps language is already the wrong word since language tends to imply something tree-like. Is it a pure language or an imperative language. Is it represented as a sequence of IR instructions, a tree, tree-like dag, dag, a graph, or something else. Is represented too weak a word for this question which seems to be very important? “BIL” represented as a sequence vs as a graph might as well be nearly entirely different things. It seems totally possible to translate between pure and imperative, and between the representations and yet it matters so much. What is the output language. It structurally isn’t concrete assembly in many ways. It is definitely un-register allocated and probably unsequenced. Sometimes it feels like tree-like quasi assembly, where the node represents an “output” register even though assembly is really just a sequence of effects. Is there freedom to choose any N^2 combination of structural representations between input and output languages, purity and impurity? None of this even starts to touch control flow. None of this touches what does “overlapping” of patterns mean and what should be allowed

Sequenced representation: Patterns may need to stretch over bits / reorderings. The sequence of the input language does not at all have to be the sequence of the output. Restricting yourself in this way

You can often macro repeat patterns in ways to undo any arbitrary choices made by the representation. Some kind of quotienting. If we have an order free representation, we could aebitrary sequence it, and then sequence the patterns into all possible sequencings. Then you end up with baically the same thing. You can’t go the other way in general. There is something that feels galois connection-y here.

What is the output of pattern matching? Typically I would consider the output of a pattern match to be just pattern variable bindings. But in this case, really we may need full identification between pattern nodes and pattee nodes since this defines the covering.

There are different axes upon which to consider graph variations

  • input/output Edges ordered or unordered / have identity are interchangeable. AST tree have identity. Consider the example of a power or any non commutative operation. Edges with identities may want to be considered to be attached to “ports”
  • Zero/many input output edges (trees)
  • Labels on vertices and or edges

Different kinds can be embedded in each other. Trees can represent graphs if you are allowed to indirectly refer to nodes via labels. Hash cons dags can have many input and output edges. However the output edges of the hash cons are unported, whereas the input edges are ported. The symmettry can be improved by using projection/port nodes connected to the output. In some sense the output of the original is then Operads

You could take a relational perspective on operations, having neither input not output.

Register Allocation

The typical starting point of register allocation is support you’ve been given as assembly program that doesn’t have registers filled in like

# input v1 v2 v3
mov v1, v2
add v1, v1
mul v3, v1
# output v3

The interference graph has an edge between any two variables that are live at the same time. Live means that the variable has been made and someone still needs to use it now or later. In this example, if we assume v1 v2 & v3 are live at the beginning, v1 is live for all 3 instructions, v3 is live for all three and at the output, but v2 is only live at the first instruction since it is never used again.

dsatur graph coliring heurisitc

RL4ReAl: Reinforcement Learning for Register Allocation Compiler gym

Instruction Scheduling

The pure instruction scheduling problem might occur even at the IR level. We can imagine an imperative IR. Certain operations commute and others don’t. We may want to minimize the liveness time of variables for example. This would make sense as a pre-processing step to a sequence input language to an instruction selector.

Instruction scheduling can be parametrized as:

  1. an embedding into actual time (cycle issue time probably). This is important if you are optimizing for runtime and can get estimates of how long each instruction takes.
  2. a ranking as integers
  3. next(i,j) relation which is basically integers. Allows for partial order. after(i,j) :- next(i,k), after(). after is path connected in temporal dag. Possibly this is mappable into a lattice notion of time (i,j,k,etc)?

Assembly Production

You need to produce actual binary, actual 1s and 0s See also:

  • Linking
  • Assembly


de-optimization paths mir an intermiedtae representation for JIT qbe libjit ryujit libfirm cranelift nanojit


copy and patch compilation

Garbage Collector

Conservative vs Exact

The boehm garbage collector seems easy to use. Also you can just malloc and never free.



mark and Sweep


Making a simple garbage collector


cs6120 adrian sampson Looks like a nice syllabus

rose compiler source to source compiler? Makes sense.

compiler optimizations website more links

<> static program analysis

modules - global symbols, function declaration, function definitions, target information program analysis resources. Big long list.

Man souffle does seem cool

It’s surprisingly difficult to find a cogent explanation of all the stuff one might need. It’s useful to call C or be called from C

<code>	.globl compute_42
    movq    %rdi, %rax # move argument into rax
	addq	$32, %rax # add 32 

#include <stdio.h>
#include <stdint.h>

extern uint64_t compute_42(uint64_t a);

int main()
    printf("result is %ld \n", compute_42(4));
    return 0;

sjklsfkjl x86 cheatsheet

alignment is for serious. It really does screw you if you don’t do function alls with stack on 16byte boundaries modern c book free online

%rdi, %rsi, %rdx, %rcx, %r8, and %r9 as first 6 arguments

pushq %rbx is usually first instruction inside function

subq somethign rsp usually happens to allocate on the stack introduction to computer systems

Bryant and OHallaran book. CMU course

gdb. Compile with -g flag. break main. step next print. tui enabe cheatsheet

objdump -d -S -l

valgrind and core dumps.




Instruction Combiner Tutorial: Creating an LLVM Backend for the Cpu0 Architecture LLVM IR tutorial

llvm-mca - static analysis of performance of code

Learning to combine instructions in LLVM compiler