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]

[patch] tree-cfg.c: Split thread_jumps into two functions.


Hi,

Attached is a patch to split thread_jumps into two functions
thread_jumps and thread_jumps_from_bb, where thread_jumps calls
thread_jumps_from_bb as a subroutine.

The reasons why I am submitting this patch are as follows.

First, the nest level of thread_jumps is becoming fairly high.

Also, I am about to submit a worklist implementation of thread_jumps
that significantly improves the current slow fixed point operation.
Even though my new implementation is a lot faster than the current
implementation, its control structure is a little more complicated
than the current one:

  do
    {
      FOR_EACH_BB (bb)
        {
          :
        }
    }
  while (rerun);

If I did't split thread_jumps and went for my worklist implementation,
the nest level would become even higher, and the code would be just
unreadable.

So basically, I don't want my next patch to appear too big.  If I can
get this change out of the way, your job of reviewing my next patch
will be a lot easier. ;-)

To give you heads up, my worklist implementation cuts down compilation
time nearly by half on the testcase in PR 17966.  It also improves
compilation time on a real-world program like fold-const.c.

There is no functional change.

Tested on i686-pc-linux-gnu.  OK to apply?

Kazu Hirata

2004-10-20  Kazu Hirata  <kazu@cs.umass.edu>

	* tree-cfg.c (thread_jumps): Move a part of it to ...
	(thread_jumps_from_bb): ... here.

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.84
diff -c -r2.84 tree-cfg.c
*** tree-cfg.c	19 Oct 2004 20:52:22 -0000	2.84
--- tree-cfg.c	20 Oct 2004 02:39:08 -0000
***************
*** 3759,3957 ****
    return true;
  }
  
  
- /* Thread jumps over empty statements.
- 
-    This code should _not_ thread over obviously equivalent conditions
-    as that requires nontrivial updates to the SSA graph.
- 
-    As a precondition, we require that all basic blocks be reachable.
-    That is, there should be no opportunities left for
-    delete_unreachable_blocks.  */
-    
  static bool
! thread_jumps (void)
  {
!   edge e, last, old;
!   basic_block bb, dest, tmp, old_dest, curr, dom;
!     tree phi;
!   int arg;
    bool retval = false;
-   bool rerun;
  
!   FOR_EACH_BB (bb)
!     bb_ann (bb)->forwardable = tree_forwarder_block_p (bb);
! 
!   do
      {
!       rerun = false;
!       FOR_EACH_BB (bb)
  	{
! 	  edge_iterator ei;
! 	  bool this_jump_threaded = false;
  
! 	  /* Don't waste time on forwarders.  */
! 	  if (bb_ann (bb)->forwardable)
! 	    continue;
  
! 	  /* Examine each of our block's successors to see if it is
! 	     forwardable.  */
! 	  for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
! 	    {
! 	      int freq;
! 	      gcov_type count;
  
! 	      /* If the edge is abnormal or its destination is not
! 		 forwardable, then there's nothing to do.  */
! 	      if ((e->flags & EDGE_ABNORMAL)
! 		  || !bb_ann (e->dest)->forwardable)
! 		{
! 		  ei_next (&ei);
! 		  continue;
! 		}
! 
! 	      count = e->count;
! 	      freq = EDGE_FREQUENCY (e);
  
! 	      /* Now walk through as many forwarder blocks as possible to
! 		 find the ultimate destination we want to thread our jump
! 		 to.  */
! 	      last = EDGE_SUCC (e->dest, 0);
! 	      bb_ann (e->dest)->forwardable = 0;
! 	      for (dest = EDGE_SUCC (e->dest, 0)->dest;
! 		   bb_ann (dest)->forwardable;
! 		   last = EDGE_SUCC (dest, 0),
! 		     dest = EDGE_SUCC (dest, 0)->dest)
! 		bb_ann (dest)->forwardable = 0;
! 
! 	      /* Reset the forwardable marks to 1.  */
! 	      for (tmp = e->dest;
! 		   tmp != dest;
! 		   tmp = EDGE_SUCC (tmp, 0)->dest)
! 		bb_ann (tmp)->forwardable = 1;
  
  	      if (dest == e->dest)
  		{
  		  ei_next (&ei);
  		  continue;
  		}
! 	      
  	      old = find_edge (bb, dest);
! 	      if (old)
! 		{
! 		  /* If there already is an edge, check whether the values
! 		     in phi nodes differ.  */
! 		  if (!phi_alternatives_equal (dest, last, old))
! 		    {
! 		      /* The previous block is forwarder.  Redirect our jump
! 			 to that target instead since we know it has no PHI
! 			 nodes that will need updating.  */
! 		      dest = last->src;
! 	  
! 		      /* That might mean that no forwarding at all is
! 			 possible.  */
! 		      if (dest == e->dest)
! 			{
! 			  ei_next (&ei);
! 			  continue;
! 			}
  
! 		      old = find_edge (bb, dest);
! 		    }
! 		}
  
! 	      /* Perform the redirection.  */
! 	      retval = this_jump_threaded = true;
! 	      old_dest = e->dest;
! 	      e = redirect_edge_and_branch (e, dest);
! 
! 	      /* Update the profile.  */
! 	      if (profile_status != PROFILE_ABSENT)
! 		for (curr = old_dest;
! 		     curr != dest;
! 		     curr = EDGE_SUCC (curr, 0)->dest)
! 		  {
! 		    curr->frequency -= freq;
! 		    if (curr->frequency < 0)
! 		      curr->frequency = 0;
! 		    curr->count -= count;
! 		    if (curr->count < 0)
! 		      curr->count = 0;
! 		    EDGE_SUCC (curr, 0)->count -= count;
! 		    if (EDGE_SUCC (curr, 0)->count < 0)
! 		      EDGE_SUCC (curr, 0)->count = 0;
! 		  }
  
! 	      if (!old)
  		{
! 		  /* Update PHI nodes.  We know that the new argument
! 		     should have the same value as the argument
! 		     associated with LAST.  Otherwise we would have
! 		     changed our target block above.  */
! 		  for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
! 		    {
! 		      arg = phi_arg_from_edge (phi, last);
! 		      gcc_assert (arg >= 0);
! 		      add_phi_arg (&phi, PHI_ARG_DEF (phi, arg), e);
! 		    }
  		}
  
! 	      /* Remove the unreachable blocks (observe that if all blocks
! 		 were reachable before, only those in the path we threaded
! 		 over and did not have any predecessor outside of the path
! 		 become unreachable).  */
! 	      for (; old_dest != dest; old_dest = tmp)
! 		{
! 		  tmp = EDGE_SUCC (old_dest, 0)->dest;
  
! 		  if (EDGE_COUNT (old_dest->preds) > 0)
! 		    break;
  
- 		  delete_basic_block (old_dest);
- 		}
  
! 	      /* Update the dominators.  */
! 	      if (dom_info_available_p (CDI_DOMINATORS))
! 		{
! 		  /* If the dominator of the destination was in the
! 		     path, set its dominator to the start of the
! 		     redirected edge.  */
! 		  if (get_immediate_dominator (CDI_DOMINATORS, old_dest) == NULL)
! 		    set_immediate_dominator (CDI_DOMINATORS, old_dest, bb);
! 
! 		  /* Now proceed like if we forwarded just over one
! 		     edge at a time.  Algorithm for forwarding edge
! 		     S --> A over edge A --> B then is
! 
! 		     if (idom (B) == A
! 		         && !dominated_by (S, B))
! 		       idom (B) = idom (A);
! 		     recount_idom (A);  */
  
! 		  for (; old_dest != dest; old_dest = tmp)
! 		    {
! 		      tmp = EDGE_SUCC (old_dest, 0)->dest;
  
! 		      if (get_immediate_dominator (CDI_DOMINATORS, tmp) == old_dest
! 			  && !dominated_by_p (CDI_DOMINATORS, bb, tmp))
! 			{
! 			  dom = get_immediate_dominator (CDI_DOMINATORS, old_dest);
! 			  set_immediate_dominator (CDI_DOMINATORS, tmp, dom);
! 			}
  
! 		      dom = recount_dominator (CDI_DOMINATORS, old_dest);
! 		      set_immediate_dominator (CDI_DOMINATORS, old_dest, dom);
! 		    }
! 		}
! 	    }
  
! 	  /* If we succeeded in threading a jump at BB, update the
! 	     forwardable mark as BB may have become a new forwarder
! 	     block.  This could happen if we have a useless "if"
! 	     statement whose two arms eventually merge without any
! 	     intervening statements.  */
! 	  if (this_jump_threaded && tree_forwarder_block_p (bb))
! 	    bb_ann (bb)->forwardable = rerun = true;
  	}
      }
    while (rerun);
--- 3759,3973 ----
    return true;
  }
  
+ /* Thread jumps from BB.  */
  
  static bool
! thread_jumps_from_bb (basic_block bb)
  {
!   edge_iterator ei;
!   edge e;
    bool retval = false;
  
!   /* Examine each of our block's successors to see if it is
!      forwardable.  */
!   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
      {
!       int freq;
!       gcov_type count;
!       edge last, old;
!       basic_block dest, tmp, curr, old_dest;
!       tree phi;
!       int arg;
! 
!       /* If the edge is abnormal or its destination is not
! 	 forwardable, then there's nothing to do.  */
!       if ((e->flags & EDGE_ABNORMAL)
! 	  || !bb_ann (e->dest)->forwardable)
  	{
! 	  ei_next (&ei);
! 	  continue;
! 	}
  
!       count = e->count;
!       freq = EDGE_FREQUENCY (e);
  
!       /* Now walk through as many forwarder blocks as possible to find
! 	 the ultimate destination we want to thread our jump to.  */
!       last = EDGE_SUCC (e->dest, 0);
!       bb_ann (e->dest)->forwardable = 0;
!       for (dest = EDGE_SUCC (e->dest, 0)->dest;
! 	   bb_ann (dest)->forwardable;
! 	   last = EDGE_SUCC (dest, 0),
! 	     dest = EDGE_SUCC (dest, 0)->dest)
! 	bb_ann (dest)->forwardable = 0;
! 
!       /* Reset the forwardable marks to 1.  */
!       for (tmp = e->dest;
! 	   tmp != dest;
! 	   tmp = EDGE_SUCC (tmp, 0)->dest)
! 	bb_ann (tmp)->forwardable = 1;
  
!       if (dest == e->dest)
! 	{
! 	  ei_next (&ei);
! 	  continue;
! 	}
  
!       old = find_edge (bb, dest);
!       if (old)
! 	{
! 	  /* If there already is an edge, check whether the values in
! 	     phi nodes differ.  */
! 	  if (!phi_alternatives_equal (dest, last, old))
! 	    {
! 	      /* The previous block is forwarder.  Redirect our jump
! 		 to that target instead since we know it has no PHI
! 		 nodes that will need updating.  */
! 	      dest = last->src;
  
+ 	      /* That might mean that no forwarding at all is
+ 		 possible.  */
  	      if (dest == e->dest)
  		{
  		  ei_next (&ei);
  		  continue;
  		}
! 
  	      old = find_edge (bb, dest);
! 	    }
! 	}
  
!       /* Perform the redirection.  */
!       retval = true;
!       old_dest = e->dest;
!       e = redirect_edge_and_branch (e, dest);
! 
!       /* Update the profile.  */
!       if (profile_status != PROFILE_ABSENT)
! 	for (curr = old_dest;
! 	     curr != dest;
! 	     curr = EDGE_SUCC (curr, 0)->dest)
! 	  {
! 	    curr->frequency -= freq;
! 	    if (curr->frequency < 0)
! 	      curr->frequency = 0;
! 	    curr->count -= count;
! 	    if (curr->count < 0)
! 	      curr->count = 0;
! 	    EDGE_SUCC (curr, 0)->count -= count;
! 	    if (EDGE_SUCC (curr, 0)->count < 0)
! 	      EDGE_SUCC (curr, 0)->count = 0;
! 	  }
! 
!       if (!old)
! 	{
! 	  /* Update PHI nodes.  We know that the new argument should
! 	     have the same value as the argument associated with LAST.
! 	     Otherwise we would have changed our target block
! 	     above.  */
! 	  for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
! 	    {
! 	      arg = phi_arg_from_edge (phi, last);
! 	      gcc_assert (arg >= 0);
! 	      add_phi_arg (&phi, PHI_ARG_DEF (phi, arg), e);
! 	    }
! 	}
! 
!       /* Remove the unreachable blocks (observe that if all blocks
! 	 were reachable before, only those in the path we threaded
! 	 over and did not have any predecessor outside of the path
! 	 become unreachable).  */
!       for (; old_dest != dest; old_dest = tmp)
! 	{
! 	  tmp = EDGE_SUCC (old_dest, 0)->dest;
  
! 	  if (EDGE_COUNT (old_dest->preds) > 0)
! 	    break;
! 
! 	  delete_basic_block (old_dest);
! 	}
! 
!       /* Update the dominators.  */
!       if (dom_info_available_p (CDI_DOMINATORS))
! 	{
! 	  /* If the dominator of the destination was in the
! 	     path, set its dominator to the start of the
! 	     redirected edge.  */
! 	  if (get_immediate_dominator (CDI_DOMINATORS, old_dest) == NULL)
! 	    set_immediate_dominator (CDI_DOMINATORS, old_dest, bb);
! 
! 	  /* Now proceed like if we forwarded just over one edge at a
! 	     time.  Algorithm for forwarding edge S --> A over
! 	     edge A --> B then is
! 
! 	     if (idom (B) == A
! 	         && !dominated_by (S, B))
! 	       idom (B) = idom (A);
! 	     recount_idom (A);  */
! 
! 	  for (; old_dest != dest; old_dest = tmp)
! 	    {
! 	      basic_block dom;
  
! 	      tmp = EDGE_SUCC (old_dest, 0)->dest;
! 
! 	      if (get_immediate_dominator (CDI_DOMINATORS, tmp) == old_dest
! 		  && !dominated_by_p (CDI_DOMINATORS, bb, tmp))
  		{
! 		  dom = get_immediate_dominator (CDI_DOMINATORS, old_dest);
! 		  set_immediate_dominator (CDI_DOMINATORS, tmp, dom);
  		}
  
! 	      dom = recount_dominator (CDI_DOMINATORS, old_dest);
! 	      set_immediate_dominator (CDI_DOMINATORS, old_dest, dom);
! 	    }
! 	}
!     }
  
!   return retval;
! }
  
  
! /* Thread jumps over empty statements.
  
!    This code should _not_ thread over obviously equivalent conditions
!    as that requires nontrivial updates to the SSA graph.
  
!    As a precondition, we require that all basic blocks be reachable.
!    That is, there should be no opportunities left for
!    delete_unreachable_blocks.  */
  
! static bool
! thread_jumps (void)
! {
!   basic_block bb;
!   bool retval = false;
!   bool rerun;
! 
!   FOR_EACH_BB (bb)
!     bb_ann (bb)->forwardable = tree_forwarder_block_p (bb);
  
!   do
!     {
!       rerun = false;
!       FOR_EACH_BB (bb)
! 	{
! 	  /* Don't waste time on forwarders.  */
! 	  if (bb_ann (bb)->forwardable)
! 	    continue;
! 
! 	  if (thread_jumps_from_bb (bb))
! 	    {
! 	      retval = true;
! 
! 	      /* If we succeeded in threading a jump at BB, update the
! 		 forwardable mark as BB may have become a new
! 		 forwarder block.  This could happen if we have a
! 		 useless "if" statement whose two arms eventually
! 		 merge without any intervening statements.  */
! 	      if (tree_forwarder_block_p (bb))
! 		bb_ann (bb)->forwardable = rerun = true;
! 	    }
  	}
      }
    while (rerun);


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