Basic Blocks in Compiler Design

What are Basic Blocks in Compiler Design?

A Basic Block in Compiler Design is a block of code that contains a sequence of instructions that has only one entry point and one exit point. Let us break this statement into smaller pieces to understand it better.

Single Entry Point: There is only one way to enter a basic block. The control flow can only get to the beginning of the basic block from the immediately preceding block.

Single Exit Point: There is only one way to exit from a basic block which is the last statement of the block, we cannot jump from in between the blocks.

Three-address code It is an intermediate code generated by the compiler. Three-address code as the name suggests can only have at max three operands in a single statement.

Consider the code below for the expression $a = b * c + 5 / 6$:

The above code doesn't contain any branches or jump statements. It is only composed of sequences of sentences. There is only one way to get to this block of code which is the first statement function and the last statement is the only exit point for this block of code.

Consider another sequence of code:

The above code contains a goto statement and therefore, it cannot be considered as a basic block.

Security Considerations

Compilers modify block structures to identify vulnerabilities in code and ensure valid control flow and transitions. The compiler changes the block layout to detect vulnerabilities. Various security checks are performed at block ends.

Two types of attacks possible are control flow integrity and data flow integrity.

• Control Flow Integrity(CFI) attacks are attacks performed by manipulating control flow to execute malicious code.
• Data Flow Integrity(DFI) attacks are attacks performed on data by unauthorized personnel leading to security breaches.

Performance

Positive Impact:

• Code is effectively optimized thus, leading to smaller and faster code.
• Performs code analysis and transformations for performance improvements.

Potential Overhead:

• Basic block identification and analysis add to compilation time.
• Optimizations can introduce extra costs sometimes.

Comparing positive and overhead impacts, the benefits of basic blocks outweigh potential overhead.

Algorithm

Before moving to the algorithm to partition into basic blocks, let us first understand the leader statement. We initially determine the set of leader statements, the first statements of each basic block.

Input

Input to the algorithm is a sequence of the three-address statements.

Output

The algorithm returns a list of basic blocks. Each of these basic blocks is returned with three-address statements in exactly one block.

Method

1. Leader Statement:

• The very first instruction in a block of code is considered a leader statement.
• Any target statement to the conditional or unconditional jump is also a leader statement.
• A statement that is immediately after a jump(conditional or unconditional) statement is also a leader statement.

2. Basic Block:

• Each of these leader statements is the very first statement of each of the basic blocks. The statement immediately before the next leader statement is the last statement of the previous basic block.

Example

Consider the source code for the dot product of two vectors a and b of length 20.

The three-address code for the above block of code can be generated as follows:

Let us identify the leader statements to get the basic blocks from the above three-address code.

• Statement 1 is always a leader statement.
• In the $3^{rd}$ statement we enter a loop and thus, its first statement is the leader statement.

Thus, there are two leader statements and the basic blocks formed are:

• Basic Block 1: STATEMENT (1) TO (2)
• Basic Block 2: STATEMENT (3) TO (12)

Basic Block Construction

Let us look at another example to understand the construction of a basic block.

Certainly! Let's consider another example and generate its three-address code. After that, we'll identify the leader statements to form basic blocks.

The three-address code for the above block of code can be generated as follows:

There are four basic blocks formed:

1. Basic Block 1: STATEMENT (1) TO (3)
2. Basic Block 2: STATEMENT (4) TO (6)
3. Basic Block 3: STATEMENT (7) TO (9)
4. Basic Block 4: STATEMENT (10) TO (11)

Explanation

Now, let's identify the leader statements to form Basic Block in Compiler Design:

• Statement 1 is always a leader statement.
• Statement 4 is a leader statement as it is the target of a conditional jump.
• Statement 7 is a leader statement, the first statement after the conditional jump.
• Statement 10 is a leader statement as it is the target of an unconditional jump.

Each Basic Block in Compiler Design represents a sequence of instructions with a single entry and exit point.

Transformations on Basic Blocks

Optimization

Code written may not always be optimal. This is due to machine-level instructions and addresses not known to the programmer, optimization by hand requires more effort and time, and advanced architecture requires certain optimization.

There are two types of optimizations:

• Machine Independent Optimization
• Machine Dependent Optimization

Basic block construction is part of Machine Dependent Optimization.

Basic Block in Compiler Design enables optimization at local and global levels.

• Local optimizations focus on individual blocks improving their efficiency.
• Global optimizations include loop optimizations, function inlining, register allocation, etc. by analyzing interactions between blocks across larger code sections.

These optimizations aim to reduce redundancy, improve execution speed, and minimize overall resource usage.

Transformations

Several transformations are applied to these basic blocks without changing the set of expressions computed by the block. In other words, without modifying the output or meaning of the code.

The transformations are performed on Basic Block in Compiler Design to improve the code's performance. The transformations allow compilers to apply a variety of analysis and transformation techniques resulting in structured and effective code without compromising the correctness of the program.

Structure-Preserving Transformations

Let us explore various structure-preserving transformations.

1. Common Subexpression Elimination: Common subexpression elimination is the optimization technique in the compiler that eliminates redundant computations by recognizing previously computed expressions.

In the above example, b + c is already computed and stored in a. This computation can be eliminated for f.

After elimination:

2. Dead-Code Elimination: Dead code elimination in compiler optimization techniques removes code that is never going to be executed and is not going to affect the program's output. It is often caused by the variables or computations which are never used in the program.

After dead-code elimination:

3. Renaming Temporary Variables Renaming temporary variables is done to remove name conflicts and improve code clarity. Using proper names for the variables is important as it defines their meaning as well as avoids conflicts.

After renaming temporary variables:

4. Interchange of Statements Interchanging statements refers to changing the positions of statements without changing the output or meaning of code. This improves performance and simplifies the code structure.

After statement interchange

Statement 1 and Statement 2 are independent and don't depend on each other's results. The compiler has determined that swapping their order could improve performance. Possible reasons for swapping could be reduced pipeline stalls and instruction level parallelism.

Algebraic Transformations

Algebraic transformations refer to changing a set of expressions computed by a basic block into an algebraically equivalent set but with reduced cost and computations.

For example:

1. $x := x + 0$ - Wasting time and space for this kind of computation is useless.
2. Another popular example is $x := x * 1$. There is no point in such calculations and they must be avoided.
3. $a := pow(5,2)$ calculates the square of 5. To simply calculate the square we can use the multiplication operator as $a := 5 * 5$ which reduces overall cost.