------- Comment #22 from hubicka at gcc dot gnu dot org 2010-03-24 18:17 ------- Hi, I am teaching CD-DCE today so I took oppurtunity to figure out what happens.
1) The original formulation by Cytron et. al. has mistake in it. It claims that after removal of dead conditional one can take any edge and follow to it. This was bug I was solving while ago that closes empty loop to infinite loop. This was subsequently corrected by Rob Shiler. He added clause for redirection of dead conditionals to nearest useful postdominator and he also use reverse dominance frontiers instead of control dependency to mark useful statements. 2) Formulation in Cytron et al. and Morgan's textbook has both problem with not handling PHIs specially as we do. This has nothing to do with allowing constants in operands, but it fails on overlapping live ranges: a_1=exp1 a_2=exp2 if (test) empty else empty a_3=phi(a_1,a_2) here we must mark control dependency for the PHI operands. So Steven's argument about problems with constant arguments in PHIs seems false. 3) as Steven observed, problem is that BB6 is control dependent on itself. It has to be. Control dependency is for basic blocks and if something in basic block is useful, it must be executed same number of times as before. So one can not mark as useful only the source 4) I think problem is that we mark BB as useful for PHI argument while we really need to know if control flow arrived from that BB or other BB. Steven is right that splitting the edge and introducing new BB on the way is correct way to get this issue resolved. I believe that same effect can be by modifying mark_control_dependent_edges_necessary to exclude self control dependences when marking PHI edges (since we are not interested in BB itself). Say that we B is the basic block with PHI. C is BB of PHI source. Now if B postdominates C, then C' (slpitting edge from B to C) will sit in dominance tree just in between B and C and result of control dependence will be same as for C just with C omitted (since C' postdominate C). This follows from equivalency of control dependence and reverse dominance frontiers and way reverse dominance frontiers computatio nworks. If B does not postdominate C, then the split C' would be predecestor of B without any succesors. We already mark reverse dominance frontier of B (since it is live) so we should be happy here. I am testing patch to do that, it bootstraps and solves the testcase. Honza -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
