From patchwork Fri Dec 3 20:39:35 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1563384 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=bUyFzuqE; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4J5Pq712xfz9s0r for ; Sat, 4 Dec 2021 07:40:51 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id EFD0C385841D for ; Fri, 3 Dec 2021 20:40:48 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org EFD0C385841D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1638564049; bh=Gdmhvu4T2LL4WLnpq3WRjSWYHqnjx6iL/KA0tizko20=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=bUyFzuqEViHqjCoftburJ9yMvPJmNv7/3UkTkdkYFvW7uJGESB0VfX3cvLPDFkUS/ 3sg1MP/GVSI7ZIaNGTa0oWP4h8Lj3sUPuho9uh7So+9AstKZ8b5HkTgvJQ4wuwEMhH kOhMrnRlJNlmbOdzzR+5hv2J/DYHGYeCHkH1qVCI= 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 9AA593858D35 for ; Fri, 3 Dec 2021 20:39:39 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 9AA593858D35 Received: from mail-qk1-f200.google.com (mail-qk1-f200.google.com [209.85.222.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-8-y1XszrfQOQ-977CHeB0Z2Q-1; Fri, 03 Dec 2021 15:39:37 -0500 X-MC-Unique: y1XszrfQOQ-977CHeB0Z2Q-1 Received: by mail-qk1-f200.google.com with SMTP id q5-20020a05620a0d8500b0045edb4779dbso4499921qkl.2 for ; Fri, 03 Dec 2021 12:39:37 -0800 (PST) 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=70fA2Te/LQ6ksyuUI96x+qSvrij/GoBb3z4UXN4tBL0=; b=HJZmZBXZekJ3RJa3mmPnLjUw0iFkOLQalvIzyyN0FutfDeN/BLLAhsBxfehCE2NX4D aIVKf3sy3iKJBScnTiJ29hPkCNaEW7IGK1WL91UMeC3+dOPCDQwrDw7gcuIRWzb2OZG9 VoNa/W/tHmi3IbXEFFCL65inKj9BKneBN1DQWppXUUPJ6C9Z+jZcyZzWRUmrDoD5AQnc dZ3taAFRLWssBi/ynMDPU/5dh/Pp0WG9I5yYliSxUIQ26pJWL5/UCzoCEQnDYL0t64kj zJwTfFMx3Zu1fyvwcsrPeUrdcAj/WGihGEJQUnSC7X34YL1ZDGu2wQk5gQjQrPRbYxBK 59VQ== X-Gm-Message-State: AOAM530/rMGNxb1siUKlHuPuW5xRcMu18hnXBdqTtbubXstRFXm4X+0O WIlZquqZbpaHwLvKElGZi/bkDAGMuEpAueUffgo1Cfu8Dby630zcHvVf1u1Unf7S9c15UEtDth5 UhYAcKw7CaycXnyYuFoLD/lA9XfS5IKqW+4IAxjX15MB2NLJrAMvfzWL3D1t752vxdEDEbg== X-Received: by 2002:a05:622a:307:: with SMTP id q7mr23312583qtw.330.1638563977163; Fri, 03 Dec 2021 12:39:37 -0800 (PST) X-Google-Smtp-Source: ABdhPJy5XWLlEdgcLTv3BgPggXPWsjiFs/kTWNXllFmhVWp5F/Nvh+g6OMTPub2L6ugCzYz3AyW13Q== X-Received: by 2002:a05:622a:307:: with SMTP id q7mr23312563qtw.330.1638563976905; Fri, 03 Dec 2021 12:39:36 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::6d7? ([2607:fea8:a262:5f00::6d7]) by smtp.gmail.com with ESMTPSA id d15sm3182144qtd.70.2021.12.03.12.39.36 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 03 Dec 2021 12:39:36 -0800 (PST) Message-ID: <361a454e-db25-4966-9d78-ace3022c8d93@redhat.com> Date: Fri, 3 Dec 2021 15:39:35 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.3.2 To: gcc-patches Subject: [PATCH 1/2] - Add BB option for outgoing_edge_range_p. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-12.2 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_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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" has_edge_range_p() and may_recompute_p() currently only take an optional edge as a parameter.  They only indicate if a range *might* be calculated for a name, but they do not do any calculations. To determine the results, they always consult the exports for the edge->src block. the value is true or false for every edge, so its really a basic block property.  This patch makes the option available to consult directly with the BB, and calls that for the edge version. Without this, if you want to know if a basic block can affect a range, you have to pick an arbitrary outgoing edge and ask with that.. which seems a little awkward. This patch is used by the next one. Bootstrapped on  x86_64-pc-linux-gnu with no regressions. OK? Andrew From cfe5cdcace399a8e615e103022140359790b3c8b Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Fri, 3 Dec 2021 10:51:18 -0500 Subject: [PATCH 1/2] Add BB option for outgoing_edge_range_p and may_reocmpute_p. There are times we only need to know if any edge from a block can calculate a range. * gimple-range-gori.h (class gori_compute):: Add prototypes. * gimple-range-gori.cc (gori_compute::has_edge_range_p): Add alternate API for basic block. Call for edge alterantive. (gori_compute::may_recompute_p): Ditto. --- gcc/gimple-range-gori.cc | 74 +++++++++++++++++++++++++--------------- gcc/gimple-range-gori.h | 6 ++-- 2 files changed, 51 insertions(+), 29 deletions(-) diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index 0dba34b58c5..6c17267ad37 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -1166,33 +1166,12 @@ gori_compute::compute_operand1_and_operand2_range (irange &r, r.intersect (op_range); return true; } -// Return TRUE if a range can be calculated or recomputed for NAME on edge E. - -bool -gori_compute::has_edge_range_p (tree name, edge e) -{ - // Check if NAME is an export or can be recomputed. - if (e) - return is_export_p (name, e->src) || may_recompute_p (name, e); - - // If no edge is specified, check if NAME can have a range calculated - // on any edge. - return is_export_p (name) || may_recompute_p (name); -} - -// Dump what is known to GORI computes to listing file F. - -void -gori_compute::dump (FILE *f) -{ - gori_map::dump (f); -} -// Return TRUE if NAME can be recomputed on edge E. If any direct dependant -// is exported on edge E, it may change the computed value of NAME. +// Return TRUE if NAME can be recomputed on any edge exiting BB. If any +// direct dependant is exported, it may also change the computed value of NAME. bool -gori_compute::may_recompute_p (tree name, edge e) +gori_compute::may_recompute_p (tree name, basic_block bb) { tree dep1 = depend1 (name); tree dep2 = depend2 (name); @@ -1207,13 +1186,47 @@ gori_compute::may_recompute_p (tree name, edge e) return false; // If edge is specified, check if NAME can be recalculated on that edge. - if (e) - return ((is_export_p (dep1, e->src)) - || (dep2 && is_export_p (dep2, e->src))); + if (bb) + return ((is_export_p (dep1, bb)) + || (dep2 && is_export_p (dep2, bb))); return (is_export_p (dep1)) || (dep2 && is_export_p (dep2)); } +// Return TRUE if NAME can be recomputed on edge E. If any direct dependant +// is exported on edge E, it may change the computed value of NAME. + +bool +gori_compute::may_recompute_p (tree name, edge e) +{ + gcc_checking_assert (e); + return may_recompute_p (name, e->src); +} + + +// Return TRUE if a range can be calculated or recomputed for NAME on any +// edge exiting BB. + +bool +gori_compute::has_edge_range_p (tree name, basic_block bb) +{ + // Check if NAME is an export or can be recomputed. + if (bb) + return is_export_p (name, bb) || may_recompute_p (name, bb); + + // If no block is specified, check for anywhere in the IL. + return is_export_p (name) || may_recompute_p (name); +} + +// Return TRUE if a range can be calculated or recomputed for NAME on edge E. + +bool +gori_compute::has_edge_range_p (tree name, edge e) +{ + gcc_checking_assert (e); + return has_edge_range_p (name, e->src); +} + // Calculate a range on edge E and return it in R. Try to evaluate a // range for NAME on this edge. Return FALSE if this is either not a // control edge or NAME is not defined by this edge. @@ -1287,6 +1300,13 @@ gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name, return false; } +// Dump what is known to GORI computes to listing file F. + +void +gori_compute::dump (FILE *f) +{ + gori_map::dump (f); +} // ------------------------------------------------------------------------ // GORI iterator. Although we have bitmap iterators, don't expose that it diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h index ec0b95145f0..b15497e9f59 100644 --- a/gcc/gimple-range-gori.h +++ b/gcc/gimple-range-gori.h @@ -158,10 +158,12 @@ class gori_compute : public gori_map public: gori_compute (int not_executable_flag = 0); bool outgoing_edge_range_p (irange &r, edge e, tree name, range_query &q); - bool has_edge_range_p (tree name, edge e = NULL); + bool has_edge_range_p (tree name, basic_block bb = NULL); + bool has_edge_range_p (tree name, edge e); void dump (FILE *f); private: - bool may_recompute_p (tree name, edge e = NULL); + bool may_recompute_p (tree name, edge e); + bool may_recompute_p (tree name, basic_block bb = NULL); bool compute_operand_range (irange &r, gimple *stmt, const irange &lhs, tree name, class fur_source &src); bool compute_operand_range_switch (irange &r, gswitch *s, const irange &lhs, -- 2.17.2 From patchwork Fri Dec 3 20:39:59 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1563385 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=Wwj1EGV6; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4J5PrJ6lkLz9s0r for ; Sat, 4 Dec 2021 07:41:52 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id BC99B385841D for ; Fri, 3 Dec 2021 20:41:50 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org BC99B385841D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1638564110; bh=mDjr6oLe/o0QYMKd4kBCch4/gpmwEKWY3AKO62BIbU0=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=Wwj1EGV6Yi4PbKq/mVmxjBmhTnQoCp1icQHacwa8DyJ2jMU2ECZ4mvEAo4iO/o9FA S1LUfr/zmMvJbzLx/XRiT/202lO+kOfNmNYDE4JYhNdzD26jUcYCUxfV6jmJc9bBaK ThPiVtTUJP4YlxfqpbHFqBxY8NPGLlWY4/wMxIpg= 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.129.124]) by sourceware.org (Postfix) with ESMTPS id 992223858420 for ; Fri, 3 Dec 2021 20:40:04 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 992223858420 Received: from mail-qt1-f200.google.com (mail-qt1-f200.google.com [209.85.160.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-393-jcmwRrJwMnqYC3-aRIOJAw-1; Fri, 03 Dec 2021 15:40:03 -0500 X-MC-Unique: jcmwRrJwMnqYC3-aRIOJAw-1 Received: by mail-qt1-f200.google.com with SMTP id o12-20020a05622a008c00b002aff5552c89so4822734qtw.23 for ; Fri, 03 Dec 2021 12:40:03 -0800 (PST) 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:from:subject:cc; bh=miAvP2CO+5Wt+slPDAe5kX+SJegdNpTnNeT+czzR1+c=; b=BorgHHyavjSKliaMQfZKVtKVG85D1URnBJyWVo42ySoZ+iCHbmoMHq8Fa7C+TXbl9R nue8xy3GvpJhuTaPTJhupsUMhj9X+t6hCXaecz3NsL65Qt7/o4kcvOzKyIyRp03dxRgj 1GBofqiZcZL+WEMNzDrHtMRzDICTyHRFCFYbPXQlIgFfVwP1/6bgzgKhMs3khJl2VzVa iV+L7WTSS2PNI+fNejqfCiVnxEp0mot+Fc+91L9GtamcCg3bB0Cr81q7zpvtOzD6yQCg SPWMn+Kl6Z0iQ3s2g7Gg4DC1vu92zeH9ufutI6QLOSiMOYyOfX60irWq1SfzR0SwuR3l GxZg== X-Gm-Message-State: AOAM531/sn3kAlYmwZHZK9v46hHKWyfbQp1dX94MbHQGI97Sz7dyUNeL azj349jFFR+ZDGM3CFClrJe6ep7gcVe2O1fxRChw86Lt7zlw7a9acQbG/hOZBEsUowR/PBjs0al IkyhQShPtIcESO4ziEUnOcLfU2Za0D02Yo3OQ+ikaiOme8mGi0R5um5YW0fNNmqHhRnQH3g== X-Received: by 2002:ac8:7d89:: with SMTP id c9mr23379961qtd.74.1638564002069; Fri, 03 Dec 2021 12:40:02 -0800 (PST) X-Google-Smtp-Source: ABdhPJx+09mIjsMIuNsb38wc1m93zk27Y0xFPec02d6JANdveh0yw/HB0yt/R4g3sW3IW07jPn5bLg== X-Received: by 2002:ac8:7d89:: with SMTP id c9mr23379934qtd.74.1638564001625; Fri, 03 Dec 2021 12:40:01 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::6d7? ([2607:fea8:a262:5f00::6d7]) by smtp.gmail.com with ESMTPSA id a38sm2561744qkp.80.2021.12.03.12.40.00 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 03 Dec 2021 12:40:01 -0800 (PST) Message-ID: <69507e99-2f0a-1187-2701-ccfb240c77b3@redhat.com> Date: Fri, 3 Dec 2021 15:39:59 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.3.2 To: gcc-patches Subject: [PATCH 2/2] Use dominators to reduce ranger cache-flling. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-12.5 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_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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" When a request is made for the range of an ssa_name at some location, the first thing we do is invoke range_of_stmt() to ensure we have looked at the definition and have an evaluation for the name at a global level.  I recently added a patch which dramatically reduces the call stack requirements for that call. Once we have confirmed the definition range has been set, a call is made for the range-on-entry to the block of the use.  This is performed by the cache, which proceeds to walk the CFG predecessors looking for when ranges are created  (exported), existing range-on-entry cache hits,  or the definition block. Once this list of  predecessors has been created, a forward walk is done, pushing the range's through successor edges of all the blocks  were visited in the initial walk. If the use is far from the definition, we end up filling a lot of the same value on these paths.  Also uses which are far from a range-modifying statement push the same value into a lot of blocks. This patch tries to address at least some inefficiencies.  It recognizes that First, if there is no range modifying stmt between this use and the last range we saw in a dominating block, we can just use the value from the dominating block and not fill in all the cache entries between here and there.  This is the biggest win. Second. if there is a range modifying statement at the end of some block, we will have to do the appropriate cache walk to this point, but its possible the range-on-entry to THAT block might be able to use a dominating range, and we can prevent the walk from going any further than this block Combined, this should prevent a lot of unnecessary ranges from being plugging into the cache. ie, to visualize: bb4:   a = foo() <..> bb60:    if (a < 30) <...> bb110:     g = a + 10 if the first place we ask for a is in bb110, we walk the CFG from 110 all the way back to bb4, on all paths leading back. then fill all those cache entries. With this patch,   a) if bb60 does not dominate bb110, the request will scan the dominators, arrive at the definition block, have seen no range modifier, and simply set the on-entry for 110 to the range of a. done.   b) if bb60 does dominate 110, we have no idea which edge out of 60 dominates it, so we will revert to he existing cache algorithm.  Before doing so, it checks and determines that there are no modifiers between bb60 and the def in bb4, and so sets the on-entry cache for bb60 to be the range of a.   Now when we do the cache fill walk, it only has to go back as far as bb60 instead of all the way to bb4. Otherwise we just revert to what we do now (or if dominators are not available).   I have yet to see a case where we miss something we use to get, but that does not mean there isn't one :-). The cumulative performance impact of this compiling a set of 390 GCC source files at -O2 (measured via callgrind) is pretty decent:  Negative numbers are a compile time decrease.  Thus -10% is 10% faster compilation time. EVRP     : %change from trunk is -26.31% (!) VRP2     : %change from trunk is -9.53% thread_jumps_full   : %change from trunk is -15.8% Total compilation time  : %change from trunk is -1.06% So its not insignificant. Risk would be very low, unless dominators are screwed up mid-pass.. but then the relation code would be screwed up too. Bootstrapped on  x86_64-pc-linux-gnu with no regressions. OK? Andrew From ea2f90151dcaeea2b5c372f900e1eef735269e18 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Fri, 3 Dec 2021 11:02:19 -0500 Subject: [PATCH 2/2] Use dominators to reduce cache-flling. Before walking the CFG and filling all cache entries, check if the same information is available in a dominator. * gimple-range-cache.cc (ranger_cache::fill_block_cache): Check for a range from dominators before filling the cache. (ranger_cache::range_from_dom): New. --- gcc/gimple-range-cache.cc | 73 +++++++++++++++++++++++++++++++++++++++ gcc/gimple-range-cache.h | 1 + 2 files changed, 74 insertions(+) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index fe31e9462aa..47e95ec23be 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -1312,6 +1312,20 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) fprintf (dump_file, " : "); } + // If there are dominators, check if a dominators can supply the range. + if (dom_info_available_p (CDI_DOMINATORS) + && range_from_dom (block_result, name, bb)) + { + m_on_entry.set_bb_range (name, bb, block_result); + if (DEBUG_RANGE_CACHE) + { + fprintf (dump_file, "Filled from dominator! : "); + block_result.dump (dump_file); + fprintf (dump_file, "\n"); + } + return; + } + while (m_workback.length () > 0) { basic_block node = m_workback.pop (); @@ -1394,3 +1408,62 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) fprintf (dump_file, " Propagation update done.\n"); } + +// Check to see if we can simply get the range from the dominator. + +bool +ranger_cache::range_from_dom (irange &r, tree name, basic_block bb) +{ + gcc_checking_assert (dom_info_available_p (CDI_DOMINATORS)); + + // Search back to the definition block or entry block. + basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name)); + if (def_bb == NULL) + def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun); + + // Flag if we encounter a block with non-null set. + bool non_null = false; + for (bb = get_immediate_dominator (CDI_DOMINATORS, bb); + bb && bb != def_bb; + bb = get_immediate_dominator (CDI_DOMINATORS, bb)) + { + // If there is an outgoing range, the on-entry value won't work. + if (m_gori.has_edge_range_p (name, bb)) + { + // Check if we can seed this block with a dominator value. THis will + // prevent the ache from being filled back further than this. + if (bb != def_bb && range_from_dom (r, name, bb)) + m_on_entry.set_bb_range (name, bb, r); + return false; + } + + // Flag if we see a non-null reference during this walk. + if (m_non_null.non_null_deref_p (name, bb, false)) + non_null = true; + + // If range-on-entry is set in this block, it can be used. + if (m_on_entry.get_bb_range (r, name, bb)) + { + // Apply non-null if appropriate. + if (r.varying_p () && non_null) + { + gcc_checking_assert (POINTER_TYPE_P (TREE_TYPE (name))); + r.set_nonzero (TREE_TYPE (name)); + } + return true; + } + } + // If this is the def block, and NAME is an export, then this value + // cannot be used. + if (bb == def_bb && m_gori.has_edge_range_p (name, bb)) + return false; + + // Otherwise choose the global value and use it. + get_global_range (r, name); + if (r.varying_p () && non_null) + { + gcc_checking_assert (POINTER_TYPE_P (TREE_TYPE (name))); + r.set_nonzero (TREE_TYPE (name)); + } + return true; +} diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index eb7a875c46b..2c52a0b6ce3 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -98,6 +98,7 @@ public: virtual bool range_of_expr (irange &r, tree name, gimple *stmt); virtual bool range_on_edge (irange &r, edge e, tree expr); bool block_range (irange &r, basic_block bb, tree name, bool calc = true); + bool range_from_dom (irange &r, tree name, basic_block bb); bool get_global_range (irange &r, tree name) const; bool get_global_range (irange &r, tree name, bool ¤t_p); -- 2.17.2