From patchwork Tue Mar 20 00:52:43 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: 10295825 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 48FE960385 for ; Tue, 20 Mar 2018 00:53:17 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 3B722290BD for ; Tue, 20 Mar 2018 00:53:17 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 3049C29466; Tue, 20 Mar 2018 00:53:17 +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 D72D1290BD for ; Tue, 20 Mar 2018 00:53:16 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S933710AbeCTAxQ (ORCPT ); Mon, 19 Mar 2018 20:53:16 -0400 Received: from mail-wr0-f193.google.com ([209.85.128.193]:46851 "EHLO mail-wr0-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933099AbeCTAxN (ORCPT ); Mon, 19 Mar 2018 20:53:13 -0400 Received: by mail-wr0-f193.google.com with SMTP id s10so7596753wra.13 for ; Mon, 19 Mar 2018 17:53:12 -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=XASHeUx5SSwN5tQA1abpoGNFVITTQfvcbV2UY+16uHA=; b=FdzC4Eg848K3Mt3pHkyUEUwuoLk9mmwY12ED/SyAEVOEWEoAlm9PpbockVb1wm2d6a 9J+G7gJlHViEGgW4qbqfp42bEYHn+SoLhbzWoAmUB+UoTHHDxyobtVugYgyUbnau6MIS gjtXM8w9M1RjGZcP1w9CziwdMEcgMO1kizoj7LKcmXEyp0+RimFvBn/frCT/lGz1S4ms Vw4m7JMy9V3/r0WMgZHyj+JHUP1hFZprIhX9zqih0fw50gwL+2obGuX0f8X1eXba6baR +/pRhZljHH88OXyk1lLHVj2dkoXBe9ho7YzOjGDDBKn8Ws0KyhJ0/r4vywuVcsCQ8PZ0 lMmw== 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=XASHeUx5SSwN5tQA1abpoGNFVITTQfvcbV2UY+16uHA=; b=nghTMgEZy0aCgP3G3/CH4v+peyc6cwUselReCj3v+8YNq2D0oaBOeuvYNH7odfa3Lt M3q9XTpuT4i/dSDlcMxTlyen9GuQrLC815PoPgE7UkSizOuy/yIIXlWLOIipzZyLcgGj 1FJlwoXpWuLD3abhmlUf9XjaNu23SeOe/F6LQbwnOR+VdRrwXBCc7rYfY7n+9Dub7dQf DCVAdcLl2Di3wej9eI5ISTlNL7RkS2KQmbir967sp0kx9aJwM2tnIXqTyV4Im5URieSk WQVHbhwC5ywOs53mCwSCV6+yO3zVqEaf5kz1Jv/eIlLVl5HUAcg7fCq1FQIgidAUIdx1 lGsw== X-Gm-Message-State: AElRT7Gh3kwnUgMymjC3md4PnF5IVP2s6P2Q9Q+Q2w8QQ6g7Z3hsrTFD 0XMXcRlfOGuMtNF2tTKBiYtUPztp7I8= X-Google-Smtp-Source: AG47ELvkl9rjs6CmsJgzPhk1v/cmuVe0f5AuznyGuvfLMwFpUVQ2kRRhy3n9pyUIdbubQft38T726Q== X-Received: by 10.223.179.195 with SMTP id x3mr6100619wrd.94.1521507191932; Mon, 19 Mar 2018 17:53:11 -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.11 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 19 Mar 2018 17:53:11 -0700 (PDT) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH v1 05/18] dom: add support for dominance queries Date: Tue, 20 Mar 2018 01:52:43 +0100 Message-Id: <20180320005256.53284-6-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 The dominance tree is useless as such, what's matter is to be able to make queries, to ask if such BB dominates this other BB. This patch add an API (domtree_dominates()) to do this. Signed-off-by: Luc Van Oostenryck --- flowgraph.c | 24 ++++++++++++++++++++++++ flowgraph.h | 4 ++++ 2 files changed, 28 insertions(+) diff --git a/flowgraph.c b/flowgraph.c index b2d95893c..8fc22dcfd 100644 --- a/flowgraph.c +++ b/flowgraph.c @@ -193,3 +193,27 @@ void domtree_build(struct entrypoint *ep) if (dbg_domtree) debug_domtree(ep); } + +// dt_dominates - does BB a dominates BB b? +bool domtree_dominates(struct basic_block *a, struct basic_block *b) +{ + if (a == b) // dominance is reflexive + return true; + if (a == b->idom) + return true; + if (b == a->idom) + return false; + + // can't dominate if deeper in the DT + if (a->dom_level >= b->dom_level) + return false; + + // FIXME: can be faster if we have the DFS in-out numbers + + // walk up the dominator tree + for (b = b->idom; b; b = b->idom) { + if (b == a) + return true; + } + return false; +} diff --git a/flowgraph.h b/flowgraph.h index 8e42f865d..7226c55f0 100644 --- a/flowgraph.h +++ b/flowgraph.h @@ -1,9 +1,13 @@ #ifndef FLOWGRAPH_H #define FLOWGRAPH_H +#include + struct entrypoint; +struct basic_block; int cfg_postorder(struct entrypoint *ep); void domtree_build(struct entrypoint *ep); +bool domtree_dominates(struct basic_block *a, struct basic_block *b); #endif