xref: /netbsd-src/external/gpl3/gcc.old/dist/gcc/graphite-scop-detection.c (revision 8feb0f0b7eaff0608f8350bbfa3098827b4bb91b)
1 /* Detection of Static Control Parts (SCoP) for Graphite.
2    Copyright (C) 2009-2020 Free Software Foundation, Inc.
3    Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4    Tobias Grosser <grosser@fim.uni-passau.de>.
5 
6 This file is part of GCC.
7 
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12 
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 GNU General Public License for more details.
17 
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21 
22 #define USES_ISL
23 
24 #include "config.h"
25 
26 #ifdef HAVE_isl
27 
28 #include "system.h"
29 #include "coretypes.h"
30 #include "backend.h"
31 #include "cfghooks.h"
32 #include "domwalk.h"
33 #include "tree.h"
34 #include "gimple.h"
35 #include "ssa.h"
36 #include "fold-const.h"
37 #include "gimple-iterator.h"
38 #include "tree-cfg.h"
39 #include "tree-ssa-loop-manip.h"
40 #include "tree-ssa-loop-niter.h"
41 #include "tree-ssa-loop.h"
42 #include "tree-into-ssa.h"
43 #include "tree-ssa.h"
44 #include "cfgloop.h"
45 #include "tree-data-ref.h"
46 #include "tree-scalar-evolution.h"
47 #include "tree-pass.h"
48 #include "tree-ssa-propagate.h"
49 #include "gimple-pretty-print.h"
50 #include "cfganal.h"
51 #include "graphite.h"
52 
53 class debug_printer
54 {
55 private:
56   FILE *dump_file;
57 
58 public:
59   void
set_dump_file(FILE * f)60   set_dump_file (FILE *f)
61   {
62     gcc_assert (f);
63     dump_file = f;
64   }
65 
66   friend debug_printer &
67   operator<< (debug_printer &output, int i)
68   {
69     fprintf (output.dump_file, "%d", i);
70     return output;
71   }
72   friend debug_printer &
73   operator<< (debug_printer &output, const char *s)
74   {
75     fprintf (output.dump_file, "%s", s);
76     return output;
77   }
78 } dp;
79 
80 #define DEBUG_PRINT(args) do \
81     {								\
82       if (dump_file && (dump_flags & TDF_DETAILS)) { args; }	\
83     } while (0)
84 
85 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
86    different colors.  If there are not enough colors, paint the
87    remaining SCoPs in gray.
88 
89    Special nodes:
90    - "*" after the node number denotes the entry of a SCoP,
91    - "#" after the node number denotes the exit of a SCoP,
92    - "()" around the node number denotes the entry or the
93      exit nodes of the SCOP.  These are not part of SCoP.  */
94 
95 DEBUG_FUNCTION void
dot_all_sese(FILE * file,vec<sese_l> & scops)96 dot_all_sese (FILE *file, vec<sese_l>& scops)
97 {
98   /* Disable debugging while printing graph.  */
99   dump_flags_t tmp_dump_flags = dump_flags;
100   dump_flags = TDF_NONE;
101 
102   fprintf (file, "digraph all {\n");
103 
104   basic_block bb;
105   FOR_ALL_BB_FN (bb, cfun)
106     {
107       int part_of_scop = false;
108 
109       /* Use HTML for every bb label.  So we are able to print bbs
110 	 which are part of two different SCoPs, with two different
111 	 background colors.  */
112       fprintf (file, "%d [label=<\n  <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
113 	       bb->index);
114       fprintf (file, "CELLSPACING=\"0\">\n");
115 
116       /* Select color for SCoP.  */
117       sese_l *region;
118       int i;
119       FOR_EACH_VEC_ELT (scops, i, region)
120 	{
121 	  bool sese_in_region = bb_in_sese_p (bb, *region);
122 	  if (sese_in_region || (region->exit->dest == bb)
123 	      || (region->entry->dest == bb))
124 	    {
125 	      const char *color;
126 	      switch (i % 17)
127 		{
128 		case 0: /* red */
129 		  color = "#e41a1c";
130 		  break;
131 		case 1: /* blue */
132 		  color = "#377eb8";
133 		  break;
134 		case 2: /* green */
135 		  color = "#4daf4a";
136 		  break;
137 		case 3: /* purple */
138 		  color = "#984ea3";
139 		  break;
140 		case 4: /* orange */
141 		  color = "#ff7f00";
142 		  break;
143 		case 5: /* yellow */
144 		  color = "#ffff33";
145 		  break;
146 		case 6: /* brown */
147 		  color = "#a65628";
148 		  break;
149 		case 7: /* rose */
150 		  color = "#f781bf";
151 		  break;
152 		case 8:
153 		  color = "#8dd3c7";
154 		  break;
155 		case 9:
156 		  color = "#ffffb3";
157 		  break;
158 		case 10:
159 		  color = "#bebada";
160 		  break;
161 		case 11:
162 		  color = "#fb8072";
163 		  break;
164 		case 12:
165 		  color = "#80b1d3";
166 		  break;
167 		case 13:
168 		  color = "#fdb462";
169 		  break;
170 		case 14:
171 		  color = "#b3de69";
172 		  break;
173 		case 15:
174 		  color = "#fccde5";
175 		  break;
176 		case 16:
177 		  color = "#bc80bd";
178 		  break;
179 		default: /* gray */
180 		  color = "#999999";
181 		}
182 
183 	      fprintf (file, "    <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
184 		       color);
185 
186 	      if (!sese_in_region)
187 		fprintf (file, " (");
188 
189 	      if (bb == region->entry->dest && bb == region->exit->dest)
190 		fprintf (file, " %d*# ", bb->index);
191 	      else if (bb == region->entry->dest)
192 		fprintf (file, " %d* ", bb->index);
193 	      else if (bb == region->exit->dest)
194 		fprintf (file, " %d# ", bb->index);
195 	      else
196 		fprintf (file, " %d ", bb->index);
197 
198 	      fprintf (file, "{lp_%d}", bb->loop_father->num);
199 
200 	      if (!sese_in_region)
201 		fprintf (file, ")");
202 
203 	      fprintf (file, "</TD></TR>\n");
204 	      part_of_scop = true;
205 	    }
206 	}
207 
208 	if (!part_of_scop)
209 	  {
210 	    fprintf (file, "    <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
211 	    fprintf (file, " %d {lp_%d} </TD></TR>\n", bb->index,
212 		     bb->loop_father->num);
213 	  }
214 	fprintf (file, "  </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
215     }
216 
217     FOR_ALL_BB_FN (bb, cfun)
218       {
219 	edge e;
220 	edge_iterator ei;
221 	FOR_EACH_EDGE (e, ei, bb->succs)
222 	  fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
223       }
224 
225   fputs ("}\n\n", file);
226 
227   /* Enable debugging again.  */
228   dump_flags = tmp_dump_flags;
229 }
230 
231 /* Display SCoP on stderr.  */
232 
233 DEBUG_FUNCTION void
dot_sese(sese_l & scop)234 dot_sese (sese_l& scop)
235 {
236   vec<sese_l> scops;
237   scops.create (1);
238 
239   if (scop)
240     scops.safe_push (scop);
241 
242   dot_all_sese (stderr, scops);
243 
244   scops.release ();
245 }
246 
247 DEBUG_FUNCTION void
dot_cfg()248 dot_cfg ()
249 {
250   vec<sese_l> scops;
251   scops.create (1);
252   dot_all_sese (stderr, scops);
253   scops.release ();
254 }
255 
256 /* Returns a COND_EXPR statement when BB has a single predecessor, the
257    edge between BB and its predecessor is not a loop exit edge, and
258    the last statement of the single predecessor is a COND_EXPR.  */
259 
260 static gcond *
single_pred_cond_non_loop_exit(basic_block bb)261 single_pred_cond_non_loop_exit (basic_block bb)
262 {
263   if (single_pred_p (bb))
264     {
265       edge e = single_pred_edge (bb);
266       basic_block pred = e->src;
267       gimple *stmt;
268 
269       if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
270 	return NULL;
271 
272       stmt = last_stmt (pred);
273 
274       if (stmt && gimple_code (stmt) == GIMPLE_COND)
275 	return as_a<gcond *> (stmt);
276     }
277 
278   return NULL;
279 }
280 
281 namespace
282 {
283 
284 /* Build the maximal scop containing LOOPs and add it to SCOPS.  */
285 
286 class scop_detection
287 {
288 public:
scop_detection()289   scop_detection () : scops (vNULL) {}
290 
~scop_detection()291   ~scop_detection ()
292   {
293     scops.release ();
294   }
295 
296   /* A marker for invalid sese_l.  */
297   static sese_l invalid_sese;
298 
299   /* Return the SCOPS in this SCOP_DETECTION.  */
300 
301   vec<sese_l>
get_scops()302   get_scops ()
303   {
304     return scops;
305   }
306 
307   /* Return an sese_l around the LOOP.  */
308 
309   sese_l get_sese (loop_p loop);
310 
311   /* Merge scops at same loop depth and returns the new sese.
312      Returns a new SESE when merge was successful, INVALID_SESE otherwise.  */
313 
314   sese_l merge_sese (sese_l first, sese_l second) const;
315 
316   /* Build scop outer->inner if possible.  */
317 
318   void build_scop_depth (loop_p loop);
319 
320   /* Return true when BEGIN is the preheader edge of a loop with a single exit
321      END.  */
322 
323   static bool region_has_one_loop (sese_l s);
324 
325   /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END.  */
326 
327   void add_scop (sese_l s);
328 
329   /* Returns true if S1 subsumes/surrounds S2.  */
330   static bool subsumes (sese_l s1, sese_l s2);
331 
332   /* Remove a SCoP which is subsumed by S1.  */
333   void remove_subscops (sese_l s1);
334 
335   /* Returns true if S1 intersects with S2.  Since we already know that S1 does
336      not subsume S2 or vice-versa, we only check for entry bbs.  */
337 
338   static bool intersects (sese_l s1, sese_l s2);
339 
340   /* Remove one of the scops when it intersects with any other.  */
341 
342   void remove_intersecting_scops (sese_l s1);
343 
344   /* Return true when a statement in SCOP cannot be represented by Graphite.  */
345 
346   bool harmful_loop_in_region (sese_l scop) const;
347 
348   /* Return true only when STMT is simple enough for being handled by Graphite.
349      This depends on SCOP, as the parameters are initialized relatively to
350      this basic block, the linear functions are initialized based on the
351      outermost loop containing STMT inside the SCOP.  BB is the place where we
352      try to evaluate the STMT.  */
353 
354   bool stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
355 			       basic_block bb) const;
356 
357   /* Something like "n * m" is not allowed.  */
358 
359   static bool graphite_can_represent_init (tree e);
360 
361   /* Return true when SCEV can be represented in the polyhedral model.
362 
363      An expression can be represented, if it can be expressed as an
364      affine expression.  For loops (i, j) and parameters (m, n) all
365      affine expressions are of the form:
366 
367      x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
368 
369      1 i + 20 j + (-2) m + 25
370 
371      Something like "i * n" or "n * m" is not allowed.  */
372 
373   static bool graphite_can_represent_scev (sese_l scop, tree scev);
374 
375   /* Return true when EXPR can be represented in the polyhedral model.
376 
377      This means an expression can be represented, if it is linear with respect
378      to the loops and the strides are non parametric.  LOOP is the place where
379      the expr will be evaluated.  SCOP defines the region we analyse.  */
380 
381   static bool graphite_can_represent_expr (sese_l scop, loop_p loop,
382 					   tree expr);
383 
384   /* Return true if the data references of STMT can be represented by Graphite.
385      We try to analyze the data references in a loop contained in the SCOP.  */
386 
387   static bool stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt);
388 
389   /* Remove the close phi node at GSI and replace its rhs with the rhs
390      of PHI.  */
391 
392   static void remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi);
393 
394   /* Returns true when Graphite can represent LOOP in SCOP.
395      FIXME: For the moment, graphite cannot be used on loops that iterate using
396      induction variables that wrap.  */
397 
398   static bool can_represent_loop (loop_p loop, sese_l scop);
399 
400   /* Returns the number of pbbs that are in loops contained in SCOP.  */
401 
402   static int nb_pbbs_in_loops (scop_p scop);
403 
404 private:
405   vec<sese_l> scops;
406 };
407 
408 sese_l scop_detection::invalid_sese (NULL, NULL);
409 
410 /* Return an sese_l around the LOOP.  */
411 
412 sese_l
get_sese(loop_p loop)413 scop_detection::get_sese (loop_p loop)
414 {
415   if (!loop)
416     return invalid_sese;
417 
418   edge scop_begin = loop_preheader_edge (loop);
419   edge scop_end = single_exit (loop);
420   if (!scop_end || (scop_end->flags & (EDGE_COMPLEX|EDGE_FAKE)))
421     return invalid_sese;
422 
423   return sese_l (scop_begin, scop_end);
424 }
425 
426 /* Merge scops at same loop depth and returns the new sese.
427    Returns a new SESE when merge was successful, INVALID_SESE otherwise.  */
428 
429 sese_l
merge_sese(sese_l first,sese_l second)430 scop_detection::merge_sese (sese_l first, sese_l second) const
431 {
432   /* In the trivial case first/second may be NULL.  */
433   if (!first)
434     return second;
435   if (!second)
436     return first;
437 
438   DEBUG_PRINT (dp << "[scop-detection] try merging sese s1: ";
439 	       print_sese (dump_file, first);
440 	       dp << "[scop-detection] try merging sese s2: ";
441 	       print_sese (dump_file, second));
442 
443   auto_bitmap worklist, in_sese_region;
444   bitmap_set_bit (worklist, get_entry_bb (first)->index);
445   bitmap_set_bit (worklist, get_exit_bb (first)->index);
446   bitmap_set_bit (worklist, get_entry_bb (second)->index);
447   bitmap_set_bit (worklist, get_exit_bb (second)->index);
448   edge entry = NULL, exit = NULL;
449 
450   /* We can optimize the case of adding a loop entry dest or exit
451      src to the worklist (for single-exit loops) by skipping
452      directly to the exit dest / entry src.  in_sese_region
453      doesn't have to cover all blocks in the region but merely
454      its border it acts more like a visited bitmap.  */
455   do
456     {
457       int index = bitmap_first_set_bit (worklist);
458       bitmap_clear_bit (worklist, index);
459       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index);
460       edge_iterator ei;
461       edge e;
462 
463       /* With fake exit edges we can end up with no possible exit.  */
464       if (index == EXIT_BLOCK)
465 	{
466 	  DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
467 	  return invalid_sese;
468 	}
469 
470       bitmap_set_bit (in_sese_region, bb->index);
471 
472       basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
473       FOR_EACH_EDGE (e, ei, bb->preds)
474 	if (e->src == dom
475 	    && (! entry
476 		|| dominated_by_p (CDI_DOMINATORS, entry->dest, bb)))
477 	  {
478 	    if (entry
479 		&& ! bitmap_bit_p (in_sese_region, entry->src->index))
480 	      bitmap_set_bit (worklist, entry->src->index);
481 	    entry = e;
482 	  }
483 	else if (! bitmap_bit_p (in_sese_region, e->src->index))
484 	  bitmap_set_bit (worklist, e->src->index);
485 
486       basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
487       FOR_EACH_EDGE (e, ei, bb->succs)
488 	if (e->dest == pdom
489 	    && (! exit
490 		|| dominated_by_p (CDI_POST_DOMINATORS, exit->src, bb)))
491 	  {
492 	    if (exit
493 		&& ! bitmap_bit_p (in_sese_region, exit->dest->index))
494 	      bitmap_set_bit (worklist, exit->dest->index);
495 	    exit = e;
496 	  }
497 	else if (! bitmap_bit_p (in_sese_region, e->dest->index))
498 	  bitmap_set_bit (worklist, e->dest->index);
499     }
500   while (! bitmap_empty_p (worklist));
501 
502   sese_l combined (entry, exit);
503 
504   DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined));
505 
506   return combined;
507 }
508 
509 /* Build scop outer->inner if possible.  */
510 
511 void
build_scop_depth(loop_p loop)512 scop_detection::build_scop_depth (loop_p loop)
513 {
514   sese_l s = invalid_sese;
515   loop = loop->inner;
516   while (loop)
517     {
518       sese_l next = get_sese (loop);
519       if (! next
520 	  || harmful_loop_in_region (next))
521 	{
522 	  if (s)
523 	    add_scop (s);
524 	  build_scop_depth (loop);
525 	  s = invalid_sese;
526 	}
527       else if (! s)
528 	s = next;
529       else
530 	{
531 	  sese_l combined = merge_sese (s, next);
532 	  if (! combined
533 	      || harmful_loop_in_region (combined))
534 	    {
535 	      add_scop (s);
536 	      s = next;
537 	    }
538 	  else
539 	    s = combined;
540 	}
541       loop = loop->next;
542     }
543   if (s)
544     add_scop (s);
545 }
546 
547 /* Returns true when Graphite can represent LOOP in SCOP.
548    FIXME: For the moment, graphite cannot be used on loops that iterate using
549    induction variables that wrap.  */
550 
551 bool
can_represent_loop(loop_p loop,sese_l scop)552 scop_detection::can_represent_loop (loop_p loop, sese_l scop)
553 {
554   tree niter;
555   struct tree_niter_desc niter_desc;
556 
557   /* We can only handle do {} while () style loops correctly.  */
558   edge exit = single_exit (loop);
559   if (!exit
560       || !single_pred_p (loop->latch)
561       || exit->src != single_pred (loop->latch)
562       || !empty_block_p (loop->latch))
563     return false;
564 
565   return !(loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
566     && number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false)
567     && niter_desc.control.no_overflow
568     && (niter = number_of_latch_executions (loop))
569     && !chrec_contains_undetermined (niter)
570     && graphite_can_represent_expr (scop, loop, niter);
571 }
572 
573 /* Return true when BEGIN is the preheader edge of a loop with a single exit
574    END.  */
575 
576 bool
region_has_one_loop(sese_l s)577 scop_detection::region_has_one_loop (sese_l s)
578 {
579   edge begin = s.entry;
580   edge end = s.exit;
581   /* Check for a single perfectly nested loop.  */
582   if (begin->dest->loop_father->inner)
583     return false;
584 
585   /* Otherwise, check whether we have adjacent loops.  */
586   return (single_pred_p (end->src)
587 	  && begin->dest->loop_father == single_pred (end->src)->loop_father);
588 }
589 
590 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END.  */
591 
592 void
add_scop(sese_l s)593 scop_detection::add_scop (sese_l s)
594 {
595   gcc_assert (s);
596 
597   /* If the exit edge is fake discard the SCoP for now as we're removing the
598      fake edges again after analysis.  */
599   if (s.exit->flags & EDGE_FAKE)
600     {
601       DEBUG_PRINT (dp << "[scop-detection-fail] Discarding infinite loop SCoP: ";
602 		   print_sese (dump_file, s));
603       return;
604     }
605 
606   /* Include the BB with the loop-closed SSA PHI nodes, we need this
607      block in the region for code-generating out-of-SSA copies.
608      canonicalize_loop_closed_ssa makes sure that is in proper shape.  */
609   if (s.exit->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
610       && loop_exit_edge_p (s.exit->src->loop_father, s.exit))
611     {
612       gcc_assert (single_pred_p (s.exit->dest)
613 		  && single_succ_p (s.exit->dest)
614 		  && sese_trivially_empty_bb_p (s.exit->dest));
615       s.exit = single_succ_edge (s.exit->dest);
616     }
617 
618   /* Do not add scops with only one loop.  */
619   if (region_has_one_loop (s))
620     {
621       DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: ";
622 		   print_sese (dump_file, s));
623       return;
624     }
625 
626   if (get_exit_bb (s) == EXIT_BLOCK_PTR_FOR_FN (cfun))
627     {
628       DEBUG_PRINT (dp << "[scop-detection-fail] "
629 		      << "Discarding SCoP exiting to return: ";
630 		   print_sese (dump_file, s));
631       return;
632     }
633 
634   /* Remove all the scops which are subsumed by s.  */
635   remove_subscops (s);
636 
637   /* Remove intersecting scops. FIXME: It will be a good idea to keep
638      the non-intersecting part of the scop already in the list.  */
639   remove_intersecting_scops (s);
640 
641   scops.safe_push (s);
642   DEBUG_PRINT (dp << "[scop-detection] Adding SCoP: "; print_sese (dump_file, s));
643 }
644 
645 /* Return true when a statement in SCOP cannot be represented by Graphite.  */
646 
647 bool
harmful_loop_in_region(sese_l scop)648 scop_detection::harmful_loop_in_region (sese_l scop) const
649 {
650   basic_block exit_bb = get_exit_bb (scop);
651   basic_block entry_bb = get_entry_bb (scop);
652 
653   DEBUG_PRINT (dp << "[checking-harmful-bbs] ";
654 	       print_sese (dump_file, scop));
655   gcc_assert (dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb));
656 
657   auto_vec<basic_block> worklist;
658   auto_bitmap loops;
659 
660   worklist.safe_push (entry_bb);
661   while (! worklist.is_empty ())
662     {
663       basic_block bb = worklist.pop ();
664       DEBUG_PRINT (dp << "Visiting bb_" << bb->index << "\n");
665 
666       /* The basic block should not be part of an irreducible loop.  */
667       if (bb->flags & BB_IRREDUCIBLE_LOOP)
668 	return true;
669 
670       /* Check for unstructured control flow: CFG not generated by structured
671 	 if-then-else.  */
672       if (bb->succs->length () > 1)
673 	{
674 	  edge e;
675 	  edge_iterator ei;
676 	  FOR_EACH_EDGE (e, ei, bb->succs)
677 	    if (!dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)
678 		&& !dominated_by_p (CDI_DOMINATORS, e->dest, bb))
679 	      return true;
680 	}
681 
682       /* Collect all loops in the current region.  */
683       loop_p loop = bb->loop_father;
684       if (loop_in_sese_p (loop, scop))
685 	bitmap_set_bit (loops, loop->num);
686 
687       /* Check for harmful statements in basic blocks part of the region.  */
688       for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
689 	   !gsi_end_p (gsi); gsi_next (&gsi))
690 	if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
691 	  return true;
692 
693       for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb);
694 	   dom;
695 	   dom = next_dom_son (CDI_DOMINATORS, dom))
696 	if (dom != scop.exit->dest)
697 	  worklist.safe_push (dom);
698     }
699 
700   /* Go through all loops and check that they are still valid in the combined
701      scop.  */
702   unsigned j;
703   bitmap_iterator bi;
704   EXECUTE_IF_SET_IN_BITMAP (loops, 0, j, bi)
705     {
706       loop_p loop = (*current_loops->larray)[j];
707       gcc_assert (loop->num == (int) j);
708 
709       /* Check if the loop nests are to be optimized for speed.  */
710       if (! loop->inner
711 	  && ! optimize_loop_for_speed_p (loop))
712 	{
713 	  DEBUG_PRINT (dp << "[scop-detection-fail] loop_"
714 		       << loop->num << " is not on a hot path.\n");
715 	  return true;
716 	}
717 
718       if (! can_represent_loop (loop, scop))
719 	{
720 	  DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_"
721 		       << loop->num << "\n");
722 	  return true;
723 	}
724 
725       /* Check if all loop nests have at least one data reference.
726 	 ???  This check is expensive and loops premature at this point.
727 	 If important to retain we can pre-compute this for all innermost
728 	 loops and reject those when we build a SESE region for a loop
729 	 during SESE discovery.  */
730       if (! loop->inner
731 	  && ! loop_nest_has_data_refs (loop))
732 	{
733 	  DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
734 		       << "does not have any data reference.\n");
735 	  return true;
736 	}
737     }
738 
739   return false;
740 }
741 
742 /* Returns true if S1 subsumes/surrounds S2.  */
743 bool
subsumes(sese_l s1,sese_l s2)744 scop_detection::subsumes (sese_l s1, sese_l s2)
745 {
746   if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
747 		      get_entry_bb (s1))
748       && dominated_by_p (CDI_POST_DOMINATORS, s2.exit->dest,
749 			 s1.exit->dest))
750     return true;
751   return false;
752 }
753 
754 /* Remove a SCoP which is subsumed by S1.  */
755 void
remove_subscops(sese_l s1)756 scop_detection::remove_subscops (sese_l s1)
757 {
758   int j;
759   sese_l *s2;
760   FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
761     {
762       if (subsumes (s1, *s2))
763 	{
764 	  DEBUG_PRINT (dp << "Removing sub-SCoP";
765 		       print_sese (dump_file, *s2));
766 	  scops.unordered_remove (j);
767 	}
768     }
769 }
770 
771 /* Returns true if S1 intersects with S2.  Since we already know that S1 does
772    not subsume S2 or vice-versa, we only check for entry bbs.  */
773 
774 bool
intersects(sese_l s1,sese_l s2)775 scop_detection::intersects (sese_l s1, sese_l s2)
776 {
777   if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
778 		      get_entry_bb (s1))
779       && !dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
780 			  get_exit_bb (s1)))
781     return true;
782   if ((s1.exit == s2.entry) || (s2.exit == s1.entry))
783     return true;
784 
785   return false;
786 }
787 
788 /* Remove one of the scops when it intersects with any other.  */
789 
790 void
remove_intersecting_scops(sese_l s1)791 scop_detection::remove_intersecting_scops (sese_l s1)
792 {
793   int j;
794   sese_l *s2;
795   FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
796     {
797       if (intersects (s1, *s2))
798 	{
799 	  DEBUG_PRINT (dp << "Removing intersecting SCoP";
800 		       print_sese (dump_file, *s2);
801 		       dp << "Intersects with:";
802 		       print_sese (dump_file, s1));
803 	  scops.unordered_remove (j);
804 	}
805     }
806 }
807 
808 /* Something like "n * m" is not allowed.  */
809 
810 bool
graphite_can_represent_init(tree e)811 scop_detection::graphite_can_represent_init (tree e)
812 {
813   switch (TREE_CODE (e))
814     {
815     case POLYNOMIAL_CHREC:
816       return graphite_can_represent_init (CHREC_LEFT (e))
817 	&& graphite_can_represent_init (CHREC_RIGHT (e));
818 
819     case MULT_EXPR:
820       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
821 	return graphite_can_represent_init (TREE_OPERAND (e, 0))
822 	  && tree_fits_shwi_p (TREE_OPERAND (e, 1));
823       else
824 	return graphite_can_represent_init (TREE_OPERAND (e, 1))
825 	  && tree_fits_shwi_p (TREE_OPERAND (e, 0));
826 
827     case PLUS_EXPR:
828     case POINTER_PLUS_EXPR:
829     case MINUS_EXPR:
830       return graphite_can_represent_init (TREE_OPERAND (e, 0))
831 	&& graphite_can_represent_init (TREE_OPERAND (e, 1));
832 
833     case NEGATE_EXPR:
834     case BIT_NOT_EXPR:
835     CASE_CONVERT:
836     case NON_LVALUE_EXPR:
837       return graphite_can_represent_init (TREE_OPERAND (e, 0));
838 
839     default:
840       break;
841     }
842 
843   return true;
844 }
845 
846 /* Return true when SCEV can be represented in the polyhedral model.
847 
848    An expression can be represented, if it can be expressed as an
849    affine expression.  For loops (i, j) and parameters (m, n) all
850    affine expressions are of the form:
851 
852    x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
853 
854    1 i + 20 j + (-2) m + 25
855 
856    Something like "i * n" or "n * m" is not allowed.  */
857 
858 bool
graphite_can_represent_scev(sese_l scop,tree scev)859 scop_detection::graphite_can_represent_scev (sese_l scop, tree scev)
860 {
861   if (chrec_contains_undetermined (scev))
862     return false;
863 
864   switch (TREE_CODE (scev))
865     {
866     case NEGATE_EXPR:
867     case BIT_NOT_EXPR:
868     CASE_CONVERT:
869     case NON_LVALUE_EXPR:
870       return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0));
871 
872     case PLUS_EXPR:
873     case POINTER_PLUS_EXPR:
874     case MINUS_EXPR:
875       return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
876 	&& graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
877 
878     case MULT_EXPR:
879       return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
880 	&& !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
881 	&& !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
882 	     && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
883 	&& graphite_can_represent_init (scev)
884 	&& graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
885 	&& graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
886 
887     case POLYNOMIAL_CHREC:
888       /* Check for constant strides.  With a non constant stride of
889 	 'n' we would have a value of 'iv * n'.  Also check that the
890 	 initial value can represented: for example 'n * m' cannot be
891 	 represented.  */
892       gcc_assert (loop_in_sese_p (get_loop (cfun,
893 					    CHREC_VARIABLE (scev)), scop));
894       if (!evolution_function_right_is_integer_cst (scev)
895 	  || !graphite_can_represent_init (scev))
896 	return false;
897       return graphite_can_represent_scev (scop, CHREC_LEFT (scev));
898 
899     case ADDR_EXPR:
900       /* We cannot encode addresses for ISL.  */
901       return false;
902 
903     default:
904       break;
905     }
906 
907   /* Only affine functions can be represented.  */
908   if (tree_contains_chrecs (scev, NULL) || !scev_is_linear_expression (scev))
909     return false;
910 
911   return true;
912 }
913 
914 /* Return true when EXPR can be represented in the polyhedral model.
915 
916    This means an expression can be represented, if it is linear with respect to
917    the loops and the strides are non parametric.  LOOP is the place where the
918    expr will be evaluated.  SCOP defines the region we analyse.  */
919 
920 bool
graphite_can_represent_expr(sese_l scop,loop_p loop,tree expr)921 scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop,
922 					     tree expr)
923 {
924   tree scev = cached_scalar_evolution_in_region (scop, loop, expr);
925   return graphite_can_represent_scev (scop, scev);
926 }
927 
928 /* Return true if the data references of STMT can be represented by Graphite.
929    We try to analyze the data references in a loop contained in the SCOP.  */
930 
931 bool
stmt_has_simple_data_refs_p(sese_l scop,gimple * stmt)932 scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
933 {
934   edge nest = scop.entry;
935   loop_p loop = loop_containing_stmt (stmt);
936   if (!loop_in_sese_p (loop, scop))
937     loop = NULL;
938 
939   auto_vec<data_reference_p> drs;
940   if (! graphite_find_data_references_in_stmt (nest, loop, stmt, &drs))
941     return false;
942 
943   int j;
944   data_reference_p dr;
945   FOR_EACH_VEC_ELT (drs, j, dr)
946     {
947       for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i)
948 	if (! graphite_can_represent_scev (scop, DR_ACCESS_FN (dr, i)))
949 	  return false;
950     }
951 
952   return true;
953 }
954 
955 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
956    Calls have side-effects, except those to const or pure
957    functions.  */
958 
959 static bool
stmt_has_side_effects(gimple * stmt)960 stmt_has_side_effects (gimple *stmt)
961 {
962   if (gimple_has_volatile_ops (stmt)
963       || (gimple_code (stmt) == GIMPLE_CALL
964 	  && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
965       || (gimple_code (stmt) == GIMPLE_ASM))
966     {
967       DEBUG_PRINT (dp << "[scop-detection-fail] "
968 		      << "Statement has side-effects:\n";
969 	print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
970       return true;
971     }
972   return false;
973 }
974 
975 /* Return true only when STMT is simple enough for being handled by Graphite.
976    This depends on SCOP, as the parameters are initialized relatively to
977    this basic block, the linear functions are initialized based on the outermost
978    loop containing STMT inside the SCOP.  BB is the place where we try to
979    evaluate the STMT.  */
980 
981 bool
stmt_simple_for_scop_p(sese_l scop,gimple * stmt,basic_block bb)982 scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
983 					basic_block bb) const
984 {
985   gcc_assert (scop);
986 
987   if (is_gimple_debug (stmt))
988     return true;
989 
990   if (stmt_has_side_effects (stmt))
991     return false;
992 
993   if (!stmt_has_simple_data_refs_p (scop, stmt))
994     {
995       DEBUG_PRINT (dp << "[scop-detection-fail] "
996 		      << "Graphite cannot handle data-refs in stmt:\n";
997 	print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS););
998       return false;
999     }
1000 
1001   switch (gimple_code (stmt))
1002     {
1003     case GIMPLE_LABEL:
1004       return true;
1005 
1006     case GIMPLE_COND:
1007       {
1008 	/* We can handle all binary comparisons.  Inequalities are
1009 	   also supported as they can be represented with union of
1010 	   polyhedra.  */
1011 	enum tree_code code = gimple_cond_code (stmt);
1012 	if (!(code == LT_EXPR
1013 	      || code == GT_EXPR
1014 	      || code == LE_EXPR
1015 	      || code == GE_EXPR
1016 	      || code == EQ_EXPR
1017 	      || code == NE_EXPR))
1018 	  {
1019 	    DEBUG_PRINT (dp << "[scop-detection-fail] "
1020 			    << "Graphite cannot handle cond stmt:\n";
1021 			 print_gimple_stmt (dump_file, stmt, 0,
1022 					    TDF_VOPS | TDF_MEMSYMS));
1023 	    return false;
1024 	  }
1025 
1026 	loop_p loop = bb->loop_father;
1027 	for (unsigned i = 0; i < 2; ++i)
1028 	  {
1029 	    tree op = gimple_op (stmt, i);
1030 	    if (!graphite_can_represent_expr (scop, loop, op)
1031 		/* We can only constrain on integer type.  */
1032 		|| ! INTEGRAL_TYPE_P (TREE_TYPE (op)))
1033 	      {
1034 		DEBUG_PRINT (dp << "[scop-detection-fail] "
1035 				<< "Graphite cannot represent stmt:\n";
1036 			     print_gimple_stmt (dump_file, stmt, 0,
1037 						TDF_VOPS | TDF_MEMSYMS));
1038 		return false;
1039 	      }
1040 	  }
1041 
1042 	return true;
1043       }
1044 
1045     case GIMPLE_ASSIGN:
1046     case GIMPLE_CALL:
1047       {
1048 	tree op, lhs = gimple_get_lhs (stmt);
1049 	ssa_op_iter i;
1050 	/* If we are not going to instantiate the stmt do not require
1051 	   its operands to be instantiatable at this point.  */
1052 	if (lhs
1053 	    && TREE_CODE (lhs) == SSA_NAME
1054 	    && scev_analyzable_p (lhs, scop))
1055 	  return true;
1056 	/* Verify that if we can analyze operands at their def site we
1057 	   also can represent them when analyzed at their uses.  */
1058 	FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
1059 	  if (scev_analyzable_p (op, scop)
1060 	      && chrec_contains_undetermined
1061 		   (cached_scalar_evolution_in_region (scop,
1062 						       bb->loop_father, op)))
1063 	    {
1064 	      DEBUG_PRINT (dp << "[scop-detection-fail] "
1065 			   << "Graphite cannot code-gen stmt:\n";
1066 			   print_gimple_stmt (dump_file, stmt, 0,
1067 					      TDF_VOPS | TDF_MEMSYMS));
1068 	      return false;
1069 	    }
1070 	return true;
1071       }
1072 
1073     default:
1074       /* These nodes cut a new scope.  */
1075       DEBUG_PRINT (
1076 	  dp << "[scop-detection-fail] "
1077 	     << "Gimple stmt not handled in Graphite:\n";
1078 	  print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1079       return false;
1080     }
1081 }
1082 
1083 /* Returns the number of pbbs that are in loops contained in SCOP.  */
1084 
1085 int
nb_pbbs_in_loops(scop_p scop)1086 scop_detection::nb_pbbs_in_loops (scop_p scop)
1087 {
1088   int i;
1089   poly_bb_p pbb;
1090   int res = 0;
1091 
1092   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1093     if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), scop->scop_info->region))
1094       res++;
1095 
1096   return res;
1097 }
1098 
1099 /* Assigns the parameter NAME an index in REGION.  */
1100 
1101 static void
assign_parameter_index_in_region(tree name,sese_info_p region)1102 assign_parameter_index_in_region (tree name, sese_info_p region)
1103 {
1104   gcc_assert (TREE_CODE (name) == SSA_NAME
1105 	      && ! defined_in_sese_p (name, region->region));
1106   int i;
1107   tree p;
1108   FOR_EACH_VEC_ELT (region->params, i, p)
1109     if (p == name)
1110       return;
1111 
1112   region->params.safe_push (name);
1113 }
1114 
1115 /* In the context of sese S, scan the expression E and translate it to
1116    a linear expression C.  When parsing a symbolic multiplication, K
1117    represents the constant multiplier of an expression containing
1118    parameters.  */
1119 
1120 static void
scan_tree_for_params(sese_info_p s,tree e)1121 scan_tree_for_params (sese_info_p s, tree e)
1122 {
1123   if (e == chrec_dont_know)
1124     return;
1125 
1126   switch (TREE_CODE (e))
1127     {
1128     case POLYNOMIAL_CHREC:
1129       scan_tree_for_params (s, CHREC_LEFT (e));
1130       break;
1131 
1132     case MULT_EXPR:
1133       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
1134 	scan_tree_for_params (s, TREE_OPERAND (e, 0));
1135       else
1136 	scan_tree_for_params (s, TREE_OPERAND (e, 1));
1137       break;
1138 
1139     case PLUS_EXPR:
1140     case POINTER_PLUS_EXPR:
1141     case MINUS_EXPR:
1142       scan_tree_for_params (s, TREE_OPERAND (e, 0));
1143       scan_tree_for_params (s, TREE_OPERAND (e, 1));
1144       break;
1145 
1146     case NEGATE_EXPR:
1147     case BIT_NOT_EXPR:
1148     CASE_CONVERT:
1149     case NON_LVALUE_EXPR:
1150       scan_tree_for_params (s, TREE_OPERAND (e, 0));
1151       break;
1152 
1153     case SSA_NAME:
1154       assign_parameter_index_in_region (e, s);
1155       break;
1156 
1157     case INTEGER_CST:
1158     case ADDR_EXPR:
1159     case REAL_CST:
1160     case COMPLEX_CST:
1161     case VECTOR_CST:
1162       break;
1163 
1164    default:
1165       gcc_unreachable ();
1166       break;
1167     }
1168 }
1169 
1170 /* Find parameters with respect to REGION in BB. We are looking in memory
1171    access functions, conditions and loop bounds.  */
1172 
1173 static void
find_params_in_bb(sese_info_p region,gimple_poly_bb_p gbb)1174 find_params_in_bb (sese_info_p region, gimple_poly_bb_p gbb)
1175 {
1176   /* Find parameters in the access functions of data references.  */
1177   int i;
1178   data_reference_p dr;
1179   FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr)
1180     for (unsigned j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
1181       scan_tree_for_params (region, DR_ACCESS_FN (dr, j));
1182 
1183   /* Find parameters in conditional statements.  */
1184   gimple *stmt;
1185   FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
1186     {
1187       loop_p loop = gimple_bb (stmt)->loop_father;
1188       tree lhs = cached_scalar_evolution_in_region (region->region, loop,
1189 						    gimple_cond_lhs (stmt));
1190       tree rhs = cached_scalar_evolution_in_region (region->region, loop,
1191 						    gimple_cond_rhs (stmt));
1192       gcc_assert (!chrec_contains_undetermined (lhs)
1193 		  && !chrec_contains_undetermined (rhs));
1194 
1195       scan_tree_for_params (region, lhs);
1196       scan_tree_for_params (region, rhs);
1197     }
1198 }
1199 
1200 /* Record the parameters used in the SCOP BBs.  A variable is a parameter
1201    in a scop if it does not vary during the execution of that scop.  */
1202 
1203 static void
find_scop_parameters(scop_p scop)1204 find_scop_parameters (scop_p scop)
1205 {
1206   unsigned i;
1207   sese_info_p region = scop->scop_info;
1208 
1209   /* Parameters used in loop bounds are processed during gather_bbs.  */
1210 
1211   /* Find the parameters used in data accesses.  */
1212   poly_bb_p pbb;
1213   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1214     find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1215 
1216   int nbp = sese_nb_params (region);
1217   scop_set_nb_params (scop, nbp);
1218 }
1219 
1220 static void
add_write(vec<tree> * writes,tree def)1221 add_write (vec<tree> *writes, tree def)
1222 {
1223   writes->safe_push (def);
1224   DEBUG_PRINT (dp << "Adding scalar write: ";
1225 	       print_generic_expr (dump_file, def);
1226 	       dp << "\nFrom stmt: ";
1227 	       print_gimple_stmt (dump_file,
1228 				  SSA_NAME_DEF_STMT (def), 0));
1229 }
1230 
1231 static void
add_read(vec<scalar_use> * reads,tree use,gimple * use_stmt)1232 add_read (vec<scalar_use> *reads, tree use, gimple *use_stmt)
1233 {
1234   DEBUG_PRINT (dp << "Adding scalar read: ";
1235 	       print_generic_expr (dump_file, use);
1236 	       dp << "\nFrom stmt: ";
1237 	       print_gimple_stmt (dump_file, use_stmt, 0));
1238   reads->safe_push (std::make_pair (use_stmt, use));
1239 }
1240 
1241 
1242 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP.  */
1243 
1244 static void
build_cross_bb_scalars_def(scop_p scop,tree def,basic_block def_bb,vec<tree> * writes)1245 build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb,
1246 			     vec<tree> *writes)
1247 {
1248   if (!is_gimple_reg (def))
1249     return;
1250 
1251   bool scev_analyzable = scev_analyzable_p (def, scop->scop_info->region);
1252 
1253   gimple *use_stmt;
1254   imm_use_iterator imm_iter;
1255   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
1256     /* Do not gather scalar variables that can be analyzed by SCEV as they can
1257        be generated out of the induction variables.  */
1258     if ((! scev_analyzable
1259 	 /* But gather SESE liveouts as we otherwise fail to rewrite their
1260 	    exit PHIs.  */
1261 	 || ! bb_in_sese_p (gimple_bb (use_stmt), scop->scop_info->region))
1262 	&& (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt)))
1263       {
1264 	add_write (writes, def);
1265 	/* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1266 	   before all the uses have been visited.  */
1267 	BREAK_FROM_IMM_USE_STMT (imm_iter);
1268       }
1269 }
1270 
1271 /* Record USE if it is defined in other bbs different than USE_STMT
1272    in the SCOP.  */
1273 
1274 static void
build_cross_bb_scalars_use(scop_p scop,tree use,gimple * use_stmt,vec<scalar_use> * reads)1275 build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
1276 			    vec<scalar_use> *reads)
1277 {
1278   if (!is_gimple_reg (use))
1279     return;
1280 
1281   /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1282      generated out of the induction variables.  */
1283   if (scev_analyzable_p (use, scop->scop_info->region))
1284     return;
1285 
1286   gimple *def_stmt = SSA_NAME_DEF_STMT (use);
1287   if (gimple_bb (def_stmt) != gimple_bb (use_stmt))
1288     add_read (reads, use, use_stmt);
1289 }
1290 
1291 /* Generates a polyhedral black box only if the bb contains interesting
1292    information.  */
1293 
1294 static gimple_poly_bb_p
try_generate_gimple_bb(scop_p scop,basic_block bb)1295 try_generate_gimple_bb (scop_p scop, basic_block bb)
1296 {
1297   vec<data_reference_p> drs = vNULL;
1298   vec<tree> writes = vNULL;
1299   vec<scalar_use> reads = vNULL;
1300 
1301   sese_l region = scop->scop_info->region;
1302   edge nest = region.entry;
1303   loop_p loop = bb->loop_father;
1304   if (!loop_in_sese_p (loop, region))
1305     loop = NULL;
1306 
1307   for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1308        gsi_next (&gsi))
1309     {
1310       gimple *stmt = gsi_stmt (gsi);
1311       if (is_gimple_debug (stmt))
1312 	continue;
1313 
1314       graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
1315 
1316       tree def = gimple_get_lhs (stmt);
1317       if (def)
1318 	build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), &writes);
1319 
1320       ssa_op_iter iter;
1321       tree use;
1322       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1323 	build_cross_bb_scalars_use (scop, use, stmt, &reads);
1324     }
1325 
1326   /* Handle defs and uses in PHIs.  Those need special treatment given
1327      that we have to present ISL with sth that looks like we've rewritten
1328      the IL out-of-SSA.  */
1329   for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
1330        gsi_next (&psi))
1331     {
1332       gphi *phi = psi.phi ();
1333       tree res = gimple_phi_result (phi);
1334       if (virtual_operand_p (res)
1335 	  || scev_analyzable_p (res, scop->scop_info->region))
1336 	continue;
1337       /* To simulate out-of-SSA the block containing the PHI node has
1338          reads of the PHI destination.  And to preserve SSA dependences
1339 	 we also write to it (the out-of-SSA decl and the SSA result
1340 	 are coalesced for dependence purposes which is good enough).  */
1341       add_read (&reads, res, phi);
1342       add_write (&writes, res);
1343     }
1344   basic_block bb_for_succs = bb;
1345   if (bb_for_succs == bb_for_succs->loop_father->latch
1346       && bb_in_sese_p (bb_for_succs, scop->scop_info->region)
1347       && sese_trivially_empty_bb_p (bb_for_succs))
1348     bb_for_succs = NULL;
1349   while (bb_for_succs)
1350     {
1351       basic_block latch = NULL;
1352       edge_iterator ei;
1353       edge e;
1354       FOR_EACH_EDGE (e, ei, bb_for_succs->succs)
1355 	{
1356 	  for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi);
1357 	       gsi_next (&psi))
1358 	    {
1359 	      gphi *phi = psi.phi ();
1360 	      tree res = gimple_phi_result (phi);
1361 	      if (virtual_operand_p (res))
1362 		continue;
1363 	      /* To simulate out-of-SSA the predecessor of edges into PHI nodes
1364 		 has a copy from the PHI argument to the PHI destination.  */
1365 	      if (! scev_analyzable_p (res, scop->scop_info->region))
1366 		add_write (&writes, res);
1367 	      tree use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1368 	      if (TREE_CODE (use) == SSA_NAME
1369 		  && ! SSA_NAME_IS_DEFAULT_DEF (use)
1370 		  && gimple_bb (SSA_NAME_DEF_STMT (use)) != bb_for_succs
1371 		  && ! scev_analyzable_p (use, scop->scop_info->region))
1372 		add_read (&reads, use, phi);
1373 	    }
1374 	  if (e->dest == bb_for_succs->loop_father->latch
1375 	      && bb_in_sese_p (e->dest, scop->scop_info->region)
1376 	      && sese_trivially_empty_bb_p (e->dest))
1377 	    latch = e->dest;
1378 	}
1379       /* Handle empty latch block PHIs here, otherwise we confuse ISL
1380 	 with extra conditional code where it then peels off the last
1381 	 iteration just because of that.  It would be simplest if we
1382 	 just didn't force simple latches (thus remove the forwarder).  */
1383       bb_for_succs = latch;
1384     }
1385 
1386   /* For the region exit block add reads for all live-out vars.  */
1387   if (bb == scop->scop_info->region.exit->src)
1388     {
1389       sese_build_liveouts (scop->scop_info);
1390       unsigned i;
1391       bitmap_iterator bi;
1392       EXECUTE_IF_SET_IN_BITMAP (scop->scop_info->liveout, 0, i, bi)
1393 	{
1394 	  tree use = ssa_name (i);
1395 	  add_read (&reads, use, NULL);
1396 	}
1397     }
1398 
1399   if (drs.is_empty () && writes.is_empty () && reads.is_empty ())
1400     return NULL;
1401 
1402   return new_gimple_poly_bb (bb, drs, reads, writes);
1403 }
1404 
1405 /* Compute alias-sets for all data references in DRS.  */
1406 
1407 static bool
build_alias_set(scop_p scop)1408 build_alias_set (scop_p scop)
1409 {
1410   int num_vertices = scop->drs.length ();
1411   struct graph *g = new_graph (num_vertices);
1412   dr_info *dr1, *dr2;
1413   int i, j;
1414   int *all_vertices;
1415 
1416   struct loop *nest
1417     = find_common_loop (scop->scop_info->region.entry->dest->loop_father,
1418 			scop->scop_info->region.exit->src->loop_father);
1419 
1420   FOR_EACH_VEC_ELT (scop->drs, i, dr1)
1421     for (j = i+1; scop->drs.iterate (j, &dr2); j++)
1422       if (dr_may_alias_p (dr1->dr, dr2->dr, nest))
1423 	{
1424 	  /* Dependences in the same alias set need to be handled
1425 	     by just looking at DR_ACCESS_FNs.  */
1426 	  if (DR_NUM_DIMENSIONS (dr1->dr) == 0
1427 	      || DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr)
1428 	      || ! operand_equal_p (DR_BASE_OBJECT (dr1->dr),
1429 				    DR_BASE_OBJECT (dr2->dr),
1430 				    OEP_ADDRESS_OF)
1431 	      || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)),
1432 				       TREE_TYPE (DR_BASE_OBJECT (dr2->dr))))
1433 	    {
1434 	      free_graph (g);
1435 	      return false;
1436 	    }
1437 	  add_edge (g, i, j);
1438 	  add_edge (g, j, i);
1439 	}
1440 
1441   all_vertices = XNEWVEC (int, num_vertices);
1442   for (i = 0; i < num_vertices; i++)
1443     all_vertices[i] = i;
1444 
1445   scop->max_alias_set
1446     = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1;
1447   free (all_vertices);
1448 
1449   for (i = 0; i < g->n_vertices; i++)
1450     scop->drs[i].alias_set = g->vertices[i].component + 1;
1451 
1452   free_graph (g);
1453   return true;
1454 }
1455 
1456 /* Gather BBs and conditions for a SCOP.  */
1457 class gather_bbs : public dom_walker
1458 {
1459 public:
1460   gather_bbs (cdi_direction, scop_p, int *);
1461 
1462   virtual edge before_dom_children (basic_block);
1463   virtual void after_dom_children (basic_block);
1464 
1465 private:
1466   auto_vec<gimple *, 3> conditions, cases;
1467   scop_p scop;
1468 };
1469 }
gather_bbs(cdi_direction direction,scop_p scop,int * bb_to_rpo)1470 gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo)
1471   : dom_walker (direction, ALL_BLOCKS, bb_to_rpo), scop (scop)
1472 {
1473 }
1474 
1475 /* Call-back for dom_walk executed before visiting the dominated
1476    blocks.  */
1477 
1478 edge
before_dom_children(basic_block bb)1479 gather_bbs::before_dom_children (basic_block bb)
1480 {
1481   sese_info_p region = scop->scop_info;
1482   if (!bb_in_sese_p (bb, region->region))
1483     return dom_walker::STOP;
1484 
1485   /* For loops fully contained in the region record parameters in the
1486      loop bounds.  */
1487   loop_p loop = bb->loop_father;
1488   if (loop->header == bb
1489       && loop_in_sese_p (loop, region->region))
1490     {
1491       tree nb_iters = number_of_latch_executions (loop);
1492       if (chrec_contains_symbols (nb_iters))
1493 	{
1494 	  nb_iters = cached_scalar_evolution_in_region (region->region,
1495 							loop, nb_iters);
1496 	  scan_tree_for_params (region, nb_iters);
1497 	}
1498     }
1499 
1500   if (gcond *stmt = single_pred_cond_non_loop_exit (bb))
1501     {
1502       edge e = single_pred_edge (bb);
1503       /* Make sure the condition is in the region and thus was verified
1504          to be handled.  */
1505       if (e != region->region.entry)
1506 	{
1507 	  conditions.safe_push (stmt);
1508 	  if (e->flags & EDGE_TRUE_VALUE)
1509 	    cases.safe_push (stmt);
1510 	  else
1511 	    cases.safe_push (NULL);
1512 	}
1513     }
1514 
1515   scop->scop_info->bbs.safe_push (bb);
1516 
1517   gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
1518   if (!gbb)
1519     return NULL;
1520 
1521   GBB_CONDITIONS (gbb) = conditions.copy ();
1522   GBB_CONDITION_CASES (gbb) = cases.copy ();
1523 
1524   poly_bb_p pbb = new_poly_bb (scop, gbb);
1525   scop->pbbs.safe_push (pbb);
1526 
1527   int i;
1528   data_reference_p dr;
1529   FOR_EACH_VEC_ELT (gbb->data_refs, i, dr)
1530     {
1531       DEBUG_PRINT (dp << "Adding memory ";
1532 		   if (dr->is_read)
1533 		     dp << "read: ";
1534 		   else
1535 		     dp << "write: ";
1536 		   print_generic_expr (dump_file, dr->ref);
1537 		   dp << "\nFrom stmt: ";
1538 		   print_gimple_stmt (dump_file, dr->stmt, 0));
1539 
1540       scop->drs.safe_push (dr_info (dr, pbb));
1541     }
1542 
1543   return NULL;
1544 }
1545 
1546 /* Call-back for dom_walk executed after visiting the dominated
1547    blocks.  */
1548 
1549 void
after_dom_children(basic_block bb)1550 gather_bbs::after_dom_children (basic_block bb)
1551 {
1552   if (!bb_in_sese_p (bb, scop->scop_info->region))
1553     return;
1554 
1555   if (single_pred_cond_non_loop_exit (bb))
1556     {
1557       edge e = single_pred_edge (bb);
1558       if (e != scop->scop_info->region.entry)
1559 	{
1560 	  conditions.pop ();
1561 	  cases.pop ();
1562 	}
1563     }
1564 }
1565 
1566 
1567 /* Compute sth like an execution order, dominator order with first executing
1568    edges that stay inside the current loop, delaying processing exit edges.  */
1569 
1570 static int *bb_to_rpo;
1571 
1572 /* Helper for qsort, sorting after order above.  */
1573 
1574 static int
cmp_pbbs(const void * pa,const void * pb)1575 cmp_pbbs (const void *pa, const void *pb)
1576 {
1577   poly_bb_p bb1 = *((const poly_bb_p *)pa);
1578   poly_bb_p bb2 = *((const poly_bb_p *)pb);
1579   if (bb_to_rpo[bb1->black_box->bb->index]
1580       < bb_to_rpo[bb2->black_box->bb->index])
1581     return -1;
1582   else if (bb_to_rpo[bb1->black_box->bb->index]
1583 	   > bb_to_rpo[bb2->black_box->bb->index])
1584     return 1;
1585   else
1586     return 0;
1587 }
1588 
1589 /* Find Static Control Parts (SCoP) in the current function and pushes
1590    them to SCOPS.  */
1591 
1592 void
build_scops(vec<scop_p> * scops)1593 build_scops (vec<scop_p> *scops)
1594 {
1595   if (dump_file)
1596     dp.set_dump_file (dump_file);
1597 
1598   scop_detection sb;
1599   sb.build_scop_depth (current_loops->tree_root);
1600 
1601   /* Now create scops from the lightweight SESEs.  */
1602   vec<sese_l> scops_l = sb.get_scops ();
1603 
1604   /* Domwalk needs a bb to RPO mapping.  Compute it once here.  */
1605   int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1606   int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true);
1607   bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
1608   for (int i = 0; i < postorder_num; ++i)
1609     bb_to_rpo[postorder[i]] = i;
1610   free (postorder);
1611 
1612   int i;
1613   sese_l *s;
1614   FOR_EACH_VEC_ELT (scops_l, i, s)
1615     {
1616       scop_p scop = new_scop (s->entry, s->exit);
1617 
1618       /* Record all basic blocks and their conditions in REGION.  */
1619       gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo).walk (s->entry->dest);
1620 
1621       /* Sort pbbs after execution order for initial schedule generation.  */
1622       scop->pbbs.qsort (cmp_pbbs);
1623 
1624       if (! build_alias_set (scop))
1625 	{
1626 	  DEBUG_PRINT (dp << "[scop-detection-fail] cannot handle dependences\n");
1627 	  free_scop (scop);
1628 	  continue;
1629 	}
1630 
1631       /* Do not optimize a scop containing only PBBs that do not belong
1632 	 to any loops.  */
1633       if (sb.nb_pbbs_in_loops (scop) == 0)
1634 	{
1635 	  DEBUG_PRINT (dp << "[scop-detection-fail] no data references.\n");
1636 	  free_scop (scop);
1637 	  continue;
1638 	}
1639 
1640       unsigned max_arrays = param_graphite_max_arrays_per_scop;
1641       if (max_arrays > 0
1642 	  && scop->drs.length () >= max_arrays)
1643 	{
1644 	  DEBUG_PRINT (dp << "[scop-detection-fail] too many data references: "
1645 		       << scop->drs.length ()
1646 		       << " is larger than --param graphite-max-arrays-per-scop="
1647 		       << max_arrays << ".\n");
1648 	  free_scop (scop);
1649 	  continue;
1650 	}
1651 
1652       find_scop_parameters (scop);
1653       graphite_dim_t max_dim = param_graphite_max_nb_scop_params;
1654       if (max_dim > 0
1655 	  && scop_nb_params (scop) > max_dim)
1656 	{
1657 	  DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: "
1658 			  << scop_nb_params (scop)
1659 			  << " larger than --param graphite-max-nb-scop-params="
1660 			  << max_dim << ".\n");
1661 	  free_scop (scop);
1662 	  continue;
1663 	}
1664 
1665       scops->safe_push (scop);
1666     }
1667 
1668   free (bb_to_rpo);
1669   bb_to_rpo = NULL;
1670   DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0););
1671 }
1672 
1673 #endif /* HAVE_isl */
1674