[graphite] Backend fixes

[graphite] Backend fixes

[Tobias Grosser]

[-- Attachment #1: Type: text/plain, Size: 2085 bytes --]

Hi,

Jan committed on Saturday some large parts for the code generation. Here
the next fixes to hit some more bugs.


Always generate graphite code.
==============================

 * graphite.c (graphite_transform_loops): Always call gloog and
 find_transform.

At the moment we call the GRAPHITE code generation only, if we applied a
transformation like "-floop-block". GRAPHITE does not change the CFG,
if we call gcc only with "-fgraphite",

I propose to always generate code, if "-fgraphite" is enables. This has
some advantages.

 - Better code coverage -> More testing of the backend
 - We can check the performance for a NULL transformation
   GIMPLE -> GRAPHITE -> GIMPLE
 - If cloog optimizations are not disabled, the cloog output is
   always optimized in control flow.

   for (i = 0; i < 100; i ++)
 	if (i < 30 && i > 60)
 		A
   becomes
   for (i = 0; i < 30; i++)
 	A
   for (i = 61; i < 100; i++)
 	A

Patch: graphite-Always_generate_graphite_code_2008-08-25.patch


Disable cloog optimizations
===========================

 * graphite.c (set_cloog_options): Disable optimizations.

Cloog optimizes the output in control flow.

Example:

          for (i = 0; i < 100; i ++)
                if (i < 30 && i > 60)
                        A
          becomes:

          for (i = 0; i < 30; i++)
                A
          for (i = 61; i < 100; i++)
                A

This breaks the current code generation, as some bbs may appear twice
or more often in the clast output.

Wait until codegen is updated.

Patch: graphite-Disable_cloog_optimizations_2008-08-25.patch


Fix SEGFAULT in remove_cond_exprs
=================================

 graphite.c (remove_cond_exprs): Do not fail on empty bbs.

Patch: graphite-Fix_SEGFAULT_in_remove_cond_exprs_2008-08-25.patch


Update dominator info
=====================

 * graphite.c (gloog): Update dominator info.

Patch: graphite-Update_dominator_info_2008-08-25.patch


Together with my latest cloog-ppl patch graphite can generate code for
the first SCoPs. That means we pass about half of the Polyhedron.

See you
Tobi

[-- Attachment #2: graphite-Always_generate_graphite_code_2008-08-25.patch --]
[-- Type: text/x-patch, Size: 1965 bytes --]

Always generate graphite code.

2008-08-25  Tobias Grosser  <grosser@fim.uni-passau.de>

	* graphite.c (graphite_transform_loops): Always call gloog and
	find_transform.

At the moment we call the GRAPHITE code generation only, if we applied a
transformation like "-floop-block". GRAPHITE does not change the CFG,
if we call gcc only with "-fgraphite",

I propose to always generate code, if "-fgraphite" is enables. This has
some advantages.

	- Better code coverage -> More testing of the backend
	- We can check the performance for a NULL transformation
	  GIMPLE -> GRAPHITE -> GIMPLE
	- If cloog optimizations are not disabled, the cloog output is
	  always optimized in control flow.

	  for (i = 0; i < 100; i ++)
		if (i < 30 && i > 60)
			A
	  becomes
	  for (i = 0; i < 30; i++)
		A
	  for (i = 61; i < 100; i++)
		A

diff --git a/gcc/graphite.c b/gcc/graphite.c
index 9ff9cd0..b3ded30 100644
--- a/gcc/graphite.c
+++ b/gcc/graphite.c
@@ -4496,16 +4496,15 @@ graphite_transform_loops (void)
 	  fprintf (dump_file, "\nnumber of data refs: %d\n", nbrefs);
 	}
 
-      /* We only build new graphite code, if we applied a transformation. But
-         call find_transform always to get more test coverage during
-         developement.  */
-      if (graphite_apply_transformations (scop))
+      /* Always generate code, even if we did not apply any transformation.
+	 Reason:
+        - Better code coverage -> More testing of the backend
+        - We can check the performance for a NULL transformation 
+          GIMPLE -> GRAPHITE -> GIMPLE
+        - If cloog optimizations are not disabled, the cloog output is
+          always optimized in control flow.  */
+      if (1 || graphite_apply_transformations (scop))
         gloog (scop, find_transform (scop));
-      else
-        {
-          struct clast_stmt* stmt = find_transform (scop);
-          cloog_clast_free (stmt);
-        }
     }
 
   if (dump_file && (dump_flags & TDF_DETAILS))

[-- Attachment #3: graphite-Disable_cloog_optimizations_2008-08-25.patch --]
[-- Type: text/x-patch, Size: 1309 bytes --]

Disable cloog optimizations

2008-08-25  Tobias Grosser  <grosser@fim.uni-passau.de>

	* graphite.c (set_cloog_options): Disable optimizations.

Cloog optimizes the output in control flow.

Example:

          for (i = 0; i < 100; i ++)
                if (i < 30 && i > 60)
                        A
          becomes:

          for (i = 0; i < 30; i++)
                A
          for (i = 61; i < 100; i++)
                A

This breaks the current code generation, as some bbs may appear twice
or more often in the clast output.

Wait until codegen is updated.

diff --git a/gcc/graphite.c b/gcc/graphite.c
index b3ded30..38940b2 100644
--- a/gcc/graphite.c
+++ b/gcc/graphite.c
@@ -3247,9 +3247,18 @@ set_cloog_options (void)
      input.  This is useful for debugging,  but later we want the optimized
      code.
 
-     XXX: We can not disable optimizations, as loop blocking is not working
-     without them.  */
-  if (0)
+     Cloog optimizes the code in control flow.
+
+     Example:
+          for (i = 0; i < 100; i ++)
+                if (i < 30 && i > 60)
+                        A
+          becomes
+          for (i = 0; i < 30; i++)
+                A
+          for (i = 61; i < 100; i++)
+                A  */
+  if (1)
     {
       options->f = -1;
       options->l = INT_MAX;

[-- Attachment #4: graphite-Fix_SEGFAULT_in_remove_cond_exprs_2008-08-25.patch --]
[-- Type: text/x-patch, Size: 642 bytes --]

Fix SEGFAULT in remove_cond_exprs

2008-08-25  Tobias Grosser  <grosser@fim.uni-passau.de>

	graphite.c (remove_cond_exprs): Do not fail on empty bbs.

diff --git a/gcc/graphite.c b/gcc/graphite.c
index 38940b2..5316833 100644
--- a/gcc/graphite.c
+++ b/gcc/graphite.c
@@ -3001,7 +3001,9 @@ move_phi_nodes (scop_p scop, loop_p old_loop_father, basic_block from,
 static void
 remove_cond_exprs (basic_block bb)
 {
-  if (gimple_code (last_stmt (bb)) == GIMPLE_COND)
+  gimple last = last_stmt (bb);
+
+  if (last && gimple_code (last) == GIMPLE_COND)
     {
       gimple_stmt_iterator gsi = gsi_last_bb (bb);
       gsi_remove (&gsi, true);

[-- Attachment #5: graphite-Update_dominator_info_2008-08-25.patch --]
[-- Type: text/x-patch, Size: 1236 bytes --]

Update dominator info

2008-08-25  Tobias Grosser  <grosser@fim.uni-passau.de>

	* graphite.c (gloog): Update dominator info.

diff --git a/gcc/graphite.c b/gcc/graphite.c
index 5316833..2a1ddd3 100644
--- a/gcc/graphite.c
+++ b/gcc/graphite.c
@@ -3637,6 +3637,14 @@ gloog (scop_p scop, struct clast_stmt *stmt)
 					construction_edge->src->loop_father,
 					stmt, construction_edge, &ivstack);
   redirect_edge_succ (new_scop_exit_edge, scop_exit);
+  if (!old_scop_exit_idom
+      || !dominated_by_p (CDI_DOMINATORS, SCOP_ENTRY (scop),
+			  old_scop_exit_idom)
+      || SCOP_ENTRY (scop) == old_scop_exit_idom)
+    set_immediate_dominator (CDI_DOMINATORS,
+			     new_scop_exit_edge->dest,
+			     new_scop_exit_edge->src);
+
   cloog_clast_free (stmt);
 
   if (new_scop_exit_edge->dest == EXIT_BLOCK_PTR)
@@ -3649,12 +3657,6 @@ gloog (scop_p scop, struct clast_stmt *stmt)
   patch_phis_for_virtual_defs ();
 
   find_unreachable_blocks ();
-  if (old_scop_exit_idom 
-      && !(old_scop_exit_idom->flags & BB_REACHABLE))
-    set_immediate_dominator (CDI_DOMINATORS,
-			     new_scop_exit_edge->dest,
-			     new_scop_exit_edge->src);
-
   delete_unreachable_blocks();
   mark_old_loops (scop);
   remove_dead_loops ();

Re: [graphite] Backend fixes

[Jack Howarth]

On Mon, Aug 25, 2008 at 05:58:22AM -0300, Tobias Grosser wrote:
> Hi,
> 
> Jan committed on Saturday some large parts for the code generation. Here
> the next fixes to hit some more bugs.
> 
> 
> Always generate graphite code.
> ==============================
> 

Tobias,
     The situation regarding code generation from graphite is still a bit confusing.
Sebastian left me with the impression that the bottleneck preventing the backend
from generating code from the new loop optimizations in graphite was the absence
of simplification operation in ppl. I also was given the impression that code
generation would work fine with cloog/graphite/polylib since it already had the
simplification operation. You proposed patch seems to indicate that graphite wasn't
really wired up to generate code in the back end at all yet. Is that a correct
reading of the situation? Also, is it correct to say that graphite's code generation
was always designed to be done by converting the GIMPLE to GRAPHITE representations,
processing these with ppl/cloog and reconverting the results back into GIMPLE for
final code generation?
                   Jack

Re: [graphite] Backend fixes

[Jack Howarth]

On Mon, Aug 25, 2008 at 05:58:22AM -0300, Tobias Grosser wrote:
> Hi,
> 
> Jan committed on Saturday some large parts for the code generation. Here
> the next fixes to hit some more bugs.
> 
> 
Tobias,
   FYI, the patches in the graphite branch, as applied to gcc trunk
and built against current cloog-git and ppl 1.0-pre24 are still failing
gcc.dg/graphite/block-1.c and gcc.dg/graphite/scop-16.c on i686 Darwin9.
                     Jack

Re: [graphite] Backend fixes

[Tobias Grosser]

Hi Jack,

> Tobias,
>      The situation regarding code generation from graphite is still a bit confusing.
> Sebastian left me with the impression that the bottleneck preventing the backend
> from generating code from the new loop optimizations in graphite was the absence
> of simplification operation in ppl. I also was given the impression that code
> generation would work fine with cloog/graphite/polylib since it already had the
> simplification operation. You proposed patch seems to indicate that graphite wasn't
> really wired up to generate code in the back end at all yet. Is that a correct
> reading of the situation?
The situation is like this (as I see it, so please correct me, if I am
wrong)

Our backend supported a limited extend of the graphite representation
and was designed to be extended. The main missing part (that Jan
committed on Saturday) was support for conditional statements, as they
where not necessary for simple loops we wanted to loop block.

The problem with cloog-ppl was, that this port always generated useless
conditions in every loop nest. So we where not able to generate any
code.

This situation has improved much, as I sent Sebastian a mail that fixes
cloog (I hope he commits this soon) and Jan has added condition support
on Saturday.

So the main problem seems to be fixed.

> Also, is it correct to say that graphite's code generation
> was always designed to be done by converting the GIMPLE to GRAPHITE representations,
> processing these with ppl/cloog and reconverting the results back into GIMPLE for
> final code generation?
Yes seems correct. At least for my last year in graphite.

See you
Tobi

Re: [graphite] Backend fixes

[Jack Howarth]

On Mon, Aug 25, 2008 at 11:50:06AM -0300, Tobias Grosser wrote:
> Hi Jack,
> 
> Our backend supported a limited extend of the graphite representation
> and was designed to be extended. The main missing part (that Jan
> committed on Saturday) was support for conditional statements, as they
> where not necessary for simple loops we wanted to loop block.
> 
> The problem with cloog-ppl was, that this port always generated useless
> conditions in every loop nest. So we where not able to generate any
> code.
> 
> This situation has improved much, as I sent Sebastian a mail that fixes
> cloog (I hope he commits this soon) and Jan has added condition support
> on Saturday.
> 
> So the main problem seems to be fixed.
> 

Tobias,
     Thanks for the clarifications. One other issue with regard to
the Graphite wiki. When I follow the instructions for getting the
cloog-ppl git...

cd cloog
git-init
git-pull git://repo.or.cz/cloog-ppl.git

I find that when I later try to update with 'git pull', I
get the errors...

fatal: 'origin': unable to chdir or not a git archive
fatal: The remote end hung up unexpectedly

You might want to update the Graphite wiki to cover that
as well. Currently, I have to delete the cloog directory
and repeat the previous steps to get the current cloog-ppl
git.
                       Jack

Re: [graphite] Backend fixes

[Jack Howarth]

Tobias,
   If the instructions in the Graphite wiki are changed to..

git clone git://repo.or.cz/cloog-ppl.git cloog

...instead of...

git-init
git-pull git://repo.or.cz/cloog-ppl.git

...the resulting cloog directory allows git pull to work.
                      Jack

Re: [graphite] Backend fixes

[Sebastian Pop]

On Mon, Aug 25, 2008 at 10:36 AM, Jack Howarth
<howarth@bromo.msbb.uc.edu> wrote:
> Tobias,
>   If the instructions in the Graphite wiki are changed to..
>
> git clone git://repo.or.cz/cloog-ppl.git cloog
>
> ...instead of...
>
> git-init
> git-pull git://repo.or.cz/cloog-ppl.git
>
> ...the resulting cloog directory allows git pull to work.

I fixed the wiki page.  In the future, please do change it as needed.

Thanks,
Sebastian

Re: [graphite] Backend fixes

[Sebastian Pop]

On Mon, Aug 25, 2008 at 3:58 AM, Tobias Grosser
<grosser@fim.uni-passau.de> wrote:
>  * graphite.c (graphite_transform_loops): Always call gloog and
>  find_transform.

I will commit that part within #ifdef ENABLE_CHECKING: it makes
no sense to put an identity transform in the production compilers.

Sebastian

Re: [graphite] Backend fixes

[Sebastian Pop]

> Disable cloog optimizations
> ===========================
>
>  * graphite.c (set_cloog_options): Disable optimizations.
>
> Cloog optimizes the output in control flow.
>
> Example:
>
>          for (i = 0; i < 100; i ++)
>                if (i < 30 && i > 60)
>                        A
>          becomes:
>
>          for (i = 0; i < 30; i++)
>                A
>          for (i = 61; i < 100; i++)
>                A
>
> This breaks the current code generation, as some bbs may appear twice
> or more often in the clast output.
>

For fixing this one, we're replacing the bb_move with a bb_copy such
that we can handle also multiple copies of A.  This triggers also the
need of another cleanup for induction variables: we need exactly one
IV per loop, otherwise we end up with variable definitions that
disappears, as not renamed or moved along from the old loop.

Sebastian

Re: [graphite] Backend fixes

[Sebastian Pop]

[-- Attachment #1: Type: text/plain, Size: 1417 bytes --]

>  * graphite.c (graphite_transform_loops): Always call gloog and
>  find_transform.

I propose to commit the attached patch when the testsuite will pass
correctly with it: for the moment it shows

FAIL: gcc.dg/graphite/block-1.c (internal compiler error)
FAIL: gcc.dg/graphite/block-1.c (test for excess errors)
FAIL: gcc.dg/graphite/block-1.c scan-tree-dump-times graphite "Loop blocked" 3
FAIL: gcc.dg/graphite/scop-16.c (internal compiler error)
FAIL: gcc.dg/graphite/scop-16.c (test for excess errors)
FAIL: gcc.dg/graphite/scop-17.c (internal compiler error)
FAIL: gcc.dg/graphite/scop-17.c (test for excess errors)
FAIL: gcc.dg/graphite/scop-18.c (internal compiler error)
FAIL: gcc.dg/graphite/scop-18.c (test for excess errors)
FAIL: gcc.dg/graphite/scop-2.c (internal compiler error)
FAIL: gcc.dg/graphite/scop-2.c (test for excess errors)
FAIL: gcc.dg/graphite/scop-2.c scan-tree-dump-times graphite "number
of SCoPs: 4" 1
FAIL: gcc.dg/graphite/scop-7.c (internal compiler error)
FAIL: gcc.dg/graphite/scop-7.c (test for excess errors)
FAIL: gcc.dg/graphite/scop-7.c scan-tree-dump-times graphite "number
of SCoPs: 3" 1

FAIL: gfortran.dg/graphite/block-1.f90  -O  (internal compiler error)
FAIL: gfortran.dg/graphite/block-1.f90  -O  (test for excess errors)
FAIL: gfortran.dg/graphite/block-1.f90  -O  scan-tree-dump-times
graphite "Loop blocked" 2
got a INT signal, interrupted by user

last one hangs.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 1190_gloog.diff --]
[-- Type: text/x-patch; name=1190_gloog.diff, Size: 2295 bytes --]

Index: graphite.c
===================================================================
--- graphite.c	(revision 139564)
+++ graphite.c	(working copy)
@@ -4392,6 +4392,7 @@ static bool
 graphite_apply_transformations (scop_p scop)
 {
   bool transform_done = false;
+
   /* Sort the list of bbs.  Keep them always sorted.  */
   graphite_sort_gbbs (scop);
   scop_remove_ignoreable_gbbs (scop);
@@ -4399,10 +4400,21 @@ graphite_apply_transformations (scop_p s
   if (flag_loop_block)
     transform_done = graphite_trans_scop_block (scop);
 
+#ifdef ENABLE_CHECKING
+  /* When the compiler is configured with ENABLE_CHECKING, always
+     generate code, even if we did not apply any transformation.  This
+     provides better code coverage of the backend code generator.
+
+     This also allows to check the performance for an identity
+     transform: GIMPLE -> GRAPHITE -> GIMPLE; and the output of CLooG
+     is never an identity: if CLooG optimizations are not disabled,
+     the CLooG output is always optimized in control flow.  */
+  transform_done = true;
+#endif
+
   return transform_done;
 }
 
-
 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop. 
 
    Example:
@@ -4503,16 +4515,8 @@ graphite_transform_loops (void)
 	  fprintf (dump_file, "\nnumber of data refs: %d\n", nbrefs);
 	}
 
-      /* We only build new graphite code, if we applied a transformation. But
-         call find_transform always to get more test coverage during
-         developement.  */
       if (graphite_apply_transformations (scop))
         gloog (scop, find_transform (scop));
-      else
-        {
-          struct clast_stmt* stmt = find_transform (scop);
-          cloog_clast_free (stmt);
-        }
     }
 
   if (dump_file && (dump_flags & TDF_DETAILS))
Index: ChangeLog.graphite
===================================================================
--- ChangeLog.graphite	(revision 139564)
+++ ChangeLog.graphite	(working copy)
@@ -1,4 +1,10 @@
 2008-08-25  Tobias Grosser  <grosser@fim.uni-passau.de>
+	    Sebastian Pop  <sebastian.pop@amd.com>
+
+	* graphite.c (graphite_transform_loops): Always enable gloog
+	and find_transform when ENABLE_CHECKING.
+
+2008-08-25  Tobias Grosser  <grosser@fim.uni-passau.de>
 
 	* graphite.c (gloog): Update dominator info.
 

Re: [graphite] Backend fixes

[Joseph S. Myers]

On Mon, 25 Aug 2008, Jack Howarth wrote:

> Tobias,
>      Thanks for the clarifications. One other issue with regard to
> the Graphite wiki. When I follow the instructions for getting the
> cloog-ppl git...
> 
> cd cloog
> git-init
> git-pull git://repo.or.cz/cloog-ppl.git

For the mainline merge (or certainly well before 4.4 branches) we need 
documentation in install.texi, not just the wiki, pointing to release 
tarballs, not git repositories, in the gcc.gnu.org infrastructure 
directory.

-- 
Joseph S. Myers
joseph@codesourcery.com