From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 93092 invoked by alias); 31 Jul 2015 11:17:29 -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 93083 invoked by uid 89); 31 Jul 2015 11:17:28 -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,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-oi0-f52.google.com Received: from mail-oi0-f52.google.com (HELO mail-oi0-f52.google.com) (209.85.218.52) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Fri, 31 Jul 2015 11:17:27 +0000 Received: by oigi136 with SMTP id i136so36419529oig.1 for ; Fri, 31 Jul 2015 04:17:25 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.202.172.70 with SMTP id v67mr2146403oie.51.1438341445198; Fri, 31 Jul 2015 04:17:25 -0700 (PDT) Received: by 10.202.106.145 with HTTP; Fri, 31 Jul 2015 04:17:25 -0700 (PDT) In-Reply-To: References: Date: Fri, 31 Jul 2015 12:07:00 -0000 Message-ID: Subject: Re: [PATCH] Unswitching outer loops. From: Yuri Rumyantsev To: Richard Biener Cc: gcc-patches , Igor Zamyatin Content-Type: text/plain; charset=UTF-8 X-SW-Source: 2015-07/txt/msg02661.txt.bz2 Hi Richard, I learned your updated patch for 23825 and it is more general in comparison with my. I'd like to propose you a compromise - let's consider my patch only for force-vectorize outer loop only to allow outer-loop vecctorization. Note that your approach will not hoist invariant guards if loops contains something else except for inner-loop, i.e. it won't be empty for taken branch. I also would like to answer on your last question - CFG cleanup is invoked to perform deletion of single-argument phi nodes from tail block through substitution - such phi's prevent outer-loop vectorization. But it is clear that such transformation can be done other pass. What is your opinion? Yuri. 2015-07-28 13:50 GMT+03:00 Richard Biener : > On Thu, Jul 23, 2015 at 4:45 PM, Yuri Rumyantsev wrote: >> Hi Richard, >> >> I checked that both test-cases from 23855 are sucessfully unswitched >> by proposed patch. I understand that it does not catch deeper loop >> nest as >> for (i=0; i<10; i++) >> for (j=0;j> for (k=0;k<20;k++) >> ... >> but duplication of middle-loop does not look reasonable. >> >> Here is dump for your second test-case: >> >> void foo(int *ie, int *je, double *x) >> { >> int i, j; >> for (j=0; j<*je; ++j) >> for (i=0; i<*ie; ++i) >> x[i+j] = 0.0; >> } >> grep -i unswitch t6.c.119t.unswitch >> ;; Unswitching outer loop > > I was saying that why go with a limited approach when a patch (in > unknown state...) > is available that does it more generally? Also unswitching is quite > expensive compared > to "moving" the invariant condition. > > In your patch: > > + if (!nloop->force_vectorize) > + nloop->force_vectorize = true; > + if (loop->safelen != 0) > + nloop->safelen = loop->safelen; > > I see no guard on force_vectorize so = true looks bogus here. Please just use > copy_loop_info. > > + if (integer_nonzerop (cond_new)) > + gimple_cond_set_condition_from_tree (cond_stmt, boolean_true_node); > + else if (integer_zerop (cond_new)) > + gimple_cond_set_condition_from_tree (cond_stmt, boolean_false_node); > > gimple_cond_make_true/false (cond_stmt); > > btw, seems odd that we have to recompute which loop is the true / false variant > when we just fed a guard condition to loop_version. Can't we statically > determine whether loop or nloop has the in-loop condition true or false? > > + /* Clean-up cfg to remove useless one-argument phi in exit block of > + outer-loop. */ > + cleanup_tree_cfg (); > > I know unswitching is already O(number-of-unswitched-loops * size-of-function) > because it updates SSA form after each individual unswitching (and it does that > because it invokes itself recursively on unswitched loops). But do you really > need to invoke CFG cleanup here? > > Richard. > >> Yuri. >> >> 2015-07-14 14:06 GMT+03:00 Richard Biener : >>> On Fri, Jul 10, 2015 at 12:02 PM, Yuri Rumyantsev wrote: >>>> Hi All, >>>> >>>> Here is presented simple transformation which tries to hoist out of >>>> outer-loop a check on zero trip count for inner-loop. This is very >>>> restricted transformation since it accepts outer-loops with very >>>> simple cfg, as for example: >>>> acc = 0; >>>> for (i = 1; i <= m; i++) { >>>> for (j = 0; j < n; j++) >>>> if (l[j] == i) { v[j] = acc; acc++; }; >>>> acc <<= 1; >>>> } >>>> >>>> Note that degenerative outer loop (without inner loop) will be >>>> completely deleted as dead code. >>>> The main goal of this transformation was to convert outer-loop to form >>>> accepted by outer-loop vectorization (such test-case is also included >>>> to patch). >>>> >>>> Bootstrap and regression testing did not show any new failures. >>>> >>>> Is it OK for trunk? >>> >>> I think this is >>> >>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=23855 >>> >>> as well. It has a patch adding a invariant loop guard hoisting >>> phase to loop-header copying. Yeah, it needs updating to >>> trunk again I suppose. It's always non-stage1 when I come >>> back to that patch. >>> >>> Your patch seems to be very specific and only handles outer >>> loops of innermost loops. >>> >>> Richard. >>> >>>> ChangeLog: >>>> 2015-07-10 Yuri Rumyantsev >>>> >>>> * tree-ssa-loop-unswitch.c: Include "tree-cfgcleanup.h" and >>>> "gimple-iterator.h", add prototype for tree_unswitch_outer_loop. >>>> (tree_ssa_unswitch_loops): Add invoke of tree_unswitch_outer_loop. >>>> (tree_unswitch_outer_loop): New function. >>>> >>>> gcc/testsuite/ChangeLog: >>>> * gcc.dg/tree-ssa/unswitch-outer-loop-1.c: New test. >>>> * gcc.dg/vect/vect-outer-simd-3.c: New test.