Predicate-Aware Live-Range Analysis / Gillie el al. Work

Dear Group,


There is a big problem while doing live-range analysis on predicated
code: if a definition of some variable Vn is guarded by a predicate, it
doesn't necessarily stops Vn's live range. So, one can't consider Vn to
be "dead" after predicate-guarded definition without further analysis.


Probably the most popular technique of such analysis is the one
described in the following well-known work: David M. Gillies, Dz-ching
Roy Ju, Richard Johnson, Michael Schlansker, "Global predicate
analysis and its application to register allocation", Proceedings of
the 29th annual ACM/IEEE International Symposium on Microarchitecture,
1996, pp. 114-125.


Still, I think that Gillies et al. approach can't handle some
situations. Here is an example:


1: P1, P2 = CMP(...);
2: P3, P4 = CMP(...);


3: IF (...) {
4: (P1) Vn = A; // definition is guarded by P1
5: (P2) Vn = B; // definition is guarded by P2
6: } else
7: {
8: (P3) Vn = C; // definition is guarded by P3
9: (P4) Vn = D; // definition is guarded by P4
10: }


11: ... = Vn; // Use of Vn


Let us assume that both "then" and "else" variants had been
if-converted in two separate hyperblocks:


                                  IF (...)
                                / \
                              / \
          (P1) Vn = A; (P3) Vn = C;
          (P2) Vn = B; (P4) Vn = D;
                              \ /
                                \ /
                                    ... = Vn;


Obviously, Vn's live range stops in each of these hyperblocks: in
"then" block by the definition guarded by P1 (line N4 of my example)
and in "else" block by the definition guarded by P3 (line N8).


But I think that this is impossible to prove with Gillies et al.
approach. Here are my reasonings:


1.) At line 11 Vn will be considered to be live under all four
predicates -- P1, P2, P3 and P4.
2.) At line 5 -- under P1, P3 and P4 (because the definition at line 5
kills Vn's liveness under P2).
3.) At line 4 -- under P3 and P4.
4.) At line 8 -- under P1 and P2 (because the definitions in "else"
block kill Vn's liveness uner P3 and P4).
5.) At line 3... again, under all four predicates! Because when
propagating live vectors between hyperblocks, you have to join them by
"OR".


So, according to my understanding, Gillies et al. approach is useless
in such situations. They concentrated their efforts on
single-hyperblock case, but the guts of my example is the presence of
multiple hyperblocks.


But my colleague from the USA claims that Gillie et al. technique is
perfectly suitable here! I read Gilles et al. article once, I read it
again, I re-read it third time -- still I don't understand how their
approach can handle this. I gave the article to my local colleague to
read -- he came to the same conclusions as me.


As for US-based colleague -- he is on the other part of the pond, so we
can't meet personally and discuss all these. E-mail conversations come
to be fruitless.


So, here is (finally!) my question. What do you think on my example? Is
it possible to handle it with Gillies et al. approach? Are there some
flaws / errors in my reasonings?


Thank you for your attention and your answers!


Andrey

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