Machine Dependent Optimization

• Machine-dependent optimization is done after the target code has been generated and when the code is transformed according to the target machine architecture.
• It involves CPU registers and may have absolute memory references rather than relative references.
• Machine-dependent optimizers put efforts to take maximum advantage of memory hierarchy.

Basic Blocks

• Source codes generally have a number of instructions, which are always executed in sequence and are considered as the basic blocks of the code.
• These basic blocks do not have any jump statements among them, i.e., when the first instruction is executed, all the instructions in the same basic block will be executed in their sequence of appearance without losing the flow control of the program.
• A program can have various constructs as basic blocks, like IF-THEN-ELSE, SWITCH-CASE conditional statements and loops such as DO-WHILE, FOR, and REPEAT-UNTIL, etc.

Basic Block Identification

We may use the following algorithm to find the basic blocks in a program:

Search header statements of all the basic blocks from where a basic block starts:

 i. First statement of a program.

 ii. Statements that are target of any branch (conditional/unconditional).

 iii. Statements that follow any branch statement.

• Header statements and the statements following them form a basic block.

• A basic block does not include any header statement of any other basic block.

  Basic blocks are important concepts from both code generation and optimization point of view.

  

• Basic blocks play an important role in identifying variables, which are being used more than once in a single basic block.

• If any variable is being used more than once, the register memory allocated to that variable need not be emptied unless the block finishes execution.

Control Flow Graphs

• Basic blocks in a program can be represented by means of control flow graphs.
• A control flow graph depicts how the program control is being passed among the blocks. It is a useful tool that helps in optimization by help locating any unwanted loops in the program.

• In a control flow graph each node in the graph represents a basic block, i.e. a straight-line piece of code without any jumps or jump targets; jump targets start a block, and jumps end a block. Directed edges are used to represent jumps in the control flow.
• There are, in most presentations, 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.

• Because of its construction procedure, in a non-trivial CFG (i.e. one with more than zero edges), every edge A→B has the property that:

  outdegree (A) > 1 or indegree (B) > 1 (or both).

• The CFG can thus be obtained, at least conceptually, by starting from the program's (full) flow graph—i.e. the graph in which every node represents an individual instruction—and performing an edge contraction for every edge that falsifies the predicate above, i.e. contracting every edge whose source has a single exit and whose destination has a single entry.

• This contraction-based algorithm is of no practical importance, except as a visualization aid for understanding the CFG construction, because the CFG can be more efficiently constructed directly from the program by scanning it for basic blocks.

Example

Consider the following fragment of code:

0: (A) t0 = read_num

1: (A) if t0 mod 2 == 0

2: (B) print t0 + " is even."

3: (B) goto 5

4: (C) print t0 + “is odd."

5: (D) end program

In the above, we have 4 basic blocks: A from 0 to 1, B from 2 to 3, C at 4 and D at 5. In particular, in this case, A is the "entry block", D the "exit block" and lines 4 and 5 are jump targets. A graph for this fragment has edges from A to B, A to C, B to D and C to D.