Optimizing compiler Scalar optimizations

Main characteristics of the application, affecting its performance

The presentation can be downloaded here.

Optimizing compiler role

Compiler translates the entire source program into an equivalent program in the resulting machine code or assembly language.

The main objective of optimizing compiler is obtaining effective code for target computer system.

From a developer point of view, the program must be:

A developer needs

An optimizing compiler is complex software system, driven by the requirements to the resulting code. Compiler developers face: the complexity of the optimizations legality proof, calculations of profitability, lack of compile-time representation of a typical input data, etc. It requires close cooperation with the developer for achieving the best results.

To use features of the compiler successfully, the programmer must:

Intel compilers

Intel provides C/C++ and Fortran compilers for Windows, Linux and Mac OS operating systems.

For Windows INTEL compiler is made as plug-in for the Microsoft Visual Studio.

The important purposes of the Intel compilers are well-timed support of all new computer systems, compatibility with Microsoft Visual Studio on a Windows platform and gcc on Linux and Mac OS, supplying convenient environment to develop effective applications.

http://www.intel.com/software/products

Front End

Parsing is the process of input characters analysis, usually in accordance with a given formal grammar.

During parsing the source code is converted into a data structure. Usually it is a tree that reflects the syntax structure of the input sequence and is well suited for further processing.

Typically, parsing is divided into two levels:

At the output we get FE related tables, which are called the internal representation of the program. The usual practice is to share one internal representation for the various high-level languages.

The statements are usually presented in a list and can be linked in two ways:

struct Stmt {
  common_members:
  int type;
  Stmt * pred;
  Stmt *succ;
  Basic_Block bblock;
  … 
 }

Some simple scalar optimizations based on walking through the list of statements to find some specific statements and process them:

For_All_Subroutine_Stmt(subroutine,stmt)  {
   if(Stmt_type(stmt) == Stmt_Assign {
      //assignment processing
   }
}

Control Flow Graph

A Control Flow Graph (CFG) represents all paths through a program control could travers during its execution. In a control flow graph each node represents a basic block (a straight-line piece of code without any jumps or jump targets). Jump target starts a block, and jump ends a block. Directed edges are used to represent jumps of the control. There are two specially designated blocks: the entry block, through which control enters into the flow graph, and the exit block, through which all control flow leaves.

The CFG is essential to many compiler optimizations.

Scalar optimizations

There are well-known scalar optimizations such as constant folding, constant propagation and copy propagation.

Constant folding is a process of calculating a constants at compile time.

Constant propagation is substitution of variables with known constant values by these values in the expression.

Copy propagation is substitution of variables by their values.

Common subexpressions elimination

Search for identical subexpressions and saving the calculation result in a temporary variable for later reuse.

Dead code elimination

Removal of code that does not change the output of the program.

There are many cases when dead code can appear. It can be the result of scalar optimizations, inlining, etc.

Removal of excessive branching, broaching conditions

Sometimes conditional branches can be deleted because of previous conditions

Why Control Flow Graph is important for scalar optimizations?

When we can propagate the information about the values of X? For straight-line piece of code the answer is trivial. CFG resolves ambiguity.

Data Flow analysis

Data Flow Analysis is a technique for gathering information about a possible set of values for each variable calculated at various points of a program. Control flow graph (CFG) is used to identify those parts of the program in which a certain value is assigned to a variable can be propagated.

A definition-use graph is a graph that contains the edges from each variable definition point in the program to every point of its use.

Construction of def-use chain for the base block is trivial. Each variable definition is associated with all subsequent uses of it. Each subsequent redefinition stops and starts a new chain.

In order to use this local graph CFG computed using several sets those characterize the behavior of the block:

To understand what definition will be used in our basic block, it is important to know reaches (b).

It can be constructed via an iterative process that will calculate the reaches (b) through the sets of previous blocks.

Reaches (b) = U for all predecessors (defsout (p) U (reaches (p) ? ¬ killed (p))

The problem is that in the presence of loops, the set reaches(b) may depend on the reaches (b). If we will repeat this equation many times for each basic block CFG – final decision can be get.

Constructed sets are used for many scalar optimizations such as dead code elimination, constant propagation and etc. The main problem of this approach is a large number of edges in the Def-Use graph and a great time for calculation of these sets. As result a lot of resources are needed for processing.

This example illustrates the problem. Definitions of S1, S2, S3 pass through the top of S4. Since each definition reaches every use, there are nine edges. Static single assignment form (SSA) was proposed to simplify DEF/USE chain.

SSA (Static single assignment form)

SSA form proposes unique name for each variable definition and introduction of special pseudo-assignments.

SSA is designed to save developers from building complex use / def chains for local variables. Power of SSA is that each variable has only one definition in the program. Therefore, use / def chain is trivial.

SSA introduces special presentation of Phi-functions in places with uncertainty, to create a new variable. This so-called pseudo-assignment. In the construction is necessary to place Phi - functions and create new unique variables.

The new variables are generated by completing the variable name with a unique option. In order to correctly insert the Phi function is necessary to consider some of the concepts of graph theory.

Node N dominates node M if all ways to M pass through N. A node is an immediate dominator of node M if it is the last dominator on any path from entry node to M.

Dominance frontier of node x is set w of all nodes where x dominates all predecessors nodes from w, but doesn’t dominates nodes from w.

Example:

 
Dom[5] = {5,6,7,8}
DF[5] ={5,4,12,11} 

In SSA form, each variable definition must dominate the use of this variable.

Construction of the dominators set for each basic block can be the following:

The set of dominators for a node N is the intersection of the dominators set of all his predecessors, and the node itself.

Strict dominator N, this dominator!= N. Immediate dominator – the closest node from the set of dominators.

idom (N) - the immediate dominator for basic block N

children (N) - the set of basic blocks for N, which it dominates

Criterion of dominance frontier: if the basic block N contains a definition of variable A, then every node on the dominance frontier of node N requires Phi function for A. Each Phi function is also the definition, so you must apply the criterion while there are nodes which requires Phi function.

Inserting ? functions for the node 5 of the scheme on slide 25

Optimization using the SSA form: