From patchwork Tue Jul 1 00:42:42 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yi Yang X-Patchwork-Id: 365842 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 07E951400AB for ; Tue, 1 Jul 2014 10:43:16 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; q=dns; s=default; b=V/U/EDcA011YBJh IpxlrB0IpS7kZlHqYp0VkRkn2JvK8txl+0ADbooUhCA1DTcuODTbECHCni0ZxrBO c3Mdzm4sYDk2nx/rzW/W6o/GC9YtO6yVi0S+xXf2/Qv9DXtJhCBYAyejrEwX1Kkh nIHlfvNrSDaE3Q8LeZd5BtQt8PnI= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; s=default; bh=P2zED8fUMRCUDljE8qt88 cvYwcM=; b=rSluWe71RYg2OloOQjYINkZLfCs/mOhns6NgPmkl5XdyZ871qKFoE zwaeNyoD2lunPG6tF6ph3joTCfAS3MnHVzGzEcongNY2A4aai88VRszVZEf6fJb9 PJmcGfwtlCidNfjQitCkV/1CL67IFLVYG9Gpk8uQoSJS8spCRQ8wEQ= Received: (qmail 26739 invoked by alias); 1 Jul 2014 00:43:10 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 26717 invoked by uid 89); 1 Jul 2014 00:43:08 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.0 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW, SPF_PASS, T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: mail-ig0-f172.google.com Received: from mail-ig0-f172.google.com (HELO mail-ig0-f172.google.com) (209.85.213.172) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Tue, 01 Jul 2014 00:43:05 +0000 Received: by mail-ig0-f172.google.com with SMTP id hn18so4939472igb.11 for ; Mon, 30 Jun 2014 17:43:03 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=IP4BvOmAdHMyuhc8LnuCH0l+f9izTL7VFisMoBauUtk=; b=mm9Qz3f1A18CyZqOhDoTQOyVJ3gnwwZqDe2h+Rm1YVqUdE1yXDXYkARPHPGM4kARY3 zZF3CCAmFsdNMul6O7NAFqfH/iNNO3UZphwltapYPY8AYlo35Q+617roQldIPbA5qdqa pPdYlytd9SRECnZMDOHGV5gMURNPKCRQpp6Qg070W8lkuqInXRXRUsMvgkj5cJuxHzJo ywjivUW+Pr1ad9SfQ9Y0JwUIR3gFpwKTRbOzNGemekoWitKKdSwi2PJer7blitZWVeeB EzTS4P4ssvhdkC9zNjQU3P3xyzeQMXBvSvBesoq5WD0DU6gtqIQZVzI9xvOCTCpbztCh SpCA== X-Gm-Message-State: ALoCoQmxqjAM/44eOnQ/O7b67nw1UdeBOaeoZplWhwuR6EZfbMVQaPjqoqj+phyCZqlni3rq8aS2 X-Received: by 10.43.7.10 with SMTP id om10mr11658681icb.66.1404175382783; Mon, 30 Jun 2014 17:43:02 -0700 (PDT) MIME-Version: 1.0 Received: by 10.64.19.200 with HTTP; Mon, 30 Jun 2014 17:42:42 -0700 (PDT) In-Reply-To: References: From: Yi Yang Date: Mon, 30 Jun 2014 17:42:42 -0700 Message-ID: Subject: Re: [GOOGLE] Report the difference between profiled and guessed or annotated branch probabilities. To: Dehao Chen Cc: Xinliang David Li , GCC Patches X-IsSubscribed: yes Fixed a style error (missing a space before a left parenthesis) On Mon, Jun 30, 2014 at 5:41 PM, Yi Yang wrote: > Done. > > On Mon, Jun 30, 2014 at 5:20 PM, Dehao Chen 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 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 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 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 wrote: >>> >>> Fixed. (outputting only the integer percentage) >>> >>> >>> >>> On Mon, Jun 30, 2014 at 2:20 PM, Yi Yang 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 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 >>> >>>>> 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 >>> >>>>>> 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 >>> >>>>>>> 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 >>> >>>>>>>> >>> >>>>>>>> * 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 >>> >>>>>>>> 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 >>> >>>>>>>> > 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 >>> >>>>>>>> >> >>> >>>>>>>> >> * 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..3122835 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; + /* Line number of the first line of function definition. */ + unsigned function_lineno; + /* Hash value calculated from function name and length, used to uniquely + identify a function across different source versions. */ + char function_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; + unsigned function_length = 0; + function *f = DECL_STRUCT_FUNCTION (function_decl); + + li->function_lineno = LOCATION_LINE (DECL_SOURCE_LOCATION (function_decl)); + + if (f) + { + function_length = LOCATION_LINE (f->function_end_locus) - + li->function_lineno; + } + + 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_finish_ctx (&ctx, md5_result); + + /* Convert MD5 to hexadecimal representation. */ + for (int i = 0; i < 16; ++i) + { + sprintf (li->function_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;%u", + li.filename, li.lineno, bb->count, annotated?1:0, + probability, e->probability, + li.function_hash, li.function_lineno); + 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 (probability + 0.5)); + first_edge = false; + } + + e->probability = probability; + } } } FOR_ALL_BB (bb) @@ -1417,8 +1550,11 @@ 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; + e->flags &= ~EDGE_PREDICTED_BY_EXPECT; + } bb->aux = NULL; } @@ -1542,9 +1678,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..cecc801 100644 --- gcc/predict.c +++ gcc/predict.c @@ -1014,6 +1014,11 @@ combine_predictions_for_bb (basic_block bb) { first->probability = combined_probability; second->probability = REG_BR_PROB_BASE - combined_probability; + if (first_match && best_predictor == PRED_BUILTIN_EXPECT) + { + first->flags |= EDGE_PREDICTED_BY_EXPECT; + second->flags |= EDGE_PREDICTED_BY_EXPECT; + } } }