From patchwork Thu May 7 16:00:54 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 1285468 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org 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@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=adacore.com 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 ozlabs.org (Postfix) with ESMTPS id 49Hyy6290Lz9sVb for ; Fri, 8 May 2020 02:04:43 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B675E3870840; Thu, 7 May 2020 16:01:15 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from rock.gnat.com (rock.gnat.com [IPv6:2620:20:4000:0:a9e:1ff:fe9b:1d1]) by sourceware.org (Postfix) with ESMTP id CF37B386F46B for ; Thu, 7 May 2020 16:01:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org CF37B386F46B Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=adacore.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=oliva@adacore.com Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id 95D851174DC; Thu, 7 May 2020 12:01:03 -0400 (EDT) X-Virus-Scanned: Debian amavisd-new at gnat.com Received: from rock.gnat.com ([127.0.0.1]) by localhost (rock.gnat.com [127.0.0.1]) (amavisd-new, port 10024) with LMTP id uwnxS7mFPhi1; Thu, 7 May 2020 12:01:03 -0400 (EDT) Received: from free.home (tron.gnat.com [IPv6:2620:20:4000:0:46a8:42ff:fe0e:e294]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by rock.gnat.com (Postfix) with ESMTPS id C11D41174D9; Thu, 7 May 2020 12:01:01 -0400 (EDT) Received: from livre.home (livre.home [172.31.160.2]) by free.home (8.15.2/8.15.2) with ESMTPS id 047G0s1b029348 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 7 May 2020 13:00:54 -0300 From: Alexandre Oliva To: gcc-patches@gcc.gnu.org Subject: avoid infinite loops in rpo fre Organization: Free thinker, does not speak for AdaCore Date: Thu, 07 May 2020 13:00:54 -0300 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux) MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 X-Spam-Status: No, score=-16.5 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_STATUS, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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: , Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" gnat.dg/opt83.adb compiled with -O2+ would enter an infinite loop with memory allocation within fre. I don't think there is anything Ada-specific in the bug, but the exact inlining and loop unrolling circumstances needed to trigger the bug are quite fragile, so I didn't try very hard to translate it to C. The problem comes about while attempting to eliminate the last of the following stmts, generated for 'R (0) := F;': A78b_144 = MEM [(struct opt83__e &)_41][0]{lb: _46 sz: 16}._tag; MEM [(struct opt83__e &)_41][0]{lb: _46 sz: 16} = f; MEM [(struct opt83__e &)_41][0]{lb: _46 sz: 16}._tag = A78b_144; valueize_refs_1 takes a sequence of vn_reference_op_s with _41 in it, and when it gets to that op, vn_valueize = rpo_vn_valueize replaces _41 with _47, defined in the previous block as: _47 = &(*_41)[0]{lb: _46 sz: 16}; _47 is the first argument passed to the function synthesized to copy F to the first element of array R, after checking that their addresses do not compare equal. There is another earlier def in the Value Numbering set associated with _41, namely: _164 = &MEM[(struct ALLOC *)_163].ARRAY; _163 is the newly-allocated storage for the 0..4 array. Unfortunately the logic in rpo_vn_valueize selects the former, and then we add the _47 definition in _41's place in the op sequence. Problem is _41 is part of the expression, and thus of the expansion, so eventually we reach it and replace it again, and again, and at every cycle we add more ops than we remove, so the sequence grows unbounded. Limiting the selection of alternate defs for the value to those that dominate the def we're replacing should be enough to avoid the problem, since we'd only perform replacements "up" the CFG. Changing the BB context for the selection of the value equivalence to that of the name we're replacing, rather than that of the expression in which we're replacing it, seems to be close enough. It does solve the problem without any codegen changes in a GCC bootstrap, despite a few differences in eliminate_avail. Regstrapped on x86_64-linux-gnu. Ok to install? As I prepare to post this, it occurs to me that maybe, instead of using vn_context_bb for a default NAME like before, we should abandon the attempt to substitute it, lest we might run into the same kind of infinite loop in for e.g. _41(D). WDYT? for gcc/ChangeLog * tree-ssa-sccvn.c (rpo_vn_valueize): Take the BB context from NAME. for gcc/testsuite/ChangeLog * gnat.dg/opt83.adb: New. --- gcc/testsuite/gnat.dg/opt83.adb | 33 +++++++++++++++++++++++++++++++++ gcc/tree-ssa-sccvn.c | 7 ++++++- 2 files changed, 39 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gnat.dg/opt83.adb diff --git a/gcc/testsuite/gnat.dg/opt83.adb b/gcc/testsuite/gnat.dg/opt83.adb new file mode 100644 index 00000000..7418520 --- /dev/null +++ b/gcc/testsuite/gnat.dg/opt83.adb @@ -0,0 +1,33 @@ +-- { dg-do compile } +-- { dg-options "-O2" } + +-- rpo fre3 used to loop indefinitely replacing _2 with _8 and back, +-- given MEM[(struct test__e &)_2][0]{lb: _7 sz: 16}._tag = A23s_29; +-- and an earlier _8 = &*_2[0]{lb: _7 sz: 16}. + +procedure Opt83 is + + type E is tagged record + I : Natural := 0; + end record; + + type A is array (Natural range <>) of aliased E; + + F : E; + + R : access A; + + procedure N is + begin + if R = null then + R := new A (0 .. 4); + end if; + end N; + +begin + + N; + + R (0) := F; + +end Opt83; diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c index 8a4af91..9008724 100644 --- a/gcc/tree-ssa-sccvn.c +++ b/gcc/tree-ssa-sccvn.c @@ -6790,9 +6790,14 @@ rpo_vn_valueize (tree name) { if (TREE_CODE (tem) != SSA_NAME) return tem; + basic_block bb = vn_context_bb; + /* Avoid replacing name with anything whose definition + could refer back to name. */ + if (! SSA_NAME_IS_DEFAULT_DEF (name)) + bb = gimple_bb (SSA_NAME_DEF_STMT (name)); /* For all values we only valueize to an available leader which means we can use SSA name info without restriction. */ - tem = rpo_avail->eliminate_avail (vn_context_bb, tem); + tem = rpo_avail->eliminate_avail (bb, tem); if (tem) return tem; }