From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 81375 invoked by alias); 4 Jan 2019 22:49:56 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 81366 invoked by uid 89); 4 Jan 2019 22:49:55 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-11.9 required=5.0 tests=BAYES_00,GIT_PATCH_2,GIT_PATCH_3,SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=5726, new_rhs X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 04 Jan 2019 22:49:52 +0000 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 03FD4A4056; Fri, 4 Jan 2019 22:49:51 +0000 (UTC) Received: from tucnak.zalov.cz (ovpn-116-18.ams2.redhat.com [10.36.116.18]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 98470600D7; Fri, 4 Jan 2019 22:49:50 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.15.2/8.15.2) with ESMTP id x04Mnm3M029887; Fri, 4 Jan 2019 23:49:48 +0100 Received: (from jakub@localhost) by tucnak.zalov.cz (8.15.2/8.15.2/Submit) id x04Mnj2l029886; Fri, 4 Jan 2019 23:49:45 +0100 Date: Fri, 04 Jan 2019 22:49:00 -0000 From: Jakub Jelinek To: Richard Biener , Jeff Law Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] Add a two value VR comparison to two consecutive PHI args optimization (PR tree-optimization/88676) Message-ID: <20190104224945.GB30353@tucnak> Reply-To: Jakub Jelinek MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.10.1 (2018-07-13) X-IsSubscribed: yes X-SW-Source: 2019-01/txt/msg00185.txt.bz2 Hi! The following patch adds an optimization, if we know certain SSA_NAME has two possible values and have GIMPLE_COND EQ_EXPR/NE_EXPR of that SSA_NAME with one of the two values and PHI which has two adjacent constants, we can optimize it into addition or subtraction. Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? The pr15826.c change is just a small change on what is present in GIMPLE with this patch, previously (from the bugzilla apparently only on some targets) we had a (_Bool) cast and now we have & 1, which effectively results in exactly the same expansion. 2019-01-04 Jakub Jelinek PR tree-optimization/88676 * tree-ssa-phiopt.c (two_value_replacement): New function. (tree_ssa_phiopt_worker): Call it. * gcc.dg/tree-ssa/pr88676.c: New test. * gcc.dg/pr88676.c: New test. * gcc.dg/tree-ssa/pr15826.c: Just verify there is no goto, allow &. --- gcc/tree-ssa-phiopt.c.jj 2019-01-01 12:37:17.716965779 +0100 +++ gcc/tree-ssa-phiopt.c 2019-01-04 13:55:26.293746657 +0100 @@ -48,6 +48,8 @@ along with GCC; see the file COPYING3. #include "case-cfn-macros.h" static unsigned int tree_ssa_phiopt_worker (bool, bool, bool); +static bool two_value_replacement (basic_block, basic_block, edge, gphi *, + tree, tree); static bool conditional_replacement (basic_block, basic_block, edge, edge, gphi *, tree, tree); static gphi *factor_out_conditional_conversion (edge, edge, gphi *, tree, tree, @@ -332,8 +334,11 @@ tree_ssa_phiopt_worker (bool do_store_el } /* Do the replacement of conditional if it can be done. */ - if (!early_p - && conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) + if (two_value_replacement (bb, bb1, e2, phi, arg0, arg1)) + cfgchanged = true; + else if (!early_p + && conditional_replacement (bb, bb1, e1, e2, phi, + arg0, arg1)) cfgchanged = true; else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; @@ -572,6 +577,118 @@ factor_out_conditional_conversion (edge return newphi; } +/* Optimize + # x_5 in range [cst1, cst2] where cst2 = cst1 + 1 + if (x_5 op cstN) # where op is == or != and N is 1 or 2 + goto bb3; + else + goto bb4; + bb3: + bb4: + # r_6 = PHI # where cst3 == cst4 + 1 or cst4 == cst3 + 1 + + to r_6 = x_5 + (min (cst3, cst4) - cst1) or + r_6 = (min (cst3, cst4) + cst1) - x_5 depending on op, N and which + of cst3 and cst4 is smaller. */ + +static bool +two_value_replacement (basic_block cond_bb, basic_block middle_bb, + edge e1, gphi *phi, tree arg0, tree arg1) +{ + /* Only look for adjacent integer constants. */ + if (!INTEGRAL_TYPE_P (TREE_TYPE (arg0)) + || !INTEGRAL_TYPE_P (TREE_TYPE (arg1)) + || TREE_CODE (arg0) != INTEGER_CST + || TREE_CODE (arg1) != INTEGER_CST + || (tree_int_cst_lt (arg0, arg1) + ? wi::to_widest (arg0) + 1 != wi::to_widest (arg1) + : wi::to_widest (arg1) + 1 != wi::to_widest (arg1))) + return false; + + if (!empty_block_p (middle_bb)) + return false; + + gimple *stmt = last_stmt (cond_bb); + tree lhs = gimple_cond_lhs (stmt); + tree rhs = gimple_cond_rhs (stmt); + + if (TREE_CODE (lhs) != SSA_NAME + || !INTEGRAL_TYPE_P (TREE_TYPE (lhs)) + || TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE + || TREE_CODE (rhs) != INTEGER_CST) + return false; + + switch (gimple_cond_code (stmt)) + { + case EQ_EXPR: + case NE_EXPR: + break; + default: + return false; + } + + wide_int min, max; + if (get_range_info (lhs, &min, &max) != VR_RANGE + || min + 1 != max + || (wi::to_wide (rhs) != min + && wi::to_wide (rhs) != max)) + return false; + + /* We need to know which is the true edge and which is the false + edge so that we know when to invert the condition below. */ + edge true_edge, false_edge; + extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); + if ((gimple_cond_code (stmt) == EQ_EXPR) + ^ (wi::to_wide (rhs) == max) + ^ (e1 == false_edge)) + std::swap (arg0, arg1); + + tree type; + if (TYPE_PRECISION (TREE_TYPE (lhs)) == TYPE_PRECISION (TREE_TYPE (arg0))) + { + if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE + || !TYPE_OVERFLOW_WRAPS (TREE_TYPE (arg0))) + type = TREE_TYPE (lhs); + else + type = TREE_TYPE (arg0); + } + else if (TYPE_PRECISION (TREE_TYPE (lhs)) > TYPE_PRECISION (TREE_TYPE (arg0))) + type = TREE_TYPE (lhs); + else + type = TREE_TYPE (arg0); + if (!TYPE_OVERFLOW_WRAPS (type)) + type = unsigned_type_for (type); + + tree m = fold_convert (type, wide_int_to_tree (TREE_TYPE (lhs), min)); + enum tree_code code; + if (tree_int_cst_lt (arg0, arg1)) + { + code = PLUS_EXPR; + m = int_const_binop (MINUS_EXPR, fold_convert (type, arg0), m); + } + else + { + code = MINUS_EXPR; + m = int_const_binop (PLUS_EXPR, fold_convert (type, arg0), m); + } + + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + if (!useless_type_conversion_p (type, TREE_TYPE (lhs))) + lhs = gimplify_build1 (&gsi, NOP_EXPR, type, lhs); + tree new_rhs; + if (code == PLUS_EXPR) + new_rhs = gimplify_build2 (&gsi, PLUS_EXPR, type, lhs, m); + else + new_rhs = gimplify_build2 (&gsi, MINUS_EXPR, type, m, lhs); + if (!useless_type_conversion_p (TREE_TYPE (arg0), type)) + new_rhs = gimplify_build1 (&gsi, NOP_EXPR, TREE_TYPE (arg0), new_rhs); + + replace_phi_edge_with_variable (cond_bb, e1, phi, new_rhs); + + /* Note that we optimized this PHI. */ + return true; +} + /* The function conditional_replacement does the main work of doing the conditional replacement. Return true if the replacement is done. Otherwise return false. --- gcc/testsuite/gcc.dg/tree-ssa/pr88676.c.jj 2019-01-04 14:20:59.659542587 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/pr88676.c 2019-01-04 14:25:38.122965795 +0100 @@ -0,0 +1,133 @@ +/* PR tree-optimization/88676 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-final { scan-tree-dump-not " = PHI <" "optimized" } } */ + +void bar (int, int, int); + +__attribute__((noipa)) int +f1 (unsigned x) +{ + int r; + if (x >= 2) + __builtin_unreachable (); + switch (x) + { + case 0: + r = 1; + break; + case 1: + r = 2; + break; + default: + r = 0; + break; + } + return r; +} + +__attribute__((noipa)) void +f2 (int x) +{ + int y; + x = (x & 1) + 98; + if (x != 98) + y = 115; + else + y = 116; + bar (x, y, 116); +} + +__attribute__((noipa)) void +f3 (int x) +{ + int y; + x = (x & 1) + 98; + if (x == 98) + y = 115; + else + y = 116; + bar (x, y, 115); +} + +__attribute__((noipa)) void +f4 (int x) +{ + int y; + x = (x & 1) + 98; + if (x != 99) + y = 115; + else + y = 116; + bar (x, y, 115); +} + +__attribute__((noipa)) void +f5 (int x) +{ + int y; + x = (x & 1) + 98; + if (x == 99) + y = 115; + else + y = 116; + bar (x, y, 116); +} + +__attribute__((noipa)) void +f6 (int x) +{ + int y; + x = (x & 1) + 98; + if (x != 98) + y = 116; + else + y = 115; + bar (x, y, 115); +} + +__attribute__((noipa)) void +f7 (int x) +{ + int y; + x = (x & 1) + 98; + if (x == 98) + y = 116; + else + y = 115; + bar (x, y, 116); +} + +__attribute__((noipa)) void +f8 (int x) +{ + int y; + x = (x & 1) + 98; + if (x != 99) + y = 116; + else + y = 115; + bar (x, y, 116); +} + +__attribute__((noipa)) void +f9 (int x) +{ + int y; + x = (x & 1) + 98; + if (x == 99) + y = 116; + else + y = 115; + bar (x, y, 115); +} + +__attribute__((noipa)) int +f10 (int x) +{ + x = (x & 1) + 36; + if (x == 36) + return 85; + else + return 84; +} --- gcc/testsuite/gcc.dg/pr88676.c.jj 2019-01-04 14:29:55.821731065 +0100 +++ gcc/testsuite/gcc.dg/pr88676.c 2019-01-04 14:29:39.048006694 +0100 @@ -0,0 +1,48 @@ +/* PR tree-optimization/88676 */ +/* { dg-do run } */ +/* { dg-options "-O2" } */ + +#include "tree-ssa/pr88676.c" + +__attribute__((noipa)) void +bar (int x, int y, int z) +{ + if (z != 115 && z != 116) + __builtin_abort (); + if (x == 98) + { + if (y != z) + __builtin_abort (); + } + else if (x != 99) + __builtin_abort (); + else if (z == 115) + { + if (y != 116) + __builtin_abort (); + } + else if (y != 115) + __builtin_abort (); +} + +int +main () +{ + if (f1 (0) != 1 || f1 (1) != 2) + __builtin_abort (); + int i; + for (i = -12; i < 12; i++) + { + f2 (i); + f3 (i); + f4 (i); + f5 (i); + f6 (i); + f7 (i); + f8 (i); + f9 (i); + if (f10 (i) != ((i & 1) ? 84 : 85)) + __builtin_abort (); + } + return 0; +} --- gcc/testsuite/gcc.dg/tree-ssa/pr15826.c.jj 2016-02-27 07:41:54.377920386 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/pr15826.c 2019-01-04 23:41:36.300566686 +0100 @@ -33,4 +33,4 @@ andrew (struct s *p) return i; } -/* { dg-final { scan-tree-dump-times " & | goto " 0 "optimized" } } */ +/* { dg-final { scan-tree-dump-not "goto " "optimized" } } */ Jakub