From patchwork Mon Jun 30 21:06:48 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yi Yang X-Patchwork-Id: 365743 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 02E341400B7 for ; Tue, 1 Jul 2014 07:07:34 +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=QtF6tuIreC1kIta SXrwHZBO9RecXko3V5zKw59x4cLCwhD8WcaMrpYtghQx+IG06thp5JnRpsDiOmtb vjQe74CEhMqlU8h6Ua/34SHMy3woFGXG7gwT6JWASRtXC1pSsuHJsjqdeZ/3dRSW wsxljKmhMCRQWzW9d71skGOJKdpk= 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=V1Vg+PTjHbtYx0qyL3f2H qqHIYk=; b=DJZZa8lMS9ZvV5oPjbR5h4jSlTbupj7hXMU4YIspeuj/CGz4Ei49m WGJi6OMybJ0tA9uZ8fhua5nE0sea0JvVdhBiVsojUYtHcJBXMxmSVyWT8dGTKrs9 YEPfkG47QfThxbv6W0kUXuTpt8zJW9DHeqOF9WWhpnq9iemZvotFm4= Received: (qmail 14244 invoked by alias); 30 Jun 2014 21:07:26 -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 14122 invoked by uid 89); 30 Jun 2014 21:07:15 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.5 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-f177.google.com Received: from mail-ig0-f177.google.com (HELO mail-ig0-f177.google.com) (209.85.213.177) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Mon, 30 Jun 2014 21:07:11 +0000 Received: by mail-ig0-f177.google.com with SMTP id c1so4730111igq.10 for ; Mon, 30 Jun 2014 14:07:08 -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=DbmzjFW7up2LBbfmAL38V862WhUGPNvse9Kj0YdxyjU=; b=Kb8rMsKdWbiHWveZxZVfAY+iJcd4hw9+WtCA2TyMc5f8exjVj+5enRLR+iHnXEKBln o3tGQ3eC4u7+wSAsjge4j4Jp0ZxUCyxX5s4aEG1XNTQO+CtD06XZDtcp5tvI78tz5Qmf xJ0pJelSwZ3THxZql6BPbo7mNblnyDPfXwk9scneOA2OA9DPcgHBBEzdjREo1AzUBOdW 8h/Y9WkjKaSL9bEK9RYe622BmSBTiXOk1RXpHNuuNyA62tnfDWzljLLrIK0/Sx4r7K5V L/OHhdElU66IjsZ1MlYonD3c5b74TqpAnM3dHMMUxj+4bJ7bg/TDI0RiqZL509AFYt5Y c10A== X-Gm-Message-State: ALoCoQm9z+d3OsUpbZImsvFtI8JRXlPXjhuhpRIzAapkDrRXnFt9vjy5SZe7noIqD4BZX9eJsTZI X-Received: by 10.50.176.194 with SMTP id ck2mr8156224igc.44.1404162428855; Mon, 30 Jun 2014 14:07:08 -0700 (PDT) MIME-Version: 1.0 Received: by 10.64.19.200 with HTTP; Mon, 30 Jun 2014 14:06:48 -0700 (PDT) In-Reply-To: References: From: Yi Yang Date: Mon, 30 Jun 2014 14:06:48 -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. 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..96cad49 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,148 @@ 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); + tree function_decl = current_function_decl; + + if (block && TREE_CODE (block) == BLOCK) + { + for (block = BLOCK_SUPERCONTEXT (block); + block && (TREE_CODE (block) == BLOCK); + block = BLOCK_SUPERCONTEXT (block)) + { + location_t tmp_locus = BLOCK_SOURCE_LOCATION (block); + if (LOCATION_LOCUS (tmp_locus) == UNKNOWN_LOCATION) + continue; + + tree decl = get_function_decl_from_block (block); + function_decl = decl; + break; + } + } + + 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; +} + +/* Fill li with default information representing an unknown location. */ + +static void +fill_invalid_locus_information (locus_information_t* li) { + li->filename = ""; + li->lineno = 0; + li->function_lineno = 0; + for (int i = 0; i < 32; ++i) + li->function_hash[i] = '0'; + li->function_hash[32] = '\0'; +} + +/* Record branch prediction comparison for the given edge and actual + probability. */ +static void +record_branch_prediction_results (edge e, double 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 + fill_invalid_locus_information (&li); + + 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;%.6f;%.6f;%s;%u", + li.filename, li.lineno, bb->count, annotated?1:0, + probability / REG_BR_PROB_BASE, + e->probability / (double) REG_BR_PROB_BASE, + 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 +1549,21 @@ 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, probability); + first_edge = false; + } + + e->probability = probability; + } } } FOR_ALL_BB (bb) @@ -1417,8 +1572,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 +1700,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; + } } }