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] Initial jump threading through conditional jumps


Leaf nodes in the dominator tree often pass control to blocks which
start with IF statements.  ie


if (cond)
  {
     then1
  }
else
  {
     else1
  }

if (cond2)
  {
    then2
  }
else
  {
    else2
  }

"then1" will be a leaf in the dominator tree (assuming then1 and else1 both
fall through to the second IF statement) and effectively represents the end
of an optimizable path for the dominator optimizer.

However consider something like this:


if (cond1)
  {
     if (x == 20)
       abort ();
  }
else
  {
     else1;
  }

if (x != 20)
  {
    then2;
  }
else
  {
    else2;
  }

At the end of the first THEN clause we know that x != 20.  However, we have
to remove that expression from the hash table when we're done with the first
THEN clause since that equivalence is associated with the first THEN clause
and the THEN clause is a leaf in the dominator tree.

This is somewhat unfortunate in that we'd like know that if we reach the
second IF statement by way of the first THEN statement that x != 20 is
always true.

The easiest way to do that is via jump threading.  Effectively before we
finish processing the first THEN clause we look at the THEN clauses's 
successor block and see if that block starts with an IF statement
for which we have an equivalence in our table.

What that effectively does is turn the above code into something like this:

if (cond1)
  {
     if (x == 20)
       abort ();
     goto then2;
  }
else
  {
     else1;
  }

if (x != 20)
  {
    then2;
  }
else
  {
    else2;
  }


This is basically the same thing we're doing with jump threading elsewhere
in the RTL optimizers, just done within the SSA dominator optimizer framework.

I've currently placed some restrictions on when we perform this transformation
so that we don't have to do PHI node updates.  Even with those restrictions
this optimization triggers quite often.

The plan is for the jump following code that Steven has been working on and
the conditional jump threading code to share PHI node updating facilities.
Once that code is complete the conditional jump threading can be made
even more aggressive.

[ It's also worth noting that the conditional jump threading optimization
  tends of expose/create more opportunities for Steven's unconditional
  jump following code. ]

The other restriction/limitation is that the successor block of the
leaf node in the dominator tree must begin with a COND_EXPR.  Dead
code at the start of the block will inhibit this optimization.   It's
unclear at this time if it's worth running the dominator optimizer again
after DCE to expose more jump threading opportunities (though it is
certainly required to fix the testcase in our testsuite).



The only interesting implementation details are latent issues that this
patch exposed.

For example, if we have COND_EXPR which is unreachable, but which has
reachable code in its THEN/ELSE arms, we can end up with an expression
which never gets renamed back to normal form (inside COND_EXPR_COND).
This causes an abort later when expanding the tree nodes into RTL.  I
fixed this in my recent patch to tree-cfg.c.

Another example is when we remove unreachable blocks, they may be incorrectly
considered subblocks of a control structure -- which can through a wonderful
series of events result in another case where we have unreachable statements
in the IL with references to variables in SSA form.  The easiest way to 
fix this was to use find_contained_blocks which does the same thing as
find_subblocks, except it does it correctly.  Again, I fixed this in my
recent patch to tree-cfg.c.

Finally, tree dumping when we have an unreachable control structure
with reachable subblocks is badly broken.  I've tweaked the code slightly
to make the output less broken, but it still emits markers for blocks which
have been deleted.


Anyway, bootstrapped and regression tested as usual.  Whee.




	* tree-pretty-print.c (last_bb): Actually record the basic block,
	not just its index.
	(maybe_init_pretty_print): Corresponding changes.
	(dump_generic_node, dump_vops): Test the actual block pointers, not
	their indices.

	* tree-ssa-dom.c (optimize_block): Use equivalences from the
	dominator tree walk to thread through conditional jumps at leafs in
	the dominator tree.

Index: tree-pretty-print.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-pretty-print.c,v
retrieving revision 1.1.2.36
diff -c -3 -p -r1.1.2.36 tree-pretty-print.c
*** tree-pretty-print.c	12 Aug 2003 19:44:44 -0000	1.1.2.36
--- tree-pretty-print.c	17 Aug 2003 18:53:58 -0000
*************** static void dump_vops (output_buffer *, 
*** 59,65 ****
  
  static output_buffer buffer;
  static int initialized = 0;
! static int last_bb;
  static bool dumping_stmts;
  
  /* Try to print something for an unknown tree code.  */
--- 59,65 ----
  
  static output_buffer buffer;
  static int initialized = 0;
! static basic_block last_bb;
  static bool dumping_stmts;
  
  /* Try to print something for an unknown tree code.  */
*************** dump_generic_node (output_buffer *buffer
*** 146,159 ****
      {
        basic_block curr_bb = bb_for_stmt (node);
  
!       if ((flags & TDF_BLOCKS) && curr_bb && curr_bb->index != last_bb)
  	dump_block_info (buffer, curr_bb, spc);
  
        if ((flags & TDF_VOPS) && stmt_ann (node))
  	dump_vops (buffer, node, spc);
  
!       if (curr_bb && curr_bb->index != last_bb)
! 	last_bb = curr_bb->index;
      }
  
    switch (TREE_CODE (node))
--- 146,159 ----
      {
        basic_block curr_bb = bb_for_stmt (node);
  
!       if ((flags & TDF_BLOCKS) && curr_bb && curr_bb != last_bb)
  	dump_block_info (buffer, curr_bb, spc);
  
        if ((flags & TDF_VOPS) && stmt_ann (node))
  	dump_vops (buffer, node, spc);
  
!       if (curr_bb && curr_bb != last_bb)
! 	last_bb = curr_bb;
      }
  
    switch (TREE_CODE (node))
*************** pretty_print_string (output_buffer *buff
*** 1911,1917 ****
  static void
  maybe_init_pretty_print (void)
  {
!   last_bb = -1;
  
    if (!initialized)
      {
--- 1911,1917 ----
  static void
  maybe_init_pretty_print (void)
  {
!   last_bb = NULL;
  
    if (!initialized)
      {
*************** dump_vops (output_buffer *buffer, tree s
*** 1984,1990 ****
    varray_type vuses = vuse_ops (stmt);
  
    bb = bb_for_stmt (stmt);
!   if (bb && bb->index != last_bb && bb->tree_annotations)
      {
        tree phi;
  
--- 1984,1990 ----
    varray_type vuses = vuse_ops (stmt);
  
    bb = bb_for_stmt (stmt);
!   if (bb && bb != last_bb && bb->tree_annotations)
      {
        tree phi;
  
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.25
diff -c -3 -p -r1.1.2.25 tree-ssa-dom.c
*** tree-ssa-dom.c	15 Aug 2003 20:47:55 -0000	1.1.2.25
--- tree-ssa-dom.c	17 Aug 2003 18:54:03 -0000
*************** optimize_block (basic_block bb, tree par
*** 445,450 ****
--- 445,534 ----
  	}
      }
  
+   /* If we have a single successor, then we may be able to thread
+      the edge out of our block to a destination of our successor.
+ 
+      To simplify the initial implementation we require that
+      our successor have no PHI nodes.  */
+   if (bb->succ && bb->succ->succ_next == NULL && ! phi_nodes (bb->succ->
dest))
+     {
+       block_stmt_iterator i = bsi_start (bb->succ->dest);
+       tree stmt;
+ 
+       /* Get the successor's first real statement.  */
+       while (! bsi_end_p (i)
+ 	     && (IS_EMPTY_STMT (bsi_stmt (i))
+ 		 || TREE_CODE (bsi_stmt (i)) == LABEL_EXPR))
+ 	bsi_next (&i);
+       stmt = bsi_end_p (i) ? NULL : bsi_stmt (i);
+ 
+       /* If the successor's first real statement is a COND_EXPR, then
+ 	 see if we know which arm will be taken.  */
+       if (stmt && TREE_CODE (stmt) == COND_EXPR)
+ 	{
+ 	  tree cached_lhs = lookup_avail_expr (stmt,
+ 					       &block_avail_exprs,
+ 					       const_and_copies);
+ 	  if (cached_lhs)
+ 	    {
+ 	      edge taken_edge = find_taken_edge (bb->succ->dest, cached_lhs);
+ 	      basic_block dest = (taken_edge ? taken_edge->dest : NULL);
+ 
+ 	      /* 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))
+ 		{
+ 		  block_stmt_iterator dest_iterator = bsi_start (dest);
+ 		  tree dest_stmt = bsi_stmt (dest_iterator);
+ 		  tree label, goto_stmt;
+ 
+ 		  /* We need a label at our final destination.  If it does
+ 		     not already exist, create it.  */
+ 		  if (TREE_CODE (dest_stmt) != LABEL_EXPR)
+ 		    {
+ 		      label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
+ 		      DECL_CONTEXT (label) = current_function_decl;
+ 		      dest_stmt = build1 (LABEL_EXPR, void_type_node, label);
+ 		      bsi_insert_before (&dest_iterator,
+ 					 dest_stmt,
+ 					 BSI_NEW_STMT);
+ 		    }
+ 		  else
+ 		    label = LABEL_EXPR_LABEL (dest_stmt);
+ 
+ 		  
+ 		  /* If our block does not end with a GOTO, then create
+ 		     one.  Otherwise redirect the existing GOTO_EXPR to
+ 		     LABEL.  */
+ 		  stmt = last_stmt (bb);
+ 		  if (TREE_CODE (stmt) != GOTO_EXPR)
+ 		    {
+ 		      basic_block tmp_bb;
+ 
+ 		      goto_stmt = build1 (GOTO_EXPR, void_type_node, label);
+ 		      bsi_insert_on_edge_immediate (bb->succ, goto_stmt,
+ 						    NULL, &tmp_bb);
+ 
+ #ifdef ENABLE_CHECKING
+ 		      if (tmp_bb)
+ 			abort ();
+ #endif
+ 		    }
+ 		  else
+ 		    GOTO_DESTINATION (stmt) = label;
+ 
+ 		  /* Update/insert PHI nodes as necessary.  */
+ 
+ 		  /* Now update the edges in the CFG.  */
+ 		  ssa_remove_edge (bb->succ);
+ 		  make_edge (bb, dest, 0);
+ 		}
+ 	    }
+ 	}
+     }
+ 
    /* Remove all the expressions made available in this block.  */
    while (VARRAY_ACTIVE_SIZE (block_avail_exprs) > 0)
      {



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