OSDN Git Service

2009-02-04 Tobias Grosser <grosser@fim.uni-passau.de>
[pf3gnuchains/gcc-fork.git] / gcc / graphite.c
1 /* Gimple Represented as Polyhedra.
2    Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
3    Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 /* This pass converts GIMPLE to GRAPHITE, performs some loop
22    transformations and then converts the resulting representation back
23    to GIMPLE.  
24
25    An early description of this pass can be found in the GCC Summit'06
26    paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC".
27    The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to
28    the related work.  
29
30    One important document to read is CLooG's internal manual:
31    http://repo.or.cz/w/cloog-ppl.git?a=blob_plain;f=doc/cloog.texi;hb=HEAD
32    that describes the data structure of loops used in this file, and
33    the functions that are used for transforming the code.  */
34
35 #include "config.h"
36 #include "system.h"
37 #include "coretypes.h"
38 #include "tm.h"
39 #include "ggc.h"
40 #include "tree.h"
41 #include "rtl.h"
42 #include "basic-block.h"
43 #include "diagnostic.h"
44 #include "tree-flow.h"
45 #include "toplev.h"
46 #include "tree-dump.h"
47 #include "timevar.h"
48 #include "cfgloop.h"
49 #include "tree-chrec.h"
50 #include "tree-data-ref.h"
51 #include "tree-scalar-evolution.h"
52 #include "tree-pass.h"
53 #include "domwalk.h"
54 #include "value-prof.h"
55 #include "pointer-set.h"
56 #include "gimple.h"
57
58 #ifdef HAVE_cloog
59 #include "cloog/cloog.h"
60 #include "graphite.h"
61
62 static VEC (scop_p, heap) *current_scops;
63
64 /* Converts a GMP constant V to a tree and returns it.  */
65
66 static tree
67 gmp_cst_to_tree (tree type, Value v)
68 {
69   return build_int_cst (type, value_get_si (v));
70 }
71
72 /* Returns true when BB is in REGION.  */
73
74 static bool
75 bb_in_sese_p (basic_block bb, sese region)
76 {
77   return pointer_set_contains (SESE_REGION_BBS (region), bb);
78 }
79
80 /* Returns true when LOOP is in the SESE region R.  */
81
82 static inline bool 
83 loop_in_sese_p (struct loop *loop, sese r)
84 {
85   return (bb_in_sese_p (loop->header, r)
86           && bb_in_sese_p (loop->latch, r));
87 }
88
89 /* For a USE in BB, if BB is outside REGION, mark the USE in the
90    SESE_LIVEIN and SESE_LIVEOUT sets.  */
91
92 static void
93 sese_build_livein_liveouts_use (sese region, basic_block bb, tree use)
94 {
95   unsigned ver;
96   basic_block def_bb;
97
98   if (TREE_CODE (use) != SSA_NAME)
99     return;
100
101   ver = SSA_NAME_VERSION (use);
102   def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
103   if (!def_bb
104       || !bb_in_sese_p (def_bb, region)
105       || bb_in_sese_p (bb, region))
106     return;
107
108   if (!SESE_LIVEIN_VER (region, ver))
109     SESE_LIVEIN_VER (region, ver) = BITMAP_ALLOC (NULL);
110
111   bitmap_set_bit (SESE_LIVEIN_VER (region, ver), bb->index);
112   bitmap_set_bit (SESE_LIVEOUT (region), ver);
113 }
114
115 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
116    used in BB that is outside of the REGION.  */
117
118 static void
119 sese_build_livein_liveouts_bb (sese region, basic_block bb)
120 {
121   gimple_stmt_iterator bsi;
122   edge e;
123   edge_iterator ei;
124   ssa_op_iter iter;
125   tree var;
126
127   FOR_EACH_EDGE (e, ei, bb->succs)
128     for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
129       sese_build_livein_liveouts_use (region, bb,
130                                       PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
131
132   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
133     FOR_EACH_SSA_TREE_OPERAND (var, gsi_stmt (bsi), iter, SSA_OP_ALL_USES)
134       sese_build_livein_liveouts_use (region, bb, var);
135 }
136
137 /* Build the SESE_LIVEIN and SESE_LIVEOUT for REGION.  */
138
139 void
140 sese_build_livein_liveouts (sese region)
141 {
142   basic_block bb;
143
144   SESE_LIVEOUT (region) = BITMAP_ALLOC (NULL);
145   SESE_NUM_VER (region) = num_ssa_names;
146   SESE_LIVEIN (region) = XCNEWVEC (bitmap, SESE_NUM_VER (region));
147
148   FOR_EACH_BB (bb)
149     sese_build_livein_liveouts_bb (region, bb);
150 }
151
152 /* Register basic blocks belonging to a region in a pointer set.  */
153
154 static void
155 register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region)
156 {
157   edge_iterator ei;
158   edge e;
159   basic_block bb = entry_bb;
160
161   FOR_EACH_EDGE (e, ei, bb->succs)
162     {
163       if (!pointer_set_contains (SESE_REGION_BBS (region), e->dest) &&
164           e->dest->index != exit_bb->index)
165         {       
166           pointer_set_insert (SESE_REGION_BBS (region), e->dest);
167           register_bb_in_sese (e->dest, exit_bb, region);
168         }
169     }
170 }
171
172 /* Builds a new SESE region from edges ENTRY and EXIT.  */
173
174 sese
175 new_sese (edge entry, edge exit)
176 {
177   sese res = XNEW (struct sese);
178
179   SESE_ENTRY (res) = entry;
180   SESE_EXIT (res) = exit;
181   SESE_REGION_BBS (res) = pointer_set_create ();
182   register_bb_in_sese (entry->dest, exit->dest, res);
183
184   SESE_LIVEOUT (res) = NULL;
185   SESE_NUM_VER (res) = 0;
186   SESE_LIVEIN (res) = NULL;
187
188   return res;
189 }
190
191 /* Deletes REGION.  */
192
193 void
194 free_sese (sese region)
195 {
196   int i;
197
198   for (i = 0; i < SESE_NUM_VER (region); i++)
199     BITMAP_FREE (SESE_LIVEIN_VER (region, i));
200
201   if (SESE_LIVEIN (region))
202     free (SESE_LIVEIN (region));
203
204   if (SESE_LIVEOUT (region))
205     BITMAP_FREE (SESE_LIVEOUT (region));
206
207   pointer_set_destroy (SESE_REGION_BBS (region));
208   XDELETE (region);
209 }
210
211 \f
212
213 /* Debug the list of old induction variables for this SCOP.  */
214
215 void
216 debug_oldivs (scop_p scop)
217 {
218   int i;
219   name_tree oldiv;
220
221   fprintf (stderr, "Old IVs:");
222
223   for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, oldiv); i++)
224     {
225       fprintf (stderr, "(");
226       print_generic_expr (stderr, oldiv->t, 0);
227       fprintf (stderr, ", %s, %d)\n", oldiv->name, oldiv->loop->num);
228     }
229   fprintf (stderr, "\n");
230 }
231
232 /* Debug the loops around basic block GB.  */
233
234 void
235 debug_loop_vec (graphite_bb_p gb)
236 {
237   int i;
238   loop_p loop;
239
240   fprintf (stderr, "Loop Vec:");
241
242   for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
243     fprintf (stderr, "%d: %d, ", i, loop ? loop->num : -1);
244
245   fprintf (stderr, "\n");
246 }
247
248 /* Returns true if stack ENTRY is a constant.  */
249
250 static bool
251 iv_stack_entry_is_constant (iv_stack_entry *entry)
252 {
253   return entry->kind == iv_stack_entry_const;
254 }
255
256 /* Returns true if stack ENTRY is an induction variable.  */
257
258 static bool
259 iv_stack_entry_is_iv (iv_stack_entry *entry)
260 {
261   return entry->kind == iv_stack_entry_iv;
262 }
263
264 /* Push (IV, NAME) on STACK.  */
265
266 static void 
267 loop_iv_stack_push_iv (loop_iv_stack stack, tree iv, const char *name)
268 {
269   iv_stack_entry *entry = XNEW (iv_stack_entry);
270   name_tree named_iv = XNEW (struct name_tree);
271
272   named_iv->t = iv;
273   named_iv->name = name;
274
275   entry->kind = iv_stack_entry_iv;
276   entry->data.iv = named_iv;
277
278   VEC_safe_push (iv_stack_entry_p, heap, *stack, entry);
279 }
280
281 /* Inserts a CONSTANT in STACK at INDEX.  */
282
283 static void
284 loop_iv_stack_insert_constant (loop_iv_stack stack, int index,
285                                tree constant)
286 {
287   iv_stack_entry *entry = XNEW (iv_stack_entry);
288   
289   entry->kind = iv_stack_entry_const;
290   entry->data.constant = constant;
291
292   VEC_safe_insert (iv_stack_entry_p, heap, *stack, index, entry);
293 }
294
295 /* Pops and frees an element out of STACK.  */
296
297 static void
298 loop_iv_stack_pop (loop_iv_stack stack)
299 {
300   iv_stack_entry_p entry = VEC_pop (iv_stack_entry_p, *stack);
301
302   free (entry->data.iv);
303   free (entry);
304 }
305
306 /* Get the IV at INDEX in STACK.  */
307
308 static tree
309 loop_iv_stack_get_iv (loop_iv_stack stack, int index)
310 {
311   iv_stack_entry_p entry = VEC_index (iv_stack_entry_p, *stack, index);
312   iv_stack_entry_data data = entry->data;
313
314   return iv_stack_entry_is_iv (entry) ? data.iv->t : data.constant;
315 }
316
317 /* Get the IV from its NAME in STACK.  */
318
319 static tree
320 loop_iv_stack_get_iv_from_name (loop_iv_stack stack, const char* name)
321 {
322   int i;
323   iv_stack_entry_p entry;
324
325   for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
326     {
327       name_tree iv = entry->data.iv;
328       if (!strcmp (name, iv->name))
329         return iv->t;
330     }
331
332   return NULL;
333 }
334
335 /* Prints on stderr the contents of STACK.  */
336
337 void
338 debug_loop_iv_stack (loop_iv_stack stack)
339 {
340   int i;
341   iv_stack_entry_p entry;
342   bool first = true;
343
344   fprintf (stderr, "(");
345
346   for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
347     {
348       if (first) 
349         first = false;
350       else
351         fprintf (stderr, " ");
352
353       if (iv_stack_entry_is_iv (entry))
354         {
355           name_tree iv = entry->data.iv;
356           fprintf (stderr, "%s:", iv->name);
357           print_generic_expr (stderr, iv->t, 0);
358         }
359       else 
360         {
361           tree constant = entry->data.constant;
362           print_generic_expr (stderr, constant, 0);
363           fprintf (stderr, ":");
364           print_generic_expr (stderr, constant, 0);
365         }
366     }
367
368   fprintf (stderr, ")\n");
369 }
370
371 /* Frees STACK.  */
372
373 static void
374 free_loop_iv_stack (loop_iv_stack stack)
375 {
376   int i;
377   iv_stack_entry_p entry;
378
379   for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
380     {
381       free (entry->data.iv);
382       free (entry);
383     }
384
385   VEC_free (iv_stack_entry_p, heap, *stack);
386 }
387
388 \f
389
390 /* Structure containing the mapping between the CLooG's induction
391    variable and the type of the old induction variable.  */
392 typedef struct ivtype_map_elt
393 {
394   tree type;
395   const char *cloog_iv;
396 } *ivtype_map_elt;
397
398 /* Print to stderr the element ELT.  */
399
400 static void
401 debug_ivtype_elt (ivtype_map_elt elt)
402 {
403   fprintf (stderr, "(%s, ", elt->cloog_iv);
404   print_generic_expr (stderr, elt->type, 0);
405   fprintf (stderr, ")\n");
406 }
407
408 /* Helper function for debug_ivtype_map.  */
409
410 static int
411 debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
412 {
413   struct ivtype_map_elt *entry = (struct ivtype_map_elt *) *slot;
414   debug_ivtype_elt (entry);
415   return 1;
416 }
417
418 /* Print to stderr all the elements of MAP.  */
419
420 void
421 debug_ivtype_map (htab_t map)
422 {
423   htab_traverse (map, debug_ivtype_map_1, NULL);
424 }
425
426 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
427
428 static inline ivtype_map_elt
429 new_ivtype_map_elt (const char *cloog_iv, tree type)
430 {
431   ivtype_map_elt res;
432   
433   res = XNEW (struct ivtype_map_elt);
434   res->cloog_iv = cloog_iv;
435   res->type = type;
436
437   return res;
438 }
439
440 /* Computes a hash function for database element ELT.  */
441
442 static hashval_t
443 ivtype_map_elt_info (const void *elt)
444 {
445   return htab_hash_pointer (((const struct ivtype_map_elt *) elt)->cloog_iv);
446 }
447
448 /* Compares database elements E1 and E2.  */
449
450 static int
451 eq_ivtype_map_elts (const void *e1, const void *e2)
452 {
453   const struct ivtype_map_elt *elt1 = (const struct ivtype_map_elt *) e1;
454   const struct ivtype_map_elt *elt2 = (const struct ivtype_map_elt *) e2;
455
456   return (elt1->cloog_iv == elt2->cloog_iv);
457 }
458
459 \f
460
461 /* Given a CLOOG_IV, returns the type that it should have in GCC land.
462    If the information is not available, i.e. in the case one of the
463    transforms created the loop, just return integer_type_node.  */
464
465 static tree
466 gcc_type_for_cloog_iv (const char *cloog_iv, graphite_bb_p gbb)
467 {
468   struct ivtype_map_elt tmp;
469   PTR *slot;
470
471   tmp.cloog_iv = cloog_iv;
472   slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT);
473
474   if (slot && *slot)
475     return ((ivtype_map_elt) *slot)->type;
476
477   return integer_type_node;
478 }
479
480 /* Inserts constants derived from the USER_STMT argument list into the
481    STACK.  This is needed to map old ivs to constants when loops have
482    been eliminated.  */
483
484 static void 
485 loop_iv_stack_patch_for_consts (loop_iv_stack stack,
486                                 struct clast_user_stmt *user_stmt)
487 {
488   struct clast_stmt *t;
489   int index = 0;
490   CloogStatement *cs = user_stmt->statement;
491   graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
492
493   for (t = user_stmt->substitutions; t; t = t->next) 
494     {
495       struct clast_expr *expr = (struct clast_expr *) 
496         ((struct clast_assignment *)t)->RHS;
497       struct clast_term *term = (struct clast_term *) expr;
498
499       /* FIXME: What should be done with expr_bin, expr_red?  */
500       if (expr->type == expr_term
501           && !term->var)
502         {
503           loop_p loop = gbb_loop_at_index (gbb, index);
504           tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop);
505           tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
506           tree value = gmp_cst_to_tree (type, term->val);
507           loop_iv_stack_insert_constant (stack, index, value);
508         }
509       index = index + 1;
510     }
511 }
512
513 /* Removes all constants in the iv STACK.  */
514
515 static void
516 loop_iv_stack_remove_constants (loop_iv_stack stack)
517 {
518   int i;
519   iv_stack_entry *entry;
520   
521   for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry);)
522     {
523       if (iv_stack_entry_is_constant (entry))
524         {
525           free (VEC_index (iv_stack_entry_p, *stack, i));
526           VEC_ordered_remove (iv_stack_entry_p, *stack, i);
527         }
528       else
529         i++;
530     }
531 }
532
533 /* Returns a new loop_to_cloog_loop_str structure.  */
534
535 static inline struct loop_to_cloog_loop_str *
536 new_loop_to_cloog_loop_str (int loop_num,
537                             int loop_position,
538                             CloogLoop *cloog_loop)
539 {
540   struct loop_to_cloog_loop_str *result;
541
542   result = XNEW (struct loop_to_cloog_loop_str);
543   result->loop_num = loop_num;
544   result->cloog_loop = cloog_loop;
545   result->loop_position = loop_position;
546
547   return result;
548 }
549
550 /* Hash function for SCOP_LOOP2CLOOG_LOOP hash table.  */
551
552 static hashval_t
553 hash_loop_to_cloog_loop (const void *elt)
554 {
555   return ((const struct loop_to_cloog_loop_str *) elt)->loop_num;
556 }
557
558 /* Equality function for SCOP_LOOP2CLOOG_LOOP hash table.  */
559
560 static int
561 eq_loop_to_cloog_loop (const void *el1, const void *el2)
562 {
563   const struct loop_to_cloog_loop_str *elt1, *elt2;
564
565   elt1 = (const struct loop_to_cloog_loop_str *) el1;
566   elt2 = (const struct loop_to_cloog_loop_str *) el2;
567   return elt1->loop_num == elt2->loop_num;
568 }
569
570 /* Compares two graphite bbs and returns an integer less than, equal to, or
571    greater than zero if the first argument is considered to be respectively
572    less than, equal to, or greater than the second. 
573    We compare using the lexicographic order of the static schedules.  */
574
575 static int 
576 gbb_compare (const void *p_1, const void *p_2)
577 {
578   const struct graphite_bb *const gbb_1
579     = *(const struct graphite_bb *const*) p_1;
580   const struct graphite_bb *const gbb_2
581     = *(const struct graphite_bb *const*) p_2;
582
583   return lambda_vector_compare (GBB_STATIC_SCHEDULE (gbb_1),
584                                 gbb_nb_loops (gbb_1) + 1,
585                                 GBB_STATIC_SCHEDULE (gbb_2),
586                                 gbb_nb_loops (gbb_2) + 1);
587 }
588
589 /* Sort graphite bbs in SCOP.  */
590
591 static void
592 graphite_sort_gbbs (scop_p scop)
593 {
594   VEC (graphite_bb_p, heap) *bbs = SCOP_BBS (scop);
595
596   qsort (VEC_address (graphite_bb_p, bbs),
597          VEC_length (graphite_bb_p, bbs),
598          sizeof (graphite_bb_p), gbb_compare);
599 }
600
601 /* Dump conditions of a graphite basic block GBB on FILE.  */
602
603 static void
604 dump_gbb_conditions (FILE *file, graphite_bb_p gbb)
605 {
606   int i;
607   gimple stmt;
608   VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb);
609   
610   if (VEC_empty (gimple, conditions))
611     return;
612
613   fprintf (file, "\tbb %d\t: cond = {", GBB_BB (gbb)->index);
614
615   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
616     print_gimple_stmt (file, stmt, 0, 0);
617
618   fprintf (file, "}\n");
619 }
620
621 /* Converts the graphite scheduling function into a cloog scattering
622    matrix.  This scattering matrix is used to limit the possible cloog
623    output to valid programs in respect to the scheduling function. 
624
625    SCATTERING_DIMENSIONS specifies the dimensionality of the scattering
626    matrix. CLooG 0.14.0 and previous versions require, that all scattering
627    functions of one CloogProgram have the same dimensionality, therefore we
628    allow to specify it. (Should be removed in future versions)  */
629
630 static CloogMatrix *
631 schedule_to_scattering (graphite_bb_p gb, int scattering_dimensions) 
632 {
633   int i;
634   scop_p scop = GBB_SCOP (gb);
635
636   int nb_iterators = gbb_nb_loops (gb);
637
638   /* The cloog scattering matrix consists of these colums:
639      1                        col  = Eq/Inq,
640      scattering_dimensions    cols = Scattering dimensions,
641      nb_iterators             cols = bb's iterators,
642      scop_nb_params        cols = Parameters,
643      1                        col  = Constant 1.
644
645      Example:
646
647      scattering_dimensions = 5
648      max_nb_iterators = 2
649      nb_iterators = 1 
650      scop_nb_params = 2
651
652      Schedule:
653      ? i
654      4 5
655
656      Scattering Matrix:
657      s1  s2  s3  s4  s5  i   p1  p2  1 
658      1   0   0   0   0   0   0   0  -4  = 0
659      0   1   0   0   0  -1   0   0   0  = 0
660      0   0   1   0   0   0   0   0  -5  = 0  */
661   int nb_params = scop_nb_params (scop);
662   int nb_cols = 1 + scattering_dimensions + nb_iterators + nb_params + 1;
663   int col_const = nb_cols - 1; 
664   int col_iter_offset = 1 + scattering_dimensions;
665
666   CloogMatrix *scat = cloog_matrix_alloc (scattering_dimensions, nb_cols);
667
668   gcc_assert (scattering_dimensions >= nb_iterators * 2 + 1);
669
670   /* Initialize the identity matrix.  */
671   for (i = 0; i < scattering_dimensions; i++)
672     value_set_si (scat->p[i][i + 1], 1);
673
674   /* Textual order outside the first loop */
675   value_set_si (scat->p[0][col_const], -GBB_STATIC_SCHEDULE (gb)[0]);
676
677   /* For all surrounding loops.  */
678   for (i = 0;  i < nb_iterators; i++)
679     {
680       int schedule = GBB_STATIC_SCHEDULE (gb)[i + 1];
681
682       /* Iterations of this loop.  */
683       value_set_si (scat->p[2 * i + 1][col_iter_offset + i], -1);
684
685       /* Textual order inside this loop.  */
686       value_set_si (scat->p[2 * i + 2][col_const], -schedule);
687     }
688
689   return scat; 
690 }
691
692 /* Print the schedules of GB to FILE with INDENT white spaces before.
693    VERBOSITY determines how verbose the code pretty printers are.  */
694
695 void
696 print_graphite_bb (FILE *file, graphite_bb_p gb, int indent, int verbosity)
697 {
698   CloogMatrix *scattering;
699   int i;
700   loop_p loop;
701   fprintf (file, "\nGBB (\n");
702
703   print_loops_bb (file, GBB_BB (gb), indent+2, verbosity);
704
705   if (GBB_DOMAIN (gb))
706     {
707       fprintf (file, "       (domain: \n");
708       cloog_matrix_print (file, GBB_DOMAIN (gb));
709       fprintf (file, "       )\n");
710     }
711
712   if (GBB_STATIC_SCHEDULE (gb))
713     {
714       fprintf (file, "       (static schedule: ");
715       print_lambda_vector (file, GBB_STATIC_SCHEDULE (gb),
716                            gbb_nb_loops (gb) + 1);
717       fprintf (file, "       )\n");
718     }
719
720   if (GBB_LOOPS (gb))
721     {
722       fprintf (file, "       (contained loops: \n");
723       for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
724         if (loop == NULL)
725           fprintf (file, "       iterator %d   =>  NULL \n", i); 
726         else
727           fprintf (file, "       iterator %d   =>  loop %d \n", i,
728                    loop->num);
729       fprintf (file, "       )\n");
730     }
731
732   if (GBB_DATA_REFS (gb))
733     dump_data_references (file, GBB_DATA_REFS (gb));
734
735   if (GBB_CONDITIONS (gb))
736     {
737       fprintf (file, "       (conditions: \n");
738       dump_gbb_conditions (file, gb);
739       fprintf (file, "       )\n");
740     }
741
742   if (GBB_SCOP (gb)
743       && GBB_STATIC_SCHEDULE (gb))
744     {
745       fprintf (file, "       (scattering: \n");
746       scattering = schedule_to_scattering (gb, 2 * gbb_nb_loops (gb) + 1);
747       cloog_matrix_print (file, scattering);
748       cloog_matrix_free (scattering);
749       fprintf (file, "       )\n");
750     }
751
752   fprintf (file, ")\n");
753 }
754
755 /* Print to STDERR the schedules of GB with VERBOSITY level.  */
756
757 void
758 debug_gbb (graphite_bb_p gb, int verbosity)
759 {
760   print_graphite_bb (stderr, gb, 0, verbosity);
761 }
762
763
764 /* Print SCOP to FILE.  VERBOSITY determines how verbose the pretty
765    printers are.  */
766
767 static void
768 print_scop (FILE *file, scop_p scop, int verbosity)
769 {
770   if (scop == NULL)
771     return;
772
773   fprintf (file, "\nSCoP_%d_%d (\n",
774            SCOP_ENTRY (scop)->index, SCOP_EXIT (scop)->index);
775
776   fprintf (file, "       (cloog: \n");
777   cloog_program_print (file, SCOP_PROG (scop));
778   fprintf (file, "       )\n");
779
780   if (SCOP_BBS (scop))
781     {
782       graphite_bb_p gb;
783       int i;
784
785       for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
786         print_graphite_bb (file, gb, 0, verbosity);
787     }
788
789   fprintf (file, ")\n");
790 }
791
792 /* Print all the SCOPs to FILE.  VERBOSITY determines how verbose the
793    code pretty printers are.  */
794
795 static void
796 print_scops (FILE *file, int verbosity)
797 {
798   int i;
799   scop_p scop;
800
801   for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
802     print_scop (file, scop, verbosity);
803 }
804
805 /* Debug SCOP.  VERBOSITY determines how verbose the code pretty
806    printers are. */
807
808 void
809 debug_scop (scop_p scop, int verbosity)
810 {
811   print_scop (stderr, scop, verbosity);
812 }
813
814 /* Debug all SCOPs from CURRENT_SCOPS.  VERBOSITY determines how
815    verbose the code pretty printers are.  */
816
817 void 
818 debug_scops (int verbosity)
819 {
820   print_scops (stderr, verbosity);
821 }
822
823 /* Pretty print to FILE the SCOP in DOT format.  */
824
825 static void 
826 dot_scop_1 (FILE *file, scop_p scop)
827 {
828   edge e;
829   edge_iterator ei;
830   basic_block bb;
831   basic_block entry = SCOP_ENTRY (scop);
832   basic_block exit = SCOP_EXIT (scop);
833     
834   fprintf (file, "digraph SCoP_%d_%d {\n", entry->index,
835            exit->index);
836
837   FOR_ALL_BB (bb)
838     {
839       if (bb == entry)
840         fprintf (file, "%d [shape=triangle];\n", bb->index);
841
842       if (bb == exit)
843         fprintf (file, "%d [shape=box];\n", bb->index);
844
845       if (bb_in_sese_p (bb, SCOP_REGION (scop))) 
846         fprintf (file, "%d [color=red];\n", bb->index);
847
848       FOR_EACH_EDGE (e, ei, bb->succs)
849         fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
850     }
851
852   fputs ("}\n\n", file);
853 }
854
855 /* Display SCOP using dotty.  */
856
857 void
858 dot_scop (scop_p scop)
859 {
860   dot_scop_1 (stderr, scop);
861 }
862
863 /* Pretty print all SCoPs in DOT format and mark them with different colors.
864    If there are not enough colors, paint later SCoPs gray.
865    Special nodes:
866    - "*" after the node number: entry of a SCoP,
867    - "#" after the node number: exit of a SCoP,
868    - "()" entry or exit not part of SCoP.  */
869
870 static void
871 dot_all_scops_1 (FILE *file)
872 {
873   basic_block bb;
874   edge e;
875   edge_iterator ei;
876   scop_p scop;
877   const char* color;
878   int i;
879
880   /* Disable debugging while printing graph.  */
881   int tmp_dump_flags = dump_flags;
882   dump_flags = 0;
883
884   fprintf (file, "digraph all {\n");
885
886   FOR_ALL_BB (bb)
887     {
888       int part_of_scop = false;
889
890       /* Use HTML for every bb label.  So we are able to print bbs
891          which are part of two different SCoPs, with two different
892          background colors.  */
893       fprintf (file, "%d [label=<\n  <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
894                      bb->index);
895       fprintf (file, "CELLSPACING=\"0\">\n");
896
897       /* Select color for SCoP.  */
898       for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
899         if (bb_in_sese_p (bb, SCOP_REGION (scop))
900             || (SCOP_EXIT (scop) == bb)
901             || (SCOP_ENTRY (scop) == bb))
902           {
903             switch (i % 17)
904               {
905               case 0: /* red */
906                 color = "#e41a1c";
907                 break;
908               case 1: /* blue */
909                 color = "#377eb8";
910                 break;
911               case 2: /* green */
912                 color = "#4daf4a";
913                 break;
914               case 3: /* purple */
915                 color = "#984ea3";
916                 break;
917               case 4: /* orange */
918                 color = "#ff7f00";
919                 break;
920               case 5: /* yellow */
921                 color = "#ffff33";
922                 break;
923               case 6: /* brown */
924                 color = "#a65628";
925                 break;
926               case 7: /* rose */
927                 color = "#f781bf";
928                 break;
929               case 8:
930                 color = "#8dd3c7";
931                 break;
932               case 9:
933                 color = "#ffffb3";
934                 break;
935               case 10:
936                 color = "#bebada";
937                 break;
938               case 11:
939                 color = "#fb8072";
940                 break;
941               case 12:
942                 color = "#80b1d3";
943                 break;
944               case 13:
945                 color = "#fdb462";
946                 break;
947               case 14:
948                 color = "#b3de69";
949                 break;
950               case 15:
951                 color = "#fccde5";
952                 break;
953               case 16:
954                 color = "#bc80bd";
955                 break;
956               default: /* gray */
957                 color = "#999999";
958               }
959
960             fprintf (file, "    <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
961         
962             if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
963               fprintf (file, " ("); 
964
965             if (bb == SCOP_ENTRY (scop)
966                 && bb == SCOP_EXIT (scop))
967               fprintf (file, " %d*# ", bb->index);
968             else if (bb == SCOP_ENTRY (scop))
969               fprintf (file, " %d* ", bb->index);
970             else if (bb == SCOP_EXIT (scop))
971               fprintf (file, " %d# ", bb->index);
972             else
973               fprintf (file, " %d ", bb->index);
974
975             if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
976               fprintf (file, ")");
977
978             fprintf (file, "</TD></TR>\n");
979             part_of_scop  = true;
980           }
981
982       if (!part_of_scop)
983         {
984           fprintf (file, "    <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
985           fprintf (file, " %d </TD></TR>\n", bb->index);
986         }
987
988       fprintf (file, "  </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
989     }
990
991   FOR_ALL_BB (bb)
992     {
993       FOR_EACH_EDGE (e, ei, bb->succs)
994               fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
995     }
996
997   fputs ("}\n\n", file);
998
999   /* Enable debugging again.  */
1000   dump_flags = tmp_dump_flags;
1001 }
1002
1003 /* Display all SCoPs using dotty.  */
1004
1005 void
1006 dot_all_scops (void)
1007 {
1008   /* When debugging, enable the following code.  This cannot be used
1009      in production compilers because it calls "system".  */
1010 #if 0
1011   FILE *stream = fopen ("/tmp/allscops.dot", "w");
1012   gcc_assert (stream);
1013
1014   dot_all_scops_1 (stream);
1015   fclose (stream);
1016
1017   system ("dotty /tmp/allscops.dot");
1018 #else
1019   dot_all_scops_1 (stderr);
1020 #endif
1021 }
1022
1023 /* Returns the outermost loop in SCOP that contains BB.  */
1024
1025 static struct loop *
1026 outermost_loop_in_scop (scop_p scop, basic_block bb)
1027 {
1028   struct loop *nest;
1029
1030   nest = bb->loop_father;
1031   while (loop_outer (nest)
1032          && loop_in_sese_p (loop_outer (nest), SCOP_REGION (scop)))
1033     nest = loop_outer (nest);
1034
1035   return nest;
1036 }
1037
1038 /* Returns the block preceding the entry of SCOP.  */
1039
1040 static basic_block
1041 block_before_scop (scop_p scop)
1042 {
1043   return SESE_ENTRY (SCOP_REGION (scop))->src;
1044 }
1045
1046 /* Return true when EXPR is an affine function in LOOP with parameters
1047    instantiated relative to SCOP_ENTRY.  */
1048
1049 static bool
1050 loop_affine_expr (basic_block scop_entry, struct loop *loop, tree expr)
1051 {
1052   int n = loop->num;
1053   tree scev = analyze_scalar_evolution (loop, expr);
1054
1055   scev = instantiate_scev (scop_entry, loop, scev);
1056
1057   return (evolution_function_is_invariant_p (scev, n)
1058           || evolution_function_is_affine_multivariate_p (scev, n));
1059 }
1060
1061 /* Return false if the tree_code of the operand OP or any of its operands
1062    is component_ref.  */
1063
1064 static bool
1065 exclude_component_ref (tree op) 
1066 {
1067   int i;
1068   int len;
1069
1070   if (op)
1071     {
1072       if (TREE_CODE (op) == COMPONENT_REF)
1073         return false;
1074       else
1075         {
1076           len = TREE_OPERAND_LENGTH (op);         
1077           for (i = 0; i < len; ++i)
1078             {
1079               if (!exclude_component_ref (TREE_OPERAND (op, i)))
1080                 return false;
1081             }
1082         }
1083     }
1084
1085   return true;
1086 }
1087
1088 /* Return true if the operand OP is simple.  */
1089
1090 static bool
1091 is_simple_operand (loop_p loop, gimple stmt, tree op) 
1092 {
1093   /* It is not a simple operand when it is a declaration,  */
1094   if (DECL_P (op)
1095       /* or a structure,  */
1096       || AGGREGATE_TYPE_P (TREE_TYPE (op))
1097       /* or a memory access that cannot be analyzed by the data
1098          reference analysis.  */
1099       || ((handled_component_p (op) || INDIRECT_REF_P (op))
1100           && !stmt_simple_memref_p (loop, stmt, op)))
1101     return false;
1102
1103   return exclude_component_ref (op);
1104 }
1105
1106 /* Return true only when STMT is simple enough for being handled by
1107    Graphite.  This depends on SCOP_ENTRY, as the parametetrs are
1108    initialized relatively to this basic block.  */
1109
1110 static bool
1111 stmt_simple_for_scop_p (basic_block scop_entry, gimple stmt)
1112 {
1113   basic_block bb = gimple_bb (stmt);
1114   struct loop *loop = bb->loop_father;
1115
1116   /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1117      Calls have side-effects, except those to const or pure
1118      functions.  */
1119   if (gimple_has_volatile_ops (stmt)
1120       || (gimple_code (stmt) == GIMPLE_CALL
1121           && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
1122       || (gimple_code (stmt) == GIMPLE_ASM))
1123     return false;
1124
1125   switch (gimple_code (stmt))
1126     {
1127     case GIMPLE_RETURN:
1128     case GIMPLE_LABEL:
1129       return true;
1130
1131     case GIMPLE_COND:
1132       {
1133         tree op;
1134         ssa_op_iter op_iter;
1135         enum tree_code code = gimple_cond_code (stmt);
1136
1137         /* We can only handle this kind of conditional expressions.  
1138            For inequalities like "if (i != 3 * k)" we need unions of
1139            polyhedrons.  Expressions like  "if (a)" or "if (a == 15)" need
1140            them for the else branch.  */
1141         if (!(code == LT_EXPR
1142               || code == GT_EXPR
1143               || code == LE_EXPR
1144               || code == GE_EXPR))
1145           return false;
1146
1147         if (!scop_entry)
1148           return false;
1149
1150         FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)
1151           if (!loop_affine_expr (scop_entry, loop, op))
1152             return false;
1153
1154         return true;
1155       }
1156
1157     case GIMPLE_ASSIGN:
1158       {
1159         enum tree_code code = gimple_assign_rhs_code (stmt);
1160
1161         switch (get_gimple_rhs_class (code))
1162           {
1163           case GIMPLE_UNARY_RHS:
1164           case GIMPLE_SINGLE_RHS:
1165             return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt))
1166                     && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt)));
1167
1168           case GIMPLE_BINARY_RHS:
1169             return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt))
1170                     && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt))
1171                     && is_simple_operand (loop, stmt, gimple_assign_rhs2 (stmt)));
1172
1173           case GIMPLE_INVALID_RHS:
1174           default:
1175             gcc_unreachable ();
1176           }
1177       }
1178
1179     case GIMPLE_CALL:
1180       {
1181         size_t i;
1182         size_t n = gimple_call_num_args (stmt);
1183         tree lhs = gimple_call_lhs (stmt);
1184
1185         if (lhs && !is_simple_operand (loop, stmt, lhs))
1186           return false;
1187
1188         for (i = 0; i < n; i++)
1189           if (!is_simple_operand (loop, stmt, gimple_call_arg (stmt, i)))
1190             return false;
1191
1192         return true;
1193       }
1194
1195     default:
1196       /* These nodes cut a new scope.  */
1197       return false;
1198     }
1199
1200   return false;
1201 }
1202
1203 /* Returns the statement of BB that contains a harmful operation: that
1204    can be a function call with side effects, the induction variables
1205    are not linear with respect to SCOP_ENTRY, etc.  The current open
1206    scop should end before this statement.  */
1207
1208 static gimple
1209 harmful_stmt_in_bb (basic_block scop_entry, basic_block bb)
1210 {
1211   gimple_stmt_iterator gsi;
1212
1213   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1214     if (!stmt_simple_for_scop_p (scop_entry, gsi_stmt (gsi)))
1215       return gsi_stmt (gsi);
1216
1217   return NULL;
1218 }
1219
1220 /* Returns true when BB will be represented in graphite.  Return false
1221    for the basic blocks that contain code eliminated in the code
1222    generation pass: i.e. induction variables and exit conditions.  */
1223
1224 static bool
1225 graphite_stmt_p (scop_p scop, basic_block bb,
1226                  VEC (data_reference_p, heap) *drs)
1227 {
1228   gimple_stmt_iterator gsi;
1229   loop_p loop = bb->loop_father;
1230
1231   if (VEC_length (data_reference_p, drs) > 0)
1232     return true;
1233
1234   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1235     {
1236       gimple stmt = gsi_stmt (gsi);
1237
1238       switch (gimple_code (stmt))
1239         {
1240           /* Control flow expressions can be ignored, as they are
1241              represented in the iteration domains and will be
1242              regenerated by graphite.  */
1243         case GIMPLE_COND:
1244         case GIMPLE_GOTO:
1245         case GIMPLE_SWITCH:
1246           break;
1247
1248         case GIMPLE_ASSIGN:
1249           {
1250             tree var = gimple_assign_lhs (stmt);
1251             var = analyze_scalar_evolution (loop, var);
1252             var = instantiate_scev (block_before_scop (scop), loop, var);
1253
1254             if (chrec_contains_undetermined (var))
1255               return true;
1256
1257             break;
1258           }
1259
1260         default:
1261           return true;
1262         }
1263     }
1264
1265   return false;
1266 }
1267
1268 /* Store the GRAPHITE representation of BB.  */
1269
1270 static void
1271 new_graphite_bb (scop_p scop, basic_block bb)
1272 {
1273   struct graphite_bb *gbb;
1274   VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
1275   struct loop *nest = outermost_loop_in_scop (scop, bb);
1276   gimple_stmt_iterator gsi;
1277
1278   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1279     find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs);
1280
1281   if (!graphite_stmt_p (scop, bb, drs))
1282     {
1283       free_data_refs (drs);
1284       return;
1285     }
1286
1287   gbb = XNEW (struct graphite_bb);
1288   bb->aux = gbb;
1289   GBB_BB (gbb) = bb;
1290   GBB_SCOP (gbb) = scop;
1291   GBB_DATA_REFS (gbb) = drs;
1292   GBB_DOMAIN (gbb) = NULL;
1293   GBB_CONDITIONS (gbb) = NULL;
1294   GBB_CONDITION_CASES (gbb) = NULL;
1295   GBB_LOOPS (gbb) = NULL;
1296   GBB_STATIC_SCHEDULE (gbb) = NULL;
1297   GBB_CLOOG_IV_TYPES (gbb) = NULL;
1298   VEC_safe_push (graphite_bb_p, heap, SCOP_BBS (scop), gbb);
1299 }
1300
1301 /* Frees GBB.  */
1302
1303 static void
1304 free_graphite_bb (struct graphite_bb *gbb)
1305 {
1306   if (GBB_DOMAIN (gbb))
1307     cloog_matrix_free (GBB_DOMAIN (gbb));
1308
1309   if (GBB_CLOOG_IV_TYPES (gbb))
1310     htab_delete (GBB_CLOOG_IV_TYPES (gbb));
1311
1312   /* FIXME: free_data_refs is disabled for the moment, but should be
1313      enabled.
1314
1315      free_data_refs (GBB_DATA_REFS (gbb)); */
1316
1317   VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
1318   VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
1319   VEC_free (loop_p, heap, GBB_LOOPS (gbb));
1320   GBB_BB (gbb)->aux = 0;
1321   XDELETE (gbb);
1322 }
1323
1324 \f
1325
1326 /* Structure containing the mapping between the old names and the new
1327    names used after block copy in the new loop context.  */
1328 typedef struct rename_map_elt
1329 {
1330   tree old_name, new_name;
1331 } *rename_map_elt;
1332
1333
1334 /* Print to stderr the element ELT.  */
1335
1336 static void
1337 debug_rename_elt (rename_map_elt elt)
1338 {
1339   fprintf (stderr, "(");
1340   print_generic_expr (stderr, elt->old_name, 0);
1341   fprintf (stderr, ", ");
1342   print_generic_expr (stderr, elt->new_name, 0);
1343   fprintf (stderr, ")\n");
1344 }
1345
1346 /* Helper function for debug_rename_map.  */
1347
1348 static int
1349 debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
1350 {
1351   struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
1352   debug_rename_elt (entry);
1353   return 1;
1354 }
1355
1356 /* Print to stderr all the elements of MAP.  */
1357
1358 void
1359 debug_rename_map (htab_t map)
1360 {
1361   htab_traverse (map, debug_rename_map_1, NULL);
1362 }
1363
1364 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
1365
1366 static inline rename_map_elt
1367 new_rename_map_elt (tree old_name, tree new_name)
1368 {
1369   rename_map_elt res;
1370   
1371   res = XNEW (struct rename_map_elt);
1372   res->old_name = old_name;
1373   res->new_name = new_name;
1374
1375   return res;
1376 }
1377
1378 /* Computes a hash function for database element ELT.  */
1379
1380 static hashval_t
1381 rename_map_elt_info (const void *elt)
1382 {
1383   return htab_hash_pointer (((const struct rename_map_elt *) elt)->old_name);
1384 }
1385
1386 /* Compares database elements E1 and E2.  */
1387
1388 static int
1389 eq_rename_map_elts (const void *e1, const void *e2)
1390 {
1391   const struct rename_map_elt *elt1 = (const struct rename_map_elt *) e1;
1392   const struct rename_map_elt *elt2 = (const struct rename_map_elt *) e2;
1393
1394   return (elt1->old_name == elt2->old_name);
1395 }
1396
1397 /* Returns the new name associated to OLD_NAME in MAP.  */
1398
1399 static tree
1400 get_new_name_from_old_name (htab_t map, tree old_name)
1401 {
1402   struct rename_map_elt tmp;
1403   PTR *slot;
1404
1405   tmp.old_name = old_name;
1406   slot = htab_find_slot (map, &tmp, NO_INSERT);
1407
1408   if (slot && *slot)
1409     return ((rename_map_elt) *slot)->new_name;
1410
1411   return old_name;
1412 }
1413
1414 \f
1415
1416 /* Creates a new scop starting with ENTRY.  */
1417
1418 static scop_p
1419 new_scop (edge entry, edge exit)
1420 {
1421   scop_p scop = XNEW (struct scop);
1422
1423   gcc_assert (entry && exit);
1424
1425   SCOP_REGION (scop) = new_sese (entry, exit);
1426   SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3);
1427   SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3);
1428   SCOP_LOOPS (scop) = BITMAP_ALLOC (NULL);
1429   SCOP_LOOP_NEST (scop) = VEC_alloc (loop_p, heap, 3);
1430   SCOP_ADD_PARAMS (scop) = true;
1431   SCOP_PARAMS (scop) = VEC_alloc (name_tree, heap, 3);
1432   SCOP_PROG (scop) = cloog_program_malloc ();
1433   cloog_program_set_names (SCOP_PROG (scop), cloog_names_malloc ());
1434   SCOP_LOOP2CLOOG_LOOP (scop) = htab_create (10, hash_loop_to_cloog_loop,
1435                                              eq_loop_to_cloog_loop,
1436                                              free);
1437   SCOP_LIVEOUT_RENAMES (scop) = htab_create (10, rename_map_elt_info,
1438                                              eq_rename_map_elts, free);
1439   return scop;
1440 }
1441
1442 /* Deletes SCOP.  */
1443
1444 static void
1445 free_scop (scop_p scop)
1446 {
1447   int i;
1448   name_tree p;
1449   struct graphite_bb *gb;
1450   name_tree iv;
1451
1452   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
1453     free_graphite_bb (gb);
1454
1455   VEC_free (graphite_bb_p, heap, SCOP_BBS (scop));
1456   BITMAP_FREE (SCOP_LOOPS (scop));
1457   VEC_free (loop_p, heap, SCOP_LOOP_NEST (scop));
1458
1459   for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
1460     free (iv);
1461   VEC_free (name_tree, heap, SCOP_OLDIVS (scop));
1462   
1463   for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
1464     free (p);
1465
1466   VEC_free (name_tree, heap, SCOP_PARAMS (scop));
1467   cloog_program_free (SCOP_PROG (scop));
1468   htab_delete (SCOP_LOOP2CLOOG_LOOP (scop)); 
1469   htab_delete (SCOP_LIVEOUT_RENAMES (scop));
1470   free_sese (SCOP_REGION (scop));
1471   XDELETE (scop);
1472 }
1473
1474 /* Deletes all scops in SCOPS.  */
1475
1476 static void
1477 free_scops (VEC (scop_p, heap) *scops)
1478 {
1479   int i;
1480   scop_p scop;
1481
1482   for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1483     free_scop (scop);
1484
1485   VEC_free (scop_p, heap, scops);
1486 }
1487
1488 typedef enum gbb_type {
1489   GBB_UNKNOWN,
1490   GBB_LOOP_SING_EXIT_HEADER,
1491   GBB_LOOP_MULT_EXIT_HEADER,
1492   GBB_LOOP_EXIT,
1493   GBB_COND_HEADER,
1494   GBB_SIMPLE,
1495   GBB_LAST
1496 } gbb_type;
1497
1498 /* Detect the type of BB.  Loop headers are only marked, if they are
1499    new.  This means their loop_father is different to LAST_LOOP.
1500    Otherwise they are treated like any other bb and their type can be
1501    any other type.  */
1502
1503 static gbb_type
1504 get_bb_type (basic_block bb, struct loop *last_loop)
1505 {
1506   VEC (basic_block, heap) *dom;
1507   int nb_dom, nb_suc;
1508   struct loop *loop = bb->loop_father;
1509
1510   /* Check, if we entry into a new loop. */
1511   if (loop != last_loop)
1512     {
1513       if (single_exit (loop) != NULL)
1514         return GBB_LOOP_SING_EXIT_HEADER;
1515       else if (loop->num != 0)
1516         return GBB_LOOP_MULT_EXIT_HEADER;
1517       else
1518         return GBB_COND_HEADER;
1519     }
1520
1521   dom = get_dominated_by (CDI_DOMINATORS, bb);
1522   nb_dom = VEC_length (basic_block, dom);
1523   VEC_free (basic_block, heap, dom);
1524
1525   if (nb_dom == 0)
1526     return GBB_LAST;
1527
1528   nb_suc = VEC_length (edge, bb->succs);
1529
1530   if (nb_dom == 1 && nb_suc == 1)
1531     return GBB_SIMPLE;
1532
1533   return GBB_COND_HEADER;
1534 }
1535
1536 /* A SCoP detection region, defined using bbs as borders. 
1537    All control flow touching this region, comes in passing basic_block ENTRY and
1538    leaves passing basic_block EXIT.  By using bbs instead of edges for the
1539    borders we are able to represent also regions that do not have a single
1540    entry or exit edge.
1541    But as they have a single entry basic_block and a single exit basic_block, we
1542    are able to generate for every sd_region a single entry and exit edge.
1543
1544    1   2
1545     \ /
1546      3  <- entry
1547      |
1548      4
1549     / \                 This region contains: {3, 4, 5, 6, 7, 8}
1550    5   6
1551    |   |
1552    7   8
1553     \ /
1554      9  <- exit  */
1555
1556
1557 typedef struct sd_region_p
1558 {
1559   /* The entry bb dominates all bbs in the sd_region.  It is part of the
1560      region.  */
1561   basic_block entry;
1562
1563   /* The exit bb postdominates all bbs in the sd_region, but is not 
1564      part of the region.  */
1565   basic_block exit;
1566 } sd_region;
1567
1568 DEF_VEC_O(sd_region);
1569 DEF_VEC_ALLOC_O(sd_region, heap);
1570
1571
1572 /* Moves the scops from SOURCE to TARGET and clean up SOURCE.  */
1573
1574 static void
1575 move_sd_regions (VEC (sd_region, heap) **source, VEC (sd_region, heap) **target)
1576 {
1577   sd_region *s;
1578   int i;
1579
1580   for (i = 0; VEC_iterate (sd_region, *source, i, s); i++)
1581     VEC_safe_push (sd_region, heap, *target, s);
1582   
1583   VEC_free (sd_region, heap, *source);
1584 }
1585
1586 /* Return true when it is not possible to represent the upper bound of
1587    LOOP in the polyhedral representation.  */
1588
1589 static bool
1590 graphite_cannot_represent_loop_niter (loop_p loop)
1591 {
1592   tree niter = number_of_latch_executions (loop);
1593
1594   return chrec_contains_undetermined (niter)
1595     || !scev_is_linear_expression (niter);
1596 }
1597 /* Store information needed by scopdet_* functions.  */
1598
1599 struct scopdet_info
1600 {
1601   /* Where the last open scop would stop if the current BB is harmful.  */
1602   basic_block last;
1603
1604   /* Where the next scop would start if the current BB is harmful.  */
1605   basic_block next;
1606
1607   /* The bb or one of its children contains open loop exits.  That means
1608      loop exit nodes that are not surrounded by a loop dominated by bb.  */ 
1609   bool exits;
1610
1611   /* The bb or one of its children contains only structures we can handle.  */ 
1612   bool difficult;
1613 };
1614
1615
1616 static struct scopdet_info build_scops_1 (basic_block, VEC (sd_region, heap) **,
1617                                           loop_p);
1618
1619 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
1620    to SCOPS.  TYPE is the gbb_type of BB.  */
1621
1622 static struct scopdet_info 
1623 scopdet_basic_block_info (basic_block bb, VEC (sd_region, heap) **scops,
1624                           gbb_type type)
1625 {
1626   struct loop *loop = bb->loop_father;
1627   struct scopdet_info result;
1628   gimple stmt;
1629
1630   /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps.  */
1631   stmt = harmful_stmt_in_bb (ENTRY_BLOCK_PTR, bb);
1632   result.difficult = (stmt != NULL);
1633   result.last = NULL;
1634
1635   switch (type)
1636     {
1637     case GBB_LAST:
1638       result.next = NULL;
1639       result.exits = false;
1640       result.last = bb;
1641
1642       /* Mark bbs terminating a SESE region difficult, if they start
1643          a condition.  */
1644       if (VEC_length (edge, bb->succs) > 1)
1645         result.difficult = true; 
1646
1647       break;
1648
1649     case GBB_SIMPLE:
1650       result.next = single_succ (bb);
1651       result.exits = false;
1652       result.last = bb;
1653       break;
1654
1655     case GBB_LOOP_SING_EXIT_HEADER:
1656       {
1657         VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap,3);
1658         struct scopdet_info sinfo;
1659
1660         sinfo = build_scops_1 (bb, &tmp_scops, loop);
1661         
1662         result.last = single_exit (bb->loop_father)->src;
1663         result.next = single_exit (bb->loop_father)->dest;
1664
1665         /* If we do not dominate result.next, remove it.  It's either
1666            the EXIT_BLOCK_PTR, or another bb dominates it and will
1667            call the scop detection for this bb.  */
1668         if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
1669           result.next = NULL;
1670
1671         if (result.last->loop_father != loop)
1672           result.next = NULL;
1673
1674         if (graphite_cannot_represent_loop_niter (loop))
1675           result.difficult = true;
1676
1677         if (sinfo.difficult)
1678           move_sd_regions (&tmp_scops, scops);
1679         else 
1680           VEC_free (sd_region, heap, tmp_scops);
1681
1682         result.exits = false;
1683         result.difficult |= sinfo.difficult;
1684         break;
1685       }
1686
1687     case GBB_LOOP_MULT_EXIT_HEADER:
1688       {
1689         /* XXX: For now we just do not join loops with multiple exits.  If the 
1690            exits lead to the same bb it may be possible to join the loop.  */
1691         VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
1692         VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1693         edge e;
1694         int i;
1695         build_scops_1 (bb, &tmp_scops, loop);
1696
1697         /* Scan the code dominated by this loop.  This means all bbs, that are
1698            are dominated by a bb in this loop, but are not part of this loop.
1699            
1700            The easiest case:
1701              - The loop exit destination is dominated by the exit sources.  
1702          
1703            TODO: We miss here the more complex cases:
1704                   - The exit destinations are dominated by another bb inside the
1705                     loop.
1706                   - The loop dominates bbs, that are not exit destinations.  */
1707         for (i = 0; VEC_iterate (edge, exits, i, e); i++)
1708           if (e->src->loop_father == loop
1709               && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
1710             {
1711               /* Pass loop_outer to recognize e->dest as loop header in
1712                  build_scops_1.  */
1713               if (e->dest->loop_father->header == e->dest)
1714                 build_scops_1 (e->dest, &tmp_scops,
1715                                loop_outer (e->dest->loop_father));
1716               else
1717                 build_scops_1 (e->dest, &tmp_scops, e->dest->loop_father);
1718             }
1719
1720         result.next = NULL; 
1721         result.last = NULL;
1722         result.difficult = true;
1723         result.exits = false;
1724         move_sd_regions (&tmp_scops, scops);
1725         VEC_free (edge, heap, exits);
1726         break;
1727       }
1728     case GBB_COND_HEADER:
1729       {
1730         VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
1731         struct scopdet_info sinfo;
1732         VEC (basic_block, heap) *dominated;
1733         int i;
1734         basic_block dom_bb;
1735         basic_block last_bb = NULL;
1736         edge e;
1737         result.exits = false;
1738  
1739         /* First check the successors of BB, and check if it is possible to join
1740            the different branches.  */
1741         for (i = 0; VEC_iterate (edge, bb->succs, i, e); i++)
1742           {
1743             /* Ignore loop exits.  They will be handled after the loop body.  */
1744             if (is_loop_exit (loop, e->dest))
1745               {
1746                 result.exits = true;
1747                 continue;
1748               }
1749
1750             /* Do not follow edges that lead to the end of the
1751                conditions block.  For example, in
1752
1753                |   0
1754                |  /|\
1755                | 1 2 |
1756                | | | |
1757                | 3 4 |
1758                |  \|/
1759                |   6
1760
1761                the edge from 0 => 6.  Only check if all paths lead to
1762                the same node 6.  */
1763
1764             if (!single_pred_p (e->dest))
1765               {
1766                 /* Check, if edge leads directly to the end of this
1767                    condition.  */
1768                 if (!last_bb)
1769                   {
1770                     last_bb = e->dest;
1771                   }
1772
1773                 if (e->dest != last_bb)
1774                   result.difficult = true;
1775
1776                 continue;
1777               }
1778
1779             if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1780               {
1781                 result.difficult = true;
1782                 continue;
1783               }
1784
1785             sinfo = build_scops_1 (e->dest, &tmp_scops, loop);
1786
1787             result.exits |= sinfo.exits;
1788             result.last = sinfo.last;
1789             result.difficult |= sinfo.difficult; 
1790
1791             /* Checks, if all branches end at the same point. 
1792                If that is true, the condition stays joinable.
1793                Have a look at the example above.  */
1794             if (sinfo.last && single_succ_p (sinfo.last))
1795               {
1796                 basic_block next_tmp = single_succ (sinfo.last);
1797                   
1798                 if (!last_bb)
1799                     last_bb = next_tmp;
1800
1801                 if (next_tmp != last_bb)
1802                   result.difficult = true;
1803               }
1804             else
1805               result.difficult = true;
1806           }
1807
1808         /* If the condition is joinable.  */
1809         if (!result.exits && !result.difficult)
1810           {
1811             /* Only return a next pointer if we dominate this pointer.
1812                Otherwise it will be handled by the bb dominating it.  */ 
1813             if (dominated_by_p (CDI_DOMINATORS, last_bb, bb) && last_bb != bb)
1814               result.next = last_bb;
1815             else
1816               result.next = NULL; 
1817
1818             VEC_free (sd_region, heap, tmp_scops);
1819             break;
1820           }
1821
1822         /* Scan remaining bbs dominated by BB.  */
1823         dominated = get_dominated_by (CDI_DOMINATORS, bb);
1824
1825         for (i = 0; VEC_iterate (basic_block, dominated, i, dom_bb); i++)
1826           {
1827             /* Ignore loop exits: they will be handled after the loop body.  */
1828             if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
1829                 < loop_depth (loop))
1830               {
1831                 result.exits = true;
1832                 continue;
1833               }
1834
1835             /* Ignore the bbs processed above.  */
1836             if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
1837               continue;
1838
1839             if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
1840               sinfo = build_scops_1 (dom_bb, &tmp_scops, loop_outer (loop));
1841             else
1842               sinfo = build_scops_1 (dom_bb, &tmp_scops, loop);
1843                                            
1844                                      
1845             result.exits |= sinfo.exits; 
1846             result.difficult = true;
1847             result.last = NULL;
1848           }
1849
1850         VEC_free (basic_block, heap, dominated);
1851
1852         result.next = NULL; 
1853         move_sd_regions (&tmp_scops, scops);
1854
1855         break;
1856       }
1857
1858     default:
1859       gcc_unreachable ();
1860     }
1861
1862   return result;
1863 }
1864
1865 /* Creates the SCoPs and writes entry and exit points for every SCoP.  */
1866
1867 static struct scopdet_info 
1868 build_scops_1 (basic_block current, VEC (sd_region, heap) **scops, loop_p loop)
1869 {
1870   bool in_scop = false;
1871   sd_region open_scop;
1872   struct scopdet_info sinfo;
1873
1874   /* Initialize result.  */ 
1875   struct scopdet_info result;
1876   result.exits = false;
1877   result.difficult = false;
1878   result.next = NULL;
1879   result.last = NULL;
1880   open_scop.entry = NULL;
1881   open_scop.exit = NULL;
1882   sinfo.last = NULL;
1883
1884   /* Loop over the dominance tree.  If we meet a difficult bb, close
1885      the current SCoP.  Loop and condition header start a new layer,
1886      and can only be added if all bbs in deeper layers are simple.  */
1887   while (current != NULL)
1888     {
1889       sinfo = scopdet_basic_block_info (current, scops, get_bb_type (current,
1890                                                                      loop));
1891
1892       if (!in_scop && !(sinfo.exits || sinfo.difficult))
1893         {
1894           open_scop.entry = current;
1895           open_scop.exit = NULL;
1896           in_scop = true;
1897         }
1898       else if (in_scop && (sinfo.exits || sinfo.difficult))
1899         {
1900           open_scop.exit = current;
1901           VEC_safe_push (sd_region, heap, *scops, &open_scop); 
1902           in_scop = false;
1903         }
1904
1905       result.difficult |= sinfo.difficult;
1906       result.exits |= sinfo.exits;
1907
1908       current = sinfo.next;
1909     }
1910
1911   /* Try to close open_scop, if we are still in an open SCoP.  */
1912   if (in_scop)
1913     {
1914       int i;
1915       edge e;
1916
1917         for (i = 0; VEC_iterate (edge, sinfo.last->succs, i, e); i++)
1918           if (dominated_by_p (CDI_POST_DOMINATORS, sinfo.last, e->dest))
1919             open_scop.exit = e->dest;
1920
1921         if (!open_scop.exit && open_scop.entry != sinfo.last)
1922           open_scop.exit = sinfo.last;
1923
1924         if (open_scop.exit)
1925           VEC_safe_push (sd_region, heap, *scops, &open_scop);
1926       
1927     }
1928
1929   result.last = sinfo.last;
1930   return result;
1931 }
1932
1933 /* Checks if a bb is contained in REGION.  */
1934
1935 static bool
1936 bb_in_sd_region (basic_block bb, sd_region *region)
1937 {
1938   return dominated_by_p (CDI_DOMINATORS, bb, region->entry)
1939          && !(dominated_by_p (CDI_DOMINATORS, bb, region->exit)
1940               && !dominated_by_p (CDI_DOMINATORS, region->entry,
1941                                   region->exit));
1942 }
1943
1944 /* Returns the single entry edge of REGION, if it does not exits NULL.  */
1945
1946 static edge
1947 find_single_entry_edge (sd_region *region)
1948 {
1949   edge e;
1950   edge_iterator ei;
1951   edge entry = NULL;
1952
1953   FOR_EACH_EDGE (e, ei, region->entry->preds)
1954     if (!bb_in_sd_region (e->src, region))
1955       {
1956         if (entry)
1957           {
1958             entry = NULL;
1959             break;
1960           }
1961
1962         else
1963           entry = e;
1964       }
1965
1966   return entry;
1967 }
1968
1969 /* Returns the single exit edge of REGION, if it does not exits NULL.  */
1970
1971 static edge
1972 find_single_exit_edge (sd_region *region)
1973 {
1974   edge e;
1975   edge_iterator ei;
1976   edge exit = NULL;
1977
1978   FOR_EACH_EDGE (e, ei, region->exit->preds)
1979     if (bb_in_sd_region (e->src, region))
1980       {
1981         if (exit)
1982           {
1983             exit = NULL;
1984             break;
1985           }
1986
1987         else
1988           exit = e;
1989       }
1990
1991   return exit;
1992 }
1993
1994 /* Create a single entry edge for REGION.  */
1995
1996 static void
1997 create_single_entry_edge (sd_region *region)
1998 {
1999   if (find_single_entry_edge (region))
2000     return;
2001
2002   /* There are multiple predecessors for bb_3 
2003
2004   |  1  2
2005   |  | /
2006   |  |/
2007   |  3  <- entry
2008   |  |\
2009   |  | |
2010   |  4 ^
2011   |  | |
2012   |  |/
2013   |  5
2014
2015   There are two edges (1->3, 2->3), that point from outside into the region,
2016   and another one (5->3), a loop latch, lead to bb_3.
2017
2018   We split bb_3.
2019   
2020   |  1  2
2021   |  | /
2022   |  |/
2023   |3.0
2024   |  |\     (3.0 -> 3.1) = single entry edge
2025   |3.1 |        <- entry
2026   |  | |
2027   |  | |
2028   |  4 ^ 
2029   |  | |
2030   |  |/
2031   |  5
2032
2033   If the loop is part of the SCoP, we have to redirect the loop latches.
2034
2035   |  1  2
2036   |  | /
2037   |  |/
2038   |3.0
2039   |  |      (3.0 -> 3.1) = entry edge
2040   |3.1          <- entry
2041   |  |\
2042   |  | |
2043   |  4 ^
2044   |  | |
2045   |  |/
2046   |  5  */
2047
2048   if (region->entry->loop_father->header != region->entry
2049       || dominated_by_p (CDI_DOMINATORS,
2050                          loop_latch_edge (region->entry->loop_father)->src,
2051                          region->exit))
2052     {
2053       edge forwarder = split_block_after_labels (region->entry);
2054       region->entry = forwarder->dest;
2055     }
2056   else
2057     /* This case is never executed, as the loop headers seem always to have a
2058        single edge pointing from outside into the loop.  */
2059     gcc_unreachable ();
2060       
2061 #ifdef ENABLE_CHECKING
2062   gcc_assert (find_single_entry_edge (region));
2063 #endif
2064 }
2065
2066 /* Check if the sd_region, mentioned in EDGE, has no exit bb.  */
2067
2068 static bool
2069 sd_region_without_exit (edge e)
2070 {
2071   sd_region *r = (sd_region *) e->aux;
2072
2073   if (r)
2074     return r->exit == NULL;
2075   else
2076     return false;
2077 }
2078
2079 /* Create a single exit edge for REGION.  */
2080
2081 static void
2082 create_single_exit_edge (sd_region *region)
2083 {
2084   edge e;
2085   edge_iterator ei;
2086   edge forwarder = NULL;
2087   basic_block exit;
2088   
2089   if (find_single_exit_edge (region))
2090     return;
2091
2092   /* We create a forwarder bb (5) for all edges leaving this region
2093      (3->5, 4->5).  All other edges leading to the same bb, are moved
2094      to a new bb (6).  If these edges where part of another region (2->5)
2095      we update the region->exit pointer, of this region.
2096
2097      To identify which edge belongs to which region we depend on the e->aux
2098      pointer in every edge.  It points to the region of the edge or to NULL,
2099      if the edge is not part of any region.
2100
2101      1 2 3 4    1->5 no region,                 2->5 region->exit = 5,
2102       \| |/     3->5 region->exit = NULL,       4->5 region->exit = NULL
2103         5       <- exit
2104
2105      changes to
2106
2107      1 2 3 4    1->6 no region,                         2->6 region->exit = 6,
2108      | | \/     3->5 no region,                         4->5 no region, 
2109      | |  5
2110       \| /      5->6 region->exit = 6
2111         6 
2112
2113      Now there is only a single exit edge (5->6).  */
2114   exit = region->exit;
2115   region->exit = NULL;
2116   forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
2117   
2118   /* Unmark the edges, that are no longer exit edges.  */
2119   FOR_EACH_EDGE (e, ei, forwarder->src->preds)
2120     if (e->aux)
2121       e->aux = NULL;
2122
2123   /* Mark the new exit edge.  */ 
2124   single_succ_edge (forwarder->src)->aux = region;
2125
2126   /* Update the exit bb of all regions, where exit edges lead to
2127      forwarder->dest.  */
2128   FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
2129     if (e->aux)
2130       ((sd_region *) e->aux)->exit = forwarder->dest;
2131
2132 #ifdef ENABLE_CHECKING
2133   gcc_assert (find_single_exit_edge (region));
2134 #endif
2135 }
2136
2137 /* Unmark the exit edges of all REGIONS.  
2138    See comment in "create_single_exit_edge". */
2139
2140 static void
2141 unmark_exit_edges (VEC (sd_region, heap) *regions)
2142 {
2143   int i;
2144   sd_region *s;
2145   edge e;
2146   edge_iterator ei;
2147
2148   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2149     FOR_EACH_EDGE (e, ei, s->exit->preds)
2150       e->aux = NULL;
2151 }
2152
2153
2154 /* Mark the exit edges of all REGIONS.  
2155    See comment in "create_single_exit_edge". */
2156
2157 static void
2158 mark_exit_edges (VEC (sd_region, heap) *regions)
2159 {
2160   int i;
2161   sd_region *s;
2162   edge e;
2163   edge_iterator ei;
2164
2165   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2166     FOR_EACH_EDGE (e, ei, s->exit->preds)
2167       if (bb_in_sd_region (e->src, s))
2168         e->aux = s;
2169 }
2170
2171 /* Free and compute again all the dominators information.  */
2172
2173 static inline void
2174 recompute_all_dominators (void)
2175 {
2176   mark_irreducible_loops ();
2177   free_dominance_info (CDI_DOMINATORS);
2178   free_dominance_info (CDI_POST_DOMINATORS);
2179   calculate_dominance_info (CDI_DOMINATORS);
2180   calculate_dominance_info (CDI_POST_DOMINATORS);
2181 }
2182
2183 /* Verifies properties that GRAPHITE should maintain during translation.  */
2184
2185 static inline void
2186 graphite_verify (void)
2187 {
2188 #ifdef ENABLE_CHECKING
2189   verify_loop_structure ();
2190   verify_dominators (CDI_DOMINATORS);
2191   verify_dominators (CDI_POST_DOMINATORS);
2192   verify_ssa (false);
2193   verify_loop_closed_ssa ();
2194 #endif
2195 }
2196
2197 /* Create for all scop regions a single entry and a single exit edge.  */
2198
2199 static void
2200 create_sese_edges (VEC (sd_region, heap) *regions)
2201 {
2202   int i;
2203   sd_region *s;
2204
2205   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2206     create_single_entry_edge (s);
2207
2208   mark_exit_edges (regions);
2209
2210   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2211     create_single_exit_edge (s);
2212
2213   unmark_exit_edges (regions);
2214
2215   fix_loop_structure (NULL);
2216
2217 #ifdef ENABLE_CHECKING
2218   verify_loop_structure ();
2219   verify_dominators (CDI_DOMINATORS);
2220   verify_ssa (false);
2221 #endif
2222 }
2223
2224 /* Create graphite SCoPs from an array of scop detection regions.  */
2225
2226 static void
2227 build_graphite_scops (VEC (sd_region, heap) *scop_regions)
2228 {
2229   int i;
2230   sd_region *s;
2231
2232   for (i = 0; VEC_iterate (sd_region, scop_regions, i, s); i++)
2233     {
2234       edge entry = find_single_entry_edge (s); 
2235       edge exit = find_single_exit_edge (s);
2236       scop_p scop = new_scop (entry, exit);
2237       VEC_safe_push (scop_p, heap, current_scops, scop);
2238
2239       /* Are there overlapping SCoPs?  */
2240 #ifdef ENABLE_CHECKING
2241         {
2242           int j;
2243           sd_region *s2;
2244
2245           for (j = 0; VEC_iterate (sd_region, scop_regions, j, s2); j++)
2246             if (s != s2)
2247               gcc_assert (!bb_in_sd_region (s->entry, s2));
2248         }
2249 #endif
2250     }
2251 }
2252
2253 /* Find static control parts.  */
2254
2255 static void
2256 build_scops (void)
2257 {
2258   struct loop *loop = current_loops->tree_root;
2259   VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
2260
2261   build_scops_1 (single_succ (ENTRY_BLOCK_PTR), &tmp_scops, loop);
2262   create_sese_edges (tmp_scops);
2263   build_graphite_scops (tmp_scops);
2264   VEC_free (sd_region, heap, tmp_scops);
2265 }
2266
2267 /* Gather the basic blocks belonging to the SCOP.  */
2268
2269 static void
2270 build_scop_bbs (scop_p scop)
2271 {
2272   basic_block *stack = XNEWVEC (basic_block, n_basic_blocks + 1);
2273   sbitmap visited = sbitmap_alloc (last_basic_block);
2274   int sp = 0;
2275
2276   sbitmap_zero (visited);
2277   stack[sp++] = SCOP_ENTRY (scop);
2278
2279   while (sp)
2280     {
2281       basic_block bb = stack[--sp];
2282       int depth = loop_depth (bb->loop_father);
2283       int num = bb->loop_father->num;
2284       edge_iterator ei;
2285       edge e;
2286
2287       /* Scop's exit is not in the scop.  Exclude also bbs, which are
2288          dominated by the SCoP exit.  These are e.g. loop latches.  */
2289       if (TEST_BIT (visited, bb->index)
2290           || dominated_by_p (CDI_DOMINATORS, bb, SCOP_EXIT (scop))
2291           /* Every block in the scop is dominated by scop's entry.  */
2292           || !dominated_by_p (CDI_DOMINATORS, bb, SCOP_ENTRY (scop)))
2293         continue;
2294
2295       new_graphite_bb (scop, bb);
2296       SET_BIT (visited, bb->index);
2297
2298       /* First push the blocks that have to be processed last.  Note
2299          that this means that the order in which the code is organized
2300          below is important: do not reorder the following code.  */
2301       FOR_EACH_EDGE (e, ei, bb->succs)
2302         if (! TEST_BIT (visited, e->dest->index)
2303             && (int) loop_depth (e->dest->loop_father) < depth)
2304           stack[sp++] = e->dest;
2305
2306       FOR_EACH_EDGE (e, ei, bb->succs)
2307         if (! TEST_BIT (visited, e->dest->index)
2308             && (int) loop_depth (e->dest->loop_father) == depth
2309             && e->dest->loop_father->num != num)
2310           stack[sp++] = e->dest;
2311
2312       FOR_EACH_EDGE (e, ei, bb->succs)
2313         if (! TEST_BIT (visited, e->dest->index)
2314             && (int) loop_depth (e->dest->loop_father) == depth
2315             && e->dest->loop_father->num == num
2316             && EDGE_COUNT (e->dest->preds) > 1)
2317           stack[sp++] = e->dest;
2318
2319       FOR_EACH_EDGE (e, ei, bb->succs)
2320         if (! TEST_BIT (visited, e->dest->index)
2321             && (int) loop_depth (e->dest->loop_father) == depth
2322             && e->dest->loop_father->num == num
2323             && EDGE_COUNT (e->dest->preds) == 1)
2324           stack[sp++] = e->dest;
2325
2326       FOR_EACH_EDGE (e, ei, bb->succs)
2327         if (! TEST_BIT (visited, e->dest->index)
2328             && (int) loop_depth (e->dest->loop_father) > depth)
2329           stack[sp++] = e->dest;
2330     }
2331
2332   free (stack);
2333   sbitmap_free (visited);
2334 }
2335
2336 /* Returns the number of reduction phi nodes in LOOP.  */
2337
2338 static int
2339 nb_reductions_in_loop (loop_p loop)
2340 {
2341   int res = 0;
2342   gimple_stmt_iterator gsi;
2343
2344   for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
2345     {
2346       gimple phi = gsi_stmt (gsi);
2347       tree scev;
2348       affine_iv iv;
2349
2350       if (!is_gimple_reg (PHI_RESULT (phi)))
2351         continue;
2352
2353       scev = analyze_scalar_evolution (loop, PHI_RESULT (phi));
2354       scev = instantiate_parameters (loop, scev);
2355       if (!simple_iv (loop, phi, PHI_RESULT (phi), &iv, true))
2356         res++;
2357     }
2358
2359   return res;
2360 }
2361
2362 /* A LOOP is in normal form when it contains only one scalar phi node
2363    that defines the main induction variable of the loop, only one
2364    increment of the IV, and only one exit condition. */
2365
2366 static tree
2367 graphite_loop_normal_form (loop_p loop)
2368 {
2369   struct tree_niter_desc niter;
2370   tree nit;
2371   gimple_seq stmts;
2372   edge exit = single_dom_exit (loop);
2373
2374   gcc_assert (number_of_iterations_exit (loop, exit, &niter, false));
2375   nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
2376                               NULL_TREE);
2377   if (stmts)
2378     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2379
2380   /* One IV per loop.  */
2381   if (nb_reductions_in_loop (loop) > 0)
2382     return NULL_TREE;
2383
2384   return canonicalize_loop_ivs (loop, NULL, nit);
2385 }
2386
2387 /* Record LOOP as occuring in SCOP.  Returns true when the operation
2388    was successful.  */
2389
2390 static bool
2391 scop_record_loop (scop_p scop, loop_p loop)
2392 {
2393   tree induction_var;
2394   name_tree oldiv;
2395
2396   if (bitmap_bit_p (SCOP_LOOPS (scop), loop->num))
2397     return true;
2398
2399   bitmap_set_bit (SCOP_LOOPS (scop), loop->num);
2400   VEC_safe_push (loop_p, heap, SCOP_LOOP_NEST (scop), loop);
2401
2402   induction_var = graphite_loop_normal_form (loop);
2403   if (!induction_var)
2404     return false;
2405
2406   oldiv = XNEW (struct name_tree);
2407   oldiv->t = induction_var;
2408   oldiv->name = get_name (SSA_NAME_VAR (oldiv->t));
2409   oldiv->loop = loop;
2410   VEC_safe_push (name_tree, heap, SCOP_OLDIVS (scop), oldiv);
2411   return true;
2412 }
2413
2414 /* Build the loop nests contained in SCOP.  Returns true when the
2415    operation was successful.  */
2416
2417 static bool
2418 build_scop_loop_nests (scop_p scop)
2419 {
2420   unsigned i;
2421   basic_block bb;
2422   struct loop *loop0, *loop1;
2423
2424   FOR_EACH_BB (bb)
2425     if (bb_in_sese_p (bb, SCOP_REGION (scop)))
2426       {
2427         struct loop *loop = bb->loop_father;
2428
2429         /* Only add loops if they are completely contained in the SCoP.  */
2430         if (loop->header == bb
2431             && bb_in_sese_p (loop->latch, SCOP_REGION (scop)))
2432           {
2433             if (!scop_record_loop (scop, loop))
2434               return false;
2435           }
2436       }
2437
2438   /* Make sure that the loops in the SCOP_LOOP_NEST are ordered.  It
2439      can be the case that an inner loop is inserted before an outer
2440      loop.  To avoid this, semi-sort once.  */
2441   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop0); i++)
2442     {
2443       if (VEC_length (loop_p, SCOP_LOOP_NEST (scop)) == i + 1)
2444         break;
2445
2446       loop1 = VEC_index (loop_p, SCOP_LOOP_NEST (scop), i + 1);
2447       if (loop0->num > loop1->num)
2448         {
2449           VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i, loop1);
2450           VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i + 1, loop0);
2451         }
2452     }
2453
2454   return true;
2455 }
2456
2457 /* Calculate the number of loops around LOOP in the SCOP.  */
2458
2459 static inline int
2460 nb_loops_around_loop_in_scop (struct loop *l, scop_p scop)
2461 {
2462   int d = 0;
2463
2464   for (; loop_in_sese_p (l, SCOP_REGION (scop)); d++, l = loop_outer (l));
2465
2466   return d;
2467 }
2468
2469 /* Calculate the number of loops around GB in the current SCOP.  */
2470
2471 int
2472 nb_loops_around_gb (graphite_bb_p gb)
2473 {
2474   return nb_loops_around_loop_in_scop (gbb_loop (gb), GBB_SCOP (gb));
2475 }
2476
2477 /* Returns the dimensionality of an enclosing loop iteration domain
2478    with respect to enclosing SCoP for a given data reference REF.  The
2479    returned dimensionality is homogeneous (depth of loop nest + number
2480    of SCoP parameters + const).  */
2481
2482 int
2483 ref_nb_loops (data_reference_p ref)
2484 {
2485   loop_p loop = loop_containing_stmt (DR_STMT (ref));
2486   scop_p scop = DR_SCOP (ref);
2487
2488   return nb_loops_around_loop_in_scop (loop, scop) + scop_nb_params (scop) + 2;
2489 }
2490
2491 /* Build dynamic schedules for all the BBs. */
2492
2493 static void
2494 build_scop_dynamic_schedules (scop_p scop)
2495 {
2496   int i, dim, loop_num, row, col;
2497   graphite_bb_p gb;
2498
2499   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2500     {
2501       loop_num = GBB_BB (gb)->loop_father->num;
2502
2503       if (loop_num != 0)
2504         {
2505           dim = nb_loops_around_gb (gb);
2506           GBB_DYNAMIC_SCHEDULE (gb) = cloog_matrix_alloc (dim, dim);
2507
2508           for (row = 0; row < GBB_DYNAMIC_SCHEDULE (gb)->NbRows; row++)
2509             for (col = 0; col < GBB_DYNAMIC_SCHEDULE (gb)->NbColumns; col++)
2510               if (row == col)
2511                 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 1);
2512               else
2513                 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 0);
2514         }
2515       else
2516         GBB_DYNAMIC_SCHEDULE (gb) = NULL;
2517     }
2518 }
2519
2520 /* Returns the number of loops that are identical at the beginning of
2521    the vectors A and B.  */
2522
2523 static int
2524 compare_prefix_loops (VEC (loop_p, heap) *a, VEC (loop_p, heap) *b)
2525 {
2526   int i;
2527   loop_p ea;
2528   int lb;
2529
2530   if (!a || !b)
2531     return 0;
2532
2533   lb = VEC_length (loop_p, b);
2534
2535   for (i = 0; VEC_iterate (loop_p, a, i, ea); i++)
2536     if (i >= lb
2537         || ea != VEC_index (loop_p, b, i))
2538       return i;
2539
2540   return 0;
2541 }
2542
2543 /* Build for BB the static schedule.
2544
2545    The STATIC_SCHEDULE is defined like this:
2546
2547    A
2548    for (i: ...)
2549      {
2550        for (j: ...)
2551          {
2552            B
2553            C 
2554          }
2555
2556        for (k: ...)
2557          {
2558            D
2559            E 
2560          }
2561      }
2562    F
2563
2564    Static schedules for A to F:
2565
2566      DEPTH
2567      0 1 2 
2568    A 0
2569    B 1 0 0
2570    C 1 0 1
2571    D 1 1 0
2572    E 1 1 1 
2573    F 2
2574 */
2575
2576 static void
2577 build_scop_canonical_schedules (scop_p scop)
2578 {
2579   int i;
2580   graphite_bb_p gb;
2581   int nb_loops = scop_nb_loops (scop);
2582   lambda_vector static_schedule = lambda_vector_new (nb_loops + 1);
2583   VEC (loop_p, heap) *loops_previous = NULL;
2584
2585   /* We have to start schedules at 0 on the first component and
2586      because we cannot compare_prefix_loops against a previous loop,
2587      prefix will be equal to zero, and that index will be
2588      incremented before copying.  */
2589   static_schedule[0] = -1;
2590
2591   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2592     {
2593       int prefix = compare_prefix_loops (loops_previous, GBB_LOOPS (gb));
2594       int nb = gbb_nb_loops (gb);
2595
2596       loops_previous = GBB_LOOPS (gb);
2597       memset (&(static_schedule[prefix + 1]), 0, sizeof (int) * (nb_loops - prefix));
2598       ++static_schedule[prefix];
2599       GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (nb + 1);
2600       lambda_vector_copy (static_schedule, 
2601                           GBB_STATIC_SCHEDULE (gb), nb + 1);
2602     }
2603 }
2604
2605 /* Build the LOOPS vector for all bbs in SCOP.  */
2606
2607 static void
2608 build_bb_loops (scop_p scop)
2609 {
2610   graphite_bb_p gb;
2611   int i;
2612
2613   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2614     {
2615       loop_p loop;
2616       int depth; 
2617
2618       depth = nb_loops_around_gb (gb) - 1; 
2619
2620       GBB_LOOPS (gb) = VEC_alloc (loop_p, heap, 3);
2621       VEC_safe_grow_cleared (loop_p, heap, GBB_LOOPS (gb), depth + 1);
2622
2623       loop = GBB_BB (gb)->loop_father;  
2624
2625       while (scop_contains_loop (scop, loop))
2626         {
2627           VEC_replace (loop_p, GBB_LOOPS (gb), depth, loop);
2628           loop = loop_outer (loop);
2629           depth--;
2630         }
2631     }
2632 }
2633
2634 /* Get the index for parameter VAR in SCOP.  */
2635
2636 static int
2637 param_index (tree var, scop_p scop)
2638 {
2639   int i;
2640   name_tree p;
2641   name_tree nvar;
2642
2643   gcc_assert (TREE_CODE (var) == SSA_NAME);
2644
2645   for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2646     if (p->t == var)
2647       return i;
2648
2649   gcc_assert (SCOP_ADD_PARAMS (scop));
2650
2651   nvar = XNEW (struct name_tree);
2652   nvar->t = var;
2653   nvar->name = NULL;
2654   VEC_safe_push (name_tree, heap, SCOP_PARAMS (scop), nvar);
2655   return VEC_length (name_tree, SCOP_PARAMS (scop)) - 1;
2656 }
2657
2658 /* Scan EXPR and translate it to an inequality vector INEQ that will
2659    be added, or subtracted, in the constraint domain matrix C at row
2660    R.  K is the number of columns for loop iterators in C. */ 
2661
2662 static void
2663 scan_tree_for_params (scop_p s, tree e, CloogMatrix *c, int r, Value k,
2664                       bool subtract)
2665 {
2666   int cst_col, param_col;
2667
2668   if (e == chrec_dont_know)
2669     return;
2670
2671   switch (TREE_CODE (e))
2672     {
2673     case POLYNOMIAL_CHREC:
2674       {
2675         tree left = CHREC_LEFT (e);
2676         tree right = CHREC_RIGHT (e);
2677         int var = CHREC_VARIABLE (e);
2678
2679         if (TREE_CODE (right) != INTEGER_CST)
2680           return;
2681
2682         if (c)
2683           {
2684             int loop_col = scop_gimple_loop_depth (s, get_loop (var)) + 1;
2685
2686             if (subtract)
2687               value_sub_int (c->p[r][loop_col], c->p[r][loop_col],
2688                              int_cst_value (right));
2689             else
2690               value_add_int (c->p[r][loop_col], c->p[r][loop_col],
2691                              int_cst_value (right));
2692           }
2693
2694         switch (TREE_CODE (left))
2695           {
2696           case POLYNOMIAL_CHREC:
2697             scan_tree_for_params (s, left, c, r, k, subtract);
2698             return;
2699
2700           case INTEGER_CST:
2701             /* Constant part.  */
2702             if (c)
2703               {
2704                 int v = int_cst_value (left);
2705                 cst_col = c->NbColumns - 1;
2706
2707                 if (v < 0)
2708                   {
2709                     v = -v;
2710                     subtract = subtract ? false : true;
2711                   }
2712
2713                 if (subtract)
2714                   value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2715                 else
2716                   value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2717               }
2718             return;
2719
2720           default:
2721             scan_tree_for_params (s, left, c, r, k, subtract);
2722             return;
2723           }
2724       }
2725       break;
2726
2727     case MULT_EXPR:
2728       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
2729         {
2730           if (c)
2731             {
2732               Value val;
2733               gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
2734               value_init (val);
2735               value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
2736               value_multiply (k, k, val);
2737               value_clear (val);
2738             }
2739           scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2740         }
2741       else
2742         {
2743           if (c)
2744             {
2745               Value val;
2746               gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
2747               value_init (val);
2748               value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
2749               value_multiply (k, k, val);
2750               value_clear (val);
2751             }
2752           scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2753         }
2754       break;
2755
2756     case PLUS_EXPR:
2757     case POINTER_PLUS_EXPR:
2758       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2759       scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2760       break;
2761
2762     case MINUS_EXPR:
2763       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2764       scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, !subtract);
2765       break;
2766
2767     case NEGATE_EXPR:
2768       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, !subtract);
2769       break;
2770
2771     case SSA_NAME:
2772       param_col = param_index (e, s);
2773
2774       if (c)
2775         {
2776           param_col += c->NbColumns - scop_nb_params (s) - 1;
2777
2778           if (subtract)
2779             value_subtract (c->p[r][param_col], c->p[r][param_col], k);
2780           else
2781             value_addto (c->p[r][param_col], c->p[r][param_col], k);
2782         }
2783       break;
2784
2785     case INTEGER_CST:
2786       if (c)
2787         {
2788           int v = int_cst_value (e);
2789           cst_col = c->NbColumns - 1;
2790
2791           if (v < 0)
2792           {
2793             v = -v;
2794             subtract = subtract ? false : true;
2795           }
2796                 
2797           if (subtract)
2798             value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v); 
2799           else
2800             value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2801         }
2802       break;
2803
2804     CASE_CONVERT:
2805     case NON_LVALUE_EXPR:
2806       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2807       break;
2808
2809     default:
2810       gcc_unreachable ();
2811       break;
2812     }
2813 }
2814
2815 /* Data structure for idx_record_params.  */
2816
2817 struct irp_data
2818 {
2819   struct loop *loop;
2820   scop_p scop;
2821 };
2822
2823 /* For a data reference with an ARRAY_REF as its BASE, record the
2824    parameters occurring in IDX.  DTA is passed in as complementary
2825    information, and is used by the automatic walker function.  This
2826    function is a callback for for_each_index.  */
2827
2828 static bool
2829 idx_record_params (tree base, tree *idx, void *dta)
2830 {
2831   struct irp_data *data = (struct irp_data *) dta;
2832
2833   if (TREE_CODE (base) != ARRAY_REF)
2834     return true;
2835
2836   if (TREE_CODE (*idx) == SSA_NAME)
2837     {
2838       tree scev;
2839       scop_p scop = data->scop;
2840       struct loop *loop = data->loop;
2841       Value one;
2842
2843       scev = analyze_scalar_evolution (loop, *idx);
2844       scev = instantiate_scev (block_before_scop (scop), loop, scev);
2845
2846       value_init (one);
2847       value_set_si (one, 1);
2848       scan_tree_for_params (scop, scev, NULL, 0, one, false);
2849       value_clear (one);
2850     }
2851
2852   return true;
2853 }
2854
2855 /* Find parameters with respect to SCOP in BB. We are looking in memory
2856    access functions, conditions and loop bounds.  */
2857
2858 static void
2859 find_params_in_bb (scop_p scop, graphite_bb_p gb)
2860 {
2861   int i;
2862   data_reference_p dr;
2863   gimple stmt;
2864   loop_p father = GBB_BB (gb)->loop_father;
2865
2866   for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), i, dr); i++)
2867     {
2868       struct irp_data irp;
2869
2870       irp.loop = father;
2871       irp.scop = scop;
2872       for_each_index (&dr->ref, idx_record_params, &irp);
2873     }
2874
2875   /* Find parameters in conditional statements.  */ 
2876   for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gb), i, stmt); i++)
2877     {
2878       Value one;
2879       loop_p loop = father;
2880
2881       tree lhs, rhs;
2882
2883       lhs = gimple_cond_lhs (stmt);
2884       lhs = analyze_scalar_evolution (loop, lhs);
2885       lhs = instantiate_scev (block_before_scop (scop), loop, lhs);
2886
2887       rhs = gimple_cond_rhs (stmt);
2888       rhs = analyze_scalar_evolution (loop, rhs);
2889       rhs = instantiate_scev (block_before_scop (scop), loop, rhs);
2890
2891       value_init (one);
2892       scan_tree_for_params (scop, lhs, NULL, 0, one, false);
2893       value_set_si (one, 1);
2894       scan_tree_for_params (scop, rhs, NULL, 0, one, false);
2895       value_clear (one);
2896     }
2897 }
2898
2899 /* Saves in NV the name of variable P->T.  */
2900
2901 static void
2902 save_var_name (char **nv, int i, name_tree p)
2903 {
2904   const char *name = get_name (SSA_NAME_VAR (p->t));
2905
2906   if (name)
2907     {
2908       int len = strlen (name) + 16;
2909       nv[i] = XNEWVEC (char, len);
2910       snprintf (nv[i], len, "%s_%d", name, SSA_NAME_VERSION (p->t));
2911     }
2912   else
2913     {
2914       nv[i] = XNEWVEC (char, 16);
2915       snprintf (nv[i], 2 + 16, "T_%d", SSA_NAME_VERSION (p->t));
2916     }
2917
2918   p->name = nv[i];
2919 }
2920
2921 /* Return the maximal loop depth in SCOP.  */
2922
2923 static int
2924 scop_max_loop_depth (scop_p scop)
2925 {
2926   int i;
2927   graphite_bb_p gbb;
2928   int max_nb_loops = 0;
2929
2930   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++) 
2931     {    
2932       int nb_loops = gbb_nb_loops (gbb);
2933       if (max_nb_loops < nb_loops)
2934         max_nb_loops = nb_loops;
2935     }    
2936
2937   return max_nb_loops;
2938 }
2939
2940 /* Initialize Cloog's parameter names from the names used in GIMPLE.
2941    Initialize Cloog's iterator names, using 'graphite_iterator_%d'
2942    from 0 to scop_nb_loops (scop).  */
2943
2944 static void
2945 initialize_cloog_names (scop_p scop)
2946 {
2947   int i, nb_params = VEC_length (name_tree, SCOP_PARAMS (scop));
2948   char **params = XNEWVEC (char *, nb_params);
2949   int nb_iterators = scop_max_loop_depth (scop);
2950   int nb_scattering= cloog_program_nb_scattdims (SCOP_PROG (scop));
2951   char **iterators = XNEWVEC (char *, nb_iterators * 2);
2952   char **scattering = XNEWVEC (char *, nb_scattering);
2953   name_tree p;
2954
2955   for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2956     save_var_name (params, i, p);
2957
2958   cloog_names_set_nb_parameters (cloog_program_names (SCOP_PROG (scop)),
2959                                  nb_params);
2960   cloog_names_set_parameters (cloog_program_names (SCOP_PROG (scop)),
2961                               params);
2962
2963   for (i = 0; i < nb_iterators; i++)
2964     {
2965       int len = 18 + 16;
2966       iterators[i] = XNEWVEC (char, len);
2967       snprintf (iterators[i], len, "graphite_iterator_%d", i);
2968     }
2969
2970   cloog_names_set_nb_iterators (cloog_program_names (SCOP_PROG (scop)),
2971                                 nb_iterators);
2972   cloog_names_set_iterators (cloog_program_names (SCOP_PROG (scop)),
2973                              iterators);
2974
2975   for (i = 0; i < nb_scattering; i++)
2976     {
2977       int len = 2 + 16;
2978       scattering[i] = XNEWVEC (char, len);
2979       snprintf (scattering[i], len, "s_%d", i);
2980     }
2981
2982   cloog_names_set_nb_scattering (cloog_program_names (SCOP_PROG (scop)),
2983                                  nb_scattering);
2984   cloog_names_set_scattering (cloog_program_names (SCOP_PROG (scop)),
2985                               scattering);
2986 }
2987
2988 /* Record the parameters used in the SCOP.  A variable is a parameter
2989    in a scop if it does not vary during the execution of that scop.  */
2990
2991 static void
2992 find_scop_parameters (scop_p scop)
2993 {
2994   graphite_bb_p gb;
2995   unsigned i;
2996   struct loop *loop;
2997   Value one;
2998
2999   value_init (one);
3000   value_set_si (one, 1);
3001
3002   /* Find the parameters used in the loop bounds.  */
3003   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
3004     {
3005       tree nb_iters = number_of_latch_executions (loop);
3006
3007       if (!chrec_contains_symbols (nb_iters))
3008         continue;
3009
3010       nb_iters = analyze_scalar_evolution (loop, nb_iters);
3011       nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
3012       scan_tree_for_params (scop, nb_iters, NULL, 0, one, false);
3013     }
3014
3015   value_clear (one);
3016
3017   /* Find the parameters used in data accesses.  */
3018   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3019     find_params_in_bb (scop, gb);
3020
3021   SCOP_ADD_PARAMS (scop) = false;
3022 }
3023
3024 /* Build the context constraints for SCOP: constraints and relations
3025    on parameters.  */
3026
3027 static void
3028 build_scop_context (scop_p scop)
3029 {
3030   int nb_params = scop_nb_params (scop);
3031   CloogMatrix *matrix = cloog_matrix_alloc (1, nb_params + 2);
3032
3033   /* Insert '0 >= 0' in the context matrix, as it is not allowed to be
3034      empty. */
3035  
3036   value_set_si (matrix->p[0][0], 1);
3037
3038   value_set_si (matrix->p[0][nb_params + 1], 0);
3039
3040   cloog_program_set_context (SCOP_PROG (scop),
3041                              cloog_domain_matrix2domain (matrix));
3042   cloog_matrix_free (matrix);
3043 }
3044
3045 /* Returns a graphite_bb from BB.  */
3046
3047 static inline graphite_bb_p
3048 gbb_from_bb (basic_block bb)
3049 {
3050   return (graphite_bb_p) bb->aux;
3051 }
3052
3053 /* Builds the constraint matrix for LOOP in SCOP.  NB_OUTER_LOOPS is the
3054    number of loops surrounding LOOP in SCOP.  OUTER_CSTR gives the
3055    constraints matrix for the surrounding loops.  */
3056
3057 static void
3058 build_loop_iteration_domains (scop_p scop, struct loop *loop,
3059                               CloogMatrix *outer_cstr, int nb_outer_loops)
3060 {
3061   int i, j, row;
3062   CloogMatrix *cstr;
3063   graphite_bb_p gb;
3064
3065   int nb_rows = outer_cstr->NbRows + 1;
3066   int nb_cols = outer_cstr->NbColumns + 1;
3067
3068   /* Last column of CSTR is the column of constants.  */
3069   int cst_col = nb_cols - 1;
3070
3071   /* The column for the current loop is just after the columns of
3072      other outer loops.  */
3073   int loop_col = nb_outer_loops + 1;
3074
3075   tree nb_iters = number_of_latch_executions (loop);
3076
3077   /* When the number of iterations is a constant or a parameter, we
3078      add a constraint for the upper bound of the loop.  So add a row
3079      to the constraint matrix before allocating it.  */
3080   if (TREE_CODE (nb_iters) == INTEGER_CST
3081       || !chrec_contains_undetermined (nb_iters))
3082     nb_rows++;
3083
3084   cstr = cloog_matrix_alloc (nb_rows, nb_cols);
3085
3086   /* Copy the outer constraints.  */
3087   for (i = 0; i < outer_cstr->NbRows; i++)
3088     {
3089       /* Copy the eq/ineq and loops columns.  */
3090       for (j = 0; j < loop_col; j++)
3091         value_assign (cstr->p[i][j], outer_cstr->p[i][j]);
3092
3093       /* Leave an empty column in CSTR for the current loop, and then
3094          copy the parameter columns.  */
3095       for (j = loop_col; j < outer_cstr->NbColumns; j++)
3096         value_assign (cstr->p[i][j + 1], outer_cstr->p[i][j]);
3097     }
3098
3099   /* 0 <= loop_i */
3100   row = outer_cstr->NbRows;
3101   value_set_si (cstr->p[row][0], 1);
3102   value_set_si (cstr->p[row][loop_col], 1);
3103
3104   /* loop_i <= nb_iters */
3105   if (TREE_CODE (nb_iters) == INTEGER_CST)
3106     {
3107       row++;
3108       value_set_si (cstr->p[row][0], 1);
3109       value_set_si (cstr->p[row][loop_col], -1);
3110
3111       value_set_si (cstr->p[row][cst_col],
3112                     int_cst_value (nb_iters));
3113     }
3114   else if (!chrec_contains_undetermined (nb_iters))
3115     {
3116       /* Otherwise nb_iters contains parameters: scan the nb_iters
3117          expression and build its matrix representation.  */
3118       Value one;
3119
3120       row++;
3121       value_set_si (cstr->p[row][0], 1);
3122       value_set_si (cstr->p[row][loop_col], -1);
3123
3124       nb_iters = analyze_scalar_evolution (loop, nb_iters);
3125       nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
3126
3127       value_init (one);
3128       value_set_si (one, 1);
3129       scan_tree_for_params (scop, nb_iters, cstr, row, one, false);
3130       value_clear (one);
3131     }
3132   else
3133     gcc_unreachable ();
3134
3135   if (loop->inner && loop_in_sese_p (loop->inner, SCOP_REGION (scop)))
3136     build_loop_iteration_domains (scop, loop->inner, cstr, nb_outer_loops + 1);
3137
3138   /* Only go to the next loops, if we are not at the outermost layer.  These
3139      have to be handled seperately, as we can be sure, that the chain at this
3140      layer will be connected.  */
3141   if (nb_outer_loops != 0 && loop->next && loop_in_sese_p (loop->next,
3142                                                            SCOP_REGION (scop)))
3143     build_loop_iteration_domains (scop, loop->next, outer_cstr, nb_outer_loops);
3144
3145   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3146     if (gbb_loop (gb) == loop)
3147       GBB_DOMAIN (gb) = cloog_matrix_copy (cstr);
3148
3149   cloog_matrix_free (cstr);
3150 }
3151
3152 /* Add conditions to the domain of GB.  */
3153
3154 static void
3155 add_conditions_to_domain (graphite_bb_p gb)
3156 {
3157   unsigned int i,j;
3158   gimple stmt;
3159   VEC (gimple, heap) *conditions = GBB_CONDITIONS (gb);
3160   CloogMatrix *domain = GBB_DOMAIN (gb);
3161   scop_p scop = GBB_SCOP (gb);
3162
3163   unsigned nb_rows;
3164   unsigned nb_cols;
3165   unsigned nb_new_rows = 0;
3166   unsigned row;
3167
3168   if (VEC_empty (gimple, conditions))
3169     return;
3170
3171   if (domain)
3172     {
3173       nb_rows = domain->NbRows;
3174       nb_cols = domain->NbColumns;
3175     }
3176   else  
3177     {
3178       nb_rows = 0;
3179       nb_cols = nb_loops_around_gb (gb) + scop_nb_params (scop) + 2;
3180     }
3181
3182   /* Count number of necessary new rows to add the conditions to the
3183      domain.  */
3184   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3185     {
3186       switch (gimple_code (stmt))
3187         {
3188         case GIMPLE_COND:
3189           {
3190             enum tree_code code = gimple_cond_code (stmt);
3191
3192             switch (code)
3193               {
3194               case NE_EXPR:
3195               case EQ_EXPR:
3196                 /* NE and EQ statements are not supported right know. */
3197                 gcc_unreachable ();
3198                 break;
3199               case LT_EXPR:
3200               case GT_EXPR:
3201               case LE_EXPR:
3202               case GE_EXPR:
3203                 nb_new_rows++;
3204                 break;
3205               default:
3206                 gcc_unreachable ();
3207                 break;
3208               }
3209           break;
3210           }
3211         case SWITCH_EXPR:
3212           /* Switch statements are not supported right know.  */
3213           gcc_unreachable ();
3214           break;
3215
3216         default:
3217           gcc_unreachable ();
3218           break;
3219         }
3220     }
3221
3222
3223   /* Enlarge the matrix.  */ 
3224   { 
3225     CloogMatrix *new_domain;
3226     new_domain = cloog_matrix_alloc (nb_rows + nb_new_rows, nb_cols);
3227
3228     if (domain)
3229       {
3230         for (i = 0; i < nb_rows; i++)
3231           for (j = 0; j < nb_cols; j++)
3232             value_assign (new_domain->p[i][j], domain->p[i][j]);
3233
3234         cloog_matrix_free (domain);
3235       }
3236
3237     domain = new_domain;
3238     GBB_DOMAIN (gb) = new_domain;
3239   }
3240
3241   /* Add the conditions to the new enlarged domain matrix.  */
3242   row = nb_rows;
3243   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3244     {
3245       switch (gimple_code (stmt))
3246         {
3247         case GIMPLE_COND:
3248           {
3249             Value one;
3250             enum tree_code code;
3251             tree left;
3252             tree right;
3253             loop_p loop = GBB_BB (gb)->loop_father;
3254
3255             left = gimple_cond_lhs (stmt);
3256             right = gimple_cond_rhs (stmt);
3257
3258             left = analyze_scalar_evolution (loop, left);
3259             right = analyze_scalar_evolution (loop, right);
3260
3261             left = instantiate_scev (block_before_scop (scop), loop, left);
3262             right = instantiate_scev (block_before_scop (scop), loop, right);
3263
3264             code = gimple_cond_code (stmt);
3265
3266             /* The conditions for ELSE-branches are inverted.  */
3267             if (VEC_index (gimple, gb->condition_cases, i) == NULL)
3268               code = invert_tree_comparison (code, false);
3269
3270             switch (code)
3271               {
3272               case NE_EXPR:
3273                 /* NE statements are not supported right know. */
3274                 gcc_unreachable ();
3275                 break;
3276               case EQ_EXPR:
3277                 value_set_si (domain->p[row][0], 1);
3278                 value_init (one);
3279                 value_set_si (one, 1);
3280                 scan_tree_for_params (scop, left, domain, row, one, true);
3281                 value_set_si (one, 1);
3282                 scan_tree_for_params (scop, right, domain, row, one, false);
3283                 row++;
3284                 value_set_si (domain->p[row][0], 1);
3285                 value_set_si (one, 1);
3286                 scan_tree_for_params (scop, left, domain, row, one, false);
3287                 value_set_si (one, 1);
3288                 scan_tree_for_params (scop, right, domain, row, one, true);
3289                 value_clear (one);
3290                 row++;
3291                 break;
3292               case LT_EXPR:
3293                 value_set_si (domain->p[row][0], 1);
3294                 value_init (one);
3295                 value_set_si (one, 1);
3296                 scan_tree_for_params (scop, left, domain, row, one, true);
3297                 value_set_si (one, 1);
3298                 scan_tree_for_params (scop, right, domain, row, one, false);
3299                 value_sub_int (domain->p[row][nb_cols - 1],
3300                     domain->p[row][nb_cols - 1], 1); 
3301                 value_clear (one);
3302                 row++;
3303                 break;
3304               case GT_EXPR:
3305                 value_set_si (domain->p[row][0], 1);
3306                 value_init (one);
3307                 value_set_si (one, 1);
3308                 scan_tree_for_params (scop, left, domain, row, one, false);
3309                 value_set_si (one, 1);
3310                 scan_tree_for_params (scop, right, domain, row, one, true);
3311                 value_sub_int (domain->p[row][nb_cols - 1],
3312                     domain->p[row][nb_cols - 1], 1);
3313                 value_clear (one);
3314                 row++;
3315                 break;
3316               case LE_EXPR:
3317                 value_set_si (domain->p[row][0], 1);
3318                 value_init (one);
3319                 value_set_si (one, 1);
3320                 scan_tree_for_params (scop, left, domain, row, one, true);
3321                 value_set_si (one, 1);
3322                 scan_tree_for_params (scop, right, domain, row, one, false);
3323                 value_clear (one);
3324                 row++;
3325                 break;
3326               case GE_EXPR:
3327                 value_set_si (domain->p[row][0], 1);
3328                 value_init (one);
3329                 value_set_si (one, 1);
3330                 scan_tree_for_params (scop, left, domain, row, one, false);
3331                 value_set_si (one, 1);
3332                 scan_tree_for_params (scop, right, domain, row, one, true);
3333                 value_clear (one);
3334                 row++;
3335                 break;
3336               default:
3337                 gcc_unreachable ();
3338                 break;
3339               }
3340             break;
3341           }
3342         case GIMPLE_SWITCH:
3343           /* Switch statements are not supported right know.  */
3344           gcc_unreachable ();
3345           break;
3346
3347         default:
3348           gcc_unreachable ();
3349           break;
3350         }
3351     }
3352 }
3353
3354 /* Returns true when PHI defines an induction variable in the loop
3355    containing the PHI node.  */
3356
3357 static bool
3358 phi_node_is_iv (gimple phi)
3359 {
3360   loop_p loop = gimple_bb (phi)->loop_father;
3361   tree scev = analyze_scalar_evolution (loop, gimple_phi_result (phi));
3362
3363   return tree_contains_chrecs (scev, NULL);
3364 }
3365
3366 /* Returns true when BB contains scalar phi nodes that are not an
3367    induction variable of a loop.  */
3368
3369 static bool
3370 bb_contains_non_iv_scalar_phi_nodes (basic_block bb)
3371 {
3372   gimple phi = NULL;
3373   gimple_stmt_iterator si;
3374
3375   for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
3376     if (is_gimple_reg (gimple_phi_result (gsi_stmt (si))))
3377       {
3378         /* Store the unique scalar PHI node: at this point, loops
3379            should be in cannonical form, so we expect to see at most
3380            one scalar phi node in the loop header.  */
3381         if (phi
3382             || bb != bb->loop_father->header)
3383           return true;
3384
3385         phi = gsi_stmt (si);
3386       }
3387
3388   if (!phi
3389       || phi_node_is_iv (phi))
3390     return false;
3391
3392   return true;
3393 }
3394
3395 /* Helper recursive function.  Record in CONDITIONS and CASES all
3396    conditions from 'if's and 'switch'es occurring in BB from SCOP.
3397
3398    Returns false when the conditions contain scalar computations that
3399    depend on the condition, i.e. when there are scalar phi nodes on
3400    the junction after the condition.  Only the computations occurring
3401    on memory can be handled in the polyhedral model: operations that
3402    define scalar evolutions in conditions, that can potentially be
3403    used to index memory, can't be handled by the polyhedral model.  */
3404
3405 static bool
3406 build_scop_conditions_1 (VEC (gimple, heap) **conditions,
3407                          VEC (gimple, heap) **cases, basic_block bb,
3408                          scop_p scop)
3409 {
3410   bool res = true;
3411   int i, j;
3412   graphite_bb_p gbb;
3413   gimple_stmt_iterator gsi;
3414   basic_block bb_child, bb_iter;
3415   VEC (basic_block, heap) *dom;
3416   
3417   /* Make sure we are in the SCoP.  */
3418   if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
3419     return true;
3420
3421   if (bb_contains_non_iv_scalar_phi_nodes (bb))
3422     return false;
3423
3424   gbb = gbb_from_bb (bb);
3425   if (gbb)
3426     {
3427       GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
3428       GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
3429     }
3430
3431   dom = get_dominated_by (CDI_DOMINATORS, bb);
3432
3433   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3434     {
3435       gimple stmt = gsi_stmt (gsi);
3436       VEC (edge, gc) *edges;
3437       edge e;
3438
3439       switch (gimple_code (stmt))
3440         {
3441         case GIMPLE_COND:
3442           edges = bb->succs;
3443           for (i = 0; VEC_iterate (edge, edges, i, e); i++)
3444             if ((dominated_by_p (CDI_DOMINATORS, e->dest, bb))
3445                 && VEC_length (edge, e->dest->preds) == 1)
3446               {
3447                 /* Remove the scanned block from the dominator successors.  */
3448                 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3449                   if (bb_iter == e->dest)
3450                     {
3451                       VEC_unordered_remove (basic_block, dom, j);
3452                       break;
3453                     }
3454
3455                 /* Recursively scan the then or else part.  */
3456                 if (e->flags & EDGE_TRUE_VALUE)
3457                   VEC_safe_push (gimple, heap, *cases, stmt);
3458                 else 
3459                   {
3460                     gcc_assert (e->flags & EDGE_FALSE_VALUE);
3461                     VEC_safe_push (gimple, heap, *cases, NULL);
3462                   }
3463
3464                 VEC_safe_push (gimple, heap, *conditions, stmt);
3465                 if (!build_scop_conditions_1 (conditions, cases, e->dest, scop))
3466                   {
3467                     res = false;
3468                     goto done;
3469                   }
3470                 VEC_pop (gimple, *conditions);
3471                 VEC_pop (gimple, *cases);
3472               }
3473           break;
3474
3475         case GIMPLE_SWITCH:
3476           {
3477             unsigned i;
3478             gimple_stmt_iterator gsi_search_gimple_label;
3479
3480             for (i = 0; i < gimple_switch_num_labels (stmt); ++i)
3481               {
3482                 basic_block bb_iter;
3483                 size_t k;
3484                 size_t n_cases = VEC_length (gimple, *conditions);
3485                 unsigned n = gimple_switch_num_labels (stmt);
3486
3487                 bb_child = label_to_block
3488                   (CASE_LABEL (gimple_switch_label (stmt, i)));
3489
3490                 for (k = 0; k < n; k++)
3491                   if (i != k
3492                       && label_to_block 
3493                       (CASE_LABEL (gimple_switch_label (stmt, k))) == bb_child)
3494                     break;
3495
3496                 /* Switches with multiple case values for the same
3497                    block are not handled.  */
3498                 if (k != n
3499                     /* Switch cases with more than one predecessor are
3500                        not handled.  */
3501                     || VEC_length (edge, bb_child->preds) != 1)
3502                   {
3503                     res = false;
3504                     goto done;
3505                   }
3506
3507                 /* Recursively scan the corresponding 'case' block.  */
3508                 for (gsi_search_gimple_label = gsi_start_bb (bb_child);
3509                      !gsi_end_p (gsi_search_gimple_label);
3510                      gsi_next (&gsi_search_gimple_label))
3511                   {
3512                     gimple label = gsi_stmt (gsi_search_gimple_label);
3513
3514                     if (gimple_code (label) == GIMPLE_LABEL)
3515                       {
3516                         tree t = gimple_label_label (label);
3517
3518                         gcc_assert (t == gimple_switch_label (stmt, i));
3519                         VEC_replace (gimple, *cases, n_cases, label);
3520                         break;
3521                       }
3522                   }
3523
3524                 if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3525                   {
3526                     res = false;
3527                     goto done;
3528                   }
3529
3530                 /* Remove the scanned block from the dominator successors.  */
3531                 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3532                   if (bb_iter == bb_child)
3533                     {
3534                       VEC_unordered_remove (basic_block, dom, j);
3535                       break;
3536                     }
3537               }
3538
3539             VEC_pop (gimple, *conditions);
3540             VEC_pop (gimple, *cases);
3541             break;
3542           }
3543
3544         default:
3545           break;
3546       }
3547   }
3548
3549   /* Scan all immediate dominated successors.  */
3550   for (i = 0; VEC_iterate (basic_block, dom, i, bb_child); i++)
3551     if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3552       {
3553         res = false;
3554         goto done;
3555       }
3556
3557  done:
3558   VEC_free (basic_block, heap, dom);
3559   return res;
3560 }
3561
3562 /* Record all conditions from SCOP.
3563
3564    Returns false when the conditions contain scalar computations that
3565    depend on the condition, i.e. when there are scalar phi nodes on
3566    the junction after the condition.  Only the computations occurring
3567    on memory can be handled in the polyhedral model: operations that
3568    define scalar evolutions in conditions, that can potentially be
3569    used to index memory, can't be handled by the polyhedral model.  */
3570
3571 static bool
3572 build_scop_conditions (scop_p scop)
3573 {
3574   bool res;
3575   VEC (gimple, heap) *conditions = NULL;
3576   VEC (gimple, heap) *cases = NULL;
3577
3578   res = build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop);
3579
3580   VEC_free (gimple, heap, conditions);
3581   VEC_free (gimple, heap, cases);
3582   return res;
3583 }
3584
3585 /* Traverses all the GBBs of the SCOP and add their constraints to the
3586    iteration domains.  */
3587
3588 static void
3589 add_conditions_to_constraints (scop_p scop)
3590 {
3591   int i;
3592   graphite_bb_p gbb;
3593
3594   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
3595     add_conditions_to_domain (gbb);
3596 }
3597
3598 /* Build the current domain matrix: the loops belonging to the current
3599    SCOP, and that vary for the execution of the current basic block.
3600    Returns false if there is no loop in SCOP.  */
3601
3602 static bool
3603 build_scop_iteration_domain (scop_p scop)
3604 {
3605   struct loop *loop;
3606   CloogMatrix *outer_cstr;
3607   int i;
3608
3609   /* Build cloog loop for all loops, that are in the uppermost loop layer of
3610      this SCoP.  */
3611   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
3612     if (!loop_in_sese_p (loop_outer (loop), SCOP_REGION (scop)))
3613       {
3614         /* The outermost constraints is a matrix that has:
3615            -first column: eq/ineq boolean
3616            -last column: a constant
3617            -scop_nb_params columns for the parameters used in the scop.  */
3618         outer_cstr = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
3619         build_loop_iteration_domains (scop, loop, outer_cstr, 0);
3620         cloog_matrix_free (outer_cstr);
3621       }
3622
3623   return (i != 0);
3624 }
3625
3626 /* Initializes an equation CY of the access matrix using the
3627    information for a subscript from AF, relatively to the loop
3628    indexes from LOOP_NEST and parameter indexes from PARAMS.  NDIM is
3629    the dimension of the array access, i.e. the number of
3630    subscripts.  Returns true when the operation succeeds.  */
3631
3632 static bool
3633 build_access_matrix_with_af (tree af, lambda_vector cy,
3634                              scop_p scop, int ndim)
3635 {
3636   int param_col;
3637
3638   switch (TREE_CODE (af))
3639     {
3640     case POLYNOMIAL_CHREC:
3641       {
3642         struct loop *outer_loop;
3643         tree left = CHREC_LEFT (af);
3644         tree right = CHREC_RIGHT (af);
3645         int var;
3646
3647         if (TREE_CODE (right) != INTEGER_CST)
3648           return false;
3649
3650         outer_loop = get_loop (CHREC_VARIABLE (af));
3651         var = nb_loops_around_loop_in_scop (outer_loop, scop);
3652         cy[var] = int_cst_value (right);
3653
3654         switch (TREE_CODE (left))
3655           {
3656           case POLYNOMIAL_CHREC:
3657             return build_access_matrix_with_af (left, cy, scop, ndim);
3658
3659           case INTEGER_CST:
3660             cy[ndim - 1] = int_cst_value (left);
3661             return true;
3662
3663           default:
3664             return build_access_matrix_with_af (left, cy, scop, ndim);
3665           }
3666       }
3667
3668     case PLUS_EXPR:
3669       build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3670       build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3671       return true;
3672       
3673     case MINUS_EXPR:
3674       build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3675       build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3676       return true;
3677
3678     case INTEGER_CST:
3679       cy[ndim - 1] = int_cst_value (af);
3680       return true;
3681
3682     case SSA_NAME:
3683       param_col = param_index (af, scop);      
3684       cy [ndim - scop_nb_params (scop) + param_col - 1] = 1; 
3685       return true;
3686
3687     default:
3688       /* FIXME: access_fn can have parameters.  */
3689       return false;
3690     }
3691 }
3692
3693 /* Initialize the access matrix in the data reference REF with respect
3694    to the loop nesting LOOP_NEST.  Return true when the operation
3695    succeeded.  */
3696
3697 static bool
3698 build_access_matrix (data_reference_p ref, graphite_bb_p gb)
3699 {