From patchwork Tue Mar 9 23:42: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: 12126703 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 6042AC433E9 for ; Tue, 9 Mar 2021 23:43:18 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 0B64C6511F for ; Tue, 9 Mar 2021 23:43:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232215AbhCIXmr (ORCPT ); Tue, 9 Mar 2021 18:42:47 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37630 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232209AbhCIXmj (ORCPT ); Tue, 9 Mar 2021 18:42:39 -0500 Received: from mail-ed1-x52b.google.com (mail-ed1-x52b.google.com [IPv6:2a00:1450:4864:20::52b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 83281C06174A for ; Tue, 9 Mar 2021 15:42:39 -0800 (PST) Received: by mail-ed1-x52b.google.com with SMTP id w9so24046476edc.11 for ; Tue, 09 Mar 2021 15:42: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=Wz7JQ0OrzzITtZbsc9a+g1KoRJ0GXqBxQR5f1BRXLF4=; b=RB59b/O8KSlS51Y8wJas3TebtsoHmatibtjAxVfS8v8dlAez5xri3Ee9xTeBnN/6rQ WLQcIaERWvFUd/NhNR8f4O3VsYoyVNIjNfT1vDqFTnBL2yLxzITjSWQ3tV2lbBETEjtX 7Iq1GUyQl6KxJDrV44TlKF+fYNX0ladLd53nlmGNAckNbXZqhpMxep4o4vxNhmvXcYLX 9MVHHXqbTpDBqe5t1Yk8Mk8ZXTY0MejhdFbdUzYVQDyrJU9Smz++YPczZWqsqcnSaltA UwyUNHkddS6Q64yIuqO4KUZF1RsByb++EtVZ2nUTI7mhx+gvIKxdJVFlt9ZfEShcx/sG NibQ== 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=Wz7JQ0OrzzITtZbsc9a+g1KoRJ0GXqBxQR5f1BRXLF4=; b=cSpD9I62r7ExQFn46k8Hg4ZQNox/9YQ07j7JcozCb97PaVlkpZonGmEg+TTUuIALIb A8xATXktaK16ollvXC/aQG1Cs2VJ8m8cyIoB5IaoR81QfIwwedEO5Op9BdooE39OhlGz 0BLBnBy2zZWYHKF3Nvrt1YRibzgDEeYaxP9qS3xHkdzKZB8tGiKK8jq5i3ZVxPpo7xXF vsCCkiro0CzgmDB5IPMHU6EWjNMltPCglQ3ak2/0vA2q5NpPJC4mtJz0pSpy3uNF9jYS 1Hq6rKb2PTsRrRShoDhzYhmW95ZFutFj8co8R1DELyUnbBfJYHeJ+/YWUCaxi1mXBdbm C+wQ== X-Gm-Message-State: AOAM533iyh4i1FoblkB6qODtKz2lWH/SZFOo9UoeHUoiiTd3WkgUeKIO m8VbTd0IK/LEdBhfcjMwBoWvtULEQKk= X-Google-Smtp-Source: ABdhPJw5ZxCfR5s6YwgDNT+RR8HJa1AVVWMD7wxsFhPW77MmotckvT+AL/Dr4xDS9mX1qmHEG2Zg7w== X-Received: by 2002:a05:6402:1c98:: with SMTP id cy24mr159823edb.296.1615333358320; Tue, 09 Mar 2021 15:42:38 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:1dad:50b9:7959:c788]) by smtp.gmail.com with ESMTPSA id cw14sm10147984edb.8.2021.03.09.15.42.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 09 Mar 2021 15:42:37 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 1/4] ssa: add some testcases for mismatched memops Date: Wed, 10 Mar 2021 00:42:29 +0100 Message-Id: <20210309234232.50889-2-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.30.0 In-Reply-To: <20210309234232.50889-1-luc.vanoostenryck@gmail.com> References: <20210309234232.50889-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org The SSA conversion is incorrect when the size or offset of the memory operations doesn't match. It shouldn't be done at all. So, add a few testcases for this. Signed-off-by: Luc Van Oostenryck --- validation/mem2reg/not-same-memop0.c | 49 ++++++++++++++++++++++++++++ validation/mem2reg/packed-bitfield.c | 36 ++++++++++++++++++++ 2 files changed, 85 insertions(+) create mode 100644 validation/mem2reg/not-same-memop0.c create mode 100644 validation/mem2reg/packed-bitfield.c diff --git a/validation/mem2reg/not-same-memop0.c b/validation/mem2reg/not-same-memop0.c new file mode 100644 index 000000000000..7a84ddce4efc --- /dev/null +++ b/validation/mem2reg/not-same-memop0.c @@ -0,0 +1,49 @@ +struct s { + int:16; + short f:6; +}; + +static short local(struct s s) +{ + return s.f; +} + +static void foo(struct s s) +{ + while (s.f) ; +} + +/* + * check-name: not-same-memop0 + * check-command: test-linearize -Wno-decl -fdump-ir=mem2reg $file + * check-known-to-fail + * + * check-output-start +local: +.L0: + + store.32 %arg1 -> 0[s] + load.16 %r1 <- 2[s] + trunc.6 %r2 <- (16) %r1 + sext.16 %r3 <- (6) %r2 + ret.16 %r3 + + +foo: +.L2: + + store.32 %arg1 -> 0[s] + br .L6 + +.L6: + load.16 %r5 <- 2[s] + trunc.6 %r6 <- (16) %r5 + setne.1 %r7 <- %r6, $0 + cbr %r7, .L6, .L5 + +.L5: + ret + + + * check-output-end + */ diff --git a/validation/mem2reg/packed-bitfield.c b/validation/mem2reg/packed-bitfield.c new file mode 100644 index 000000000000..4eaf0befeaf5 --- /dev/null +++ b/validation/mem2reg/packed-bitfield.c @@ -0,0 +1,36 @@ +struct s { + int:16; + int f:16; +} __attribute__((__packed__)); + +static void foo(struct s s) +{ + while (s.f) + ; +} + +/* + * check-name: packed-bitfield + * check-command: test-linearize -fmem2reg $file + * check-known-to-fail + * + * check-output-contains: store.32 + * check-output-contains: load.16 + * + * check-output-start +foo: +.L0: + + store.32 %arg1 -> 0[s] + br .L4 + +.L4: + load.16 %r1 <- 2[s] + cbr %r1, .L4, .L3 + +.L3: + ret + + + * check-output-end + */ From patchwork Tue Mar 9 23:42: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: 12126705 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 3FF36C433E6 for ; Tue, 9 Mar 2021 23:43:18 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E65B865100 for ; Tue, 9 Mar 2021 23:43:17 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232213AbhCIXmq (ORCPT ); Tue, 9 Mar 2021 18:42:46 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37638 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232225AbhCIXmk (ORCPT ); Tue, 9 Mar 2021 18:42:40 -0500 Received: from mail-ed1-x52a.google.com (mail-ed1-x52a.google.com [IPv6:2a00:1450:4864:20::52a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 42DE8C06174A for ; Tue, 9 Mar 2021 15:42:40 -0800 (PST) Received: by mail-ed1-x52a.google.com with SMTP id x9so24036141edd.0 for ; Tue, 09 Mar 2021 15:42: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=es/SK1q1KGUvCOyVSta1FFBoZxR4tOMghpelImSO+4w=; b=q8kGLveFFtyEO+eUI6iws6MF/9SzMyngXxRiFBn48ZWatNGtlkUsh52hBVGWGcEPzU xeA5cYcvKFHOJoLL2Unp+2UKwChIQwjV5bgVeeANkkPgq2XJ9xNpft0IahXgr1mPzFXI qi3DputOGWHPgAHXQb6u7ILENedGXLmbz/8EQtlJWwFAmXt6FKuxyYahtIV8A8hS8/qA 0lIm043Ob2/rmkvEVPMuPvdsU2pUDagPjaY+Mfdod8IQT2ufpfLY+PZ+h2XXmReX2x4g 8hk9cirVhA3VYCnpRDIFoSMwrlTu44AnxVNAFC3F8RFfe/O5c3yXGjh4TdrqIdHuqW6g cTMw== 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=es/SK1q1KGUvCOyVSta1FFBoZxR4tOMghpelImSO+4w=; b=FytZv6tc+kZre83U9DHpqDzu59khGoQKSRcfTsMk+R0CayUXWH1jqAHHxsmu/5ID+t NdQsHHvOmP2pW//tZbXbpsDvYgN5ong9qEZPkqSjjCBG1k5oMhPdtN0WSoXWKoGOnxOx pU0w2Ihs++yLY0wXafabHTbRrfmLc56BQl3nqAQm/mEfR69AS3h8yTben2uV6pAEJycC uPyVm/VTAzeb+UNDT+JY7tMaKwRubZ8mKHmPuFkEnY/huG6X+LD48Yts05aBlpkbBIeP EpIefV9yK4pKsPRG0au911vDyEzMC9ynbxti12K3gPREE3Rsmm7CCO4AVLymf/zkUdu+ uiRA== X-Gm-Message-State: AOAM5317mRzGyvO0Tq99pHw1HsVYW2w/nm4jVpHUXL0n89ZQBCPUETeY EWmAC8nulvWUh57odDRqyIRPQGQBTew= X-Google-Smtp-Source: ABdhPJwwEiNoA31sW+mm2AKKM3jROM6ZMjnfEw8A3f1wNhX5ngQFCUGeTQxvWzW9LJVFH0D/7xzzMg== X-Received: by 2002:a50:ed83:: with SMTP id h3mr178239edr.140.1615333359066; Tue, 09 Mar 2021 15:42:39 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:1dad:50b9:7959:c788]) by smtp.gmail.com with ESMTPSA id cw14sm10147984edb.8.2021.03.09.15.42.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 09 Mar 2021 15:42:38 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 2/4] ssa: the sparse set is not needed Date: Wed, 10 Mar 2021 00:42:30 +0100 Message-Id: <20210309234232.50889-3-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.30.0 In-Reply-To: <20210309234232.50889-1-luc.vanoostenryck@gmail.com> References: <20210309234232.50889-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org The implementation of a 'sparse set without initialization' was somehow needed during the initial design but it's not needed anymore. So, remove the implementation and replace its use by the usual bb->generation mechanism. Signed-off-by: Luc Van Oostenryck --- Makefile | 1 - ssa.c | 11 ++++------- sset.c | 28 ---------------------------- sset.h | 56 -------------------------------------------------------- 4 files changed, 4 insertions(+), 92 deletions(-) delete mode 100644 sset.c delete mode 100644 sset.h diff --git a/Makefile b/Makefile index f9883da101c7..6ad14375b3cd 100644 --- a/Makefile +++ b/Makefile @@ -63,7 +63,6 @@ LIB_OBJS += show-parse.o LIB_OBJS += simplify.o LIB_OBJS += sort.o LIB_OBJS += ssa.o -LIB_OBJS += sset.o LIB_OBJS += stats.o LIB_OBJS += storage.o LIB_OBJS += symbol.o diff --git a/ssa.c b/ssa.c index b9044207db16..3f4fa1a831df 100644 --- a/ssa.c +++ b/ssa.c @@ -7,7 +7,6 @@ #include #include "ssa.h" #include "lib.h" -#include "sset.h" #include "dominate.h" #include "flowgraph.h" #include "linearize.h" @@ -162,13 +161,12 @@ static bool rewrite_single_store(struct instruction *store) return true; } -static struct sset *processed; - // we would like to know: // is there one or more stores? // are all loads & stores local/done in a single block? static void ssa_convert_one_var(struct entrypoint *ep, struct symbol *var) { + unsigned long generation = ++bb_generation; struct basic_block_list *alpha = NULL; struct basic_block_list *idf = NULL; struct basic_block *samebb = NULL; @@ -199,7 +197,6 @@ static void ssa_convert_one_var(struct entrypoint *ep, struct symbol *var) return; // 1) insert in the worklist all BBs that may modify var - sset_reset(processed); FOR_EACH_PTR(addr->users, pu) { struct instruction *insn = pu->insn; struct basic_block *bb = insn->bb; @@ -208,8 +205,10 @@ static void ssa_convert_one_var(struct entrypoint *ep, struct symbol *var) case OP_STORE: nbr_stores++; store = insn; - if (!sset_testset(processed, bb->nr)) + if (bb->generation != generation) { + bb->generation = generation; add_bb(&alpha, bb); + } /* fall through */ case OP_LOAD: if (local) { @@ -390,8 +389,6 @@ void ssa_convert(struct entrypoint *ep) bb->phi_map = NULL; } END_FOR_EACH_PTR(bb); - processed = sset_init(first, last); - // try to promote memory accesses to pseudos FOR_EACH_PTR(ep->accesses, pseudo) { ssa_convert_one_var(ep, pseudo->sym); diff --git a/sset.c b/sset.c deleted file mode 100644 index e9681e00ddd4..000000000000 --- a/sset.c +++ /dev/null @@ -1,28 +0,0 @@ -// SPDX-License-Identifier: MIT -// -// sset.c - an all O(1) implementation of sparse sets as presented in: -// "An Efficient Representation for Sparse Sets" -// by Preston Briggs and Linda Torczon -// -// Copyright (C) 2017 - Luc Van Oostenryck - -#include "sset.h" -#include "lib.h" -#include - - -struct sset *sset_init(unsigned int first, unsigned int last) -{ - unsigned int size = last - first + 1; - struct sset *s = malloc(sizeof(*s) + size * 2 * sizeof(s->sets[0])); - - s->size = size; - s->off = first; - s->nbr = 0; - return s; -} - -void sset_free(struct sset *s) -{ - free(s); -} diff --git a/sset.h b/sset.h deleted file mode 100644 index 69cee18a2768..000000000000 --- a/sset.h +++ /dev/null @@ -1,56 +0,0 @@ -// SPDX-License-Identifier: MIT - -#ifndef SSET_H -#define SSET_H - -/* - * sset.h - an all O(1) implementation of sparse sets as presented in: - * "An Efficient Representation for Sparse Sets" - * by Preston Briggs and Linda Torczon - * - * Copyright (C) 2017 - Luc Van Oostenryck - */ - -#include - -struct sset { - unsigned int nbr; - unsigned int off; - unsigned int size; - unsigned int sets[0]; -}; - -extern struct sset *sset_init(unsigned int size, unsigned int off); -extern void sset_free(struct sset *s); - - -static inline void sset_reset(struct sset *s) -{ - s->nbr = 0; -} - -static inline void sset_add(struct sset *s, unsigned int idx) -{ - unsigned int __idx = idx - s->off; - unsigned int n = s->nbr++; - s->sets[__idx] = n; - s->sets[s->size + n] = __idx; -} - -static inline bool sset_test(struct sset *s, unsigned int idx) -{ - unsigned int __idx = idx - s->off; - unsigned int n = s->sets[__idx]; - - return (n < s->nbr) && (s->sets[s->size + n] == __idx); -} - -static inline bool sset_testset(struct sset *s, unsigned int idx) -{ - if (sset_test(s, idx)) - return true; - sset_add(s, idx); - return false; -} - -#endif From patchwork Tue Mar 9 23:42: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: 12126709 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 8C10CC4332D for ; Tue, 9 Mar 2021 23:43:18 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6819C65111 for ; Tue, 9 Mar 2021 23:43:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232200AbhCIXmr (ORCPT ); Tue, 9 Mar 2021 18:42:47 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37640 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232227AbhCIXml (ORCPT ); Tue, 9 Mar 2021 18:42:41 -0500 Received: from mail-ed1-x52e.google.com (mail-ed1-x52e.google.com [IPv6:2a00:1450:4864:20::52e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 07D0BC06174A for ; Tue, 9 Mar 2021 15:42:41 -0800 (PST) Received: by mail-ed1-x52e.google.com with SMTP id m9so24052786edd.5 for ; Tue, 09 Mar 2021 15:42: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=reRUHmuQaArHa3HhSjsmi+MCjA7ucxAIN8NpZBPutWo=; b=Xgc4BIweitELayiPx00eMdN0WVL1n/BV9yB5RQcOWX27NQbrN16zBRe+A+EQ1WI0bJ WTXiwalYHV5zehNzwbx1jSU01VZrcYnqtyu02Qef8osWmcCGyWHgktAigkdu3f6him11 pgz5MwQkIeU0a0gexlqvs9vrAKVns0pUnilbaa9WqATMx6YI6CXsdCWh5dOjhSdd+0bc p6Qg3eI58BYUyUEdDC80VCiCDRRuWnyBIlO4+Gp04nhJ7nBICM5BC9wmJHIgpw1cXwxW b6u19xtmqGsNNAjgK4/sm25oe+1n5fqYII2Rri5oY+Z2fvPlhKG550M7VhcaSMxp5q0V gHAg== 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=reRUHmuQaArHa3HhSjsmi+MCjA7ucxAIN8NpZBPutWo=; b=sOFSXQ9KjtpOFInZ4XOjDfjk9tq0tO1xPOeNdbCmU+fBF/G9VLmhblVFvfnRTWDVz+ JynbOFYMnb0Jp9DqouGMOA8BnL4lALPZu4E8xz6ZtS5fYwM7cy0R+iFpbhvFh1t1NyS/ e3cZekySNU5W0V3MUzXOeLLcZJsNPWMhQZ3nOkwmg1pYxQ/xOagMqox44AMDKRwOfP2T +vAbS+a4uYwIKM9L0WXHUmhAiqbUlPrKBJBPy8R4Y5SyOKLMK2LRujF2iMx8+8LHkSEN boVQmWnWf22X0PucC//sjm0ZmK5tQOB+7ZlR5e8bxZncd2tvnjFzRAfQoXxwTeGX2Z7e Pcow== X-Gm-Message-State: AOAM532PLjm7lw/Fr+1ZvwB2FJkdnXmcg9gQ/8wPcaGVI32mpTaqYoY3 6zeUdnkcq1Dm/kwmqR+scxIPy5BuYzo= X-Google-Smtp-Source: ABdhPJz9QVKRek6p0yxZ/mH+q1q/4jlABvcRtTtBDSdPNjqAOGXV8RO27ad0MZaIsr0bG8ZmFFLg3g== X-Received: by 2002:a50:e14d:: with SMTP id i13mr173487edl.106.1615333359864; Tue, 09 Mar 2021 15:42:39 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:1dad:50b9:7959:c788]) by smtp.gmail.com with ESMTPSA id cw14sm10147984edb.8.2021.03.09.15.42.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 09 Mar 2021 15:42:39 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 3/4] ssa: avoid SSA conversion of packed bitfields Date: Wed, 10 Mar 2021 00:42:31 +0100 Message-Id: <20210309234232.50889-4-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.30.0 In-Reply-To: <20210309234232.50889-1-luc.vanoostenryck@gmail.com> References: <20210309234232.50889-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org Packed bitfields are incompatible with the SSA conversion which works on the assumption that memory operations are done on the whole symbol. So, directly exclude packed bitfields from the SSA conversion. Signed-off-by: Luc Van Oostenryck --- ssa.c | 3 +++ validation/mem2reg/packed-bitfield.c | 1 - 2 files changed, 3 insertions(+), 1 deletion(-) diff --git a/ssa.c b/ssa.c index 3f4fa1a831df..26d46baaa16c 100644 --- a/ssa.c +++ b/ssa.c @@ -32,6 +32,9 @@ static inline bool is_promotable(struct symbol *type) case SYM_STRUCT: // we allow a single scalar field // but a run of bitfields count for 1 + // (and packed bifields are excluded). + if (type->packed) + return 0; nbr = 0; bf_seen = 0; FOR_EACH_PTR(type->symbol_list, member) { diff --git a/validation/mem2reg/packed-bitfield.c b/validation/mem2reg/packed-bitfield.c index 4eaf0befeaf5..f3ee259a62b8 100644 --- a/validation/mem2reg/packed-bitfield.c +++ b/validation/mem2reg/packed-bitfield.c @@ -12,7 +12,6 @@ static void foo(struct s s) /* * check-name: packed-bitfield * check-command: test-linearize -fmem2reg $file - * check-known-to-fail * * check-output-contains: store.32 * check-output-contains: load.16 From patchwork Tue Mar 9 23:42: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: 12126707 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 6A73BC43381 for ; Tue, 9 Mar 2021 23:43:18 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 39249650FD for ; Tue, 9 Mar 2021 23:43:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232209AbhCIXms (ORCPT ); Tue, 9 Mar 2021 18:42:48 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37648 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231929AbhCIXmm (ORCPT ); Tue, 9 Mar 2021 18:42:42 -0500 Received: from mail-ej1-x62b.google.com (mail-ej1-x62b.google.com [IPv6:2a00:1450:4864:20::62b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B6FB8C06174A for ; Tue, 9 Mar 2021 15:42:41 -0800 (PST) Received: by mail-ej1-x62b.google.com with SMTP id bm21so33028555ejb.4 for ; Tue, 09 Mar 2021 15:42: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=NDOrXrXq3W6dYiwD4LWQb5jtSN56eL5saJFxPOWBAII=; b=KkdaxAOL+C/trHOuX2SvP6KBtt/PzFQzRANJ9WDfdGp+Om2tJgmiuhErmzgauZGi3s DOmb61QleE6qDGse5EPvEjgRyv8Y1O9QzPvHd8zFqvuP+CHCWLswJOG/srQDUDCCAQvp 2wP5irjSmRbGLc+6g46uZglu/TvCmgQsxV95x4rCwP7uglusbvtGU3Ux5o2KfFQCoEvG vgGBP9zgLNA1uFH9jHp8z7MMR/nistJqd2u0GsOSj+sEzFLD14hiro8a1n3ODEaFsmMd Rwiypx3Oi4X+JLJkZzUDY0ygK73j2R7yJVY1jJfKDzkL35dxUUi3gWQx/LDnG1NJ5Eb/ hdag== 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=NDOrXrXq3W6dYiwD4LWQb5jtSN56eL5saJFxPOWBAII=; b=CDQe/jEKT9IrXbjDw4ZgcxKDFvlNO8qqTYlZotybhDGdemlGp0ZJRdlI6CLd2YDJDl 3PKrE8M6Epco64dic8RvvBEbuJPhFnYRwjdl70hRRjdSewSVigsbE3dL//Xk3mCgqjIl Gu8dMUKee8yHq5D4jz2kPcqC0azrSNAfOaBJpqbIEhIJzdeNGNTzSWHHXqCbgVZFYEe1 usuBpZXHOaZimX7FSnoHntcfr4XLF7gXwFIn0OKR8jw410H3R/lKpFVYBgCikaoPuQR3 QZOEKT+jXYVdv4bRDcYwhy4IozZj4ezdP+L7lhUe1poXIyFzKBII9I5kZNOGIcRLeeC8 WBPg== X-Gm-Message-State: AOAM532uyJbnnVYnG/ay1nLNYXWqeaETwQ8ssnrqZfjGfdwNdHUDkpNm IVso4yIVe9+h+gxyTVELjoGc2PpKMrg= X-Google-Smtp-Source: ABdhPJxkwPif/YLdwjQzbFJsTqCo92Z/sIORM7uGT7LCqxeyvtjoPUbYYPTei76vWKZg2kbx6/AqSA== X-Received: by 2002:a17:906:ecf3:: with SMTP id qt19mr502283ejb.467.1615333360540; Tue, 09 Mar 2021 15:42:40 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:1dad:50b9:7959:c788]) by smtp.gmail.com with ESMTPSA id cw14sm10147984edb.8.2021.03.09.15.42.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 09 Mar 2021 15:42:40 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 4/4] ssa: fix conversion with mismatched size or offset Date: Wed, 10 Mar 2021 00:42:32 +0100 Message-Id: <20210309234232.50889-5-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.30.0 In-Reply-To: <20210309234232.50889-1-luc.vanoostenryck@gmail.com> References: <20210309234232.50889-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org The SSA conversion works under the assumption that all the memory operations on a given symbol always refer to the same object. So, exclude the conversion of variables where: * memory operations do not always match in size or offset * there is an implicit integer/float conversion. Signed-off-by: Luc Van Oostenryck --- linearize.h | 2 +- ssa.c | 97 ++++++++++++++++++++++------ validation/mem2reg/not-same-memop0.c | 1 - 3 files changed, 80 insertions(+), 20 deletions(-) diff --git a/linearize.h b/linearize.h index 7909b01f29c5..86ae119c82e6 100644 --- a/linearize.h +++ b/linearize.h @@ -18,7 +18,7 @@ struct pseudo_user { DECLARE_ALLOCATOR(pseudo_user); DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user); -DECLARE_PTRMAP(phi_map, struct symbol *, pseudo_t); +DECLARE_PTRMAP(phi_map, struct symbol *, struct instruction *); enum pseudo_type { diff --git a/ssa.c b/ssa.c index 26d46baaa16c..f61672a0b530 100644 --- a/ssa.c +++ b/ssa.c @@ -96,10 +96,22 @@ static void kill_store(struct instruction *insn) insn->bb = NULL; } +static bool same_memop(struct instruction *a, struct instruction *b) +{ + if (a->size != b->size || a->offset != b->offset) + return false; + if (is_integral_type(a->type) && is_float_type(b->type)) + return false; + if (is_float_type(a->type) && is_integral_type(b->type)) + return false; + return true; +} + static void rewrite_local_var(struct basic_block *bb, pseudo_t addr, int nbr_stores, int nbr_uses) { + struct instruction *store = NULL; struct instruction *insn; - pseudo_t val = NULL; + bool remove = false; if (!bb) return; @@ -110,18 +122,21 @@ static void rewrite_local_var(struct basic_block *bb, pseudo_t addr, int nbr_sto continue; switch (insn->opcode) { case OP_LOAD: - if (!val) - val = undef_pseudo(); - replace_with_pseudo(insn, val); + if (!store) + replace_with_pseudo(insn, undef_pseudo()); + else if (same_memop(store, insn)) + replace_with_pseudo(insn, store->target); + else + remove = false; break; case OP_STORE: - val = insn->target; - // can't use kill_instruction() unless - // we add a fake user to val - kill_store(insn); + store = insn; + remove = true; break; } } END_FOR_EACH_PTR(insn); + if (remove) + kill_store(store); } static bool rewrite_single_store(struct instruction *store) @@ -139,6 +154,8 @@ static bool rewrite_single_store(struct instruction *store) // by the value from the store. This is only valid // if the store dominate the load. + if (!same_memop(store, insn)) + continue; if (insn->bb == store->bb) { // the load and the store are in the same BB // we can convert if the load is after the store. @@ -257,21 +274,40 @@ external_visibility: kill_dead_stores(ep, addr, !mod); } -static pseudo_t lookup_var(struct basic_block *bb, struct symbol *var) +static struct instruction *lookup_var(struct basic_block *bb, struct symbol *var) { do { - pseudo_t val = phi_map_lookup(bb->phi_map, var); - if (val) - return val; + struct instruction *insn = phi_map_lookup(bb->phi_map, var); + if (insn) + return insn; } while ((bb = bb->idom)); - return undef_pseudo(); + return NULL; } static struct instruction_list *phis_all; static struct instruction_list *phis_used; +static struct instruction_list *stores; + +static bool matching_load(struct instruction *def, struct instruction *insn) +{ + if (insn->size != def->size) + return false; + switch (def->opcode) { + case OP_STORE: + case OP_LOAD: + if (insn->offset != def->offset) + return false; + case OP_PHI: + break; + default: + return false; + } + return true; +} static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn) { + struct instruction *def; struct symbol *var; pseudo_t addr; pseudo_t val; @@ -284,8 +320,8 @@ static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn) var = addr->sym; if (!var || !var->torename) break; - phi_map_update(&bb->phi_map, var, insn->target); - kill_store(insn); + phi_map_update(&bb->phi_map, var, insn); + add_instruction(&stores, insn); break; case OP_LOAD: addr = insn->src; @@ -294,14 +330,22 @@ static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn) var = addr->sym; if (!var || !var->torename) break; - val = lookup_var(bb, var); + def = lookup_var(bb, var); + if (!def) { + val = undef_pseudo(); + } else if (!matching_load(def, insn)) { + var->torename = false; + break; + } else { + val = def->target; + } replace_with_pseudo(insn, val); break; case OP_PHI: var = insn->type; if (!var || !var->torename) break; - phi_map_update(&bb->phi_map, var, insn->target); + phi_map_update(&bb->phi_map, var, insn); add_instruction(&phis_all, insn); break; } @@ -348,7 +392,8 @@ static void ssa_rename_phi(struct instruction *insn) return; FOR_EACH_PTR(insn->bb->parents, par) { struct instruction *term = delete_last_instruction(&par->insns); - pseudo_t val = lookup_var(par, var); + struct instruction *def = lookup_var(par, var); + pseudo_t val = def ? def->target : undef_pseudo(); pseudo_t phi = alloc_phi(par, val, var); phi->ident = var->ident; add_instruction(&par->insns, term); @@ -376,6 +421,18 @@ static void ssa_rename_phis(struct entrypoint *ep) } END_FOR_EACH_PTR(phi); } +static void remove_dead_stores(struct instruction_list *stores) +{ + struct instruction *store; + + FOR_EACH_PTR(stores, store) { + struct symbol *var = store->addr->sym; + + if (var->torename) + kill_store(store); + } END_FOR_EACH_PTR(store); +} + void ssa_convert(struct entrypoint *ep) { struct basic_block *bb; @@ -393,6 +450,7 @@ void ssa_convert(struct entrypoint *ep) } END_FOR_EACH_PTR(bb); // try to promote memory accesses to pseudos + stores = NULL; FOR_EACH_PTR(ep->accesses, pseudo) { ssa_convert_one_var(ep, pseudo->sym); } END_FOR_EACH_PTR(pseudo); @@ -401,4 +459,7 @@ void ssa_convert(struct entrypoint *ep) phis_all = phis_used = NULL; ssa_rename_insns(ep); ssa_rename_phis(ep); + + // remove now dead stores + remove_dead_stores(stores); } diff --git a/validation/mem2reg/not-same-memop0.c b/validation/mem2reg/not-same-memop0.c index 7a84ddce4efc..4de981956b74 100644 --- a/validation/mem2reg/not-same-memop0.c +++ b/validation/mem2reg/not-same-memop0.c @@ -16,7 +16,6 @@ static void foo(struct s s) /* * check-name: not-same-memop0 * check-command: test-linearize -Wno-decl -fdump-ir=mem2reg $file - * check-known-to-fail * * check-output-start local: