Common subexpression elimination (CSE) using value numbering?

Hi, all


I am a graduated student from Department of Computer Science and
Information Engineering of National Taiwan University in Taiwan.


I have already read two papers:


1) Li Xu: Program Redundancy Analysis and Optimization to Improve
Memory Performance
2) Taylor Simpson: Value-Driven Redundancy Elimination


and implemented this technology into my dynamic compiler.


All things are perfect except one condition. I don't know how to
handle this condition in your optimization framework. The condition I
can't handle is as following:


A = B + C
A = D <-- this expression must define the same variable
as the previous one
E = B + C


After transfering to the SSA form:


A0 = B0 + C0
A1 = D0
E0 = B0 + C0


After applying the value numbering, I can say that A0 and E0 have the
same value. After applying AVAIL common subexpression elimination, I
can replace the last expression with "E0 = A0". Thus, the whole codes
become this one:


A0 = B0 + C0
A1 = D0
E0 = A0 <--


However, because both "A0" and "A1" have the same memory address, so
that I will get a wrong value when I execute the last expression after
the second expression.


The procedure described in these papers is:


1) When seeing the first expression, add A0 to the AVIN bitset of this
basic block.
2) When seeing the second expression, add A1 to the AVIN bitset of this
basic block, too.
3) When seeing the third expression, value numbering determines that
the value of E0 is equal to A0,
          and A0 has already been in AVIN of this basic block,
          thus the third expression is redundant and can be removed.
          However, if I remove the third expression, then the final value of
E will be wrong.
          Further more, I don't want to break the SSA form, because I don't
want to recalculate the SSA form
          again when I implement a dynamic compiler,
          so I replace the third expression using a MOV instruction rather
than removing it.
          However, not only remove it, but also replace it, the result will
be incorrect.


          One way removes the definition of E0, and the other way assigns a
wrong value to E0.


How can this condition be handled in this optimization framework? I
think I do misunderstand these papers, but after reading it several
times, I still can't find out what's the point. Could someone give me
some directions to help me handle this condition right?


Thank you, Thank you, Thank you very much.


-------------------------------------------
Wei
http://www.csie.ntu.edu.tw/~r88052/

Return to the comp.compilers page.
Search the comp.compilers archives again.