• PhiLookUp

Plan for O(1) PHI argument look up

Kazu Hirata is planning to implement O(1) PHI argument look up in the following order:

Stop assigning to PHI_ARG_EDGE

tree-cfg.c:tree_split_edge

• Call redirect_edge_and_branch first and then reinstall PHI arguments.

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.

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.

cfg.c:unchecked_make_edge, redirect_edge_succ.

• Update dest_index to EDGE_COUNT (e->preds) - 1.

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.

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.