This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Optimising std::find on x86 and PPC
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: Daniel Berlin <dberlin at dberlin dot org>
- Cc: Gabriel Dos Reis <gdr at integrable-solutions dot net>,Paolo Carlini <pcarlini at suse dot de>,Theodore Papadopoulo <Theodore dot Papadopoulo at sophia dot inria dot fr>,Chris Jefferson <caj at cs dot york dot ac dot uk>, gcc at gcc dot gnu dot org,libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Tue, 14 Dec 2004 23:16:50 +0100
- Subject: Re: Optimising std::find on x86 and PPC
- References: <200412141909.iBEJ9XZ7027097@mururoa.inria.fr> <41BF4753.3070803@suse.de> <41BF4E0F.5020703@suse.de> <m3sm68zhga.fsf@uniton.integrable-solutions.net> <Pine.LNX.4.60.0412141651111.24937@dberlin.org>
Hello,
> Just so others have context, the trivially broken loop that Paolo had
> sent to me looks like this:
>
> int*
> check(int* a, int* b)
> {
> for (; a < b; ++a)
> if (*a == 1)
> return a;
> return a;
> }
>
>
> This was unrolled with 3.3.3, but 4.0 (and apparently 3.4) claims the
> number of iterations is not runtime computable.
>
> This is clearly wrong, as there are no stores in the entire function, so b
> couldn't *possible* change, no matter what we do.
as Andrew noted, the problem is that the loop actually looks like
for (i = a; i < b; i += 4)
something;
At rtl level we do not have sufficient information to determine the
number of iterations of this loop precisely at runtime -- we cannot
determine whether it is not infinite. This however should not block
loop unrolling, and should be relatively simple to fix; I will try.
Note however that the fact that 3.3 unrolls this loop very likely means
that 3.3 is buggy; I guess that 3.3 would also unroll
for (i = a; i < b; i += 5)
something;
Which would be obviously wrong, unless you are very careful with the way
number of iterations is determined (which 3.3 is not).
Zdenek
Zdenek