From patchwork Tue Jan 26 22:04:23 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 12048795 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 EF28BC433DB for ; Wed, 27 Jan 2021 03:45:29 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C10B6206B5 for ; Wed, 27 Jan 2021 03:45:29 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232981AbhA0DpD (ORCPT ); Tue, 26 Jan 2021 22:45:03 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59242 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727934AbhAZWFT (ORCPT ); Tue, 26 Jan 2021 17:05:19 -0500 Received: from mail-wr1-x434.google.com (mail-wr1-x434.google.com [IPv6:2a00:1450:4864:20::434]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 381D6C0613ED for ; Tue, 26 Jan 2021 14:04:39 -0800 (PST) Received: by mail-wr1-x434.google.com with SMTP id a1so18104375wrq.6 for ; Tue, 26 Jan 2021 14:04: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=mCp66NLhpBgYgFPO6oStYivRlowXSYjV5YHCs1YAk1U=; b=FEdODn3dX3yDorqu/WcXgDOVbqbySwQwso22vwJhzdFj4ke3fx6SUUlYruDEkpK3ac QxQLA4kwrKY/IVNfsXeRGmW1ZmzSLjtjQorxSnGWruzNeRg47qnTfqIM7onANq3+RjZp rmzc7jlkes1eMBP0nYB7ru0I11oBaZhHIAzRAa7bTEM0U+2XvqLlvODbys0DEwSc2FLt wU+iNlMzikdN7EtEX682oGO0Bhs4BbNjod96x5YoBAKd2unyfcnDWCXxu2SMqjRMrHSa EjGAQ0o7gs832Bi6iH6imgJjkuxUBUNxqDa6ceyjqc6vy9p4a2RV6UUGCgckc1AKf90R Vctg== 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=mCp66NLhpBgYgFPO6oStYivRlowXSYjV5YHCs1YAk1U=; b=p1UrhO+uDJnY3XUzP0rVPDEaMGKNXdJzs3+GVNZo2SwNRGuHKAyls0lySTXGlD0fiv iJDDIpQZyUGnJU5CGNYRlzNxZ+T/GVgGNBJFOKsIRxO9hPOiGCGPHse5xVrmJUtVhqin Jwp3OVJwYj5ejCc6HuECXoGoBqRAeRGMWSpknPFomvqw7fab0PkSNyFLghn2vl4bSqWt kLeocOSJnBxv20XFfnZBVwN9O4jTXi1E8sELbdwmf5f8fit8UxWXLMvy1rQDxCQ+XyVn 4FmHdnJcs3qEQTudRVmypjT2s1bweeedKZ0J6IpeWpttYSOuOUOmueVGIBzKe0fYIGX4 IJJQ== X-Gm-Message-State: AOAM533X81nqe89xC95bN9OS+eAJwKXhJQlHDAzWHo/jTuzJ++YI19rj K0pIneQVr6cPqPrObzdbWzrp2ze0oHo= X-Google-Smtp-Source: ABdhPJyOX07bwggTUjfVCEjcFsfbJHHpK8obSz0P6meMz0eftgqv2AoL41/T2gCWJnECg1x5h8D0xQ== X-Received: by 2002:adf:f183:: with SMTP id h3mr8414554wro.30.1611698677982; Tue, 26 Jan 2021 14:04:37 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:285a:40db:3257:f0fd]) by smtp.gmail.com with ESMTPSA id b132sm5268447wmh.21.2021.01.26.14.04.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 26 Jan 2021 14:04:37 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 01/10] cmps: make clearer we're using the operands' size Date: Tue, 26 Jan 2021 23:04:23 +0100 Message-Id: <20210126220432.58265-2-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.30.0 In-Reply-To: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> References: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org When handling compares of an {zero,sign}-extended value, the size of these extended values are used but this size is just the operands' size of the compares. Make this clearer by using a single variable 'size' for it. Signed-off-by: Luc Van Oostenryck --- simplify.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) diff --git a/simplify.c b/simplify.c index bf6397dfd582..2f6f41c249dc 100644 --- a/simplify.c +++ b/simplify.c @@ -1162,7 +1162,8 @@ static int simplify_seteq_setne(struct instruction *insn, long long value) static int simplify_compare_constant(struct instruction *insn, long long value) { - unsigned long long bits = bits_mask(insn->itype->bit_size); + unsigned size = insn->itype->bit_size; + unsigned long long bits = bits_mask(size); struct instruction *def; pseudo_t src1, src2; unsigned int osize; @@ -1217,7 +1218,7 @@ static int simplify_compare_constant(struct instruction *insn, long long value) switch (DEF_OPCODE(def, src1)) { case OP_SEXT: // sext(x) cmp C --> x cmp trunc(C) osize = def->orig_type->bit_size; - if (is_signed_constant(value, osize, def->size)) { + if (is_signed_constant(value, osize, size)) { insn->itype = def->orig_type; insn->src2 = value_pseudo(zero_extend(value, osize)); return replace_pseudo(insn, &insn->src1, def->src); @@ -1263,13 +1264,13 @@ static int simplify_compare_constant(struct instruction *insn, long long value) } switch (insn->opcode) { case OP_SET_LT: case OP_SET_LE: - if (sign_extend(value, def->size) > (long long)bits) + if (sign_extend(value, size) > (long long)bits) return replace_with_value(insn, 1); else return replace_with_value(insn, 0); break; case OP_SET_GE: case OP_SET_GT: - if (sign_extend(value, def->size) > (long long)bits) + if (sign_extend(value, size) > (long long)bits) return replace_with_value(insn, 0); else return replace_with_value(insn, 1); From patchwork Tue Jan 26 22:04:24 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 12048799 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 A6FBDC433DB for ; Wed, 27 Jan 2021 03:45:40 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6BE23206B5 for ; Wed, 27 Jan 2021 03:45:40 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237040AbhA0DpX (ORCPT ); Tue, 26 Jan 2021 22:45:23 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59248 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728157AbhAZWFV (ORCPT ); Tue, 26 Jan 2021 17:05:21 -0500 Received: from mail-wr1-x42a.google.com (mail-wr1-x42a.google.com [IPv6:2a00:1450:4864:20::42a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1AD6AC061786 for ; Tue, 26 Jan 2021 14:04:40 -0800 (PST) Received: by mail-wr1-x42a.google.com with SMTP id h9so7855413wrr.9 for ; Tue, 26 Jan 2021 14:04: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=9dSeTy0FpRyAvUeb4DXxdtoKChR3B565ZqYajK810Tw=; b=MjRiF5hsUvC6EpG9WNSkxB1Xv4Fnp/tOqy8vc5ECvJekPu+c0KLL8EOHNKeE+GCY83 gffA7X/c7qv4DpmFdlsIOw2FSdh/EBo1rf4HD1RsXp2fKiTPxRw4X6nEldengZJ8JTMU e9PzyG7p5fUxDKt/XCCipy7f3JkTBMQARXYOY4lb5zSowYa7eXh83Ilg8pHO+mJcWE2V knqL4UIP0vtmwHfooHmh/q3paM2APRKsbjuFkrnRg2wuLSvKGSQ60kQU36Qxcb6/LNsg Dz0Kt1UF1Mn6YnCWA7mM1k8HFcMOE80RUdpmHY/IHtEauMHiRto/VoQV0neLCpwSkDXF GLDg== 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=9dSeTy0FpRyAvUeb4DXxdtoKChR3B565ZqYajK810Tw=; b=jxJNrYH5FArl48IRR3Kap2BvYvh9Ly/VJtS83jVy66iMsmOGHu7T+lh7StYNfFba3v UwAPpAjOpajKaKbIOUysaFlXkvqq5M8NpVjCAMSOgbOuhv7MDNtncH5ST0CARAPSq/Q0 iPb+roT5FQ19vPcbHa/h1UXt00zxdz7J3DLQBfaOHiGatZBzmZ57vixtyJY9lNFKwhta 8dXb3Yb+y2fSGgyyctauO7Lc3T2yEFecstQI9iUZEJ0xYd6ohjscLgfsBaR7c78zlDmR ICTfk2JER/1B/thphwBM+FUt4vP7yDZPo35JRo2sbXEoSAQQOtLV/kG3+zjj8YOjdHi5 Civg== X-Gm-Message-State: AOAM532Q+xbdsWGAAlt4fZgh4ta1xKR2BXURqXDKuqNmr+/LefSRYcU+ F6JZccxulV/3fFx2nxqHEMd4QrCThuw= X-Google-Smtp-Source: ABdhPJyFmfj7tnR57HsqiGnn2wtM7Uq2xkIw1r7hahV+Rrtu8nWONtZ9+ZoEkVgAnCtdsBkfc5h3qQ== X-Received: by 2002:adf:814f:: with SMTP id 73mr8249739wrm.368.1611698678940; Tue, 26 Jan 2021 14:04:38 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:285a:40db:3257:f0fd]) by smtp.gmail.com with ESMTPSA id b132sm5268447wmh.21.2021.01.26.14.04.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 26 Jan 2021 14:04:38 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 02/10] cmps: fix simplification of sext(x) + signed compare of {SMAX,SMIN} Date: Tue, 26 Jan 2021 23:04:24 +0100 Message-Id: <20210126220432.58265-3-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.30.0 In-Reply-To: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> References: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org Commit a1c1b9236d5d ("cmp: simplify sext(x) cmps {SMAX,SMIN}") had a double error (wrong size and wrong compare direction) which was hidden because of too narrow testcases. So, fix the simplification and extend the testcases. Fixes: a1c1b9236d5d4af1681a45ced26f8350bd7721c2 Signed-off-by: Luc Van Oostenryck --- simplify.c | 4 +-- validation/optim/cmp-sext-simm.c | 46 ++++++++++++++++++++++++-------- 2 files changed, 37 insertions(+), 13 deletions(-) diff --git a/simplify.c b/simplify.c index 2f6f41c249dc..9a24058f6e55 100644 --- a/simplify.c +++ b/simplify.c @@ -1239,13 +1239,13 @@ static int simplify_compare_constant(struct instruction *insn, long long value) } break; case OP_SET_LT: case OP_SET_LE: - if (value >= sign_bit(osize)) + if (value < sign_bit(size)) return replace_with_value(insn, 1); else return replace_with_value(insn, 0); break; case OP_SET_GE: case OP_SET_GT: - if (value >= sign_bit(osize)) + if (value < sign_bit(size)) return replace_with_value(insn, 0); else return replace_with_value(insn, 1); diff --git a/validation/optim/cmp-sext-simm.c b/validation/optim/cmp-sext-simm.c index a8b2a8f9feff..57a4df1d57b1 100644 --- a/validation/optim/cmp-sext-simm.c +++ b/validation/optim/cmp-sext-simm.c @@ -4,21 +4,45 @@ static int lt_ge0(int x) { return (sext(x) < (POS + 0)) == 1; } static int lt_ge1(int x) { return (sext(x) < (POS + 1)) == 1; } +static int lt_ge2(int x) { return (sext(x) < (POS + 2)) == 1; } +static int lt_gex(int x) { return (sext(x) < (POS<< 1)) == 1; } +static int lt_gey(int x) { return (sext(x) < (POS<< 3)) == 1; } static int le_ge0(int x) { return (sext(x) <= (POS + 0)) == 1; } static int le_ge1(int x) { return (sext(x) <= (POS + 1)) == 1; } -static int lt_lt0(int x) { return (sext(x) < (NEG - 0)) == 1; } -static int lt_lt1(int x) { return (sext(x) < (NEG - 1)) == 1; } -static int le_lt0(int x) { return (sext(x) <= (NEG - 0)) == 1; } -static int le_lt1(int x) { return (sext(x) <= (NEG - 1)) == 1; } - -static int gt_ge0(int x) { return (sext(x) > (POS + 0)) == 0; } -static int gt_ge1(int x) { return (sext(x) > (POS + 1)) == 0; } +static int le_ge2(int x) { return (sext(x) <= (POS + 2)) == 1; } +static int le_gex(int x) { return (sext(x) <= (POS<< 1)) == 1; } +static int le_gey(int x) { return (sext(x) <= (POS<< 3)) == 1; } static int ge_ge0(int x) { return (sext(x) >= (POS + 0)) == 0; } static int ge_ge1(int x) { return (sext(x) >= (POS + 1)) == 0; } -static int gt_lt0(int x) { return (sext(x) > (NEG - 0)) == 0; } -static int gt_lt1(int x) { return (sext(x) > (NEG - 1)) == 0; } -static int ge_lt0(int x) { return (sext(x) >= (NEG - 0)) == 0; } -static int ge_lt1(int x) { return (sext(x) >= (NEG - 1)) == 0; } +static int ge_ge2(int x) { return (sext(x) >= (POS + 2)) == 0; } +static int ge_gex(int x) { return (sext(x) >= (POS<< 1)) == 0; } +static int ge_gey(int x) { return (sext(x) >= (POS<< 3)) == 0; } +static int gt_ge0(int x) { return (sext(x) > (POS + 0)) == 0; } +static int gt_ge1(int x) { return (sext(x) > (POS + 1)) == 0; } +static int gt_ge2(int x) { return (sext(x) > (POS + 2)) == 0; } +static int gt_gex(int x) { return (sext(x) > (POS<< 1)) == 0; } +static int gt_gey(int x) { return (sext(x) > (POS<< 3)) == 0; } + +static int lt_lt0(int x) { return (sext(x) < (NEG - 0)) == 0; } +static int lt_lt1(int x) { return (sext(x) < (NEG - 1)) == 0; } +static int lt_lt2(int x) { return (sext(x) < (NEG - 2)) == 0; } +static int lt_ltx(int x) { return (sext(x) < (NEG<< 1)) == 0; } +static int lt_lty(int x) { return (sext(x) < (NEG<< 3)) == 0; } +static int le_lt0(int x) { return (sext(x) <= (NEG - 0)) == 0; } +static int le_lt1(int x) { return (sext(x) <= (NEG - 1)) == 0; } +static int le_lt2(int x) { return (sext(x) <= (NEG - 2)) == 0; } +static int le_ltx(int x) { return (sext(x) <= (NEG<< 1)) == 0; } +static int le_lty(int x) { return (sext(x) <= (NEG<< 3)) == 0; } +static int ge_lt0(int x) { return (sext(x) >= (NEG - 0)) == 1; } +static int ge_lt1(int x) { return (sext(x) >= (NEG - 1)) == 1; } +static int ge_lt2(int x) { return (sext(x) >= (NEG - 2)) == 1; } +static int ge_ltx(int x) { return (sext(x) >= (NEG<< 1)) == 1; } +static int ge_lty(int x) { return (sext(x) >= (NEG<< 3)) == 1; } +static int gt_lt0(int x) { return (sext(x) > (NEG - 0)) == 1; } +static int gt_lt1(int x) { return (sext(x) > (NEG - 1)) == 1; } +static int gt_lt2(int x) { return (sext(x) > (NEG - 2)) == 1; } +static int gt_ltx(int x) { return (sext(x) > (NEG<< 1)) == 1; } +static int gt_lty(int x) { return (sext(x) > (NEG<< 3)) == 1; } /* * check-name: cmp-sext-simm From patchwork Tue Jan 26 22:04:25 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 12048797 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 E49BBC433DB for ; Wed, 27 Jan 2021 03:45:32 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id A998A206B5 for ; Wed, 27 Jan 2021 03:45:32 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234446AbhA0DpR (ORCPT ); Tue, 26 Jan 2021 22:45:17 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59254 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728151AbhAZWFV (ORCPT ); Tue, 26 Jan 2021 17:05:21 -0500 Received: from mail-wr1-x430.google.com (mail-wr1-x430.google.com [IPv6:2a00:1450:4864:20::430]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E39D7C061788 for ; Tue, 26 Jan 2021 14:04:40 -0800 (PST) Received: by mail-wr1-x430.google.com with SMTP id m13so3662030wro.12 for ; Tue, 26 Jan 2021 14:04: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=s4u24hLglrfhJEiU+ZVHHw5eMIoLKjrX49zqfITxO1g=; b=G4S7iU8MKj71xrmJjcUtHLoFjj+Hmc6ki92myn1kyBvJr/+h09l+tbyE24/mzsqTrv JRWPhIGo0M/bYvUL8HHjwl2XG8O/gOVa2ixV4aiMagYwau88VEoZrPfoDqBac01Uwt7b W/i0pUm1eI526LP15DKmxvJTaSSc8Ghl8rT/uQlICy3vLmrEFDBByl89Y8eAjSyLUKRG OOU8B4XB+yncQrSaxVpmxWBtHbXzIwbZB+oP3uheA722kuCMhoV/pfX3DbwUwnyQcA5A cpyxSDABY/2OffxJI60NfQjad6g6oZckm3fEwp9g8IxS4s1i/WN95Kdj4TGlWeNTqD78 VxaA== 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=s4u24hLglrfhJEiU+ZVHHw5eMIoLKjrX49zqfITxO1g=; b=Vn9++UbNjYVZkkMk7uZBA10r/e+KkS9VDvHlOFenEdYyKpYmqiCw+5SKPuh/jJD3vi uX3kj1BpnbwzvYAGZWqL5N5dZtlZL+PUgT524syCyKHETbBnCUexCH7GYNPyjpfj24VA K0SKBX/SszqW47mcgK693IaqlMm5qVVln7fptaYZ714OCj7OiRGS8TwrITP/cL4kZVF9 vI1dQ0NS+mLpjGteraHPwmGFjQ2QpQNw4nAz0lkdbh/cxSXdLzGNh/EyzX5IXKcF2G7x wy2H5ICo7zb/9OmAU8nBhUmBe6AyEtiMF4Pu15I8g/KAND3KSM9sZOgzuMWYDwApJM6L ZHvg== X-Gm-Message-State: AOAM532CAfpsHD+ta5y5emv8XmUSmJPWToVhFmZITM+B4UgmXheov7Ad qV4PuoSFvKMHPZovM5JcQB2EPRz3t/s= X-Google-Smtp-Source: ABdhPJwQN6IeJhd7ZQxi2LosLE1Jeq5rKIrhQkPDo3psu0O4W6bYSa7e5ulKtWbjxpX5mPZDRRQ1Pg== X-Received: by 2002:adf:9cc4:: with SMTP id h4mr7008967wre.403.1611698679770; Tue, 26 Jan 2021 14:04:39 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:285a:40db:3257:f0fd]) by smtp.gmail.com with ESMTPSA id b132sm5268447wmh.21.2021.01.26.14.04.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 26 Jan 2021 14:04:39 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 03/10] cmpu: fix canonicalization of unsigned (x {<,>=} C) --> (x {<=,>} C-1) Date: Tue, 26 Jan 2021 23:04:25 +0100 Message-Id: <20210126220432.58265-4-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.30.0 In-Reply-To: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> References: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org In Sparse, the PSEUDO_VALUEs are required to be truncated at their effective size. For example, for a 32-bit instruction and Sparse using 64-bit integers, a pseudo of -1 must contain the value 0x00000000ffffffff, not 0xffffffffffffffff. Add the missing truncation in the canonicalization here. Fixes: c355e5ac5dce35f3d95c30cd5e2e9a5074c38437 Signed-off-by: Luc Van Oostenryck --- simplify.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/simplify.c b/simplify.c index 9a24058f6e55..a306828c1c4b 100644 --- a/simplify.c +++ b/simplify.c @@ -1178,7 +1178,7 @@ static int simplify_compare_constant(struct instruction *insn, long long value) else if (value == bits) // (x < ~0) --> (x != ~0) return replace_binop_value(insn, OP_SET_NE, value); else // (x < y) --> (x <= (y-1)) - changed |= replace_binop_value(insn, OP_SET_BE, value - 1); + changed |= replace_binop_value(insn, OP_SET_BE, (value - 1) & bits); break; case OP_SET_AE: if (!value) // (x >= 0) --> 1 @@ -1188,7 +1188,7 @@ static int simplify_compare_constant(struct instruction *insn, long long value) else if (value == bits) // (x >= ~0) --> (x == ~0) return replace_binop_value(insn, OP_SET_EQ, value); else // (x >= y) --> (x > (y-1) - changed |= replace_binop_value(insn, OP_SET_A, value - 1); + changed |= replace_binop_value(insn, OP_SET_A, (value - 1) & bits); break; case OP_SET_BE: if (!value) // (x <= 0) --> (x == 0) From patchwork Tue Jan 26 22:04:26 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 12048801 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 31F49C433DB for ; Wed, 27 Jan 2021 03:45:49 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E6D75206B5 for ; Wed, 27 Jan 2021 03:45:48 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237044AbhA0Dpa (ORCPT ); Tue, 26 Jan 2021 22:45:30 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59260 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728160AbhAZWFW (ORCPT ); Tue, 26 Jan 2021 17:05:22 -0500 Received: from mail-wm1-x332.google.com (mail-wm1-x332.google.com [IPv6:2a00:1450:4864:20::332]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 5701FC06178A for ; Tue, 26 Jan 2021 14:04:42 -0800 (PST) Received: by mail-wm1-x332.google.com with SMTP id s24so2239909wmj.0 for ; Tue, 26 Jan 2021 14:04:42 -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=WVRsNPLUFnv0MZn5XhUmlbwMAhgVh1ZY6p1pgO0Wh3M=; b=QuKA81sq+/HzDsz4vEEMZ2BzycrqGj2SeAgcWXZxtaLJGvjyWWFub5y8ZH6pi8x8vg B+LpSFwv+4s37R56Ejd3VoXpB96b378bLVr4w2JB4x1noJ+dpWqIloElLcMYpx/UYfyt ilQxxiwhd9DcQL4nEvhN5z6hqyGmk5cnqxKeuuwrvyEkI1Bn/zrpjagZytRv0gqGQIfs mQQfi0yEcwjRNHTBtNW80vX7Istp2acLcJOBpG5l05IUxIB55qANteB6MjPYeKrg4KQZ 0cUVgO1LwKQ+aWMEWHi+LTmyRP2K5rPgAshJ3lc49ZPx5duNMdKnlJKzoNRTx46hY7Gz egLQ== 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=WVRsNPLUFnv0MZn5XhUmlbwMAhgVh1ZY6p1pgO0Wh3M=; b=XX7NQ/Rwh12ewesuLLNKM0B1I1xXpwI27LEkHUG/LxZFVFkYtBeC8pLUKvp9NeID3U lBxqdc+X23W5GV3jnBlm/VbMVsa0FRPlhMZItr/pzD1k2eChRZ6lCf3bzYLfVp3rUZ6L 0+X7Jqb09EZaHxk6qaOMbPwjOTuOLfkhwmSqexDFU7crLQmZLkKgXggVv/Pcak1xEfBf MIeINQZmNyk6W5IJYgurOHwg05Tx7FgxASfGNxvqjbBzP2d8p+ncZW9KXfdT/ctSVIXZ yQxkmI7m5F5PLfa/gTaxTH/2P37q9bbcESQzXNyNCTAvH+jDsc1YFD/8Aa19CdOu+Zv7 TS8A== X-Gm-Message-State: AOAM532IbwVCI1jnkW6LoLczW19Sj2wKBnk/24TikNWf54Ud9PZ2HCba 3bbW/V7iqquuHn4aSzNyYRY3oNgpkZk= X-Google-Smtp-Source: ABdhPJxo+SvaEfMdr0KfWQebT6IUZSuREDIcX4N3YO9kX/cNFm48CvRRpubfwW7bzw+hIFkh4lSyDA== X-Received: by 2002:a05:600c:3515:: with SMTP id h21mr1423793wmq.179.1611698681152; Tue, 26 Jan 2021 14:04:41 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:285a:40db:3257:f0fd]) by smtp.gmail.com with ESMTPSA id b132sm5268447wmh.21.2021.01.26.14.04.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 26 Jan 2021 14:04:40 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 04/10] cmps: add testcases for simplification of signed compares Date: Tue, 26 Jan 2021 23:04:26 +0100 Message-Id: <20210126220432.58265-5-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.30.0 In-Reply-To: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> References: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org Signed compares miss some simplifications/canonicalizations. Add some testcases for them. Signed-off-by: Luc Van Oostenryck --- validation/optim/canonical-abs.c | 12 +++++++++++ validation/optim/canonical-cmpe-minmax.c | 17 ++++++++++++++++ validation/optim/canonical-cmps-minmax.c | 17 ++++++++++++++++ validation/optim/canonical-cmps-sel.c | 26 ++++++++++++++++++++++++ validation/optim/canonical-cmps.c | 17 ++++++++++++++++ validation/optim/cmps-minmax.c | 17 ++++++++++++++++ 6 files changed, 106 insertions(+) create mode 100644 validation/optim/canonical-abs.c create mode 100644 validation/optim/canonical-cmpe-minmax.c create mode 100644 validation/optim/canonical-cmps-minmax.c create mode 100644 validation/optim/canonical-cmps-sel.c create mode 100644 validation/optim/canonical-cmps.c create mode 100644 validation/optim/cmps-minmax.c diff --git a/validation/optim/canonical-abs.c b/validation/optim/canonical-abs.c new file mode 100644 index 000000000000..0809a52d445b --- /dev/null +++ b/validation/optim/canonical-abs.c @@ -0,0 +1,12 @@ +_Bool abs0(int a) { return (a < 0 ? -a : a) == (a >= 0 ? a : -a); } +_Bool abs1(int a) { return (a < 0 ? -a : a) == (a > 0 ? a : -a); } +_Bool abs2(int a) { return (a < 0 ? -a : a) == (a <= 0 ? -a : a); } + +/* + * check-name: canonical-abs1 + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-returns: 1 + */ diff --git a/validation/optim/canonical-cmpe-minmax.c b/validation/optim/canonical-cmpe-minmax.c new file mode 100644 index 000000000000..c72819244b95 --- /dev/null +++ b/validation/optim/canonical-cmpe-minmax.c @@ -0,0 +1,17 @@ +#define SMAX __INT_MAX__ +#define SMIN (-__INT_MAX__-1) + +int le_smax(int a) { return (a <= (SMAX - 1)) == (a != SMAX); } +int gt_smax(int a) { return (a > (SMAX - 1)) == (a == SMAX); } + +int lt_smin(int a) { return (a < (SMIN + 1)) == (a == SMIN); } +int ge_smin(int a) { return (a >= (SMIN + 1)) == (a != SMIN); } + +/* + * check-name: canonical-cmpe-minmax + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-returns: 1 + */ diff --git a/validation/optim/canonical-cmps-minmax.c b/validation/optim/canonical-cmps-minmax.c new file mode 100644 index 000000000000..bab09282d241 --- /dev/null +++ b/validation/optim/canonical-cmps-minmax.c @@ -0,0 +1,17 @@ +#define SMAX __INT_MAX__ +#define SMIN (-__INT_MAX__-1) + +int lt_smax(int a) { return (a < SMAX) == (a != SMAX); } +int ge_smax(int a) { return (a >= SMAX) == (a == SMAX); } + +int le_smin(int a) { return (a <= SMIN) == (a == SMIN); } +int gt_smin(int a) { return (a > SMIN) == (a != SMIN); } + +/* + * check-name: canonical-cmps-minmax + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-returns: 1 + */ diff --git a/validation/optim/canonical-cmps-sel.c b/validation/optim/canonical-cmps-sel.c new file mode 100644 index 000000000000..f0a0effc7954 --- /dev/null +++ b/validation/optim/canonical-cmps-sel.c @@ -0,0 +1,26 @@ +_Bool sel_lts(int a, int b, int x, int y) +{ + return ((a < b) ? x : y) == ((a >= b) ? y : x); +} +_Bool sel_les(int a, int b, int x, int y) +{ + return ((a <= b) ? x : y) == ((a > b) ? y : x); +} + +_Bool sel_ltu(unsigned int a, unsigned int b, int x, int y) +{ + return ((a < b) ? x : y) == ((a >= b) ? y : x); +} +_Bool sel_leu(unsigned int a, unsigned int b, int x, int y) +{ + return ((a <= b) ? x : y) == ((a > b) ? y : x); +} + +/* + * check-name: canonical-cmps-sel + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-returns: 1 + */ diff --git a/validation/optim/canonical-cmps.c b/validation/optim/canonical-cmps.c new file mode 100644 index 000000000000..f42664b21e04 --- /dev/null +++ b/validation/optim/canonical-cmps.c @@ -0,0 +1,17 @@ +_Bool lt_p(int a) { return (a > 0) == (a >= 1); } +_Bool ge_p(int a) { return (a <= 0) == (a < 1); } + +_Bool lt_m(int a) { return (a < 0) == (a <= -1); } +_Bool ge_m(int a) { return (a >= 0) == (a > -1); } + +_Bool lt_x(int a) { return (a <= 1234) == (a < 1235); } +_Bool ge_x(int a) { return (a >= 1234) == (a > 1233); } + +/* + * check-name: canonical-cmps + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-returns: 1 + */ diff --git a/validation/optim/cmps-minmax.c b/validation/optim/cmps-minmax.c new file mode 100644 index 000000000000..ded3286cf752 --- /dev/null +++ b/validation/optim/cmps-minmax.c @@ -0,0 +1,17 @@ +#define SMAX __INT_MAX__ +#define SMIN (-__INT_MAX__-1) + +int lt_smin(int a) { return (a < SMIN) == 0; } +int le_smax(int a) { return (a <= SMAX) == 1; } + +int ge_smin(int a) { return (a >= SMIN) == 1; } +int gt_smax(int a) { return (a > SMAX) == 0; } + +/* + * check-name: cmps-minmax + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-returns: 1 + */ From patchwork Tue Jan 26 22:04:27 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 12048805 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 CF95CC433E0 for ; Wed, 27 Jan 2021 03:46:04 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 9D481206B5 for ; Wed, 27 Jan 2021 03:46:04 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237064AbhA0Dpp (ORCPT ); Tue, 26 Jan 2021 22:45:45 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59264 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728165AbhAZWFZ (ORCPT ); Tue, 26 Jan 2021 17:05:25 -0500 Received: from mail-wm1-x334.google.com (mail-wm1-x334.google.com [IPv6:2a00:1450:4864:20::334]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 38B78C06178B for ; Tue, 26 Jan 2021 14:04:43 -0800 (PST) Received: by mail-wm1-x334.google.com with SMTP id m187so3729300wme.2 for ; Tue, 26 Jan 2021 14:04:43 -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=xn/y5fWz+bSTA74YnAs3vllw5bYBv1J7ij1cyNTfF3k=; b=rsFzlo0ZjmFRuSkVlhmA8i5uyKn1K8gz4j8o2+RLpJb/UWjoAsd8DxcGgoBmV//64O pyioA45qE29PNGSjQngqUMEKfR+4uyefbyqYiCMa+eT5Gt5wCbMKiF0pSm/+MJ7XJWvj RawF54xrdWl0oa621LJD1IuErN2Ge16jS3XWZQGBW3MJL3X2sV48soXw1MA/dEY32+QD Jn/OKlqJ1GKY8vm5yG/qgATzaT2pXT6WYAbsz3YZMGAjvIK/0RFpqa2AxzleXvXSH8dC 1m0KhrdM/0CeC+lgsbGF/JKtED8u6ICnvFUHHZqmdsR9DXkSkPk9Zm5jMK9VbwkuZFxm 89uA== 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=xn/y5fWz+bSTA74YnAs3vllw5bYBv1J7ij1cyNTfF3k=; b=C72boDjHkqB5NMVOrcUQdiIQ8xJLIQ/iZYCHLlsqGFEHj1RpbDK4Nbu9oN+bBZtUA6 1AywxnQB37Ru3MgrLUKYx9iE/HY40O0Qq8XoOFUZYXfBLe0VeOJCaTtPP+m0vA2l2sxe ijUqJc9hlbkngEQG+ZznLV8YdKfX8HS0zOXmSa2zTQVMwGxUtcrfrFQ5ZYlf6iB7VZ3u GFdISY4HK7/x4zrhvADA2ncbEjp99tR3FWs9uAnIyQkMCU+dm07iKvGT2hotFtzCjyre ely4dv4GLWvdbsNVFZ3YxiBiFZrt7wX9FKGzlXZsO+Gms96h+ffXXsfI3CEwN1Qu2NXd QesQ== X-Gm-Message-State: AOAM532wzNN6YP8rqwNUJK/5kmU7F0+ekiKjpfLG4cOdayqh04jn80qj dU0ufnM0WkkrUpLKZV50oABtTp77SYo= X-Google-Smtp-Source: ABdhPJwuc1huwZRCgUw5lrcHpNo8D6Q0LXE0P7G44kjBtSb9MV/czs6z3Zf5prb01lpHwCFf37sATA== X-Received: by 2002:a7b:cd8e:: with SMTP id y14mr1485794wmj.61.1611698681991; Tue, 26 Jan 2021 14:04:41 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:285a:40db:3257:f0fd]) by smtp.gmail.com with ESMTPSA id b132sm5268447wmh.21.2021.01.26.14.04.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 26 Jan 2021 14:04:41 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 05/10] cmps: simplify signed compares with SMIN or SMAX Date: Tue, 26 Jan 2021 23:04:27 +0100 Message-Id: <20210126220432.58265-6-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.30.0 In-Reply-To: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> References: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org Simplify away signed compares with SMIN or SMAX which can be statically be determined to be always true or always false. Signed-off-by: Luc Van Oostenryck --- simplify.c | 17 +++++++++++++++++ validation/optim/cmps-minmax.c | 1 - 2 files changed, 17 insertions(+), 1 deletion(-) diff --git a/simplify.c b/simplify.c index a306828c1c4b..096742d51a16 100644 --- a/simplify.c +++ b/simplify.c @@ -1170,6 +1170,23 @@ static int simplify_compare_constant(struct instruction *insn, long long value) int changed = 0; switch (insn->opcode) { + case OP_SET_LT: + if (value == sign_bit(size)) // (x < SMIN) --> 0 + return replace_with_pseudo(insn, value_pseudo(0)); + break; + case OP_SET_LE: + if (value == sign_mask(size)) // (x <= SMAX) --> 1 + return replace_with_pseudo(insn, value_pseudo(1)); + break; + case OP_SET_GE: + if (value == sign_bit(size)) // (x >= SMIN) --> 1 + return replace_with_pseudo(insn, value_pseudo(1)); + break; + case OP_SET_GT: + if (value == sign_mask(size)) // (x > SMAX) --> 0 + return replace_with_pseudo(insn, value_pseudo(0)); + break; + case OP_SET_B: if (!value) // (x < 0) --> 0 return replace_with_pseudo(insn, value_pseudo(0)); diff --git a/validation/optim/cmps-minmax.c b/validation/optim/cmps-minmax.c index ded3286cf752..5802cdbcafd1 100644 --- a/validation/optim/cmps-minmax.c +++ b/validation/optim/cmps-minmax.c @@ -10,7 +10,6 @@ int gt_smax(int a) { return (a > SMAX) == 0; } /* * check-name: cmps-minmax * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-returns: 1 From patchwork Tue Jan 26 22:04:28 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 12048803 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 B2847C433E0 for ; Wed, 27 Jan 2021 03:45:59 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 7E33E206B5 for ; Wed, 27 Jan 2021 03:45:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237047AbhA0Dpf (ORCPT ); Tue, 26 Jan 2021 22:45:35 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59270 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728162AbhAZWFZ (ORCPT ); Tue, 26 Jan 2021 17:05:25 -0500 Received: from mail-wm1-x32b.google.com (mail-wm1-x32b.google.com [IPv6:2a00:1450:4864:20::32b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 49D2FC06178C for ; Tue, 26 Jan 2021 14:04:44 -0800 (PST) Received: by mail-wm1-x32b.google.com with SMTP id m187so3729332wme.2 for ; Tue, 26 Jan 2021 14:04:44 -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=pTaH/oxw1TlzjdASrYk0d5gVWNTFa1swlm5naHKiok0=; b=l6v7Yi6eK/YvUSCaEFuZ4N87uyxAAoHKmu79v4eV3aI9Sih3TSnB54MMs8Yvc0c2EV t9jw4bzrsGDjFDmBQtG8Uy7zoi03cBgUOovEyPrMr4kMZvmFkLvqIeP5GO9IZggRl0MT u7oZz87ZD+D8v3zHOcex/s+anU8CCqjr9+s1+OIaOhJSUIsUdnAdjGjRfmDQDjJ3phkd lx+/VV3mRg8jSTxcDuVcsAeYgl51r/SQZl2HH/jZvrI+R11xzhGIz5G3gNoTFIwUUITQ Yg6LEC2HO6m0drKcefPj3kHgBw92QngmerK+CidYqumIreGszQ69OT5p9eODubs5VKn6 dITA== 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=pTaH/oxw1TlzjdASrYk0d5gVWNTFa1swlm5naHKiok0=; b=A42tuHV0vevGTw/rckeT9cGSBzCEmvpZnl2hnCyRCOmX+M++DnJLMTTysX8UwkR3NG grMb2VuGz6FkGg3uEF1IOVZj3ZqTyg1lG5pRUY5pxhWvCB56rmlmJwAyVco4H7tJ0C/I e70LDUZfDq8hukpvXFWig35c6GOSfLWmOcHR2zvIVZSr+HY9e8nL+RyJt/V19AUWAkNF /gjqaPecOAoR6S+JzErWmPSlfeijkZixBS4WlCb3x23+LG0gWv+pZuuC8rI74FcFNUYu RHfaxcNTML0dVRwZ+GN0kKJEWPhd/ld/wxU7dgwDAHsXruQeI3KhRXfZ5FQwiCKAHdUO K+kg== X-Gm-Message-State: AOAM53190vnwQEMNFqhkXZuKiym+w7GovqaiXKGYMMUwt+XpFBKfIeC7 wQceiB+XU553HbpDdNMgD9mn2VOHNNs= X-Google-Smtp-Source: ABdhPJymB1gjiBPDnwkQLNvGf5aQnkGec7yvY8vlpN3GKyk/9FglPZV0c9CPjkd4urqk9TNL20IRAg== X-Received: by 2002:a1c:e346:: with SMTP id a67mr1494467wmh.142.1611698683145; Tue, 26 Jan 2021 14:04:43 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:285a:40db:3257:f0fd]) by smtp.gmail.com with ESMTPSA id b132sm5268447wmh.21.2021.01.26.14.04.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 26 Jan 2021 14:04:42 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 06/10] cmps: canonicalize signed compares with SMIN/SMAX Date: Tue, 26 Jan 2021 23:04:28 +0100 Message-Id: <20210126220432.58265-7-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.30.0 In-Reply-To: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> References: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org The remaining compares with SMIN or SMAX are equivalent to an equality testing. For example, (x < SMAX) is the same as (x != SMAX). Canonicalize these to the equality testing since these are usually simpler to handle. Signed-off-by: Luc Van Oostenryck --- simplify.c | 8 ++++++++ validation/optim/canonical-cmps-minmax.c | 1 - 2 files changed, 8 insertions(+), 1 deletion(-) diff --git a/simplify.c b/simplify.c index 096742d51a16..f7c6c68d4ce9 100644 --- a/simplify.c +++ b/simplify.c @@ -1173,18 +1173,26 @@ static int simplify_compare_constant(struct instruction *insn, long long value) case OP_SET_LT: if (value == sign_bit(size)) // (x < SMIN) --> 0 return replace_with_pseudo(insn, value_pseudo(0)); + if (value == sign_mask(size)) // (x < SMAX) --> (x != SMAX) + return replace_opcode(insn, OP_SET_NE); break; case OP_SET_LE: if (value == sign_mask(size)) // (x <= SMAX) --> 1 return replace_with_pseudo(insn, value_pseudo(1)); + if (value == sign_bit(size)) // (x <= SMIN) --> (x == SMIN) + return replace_opcode(insn, OP_SET_EQ); break; case OP_SET_GE: if (value == sign_bit(size)) // (x >= SMIN) --> 1 return replace_with_pseudo(insn, value_pseudo(1)); + if (value == sign_mask(size)) // (x >= SMAX) --> (x == SMAX) + return replace_opcode(insn, OP_SET_EQ); break; case OP_SET_GT: if (value == sign_mask(size)) // (x > SMAX) --> 0 return replace_with_pseudo(insn, value_pseudo(0)); + if (value == sign_bit(size)) // (x > SMIN) --> (x != SMIN) + return replace_opcode(insn, OP_SET_NE); break; case OP_SET_B: diff --git a/validation/optim/canonical-cmps-minmax.c b/validation/optim/canonical-cmps-minmax.c index bab09282d241..48927f49db6e 100644 --- a/validation/optim/canonical-cmps-minmax.c +++ b/validation/optim/canonical-cmps-minmax.c @@ -10,7 +10,6 @@ int gt_smin(int a) { return (a > SMIN) == (a != SMIN); } /* * check-name: canonical-cmps-minmax * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-returns: 1 From patchwork Tue Jan 26 22:04:29 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 12048807 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 EF0ABC433DB for ; Wed, 27 Jan 2021 03:46:04 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id BABE4206B9 for ; Wed, 27 Jan 2021 03:46:04 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237068AbhA0Dpx (ORCPT ); Tue, 26 Jan 2021 22:45:53 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59276 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728166AbhAZWFZ (ORCPT ); Tue, 26 Jan 2021 17:05:25 -0500 Received: from mail-wm1-x334.google.com (mail-wm1-x334.google.com [IPv6:2a00:1450:4864:20::334]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 6C4DEC061793 for ; Tue, 26 Jan 2021 14:04:45 -0800 (PST) Received: by mail-wm1-x334.google.com with SMTP id u14so3724974wml.4 for ; Tue, 26 Jan 2021 14:04:45 -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=UiDtC0rGEvDBNd5KuO4qSXEFzNoVybxHjeCANkLQb90=; b=GkgJ/gyJ/Eyxyq/clbj/M4nyNgImYOo+0AXcoeIU6dkKkPaswpxji+ipOrvYe1gJEq EZR5DhnVqaNX8CeJh/V8g46VrNt2On0+nEPVl61hj7YI9MfO7fZU/YUjl8xgkZr5c7wM PccpkzW45hE671dMO2rv8Txeh/sDxYWfZvAeJk4k8ezd8Hy9I4Xgo1T1hWFB2VmFuWvV Jfm64H4mItkpk3vmHkFcInygj4kzntJKJ3IoH1tDdJ3THCT9glFtY83uCA8qg8bli2sq IkIpPKUJJSZuAMg3GvwEKhIqeLOWzmcPbI7LwJ6mzi/jbYy1XB9lQDJFHUfKCRlUIWmS MKIA== 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=UiDtC0rGEvDBNd5KuO4qSXEFzNoVybxHjeCANkLQb90=; b=an8z0Ex1/uP+2hElPnk6286CGS91UFuVKnNA7RE85uovuwMMWyw5xnumpUiErKULba 1Bop1fPVJZE/FTVp07sdwB9TSeFlj42fuXqJDp7blR35mMhOZtUWyIZizW1z67naJ9Kx hr9cS9a0ObA3vWG/j8vaO5CjOY7Skaf55xhRiDxxKGkuq0dx+hGHaJ6EfH12il0qzL3N 8njMFbJw7KC1mjuUB+wYqEPcb8ecxdP5j7KdBKGrOz7Te20e2O+BJhE4b5szSA6sTqYC 34iDTyfOmbCFThwaxiz2VCo8GG+rNKmqwSnlDVz1Yuwk4MDeasE7uwrtIadJOgAF/FR7 la8w== X-Gm-Message-State: AOAM532ZfFcm7opmzNo4YgQGkfjupSY8+3jpkhaCGYdIxTWqWdw83363 Q5S/Tq81VFq/d9mbvk29oa0Ad6P1DQY= X-Google-Smtp-Source: ABdhPJz6Ib3KNYP1e6lRZecpn8pPCVRTkAUnSpA20rKncYd3AXULfMxRptb486O+mzgulU5MB256Fg== X-Received: by 2002:a1c:4984:: with SMTP id w126mr1402302wma.139.1611698684274; Tue, 26 Jan 2021 14:04:44 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:285a:40db:3257:f0fd]) by smtp.gmail.com with ESMTPSA id b132sm5268447wmh.21.2021.01.26.14.04.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 26 Jan 2021 14:04:43 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 07/10] cmps: canonicalize SMIN/SMAX +- 1 --> EQ/NE Date: Tue, 26 Jan 2021 23:04:29 +0100 Message-Id: <20210126220432.58265-8-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.30.0 In-Reply-To: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> References: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org Compares with SMIN + 1 or SMAX - 1 are equivalent to an equality testing. For example, (x < SMIN + 1) is the same as (x == SMIN). Canonicalize these to the equality testing since these are usually simpler to handle. Signed-off-by: Luc Van Oostenryck --- simplify.c | 8 ++++++++ validation/optim/canonical-cmpe-minmax.c | 1 - 2 files changed, 8 insertions(+), 1 deletion(-) diff --git a/simplify.c b/simplify.c index f7c6c68d4ce9..ad3adb11595e 100644 --- a/simplify.c +++ b/simplify.c @@ -1175,24 +1175,32 @@ static int simplify_compare_constant(struct instruction *insn, long long value) return replace_with_pseudo(insn, value_pseudo(0)); if (value == sign_mask(size)) // (x < SMAX) --> (x != SMAX) return replace_opcode(insn, OP_SET_NE); + if (value == sign_bit(size) + 1)// (x < SMIN + 1) --> (x == SMIN) + return replace_binop_value(insn, OP_SET_EQ, sign_bit(size)); break; case OP_SET_LE: if (value == sign_mask(size)) // (x <= SMAX) --> 1 return replace_with_pseudo(insn, value_pseudo(1)); if (value == sign_bit(size)) // (x <= SMIN) --> (x == SMIN) return replace_opcode(insn, OP_SET_EQ); + if (value == sign_mask(size) - 1) // (x <= SMAX - 1) --> (x != SMAX) + return replace_binop_value(insn, OP_SET_NE, sign_mask(size)); break; case OP_SET_GE: if (value == sign_bit(size)) // (x >= SMIN) --> 1 return replace_with_pseudo(insn, value_pseudo(1)); if (value == sign_mask(size)) // (x >= SMAX) --> (x == SMAX) return replace_opcode(insn, OP_SET_EQ); + if (value == sign_bit(size) + 1)// (x >= SMIN + 1) --> (x != SMIN) + return replace_binop_value(insn, OP_SET_NE, sign_bit(size)); break; case OP_SET_GT: if (value == sign_mask(size)) // (x > SMAX) --> 0 return replace_with_pseudo(insn, value_pseudo(0)); if (value == sign_bit(size)) // (x > SMIN) --> (x != SMIN) return replace_opcode(insn, OP_SET_NE); + if (value == sign_mask(size) - 1) // (x > SMAX - 1) --> (x == SMAX) + return replace_binop_value(insn, OP_SET_EQ, sign_mask(size)); break; case OP_SET_B: diff --git a/validation/optim/canonical-cmpe-minmax.c b/validation/optim/canonical-cmpe-minmax.c index c72819244b95..32b272435fa2 100644 --- a/validation/optim/canonical-cmpe-minmax.c +++ b/validation/optim/canonical-cmpe-minmax.c @@ -10,7 +10,6 @@ int ge_smin(int a) { return (a >= (SMIN + 1)) == (a != SMIN); } /* * check-name: canonical-cmpe-minmax * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-returns: 1 From patchwork Tue Jan 26 22:04:30 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 12048809 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 2CC48C433DB for ; Wed, 27 Jan 2021 03:46:14 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E2548206B5 for ; Wed, 27 Jan 2021 03:46:13 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237072AbhA0DqB (ORCPT ); Tue, 26 Jan 2021 22:46:01 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:58790 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728170AbhAZWF0 (ORCPT ); Tue, 26 Jan 2021 17:05:26 -0500 Received: from mail-wr1-x42e.google.com (mail-wr1-x42e.google.com [IPv6:2a00:1450:4864:20::42e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 51709C061794 for ; Tue, 26 Jan 2021 14:04:46 -0800 (PST) Received: by mail-wr1-x42e.google.com with SMTP id d16so17426742wro.11 for ; Tue, 26 Jan 2021 14:04:46 -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=kgm7kxF29Ax0Vo6bQpRB0+xryXYstzCCJl7s01b9uBM=; b=UtBavKqqWrhcWOl80vDMmhHzFAJ/4+i0+qnox2WivFJ9yZLIZKEmI1WJqwRkE5pGfi 4N6rVQdaz3f6+7piTa20Hk7WZ7xm8F0lqvifmCHqrqmN+BmKdZeti5qgqhY7v9sF4uNJ rsd7hceSYezCOWLezL3x6EmBiJNi189L1eiLajPDu6nd5DYOwqKqBB95l+IPIF7o1U7x NI4xVG2ryU53f1cjl6x6rXpXYp5V5ONJrWb1StPmgBZjz3mPbaS/BWL8ZdC7b46T44q4 RC02zs9gY2rvqcaguVfGtp5fuIl5PaH/O/AuKUxcqMP9GvqHUa4czlucFdvfzh/RmGRY sMwA== 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=kgm7kxF29Ax0Vo6bQpRB0+xryXYstzCCJl7s01b9uBM=; b=h42IH9wXKRimh6+WMPhwIXFP/xxvkxIBdhcGdRZNRklpUFop1pjqRDuFKP50Op5a7G 7mcLmJmJMsRpXT3hx+oSe0ekurkX1bvOfz3B6D2RulZpIPLvY3LcYBGlIMZL3NPnqD20 qn93A5snAqBSksqgqQBbcvC7+x7JOZlzBhBA0qc6qgqnugMRoeXI4HRKYcHbddenBKvb XneBtxVJxaHq+Qfk8N0pVPYohuc+JNDASnyXoumNqR5ks8wqat2OkOQx072VKzXVW+tQ +1++2xrB+LHWCwf4QSjZSHSJra7m8n2ck/Nrpf4QZ+PWw3ogw8rdps6m6X75g8J/xM/4 wXNg== X-Gm-Message-State: AOAM533AADLjRULzqvdie9Zfs7v8nkfEpIutMdxjEi1f/3gd43KZS8m/ PAgyP8ugJVjhMirvtGKy1yV604gnNco= X-Google-Smtp-Source: ABdhPJxKT1nSKm3zR4eJ6MkQSTCytIkELUIPzSbtWfmKbhh6SrvYegOlTVRc95K4X7pC6txOrf851w== X-Received: by 2002:a5d:453b:: with SMTP id j27mr8305833wra.92.1611698685163; Tue, 26 Jan 2021 14:04:45 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:285a:40db:3257:f0fd]) by smtp.gmail.com with ESMTPSA id b132sm5268447wmh.21.2021.01.26.14.04.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 26 Jan 2021 14:04:44 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 08/10] cmps: canonicalize signed compares with constant Date: Tue, 26 Jan 2021 23:04:30 +0100 Message-Id: <20210126220432.58265-9-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.30.0 In-Reply-To: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> References: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org Modify the constants to canonicalize (x < C) to (x <= (C-1)) and (x <= C) to (x > (C-1)). This choice is partially arbitrary but 1) it's the one with the smallest positive constants, 2) it eliminates all OP_SET_LT & OP_SET_GE with a constant. A disadvantage of this choice is that we lost some compares with 0: (x < 0) is now canonicalized into (x <= -1). Note: Another good choice would be to canonicalize using the smallest absolute constants. This would keep compares with 0 but would also keep the 4 kinds of comparison. Signed-off-by: Luc Van Oostenryck --- simplify.c | 2 ++ validation/optim/canonical-cmps.c | 1 - 2 files changed, 2 insertions(+), 1 deletion(-) diff --git a/simplify.c b/simplify.c index ad3adb11595e..b29f5d5b2444 100644 --- a/simplify.c +++ b/simplify.c @@ -1177,6 +1177,7 @@ static int simplify_compare_constant(struct instruction *insn, long long value) return replace_opcode(insn, OP_SET_NE); if (value == sign_bit(size) + 1)// (x < SMIN + 1) --> (x == SMIN) return replace_binop_value(insn, OP_SET_EQ, sign_bit(size)); + changed |= replace_binop_value(insn, OP_SET_LE, (value - 1) & bits); break; case OP_SET_LE: if (value == sign_mask(size)) // (x <= SMAX) --> 1 @@ -1193,6 +1194,7 @@ static int simplify_compare_constant(struct instruction *insn, long long value) return replace_opcode(insn, OP_SET_EQ); if (value == sign_bit(size) + 1)// (x >= SMIN + 1) --> (x != SMIN) return replace_binop_value(insn, OP_SET_NE, sign_bit(size)); + changed |= replace_binop_value(insn, OP_SET_GT, (value - 1) & bits); break; case OP_SET_GT: if (value == sign_mask(size)) // (x > SMAX) --> 0 diff --git a/validation/optim/canonical-cmps.c b/validation/optim/canonical-cmps.c index f42664b21e04..42801cdce520 100644 --- a/validation/optim/canonical-cmps.c +++ b/validation/optim/canonical-cmps.c @@ -10,7 +10,6 @@ _Bool ge_x(int a) { return (a >= 1234) == (a > 1233); } /* * check-name: canonical-cmps * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-returns: 1 From patchwork Tue Jan 26 22:04:31 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 12048813 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 ECAA0C433E0 for ; Wed, 27 Jan 2021 03:46:41 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id B2CE3206B5 for ; Wed, 27 Jan 2021 03:46:41 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237079AbhA0DqO (ORCPT ); Tue, 26 Jan 2021 22:46:14 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59368 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728177AbhAZWF6 (ORCPT ); Tue, 26 Jan 2021 17:05:58 -0500 Received: from mail-wr1-x434.google.com (mail-wr1-x434.google.com [IPv6:2a00:1450:4864:20::434]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7B9A5C061797 for ; Tue, 26 Jan 2021 14:04:47 -0800 (PST) Received: by mail-wr1-x434.google.com with SMTP id a9so18101935wrt.5 for ; Tue, 26 Jan 2021 14:04:47 -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=fw5+CX6TI2CvHGEEzxLcRpfZw/VeG8LzYlccTQEiPYU=; b=HOjbI3R6ekHNj3A6RnYGb5x8uOUjxCUVr19043jYOCSny4M1CIcrfJ/YigqELw7rR5 URSem1gPVnD6DK5H+FT5jqsJ6eTbgUFxedzBNulLWnuqd2k0AdYmhktQzxiI1Wui/GhR nuqhxw75X0hxZJFhL7jHHrTvMfxp1VMgr3T0XW/9erjgPDkcEHRlX9c73dETzNTePr1v BQg+sf8jwHRGX4wtJ87p5KJn3W8eM6RjnlWyML8sP06DtqPQd7LbuOOVrYGkE4gMVrWs wPuZXVNBx1CeZPddmZ0PwflwirRHM8zDl0sgvnKlShSqeqxgjTZ3dYJOvgKdKfbCvNyx pZgw== 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=fw5+CX6TI2CvHGEEzxLcRpfZw/VeG8LzYlccTQEiPYU=; b=eUjuljjqEh12NEf0zJ16e5ulBZIBXQ/ufC8tAtRon7zafpBCA750DgxwF7GOkTzfej kYeW3RMEwHHgoY2G4IV55mEEbB6QwJlkomodHbwGDxk+PUob59sLJR0ScgPwoVQgLatV b8q9qOwytaK/ZXpzahU32lfR1vT7n1k7n7FxW737opPmCYx0zJSQajNFnNBKBPLfRgjV eh36wt5D9lPQQslxM4skfV46EtvykiDL1/93ae8tY0R4pMz536LfBlQDdCuWiNYoacmw bywZRs9TWC6cJRrej12/5WR1n20xwhwvPSQrkt3kBNaFl308N6krrOEu4WMuBmct9d1S i8KQ== X-Gm-Message-State: AOAM530r/wWceuqf4Cs6PxtsQBG8+7F+/1ZBxj5isgqgv2cPPDub4Kkk IIpAh6xtG+r9kdUdIuzjlMbsREv7dYU= X-Google-Smtp-Source: ABdhPJz+FmKkXO0q3MfxDIhrsnHzz3kLbmvcsazHcpWLX/aFBgvbExCZVEAQnVf0X3IfSgSxdot1TA== X-Received: by 2002:a5d:58ec:: with SMTP id f12mr8050266wrd.134.1611698686350; Tue, 26 Jan 2021 14:04:46 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:285a:40db:3257:f0fd]) by smtp.gmail.com with ESMTPSA id b132sm5268447wmh.21.2021.01.26.14.04.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 26 Jan 2021 14:04:45 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 09/10] cmps: canonicalize SEL(x {<,<=} y, a, b) --> SEL(x {>=,>} y, b, a) Date: Tue, 26 Jan 2021 23:04:31 +0100 Message-Id: <20210126220432.58265-10-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.30.0 In-Reply-To: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> References: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org Both compares and OP_SELECT are anti-symmetrical: swapping the arguments is equivalent to inversing the condition. As consequence, when combined, they're symmetrical: swapping the arguments of the compare (or equivalently reversing the direction of the compare) and swapping the operand of the OP_SELECT is a no-op, both forms are equivalent. So, canonicalize these to always use OP_GT or OP_GE. Signed-off-by: Luc Van Oostenryck --- simplify.c | 7 +++++++ validation/optim/canonical-cmps-sel.c | 1 - 2 files changed, 7 insertions(+), 1 deletion(-) diff --git a/simplify.c b/simplify.c index b29f5d5b2444..10cdf50dcbf1 100644 --- a/simplify.c +++ b/simplify.c @@ -2301,6 +2301,13 @@ static int simplify_select(struct instruction *insn) if (src2 == def->src1 && src1 == def->src2) return replace_with_pseudo(insn, src1); // SEL(y!=x,x,y) --> x break; + case OP_SET_LE: case OP_SET_LT: + case OP_SET_BE: case OP_SET_B: + if (!one_use(cond)) + break; + // SEL(x {<,<=} y, a, b) --> SEL(x {>=,>} y, b, a) + def->opcode = opcode_negate(def->opcode); + return switch_pseudo(insn, &insn->src2, insn, &insn->src3); case OP_SEL: if (constant(def->src2) && constant(def->src3)) { // Is the def of the conditional another select? diff --git a/validation/optim/canonical-cmps-sel.c b/validation/optim/canonical-cmps-sel.c index f0a0effc7954..bba5e5c894f8 100644 --- a/validation/optim/canonical-cmps-sel.c +++ b/validation/optim/canonical-cmps-sel.c @@ -19,7 +19,6 @@ _Bool sel_leu(unsigned int a, unsigned int b, int x, int y) /* * check-name: canonical-cmps-sel * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-returns: 1 From patchwork Tue Jan 26 22:04:32 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 12048811 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 737FAC433DB for ; Wed, 27 Jan 2021 03:46:31 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 3A60E206B5 for ; Wed, 27 Jan 2021 03:46:31 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237074AbhA0DqF (ORCPT ); Tue, 26 Jan 2021 22:46:05 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:58796 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728173AbhAZWF3 (ORCPT ); Tue, 26 Jan 2021 17:05:29 -0500 Received: from mail-wr1-x429.google.com (mail-wr1-x429.google.com [IPv6:2a00:1450:4864:20::429]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 70FFDC0617A7 for ; Tue, 26 Jan 2021 14:04:48 -0800 (PST) Received: by mail-wr1-x429.google.com with SMTP id v15so18086287wrx.4 for ; Tue, 26 Jan 2021 14:04:48 -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=4Tf4QCvFpyAobhU0JFMAJACQeSxWnQofabURU0HmY5I=; b=VC2pGgUtWd4hsm1jHOaWSEr+PiNcwjaka1x5WSfbOTGLs7+4os7ySxK+noeVcaRA8m SYDNA83fzfXWc5j7kbRNiMekFx+Mgmk4AsPMVWH0XLUQ/9PmzmAbWgBdAbqnjwPS+H0Q TNitmErltuUIhP6jVtOvVOkNaVWo1HSyv4E5SuU5JtbhZo52yKzR9r2uEKzFu6qeITVi 6mxTJxJCtLXrE6AQRZXYpq++qvw34OdRyaPfz21H5SAvT8jmzZITcL1QBwUJWZmKSH0/ OsMh/9yCrB9BHPLz60BBhBOqGB5zgINZje7k48iK1NyiBUkTFeRQxNDaWlJ8I92+Vv/k JBdA== 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=4Tf4QCvFpyAobhU0JFMAJACQeSxWnQofabURU0HmY5I=; b=Y5H5mOrII5UuZrpMMcuSQ+Dh3Mv7uNGOCSvN+luAcisWtU3tMvF0Dx29rG/iCa/pVl GDdtOIs+zxLvwKeCYS1JB5wXNStA0UoJRQVvpHVZV3BPaB1TOZ/OgF/d0U8iVzCXTjG6 AjGyUdVktVTtr85+8IgDxKj0tvfYQyebiWDqYMd9S5NMkvrCjVYnsGBZImJMuIVu/M3X 4qar1xLQfZeTHH0hVxXL6gA6E5FnRsLoF4YtoXRYk+RN6+aI0nwP+od64wgm+RXPcmcI IHChT7GJZR5TbBpVzBK37ueMklC7BnHwbNlalM7exaLaEaqKYuA55eUg7IPJmpd/eIJv WhdQ== X-Gm-Message-State: AOAM533PUzpZ6FljP8JYiYAAB6VZFWRBqKZkEOhFwgeOK9pRpMnW/ME2 g9/8bPK3koKGypW8qt1ODoTKKyjLx3Y= X-Google-Smtp-Source: ABdhPJxraAXlk0iG5esLm7vrLzAHdXXgXOpf7+D9qjGcifMVJf+uQ+dQDMiLUK35OEzhLQun5mWv6w== X-Received: by 2002:a05:6000:254:: with SMTP id m20mr8268234wrz.300.1611698687292; Tue, 26 Jan 2021 14:04:47 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:285a:40db:3257:f0fd]) by smtp.gmail.com with ESMTPSA id b132sm5268447wmh.21.2021.01.26.14.04.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 26 Jan 2021 14:04:46 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 10/10] cmps: canonicalize SEL(x > 0, a, -a) --> SEL(x >= 0, a, -a) Date: Tue, 26 Jan 2021 23:04:32 +0100 Message-Id: <20210126220432.58265-11-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.30.0 In-Reply-To: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> References: <20210126220432.58265-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org When computing the absolute value using an expression like: (a > 0) ? a : -a it's irrelevant to use '>' or '>=', both will give the same result since 0 is its own negation. Canonicalize these equivalent expressions, such that OP_GE is always used. Signed-off-by: Luc Van Oostenryck --- simplify.c | 14 ++++++++++++++ validation/optim/canonical-abs.c | 1 - 2 files changed, 14 insertions(+), 1 deletion(-) diff --git a/simplify.c b/simplify.c index 10cdf50dcbf1..584078ddca89 100644 --- a/simplify.c +++ b/simplify.c @@ -454,6 +454,13 @@ static inline pseudo_t is_same_op(pseudo_t src, int op, unsigned osize) return def->src; } +static bool is_negate_of(pseudo_t p, pseudo_t ref) +{ + struct instruction *def; + + return (DEF_OPCODE(def, p) == OP_NEG) && (def->src == ref); +} + /// // replace the operand of an instruction // @insn: the instruction @@ -2308,6 +2315,13 @@ static int simplify_select(struct instruction *insn) // SEL(x {<,<=} y, a, b) --> SEL(x {>=,>} y, b, a) def->opcode = opcode_negate(def->opcode); return switch_pseudo(insn, &insn->src2, insn, &insn->src3); + case OP_SET_GT: + if (one_use(cond) && is_zero(def->src2)) { + if (is_negate_of(src2, src1)) + // SEL(x > 0, a, -a) --> SEL(x >= 0, a, -a) + return replace_opcode(def, OP_SET_GE); + } + break; case OP_SEL: if (constant(def->src2) && constant(def->src3)) { // Is the def of the conditional another select? diff --git a/validation/optim/canonical-abs.c b/validation/optim/canonical-abs.c index 0809a52d445b..1bd6d89a3ad5 100644 --- a/validation/optim/canonical-abs.c +++ b/validation/optim/canonical-abs.c @@ -5,7 +5,6 @@ _Bool abs2(int a) { return (a < 0 ? -a : a) == (a <= 0 ? -a : a); } /* * check-name: canonical-abs1 * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-returns: 1