From patchwork Mon Mar 27 17:33:55 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 9647235 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 1DC20601D7 for ; Mon, 27 Mar 2017 17:38:30 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 0FC94283FF for ; Mon, 27 Mar 2017 17:38:30 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 04CC528414; Mon, 27 Mar 2017 17:38:30 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.3 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, RCVD_IN_DNSWL_HI, RCVD_IN_SORBS_SPAM, T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 26FB328408 for ; Mon, 27 Mar 2017 17:38:29 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751692AbdC0Rh2 (ORCPT ); Mon, 27 Mar 2017 13:37:28 -0400 Received: from mail-wr0-f195.google.com ([209.85.128.195]:34595 "EHLO mail-wr0-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751340AbdC0RhN (ORCPT ); Mon, 27 Mar 2017 13:37:13 -0400 Received: by mail-wr0-f195.google.com with SMTP id w43so12462276wrb.1 for ; Mon, 27 Mar 2017 10:36:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=yc91+dAq/B4MC7urAkLlpw1IMuIayT2Ond+R8sooKFY=; b=WVi7nVZ5MykJB8k0EzjM8D9l1vc1g2RzfVlyH0pJ1Pyahok3CTIc/UmXOgT6g3m2Ix oC39VOKTad4NFXGHkoM72I7cWFq+PucxmKZNufGli8Q+oxpneN4lmPjniIxXcrqqmQo0 xAHlX4hP8xAfasJ3/6FEd5w9vm/NWsCt/p0aEhaPpZyyUOnR7hFl3r+v/UTwmPHOs21u c1nxEQgJ+66iXO5mlpeTY4SRy8sEW3RA7prpEI95A/OBRHQz9c25TTAZs3EjqcIJ96E6 VEstKaJ3HPL1NxKhQQMxS12qyQYx4U3ZE32aYx5lpYoLAkSZnvrgb1Gz443sfNIaecLa LtlQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=yc91+dAq/B4MC7urAkLlpw1IMuIayT2Ond+R8sooKFY=; b=PQkGLeVVekeEFpN6vQSwLFpP5dFNp6BtnSAvTD5Gi8Rk7Ix586B2+ho2HRu/jvOeiQ cnwvcjzN+Jqjy2fXr4jqI3NqI3q9ZByIc2uYQbz+MP5cYY9s47xPspTp/2jULZiJSjbv DY/JHbwp+RDVqzgr7KpxfTMtYRxWK/UFm8SksQJIc7fBXbrXDMJxYXF6SM2pFBxfPHYE Nl/i5PFd9YrVsJkb2kmuD0kR4Jhc6tJBofxHOzn+C8bl2sot6t5yyJoF1qjprcdAJzc1 eBhdvOc5q/F3aoOUa9x9jHxZk27NK0dz6ODD1krGOnUQepUV+FjbWR78ToIoSlJ9Otd0 ygqw== X-Gm-Message-State: AFeK/H3dO2AowE1P8EIv1F6BQ3WrILZimzEmk7NcwVFrkp9Lu/98wgooGNNoL7IWwIZCjw== X-Received: by 10.223.165.85 with SMTP id j21mr20503115wrb.186.1490636178021; Mon, 27 Mar 2017 10:36:18 -0700 (PDT) Received: from localhost.localdomain ([2a02:a03f:802:b00:496:ae63:aebb:a034]) by smtp.gmail.com with ESMTPSA id e72sm304116wma.5.2017.03.27.10.36.16 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 27 Mar 2017 10:36:17 -0700 (PDT) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Christopher Li , Luc Van Oostenryck Subject: [PATCH v6 05/15] canonicalize compare instructions Date: Mon, 27 Mar 2017 19:33:55 +0200 Message-Id: <20170327173405.11405-6-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.12.0 In-Reply-To: <20170327173405.11405-1-luc.vanoostenryck@gmail.com> References: <20170327173405.11405-1-luc.vanoostenryck@gmail.com> Sender: linux-sparse-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Currently only commutative instructions are canonicalized (the "simpler" operands, often a constant, is forced, if present to be in the second operand). This improve CSE (more cases are considered as equivalent) and help to reduce the number of "pattern" to be handled at simplification. Do this also for compare instructions since in thsi case we can swap the order of the operands if at the same time we also swap the 'direction' on the comparison. Signed-off-by: Luc Van Oostenryck --- opcode.c | 20 +++---- opcode.h | 1 + simplify.c | 20 +++++-- validation/optim/canonical-cmp.c | 124 +++++++++++++++++++++++++++++++++++++++ 4 files changed, 151 insertions(+), 14 deletions(-) create mode 100644 validation/optim/canonical-cmp.c diff --git a/opcode.c b/opcode.c index 0aed1ca1f..102bef68d 100644 --- a/opcode.c +++ b/opcode.c @@ -23,14 +23,14 @@ #include "linearize.h" const struct opcode_table opcode_table[OP_LAST] = { - [OP_SET_EQ] = { .negate = OP_SET_NE, }, - [OP_SET_NE] = { .negate = OP_SET_EQ, }, - [OP_SET_LT] = { .negate = OP_SET_GE, }, - [OP_SET_LE] = { .negate = OP_SET_GT, }, - [OP_SET_GE] = { .negate = OP_SET_LT, }, - [OP_SET_GT] = { .negate = OP_SET_LE, }, - [OP_SET_B ] = { .negate = OP_SET_AE, }, - [OP_SET_BE] = { .negate = OP_SET_A , }, - [OP_SET_AE] = { .negate = OP_SET_B , }, - [OP_SET_A ] = { .negate = OP_SET_BE, }, + [OP_SET_EQ] = { .negate = OP_SET_NE, .swap = OP_SET_EQ, }, + [OP_SET_NE] = { .negate = OP_SET_EQ, .swap = OP_SET_NE, }, + [OP_SET_LT] = { .negate = OP_SET_GE, .swap = OP_SET_GT, }, + [OP_SET_LE] = { .negate = OP_SET_GT, .swap = OP_SET_GE, }, + [OP_SET_GE] = { .negate = OP_SET_LT, .swap = OP_SET_LE, }, + [OP_SET_GT] = { .negate = OP_SET_LE, .swap = OP_SET_LT, }, + [OP_SET_B ] = { .negate = OP_SET_AE, .swap = OP_SET_A , }, + [OP_SET_BE] = { .negate = OP_SET_A , .swap = OP_SET_AE, }, + [OP_SET_AE] = { .negate = OP_SET_B , .swap = OP_SET_BE, }, + [OP_SET_A ] = { .negate = OP_SET_BE, .swap = OP_SET_B , }, }; diff --git a/opcode.h b/opcode.h index 3a89de05e..4a9b102f2 100644 --- a/opcode.h +++ b/opcode.h @@ -4,6 +4,7 @@ extern const struct opcode_table { int negate:8; + int swap:8; } opcode_table[]; #endif diff --git a/simplify.c b/simplify.c index 90f51e2a9..21ed39d78 100644 --- a/simplify.c +++ b/simplify.c @@ -720,6 +720,16 @@ static int canonicalize_commutative(struct instruction *insn) return repeat_phase |= REPEAT_CSE; } +static int canonicalize_compare(struct instruction *insn) +{ + if (canonical_order(insn->src1, insn->src2)) + return 0; + + switch_pseudo(insn, &insn->src1, insn, &insn->src2); + insn->opcode = opcode_table[insn->opcode].swap; + return repeat_phase |= REPEAT_CSE; +} + static inline int simple_pseudo(pseudo_t pseudo) { return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM; @@ -1115,15 +1125,17 @@ int simplify_instruction(struct instruction *insn) canonicalize_commutative(insn); return simplify_binop(insn); + case OP_SET_LE: case OP_SET_GE: + case OP_SET_LT: case OP_SET_GT: + case OP_SET_B: case OP_SET_A: + case OP_SET_BE: case OP_SET_AE: + canonicalize_compare(insn); + /* fall through */ case OP_SUB: case OP_DIVU: case OP_DIVS: case OP_MODU: case OP_MODS: case OP_SHL: case OP_LSR: case OP_ASR: - case OP_SET_LE: case OP_SET_GE: - case OP_SET_LT: case OP_SET_GT: - case OP_SET_B: case OP_SET_A: - case OP_SET_BE: case OP_SET_AE: return simplify_binop(insn); case OP_NOT: case OP_NEG: diff --git a/validation/optim/canonical-cmp.c b/validation/optim/canonical-cmp.c new file mode 100644 index 000000000..19b416310 --- /dev/null +++ b/validation/optim/canonical-cmp.c @@ -0,0 +1,124 @@ +typedef signed int sint; +typedef unsigned int uint; + +sint seq(sint p, sint a) { return (123 == p) ? a : 0; } +sint sne(sint p, sint a) { return (123 != p) ? a : 0; } + +sint slt(sint p, sint a) { return (123 > p) ? a : 0; } +sint sle(sint p, sint a) { return (123 >= p) ? a : 0; } +sint sge(sint p, sint a) { return (123 <= p) ? a : 0; } +sint sgt(sint p, sint a) { return (123 < p) ? a : 0; } + +uint ueq(uint p, uint a) { return (123 == p) ? a : 0; } +uint une(uint p, uint a) { return (123 != p) ? a : 0; } + +uint ubt(uint p, uint a) { return (123 > p) ? a : 0; } +uint ube(uint p, uint a) { return (123 >= p) ? a : 0; } +uint uae(uint p, uint a) { return (123 <= p) ? a : 0; } +uint uat(uint p, uint a) { return (123 < p) ? a : 0; } + +/* + * check-name: canonical-cmp + * check-command: test-linearize -Wno-decl $file + * + * check-output-exclude: \$123, + * + * check-output-start +seq: +.L0: + + seteq.32 %r4 <- %arg1, $123 + select.32 %r5 <- %r4, %arg2, $0 + ret.32 %r5 + + +sne: +.L2: + + setne.32 %r11 <- %arg1, $123 + select.32 %r12 <- %r11, %arg2, $0 + ret.32 %r12 + + +slt: +.L4: + + setlt.32 %r18 <- %arg1, $123 + select.32 %r19 <- %r18, %arg2, $0 + ret.32 %r19 + + +sle: +.L6: + + setle.32 %r25 <- %arg1, $123 + select.32 %r26 <- %r25, %arg2, $0 + ret.32 %r26 + + +sge: +.L8: + + setge.32 %r32 <- %arg1, $123 + select.32 %r33 <- %r32, %arg2, $0 + ret.32 %r33 + + +sgt: +.L10: + + setgt.32 %r39 <- %arg1, $123 + select.32 %r40 <- %r39, %arg2, $0 + ret.32 %r40 + + +ueq: +.L12: + + seteq.32 %r45 <- %arg1, $123 + select.32 %r46 <- %r45, %arg2, $0 + ret.32 %r46 + + +une: +.L14: + + setne.32 %r50 <- %arg1, $123 + select.32 %r51 <- %r50, %arg2, $0 + ret.32 %r51 + + +ubt: +.L16: + + setb.32 %r55 <- %arg1, $123 + select.32 %r56 <- %r55, %arg2, $0 + ret.32 %r56 + + +ube: +.L18: + + setbe.32 %r60 <- %arg1, $123 + select.32 %r61 <- %r60, %arg2, $0 + ret.32 %r61 + + +uae: +.L20: + + setae.32 %r65 <- %arg1, $123 + select.32 %r66 <- %r65, %arg2, $0 + ret.32 %r66 + + +uat: +.L22: + + seta.32 %r70 <- %arg1, $123 + select.32 %r71 <- %r70, %arg2, $0 + ret.32 %r71 + + + * check-output-end + */