Re: [PATCH] remove dead code used by the old cloog scheduler

[Tobias Grosser]

On 10/06/2015 05:45 PM, Sebastian Pop wrote:

2015-10-05  Aditya Kumar  
 Sebastian Pop  

 * graphite-dependences.c (scop_get_transformed_schedule): 
Remove.
 (no_violations): Remove.
 (subtract_commutative_associative_deps): Remove.
 (compute_deps): Do not call 
subtract_commutative_associative_deps.
 (transform_is_safe): Remove.
 (graphite_legal_transform): Remove.
 * graphite-poly.h (graphite_legal_transform): Remove.


LGTM.

Tobias

---
  gcc/graphite-dependences.c | 255 +
  gcc/graphite-poly.h|   3 -
  2 files changed, 1 insertion(+), 257 deletions(-)

diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
index e39394a..2c4f92c 100644
--- a/gcc/graphite-dependences.c
+++ b/gcc/graphite-dependences.c
@@ -154,26 +154,6 @@ scop_get_original_schedule (scop_p scop, vec 
pbbs)
return res;
  }

-/* Returns all the transformed schedules in SCOP.  */
-
-static isl_union_map *
-scop_get_transformed_schedule (scop_p scop, vec pbbs)
-{
-  int i;
-  poly_bb_p pbb;
-  isl_space *space = isl_set_get_space (scop->context);
-  isl_union_map *res = isl_union_map_empty (space);
-
-  FOR_EACH_VEC_ELT (pbbs, i, pbb)
-{
-  res = isl_union_map_add_map
-   (res, constrain_domain (isl_map_copy (pbb->transformed),
-   isl_set_copy (pbb->domain)));
-}
-
-  return res;
-}
-
  /* Helper function used on each MAP of a isl_union_map.  Computes the
 maximal output dimension.  */

@@ -262,33 +242,6 @@ apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
return x;
  }

-/* Return true when SCHEDULE does not violate the data DEPS: that is
-   when the intersection of LEX with the DEPS transformed by SCHEDULE
-   is empty.  LEX is the relation in which the outputs occur before
-   the inputs.  */
-
-static bool
-no_violations (__isl_keep isl_union_map *schedule,
-  __isl_keep isl_union_map *deps)
-{
-  bool res;
-  isl_space *space;
-  isl_map *lex, *x;
-
-  if (isl_union_map_is_empty (deps))
-return true;
-
-  x = apply_schedule_on_deps (schedule, deps);
-  space = isl_map_get_space (x);
-  space = isl_space_range (space);
-  lex = isl_map_lex_ge (space);
-  x = isl_map_intersect (x, lex);
-  res = isl_map_is_empty (x);
-
-  isl_map_free (x);
-  return res;
-}
-
  /* Return true when DEPS is non empty and the intersection of LEX with
 the DEPS transformed by SCHEDULE is non empty.  LEX is the relation
 in which all the inputs before DEPTH occur at the same time as the
@@ -332,161 +285,6 @@ carries_deps (__isl_keep isl_union_map *schedule,
return res;
  }

-/* Subtract from the RAW, WAR, and WAW dependences those relations
-   that have been marked as belonging to an associative commutative
-   reduction.  */
-
-static void
-subtract_commutative_associative_deps (scop_p scop,
-  vec pbbs,
-  isl_union_map *original,
-  isl_union_map **must_raw,
-  isl_union_map **may_raw,
-  isl_union_map **must_raw_no_source,
-  isl_union_map **may_raw_no_source,
-  isl_union_map **must_war,
-  isl_union_map **may_war,
-  isl_union_map **must_war_no_source,
-  isl_union_map **may_war_no_source,
-  isl_union_map **must_waw,
-  isl_union_map **may_waw,
-  isl_union_map **must_waw_no_source,
-  isl_union_map **may_waw_no_source)
-{
-  int i, j;
-  poly_bb_p pbb;
-  poly_dr_p pdr;
-  isl_space *space = isl_set_get_space (scop->context);
-
-  FOR_EACH_VEC_ELT (pbbs, i, pbb)
-if (PBB_IS_REDUCTION (pbb))
-  {
-   isl_union_map *r = isl_union_map_empty (isl_space_copy (space));
-   isl_union_map *must_w = isl_union_map_empty (isl_space_copy (space));
-   isl_union_map *may_w = isl_union_map_empty (isl_space_copy (space));
-   isl_union_map *all_w;
-   isl_union_map *empty;
-   isl_union_map *x_must_raw;
-   isl_union_map *x_may_raw;
-   isl_union_map *x_must_raw_no_source;
-   isl_union_map *x_may_raw_no_source;
-   isl_union_map *x_must_war;
-   isl_union_map *x_may_war;
-   isl_union_map *x_must_war_no_source;
-   isl_union_map *x_may_war_no_source;
-   isl_union_map *x_must_waw;
-   isl_union_map *x_may_waw;
-   isl_union_map *x_must_waw_no_source;
-   isl_union_map *x_may_waw_no_source;
-
-   FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
- if (pdr_read_p 

Re: [PATCH 1/3] remove dead code in computation of alias sets

[Tobias Grosser]

On 10/06/2015 10:45 PM, Sebastian Pop wrote:

2015-10-06  Aditya Kumar  
 Sebastian Pop  

 * graphite-poly.c (new_poly_dr): Remove dr_base_object_set.
 Do not set PDR_BASE_OBJECT_SET.
 * graphite-poly.h (poly_dr): Same.
 (PDR_BASE_OBJECT_SET): Remove.
 (new_poly_dr): Update decl.
 * graphite-sese-to-poly.c (build_poly_dr): Update call to
 new_poly_dr.
 (write_alias_graph_to_ascii_dimacs): Remove.
 (write_alias_graph_to_ascii_dot): Remove.
 (write_alias_graph_to_ascii_ecc): Remove.
 (dr_same_base_object_p): Remove.
 (build_alias_set_optimal_p): Rename build_alias_set.  Remove 
dead
 code.
 (build_base_obj_set_for_drs): Remove.
 (dump_alias_graphs): Remove.
 (build_scop_drs): Remove dead code.


All LGTM.

Tobias

Re: [PATCH 3/3] increase the number of parameters

[Tobias Grosser]

On October 2, 2015 10:44:00 PM GMT+01:00, Sebastian Pop  
wrote:
>---
> gcc/params.def   | 2 +-
> gcc/testsuite/gcc.dg/graphite/scop-sor.c | 3 +--
> 2 files changed, 2 insertions(+), 3 deletions(-)
>
>diff --git a/gcc/params.def b/gcc/params.def
>index 3f91992..da2c6a3 100644
>--- a/gcc/params.def
>+++ b/gcc/params.def
>@@ -835,7 +835,7 @@ DEFPARAM (PARAM_LOOP_BLOCK_TILE_SIZE,
> DEFPARAM (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS,
> "graphite-max-nb-scop-params",
> "maximum number of parameters in a SCoP",
>-3, 0, 0)
>+7, 0, 0)
> 
>/* Maximal number of basic blocks in the functions analyzed by
>Graphite.  */
> 
>diff --git a/gcc/testsuite/gcc.dg/graphite/scop-sor.c
>b/gcc/testsuite/gcc.dg/graphite/scop-sor.c
>index aec8b9c..ad5278a 100644
>--- a/gcc/testsuite/gcc.dg/graphite/scop-sor.c
>+++ b/gcc/testsuite/gcc.dg/graphite/scop-sor.c
>@@ -14,5 +14,4 @@ void sor(int N1, int N2){
> #pragma endscop
> }
> 
>-/* This requires more than 3 parameters.  */
>-/* { dg-final { scan-tree-dump-times "number of SCoPs: 0" 1 "graphite"
>} } */
>+/* { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite"
>} } */

Lgtm

Re: [PATCH] outline functions from stmt_simple_for_scop_p

[Tobias Grosser]

On 10/02/2015 06:54 AM, Aditya Kumar wrote:

From: hiraditya 

Outlined functions from stmt_simple_for_scop_p. No functional changes intended.
Passes regtest and bootstrap.

gcc/ChangeLog:

2015-10-01  Aditya Kumar  

 * graphite-scop-detection.c (stmt_has_side_effects): New function
   outlined from stmt_simple_for_scop_p.
 (graphite_can_represent_stmt): Same.
 (stmt_simple_for_scop_p): Moved code out of this function for better
 readability.


LGTM.

Tobias

Re: [PATCH 2/2] call scev analysis in scop-detection as in sese-to-poly

[Tobias Grosser]

On 10/01/2015 12:11 AM, Sebastian Pop wrote:

Before our rewrite of the scop detection, we used to not have a valid SESE
region under hand, and so we used to do more ad-hoc analysis of data references
by trying to prove that at all levels of a loop nest the data references would
be still valid.

Now that we have a valid SESE region, we can call the scev analysis in the same
way on the same computed loop nest in the scop-detection as in the sese-to-poly.

Next step will be to cache the data references analyzed in the scop detection
and not compute the same info in sese-to-poly.

The patch fixes block-1.f90 that used to ICE on x86_64-linux when compiled with
-m32.  Patch passed bootstrap with BOOT_CFLAGS="-g -O2 -fgraphite-identity
-floop-nest-optimize" and check on x86_64-linux using ISL-0.15.


Nice.

Tobias

Re: [PATCH] correctly handle non affine data references

[Tobias Grosser]

On 10/01/2015 06:31 PM, Sebastian Pop wrote:

  create mode 100644 gcc/testsuite/gcc.dg/graphite/scop-pr66980.c

diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c



LGTM.

Tobias

Re: [PATCH] use sese_l throughout scop-detection

[Tobias Grosser]

On 10/01/2015 11:23 PM, Aditya Kumar wrote:

From: hiraditya 

Use sese_l throughout SCoP detection and create vec at the very end when
all SCoPs have been identified. 'struct sese_l' is very lightweight (two
pointers) compared to 'struct scop'.

No functional change intended. Passes regtest and bootstrap.


LGTM.

Tobias

Re: [PATCH] Rename gimple_bb to gimple_poly_bb

[Tobias Grosser]

On 10/01/2015 10:36 PM, Aditya Kumar wrote:

From: hiraditya 

Renaming gimple_bb to gimple_poly_bb because there is a function gimple_bb
by the same name in gimple.h. No functional change intended.
Passes regtest and bootstrap.


LGTM

Tobias

Re: [PATCH] remove dead code of commutative_reductions

[Tobias Grosser]

On 09/29/2015 06:26 PM, Sebastian Pop wrote:

This code is not used anymore after we removed the previous loop optimizer (not
based on the ISL scheduler.)  We will add back the detection of commutative
reductions after we improve the code generation of scalar dependences (by not
going out of SSA for scalar dependences just to expose them to the data
dependence graph.)

Patch passed bootstrap and check on x86_64-linux with ISL-0.15.
I will commit this patch to trunk.


LGTM.

Regarding the handling of scalars, Polly does this now by only virtually 
modeling
them as memory dependences, but leaving them as registers until code generation.
The final code generation is still done by alloca(ing) a memory slot and then
generating loads/stores from this memory slot. This is significantly easier than
trying to directly generate SSA again.

Best,
Tobias

Re: [PATCH] Make compute_deps, extend_schedule static

[Tobias Grosser]

On 09/29/2015 10:19 PM, Aditya Kumar wrote:

From: hiraditya 

No functional changes intended. Passes make check and bootstrap.


LGTM.

Tobias

Re: [PATCH] use MIN fusion for ISL-14

[Tobias Grosser]

On 09/30/2015 12:10 AM, Sebastian Pop wrote:

This patch fixes PR66754 by reverting an earlier unintended change.
We now generate a much simpler AST for interchange-1.c:

ISL AST generated by ISL:
{
   for (int c1 = 0; c1 <= 1334; c1 += 1) {
 S_7(c1);
 for (int c3 = 0; c3 <= 1334; c3 += 1)
   S_4(c1, c3);
 S_5(c1);
   }
   for (int c1 = 0; c1 <= 1334; c1 += 1)
 S_10(c1);
   S_8();
}


Sure. Out of interest. How did the AST look before? Also, does it
make sense to add a test case?

Best,
Tobias

Re: [Graphite] Redesign Graphite scop detection

[Tobias Grosser]

On 09/28/2015 03:30 AM, Aditya Kumar wrote:

From: hiraditya 

Redesign Graphite scop detection for faster compiler time and detecting more 
SCoPs.

Existing algorithm for SCoP detection in graphite was based on dominator tree
where a tree (CFG) traversal was required for analyzing an SESE. The tree
traversal is linear in the number of basic blocks and SCoP detection is
(probably) linear in number of instructions. That algorithm utilized a generic
infrastructure of SESE which does not directly represent loops.  With regards to
graphite framework, we are only interested in subtrees with loops. The new
algorithm is geared towards tree traversal on loop structure. The algorithm is
linear in number of loops which is faster than the previous algorithm.

Briefly, we start the traversal at a loop-nest and analyze it recursively for
validity. Once a valid loop is found we find a valid adjacent loop. If an
adjacent loop is found and is valid, we merge both loop nests otherwise we form
a SCoP from the previous loop nest, and resume the algorithm from the adjacent
loop nest. The data structure to represent an SESE is an ordered pair of edges
(entry, exit). The new algoritm can extend a SCoP in both the directions. With
this approach, the number of instructions to be analyzed for validity reduces to
a minimal set.  We start by analyzing those statements which are inside a loop,
because validity of those statements is necessary for the validity of loop. The
statements outside the loop nest can be just excluded from the SESE if they are
not valid.


I am generally fine with this, but please consider that when growing a SCoP 
certain
previous analysis may become invalid (an affine expression may suddenly become
non-affine as parameters that were previously scop-invariant may now be part of
the scop. Also, how are you planning to handle non-affine regions/loops. In 
polly
we can encapsulate non-affine loops and regions in bigger scops. To handle this,
I assume you would need to teach your patch to start growing regions even though
the innermost loops cannot be modeled precisely.

Best,
Tobias

Re: [PATCH] fix PR67700

[Tobias Grosser]

On 09/25/2015 10:39 PM, Sebastian Pop wrote:

The patch makes the detection of scop parameters in parameter_index_in_region a
bit more conservative by discarding scalar variables defined in function of data
references defined in the scop.

2015-09-25  Aditya Kumar  
 Sebastian Pop  

 PR tree-optimization/67700
 * graphite-sese-to-poly.c (parameter_index_in_region): Call
 invariant_in_sese_p_rec.
 (extract_affine): Same.
 (rewrite_cross_bb_scalar_deps): Call update_ssa.
 * sese.c (invariant_in_sese_p_rec): Export.  Handle vdefs and 
vuses.
 * sese.h (invariant_in_sese_p_rec): Declare.

 * testsuite/gcc.dg/graphite/run-id-pr67700.c: New.


LGTM.

Tobias

Re: [PATCH] Refactor optimize isl

[Tobias Grosser]

On 09/11/2015 07:07 PM, Aditya Kumar wrote:

Updated patch with corrections:

Refactor graphite-optimize-isl.c. Renamed function name, variable names etc.,
and indented the source according to gcc style guidelines.  Modified comments
accordingly. No functional change intended.


Looks reasonable.

Just for history, this code was copied from Polly this is why the formatting 
does
not match gcc's style. The relevant file in Polly has been evolved since then
and might provide you with ideas on how to improve this file in gcc.

Tobias


Passes regtest and bootstap on x86_64.

gcc/ChangeLog:

2015-09-10  Aditya Kumar  

 * graphite-optimize-isl.c (get_tile_map): Refactor.
 (get_schedule_for_band): Same.
 (getScheduleForBand): Same.
 (get_prevector_map): Same.
 (get_schedule_for_band_list): Same.
 (get_schedule_map): Same.
 (get_single_map): Same.
 (apply_schedule_map_to_scop): Same.
 (optimize_isl): Same.


---
  gcc/graphite-optimize-isl.c | 416 ++--
  1 file changed, 210 insertions(+), 206 deletions(-)

diff --git a/gcc/graphite-optimize-isl.c b/gcc/graphite-optimize-isl.c
index 811a510..e891e91 100644
--- a/gcc/graphite-optimize-isl.c
+++ b/gcc/graphite-optimize-isl.c
@@ -50,6 +50,9 @@ along with GCC; see the file COPYING3.  If not see
  #include "params.h"
  #include "dumpfile.h"

+/* Set this to true to disable tiling of nested loops.  */
+static bool disable_tiling = false;
+
  static isl_union_set *
  scop_get_domains (scop_p scop ATTRIBUTE_UNUSED)
  {
@@ -64,152 +67,153 @@ scop_get_domains (scop_p scop ATTRIBUTE_UNUSED)
return res;
  }

-/* getTileMap - Create a map that describes a n-dimensonal tiling.
-
-   getTileMap creates a map from a n-dimensional scattering space into an
+/* get_tile_map - Create a map that describes a n-dimensonal tiling.
+
+   get_tile_map creates a map from a n-dimensional scattering space into an
 2*n-dimensional scattering space. The map describes a rectangular tiling.
-
+
 Example:
- scheduleDimensions = 2, parameterDimensions = 1, tileSize = 32
-
-tileMap := [p0] -> {[s0, s1] -> [t0, t1, s0, s1]:
- t0 % 32 = 0 and t0 <= s0 < t0 + 32 and
- t1 % 32 = 0 and t1 <= s1 < t1 + 32}
-
+ SCHEDULE_DIMENSIONS = 2, PARAMETER_DIMENSIONS = 1, TILE_SIZE = 32
+
+tile_map := [p0] -> {[s0, s1] -> [t0, t1, s0, s1]:
+t0 % 32 = 0 and t0 <= s0 < t0 + 32 and
+t1 % 32 = 0 and t1 <= s1 < t1 + 32}
+
 Before tiling:
-
+
 for (i = 0; i < N; i++)
   for (j = 0; j < M; j++)
-   S(i,j)
-
+   S(i,j)
+
 After tiling:
-
+
 for (t_i = 0; t_i < N; i+=32)
   for (t_j = 0; t_j < M; j+=32)
-   for (i = t_i; i < min(t_i + 32, N); i++)  | Unknown that N % 32 = 0
- for (j = t_j; j < t_j + 32; j++)|   Known that M % 32 = 0
-   S(i,j)
-   */
-
+   for (i = t_i; i < min(t_i + 32, N); i++)  | Unknown that N % 32 = 0
+ for (j = t_j; j < t_j + 32; j++)|   Known that M % 32 = 0
+   S(i,j)
+  */
+
  static isl_basic_map *
-getTileMap (isl_ctx *ctx, int scheduleDimensions, int tileSize)
+get_tile_map (isl_ctx *ctx, int schedule_dimensions, int tile_size)
  {
-  int x;
/* We construct

- tileMap := [p0] -> {[s0, s1] -> [t0, t1, p0, p1, a0, a1]:
-   s0 = a0 * 32 and s0 = p0 and t0 <= p0 < t0 + 32 and
-   s1 = a1 * 32 and s1 = p1 and t1 <= p1 < t1 + 32}
+ tile_map := [p0] -> {[s0, s1] -> [t0, t1, p0, p1, a0, a1]:
+   s0 = a0 * 32 and s0 = p0 and t0 <= p0 < t0 + 32 and
+   s1 = a1 * 32 and s1 = p1 and t1 <= p1 < t1 + 32}

   and project out the auxilary dimensions a0 and a1.  */
-  isl_space *Space = isl_space_alloc (ctx, 0, scheduleDimensions,
- scheduleDimensions * 3);
-  isl_basic_map *tileMap = isl_basic_map_universe (isl_space_copy (Space));
+  isl_space *space
+  = isl_space_alloc (ctx, 0, schedule_dimensions, schedule_dimensions * 3);
+  isl_basic_map *tile_map = isl_basic_map_universe (isl_space_copy (space));

-  isl_local_space *LocalSpace = isl_local_space_from_space (Space);
+  isl_local_space *local_space = isl_local_space_from_space (space);

-  for (x = 0; x < scheduleDimensions; x++)
+  for (int x = 0; x < schedule_dimensions; x++)
  {
int sX = x;
int tX = x;
-  int pX = scheduleDimensions + x;
-  int aX = 2 * scheduleDimensions + x;
+  int pX = schedule_dimensions + x;
+  int aX = 2 * schedule_dimensions + x;

isl_constraint *c;

-  /* sX = aX * tileSize; */
-  c = isl_equality_alloc (isl_local_space_copy (LocalSpace));
+  /* sX = aX * tile_size; */
+  c = isl_equality_alloc (isl_local_space_copy (local_space));
isl_constraint_set_coefficient_si (c, isl_dim_out, sX, 

Re: [PATCH] Remove dead code from graphite-optimize-isl.c

[Tobias Grosser]

On 09/11/2015 07:29 PM, Aditya Kumar wrote:

The variable `static bool enable_polly_vector' is always assigned to false. 
This results in dead code in optimize-isl.c.
Removing the dead code. No functional change intended.


Fine with me as well. This code is used in Polly to enable outer loop 
vectorization with Polly.
It was historically disabled in gcc, as we missed heuristics to drive this. 
Again, it might
be worth looking into Polly's version of this code, which now works on schedule 
trees and
which is now a lot easier to read and work with.

Best,
Tobias

Re: [PATCH] [graphite] Remove limit_scops

[Tobias Grosser]

On 09/05/2015 12:57 AM, Aditya Kumar wrote:

This patch removes graphite-scop-detection.c:limit_scops function and fix
related issues arising because of that. The functionality limit_scop was added
as an intermediate step to discard the loops which graphite could not
handle. Removing limit_scop required handling of different cases of loops and
surrounding code.  The scop is now larger so most test cases required 'number of
scops detected' to be fixed. By increasing the size of scop we can now optimize
loops which are 'siblings' of each other. This could enable loop fusion on a
number of loops. Since in the graphite framework we mostly want to opimize
loop-nests/adjacent-loops, we now discard scops with less than 2 loops. We
also discard scops without any data references.


Essentially:
  - Remove limite_scops.
  - Only select scops when there are at least two loops (loop nest or, side by 
side).
  - Discard loops without data-refs.
  - Fix test cases.


Passes bootstrap and reg-test.


I did not check every detail, but conceptually this is looks good to me.

Tobias

Re: [PATCH] fix PR53852: stop ISL after a given number of operations

[Tobias Grosser]

On 09/03/2015 12:34 AM, Sebastian Pop wrote:

2015-09-02  Sebastian Pop  

 * config.in: Regenerate.
 * configure: Regenerate.
 * configure.ac (HAVE_ISL_CTX_MAX_OPERATIONS): Detect.
 * graphite-optimize-isl.c (optimize_isl): Stop computation when
 PARAM_MAX_ISL_OPERATIONS is reached.
 * params.def (PARAM_MAX_ISL_OPERATIONS): Add.

 * graphite-dependences.c (extend_schedule): Remove gcc_asserts on
 result equal to isl_stat_ok as the status now can be 
isl_error_quota.
 (subtract_commutative_associative_deps): Same.
 (compute_deps): Same.

testsuite/
 * gcc.dg/graphite/uns-interchange-12.c: Adjust pattern to pass with
 both isl-0.12 and isl-0.15.
 * gcc.dg/graphite/uns-interchange-14.c: Same.
 * gcc.dg/graphite/uns-interchange-15.c: Same.
 * gcc.dg/graphite/uns-interchange-mvt.c: Same.


Hi Sebastian,

this looks good to me.

Tobias

Re: [PATCH 0/2] Final cleanup in move to ISL

[Tobias Grosser]

On 08/27/2015 12:14 AM, Sebastian Pop wrote:

Hi,

Richi suggested at the Cauldron that it would be good to have graphite more
automatic and with fewer flags.  The first patch removes the -funroll-and-jam
pass that does not seem very stable or useful for now.  The second patch removes
the other -floop-* flags that were part of the old graphite's middle-end (these
were the first transforms implemented on the polyhedral representation
(matrices, etc.) when we had no ISL scheduler.)  The transition to ISL that
removed GCC's dependence on PPL and Cloog has not removed all graphite's
middle-end for loop transforms.  We now can remove that code as it is replaced
by ISL's scheduler.

The patches pass make check and bootstrap (in progress) with 
-fgraphite-identity.
Ok to commit?


From the graphite side, this is right. One thing I am not sure about if we need 
to
keep these flags as 'do-nothing' flags to meet certain backward compatibility
guarantees in gcc.

Best,
Tobias

Re: [PATCH] Specify the type of scop-region

[Tobias Grosser]

On 08/17/2015 10:30 PM, Aditya Kumar wrote:

From: Aditya Kumar aditya...@samsung.com

Changing the type of scop::region from void* to sese, as this is
the only type assigned to scop::region for now. No functional changes intended.
Passes regtest and bootstrap.



LGTM.

Tobias

Re: [PATCH] [graphite] Constrain only on INTEGER_TYPE

[Tobias Grosser]

On 08/12/2015 10:33 PM, Aditya Kumar wrote:

Passes bootstrap, no regressions.

With this patch gcc bootstraps with graphite.
make BOOT_CFLAGS=-g -O2 -fgraphite-identity -floop-interchange -floop-block


LGTM, but please use a longer sentence to explain what you do.

Tobias

Re: [PATCH] [graphite] dump reasons why graphite failed to detect a scop

[Tobias Grosser]

On 07/25/2015 12:36 AM, Sebastian Pop wrote:

When trying to analyze why Graphite does not handle a loop nest, it is easy to
look in the dumps of -fdump-tree-graphite-all to guess what has to be changed to
catch the loop.  This patch makes the dumps a bit more verbose and useful.
---
  gcc/graphite-scop-detection.c | 72 +++
  1 file changed, 66 insertions(+), 6 deletions(-)


LGTM.

Tobias


diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
index 686f495..fb7247e 100644
--- a/gcc/graphite-scop-detection.c
+++ b/gcc/graphite-scop-detection.c
@@ -51,6 +51,7 @@ along with GCC; see the file COPYING3.  If not see
  #include graphite-poly.h
  #include tree-ssa-propagate.h
  #include graphite-scop-detection.h
+#include gimple-pretty-print.h

  /* Forward declarations.  */
  static void make_close_phi_nodes_unique (basic_block);
@@ -350,13 +351,31 @@ stmt_simple_for_scop_p (basic_block scop_entry, loop_p 
outermost_loop,
|| (gimple_code (stmt) == GIMPLE_CALL
   !(gimple_call_flags (stmt)  (ECF_CONST | ECF_PURE)))
|| (gimple_code (stmt) == GIMPLE_ASM))
-return false;
+{
+  if (dump_file  (dump_flags  TDF_DETAILS))
+   {
+ fprintf (dump_file, [scop-detection-fail] );
+ fprintf (dump_file, Graphite cannot handle this stmt:\n);
+ print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS);
+   }
+
+  return false;
+}

if (is_gimple_debug (stmt))
  return true;

if (!stmt_has_simple_data_refs_p (outermost_loop, stmt))
-return false;
+{
+  if (dump_file  (dump_flags  TDF_DETAILS))
+   {
+ fprintf (dump_file, [scop-detection-fail] );
+ fprintf (dump_file, Graphite cannot handle data-refs in stmt:\n);
+ print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS);
+   }
+
+  return false;
+}

switch (gimple_code (stmt))
  {
@@ -375,7 +394,16 @@ stmt_simple_for_scop_p (basic_block scop_entry, loop_p 
outermost_loop,
  || code == GE_EXPR
  || code == EQ_EXPR
  || code == NE_EXPR))
-  return false;
+  {
+   if (dump_file  (dump_flags  TDF_DETAILS))
+ {
+   fprintf (dump_file, [scop-detection-fail] );
+   fprintf (dump_file, Graphite cannot handle cond stmt:\n);
+   print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS);
+ }
+
+   return false;
+ }

for (unsigned i = 0; i  2; ++i)
  {
@@ -383,7 +411,16 @@ stmt_simple_for_scop_p (basic_block scop_entry, loop_p 
outermost_loop,
if (!graphite_can_represent_expr (scop_entry, loop, op)
/* We can not handle REAL_TYPE. Failed for pr39260.  */
|| TREE_CODE (TREE_TYPE (op)) == REAL_TYPE)
- return false;
+ {
+   if (dump_file  (dump_flags  TDF_DETAILS))
+ {
+   fprintf (dump_file, [scop-detection-fail] );
+   fprintf (dump_file, Graphite cannot represent stmt:\n);
+   print_gimple_stmt (dump_file, stmt, 0, 
TDF_VOPS|TDF_MEMSYMS);
+ }
+
+   return false;
+ }
  }

return true;
@@ -395,6 +432,12 @@ stmt_simple_for_scop_p (basic_block scop_entry, loop_p 
outermost_loop,

  default:
/* These nodes cut a new scope.  */
+  if (dump_file  (dump_flags  TDF_DETAILS))
+   {
+ fprintf (dump_file, [scop-detection-fail] );
+ fprintf (dump_file, Gimple stmt not handled in Graphite:\n);
+ print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS);
+   }
return false;
  }

@@ -488,7 +531,16 @@ scopdet_basic_block_info (basic_block bb, loop_p 
outermost_loop,
 with make_forwarder_block.  */
if (!single_succ_p (bb)
  || bb_has_abnormal_pred (single_succ (bb)))
-   result.difficult = true;
+   {
+ if (dump_file  (dump_flags  TDF_DETAILS))
+   {
+ fprintf (dump_file, [scop-detection-fail] );
+ fprintf (dump_file, BB %d cannot be part of a scop.\n,
+  bb-index);
+   }
+
+ result.difficult = true;
+   }
else
result.exit = single_succ (bb);

@@ -509,7 +561,15 @@ scopdet_basic_block_info (basic_block bb, loop_p 
outermost_loop,
sinfo = build_scops_1 (bb, outermost_loop, regions, loop);

if (!graphite_can_represent_loop (entry_block, loop))
- result.difficult = true;
+ {
+   if (dump_file  (dump_flags  TDF_DETAILS))
+ {
+   fprintf (dump_file, [scop-detection-fail] );
+   fprintf (dump_file, Graphite cannot represent loop %d.\n,
+loop-num);
+ }
+   result.difficult = true;
+ }

result.difficult |= sinfo.difficult;

Re: [PATCH] Refactor graphite-isl-ast-to-gimple.c

[Tobias Grosser]

On 07/20/2015 06:24 PM, Aditya Kumar wrote:

From: Aditya Kumar hiradi...@msn.com

Refactor graphite-isl-ast-to-gimple.c:
Refactor so that each function can access 'region'. This will help
maintain a parameter rename_map within a region. No functional change intended.
This patch will be followed by another set of patches
where translate_isl_ast_to_gimple::region is used to keep parameters which needs


which need


renaming. Since we are planning to remove limit_scops, we now have to maintain a
set of parameters which needs renaming. This refactoring helps avoid passing
`region' to all the functions in this file.

It passes bootstrap and regtest.


LGTM.

Best,
Tobias

Re: [PATCH] gcc/: Fix building with isl-0.15.0; includes

[Tobias Grosser]

On 07/19/2015 11:10 PM, james harvey wrote:

These two patches appear to do the trick.  I'm building with ISL 0.15
just fine now.


Nice.

Tobias

Re: [PATCH] Refactor graphite-isl-ast-to-gimple.c

[Tobias Grosser]

On 07/19/2015 09:46 PM, Aditya Kumar wrote:

Refactor graphite-isl-ast-to-gimple.c:
Refactor so that each function can access 'region'. This will help
maintain a parameter rename_map within a region. No functional change intended.
This patch will be followed by another set of patches
where translate_isl_ast_to_gimple::region is used to keep parameters which needs
renaming. Since we are planning to remove limit_scops, we now have to maintain a
set of parameters which needs renaming. This refactoring helps avoid passing
`region' to many functions.


Ah, OK. Now I get it. Generally this looks fine to me (assuming it 
passes a bootstrap), but I wonder if it would not make more sense to 
move the comments inside the class right over the function declarations.


Best,
Tobias


gcc/ChangeLog:

2015-07-19  Aditya Kumar  hiradi...@msn.com

 * graphite-isl-ast-to-gimple.c:
Refactor so that each function can access 'region'. This will help
maintain a parameter rename_map within a region.
---
  gcc/graphite-isl-ast-to-gimple.c | 153 +++
  1 file changed, 122 insertions(+), 31 deletions(-)

diff --git a/gcc/graphite-isl-ast-to-gimple.c b/gcc/graphite-isl-ast-to-gimple.c
index b32781a..86a921b 100644
--- a/gcc/graphite-isl-ast-to-gimple.c
+++ b/gcc/graphite-isl-ast-to-gimple.c
@@ -124,9 +124,84 @@ void ivs_params_clear (ivs_params ip)
  }
  }

-static tree
-gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *,
-   ivs_params ip);
+class translate_isl_ast_to_gimple
+{
+public:
+  translate_isl_ast_to_gimple (sese r)
+   : region (r)
+  { }
+
+  edge translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
+ edge next_e, ivs_params ip);
+
+  edge translate_isl_ast_node_for (loop_p context_loop,
+  __isl_keep isl_ast_node *node,
+  edge next_e, ivs_params ip);
+
+  edge translate_isl_ast_for_loop (loop_p context_loop,
+  __isl_keep isl_ast_node *node_for,
+  edge next_e,
+  tree type, tree lb, tree ub,
+  ivs_params ip);
+
+  edge translate_isl_ast_node_if (loop_p context_loop,
+ __isl_keep isl_ast_node *node,
+ edge next_e, ivs_params ip);
+
+  edge translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
+   edge next_e, ivs_params ip);
+
+  edge translate_isl_ast_node_block (loop_p context_loop,
+__isl_keep isl_ast_node *node,
+edge next_e, ivs_params ip);
+
+  tree unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
+ivs_params ip);
+
+  tree binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
+ ivs_params ip);
+
+  tree ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
+  ivs_params ip);
+
+  tree nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
+   ivs_params ip);
+
+  tree gcc_expression_from_isl_expression (tree type,
+  __isl_take isl_ast_expr *,
+  ivs_params ip);
+
+  tree gcc_expression_from_isl_ast_expr_id (tree type,
+   __isl_keep isl_ast_expr *expr_id,
+   ivs_params ip);
+
+  tree gcc_expression_from_isl_expr_int (tree type,
+__isl_take isl_ast_expr *expr);
+
+  tree gcc_expression_from_isl_expr_op (tree type,
+   __isl_take isl_ast_expr *expr,
+   ivs_params ip);
+
+  struct loop *graphite_create_new_loop (edge entry_edge,
+__isl_keep isl_ast_node *node_for,
+loop_p outer, tree type,
+tree lb, tree ub, ivs_params ip);
+
+  edge graphite_create_new_guard (edge entry_edge,
+ __isl_take isl_ast_expr *if_cond,
+ ivs_params ip);
+
+  edge graphite_create_new_loop_guard (edge entry_edge,
+  __isl_keep isl_ast_node *node_for,
+  tree *type,
+  tree *lb, tree *ub, ivs_params ip);
+
+  void build_iv_mapping (vectree iv_map, gimple_bb_p gbb,
+__isl_keep isl_ast_expr *user_expr, ivs_params ip,
+sese region);
+private:
+  sese region;
+};

  /* Return the tree variable that corresponds to the given isl ast identifier
 expression (an isl_ast_expr of type isl_ast_expr_id).
@@ 

Re: [PATCH] [graphite] fix pr61929

[Tobias Grosser]

)
   isl_set_dim (valid, isl_dim_set));
  scop-context = isl_set_intersect (scop-context, valid);

- space = isl_set_get_space (extent);
  aff = isl_aff_zero_on_domain (isl_local_space_from_space (space));
  aff = isl_aff_add_coefficient_si (aff, isl_dim_in, i + 1, 1);
  univ = isl_set_universe (isl_space_domain (isl_aff_get_space
(aff)));
  index = isl_pw_aff_alloc (univ, aff);

- id = isl_set_get_tuple_id (extent);
+ id = isl_set_get_tuple_id (subscript_sizes);
  lb = isl_pw_aff_set_tuple_id (lb, isl_dim_in, isl_id_copy (id));
  ub = isl_pw_aff_set_tuple_id (ub, isl_dim_in, id);

  /* low = sub_i = high */
  lbs = isl_pw_aff_ge_set (isl_pw_aff_copy (index), lb);
  ubs = isl_pw_aff_le_set (index, ub);
- extent = isl_set_intersect (extent, lbs);
- extent = isl_set_intersect (extent, ubs);
+ subscript_sizes = isl_set_intersect (subscript_sizes, lbs);
+ subscript_sizes = isl_set_intersect (subscript_sizes, ubs);
}
  }

-  return extent;
+  return subscript_sizes;
  }

  /* Build data accesses for DR in PBB.  */ @@ -1550,7 +1547,7 @@
build_poly_dr (data_reference_p dr, poly_bb_p pbb)  {
int dr_base_object_set;
isl_map *acc;
-  isl_set *extent;
+  isl_set *subscript_sizes;
scop_p scop = PBB_SCOP (pbb);

{
@@ -1577,9 +1574,10 @@ build_poly_dr (data_reference_p dr, poly_bb_p pbb)
alias_set_num = *(bap-alias_set);

  space = isl_space_set_tuple_id (space, isl_dim_set, id);
-extent = isl_set_nat_universe (space);
-extent = isl_set_fix_si (extent, isl_dim_set, 0, alias_set_num);
-extent = pdr_add_data_dimensions (extent, scop, dr);
+subscript_sizes = isl_set_nat_universe (space);
+subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0,
+ alias_set_num);
+subscript_sizes = pdr_add_data_dimensions (subscript_sizes, scop,
+dr);
}

gcc_assert (dr-aux);
@@ -1587,7 +1585,7 @@ build_poly_dr (data_reference_p dr, poly_bb_p pbb)

new_poly_dr (pbb, dr_base_object_set,
   DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
-  dr, DR_NUM_DIMENSIONS (dr), acc, extent);
+  dr, DR_NUM_DIMENSIONS (dr), acc, subscript_sizes);
  }

  /* Write to FILE the alias graph of data references in DIMACS format.  */
diff --git a/gcc/testsuite/gcc.dg/graphite/pr61929.c
b/gcc/testsuite/gcc.dg/graphite/pr61929.c
new file mode 100644
index 000..ebf
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/pr61929.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options -O2 -ftree-loop-linear -floop-strip-mine } */
+
+typedef struct m {
+  char *A;
+  char *B;
+} mystruct;
+mystruct arr[52];
+
+void main () {}
+void generateICE (void)
+{
+  int i;
+  for (i=0; i52; i++)
+{
+  arr[i].A = ;
+  arr[i].B = 0;
+}
+}
--
2.1.0.243.g30d45f7

-Original Message-
From: Tobias Grosser [mailto:tob...@grosser.es]
Sent: Thursday, July 16, 2015 11:31 PM
To: Sebastian Pop; gcc-patches@gcc.gnu.org
Cc: seb...@gmail.com; aditya...@samsung.com; richard.guent...@gmail.com
Subject: Re: [PATCH] [graphite] fix pr61929

On 07/17/2015 12:23 AM, Sebastian Pop wrote:

This fixes bootstrap of GCC with BOOT_CFLAGS=-g -O2
-fgraphite-identity -floop-nest-optimize -floop-block -floop-interchange

-floop-strip-mine.

It passes regstrap on amd64-linux.

Ok to commit to trunk?


Very nice.

this but  seems to include multiple fixes and refactorings at the same time.
I personally would prefer to at least separate the functional and
non-functional changes, such that the actual bug fixed becomes clear.
If splitting the patch is difficult, can you at least point out in the
commit message, which of your changes now actually fixed the bootstrap?

Otherwise, LGTM.

Best,
Tobias


Thanks.

2015-07-15  Aditya Kumar  aditya...@samsung.com
Sebastian Pop  s@samsung.com

PR middle-end/61929
* graphite-dependences.c (add_pdr_constraints): Renamed
pdr-extent to pdr-subscript_sizes.
* graphite-interchange.c (build_linearized_memory_access): Add
back all gcc_assert's that the isl_int to isl_val conversion
patch has removed.  Refactored.
(pdr_stride_in_loop): Renamed pdr-extent to pdr-subscript_sizes.
* graphite-poly.c (new_poly_dr): Same.
(free_poly_dr): Same.
* graphite-poly.h (struct poly_dr): Same.
* graphite-scop-detection.c (stmt_has_simple_data_refs_p): Ignore
all data references other than ARRAY_REF and MEM_REF.
* graphite-scop-detection.h: Fix space.
* graphite-sese-to-poly.c (build_pbb_scattering_polyhedrons): Add
back all gcc_assert's removed by a previous patch.
(wrap): Remove the_isl_ctx global variable that the same patch has
added.
(build_loop_iteration_domains): Same.
(add_param_constraints): Same

Re: [PATCH] Rename parameters which are within scop

[Tobias Grosser]

Hi Aditya,

could you possible expand the commit message a little bit to explain 
what you are doing?


Tobias


On 07/18/2015 01:00 AM, Aditya Kumar wrote: ---

  gcc/graphite-isl-ast-to-gimple.c | 153 +++
  1 file changed, 122 insertions(+), 31 deletions(-)

diff --git a/gcc/graphite-isl-ast-to-gimple.c b/gcc/graphite-isl-ast-to-gimple.c
index b32781a..3e2c1fa 100644
--- a/gcc/graphite-isl-ast-to-gimple.c
+++ b/gcc/graphite-isl-ast-to-gimple.c
@@ -124,9 +124,84 @@ void ivs_params_clear (ivs_params ip)
  }
  }

-static tree
-gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *,
-   ivs_params ip);
+class translate_isl_ast_to_gimple
+{
+public:
+  translate_isl_ast_to_gimple (sese r)
+   : region (r)
+  { }
+
+  edge translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
+ edge next_e, ivs_params ip);
+
+  edge translate_isl_ast_node_for (loop_p context_loop,
+  __isl_keep isl_ast_node *node,
+  edge next_e, ivs_params ip);
+
+  edge translate_isl_ast_for_loop (loop_p context_loop,
+  __isl_keep isl_ast_node *node_for,
+  edge next_e,
+  tree type, tree lb, tree ub,
+  ivs_params ip);
+
+  edge translate_isl_ast_node_if (loop_p context_loop,
+ __isl_keep isl_ast_node *node,
+ edge next_e, ivs_params ip);
+
+  edge translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
+   edge next_e, ivs_params ip);
+
+  edge translate_isl_ast_node_block (loop_p context_loop,
+__isl_keep isl_ast_node *node,
+edge next_e, ivs_params ip);
+
+  tree unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
+ivs_params ip);
+
+  tree binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
+ ivs_params ip);
+
+  tree ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
+  ivs_params ip);
+
+  tree nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
+   ivs_params ip);
+
+  tree gcc_expression_from_isl_expression (tree type,
+  __isl_take isl_ast_expr *,
+  ivs_params ip);
+
+  tree gcc_expression_from_isl_ast_expr_id (tree type,
+   __isl_keep isl_ast_expr *expr_id,
+   ivs_params ip);
+
+  tree gcc_expression_from_isl_expr_int (tree type,
+__isl_take isl_ast_expr *expr);
+
+  tree gcc_expression_from_isl_expr_op (tree type,
+   __isl_take isl_ast_expr *expr,
+   ivs_params ip);
+
+  struct loop *graphite_create_new_loop (edge entry_edge,
+__isl_keep isl_ast_node *node_for,
+loop_p outer, tree type,
+tree lb, tree ub, ivs_params ip);
+
+  edge graphite_create_new_guard (edge entry_edge,
+ __isl_take isl_ast_expr *if_cond,
+ ivs_params ip);
+
+  edge graphite_create_new_loop_guard (edge entry_edge,
+  __isl_keep isl_ast_node *node_for,
+  tree *type,
+  tree *lb, tree *ub, ivs_params ip);
+
+  void build_iv_mapping (vectree iv_map, gimple_bb_p gbb,
+__isl_keep isl_ast_expr *user_expr, ivs_params ip,
+sese region);
+private:
+  sese region;
+};

  /* Return the tree variable that corresponds to the given isl ast identifier
 expression (an isl_ast_expr of type isl_ast_expr_id).
@@ -136,7 +211,8 @@ gcc_expression_from_isl_expression (tree type, __isl_take 
isl_ast_expr *,
 converting type sizes may be problematic when we switch to smaller
 types.  */

-static tree
+tree
+translate_isl_ast_to_gimple::
  gcc_expression_from_isl_ast_expr_id (tree type,
 __isl_keep isl_ast_expr *expr_id,
 ivs_params ip)
@@ -147,7 +223,7 @@ gcc_expression_from_isl_ast_expr_id (tree type,
res = ip.find (tmp_isl_id);
isl_id_free (tmp_isl_id);
gcc_assert (res != ip.end () 
-  Could not map isl_id to tree expression);
+ Could not map isl_id to tree expression);
isl_ast_expr_free (expr_id);
return fold_convert (type, res-second);
  }
@@ -155,7 +231,8 @@ gcc_expression_from_isl_ast_expr_id (tree type,
  /* Converts an 

Re: [PATCH] enable loop fusion with ISL scheduler

[Tobias Grosser]

On 07/17/2015 12:35 AM, Sebastian Pop wrote:

gcc/ChangeLog:

2015-07-16  Aditya Kumar  aditya...@samsung.com
 Sebastian Pop  s@samsung.com

 * common.opt (floop-fuse): New.
 * doc/invoke.texi (floop-fuse): Documented.
 * graphite-optimize-isl.c (optimize_isl): Use
 ISL_SCHEDULE_FUSE_MAX when using flag_loop_fuse.
 * graphite-poly.c (apply_poly_transforms): Call optimize_isl when
 using flag_loop_fuse.
 * graphite.c (gate_graphite_transforms): Enable graphite with
 flag_loop_fuse.


LGTM.

Tobias


gcc/testsuite/ChangeLog:

2015-07-16  Aditya Kumar  aditya...@samsung.com
 Sebastian Pop  s@samsung.com

 * gcc.dg/graphite/fuse-1.c: New test.
 * gcc.dg/graphite/fuse-2.c: New test.
---
  gcc/common.opt |  4 
  gcc/doc/invoke.texi| 23 +++-
  gcc/graphite-optimize-isl.c|  5 -
  gcc/graphite-poly.c|  2 +-
  gcc/graphite.c |  3 ++-
  gcc/testsuite/gcc.dg/graphite/fuse-1.c | 32 
  gcc/testsuite/gcc.dg/graphite/fuse-2.c | 38 ++
  7 files changed, 103 insertions(+), 4 deletions(-)
  create mode 100644 gcc/testsuite/gcc.dg/graphite/fuse-1.c
  create mode 100644 gcc/testsuite/gcc.dg/graphite/fuse-2.c

diff --git a/gcc/common.opt b/gcc/common.opt
index dd49ae3..200ecc1 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -1365,6 +1365,10 @@ floop-nest-optimize
  Common Report Var(flag_loop_optimize_isl) Optimization
  Enable the ISL based loop nest optimizer

+floop-fuse
+Common Report Var(flag_loop_fuse) Optimization
+Enable loop fusion
+
  fstrict-volatile-bitfields
  Common Report Var(flag_strict_volatile_bitfields) Init(-1) Optimization
  Force bitfield accesses to match their type width
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index b99ab1c..7cc8bb9 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -409,7 +409,7 @@ Objective-C and Objective-C++ Dialects}.
  -fivopts -fkeep-inline-functions -fkeep-static-consts @gol
  -flive-range-shrinkage @gol
  -floop-block -floop-interchange -floop-strip-mine @gol
--floop-unroll-and-jam -floop-nest-optimize @gol
+-floop-unroll-and-jam -floop-nest-optimize -floop-fuse @gol
  -floop-parallelize-all -flra-remat -flto -flto-compression-level @gol
  -flto-partition=@var{alg} -flto-report -flto-report-wpa -fmerge-all-constants 
@gol
  -fmerge-constants -fmodulo-sched -fmodulo-sched-allow-regmoves @gol
@@ -8796,6 +8796,27 @@ optimizer based on the Pluto optimization algorithms.  
It calculates a loop
  structure optimized for data-locality and parallelism.  This option
  is experimental.

+@item -floop-fuse
+@opindex floop-fuse
+Enable loop fusion.  This option is experimental.
+
+For example, given a loop like:
+@smallexample
+DO I = 1, N
+  A(I) = A(I) + B(I)
+ENDDO
+DO I = 1, N
+  A(I) = A(I) + C(I)
+ENDDO
+@end smallexample
+@noindent
+loop fusion transforms the loop as if it were written:
+@smallexample
+DO I = 1, N
+  A(I) = A(I) + B(I) + C(I)
+ENDDO
+@end smallexample
+
  @item -floop-unroll-and-jam
  @opindex floop-unroll-and-jam
  Enable unroll and jam for the ISL based loop nest optimizer.  The unroll
diff --git a/gcc/graphite-optimize-isl.c b/gcc/graphite-optimize-isl.c
index 624cc87..c016461 100644
--- a/gcc/graphite-optimize-isl.c
+++ b/gcc/graphite-optimize-isl.c
@@ -599,7 +599,10 @@ optimize_isl (scop_p scop)

isl_options_set_schedule_max_constant_term (scop-ctx, CONSTANT_BOUND);
isl_options_set_schedule_maximize_band_depth (scop-ctx, 1);
-  isl_options_set_schedule_fuse (scop-ctx, ISL_SCHEDULE_FUSE_MIN);
+  if (flag_loop_fuse)
+isl_options_set_schedule_fuse (scop-ctx, ISL_SCHEDULE_FUSE_MAX);
+  else
+isl_options_set_schedule_fuse (scop-ctx, ISL_SCHEDULE_FUSE_MIN);
isl_options_set_on_error (scop-ctx, ISL_ON_ERROR_CONTINUE);

  #ifdef HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE
diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c
index 4407dc5..4808fbe 100644
--- a/gcc/graphite-poly.c
+++ b/gcc/graphite-poly.c
@@ -272,7 +272,7 @@ apply_poly_transforms (scop_p scop)

/* This pass needs to be run at the final stage, as it does not
   update the lst.  */
-  if (flag_loop_optimize_isl || flag_loop_unroll_jam)
+  if (flag_loop_optimize_isl || flag_loop_unroll_jam || flag_loop_fuse)
  transform_done |= optimize_isl (scop);

return transform_done;
diff --git a/gcc/graphite.c b/gcc/graphite.c
index ba8029a..51af1a2a 100644
--- a/gcc/graphite.c
+++ b/gcc/graphite.c
@@ -342,7 +342,8 @@ gate_graphite_transforms (void)
|| flag_graphite_identity
|| flag_loop_parallelize_all
|| flag_loop_optimize_isl
-  || flag_loop_unroll_jam)
+  || flag_loop_unroll_jam
+  || flag_loop_fuse)
  flag_graphite = 1;

return flag_graphite != 0;
diff --git a/gcc/testsuite/gcc.dg/graphite/fuse-1.c 

Re: [PATCH] [graphite] fix pr61929

[Tobias Grosser]

On 07/17/2015 12:23 AM, Sebastian Pop wrote:

This fixes bootstrap of GCC with BOOT_CFLAGS=-g -O2 -fgraphite-identity
-floop-nest-optimize -floop-block -floop-interchange -floop-strip-mine.
It passes regstrap on amd64-linux.

Ok to commit to trunk?


Very nice.

this but  seems to include multiple fixes and refactorings at the same 
time. I personally would prefer to at least separate the functional and 
non-functional changes, such that the actual bug fixed becomes clear.
If splitting the patch is difficult, can you at least point out in the 
commit message, which of your changes now actually fixed the bootstrap?


Otherwise, LGTM.

Best,
Tobias


Thanks.

2015-07-15  Aditya Kumar  aditya...@samsung.com
Sebastian Pop  s@samsung.com

PR middle-end/61929
* graphite-dependences.c (add_pdr_constraints): Renamed
pdr-extent to pdr-subscript_sizes.
* graphite-interchange.c (build_linearized_memory_access): Add
back all gcc_assert's that the isl_int to isl_val conversion
patch has removed.  Refactored.
(pdr_stride_in_loop): Renamed pdr-extent to pdr-subscript_sizes.
* graphite-poly.c (new_poly_dr): Same.
(free_poly_dr): Same.
* graphite-poly.h (struct poly_dr): Same.
* graphite-scop-detection.c (stmt_has_simple_data_refs_p): Ignore
all data references other than ARRAY_REF and MEM_REF.
* graphite-scop-detection.h: Fix space.
* graphite-sese-to-poly.c (build_pbb_scattering_polyhedrons): Add
back all gcc_assert's removed by a previous patch.
(wrap): Remove the_isl_ctx global variable that the same patch has
added.
(build_loop_iteration_domains): Same.
(add_param_constraints): Same.
(pdr_add_data_dimensions): Same.  Refactored.
(build_poly_dr): Renamed extent to subscript_sizes.

testsuite/
PR middle-end/61929
* gcc.dg/graphite/pr61929.c: New.
---
  gcc/graphite-dependences.c  |  4 +--
  gcc/graphite-interchange.c  | 55 +
  gcc/graphite-poly.c |  6 ++--
  gcc/graphite-poly.h |  2 +-
  gcc/graphite-scop-detection.c   | 22 +
  gcc/graphite-scop-detection.h   |  2 +-
  gcc/graphite-sese-to-poly.c | 54 
  gcc/testsuite/gcc.dg/graphite/pr61929.c | 19 
  8 files changed, 97 insertions(+), 67 deletions(-)
  create mode 100644 gcc/testsuite/gcc.dg/graphite/pr61929.c

diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
index 50fe73e..af18ecb 100644
--- a/gcc/graphite-dependences.c
+++ b/gcc/graphite-dependences.c
@@ -88,13 +88,13 @@ constrain_domain (isl_map *map, isl_set *s)
return isl_map_intersect_domain (map, s);
  }

-/* Constrain pdr-accesses with pdr-extent and pbb-domain.  */
+/* Constrain pdr-accesses with pdr-subscript_sizes and pbb-domain.  */

  static isl_map *
  add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
  {
isl_map *x = isl_map_intersect_range (isl_map_copy (pdr-accesses),
-   isl_set_copy (pdr-extent));
+   isl_set_copy (pdr-subscript_sizes));
x = constrain_domain (x, isl_set_copy (pbb-domain));
return x;
  }
diff --git a/gcc/graphite-interchange.c b/gcc/graphite-interchange.c
index aee51a8..03c2c63 100644
--- a/gcc/graphite-interchange.c
+++ b/gcc/graphite-interchange.c
@@ -79,37 +79,40 @@ extern C {
  static isl_constraint *
  build_linearized_memory_access (isl_map *map, poly_dr_p pdr)
  {
-  isl_constraint *res;
isl_local_space *ls = isl_local_space_from_space (isl_map_get_space (map));
-  unsigned offset, nsubs;
-  int i;
-  isl_ctx *ctx;
+  isl_constraint *res = isl_equality_alloc (ls);
+  isl_val *size = isl_val_int_from_ui (isl_map_get_ctx (map), 1);

-  isl_val *size, *subsize, *size1;
-
-  res = isl_equality_alloc (ls);
-  ctx = isl_local_space_get_ctx (ls);
-  size = isl_val_int_from_ui (ctx, 1);
-
-  nsubs = isl_set_dim (pdr-extent, isl_dim_set);
+  unsigned nsubs = isl_set_dim (pdr-subscript_sizes, isl_dim_set);
/* -1 for the already included L dimension.  */
-  offset = isl_map_dim (map, isl_dim_out) - 1 - nsubs;
+  unsigned offset = isl_map_dim (map, isl_dim_out) - 1 - nsubs;
res = isl_constraint_set_coefficient_si (res, isl_dim_out, offset + nsubs, 
-1);
-  /* Go through all subscripts from last to first.  First dimension
+  /* Go through all subscripts from last to first.  The dimension i=0
   is the alias set, ignore it.  */
-  for (i = nsubs - 1; i = 1; i--)
+  for (int i = nsubs - 1; i = 1; i--)
  {
-  isl_space *dc;
-  isl_aff *aff;
-
-  size1 = isl_val_copy (size);
-  res = isl_constraint_set_coefficient_val (res, isl_dim_out, offset + i, 
size);
-  dc = isl_set_get_space (pdr-extent);
-  aff = isl_aff_zero_on_domain (isl_local_space_from_space (dc));
-  

Re: [PATCH] Discard Scops for which entry==exit

[Tobias Grosser]

On 06/30/2015 05:47 PM, Aditya K wrote:

Hi Tobias,
A test case (gcc/testsuite/gcc.dg/graphite/pr18792.c) came up when we removed 
`graphite-scop-detection.c:limit_scops'.
The test case is a scop where entry==exit,

BB5 (*#) - BB6 (#);
BB6 - BB5;

In this case BB2 is out of the scop. This is basically an empty (infinite) loop 
with no entr


OK, maybe mention this in the commit message.


Best,
Tobias

Re: [PATCH] Graphite cannot handle return stmt

[Tobias Grosser]

On 06/30/2015 10:50 PM, Aditya Kumar wrote:

No regressions.

2015-06-29  Aditya Kumar  aditya...@samsung.com
 Sebastian Pop s@samsung.com

 * graphite-scop-detection.c (stmt_simple_for_scop_p): Bail out in case 
of a return statement.


LGTM.

Tobias

Re: [PATCH] Discard Scops for which entry==exit

[Tobias Grosser]

On 07/02/2015 05:37 PM, Aditya K wrote:

A test case (gcc/testsuite/gcc.dg/graphite/pr18792.c) came up when we removed 
`graphite-scop-detection.c:limit_scops'.
The test case is a scop where entry==exit,

BB5 (*#) - BB6 (#);
BB6 - BB5;

In this case BB2 is out of the scop. This is basically an empty (infinite) loop.


LGTM.

Tobias

Re: [PATCH] Restore previous change for gimple_phi_iterator

[Tobias Grosser]

On 07/02/2015 06:52 PM, Aditya Kumar wrote:

gcc/ChangeLog:

2015-07-02  Aditya Kumar  aditya...@samsung.com
Sebastian Pop  s@samsung.com

 * graphite-sese-to-poly.c (rewrite_cross_bb_scalar_deps):
Point iterator to use_stmt.



Hi Aditya,

this patch does not explain what was wrong and why this change is 
correct. Could you possibly add such an explanation.


Best,
Tobias



Bug introduced by patch:
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@217787
---
  gcc/graphite-sese-to-poly.c | 7 +++
  1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 271c499..78f10e4 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -2458,11 +2458,10 @@ rewrite_cross_bb_scalar_deps (scop_p scop, 
gimple_stmt_iterator *gsi)
handle_scalar_deps_crossing_scop_limits (scop, def, stmt);

FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
-if (gimple_code (use_stmt) == GIMPLE_PHI
-(res = true))
+if (gphi *phi = dyn_cast gphi * (use_stmt))
{
-   gphi_iterator psi = gsi_start_phis (gimple_bb (use_stmt));
-
+   res = true;
+   gphi_iterator psi = gsi_for_phi (phi);
if (scalar_close_phi_node_p (gsi_stmt (psi)))
  rewrite_close_phi_out_of_ssa (scop, psi);
else

Re: [PATCH] Restore previous change for gimple_phi_iterator

[Tobias Grosser]

On 07/02/2015 08:34 PM, Sebastian Pop wrote:

On Thu, Jul 2, 2015 at 1:17 PM, Tobias Grosser tob...@grosser.es wrote:

On 07/02/2015 06:52 PM, Aditya Kumar wrote:


gcc/ChangeLog:

2015-07-02  Aditya Kumar  aditya...@samsung.com
 Sebastian Pop  s@samsung.com

  * graphite-sese-to-poly.c (rewrite_cross_bb_scalar_deps):
 Point iterator to use_stmt.



Hi Aditya,

this patch does not explain what was wrong and why this change is correct.
Could you possibly add such an explanation.


One of the code refactorings introducing phi node iterators modified
the semantics of this code as described below ...



Best,
Tobias




Bug introduced by patch:
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@217787


... here.
If you git log grep for this commit, you would see that this patch
reverts this typo introduced in a very large patch.


Sure. The corresponding change was:

-   gimple_stmt_iterator psi = gsi_for_stmt (use_stmt);
+   gphi_iterator psi = gsi_start_phis (gimple_bb (use_stmt));

Now this commit is not a pure revert. Instead of falling back to 
gsi_for_stmt, we now use gsi_for_phi(phi) and also somehow modify the 
condition above. I assume this is still correct, but as I am a little 
out of graphite, it would really help to explain (in two sentences in 
the commit message) why the previous change was wrong and how the 
behavior is now different. Something like:


After this patch we start to iterate at the very first phi node,
whereas before this applied we skipped the PHI nodes and started 
iterating at the first actual instruciton.


Thanks,
Tobias

Re: [PATCH] Restore previous change for gimple_phi_iterator

[Tobias Grosser]

On 07/02/2015 09:03 PM, Sebastian Pop wrote:

On Thu, Jul 2, 2015 at 1:44 PM, Tobias Grosser tob...@grosser.es wrote:

If you git log grep for this commit, you would see that this patch
reverts this typo introduced in a very large patch.



Sure. The corresponding change was:

-   gimple_stmt_iterator psi = gsi_for_stmt (use_stmt);
+   gphi_iterator psi = gsi_start_phis (gimple_bb (use_stmt));

Now this commit is not a pure revert. Instead of falling back to


IMO the patch restores the semantics, so it is a revert to some syntax changes:
in the past we had this:


-   gimple_stmt_iterator psi = gsi_for_stmt (use_stmt);


that is get me an iterator pointing on the use_stmt.
After our patch we get the same semantics back (modulo some change in
function names, c++-ification, etc.)

gphi *phi = dyn_cast gphi * (use_stmt)
gphi_iterator psi = gsi_for_phi (phi);

that is again an iterator pointing on the use_stmt.

The patch at r217787 was incorrectly initializing the iterator
to point at the beginning of the phi nodes in the BB of the use_stmt:


+   gphi_iterator psi = gsi_start_phis (gimple_bb (use_stmt));


This makes no sense, as then we would start processing a random phi node
and would fail to insert an array for a virtual phi node.


Thanks. I am a little slow today. The patch looks indeed correct. Maybe 
you could add this explanation to the commit message and also add a test 
case as Ramana suggested.


Tobias

Re: [PATCH] Restore previous change for gimple_phi_iterator

[Tobias Grosser]

On 07/02/2015 09:09 PM, Sebastian Pop wrote:

On Thu, Jul 2, 2015 at 2:03 PM, Ramana Radhakrishnan
ramana@googlemail.com wrote:

How about a testcase or 2 or mentioning if it is covered by existing
testcases ?


The patch fixes a test in testsuite/gcc.dg/graphite/ when removing the
use of limit_scops().
Maybe the commit message could contain the name of the test that it fixed.


Right. I think just adding the missing information to the commit message 
will be enough.



The patch that removes limit_scops() is in my opinion trivial, and
will be submitted for review once we fixed all the errors it can cause
(code gen, scop translation to polyhedral, etc.)
We will also fix bootstrap with graphite enabled, and then we will fix
all problems in bootstrap with limit_scops() removed.
I will also add a buildbot tracking nightly bootstraps with -floop-*
and -fgraphite-identity.


Sounds great. Nice to see more graphite activity again.

Best,
Tobias

Re: [PATCH] Discard Scops for which entry==exit

[Tobias Grosser]

On 06/30/2015 02:09 AM, Sebastian Pop wrote:

On Mon, Jun 29, 2015 at 3:04 PM, Aditya Kumar hiradi...@msn.com wrote:

In this patch we discard the scops where entry and exit are the same BB.
This is an effort to remove graphite-scop-detection.c:limit_scops.
Removing the limit_scops function introduces correctness regressions.
We are making relevant changes in incremental steps to fix those bugs,
and finally we intend to remove limit_scops.

2015-06-29  Aditya Kumar  aditya...@samsung.com
 Sebastian Pop s@samsung.com

 * graphite-scop-detection.c (build_scops_1): Discard scops for which 
entry==exit


Looks good to me.
Let's wait on comments from Tobi before pushing this patch.


Hi Sebastian,

the commit message should probably give a short reasoning why scops with 
entry == exit need to be discarded. I currently don't see why they would 
be incorrect/problematic (despite being possibly very small/empty).


Tobias

Re: [PATCH] Graphite cannot handle return stmt

[Tobias Grosser]

On 06/30/2015 02:12 AM, Sebastian Pop wrote:

On Mon, Jun 29, 2015 at 3:58 PM, Aditya Kumar hiradi...@msn.com wrote:

No regressions.

2015-06-29  Aditya Kumar  aditya...@samsung.com
 Sebastian Pop s@samsung.com

 * graphite-scop-detection.c (stmt_simple_for_scop_p): Bail out in case 
of a return statement.


Looks good to me.
Tobi, do you see a good reason not to cut scops at return stmts?


Return stmts in a SCoP are definitely invalid. Now, as in my last email, 
I wonder why this is not a positive list. There are probably a lot of 
gimple codes that are invalid inside scops. By default we should refuse 
everything we do _not_ know.


Best,
Tobias

Re: [PATCH] Do not constrain on REAL_TYPE

[Tobias Grosser]

On 06/25/2015 04:27 PM, Sebastian Pop wrote:

On Thu, Jun 25, 2015 at 5:00 AM, Richard Biener
richard.guent...@gmail.com wrote:

Yes, it looks good.  What about COMPLEX_CST and VECTOR_CST and
their types?


The question came around also when we were looking at these problems:
we really only care for integer_cst constants (I in ISL stands for integer ;-)
I think we can also discard those, though we do not have a test-case yet.
Probably we can write one from the real_cst test and add it with the patch.


Would it not make sense to use a positive list here, instead of trying 
to find all types where this does _not_ work?


Tobias

Re: [PATCH, v2] Fix bootstrap with in-tree ISL

[Tobias Grosser]

On 05/29/2015 06:54 PM, Bernhard Reutner-Fischer wrote:

Hi,

config/ChangeLog:

2015-05-29  Bernhard Reutner-Fischer  al...@gcc.gnu.org

 * isl.m4 (ISL_CHECK_VERSION): AC_SUBST ENABLE_ISL_CHECK and set
gcc_cv_isl. Tidy whitespace. Lowercase first line of help-text
like for all the other help texts.

ChangeLog:

2015-05-29  Bernhard Reutner-Fischer  al...@gcc.gnu.org

* configure.ac (build_configdirs, configdirs, target_configdirs):
Accept autogen.sh along configure. Tidy whitespace around ISL.
 * Makefile.tpl: Set HOST_ISL_CHECK from substituted
 ENABLE_ISL_CHECK.
 (HOST_EXPORTS): Add ENABLE_ISL_CHECK.
 * Makefile.in: Regenerate.
* configure: Regenerate.

gcc/ChangeLog:

2015-05-29  Bernhard Reutner-Fischer  al...@gcc.gnu.org

 * configure.ac: Assume a current ISL when using in-tree ISL.
 * configure: Regenerate.

---
This allows for configuring a pristine isl checkout in a combined tree
and fixes the version-checks of isl for in-tree builds.

Bootstrapped on x86_64-unknown-linux-gnu, ok for trunk?


From the graphite site this is fine from me, but this needs a autoconf 
maintainer approval.


Tobias

Re: [PATCH, CFT] Fix bootstrap with in-tree ISL

[Tobias Grosser]

On 04/01/2015 05:09 PM, Bernhard Reutner-Fischer wrote:

Hi,

Trying to build config-list.mk for current trunk.
The box is a stable debian (7.8 it seems) so the OS' ISL is too old
thus i was attempting to use in-tree ISL.

When using an in-tree ISL gcc attempts to determine if it is recent
enough and AFAIU fails to do so since the system's ISL (which we will not use)
might be too old and the in-tree ISL is not yet built.

This results in HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE being not
set and thus compilation of graphite-isl-ast-to-gimple.c fails with
template with C linkage.

The attached seems to get me past compilation of
graphite-isl-ast-to-gimple.c with config-list.mk for e.g.
alpha-linux-gnu

I'm scheduling a proper regstrap on x86_64-linux-gnu for a native
compiler but this will take days to start i fear.
So.. if somebody has spare cycles.. :)


Hi Bernhard,

I can not give an OK for the makefile/configure changes, but in general 
this seems to be the right direction.


Thanks,
Tobias

Re: [Build, Graphite] PR64017 - support ISL-0.14 (gcc/configure.ac and gcc/graphite*.c)

[Tobias Grosser]

On 26.11.2014 16:55, Tobias Burnus wrote:

This patch adds a configure check for isl_schedule_constraints_compute_schedule,
which is new in ISL 0.13 - and uses it for conditional compilation.

The graphite*c patch is based on the one of Jack Howarth,
https://gcc.gnu.org/ml/gcc-patches/2014-11/msg00906.html - without checking
whether the ISL replacements make sense.

With the patch, I have successfully bootstrapped GCC with ISL 0.12.2 and
ISL 0.14 (both using an in-tree build).  [I still have to regtest the two
variants and I also want to do a system-ISL built with ISL 0.12.2]

Is the patch OK for the trunk?

Tobias

PS: I'd be happy if some others could run additional tests.

PPS: If the patch is in, can someone put ISL 0.14 to infrastructure? Then
one can update contrib/download_prerequisites - such that the graphite
failure is at least fixed for in-tree builds (cf. PR64017, PR62289).


That looks good from the graphite site.

Cheers,
Tobias

Re: [Build, Graphite] PR64017 - support ISL-0.14 (gcc/configure.ac and gcc/graphite*.c)

[Tobias Grosser]

On 26.11.2014 17:27, Tobias Burnus wrote:

On Wed, Nov 26, 2014 at 04:55:40PM +0100, Tobias Burnus wrote:

This patch adds a configure check for isl_schedule_constraints_compute_schedule,
which is new in ISL 0.13 - and uses it for conditional compilation.


Repeating the test on a massively multicore system, it fails at stage2 with an
in-tree 0.14 because -lisl cannot be found at gcc/configure time. Hence,
HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE is false and one gets later an
error because a 0.12.2 function is not available with ISL 0.14.

However, running the configure test case manually - or building with fewer
cores - works. As does removing gcc after the failure such that isl/ is
available.  Thus, it looks like a dependency problem.

It seems to be fixed by the attached patch.
OK for the trunk?


OK from the graphite site. This needs a buildsystem OK though.

Tobias

Re: [Build, patch] Remove CLooG from the main configure.ac

[Tobias Grosser]

On 11.11.2014 14:01, Tobias Burnus wrote:

Now that CLooG is no longer used by GCC, it makes sense to also remove it from
the main configure file. Especially as the in-tree build currently only works
if also CLooG is available.

Build on x86-64-gnu-linux - and tested that Graphite still works.*
OK for the trunk?


[* I did see a failure for gcc.dg/graphite/vect-pr43423.c, but that seems to be
independent as I see it also with the yesterday's GCC; for Sparc/arm/aarch64,
it's PR62630.]


Conceptually that is the right way to go. This requires however the OK 
from a autoconf maintainer.


Tobias

Re: RFC: Update ISL under gcc/infrastructure/ ? // Remove CLooG?

[Tobias Grosser]

On 10.11.2014 10:03, Roman Gareev wrote:

The patch looks great. The only piece I think we missed is the
fgraphite-code-generator flag. I would propose to remove it as well in this
commit, as it does not have any effect any more.


In this case, we’ll also have to change tests which use
fgraphite-code-generator flag (isl-ast-gen-blocks-1.c,
isl-ast-gen-blocks-2.c, isl-ast-gen-blocks-3.c,
isl-ast-gen-blocks-4.c, isl-ast-gen-if-1.c, isl-ast-gen-if-2.c,
isl-ast-gen-single-loop-1.c, isl-ast-gen-single-loop-2.c,
isl-ast-gen-user-1.c, isl-codegen-loop-dumping.c). Maybe we should do
this in the next patch?


Sure. We should drop the flag in these test cases.

This seems to make sense, as they now test something different and the 
flag removal would reflect this.


I personally would include this in the same patch. Would this be difficult?

Cheers,
Tobias

Re: RFC: Update ISL under gcc/infrastructure/ ? // Remove CLooG?

[Tobias Grosser]

On 10.11.2014 20:14, Roman Gareev wrote:

Sure. We should drop the flag in these test cases.

This seems to make sense, as they now test something different and the flag
removal would reflect this.

I personally would include this in the same patch. Would this be difficult?


I don’t think that it could be difficult. I just wanted to reduce the
size of a patch which can be found below.


Thanks!

This LGTM if it passes tests.

Tobias

Re: RFC: Update ISL under gcc/infrastructure/ ? // Remove CLooG?

[Tobias Grosser]

On 09.11.2014 18:16, Roman Gareev wrote:

Hi Tobias,

I've attached a patch which removes using of CLooG library from
Graphite. Is it fine for trunk?


The patch looks great. The only piece I think we missed is the 
fgraphite-code-generator flag. I would propose to remove it as well in 
this commit, as it does not have any effect any more.


See r212124 for the files that have changed when it was added.

In case you agree, feel free to commit the modified patch and just 
repost the final version of the patch that you applied.


We still need to update configure and the documentation, but I believe 
this can be done in a separate patch.


Cheers,
Tobias

Re: RFC: Update ISL under gcc/infrastructure/ ? // Remove CLooG?

[Tobias Grosser]

On 09.11.2014 18:35, Tobias Burnus wrote:

Roman Gareev wrote:

* Makefile.in: Remove the compilation of graphite-clast-to-gimple.o.
* graphite.c: Remove using of CLooG.
* graphite-blocking.c: Likewise.
* graphite-dependences.c: Likewise.
* graphite-poly.c: Likewise.
* graphite-poly.h: Likewise.
* graphite-scop-detection.c: Likewise.
* graphite-sese-to-poly.c: Likewise.
* graphite-clast-to-gimple.c: Removed.
* graphite-clast-to-gimple.h: Likewise.
* graphite-htab.h: Likewise.


When that's in, I think one can also remove cloog from the main
configure.ac and Makefile.tpl (assuming that no one at sourceware.org
needs it). Additionally, CLooG could then be removed from
doc/install.texi's prerequisites list and from the trunk's
contrib/download_prerequisites.


Right.


Is there something to add to https://gcc.gnu.org/gcc-5/changes.html –
either to caveats or to general optimizer improvements?


We now have a new AST generator. It produces in several cases better 
code, but that must not necessarily show up in performance numbers. The

two main benefits are:

- One run-time dependence less
- A set of advanced features

  Mircea just demonstrated one of them, but there are several others.

Cheers,
Tobias

Re: [GSoC] Elimination of CLooG library installation dependency

[Tobias Grosser]

On 16/08/2014 13:28, Roman Gareev wrote:

Richard, could you please review these patches?  We would be very glad
for your comments.

P.S: I’ve attached an improved ChangeLog_entry.


The patch and changelog looks good to me, but we still need a 
non-graphite reviewer oking the changes.


Tobias

Re: [GSoC] Elimination of CLooG library installation dependency

[Tobias Grosser]

On 13/08/2014 16:07, Roman Gareev wrote:

If I’m not mistaken all tree nodes, which have pointer type, can be
divided into two groups:  the type is a  is a pointer to data member
(TYPE_PTRMEM_P is true for it),  the type is a pointer type, and the
pointee is not a data member (TYPE_PTR_P is true for it). I think that
we’re interested in disabling of the second group handling. It can
also be divided into two  groups:  the type is a pointer to function
type (TYPE_PTRFN_P is true for it), the type is a pointer to object
type (TYPE_PTROB_P is true for it). In my opinion, the second one is
worth to be considered. It contains, for example, nop_expr (these
nodes are used to represent conversions that do not require any
code-generation) integer_cst (these nodes represent integer
constants), ssa_name. I haven’t found all types, which are contained
in it. However, I think that we could disable other types, if it is
necessary in the future.


What we should do later is to build a run-time check that ensures
no pointer overflow is happening and then just create code without it.


I think that it is better to do this when the pointer handling is completed.

I’ve attached a Change_Log, which corresponds to the previous patch.
Are they fine for trunk? Could we give a headsup on the GCC mailing
list and ask other people to try the new isl support in case this
patch is committed?


Two minor thinks:

 - I assume you verified this passes all graphite tests.
 - Please add a brief comment in the source code regarding why we
   do not want to detect such SCoPs.

Otherwise LGTM.

Cheers,
Tobias

Re: [GSoC] the separate option for all dimensions

[Tobias Grosser]

On August 12, 2014 8:15:34 AM CEST, Roman Gareev gareevro...@gmail.com wrote:
 Checking for this specific AST may cause failures with future
versions of
 isl that choose a different schedule. Could you write a regular
expression
 that checks that there is no if-condition contained in a for loop? I
think
 this best models the issue that was addressed in the original bug
report.

I’ve implemented this in the attached patch. Is it fine for trunk?

LGTM. 

Thanks 

Re: [GSoC] Elimination of CLooG library installation dependency

[Tobias Grosser]

On 09/08/2014 12:05, Roman Gareev wrote:

With just C++ code, Sven can help little. He has no knowledge about graphite
internals.


I want to ask him about correctness of ISL ASTs generated from
mentioned isl_codegens.


I am not sure if he can see it just like this.


Do you now have a setup where you can just compile one of the attached files
with graphite and everything else without and the code crashes?


No, I don't. As I mentioned earlier, all the files from this test case
individually produce object files which linked into the one
executable, which cause “Segmentation fault (core dumped)” (It'll
cause “Segmentation fault (core dumped)”, if we try to run it). I
think that it's very difficult to detach the code, which would produce
the executable and save the semantics of this big OOP project.
Furthermore, there is a possibility that the detached code can produce
no new useful information.

I've found that if we try to compile any of the btCollisionWorld.cpp,
btCollisionDispatcher.cpp
and btDiscreteDynamicsWorld.llvm.cpp by modified Graphite, the
produced object file will lead to creation of the wrong executable
(after linking with other object files generated by origin Graphite).


I am confused. It seems you attached some kind of reduced version of 
btCollisionWorld.cpp? How did you obtain it? Did you compile and test

with these versions?


That's why I think that we could consider only, for example,
btCollisionDispatcher.cpp. It contains only one scope, which is
incorrectly processed by Graphite with the ISL code generator as the
main generator.


Why did you provide two files. I assume one should be sufficient to
reproduce the crash, no?


I've detached the code, which is used by Graphite to produce similar AST's.


OK. But did you check if they actually segfault or fail?


I think for the one file you choose, it would be interesting to look
at the code generation input as well as the kernels generated by CLooG and
isl. Maybe we can understand what is going on.


Yes, exactly those that you provided. At a first look, I don't see 
anything obvious wrong, except that the huge modulo values, which arise 
from some integer wrapping support Sebastian added once for unsigned 
integers.


I see two approaches you can take:

1) The easy one

Disallow unsigned integers in the scop detection. I have doubts we can 
do anything good with those huge modulo constraints placed all over the 
generated code


2) Try to understand the test case

I would try a couple of easy unsigned int loops to see if we can handle 
them properly. Something like:


for (unsigned long i = 0; i  M; i++)
  A[i] += i;

At best, we could even write your test case as such a loop and reproduce
the bug outside of this huge C++ code. Maybe looking at the GIMPLE 
allows you to write C code that has similar behavior and where we could 
check the output?


Tobias

Re: [GSoC] Elimination of CLooG library installation dependency

[Tobias Grosser]

On 11/08/2014 09:11, Roman Gareev wrote:

I am confused. It seems you attached some kind of reduced version of
btCollisionWorld.cpp? How did you obtain it? Did you compile and test
with these versions?


I’ve manually selected parts of code, which produce the scope.

I’ve found out that this bug is most probably caused by absence of
pointer handling.  The tree, which is corresponding to P_11 has
pointer type. Furthermore,  if we consider the transformed gimple code
for (it can be found attached), we’ll see that it contains wrong
parts:


Could you please advise me an algorithm for pointer handling?


Did you try your code with 64bit pointer types?

In any case, I don't think it is worth spending time on this. I would 
check in the scop detection that we disable the handling of unsigned and 
pointer types. It is a complex thing to model and the approach currently 
taking of always model their wrapping behaviour seems wrong.

What we should do later is to build a run-time check that ensures
no pointer overflow is happening and then just create code without it.

Cheers,
Tobias

Re: [GSoC] Elimination of CLooG library installation dependency

[Tobias Grosser]

On 09/08/2014 09:42, Roman Gareev wrote:

Is this segmentation fault at compile time or at run-time? I believe it was
a segfault at run-time due to a miscompile.


Yes, it's a segfault at run-time. These source codes produce wrong object files.


Possibly. Can you split the .cpp files such that you only compile a single
function with graphite and that compiling this function causes the
miscompile. This allows us to look at less code.


I've tried to reduce btCollisionWorld.cpp and
btCollisionDispatcher.cpp (They can be found attached). Should we ask
Sven?


With just C++ code, Sven can help little. He has no knowledge about 
graphite internals.


Do you now have a setup where you can just compile one of the attached 
files with graphite and everything else without and the code crashes?


Why did you provide two files. I assume one should be sufficient to 
reproduce the crash, no?


I think for the one file you choose, it would be interesting to look
at the code generation input as well as the kernels generated by CLooG 
and isl. Maybe we can understand what is going on.


Cheers,
Tobias

Re: [GSoC] Elimination of CLooG library installation dependency

[Tobias Grosser]

On 08/08/2014 15:11, Roman Gareev wrote:

I think this is fine. On the other side, I think the test case itself
is unnecessarily large. I would assume the majority of the code could
be deleted while still triggering the bug. Could you give it a shot.

I've attached an improved version of the patch.


LGTM.


Is there anything else you still would like to do?

I wanted to make the current code available to be able to fix all new
possible bugs before 'pencils down'. If I have free time, I'll try to
improve the performance of the generation.


Good, though before let's try to get the correctness right.


Otherwise, I believe fixing the last remaining bugs is of high importance, as 
we want to enable
this code as soon as possible to avoid future bitrot.

I understand that reducing this may require some work, but I don't think it
is that hard. Specifically, you could first compile the individual *.cpp
files to .o files once using once graphite once not.

I've found out that btCollisionWorld.cpp, btCollisionDispatcher.cpp
and btDiscreteDynamicsWorld.llvm.cpp cause “Segmentation fault”. All
of them produce similar ASTs:


Is this segmentation fault at compile time or at run-time? I believe it 
was a segfault at run-time due to a miscompile.



btCollisionWorld.cpp:

CLAST generated by CLooG:

if (8*T_45 = -T_44+9) {
   for (scat_1=0;scat_1=T_45-1;scat_1++) {
 if ((8*scat_1+T_44+18446744073709551615)%18446744073709551616 =
18446744073709551614) {
   (scat_1);
 }
   }
}

isl_codegen:

[P_45, P_44] - { S_12[i0] - [0, i0, 0] : exists (e0 = floor((-1 +
P_45)/4294967296), e1 = floor((P_44 + 8i0)/18446744073709551616): i0

= 0 and 4294967296e0 = -1 + P_45 and 4294967296e0 = -4294967296 +

P_45 and 4294967296e0 = -1 + P_45 - i0 and i0 = 2147483646 and
18446744073709551616e1 = -18446744073709551615 + P_44 + 8i0 and
18446744073709551616e1 = -1 + P_44 + 8i0) }

[P_45, P_44] - {  : exists (e0 = floor((-1 + P_45)/4294967296):
4294967296e0 = -1 + P_45 and 4294967296e0 = -2147483647 + P_45 and
P_45 = -2147483648 and P_45 = 2147483647 and P_44 = 0 and P_44 =
18446744073709551615) }

[P_45, P_44] - { [i0, i1, i2] - separate[o0] }

ISL AST generated by ISL:

for (int c1 = 0; c1  P_45; c1 += 1)
   if ((P_44 + 8 * c1) % 18446744073709551616 = 1)
 S_12(c1);

btCollisionDispatcher.cpp:

CLAST generated by CLooG:

if (8*T_81 = -T_80+9) {
   for (scat_1=0;scat_1=T_81-1;scat_1++) {
 if ((8*scat_1+T_80+18446744073709551615)%18446744073709551616 =
18446744073709551614) {
   (scat_1);
 }
   }
}

isl_codegen:

[P_81, P_80] - { S_22[i0] - [0, i0, 0] : exists (e0 = floor((-1 +
P_81)/4294967296), e1 = floor((P_80 + 8i0)/18446744073709551616): i0

= 0 and 4294967296e0 = -1 + P_81 and 4294967296e0 = -4294967296 +

P_81 and 4294967296e0 = -1 + P_81 - i0 and i0 = 2147483646 and
18446744073709551616e1 = -18446744073709551615 + P_80 + 8i0 and
18446744073709551616e1 = -1 + P_80 + 8i0) }

[P_81, P_80] - {  : exists (e0 = floor((-1 + P_81)/4294967296):
4294967296e0 = -1 + P_81 and 4294967296e0 = -2147483647 + P_81 and
P_81 = -2147483648 and P_81 = 2147483647 and P_80 = 0 and P_80 =
18446744073709551615) }

[P_81, P_80] - { [i0, i1, i2] - separate[o0] }

ISL AST generated by ISL:

for (int c1 = 0; c1  P_81; c1 += 1)
   if ((P_80 + 8 * c1) % 18446744073709551616 = 1)
 S_22(c1);

btDiscreteDynamicsWorld.llvm.cpp:

CLAST generated by CLooG:

if (8*T_24 = -T_23+9) {
   for (scat_1=0;scat_1=T_24-1;scat_1++) {
 if ((8*scat_1+T_23+18446744073709551615)%18446744073709551616 =
18446744073709551614) {
   (scat_1);
 }
   }
}

isl_codegen:

[P_24, P_23] - { S_13[i0] - [0, i0, 0] : exists (e0 = floor((-1 +
P_24)/4294967296), e1 = floor((P_23 + 8i0)/18446744073709551616): i0

= 0 and 4294967296e0 = -1 + P_24 and 4294967296e0 = -4294967296 +

P_24 and 4294967296e0 = -1 + P_24 - i0 and i0 = 2147483646 and
18446744073709551616e1 = -18446744073709551615 + P_23 + 8i0 and
18446744073709551616e1 = -1 + P_23 + 8i0) }

[P_24, P_23] - {  : exists (e0 = floor((-1 + P_24)/4294967296):
4294967296e0 = -1 + P_24 and 4294967296e0 = -2147483647 + P_24 and
P_24 = -2147483648 and P_24 = 2147483647 and P_23 = 0 and P_23 =
18446744073709551615) }

[P_24, P_23] - { [i0, i1, i2] - separate[o0] }

ISL AST generated by ISL:

for (int c1 = 0; c1  P_24; c1 += 1)
   if ((P_23 + 8 * c1) % 18446744073709551616 = 1)
 S_13(c1);

CLAST generated by CLooG:

if (8*T_46 = -T_45+9) {
   for (scat_1=0;scat_1=T_46-1;scat_1++) {
 if ((8*scat_1+T_45+18446744073709551615)%18446744073709551616 =
18446744073709551614) {
   (scat_1);
 }
   }
}

isl_codegen:

[P_46, P_45] - { S_16[i0] - [0, i0, 0] : exists (e0 = floor((-1 +
P_46)/4294967296), e1 = floor((P_45 + 8i0)/18446744073709551616): i0

= 0 and 4294967296e0 = -1 + P_46 and 4294967296e0 = -4294967296 +

P_46 and 4294967296e0 = -1 + P_46 - i0 and i0 = 2147483646 and
18446744073709551616e1 = -18446744073709551615 + P_45 + 8i0 and
18446744073709551616e1 = -1 + P_45 + 8i0) }

[P_46, P_45] - {  : 

Re: [GSoC] the separate option for all dimensions

[Tobias Grosser]

On 06/08/2014 17:21, Roman Gareev wrote:

I've tested the modified version of Graphite using the gcc test suite
and haven't found out new failed tests.

However, pr35356-2.c is still not suitable for testing. The ISL AST
generated from its source code doesn't contain MIN or MAX.

 if (k = -1) {
   for (int c1 = 0; c1  n; c1 += 1)
 S_7(c1);
 } else if (k = n) {
   for (int c1 = 0; c1  n; c1 += 1)
 S_7(c1);
 } else {
   for (int c1 = 0; c1  k; c1 += 1)
 S_7(c1);
   S_6(k);
   for (int c1 = k + 1; c1  n; c1 += 1)
 S_7(c1);
 }

Should we make pr35356-2.c to be similar to isl-codegen-loop-dumping.c
by replacing “MIN_EXPR\[^\\n\\r]*; and MAX_EXPR\[^\\n\\r]*; with
the regexp, which contains the the above-mentioned isl ast?


Checking for this specific AST may cause failures with future versions 
of isl that choose a different schedule. Could you write a regular 
expression that checks that there is no if-condition contained in a for 
loop? I think this best models the issue that was addressed in the 
original bug report.


(Also as this test then becomes isl specific I propose to just force the 
use of isl in the run line).


Cheers,
Tobias

Re: [GSoC] Elimination of CLooG library installation dependency

[Tobias Grosser]

On 06/08/2014 17:21, Roman Gareev wrote:

Hi Tobias,

I've attached the patch, which should eliminate CLooG library
installation dependency from GCC. The CLooG AST generator is still the
main code generator, but the isl ast generator will be chosen in case
of nonavailability of CLooG library.


Nice.


However, I've found out a problem. Almost all the functions of the ISL
cannot be used without installed CLooG. (I get errors which contain
“undefined reference to...”). Maybe I missed something. What do you
think about this?


This is surprising.

What is the exact error message? To which library does gcc link (Check 
with 'ldd cc1')? I wonder if gcc happens to link against the system 
CLooG/isl instead of the ones you installed?

Also, does objdump -x libisl.so show those missing symbols?


I also have a few questions about gcc. Could you please answer them?

Should Makefile.in be regenerated or manually changed? (I haven't
found out how to regenerate.)


I think it is manually maintained.


I've used printf to print “The CLooG code generator cannot be used
+(CLooG is not available). The ISL code generator was chosen.\n”.
Should another function be used for this purpose?


I have no idea. Let's leave it for now. I expect the CLooG code to 
disappear very soon.


Also, regarding this patch. It seems you mix two important changes.

1) The configure/makefile changes that make cloog optional
2) The switch from isl to cloog

Best starting with 2), followed by 1).

To commit 2), I would like you to run a wider set of tests (e.g., the 
LLVM test suite). If this passes successful, we should give a headsup on 
the GCC mailing list and ask other people to try the new isl support.

If now bugs have found, we switch.

Cheers,
Tobias

Re: [GSoC] the separate option for all dimensions

[Tobias Grosser]

On 05/08/2014 06:02, Roman Gareev wrote:

I've attached the patch, which sets the separate option for all
dimensions. Is it fine for trunk?


LGTM.

Tobias

Re: [GSoC] checking for the loop parallelism

[Tobias Grosser]

On 04/08/2014 08:09, Roman Gareev wrote:

Those waw dependences seem to be correct. Should even the previous analysis
only mark the j-loop as parallel?


The previous and the current analysis mark the j-loop as
nonparallelizable. (Possibly, I don't fully understand the question.
Could you please reformulate it?)


I would expect the to mark the i loop as non-parallel, but the j-loop
as parallel. What is the partial schedule, the set of dependences and
the dimension you check for both the i and the j loop?

Cheers,
Tobias

Re: Replacement of isl_int by isl_val

[Tobias Grosser]

LGTM.

Cheers,
Tobias

Re: [GSoC] checking for the loop parallelism

[Tobias Grosser]

On 04/08/2014 16:23, Roman Gareev wrote:

I would expect the to mark the i loop as non-parallel, but the j-loop
as parallel. What is the partial schedule, the set of dependences and
the dimension you check for both the i and the j loop?


Yes, you are right. The i loop is non-parallel and j-loop is parallel.
I've found that this substraction “ int dimension = isl_space_dim
(schedule_space, isl_dim_out) – 1;” was wrong.

The attached patch contains the improved version of checking for the
loop parallelism, which passes all the tests from
libgomp/testsuite/libgomp.graphite except
graphite-isl-ast-to-gimple.c.

P.S.: I've added checking of the ux's emptiness and of the x's value,
because ux is empty for specific test cases and produces the following
error: “/home/roman/graphite_stuff/isl-0.12.2/isl_union_map.c:418:
union map needs to contain elements in exactly one space”


LGTM. Very nice work!

Cheers,
Tobias

Re: [GSoC] checking for the loop parallelism

[Tobias Grosser]

On 03/08/2014 16:05, Roman Gareev wrote:

This looks very similar to what we reported to the isl mailing list. It is
definitely not the best test case for the parallelism patch. In fact, I
doubt this requires the parallelism test at all.


I've found out, that Graphite generates the expected code using the
separate option for all dimensions:

{
   for (int c1 = 0; c1  min(n, mid); c1 += 1) {
 S_6(c1);
 S_8(c1);
   }
   for (int c1 = max(mid, 0); c1  n; c1 += 1) {
 S_7(c1);
 S_8(c1);
   }
}


Good.


However, there are problems in vectorization of this code (I've
attached .vect files generated by versions, which use CLooG and ISL).
It seems that it is related to inappropriate type sizes. Do you know
anything about it?


No idea here. This is a question for the vectorizer people. I propose to 
focus on correctness first. After this is finished, we can have a look 
at the performance of the generated code as well as a look at possible 
bad interactions with the vectorizer.



You should have a look at the following test case for openmp tests:
libgomp/testsuite/libgomp.graphite


Graphite successfully passes all the tests from
libgomp/testsuite/libgomp.graphite except graphite-isl-ast-to-gimple.c
and graphite-poly.h.

If we consider the code generated by ISL and by CLooG from
force-parallel-5.c, we'll see, that they are similar:

the code generated by ISL:

for (int c1 = 0; c1 = 1499; c1 += 1)
   S_3(c1);

for (int c1 = 0; c1 = 497; c1 += 1)
   for (int c3 = 0; c3 = c1; c3 += 1)
 S_7(c1, c3);

the code generated by ClooG:


for (scat_1=0;scat_1=1499;scat_1++) {
   (scat_1);
}

for (scat_1=0;scat_1=497;scat_1++) {
   for (scat_3=0;scat_3=scat_1;scat_3++) {
 (scat_1,scat_3);
   }
}

the source code:

void abort (void);

#define N 500

void foo(void)
{
   int i,j;
   int A[3*N], B[3*N];

   for (i = 0; i  3*N; i++)
 B[i] = A[i] = i;

   for (i = 1; i  N; i++)
 for (j = 1; j  i; j++)
   /* This loop carried no dependency, it fails
at code generation part.*/
   A[j+N] = A[j] + j;

   for (i = 1; i  N; i++)
 for (j = 1; j  i; j++)
   if (A[j+N] != B[j] + j)
abort();
}

int main(void)
{
   foo();

   return 0;
}

The previous implementation of dependence analysis marks “for
(scat_1=0;scat_1=497;scat_1++) {“ as parallelizable. However, the
current dependence analysis finds must_waw dependence:

{ [i0] - [1 + i0] : i0 = 1 and i0 = 496 }


Those waw dependences seem to be correct. Should even the previous 
analysis only mark the j-loop as parallel?



(schedule:

{ S_7[i0, i1] - [i0] : exists (e0 = [(i0)/4294967296]: i0 = 0 and i0
= 497 and i1 = 0 and 4294967296e0 = i0 and 4294967296e0 =
-4294967295 + i0 and 4294967296e0 = i0 - i1 and i1 = 498) }

dependence:

{ S_7[i0, i1] - S_7[1 + i0, i1] : exists (e0 = [(1 + i0)/4294967296],
e1 = [(i0)/4294967296]: i1 = 0 and i1 = 498 and i0 = 0 and i0 =
496 and 4294967296e0 = 1 + i0 - i1 and 4294967296e0 = 1 + i0 and
4294967296e0 = -4294967294 + i0 and i1 = i0 and 4294967296e1 = i0 -
i1 and 4294967296e1 = -4294967295 + i0 and 4294967296e1 = i0) })

Could you please advise me what can be improved in the the current analysis?


Why did you copy this code, instead of exposing the carries_deps functions
from graphite-dependences?


If I'm not mistaken, the carries_deps functions can't be called in
graphite-isl-ast-to-gimple.c. Should we add its declaration to
graphite-poly.h to allow this?


Yes.

Tobias

Re: [GSoC] checking for the loop parallelism

[Tobias Grosser]

On 02/08/2014 11:49, Roman Gareev wrote:

Hi Roman,

you can get this information from the isl_ast_build that was used when
generating a certain loop (you can access this isl_ast_build from the
callbacks isl_ast_build_set_before_each_for and
isl_ast_build_set_after_each_for). With isl_ast_build_get_schedule, you can
get an incomplete schedule (less dimensions then the schedule that you gave
to the isl ast generator). Specifically, it only contains the dimensions of
the current loop and all surrounding ones. Consequently the last dimension
in this incomplete schedule is the dimension you want to check for
parallelism.

Hi Tobias,

thank you! I've attached a patch, which contains the first draft of
checking for the loop parallelism.

If I'm not mistaken, the depth, which can be obtained from
isl_ast_build, is only suitable for the incomplete schedule, which can
be obtained using isl_ast_build_get_schedule. That's why the temporary
implementation works with the incomplete schedule instead of the
result from scop_get_transformed_schedule.


Yes. Using the isl_ast_build_get_schedule is the right approach.


I have a question about vect-pr43423.c. CLooG generates the following
code from this example:

vect-pr43423.c
for (scat_1=0;scat_1=min(mid_6-1,n_5-1);scat_1++) {
   (scat_1);
   (scat_1);
}
for (scat_1=max(0,mid_6);scat_1=n_5-1;scat_1++) {
   (scat_1);
   (scat_1);
}

This loops can be parallelized, according to the description of pr43423:

...
void foo(int n, int mid)
{
   int i;
   for(i=0; in; i++)
 {
   if (i  mid)
 a[i] = a[i] + b[i];
   else
 a[i] = a[i] + c[i];
 }
}

chfang@pathscale:~/gcc$ gcc -O3 -ftree-vectorizer-verbose=7 -c foo.c

foo.c:6: note: not vectorized: control flow in loop.
foo.c:3: note: vectorized 0 loops in function.

This loop can be vectorized by icc.

For this case, I would expect to see two loops with iteration range
of [0, mid) and [mid, n). Then both loops can be vectorized.
...

and the code of vect-pr43423.c:

/* { dg-final { scan-tree-dump-times vectorized 2 loops 1 vect } } */

ISL generates the following code:

for (int c1 = 0; c1  n; c1 += 1) {
   if (mid = c1 + 1) {
 S_6(c1);
   } else
 S_7(c1);
   S_8(c1);
}

I think it can't be parallelized.


This looks very similar to what we reported to the isl mailing list. It 
is definitely not the best test case for the parallelism patch. In fact, 
I doubt this requires the parallelism test at all.


You should have a look at the following test case for openmp tests:
libgomp/testsuite/libgomp.graphite

I reply to the isl mailing list regarding the problem reported above.




Index: gcc/graphite-isl-ast-to-gimple.c
===
--- gcc/graphite-isl-ast-to-gimple.c(revision 213262)
+++ gcc/graphite-isl-ast-to-gimple.c(working copy)
@@ -435,7 +435,14 @@
redirect_edge_succ_nodup (next_e, after);
set_immediate_dominator (CDI_DOMINATORS, next_e-dest, next_e-src);

-  /* TODO: Add checking for the loop parallelism.  */
+  if (flag_loop_parallelize_all)
+  {
+isl_id *id = isl_ast_node_get_annotation (node_for);
+gcc_assert (id);
+if (isl_id_get_user (id) != NULL)
+  loop-can_be_parallel = true;


I would prefer if we actually use a user structure which contains an 
isParallel flag. The use of the presence of isl_id to show parallelism 
is a little indirect.



+static __isl_give isl_map *
+apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
+   __isl_keep isl_union_map *deps)
+{
+  isl_map *x;
+  isl_union_map *ux, *trans;
+
+  trans = isl_union_map_copy (schedule);
+  trans = extend_schedule (trans);
+  ux = isl_union_map_copy (deps);
+  ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
+  ux = isl_union_map_apply_range (ux, trans);
+  if (isl_union_map_is_empty (ux))
+{
+  isl_union_map_free (ux);
+  return NULL;
+}
+  x = isl_map_from_union_map (ux);
+
+  return x;
+}
+
+/* Return true when DEPS is non empty and the intersection of LEX with
+   the DEPS transformed by SCHEDULE is non empty.  LEX is the relation
+   in which all the inputs before DEPTH occur at the same time as the
+   output, and the input at DEPTH occurs before output.  */
+
+static bool
+carries_deps (__isl_keep isl_union_map *schedule,
+ __isl_keep isl_union_map *deps,
+ int depth)
+{
+  bool res;
+  int i;
+  isl_space *space;
+  isl_map *lex, *x;
+  isl_constraint *ineq;
+
+  if (isl_union_map_is_empty (deps))
+return false;
+
+  x = apply_schedule_on_deps (schedule, deps);
+  if (x == NULL)
+return false;
+  space = isl_map_get_space (x);
+  space = isl_space_range (space);
+  lex = isl_map_lex_le (space);
+  space = isl_map_get_space (x);
+  ineq = isl_inequality_alloc (isl_local_space_from_space (space));
+
+  for (i = 0; i  depth - 1; i++)
+lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
+
+  /* in + 1 = out  */
+  ineq = 

Re: [GSoC] type of an isl_ast_expr_id

[Tobias Grosser]

On 31/07/2014 08:19, Roman Gareev wrote:

Could you please advise me how is it better to answer the following
questions of Sven:


In what way is it not optimal?
That is, what are your optimality criteria?


(I could answer them, but I don't want to miss anything)


Don't worry. Just give it a shot. ;-) (I even don't understand the 
question in this case. Not having conditions in the loops reduces

control overhead, while in this case it does not seem to come with
code size growth either.)

Tobias

Re: [GSoC] type of an isl_ast_expr_id

[Tobias Grosser]

On 30/07/2014 09:56, Roman Gareev wrote:

Blindly converting type sizes is not a good idea and may be problematic when
we switch to smaller types. As we can obviously only improve this when we
have the appropriate support in isl, I think the attached patch is fine.
However, please add a fixme that states that this should
be looked at again at the moment when we get isl support to derive the
optimal types.

I've attached a patch, which contains the fixme.


OK. I proposed a slightly longer description. With the updated 
description, you can commit this patch.



Please have a look at the original bug report:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35356

The isl ast generator should produce something like:

   for (i = 0; i  min (n, k); i++)
  a[i] = i;
   if (k = 0  k  n)
  a[k] = 1;
   for (i = max(k+1,0); i  n; i++)
  a[i] = i;

CLooG does not generate optimal code either, but the code generated by isl
is a regression compared to CLooG.

Can you generate an isl_codegen input for this test case and verify that the
latest public version of isl does not generate this optimal code either. If
it does not, please report this as an optimization bug to the isl mailing
list.

After you got feedback, I think it is OK to disable this test and to
add a FIXME explaining why this test is disabled and if we can expect a fix
in later versions of isl.

I've generated the code using the isl-0.13

if (n = k + 1) {
   for (int c1 = 0; c1  n; c1 += 1) {
 if (c1 = k + 1) {
   S_7(c1);
 } else if (k = c1 + 1) {
   S_7(c1);
 } else
   S_6(k);
   }
} else
   for (int c1 = 0; c1  n; c1 += 1)
 S_7(c1);

If I'm not mistaken it's also a regression compared to ClooG and it's
better to report this to the isl mailing list.


That's what I suggested earlier, no? The only thing I would like you to 
check beforehand is if the very same problem still exists with isl 
trunk. For this you need to generate an input file for the 'isl_codegen' 
tool as it comes with isl that allows to reproduce the bug. The very 
same input file can then be submitted to the isl mailing list as a bug 
report. Could you do the reporting (and CC me)?



What is the problem with this last test case?

It is related to checking for the loop parallelism, which is not yet
implemented in the current version of graphite-isl-ast-to-gimple.c.


OK. So yes, you are right that we need the parallelism test soon.

Cheers,
Tobias

Re: [GSoC] type of an isl_ast_expr_id

[Tobias Grosser]

On 30/07/2014 14:32, Roman Gareev wrote:

OK. I proposed a slightly longer description. With the updated description,
you can commit this patch.


I've fixed the fixme.

FIXME: We should replace blind conversation of id's type with
derivation of the optimal type when we get the corresponding isl
support. Blindly converting type sizes may be problematic when we
switch to smaller types.



Would you add anything to it?


Fine with me.


That's what I suggested earlier, no? The only thing I would like you to
check beforehand is if the very same problem still exists with isl trunk.
For this you need to generate an input file for the 'isl_codegen' tool as it
comes with isl that allows to reproduce the bug. The very same input file
can then be submitted to the isl mailing list as a bug report. Could you do
the reporting (and CC me)?


Yes, I wanted to make sure that the code generated by the isl-0.13 is
also not optimal (I sent you the code generated by isl-0.12.2 before).
The report has been sent to the isl mailing list and CC you.


Great. Thanks.

(Sven already replied)

Two comments on your bug report:

1) It would be helpful to also point give the output CLooG generates for 
similar input


2) The input is a little involved. If you can provide a minimal test 
case, this normally helps in getting bugs fixed faster.



Cheers,
Tobias

Re: [GSoC] type of an isl_ast_expr_id

[Tobias Grosser]

On 29/07/2014 12:14, Roman Gareev wrote:

I've tested Graphite with the ISL AST generator as the main code
generator and found out the following problem: in the current
implementation the gcc_expression_from_isl_ast_expr_id can return a
tree of a type, which doesn't correspond to the type chosen for
graphite expressions.


[..]



It is caused by difference in precisions of arguments in the min
expression. The attached patch may fix this.


Great.

Blindly converting type sizes is not a good idea and may be problematic 
when we switch to smaller types. As we can obviously only improve this 
when we have the appropriate support in isl, I think the attached patch 
is fine. However, please add a fixme that states that this should
be looked at again at the moment when we get isl support to derive the 
optimal types.



I've also found out that pr35356-2.c is no longer suitable for
testing. The following CLooG AST

for (scat_1=0;scat_1=min(k_6-1,n_5-1);scat_1++) {
   (scat_1);
}
if ((k_6 = 0)  (n_5 = k_6+1)) {
   (k_6);
}
for (scat_1=max(0,k_6+1);scat_1=n_5-1;scat_1++) {
   (scat_1);
}

is generated from its source code

int a[100];

int
foo (int bar, int n, int k)
{
   int i;

   for (i = 0; i  n; i++)
 if (i == k)
   a[i] = 1;
 else
   a[i] = i;

   return a[bar];
}

The test checks that the dump file contains four MIN_EXPR and four MAX_EXPR

/* { dg-final { scan-tree-dump-times MIN_EXPR\[^\\n\\r]*; 4 graphite } } */
/* { dg-final { scan-tree-dump-times MAX_EXPR\[^\\n\\r]*; 4 graphite } } */

However, the ISL AST generated from this code

if (k = 1) {
   for (int c1 = 0; c1  n; c1 += 1)
 if (c1 = k + 1) {
   S_7(c1);
 } else if (k = c1 + 1) {
   S_7(c1);
 } else
   S_6(k);
} else {
   if (k == 0)
 S_6(0);
   for (int c1 = max(k + 1, 0); c1  n; c1 += 1)
 S_7(c1);
}

doesn't contain min expression at all.

Should we remove /* { dg-final { scan-tree-dump-times
MIN_EXPR\[^\\n\\r]*; 4 graphite } } */ from this test case?


Please have a look at the original bug report:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35356

The isl ast generator should produce something like:

  for (i = 0; i  min (n, k); i++)
 a[i] = i;
  if (k = 0  k  n)
 a[k] = 1;
  for (i = max(k+1,0); i  n; i++)
 a[i] = i;

CLooG does not generate optimal code either, but the code generated by 
isl is a regression compared to CLooG.


Can you generate an isl_codegen input for this test case and verify that 
the latest public version of isl does not generate this optimal code 
either. If it does not, please report this as an optimization bug to the 
isl mailing list.


After you got feedback, I think it is OK to disable this test and to
add a FIXME explaining why this test is disabled and if we can expect a 
fix in later versions of isl.



P.S.: The other graphite tests (except vect-pr43423.c) are passed by
graphite in case we run it with the ISL AST generator.


Amazing.

What is the problem with this last test case?

Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 27/07/2014 08:12, Roman Gareev wrote:

Can you explain why you believe it is hard/impossible to generate a test
case without reduction?


I don't believe this. I only know that all the test cases considered
by me have the same problem.

Could you please explain what is 'reduction'? I've found out that,
according to the comment of the rewrite_reductions_out_of_ssa (this
function duplicates pbbs), the rewrite_reductions_out_of_ssa  rewrite
out of SSA all the reduction phi nodes of SCOP. What are reduction phi
nodes? How are they related to 'reduction'?


A reduction is an operation that combines a set of elements into a 
single element.


for (i = 0; i  100; i++)
   sum += i;

combines the different elements 'i' into the single element 'sum'. 
Reductions where the combine operation *here '+') is associative and 
commutative can be reordered. This means you can e.g. write the loop as


for (i = 99; i = 0; i--)
   sum += i;

and you get the same result. There are two ways to ensure something is 
not optimized as a reduction


1) Destroy associativity/commutativity

Floating point operations are generally not associative/commutative, 
except if -ffast-math is given to the compiler


2) Do not reduce into one element.

If we just assign to different elements of an array, there is no 
possibility we have a reduction.


Let's get back to the earlier test case:

for (i = 0; i  n; i++) {
   if (i = m)
T: A[i] = i;

S: A[i + p] = j;
}

What is the ast generated for this one? I just created this input file 
for isl_codegen:


[n,m] - {S[i] - [i]: 0= i = n;T[i] - [i]: 0= i = m and i = n}
[n,m] - {:n,m  1}
{}

$ isl_codegen  input.file

for (int c0 = 0; c0 = n; c0 += 1) {
  if (m = c0)
T(c0);
  S(c0);
}

Is something in graphite preventing us to generate this simple loop with 
just one if-condition and no statement duplication?


Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 27/07/2014 12:48, Roman Gareev wrote:

Thank you! I've attached patches with a test case (it is located in
patch1.txt), which generates the following ISL AST:

for (int c1 = 0; c1 = 49; c1 += 1) {
   if (c1 = 24)
 S_4(c1);
   S_5(c1);
}

I think that it doesn't contain reduction and doesn't yield several
bbs. I've also checked that pbbs correspond to pbbs of pbb-domain and
pbb-transformed.


OK. LGTM.

Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 26/07/2014 10:59, Roman Gareev wrote:

If I'm not mistaken, the reason of this bug is incorrect creation of a
poly_bb_p for basic_block from the existing pbb in new_pbb_from_pbb
(It is located in graphite-sese-to-poly.c). I think, that we should
set a new id of pbb1-domain (instead of using the id of the pbb),
which contains pointer to the pbb1.



I found out this after dumping of an index of pbb in the user
statement S_3. Its index is 9. It is created in
rewrite_reduction_out_of_ssa using new_pbb_from_pbb and the pbb with
index 3. After that the user statement S_3 is removed in
build_scop_drs, but the id of the  pbb-domain and the
pbb-transformed point to the old pbb with index 3.


Interesting. I was not even aware that we did statement splitting for 
reductions. Very nice analysis.



I've attached the patch, which may fix this.

--
Cheers, Roman Gareev.


patch.txt


Index: gcc/graphite-sese-to-poly.c
===
--- gcc/graphite-sese-to-poly.c (revision 212995)
+++ gcc/graphite-sese-to-poly.c (working copy)
@@ -2044,6 +2044,10 @@
break;

pbb1-domain = isl_set_copy (pbb-domain);
+  char name[50];
+  snprintf (name, sizeof (name), S_%d, pbb_index (pbb1));
+  pbb1-domain = isl_set_set_tuple_id (pbb1-domain,
+  isl_id_alloc (scop-ctx, name, pbb1));


Any reason you don't use isl_id_for_pbb() to create this isl_id?

Otherwise, the patch looks good to me. You can commit it if the graphite 
tests still pass and you add an appropriate ChangeLog entry.


Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 24/07/2014 12:09, Roman Gareev wrote:

I've attached the patch, which contains generation of Gimple code from
isl_ast_node_if.

However, I've found out a problem. When I'm trying to generate Gimple
code from, for example, the following ISL AST:

{
   for (int c1 = 0; c1 = 49; c1 += 1) {
 S_6(c1);
 if (c1 = 48) {
   S_3(c1);
   if (c1 = 24)
 S_4(c1);
   S_5(c1);
 }
   }
   S_7();
}

the pointer to Gimple basic block of S_3's poly basic block is NULL.

Could you please advise me possible reasons of this issue?

The source code of the example:

int
foo ()
{
   int i, res = 0;

   for (i = 0; i  50; i++)
 {
   if (i = 25)
 res += i;
 }

   return res;
}

extern void abort ();

int
main (void)
{
   int res = foo ();

   if (res != 1225)
 abort ();

   return 0;
}


This patch looks also good. Can you quickly repost with the two test 
cases as well as the appropriate ChangeLog, before I give the final OK.


Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 26/07/2014 11:53, Roman Gareev wrote:

Any reason you don't use isl_id_for_pbb() to create this isl_id?


Yes, it is redundant. I've used isl_id_for_pbb() in the improved version.


Otherwise, the patch looks good to me. You can commit it if the graphite tests 
still pass and you add an appropriate ChangeLog entry.


I haven't found out regression during testing with the graphite tests.


This patch looks also good. Can you quickly repost with the two test cases as 
well as the appropriate ChangeLog, before I give the final OK.


If I'm not mistaken, I sent you only one test case. Should we create
another one?


Right, I got confused.

I would still add a test case which does not contain a reduction (+=)
and where graphite is not duplicating pbbs.

If you make res of type float I assume graphite will not detect it as a 
reduction. On the other side, it may not even introduce if conditions. 
So you may need a little bit more complicated code e.g:



  for (i = 0; i  50; i++)
{
  res += i * 2.1;
  if (i = 25)
res += i * 3;
}

This should in the best case yield an isl_ast which matches the input code.

Also, please add a comment to the other test case that notes what kind 
of issue this one is testing (reduction, where the pbbs are possibly 
duplicated).


Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 26/07/2014 14:59, Roman Gareev wrote:

I've tried to compile your example and had the similar problem. It
generates the following ISL AST


{
   for (int c1 = 0; c1 = 49; c1 += 1) {
 S_6(c1);
 if (c1 = 48) {
   S_3(c1);
   S_9(c1);
   if (c1 = 24)
 S_4(c1);
   S_5(c1);
 }
   }
   S_7();
}


where S_9 has pbb-domain and pbb-transformed of S_3. A pointer to a
Gimple basic block is not NULL now, but it leads to the wrong answer.


What do you mean by wrong answer? Is there still a bug in the code 
generation or the AST is just more complex as expected.



I've tried different examples, which generate ISL AST, but they have
same problems. Could you please advise me another one?


To my understanding bb copies are introduced in case reductions are 
seen. You could try to just initialize an array (maybe a little bit more 
complex, but without += statements):


for i:
  A[i] = ...

You could do the summation/verfication outside of the scop e.g. in the 
main function.


Cheers
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 26/07/2014 15:48, Roman Gareev wrote:

What do you mean by wrong answer? Is there still a bug in the code
generation or the AST is just more complex as expected.


I mean that the value of res is wrong. I think it is because of the
wrong id of pbb-domain and pbb-transformed inherited from S_3 by S_9
(It was correct for S_3, but it is incorrect for S_9).


Sorry Roman. I am still confused. Are we looking for a test case or are 
we still trying to understand an issue. Specifically, do we still 
incorrectly transform the code even after your isl_id_for_pbb() patch?



To my understanding bb copies are introduced in case reductions are seen.
You could try to just initialize an array (maybe a little bit more complex,
but without += statements):

for i:
   A[i] = ...

You could do the summation/verfication outside of the scop e.g. in the main
function.


It seems that it doesn't help (at least for now).


Help for what? I was looking to create a simple test case. Is there 
still an open bug?


I am looking for a simple test case that does _not_ contain a reduction 
in addition to the test case you already have.



However, I've found out the following example:

static int __attribute__((noinline))
foo ()
{
   int i, res = 0;

   for (i = 0; i  50; i++)
 {
   if (i  5)
 res += 1;
 }


This one still has a reduction.


It gives the correct result, inspite of duplicating of pbbs and
generates the following ISL AST

{
   for (int c1 = 0; c1 = 49; c1 += 1) {
 for (int c2 = 0; c2 = 1; c2 += 1)
   S_3(c1);
 if (c1 = 4)
   S_4(c1);
 S_5(c1);
   }
   S_7();


And this one still duplicates pbbs. So this is not the simple test case 
I am looking for. It introduces several new statements I do not 
understand, so it does not seem to be a trivial test case.



Maybe we could use it. What do you think about this?


What do you want to use it for?

Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 26/07/2014 16:16, Roman Gareev wrote:

I would still add a test case which does not contain a reduction (+=)
and where graphite is not duplicating pbbs.



Help for what? I was looking to create a simple test case. Is there still an
open bug?


Sorry, I thought, we should add this test case to be able to test
graphite without patch related to graphite-sese-to-poly.c (patch1).


Right. I think we should have a simple test case that does not trigger 
basic block duplication, which is basically triggered for reductions.


The test case:

static int __attribute__((noinline))
foo ()
{
  int i, res = 0;

  for (i = 0; i  50; i++)
{
  if (i  5)
res += 1;
}

  return res;
}

that you just proposed contains again a reduction and yields several bbs 
that cause problems.


{
  for (int c1 = 0; c1 = 49; c1 += 1) {
for (int c2 = 0; c2 = 1; c2 += 1)
  S_3(c1);
if (c1 = 4)
  S_4(c1);
S_5(c1);
  }
  S_7();
}

I proposed a test case without a reduction (possibly a little bit more 
complex):


  for i:
A[i] = ...
 
  You could do the summation/verfication outside of the scop e.g. in
  the main
  function.

 It seems that it doesn't help (at least for now).

Can you explain why you believe it is hard/impossible to generate a test 
case without reduction?



Sorry Roman. I am still confused. Are we looking for a test case or are we
still trying to understand an issue. Specifically, do we still incorrectly
transform the code even after your isl_id_for_pbb() patch?


I gives a wrong answer without patch1. The code is transformed
correctly with this patch.


OK. So we don't need to solve another bug. That is good.

Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 25/07/2014 13:20, Roman Gareev wrote:

I have no idea. Is the Gimple basic block of S_3 never set, or is it set and
deleted on the way?


I think, that it is deleted on the way. I've found out, that the
Gimple basic block will be set, if we add the following code to the
generate_isl_schedule:

bb_schedule = isl_map_set_tuple_id (bb_schedule, isl_dim_in,
isl_id_for_pbb (scop, pbb));


Is at this point the pbb of S_3 still valid? Does it point to valid data?


where isl_id_for_pbb is

static isl_id *
isl_id_for_pbb (scop_p s, poly_bb_p pbb)
{
   char name[50];
   snprintf (name, sizeof (name), S_%d, pbb_index (pbb));
   return isl_id_alloc (s-ctx, name, pbb);
}


This is surprising. You previously said the pbb pointer is still valid, 
but only the pointer that within the pbb that points to the gimple bb is 
invalid. I don't really see why setting the isl_id again (pointing to 
the very same pbb) helps in preserving the data structures in pbb.



What code does S_3 correspond to?


If I'm not mistaken, it is corresponds to:

res_18 = Cross_BB_scalar_dependence.7[0];
phi_out_of_ssa.4[0] = res_18;

I used the following code from
https://gcc.gnu.org/onlinedocs/gccint/Basic-Blocks.html to dump basic
block of the Gimple basic block:

gimple_stmt_iterator si;

for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (si))
   {
 gimple phi = gsi_stmt (si);
 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
   }
for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (si))
   {
 gimple stmt = gsi_stmt (si);
 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
   }

Could you please advise me possible functions from
graphite-sese-to-poly.c, which can delete this?


This is a hard guess. I would propose to debug this in gdb. Add a 
breakpoint at a location where pbb/isl_id are set, verify that they are 
correctly set and add a watchpoint on the pointer that is set to ZERO. 
This should make gdb stop exactly at the point where the information is 
lost.


Alternatively, you could also try to run this in valgrind.

Cheers,
Tobias

Re: [GSoC] Handling of isl_ast_op_pdiv_q and isl_ast_op_pdiv_r

[Tobias Grosser]

On 24/07/2014 12:09, Roman Gareev wrote:

Any reason you don't make 'k' a function parameter?


Yes, ISL'll generate the following code, if 'k' a function parameter:

for (int c1 = 0; c1 = 24; c1 += 1)
   S_3(c1);

However, we could use  -fno-ipa-cp to get the ISL AST, which contains
isl_ast_op_pdiv_r. What do you think about this?


I see. Just add a comment that we use globals to avoid ipa-cp.


Can you initialize res outside of the loop?


Yes, I've implemented this in the improved version.


Nice. Feel free to commit.

Tobias

Re: [GSoC] A bug related to induction variables and blocks

[Tobias Grosser]

On 24/07/2014 12:09, Roman Gareev wrote:

Is there a reason you have those global values? To my understanding they
could possibly just be function parameters?


Yes, it would be fine for this test case. I've implemented this in the
improved version.


LGTM.

Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 24/07/2014 12:09, Roman Gareev wrote:

I've attached the patch, which contains generation of Gimple code from
isl_ast_node_if.


Nice.


However, I've found out a problem. When I'm trying to generate Gimple
code from, for example, the following ISL AST:

{
   for (int c1 = 0; c1 = 49; c1 += 1) {
 S_6(c1);
 if (c1 = 48) {
   S_3(c1);
   if (c1 = 24)
 S_4(c1);
   S_5(c1);
 }
   }
   S_7();
}

the pointer to Gimple basic block of S_3's poly basic block is NULL.

Could you please advise me possible reasons of this issue?


I have no idea. Is the Gimple basic block of S_3 never set, or is it set 
and deleted on the way? What code does S_3 correspond to?


The code itself looks good. Let's get back to this after we understood 
this bug.


Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_block

[Tobias Grosser]

On 23/07/2014 11:13, Rainer Orth wrote:

Roman Gareev gareevro...@gmail.com writes:


I've attached the patch, which contains generation of Gimple code from
isl_ast_node_block. Is it fine for trunk?


2014-07-22  Roman Gareev  gareevro...@gmail.com

gcc/
* graphite-isl-ast-to-gimple.c:
(translate_isl_ast_node_block): New function.
(translate_isl_ast): Add calling of translate_isl_ast_node_block.

gcc/testsuite/gcc.dg/graphite/
* isl-ast-gen-blocks-1.c: New testcase.
* isl-ast-gen-blocks-2.c: New testcase.

The second part of the ChangeLog entry is wrong: it should go into
gcc/testsuite/ChangeLog as

* gcc.dg/graphite/isl-ast-gen-blocks-1.c: New testcase.
* gcc.dg/graphite/isl-ast-gen-blocks-2.c: New testcase.

Please fix the ChangeLog entries; no need to add another one for that
change or ask for approval: such a fix is obvious.


Thanks Rainer for catching this.

Cheers,
Tobias

Re: [GSoC] Handling of isl_ast_op_pdiv_q and isl_ast_op_pdiv_r

[Tobias Grosser]

On 23/07/2014 16:55, Roman Gareev wrote:

I've attached the patch, which adds handling of isl_ast_op_pdiv_q and
isl_ast_op_pdiv_r. It also contains a corresponding test case, which
generates the following ISL AST:

{
   for (int c1 = 0; c1  -((-k.0 + i + 4294967296) % 4294967296) +
4294967296; c1 += 1)
 S_4(c1);
   S_6();
}

Is it fine for trunk?


Some minor comments in the test case, otherwise LGTM. Feel free to 
commit after addressing those.



Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-3.c
===
--- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-3.c(revision 0)
+++ gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-3.c(working copy)
@@ -0,0 +1,27 @@
+/* { dg-do run } */
+/* { dg-options -O2 -fgraphite-identity -fgraphite-code-generator=isl } */
+
+int k = 50;


Any reason you don't make 'k' a function parameter?


+static int __attribute__((noinline))
+foo ()
+{
+  int i, res;
+  for (i = k/2, res = 0; i  k; i++)


Can you initialize res outside of the loop?

Cheers,
Tobias

Re: [GSoC] A bug related to induction variables and blocks

[Tobias Grosser]

On 23/07/2014 16:55, Roman Gareev wrote:

If we try to generate code from the following ISL AST:

{
   for (int c1 = 0; c1  k.3; c1 += 1) {
 S_21(c1);
 S_21(c1);
 S_4(c1);
 for (int c3 = 0; c3  pretmp; c3 += 1)
   S_5(c1, c3);
 S_7(c1);
 S_26(c1);
 S_8(c1);
 S_8(c1);
 S_9(c1);
 for (int c3 = 0; c3  pretmp; c3 += 1)
   S_10(c1, c3);
 S_11(c1);
 S_25(c1);
 S_13(c1);
 S_13(c1);
 S_14(c1);
 for (int c3 = 0; c3  pretmp; c3 += 1)
   S_15(c1, c3);
 S_16(c1);
 S_24(c1);
 S_18(c1);
   }
   S_19();
}

we'll get the following error:

isl_ctx.c:172: isl_ctx freed, but some objects still reference it

If I'm not mistaken, it is caused by missing of isl_id_free functions,
which should be called in the same quantity as isl_ast_expr_get_id
because of the implementation of ISL.

I've attached the patch, which may fix the problem. It also contains a
corresponding test case. Is it fine for trunk?


LGTM. Some minor comments.


ChangeLog_entry.txt


2014-07-23  Roman Gareevgareevro...@gmail.com

[gcc/]

* graphite-isl-ast-to-gimple.c:
(graphite_create_new_loop): Add calling of isl_id_free.


Add calling of isl_id_free to properly decrement reference counts.



[gcc/testsuite]

* gcc.dg/graphite/isl-ast-gen-blocks-4.c: New testcase.


patch.txt


Index: gcc/graphite-isl-ast-to-gimple.c
===
--- gcc/graphite-isl-ast-to-gimple.c(revision 212922)
+++ gcc/graphite-isl-ast-to-gimple.c(working copy)
@@ -383,6 +383,10 @@

isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for);
isl_id *id = isl_ast_expr_get_id (for_iterator);
+  std::mapisl_id *, tree::iterator res;
+  res = ip.find (id);
+  if (res != ip.end ())


What about:

if (ip.count(id))
  isl_id_free(res-first())


+isl_id_free (res-first);
ip[id] = iv;
isl_ast_expr_free (for_iterator);
return loop;

Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-4.c
===
--- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-4.c(revision 0)
+++ gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-4.c(working copy)
@@ -0,0 +1,37 @@
+/* { dg-do run } */
+/* { dg-options -O2 -fgraphite-identity -fgraphite-code-generator=isl } */
+
+int k = 4;
+int n1 = 50;
+int n2 = 50;
+int n3 = 50;


Is there a reason you have those global values? To my understanding they 
could possibly just be function parameters?



+static int __attribute__((noinline))
+foo ()
+{
+  int j, res = 0;
+  for (j = 0, res = 0; j  k; j++)
+{
+  int i;
+  for (i = 0; i  n1; i++)
+res += i;
+  for (i = 0; i  n2; i++)
+res += i;
+  for (i = 0; i  n3; i++)
+res += i;
+}
+
+  return res;
+}
+
+extern void abort ();
+
+int
+main (void)
+{
+  int res = foo ();
+  if (res != 14700)
+abort ();
+
+  return 0;
+}

Re: [GSoC] extend schedules

[Tobias Grosser]

On 22/07/2014 18:00, Roman Gareev wrote:

I've attached the patch, which adds the extension of all schedules to
the maximal number of schedule dimensions. It is necessary for the
proper work of the isl AST generator. Is it fine for trunk?

--
Cheers, Roman Gareev.


ChangeLog_entry.txt


2014-07-22  Roman Gareevgareevro...@gmail.com

gcc/
* graphite-isl-ast-to-gimple.c:
(get_max_schedule_dimensions): New function.
(extend_schedule): Likewise.
(generate_isl_schedule): Add calling of extend_schedule.


patch.txt


Index: gcc/graphite-isl-ast-to-gimple.c
===
--- gcc/graphite-isl-ast-to-gimple.c(revision 212913)
+++ gcc/graphite-isl-ast-to-gimple.c(working copy)
@@ -685,12 +685,57 @@
return isl_ast_build_from_context (context_isl);
  }

+/* Get the maximal number of schedule dimensions in the scop SCOP.  */
+
+static
+int get_max_schedule_dimensions (scop_p scop)
+{
+  int i;
+  poly_bb_p pbb;
+  int schedule_dims = 0;
+
+  FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
+{
+  int pbb_schedule_dims = isl_map_dim (pbb-transformed, isl_dim_out);
+  if (pbb_schedule_dims  schedule_dims)
+   schedule_dims = pbb_schedule_dims;
+}
+
+  return schedule_dims;
+}
+
+/* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
+
+   For schedules with different dimensionality, the isl AST generator can not
+   define an order and just randomly chooses an order.


  and will just

Otherwise, LGTM.

Please commit.

Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_block

[Tobias Grosser]

On 22/07/2014 18:00, Roman Gareev wrote:

I've attached the patch, which contains generation of Gimple code from
isl_ast_node_block. Is it fine for trunk?


LGTM.

Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_user

[Tobias Grosser]

On 21/07/2014 10:25, Roman Gareev wrote:

Maybe we should  temporary postpone this and add a FIXME that says:

“We should remove iv_map.create (loop-num + 1), if it is possible.”

What do you think about this?


Fine with me. Please post a question on gcc devel to see if someone can 
explain us the vec.h implementation.


Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_user

[Tobias Grosser]

On 21/07/2014 12:25, Roman Gareev wrote:

I've asked the community about this.

The patch below contains the FIXME.


LGTM. Feel free to commit.

Thanks,
Tobias

Re: [GSoC] A formatting issue.

[Tobias Grosser]

On July 20, 2014 1:39:08 PM CEST, Roman Gareev gareevro...@gmail.com wrote:
This patch fixes a formatting issue related to the number of
characters in the line. Is it fine for trunk?

Yes. 

That's an obvious fix. In case you feel a patch is obvious and it only touches 
graphite. Feel free to commit directly and to then send the patch for 
information to gcc-patches and to add me in cc. 

Thanks Tobias 



--
   Cheers, Roman Gareev.

Re: [GSoC] Addition of ISL AST generation to Graphite

[Tobias Grosser]

On July 20, 2014 1:29:30 PM CEST, Roman Gareev gareevro...@gmail.com wrote:
 I am not aware of any problems with isl 0.12 and would be surprised
if such
 problems exist. Are you?

I'm not aware of them, too.

 P.S: As Richard suggested, we may also want to forbid CLooG 0.17.

I've attached the patch, which adds the requirement for ClooG 0.18.1.
Is it fine for trunk?

Great. Yes, I think it's fine for trunk. 

Tobias 



--
   Cheers, Roman Gareev.

-- 
Sent from my Android device with K-9 Mail. Please excuse my brevity.

Re: [GSoC] generation of Gimple code from isl_ast_node_user

[Tobias Grosser]

One last question:

On 18/07/2014 12:28, Roman Gareev wrote:

+  iv_map.create (loop-num + 1);
+  iv_map.safe_grow_cleared (loop-num + 1);


One of these two seems redundant.

Cheers,
Tobias

Re: [GSoC] generation of Gimple loops with empty bodies

[Tobias Grosser]

On 18/07/2014 12:34, Roman Gareev wrote:

I suggest you use the largest available integer mode via
mode = mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0);
type = build_nonstandard_integer_type (GET_MODE_PRECISION (mode), [01]);

Thank you for the suggestion!


Roman, can you give this a shot?

Maybe, we could use the following code:

static int max_mode_int_precision =
   GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0));
static int graphite_expression_type_precision = 128 = max_mode_int_precision ?

128 : max_mode_int_precision;

This allows us to change the size during debugging and avoid using
unacceptable mode size. Tobias, what do you think about this?


One comment is unclear. Otherwise it is good.

If my proposed comment is OK, please update, commit and close the bug 
report.


Tobias


--
Cheers, Roman Gareev


ChangeLog_entry.txt


2014-07-08  Roman Gareevgareevro...@gmail.com

gcc/
* graphite-isl-ast-to-gimple.c:
Add using of build_nonstandard_integer_type instead of
int128_integer_type_node.


patch.txt


Index: gcc/graphite-isl-ast-to-gimple.c
===
--- gcc/graphite-isl-ast-to-gimple.c(revision 212804)
+++ gcc/graphite-isl-ast-to-gimple.c(working copy)
@@ -62,10 +62,13 @@

  static bool graphite_regenerate_error;

-/* We always use signed 128, until isl is able to give information about
-types  */
+/* We always use signed 128, until it is not accpeted or isl is able to give
+   information about types.  */


This is not understandable.

What about;

/* We always try to use signed 128 bit types, but fall back to smaller 
types in case a platform does not provide types of this sizes. In the
future we should use isl to derive the optimal type for each 
subexpression. */



-static tree *graphite_expression_size_type = int128_integer_type_node;
+static int max_mode_int_precision =
+  GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0));
+static int graphite_expression_type_precision = 128 = max_mode_int_precision ?
+   128 : max_mode_int_precision;

  /* Converts a GMP constant VAL to a tree and returns it.  */

@@ -494,7 +497,8 @@
tree cond_expr;
edge exit_edge;

-  *type = *graphite_expression_size_type;
+  *type =
+build_nonstandard_integer_type (graphite_expression_type_precision, 0);
isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
*lb = gcc_expression_from_isl_expression (*type, for_init, ip);
isl_ast_expr *upper_bound = get_upper_bound (node_for);

Re: [GSoC] Addition of ISL AST generation to Graphite

[Tobias Grosser]

On 17/07/2014 16:11, Roman Gareev wrote:

I've attached the patch, which adds the requirement for isl 0.12.
Tobias, is it important to accept only 0.12.1, 0.12.2 and forbid 0.12?


I am not aware of any problems with isl 0.12 and would be surprised if 
such problems exist. Are you?


The patch itself looks good. As it is trivial, fixing an annoying 
bootstrapping bug, and people agreed that this is the right direction, I 
propose that you commit it right ahead.


Further reviews are still welcome.

Cheers,
Tobias

P.S: As Richard suggested, we may also want to forbid CLooG 0.17.

Re: [GSoC] generation of Gimple code from isl_ast_node_user

[Tobias Grosser]

On 17/07/2014 16:08, Roman Gareev wrote:

I see. Could you use vec_safe_grow_cleared(iv_map, loop_num) instead?
This shows probably better that you zero initialize the vector.

If I am not mistaken, vec_safe_grow_cleared has the following declaration:

vec_safe_grow_cleared (vecT, A, vl_embed *v, unsigned len CXX_MEM_STAT_INFO)

Should we rewrite all the functions, which interact with iv_map?


Can you explain why all functions would need to be rewritten? I proposed
this function as an easier way to NULL initialize the vector and did not 
expect any rewrite to be necessary.


If there is no such thing, please just add a comment that your loop NULL 
initializes the vector. We can later improve this.



I've added test cases, which produce the following ISL code:

isl-ast-gen-single-loop-1.c

for (int c1 = 0; c1 = 49; c1 += 1)
   S_3(c1);

isl-ast-gen-single-loop-2.c
for (int c1 = 0; c1 = -n.0 + 69; c1 += 1)
   S_5(c1);

isl-ast-gen-single-loop-3.c
for (int c1 = 0; c1  n.0; c1 += 1)
   S_5(c1);

The second and the third one use arrays. I wanted to make them similar
to the first one, but inability to handle blocks prevented this. For
example,



OK. The tests look good.

Cheers,
Tobias

Re: [GSoC] Addition of ISL AST generation to Graphite

[Tobias Grosser]

On 16/07/2014 11:36, Richard Biener wrote:

On Tue, Jul 15, 2014 at 5:34 PM, Tobias Grosser tob...@grosser.es wrote:

On 15/07/2014 17:02, Roman Gareev wrote:


I'm seeing the error:

gcc/graphite-isl-ast-to-gimple.c:31:25: warning: isl/val_gmp.h: No such
file
or directory

when building for aarch64.

isl/val_gmp.h is included in 0.12 AFAICS so perhaps we should demand 0.12
instead of 0.11 ?



According to isl's ChangeLog, isl_val abstraction was added in version
0.12. Therefore, I think it would be right to demand on 0.12.

Tobias, what do you think about this? Is this fine for the backend,
which uses CLooG to generate Gimple code?



I think so. The latest release of CLooG (0.18.1) was released with isl
0.12.1 and is part of ftp://gcc.gnu.org/pub/gcc/infrastructure/. So
requiring isl 0.12.1 sounds reasonable.

Could you prepare such a patch?


Note that we also still accept CLooG 0.17.0.


In this case we need to update the minimal required CLooG version to 
CLooG 0.18.1, right?


 Btw, it's unfortunate that

ISL 0.13 cannot be used because it dropped some APIs we use
(it's important for testing on branches that a single cloog/isl version
can be used to bootstrap and test on active branches and trunk).


Right. I also believe this is very unfortunate. I copy Sven to let him 
now that dropping APIs too quickly regularly causes issues.


Cheers,
Tobias

Re: [GSoC] Addition of ISL AST generation to Graphite

[Tobias Grosser]

On 16/07/2014 14:03, Roman Gareev wrote:

Could you prepare such a patch?


Yes, I've started working on it.

I have a question about isl. Can we require that isl is always
compiled with GMP support?


isl 0.12.2 is always compiled with GMP support. Only for the unreleased 
isl-0.14 imath was introduced as an alternative.


Cheers,
Tobias

Re: [GSoC] Addition of ISL AST generation to Graphite

[Tobias Grosser]

On 15/07/2014 17:02, Roman Gareev wrote:

I'm seeing the error:

gcc/graphite-isl-ast-to-gimple.c:31:25: warning: isl/val_gmp.h: No such file
or directory

when building for aarch64.

isl/val_gmp.h is included in 0.12 AFAICS so perhaps we should demand 0.12
instead of 0.11 ?


According to isl's ChangeLog, isl_val abstraction was added in version
0.12. Therefore, I think it would be right to demand on 0.12.

Tobias, what do you think about this? Is this fine for the backend,
which uses CLooG to generate Gimple code?


I think so. The latest release of CLooG (0.18.1) was released with isl 
0.12.1 and is part of ftp://gcc.gnu.org/pub/gcc/infrastructure/. So 
requiring isl 0.12.1 sounds reasonable.


Could you prepare such a patch?

Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_user

[Tobias Grosser]

On 15/07/2014 16:59, Roman Gareev wrote:
 This is a pure style change which seems unrelated. Also, is the 
original

line really too long? I may have miscounted, but it seems to fit
exactly.

If I am not mistaken, lines should be limited to 80 characters,
according to conventions, which are mentioned here
https://gcc.gnu.org/wiki/CppConventions. This line contains 81
characters.


OK. Then I miscounted. Please commit this as a separate (obvious) change
and post the ChangeLog to gcc-patches.

We should keep unrelated cleanup patches out of patch reviews.


In polly we just create an iv_map from [0, max-loop-depth-within-scop], so
it contains at most as many elements as the maximal loop depth. Your map
is unnecessarily large, as it contains all loops in the function.

If we can avoid this immediately, e.g. by indexing according to the
loop-depths that would be great. On the other side, if the existing
functions require this, I propose to not touch this area, but to add a
fixme that documents this issue. We can solve it after having removed
the CLooG codegen.

If I am not mistaken, the existing function doesn't require that
iv_map contains at most as many elements as the maximal loop depth.
(If we consider chrec_apply_map (I think that it is the only function,
which works with iv_map), we'll see that it calls chrec_apply when the
expression is not NULL. In our case, we push NULL_TREEs into iv_map to
extend its size to the maximal loop depth. They aren't considered,
because tree NULL_TREE is equivalent to NULL, according to tree.h)

Maybe we could use a number of the innermost loop that contains the
basic block gbb. If I am not mistaken, outer loops considered in
build_iv_mapping have smaller numbers than it. What do you think about
this?


I just looked again into chrec_apply_map and it requires a vector that
maps from the loop id to a tree. So the existing interface requires this
kind of input. I think the interface is not nice, but don't think we
should worry about this at the moment.

Maybe add a FIXME that says:

FIXME: Instead of using a vectree that maps each loop id to a possible
chrec, we could consider using a mapint, tree that maps loop ids
to the corresponding tree expressions.


Why do you need to first push NULL_TREEs into this vec, which will be
overwritten right after?

In the current implementation, we'll get the error “internal compiler
error: in operator[], at vec.h:736”, if we try to assign a value to
iv_map via [] and remove initial pushing of NULL_TREEs. We could push
new values into iv_map in build_iv_mapping, but I am not sure if there
are cases, which require special processing (for example, NULL_TREEs
should be pushed into iv_map before the next old_loop-num. Possibly,
there are no such cases.).


I see. Could you use vec_safe_grow_cleared(iv_map, loop_num) instead?
This shows probably better that you zero initialize the vector.


It is unclear how this patches have been tested. Can you elaborate?

I've compared the result of Gimple code generation (I've attached them
to the letter) for the following examples:

int
main (int n, int *a)
{
   int i;

   for (i = n; i  100; i++)
 a[i] = i;

  return 0;
}


int
main (int 0, int *a)
{
   int i;

   for (i = n; i  100; i++)
 a[i] = i;

  return 0;
}


Also, we need to find a way to test this in gcc itself, possibly by
running test cases that already work with both the cloog and the isl ast
generator.

Maybe we could choose the strategy, which was used in
/gcc/testsuite/gcc.dg/graphite/interchange-1.c,
/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c,
/gcc/testsuite/gcc.dg/graphite/run-id-5.c?
(The result of the transformed function is compared to the assumed
value and the abort function is called in case of inequality.) What do
you think about this?


Right. You can just start by adjusting your test case, naming it
isl-ast-gen-single-loop.c

and adding the following at the beginnign of the file:

/* { dg-do run } */
/* { dg-options -O2 -fgraphite-identity } */

Some more comments:


  /* We always use signed 128, until isl is able to give information about
  types  */

-static tree *graphite_expression_size_type = int128_integer_type_node;
+static tree *graphite_expression_size_type = int128_integer_type_node ?
+int128_integer_type_node :
+long_long_integer_type_node;


Please keep unrelated changes out of the patch review.


  /* Converts a GMP constant VAL to a tree and returns it.  */

@@ -460,7 +464,8 @@
  case isl_ast_op_lt:
{
  // (iterator  ub) = (iterator = ub - 1)
-isl_val *one = isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 
1);
+isl_val *one =
+  isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);

Please keep unrelated changes out of the patch review.

Also, I think the patch now got nice and clean.

Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_user

[Tobias Grosser]

On 12/07/2014 14:18, Roman Gareev wrote:

I've attached the patch, which contains generation of Gimple code from
isl_ast_node_user.

I think that it would be better to add motivation for the following
line from the original source:

if (GBB_BB (gbb) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
   {
 isl_ast_expr_free (user_expr);
 return next_e;
   }



Do you know anything about this?


No, no idea. To my understanding the entry block should not even appear
within a scop (see build_scops, where we only start detecting scops at
the successor of the entry_block). Maybe we replace this with an assert
to get a good error message in case I have missed something.


-/* IVS_PARAMS maps ISL's scattering and parameter identifiers



+/* TREE_FROM_ISL_ID maps ISL's scattering and parameter identifiers
 to corresponding trees.  */




-typedef std::mapisl_id *, tree ivs_params;
+typedef struct ivs_params {
+  std::mapisl_id *, tree tree_from_isl_id;
+  sese region;


I think this region is actually not needed. At the place where you need
it, you have a pbb available, from which you can obtain a pointer to the
surrounding scop and from this you can obtain this region itself.


+} *ivs_params_p;




  case isl_ast_op_lt:
{
  // (iterator  ub) = (iterator = ub - 1)
-isl_val *one = isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 
1);
+isl_val *one =
+  isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);


This is a pure style change which seems unrelated. Also, is the original
line really too long? I may have miscounted, but it seems to fit
exactly.


+/* Inserts in iv_map a tuple (OLD_LOOP-num, NEW_NAME) for the
+   induction variables of the loops around GBB in SESE.  */


In polly we just create an iv_map from [0, max-loop-depth-within-scop], so
it contains at most as many elements as the maximal loop depth. Your map
is unnecessarily large, as it contains all loops in the function.

If we can avoid this immediately, e.g. by indexing according to the
loop-depths that would be great. On the other side, if the existing
functions require this, I propose to not touch this area, but to add a
fixme that documents this issue. We can solve it after having removed
the CLooG codegen.


+/* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING.  */
+
+static void
+mark_bb_with_pbb (poly_bb_p pbb, basic_block bb,
+ bb_pbb_htab_type *bb_pbb_mapping)
+{
+  bool existed;
+  poly_bb_p e = bb_pbb_mapping-get_or_insert (bb, existed);
+  if (!existed)
+e = pbb;
+}


I was just briefly looking the code to remind me what this
bb_pbb_mapping hash table is about, but could not find the reason it is
needed. Do you know why it is needed?

Is it necessary for this patch? Or did you just copy it from the
previous code generation?


+/* Translates an isl_ast_node_user to Gimple. */
+
+static edge
+translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
+edge next_e, bb_pbb_htab_type *bb_pbb_mapping,
+ivs_params_p ip)
+{
+  gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user);
+  int i, nb_loops;
+  basic_block new_bb;
+  isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node);
+  isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0);
+  gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id);
+  isl_id *name_id = isl_ast_expr_get_id (name_expr);
+  poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id);
+  gcc_assert (pbb);
+  gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
+  vectree iv_map;
+  isl_ast_expr_free (name_expr);
+  isl_id_free (name_id);
+
+  if (GBB_BB (gbb) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
+{
+  isl_ast_expr_free (user_expr);
+  return next_e;
+}
+
+  nb_loops = number_of_loops (cfun);
+  iv_map.create (nb_loops);
+  for (i = 0; i  nb_loops; i++)
+iv_map.quick_push (NULL_TREE);


Why do you need to first push NULL_TREEs into this vec, which will be
overwritten right after?


+  build_iv_mapping (iv_map, gbb, user_expr, ip);
+  isl_ast_expr_free (user_expr);
+  next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), ip-region,
+  next_e, iv_map,
+  graphite_regenerate_error);
+  iv_map.release ();
+  new_bb = next_e-src;
+  mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
+  mark_virtual_operands_for_renaming (cfun);
+  update_ssa (TODO_update_ssa);
+  return next_e;
+}
+


It is unclear how this patches have been tested. Can you elaborate?

Also, we need to find a way to test this in gcc itself, possibly by
running test cases that already work with both the cloog and the isl ast
generator.

Cheers,
Tobias

Re: [GSoC] generation of Gimple loops with empty bodies

[Tobias Grosser]

On 13/07/2014 12:34, Roman Gareev wrote:

Hi Dominique,

thank you for the message! I've attached a patch, that may fix the issue.

Please report back if it fixes the problem.


Roman, this patch is OK to commit, but please include a correct 
changelog file.


Tobias

Re: [GSoC] generation of Gimple loops with empty bodies

[Tobias Grosser]

I tried to incorporate all your comments in the attached patch.


Nice. It looks now very good to me. One final and last detail:


+/* TREE_FROM_ISL_ID maps ISL's scattering and parameter identifiers
+   to corresponding trees.  */
+
+typedef struct ivs_params {
+  std::mapisl_id *, tree tree_from_isl_id;
+} *ivs_params_p;

The struct now contains only a single element such that there seems to 
be no need for it anymore. Should we remove it? (We could still use a 
typedef if you believe the datatype is too long).


Cheers,
Tobias

Re: [GSoC] generation of Gimple loops with empty bodies

[Tobias Grosser]

On 11/07/2014 13:11, Roman Gareev wrote:

The struct now contains only a single element such that there seems to be no
need for it anymore. Should we remove it? (We could still use a typedef if
you believe the datatype is too long).


I don't mind removing it. However I think that we should choose the
way of transferring of sese region, which is used for translation of
an isl_ast_node_user to Gimple code. Should we transfer it separately
or restore ivs_params later? What do you think?


Sorry, I currently don't see why sese region is needed later. In case it
is, we may keep it, but this would require to pull more code in the 
review. I personally would just remove it to finish this review.


Feel free to commit after applying this change.

Cheers,
Tobias

Re: [GSoC] generation of Gimple loops with empty bodies

[Tobias Grosser]

On 11/07/2014 15:41, Roman Gareev wrote:

I've attached an improved version of the patch and the ChangeLog
entry. Are they fine for trunk?


LGTM.

Thank you!
Tobias