From patchwork Tue Jul 19 22:11:09 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1658253 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=NjIGwqnx; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4LnY2d279zz9sFr for ; Wed, 20 Jul 2022 08:11:37 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id A1D4B3857C43 for ; Tue, 19 Jul 2022 22:11:34 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A1D4B3857C43 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1658268694; bh=51agEYzbxZYbGeL3IdMPNbavVBYzU6SSTHMZaLwTDVY=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=NjIGwqnxbLM506KFi2jNH/KVqBPSsI4fEXnAzjbi7ZaaFbloHvpCmwvNIPmKrSxkY fm27x49bbUnQmVdLEbXlnlO69uEGdN9o9mKbmZyt6+7gjCcMWeXEPMXkFChwwTDaBS 9H6AIUEuWKHU+Fu32UvVQF7NtvRgZQZhp/M3m9kk= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 2A1173857BB3 for ; Tue, 19 Jul 2022 22:11:14 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 2A1173857BB3 Received: from mail-qk1-f198.google.com (mail-qk1-f198.google.com [209.85.222.198]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-118-dLSfcFutPbWsqrc7v9XOIg-1; Tue, 19 Jul 2022 18:11:12 -0400 X-MC-Unique: dLSfcFutPbWsqrc7v9XOIg-1 Received: by mail-qk1-f198.google.com with SMTP id t203-20020a3746d4000000b006af1d3e8068so12780925qka.0 for ; Tue, 19 Jul 2022 15:11:12 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent :content-language:to:cc:from:subject; bh=pOSvA6tDxePygAQqmhURZ00S8a0MJgBs/5LU25rhuDY=; b=zyHRcfuf0DdBT5oNbJoTEL9dMbT2zbgCe7bCQRTeFwJAGOxCZwK32mDqKmjp8QSQw3 JNrjaBrhBadC6GXk0UAsoicFqLC39o7EcGgxd2AUojonhgjRJqZ18mvtu9KiMmdXsS4n f3SKpY3g+9zuCwRZF1WHbec22G0bk9GL3u9e2Xp0cAtMXEDtLRXL2P4mv9FrebsSrFxJ jJauSxgagszKXbpDVDTpnW9q6CGWX59c48BI5JlKxwy4SrTY7pgnhYdL0ofvIpdHiQyr qdpq1EBpcYNux/VH39yuSzGt77bz/qEMuNzn/msFet2uKABnPD9S4b/siAg1t1CRe5L0 JCMg== X-Gm-Message-State: AJIora9QFmpEYxR1pVUbR9vgO40vpdtQRCw81zEQdSCUWDiHsP33OSzZ qv64r1ZzCPZp3ODJEYI5KphKghlYBiqO1G/78VHKztMq3uzUsInFHsV0GSqbTTFg/dKqVLmly52 OgVE/inNlC6G82bo1Aq/HWE/t94PRUw3H7cEp7kp23lHGDE/D8m89Kf9ExGKQQ7AhqgAzYQ== X-Received: by 2002:a05:622a:5d4:b0:31e:e357:f843 with SMTP id d20-20020a05622a05d400b0031ee357f843mr14213009qtb.588.1658268671828; Tue, 19 Jul 2022 15:11:11 -0700 (PDT) X-Google-Smtp-Source: AGRyM1vvej4wIO0xcH3g/0u6Lx/wwYzyon4CpZW9xBpQkuyviUzXglrZ1wxZ+2kHG6GPRcFl37ojww== X-Received: by 2002:a05:622a:5d4:b0:31e:e357:f843 with SMTP id d20-20020a05622a05d400b0031ee357f843mr14212986qtb.588.1658268671535; Tue, 19 Jul 2022 15:11:11 -0700 (PDT) Received: from ?IPV6:2607:fea8:a263:f600::8ef5? ([2607:fea8:a263:f600::8ef5]) by smtp.gmail.com with ESMTPSA id v11-20020a05620a0f0b00b006b28349678dsm15653859qkl.80.2022.07.19.15.11.10 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 19 Jul 2022 15:11:10 -0700 (PDT) Message-ID: <61469f5a-5706-c7b4-50ea-a83b6cec27e8@redhat.com> Date: Tue, 19 Jul 2022 18:11:09 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.11.0 To: gcc-patches Subject: [COMMITTED] [PATCH 2/2] Resolve complicated join nodes in range_from_dom. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_NONE, TXREP 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: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" The main time a dominator search in the cache fails to produce an accurate range is when we have a "complicated" join node. ie bb4:    if (a > 200) goto bb5 ; else goto bb9 bb5    if (b > 400) goto bb6 ; else goto bb7 bb6    foo (b) bb7    onward()    goto bb200; bb9:   if (b > 200) goto bb6; else goto bb200 in this case bb6  is a complicated join node by ranger standards. It has 2 incoming edges which carry range information for b:    9->6 has [201, +INF] and    5->6 has[401, +INF] The immediate dominator of bb6 is bb4.  When asking bb6 for a range from its dominator, there is no sign of any outgoing ranges for b, and range_from_dom would simply return VARYING. This patch tweaks range_from_dom()  so that we calculate the range for any block in which either   1) The dominator has an outgoing range    (this was the old behaviour only)   2) The current block sees an outgoing range on an incoming edge. The addition of 2) allows us to capture the above case with minimal cost which gets use very very close to the results from the old style full cache value propagation. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  pushed. Andrew From dbb093f4f15ea66f2ce5cd2dc1903a6894563356 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Mon, 18 Jul 2022 15:04:23 -0400 Subject: [PATCH 2/2] Resolve complicated join nodes in range_from_dom. Join nodes which carry outgoing ranges on incoming edges are uncommon, but can still be resolved by setting the dominator range, and then calculating incoming edges. Avoid doing so if one of the incoing edges is not dominated by the same dominator. * gimple-range-cache.cc (ranger_cache::range_from_dom): Check for incoming ranges on join nodes and add to worklist. --- gcc/gimple-range-cache.cc | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 20dd5ead3bc..f3292fccaee 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -1384,6 +1384,32 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb, // This block has an outgoing range. if (m_gori.has_edge_range_p (name, bb)) m_workback.quick_push (prev_bb); + else + { + // Normally join blocks don't carry any new range information on + // incoming edges. If the first incoming edge to this block does + // generate a range, calculate the ranges if all incoming edges + // are also dominated by the dominator. (Avoids backedges which + // will break the rule of moving only upward in the domniator tree). + // If the first pred does not generate a range, then we will be + // using the dominator range anyway, so thats all the check needed. + if (EDGE_COUNT (prev_bb->preds) > 1 + && m_gori.has_edge_range_p (name, EDGE_PRED (prev_bb, 0)->src)) + { + edge e; + edge_iterator ei; + bool all_dom = true; + FOR_EACH_EDGE (e, ei, prev_bb->preds) + if (e->src != bb + && !dominated_by_p (CDI_DOMINATORS, e->src, bb)) + { + all_dom = false; + break; + } + if (all_dom) + m_workback.quick_push (prev_bb); + } + } if (def_bb == bb) break; -- 2.36.1