Re: [patch] for one of problems in PR28364

[Jan Hubicka <jh at suse dot cz>]

> Hello,
Hi,
> 
> one of the problems in this PR is a weird code placement with
> -no-tree-loop-ch -- we end up with the return in the middle of the loop,
> causing us to jump around it each time.  This turns out to be caused by
> the deficiences in the updating of edge probabilities and frequencies
> during tree->rtl expansion.  In this particular testcase, we have
> 
> while (1)
>   {
>     ...
>     if (cond1 || cond2)
>       break;
>     ...
>   }
> 
> The exit is estimated to be taken with 4% probability.  The if condition is expanded to
> just one block, that is later split in find_many_sub_basic_blocks.  To
> get the probabilities of the created branches, we use
> compute_outgoing_frequencies, that however estimates the frequencies on
> purely local basis (using guess_outgoing_edge_probabilities), making us
> believe that the two exits are taken with 50% and 30% probabilities.
> This makes all the frequencies hopelessly wrong, confusing bb-reorder
> and making it choose nonsensical order of blocks.
> 
> This patch tries to improve this.  Instead of using
> guess_outgoing_edge_probabilities, it makes us redistribute the
> frequencies evenly, so the outgoing edges have ~2% probability each,
> and the frequencies sum correctly.

Yep, this seems to make sense to me (we should use
guess-outgoing_edge_probabilities only for edges destinating inside the
split regions. I never implemented this as dealing with general case is
dificult.  This seems like good simplification.  I also have simple fix
to fix count estimation on self loops we construct while expanding
memcpy and such)

In genera,l of course, we should not TER the above conditional so we
should not end up with multiple exit edges.  However even without TER
still can create the exit edges by non-trivial expansion of the
conditional (ie for floats or long longs on i386) and in that case
probably machine description should be responsible for distributing
probabilities, but we don't do that and I am unsure it is worth the
effort, so this seems very resonable in longer term too.
> + 
> + /* Determine the probabilities in subblocks created by splitting
> +    basic block BB.  */

Some introductory comment to the black magic with testcase would help I
guess ;)

The patch is OK for mainline once it reopens for stage1.  I am not sure
if this classify as stage3 fix (ie it is quite a lot of code but still
relatively safe).  Do you have idea how often it helps?

I am also attaching the self loop code I use in my local tree (waiting
for stage1) in case you want to go ahead and integrate it with your
patch ;). It probably could be extended to superblock loops since memcpy
can have EH edge in it.

Honza

Index: cfgbuild.c
===================================================================
*** cfgbuild.c	(revision 115583)
--- cfgbuild.c	(working copy)
*************** static void find_basic_blocks_1 (rtx);
*** 51,57 ****
  static void make_edges (basic_block, basic_block, int);
  static void make_label_edge (sbitmap, basic_block, rtx, int);
  static void find_bb_boundaries (basic_block);
- static void compute_outgoing_frequencies (basic_block);
  
  /* Return true if insn is something that should be contained inside basic
     block.  */
--- 51,56 ----
*************** find_bb_boundaries (basic_block bb)
*** 696,709 ****
      purge_dead_tablejump_edges (bb, table);
  }
  
! /*  Assume that frequency of basic block B is known.  Compute frequencies
!     and probabilities of outgoing edges.  */
! 
  static void
! compute_outgoing_frequencies (basic_block b)
  {
    edge e, f;
-   edge_iterator ei;
  
    if (EDGE_COUNT (b->succs) == 2)
      {
--- 695,705 ----
      purge_dead_tablejump_edges (bb, table);
  }
  
! /* Compute probabilities of succestor edges of B.  */
  static void
! compute_outgoing_probabilities (basic_block b)
  {
    edge e, f;
  
    if (EDGE_COUNT (b->succs) == 2)
      {
*************** compute_outgoing_frequencies (basic_bloc
*** 715,741 ****
  	  probability = INTVAL (XEXP (note, 0));
  	  e = BRANCH_EDGE (b);
  	  e->probability = probability;
- 	  e->count = ((b->count * probability + REG_BR_PROB_BASE / 2)
- 		      / REG_BR_PROB_BASE);
  	  f = FALLTHRU_EDGE (b);
  	  f->probability = REG_BR_PROB_BASE - probability;
- 	  f->count = b->count - e->count;
  	  return;
  	}
      }
- 
    if (single_succ_p (b))
      {
        e = single_succ_edge (b);
        e->probability = REG_BR_PROB_BASE;
-       e->count = b->count;
        return;
      }
    guess_outgoing_edge_probabilities (b);
!   if (b->count)
!     FOR_EACH_EDGE (e, ei, b->succs)
!       e->count = ((b->count * e->probability + REG_BR_PROB_BASE / 2)
! 		  / REG_BR_PROB_BASE);
  }
  
  /* Assume that some pass has inserted labels or control flow
--- 711,745 ----
  	  probability = INTVAL (XEXP (note, 0));
  	  e = BRANCH_EDGE (b);
  	  e->probability = probability;
  	  f = FALLTHRU_EDGE (b);
  	  f->probability = REG_BR_PROB_BASE - probability;
  	  return;
  	}
      }
    if (single_succ_p (b))
      {
        e = single_succ_edge (b);
        e->probability = REG_BR_PROB_BASE;
        return;
      }
    guess_outgoing_edge_probabilities (b);
! }
! 
! /*  Assume that counts of basic block B is known.  Compute counts
!     of outgoing edges.  */
! 
! static void
! compute_outgoing_counts (basic_block b)
! {
!   edge e;
!   edge_iterator ei;
! 
!   if (!b->count)
!     return;
! 
!   FOR_EACH_EDGE (e, ei, b->succs)
!     e->count = ((b->count * e->probability + REG_BR_PROB_BASE / 2)
! 		/ REG_BR_PROB_BASE);
  }
  
  /* Assume that some pass has inserted labels or control flow
*************** find_many_sub_basic_blocks (sbitmap bloc
*** 778,795 ****
  
  	if (STATE (bb) == BLOCK_ORIGINAL)
  	  continue;
  	if (STATE (bb) == BLOCK_NEW)
  	  {
  	    bb->count = 0;
  	    bb->frequency = 0;
  	    FOR_EACH_EDGE (e, ei, bb->preds)
  	      {
! 		bb->count += e->count;
! 		bb->frequency += EDGE_FREQUENCY (e);
! 	      }
  	  }
  
! 	compute_outgoing_frequencies (bb);
        }
  
    FOR_EACH_BB (bb)
--- 782,819 ----
  
  	if (STATE (bb) == BLOCK_ORIGINAL)
  	  continue;
+ 	compute_outgoing_probabilities (bb);
  	if (STATE (bb) == BLOCK_NEW)
  	  {
+ 	    int loop_prob = 0;
  	    bb->count = 0;
  	    bb->frequency = 0;
  	    FOR_EACH_EDGE (e, ei, bb->preds)
  	      {
! 		if (e->src != bb)
! 		  {
! 		    bb->count += e->count;
! 		    bb->frequency += EDGE_FREQUENCY (e);
! 		  }
! 		else
! 		  loop_prob += e->probability;
! 	       }
! 	     if (loop_prob >= REG_BR_PROB_BASE)
! 		loop_prob = REG_BR_PROB_BASE - 1;
! 	     if (loop_prob)
! 	       {
! 		 int niter = (REG_BR_PROB_BASE / (REG_BR_PROB_BASE - loop_prob));
! 
! 		 bb->count *= niter;
! 		 /* Too large number of iterations may lead to overflows later.  */
! 		 if (bb->frequency * niter > REG_BR_PROB_BASE * 10)
! 		   bb->frequency = REG_BR_PROB_BASE * 10;
! 		 else
! 		   bb->frequency *= niter;
! 	       }
  	  }
  
! 	compute_outgoing_counts (bb);
        }
  
    FOR_EACH_BB (bb)