Compiler Optimization

Resource

Dataflow Analysis

A simple problem we want to solve looks like

a = 3
b = a
c = b
print c

which is equivalent to

print 3

It’s indeed intuitive to human that this optimization is correct, but it raises complexity when compiler deals with this problem. The above example used two techiques Constant Propagation and Copy Propagation.

Why?

Because the Goal is to optimize the program while retaining the correctness. Branching will greatly raise the cost of retaining correctness. So the Control Flow Graph comes into play. Whatever optimization we do, we need to ensure all path results in the same as before.

Instruction Scheduling

Cache

Consider we only have one register, here is a snippet.

a = 3
c = 2
print a
print c

Notice when print a we need to reload a from memory since cache is tiny. However, it’s possible to rewrite the program into

a = 3
print a
c = 2
print c

By some simple Data Dependence Analysis, we can assure out optimization is correct.

Software pipelining

Consider a loop.

int a[4];
for (int i = 0; i < 4; i++) {
	a[i] = 1;
}

By default, this loop will run sequentially on one core. But it’s obvious that we want to achieve parallism when we have multiple processors. However, we do need to introduce complexity to handle data dependency and resource constraint.

Grabage Collection

Reference Counting and Mark and Sweep are way too introductory.

A interesting topic is generational garbage collection. The assumption is variables are mostly young (create and delete soon). Whenver objects that are reachable after one garbage collection pass, it would probably pass the next garbage collection pass. So it’s wise to ignore them in the next few garbage collection pass. So we gain the perfomance by ignoring things like global objects.

Jiayu Ye