Local Optimization

The simplest form of optimization
Optimize one basic block. (No need to analyze the whole procedure body).

Some statements can be deleted

x := x + 0
x := x * 1

Eliminating these instructions are great optimizations as we are removing an entire instruction. These transformations may look silly, but they are actually quite general, and are usually created because of the use of compile-time constants, e.g., macros, template parameters, etc.

Some statements can be simplified

x := x * 0  =>  x := 0

Maybe the instruction on the right is faster than the instruction on the right. More importantly, assigning to a constant allows more cascading optimizations, as we will see later.

Another example:

y := y ** 2  => y := y * y

Typically, an architecture will not have the exponentiation instruction and so this operator may have to be implemented by an exponentiation loop in software. For the special cases (e.g., exponent = 2), we can simply replace by multiplication.

Another example:

x := x * 8  => x := x << 3
x := x * 15  => t := x << 4; x := t - x

Replace multiplication by a power-of-two to a shift-left operation. Can also do this for non powers-of-two. On some machines, left-shift is faster than multiply, but not on all! Modern machines have their own "rewriting logic" in hardware that can deal with these special cases really fast. In other words, some of these compiler local optimizations may become less relevant on modern hardware. Yet, some optimizations are always done because they are "harmless" (e.g., the first one) while others may be more controversial (e.g., the second one).

All these transformations are examples of algebraic simplifications.

Some algebraic simplifications transfer from high-school algebra while others do not, because of the finite representation of integers and reals in a computer through bitvectors. For example, a+(b-a)/2 cannot be replaced with (a+b)/2 on a computer, as a+b may overflow for large values of a and b. Similarly, i+1<j+1 cannot be replaced with i<j in general, e.g., if i and j are unsigned integers in C.

Further, some algebraic simplifications are only legal on a computer, and do not hold for integers or reals, e.g., instead of "Numerator / Constant", use "(Numerator * M) >> shift". Hardware division instructions can take 30 to 100 cycles, whereas a multiplication only takes one to three cycles.

An important detail that we have omitted for simplicity is that LLVM IR has types. For example, pseudo-register x is of type iN (e.g., i1, i8, i32, ...) or fN for floating point (e.g., f16, f32, f64, f80), or ptr (for pointers).

Another underlying assumption is on the "notion of correctness". A compiler is usually required to preserve bit-correctness, also called bit-precision. This is the default compiler behaviour, even for floating point computations. However, compilers allow you, through a command-line flag, to relax bit-correctness requirements, to enable more optimizations. For example, a compiler may assume associativity of FP addition while performing transformations.

Operations on constants can be computed at compile time

If there is a statement x := y op z
And y and z are constants.
Then y op z can be computed at compile time.

Examples

x:= 2 + 2 can be changed to x := 4
if 2 < 0 jump L can be deleted.
if 2 > 0 jump L can be replaced by jump L

This class of optimizations is called constant folding. One of the most consequential and most common optimizations performed by compilers.

Another important optimization: eliminate unreachable basic blocks (dead code):

Code that is unreachable from the initial block
- e.g., basic blocks that are not the target of any jump or "fall through" from a conditional
Removing unreachable code makes the program smaller
- And sometimes also faster
  - Due to memory cache effects
  - Increased spatial locality

Called dead-code elimination.

Why would unreachable basic blocks occur?

e.g., if (DEBUG) then { .... }
- Need constant propagation followed with dead-code elimination to remove this whole code.
Libraries: a library may supply a 100 methods but we are using only a 3 of those methods, the other 97 are dead-code.
Usually other optimizations may result in more dead code

Dead code is more general the unreachable code. A register is live if the value contained in it may be consequential to the future execution of the program. An assignment to a register that is not live can be removed.

Discuss how one would implement dead code elimination and constant folding for a single basic block, using the following example:

i1: d := 10
i2: a := w + y
i3: x := 3 + a
i4: b := x * 5
i5: w := 3 + d
i6: x := w + 1
i7: d := (x % 1)
i8: if d goto L
...

For liveness, we will walk the basic block backward, maintaining at each point, which registrs are live at each program point. Conservatively assume that all a,b,d,w,x,y are live at the end of the basic block. At the beginning of i8, all are live; i7, all except d are live; i6, all except x,d are live; i5, a,b,y are live; i4, all except a,b,x,y are live; i3, a,d,y are live; i2, d,w,y are live; i1, w,y are live.

Similarly, for constant folding, we will walk the basic block forward, maintaining at each point, which registers are constant (along with constant value) at each point. Let NAC represent the "NotAConstant" determination. At i1, we conservatively assume that all the registers are NAC. At i2,i3,i4,i5, d=10; i6, d,w are 10,13.; i7, d,w,x are 10,13,14; i8, exit, d,w,x are 0,13,14.

If we make transformations based on any of these analyses, that may change the results of the analysis; e.g., the analysis may need to be run again, usually to obtain more optimization opportunities, e.g., b is dead and after its assignment is removed, x at i3 becomes dead too, and its assignment may also be removed.

Some optimizations are simplified if each register occurs only once on the left-hand side of an assignment.

Rewrite intermediate code in single assignment form, where every register is assigned at most once:
```
i1: d1 := 10
i2: a1 := w + y
i3: x1 := 3 + a1
i4: b1 := x1 * 5
i5: w1 := 3 + d1
i6: x2 := w1 + 1
i7: d2 := (x2 % 1)
i8: if d2 goto L
...
```
Why Static Single Assignment (SSA)?
- Optimization algorithms become simpler and more efficient if each variable has only one definition: instead of tracking (variable-value-at-PC), simply track (variable-value).
  - Consider constant folding: instead of maintaining the constant-ness information at every PC for every variable, we can maintain constant-ness for every variable (without the per-PC state). This effectively brings us from near-quadratic to near-linear complexity. The number of variables may have increased (which is why it is not exactly linear).
  - Consider liveness analysis: instead of maintaining the liveness information at every PC for every variable, we can just maintain liveness of a variable anywhere in the program (i.e., is it used anywhere).
  - Question: but why does the non-single-assignment algorithm need to maintain a per-PC state. For example, why can't the constant folding example work by just maintaining the constantness of the last assignment to a variable (in the forward direction); similarly, why can't liveness track the last use of a variable (in the reverse direction). Answer: Yes, that is possible for a single basic block, by maintaining a careful ordering of the traversal; but notice that if we maintained per-PC information, then the order in which we transfer the information across an instruction can be arbitrary. Such arbitrary order possibility becomes necessary for a control-flow graph, where a compiler cannot determine at compile time which branch may be taken (e.g., branch1 may be taken in the first iteration of a loop followed by branch2 in the second iteration). Thus, single-assignment becomes a necessity for better runtime in the setting of a control-flow graph.
- Unrelated uses of the same variable become independent (eliminates Write-After-Write dependencies).
- More values become available at each program point.
Converting to Single-assignment form
- Replace the target of each assignment with a new variable
- Replace each use of a variable with the version of the variable reaching that point.
Show an example with a diamond structure.
The need for phi nodes: show a diamond structure where two different versions of the same variable reach the same point. Define y3=phi(BB1,y1,BB2,y2) at the beginning of the meet point.
- Phi function chooses the version depending on the incoming edge.
- The phi node is present only at the beginning of a basic block.
Show an example with a do-while loop. Introduce Static Single Assignment (SSA)
Show an example with a while-do loop. Inserting PHI nodes: Path convergence criterion: need Phi node for a variable a at node z iff:
- There is a block x containing definition of a.
- There is a block y!=x containing a definition of a.
- There are non-empty paths Pxz and Pyz from x-to-z and y-to-z respectively.
- Pxz and Pyz don't have any node in common except z.
We will later learn how to convert a program to SSA form. LLVM IR is an SSA IR, to take advantage of all the benefits discussed earlier.
Common subexpressions: If
- Basic block is in single assignment form
- A definition x := is the first use of x in a block
Then
- When two assignments have the same rhs, they compute the same value.
Example
```
x := y + z
....
....
w := y + z
```
We can be sure that the values of x, y, and z do not change in the code. Hence, we can replace the assignment to w as follows:
```
x := y + z
....
....
w := x
```
This optimization is called common-subexpression elimination. This is also another very common and consequential compiler optimization.
Copy propagation: If we see w := x appears in a block, replace subsequent uses of w with uses of x
- Assumes single assignment form
Example:
```
b := z + y
a := b
x := 2 * a
```
This can be replaced with
```
b := z + y
a := b
x := 2 * b
```
This is called copy propagation. This is useful for enabling other optimizations
- Constant folding. e.g., if the propagated value is a constant
- Dead code elimination. e.g., the copy statement can be eliminated as it is inconsequential.
If w := rhs appears in a basic block and w does not appear anywhere else in the program, THEN the statement w := rhs is dead and can be eliminated.
- Dead: does not contribute to the program's result
In our copy-propagation example, one of the assignments is dead and can be eliminated.

Each local optimization does little by itself
Typical optimizations interact
- Performing one optimization enables another
Optimizing compilers can be thought of as a big bag of tricks.
Optimizing compilers repeat optimizations until no improvement is possible
- The optimizer can also be stopped at any point to limit compilation time
- Certain properties on these transformations (tricks) ensure that we converge (and not oscillate) in this fixed point procedure. e.g., we always improve for some notion of improvement. This means that we are uni-directional and can never oscillate.

Example

a := x ** 2
b := 3
c := x
d := c * c
e := b * 2
f := a + d
g := e + f

Final form

a := x * x
f := a + a
g := 6 * f

Possible to simplify further, but the compiler may get stuck in "local minima". e.g., should it have changed a + a to 2 * a, it would have had a better optimization opportunity (replacing g = 12*f and eliminating computation of f).

There are two questions here:

What order to apply the transformations?
If we repeat optimizations until no improvement possible, do we expect to converge?

On order of application:

The order perhaps becomes less consequential, if we are going to apply the transformations in a loop anyway
But even then, the order matters, as one transformation may potentially preclude another. Consider the example x := x * 4; x := x * 3. This program can transformed through a combination of common-subexpression elimination and constant folding to x := x * 12. However, if we first implement the algebraic simplification x := x * 4 ==> x := x << 2, then maybe the constant folding transformation can no longer be triggered, as the compiler may not recognize that it can fold a left shift and a multiplication to a single multiplication.
It can be argued above that a compiler can be made smarter by getting it to fold a left-shift and a multiplication by a constant, to a multiplication by a folded constant. Consider the example x := y * 5; w := x * 3

 being transformed first to t := y << 2; x := t + y; w := t * 3, and now the constant folding becomes harder.  In general, the compiler will have a limited capability or scope of transformations, and a previous transformation can get the program to a state where the best solution falls outside the scope of transformations performed by a compiler.  An infinitely capable compiler should still be able to perform the transformation, but that is not the compiler we have at hand.
	It is possible for a compiler to try multiple orders of application, and get the best result.  However, compile-time is an important consideration, and is often a productivity drag in today's world.  That said, compilers use sophisticated tricks to alleviate these problems, e.g., somehow maintain this property that x is formed by multiplication of y by a constant, even after the code transformation, e.g., through an extra common-subexpression entry.
	This is called the phase ordering problem.
	In general, identifying the order of application that produces the optimizal result is an NP-hard problem under practical formulations of the problem



 On convergence:

	In general, it is possible for the application of transformations to oscillate between two programs, causing the application loop to run forever.
	If we ensure that a transformation is applied only if it strictly reduces the number of instructions, then we are guaranteed to converge, because in the "worst" case we will eventually eliminate all instructions (in which case we will converge too).
	To generalize this idea, we can have a cost function that takes as input a program, and outputs a number that represents the cost of that program.  For example the cost function could be the number of instructions in a program. Thus, we will apply a transformation only if it strictly reduces the cost of the program with respect to a cost function.
	The number of instructions as a program's cost has many problems: e.g., a division is tens of cycles, while a multiply or a shift is 1-3 cycles.  Moreover, recall that some transformations such as vectorization increase the size (number of instructions) of a program (e.g., to implement warm-up or cool-down loops), yet making it significantly faster.
	Another option is to have a cost for every instruction, and then use an additive model to capture the cost of a basic block.  This has problems too, as it does not consider the fact that the hardware can execute multiple instructions in parallel. For example, a transformation from x := y * 4; z := x * 3 to x := y * 4; z := y * 12 may seem non-profitable in this model, even though it improves performance by reducing dependencies, and unlocking parallelism.
	A better option is to have a hardware model, that dictates what the issue width, number of ALUs, etc. are.  Then simulate the instruction sequence on the hardware model to estimate the number of cycles it takes.  This is what is typically done at the very backend of the compiler, where a different model exists for every different chip model (aka ISA implementation), e.g., the chip model may be vastly different for an low-power embedded processor like Intel Atom than a high-performance processor like Intel Cascade Lake. For the final stages of code generation, such a cost model is used; however what about the transformations at the IR level?
	At the IR level, some approximation of the machine model is used to estimate the cost.   The cost model typically accounts for opcode costs and dependency chain lengths, i.e., features that are machine-agnostic.
	Every opcode needs to be associated with two values: latency (number of cycles to execute the operation on the given hardware) and throughput (number of operations that can execute in parallel on the given machine).
	
Memory accesses add another level of complexity to the cost model.
		
			A store can be performed asynchronously, as it does not return a register.  Thus, throughput is more important than latency for a store option. For a load, both the latency and throughput are consequential.
			What if a store is followed by a load, e.g., store (r1), r2; r3 := load(r4); does the cost of the load depend on the latency of the preceding store. Answer: it depends on the values of address regsiters r1 and r4.  If r1 and r4 refer to the same memory address, then the value that is returned by load is r2; else it is the original contents of the memory location at r4.  This is called aliasing, where the same object in the machine can have more than two names --- here the same memory locations may have names r1 and r4.
			To model cost in the presence of aliasing, the hardware model needs to have a queue of outstanding stores, also called the store buffer, so that the following loads can either obtain their values from the store buffer or go to the memory hierarchy; each possibility has a different cost.  The store buffer is of a finite size, e.g., 4-8 entries, and so the latency of a store also becomes relevant now, as the latency dictates the probability that a load will have to stall or not, e.g., a store followed by a load, where both have the same address with a high probability indicate that the load likely has a low cost.
			Finally, the caching behaviour of a memory access becomes a significant determining cost. A cost model needs a prediction for every memory access on how likely it is going to be an L1-hit, or an L3-miss, or so on... For example, stack accesses can be predicted to be L1-hits with a high probability, because the compiler itself orchestrates the stack accesses. Also, if the compiler identifies a sequential access pattern, e.g., for i = 0 to n { a[i] += ... }, then it can predict with a high probability that a[i] will be L1-hit, as it will likely be prefetched due to spatial locality.  Similarly, random looking accesses are given a high probability of being a cache miss.
		
	


Peephole optimizations
All the transformations we have studied so far, involve the identification of a pattern, and then a transformation (or a replacement for that pattern).  One way to implement
these pattern-replacement rules is through explicit hand-optimized code, e.g., in C++ to identify a pattern and transform it.  Another way is to define a small
language for specifying these patterns and their associated desired replacements.  Such a pair of a pattern and its replacement is called a peephole optimization.

A peephole optimization (also called a peephole optimization rule) is typically specified as one sequence of instructions (pattern) to be transformed to another sequence of instructions (replacement).
i1; i2; i3; ..; in --> j1; j2; ..; jm


For example,
say x := x + 4; x := x + 3 should be replaced with x := x + 7.  It seems wasteful to have specific constants in a peephole optimization rule, so we can generalize the format of a peephole optimization so it supports holes which indicate that any value (e.g., constant) can substitute for that hole (think of a hole as a "variable"). So we generalize the example rule: x := x + C1; x := x + C2 to x := x + (C1 + C2).  Here, C1 and C2 are compile-time constants, and the computation C1+C2 is performed by the compiler at compile time.  Notice that there are subtleties here, e.g., what should happen if C1+C2 overflows at compile time? Answer, the behaviour should be identical to that of the original program, so the final result should maintain the addition semantics for the types of the original registers.  For example, it would be valid to have a rule that says: (C1+C2) does not overflow; x := x + C1; x := x + C2 to x := x + (C1 + C2). Here, the compiler is forced to check that C1+C2 does not overflow before potentially applying the transformation.

The example peephole optimization rule above can be generalized further, e.g., x := y + C1; x := x + C2 to x := y + (C1+C2) is more general, as it allows x and y to refer to the same or different registers.  A more general peephole optimization rule is better as it can trigger in strictly more number of situations.

In fact, the rule can be generalized further to something like: x := y + C1; z := x + C2; x is not live  to z := y + (C1+C2).  In this generalization, we introduce a third register z, and allow it to be (same or) different to registers x, y. Notice that the x is not live is required because the replacement gets rid of the assignment to x.  Further, notice that the original code still matches this pattern --- if both z and x match to the same register, say r, then the rule triggers even if r is live at the end of the instruction sequence, because z is allowed to be live (requires a slightly more sophisticated logic to interpret the rule).

Notice that through my examples, I have sneaked in constraints in addition to instruction sequences in a peephole optimization.  Examples of constraints above are: C1+C2 does not overflow, x is not live, etc.  In general, the language of these constraints (and consequently the language of a peephole optimization) can be made arbitrarily rich.  For example, it may be possible to say that the two instructions present in the pattern may be separated by an arbitrary length sequence of instructions, as long as those instructions obey certain properties.  The richer the language of a peephole optimization, the more general a peephole optimization rule can be made; however this richness comes at a significant cost for the compiler as it needs to interpret and apply the peephole optimization. For example, the application of x is not live requires a compiler to first execute a liveness analysis.  Or the allowance of an arbitrary instruction sequence between the two instructions in the pattern, can require a compiler to perform a search over the basic block that can be linear or quadratic in running time, depending on the implementation.  Arguably, peephole optimization formats can be made arbitrarily rich, and a compiler can be made to support them; however this is rarely done today, instead the common transformations are simply hand-coded in C++ so they execute fast (much faster than interpreting an arbitrarily-rich peephole optimization rule).

As for local optimizations, peephole optimizations are usually applied repeatedly
for maximum effect.  Just like other local optimizations,
need to ensure that the replacement rules cannot cause oscillations. e.g., each replacement rule can only "improve" the code.

Originally, the idea of peephole optimizations was first applied to the assembly code (after the code generation and optimization phases, as the final step).  The idea was that 
at the assembly-level, we have greater visibility into instruction costs and instruction opcodes. e.g., hardware opcodes may be higher-level than IR opcodes.  And so peephole optimizations were effective at improving assembly code.
Example:
move $a $b; move $b $a --> move $a $b

Works if the second instruction is not the target of a jump (i.e., both instructions belong to a basic block).
Another example:
addiu $a $a i; addiu $a $a j --> addiu $a $a (i+j)

Many (but not all) of the basic block optimizations can be cast as peephole optimizations

	Example: addiu $a $b 0 --> move $a $b
	Example: move $a $a --> 
	These two together eliminate addiu $a $a 0.


Today, peephole optimizations are used at the LLVM IR level, at the Machine-IR level, and at the assembly level, e.g., LLVM IR peephole optimizer (called Instcombine) implements hundreds or thousands of peephole optimizations. They support a restricted language of constraints, e.g., the kind of constraints shown in examples above.

Research efforts have tried to make peephole optimizers much more general, and also discover peephole optimization rules automatically using AI, but these ideas have found only limited adoption in production so far.

Order of transformations in LLVM IR
So far we have studied the following compiler analyses and transformations

	Algebraic simplifications (AS)
	Constant folding / propagation (CP)
	Liveness analysis (LA)
	Dead code elimination (DCE)
	Copy propagation (CP)
	Common Subexpression Elimination (CSE)

In LLVM, CP is done at construction time, as the IR does not support copy instructions
at all; in other words, CP is done
at the very beginning.  CSE is also done while constructing an instruction in the IR, as if an RHS expression
is already available (in SSA form) as a register, that register is used, instead of creating
a new register. Similarly, the liveness information is easily maintained at all times, by maintaining
the "users" of every SSA definition (a user is an instruction that uses that definition). Constant folding or
propagation is done a few times in the transformation pipeline; DCE is usually done in the later stages, but
it is also done multiple times, especially after passes such as CP.

"Program optimiztion" is grossly misnamed

	Code "optimizers" have no intention or even pretense of working towards the optimal program.
	
Code "improvers" is a better term.