OSDN Git Service

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