{"id":807593,"url":"http://patchwork.ozlabs.org/api/patches/807593/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/patch/bde90963-7695-89d5-6792-e8f803f71160@suse.cz/","project":{"id":17,"url":"http://patchwork.ozlabs.org/api/projects/17/?format=json","name":"GNU Compiler Collection","link_name":"gcc","list_id":"gcc-patches.gcc.gnu.org","list_email":"gcc-patches@gcc.gnu.org","web_url":null,"scm_url":null,"webscm_url":null,"list_archive_url":"","list_archive_url_format":"","commit_url_format":""},"msgid":"","list_archive_url":null,"date":"2017-08-30T11:13:35","name":"Expand switch statements with a single (or none) non-default case.","commit_ref":null,"pull_url":null,"state":"new","archived":false,"hash":"7d522351f5fa394d1e8ac90c4028652986b87ca7","submitter":{"id":62010,"url":"http://patchwork.ozlabs.org/api/people/62010/?format=json","name":"Martin Liška","email":"mliska@suse.cz"},"delegate":null,"mbox":"http://patchwork.ozlabs.org/project/gcc/patch/bde90963-7695-89d5-6792-e8f803f71160@suse.cz/mbox/","series":[{"id":589,"url":"http://patchwork.ozlabs.org/api/series/589/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/list/?series=589","date":"2017-08-30T11:13:35","name":"Expand switch statements with a single (or none) non-default case.","version":1,"mbox":"http://patchwork.ozlabs.org/series/589/mbox/"}],"comments":"http://patchwork.ozlabs.org/api/patches/807593/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/807593/checks/","tags":{},"related":[],"headers":{"Return-Path":"","X-Original-To":"incoming@patchwork.ozlabs.org","Delivered-To":["patchwork-incoming@bilbo.ozlabs.org","mailing list gcc-patches@gcc.gnu.org"],"Authentication-Results":["ozlabs.org;\n\tspf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org\n\t(client-ip=209.132.180.131; helo=sourceware.org;\n\tenvelope-from=gcc-patches-return-461153-incoming=patchwork.ozlabs.org@gcc.gnu.org;\n\treceiver=)","ozlabs.org; dkim=pass (1024-bit key;\n\tunprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org\n\theader.b=\"YNF7kzTk\"; dkim-atps=neutral","sourceware.org; auth=none"],"Received":["from sourceware.org (server1.sourceware.org [209.132.180.131])\n\t(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256\n\tbits)) (No client certificate requested)\n\tby ozlabs.org (Postfix) with ESMTPS id 3xj2v12vfgz9sN7\n\tfor ;\n\tWed, 30 Aug 2017 21:13:47 +1000 (AEST)","(qmail 39410 invoked by alias); 30 Aug 2017 11:13:40 -0000","(qmail 39172 invoked by uid 89); 30 Aug 2017 11:13:39 -0000","from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by\n\tsourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP;\n\tWed, 30 Aug 2017 11:13:37 +0000","from relay2.suse.de (charybdis-ext.suse.de [195.135.220.254])\tby\n\tmx1.suse.de (Postfix) with ESMTP id 57C13ABB2\tfor\n\t; Wed, 30 Aug 2017 11:13:35 +0000 (UTC)"],"DomainKey-Signature":"a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id\n\t:list-unsubscribe:list-archive:list-post:list-help:sender:from\n\t:subject:to:message-id:date:mime-version:content-type; q=dns; s=\n\tdefault; b=oJlc5N9AApzbIdHybABTYUwhXxsSeHWC7OOUIciWk2AmYoGfFtk2L\n\tdF8b1bwS/VVNdtnXH2uPzp6eEUH/MxFT8BYCLwnTBAq5/E3oN/ycvdiFAtUCn4zE\n\tN1NIUMxX40cEXAf5MTScAPFN35YusuRWUDTTuDYqF+Heyb3rKcFye8=","DKIM-Signature":"v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id\n\t:list-unsubscribe:list-archive:list-post:list-help:sender:from\n\t:subject:to:message-id:date:mime-version:content-type; s=\n\tdefault; bh=HP6LIx7QPpv8+bqgD1wec0hjKhY=; b=YNF7kzTkfC70HNDg+OKq\n\tFUuMyGeMK4inm4qJWcEOeA2cCIgg0p1z1k9oKrnP+MBkS5TYPKdmbV2KbiUZPTtw\n\tqrYqPjI29aePXTWAxoLIuq8y/e66Oq/N6HwUtgSt2cAXClTsgYm4tW/AXlFf0K4b\n\tDWBtP9FAm9ShBNPtZCfKIi4=","Mailing-List":"contact gcc-patches-help@gcc.gnu.org; run by ezmlm","Precedence":"bulk","List-Id":"","List-Unsubscribe":"","List-Archive":"","List-Post":"","List-Help":"","Sender":"gcc-patches-owner@gcc.gnu.org","X-Virus-Found":"No","X-Spam-SWARE-Status":"No, score=-26.9 required=5.0 tests=BAYES_00, GIT_PATCH_0,\n\tGIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3,\n\tSPF_PASS autolearn=ham version=3.3.2 spammy=H*MI:6792,\n\tH*MI:7695","X-HELO":"mx1.suse.de","From":"=?utf-8?q?Martin_Li=C5=A1ka?= ","Subject":"[PATCH] Expand switch statements with a single (or none)\n\tnon-default case.","To":"gcc-patches@gcc.gnu.org","Message-ID":"","Date":"Wed, 30 Aug 2017 13:13:35 +0200","User-Agent":"Mozilla/5.0 (X11; Linux x86_64;\n\trv:52.0) Gecko/20100101 Thunderbird/52.2.1","MIME-Version":"1.0","Content-Type":"multipart/mixed;\n\tboundary=\"------------C11DB3AF010214F566B75B30\"","X-IsSubscribed":"yes"},"content":"Hi.\n\nSimple transformation of switch statements where degenerated switch can be interpreted\nas gimple condition (or removed if having any non-default case). I originally though\nthat we don't have switch statements without non-default cases, but PR82032 shows we\ncan see it.\n\nPatch can bootstrap on ppc64le-redhat-linux and survives regression tests.\n\nReady to be installed?\nMartin\n\ngcc/ChangeLog:\n\n2017-08-25 Martin Liska \n\n\tPR tree-optimization/82032\n\t* tree-switch-conversion.c (generate_high_low_equality): New\n\tfunction.\n\t(expand_degenerated_switch): Likewise.\n\t(process_switch): Call expand_degenerated_switch.\n\t(try_switch_expansion): Likewise.\n\t(emit_case_nodes): Use generate_high_low_equality.\n\ngcc/testsuite/ChangeLog:\n\n2017-08-25 Martin Liska \n\n\tPR tree-optimization/82032\n\t* gcc.dg/tree-ssa/pr68198.c: Update jump threading expectations.\n\t* gcc.dg/tree-ssa/switch-expansion.c: New test.\n\t* gcc.dg/tree-ssa/vrp34.c: Update scanned pattern.\n\t* g++.dg/other/pr82032.C: New test.\n---\n gcc/testsuite/g++.dg/other/pr82032.C | 36 +++++++\n gcc/testsuite/gcc.dg/tree-ssa/pr68198.c | 6 +-\n gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c | 14 +++\n gcc/testsuite/gcc.dg/tree-ssa/vrp34.c | 5 +-\n gcc/tree-switch-conversion.c | 123 ++++++++++++++++++-----\n 5 files changed, 152 insertions(+), 32 deletions(-)\n create mode 100644 gcc/testsuite/g++.dg/other/pr82032.C\n create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c","diff":"diff --git a/gcc/testsuite/g++.dg/other/pr82032.C b/gcc/testsuite/g++.dg/other/pr82032.C\nnew file mode 100644\nindex 00000000000..607bf85c8e1\n--- /dev/null\n+++ b/gcc/testsuite/g++.dg/other/pr82032.C\n@@ -0,0 +1,36 @@\n+/* { dg-do compile } */\n+/* { dg-options \"-O3 -Wno-return-type\" } */\n+\n+template class b\n+{\n+public:\n+ typename a::aa operator[] (typename a::c) { }\n+};\n+class d\n+{\n+public:\n+ typedef long c;\n+ typedef int aa;\n+};\n+struct e\n+{\n+ int af[4];\n+ int ag;\n+};\n+b f;\n+bool\n+g (e &i)\n+{\n+ for (int h; h; ++h)\n+ switch (f[h])\n+ {\n+ case 'x':\n+ case 'a':\n+\ti.af[h] = 3;\n+\tbreak;\n+ default:\n+\treturn false;\n+ }\n+\n+ return true;\n+}\ndiff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c b/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c\nindex 16097d7e2bc..59d562e156c 100644\n--- a/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c\n+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c\n@@ -37,7 +37,5 @@ c_finish_omp_clauses (tree clauses)\n }\n }\n \n-/* There are 3 FSM jump threading opportunities, two of which will\n- get filtered out. */\n-/* { dg-final { scan-tree-dump-times \"Registering FSM\" 1 \"thread1\"} } */\n-/* { dg-final { scan-tree-dump-times \"FSM Thread through multiway branch without threading a multiway branch\" 2 \"thread1\"} } */\n+/* There are 3 FSM jump threading opportunities. */\n+/* { dg-final { scan-tree-dump-times \"Registering FSM\" 3 \"thread1\"} } */\ndiff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c b/gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c\nnew file mode 100644\nindex 00000000000..306253f3f9c\n--- /dev/null\n+++ b/gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c\n@@ -0,0 +1,14 @@\n+/* { dg-options \"-O2 -fdump-tree-switchconv\" } */\n+\n+int check(int param)\n+{\n+ switch (param) \n+ {\n+ case -2:\n+ return 1;\n+ default:\n+ return 0;\n+ }\n+}\n+\n+/* { dg-final { scan-tree-dump \"Expanding GIMPLE switch as condition\" \"switchconv\" } } */\ndiff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp34.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp34.c\nindex 142e56c1641..d2a36a706f2 100644\n--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp34.c\n+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp34.c\n@@ -15,5 +15,6 @@ foo (int a)\n }\n }\n \n-/* Both ifs should be optimized. */\n-/* { dg-final { scan-tree-dump-times \"if \\\\\\(\" 0 \"vrp1\" } } */\n+/* Both ifs should be optimized (and switch statement will be the only if\n+ in the function). */\n+/* { dg-final { scan-tree-dump-times \"if \\\\\\(\" 1 \"vrp1\" } } */\ndiff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c\nindex 5a827a6f1f9..b1cc203aba2 100644\n--- a/gcc/tree-switch-conversion.c\n+++ b/gcc/tree-switch-conversion.c\n@@ -1486,6 +1486,88 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)\n }\n }\n \n+/* Generate GIMPLE IL to basic block BB which compares whether INDEX\n+ value is within range LOW ... HIGH. We create a LHS and RHS that\n+ can be then compared in order to hit the interval or not. */\n+\n+static void\n+generate_high_low_equality (basic_block bb, tree index, tree low, tree high,\n+\t\t\t tree *lhs, tree *rhs)\n+{\n+ tree type = TREE_TYPE (index);\n+ tree utype = unsigned_type_for (type);\n+\n+ low = fold_convert (type, low);\n+ high = fold_convert (type, high);\n+\n+ tree tmp = make_ssa_name (type);\n+ gassign *sub1\n+ = gimple_build_assign (tmp, MINUS_EXPR, index, low);\n+\n+ *lhs = make_ssa_name (utype);\n+ gassign *a = gimple_build_assign (*lhs, NOP_EXPR, tmp);\n+\n+ *rhs = fold_build2 (MINUS_EXPR, utype, high, low);\n+ gimple_stmt_iterator gsi = gsi_last_bb (bb);\n+ gsi_insert_before (&gsi, sub1, GSI_SAME_STMT);\n+ gsi_insert_before (&gsi, a, GSI_SAME_STMT);\n+}\n+\n+/* Expand SWTCH with at maximum a single non-default edge to simple gimple\n+ condition. */\n+\n+static void\n+expand_degenerated_switch (gswitch *swtch)\n+{\n+ tree index = gimple_switch_index (swtch);\n+ gimple_stmt_iterator gsi = gsi_for_stmt (swtch);\n+\n+ if (gimple_switch_num_labels (swtch) == 1)\n+ {\n+ gsi_remove (&gsi, true);\n+\n+ if (dump_file)\n+\tfprintf (dump_file, \";; Removing GIMPLE switch:\\n\");\n+ }\n+ else\n+ {\n+ tree default_label = CASE_LABEL (gimple_switch_default_label (swtch));\n+ tree label = gimple_switch_label (swtch, 1);\n+ tree low = CASE_LOW (label);\n+ tree high = CASE_HIGH (label);\n+\n+ basic_block default_bb = label_to_block_fn (cfun, default_label);\n+ basic_block case_bb = label_to_block_fn (cfun, CASE_LABEL (label));\n+\n+ basic_block bb = gimple_bb (swtch);\n+ gcond *cond;\n+\n+ /* Replace switch statement with condition statement. */\n+ if (high)\n+\t{\n+\t tree lhs, rhs;\n+\t generate_high_low_equality (bb, index, low, high, &lhs, &rhs);\n+\t cond = gimple_build_cond (LE_EXPR, lhs, rhs, NULL_TREE, NULL_TREE);\n+\t}\n+ else\n+\tcond = gimple_build_cond (EQ_EXPR, index,\n+\t\t\t\t fold_convert (TREE_TYPE (index), low),\n+\t\t\t\t NULL_TREE, NULL_TREE);\n+\n+ gsi_replace (&gsi, cond, true);\n+\n+ /* Update edges. */\n+ edge case_edge = find_edge (bb, case_bb);\n+ edge default_edge = find_edge (bb, default_bb);\n+\n+ case_edge->flags |= EDGE_TRUE_VALUE;\n+ default_edge->flags |= EDGE_FALSE_VALUE;\n+\n+ if (dump_file)\n+\tfprintf (dump_file, \";; Expanding GIMPLE switch as condition:\\n\");\n+ }\n+}\n+\n /* The following function is invoked on every switch statement (the current one\n is given in SWTCH) and runs the individual phases of switch conversion on it\n one after another until one fails or the conversion is completed.\n@@ -1501,10 +1583,11 @@ process_switch (gswitch *swtch)\n that decide on the code generation approach for this switch. */\n group_case_labels_stmt (swtch);\n \n- /* If this switch is now a degenerate case with only a default label,\n- there is nothing left for us to do. */\n- if (gimple_switch_num_labels (swtch) < 2)\n- return \"switch is a degenerate case\";\n+ if (gimple_switch_num_labels (swtch) <= 2)\n+ {\n+ expand_degenerated_switch (swtch);\n+ return NULL;\n+ }\n \n collect_switch_conv_info (swtch, &info);\n \n@@ -2047,6 +2130,12 @@ try_switch_expansion (gswitch *stmt)\n hash_map phi_mapping;\n auto_vec case_bbs;\n \n+ if (gimple_switch_num_labels (stmt) <= 2)\n+ {\n+ expand_degenerated_switch (stmt);\n+ return true;\n+ }\n+\n /* A list of case labels; it is first built as a list and it may then\n be rearranged into a nearly balanced binary tree. */\n case_node *case_list = 0;\n@@ -2058,10 +2147,6 @@ try_switch_expansion (gswitch *stmt)\n expressions being INTEGER_CST. */\n gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);\n \n- /* Optimization of switch statements with only one label has already\n- occurred, so we should never see them at this point. */\n- gcc_assert (ncases > 1);\n-\n /* Find the default case target label. */\n tree default_label = CASE_LABEL (gimple_switch_default_label (stmt));\n default_bb = label_to_block_fn (cfun, default_label);\n@@ -2702,27 +2787,13 @@ emit_case_nodes (basic_block bb, tree index, case_node_ptr node,\n \t }\n \t else if (!low_bound && !high_bound)\n \t {\n-\t tree type = TREE_TYPE (index);\n-\t tree utype = unsigned_type_for (type);\n-\n-\t tree lhs = make_ssa_name (type);\n-\t gassign *sub1\n-\t\t= gimple_build_assign (lhs, MINUS_EXPR, index, node->low);\n-\n-\t tree converted = make_ssa_name (utype);\n-\t gassign *a = gimple_build_assign (converted, NOP_EXPR, lhs);\n-\n-\t tree rhs = fold_build2 (MINUS_EXPR, utype,\n-\t\t\t\t fold_convert (type, node->high),\n-\t\t\t\t fold_convert (type, node->low));\n-\t gimple_stmt_iterator gsi = gsi_last_bb (bb);\n-\t gsi_insert_before (&gsi, sub1, GSI_SAME_STMT);\n-\t gsi_insert_before (&gsi, a, GSI_SAME_STMT);\n-\n+\t tree lhs, rhs;\n+\t generate_high_low_equality (bb, index, node->low, node->high,\n+\t\t\t\t\t &lhs, &rhs);\n \t probability\n \t\t= conditional_probability (default_prob,\n \t\t\t\t\t subtree_prob + default_prob);\n-\t bb = emit_cmp_and_jump_insns (bb, converted, rhs, GT_EXPR,\n+\t bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR,\n \t\t\t\t\t default_bb, probability,\n \t\t\t\t\t phi_mapping);\n \t }\n\n","prefixes":[]}