This is from Briggs' code quality suite: void vnum_test8(int *data) { int i; int stop = data[3]; int m = data[4]; int n = m; for (i=0; i<stop; i++) { int k = data[2]; data[k] = 2; data[0] = m - n; k = data[1]; m = m + k; n = n + k; } } void vnum_result8(int *data) { int i; int stop = data[3]; for (i=0; i<stop; i++) { int k = data[2]; data[k] = 2; data[0] = 0; } } In the .ivopts dump we have (set_scalar_evolution (scalar = n_2) (scalar_evolution = {m_8, +, k_19}_1)) ) and (set_scalar_evolution (scalar = m_1) (scalar_evolution = {m_8, +, k_19}_1)) ) But we don't eliminate one of these IVs.
Confirmed.
This hasn't been addressed yet in r106784.
This is easy to implement; the question is whether we really want to waste compile time to handle this type of examples that do not seem very likely to appear in practice.
They can happen due to macro expansion or C++ template inlining. I wonder if PRE for scalar-evolutions would be useful ;)
Subject: Re: IVs with the same evolution not eliminated > They can happen due to macro expansion or C++ template inlining. And do they? > I wonder if PRE for scalar-evolutions would be useful ;) I would guess that this would be unnecessarily expensive. The only place where scev should give you some useful information should be for induction variables inside loops, in which case you can simply pass over the loop phi nodes and merge the variables with the same evolution.
> > They can happen due to macro expansion or C++ template inlining. > And do they? If they can, they will do. Will this regularly happen? I think no.
It would be more interesting to measure than think ;-) My experience is that when it is in Briggs' test suite, it usually also happens in actually useful code. But, only the numbers will tell :-) Zdenek is right, it's just a matter of comparing the evolutions of loop PHI nodes. Instrumenting the compiler to count how often this happens is half the work of implementing the optimization if it turns out to be useful.
Comparing the IVs themselves take no time, now figuring out which one are equal to which set could take some time, at max O(n^2) time. Now n is going to be small for most cases anyways.
Actually, it's not really expensive at all. It's certainly not N^2. The new SCC value numberer for PRE i'm working on gets this case right (and this is in fact, one of the advantages of SCC based value numbering). You could also do it with an RPO iteration algorithm, which is what open64 does, but that will iterate over defs/uses in changing blocks repeatedly instead of only iterating over the members of the SCC. For this case, i get: Value numbers: n_3 = m_2 n_9 = m_8 n_21 = m_20 Which is what you wanted.
Subject: Re: IVs with the same evolution not eliminated > The new SCC value numberer for PRE i'm working on gets this case right (and > this is in fact, one of the advantages of SCC based value numbering). Is the SCC-VN patch I posted long ago still of some use to you, or are you writing something new from scratch? (See http://gcc.gnu.org/ml/gcc-patches/2004-01/msg00211.html)
Subject: Re: IVs with the same evolution not eliminated > ------- Comment #10 from stevenb dot gcc at gmail dot com 2006-04-08 21:13 ------- > Subject: Re: IVs with the same evolution not eliminated > > > The new SCC value numberer for PRE i'm working on gets this case right (and > > this is in fact, one of the advantages of SCC based value numbering). > > Is the SCC-VN patch I posted long ago still of some use to you, or are > you writing something new from scratch? I ended up rewriting it from scratch, for other reasons. In particular 1. I keep separate hash tables for unary, binary, references, and phi expressions, each with their own structure This is because you really want valuized structures in the hash table. Your implementation will get the wrong answers during optimistic lookup at times, because the value representative for a phi argument can change and will get hashed to the wrong value. 2. I keep track of what expressions simplified to, and whether they have constants in the simplified expression. This enables much more simplification that simply storing the value number name. In particular, in something like int main(int argc) { int a; int b; int c; int d; a = argc + 4; b = argc + 8; c = a & b; d = a + 4; return c + d; } We will prove that d and b have the same value. BTW, you missed the part of the thesis where he explains that phi nodes in different blocks can't be congruent to each other (this isn't quite true, but it's a much harder property to prove). 3. I needed the structures i made so i could directly transform the results into value handles.
Created attachment 11235 [details] proposed fix This patch fixes the problem, but probably it is a more general optimization fix than the one described in the PR.
I wonder if it helps placing this between cunroll and ivopts... void foo(int n, int m, int stridex, int stridey, int stridex2, int stridey2, double *x, double *y) { for (int k=0; k<m; ++k) for (int j=0; j<n; ++j) for (int i=0; i<2; ++i) x[i + stridex*j + stridex2*k] = y[i + stridey*j + stridey2*k]; } producing better IV selection than what we get now.
Subject: Re: IVs with the same evolution not eliminated > I wonder if it helps placing this between cunroll and ivopts... > > void foo(int n, int m, int stridex, int stridey, int stridex2, int stridey2, > double *x, double *y) > { > for (int k=0; k<m; ++k) > for (int j=0; j<n; ++j) > for (int i=0; i<2; ++i) > x[i + stridex*j + stridex2*k] = y[i + stridey*j + stridey2*k]; > } > > producing better IV selection than what we get now. ivopts do not care (they will recognize that the two array references have the same offsets).
*** Bug 30098 has been marked as a duplicate of this bug. ***
Subject: Bug 19590 Author: spop Date: Thu Jun 21 17:06:05 2007 New Revision: 125925 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=125925 Log: PR tree-optimization/19590 * tree-vrp.c (adjust_range_with_scev): Set the range when the result of scev is a constant. * gcc/testsuite/gcc.dg/tree-ssa/pr19590.c: New. Added: trunk/gcc/testsuite/gcc.dg/tree-ssa/pr19590.c Modified: trunk/gcc/ChangeLog trunk/gcc/tree-vrp.c
Fixed. Note I think the proposed patch attached here will fix PR 32200. That testcase was not fixed the VRP patch. The VRP patch fixes the case where we have IV - IV inside the loop.
Subject: Re: IVs with the same evolution not eliminated > Note I think the proposed patch attached here will fix PR 32200. Nop. Reverting the patch and diffing the assembly code for i686-linux on both codes from PR32200 does not show any change. I'm going to look more closely at PR32200. Sebastian