From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1851) id 5D0583858025; Tue, 31 Aug 2021 14:33:44 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 5D0583858025 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-unswitching-switch)] Richi's version. X-Act-Checkin: gcc X-Git-Author: Martin Liska X-Git-Refname: refs/users/marxin/heads/loop-unswitching-switch X-Git-Oldrev: 89f33f44addbf9853bc3e6677db1fa941713cb6c X-Git-Newrev: 717b4d8176d645b19ee2d89c5d2d743420c1c759 Message-Id: <20210831143344.5D0583858025@sourceware.org> Date: Tue, 31 Aug 2021 14:33:44 +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: Tue, 31 Aug 2021 14:33:44 -0000 https://gcc.gnu.org/g:717b4d8176d645b19ee2d89c5d2d743420c1c759 commit 717b4d8176d645b19ee2d89c5d2d743420c1c759 Author: Martin Liska Date: Mon Aug 30 15:47:34 2021 +0200 Richi's version. Diff: --- gcc/tree-ssa-loop-unswitch.c | 86 +++++++++++++++++++++++++++++++++++++------- 1 file changed, 74 insertions(+), 12 deletions(-) diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c index fe4dacc0833..9bfa053bb62 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 "cfganal.h" +#include "tree-cfgcleanup.h" /* This file implements the loop unswitching, i.e. transformation of loops like @@ -188,17 +190,14 @@ static tree tree_may_unswitch_on (basic_block bb, class loop *loop) { gimple *last, *def; - gcond *stmt; tree cond, use; basic_block def_bb; ssa_op_iter iter; /* BB must end in a simple conditional jump. */ last = last_stmt (bb); - if (!last || gimple_code (last) != GIMPLE_COND) - return NULL_TREE; - stmt = as_a (last); - + if (gcond *stmt = safe_dyn_cast (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. */ @@ -223,6 +222,31 @@ tree_may_unswitch_on (basic_block bb, class loop *loop) gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); return cond; + } + else if (gswitch *stmt = safe_dyn_cast (last)) + { + tree idx = gimple_switch_index (stmt); + if (TREE_CODE (idx) != SSA_NAME + || gimple_switch_num_labels (stmt) < 1) + return NULL_TREE; + /* Index must be invariant. */ + def = SSA_NAME_DEF_STMT (idx); + def_bb = gimple_bb (def); + if (def_bb + && flow_bb_inside_loop_p (loop, def_bb)) + return NULL_TREE; + /* Unswitching on undefined values would introduce undefined + behavior that the original program might never exercise. */ + if (is_maybe_undefined (idx, stmt, loop)) + return NULL_TREE; + /* TODO: pick based on profile or on biggest range (TODO: implement + ranges). */ + tree lab = gimple_switch_label (stmt, 1); + if (CASE_HIGH (lab)) + return NULL_TREE; + cond = build2 (EQ_EXPR, boolean_type_node, idx, CASE_LOW (lab)); + return cond; + } } /* Simplifies COND using checks in front of the entry of the LOOP. Just very @@ -333,22 +357,55 @@ tree_unswitch_single_loop (class loop *loop, int num) break; } + // likewise, using copy tables we should be able to "translate" + // the unswitched edge instead and adjust the code directly + // after the versioning rather than relying on recursion to + // fixup the code. + tree orig_cond = cond; cond = simplify_using_entry_checks (loop, cond); stmt = last_stmt (bbs[i]); if (integer_nonzerop (cond)) { /* Remove false path. */ - gimple_cond_set_condition_from_tree (as_a (stmt), - boolean_true_node); + if (is_a (stmt)) + gimple_cond_set_condition_from_tree (as_a (stmt), + boolean_true_node); + else + gimple_switch_set_index (as_a (stmt), + TREE_OPERAND (orig_cond, 1)); changed = true; } else if (integer_zerop (cond)) { /* Remove true path. */ - gimple_cond_set_condition_from_tree (as_a (stmt), - boolean_false_node); + if (is_a (stmt)) + gimple_cond_set_condition_from_tree (as_a (stmt), + boolean_false_node); + else + { + start_recording_case_labels (); + // we should know the edge already + gswitch *gs = as_a (stmt); + tree lab = gimple_switch_label (gs, 1); + basic_block dest = label_to_block (cfun, CASE_LABEL (lab)); + edge e = find_edge (gimple_bb (stmt), dest); + // modifying the CFG here may play havoc on things like + // dominators and we really would like to prevent doing + // full update_ssa for each individual unswitching as well + remove_edge (e); + if (gimple_switch_num_labels (gs) > 1) + gimple_switch_set_label (gs, 1, + gimple_switch_label (gs, gimple_switch_num_labels (gs) - 1)); + gimple_switch_set_num_labels (gs, gimple_switch_num_labels (gs) - 1); + end_recording_case_labels (); + /* Update based on the adjusted switch. */ + cond = tree_may_unswitch_on (bbs[i], loop); + } changed = true; } + // As said, it's a bit hackish to do it this way. */ + if (TREE_CODE (cond) == INTEGER_CST) + ; /* Do not unswitch too much. */ else if (num > param_max_unswitch_level) { @@ -459,7 +516,9 @@ tree_unswitch_single_loop (class loop *loop, int num) } /* Update the SSA form after unswitching. */ - update_ssa (TODO_update_ssa); + free_dominance_info (CDI_DOMINATORS); + cleanup_tree_cfg (TODO_update_ssa); + //update_ssa (TODO_update_ssa); free_original_copy_tables (); /* Invoke itself on modified loops. */ @@ -483,10 +542,13 @@ tree_unswitch_loop (class loop *loop, /* Some sanity checking. */ gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on)); - gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2); + //gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2); gcc_assert (loop->inner == NULL); - extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false); + // TODO: should switch on the edge rather than passing around + // a cond tree + //extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false); + edge_true = EDGE_SUCC (unswitch_on, 0); prob_true = edge_true->probability; return loop_version (loop, unshare_expr (cond), NULL, prob_true,