From patchwork Wed Jul 25 20:44:37 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 10544677 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id CF9E614E2 for ; Wed, 25 Jul 2018 20:46:50 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id BF6972A9E7 for ; Wed, 25 Jul 2018 20:46:50 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id B31982A9EC; Wed, 25 Jul 2018 20:46:50 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.8 required=2.0 tests=BAYES_00,DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 4DABF2A9E7 for ; Wed, 25 Jul 2018 20:46:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1731292AbeGYWAM (ORCPT ); Wed, 25 Jul 2018 18:00:12 -0400 Received: from mail-ed1-f65.google.com ([209.85.208.65]:43477 "EHLO mail-ed1-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1731168AbeGYWAM (ORCPT ); Wed, 25 Jul 2018 18:00:12 -0400 Received: by mail-ed1-f65.google.com with SMTP id b20-v6so8323563edt.10 for ; Wed, 25 Jul 2018 13:46:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=raW2QEVs+ECmzA6VUsuF9lJjxdA3ruOqU6syCUdn1wg=; b=a0S/WnwPXL38KbSgR/I71ux6t7zEQ6ZZkMlEjkRUnM+Ie2RjT6IwdjvxA1p77TJBKi dKbcVgc14xsO8k9ynRo3l7fhRpIeqbtBHNS/1IFH0PDjThIqlPKmIlOcO6xHG6hylbfJ VVDiBLdj1RYFjlgTkzBDxJxwg4fGSteOqrb6xmS6neguN+uozFPURUPoUWI7+3MYCCoE u4nUGpojB9XXMcCal3tOGKS6TTJM6CXqdf3OgJdMGqpZt7o2ryrxtVFHlD8hcV+sLytC 0Rrva+qtlwqU9z+wdN0wB9mZzcPvuM0zx58HaRq0KsJxYyXXOA14FwIN2qemrC9NYJIs H1Dg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=raW2QEVs+ECmzA6VUsuF9lJjxdA3ruOqU6syCUdn1wg=; b=nIvQuqwpiQxNW0+W48t10Oh7vhwwPVgfCGZ5qlre71QqMn4Itj8SeE8Gie9uo4x8vM P6kseCC36EzEYfIPHSxD4B1sZcSGU1ZkBMaOlItnpcxG63QhfJ3qaZl6un/TVJwCzkXE 75Sr6L4U8pBsHmN3nEJA90XztCXp+0Pvowp1BTInCjEqBXjclcK19+cowRdJajieyHE9 JAGgFWVRLVBsvILIMlCnbUS9rgjDUqsInAvHE7qeKT06ljKklmNUzh0oZjs2D68OPQg7 GR+zm9CdbOy715zymFl8iX5dxndUKRHZoZPNt3+Fn++WM5ekpd/2xoM+SZTaio8fJEdr Yt2A== X-Gm-Message-State: AOUpUlE/aM10WAumSYPnOqEfofz5A9boLn7t2sOo71YhvT/IF2R5nGep 7uzDtKs3SX3SdAhu1Tk9hCrh12Af X-Google-Smtp-Source: AAOMgpc9JvKSs7FnQGM9cktyBjlbrDCOVIRv4XaUuaAzic5B38mPg4OOTAzwQ+9GrA79A5rD6eDkpA== X-Received: by 2002:a50:a1c6:: with SMTP id 64-v6mr23444619edk.309.1532551607615; Wed, 25 Jul 2018 13:46:47 -0700 (PDT) Received: from localhost.localdomain ([2a02:a03f:40d9:b300:a08b:7c37:c755:ffe3]) by smtp.gmail.com with ESMTPSA id n64-v6sm11195114edc.49.2018.07.25.13.46.46 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 25 Jul 2018 13:46:47 -0700 (PDT) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Ramsay Jones , Luc Van Oostenryck Subject: [PATCH v2 1/5] add copy_ptr_list() Date: Wed, 25 Jul 2018 22:44:37 +0200 Message-Id: <20180725204441.91527-2-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.18.0 In-Reply-To: <20180725204441.91527-1-luc.vanoostenryck@gmail.com> References: <20180725204441.91527-1-luc.vanoostenryck@gmail.com> Sender: linux-sparse-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP When an instruction can be replaced by a pseudo, the user list of this pseudo and the instruction's target must be merged. Currently this is done by concat_ptr_list() which copy the elements of one list into the other using add_ptr_list(). This incurs quite a bit overhead. Add a new more efficient ptrlist function: copy_ptr_list() which copy the element by block by looping over both list in parallel. This gives a speedup up to 26% on some pathological workloads. Signed-off-by: Luc Van Oostenryck --- flow.c | 2 +- ptrlist.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++ ptrlist.h | 1 + 3 files changed, 51 insertions(+), 1 deletion(-) diff --git a/flow.c b/flow.c index f928c2684..9483938fb 100644 --- a/flow.c +++ b/flow.c @@ -278,7 +278,7 @@ int simplify_flow(struct entrypoint *ep) static inline void concat_user_list(struct pseudo_user_list *src, struct pseudo_user_list **dst) { - concat_ptr_list((struct ptr_list *)src, (struct ptr_list **)dst); + copy_ptr_list((struct ptr_list **)dst, (struct ptr_list *)src); } void convert_instruction_target(struct instruction *insn, pseudo_t src) diff --git a/ptrlist.c b/ptrlist.c index c7ebf5a3f..684aff8c5 100644 --- a/ptrlist.c +++ b/ptrlist.c @@ -340,6 +340,55 @@ void concat_ptr_list(struct ptr_list *a, struct ptr_list **b) } END_FOR_EACH_PTR(entry); } +/// +// copy the elements of a list at the end of another list. +// @listp: a pointer to the destination list. +// @src: the head of the source list. +void copy_ptr_list(struct ptr_list **listp, struct ptr_list *src) +{ + struct ptr_list *head, *tail; + struct ptr_list *cur = src; + int idx; + + if (!src) + return; + head = *listp; + if (!head) { + *listp = src; + return; + } + + tail = head->prev; + idx = tail->nr; + do { + struct ptr_list *next; + int nr = cur->nr; + int i; + for (i = 0; i < nr;) { + void *ptr = cur->list[i++]; + if (!ptr) + continue; + if (idx >= LIST_NODE_NR) { + struct ptr_list *prev = tail; + tail = __alloc_ptrlist(0); + prev->next = tail; + tail->prev = prev; + prev->nr = idx; + idx = 0; + } + tail->list[idx++] = ptr; + } + + next = cur->next; + __free_ptrlist(cur); + cur = next; + } while (cur != src); + + tail->nr = idx; + head->prev = tail; + tail->next = head; +} + /// // free a ptrlist // @listp: a pointer to the list diff --git a/ptrlist.h b/ptrlist.h index e97cdda31..46a9baee2 100644 --- a/ptrlist.h +++ b/ptrlist.h @@ -35,6 +35,7 @@ int replace_ptr_list_entry(struct ptr_list **, void *old, void *new, int); extern void sort_list(struct ptr_list **, int (*)(const void *, const void *)); extern void concat_ptr_list(struct ptr_list *a, struct ptr_list **b); +extern void copy_ptr_list(struct ptr_list **h, struct ptr_list *t); extern int ptr_list_size(struct ptr_list *); extern int linearize_ptr_list(struct ptr_list *, void **, int); extern void *first_ptr_list(struct ptr_list *); From patchwork Wed Jul 25 20:44:38 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 10544679 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id EB812139A for ; Wed, 25 Jul 2018 20:46:52 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id DAA022A9E7 for ; Wed, 25 Jul 2018 20:46:52 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id CF9422A9EC; Wed, 25 Jul 2018 20:46:52 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.8 required=2.0 tests=BAYES_00,DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 646622A9E7 for ; Wed, 25 Jul 2018 20:46:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1731497AbeGYWAN (ORCPT ); Wed, 25 Jul 2018 18:00:13 -0400 Received: from mail-ed1-f68.google.com ([209.85.208.68]:35288 "EHLO mail-ed1-f68.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730624AbeGYWAN (ORCPT ); Wed, 25 Jul 2018 18:00:13 -0400 Received: by mail-ed1-f68.google.com with SMTP id e6-v6so8323833edr.2 for ; Wed, 25 Jul 2018 13:46:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=ISLo6fXAUXD+7096aDWs9LB5gYudaicKxOoje4N/wBY=; b=uoYYtz0YngOy+Y2REa/0M6Jc+nvkzWeHfRGhfoxVRrtCuYtCXg8V0vlWNtIIBdzhl+ qkPuRKGhWbQAmcwGtEF5tWfV5dRpxg2U36mATWXK8FZyLKhwq1ZDa/ayf5H1+Ew48Vmt 4V74e1gb6pT28OexlZPWCUth3lacBQCNanQ6xjqlIcv8x1VmFi/O2HmNq8gJYWtZ/eUL D0RKJbIWyr3WXTpMY2B4Figg++QsxaAloWMCG4Q7t9l3Urh38LrC5K+hrO98mLy/iNqY ZGGuKpd2I8xWUKE3b2eJGW3rpvn6dMZjAQE2qcTzDLrt0kmL+v7h/7QD5GLamEo3qt2l 5i8g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=ISLo6fXAUXD+7096aDWs9LB5gYudaicKxOoje4N/wBY=; b=QGUGOyeuFqNXvFfnyQIx8zp5/y0vZHW/+kMbuSwOvHu6QjSGp56iqTGMdH0vZpRGDi EmugnweZSkPpEOf3EL2C2TeY9YKUSmNWRmLyrpCqho1EZm8QyAinN2jx8SaNx+aR9Siy A/nuKz6xIbbf0mo+ZqICTaNj8f3Ms98yyXMdiEC2xaODQYVzhzQrolR5xuNHjWHmUz2P Jus2itDZNvtZwRgPC3c9vyiC8lOEVpa1geSBfMoKr0vIg1VxZxGoMbQQbPrnPb2vRomK x6Rw6duGakvszRadUWt4Lyj7J7iRVP40+dKaKqSadqNx9ebszeD8YaD1SEotSonUZkgR sf7w== X-Gm-Message-State: AOUpUlEythywB55ZhNQFHr8BATXIeA8soG5QnjPfTm01zBx/bhlGMyB/ uJMlHC0Bb8CiCWQpqzFJSqw9IhHL X-Google-Smtp-Source: AAOMgpeNTPTv2I++FQnrqxZL9npuVGIE8Z/BxGxOGp1edlOw3VeUeqTepG9FFNYXmpGzVYDZNk8haA== X-Received: by 2002:aa7:da9a:: with SMTP id q26-v6mr24233300eds.115.1532551608537; Wed, 25 Jul 2018 13:46:48 -0700 (PDT) Received: from localhost.localdomain ([2a02:a03f:40d9:b300:a08b:7c37:c755:ffe3]) by smtp.gmail.com with ESMTPSA id n64-v6sm11195114edc.49.2018.07.25.13.46.47 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 25 Jul 2018 13:46:47 -0700 (PDT) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Ramsay Jones , Luc Van Oostenryck Subject: [PATCH v2 2/5] add ptr_list_empty() Date: Wed, 25 Jul 2018 22:44:38 +0200 Message-Id: <20180725204441.91527-3-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.18.0 In-Reply-To: <20180725204441.91527-1-luc.vanoostenryck@gmail.com> References: <20180725204441.91527-1-luc.vanoostenryck@gmail.com> Sender: linux-sparse-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Sometimes we need to know if a list is empty, for example, in order to determine if a pseudo has some users or not. Currently, this is done using ptr_list_size(), which always walks the whole list but the needed answer can be returned as soon as it's known that the list contains at least one element. Add the helper ptr_list_empty() and use it for has_users(). This gives a speedup up to 18% on some pathological workloads. Signed-off-by: Luc Van Oostenryck --- linearize.h | 7 ++++++- ptrlist.c | 19 +++++++++++++++++++ ptrlist.h | 2 ++ simplify.c | 2 +- 4 files changed, 28 insertions(+), 2 deletions(-) diff --git a/linearize.h b/linearize.h index 092e1ac23..de42e718d 100644 --- a/linearize.h +++ b/linearize.h @@ -333,9 +333,14 @@ static inline int pseudo_user_list_size(struct pseudo_user_list *list) return ptr_list_size((struct ptr_list *)list); } +static inline bool pseudo_user_list_empty(struct pseudo_user_list *list) +{ + return ptr_list_empty((struct ptr_list *)list); +} + static inline int has_users(pseudo_t p) { - return pseudo_user_list_size(p->users) != 0; + return !pseudo_user_list_empty(p->users); } static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, pseudo_t *pp) diff --git a/ptrlist.c b/ptrlist.c index 684aff8c5..356785dfc 100644 --- a/ptrlist.c +++ b/ptrlist.c @@ -36,6 +36,25 @@ int ptr_list_size(struct ptr_list *head) return nr; } +/// +// test if a list is empty +// @head: the head of the list +// @return: ``true`` if the list is empty, ``false`` otherwise. +bool ptr_list_empty(const struct ptr_list *head) +{ + const struct ptr_list *list = head; + + if (!head) + return true; + + do { + if (list->nr - list->rm) + return false; + } while ((list = list->next) != head); + + return true; +} + /// // get the first element of a ptrlist // @head: the head of the list diff --git a/ptrlist.h b/ptrlist.h index 46a9baee2..f145bc5f1 100644 --- a/ptrlist.h +++ b/ptrlist.h @@ -2,6 +2,7 @@ #define PTR_LIST_H #include +#include /* * Generic pointer list manipulation code. @@ -37,6 +38,7 @@ extern void sort_list(struct ptr_list **, int (*)(const void *, const void *)); extern void concat_ptr_list(struct ptr_list *a, struct ptr_list **b); extern void copy_ptr_list(struct ptr_list **h, struct ptr_list *t); extern int ptr_list_size(struct ptr_list *); +extern bool ptr_list_empty(const struct ptr_list *head); extern int linearize_ptr_list(struct ptr_list *, void **, int); extern void *first_ptr_list(struct ptr_list *); extern void *last_ptr_list(struct ptr_list *); diff --git a/simplify.c b/simplify.c index 741b1272c..4dc24a505 100644 --- a/simplify.c +++ b/simplify.c @@ -179,7 +179,7 @@ static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_ } END_FOR_EACH_PTR(pu); assert(count <= 0); out: - if (pseudo_user_list_size(*list) == 0) + if (pseudo_user_list_empty(*list)) *list = NULL; return count; } From patchwork Wed Jul 25 20:44:39 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 10544681 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 1AA68A517 for ; Wed, 25 Jul 2018 20:46:53 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 0A0432A9E7 for ; Wed, 25 Jul 2018 20:46:53 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id F2BB42A9EA; Wed, 25 Jul 2018 20:46:52 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.8 required=2.0 tests=BAYES_00,DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 8BF8E2A9E9 for ; Wed, 25 Jul 2018 20:46:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1731504AbeGYWAO (ORCPT ); Wed, 25 Jul 2018 18:00:14 -0400 Received: from mail-ed1-f65.google.com ([209.85.208.65]:34064 "EHLO mail-ed1-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1731294AbeGYWAO (ORCPT ); Wed, 25 Jul 2018 18:00:14 -0400 Received: by mail-ed1-f65.google.com with SMTP id h1-v6so8340127eds.1 for ; Wed, 25 Jul 2018 13:46:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=k26OwE+8PAyVsV39dr7vLJ+7oAZs7qDlAT5YSFi8eEU=; b=a9ccccvb6oDtWfDHkZNdtOrXqvUaYjiG0Vq6STBwNNzi/F2/Kt6opbAkHh7WrAwcGa 5WrpWy4LW4hJf6IRKOJYZCUzqFNm0fOs0J7efgyx4yYZKWXBbmrtUp3TRdrmaMXBDyxa nUN/f+HeuvPKxBLmdw/rPc3jwDAmeG0H5X05OVz4YYkL6h3ph+KcKPKDYwQmGaphr5yC N8e5qLwugU4mwkL6abICbIIJaAC7EdTcxlQwQidDsET/zEIYMFSkB0RG8ZqM81Pf3I4i MJO93LT9Il5buORfoXUfJVkRO/SA7nS2SBOBEmga8/cOWHXJ6yl3JshFyP+IuWVAH/PJ Nbzg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=k26OwE+8PAyVsV39dr7vLJ+7oAZs7qDlAT5YSFi8eEU=; b=VWdpmjKmUSeI57fGP5Jc3gB8aGZYY5GRUBwU5R9SOlU5Nez0Dbv1QehWSuj26kicsm vDkVv3onBR8NOv7P2+8SJsuF4uhvmWOT2O0FviioYl6WvAthoiJSv+eFxDI+vzXdT8RB YIUv4OxlagQ9RKKkWoHNbRRfSxTLY/Yx3T7VerkkjoQ7T47L1CR4a4lZ30NZl4My3tA9 P15aB/UtCPI4XKMVmTwl4sClKyLeIisO0S2AOlHnt6L3NoGm2E+8aYb4yxM57zVgXrnh KZ7YD5/8oa9S3srPvcl+BdCGiTfJSiJC21Hv8ZQC7DojAU9WwtewTNCt7gN4Y3ZWWeLG Ur+A== X-Gm-Message-State: AOUpUlGiGPHEXuVVevS5WZW8t6Iw+AVyWqE3af3d1xg8ASK21RGQ6a/v +WvvsUCKUVUdUUDBf2IbKswyyiF8 X-Google-Smtp-Source: AAOMgpd+7DBb4bAMKReQf5NMwWQ08gyNOOSRiaKI+Y5IciZVNtnJfg4Aei6ZQ9XBOSVP15CrOEAKYA== X-Received: by 2002:a50:c201:: with SMTP id n1-v6mr9479845edf.11.1532551609849; Wed, 25 Jul 2018 13:46:49 -0700 (PDT) Received: from localhost.localdomain ([2a02:a03f:40d9:b300:a08b:7c37:c755:ffe3]) by smtp.gmail.com with ESMTPSA id n64-v6sm11195114edc.49.2018.07.25.13.46.48 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 25 Jul 2018 13:46:49 -0700 (PDT) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Ramsay Jones , Luc Van Oostenryck Subject: [PATCH v2 3/5] add ptr_list_multiple() Date: Wed, 25 Jul 2018 22:44:39 +0200 Message-Id: <20180725204441.91527-4-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.18.0 In-Reply-To: <20180725204441.91527-1-luc.vanoostenryck@gmail.com> References: <20180725204441.91527-1-luc.vanoostenryck@gmail.com> Sender: linux-sparse-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP When doing IR simplification, to know if an instruction can be destructively modified, it's needed to know if the pseudo it defines is used by a single instruction or not. Currently this is done using ptr_list_size() which needs to walk the whole list. This walk is relatively costly when the list is long but knowing if the list contains more than 1 element can often be answered more cheaply since an answer can be returned as soon as it's known that the list contains at least 2 elements. Add the helpers ptr_list_multiple() and multi_users(). Signed-off-by: Luc Van Oostenryck --- linearize.h | 5 +++++ ptrlist.c | 21 +++++++++++++++++++++ ptrlist.h | 1 + simplify.c | 2 +- 4 files changed, 28 insertions(+), 1 deletion(-) diff --git a/linearize.h b/linearize.h index de42e718d..b067b3e84 100644 --- a/linearize.h +++ b/linearize.h @@ -343,6 +343,11 @@ static inline int has_users(pseudo_t p) return !pseudo_user_list_empty(p->users); } +static inline bool multi_users(pseudo_t p) +{ + return ptr_list_multiple((struct ptr_list *)(p->users)); +} + static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, pseudo_t *pp) { struct pseudo_user *user = __alloc_pseudo_user(0); diff --git a/ptrlist.c b/ptrlist.c index 356785dfc..ae00b5134 100644 --- a/ptrlist.c +++ b/ptrlist.c @@ -55,6 +55,27 @@ bool ptr_list_empty(const struct ptr_list *head) return true; } +/// +// test is a list contains more than one element +// @head: the head of the list +// @return: ``true`` if the list has more than 1 element, ``false`` otherwise. +bool ptr_list_multiple(const struct ptr_list *head) +{ + const struct ptr_list *list = head; + int nr = 0; + + if (!head) + return false; + + do { + nr += list->nr - list->rm; + if (nr > 1) + return true; + } while ((list = list->next) != head); + + return false; +} + /// // get the first element of a ptrlist // @head: the head of the list diff --git a/ptrlist.h b/ptrlist.h index f145bc5f1..176bb0712 100644 --- a/ptrlist.h +++ b/ptrlist.h @@ -39,6 +39,7 @@ extern void concat_ptr_list(struct ptr_list *a, struct ptr_list **b); extern void copy_ptr_list(struct ptr_list **h, struct ptr_list *t); extern int ptr_list_size(struct ptr_list *); extern bool ptr_list_empty(const struct ptr_list *head); +extern bool ptr_list_multiple(const struct ptr_list *head); extern int linearize_ptr_list(struct ptr_list *, void **, int); extern void *first_ptr_list(struct ptr_list *); extern void *last_ptr_list(struct ptr_list *); diff --git a/simplify.c b/simplify.c index 4dc24a505..65f29de0a 100644 --- a/simplify.c +++ b/simplify.c @@ -824,7 +824,7 @@ static int simplify_associative_binop(struct instruction *insn) return 0; if (!simple_pseudo(def->src2)) return 0; - if (pseudo_user_list_size(def->target->users) != 1) + if (multi_users(def->target)) return 0; switch_pseudo(def, &def->src1, insn, &insn->src2); return REPEAT_CSE; From patchwork Wed Jul 25 20:44:40 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 10544683 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 27CEE14E2 for ; Wed, 25 Jul 2018 20:46:57 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 15F5D2A9E7 for ; Wed, 25 Jul 2018 20:46:57 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 0870F2A9EC; Wed, 25 Jul 2018 20:46:57 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.8 required=2.0 tests=BAYES_00,DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id EBEE82A9E7 for ; Wed, 25 Jul 2018 20:46:55 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1731294AbeGYWAR (ORCPT ); Wed, 25 Jul 2018 18:00:17 -0400 Received: from mail-ed1-f67.google.com ([209.85.208.67]:40504 "EHLO mail-ed1-f67.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1731168AbeGYWAP (ORCPT ); Wed, 25 Jul 2018 18:00:15 -0400 Received: by mail-ed1-f67.google.com with SMTP id e19-v6so8333557edq.7 for ; Wed, 25 Jul 2018 13:46:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=YGR57S52bPf98Q2RyUNjdE8chpASVD4PUz7g8pkgEe4=; b=YG6DviJEJQ+WIh9Tx43Ec+EYiGEWQK5epL2/ipo38PyNGfO95bpKIA1+AhGXcTunTt NxN81S5tl3oTsmsH+QKLev8lyFUA+ydOYYretagPyOJ2oVTk5EUkgqDrcywZdMG+j0y/ OeNTkV7i4us5+UB2D68umKWVZjZiLFNhsUP1u5/VDPDyny1iK0vozx4sKzlMNk2GeqTo ZmwZ9T+rFL65exsMFj95ba1L4jUfGrM63eaOSphjN+wL8QnR3AX3wgN8ucFxFdP1e1aJ yNaKpOxokD3AKvXgj3OB734NgLnUOfApTma+m2YtmoeuZfdEysSnjk4r6s+p6xaiXon2 bWJA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=YGR57S52bPf98Q2RyUNjdE8chpASVD4PUz7g8pkgEe4=; b=IVll31eycfwbVNghsMwEflKuOYlJr8I+pMaaI31xRyoBYODEttj6e7kxSPFCwINOKd 0R44aZUr4MQIWEV8txe96QpinKN7QM2P6rjDzLj8Ohu8nP1PirVXgo58AQHvR3OJiHL/ ftYvWo7Jo2OO05qfe1goXdg2W/mvi/fuSVdfmXE0MHhLHwf05uSFhbVPWMB9v6Oj3cuU MBXBHpg5do2Ut2McHufzxwtwD4sR02orStM7hYTyEzzQFbVCVzATg56N7++BxqKdmmkj v1TF12vvo5mX46FAcwOQ1h81viWZWesjdNiKlPCa/BjgRepDS21Y9O5gKnT9UjoSCXSu i7rw== X-Gm-Message-State: AOUpUlF1SZq5z/NU/dwr8f26CWcmUK0i84FYTW9oi+DJd0Gl0Ktld4Xp gRbj805nWvjGmHjBCZUTGGuvcs9D X-Google-Smtp-Source: AAOMgpdSf0xfBW6h8Lo6W659M8YIbx5Sl6pCjTgSGBfPg+wo+/tjMqtULJ4UJgL5+Itppb97kQc9BA== X-Received: by 2002:a50:a186:: with SMTP id 6-v6mr25259253edk.12.1532551610758; Wed, 25 Jul 2018 13:46:50 -0700 (PDT) Received: from localhost.localdomain ([2a02:a03f:40d9:b300:a08b:7c37:c755:ffe3]) by smtp.gmail.com with ESMTPSA id n64-v6sm11195114edc.49.2018.07.25.13.46.50 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 25 Jul 2018 13:46:50 -0700 (PDT) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Ramsay Jones , Luc Van Oostenryck Subject: [PATCH v2 4/5] add lookup_ptr_list_entry() Date: Wed, 25 Jul 2018 22:44:40 +0200 Message-Id: <20180725204441.91527-5-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.18.0 In-Reply-To: <20180725204441.91527-1-luc.vanoostenryck@gmail.com> References: <20180725204441.91527-1-luc.vanoostenryck@gmail.com> Sender: linux-sparse-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP For liveness analysis, the ptrlists need to be used as sets. IOW, before adding a new element, it's needed to check if it doesn't already belong to the list. This check is currently done, specifically for pseudos, using the list walking macros FOR_EACH_PTR/END_FOR_EACH_PTR. Add a new generic ptrlist function: lookup_ptr_list_entry() which test if a given pointer already belong to the list. Signed-off-by: Luc Van Oostenryck --- linearize.h | 5 +++++ liveness.c | 9 --------- ptrlist.c | 21 +++++++++++++++++++++ ptrlist.h | 1 + 4 files changed, 27 insertions(+), 9 deletions(-) diff --git a/linearize.h b/linearize.h index b067b3e84..63a51ff35 100644 --- a/linearize.h +++ b/linearize.h @@ -303,6 +303,11 @@ static inline int remove_pseudo(struct pseudo_list **list, pseudo_t pseudo) return delete_ptr_list_entry((struct ptr_list **)list, pseudo, 0) != 0; } +static inline int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo) +{ + return lookup_ptr_list_entry((struct ptr_list *)list, pseudo); +} + static inline int bb_terminated(struct basic_block *bb) { struct instruction *insn; diff --git a/liveness.c b/liveness.c index 4c3339f10..d1968ce4b 100644 --- a/liveness.c +++ b/liveness.c @@ -139,15 +139,6 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction * } } -int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo) -{ - pseudo_t old; - FOR_EACH_PTR(list,old) { - if (old == pseudo) - return 1; - } END_FOR_EACH_PTR(old); - return 0; -} static int liveness_changed; diff --git a/ptrlist.c b/ptrlist.c index ae00b5134..3677a347c 100644 --- a/ptrlist.c +++ b/ptrlist.c @@ -272,6 +272,27 @@ void **__add_ptr_list_tag(struct ptr_list **listp, void *ptr, unsigned long tag) return __add_ptr_list(listp, ptr); } +/// +// test if some entry is already present in a ptrlist +// @list: the head of the list +// @entry: the entry to test +// @return: ``true`` if the entry is already present, ``false`` otherwise. +bool lookup_ptr_list_entry(const struct ptr_list *head, const void *entry) +{ + const struct ptr_list *list = head; + + if (!head) + return false; + do { + int nr = list->nr; + int i; + for (i = 0; i < nr; i++) + if (list->list[i] == entry) + return true; + } while ((list = list->next) != head); + return false; +} + /// // delete an entry from a ptrlist // @list: a pointer to the list diff --git a/ptrlist.h b/ptrlist.h index 176bb0712..2f0234784 100644 --- a/ptrlist.h +++ b/ptrlist.h @@ -33,6 +33,7 @@ void * undo_ptr_list_last(struct ptr_list **head); void * delete_ptr_list_last(struct ptr_list **head); int delete_ptr_list_entry(struct ptr_list **, void *, int); int replace_ptr_list_entry(struct ptr_list **, void *old, void *new, int); +bool lookup_ptr_list_entry(const struct ptr_list *head, const void *entry); extern void sort_list(struct ptr_list **, int (*)(const void *, const void *)); extern void concat_ptr_list(struct ptr_list *a, struct ptr_list **b); From patchwork Wed Jul 25 20:44:41 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 10544685 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 52A46A517 for ; Wed, 25 Jul 2018 20:46:57 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 42A9B2A9E7 for ; Wed, 25 Jul 2018 20:46:57 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 36C0F2A9EA; Wed, 25 Jul 2018 20:46:57 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.8 required=2.0 tests=BAYES_00,DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 193272A9E9 for ; Wed, 25 Jul 2018 20:46:56 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1731357AbeGYWAR (ORCPT ); Wed, 25 Jul 2018 18:00:17 -0400 Received: from mail-ed1-f66.google.com ([209.85.208.66]:38857 "EHLO mail-ed1-f66.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1731294AbeGYWAQ (ORCPT ); Wed, 25 Jul 2018 18:00:16 -0400 Received: by mail-ed1-f66.google.com with SMTP id t2-v6so8331616edr.5 for ; Wed, 25 Jul 2018 13:46:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=2OBh5d3syhIhDDDCdciLh6rc+P63BtO06AaQZFCR734=; b=FrUiCOqk1bZnQ8uPILj3WJRub05XQyJdys+HSxaZMytXWa3ihJk6iQ+jplW3CN0Uko LycO/cVc36ngPI3riPEnF6iXoh12t5hV98fZpGo777pipfod66O5JiMnsVTmLNruL/9H x9D6FgHGwwcxVNgX5uvSYR0jChPtszYGkDhX9nmuDwmn1pMm2Q1aRqlvH3dv3X7pOlqM nBTduB6S/H99ttCDsRoPIhl/PcDE6hPWTYkKA6b0v/ZY0j+bLNCCBei/jbKC6Pu3trDD d/R38XFmHExNSdLr/y9xjVEQlW+ZuUlL6OQzmfE7Qy0vDX0rZytK1SvmNju1gH6bSyEJ Qgdw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=2OBh5d3syhIhDDDCdciLh6rc+P63BtO06AaQZFCR734=; b=rKlujSyRP5MQDfw9DAuvBIHz/xgx/n14pEM1zXLtuNJRDzHqexoU+t3vjDUewEAY0p 2YLdUiQcqwh4jhHNK1pV0WbFt52VU7CnM5XIDPLQUh5gaaK6HfM/ldf0SokkfeFVhHN3 Nqi5AfJZLarMgrd/9Pr3EOAvwXEZxXsAJna+nCJxK8Qxcw20rJEKhQT/lucAvRHedavs PK2PxxNbLM7GnDpVvpwCGDkaHa8lVQiPPS5T+z2NwZl+7/paxAq9qK5OsjRyR+ueWKbe 1ZhMVNv6uu4clFgsXnffujyrUSOtm/2zs0GOI/1Btzp9YqqN8wS7g0NtzFdpES3BSkqr J2lw== X-Gm-Message-State: AOUpUlG0J4e3W+bELCoNIP//VvvMTkq4Kjf3iUXpHPNsk/zJjIluyxOJ jB2lRzlyE/JOSPYPr/cgkn33ohKB X-Google-Smtp-Source: AAOMgpeZK/+RQMlbtvclcR7uR+ysgWNyYow3bufpJJIcgycdtudMbHTvz+mvK0REzMbATGz7nejM0Q== X-Received: by 2002:a50:ae04:: with SMTP id c4-v6mr24812937edd.137.1532551611734; Wed, 25 Jul 2018 13:46:51 -0700 (PDT) Received: from localhost.localdomain ([2a02:a03f:40d9:b300:a08b:7c37:c755:ffe3]) by smtp.gmail.com with ESMTPSA id n64-v6sm11195114edc.49.2018.07.25.13.46.50 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 25 Jul 2018 13:46:51 -0700 (PDT) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Ramsay Jones , Luc Van Oostenryck Subject: [PATCH v2 5/5] no VOID test in convert_instruction_target() Date: Wed, 25 Jul 2018 22:44:41 +0200 Message-Id: <20180725204441.91527-6-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.18.0 In-Reply-To: <20180725204441.91527-1-luc.vanoostenryck@gmail.com> References: <20180725204441.91527-1-luc.vanoostenryck@gmail.com> Sender: linux-sparse-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP In convert_instruction_target(), when replacing the pseudo in the target user list, it's first checked if the old pseudo is not VOID and nothing is done otherwise. But this test is not needed because: 1) the only case where VOID is stored in the user list is when a BB is killed and a killed instruction wouln't be converted 2) this test used to be needed when OP_PHIs were converted during CSE (meaning that the pseudo stored there have been removed from the list) but OP_PHIs are not CSEed anymore. So, removed this unneeded test. This gives a speedup up to 9% in some pathological workloads. Signed-off-by: Luc Van Oostenryck --- flow.c | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-) diff --git a/flow.c b/flow.c index 9483938fb..0fdbdf44d 100644 --- a/flow.c +++ b/flow.c @@ -292,10 +292,7 @@ void convert_instruction_target(struct instruction *insn, pseudo_t src) if (target == src) return; FOR_EACH_PTR(target->users, pu) { - if (*pu->userp != VOID) { - assert(*pu->userp == target); - *pu->userp = src; - } + *pu->userp = src; } END_FOR_EACH_PTR(pu); if (has_use_list(src)) concat_user_list(target->users, &src->users);