From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 5179 invoked by alias); 12 Oct 2004 23:07:58 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 5169 invoked from network); 12 Oct 2004 23:07:57 -0000 Received: from unknown (HELO dberlin.org) (68.164.203.246) by sourceware.org with SMTP; 12 Oct 2004 23:07:57 -0000 Received: from [127.0.0.1] (HELO dberlin.org) by dberlin.org (CommuniGate Pro SMTP 4.2.1) with ESMTP-TLS id 7391299; Tue, 12 Oct 2004 19:07:56 -0400 Date: Tue, 12 Oct 2004 23:10:00 -0000 From: Daniel Berlin To: radkver@atrey.karlin.mff.cuni.cz, gcc-patches@gcc.gnu.org Subject: Re: [patch] for PR 17133 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-SW-Source: 2004-10/txt/msg01057.txt.bz2 Hello, > > with V_MUST_DEFS, the virtual operands no longer represent output > dependence of the statements with them. This causes the original > approach of store motion to fail. > > Example 1: > > do > { > x = ... ; V_MUST_DEF bla_1; > use x ; VUSE bla_1 > x = ... ; V_MUST_DEF bla_2; > } while (something); > > Note that there is no loop phi node for bla, since it is not > live over back edge of loop, so the approach of tree-lim to > check just phi nodes fails miserably. Furthermore there is > no connection between bla_1 and bla_2 in ssa graph, so tree-lim > cannot locate both of them using ssa form. > > Example 2: > > The bug is caused by situation looking like > > do > { > bla_3 = phi (bla_0, bla2); > use x; ; VUSE bla_3 > x = ... ; V_MUST_DEF bla_1; (*) > if (cond) > break; > x = ... ; V_MUST_DEF bla_2; > } while (something); > > Assignment (*) is not noticed by tree-lim, since it is not reachable > from the phi node, which causes misscompilation when store to x is emitted > to the if (cond) break; edge by store motion. > The redesign of store motion in tree-lim is necessary to fix the > problem. There are two possible approaches: > > 1) Use ssa form, but track the names from exits of the loop. > 2) Avoid usage of SSA form for store motion, and use classical > "gather the memory references and optimize those that do not > alias anything else" approach. > > While your analysis is correct, you have missed the most obvious, and correct, approach. That is, to add the information on what the must-def is killing to the v_must_def, and make sure it shows up in immediate uses. This makes the right phi nodes and immediate uses necessary to block these illegal movements appear automatically. > do > { > x = ... ; V_MUST_DEF bla_1; > use x ; VUSE bla_1 > x = ... ; V_MUST_DEF bla_2; > } while (something); > > automatically becomes do { bla_3 = PHI x = ... ; bla_1 = V_MUST_DEF use x ; VUSE bla_1 x = ... ; bla_2 = V_MUST_DEF } And now you know you know exactly the info you wanted. > do > { > bla_3 = phi (bla_0, bla2); > use x; ; VUSE bla_3 > x = ... ; V_MUST_DEF bla_1; (*) > if (cond) > break; > x = ... ; V_MUST_DEF bla_2; > } while (something); > > becomes do { bla_3 = phi (bla_0, bla_2); use x ; VUSE bla_3 x = ... ; bla_1 = V_MUST_DEF if (cond) break; x = ... ; bla_2 = V_MUST_DEF } while (something); Note that bla_3 is now linked to the bla_1 must def through the immediate uses (and bla_2 is linked to bla_1 through immediate uses), so that we know the info we need. I have a patch to add this information to must_defs that was originally going to be submitted to 4.1 (as part of some partial dead code elimination work), but it's ready and waiting, and is a better fix for these problems. I will submit it to 4.0 tomorrow. Note that it automatically fixes PR 17133 without any changes to lim. I'd much rather see us not cripple lim and fix the actual problem, which was that the ssa information wasn't including the stuff necessary for things like this to work. --Dan