Implement Code Optimisation Stage, Part 2 - Global Optimisation

[aalhour]

Global Optimisation

Assumes information exists on all points of the program execution, which is typically gathered through Data Flow Analysis.

Data Flow Analysis

Data Flow Analysis runs in terms of relating information between adjacent program points by either transferring information or pushing information. Information about expressions gets transferred from the output of predecessor expressions to the input of their proceeding ones. Pushing information runs in terms of the body of each and every expression from the input of that expression until its output. Transferring information is an analysis of information running from one expression to the other, as adjacent points in the program, whereas pushing information is analysis of the flow of information within the scope of every expression.

Typically Data Flow Analysis tags all SSA-expressions in the execution of the program with 3 tags: C for constant, T for top and B for bottom. Constant means that the value of the expression up until the given point of execution is a constant and therefore can be propagated with a constant. Top means that up until the given point of execution we don't know the value of the expression. Bottom means that up until the given point of execution, the subject expression never excuses and therefore can be eliminated.

The ordering of these tags is as follows: B < C < T.

The Least-Upper Bound logical operation calculates the upper bound in the previous ordering. For example:

• lub(B, 1) = 1, where 1 and 2 are constants, and therefore tagged with C.
• lub(B, C) = C.
• lub(1, 2) = T. Constants are incomparable.
• lub(T, B) = T.

Global Constant Propagation

Given an ordered set of predecessor statements (SSA-expressions) called ps, and a successor statement we are analysing called s then we can define the following Constant Propagation rules.

We begin by defining the rule that relates information between adjacent points in the program:

• C(s, x, in) = lub { C(p, x, out) | p is a predecessor of s }; where:

  • in is the input to point of s.

  • out is the output point of every predecessor p the belongs to the set ps.

  • x is an assignment statement target propagated until the execution point of s, for example:

    x := 1
    y := x * 2
    ...
    s := ... 
    

  • This rule relates the out of one statement to the in of the next statement.

Next, we define the following rules which relate the in of a statement to the out of the same statement:

• C(s, x, out) = B if C(s, x, in) = B.
• C(x := c, x, out) = c if c is a constant (C).
• C(x := f(...), x, out) = T. We don't evaluate the complex inner statement.
• C(y := ..., x, out) = C(y := ..., x, in) if x <> y; where:
  • y := ... means that it's an statement that does't read nor update x.

Algorithm:

1. For every entry s to the program, set C(s, x, in) = T.

2. Set C(s, x, in) = C(s, x, out) = B everywhere else.

3. Repeat until all points satisfy the above rules (1-5):

   3.1. Pick s, where s is not satisfying rules 1-5 and update it using the appropriate rule.

Global Constant Propagation is a forward-probagation analysis. This analysis runs from earlier points in the program to later ones.

Global Liveness Analysis

Also know as Live Variables Analysis.

A variable x is live at statement s if:

• There exists a statement s' that uses x.
• There is a path from s to s'.
• That path has no intervening assignment to x.

A statement x := ... is dead code if x is dead after the assignment.

We can express Livelinessin terms of information transferred between adjacent statements, just as in copy/constant propagation. Except that it is much simpler. Liveliness is a boolean: True or False. A statement is either live or not.

Given a predecessor statement p and a set of successor statements ss, we can define the following Liveliness Analysis rules:

• L(p, x, out) = v { L(s, x, in) | s a successor of p }; where v is the logical OR operator.
• L(s, x, in) = True if s refers to x on the rhs.

  • Example:

    ...          => x is live!
    ... := f(x)
    ...          => x is live!
    

• L(x := e, x, in) = False if e does not refer to x.
• L(s, x, in) = L(s, x, out) if s does not refer to x.

Algorithm:

1. Let all L(...) = False initially.

2. Repeat until all statements s satisfy rules 1-4:

   2.1. Pick s where one of 1-4 does not hold and update using the appropriate rule

Global Liveness Analysis is a backward-probagation analysis. This analysis runs backwards from later points in the program to earlier ones.