From patchwork Tue Oct 25 10:11:31 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 10697 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp916500wru; Tue, 25 Oct 2022 03:12:34 -0700 (PDT) X-Google-Smtp-Source: AMsMyM71rSroiPhgv/Gihx4PNm820zocUBCHIOuX8FRaWzPBrf/06ucWFq+Yj+o0Sqy660qx5jRC X-Received: by 2002:a17:906:dacd:b0:780:a90c:e144 with SMTP id xi13-20020a170906dacd00b00780a90ce144mr31551861ejb.153.1666692754029; Tue, 25 Oct 2022 03:12:34 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1666692754; cv=none; d=google.com; s=arc-20160816; b=LcuJeb7keuvXF+ZPFFXAZDDmSDE1iMqhYicOB9AT8FpGKn5oNEX4HFgR+ZUOdIYBiY eEEC7EFz9kNP565aNniDfOFaRlXWwCu80AZo6tPcvR6MGcAqEgfh19QfjMWV7+idDbur 641X4NBGMXqqoklOhEIX9sPcZVeKfk7mWEjZzPWqiA/7h4Vs4vhWa8BkwAQXuDpv+mFk VhQZ4JkvZlkaUpXEKnvt/oJ966j8M5GN9LGucSWE2gwNtBqeKaNy37rSm6ARtjBiCnj8 Tn3VLB62h0UrCWChGxQS2LOgAcdyknGK1ZefIFV+r11Rx2n7F0LgAQCrNuzmOyFK+tvA 51ww== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:cc:reply-to:from:list-subscribe:list-help :list-post:list-archive:list-unsubscribe:list-id:precedence :message-id:mime-version:subject:to:date:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=+z40w4vm7QqCixJSVWHSC8AVgZbKAFzolVt0zqO3TaY=; b=OBTb5mNc+YXFQsy4U5/dVmNyPTssoUp2Mnei7rXvR+2ddi5ZaiXnFaAiaS0RRmxHTI JzDV0iYgLbH+26sAm+cj12mvcn5pmo6KRRUa3Yv/vJ4FsJdXFznzXMvTV7Fi7uBdZkTn Vpk/hMZ1L473QKk/vzGJKncRHM3Uw1FyIez3r8j3n+dRTyPkhkTvHImRM72o8tIDi4jv 7ZqF1t+wYfwYSfsM5XuOl1d396mJh+sdeyk+M7kaQvWnbVz6EEN7v7UPZNeXfnwV+bs0 RUIuTvbfJ1L4IDq4Eoh21T7DqbJutZA1+PhyTcyf1F9IlqZG2M/bNcywcZA8mQCx3Ttb a1ag== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=Jg6ulwSP; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id cw22-20020a170906479600b0078d3b4510b5si2879094ejc.854.2022.10.25.03.12.33 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 25 Oct 2022 03:12:34 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=Jg6ulwSP; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B648E3857367 for ; Tue, 25 Oct 2022 10:12:26 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B648E3857367 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1666692746; bh=+z40w4vm7QqCixJSVWHSC8AVgZbKAFzolVt0zqO3TaY=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=Jg6ulwSPcdOYqM5RIK9UNMsaznmMDN8kbsTnFON3pAFENNzvUrtnRTbGOqyGVFmR8 n8lm0iaudKJ2pyqnljT8aU1zK6D9Iext4fgjcbb56MSzuMt4Oc/Ny9n/fOirukICqE FBf0Ze+UVGotWacLeCbRWhD4zeHrONa0NBwx+DZU= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id 5572E3857BB8 for ; Tue, 25 Oct 2022 10:11:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 5572E3857BB8 Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 6BA9A21F3F; Tue, 25 Oct 2022 10:11:32 +0000 (UTC) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 58E5F13A64; Tue, 25 Oct 2022 10:11:32 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id Re/pFFS2V2M2VAAAMHmgww (envelope-from ); Tue, 25 Oct 2022 10:11:32 +0000 Date: Tue, 25 Oct 2022 12:11:31 +0200 (CEST) To: gcc-patches@gcc.gnu.org Subject: [PATCH] tree-optimization/107176 - SCEV analysis association issue MIME-Version: 1.0 Message-Id: <20221025101132.58E5F13A64@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-10.5 required=5.0 tests=BAYES_00, DKIM_INVALID, DKIM_SIGNED, GIT_PATCH_0, KAM_DMARC_STATUS, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener Cc: sebpop@gmail.com Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1747654021189637122?= X-GMAIL-MSGID: =?utf-8?q?1747654021189637122?= The following fixes a wrong-code issue caused by SCEV analysis associating an addition due trying to use tail-recursion in follow_ssa_edge_expr. That causes us to apply a conversion at the wrong point and thus miscompute the scalar evolution of an induction variable. This reverts the PR66375 fix and revisits the PR42512 fix by keeping the evolution symbolic up to the point we process the first linear function when we then can check for the supported cases and substitute the whole symbolic expression with the built chrec substituting the proper initial value. To simplify passing around things and to clarify scoping of the involved functions this change wraps the SCEV DFS walking code into a class. Bootstrapped and tested on x86_64-unknown-linux-gnu, I'm doing final testing on the following which includes some API streamlining over the tested prototype. PR tree-optimization/107176 PR tree-optimization/66375 PR tree-optimization/42512 * tree-scalar-evolution.cc (follow_ssa_edge_expr): Revert the PR66375 fix, do not not associate PLUS_EXPR to be able to use tail-recursion. (follow_ssa_edge_binary): Likewise. (interpret_loop_phi): Revert PR42512 fix, do not throw away analyze_evolution_in_loop result after the fact. (follow_ssa_edge_expr): When reaching halting_phi initalize the evolution to the symbolic value of the PHI result. (add_to_evolution_1): When adding the first evolution verify we can handle the expression wrapping the symbolic evolution and replace that in full using the initial condition. (class scev_dfs): New, contains ... (follow_ssa_edge_expr, follow_ssa_edge_binary, follow_ssa_edge_in_condition_phi_branch, follow_ssa_edge_in_condition_phi, follow_ssa_edge_inner_loop_phi, add_to_evolution, add_to_evolution_1): ... these with loop and halting_phi arguments in class data. (scev_dfs::get_ev): New toplevel DFS entry, start with a chrec_dont_know evolution. (analyze_evolution_in_loop): Use scev_dfs. * gcc.dg/torture/pr107176.c: New testcase. --- gcc/testsuite/gcc.dg/torture/pr107176.c | 22 ++ gcc/tree-scalar-evolution.cc | 320 ++++++++++++------------ 2 files changed, 185 insertions(+), 157 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/torture/pr107176.c diff --git a/gcc/testsuite/gcc.dg/torture/pr107176.c b/gcc/testsuite/gcc.dg/torture/pr107176.c new file mode 100644 index 00000000000..c4f7b6d7336 --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/pr107176.c @@ -0,0 +1,22 @@ +/* { dg-do run } */ + +__INT32_TYPE__ a; +__INT64_TYPE__ b; +static inline __INT64_TYPE__ c(__UINT32_TYPE__ d) +{ + return d; +} +static inline void e(__INT32_TYPE__ d) +{ + a = d; +} +int main() +{ + b = 0; + for (; b < 1; b = c(b - 90) + 90 + 1) + ; + e(b >> 2); + if (a != 1073741824) + __builtin_abort(); + return 0; +} diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc index 8b927094324..7e2a3e98661 100644 --- a/gcc/tree-scalar-evolution.cc +++ b/gcc/tree-scalar-evolution.cc @@ -577,6 +577,51 @@ get_scalar_evolution (basic_block instantiated_below, tree scalar) return res; } + +/* Depth first search algorithm. */ + +enum t_bool { + t_false, + t_true, + t_dont_know +}; + +class scev_dfs +{ +public: + scev_dfs (class loop *loop_, gphi *phi_, tree init_cond_) + : loop (loop_), loop_phi_node (phi_), init_cond (init_cond_) {} + t_bool get_ev (tree *, tree); + +private: + t_bool follow_ssa_edge_expr (gimple *, tree, tree *, int); + t_bool follow_ssa_edge_binary (gimple *at_stmt, + tree type, tree rhs0, enum tree_code code, + tree rhs1, tree *evolution_of_loop, int limit); + t_bool follow_ssa_edge_in_condition_phi_branch (int i, + gphi *condition_phi, + tree *evolution_of_branch, + tree init_cond, int limit); + t_bool follow_ssa_edge_in_condition_phi (gphi *condition_phi, + tree *evolution_of_loop, int limit); + t_bool follow_ssa_edge_inner_loop_phi (gphi *loop_phi_node, + tree *evolution_of_loop, int limit); + tree add_to_evolution (tree chrec_before, enum tree_code code, + tree to_add, gimple *at_stmt); + tree add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt); + + class loop *loop; + gphi *loop_phi_node; + tree init_cond; +}; + +t_bool +scev_dfs::get_ev (tree *ev_fn, tree arg) +{ + *ev_fn = chrec_dont_know; + return follow_ssa_edge_expr (loop_phi_node, arg, ev_fn, 0); +} + /* Helper function for add_to_evolution. Returns the evolution function for an assignment of the form "a = b + c", where "a" and "b" are on the strongly connected component. CHREC_BEFORE is the @@ -587,12 +632,12 @@ get_scalar_evolution (basic_block instantiated_below, tree scalar) evolution the expression TO_ADD, otherwise construct an evolution part for this loop. */ -static tree -add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add, - gimple *at_stmt) +tree +scev_dfs::add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt) { tree type, left, right; - class loop *loop = get_loop (cfun, loop_nb), *chloop; + unsigned loop_nb = loop->num; + class loop *chloop; switch (TREE_CODE (chrec_before)) { @@ -631,7 +676,7 @@ add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add, gcc_assert (flow_loop_nested_p (loop, chloop)); /* Search the evolution in LOOP_NB. */ - left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), + left = add_to_evolution_1 (CHREC_LEFT (chrec_before), to_add, at_stmt); right = CHREC_RIGHT (chrec_before); right = chrec_convert_rhs (chrec_type (left), right, at_stmt); @@ -646,6 +691,17 @@ add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add, left = chrec_before; right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt); + /* When we add the first evolution we need to replace the symbolic + evolution we've put in when the DFS reached the loop PHI node + with the initial value. There's only a limited cases of + extra operations ontop of that symbol allowed, namely + sign-conversions we can look through. For other cases we leave + the symbolic initial condition which causes build_polynomial_chrec + to return chrec_dont_know. See PR42512, PR66375 and PR107176 for + cases we mishandled before. */ + STRIP_NOPS (chrec_before); + if (chrec_before == gimple_phi_result (loop_phi_node)) + left = fold_convert (TREE_TYPE (left), init_cond); return build_polynomial_chrec (loop_nb, left, right); } } @@ -784,9 +840,9 @@ add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add, */ -static tree -add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code, - tree to_add, gimple *at_stmt) +tree +scev_dfs::add_to_evolution (tree chrec_before, enum tree_code code, + tree to_add, gimple *at_stmt) { tree type = chrec_type (to_add); tree res = NULL_TREE; @@ -803,7 +859,7 @@ add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code, if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, "(add_to_evolution \n"); - fprintf (dump_file, " (loop_nb = %d)\n", loop_nb); + fprintf (dump_file, " (loop_nb = %d)\n", loop->num); fprintf (dump_file, " (chrec_before = "); print_generic_expr (dump_file, chrec_before); fprintf (dump_file, ")\n (to_add = "); @@ -816,7 +872,7 @@ add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code, ? build_real (type, dconstm1) : build_int_cst_type (type, -1)); - res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt); + res = add_to_evolution_1 (chrec_before, to_add, at_stmt); if (dump_file && (dump_flags & TDF_SCEV)) { @@ -828,64 +884,14 @@ add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code, return res; } - - -/* This section selects the loops that will be good candidates for the - scalar evolution analysis. For the moment, greedily select all the - loop nests we could analyze. */ - -/* For a loop with a single exit edge, return the COND_EXPR that - guards the exit edge. If the expression is too difficult to - analyze, then give up. */ - -gcond * -get_loop_exit_condition (const class loop *loop) -{ - gcond *res = NULL; - edge exit_edge = single_exit (loop); - - if (dump_file && (dump_flags & TDF_SCEV)) - fprintf (dump_file, "(get_loop_exit_condition \n "); - - if (exit_edge) - { - gimple *stmt; - - stmt = last_stmt (exit_edge->src); - if (gcond *cond_stmt = safe_dyn_cast (stmt)) - res = cond_stmt; - } - - if (dump_file && (dump_flags & TDF_SCEV)) - { - print_gimple_stmt (dump_file, res, 0); - fprintf (dump_file, ")\n"); - } - - return res; -} - - -/* Depth first search algorithm. */ - -enum t_bool { - t_false, - t_true, - t_dont_know -}; - - -static t_bool follow_ssa_edge_expr (class loop *loop, gimple *, tree, gphi *, - tree *, int); /* Follow the ssa edge into the binary expression RHS0 CODE RHS1. Return true if the strongly connected component has been found. */ -static t_bool -follow_ssa_edge_binary (class loop *loop, gimple *at_stmt, - tree type, tree rhs0, enum tree_code code, tree rhs1, - gphi *halting_phi, tree *evolution_of_loop, - int limit) +t_bool +scev_dfs::follow_ssa_edge_binary (gimple *at_stmt, tree type, tree rhs0, + enum tree_code code, tree rhs1, + tree *evolution_of_loop, int limit) { t_bool res = t_false; tree evol; @@ -907,23 +913,18 @@ follow_ssa_edge_binary (class loop *loop, gimple *at_stmt, limit++; evol = *evolution_of_loop; - evol = add_to_evolution - (loop->num, - chrec_convert (type, evol, at_stmt), - code, rhs1, at_stmt); - res = follow_ssa_edge_expr - (loop, at_stmt, rhs0, halting_phi, &evol, limit); + res = follow_ssa_edge_expr (at_stmt, rhs0, &evol, limit); if (res == t_true) - *evolution_of_loop = evol; + *evolution_of_loop = add_to_evolution + (chrec_convert (type, evol, at_stmt), code, rhs1, at_stmt); else if (res == t_false) { - *evolution_of_loop = add_to_evolution - (loop->num, - chrec_convert (type, *evolution_of_loop, at_stmt), - code, rhs0, at_stmt); res = follow_ssa_edge_expr - (loop, at_stmt, rhs1, halting_phi, - evolution_of_loop, limit); + (at_stmt, rhs1, evolution_of_loop, limit); + if (res == t_true) + *evolution_of_loop = add_to_evolution + (chrec_convert (type, *evolution_of_loop, at_stmt), + code, rhs0, at_stmt); } } @@ -935,13 +936,11 @@ follow_ssa_edge_binary (class loop *loop, gimple *at_stmt, { /* Match an assignment under the form: "a = ... + c". */ - *evolution_of_loop = add_to_evolution - (loop->num, chrec_convert (type, *evolution_of_loop, - at_stmt), - code, rhs0, at_stmt); - res = follow_ssa_edge_expr - (loop, at_stmt, rhs1, halting_phi, - evolution_of_loop, limit); + res = follow_ssa_edge_expr (at_stmt, rhs1, evolution_of_loop, limit); + if (res == t_true) + *evolution_of_loop = add_to_evolution + (chrec_convert (type, *evolution_of_loop, at_stmt), + code, rhs0, at_stmt); } else @@ -989,13 +988,11 @@ backedge_phi_arg_p (gphi *phi, int i) true if the strongly connected component has been found following this path. */ -static inline t_bool -follow_ssa_edge_in_condition_phi_branch (int i, - class loop *loop, - gphi *condition_phi, - gphi *halting_phi, - tree *evolution_of_branch, - tree init_cond, int limit) +t_bool +scev_dfs::follow_ssa_edge_in_condition_phi_branch (int i, + gphi *condition_phi, + tree *evolution_of_branch, + tree init_cond, int limit) { tree branch = PHI_ARG_DEF (condition_phi, i); *evolution_of_branch = chrec_dont_know; @@ -1008,7 +1005,7 @@ follow_ssa_edge_in_condition_phi_branch (int i, if (TREE_CODE (branch) == SSA_NAME) { *evolution_of_branch = init_cond; - return follow_ssa_edge_expr (loop, condition_phi, branch, halting_phi, + return follow_ssa_edge_expr (condition_phi, branch, evolution_of_branch, limit); } @@ -1025,17 +1022,14 @@ follow_ssa_edge_in_condition_phi_branch (int i, /* This function merges the branches of a condition-phi-node in a loop. */ -static t_bool -follow_ssa_edge_in_condition_phi (class loop *loop, - gphi *condition_phi, - gphi *halting_phi, - tree *evolution_of_loop, int limit) +t_bool +scev_dfs::follow_ssa_edge_in_condition_phi (gphi *condition_phi, + tree *evolution_of_loop, int limit) { int i, n; tree init = *evolution_of_loop; tree evolution_of_branch; - t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi, - halting_phi, + t_bool res = follow_ssa_edge_in_condition_phi_branch (0, condition_phi, &evolution_of_branch, init, limit); if (res == t_false || res == t_dont_know) @@ -1053,8 +1047,7 @@ follow_ssa_edge_in_condition_phi (class loop *loop, /* Increase the limit by the PHI argument number to avoid exponential time and memory complexity. */ - res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi, - halting_phi, + res = follow_ssa_edge_in_condition_phi_branch (i, condition_phi, &evolution_of_branch, init, limit + i); if (res == t_false || res == t_dont_know) @@ -1072,11 +1065,9 @@ follow_ssa_edge_in_condition_phi (class loop *loop, it follows the edges in the parent loop. The inner loop is considered as a single statement. */ -static t_bool -follow_ssa_edge_inner_loop_phi (class loop *outer_loop, - gphi *loop_phi_node, - gphi *halting_phi, - tree *evolution_of_loop, int limit) +t_bool +scev_dfs::follow_ssa_edge_inner_loop_phi (gphi *loop_phi_node, + tree *evolution_of_loop, int limit) { class loop *loop = loop_containing_stmt (loop_phi_node); tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node)); @@ -1096,9 +1087,8 @@ follow_ssa_edge_inner_loop_phi (class loop *outer_loop, /* Follow the edges that exit the inner loop. */ bb = gimple_phi_arg_edge (loop_phi_node, i)->src; if (!flow_bb_inside_loop_p (loop, bb)) - res = follow_ssa_edge_expr (outer_loop, loop_phi_node, - arg, halting_phi, - evolution_of_loop, limit); + res = follow_ssa_edge_expr (loop_phi_node, + arg, evolution_of_loop, limit); if (res == t_true) break; } @@ -1112,18 +1102,17 @@ follow_ssa_edge_inner_loop_phi (class loop *outer_loop, /* Otherwise, compute the overall effect of the inner loop. */ ev = compute_overall_effect_of_inner_loop (loop, ev); - return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi, - evolution_of_loop, limit); + return follow_ssa_edge_expr (loop_phi_node, ev, evolution_of_loop, limit); } /* Follow the ssa edge into the expression EXPR. Return true if the strongly connected component has been found. */ -static t_bool -follow_ssa_edge_expr (class loop *loop, gimple *at_stmt, tree expr, - gphi *halting_phi, tree *evolution_of_loop, - int limit) +t_bool +scev_dfs::follow_ssa_edge_expr (gimple *at_stmt, tree expr, + tree *evolution_of_loop, int limit) { + gphi *halting_phi = loop_phi_node; enum tree_code code; tree type, rhs0, rhs1 = NULL_TREE; @@ -1161,14 +1150,17 @@ tail_recurse: record their evolutions. Finally, merge the collected information and set the approximation to the main variable. */ - return follow_ssa_edge_in_condition_phi - (loop, phi, halting_phi, evolution_of_loop, limit); + return follow_ssa_edge_in_condition_phi (phi, evolution_of_loop, + limit); /* When the analyzed phi is the halting_phi, the depth-first search is over: we have found a path from the halting_phi to itself in the loop. */ if (phi == halting_phi) - return t_true; + { + *evolution_of_loop = expr; + return t_true; + } /* Otherwise, the evolution of the HALTING_PHI depends on the evolution of another loop-phi-node, i.e. the @@ -1179,9 +1171,8 @@ tail_recurse: /* Inner loop. */ if (flow_loop_nested_p (loop, def_loop)) - return follow_ssa_edge_inner_loop_phi - (loop, phi, halting_phi, evolution_of_loop, - limit + 1); + return follow_ssa_edge_inner_loop_phi (phi, evolution_of_loop, + limit + 1); /* Outer loop. */ return t_false; @@ -1239,7 +1230,7 @@ tail_recurse: CASE_CONVERT: { /* This assignment is under the form "a_1 = (cast) rhs. */ - t_bool res = follow_ssa_edge_expr (loop, at_stmt, rhs0, halting_phi, + t_bool res = follow_ssa_edge_expr (at_stmt, rhs0, evolution_of_loop, limit); *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt); return res; @@ -1268,18 +1259,18 @@ tail_recurse: && (TREE_CODE (rhs1) != SSA_NAME || code == MINUS_EXPR)) { /* Match an assignment under the form: - "a = b +- ...". - Use tail-recursion for the simple case. */ - *evolution_of_loop = add_to_evolution - (loop->num, chrec_convert (type, *evolution_of_loop, - at_stmt), - code, rhs1, at_stmt); - expr = rhs0; - goto tail_recurse; + "a = b +- ...". */ + t_bool res = follow_ssa_edge_expr (at_stmt, rhs0, + evolution_of_loop, limit); + if (res == t_true) + *evolution_of_loop = add_to_evolution + (chrec_convert (type, *evolution_of_loop, at_stmt), + code, rhs1, at_stmt); + return res; } /* Else search for the SCC in both rhs0 and rhs1. */ - return follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1, - halting_phi, evolution_of_loop, limit); + return follow_ssa_edge_binary (at_stmt, type, rhs0, code, rhs1, + evolution_of_loop, limit); case ASSERT_EXPR: /* This assignment is of the form: "a_1 = ASSERT_EXPR " @@ -1291,6 +1282,42 @@ tail_recurse: return t_false; } } + + +/* This section selects the loops that will be good candidates for the + scalar evolution analysis. For the moment, greedily select all the + loop nests we could analyze. */ + +/* For a loop with a single exit edge, return the COND_EXPR that + guards the exit edge. If the expression is too difficult to + analyze, then give up. */ + +gcond * +get_loop_exit_condition (const class loop *loop) +{ + gcond *res = NULL; + edge exit_edge = single_exit (loop); + + if (dump_file && (dump_flags & TDF_SCEV)) + fprintf (dump_file, "(get_loop_exit_condition \n "); + + if (exit_edge) + { + gimple *stmt; + + stmt = last_stmt (exit_edge->src); + if (gcond *cond_stmt = safe_dyn_cast (stmt)) + res = cond_stmt; + } + + if (dump_file && (dump_flags & TDF_SCEV)) + { + print_gimple_stmt (dump_file, res, 0); + fprintf (dump_file, ")\n"); + } + + return res; +} /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP. @@ -1381,7 +1408,7 @@ analyze_evolution_in_loop (gphi *loop_phi_node, for (i = 0; i < n; i++) { tree arg = PHI_ARG_DEF (loop_phi_node, i); - tree ev_fn; + tree ev_fn = chrec_dont_know; t_bool res; /* Select the edges that enter the loop body. */ @@ -1394,9 +1421,8 @@ analyze_evolution_in_loop (gphi *loop_phi_node, bool val = false; /* Pass in the initial condition to the follow edge function. */ - ev_fn = init_cond; - res = follow_ssa_edge_expr (loop, loop_phi_node, arg, - loop_phi_node, &ev_fn, 0); + scev_dfs dfs (loop, loop_phi_node, init_cond); + res = dfs.get_ev (&ev_fn, arg); /* If ev_fn has no evolution in the inner loop, and the init_cond is not equal to ev_fn, then we have an @@ -1551,7 +1577,6 @@ analyze_initial_condition (gphi *loop_phi_node) static tree interpret_loop_phi (class loop *loop, gphi *loop_phi_node) { - tree res; class loop *phi_loop = loop_containing_stmt (loop_phi_node); tree init_cond; @@ -1559,26 +1584,7 @@ interpret_loop_phi (class loop *loop, gphi *loop_phi_node) /* Otherwise really interpret the loop phi. */ init_cond = analyze_initial_condition (loop_phi_node); - res = analyze_evolution_in_loop (loop_phi_node, init_cond); - - /* Verify we maintained the correct initial condition throughout - possible conversions in the SSA chain. */ - if (res != chrec_dont_know) - { - tree new_init = res; - if (CONVERT_EXPR_P (res) - && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC) - new_init = fold_convert (TREE_TYPE (res), - CHREC_LEFT (TREE_OPERAND (res, 0))); - else if (TREE_CODE (res) == POLYNOMIAL_CHREC) - new_init = CHREC_LEFT (res); - STRIP_USELESS_TYPE_CONVERSION (new_init); - if (TREE_CODE (new_init) == POLYNOMIAL_CHREC - || !operand_equal_p (init_cond, new_init, 0)) - return chrec_dont_know; - } - - return res; + return analyze_evolution_in_loop (loop_phi_node, init_cond); } /* This function merges the branches of a condition-phi-node,