[4.5] Doloop improvement patches, 0/7

[Bernd Schmidt]

I'll be sending out, as replies to this mail, a series of patches that
improves the loop-iv machinery so that we generate more hardware loops.
 Most of them change the function simplify_using_initial_values, which
is used when we compute the number of iterations (both an exact value
and an upper bound), and when we try to prove that a loop is not infinite.

To summarize what this function is doing, let's start with a code example:
    R6 = [memory];
    CC = R6 > 0;
    IF !CC jump over the loop;
  loop starts here:
    decrement R6 and branch if not zero.

We'd like to know the number of iterations (to begin with we only know
the exit test involving R6), so we start from the top of the loop and
scan through the insns backwards to find more information.  We'll
eventually conclude that R6 was loaded from memory and there's nothing
we can do.  However, to use a hardware loop on the Blackfin, we also
need to know that R6 isn't zero, so we start with the condition "R6 !=
0" and scan backwards, trying to prove that it is true.  Here, the
conditional branch is helpful and we can in fact prove that the
condition is always true when entering the loop.

The following patches incrementally improve this analysis so that it is
able to deal with more complex cases, such as e.g.

1.
    R7 = R6;
    CC = R7 > 0;
    IF !CC jump over the loop;
  loop starts here:
    decrement R6 and branch if not zero.

2.
    CC = R7 > 0;
    IF !CC jump over the loop;
    R6 = R7;
  loop starts here:
    decrement R6 and branch if not zero.

I've bootstrapped the entire series on x86_64-pc-linux-gnu; the
regression test produced the following FAILs, all of which appear to be
unrelated (most of them appear in gcc-testresults submissions):

FAIL: gcc.dg/cpp/direct2s.c -fno-show-column (test for excess errors)
FAIL: gcc.dg/tree-prof/bb-reorg.c compilation,  -fprofile-use -D_PROFILE_USE
FAIL: gcc.dg/tree-prof/pr34999.c compilation,  -fprofile-use -D_PROFILE_USE
FAIL: gcc.target/i386/avx-vmovntdq-256-1.c (test for excess errors)
FAIL: gcc.target/i386/avx-vmovntpd-256-1.c (test for excess errors)
FAIL: gcc.target/i386/avx-vmovntps-256-1.c (test for excess errors)
FAIL: objc/execute/forward-1.m execution,  -O0 -fgnu-runtime
FAIL: objc/execute/forward-1.m execution,  -O1 -fgnu-runtime
FAIL: objc/execute/forward-1.m execution,  -O2 -fgnu-runtime
FAIL: objc/execute/forward-1.m execution,  -O3 -fomit-frame-pointer
-fgnu-runtime
FAIL: objc/execute/forward-1.m execution,  -O3 -fomit-frame-pointer
-funroll-loops -fgnu-runtime
FAIL: objc/execute/forward-1.m execution,  -O3 -fomit-frame-pointer
-funroll-all-loops -finline-functions -fgnu-runtime
FAIL: objc/execute/forward-1.m execution,  -O3 -g -fgnu-runtime
FAIL: objc/execute/forward-1.m execution,  -Os -fgnu-runtime
FAIL: libmudflap.c++/pass41-frag.cxx execution test
FAIL: libmudflap.c++/pass41-frag.cxx (-static) execution test
FAIL: libmudflap.c++/pass41-frag.cxx (-O2) execution test
FAIL: libmudflap.c++/pass41-frag.cxx (-O3) execution test

The individual patches (in slightly different shape) have been
regression tested in our 4.3-based Blackfin tree.  If only parts of this
series are approved I'll run tests on the subset.


Bernd
-- 
This footer brought to you by insane German lawmakers.
Analog Devices GmbH      Wilhelm-Wagenfeld-Str. 6      80807 Muenchen
Sitz der Gesellschaft Muenchen, Registergericht Muenchen HRB 40368
Geschaeftsfuehrer Thomas Wessel, William A. Martin, Margaret Seif

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: altered-assignment.diff
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20090305/36d439e5/attachment.ksh>