From patchwork Wed Dec 17 09:47:36 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Bin.Cheng" X-Patchwork-Id: 422217 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id C2CF81400DD for ; Wed, 17 Dec 2014 20:47:50 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; q=dns; s=default; b=E1rPJoSV9u1WyOQHwG AzW+6/Mn0qoNyHOZ1ACi2Dkr09peCdVKE9m0kuKz8tmNkThyd4WQXHAPXX/7xhQi hCO+xsjNSdc3LtuTtNiWSw+qSOT16xn+2P7sTvDuSkC7fQ0ByMnV0OGT+/d1UUmg /adJYqoIK8uSu+/kfePVrWSE4= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; s=default; bh=2th+05MPRgQeo3x3O/g9Sk7R tNw=; b=u5w6dWX3x+EDnFStS+kKWpuB+5EFk1l1MrlcdwDKLKmfO2Lx/5V3BLZ8 +cJ8tv4e9bICSWmsAjcluQYBVewFU6mxNd1xbApnrYJuX5jjUi1W+mWc5sNXYp/V VV8hLJBtr4rjKzxUWwgul12O6WUhcDOSp+LKKCGacXPKP0HSJfw= Received: (qmail 2230 invoked by alias); 17 Dec 2014 09:47:41 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 2217 invoked by uid 89); 17 Dec 2014 09:47:40 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.2 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-oi0-f48.google.com Received: from mail-oi0-f48.google.com (HELO mail-oi0-f48.google.com) (209.85.218.48) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Wed, 17 Dec 2014 09:47:38 +0000 Received: by mail-oi0-f48.google.com with SMTP id u20so10757538oif.35 for ; Wed, 17 Dec 2014 01:47:36 -0800 (PST) MIME-Version: 1.0 X-Received: by 10.182.98.197 with SMTP id ek5mr22436138obb.72.1418809656486; Wed, 17 Dec 2014 01:47:36 -0800 (PST) Received: by 10.76.153.130 with HTTP; Wed, 17 Dec 2014 01:47:36 -0800 (PST) In-Reply-To: References: <001001d01085$2a1e7bc0$7e5b7340$@arm.com> Date: Wed, 17 Dec 2014 17:47:36 +0800 Message-ID: Subject: Re: [PATCH PR62178]Improve candidate selecting in IVOPT, 2nd try. From: "Bin.Cheng" To: GCC Patches Cc: Zdenek Dvorak , Jeff Law , Sebastian Pop , Richard Biener X-IsSubscribed: yes On Tue, Dec 16, 2014 at 4:42 PM, Bin.Cheng wrote: > On Thu, Dec 11, 2014 at 8:08 PM, Richard Biener > wrote: >> On Thu, Dec 11, 2014 at 10:56 AM, Bin.Cheng wrote: >>> On Wed, Dec 10, 2014 at 9:47 PM, Richard Biener >>> wrote: >>>> On Fri, Dec 5, 2014 at 1:15 PM, Bin Cheng wrote: >>>>> Hi, >>>>> Though PR62178 is hidden by recent cost change in aarch64 backend, the ivopt >>>>> issue still exists. >>>>> >>>>> Current candidate selecting algorithm tends to select fewer candidates given >>>>> below reasons: >>>>> 1) to better handle loops with many induction uses but the best choice is >>>>> one generic basic induction variable; >>>>> 2) to keep compilation time low. >>>>> >>>>> One fundamental weakness of the strategy is the opposite situation can't be >>>>> handled properly sometimes. For these cases the best choice is each >>>>> induction variable has its own candidate. >>>>> This patch fixes the problem by shuffling candidate set after fix-point is >>>>> reached by current implementation. The reason why this strategy works is it >>>>> replaces candidate set by selecting local optimal candidate for some >>>>> induction uses, and the new candidate set (has lower cost) is exact what we >>>>> want in the mentioned case. Instrumentation data shows this can find better >>>>> candidates set for ~6% loops in spec2006 on x86_64, and ~4% on aarch64. >>>>> >>>>> This patch actually is extension to the first version patch posted at >>>>> https://gcc.gnu.org/ml/gcc-patches/2014-09/msg02620.html, that only adds >>>>> another selecting pass with special seed set (more or less like the shuffled >>>>> set in this patch). Data also confirms this patch can find optimal sets for >>>>> most loops found by the first one, as well as optimal sets for many new >>>>> loops. >>>>> >>>>> Bootstrap and test on x86_64, no regression on benchmarks. Bootstrap and >>>>> test on aarch64. >>>>> Since this patch only selects candidate set with lower cost, any regressions >>>>> revealed are latent bugs of other components in GCC. >>>>> I also collected GCC bootstrap time on x86_64, no regression either. >>>>> Is this OK? >>>> >>>> The algorithm seems to be quadratic in the number of IV candidates >>>> (at least): >>> Yes, I worried about that too, that's why I measured the bootstrap >>> time. One way is restrict this procedure one time for each loop. I >>> already tried that and it can capture +90% loops. Is this sounds >>> reasonable? >> >> Yes. That's my suggestion to handle it in the caller of try_improve_iv_set? >> >>> BTW, do we have some compilation time benchmarks for GCC? >> >> There are various testcases linked from PR47344, I don't remember >> any particular one putting load on IVOPTs (but I do remember seeing >> IVOPTs in the ~25% area in -ftime-report for some testcases). > Hi, I further refined the patch. Specifically, I factored out common code, improved comments, and restricted new code in several ways, for example, now iv_ca_replace runs exactly one time for each find_optimal_iv_set; iv_ca_replace only tries to replace one candidate in IVS each time and makes quick return if lower cost set is found; most importantly, iv_ca_replace now checks ALWAYS_PRUNE_CAND_SET_BOUND. The patch is simplified with these changes. As for compilation time, IVOPT isn't regressed obviously for the overloaded case I created, also regression in llvm compilation time benchmarks is gone. I think we could adapt data structure in IVOPT to make it faster, for example, record information in candidate about which uses are represented by each cand, sort candidates by cost for each iv use. I may do some refactor in next stage1. Bootstrap on x86_64, test ongoing. So OK if no regressions? Thanks, bin 2014-12-17 Bin Cheng PR tree-optimization/62178 * tree-ssa-loop-ivopts.c (cheaper_cost_with_cand): New function. (iv_ca_replace): New function. (try_improve_iv_set): New parameter try_replace_p. Break local optimal fixed-point by calling iv_ca_replace. (find_optimal_iv_set_1): Pass new argument to try_improve_iv_set. gcc/testsuite/ChangeLog 2014-12-17 Bin Cheng PR tree-optimization/62178 * gcc.target/aarch64/pr62178.c: New test. Index: gcc/testsuite/gcc.target/aarch64/pr62178.c =================================================================== --- gcc/testsuite/gcc.target/aarch64/pr62178.c (revision 0) +++ gcc/testsuite/gcc.target/aarch64/pr62178.c (revision 0) @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-O3" } */ + +int a[30 +1][30 +1], b[30 +1][30 +1], r[30 +1][30 +1]; + +void foo (void) { + int i, j, k; + + for ( i = 1; i <= 30; i++ ) + for ( j = 1; j <= 30; j++ ) { + r[i][j] = 0; + for(k = 1; k <= 30; k++ ) + r[i][j] += a[i][k]*b[k][j]; + } +} + +/* { dg-final { scan-assembler "ld1r\\t\{v\[0-9\]+\."} } */ Index: gcc/tree-ssa-loop-ivopts.c =================================================================== --- gcc/tree-ssa-loop-ivopts.c (revision 218200) +++ gcc/tree-ssa-loop-ivopts.c (working copy) @@ -5862,6 +5862,108 @@ iv_ca_prune (struct ivopts_data *data, struct iv_c return best_cost; } +/* Check if CAND_IDX is a candidate other than OLD_CAND and has + cheaper local cost for USE than BEST_CP. Return pointer to + the corresponding cost_pair, otherwise just return BEST_CP. */ + +static struct cost_pair* +cheaper_cost_with_cand (struct ivopts_data *data, struct iv_use *use, + unsigned int cand_idx, struct iv_cand *old_cand, + struct cost_pair *best_cp) +{ + struct iv_cand *cand; + struct cost_pair *cp; + + gcc_assert (old_cand != NULL && best_cp != NULL); + if (cand_idx == old_cand->id) + return best_cp; + + cand = iv_cand (data, cand_idx); + cp = get_use_iv_cost (data, use, cand); + if (cp != NULL && cheaper_cost_pair (cp, best_cp)) + return cp; + + return best_cp; +} + +/* Try breaking local optimal fixed-point for IVS by replacing candidates + which are used by more than one iv uses. For each of those candidates, + this function tries to represent iv uses under that candidate using + other ones with lower local cost, then tries to prune the new set. + If the new set has lower cost, It returns the new cost after recording + candidate replacement in list DELTA. */ + +static comp_cost +iv_ca_replace (struct ivopts_data *data, struct iv_ca *ivs, + struct iv_ca_delta **delta) +{ + bitmap_iterator bi, bj; + unsigned int i, j, k; + struct iv_use *use; + struct iv_cand *cand; + comp_cost orig_cost, acost; + struct iv_ca_delta *act_delta, *tmp_delta; + struct cost_pair *old_cp, *best_cp = NULL; + + *delta = NULL; + orig_cost = iv_ca_cost (ivs); + + EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi) + { + if (ivs->n_cand_uses[i] == 1 + || ivs->n_cand_uses[i] > ALWAYS_PRUNE_CAND_SET_BOUND) + continue; + + cand = iv_cand (data, i); + + act_delta = NULL; + /* Represent uses under current candidate using other ones with + lower local cost. */ + for (j = 0; j < ivs->upto; j++) + { + use = iv_use (data, j); + old_cp = iv_ca_cand_for_use (ivs, use); + + if (old_cp->cand != cand) + continue; + + best_cp = old_cp; + if (data->consider_all_candidates) + for (k = 0; k < n_iv_cands (data); k++) + best_cp = cheaper_cost_with_cand (data, use, k, + old_cp->cand, best_cp); + else + EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, k, bj) + best_cp = cheaper_cost_with_cand (data, use, k, + old_cp->cand, best_cp); + + if (best_cp == old_cp) + continue; + + act_delta = iv_ca_delta_add (use, old_cp, best_cp, act_delta); + } + /* No need for further prune. */ + if (!act_delta) + continue; + + /* Prune the new candidate set. */ + iv_ca_delta_commit (data, ivs, act_delta, true); + acost = iv_ca_prune (data, ivs, NULL, &tmp_delta); + iv_ca_delta_commit (data, ivs, act_delta, false); + act_delta = iv_ca_delta_join (act_delta, tmp_delta); + + if (compare_costs (acost, orig_cost) < 0) + { + *delta = act_delta; + return acost; + } + else + iv_ca_delta_free (&act_delta); + } + + return orig_cost; +} + /* Tries to extend the sets IVS in the best possible way in order to express the USE. If ORIGINALP is true, prefer candidates from the original set of IVs, otherwise favor important candidates not @@ -5995,10 +6097,13 @@ get_initial_solution (struct ivopts_data *data, bo return ivs; } -/* Tries to improve set of induction variables IVS. */ +/* Tries to improve set of induction variables IVS. TRY_REPLACE_P + points to a bool variable, this function tries to break local + optimal fixed-point by replacing candidates in IVS if it's true. */ static bool -try_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs) +try_improve_iv_set (struct ivopts_data *data, + struct iv_ca *ivs, bool *try_replace_p) { unsigned i, n_ivs; comp_cost acost, best_cost = iv_ca_cost (ivs); @@ -6042,7 +6147,20 @@ static bool /* Try removing the candidates from the set instead. */ best_cost = iv_ca_prune (data, ivs, NULL, &best_delta); - /* Nothing more we can do. */ + if (!best_delta && *try_replace_p) + { + *try_replace_p = false; + /* So far candidate selecting algorithm tends to choose fewer IVs + so that it can handle cases in which loops have many variables + but the best choice is often to use only one general biv. One + weakness is it can't handle opposite cases, in which different + candidates should be chosen with respect to each use. To solve + the problem, we replace candidates in a manner described by the + comments of iv_ca_replace, thus give general algorithm a chance + to break local optimal fixed-point in these cases. */ + best_cost = iv_ca_replace (data, ivs, &best_delta); + } + if (!best_delta) return false; } @@ -6061,6 +6179,7 @@ static struct iv_ca * find_optimal_iv_set_1 (struct ivopts_data *data, bool originalp) { struct iv_ca *set; + bool try_replace_p = true; /* Get the initial solution. */ set = get_initial_solution (data, originalp); @@ -6077,7 +6196,7 @@ find_optimal_iv_set_1 (struct ivopts_data *data, b iv_ca_dump (data, dump_file, set); } - while (try_improve_iv_set (data, set)) + while (try_improve_iv_set (data, set, &try_replace_p)) { if (dump_file && (dump_flags & TDF_DETAILS)) {