OSDN Git Service

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