From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 9976 invoked by alias); 30 Sep 2014 04:33:53 -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 9967 invoked by uid 89); 30 Sep 2014 04:33:52 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.1 required=5.0 tests=AWL,BAYES_00,RP_MATCHES_RCVD,SPF_HELO_PASS,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Tue, 30 Sep 2014 04:33:51 +0000 Received: from int-mx10.intmail.prod.int.phx2.redhat.com (int-mx10.intmail.prod.int.phx2.redhat.com [10.5.11.23]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id s8U4XnAu002306 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL); Tue, 30 Sep 2014 00:33:49 -0400 Received: from stumpy.slc.redhat.com (ovpn-113-24.phx2.redhat.com [10.3.113.24]) by int-mx10.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id s8U4XlUw026958; Tue, 30 Sep 2014 00:33:48 -0400 Message-ID: <542A32AB.1040708@redhat.com> Date: Tue, 30 Sep 2014 04:33:00 -0000 From: Jeff Law User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.1.1 MIME-Version: 1.0 To: Teresa Johnson CC: "gcc-patches@gcc.gnu.org" , Jan Hubicka , David Li Subject: Re: [PATCH] Redesign jump threading profile updates References: <53CF1DFD.7080805@redhat.com> In-Reply-To: Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit X-IsSubscribed: yes X-SW-Source: 2014-09/txt/msg02601.txt.bz2 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. With that fix, approved for the trunk. Thanks for taking the time to sort out all these issues. jeff