From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 1156 invoked by alias); 24 Sep 2013 18:25:51 -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 1143 invoked by uid 89); 24 Sep 2013 18:25:50 -0000 Received: from mail-qe0-f42.google.com (HELO mail-qe0-f42.google.com) (209.85.128.42) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Tue, 24 Sep 2013 18:25:50 +0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.6 required=5.0 tests=AWL,BAYES_00,NO_RELAYS autolearn=ham version=3.3.2 X-HELO: mail-qe0-f42.google.com Received: by mail-qe0-f42.google.com with SMTP id 1so3495325qec.29 for ; Tue, 24 Sep 2013 11:25:47 -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:date :message-id:subject:from:to:cc:content-type; bh=awOeKW497OI2s2+p84V1cbhvEWOjAyXEXogEKIZ7nNQ=; b=mk4TNK+doZCAx6SJET/NYMP3ZjSWdMToBJEk7FjDMacfMaIsRnokiuGgdl2xizboHN 9NHt0K/KkUQOwicK23MfTj5HrbVwOuQB6f6LRKSVTLSQQaa+tJT8HqLxfABEsxp3u5gB LzA4aPj5pwfKfJlTJB1305zW5aQsMy/o6ddYCH+5dOvlo9MAKQlVWb8MWUvwgM5WTkoN fscCLX4zUIvxuK7JVReB2LCNeK50OKM4smp+yNMg3psKtxY/LAH8Vhcybft3ekFBQ2cM kng44hqoDI7YEe0rVwUPQUcA5IY11BGBcnSIwpRFi0YrxobBn3wkZ6oB+fUw/sMKLYJr 5F6Q== X-Gm-Message-State: ALoCoQk4DHoe2d4F2WOAxLXPNucrc2/BG2pJNltBUTwcA0mstWff0UIWaV1K3Y+yww64mB+bhIPazl+xs1KGBPKvvjUDQzrbHjO8wW8NwTVuN4KBU52QYkkURTVu1Gx+oW67MH47XK6IsprMnMkUQfvOSTOK6j384MFu16MoUiR88xQM9HDITBrugTs/59Hv1DV6J+qOLElzyF+DTDGj9zp0XCrpz4vqnQ== MIME-Version: 1.0 X-Received: by 10.229.79.70 with SMTP id o6mr10843081qck.21.1380047147485; Tue, 24 Sep 2013 11:25:47 -0700 (PDT) Received: by 10.49.24.225 with HTTP; Tue, 24 Sep 2013 11:25:47 -0700 (PDT) In-Reply-To: <20130924175727.GA24697@kam.mff.cuni.cz> References: <20130817204408.GA16557@kam.mff.cuni.cz> <20130819150942.GA28264@kam.mff.cuni.cz> <20130831160420.GC7492@kam.mff.cuni.cz> <20130831214614.GA12372@kam.mff.cuni.cz> <20130924175727.GA24697@kam.mff.cuni.cz> Date: Tue, 24 Sep 2013 18:51:00 -0000 Message-ID: Subject: Re: [PATCH] Sanitize block partitioning under -freorder-blocks-and-partition From: Teresa Johnson To: Jan Hubicka Cc: "gcc-patches@gcc.gnu.org" , "marxin.liska" Content-Type: text/plain; charset=ISO-8859-1 X-IsSubscribed: yes X-SW-Source: 2013-09/txt/msg01814.txt.bz2 On Tue, Sep 24, 2013 at 10:57 AM, Jan Hubicka wrote: >> >> I looked at one that failed after 100 as well (20031204-1.c). In this >> case, it was due to expansion which was creating multiple branches/bbs >> from a logical OR and guessing incorrectly on how to assign the >> counts: >> >> if (octets == 4 && (*cp == ':' || *cp == '\0')) { >> >> The (*cp == ':' || *cp == '\0') part looked like the following going >> into RTL expansion: >> >> [20031204-1.c : 31:33] _29 = _28 == 58; >> [20031204-1.c : 31:33] _30 = _28 == 0; >> [20031204-1.c : 31:33] _31 = _29 | _30; >> [20031204-1.c : 31:18] if (_31 != 0) >> goto ; >> else >> goto ; >> >> where the result of the OR was always true, so bb 16 had a count of >> 100 and bb 19 a count of 0. When it was expanded, the expanded version >> of the above turned into 2 bbs with a branch in between. Both >> comparisons were done in the first bb, but the first bb checked >> whether the result of the *cp == '\0' compare was true, and if not >> branched to the check for whether the *cp == ':' compare was true. It >> gave the branch to the second check against ':' a count of 0, so that >> bb got a count of 0 and was split out, and put the count of 100 on the >> fall through assuming the compare with '\0' always evaluated to true. >> In reality, this OR condition was always true because *cp was ':', not >> '\0'. Therefore, the count of 0 on the second block with the check for >> ':' was incorrect, we ended up trying to execute it, and failed. > > I see, we produce: > ;; if (_26 != 0) > > (insn 94 93 95 (set (reg:CCZ 17 flags) > (compare:CCZ (reg:QI 107 [ D.2184 ]) > (const_int 0 [0]))) a.c:31 -1 > (nil)) > > (insn 95 94 96 (set (reg:QI 122 [ D.2186 ]) > (eq:QI (reg:CCZ 17 flags) > (const_int 0 [0]))) a.c:31 -1 > (nil)) > > (insn 96 95 97 (set (reg:CCZ 17 flags) > (compare:CCZ (reg:QI 122 [ D.2186 ]) > (const_int 0 [0]))) a.c:31 -1 > (nil)) > > (jump_insn 97 96 98 (set (pc) > (if_then_else (ne (reg:CCZ 17 flags) > (const_int 0 [0])) > (label_ref 100) > (pc))) a.c:31 -1 > (expr_list:REG_BR_PROB (const_int 6100 [0x17d4]) > (nil))) > > (insn 98 97 99 (set (reg:CCZ 17 flags) > (compare:CCZ (reg:QI 108 [ D.2186 ]) > (const_int 0 [0]))) a.c:31 -1 > (nil)) > > (jump_insn 99 98 100 (set (pc) > (if_then_else (eq (reg:CCZ 17 flags) > (const_int 0 [0])) > (label_ref 0) > (pc))) a.c:31 -1 > (expr_list:REG_BR_PROB (const_int 3900 [0xf3c]) > (nil))) > > (code_label 100 99 0 14 "" [0 uses]) > > That is because we TER together "_26 = _25 | _24" and "if (_26 != 0)" > > First I think the logic of do_jump should really be moved to trees. It is not > doing things that can not be adequately represented by gimple. > > I am not that certain we want to move it before profiling though. >> >> Presumably we had the correct profile data for both blocks, but the >> accuracy was reduced when the OR was represented as a logical >> computation with a single branch. We could change the expansion code >> to do something different, e.g. treat as a 50-50 branch. But we would >> still end up with integer truncation issues when there was a single >> training run. But that could be dealt with conservatively in the > > Yep, but it is still better than what we have now - if the test above was > in hot part of program (i.e. not executed once), we will end up optimizing > the second conditional for size. > > So I think it is do_jump bug to not distribute probabilities across the two > conditoinals introduced. >> bbpart code as I suggested for the jump threading issue above. I.e. a >> cold block with incoming non-cold edges conservatively not marked cold >> for splitting. > > Yep, we can probably do that, but we ought to fix the individual cases > above at least for resonable number of runs. I made this change and it removed a few of the failures. I looked at another case that still failed with 1 train run but passed with 100. It turned out to be another truncation issue exposed by RTL expansion, where we created some control flow for a memset builtin which was in a block with an execution count of 1. Some of the blocks got frequencies less than half the original block, so the count was rounded down or truncated to 0. I noticed that in this case (as well as the jump threading case I fixed by looking for non-zero incoming edges in partitioning) that the bb frequency was non-zero. Why not just have probably_never_executed_bb_p return simply return false bb->frequency is non-zero (right now it does the opposite - returns true when bb->frequency is 0)? Making this change removed a bunch of other failures. With this change as well, there are only 3 cases that still fail with 1 train run that pass with 100. Need to look at those. > > Will you look into logic of do_jump or shall I try to dive in? I can take a look, but probably won't have a chance until late this week. If you don't get to it before then I will see if I can figure out why it is applying the branch probabilities this way. Teresa > > Honza -- Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413