Cocke-Schwartz method of removing redundant expressions:
dep(A) = i iff (i) = A _
dep(i) = 1 + max( dependency of operands)
d = d + c * b;
a = d + c * b;
c = d + c * b;
|
|
triples |
dep(variable) a b c d |
dep(i) |
|
opt triples |
|
(1) |
* c b |
0 0 0 0 |
1 |
(1) |
* c b |
|
(2) |
+ d (1) |
0 0 0 0 |
2 |
(2) |
+ d (1) |
|
(3) |
= d (2) |
0 0 0 0 |
3 |
(3) |
= d (2) |
|
(4) |
* c b |
0 0 0 3 |
1 |
(4) |
same 1 |
|
(5) |
+ d (4) |
0 0 0 3 |
4 |
(5) |
+ d (1) |
|
(6) |
= a (5) |
0 0 0 3 |
5 |
(6) |
= a (5) |
|
(7) |
* c b |
6 0 0 3 |
1 |
(7) |
same 1 |
|
(8) |
+ d (7) |
6 0 0 3 |
4 |
(8) |
same 5 |
|
(9) |
= c (8) |
6 0 0 3 |
|
(9) |
= c (5) |