Continue stmt branch prediction

Continue stmt branch prediction

[Jan Hubicka]

Hi,
this patch adds a continue branch predictor that was dropped by introduction of
gimplifier (that replaced continue statement by goto).

The idea is that continue statements forms a loops that are usually not looping,
as proper loops are written via the loop construct.  On SPECint2000 average loop
tends to loop 7 times, while average loop constructed via continue loops less
than once.

The prediction is implemented via high level predictors that used also to predict,
for example, that explicit goto statements are not taken (this is helping kernel) 
and can be used for other stuff in other languages too.
I will re-introduce the other predictors by followups later, this patch was
developed while looking into the gzip regression as predicting continue formed
loop to loop a lot is one of problems there:

statement
  if (test1 || test2 || test3 || test4)
    continue;

is in mainline handled as 4 nested loops, each predicted to loop roughly 4 times, 
making all the rest of function cold.

Since the patch itself is not solving the regression fully (it makes improvement
on prelbmk 64bit peak, 920->980, and gzip 64bit, 750->770) but irronically it causes
regression at -O3 score of gzip 32bit by exposing other problems.  So I am holding
it for 4.4.

The branch prediction bits I can approve myself, but I would welcome comment on
introducing PREDICT_EXPR.  This was discussed while ago on GCC summit.  (the
original patch was done at CFG expansion times, but since we was about to run
out of tree codes I holded it and then forgot about the issue completely).

Bootstrapped/regtested i686-linux.

Honza

	* tree-pretty-print.c: Include predict.h.
	(dump_generic_node): Dump predictor.
	* tree.h (PREDICT_EXPR_OUTCOME, PREDICT_EXPR_PREDICTION): Update.
	* tree-gimple.c (is_gimple_stmt): Add PREDICT_EXPR.
	* gimple-low.c (lower_stmt): Likewise.
	* expr.c (expand_expr_real): Likewise.
	* predict.c (tree_bb_level_predictions): Use PREDICT_EXPRs and remove
	them.
	(build_predict_expr, build_predict_expr): New.
	* predict.h (predictor_name, build_predict_expr): Update.
	* c-typeck.c (c_finish_bc_stmt): Add prediction.
	* gimplify.c (gimplify_expr): Add PREDICT_EXPR.
	* predict.def (PRED_CONTINUE): Update hitrate.
	* tree.def (PREDICT_EXPR): Define.
	* tree-ssa-dce.c (mark_stmt_if_obviously_necessary): Mark PREDICT_EXPR;
	do not handle BIND_EXPR.
	* tree-inline.c (estimate_num_insns_1): PREDICT_EXPR is free.
	* tree-cfg.c (verify_gimple_stmt): PREDICT_EXPR is valid.
	* tree-ssa-operands.c (get_expr_operands): PREDICT_EXPR takes no operands.


Index: tree-pretty-print.c
===================================================================
*** tree-pretty-print.c	(revision 132144)
--- tree-pretty-print.c	(working copy)
*************** along with GCC; see the file COPYING3.  
*** 35,40 ****
--- 35,41 ----
  #include "tree-pass.h"
  #include "fixed-value.h"
  #include "value-prof.h"
+ #include "predict.h"
  
  /* Local functions, macros and variables.  */
  static int op_prio (const_tree);
*************** dump_generic_node (pretty_printer *buffe
*** 1586,1591 ****
--- 1587,1602 ----
        is_expr = false;
        break;
  
+     case PREDICT_EXPR:
+       pp_string (buffer, "// predicted ");
+       if (PREDICT_EXPR_OUTCOME (node))
+         pp_string (buffer, "likely by ");
+       else
+         pp_string (buffer, "unlikely by ");
+       pp_string (buffer, predictor_name (PREDICT_EXPR_PREDICTOR (node)));
+       pp_string (buffer, " predictor.");
+       break;
+ 
      case RETURN_EXPR:
        pp_string (buffer, "return");
        op0 = TREE_OPERAND (node, 0);
Index: tree.h
===================================================================
*** tree.h	(revision 132144)
--- tree.h	(working copy)
*************** struct gimple_stmt GTY(())
*** 436,441 ****
--- 436,442 ----
  	   expression.
         CALL_EXPR_TAILCALL in CALL_EXPR
         CASE_LOW_SEEN in CASE_LABEL_EXPR
+        RETURN_EXPR_OUTCOME in RETURN_EXPR
  
     static_flag:
  
*************** extern void omp_clause_range_check_faile
*** 1160,1165 ****
--- 1161,1171 ----
  #define CASE_LOW_SEEN(NODE) \
    (CASE_LABEL_EXPR_CHECK (NODE)->base.addressable_flag)
  
+ #define PREDICT_EXPR_OUTCOME(NODE) \
+   (PREDICT_EXPR_CHECK(NODE)->base.addressable_flag)
+ #define PREDICT_EXPR_PREDICTOR(NODE) \
+   ((enum br_predictor)tree_low_cst (TREE_OPERAND (PREDICT_EXPR_CHECK (NODE), 0), 0))
+ 
  /* In a VAR_DECL, nonzero means allocate static storage.
     In a FUNCTION_DECL, nonzero if function has been defined.
     In a CONSTRUCTOR, nonzero means allocate static storage.
Index: tree-gimple.c
===================================================================
*** tree-gimple.c	(revision 132144)
--- tree-gimple.c	(working copy)
*************** is_gimple_stmt (tree t)
*** 248,253 ****
--- 248,254 ----
  
      case CALL_EXPR:
      case GIMPLE_MODIFY_STMT:
+     case PREDICT_EXPR:
        /* These are valid regardless of their type.  */
        return true;
  
Index: gimple-low.c
===================================================================
*** gimple-low.c	(revision 132144)
--- gimple-low.c	(working copy)
*************** lower_stmt (tree_stmt_iterator *tsi, str
*** 239,244 ****
--- 239,245 ----
      case NOP_EXPR:
      case ASM_EXPR:
      case GOTO_EXPR:
+     case PREDICT_EXPR:
      case LABEL_EXPR:
      case SWITCH_EXPR:
      case CHANGE_DYNAMIC_TYPE_EXPR:
Index: expr.c
===================================================================
*** expr.c	(revision 132144)
--- expr.c	(working copy)
*************** expand_expr_real (tree exp, rtx target, 
*** 7053,7058 ****
--- 7053,7059 ----
  
    /* Handle ERROR_MARK before anybody tries to access its type.  */
    if (TREE_CODE (exp) == ERROR_MARK
+       || TREE_CODE (exp) == PREDICT_EXPR
        || (!GIMPLE_TUPLE_P (exp) && TREE_CODE (TREE_TYPE (exp)) == ERROR_MARK))
      {
        ret = CONST0_RTX (tmode);
Index: predict.c
===================================================================
*** predict.c	(revision 132144)
--- predict.c	(working copy)
*************** static void
*** 1286,1310 ****
  tree_bb_level_predictions (void)
  {
    basic_block bb;
-   int *heads;
  
!   heads = XCNEWVEC (int, last_basic_block);
!   heads[ENTRY_BLOCK_PTR->next_bb->index] = last_basic_block;
! 
!   apply_return_prediction (heads);
  
    FOR_EACH_BB (bb)
      {
        block_stmt_iterator bsi = bsi_last (bb);
  
!       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
  	{
  	  tree stmt = bsi_stmt (bsi);
  	  tree decl;
  	  switch (TREE_CODE (stmt))
  	    {
  	      case GIMPLE_MODIFY_STMT:
--- 1290,1307 ----
  tree_bb_level_predictions (void)
  {
    basic_block bb;
  
!   apply_return_prediction ();
  
!   heads = XCNEWVEC (int, last_basic_block);
!   heads[ENTRY_BLOCK_PTR->next_bb->index] = last_basic_block;
! 
!   apply_return_prediction (heads);
    FOR_EACH_BB (bb)
      {
        block_stmt_iterator bsi = bsi_last (bb);
  
!       for (bsi = bsi_start (bb); !bsi_end_p (bsi);)
  	{
  	  tree stmt = bsi_stmt (bsi);
  	  tree decl;
+ 	  bool next = false;
  	  switch (TREE_CODE (stmt))
  	    {
  	      case GIMPLE_MODIFY_STMT:
*************** tree_bb_level_predictions (void)
*** 1313,1336 ****
  	      case CALL_EXPR:
  call_expr:;
  		if (call_expr_flags (stmt) & ECF_NORETURN)
! 		  predict_paths_leading_to (bb, heads, PRED_NORETURN,
  		      			    NOT_TAKEN);
  		decl = get_callee_fndecl (stmt);
  		if (decl
  		    && lookup_attribute ("cold",
  					 DECL_ATTRIBUTES (decl)))
! 		  predict_paths_leading_to (bb, heads, PRED_COLD_FUNCTION,
  		      			    NOT_TAKEN);
  		break;
  	      default:
  		break;
  	    }
  	}
      }
  
    free (heads);
  }
  
  #ifdef ENABLE_CHECKING
--- 1314,1341 ----
  	      case CALL_EXPR:
  call_expr:;
  		if (call_expr_flags (stmt) & ECF_NORETURN)
! 		  predict_paths_leading_to (bb, heads, PRED_NORETURN,
  		      			    NOT_TAKEN);
  		decl = get_callee_fndecl (stmt);
  		if (decl
  		    && lookup_attribute ("cold",
  					 DECL_ATTRIBUTES (decl)))
! 		  predict_paths_leading_to (bb, heads, PRED_COLD_FUNCTION,
  		      			    NOT_TAKEN);
  		break;
+ 	      case PREDICT_EXPR:
+ 		predict_paths_leading_to (bb, heads, PREDICT_EXPR_PREDICTOR (stmt),
+ 		      			  PREDICT_EXPR_OUTCOME (stmt));
+ 		bsi_remove (&bsi, true);
+ 		next = true;
+ 		break;
  	      default:
  		break;
  	    }
+ 	  if (!next)
+ 	    bsi_next (&bsi);
  	}
      }
  }
  
  #ifdef ENABLE_CHECKING
*************** gate_estimate_probability (void)
*** 1937,1942 ****
--- 1930,1950 ----
    return flag_guess_branch_prob;
  }
  
+ /* Build PREDICT_EXPR.  */
+ tree
+ build_predict_expr (enum br_predictor predictor, enum prediction taken)
+ {
+   tree t = build1 (PREDICT_EXPR, NULL_TREE, build_int_cst (NULL, predictor));
+   PREDICT_EXPR_OUTCOME (t) = taken;
+   return t;
+ }
+ 
+ const char *
+ predictor_name (enum br_predictor predictor)
+ {
+   return predictor_info[predictor].name;
+ }
+ 
  struct tree_opt_pass pass_profile = 
  {
    "profile",				/* name */
Index: predict.h
===================================================================
*** predict.h	(revision 132144)
--- predict.h	(working copy)
*************** enum prediction
*** 38,42 ****
--- 38,44 ----
  extern void predict_insn_def (rtx, enum br_predictor, enum prediction);
  extern int counts_to_freqs (void);
  extern void estimate_bb_frequencies (void);
+ extern const char *predictor_name (enum br_predictor);
+ extern tree build_predict_expr (enum br_predictor, enum prediction);
  
  #endif  /* GCC_PREDICT_H */
Index: c-typeck.c
===================================================================
*** c-typeck.c	(revision 132144)
--- c-typeck.c	(working copy)
*************** c_finish_bc_stmt (tree *label_p, bool is
*** 7500,7505 ****
--- 7500,7508 ----
    if (skip)
      return NULL_TREE;
  
+   if (!is_break)
+     add_stmt (build_predict_expr (PRED_CONTINUE, NOT_TAKEN));
+ 
    return add_stmt (build1 (GOTO_EXPR, void_type_node, label));
  }
  
Index: gimplify.c
===================================================================
*** gimplify.c	(revision 132144)
--- gimplify.c	(working copy)
*************** gimplify_expr (tree *expr_p, tree *pre_p
*** 5833,5838 ****
--- 5833,5842 ----
  				 NULL, is_gimple_val, fb_rvalue);
  	  break;
  
+ 	  /* Predictions are always gimplified.  */
+ 	case PREDICT_EXPR:
+ 	  goto out;
+ 
  	case LABEL_EXPR:
  	  ret = GS_ALL_DONE;
  	  gcc_assert (decl_function_context (LABEL_EXPR_LABEL (*expr_p))
Index: predict.def
===================================================================
*** predict.def	(revision 132144)
--- predict.def	(working copy)
*************** DEF_PREDICTOR (PRED_LOOP_ITERATIONS_GUES
*** 66,72 ****
  	       PROB_ALWAYS, PRED_FLAG_FIRST_MATCH)
  
  /* Branch containing goto is probably not taken.  */
! DEF_PREDICTOR (PRED_CONTINUE, "continue", HITRATE (56), 0)
  
  /* Branch to basic block containing call marked by noreturn attribute.  */
  DEF_PREDICTOR (PRED_NORETURN, "noreturn call", HITRATE (99),
--- 66,72 ----
  	       PROB_ALWAYS, PRED_FLAG_FIRST_MATCH)
  
  /* Branch containing goto is probably not taken.  */
! DEF_PREDICTOR (PRED_CONTINUE, "continue", HITRATE (50), 0)
  
  /* Branch to basic block containing call marked by noreturn attribute.  */
  DEF_PREDICTOR (PRED_NORETURN, "noreturn call", HITRATE (99),
Index: tree.def
===================================================================
*** tree.def	(revision 132144)
--- tree.def	(working copy)
*************** DEFTREECODE (VEC_EXTRACT_ODD_EXPR, "vec_
*** 1165,1170 ****
--- 1165,1176 ----
  DEFTREECODE (VEC_INTERLEAVE_HIGH_EXPR, "vec_interleavehigh_expr", tcc_binary, 2)
  DEFTREECODE (VEC_INTERLEAVE_LOW_EXPR, "vec_interleavelow_expr", tcc_binary, 2)
  
+ /* PREDICT_EXPR.  Specify hint for branch prediction.  The
+    PREDICT_EXPR_PREDICTOR specify predictor and PREDICT_EXPR_OUTCOME the
+    outcome (0 for not taken and 1 for taken).  Once the profile is guessed
+    all conditional branches leading to execution paths executing the
+    PREDICT_EXPR will get predicted by the specified predictor.  */
+ DEFTREECODE (PREDICT_EXPR, "predict_expr", tcc_unary, 1)
  /*
  Local variables:
  mode:c
Index: tree-ssa-dce.c
===================================================================
*** tree-ssa-dce.c	(revision 132144)
--- tree-ssa-dce.c	(working copy)
*************** mark_stmt_if_obviously_necessary (tree s
*** 277,283 ****
       can then remove the block and labels.  */
    switch (TREE_CODE (stmt))
      {
!     case BIND_EXPR:
      case LABEL_EXPR:
      case CASE_LABEL_EXPR:
        mark_stmt_necessary (stmt, false);
--- 277,283 ----
       can then remove the block and labels.  */
    switch (TREE_CODE (stmt))
      {
!     case PREDICT_EXPR:
      case LABEL_EXPR:
      case CASE_LABEL_EXPR:
        mark_stmt_necessary (stmt, false);
Index: tree-inline.c
===================================================================
*** tree-inline.c	(revision 132144)
--- tree-inline.c	(working copy)
*************** estimate_num_insns_1 (tree *tp, int *wal
*** 2265,2270 ****
--- 2265,2271 ----
      case COMPLEX_CST:
      case VECTOR_CST:
      case STRING_CST:
+     case PREDICT_EXPR:
        *walk_subtrees = 0;
        return NULL;
  
Index: tree-cfg.c
===================================================================
*** tree-cfg.c	(revision 132144)
--- tree-cfg.c	(working copy)
*************** verify_gimple_stmt (tree stmt)
*** 4065,4070 ****
--- 4065,4071 ----
      case NOP_EXPR:
      case CHANGE_DYNAMIC_TYPE_EXPR:
      case ASM_EXPR:
+     case PREDICT_EXPR:
        return false;
  
      default:
Index: tree-ssa-operands.c
===================================================================
*** tree-ssa-operands.c	(revision 132144)
--- tree-ssa-operands.c	(working copy)
*************** get_expr_operands (tree stmt, tree *expr
*** 2376,2381 ****
--- 2376,2382 ----
      case OMP_RETURN:
      case OMP_SECTION:
      case OMP_SECTIONS_SWITCH:
+     case PREDICT_EXPR:
        /* Expressions that make no memory references.  */
        return;
  

Re: Continue stmt branch prediction

[Diego Novillo]

On Sat, Feb 9, 2008 at 2:48 PM, Jan Hubicka <jh@suse.cz> wrote:

>  statement
>   if (test1 || test2 || test3 || test4)
>     continue;

I'm wondering if we really need another IL node for this.  Why not add
new attributes to GOTO_EXPR, instead?  Those then become edge
attributes.  Much less machinery to manipulate this way.


Diego.

Re: Continue stmt branch prediction

[Jan Hubicka]

> On Sat, Feb 9, 2008 at 2:48 PM, Jan Hubicka <jh@suse.cz> wrote:
> 
> >  statement
> >   if (test1 || test2 || test3 || test4)
> >     continue;
> 
> I'm wondering if we really need another IL node for this.  Why not add
> new attributes to GOTO_EXPR, instead?  Those then become edge

Well, this was discussed some time ago too.
Adding flag to GOTO_EXPR has few problems:
  1) One would need to disable cfg operations killing the flag 
  (branch forwarding, jump threading, basic block merging and friends)
  This effectively mean to teach code that marked GOTO_EXPR is a real
  statement that goes nicely with PREDICT_EXPR in the code.

  Statement is relatively short lived but still one has to iterate over
  early cleanup passes.

  2) The high level predictors are intended to be more generic than just
  for CONTINUE and GOTO statements as done by this patch.
  (that is, for example, EH machinery, bounds checking code, OMP
  expansion, default path of SWITCH statement of C enum with all named
  values taken specially, or error recovery. Simply cases that are easy
  to identify at language level but that is getting translated to gimple
  code that is not properly predicted by the low level stuff).

  It is true that in GCC we sort of stopped on those two simple cases.
  Some extra ideas for C (not that good IMO) are discussed in 
  http://citeseer.ist.psu.edu/249874.html. Other languages we support
  surely has more high level constructs that falls into this category.

Honza
> attributes.  Much less machinery to manipulate this way.
> 
> 
> Diego.

Re: Continue stmt branch prediction

[Diego Novillo]

On Sun, Feb 10, 2008 at 10:17 AM, Jan Hubicka <jh@suse.cz> wrote:

>   Statement is relatively short lived but still one has to iterate over
>   early cleanup passes.

OK, but this statement also does not seem to affect data-flow and has
hidden semantics.  Unless optimizations treat it specially, the
statement may be moved or removed.  I'm not sure I understand the
semantics too well, either.


>   2) The high level predictors are intended to be more generic than just
>   for CONTINUE and GOTO statements as done by this patch.
>   (that is, for example, EH machinery, bounds checking code, OMP
>   expansion, default path of SWITCH statement of C enum with all named
>   values taken specially, or error recovery. Simply cases that are easy
>   to identify at language level but that is getting translated to gimple
>   code that is not properly predicted by the low level stuff).

OK, this is useful.  What if get rid of this statement after building
the CFG?  The only thing that bothers me about it is the magic
dataflow (rather, the lack of dataflow).  On CFG build, we'd set the
predict bits as edge attributes, which is really where they are
needed, IIUC.


>   It is true that in GCC we sort of stopped on those two simple cases.
>   Some extra ideas for C (not that good IMO) are discussed in
>   http://citeseer.ist.psu.edu/249874.html. Other languages we support
>   surely has more high level constructs that falls into this category.

Thanks.  Will take a look.


Diego.

Re: Continue stmt branch prediction

[Jan Hubicka]

> On Sun, Feb 10, 2008 at 10:17 AM, Jan Hubicka <jh@suse.cz> wrote:
> 
> >   Statement is relatively short lived but still one has to iterate over
> >   early cleanup passes.
> 
> OK, but this statement also does not seem to affect data-flow and has
> hidden semantics.  Unless optimizations treat it specially, the
> statement may be moved or removed.  I'm not sure I understand the
> semantics too well, either.

Well, the statement just sits there and does nothing, has no operands.
It is just note saying that across that portion of program the control
flow passes either regularlly or iregularly, based on the prediction.
From control flow POW it is not different than any statement with side
effect: function call, volatile asm.

As far as I know only pass that needs modification is DCE that needs to
know that the statement should not be removed (and ICEs otherwise on
unknown thingy). All propagation stuff cares just about operands that
are none.  This seems relatively robust to me.

On RTL level this used to be implemented with INSN_NOTE.  I agree that
INSN_NOTEs are pretty evil, but their evilness live in a fact that they
are not statements (or instructions) and they not live in basic blocks,
rather based on type of note they are drifiting from BB to BB.

PREDICT_EXPR is not weird in this way: because it is there for short
time, we don't care about fact that we can't optimize out, for instance,
optimize:

if (test)
  predict_expr something.

So we can declare it a proper statement.
> 
> 
> >   2) The high level predictors are intended to be more generic than just
> >   for CONTINUE and GOTO statements as done by this patch.
> >   (that is, for example, EH machinery, bounds checking code, OMP
> >   expansion, default path of SWITCH statement of C enum with all named
> >   values taken specially, or error recovery. Simply cases that are easy
> >   to identify at language level but that is getting translated to gimple
> >   code that is not properly predicted by the low level stuff).
> 
> OK, this is useful.  What if get rid of this statement after building
> the CFG?  The only thing that bothers me about it is the magic

We get rid of the statement during tree_profile pass.  It is later than
CFG build, because the early cleanups tends to be busy on CFG
manipulations and profile built bit later after the early passes tends
to be more realistic and survive more consistent across the
optimization.

If we lower PREDICT_EXPR into an edge, we will end up with kind of
volatile edge we don't want to optimize across.  We can add EH_PREDICTED
flag implying EH_ABNORMAL and have on side hashtable holding those
predictors and we will have all the usual fun with ABNORMAL_PHI stuff.

We can probably do that, but I don't necessarily see a win here: we have
fewer special kinds of CFG edges than we have kinds of statements and it
seems right to me. Also this way we would end up with both, though the
statement would be short lived.

> dataflow (rather, the lack of dataflow).  On CFG build, we'd set the
> predict bits as edge attributes, which is really where they are
> needed, IIUC.
> 
> 
> >   It is true that in GCC we sort of stopped on those two simple cases.
> >   Some extra ideas for C (not that good IMO) are discussed in
> >   http://citeseer.ist.psu.edu/249874.html. Other languages we support
> >   surely has more high level constructs that falls into this category.
> 
> Thanks.  Will take a look.

I warned you it is not particularly good paper, but if you search for
language level branch prediction, there are other studies of this too.

Honza
> 
> 
> Diego.

Re: Continue stmt branch prediction

[Andrew MacLeod]

Jan Hubicka wrote:
> The prediction is implemented via high level predictors that used also to predict,
> for example, that explicit goto statements are not taken (this is helping kernel) 
> and can be used for other stuff in other languages too.
> I will re-introduce the other predictors by followups later, this patch was
> developed while looking into the gzip regression as predicting continue formed
>   

What are the other predictors?  It might help to understand it better if 
we had a better overview of everything PREDICT_EXPR was going to do.

Andrew

Re: Continue stmt branch prediction

[Jan Hubicka]

> Jan Hubicka wrote:
> >The prediction is implemented via high level predictors that used also to 
> >predict,
> >for example, that explicit goto statements are not taken (this is helping 
> >kernel) and can be used for other stuff in other languages too.
> >I will re-introduce the other predictors by followups later, this patch was
> >developed while looking into the gzip regression as predicting continue 
> >formed
> >  
> 
> What are the other predictors?  It might help to understand it better if 
> we had a better overview of everything PREDICT_EXPR was going to do.

I was mostly looking into following stuff:
  1) the continue bit
  2) explicit goto statements are usually not executed
  3) default path of C switch statement on emum with all named fields
  explicit is unlikely
  4) expanded bounds checks (ie arrays tends to be in bounds. We used to
  have PRED_MUDLFAP here but it was dropped and Java has similar logic)
  5) expanded openMP constructs
  6) higher level constructs from non-C frontends we have.  There are
  cases where we produce control flow expanding stuff like fortran
  vectors where we have unlikely paths through. Though I didn't look
  into great detail into this yet.

We already handle same way the calls to noreturn functions and functions
marked via cold attribute, but those are easilly recognized on gimple
and don't need extra marker. 

Honza
> 
> Andrew

Re: Continue stmt branch prediction

[Richard Guenther]

On Thu, Feb 14, 2008 at 4:11 PM, Jan Hubicka <jh@suse.cz> wrote:
>
> > Jan Hubicka wrote:
>  > >The prediction is implemented via high level predictors that used also to
>  > >predict,
>  > >for example, that explicit goto statements are not taken (this is helping
>  > >kernel) and can be used for other stuff in other languages too.
>  > >I will re-introduce the other predictors by followups later, this patch was
>  > >developed while looking into the gzip regression as predicting continue
>  > >formed
>  > >
>  >
>  > What are the other predictors?  It might help to understand it better if
>  > we had a better overview of everything PREDICT_EXPR was going to do.
>
>  I was mostly looking into following stuff:
>   1) the continue bit
>   2) explicit goto statements are usually not executed
>   3) default path of C switch statement on emum with all named fields
>   explicit is unlikely
>   4) expanded bounds checks (ie arrays tends to be in bounds. We used to
>   have PRED_MUDLFAP here but it was dropped and Java has similar logic)
>   5) expanded openMP constructs
>   6) higher level constructs from non-C frontends we have.  There are
>   cases where we produce control flow expanding stuff like fortran
>   vectors where we have unlikely paths through. Though I didn't look
>   into great detail into this yet.
>
>  We already handle same way the calls to noreturn functions and functions
>  marked via cold attribute, but those are easilly recognized on gimple
>  and don't need extra marker.

Wouldn't it be easier to add a unlikely_goto stmt for all these and translate
that to edge probabilities once we build the cfg?  That is, stick the unlikely
bit onto the goto stmt instead of having an extra predict_expr floating around.

Richard.

Re: Continue stmt branch prediction

[Andrew MacLeod]

>> What are the other predictors?  It might help to understand it better if 
>> we had a better overview of everything PREDICT_EXPR was going to do.
>>     
>
> I was mostly looking into following stuff:
>   1) the continue bit
>   2) explicit goto statements are usually not executed
>   3) default path of C switch statement on emum with all named fields
>   explicit is unlikely
>   4) expanded bounds checks (ie arrays tends to be in bounds. We used to
>   have PRED_MUDLFAP here but it was dropped and Java has similar logic)
>   5) expanded openMP constructs
>   6) higher level constructs from non-C frontends we have.  There are
>   cases where we produce control flow expanding stuff like fortran
>   vectors where we have unlikely paths through. Though I didn't look
>   into great detail into this yet.
>
> We already handle same way the calls to noreturn functions and functions
> marked via cold attribute, but those are easilly recognized on gimple
> and don't need extra marker. 
>
>   
So if I get the idea:

 When these higher level constructs are being lowered, their usual 
behaviour is used to place PREDICT_EXPR into the insn stream to indicate 
whether this path code is likely to be executed or not.

And these PREDICT_EXPR's just bob along in the code stream as its moved 
around so that later on, we can reconstruct the likely paths by scanning 
the IL. Their primary function is to modify branch probabilities from 
what would otherwise be the default? Whether they are created or not 
affects nothing but branch probabilities (and of course generated code 
performance, but never correctness).  And if they somehow ended up in 
the wrong place, again, it only affects probabilities?

So there is therefore no flow or other side effects from these expressions.

These thing primarily exist before we get around to being able to 
annotate branches and such with probabilities of being taken, and once 
that happens, we chuck them never to be seen again?   And they also 
indicate nothing but TRUE if this is an expected code path, or FALSE if 
its not expected.

Is that more or less correct?

Andrew

Re: Continue stmt branch prediction

[Jan Hubicka]

> 
> Wouldn't it be easier to add a unlikely_goto stmt for all these and translate
> that to edge probabilities once we build the cfg?  That is, stick the unlikely
> bit onto the goto stmt instead of having an extra predict_expr floating around.

We've disucussed this few mails back.  The problem is that if you have
something like

if (something)
   something2
   goto somewhere else

somewhere else:
   something_else

then after gimplifing we get


if (something) goto around
something2
somewehre_else
around:

and goto is gone.  It is really more a property of the some specific
place in program (ie source level construct sitting in between something
and somewhere_else) rather than than property of control flow statement
itself.

Honza
> 
> Richard.

Re: Continue stmt branch prediction

[Jan Hubicka]

> 
> >>What are the other predictors?  It might help to understand it better if 
> >>we had a better overview of everything PREDICT_EXPR was going to do.
> >>    
> >
> >I was mostly looking into following stuff:
> >  1) the continue bit
> >  2) explicit goto statements are usually not executed
> >  3) default path of C switch statement on emum with all named fields
> >  explicit is unlikely
> >  4) expanded bounds checks (ie arrays tends to be in bounds. We used to
> >  have PRED_MUDLFAP here but it was dropped and Java has similar logic)
> >  5) expanded openMP constructs
> >  6) higher level constructs from non-C frontends we have.  There are
> >  cases where we produce control flow expanding stuff like fortran
> >  vectors where we have unlikely paths through. Though I didn't look
> >  into great detail into this yet.
> >
> >We already handle same way the calls to noreturn functions and functions
> >marked via cold attribute, but those are easilly recognized on gimple
> >and don't need extra marker. 
> >
> >  
> So if I get the idea:
> 
> When these higher level constructs are being lowered, their usual 
> behaviour is used to place PREDICT_EXPR into the insn stream to indicate 
> whether this path code is likely to be executed or not.
> 
> And these PREDICT_EXPR's just bob along in the code stream as its moved 
> around so that later on, we can reconstruct the likely paths by scanning 
> the IL. Their primary function is to modify branch probabilities from 
> what would otherwise be the default? Whether they are created or not 
> affects nothing but branch probabilities (and of course generated code 
> performance, but never correctness).  And if they somehow ended up in 
> the wrong place, again, it only affects probabilities?

Yes, this is correct.  Except that I hope they won't end up in wrong
place precisely because they are statement and sit in the control flow
on the place the original construct was.  But if they do, we just mess
the profile.

> 
> So there is therefore no flow or other side effects from these expressions.

Yes.
> 
> These thing primarily exist before we get around to being able to 
> annotate branches and such with probabilities of being taken, and once 
> that happens, we chuck them never to be seen again?   And they also 
> indicate nothing but TRUE if this is an expected code path, or FALSE if 
> its not expected.

They have TRUE/FALSE (or TAKEN flag as it is called in the patch) along
with PREDICTOR.  The predictor is enum defined in predict_def that
defines the reliability of prediction and translates to branch
percentages at the time we lower them to actual profile and nuke away.

(just for overview.

Our branch prediction code is organized into set of predictors, each
having its entry in predict.def.  They are annotated to the CFG edges
during tree profile and later combined into single outcome using
statistical tool combining hypothesis with different reliabilities into
singly hypotesis and reliability that is then used as predicted branch
outcome.

The reliablities are measured by one of our SPEC testers by comparing
real branch outcomes from -fprofile-use with ones predicted.

The PREDICT_EXPR at this time is lowered in a way so all paths arriving
to the place in program PREDICT_EXPRs sits get the conditional from last
basic block on path not posdominated by PREDICT_EXPR to the first bb
postdominated predicted with the specified predictor)
> 
> Is that more or less correct?

Definitly.
Honza
> 
> Andrew
> 

Re: Continue stmt branch prediction

[Andrew MacLeod]

Jan Hubicka wrote:
>> Wouldn't it be easier to add a unlikely_goto stmt for all these and translate
>> that to edge probabilities once we build the cfg?  That is, stick the unlikely
>> bit onto the goto stmt instead of having an extra predict_expr floating around.
>>     
>
> We've disucussed this few mails back.  The problem is that if you have
> something like
>
> if (something)
>    something2
>    goto somewhere else
>
> somewhere else:
>    something_else
>
> then after gimplifing we get
>
>
> if (something) goto around
> something2
> somewehre_else
> around:
>
> and goto is gone.  It is really more a property of the some specific
>   
This example doesn't seem right. You've just changed the meaning of the 
'if' in your example... At least the way I read it. you are no longer 
executing 'something2' if 'something' is true, nor executing 'something 
else' on both paths as in the original case. There are too many 
different things you could have meant for me to guess exactly what you 
did mean :-)

I'll try tho :-)

Did you perhaps mean to reverse the condition to if (!something) in the 
latter case?  If so, then you seem to be arguing that since the original 
'if''s code segment contained an explicit GOTO, that the end result is 
we should predict that it is unlikely to be taken, and therefore we 
should predict that the  'if (!something) goto around' branch *will* be 
taken after gimplifying, and that we lose that info.

Is that correct or were you trying to say something else?

Andrew

Re: Continue stmt branch prediction

[Jan Hubicka]

> Jan Hubicka wrote:
> >>Wouldn't it be easier to add a unlikely_goto stmt for all these and 
> >>translate
> >>that to edge probabilities once we build the cfg?  That is, stick the 
> >>unlikely
> >>bit onto the goto stmt instead of having an extra predict_expr floating 
> >>around.
> >>    
> >
> >We've disucussed this few mails back.  The problem is that if you have
> >something like
> >
> >if (something)
> >   something2
> >   goto somewhere else
> >
> >somewhere else:
> >   something_else
> >
> >then after gimplifing we get
> >
> >
> >if (something) goto around
> >something2
> >somewehre_else
> >around:
> >
> >and goto is gone.  It is really more a property of the some specific
> >  
> This example doesn't seem right. You've just changed the meaning of the 
> 'if' in your example... At least the way I read it. you are no longer 
> executing 'something2' if 'something' is true, nor executing 'something 
> else' on both paths as in the original case. There are too many 

Hehe, I really messed up gimplification.  I meant to do block merging of
something2 and somethign_else blocks to show that the goto stateemnts
are often easilly eliminated early in compilation and that the source
level control flow is not that directly related to what we want to have
in CFG.

> different things you could have meant for me to guess exactly what you 
> did mean :-)
> 
> I'll try tho :-)
> 
> Did you perhaps mean to reverse the condition to if (!something) in the 
> latter case?  If so, then you seem to be arguing that since the original 

Yes. 

> 'if''s code segment contained an explicit GOTO, that the end result is 
> we should predict that it is unlikely to be taken, and therefore we 
> should predict that the  'if (!something) goto around' branch *will* be 
> taken after gimplifying, and that we lose that info.
> 
> Is that correct or were you trying to say something else?

Yes, it is correct. Sorry for the confussion.

Honza
> 
> Andrew

Re: Continue stmt branch prediction

[Jan Hubicka]

Andrew and Diego,
can I ask if there was some outcome of the discussion of PREDICT_EXPR
patch? Looks like the thread just died out without any conclusion about
the patch itself...

Thanks,
Honza

Re: Continue stmt branch prediction

[Diego Novillo]

On Wed, Mar 5, 2008 at 13:33, Jan Hubicka <hubicka@ucw.cz> wrote:
> Andrew and Diego,
>  can I ask if there was some outcome of the discussion of PREDICT_EXPR
>  patch? Looks like the thread just died out without any conclusion about
>  the patch itself...

I'm really hesitant about adding another instruction that does not
seem to have any dataflow nor control flow properties, other than
affecting edges that come out of this block.  The semantics of the
instruction are very vague to me and I can't shake the idea that the
FE could put these attributes in the jumps or conditionals or switches
that it generates which we then convert into edge attributes.

I feel I'm being dense here and I'm totally missing your point.  Sorry.


Diego.

Re: Continue stmt branch prediction

[Jan Hubicka]

> On Wed, Mar 5, 2008 at 13:33, Jan Hubicka <hubicka@ucw.cz> wrote:
> > Andrew and Diego,
> >  can I ask if there was some outcome of the discussion of PREDICT_EXPR
> >  patch? Looks like the thread just died out without any conclusion about
> >  the patch itself...
> 
> I'm really hesitant about adding another instruction that does not
> seem to have any dataflow nor control flow properties, other than
> affecting edges that come out of this block.  The semantics of the

I will give it one last try.  I think the misunderstanding can be here.
The prediction hint is not affecting edges *out* of the block it sits
in. When lowered, it is affecting all the edges that are going from
basic block not postdominated by the block to basic block postdominated
by the block (here the course of execution is crossing the point that it
inavoidably leads to the place PREDICT_EXPR is).  Think of abort call:
it is affecting all conditionals that are guarding it in the program.

PREDICT_EXPR is sort of marker in the program saying that this place is
unlikely for reasons that are no longer obvious from lowered IL.  It is
not part of other control flow construct and it is not part of other
instruction in a sense that the high level construct it originated from
migh've expended to nothing (as continue statement does, it is
translated to GOTO_EXPR that is very soon removed by CFG construction
and translated to edge that is usually very soon removed by CFG
cleanup). It is just sort of no-op instruction.

Making the marker part of some other instruction (GOTO_EXPR) would
introduce need to forcingly keep that GOTO around until the lowering
happends (and it can't happen at CFG construction, since it works better
after some early cleanups and inlining).  Not undoable but it seems less
clean than PREDICT_EXPR to me. In fact it seems to me as bad as adding
any other side effect to GOTO_EXPR via flag.

Na
> instruction are very vague to me and I can't shake the idea that the
> FE could put these attributes in the jumps or conditionals or switches
> that it generates which we then convert into edge attributes.
> 
> I feel I'm being dense here and I'm totally missing your point.  Sorry.
> 
> 
> Diego.

Re: Continue stmt branch prediction

[Diego Novillo]

On 3/5/08 2:28 PM, Jan Hubicka wrote:

> I will give it one last try.  I think the misunderstanding can be here.
> The prediction hint is not affecting edges *out* of the block it sits
> in. When lowered, it is affecting all the edges that are going from
> basic block not postdominated by the block to basic block postdominated
> by the block (here the course of execution is crossing the point that it
> inavoidably leads to the place PREDICT_EXPR is).  Think of abort call:
> it is affecting all conditionals that are guarding it in the program.

Ah, I see now.  Yes, I think I finally got your point.  Adding 
PREDICT_EXPR is fine with me.

Instead of having to special-case it in places like DCE, how about we 
make it produce a value which is assigned to an artificial volatile 
global temporary?  This way, we don't need to touch the optimizers, they 
will all naturally back away from moving and/or removing it.


Diego.

Re: Continue stmt branch prediction

[Jan Hubicka]

> On 3/5/08 2:28 PM, Jan Hubicka wrote:
> 
> >I will give it one last try.  I think the misunderstanding can be here.
> >The prediction hint is not affecting edges *out* of the block it sits
> >in. When lowered, it is affecting all the edges that are going from
> >basic block not postdominated by the block to basic block postdominated
> >by the block (here the course of execution is crossing the point that it
> >inavoidably leads to the place PREDICT_EXPR is).  Think of abort call:
> >it is affecting all conditionals that are guarding it in the program.
> 
> Ah, I see now.  Yes, I think I finally got your point.  Adding 
> PREDICT_EXPR is fine with me.

Great :)
Thanks for time needed to get through this!
> 
> Instead of having to special-case it in places like DCE, how about we 
> make it produce a value which is assigned to an artificial volatile 
> global temporary?  This way, we don't need to touch the optimizers, they 
> will all naturally back away from moving and/or removing it.

This decision is definitly up to you.  I can definitly make PREDICT_EXPR
an expression tree instead of GIMPLE statement and put it into
MODIFY_EXPR destinating some dummy volatile.  This seems bit hackish way
to me to save one case label in DCE: DCE is a bit special among the
early passes in a way that it does worry about more side effects of
statements beside the usual operands+semantics of statements all the
other propagation passes are about.  DCE has to know all GIMPLE
statement types (and it just aborts on any new). I would tend to argue
that with exception of DCE we can hardly come with early scalar cleanup
pass that really do care here and will need to special case MODIFY_EXPR
statement.

Honza
> 
> 
> Diego.

Re: Continue stmt branch prediction

[Jan Hubicka]

> > On 3/5/08 2:28 PM, Jan Hubicka wrote:
> > 
> > >I will give it one last try.  I think the misunderstanding can be here.
> > >The prediction hint is not affecting edges *out* of the block it sits
> > >in. When lowered, it is affecting all the edges that are going from
> > >basic block not postdominated by the block to basic block postdominated
> > >by the block (here the course of execution is crossing the point that it
> > >inavoidably leads to the place PREDICT_EXPR is).  Think of abort call:
> > >it is affecting all conditionals that are guarding it in the program.
> > 
> > Ah, I see now.  Yes, I think I finally got your point.  Adding 
> > PREDICT_EXPR is fine with me.
> 
> Great :)
> Thanks for time needed to get through this!
> > 
> > Instead of having to special-case it in places like DCE, how about we 
> > make it produce a value which is assigned to an artificial volatile 
> > global temporary?  This way, we don't need to touch the optimizers, they 
> > will all naturally back away from moving and/or removing it.
> 
> This decision is definitly up to you.  I can definitly make PREDICT_EXPR
> an expression tree instead of GIMPLE statement and put it into
> MODIFY_EXPR destinating some dummy volatile.  This seems bit hackish way
> to me to save one case label in DCE: DCE is a bit special among the
> early passes in a way that it does worry about more side effects of
> statements beside the usual operands+semantics of statements all the
						    ^^^^ assignments (ie
						    passes tends to look
						    only into RHS of
						    modify statements)
> other propagation passes are about.  DCE has to know all GIMPLE
> statement types (and it just aborts on any new). I would tend to argue
> that with exception of DCE we can hardly come with early scalar cleanup
> pass that really do care here and will need to special case MODIFY_EXPR
> statement.
> 
> Honza
> > 
> > 
> > Diego.

Re: Continue stmt branch prediction

[Richard Guenther]

On Thu, Mar 13, 2008 at 2:37 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
> > On 3/5/08 2:28 PM, Jan Hubicka wrote:
>  >
>  > >I will give it one last try.  I think the misunderstanding can be here.
>  > >The prediction hint is not affecting edges *out* of the block it sits
>  > >in. When lowered, it is affecting all the edges that are going from
>  > >basic block not postdominated by the block to basic block postdominated
>  > >by the block (here the course of execution is crossing the point that it
>  > >inavoidably leads to the place PREDICT_EXPR is).  Think of abort call:
>  > >it is affecting all conditionals that are guarding it in the program.
>  >
>  > Ah, I see now.  Yes, I think I finally got your point.  Adding
>  > PREDICT_EXPR is fine with me.
>
>  Great :)
>  Thanks for time needed to get through this!
>
> >
>  > Instead of having to special-case it in places like DCE, how about we
>  > make it produce a value which is assigned to an artificial volatile
>  > global temporary?  This way, we don't need to touch the optimizers, they
>  > will all naturally back away from moving and/or removing it.
>
>  This decision is definitly up to you.  I can definitly make PREDICT_EXPR
>  an expression tree instead of GIMPLE statement and put it into
>  MODIFY_EXPR destinating some dummy volatile.  This seems bit hackish way
>  to me to save one case label in DCE: DCE is a bit special among the
>  early passes in a way that it does worry about more side effects of
>  statements beside the usual operands+semantics of statements all the
>  other propagation passes are about.  DCE has to know all GIMPLE
>  statement types (and it just aborts on any new). I would tend to argue
>  that with exception of DCE we can hardly come with early scalar cleanup
>  pass that really do care here and will need to special case MODIFY_EXPR
>  statement.

I also think this is a hack and adjusting DCE sounds more natural.  A
volatile global will also affect optimization because of the needed
VOPs.

Richard.

Re: Continue stmt branch prediction

[Diego Novillo]

On Wed, Mar 12, 2008 at 18:37, Jan Hubicka <hubicka@ucw.cz> wrote:

> This seems bit hackish way
>  to me to save one case label in DCE: DCE is a bit special among the
>  early passes in a way that it does worry about more side effects of
>  statements beside the usual operands+semantics of statements all the
>  other propagation passes are about.  DCE has to know all GIMPLE
>  statement types (and it just aborts on any new). I would tend to argue
>  that with exception of DCE we can hardly come with early scalar cleanup
>  pass that really do care here and will need to special case MODIFY_EXPR
>  statement.

Hm, good point.  Let's leave it as a special instruction then.


Diego.

Re: Continue stmt branch prediction

[H.J. Lu]

Hi,

This patch may have caused

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35636


H.J.
On Sat, Feb 9, 2008 at 12:48 PM, Jan Hubicka <jh@suse.cz> wrote:
>
>  Hi,
>  this patch adds a continue branch predictor that was dropped by introduction of
>  gimplifier (that replaced continue statement by goto).
>
>  The idea is that continue statements forms a loops that are usually not looping,
>  as proper loops are written via the loop construct.  On SPECint2000 average loop
>  tends to loop 7 times, while average loop constructed via continue loops less
>  than once.
>
>  The prediction is implemented via high level predictors that used also to predict,
>  for example, that explicit goto statements are not taken (this is helping kernel)
>  and can be used for other stuff in other languages too.
>  I will re-introduce the other predictors by followups later, this patch was
>  developed while looking into the gzip regression as predicting continue formed
>  loop to loop a lot is one of problems there:
>
>  statement
>   if (test1 || test2 || test3 || test4)
>     continue;
>
>  is in mainline handled as 4 nested loops, each predicted to loop roughly 4 times,
>  making all the rest of function cold.
>
>  Since the patch itself is not solving the regression fully (it makes improvement
>  on prelbmk 64bit peak, 920->980, and gzip 64bit, 750->770) but irronically it causes
>  regression at -O3 score of gzip 32bit by exposing other problems.  So I am holding
>  it for 4.4.
>
>  The branch prediction bits I can approve myself, but I would welcome comment on
>  introducing PREDICT_EXPR.  This was discussed while ago on GCC summit.  (the
>  original patch was done at CFG expansion times, but since we was about to run
>  out of tree codes I holded it and then forgot about the issue completely).
>
>  Bootstrapped/regtested i686-linux.
>
>  Honza
>
>         * tree-pretty-print.c: Include predict.h.
>         (dump_generic_node): Dump predictor.
>         * tree.h (PREDICT_EXPR_OUTCOME, PREDICT_EXPR_PREDICTION): Update.
>         * tree-gimple.c (is_gimple_stmt): Add PREDICT_EXPR.
>         * gimple-low.c (lower_stmt): Likewise.
>         * expr.c (expand_expr_real): Likewise.
>         * predict.c (tree_bb_level_predictions): Use PREDICT_EXPRs and remove
>         them.
>         (build_predict_expr, build_predict_expr): New.
>         * predict.h (predictor_name, build_predict_expr): Update.
>         * c-typeck.c (c_finish_bc_stmt): Add prediction.
>         * gimplify.c (gimplify_expr): Add PREDICT_EXPR.
>         * predict.def (PRED_CONTINUE): Update hitrate.
>         * tree.def (PREDICT_EXPR): Define.
>         * tree-ssa-dce.c (mark_stmt_if_obviously_necessary): Mark PREDICT_EXPR;
>         do not handle BIND_EXPR.
>         * tree-inline.c (estimate_num_insns_1): PREDICT_EXPR is free.
>         * tree-cfg.c (verify_gimple_stmt): PREDICT_EXPR is valid.
>         * tree-ssa-operands.c (get_expr_operands): PREDICT_EXPR takes no operands.
>
>

Re: Continue stmt branch prediction

[Jan Hubicka]

> Hi,
> 
> This patch may have caused
> 
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35636

Yes, the testcase needs adjusting (with PREDICT_EXPR sitting in, there
are no longer perfectly nested loops, but a butterfly CFG).  I will look
into it.

Honza

Re: Continue stmt branch prediction

[Richard Guenther]

On Wed, Mar 19, 2008 at 11:52 AM, Jan Hubicka <jh@suse.cz> wrote:
> > Hi,
>  >
>  > This patch may have caused
>  >
>  > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35636
>
>  Yes, the testcase needs adjusting (with PREDICT_EXPR sitting in, there
>  are no longer perfectly nested loops, but a butterfly CFG).  I will look
>  into it.

PREDICT_EXPRs should not cause such effect (I still think they are
ugly, but you made your point that BB or edge flags won't work).

Richard.

Re: Continue stmt branch prediction

[Jan Hubicka]

> On Wed, Mar 19, 2008 at 11:52 AM, Jan Hubicka <jh@suse.cz> wrote:
> > > Hi,
> >  >
> >  > This patch may have caused
> >  >
> >  > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35636
> >
> >  Yes, the testcase needs adjusting (with PREDICT_EXPR sitting in, there
> >  are no longer perfectly nested loops, but a butterfly CFG).  I will look
> >  into it.
> 
> PREDICT_EXPRs should not cause such effect (I still think they are
> ugly, but you made your point that BB or edge flags won't work).

If you have

  loopback:
    if (test1)
      goto loopback;
    if (test2)
      goto loopback;

You have two perfectly nested loops.  Now

  loopback:
    if (test1)
      {
        somecode;
        goto loopback;
      }
    somecode;
    if (test2)
      goto loopback;

You have two sibbling loops sharing header block.  The testcase is about
how loop infrastructure disambiguate the first case.  With predict_expr
in, we handle prediction more realistically (realizing that the test1 is
probably not closing loop construct since it comes from continue), but
disambiguation does not happen.

I will look into the other two cases tested by testcase but I think they
are same.  I think it is best to convert the inner loop into do-while
so it will still test the same.

Honza
> 
> Richard.

Re: Continue stmt branch prediction

[Richard Guenther]

On Wed, Mar 19, 2008 at 12:20 PM, Jan Hubicka <jh@suse.cz> wrote:
>
> > On Wed, Mar 19, 2008 at 11:52 AM, Jan Hubicka <jh@suse.cz> wrote:
>  > > > Hi,
>  > >  >
>  > >  > This patch may have caused
>  > >  >
>  > >  > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35636
>  > >
>  > >  Yes, the testcase needs adjusting (with PREDICT_EXPR sitting in, there
>  > >  are no longer perfectly nested loops, but a butterfly CFG).  I will look
>  > >  into it.
>  >
>  > PREDICT_EXPRs should not cause such effect (I still think they are
>  > ugly, but you made your point that BB or edge flags won't work).
>
>  If you have
>
>   loopback:
>     if (test1)
>       goto loopback;
>     if (test2)
>       goto loopback;
>
>  You have two perfectly nested loops.  Now
>
>   loopback:
>     if (test1)
>       {
>         somecode;
>         goto loopback;
>       }
>     somecode;
>     if (test2)
>       goto loopback;
>
>  You have two sibbling loops sharing header block.  The testcase is about
>  how loop infrastructure disambiguate the first case.  With predict_expr
>  in, we handle prediction more realistically (realizing that the test1 is
>  probably not closing loop construct since it comes from continue), but
>  disambiguation does not happen.
>
>  I will look into the other two cases tested by testcase but I think they
>  are same.  I think it is best to convert the inner loop into do-while
>  so it will still test the same.

Can you also split the testcase so the counters do not get (falsely) added?

Thanks,
Richard.

Re: Continue stmt branch prediction

[Bradley Lucier]

Re:

>> What are the other predictors?  It might help to understand it  
>> better if we had a better overview of everything PREDICT_EXPR was  
>> going to do.
>
>
> I was mostly looking into following stuff:
>   1) the continue bit
>   2) explicit goto statements are usually not executed
>   3) default path of C switch statement on emum with all named fields
>   explicit is unlikely
>   4) expanded bounds checks (ie arrays tends to be in bounds. We  
> used to
>   have PRED_MUDLFAP here but it was dropped and Java has similar  
> logic)
>   5) expanded openMP constructs
>   6) higher level constructs from non-C frontends we have.  There are
>   cases where we produce control flow expanding stuff like fortran
>   vectors where we have unlikely paths through. Though I didn't look
>   into great detail into this yet.


Honza:

Computer-generated C code as the back end of compilers for other  
languages may implement function calls as gotos (the callee, not the  
caller, controls the argument stack in Scheme, for example, so The  
Gambit Scheme->C compiler generate C code where function calls are  
just goto's with arguments).  It appears that heuristics such as 2  
may make such code perform worse (especially as incorrectly-predicted  
jumps have such a high cost on some processors).

Are there predictors already implemented in gcc based on other  
things, such as control flow graphs?

If gcc does adopt heuristics such as these, I hope they can be  
documented so that people automatically generating C code can either  
exploit them or avoid them as necessary.  (An example is that the  
Gambit Scheme compiler has been generating SSA-style floating-point  
code for years because the original code generator produced code that  
gcc's register allocator didn't handle very well.)

Brad