Re: pretty-ipa merge 17: CD-DCE wrt cyclic CFGs fix

["H.J. Lu" <hjl dot tools at gmail dot com>]

On Sun, Apr 26, 2009 at 3:53 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> Hi,
> enabling CD-DCE on looping regions shows bug in current way it is removing
> control flow statements.
>
> ! ? ? ? /* There are three particularly problematical cases.
> !
> ! ? ? ? ?1. Blocks that do not have an immediate post dominator. ?This
> ! ? ? ? ? ? can happen with infinite loops.
> !
> ! ? ? ? ?2. Blocks that are only post dominated by the exit block. ?These
> ! ? ? ? ? ? can also happen for infinite loops as we create fake edges
> ! ? ? ? ? ? in the dominator tree.
> !
> ! ? ? ? ?3. If the post dominator has PHI nodes we may be able to compute
> ! ? ? ? ? ? the right PHI args for them.
> !
> ! ? ? ? ?In each of these cases we must remove the control statement
> ! ? ? ? ?as it may reference SSA_NAMEs which are going to be removed and
> ! ? ? ? ?we remove all but one outgoing edge from the block. ?*/
>
> This leads on several testcases in testuite and mpfr library to be miscompiled in
> a way turning finite dead loop to infinite. ?The problem here is that skipping
> the redirection and following to code removing all but first succestor edge
> of the BB might lead to picking "wrong" edge and removing everything except
> for loopback.
>
> The function is slightly wrong in two ways. ?First the formulation of algoritm
> says that edges should be forwarded to first "useful" postdomominator (i.e. BB
> containing live statements or one marked in control dependency because of PHI).
> Second it should be able to update the PHIs: since control dependent BB are
> marked as neccesary, we know that the edge being forwarded is control dependent
> BB. ?As such it is at post-dominance frontier of one of blocks corresponding to
> PHI arguments. ?Looking those up is easy and PHI argument can be copied by one
> corresponding to the edge found. (I hope that this is right with the actual
> implementation, there are multiple CD-DCE formulations and there is no specific
> paper quoted).
>
> This works for acyclic regions, since every random path through the acyclic
> region eventually leads to postdominance, so cfgcleanup and PHI merging does
> the job later.
>
> Updating however run into problem with VOP PHIs. ?Since those are not marked,
> the invariants here are broken. We can not be sure about control dependence of
> BB forwarded and we can not be sure that useless basic blocks are not
> containing live PHIs and they do in practice.
>
> So I made virtual PHIs to be simply marked for renaming when they are reached
> via new edges and in addition to that, unreachable basic blocks are removed,
> virtual PHIs there are inspected and in case they define result that ?might be
> used in live BBs, they are also sent for renaming.
>
> This patch bootstraps/regtests x86_64-linux with the infinite loop hack removed.
> Seems sane?
>
> Honza
>
> ? ? ? ?* tree-ssa-dce.c (bb_contains_live_stmts): New bitmap.
> ? ? ? ?(mark_stmt_necessary): Set it.
> ? ? ? ?(mark_operand_necessary): Set it.
> ? ? ? ?(mark_control_dependent_edges_necessary): Set it.
> ? ? ? ?(mark_virtual_phi_result_for_renaming): New function.
> ? ? ? ?(get_live_post_dom): New function.
> ? ? ? ?(forward_edge_to_pdom): New function.
> ? ? ? ?(remove_dead_stmt): Fix handling of control dependences.
> ? ? ? ?(eliminate_unnecessary_stmts): Remove dead BBs and PHIs.
> ? ? ? ?(tree_dce_init): Init new bitmap.
> ? ? ? ?(tree_dce_done): Free it.

This patch caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42717

-- 
H.J.