diff options
| -rw-r--r-- | gcc/ChangeLog | 19 | ||||
| -rw-r--r-- | gcc/basic-block.h | 1 | ||||
| -rw-r--r-- | gcc/builtins.c | 45 | ||||
| -rw-r--r-- | gcc/builtins.def | 1 | ||||
| -rw-r--r-- | gcc/c-common.c | 10 | ||||
| -rw-r--r-- | gcc/extend.texi | 35 | ||||
| -rw-r--r-- | gcc/predict.c | 87 | ||||
| -rw-r--r-- | gcc/print-rtl.c | 76 | ||||
| -rw-r--r-- | gcc/rtl.c | 2 | ||||
| -rw-r--r-- | gcc/rtl.h | 5 | ||||
| -rw-r--r-- | gcc/toplev.c | 7 |
11 files changed, 256 insertions, 32 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index f400c95..6366fbc 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,22 @@ +2000-04-17 Richard Henderson <rth@cygnus.com> + + * builtins.c (expand_builtin_expect): New. + (expand_builtin): Call it. + * builtins.def (BUILT_IN_EXPECT): New. + * c-common.c (c_common_nodes_and_builtins): Declare __builtin_expect. + * extend.texi: Document it. + + * predict.c (expected_value_to_br_prob): New. + (find_expected_value): New. + * basic-block.h (expected_value_to_br_prob): Declare. + * toplev.c (rest_of_compilation): Invoke it. + + * rtl.h (NOTE_EXPECTED_VALUE): New. + (NOTE_INSN_EXPECTED_VALUE): New. + * rtl.c (note_insn_name): Update. + * print-rtl.c (print_rtx): Reorg NOTE_LINE_NUMBER special + cases; handle NOTE_INSN_EXPECTED_VALUE. + 2000-04-17 Jakub Jelinek <jakub@redhat.com> * config/sparc/sparc.c (eligible_for_sibcall_delay): Cannot use diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 62a4b5b..bd1d2d4 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -449,6 +449,7 @@ extern rtx emit_block_insn_before PARAMS ((rtx, rtx, basic_block)); /* In predict.c */ extern void estimate_probability PARAMS ((struct loops *)); +extern void expected_value_to_br_prob PARAMS ((void)); /* In flow.c */ extern void reorder_basic_blocks PARAMS ((void)); diff --git a/gcc/builtins.c b/gcc/builtins.c index 9159a1b..7c833e5 100644 --- a/gcc/builtins.c +++ b/gcc/builtins.c @@ -103,6 +103,7 @@ static rtx expand_builtin_alloca PARAMS ((tree, rtx)); static rtx expand_builtin_ffs PARAMS ((tree, rtx, rtx)); static rtx expand_builtin_frame_address PARAMS ((tree)); static tree stabilize_va_list PARAMS ((tree, int)); +static rtx expand_builtin_expect PARAMS ((tree, rtx)); /* Return the alignment in bits of EXP, a pointer valued expression. But don't return more than MAX_ALIGN no matter what. @@ -2306,6 +2307,48 @@ expand_builtin_ffs (arglist, target, subtarget) abort (); return target; } + +/* Expand a call to __builtin_expect. We return our argument and + emit a NOTE_INSN_EXPECTED_VALUE note. */ + +static rtx +expand_builtin_expect (arglist, target) + tree arglist; + rtx target; +{ + tree exp, c; + rtx note, rtx_c; + + if (arglist == NULL_TREE + || TREE_CHAIN (arglist) == NULL_TREE) + return const0_rtx; + exp = TREE_VALUE (arglist); + c = TREE_VALUE (TREE_CHAIN (arglist)); + + if (TREE_CODE (c) != INTEGER_CST) + { + error ("second arg to `__builtin_expect' must be a constant"); + c = integer_zero_node; + } + + target = expand_expr (exp, target, VOIDmode, EXPAND_NORMAL); + + /* Don't bother with expected value notes for integral constants. */ + if (GET_CODE (target) != CONST_INT) + { + /* We do need to force this into a register so that we can be + moderately sure to be able to correctly interpret the branch + condition later. */ + target = force_reg (GET_MODE (target), target); + + rtx_c = expand_expr (c, NULL_RTX, GET_MODE (target), EXPAND_NORMAL); + + note = emit_note (NULL, NOTE_INSN_EXPECTED_VALUE); + NOTE_EXPECTED_VALUE (note) = gen_rtx_EQ (VOIDmode, target, rtx_c); + } + + return target; +} /* Expand an expression EXP that calls a built-in function, with result going to TARGET if that's convenient @@ -2581,6 +2624,8 @@ expand_builtin (exp, target, subtarget, mode, ignore) return expand_builtin_va_end (arglist); case BUILT_IN_VA_COPY: return expand_builtin_va_copy (arglist); + case BUILT_IN_EXPECT: + return expand_builtin_expect (arglist, target); default: /* just do library call, if unknown builtin */ error ("built-in function `%s' not currently supported", diff --git a/gcc/builtins.def b/gcc/builtins.def index 506bc41..308257f 100644 --- a/gcc/builtins.def +++ b/gcc/builtins.def @@ -79,6 +79,7 @@ DEF_BUILTIN(BUILT_IN_VARARGS_START) DEF_BUILTIN(BUILT_IN_STDARG_START) DEF_BUILTIN(BUILT_IN_VA_END) DEF_BUILTIN(BUILT_IN_VA_COPY) +DEF_BUILTIN(BUILT_IN_EXPECT) /* C++ extensions */ DEF_BUILTIN(BUILT_IN_NEW) diff --git a/gcc/c-common.c b/gcc/c-common.c index 1033035..386721a 100644 --- a/gcc/c-common.c +++ b/gcc/c-common.c @@ -3767,6 +3767,16 @@ c_common_nodes_and_builtins (cplus_mode, no_builtins, no_nonansi_builtins) endlink))), BUILT_IN_VA_COPY, BUILT_IN_NORMAL, NULL_PTR); + /* ??? Ought to be `T __builtin_expect(T, T)' for any type T. */ + builtin_function ("__builtin_expect", + build_function_type (long_integer_type_node, + tree_cons (NULL_TREE, + long_integer_type_node, + tree_cons (NULL_TREE, + long_integer_type_node, + endlink))), + BUILT_IN_EXPECT, BUILT_IN_NORMAL, NULL_PTR); + /* Currently under experimentation. */ builtin_function ("__builtin_memcpy", memcpy_ftype, BUILT_IN_MEMCPY, BUILT_IN_NORMAL, "memcpy"); diff --git a/gcc/extend.texi b/gcc/extend.texi index 22fe741..36c451b 100644 --- a/gcc/extend.texi +++ b/gcc/extend.texi @@ -3199,7 +3199,9 @@ correspond to the C library functions @code{abort}, @code{abs}, @code{sinf}, @code{sinl}, @code{sqrt}, @code{sqrtf}, @code{sqrtl}, @code{strcmp}, @code{strcpy}, and @code{strlen}. +@table @code @findex __builtin_constant_p +@item __builtin_constant_p (@var{exp}) You can use the builtin function @code{__builtin_constant_p} to determine if a value is known to be constant at compile-time and hence that GNU CC can perform constant-folding on expressions involving that @@ -3228,6 +3230,39 @@ or constructor expression (@pxref{Constructors}) and will not return 1 when you pass a constant numeric value to the inline function unless you specify the @samp{-O} option. +@findex __builtin_expect +@item __builtin_expect(@var{exp}, @var{c}) +You may use @code{__builtin_expect} to provide the compiler with +branch prediction information. In general, you should prefer to +use actual profile feedback for this (@samp{-fprofile-arcs}), as +programmers are notoriously bad at predicting how their programs +actually preform. However, there are applications in which this +data is hard to collect. + +The return value is the value of @var{exp}, which should be an +integral expression. The value of @var{c} must be a compile-time +constant. The semantics of the builtin are that it is expected +that @var{exp} == @var{c}. For example: + +@smallexample +if (__builtin_expect (x, 0)) + foo (); +@end smallexample + +@noindent +would indicate that we do not expect to call @code{foo}, since +we expect @code{x} to be zero. Since you are limited to integral +expressions for @var{exp}, you should use constructions such as + +@smallexample +if (__builtin_expect (ptr != NULL, 1)) + error (); +@end smallexample + +@noindent +when testing pointer or floating-point values. +@end table + @node Deprecated Features @section Deprecated Features diff --git a/gcc/predict.c b/gcc/predict.c index 2cae39a..767afdc 100644 --- a/gcc/predict.c +++ b/gcc/predict.c @@ -180,4 +180,91 @@ estimate_probability (loops_info) REG_NOTES (last_insn)); } } + +/* __builtin_expect dropped tokens into the insn stream describing + expected values of registers. Generate branch probabilities + based off these values. */ +static rtx find_expected_value PARAMS ((rtx, rtx)); + +void +expected_value_to_br_prob () +{ + rtx insn, cond, earliest, ev; + + for (insn = get_insns (); insn ; insn = NEXT_INSN (insn)) + { + /* Look for simple conditional branches. */ + if (GET_CODE (insn) != JUMP_INSN) + continue; + if (! condjump_p (insn) || simplejump_p (insn)) + continue; + + /* Collect the branch condition. Some machines can branch on + user values directly, others need a compare instruction. If + the branch condition involves a MODE_INT register, try that + expression first. Otherwise use get_condition. */ + cond = XEXP (SET_SRC (PATTERN (insn)), 0); + if (GET_RTX_CLASS (GET_CODE (cond)) != '<') + abort (); + if (GET_CODE (XEXP (cond, 0)) == REG + && GET_MODE_CLASS (GET_MODE (XEXP (cond, 0))) == MODE_INT + && (ev = find_expected_value (cond, insn)) != NULL_RTX) + ; + else if ((cond = get_condition (insn, &earliest)) == NULL_RTX + || (ev = find_expected_value (cond, earliest)) == NULL_RTX) + continue; + + /* Substitute and simplify. Given that the expression we're + building involves two constants, we should wind up with either + true or false. */ + cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode, + XEXP (ev, 1), XEXP (cond, 1)); + cond = simplify_rtx (cond); + + /* Turn the condition into a scaled branch probability. */ + if (cond == const0_rtx) + cond = const1_rtx; + else if (cond == const1_rtx) + cond = GEN_INT (REG_BR_PROB_BASE - 1); + else + abort (); + REG_NOTES (insn) = alloc_EXPR_LIST (REG_BR_PROB, cond, REG_NOTES (insn)); + } +} + +/* Search backwards for a NOTE_INSN_EXPECTED_VALUE note with a register + that matches the condition. */ + +static rtx +find_expected_value (cond, earliest) + rtx cond, earliest; +{ + rtx insn, reg = XEXP (cond, 0); + int timeout; + + /* The condition should be (op (reg) (const_int)), otherwise we + won't be able to intuit anything about it. */ + if (GET_CODE (reg) != REG + || GET_CODE (XEXP (cond, 1)) != CONST_INT + || GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT) + return NULL_RTX; + + /* Assuming the user wrote something like `if (__builtin_expect(...))', + we shouldn't have to search too far. Also stop if we reach a code + label or if REG is modified. */ + for (insn = earliest, timeout = 10; + insn && timeout > 0; + insn = PREV_INSN (insn), --timeout) + { + if (GET_CODE (insn) == NOTE + && NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE + && XEXP (NOTE_EXPECTED_VALUE (insn), 0) == reg) + return NOTE_EXPECTED_VALUE (insn); + + if (GET_CODE (insn) == CODE_LABEL || reg_set_p (reg, insn)) + break; + } + + return NULL_RTX; +} diff --git a/gcc/print-rtl.c b/gcc/print-rtl.c index ee7e64c..8b7bebe 100644 --- a/gcc/print-rtl.c +++ b/gcc/print-rtl.c @@ -162,18 +162,19 @@ print_rtx (in_rtx) case '0': if (i == 3 && GET_CODE (in_rtx) == NOTE) { - if (NOTE_LINE_NUMBER (in_rtx) == NOTE_INSN_EH_REGION_BEG - || NOTE_LINE_NUMBER (in_rtx) == NOTE_INSN_EH_REGION_END) + switch (NOTE_LINE_NUMBER (in_rtx)) { + case NOTE_INSN_EH_REGION_BEG: + case NOTE_INSN_EH_REGION_END: if (flag_dump_unnumbered) fprintf (outfile, " #"); else fprintf (outfile, " %d", NOTE_EH_HANDLER (in_rtx)); sawclose = 1; - } - else if (NOTE_LINE_NUMBER (in_rtx) == NOTE_INSN_BLOCK_BEG - || NOTE_LINE_NUMBER (in_rtx) == NOTE_INSN_BLOCK_END) - { + break; + + case NOTE_INSN_BLOCK_BEG: + case NOTE_INSN_BLOCK_END: fprintf (outfile, " "); if (flag_dump_unnumbered) fprintf (outfile, "#"); @@ -181,36 +182,51 @@ print_rtx (in_rtx) fprintf (outfile, HOST_PTR_PRINTF, (char *) NOTE_BLOCK (in_rtx)); sawclose = 1; - } - else if (NOTE_LINE_NUMBER (in_rtx) == NOTE_INSN_RANGE_START - || NOTE_LINE_NUMBER (in_rtx) == NOTE_INSN_RANGE_END - || NOTE_LINE_NUMBER (in_rtx) == NOTE_INSN_LIVE) - { + break; + + case NOTE_INSN_RANGE_START: + case NOTE_INSN_RANGE_END: + case NOTE_INSN_LIVE: indent += 2; if (!sawclose) fprintf (outfile, " "); print_rtx (NOTE_RANGE_INFO (in_rtx)); indent -= 2; - } - else if (NOTE_LINE_NUMBER (in_rtx) == NOTE_INSN_BASIC_BLOCK) - { - basic_block bb = NOTE_BASIC_BLOCK (in_rtx); + break; - if (bb != 0) - fprintf (outfile, " [bb %d]", bb->index); - } - else - { - const char * const str = X0STR (in_rtx, i); - if (str == 0) - fputs (dump_for_graph ? " \\\"\\\"" : " \"\"", outfile); - else - { - if (dump_for_graph) - fprintf (outfile, " (\\\"%s\\\")", str); - else - fprintf (outfile, " (\"%s\")", str); - } + case NOTE_INSN_BASIC_BLOCK: + { + basic_block bb = NOTE_BASIC_BLOCK (in_rtx); + if (bb != 0) + fprintf (outfile, " [bb %d]", bb->index); + break; + } + + case NOTE_INSN_EXPECTED_VALUE: + indent += 2; + if (!sawclose) + fprintf (outfile, " "); + print_rtx (NOTE_EXPECTED_VALUE (in_rtx)); + indent -= 2; + break; + + default: + { + const char * const str = X0STR (in_rtx, i); + + if (NOTE_LINE_NUMBER (in_rtx) < 0) + ; + else if (str == 0) + fputs (dump_for_graph ? " \\\"\\\"" : " \"\"", outfile); + else + { + if (dump_for_graph) + fprintf (outfile, " (\\\"%s\\\")", str); + else + fprintf (outfile, " (\"%s\")", str); + } + break; + } } } break; @@ -247,7 +247,7 @@ const char * const note_insn_name[NOTE_INSN_MAX - NOTE_INSN_BIAS] = "NOTE_INSN_EH_REGION_BEG", "NOTE_INSN_EH_REGION_END", "NOTE_REPEATED_LINE_NUMBER", "NOTE_INSN_RANGE_START", "NOTE_INSN_RANGE_END", "NOTE_INSN_LIVE", - "NOTE_INSN_BASIC_BLOCK" + "NOTE_INSN_BASIC_BLOCK", "NOTE_INSN_EXPECTED_VALUE" }; const char * const reg_note_name[] = @@ -577,6 +577,7 @@ extern const char * const reg_note_name[]; #define NOTE_RANGE_INFO(INSN) XCEXP(INSN, 3, NOTE) #define NOTE_LIVE_INFO(INSN) XCEXP(INSN, 3, NOTE) #define NOTE_BASIC_BLOCK(INSN) XCBBDEF(INSN, 3, NOTE) +#define NOTE_EXPECTED_VALUE(INSN) XCEXP(INSN, 3, NOTE) /* In a NOTE that is a line number, this is the line number. Other kinds of NOTEs are identified by negative numbers here. */ @@ -664,6 +665,10 @@ enum insn_note /* Record the struct for the following basic block. Uses NOTE_BASIC_BLOCK. */ NOTE_INSN_BASIC_BLOCK, + /* Record the expected value of a register at a location. Uses + NOTE_EXPECTED_VALUE; stored as (eq (reg) (const_int)). */ + NOTE_INSN_EXPECTED_VALUE, + NOTE_INSN_MAX }; diff --git a/gcc/toplev.c b/gcc/toplev.c index 6d8336d..4f9a385 100644 --- a/gcc/toplev.c +++ b/gcc/toplev.c @@ -2893,9 +2893,10 @@ rest_of_compilation (decl) goto exit_rest_of_compilation; } + init_EXPR_INSN_LIST_cache (); + /* We may have potential sibling or tail recursion sites. Select one (of possibly multiple) methods of performing the call. */ - init_EXPR_INSN_LIST_cache (); if (flag_optimize_sibling_calls) optimize_sibling_and_tail_recursive_calls (); @@ -2962,6 +2963,10 @@ rest_of_compilation (decl) of the function. */ TIMEVAR (jump_time, { + /* Turn NOTE_INSN_EXPECTED_VALUE into REG_BR_PROB. Do this + before jump optimization switches branch directions. */ + expected_value_to_br_prob (); + reg_scan (insns, max_reg_num (), 0); jump_optimize (insns, !JUMP_CROSS_JUMP, !JUMP_NOOP_MOVES, JUMP_AFTER_REGSCAN); |