## Friday, March 9, 2018

### Compiler Optimizations

Peephole optimization
In compiler theory, peephole optimization is a kind of optimization performed over a very small set of instructions in a segment of generated code. The set is called a "peephole" or a "window". It works by recognising sets of instructions that can be replaced by shorter or faster sets of instructions.
• Null sequences – Delete useless operations.
• Combine operations – Replace several operations with one equivalent.
• Algebraic laws – Use algebraic laws to simplify or reorder instructions.
• Special case instructions – Use instructions designed for special operand cases.
The following Java bytecode
can be replaced by
... aload 1 dup mul ...

Induction variable
In computer science, an induction variable is a variable that gets increased or decreased by a fixed amount on every iteration of a loop or is a linear function of another induction variable.

For example, in the following loop, i and j are induction variables:
for (i = 0; i < 10; ++i) { j = 17 * i; }

Induction variable substitution
Induction variable substitution is a compiler transformation to recognize variables which can be expressed as functions of the indices of enclosing loops and replace them with expressions involving loop indices.
This transformation makes the relationship between the variables and loop indices explicit, which helps other compiler analysis, such as dependence analysis.

Example:
Input code:
int c, i; c = 10; for (i = 0; i < 10; i++) { c = c + 5; // c is incremented by 5 for each loop iteration }
Output code
int c, i; c = 10; for (i = 0; i < 10; i++) { c = 10 + 5 * (i + 1); // c is explicitly expressed as a function of loop index }
Non-linear induction variables
The same optimizations can be applied to induction variables that are not necessarily linear functions of the loop counter; for example, the loop
j = 1; for (i = 0; i < 10; ++i) { j = j << 1; }
may be converted to
for (i = 0; i < 10; ++i) { j = 1 << i+1; }

Strength reduction
In compiler construction, strength reduction is a compiler optimization where expensive operations are replaced with equivalent but less expensive operations. The classic example of strength reduction converts "strong" multiplications inside a loop into "weaker" additions – something that frequently occurs in array addressing. (Cooper, Simpson & Vick 1995, p. 1)
Examples of strength reduction include:
• replacing a multiplication within a loop with an addition
• replacing an exponentiation within a loop with a multiplication

●用循环替换循环中的乘法
●用乘法替换循环中的幂运算

Loop fission and fusion(循环整合/拆分)
In computer science, loop fission (or loop distribution) is a compiler optimization in which a loop is broken into multiple loops over the same index range with each taking only a part of the original loop's body. The goal is to break down a large loop body into smaller ones to achieve better utilization of locality of reference. This optimization is most efficient in multi-core processors that can split a task into multiple tasks for each processor.
Conversely, loop fusion (or loop jamming) is a compiler optimization and loop transformation which replaces multiple loops with a single one. It is possible when two loops iterate over the same range and do not reference each other's data. Loop fusion does not always improve run-time speed. On some architectures, two loops may actually perform better than one loop because, for example, there is increased data locality within each loop.

Loop inversion(利用流水线)
int i, a[100];
i = 0;
while (i < 100) {
a[i] = 0;
i++;
}

is equivalent to:
int i, a[100];
i = 0;
if (i < 100) {
do {
a[i] = 0;
i++;
} while (i < 100);
}

Despite the seemingly greater complexity of the second example, it may actually run faster on modern CPUs because they use an instruction pipeline. By nature, any jump in the code causes a pipeline stall, which is a detriment to performance.

Loop interchange(利用缓存机制)
In compiler theory, loop interchange is the process of exchanging the order of two iteration variables used by a nested loop. The variable used in the inner loop switches to the outer loop, and vice versa. It is often done to ensure that the elements of a multi-dimensional array are accessed in the order in which they are present in memory, improving locality of reference.

For example, in the code fragment:
for i from 0 to 10
for j from 0 to 20
a[i,j] = i + j
loop interchange would result in:
for j from 0 to 20
for i from 0 to 10
a[i,j] = i + j
On occasion, such a transformation may create opportunities to further optimize, such as automatic vectorization of the array assignment

Loop-invariant code motion
In computer programming, loop-invariant code consists of statements or expressions (in an imperative programming language) which can be moved outside the body of a loop without affecting the semantics of the program. Loop-invariant code motion (also called hoisting or scalar promotion) is a compiler optimization which performs this movement automatically.

If we consider the following code sample, two optimizations can be easily applied.
for (int i = 0; i < n; i++) {
x = y + z;
a[i] = 6 * i + x * x;
}
The calculation x = y + z and x * x can be moved outside the loop since within they are loop-invariant code, so the optimized code will be something like this:
x = y + z;
t1 = x * x;
for (int i = 0; i < n; i++) {
a[i] = 6 * i + t1;
}

Invariant code detection(RDA)
Usually a reaching definitions analysis is used to detect whether a statement or expression is loop invariant.
For example, if all reaching definitions for the operands of some simple expression are outside of the loop, the expression can be moved out of the loop.

Loop nest optimization(循环嵌套优化)
In computer science and particularly in compiler design, loop nest optimization (LNO) is an optimization technique that applies a set of loop transformations for the purpose of locality optimization or parallelization or other loop overhead reduction of the loop nests. One classical usage is to reduce memory access latency or the cache bandwidth necessary due to cache reuse for some common linear algebra algorithms.
The technique used to produce this optimization is called loop tiling; also known as loop blocking, or strip mine and interchange.

Loop unrolling(空间换时间)
Loop unrolling, also known as loop unwinding, is a loop transformation technique that attempts to optimize a program's execution speed at the expense of its binary size, which is an approach known as the space–time tradeoff. The transformation can be undertaken manually by the programmer or by an optimizing compiler.
The goal of loop unwinding is to increase a program's speed by reducing or eliminating instructions that control the loop, such as pointer arithmetic and "end of loop" tests on each iteration; reducing branch penalties; as well as hiding latencies including the delay in reading data from memory. To eliminate this computational overhead, loops can be re-written as a repeated sequence of similar independent statements.
Loop unrolling is also part of certain formal verification techniques, in particular bounded model checking.

Loop splitting(拆分循环以简化依赖关系)
Loop splitting is a compiler optimization technique. It attempts to simplify a loop or eliminate dependencies by breaking it into multiple loops which have the same bodies but iterate over different contiguous portions of the index range.
Loop peeling is a special case of loop splitting which splits any problematic first (or last) few iterations from the loop and performs them outside of the loop body.
Suppose a loop was written like this:
int p = 10;
for (int i=0; i<10; ++i)
{
y[i] = x[i] + x[p];
p = i;
}
Notice that p = 10 only for the first iteration, and for all other iterations, p = i - 1. A compiler can take advantage of this by unwinding (or "peeling") the first iteration from the loop.
After peeling the first iteration, the code would look like this:
y[0] = x[0] + x[10];
for (int i=1; i<10; ++i)
{
y[i] = x[i] + x[i-1];
}
This equivalent form eliminates the need for the variable p inside the loop body.

Loop unswitching(提高并行性)
Loop unswitching is a compiler optimization. It moves a conditional inside a loop outside of it by duplicating the loop's body, and placing a version of it inside each of the if and else clauses of the conditional. This can improve the parallelization of the loop. Since modern processors can operate fast on vectors this increases the speed.

Software pipelining(软流水线)
In computer science, software pipelining is a technique used to optimize loops, in a manner that parallels hardware pipelining. Software pipelining is a type of out-of-order execution, except that the reordering is done by a compiler (or in the case of hand written assembly code, by the programmer) instead of the processor. Some computer architectures have explicit support for software pipelining, notably Intel's IA-64 architecture.
It is important to distinguish software pipelining which is a target code technique for overlapping loop iterations, from modulo scheduling, the currently most effective known compiler technique for generating software pipelined loops. Software pipelining has been known to assembly language programmers of machines with instruction-level parallelism since such architectures existed. Effective compiler generation of such code dates to the invention of modulo scheduling by Rau and Glaeser. Lam showed that special hardware is unnecessary for effective modulo scheduling. Her technique, modulo variable expansion is widely used in practice. Gao et al. formulated optimal software pipelining in integer linear programming, culminating in validation of advanced heuristics in an evaluation paper. This paper has a good set of references on the topic.

Common subexpression elimination
In compiler theory, common subexpression elimination (CSE) is a compiler optimization that searches for instances of identical expressions (i.e., they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a single variable holding the computed value.

Constant folding(RDA)
Constant folding and constant propagation are related compiler optimizations used by many modern compilers. An advanced form of constant propagation known as sparse conditional constant propagation can more accurately propagate constants and simultaneously remove dead code.
Constant propagation is implemented in compilers using reaching definition analysis results. If all a variable's reaching definitions are the same assignment which assigns a same constant to the variable, then the variable has a constant value and can be replaced with the constant.

In computer programming, a local variable that is assigned a value but is not read by any subsequent instruction is referred to as a dead store. Dead stores waste processor time and memory, and may be detected through the use of static program analysis, and removed by an optimizing compiler.
If the purpose of a store is intentionally to overwrite data, for example when a password is being removed from memory, dead store optimizations can cause the write not to happen, leading to a security issue. Some system libraries have specific functions designed to avoid such dangerous optimizations, e.g. explicit_bzero on OpenBSD.

Live variable analysis
In compiler theory, live variable analysis (or simply liveness analysis) is a classic data-flow analysis performed by compilers to calculate for each program point the variables that may be potentially read before their next write, that is, the variables that are live at the exit from each program point.
Stated simply: a variable is live if it holds a value that may be needed in the future.

Available expression(CSE)
In the field of compiler optimizations, available expressions is an analysis algorithm that determines for each point in the program the set of expressions that need not be recomputed. Those expressions are said to be available at such a point. To be available on a program point, the operands of the expression should not be modified on any path from the occurrence of that expression to the program point.
The analysis is an example of a forward data flow analysis problem. A set of available expressions is maintained. Each statement is analysed to see whether it changes the operands of one or more available expressions. This yields sets of available expressions at the end of each basic block, known as the outset in data flow analysis terms. An expression is available at the start of a basic block if it is available at the end of each of the basic block's predecessors. This gives a set of equations in terms of available sets, which can be solved by an iterative algorithm.
Available expression analysis is used to do global common subexpression elimination (CSE). If an expression is available at a point, there is no need to re-evaluate it.

Value numbering
Value numbering is a technique of determining when two computations in a program are equivalent and eliminating one of them with a semantics preserving information.

Sparse conditional constant propagation
In computer science, sparse conditional constant propagation is an optimization frequently applied in compilers after conversion to static single assignment form (SSA). It simultaneously removes some kinds of dead code and propagates constants throughout a program. Moreover, it can find more constant values, and thus more opportunities for improvement, than separately applying dead code elimination and constant propagation in any order or any number of repetitions.
The algorithm operates by performing abstract interpretation of the code in SSA form. During abstract interpretation, it typically uses a flat lattice of constants for values and a global environment mapping SSA variables to values in this lattice. The crux of the algorithm comes in how it handles the interpretation of branch instructions. When encountered, the condition for a branch is evaluated as best possible given the precision of the abstract values bound to variables in the condition. It may be the case that the values are perfectly precise (neither top nor bottom) and hence, abstract execution can decide in which direction to branch. If the values are not constant, or a variable in the condition is undefined, then both branch directions must be taken to remain conservative.
Upon completion of the abstract interpretation, instructions which were never reached are marked as dead code. SSA variables found to have constant values may then be inlined at (propagated to) their point of use.