Local Optimization in Compiler Design

---

---

Optimization is an important phase in compilation. There are several types of optimizations. We covered the concept of global optimization in an earlier chapter and here we will explain the role of local optimization.

When we want to make programs faster, it is easy to imagine big changes or complicated solutions. But sometimes, it is the small changes that matter the most. Local optimization is such a phase in compilers because it focuses on improving specific parts of the code. By carefully checking the sequences of instructions in our local optimization, it makes the object program smaller and faster.

In this chapter, we will see what local optimization is and why it’s useful.

What is Local Optimization?

Local optimization is all about efficiency. It is done by targeting small sections of code, usually within a block or function, to make them better. Unlike global optimization that focuses on the entire program, local optimization works on smaller, localized parts of the code.

Local optimization is sometimes called machine-dependent optimization because it improves instructions in ways specific to the target machine. By doing so, local optimization gives us the object program with fewer resources while maintaining the same output.

Why Local Optimization is Important?

We must understand why local or machinedependent optimization is needed. Imagine you are carrying groceries from the car to your house. If you take one item at a time, it will be exhausting. But if you optimize by carrying a few items together, then you will save time and effort. Local optimization works the same way.

In programming, a poorly optimized sequence of instructions might waste resources. Here in performing unnecessary calculations or duplicating effort. The Local optimization fixes this by simplifying those instructions. And as a result it words faster and lower memory usage.

Example of Local Optimization

To understand local optimization properly, let us see an example. Consider this code fragment, where the goal is to calculate the sum of three variables, a + b + c −

lw $t0, a         # Load a into register $t0  
lw $t1, b         # Load b into register $t1  
add $t2, $t1, $t0 # Add a and b, store result in $t2  
sw $t2, temp1     # Store the sum (a + b) into temp1  
lw $t2, temp1     # Load temp1 back into register $t2  
lw $t1, c         # Load c into register $t1  
add $t2, $t1, $t2 # Add c to (a + b), store result in $t2  
sw $t2, temp2     # Store final result (a + b + c) into temp2  

This code works, but it is not efficient. If we look closely at the lines marked with temp1, the value of (a + b) is stored in memory. It is only to be loaded back into the register before being used. This extra step does not actually help. It just slows things down.

Optimized Sequence of Instructions

After applying local optimization, the unnecessary load/store operations are removed. The optimized code looks like this −

lw $t0, a         # Load a into register $t0  
lw $t1, b         # Load b into register $t1  
add $t2, $t1, $t0 # Add a and b, store result in $t2  
lw $t1, c         # Load c into register $t1  
add $t2, $t1, $t2 # Add c to (a + b), store result in $t2  
sw $t2, temp2     # Store final result (a + b + c) into temp2  

Here, by skipping the temp1 step, we can eliminate two instructions. This small change might not seem like a big changes, but it can have a noticeable impact. This is when in larger programs or repeated operations.

Techniques in Local Optimization

Local optimization provides a handful of clever tricks to clean up code. Let us see a few key techniques −

Load / Store Optimization

As we saw in the example, unnecessary load and store operations can be removed. It reduces memory access and makes the program faster.

Constant Folding

If a value can be calculated at compile time, the compiler replaces the calculation with the result. For example −

int x = 3 * 5;

Instead of performing the multiplication during program execution, the compiler can directly assigns x = 15.

Eliminating Redundant Instructions

Sometimes the same instruction appears more than once without any changes to the inputs. And local optimization gets rid of these duplicates.

Strength Reduction

Sometimes it involves replacing expensive operations with cheaper ones. For instance, multiplying by 2 can be replaced with a left shift operation. This is faster on most machines.

Challenges in Local Optimization

We understood the benefits of local optimizations; let us now check out its limitations −

• Trade-offs − Simplifying one part of the code might make another part less efficient. Striking the right balance can be a little challenging.
• Machine-Dependence − Because local optimization often tailors instructions to specific hardware, it may not work as well across different machines.
• Code Clarity − Highly optimized code can be harder to understand or debug. This is especially for developers who do not write it.

Although local optimization focuses on small sections, its benefits add up. So by improving individual blocks of code, it contributes to the overall performance of the program. It is like fixing potholes on a road. It may look not as major as building a new highway, but it makes the trip smoother and faster.

At the same time, it is important to remember that local optimization is just one piece of the entire work. It works best when combined with other optimization techniques, like global optimization or better algorithm design.

Key Local Optimization Techniques

In this section, we will discuss some of the important local optimization techniques in detail.

Constant Folding

This method is interesting. This evaluates constant expressions at compile-time rather than runtime. If an arithmetic operation involves only constants then the compiler precomputes the result and replaces the expression with a constant value.

Example: Before Optimization

int x = 5 * 2;  
int y = x + 10;  

Intermediate Representation (IR) −

(MUL, 5, 2, x)  
(ADD, x, 10, y)    

After Constant Folding,

Since 5 * 2 = 10, the compiler replaces x with 10 −

(MOV, 10, , x)  
(ADD, 10, 10, y)    

It simplifies further to −

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

Here, the compiler removes unnecessary calculations and directly assigns values. This simple trick makes quite optimized.

Common Subexpression Elimination

Common Subexpression Elimination (CSE) identifies and removes duplicate expressions within a basic block. If an expression repeats, then the compiler computes it once and reuses the result.

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)    

Here, we can see this is eliminating redundancy. And reducing the instruction count.

Dead Code Elimination

Dead code elimination technique removes the statements that have no impact on the program’s output.

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, so the compiler will remove it after optimization.

After Dead Code Elimination,

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

It removes unnecessary instructions improving the performance.

Strength Reduction

Here the strength reduction replaces computationally expensive operations with simpler, faster operations.

Example: Before Optimization

x = y * 8;        

Multiplication is costly, but y * 8 can be rewritten as −

x = y << 3;         

Intermediate Representation (IR)

(SHL, y, 3, x)         

Shifting (SHL) operation is faster than multiplication. This is improving performance.

Peephole Optimization

Peephole optimization is one of the mostly discussed optimization schemes. It scans a small set of instructions (a peephole) in a basic block and replaces inefficient patterns with optimized versions.

Example: Before Optimization

(MOV, x, R1)  
(ADD, R1, 0, R1)          

Since adding 0 does nothing, then the compiler removes the instruction −

After Peephole Optimization,

(MOV, x, R1)           

This makes the instruction sequence shorter and faster.

Example: Applying Multiple Local Optimizations

Consider the following Java expression −

int a = (x + 2) * (x + 2);             

The unoptimized atom sequence is generated by the compiler −

(ADD, x, 2, T1)  
(ADD, x, 2, T2)  
(MUL, T1, T2, a)               

We have seen a set of optimization techniques. If we see them in action we can understand they are quite useful. For example, the Common Subexpression Elimination (CSE) this is recognizing that x + 2 is computed twice, we store it once and reuse it.

Strength Reduction − If MUL is by a power of two, we replace it with a shift operation.

Optimized Code Using Local Techniques −

(ADD, x, 2, T1)  
(MUL, T1, T1, a)                 

Here, only two operations remain, this is majorly improving efficiency.

Real-World Applications of Local Optimization

Local optimization is used in −

• Compilers (GCC, LLVM, Clang) − This makes them efficient execution of compiled code.
• Embedded Systems − Optimizing individual blocks and reduces execution time in low-power devices.
• JIT Compilers (Java, JavaScript, Python) − Improves the runtime performance for interpreted languages.

Comparison of Local Optimization Techniques

The following table highlights the purpose and effects of different local optimization techniques −

Conclusion

In this chapter, we explained the concept of local optimization and its role in making programs faster and more efficient. Starting with the basics, we explored how local optimization focuses on small sections of the code and why it is so important.

Through a simple example, we demonstrated how removing unnecessary load/store instructions simplifies the code. We also touched upon key techniques like constant folding and load/store optimization along with the challenges that come with this process.