From patchwork Tue Aug 7 13:33:31 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vlad Lazar X-Patchwork-Id: 954517 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-483310-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=arm.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="Std6gr9P"; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=armh.onmicrosoft.com header.i=@armh.onmicrosoft.com header.b="SqpaBOVJ"; dkim-atps=neutral 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 41lFqD6BRBz9s0R for ; Tue, 7 Aug 2018 23:34:13 +1000 (AEST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to:cc :from:subject:message-id:date:mime-version:content-type :content-transfer-encoding; q=dns; s=default; b=xjjgViR9/gKDNNI7 t96NncMxtO/qHpJVLOxXaD0OkRViNtStIj9IeUUk2At0DernCD5/PfYhH1PWdkk6 NsRZymwQPLiFdEkvEZ/W0fwPPmfpe0NztUwIyO9khGUYtnjuR2gV1L4H0fFNYICZ VyKtpXcENiMpztShtAjO52zJM6M= 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:to:cc :from:subject:message-id:date:mime-version:content-type :content-transfer-encoding; s=default; bh=PmrzqTVefO03DaHQBAM69i 4VCKE=; b=Std6gr9Pdr0F/fZE2PPq7VTIlB63egfuEM8ZDcAVEKxdIkZih5XomF jMvmqGPmvFyw3wQIJh44S8+JxfB6UOZJFPTWyygnFsj+HWk/GLqHiiqxZerSZaIr /gx9hS/ZpsdeP/UDOqCLSvG/BMAzSPouNe0T71lBRoQpa2jB6kGTg= Received: (qmail 119855 invoked by alias); 7 Aug 2018 13:34:04 -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 119840 invoked by uid 89); 7 Aug 2018 13:34:04 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS, SPF_PASS autolearn=ham version=3.3.2 spammy=choices, PLUS_EXPR, plus_expr X-HELO: EUR03-AM5-obe.outbound.protection.outlook.com Received: from mail-eopbgr30067.outbound.protection.outlook.com (HELO EUR03-AM5-obe.outbound.protection.outlook.com) (40.107.3.67) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 07 Aug 2018 13:34:00 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector1-arm-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=dUq9iPxHV6Q6H7Wkr1ZKst+GzYXr7hHbl61dXBW22Ec=; b=SqpaBOVJIqIe5Go/ChtxFEu2mdUTyiSpX4DeldNYMwla6LfvYTQyVqhD9VTnmX8IebDkHmJjXkiRKso31+K+pwzkty3vyS+9+2nkur9oCksGYQEiOluT2bexXL5chm899Z3niUREVrs88d3CU5niL5Z8Lx5l6VKQB+vviBVshBQ= Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=Vlad.Lazar@arm.com; Received: from [10.2.206.48] (217.140.106.52) by AM5PR0801MB1636.eurprd08.prod.outlook.com (2603:10a6:203:39::18) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1017.15; Tue, 7 Aug 2018 13:33:53 +0000 To: "gcc-patches@gcc.gnu.org" Cc: nd , law@redhat.com, ian@airs.com, rguenther@suse.de From: Vlad Lazar Subject: [RFC][PATCH][mid-end] Optimize immediate choice in comparisons. Message-ID: Date: Tue, 7 Aug 2018 14:33:31 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1 MIME-Version: 1.0 Received-SPF: None (protection.outlook.com: arm.com does not designate permitted sender hosts) X-IsSubscribed: yes Hi. This patch optimises the choice of immediates in integer comparisons. Integer comparisons allow for different choices (e.g. a > b is equivalent to a >= b+1) and there are cases where an incremented/decremented immediate can be loaded into a register in fewer instructions. The cases are as follows: i) a > b or a >= b + 1 ii) a <= b or a < b + 1 iii) a >= b or a > b - 1 iv) a < b or a <= b - 1 For each comparison we check whether the equivalent can be performed in less instructions. This is done on a statement by statement basis, right before the GIMPLE statement is expanded to RTL. Therefore, it requires a correct implementation of the TARGET_INSN_COST hook. The change is general and it applies to any integer comparison, regardless of types or location. For example, on AArch64 for the following code: int foo (int x) { return x > 0xfefffffe; } it generates: mov w1, -16777217 cmp w0, w1 cset w0, cs instead of: mov w1, 65534 movk w1, 0xfeff, lsl 16 cmp w0, w1 cset w0, hi Bootstrapped and regtested on aarch64-none-linux-gnu, x86_64-pc-linux-gnu and there are no regressions. Thanks, Vlad gcc/testsuite/ Changelog for gcc/testsuite/Changelog 2018-07-30 Vlad Lazar * gcc.target/aarch64/imm_choice_comparison.c: New. gcc/ Changelog for gcc/Changelog 2018-07-30 Vlad Lazar * cfgexpand.c (optimize_immediate_choice): New. (can_optimize_immediate_p): Likewise. (validate_immediate_optimization): Likewise. (update_immediate): Likewise. (immediate_optimized_code): Likewise. diff --git a/gcc/cfgexpand.c b/gcc/cfgexpand.c index 9b91279282e1c6956c8b3699f13036c401ea1dcd..5b0a2e0cdb23f649336844506c8241428b3e6e7d 100644 --- a/gcc/cfgexpand.c +++ b/gcc/cfgexpand.c @@ -5423,6 +5423,157 @@ reorder_operands (basic_block bb) XDELETE (lattice); } +/* Helper function for update_immediate. Returns the adjusted conditional + code for the immediate choice optimization. See optimize_immediate_choice + for cases. */ + +static enum tree_code +immediate_optimized_code (enum tree_code code) +{ + switch (code) + { + case GT_EXPR: + return GE_EXPR; + case GE_EXPR: + return GT_EXPR; + case LT_EXPR: + return LE_EXPR; + case LE_EXPR: + return LT_EXPR; + default: + return code; + } +} + +/* Helper function for optimize_immediate_choice. It updates the immediate + and the subcode of the gimple statement. At the point of calling + the function we know that the optimization leads to fewer instructions. + stmt points to the gimple statement containing the comparison we wish to + optimize and to_add is the amount by which the immediate needs to be + adjusted (1 or -1). */ + +static void +update_immediate (gimple *stmt, int to_add) +{ + tree inc_dec = to_add == 1 ? build_one_cst (integer_type_node) : + build_minus_one_cst (integer_type_node); + + enum gimple_code code = gimple_code (stmt); + if (code == GIMPLE_COND) + { + gcond *gc = GIMPLE_CHECK2 (stmt); + tree rhs = gimple_cond_rhs (gc); + + /* Update the statement. */ + tree new_rhs = fold_build2 (PLUS_EXPR, TREE_TYPE (rhs), rhs, inc_dec); + gimple_cond_set_rhs (gc, new_rhs); + gc->subcode = immediate_optimized_code ((enum tree_code) gc->subcode); + } + if (code == GIMPLE_ASSIGN) + { + gassign *ga = GIMPLE_CHECK2 (stmt); + tree rhs2 = gimple_assign_rhs2 (ga); + + tree new_rhs2 = fold_build2 (PLUS_EXPR, TREE_TYPE (rhs2), rhs2, inc_dec); + gimple_assign_set_rhs2 (ga, new_rhs2); + ga->subcode = immediate_optimized_code ((enum tree_code) ga->subcode); + } +} + +/* Helper function for optimize_immediate_choice. It checks if the other + possible immediate leads to a lower rtx cost. to_add is the amount by + which the immediate needs to be adjusted (1 or -1). The function + returns 0 if there is no improvement and the amount by which the immediate + needs to be adjusted (1 or -1) otherwise. */ + +static int +validate_immediate_optimization (gimple *stmt, int to_add) +{ + tree tree_imm = gimple_code (stmt) == GIMPLE_COND ? gimple_cond_rhs (stmt) + : gimple_assign_rhs2 (stmt); + const_tree type = TREE_TYPE (tree_imm); + widest_int imm = wi::to_widest (tree_imm); + enum signop sgn = TYPE_UNSIGNED (type) ? UNSIGNED : SIGNED; + + /* Check for overflow/underflow in the case of signed values and + wrapping around in the case of unsigned values. If any occur + cancel the optimization. */ + + widest_int max_type = wi::to_widest (TYPE_MAX_VALUE (type)); + widest_int min_type = wi::to_widest (TYPE_MIN_VALUE (type)); + if ((wi::cmp (imm, max_type, sgn) == 0 && to_add == 1) + || (wi::cmp (imm, min_type, sgn) == 0 && to_add == -1)) + return 0; + + widest_int imm_modif = wi::add (imm, to_add); + + rtx reg = gen_reg_rtx (DImode); + rtx old_imm = GEN_INT (imm.to_shwi ()); + rtx new_imm = GEN_INT (imm_modif.to_shwi ()); + + rtx_insn *old_rtx = gen_move_insn (reg, old_imm); + rtx_insn *new_rtx = gen_move_insn (reg, new_imm); + + /* If the change is beneficial we can just propagate to_add further, + otherwise return 0 to cancel the optimization. */ + return insn_cost (old_rtx, true) > insn_cost (new_rtx, true) ? to_add : 0; +} + +/* Helper function for optimize_immediate_choice. Checks if the gimple + statement has the right shape for the optimization. */ + +static bool +can_optimize_immediate_p (const gimple *stmt) +{ + enum gimple_code code = gimple_code (stmt); + if (code != GIMPLE_ASSIGN && code != GIMPLE_COND) + return false; + + if (code == GIMPLE_ASSIGN + && (gimple_num_ops (stmt) != 3 + || TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)) + return false; + if (code == GIMPLE_COND && TREE_CODE (gimple_cond_rhs (stmt)) != INTEGER_CST) + return false; + + return true; +} + +/* Entry point for immediate choice optimization. It aims to choose + the simpler immediate in integer comparisons. The purpose of this + is to end up with an immediate which can be loaded into a register + in fewer moves, if possible. + + For each integer comparison there exists an equivalent choice: + i) a > b or a >= b + 1 + ii) a <= b or a < b + 1 + iii) a >= b or a > b - 1 + iv) a < b or a <= b - 1 + + Comparisons can only appear on the rhs of a GIMPLE_ASSIGN + or in a GIMPLE_COND. */ + +static void +optimize_immediate_choice (gimple *stmt) +{ + if (!can_optimize_immediate_p (stmt)) + return; + + /* Check if the other immediate available is preferable. */ + int to_add = 0; + if (stmt->subcode == GT_EXPR || stmt->subcode == LE_EXPR) + to_add = validate_immediate_optimization (stmt, 1); + + if (stmt->subcode == GE_EXPR || stmt->subcode == LT_EXPR) + to_add = validate_immediate_optimization (stmt, -1); + + if (!to_add) + return; + + /* Update the current statement. */ + update_immediate (stmt, to_add); +} + /* Expand basic block BB from GIMPLE trees to RTL. */ static basic_block @@ -5515,6 +5666,7 @@ expand_gimple_basic_block (basic_block bb, bool disable_tail_calls) basic_block new_bb; stmt = gsi_stmt (gsi); + optimize_immediate_choice (stmt); /* If this statement is a non-debug one, and we generate debug insns, then this one might be the last real use of a TERed diff --git a/gcc/testsuite/gcc.target/aarch64/imm_choice_comparison.c b/gcc/testsuite/gcc.target/aarch64/imm_choice_comparison.c new file mode 100644 index 0000000000000000000000000000000000000000..b30dcca88f44ca73fcb8202ea488888b365400c8 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/imm_choice_comparison.c @@ -0,0 +1,53 @@ +/* { dg-do compile } */ +/* { dg-options "-O2" } */ + +int +foo (int x) +{ + return x >= 0xfff01; +} + +int +GT (unsigned int x) +{ + return x > 0xfefffffe; +} + +/* Go from four moves to two. */ + +int +baz (long long x) +{ + return x <= 0x1999999999999998; +} + +int +LE (unsigned int x) +{ + return x <= 0xfefffffe; +} + +int +GE (long long x) +{ + return x >= 0xff000000; +} + +int +LT (int x) +{ + return x < 0xff000000; +} + +/* Optimize the immediate in conditionals. */ + +int check (int x, int y) +{ + if (x > y && GT (x)) + return 100; + + return x; +} + +/* baz produces one movk instruction. */ +/* { dg-final { scan-assembler-times "movk" 1 } } */