From patchwork Wed Nov 3 14:38:19 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 46992 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C7C793858D35 for ; Wed, 3 Nov 2021 14:38:59 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C7C793858D35 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1635950339; bh=d54Xz1t7cORruHYyqErAdn6oFJU9yrUm5I9aEv3ZYsg=; h=Subject:To:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=XbOeu1qWT5Mh6zDxyAD0gb5VSjO6F/r8ESGjFAL/r6xQjMeNB5BoMTzmyimQ4JdFB 65z5VfTXaxHAGMTXf+x3OCLD4BMhYnvr+7dR1DdzMhnB+N0odWl3Xm3R71i9mF9bMA SKYnww8rFvfmlaowymBz85QyEoY4Kh0PQdGe8HiU= 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 317E13858003 for ; Wed, 3 Nov 2021 14:38:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 317E13858003 Received: from mail-qk1-f200.google.com (mail-qk1-f200.google.com [209.85.222.200]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-434-dNszQDtGMJqjEWCUiImeFA-1; Wed, 03 Nov 2021 10:38:23 -0400 X-MC-Unique: dNszQDtGMJqjEWCUiImeFA-1 Received: by mail-qk1-f200.google.com with SMTP id br11-20020a05620a460b00b004630d0237f2so2478835qkb.17 for ; Wed, 03 Nov 2021 07:38:23 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:subject:to:cc:message-id:date:user-agent :mime-version:content-language; bh=d54Xz1t7cORruHYyqErAdn6oFJU9yrUm5I9aEv3ZYsg=; b=MxpwU4+FpWQOM9ejR1Jy+765Tq2TNmAlKfkq8YfpZvdUTzzZ8a3XFyMmc2mXg1qjRa 2mG9RNJwjgALoDqdaRKQqjyZ3gjzUClfxhLyJfCOBNzAW9/xei2sIIu83RQd6ZVyVvDI c4jSdoEdxgZB3Ayw5sXlNBiz9kYqGG3DbztLEoygjXZ1Sj5BmpEHsypnw1VcC0qkpGsQ QapYiKiLkW9fOyGZzTNKrnU5eQ+0GCpj0iF8y4oJS6B6ic7GaWycRoO5MkeU8uqHckcg OBXa6r3XXVQ/syPyXjbhiZq07SggzwYyTeH78SX55c/rqsTp6ZGjgnbMmBjrFGWbxKkP JmaA== X-Gm-Message-State: AOAM533zYcKot5EjcLTMVstByXunMMppnkmIovlpPhaYTrUK8QLLkBq7 +GKgCix/pB69TA3obyY8iWJFoNxDLvlldW0y4lBh8TZMFNjjvuatkWRiLMeH64lssy54aWWlqof qC5usWJzKrIb27xCJhQ== X-Received: by 2002:a0c:e84b:: with SMTP id l11mr29346863qvo.25.1635950302979; Wed, 03 Nov 2021 07:38:22 -0700 (PDT) X-Google-Smtp-Source: ABdhPJzVscsALb6qWGu6yETEAzZrWjGQeJqaobAUK9G1hKH6S9jkAkSF3m740In73rT7IJBxyV1W9g== X-Received: by 2002:a0c:e84b:: with SMTP id l11mr29346844qvo.25.1635950302740; Wed, 03 Nov 2021 07:38:22 -0700 (PDT) Received: from ?IPv6:2607:fea8:a262:5f00::38cf? ([2607:fea8:a262:5f00::38cf]) by smtp.gmail.com with ESMTPSA id i14sm1755229qti.25.2021.11.03.07.38.19 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 03 Nov 2021 07:38:20 -0700 (PDT) Subject: [COMMITTED] Provide some context to folding via ranger. To: gcc-patches Message-ID: Date: Wed, 3 Nov 2021 10:38:19 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-11.0 required=5.0 tests=BAYES_00, BODY_8BITS, 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 Cc: Jakub Jelinek Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" So one thing rangers version of VRP is missing that EVRP and VRP were capable of are demonstrated in gcc.dg/pr69097-1.c. This testcase uses the gimple simplifier to eliminate the negation of x % -y   :   if (y_2(D) == -1)     goto ; [INV]   else     goto ; [INV]   :   __builtin_unreachable ();   :   _1 = -y_2(D);   _4 = x_3(D) % _1;   return _4; The pattern in match.pd is triggered: /* X % -Y is the same as X % Y.  */ (simplify  (trunc_mod @0 (convert? (negate @1)))  (if (INTEGRAL_TYPE_P (type)       && !TYPE_UNSIGNED (type)       && !TYPE_OVERFLOW_TRAPS (type)       && tree_nop_conversion_p (type, TREE_TYPE (@1))       /* Avoid this transformation if X might be INT_MIN or          Y might be -1, because we would then change valid          INT_MIN % -(-1) into invalid INT_MIN % -1.  */       && (expr_not_equal_to (@0, wi::to_wide (TYPE_MIN_VALUE (type)))           || expr_not_equal_to (@1, wi::minus_one (TYPE_PRECISION                                                         (TREE_TYPE (@1))))))   (trunc_mod @0 (convert @1)))) but the problem is a lack of context provided by the query for ranger to provide the proper range.  from fold-const.c: bool expr_not_equal_to (tree t, const wide_int &w) {  <..>     case SSA_NAME:       if (!INTEGRAL_TYPE_P (TREE_TYPE (t)))         return false;       if (cfun)         get_range_query (cfun)->range_of_expr (vr, t);       else         get_global_range_query ()->range_of_expr (vr, t); we call range_of_expr, but there is no context, so ranger has to resort to global values, and we do not have the correct value of ~[-1,-1] for Y as a global value.  Then we miss the fold. EVRP provides a "current" value vector so it always picks the latest value in the block, and VRP uses ASSERT_EXPR to split up the live ranges of SSA_NAMEs such that the global value of a name is its actual contextual value. The call chain starts with the stmt in fold_stmt, so the context is provided initially, but as we get into the match and fold mechanism, we drop the context and simple deal with gimple sequences. This patch provides a temporary solution for ranger. With this patch Ranger now provides a fold_stmt() routine in which we store the block the stmt is in privately, call fold_stmt, and then clear the block.   When range_of_expr is called with no context, it now checks to see if the private block is present, and grabs the value out of the on-entry cache for that block if it has one, otherwise defaults to the global value.    This is completely safe (as long as we have the block correctly marked) because the query for the on-entry cache is read-only, so no additional lookups are done.  The block is only ever set just before a fold_stmt call, and then cleared upon return. The on-entry cache works much like the "current value" vector in EVRP, and provides the value for anything which has been queried already and is not defined in this block.  If it is not defined in this block, then the global value will already be the most up-to-date.   ranger vrp first tries to simplify the stmt with ranges, which means it will query all the ranges used by the stmt.  That means they will all be up to date in the cache. Then when we invoke ranger->fold_stmt() , and the on-entry cache will a have all the needed values. ::fold_stmt is called with the block set, and folding works exactly as we expect. I considered caching the stmt privately instead of the block, and although that would also work, I think its best at this point to avoid an active query in fold_stmt in case someone wants to call it from an "unsafe" place.    There are none of those at this point, but just in case :-) I think there is a better long term solution where if we can integrate a context with the gimple folder and other simplifications, then we should be able to unify a lot of the folding and simplification code.   Most of the code in class simply_using_ranges can probably be unified with gimple_simplification and match.pd patterns,  we can end the segregation of constant vs range folding into a single code-base, and bring a lot of the fold_using_range/range-ops work into gimple-fold as well.   It seems worthwhile to have a single fold() and simplify() entry point as much as possible, and it seems doable.  Thats a discussion we can have later for next stage 1. food for thought anyway :-) Bootstraps on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From fc4076752067fb400b43adbd629081df658da246 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Mon, 1 Nov 2021 13:32:11 -0400 Subject: [PATCH 1/6] Provide some context to folding via ranger. Provide an internal mechanism to supply context to range_of_expr for calls to ::fold_stmt. * gimple-range.cc (gimple_ranger::gimple_ranger): Initialize current_bb. (gimple_ranger::range_of_expr): Pick up range_on_entry when there is no explcit context and current_bb is set. (gimple_ranger::fold_stmt): New. * gimple-range.h (current_bb, fold_stmt): New. * tree-vrp.c (rvrp_folder::fold_stmt): Call ranger's fold_stmt. --- gcc/gimple-range.cc | 28 +++++++++++++++++++++++++++- gcc/gimple-range.h | 2 ++ gcc/tree-vrp.c | 2 +- 3 files changed, 30 insertions(+), 2 deletions(-) diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index 2c9715a6f2c..e1177b1c5e8 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -34,11 +34,13 @@ along with GCC; see the file COPYING3. If not see #include "cfgloop.h" #include "tree-scalar-evolution.h" #include "gimple-range.h" +#include "gimple-fold.h" gimple_ranger::gimple_ranger () : non_executable_edge_flag (cfun), m_cache (non_executable_edge_flag), - tracer ("") + tracer (""), + current_bb (NULL) { // If the cache has a relation oracle, use it. m_oracle = m_cache.oracle (); @@ -82,8 +84,19 @@ gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt) // If there is no statement, just get the global value. if (!stmt) { + int_range_max tmp; if (!m_cache.get_global_range (r, expr)) r = gimple_range_global (expr); + // Pick up implied context information from the on-entry cache + // if current_bb is set. + if (current_bb && m_cache.block_range (tmp, current_bb, expr)) + { + r.intersect (tmp); + char str[80]; + sprintf (str, "picked up range from bb %d\n",current_bb->index); + if (idx) + tracer.print (idx, str); + } } // For a debug stmt, pick the best value currently available, do not // trigger new value calculations. PR 100781. @@ -295,6 +308,19 @@ gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) return res; } +// This routine will invoke the gimple fold_stmt routine, providing context to +// range_of_expr calls via an private interal API. + +bool +gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree)) +{ + gimple *stmt = gsi_stmt (*gsi); + current_bb = gimple_bb (stmt); + bool ret = ::fold_stmt (gsi, valueize); + current_bb = NULL; + return ret; +} + // This routine will export whatever global ranges are known to GCC // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields. diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index 0713af40fcd..615496ec9b8 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -58,10 +58,12 @@ public: void debug (); void dump_bb (FILE *f, basic_block bb); auto_edge_flag non_executable_edge_flag; + bool fold_stmt (gimple_stmt_iterator *gsi, tree (*) (tree)); protected: bool fold_range_internal (irange &r, gimple *s, tree name); ranger_cache m_cache; range_tracer tracer; + basic_block current_bb; }; /* Create a new ranger instance and associate it with a function. diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index dc3e250537a..5380508a9ec 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -4323,7 +4323,7 @@ public: { if (m_simplifier.simplify (gsi)) return true; - return ::fold_stmt (gsi, follow_single_use_edges); + return m_ranger->fold_stmt (gsi, follow_single_use_edges); } private: -- 2.17.2