From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 10213 invoked by alias); 30 Sep 2014 18:20:45 -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 10196 invoked by uid 89); 30 Sep 2014 18:20:43 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.3 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_LOW,RP_MATCHES_RCVD,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-qc0-f178.google.com Received: from mail-qc0-f178.google.com (HELO mail-qc0-f178.google.com) (209.85.216.178) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Tue, 30 Sep 2014 18:20:42 +0000 Received: by mail-qc0-f178.google.com with SMTP id c9so2896134qcz.9 for ; Tue, 30 Sep 2014 11:20:40 -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=6u+OoAjl9UT/xYwl5plAEH0cWPvXmo5sN4rWeHY8JDE=; b=fT9lsJWQ6/RhQBqAiOYmx3mx+O4qR7TXA2Gu6p7y1NqS6QwRhOfAHPitdedtSrkS27 A96ABfpptrPCdhxgVWa5xYk62kYEO+2ei1Csdn9lpxxQfR4MKHFyimjpWlO2Aj5dT3mT VLdSOicgocA+gzwLwLr9gVTi/nmvp7gyX5vsEOwhZzu9Jr3ctpUAZ9HjhHHjCGydRpjQ L2BunpfkN1vsEv9hUERZ2hq//3KdQYW4tWtMXzb4pOgkyoxd6eGsBJWt7issaUdFv//c Vkh5mvgUDILd0/vc80yrie0UBaA5CADJ0bT2RAoLSkVKdDvzkD8fhu2jatyetBbJnR4e KfIA== X-Gm-Message-State: ALoCoQkO8/baj9mdDsaBn6dr7EH/ppUnWgb5hJ9vFJtJAUyXl7EYxfUmpyABLD8gTo0MY+e/8scP MIME-Version: 1.0 X-Received: by 10.140.92.199 with SMTP id b65mr27099159qge.86.1412101238185; Tue, 30 Sep 2014 11:20:38 -0700 (PDT) Received: by 10.229.148.1 with HTTP; Tue, 30 Sep 2014 11:20:38 -0700 (PDT) In-Reply-To: <542A32AB.1040708@redhat.com> References: <53CF1DFD.7080805@redhat.com> <542A32AB.1040708@redhat.com> Date: Tue, 30 Sep 2014 18:20:00 -0000 Message-ID: Subject: Re: [PATCH] Redesign jump threading profile updates From: Teresa Johnson To: Jeff Law Cc: "gcc-patches@gcc.gnu.org" , Jan Hubicka , David Li Content-Type: text/plain; charset=UTF-8 X-IsSubscribed: yes X-SW-Source: 2014-09/txt/msg02686.txt.bz2 On Mon, Sep 29, 2014 at 9:33 PM, Jeff Law wrote: > On 09/29/14 08:19, Teresa Johnson wrote: >>> >>> >>> Just an update - I found some good test cases by compiling the >>> c-torture tests with profile feedback with and without my patch. But >>> in the cases I pulled out I saw that there were still a couple profile >>> or probability insanities introduced by jump threading (albeit far >>> less than before), so I wanted to investigate before I commit. I ran >>> out of time this week and will not get to this until I get back from >>> vacation the week after next. >> >> >> Hi Jeff, >> >> I finally had a chance to get back to this and look at the remaining >> insanities in the new test cases I created. It turns out that there >> were still a few issues in the case where there were guessed >> frequencies and no profile counts. The two test cases I created do use >> FDO, and the insanities in the routines with profile counts went away >> with my patch. But the outlined copies of routines that were also >> inlined into the main routine still had estimated frequencies, and >> these still had a few issues. >> >> The problem is that the profile updates are done incrementally as we >> walk and update the paths in ssa_fix_duplicate_block_edges, including >> the block and edge counts, the block frequencies and the >> probabilities. This is very difficult to do when only operating on >> frequencies since the edge frequencies are derived from the source >> block frequency and the probability. Therefore, once the source block >> frequency is updated, the edge frequency is also affected, and it is >> really difficult to figure out what the update to the edge frequency >> (essentially the probability) is using the same incremental update >> approach. I was attempting to handle this with the routine >> deduce_freq, for example, but this turned out to have issues for >> certain types of paths. I tried a few other approaches, but they start >> looking really ugly and I didn't want to add a parallel but different >> algorithm in the case of no profile counts. >> >> So by far the simplest approach was simply to take a snapshot of the >> existing block and edge frequencies along the path before we start the >> updates in ssa_fix_duplicate_block_edges, by copying them into the >> profile count fields of those blocks and edges. Then the existing >> algorithm operates the same as when we do have counts, and can >> essentially operate incrementally on the edge frequencies since they >> live in the count field of the edge and are no longer affected anytime >> the source block is updated. Since the algorithm does update block >> frequencies and probabilities as well (based on the count updates >> performed), we can simply clear out these fake count fields at the end >> of ssa_fix_duplicate_block_edges. This takes care of the remaining >> insanities introduced by jump threading from these test cases. During >> testing I also added in some checking to ensure that the count fields >> for the whole routine were cleared properly to make sure the new >> clear_counts_path was not missing anything (checking is a little too >> heavyweight to add in normally). >> >> New patch below (also attached since my mailer sometimes eats spaces). >> The differences between the old patch and the new one: >> - removed deduce_freq (which was my least favorite part of the patch >> anyway!), and its call from recompute_probabilities, since it is no >> longer necessary. >> - two new routines freqs_to_counts_path and clear_counts_path, invoked >> from ssa_fix_duplicate_block_edges. >> - two new tests >> >> Bootstrapped and tested on x86_64-unknown-linux-gnu, ok for trunk? >> >> Thanks, >> Teresa >> >> gcc: >> >> 2014-09-29 Teresa Johnson >> >> * tree-ssa-threadupdate.c (struct ssa_local_info_t): New >> duplicate_blocks bitmap. >> (remove_ctrl_stmt_and_useless_edges): Ditto. >> (create_block_for_threading): Ditto. >> (compute_path_counts): New function. >> (update_profile): Ditto. >> (recompute_probabilities): Ditto. >> (update_joiner_offpath_counts): Ditto. >> (freqs_to_counts_path): Ditto. >> (clear_counts_path): Ditto. >> (ssa_fix_duplicate_block_edges): Update profile info. >> (ssa_create_duplicates): Pass new parameter. >> (ssa_redirect_edges): Remove old profile update. >> (thread_block_1): New duplicate_blocks bitmap, >> remove old profile update. >> (thread_single_edge): Pass new parameter. >> >> gcc/testsuite: >> >> 2014-09-29 Teresa Johnson >> >> * testsuite/gcc.dg/tree-prof/20050826-2.c: New test. >> * testsuite/gcc.dg/tree-prof/cmpsf-1.c: Ditto. > > Given I'd already been through this pretty thoroughly, I just gave this a > cursory review. > > clear_counts_path needs a function comment. It's pretty obvious what it's > doing, but for completeness let's go ahead and get the obvious comment in > there. Done and committed as r215739. Thanks, Teresa > > With that fix, approved for the trunk. Thanks for taking the time to sort > out all these issues. > > jeff > > -- Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413