From patchwork Tue Jul 19 22:10:57 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: "Li, Pan2 via Gcc-patches" X-Patchwork-Id: 68 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a98:d5ce:0:b0:178:cc93:bf7d with SMTP id g14csp2717101eik; Tue, 19 Jul 2022 15:11:56 -0700 (PDT) X-Google-Smtp-Source: AGRyM1sSWsSC2zbktiMrwU7O3PHFaUB7epjDUX4ppX66ik5jMyn7qai7wgDBuomWoRBJ7cL6rOCt X-Received: by 2002:a17:906:cc46:b0:72b:83d4:de11 with SMTP id mm6-20020a170906cc4600b0072b83d4de11mr31633765ejb.428.1658268716442; Tue, 19 Jul 2022 15:11:56 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1658268716; cv=none; d=google.com; s=arc-20160816; b=aWIKakuS3F4nqbJwMLIKWypGMkfSAcBPJ2+LaiCQVweY5+NL8egPC1Plyd6mMCzsrD 9cJ8I27nDofKmzZ7NtV+cyNucPa4UQnP/I4s21x1KmlpA3lLGavQR92zX5mDyhORoenY 6VAW2YBvkmvROPnS3HaDsCJWJp1kHstjzuTA7Lue9ZGpA4oKZfMTj0mio6jz7KusLffH ahMFobSpSslusCg+kgA1J6MquhfwaIndECmiViHpPGIGNBS9dEE8DUXKXQZNryCORF87 ++/FiMmr+aoMuG7MdJCJyBisv9og/f3f3KRJb6ZH6Zt2iP3hVOP6lSxnEUAcntz6cjY/ qIrQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:content-language :subject:to:user-agent:mime-version:date:message-id:dmarc-filter :delivered-to:dkim-signature:dkim-filter; bh=gdjz1yA3myowAbPo5vLW2UHbJq9hA91u7fQLroq+3U0=; b=MnFPMkXdlk9KfKypsixjPxTj26rlaJ6OSnMiS3ybqPYkNxsBgKIOV/QFzCl66Zjb95 hTeX+8OFsEqfryuNE8vxqTLv0k1CrZso1O3MJwpSM+pcj4PYQn0nEZbZph+wZo7Ntjnn ElsPHnP99m7jK2xuAKKCpxJHPFm4UBOIra6dkeZd1xS7I1DLzmWXxUyBpkhIkjd0ZmOs ikgNbQNGUYi7J0M7fZsfpueITIrmN3XU3XoOWBFSkPnS5IhaSnUlAKreu8h+yU/8ptz1 LM/6TzmPP1xhqn/PDOFxXePeu9IRQKiHaQ3uA5AgHzMuPfO8NnH1I3SQ0VewOlb9kO2+ ZWPw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=AmT7DGN5; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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 (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id gb34-20020a170907962200b0072b2e339b71si23482537ejc.429.2022.07.19.15.11.56 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jul 2022 15:11:56 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=AmT7DGN5; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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 D534E3857005 for ; Tue, 19 Jul 2022 22:11:45 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org D534E3857005 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1658268705; bh=gdjz1yA3myowAbPo5vLW2UHbJq9hA91u7fQLroq+3U0=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=AmT7DGN5wHftY5R1M2p8DHNgM0xoyiLemqity415V6pQuJ8Ga+Yq2gl/RMh/yeK2v uS7C9iQcDiYnlU24yuI8i6QZeR+ADbZftgeD+TZjgStUF0fzaYzmrKyWH3JGsvC+R9 febb3tPDk4+gFgtei88i1eXJagyo4036wgLQ3CMg= 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 F08C03858C00 for ; Tue, 19 Jul 2022 22:11:01 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org F08C03858C00 Received: from mail-qt1-f199.google.com (mail-qt1-f199.google.com [209.85.160.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-22-ZbK69JjDOoOhOh3nGCLCrA-1; Tue, 19 Jul 2022 18:11:00 -0400 X-MC-Unique: ZbK69JjDOoOhOh3nGCLCrA-1 Received: by mail-qt1-f199.google.com with SMTP id ca5-20020a05622a1f0500b0031ef0a522c4so4484371qtb.5 for ; Tue, 19 Jul 2022 15:11:00 -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=VBMFNn+GQcudgcaBvsqcy+eTKcY7Fvo4gH/n/GoKuQQ=; b=MbtbFOyhFvmmHc3klPRUmEMJ6WjUq4BML8PLg8vSCD1322KZxhEdIrq7+41SVS1gQG zoh+aZx9TtkX81v7OwkDZFEjCcSm+GcPyw8DdJQdLxOgy2K18EkKwYLMXR8VXfLA7lRT MgRPSpUMQbTc/RoLkDW+1pJ9arOoOOnfB+x7/cfuMD13m/33o+5/OGxB6stXJLc0ZhII 45YzVMcWPpwx60MYU99zDXlF/xmMjYUU0qxvRSloTjhIKCPeMddmBCJOQZbWjqt8nweV iY4bTZBkEbrUPCPEjrxleBu/6cbOOUuLewrj0TFC2yDQZbZxIk8vOAMugqnQqP62/ZcH u9Vw== X-Gm-Message-State: AJIora+L2bwc9sSk3SfXR5koCAM+E3NxOaLqVXindiO3l6Nm2AZp7zXM d+3kjAmlRRNPpjmdegBfTQ/mVTC9BhJtAgPnI+GfaKNgVEaeIx77L4rAlXy4o8DZ/4CM4/uoSu0 H6VMdqrXDH7gVUzfyK4nZuiw5brjlZyxUmvBT0X6OQWX9rdq82wXe0gs/B6vPF7DRcm+TRA== X-Received: by 2002:a05:620a:25c6:b0:6ae:2408:6e05 with SMTP id y6-20020a05620a25c600b006ae24086e05mr21773689qko.240.1658268659356; Tue, 19 Jul 2022 15:10:59 -0700 (PDT) X-Received: by 2002:a05:620a:25c6:b0:6ae:2408:6e05 with SMTP id y6-20020a05620a25c600b006ae24086e05mr21773673qko.240.1658268659091; Tue, 19 Jul 2022 15:10:59 -0700 (PDT) Received: from ?IPV6:2607:fea8:a263:f600::8ef5? ([2607:fea8:a263:f600::8ef5]) by smtp.gmail.com with ESMTPSA id s22-20020ac85296000000b0031eed13a58asm4909046qtn.92.2022.07.19.15.10.57 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 19 Jul 2022 15:10:58 -0700 (PDT) Message-ID: Date: Tue, 19 Jul 2022 18:10:57 -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 1/2] Remove recursion from 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: "Li, Pan2 via Gcc-patches" Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1738820777595979462?= X-GMAIL-MSGID: =?utf-8?q?1738820777595979462?= This patch removes the recursion from range_from_dom. It was walking the dominators looking for a range, and if a block was encountered with outgoing ranges, a recursive call was made to resolve the incoming dominator range and then calculate incoming edges. This meant the edges could all be resolved by simply calculating to the nearest dominator. This allowed range_from_dom to always get a decent answer. Along the way, any "simple" blocks which had only a single incoming edge were pushed onto a stack to be quickly resolved by applying the dominators range instead of doing a full range-on-entry. This patch extends that such that all interesting blocks are pushed onto the list, and after a range is found from a dominator, any such blocks are simply calculated at the end as they are opped off.  ITs just a better genralization of what we were doing and no longer requires a recursive call. It also enables the enhancement from the follow on patch. There should be no functional change, and its just a hair faster.  There will be less pressure on deep call stacks as a result as well. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From b0cc57cd76f511f29cab233654249817312ec2a6 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Fri, 15 Jul 2022 09:35:29 -0400 Subject: [PATCH 1/2] Remove recursion from range_from_dom. Avoid calling range_of_dom recursively by putting all nodes to be calculated on the worklist, and figure out which kind they are when removed from the list. * gimple-range-cache.cc (ranger_cache::resolve_dom): New. (ranger_cache::range_from_dom): Put all nodes to be calculated in the worklist and resolve after the dom walk. * gimple-range-cache.h (resolve_dom): New prototype. --- gcc/gimple-range-cache.cc | 84 ++++++++++++++++++++++----------------- gcc/gimple-range-cache.h | 1 + 2 files changed, 48 insertions(+), 37 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index da7b8055d42..20dd5ead3bc 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -1312,6 +1312,38 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) fprintf (dump_file, " Propagation update done.\n"); } +// Resolve the range of BB if the dominators range is R by calculating incoming +// edges to this block. All lead back to the dominator so should be cheap. +// The range for BB is set and returned in R. + +void +ranger_cache::resolve_dom (vrange &r, tree name, basic_block bb) +{ + basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name)); + basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb); + + // if it doesn't already have a value, store the incoming range. + if (!m_on_entry.bb_range_p (name, dom_bb) && def_bb != dom_bb) + { + // If the range can't be store, don't try to accumulate + // the range in PREV_BB due to excessive recalculations. + if (!m_on_entry.set_bb_range (name, dom_bb, r)) + return; + } + // With the dominator set, we should be able to cheaply query + // each incoming edge now and accumulate the results. + r.set_undefined (); + edge e; + edge_iterator ei; + Value_Range er (TREE_TYPE (name)); + FOR_EACH_EDGE (e, ei, bb->preds) + { + edge_range (er, e, name, RFD_READ_ONLY); + r.union_ (er); + } + // Set the cache in PREV_BB so it is not calculated again. + m_on_entry.set_bb_range (name, bb, r); +} // Get the range of NAME from dominators of BB and return it in R. Search the // dominator tree based on MODE. @@ -1341,7 +1373,7 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb, // Default value is global range. get_global_range (r, name); - // Search until a value is found, pushing outgoing edges encountered. + // Search until a value is found, pushing blocks which may need calculating. for (bb = get_immediate_dominator (CDI_DOMINATORS, start_bb); bb; prev_bb = bb, bb = get_immediate_dominator (CDI_DOMINATORS, bb)) @@ -1351,40 +1383,7 @@ 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)) - { - // Only outgoing ranges to single_pred blocks are dominated by - // outgoing edge ranges, so those can be simply adjusted on the fly. - edge e = find_edge (bb, prev_bb); - if (e && single_pred_p (prev_bb)) - m_workback.quick_push (prev_bb); - else if (mode == RFD_FILL) - { - // Multiple incoming edges, so recursively satisfy this block - // if it doesn't already have a value, and store the range. - if (!m_on_entry.bb_range_p (name, bb) && def_bb != bb) - { - // If the dominator has not been set, look it up. - range_from_dom (r, name, bb, RFD_FILL); - // If the range can't be store, don't try to accumulate - // the range in PREV_BB due to excessive recalculations. - if (!m_on_entry.set_bb_range (name, bb, r)) - break; - } - // With the dominator set, we should be able to cheaply query - // each incoming edge now and accumulate the results. - r.set_undefined (); - edge_iterator ei; - Value_Range er (TREE_TYPE (name)); - FOR_EACH_EDGE (e, ei, prev_bb->preds) - { - edge_range (er, e, name, RFD_READ_ONLY); - r.union_ (er); - } - // Set the cache in PREV_BB so it is not calculated again. - m_on_entry.set_bb_range (name, prev_bb, r); - break; - } - } + m_workback.quick_push (prev_bb); if (def_bb == bb) break; @@ -1403,14 +1402,25 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb, fprintf (dump_file, " at function top\n"); } - // Now process any outgoing edges that we seen along the way. + // Now process any blocks wit incoming edges that nay have adjustemnts. while (m_workback.length () > start_limit) { int_range_max er; prev_bb = m_workback.pop (); + if (!single_pred_p (prev_bb)) + { + // Non single pred means we need to cache a vsalue in the dominator + // so we can cheaply calculate incoming edges to this block, and + // then store the resulting value. If processing mode is not + // RFD_FILL, then the cache cant be stored to, so don't try. + // Otherwise this becomes a quadratic timed calculation. + if (mode == RFD_FILL) + resolve_dom (r, name, prev_bb); + continue; + } + edge e = single_pred_edge (prev_bb); bb = e->src; - if (m_gori.outgoing_edge_range_p (er, e, name, *this)) { r.intersect (er); diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 0341192c9cb..45053b5873a 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -107,6 +107,7 @@ private: RFD_FILL // Scan DOM tree, updating important nodes. }; bool range_from_dom (vrange &r, tree name, basic_block bb, enum rfd_mode); + void resolve_dom (vrange &r, tree name, basic_block bb); void range_of_def (vrange &r, tree name, basic_block bb = NULL); void entry_range (vrange &r, tree expr, basic_block bb, enum rfd_mode); void exit_range (vrange &r, tree expr, basic_block bb, enum rfd_mode); -- 2.36.1 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: "Li, Pan2 via Gcc-patches" X-Patchwork-Id: 69 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a98:d5ce:0:b0:178:cc93:bf7d with SMTP id g14csp2717225eik; Tue, 19 Jul 2022 15:12:12 -0700 (PDT) X-Google-Smtp-Source: AGRyM1tMNKt9E2tFAemgyy5Jp8h40N4bae8uYnHx8/m7MFWDs4quahmFiPVTmT0H8+uZqlKlYAde X-Received: by 2002:a17:906:5055:b0:6ff:1dfb:1e2c with SMTP id e21-20020a170906505500b006ff1dfb1e2cmr32791879ejk.200.1658268732309; Tue, 19 Jul 2022 15:12:12 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1658268732; cv=none; d=google.com; s=arc-20160816; b=yu+1mpqSmu/PCY3kAYyR7ZD4ub2OnmTequx4mUWyjOZH2gZYBmNsJartqXSyeFWjY4 hppv2Az762GaISDaTgnT3rzKjKfkqG56ZNCPQBQmkDlntD59XXu1m/rxmi2KH7A+uLrX 5nKJMC16dOXGHikY6bCBYQrXGCbotA7QMUbaMusci/xxl730wM4dt4R5DohLBPfK9jXs Ft2SbApR3l1/nKXBB2xSGbkgsbC7mt2Ut02GW50Z1SvhDtW8bLZs//4SOJURO28M2B1m m3dbbr3riBpJ7Ng4q12FR6HT3aviZjPHeVsqFrsfFYpB43BSgHB+doo4ZJlbtySjKYdI QfOA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:content-language :subject:to:user-agent:mime-version:date:message-id:dmarc-filter :delivered-to:dkim-signature:dkim-filter; bh=51agEYzbxZYbGeL3IdMPNbavVBYzU6SSTHMZaLwTDVY=; b=l1HksOVNzwylLRzuTMObD8k+5tzrZSwlYNEWrxN3Aejl8tpOKorYd2O632a0h8R6GN K9iDWlPmaubjxTry0RfcbJL5Ox1GvSxxKvug3ofp0gCf7yS/vl44rv2VMDmr1aR9vG8k nIUJJmHAZY2QyqoUTTXK7D6E/p49TORUSGA1mhAKSTbvS6ZTd2GoE9pERKXmdqor8pZY S064+jJ0UznT8QMaSLnltW4cJNpZn+TdVVA7BNTUae4pjyqHET4CQjEqPhIaQG4IHOvW tWxiTRyjTEG1FGb3IichU7/Nf3UbXBPNWxUjYUY8hJQXG4k9Lbl02DhmistLIFvEdc4e XL6w== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=pqOUwtrh; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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 (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id f12-20020a056402150c00b0043a737ac218si4440169edw.539.2022.07.19.15.12.12 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jul 2022 15:12:12 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=pqOUwtrh; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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 B7E833857BB5 for ; Tue, 19 Jul 2022 22:11:58 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B7E833857BB5 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1658268718; bh=51agEYzbxZYbGeL3IdMPNbavVBYzU6SSTHMZaLwTDVY=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=pqOUwtrhmWFRU2sD8rQpVUUjny7vkb5/3g31mWYW+IPs58+EmLXAJDMpmLiO90K7E SAZcno8kLsKFXlEY7/Zg7wZSntwMXFc5QOyoPGv+COByFl/ZET/IFV43AZU4aAqlF2 Ohu1ditqoUQaCtzMmjlc6cl2XA7iilpAK4MbLhbI= 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-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: "Li, Pan2 via Gcc-patches" Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-LABELS: =?utf-8?b?IlxcSW1wb3J0YW50Ig==?= X-GMAIL-THRID: =?utf-8?q?1738820793888441019?= X-GMAIL-MSGID: =?utf-8?q?1738820793888441019?= 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