11.1 Preparation for Code Generation

11.2 Generation of Directives

11.3 Simple Code Generation from AST's

11.4 Standard Code Generation Strategies

11.5 Code Generator Generators

11.6 Register Allocation

11.7 A Better Code Generation Algorithm from AST's 11.8 Code Generation from DAG's

11.9 Retargetable Code Generation

11.10 Peephole Optimization

11.11 Summary

Web References

Exercises

11. 4 Standard Code Generation Strategies

A code generator can be written to recognize standard "templates":

  1. Assignment Statements

    A tree pattern of the form:

    generates a Move instruction:

      MOVE aPlace,T

    where aPlace represents the register, stack position or memory location assigned to a.

  2. Arithmetic Operations

    Suppose Op represents an arithmetic operation and consider an abstract syntax tree for the statement t = a Op b:

    One possible code sequence is: 

       	MOVE	aPlace,Reg
 	OP	bPlace,Reg
 	MOVE	Reg,T

    This is the method used in the example of the previous section. Of course, some machines require that special registers be used for operations such as multiplication and division.

    Example 2

  3. IF Statements

    IF statements can be represented by an abstract syntax tree such as:

    A typical code sequence is: 

       	(Code for condition)
 	BRANCHIFFALSE	Label1
 	(Code for Statements1)
 	BRANCH		Label2
 Label1: (Code for Statements2)
 Label2:

    Example 3 illustrates this for the statement:

      IF a < b THEN Max = b ELSE Max = a;

    In Example 3, aPlace and bPlace mey refer to the variables a and b themselves, if the machine allows two memory operands. For machines such as the 86-family (PC-clones) which require that one operand be in a register, the instruction:

      COMPARE aPlace,bPlace

    can be replaced by:

      MOVE Reg,aPlace
      CMP Reg,bPlace

    if neither a nor b have been previously assigned to a register.

  4. Loops

    Loops are just conditionals whose code is repeated. Consider the loop: 

     	LOOP While condition DO
 	   Statements
 	ENDLOOP

    An abstract syntax tree is:

    A reasonable code sequence is: 

       Label1:	(Code for NOT condition)
          BRANCHIFTRUE	Label2
 	(Code for Statements)
 	BRANCH		Label1
 Label2:

    Example 4 shows such a loop: