33 Code Generation Tree Rewriting and Introduction to Code Optimization

Rajeswari Sridhar

In this module, we learn to generate code using a template based approach. The template based approach to code generation is preceded by tree rewriting. We will also learn to understand the need for a code optimizer

 

33.1 Code-Gene rator generators

 

We have already seen three approaches to code generation namely, simple code generator, DAG based approach and dynamic programming strategy for code generation. All these approaches start from the scratch to generate code. Instead of this approach, we could use a black box based approach, where the black box would generate code if the input is given in a particular format using a template based approach. We need to however, convert o ur input to the input format of the code generator. The flow of the data is shown below:

 

Input instruction à Standard format à Template based code generator à code

 

The steps involved in any code generation approach would include p icking an evaluation order, assigning registers and selecting appropriate target- language instructions and these steps are done in this method also with an addition of converting the input to a standardized representation.

 

33.2Code-generation by tree rewriting

 

Let us assume that the evaluation order and registers allocation are completed, then the intermediate language could be converted to a representation as a tree. The tree should correspond to one of the pre-defined template. After matching with the template, there is a predefined code for every tree and code is generated. The sequence of flow for the code-generator is given in Figure 33.1.

 

Input tree is reduced into a single node by applying a sequence of tree-rewriting rules. The tree-writing rules is a translation scheme. The rewriting translation scheme has the following format:

 

Replacement ← template {action}

 

The LHS which is a Replacement is the reduction of the template and the RHS will have a tree representation of the input. Replacement is a single node of the tree and template is a tree. The action will be the code fragment that is to be generated. Table 33.1 discusses few tree-writing rules and their corresponding target code

The RHS is the expression “b+1” and hence the right sub-tree corresponds to Mb which is added to constant 1. The root of the tree is the assignment operator. The LHS corresponds to a[i]. To compute a[i] we first index the variable ‘i’ using the stack pointer register and using the base address of ‘a’ using the constant Ca we use the “ind” to indicate it is indexed operation and this forms the left sub-tree. The corresponding code for the above expression is given below which is generated by applying the rules as given in Table 33.1

 

  • Apply rule 1: MOV #a, R0
  • Apply rule 6: ADD SP, R0
  • Apply rule 7: ADD i(SP), R0
  • Apply rule 2: MOV b, R1
  • Apply rule 8: INC R1
  • Apply rule 4: MOV R1, *R0

The same tree rewriting rules can be implemented using syntax directed translation. The SDT for scheme construction and their corresponding target code is given below:

 

  • • regi  constc {MOV #c, Ri }
    • regi  mema {MOV a, Ri }
    • mem  := mem a regi {MOV Ri , a}
  •  mem  := ind regi regj {MOV Rj , *Ri }
    • regi  ind + constc regj {MOV c(Rj ), Ri }
    • regi  + regi ind + constc regj {ADD c(Rj ), Ri }
    • regi  + regi regj {ADD Rj , Ri }
    • regi  + regi const1 {INC Ri }

All the methods of code generations have its own advantages and disadvantages. Depending on the application we could use the corresponding algorithm for code generation.

 

33.3Code Optimization

 

The code that is being generated by the code generator using any one of the approaches discussed above need not be efficient. In addition the intermediate code that is generated also may not be efficient. DAG and instruction selection algorithms are used for getting efficient code. There is still some more means of improving the code generation. The following criteria are used for generating optimized code:

 

  • The optimized code should have the most benefit for the least effort that is being put in optimizing
  • Transformation should preserve the meaning of the program. This essentially emphasizes the fact that optimization should not change the output of the program  After incorporating the code optimization, the code that is generated is transformed to an optimized one. The following are some of the properties of transformation that a code optimization algorithm should ensure:
  • Transformation must on an average speed up the programs by a measurable amount. Optimization sometimes would slow down the program. Prevention should be taken for this.
  • Transformation must be worth the effort. Time should not be spent in writing optimization code rather than the actual code of the problem

33.4 Position of the Code optimizer

 

The code optimization algorithm needs to achieve a better performance. The code optimization could be implemented either at the intermediate code level or at the final code generation level. The position of the code optimizer is shown in figure 33.3.