From patchwork Sat Nov 21 08:27:39 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom de Vries X-Patchwork-Id: 547135 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 161911402CC for ; Sat, 21 Nov 2015 19:28:50 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=YMaAR9h3; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :subject:to:references:cc:from:message-id:date:mime-version :in-reply-to:content-type; q=dns; s=default; b=x6CbqNSbbisDHCZ2k 2wQ9fpBKKg+AO1+mlTZFUue4HQiPjbKDWDyIOgw91zWNNfw9V0zH+/RfCYmEP+wE Cf6MMTRvHKYwzG2WFSvOazmjJ+IDh5nDKvO9tdC33f48eI/Lv9RX2WZErmTHF6YQ kTJ0rmFKNDnZXIWtQVbt/4Ki6c= 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 :subject:to:references:cc:from:message-id:date:mime-version :in-reply-to:content-type; s=default; bh=1VxAHp0qKL8yqYUXu/aqYm8 rhA4=; b=YMaAR9h3csU4PB9ODWxl3vZyIQ8BHxxVBBrpGMV5zO9E3/J9pRiUpGe dlXtZnL0d9J/IpAmEXBRbVR0KWP0JD9sHUTbp5bDZZnNQnWUK61t5v+uLDBceiLx tHnWkMRTHxF5hZYNV7fD3vPUteJ1mCNPPy/9f3QAcoFowPzAc+BE= Received: (qmail 64308 invoked by alias); 21 Nov 2015 08:28: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 64283 invoked by uid 89); 21 Nov 2015 08:28:40 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.3 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD, SPF_PASS autolearn=ham version=3.3.2 X-HELO: fencepost.gnu.org Received: from fencepost.gnu.org (HELO fencepost.gnu.org) (208.118.235.10) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Sat, 21 Nov 2015 08:28:37 +0000 Received: from eggs.gnu.org ([2001:4830:134:3::10]:47961) by fencepost.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1a03X9-000505-9l for gcc-patches@gnu.org; Sat, 21 Nov 2015 03:28:35 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1a03X3-0002wW-MP for gcc-patches@gnu.org; Sat, 21 Nov 2015 03:28:34 -0500 Received: from relay1.mentorg.com ([192.94.38.131]:44597) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1a03X3-0002wO-Dh for gcc-patches@gnu.org; Sat, 21 Nov 2015 03:28:29 -0500 Received: from nat-ies.mentorg.com ([192.94.31.2] helo=SVR-IES-FEM-01.mgc.mentorg.com) by relay1.mentorg.com with esmtp id 1a03X0-00015N-CM from Tom_deVries@mentor.com ; Sat, 21 Nov 2015 00:28:26 -0800 Received: from [127.0.0.1] (137.202.0.76) by SVR-IES-FEM-01.mgc.mentorg.com (137.202.0.104) with Microsoft SMTP Server id 14.3.224.2; Sat, 21 Nov 2015 08:28:24 +0000 Subject: Re: [PATCH, 10/16] Add pass_oacc_kernels pass group in passes.def To: Richard Biener References: <5640BD31.2060602@mentor.com> <5640FB07.6010008@mentor.com> <5649C41A.40403@mentor.com> <564A64B3.7080305@mentor.com> <564B3F69.50600@mentor.com> <564D1930.8040104@mentor.com> CC: Richard Biener , "gcc-patches@gnu.org" , Jakub Jelinek From: Tom de Vries Message-ID: <56502AFB.8050105@mentor.com> Date: Sat, 21 Nov 2015 09:27:39 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.3.0 MIME-Version: 1.0 In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Windows NT kernel [generic] [fuzzy] X-Received-From: 192.94.38.131 On 20/11/15 11:28, Richard Biener wrote: > On Thu, 19 Nov 2015, Tom de Vries wrote: > >> >On 17/11/15 15:53, Tom de Vries wrote: >>>> > > >And the above LIM example >>>> > > >is none for why you need two LIM passes... >>> > > >>> > >Indeed. I'm planning a separate reply to explain in more detail the need >>> > >for the two pass_lims. >> > >> >I. >> > >> >I managed to get rid of the two pass_lims for the motivating example that I >> >used until now (goacc/kernels-double-reduction.c). I found that by adding a >> >pass_dominator instance after pass_ch, I could get rid of the second pass_lim >> >(and pass_copyprop as well). >> > >> >But... then I wrote a counter example (goacc/kernels-double-reduction-n.c), >> >and I'm back at two pass_lims (and two pass_dominators). >> >Also I've split the pass group into a bit before and after pass_fre. >> > >> >So, the current pass group looks like: >> >... >> >NEXT_PASS (pass_build_ealias); >> > >> >/* Pass group that runs when the function is an offloaded function >> > containing oacc kernels loops. Part 1. */ >> >NEXT_PASS (pass_oacc_kernels); >> >PUSH_INSERT_PASSES_WITHIN (pass_oacc_kernels) >> > /* We need pass_ch here, because pass_lim has no effect on >> > exit-first loops (PR65442). Ideally we want to remove both >> > this pass instantiation, and the reverse transformation >> > transform_to_exit_first_loop_alt, which is done in >> > pass_parallelize_loops_oacc_kernels. */ >> > NEXT_PASS (pass_ch); >> >POP_INSERT_PASSES () >> > >> >NEXT_PASS (pass_fre); >> > >> >/* Pass group that runs when the function is an offloaded function >> > containing oacc kernels loops. Part 2. */ >> >NEXT_PASS (pass_oacc_kernels2); >> >PUSH_INSERT_PASSES_WITHIN (pass_oacc_kernels2) >> > /* We use pass_lim to rewrite in-memory iteration and reduction >> > variable accesses in loops into local variables accesses. */ >> > NEXT_PASS (pass_lim); >> > NEXT_PASS (pass_dominator, false /* may_peel_loop_headers_p */); >> > NEXT_PASS (pass_lim); >> > NEXT_PASS (pass_dominator, false /* may_peel_loop_headers_p */); >> > NEXT_PASS (pass_dce); >> > NEXT_PASS (pass_parallelize_loops_oacc_kernels); >> > NEXT_PASS (pass_expand_omp_ssa); >> >POP_INSERT_PASSES () >> >NEXT_PASS (pass_merge_phi); >> >... >> > >> > >> >II. >> > >> >The motivating test-case kernels-double-reduction-n.c: >> >... >> >#include >> > >> >#define N 500 >> > >> >unsigned int a[N][N]; >> > >> >void __attribute__((noinline,noclone)) >> >foo (unsigned int n) >> >{ >> > int i, j; >> > unsigned int sum = 1; >> > >> >#pragma acc kernels copyin (a[0:n]) copy (sum) >> > { >> > for (i = 0; i < n; ++i) >> > for (j = 0; j < n; ++j) >> > sum += a[i][j]; >> > } >> > >> > if (sum != 5001) >> > abort (); >> >} >> >... >> > >> > >> >III. >> > >> >Before first pass_lim. Note no phis on inner or outer loop header for >> >iteration varables or reduction variable: >> >... >> > : >> > _5 = *.omp_data_i_4(D).i; >> > *_5 = 0; >> > _44 = *.omp_data_i_4(D).n; >> > _45 = *_44; >> > if (_45 != 0) >> > goto ; >> > else >> > goto ; >> > >> > : outer loop header >> > _12 = *.omp_data_i_4(D).j; >> > *_12 = 0; >> > if (_45 != 0) >> > goto ; >> > else >> > goto ; >> > >> > : inner loop header, latch >> > _19 = *.omp_data_i_4(D).a; >> > _21 = *_5; >> > _23 = *_12; >> > _24 = *_19[_21][_23]; >> > _25 = *.omp_data_i_4(D).sum; >> > sum.0_26 = *_25; >> > sum.1_27 = _24 + sum.0_26; >> > *_25 = sum.1_27; >> > _33 = _23 + 1; >> > *_12 = _33; >> > j.2_16 = (unsigned int) _33; >> > if (j.2_16 < _45) >> > goto ; >> > else >> > goto ; >> > >> > : outer loop latch >> > _36 = *_5; >> > _38 = _36 + 1; >> > *_5 = _38; >> > i.3_9 = (unsigned int) _38; >> > if (i.3_9 < _45) >> > goto ; >> > else >> > goto ; >> > >> > : >> > return; >> >... >> > >> > >> >IV. >> > >> >After first pass_lim/pass_dom pair. Note there are phis on the inner loop >> >header for the reduction and the iteration variable, but not on the outer loop >> >header: >> >... >> > : >> > _5 = *.omp_data_i_4(D).i; >> > *_5 = 0; >> > _44 = *.omp_data_i_4(D).n; >> > _45 = *_44; >> > if (_45 != 0) >> > goto ; >> > else >> > goto ; >> > >> > : >> > _12 = *.omp_data_i_4(D).j; >> > _19 = *.omp_data_i_4(D).a; >> > D__lsm.10_50 = *_12; >> > D__lsm.11_51 = 0; >> > _25 = *.omp_data_i_4(D).sum; >> > >> > : outer loop header >> > D__lsm.10_20 = 0; >> > D__lsm.11_22 = 1; >> > _21 = *_5; >> > D__lsm.12_28 = *_25; >> > D__lsm.13_30 = 0; >> > goto ; >> > >> > : inner loop header, latch >> > # D__lsm.10_47 = PHI <0(5), _33(7)> >> > # D__lsm.12_49 = PHI >> > _23 = D__lsm.10_47; >> > _24 = *_19[_21][D__lsm.10_47]; >> > sum.0_26 = D__lsm.12_49; >> > sum.1_27 = _24 + D__lsm.12_49; >> > D__lsm.12_31 = sum.1_27; >> > D__lsm.13_32 = 1; >> > _33 = D__lsm.10_47 + 1; >> > D__lsm.10_14 = _33; >> > D__lsm.11_15 = 1; >> > j.2_16 = (unsigned int) _33; >> > if (j.2_16 < _45) >> > goto ; >> > else >> > goto ; >> > >> > : outer loop latch >> > # D__lsm.10_35 = PHI <_33(7)> >> > # D__lsm.11_37 = PHI <1(7)> >> > # D__lsm.12_7 = PHI >> > # D__lsm.13_8 = PHI <1(7)> >> > *_25 = sum.1_27; >> > _36 = *_5; >> > _38 = _36 + 1; >> > *_5 = _38; >> > i.3_9 = (unsigned int) _38; >> > if (i.3_9 < _45) >> > goto ; >> > else >> > goto ; >> > >> > : >> > # D__lsm.10_10 = PHI <_33(8)> >> > # D__lsm.11_11 = PHI <1(8)> >> > *_12 = _33; >> > goto ; >> > >> > : >> > return; >> >... >> > >> > >> >V. >> > >> >After second pass_lim/pass_dom pair. Note there are phis on the inner and >> >outer loop header for the reduction and the iteration variables: >> >... >> > : >> > _5 = *.omp_data_i_4(D).i; >> > *_5 = 0; >> > _44 = *.omp_data_i_4(D).n; >> > _45 = *_44; >> > if (_45 != 0) >> > goto ; >> > else >> > goto ; >> > >> > : >> > _12 = *.omp_data_i_4(D).j; >> > _19 = *.omp_data_i_4(D).a; >> > D__lsm.10_50 = *_12; >> > D__lsm.11_51 = 0; >> > _25 = *.omp_data_i_4(D).sum; >> > D__lsm.14_40 = 0; >> > D__lsm.15_2 = 0; >> > D__lsm.16_1 = *_25; >> > D__lsm.17_46 = 0; >> > >> > : outer loop header >> > # D__lsm.14_13 = PHI <0(4), _38(8)> >> > # D__lsm.16_34 = PHI >> > D__lsm.10_20 = 0; >> > D__lsm.11_22 = 1; >> > _21 = D__lsm.14_13; >> > D__lsm.12_28 = D__lsm.16_34; >> > D__lsm.13_30 = 0; >> > goto ; >> > >> > : inner loop header, latch >> > # D__lsm.10_47 = PHI <0(5), _33(7)> >> > # D__lsm.12_49 = PHI >> > _23 = D__lsm.10_47; >> > _24 = *_19[D__lsm.14_13][D__lsm.10_47]; >> > sum.0_26 = D__lsm.12_49; >> > sum.1_27 = _24 + D__lsm.12_49; >> > D__lsm.12_31 = sum.1_27; >> > D__lsm.13_32 = 1; >> > _33 = D__lsm.10_47 + 1; >> > D__lsm.10_14 = _33; >> > D__lsm.11_15 = 1; >> > j.2_16 = (unsigned int) _33; >> > if (j.2_16 < _45) >> > goto ; >> > else >> > goto ; >> > >> > : outer loop latch >> > # D__lsm.10_35 = PHI <_33(7)> >> > # D__lsm.11_37 = PHI <1(7)> >> > # D__lsm.12_7 = PHI >> > # D__lsm.13_8 = PHI <1(7)> >> > # sum.1_48 = PHI >> > # _53 = PHI <_33(7)> >> > D__lsm.16_56 = sum.1_27; >> > D__lsm.17_57 = 1; >> > _36 = D__lsm.14_13; >> > _38 = D__lsm.14_13 + 1; >> > D__lsm.14_58 = _38; >> > D__lsm.15_59 = 1; >> > i.3_9 = (unsigned int) _38; >> > if (i.3_9 < _45) >> > goto ; >> > else >> > goto ; >> > >> > : >> > # D__lsm.10_10 = PHI <_33(8)> >> > # D__lsm.11_11 = PHI <1(8)> >> > # _43 = PHI <_33(8)> >> > # D__lsm.16_62 = PHI >> > # D__lsm.17_63 = PHI <1(8)> >> > # D__lsm.14_64 = PHI <_38(8)> >> > # D__lsm.15_65 = PHI <1(8)> >> > *_5 = _38; >> > *_25 = sum.1_27; >> > *_12 = _33; >> > goto ; >> > >> > : >> > return; >> >... > Sorry but staring at dumps doesn't make me understand the issue you > run into. Where can I reproduce this if I have time to look at this? I've posted the state of the patch series that reproduces this problem at https://github.com/vries/gcc/commits/vries/master-port-kernels-test-rb , run goacc.exp, testcase kernels-double-reduction-n.c. > From the dump below I understand you want no memory references in > the outer loop? > So the issue seems to be that store motion fails > to insert the preheader load / exit store to the outermost loop > possible and thus another LIM pass is needed to "store motion" those > again? Yep. > But a simple testcase > > int a; > int *p = &a; > int foo (int n) > { > for (int i = 0; i < n; ++i) > for (int j = 0; j < 100; ++j) > *p += j + i; > return a; > } > > shows that LIM can do this in one step. I've filed a FTR PR68465 - "pass_lim doesn't detect identical loop entry conditions" for a test-case where that doesn't happen (when using -fno-tree-dominator-opts). > Which means it should > be investigated why it doesn't do this properly for your testcase > (store motion of *_25). There seems to be two related problems: 1. the store has tree_could_trap_p (ref->mem.ref) true, which should be false. I'll work on a fix for this. 2. Give that the store can trap, I was running into PR68465. I managed to eliminate the 2nd pass_lim by moving the pass_dominator instance before the pass_lim instance. Attached patch shows the pass group with only one pass_lim. I hope to be able to eliminate the first pass_dominator instance before pass_lim once I fix 1. > Simply adding two LIM passes either papers over a wrong-code > bug (in LIM or in DOM) or over a missed-optimization in LIM. AFAIU now, it's PR68465, a missed optimization in LIM. Thanks, - Tom Add pass_oacc_kernels pass group in passes.def 2015-11-09 Tom de Vries * loop-init.c (loop_optimizer_init): If loops state doesn't need fixup, and requested flags are present in the loops state, don't reapply flags. * omp-low.c (pass_expand_omp_ssa::clone): New function. * passes.def: Add pass_oacc_kernels pass group. * tree-ssa-loop-ch.c (pass_ch::clone): New function. * tree-ssa-loop-im.c (tree_ssa_lim): Make static. (pass_lim::execute): Allow to run outside pass_tree_loop. --- gcc/loop-init.c | 11 ++++++++--- gcc/omp-low.c | 1 + gcc/passes.def | 24 ++++++++++++++++++++++++ gcc/tree-ssa-loop-ch.c | 2 ++ gcc/tree-ssa-loop-im.c | 4 +++- 5 files changed, 38 insertions(+), 4 deletions(-) diff --git a/gcc/loop-init.c b/gcc/loop-init.c index e32c94a..5bc0c54 100644 --- a/gcc/loop-init.c +++ b/gcc/loop-init.c @@ -103,7 +103,11 @@ loop_optimizer_init (unsigned flags) calculate_dominance_info (CDI_DOMINATORS); if (!needs_fixup) - checking_verify_loop_structure (); + { + checking_verify_loop_structure (); + if (loops_state_satisfies_p (flags)) + goto out; + } /* Clear all flags. */ if (recorded_exits) @@ -122,11 +126,12 @@ loop_optimizer_init (unsigned flags) /* Apply flags to loops. */ apply_loop_flags (flags); + checking_verify_loop_structure (); + + out: /* Dump loops. */ flow_loops_dump (dump_file, NULL, 1); - checking_verify_loop_structure (); - timevar_pop (TV_LOOP_INIT); } diff --git a/gcc/omp-low.c b/gcc/omp-low.c index 9c27396..d2f88b3 100644 --- a/gcc/omp-low.c +++ b/gcc/omp-low.c @@ -13385,6 +13385,7 @@ public: return !(fun->curr_properties & PROP_gimple_eomp); } virtual unsigned int execute (function *) { return execute_expand_omp (); } + opt_pass * clone () { return new pass_expand_omp_ssa (m_ctxt); } }; // class pass_expand_omp_ssa diff --git a/gcc/passes.def b/gcc/passes.def index 17027786..67f6829 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -88,7 +88,31 @@ along with GCC; see the file COPYING3. If not see /* pass_build_ealias is a dummy pass that ensures that we execute TODO_rebuild_alias at this point. */ NEXT_PASS (pass_build_ealias); + /* Pass group that runs when the function is an offloaded function + containing oacc kernels loops. Part 1. */ + NEXT_PASS (pass_oacc_kernels); + PUSH_INSERT_PASSES_WITHIN (pass_oacc_kernels) + /* We need pass_ch here, because pass_lim has no effect on + exit-first loops (PR65442). Ideally we want to remove both + this pass instantiation, and the reverse transformation + transform_to_exit_first_loop_alt, which is done in + pass_parallelize_loops_oacc_kernels. */ + NEXT_PASS (pass_ch); + NEXT_PASS (pass_dominator, false /* may_peel_loop_headers_p */); + POP_INSERT_PASSES () NEXT_PASS (pass_fre); + /* Pass group that runs when the function is an offloaded function + containing oacc kernels loops. Part 2. */ + NEXT_PASS (pass_oacc_kernels2); + PUSH_INSERT_PASSES_WITHIN (pass_oacc_kernels2) + /* We use pass_lim to rewrite in-memory iteration and reduction + variable accesses in loops into local variables accesses. */ + NEXT_PASS (pass_lim); + NEXT_PASS (pass_dominator, false /* may_peel_loop_headers_p */); + NEXT_PASS (pass_dce); + NEXT_PASS (pass_parallelize_loops_oacc_kernels); + NEXT_PASS (pass_expand_omp_ssa); + POP_INSERT_PASSES () NEXT_PASS (pass_merge_phi); NEXT_PASS (pass_dse); NEXT_PASS (pass_cd_dce); diff --git a/gcc/tree-ssa-loop-ch.c b/gcc/tree-ssa-loop-ch.c index 7e618bf..6493fcc 100644 --- a/gcc/tree-ssa-loop-ch.c +++ b/gcc/tree-ssa-loop-ch.c @@ -165,6 +165,8 @@ public: /* Initialize and finalize loop structures, copying headers inbetween. */ virtual unsigned int execute (function *); + opt_pass * clone () { return new pass_ch (m_ctxt); } + protected: /* ch_base method: */ virtual bool process_loop_p (struct loop *loop); diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c index 30b53ce..2435da6 100644 --- a/gcc/tree-ssa-loop-im.c +++ b/gcc/tree-ssa-loop-im.c @@ -2496,7 +2496,7 @@ tree_ssa_lim_finalize (void) /* Moves invariants from loops. Only "expensive" invariants are moved out -- i.e. those that are likely to be win regardless of the register pressure. */ -unsigned int +static unsigned int tree_ssa_lim (void) { unsigned int todo; @@ -2560,6 +2560,8 @@ public: unsigned int pass_lim::execute (function *fun) { + loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS); + if (number_of_loops (fun) <= 1) return 0;