CSCE 434 Lecture 37

« previous | Friday, November 22, 2013 | next »

Lecture Slides

Subexpression Elimination

any DAG node that has more than one parent should only be calculated once.

To build a DAG, teach makeleaf() and makenode() to catch common subexpressions

• hash on (operator, left, right)
• each node gets a unique name
  • leaves labeled with variable or constant identifier
  • interior nodes labeled with operators

Common subexpressions only happen within expressions (obviously)

• will not work on assignments, loops, etc.
• exception to this rule: pure function memoization (if a function has no side-effects, calls to that function with a certain set of parameters can be computed once.

Example

Original Code:

a = b + c
b = a - d
c = b + c
d = a - d

Labeled code:

a0 = b0 + c0
b1 = a0 - d0
c1 = b1 + c0
d1 = a0 - d0

Notice how each redefinition creates a "new instance" (i.e. it kills/clobbers all previous definitions)

Resulting DAG:

c1   [label="+"];
b1d1 [label="-"];
d0   [label="d0"];
a0   [label="+"];
b0   [label="b0"];
c0   [label="c0"];
c1 -> b1d1;
c1 -> c0;
b1d1 -> a0;
b1d1 -> d0;
a0 -> b0;
a0 -> c0;

Optimal Code for Simple Machine Model

Simple machine model with $n$ registers and 2-address instructions (assumes destination of a 2-source operation must be one of the sources)

More Realistic Machine Model

Delayed-load

• Results to a load appear $delay$ cycles later.
• Execution may continue unless the result of the load is needed.
• Premature reference causes hardware to stall/block (interlock)
• Goal: find things to do while memory is doing its thing.
• We can move a load instruction to be $delay$ cycles earlier than when it's used.