Defining a dead code elimination

 

  
Figure: Simple code with dead code highlighted by preconditions

Semantical information known at compile time can be used to simplify the code in many situations, such as for code specialization when a library function is used in a specific context, when all the code is not used and thus can be removed, for simplifying old code with useless parts or as back-end optimizer after some generic code transformations or compilation phases.

In PIPS for example, the preconditions give some affine predicates on integer variables of the program. These predicates can be used to simplify the code locally by partially evaluating it.

The simplest rule is to remove a statement when its predicate has no integer solution such as in an IF statement with a condition never satisfied such as $\{0==-1\}$ on Figure 3.

In fact this can be done further: since the IF is then empty, it can be removed itself if the condition computation as no side effect such as doing an I/O or touching a global variable. This last information is abstracted in PIPS by the proper effects resource that give information about the variables read or written for each statement.

For the loop optimizations, if the preconditions can prove that a loop cannot be executed, it can be removed. But if the computation of the loop bounds has some side effects, the loop must be replaced with these equivalent side effects, such as setting the index variable to its lower bound value if it is used later.

In the same way, if a loop can be proved to be executed only once, the loop can be replaced by its body and if the loop statement itself has a side effect, the same side effect should be kept. The information needed to implement this kind of transformation is the preconditions, the proper effects and of course the code itself.

Many rules such as the previous one can be easily added and implemented in a dead code elimination transformation in PIPS . In the following part we do not focus on the kind of optimizations that can be made but on how to use the PIPS framework to add such a transformation.