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]

[tree-ssa] Thread jumps to blocks with PHIs


This patch allows the jump threader to target a block with PHI nodes. 

Much like threading through a block with PHI nodes, we have to mark
variables appearing in those PHI nodes as needing to be rewritten out
of SSA form.

The only other complication is that we record the edge that leads to
the final target rather than the final block.  This makes the code
handle cases where out-of-ssa has to split the edge leading to
the target block.  Whee.  About a 7% increase in the number of threading
opportunities we find in the dominator jump threader and a tiny decrease
in the number of threading opportunities in the RTL threader (which is
precisely what we want -- to catch this stuff at the tree level rather
than at the RTL level).

Bootstrapped and regression tested i686-pc-linux-gnu.

Next up -- threading through blocks with realK statements...

	* tree-ssa-dom.c (edges_to_redirect, redirection_targets): Merged
	into a single varray "redirection_edges".
	(tree_ssa_dominator_optimize): Twiddle initialization, finalization
	and accessors to redirection information based on combining varrays.
	Get the threading destination from the saved edge rather than from a
	saved block.  Mark variables appearing in PHIs at the jump thread
	destination to be taken out of SSA form.
	(thread_across_edge): Save the edge into the destination block
	rather than the destination block itself.  Twiddle based on 
	combining varrays of jump threading information.
	* tree-flow.h (tree_block_forwards_to): Returns an edge rather than
	a block.
	* tree-cfg.c (tree_block_forwards_to): Return the edge leading to
	the target block rather than the target block itself.



Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.99
diff -c -p -3 -r1.1.2.99 tree-ssa-dom.c
*** tree-ssa-dom.c	17 Dec 2003 23:19:04 -0000	1.1.2.99
--- tree-ssa-dom.c	18 Dec 2003 21:18:06 -0000
*************** struct vrp_element
*** 145,153 ****
  
  static struct opt_stats_d opt_stats;
  
! /* Redirections scheduled by jump threading.   */
! static varray_type edges_to_redirect;
! static varray_type redirection_targets;
  
  /* A virtual array holding value range records for the variable identified
     by the index, SSA_VERSION.  */
--- 145,161 ----
  
  static struct opt_stats_d opt_stats;
  
! /* This virtual array holds pairs of edges which describe a scheduled
!    edge redirection from jump threading.
! 
!    The first entry in each pair is the edge we are going to redirect.
! 
!    The second entry in each pair is the edge leading to our final
!    destination block.  By providing this as an edge rather than the
!    final target block itself we can correctly handle redirections
!    when the target block had PHIs which required edge insertions/splitting
!    to remove the PHIs.  */
! static varray_type redirection_edges;
  
  /* A virtual array holding value range records for the variable identified
     by the index, SSA_VERSION.  */
*************** tree_ssa_dominator_optimize (tree fndecl
*** 308,315 ****
  			     true_false_expr_eq, NULL);
    VARRAY_TREE_INIT (const_and_copies, highest_ssa_version, 
"const_and_copies");
    VARRAY_TREE_INIT (nonzero_vars, highest_ssa_version, "nonzero_vars");
!   VARRAY_EDGE_INIT (edges_to_redirect, 20, "edges_to_redirect");
!   VARRAY_BB_INIT (redirection_targets, 20, "redirection_targets");
    VARRAY_GENERIC_PTR_INIT (vrp_data, highest_ssa_version, "vrp_data");
  
  
--- 316,322 ----
  			     true_false_expr_eq, NULL);
    VARRAY_TREE_INIT (const_and_copies, highest_ssa_version, 
"const_and_copies");
    VARRAY_TREE_INIT (nonzero_vars, highest_ssa_version, "nonzero_vars");
!   VARRAY_EDGE_INIT (redirection_edges, 20, "redirection_edges");
    VARRAY_GENERIC_PTR_INIT (vrp_data, highest_ssa_version, "vrp_data");
  
  
*************** tree_ssa_dominator_optimize (tree fndecl
*** 382,397 ****
  
        /* If some edges were threaded in this iteration, then perform
  	 the required redirections and recompute the dominators.  */
!       if (VARRAY_ACTIVE_SIZE (edges_to_redirect) > 0)
  	{
  	  basic_block tgt;
  	  unsigned int i;
  
  	  /* First note any variables which we are going to have to take
  	     out of SSA form.  */
! 	  for (i = 0; i < VARRAY_ACTIVE_SIZE (edges_to_redirect); i++)
  	    {
! 	      e = VARRAY_EDGE (edges_to_redirect, i);
  
  	      for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
  		{
--- 389,405 ----
  
        /* If some edges were threaded in this iteration, then perform
  	 the required redirections and recompute the dominators.  */
!       if (VARRAY_ACTIVE_SIZE (redirection_edges) > 0)
  	{
  	  basic_block tgt;
  	  unsigned int i;
  
  	  /* First note any variables which we are going to have to take
  	     out of SSA form.  */
! 	  for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
  	    {
! 	      e = VARRAY_EDGE (redirection_edges, i);
! 	      tgt = VARRAY_EDGE (redirection_edges, i + 1)->dest;
  
  	      for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
  		{
*************** tree_ssa_dominator_optimize (tree fndecl
*** 411,416 ****
--- 419,444 ----
  		      bitmap_set_bit (vars_to_rename, var_ann (arg)->uid);
  		    }
  	        }
+ 
+ 	      /* Similarly for our destination.  */
+ 	      for (phi = phi_nodes (tgt); phi; phi = TREE_CHAIN (phi))
+ 		{
+ 		  tree result = SSA_NAME_VAR (PHI_RESULT (phi));
+ 		  int j;
+ 
+                   bitmap_set_bit (vars_to_rename, var_ann (result)->uid);
+ 
+ 		  for (j = 0; j < PHI_NUM_ARGS (phi); j++)
+ 		    {
+ 		      tree arg = PHI_ARG_DEF (phi, j);
+ 
+ 		      if (TREE_CODE (arg) != SSA_NAME)
+ 			continue;
+ 
+ 		      arg = SSA_NAME_VAR (arg);
+ 		      bitmap_set_bit (vars_to_rename, var_ann (arg)->uid);
+ 		    }
+ 	        }
  	    }
  
  	  /* Take those selected variables out of SSA form.  This must be
*************** tree_ssa_dominator_optimize (tree fndecl
*** 419,432 ****
  	    rewrite_vars_out_of_ssa (vars_to_rename);
  
  	  /* Now redirect the edges.  */
! 	  while (VARRAY_ACTIVE_SIZE (edges_to_redirect) > 0)
  	    {
  	      basic_block src;
  
! 	      e = VARRAY_TOP_EDGE (edges_to_redirect);
! 	      tgt = VARRAY_TOP_BB (redirection_targets);
! 	      VARRAY_POP (edges_to_redirect);
! 	      VARRAY_POP (redirection_targets);
  
  	      if (dump_file && (dump_flags & TDF_DETAILS))
  		fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
--- 447,458 ----
  	    rewrite_vars_out_of_ssa (vars_to_rename);
  
  	  /* Now redirect the edges.  */
! 	  for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
  	    {
  	      basic_block src;
  
! 	      e = VARRAY_EDGE (redirection_edges, i);
! 	      tgt = VARRAY_EDGE (redirection_edges, i + 1)->dest;
  
  	      if (dump_file && (dump_flags & TDF_DETAILS))
  		fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
*************** tree_ssa_dominator_optimize (tree fndecl
*** 442,447 ****
--- 468,474 ----
  			 e->src->index);
  	    }
  
+ 	  VARRAY_CLEAR (redirection_edges);
  	  cfg_altered = true;
  	}
  
*************** tree_ssa_dominator_optimize (tree fndecl
*** 500,507 ****
    htab_delete (true_exprs);
    htab_delete (false_exprs);
  
!   VARRAY_FREE (edges_to_redirect);
!   VARRAY_FREE (redirection_targets);
  
    /* And finalize the dominator walker.  */
    fini_walk_dominator_tree (&walk_data);
--- 527,533 ----
    htab_delete (true_exprs);
    htab_delete (false_exprs);
  
!   VARRAY_FREE (redirection_edges);
  
    /* And finalize the dominator walker.  */
    fini_walk_dominator_tree (&walk_data);
*************** thread_across_edge (edge e)
*** 572,591 ****
  	  /* If we have a known destination for the conditional, then
  	     we can perform this optimization, which saves at least one
  	     conditional jump each time it applies since we get to
! 	     bypass the conditional at our original destination.  */
! 	  if (dest && ! phi_nodes (dest))
  	    {
- 	      basic_block forwards_to;
  	      int saved_forwardable = bb_ann (e->src)->forwardable;
  
  	      bb_ann (e->src)->forwardable = 0;
! 
! 	      forwards_to = tree_block_forwards_to (dest);
! 
  	      bb_ann (e->src)->forwardable = saved_forwardable;
! 	      dest = (forwards_to ? forwards_to : dest);
! 	      VARRAY_PUSH_EDGE (edges_to_redirect, e);
! 	      VARRAY_PUSH_BB (redirection_targets, dest);
  	    }
  	}
      }
--- 598,620 ----
  	  /* If we have a known destination for the conditional, then
  	     we can perform this optimization, which saves at least one
  	     conditional jump each time it applies since we get to
! 	     bypass the conditional at our original destination. 
! 
! 	     Note that we can either thread through a block with PHIs
! 	     or to a block with PHIs, but not both.  At this time the
! 	     bookkeeping to keep the CFG & SSA up-to-date has proven
! 	     difficult.  */
! 	  if (dest)
  	    {
  	      int saved_forwardable = bb_ann (e->src)->forwardable;
+ 	      edge tmp_edge;
  
  	      bb_ann (e->src)->forwardable = 0;
! 	      tmp_edge = tree_block_forwards_to (dest);
! 	      taken_edge = (tmp_edge ? tmp_edge : taken_edge);
  	      bb_ann (e->src)->forwardable = saved_forwardable;
! 	      VARRAY_PUSH_EDGE (redirection_edges, e);
! 	      VARRAY_PUSH_EDGE (redirection_edges, taken_edge);
  	    }
  	}
      }
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.173
diff -c -p -r1.1.4.173 tree-flow.h
*** tree-flow.h	17 Dec 2003 19:53:01 -0000	1.1.4.173
--- tree-flow.h	18 Dec 2003 21:21:07 -0000
*************** extern edge thread_edge (edge, basic_blo
*** 419,425 ****
  extern basic_block label_to_block (tree);
  extern bool cleanup_control_expr_graph (basic_block, block_stmt_iterator);
  extern void tree_optimize_tail_calls (bool, enum tree_dump_index);
! extern basic_block tree_block_forwards_to (basic_block bb);
  extern void bsi_insert_on_edge (edge, tree);
  extern void bsi_commit_edge_inserts (bool, int *);
  extern void bsi_insert_on_edge_immediate (edge, tree);
--- 419,425 ----
  extern basic_block label_to_block (tree);
  extern bool cleanup_control_expr_graph (basic_block, block_stmt_iterator);
  extern void tree_optimize_tail_calls (bool, enum tree_dump_index);
! extern edge tree_block_forwards_to (basic_block bb);
  extern void bsi_insert_on_edge (edge, tree);
  extern void bsi_commit_edge_inserts (bool, int *);
  extern void bsi_insert_on_edge_immediate (edge, tree);
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.238
diff -c -p -r1.1.4.238 tree-cfg.c
*** tree-cfg.c	17 Dec 2003 23:19:03 -0000	1.1.4.238
--- tree-cfg.c	18 Dec 2003 21:21:16 -0000
*************** remove_bb (basic_block bb)
*** 1460,1468 ****
  
  /* Examine BB to determine if it is a forwarding block (a block which only
     transfers control to a new destination).  If BB is a forwarding block,
!    then return the ultimate destination.  */
  
! basic_block
  tree_block_forwards_to (basic_block bb)
  {
    block_stmt_iterator bsi;
--- 1460,1468 ----
  
  /* Examine BB to determine if it is a forwarding block (a block which only
     transfers control to a new destination).  If BB is a forwarding block,
!    then return edge leading to the ultimate destination.  */
  
! edge
  tree_block_forwards_to (basic_block bb)
  {
    block_stmt_iterator bsi;
*************** tree_block_forwards_to (basic_block bb)
*** 1503,1516 ****
       case.  */
    if (bsi_end_p (bsi))
      {
!       basic_block dest;
  
        /* Recursive call to pick up chains of forwarding blocks.  */
        dest = tree_block_forwards_to (bb->succ->dest);
  
!       /* If none found, we forward to bb->succ->dest at minimum.  */
        if (!dest)
! 	dest = bb->succ->dest;
  
        ann->forwardable = 1;
        return dest;
--- 1503,1516 ----
       case.  */
    if (bsi_end_p (bsi))
      {
!       edge dest;
  
        /* Recursive call to pick up chains of forwarding blocks.  */
        dest = tree_block_forwards_to (bb->succ->dest);
  
!       /* If none found, we forward to bb->succ at minimum.  */
        if (!dest)
! 	dest = bb->succ;
  
        ann->forwardable = 1;
        return dest;





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