1 /* Detection of Static Control Parts (SCoP) for Graphite.
2    Copyright (C) 2009-2021 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 INCLUDE_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 	break;
1266       }
1267 }
1268 
1269 /* Record USE if it is defined in other bbs different than USE_STMT
1270    in the SCOP.  */
1271 
1272 static void
build_cross_bb_scalars_use(scop_p scop,tree use,gimple * use_stmt,vec<scalar_use> * reads)1273 build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
1274 			    vec<scalar_use> *reads)
1275 {
1276   if (!is_gimple_reg (use))
1277     return;
1278 
1279   /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1280      generated out of the induction variables.  */
1281   if (scev_analyzable_p (use, scop->scop_info->region))
1282     return;
1283 
1284   gimple *def_stmt = SSA_NAME_DEF_STMT (use);
1285   if (gimple_bb (def_stmt) != gimple_bb (use_stmt))
1286     add_read (reads, use, use_stmt);
1287 }
1288 
1289 /* Generates a polyhedral black box only if the bb contains interesting
1290    information.  */
1291 
1292 static gimple_poly_bb_p
try_generate_gimple_bb(scop_p scop,basic_block bb)1293 try_generate_gimple_bb (scop_p scop, basic_block bb)
1294 {
1295   vec<data_reference_p> drs = vNULL;
1296   vec<tree> writes = vNULL;
1297   vec<scalar_use> reads = vNULL;
1298 
1299   sese_l region = scop->scop_info->region;
1300   edge nest = region.entry;
1301   loop_p loop = bb->loop_father;
1302   if (!loop_in_sese_p (loop, region))
1303     loop = NULL;
1304 
1305   for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1306        gsi_next (&gsi))
1307     {
1308       gimple *stmt = gsi_stmt (gsi);
1309       if (is_gimple_debug (stmt))
1310 	continue;
1311 
1312       graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
1313 
1314       tree def = gimple_get_lhs (stmt);
1315       if (def)
1316 	build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), &writes);
1317 
1318       ssa_op_iter iter;
1319       tree use;
1320       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1321 	build_cross_bb_scalars_use (scop, use, stmt, &reads);
1322     }
1323 
1324   /* Handle defs and uses in PHIs.  Those need special treatment given
1325      that we have to present ISL with sth that looks like we've rewritten
1326      the IL out-of-SSA.  */
1327   for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
1328        gsi_next (&psi))
1329     {
1330       gphi *phi = psi.phi ();
1331       tree res = gimple_phi_result (phi);
1332       if (virtual_operand_p (res)
1333 	  || scev_analyzable_p (res, scop->scop_info->region))
1334 	continue;
1335       /* To simulate out-of-SSA the block containing the PHI node has
1336          reads of the PHI destination.  And to preserve SSA dependences
1337 	 we also write to it (the out-of-SSA decl and the SSA result
1338 	 are coalesced for dependence purposes which is good enough).  */
1339       add_read (&reads, res, phi);
1340       add_write (&writes, res);
1341     }
1342   basic_block bb_for_succs = bb;
1343   if (bb_for_succs == bb_for_succs->loop_father->latch
1344       && bb_in_sese_p (bb_for_succs, scop->scop_info->region)
1345       && sese_trivially_empty_bb_p (bb_for_succs))
1346     bb_for_succs = NULL;
1347   while (bb_for_succs)
1348     {
1349       basic_block latch = NULL;
1350       edge_iterator ei;
1351       edge e;
1352       FOR_EACH_EDGE (e, ei, bb_for_succs->succs)
1353 	{
1354 	  for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi);
1355 	       gsi_next (&psi))
1356 	    {
1357 	      gphi *phi = psi.phi ();
1358 	      tree res = gimple_phi_result (phi);
1359 	      if (virtual_operand_p (res))
1360 		continue;
1361 	      /* To simulate out-of-SSA the predecessor of edges into PHI nodes
1362 		 has a copy from the PHI argument to the PHI destination.  */
1363 	      if (! scev_analyzable_p (res, scop->scop_info->region))
1364 		add_write (&writes, res);
1365 	      tree use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1366 	      if (TREE_CODE (use) == SSA_NAME
1367 		  && ! SSA_NAME_IS_DEFAULT_DEF (use)
1368 		  && gimple_bb (SSA_NAME_DEF_STMT (use)) != bb_for_succs
1369 		  && ! scev_analyzable_p (use, scop->scop_info->region))
1370 		add_read (&reads, use, phi);
1371 	    }
1372 	  if (e->dest == bb_for_succs->loop_father->latch
1373 	      && bb_in_sese_p (e->dest, scop->scop_info->region)
1374 	      && sese_trivially_empty_bb_p (e->dest))
1375 	    latch = e->dest;
1376 	}
1377       /* Handle empty latch block PHIs here, otherwise we confuse ISL
1378 	 with extra conditional code where it then peels off the last
1379 	 iteration just because of that.  It would be simplest if we
1380 	 just didn't force simple latches (thus remove the forwarder).  */
1381       bb_for_succs = latch;
1382     }
1383 
1384   /* For the region exit block add reads for all live-out vars.  */
1385   if (bb == scop->scop_info->region.exit->src)
1386     {
1387       sese_build_liveouts (scop->scop_info);
1388       unsigned i;
1389       bitmap_iterator bi;
1390       EXECUTE_IF_SET_IN_BITMAP (scop->scop_info->liveout, 0, i, bi)
1391 	{
1392 	  tree use = ssa_name (i);
1393 	  add_read (&reads, use, NULL);
1394 	}
1395     }
1396 
1397   if (drs.is_empty () && writes.is_empty () && reads.is_empty ())
1398     return NULL;
1399 
1400   return new_gimple_poly_bb (bb, drs, reads, writes);
1401 }
1402 
1403 /* Compute alias-sets for all data references in DRS.  */
1404 
1405 static bool
build_alias_set(scop_p scop)1406 build_alias_set (scop_p scop)
1407 {
1408   int num_vertices = scop->drs.length ();
1409   struct graph *g = new_graph (num_vertices);
1410   dr_info *dr1, *dr2;
1411   int i, j;
1412   int *all_vertices;
1413 
1414   struct loop *nest
1415     = find_common_loop (scop->scop_info->region.entry->dest->loop_father,
1416 			scop->scop_info->region.exit->src->loop_father);
1417 
1418   FOR_EACH_VEC_ELT (scop->drs, i, dr1)
1419     for (j = i+1; scop->drs.iterate (j, &dr2); j++)
1420       if (dr_may_alias_p (dr1->dr, dr2->dr, nest))
1421 	{
1422 	  /* Dependences in the same alias set need to be handled
1423 	     by just looking at DR_ACCESS_FNs.  */
1424 	  if (DR_NUM_DIMENSIONS (dr1->dr) == 0
1425 	      || DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr)
1426 	      || ! operand_equal_p (DR_BASE_OBJECT (dr1->dr),
1427 				    DR_BASE_OBJECT (dr2->dr),
1428 				    OEP_ADDRESS_OF)
1429 	      || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)),
1430 				       TREE_TYPE (DR_BASE_OBJECT (dr2->dr))))
1431 	    {
1432 	      free_graph (g);
1433 	      return false;
1434 	    }
1435 	  add_edge (g, i, j);
1436 	  add_edge (g, j, i);
1437 	}
1438 
1439   all_vertices = XNEWVEC (int, num_vertices);
1440   for (i = 0; i < num_vertices; i++)
1441     all_vertices[i] = i;
1442 
1443   scop->max_alias_set
1444     = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1;
1445   free (all_vertices);
1446 
1447   for (i = 0; i < g->n_vertices; i++)
1448     scop->drs[i].alias_set = g->vertices[i].component + 1;
1449 
1450   free_graph (g);
1451   return true;
1452 }
1453 
1454 /* Gather BBs and conditions for a SCOP.  */
1455 class gather_bbs : public dom_walker
1456 {
1457 public:
1458   gather_bbs (cdi_direction, scop_p, int *);
1459 
1460   virtual edge before_dom_children (basic_block);
1461   virtual void after_dom_children (basic_block);
1462 
1463 private:
1464   auto_vec<gimple *, 3> conditions, cases;
1465   scop_p scop;
1466 };
1467 }
gather_bbs(cdi_direction direction,scop_p scop,int * bb_to_rpo)1468 gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo)
1469   : dom_walker (direction, ALL_BLOCKS, bb_to_rpo), scop (scop)
1470 {
1471 }
1472 
1473 /* Call-back for dom_walk executed before visiting the dominated
1474    blocks.  */
1475 
1476 edge
before_dom_children(basic_block bb)1477 gather_bbs::before_dom_children (basic_block bb)
1478 {
1479   sese_info_p region = scop->scop_info;
1480   if (!bb_in_sese_p (bb, region->region))
1481     return dom_walker::STOP;
1482 
1483   /* For loops fully contained in the region record parameters in the
1484      loop bounds.  */
1485   loop_p loop = bb->loop_father;
1486   if (loop->header == bb
1487       && loop_in_sese_p (loop, region->region))
1488     {
1489       tree nb_iters = number_of_latch_executions (loop);
1490       if (chrec_contains_symbols (nb_iters))
1491 	{
1492 	  nb_iters = cached_scalar_evolution_in_region (region->region,
1493 							loop, nb_iters);
1494 	  scan_tree_for_params (region, nb_iters);
1495 	}
1496     }
1497 
1498   if (gcond *stmt = single_pred_cond_non_loop_exit (bb))
1499     {
1500       edge e = single_pred_edge (bb);
1501       /* Make sure the condition is in the region and thus was verified
1502          to be handled.  */
1503       if (e != region->region.entry)
1504 	{
1505 	  conditions.safe_push (stmt);
1506 	  if (e->flags & EDGE_TRUE_VALUE)
1507 	    cases.safe_push (stmt);
1508 	  else
1509 	    cases.safe_push (NULL);
1510 	}
1511     }
1512 
1513   scop->scop_info->bbs.safe_push (bb);
1514 
1515   gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
1516   if (!gbb)
1517     return NULL;
1518 
1519   GBB_CONDITIONS (gbb) = conditions.copy ();
1520   GBB_CONDITION_CASES (gbb) = cases.copy ();
1521 
1522   poly_bb_p pbb = new_poly_bb (scop, gbb);
1523   scop->pbbs.safe_push (pbb);
1524 
1525   int i;
1526   data_reference_p dr;
1527   FOR_EACH_VEC_ELT (gbb->data_refs, i, dr)
1528     {
1529       DEBUG_PRINT (dp << "Adding memory ";
1530 		   if (dr->is_read)
1531 		     dp << "read: ";
1532 		   else
1533 		     dp << "write: ";
1534 		   print_generic_expr (dump_file, dr->ref);
1535 		   dp << "\nFrom stmt: ";
1536 		   print_gimple_stmt (dump_file, dr->stmt, 0));
1537 
1538       scop->drs.safe_push (dr_info (dr, pbb));
1539     }
1540 
1541   return NULL;
1542 }
1543 
1544 /* Call-back for dom_walk executed after visiting the dominated
1545    blocks.  */
1546 
1547 void
after_dom_children(basic_block bb)1548 gather_bbs::after_dom_children (basic_block bb)
1549 {
1550   if (!bb_in_sese_p (bb, scop->scop_info->region))
1551     return;
1552 
1553   if (single_pred_cond_non_loop_exit (bb))
1554     {
1555       edge e = single_pred_edge (bb);
1556       if (e != scop->scop_info->region.entry)
1557 	{
1558 	  conditions.pop ();
1559 	  cases.pop ();
1560 	}
1561     }
1562 }
1563 
1564 
1565 /* Compute sth like an execution order, dominator order with first executing
1566    edges that stay inside the current loop, delaying processing exit edges.  */
1567 
1568 static int *bb_to_rpo;
1569 
1570 /* Helper for qsort, sorting after order above.  */
1571 
1572 static int
cmp_pbbs(const void * pa,const void * pb)1573 cmp_pbbs (const void *pa, const void *pb)
1574 {
1575   poly_bb_p bb1 = *((const poly_bb_p *)pa);
1576   poly_bb_p bb2 = *((const poly_bb_p *)pb);
1577   if (bb_to_rpo[bb1->black_box->bb->index]
1578       < bb_to_rpo[bb2->black_box->bb->index])
1579     return -1;
1580   else if (bb_to_rpo[bb1->black_box->bb->index]
1581 	   > bb_to_rpo[bb2->black_box->bb->index])
1582     return 1;
1583   else
1584     return 0;
1585 }
1586 
1587 /* Find Static Control Parts (SCoP) in the current function and pushes
1588    them to SCOPS.  */
1589 
1590 void
build_scops(vec<scop_p> * scops)1591 build_scops (vec<scop_p> *scops)
1592 {
1593   if (dump_file)
1594     dp.set_dump_file (dump_file);
1595 
1596   scop_detection sb;
1597   sb.build_scop_depth (current_loops->tree_root);
1598 
1599   /* Now create scops from the lightweight SESEs.  */
1600   vec<sese_l> scops_l = sb.get_scops ();
1601 
1602   /* Domwalk needs a bb to RPO mapping.  Compute it once here.  */
1603   int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1604   int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true);
1605   bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
1606   for (int i = 0; i < postorder_num; ++i)
1607     bb_to_rpo[postorder[i]] = i;
1608   free (postorder);
1609 
1610   int i;
1611   sese_l *s;
1612   FOR_EACH_VEC_ELT (scops_l, i, s)
1613     {
1614       scop_p scop = new_scop (s->entry, s->exit);
1615 
1616       /* Record all basic blocks and their conditions in REGION.  */
1617       gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo).walk (s->entry->dest);
1618 
1619       /* Sort pbbs after execution order for initial schedule generation.  */
1620       scop->pbbs.qsort (cmp_pbbs);
1621 
1622       if (! build_alias_set (scop))
1623 	{
1624 	  DEBUG_PRINT (dp << "[scop-detection-fail] cannot handle dependences\n");
1625 	  free_scop (scop);
1626 	  continue;
1627 	}
1628 
1629       /* Do not optimize a scop containing only PBBs that do not belong
1630 	 to any loops.  */
1631       if (sb.nb_pbbs_in_loops (scop) == 0)
1632 	{
1633 	  DEBUG_PRINT (dp << "[scop-detection-fail] no data references.\n");
1634 	  free_scop (scop);
1635 	  continue;
1636 	}
1637 
1638       unsigned max_arrays = param_graphite_max_arrays_per_scop;
1639       if (max_arrays > 0
1640 	  && scop->drs.length () >= max_arrays)
1641 	{
1642 	  DEBUG_PRINT (dp << "[scop-detection-fail] too many data references: "
1643 		       << scop->drs.length ()
1644 		       << " is larger than --param graphite-max-arrays-per-scop="
1645 		       << max_arrays << ".\n");
1646 	  free_scop (scop);
1647 	  continue;
1648 	}
1649 
1650       find_scop_parameters (scop);
1651       graphite_dim_t max_dim = param_graphite_max_nb_scop_params;
1652       if (max_dim > 0
1653 	  && scop_nb_params (scop) > max_dim)
1654 	{
1655 	  DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: "
1656 			  << scop_nb_params (scop)
1657 			  << " larger than --param graphite-max-nb-scop-params="
1658 			  << max_dim << ".\n");
1659 	  free_scop (scop);
1660 	  continue;
1661 	}
1662 
1663       scops->safe_push (scop);
1664     }
1665 
1666   free (bb_to_rpo);
1667   bb_to_rpo = NULL;
1668   DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0););
1669 }
1670 
1671 #endif /* HAVE_isl */
1672