From patchwork Wed Sep 15 08:46:51 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Martin_Li=C5=A1ka?= X-Patchwork-Id: 45015 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id AAA6D385843D for ; Wed, 15 Sep 2021 08:47:10 +0000 (GMT) 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 CDEF93858C60 for ; Wed, 15 Sep 2021 08:46:52 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org CDEF93858C60 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.cz 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 9C881221B6; Wed, 15 Sep 2021 08:46:51 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1631695611; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=zk2d6/2d0XIIky90eolO9bglx0RlJxwFPaxdQX9XHvE=; b=q06snlocBj2LNkb6mUydKUifKUV7xid/cSZtHCZW9MchQNElJVF3fZ5LShXObCdb+cN4Ff F17Kc4xEwSqdqKC3aBLk4mBXVsEJ5Sn6YE4APt1SK24a0StqJGjmZQLbRXTTV57Jp7bAP+ SKtE0rEstzzlOZ5qeDQ715Q9PIMdxxw= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1631695611; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=zk2d6/2d0XIIky90eolO9bglx0RlJxwFPaxdQX9XHvE=; b=INDvADeX3MTPJbjXDLez1Mxn4iKv0GbW71Wgs8hvU4h0LfkSkiQnfHzVgBuzD4KuXo/YA4 qKTkbouDvrJayRAQ== 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 866AA13A76; Wed, 15 Sep 2021 08:46:51 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id DgjRH/uyQWGHQAAAMHmgww (envelope-from ); Wed, 15 Sep 2021 08:46:51 +0000 Message-ID: Date: Wed, 15 Sep 2021 10:46:51 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.1.0 From: =?utf-8?q?Martin_Li=C5=A1ka?= Subject: [PATCH] Loop unswitching: support gswitch statements. To: gcc-patches@gcc.gnu.org Content-Language: en-US X-Spam-Status: No, score=-11.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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: , Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Hello. The patch extends the loop unswitching pass so that gswitch statements are supported. The pass now uses ranger which marks switch edges that are known to be unreachable in a versioned loop. Patch can bootstrap on x86_64-linux-gnu and survives regression tests. Ready to be installed? Thanks, Martin gcc/ChangeLog: * tree-cfg.c (gimple_lv_add_condition_to_bb): Support non-gimple expressions that needs to be gimplified. * tree-ssa-loop-unswitch.c (tree_unswitch_loop): Add new cond_edge parameter. (tree_may_unswitch_on): Support gswitch statements. (clean_up_switches): New function. (tree_ssa_unswitch_loops): Call clean_up_switches. (simplify_using_entry_checks): Removed and replaced with ranger. (tree_unswitch_single_loop): Change assumptions. gcc/testsuite/ChangeLog: * gcc.dg/loop-unswitch-6.c: New test. * gcc.dg/loop-unswitch-7.c: New test. * gcc.dg/loop-unswitch-8.c: New test. * gcc.dg/loop-unswitch-9.c: New test. Co-Authored-By: Richard Biener --- gcc/testsuite/gcc.dg/loop-unswitch-6.c | 56 +++++ gcc/testsuite/gcc.dg/loop-unswitch-7.c | 45 ++++ gcc/testsuite/gcc.dg/loop-unswitch-8.c | 28 +++ gcc/testsuite/gcc.dg/loop-unswitch-9.c | 34 +++ gcc/tree-cfg.c | 7 +- gcc/tree-ssa-loop-unswitch.c | 284 ++++++++++++++++++------- 6 files changed, 374 insertions(+), 80 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/loop-unswitch-6.c create mode 100644 gcc/testsuite/gcc.dg/loop-unswitch-7.c create mode 100644 gcc/testsuite/gcc.dg/loop-unswitch-8.c create mode 100644 gcc/testsuite/gcc.dg/loop-unswitch-9.c diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-6.c b/gcc/testsuite/gcc.dg/loop-unswitch-6.c new file mode 100644 index 00000000000..8a022e0f200 --- /dev/null +++ b/gcc/testsuite/gcc.dg/loop-unswitch-6.c @@ -0,0 +1,56 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details --param=max-unswitch-insns=1000 --param=max-unswitch-level=10" } */ + +int +__attribute__((noipa)) +foo(double *a, double *b, double *c, double *d, double *r, int size, int order) +{ + for (int i = 0; i < size; i++) + { + double tmp, tmp2; + + switch(order) + { + case 0: + tmp = -8 * a[i]; + tmp2 = 2 * b[i]; + break; + case 1: + tmp = 3 * a[i] - 2 * b[i]; + tmp2 = 5 * b[i] - 2 * c[i]; + break; + case 2: + tmp = 9 * a[i] + 2 * b[i] + c[i]; + tmp2 = 4 * b[i] + 2 * c[i] + 8 * d[i]; + break; + case 3: + tmp = 3 * a[i] + 2 * b[i] - c[i]; + tmp2 = b[i] - 2 * c[i] + 8 * d[i]; + break; + defaut: + __builtin_unreachable (); + } + + double x = 3 * tmp + d[i] + tmp; + double y = 3.4f * tmp + d[i] + tmp2; + r[i] = x + y; + } + + return 0; +} + +#define N 16 * 1024 +double aa[N], bb[N], cc[N], dd[N], rr[N]; + +int main() +{ + for (int i = 0; i < 100 * 1000; i++) + foo (aa, bb, cc, dd, rr, N, i % 4); +} + + +/* Test that we actually unswitched something. */ +/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 0" "unswitch" } } */ +/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 1" "unswitch" } } */ +/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 2" "unswitch" } } */ +/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 3" "unswitch" } } */ diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-7.c b/gcc/testsuite/gcc.dg/loop-unswitch-7.c new file mode 100644 index 00000000000..00f2fcff64b --- /dev/null +++ b/gcc/testsuite/gcc.dg/loop-unswitch-7.c @@ -0,0 +1,45 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details --param=max-unswitch-insns=1000 --param=max-unswitch-level=10" } */ + +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, tmp2; + + switch(order) + { + case 5 ... 6: + case 9: + tmp = -8 * a[i]; + tmp2 = 2 * b[i]; + break; + case 11: + tmp = 3 * a[i] - 2 * b[i]; + tmp2 = 5 * b[i] - 2 * c[i]; + break; + case 22: + tmp = 9 * a[i] + 2 * b[i] + c[i]; + tmp2 = 4 * b[i] + 2 * c[i] + 8 * d[i]; + break; + case 33: + tmp = 3 * a[i] + 2 * b[i] - c[i]; + tmp2 = b[i] - 2 * c[i] + 8 * d[i]; + break; + defaut: + __builtin_unreachable (); + } + + double x = 3 * tmp + d[i] + tmp; + double y = 3.4f * tmp + d[i] + tmp2; + r[i] = x + y; + } + + return 0; +} + +/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order_.* >= 5 & order_.* <= 6 | order_.* == 9" "unswitch" } } */ +/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 1" "unswitch" } } */ +/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 2" "unswitch" } } */ +/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 3" "unswitch" } } */ 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..4cec1f53bcc --- /dev/null +++ b/gcc/testsuite/gcc.dg/loop-unswitch-8.c @@ -0,0 +1,28 @@ +/* { 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 == 1) + tmp = -8 * a[i]; + else + tmp = -4 * b[i]; + + double x = 3 * tmp + d[i] + tmp; + + if (order == 1) + x += 2; + + 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" 1 "unswitch" } } */ diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-9.c b/gcc/testsuite/gcc.dg/loop-unswitch-9.c new file mode 100644 index 00000000000..3058d4a5b38 --- /dev/null +++ b/gcc/testsuite/gcc.dg/loop-unswitch-9.c @@ -0,0 +1,34 @@ +/* { 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, unsigned order) +{ + for (int i = 0; i < size; i++) + { + double tmp; + + switch (order) + { + case 0 ... 4: + tmp = -8 * a[i]; + break; + default: + tmp = -4 * b[i]; + break; + } + + double x = 3 * tmp + d[i] + tmp; + + /* This should not be unswitched as it's mutually excluded with case 0 ... 4. */ + if (order >= 5) + x += 2; + + double y = 3.4f * tmp + d[i]; + r[i] = x + y; + } + + return 0; +} + +/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* <= 4" 1 "unswitch" } } */ diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index 367dcfa20bf..159e5d83c06 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -9053,11 +9053,16 @@ gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED, edge e0; /* Build new conditional expr */ + gsi = gsi_last_bb (cond_bb); + + cond_expr = force_gimple_operand_gsi_1 (&gsi, cond_expr, + is_gimple_condexpr_for_cond, + NULL_TREE, false, + GSI_CONTINUE_LINKING); new_cond_expr = gimple_build_cond_from_tree (cond_expr, NULL_TREE, NULL_TREE); /* Add new cond in cond_bb. */ - gsi = gsi_last_bb (cond_bb); gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT); /* Adjust edges appropriately to connect new head with first head diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c index fe4dacc0833..a509938c7d0 100644 --- a/gcc/tree-ssa-loop-unswitch.c +++ b/gcc/tree-ssa-loop-unswitch.c @@ -37,6 +37,10 @@ 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" +#include "tree-pretty-print.h" +#include "gimple-range.h" /* This file implements the loop unswitching, i.e. transformation of loops like @@ -74,9 +78,9 @@ 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. */ -static class loop *tree_unswitch_loop (class loop *, basic_block, tree); +static class loop *tree_unswitch_loop (class loop *, basic_block, tree, edge); static bool tree_unswitch_single_loop (class loop *, int); -static tree tree_may_unswitch_on (basic_block, class loop *); +static tree tree_may_unswitch_on (basic_block, class loop *, edge *); 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); @@ -84,6 +88,7 @@ static bool used_outside_loop_p (class loop *, tree); static void hoist_guard (class loop *, edge); static bool check_exit_phi (class loop *); static tree get_vop_from_header (class loop *); +static void clean_up_switches (void); /* Main entry point. Perform loop unswitching on all suitable loops. */ @@ -103,7 +108,10 @@ tree_ssa_unswitch_loops (void) } if (changed) - return TODO_cleanup_cfg; + { + clean_up_switches (); + return TODO_cleanup_cfg; + } return 0; } @@ -182,80 +190,114 @@ 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). + When a gswitch case is returned, fill up COND_EDGE for it. */ static tree -tree_may_unswitch_on (basic_block bb, class loop *loop) +tree_may_unswitch_on (basic_block bb, class loop *loop, edge *cond_edge) { gimple *last, *def; - gcond *stmt; - tree cond, use; + tree 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); - - /* 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; - - /* Condition must be invariant. */ - FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) + if (gcond *stmt = safe_dyn_cast (last)) { - def = SSA_NAME_DEF_STMT (use); + /* 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; + + /* Condition must be invariant. */ + FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) + { + def = SSA_NAME_DEF_STMT (use); + 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 (use, stmt, loop)) + return NULL_TREE; + } + + edge e1 = EDGE_SUCC (bb, 0); + edge e2 = EDGE_SUCC (bb, 1); + *cond_edge = e1->flags & EDGE_TRUE_VALUE ? e1 : e2; + return build2 (gimple_cond_code (stmt), boolean_type_node, + gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); + } + else if (gswitch *stmt = safe_dyn_cast (last)) + { + unsigned nlabels = gimple_switch_num_labels (stmt); + tree idx = gimple_switch_index (stmt); + if (TREE_CODE (idx) != SSA_NAME + || nlabels < 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 (use, stmt, loop)) + if (is_maybe_undefined (idx, stmt, loop)) return NULL_TREE; - } - - cond = build2 (gimple_cond_code (stmt), boolean_type_node, - gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); - return cond; -} - -/* 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). */ - -static tree -simplify_using_entry_checks (class loop *loop, tree cond) -{ - edge e = loop_preheader_edge (loop); - gimple *stmt; + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs) + { + if (!(e->flags & EDGE_IGNORE)) + { + /* Build compound expression for all cases leading + to this edge. */ + tree expr = NULL_TREE; + for (unsigned i = 1; i < gimple_switch_num_labels (stmt); ++i) + { + tree lab = gimple_switch_label (stmt, i); + basic_block dest = label_to_block (cfun, CASE_LABEL (lab)); + edge e2 = find_edge (gimple_bb (stmt), dest); + if (e == e2) + { + tree cmp; + if (CASE_HIGH (lab) != NULL_TREE) + { + tree cmp1 = build2 (GE_EXPR, boolean_type_node, idx, + CASE_LOW (lab)); + tree cmp2 = build2 (LE_EXPR, boolean_type_node, idx, + CASE_HIGH (lab)); + cmp = build2 (BIT_AND_EXPR, boolean_type_node, cmp1, + cmp2); + } + else + cmp = build2 (EQ_EXPR, boolean_type_node, idx, + CASE_LOW (lab)); + + /* Combine the expression with the existing one. */ + if (expr == NULL_TREE) + expr = cmp; + else + expr = build2 (BIT_IOR_EXPR, boolean_type_node, expr, + cmp); + } + } - while (1) - { - 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); - - if (!single_pred_p (e->src)) - return cond; - - e = single_pred_edge (e->src); - if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) - return cond; + if (expr != NULL_TREE) + { + *cond_edge = e; + return expr; + } + } + } } + + return NULL_TREE; } /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow @@ -269,6 +311,7 @@ tree_unswitch_single_loop (class loop *loop, int num) class loop *nloop; unsigned i, found; tree cond = NULL_TREE; + edge cond_edge = NULL; gimple *stmt; bool changed = false; HOST_WIDE_INT iterations; @@ -311,11 +354,12 @@ tree_unswitch_single_loop (class loop *loop, int num) bbs = get_loop_body (loop); found = loop->num_nodes; + gimple_ranger ranger; while (1) { /* Find a bb to unswitch on. */ for (; i < loop->num_nodes; i++) - if ((cond = tree_may_unswitch_on (bbs[i], loop))) + if ((cond = tree_may_unswitch_on (bbs[i], loop, &cond_edge))) break; if (i == loop->num_nodes) @@ -333,24 +377,70 @@ tree_unswitch_single_loop (class loop *loop, int num) break; } - cond = simplify_using_entry_checks (loop, cond); stmt = last_stmt (bbs[i]); - if (integer_nonzerop (cond)) + gcond *condition = dyn_cast (stmt); + gswitch *swtch = dyn_cast (stmt); + + if (condition != NULL) { - /* Remove false path. */ - gimple_cond_set_condition_from_tree (as_a (stmt), - boolean_true_node); - changed = true; + int_range_max r; + edge edge_true, edge_false; + extract_true_false_edges_from_block (bbs[i], &edge_true, &edge_false); + tree cond = gimple_cond_lhs (stmt); + + if (r.supports_type_p (TREE_TYPE (cond))) + { + if (ranger.range_on_edge (r, edge_true, cond) + && r.undefined_p ()) + { + gimple_cond_set_condition_from_tree (condition, + boolean_false_node); + update_stmt (condition); + changed = true; + } + else if(ranger.range_on_edge (r, edge_false, gimple_cond_lhs (stmt)) + && r.undefined_p ()) + { + gimple_cond_set_condition_from_tree (condition, + boolean_true_node); + update_stmt (condition); + changed = true; + } + } } - else if (integer_zerop (cond)) + else if (swtch != NULL) { - /* Remove true path. */ - gimple_cond_set_condition_from_tree (as_a (stmt), - boolean_false_node); - changed = true; + hash_set ignored_edges; + unsigned nlabels = gimple_switch_num_labels (swtch); + tree index_candidate = NULL_TREE; + + for (unsigned i = 0; i < nlabels; ++i) + { + tree lab = gimple_switch_label (swtch, i); + basic_block dest = label_to_block (cfun, CASE_LABEL (lab)); + edge e = find_edge (gimple_bb (stmt), dest); + + int_range_max r; + if (ranger.range_on_edge (r, e, gimple_switch_index (swtch)) + && r.undefined_p ()) + { + e->flags |= EDGE_IGNORE; + ignored_edges.add (e); + } + else + index_candidate = CASE_LOW (lab); + } + + if (index_candidate != NULL_TREE + && ignored_edges.elements () == EDGE_COUNT (bbs[i]->succs) - 1) + { + gimple_switch_set_index (swtch, index_candidate); + update_stmt (swtch); + } } + /* Do not unswitch too much. */ - else if (num > param_max_unswitch_level) + if (num > param_max_unswitch_level) { i++; continue; @@ -371,7 +461,6 @@ tree_unswitch_single_loop (class loop *loop, int num) break; } - update_stmt (stmt); i++; } @@ -435,7 +524,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))) + && (cond = tree_may_unswitch_on (bbs[found], loop, &cond_edge))) break; if (found == loop->num_nodes) @@ -446,11 +535,15 @@ 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, cond); + 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], cond, cond_edge); if (!nloop) { free_original_copy_tables (); @@ -476,18 +569,15 @@ tree_unswitch_single_loop (class loop *loop, int num) static class loop * tree_unswitch_loop (class loop *loop, - basic_block unswitch_on, tree cond) + basic_block unswitch_on, tree cond, edge cond_edge) { profile_probability prob_true; - edge edge_true, edge_false; /* Some sanity checking. */ gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on)); - 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); - prob_true = edge_true->probability; + prob_true = cond_edge->probability; return loop_version (loop, unshare_expr (cond), NULL, prob_true, prob_true.invert (), @@ -965,6 +1055,42 @@ check_exit_phi (class loop *loop) return true; } +/* Remove all dead cases from switches that are unswitched. */ + +static void +clean_up_switches (void) +{ + basic_block bb; + + FOR_EACH_BB_FN (bb, cfun) + { + gimple *last = last_stmt (bb); + if (gswitch *stmt = safe_dyn_cast (last)) + { + unsigned nlabels = gimple_switch_num_labels (stmt); + unsigned index = 1; + for (unsigned i = 1; i < nlabels; ++i) + { + tree lab = gimple_switch_label (stmt, i); + basic_block dest = label_to_block (cfun, CASE_LABEL (lab)); + edge e = find_edge (gimple_bb (stmt), dest); + if (e == NULL) + ; /* The edge is already removed. */ + else if (e->flags & EDGE_IGNORE) + remove_edge (e); + else + { + gimple_switch_set_label (stmt, index, lab); + ++index; + } + } + + if (index != nlabels) + gimple_switch_set_num_labels (stmt, index); + } + } +} + /* Loop unswitching pass. */ namespace {