From patchwork Wed Mar 29 17:22:27 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 67095 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 E3F1C385841C for ; Wed, 29 Mar 2023 17:23:01 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E3F1C385841C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1680110581; bh=1+/8Y74QsGiv8x5f7ZJBUBWSS0u2lQAN0WEYYO2Qbhs=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=k7cBEFdkZLnbPbIK95/iJOM5zMUrZFGbRV3Pn9TeZ7vsPXx2Xxqd/erxVE2th8BPi ys/+AST+iB1DwhEK6aFE+sJdydZfqVEnxJBsKK+FgJi9t5QgtF7vrwT35fdnFIacri SlvOmopPPUlHejgvQPUkv1aSEuCeybJCPpOr2uGs= 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 612E63858D1E for ; Wed, 29 Mar 2023 17:22:32 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 612E63858D1E 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-412-p94jxQWxNo-zTw4p_Mfqxw-1; Wed, 29 Mar 2023 13:22:31 -0400 X-MC-Unique: p94jxQWxNo-zTw4p_Mfqxw-1 Received: by mail-qv1-f69.google.com with SMTP id v8-20020a0ccd88000000b005c1927d1609so6877776qvm.12 for ; Wed, 29 Mar 2023 10:22:30 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1680110549; h=subject:from:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=QCC1upGmlwnF3rDiyapAhMZqm5++HWlyTocqsSw05WU=; b=d6pX9b1gzN9nI2574F0d41dGoKtUVZ+15wDZhtBfhKvGLHkOwuRY/RP3T4986t4xBb vWdoqK/MY5HvM1GBWDxZIQ27yTOj9uFtveN3krzlepfJ4CMH+1Qua9XGV4OdNUOH/Ouk EE8SNTW/3SYQr4XDz4frwNA5ZD2Fr7fwIlycg/xA3xiY3QEVBbcrzNcXK+GqbltvwrhN DI7DjeDD1628NHkh6gJxpCwtdvMTuz6EEBVFKKagPC+j+4MKMtEUJvc23u08d6A0OBEV FyArg2FT4T63HcttA5KJCqog6HfDWG1LZzahPqHzO9c1YVta5jttj+tUX5dJAByPIuin Mx7w== X-Gm-Message-State: AAQBX9fAOMgOqX6zx4ot27/3jf+EGzwzmZ1GfnvmQ10OI2SMtvQKjyDe rvW4NCn4c59ltS/dC7+Sdsa+272u/GAoSkyUiRZ6eyUZoZnHkpAoxtNrIHmXxX+iGrpRfzuDk/W Wm2sErvw+rd6oA5+Togea7pNlu6pal5U4oZXYIzjr6phQFDBQJOVPcYNdO/zglVDX9yAyzR+JGw LHew== X-Received: by 2002:a05:6214:1d26:b0:5a3:cbc6:8145 with SMTP id f6-20020a0562141d2600b005a3cbc68145mr35806859qvd.19.1680110549523; Wed, 29 Mar 2023 10:22:29 -0700 (PDT) X-Google-Smtp-Source: AKy350YPmSE0BCduWE5YFgZWpDYIduelx+355E94whwHwzh4tr0TR1kZ8VaUOGZoDpOuP4qp+t8l+g== X-Received: by 2002:a05:6214:1d26:b0:5a3:cbc6:8145 with SMTP id f6-20020a0562141d2600b005a3cbc68145mr35806814qvd.19.1680110549063; Wed, 29 Mar 2023 10:22:29 -0700 (PDT) Received: from ?IPV6:2607:fea8:a263:f600::759b? ([2607:fea8:a263:f600::759b]) by smtp.gmail.com with ESMTPSA id cn5-20020ad44a65000000b005dd8b9345e1sm4753323qvb.121.2023.03.29.10.22.28 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 29 Mar 2023 10:22:28 -0700 (PDT) Message-ID: <54bb3bc9-e0c1-b5ab-4447-5908b09fd19f@redhat.com> Date: Wed, 29 Mar 2023 13:22:27 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.8.0 To: gcc-patches , Jakub Jelinek , Richard Biener , "hernandez, aldy" Subject: recomputation and PR 109154 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-10.2 required=5.0 tests=BAYES_00, BODY_8BITS, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_NUMSUBJECT, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, 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+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" The patch, or a slight variation (attached), in the PR allows us to generate better ranges be recomputing longer instruction sequences on outgoing edges. This in fact also fixes XPASS: gcc.dg/Walloca-13.c  (test for bogus messages, line 11)   [local count: 1073741824]:   _1 = p_5(D) - q_6(D);   _2 = _1 /[ex] 4;   n_7 = (long unsigned int) _2;   _11 = (long unsigned int) _1;   if (_11 <= 396)     goto ; [33.00%]   else     goto ; [67.00%]   [local count: 354334800]:   _3 = __builtin_alloca (n_7); Where _2 was recomputed before, but n_7 was not.  Now it is, and we correctly do not issue the warning any more.  awesome., however, as seems to be the case often, better ranges result in, I now get: FAIL: 23_containers/vector/bool/allocator/copy.cc (test for excess errors) because we now generate: /opt/notnfs/amacleod/master/build/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/stl_algobase.h:437: warning: ‘void* __builtin_memmove(void*, const void*, long unsigned int)’ writing between 9 and 9223372036854775807 bytes into a region of size 8 overflows the destination [-Wstringop-overflow=]  I see:  ....     _216 = operator new (8); _216 : [irange] long unsigned int * [1, +INF]   ......     [local count: 86938296]:     D.245552 ={v} {CLOBBER(eol)};     _74 = v1.D.217578._M_impl.D.217043._M_start.D.58619._M_p;     _638 = (long int) _74;     _261 = -_638;     _383 = (long unsigned int) _261;     if (_638 < -8)       goto ; [90.00%]     else       goto ; [10.00%] _261 : [irange] long int [-9223372036854775807, +INF] _383 : [irange] long unsigned int [0, 9223372036854775807][9223372036854775809, +INF] 8->12  (T) _74 :        [irange] _Bit_type * [1, +INF] 8->12  (T) _261 :       [irange] long int [9, +INF] NONZERO 0x7fffffffffffffff 8->12  (T) _383 :       [irange] long unsigned int [9, 9223372036854775807] NONZERO 0x7fffffffffffffff 8->12  (T) _638 :       [irange] long int [-INF, -9] =========== BB 12 ============ _74     [irange] _Bit_type * [9223372036854775808, 18446744073709551607] _383    [irange] long unsigned int [9, 9223372036854775807] NONZERO 0x7fffffffffffffff     [local count: 78244465]:     __builtin_memmove (_216, _74, _383); The change is that we now recompute _383 which we didnt before. so we are seeing memmove being called on what is effectively: memmove (operator new (8), _74, [9, 9223372036854775807]) And thus the warning. IS this one of the warnings that has been causing issues?  and now Im triggering it again? Back at fixup_cfg3 time, it looks like:  _261 = __last$D58797$_M_p_245 - _247;   _262 = _261 > 8;   _263 = (long int) _262;   _264 = __builtin_expect (_263, 1);   if (_264 != 0)     goto ; [90.00%]   else     goto ; [10.00%] ..................   [local count: 78244465]:   _265 = (long unsigned int) _261;   __builtin_memmove (_246, _247, _265); So the builtin expect certainly implies it is expecting to have a value > 8 Early on the code looks like: _1 = __last_10(D) - __first_11(D);   _Num_12 = _1 /[ex] 8;   _2 = _Num_12 > 1;   _3 = (long int) _2;   _4 = __builtin_expect (_3, 1);   if (_4 != 0)     goto ; [INV]   else     goto ; [INV]   :   _Num.28_5 = (long unsigned int) _Num_12;   _6 = _Num.28_5 * 8;   __builtin_memmove (__result_14(D), __first_11(D), _6); SO it does still do basically the same thing. Im not sure whether this is pointing out something real or another false positive... Andrew commit 358d0ca44faf2e20fbacd0f74386308b5ca52cd4 Author: Andrew MacLeod Date: Tue Mar 28 12:16:34 2023 -0400 Add recursive GORI recompuations with a depth limit. diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index 6e8dfa85ca8..5f4313b27dd 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -1308,7 +1308,7 @@ gori_compute::compute_operand1_and_operand2_range (vrange &r, // direct dependent is exported, it may also change the computed value of NAME. bool -gori_compute::may_recompute_p (tree name, basic_block bb) +gori_compute::may_recompute_p (tree name, basic_block bb, int depth) { tree dep1 = depend1 (name); tree dep2 = depend2 (name); @@ -1322,22 +1322,36 @@ gori_compute::may_recompute_p (tree name, basic_block bb) if (is_a (s) || gimple_has_side_effects (s)) return false; - // If edge is specified, check if NAME can be recalculated on that edge. - if (bb) - return ((is_export_p (dep1, bb)) - || (dep2 && is_export_p (dep2, bb))); + if (!dep2) + { + // -1 indicates a default param, convert it to the real default. + if (depth == -1) + { + depth = (int)param_ranger_recompute_depth; + gcc_checking_assert (depth >= 1); + } - return (is_export_p (dep1)) || (dep2 && is_export_p (dep2)); + bool res = (bb ? is_export_p (dep1, bb) : is_export_p (dep1)); + if (res || depth <= 1) + return res; + // Check another level of recomputation. + return may_recompute_p (dep1, bb, --depth); + } + // Two dependencies terminate the depth of the search. + if (bb) + return is_export_p (dep1, bb) || is_export_p (dep2, bb); + else + return is_export_p (dep1) || is_export_p (dep2); } // Return TRUE if NAME can be recomputed on edge E. If any direct dependent // is exported on edge E, it may change the computed value of NAME. bool -gori_compute::may_recompute_p (tree name, edge e) +gori_compute::may_recompute_p (tree name, edge e, int depth) { gcc_checking_assert (e); - return may_recompute_p (name, e->src); + return may_recompute_p (name, e->src, depth); } diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h index 0fc90ec8a18..3ea4b45595b 100644 --- a/gcc/gimple-range-gori.h +++ b/gcc/gimple-range-gori.h @@ -172,8 +172,8 @@ private: bool refine_using_relation (tree op1, vrange &op1_range, tree op2, vrange &op2_range, fur_source &src, relation_kind k); - bool may_recompute_p (tree name, edge e); - bool may_recompute_p (tree name, basic_block bb = NULL); + bool may_recompute_p (tree name, edge e, int depth = -1); + bool may_recompute_p (tree name, basic_block bb = NULL, int depth = -1); bool compute_operand_range_switch (vrange &r, gswitch *s, const vrange &lhs, tree name, fur_source &src); bool compute_operand1_range (vrange &r, gimple_range_op_handler &handler, diff --git a/gcc/params.opt b/gcc/params.opt index 2329d150ef0..b2ec436546c 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -900,6 +900,11 @@ Common Joined UInteger Var(param_ranger_logical_depth) Init(6) IntegerRange(1, 9 Maximum depth of logical expression evaluation ranger will look through when evaluating outgoing edge ranges. +-param=ranger-recompute-depth= +Common Joined UInteger Var(param_ranger_recompute_depth) Init(5) IntegerRange(1, 100) Param Optimization +Maximum depth of instruction chains to consider for recomputation in the +outgoing range calculator. + -param=relation-block-limit= Common Joined UInteger Var(param_relation_block_limit) Init(200) IntegerRange(0, 9999) Param Optimization Maximum number of relations the oracle will register in a basic block.