From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 23717 invoked by alias); 2 Aug 2014 05:10:24 -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 23694 invoked by uid 89); 2 Aug 2014 05:10:22 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.2 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-yk0-f177.google.com Received: from mail-yk0-f177.google.com (HELO mail-yk0-f177.google.com) (209.85.160.177) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Sat, 02 Aug 2014 05:10:20 +0000 Received: by mail-yk0-f177.google.com with SMTP id 79so2938289ykr.22 for ; Fri, 01 Aug 2014 22:10:18 -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=8eOZMtr+55EIzPOdv8wTauNOrNfe/EkjNTrX5E8CgVk=; b=S94C39WfyVEvj+gGAM3q2iqH7PSH/hfPpOxgwGukxCFHtidgdFJHZXjS8YDbxKl/tf ESsngNznm+BIzoMO9ZKJzuM7ZwfdcUFk2mStpdpO1IQGQxieqimeYZMBtkAcNGUo4WBV TGKGRMfsHx5lPhY40je+tVb5Wl6VlJOP+27pqdoKgBS4rT3pqoAvhQTymiJsg72yndhP tKKQ8uGRgBy+4ZhUTO6u8J002mab54c4JXDXmR7gNOPwduvIQ7sNi0Rx5sXkJDdn9dJH Y9KdrDZeFTsWhaQHYWBLJjG0fZDiAh2X9wfpAyMP0vLuVevapc1NoNoonO+4n6PNmD0k eRCw== X-Gm-Message-State: ALoCoQn5cyjKFcAXGRubDnpmiYmbnA2XQSRImUFFTCoe2l6sLqbs7Nw/j1dRV3rVJnVwn0nL8aTS MIME-Version: 1.0 X-Received: by 10.236.61.225 with SMTP id w61mr14680591yhc.130.1406956218021; Fri, 01 Aug 2014 22:10:18 -0700 (PDT) Received: by 10.170.206.87 with HTTP; Fri, 1 Aug 2014 22:10:17 -0700 (PDT) In-Reply-To: References: <53CF1DFD.7080805@redhat.com> Date: Sat, 02 Aug 2014 05:10: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-08/txt/msg00114.txt.bz2 On Wed, Jul 23, 2014 at 2:08 PM, Teresa Johnson wrote: > On Tue, Jul 22, 2014 at 7:29 PM, Jeff Law wrote: >> On 03/26/14 17:44, Teresa Johnson wrote: >>> >>> Recently I discovered that the profile updates being performed by jump >>> threading were incorrect in many cases, particularly in the case where >>> the threading path contains a joiner. Some of the duplicated >>> blocks/edges were not getting any counts, leading to incorrect >>> function splitting and other downstream optimizations, and there were >>> other insanities as well. After making a few attempts to fix the >>> handling I ended up completely redesigning the profile update code, >>> removing a few places throughout the code where it was attempting to >>> do some updates. >>> >>> The biggest complication (see the large comment and example above the >>> new routine compute_path_counts) is that we duplicate a conditional >>> jump in the joiner case, possibly multiple times for multiple jump >>> thread paths through that joiner, and it isn't trivial to figure out >>> what probability to assign each of the duplicated successor edges (and >>> the original after threading). Each jump thread path may need to have >>> a different probability of staying on path through the joiner in order >>> to keep the counts going out of the threading path sane. >>> >>> The patch below was bootstrapped and tested on >>> x86_64-unknown-linux-gnu, and also tested with a profiledbootstrap. I >>> additionally tested with cpu2006, confirming that the amount of >>> resulting cycle samples in the split cold sections reduced, and >>> through manual inspection that many different cases were now correct. >>> I also measured performance with cpu2006, running each benchmark >>> multiple times on a Westmere and see some speedups (453.povray 1-2%, >>> 403.gcc 1-1.5%, and noisy but positive speedups in 471.omnetpp and >>> 483.xalancbmk). >>> >>> Looks like my mailer is corrupting the spacing, which makes it harder >>> to look at the CFG examples in the big header comment block I added. >>> So I have also included the patch as an attachment. >>> >>> Ok for stage 1? >>> >>> Thanks, >>> Teresa >>> >>> 2014-03-26 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. >>> (deduce_freq): Ditto. >>> (recompute_probabilities): Ditto. >>> (update_joiner_offpath_counts): 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. >> >> First off, sorry this took so long to get reviewed. >> >> Most of what's going on in here is similar to something I sketched out, but >> never coded up a while back -- with the significant difference that you're >> handling joiner blocks as well. >> >> Everything looks to be well thought through and documented in the code at a >> level I wish existed throughout GCC. >> >> The only thing I see missing is regression tests. I don't think you need to >> do anything huge here, but it ought to be possible to set up relatively >> simple cases which show the probabilities/counts being updated properly. >> >> Otherwise it looks excellent. It's pre-approved once you've added some kind >> of testing and fixed the nits noted below. > > Thanks! I will fix the issues you note below and create some test > cases before I commit. 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. Teresa > Teresa > >> >> >> >>> + In the aboe example, after all jump threading is complete, we will >> >> s/aboe/above/ >> >> >> >>> + struct el *next, *el; >>> + bitmap in_edge_srcs = BITMAP_ALLOC (NULL); >>> + for (el = rd->incoming_edges; el; el = next) >>> + { >>> + next = el->next; >>> + bitmap_set_bit (in_edge_srcs, el->e->src->index); >>> + } >> >> Please add vertical whitespace after this loop, but before declaring >> variables for the next loop. >> >> Jeff >> > > > > -- > Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413 -- Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413