Within-block optimization example

Source code:            Original tuples

a = 1 + 1;              1. ADD   1  1  a
b = a * x + 1;          2. MUL   a  x  t1 
a = 2 * x;              3. ADD   t1 1  t2 
c = a + 1 + b;          4. MOV   t2 -  b  
(assume a, b, c, x      5. MUL   2  x  t3 
 are live on            6. MOV   t3 -  a  
 block exit)            7. ADD   a  1  t4 
                        8. ADD   t4 b  t5 
                        9. MOV   t5 -  c  


Forward: Available expressions subexpressions and strength reduction

original               replacement             alist

1. ADD     1  1  a                             (a,2)
  (sr)                 MOV   2  -  a            "
2. MUL     a  x  t1    MUL   2  x  t1           "
  (sr)                 ADD   x  x  t1             
3. ADD     t1 1  t2                             "
4. MOV     t2 -  b                             (a,2),(t2,b)
5. MUL     2  x  t3    MOV   t1 -  t3          (a,2),(t2,b),(t1,t3)
6. MOV     t3 -  a                             (a,t1),(t2,b),(t1,t3)
7. ADD     a  1  t4    MOV   t2 -  t4          (a,t1),(t2,b),(t1,t3),(t2,t4)
8. ADD     t4 b  t5    ADD   b  b  t5           "
9. MOV     t5 -  c                              -

Backward: liveness and copy propagation
                                           usecounts
 original           replacements      a   b   c  t1  t2  t3  t4  t5  x
    -                   -             1   1   1  0   0   0   0   0   1
9. MOV  t5 -  c     9: NOP  
                    8: ADD  b  b  c   1   1   0  0   0   0   0   0   1
8. ADD  b  b  c        -              1   3   0  0   0   0   0   0   1
7. MOV  t2 -  t4    7: NOP            1   3   0  0   0   0   0   0   1
6. MOV  t3 -  a     6: NOP  
                    5: MOV  a  -  t3
                    3: ADD  a  1  t2
                    2: ADD  x  x  a   0   3   0  0   0   0   0   0   1
5. MOV  a  -  t3    5: NOP            0   3   0  0   0   0   0   0   1
4. MOV  t2 -  b     4: NOP  
                    3: ADD  a  1  b   0   3   0  0   0   0   0   0   1
3. ADD  a  1  b        -              1   0   0  0   0   0   0   0   1
2. ADD  x  x  a        -              0   0   0  0   0   0   0   0   2
1. MOV  2  -  a     1: NOP            0   0   0  0   0   0   0   0   2


Final Code (omitting NOPs)

2. ADD  x  x  a
3. ADD  a  1  b
8. ADD  b  b  c