This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: patch for merging graphite branch (before tuplification)
- From: "Sebastian Pop" <sebpop at gmail dot com>
- To: "Richard Guenther" <richard dot guenther at gmail dot com>
- Cc: "GCC Patches" <gcc-patches at gcc dot gnu dot org>, "Mark Mitchell" <mark at codesourcery dot com>, "Jakub Jelinek" <jakub at redhat dot com>, "David Edelsohn" <edelsohn at gmail dot com>, "Harle, Christophe" <christophe dot harle at amd dot com>, "Tobias Grosser" <grosser at fim dot uni-passau dot de>, "Konrad Trifunovic" <konrad dot trifunovic at gmail dot com>, "Albert Cohen" <Albert dot Cohen at inria dot fr>
- Date: Wed, 30 Jul 2008 10:41:56 -0500
- Subject: Re: patch for merging graphite branch (before tuplification)
- References: <cb9d34b20807251914jb7fb76q4452be18461d7464@mail.gmail.com> <84fc9c000807260228h12552595x17b2a7556d35913b@mail.gmail.com>
On Sat, Jul 26, 2008 at 4:28 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> I miss an overview that helps reviewing the patches. In particular I would like
> you to split it into separate parts with separate ChangeLogs; I am interested
> in seeing the build machinery bits, the testsuite bits and the middle-end pieces
> (that are not graphite.[ch]) posted separately with some short explanation.
-- 1127_build.diff contains the build scripts and makefiles modifications.
* The changes asked by Joseph for checking the version of Cloog,
and for giving an error if Cloog or PPL are not available when
one of the graphite flags is used, are still not implemented.
* The changes for configuring with PPL are not in this patch
either.
-- 1127_testsuite.diff contains the testsuite changes and several testcases.
* gcc/testsuite/gcc.dg/graphite/graphite.exp: New file,
copied from tree-ssa.exp.
* gcc/testsuite/gfortran.dg/graphite/graphite.exp: New,
copied from gfortran.exp.
I've updated the copyright notices for both these files.
-- 1127_middle-end.diff contains the changes needed for adding new
flags, documentation and new functionality needed in graphite.[ch]
Note that after tuplification we do not need the tree-phinodes.c
changes. The most important changes are:
* tree-loop-distribution.c: the code is moved to tree-data-ref.h
* cfgloopmanip.c (update_dominators_in_loop,
create_empty_loop_on_edge): New functions.
* cfghooks.c (update_dominator_information): Split out from
split_edge.
* tree-chrec.c (for_each_scev_op): New iterator over the operands
of a chrec.
* other files: make extern some of the static functions.
Index: gcc/config.in
===================================================================
--- gcc/config.in (.../trunk) (revision 138072)
+++ gcc/config.in (.../branches/graphite) (revision 138161)
@@ -1303,6 +1303,18 @@
#endif
+/* Define if cloog is in use. */
+#ifndef USED_FOR_TARGET
+#undef HAVE_cloog
+#endif
+
+
+/* Define if polylib is in use. */
+#ifndef USED_FOR_TARGET
+#undef HAVE_polylib
+#endif
+
+
/* Define as const if the declaration of iconv() needs const. */
#ifndef USED_FOR_TARGET
#undef ICONV_CONST
Index: gcc/configure.ac
===================================================================
--- gcc/configure.ac (.../trunk) (revision 138072)
+++ gcc/configure.ac (.../branches/graphite) (revision 138161)
@@ -3837,6 +3837,20 @@ fi
AC_ARG_VAR(GMPLIBS,[How to link GMP])
AC_ARG_VAR(GMPINC,[How to find GMP include files])
+AC_ARG_VAR(POLYLIBLIBS,[How to link POLYLIB])
+AC_ARG_VAR(POLYLIBINC,[How to find POLYLIB include files])
+if test "x${POLYLIBLIBS}" != "x" ; then
+ AC_DEFINE(HAVE_polylib, 1, [Define if polylib is in use.])
+fi
+
+AC_ARG_VAR(CLOOGLIBS,[How to link CLOOG])
+AC_ARG_VAR(CLOOGINC,[How to find CLOOG include files])
+if test "x${CLOOGLIBS}" != "x" ; then
+ AC_DEFINE(HAVE_cloog, 1, [Define if cloog is in use.])
+ GRAPHITE=graphite.o
+fi
+AC_SUBST(GRAPHITE)
+
# Configure the subdirectories
# AC_CONFIG_SUBDIRS($subdirs)
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in (.../trunk) (revision 138072)
+++ gcc/Makefile.in (.../branches/graphite) (revision 138161)
@@ -190,6 +190,8 @@ dfp.o-warn = -Wno-error
bitmap.o-warn = -Wno-error
# dominance.c contains a -Wc++compat warning.
dominance.o-warn = -Wno-error
+# graphite.c contains code calling cloog that has problems.
+graphite.o-warn = -Wno-error
# All warnings have to be shut off in stage1 if the compiler used then
# isn't gcc; configure determines that. WARN_CFLAGS will be either
@@ -291,6 +293,14 @@ ZLIBINC = @zlibinc@
GMPLIBS = @GMPLIBS@
GMPINC = @GMPINC@
+# How to find POLYLIB
+POLYLIBLIBS = @POLYLIBLIBS@
+POLYLIBINC = @POLYLIBINC@
+
+# How to find CLOOG
+CLOOGLIBS = @CLOOGLIBS@
+CLOOGINC = @CLOOGINC@
+
CPPLIB = ../libcpp/libcpp.a
CPPINC = -I$(srcdir)/../libcpp/include
@@ -896,7 +906,8 @@ BUILD_LIBDEPS= $(BUILD_LIBIBERTY)
# How to link with both our special library facilities
# and the system's installed libraries.
-LIBS = @LIBS@ $(CPPLIB) $(LIBINTL) $(LIBICONV) $(LIBIBERTY) $(LIBDECNUMBER)
+LIBS = @LIBS@ $(CPPLIB) $(LIBINTL) $(LIBICONV) $(LIBIBERTY) $(LIBDECNUMBER) \
+ $(CLOOGLIBS) $(POLYLIBLIBS)
# Any system libraries needed just for GNAT.
SYSLIBS = @GNAT_LIBEXC@
@@ -925,7 +936,8 @@ BUILD_ERRORS = build/errors.o
# libintl.h will be found in ../intl if we are using the included libintl.
INCLUDES = -I. -I$(@D) -I$(srcdir) -I$(srcdir)/$(@D) \
-I$(srcdir)/../include @INCINTL@ \
- $(CPPINC) $(GMPINC) $(DECNUMINC)
+ $(CPPINC) $(GMPINC) $(DECNUMINC) \
+ $(POLYLIBINC) $(CLOOGINC)
.c.o:
$(CC) -c $(ALL_CFLAGS) $(ALL_CPPFLAGS) $< $(OUTPUT_OPTION)
@@ -1298,7 +1310,7 @@ ALL_HOST_OBJS = $(GCC_OBJS) $(C_OBJS) $(
mips-tfile.o mips-tdump.o \
$(PROTO_OBJS) $(GCOV_OBJS) $(GCOV_DUMP_OBJS)
-BACKEND = main.o @TREEBROWSER@ libbackend.a $(CPPLIB) $(LIBDECNUMBER)
+BACKEND = main.o @TREEBROWSER@ @GRAPHITE@ libbackend.a $(CPPLIB) $(LIBDECNUMBER)
MOSTLYCLEANFILES = insn-flags.h insn-config.h insn-codes.h \
insn-output.c insn-recog.c insn-emit.c insn-extract.c insn-peep.c \
@@ -2323,7 +2335,11 @@ tree-scalar-evolution.o: tree-scalar-evo
tree-data-ref.o: tree-data-ref.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) \
$(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
- $(TREE_DATA_REF_H) $(SCEV_H) tree-pass.h tree-chrec.h langhooks.h
+ $(TREE_DATA_REF_H) $(SCEV_H) tree-pass.h tree-chrec.h langhooks.h graphite.h
+graphite.o: graphite.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
+ $(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) \
+ $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) domwalk.h \
+ $(TREE_DATA_REF_H) $(SCEV_H) tree-pass.h tree-chrec.h graphite.h
tree-vect-analyze.o: tree-vect-analyze.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
$(TM_H) $(GGC_H) $(OPTABS_H) $(TREE_H) $(RECOG_H) $(BASIC_BLOCK_H) \
$(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
Index: configure.ac
===================================================================
--- configure.ac (.../trunk) (revision 138072)
+++ configure.ac (.../branches/graphite) (revision 138161)
@@ -158,7 +158,7 @@ build_tools="build-texinfo build-byacc b
# these libraries are used by various programs built for the host environment
#
-host_libs="intl mmalloc libiberty opcodes bfd readline tcl tk itcl libgui zlib libcpp libdecnumber gmp mpfr"
+host_libs="intl mmalloc libiberty opcodes bfd readline tcl tk itcl libgui zlib libcpp libdecnumber gmp mpfr polylib cloog"
# these tools are built for the host environment
# Note, the powerpc-eabi build depends on sim occurring before gdb in order to
@@ -1302,6 +1302,73 @@ fi
AC_SUBST(gmplibs)
AC_SUBST(gmpinc)
+
+# Check for POLYLIB
+polyliblibs=
+polylibinc=
+
+AC_ARG_WITH(polylib, [ --with-polylib=PATH Specify prefix directory for the installed POLYLIB package
+ Equivalent to --with-polylib-include=PATH/include
+ plus --with-polylib-lib=PATH/lib])
+AC_ARG_WITH(polylib_include, [ --with-polylib-include=PATH Specify directory for installed POLYLIB include files])
+AC_ARG_WITH(polylib_lib, [ --with-polylib-lib=PATH Specify the directory for the installed POLYLIB library])
+
+if test "x$with_polylib" != x; then
+ polyliblibs="-L$with_polylib/lib -lpolylibgmp"
+ polylibinc="-I$with_polylib/include $polylibinc"
+ LIBS="$polyliblibs $LIBS"
+fi
+if test "x$with_polylib_include" != x; then
+ polylibinc="-I$with_polylib_include $polylibinc"
+fi
+if test "x$with_polylib_lib" != x; then
+ polyliblibs="-L$with_polylib_lib -lpolylibgmp"
+ LIBS="$polyliblibs $LIBS"
+fi
+if test "x$with_polylib$with_polylib_include$with_polylib_lib" = x && test -d ${srcdir}/polylib; then
+ polyliblibs='-L$$r/$(HOST_SUBDIR)/polylib/.libs -L$$r/$(HOST_SUBDIR)/polylib/_libs -lpolylibgmp '
+ polylibinc='-I$$r/$(HOST_SUBDIR)/polylib/include -I$$s/polylib/include '
+ LIBS="$polyliblibs $LIBS"
+fi
+
+# Flags needed for POLYLIB
+AC_SUBST(polyliblibs)
+AC_SUBST(polylibinc)
+
+
+# Check for CLOOG
+clooglibs=
+clooginc=
+
+AC_ARG_WITH(cloog, [ --with-cloog=PATH Specify prefix directory for the installed CLOOG package
+ Equivalent to --with-cloog-include=PATH/include
+ plus --with-cloog-lib=PATH/lib])
+AC_ARG_WITH(cloog_include, [ --with-cloog-include=PATH Specify directory for installed CLOOG include files])
+AC_ARG_WITH(cloog_lib, [ --with-cloog-lib=PATH Specify the directory for the installed CLOOG library])
+
+if test "x$with_cloog" != x; then
+ clooglibs="-L$with_cloog/lib -lcloog"
+ clooginc="-I$with_cloog/include"
+ LIBS="$clooglibs $LIBS"
+fi
+ if test "x$with_cloog_include" != x; then
+ clooginc="-I$with_cloog_include"
+fi
+if test "x$with_cloog_lib" != x; then
+ clooglibs="-L$with_cloog_lib -lcloog"
+ LIBS="$clooglibs $LIBS"
+fi
+if test "x$with_cloog$with_cloog_include$with_cloog_lib" = x && test -d ${srcdir}/cloog; then
+ clooglibs='-L$$r/$(HOST_SUBDIR)/cloog/.libs -L$$r/$(HOST_SUBDIR)/cloog/_libs -lcloog '
+ clooginc='-I$$r/$(HOST_SUBDIR)/cloog/include -I$$s/cloog/include '
+ LIBS="$clooglibs $LIBS"
+fi
+
+# Flags needed for CLOOG
+AC_SUBST(clooglibs)
+AC_SUBST(clooginc)
+
+
# By default, C is the only stage 1 language.
stage1_languages=,c,
Index: Makefile.def
===================================================================
--- Makefile.def (.../trunk) (revision 138072)
+++ Makefile.def (.../branches/graphite) (revision 138161)
@@ -68,6 +68,16 @@ host_modules= { module= mpfr; lib_path=.
no_install= true;
host="none-${host_vendor}-${host_os}";
target="none-${host_vendor}-${host_os}"; };
+host_modules= { module= polylib; lib_path=.libs; bootstrap=true;
+ extra_configure_flags='--disable-shared --with-gmp-libs=$$r/$(HOST_SUBDIR)/gmp/.libs --with-gmp-includes=$$r/$(HOST_SUBDIR)/gmp';
+ no_install= true;
+ host="none-${host_vendor}-${host_os}";
+ target="none-${host_vendor}-${host_os}"; };
+host_modules= { module= cloog; lib_path=.libs; bootstrap=true;
+ extra_configure_flags='--disable-shared --with-gmp-library=$$r/$(HOST_SUBDIR)/gmp/.libs --with-gmp-include=$$r/$(HOST_SUBDIR)/gmp --with-polylib-builddir=$$r/$(HOST_SUBDIR)/polylib/ --with-bits=gmp';
+ no_install= true;
+ host="none-${host_vendor}-${host_os}";
+ target="none-${host_vendor}-${host_os}"; };
host_modules= { module= gnuserv; };
host_modules= { module= gold; bootstrap=true; };
host_modules= { module= gprof; };
@@ -294,6 +304,8 @@ dependencies = { module=all-gcc; on=all-
dependencies = { module=all-gcc; on=all-gmp; };
dependencies = { module=all-gcc; on=all-intl; };
dependencies = { module=all-gcc; on=all-mpfr; };
+dependencies = { module=all-gcc; on=all-polylib; };
+dependencies = { module=all-gcc; on=all-cloog; };
dependencies = { module=all-gcc; on=all-build-texinfo; };
dependencies = { module=all-gcc; on=all-build-bison; };
dependencies = { module=all-gcc; on=all-build-byacc; };
@@ -317,6 +329,9 @@ dependencies = { module=all-fixincludes;
dependencies = { module=all-gnattools; on=all-target-libada; };
dependencies = { module=configure-mpfr; on=all-gmp; };
+dependencies = { module=configure-polylib; on=all-gmp; };
+dependencies = { module=configure-polylib; on=all-mpfr; };
+dependencies = { module=configure-cloog; on=all-polylib; };
// Host modules specific to gdb.
dependencies = { module=configure-gdb; on=all-intl; };
Index: Makefile.tpl
===================================================================
--- Makefile.tpl (.../trunk) (revision 138072)
+++ Makefile.tpl (.../branches/graphite) (revision 138161)
@@ -193,6 +193,10 @@ HOST_EXPORTS = \
TOPLEVEL_CONFIGURE_ARGUMENTS="$(TOPLEVEL_CONFIGURE_ARGUMENTS)"; export TOPLEVEL_CONFIGURE_ARGUMENTS; \
GMPLIBS="$(HOST_GMPLIBS)"; export GMPLIBS; \
GMPINC="$(HOST_GMPINC)"; export GMPINC; \
+ POLYLIBLIBS="$(HOST_POLYLIBLIBS)"; export POLYLIBLIBS; \
+ POLYLIBINC="$(HOST_POLYLIBINC)"; export POLYLIBINC; \
+ CLOOGLIBS="$(HOST_CLOOGLIBS)"; export CLOOGLIBS; \
+ CLOOGINC="$(HOST_CLOOGINC)"; export CLOOGINC; \
@if gcc-bootstrap
$(RPATH_ENVVAR)=`echo "$(TARGET_LIB_PATH)$$$(RPATH_ENVVAR)" | sed 's,::*,:,g;s,^:*,,;s,:*$$,,'`; export $(RPATH_ENVVAR); \
@endif gcc-bootstrap
@@ -252,6 +256,14 @@ NORMAL_TARGET_EXPORTS = \
HOST_GMPLIBS = @gmplibs@
HOST_GMPINC = @gmpinc@
+# Where to find POLYLIB
+HOST_POLYLIBLIBS = @polyliblibs@
+HOST_POLYLIBINC = @polylibinc@
+
+# Where to find CLOOG
+HOST_CLOOGLIBS = @clooglibs@
+HOST_CLOOGINC = @clooginc@
+
# ----------------------------------------------
# Programs producing files for the BUILD machine
# ----------------------------------------------
Index: gcc/testsuite/gcc.dg/graphite/scop-0.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-0.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-0.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,24 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+
+int foo (void);
+void bar (void);
+
+int toto()
+{
+ /* Scop 1. */
+ int i, j, k;
+ int a[100][100];
+ int b[100];
+ int N = foo ();
+
+ for (i = 0; i < 2*N+ 100; i++)
+ for (j = 0; j < 200; j++)
+ a[j][i] = a[j+1][10] + 2;
+
+ return a[3][5] + b[1];
+ /* End scop 1. */
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 3" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-1.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-1.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-1.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+
+void bar (void);
+
+int toto()
+{
+ int i, j, k;
+ int a[100][100];
+ int b[100];
+
+ for (i = 1; i < 100; i++)
+ {
+ for (j = 1; j < 100; j++)
+ a[j][i] = a[j+1][i-1] + 2;
+
+ b[i] = b[i-1] + 2;
+
+ bar ();
+
+ for (j = 1; j < 100; j++)
+ a[j][i] = a[j+1][i-1] + 2;
+
+ b[i] = a[i-1][i] + 2;
+
+ for (j = 1; j < 100; j++)
+ a[j][i] = a[j+1][i-1] + 2;
+ }
+
+ return a[3][5] + b[1];
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 5" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-2.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-2.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-2.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,42 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+
+void bar (void);
+
+int toto()
+{
+ int i, j, k;
+ int a[100][100];
+ int b[100];
+
+ for (i = 1; i < 100; i++)
+ {
+ for (j = 1; j < 100; j++)
+ for (k = 1; k < 100; k++)
+ a[j][k] = a[j+1][i-1] + 2;
+
+ b[i] = b[i-1] + 2;
+
+ bar ();
+
+ for (j = 1; j < 100; j++)
+ a[j][i] = a[j+1][i-1] + 2;
+
+ b[i] = b[i-1] + 2;
+
+ bar ();
+
+ for (j = 1; j < 100; j++)
+ a[j][i] = a[j+1][i-1] + 2;
+
+ b[i] = a[i-1][i] + 2;
+
+ for (j = 1; j < 100; j++)
+ a[j][i] = a[j+1][i-1] + 2;
+ }
+
+ return a[3][5] + b[1];
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 6" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-3.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-3.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-3.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,31 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+
+int toto()
+{
+ int i, j, k;
+ int a[100][100];
+ int b[100];
+
+ for (i = 1; i < 100; i++)
+ {
+ for (j = 1; j < 80; j++)
+ a[j][i] = a[j+1][2*i-1*j] + 12;
+
+ b[i] = b[i-1] + 10;
+
+ for (j = 1; j < 60; j++)
+ a[j][i] = a[j+1][i-1] + 8;
+
+ if (i == 23)
+ b[i] = a[i-1][i] + 6;
+
+ for (j = 1; j < 40; j++)
+ a[j][i] = a[j+1][i-1] + 4;
+ }
+
+ return a[3][5] + b[1];
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-4.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-4.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-4.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,32 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+
+void bar ();
+
+int toto()
+{
+ int i, j, k;
+ int a[100][100];
+ int b[100];
+
+ for (i = 1; i < 100; i++)
+ {
+ for (j = 1; j < 80; j++)
+ a[j][i] = a[j+1][2*i-1*j] + 12;
+
+ b[i] = b[i-1] + 10;
+
+ for (j = 1; j < 60; j++)
+ a[j][i] = a[j+1][i-1] + 8;
+
+ bar ();
+
+ if (i == 23)
+ b[i] = a[i-1][i] + 6;
+ }
+
+ return a[3][5] + b[1];
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 5" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-5.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-5.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-5.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,38 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+
+void bar ();
+
+int toto()
+{
+ int i,j, b;
+ int a[100];
+
+ if (i == 20)
+ {
+ for (j = 0; j <= 20; j++)
+ a[j] = b + i;
+ b = 3;
+ bar();
+ }
+ else
+ {
+ if (i == 30)
+ {
+ for (j = 0; j <= 20; j++)
+ a[j] = b + i;
+ b = 5;
+ }
+ else
+ {
+ for (j = 0; j <= 20; j++)
+ a[j] = b + i;
+ b = 8;
+ }
+ }
+
+ return a[b];
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 4" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-6.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-6.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-6.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+
+void bar (void);
+
+int toto()
+{
+ int i, j, k;
+ int a[100][100];
+ int b[100];
+
+ for (i = 1; i < 100; i++)
+ {
+ for (j = 1; j < 100; j++)
+ b[i+j] = b[i+j-1] + 2;
+
+ if (i * 2 == i + 8)
+ b[i+k] = b[i+k-1] + 2;
+ else
+ {
+ for (k = 1; k < 100; k++)
+ b[i+k] = b[i+k-1] + 2;
+ bar ();
+ }
+
+ for (k = 1; k < 100; k++)
+ b[i+k] = b[i+k-5] + 2;
+ }
+
+ return a[3][5] + b[1];
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 7" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-7.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-7.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-7.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+
+void bar (void);
+
+int toto()
+{
+ int i, j, k;
+ int a[100][100];
+ int b[100];
+
+ for (i = 1; i < 100; i++)
+ {
+ for (j = 1; j < 100; j++)
+ b[i+j] = b[i+j-1] + 2;
+
+ if (i * 2 == i + 8)
+ {
+ bar ();
+ for (j = 1; j < 100; j++)
+ b[i+j] = b[i+j-1] + 2;
+ }
+ else
+ a[i][i] = 2;
+
+ for (k = 1; k < 100; k++)
+ b[i+k] = b[i+k-5] + 2;
+ }
+
+ return a[3][5] + b[1];
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 7" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-8.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-8.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-8.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+
+int bar (void);
+
+int toto()
+{
+ int i, j, k;
+ int a[100][100];
+ int b[100];
+
+ for (i = 1; i < 100; i++)
+ {
+ for (j = 1; j < 100; j++)
+ b[i+j] = b[i+j-1] + 2;
+
+ if (i * 2 == i + 8)
+ {
+ for (j = 1; j < 100; j++)
+ if (bar ())
+ b[i+j] = b[i+j-1] + 2;
+ }
+ else
+ a[i][i] = 2;
+
+ for (k = 1; k < 100; k++)
+ b[i+k] = b[i+k-5] + 2;
+ }
+
+ return a[3][5] + b[1];
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 10" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-9.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-9.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-9.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,30 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+
+void bar (void);
+
+int toto()
+{
+ int i, j, k;
+ int a[100][100];
+ int b[100];
+
+ for (i = 1; i < 100; i++)
+ {
+ for (j = 1; j < 100; j++)
+ b[i+j] = b[i+j-1] + 2;
+
+ if (i * 2 == i + 8)
+ bar ();
+ else
+ a[i][i] = 2;
+
+ for (k = 1; k < 100; k++)
+ b[i+k] = b[i+k-5] + 2;
+ }
+
+ return a[3][5] + b[1];
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 6" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/graphite.exp
===================================================================
--- gcc/testsuite/gcc.dg/graphite/graphite.exp (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/graphite.exp (.../branches/graphite) (revision 138161)
@@ -0,0 +1,36 @@
+# Copyright (C) 2006 Free Software Foundation, Inc.
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+
+# GCC testsuite that uses the `dg.exp' driver.
+
+# Load support procs.
+load_lib gcc-dg.exp
+
+# If a testcase doesn't have special options, use these.
+global DEFAULT_CFLAGS
+if ![info exists DEFAULT_CFLAGS] then {
+ set DEFAULT_CFLAGS " -ansi -pedantic-errors"
+}
+
+# Initialize `dg'.
+dg-init
+
+# Main loop.
+dg-runtest [lsort [glob -nocomplain $srcdir/$subdir/*.\[cS\]]] \
+ "" $DEFAULT_CFLAGS
+
+# All done.
+dg-finish
Index: gcc/testsuite/gcc.dg/graphite/scop-10.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-10.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-10.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+
+void bar (void);
+
+int toto()
+{
+ int i, j, k;
+ int a[100][100];
+ int b[100];
+
+ for (i = 1; i < 100; i++)
+ {
+ for (j = 1; j < 100; j++)
+ b[i+j] = b[i+j-1] + 2;
+
+ if (i * 2 == i + 8)
+ bar ();
+ else
+ {
+ for (j = 1; j < 100; j++)
+ b[i+j] = b[i+j-1] + 2;
+ a[i][i] = 2;
+ }
+
+ for (k = 1; k < 100; k++)
+ b[i+k] = b[i+k-5] + 2;
+ }
+
+ return a[3][5] + b[1];
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 6" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-11.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-11.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-11.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+
+void bar ();
+
+int toto()
+{
+ int i,j, b;
+ int a[100];
+
+ if (i == 20)
+ {
+ for (j = 0; j <= 20; j++)
+ a[j] = b + i;
+ b = 3;
+ bar();
+ }
+ else
+ {
+ if (i == 30)
+ {
+ for (j = 0; j <= 20; j++)
+ a[j] = b + i;
+ b = 5;
+ }
+ }
+
+ for (j = 0; j <= 20; j++)
+ a[j] = b + i;
+
+ return a[b];
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 4" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-12.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-12.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-12.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,39 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+
+void bar ();
+
+int toto()
+{
+ int i,j, b;
+ int a[100];
+
+ switch (i)
+ {
+
+ case 5:
+ for (j = 0; j <= 20; j++)
+ a[j] = b + i + 12;
+ break;
+ case 8:
+ for (j = 0; j <= 20; j++)
+ a[j] = b + i + 122;
+ break;
+ case 15:
+ for (j = 0; j <= 20; j++)
+ a[j] = b + i + 12;
+ break;
+ case 18:
+ for (j = 0; j <= 20; j++)
+ a[j] = b + i + 4;
+ break;
+ default:
+ for (j = 0; j <= 20; j++)
+ a[j] = b + i + 3;
+ }
+
+ return a[b];
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 7" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-13.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-13.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-13.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,44 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+
+void bar ();
+
+int toto()
+{
+ int i,j, b;
+ int a[100];
+
+ if (i == 20)
+ {
+ b = 3;
+ goto B;
+ }
+ else
+ {
+ if (i == 30)
+ {
+ a[i] = b;
+
+
+ for (j = 0; j <= 20; j++)
+ a[j] = b + i;
+
+ B:
+
+ for (j = 0; j <= 20; j++)
+ a[j+b] = b + i;
+
+ bar ();
+ }
+ else
+ {
+ a[i] = b + 3;
+ }
+ }
+
+
+ return a[b];
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 5" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-matmult.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-matmult.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-matmult.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+#define FLOAT float
+
+int foo (void);
+
+/* Multiply two n x n matrices A and B and store the result in C. */
+
+void matmult (FLOAT **A, FLOAT **B, FLOAT **C, int n)
+{
+ int i,j,k;
+
+ for (i = 0; i < n; i++)
+ for (j = 0; j < n; j++)
+ for (k = 0; k < n; k++)
+ A[i][j] += B[i][k] * C[k][j];
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 3" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-14.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-14.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-14.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,28 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+
+void bar ();
+
+int toto()
+{
+ int i,j, b;
+ int a[100];
+
+ for (j = 0; j <= 20; j++)
+ {
+ a[j] = b + i;
+
+ if (j * i == b)
+ break;
+
+ a[j+b] = b + i;
+ }
+
+ a[i] = b + 3;
+
+
+ return a[b];
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 3" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-15.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-15.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-15.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,53 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
+
+# define EXTERN(type, array) extern type array[]
+typedef unsigned char uch;
+typedef unsigned short ush;
+EXTERN(uch, window);
+EXTERN(ush, prev);
+#ifndef WSIZE
+# define WSIZE 0x8000
+#endif
+#define MIN_MATCH 3
+#define MAX_MATCH 258
+#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
+#define MAX_DIST (WSIZE-MIN_LOOKAHEAD)
+#define near
+typedef unsigned IPos;
+unsigned near max_chain_length;
+extern unsigned near strstart;
+unsigned int near prev_length;
+#define NIL 0
+unsigned near good_match;
+int near nice_match;
+#define WMASK (WSIZE-1)
+int longest_match(IPos cur_match)
+{
+ unsigned chain_length = max_chain_length;
+ register uch *scan = window + strstart;
+ register uch *match;
+ register int len;
+ int best_len = prev_length;
+ IPos limit = strstart > (IPos)MAX_DIST ? strstart - (IPos)MAX_DIST : NIL;
+ register uch *strend = window + strstart + MAX_MATCH;
+ register uch scan_end = scan[best_len];
+ if (prev_length >= good_match) {
+ }
+ do {
+ if (match[best_len] != scan_end ||
+ *++match != scan[1]) continue;
+ do {
+ } while (*++scan == *++match && *++scan == *++match &&
+ scan < strend);
+ len = MAX_MATCH - (int)(strend - scan);
+ if (len > best_len) {
+ best_len = len;
+ if (len >= nice_match) break;
+ }
+ } while ((cur_match = prev[cur_match & WMASK]) > limit
+ && --chain_length != 0);
+ return best_len;
+}
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 11" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/block-0.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/block-0.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/block-0.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-O -floop-block -fdump-tree-graphite-all" } */
+
+#define N 1000
+
+int toto()
+{
+ int j;
+ int i;
+ int a[N];
+ int b[N];
+
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ a[j] = a[i] + 1;
+
+ return a[0];
+}
+
+main()
+{
+ return toto();
+}
+
+/* { dg-final { scan-tree-dump-times "Loop blocked" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-16.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-16.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-16.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */
+#define N 100000
+void foo (int);
+int test ()
+{
+ int a[N][N];
+ int b[N][N];
+ unsigned i, j;
+
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ a[i][j] = i*j;
+
+ for (j = 1; j < N; j++)
+ for (i = 0; i < N; i++)
+ a[i][j] = a[i][j-1] + b[i][j];
+
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ foo (a[i][j]);
+}
+
+/* Interchange is legal for loops 2 and 3. */
+/* { dg-final { scan-tree-dump-times "Interchange valid for loops 2 and 3:" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-17.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-17.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-17.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */
+#define N 100000
+void foo (int);
+int test ()
+{
+ int a[N][N];
+ unsigned i, j;
+
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ a[i][j] = i*j;
+
+ for (i = 1; i < N; i++)
+ for (j = 1; j < (N-1) ; j++)
+ a[i][j] = a[i-1][j+1] * a[i-1][j+1]/2;
+
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ foo (a[i][j]);
+}
+
+/* Interchange is not legal for loops 2 and 3. */
+/* { dg-final { scan-tree-dump-times "Interchange not valid for loops 2 and 3:" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/scop-18.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/scop-18.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/graphite/scop-18.c (.../branches/graphite) (revision 138161)
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */
+
+#define N 24
+#define M 1000
+
+void test (float **A, float **B, float **C)
+{
+ int i, j, k;
+
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ for (k = 0; k < N; k++)
+ A[i][j] += B[i][k] * C[k][j];
+
+
+ for (i = 0; i < M; i++)
+ for (j = 0; j < M; j++)
+ for (k = 0; k < M; k++)
+ A[i][j] += B[i][k] * C[k][j];
+}
+
+/* Strip Mining is not profitable for loops 0, 1 and 2. */
+
+/* { dg-final { scan-tree-dump-times "Strip Mining is not profitable" 3 "graphite" } } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: gcc/testsuite/gfortran.dg/graphite/scop-1.f
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/scop-1.f (.../trunk) (revision 0)
+++ gcc/testsuite/gfortran.dg/graphite/scop-1.f (.../branches/graphite) (revision 138161)
@@ -0,0 +1,14 @@
+C { dg-do compile }
+C { dg-options "-O2 -fgraphite" }
+
+ dimension p1(2),t(6,4),b1(2),b2(2),al1(2),al2(2),g1(2),g2(2)
+ save
+ if(nlin.eq.0) then
+ do 20 l=1,2
+ ll=2*l
+ b2(l)=t(6-ll,ll-1)*t(6-ll,ll-1)+t(7-ll,ll-1)*t(7-ll,ll-1)
+ write(*,*) b2(l)
+ 20 continue
+ endif
+ end
+
Index: gcc/testsuite/gfortran.dg/graphite/graphite.exp
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/graphite.exp (.../trunk) (revision 0)
+++ gcc/testsuite/gfortran.dg/graphite/graphite.exp (.../branches/graphite) (revision 138161)
@@ -0,0 +1,37 @@
+# Copyright (C) 2006 Free Software Foundation, Inc.
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+
+# GCC testsuite that uses the `dg.exp' driver.
+
+# Load support procs.
+load_lib gfortran-dg.exp
+
+# If a testcase doesn't have special options, use these.
+set DEFAULT_GRAPHITE_FLAGS ""
+
+# Initialize `dg'.
+dg-init
+
+# Main loop.
+gfortran-dg-runtest [lsort \
+ [glob -nocomplain $srcdir/$subdir/*.\[fF\]{,90,95,03,08} ] ] $DEFAULT_GRAPHITE_FLAGS
+
+gfortran-dg-runtest [lsort \
+ [glob -nocomplain $srcdir/$subdir/g77/*.\[fF\] ] ] $DEFAULT_GRAPHITE_FLAGS
+
+
+# All done.
+dg-finish
Index: gcc/tree-loop-linear.c
===================================================================
--- gcc/tree-loop-linear.c (.../trunk) (revision 138072)
+++ gcc/tree-loop-linear.c (.../branches/graphite) (revision 138161)
@@ -272,7 +272,7 @@ try_interchange_loops (lambda_trans_matr
/* Return the number of nested loops in LOOP_NEST, or 0 if the loops
are not perfectly nested. */
-static unsigned int
+unsigned int
perfect_loop_nest_depth (struct loop *loop_nest)
{
struct loop *temp;
Index: invoke.texi
===================================================================
--- invoke.texi (.../trunk/gcc/doc/invoke.texi) (revision 138072)
+++ invoke.texi (.../branches/graphite/gcc/doc/invoke.texi) (revision 138162)
@@ -333,6 +333,7 @@ Objective-C and Objective-C++ Dialects}.
-finline-small-functions -fipa-cp -fipa-marix-reorg -fipa-pta @gol
-fipa-pure-const -fipa-reference -fipa-struct-reorg @gol
-fipa-type-escape -fivopts -fkeep-inline-functions -fkeep-static-consts @gol
+-floop-block -floop-interchange -floop-strip-mine @gol
-fmerge-all-constants -fmerge-constants -fmodulo-sched @gol
-fmodulo-sched-allow-regmoves -fmove-loop-invariants -fmudflap @gol
-fmudflapir -fmudflapth -fno-branch-count-reg -fno-default-inline @gol
@@ -5931,6 +5932,15 @@ at @option{-O} and higher.
Perform linear loop transformations on tree. This flag can improve cache
performance and allow further loop optimizations to take place.
+@item -floop-block
+Perform loop blocking transformations on loops.
+
+@item -floop-strip-mine
+Perform loop strip mining transformations on loops.
+
+@item -floop-interchange
+Perform loop interchange transformations on loops.
+
@item -fcheck-data-deps
@opindex fcheck-data-deps
Compare the results of several data dependence analyzers. This option
Index: gcc/tree-loop-distribution.c
===================================================================
--- gcc/tree-loop-distribution.c (.../trunk) (revision 138072)
+++ gcc/tree-loop-distribution.c (.../branches/graphite) (revision 138161)
@@ -720,17 +720,6 @@ rdg_flag_loop_exits (struct graph *rdg,
}
}
-/* Strongly connected components of the reduced data dependence graph. */
-
-typedef struct rdg_component
-{
- int num;
- VEC (int, heap) *vertices;
-} *rdgc;
-
-DEF_VEC_P (rdgc);
-DEF_VEC_ALLOC_P (rdgc, heap);
-
/* Flag all the nodes of RDG containing memory accesses that could
potentially belong to arrays already accessed in the current
PARTITION. */
@@ -874,9 +863,6 @@ rdg_build_components (struct graph *rdg,
BITMAP_FREE (saved_components);
}
-DEF_VEC_P (bitmap);
-DEF_VEC_ALLOC_P (bitmap, heap);
-
/* Aggregate several components into a useful partition that is
registered in the PARTITIONS vector. Partitions will be
distributed in different loops. */
Index: gcc/cfgloopmanip.c
===================================================================
--- gcc/cfgloopmanip.c (.../trunk) (revision 138072)
+++ gcc/cfgloopmanip.c (.../branches/graphite) (revision 138161)
@@ -30,6 +30,7 @@ along with GCC; see the file COPYING3.
#include "cfglayout.h"
#include "cfghooks.h"
#include "output.h"
+#include "tree-flow.h"
static void duplicate_subloops (struct loop *, struct loop *);
static void copy_loops_to (struct loop **, int,
@@ -466,6 +467,160 @@ scale_loop_frequencies (struct loop *loo
free (bbs);
}
+/* Recompute dominance information for basic blocks outside LOOP. */
+
+static void update_dominators_in_loop (struct loop *loop)
+{
+ VEC (basic_block, heap) *dom_bbs = NULL;
+ sbitmap seen;
+ basic_block *body;
+ unsigned i;
+
+ seen = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (seen);
+ body = get_loop_body (loop);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ SET_BIT (seen, body[i]->index);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ basic_block ldom;
+
+ for (ldom = first_dom_son (CDI_DOMINATORS, body[i]);
+ ldom;
+ ldom = next_dom_son (CDI_DOMINATORS, ldom))
+ if (!TEST_BIT (seen, ldom->index))
+ {
+ SET_BIT (seen, ldom->index);
+ VEC_safe_push (basic_block, heap, dom_bbs, ldom);
+ }
+ }
+
+ iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
+ free (body);
+ free (seen);
+ VEC_free (basic_block, heap, dom_bbs);
+}
+
+/* create_empty_loop_on_edge
+ |
+ | ------------- -----------------------
+ | | pred_bb | | pred_bb |
+ | ------------- | IV = INITIAL_VALUE |
+ | | -----------------------
+ | | ______ | ENTRY_EDGE
+ | | ENTRY_EDGE / V V
+ | | ====> | ------------------
+ | | | | loop_header |
+ | V | | IV <= UPPER_BOUND|---
+ | ------------- | ------------------ \
+ | | succ_bb | | | \
+ | ------------- | | |
+ | | V | exit_e
+ | | -------------- |
+ | | | loop_latch | |
+ | | |IV += STEP | V
+ | | -------------- ------------
+ | \ / | succ_bb |
+ | \ ___ / ------------
+
+ Creates an empty loop as shown above, the IV_BEFORE is the SSA_NAME
+ that is used before the increment of IV. IV_BEFORE should be used for
+ adding code to the body that uses the IV. OUTER is the outer loop in
+ which the new loop should be inserted.
+*/
+struct loop *
+create_empty_loop_on_edge (edge entry_edge,
+ tree initial_value,
+ tree stride, tree upper_bound,
+ tree iv,
+ tree *iv_before,
+ struct loop *outer)
+{
+ basic_block loop_header, loop_latch, succ_bb, pred_bb;
+ tree cond_expr;
+ struct loop *loop;
+ int freq;
+ gcov_type cnt;
+ block_stmt_iterator bsi;
+ bool insert_after;
+ tree stmts, exit_test;
+ edge exit_e;
+ int prob;
+
+ gcc_assert (entry_edge);
+ gcc_assert (initial_value);
+ gcc_assert (stride);
+ gcc_assert (upper_bound);
+ gcc_assert (iv);
+
+ /* Create header, latch and wire up the loop. */
+ pred_bb = entry_edge->src;
+ loop_header = split_edge (entry_edge);
+ loop_latch = split_edge (single_succ_edge (loop_header));
+ succ_bb = single_succ (loop_latch);
+ make_edge (loop_header, succ_bb, 0);
+ redirect_edge_succ_nodup (single_succ_edge (loop_latch), loop_header);
+
+ /* Set immediate dominator information. */
+ set_immediate_dominator (CDI_DOMINATORS, loop_header, pred_bb);
+ set_immediate_dominator (CDI_DOMINATORS, loop_latch, loop_header);
+ set_immediate_dominator (CDI_DOMINATORS, succ_bb, loop_header);
+
+ /* Initialize a loop structure and put it in a loop hierarchy. */
+ loop = alloc_loop ();
+ loop->header = loop_header;
+ loop->latch = loop_latch;
+ add_loop (loop, outer);
+
+ /* TODO: Fix frequencies and counts. */
+ freq = EDGE_FREQUENCY (entry_edge);
+ cnt = entry_edge->count;
+
+ prob = REG_BR_PROB_BASE / 2;
+
+ scale_loop_frequencies (loop, REG_BR_PROB_BASE - prob, REG_BR_PROB_BASE);
+
+ /* Update dominators. */
+ update_dominators_in_loop (loop);
+
+ /* Construct IV code in loop. */
+ initial_value = force_gimple_operand (initial_value, &stmts, true, iv);
+ if (stmts)
+ {
+ bsi_insert_on_edge (loop_preheader_edge (loop), stmts);
+ bsi_commit_edge_inserts ();
+ }
+
+ add_referenced_var (iv);
+ standard_iv_increment_position (loop, &bsi, &insert_after);
+ create_iv (initial_value, stride, iv, loop, &bsi, insert_after, iv_before, NULL);
+
+ /* Modify edge flags. */
+ exit_e = single_exit (loop);
+ exit_e->flags = EDGE_LOOP_EXIT | EDGE_FALSE_VALUE;
+ single_pred_edge (loop_latch)->flags = EDGE_TRUE_VALUE;
+
+ bsi = bsi_last (exit_e->src);
+
+
+ cond_expr = build2 (LE_EXPR, boolean_type_node, *iv_before, upper_bound);
+ cond_expr = build3 (COND_EXPR, void_type_node, cond_expr,
+ NULL_TREE, NULL_TREE);
+
+ exit_test = TREE_OPERAND(cond_expr, 0);
+ exit_test = force_gimple_operand (exit_test, &stmts, true, NULL);
+ TREE_OPERAND (cond_expr,0) = exit_test;
+ if (stmts)
+ bsi_insert_after (&bsi, stmts, BSI_NEW_STMT);
+
+ bsi = bsi_last (exit_e->src);
+ bsi_insert_after (&bsi, cond_expr, BSI_NEW_STMT);
+
+ return loop;
+}
+
/* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
latch to header and update loop tree and dominators
accordingly. Everything between them plus LATCH_EDGE destination must
Index: gcc/tree-pass.h
===================================================================
--- gcc/tree-pass.h (.../trunk) (revision 138072)
+++ gcc/tree-pass.h (.../branches/graphite) (revision 138161)
@@ -319,6 +319,7 @@ extern struct gimple_opt_pass pass_iv_ca
extern struct gimple_opt_pass pass_scev_cprop;
extern struct gimple_opt_pass pass_empty_loop;
extern struct gimple_opt_pass pass_record_bounds;
+extern struct gimple_opt_pass pass_graphite_transforms;
extern struct gimple_opt_pass pass_if_conversion;
extern struct gimple_opt_pass pass_loop_distribution;
extern struct gimple_opt_pass pass_vectorize;
Index: gcc/tree-phinodes.c
===================================================================
--- gcc/tree-phinodes.c (.../trunk) (revision 138072)
+++ gcc/tree-phinodes.c (.../branches/graphite) (revision 138161)
@@ -80,7 +80,6 @@ static GTY ((deletable (""))) tree free_
static unsigned long free_phinode_count;
static int ideal_phi_node_len (int);
-static void resize_phi_node (tree *, int);
#ifdef GATHER_STATISTICS
unsigned int phi_nodes_reused;
@@ -261,7 +260,7 @@ release_phi_node (tree phi)
/* Resize an existing PHI node. The only way is up. Return the
possibly relocated phi. */
-static void
+void
resize_phi_node (tree *phi, int len)
{
int old_size, i;
@@ -440,14 +439,10 @@ remove_phi_args (edge e)
remove_phi_arg_num (phi, e->dest_idx);
}
+/* Unlink PHI node. */
-/* Remove PHI node PHI from basic block BB. If PREV is non-NULL, it is
- used as the node immediately before PHI in the linked list. If
- RELEASE_LHS_P is true, the LHS of this PHI node is released into
- the free pool of SSA names. */
-
-void
-remove_phi_node (tree phi, tree prev, bool release_lhs_p)
+static void
+unlink_phi_node (tree phi, tree prev)
{
tree *loc;
@@ -465,7 +460,29 @@ remove_phi_node (tree phi, tree prev, bo
/* Remove PHI from the chain. */
*loc = PHI_CHAIN (phi);
+}
+
+/* Move PHI node to new basick block BB. */
+
+void
+move_phi_node (tree phi, basic_block bb)
+{
+ tree old_phis = phi_nodes (bb);
+
+ unlink_phi_node (phi, NULL);
+ PHI_CHAIN (phi) = old_phis;
+ set_phi_nodes (bb, phi);
+}
+
+/* Remove PHI node PHI from basic block BB. If PREV is non-NULL, it is
+ used as the node immediately before PHI in the linked list. If
+ RELEASE_LHS_P is true, the LHS of this PHI node is released into
+ the free pool of SSA names. */
+void
+remove_phi_node (tree phi, tree prev, bool release_lhs_p)
+{
+ unlink_phi_node (phi, prev);
/* If we are deleting the PHI node, then we should release the
SSA_NAME node so that it can be reused. */
release_phi_node (phi);
Index: gcc/cfghooks.c
===================================================================
--- gcc/cfghooks.c (.../trunk) (revision 138072)
+++ gcc/cfghooks.c (.../branches/graphite) (revision 138161)
@@ -507,41 +507,16 @@ delete_basic_block (basic_block bb)
expunge_block (bb);
}
-/* Splits edge E and returns the newly created basic block. */
+/* Updates the dominator information for block RET. */
-basic_block
-split_edge (edge e)
+static void
+update_dominator_information (basic_block ret)
{
- basic_block ret;
- gcov_type count = e->count;
- int freq = EDGE_FREQUENCY (e);
edge f;
- bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
- struct loop *loop;
- basic_block src = e->src, dest = e->dest;
-
- if (!cfg_hooks->split_edge)
- internal_error ("%s does not support split_edge", cfg_hooks->name);
-
- if (current_loops != NULL)
- rescan_loop_exit (e, false, true);
-
- ret = cfg_hooks->split_edge (e);
- ret->count = count;
- ret->frequency = freq;
- single_succ_edge (ret)->probability = REG_BR_PROB_BASE;
- single_succ_edge (ret)->count = count;
-
- if (irr)
- {
- ret->flags |= BB_IRREDUCIBLE_LOOP;
- single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
- single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
- }
if (dom_info_available_p (CDI_DOMINATORS))
set_immediate_dominator (CDI_DOMINATORS, ret, single_pred (ret));
-
+
if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
{
/* There are two cases:
@@ -571,6 +546,41 @@ split_edge (edge e)
set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret);
}
}
+}
+
+
+/* Splits edge E and returns the newly created basic block. */
+
+basic_block
+split_edge (edge e)
+{
+ basic_block ret;
+ gcov_type count = e->count;
+ int freq = EDGE_FREQUENCY (e);
+ bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
+ struct loop *loop;
+ basic_block src = e->src, dest = e->dest;
+
+ if (!cfg_hooks->split_edge)
+ internal_error ("%s does not support split_edge", cfg_hooks->name);
+
+ if (current_loops != NULL)
+ rescan_loop_exit (e, false, true);
+
+ ret = cfg_hooks->split_edge (e);
+ ret->count = count;
+ ret->frequency = freq;
+ single_succ_edge (ret)->probability = REG_BR_PROB_BASE;
+ single_succ_edge (ret)->count = count;
+
+ if (irr)
+ {
+ ret->flags |= BB_IRREDUCIBLE_LOOP;
+ single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
+ single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
+ }
+
+ update_dominator_information(ret);
if (current_loops != NULL)
{
Index: gcc/toplev.c
===================================================================
--- gcc/toplev.c (.../trunk) (revision 138072)
+++ gcc/toplev.c (.../branches/graphite) (revision 138161)
@@ -1937,6 +1937,11 @@ process_options (void)
"for correctness");
flag_omit_frame_pointer = 0;
}
+
+ /* Enable -fgraphite pass if any one of the graphite optimization flags
+ is turned on. */
+ if (flag_loop_block || flag_loop_interchange || flag_loop_strip_mine)
+ flag_graphite = 1;
}
/* This function can be called multiple times to reinitialize the compiler
Index: gcc/tree-chrec.c
===================================================================
--- gcc/tree-chrec.c (.../trunk) (revision 138072)
+++ gcc/tree-chrec.c (.../branches/graphite) (revision 138161)
@@ -1408,3 +1408,26 @@ scev_direction (const_tree chrec)
else
return EV_DIR_GROWS;
}
+
+/* Iterates over all the components of SCEV, and calls CBCK. */
+
+void
+for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
+{
+ switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
+ {
+ case 3:
+ for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
+
+ case 2:
+ for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
+
+ case 1:
+ for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
+
+ default:
+ cbck (scev, data);
+ break;
+ }
+}
+
Index: gcc/tree-chrec.h
===================================================================
--- gcc/tree-chrec.h (.../trunk) (revision 138072)
+++ gcc/tree-chrec.h (.../branches/graphite) (revision 138161)
@@ -70,6 +70,7 @@ extern tree evolution_part_in_loop_num (
extern tree hide_evolution_in_other_loops_than_loop (tree, unsigned);
extern tree reset_evolution_in_loop (unsigned, tree, tree);
extern tree chrec_merge (tree, tree);
+extern void for_each_scev_op (tree *, bool (*) (tree *, void *), void *);
/* Observers. */
extern bool eq_evolutions_p (const_tree, const_tree);
Index: gcc/timevar.def
===================================================================
--- gcc/timevar.def (.../trunk) (revision 138072)
+++ gcc/timevar.def (.../branches/graphite) (revision 138161)
@@ -125,6 +125,7 @@ DEFTIMEVAR (TV_TREE_LOOP_UNSWITCH , "
DEFTIMEVAR (TV_COMPLETE_UNROLL , "complete unrolling")
DEFTIMEVAR (TV_TREE_PARALLELIZE_LOOPS, "tree parallelize loops")
DEFTIMEVAR (TV_TREE_VECTORIZATION , "tree vectorization")
+DEFTIMEVAR (TV_GRAPHITE_TRANSFORMS , "GRAPHITE loop transforms")
DEFTIMEVAR (TV_TREE_LINEAR_TRANSFORM , "tree loop linear")
DEFTIMEVAR (TV_TREE_LOOP_DISTRIBUTION, "tree loop distribution")
DEFTIMEVAR (TV_CHECK_DATA_DEPS , "tree check data dependences")
Index: gcc/tree-ssa-loop.c
===================================================================
--- gcc/tree-ssa-loop.c (.../trunk) (revision 138072)
+++ gcc/tree-ssa-loop.c (.../branches/graphite) (revision 138161)
@@ -294,6 +294,46 @@ struct gimple_opt_pass pass_linear_trans
}
};
+/* GRAPHITE optimizations. */
+
+static unsigned int
+graphite_transforms (void)
+{
+ if (!current_loops)
+ return 0;
+
+#ifdef HAVE_cloog
+ graphite_transform_loops ();
+#endif
+
+ return 0;
+}
+
+static bool
+gate_graphite_transforms (void)
+{
+ return flag_graphite != 0;
+}
+
+struct gimple_opt_pass pass_graphite_transforms =
+{
+ {
+ GIMPLE_PASS,
+ "graphite", /* name */
+ gate_graphite_transforms, /* gate */
+ graphite_transforms, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_GRAPHITE_TRANSFORMS, /* tv_id */
+ PROP_cfg | PROP_ssa, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_verify_loops /* todo_flags_finish */
+ }
+};
+
/* Check the correctness of the data dependence analyzers. */
static unsigned int
Index: gcc/tree-vectorizer.c
===================================================================
--- gcc/tree-vectorizer.c (.../trunk) (revision 138072)
+++ gcc/tree-vectorizer.c (.../branches/graphite) (revision 138161)
@@ -195,7 +195,7 @@ rename_use_op (use_operand_p op_p)
/* Renames the variables in basic block BB. */
-static void
+void
rename_variables_in_bb (basic_block bb)
{
tree phi;
Index: gcc/tree-vectorizer.h
===================================================================
--- gcc/tree-vectorizer.h (.../trunk) (revision 138072)
+++ gcc/tree-vectorizer.h (.../branches/graphite) (revision 138161)
@@ -628,6 +628,7 @@ extern bitmap vect_memsyms_to_rename;
to force the alignment of data references in the loop. */
extern struct loop *slpeel_tree_peel_loop_to_edge
(struct loop *, edge, tree, tree, bool, unsigned int, bool);
+struct loop *tree_duplicate_loop_on_edge (struct loop *, edge);
extern void set_prologue_iterations (basic_block, tree,
struct loop *, unsigned int);
struct loop *tree_duplicate_loop_on_edge (struct loop *, edge);
Index: gcc/tree-data-ref.c
===================================================================
--- gcc/tree-data-ref.c (.../trunk) (revision 138072)
+++ gcc/tree-data-ref.c (.../branches/graphite) (revision 138161)
@@ -1211,7 +1211,7 @@ disjoint_objects_p (tree a, tree b)
/* Returns false if we can prove that data references A and B do not alias,
true otherwise. */
-static bool
+bool
dr_may_alias_p (const struct data_reference *a, const struct data_reference *b)
{
const_tree addr_a = DR_BASE_ADDRESS (a);
@@ -4057,9 +4057,9 @@ get_references_in_stmt (tree stmt, VEC (
/* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
reference, returns false, otherwise returns true. NEST is the outermost
- loop of the loop nest in that the references should be analyzed. */
+ loop of the loop nest in which the references should be analyzed. */
-static bool
+bool
find_data_references_in_stmt (struct loop *nest, tree stmt,
VEC (data_reference_p, heap) **datarefs)
{
@@ -4104,7 +4104,7 @@ find_data_references_in_stmt (struct loo
TODO: This function should be made smarter so that it can handle address
arithmetic as if they were array accesses, etc. */
-static tree
+tree
find_data_references_in_loop (struct loop *loop,
VEC (data_reference_p, heap) **datarefs)
{
@@ -4632,6 +4632,7 @@ create_rdg_edge_for_ddr (struct graph *r
e->data = XNEW (struct rdg_edge);
RDGE_LEVEL (e) = level;
+ RDGE_RELATION (e) = ddr;
/* Determines the type of the data dependence. */
if (DR_IS_READ (dra) && DR_IS_READ (drb))
@@ -4664,6 +4665,7 @@ create_rdg_edges_for_scalar (struct grap
e = add_edge (rdg, idef, use);
e->data = XNEW (struct rdg_edge);
RDGE_TYPE (e) = flow_dd;
+ RDGE_RELATION (e) = NULL;
}
}
@@ -4689,7 +4691,7 @@ create_rdg_edges (struct graph *rdg, VEC
/* Build the vertices of the reduced dependence graph RDG. */
-static void
+void
create_rdg_vertices (struct graph *rdg, VEC (tree, heap) *stmts)
{
int i, j;
@@ -4811,6 +4813,21 @@ hash_stmt_vertex_del (void *e)
scalar dependence. */
struct graph *
+build_empty_rdg (int n_stmts)
+{
+ int nb_data_refs = 10;
+ struct graph *rdg = new_graph (n_stmts);
+
+ rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
+ eq_stmt_vertex_info, hash_stmt_vertex_del);
+ return rdg;
+}
+
+/* Build the Reduced Dependence Graph (RDG) with one vertex per
+ statement of the loop nest, and one edge per data dependence or
+ scalar dependence. */
+
+struct graph *
build_rdg (struct loop *loop)
{
int nb_data_refs = 10;
@@ -4827,21 +4844,23 @@ build_rdg (struct loop *loop)
&dependence_relations);
if (!known_dependences_p (dependence_relations))
- goto end_rdg;
+ {
+ free_dependence_relations (dependence_relations);
+ free_data_refs (datarefs);
+ VEC_free (tree, heap, stmts);
+
+ return rdg;
+ }
stmts_from_loop (loop, &stmts);
- rdg = new_graph (VEC_length (tree, stmts));
+ rdg = build_empty_rdg (VEC_length (tree, stmts));
rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
eq_stmt_vertex_info, hash_stmt_vertex_del);
create_rdg_vertices (rdg, stmts);
create_rdg_edges (rdg, dependence_relations);
- end_rdg:
- free_dependence_relations (dependence_relations);
- free_data_refs (datarefs);
VEC_free (tree, heap, stmts);
-
return rdg;
}
Index: gcc/tree-data-ref.h
===================================================================
--- gcc/tree-data-ref.h (.../trunk) (revision 138072)
+++ gcc/tree-data-ref.h (.../branches/graphite) (revision 138161)
@@ -96,6 +96,8 @@ struct dr_alias
bitmap vops;
};
+typedef struct scop *scop_p;
+
/* Each vector of the access matrix represents a linear access
function for a subscript. First elements correspond to the
leftmost indices, ie. for a[i][j] the first vector corresponds to
@@ -176,10 +178,14 @@ struct data_reference
/* Alias information for the data reference. */
struct dr_alias alias;
+ /* The SCoP in which the data reference was analyzed. */
+ scop_p scop;
+
/* Matrix representation for the data access functions. */
struct access_matrix *access_matrix;
};
+#define DR_SCOP(DR) (DR)->scop
#define DR_STMT(DR) (DR)->stmt
#define DR_REF(DR) (DR)->ref
#define DR_BASE_OBJECT(DR) (DR)->indices.base_object
@@ -373,6 +379,8 @@ void dr_analyze_innermost (struct data_r
extern bool compute_data_dependences_for_loop (struct loop *, bool,
VEC (data_reference_p, heap) **,
VEC (ddr_p, heap) **);
+extern tree find_data_references_in_loop (struct loop *,
+ VEC (data_reference_p, heap) **);
extern void print_direction_vector (FILE *, lambda_vector, int);
extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int);
extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int);
@@ -392,11 +400,17 @@ extern void free_dependence_relation (st
extern void free_dependence_relations (VEC (ddr_p, heap) *);
extern void free_data_ref (data_reference_p);
extern void free_data_refs (VEC (data_reference_p, heap) *);
+extern bool find_data_references_in_stmt (struct loop *, tree,
+ VEC (data_reference_p, heap) **);
struct data_reference *create_data_ref (struct loop *, tree, tree, bool);
bool find_loop_nest (struct loop *, VEC (loop_p, heap) **);
void compute_all_dependences (VEC (data_reference_p, heap) *,
VEC (ddr_p, heap) **, VEC (loop_p, heap) *, bool);
+extern void create_rdg_vertices (struct graph *, VEC (tree, heap) *);
+extern bool dr_may_alias_p (const struct data_reference *,
+ const struct data_reference *);
+
/* Return true when the DDR contains two data references that have the
same access functions. */
@@ -511,15 +525,21 @@ typedef struct rdg_edge
/* Type of the dependence. */
enum rdg_dep_type type;
- /* Levels of the dependence: the depth of the loops that
- carry the dependence. */
+ /* Levels of the dependence: the depth of the loops that carry the
+ dependence. */
unsigned level;
+
+ /* Dependence relation between data dependences, NULL when one of
+ the vertices is a scalar. */
+ ddr_p relation;
} *rdg_edge_p;
#define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
#define RDGE_LEVEL(E) ((struct rdg_edge *) ((E)->data))->level
+#define RDGE_RELATION(E) ((struct rdg_edge *) ((E)->data))->relation
struct graph *build_rdg (struct loop *);
+struct graph *build_empty_rdg (int);
void free_rdg (struct graph *);
/* Return the index of the variable VAR in the LOOP_NEST array. */
@@ -564,4 +584,18 @@ bool lambda_compute_access_matrices (VEC
/* In tree-data-refs.c */
void split_constant_offset (tree , tree *, tree *);
+/* Strongly connected components of the reduced data dependence graph. */
+
+typedef struct rdg_component
+{
+ int num;
+ VEC (int, heap) *vertices;
+} *rdgc;
+
+DEF_VEC_P (rdgc);
+DEF_VEC_ALLOC_P (rdgc, heap);
+
+DEF_VEC_P (bitmap);
+DEF_VEC_ALLOC_P (bitmap, heap);
+
#endif /* GCC_TREE_DATA_REF_H */
Index: gcc/tree-dfa.c
===================================================================
--- gcc/tree-dfa.c (.../trunk) (revision 138072)
+++ gcc/tree-dfa.c (.../branches/graphite) (revision 138161)
@@ -526,11 +526,12 @@ collect_dfa_stats (struct dfa_stats_d *d
memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
- /* Walk all the trees in the function counting references. Start at
- basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries. */
+ /* Walk all the trees in the function counting references. Start
+ with the successor of the entry block, but don't stop at block
+ boundaries. */
pset = pointer_set_create ();
- for (i = bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
+ for (i = bsi_start (single_succ (ENTRY_BLOCK_PTR));
!bsi_end_p (i); bsi_next (&i))
walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
pset);
Index: gcc/lambda.h
===================================================================
--- gcc/lambda.h (.../trunk) (revision 138072)
+++ gcc/lambda.h (.../branches/graphite) (revision 138161)
@@ -39,6 +39,9 @@ DEF_VEC_ALLOC_P (lambda_vector_vec_p, he
all vectors are the same length). */
typedef lambda_vector *lambda_matrix;
+DEF_VEC_P (lambda_matrix);
+DEF_VEC_ALLOC_P (lambda_matrix, heap);
+
/* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
matrix. Rather than use floats, we simply keep a single DENOMINATOR that
represents the denominator for every element in the matrix. */
@@ -213,6 +216,7 @@ void lambda_loopnest_to_gcc_loopnest (st
lambda_loopnest, lambda_trans_matrix,
struct obstack *);
void remove_iv (tree);
+tree find_induction_var_from_exit_cond (struct loop *);
static inline void lambda_vector_negate (lambda_vector, lambda_vector, int);
static inline void lambda_vector_mult_const (lambda_vector, lambda_vector, int, int);
@@ -374,6 +378,33 @@ lambda_vector_matrix_mult (lambda_vector
dest[i] += mat[j][i] * vect[j];
}
+/* Compare two vectors returning an integer less than, equal to, or
+ greater than zero if the first argument is considered to be respectively
+ less than, equal to, or greater than the second.
+ We use the lexicographic order. */
+
+static inline int
+lambda_vector_compare (lambda_vector vec1, int length1, lambda_vector vec2,
+ int length2)
+{
+ int min_length;
+ int i;
+
+ if (length1 < length2)
+ min_length = length1;
+ else
+ min_length = length2;
+
+ for (i = 0; i < min_length; i++)
+ if (vec1[i] < vec2[i])
+ return -1;
+ else if (vec1[i] > vec2[i])
+ return 1;
+ else
+ continue;
+
+ return length1 - length2;
+}
/* Print out a vector VEC of length N to OUTFILE. */
Index: gcc/common.opt
===================================================================
--- gcc/common.opt (.../trunk) (revision 138072)
+++ gcc/common.opt (.../branches/graphite) (revision 138161)
@@ -543,6 +543,22 @@ Common Report Var(flag_gcse_after_reload
Perform global common subexpression elimination after register allocation
has finished
+fgraphite
+Common Report Var(flag_graphite)
+Enable in and out of Graphite representation, not modifying the compiled program
+
+floop-strip-mine
+Common Report Var(flag_loop_strip_mine) Optimization
+Enable Loop Strip Mining transformation
+
+floop-interchange
+Common Report Var(flag_loop_interchange) Optimization
+Enable Loop Interchange transformation
+
+floop-block
+Common Report Var(flag_loop_block) Optimization
+Enable Loop Blocking transformation
+
fguess-branch-probability
Common Report Var(flag_guess_branch_prob) Optimization
Enable guessing of branch probabilities
Index: gcc/lambda-code.c
===================================================================
--- gcc/lambda-code.c (.../trunk) (revision 138072)
+++ gcc/lambda-code.c (.../branches/graphite) (revision 138161)
@@ -147,7 +147,6 @@ static lambda_lattice lambda_lattice_new
static lambda_lattice lambda_lattice_compute_base (lambda_loopnest,
struct obstack *);
-static tree find_induction_var_from_exit_cond (struct loop *);
static bool can_convert_to_perfect_nest (struct loop *);
/* Create a new lambda body vector. */
@@ -1436,7 +1435,7 @@ gcc_loop_to_lambda_loop (struct loop *lo
/* Given a LOOP, find the induction variable it is testing against in the exit
condition. Return the induction variable if found, NULL otherwise. */
-static tree
+tree
find_induction_var_from_exit_cond (struct loop *loop)
{
tree expr = get_loop_exit_condition (loop);
Index: gcc/cfgloop.h
===================================================================
--- gcc/cfgloop.h (.../trunk) (revision 138072)
+++ gcc/cfgloop.h (.../branches/graphite) (revision 138161)
@@ -279,6 +279,8 @@ extern bool can_duplicate_loop_p (const
#define DLTHE_FLAG_COMPLETTE_PEEL 4 /* Update frequencies expecting
a complete peeling. */
+extern struct loop *create_empty_loop_on_edge (edge, tree, tree, tree, tree,
+ tree *, struct loop *);
extern struct loop * duplicate_loop (struct loop *, struct loop *);
extern bool duplicate_loop_to_header_edge (struct loop *, edge,
unsigned, sbitmap, edge,
Index: gcc/tree-flow.h
===================================================================
--- gcc/tree-flow.h (.../trunk) (revision 138072)
+++ gcc/tree-flow.h (.../branches/graphite) (revision 138161)
@@ -727,6 +727,7 @@ tree copy_var_decl (tree, tree, tree);
/* Location to track pending stmt for edge insertion. */
#define PENDING_STMT(e) ((e)->insns.t)
+extern void remove_bb (basic_block bb);
extern void delete_tree_cfg_annotations (void);
extern bool stmt_ends_bb_p (const_tree);
extern bool is_ctrl_stmt (const_tree);
@@ -835,6 +836,8 @@ extern void reserve_phi_args_for_new_edg
extern tree create_phi_node (tree, basic_block);
extern void add_phi_arg (tree, tree, edge);
extern void remove_phi_args (edge);
+extern void resize_phi_node (tree *, int);
+extern void move_phi_node (tree, basic_block);
extern void remove_phi_node (tree, tree, bool);
extern tree phi_reverse (tree);
extern void init_phinodes (void);
@@ -1071,6 +1074,7 @@ bool tree_duplicate_loop_to_header_edge
int);
struct loop *slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *, edge);
void rename_variables_in_loop (struct loop *);
+void rename_variables_in_bb (basic_block bb);
struct loop *tree_ssa_loop_version (struct loop *, tree,
basic_block *);
tree expand_simple_operations (tree);
@@ -1157,6 +1161,10 @@ bool sra_type_can_be_decomposed_p (tree)
/* In tree-loop-linear.c */
extern void linear_transform_loops (void);
+extern unsigned perfect_loop_nest_depth (struct loop *);
+
+/* In graphite.c */
+extern void graphite_transform_loops (void);
/* In tree-data-ref.c */
extern void tree_check_data_deps (void);
Index: gcc/tree-cfg.c
===================================================================
--- gcc/tree-cfg.c (.../trunk) (revision 138072)
+++ gcc/tree-cfg.c (.../branches/graphite) (revision 138161)
@@ -107,7 +107,6 @@ static bool computed_goto_p (const_tree)
/* Flowgraph optimization and cleanup. */
static void tree_merge_blocks (basic_block, basic_block);
static bool tree_can_merge_blocks_p (basic_block, basic_block);
-static void remove_bb (basic_block);
static edge find_taken_edge_computed_goto (basic_block, tree);
static edge find_taken_edge_cond_expr (basic_block, tree);
static edge find_taken_edge_switch_expr (basic_block, tree);
@@ -2031,7 +2030,7 @@ remove_phi_nodes_and_edges_for_unreachab
/* Remove statements of basic block BB. */
-static void
+void
remove_bb (basic_block bb)
{
block_stmt_iterator i;
@@ -6495,7 +6494,7 @@ print_loops (FILE *file, int verbosity)
{
basic_block bb;
- bb = BASIC_BLOCK (NUM_FIXED_BLOCKS);
+ bb = ENTRY_BLOCK_PTR;
if (bb && bb->loop_father)
print_loop_and_siblings (file, bb->loop_father, 0, verbosity);
}
Index: gcc/passes.c
===================================================================
--- gcc/passes.c (.../trunk) (revision 138072)
+++ gcc/passes.c (.../branches/graphite) (revision 138161)
@@ -667,6 +667,7 @@ init_optimization_passes (void)
NEXT_PASS (pass_check_data_deps);
NEXT_PASS (pass_loop_distribution);
NEXT_PASS (pass_linear_transform);
+ NEXT_PASS (pass_graphite_transforms);
NEXT_PASS (pass_iv_canon);
NEXT_PASS (pass_if_conversion);
NEXT_PASS (pass_vectorize);