From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 10000 invoked by alias); 17 Aug 2013 06:31:54 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 9987 invoked by uid 89); 17 Aug 2013 06:31:53 -0000 X-Spam-SWARE-Status: No, score=-5.3 required=5.0 tests=AWL,BAYES_00,KHOP_THREADED,RCVD_IN_DNSWL_LOW,RCVD_IN_HOSTKARMA_YE,RP_MATCHES_RCVD,SPF_PASS autolearn=ham version=3.3.2 Received: from mail-qe0-f47.google.com (HELO mail-qe0-f47.google.com) (209.85.128.47) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Sat, 17 Aug 2013 06:31:51 +0000 Received: by mail-qe0-f47.google.com with SMTP id b10so1659200qen.34 for ; Fri, 16 Aug 2013 23:31:49 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=d5eZhtcibJW4DJVJmmigdiYMKfTDe6svwPR43vTYUek=; b=hqP0729qnGrwQeruK1/vz+U39Ob3bVYe3NcYu2oGIgD3CuuFPFxne9Gmh2q4rSpXKh StPaPL7lCzD0hll9TTTNUr4mITJPfHqtY72AL20mhv3208tbyS86QmTBJcXsfZ7A/0hh bD3z+a1t26N8pp6ITZ3zCzzSd4y9xd2l8aPBVlqCgE9VhccFgb+VSDVKdZRiXZcC4DhZ ertJ8ojXdB2G0HZSPe880pzpUl7P+TvyOjuLebfgdeAxCE8qv1fCxkE06fNzjTIonjxC 4ohREMA29AyHBh46a1Hr+U4KlEVe1Mv33GIZtA9U+U3clUv6xm8IH4XzepRroQUOOOpH 4Pbg== X-Gm-Message-State: ALoCoQk5TY+k5K+AwGaZMbJbpkSRX1VCPN7Xh/QO4qEfxlQvcxKRjBg5Oh2hGIJu3hW5pXqQ848NqV0tM1WnM+yeLtabXaZBu003n+yRDt5I9Ei3pVsYlVCUdeDaaagR6Ae5zNpE1QvvRslgeZFpO4UU6S2YjZKBe70Xl3CM46gx7prOT1c2qs5k8ql6M6MPzavw57knmMhHTwS50NnDmV1JKc6rrYoNNg== MIME-Version: 1.0 X-Received: by 10.224.162.210 with SMTP id w18mr1697868qax.56.1376721109690; Fri, 16 Aug 2013 23:31:49 -0700 (PDT) Received: by 10.49.40.162 with HTTP; Fri, 16 Aug 2013 23:31:49 -0700 (PDT) In-Reply-To: References: <20130802150529.GC15776@kam.mff.cuni.cz> <20130808222332.GA31755@kam.mff.cuni.cz> <20130809095843.GC31755@kam.mff.cuni.cz> <20130809152804.GA6579@kam.mff.cuni.cz> Date: Sat, 17 Aug 2013 15:54:00 -0000 Message-ID: Subject: Re: [PATCH] Sanitize block partitioning under -freorder-blocks-and-partition From: Teresa Johnson To: Jan Hubicka Cc: Bernhard Reutner-Fischer , "gcc-patches@gcc.gnu.org" , Steven Bosscher , Jeff Law , "marxin.liska" , Sriraman Tallam Content-Type: text/plain; charset=ISO-8859-1 X-SW-Source: 2013-08/txt/msg00929.txt.bz2 On Fri, Aug 9, 2013 at 2:02 PM, Teresa Johnson wrote: > On Fri, Aug 9, 2013 at 8:28 AM, Jan Hubicka wrote: >>> > Do we sanity check that the cold partition does not contain any blocks of >>> > count 0? It may be that the profile is broken enough to make partitioning >>> > not work. >>> >>> Do you mean sanity check that the cold partition does not contain any >>> blocks of count > 0? (they should all be zero) I don't think that >>> sanity check is there, but I can try adding that. >> >> Thanks, lets start with this - I suppose we need to figure out if >> 1) the reachable blocks goes to cold section because partitioning decides >> so even if they have non-0 count. > > Right, this should be easy enough to check and should hopefully never happen. > >> 2) the reachable blocks goes to cold section because they have incorrectly >> updated count to 0 by someone > > A sanity check should find this too. But it can happen now for various > reasons like the comdat issue I described below. But it will be good > to flag these and fix them. > >> 3) profiling gets some blocks wrong. > > This is the one that will be tough to fix, if the training run isn't > representative. > >>> >>> The issue with such a sanity check may be due to the later fixup I >>> have in this patch (fixup_partitions). It is invoked after certain >>> optimizations on the cfg that may make hot blocks previously reached >>> by both hot and cold edges only reachable by cold blocks. These blocks >>> are remarked cold. If the profile data hasn't been updated correctly >>> it is possible that they would still have a non-0 count, although they >>> are essentially cold after the cfg transformation. >> >> Well, or the other posibility is that the edges was updated wrong >> and the blocks are really cold. We need to figure out if that happens >> commonly enough. >> >> I will try to think of some artificial testcases. >> >>> >>> But certainly such a sanity check should always succeed after the >>> original partitioning. >>> >>> > I can think of inlining where the count gets scaled all way down to 0. Perhaps >>> > count scaling code can be modified to never round towards 0 for block executing >>> > non-0 times... >>> >>> This reminds me of why this situation could happen. When I have been >>> testing this on the google branch I found situations where COMDAT >>> routines have 0 profile counts (if I remember correctly, this happens >>> when profile-gen binary has call to out-of-line copy of COMDAT in >>> module A, linker chooses the out-of-line copy from module B, therefore >>> the profile data for COMDAT in module A is 0). When the COMDAT gets >>> inlined, the 0 counts on its bbs are scaled to 0, even though the >>> callsite is non-zero. I have a patch that I was planning to send as a >>> follow-up that handles this case by propagating the callsite bb's >>> count to the inlined code when it has 0 counts, scaling by the edge >>> frequencies. I can either include that patch in this one, or send it >>> for review separately right now. Do you want to give it a try with >>> this one to see if it addresses the issue? >> >> This scenario should not happen with LTO setup: the LTO symbol tables contains >> code before early optimization and should be identical with profiling or >> without (modulo the new references and call from profile code). >> >> But this patch seems useful as a backup solution for non-LTO, so yes, please >> send it separately and I can try to double check that it really do not happen >> with LTO. >> (acutally LTO symtab may just chose COMDAT from module that has counts with it. >> It has all the info for it. I was thinkin about it few weeks back. It is >> bit hard to do - you need to verify that all references from the function are >> the same or linking might fail if you overwrite linker's decisiosns). > > I see, yes LTO can deal with this better since it has global > information. In non-LTO mode (including LIPO) we have the issue. > > I take it gimp is built with LTO and therefore shouldn't be hitting > this comdat issue? > > Let me do a couple things: Here is some status: > - port over my comdat inlining fix from the google branch to trunk and > send it for review. If you or Martin could try it to see if it helps > with function splitting to avoid the hits from the cold code that > would be great I have included the cleaned up patch below. I will send it to trunk for review, but included it below if you want to try it out before I send it pending a little more extensive testing I want to do after the cleanup (it passes bootstrap and some small test cases I checked manually). > - I'll add some new sanity checking to try to detect non-zero blocks > in the cold section, or 0 blocks reached by non-zero edges and see if > I can flush out any problems with my tests or a profiledbootstrap or > gimp. I added both of these and ran into issues due to profile maintenance. For example, there were non-zero blocks in the cold section because pro_and_epilogue split a simple return block that was previously reach by both hot and cold paths. The new return block that was then only reached via the cold path did not have its count properly updated to reflect this, and since with this patch, blocks dominated by cold blocks are remarked cold, we ended up with a non-zero count block in the cold section. And there were 0 count blocks reached by non-zero edges because copyprop did not clean up edge weights after removing some branches and blocks, leading to non-zero edge weights that had previously targeted a branch that was removed, now targeting a 0 count block that the removed branch always branched around. In any case, the good news is in that the cases I looked at, the splitting code is doing the right thing and these blocks that were marked cold really were cold. It would be great to fix the profile maintenance issues, but that in the meantime the above sanity checks are too aggressive. I think it makes sense to commit the current patch if possible, as it is making the splitting more sane. > - I'll try building and profiling gimp myself to see if I can > reproduce the issue with code executing out of the cold section. I have spent some time this week trying to get the latest gimp Martin pointed me to configured and built, but it took awhile to track down and configure/build all of the required versions of dependent packages. I'm still hitting some issues trying to get it compiled, so it may not yet be configured properly. I'll take a look again early next week. Teresa patch for updating counts based on estimated frequencies to address inlined comdats with 0 profile counts: 013-08-16 Teresa Johnson * tree-inline.c (copy_bb): Compute count based on frequency. (copy_edges_for_bb): Ditto. (copy_cfg_body): Ditto. (copy_body): Pass down frequency. (expand_call_inline): Ditto. (tree_function_versioning): Ditto. * predict.c (init_and_estimate_bb_frequencies): New function. (rebuild_frequencies): Invoke init_and_estimate_bb_frequencies. * predict.h (init_and_estimate_bb_frequencies): Declare. * profile.c (branch_prob): Invoke init_and_estimate_bb_frequencies. * ipa-inline-transform.c (update_noncloned_frequencies): Scale edge counts. (clone_inlined_nodes): Compute edge count scale if needed. Index: tree-inline.c =================================================================== --- tree-inline.c (revision 201644) +++ tree-inline.c (working copy) @@ -1502,7 +1502,7 @@ remap_gimple_stmt (gimple stmt, copy_body_data *id static basic_block copy_bb (copy_body_data *id, basic_block bb, int frequency_scale, - gcov_type count_scale) + gcov_type count_scale, gcov_type freq_to_count_scale) { gimple_stmt_iterator gsi, copy_gsi, seq_gsi; basic_block copy_basic_block; @@ -1519,7 +1519,13 @@ copy_bb (copy_body_data *id, basic_block bb, int f basic_block_info automatically. */ copy_basic_block = create_basic_block (NULL, (void *) 0, (basic_block) prev->aux); - copy_basic_block->count = apply_scale (bb->count, count_scale); + copy_basic_block->count + = (count_scale + ? apply_scale (bb->count, count_scale) + /* When the callee bb counts were all zero (e.g. this was a COMDAT + that didn't get profile counts) then we compute the new bb counts + via the statically-estimated frequencies. */ + : RDIV ((gcov_type)bb->frequency * freq_to_count_scale, BB_FREQ_MAX)); /* We are going to rebuild frequencies from scratch. These values have just small importance to drive canonicalize_loop_headers. */ @@ -1888,7 +1894,8 @@ update_ssa_across_abnormal_edges (basic_block bb, debug stmts are left after a statement that must end the basic block. */ static bool -copy_edges_for_bb (basic_block bb, gcov_type count_scale, basic_block ret_bb, +copy_edges_for_bb (basic_block bb, gcov_type count_scale, + basic_block ret_bb, bool can_make_abnormal_goto) { basic_block new_bb = (basic_block) bb->aux; @@ -1912,7 +1919,14 @@ static bool && old_edge->dest->aux != EXIT_BLOCK_PTR) flags |= EDGE_FALLTHRU; new_edge = make_edge (new_bb, (basic_block) old_edge->dest->aux, flags); - new_edge->count = apply_scale (old_edge->count, count_scale); + basic_block new_src_bb = (basic_block) old_edge->src->aux; + new_edge->count + = (count_scale + ? apply_scale (old_edge->count, count_scale) + // The bb counts have already been scaled with freq_to_count_scale + // when that is non-zero, so just scale that new bb count by + // the edge probability. + : apply_probability (new_src_bb->count, old_edge->probability)); new_edge->probability = old_edge->probability; } @@ -2282,7 +2296,8 @@ redirect_all_calls (copy_body_data * id, basic_blo another function. Walks FN via CFG, returns new fndecl. */ static tree -copy_cfg_body (copy_body_data * id, gcov_type count, int frequency_scale, +copy_cfg_body (copy_body_data * id, gcov_type count, + int frequency, int frequency_scale, basic_block entry_block_map, basic_block exit_block_map, bitmap blocks_to_copy, basic_block new_entry) { @@ -2293,15 +2308,20 @@ static tree basic_block bb; tree new_fndecl = NULL; bool need_debug_cleanup = false; - gcov_type count_scale; + gcov_type count_scale = 0; + gcov_type freq_to_count_scale = 0; int last; int incoming_frequency = 0; gcov_type incoming_count = 0; - if (ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->count) - count_scale - = GCOV_COMPUTE_SCALE (count, - ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->count); + basic_block entry_bb = ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun); + if (entry_bb->count) + count_scale = GCOV_COMPUTE_SCALE (count, entry_bb->count); + /* When the callee bb counts were all zero (e.g. this was a COMDAT + that didn't get profile counts) then we compute the new bb counts + via the statically-estimated frequencies. */ + else if (entry_bb->frequency) + freq_to_count_scale = RDIV (count * frequency, entry_bb->frequency); else count_scale = REG_BR_PROB_BASE; @@ -2323,7 +2343,13 @@ static tree incoming_frequency += EDGE_FREQUENCY (e); incoming_count += e->count; } - incoming_count = apply_scale (incoming_count, count_scale); + incoming_count + = (count_scale + ? apply_scale (incoming_count, count_scale) + /* When the callee bb counts were all zero (e.g. this was a COMDAT + that didn't get profile counts) then we compute the new bb counts + via the statically-estimated frequencies. */ + : RDIV (incoming_frequency * freq_to_count_scale, BB_FREQ_MAX)); incoming_frequency = apply_scale ((gcov_type)incoming_frequency, frequency_scale); ENTRY_BLOCK_PTR->count = incoming_count; @@ -2350,7 +2376,8 @@ static tree FOR_EACH_BB_FN (bb, cfun_to_copy) if (!blocks_to_copy || bitmap_bit_p (blocks_to_copy, bb->index)) { - basic_block new_bb = copy_bb (id, bb, frequency_scale, count_scale); + basic_block new_bb = copy_bb (id, bb, frequency_scale, count_scale, + freq_to_count_scale); bb->aux = new_bb; new_bb->aux = bb; new_bb->loop_father = entry_block_map->loop_father; @@ -2364,7 +2391,8 @@ static tree FOR_ALL_BB_FN (bb, cfun_to_copy) if (!blocks_to_copy || (bb->index > 0 && bitmap_bit_p (blocks_to_copy, bb->index))) - need_debug_cleanup |= copy_edges_for_bb (bb, count_scale, exit_block_map, + need_debug_cleanup |= copy_edges_for_bb (bb, count_scale, + exit_block_map, can_make_abormal_goto); if (new_entry) @@ -2562,7 +2590,8 @@ copy_tree_body (copy_body_data *id) another function. */ static tree -copy_body (copy_body_data *id, gcov_type count, int frequency_scale, +copy_body (copy_body_data *id, gcov_type count, int frequency, + int frequency_scale, basic_block entry_block_map, basic_block exit_block_map, bitmap blocks_to_copy, basic_block new_entry) { @@ -2571,7 +2600,8 @@ static tree /* If this body has a CFG, walk CFG and copy. */ gcc_assert (ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (fndecl))); - body = copy_cfg_body (id, count, frequency_scale, entry_block_map, exit_block_map, + body = copy_cfg_body (id, count, frequency, frequency_scale, + entry_block_map, exit_block_map, blocks_to_copy, new_entry); copy_debug_stmts (id); @@ -4172,7 +4202,7 @@ expand_call_inline (basic_block bb, gimple stmt, c function in any way before this point, as this CALL_EXPR may be a self-referential call; if we're calling ourselves, we need to duplicate our body before altering anything. */ - copy_body (id, bb->count, + copy_body (id, bb->count, bb->frequency, GCOV_COMPUTE_SCALE (cg_edge->frequency, CGRAPH_FREQ_BASE), bb, return_block, NULL, NULL); @@ -5299,8 +5329,9 @@ tree_function_versioning (tree old_decl, tree new_ } /* Copy the Function's body. */ - copy_body (&id, old_entry_block->count, REG_BR_PROB_BASE, - ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, blocks_to_copy, new_entry); + copy_body (&id, old_entry_block->count, old_entry_block->frequency, + REG_BR_PROB_BASE, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, + blocks_to_copy, new_entry); /* Renumber the lexical scoping (non-code) blocks consecutively. */ number_blocks (new_decl); Index: predict.c =================================================================== --- predict.c (revision 201644) +++ predict.c (working copy) @@ -2976,6 +2976,24 @@ make_pass_strip_predict_hints (gcc::context *ctxt) return new pass_strip_predict_hints (ctxt); } +/* Initialize loop edges and compute estimated bb frequencies when there + is no profile data available. */ + +void +init_and_estimate_bb_frequencies (void) +{ + if (profile_status == PROFILE_READ && counts_to_freqs ()) + return; + + loop_optimizer_init (0); + add_noreturn_fake_exit_edges (); + mark_irreducible_loops (); + connect_infinite_loops_to_exit (); + estimate_bb_frequencies (); + remove_fake_exit_edges (); + loop_optimizer_finalize (); +} + /* Rebuild function frequencies. Passes are in general expected to maintain profile by hand, however in some cases this is not possible: for example when inlining several functions with loops freuqencies might run @@ -2986,15 +3004,7 @@ rebuild_frequencies (void) { timevar_push (TV_REBUILD_FREQUENCIES); if (profile_status == PROFILE_GUESSED) - { - loop_optimizer_init (0); - add_noreturn_fake_exit_edges (); - mark_irreducible_loops (); - connect_infinite_loops_to_exit (); - estimate_bb_frequencies (); - remove_fake_exit_edges (); - loop_optimizer_finalize (); - } + init_and_estimate_bb_frequencies (); else if (profile_status == PROFILE_READ) counts_to_freqs (); else Index: predict.h =================================================================== --- predict.h (revision 201644) +++ predict.h (working copy) @@ -38,6 +38,7 @@ enum prediction extern void predict_insn_def (rtx, enum br_predictor, enum prediction); extern int counts_to_freqs (void); extern void estimate_bb_frequencies (void); +extern void init_and_estimate_bb_frequencies (void); extern const char *predictor_name (enum br_predictor); extern tree build_predict_expr (enum br_predictor, enum prediction); extern void tree_estimate_probability (void); Index: profile.c =================================================================== --- profile.c (revision 201644) +++ profile.c (working copy) @@ -1305,6 +1305,12 @@ branch_prob (void) values.release (); free_edge_list (el); + + /* Call after setting profile_status to PROFILE_READ, will then + invoke counts_to_freqs and if the sum of the counts is zero, will + estimate the frequencies. */ + init_and_estimate_bb_frequencies (); + coverage_end_function (lineno_checksum, cfg_checksum); } ^L Index: ipa-inline-transform.c =================================================================== --- ipa-inline-transform.c (revision 201644) +++ ipa-inline-transform.c (working copy) @@ -51,7 +51,7 @@ int nfunctions_inlined; static void update_noncloned_frequencies (struct cgraph_node *node, - int freq_scale) + gcov_type count_scale, int freq_scale) { struct cgraph_edge *e; @@ -60,14 +60,16 @@ update_noncloned_frequencies (struct cgraph_node * freq_scale = 1; for (e = node->callees; e; e = e->next_callee) { + e->count = apply_scale (e->count, count_scale); e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE; if (e->frequency > CGRAPH_FREQ_MAX) e->frequency = CGRAPH_FREQ_MAX; if (!e->inline_failed) - update_noncloned_frequencies (e->callee, freq_scale); + update_noncloned_frequencies (e->callee, count_scale, freq_scale); } for (e = node->indirect_calls; e; e = e->next_callee) { + e->count = apply_scale (e->count, count_scale); e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE; if (e->frequency > CGRAPH_FREQ_MAX) e->frequency = CGRAPH_FREQ_MAX; @@ -169,7 +171,13 @@ clone_inlined_nodes (struct cgraph_edge *e, bool d } duplicate = false; e->callee->symbol.externally_visible = false; - update_noncloned_frequencies (e->callee, e->frequency); + // In the case of a COMDAT, the callee's count may be from other + // modules, and we need to scale it for the current module's calls + // (e.g. e->count may be 0 despite e->callee->count > 0). + gcov_type count_scale = REG_BR_PROB_BASE; + if (e->callee->count > e->count) + count_scale = GCOV_COMPUTE_SCALE (e->count, e->callee->count); + update_noncloned_frequencies (e->callee, count_scale, e->frequency); } else { > > Thanks, > Teresa > >>> >>> Also, can you send me reproduction instructions for gimp? I don't >>> think I need Martin's patch, but which version of gimp and what is the >>> equivalent way for me to train it? I have some scripts to generate a >>> similar type of instruction heat map graph that I have been using to >>> tune partitioning and function reordering. Essentially it uses linux >>> perf to sample on instructions_retired and then munge the data in >>> several ways to produce various stats and graphs. One thing that has >>> been useful has been to combine the perf data with nm output to >>> determine which cold functions are being executed at runtime. >> >> Martin? >> >>> >>> However, for this to tell me which split cold bbs are being executed I >>> need to use a patch that Sri sent for review several months back that >>> gives the split cold section its own name: >>> http://gcc.gnu.org/ml/gcc-patches/2013-04/msg01571.html >>> Steven had some follow up comments that Sri hasn't had a chance to address yet: >>> http://gcc.gnu.org/ml/gcc-patches/2013-05/msg00798.html >>> (cc'ing Sri as we should probably revive this patch soon to address >>> gdb and other issues with detecting split functions properly) >> >> Intresting, I used linker script for this purposes, but that his GNU ld only... >> >> Honza >>> >>> Thanks! >>> Teresa >>> >>> > >>> > Honza >>> >> >>> >> Thanks, >>> >> Teresa >>> >> >>> >> > I think we are really looking primarily for dead parts of the functions (sanity checks/error handling) >>> >> > that should not be visited by train run. We can then see how to make the heuristic more aggressive? >>> >> > >>> >> > Honza >>> >> >>> >> >>> >> >>> >> -- >>> >> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413 >>> >>> >>> >>> -- >>> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413 > > > > -- > Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413 -- Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413