Re: RFA: Avoiding unprofitable speculation

[Jeff Law <law@redhat.com>]

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

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

On 08/18/11 15:59, Richard Henderson wrote:
> On 08/17/2011 12:21 AM, Richard Guenther wrote:
>> The patch itself looks sensible, though I am surprised ifcvt
>> doesn't run in cfglayout mode (so you have to use reg notes to
>> find probabilities ...)
> 
> It does run in cfglayout mode.
> 
> Jeff, I believe you're supposed to get the probabilities from some
> combination of
> 
> bb->frequency edge->probability EDGE_FREQUENCY(edge)
OK.  Here's the revised patch.  There's other places in ifcvt.c that
utilize the notes that I didn't modify.

Bootstrapped & regression tested x86_64-unknown-linux-gnu.  Also
verified performance data hasn't changed materially.

OK for trunk?

Thanks,
jeff


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOgPzuAAoJEBRtltQi2kC7uQkH+wTyLl3MwKkqC11ozyOAVSQ9
CrlwLAuN7JV7kZcguKZ9GpXYHePZHZHCISXaVv3LQQBXnE7PehJOWsd1D5BQRv2/
eqVHIAOYg0LamY2cRiWW8pKMiMjs7vb9q0fiehQGg0zxAJMc9crBjwLPGFjZAksw
UNzzon/NKfSMYsz9X/olDfk8DPa1DmAjBnNOcHzKLGdx7KDa6Npo20k3D/PwDbIe
y1Ff9pZBXJP6tNU+0cn9lyyt+w6ghFQRkpKJoJ6iSOxKQ6v23+03o4sT5GHv3Gvy
07R6NJU9vqt7a9GvxcyJ9BsOlCCJ/pA/4lProHrdcAZrOYWZAA4uoJeDBPOEq+g=
=a5LI
-----END PGP SIGNATURE-----

[-- Attachment #2: Q --]
[-- Type: text/plain, Size: 6923 bytes --]

	* ifcvt.c (cheap_bb_rtx_cost_p): Add SCALE argument.  Scale
	non-jumping insns by REG_BR_PROB_BASE and the maximum cost
	by SCALE.
	(find_if_case_1): Use the probability of the THEN clause when
	determining if speculation if profitable.
	(find_if_case_2): Similarly for the ELSE clause.
	
Index: ifcvt.c
===================================================================
*** ifcvt.c	(revision 179218)
--- ifcvt.c	(working copy)
*************** static int cond_exec_changed_p;
*** 85,91 ****
  
  /* Forward references.  */
  static int count_bb_insns (const_basic_block);
! static bool cheap_bb_rtx_cost_p (const_basic_block, int);
  static rtx first_active_insn (basic_block);
  static rtx last_active_insn (basic_block, int);
  static rtx find_active_insn_before (basic_block, rtx);
--- 85,91 ----
  
  /* Forward references.  */
  static int count_bb_insns (const_basic_block);
! static bool cheap_bb_rtx_cost_p (const_basic_block, int, int);
  static rtx first_active_insn (basic_block);
  static rtx last_active_insn (basic_block, int);
  static rtx find_active_insn_before (basic_block, rtx);
*************** count_bb_insns (const_basic_block bb)
*** 131,150 ****
  
  /* Determine whether the total insn_rtx_cost on non-jump insns in
     basic block BB is less than MAX_COST.  This function returns
!    false if the cost of any instruction could not be estimated.  */
  
  static bool
! cheap_bb_rtx_cost_p (const_basic_block bb, int max_cost)
  {
    int count = 0;
    rtx insn = BB_HEAD (bb);
    bool speed = optimize_bb_for_speed_p (bb);
  
    while (1)
      {
        if (NONJUMP_INSN_P (insn))
  	{
! 	  int cost = insn_rtx_cost (PATTERN (insn), speed);
  	  if (cost == 0)
  	    return false;
  
--- 131,161 ----
  
  /* Determine whether the total insn_rtx_cost on non-jump insns in
     basic block BB is less than MAX_COST.  This function returns
!    false if the cost of any instruction could not be estimated. 
! 
!    The cost of the non-jump insns in BB is scaled by REG_BR_PROB_BASE
!    as those insns are being speculated.  MAX_COST is scaled with SCALE
!    plus a small fudge factor.  */
  
  static bool
! cheap_bb_rtx_cost_p (const_basic_block bb, int scale, int max_cost)
  {
    int count = 0;
    rtx insn = BB_HEAD (bb);
    bool speed = optimize_bb_for_speed_p (bb);
  
+   /* Our branch probability/scaling factors are just estimates and don't
+      account for cases where we can get speculation for free and other
+      secondary benefits.  So we fudge the scale factor to make speculating
+      appear a little more profitable.  */
+   scale += REG_BR_PROB_BASE / 8;
+   max_cost *= scale;
+ 
    while (1)
      {
        if (NONJUMP_INSN_P (insn))
  	{
! 	  int cost = insn_rtx_cost (PATTERN (insn), speed) * REG_BR_PROB_BASE;
  	  if (cost == 0)
  	    return false;
  
*************** find_if_case_1 (basic_block test_bb, edg
*** 3796,3803 ****
    basic_block then_bb = then_edge->dest;
    basic_block else_bb = else_edge->dest;
    basic_block new_bb;
    rtx else_target = NULL_RTX;
-   int then_bb_index;
  
    /* If we are partitioning hot/cold basic blocks, we don't want to
       mess up unconditional or indirect jumps that cross between hot
--- 3807,3814 ----
    basic_block then_bb = then_edge->dest;
    basic_block else_bb = else_edge->dest;
    basic_block new_bb;
+   int then_bb_index, then_prob;
    rtx else_target = NULL_RTX;
  
    /* If we are partitioning hot/cold basic blocks, we don't want to
       mess up unconditional or indirect jumps that cross between hot
*************** find_if_case_1 (basic_block test_bb, edg
*** 3840,3847 ****
  	     "\nIF-CASE-1 found, start %d, then %d\n",
  	     test_bb->index, then_bb->index);
  
!   /* THEN is small.  */
!   if (! cheap_bb_rtx_cost_p (then_bb,
  	COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (then_edge->src),
  				    predictable_edge_p (then_edge)))))
      return FALSE;
--- 3851,3864 ----
  	     "\nIF-CASE-1 found, start %d, then %d\n",
  	     test_bb->index, then_bb->index);
  
!   if (then_edge->probability)
!     then_prob = REG_BR_PROB_BASE - then_edge->probability;
!   else
!     then_prob = REG_BR_PROB_BASE / 2;
! 
!   /* We're speculating from the THEN path, we want to make sure the cost
!      of speculation is within reason.  */
!   if (! cheap_bb_rtx_cost_p (then_bb, then_prob,
  	COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (then_edge->src),
  				    predictable_edge_p (then_edge)))))
      return FALSE;
*************** find_if_case_2 (basic_block test_bb, edg
*** 3910,3916 ****
    basic_block then_bb = then_edge->dest;
    basic_block else_bb = else_edge->dest;
    edge else_succ;
!   rtx note;
  
    /* If we are partitioning hot/cold basic blocks, we don't want to
       mess up unconditional or indirect jumps that cross between hot
--- 3927,3933 ----
    basic_block then_bb = then_edge->dest;
    basic_block else_bb = else_edge->dest;
    edge else_succ;
!   int then_prob, else_prob;
  
    /* If we are partitioning hot/cold basic blocks, we don't want to
       mess up unconditional or indirect jumps that cross between hot
*************** find_if_case_2 (basic_block test_bb, edg
*** 3949,3957 ****
    if (then_bb->index < NUM_FIXED_BLOCKS)
      return FALSE;
  
    /* ELSE is predicted or SUCC(ELSE) postdominates THEN.  */
!   note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
!   if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
      ;
    else if (else_succ->dest->index < NUM_FIXED_BLOCKS
  	   || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
--- 3966,3984 ----
    if (then_bb->index < NUM_FIXED_BLOCKS)
      return FALSE;
  
+   if (else_edge->probability)
+     {
+       else_prob = else_edge->probability;
+       then_prob = REG_BR_PROB_BASE - else_prob;
+     }
+   else
+     {
+       else_prob = REG_BR_PROB_BASE / 2;
+       then_prob = REG_BR_PROB_BASE / 2;
+     }
+ 
    /* ELSE is predicted or SUCC(ELSE) postdominates THEN.  */
!   if (else_prob > then_prob)
      ;
    else if (else_succ->dest->index < NUM_FIXED_BLOCKS
  	   || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
*************** find_if_case_2 (basic_block test_bb, edg
*** 3966,3973 ****
  	     "\nIF-CASE-2 found, start %d, else %d\n",
  	     test_bb->index, else_bb->index);
  
!   /* ELSE is small.  */
!   if (! cheap_bb_rtx_cost_p (else_bb,
  	COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (else_edge->src),
  				    predictable_edge_p (else_edge)))))
      return FALSE;
--- 3993,4001 ----
  	     "\nIF-CASE-2 found, start %d, else %d\n",
  	     test_bb->index, else_bb->index);
  
!   /* We're speculating from the ELSE path, we want to make sure the cost
!      of speculation is within reason.  */
!   if (! cheap_bb_rtx_cost_p (else_bb, else_prob,
  	COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (else_edge->src),
  				    predictable_edge_p (else_edge)))))
      return FALSE;