From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1851) id DADA43857C75; Mon, 15 Nov 2021 14:23:55 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org DADA43857C75 Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Martin Liska To: gcc-cvs@gcc.gnu.org Subject: [gcc(refs/users/marxin/heads/loop-unswitch-improvement)] Support ranger in loop unswitching. X-Act-Checkin: gcc X-Git-Author: Martin Liska X-Git-Refname: refs/users/marxin/heads/loop-unswitch-improvement X-Git-Oldrev: abcac73a921e2c8422c85c20b02149d92511ec50 X-Git-Newrev: 8455c144912769dbd231bffcf99a0e9f6cbce274 Message-Id: <20211115142355.DADA43857C75@sourceware.org> Date: Mon, 15 Nov 2021 14:23:55 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 15 Nov 2021 14:23:56 -0000 https://gcc.gnu.org/g:8455c144912769dbd231bffcf99a0e9f6cbce274 commit 8455c144912769dbd231bffcf99a0e9f6cbce274 Author: Martin Liska Date: Mon Nov 15 14:22:52 2021 +0100 Support ranger in loop unswitching. Diff: --- gcc/testsuite/gcc.dg/loop-unswitch-8.c | 31 ++++++++++ gcc/tree-ssa-loop-unswitch.c | 110 ++++++++++++++++++++++----------- 2 files changed, 105 insertions(+), 36 deletions(-) diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-8.c b/gcc/testsuite/gcc.dg/loop-unswitch-8.c new file mode 100644 index 00000000000..37692966fc5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/loop-unswitch-8.c @@ -0,0 +1,31 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details" } */ + +int +foo(double *a, double *b, double *c, double *d, double *r, int size, int order) +{ + for (int i = 0; i < size; i++) + { + double tmp; + + if (order < 3) + tmp = -8 * a[i]; + else + tmp = -4 * b[i]; + + double x = 3 * tmp + d[i] + tmp; + + if (5 > order) + x += 2; + + if (order == 12345) + x *= 5; + + double y = 3.4f * tmp + d[i]; + r[i] = x + y; + } + + return 0; +} + +/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order" 1 "unswitch" } } */ diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c index d77914e2ba5..b3c18cc5817 100644 --- a/gcc/tree-ssa-loop-unswitch.c +++ b/gcc/tree-ssa-loop-unswitch.c @@ -37,6 +37,8 @@ along with GCC; see the file COPYING3. If not see #include "gimple-iterator.h" #include "cfghooks.h" #include "tree-ssa-loop-manip.h" +#include "tree-pretty-print.h" +#include "gimple-range.h" /* This file implements the loop unswitching, i.e. transformation of loops like @@ -74,9 +76,21 @@ along with GCC; see the file COPYING3. If not see tree-ssa-loop-im.c ensures that all the suitable conditions are in this shape. */ +struct unswitch_predicate +{ + /* Default constructor. */ + unswitch_predicate (tree cond) + : condition (cond), range () + {} + + tree condition; + int_range_max range; +}; + static class loop *tree_unswitch_loop (class loop *, basic_block, tree); -static bool tree_unswitch_single_loop (class loop *, int); -static tree tree_may_unswitch_on (basic_block, class loop *); +static bool tree_unswitch_single_loop (class loop *, int, gimple_ranger *); +static unswitch_predicate *tree_may_unswitch_on (basic_block, class loop *, + gimple_ranger *); static bool tree_unswitch_outer_loop (class loop *); static edge find_loop_guard (class loop *); static bool empty_bb_without_guard_p (class loop *, basic_block); @@ -92,16 +106,20 @@ tree_ssa_unswitch_loops (void) { bool changed = false; + gimple_ranger *ranger = enable_ranger (cfun); + /* Go through all loops starting from innermost. */ for (auto loop : loops_list (cfun, LI_FROM_INNERMOST)) { if (!loop->inner) /* Unswitch innermost loop. */ - changed |= tree_unswitch_single_loop (loop, 0); + changed |= tree_unswitch_single_loop (loop, 0, ranger); else changed |= tree_unswitch_outer_loop (loop); } + disable_ranger (cfun); + if (changed) return TODO_cleanup_cfg; return 0; @@ -182,10 +200,11 @@ is_maybe_undefined (const tree name, gimple *stmt, class loop *loop) } /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its - basic blocks (for what it means see comments below). */ + basic blocks (for what it means see comments below). + RANGER is gimple ranger used in this pass. */ -static tree -tree_may_unswitch_on (basic_block bb, class loop *loop) +static unswitch_predicate * +tree_may_unswitch_on (basic_block bb, class loop *loop, gimple_ranger *ranger) { gimple *last, *def; gcond *stmt; @@ -196,14 +215,14 @@ tree_may_unswitch_on (basic_block bb, class loop *loop) /* BB must end in a simple conditional jump. */ last = last_stmt (bb); if (!last || gimple_code (last) != GIMPLE_COND) - return NULL_TREE; + return NULL; stmt = as_a (last); /* To keep the things simple, we do not directly remove the conditions, but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite loop where we would unswitch again on such a condition. */ if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt)) - return NULL_TREE; + return NULL; /* Condition must be invariant. */ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) @@ -212,27 +231,29 @@ tree_may_unswitch_on (basic_block bb, class loop *loop) def_bb = gimple_bb (def); if (def_bb && flow_bb_inside_loop_p (loop, def_bb)) - return NULL_TREE; + return NULL; /* Unswitching on undefined values would introduce undefined behavior that the original program might never exercise. */ if (is_maybe_undefined (use, stmt, loop)) - return NULL_TREE; + return NULL; } cond = build2 (gimple_cond_code (stmt), boolean_type_node, gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); - return cond; + unswitch_predicate *predicate = new unswitch_predicate (cond); + ranger->range_of_expr (predicate->range, gimple_cond_lhs (stmt), stmt); + return predicate; } -/* Simplifies COND using checks in front of the entry of the LOOP. Just very - simplish (sufficient to prevent us from duplicating loop in unswitching - unnecessarily). */ +/* Simplifies COND using checks in front of the entry of the LOOP. + Utilize both symbolic expressions and value ranges calculated by Ranger. */ static tree -simplify_using_entry_checks (class loop *loop, tree cond) +simplify_using_entry_checks (class loop *loop, unswitch_predicate *predicate) { edge e = loop_preheader_edge (loop); + tree cond = predicate->condition; gimple *stmt; while (1) @@ -240,35 +261,45 @@ simplify_using_entry_checks (class loop *loop, tree cond) stmt = last_stmt (e->src); if (stmt && gimple_code (stmt) == GIMPLE_COND - && gimple_cond_code (stmt) == TREE_CODE (cond) && operand_equal_p (gimple_cond_lhs (stmt), - TREE_OPERAND (cond, 0), 0) - && operand_equal_p (gimple_cond_rhs (stmt), - TREE_OPERAND (cond, 1), 0)) - return (e->flags & EDGE_TRUE_VALUE - ? boolean_true_node - : boolean_false_node); + TREE_OPERAND (cond, 0), 0)) + { + if (gimple_cond_code (stmt) == TREE_CODE (cond) + && operand_equal_p (gimple_cond_rhs (stmt), + TREE_OPERAND (cond, 1), 0)) + return (e->flags & EDGE_TRUE_VALUE + ? boolean_true_node + : boolean_false_node); + else + { + int_range_max r; + if (!predicate->range.undefined_p () + && fold_range (r, stmt, predicate->range) + && r.singleton_p ()) + return r.zero_p () ? boolean_true_node : boolean_false_node; + } + } if (!single_pred_p (e->src)) - return cond; + return NULL_TREE; e = single_pred_edge (e->src); if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) - return cond; + return NULL_TREE; } } /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow it to grow too much, it is too easy to create example on that the code would - grow exponentially. */ + grow exponentially. RANGER is gimple ranger used in this pass. */ static bool -tree_unswitch_single_loop (class loop *loop, int num) +tree_unswitch_single_loop (class loop *loop, int num, gimple_ranger *ranger) { basic_block *bbs; class loop *nloop; unsigned i, found; - tree cond = NULL_TREE; + unswitch_predicate *predicate = NULL; gimple *stmt; bool changed = false; HOST_WIDE_INT iterations; @@ -314,7 +345,7 @@ tree_unswitch_single_loop (class loop *loop, int num) { /* Find a bb to unswitch on. */ for (; i < loop->num_nodes; i++) - if ((cond = tree_may_unswitch_on (bbs[i], loop))) + if ((predicate = tree_may_unswitch_on (bbs[i], loop, ranger))) break; if (i == loop->num_nodes) @@ -332,20 +363,22 @@ tree_unswitch_single_loop (class loop *loop, int num) break; } - cond = simplify_using_entry_checks (loop, cond); + tree folded = simplify_using_entry_checks (loop, predicate); stmt = last_stmt (bbs[i]); - if (integer_nonzerop (cond)) + if (folded != NULL_TREE && integer_nonzerop (folded)) { /* Remove false path. */ gimple_cond_set_condition_from_tree (as_a (stmt), boolean_true_node); + delete predicate; changed = true; } - else if (integer_zerop (cond)) + else if (folded != NULL_TREE && integer_zerop (folded)) { /* Remove true path. */ gimple_cond_set_condition_from_tree (as_a (stmt), boolean_false_node); + delete predicate; changed = true; } /* Do not unswitch too much. */ @@ -429,7 +462,7 @@ tree_unswitch_single_loop (class loop *loop, int num) /* Find a bb to unswitch on. */ for (; found < loop->num_nodes; found++) if ((bbs[found]->flags & BB_REACHABLE) - && (cond = tree_may_unswitch_on (bbs[found], loop))) + && (predicate = tree_may_unswitch_on (bbs[found], loop, ranger))) break; if (found == loop->num_nodes) @@ -440,11 +473,16 @@ tree_unswitch_single_loop (class loop *loop, int num) } if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, ";; Unswitching loop\n"); + { + fprintf (dump_file, ";; Unswitching loop with condition: "); + print_generic_expr (dump_file, predicate->condition); + fprintf (dump_file, "\n"); + } initialize_original_copy_tables (); /* Unswitch the loop on this condition. */ - nloop = tree_unswitch_loop (loop, bbs[found], cond); + nloop = tree_unswitch_loop (loop, bbs[found], predicate->condition); + delete predicate; if (!nloop) { free_original_copy_tables (); @@ -457,8 +495,8 @@ tree_unswitch_single_loop (class loop *loop, int num) free_original_copy_tables (); /* Invoke itself on modified loops. */ - tree_unswitch_single_loop (nloop, num + 1); - tree_unswitch_single_loop (loop, num + 1); + tree_unswitch_single_loop (nloop, num + 1, ranger); + tree_unswitch_single_loop (loop, num + 1, ranger); free (bbs); return true; }