From patchwork Sun Nov 22 15:27:25 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 11923897 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id AB98FC5519F for ; Sun, 22 Nov 2020 15:27:39 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 74D8720773 for ; Sun, 22 Nov 2020 15:27:39 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="L4oFMKWd" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727728AbgKVP1j (ORCPT ); Sun, 22 Nov 2020 10:27:39 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59954 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727317AbgKVP1i (ORCPT ); Sun, 22 Nov 2020 10:27:38 -0500 Received: from mail-wm1-x32f.google.com (mail-wm1-x32f.google.com [IPv6:2a00:1450:4864:20::32f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CAE68C0613CF for ; Sun, 22 Nov 2020 07:27:36 -0800 (PST) Received: by mail-wm1-x32f.google.com with SMTP id p22so15516998wmg.3 for ; Sun, 22 Nov 2020 07:27:36 -0800 (PST) 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 :mime-version:content-transfer-encoding; bh=hmr00zOWFqVtU2ZJqQ1XXCDojaeX8UGyp+GyZR8LHTU=; b=L4oFMKWdmod+yJtpifXvWwb+wUAkc0DAbWg9abJzaYljfYz/ITPgt8Z6wI7hcvIr5v JUMCQVSsMtYZIuF1zr2S0ZqWONemHLxHl/T9xLiFC5rNOtQq+C1Phnhvz0nP29Pm/X8h ROprJ+/TVOIQl/MDIMAWXNEwceMCZXVI5f8z46VYKY19QqyX70z7UZUDf3ao44sC4L1W wvuZWi7QBxQKN1H7TWGAIANyqcn2PZZ1gNeur8IsyKWeTMK3j6yVux2Xe/Qr/h5d1NAV cjiHVgZ/ZUcAQvbxEr/D+YeVg3Gacvf4TG0sD6M0nqcLhg3mMxHreVVFd30cYND3gsne aIeg== 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:mime-version:content-transfer-encoding; bh=hmr00zOWFqVtU2ZJqQ1XXCDojaeX8UGyp+GyZR8LHTU=; b=dgoQIpCpp9CnPFtFK4b8/zDWO9uzma1PoKYVVJOgmWaqFDw2D5SiSLcNNJARbtYgyd EkV3wWQA5ILncVCXxLZe2nHO3n3rsvvgCrpT4YmhAJb5x30ZOYDmqWwWlLTJVwQrnFLX t/XrxcAfHxsNy2WtJA+pRgI7joXHOa3y/qYreD9jO1ubfu7ZBwf9l/50TxiBYBrFASGw CFkfeEBXWu9l3lM+pyYGpJzqEECPsSdLSJlv3F5b6U674WeRNWVSfyDJLGyDmjaLefsH Z2jbcUkT0Y2Q5eMfPvZsZECxZ+gq6CmNYZCAaLtND36vynv+oCEfFltEcdT4jbLBEfYW 6dxg== X-Gm-Message-State: AOAM532lbPwNXPPFfbvG/H0ZWG5UC5ya++UTNomShRKsSG3vGL4LDC0D FCRTwD1we9f+0sP6zH3bJbQ/boxId/E= X-Google-Smtp-Source: ABdhPJxSSb52z2ecip1BhTYfdqikT4xAGl64IJPDjaly0mjxR2DfpdGPt61Crpu/UuYIC/+lJRJg7g== X-Received: by 2002:a05:600c:2541:: with SMTP id e1mr20803299wma.185.1606058855288; Sun, 22 Nov 2020 07:27:35 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:b0e1:b041:18e2:46cf]) by smtp.gmail.com with ESMTPSA id k1sm13712265wrp.23.2020.11.22.07.27.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 22 Nov 2020 07:27:34 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 1/7] not: add testcases for canonicalization & simplification of negations Date: Sun, 22 Nov 2020 16:27:25 +0100 Message-Id: <20201122152731.10994-2-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201122152731.10994-1-luc.vanoostenryck@gmail.com> References: <20201122152731.10994-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org Signed-off-by: Luc Van Oostenryck --- validation/optim/canonical-arg.c | 20 ++++++++++++++++++++ validation/optim/canonical-not.c | 9 +++++++++ validation/optim/cse-arg01.c | 10 ++++++++++ validation/optim/cse-not01.c | 12 ++++++++++++ validation/optim/cse-not02.c | 12 ++++++++++++ validation/optim/cse-reg01.c | 10 ++++++++++ 6 files changed, 73 insertions(+) create mode 100644 validation/optim/canonical-arg.c create mode 100644 validation/optim/canonical-not.c create mode 100644 validation/optim/cse-arg01.c create mode 100644 validation/optim/cse-not01.c create mode 100644 validation/optim/cse-not02.c create mode 100644 validation/optim/cse-reg01.c diff --git a/validation/optim/canonical-arg.c b/validation/optim/canonical-arg.c new file mode 100644 index 000000000000..a8ecc9bd0083 --- /dev/null +++ b/validation/optim/canonical-arg.c @@ -0,0 +1,20 @@ +int def(void); + +int canon_arg_arg(int a, int b) +{ + return (a + b) == (b + a); +} + +int canon_arg_reg(int a) +{ + int b = def(); + return (a + b) == (b + a); +} + +/* + * check-name: canonical-arg + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-returns: 1 + */ diff --git a/validation/optim/canonical-not.c b/validation/optim/canonical-not.c new file mode 100644 index 000000000000..9698590fd245 --- /dev/null +++ b/validation/optim/canonical-not.c @@ -0,0 +1,9 @@ +int canon_not(int a, int b) { return (a & ~b) == (~b & a); } + +/* + * check-name: canonical-not + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-returns: 1 + */ diff --git a/validation/optim/cse-arg01.c b/validation/optim/cse-arg01.c new file mode 100644 index 000000000000..c3f2963ffdeb --- /dev/null +++ b/validation/optim/cse-arg01.c @@ -0,0 +1,10 @@ +int foo(int a, int b) { return (a < b) == (b > a); } + +/* + * check-name: cse-arg01 + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-returns: 1 + */ diff --git a/validation/optim/cse-not01.c b/validation/optim/cse-not01.c new file mode 100644 index 000000000000..f87123f14f13 --- /dev/null +++ b/validation/optim/cse-not01.c @@ -0,0 +1,12 @@ +int and(int a) { return (~a & a) == 0; } +int ior(int a) { return (~a | a) == ~0; } +int xor(int a) { return (~a ^ a) == ~0; } + +/* + * check-name: cse-not01 + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-returns: 1 + */ diff --git a/validation/optim/cse-not02.c b/validation/optim/cse-not02.c new file mode 100644 index 000000000000..aa54a375a9ea --- /dev/null +++ b/validation/optim/cse-not02.c @@ -0,0 +1,12 @@ +int and(int a, int b) { return ((a == b) & (a != b)) == 0; } +int ior(int a, int b) { return ((a == b) | (a != b)) == 1; } +int xor(int a, int b) { return ((a == b) ^ (a != b)) == 1; } + +/* + * check-name: cse-not02 + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-returns: 1 + */ diff --git a/validation/optim/cse-reg01.c b/validation/optim/cse-reg01.c new file mode 100644 index 000000000000..938858f4649b --- /dev/null +++ b/validation/optim/cse-reg01.c @@ -0,0 +1,10 @@ +int foo(int a, int b) { int x = a + b, y = ~b; return (x < y) == (y > x); } + +/* + * check-name: cse-reg01 + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-returns: 1 + */ From patchwork Sun Nov 22 15:27:26 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 11923903 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 6969BC56202 for ; Sun, 22 Nov 2020 15:27:40 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 3867220773 for ; Sun, 22 Nov 2020 15:27:40 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="iunR62yd" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727745AbgKVP1j (ORCPT ); Sun, 22 Nov 2020 10:27:39 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59958 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727317AbgKVP1j (ORCPT ); Sun, 22 Nov 2020 10:27:39 -0500 Received: from mail-wm1-x344.google.com (mail-wm1-x344.google.com [IPv6:2a00:1450:4864:20::344]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9235EC0613D3 for ; Sun, 22 Nov 2020 07:27:37 -0800 (PST) Received: by mail-wm1-x344.google.com with SMTP id c9so15530006wml.5 for ; Sun, 22 Nov 2020 07:27:37 -0800 (PST) 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 :mime-version:content-transfer-encoding; bh=99vJL0KZqnWj49eesnocy4L83k8E63+yml2GC2QpAM0=; b=iunR62yd0B2+E+/DU02N/LSIVJdw58uBbeD71DBIxWel9w3RsUFQPwYIfdGdxB949D fvdM/creWTjwmshuE8g7IMPHGsXm+XWnaS8KtUtsDe+6jFbg8gM3vyQ04wSp7tO9ePNR lr5A8nqSpmg8rEAzcks4/KdV+GKOUkLjtpNPiiVHX/cnsKTkgIS7tRJKnXoZOZ8k5I3b Wm9m8ocbrUmUaxLQdN+rmGiPR1vVDU+vSZvSOuPHI86VgK/0c7GXaPKPkA74T6lGRj+r TIxI0qVYsM43S1BfWUeXxZ+A2Vw3sPG9BhimrQUDiRzQ6UAr6ve3Bn4KgNP9h7/pl/HJ vLcQ== 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:mime-version:content-transfer-encoding; bh=99vJL0KZqnWj49eesnocy4L83k8E63+yml2GC2QpAM0=; b=iH2nXuI2G+cENL6y2KbWV7FBs42ET+k0fq+Hrt7ycMv03MpB9ArXKrNB+BhxVWRRyp mUixmCwt6b37pIyXvQ48G7x9TDQZUDXW0CnjtGkKSXOR4sJjK7LoqZYslJ/uxARvjzej bmrXIBczEfChFfbuQk5cRU3Q4urVhI5JqVIuk6FIMSKkS4+Cu7q8MhRzTYFUdBabEWsK rP0kx/9FatMCXMU3kCmLkjO3NbWsbdjt7OuhQU5kz0K89UjBphNJFzmeKyuYS1gu/NzI Or65/XvvZR8YkudL6TE4COf//z8s+Px9zsTDH0m8A0rmaMotNHUR6Nn+iQQT6LPtUoSM oPjg== X-Gm-Message-State: AOAM532M+uX2mj8emU369ThtpT9sTLtBbKtgrImOX/Cw0Yl/B0aNPzh3 qlhCFUbJwPceNJiFI9IhxdZLdakrgvk= X-Google-Smtp-Source: ABdhPJxeGpEoNzzJXJQWiVSQFlhVtRMAMrW2f60KoJ3kTB3EtML5IrpsQOSTY0MHEgpn8d1ZDVkpvw== X-Received: by 2002:a05:600c:2:: with SMTP id g2mr11945785wmc.156.1606058856085; Sun, 22 Nov 2020 07:27:36 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:b0e1:b041:18e2:46cf]) by smtp.gmail.com with ESMTPSA id k1sm13712265wrp.23.2020.11.22.07.27.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 22 Nov 2020 07:27:35 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 2/7] canon: put PSEUDO_ARGs in canonical order too Date: Sun, 22 Nov 2020 16:27:26 +0100 Message-Id: <20201122152731.10994-3-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201122152731.10994-1-luc.vanoostenryck@gmail.com> References: <20201122152731.10994-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org Currently, only binops containing PSEUDO_VAL or PSEUDO_SYM were put in canonical order. This means that binops containing only PSEUDO_ARGs or PSEUDO_REGs are not ordered. This is not directly a problem for CSE because commutativity is taken in account but: * more combination need to be checked during simplification * 'anti-commutative' operations like (a > b) & (b < a) are not recognized as such. So, as a first step, also take PSEUDO_ARGs in account when checking if operands are in canonical order. Signed-off-by: Luc Van Oostenryck --- simplify.c | 3 +++ validation/linear/pointer-arith32.c | 12 ++++++------ validation/linear/pointer-arith64.c | 10 +++++----- validation/optim/cse-arg01.c | 1 - 4 files changed, 14 insertions(+), 12 deletions(-) diff --git a/simplify.c b/simplify.c index a0e23d6de01f..c809b832afeb 100644 --- a/simplify.c +++ b/simplify.c @@ -1471,6 +1471,9 @@ static int canonical_order(pseudo_t p1, pseudo_t p2) if (p1->type == PSEUDO_SYM) return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL; + if (p1->type == PSEUDO_ARG) + return (p2->type == PSEUDO_ARG && p1->nr <= p2->nr) || p2->type == PSEUDO_VAL || p2->type == PSEUDO_SYM; + return 1; } diff --git a/validation/linear/pointer-arith32.c b/validation/linear/pointer-arith32.c index 531fd2324911..c0163a6f528b 100644 --- a/validation/linear/pointer-arith32.c +++ b/validation/linear/pointer-arith32.c @@ -42,7 +42,7 @@ cps: .L0: sext.32 %r2 <- (16) %arg2 - add.32 %r5 <- %arg1, %r2 + add.32 %r5 <- %r2, %arg1 ret.32 %r5 @@ -51,7 +51,7 @@ ipss: sext.32 %r10 <- (16) %arg2 mul.32 %r11 <- %r10, $4 - add.32 %r14 <- %arg1, %r11 + add.32 %r14 <- %r11, %arg1 ret.32 %r14 @@ -60,7 +60,7 @@ ipus: zext.32 %r19 <- (16) %arg2 mul.32 %r20 <- %r19, $4 - add.32 %r23 <- %arg1, %r20 + add.32 %r23 <- %r20, %arg1 ret.32 %r23 @@ -68,7 +68,7 @@ cpq: .L6: trunc.32 %r28 <- (64) %arg2 - add.32 %r31 <- %arg1, %r28 + add.32 %r31 <- %r28, %arg1 ret.32 %r31 @@ -77,7 +77,7 @@ ipq_ref: trunc.32 %r37 <- (64) %arg2 mul.32 %r38 <- %r37, $4 - add.32 %r39 <- %arg1, %r38 + add.32 %r39 <- %r38, %arg1 ret.32 %r39 @@ -86,7 +86,7 @@ ipq: trunc.32 %r43 <- (64) %arg2 mul.32 %r44 <- %r43, $4 - add.32 %r47 <- %arg1, %r44 + add.32 %r47 <- %r44, %arg1 ret.32 %r47 diff --git a/validation/linear/pointer-arith64.c b/validation/linear/pointer-arith64.c index dad10331b297..7f1aac56bfc2 100644 --- a/validation/linear/pointer-arith64.c +++ b/validation/linear/pointer-arith64.c @@ -35,7 +35,7 @@ cps: .L0: sext.64 %r2 <- (16) %arg2 - add.64 %r5 <- %arg1, %r2 + add.64 %r5 <- %r2, %arg1 ret.64 %r5 @@ -44,7 +44,7 @@ ipss: sext.64 %r10 <- (16) %arg2 mul.64 %r11 <- %r10, $4 - add.64 %r14 <- %arg1, %r11 + add.64 %r14 <- %r11, %arg1 ret.64 %r14 @@ -53,7 +53,7 @@ ipus: zext.64 %r19 <- (16) %arg2 mul.64 %r20 <- %r19, $4 - add.64 %r23 <- %arg1, %r20 + add.64 %r23 <- %r20, %arg1 ret.64 %r23 @@ -62,7 +62,7 @@ ipsi: sext.64 %r28 <- (32) %arg2 mul.64 %r29 <- %r28, $4 - add.64 %r32 <- %arg1, %r29 + add.64 %r32 <- %r29, %arg1 ret.64 %r32 @@ -71,7 +71,7 @@ ipui: zext.64 %r37 <- (32) %arg2 mul.64 %r38 <- %r37, $4 - add.64 %r41 <- %arg1, %r38 + add.64 %r41 <- %r38, %arg1 ret.64 %r41 diff --git a/validation/optim/cse-arg01.c b/validation/optim/cse-arg01.c index c3f2963ffdeb..3e3e141aa1fb 100644 --- a/validation/optim/cse-arg01.c +++ b/validation/optim/cse-arg01.c @@ -3,7 +3,6 @@ int foo(int a, int b) { return (a < b) == (b > a); } /* * check-name: cse-arg01 * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-returns: 1 From patchwork Sun Nov 22 15:27:27 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 11923895 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id E187AC63697 for ; Sun, 22 Nov 2020 15:27:39 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id A129820776 for ; Sun, 22 Nov 2020 15:27:39 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="RyXzgDSL" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727740AbgKVP1j (ORCPT ); Sun, 22 Nov 2020 10:27:39 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59962 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727646AbgKVP1i (ORCPT ); Sun, 22 Nov 2020 10:27:38 -0500 Received: from mail-wm1-x341.google.com (mail-wm1-x341.google.com [IPv6:2a00:1450:4864:20::341]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 657BFC061A4A for ; Sun, 22 Nov 2020 07:27:38 -0800 (PST) Received: by mail-wm1-x341.google.com with SMTP id 10so15530396wml.2 for ; Sun, 22 Nov 2020 07:27:38 -0800 (PST) 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 :mime-version:content-transfer-encoding; bh=dW9vlsLOdOZmbNrzdKKE/u+wafhEWcahlRHi87i9YIY=; b=RyXzgDSLsFIdOSuwZ9EkxnpZAvThSrLgvbg7XQrbXQj2K97ENTc0Pp0tyZieHqg3IR EpaTkiqD7WUUOdIXScznqsv+cTUm9xh2BwL/mrSfpchpnu53J+UNE+hZItULy3D6u1Vn uJNniUB5kU0XK9D3kWrABUoikCnbW+sZXuVXt5Iv9vBvGWO4B/HpnjcDQqU6yXzUtEz2 QSwCd9j5QJwx0/a4k4S3EPfZGTcc1nNUIRH1HHGEYK/0Y35DwM8o1/rnGIdq4KxpXBLm X9MUXc6YOBPlM3aW0UomyHSsmoYydbEXCOADErp4DNG/gsuJ/ZAqsgy9QwHRJt3E/3wr y3lQ== 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:mime-version:content-transfer-encoding; bh=dW9vlsLOdOZmbNrzdKKE/u+wafhEWcahlRHi87i9YIY=; b=cgxfw3ECS59saLQ1P+Sk+uaJWRsl15ycS53fdLSPKv5H4/wmXNXpLMDzXPM/nzsthN PSdF57BZtHJcz9HdXDRVPcDW+eVszkvKIQ+0h21I4U5T7fyNGCSA8FJIg3i8la+xwj1+ 2GjF6zpfdgAHmJ+j3sCX4UBCNLY4JwTovsbMrMDlwoxML8kFuPU+dyg1ea33zUk57b5L VBXqoL8OZdP8P6laAxo7oxNtPd5y61y4Fl9F0NWRYLesWrCl5GxmA9zyC8neiN5kCv0N F8hS7XTk7MSzLFtNa5aBWh2EzFB9I1kMmbks5E04Oe8D3ArdJwYtzx2dVizTYmufA65t E+gg== X-Gm-Message-State: AOAM530ZxoonlD3Q/loD3kMoTkupm9XvTpdK9ku0DWEuHrAK8U/EidhO kugMt4ZR1Cdw4ppVLo02Eda7AFvOPzc= X-Google-Smtp-Source: ABdhPJxkjfHvIe0AlOpBLX5Smtofv5ikGv1hno+GizV4ehr2ynTJAI2ATuXTu0O0f9+PLT5CFbe/pA== X-Received: by 2002:a1c:98cd:: with SMTP id a196mr19789066wme.42.1606058856913; Sun, 22 Nov 2020 07:27:36 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:b0e1:b041:18e2:46cf]) by smtp.gmail.com with ESMTPSA id k1sm13712265wrp.23.2020.11.22.07.27.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 22 Nov 2020 07:27:36 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 3/7] canon: put PSEUDO_REGs in canonical order too Date: Sun, 22 Nov 2020 16:27:27 +0100 Message-Id: <20201122152731.10994-4-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201122152731.10994-1-luc.vanoostenryck@gmail.com> References: <20201122152731.10994-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org Currently, only binops containing PSEUDO_VAL, SYM or ARG were put in canonical order. This means that binops containing only PSEUDO_REGs are not ordered. This is not directly a problem for CSE because commutativity is taken in account but: * more combination need to be checked during simplification * 'anti-commutative' operations like (a > b) & (b < a) are not recognized as such. So, take PSEUDO_REGs in account when checking if operands are in canonical order. Signed-off-by: Luc Van Oostenryck --- simplify.c | 3 +++ validation/optim/cse-reg01.c | 1 - 2 files changed, 3 insertions(+), 1 deletion(-) diff --git a/simplify.c b/simplify.c index c809b832afeb..ee485798148b 100644 --- a/simplify.c +++ b/simplify.c @@ -1474,6 +1474,9 @@ static int canonical_order(pseudo_t p1, pseudo_t p2) if (p1->type == PSEUDO_ARG) return (p2->type == PSEUDO_ARG && p1->nr <= p2->nr) || p2->type == PSEUDO_VAL || p2->type == PSEUDO_SYM; + if (p1->type == PSEUDO_REG) + return (p2->type == PSEUDO_REG && p1->nr <= p2->nr) || p2->type == PSEUDO_VAL || p2->type == PSEUDO_SYM || p2->type == PSEUDO_ARG; + return 1; } diff --git a/validation/optim/cse-reg01.c b/validation/optim/cse-reg01.c index 938858f4649b..3ea283d35368 100644 --- a/validation/optim/cse-reg01.c +++ b/validation/optim/cse-reg01.c @@ -3,7 +3,6 @@ int foo(int a, int b) { int x = a + b, y = ~b; return (x < y) == (y > x); } /* * check-name: cse-reg01 * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-returns: 1 From patchwork Sun Nov 22 15:27:28 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 11923901 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id A9D2AC63798 for ; Sun, 22 Nov 2020 15:27:40 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 77E7D20773 for ; Sun, 22 Nov 2020 15:27:40 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="EVDA5BtI" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727777AbgKVP1k (ORCPT ); Sun, 22 Nov 2020 10:27:40 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59964 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727646AbgKVP1j (ORCPT ); Sun, 22 Nov 2020 10:27:39 -0500 Received: from mail-wm1-x342.google.com (mail-wm1-x342.google.com [IPv6:2a00:1450:4864:20::342]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 2C79AC0613CF for ; Sun, 22 Nov 2020 07:27:39 -0800 (PST) Received: by mail-wm1-x342.google.com with SMTP id d142so15517727wmd.4 for ; Sun, 22 Nov 2020 07:27:39 -0800 (PST) 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 :mime-version:content-transfer-encoding; bh=47ZLYZ+qbCUuft6A6B4WnAnhMeO/AyT4HtLyQ+HmHkw=; b=EVDA5BtIKaAYDN/JUyntLShZ5lqUThJqQXHNXmIXEYWGE4KXEA99wbnh6SHSZziaEg 3aEbpPaolYbomet2rlfJpVNM+1Si5XvY7v05YKfmo11JyyoDHUVyVmrMUaUPnXRyBVmZ aRcNfuVwj81ZkTnDjlJ+pyiiZ8sRQnUnpA8bd/ujLytvA2J5jBlpaK0CTyMIocDiJTjI 1HVpZiMb23czK2AhDslBk586Hkwdg7nO2Abm97MXTiVgyOppccJ2aNN4PTVbFLnpIpR4 7IBD+ppXWVQPoXD+BH+25HpqNAD/9n8+hVmaWn93PRUOoUdn+j/oSV2w3Buu/U7fR/SP yHKg== 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:mime-version:content-transfer-encoding; bh=47ZLYZ+qbCUuft6A6B4WnAnhMeO/AyT4HtLyQ+HmHkw=; b=uoWIxpFXwXYWonrqBJ7Xuh8WscXGU8/Ub2NN417ww97a9cemqhw5E7nOUNMFHuGibo 66U99Xv1nW9T7cmzdI02Q6uPGG+fBdC7NYnhbNZRR+CJqhXBDYazhHsYMcPXDBJMeXAe iLT0/zJgU8HYar4Qx0TNRiOhNqHUTDOafagjxqF63UqCyvXBmS32Db9Y57e7092Ts9xX Zdp5yOod0ZkJzETF82DphzoZ6SJ92z/wfD940pCmmFT6xaVdzx0fkoqhsxCAgfOmadZA RxiZzPc1nkGiS0092ARIf2bAxIZ5eEPSctRfjf08/Enw+Gbm2wUTPRIFCxg5xUXme558 ejBA== X-Gm-Message-State: AOAM532/KykprsU7wPUILtE1MSFPnNgci6Za6swbeIoMTJ8WTWa/UNfV za3OG8KJmrgCBZH6tDToB2EIq5f5XH0= X-Google-Smtp-Source: ABdhPJxmCz6mxzEJ1Y0VU1/tX4/A7w35SkDoSnWNXb3R8Uh0383fUO0N+tGdu/APFMjwtAPUhq79EQ== X-Received: by 2002:a1c:a706:: with SMTP id q6mr19228997wme.2.1606058857737; Sun, 22 Nov 2020 07:27:37 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:b0e1:b041:18e2:46cf]) by smtp.gmail.com with ESMTPSA id k1sm13712265wrp.23.2020.11.22.07.27.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 22 Nov 2020 07:27:37 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 4/7] canon: simplify calculation of canonical order Date: Sun, 22 Nov 2020 16:27:28 +0100 Message-Id: <20201122152731.10994-5-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201122152731.10994-1-luc.vanoostenryck@gmail.com> References: <20201122152731.10994-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org The calculation of the canonical order is currently somehow complicated. Fix this by reordering the definition of the different type of pseudos so that they are already in canonical order and just comparing the types to determine the order. Signed-off-by: Luc Van Oostenryck --- linearize.h | 4 ++-- simplify.c | 40 +++++++++++++++++++++++++++------------- 2 files changed, 29 insertions(+), 15 deletions(-) diff --git a/linearize.h b/linearize.h index 31c754e200c2..2c548d43526f 100644 --- a/linearize.h +++ b/linearize.h @@ -24,11 +24,11 @@ DECLARE_PTRMAP(phi_map, struct symbol *, pseudo_t); enum pseudo_type { PSEUDO_VOID, PSEUDO_UNDEF, + PSEUDO_PHI, PSEUDO_REG, + PSEUDO_ARG, PSEUDO_SYM, PSEUDO_VAL, - PSEUDO_ARG, - PSEUDO_PHI, }; struct pseudo { diff --git a/simplify.c b/simplify.c index ee485798148b..203472972bca 100644 --- a/simplify.c +++ b/simplify.c @@ -1462,22 +1462,36 @@ static int switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instru return REPEAT_CSE; } +/// +// check if the given pseudos are in canonical order +// +// The canonical order is VOID < UNDEF < PHI < REG < ARG < SYM < VAL +// The rationale is: +// * VALs at right (they don't need a definition) +// * REGs at left (they need a defining instruction) +// * SYMs & ARGs between REGs & VALs +// * REGs & ARGs are ordered between themselves by their internal number +// * SYMs are ordered between themselves by address +// * VOID, UNDEF and PHI are uninteresting (but VOID should have type 0) static int canonical_order(pseudo_t p1, pseudo_t p2) { - /* symbol/constants on the right */ - if (p1->type == PSEUDO_VAL) - return p2->type == PSEUDO_VAL; - - if (p1->type == PSEUDO_SYM) - return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL; - - if (p1->type == PSEUDO_ARG) - return (p2->type == PSEUDO_ARG && p1->nr <= p2->nr) || p2->type == PSEUDO_VAL || p2->type == PSEUDO_SYM; + int t1 = p1->type; + int t2 = p2->type; - if (p1->type == PSEUDO_REG) - return (p2->type == PSEUDO_REG && p1->nr <= p2->nr) || p2->type == PSEUDO_VAL || p2->type == PSEUDO_SYM || p2->type == PSEUDO_ARG; - - return 1; + /* symbol/constants on the right */ + if (t1 < t2) + return 1; + if (t1 > t2) + return 0; + switch (t1) { + case PSEUDO_SYM: + return p1->sym <= p2->sym; + case PSEUDO_REG: + case PSEUDO_ARG: + return p1->nr <= p2->nr; + default: + return 1; + } } static int canonicalize_commutative(struct instruction *insn) From patchwork Sun Nov 22 15:27:29 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 11923899 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 08A04C6379D for ; Sun, 22 Nov 2020 15:27:41 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C332720773 for ; Sun, 22 Nov 2020 15:27:40 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Q14tuRKP" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727646AbgKVP1k (ORCPT ); Sun, 22 Nov 2020 10:27:40 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59968 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727317AbgKVP1k (ORCPT ); Sun, 22 Nov 2020 10:27:40 -0500 Received: from mail-wr1-x444.google.com (mail-wr1-x444.google.com [IPv6:2a00:1450:4864:20::444]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id DD6CDC0613D3 for ; Sun, 22 Nov 2020 07:27:39 -0800 (PST) Received: by mail-wr1-x444.google.com with SMTP id 64so2579414wra.11 for ; Sun, 22 Nov 2020 07:27:39 -0800 (PST) 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 :mime-version:content-transfer-encoding; bh=e3/QE1edvmloZ71nFb9phi4Ljg6NQPZDU9YiAutsAMQ=; b=Q14tuRKPqxfaut1N8Bolv0wuhpoET7JRHTjngHv00uYoZPyo1Nc/MWW1VPtYAbWXaq MTL8ILI/Zx48f7AMcAFv9/+RGvgzqHfg8+sCIhk7StYJfCB5izilnTlTKiBA8cdb8IUO hQRTL81lNv5na48QiDvnCfA4r7oQ8IS1yoCSkL3jx6PvE/k81bHwihNrKLVs0wh18o0T 2hGpTGkHCmtDFErgtgcMnNWqtHdj0hSqmZvPUghWRdwYfRpGzBZQ1Qm02rzt2Iv/XSVV J6BSOGgEtvSN5F4aFjYIU1HYEaERnlXAgTU+Q71jWa0cHN+c/zvEFfFCNLK5RozwpBI+ appg== 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:mime-version:content-transfer-encoding; bh=e3/QE1edvmloZ71nFb9phi4Ljg6NQPZDU9YiAutsAMQ=; b=ec4hcp+pBm8mkHqW094osRFX4xOj8prXI5dr3kki4NvEefolWap5P4wQguL7LZX+55 BOmqfzIlX+iX1tOJf6aijak7+OeDCtTswGF4cgGNAsu/zBbYD3sGSLp7RAHihHkuem3N jpcnnhbHhIzZ0f9apgjwoC99wle0XnT705Do7gkwW4rhHewlRqHdCb4Yohx+OsgLUdK7 BDseO2yS7C5e9El8c2bqS9rU+yrYHnhXHPawpPlLMCe59zXDnDEWjC52nsN9jRBuz7a5 glcfQewYsA0f/PDs8E3t3+5vrVVhZC5Jn3DCrkWweON7p4lcX0r3Qjs2Ie1gm3de4va8 SDiw== X-Gm-Message-State: AOAM532J3CYXYUJWOx3sVRMxxw4jqsyZcazcHv74RMBhfBb7Q7QLZLsJ C9SoYTgtK2K5pZ+EVbC39Bqsaz7CmuY= X-Google-Smtp-Source: ABdhPJxjMFa+u/ZevIaAhufBRKc5QqmerqGf9mwTu5VJg579r4kS/StSF96L8UVUVB8XBuePIxCBeQ== X-Received: by 2002:adf:f102:: with SMTP id r2mr7786542wro.315.1606058858515; Sun, 22 Nov 2020 07:27:38 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:b0e1:b041:18e2:46cf]) by smtp.gmail.com with ESMTPSA id k1sm13712265wrp.23.2020.11.22.07.27.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 22 Nov 2020 07:27:38 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 5/7] opcode: add helpers opcode_negate() & opcode_swap() Date: Sun, 22 Nov 2020 16:27:29 +0100 Message-Id: <20201122152731.10994-6-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201122152731.10994-1-luc.vanoostenryck@gmail.com> References: <20201122152731.10994-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org Signed-off-by: Luc Van Oostenryck --- opcode.h | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/opcode.h b/opcode.h index 1524272f0320..b74ba02d94bd 100644 --- a/opcode.h +++ b/opcode.h @@ -32,6 +32,16 @@ extern const struct opcode_table { } opcode_table[]; +static inline int opcode_negate(int opcode) +{ + return opcode_table[opcode].negate; +} + +static inline int opcode_swap(int opcode) +{ + return opcode_table[opcode].swap; +} + static inline int opcode_float(int opcode, struct symbol *type) { if (!type || !is_float_type(type)) From patchwork Sun Nov 22 15:27:30 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 11923905 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id EBBBCC63697 for ; Sun, 22 Nov 2020 15:27:41 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id B432720773 for ; Sun, 22 Nov 2020 15:27:41 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="P9TL5kMy" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727859AbgKVP1l (ORCPT ); Sun, 22 Nov 2020 10:27:41 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59974 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727317AbgKVP1l (ORCPT ); Sun, 22 Nov 2020 10:27:41 -0500 Received: from mail-wr1-x443.google.com (mail-wr1-x443.google.com [IPv6:2a00:1450:4864:20::443]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id BB271C0613CF for ; Sun, 22 Nov 2020 07:27:40 -0800 (PST) Received: by mail-wr1-x443.google.com with SMTP id r17so16045431wrw.1 for ; Sun, 22 Nov 2020 07:27:40 -0800 (PST) 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 :mime-version:content-transfer-encoding; bh=oDGqLs35aEjYeKpnafqEha/8dZETW9wL39KF/lxxmH4=; b=P9TL5kMyMIszzdk/uq/IOtsIuFVxVn33KS3T/Tem2KwoxpuyhUVyRtZxvWGqo0nIyQ LEYusfi0CaQEPBUTsOarr51+G78x1cPDlxho7nQcz2AV0vfdvxIB2pvntkwGlPQQCWoA LGMWLmnZmYQqmYfYh/Avcq+ZlxwBfo174OSy5GJkFhtMCLhrnC1cr/3MQ3gU3Zk3d7Hu ukLyvdMrkDm37r/x/reADcKtZThzSULoWagvebxO/UcMLh4m9uetSuv5bXoXMGoHmuzU tSIhzJnVFwY9THj4bUZbh5YpthNG9F1qq8/evr8A0YZyP/kqE0aal36bRdiLGRIu1yNM jI0Q== 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:mime-version:content-transfer-encoding; bh=oDGqLs35aEjYeKpnafqEha/8dZETW9wL39KF/lxxmH4=; b=AvpP40coCwPLeEqNBn39xyZ6WacWnDZFjNeZSfuPzpKpyn4awTMsm7axZVwvBnIH+3 6JaSquFq28xAaZHM/t8+lRMfUWj5fsqxSZCwa6PdxqHs59C3Y0JGwM/mRGmsf7mA7lje +3OE86deutY4XWr8Xapvf3+ytd0xZ2xy3XxikVGXPTUKBq+2DUqouBRCG/eaSkQ6n9bT VyQygMdgG9ZnpdcFA1TZf6edfAePTcuDV0wVvkNGCVQ8bTL0+ZC5lkhRbvyT16Hcj5Jt 8srrA6NgMKLNMLhCMak6SZvMjTuyfIW3uqinYYmCdThke+4C1fCXZyBfnjeGkeTjRnR2 e8gQ== X-Gm-Message-State: AOAM532fxj2hYSxMrnAaB0+8/FEF0pbYuUsoZlxWgug6POQ09c8RXOP/ ehrE2DIAgpLyuNpuwBmgU2WMTOU1BVI= X-Google-Smtp-Source: ABdhPJyq+Pnm3GiLErpJJMcOutlWhpLzgoZvsmM98AFByIii5bwopT7bdTw9Lb6HC9tO2e2dNn6C9g== X-Received: by 2002:a5d:66d2:: with SMTP id k18mr25180198wrw.327.1606058859318; Sun, 22 Nov 2020 07:27:39 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:b0e1:b041:18e2:46cf]) by smtp.gmail.com with ESMTPSA id k1sm13712265wrp.23.2020.11.22.07.27.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 22 Nov 2020 07:27:38 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 6/7] not: simplify (~x {&,|,^} x) --> {0,~0,~0} Date: Sun, 22 Nov 2020 16:27:30 +0100 Message-Id: <20201122152731.10994-7-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201122152731.10994-1-luc.vanoostenryck@gmail.com> References: <20201122152731.10994-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org Simplify bitwise operations on a pseudo and its complement into 0 (for &) or ~0 for (| and ^). Signed-off-by: Luc Van Oostenryck --- simplify.c | 66 ++++++++++++++++++++++++++++++++++-- validation/optim/cse-not01.c | 1 - 2 files changed, 63 insertions(+), 4 deletions(-) diff --git a/simplify.c b/simplify.c index 203472972bca..b41c155735d1 100644 --- a/simplify.c +++ b/simplify.c @@ -1630,6 +1630,66 @@ static int simplify_compare(struct instruction *insn) return 0; } +static int simplify_and_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2) +{ + struct instruction *def; + pseudo_t src1 = *p1; + + switch (DEF_OPCODE(def, src1)) { + case OP_NOT: + if (def->src == *p2) + return replace_with_value(insn, 0); + break; + } + return 0; +} + +static int simplify_and(struct instruction *insn) +{ + return simplify_and_one_side(insn, &insn->src1, &insn->src2) || + simplify_and_one_side(insn, &insn->src2, &insn->src1); +} + +static int simplify_ior_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2) +{ + struct instruction *def; + pseudo_t src1 = *p1; + + switch (DEF_OPCODE(def, src1)) { + case OP_NOT: + if (def->src == *p2) + return replace_with_value(insn, bits_mask(insn->size)); + break; + } + return 0; +} + +static int simplify_ior(struct instruction *insn) +{ + return simplify_ior_one_side(insn, &insn->src1, &insn->src2) || + simplify_ior_one_side(insn, &insn->src2, &insn->src1); +} + +static int simplify_xor_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2) +{ + struct instruction *def; + pseudo_t src1 = *p1; + + switch (DEF_OPCODE(def, src1)) { + case OP_NOT: + if (def->src == *p2) + return replace_with_value(insn, bits_mask(insn->size)); + break; + } + return 0; +} + +static int simplify_xor(struct instruction *insn) +{ + return simplify_xor_one_side(insn, &insn->src1, &insn->src2) || + simplify_xor_one_side(insn, &insn->src2, &insn->src1); +} + static int simplify_constant_unop(struct instruction *insn) { long long val = insn->src1->value; @@ -2162,10 +2222,10 @@ int simplify_instruction(struct instruction *insn) switch (insn->opcode) { case OP_ADD: return simplify_add(insn); case OP_SUB: return simplify_sub(insn); + case OP_AND: return simplify_and(insn); + case OP_OR: return simplify_ior(insn); + case OP_XOR: return simplify_xor(insn); case OP_MUL: - case OP_AND: - case OP_OR: - case OP_XOR: case OP_SHL: case OP_LSR: case OP_ASR: diff --git a/validation/optim/cse-not01.c b/validation/optim/cse-not01.c index f87123f14f13..ea1bb7cf25d4 100644 --- a/validation/optim/cse-not01.c +++ b/validation/optim/cse-not01.c @@ -5,7 +5,6 @@ int xor(int a) { return (~a ^ a) == ~0; } /* * check-name: cse-not01 * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-returns: 1 From patchwork Sun Nov 22 15:27:31 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 11923907 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id BCD2EC6379F for ; Sun, 22 Nov 2020 15:27:42 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 85C1420773 for ; Sun, 22 Nov 2020 15:27:42 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="K6hRn/gj" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727876AbgKVP1m (ORCPT ); Sun, 22 Nov 2020 10:27:42 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59978 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727317AbgKVP1l (ORCPT ); Sun, 22 Nov 2020 10:27:41 -0500 Received: from mail-wm1-x342.google.com (mail-wm1-x342.google.com [IPv6:2a00:1450:4864:20::342]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8BBB5C0613CF for ; Sun, 22 Nov 2020 07:27:41 -0800 (PST) Received: by mail-wm1-x342.google.com with SMTP id c9so15530113wml.5 for ; Sun, 22 Nov 2020 07:27:41 -0800 (PST) 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 :mime-version:content-transfer-encoding; bh=Zltb2qLLAHtwKEbB3MDd2Q4e9WUZbVZ+eHiHjUTpFQw=; b=K6hRn/gjKJq711s95wMK2hXdueFWQP8HodgZW0aUJ0cKRF2goGN4U/NprCXzcRWGcb YP+nruKdzyOJcrCoFh2huXrogs0aEuYeqgdLF5l5/VwI4KYvMhdvDzwvQ/4Pg6Y+Cwji CXiytIaFK1Z5QyrccWcMbzp0uRppLcN6QJO+nIJEY8+y+Z6adFO43ChiBWTPbswc5y6V U3NRzu5bjhJEgsE8rILt1idJIgPt40IicNYN3K1IFn3gIfgFUbkBu1kTEms9d4Cc2tVu DLJNcPrKx+hhJsNV8Jsv1wZf+6u+hwfKESA6hglK/BrSv5/CJ2mUPO7Sr0C+jKKsF2fp ainw== 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:mime-version:content-transfer-encoding; bh=Zltb2qLLAHtwKEbB3MDd2Q4e9WUZbVZ+eHiHjUTpFQw=; b=rvaJBLmimPD7d2dkGkMu1bmPf7LzzEOtMjQOQnWfVxHWbRgY77oUU31F+zH9sF2kcJ bPoXL3eO8xocvBp3fHlUnF6qNCJ3R7sTxBK9+4ROujQ/7C+HawAD2FjT4aGLCmodHDEM rbtLoyOowNU6ACH0lyIiHvCgDp87uLTs1GJV07TAy8/otTt++VvdYf8pYmOpIHVVYKnt O2lmZffo+NoBLM3i3ytUrsQdIrXj8WGwsCgPrIsY+laCNCvXV0kWAWJv7HmMkDU/JzS6 4zucNQqyMMOd1SyNrLL89DQIrUMLM6dsFLar4qu2XaSSMTbHIMuBy7l0MssaqC4nM32u mcHg== X-Gm-Message-State: AOAM5331KMSX/hV6qpzk7zziFqgItCYZe5BR+/sQNlxgjcUlC2b6j93R kxXQD20sxTgmc1biQGkW3PwKllf2v+c= X-Google-Smtp-Source: ABdhPJxTiQMzoiYGEex5XXD0wJV+bhhN64++XEw5aVNva0X5uyl9EOR7KnxJJ3upQjU+czlhQmUz+w== X-Received: by 2002:a1c:6a16:: with SMTP id f22mr11407539wmc.86.1606058860032; Sun, 22 Nov 2020 07:27:40 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:b0e1:b041:18e2:46cf]) by smtp.gmail.com with ESMTPSA id k1sm13712265wrp.23.2020.11.22.07.27.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 22 Nov 2020 07:27:39 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 7/7] not: simplify ((x cmp y) {&,|,^} (x !cmp y)) --> {0,1,1} Date: Sun, 22 Nov 2020 16:27:31 +0100 Message-Id: <20201122152731.10994-8-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201122152731.10994-1-luc.vanoostenryck@gmail.com> References: <20201122152731.10994-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org Simplify bitwise operations on a compare and its complement into 0 (for &) or 1 for (| and ^). Signed-off-by: Luc Van Oostenryck --- simplify.c | 24 +++++++++++++++++++++--- validation/optim/cse-not02.c | 1 - 2 files changed, 21 insertions(+), 4 deletions(-) diff --git a/simplify.c b/simplify.c index b41c155735d1..9938a5974744 100644 --- a/simplify.c +++ b/simplify.c @@ -1632,7 +1632,7 @@ static int simplify_compare(struct instruction *insn) static int simplify_and_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2) { - struct instruction *def; + struct instruction *def, *defr = NULL; pseudo_t src1 = *p1; switch (DEF_OPCODE(def, src1)) { @@ -1640,6 +1640,12 @@ static int simplify_and_one_side(struct instruction *insn, pseudo_t *p1, pseudo_ if (def->src == *p2) return replace_with_value(insn, 0); break; + case OP_BINCMP ... OP_BINCMP_END: + if (DEF_OPCODE(defr, *p2) == opcode_negate(def->opcode)) { + if (def->src1 == defr->src1 && def->src2 == defr->src2) + return replace_with_value(insn, 0); + } + break; } return 0; } @@ -1652,7 +1658,7 @@ static int simplify_and(struct instruction *insn) static int simplify_ior_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2) { - struct instruction *def; + struct instruction *def, *defr = NULL; pseudo_t src1 = *p1; switch (DEF_OPCODE(def, src1)) { @@ -1660,6 +1666,12 @@ static int simplify_ior_one_side(struct instruction *insn, pseudo_t *p1, pseudo_ if (def->src == *p2) return replace_with_value(insn, bits_mask(insn->size)); break; + case OP_BINCMP ... OP_BINCMP_END: + if (DEF_OPCODE(defr, *p2) == opcode_negate(def->opcode)) { + if (def->src1 == defr->src1 && def->src2 == defr->src2) + return replace_with_value(insn, 1); + } + break; } return 0; } @@ -1672,7 +1684,7 @@ static int simplify_ior(struct instruction *insn) static int simplify_xor_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2) { - struct instruction *def; + struct instruction *def, *defr = NULL; pseudo_t src1 = *p1; switch (DEF_OPCODE(def, src1)) { @@ -1680,6 +1692,12 @@ static int simplify_xor_one_side(struct instruction *insn, pseudo_t *p1, pseudo_ if (def->src == *p2) return replace_with_value(insn, bits_mask(insn->size)); break; + case OP_BINCMP ... OP_BINCMP_END: + if (DEF_OPCODE(defr, *p2) == opcode_negate(def->opcode)) { + if (def->src1 == defr->src1 && def->src2 == defr->src2) + return replace_with_value(insn, 1); + } + break; } return 0; } diff --git a/validation/optim/cse-not02.c b/validation/optim/cse-not02.c index aa54a375a9ea..70addebcfbb6 100644 --- a/validation/optim/cse-not02.c +++ b/validation/optim/cse-not02.c @@ -5,7 +5,6 @@ int xor(int a, int b) { return ((a == b) ^ (a != b)) == 1; } /* * check-name: cse-not02 * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-returns: 1