From patchwork Tue Apr 19 17:50:04 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 612238 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3qqCH56GpMz9t8b for ; Wed, 20 Apr 2016 03:50:57 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=GSlA5aGR; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id; q=dns; s=default; b=P1N051uegQL4 iki7868usYtUuthi6HZHbZnreR+CGmt/TBF9k6aRhKjScgW7840NpOCf6rJ+0038 b5tjxBGpR/3fyR6Xi/SGDhpnrA7RgmLEJ54jDoUhG+zsZy718ZM0hK8ixv2NUwI3 1hp7Q3vY/Zh8TIMd5OwWz/YqB9PgpGU= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id; s=default; bh=MfKOvqO39yXFEVcyo3 91DrXwKC4=; b=GSlA5aGRvldcOLNc07gNqz64ymAvpWNaTDicxcc81OUhEh4f/h B69kUcZW+ZKESyvBNfGjneoAgla7+CmSr3U5QmZU+XTgBykWMrES5oESsK/Y8MPA 5F51T//AoFUxHd19j0lJsA/XDCBhubfIU1rwzZWzVooxg5ATyKrI1I46I= Received: (qmail 106422 invoked by alias); 19 Apr 2016 17:50:42 -0000 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 Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 106322 invoked by uid 89); 19 Apr 2016 17:50:39 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.6 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.2 spammy=res2, res1, sk:!is_gim, sk:is_gim X-HELO: mail-qg0-f48.google.com Received: from mail-qg0-f48.google.com (HELO mail-qg0-f48.google.com) (209.85.192.48) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Tue, 19 Apr 2016 17:50:14 +0000 Received: by mail-qg0-f48.google.com with SMTP id c6so13649239qga.1 for ; Tue, 19 Apr 2016 10:50:14 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id; bh=TC6Vj8iVriHKlCTAvaJfqHoGEgV02d1/5hH/LaYi4Fw=; b=JpTT05Vpw5byeyZSLdNmsF3wKhO2nFuOIoa6jgqmqXdxRXN1iIUVUftjH9C/Lgx6BM GaqhiiSEaUl637UMoffT/B35KpqlL1AbAQMQABjc29Z0Ae6TfDjtRpM9WB7y4XajBrBN WwaoIgRKVGs4UIXpFYXYc0re/AaZhB8P35yNwsmIFdox1MAuteEwR7U1dPY+VTg3o070 g6O0nLYKN2Q8tEgUKg/1hcNPch6tdq5m6jnz4+K0Fqh5H6JwLswwp6RtTItHUm7G5339 4EAnhmAaD96XbZTjSukKx8tRjY3sJf4k065f9kxUIxZje07c3jctwYuLESmVoTZn/DcT 3ySA== X-Gm-Message-State: AOPr4FURM2qcJq1NrAxHcGASfjNRnvgvkiDYFCJeK6KHBqqeCGEnbtb+GCSe7Ni4frS0HQ== X-Received: by 10.141.2.9 with SMTP id e9mr5670046qhd.18.1461088212041; Tue, 19 Apr 2016 10:50:12 -0700 (PDT) Received: from localhost.localdomain (ool-4353abbc.dyn.optonline.net. [67.83.171.188]) by smtp.gmail.com with ESMTPSA id g11sm21513272qhg.22.2016.04.19.10.50.11 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Tue, 19 Apr 2016 10:50:11 -0700 (PDT) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: Patrick Palka Subject: [PATCH] Improve detection of constant conditions during jump threading Date: Tue, 19 Apr 2016 13:50:04 -0400 Message-Id: <1461088204-24966-1-git-send-email-patrick@parcs.ath.cx> This patch makes the jump threader look through the BIT_AND_EXPRs and BIT_IOR_EXPRs within a condition so that we could find dominating ASSERT_EXPRs that could help make the overall condition evaluate to a constant. For example, we currently don't perform any jump threading in the following test case even though it's known that if the code calls foo() then it can't possibly call bar() afterwards: void baz_1 (int a, int b, int c) { if (a && b) foo (); if (!b && c) bar (); } : _4 = a_3(D) != 0; _6 = b_5(D) != 0; _7 = _4 & _6; if (_7 != 0) goto ; else goto ; : b_15 = ASSERT_EXPR ; foo (); : _10 = b_5(D) == 0; _12 = c_11(D) != 0; _13 = _10 & _12; if (_13 != 0) goto ; else goto ; : bar (); : return; So we here miss a jump threading opportunity that would have made bb 3 jump straight to bb 6 instead of falling through to bb 4. If we inspect the operands of the BIT_AND_EXPR of _13 we'll notice that there is an ASSERT_EXPR that says its left operand b_5 is non-zero. We could use this ASSERT_EXPR to deduce that the condition (_13 != 0) is always false. This is what this patch does, basically by making simplify_control_stmt_condition recurse into BIT_AND_EXPRs and BIT_IOR_EXPRs. Does this seem like a good idea/approach? Notes: 1. This patch introduces a "regression" in gcc.dg/tree-ssa/ssa-thread-11.c in that we no longer perform FSM threading during vrp2 but instead we detect two new jump threading opportunities during vrp1. Not sure if the new code is better but it is shorter. I wonder how this should be resolved... 2. I haven't tested the performance impact of this patch. What would be a good way to do this? 3. According to my instrumentation, an older version of this change added 4000 new threaded jumps during bootstrap. gcc/ChangeLog: * tree-ssa-threadedge.c (simplify_control_stmt_condition): Split out into ... (simplify_control_stmt_condition_1): ... here. Recurse into BIT_AND_EXPRs and BIT_IOR_EXPRs. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/ssa-thread-14.c: New test. --- gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-14.c | 81 +++++++++ gcc/tree-ssa-threadedge.c | 249 +++++++++++++++++++++----- 2 files changed, 285 insertions(+), 45 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-14.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-14.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-14.c new file mode 100644 index 0000000..db9ed3b --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-14.c @@ -0,0 +1,81 @@ +/* { dg-do compile } */ +/* { dg-additional-options "-O2 -fdump-tree-vrp" } */ +/* { dg-final { scan-tree-dump-times "Threaded jump" 8 "vrp1" } } */ + +void foo (void); +void bar (void); +void blah (void); + +/* One jump threaded here. */ + +void +baz_1 (int a, int b, int c) +{ + if (a && b) + foo (); + if (!b && c) + bar (); +} + +/* One jump threaded here. */ + +void +baz_2 (int a, int b, int c) +{ + if (a && b) + foo (); + if (b || c) + bar (); +} + +/* One jump threaded here. */ + +void +baz_3 (int a, int b, int c) +{ + if (a && b > 10) + foo (); + if (b < 5 && c) + bar (); +} + +/* Two jumps threaded here. */ + +void +baz_4 (int a, int b, int c) +{ + if (a && b) + { + foo (); + if (c) + bar (); + } + if (b && c) + blah (); +} + +/* Two jumps threaded here. */ + +void +baz_5 (int a, int b, int c) +{ + if (a && b) + { + foo (); + if (c) + bar (); + } + if (!b || !c) + blah (); +} + +/* One jump threaded here. */ + +void +baz_6 (int a, int b, int c) +{ + if (a == 39 && b == 41) + foo (); + if (c == 12 || b == 41) + bar (); +} diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c index f60be38..a4e8a26 100644 --- a/gcc/tree-ssa-threadedge.c +++ b/gcc/tree-ssa-threadedge.c @@ -376,6 +376,12 @@ record_temporary_equivalences_from_stmts_at_dest (edge e, return stmt; } +static tree simplify_control_stmt_condition_1 (edge, gimple *, + class avail_exprs_stack *, + tree, enum tree_code, tree, + gcond *, pfn_simplify, bool, + unsigned); + /* Simplify the control statement at the end of the block E->dest. To avoid allocating memory unnecessarily, a scratch GIMPLE_COND @@ -436,52 +442,14 @@ simplify_control_stmt_condition (edge e, } } - if (handle_dominating_asserts) - { - /* Now see if the operand was consumed by an ASSERT_EXPR - which dominates E->src. If so, we want to replace the - operand with the LHS of the ASSERT_EXPR. */ - if (TREE_CODE (op0) == SSA_NAME) - op0 = lhs_of_dominating_assert (op0, e->src, stmt); - - if (TREE_CODE (op1) == SSA_NAME) - op1 = lhs_of_dominating_assert (op1, e->src, stmt); - } - - /* We may need to canonicalize the comparison. For - example, op0 might be a constant while op1 is an - SSA_NAME. Failure to canonicalize will cause us to - miss threading opportunities. */ - if (tree_swap_operands_p (op0, op1, false)) - { - cond_code = swap_tree_comparison (cond_code); - std::swap (op0, op1); - } + const unsigned recursion_limit = 4; - /* Stuff the operator and operands into our dummy conditional - expression. */ - gimple_cond_set_code (dummy_cond, cond_code); - gimple_cond_set_lhs (dummy_cond, op0); - gimple_cond_set_rhs (dummy_cond, op1); - - /* We absolutely do not care about any type conversions - we only care about a zero/nonzero value. */ - fold_defer_overflow_warnings (); - - cached_lhs = fold_binary (cond_code, boolean_type_node, op0, op1); - if (cached_lhs) - while (CONVERT_EXPR_P (cached_lhs)) - cached_lhs = TREE_OPERAND (cached_lhs, 0); - - fold_undefer_overflow_warnings ((cached_lhs - && is_gimple_min_invariant (cached_lhs)), - stmt, WARN_STRICT_OVERFLOW_CONDITIONAL); - - /* If we have not simplified the condition down to an invariant, - then use the pass specific callback to simplify the condition. */ - if (!cached_lhs - || !is_gimple_min_invariant (cached_lhs)) - cached_lhs = (*simplify) (dummy_cond, stmt, avail_exprs_stack); + cached_lhs + = simplify_control_stmt_condition_1 (e, stmt, avail_exprs_stack, + op0, cond_code, op1, + dummy_cond, simplify, + handle_dominating_asserts, + recursion_limit); /* If we were testing an integer/pointer against a constant, then we can use the FSM code to trace the value of the SSA_NAME. If @@ -560,6 +528,197 @@ simplify_control_stmt_condition (edge e, return cached_lhs; } +/* Recursive helper for simplify_control_stmt_condition. */ + +static tree +simplify_control_stmt_condition_1 (edge e, + gimple *stmt, + class avail_exprs_stack *avail_exprs_stack, + tree op0, + enum tree_code cond_code, + tree op1, + gcond *dummy_cond, + pfn_simplify simplify, + bool handle_dominating_asserts, + unsigned limit) +{ + if (limit == 0) + return NULL_TREE; + + /* We may need to canonicalize the comparison. For + example, op0 might be a constant while op1 is an + SSA_NAME. Failure to canonicalize will cause us to + miss threading opportunities. */ + if (tree_swap_operands_p (op0, op1, false)) + { + cond_code = swap_tree_comparison (cond_code); + std::swap (op0, op1); + } + + /* If the condition has the form (A & B) CMP 0 or (A | B) CMP 0 then + recurse into the LHS to see if there is a dominating ASSERT_EXPR + of A or of B that makes this condition always true or always false + along the edge E. */ + if (handle_dominating_asserts + && (cond_code == EQ_EXPR || cond_code == NE_EXPR) + && TREE_CODE (op0) == SSA_NAME + && integer_zerop (op1)) + { + gimple *def_stmt = SSA_NAME_DEF_STMT (op0); + if (gimple_code (def_stmt) != GIMPLE_ASSIGN) + ; + else if (gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR + || gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR) + { + enum tree_code rhs_code = gimple_assign_rhs_code (def_stmt); + const tree rhs1 = gimple_assign_rhs1 (def_stmt); + const tree rhs2 = gimple_assign_rhs2 (def_stmt); + const tree zero_cst = build_zero_cst (TREE_TYPE (op0)); + const tree one_cst = build_one_cst (TREE_TYPE (op0)); + + /* Is A != 0 ? */ + const tree res1 + = simplify_control_stmt_condition_1 (e, def_stmt, avail_exprs_stack, + rhs1, NE_EXPR, op1, + dummy_cond, simplify, + handle_dominating_asserts, + limit - 1); + if (res1 == NULL_TREE) + ; + else if (rhs_code == BIT_AND_EXPR && integer_zerop (res1)) + { + /* If A == 0 then (A & B) != 0 is always false. */ + if (cond_code == NE_EXPR) + return zero_cst; + /* If A == 0 then (A & B) == 0 is always true. */ + if (cond_code == EQ_EXPR) + return one_cst; + } + else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res1)) + { + /* If A != 0 then (A | B) != 0 is always true. */ + if (cond_code == NE_EXPR) + return one_cst; + /* If A != 0 then (A | B) == 0 is always false. */ + if (cond_code == EQ_EXPR) + return zero_cst; + } + + /* Is B != 0 ? */ + const tree res2 + = simplify_control_stmt_condition_1 (e, def_stmt, avail_exprs_stack, + rhs2, NE_EXPR, op1, + dummy_cond, simplify, + handle_dominating_asserts, + limit - 1); + if (res2 == NULL_TREE) + ; + else if (rhs_code == BIT_AND_EXPR && integer_zerop (res2)) + { + /* If B == 0 then (A & B) != 0 is always false. */ + if (cond_code == NE_EXPR) + return zero_cst; + /* If B == 0 then (A & B) == 0 is always true. */ + if (cond_code == EQ_EXPR) + return one_cst; + } + else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res2)) + { + /* If B != 0 then (A | B) != 0 is always true. */ + if (cond_code == NE_EXPR) + return one_cst; + /* If B != 0 then (A | B) == 0 is always false. */ + if (cond_code == EQ_EXPR) + return zero_cst; + } + + if (res1 != NULL_TREE && res2 != NULL_TREE) + { + if (rhs_code == BIT_AND_EXPR + && TYPE_PRECISION (TREE_TYPE (op0)) == 1 + && integer_nonzerop (res1) + && integer_nonzerop (res2)) + { + /* If A != 0 and B != 0 then (bool)(A | B) != 0 is true. */ + if (cond_code == NE_EXPR) + return one_cst; + /* If A != 0 and B != 0 then (bool)(A | B) == 0 is false. */ + if (cond_code == EQ_EXPR) + return zero_cst; + } + + if (rhs_code == BIT_IOR_EXPR + && integer_zerop (res1) + && integer_zerop (res2)) + { + /* If A == 0 and B == 0 then (A | B) != 0 is false. */ + if (cond_code == NE_EXPR) + return zero_cst; + /* If A == 0 and B == 0 then (A | B) == 0 is true. */ + if (cond_code == EQ_EXPR) + return one_cst; + } + } + } + /* Handle (A CMP B) CMP 0. */ + else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) + == tcc_comparison) + { + tree rhs1 = gimple_assign_rhs1 (def_stmt); + tree rhs2 = gimple_assign_rhs2 (def_stmt); + + tree_code new_cond = gimple_assign_rhs_code (def_stmt); + if (cond_code == EQ_EXPR) + new_cond = invert_tree_comparison (new_cond, false); + + tree res + = simplify_control_stmt_condition_1 (e, def_stmt, avail_exprs_stack, + rhs1, new_cond, rhs2, + dummy_cond, simplify, + handle_dominating_asserts, + limit - 1); + if (res != NULL_TREE && is_gimple_min_invariant (res)) + return res; + } + } + + if (handle_dominating_asserts) + { + /* Now see if the operand was consumed by an ASSERT_EXPR + which dominates E->src. If so, we want to replace the + operand with the LHS of the ASSERT_EXPR. */ + if (TREE_CODE (op0) == SSA_NAME) + op0 = lhs_of_dominating_assert (op0, e->src, stmt); + + if (TREE_CODE (op1) == SSA_NAME) + op1 = lhs_of_dominating_assert (op1, e->src, stmt); + } + + gimple_cond_set_code (dummy_cond, cond_code); + gimple_cond_set_lhs (dummy_cond, op0); + gimple_cond_set_rhs (dummy_cond, op1); + + /* We absolutely do not care about any type conversions + we only care about a zero/nonzero value. */ + fold_defer_overflow_warnings (); + + tree res = fold_binary (cond_code, boolean_type_node, op0, op1); + if (res) + while (CONVERT_EXPR_P (res)) + res = TREE_OPERAND (res, 0); + + fold_undefer_overflow_warnings ((res && is_gimple_min_invariant (res)), + stmt, WARN_STRICT_OVERFLOW_CONDITIONAL); + + /* If we have not simplified the condition down to an invariant, + then use the pass specific callback to simplify the condition. */ + if (!res + || !is_gimple_min_invariant (res)) + res = (*simplify) (dummy_cond, stmt, avail_exprs_stack); + + return res; +} + /* Copy debug stmts from DEST's chain of single predecessors up to SRC, so that we don't lose the bindings as PHI nodes are introduced when DEST gains new predecessors. */