Re: [RFC] Mixed results with O(1) PHI arg lookup

[Kazu Hirata <kazu at cs dot umass dot edu>]

Hi Andrew,

> > o Every time an edge is added or removed, I call a callback function
> >   to appropriately resize PHI arg arrays.  This adds some overhead.
> >   In particular, we don't have PHI nodes in RTL.  Even in tree, not
> >   every basic block has PHI node.
> 
> > I thought about not adding CFG hooks and having add_phi_arg resize PHI
> > arrays the first time add_phi_arg is called after adding edges, but
> > this is a little dirty because we have some time period when
> > PHI_NUM_ARGS != EDGE_COUNT.
> 
> but in theory, whoever is creating the edge must know that a phi
> argument needs to be created for the new edge, and *should* be adding
> the phi argument immediately after creating the edge. Or edges. You
> could certainly create multiple edges , then add the PHI arguments.

Yes.  Just in case people don't put enough PHI arguments, I am zeroing
the new PHI args.  If a new PHI node is added, I zero the entire
array.  If a new edge is inserted, I zero the new PHI arg.  I guess I
could remove these zeroing.  I put them so that the garbage collector
wouldn't follow garbage pointers.

> I think it would be wrong to add the edges then allow other
> optimizations to proceed without fixing up the PHI arguments, so I don't
> see a problem having add_phi_arg() resize the PHI node to the number of
> edges.  In fact, this could be more efficient if you were adding 20
> edges for some reason, you only have to resize once if you create the 20
> edges, then add the phi args.

Surprisingly, in the specific case of compiling fold-const.i, the
number of calls to resize_phi_args is the same with or without my
patch.  In other words, after people dive into SSA and create PHI
nodes, they don't add enough edges to cause the resizing of PHI
arrays.

I have not profiled, but I bet my new CFG hooks are hurting
performance.  Here is a call tree for adding an edge.

  Any CFG operation to add an edge (or redirect an edge) in cfg.c
    execute_on_new_edge in cfghooks.c
      tree_execute_on_new_edge in tree-cfg.c
        reserve_phi_args_for_new_edge in tree-phinodes.c

Here is another call tree for removing an edge.

  Any CFG operation to remove an edge (or redirect an edge) in cfg.c
    execute_on_removing_edge in cfghooks.c
      tree_execute_on_removing_edge in tree-cfg.c
        remove_phi_args

Even in RTL or tree-level basic blocks without PHI node, we still have
calls to execute_on_new_edge and execute_on_removing_edge, which are
callbacks that are called upon adding or removing every edge.  An edge
redirection counts as one add and one remove operation.

Kazu Hirata