Per offline discussion,
* do not export function start line number. Instead, hash branch
offset and discriminator into the "function_hash" (renamed to just
"hash" to clarify)
* protect all operations about the new EDGE_PREDICTED_BY_EXPECT flag
with flag_check_branch_annotation.
On Mon, Jun 30, 2014 at 5:42 PM, Yi Yang <ahyan...@google.com> wrote:
> Fixed a style error (missing a space before a left parenthesis)
>
>
> On Mon, Jun 30, 2014 at 5:41 PM, Yi Yang <ahyan...@google.com> wrote:
>> Done.
>>
>> On Mon, Jun 30, 2014 at 5:20 PM, Dehao Chen <de...@google.com> wrote:
>>> For get_locus_information, can you cal get_inline_stack and directly use its
>>> output to get the function name instead?
>>>
>>> Dehao
>>>
>>>
>>> On Mon, Jun 30, 2014 at 4:47 PM, Yi Yang <ahyan...@google.com> wrote:
>>>>
>>>> Removed fill_invalid_locus_information. Change the function call to a
>>>> return statement.
>>>>
>>>> On Mon, Jun 30, 2014 at 4:42 PM, Dehao Chen <de...@google.com> wrote:
>>>> > There is no need for fill_invalid_locus_information, just initialize
>>>> > every field to 0, and if it's unknown location, no need to output this
>>>> > line.
>>>> >
>>>> > Dehao
>>>> >
>>>> > On Mon, Jun 30, 2014 at 4:26 PM, Yi Yang <ahyan...@google.com> wrote:
>>>> >> Instead of storing percentages of the branch probabilities, store them
>>>> >> times REG_BR_PROB_BASE.
>>>> >>
>>>> >> On Mon, Jun 30, 2014 at 3:26 PM, Yi Yang <ahyan...@google.com> wrote:
>>>> >>> Fixed. (outputting only the integer percentage)
>>>> >>>
>>>> >>> On Mon, Jun 30, 2014 at 2:20 PM, Yi Yang <ahyan...@google.com> wrote:
>>>> >>>> This is intermediate result, which is meant to be consumed by further
>>>> >>>> post-processing. For this reason I'd prefer to put a number without
>>>> >>>> that percentage sign.
>>>> >>>>
>>>> >>>> I'd just output (int)(probability*100000000+0.5). Does this look good
>>>> >>>> for you? Or maybe change that to 1000000 since six digits are more
>>>> >>>> than enough. I don't see a reason to intentionally drop precision
>>>> >>>> though.
>>>> >>>>
>>>> >>>> Note that for the actual probability, the best way to store it is to
>>>> >>>> store the edge count, since the probability is just
>>>> >>>> edge_count/bb_count. But this causes disparity in the formats of the
>>>> >>>> two probabilities.
>>>> >>>>
>>>> >>>> On Mon, Jun 30, 2014 at 2:12 PM, Dehao Chen <de...@google.com> wrote:
>>>> >>>>> Let's use %d to replace %f (manual conversion, let's do xx%).
>>>> >>>>>
>>>> >>>>> Dehao
>>>> >>>>>
>>>> >>>>> On Mon, Jun 30, 2014 at 2:06 PM, Yi Yang <ahyan...@google.com>
>>>> >>>>> wrote:
>>>> >>>>>> Fixed.
>>>> >>>>>>
>>>> >>>>>> Also, I spotted some warnings caused by me using "%lf"s in
>>>> >>>>>> snprintf().
>>>> >>>>>> I changed these to "%f" and tested.
>>>> >>>>>>
>>>> >>>>>>
>>>> >>>>>> On Mon, Jun 30, 2014 at 1:49 PM, Dehao Chen <de...@google.com>
>>>> >>>>>> wrote:
>>>> >>>>>>> You don't need extra space to store file name in
>>>> >>>>>>> locus_information_t.
>>>> >>>>>>> Use pointer instead.
>>>> >>>>>>>
>>>> >>>>>>> Dehao
>>>> >>>>>>>
>>>> >>>>>>>
>>>> >>>>>>> On Mon, Jun 30, 2014 at 1:36 PM, Yi Yang <ahyan...@google.com>
>>>> >>>>>>> wrote:
>>>> >>>>>>>>
>>>> >>>>>>>> I refactored the code and added comments. A bug (prematurely
>>>> >>>>>>>> breaking
>>>> >>>>>>>> from a loop) was fixed during the refactoring.
>>>> >>>>>>>>
>>>> >>>>>>>> (My last mail was wrongly set to HTML instead of plain text. I
>>>> >>>>>>>> apologize for that.)
>>>> >>>>>>>>
>>>> >>>>>>>> 2014-06-30 Yi Yang <ahyan...@google.com>
>>>> >>>>>>>>
>>>> >>>>>>>> * auto-profile.c (get_locus_information)
>>>> >>>>>>>> (fill_invalid_locus_information,
>>>> >>>>>>>> record_branch_prediction_results)
>>>> >>>>>>>> (afdo_calculate_branch_prob, afdo_annotate_cfg): Main
>>>> >>>>>>>> comparison and
>>>> >>>>>>>> reporting logic.
>>>> >>>>>>>> * cfg-flags.def (PREDICTED_BY_EXPECT): Add an extra flag
>>>> >>>>>>>> representing
>>>> >>>>>>>> an edge's probability is predicted by annotations.
>>>> >>>>>>>> * predict.c (combine_predictions_for_bb): Set up the extra
>>>> >>>>>>>> flag on an
>>>> >>>>>>>> edge when appropriate.
>>>> >>>>>>>> * common.opt (fcheck-branch-annotation)
>>>> >>>>>>>> (fcheck-branch-annotation-threshold=): Add an extra GCC
>>>> >>>>>>>> option to turn
>>>> >>>>>>>> on report
>>>> >>>>>>>>
>>>> >>>>>>>> On Fri, Jun 27, 2014 at 3:20 PM, Xinliang David Li
>>>> >>>>>>>> <davi...@google.com> wrote:
>>>> >>>>>>>> > Hi Yi,
>>>> >>>>>>>> >
>>>> >>>>>>>> > 1) please add comments before new functions as documentation --
>>>> >>>>>>>> > follow
>>>> >>>>>>>> > the coding style guideline
>>>> >>>>>>>> > 2) missing documenation on the new flags (pointed out by
>>>> >>>>>>>> > Gerald)
>>>> >>>>>>>> > 3) Please refactor the check code in afdo_calculate_branch_prob
>>>> >>>>>>>> > into a
>>>> >>>>>>>> > helper function
>>>> >>>>>>>> >
>>>> >>>>>>>> > 4) the change log is not needed for google branches, but if
>>>> >>>>>>>> > provided,
>>>> >>>>>>>> > the format should follow the style guide (e.g, function name in
>>>> >>>>>>>> > () ).
>>>> >>>>>>>> >
>>>> >>>>>>>> > David
>>>> >>>>>>>> >
>>>> >>>>>>>> >
>>>> >>>>>>>> > On Fri, Jun 27, 2014 at 11:07 AM, Yi Yang <ahyan...@google.com>
>>>> >>>>>>>> > wrote:
>>>> >>>>>>>> >> Hi,
>>>> >>>>>>>> >>
>>>> >>>>>>>> >> This patch adds an option. When the option is enabled, GCC
>>>> >>>>>>>> >> will add a
>>>> >>>>>>>> >> record about it in an elf section called
>>>> >>>>>>>> >> ".gnu.switches.text.branch.annotation" for every branch.
>>>> >>>>>>>> >>
>>>> >>>>>>>> >> gcc/
>>>> >>>>>>>> >>
>>>> >>>>>>>> >> 2014-06-27 Yi Yang <ahyan...@google.com>
>>>> >>>>>>>> >>
>>>> >>>>>>>> >> * auto-profile.c: Main comparison and reporting logic.
>>>> >>>>>>>> >> * cfg-flags.def: Add an extra flag representing an
>>>> >>>>>>>> >> edge's
>>>> >>>>>>>> >> probability is predicted by annotations.
>>>> >>>>>>>> >> * predict.c: Set up the extra flag on an edge when
>>>> >>>>>>>> >> appropriate.
>>>> >>>>>>>> >> * common.opt: Add an extra GCC option to turn on this
>>>> >>>>>>>> >> report mechanism
>>>
>>>
diff --git gcc/auto-profile.c gcc/auto-profile.c
index 74d3d1d..b36c506 100644
--- gcc/auto-profile.c
+++ gcc/auto-profile.c
@@ -40,6 +40,7 @@ along with GCC; see the file COPYING3. If not see
#include "opts.h" /* for in_fnames. */
#include "tree-pass.h" /* for ipa pass. */
#include "cfgloop.h" /* for loop_optimizer_init. */
+#include "md5.h" /* for hashing function names. */
#include "gimple.h"
#include "cgraph.h"
#include "tree-flow.h"
@@ -1367,6 +1368,125 @@ afdo_propagate (void)
}
}
+/* All information parsed from a location_t that will be stored into the ELF
+ section. */
+
+struct locus_information_t {
+ /* File name of the source file containing the branch. */
+ const char *filename;
+ /* Line number of the branch location. */
+ unsigned lineno;
+ /* Hash value calculated from function name, function length, branch site
+ offset and discriminator, used to uniquely identify a branch across
+ different source versions. */
+ char hash[33];
+};
+
+/* Return true iff file and lineno are available for the provided locus.
+ Fill all fields of li with information about locus. */
+
+static bool
+get_locus_information (location_t locus, locus_information_t* li) {
+ if (locus == UNKNOWN_LOCATION || !LOCATION_FILE (locus))
+ return false;
+ li->filename = LOCATION_FILE (locus);
+ li->lineno = LOCATION_LINE (locus);
+
+ tree block = LOCATION_BLOCK (locus);
+ inline_stack stack;
+
+ get_inline_stack (locus, &stack);
+ if (stack.empty ())
+ return false;
+
+ tree function_decl = stack[0].first;
+
+ if (!(function_decl && TREE_CODE (function_decl) == FUNCTION_DECL))
+ return false;
+
+ /* Get function_length, branch_offset and discriminator to identify branches
+ across different source versions. */
+ unsigned function_lineno =
+ LOCATION_LINE (DECL_SOURCE_LOCATION (function_decl));
+ function *f = DECL_STRUCT_FUNCTION (function_decl);
+ unsigned function_length = f? LOCATION_LINE (f->function_end_locus) -
+ function_lineno : 0;
+ unsigned branch_offset = li->lineno - function_lineno;
+ int discriminator = get_discriminator_from_locus (locus);
+
+ const char *fn_name = fndecl_name (function_decl);
+ unsigned char md5_result[16];
+
+ md5_ctx ctx;
+
+ md5_init_ctx (&ctx);
+ md5_process_bytes (fn_name, strlen (fn_name), &ctx);
+ md5_process_bytes (&function_length, sizeof (function_length), &ctx);
+ md5_process_bytes (&branch_offset, sizeof (branch_offset), &ctx);
+ md5_process_bytes (&discriminator, sizeof (discriminator), &ctx);
+ md5_finish_ctx (&ctx, md5_result);
+
+ /* Convert MD5 to hexadecimal representation. */
+ for (int i = 0; i < 16; ++i)
+ {
+ sprintf (li->hash + i*2, "%02x", md5_result[i]);
+ }
+
+ return true;
+}
+
+/* Record branch prediction comparison for the given edge and actual
+ probability. */
+static void
+record_branch_prediction_results (edge e, int probability) {
+ basic_block bb = e->src;
+
+ if (bb->succs->length () == 2 &&
+ maybe_hot_count_p (cfun, bb->count) &&
+ bb->count >= check_branch_annotation_threshold)
+ {
+ gimple_stmt_iterator gsi;
+ gimple last = NULL;
+
+ for (gsi = gsi_last_nondebug_bb (bb);
+ !gsi_end_p (gsi);
+ gsi_prev_nondebug (&gsi))
+ {
+ last = gsi_stmt (gsi);
+
+ if (gimple_has_location (last))
+ break;
+ }
+
+ struct locus_information_t li;
+ bool annotated;
+
+ if (e->flags & EDGE_PREDICTED_BY_EXPECT)
+ annotated = true;
+ else
+ annotated = false;
+
+ if (get_locus_information (e->goto_locus, &li))
+ ; /* Intentionally do nothing. */
+ else if (get_locus_information (gimple_location (last), &li))
+ ; /* Intentionally do nothing. */
+ else
+ return; /* Can't get locus information, return. */
+
+ switch_to_section (get_section (
+ ".gnu.switches.text.branch.annotation",
+ SECTION_DEBUG | SECTION_MERGE |
+ SECTION_STRINGS | (SECTION_ENTSIZE & 1),
+ NULL));
+ char buf[1024];
+ snprintf (buf, 1024, "%s;%u;"
+ HOST_WIDEST_INT_PRINT_DEC";%d;%d;%d;%s",
+ li.filename, li.lineno, bb->count, annotated?1:0,
+ probability, e->probability, li.hash);
+ dw2_asm_output_nstring (buf, (size_t)-1, NULL);
+ }
+}
+
/* Propagate counts on control flow graph and calculate branch
probabilities. */
@@ -1406,9 +1526,22 @@ afdo_calculate_branch_prob (void)
}
if (num_unknown_succ == 0 && total_count > 0)
{
+ bool first_edge = true;
+
FOR_EACH_EDGE (e, ei, bb->succs)
- e->probability =
- (double) e->count * REG_BR_PROB_BASE / total_count;
+ {
+ double probability =
+ (double) e->count * REG_BR_PROB_BASE / total_count;
+
+ if (first_edge && flag_check_branch_annotation)
+ {
+ record_branch_prediction_results (
+ e, static_cast<int> (probability + 0.5));
+ first_edge = false;
+ }
+
+ e->probability = probability;
+ }
}
}
FOR_ALL_BB (bb)
@@ -1417,8 +1550,14 @@ afdo_calculate_branch_prob (void)
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
- e->count =
- (double) bb->count * e->probability / REG_BR_PROB_BASE;
+ {
+ e->count =
+ (double) bb->count * e->probability / REG_BR_PROB_BASE;
+ if (flag_check_branch_annotation)
+ {
+ e->flags &= ~EDGE_PREDICTED_BY_EXPECT;
+ }
+ }
bb->aux = NULL;
}
@@ -1542,9 +1681,9 @@ afdo_annotate_cfg (const stmt_set &promoted_stmts)
afdo_source_profile->mark_annotated (cfun->function_end_locus);
if (max_count > 0)
{
+ profile_status = PROFILE_READ;
afdo_calculate_branch_prob ();
counts_to_freqs ();
- profile_status = PROFILE_READ;
}
if (flag_value_profile_transformations)
gimple_value_profile_transformations ();
diff --git gcc/cfg-flags.def gcc/cfg-flags.def
index 42a0473..12a17f2 100644
--- gcc/cfg-flags.def
+++ gcc/cfg-flags.def
@@ -186,6 +186,9 @@ DEF_EDGE_FLAG(TM_ABORT, 16)
/* Annotated during AutoFDO profile attribution. */
DEF_EDGE_FLAG(ANNOTATED, 17)
+/* Edge probability predicted by __builtin_expect. */
+DEF_EDGE_FLAG(PREDICTED_BY_EXPECT, 18)
+
#endif
/*
diff --git gcc/common.opt gcc/common.opt
index 4305c89..439ed4c 100644
--- gcc/common.opt
+++ gcc/common.opt
@@ -950,6 +950,16 @@ fauto-profile-record-coverage-in-elf
Common Report Var(flag_auto_profile_record_coverage_in_elf) Optimization
Whether to record annotation coverage info in elf.
+fcheck-branch-annotation
+Common Report Var(flag_check_branch_annotation)
+Compare branch prediction result and autofdo profile information, store the
+result in a section in the generated elf file.
+
+fcheck-branch-annotation-threshold=
+Common Joined UInteger Var(check_branch_annotation_threshold) Init(100)
+The number of executions a basic block needs to reach before GCC dumps its
+branch prediction information with -fcheck-branch-annotation.
+
; -fcheck-bounds causes gcc to generate array bounds checks.
; For C, C++ and ObjC: defaults off.
; For Java: defaults to on.
diff --git gcc/doc/invoke.texi gcc/doc/invoke.texi
index fd89ecd..227da64 100644
--- gcc/doc/invoke.texi
+++ gcc/doc/invoke.texi
@@ -360,7 +360,7 @@ Objective-C and Objective-C++ Dialects}.
-fassociative-math -fauto-inc-dec -fauto-profile -fbranch-probabilities @gol
-fbranch-target-load-optimize -fbranch-target-load-optimize2 @gol
-fbtr-bb-exclusive -fcaller-saves @gol
--fcheck-data-deps -fclone-hot-version-paths @gol
+-fcheck-branch-annotation -fcheck-data-deps -fclone-hot-version-paths @gol
-fcombine-stack-adjustments -fconserve-stack @gol
-fcompare-elim -fcprop-registers -fcrossjumping @gol
-fcse-follow-jumps -fcse-skip-blocks -fcx-fortran-rules @gol
@@ -8636,6 +8636,11 @@ If @var{path} is specified, GCC will look at the
@var{path} to find
the profile feedback data files. Otherwise, GCC will find fbdata.afdo
in the current directory.
+@item -fcheck-branch-annotation
+@opindex -fcheck-branch-annotation
+Compare branch prediction result and autofdo profile information, store the
+result in a section in the generated elf file.
+
@item -fprofile-correction
@opindex fprofile-correction
Profiles collected using an instrumented binary for multi-threaded programs may
diff --git gcc/predict.c gcc/predict.c
index f27c58c..a19160a 100644
--- gcc/predict.c
+++ gcc/predict.c
@@ -1014,6 +1014,12 @@ combine_predictions_for_bb (basic_block bb)
{
first->probability = combined_probability;
second->probability = REG_BR_PROB_BASE - combined_probability;
+ if (flag_check_branch_annotation && first_match &&
+ best_predictor == PRED_BUILTIN_EXPECT)
+ {
+ first->flags |= EDGE_PREDICTED_BY_EXPECT;
+ second->flags |= EDGE_PREDICTED_BY_EXPECT;
+ }
}
}
--
2.0.0.526.g5318336
