OSDN Git Service

1dea7fdda30621f11143f46e353e7c31748ff1d5
[pf3gnuchains/gcc-fork.git] / gcc / graphite-sese-to-poly.c
1 /* Conversion of SESE regions to Polyhedra.
2    Copyright (C) 2009 Free Software Foundation, Inc.
3    Contributed by Sebastian Pop <sebastian.pop@amd.com>.
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 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "ggc.h"
26 #include "tree.h"
27 #include "rtl.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-flow.h"
31 #include "toplev.h"
32 #include "tree-dump.h"
33 #include "timevar.h"
34 #include "cfgloop.h"
35 #include "tree-chrec.h"
36 #include "tree-data-ref.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-pass.h"
39 #include "domwalk.h"
40 #include "value-prof.h"
41 #include "pointer-set.h"
42 #include "gimple.h"
43 #include "sese.h"
44
45 #ifdef HAVE_cloog
46 #include "cloog/cloog.h"
47 #include "ppl_c.h"
48 #include "graphite-ppl.h"
49 #include "graphite.h"
50 #include "graphite-poly.h"
51 #include "graphite-scop-detection.h"
52 #include "graphite-clast-to-gimple.h"
53 #include "graphite-sese-to-poly.h"
54
55 /* Check if VAR is used in a phi node, that is no loop header.  */
56
57 static bool
58 var_used_in_not_loop_header_phi_node (tree var)
59 {
60   imm_use_iterator imm_iter;
61   gimple stmt;
62   bool result = false;
63
64   FOR_EACH_IMM_USE_STMT (stmt, imm_iter, var)
65     {
66       basic_block bb = gimple_bb (stmt);
67
68       if (gimple_code (stmt) == GIMPLE_PHI
69           && bb->loop_father->header != bb)
70         result = true;
71     }
72
73   return result;
74 }
75
76 /* Returns the index of the phi argument corresponding to the initial
77    value in the loop.  */
78
79 static size_t
80 loop_entry_phi_arg (gimple phi)
81 {
82   loop_p loop = gimple_bb (phi)->loop_father;
83   size_t i;
84
85   for (i = 0; i < gimple_phi_num_args (phi); i++)
86     if (!flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, i)->src))
87       return i;
88
89   gcc_unreachable ();
90   return 0;
91 }
92
93 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
94    PSI by inserting on the loop ENTRY edge assignment "RES = INIT".  */
95
96 static void
97 remove_simple_copy_phi (gimple_stmt_iterator *psi)
98 {
99   gimple phi = gsi_stmt (*psi);
100   tree res = gimple_phi_result (phi);
101   size_t entry = loop_entry_phi_arg (phi);
102   tree init = gimple_phi_arg_def (phi, entry);
103   gimple stmt = gimple_build_assign (res, init);
104   edge e = gimple_phi_arg_edge (phi, entry);
105
106   remove_phi_node (psi, false);
107   gsi_insert_on_edge_immediate (e, stmt);
108   SSA_NAME_DEF_STMT (res) = stmt;
109 }
110
111 /* Removes an invariant phi node at position PSI by inserting on the
112    loop ENTRY edge the assignment RES = INIT.  */
113
114 static void
115 remove_invariant_phi (sese region, gimple_stmt_iterator *psi)
116 {
117   gimple phi = gsi_stmt (*psi);
118   loop_p loop = loop_containing_stmt (phi);
119   tree res = gimple_phi_result (phi);
120   tree scev = scalar_evolution_in_region (region, loop, res);
121   size_t entry = loop_entry_phi_arg (phi);
122   edge e = gimple_phi_arg_edge (phi, entry);
123   tree var;
124   gimple stmt;
125   gimple_seq stmts;
126   gimple_stmt_iterator gsi;
127
128   if (tree_contains_chrecs (scev, NULL))
129     scev = gimple_phi_arg_def (phi, entry);
130
131   var = force_gimple_operand (scev, &stmts, true, NULL_TREE);
132   stmt = gimple_build_assign (res, var);
133   remove_phi_node (psi, false);
134
135   if (!stmts)
136     stmts = gimple_seq_alloc ();
137
138   gsi = gsi_last (stmts);
139   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
140   gsi_insert_seq_on_edge (e, stmts);
141   gsi_commit_edge_inserts ();
142   SSA_NAME_DEF_STMT (res) = stmt;
143 }
144
145 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)".  */
146
147 static inline bool
148 simple_copy_phi_p (gimple phi)
149 {
150   tree res;
151
152   if (gimple_phi_num_args (phi) != 2)
153     return false;
154
155   res = gimple_phi_result (phi);
156   return (res == gimple_phi_arg_def (phi, 0)
157           || res == gimple_phi_arg_def (phi, 1));
158 }
159
160 /* Returns true when the phi node at position PSI is a reduction phi
161    node in REGION.  Otherwise moves the pointer PSI to the next phi to
162    be considered.  */
163
164 static bool
165 reduction_phi_p (sese region, gimple_stmt_iterator *psi)
166 {
167   loop_p loop;
168   tree scev;
169   affine_iv iv;
170   gimple phi = gsi_stmt (*psi);
171   tree res = gimple_phi_result (phi);
172
173   if (!is_gimple_reg (res))
174     {
175       gsi_next (psi);
176       return false;
177     }
178
179   loop = loop_containing_stmt (phi);
180
181   if (simple_copy_phi_p (phi))
182     {
183       /* FIXME: PRE introduces phi nodes like these, for an example,
184          see id-5.f in the fortran graphite testsuite:
185
186          # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
187       */
188       remove_simple_copy_phi (psi);
189       return false;
190     }
191
192   /* Main induction variables with constant strides in LOOP are not
193      reductions.  */
194   if (simple_iv (loop, loop, res, &iv, true))
195     {
196       if (integer_zerop (iv.step))
197         remove_invariant_phi (region, psi);
198       else
199         gsi_next (psi);
200
201       return false;
202     }
203
204   scev = scalar_evolution_in_region (region, loop, res);
205   if (chrec_contains_undetermined (scev))
206     return true;
207
208   if (evolution_function_is_invariant_p (scev, loop->num))
209     {
210       remove_invariant_phi (region, psi);
211       return false;
212     }
213
214   /* All the other cases are considered reductions.  */
215   return true;
216 }
217
218 /* Returns true when BB will be represented in graphite.  Return false
219    for the basic blocks that contain code eliminated in the code
220    generation pass: i.e. induction variables and exit conditions.  */
221
222 static bool
223 graphite_stmt_p (sese region, basic_block bb,
224                  VEC (data_reference_p, heap) *drs)
225 {
226   gimple_stmt_iterator gsi;
227   loop_p loop = bb->loop_father;
228
229   if (VEC_length (data_reference_p, drs) > 0)
230     return true;
231
232   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
233     {
234       gimple stmt = gsi_stmt (gsi);
235
236       switch (gimple_code (stmt))
237         {
238         case GIMPLE_DEBUG:
239           /* Control flow expressions can be ignored, as they are
240              represented in the iteration domains and will be
241              regenerated by graphite.  */
242         case GIMPLE_COND:
243         case GIMPLE_GOTO:
244         case GIMPLE_SWITCH:
245           break;
246
247         case GIMPLE_ASSIGN:
248           {
249             tree var = gimple_assign_lhs (stmt);
250
251             /* We need these bbs to be able to construct the phi nodes.  */
252             if (var_used_in_not_loop_header_phi_node (var))
253               return true;
254
255             var = scalar_evolution_in_region (region, loop, var);
256             if (chrec_contains_undetermined (var))
257               return true;
258
259             break;
260           }
261
262         default:
263           return true;
264         }
265     }
266
267   return false;
268 }
269
270 /* Store the GRAPHITE representation of BB.  */
271
272 static gimple_bb_p
273 new_gimple_bb (basic_block bb, VEC (data_reference_p, heap) *drs)
274 {
275   struct gimple_bb *gbb;
276
277   gbb = XNEW (struct gimple_bb);
278   bb->aux = gbb;
279   GBB_BB (gbb) = bb;
280   GBB_DATA_REFS (gbb) = drs;
281   GBB_CONDITIONS (gbb) = NULL;
282   GBB_CONDITION_CASES (gbb) = NULL;
283   GBB_CLOOG_IV_TYPES (gbb) = NULL;
284
285   return gbb;
286 }
287
288 static void
289 free_data_refs_aux (VEC (data_reference_p, heap) *datarefs)
290 {
291   unsigned int i;
292   struct data_reference *dr;
293
294   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
295     if (!dr->aux)
296       {
297         free (dr->aux);
298         dr->aux = NULL;
299       }
300 }
301
302 /* Frees GBB.  */
303
304 static void
305 free_gimple_bb (struct gimple_bb *gbb)
306 {
307   if (GBB_CLOOG_IV_TYPES (gbb))
308     htab_delete (GBB_CLOOG_IV_TYPES (gbb));
309
310   free_data_refs_aux (GBB_DATA_REFS (gbb));
311   free_data_refs (GBB_DATA_REFS (gbb));
312
313   VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
314   VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
315   GBB_BB (gbb)->aux = 0;
316   XDELETE (gbb);
317 }
318
319 /* Deletes all gimple bbs in SCOP.  */
320
321 static void
322 remove_gbbs_in_scop (scop_p scop)
323 {
324   int i;
325   poly_bb_p pbb;
326
327   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
328     free_gimple_bb (PBB_BLACK_BOX (pbb));
329 }
330
331 /* Deletes all scops in SCOPS.  */
332
333 void
334 free_scops (VEC (scop_p, heap) *scops)
335 {
336   int i;
337   scop_p scop;
338
339   for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
340     {
341       remove_gbbs_in_scop (scop);
342       free_sese (SCOP_REGION (scop));
343       free_scop (scop);
344     }
345
346   VEC_free (scop_p, heap, scops);
347 }
348
349 /* Generates a polyhedral black box only if the bb contains interesting
350    information.  */
351
352 static void
353 try_generate_gimple_bb (scop_p scop, basic_block bb, sbitmap reductions)
354 {
355   VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
356   loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
357   gimple_stmt_iterator gsi;
358
359   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
360     {
361       gimple stmt = gsi_stmt (gsi);
362       if (!is_gimple_debug (stmt))
363         graphite_find_data_references_in_stmt (nest, stmt, &drs);
364     }
365
366   if (!graphite_stmt_p (SCOP_REGION (scop), bb, drs))
367     free_data_refs (drs);
368   else
369     new_poly_bb (scop, new_gimple_bb (bb, drs), TEST_BIT (reductions,
370                                                           bb->index));
371 }
372
373 /* Returns true if all predecessors of BB, that are not dominated by BB, are
374    marked in MAP.  The predecessors dominated by BB are loop latches and will
375    be handled after BB.  */
376
377 static bool
378 all_non_dominated_preds_marked_p (basic_block bb, sbitmap map)
379 {
380   edge e;
381   edge_iterator ei;
382
383   FOR_EACH_EDGE (e, ei, bb->preds)
384     if (!TEST_BIT (map, e->src->index)
385         && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
386         return false;
387
388   return true;
389 }
390
391 /* Compare the depth of two basic_block's P1 and P2.  */
392
393 static int
394 compare_bb_depths (const void *p1, const void *p2)
395 {
396   const_basic_block const bb1 = *(const_basic_block const*)p1;
397   const_basic_block const bb2 = *(const_basic_block const*)p2;
398   int d1 = loop_depth (bb1->loop_father);
399   int d2 = loop_depth (bb2->loop_father);
400
401   if (d1 < d2)
402     return 1;
403
404   if (d1 > d2)
405     return -1;
406
407   return 0;
408 }
409
410 /* Sort the basic blocks from DOM such that the first are the ones at
411    a deepest loop level.  */
412
413 static void
414 graphite_sort_dominated_info (VEC (basic_block, heap) *dom)
415 {
416   size_t len = VEC_length (basic_block, dom);
417
418   qsort (VEC_address (basic_block, dom), len, sizeof (basic_block),
419          compare_bb_depths);
420 }
421
422 /* Recursive helper function for build_scops_bbs.  */
423
424 static void
425 build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb, sbitmap reductions)
426 {
427   sese region = SCOP_REGION (scop);
428   VEC (basic_block, heap) *dom;
429
430   if (TEST_BIT (visited, bb->index)
431       || !bb_in_sese_p (bb, region))
432     return;
433
434   try_generate_gimple_bb (scop, bb, reductions);
435   SET_BIT (visited, bb->index);
436
437   dom = get_dominated_by (CDI_DOMINATORS, bb);
438
439   if (dom == NULL)
440     return;
441
442   graphite_sort_dominated_info (dom);
443
444   while (!VEC_empty (basic_block, dom))
445     {
446       int i;
447       basic_block dom_bb;
448
449       for (i = 0; VEC_iterate (basic_block, dom, i, dom_bb); i++)
450         if (all_non_dominated_preds_marked_p (dom_bb, visited))
451           {
452             build_scop_bbs_1 (scop, visited, dom_bb, reductions);
453             VEC_unordered_remove (basic_block, dom, i);
454             break;
455           }
456     }
457
458   VEC_free (basic_block, heap, dom);
459 }
460
461 /* Gather the basic blocks belonging to the SCOP.  */
462
463 static void
464 build_scop_bbs (scop_p scop, sbitmap reductions)
465 {
466   sbitmap visited = sbitmap_alloc (last_basic_block);
467   sese region = SCOP_REGION (scop);
468
469   sbitmap_zero (visited);
470   build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region), reductions);
471   sbitmap_free (visited);
472 }
473
474 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
475    We generate SCATTERING_DIMENSIONS scattering dimensions.
476
477    CLooG 0.15.0 and previous versions require, that all
478    scattering functions of one CloogProgram have the same number of
479    scattering dimensions, therefore we allow to specify it.  This
480    should be removed in future versions of CLooG.
481
482    The scattering polyhedron consists of these dimensions: scattering,
483    loop_iterators, parameters.
484
485    Example:
486
487    | scattering_dimensions = 5
488    | used_scattering_dimensions = 3
489    | nb_iterators = 1
490    | scop_nb_params = 2
491    |
492    | Schedule:
493    |   i
494    | 4 5
495    |
496    | Scattering polyhedron:
497    |
498    | scattering: {s1, s2, s3, s4, s5}
499    | loop_iterators: {i}
500    | parameters: {p1, p2}
501    |
502    | s1  s2  s3  s4  s5  i   p1  p2  1
503    | 1   0   0   0   0   0   0   0  -4  = 0
504    | 0   1   0   0   0  -1   0   0   0  = 0
505    | 0   0   1   0   0   0   0   0  -5  = 0  */
506
507 static void
508 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule,
509                                   poly_bb_p pbb, int scattering_dimensions)
510 {
511   int i;
512   scop_p scop = PBB_SCOP (pbb);
513   int nb_iterators = pbb_dim_iter_domain (pbb);
514   int used_scattering_dimensions = nb_iterators * 2 + 1;
515   int nb_params = scop_nb_params (scop);
516   ppl_Coefficient_t c;
517   ppl_dimension_type dim = scattering_dimensions + nb_iterators + nb_params;
518   Value v;
519
520   gcc_assert (scattering_dimensions >= used_scattering_dimensions);
521
522   value_init (v);
523   ppl_new_Coefficient (&c);
524   PBB_TRANSFORMED (pbb) = poly_scattering_new ();
525   ppl_new_C_Polyhedron_from_space_dimension
526     (&PBB_TRANSFORMED_SCATTERING (pbb), dim, 0);
527
528   PBB_NB_SCATTERING_TRANSFORM (pbb) = scattering_dimensions;
529
530   for (i = 0; i < scattering_dimensions; i++)
531     {
532       ppl_Constraint_t cstr;
533       ppl_Linear_Expression_t expr;
534
535       ppl_new_Linear_Expression_with_dimension (&expr, dim);
536       value_set_si (v, 1);
537       ppl_assign_Coefficient_from_mpz_t (c, v);
538       ppl_Linear_Expression_add_to_coefficient (expr, i, c);
539
540       /* Textual order inside this loop.  */
541       if ((i % 2) == 0)
542         {
543           ppl_Linear_Expression_coefficient (static_schedule, i / 2, c);
544           ppl_Coefficient_to_mpz_t (c, v);
545           value_oppose (v, v);
546           ppl_assign_Coefficient_from_mpz_t (c, v);
547           ppl_Linear_Expression_add_to_inhomogeneous (expr, c);
548         }
549
550       /* Iterations of this loop.  */
551       else /* if ((i % 2) == 1) */
552         {
553           int loop = (i - 1) / 2;
554
555           value_set_si (v, -1);
556           ppl_assign_Coefficient_from_mpz_t (c, v);
557           ppl_Linear_Expression_add_to_coefficient
558             (expr, scattering_dimensions + loop, c);
559         }
560
561       ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
562       ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
563       ppl_delete_Linear_Expression (expr);
564       ppl_delete_Constraint (cstr);
565     }
566
567   value_clear (v);
568   ppl_delete_Coefficient (c);
569
570   PBB_ORIGINAL (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
571 }
572
573 /* Build for BB the static schedule.
574
575    The static schedule is a Dewey numbering of the abstract syntax
576    tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
577
578    The following example informally defines the static schedule:
579
580    A
581    for (i: ...)
582      {
583        for (j: ...)
584          {
585            B
586            C
587          }
588
589        for (k: ...)
590          {
591            D
592            E
593          }
594      }
595    F
596
597    Static schedules for A to F:
598
599      DEPTH
600      0 1 2
601    A 0
602    B 1 0 0
603    C 1 0 1
604    D 1 1 0
605    E 1 1 1
606    F 2
607 */
608
609 static void
610 build_scop_scattering (scop_p scop)
611 {
612   int i;
613   poly_bb_p pbb;
614   gimple_bb_p previous_gbb = NULL;
615   ppl_Linear_Expression_t static_schedule;
616   ppl_Coefficient_t c;
617   Value v;
618
619   value_init (v);
620   ppl_new_Coefficient (&c);
621   ppl_new_Linear_Expression (&static_schedule);
622
623   /* We have to start schedules at 0 on the first component and
624      because we cannot compare_prefix_loops against a previous loop,
625      prefix will be equal to zero, and that index will be
626      incremented before copying.  */
627   value_set_si (v, -1);
628   ppl_assign_Coefficient_from_mpz_t (c, v);
629   ppl_Linear_Expression_add_to_coefficient (static_schedule, 0, c);
630
631   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
632     {
633       gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
634       ppl_Linear_Expression_t common;
635       int prefix;
636       int nb_scat_dims = pbb_dim_iter_domain (pbb) * 2 + 1;
637
638       if (previous_gbb)
639         prefix = nb_common_loops (SCOP_REGION (scop), previous_gbb, gbb);
640       else
641         prefix = 0;
642
643       previous_gbb = gbb;
644       ppl_new_Linear_Expression_with_dimension (&common, prefix + 1);
645       ppl_assign_Linear_Expression_from_Linear_Expression (common,
646                                                            static_schedule);
647
648       value_set_si (v, 1);
649       ppl_assign_Coefficient_from_mpz_t (c, v);
650       ppl_Linear_Expression_add_to_coefficient (common, prefix, c);
651       ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule,
652                                                            common);
653
654       build_pbb_scattering_polyhedrons (common, pbb, nb_scat_dims);
655
656       ppl_delete_Linear_Expression (common);
657     }
658
659   value_clear (v);
660   ppl_delete_Coefficient (c);
661   ppl_delete_Linear_Expression (static_schedule);
662 }
663
664 /* Add the value K to the dimension D of the linear expression EXPR.  */
665
666 static void
667 add_value_to_dim (ppl_dimension_type d, ppl_Linear_Expression_t expr,
668                   Value k)
669 {
670   Value val;
671   ppl_Coefficient_t coef;
672
673   ppl_new_Coefficient (&coef);
674   ppl_Linear_Expression_coefficient (expr, d, coef);
675   value_init (val);
676   ppl_Coefficient_to_mpz_t (coef, val);
677
678   value_addto (val, val, k);
679
680   ppl_assign_Coefficient_from_mpz_t (coef, val);
681   ppl_Linear_Expression_add_to_coefficient (expr, d, coef);
682   value_clear (val);
683   ppl_delete_Coefficient (coef);
684 }
685
686 /* In the context of scop S, scan E, the right hand side of a scalar
687    evolution function in loop VAR, and translate it to a linear
688    expression EXPR.  */
689
690 static void
691 scan_tree_for_params_right_scev (sese s, tree e, int var,
692                                  ppl_Linear_Expression_t expr)
693 {
694   if (expr)
695     {
696       loop_p loop = get_loop (var);
697       ppl_dimension_type l = sese_loop_depth (s, loop) - 1;
698       Value val;
699
700       /* Scalar evolutions should happen in the sese region.  */
701       gcc_assert (sese_loop_depth (s, loop) > 0);
702
703       /* We can not deal with parametric strides like:
704
705       | p = parameter;
706       |
707       | for i:
708       |   a [i * p] = ...   */
709       gcc_assert (TREE_CODE (e) == INTEGER_CST);
710
711       value_init (val);
712       value_set_si (val, int_cst_value (e));
713       add_value_to_dim (l, expr, val);
714       value_clear (val);
715     }
716 }
717
718 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
719    linear expression EXPR.  K is the multiplier of the constant.  */
720
721 static void
722 scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, Value k)
723 {
724   Value val;
725   ppl_Coefficient_t coef;
726   int v = int_cst_value (cst);
727
728   value_init (val);
729   value_set_si (val, 0);
730
731   /* Necessary to not get "-1 = 2^n - 1". */
732   if (v < 0)
733     value_sub_int (val, val, -v);
734   else
735     value_add_int (val, val, v);
736
737   value_multiply (val, val, k);
738   ppl_new_Coefficient (&coef);
739   ppl_assign_Coefficient_from_mpz_t (coef, val);
740   ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
741   value_clear (val);
742   ppl_delete_Coefficient (coef);
743 }
744
745 /* Saves in NV at index I a new name for variable P.  */
746
747 static void
748 save_var_name (char **nv, int i, tree p)
749 {
750   const char *name = get_name (SSA_NAME_VAR (p));
751
752   if (name)
753     {
754       int len = strlen (name) + 16;
755       nv[i] = XNEWVEC (char, len);
756       snprintf (nv[i], len, "%s_%d", name, SSA_NAME_VERSION (p));
757     }
758   else
759     {
760       nv[i] = XNEWVEC (char, 16);
761       snprintf (nv[i], 2 + 16, "T_%d", SSA_NAME_VERSION (p));
762     }
763 }
764
765 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
766    Otherwise returns -1.  */
767
768 static inline int
769 parameter_index_in_region_1 (tree name, sese region)
770 {
771   int i;
772   tree p;
773
774   gcc_assert (TREE_CODE (name) == SSA_NAME);
775
776   for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++)
777     if (p == name)
778       return i;
779
780   return -1;
781 }
782
783 /* When the parameter NAME is in REGION, returns its index in
784    SESE_PARAMS.  Otherwise this function inserts NAME in SESE_PARAMS
785    and returns the index of NAME.  */
786
787 static int
788 parameter_index_in_region (tree name, sese region)
789 {
790   int i;
791
792   gcc_assert (TREE_CODE (name) == SSA_NAME);
793
794   i = parameter_index_in_region_1 (name, region);
795   if (i != -1)
796     return i;
797
798   gcc_assert (SESE_ADD_PARAMS (region));
799
800   i = VEC_length (tree, SESE_PARAMS (region));
801   save_var_name (SESE_PARAMS_NAMES (region), i, name);
802   save_clast_name_index (SESE_PARAMS_INDEX (region),
803                          SESE_PARAMS_NAMES (region)[i], i);
804   VEC_safe_push (tree, heap, SESE_PARAMS (region), name);
805   return i;
806 }
807
808 /* In the context of sese S, scan the expression E and translate it to
809    a linear expression C.  When parsing a symbolic multiplication, K
810    represents the constant multiplier of an expression containing
811    parameters.  */
812
813 static void
814 scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c,
815                       Value k)
816 {
817   if (e == chrec_dont_know)
818     return;
819
820   switch (TREE_CODE (e))
821     {
822     case POLYNOMIAL_CHREC:
823       scan_tree_for_params_right_scev (s, CHREC_RIGHT (e),
824                                        CHREC_VARIABLE (e), c);
825       scan_tree_for_params (s, CHREC_LEFT (e), c, k);
826       break;
827
828     case MULT_EXPR:
829       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
830         {
831           if (c)
832             {
833               Value val;
834               gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
835               value_init (val);
836               value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
837               value_multiply (val, val, k);
838               scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val);
839               value_clear (val);
840             }
841           else
842             scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
843         }
844       else
845         {
846           if (c)
847             {
848               Value val;
849               gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
850               value_init (val);
851               value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
852               value_multiply (val, val, k);
853               scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val);
854               value_clear (val);
855             }
856           else
857             scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
858         }
859       break;
860
861     case PLUS_EXPR:
862     case POINTER_PLUS_EXPR:
863       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
864       scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
865       break;
866
867     case MINUS_EXPR:
868       {
869         ppl_Linear_Expression_t tmp_expr = NULL;
870
871         if (c)
872           {
873             ppl_dimension_type dim;
874             ppl_Linear_Expression_space_dimension (c, &dim);
875             ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
876           }
877
878         scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
879         scan_tree_for_params (s, TREE_OPERAND (e, 1), tmp_expr, k);
880
881         if (c)
882           {
883             ppl_subtract_Linear_Expression_from_Linear_Expression (c,
884                                                                    tmp_expr);
885             ppl_delete_Linear_Expression (tmp_expr);
886           }
887
888         break;
889       }
890
891     case NEGATE_EXPR:
892       {
893         ppl_Linear_Expression_t tmp_expr = NULL;
894
895         if (c)
896           {
897             ppl_dimension_type dim;
898             ppl_Linear_Expression_space_dimension (c, &dim);
899             ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
900           }
901
902         scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
903
904         if (c)
905           {
906             ppl_subtract_Linear_Expression_from_Linear_Expression (c,
907                                                                    tmp_expr);
908             ppl_delete_Linear_Expression (tmp_expr);
909           }
910
911         break;
912       }
913
914     case BIT_NOT_EXPR:
915       {
916         ppl_Linear_Expression_t tmp_expr = NULL;
917
918         if (c)
919           {
920             ppl_dimension_type dim;
921             ppl_Linear_Expression_space_dimension (c, &dim);
922             ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
923           }
924
925         scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
926
927         if (c)
928           {
929             ppl_Coefficient_t coef;
930             Value minus_one;
931
932             ppl_subtract_Linear_Expression_from_Linear_Expression (c,
933                                                                    tmp_expr);
934             ppl_delete_Linear_Expression (tmp_expr);
935             value_init (minus_one);
936             value_set_si (minus_one, -1);
937             ppl_new_Coefficient_from_mpz_t (&coef, minus_one);
938             ppl_Linear_Expression_add_to_inhomogeneous (c, coef);
939             value_clear (minus_one);
940             ppl_delete_Coefficient (coef);
941           }
942
943         break;
944       }
945
946     case SSA_NAME:
947       {
948         ppl_dimension_type p = parameter_index_in_region (e, s);
949
950         if (c)
951           {
952             ppl_dimension_type dim;
953             ppl_Linear_Expression_space_dimension (c, &dim);
954             p += dim - sese_nb_params (s);
955             add_value_to_dim (p, c, k);
956           }
957         break;
958       }
959
960     case INTEGER_CST:
961       if (c)
962         scan_tree_for_params_int (e, c, k);
963       break;
964
965     CASE_CONVERT:
966     case NON_LVALUE_EXPR:
967       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
968       break;
969
970    default:
971       gcc_unreachable ();
972       break;
973     }
974 }
975
976 /* Find parameters with respect to REGION in BB. We are looking in memory
977    access functions, conditions and loop bounds.  */
978
979 static void
980 find_params_in_bb (sese region, gimple_bb_p gbb)
981 {
982   int i;
983   unsigned j;
984   data_reference_p dr;
985   gimple stmt;
986   loop_p loop = GBB_BB (gbb)->loop_father;
987   Value one;
988
989   value_init (one);
990   value_set_si (one, 1);
991
992   /* Find parameters in the access functions of data references.  */
993   for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gbb), i, dr); i++)
994     for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
995       scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one);
996
997   /* Find parameters in conditional statements.  */
998   for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gbb), i, stmt); i++)
999     {
1000       tree lhs = scalar_evolution_in_region (region, loop,
1001                                              gimple_cond_lhs (stmt));
1002       tree rhs = scalar_evolution_in_region (region, loop,
1003                                              gimple_cond_rhs (stmt));
1004
1005       scan_tree_for_params (region, lhs, NULL, one);
1006       scan_tree_for_params (region, rhs, NULL, one);
1007     }
1008
1009   value_clear (one);
1010 }
1011
1012 /* Record the parameters used in the SCOP.  A variable is a parameter
1013    in a scop if it does not vary during the execution of that scop.  */
1014
1015 static void
1016 find_scop_parameters (scop_p scop)
1017 {
1018   poly_bb_p pbb;
1019   unsigned i;
1020   sese region = SCOP_REGION (scop);
1021   struct loop *loop;
1022   Value one;
1023
1024   value_init (one);
1025   value_set_si (one, 1);
1026
1027   /* Find the parameters used in the loop bounds.  */
1028   for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1029     {
1030       tree nb_iters = number_of_latch_executions (loop);
1031
1032       if (!chrec_contains_symbols (nb_iters))
1033         continue;
1034
1035       nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1036       scan_tree_for_params (region, nb_iters, NULL, one);
1037     }
1038
1039   value_clear (one);
1040
1041   /* Find the parameters used in data accesses.  */
1042   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1043     find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1044
1045   scop_set_nb_params (scop, sese_nb_params (region));
1046   SESE_ADD_PARAMS (region) = false;
1047 }
1048
1049 /* Returns a gimple_bb from BB.  */
1050
1051 static inline gimple_bb_p
1052 gbb_from_bb (basic_block bb)
1053 {
1054   return (gimple_bb_p) bb->aux;
1055 }
1056
1057 /* Builds the constraint polyhedra for LOOP in SCOP.  OUTER_PH gives
1058    the constraints for the surrounding loops.  */
1059
1060 static void
1061 build_loop_iteration_domains (scop_p scop, struct loop *loop,
1062                               ppl_Polyhedron_t outer_ph, int nb)
1063
1064 {
1065   int i;
1066   ppl_Polyhedron_t ph;
1067   tree nb_iters = number_of_latch_executions (loop);
1068   ppl_dimension_type dim = nb + 1 + scop_nb_params (scop);
1069   sese region = SCOP_REGION (scop);
1070
1071   {
1072     ppl_const_Constraint_System_t pcs;
1073     ppl_dimension_type *map
1074       = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
1075
1076     ppl_new_C_Polyhedron_from_space_dimension (&ph, dim, 0);
1077     ppl_Polyhedron_get_constraints (outer_ph, &pcs);
1078     ppl_Polyhedron_add_constraints (ph, pcs);
1079
1080     for (i = 0; i < (int) nb; i++)
1081       map[i] = i;
1082     for (i = (int) nb; i < (int) dim - 1; i++)
1083       map[i] = i + 1;
1084     map[dim - 1] = nb;
1085
1086     ppl_Polyhedron_map_space_dimensions (ph, map, dim);
1087     free (map);
1088   }
1089
1090   /* 0 <= loop_i */
1091   {
1092     ppl_Constraint_t lb;
1093     ppl_Linear_Expression_t lb_expr;
1094
1095     ppl_new_Linear_Expression_with_dimension (&lb_expr, dim);
1096     ppl_set_coef (lb_expr, nb, 1);
1097     ppl_new_Constraint (&lb, lb_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1098     ppl_delete_Linear_Expression (lb_expr);
1099     ppl_Polyhedron_add_constraint (ph, lb);
1100     ppl_delete_Constraint (lb);
1101   }
1102
1103   if (TREE_CODE (nb_iters) == INTEGER_CST)
1104     {
1105       ppl_Constraint_t ub;
1106       ppl_Linear_Expression_t ub_expr;
1107
1108       ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1109
1110       /* loop_i <= cst_nb_iters */
1111       ppl_set_coef (ub_expr, nb, -1);
1112       ppl_set_inhomogeneous_tree (ub_expr, nb_iters);
1113       ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1114       ppl_Polyhedron_add_constraint (ph, ub);
1115       ppl_delete_Linear_Expression (ub_expr);
1116       ppl_delete_Constraint (ub);
1117     }
1118   else if (!chrec_contains_undetermined (nb_iters))
1119     {
1120       Value one;
1121       ppl_Constraint_t ub;
1122       ppl_Linear_Expression_t ub_expr;
1123
1124       value_init (one);
1125       value_set_si (one, 1);
1126       ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1127       nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1128       scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one);
1129       value_clear (one);
1130
1131       /* loop_i <= expr_nb_iters */
1132       ppl_set_coef (ub_expr, nb, -1);
1133       ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1134       ppl_Polyhedron_add_constraint (ph, ub);
1135       ppl_delete_Linear_Expression (ub_expr);
1136       ppl_delete_Constraint (ub);
1137     }
1138   else
1139     gcc_unreachable ();
1140
1141   if (loop->inner && loop_in_sese_p (loop->inner, region))
1142     build_loop_iteration_domains (scop, loop->inner, ph, nb + 1);
1143
1144   if (nb != 0
1145       && loop->next
1146       && loop_in_sese_p (loop->next, region))
1147     build_loop_iteration_domains (scop, loop->next, outer_ph, nb);
1148
1149   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1150     ((ppl_Pointset_Powerset_C_Polyhedron_t *) &loop->aux, ph);
1151
1152   ppl_delete_Polyhedron (ph);
1153 }
1154
1155 /* Returns a linear expression for tree T evaluated in PBB.  */
1156
1157 static ppl_Linear_Expression_t
1158 create_linear_expr_from_tree (poly_bb_p pbb, tree t)
1159 {
1160   Value one;
1161   ppl_Linear_Expression_t res;
1162   ppl_dimension_type dim;
1163   sese region = SCOP_REGION (PBB_SCOP (pbb));
1164   loop_p loop = pbb_loop (pbb);
1165
1166   dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
1167   ppl_new_Linear_Expression_with_dimension (&res, dim);
1168
1169   t = scalar_evolution_in_region (region, loop, t);
1170   gcc_assert (!automatically_generated_chrec_p (t));
1171
1172   value_init (one);
1173   value_set_si (one, 1);
1174   scan_tree_for_params (region, t, res, one);
1175   value_clear (one);
1176
1177   return res;
1178 }
1179
1180 /* Returns the ppl constraint type from the gimple tree code CODE.  */
1181
1182 static enum ppl_enum_Constraint_Type
1183 ppl_constraint_type_from_tree_code (enum tree_code code)
1184 {
1185   switch (code)
1186     {
1187     /* We do not support LT and GT to be able to work with C_Polyhedron.
1188        As we work on integer polyhedron "a < b" can be expressed by
1189        "a + 1 <= b".  */
1190     case LT_EXPR:
1191     case GT_EXPR:
1192       gcc_unreachable ();
1193
1194     case LE_EXPR:
1195       return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL;
1196
1197     case GE_EXPR:
1198       return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL;
1199
1200     case EQ_EXPR:
1201       return PPL_CONSTRAINT_TYPE_EQUAL;
1202
1203     default:
1204       gcc_unreachable ();
1205     }
1206 }
1207
1208 /* Add conditional statement STMT to PS.  It is evaluated in PBB and
1209    CODE is used as the comparison operator.  This allows us to invert the
1210    condition or to handle inequalities.  */
1211
1212 static void
1213 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt,
1214                          poly_bb_p pbb, enum tree_code code)
1215 {
1216   Value v;
1217   ppl_Coefficient_t c;
1218   ppl_Linear_Expression_t left, right;
1219   ppl_Constraint_t cstr;
1220   enum ppl_enum_Constraint_Type type;
1221
1222   left = create_linear_expr_from_tree (pbb, gimple_cond_lhs (stmt));
1223   right = create_linear_expr_from_tree (pbb, gimple_cond_rhs (stmt));
1224
1225   /* If we have < or > expressions convert them to <= or >= by adding 1 to
1226      the left or the right side of the expression. */
1227   if (code == LT_EXPR)
1228     {
1229       value_init (v);
1230       value_set_si (v, 1);
1231       ppl_new_Coefficient (&c);
1232       ppl_assign_Coefficient_from_mpz_t (c, v);
1233       ppl_Linear_Expression_add_to_inhomogeneous (left, c);
1234       ppl_delete_Coefficient (c);
1235       value_clear (v);
1236
1237       code = LE_EXPR;
1238     }
1239   else if (code == GT_EXPR)
1240     {
1241       value_init (v);
1242       value_set_si (v, 1);
1243       ppl_new_Coefficient (&c);
1244       ppl_assign_Coefficient_from_mpz_t (c, v);
1245       ppl_Linear_Expression_add_to_inhomogeneous (right, c);
1246       ppl_delete_Coefficient (c);
1247       value_clear (v);
1248
1249       code = GE_EXPR;
1250     }
1251
1252   type = ppl_constraint_type_from_tree_code (code);
1253
1254   ppl_subtract_Linear_Expression_from_Linear_Expression (left, right);
1255
1256   ppl_new_Constraint (&cstr, left, type);
1257   ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps, cstr);
1258
1259   ppl_delete_Constraint (cstr);
1260   ppl_delete_Linear_Expression (left);
1261   ppl_delete_Linear_Expression (right);
1262 }
1263
1264 /* Add conditional statement STMT to pbb.  CODE is used as the comparision
1265    operator.  This allows us to invert the condition or to handle
1266    inequalities.  */
1267
1268 static void
1269 add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
1270 {
1271   if (code == NE_EXPR)
1272     {
1273       ppl_Pointset_Powerset_C_Polyhedron_t left = PBB_DOMAIN (pbb);
1274       ppl_Pointset_Powerset_C_Polyhedron_t right;
1275       ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1276         (&right, left);
1277       add_condition_to_domain (left, stmt, pbb, LT_EXPR);
1278       add_condition_to_domain (right, stmt, pbb, GT_EXPR);
1279       ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left,
1280                                                                right);
1281       ppl_delete_Pointset_Powerset_C_Polyhedron (right);
1282     }
1283   else
1284     add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code);
1285 }
1286
1287 /* Add conditions to the domain of PBB.  */
1288
1289 static void
1290 add_conditions_to_domain (poly_bb_p pbb)
1291 {
1292   unsigned int i;
1293   gimple stmt;
1294   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1295   VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb);
1296
1297   if (VEC_empty (gimple, conditions))
1298     return;
1299
1300   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
1301     switch (gimple_code (stmt))
1302       {
1303       case GIMPLE_COND:
1304           {
1305             enum tree_code code = gimple_cond_code (stmt);
1306
1307             /* The conditions for ELSE-branches are inverted.  */
1308             if (VEC_index (gimple, gbb->condition_cases, i) == NULL)
1309               code = invert_tree_comparison (code, false);
1310
1311             add_condition_to_pbb (pbb, stmt, code);
1312             break;
1313           }
1314
1315       case GIMPLE_SWITCH:
1316         /* Switch statements are not supported right now - fall throught.  */
1317
1318       default:
1319         gcc_unreachable ();
1320         break;
1321       }
1322 }
1323
1324 /* Structure used to pass data to dom_walk.  */
1325
1326 struct bsc
1327 {
1328   VEC (gimple, heap) **conditions, **cases;
1329   sese region;
1330 };
1331
1332 /* Returns non NULL when BB has a single predecessor and the last
1333    statement of that predecessor is a COND_EXPR.  */
1334
1335 static gimple
1336 single_pred_cond (basic_block bb)
1337 {
1338   if (single_pred_p (bb))
1339     {
1340       edge e = single_pred_edge (bb);
1341       basic_block pred = e->src;
1342       gimple stmt = last_stmt (pred);
1343
1344       if (stmt && gimple_code (stmt) == GIMPLE_COND)
1345         return stmt;
1346     }
1347   return NULL;
1348 }
1349
1350 /* Call-back for dom_walk executed before visiting the dominated
1351    blocks.  */
1352
1353 static void
1354 build_sese_conditions_before (struct dom_walk_data *dw_data,
1355                               basic_block bb)
1356 {
1357   struct bsc *data = (struct bsc *) dw_data->global_data;
1358   VEC (gimple, heap) **conditions = data->conditions;
1359   VEC (gimple, heap) **cases = data->cases;
1360   gimple_bb_p gbb = gbb_from_bb (bb);
1361   gimple stmt = single_pred_cond (bb);
1362
1363   if (!bb_in_sese_p (bb, data->region))
1364     return;
1365
1366   if (stmt)
1367     {
1368       edge e = single_pred_edge (bb);
1369
1370       VEC_safe_push (gimple, heap, *conditions, stmt);
1371
1372       if (e->flags & EDGE_TRUE_VALUE)
1373         VEC_safe_push (gimple, heap, *cases, stmt);
1374       else
1375         VEC_safe_push (gimple, heap, *cases, NULL);
1376     }
1377
1378   if (gbb)
1379     {
1380       GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
1381       GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
1382     }
1383 }
1384
1385 /* Call-back for dom_walk executed after visiting the dominated
1386    blocks.  */
1387
1388 static void
1389 build_sese_conditions_after (struct dom_walk_data *dw_data,
1390                              basic_block bb)
1391 {
1392   struct bsc *data = (struct bsc *) dw_data->global_data;
1393   VEC (gimple, heap) **conditions = data->conditions;
1394   VEC (gimple, heap) **cases = data->cases;
1395
1396   if (!bb_in_sese_p (bb, data->region))
1397     return;
1398
1399   if (single_pred_cond (bb))
1400     {
1401       VEC_pop (gimple, *conditions);
1402       VEC_pop (gimple, *cases);
1403     }
1404 }
1405
1406 /* Record all conditions in REGION.  */
1407
1408 static void
1409 build_sese_conditions (sese region)
1410 {
1411   struct dom_walk_data walk_data;
1412   VEC (gimple, heap) *conditions = VEC_alloc (gimple, heap, 3);
1413   VEC (gimple, heap) *cases = VEC_alloc (gimple, heap, 3);
1414   struct bsc data;
1415
1416   data.conditions = &conditions;
1417   data.cases = &cases;
1418   data.region = region;
1419
1420   walk_data.dom_direction = CDI_DOMINATORS;
1421   walk_data.initialize_block_local_data = NULL;
1422   walk_data.before_dom_children = build_sese_conditions_before;
1423   walk_data.after_dom_children = build_sese_conditions_after;
1424   walk_data.global_data = &data;
1425   walk_data.block_local_data_size = 0;
1426
1427   init_walk_dominator_tree (&walk_data);
1428   walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region));
1429   fini_walk_dominator_tree (&walk_data);
1430
1431   VEC_free (gimple, heap, conditions);
1432   VEC_free (gimple, heap, cases);
1433 }
1434
1435 /* Traverses all the GBBs of the SCOP and add their constraints to the
1436    iteration domains.  */
1437
1438 static void
1439 add_conditions_to_constraints (scop_p scop)
1440 {
1441   int i;
1442   poly_bb_p pbb;
1443
1444   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1445     add_conditions_to_domain (pbb);
1446 }
1447
1448 /* Add constraints on the possible values of parameter P from the type
1449    of P.  */
1450
1451 static void
1452 add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
1453 {
1454   ppl_Constraint_t cstr;
1455   ppl_Linear_Expression_t le;
1456   tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p);
1457   tree type = TREE_TYPE (parameter);
1458   tree lb, ub;
1459
1460   /* Disabled until we fix CPU2006.  */
1461   return;
1462
1463   if (!INTEGRAL_TYPE_P (type))
1464     return;
1465
1466   lb = TYPE_MIN_VALUE (type);
1467   ub = TYPE_MAX_VALUE (type);
1468
1469   if (lb)
1470     {
1471       ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1472       ppl_set_coef (le, p, -1);
1473       ppl_set_inhomogeneous_tree (le, lb);
1474       ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1475       ppl_Polyhedron_add_constraint (context, cstr);
1476       ppl_delete_Linear_Expression (le);
1477       ppl_delete_Constraint (cstr);
1478     }
1479
1480   if (ub)
1481     {
1482       ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1483       ppl_set_coef (le, p, -1);
1484       ppl_set_inhomogeneous_tree (le, ub);
1485       ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1486       ppl_Polyhedron_add_constraint (context, cstr);
1487       ppl_delete_Linear_Expression (le);
1488       ppl_delete_Constraint (cstr);
1489     }
1490 }
1491
1492 /* Build the context of the SCOP.  The context usually contains extra
1493    constraints that are added to the iteration domains that constrain
1494    some parameters.  */
1495
1496 static void
1497 build_scop_context (scop_p scop)
1498 {
1499   ppl_Polyhedron_t context;
1500   graphite_dim_t p, n = scop_nb_params (scop);
1501
1502   ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0);
1503
1504   for (p = 0; p < n; p++)
1505     add_param_constraints (scop, context, p);
1506
1507   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1508     (&SCOP_CONTEXT (scop), context);
1509
1510   ppl_delete_Polyhedron (context);
1511 }
1512
1513 /* Build the iteration domains: the loops belonging to the current
1514    SCOP, and that vary for the execution of the current basic block.
1515    Returns false if there is no loop in SCOP.  */
1516
1517 static void
1518 build_scop_iteration_domain (scop_p scop)
1519 {
1520   struct loop *loop;
1521   sese region = SCOP_REGION (scop);
1522   int i;
1523   ppl_Polyhedron_t ph;
1524   poly_bb_p pbb;
1525
1526   ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0);
1527
1528   for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1529     if (!loop_in_sese_p (loop_outer (loop), region))
1530       build_loop_iteration_domains (scop, loop, ph, 0);
1531
1532   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1533     if (gbb_loop (PBB_BLACK_BOX (pbb))->aux)
1534       ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1535         (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
1536          gbb_loop (PBB_BLACK_BOX (pbb))->aux);
1537     else
1538       ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1539         (&PBB_DOMAIN (pbb), ph);
1540
1541   for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1542     if (loop->aux)
1543       {
1544         ppl_delete_Pointset_Powerset_C_Polyhedron
1545           ((ppl_Pointset_Powerset_C_Polyhedron_t) loop->aux);
1546         loop->aux = NULL;
1547       }
1548
1549   ppl_delete_Polyhedron (ph);
1550 }
1551
1552 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1553    data reference DR.  ACCESSP_NB_DIMS is the dimension of the
1554    ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1555    domain.  */
1556
1557 static void
1558 pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr,
1559                    ppl_dimension_type accessp_nb_dims,
1560                    ppl_dimension_type dom_nb_dims)
1561 {
1562   ppl_Linear_Expression_t alias;
1563   ppl_Constraint_t cstr;
1564   int alias_set_num = 0;
1565
1566   if (dr->aux != NULL)
1567     alias_set_num = ((int *)(dr->aux))[ALIAS_SET_INDEX];
1568
1569   ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims);
1570
1571   ppl_set_coef (alias, dom_nb_dims, 1);
1572   ppl_set_inhomogeneous (alias, -alias_set_num);
1573   ppl_new_Constraint (&cstr, alias, PPL_CONSTRAINT_TYPE_EQUAL);
1574   ppl_Polyhedron_add_constraint (accesses, cstr);
1575
1576   ppl_delete_Linear_Expression (alias);
1577   ppl_delete_Constraint (cstr);
1578 }
1579
1580 /* Add to ACCESSES polyhedron equalities defining the access functions
1581    to the memory.  ACCESSP_NB_DIMS is the dimension of the ACCESSES
1582    polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1583    PBB is the poly_bb_p that contains the data reference DR.  */
1584
1585 static void
1586 pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr,
1587                          ppl_dimension_type accessp_nb_dims,
1588                          ppl_dimension_type dom_nb_dims,
1589                          poly_bb_p pbb)
1590 {
1591   int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1592   Value v;
1593   scop_p scop = PBB_SCOP (pbb);
1594   sese region = SCOP_REGION (scop);
1595
1596   value_init (v);
1597
1598   for (i = 0; i < nb_subscripts; i++)
1599     {
1600       ppl_Linear_Expression_t fn, access;
1601       ppl_Constraint_t cstr;
1602       ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1603       tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i);
1604
1605       ppl_new_Linear_Expression_with_dimension (&fn, dom_nb_dims);
1606       ppl_new_Linear_Expression_with_dimension (&access, accessp_nb_dims);
1607
1608       value_set_si (v, 1);
1609       scan_tree_for_params (region, afn, fn, v);
1610       ppl_assign_Linear_Expression_from_Linear_Expression (access, fn);
1611
1612       ppl_set_coef (access, subscript, -1);
1613       ppl_new_Constraint (&cstr, access, PPL_CONSTRAINT_TYPE_EQUAL);
1614       ppl_Polyhedron_add_constraint (accesses, cstr);
1615
1616       ppl_delete_Linear_Expression (fn);
1617       ppl_delete_Linear_Expression (access);
1618       ppl_delete_Constraint (cstr);
1619     }
1620
1621   value_clear (v);
1622 }
1623
1624 /* Add constrains representing the size of the accessed data to the
1625    ACCESSES polyhedron.  ACCESSP_NB_DIMS is the dimension of the
1626    ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1627    domain.  */
1628
1629 static void
1630 pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr,
1631                          ppl_dimension_type accessp_nb_dims,
1632                          ppl_dimension_type dom_nb_dims)
1633 {
1634   tree ref = DR_REF (dr);
1635   int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1636
1637   for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
1638     {
1639       ppl_Linear_Expression_t expr;
1640       ppl_Constraint_t cstr;
1641       ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1642       tree low, high;
1643
1644       if (TREE_CODE (ref) != ARRAY_REF)
1645         break;
1646
1647       low = array_ref_low_bound (ref);
1648
1649       /* subscript - low >= 0 */
1650       if (host_integerp (low, 0))
1651         {
1652           ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1653           ppl_set_coef (expr, subscript, 1);
1654
1655           ppl_set_inhomogeneous (expr, -int_cst_value (low));
1656
1657           ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1658           ppl_Polyhedron_add_constraint (accesses, cstr);
1659           ppl_delete_Linear_Expression (expr);
1660           ppl_delete_Constraint (cstr);
1661         }
1662
1663       high = array_ref_up_bound (ref);
1664
1665       /* high - subscript >= 0
1666          XXX: 1-element arrays at end of structures may extend over their
1667          declared size.  */
1668       if (high && host_integerp (high, 0))
1669         {
1670           ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1671           ppl_set_coef (expr, subscript, -1);
1672
1673           ppl_set_inhomogeneous (expr, int_cst_value (high));
1674
1675           ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1676           ppl_Polyhedron_add_constraint (accesses, cstr);
1677           ppl_delete_Linear_Expression (expr);
1678           ppl_delete_Constraint (cstr);
1679         }
1680     }
1681 }
1682
1683 /* Build data accesses for DR in PBB.  */
1684
1685 static void
1686 build_poly_dr (data_reference_p dr, poly_bb_p pbb)
1687 {
1688   ppl_Polyhedron_t accesses;
1689   ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps;
1690   ppl_dimension_type dom_nb_dims;
1691   ppl_dimension_type accessp_nb_dims;
1692   int dr_base_object_set;
1693
1694   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb),
1695                                                       &dom_nb_dims);
1696   accessp_nb_dims = dom_nb_dims + 1 + DR_NUM_DIMENSIONS (dr);
1697
1698   ppl_new_C_Polyhedron_from_space_dimension (&accesses, accessp_nb_dims, 0);
1699
1700   pdr_add_alias_set (accesses, dr, accessp_nb_dims, dom_nb_dims);
1701   pdr_add_memory_accesses (accesses, dr, accessp_nb_dims, dom_nb_dims, pbb);
1702   pdr_add_data_dimensions (accesses, dr, accessp_nb_dims, dom_nb_dims);
1703
1704   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps,
1705                                                             accesses);
1706   ppl_delete_Polyhedron (accesses);
1707
1708   dr_base_object_set = ((int *)(dr->aux))[BASE_OBJECT_SET_INDEX];
1709
1710   new_poly_dr (pbb, dr_base_object_set, accesses_ps, DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
1711                dr, DR_NUM_DIMENSIONS (dr));
1712 }
1713
1714 /* Write to FILE the alias graph of data references with DIMACS format.  */
1715
1716 static inline bool
1717 write_alias_graph_to_ascii_dimacs (FILE *file, char *comment,
1718                                    VEC (data_reference_p, heap) *drs)
1719 {
1720   int num_vertex = VEC_length (data_reference_p, drs);
1721   int edge_num = 0;
1722   data_reference_p dr1, dr2;
1723   int i, j;
1724
1725   if (num_vertex == 0)
1726     return true;
1727
1728   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1729     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1730       if (dr_may_alias_p (dr1, dr2))
1731         edge_num++;
1732
1733   fprintf (file, "$\n");
1734
1735   if (comment)
1736     fprintf (file, "c %s\n", comment);
1737
1738   fprintf (file, "p edge %d %d\n", num_vertex, edge_num);
1739
1740   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1741     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1742       if (dr_may_alias_p (dr1, dr2))
1743         fprintf (file, "e %d %d\n", i + 1, j + 1);
1744
1745   return true;
1746 }
1747
1748 static void
1749 partition_drs_to_sets (VEC (data_reference_p, heap) *drs, int choice,
1750                        bool (* edge_exist_p) (const struct data_reference *,
1751                                               const struct data_reference *))
1752 {
1753   int num_vertex = VEC_length (data_reference_p, drs);
1754   struct graph *g = new_graph (num_vertex);
1755   data_reference_p dr1, dr2;
1756   int i, j;
1757   int num_component;
1758   int *queue;
1759
1760   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1761     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1762       if ((*edge_exist_p) (dr1, dr2))
1763         {
1764           add_edge (g, i, j);
1765           add_edge (g, j, i);
1766         }
1767
1768   queue = XNEWVEC (int, num_vertex);
1769   for (i = 0; i < num_vertex; i++)
1770     queue[i] = i;
1771
1772   num_component = graphds_dfs (g, queue, num_vertex, NULL, true, NULL);
1773
1774   for (i = 0; i < g->n_vertices; i++)
1775     {
1776       data_reference_p dr = VEC_index (data_reference_p, drs, i);
1777       if (!dr->aux)
1778         dr->aux = XNEWVEC (int, 2);
1779       ((int *)(dr->aux))[choice] = g->vertices[i].component + 1;
1780     }
1781
1782   free (queue);
1783   free_graph (g);
1784 }
1785
1786 static bool
1787 dr_same_base_object_p (const struct data_reference *dr1,
1788                        const struct data_reference *dr2)
1789 {
1790   return operand_equal_p (DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), 0);
1791 }
1792
1793 /* Group each data reference in DRS with it's alias set num.  */
1794
1795 static void
1796 build_alias_set_for_drs (VEC (data_reference_p, heap) *drs)
1797 {
1798   partition_drs_to_sets (drs, ALIAS_SET_INDEX, dr_may_alias_p);
1799 }
1800
1801 /* Group each data reference in DRS with it's base object set num.  */
1802
1803 static void
1804 build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs)
1805 {
1806   partition_drs_to_sets (drs, BASE_OBJECT_SET_INDEX, dr_same_base_object_p);
1807 }
1808
1809 /* Build the data references for PBB.  */
1810
1811 static void
1812 build_pbb_drs (poly_bb_p pbb)
1813 {
1814   int j;
1815   data_reference_p dr;
1816   VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb));
1817
1818   for (j = 0; VEC_iterate (data_reference_p, gbb_drs, j, dr); j++)
1819     build_poly_dr (dr, pbb);
1820 }
1821
1822 /* Build data references in SCOP.  */
1823
1824 static void
1825 build_scop_drs (scop_p scop)
1826 {
1827   int i, j;
1828   poly_bb_p pbb;
1829   data_reference_p dr;
1830   VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
1831
1832   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1833     for (j = 0; VEC_iterate (data_reference_p,
1834                              GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++)
1835       VEC_safe_push (data_reference_p, heap, drs, dr);
1836
1837   build_alias_set_for_drs (drs);
1838   build_base_obj_set_for_drs (drs);
1839
1840   /* When debugging, enable the following code.  This cannot be used
1841      in production compilers.  */
1842 #if 0
1843   {
1844     char comment[100];
1845     FILE *file;
1846
1847     file = fopen ("/tmp/dr_alias_graph", "ab");
1848     if (file)
1849       {
1850         snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
1851                   current_function_name ());
1852         write_alias_graph_to_ascii_dimacs (file, comment, drs);
1853         fclose (file);
1854       }
1855   }
1856 #endif
1857
1858   VEC_free (data_reference_p, heap, drs);
1859
1860   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1861     build_pbb_drs (pbb);
1862 }
1863
1864 /* Return a gsi at the position of the phi node STMT.  */
1865
1866 static gimple_stmt_iterator
1867 gsi_for_phi_node (gimple stmt)
1868 {
1869   gimple_stmt_iterator psi;
1870   basic_block bb = gimple_bb (stmt);
1871
1872   for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1873     if (stmt == gsi_stmt (psi))
1874       return psi;
1875
1876   gcc_unreachable ();
1877   return psi;
1878 }
1879
1880 /* Insert the assignment "RES := VAR" just after the definition of VAR.  */
1881
1882 static void
1883 insert_out_of_ssa_copy (tree res, tree var)
1884 {
1885   gimple stmt;
1886   gimple_seq stmts;
1887   gimple_stmt_iterator si;
1888   gimple_stmt_iterator gsi;
1889
1890   var = force_gimple_operand (var, &stmts, true, NULL_TREE);
1891   stmt = gimple_build_assign (res, var);
1892   if (!stmts)
1893     stmts = gimple_seq_alloc ();
1894   si = gsi_last (stmts);
1895   gsi_insert_after (&si, stmt, GSI_NEW_STMT);
1896
1897   stmt = SSA_NAME_DEF_STMT (var);
1898   if (gimple_code (stmt) == GIMPLE_PHI)
1899     {
1900       gsi = gsi_after_labels (gimple_bb (stmt));
1901       gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
1902     }
1903   else
1904     {
1905       gsi = gsi_for_stmt (stmt);
1906       gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
1907     }
1908 }
1909
1910 /* Insert on edge E the assignment "RES := EXPR".  */
1911
1912 static void
1913 insert_out_of_ssa_copy_on_edge (edge e, tree res, tree expr)
1914 {
1915   gimple_stmt_iterator gsi;
1916   gimple_seq stmts;
1917   tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
1918   gimple stmt = gimple_build_assign (res, var);
1919
1920   if (!stmts)
1921     stmts = gimple_seq_alloc ();
1922
1923   gsi = gsi_last (stmts);
1924   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1925   gsi_insert_seq_on_edge (e, stmts);
1926   gsi_commit_edge_inserts ();
1927 }
1928
1929 /* Creates a zero dimension array of the same type as VAR.  */
1930
1931 static tree
1932 create_zero_dim_array (tree var)
1933 {
1934   tree index_type = build_index_type (integer_zero_node);
1935   tree elt_type = TREE_TYPE (var);
1936   tree array_type = build_array_type (elt_type, index_type);
1937   tree base = create_tmp_var (array_type, "Red");
1938
1939   add_referenced_var (base);
1940
1941   return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
1942                  NULL_TREE);
1943 }
1944
1945 /* Returns true when PHI is a loop close phi node.  */
1946
1947 static bool
1948 scalar_close_phi_node_p (gimple phi)
1949 {
1950   if (gimple_code (phi) != GIMPLE_PHI
1951       || !is_gimple_reg (gimple_phi_result (phi)))
1952     return false;
1953
1954   return (gimple_phi_num_args (phi) == 1);
1955 }
1956
1957 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1958    dimension array for it.  */
1959
1960 static void
1961 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi)
1962 {
1963   gimple phi = gsi_stmt (*psi);
1964   tree res = gimple_phi_result (phi);
1965   tree var = SSA_NAME_VAR (res);
1966   tree zero_dim_array = create_zero_dim_array (var);
1967   gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
1968   gimple stmt = gimple_build_assign (res, zero_dim_array);
1969   tree arg = gimple_phi_arg_def (phi, 0);
1970
1971   insert_out_of_ssa_copy (zero_dim_array, arg);
1972
1973   remove_phi_node (psi, false);
1974   gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1975   SSA_NAME_DEF_STMT (res) = stmt;
1976 }
1977
1978 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1979    dimension array for it.  */
1980
1981 static void
1982 rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi)
1983 {
1984   size_t i;
1985   gimple phi = gsi_stmt (*psi);
1986   basic_block bb = gimple_bb (phi);
1987   tree res = gimple_phi_result (phi);
1988   tree var = SSA_NAME_VAR (res);
1989   tree zero_dim_array = create_zero_dim_array (var);
1990   gimple_stmt_iterator gsi;
1991   gimple stmt;
1992   gimple_seq stmts;
1993
1994   for (i = 0; i < gimple_phi_num_args (phi); i++)
1995     {
1996       tree arg = gimple_phi_arg_def (phi, i);
1997
1998       /* Try to avoid the insertion on edges as much as possible: this
1999          would avoid the insertion of code on loop latch edges, making
2000          the pattern matching of the vectorizer happy, or it would
2001          avoid the insertion of useless basic blocks.  Note that it is
2002          incorrect to insert out of SSA copies close by their
2003          definition when they are more than two loop levels apart:
2004          for example, starting from a double nested loop
2005
2006          | a = ...
2007          | loop_1
2008          |  loop_2
2009          |    b = phi (a, c)
2010          |    c = ...
2011          |  end_2
2012          | end_1
2013
2014          the following transform is incorrect
2015
2016          | a = ...
2017          | Red[0] = a
2018          | loop_1
2019          |  loop_2
2020          |    b = Red[0]
2021          |    c = ...
2022          |    Red[0] = c
2023          |  end_2
2024          | end_1
2025
2026          whereas inserting the copy on the incomming edge is correct
2027
2028          | a = ...
2029          | loop_1
2030          |  Red[0] = a
2031          |  loop_2
2032          |    b = Red[0]
2033          |    c = ...
2034          |    Red[0] = c
2035          |  end_2
2036          | end_1
2037       */
2038       if (TREE_CODE (arg) == SSA_NAME
2039           && is_gimple_reg (arg)
2040           && gimple_bb (SSA_NAME_DEF_STMT (arg))
2041           && (flow_bb_inside_loop_p (bb->loop_father,
2042                                      gimple_bb (SSA_NAME_DEF_STMT (arg)))
2043               || flow_bb_inside_loop_p (loop_outer (bb->loop_father),
2044                                         gimple_bb (SSA_NAME_DEF_STMT (arg)))))
2045         insert_out_of_ssa_copy (zero_dim_array, arg);
2046       else
2047         insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi, i),
2048                                         zero_dim_array, arg);
2049     }
2050
2051   var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE);
2052
2053   if (!stmts)
2054     stmts = gimple_seq_alloc ();
2055
2056   stmt = gimple_build_assign (res, var);
2057   remove_phi_node (psi, false);
2058   SSA_NAME_DEF_STMT (res) = stmt;
2059
2060   gsi = gsi_last (stmts);
2061   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2062
2063   gsi = gsi_after_labels (bb);
2064   gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2065 }
2066
2067 /* Return true when DEF can be analyzed in REGION by the scalar
2068    evolution analyzer.  */
2069
2070 static bool
2071 scev_analyzable_p (tree def, sese region)
2072 {
2073   gimple stmt = SSA_NAME_DEF_STMT (def);
2074   loop_p loop = loop_containing_stmt (stmt);
2075   tree scev = scalar_evolution_in_region (region, loop, def);
2076
2077   return !chrec_contains_undetermined (scev);
2078 }
2079
2080 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2081    read from ZERO_DIM_ARRAY.  */
2082
2083 static void
2084 rewrite_cross_bb_scalar_dependence (tree zero_dim_array, tree def, gimple use_stmt)
2085 {
2086   tree var = SSA_NAME_VAR (def);
2087   gimple name_stmt = gimple_build_assign (var, zero_dim_array);
2088   tree name = make_ssa_name (var, name_stmt);
2089   ssa_op_iter iter;
2090   use_operand_p use_p;
2091   gimple_stmt_iterator gsi;
2092
2093   gimple_assign_set_lhs (name_stmt, name);
2094
2095   if (gimple_code (use_stmt) == GIMPLE_PHI)
2096     {
2097       gimple phi = use_stmt;
2098       edge entry;
2099       unsigned i;
2100
2101       for (i = 0; i < gimple_phi_num_args (phi); i++)
2102         if (operand_equal_p (def, gimple_phi_arg_def (phi, i), 0))
2103           {
2104             entry = gimple_phi_arg_edge (phi, i);
2105             break;
2106           }
2107
2108       FOR_EACH_PHI_ARG (use_p, phi, iter, SSA_OP_USE)
2109         if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2110           {
2111             gsi = gsi_last_bb (entry->src);
2112             gsi_insert_after (&gsi, name_stmt, GSI_NEW_STMT);
2113             SET_USE (use_p, name);
2114             break;
2115           }
2116     }
2117   else
2118     {
2119       gsi = gsi_for_stmt (use_stmt);
2120       gsi_insert_before (&gsi, name_stmt, GSI_NEW_STMT);
2121
2122       FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2123         if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2124           replace_exp (use_p, name);
2125     }
2126
2127   update_stmt (use_stmt);
2128 }
2129
2130 /* Rewrite the scalar dependences crossing the boundary of the BB
2131    containing STMT with an array.  */
2132
2133 static void
2134 rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi)
2135 {
2136   gimple stmt = gsi_stmt (*gsi);
2137   imm_use_iterator imm_iter;
2138   tree def;
2139   basic_block def_bb;
2140   tree zero_dim_array = NULL_TREE;
2141   gimple use_stmt;
2142
2143   if (gimple_code (stmt) != GIMPLE_ASSIGN)
2144     return;
2145
2146   def = gimple_assign_lhs (stmt);
2147   if (!is_gimple_reg (def)
2148       || scev_analyzable_p (def, region))
2149     return;
2150
2151   def_bb = gimple_bb (stmt);
2152
2153   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2154     if (def_bb != gimple_bb (use_stmt))
2155       {
2156         if (!zero_dim_array)
2157           {
2158             zero_dim_array = create_zero_dim_array (SSA_NAME_VAR (def));
2159             insert_out_of_ssa_copy (zero_dim_array, def);
2160             gsi_next (gsi);
2161           }
2162
2163         rewrite_cross_bb_scalar_dependence (zero_dim_array, def, use_stmt);
2164       }
2165 }
2166
2167 /* Rewrite out of SSA all the reduction phi nodes of SCOP.  */
2168
2169 static void
2170 rewrite_reductions_out_of_ssa (scop_p scop)
2171 {
2172   basic_block bb;
2173   gimple_stmt_iterator psi;
2174   sese region = SCOP_REGION (scop);
2175
2176   FOR_EACH_BB (bb)
2177     if (bb_in_sese_p (bb, region))
2178       for (psi = gsi_start_phis (bb); !gsi_end_p (psi);)
2179         {
2180           if (scalar_close_phi_node_p (gsi_stmt (psi)))
2181             rewrite_close_phi_out_of_ssa (&psi);
2182           else if (reduction_phi_p (region, &psi))
2183             rewrite_phi_out_of_ssa (&psi);
2184         }
2185
2186   update_ssa (TODO_update_ssa);
2187 #ifdef ENABLE_CHECKING
2188   verify_ssa (false);
2189   verify_loop_closed_ssa ();
2190 #endif
2191
2192   FOR_EACH_BB (bb)
2193     if (bb_in_sese_p (bb, region))
2194       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
2195         rewrite_cross_bb_scalar_deps (region, &psi);
2196
2197   update_ssa (TODO_update_ssa);
2198 #ifdef ENABLE_CHECKING
2199   verify_ssa (false);
2200   verify_loop_closed_ssa ();
2201 #endif
2202 }
2203
2204 /* Returns the number of pbbs that are in loops contained in SCOP.  */
2205
2206 static int
2207 nb_pbbs_in_loops (scop_p scop)
2208 {
2209   int i;
2210   poly_bb_p pbb;
2211   int res = 0;
2212
2213   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2214     if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2215       res++;
2216
2217   return res;
2218 }
2219
2220 /* Return the number of data references in BB that write in
2221    memory.  */
2222
2223 static int
2224 nb_data_writes_in_bb (basic_block bb)
2225 {
2226   int res = 0;
2227   gimple_stmt_iterator gsi;
2228
2229   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2230     if (gimple_vdef (gsi_stmt (gsi)))
2231       res++;
2232
2233   return res;
2234 }
2235
2236 /* Splits STMT out of its current BB.  */
2237
2238 static basic_block
2239 split_reduction_stmt (gimple stmt)
2240 {
2241   gimple_stmt_iterator gsi;
2242   basic_block bb = gimple_bb (stmt);
2243   edge e;
2244
2245   /* Do not split basic blocks with no writes to memory: the reduction
2246      will be the only write to memory.  */
2247   if (nb_data_writes_in_bb (bb) == 0)
2248     return bb;
2249
2250   split_block (bb, stmt);
2251
2252   gsi = gsi_last_bb (bb);
2253   gsi_prev (&gsi);
2254   e = split_block (bb, gsi_stmt (gsi));
2255
2256   return e->dest;
2257 }
2258
2259 /* Return true when stmt is a reduction operation.  */
2260
2261 static inline bool
2262 is_reduction_operation_p (gimple stmt)
2263 {
2264   return flag_associative_math
2265     && commutative_tree_code (gimple_assign_rhs_code (stmt))
2266     && associative_tree_code (gimple_assign_rhs_code (stmt));
2267 }
2268
2269 /* Returns true when PHI contains an argument ARG.  */
2270
2271 static bool
2272 phi_contains_arg (gimple phi, tree arg)
2273 {
2274   size_t i;
2275
2276   for (i = 0; i < gimple_phi_num_args (phi); i++)
2277     if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
2278       return true;
2279
2280   return false;
2281 }
2282
2283 /* Return a loop phi node that corresponds to a reduction containing LHS.  */
2284
2285 static gimple
2286 follow_ssa_with_commutative_ops (tree arg, tree lhs)
2287 {
2288   gimple stmt;
2289
2290   if (TREE_CODE (arg) != SSA_NAME)
2291     return NULL;
2292
2293   stmt = SSA_NAME_DEF_STMT (arg);
2294
2295   if (gimple_code (stmt) == GIMPLE_PHI)
2296     {
2297       if (phi_contains_arg (stmt, lhs))
2298         return stmt;
2299       return NULL;
2300     }
2301
2302   if (gimple_num_ops (stmt) == 2)
2303     return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2304
2305   if (is_reduction_operation_p (stmt))
2306     {
2307       gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2308
2309       return res ? res :
2310         follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
2311     }
2312
2313   return NULL;
2314 }
2315
2316 /* Detect commutative and associative scalar reductions starting at
2317    the STMT.  */
2318
2319 static gimple
2320 detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
2321                                   VEC (gimple, heap) **in,
2322                                   VEC (gimple, heap) **out)
2323 {
2324   gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
2325
2326   if (phi)
2327     {
2328       VEC_safe_push (gimple, heap, *in, stmt);
2329       VEC_safe_push (gimple, heap, *out, stmt);
2330       return phi;
2331     }
2332
2333   return NULL;
2334 }
2335
2336 /* Detect commutative and associative scalar reductions starting at
2337    the STMT.  */
2338
2339 static gimple
2340 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
2341                                      VEC (gimple, heap) **out)
2342 {
2343   tree lhs = gimple_assign_lhs (stmt);
2344
2345   if (gimple_num_ops (stmt) == 2)
2346     return detect_commutative_reduction_arg (lhs, stmt,
2347                                              gimple_assign_rhs1 (stmt),
2348                                              in, out);
2349
2350   if (is_reduction_operation_p (stmt))
2351     {
2352       gimple res = detect_commutative_reduction_arg (lhs, stmt,
2353                                                      gimple_assign_rhs1 (stmt),
2354                                                      in, out);
2355       return res ? res
2356         : detect_commutative_reduction_arg (lhs, stmt,
2357                                             gimple_assign_rhs2 (stmt),
2358                                             in, out);
2359     }
2360
2361   return NULL;
2362 }
2363
2364 /* Return a loop phi node that corresponds to a reduction containing LHS.  */
2365
2366 static gimple
2367 follow_inital_value_to_phi (tree arg, tree lhs)
2368 {
2369   gimple stmt;
2370
2371   if (!arg || TREE_CODE (arg) != SSA_NAME)
2372     return NULL;
2373
2374   stmt = SSA_NAME_DEF_STMT (arg);
2375
2376   if (gimple_code (stmt) == GIMPLE_PHI
2377       && phi_contains_arg (stmt, lhs))
2378     return stmt;
2379
2380   return NULL;
2381 }
2382
2383
2384 /* Return the argument of the loop PHI that is the inital value coming
2385    from outside the loop.  */
2386
2387 static edge
2388 edge_initial_value_for_loop_phi (gimple phi)
2389 {
2390   size_t i;
2391
2392   for (i = 0; i < gimple_phi_num_args (phi); i++)
2393     {
2394       edge e = gimple_phi_arg_edge (phi, i);
2395
2396       if (loop_depth (e->src->loop_father)
2397           < loop_depth (e->dest->loop_father))
2398         return e;
2399     }
2400
2401   return NULL;
2402 }
2403
2404 /* Return the argument of the loop PHI that is the inital value coming
2405    from outside the loop.  */
2406
2407 static tree
2408 initial_value_for_loop_phi (gimple phi)
2409 {
2410   size_t i;
2411
2412   for (i = 0; i < gimple_phi_num_args (phi); i++)
2413     {
2414       edge e = gimple_phi_arg_edge (phi, i);
2415
2416       if (loop_depth (e->src->loop_father)
2417           < loop_depth (e->dest->loop_father))
2418         return gimple_phi_arg_def (phi, i);
2419     }
2420
2421   return NULL_TREE;
2422 }
2423
2424 /* Detect commutative and associative scalar reductions starting at
2425    the loop closed phi node CLOSE_PHI.  */
2426
2427 static gimple
2428 detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in,
2429                               VEC (gimple, heap) **out)
2430 {
2431   if (scalar_close_phi_node_p (stmt))
2432     {
2433       tree arg = gimple_phi_arg_def (stmt, 0);
2434       gimple def = SSA_NAME_DEF_STMT (arg);
2435       gimple loop_phi = detect_commutative_reduction (def, in, out);
2436
2437       if (loop_phi)
2438         {
2439           tree lhs = gimple_phi_result (stmt);
2440           tree init = initial_value_for_loop_phi (loop_phi);
2441           gimple phi = follow_inital_value_to_phi (init, lhs);
2442
2443           VEC_safe_push (gimple, heap, *in, loop_phi);
2444           VEC_safe_push (gimple, heap, *out, stmt);
2445           return phi;
2446         }
2447       else
2448         return NULL;
2449     }
2450
2451   if (gimple_code (stmt) == GIMPLE_ASSIGN)
2452     return detect_commutative_reduction_assign (stmt, in, out);
2453
2454   return NULL;
2455 }
2456
2457 /* Translate the scalar reduction statement STMT to an array RED
2458    knowing that its recursive phi node is LOOP_PHI.  */
2459
2460 static void
2461 translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt,
2462                                               gimple loop_phi)
2463 {
2464   basic_block bb = gimple_bb (stmt);
2465   gimple_stmt_iterator insert_gsi = gsi_after_labels (bb);
2466   tree res = gimple_phi_result (loop_phi);
2467   gimple assign = gimple_build_assign (res, red);
2468
2469   gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2470
2471   assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
2472   insert_gsi = gsi_for_stmt (stmt);
2473   gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT);
2474 }
2475
2476 /* Insert the assignment "result (CLOSE_PHI) = RED".  */
2477
2478 static void
2479 insert_copyout (tree red, gimple close_phi)
2480 {
2481   tree res = gimple_phi_result (close_phi);
2482   basic_block bb = gimple_bb (close_phi);
2483   gimple_stmt_iterator insert_gsi = gsi_after_labels (bb);
2484   gimple assign = gimple_build_assign (res, red);
2485
2486   gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2487 }
2488
2489 /* Insert the assignment "RED = initial_value (LOOP_PHI)".  */
2490
2491 static void
2492 insert_copyin (tree red, gimple loop_phi)
2493 {
2494   gimple_seq stmts;
2495   tree init = initial_value_for_loop_phi (loop_phi);
2496   edge e = edge_initial_value_for_loop_phi (loop_phi);
2497   basic_block bb = e->src;
2498   gimple_stmt_iterator insert_gsi = gsi_last_bb (bb);
2499   tree expr = build2 (MODIFY_EXPR, TREE_TYPE (init), red, init);
2500
2501   force_gimple_operand (expr, &stmts, true, NULL);
2502   gsi_insert_seq_before (&insert_gsi, stmts, GSI_SAME_STMT);
2503 }
2504
2505 /* Rewrite out of SSA the reduction described by the loop phi nodes
2506    IN, and the close phi nodes OUT.  IN and OUT are structured by loop
2507    levels like this:
2508
2509    IN: stmt, loop_n, ..., loop_0
2510    OUT: stmt, close_n, ..., close_0
2511
2512    the first element is the reduction statement, and the next elements
2513    are the loop and close phi nodes of each of the outer loops.  */
2514
2515 static void
2516 translate_scalar_reduction_to_array (VEC (gimple, heap) *in,
2517                                      VEC (gimple, heap) *out,
2518                                      sbitmap reductions)
2519 {
2520   unsigned int i;
2521   gimple loop_phi;
2522   tree red;
2523   gimple_stmt_iterator gsi;
2524
2525   for (i = 0; VEC_iterate (gimple, in, i, loop_phi); i++)
2526     {
2527       gimple close_phi = VEC_index (gimple, out, i);
2528
2529       if (i == 0)
2530         {
2531           gimple stmt = loop_phi;
2532           basic_block bb = split_reduction_stmt (stmt);
2533
2534           SET_BIT (reductions, bb->index);
2535           gcc_assert (close_phi == loop_phi);
2536
2537           red = create_zero_dim_array (gimple_assign_lhs (stmt));
2538           translate_scalar_reduction_to_array_for_stmt
2539             (red, stmt, VEC_index (gimple, in, 1));
2540           continue;
2541         }
2542
2543       if (i == VEC_length (gimple, in) - 1)
2544         {
2545           insert_copyout (red, close_phi);
2546           insert_copyin (red, loop_phi);
2547         }
2548
2549       gsi = gsi_for_phi_node (loop_phi);
2550       remove_phi_node (&gsi, false);
2551
2552       gsi = gsi_for_phi_node (close_phi);
2553       remove_phi_node (&gsi, false);
2554     }
2555 }
2556
2557 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI.  */
2558
2559 static void
2560 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi,
2561                                                      sbitmap reductions)
2562 {
2563   VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
2564   VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
2565
2566   detect_commutative_reduction (close_phi, &in, &out);
2567   if (VEC_length (gimple, in) > 0)
2568     translate_scalar_reduction_to_array (in, out, reductions);
2569
2570   VEC_free (gimple, heap, in);
2571   VEC_free (gimple, heap, out);
2572 }
2573
2574 /* Rewrites all the commutative reductions from LOOP out of SSA.  */
2575
2576 static void
2577 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop,
2578                                                 sbitmap reductions)
2579 {
2580   gimple_stmt_iterator gsi;
2581   edge exit = single_exit (loop);
2582
2583   if (!exit)
2584     return;
2585
2586   for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
2587     rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi),
2588                                                          reductions);
2589 }
2590
2591 /* Rewrites all the commutative reductions from SCOP out of SSA.  */
2592
2593 static void
2594 rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions)
2595 {
2596   loop_iterator li;
2597   loop_p loop;
2598
2599   FOR_EACH_LOOP (li, loop, 0)
2600     if (loop_in_sese_p (loop, region))
2601       rewrite_commutative_reductions_out_of_ssa_loop (loop, reductions);
2602 }
2603
2604 /* Builds the polyhedral representation for a SESE region.  */
2605
2606 bool
2607 build_poly_scop (scop_p scop)
2608 {
2609   sese region = SCOP_REGION (scop);
2610   sbitmap reductions = sbitmap_alloc (last_basic_block * 2);
2611
2612   sbitmap_zero (reductions);
2613   rewrite_commutative_reductions_out_of_ssa (region, reductions);
2614   rewrite_reductions_out_of_ssa (scop);
2615   build_scop_bbs (scop, reductions);
2616   sbitmap_free (reductions);
2617
2618   /* FIXME: This restriction is needed to avoid a problem in CLooG.
2619      Once CLooG is fixed, remove this guard.  Anyways, it makes no
2620      sense to optimize a scop containing only PBBs that do not belong
2621      to any loops.  */
2622   if (nb_pbbs_in_loops (scop) == 0)
2623     return false;
2624
2625   build_sese_loop_nests (region);
2626   build_sese_conditions (region);
2627   find_scop_parameters (scop);
2628
2629   build_scop_iteration_domain (scop);
2630   build_scop_context (scop);
2631
2632   add_conditions_to_constraints (scop);
2633   scop_to_lst (scop);
2634   build_scop_scattering (scop);
2635   build_scop_drs (scop);
2636
2637   return true;
2638 }
2639
2640 /* Always return false.  Exercise the scop_to_clast function.  */
2641
2642 void
2643 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED)
2644 {
2645 #ifdef ENABLE_CHECKING
2646   cloog_prog_clast pc = scop_to_clast (scop);
2647   cloog_clast_free (pc.stmt);
2648   cloog_program_free (pc.prog);
2649 #endif
2650 }
2651 #endif