From patchwork Wed Aug 23 18:47:53 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1824899 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.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=cnxK/7Ug; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.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 ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4RWFbj6cgQz1ydy for ; Thu, 24 Aug 2023 04:48:22 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 1DF35385DC04 for ; Wed, 23 Aug 2023 18:48:20 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 1DF35385DC04 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1692816500; bh=13xJGHZY3WXSVUORsr1zeONZuR5ipr5UvsMf5/B1eZI=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=cnxK/7UgK4csoqtoUPont0FrM68fOjH6YCGNVweUVQZGAmA4XEMu9Tq3OpfaeU3SO kN/jn6QKU+7WGAzAyoqQxeTDOmj26c6ahG1ou5apeM4hv+o5fBEbg0qRO1oejwqSlX 6g7eKSzm3Gp+3wQsiieW4LBjxT8LSuzdunvpC3wQ= 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 6FFE3385B524 for ; Wed, 23 Aug 2023 18:47:58 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6FFE3385B524 Received: from mail-qv1-f69.google.com (mail-qv1-f69.google.com [209.85.219.69]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-376-rO6NKF1bNgCJd28ti1PnlA-1; Wed, 23 Aug 2023 14:47:56 -0400 X-MC-Unique: rO6NKF1bNgCJd28ti1PnlA-1 Received: by mail-qv1-f69.google.com with SMTP id 6a1803df08f44-64a459efdbcso74635316d6.3 for ; Wed, 23 Aug 2023 11:47:56 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692816475; x=1693421275; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=2y4i5S9bxPXOhubhqNL6UKvrXVJTsCwb93tUyzjqc48=; b=B6wjDW1C4ry8Oyx8lCrXiAYUn6HFVaJjmnEkTZs4H+vuuhiS1w+HylBJm6MSg2wmb+ PpexqWPcKbaTupUuZmfGwEwoERzuy6k3SMl3ZsD+482+BgpXgxR3balJxZXlnKvroAR1 qi4EG/5R+rCkzTzmCh/QIDlWgvF47RPJozPpYQCK8EK0MKhF879KLaYZMtrz3QGiAPCe 2pUfqWSk3gtlOgrjnQJmrvtEbKv0LW43azvz+MOWIptXNzIp5ysz/4r/yx+CNooTupCh K99rNNiS8IihV8H2/nKRC5s+fyXo5L8X6U9L6NkOcBfylAw6NRKlXOdJ2q5QuniKqQCm PtOA== X-Gm-Message-State: AOJu0Yw+LJYKZkOc/wF3WrgYm3tHQPrQ5+nBjAWYWwZomxlNaxIBuECI 7rxEosMs2+VRXvNABiEdet1QCVkLq4WIQOrKJxs/1pFQfeqRc3OrKBYdIYY8ScXTyn4oxJ7OIO/ gEe7z++D6HVw9ZKXbKKHHl3guvHe77el0F6Dl6DIW/ox4v2wTaE3+FCNuVFwN+UzC/MBvQsupRm Jtxw== X-Received: by 2002:ad4:559c:0:b0:626:b17:3b97 with SMTP id f28-20020ad4559c000000b006260b173b97mr10904874qvx.65.1692816475502; Wed, 23 Aug 2023 11:47:55 -0700 (PDT) X-Google-Smtp-Source: AGHT+IHkMHQbV8giH2Fie1Qv5/mNRaf0hMM09Tut8KoWVbptSucNkn7hQmPSShxQUf3Oir1xJ1+LKA== X-Received: by 2002:ad4:559c:0:b0:626:b17:3b97 with SMTP id f28-20020ad4559c000000b006260b173b97mr10904862qvx.65.1692816475175; Wed, 23 Aug 2023 11:47:55 -0700 (PDT) Received: from ?IPV6:2607:fea8:51e3:8300::28f5? ([2607:fea8:51e3:8300::28f5]) by smtp.gmail.com with ESMTPSA id k8-20020a0cb248000000b006490a9946b6sm4812608qve.119.2023.08.23.11.47.54 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 23 Aug 2023 11:47:54 -0700 (PDT) Message-ID: <921b7149-303a-bf0f-e550-864d5d4b5056@redhat.com> Date: Wed, 23 Aug 2023 14:47:53 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.13.0 To: gcc-patches Cc: "hernandez, aldy" Subject: [COMMITTED 1/2] Phi analyzer - Do not create phi groups with a single phi. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US 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_NONE, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, 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" Rangers Phi Analyzer was creating a group consisting of a single PHI, which was problematic.  It didn't really help anything, and it prevented larger groups from including those PHIs and stopped some useful things from happening. Bootstrapped on x86_64-pc-linux-gnu  with no regressions. Pushed. Andrew From 9855b3f0a2869d456f0ee34a94a1231eb6d44c4a Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Wed, 16 Aug 2023 13:23:06 -0400 Subject: [PATCH 1/4] Don't process phi groups with one phi. The phi analyzer should not create a phi group containing a single phi. * gimple-range-phi.cc (phi_analyzer::operator[]): Return NULL if no group was created. (phi_analyzer::process_phi): Do not create groups of one phi node. --- gcc/gimple-range-phi.cc | 16 +++++++++++----- 1 file changed, 11 insertions(+), 5 deletions(-) diff --git a/gcc/gimple-range-phi.cc b/gcc/gimple-range-phi.cc index ffb4691d06b..a94b90a4660 100644 --- a/gcc/gimple-range-phi.cc +++ b/gcc/gimple-range-phi.cc @@ -344,9 +344,10 @@ phi_analyzer::operator[] (tree name) process_phi (as_a (SSA_NAME_DEF_STMT (name))); if (bitmap_bit_p (m_simple, v)) return NULL; - // If m_simple bit isn't set, then process_phi allocated the table - // and should have a group. - gcc_checking_assert (v < m_tab.length ()); + // If m_simple bit isn't set, and process_phi didn't allocated the table + // no group was created, so return NULL. + if (v >= m_tab.length ()) + return NULL; } return m_tab[v]; } @@ -363,6 +364,7 @@ phi_analyzer::process_phi (gphi *phi) unsigned x; m_work.truncate (0); m_work.safe_push (gimple_phi_result (phi)); + unsigned phi_count = 1; bitmap_clear (m_current); // We can only have 2 externals: an initial value and a modifier. @@ -407,6 +409,7 @@ phi_analyzer::process_phi (gphi *phi) gimple *arg_stmt = SSA_NAME_DEF_STMT (arg); if (arg_stmt && is_a (arg_stmt)) { + phi_count++; m_work.safe_push (arg); continue; } @@ -430,9 +433,12 @@ phi_analyzer::process_phi (gphi *phi) } } - // If there are no names in the group, we're done. - if (bitmap_empty_p (m_current)) + // If there are less than 2 names, just return. This PHI may be included + // by another PHI, making it simple or a group of one will prevent a larger + // group from being formed. + if (phi_count < 2) return; + gcc_checking_assert (!bitmap_empty_p (m_current)); phi_group *g = NULL; if (cycle_p) -- 2.41.0 From patchwork Wed Aug 23 18:48:15 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1824901 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.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=on704oxa; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.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 ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4RWFbx3tC6z1ybW for ; Thu, 24 Aug 2023 04:48:45 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 55F003853543 for ; Wed, 23 Aug 2023 18:48:43 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 55F003853543 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1692816523; bh=9nHi5n/BQ9M6QITgmpnbwheEMM1CQCGjLzSEdTLYnTs=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=on704oxar23OmaLCUi6Fxz7SuDYUeLawlvW5l1rKXzbNxMvsqXMz3rQRzdc1hAwOk iJB74bMUzX/zAfccsmRHcDmxNG0iU8bKHVxB1PMlkkq16gLLtuKdwXMLn01/+zIfYr pctbVEbxZQ9QQRTc95i+/u5mwGsKFUjERugVfQjY= 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 5FD35385DC10 for ; Wed, 23 Aug 2023 18:48:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 5FD35385DC10 Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-602-jynI-kRwOKyJBvJGyh9ifg-1; Wed, 23 Aug 2023 14:48:18 -0400 X-MC-Unique: jynI-kRwOKyJBvJGyh9ifg-1 Received: by mail-qk1-f197.google.com with SMTP id af79cd13be357-76dbe1865c1so126530685a.0 for ; Wed, 23 Aug 2023 11:48:18 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692816498; x=1693421298; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=j8HjqGNgjlY2yb6aTGaSNyarg77dymDxo2xL5BWY++Y=; b=G/nWEMIHvnoq7vhXDRfhNLSpjHqWfCXupu6diK8gTC5SsmWnLzCo35PMEnSPgOdPgo D3If7VRWNIVzLB6E/pxcEkUz+w42+5h7EHgsnah99EcttZhbc52hcktCFDfBBSdVsLuf nWZWKNMe0koSzP0QIyOJqXxcN6DJZ0h1SNJTyP/LlSR2KAP5yFL+MZ9vd+srP1OPzkwN PECSDQBjLJxJpHin1hxoWoo8K8bx1JtvbAnwQgEkGL7iC5DaEN8aPl4L6ontvcNnUisO //YTY4wfFMiIqfifZTcKWVVpKk6JlM5VRyGtMeslTog0nnD2n68hBfWhEofslLJKWeA6 knjA== X-Gm-Message-State: AOJu0YzwbM+MQTm5Arv1KixKmPGU2yMBnCkDUn5Aryu0xOOXdwAwCqmr pZa1/pvTg/u0tIiV9RM7/0owfjvaauqWh7ZTksr6QN8rYEfjQ+2CmZDTQfGR+MPfXPVVSnbwVsW SELIcqtlvgeOvT8YUWytIM7pqXW8WZ4Vv55HE3h4q0dS473a3ZTTRpyE7hbuRva8lnUg/CB511R ICkA== X-Received: by 2002:a05:6214:468a:b0:64f:4bfc:714b with SMTP id or10-20020a056214468a00b0064f4bfc714bmr7930513qvb.44.1692816497774; Wed, 23 Aug 2023 11:48:17 -0700 (PDT) X-Google-Smtp-Source: AGHT+IHenQbpEPOFPoP64N179G3T11Fw7nQDlFm/EzREKuV63PHTYWH63fbZwSzIUXykPE6ANDEAJA== X-Received: by 2002:a05:6214:468a:b0:64f:4bfc:714b with SMTP id or10-20020a056214468a00b0064f4bfc714bmr7930494qvb.44.1692816497408; Wed, 23 Aug 2023 11:48:17 -0700 (PDT) Received: from ?IPV6:2607:fea8:51e3:8300::28f5? ([2607:fea8:51e3:8300::28f5]) by smtp.gmail.com with ESMTPSA id b10-20020a0cb3ca000000b0064f378f89a7sm3352384qvf.73.2023.08.23.11.48.16 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 23 Aug 2023 11:48:16 -0700 (PDT) Message-ID: <42ea3288-ddc2-4a49-9e9c-41116dffc62e@redhat.com> Date: Wed, 23 Aug 2023 14:48:15 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.13.0 To: gcc-patches Cc: "hernandez, aldy" Subject: [COMMITTED 2/2] tree-optimization/110918 - Phi analyzer - Initialize with a range instead of a tree. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US 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_NONE, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, 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" Rangers PHI analyzer currently only allows a single initializing value to a group. This patch changes that to use an initialization range, which is cumulative of all integer constants, plus a single symbolic value.  There were many times when there were multiple constants feeding into PHIs and there is no reason to disqualify those from determining if there is a better starting range for a PHI, This patch also changes the way PHI groups are printed so they show up in the listing as they are encountered, rather than as a list at the end.  It was quite difficult to see what was going on when it simply dumped the groups at the end of processing. Bootstraps on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From bd50bbfa95e51edf51392f147e9a860adb5f495e Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 17 Aug 2023 12:34:59 -0400 Subject: [PATCH 2/4] Phi analyzer - Initialize with range instead of a tree. Rangers PHI analyzer currently only allows a single initializer to a group. This patch changes that to use an inialization range, which is cumulative of all integer constants, plus a single symbolic value. There is no other change to group functionality. This patch also changes the way PHI groups are printed so they show up in the listing as they are encountered, rather than as a list at the end. It was more difficult to see what was going on previously. PR tree-optimization/110918 - Initialize with range instead of a tree. gcc/ * gimple-range-fold.cc (fold_using_range::range_of_phi): Tweak output. * gimple-range-phi.cc (phi_group::phi_group): Remove unused members. Initialize using a range instead of value and edge. (phi_group::calculate_using_modifier): Use initializer value and process for relations after trying for iteration convergence. (phi_group::refine_using_relation): Use initializer range. (phi_group::dump): Rework the dump output. (phi_analyzer::process_phi): Allow multiple constant initilizers. Dump groups immediately as created. (phi_analyzer::dump): Tweak output. * gimple-range-phi.h (phi_group::phi_group): Adjust prototype. (phi_group::initial_value): Delete. (phi_group::refine_using_relation): Adjust prototype. (phi_group::m_initial_value): Delete. (phi_group::m_initial_edge): Delete. (phi_group::m_vr): Use int_range_max. * tree-vrp.cc (execute_ranger_vrp): Don't dump phi groups. gcc/testsuite/ * gcc.dg/pr102983.c: Adjust output expectations. * gcc.dg/pr110918.c: New. --- gcc/gimple-range-fold.cc | 6 +- gcc/gimple-range-phi.cc | 186 ++++++++++++++++---------------- gcc/gimple-range-phi.h | 9 +- gcc/testsuite/gcc.dg/pr102983.c | 2 +- gcc/testsuite/gcc.dg/pr110918.c | 26 +++++ gcc/tree-vrp.cc | 5 +- 6 files changed, 129 insertions(+), 105 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/pr110918.c diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index 7fa5a27cb12..8ebff7f5980 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -953,7 +953,7 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src) { if (dump_file && (dump_flags & TDF_DETAILS)) { - fprintf (dump_file, " Loops range found for "); + fprintf (dump_file, "Loops range found for "); print_generic_expr (dump_file, phi_def, TDF_SLIM); fprintf (dump_file, ": "); loop_range.dump (dump_file); @@ -975,9 +975,9 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src) { if (dump_file && (dump_flags & TDF_DETAILS)) { - fprintf (dump_file, " PHI group range found for "); + fprintf (dump_file, "PHI GROUP query for "); print_generic_expr (dump_file, phi_def, TDF_SLIM); - fprintf (dump_file, ": "); + fprintf (dump_file, " found : "); g->range ().dump (dump_file); fprintf (dump_file, " and adjusted original range from :"); r.dump (dump_file); diff --git a/gcc/gimple-range-phi.cc b/gcc/gimple-range-phi.cc index a94b90a4660..9884a0ebbb0 100644 --- a/gcc/gimple-range-phi.cc +++ b/gcc/gimple-range-phi.cc @@ -79,39 +79,33 @@ phi_analyzer &phi_analysis () phi_group::phi_group (const phi_group &g) { m_group = g.m_group; - m_initial_value = g.m_initial_value; - m_initial_edge = g.m_initial_edge; m_modifier = g.m_modifier; m_modifier_op = g.m_modifier_op; m_vr = g.m_vr; } -// Create a new phi_group with members BM, initialvalue INIT_VAL, modifier -// statement MOD, and resolve values using query Q. -// Calculate the range for the gropup if possible, otherwise set it to -// VARYING. +// Create a new phi_group with members BM, initial range INIT_RANGE, modifier +// statement MOD on edge MOD_EDGE, and resolve values using query Q. Calculate +// the range for the group if possible, otherwise set it to VARYING. -phi_group::phi_group (bitmap bm, tree init_val, edge e, gimple *mod, +phi_group::phi_group (bitmap bm, irange &init_range, gimple *mod, range_query *q) { // we dont expect a modifer and no inital value, so trap to have a look. // perhaps they are dead cycles and we can just used UNDEFINED. - gcc_checking_assert (init_val); + gcc_checking_assert (!init_range.undefined_p ()); + gcc_checking_assert (!init_range.varying_p ()); m_modifier_op = is_modifier_p (mod, bm); m_group = bm; - m_initial_value = init_val; - m_initial_edge = e; + m_vr = init_range; m_modifier = mod; - if (q->range_on_edge (m_vr, m_initial_edge, m_initial_value)) - { - // No modifier means the initial range is the full range. - // Otherwise try to calculate a range. - if (!m_modifier_op || calculate_using_modifier (q)) - return; - } + // No modifier means the initial range is the full range. + // Otherwise try to calculate a range. + if (!m_modifier_op || calculate_using_modifier (q)) + return; // Couldn't calculate a range, set to varying. - m_vr.set_varying (TREE_TYPE (init_val)); + m_vr.set_varying (init_range.type ()); } // Return 0 if S is not a modifier statment for group members BM. @@ -151,27 +145,29 @@ phi_group::calculate_using_modifier (range_query *q) else return false; - // If we can resolve the range using relations, use that range. - if (refine_using_relation (k, q)) - return true; - - // If the initial value is undefined, do not calculate a range. - if (m_vr.undefined_p ()) - return false; - - // Examine modifier and run X iterations to see if it convergences. + // Examine modifier and run 10 iterations to see if it convergences. // The constructor initilaized m_vr to the initial value already. + const unsigned num_iter = 10; int_range_max nv; - for (unsigned x = 0; x< 10; x++) + int_range_max iter_value = m_vr; + for (unsigned x = 0; x < num_iter; x++) { - if (!fold_range (nv, m_modifier, m_vr, q)) - return false; - // If they are equal, then we have convergence. - if (nv == m_vr) - return true; - // Update range and try again. - m_vr.union_ (nv); + if (!fold_range (nv, m_modifier, iter_value, q)) + break; + // If union does nothing, then we have convergence. + if (!iter_value.union_ (nv)) + { + if (iter_value.varying_p ()) + break; + m_vr = iter_value; + return true; + } } + + // If we can resolve the range using relations, use that range. + if (refine_using_relation (k)) + return true; + // Never converged, so bail for now. we could examine the pattern // from m_initial to m_vr as an extension Especially if we had a way // to project the actual number of iterations (SCEV?) @@ -185,34 +181,29 @@ phi_group::calculate_using_modifier (range_query *q) // IF the modifier statement has a relation K between the modifier and the // PHI member in it, we can project a range based on that. -// Use range_query Q to resolve values. // ie, a_2 = PHI <0, a_3> and a_3 = a_2 + 1 // if the relation a_3 > a_2 is present, the know the range is [0, +INF] +// m_vr contains the initial value for the PHI range. bool -phi_group::refine_using_relation (relation_kind k, range_query *q) +phi_group::refine_using_relation (relation_kind k) { if (k == VREL_VARYING) return false; - tree type = TREE_TYPE (m_initial_value); + tree type = m_vr.type (); // If the type wraps, then relations dont tell us much. if (TYPE_OVERFLOW_WRAPS (type)) return false; + int_range<2> type_range; + type_range.set_varying (type); switch (k) { case VREL_LT: case VREL_LE: { // Value always decreases. - int_range<2> lb; - int_range<2> ub; - if (!q->range_on_edge (ub, m_initial_edge, m_initial_value)) - break; - if (ub.undefined_p ()) - return false; - lb.set_varying (type); - m_vr.set (type, lb.lower_bound (), ub.upper_bound ()); + m_vr.set (type, type_range.lower_bound (), m_vr.upper_bound ()); return true; } @@ -220,14 +211,7 @@ phi_group::refine_using_relation (relation_kind k, range_query *q) case VREL_GE: { // Value always increases. - int_range<2> lb; - int_range<2> ub; - if (!q->range_on_edge (lb, m_initial_edge, m_initial_value)) - break; - if (lb.undefined_p ()) - return false; - ub.set_varying (type); - m_vr.set (type, lb.lower_bound (), ub.upper_bound ()); + m_vr.set (type, m_vr.lower_bound (), type_range.upper_bound ()); return true; } @@ -250,34 +234,20 @@ phi_group::dump (FILE *f) { unsigned i; bitmap_iterator bi; - fprintf (f, "PHI GROUP <"); + fprintf (f, "PHI GROUP < "); EXECUTE_IF_SET_IN_BITMAP (m_group, 0, i, bi) { print_generic_expr (f, ssa_name (i), TDF_SLIM); fputc (' ',f); } - - fprintf (f, ">\n - Initial value : "); - if (m_initial_value) - { - if (TREE_CODE (m_initial_value) == SSA_NAME) - print_gimple_stmt (f, SSA_NAME_DEF_STMT (m_initial_value), 0, TDF_SLIM); - else - print_generic_expr (f, m_initial_value, TDF_SLIM); - fprintf (f, " on edge %d->%d", m_initial_edge->src->index, - m_initial_edge->dest->index); - } - else - fprintf (f, "NONE"); - fprintf (f, "\n - Modifier : "); + fprintf (f, "> : range : "); + m_vr.dump (f); + fprintf (f, "\n Modifier : "); if (m_modifier) print_gimple_stmt (f, m_modifier, 0, TDF_SLIM); else fprintf (f, "NONE\n"); - fprintf (f, " - Range : "); - m_vr.dump (f); - fputc ('\n', f); } // ------------------------------------------------------------------------- @@ -372,17 +342,18 @@ phi_analyzer::process_phi (gphi *phi) unsigned m_num_extern = 0; tree m_external[2]; edge m_ext_edge[2]; + int_range_max init_range; + init_range.set_undefined (); while (m_work.length () > 0) { tree phi_def = m_work.pop (); gphi *phi_stmt = as_a (SSA_NAME_DEF_STMT (phi_def)); - // if the phi is already in a cycle, its a complex situation, so revert - // to simple. + // if the phi is already in a different cycle, we don't try to merge. if (group (phi_def)) { cycle_p = false; - continue; + break; } bitmap_set_bit (m_current, SSA_NAME_VERSION (phi_def)); // Process the args. @@ -405,7 +376,6 @@ phi_analyzer::process_phi (gphi *phi) break; } // Check if its a PHI to examine. - // *FIX* Will miss initial values that originate from a PHI. gimple *arg_stmt = SSA_NAME_DEF_STMT (arg); if (arg_stmt && is_a (arg_stmt)) { @@ -413,23 +383,28 @@ phi_analyzer::process_phi (gphi *phi) m_work.safe_push (arg); continue; } + // More than 2 outside names is too complicated. + if (m_num_extern >= 2) + { + cycle_p = false; + break; + } + m_external[m_num_extern] = arg; + m_ext_edge[m_num_extern++] = gimple_phi_arg_edge (phi_stmt, x); } - // Other non-ssa names that arent constants are not understood - // and terminate analysis. - else if (code != INTEGER_CST && code != REAL_CST) + else if (code == INTEGER_CST) { - cycle_p = false; - continue; + // Constants are just added to the initialization value. + int_range<1> val (TREE_TYPE (arg), wi::to_wide (arg), + wi::to_wide (arg)); + init_range.union_ (val); } - // More than 2 outside names/CONST is too complicated. - if (m_num_extern >= 2) + else { + // Everything else terminates the cycle. cycle_p = false; break; } - - m_external[m_num_extern] = arg; - m_ext_edge[m_num_extern++] = gimple_phi_arg_edge (phi_stmt, x); } } @@ -465,14 +440,43 @@ phi_analyzer::process_phi (gphi *phi) valid = false; init_idx = x; } - if (valid) + int_range_max init_sym; + // If there is an symbolic initializer as well, include it here. + if (valid && init_idx != -1) + { + if (m_global.range_on_edge (init_sym, m_ext_edge[init_idx], + m_external[init_idx])) + init_range.union_ (init_sym); + else + valid = false; + } + if (valid && !init_range.varying_p () && !init_range.undefined_p ()) { // Try to create a group based on m_current. If a result comes back // with a range that isn't varying, create the group. - phi_group cyc (m_current, m_external[init_idx], - m_ext_edge[init_idx], mod, &m_global); + phi_group cyc (m_current, init_range, mod, &m_global); if (!cyc.range ().varying_p ()) - g = new phi_group (cyc); + { + g = new phi_group (cyc); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "PHI ANALYZER : New "); + g->dump (dump_file); + fprintf (dump_file," Initial range was "); + init_range.dump (dump_file); + if (init_idx != -1) + { + fprintf (dump_file, " including symbolic "); + print_generic_expr (dump_file, m_external[init_idx], + TDF_SLIM); + fprintf (dump_file, " on edge %d->%d with range ", + m_ext_edge[init_idx]->src->index, + m_ext_edge[init_idx]->dest->index); + init_sym.dump (dump_file); + } + fputc ('\n',dump_file); + } + } } } // If this dpoesn;t form a group, all members are instead simple phis. @@ -517,7 +521,7 @@ phi_analyzer::dump (FILE *f) if (!header) { header = true; - fprintf (dump_file, "\nPHI GROUPS:\n"); + fprintf (f, "\nPHI GROUPS:\n"); } g->dump (f); } diff --git a/gcc/gimple-range-phi.h b/gcc/gimple-range-phi.h index b5120e97bf3..8e63303f708 100644 --- a/gcc/gimple-range-phi.h +++ b/gcc/gimple-range-phi.h @@ -50,23 +50,20 @@ along with GCC; see the file COPYING3. If not see class phi_group { public: - phi_group (bitmap bm, tree init_val, edge e, gimple *mod, range_query *q); + phi_group (bitmap bm, irange &init_range, gimple *mod, range_query *q); phi_group (const phi_group &g); const_bitmap group () const { return m_group; } const vrange &range () const { return m_vr; } - tree initial_value () const { return m_initial_value; } gimple *modifier_stmt () const { return m_modifier; } void dump (FILE *); protected: bool calculate_using_modifier (range_query *q); - bool refine_using_relation (relation_kind k, range_query *q); + bool refine_using_relation (relation_kind k); static unsigned is_modifier_p (gimple *s, const bitmap bm); bitmap m_group; - tree m_initial_value; // Name or constant. - edge m_initial_edge; // Edge of initial value. gimple *m_modifier; // Single stmt which modifies phi group. unsigned m_modifier_op; // Operand of group member in modifier stmt. - int_range<3> m_vr; + int_range_max m_vr; friend class phi_analyzer; }; diff --git a/gcc/testsuite/gcc.dg/pr102983.c b/gcc/testsuite/gcc.dg/pr102983.c index e1bd24b2e39..ded748af08a 100644 --- a/gcc/testsuite/gcc.dg/pr102983.c +++ b/gcc/testsuite/gcc.dg/pr102983.c @@ -18,4 +18,4 @@ int main() { } } -/* { dg-final { scan-tree-dump-times "Folding predicate c_.* to 1" 1 "evrp" } } */ +/* { dg-final { scan-tree-dump-times "Global Exported: c_.*1, 1" 1 "evrp" } } */ diff --git a/gcc/testsuite/gcc.dg/pr110918.c b/gcc/testsuite/gcc.dg/pr110918.c new file mode 100644 index 00000000000..e2dff27e078 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr110918.c @@ -0,0 +1,26 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-tree-optimized" } */ + +static char b = 53; +static unsigned c; +void foo(void); +static int(a)(int d, int e) { return (d ^ e) < 0 ? d : d - e; } +int main() { + { + int f = 2; + c = b; + b = 0; + for (; c <= 6;) { + if (f >= 2) + f = 0; + for (; f >= -9; f = a(f, 8)) + if (!(f >= -8 && f <= 0)) + foo(); + } + } +} + + +/* { dg-final { scan-tree-dump-not "foo" "optimized" } } */ + + diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc index d61b087b730..2d9f6273280 100644 --- a/gcc/tree-vrp.cc +++ b/gcc/tree-vrp.cc @@ -934,10 +934,7 @@ execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p, // Remove tagged builtin-unreachable and maybe update globals. folder.m_unreachable.remove_and_update_globals (final_p); if (dump_file && (dump_flags & TDF_DETAILS)) - { - phi_analysis ().dump (dump_file); - ranger->dump (dump_file); - } + ranger->dump (dump_file); if ((warn_array_bounds || warn_strict_flex_arrays) && warn_array_bounds_p) { -- 2.41.0