OSDN Git Service

canonicalize_loop_ivs should add the IV bump in loop->header.
[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       /* 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 /* Insert in the SCOP context constraints from the estimation of the
1042    number of iterations.  UB_EXPR is a linear expression describing
1043    the number of iterations in a loop.  This expression is bounded by
1044    the estimation NIT.  */
1045
1046 static void
1047 add_upper_bounds_from_estimated_nit (scop_p scop, double_int nit,
1048                                      ppl_dimension_type dim,
1049                                      ppl_Linear_Expression_t ub_expr)
1050 {
1051   Value val;
1052   ppl_Linear_Expression_t nb_iters_le;
1053   ppl_Polyhedron_t pol;
1054   ppl_Coefficient_t coef;
1055   ppl_Constraint_t ub;
1056
1057   ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1058   ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0);
1059   ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le,
1060                                                     ub_expr);
1061
1062   /* Construct the negated number of last iteration in VAL.  */
1063   value_init (val);
1064   mpz_set_double_int (val, nit, false);
1065   value_sub_int (val, val, 1);
1066   value_oppose (val, val);
1067
1068   /* NB_ITERS_LE holds the number of last iteration in
1069      parametrical form.  Subtract estimated number of last
1070      iteration and assert that result is not positive.  */
1071   ppl_new_Coefficient_from_mpz_t (&coef, val);
1072   ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le, coef);
1073   ppl_delete_Coefficient (coef);
1074   ppl_new_Constraint (&ub, nb_iters_le,
1075                       PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1076   ppl_Polyhedron_add_constraint (pol, ub);
1077
1078   /* Remove all but last GDIM dimensions from POL to obtain
1079      only the constraints on the parameters.  */
1080   {
1081     graphite_dim_t gdim = scop_nb_params (scop);
1082     ppl_dimension_type *dims = XNEWVEC (ppl_dimension_type, dim - gdim);
1083     graphite_dim_t i;
1084
1085     for (i = 0; i < dim - gdim; i++)
1086       dims[i] = i;
1087
1088     ppl_Polyhedron_remove_space_dimensions (pol, dims, dim - gdim);
1089     XDELETEVEC (dims);
1090   }
1091
1092   /* Add the constraints on the parameters to the SCoP context.  */
1093   {
1094     ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps;
1095
1096     ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1097       (&constraints_ps, pol);
1098     ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1099       (SCOP_CONTEXT (scop), constraints_ps);
1100     ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps);
1101   }
1102
1103   ppl_delete_Polyhedron (pol);
1104   ppl_delete_Linear_Expression (nb_iters_le);
1105   ppl_delete_Constraint (ub);
1106   value_clear (val);
1107 }
1108
1109 /* Builds the constraint polyhedra for LOOP in SCOP.  OUTER_PH gives
1110    the constraints for the surrounding loops.  */
1111
1112 static void
1113 build_loop_iteration_domains (scop_p scop, struct loop *loop,
1114                               ppl_Polyhedron_t outer_ph, int nb,
1115                               ppl_Pointset_Powerset_C_Polyhedron_t *domains)
1116 {
1117   int i;
1118   ppl_Polyhedron_t ph;
1119   tree nb_iters = number_of_latch_executions (loop);
1120   ppl_dimension_type dim = nb + 1 + scop_nb_params (scop);
1121   sese region = SCOP_REGION (scop);
1122
1123   {
1124     ppl_const_Constraint_System_t pcs;
1125     ppl_dimension_type *map
1126       = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
1127
1128     ppl_new_C_Polyhedron_from_space_dimension (&ph, dim, 0);
1129     ppl_Polyhedron_get_constraints (outer_ph, &pcs);
1130     ppl_Polyhedron_add_constraints (ph, pcs);
1131
1132     for (i = 0; i < (int) nb; i++)
1133       map[i] = i;
1134     for (i = (int) nb; i < (int) dim - 1; i++)
1135       map[i] = i + 1;
1136     map[dim - 1] = nb;
1137
1138     ppl_Polyhedron_map_space_dimensions (ph, map, dim);
1139     free (map);
1140   }
1141
1142   /* 0 <= loop_i */
1143   {
1144     ppl_Constraint_t lb;
1145     ppl_Linear_Expression_t lb_expr;
1146
1147     ppl_new_Linear_Expression_with_dimension (&lb_expr, dim);
1148     ppl_set_coef (lb_expr, nb, 1);
1149     ppl_new_Constraint (&lb, lb_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1150     ppl_delete_Linear_Expression (lb_expr);
1151     ppl_Polyhedron_add_constraint (ph, lb);
1152     ppl_delete_Constraint (lb);
1153   }
1154
1155   if (TREE_CODE (nb_iters) == INTEGER_CST)
1156     {
1157       ppl_Constraint_t ub;
1158       ppl_Linear_Expression_t ub_expr;
1159
1160       ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1161
1162       /* loop_i <= cst_nb_iters */
1163       ppl_set_coef (ub_expr, nb, -1);
1164       ppl_set_inhomogeneous_tree (ub_expr, nb_iters);
1165       ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1166       ppl_Polyhedron_add_constraint (ph, ub);
1167       ppl_delete_Linear_Expression (ub_expr);
1168       ppl_delete_Constraint (ub);
1169     }
1170   else if (!chrec_contains_undetermined (nb_iters))
1171     {
1172       Value one;
1173       ppl_Constraint_t ub;
1174       ppl_Linear_Expression_t ub_expr;
1175       double_int nit;
1176
1177       value_init (one);
1178       value_set_si (one, 1);
1179       ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1180       nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1181       scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one);
1182       value_clear (one);
1183
1184       if (estimated_loop_iterations (loop, true, &nit))
1185         add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr);
1186
1187       /* loop_i <= expr_nb_iters */
1188       ppl_set_coef (ub_expr, nb, -1);
1189       ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1190       ppl_Polyhedron_add_constraint (ph, ub);
1191       ppl_delete_Linear_Expression (ub_expr);
1192       ppl_delete_Constraint (ub);
1193     }
1194   else
1195     gcc_unreachable ();
1196
1197   if (loop->inner && loop_in_sese_p (loop->inner, region))
1198     build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains);
1199
1200   if (nb != 0
1201       && loop->next
1202       && loop_in_sese_p (loop->next, region))
1203     build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains);
1204
1205   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1206     (&domains[loop->num], ph);
1207
1208   ppl_delete_Polyhedron (ph);
1209 }
1210
1211 /* Returns a linear expression for tree T evaluated in PBB.  */
1212
1213 static ppl_Linear_Expression_t
1214 create_linear_expr_from_tree (poly_bb_p pbb, tree t)
1215 {
1216   Value one;
1217   ppl_Linear_Expression_t res;
1218   ppl_dimension_type dim;
1219   sese region = SCOP_REGION (PBB_SCOP (pbb));
1220   loop_p loop = pbb_loop (pbb);
1221
1222   dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
1223   ppl_new_Linear_Expression_with_dimension (&res, dim);
1224
1225   t = scalar_evolution_in_region (region, loop, t);
1226   gcc_assert (!automatically_generated_chrec_p (t));
1227
1228   value_init (one);
1229   value_set_si (one, 1);
1230   scan_tree_for_params (region, t, res, one);
1231   value_clear (one);
1232
1233   return res;
1234 }
1235
1236 /* Returns the ppl constraint type from the gimple tree code CODE.  */
1237
1238 static enum ppl_enum_Constraint_Type
1239 ppl_constraint_type_from_tree_code (enum tree_code code)
1240 {
1241   switch (code)
1242     {
1243     /* We do not support LT and GT to be able to work with C_Polyhedron.
1244        As we work on integer polyhedron "a < b" can be expressed by
1245        "a + 1 <= b".  */
1246     case LT_EXPR:
1247     case GT_EXPR:
1248       gcc_unreachable ();
1249
1250     case LE_EXPR:
1251       return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL;
1252
1253     case GE_EXPR:
1254       return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL;
1255
1256     case EQ_EXPR:
1257       return PPL_CONSTRAINT_TYPE_EQUAL;
1258
1259     default:
1260       gcc_unreachable ();
1261     }
1262 }
1263
1264 /* Add conditional statement STMT to PS.  It is evaluated in PBB and
1265    CODE is used as the comparison operator.  This allows us to invert the
1266    condition or to handle inequalities.  */
1267
1268 static void
1269 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt,
1270                          poly_bb_p pbb, enum tree_code code)
1271 {
1272   Value v;
1273   ppl_Coefficient_t c;
1274   ppl_Linear_Expression_t left, right;
1275   ppl_Constraint_t cstr;
1276   enum ppl_enum_Constraint_Type type;
1277
1278   left = create_linear_expr_from_tree (pbb, gimple_cond_lhs (stmt));
1279   right = create_linear_expr_from_tree (pbb, gimple_cond_rhs (stmt));
1280
1281   /* If we have < or > expressions convert them to <= or >= by adding 1 to
1282      the left or the right side of the expression. */
1283   if (code == LT_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 (left, c);
1290       ppl_delete_Coefficient (c);
1291       value_clear (v);
1292
1293       code = LE_EXPR;
1294     }
1295   else if (code == GT_EXPR)
1296     {
1297       value_init (v);
1298       value_set_si (v, 1);
1299       ppl_new_Coefficient (&c);
1300       ppl_assign_Coefficient_from_mpz_t (c, v);
1301       ppl_Linear_Expression_add_to_inhomogeneous (right, c);
1302       ppl_delete_Coefficient (c);
1303       value_clear (v);
1304
1305       code = GE_EXPR;
1306     }
1307
1308   type = ppl_constraint_type_from_tree_code (code);
1309
1310   ppl_subtract_Linear_Expression_from_Linear_Expression (left, right);
1311
1312   ppl_new_Constraint (&cstr, left, type);
1313   ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps, cstr);
1314
1315   ppl_delete_Constraint (cstr);
1316   ppl_delete_Linear_Expression (left);
1317   ppl_delete_Linear_Expression (right);
1318 }
1319
1320 /* Add conditional statement STMT to pbb.  CODE is used as the comparision
1321    operator.  This allows us to invert the condition or to handle
1322    inequalities.  */
1323
1324 static void
1325 add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
1326 {
1327   if (code == NE_EXPR)
1328     {
1329       ppl_Pointset_Powerset_C_Polyhedron_t left = PBB_DOMAIN (pbb);
1330       ppl_Pointset_Powerset_C_Polyhedron_t right;
1331       ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1332         (&right, left);
1333       add_condition_to_domain (left, stmt, pbb, LT_EXPR);
1334       add_condition_to_domain (right, stmt, pbb, GT_EXPR);
1335       ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left,
1336                                                                right);
1337       ppl_delete_Pointset_Powerset_C_Polyhedron (right);
1338     }
1339   else
1340     add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code);
1341 }
1342
1343 /* Add conditions to the domain of PBB.  */
1344
1345 static void
1346 add_conditions_to_domain (poly_bb_p pbb)
1347 {
1348   unsigned int i;
1349   gimple stmt;
1350   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1351   VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb);
1352
1353   if (VEC_empty (gimple, conditions))
1354     return;
1355
1356   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
1357     switch (gimple_code (stmt))
1358       {
1359       case GIMPLE_COND:
1360           {
1361             enum tree_code code = gimple_cond_code (stmt);
1362
1363             /* The conditions for ELSE-branches are inverted.  */
1364             if (VEC_index (gimple, gbb->condition_cases, i) == NULL)
1365               code = invert_tree_comparison (code, false);
1366
1367             add_condition_to_pbb (pbb, stmt, code);
1368             break;
1369           }
1370
1371       case GIMPLE_SWITCH:
1372         /* Switch statements are not supported right now - fall throught.  */
1373
1374       default:
1375         gcc_unreachable ();
1376         break;
1377       }
1378 }
1379
1380 /* Structure used to pass data to dom_walk.  */
1381
1382 struct bsc
1383 {
1384   VEC (gimple, heap) **conditions, **cases;
1385   sese region;
1386 };
1387
1388 /* Returns non NULL when BB has a single predecessor and the last
1389    statement of that predecessor is a COND_EXPR.  */
1390
1391 static gimple
1392 single_pred_cond (basic_block bb)
1393 {
1394   if (single_pred_p (bb))
1395     {
1396       edge e = single_pred_edge (bb);
1397       basic_block pred = e->src;
1398       gimple stmt = last_stmt (pred);
1399
1400       if (stmt && gimple_code (stmt) == GIMPLE_COND)
1401         return stmt;
1402     }
1403   return NULL;
1404 }
1405
1406 /* Call-back for dom_walk executed before visiting the dominated
1407    blocks.  */
1408
1409 static void
1410 build_sese_conditions_before (struct dom_walk_data *dw_data,
1411                               basic_block bb)
1412 {
1413   struct bsc *data = (struct bsc *) dw_data->global_data;
1414   VEC (gimple, heap) **conditions = data->conditions;
1415   VEC (gimple, heap) **cases = data->cases;
1416   gimple_bb_p gbb = gbb_from_bb (bb);
1417   gimple stmt = single_pred_cond (bb);
1418
1419   if (!bb_in_sese_p (bb, data->region))
1420     return;
1421
1422   if (stmt)
1423     {
1424       edge e = single_pred_edge (bb);
1425
1426       VEC_safe_push (gimple, heap, *conditions, stmt);
1427
1428       if (e->flags & EDGE_TRUE_VALUE)
1429         VEC_safe_push (gimple, heap, *cases, stmt);
1430       else
1431         VEC_safe_push (gimple, heap, *cases, NULL);
1432     }
1433
1434   if (gbb)
1435     {
1436       GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
1437       GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
1438     }
1439 }
1440
1441 /* Call-back for dom_walk executed after visiting the dominated
1442    blocks.  */
1443
1444 static void
1445 build_sese_conditions_after (struct dom_walk_data *dw_data,
1446                              basic_block bb)
1447 {
1448   struct bsc *data = (struct bsc *) dw_data->global_data;
1449   VEC (gimple, heap) **conditions = data->conditions;
1450   VEC (gimple, heap) **cases = data->cases;
1451
1452   if (!bb_in_sese_p (bb, data->region))
1453     return;
1454
1455   if (single_pred_cond (bb))
1456     {
1457       VEC_pop (gimple, *conditions);
1458       VEC_pop (gimple, *cases);
1459     }
1460 }
1461
1462 /* Record all conditions in REGION.  */
1463
1464 static void
1465 build_sese_conditions (sese region)
1466 {
1467   struct dom_walk_data walk_data;
1468   VEC (gimple, heap) *conditions = VEC_alloc (gimple, heap, 3);
1469   VEC (gimple, heap) *cases = VEC_alloc (gimple, heap, 3);
1470   struct bsc data;
1471
1472   data.conditions = &conditions;
1473   data.cases = &cases;
1474   data.region = region;
1475
1476   walk_data.dom_direction = CDI_DOMINATORS;
1477   walk_data.initialize_block_local_data = NULL;
1478   walk_data.before_dom_children = build_sese_conditions_before;
1479   walk_data.after_dom_children = build_sese_conditions_after;
1480   walk_data.global_data = &data;
1481   walk_data.block_local_data_size = 0;
1482
1483   init_walk_dominator_tree (&walk_data);
1484   walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region));
1485   fini_walk_dominator_tree (&walk_data);
1486
1487   VEC_free (gimple, heap, conditions);
1488   VEC_free (gimple, heap, cases);
1489 }
1490
1491 /* Traverses all the GBBs of the SCOP and add their constraints to the
1492    iteration domains.  */
1493
1494 static void
1495 add_conditions_to_constraints (scop_p scop)
1496 {
1497   int i;
1498   poly_bb_p pbb;
1499
1500   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1501     add_conditions_to_domain (pbb);
1502 }
1503
1504 /* Add constraints on the possible values of parameter P from the type
1505    of P.  */
1506
1507 static void
1508 add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
1509 {
1510   ppl_Constraint_t cstr;
1511   ppl_Linear_Expression_t le;
1512   tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p);
1513   tree type = TREE_TYPE (parameter);
1514   tree lb = NULL_TREE;
1515   tree ub = NULL_TREE;
1516
1517   if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
1518     lb = lower_bound_in_type (type, type);
1519   else
1520     lb = TYPE_MIN_VALUE (type);
1521
1522   if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
1523     ub = upper_bound_in_type (type, type);
1524   else
1525     ub = TYPE_MAX_VALUE (type);
1526
1527   if (lb)
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, lb);
1532       ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1533       ppl_Polyhedron_add_constraint (context, cstr);
1534       ppl_delete_Linear_Expression (le);
1535       ppl_delete_Constraint (cstr);
1536     }
1537
1538   if (ub)
1539     {
1540       ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1541       ppl_set_coef (le, p, -1);
1542       ppl_set_inhomogeneous_tree (le, ub);
1543       ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1544       ppl_Polyhedron_add_constraint (context, cstr);
1545       ppl_delete_Linear_Expression (le);
1546       ppl_delete_Constraint (cstr);
1547     }
1548 }
1549
1550 /* Build the context of the SCOP.  The context usually contains extra
1551    constraints that are added to the iteration domains that constrain
1552    some parameters.  */
1553
1554 static void
1555 build_scop_context (scop_p scop)
1556 {
1557   ppl_Polyhedron_t context;
1558   ppl_Pointset_Powerset_C_Polyhedron_t ps;
1559   graphite_dim_t p, n = scop_nb_params (scop);
1560
1561   ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0);
1562
1563   for (p = 0; p < n; p++)
1564     add_param_constraints (scop, context, p);
1565
1566   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1567     (&ps, context);
1568   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1569     (SCOP_CONTEXT (scop), ps);
1570
1571   ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
1572   ppl_delete_Polyhedron (context);
1573 }
1574
1575 /* Build the iteration domains: the loops belonging to the current
1576    SCOP, and that vary for the execution of the current basic block.
1577    Returns false if there is no loop in SCOP.  */
1578
1579 static void
1580 build_scop_iteration_domain (scop_p scop)
1581 {
1582   struct loop *loop;
1583   sese region = SCOP_REGION (scop);
1584   int i;
1585   ppl_Polyhedron_t ph;
1586   poly_bb_p pbb;
1587   int nb_loops = number_of_loops ();
1588   ppl_Pointset_Powerset_C_Polyhedron_t *domains
1589     = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t, nb_loops);
1590
1591   for (i = 0; i < nb_loops; i++)
1592     domains[i] = NULL;
1593
1594   ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0);
1595
1596   for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1597     if (!loop_in_sese_p (loop_outer (loop), region))
1598       build_loop_iteration_domains (scop, loop, ph, 0, domains);
1599
1600   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1601     if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num])
1602       ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1603         (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
1604          domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]);
1605     else
1606       ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1607         (&PBB_DOMAIN (pbb), ph);
1608
1609   for (i = 0; i < nb_loops; i++)
1610     if (domains[i])
1611       ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]);
1612
1613   ppl_delete_Polyhedron (ph);
1614   free (domains);
1615 }
1616
1617 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1618    data reference DR.  ACCESSP_NB_DIMS is the dimension of the
1619    ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1620    domain.  */
1621
1622 static void
1623 pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr,
1624                    ppl_dimension_type accessp_nb_dims,
1625                    ppl_dimension_type dom_nb_dims)
1626 {
1627   ppl_Linear_Expression_t alias;
1628   ppl_Constraint_t cstr;
1629   int alias_set_num = 0;
1630   base_alias_pair *bap = (base_alias_pair *)(dr->aux);
1631
1632   if (bap && bap->alias_set)
1633     alias_set_num = *(bap->alias_set);
1634
1635   ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims);
1636
1637   ppl_set_coef (alias, dom_nb_dims, 1);
1638   ppl_set_inhomogeneous (alias, -alias_set_num);
1639   ppl_new_Constraint (&cstr, alias, PPL_CONSTRAINT_TYPE_EQUAL);
1640   ppl_Polyhedron_add_constraint (accesses, cstr);
1641
1642   ppl_delete_Linear_Expression (alias);
1643   ppl_delete_Constraint (cstr);
1644 }
1645
1646 /* Add to ACCESSES polyhedron equalities defining the access functions
1647    to the memory.  ACCESSP_NB_DIMS is the dimension of the ACCESSES
1648    polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1649    PBB is the poly_bb_p that contains the data reference DR.  */
1650
1651 static void
1652 pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr,
1653                          ppl_dimension_type accessp_nb_dims,
1654                          ppl_dimension_type dom_nb_dims,
1655                          poly_bb_p pbb)
1656 {
1657   int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1658   Value v;
1659   scop_p scop = PBB_SCOP (pbb);
1660   sese region = SCOP_REGION (scop);
1661
1662   value_init (v);
1663
1664   for (i = 0; i < nb_subscripts; i++)
1665     {
1666       ppl_Linear_Expression_t fn, access;
1667       ppl_Constraint_t cstr;
1668       ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1669       tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i);
1670
1671       ppl_new_Linear_Expression_with_dimension (&fn, dom_nb_dims);
1672       ppl_new_Linear_Expression_with_dimension (&access, accessp_nb_dims);
1673
1674       value_set_si (v, 1);
1675       scan_tree_for_params (region, afn, fn, v);
1676       ppl_assign_Linear_Expression_from_Linear_Expression (access, fn);
1677
1678       ppl_set_coef (access, subscript, -1);
1679       ppl_new_Constraint (&cstr, access, PPL_CONSTRAINT_TYPE_EQUAL);
1680       ppl_Polyhedron_add_constraint (accesses, cstr);
1681
1682       ppl_delete_Linear_Expression (fn);
1683       ppl_delete_Linear_Expression (access);
1684       ppl_delete_Constraint (cstr);
1685     }
1686
1687   value_clear (v);
1688 }
1689
1690 /* Add constrains representing the size of the accessed data to the
1691    ACCESSES polyhedron.  ACCESSP_NB_DIMS is the dimension of the
1692    ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1693    domain.  */
1694
1695 static void
1696 pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr,
1697                          ppl_dimension_type accessp_nb_dims,
1698                          ppl_dimension_type dom_nb_dims)
1699 {
1700   tree ref = DR_REF (dr);
1701   int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1702
1703   for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
1704     {
1705       ppl_Linear_Expression_t expr;
1706       ppl_Constraint_t cstr;
1707       ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1708       tree low, high;
1709
1710       if (TREE_CODE (ref) != ARRAY_REF)
1711         break;
1712
1713       low = array_ref_low_bound (ref);
1714
1715       /* subscript - low >= 0 */
1716       if (host_integerp (low, 0))
1717         {
1718           ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1719           ppl_set_coef (expr, subscript, 1);
1720
1721           ppl_set_inhomogeneous (expr, -int_cst_value (low));
1722
1723           ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1724           ppl_Polyhedron_add_constraint (accesses, cstr);
1725           ppl_delete_Linear_Expression (expr);
1726           ppl_delete_Constraint (cstr);
1727         }
1728
1729       high = array_ref_up_bound (ref);
1730
1731       /* high - subscript >= 0 */
1732       if (high && host_integerp (high, 0)
1733           /* 1-element arrays at end of structures may extend over
1734              their declared size.  */
1735           && !(array_at_struct_end_p (ref)
1736                && operand_equal_p (low, high, 0)))
1737         {
1738           ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1739           ppl_set_coef (expr, subscript, -1);
1740
1741           ppl_set_inhomogeneous (expr, int_cst_value (high));
1742
1743           ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1744           ppl_Polyhedron_add_constraint (accesses, cstr);
1745           ppl_delete_Linear_Expression (expr);
1746           ppl_delete_Constraint (cstr);
1747         }
1748     }
1749 }
1750
1751 /* Build data accesses for DR in PBB.  */
1752
1753 static void
1754 build_poly_dr (data_reference_p dr, poly_bb_p pbb)
1755 {
1756   ppl_Polyhedron_t accesses;
1757   ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps;
1758   ppl_dimension_type dom_nb_dims;
1759   ppl_dimension_type accessp_nb_dims;
1760   int dr_base_object_set;
1761
1762   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb),
1763                                                       &dom_nb_dims);
1764   accessp_nb_dims = dom_nb_dims + 1 + DR_NUM_DIMENSIONS (dr);
1765
1766   ppl_new_C_Polyhedron_from_space_dimension (&accesses, accessp_nb_dims, 0);
1767
1768   pdr_add_alias_set (accesses, dr, accessp_nb_dims, dom_nb_dims);
1769   pdr_add_memory_accesses (accesses, dr, accessp_nb_dims, dom_nb_dims, pbb);
1770   pdr_add_data_dimensions (accesses, dr, accessp_nb_dims, dom_nb_dims);
1771
1772   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps,
1773                                                             accesses);
1774   ppl_delete_Polyhedron (accesses);
1775
1776   if (dr->aux)
1777     dr_base_object_set = ((base_alias_pair *)(dr->aux))->base_obj_set;
1778
1779   new_poly_dr (pbb, dr_base_object_set, accesses_ps, DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
1780                dr, DR_NUM_DIMENSIONS (dr));
1781 }
1782
1783 /* Write to FILE the alias graph of data references in DIMACS format.  */
1784
1785 static inline bool
1786 write_alias_graph_to_ascii_dimacs (FILE *file, char *comment,
1787                                    VEC (data_reference_p, heap) *drs)
1788 {
1789   int num_vertex = VEC_length (data_reference_p, drs);
1790   int edge_num = 0;
1791   data_reference_p dr1, dr2;
1792   int i, j;
1793
1794   if (num_vertex == 0)
1795     return true;
1796
1797   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1798     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1799       if (dr_may_alias_p (dr1, dr2))
1800         edge_num++;
1801
1802   fprintf (file, "$\n");
1803
1804   if (comment)
1805     fprintf (file, "c %s\n", comment);
1806
1807   fprintf (file, "p edge %d %d\n", num_vertex, edge_num);
1808
1809   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1810     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1811       if (dr_may_alias_p (dr1, dr2))
1812         fprintf (file, "e %d %d\n", i + 1, j + 1);
1813
1814   return true;
1815 }
1816
1817 /* Write to FILE the alias graph of data references in DOT format.  */
1818
1819 static inline bool
1820 write_alias_graph_to_ascii_dot (FILE *file, char *comment,
1821                                 VEC (data_reference_p, heap) *drs)
1822 {
1823   int num_vertex = VEC_length (data_reference_p, drs);
1824   data_reference_p dr1, dr2;
1825   int i, j;
1826
1827   if (num_vertex == 0)
1828     return true;
1829
1830   fprintf (file, "$\n");
1831
1832   if (comment)
1833     fprintf (file, "c %s\n", comment);
1834
1835   /* First print all the vertices.  */
1836   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1837     fprintf (file, "n%d;\n", i);
1838
1839   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1840     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1841       if (dr_may_alias_p (dr1, dr2))
1842         fprintf (file, "n%d n%d\n", i, j);
1843
1844   return true;
1845 }
1846
1847 /* Write to FILE the alias graph of data references in ECC format.  */
1848
1849 static inline bool
1850 write_alias_graph_to_ascii_ecc (FILE *file, char *comment,
1851                                 VEC (data_reference_p, heap) *drs)
1852 {
1853   int num_vertex = VEC_length (data_reference_p, drs);
1854   data_reference_p dr1, dr2;
1855   int i, j;
1856
1857   if (num_vertex == 0)
1858     return true;
1859
1860   fprintf (file, "$\n");
1861
1862   if (comment)
1863     fprintf (file, "c %s\n", comment);
1864
1865   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1866     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1867       if (dr_may_alias_p (dr1, dr2))
1868         fprintf (file, "%d %d\n", i, j);
1869
1870   return true;
1871 }
1872
1873 /* Check if DR1 and DR2 are in the same object set.  */
1874
1875 static bool
1876 dr_same_base_object_p (const struct data_reference *dr1,
1877                        const struct data_reference *dr2)
1878 {
1879   return operand_equal_p (DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), 0);
1880 }
1881
1882 /* Uses DFS component number as representative of alias-sets. Also tests for
1883    optimality by verifying if every connected component is a clique. Returns
1884    true (1) if the above test is true, and false (0) otherwise.  */
1885
1886 static int
1887 build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs)
1888 {
1889   int num_vertices = VEC_length (data_reference_p, drs);
1890   struct graph *g = new_graph (num_vertices);
1891   data_reference_p dr1, dr2;
1892   int i, j;
1893   int num_connected_components;
1894   int v_indx1, v_indx2, num_vertices_in_component;
1895   int *all_vertices;
1896   int *vertices;
1897   struct graph_edge *e;
1898   int this_component_is_clique;
1899   int all_components_are_cliques = 1;
1900
1901   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1902     for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1903       if (dr_may_alias_p (dr1, dr2))
1904         {
1905           add_edge (g, i, j);
1906           add_edge (g, j, i);
1907         }
1908
1909   all_vertices = XNEWVEC (int, num_vertices);
1910   vertices = XNEWVEC (int, num_vertices);
1911   for (i = 0; i < num_vertices; i++)
1912     all_vertices[i] = i;
1913
1914   num_connected_components = graphds_dfs (g, all_vertices, num_vertices,
1915                                           NULL, true, NULL);
1916   for (i = 0; i < g->n_vertices; i++)
1917     {
1918       data_reference_p dr = VEC_index (data_reference_p, drs, i);
1919       base_alias_pair *bap;
1920
1921       if (dr->aux)
1922         bap = (base_alias_pair *)(dr->aux);
1923
1924       bap->alias_set = XNEW (int);
1925       *(bap->alias_set) = g->vertices[i].component + 1;
1926     }
1927
1928   /* Verify if the DFS numbering results in optimal solution.  */
1929   for (i = 0; i < num_connected_components; i++)
1930     {
1931       num_vertices_in_component = 0;
1932       /* Get all vertices whose DFS component number is the same as i.  */
1933       for (j = 0; j < num_vertices; j++)
1934         if (g->vertices[j].component == i)
1935           vertices[num_vertices_in_component++] = j;
1936
1937       /* Now test if the vertices in 'vertices' form a clique, by testing
1938          for edges among each pair.  */
1939       this_component_is_clique = 1;
1940       for (v_indx1 = 0; v_indx1 < num_vertices_in_component; v_indx1++)
1941         {
1942           for (v_indx2 = v_indx1+1; v_indx2 < num_vertices_in_component; v_indx2++)
1943             {
1944               /* Check if the two vertices are connected by iterating
1945                  through all the edges which have one of these are source.  */
1946               e = g->vertices[vertices[v_indx2]].pred;
1947               while (e)
1948                 {
1949                   if (e->src == vertices[v_indx1])
1950                     break;
1951                   e = e->pred_next;
1952                 }
1953               if (!e)
1954                 {
1955                   this_component_is_clique = 0;
1956                   break;
1957                 }
1958             }
1959           if (!this_component_is_clique)
1960             all_components_are_cliques = 0;
1961         }
1962     }
1963
1964   free (all_vertices);
1965   free (vertices);
1966   free_graph (g);
1967   return all_components_are_cliques;
1968 }
1969
1970 /* Group each data reference in DRS with it's base object set num.  */
1971
1972 static void
1973 build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs)
1974 {
1975   int num_vertex = VEC_length (data_reference_p, drs);
1976   struct graph *g = new_graph (num_vertex);
1977   data_reference_p dr1, dr2;
1978   int i, j;
1979   int *queue;
1980
1981   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1982     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1983       if (dr_same_base_object_p (dr1, dr2))
1984         {
1985           add_edge (g, i, j);
1986           add_edge (g, j, i);
1987         }
1988
1989   queue = XNEWVEC (int, num_vertex);
1990   for (i = 0; i < num_vertex; i++)
1991     queue[i] = i;
1992
1993   graphds_dfs (g, queue, num_vertex, NULL, true, NULL);
1994
1995   for (i = 0; i < g->n_vertices; i++)
1996     {
1997       data_reference_p dr = VEC_index (data_reference_p, drs, i);
1998       base_alias_pair *bap;
1999
2000       if (dr->aux)
2001         bap = (base_alias_pair *)(dr->aux);
2002
2003       bap->base_obj_set = g->vertices[i].component + 1;
2004     }
2005
2006   free (queue);
2007   free_graph (g);
2008 }
2009
2010 /* Build the data references for PBB.  */
2011
2012 static void
2013 build_pbb_drs (poly_bb_p pbb)
2014 {
2015   int j;
2016   data_reference_p dr;
2017   VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb));
2018
2019   for (j = 0; VEC_iterate (data_reference_p, gbb_drs, j, dr); j++)
2020     build_poly_dr (dr, pbb);
2021 }
2022
2023 /* Dump to file the alias graphs for the data references in DRS.  */
2024
2025 static void
2026 dump_alias_graphs (VEC (data_reference_p, heap) *drs)
2027 {
2028   char comment[100];
2029   FILE *file_dimacs, *file_ecc, *file_dot;
2030
2031   file_dimacs = fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2032   if (file_dimacs)
2033     {
2034       snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2035                 current_function_name ());
2036       write_alias_graph_to_ascii_dimacs (file_dimacs, comment, drs);
2037       fclose (file_dimacs);
2038     }
2039
2040   file_ecc = fopen ("/tmp/dr_alias_graph_ecc", "ab");
2041   if (file_ecc)
2042     {
2043       snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2044                 current_function_name ());
2045       write_alias_graph_to_ascii_ecc (file_ecc, comment, drs);
2046       fclose (file_ecc);
2047     }
2048
2049   file_dot = fopen ("/tmp/dr_alias_graph_dot", "ab");
2050   if (file_dot)
2051     {
2052       snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2053                 current_function_name ());
2054       write_alias_graph_to_ascii_dot (file_dot, comment, drs);
2055       fclose (file_dot);
2056     }
2057 }
2058
2059 /* Build data references in SCOP.  */
2060
2061 static void
2062 build_scop_drs (scop_p scop)
2063 {
2064   int i, j;
2065   poly_bb_p pbb;
2066   data_reference_p dr;
2067   VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
2068
2069   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2070     for (j = 0; VEC_iterate (data_reference_p,
2071                              GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++)
2072       VEC_safe_push (data_reference_p, heap, drs, dr);
2073
2074   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr); i++)
2075     dr->aux = XNEW (base_alias_pair);
2076
2077   if (!build_alias_set_optimal_p (drs))
2078     {
2079       /* TODO: Add support when building alias set is not optimal.  */
2080       ;
2081     }
2082
2083   build_base_obj_set_for_drs (drs);
2084
2085   /* When debugging, enable the following code.  This cannot be used
2086      in production compilers.  */
2087   if (0)
2088     dump_alias_graphs (drs);
2089
2090   VEC_free (data_reference_p, heap, drs);
2091
2092   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2093     build_pbb_drs (pbb);
2094 }
2095
2096 /* Return a gsi at the position of the phi node STMT.  */
2097
2098 static gimple_stmt_iterator
2099 gsi_for_phi_node (gimple stmt)
2100 {
2101   gimple_stmt_iterator psi;
2102   basic_block bb = gimple_bb (stmt);
2103
2104   for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2105     if (stmt == gsi_stmt (psi))
2106       return psi;
2107
2108   gcc_unreachable ();
2109   return psi;
2110 }
2111
2112 /* Insert the assignment "RES := VAR" just after the definition of VAR.  */
2113
2114 static void
2115 insert_out_of_ssa_copy (tree res, tree var)
2116 {
2117   gimple stmt;
2118   gimple_seq stmts;
2119   gimple_stmt_iterator si;
2120   gimple_stmt_iterator gsi;
2121
2122   var = force_gimple_operand (var, &stmts, true, NULL_TREE);
2123   stmt = gimple_build_assign (res, var);
2124   if (!stmts)
2125     stmts = gimple_seq_alloc ();
2126   si = gsi_last (stmts);
2127   gsi_insert_after (&si, stmt, GSI_NEW_STMT);
2128
2129   stmt = SSA_NAME_DEF_STMT (var);
2130   if (gimple_code (stmt) == GIMPLE_PHI)
2131     {
2132       gsi = gsi_after_labels (gimple_bb (stmt));
2133       gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2134     }
2135   else
2136     {
2137       gsi = gsi_for_stmt (stmt);
2138       gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
2139     }
2140 }
2141
2142 /* Insert on edge E the assignment "RES := EXPR".  */
2143
2144 static void
2145 insert_out_of_ssa_copy_on_edge (edge e, tree res, tree expr)
2146 {
2147   gimple_stmt_iterator gsi;
2148   gimple_seq stmts;
2149   tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2150   gimple stmt = gimple_build_assign (res, var);
2151
2152   if (!stmts)
2153     stmts = gimple_seq_alloc ();
2154
2155   gsi = gsi_last (stmts);
2156   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2157   gsi_insert_seq_on_edge (e, stmts);
2158   gsi_commit_edge_inserts ();
2159 }
2160
2161 /* Creates a zero dimension array of the same type as VAR.  */
2162
2163 static tree
2164 create_zero_dim_array (tree var, const char *base_name)
2165 {
2166   tree index_type = build_index_type (integer_zero_node);
2167   tree elt_type = TREE_TYPE (var);
2168   tree array_type = build_array_type (elt_type, index_type);
2169   tree base = create_tmp_var (array_type, base_name);
2170
2171   add_referenced_var (base);
2172
2173   return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
2174                  NULL_TREE);
2175 }
2176
2177 /* Returns true when PHI is a loop close phi node.  */
2178
2179 static bool
2180 scalar_close_phi_node_p (gimple phi)
2181 {
2182   if (gimple_code (phi) != GIMPLE_PHI
2183       || !is_gimple_reg (gimple_phi_result (phi)))
2184     return false;
2185
2186   return (gimple_phi_num_args (phi) == 1);
2187 }
2188
2189 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2190    dimension array for it.  */
2191
2192 static void
2193 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi)
2194 {
2195   gimple phi = gsi_stmt (*psi);
2196   tree res = gimple_phi_result (phi);
2197   tree var = SSA_NAME_VAR (res);
2198   tree zero_dim_array = create_zero_dim_array (var, "Close_Phi");
2199   gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
2200   gimple stmt = gimple_build_assign (res, zero_dim_array);
2201   tree arg = gimple_phi_arg_def (phi, 0);
2202
2203   if (TREE_CODE (arg) == SSA_NAME
2204       && !SSA_NAME_IS_DEFAULT_DEF (arg))
2205     insert_out_of_ssa_copy (zero_dim_array, arg);
2206   else
2207     insert_out_of_ssa_copy_on_edge (single_pred_edge (gimple_bb (phi)),
2208                                     zero_dim_array, arg);
2209
2210   remove_phi_node (psi, false);
2211   gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2212   SSA_NAME_DEF_STMT (res) = stmt;
2213 }
2214
2215 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2216    dimension array for it.  */
2217
2218 static void
2219 rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi)
2220 {
2221   size_t i;
2222   gimple phi = gsi_stmt (*psi);
2223   basic_block bb = gimple_bb (phi);
2224   tree res = gimple_phi_result (phi);
2225   tree var = SSA_NAME_VAR (res);
2226   tree zero_dim_array = create_zero_dim_array (var, "General_Reduction");
2227   gimple_stmt_iterator gsi;
2228   gimple stmt;
2229   gimple_seq stmts;
2230
2231   for (i = 0; i < gimple_phi_num_args (phi); i++)
2232     {
2233       tree arg = gimple_phi_arg_def (phi, i);
2234
2235       /* Try to avoid the insertion on edges as much as possible: this
2236          would avoid the insertion of code on loop latch edges, making
2237          the pattern matching of the vectorizer happy, or it would
2238          avoid the insertion of useless basic blocks.  Note that it is
2239          incorrect to insert out of SSA copies close by their
2240          definition when they are more than two loop levels apart:
2241          for example, starting from a double nested loop
2242
2243          | a = ...
2244          | loop_1
2245          |  loop_2
2246          |    b = phi (a, c)
2247          |    c = ...
2248          |  end_2
2249          | end_1
2250
2251          the following transform is incorrect
2252
2253          | a = ...
2254          | Red[0] = a
2255          | loop_1
2256          |  loop_2
2257          |    b = Red[0]
2258          |    c = ...
2259          |    Red[0] = c
2260          |  end_2
2261          | end_1
2262
2263          whereas inserting the copy on the incoming edge is correct
2264
2265          | a = ...
2266          | loop_1
2267          |  Red[0] = a
2268          |  loop_2
2269          |    b = Red[0]
2270          |    c = ...
2271          |    Red[0] = c
2272          |  end_2
2273          | end_1
2274       */
2275       if (TREE_CODE (arg) == SSA_NAME
2276           && is_gimple_reg (arg)
2277           && gimple_bb (SSA_NAME_DEF_STMT (arg))
2278           && (flow_bb_inside_loop_p (bb->loop_father,
2279                                      gimple_bb (SSA_NAME_DEF_STMT (arg)))
2280               || flow_bb_inside_loop_p (loop_outer (bb->loop_father),
2281                                         gimple_bb (SSA_NAME_DEF_STMT (arg)))))
2282         insert_out_of_ssa_copy (zero_dim_array, arg);
2283       else
2284         insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi, i),
2285                                         zero_dim_array, arg);
2286     }
2287
2288   var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE);
2289
2290   if (!stmts)
2291     stmts = gimple_seq_alloc ();
2292
2293   stmt = gimple_build_assign (res, var);
2294   remove_phi_node (psi, false);
2295   SSA_NAME_DEF_STMT (res) = stmt;
2296
2297   gsi = gsi_last (stmts);
2298   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2299
2300   gsi = gsi_after_labels (bb);
2301   gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2302 }
2303
2304 /* Return true when DEF can be analyzed in REGION by the scalar
2305    evolution analyzer.  */
2306
2307 static bool
2308 scev_analyzable_p (tree def, sese region)
2309 {
2310   gimple stmt = SSA_NAME_DEF_STMT (def);
2311   loop_p loop = loop_containing_stmt (stmt);
2312   tree scev = scalar_evolution_in_region (region, loop, def);
2313
2314   return !chrec_contains_undetermined (scev);
2315 }
2316
2317 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2318    read from ZERO_DIM_ARRAY.  */
2319
2320 static void
2321 rewrite_cross_bb_scalar_dependence (tree zero_dim_array, tree def, gimple use_stmt)
2322 {
2323   tree var = SSA_NAME_VAR (def);
2324   gimple name_stmt = gimple_build_assign (var, zero_dim_array);
2325   tree name = make_ssa_name (var, name_stmt);
2326   ssa_op_iter iter;
2327   use_operand_p use_p;
2328   gimple_stmt_iterator gsi;
2329
2330   gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2331
2332   gimple_assign_set_lhs (name_stmt, name);
2333
2334   gsi = gsi_for_stmt (use_stmt);
2335   gsi_insert_before (&gsi, name_stmt, GSI_NEW_STMT);
2336
2337   FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2338     if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2339       replace_exp (use_p, name);
2340
2341   update_stmt (use_stmt);
2342 }
2343
2344 /* Rewrite the scalar dependences crossing the boundary of the BB
2345    containing STMT with an array.  */
2346
2347 static void
2348 rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi)
2349 {
2350   gimple stmt = gsi_stmt (*gsi);
2351   imm_use_iterator imm_iter;
2352   tree def;
2353   basic_block def_bb;
2354   tree zero_dim_array = NULL_TREE;
2355   gimple use_stmt;
2356
2357   if (gimple_code (stmt) != GIMPLE_ASSIGN)
2358     return;
2359
2360   def = gimple_assign_lhs (stmt);
2361   if (!is_gimple_reg (def)
2362       || scev_analyzable_p (def, region))
2363     return;
2364
2365   def_bb = gimple_bb (stmt);
2366
2367   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2368     if (def_bb != gimple_bb (use_stmt)
2369         && gimple_code (use_stmt) != GIMPLE_PHI
2370         && !is_gimple_debug (use_stmt))
2371       {
2372         if (!zero_dim_array)
2373           {
2374             zero_dim_array = create_zero_dim_array
2375               (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence");
2376             insert_out_of_ssa_copy (zero_dim_array, def);
2377             gsi_next (gsi);
2378           }
2379
2380         rewrite_cross_bb_scalar_dependence (zero_dim_array, def, use_stmt);
2381       }
2382 }
2383
2384 /* Rewrite out of SSA all the reduction phi nodes of SCOP.  */
2385
2386 static void
2387 rewrite_reductions_out_of_ssa (scop_p scop)
2388 {
2389   basic_block bb;
2390   gimple_stmt_iterator psi;
2391   sese region = SCOP_REGION (scop);
2392
2393   FOR_EACH_BB (bb)
2394     if (bb_in_sese_p (bb, region))
2395       for (psi = gsi_start_phis (bb); !gsi_end_p (psi);)
2396         {
2397           if (scalar_close_phi_node_p (gsi_stmt (psi)))
2398             rewrite_close_phi_out_of_ssa (&psi);
2399           else if (reduction_phi_p (region, &psi))
2400             rewrite_phi_out_of_ssa (&psi);
2401         }
2402
2403   update_ssa (TODO_update_ssa);
2404 #ifdef ENABLE_CHECKING
2405   verify_ssa (false);
2406   verify_loop_closed_ssa ();
2407 #endif
2408
2409   FOR_EACH_BB (bb)
2410     if (bb_in_sese_p (bb, region))
2411       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
2412         rewrite_cross_bb_scalar_deps (region, &psi);
2413
2414   update_ssa (TODO_update_ssa);
2415 #ifdef ENABLE_CHECKING
2416   verify_ssa (false);
2417   verify_loop_closed_ssa ();
2418 #endif
2419 }
2420
2421 /* Returns the number of pbbs that are in loops contained in SCOP.  */
2422
2423 static int
2424 nb_pbbs_in_loops (scop_p scop)
2425 {
2426   int i;
2427   poly_bb_p pbb;
2428   int res = 0;
2429
2430   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2431     if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2432       res++;
2433
2434   return res;
2435 }
2436
2437 /* Return the number of data references in BB that write in
2438    memory.  */
2439
2440 static int
2441 nb_data_writes_in_bb (basic_block bb)
2442 {
2443   int res = 0;
2444   gimple_stmt_iterator gsi;
2445
2446   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2447     if (gimple_vdef (gsi_stmt (gsi)))
2448       res++;
2449
2450   return res;
2451 }
2452
2453 /* Splits STMT out of its current BB.  */
2454
2455 static basic_block
2456 split_reduction_stmt (gimple stmt)
2457 {
2458   gimple_stmt_iterator gsi;
2459   basic_block bb = gimple_bb (stmt);
2460   edge e;
2461
2462   /* Do not split basic blocks with no writes to memory: the reduction
2463      will be the only write to memory.  */
2464   if (nb_data_writes_in_bb (bb) == 0)
2465     return bb;
2466
2467   split_block (bb, stmt);
2468
2469   if (gsi_one_before_end_p (gsi_start_nondebug_bb (bb)))
2470     return bb;
2471
2472   gsi = gsi_last_bb (bb);
2473   gsi_prev (&gsi);
2474   e = split_block (bb, gsi_stmt (gsi));
2475
2476   return e->dest;
2477 }
2478
2479 /* Return true when stmt is a reduction operation.  */
2480
2481 static inline bool
2482 is_reduction_operation_p (gimple stmt)
2483 {
2484   enum tree_code code;
2485
2486   gcc_assert (is_gimple_assign (stmt));
2487   code = gimple_assign_rhs_code (stmt);
2488
2489   return flag_associative_math
2490     && commutative_tree_code (code)
2491     && associative_tree_code (code);
2492 }
2493
2494 /* Returns true when PHI contains an argument ARG.  */
2495
2496 static bool
2497 phi_contains_arg (gimple phi, tree arg)
2498 {
2499   size_t i;
2500
2501   for (i = 0; i < gimple_phi_num_args (phi); i++)
2502     if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
2503       return true;
2504
2505   return false;
2506 }
2507
2508 /* Return a loop phi node that corresponds to a reduction containing LHS.  */
2509
2510 static gimple
2511 follow_ssa_with_commutative_ops (tree arg, tree lhs)
2512 {
2513   gimple stmt;
2514
2515   if (TREE_CODE (arg) != SSA_NAME)
2516     return NULL;
2517
2518   stmt = SSA_NAME_DEF_STMT (arg);
2519
2520   if (gimple_code (stmt) == GIMPLE_NOP
2521       || gimple_code (stmt) == GIMPLE_CALL)
2522     return NULL;
2523
2524   if (gimple_code (stmt) == GIMPLE_PHI)
2525     {
2526       if (phi_contains_arg (stmt, lhs))
2527         return stmt;
2528       return NULL;
2529     }
2530
2531   if (!is_gimple_assign (stmt))
2532     return NULL;
2533
2534   if (gimple_num_ops (stmt) == 2)
2535     return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2536
2537   if (is_reduction_operation_p (stmt))
2538     {
2539       gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2540
2541       return res ? res :
2542         follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
2543     }
2544
2545   return NULL;
2546 }
2547
2548 /* Detect commutative and associative scalar reductions starting at
2549    the STMT.  Return the phi node of the reduction cycle, or NULL.  */
2550
2551 static gimple
2552 detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
2553                                   VEC (gimple, heap) **in,
2554                                   VEC (gimple, heap) **out)
2555 {
2556   gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
2557
2558   if (!phi)
2559     return NULL;
2560
2561   VEC_safe_push (gimple, heap, *in, stmt);
2562   VEC_safe_push (gimple, heap, *out, stmt);
2563   return phi;
2564 }
2565
2566 /* Detect commutative and associative scalar reductions starting at
2567    the STMT.  Return the phi node of the reduction cycle, or NULL.  */
2568
2569 static gimple
2570 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
2571                                      VEC (gimple, heap) **out)
2572 {
2573   tree lhs = gimple_assign_lhs (stmt);
2574
2575   if (gimple_num_ops (stmt) == 2)
2576     return detect_commutative_reduction_arg (lhs, stmt,
2577                                              gimple_assign_rhs1 (stmt),
2578                                              in, out);
2579
2580   if (is_reduction_operation_p (stmt))
2581     {
2582       gimple res = detect_commutative_reduction_arg (lhs, stmt,
2583                                                      gimple_assign_rhs1 (stmt),
2584                                                      in, out);
2585       return res ? res
2586         : detect_commutative_reduction_arg (lhs, stmt,
2587                                             gimple_assign_rhs2 (stmt),
2588                                             in, out);
2589     }
2590
2591   return NULL;
2592 }
2593
2594 /* Return a loop phi node that corresponds to a reduction containing LHS.  */
2595
2596 static gimple
2597 follow_inital_value_to_phi (tree arg, tree lhs)
2598 {
2599   gimple stmt;
2600
2601   if (!arg || TREE_CODE (arg) != SSA_NAME)
2602     return NULL;
2603
2604   stmt = SSA_NAME_DEF_STMT (arg);
2605
2606   if (gimple_code (stmt) == GIMPLE_PHI
2607       && phi_contains_arg (stmt, lhs))
2608     return stmt;
2609
2610   return NULL;
2611 }
2612
2613
2614 /* Return the argument of the loop PHI that is the inital value coming
2615    from outside the loop.  */
2616
2617 static edge
2618 edge_initial_value_for_loop_phi (gimple phi)
2619 {
2620   size_t i;
2621
2622   for (i = 0; i < gimple_phi_num_args (phi); i++)
2623     {
2624       edge e = gimple_phi_arg_edge (phi, i);
2625
2626       if (loop_depth (e->src->loop_father)
2627           < loop_depth (e->dest->loop_father))
2628         return e;
2629     }
2630
2631   return NULL;
2632 }
2633
2634 /* Return the argument of the loop PHI that is the inital value coming
2635    from outside the loop.  */
2636
2637 static tree
2638 initial_value_for_loop_phi (gimple phi)
2639 {
2640   size_t i;
2641
2642   for (i = 0; i < gimple_phi_num_args (phi); i++)
2643     {
2644       edge e = gimple_phi_arg_edge (phi, i);
2645
2646       if (loop_depth (e->src->loop_father)
2647           < loop_depth (e->dest->loop_father))
2648         return gimple_phi_arg_def (phi, i);
2649     }
2650
2651   return NULL_TREE;
2652 }
2653
2654 /* Detect commutative and associative scalar reductions starting at
2655    the loop closed phi node CLOSE_PHI.  Return the phi node of the
2656    reduction cycle, or NULL.  */
2657
2658 static gimple
2659 detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in,
2660                               VEC (gimple, heap) **out)
2661 {
2662   if (scalar_close_phi_node_p (stmt))
2663     {
2664       tree arg = gimple_phi_arg_def (stmt, 0);
2665       gimple def, loop_phi;
2666
2667       if (TREE_CODE (arg) != SSA_NAME)
2668         return NULL;
2669
2670       def = SSA_NAME_DEF_STMT (arg);
2671       loop_phi = detect_commutative_reduction (def, in, out);
2672
2673       if (loop_phi)
2674         {
2675           tree lhs = gimple_phi_result (stmt);
2676           tree init = initial_value_for_loop_phi (loop_phi);
2677           gimple phi = follow_inital_value_to_phi (init, lhs);
2678
2679           VEC_safe_push (gimple, heap, *in, loop_phi);
2680           VEC_safe_push (gimple, heap, *out, stmt);
2681           return phi;
2682         }
2683       else
2684         return NULL;
2685     }
2686
2687   if (gimple_code (stmt) == GIMPLE_ASSIGN)
2688     return detect_commutative_reduction_assign (stmt, in, out);
2689
2690   return NULL;
2691 }
2692
2693 /* Translate the scalar reduction statement STMT to an array RED
2694    knowing that its recursive phi node is LOOP_PHI.  */
2695
2696 static void
2697 translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt,
2698                                               gimple loop_phi)
2699 {
2700   gimple_stmt_iterator insert_gsi = gsi_after_labels (gimple_bb (loop_phi));
2701   tree res = gimple_phi_result (loop_phi);
2702   gimple assign = gimple_build_assign (res, red);
2703
2704   gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2705
2706   insert_gsi = gsi_after_labels (gimple_bb (stmt));
2707   assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
2708   insert_gsi = gsi_for_stmt (stmt);
2709   gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT);
2710 }
2711
2712 /* Insert the assignment "result (CLOSE_PHI) = RED".  */
2713
2714 static void
2715 insert_copyout (tree red, gimple close_phi)
2716 {
2717   tree res = gimple_phi_result (close_phi);
2718   basic_block bb = gimple_bb (close_phi);
2719   gimple_stmt_iterator insert_gsi = gsi_after_labels (bb);
2720   gimple assign = gimple_build_assign (res, red);
2721
2722   gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2723 }
2724
2725 /* Insert the assignment "RED = initial_value (LOOP_PHI)".  */
2726
2727 static void
2728 insert_copyin (tree red, gimple loop_phi)
2729 {
2730   gimple_seq stmts;
2731   tree init = initial_value_for_loop_phi (loop_phi);
2732   tree expr = build2 (MODIFY_EXPR, TREE_TYPE (init), red, init);
2733
2734   force_gimple_operand (expr, &stmts, true, NULL);
2735   gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi), stmts);
2736 }
2737
2738 /* Removes the PHI node and resets all the debug stmts that are using
2739    the PHI_RESULT.  */
2740
2741 static void
2742 remove_phi (gimple phi)
2743 {
2744   imm_use_iterator imm_iter;
2745   tree def;
2746   use_operand_p use_p;
2747   gimple_stmt_iterator gsi;
2748   VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3);
2749   unsigned int i;
2750   gimple stmt;
2751
2752   def = PHI_RESULT (phi);
2753   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
2754     {
2755       stmt = USE_STMT (use_p);
2756
2757       if (is_gimple_debug (stmt))
2758         {
2759           gimple_debug_bind_reset_value (stmt);
2760           VEC_safe_push (gimple, heap, update, stmt);
2761         }
2762     }
2763
2764   for (i = 0; VEC_iterate (gimple, update, i, stmt); i++)
2765     update_stmt (stmt);
2766
2767   VEC_free (gimple, heap, update);
2768
2769   gsi = gsi_for_phi_node (phi);
2770   remove_phi_node (&gsi, false);
2771 }
2772
2773 /* Rewrite out of SSA the reduction described by the loop phi nodes
2774    IN, and the close phi nodes OUT.  IN and OUT are structured by loop
2775    levels like this:
2776
2777    IN: stmt, loop_n, ..., loop_0
2778    OUT: stmt, close_n, ..., close_0
2779
2780    the first element is the reduction statement, and the next elements
2781    are the loop and close phi nodes of each of the outer loops.  */
2782
2783 static void
2784 translate_scalar_reduction_to_array (VEC (gimple, heap) *in,
2785                                      VEC (gimple, heap) *out,
2786                                      sbitmap reductions)
2787 {
2788   unsigned int i;
2789   gimple loop_phi;
2790   tree red;
2791
2792   for (i = 0; VEC_iterate (gimple, in, i, loop_phi); i++)
2793     {
2794       gimple close_phi = VEC_index (gimple, out, i);
2795
2796       if (i == 0)
2797         {
2798           gimple stmt = loop_phi;
2799           basic_block bb = split_reduction_stmt (stmt);
2800
2801           SET_BIT (reductions, bb->index);
2802           gcc_assert (close_phi == loop_phi);
2803
2804           red = create_zero_dim_array
2805             (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction");
2806           translate_scalar_reduction_to_array_for_stmt
2807             (red, stmt, VEC_index (gimple, in, 1));
2808           continue;
2809         }
2810
2811       if (i == VEC_length (gimple, in) - 1)
2812         {
2813           insert_copyout (red, close_phi);
2814           insert_copyin (red, loop_phi);
2815         }
2816
2817       remove_phi (loop_phi);
2818       remove_phi (close_phi);
2819     }
2820 }
2821
2822 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI.  */
2823
2824 static void
2825 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi,
2826                                                      sbitmap reductions)
2827 {
2828   VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
2829   VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
2830
2831   detect_commutative_reduction (close_phi, &in, &out);
2832   if (VEC_length (gimple, in) > 0)
2833     translate_scalar_reduction_to_array (in, out, reductions);
2834
2835   VEC_free (gimple, heap, in);
2836   VEC_free (gimple, heap, out);
2837 }
2838
2839 /* Rewrites all the commutative reductions from LOOP out of SSA.  */
2840
2841 static void
2842 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop,
2843                                                 sbitmap reductions)
2844 {
2845   gimple_stmt_iterator gsi;
2846   edge exit = single_exit (loop);
2847
2848   if (!exit)
2849     return;
2850
2851   for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
2852     rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi),
2853                                                          reductions);
2854 }
2855
2856 /* Rewrites all the commutative reductions from SCOP out of SSA.  */
2857
2858 static void
2859 rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions)
2860 {
2861   loop_iterator li;
2862   loop_p loop;
2863
2864   FOR_EACH_LOOP (li, loop, 0)
2865     if (loop_in_sese_p (loop, region))
2866       rewrite_commutative_reductions_out_of_ssa_loop (loop, reductions);
2867
2868   gsi_commit_edge_inserts ();
2869   update_ssa (TODO_update_ssa);
2870 #ifdef ENABLE_CHECKING
2871   verify_ssa (false);
2872   verify_loop_closed_ssa ();
2873 #endif
2874 }
2875
2876 /* A LOOP is in normal form for Graphite when it contains only one
2877    scalar phi node that defines the main induction variable of the
2878    loop, only one increment of the IV, and only one exit condition.  */
2879
2880 static void
2881 graphite_loop_normal_form (loop_p loop)
2882 {
2883   struct tree_niter_desc niter;
2884   tree nit;
2885   gimple_seq stmts;
2886   edge exit = single_dom_exit (loop);
2887
2888   bool known_niter = number_of_iterations_exit (loop, exit, &niter, false);
2889
2890   /* At this point we should know the number of iterations.  */
2891   gcc_assert (known_niter);
2892
2893   nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
2894                               NULL_TREE);
2895   if (stmts)
2896     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2897
2898   loop->single_iv = canonicalize_loop_ivs (loop, &nit, false);
2899 }
2900
2901 /* Rewrite all the loops of SCOP in normal form: one induction
2902    variable per loop.  */
2903
2904 static void
2905 scop_canonicalize_loops (scop_p scop)
2906 {
2907   loop_iterator li;
2908   loop_p loop;
2909
2910   FOR_EACH_LOOP (li, loop, 0)
2911     if (loop_in_sese_p (loop, SCOP_REGION (scop)))
2912       graphite_loop_normal_form (loop);
2913 }
2914
2915 /* Java does not initialize long_long_integer_type_node.  */
2916 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype)
2917
2918 /* Can all ivs be represented by a signed integer?
2919    As CLooG might generate negative values in its expressions, signed loop ivs
2920    are required in the backend. */
2921 static bool
2922 scop_ivs_can_be_represented (scop_p scop)
2923 {
2924   loop_iterator li;
2925   loop_p loop;
2926
2927   FOR_EACH_LOOP (li, loop, 0)
2928     {
2929       tree type;
2930       int precision;
2931
2932       if (!loop_in_sese_p (loop, SCOP_REGION (scop)))
2933         continue;
2934
2935       if (!loop->single_iv)
2936         continue;
2937
2938       type = TREE_TYPE(loop->single_iv);
2939       precision = TYPE_PRECISION (type);
2940
2941       if (TYPE_UNSIGNED (type)
2942           && precision >= TYPE_PRECISION (my_long_long))
2943         return false;
2944     }
2945
2946   return true;
2947 }
2948
2949 #undef my_long_long
2950
2951 /* Builds the polyhedral representation for a SESE region.  */
2952
2953 void
2954 build_poly_scop (scop_p scop)
2955 {
2956   sese region = SCOP_REGION (scop);
2957   sbitmap reductions = sbitmap_alloc (last_basic_block * 2);
2958   graphite_dim_t max_dim;
2959
2960   sbitmap_zero (reductions);
2961   rewrite_commutative_reductions_out_of_ssa (region, reductions);
2962   rewrite_reductions_out_of_ssa (scop);
2963   build_scop_bbs (scop, reductions);
2964   sbitmap_free (reductions);
2965
2966   /* FIXME: This restriction is needed to avoid a problem in CLooG.
2967      Once CLooG is fixed, remove this guard.  Anyways, it makes no
2968      sense to optimize a scop containing only PBBs that do not belong
2969      to any loops.  */
2970   if (nb_pbbs_in_loops (scop) == 0)
2971     return;
2972
2973   scop_canonicalize_loops (scop);
2974   if (!scop_ivs_can_be_represented (scop))
2975     return;
2976
2977   build_sese_loop_nests (region);
2978   build_sese_conditions (region);
2979   find_scop_parameters (scop);
2980
2981   max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
2982   if (scop_nb_params (scop) > max_dim)
2983     return;
2984
2985   build_scop_iteration_domain (scop);
2986   build_scop_context (scop);
2987
2988   add_conditions_to_constraints (scop);
2989   scop_to_lst (scop);
2990   build_scop_scattering (scop);
2991   build_scop_drs (scop);
2992
2993   /* This SCoP has been translated to the polyhedral
2994      representation.  */
2995   POLY_SCOP_P (scop) = true;
2996 }
2997
2998 /* Always return false.  Exercise the scop_to_clast function.  */
2999
3000 void
3001 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED)
3002 {
3003 #ifdef ENABLE_CHECKING
3004   cloog_prog_clast pc = scop_to_clast (scop);
3005   cloog_clast_free (pc.stmt);
3006   cloog_program_free (pc.prog);
3007 #endif
3008 }
3009 #endif