From patchwork Tue Aug 23 12:16:32 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 676 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:ecc5:0:0:0:0:0 with SMTP id s5csp922089wro; Tue, 23 Aug 2022 05:17:39 -0700 (PDT) X-Google-Smtp-Source: AA6agR5VrQUkRW4FulPCpqUEYb8BabM9NBKySmx5Vfc05BzJuz7kYjwCg5YtrPX8rSaSHTDi9nVz X-Received: by 2002:a17:906:7f90:b0:73d:7d37:a893 with SMTP id f16-20020a1709067f9000b0073d7d37a893mr7130317ejr.741.1661257058849; Tue, 23 Aug 2022 05:17:38 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1661257058; cv=none; d=google.com; s=arc-20160816; b=cM8MOw9y9MXhU6oEzL4RuCh6fAGWVLdo2Rt/lOU6suHUX+YDFyuM7aXw2tOdHMY6mU wAeftNu0oi7NMNb/toNT8btxcp+ROIdoyIhd5ni4x7NK5NZ44PfSb6Cz2bVWQUPq8NvD T494IopOPfV4B7gNiYzuOtoar+tgyhmz4zXLju9imkMZXxO1AKyBkyVBBnc5uGF+xTMN WSkEu97rXko3vNsOB14UOXItrQ6pJEEwdYH7JvcjdvxJ+JwNjssAkRRJt1z2lPiJAqgo I5Z02N7Dz2WZ9B3LjCksfDZ4i90weJQ9NBtMkC+U01o9EdvzGFQmuuV6AO+Emw/v68BR GoAQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=message-id:sender:errors-to:reply-to:from:list-subscribe:list-help :list-post:list-archive:list-unsubscribe:list-id:precedence :mime-version:user-agent:subject:to:date:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=ufo59pnH/FtNsacsx7QCZ4unffk1QENZ4YyltvWhsWE=; b=aaVjS+T6zOsUAbIF98EJFsAfmPWNTfvdeoPtRtQ+J+r8GfGvujsvfyB9+ISOncfiqA KYAS3rqJSQafxA44ZZktUHV4phgDrMxuLPD4KauFEDNqgQurM8QIo9FI58IDTiCSANja Fch2XgmYvL4fomLZRn6hv1wQC2N+iyPyan9HfV43N+2ZzErEui8EYHkykmwrd7GrNk+D japRzXSCmFHmdqdt6cHVU+jq4VYN6M6NmP28ws39Zz7OvYBXW4zdfcHiQnm36UqKe/tr 6XHpqwYfPIXOMvcqBzF+G9F6styTDgUuSDE11nVeYFeYrfQg3LBoEu9nlICbZeMd39Cb dBdg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=dBwJuHi7; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id dz14-20020a0564021d4e00b00445eb9dfb3dsi2338398edb.353.2022.08.23.05.17.38 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 23 Aug 2022 05:17:38 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=dBwJuHi7; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B8B203858012 for ; Tue, 23 Aug 2022 12:17:37 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B8B203858012 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661257057; bh=ufo59pnH/FtNsacsx7QCZ4unffk1QENZ4YyltvWhsWE=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=dBwJuHi7CswAgdkfWqh55pqpU9EME8euD8v7tJba6lYj93q+TZI8duX1FuQDIqsIh IOe6BVJcxI3Hq4EPQ2vhIUoWGbvP5R/7mqOCzLl61iiqrxmhItMjQI8zFXctxeJ+Uz I01SqkSv7zlhnnO1lfhlVp0PkoanaJvCxzdCOJd0= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [IPv6:2001:67c:2178:6::1d]) by sourceware.org (Postfix) with ESMTPS id 5FCE23858290 for ; Tue, 23 Aug 2022 12:16:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 5FCE23858290 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id E3F3E1F86C; Tue, 23 Aug 2022 12:16:32 +0000 (UTC) Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id D89B42C141; Tue, 23 Aug 2022 12:16:32 +0000 (UTC) Date: Tue, 23 Aug 2022 12:16:32 +0000 (UTC) To: gcc-patches@gcc.gnu.org Subject: [PATCH] Speedup path discovery in predicate::use_cannot_happen User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, MISSING_MID, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" Message-Id: <20220823121737.B8B203858012@sourceware.org> X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1741954281861944733?= X-GMAIL-MSGID: =?utf-8?q?1741954281861944733?= The following reverts a hunk from r8-5789-g11ef0b22d68cd1 that made compute_control_dep_chain start from function entry rather than the immediate dominator of the source block of the edge with the undefined value on the PHI node. Reverting at that point does not reveal any testsuite FAIL, in particular the added testcase still passes. The following adjusts this to the other function that computes predicates that hold on the PHI incoming edges with undefined values, predicate::init_from_phi_def, which starts at the immediate dominator of the PHI. That's much less likely to run into the CFG walking limit. Bootstrapped and tested on x86_64-unknown-linux-gnu. Aldy - you did this change, do you remember anything here? In fact the whole thing that's now called predicate::use_cannot_happen seems to be redundant - the two testcases attributed to its history do not fail when that's disabled, nor did they fail when it was introduced. In principle whats now called predicate::superset_of should cover this (but different implementation limits might apply). OK? * gimple-predicate-analysis.cc (predicate::use_cannot_happen): Start the compute_control_dep_chain walk from the immediate dominator of the PHI. --- gcc/gimple-predicate-analysis.cc | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc index a4291657d0b..ea81daacd4f 100644 --- a/gcc/gimple-predicate-analysis.cc +++ b/gcc/gimple-predicate-analysis.cc @@ -1293,6 +1293,12 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds) use_guard = &phi_use_guard_intersection; } + basic_block phi_bb = gimple_bb (phi); + /* Find the closest dominating bb to be the control dependence root. */ + basic_block cd_root = get_immediate_dominator (CDI_DOMINATORS, phi_bb); + if (!cd_root) + return false; + /* Look for the control dependencies of all the interesting operands and build guard predicates describing them. */ unsigned n = gimple_phi_num_args (phi); @@ -1308,7 +1314,7 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds) unsigned num_calls = 0; /* Build the control dependency chain for the PHI argument... */ - if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun), + if (!compute_control_dep_chain (cd_root, e->src, dep_chains, &num_chains, cur_chain, &num_calls)) {