O(1) PHI argument look-up

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

Hi,

I would like to announce that I am working on O(1) PHI argument
look-up.

With this improvement, given an edge, we can find a corresponding PHI
argument in constant time.

Under the hood, at each basic block, the arrays of PHI nodes will have
the same order of edges (as Kenneth Zadeck talked about in the GCC
Summit).  edge_def will probably have a new member, dest_index, so
that we can find where an edge E is in E->dest->preds.

Attached is my implementation plan in the chronlogical order.  After
each sub-project, we should have a usable GCC.

I haven't decided whether I will do this on a branch or a personal
tree.

Comments are very welcome.

Kazu Hirata

Plan for O(1) PHI argument look up
==================================

Add an edge before we add PHI arguments
---------------------------------------

Everywhere
  Create an edge E before adding PHI args to E->dest

tree-phinodes.c:add_phi_arg
  Abort if the edge does not exist.  (This check is very expensive
  though.)

Add a CFG hook so that we can do something upon edge creation
-------------------------------------------------------------

cfghooks.h:cfghooks
  Add execute_on_new_edge (edge e).

cfghooks.c:execute_on_new_edge (edge e)
  New.  Call cfg_hooks->execute_on_new_edge if the function pointer is
  not null.

cfgrtl.c:rtl_cfg_hooks
  Add null on execute_on_new_edge.

cfgrtl.c:cfg_layout_rtl_cfg_hooks
  Add null on execute_on_new_edge.

tree-cfg.c:tree_cfg_hooks
  Add null on execute_on_new_edge.

cfg.c:unchecked_make_edge, redirect_edge_succ, redirect_edge_pred
  Call execute_on_new_edge.

Resize PHI nodes upon edge creation
-----------------------------------

tree-phinodes.c:reserve_phi_args_for_new_edge (basic_block bb)
  New.  Resize each PHI node at BB if necessary to take one more
  argument.

tree-cfg.c:tree_execute_on_new_edge (edge e)
  New.  Call reserve_phi_args_for_new_edge.

tree-cfg.c:tree_cfg_hooks
  Add tree_execute_on_new_edge on execute_on_new_edge.

tree-phinodes.c:add_phi_arg
  Abort if we have to resize any PHI node.

Clean up add_phi_arg
--------------------

tree-phinodes.c:add_phi_arg
  Pass "tree phi" instead of "tree *phi".

Everywhere add_phi_arg is used
  Adjust accordingly.

O(1) discovery of edge E in E->dest->preds
------------------------------------------

basic-block.h:edge_def
  Add dest_index.

cfg.c:remove_edge, redirect_succ
  Use dest_index to find edge E in E->dest->preds.

tree-cfg.c:verify_flow_info
  Verify that dest_index is consistent.

Line up PHI arguments with edges
--------------------------------

tree-phinodes.c:create_phi_node
  Zero the whole PHI argument array.
  Initialize num_args to EDGE_COUNT (bb->preds).

tree-phinodes.c:reserve_phi_args_for_new_edge (basic_block bb)
  Zero the new argument for each PHI node at bb.

tree-phinodes.c:add_phi_arg (tree phi, tree def, edge e)
  Fill in the argument using E->dest_index add_phi_arg_num.

tree-cfg.c:verify_flow_info
  Check that each PHI argument's edge matches the edge in the edge
  vector with the same index

Speed up phi_arg_from_edge
--------------------------

tree-flow-inline.h:phi_arg_from_edge (tree phi, edge e)
  Simply return e->dest_index.

Remove edge e in tree_phi_node
------------------------------

tree.h:PHI_ARG_EDGE(NODE, I)
  Define as "EDGE_I (bb_for_stmt ((NODE))->preds, (I))".

tree-phinodes.c:everywhere
  Don't read/write PHI_ARG_EDGE.

tree.h:tree_phi_node
  Remove e.

Speed up ssa_remove_edge
------------------------

tree-ssa.c:ssa_remove_edge
  Use phi_arg_from_edge and remove_phi_arg_num.

tree-phinodes.c:remove_phi_arg
  Remove.

Clean up uses of PHI_ARG_EDGE
-----------------------------

Everywhere where PHI_ARG_EDGE is used
  Replace each use with the definition of PHI_ARG_EDGE.
  Simplify as needed because we are likely to know
  "bb_for_stmt ((NODE))" without calling bb_for_stmt.

Clean up uses of phi_arg_from_edge
----------------------------------

Everywhere where phi_arg_from_edge is used
  Move phi_arg_from_edge out of the "for" loop visiting each PHI at a
  given basic block.