From patchwork Tue Mar 20 00:52:47 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: 10295833 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id B966160385 for ; Tue, 20 Mar 2018 00:53:20 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id ABB52290BD for ; Tue, 20 Mar 2018 00:53:20 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id A05D629499; Tue, 20 Mar 2018 00:53:20 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, 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 2C46C290BD for ; Tue, 20 Mar 2018 00:53:20 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S933964AbeCTAxT (ORCPT ); Mon, 19 Mar 2018 20:53:19 -0400 Received: from mail-wr0-f193.google.com ([209.85.128.193]:40909 "EHLO mail-wr0-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933722AbeCTAxQ (ORCPT ); Mon, 19 Mar 2018 20:53:16 -0400 Received: by mail-wr0-f193.google.com with SMTP id z8so10722069wrh.7 for ; Mon, 19 Mar 2018 17:53:16 -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=NIvPbWyKUqskwGyzbRlOLHFtqpsRU1hJ9TmRRf0CiKE=; b=Mb+bjlToTsGGrygol+nftxEmzNjgVuVsc1SY57pl47pHDBjH6EEF+UoFr4y75RLAgh JfLdBDnS/XdaPrTY6xHgsfGoBpGPv77uatQLvhsU7m7y0tfS9amVkumYyNSemXJxNsuL qJBbyU4zeBH97HSJZNei32hpxE16FJ5+Gen9RUXDR3KIWpLP/b1Di5Pw51P8YSFRsHdp v4T2Xz+sOayor+inZSxYfvxytvXKd/xeAy1X0FaZNJViIXzQKWJJ9A4c1gXAI/p0mHPf DLjIC9O88jSar4muJyqJBNSnXN7xqbiYDqPnqa/PvizcKxeXgMb/P4u/3sC0K9iMdkyt erJQ== 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=NIvPbWyKUqskwGyzbRlOLHFtqpsRU1hJ9TmRRf0CiKE=; b=OiZEhWVJZcIYIkBWYPRskIlYjxd7sauBuHpyJKyynrG2WzJd+EeKFwTHINFOumuO4a DWYOpKZbbtOzPszIt5uzh6KfkOLw7bSxz67jVh/bEsch3/nJYoKqrlg0GmKFh8cfR7gt L6VexoqapS8MPDHZuXOhfn4MJXESBWSgnjq+T+ZgLQcyyZr0oNOPEoyV8hUgsLUP0eR/ g4e3ZkWMbUmQJBo+XsZfkc1kY2SsIWHoy31iOpGpEsHGd2n3irw0LXjDRzFyWHMQzX2J O0lZkukMFptFv/KjhxMbEzQDr5xhjc13HFbdJQardDTZalj1MkrZOBcmL5o+t8z7+jog T1pA== X-Gm-Message-State: AElRT7HdNLhnxQchXgor/8eohktpkfCzCiSLKaZysE4yWQyd4Rw046Gt lSawyaMwvjBjb47iTr3jPeracqVBb60= X-Google-Smtp-Source: AG47ELtexvGIeX9Hzpnosnqtvd76Y9MQWA0m3CZtrC5jQndVfVV5ASNpcuziK0KW43FOWAajPW6mlA== X-Received: by 10.223.162.203 with SMTP id t11mr11776117wra.88.1521507195267; Mon, 19 Mar 2018 17:53:15 -0700 (PDT) Received: from localhost.localdomain ([2a02:a03f:40ef:cf00:d148:9bbf:a73b:78ed]) by smtp.gmail.com with ESMTPSA id n47sm591309wrf.41.2018.03.19.17.53.14 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 19 Mar 2018 17:53:14 -0700 (PDT) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH v1 09/18] idf: compute the iterated dominance frontier Date: Tue, 20 Mar 2018 01:52:47 +0100 Message-Id: <20180320005256.53284-10-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.16.2 In-Reply-To: <20180320005256.53284-1-luc.vanoostenryck@gmail.com> References: <20180320005256.53284-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 Conversion of some IR into SSA form requires to place so called phi-nodes where different paths for some value meet. It's important, of course to place these correctly, but it's also important to try to minimize the number of these phi-nodes. Several algorithms exist for the placing of these phi-nodes but it can be shown that, for each variable, it is suffisant to place their phi-nodes on the dominance frontier of the nodes defining this variable and since phi-nodes themselves give a new definition, to have the minimal number of phi-nodes, these phi-nodes must be paced on the iterated dominance frontier (the transitive closure of the dominance frontier of the initial defining nodes). This patch implement what's needed to compute the iterated dominance frontier of a set of nodes. Signed-off-by: Luc Van Oostenryck --- Makefile | 1 + dominate.c | 126 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ dominate.h | 9 +++++ 3 files changed, 136 insertions(+) create mode 100644 dominate.c create mode 100644 dominate.h diff --git a/Makefile b/Makefile index dae6a07b1..0976ee818 100644 --- a/Makefile +++ b/Makefile @@ -37,6 +37,7 @@ LIB_OBJS += char.o LIB_OBJS += compat-$(OS).o LIB_OBJS += cse.o LIB_OBJS += dissect.o +LIB_OBJS += dominate.o LIB_OBJS += evaluate.o LIB_OBJS += expand.o LIB_OBJS += expression.o diff --git a/dominate.c b/dominate.c new file mode 100644 index 000000000..d7808119b --- /dev/null +++ b/dominate.c @@ -0,0 +1,126 @@ +// SPDX-License-Identifier: MIT +// +// dominate.c - compute the (iterated) dominance frontier of (a set of) nodes. +// +// Copyright (C) 2017 - Luc Van Oostenryck +// +// The algorithm used is the one described in: +// "A Linear Time Algorithm for Placing phi-nodes" +// by Vugranam C. Sreedhar and Guang R. Gao +// + +#include "dominate.h" +#include "flowgraph.h" +#include "linearize.h" +#include "flow.h" +#include +#include + + +struct piggy { + unsigned int max; + struct basic_block_list *lists[0]; +}; + +struct piggy *bank_init(unsigned levels) +{ + struct piggy *bank; + bank = calloc(1, sizeof(*bank) + levels * sizeof(bank->lists[0])); + bank->max = levels - 1; + return bank; +} + +static void bank_free(struct piggy *bank, unsigned int levels) +{ + for (; levels-- ;) + free_ptr_list(&bank->lists[levels]); + free(bank); +} + +static void bank_put(struct piggy *bank, struct basic_block *bb) +{ + unsigned int level = bb->dom_level; + assert(level <= bank->max); + add_bb(&bank->lists[level], bb); +} + +static inline struct basic_block *pop_bb(struct basic_block_list **list) +{ + return delete_ptr_list_last((struct ptr_list **)list); +} + +static struct basic_block *bank_get(struct piggy *bank) +{ + int level = bank->max; + do { + struct basic_block *bb = pop_bb(&bank->lists[level]); + if (bb) + return bb; + if (!level) + return NULL; + bank->max = --level; + } while (1); +} + + +#define VISITED 0x1 +#define INPHI 0x2 +#define ALPHA 0x4 +#define FLAGS 0x7 + +static void visit(struct piggy *bank, struct basic_block_list **idf, struct basic_block *x, int curr_level) +{ + struct basic_block *y; + + x->generation |= 1; + FOR_EACH_PTR(x->children, y) { + unsigned flags = y->generation & FLAGS; + if (y->idom == x) // J-edges will be processed later + continue; + if (y->dom_level > curr_level) + continue; + if (flags & INPHI) + continue; + y->generation |= INPHI; + add_bb(idf, y); + if (flags & ALPHA) + continue; + bank_put(bank, y); + } END_FOR_EACH_PTR(y); + + FOR_EACH_PTR(x->doms, y) { + if (y->generation & VISITED) + continue; + visit(bank, idf, y, curr_level); + } END_FOR_EACH_PTR(y); +} + +void idf_compute(struct entrypoint *ep, struct basic_block_list **idf, struct basic_block_list *alpha) +{ + int levels = ep->dom_levels; + struct piggy *bank = bank_init(levels); + struct basic_block *bb; + unsigned long generation = bb_generation; + + generation = bb_generation; + generation += -generation & FLAGS; + bb_generation = generation + (FLAGS + 1); + + // init all the nodes + FOR_EACH_PTR(ep->bbs, bb) { + // FIXME: this should be removed and the tests for + // visited/in_phi/alpha should use a sparse set + bb->generation = generation; + } END_FOR_EACH_PTR(bb); + + FOR_EACH_PTR(alpha, bb) { + bb->generation = generation | ALPHA; + bank_put(bank, bb); + } END_FOR_EACH_PTR(bb); + + while ((bb = bank_get(bank))) { + visit(bank, idf, bb, bb->dom_level); + } + + bank_free(bank, levels); +} diff --git a/dominate.h b/dominate.h new file mode 100644 index 000000000..6ac515d07 --- /dev/null +++ b/dominate.h @@ -0,0 +1,9 @@ +#ifndef DOMINATE_H +#define DOMINATE_H + +struct entrypoint; +struct basic_block_list; + +void idf_compute(struct entrypoint *ep, struct basic_block_list **idf, struct basic_block_list *alpha); + +#endif