This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [tcb] Merge PHI nodes -- 7.4% reduction of PHI nodes.


Hello,

> Attached is a patch to merge PHI nodes.  Consider:
> 
>   # ptr_5 = PHI <0B(8), ptr_4(7)>;
> <L16>:;
> 
>   # ptr_1 = PHI <D.9200_13(1), ptr_5(9), D.9200_13(0)>;
> <L18>:;
>   if (ptr_1 == 0B) goto <L21>; else goto <L20>;
> 
> Note that we can merge the two PHI nodes.  That is, we can redirect
> incoming edges to <L16> to <L18> like so:
> 
>   # ptr_1 = PHI <D.9200_13(1), ptr_4(7), D.9200_13(0), 0B(8)>;
> <L18>:;
>   if (ptr_1 == 0B) goto <L21>; else goto <L20>;
> 
> Note that we expose one jump threading opportunity, namely the
> incoming edge from basic block 8, aside from direct benefits like
> fewer basic blocks, fewer SSA_NAMEs, and such.

I think this would be easier (and would avoid code duplication)
to teach tree-cfg.c:thread_jumps to do this optimization.  I.e. allow
threading over basic block that contains just phi nodes,
provided that the results of those phi nodes are only used in
arguments of the phi nodes at the block to that the edge is
redirected.

Umm... easier... it would need a major cleanup of
tree-cfg.c:thread_jumps, because that function is just mess now
(I can tell since I am the one responsible for the mess :-( )

> +  do
> +    {
> +      something_changed = false;
> +
> +      FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
> +	{
> +	  tree phi;
> +
> +	  /* Look for a basic block with PHI nodes.  */
> +	  if (!tree_forwarder_block_with_phi_p (bb))
> +	    continue;
> +
> +	  /* We have to feed into another block with PHI nodes.  */
> +	  if (!phi_nodes (bb->succ->dest))
> +	    continue;
> +
> +	  for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
> +	    bitmap_set_bit (vars, SSA_NAME_VERSION (PHI_RESULT (phi)));
> +
> +	  /* Now compute immediate uses for all the PHI nodes we care
> +	     about.  */
> +	  compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS,
> +				  need_imm_uses_for);

This is not a good idea.  You may call compute_immediate_uses for
most of the basic blocks.  Since compute_immediate_uses performs a pass
over a whole program, you are likely to end up with a quadratic
behavior.

It would be probably better to run compute_immediate_uses just once,
recording uses for all phi results.

Zdenek


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]