OSDN Git Service

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