Global Optimization in Compiler Design

---

---

In computer science, we need compilers to convert programming languages to machineunderstandable codes. In compilers, there are several stages, among which optimization is an interesting and important step.

Our goal is not just to make a program that works but one that works well, which will save both time and resources. This is where global optimization comes into the picture. This phase in compilers has been designed to improve the efficiency of the generated object program. By streamlining the code, global optimization helps the programs run faster and consume less memory. Read this chapter to understand the basics of Global Optimization in Compilers.

What is Global Optimization?

Global optimization is a process within the compiler that identifies and eliminates inefficiencies in the code. Unlike local optimization that focuses on small, specific portions of code, global optimization looks at the entire program. It checks for redundant instructions, unreachable code, and other inefficiencies.

Global optimization is often referred to as machine-independent optimization. This is because it focuses on optimizing the logical structure of the program. This is independent of the hardware it will eventually run on.

Why is Global Optimization Important?

To get the importance of global optimization understand with examples. Let us imagine running a program that has unnecessary or repetitive operations. Not only does it slow down execution, but it also consumes extra resources. For example, if a loop recalculates the same value multiple times when the value could be calculated once. It wastes computational effort. Global optimization steps in to identify these scenarios and fixes them.

In practical terms, global optimization ensures −

• Faster program execution
• Reduced memory usage
• A cleaner, more streamlined object program.

Examples of Global Optimization

To understand how global optimization works, let us see two examples.

Example 1: Eliminating Unreachable Code

Consider this simple segment of code −

statement 1;
goto label1;
statement 2;
statement 3;
label1: statement 4;

Here, statement 2 and statement 3 are never executed because the program directly jumps to label1 after statement 1. These lines are termed as unreachable code. Global optimization identifies such code segments and removes them from the object program. By doing this, the final code becomes leaner and faster.

Example 2: Moving Loop-Invariant Code

This is a slightly more advanced concept, but it has a significant impact on performance. Let us take a code snippet to illustrate −

for (i = 1; i <= 100000; i++) {
   x = Math.sqrt(y); 	// square root calculation
   System.out.println(x + i);
}

Notice that the value of Math.sqrt(y) does not change with each iteration of the loop because y remains constant. However, the calculation is performed 100,000 times unnecessarily. The global optimization recognizes this inefficiency and modifies the code as follows −

x = Math.sqrt(y); 	// move outside the loop
for (i = 1; i <= 100000; i++) {
   System.out.println(x + i);
}

Here we can see the calculation is made outside the loop. This is eliminating 99,999 redundant calls to the sqrt method. This is saving a massive amount of computational resources.

Challenges in Global Optimization

We understood the benefits of global optimization. Let us see some challenges associated with this global optimization. For one, it can complicate debugging. In the loop example above, if y were to contain a negative value then the program would throw an error when calculating Math.sqrt(y). But because the optimization moves the calculation outside the loop, identifying the actual point of error becomes more difficult.

To address this, many compilers offer a switch to turn optimization on or off. Coders or developers can keep it off during debugging and switch it on once the program is finalized and ready for deployment.

Another challenge is when ensuring that optimized and unoptimized versions of the program behave exactly the same. This requires meticulous design and testing on the part of compiler developers.

Features of Global Optimization

Let us see some of the common features of global optimization include −

• Dead Code Elimination − Removing code that has no impact on the program's output.
• Common Subexpression Elimination − Identifying and reusing previously computed expressions to avoid redundant calculations.
• Loop-Invariant Code Motion − Moving calculations or assignments outside loops when their values do not change during iterations.
• Constant Folding − Replacing expressions with constant values wherever possible.

The Role of Developers in Handling Global Optimization

Compilers handle global optimization, but the developers play an important role too. We must write clean, modular code which makes it easier for the compiler to optimize the program. For instance, explicitly defining constants and avoiding overly complex logic can help the compiler perform better.

It is also important for developers to understand the limitations of global optimization. For example, heavily relying on it to fix poorly written code is not a good practice. And it should be seen as an enhancement rather than a puzzling code.

Debugging and Optimization

Global optimization can make debugging more challenging. Consider the loop example again. If an error occurs in the Math.sqrt(y) calculation, the error message might point to the line outside the loop rather than its original location within the loop.

To handle this, developers should −

• Use the compiler's optimization switch to turn it off during debugging.
• Test thoroughly after enabling optimization to ensure the program behaves as expected.
• This balance between debugging and optimization is critical to creating high-quality software.

Global Optimization Techniques

Let us understand some of the key global optimization techniques.

Constant Propagation

Constant propagation replaces variables with their known constant values across the entire program. It helps in reducing the unnecessary calculations. Take a look at the following example −

Example: Before Optimization −

int x = 5;  
int y = x + 3;  
int z = y * 2;  

Intermediate Representation (IR) −

(MOV, 5, , x)  
(ADD, x, 3, y)  
(MUL, y, 2, z)  

After Constant Propagation − Since x = 5, the compiler replaces x with 5 −

(ADD, 5, 3, y)
(MUL, 8, 2, z)  

It simplifies further −

(MOV, 8, , y)  
(MOV, 16, , z)  

Here, we can see the compiler eliminates unnecessary arithmetic and directly assigns values to the variables.

Common Subexpression Elimination (CSE)

Another technique is the CSE. This technique detects duplicate expressions appearing multiple times and reuses the previously computed value instead of recalculating it. Take a look at the following example −

Example: Before Optimization −

a = b + c;  
d = b + c + e;  

Intermediate Representation (IR) −

(ADD, b, c, T1)  
(ADD, T1, e, d)  

Since b + c is computed twice, we reuse T1 instead:

After CSE Optimization −

(ADD, b, c, T1)  
(ADD, T1, e, d)  

The redundant addition is removed, which improves the efficiency.

Loop-Invariant Code Motion

If a code statement produces the same result in every iteration, it should be moved outside the loop to reduce redundant execution. Take a look at the following example −

Example: Before Optimization −

for (i = 0; i < 10; i++) {  
   sum = sum + a * 5;  
}    

Intermediate Representation (IR) −

(LBL, L1)  
(TST, i, 10, <, L2)  
(MUL, a, 5, T1)  
(ADD, sum, T1, sum)  
(ADD, i, 1, i)  
(JMP, L1)  
(LBL, L2)  

After Moving Loop-Invariant Code − The expression a * 5 does not change, so we move it outside the loop −

(MUL, a, 5, T1)  # Compute once before loop  
(LBL, L1)  
(TST, i, 10, <, L2)  
(ADD, sum, T1, sum)  
(ADD, i, 1, i)  
(JMP, L1)  
(LBL, L2)  

This method reduces unnecessary multiplication inside the loop. And it is improving the execution speed.

Dead Code Elimination

Dead code elimination removes unreachable or unused code that does not affect the program’s output. Take a look at the following example −

Example: Before Optimization −

int x = 10;  
x = 20;  
y = x * 2;     

Intermediate Representation (IR) −

(MOV, 10, , x)  
(MOV, 20, , x)  
(MUL, x, 2, y)  

Since x = 10 is never used, and the compiler removes it:

After Dead Code Elimination −

(MOV, 20, , x)  
(MUL, x, 2, y)  

Observe that we are keeping the useful instructions only, which in turn helps in reducing memory usage and improving efficiency.

Register Allocation Across Basic Blocks

The compiler reuses CPU registers across multiple blocks instead of storing values in memory. Take a look at the following example −

Example: Before Optimization −

(MOV, a, R1)  
(ADD, b, c, R2)  
(STORE, R1, a)  
(STORE, R2, T1)       

Notice that we are using registers here, which is why the values are unnecessarily stored back in the memory.

After Register Allocation Optimization −

(MOV, a, R1)  
(ADD, b, c, R2)  

By keeping the values in registers, the memory access is reduced, which leads to faster execution.

Real-World Applications of Global Optimization

We have seen a ser of optimization techniques. Let us see some of the real world applications. The Global optimization techniques are used in −

• Compilers like GCC and LLVM − These techniques improve the performance at the machine code level.
• Just-In-Time (JIT) Compilers − This is used in Java, Python, and JavaScript engines to speed up execution.
• Embedded Systems − This is reducing instruction count helps in low-power and resource-limited environments.

Comparison of Global Optimization Techniques

The following table compares and contrasts the purpose and performance of the different global optimization techniques we discussed above −

Conclusion

In this chapter, we covered the concept of global optimization and its importance in making programs efficient. Starting with the basics, we understood how global optimization works and how it differs from local optimization.

We explained through examples how unreachable code can be removed and loop-invariant code can be moved to enhance performance. We also highlighted the challenges and limitations of this process, including its impact on debugging.

Global optimization is a powerful feature in compilers. When it is used effectively, it can significantly improve the performance of a program and save both time and resources in the process.