Difference: CS255Spring09Discussions (3 vs. 4)

Revision 42009-02-22 - BinBao

Line: 1 to 1
META TOPICPARENT name="CS255Spring09"

CS255/455 Spring 2009 Discussion Board

Line: 7 to 7
Q: I had several questions that Bin answered via e-mail. He asked me to summarize them here. It was never really detailed in class exactly what you do when you find a redundant statement. My initial thought was to simply replace the right hand side of a redundant statement with the left hand side of the statement which it was repeating. I then noticed that the success benchmark in this class how many statements we could remove from a program, and this method didn't remove any, it optimized the program by decreasing the number of operations executed, but didn't change the statement count. My next thought was that you needed to delete the statement and replace subsequent instances of the left hand side with what you would have replaced the right hand side with, but that has issues since we're only doing local value numbering, and deleting a statement could have wide spread effects in other basic blocks. So the question is what action should we take when we find a redundant statement?
A: This question reveals a very important issue in compiler design, interaction among various compiler optimizations. It is true that we can not simply remove a redundant assignment during value numbering. But the later dead code elimination phase should be able to handle this properly. Here is an example to illustrate this.
a = b + c;
d = b + c;
e = b + d;
f = b + a;
should be transformed (by LVN) into
a = b + c;
d = a;
e = b + a; // here d get replaced with a.
f = e;
We also replaced d in e = b + d here, because that can eliminate a use to d. Then if there is no use to d after d = a, dead code elimination can remove d = a. However, in a real compiler, such a replacement is not always beneficial, because it will increase the lifetime of variable a, which might cause trouble to later register allocation phase. Again, here you can see the interaction among optimization phases. For our project, the metric of your compiler performance is the number of executed statements, so you don't need to worry about register allocation here.
URCC problems
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback