OSDN Git Service

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