When a DAG is created, common subexpressions are detected. Also,creating a DAG makes it easy to see variables and expressionswhich are used or defined within a block.
DAGs also produce good code at code generation time. In Module11, we will see a code generation algorithm which produces good(but not optimal!) code from a DAG.
Example 6 shows a bubble sort procedure and a set of quadruplesto which it might be translated. Quadruples are an intermediaterepresentation consisting of a single operation, up to two operandsand a result. They are easier for humans to read than an abstractsyntax tree. The quadruples shown here are in "assignment statement" form.
EXAMPLE 6 IR for a bubble sort procedureFOR I := 1 TO n - 1 DO FOR J := 1 TO I DOIF A[J] > A[J+1] THEN BEGINTemp := A[J]A[J] := A[ J + 1 ]A[ J + 1 ] := Temp ENDI := 1GOTO ITestILoop:J := 1GOTO JTestJLoop:T1 := 4 * JT2 := A [T1] ; A[J]T3 := J + 1T4 := 4 * T3T5 := A[T4] ; A[ J + 1 ]IF T2 <= T5 GOTO JPlusT6 := 4 * JTemp := A[T6] ; Temp := A[J]T7 := J + 1T8 := 4 * T7T9 := A[T8] ; A { J + 1 ]T10 := 4 * JA[T10] := T9 ; A[J] := A[ J + 1 ]T11 := J + 1T12 := 4 * T11A[T12] := Temp; A [ J + 1 ] := TempJPlus:J := J + 1JTest:IF J < = I GOTO JLoopIPlus:I := I + 1ITest:IF I <= n - 1 GOTO ILoop
I := 1GOTO ITestILoop:J := 1GOTO JTestJLoop:T1 := 4 * JT2 := A [T1] ; A[J]T3 := J + 1T4 := 4 * T3T5 := A[T4] ; A[ J + 1 ]IF T2 <= T5 GOTO JPlusT6 := 4 * JTemp := A[T6] ; Temp := A[J]T7 := J + 1T8 := 4 * T7T9 := A[T8] ; A { J + 1 ]T10 := 4 * JA[T10] := T9 ; A[J] := A[ J + 1 ]T11 := J + 1T12 := 4 * T11A[T12] := Temp; A [ J + 1 ] := TempJPlus:J := J + 1JTest:IF J < = I GOTO JLoopIPlus:I := I + 1ITest:IF I <= n - 1 GOTO ILoop- The intermediate code shown in Example 6 is rather high-level. For machines which have no indexing modes, the references to A[...] will have to be computed by the compiler. Also, the IF statements really involve several quadruples (see Module 6). The multiplication by "4" could, alternatively, be done at code generation time. We do it here because it will give us more opportunities for optimization of our example.
Using "( )" to mean "contents of " and "addr" to mean "address of", the low-level quadruples for "Temp := List[i]" might be:
T1 := addr(List)T2 := T1 + Itemp := (T2)
- Similarly, if the array reference is on the left-hand side of an assignment statement as in "List[i] := temp", low-level quadruples would be:
T1 := addr (List)T2 := T1 + I(T2) := Temp
- Even if a machine has an indexing addressing mode, translating array references into their low-level format may allow optimizations (for example, if the subscript reference were a common subexpression).
Nevertheless, there will be numerous opportunities to improve the code sequence in Example 6.
- The program of Example 7 contains cycles which may be loops. Determining loops is a major activity of control flow analysis. Creating basic blocks and a control flow graph are two steps toward this process. In the next section, we will formalize the process of determining a loop in a control flow graph.
