Quadratic bottleneck in SSA propagation engine

[Diego Novillo]

Jan Hubicka wrote on 09/15/06 04:46:

> Does this appear to make sense?
> 
A couple of things are not clear to me (below).

> Bootstrapped/regtested i686-linux.  I can get some more performance data
> (gerald's testcase, tramp3d, combine, insn-attrtab) if this seems appropriate
> for mainline.
> 
Yes, please.  Let's wait for 4.3, unless you can prove good speedups
across the board.

> *************** add_control_edge (edge e)
> *** 275,281 ****
>     if (TEST_BIT (bb_in_list, bb->index))
>       return;
>   
> !   cfg_blocks_add (bb);
>   
>     if (dump_file && (dump_flags & TDF_DETAILS))
>       fprintf (dump_file, "Adding Destination of edge (%d -> %d) to worklist\n\n",
> --- 295,316 ----
>     if (TEST_BIT (bb_in_list, bb->index))
>       return;
>   
> !   /* Only PHI nodes needs updating if the BB was reachable previously.  */
> !   if (TEST_BIT (executable_blocks, bb->index))
> !     {
> !       tree phi;
> !       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
> ! 	if (!STMT_IN_SSA_EDGE_WORKLIST (phi))
> ! 	  { 
> ! 	    STMT_IN_SSA_EDGE_WORKLIST (phi) = true;
> ! 	    if (PHI_NUM_ARGS (phi) > 4)
> ! 	      VEC_safe_push (tree, gc, expensive_varying_ssa_edges, phi);
> ! 	    else
> ! 	      VEC_safe_push (tree, gc, varying_ssa_edges, phi);
> ! 	  }
> !     }
> !   else
> !     cfg_blocks_add (bb);
>   
simulate_block will already ignore blocks that have already been
executed.  I'm not sure why you need this.

Spelling nit: s/incomming/incoming/

I'm interested in the VRP patch.  This propagator patch will paper over
the real problem.  It's useful, though.