# Class 39: Code Improvement, Concluded

Back to Additional Improvement Techniques. On to Type Inference.

Held Friday, December 6, 2002

Summary

Today we conclude our exploration of code improvement.

Notes

• Please bring questions on the final next week.

Assignments

Overview

• Sample loop from last class
• Improved version
• Identifying loops

## Review

• Here's the Pascal code we started with
```for i := 1 to n
for j := 1 to n
A[i,j] := B[j,i];
```
• Assume arrays are in row-major order Where in memory is A[i,j]?
• base of A + cell-size*(n*(i-1) + j-1)
• base of A + cell-size*n*(i-1) + cell-size*(j-1)
• Here's a slight variant of the PAL code we converted to. (Yes, I've chosen the less-inteligent translation, but I think it's more interesting.)
```START_EVERYTHING:
MOV \$1 i
OUTER_LOOP:
MOV \$1 j
INNER_LOOP:
# Compute B[j,i]
ISUB j \$1 -> %T1
IMUL %T1 \$4 -> %T2
IMUL %T2 n -> T3
ISUB i \$1 -> %T4
IMUL %T4 \$4 -> %T5
MOV offset(B,%T6) -> %T7
# Compute A[i,j]
ISUB i \$1 -> %T8
IMUL %T8 \$4 -> %T9
IMUL %T9 n -> %T10
ISUB j \$1 -> %T11
IMUL %T11 \$4 -> %T12
MOV %T6 -> offset(A,%T13)
JEQ j n END_INNER_LOOP
INC j
JUMP INNER_LOOP
END_INNER_LOOP:
JEQ i n END_OUTER_LOOP
INC i
JUMP OUTER_LOOP
END_OUTER_LOOP:
```

## Basic Blocks

• The blocks
```Block 1
START_EVERYTHING:
MOV \$1 i

Block 2
OUTER_LOOP:
MOV \$1 j

Block 3
INNER_LOOP:
# Compute B[j,i]
ISUB j \$1 -> %T1
IMUL %T1 \$4 -> %T2
IMUL %T2 n -> T3
ISUB i \$1 -> %T4
IMUL %T4 \$4 -> %T5
MOV offset(B,%T6) -> %T7
# Compute A[i,j]
ISUB i \$1 -> %T8
IMUL %T8 \$4 -> %T9
IMUL %T9 n -> %T10
ISUB j \$1 -> %T11
IMUL %T11 \$4 -> %T12
MOV %T6 -> offset(A,%T13)
JEQ j n END_INNER_LOOP

Block 4
INC j
JUMP INNER_LOOP

Block 5
END_INNER_LOOP:
JEQ i n END_OUTER_LOOP

Block 6
INC i
JUMP OUTER_LOOP

Block 7
END_OUTER_LOOP:
```
• The edges
• 1 -> 2
• 2 -> 3
• 3 -> 4
• 3 -> 5
• 4 -> 3
• 5 -> 6
• 5 -> 7
• 6 -> 2

## Standard Optimizations

• Common Subexpression Elimination
```Block 3
INNER_LOOP:
# Compute B[j,i]
ISUB j \$1 -> %T1
IMUL %T1 \$4 -> %T2
IMUL %T2 n -> T3
ISUB i \$1 -> %T4
IMUL %T4 \$4 -> %T5
MOV offset(B,%T6) -> %T7
# Compute A[i,j]
MOV %T4 %T8			# ISUB i \$1 -> %T8
IMUL %T8 \$4 -> %T9
IMUL %T9 n -> %T10
MOV %T1 %T11		# ISUB j \$1 -> %T11
IMUL %T11 \$4 -> %T12
MOV %T6 -> offset(A,%T13)
JEQ j n END_INNER_LOOP
```
• Copy Propagation
```Block 3
INNER_LOOP:
# Compute B[j,i]
ISUB j \$1 -> %T1
IMUL %T1 \$4 -> %T2
IMUL %T2 n -> T3
ISUB i \$1 -> %T4
IMUL %T4 \$4 -> %T5
MOV offset(B,%T6) -> %T7
# Compute A[i,j]
MOV %T4 %T8			# ISUB i \$1 -> %T8
IMUL %T4 \$4 -> %T9	# IMUL %T8 \$4 -> %T9
IMUL %T9 n -> %T10
MOV %T1 %T11		# ISUB j \$1 -> %T11
IMUL %T1 \$4 -> %T12	# IMUL %T11 \$4 -> %T12
MOV %T6 -> offset(A,%T13)
JEQ j n END_INNER_LOOP
```
```Block 3
INNER_LOOP:
# Compute B[j,i]
ISUB j \$1 -> %T1
IMUL %T1 \$4 -> %T2
IMUL %T2 n -> T3
ISUB i \$1 -> %T4
IMUL %T4 \$4 -> %T5
MOV offset(B,%T6) -> %T7
# Compute A[i,j]
IMUL %T4 \$4 -> %T9	# IMUL %T8 \$4 -> %T9
IMUL %T9 n -> %T10
IMUL %T1 \$4 -> %T12	# IMUL %T11 \$4 -> %T12
MOV %T6 -> offset(A,%T13)
JEQ j n END_INNER_LOOP
```
• Common Subexpression Elimination
```Block 3
INNER_LOOP:
# Compute B[j,i]
ISUB j \$1 -> %T1
IMUL %T1 \$4 -> %T2
IMUL %T2 n -> T3
ISUB i \$1 -> %T4
IMUL %T4 \$4 -> %T5
MOV offset(B,%T6) -> %T7
# Compute A[i,j]
MOV %T5 %T9			# IMUL %T4 \$4 -> %T9	# IMUL %T8 \$4 -> %T9
IMUL %T9 n -> %T10
MOV %T2 %T12		# IMUL %T1 \$4 -> %T12	# IMUL %T11 \$4 -> %T12
MOV %T6 -> offset(A,%T13)
JEQ j n END_INNER_LOOP
```
• More to come ...

## History

Thursday, 29 August 2002

• First version, based somewhat on outlines from CS362 2001S.

Back to Additional Improvement Techniques. On to Type Inference.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Fri Dec 6 10:38:43 2002.
The source to the document was last modified on Wed Sep 4 10:08:38 2002.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2002F/Outlines/outline.39.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Glimmer Labs: The Grinnell Laboratory for Interactive Multimedia Experimentation & Research
glimmer@grinnell.edu