From patchwork Thu Oct 27 13:37:15 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bin Cheng X-Patchwork-Id: 687607 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 3t4Sch5M4tz9t25 for ; Fri, 28 Oct 2016 00:37:40 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=DjtjzfnJ; 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:mime-version:content-type; q=dns; s=default; b=o1eQ82OuFE08vLfLfBhH9wsqd/lqrMr6HifdcaupBmnfVzjh7b 09hvj+fE1jEVASAuDufu+Wy/f9Mmi5jYDIiGdTSsPGSlU6MaduZidqShqvsdab6D ZyvrmDDiVvVVrfvlkhdPesQupU2r6yZm09qR8h5rL1wy/0VWSRngGwiWM= 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:mime-version:content-type; s= default; bh=wwp6Dvvzy4xdWD9OTBeI3U2gv6s=; b=DjtjzfnJqQlKlZqKVCTQ zKI0/trgxiPRpRtEN06yFWFl7cRXfEVLgdc/9YZhjqC2D03qy9rhSYsy37aotQ2n l/5oq2qkOr7LKacWTLAJU/9IiZ4hg7UvtWaH8+2vrdpnUwEMjc68a0XWLXS3YwFE aNQ5xyxMVXI+XBNZMJ6Gkys= Received: (qmail 26567 invoked by alias); 27 Oct 2016 13:37:31 -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 26553 invoked by uid 89); 27 Oct 2016 13:37:30 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=AWL, BAYES_00, SPF_PASS autolearn=ham version=3.3.2 spammy=carried, During, sk:number_, father X-HELO: eu-smtp-delivery-143.mimecast.com Received: from eu-smtp-delivery-143.mimecast.com (HELO eu-smtp-delivery-143.mimecast.com) (146.101.78.143) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 27 Oct 2016 13:37:20 +0000 Received: from EUR01-HE1-obe.outbound.protection.outlook.com (mail-he1eur01lp0214.outbound.protection.outlook.com [213.199.154.214]) (Using TLS) by eu-smtp-1.mimecast.com with ESMTP id uk-mta-13-Edh7noqhOP-IfJotgY2nwA-1; Thu, 27 Oct 2016 14:37:16 +0100 Received: from VI1PR0802MB2176.eurprd08.prod.outlook.com (10.172.12.21) by VI1PR0802MB2175.eurprd08.prod.outlook.com (10.172.12.20) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.679.12; Thu, 27 Oct 2016 13:37:15 +0000 Received: from VI1PR0802MB2176.eurprd08.prod.outlook.com ([10.172.12.21]) by VI1PR0802MB2176.eurprd08.prod.outlook.com ([10.172.12.21]) with mapi id 15.01.0659.028; Thu, 27 Oct 2016 13:37:15 +0000 From: Bin Cheng To: "gcc-patches@gcc.gnu.org" CC: nd Subject: [PATCH VECT]Support operand swapping for cond_expr in vect_slp Date: Thu, 27 Oct 2016 13:37:15 +0000 Message-ID: x-ms-office365-filtering-correlation-id: 2d4b9db0-7efd-452c-ed8a-08d3fe6e5d34 x-microsoft-exchange-diagnostics: 1; VI1PR0802MB2175; 7:16uzPczYRco50FJCAJ9U8vEColD7CHIsRpWnZVSUeiYjB91e8gyxkKA03laP++sNJ8+dLIk9OXgsFdGPIpliaMlCBM1nhkvwfV5v/DgEBIlZr0VqaRqHsXp98VsestmQYQNk0e14kLQjhsvv1R0Z7pRTGmxkw8nPOXVprIhrS6aH808dP0gwKZNSlJtuQSkgkj1YfENKheEpj9/gUO/icQj0BCUMkxpXnflSd9XcpCfUxf4/c5Na76cwKVVugVuujq/+JMwXLynY1jEJ45iO2vN8xi0q1DSoOhJpOb855U59ENubYyrhORC1EnRZs/LgqfWSH2fGNNUGm6jiKrLrwmD0jLHkSoVZ+jtkZcPe9Ik= x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:VI1PR0802MB2175; nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(180628864354917); x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(102415321)(6040176)(601004)(2401047)(5005006)(8121501046)(3002001)(10201501046)(6055026); SRVR:VI1PR0802MB2175; BCL:0; PCL:0; RULEID:; SRVR:VI1PR0802MB2175; x-forefront-prvs: 0108A997B2 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(7916002)(377424004)(189002)(199003)(19580405001)(54356999)(101416001)(450100001)(122556002)(19580395003)(86362001)(2351001)(106116001)(66066001)(229853001)(105586002)(106356001)(99936001)(50986999)(4326007)(4001150100001)(76576001)(586003)(6116002)(3280700002)(102836003)(3846002)(3660700001)(92566002)(5002640100001)(7736002)(68736007)(11100500001)(305945005)(74316002)(7846002)(2501003)(81166006)(10400500002)(33656002)(189998001)(77096005)(2900100001)(8676002)(81156014)(9686002)(110136003)(2906002)(7696004)(87936001)(5660300001)(6916009)(8936002)(97736004); DIR:OUT; SFP:1101; SCL:1; SRVR:VI1PR0802MB2175; H:VI1PR0802MB2176.eurprd08.prod.outlook.com; FPR:; SPF:None; PTR:InfoNoRecords; MX:1; A:1; LANG:en; spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-originalarrivaltime: 27 Oct 2016 13:37:15.0297 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR0802MB2175 X-MC-Unique: Edh7noqhOP-IfJotgY2nwA-1 X-IsSubscribed: yes Hi, During analysis, vect_slp checks if statements of a group are isomorphic to each other, specifically, all statements have to be isomorphic to the first one. Apparently, operands of commutative operators (PLUS_EXPR/MINUS_EXPR etc.) could be swapped when checking isomorphic property. Though vect_slp has basic support for such commutative operators, the related code is not properly implemented: 1) vect_build_slp_tree mixes operand swapping in the current slp tree node and operand swapping in its child slp tree nodes. 2) Operand swapping in the current slp tree is incorrect when vect_get_and_check_slp_defs has already committed to a fixed operand order. In addition, operand swapping for COND_EXPR is implemented in a wrong way (place) because: 3) vect_get_and_check_slp_defs swaps operands for COND_EXPR by changing comparison code after vect_build_slp_tree_1 checks the code consistency for the statement group. 4) vect_build_slp_tree_1 should support operand swapping for COND_EXPR while it doesn't. This patch addresses above issues. It supports COND_EXPR by recording swapping information in vect_build_slp_tree_1 and applies the swap in vect_get_check_slp_defs. It supports two types swapping: swapping and inverting. The patch also does refactoring so that operand swapping in child slp tree node and the current slp tree node are differentiated. With this patch, failures (gcc.dg/vect/slp-cond-3.c) revealed by previous COND_EXPR match.pd patches are resolved. Bootstrap and test on x86_64 and AArch64. Is it OK? Thanks, bin 2016-10-25 Bin Cheng * tree-vect-slp.c (vect_get_and_check_slp_defs): New parameter SWAP. Check slp defs for COND_EXPR by swapping/inverting operands if indicated by the new parameter SWAP. (vect_build_slp_tree_1): New parameter SWAP. Check COND_EXPR stmt is isomorphic to the first stmt via swapping/inverting. Store swap information in the new parameter SWAP. (vect_build_slp_tree): New local array SWAP and pass it to function vect_build_slp_tree_1. Cleanup result handlding code for function call to vect_get_and_check_slp_defs. Skip oeprand swapping if the order of operands has been fixed as indicated by SWAP[i]. diff --git a/gcc/tree-vect-slp.c b/gcc/tree-vect-slp.c index 5a611e4..1f2551d 100644 --- a/gcc/tree-vect-slp.c +++ b/gcc/tree-vect-slp.c @@ -207,14 +207,20 @@ vect_get_place_in_interleaving_chain (gimple *stmt, gimple *first_stmt) /* Get the defs for the rhs of STMT (collect them in OPRNDS_INFO), check that they are of a valid type and that they match the defs of the first stmt of - the SLP group (stored in OPRNDS_INFO). If there was a fatal error - return -1, if the error could be corrected by swapping operands of the - operation return 1, if everything is ok return 0. */ + the SLP group (stored in OPRNDS_INFO). This function tries to match stmts + by swapping operands of STMT when possible. Non-zero *SWAP indicates swap + is required for cond_expr stmts. Specifically, *SWAP is 1 if STMT is cond + and operands of comparison need to be swapped; *SWAP is 2 if STMT is cond + and code of comparison needs to be inverted. If there is any operand swap + in this function, *SWAP is set to non-zero value. + If there was a fatal error return -1; if the error could be corrected by + swapping operands of father node of this one, return 1; if everything is + ok return 0. */ -static int -vect_get_and_check_slp_defs (vec_info *vinfo, +static int +vect_get_and_check_slp_defs (vec_info *vinfo, unsigned char *swap, gimple *stmt, unsigned stmt_num, - vec *oprnds_info) + vec *oprnds_info) { tree oprnd; unsigned int i, number_of_oprnds; @@ -237,11 +243,12 @@ vect_get_and_check_slp_defs (vec_info *vinfo, { enum tree_code code = gimple_assign_rhs_code (stmt); number_of_oprnds = gimple_num_ops (stmt) - 1; + /* Swap can only be done for cond_expr if asked to, otherwise we + could result in different comparison code to the first stmt. */ if (gimple_assign_rhs_code (stmt) == COND_EXPR && COMPARISON_CLASS_P (gimple_assign_rhs1 (stmt))) { first_op_cond = true; - commutative = true; number_of_oprnds++; } else @@ -250,20 +257,24 @@ vect_get_and_check_slp_defs (vec_info *vinfo, else return -1; - bool swapped = false; + bool swapped = (*swap != 0); + gcc_assert (!swapped || first_op_cond); for (i = 0; i < number_of_oprnds; i++) { again: if (first_op_cond) { - if (i == 0 || i == 1) - oprnd = TREE_OPERAND (gimple_op (stmt, first_op_idx), - swapped ? !i : i); + /* Map indicating how operands of cond_expr should be swapped. */ + int maps[3][4] = {{0, 1, 2, 3}, {1, 0, 2, 3}, {0, 1, 3, 2}}; + int *map = maps[*swap]; + + if (i < 2) + oprnd = TREE_OPERAND (gimple_op (stmt, first_op_idx), map[i]); else - oprnd = gimple_op (stmt, first_op_idx + i - 1); + oprnd = gimple_op (stmt, map[i]); } else - oprnd = gimple_op (stmt, first_op_idx + (swapped ? !i : i)); + oprnd = gimple_op (stmt, first_op_idx + (swapped ? !i : i)); oprnd_info = (*oprnds_info)[i]; @@ -431,9 +442,25 @@ again: if (first_op_cond) { tree cond = gimple_assign_rhs1 (stmt); - swap_ssa_operands (stmt, &TREE_OPERAND (cond, 0), - &TREE_OPERAND (cond, 1)); - TREE_SET_CODE (cond, swap_tree_comparison (TREE_CODE (cond))); + enum tree_code code = TREE_CODE (cond); + + /* Swap. */ + if (*swap == 1) + { + swap_ssa_operands (stmt, &TREE_OPERAND (cond, 0), + &TREE_OPERAND (cond, 1)); + TREE_SET_CODE (cond, swap_tree_comparison (code)); + } + /* Invert. */ + else + { + swap_ssa_operands (stmt, gimple_assign_rhs2_ptr (stmt), + gimple_assign_rhs3_ptr (stmt)); + bool honor_nans = HONOR_NANS (TREE_OPERAND (cond, 0)); + code = invert_tree_comparison (TREE_CODE (cond), honor_nans); + gcc_assert (code != ERROR_MARK); + TREE_SET_CODE (cond, code); + } } else swap_ssa_operands (stmt, gimple_assign_rhs1_ptr (stmt), @@ -446,6 +473,7 @@ again: } } + *swap = swapped; return 0; } @@ -455,10 +483,17 @@ again: true if they are, otherwise return false and indicate in *MATCHES which stmts are not isomorphic to the first one. If MATCHES[0] is false then this indicates the comparison could not be - carried out or the stmts will never be vectorized by SLP. */ + carried out or the stmts will never be vectorized by SLP. + + Note COND_EXPR is possibly ismorphic to another one after swapping its + operands. Set SWAP[i] to 1 if stmt I is COND_EXPR and isomorphic to + the first stmt by swapping the two operands of comparison; set SWAP[i] + to 2 if stmt I is isormorphic to the first stmt by inverting the code + of comparison. Take A1 >= B1 ? X1 : Y1 as an exmple, it can be swapped + to (B1 <= A1 ? X1 : Y1); or be inverted to (A1 < B1) ? Y1 : X1. */ static bool -vect_build_slp_tree_1 (vec_info *vinfo, +vect_build_slp_tree_1 (vec_info *vinfo, unsigned char *swap, vec stmts, unsigned int group_size, unsigned nops, unsigned int *max_nunits, bool *matches, bool *two_operators) @@ -482,6 +517,7 @@ vect_build_slp_tree_1 (vec_info *vinfo, /* For every stmt in NODE find its def stmt/s. */ FOR_EACH_VEC_ELT (stmts, i, stmt) { + swap[i] = 0; matches[i] = false; if (dump_enabled_p ()) @@ -782,26 +818,44 @@ vect_build_slp_tree_1 (vec_info *vinfo, return false; } - if (rhs_code == COND_EXPR) - { - tree cond_expr = gimple_assign_rhs1 (stmt); + if (rhs_code == COND_EXPR) + { + tree cond_expr = gimple_assign_rhs1 (stmt); + enum tree_code cond_code = TREE_CODE (cond_expr); + enum tree_code swap_code = ERROR_MARK; + enum tree_code invert_code = ERROR_MARK; if (i == 0) first_cond_code = TREE_CODE (cond_expr); - else if (first_cond_code != TREE_CODE (cond_expr)) - { - if (dump_enabled_p ()) - { - dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, + else if (TREE_CODE_CLASS (cond_code) == tcc_comparison) + { + bool honor_nans = HONOR_NANS (TREE_OPERAND (cond_expr, 0)); + swap_code = swap_tree_comparison (cond_code); + invert_code = invert_tree_comparison (cond_code, honor_nans); + } + + if (first_cond_code == cond_code) + ; + /* Isomorphic can be achieved by swapping. */ + else if (first_cond_code == swap_code) + swap[i] = 1; + /* Isomorphic can be achieved by inverting. */ + else if (first_cond_code == invert_code) + swap[i] = 2; + else + { + if (dump_enabled_p ()) + { + dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, "Build SLP failed: different" " operation"); - dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, + dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0); - } + } /* Mismatch. */ continue; } - } + } } matches[i] = true; @@ -885,7 +939,8 @@ vect_build_slp_tree (vec_info *vinfo, return NULL; bool two_operators = false; - if (!vect_build_slp_tree_1 (vinfo, + unsigned char *swap = XALLOCAVEC (unsigned char, group_size); + if (!vect_build_slp_tree_1 (vinfo, swap, stmts, group_size, nops, &this_max_nunits, matches, &two_operators)) return NULL; @@ -905,18 +960,10 @@ vect_build_slp_tree (vec_info *vinfo, slp_oprnd_info oprnd_info; FOR_EACH_VEC_ELT (stmts, i, stmt) { - switch (vect_get_and_check_slp_defs (vinfo, stmt, i, &oprnds_info)) - { - case 0: - break; - case -1: - matches[0] = false; - vect_free_oprnd_info (oprnds_info); - return NULL; - case 1: - matches[i] = false; - break; - } + int res = vect_get_and_check_slp_defs (vinfo, &swap[i], + stmt, i, &oprnds_info); + if (res != 0) + matches[(res == -1) ? 0 : i] = false; } for (i = 0; i < group_size; ++i) if (!matches[i]) @@ -1040,7 +1087,8 @@ vect_build_slp_tree (vec_info *vinfo, operand order already. */ for (j = 0; j < group_size; ++j) if (!matches[j] - && STMT_VINFO_NUM_SLP_USES (vinfo_for_stmt (stmts[j])) != 0) + && (swap[j] != 0 + || STMT_VINFO_NUM_SLP_USES (vinfo_for_stmt (stmts[j])))) { if (dump_enabled_p ()) {