[patch][cprop.c] Allow splitting of critical edges to expose implicit sets

[patch][cprop.c] Allow splitting of critical edges to expose implicit sets

[Steven Bosscher]

[-- Attachment #1: Type: text/plain, Size: 348 bytes --]

Hi,

With this patch, it is OK for find_implicit_sets to split an edge if
that makes it possible to record an implicit set on that edge. This is
possible and cheap now because CPROP runs in cfglayout mode.

Bootstrapped and tested on x86_64-unknown-linux-gnu. Shaves off ~1kb
of cc1, which isn't very much but still kind of nice.
OK?

Ciao!
Steven

[-- Attachment #2: cprop_cleanup_4.diff.txt --]
[-- Type: text/plain, Size: 7716 bytes --]

	* cprop.c (implicit_set_cond_p): Assume nothing about COND, move
	checks on form of COND from find_implicit_sets to here.
	(find_implicit_sets): Cleanup control flow. Split critical edges
	if it exposes implicit sets.  Allocate/resize implicit_sets as
	necessary.
	(one_cprop_pass): Only delete unreachable blocks if local_cprop_pass
	changed something.  Run df_analyze after find_implicit_sets if any
	edges were split.  Do not allocate implicit_sets here.

*** cprop.c.v4	2011-03-31 23:40:16.000000000 +0200
--- cprop.c	2011-04-01 13:22:34.000000000 +0200
*************** fis_get_condition (rtx jump)
*** 1343,1356 ****
    return get_condition (jump, NULL, false, true);
  }
  
! /* Check the comparison COND to see if we can safely form an implicit set from
!    it.  COND is either an EQ or NE comparison.  */
  
  static bool
  implicit_set_cond_p (const_rtx cond)
  {
!   const enum machine_mode mode = GET_MODE (XEXP (cond, 0));
!   const_rtx cst = XEXP (cond, 1);
  
    /* We can't perform this optimization if either operand might be or might
       contain a signed zero.  */
--- 1343,1369 ----
    return get_condition (jump, NULL, false, true);
  }
  
! /* Check the comparison COND to see if we can safely form an implicit
!    set from it.  */
  
  static bool
  implicit_set_cond_p (const_rtx cond)
  {
!   enum machine_mode mode;
!   rtx cst;
! 
!   /* COND must be either an EQ or NE comparison.  */
!   if (GET_CODE (cond) != EQ && GET_CODE (cond) != NE)
!     return false;
! 
!   /* The first operand of COND must be a pseudo-reg.  */
!   if (! REG_P (XEXP (cond, 0))
!       || HARD_REGISTER_P (XEXP (cond, 0)))
!     return false;
! 
!   /* The second operand of COND must be a suitable constant.  */
!   mode = GET_MODE (XEXP (cond, 0));
!   cst = XEXP (cond, 1);
  
    /* We can't perform this optimization if either operand might be or might
       contain a signed zero.  */
*************** implicit_set_cond_p (const_rtx cond)
*** 1382,1436 ****
     function records the set patterns that are implicit at the start of each
     basic block.
  
!    FIXME: This would be more effective if critical edges are pre-split.  As
! 	  it is now, we can't record implicit sets for blocks that have
! 	  critical successor edges.  This results in missed optimizations
! 	  and in more (unnecessary) work in cfgcleanup.c:thread_jump().  */
  
! static void
  find_implicit_sets (void)
  {
    basic_block bb, dest;
-   unsigned int count;
    rtx cond, new_rtx;
  
-   count = 0;
    FOR_EACH_BB (bb)
!     /* Check for more than one successor.  */
!     if (EDGE_COUNT (bb->succs) > 1)
!       {
! 	cond = fis_get_condition (BB_END (bb));
  
! 	if (cond
! 	    && (GET_CODE (cond) == EQ || GET_CODE (cond) == NE)
! 	    && REG_P (XEXP (cond, 0))
! 	    && REGNO (XEXP (cond, 0)) >= FIRST_PSEUDO_REGISTER
! 	    && implicit_set_cond_p (cond))
! 	  {
! 	    dest = GET_CODE (cond) == EQ ? BRANCH_EDGE (bb)->dest
! 					 : FALLTHRU_EDGE (bb)->dest;
! 
! 	    if (dest
! 		/* Record nothing for a critical edge.  */
! 		&& single_pred_p (dest)
! 		&& dest != EXIT_BLOCK_PTR)
! 	      {
! 		new_rtx = gen_rtx_SET (VOIDmode, XEXP (cond, 0),
! 					     XEXP (cond, 1));
! 		implicit_sets[dest->index] = new_rtx;
! 		if (dump_file)
! 		  {
! 		    fprintf(dump_file, "Implicit set of reg %d in ",
! 			    REGNO (XEXP (cond, 0)));
! 		    fprintf(dump_file, "basic block %d\n", dest->index);
! 		  }
! 		count++;
! 	      }
! 	  }
        }
  
    if (dump_file)
      fprintf (dump_file, "Found %d implicit sets\n", count);
  }
  
  /* Bypass conditional jumps.  */
--- 1395,1472 ----
     function records the set patterns that are implicit at the start of each
     basic block.
  
!    If an implicit set is found but the set is implicit on a critical edge,
!    this critical edge is split.
! 
!    Return true if the CFG was modified, false otherwise.  */
  
! static bool
  find_implicit_sets (void)
  {
    basic_block bb, dest;
    rtx cond, new_rtx;
+   unsigned int count = 0;
+   bool edges_split = false;
+   size_t implicit_sets_size = last_basic_block + 10;
+ 
+   implicit_sets = XCNEWVEC (rtx, implicit_sets_size);
  
    FOR_EACH_BB (bb)
!     {
!       /* Check for more than one successor.  */
!       if (! EDGE_COUNT (bb->succs) > 1)
! 	continue;
! 
!       cond = fis_get_condition (BB_END (bb));
! 
!       /* If no condition is found or if it isn't of a suitable form,
! 	 ignore it.  */
!       if (! cond || ! implicit_set_cond_p (cond))
! 	continue;
! 
!       dest = GET_CODE (cond) == EQ
! 	? BRANCH_EDGE (bb)->dest : FALLTHRU_EDGE (bb)->dest;
! 
!       /* If DEST doesn't go anywhere, ignore it.  */
!       if (! dest || dest == EXIT_BLOCK_PTR)
! 	continue;
! 
!       /* We have found a suitable implicit set.  Try to record it now as
! 	 a SET in DEST.  If DEST has more than one predecessor, the edge
! 	 between BB and DEST is a critical edge and we must split it,
! 	 because we can only record one implicit set per DEST basic block.  */
!       if (! single_pred_p (dest))
!         {
! 	  dest = split_edge (find_edge (bb, dest));
! 	  edges_split = true;
! 	}
  
!       if (implicit_sets_size <= (size_t) dest->index)
!       {
!         size_t old_implicit_sets_size = implicit_sets_size;
! 	implicit_sets_size *= 2;
! 	implicit_sets = XRESIZEVEC (rtx, implicit_sets, implicit_sets_size);
! 	memset (implicit_sets + old_implicit_sets_size, 0,
! 		(implicit_sets_size - old_implicit_sets_size) * sizeof (rtx));
        }
  
+       new_rtx = gen_rtx_SET (VOIDmode, XEXP (cond, 0),
+ 			     XEXP (cond, 1));
+       implicit_sets[dest->index] = new_rtx;
+       if (dump_file)
+ 	{
+ 	  fprintf(dump_file, "Implicit set of reg %d in ",
+ 		  REGNO (XEXP (cond, 0)));
+ 	  fprintf(dump_file, "basic block %d\n", dest->index);
+ 	}
+       count++;
+     }
+ 
    if (dump_file)
      fprintf (dump_file, "Found %d implicit sets\n", count);
+ 
+   /* Confess our sins.  */
+   return edges_split;
  }
  
  /* Bypass conditional jumps.  */
*************** one_cprop_pass (void)
*** 1797,1810 ****
  	    the solver implemented in this file.  */
    changed |= local_cprop_pass ();
    if (changed)
!     {
!       delete_unreachable_blocks ();
!       df_analyze ();
!     }
  
!   /* Determine implicit sets.  */
!   implicit_sets = XCNEWVEC (rtx, last_basic_block);
!   find_implicit_sets ();
  
    alloc_hash_table (&set_hash_table);
    compute_hash_table (&set_hash_table);
--- 1833,1860 ----
  	    the solver implemented in this file.  */
    changed |= local_cprop_pass ();
    if (changed)
!     delete_unreachable_blocks ();
  
!   /* Determine implicit sets.  This may change the CFG (split critical
!      edges if that exposes an implicit set).
!      Note that find_implicit_sets() does not rely on up-to-date DF caches
!      so that we do not have to re-run df_analyze() even if local CPROP
!      changed something.
!      ??? This could run earlier so that any uncovered implicit sets
! 	 sets could be exploited in local_cprop_pass() also.  Later.  */
!   changed |= find_implicit_sets ();
! 
!   /* If local_cprop_pass() or find_implicit_sets() changed something,
!      run df_analyze() to bring all insn caches up-to-date, and to take
!      new basic blocks from edge splitting on the DF radar.
! 
!      ??? It may be helpful to add DF_LR_RUN_DCE if local_cprop_pass()
! 	 changed something.  Or maybe local_cprop_pass() should just
! 	 clean up after itself and remove insns if it can prove that
! 	 a register is dead after a local CPROP opportunity.  For now
! 	 dead code is just left in the insns stream.  */
!   if (changed)
!     df_analyze ();
  
    alloc_hash_table (&set_hash_table);
    compute_hash_table (&set_hash_table);

Re: [patch][cprop.c] Allow splitting of critical edges to expose implicit sets

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 04/01/11 07:55, Steven Bosscher wrote:
> Hi,
> 
> With this patch, it is OK for find_implicit_sets to split an edge if
> that makes it possible to record an implicit set on that edge. This is
> possible and cheap now because CPROP runs in cfglayout mode.
> 
> Bootstrapped and tested on x86_64-unknown-linux-gnu. Shaves off ~1kb
> of cc1, which isn't very much but still kind of nice.
OK.
jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJNmgqKAAoJEBRtltQi2kC760oH/A+4A5rbGMQfgzupMuO0rs/a
GtK9o9nSMTbZiQf1qpcKNajAulg55F4C7wRHDkaLIQ03qkmjmoxiSfEh7KAU7bz+
sfjgp42j/WiMOWFH6+fgOoLcMU8LIW+moRq+17oApPiyQRv7w6AioOcBdsroU9AC
ElCHtjopSyz+jgAcGxNVSJLEesrLgJkGVJL5bSQ8ehpLtusaE1E6pmcgd3OVPu9n
ioRNsqhK8mp4eY7acjCLkDqeqr3Z2Ifa7EWyjBK6NmjMWHXCCXA30tC7O4Dxj1r6
1dv4h+Bl5eVyFV3QdDlqqpYnSsILtpS2Q6wgcjOLSVJch04r1Hqs86geX0cMJic=
=LAKB
-----END PGP SIGNATURE-----