From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [63.128.21.124]) by sourceware.org (Postfix) with ESMTP id E30A33954457 for ; Wed, 2 Dec 2020 00:26:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org E30A33954457 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-86-mZtFyJnjMH-GZ3s4LYRcBA-1; Tue, 01 Dec 2020 19:25:59 -0500 X-MC-Unique: mZtFyJnjMH-GZ3s4LYRcBA-1 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.phx2.redhat.com [10.5.11.22]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id EB0101842156; Wed, 2 Dec 2020 00:25:57 +0000 (UTC) Received: from localhost.localdomain (ovpn-112-145.phx2.redhat.com [10.3.112.145]) by smtp.corp.redhat.com (Postfix) with ESMTP id 22B4710013BD; Wed, 2 Dec 2020 00:25:57 +0000 (UTC) Subject: Re: [00/23] Make fwprop use an on-the-side RTL SSA representation To: Michael Matz Cc: Jeff Law via Gcc-patches , richard.sandiford@arm.com References: <97fbb734-bd83-1d1b-6b80-372f2743d76d@redhat.com> From: Jeff Law Message-ID: <28f7d03c-9dfa-ca68-8ded-0b6cc12ac846@redhat.com> Date: Tue, 1 Dec 2020 17:25:56 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.4.0 MIME-Version: 1.0 In-Reply-To: X-Scanned-By: MIMEDefang 2.84 on 10.5.11.22 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Content-Language: en-US X-Spam-Status: No, score=-6.2 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, 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: , X-List-Received-Date: Wed, 02 Dec 2020 00:26:05 -0000 On 11/30/20 5:03 PM, Michael Matz wrote: > Hello, > > On Mon, 30 Nov 2020, Jeff Law wrote: > >>>> So, then let's start with one of >>>> the prime examples of SSA deconstruction problems, the lost swap, and how >>>> it comes to be: we start with a swap: >>>> >>>> x = ..., y = ... >>>> if (cond) >>>> tmp=x, x=y, y=tmp >>>> >>>> (1) into SSA: >>>> >>>> x0 = ..., y0 = ... >>>> if (cond) >>>> tmp = x0, x1=y0, y1=tmp; >>>> x2 = PHI(x0,x1), y2 = PHI(y0,y1) >>>> >>>> (2) copy-prop: >>>> >>>> x0 = ..., y0 = ... >>>> if (cond) >>>> ; >>>> x2 = PHI(x0,y0), y2 = PHI(y0,x0) >>> So the point is that this isn't what the RTL would look like even >>> when using RTL SSA. Putting y0 in x2 PHI and x0 in the y2 PHI is >>> representationally invalid. >>> >>> Like I say, this isn't a “native” SSA form: it's just using SSA >>> constructs to represent dataflow in normal RTL. >> It appears that the PHI arguments have to be different instances of the >> result.  So the case above can't happen, which helps, but I'm not sure >> it's necessarily sufficient to avoid all the problems in this space. >> IIRC you can get into a similar scenario by transformations that result >> in overlapping lifetimes for different instances of the same object.  >> They didn't necessarily overlap when the SSA form was created, but may >> after things like CSE or copy propagation. > I think the reasoning why this can't (or should not) happen is the > following: if different instances of the same objects (say, one before, > one after a modification) exist, they must necessarily be stored in > different pseudos (otherwise the RTL transformation itself was already > invalid), and that causes them to be invalid operands of the same PHI > node. Ala: > > input: > > regA = .... /1 > use1(regA) /2 > regA += ... /3 > use2(regA) /4 > > let's try creating different instances of regA (from point 2 and 4) that > overlap, e.g. by swapping insns 2 and 3. We _have_ to rename regA from > insn 3 into a new pseudo, otherwise the uses of 2 and 4 can't be > differentiated anymore, so: > > regA = .... /1 > regA' = regA > regA' += .... /3' > use1(regA) /2 > use2(regA') /4' > > So if Richards model constrains the pseudo PHI nodes such that regA and > regA' can't be operands of one, that might solve the issue, as both the > lost copy and the swap problem need overlaps of different values to occur. Right.  I was thinking about cases where something like CSE on this form transforms the RHS of some operation into an instance of a pseudo.  That insn is now a copy and we propagate the RHS into the uses of the LHS.  That extends the lifetime of the pseudo's instance.  The question is whether or not those actions either create a lost copy/swap problem or not within the on-the-side SSA representation and whether or not there could be implications if that happens. > >> The fact that passes don't directly manipulate the PHIs definitely helps >> as well.  But I've still got some reading to do in this space to refresh >> my memory of the issues. > AFAIU Richards approach is more comparable to factored def-use chains than > to real SSA, which might indeed have no issues, though I then think the > problem moves into keeping _those_ consistent with the real instruction > stream as it changes. To some degree, the change in model moves where we have to tackle these issues.  Instead of tackling them in the out-of-ssa phase, we instead have to think more about them in the analysis/optimization phases.  We already do that to some degree in the gimple SSA representation (for things like SSA_NAMEs associated with abnormal edges). jeff