From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 27847 invoked by alias); 17 May 2019 04:17:14 -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 27836 invoked by uid 89); 17 May 2019 04:17:14 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-25.6 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_NONE,SPF_HELO_PASS,SPF_PASS autolearn=ham version=3.3.1 spammy=gate, 3956 X-HELO: NAM03-BY2-obe.outbound.protection.outlook.com Received: from mail-eopbgr780099.outbound.protection.outlook.com (HELO NAM03-BY2-obe.outbound.protection.outlook.com) (40.107.78.99) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 17 May 2019 04:17:12 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amperemail.onmicrosoft.com; s=selector2-amperemail-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=YeIQOqZh8S8Jd0hww+KlrmOIrpuLnQmiZzLQP2C4vMs=; b=2Iq76qnm8juIsbq8md/GBYxghp6qXivtrVWtg1z9H2hpTBKBV3JaFE3Yf1LGxhARghnQdvbxyFyua7vUCdBGdDV/sxWBPTCCOsnQuN2PqjXx1yqd7umNs7Txmm7DjrHB0KPL/pPI9zz7R4pKI99IaZLX68lZxhCvqI9DsimPzak= Received: from BYAPR01MB4869.prod.exchangelabs.com (20.177.228.18) by BYAPR01MB5079.prod.exchangelabs.com (20.177.184.152) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1900.18; Fri, 17 May 2019 04:17:08 +0000 Received: from BYAPR01MB4869.prod.exchangelabs.com ([fe80::9454:7630:22d5:a934]) by BYAPR01MB4869.prod.exchangelabs.com ([fe80::9454:7630:22d5:a934%7]) with mapi id 15.20.1900.010; Fri, 17 May 2019 04:17:08 +0000 From: Feng Xue OS To: "gcc-patches@gcc.gnu.org" CC: Feng Xue OS Subject: [PATCH] Remove empty loop with assumed finiteness (PR tree-optimization/89713) Date: Fri, 17 May 2019 04:17:00 -0000 Message-ID: authentication-results: spf=none (sender IP is ) smtp.mailfrom=fxue@os.amperecomputing.com; x-ms-oob-tlc-oobclassifiers: OLM:10000; received-spf: None (protection.outlook.com: os.amperecomputing.com does not designate permitted sender hosts) x-ms-exchange-senderadcheck: 1 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-SW-Source: 2019-05/txt/msg01027.txt.bz2 This patch is meant to give user a way to optimize away those empty loops w= hich are impossible to be recognized by compiler, such as C++ STL container= -based loop, void f (std::map &m) =A0 { =A0 =A0 for (auto it =3D m.begin (); it !=3D m.end (); ++it); =A0 } =20 An option "-ffinite-loop" is added to tell compiler about finiteness of loo= ps so that compiler can apply the optimization. Feng diff --git a/gcc/ChangeLog b/gcc/ChangeLog index d8bed3a..c55f2e6 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,18 @@ +2019-05-16 Feng Xue + + PR tree-optimization/89713 + * doc/invoke.texi (-ffinite-loop): Document new option. + * common.opt (-ffinite-loop): New option. + * passes.def: Replace pass_cd_dce with pass_cd_dce2. + * tree-pass.h (pass_cd_dce2): New declaration. + * tree-ssa-dce.c (loop_has_true_exits): New function. + (find_obviously_necessary_stmts): Add aggressive_loop_removal + parameter. + (perform_tree_ssa_dce, tree_ssa_cd_dce): Likewise. + (class pass_cd_dce): Add new member aggressive_loop_removal. + (pass_cd_dce::pass_cd_dce: Add alr parameter. + (make_pass_cd_dce2): New function. + 2019-05-16 Jakub Jelinek =20 PR c++/90484 diff --git a/gcc/common.opt b/gcc/common.opt index d342c4f..e98a34d 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -1437,6 +1437,10 @@ ffinite-math-only Common Report Var(flag_finite_math_only) Optimization SetByCombined Assume no NaNs or infinities are generated. =20 +ffinite-loop +Common Report Var(flag_finite_loop) Optimization +Assume loops are finite if can not be analytically determined. + ffixed- Common Joined RejectNegative Var(common_deferred_options) Defer -ffixed- Mark as being unavailable to the compiler. diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 5e3e887..9a3882c 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -412,6 +412,7 @@ Objective-C and Objective-C++ Dialects}. -fdevirtualize-at-ltrans -fdse @gol -fearly-inlining -fipa-sra -fexpensive-optimizations -ffat-lto-objects = @gol -ffast-math -ffinite-math-only -ffloat-store -fexcess-precision=3D@var{= style} @gol +-ffinite-loop @gol -fforward-propagate -ffp-contract=3D@var{style} -ffunction-sections @gol -fgcse -fgcse-after-reload -fgcse-las -fgcse-lm -fgraphite-identity @g= ol -fgcse-sm -fhoist-adjacent-loads -fif-conversion @gol @@ -9501,6 +9502,20 @@ that may set @code{errno} but are otherwise free of = side effects. This flag is enabled by default at @option{-O2} and higher if @option{-Os} is not also specified. =20 +@item -ffinite-loop +@opindex ffinite-loop +@opindex fno-finite-loop +Allow the compiler to assume that if finiteness of a loop can not be +analytically determined, the loop must be finite. With the assumption, some +aggressive transformation could be possible, such as removal of this kind +of empty loop by dead code elimination (DCE). + +This option is not turned on by any @option{-O} option since it might resu= lt +in incorrect behaviour for programs that contain seemly finite, but actual= ly +infinite loop. + +The default is @option{-fno-finite-loop}. + @item -ftree-dominator-opts @opindex ftree-dominator-opts Perform a variety of simple scalar cleanups (constant/copy diff --git a/gcc/passes.def b/gcc/passes.def index ad2efab..b84ee34 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -322,7 +322,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_copy_prop); NEXT_PASS (pass_warn_restrict); NEXT_PASS (pass_dse); - NEXT_PASS (pass_cd_dce); + NEXT_PASS (pass_cd_dce2); NEXT_PASS (pass_forwprop); NEXT_PASS (pass_phiopt, false /* early_p */); NEXT_PASS (pass_fold_builtins); diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 3a0b380..2392bc5 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -395,6 +395,7 @@ extern gimple_opt_pass *make_pass_build_ealias (gcc::co= ntext *ctxt); extern gimple_opt_pass *make_pass_dominator (gcc::context *ctxt); extern gimple_opt_pass *make_pass_dce (gcc::context *ctxt); extern gimple_opt_pass *make_pass_cd_dce (gcc::context *ctxt); +extern gimple_opt_pass *make_pass_cd_dce2 (gcc::context *ctxt); extern gimple_opt_pass *make_pass_call_cdce (gcc::context *ctxt); extern gimple_opt_pass *make_pass_merge_phi (gcc::context *ctxt); extern gimple_opt_pass *make_pass_thread_jumps (gcc::context *ctxt); diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c index 2478219..d4659df 100644 --- a/gcc/tree-ssa-dce.c +++ b/gcc/tree-ssa-dce.c @@ -356,6 +356,27 @@ mark_control_dependent_edges_necessary (basic_block bb= , bool ignore_self) bitmap_set_bit (visited_control_parents, bb->index); } =20 +/* Check whether a loop has any non-EH exit. */ + +static bool +loop_has_true_exits (const struct loop *loop) +{ + vec exits =3D get_loop_exit_edges (loop); + bool found =3D false; + edge e; + unsigned i; + + FOR_EACH_VEC_ELT (exits, i, e) + if (!(e->flags & EDGE_EH)) + { + found =3D true; + break; + } + + exits.release (); + return found; +} + =20 /* Find obviously necessary statements. These are things like most functi= on calls, and stores to file level variables. @@ -365,7 +386,7 @@ mark_control_dependent_edges_necessary (basic_block bb,= bool ignore_self) dependence analysis. */ =20 static void -find_obviously_necessary_stmts (bool aggressive) +find_obviously_necessary_stmts (bool aggressive, bool aggressive_loop_remo= val) { basic_block bb; gimple_stmt_iterator gsi; @@ -417,7 +438,8 @@ find_obviously_necessary_stmts (bool aggressive) } =20 FOR_EACH_LOOP (loop, 0) - if (!finite_loop_p (loop)) + if (!finite_loop_p (loop) + && (!aggressive_loop_removal || !loop_has_true_exits (loop))) { if (dump_file) fprintf (dump_file, "cannot prove finiteness of loop %i\n", loop->n= um); @@ -1532,6 +1554,8 @@ tree_dce_done (bool aggressive) /* Main routine to eliminate dead code. =20 AGGRESSIVE controls the aggressiveness of the algorithm. + If aggressive mode is on, AGGRESSIVE_LOOP_REMOVAL enables more aggressi= ve + removal of empty loop whose finiteness can not be statically determined. In conservative mode, we ignore control dependence and simply declare all but the most trivially dead branches necessary. This mode is fast. In aggressive mode, control dependences are taken into account, which @@ -1544,7 +1568,7 @@ tree_dce_done (bool aggressive) start experimenting with pass ordering. */ =20 static unsigned int -perform_tree_ssa_dce (bool aggressive) +perform_tree_ssa_dce (bool aggressive, bool aggressive_loop_removal =3D fa= lse) { bool something_changed =3D 0; =20 @@ -1576,7 +1600,7 @@ perform_tree_ssa_dce (bool aggressive) mark_dfs_back_edges (); } =20 - find_obviously_necessary_stmts (aggressive); + find_obviously_necessary_stmts (aggressive, aggressive_loop_removal); =20 if (aggressive && ! in_loop_pipeline) { @@ -1631,9 +1655,10 @@ tree_ssa_dce (void) } =20 static unsigned int -tree_ssa_cd_dce (void) +tree_ssa_cd_dce (bool aggressive_loop_removal) { - return perform_tree_ssa_dce (/*aggressive=3D*/optimize >=3D 2); + return perform_tree_ssa_dce (/*aggressive=3D*/optimize >=3D 2, + aggressive_loop_removal && flag_finite_loop= ); } =20 namespace { @@ -1690,15 +1715,20 @@ const pass_data pass_data_cd_dce =3D =20 class pass_cd_dce : public gimple_opt_pass { + bool aggressive_loop_removal; public: - pass_cd_dce (gcc::context *ctxt) + pass_cd_dce (gcc::context *ctxt, bool alr =3D false) : gimple_opt_pass (pass_data_cd_dce, ctxt) + , aggressive_loop_removal (alr) {} =20 /* opt_pass methods: */ opt_pass * clone () { return new pass_cd_dce (m_ctxt); } virtual bool gate (function *) { return flag_tree_dce !=3D 0; } - virtual unsigned int execute (function *) { return tree_ssa_cd_dce (); } + virtual unsigned int execute (function *) + { + return tree_ssa_cd_dce (aggressive_loop_removal); + } =20 }; // class pass_cd_dce =20 @@ -1710,6 +1740,12 @@ make_pass_cd_dce (gcc::context *ctxt) return new pass_cd_dce (ctxt); } =20 +gimple_opt_pass * +make_pass_cd_dce2 (gcc::context *ctxt) +{ + return new pass_cd_dce (ctxt, true); +} + =20 /* A cheap DCE interface. WORKLIST is a list of possibly dead stmts and is consumed by this function. The function has linear complexity in