From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 2522 invoked by alias); 13 Apr 2005 17:11:47 -0000 Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org Received: (qmail 2479 invoked by alias); 13 Apr 2005 17:11:40 -0000 Date: Wed, 13 Apr 2005 17:11:00 -0000 Message-ID: <20050413171140.2478.qmail@sourceware.org> From: "law at redhat dot com" To: gcc-bugs@gcc.gnu.org In-Reply-To: <20040518194300.15524.pinskia@gcc.gnu.org> References: <20040518194300.15524.pinskia@gcc.gnu.org> Reply-To: gcc-bugzilla@gcc.gnu.org Subject: [Bug tree-optimization/15524] [4.0 Regression] jump threading on trees is slow with switch statements with large # of cases X-Bugzilla-Reason: CC X-SW-Source: 2005-04/txt/msg01749.txt.bz2 List-Id: ------- Additional Comments From law at redhat dot com 2005-04-13 17:11 ------- Subject: Re: [4.0 Regression] jump threading on trees is slow with switch statements with large # of cases On Wed, 2005-04-13 at 13:04 +0000, dnovillo at redhat dot com wrote: > ------- Additional Comments From dnovillo at redhat dot com 2005-04-13 13:03 ------- > Subject: Re: [4.0 Regression] jump threading on trees is slow with switch statements with large # of cases > > On Tue, Apr 12, 2005 at 04:55:20PM -0000, law at redhat dot com wrote: > > > That mental model doesn't work right now with the way DOM & the > > jump threader because they are too tightly intertwined. > > > The link that you have still not shown me is why doesn't this > mental model work for the jump threader. That's why I said that > I need to run the threader myself and see why it needs all these > additional crutches. That the model we wont to go to -- but it's certainly not where we are today. Why? Because the jump threader exposes more optimization opportunities for DOM (including constant and copy propagations) and DOM exposes more opportunities for the threader. They are inherently tied together with their current structure. > > If the code has been cleaned up of redundancies, copies > propagated, names have known values and ranges are set, then I > don't see why we would need all the extra baggage. Because threading exposes new opportunities to perform constant and copy propagation and redundancy elimination. > > > The iteration step we see today would turn into a worklist. > > ie, after we thread jumps, we walk through the IL for PHIs > > which represent a copy that can be propagated. > > > Ah, here's something specific I don't follow. Why would you have > these PHIs anymore? If all the arguments were ultimately > equivalent, then the various propagators are bound to have > removed them. If not, that sounds like a bug in them. They are exposed as a result of jump threading. For example we might have something like: BB 3: x3 = PHI (x2 (0), x1 (1), x1 (2)); [ ... ] if (cond) goto X, else goto Y If jump threading manages to determine where the conditional will go when BB3 is reached via BB0, then we'll be able to remove the PHI argument associated with the edge from BB0 to BB3. That in turn exposes a copy propagation opportunity (x3 = x1). Or when we thread a jump we might expose a new redundancy because the dominator graph changed. Whenever we expose a redundancy we also expose a copy propagation opportunity. > > > What's nice about this is the bulk of DOM as we know it today > > disappears along with the expensive iteration in the case when > > jumps are threaded. We just need the right APIs for copy > > propagation and value handles. > > > Again, why? The propagators are supposed to have done this > already. They are all supposed to work in conditional regions. You really don't seem to understand what the threader does and how its actions can expose new optimization opportunities. I might suggest you look very closely at what happens for a test like 20030714-2.c which is derived from real code. As we thread jumps, we expose new redundancy elimination opportunities, which in turn expose new copy propagation opportunities. > > We could still potentially use ASSERT_EXPRs to encode > > information about edge equivalences, though we probably would > > still want the ASSERT_EXPR to appear as statement rather than > > the RHS of a MODIFY_EXPR. > > > Odd, the nice thing about assertions being on the RHS is that you > pin their result to a specific SSA name that you then get to use > at every place naturally dominated by the assertion. > > If you could give me a concrete test case that I could sink my > teeth in, that'd be great. Go back the PR I've referenced twice. jeff -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15524