OSDN Git Service

89330727337d9e758ef1afb672e2fbe92e492764
[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         base_alias_pair *bap = (base_alias_pair *)(dr->aux);
298
299         if (bap->alias_set)
300           free (bap->alias_set);
301
302         free (bap);
303         dr->aux = NULL;
304       }
305 }
306 /* Frees GBB.  */
307
308 static void
309 free_gimple_bb (struct gimple_bb *gbb)
310 {
311   if (GBB_CLOOG_IV_TYPES (gbb))
312     htab_delete (GBB_CLOOG_IV_TYPES (gbb));
313
314   free_data_refs_aux (GBB_DATA_REFS (gbb));
315   free_data_refs (GBB_DATA_REFS (gbb));
316
317   VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
318   VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
319   GBB_BB (gbb)->aux = 0;
320   XDELETE (gbb);
321 }
322
323 /* Deletes all gimple bbs in SCOP.  */
324
325 static void
326 remove_gbbs_in_scop (scop_p scop)
327 {
328   int i;
329   poly_bb_p pbb;
330
331   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
332     free_gimple_bb (PBB_BLACK_BOX (pbb));
333 }
334
335 /* Deletes all scops in SCOPS.  */
336
337 void
338 free_scops (VEC (scop_p, heap) *scops)
339 {
340   int i;
341   scop_p scop;
342
343   for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
344     {
345       remove_gbbs_in_scop (scop);
346       free_sese (SCOP_REGION (scop));
347       free_scop (scop);
348     }
349
350   VEC_free (scop_p, heap, scops);
351 }
352
353 /* Generates a polyhedral black box only if the bb contains interesting
354    information.  */
355
356 static void
357 try_generate_gimple_bb (scop_p scop, basic_block bb, sbitmap reductions)
358 {
359   VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
360   loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
361   gimple_stmt_iterator gsi;
362
363   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
364     {
365       gimple stmt = gsi_stmt (gsi);
366       if (!is_gimple_debug (stmt))
367         graphite_find_data_references_in_stmt (nest, stmt, &drs);
368     }
369
370   if (!graphite_stmt_p (SCOP_REGION (scop), bb, drs))
371     free_data_refs (drs);
372   else
373     new_poly_bb (scop, new_gimple_bb (bb, drs), TEST_BIT (reductions,
374                                                           bb->index));
375 }
376
377 /* Returns true if all predecessors of BB, that are not dominated by BB, are
378    marked in MAP.  The predecessors dominated by BB are loop latches and will
379    be handled after BB.  */
380
381 static bool
382 all_non_dominated_preds_marked_p (basic_block bb, sbitmap map)
383 {
384   edge e;
385   edge_iterator ei;
386
387   FOR_EACH_EDGE (e, ei, bb->preds)
388     if (!TEST_BIT (map, e->src->index)
389         && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
390         return false;
391
392   return true;
393 }
394
395 /* Compare the depth of two basic_block's P1 and P2.  */
396
397 static int
398 compare_bb_depths (const void *p1, const void *p2)
399 {
400   const_basic_block const bb1 = *(const_basic_block const*)p1;
401   const_basic_block const bb2 = *(const_basic_block const*)p2;
402   int d1 = loop_depth (bb1->loop_father);
403   int d2 = loop_depth (bb2->loop_father);
404
405   if (d1 < d2)
406     return 1;
407
408   if (d1 > d2)
409     return -1;
410
411   return 0;
412 }
413
414 /* Sort the basic blocks from DOM such that the first are the ones at
415    a deepest loop level.  */
416
417 static void
418 graphite_sort_dominated_info (VEC (basic_block, heap) *dom)
419 {
420   size_t len = VEC_length (basic_block, dom);
421
422   qsort (VEC_address (basic_block, dom), len, sizeof (basic_block),
423          compare_bb_depths);
424 }
425
426 /* Recursive helper function for build_scops_bbs.  */
427
428 static void
429 build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb, sbitmap reductions)
430 {
431   sese region = SCOP_REGION (scop);
432   VEC (basic_block, heap) *dom;
433
434   if (TEST_BIT (visited, bb->index)
435       || !bb_in_sese_p (bb, region))
436     return;
437
438   try_generate_gimple_bb (scop, bb, reductions);
439   SET_BIT (visited, bb->index);
440
441   dom = get_dominated_by (CDI_DOMINATORS, bb);
442
443   if (dom == NULL)
444     return;
445
446   graphite_sort_dominated_info (dom);
447
448   while (!VEC_empty (basic_block, dom))
449     {
450       int i;
451       basic_block dom_bb;
452
453       for (i = 0; VEC_iterate (basic_block, dom, i, dom_bb); i++)
454         if (all_non_dominated_preds_marked_p (dom_bb, visited))
455           {
456             build_scop_bbs_1 (scop, visited, dom_bb, reductions);
457             VEC_unordered_remove (basic_block, dom, i);
458             break;
459           }
460     }
461
462   VEC_free (basic_block, heap, dom);
463 }
464
465 /* Gather the basic blocks belonging to the SCOP.  */
466
467 static void
468 build_scop_bbs (scop_p scop, sbitmap reductions)
469 {
470   sbitmap visited = sbitmap_alloc (last_basic_block);
471   sese region = SCOP_REGION (scop);
472
473   sbitmap_zero (visited);
474   build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region), reductions);
475   sbitmap_free (visited);
476 }
477
478 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
479    We generate SCATTERING_DIMENSIONS scattering dimensions.
480
481    CLooG 0.15.0 and previous versions require, that all
482    scattering functions of one CloogProgram have the same number of
483    scattering dimensions, therefore we allow to specify it.  This
484    should be removed in future versions of CLooG.
485
486    The scattering polyhedron consists of these dimensions: scattering,
487    loop_iterators, parameters.
488
489    Example:
490
491    | scattering_dimensions = 5
492    | used_scattering_dimensions = 3
493    | nb_iterators = 1
494    | scop_nb_params = 2
495    |
496    | Schedule:
497    |   i
498    | 4 5
499    |
500    | Scattering polyhedron:
501    |
502    | scattering: {s1, s2, s3, s4, s5}
503    | loop_iterators: {i}
504    | parameters: {p1, p2}
505    |
506    | s1  s2  s3  s4  s5  i   p1  p2  1
507    | 1   0   0   0   0   0   0   0  -4  = 0
508    | 0   1   0   0   0  -1   0   0   0  = 0
509    | 0   0   1   0   0   0   0   0  -5  = 0  */
510
511 static void
512 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule,
513                                   poly_bb_p pbb, int scattering_dimensions)
514 {
515   int i;
516   scop_p scop = PBB_SCOP (pbb);
517   int nb_iterators = pbb_dim_iter_domain (pbb);
518   int used_scattering_dimensions = nb_iterators * 2 + 1;
519   int nb_params = scop_nb_params (scop);
520   ppl_Coefficient_t c;
521   ppl_dimension_type dim = scattering_dimensions + nb_iterators + nb_params;
522   Value v;
523
524   gcc_assert (scattering_dimensions >= used_scattering_dimensions);
525
526   value_init (v);
527   ppl_new_Coefficient (&c);
528   PBB_TRANSFORMED (pbb) = poly_scattering_new ();
529   ppl_new_C_Polyhedron_from_space_dimension
530     (&PBB_TRANSFORMED_SCATTERING (pbb), dim, 0);
531
532   PBB_NB_SCATTERING_TRANSFORM (pbb) = scattering_dimensions;
533
534   for (i = 0; i < scattering_dimensions; i++)
535     {
536       ppl_Constraint_t cstr;
537       ppl_Linear_Expression_t expr;
538
539       ppl_new_Linear_Expression_with_dimension (&expr, dim);
540       value_set_si (v, 1);
541       ppl_assign_Coefficient_from_mpz_t (c, v);
542       ppl_Linear_Expression_add_to_coefficient (expr, i, c);
543
544       /* Textual order inside this loop.  */
545       if ((i % 2) == 0)
546         {
547           ppl_Linear_Expression_coefficient (static_schedule, i / 2, c);
548           ppl_Coefficient_to_mpz_t (c, v);
549           value_oppose (v, v);
550           ppl_assign_Coefficient_from_mpz_t (c, v);
551           ppl_Linear_Expression_add_to_inhomogeneous (expr, c);
552         }
553
554       /* Iterations of this loop.  */
555       else /* if ((i % 2) == 1) */
556         {
557           int loop = (i - 1) / 2;
558
559           value_set_si (v, -1);
560           ppl_assign_Coefficient_from_mpz_t (c, v);
561           ppl_Linear_Expression_add_to_coefficient
562             (expr, scattering_dimensions + loop, c);
563         }
564
565       ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
566       ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
567       ppl_delete_Linear_Expression (expr);
568       ppl_delete_Constraint (cstr);
569     }
570
571   value_clear (v);
572   ppl_delete_Coefficient (c);
573
574   PBB_ORIGINAL (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
575 }
576
577 /* Build for BB the static schedule.
578
579    The static schedule is a Dewey numbering of the abstract syntax
580    tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
581
582    The following example informally defines the static schedule:
583
584    A
585    for (i: ...)
586      {
587        for (j: ...)
588          {
589            B
590            C
591          }
592
593        for (k: ...)
594          {
595            D
596            E
597          }
598      }
599    F
600
601    Static schedules for A to F:
602
603      DEPTH
604      0 1 2
605    A 0
606    B 1 0 0
607    C 1 0 1
608    D 1 1 0
609    E 1 1 1
610    F 2
611 */
612
613 static void
614 build_scop_scattering (scop_p scop)
615 {
616   int i;
617   poly_bb_p pbb;
618   gimple_bb_p previous_gbb = NULL;
619   ppl_Linear_Expression_t static_schedule;
620   ppl_Coefficient_t c;
621   Value v;
622
623   value_init (v);
624   ppl_new_Coefficient (&c);
625   ppl_new_Linear_Expression (&static_schedule);
626
627   /* We have to start schedules at 0 on the first component and
628      because we cannot compare_prefix_loops against a previous loop,
629      prefix will be equal to zero, and that index will be
630      incremented before copying.  */
631   value_set_si (v, -1);
632   ppl_assign_Coefficient_from_mpz_t (c, v);
633   ppl_Linear_Expression_add_to_coefficient (static_schedule, 0, c);
634
635   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
636     {
637       gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
638       ppl_Linear_Expression_t common;
639       int prefix;
640       int nb_scat_dims = pbb_dim_iter_domain (pbb) * 2 + 1;
641
642       if (previous_gbb)
643         prefix = nb_common_loops (SCOP_REGION (scop), previous_gbb, gbb);
644       else
645         prefix = 0;
646
647       previous_gbb = gbb;
648       ppl_new_Linear_Expression_with_dimension (&common, prefix + 1);
649       ppl_assign_Linear_Expression_from_Linear_Expression (common,
650                                                            static_schedule);
651
652       value_set_si (v, 1);
653       ppl_assign_Coefficient_from_mpz_t (c, v);
654       ppl_Linear_Expression_add_to_coefficient (common, prefix, c);
655       ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule,
656                                                            common);
657
658       build_pbb_scattering_polyhedrons (common, pbb, nb_scat_dims);
659
660       ppl_delete_Linear_Expression (common);
661     }
662
663   value_clear (v);
664   ppl_delete_Coefficient (c);
665   ppl_delete_Linear_Expression (static_schedule);
666 }
667
668 /* Add the value K to the dimension D of the linear expression EXPR.  */
669
670 static void
671 add_value_to_dim (ppl_dimension_type d, ppl_Linear_Expression_t expr,
672                   Value k)
673 {
674   Value val;
675   ppl_Coefficient_t coef;
676
677   ppl_new_Coefficient (&coef);
678   ppl_Linear_Expression_coefficient (expr, d, coef);
679   value_init (val);
680   ppl_Coefficient_to_mpz_t (coef, val);
681
682   value_addto (val, val, k);
683
684   ppl_assign_Coefficient_from_mpz_t (coef, val);
685   ppl_Linear_Expression_add_to_coefficient (expr, d, coef);
686   value_clear (val);
687   ppl_delete_Coefficient (coef);
688 }
689
690 /* In the context of scop S, scan E, the right hand side of a scalar
691    evolution function in loop VAR, and translate it to a linear
692    expression EXPR.  */
693
694 static void
695 scan_tree_for_params_right_scev (sese s, tree e, int var,
696                                  ppl_Linear_Expression_t expr)
697 {
698   if (expr)
699     {
700       loop_p loop = get_loop (var);
701       ppl_dimension_type l = sese_loop_depth (s, loop) - 1;
702       Value val;
703
704       /* Scalar evolutions should happen in the sese region.  */
705       gcc_assert (sese_loop_depth (s, loop) > 0);
706
707       /* We can not deal with parametric strides like:
708
709       | p = parameter;
710       |
711       | for i:
712       |   a [i * p] = ...   */
713       gcc_assert (TREE_CODE (e) == INTEGER_CST);
714
715       value_init (val);
716       value_set_si (val, int_cst_value (e));
717       add_value_to_dim (l, expr, val);
718       value_clear (val);
719     }
720 }
721
722 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
723    linear expression EXPR.  K is the multiplier of the constant.  */
724
725 static void
726 scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, Value k)
727 {
728   Value val;
729   ppl_Coefficient_t coef;
730   int v = int_cst_value (cst);
731
732   value_init (val);
733   value_set_si (val, 0);
734
735   /* Necessary to not get "-1 = 2^n - 1". */
736   if (v < 0)
737     value_sub_int (val, val, -v);
738   else
739     value_add_int (val, val, v);
740
741   value_multiply (val, val, k);
742   ppl_new_Coefficient (&coef);
743   ppl_assign_Coefficient_from_mpz_t (coef, val);
744   ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
745   value_clear (val);
746   ppl_delete_Coefficient (coef);
747 }
748
749 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
750    Otherwise returns -1.  */
751
752 static inline int
753 parameter_index_in_region_1 (tree name, sese region)
754 {
755   int i;
756   tree p;
757
758   gcc_assert (TREE_CODE (name) == SSA_NAME);
759
760   for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++)
761     if (p == name)
762       return i;
763
764   return -1;
765 }
766
767 /* When the parameter NAME is in REGION, returns its index in
768    SESE_PARAMS.  Otherwise this function inserts NAME in SESE_PARAMS
769    and returns the index of NAME.  */
770
771 static int
772 parameter_index_in_region (tree name, sese region)
773 {
774   int i;
775
776   gcc_assert (TREE_CODE (name) == SSA_NAME);
777
778   i = parameter_index_in_region_1 (name, region);
779   if (i != -1)
780     return i;
781
782   gcc_assert (SESE_ADD_PARAMS (region));
783
784   i = VEC_length (tree, SESE_PARAMS (region));
785   VEC_safe_push (tree, heap, SESE_PARAMS (region), name);
786   return i;
787 }
788
789 /* In the context of sese S, scan the expression E and translate it to
790    a linear expression C.  When parsing a symbolic multiplication, K
791    represents the constant multiplier of an expression containing
792    parameters.  */
793
794 static void
795 scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c,
796                       Value k)
797 {
798   if (e == chrec_dont_know)
799     return;
800
801   switch (TREE_CODE (e))
802     {
803     case POLYNOMIAL_CHREC:
804       scan_tree_for_params_right_scev (s, CHREC_RIGHT (e),
805                                        CHREC_VARIABLE (e), c);
806       scan_tree_for_params (s, CHREC_LEFT (e), c, k);
807       break;
808
809     case MULT_EXPR:
810       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
811         {
812           if (c)
813             {
814               Value val;
815               gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
816               value_init (val);
817               value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
818               value_multiply (val, val, k);
819               scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val);
820               value_clear (val);
821             }
822           else
823             scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
824         }
825       else
826         {
827           if (c)
828             {
829               Value val;
830               gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
831               value_init (val);
832               value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
833               value_multiply (val, val, k);
834               scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val);
835               value_clear (val);
836             }
837           else
838             scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
839         }
840       break;
841
842     case PLUS_EXPR:
843     case POINTER_PLUS_EXPR:
844       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
845       scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
846       break;
847
848     case MINUS_EXPR:
849       {
850         ppl_Linear_Expression_t tmp_expr = NULL;
851
852         if (c)
853           {
854             ppl_dimension_type dim;
855             ppl_Linear_Expression_space_dimension (c, &dim);
856             ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
857           }
858
859         scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
860         scan_tree_for_params (s, TREE_OPERAND (e, 1), tmp_expr, k);
861
862         if (c)
863           {
864             ppl_subtract_Linear_Expression_from_Linear_Expression (c,
865                                                                    tmp_expr);
866             ppl_delete_Linear_Expression (tmp_expr);
867           }
868
869         break;
870       }
871
872     case NEGATE_EXPR:
873       {
874         ppl_Linear_Expression_t tmp_expr = NULL;
875
876         if (c)
877           {
878             ppl_dimension_type dim;
879             ppl_Linear_Expression_space_dimension (c, &dim);
880             ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
881           }
882
883         scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
884
885         if (c)
886           {
887             ppl_subtract_Linear_Expression_from_Linear_Expression (c,
888                                                                    tmp_expr);
889             ppl_delete_Linear_Expression (tmp_expr);
890           }
891
892         break;
893       }
894
895     case BIT_NOT_EXPR:
896       {
897         ppl_Linear_Expression_t tmp_expr = NULL;
898
899         if (c)
900           {
901             ppl_dimension_type dim;
902             ppl_Linear_Expression_space_dimension (c, &dim);
903             ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
904           }
905
906         scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
907
908         if (c)
909           {
910             ppl_Coefficient_t coef;
911             Value minus_one;
912
913             ppl_subtract_Linear_Expression_from_Linear_Expression (c,
914                                                                    tmp_expr);
915             ppl_delete_Linear_Expression (tmp_expr);
916             value_init (minus_one);
917             value_set_si (minus_one, -1);
918             ppl_new_Coefficient_from_mpz_t (&coef, minus_one);
919             ppl_Linear_Expression_add_to_inhomogeneous (c, coef);
920             value_clear (minus_one);
921             ppl_delete_Coefficient (coef);
922           }
923
924         break;
925       }
926
927     case SSA_NAME:
928       {
929         ppl_dimension_type p = parameter_index_in_region (e, s);
930
931         if (c)
932           {
933             ppl_dimension_type dim;
934             ppl_Linear_Expression_space_dimension (c, &dim);
935             p += dim - sese_nb_params (s);
936             add_value_to_dim (p, c, k);
937           }
938         break;
939       }
940
941     case INTEGER_CST:
942       if (c)
943         scan_tree_for_params_int (e, c, k);
944       break;
945
946     CASE_CONVERT:
947     case NON_LVALUE_EXPR:
948       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
949       break;
950
951    default:
952       gcc_unreachable ();
953       break;
954     }
955 }
956
957 /* Find parameters with respect to REGION in BB. We are looking in memory
958    access functions, conditions and loop bounds.  */
959
960 static void
961 find_params_in_bb (sese region, gimple_bb_p gbb)
962 {
963   int i;
964   unsigned j;
965   data_reference_p dr;
966   gimple stmt;
967   loop_p loop = GBB_BB (gbb)->loop_father;
968   Value one;
969
970   value_init (one);
971   value_set_si (one, 1);
972
973   /* Find parameters in the access functions of data references.  */
974   for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gbb), i, dr); i++)
975     for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
976       scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one);
977
978   /* Find parameters in conditional statements.  */
979   for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gbb), i, stmt); i++)
980     {
981       tree lhs = scalar_evolution_in_region (region, loop,
982                                              gimple_cond_lhs (stmt));
983       tree rhs = scalar_evolution_in_region (region, loop,
984                                              gimple_cond_rhs (stmt));
985
986       scan_tree_for_params (region, lhs, NULL, one);
987       scan_tree_for_params (region, rhs, NULL, one);
988     }
989
990   value_clear (one);
991 }
992
993 /* Record the parameters used in the SCOP.  A variable is a parameter
994    in a scop if it does not vary during the execution of that scop.  */
995
996 static void
997 find_scop_parameters (scop_p scop)
998 {
999   poly_bb_p pbb;
1000   unsigned i;
1001   sese region = SCOP_REGION (scop);
1002   struct loop *loop;
1003   Value one;
1004
1005   value_init (one);
1006   value_set_si (one, 1);
1007
1008   /* Find the parameters used in the loop bounds.  */
1009   for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1010     {
1011       tree nb_iters = number_of_latch_executions (loop);
1012
1013       if (!chrec_contains_symbols (nb_iters))
1014         continue;
1015
1016       nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1017       scan_tree_for_params (region, nb_iters, NULL, one);
1018     }
1019
1020   value_clear (one);
1021
1022   /* Find the parameters used in data accesses.  */
1023   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1024     find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1025
1026   scop_set_nb_params (scop, sese_nb_params (region));
1027   SESE_ADD_PARAMS (region) = false;
1028
1029   ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
1030     (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0);
1031 }
1032
1033 /* Returns a gimple_bb from BB.  */
1034
1035 static inline gimple_bb_p
1036 gbb_from_bb (basic_block bb)
1037 {
1038   return (gimple_bb_p) bb->aux;
1039 }
1040
1041 /* Builds the constraint polyhedra for LOOP in SCOP.  OUTER_PH gives
1042    the constraints for the surrounding loops.  */
1043
1044 static void
1045 build_loop_iteration_domains (scop_p scop, struct loop *loop,
1046                               ppl_Polyhedron_t outer_ph, int nb,
1047                               ppl_Pointset_Powerset_C_Polyhedron_t *domains)
1048 {
1049   int i;
1050   ppl_Polyhedron_t ph;
1051   tree nb_iters = number_of_latch_executions (loop);
1052   ppl_dimension_type dim = nb + 1 + scop_nb_params (scop);
1053   sese region = SCOP_REGION (scop);
1054
1055   {
1056     ppl_const_Constraint_System_t pcs;
1057     ppl_dimension_type *map
1058       = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
1059
1060     ppl_new_C_Polyhedron_from_space_dimension (&ph, dim, 0);
1061     ppl_Polyhedron_get_constraints (outer_ph, &pcs);
1062     ppl_Polyhedron_add_constraints (ph, pcs);
1063
1064     for (i = 0; i < (int) nb; i++)
1065       map[i] = i;
1066     for (i = (int) nb; i < (int) dim - 1; i++)
1067       map[i] = i + 1;
1068     map[dim - 1] = nb;
1069
1070     ppl_Polyhedron_map_space_dimensions (ph, map, dim);
1071     free (map);
1072   }
1073
1074   /* 0 <= loop_i */
1075   {
1076     ppl_Constraint_t lb;
1077     ppl_Linear_Expression_t lb_expr;
1078
1079     ppl_new_Linear_Expression_with_dimension (&lb_expr, dim);
1080     ppl_set_coef (lb_expr, nb, 1);
1081     ppl_new_Constraint (&lb, lb_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1082     ppl_delete_Linear_Expression (lb_expr);
1083     ppl_Polyhedron_add_constraint (ph, lb);
1084     ppl_delete_Constraint (lb);
1085   }
1086
1087   if (TREE_CODE (nb_iters) == INTEGER_CST)
1088     {
1089       ppl_Constraint_t ub;
1090       ppl_Linear_Expression_t ub_expr;
1091
1092       ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1093
1094       /* loop_i <= cst_nb_iters */
1095       ppl_set_coef (ub_expr, nb, -1);
1096       ppl_set_inhomogeneous_tree (ub_expr, nb_iters);
1097       ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1098       ppl_Polyhedron_add_constraint (ph, ub);
1099       ppl_delete_Linear_Expression (ub_expr);
1100       ppl_delete_Constraint (ub);
1101     }
1102   else if (!chrec_contains_undetermined (nb_iters))
1103     {
1104       Value one;
1105       ppl_Constraint_t ub;
1106       ppl_Linear_Expression_t ub_expr;
1107       double_int nit;
1108
1109       value_init (one);
1110       value_set_si (one, 1);
1111       ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1112       nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1113       scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one);
1114       value_clear (one);
1115
1116       /* N <= estimated_nb_iters
1117
1118          FIXME: This is a workaround that should go away once we will
1119          have the PIP algorithm.  */
1120       if (estimated_loop_iterations (loop, true, &nit))
1121         {
1122           Value val;
1123           ppl_Linear_Expression_t nb_iters_le;
1124           ppl_Polyhedron_t pol;
1125           graphite_dim_t n = scop_nb_params (scop);
1126           ppl_Coefficient_t coef;
1127
1128           ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0);
1129           ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le,
1130                                                             ub_expr);
1131
1132           /* Construct the negated number of last iteration in VAL.  */
1133           value_init (val);
1134           mpz_set_double_int (val, nit, false);
1135           value_sub_int (val, val, 1);
1136           value_oppose (val, val);
1137
1138           /* NB_ITERS_LE holds number of last iteration in parametrical form.
1139           Subtract estimated number of last iteration and assert that result
1140           is not positive.  */
1141           ppl_new_Coefficient_from_mpz_t (&coef, val);
1142           ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le, coef);
1143           ppl_delete_Coefficient (coef);
1144           ppl_new_Constraint (&ub, nb_iters_le,
1145                               PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1146           ppl_Polyhedron_add_constraint (pol, ub);
1147
1148           /* Remove all but last N dimensions from POL to obtain constraints
1149              on parameters.  */
1150             {
1151               ppl_dimension_type *dims = XNEWVEC (ppl_dimension_type, dim - n);
1152               graphite_dim_t i;
1153               for (i = 0; i < dim - n; i++)
1154                 dims[i] = i;
1155               ppl_Polyhedron_remove_space_dimensions (pol, dims, dim - n);
1156               XDELETEVEC (dims);
1157             }
1158
1159           /* Add constraints on parameters to SCoP context.  */
1160             {
1161               ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps;
1162               ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1163                (&constraints_ps, pol);
1164               ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1165                (SCOP_CONTEXT (scop), constraints_ps);
1166               ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps);
1167             }
1168
1169           ppl_delete_Polyhedron (pol);
1170           ppl_delete_Linear_Expression (nb_iters_le);
1171           ppl_delete_Constraint (ub);
1172           value_clear (val);
1173         }
1174
1175       /* loop_i <= expr_nb_iters */
1176       ppl_set_coef (ub_expr, nb, -1);
1177       ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1178       ppl_Polyhedron_add_constraint (ph, ub);
1179       ppl_delete_Linear_Expression (ub_expr);
1180       ppl_delete_Constraint (ub);
1181     }
1182   else
1183     gcc_unreachable ();
1184
1185   if (loop->inner && loop_in_sese_p (loop->inner, region))
1186     build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains);
1187
1188   if (nb != 0
1189       && loop->next
1190       && loop_in_sese_p (loop->next, region))
1191     build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains);
1192
1193   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1194     (&domains[loop->num], ph);
1195
1196   ppl_delete_Polyhedron (ph);
1197 }
1198
1199 /* Returns a linear expression for tree T evaluated in PBB.  */
1200
1201 static ppl_Linear_Expression_t
1202 create_linear_expr_from_tree (poly_bb_p pbb, tree t)
1203 {
1204   Value one;
1205   ppl_Linear_Expression_t res;
1206   ppl_dimension_type dim;
1207   sese region = SCOP_REGION (PBB_SCOP (pbb));
1208   loop_p loop = pbb_loop (pbb);
1209
1210   dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
1211   ppl_new_Linear_Expression_with_dimension (&res, dim);
1212
1213   t = scalar_evolution_in_region (region, loop, t);
1214   gcc_assert (!automatically_generated_chrec_p (t));
1215
1216   value_init (one);
1217   value_set_si (one, 1);
1218   scan_tree_for_params (region, t, res, one);
1219   value_clear (one);
1220
1221   return res;
1222 }
1223
1224 /* Returns the ppl constraint type from the gimple tree code CODE.  */
1225
1226 static enum ppl_enum_Constraint_Type
1227 ppl_constraint_type_from_tree_code (enum tree_code code)
1228 {
1229   switch (code)
1230     {
1231     /* We do not support LT and GT to be able to work with C_Polyhedron.
1232        As we work on integer polyhedron "a < b" can be expressed by
1233        "a + 1 <= b".  */
1234     case LT_EXPR:
1235     case GT_EXPR:
1236       gcc_unreachable ();
1237
1238     case LE_EXPR:
1239       return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL;
1240
1241     case GE_EXPR:
1242       return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL;
1243
1244     case EQ_EXPR:
1245       return PPL_CONSTRAINT_TYPE_EQUAL;
1246
1247     default:
1248       gcc_unreachable ();
1249     }
1250 }
1251
1252 /* Add conditional statement STMT to PS.  It is evaluated in PBB and
1253    CODE is used as the comparison operator.  This allows us to invert the
1254    condition or to handle inequalities.  */
1255
1256 static void
1257 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt,
1258                          poly_bb_p pbb, enum tree_code code)
1259 {
1260   Value v;
1261   ppl_Coefficient_t c;
1262   ppl_Linear_Expression_t left, right;
1263   ppl_Constraint_t cstr;
1264   enum ppl_enum_Constraint_Type type;
1265
1266   left = create_linear_expr_from_tree (pbb, gimple_cond_lhs (stmt));
1267   right = create_linear_expr_from_tree (pbb, gimple_cond_rhs (stmt));
1268
1269   /* If we have < or > expressions convert them to <= or >= by adding 1 to
1270      the left or the right side of the expression. */
1271   if (code == LT_EXPR)
1272     {
1273       value_init (v);
1274       value_set_si (v, 1);
1275       ppl_new_Coefficient (&c);
1276       ppl_assign_Coefficient_from_mpz_t (c, v);
1277       ppl_Linear_Expression_add_to_inhomogeneous (left, c);
1278       ppl_delete_Coefficient (c);
1279       value_clear (v);
1280
1281       code = LE_EXPR;
1282     }
1283   else if (code == GT_EXPR)
1284     {
1285       value_init (v);
1286       value_set_si (v, 1);
1287       ppl_new_Coefficient (&c);
1288       ppl_assign_Coefficient_from_mpz_t (c, v);
1289       ppl_Linear_Expression_add_to_inhomogeneous (right, c);
1290       ppl_delete_Coefficient (c);
1291       value_clear (v);
1292
1293       code = GE_EXPR;
1294     }
1295
1296   type = ppl_constraint_type_from_tree_code (code);
1297
1298   ppl_subtract_Linear_Expression_from_Linear_Expression (left, right);
1299
1300   ppl_new_Constraint (&cstr, left, type);
1301   ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps, cstr);
1302
1303   ppl_delete_Constraint (cstr);
1304   ppl_delete_Linear_Expression (left);
1305   ppl_delete_Linear_Expression (right);
1306 }
1307
1308 /* Add conditional statement STMT to pbb.  CODE is used as the comparision
1309    operator.  This allows us to invert the condition or to handle
1310    inequalities.  */
1311
1312 static void
1313 add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
1314 {
1315   if (code == NE_EXPR)
1316     {
1317       ppl_Pointset_Powerset_C_Polyhedron_t left = PBB_DOMAIN (pbb);
1318       ppl_Pointset_Powerset_C_Polyhedron_t right;
1319       ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1320         (&right, left);
1321       add_condition_to_domain (left, stmt, pbb, LT_EXPR);
1322       add_condition_to_domain (right, stmt, pbb, GT_EXPR);
1323       ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left,
1324                                                                right);
1325       ppl_delete_Pointset_Powerset_C_Polyhedron (right);
1326     }
1327   else
1328     add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code);
1329 }
1330
1331 /* Add conditions to the domain of PBB.  */
1332
1333 static void
1334 add_conditions_to_domain (poly_bb_p pbb)
1335 {
1336   unsigned int i;
1337   gimple stmt;
1338   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1339   VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb);
1340
1341   if (VEC_empty (gimple, conditions))
1342     return;
1343
1344   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
1345     switch (gimple_code (stmt))
1346       {
1347       case GIMPLE_COND:
1348           {
1349             enum tree_code code = gimple_cond_code (stmt);
1350
1351             /* The conditions for ELSE-branches are inverted.  */
1352             if (VEC_index (gimple, gbb->condition_cases, i) == NULL)
1353               code = invert_tree_comparison (code, false);
1354
1355             add_condition_to_pbb (pbb, stmt, code);
1356             break;
1357           }
1358
1359       case GIMPLE_SWITCH:
1360         /* Switch statements are not supported right now - fall throught.  */
1361
1362       default:
1363         gcc_unreachable ();
1364         break;
1365       }
1366 }
1367
1368 /* Structure used to pass data to dom_walk.  */
1369
1370 struct bsc
1371 {
1372   VEC (gimple, heap) **conditions, **cases;
1373   sese region;
1374 };
1375
1376 /* Returns non NULL when BB has a single predecessor and the last
1377    statement of that predecessor is a COND_EXPR.  */
1378
1379 static gimple
1380 single_pred_cond (basic_block bb)
1381 {
1382   if (single_pred_p (bb))
1383     {
1384       edge e = single_pred_edge (bb);
1385       basic_block pred = e->src;
1386       gimple stmt = last_stmt (pred);
1387
1388       if (stmt && gimple_code (stmt) == GIMPLE_COND)
1389         return stmt;
1390     }
1391   return NULL;
1392 }
1393
1394 /* Call-back for dom_walk executed before visiting the dominated
1395    blocks.  */
1396
1397 static void
1398 build_sese_conditions_before (struct dom_walk_data *dw_data,
1399                               basic_block bb)
1400 {
1401   struct bsc *data = (struct bsc *) dw_data->global_data;
1402   VEC (gimple, heap) **conditions = data->conditions;
1403   VEC (gimple, heap) **cases = data->cases;
1404   gimple_bb_p gbb = gbb_from_bb (bb);
1405   gimple stmt = single_pred_cond (bb);
1406
1407   if (!bb_in_sese_p (bb, data->region))
1408     return;
1409
1410   if (stmt)
1411     {
1412       edge e = single_pred_edge (bb);
1413
1414       VEC_safe_push (gimple, heap, *conditions, stmt);
1415
1416       if (e->flags & EDGE_TRUE_VALUE)
1417         VEC_safe_push (gimple, heap, *cases, stmt);
1418       else
1419         VEC_safe_push (gimple, heap, *cases, NULL);
1420     }
1421
1422   if (gbb)
1423     {
1424       GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
1425       GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
1426     }
1427 }
1428
1429 /* Call-back for dom_walk executed after visiting the dominated
1430    blocks.  */
1431
1432 static void
1433 build_sese_conditions_after (struct dom_walk_data *dw_data,
1434                              basic_block bb)
1435 {
1436   struct bsc *data = (struct bsc *) dw_data->global_data;
1437   VEC (gimple, heap) **conditions = data->conditions;
1438   VEC (gimple, heap) **cases = data->cases;
1439
1440   if (!bb_in_sese_p (bb, data->region))
1441     return;
1442
1443   if (single_pred_cond (bb))
1444     {
1445       VEC_pop (gimple, *conditions);
1446       VEC_pop (gimple, *cases);
1447     }
1448 }
1449
1450 /* Record all conditions in REGION.  */
1451
1452 static void
1453 build_sese_conditions (sese region)
1454 {
1455   struct dom_walk_data walk_data;
1456   VEC (gimple, heap) *conditions = VEC_alloc (gimple, heap, 3);
1457   VEC (gimple, heap) *cases = VEC_alloc (gimple, heap, 3);
1458   struct bsc data;
1459
1460   data.conditions = &conditions;
1461   data.cases = &cases;
1462   data.region = region;
1463
1464   walk_data.dom_direction = CDI_DOMINATORS;
1465   walk_data.initialize_block_local_data = NULL;
1466   walk_data.before_dom_children = build_sese_conditions_before;
1467   walk_data.after_dom_children = build_sese_conditions_after;
1468   walk_data.global_data = &data;
1469   walk_data.block_local_data_size = 0;
1470
1471   init_walk_dominator_tree (&walk_data);
1472   walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region));
1473   fini_walk_dominator_tree (&walk_data);
1474
1475   VEC_free (gimple, heap, conditions);
1476   VEC_free (gimple, heap, cases);
1477 }
1478
1479 /* Traverses all the GBBs of the SCOP and add their constraints to the
1480    iteration domains.  */
1481
1482 static void
1483 add_conditions_to_constraints (scop_p scop)
1484 {
1485   int i;
1486   poly_bb_p pbb;
1487
1488   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1489     add_conditions_to_domain (pbb);
1490 }
1491
1492 /* Add constraints on the possible values of parameter P from the type
1493    of P.  */
1494
1495 static void
1496 add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
1497 {
1498   ppl_Constraint_t cstr;
1499   ppl_Linear_Expression_t le;
1500   tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p);
1501   tree type = TREE_TYPE (parameter);
1502   tree lb = NULL_TREE;
1503   tree ub = NULL_TREE;
1504
1505   if (INTEGRAL_TYPE_P (type))
1506     {
1507       lb = TYPE_MIN_VALUE (type);
1508       ub = TYPE_MAX_VALUE (type);
1509     }
1510   else if (POINTER_TYPE_P (type))
1511     {
1512       lb = TYPE_MIN_VALUE (unsigned_type_node);
1513       ub = TYPE_MAX_VALUE (unsigned_type_node);
1514     }
1515
1516   if (lb)
1517     {
1518       ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1519       ppl_set_coef (le, p, -1);
1520       ppl_set_inhomogeneous_tree (le, lb);
1521       ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1522       ppl_Polyhedron_add_constraint (context, cstr);
1523       ppl_delete_Linear_Expression (le);
1524       ppl_delete_Constraint (cstr);
1525     }
1526
1527   if (ub)
1528     {
1529       ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1530       ppl_set_coef (le, p, -1);
1531       ppl_set_inhomogeneous_tree (le, ub);
1532       ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1533       ppl_Polyhedron_add_constraint (context, cstr);
1534       ppl_delete_Linear_Expression (le);
1535       ppl_delete_Constraint (cstr);
1536     }
1537 }
1538
1539 /* Build the context of the SCOP.  The context usually contains extra
1540    constraints that are added to the iteration domains that constrain
1541    some parameters.  */
1542
1543 static void
1544 build_scop_context (scop_p scop)
1545 {
1546   ppl_Polyhedron_t context;
1547   ppl_Pointset_Powerset_C_Polyhedron_t ps;
1548   graphite_dim_t p, n = scop_nb_params (scop);
1549
1550   ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0);
1551
1552   for (p = 0; p < n; p++)
1553     add_param_constraints (scop, context, p);
1554
1555   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1556     (&ps, context);
1557   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1558     (SCOP_CONTEXT (scop), ps);
1559
1560   ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
1561   ppl_delete_Polyhedron (context);
1562 }
1563
1564 /* Build the iteration domains: the loops belonging to the current
1565    SCOP, and that vary for the execution of the current basic block.
1566    Returns false if there is no loop in SCOP.  */
1567
1568 static void
1569 build_scop_iteration_domain (scop_p scop)
1570 {
1571   struct loop *loop;
1572   sese region = SCOP_REGION (scop);
1573   int i;
1574   ppl_Polyhedron_t ph;
1575   poly_bb_p pbb;
1576   int nb_loops = number_of_loops ();
1577   ppl_Pointset_Powerset_C_Polyhedron_t *domains
1578     = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t, nb_loops);
1579
1580   for (i = 0; i < nb_loops; i++)
1581     domains[i] = NULL;
1582
1583   ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0);
1584
1585   for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1586     if (!loop_in_sese_p (loop_outer (loop), region))
1587       build_loop_iteration_domains (scop, loop, ph, 0, domains);
1588
1589   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1590     if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num])
1591       ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1592         (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
1593          domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]);
1594     else
1595       ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1596         (&PBB_DOMAIN (pbb), ph);
1597
1598   for (i = 0; i < nb_loops; i++)
1599     if (domains[i])
1600       ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]);
1601
1602   ppl_delete_Polyhedron (ph);
1603   free (domains);
1604 }
1605
1606 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1607    data reference DR.  ACCESSP_NB_DIMS is the dimension of the
1608    ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1609    domain.  */
1610
1611 static void
1612 pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr,
1613                    ppl_dimension_type accessp_nb_dims,
1614                    ppl_dimension_type dom_nb_dims)
1615 {
1616   ppl_Linear_Expression_t alias;
1617   ppl_Constraint_t cstr;
1618   int alias_set_num = 0;
1619   base_alias_pair *bap = (base_alias_pair *)(dr->aux);
1620
1621   if (bap && bap->alias_set)
1622     alias_set_num = *(bap->alias_set);
1623
1624   ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims);
1625
1626   ppl_set_coef (alias, dom_nb_dims, 1);
1627   ppl_set_inhomogeneous (alias, -alias_set_num);
1628   ppl_new_Constraint (&cstr, alias, PPL_CONSTRAINT_TYPE_EQUAL);
1629   ppl_Polyhedron_add_constraint (accesses, cstr);
1630
1631   ppl_delete_Linear_Expression (alias);
1632   ppl_delete_Constraint (cstr);
1633 }
1634
1635 /* Add to ACCESSES polyhedron equalities defining the access functions
1636    to the memory.  ACCESSP_NB_DIMS is the dimension of the ACCESSES
1637    polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1638    PBB is the poly_bb_p that contains the data reference DR.  */
1639
1640 static void
1641 pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr,
1642                          ppl_dimension_type accessp_nb_dims,
1643                          ppl_dimension_type dom_nb_dims,
1644                          poly_bb_p pbb)
1645 {
1646   int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1647   Value v;
1648   scop_p scop = PBB_SCOP (pbb);
1649   sese region = SCOP_REGION (scop);
1650
1651   value_init (v);
1652
1653   for (i = 0; i < nb_subscripts; i++)
1654     {
1655       ppl_Linear_Expression_t fn, access;
1656       ppl_Constraint_t cstr;
1657       ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1658       tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i);
1659
1660       ppl_new_Linear_Expression_with_dimension (&fn, dom_nb_dims);
1661       ppl_new_Linear_Expression_with_dimension (&access, accessp_nb_dims);
1662
1663       value_set_si (v, 1);
1664       scan_tree_for_params (region, afn, fn, v);
1665       ppl_assign_Linear_Expression_from_Linear_Expression (access, fn);
1666
1667       ppl_set_coef (access, subscript, -1);
1668       ppl_new_Constraint (&cstr, access, PPL_CONSTRAINT_TYPE_EQUAL);
1669       ppl_Polyhedron_add_constraint (accesses, cstr);
1670
1671       ppl_delete_Linear_Expression (fn);
1672       ppl_delete_Linear_Expression (access);
1673       ppl_delete_Constraint (cstr);
1674     }
1675
1676   value_clear (v);
1677 }
1678
1679 /* Add constrains representing the size of the accessed data to the
1680    ACCESSES polyhedron.  ACCESSP_NB_DIMS is the dimension of the
1681    ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1682    domain.  */
1683
1684 static void
1685 pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr,
1686                          ppl_dimension_type accessp_nb_dims,
1687                          ppl_dimension_type dom_nb_dims)
1688 {
1689   tree ref = DR_REF (dr);
1690   int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1691
1692   for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
1693     {
1694       ppl_Linear_Expression_t expr;
1695       ppl_Constraint_t cstr;
1696       ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1697       tree low, high;
1698
1699       if (TREE_CODE (ref) != ARRAY_REF)
1700         break;
1701
1702       low = array_ref_low_bound (ref);
1703
1704       /* subscript - low >= 0 */
1705       if (host_integerp (low, 0))
1706         {
1707           ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1708           ppl_set_coef (expr, subscript, 1);
1709
1710           ppl_set_inhomogeneous (expr, -int_cst_value (low));
1711
1712           ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1713           ppl_Polyhedron_add_constraint (accesses, cstr);
1714           ppl_delete_Linear_Expression (expr);
1715           ppl_delete_Constraint (cstr);
1716         }
1717
1718       high = array_ref_up_bound (ref);
1719
1720       /* high - subscript >= 0 */
1721       if (high && host_integerp (high, 0)
1722           /* 1-element arrays at end of structures may extend over
1723              their declared size.  */
1724           && !(array_at_struct_end_p (ref)
1725                && operand_equal_p (low, high, 0)))
1726         {
1727           ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1728           ppl_set_coef (expr, subscript, -1);
1729
1730           ppl_set_inhomogeneous (expr, int_cst_value (high));
1731
1732           ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1733           ppl_Polyhedron_add_constraint (accesses, cstr);
1734           ppl_delete_Linear_Expression (expr);
1735           ppl_delete_Constraint (cstr);
1736         }
1737     }
1738 }
1739
1740 /* Build data accesses for DR in PBB.  */
1741
1742 static void
1743 build_poly_dr (data_reference_p dr, poly_bb_p pbb)
1744 {
1745   ppl_Polyhedron_t accesses;
1746   ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps;
1747   ppl_dimension_type dom_nb_dims;
1748   ppl_dimension_type accessp_nb_dims;
1749   int dr_base_object_set;
1750
1751   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb),
1752                                                       &dom_nb_dims);
1753   accessp_nb_dims = dom_nb_dims + 1 + DR_NUM_DIMENSIONS (dr);
1754
1755   ppl_new_C_Polyhedron_from_space_dimension (&accesses, accessp_nb_dims, 0);
1756
1757   pdr_add_alias_set (accesses, dr, accessp_nb_dims, dom_nb_dims);
1758   pdr_add_memory_accesses (accesses, dr, accessp_nb_dims, dom_nb_dims, pbb);
1759   pdr_add_data_dimensions (accesses, dr, accessp_nb_dims, dom_nb_dims);
1760
1761   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps,
1762                                                             accesses);
1763   ppl_delete_Polyhedron (accesses);
1764
1765   if (dr->aux)
1766     dr_base_object_set = ((base_alias_pair *)(dr->aux))->base_obj_set;
1767
1768   new_poly_dr (pbb, dr_base_object_set, accesses_ps, DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
1769                dr, DR_NUM_DIMENSIONS (dr));
1770 }
1771
1772 /* Write to FILE the alias graph of data references in DIMACS format.  */
1773
1774 static inline bool
1775 write_alias_graph_to_ascii_dimacs (FILE *file, char *comment,
1776                                    VEC (data_reference_p, heap) *drs)
1777 {
1778   int num_vertex = VEC_length (data_reference_p, drs);
1779   int edge_num = 0;
1780   data_reference_p dr1, dr2;
1781   int i, j;
1782
1783   if (num_vertex == 0)
1784     return true;
1785
1786   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1787     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1788       if (dr_may_alias_p (dr1, dr2))
1789         edge_num++;
1790
1791   fprintf (file, "$\n");
1792
1793   if (comment)
1794     fprintf (file, "c %s\n", comment);
1795
1796   fprintf (file, "p edge %d %d\n", num_vertex, edge_num);
1797
1798   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1799     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1800       if (dr_may_alias_p (dr1, dr2))
1801         fprintf (file, "e %d %d\n", i + 1, j + 1);
1802
1803   return true;
1804 }
1805
1806 /* Write to FILE the alias graph of data references in DOT format.  */
1807
1808 static inline bool
1809 write_alias_graph_to_ascii_dot (FILE *file, char *comment,
1810                                 VEC (data_reference_p, heap) *drs)
1811 {
1812   int num_vertex = VEC_length (data_reference_p, drs);
1813   data_reference_p dr1, dr2;
1814   int i, j;
1815
1816   if (num_vertex == 0)
1817     return true;
1818
1819   fprintf (file, "$\n");
1820
1821   if (comment)
1822     fprintf (file, "c %s\n", comment);
1823
1824   /* First print all the vertices.  */
1825   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1826     fprintf (file, "n%d;\n", i);
1827
1828   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1829     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1830       if (dr_may_alias_p (dr1, dr2))
1831         fprintf (file, "n%d n%d\n", i, j);
1832
1833   return true;
1834 }
1835
1836 /* Write to FILE the alias graph of data references in ECC format.  */
1837
1838 static inline bool
1839 write_alias_graph_to_ascii_ecc (FILE *file, char *comment,
1840                                 VEC (data_reference_p, heap) *drs)
1841 {
1842   int num_vertex = VEC_length (data_reference_p, drs);
1843   data_reference_p dr1, dr2;
1844   int i, j;
1845
1846   if (num_vertex == 0)
1847     return true;
1848
1849   fprintf (file, "$\n");
1850
1851   if (comment)
1852     fprintf (file, "c %s\n", comment);
1853
1854   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1855     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1856       if (dr_may_alias_p (dr1, dr2))
1857         fprintf (file, "%d %d\n", i, j);
1858
1859   return true;
1860 }
1861
1862 /* Check if DR1 and DR2 are in the same object set.  */
1863
1864 static bool
1865 dr_same_base_object_p (const struct data_reference *dr1,
1866                        const struct data_reference *dr2)
1867 {
1868   return operand_equal_p (DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), 0);
1869 }
1870
1871 /* Uses DFS component number as representative of alias-sets. Also tests for
1872    optimality by verifying if every connected component is a clique. Returns
1873    true (1) if the above test is true, and false (0) otherwise.  */
1874
1875 static int
1876 build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs)
1877 {
1878   int num_vertices = VEC_length (data_reference_p, drs);
1879   struct graph *g = new_graph (num_vertices);
1880   data_reference_p dr1, dr2;
1881   int i, j;
1882   int num_connected_components;
1883   int v_indx1, v_indx2, num_vertices_in_component;
1884   int *all_vertices;
1885   int *vertices;
1886   struct graph_edge *e;
1887   int this_component_is_clique;
1888   int all_components_are_cliques = 1;
1889
1890   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1891     for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1892       if (dr_may_alias_p (dr1, dr2))
1893         {
1894           add_edge (g, i, j);
1895           add_edge (g, j, i);
1896         }
1897
1898   all_vertices = XNEWVEC (int, num_vertices);
1899   vertices = XNEWVEC (int, num_vertices);
1900   for (i = 0; i < num_vertices; i++)
1901     all_vertices[i] = i;
1902
1903   num_connected_components = graphds_dfs (g, all_vertices, num_vertices,
1904                                           NULL, true, NULL);
1905   for (i = 0; i < g->n_vertices; i++)
1906     {
1907       data_reference_p dr = VEC_index (data_reference_p, drs, i);
1908       base_alias_pair *bap;
1909
1910       if (dr->aux)
1911         bap = (base_alias_pair *)(dr->aux);
1912
1913       bap->alias_set = XNEW (int);
1914       *(bap->alias_set) = g->vertices[i].component + 1;
1915     }
1916
1917   /* Verify if the DFS numbering results in optimal solution.  */
1918   for (i = 0; i < num_connected_components; i++)
1919     {
1920       num_vertices_in_component = 0;
1921       /* Get all vertices whose DFS component number is the same as i.  */
1922       for (j = 0; j < num_vertices; j++)
1923         if (g->vertices[j].component == i)
1924           vertices[num_vertices_in_component++] = j;
1925
1926       /* Now test if the vertices in 'vertices' form a clique, by testing
1927          for edges among each pair.  */
1928       this_component_is_clique = 1;
1929       for (v_indx1 = 0; v_indx1 < num_vertices_in_component; v_indx1++)
1930         {
1931           for (v_indx2 = v_indx1+1; v_indx2 < num_vertices_in_component; v_indx2++)
1932             {
1933               /* Check if the two vertices are connected by iterating
1934                  through all the edges which have one of these are source.  */
1935               e = g->vertices[vertices[v_indx2]].pred;
1936               while (e)
1937                 {
1938                   if (e->src == vertices[v_indx1])
1939                     break;
1940                   e = e->pred_next;
1941                 }
1942               if (!e)
1943                 {
1944                   this_component_is_clique = 0;
1945                   break;
1946                 }
1947             }
1948           if (!this_component_is_clique)
1949             all_components_are_cliques = 0;
1950         }
1951     }
1952
1953   free (all_vertices);
1954   free (vertices);
1955   free_graph (g);
1956   return all_components_are_cliques;
1957 }
1958
1959 /* Group each data reference in DRS with it's base object set num.  */
1960
1961 static void
1962 build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs)
1963 {
1964   int num_vertex = VEC_length (data_reference_p, drs);
1965   struct graph *g = new_graph (num_vertex);
1966   data_reference_p dr1, dr2;
1967   int i, j;
1968   int *queue;
1969
1970   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1971     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1972       if (dr_same_base_object_p (dr1, dr2))
1973         {
1974           add_edge (g, i, j);
1975           add_edge (g, j, i);
1976         }
1977
1978   queue = XNEWVEC (int, num_vertex);
1979   for (i = 0; i < num_vertex; i++)
1980     queue[i] = i;
1981
1982   graphds_dfs (g, queue, num_vertex, NULL, true, NULL);
1983
1984   for (i = 0; i < g->n_vertices; i++)
1985     {
1986       data_reference_p dr = VEC_index (data_reference_p, drs, i);
1987       base_alias_pair *bap;
1988
1989       if (dr->aux)
1990         bap = (base_alias_pair *)(dr->aux);
1991
1992       bap->base_obj_set = g->vertices[i].component + 1;
1993     }
1994
1995   free (queue);
1996   free_graph (g);
1997 }
1998
1999 /* Build the data references for PBB.  */
2000
2001 static void
2002 build_pbb_drs (poly_bb_p pbb)
2003 {
2004   int j;
2005   data_reference_p dr;
2006   VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb));
2007
2008   for (j = 0; VEC_iterate (data_reference_p, gbb_drs, j, dr); j++)
2009     build_poly_dr (dr, pbb);
2010 }
2011
2012 /* Dump to file the alias graphs for the data references in DRS.  */
2013
2014 static void
2015 dump_alias_graphs (VEC (data_reference_p, heap) *drs)
2016 {
2017   char comment[100];
2018   FILE *file_dimacs, *file_ecc, *file_dot;
2019
2020   file_dimacs = fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2021   if (file_dimacs)
2022     {
2023       snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2024                 current_function_name ());
2025       write_alias_graph_to_ascii_dimacs (file_dimacs, comment, drs);
2026       fclose (file_dimacs);
2027     }
2028
2029   file_ecc = fopen ("/tmp/dr_alias_graph_ecc", "ab");
2030   if (file_ecc)
2031     {
2032       snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2033                 current_function_name ());
2034       write_alias_graph_to_ascii_ecc (file_ecc, comment, drs);
2035       fclose (file_ecc);
2036     }
2037
2038   file_dot = fopen ("/tmp/dr_alias_graph_dot", "ab");
2039   if (file_dot)
2040     {
2041       snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2042                 current_function_name ());
2043       write_alias_graph_to_ascii_dot (file_dot, comment, drs);
2044       fclose (file_dot);
2045     }
2046 }
2047
2048 /* Build data references in SCOP.  */
2049
2050 static void
2051 build_scop_drs (scop_p scop)
2052 {
2053   int i, j;
2054   poly_bb_p pbb;
2055   data_reference_p dr;
2056   VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
2057
2058   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2059     for (j = 0; VEC_iterate (data_reference_p,
2060                              GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++)
2061       VEC_safe_push (data_reference_p, heap, drs, dr);
2062
2063   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr); i++)
2064     dr->aux = XNEW (base_alias_pair);
2065
2066   if (!build_alias_set_optimal_p (drs))
2067     {
2068       /* TODO: Add support when building alias set is not optimal.  */
2069       ;
2070     }
2071
2072   build_base_obj_set_for_drs (drs);
2073
2074   /* When debugging, enable the following code.  This cannot be used
2075      in production compilers.  */
2076   if (0)
2077     dump_alias_graphs (drs);
2078
2079   VEC_free (data_reference_p, heap, drs);
2080
2081   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2082     build_pbb_drs (pbb);
2083 }
2084
2085 /* Return a gsi at the position of the phi node STMT.  */
2086
2087 static gimple_stmt_iterator
2088 gsi_for_phi_node (gimple stmt)
2089 {
2090   gimple_stmt_iterator psi;
2091   basic_block bb = gimple_bb (stmt);
2092
2093   for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2094     if (stmt == gsi_stmt (psi))
2095       return psi;
2096
2097   gcc_unreachable ();
2098   return psi;
2099 }
2100
2101 /* Insert the assignment "RES := VAR" just after the definition of VAR.  */
2102
2103 static void
2104 insert_out_of_ssa_copy (tree res, tree var)
2105 {
2106   gimple stmt;
2107   gimple_seq stmts;
2108   gimple_stmt_iterator si;
2109   gimple_stmt_iterator gsi;
2110
2111   var = force_gimple_operand (var, &stmts, true, NULL_TREE);
2112   stmt = gimple_build_assign (res, var);
2113   if (!stmts)
2114     stmts = gimple_seq_alloc ();
2115   si = gsi_last (stmts);
2116   gsi_insert_after (&si, stmt, GSI_NEW_STMT);
2117
2118   stmt = SSA_NAME_DEF_STMT (var);
2119   if (gimple_code (stmt) == GIMPLE_PHI)
2120     {
2121       gsi = gsi_after_labels (gimple_bb (stmt));
2122       gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2123     }
2124   else
2125     {
2126       gsi = gsi_for_stmt (stmt);
2127       gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
2128     }
2129 }
2130
2131 /* Insert on edge E the assignment "RES := EXPR".  */
2132
2133 static void
2134 insert_out_of_ssa_copy_on_edge (edge e, tree res, tree expr)
2135 {
2136   gimple_stmt_iterator gsi;
2137   gimple_seq stmts;
2138   tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2139   gimple stmt = gimple_build_assign (res, var);
2140
2141   if (!stmts)
2142     stmts = gimple_seq_alloc ();
2143
2144   gsi = gsi_last (stmts);
2145   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2146   gsi_insert_seq_on_edge (e, stmts);
2147   gsi_commit_edge_inserts ();
2148 }
2149
2150 /* Creates a zero dimension array of the same type as VAR.  */
2151
2152 static tree
2153 create_zero_dim_array (tree var, const char *base_name)
2154 {
2155   tree index_type = build_index_type (integer_zero_node);
2156   tree elt_type = TREE_TYPE (var);
2157   tree array_type = build_array_type (elt_type, index_type);
2158   tree base = create_tmp_var (array_type, base_name);
2159
2160   add_referenced_var (base);
2161
2162   return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
2163                  NULL_TREE);
2164 }
2165
2166 /* Returns true when PHI is a loop close phi node.  */
2167
2168 static bool
2169 scalar_close_phi_node_p (gimple phi)
2170 {
2171   if (gimple_code (phi) != GIMPLE_PHI
2172       || !is_gimple_reg (gimple_phi_result (phi)))
2173     return false;
2174
2175   return (gimple_phi_num_args (phi) == 1);
2176 }
2177
2178 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2179    dimension array for it.  */
2180
2181 static void
2182 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi)
2183 {
2184   gimple phi = gsi_stmt (*psi);
2185   tree res = gimple_phi_result (phi);
2186   tree var = SSA_NAME_VAR (res);
2187   tree zero_dim_array = create_zero_dim_array (var, "Close_Phi");
2188   gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
2189   gimple stmt = gimple_build_assign (res, zero_dim_array);
2190   tree arg = gimple_phi_arg_def (phi, 0);
2191
2192   if (TREE_CODE (arg) == SSA_NAME)
2193     insert_out_of_ssa_copy (zero_dim_array, arg);
2194   else
2195     insert_out_of_ssa_copy_on_edge (single_pred_edge (gimple_bb (phi)),
2196                                     zero_dim_array, arg);
2197
2198   remove_phi_node (psi, false);
2199   gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2200   SSA_NAME_DEF_STMT (res) = stmt;
2201 }
2202
2203 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2204    dimension array for it.  */
2205
2206 static void
2207 rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi)
2208 {
2209   size_t i;
2210   gimple phi = gsi_stmt (*psi);
2211   basic_block bb = gimple_bb (phi);
2212   tree res = gimple_phi_result (phi);
2213   tree var = SSA_NAME_VAR (res);
2214   tree zero_dim_array = create_zero_dim_array (var, "General_Reduction");
2215   gimple_stmt_iterator gsi;
2216   gimple stmt;
2217   gimple_seq stmts;
2218
2219   for (i = 0; i < gimple_phi_num_args (phi); i++)
2220     {
2221       tree arg = gimple_phi_arg_def (phi, i);
2222
2223       /* Try to avoid the insertion on edges as much as possible: this
2224          would avoid the insertion of code on loop latch edges, making
2225          the pattern matching of the vectorizer happy, or it would
2226          avoid the insertion of useless basic blocks.  Note that it is
2227          incorrect to insert out of SSA copies close by their
2228          definition when they are more than two loop levels apart:
2229          for example, starting from a double nested loop
2230
2231          | a = ...
2232          | loop_1
2233          |  loop_2
2234          |    b = phi (a, c)
2235          |    c = ...
2236          |  end_2
2237          | end_1
2238
2239          the following transform is incorrect
2240
2241          | a = ...
2242          | Red[0] = a
2243          | loop_1
2244          |  loop_2
2245          |    b = Red[0]
2246          |    c = ...
2247          |    Red[0] = c
2248          |  end_2
2249          | end_1
2250
2251          whereas inserting the copy on the incoming edge is correct
2252
2253          | a = ...
2254          | loop_1
2255          |  Red[0] = a
2256          |  loop_2
2257          |    b = Red[0]
2258          |    c = ...
2259          |    Red[0] = c
2260          |  end_2
2261          | end_1
2262       */
2263       if (TREE_CODE (arg) == SSA_NAME
2264           && is_gimple_reg (arg)
2265           && gimple_bb (SSA_NAME_DEF_STMT (arg))
2266           && (flow_bb_inside_loop_p (bb->loop_father,
2267                                      gimple_bb (SSA_NAME_DEF_STMT (arg)))
2268               || flow_bb_inside_loop_p (loop_outer (bb->loop_father),
2269                                         gimple_bb (SSA_NAME_DEF_STMT (arg)))))
2270         insert_out_of_ssa_copy (zero_dim_array, arg);
2271       else
2272         insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi, i),
2273                                         zero_dim_array, arg);
2274     }
2275
2276   var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE);
2277
2278   if (!stmts)
2279     stmts = gimple_seq_alloc ();
2280
2281   stmt = gimple_build_assign (res, var);
2282   remove_phi_node (psi, false);
2283   SSA_NAME_DEF_STMT (res) = stmt;
2284
2285   gsi = gsi_last (stmts);
2286   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2287
2288   gsi = gsi_after_labels (bb);
2289   gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2290 }
2291
2292 /* Return true when DEF can be analyzed in REGION by the scalar
2293    evolution analyzer.  */
2294
2295 static bool
2296 scev_analyzable_p (tree def, sese region)
2297 {
2298   gimple stmt = SSA_NAME_DEF_STMT (def);
2299   loop_p loop = loop_containing_stmt (stmt);
2300   tree scev = scalar_evolution_in_region (region, loop, def);
2301
2302   return !chrec_contains_undetermined (scev);
2303 }
2304
2305 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2306    read from ZERO_DIM_ARRAY.  */
2307
2308 static void
2309 rewrite_cross_bb_scalar_dependence (tree zero_dim_array, tree def, gimple use_stmt)
2310 {
2311   tree var = SSA_NAME_VAR (def);
2312   gimple name_stmt = gimple_build_assign (var, zero_dim_array);
2313   tree name = make_ssa_name (var, name_stmt);
2314   ssa_op_iter iter;
2315   use_operand_p use_p;
2316   gimple_stmt_iterator gsi;
2317
2318   gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2319
2320   gimple_assign_set_lhs (name_stmt, name);
2321
2322   gsi = gsi_for_stmt (use_stmt);
2323   gsi_insert_before (&gsi, name_stmt, GSI_NEW_STMT);
2324
2325   FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2326     if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2327       replace_exp (use_p, name);
2328
2329   update_stmt (use_stmt);
2330 }
2331
2332 /* Rewrite the scalar dependences crossing the boundary of the BB
2333    containing STMT with an array.  */
2334
2335 static void
2336 rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi)
2337 {
2338   gimple stmt = gsi_stmt (*gsi);
2339   imm_use_iterator imm_iter;
2340   tree def;
2341   basic_block def_bb;
2342   tree zero_dim_array = NULL_TREE;
2343   gimple use_stmt;
2344
2345   if (gimple_code (stmt) != GIMPLE_ASSIGN)
2346     return;
2347
2348   def = gimple_assign_lhs (stmt);
2349   if (!is_gimple_reg (def)
2350       || scev_analyzable_p (def, region))
2351     return;
2352
2353   def_bb = gimple_bb (stmt);
2354
2355   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2356     if (def_bb != gimple_bb (use_stmt)
2357         && gimple_code (use_stmt) != GIMPLE_PHI)
2358       {
2359         if (!zero_dim_array)
2360           {
2361             zero_dim_array = create_zero_dim_array
2362               (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence");
2363             insert_out_of_ssa_copy (zero_dim_array, def);
2364             gsi_next (gsi);
2365           }
2366
2367         rewrite_cross_bb_scalar_dependence (zero_dim_array, def, use_stmt);
2368       }
2369 }
2370
2371 /* Rewrite out of SSA all the reduction phi nodes of SCOP.  */
2372
2373 static void
2374 rewrite_reductions_out_of_ssa (scop_p scop)
2375 {
2376   basic_block bb;
2377   gimple_stmt_iterator psi;
2378   sese region = SCOP_REGION (scop);
2379
2380   FOR_EACH_BB (bb)
2381     if (bb_in_sese_p (bb, region))
2382       for (psi = gsi_start_phis (bb); !gsi_end_p (psi);)
2383         {
2384           if (scalar_close_phi_node_p (gsi_stmt (psi)))
2385             rewrite_close_phi_out_of_ssa (&psi);
2386           else if (reduction_phi_p (region, &psi))
2387             rewrite_phi_out_of_ssa (&psi);
2388         }
2389
2390   update_ssa (TODO_update_ssa);
2391 #ifdef ENABLE_CHECKING
2392   verify_ssa (false);
2393   verify_loop_closed_ssa ();
2394 #endif
2395
2396   FOR_EACH_BB (bb)
2397     if (bb_in_sese_p (bb, region))
2398       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
2399         rewrite_cross_bb_scalar_deps (region, &psi);
2400
2401   update_ssa (TODO_update_ssa);
2402 #ifdef ENABLE_CHECKING
2403   verify_ssa (false);
2404   verify_loop_closed_ssa ();
2405 #endif
2406 }
2407
2408 /* Returns the number of pbbs that are in loops contained in SCOP.  */
2409
2410 static int
2411 nb_pbbs_in_loops (scop_p scop)
2412 {
2413   int i;
2414   poly_bb_p pbb;
2415   int res = 0;
2416
2417   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2418     if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2419       res++;
2420
2421   return res;
2422 }
2423
2424 /* Return the number of data references in BB that write in
2425    memory.  */
2426
2427 static int
2428 nb_data_writes_in_bb (basic_block bb)
2429 {
2430   int res = 0;
2431   gimple_stmt_iterator gsi;
2432
2433   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2434     if (gimple_vdef (gsi_stmt (gsi)))
2435       res++;
2436
2437   return res;
2438 }
2439
2440 /* Splits STMT out of its current BB.  */
2441
2442 static basic_block
2443 split_reduction_stmt (gimple stmt)
2444 {
2445   gimple_stmt_iterator gsi;
2446   basic_block bb = gimple_bb (stmt);
2447   edge e;
2448
2449   /* Do not split basic blocks with no writes to memory: the reduction
2450      will be the only write to memory.  */
2451   if (nb_data_writes_in_bb (bb) == 0)
2452     return bb;
2453
2454   split_block (bb, stmt);
2455
2456   if (gsi_one_before_end_p (gsi_start_bb (bb)))
2457     return bb;
2458
2459   gsi = gsi_last_bb (bb);
2460   gsi_prev (&gsi);
2461   e = split_block (bb, gsi_stmt (gsi));
2462
2463   return e->dest;
2464 }
2465
2466 /* Return true when stmt is a reduction operation.  */
2467
2468 static inline bool
2469 is_reduction_operation_p (gimple stmt)
2470 {
2471   enum tree_code code;
2472
2473   gcc_assert (is_gimple_assign (stmt));
2474   code = gimple_assign_rhs_code (stmt);
2475
2476   return flag_associative_math
2477     && commutative_tree_code (code)
2478     && associative_tree_code (code);
2479 }
2480
2481 /* Returns true when PHI contains an argument ARG.  */
2482
2483 static bool
2484 phi_contains_arg (gimple phi, tree arg)
2485 {
2486   size_t i;
2487
2488   for (i = 0; i < gimple_phi_num_args (phi); i++)
2489     if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
2490       return true;
2491
2492   return false;
2493 }
2494
2495 /* Return a loop phi node that corresponds to a reduction containing LHS.  */
2496
2497 static gimple
2498 follow_ssa_with_commutative_ops (tree arg, tree lhs)
2499 {
2500   gimple stmt;
2501
2502   if (TREE_CODE (arg) != SSA_NAME)
2503     return NULL;
2504
2505   stmt = SSA_NAME_DEF_STMT (arg);
2506
2507   if (gimple_code (stmt) == GIMPLE_NOP
2508       || gimple_code (stmt) == GIMPLE_CALL)
2509     return NULL;
2510
2511   if (gimple_code (stmt) == GIMPLE_PHI)
2512     {
2513       if (phi_contains_arg (stmt, lhs))
2514         return stmt;
2515       return NULL;
2516     }
2517
2518   if (!is_gimple_assign (stmt))
2519     return NULL;
2520
2521   if (gimple_num_ops (stmt) == 2)
2522     return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2523
2524   if (is_reduction_operation_p (stmt))
2525     {
2526       gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2527
2528       return res ? res :
2529         follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
2530     }
2531
2532   return NULL;
2533 }
2534
2535 /* Detect commutative and associative scalar reductions starting at
2536    the STMT.  Return the phi node of the reduction cycle, or NULL.  */
2537
2538 static gimple
2539 detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
2540                                   VEC (gimple, heap) **in,
2541                                   VEC (gimple, heap) **out)
2542 {
2543   gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
2544
2545   if (!phi)
2546     return NULL;
2547
2548   VEC_safe_push (gimple, heap, *in, stmt);
2549   VEC_safe_push (gimple, heap, *out, stmt);
2550   return phi;
2551 }
2552
2553 /* Detect commutative and associative scalar reductions starting at
2554    the STMT.  Return the phi node of the reduction cycle, or NULL.  */
2555
2556 static gimple
2557 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
2558                                      VEC (gimple, heap) **out)
2559 {
2560   tree lhs = gimple_assign_lhs (stmt);
2561
2562   if (gimple_num_ops (stmt) == 2)
2563     return detect_commutative_reduction_arg (lhs, stmt,
2564                                              gimple_assign_rhs1 (stmt),
2565                                              in, out);
2566
2567   if (is_reduction_operation_p (stmt))
2568     {
2569       gimple res = detect_commutative_reduction_arg (lhs, stmt,
2570                                                      gimple_assign_rhs1 (stmt),
2571                                                      in, out);
2572       return res ? res
2573         : detect_commutative_reduction_arg (lhs, stmt,
2574                                             gimple_assign_rhs2 (stmt),
2575                                             in, out);
2576     }
2577
2578   return NULL;
2579 }
2580
2581 /* Return a loop phi node that corresponds to a reduction containing LHS.  */
2582
2583 static gimple
2584 follow_inital_value_to_phi (tree arg, tree lhs)
2585 {
2586   gimple stmt;
2587
2588   if (!arg || TREE_CODE (arg) != SSA_NAME)
2589     return NULL;
2590
2591   stmt = SSA_NAME_DEF_STMT (arg);
2592
2593   if (gimple_code (stmt) == GIMPLE_PHI
2594       && phi_contains_arg (stmt, lhs))
2595     return stmt;
2596
2597   return NULL;
2598 }
2599
2600
2601 /* Return the argument of the loop PHI that is the inital value coming
2602    from outside the loop.  */
2603
2604 static edge
2605 edge_initial_value_for_loop_phi (gimple phi)
2606 {
2607   size_t i;
2608
2609   for (i = 0; i < gimple_phi_num_args (phi); i++)
2610     {
2611       edge e = gimple_phi_arg_edge (phi, i);
2612
2613       if (loop_depth (e->src->loop_father)
2614           < loop_depth (e->dest->loop_father))
2615         return e;
2616     }
2617
2618   return NULL;
2619 }
2620
2621 /* Return the argument of the loop PHI that is the inital value coming
2622    from outside the loop.  */
2623
2624 static tree
2625 initial_value_for_loop_phi (gimple phi)
2626 {
2627   size_t i;
2628
2629   for (i = 0; i < gimple_phi_num_args (phi); i++)
2630     {
2631       edge e = gimple_phi_arg_edge (phi, i);
2632
2633       if (loop_depth (e->src->loop_father)
2634           < loop_depth (e->dest->loop_father))
2635         return gimple_phi_arg_def (phi, i);
2636     }
2637
2638   return NULL_TREE;
2639 }
2640
2641 /* Detect commutative and associative scalar reductions starting at
2642    the loop closed phi node CLOSE_PHI.  Return the phi node of the
2643    reduction cycle, or NULL.  */
2644
2645 static gimple
2646 detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in,
2647                               VEC (gimple, heap) **out)
2648 {
2649   if (scalar_close_phi_node_p (stmt))
2650     {
2651       tree arg = gimple_phi_arg_def (stmt, 0);
2652       gimple def, loop_phi;
2653
2654       if (TREE_CODE (arg) != SSA_NAME)
2655         return NULL;
2656
2657       def = SSA_NAME_DEF_STMT (arg);
2658       loop_phi = detect_commutative_reduction (def, in, out);
2659
2660       if (loop_phi)
2661         {
2662           tree lhs = gimple_phi_result (stmt);
2663           tree init = initial_value_for_loop_phi (loop_phi);
2664           gimple phi = follow_inital_value_to_phi (init, lhs);
2665
2666           VEC_safe_push (gimple, heap, *in, loop_phi);
2667           VEC_safe_push (gimple, heap, *out, stmt);
2668           return phi;
2669         }
2670       else
2671         return NULL;
2672     }
2673
2674   if (gimple_code (stmt) == GIMPLE_ASSIGN)
2675     return detect_commutative_reduction_assign (stmt, in, out);
2676
2677   return NULL;
2678 }
2679
2680 /* Translate the scalar reduction statement STMT to an array RED
2681    knowing that its recursive phi node is LOOP_PHI.  */
2682
2683 static void
2684 translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt,
2685                                               gimple loop_phi)
2686 {
2687   gimple_stmt_iterator insert_gsi = gsi_after_labels (gimple_bb (loop_phi));
2688   tree res = gimple_phi_result (loop_phi);
2689   gimple assign = gimple_build_assign (res, red);
2690
2691   gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2692
2693   insert_gsi = gsi_after_labels (gimple_bb (stmt));
2694   assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
2695   insert_gsi = gsi_for_stmt (stmt);
2696   gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT);
2697 }
2698
2699 /* Insert the assignment "result (CLOSE_PHI) = RED".  */
2700
2701 static void
2702 insert_copyout (tree red, gimple close_phi)
2703 {
2704   tree res = gimple_phi_result (close_phi);
2705   basic_block bb = gimple_bb (close_phi);
2706   gimple_stmt_iterator insert_gsi = gsi_after_labels (bb);
2707   gimple assign = gimple_build_assign (res, red);
2708
2709   gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2710 }
2711
2712 /* Insert the assignment "RED = initial_value (LOOP_PHI)".  */
2713
2714 static void
2715 insert_copyin (tree red, gimple loop_phi)
2716 {
2717   gimple_seq stmts;
2718   tree init = initial_value_for_loop_phi (loop_phi);
2719   tree expr = build2 (MODIFY_EXPR, TREE_TYPE (init), red, init);
2720
2721   force_gimple_operand (expr, &stmts, true, NULL);
2722   gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi), stmts);
2723 }
2724
2725 /* Removes the PHI node and resets all the debug stmts that are using
2726    the PHI_RESULT.  */
2727
2728 static void
2729 remove_phi (gimple phi)
2730 {
2731   imm_use_iterator imm_iter;
2732   tree def;
2733   use_operand_p use_p;
2734   gimple_stmt_iterator gsi;
2735   VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3);
2736   unsigned int i;
2737   gimple stmt;
2738
2739   def = PHI_RESULT (phi);
2740   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
2741     {
2742       stmt = USE_STMT (use_p);
2743
2744       if (is_gimple_debug (stmt))
2745         {
2746           gimple_debug_bind_reset_value (stmt);
2747           VEC_safe_push (gimple, heap, update, stmt);
2748         }
2749     }
2750
2751   for (i = 0; VEC_iterate (gimple, update, i, stmt); i++)
2752     update_stmt (stmt);
2753
2754   VEC_free (gimple, heap, update);
2755
2756   gsi = gsi_for_phi_node (phi);
2757   remove_phi_node (&gsi, false);
2758 }
2759
2760 /* Rewrite out of SSA the reduction described by the loop phi nodes
2761    IN, and the close phi nodes OUT.  IN and OUT are structured by loop
2762    levels like this:
2763
2764    IN: stmt, loop_n, ..., loop_0
2765    OUT: stmt, close_n, ..., close_0
2766
2767    the first element is the reduction statement, and the next elements
2768    are the loop and close phi nodes of each of the outer loops.  */
2769
2770 static void
2771 translate_scalar_reduction_to_array (VEC (gimple, heap) *in,
2772                                      VEC (gimple, heap) *out,
2773                                      sbitmap reductions)
2774 {
2775   unsigned int i;
2776   gimple loop_phi;
2777   tree red;
2778
2779   for (i = 0; VEC_iterate (gimple, in, i, loop_phi); i++)
2780     {
2781       gimple close_phi = VEC_index (gimple, out, i);
2782
2783       if (i == 0)
2784         {
2785           gimple stmt = loop_phi;
2786           basic_block bb = split_reduction_stmt (stmt);
2787
2788           SET_BIT (reductions, bb->index);
2789           gcc_assert (close_phi == loop_phi);
2790
2791           red = create_zero_dim_array
2792             (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction");
2793           translate_scalar_reduction_to_array_for_stmt
2794             (red, stmt, VEC_index (gimple, in, 1));
2795           continue;
2796         }
2797
2798       if (i == VEC_length (gimple, in) - 1)
2799         {
2800           insert_copyout (red, close_phi);
2801           insert_copyin (red, loop_phi);
2802         }
2803
2804       remove_phi (loop_phi);
2805       remove_phi (close_phi);
2806     }
2807 }
2808
2809 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI.  */
2810
2811 static void
2812 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi,
2813                                                      sbitmap reductions)
2814 {
2815   VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
2816   VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
2817
2818   detect_commutative_reduction (close_phi, &in, &out);
2819   if (VEC_length (gimple, in) > 0)
2820     translate_scalar_reduction_to_array (in, out, reductions);
2821
2822   VEC_free (gimple, heap, in);
2823   VEC_free (gimple, heap, out);
2824 }
2825
2826 /* Rewrites all the commutative reductions from LOOP out of SSA.  */
2827
2828 static void
2829 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop,
2830                                                 sbitmap reductions)
2831 {
2832   gimple_stmt_iterator gsi;
2833   edge exit = single_exit (loop);
2834
2835   if (!exit)
2836     return;
2837
2838   for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
2839     rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi),
2840                                                          reductions);
2841 }
2842
2843 /* Rewrites all the commutative reductions from SCOP out of SSA.  */
2844
2845 static void
2846 rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions)
2847 {
2848   loop_iterator li;
2849   loop_p loop;
2850
2851   FOR_EACH_LOOP (li, loop, 0)
2852     if (loop_in_sese_p (loop, region))
2853       rewrite_commutative_reductions_out_of_ssa_loop (loop, reductions);
2854
2855   gsi_commit_edge_inserts ();
2856   update_ssa (TODO_update_ssa);
2857 #ifdef ENABLE_CHECKING
2858   verify_ssa (false);
2859   verify_loop_closed_ssa ();
2860 #endif
2861 }
2862
2863 /* A LOOP is in normal form for Graphite when it contains only one
2864    scalar phi node that defines the main induction variable of the
2865    loop, only one increment of the IV, and only one exit condition.  */
2866
2867 static void
2868 graphite_loop_normal_form (loop_p loop)
2869 {
2870   struct tree_niter_desc niter;
2871   tree nit;
2872   gimple_seq stmts;
2873   edge exit = single_dom_exit (loop);
2874
2875   bool known_niter = number_of_iterations_exit (loop, exit, &niter, false);
2876
2877   /* At this point we should know the number of iterations,  */
2878   gcc_assert (known_niter);
2879
2880   nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
2881                               NULL_TREE);
2882   if (stmts)
2883     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2884
2885   loop->single_iv = canonicalize_loop_ivs (loop, &nit);
2886 }
2887
2888 /* Rewrite all the loops of SCOP in normal form: one induction
2889    variable per loop.  */
2890
2891 static void
2892 scop_canonicalize_loops (scop_p scop)
2893 {
2894   loop_iterator li;
2895   loop_p loop;
2896
2897   FOR_EACH_LOOP (li, loop, 0)
2898     if (loop_in_sese_p (loop, SCOP_REGION (scop)))
2899       graphite_loop_normal_form (loop);
2900 }
2901
2902 /* Can all ivs be represented by a signed integer?
2903    As CLooG might generate negative values in its expressions, signed loop ivs
2904    are required in the backend. */
2905 static bool
2906 scop_ivs_can_be_represented (scop_p scop)
2907 {
2908   loop_iterator li;
2909   loop_p loop;
2910
2911   FOR_EACH_LOOP (li, loop, 0)
2912     {
2913       tree type;
2914       int precision;
2915
2916       if (!loop_in_sese_p (loop, SCOP_REGION (scop)))
2917         continue;
2918
2919       if (!loop->single_iv)
2920         continue;
2921
2922       type = TREE_TYPE(loop->single_iv);
2923       precision = TYPE_PRECISION (type);
2924
2925       if (TYPE_UNSIGNED (type)
2926           && precision >= TYPE_PRECISION (long_long_integer_type_node))
2927         return false;
2928     }
2929
2930   return true;
2931 }
2932
2933
2934 /* Builds the polyhedral representation for a SESE region.  */
2935
2936 bool
2937 build_poly_scop (scop_p scop)
2938 {
2939   sese region = SCOP_REGION (scop);
2940   sbitmap reductions = sbitmap_alloc (last_basic_block * 2);
2941
2942   sbitmap_zero (reductions);
2943   rewrite_commutative_reductions_out_of_ssa (region, reductions);
2944   rewrite_reductions_out_of_ssa (scop);
2945   build_scop_bbs (scop, reductions);
2946   sbitmap_free (reductions);
2947
2948   /* FIXME: This restriction is needed to avoid a problem in CLooG.
2949      Once CLooG is fixed, remove this guard.  Anyways, it makes no
2950      sense to optimize a scop containing only PBBs that do not belong
2951      to any loops.  */
2952   if (nb_pbbs_in_loops (scop) == 0)
2953     return false;
2954
2955   scop_canonicalize_loops (scop);
2956
2957   if (!scop_ivs_can_be_represented (scop))
2958     return false;
2959
2960   build_sese_loop_nests (region);
2961   build_sese_conditions (region);
2962   find_scop_parameters (scop);
2963
2964   build_scop_iteration_domain (scop);
2965   build_scop_context (scop);
2966
2967   add_conditions_to_constraints (scop);
2968   scop_to_lst (scop);
2969   build_scop_scattering (scop);
2970   build_scop_drs (scop);
2971   POLY_SCOP_P (scop) = true;
2972
2973   return true;
2974 }
2975
2976 /* Always return false.  Exercise the scop_to_clast function.  */
2977
2978 void
2979 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED)
2980 {
2981 #ifdef ENABLE_CHECKING
2982   cloog_prog_clast pc = scop_to_clast (scop);
2983   cloog_clast_free (pc.stmt);
2984   cloog_program_free (pc.prog);
2985 #endif
2986 }
2987 #endif