Compiler Designing W08L1501

Global Optimization: Dataflow Analysis

  • It is a global optimizations technique.
  • The main strategies are:
    • Dead Code elimination and;
    • Code propagation
  • A variable x can be replaced by a constant k if on every path to use of x the last assignment of x is x:= k. It simply means that at the compile-time if x is not used in some blocks till the block where this x is to be replaced by k and there is no change in value of x via any path, then x is replaced by k.(in control-flow diagram)
  • The above method is not that easy as path can have iterations of conditions etc. Checking for the required condition is given a name: global data flow analysis, it analyzes the whole graph.
  • Global optimization tasks share several traits:
    • depends on the value of some X at some point in the program;
    • Proving X can require knowledge of entire program;
    • and it is always safe to say that X is not known if it cannot be decided.
Advertisements

Compiler Designing W08L1404

Peephole Optimization

  • It can be directly applied to assembly code, basically it is short sequence of instructions.
  • Instruction sequence is replaced to other via transformations.
  • Many basic blocks optimization is also a peephole optomization.
  • It should be applied repeatedly to get maximum optimization.
  • Program improvement is the more suitable term for all these transformations as discussed in previous posts also, instead of program optimization.

Compiler Designing W08L1403

Local Optimization

  • As defined in the last post, it is the optimization done on the basic blocks in isolation. For example, some algebraic simplifications are:
Some examples of optimization:
x=x*1 or x=x+0       ⇒ deleted
x=x*0                ⇒ x=0
x=x**2               ⇒ x=x*x    //as exponentiation would require call of other instructions 
                                //that cannot help in reducing the instructions
x=x*8                ⇒ x<<3     //not a good replacement on modern machine

Examples of constant folding:

x := y op z                    //if y and z are constant then they can be replaced at 
                               //compiler-time
if 3 < 9                       //it can be computed at compile time, improves on IC as it 
                               //removes the false branch altogether

A problem in constant-folding can be seen when doing cross-compilation. Lets assume that the source code is compiled on machine X then the generated code is ran on machine Y. If floating point operations are constant folded, then it is possible in the case of different architectures of the machines that they need different precision. Though this case be avoided by using a string to compute the floating point with full precision and then the code can be run on Y and Y would round that literal according to it’s architecture.

Constant propagation is the process of substituting the values of known constants in expressions at compile time. Dead codes can also be removed.

Dead Code removal: As the instructions of this portion is never executed but making the code smaller actually make it faster because of spatial locality in memory cache. If w= is used only once in a procedure and tehre is no use of w again then its a dead code and can be deleted. Reasons can be using libraries, result of optimization.

b := y+z
a := b          //not needed //dead code
y := 2*a
  • Single Assignment form: Some optimizations can be simplified if all the registers on LHS are different.
    • Common sub-expression elimination: If the basic block is in single assignment form then x:= appears just once in the block, so the statements having same RHS would compute to same value if the value of those variables at the RHS doesn’t change.
  • Example is here from 18:13 minute.
  • Local optimizations doesn’t make big difference. Optimization can be repeated till no improvement is made and can be halted any time.
  • Example 22:55 minute.

Compiler Designing W08L1402

Optimization Overview

  • It is the fourth and the largest phase of the compilers.
  • Lets see the chances where optimizations can be done:
    • On AST: machine independent but very high level
    • On assembly language: optimization can be rich in quality but it is machine dependent so it is inefficient.
    • On intermediate language: most suitable because it is machine independent as well as optimization opportunities are rich.
  • Control flow graphs are very important to visualize the program execution. In the graph each node is a basic block.
    • Basic block: it contains the instruction of a portion of a program, the condition is it has no jump, except at the last statement and no label except at the beginning of the block. See example.
    • These blocks are connected to each other depending on the program structure.
  • Optimization often improves on execution time and doesn’t alter program meaning.
  • There are three types of optimizations:
    • Local: optimization of basic blocks in isolation.(most of the compilers do it)
    • Global: optimization of control-flow graph in isolation.
    • Inter-procedural: Applied across method boundaries.
  • Optimization not always done, as it can be hard to implement, low benefit, may be costly in compile time.

Compiler Designing W08L1401

Intermediate Code

  • Language between source and target.
  • In many compiler, source code is first converted to an intermediate code or number of intermediate codes and then converted to machine code.
  • Intermediate code contains more details in the terms of register usage (or there can be more advantage) than source code.
  • The source code is converted into this form as the optimization can be done easily here.
  • Intermediate language looks very much like assembly language but it’s level is higher. For example, only a push operation is used to push onto the stack. In intermediate code each instruction is of either of these two forms:
    •  Three-address form: (binary) x := y op z
    • (unary) x := op y

If the operation is of some complicated form then it is decomposed to these form using temporary registers and every sub-expression is given a name. IC can have unlimited/large number of registers.

  • A function called igen(e,t) is used to represent it which generates the intermediate code for e and stores it in register t.
igen(e1+e2, t)
     igen(e1,t1)            //t1 is a fresh register
     igen(e2,t2)            //t2 is a fresh register
     t := t1+t2

using unlimited number of register makes the code simpler.

Compiler Designing W07L1304

COOL Semantics II

  • The declared object for a class C would return list of argument with their types and values.
 Class(C)={a1 : T1 ← e1, a2 : T2 ← e2... an : Tn ← en}

If class C is inherited from other class, then the list of the attributes generated would in same order as they are in memory, i.e. first come the superclass’s attributes then the attributes of class.

These are the rules for creating a new object of any class:

gif (1)

See the self object is the allocated object, first three lines are for allocating memory to the class object and remaining for initializing it. Defaults are given to values initially and see that all the attributes are in scope.

  • Discussion about the informal semantics of e0.f(a1,a2…an)
    • Evaluation of the arguments.
    • evaluate target object e0 and let X is the dynamic type of the target object e0
    • Fetch from X the definition of f with n arguments.
    • create n new locations and make environment mapping from attributes to these new locations.
    • set self to target object and evaluate f’s body.
  • impl(A,f)={args, f_body} –lookup in memory of function
  • Example of above @14:00 min, in the example, E have the formal arguments and self attributes. S contains the locations of attributes and formal arguments.

[II]

  • Operational semantics do not cover all the cases.
  • When function impl(A, f) is used, there is not this case of checking that if f exists in A or not that work is already been done by type checker. But there are some error that type checker cannot prevent:
    • Heap overflow
    • string out of range
    • division by zero
    • dispatch on void
  • Operational semantics are good if portability is expected.

Compiler Designing W07L1303

COOL Semantics I

  • Some judgement rules are given:

gif

  • CodeCogsEqn (3)In the case above, store is not change as there is no side-effect of evaluating the expression.
  • if id=self then v=so.
  • Judgement rules where value of store changes due to the side-effect of expressions.

CodeCogsEqn (4)

CodeCogsEqn (5)CodeCogsEqn (6)

  • Example: addition, 8:06 minute: if then else 15 minute: while loop 15:53 minute: let 17:40 minute.
  • Let judgement rule: to change E newloc(S) is used.CodeCogsEqn (7)

Compiler Designing W07L1302

Operational Semantics

  • It has similar rules as type checking:
For type checking, the rules are defined like:
     Context ⊦ e : C
          means the under some conetext e has type C.
Similarly, in evaluation rules 
     Context ⊦ e : v
          means that under some context e evaluates v.

For example,

CodeCogsEqn (2)

  • There are two function to track variables and their values:
    • environment(variable) = memory location of the variable; it stores the variables which are in scope E=[a:loc1, b:loc2].
    • store(memory address) = value at that address. S = [loc1→ 5, loc2 → 7]; to update the value at some location: S’=S[12/loc1].
  • An class object is stored as X(a1=l1, a2=l2 … an=ln) where X is the object and ai and li are attribute and location respectively.
  • Classes not having any attributes like Int(2), Bool(true), void.
  • Evaluations judgement is:
so, E, S ⊦ e:v, S'   //so:self object; E:environment; S:Store; S':new store; e:expression;
                     //v:value of the expression
  • After evaluation so and E do not change but S may change.
  • The judgement is only valid when e terminates.

Compiler Designing W07L1301

Semantics Overview

  • When the programming language was being defined, these tools are used:
    • Tokens for lexical analysis
    • Context free grammar for parsing
    • Type checking for semantic analysis
    • The evaluation rules for code generation and optimization
  • But the code generation is inefficient. Assembly language code generation code contains irrelevant details. So a complete descriptive and less restrictive language is needed.
  • Operational semantic is used to generate code instead of assembly language. It descibes program evaluation via execution rules.
  • Other ways can be:
    • Denotational semantics: Here the program is mapped into a mathematical sense. Although its an elegant way but poses complexity.
    • Axiomatic semantics: It describes program via logical rules. Like if execution of the program begins with satisfying X then it will end with Y.

Compiler Designing W07L1206

Object Layout I: Attributes

  • Object layout is the structure for storing an object of a class in memory. According to OO implementation techniques, if B inherits from class A then every place object of B can be used where A’s object is expected. This means that the structure is such that the class B’s implementation in memory should be same until it is same as A.
  • Every attribute is stored at some fixed offset in object. Also object have contiguous memory allocation for attributes and its header.
  • Object layout for an object of class A:(contiguous memory allocation)

object

The first three entries are collectively called the header of the class. Class tag is an integer used to identify the class. Dispatch Pointer points to the dispatch table.

When a class inherits from A then layout till the attributes is the same, and this layout is extended for the attributes of the inherited class.

Object Layout II: Dispatch Table

  • Dispatch table contains the pointer to the functions and these functions remain at same offset in the class and all of its subclasses. If any subclass overrides to the function of its super class then it is at the same offset.
  • All the objects of the same class would use the dispatch table.