OSDN Git Service

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