OSDN Git Service

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