Re: Predicate-Aware Live-Range Analysis / Gillies et al. Work

andreybokhanko@mail.ru wrote:
> 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?


Andrey,


      Actually our approach will handle this case. The details are in how
the graph represents the liveness of the variable. With respect to
your example:


- At line 11 the variable is live under P0 or the whole universe
- After applying the effects of line 5, the variable will be live under
P0 - P2 = P1
- After applying the effects of line 4, the variable will no longer be
live.
- The same applies on the other branch of the if.


The key to understanding this situation is to realize that the P1/P2
and P3/P4 are separate partitions of the universal predicate P0. For
more details on the graph repesentation you should look at Johnson and
Schlansker's paper from the same conference.


Thanks for your interest in our work.


Dave

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