Mercurial > hg > CbC > CbC_gcc
annotate gcc/graphite-scop-detection.c @ 158:494b0b89df80 default tip
...
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 25 May 2020 18:13:55 +0900 |
| parents | 1830386684a0 |
| children |
| rev | line source |
|---|---|
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 /* Detection of Static Control Parts (SCoP) for Graphite. |
| 145 | 2 Copyright (C) 2009-2020 Free Software Foundation, Inc. |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 Tobias Grosser <grosser@fim.uni-passau.de>. |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 This file is part of GCC. |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8 GCC is free software; you can redistribute it and/or modify |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9 it under the terms of the GNU General Public License as published by |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10 the Free Software Foundation; either version 3, or (at your option) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11 any later version. |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
12 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13 GCC is distributed in the hope that it will be useful, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14 but WITHOUT ANY WARRANTY; without even the implied warranty of |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
16 GNU General Public License for more details. |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
17 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
18 You should have received a copy of the GNU General Public License |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
19 along with GCC; see the file COPYING3. If not see |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
20 <http://www.gnu.org/licenses/>. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
21 |
| 111 | 22 #define USES_ISL |
| 23 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
24 #include "config.h" |
| 111 | 25 |
| 26 #ifdef HAVE_isl | |
| 27 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
28 #include "system.h" |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
29 #include "coretypes.h" |
| 111 | 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" | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
44 #include "cfgloop.h" |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
45 #include "tree-data-ref.h" |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
46 #include "tree-scalar-evolution.h" |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
47 #include "tree-pass.h" |
| 111 | 48 #include "tree-ssa-propagate.h" |
| 49 #include "gimple-pretty-print.h" | |
| 50 #include "cfganal.h" | |
| 51 #include "graphite.h" | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
52 |
| 111 | 53 class debug_printer |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
54 { |
| 111 | 55 private: |
| 56 FILE *dump_file; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
57 |
| 111 | 58 public: |
| 59 void | |
| 60 set_dump_file (FILE *f) | |
| 61 { | |
| 62 gcc_assert (f); | |
| 63 dump_file = f; | |
| 64 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
65 |
| 111 | 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; | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
79 |
| 111 | 80 #define DEBUG_PRINT(args) do \ |
| 81 { \ | |
| 82 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \ | |
| 131 | 83 } while (0) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
84 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
85 /* Pretty print to FILE all the SCoPs in DOT format and mark them with |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
86 different colors. If there are not enough colors, paint the |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
87 remaining SCoPs in gray. |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
88 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
89 Special nodes: |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
90 - "*" after the node number denotes the entry of a SCoP, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
91 - "#" after the node number denotes the exit of a SCoP, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
92 - "()" around the node number denotes the entry or the |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
93 exit nodes of the SCOP. These are not part of SCoP. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
94 |
| 111 | 95 DEBUG_FUNCTION void |
| 96 dot_all_sese (FILE *file, vec<sese_l>& scops) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
97 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
98 /* Disable debugging while printing graph. */ |
| 111 | 99 dump_flags_t tmp_dump_flags = dump_flags; |
| 100 dump_flags = TDF_NONE; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
101 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
102 fprintf (file, "digraph all {\n"); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
103 |
| 111 | 104 basic_block bb; |
| 105 FOR_ALL_BB_FN (bb, cfun) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
106 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
107 int part_of_scop = false; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
108 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
109 /* Use HTML for every bb label. So we are able to print bbs |
| 111 | 110 which are part of two different SCoPs, with two different |
| 111 background colors. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
112 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ", |
| 111 | 113 bb->index); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
114 fprintf (file, "CELLSPACING=\"0\">\n"); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
115 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
116 /* Select color for SCoP. */ |
| 111 | 117 sese_l *region; |
| 118 int i; | |
| 119 FOR_EACH_VEC_ELT (scops, i, region) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
120 { |
| 111 | 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)) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
124 { |
| 111 | 125 const char *color; |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
126 switch (i % 17) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
127 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
128 case 0: /* red */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
129 color = "#e41a1c"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
130 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
131 case 1: /* blue */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
132 color = "#377eb8"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
133 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
134 case 2: /* green */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
135 color = "#4daf4a"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
136 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
137 case 3: /* purple */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
138 color = "#984ea3"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
139 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
140 case 4: /* orange */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
141 color = "#ff7f00"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
142 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
143 case 5: /* yellow */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
144 color = "#ffff33"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
145 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
146 case 6: /* brown */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
147 color = "#a65628"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
148 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
149 case 7: /* rose */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
150 color = "#f781bf"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
151 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
152 case 8: |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
153 color = "#8dd3c7"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
154 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
155 case 9: |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
156 color = "#ffffb3"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
157 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
158 case 10: |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
159 color = "#bebada"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
160 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
161 case 11: |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
162 color = "#fb8072"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
163 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
164 case 12: |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
165 color = "#80b1d3"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
166 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
167 case 13: |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
168 color = "#fdb462"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
169 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
170 case 14: |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
171 color = "#b3de69"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
172 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
173 case 15: |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
174 color = "#fccde5"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
175 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
176 case 16: |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
177 color = "#bc80bd"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
178 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
179 default: /* gray */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
180 color = "#999999"; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
181 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
182 |
| 111 | 183 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", |
| 184 color); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
185 |
| 111 | 186 if (!sese_in_region) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
187 fprintf (file, " ("); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
188 |
| 111 | 189 if (bb == region->entry->dest && bb == region->exit->dest) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
190 fprintf (file, " %d*# ", bb->index); |
| 111 | 191 else if (bb == region->entry->dest) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
192 fprintf (file, " %d* ", bb->index); |
| 111 | 193 else if (bb == region->exit->dest) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
194 fprintf (file, " %d# ", bb->index); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
195 else |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
196 fprintf (file, " %d ", bb->index); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
197 |
| 111 | 198 fprintf (file, "{lp_%d}", bb->loop_father->num); |
| 199 | |
| 200 if (!sese_in_region) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
201 fprintf (file, ")"); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
202 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
203 fprintf (file, "</TD></TR>\n"); |
| 111 | 204 part_of_scop = true; |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
205 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
206 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
207 |
| 111 | 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"); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
215 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
216 |
| 111 | 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 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
224 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
225 fputs ("}\n\n", file); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
226 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
227 /* Enable debugging again. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
228 dump_flags = tmp_dump_flags; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
229 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
230 |
| 111 | 231 /* Display SCoP on stderr. */ |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
232 |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
233 DEBUG_FUNCTION void |
| 111 | 234 dot_sese (sese_l& scop) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
235 { |
| 111 | 236 vec<sese_l> scops; |
| 237 scops.create (1); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
238 |
| 111 | 239 if (scop) |
| 240 scops.safe_push (scop); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
241 |
| 111 | 242 dot_all_sese (stderr, scops); |
| 243 | |
| 244 scops.release (); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
245 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
246 |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
247 DEBUG_FUNCTION void |
| 111 | 248 dot_cfg () |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
249 { |
| 111 | 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 * | |
| 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); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
273 |
| 111 | 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. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
285 |
| 111 | 286 class scop_detection |
| 287 { | |
| 288 public: | |
| 289 scop_detection () : scops (vNULL) {} | |
| 290 | |
| 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> | |
| 302 get_scops () | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
303 { |
| 111 | 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 | |
| 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); | |
| 131 | 420 if (!scop_end || (scop_end->flags & (EDGE_COMPLEX|EDGE_FAKE))) |
| 111 | 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 | |
| 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 | |
| 131 | 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; | |
| 111 | 449 |
| 131 | 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; | |
| 111 | 462 |
| 131 | 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 } | |
| 111 | 469 |
| 131 | 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); | |
| 111 | 485 |
| 131 | 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)); | |
| 111 | 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. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
510 |
| 111 | 511 void |
| 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 | |
| 552 scop_detection::can_represent_loop (loop_p loop, sese_l scop) | |
| 553 { | |
| 554 tree niter; | |
| 555 struct tree_niter_desc niter_desc; | |
| 556 | |
| 145 | 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) | |
| 111 | 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 | |
| 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 | |
| 593 scop_detection::add_scop (sese_l s) | |
| 594 { | |
| 595 gcc_assert (s); | |
| 596 | |
| 131 | 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 | |
| 111 | 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 | |
| 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 | |
| 131 | 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) | |
| 111 | 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 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
717 |
| 111 | 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 145 | 899 case ADDR_EXPR: |
| 900 /* We cannot encode addresses for ISL. */ | |
| 901 return false; | |
| 902 | |
| 111 | 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; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
912 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
913 |
| 111 | 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 | |
| 921 scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop, | |
| 922 tree expr) | |
| 923 { | |
| 145 | 924 tree scev = cached_scalar_evolution_in_region (scop, loop, expr); |
| 111 | 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 | |
| 932 scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt) | |
| 933 { | |
| 131 | 934 edge nest = scop.entry; |
| 111 | 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 | |
| 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 | |
| 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: | |
| 131 | 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 | |
| 145 | 1061 (cached_scalar_evolution_in_region (scop, |
| 1062 bb->loop_father, op))) | |
| 131 | 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 } | |
| 111 | 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 | |
| 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 | |
| 1102 assign_parameter_index_in_region (tree name, sese_info_p region) | |
| 1103 { | |
| 1104 gcc_assert (TREE_CODE (name) == SSA_NAME | |
| 1105 && INTEGRAL_TYPE_P (TREE_TYPE (name)) | |
| 1106 && ! defined_in_sese_p (name, region->region)); | |
| 1107 int i; | |
| 1108 tree p; | |
| 1109 FOR_EACH_VEC_ELT (region->params, i, p) | |
| 1110 if (p == name) | |
| 1111 return; | |
| 1112 | |
| 1113 region->params.safe_push (name); | |
| 1114 } | |
| 1115 | |
| 1116 /* In the context of sese S, scan the expression E and translate it to | |
| 1117 a linear expression C. When parsing a symbolic multiplication, K | |
| 1118 represents the constant multiplier of an expression containing | |
| 1119 parameters. */ | |
| 1120 | |
| 1121 static void | |
| 1122 scan_tree_for_params (sese_info_p s, tree e) | |
| 1123 { | |
| 1124 if (e == chrec_dont_know) | |
| 1125 return; | |
| 1126 | |
| 1127 switch (TREE_CODE (e)) | |
| 1128 { | |
| 1129 case POLYNOMIAL_CHREC: | |
| 1130 scan_tree_for_params (s, CHREC_LEFT (e)); | |
| 1131 break; | |
| 1132 | |
| 1133 case MULT_EXPR: | |
| 1134 if (chrec_contains_symbols (TREE_OPERAND (e, 0))) | |
| 1135 scan_tree_for_params (s, TREE_OPERAND (e, 0)); | |
| 1136 else | |
| 1137 scan_tree_for_params (s, TREE_OPERAND (e, 1)); | |
| 1138 break; | |
| 1139 | |
| 1140 case PLUS_EXPR: | |
| 1141 case POINTER_PLUS_EXPR: | |
| 1142 case MINUS_EXPR: | |
| 1143 scan_tree_for_params (s, TREE_OPERAND (e, 0)); | |
| 1144 scan_tree_for_params (s, TREE_OPERAND (e, 1)); | |
| 1145 break; | |
| 1146 | |
| 1147 case NEGATE_EXPR: | |
| 1148 case BIT_NOT_EXPR: | |
| 1149 CASE_CONVERT: | |
| 1150 case NON_LVALUE_EXPR: | |
| 1151 scan_tree_for_params (s, TREE_OPERAND (e, 0)); | |
| 1152 break; | |
| 1153 | |
| 1154 case SSA_NAME: | |
| 1155 assign_parameter_index_in_region (e, s); | |
| 1156 break; | |
| 1157 | |
| 1158 case INTEGER_CST: | |
| 1159 case ADDR_EXPR: | |
| 1160 case REAL_CST: | |
| 1161 case COMPLEX_CST: | |
| 1162 case VECTOR_CST: | |
| 1163 break; | |
| 1164 | |
| 1165 default: | |
| 1166 gcc_unreachable (); | |
| 1167 break; | |
| 1168 } | |
| 1169 } | |
| 1170 | |
| 1171 /* Find parameters with respect to REGION in BB. We are looking in memory | |
| 1172 access functions, conditions and loop bounds. */ | |
| 1173 | |
| 1174 static void | |
| 1175 find_params_in_bb (sese_info_p region, gimple_poly_bb_p gbb) | |
| 1176 { | |
| 1177 /* Find parameters in the access functions of data references. */ | |
| 1178 int i; | |
| 1179 data_reference_p dr; | |
| 1180 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr) | |
| 1181 for (unsigned j = 0; j < DR_NUM_DIMENSIONS (dr); j++) | |
| 1182 scan_tree_for_params (region, DR_ACCESS_FN (dr, j)); | |
| 1183 | |
| 1184 /* Find parameters in conditional statements. */ | |
| 1185 gimple *stmt; | |
| 1186 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt) | |
| 1187 { | |
| 131 | 1188 loop_p loop = gimple_bb (stmt)->loop_father; |
| 145 | 1189 tree lhs = cached_scalar_evolution_in_region (region->region, loop, |
| 1190 gimple_cond_lhs (stmt)); | |
| 1191 tree rhs = cached_scalar_evolution_in_region (region->region, loop, | |
| 1192 gimple_cond_rhs (stmt)); | |
| 131 | 1193 gcc_assert (!chrec_contains_undetermined (lhs) |
| 1194 && !chrec_contains_undetermined (rhs)); | |
| 111 | 1195 |
| 1196 scan_tree_for_params (region, lhs); | |
| 1197 scan_tree_for_params (region, rhs); | |
| 1198 } | |
| 1199 } | |
| 1200 | |
| 1201 /* Record the parameters used in the SCOP BBs. A variable is a parameter | |
| 1202 in a scop if it does not vary during the execution of that scop. */ | |
| 1203 | |
| 1204 static void | |
| 1205 find_scop_parameters (scop_p scop) | |
| 1206 { | |
| 1207 unsigned i; | |
| 1208 sese_info_p region = scop->scop_info; | |
| 1209 | |
| 1210 /* Parameters used in loop bounds are processed during gather_bbs. */ | |
| 1211 | |
| 1212 /* Find the parameters used in data accesses. */ | |
| 1213 poly_bb_p pbb; | |
| 1214 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) | |
| 1215 find_params_in_bb (region, PBB_BLACK_BOX (pbb)); | |
| 1216 | |
| 1217 int nbp = sese_nb_params (region); | |
| 1218 scop_set_nb_params (scop, nbp); | |
| 1219 } | |
| 1220 | |
| 1221 static void | |
| 1222 add_write (vec<tree> *writes, tree def) | |
| 1223 { | |
| 1224 writes->safe_push (def); | |
| 1225 DEBUG_PRINT (dp << "Adding scalar write: "; | |
| 1226 print_generic_expr (dump_file, def); | |
| 1227 dp << "\nFrom stmt: "; | |
| 1228 print_gimple_stmt (dump_file, | |
| 1229 SSA_NAME_DEF_STMT (def), 0)); | |
| 1230 } | |
| 1231 | |
| 1232 static void | |
| 1233 add_read (vec<scalar_use> *reads, tree use, gimple *use_stmt) | |
| 1234 { | |
| 1235 DEBUG_PRINT (dp << "Adding scalar read: "; | |
| 1236 print_generic_expr (dump_file, use); | |
| 1237 dp << "\nFrom stmt: "; | |
| 1238 print_gimple_stmt (dump_file, use_stmt, 0)); | |
| 1239 reads->safe_push (std::make_pair (use_stmt, use)); | |
| 1240 } | |
| 1241 | |
| 1242 | |
| 1243 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */ | |
| 1244 | |
| 1245 static void | |
| 1246 build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb, | |
| 1247 vec<tree> *writes) | |
| 1248 { | |
| 1249 if (!is_gimple_reg (def)) | |
| 1250 return; | |
| 1251 | |
| 1252 bool scev_analyzable = scev_analyzable_p (def, scop->scop_info->region); | |
| 1253 | |
| 1254 gimple *use_stmt; | |
| 1255 imm_use_iterator imm_iter; | |
| 1256 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) | |
| 1257 /* Do not gather scalar variables that can be analyzed by SCEV as they can | |
| 1258 be generated out of the induction variables. */ | |
| 1259 if ((! scev_analyzable | |
| 1260 /* But gather SESE liveouts as we otherwise fail to rewrite their | |
| 1261 exit PHIs. */ | |
| 1262 || ! bb_in_sese_p (gimple_bb (use_stmt), scop->scop_info->region)) | |
| 1263 && (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt))) | |
| 1264 { | |
| 1265 add_write (writes, def); | |
| 1266 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break | |
| 1267 before all the uses have been visited. */ | |
| 1268 BREAK_FROM_IMM_USE_STMT (imm_iter); | |
| 1269 } | |
| 1270 } | |
| 1271 | |
| 1272 /* Record USE if it is defined in other bbs different than USE_STMT | |
| 1273 in the SCOP. */ | |
| 1274 | |
| 1275 static void | |
| 1276 build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt, | |
| 1277 vec<scalar_use> *reads) | |
| 1278 { | |
| 1279 if (!is_gimple_reg (use)) | |
| 1280 return; | |
| 1281 | |
| 1282 /* Do not gather scalar variables that can be analyzed by SCEV as they can be | |
| 1283 generated out of the induction variables. */ | |
| 1284 if (scev_analyzable_p (use, scop->scop_info->region)) | |
| 1285 return; | |
| 1286 | |
| 1287 gimple *def_stmt = SSA_NAME_DEF_STMT (use); | |
| 1288 if (gimple_bb (def_stmt) != gimple_bb (use_stmt)) | |
| 1289 add_read (reads, use, use_stmt); | |
| 1290 } | |
| 1291 | |
| 1292 /* Generates a polyhedral black box only if the bb contains interesting | |
| 1293 information. */ | |
| 1294 | |
| 1295 static gimple_poly_bb_p | |
| 1296 try_generate_gimple_bb (scop_p scop, basic_block bb) | |
| 1297 { | |
| 1298 vec<data_reference_p> drs = vNULL; | |
| 1299 vec<tree> writes = vNULL; | |
| 1300 vec<scalar_use> reads = vNULL; | |
| 1301 | |
| 1302 sese_l region = scop->scop_info->region; | |
| 1303 edge nest = region.entry; | |
| 1304 loop_p loop = bb->loop_father; | |
| 1305 if (!loop_in_sese_p (loop, region)) | |
| 1306 loop = NULL; | |
| 1307 | |
| 1308 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); | |
| 1309 gsi_next (&gsi)) | |
| 1310 { | |
| 1311 gimple *stmt = gsi_stmt (gsi); | |
| 1312 if (is_gimple_debug (stmt)) | |
| 1313 continue; | |
| 1314 | |
| 1315 graphite_find_data_references_in_stmt (nest, loop, stmt, &drs); | |
| 1316 | |
| 1317 tree def = gimple_get_lhs (stmt); | |
| 1318 if (def) | |
| 1319 build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), &writes); | |
| 1320 | |
| 1321 ssa_op_iter iter; | |
| 1322 tree use; | |
| 1323 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) | |
| 1324 build_cross_bb_scalars_use (scop, use, stmt, &reads); | |
| 1325 } | |
| 1326 | |
| 1327 /* Handle defs and uses in PHIs. Those need special treatment given | |
| 1328 that we have to present ISL with sth that looks like we've rewritten | |
| 1329 the IL out-of-SSA. */ | |
| 1330 for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi); | |
| 1331 gsi_next (&psi)) | |
| 1332 { | |
| 1333 gphi *phi = psi.phi (); | |
| 1334 tree res = gimple_phi_result (phi); | |
| 1335 if (virtual_operand_p (res) | |
| 1336 || scev_analyzable_p (res, scop->scop_info->region)) | |
| 1337 continue; | |
| 1338 /* To simulate out-of-SSA the block containing the PHI node has | |
| 1339 reads of the PHI destination. And to preserve SSA dependences | |
| 1340 we also write to it (the out-of-SSA decl and the SSA result | |
| 1341 are coalesced for dependence purposes which is good enough). */ | |
| 1342 add_read (&reads, res, phi); | |
| 1343 add_write (&writes, res); | |
| 1344 } | |
| 1345 basic_block bb_for_succs = bb; | |
| 1346 if (bb_for_succs == bb_for_succs->loop_father->latch | |
| 1347 && bb_in_sese_p (bb_for_succs, scop->scop_info->region) | |
| 1348 && sese_trivially_empty_bb_p (bb_for_succs)) | |
| 1349 bb_for_succs = NULL; | |
| 1350 while (bb_for_succs) | |
| 1351 { | |
| 1352 basic_block latch = NULL; | |
| 1353 edge_iterator ei; | |
| 1354 edge e; | |
| 1355 FOR_EACH_EDGE (e, ei, bb_for_succs->succs) | |
| 1356 { | |
| 1357 for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi); | |
| 1358 gsi_next (&psi)) | |
| 1359 { | |
| 1360 gphi *phi = psi.phi (); | |
| 1361 tree res = gimple_phi_result (phi); | |
| 1362 if (virtual_operand_p (res)) | |
| 1363 continue; | |
| 1364 /* To simulate out-of-SSA the predecessor of edges into PHI nodes | |
| 1365 has a copy from the PHI argument to the PHI destination. */ | |
| 1366 if (! scev_analyzable_p (res, scop->scop_info->region)) | |
| 1367 add_write (&writes, res); | |
| 1368 tree use = PHI_ARG_DEF_FROM_EDGE (phi, e); | |
| 1369 if (TREE_CODE (use) == SSA_NAME | |
| 1370 && ! SSA_NAME_IS_DEFAULT_DEF (use) | |
| 1371 && gimple_bb (SSA_NAME_DEF_STMT (use)) != bb_for_succs | |
| 1372 && ! scev_analyzable_p (use, scop->scop_info->region)) | |
| 1373 add_read (&reads, use, phi); | |
| 1374 } | |
| 1375 if (e->dest == bb_for_succs->loop_father->latch | |
| 1376 && bb_in_sese_p (e->dest, scop->scop_info->region) | |
| 1377 && sese_trivially_empty_bb_p (e->dest)) | |
| 1378 latch = e->dest; | |
| 1379 } | |
| 1380 /* Handle empty latch block PHIs here, otherwise we confuse ISL | |
| 1381 with extra conditional code where it then peels off the last | |
| 1382 iteration just because of that. It would be simplest if we | |
| 1383 just didn't force simple latches (thus remove the forwarder). */ | |
| 1384 bb_for_succs = latch; | |
| 1385 } | |
| 1386 | |
| 1387 /* For the region exit block add reads for all live-out vars. */ | |
| 1388 if (bb == scop->scop_info->region.exit->src) | |
| 1389 { | |
| 1390 sese_build_liveouts (scop->scop_info); | |
| 1391 unsigned i; | |
| 1392 bitmap_iterator bi; | |
| 1393 EXECUTE_IF_SET_IN_BITMAP (scop->scop_info->liveout, 0, i, bi) | |
| 1394 { | |
| 1395 tree use = ssa_name (i); | |
| 1396 add_read (&reads, use, NULL); | |
| 1397 } | |
| 1398 } | |
| 1399 | |
| 1400 if (drs.is_empty () && writes.is_empty () && reads.is_empty ()) | |
| 1401 return NULL; | |
| 1402 | |
| 1403 return new_gimple_poly_bb (bb, drs, reads, writes); | |
| 1404 } | |
| 1405 | |
| 1406 /* Compute alias-sets for all data references in DRS. */ | |
| 1407 | |
| 1408 static bool | |
| 1409 build_alias_set (scop_p scop) | |
| 1410 { | |
| 1411 int num_vertices = scop->drs.length (); | |
| 1412 struct graph *g = new_graph (num_vertices); | |
| 1413 dr_info *dr1, *dr2; | |
| 1414 int i, j; | |
| 1415 int *all_vertices; | |
| 1416 | |
| 145 | 1417 struct loop *nest |
| 1418 = find_common_loop (scop->scop_info->region.entry->dest->loop_father, | |
| 1419 scop->scop_info->region.exit->src->loop_father); | |
| 1420 | |
| 111 | 1421 FOR_EACH_VEC_ELT (scop->drs, i, dr1) |
| 1422 for (j = i+1; scop->drs.iterate (j, &dr2); j++) | |
| 145 | 1423 if (dr_may_alias_p (dr1->dr, dr2->dr, nest)) |
| 111 | 1424 { |
| 1425 /* Dependences in the same alias set need to be handled | |
| 1426 by just looking at DR_ACCESS_FNs. */ | |
| 1427 if (DR_NUM_DIMENSIONS (dr1->dr) == 0 | |
| 1428 || DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr) | |
| 1429 || ! operand_equal_p (DR_BASE_OBJECT (dr1->dr), | |
| 1430 DR_BASE_OBJECT (dr2->dr), | |
| 1431 OEP_ADDRESS_OF) | |
| 1432 || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)), | |
| 1433 TREE_TYPE (DR_BASE_OBJECT (dr2->dr)))) | |
| 1434 { | |
| 1435 free_graph (g); | |
| 1436 return false; | |
| 1437 } | |
| 1438 add_edge (g, i, j); | |
| 1439 add_edge (g, j, i); | |
| 1440 } | |
| 1441 | |
| 1442 all_vertices = XNEWVEC (int, num_vertices); | |
| 1443 for (i = 0; i < num_vertices; i++) | |
| 1444 all_vertices[i] = i; | |
| 1445 | |
| 1446 scop->max_alias_set | |
| 1447 = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1; | |
| 1448 free (all_vertices); | |
| 1449 | |
| 1450 for (i = 0; i < g->n_vertices; i++) | |
| 1451 scop->drs[i].alias_set = g->vertices[i].component + 1; | |
| 1452 | |
| 1453 free_graph (g); | |
| 1454 return true; | |
| 1455 } | |
| 1456 | |
| 1457 /* Gather BBs and conditions for a SCOP. */ | |
| 1458 class gather_bbs : public dom_walker | |
| 1459 { | |
| 1460 public: | |
| 1461 gather_bbs (cdi_direction, scop_p, int *); | |
| 1462 | |
| 1463 virtual edge before_dom_children (basic_block); | |
| 1464 virtual void after_dom_children (basic_block); | |
| 1465 | |
| 1466 private: | |
| 1467 auto_vec<gimple *, 3> conditions, cases; | |
| 1468 scop_p scop; | |
| 1469 }; | |
| 1470 } | |
| 1471 gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo) | |
| 131 | 1472 : dom_walker (direction, ALL_BLOCKS, bb_to_rpo), scop (scop) |
| 111 | 1473 { |
| 1474 } | |
| 1475 | |
| 1476 /* Call-back for dom_walk executed before visiting the dominated | |
| 1477 blocks. */ | |
| 1478 | |
| 1479 edge | |
| 1480 gather_bbs::before_dom_children (basic_block bb) | |
| 1481 { | |
| 1482 sese_info_p region = scop->scop_info; | |
| 1483 if (!bb_in_sese_p (bb, region->region)) | |
| 1484 return dom_walker::STOP; | |
| 1485 | |
| 1486 /* For loops fully contained in the region record parameters in the | |
| 1487 loop bounds. */ | |
| 1488 loop_p loop = bb->loop_father; | |
| 1489 if (loop->header == bb | |
| 1490 && loop_in_sese_p (loop, region->region)) | |
| 1491 { | |
| 1492 tree nb_iters = number_of_latch_executions (loop); | |
| 1493 if (chrec_contains_symbols (nb_iters)) | |
| 1494 { | |
| 145 | 1495 nb_iters = cached_scalar_evolution_in_region (region->region, |
| 1496 loop, nb_iters); | |
| 111 | 1497 scan_tree_for_params (region, nb_iters); |
| 1498 } | |
| 1499 } | |
| 1500 | |
| 131 | 1501 if (gcond *stmt = single_pred_cond_non_loop_exit (bb)) |
| 111 | 1502 { |
| 1503 edge e = single_pred_edge (bb); | |
| 131 | 1504 /* Make sure the condition is in the region and thus was verified |
| 1505 to be handled. */ | |
| 1506 if (e != region->region.entry) | |
| 1507 { | |
| 1508 conditions.safe_push (stmt); | |
| 1509 if (e->flags & EDGE_TRUE_VALUE) | |
| 1510 cases.safe_push (stmt); | |
| 1511 else | |
| 1512 cases.safe_push (NULL); | |
| 1513 } | |
| 111 | 1514 } |
| 1515 | |
| 1516 scop->scop_info->bbs.safe_push (bb); | |
| 1517 | |
| 1518 gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb); | |
| 1519 if (!gbb) | |
| 1520 return NULL; | |
| 1521 | |
| 1522 GBB_CONDITIONS (gbb) = conditions.copy (); | |
| 1523 GBB_CONDITION_CASES (gbb) = cases.copy (); | |
| 1524 | |
| 1525 poly_bb_p pbb = new_poly_bb (scop, gbb); | |
| 1526 scop->pbbs.safe_push (pbb); | |
| 1527 | |
| 1528 int i; | |
| 1529 data_reference_p dr; | |
| 1530 FOR_EACH_VEC_ELT (gbb->data_refs, i, dr) | |
| 1531 { | |
| 1532 DEBUG_PRINT (dp << "Adding memory "; | |
| 1533 if (dr->is_read) | |
| 1534 dp << "read: "; | |
| 1535 else | |
| 1536 dp << "write: "; | |
| 1537 print_generic_expr (dump_file, dr->ref); | |
| 1538 dp << "\nFrom stmt: "; | |
| 1539 print_gimple_stmt (dump_file, dr->stmt, 0)); | |
| 1540 | |
| 1541 scop->drs.safe_push (dr_info (dr, pbb)); | |
| 1542 } | |
| 1543 | |
| 1544 return NULL; | |
| 1545 } | |
| 1546 | |
| 1547 /* Call-back for dom_walk executed after visiting the dominated | |
| 1548 blocks. */ | |
| 1549 | |
| 1550 void | |
| 1551 gather_bbs::after_dom_children (basic_block bb) | |
| 1552 { | |
| 1553 if (!bb_in_sese_p (bb, scop->scop_info->region)) | |
| 1554 return; | |
| 1555 | |
| 1556 if (single_pred_cond_non_loop_exit (bb)) | |
| 1557 { | |
| 131 | 1558 edge e = single_pred_edge (bb); |
| 1559 if (e != scop->scop_info->region.entry) | |
| 1560 { | |
| 1561 conditions.pop (); | |
| 1562 cases.pop (); | |
| 1563 } | |
| 111 | 1564 } |
| 1565 } | |
| 1566 | |
| 1567 | |
| 1568 /* Compute sth like an execution order, dominator order with first executing | |
| 1569 edges that stay inside the current loop, delaying processing exit edges. */ | |
| 1570 | |
| 131 | 1571 static int *bb_to_rpo; |
| 111 | 1572 |
| 1573 /* Helper for qsort, sorting after order above. */ | |
| 1574 | |
| 1575 static int | |
| 1576 cmp_pbbs (const void *pa, const void *pb) | |
| 1577 { | |
| 1578 poly_bb_p bb1 = *((const poly_bb_p *)pa); | |
| 1579 poly_bb_p bb2 = *((const poly_bb_p *)pb); | |
| 131 | 1580 if (bb_to_rpo[bb1->black_box->bb->index] |
| 1581 < bb_to_rpo[bb2->black_box->bb->index]) | |
| 111 | 1582 return -1; |
| 131 | 1583 else if (bb_to_rpo[bb1->black_box->bb->index] |
| 1584 > bb_to_rpo[bb2->black_box->bb->index]) | |
| 111 | 1585 return 1; |
| 1586 else | |
| 1587 return 0; | |
| 1588 } | |
| 1589 | |
| 1590 /* Find Static Control Parts (SCoP) in the current function and pushes | |
| 1591 them to SCOPS. */ | |
| 1592 | |
| 1593 void | |
| 1594 build_scops (vec<scop_p> *scops) | |
| 1595 { | |
| 1596 if (dump_file) | |
| 1597 dp.set_dump_file (dump_file); | |
| 1598 | |
| 1599 scop_detection sb; | |
| 1600 sb.build_scop_depth (current_loops->tree_root); | |
| 1601 | |
| 1602 /* Now create scops from the lightweight SESEs. */ | |
| 1603 vec<sese_l> scops_l = sb.get_scops (); | |
| 1604 | |
| 1605 /* Domwalk needs a bb to RPO mapping. Compute it once here. */ | |
| 1606 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); | |
| 1607 int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true); | |
| 131 | 1608 bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun)); |
| 111 | 1609 for (int i = 0; i < postorder_num; ++i) |
| 1610 bb_to_rpo[postorder[i]] = i; | |
| 1611 free (postorder); | |
| 1612 | |
| 1613 int i; | |
| 1614 sese_l *s; | |
| 1615 FOR_EACH_VEC_ELT (scops_l, i, s) | |
| 1616 { | |
| 1617 scop_p scop = new_scop (s->entry, s->exit); | |
| 1618 | |
| 1619 /* Record all basic blocks and their conditions in REGION. */ | |
| 1620 gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo).walk (s->entry->dest); | |
| 1621 | |
| 131 | 1622 /* Sort pbbs after execution order for initial schedule generation. */ |
| 111 | 1623 scop->pbbs.qsort (cmp_pbbs); |
| 1624 | |
| 1625 if (! build_alias_set (scop)) | |
| 1626 { | |
| 1627 DEBUG_PRINT (dp << "[scop-detection-fail] cannot handle dependences\n"); | |
| 1628 free_scop (scop); | |
| 1629 continue; | |
| 1630 } | |
| 1631 | |
| 1632 /* Do not optimize a scop containing only PBBs that do not belong | |
| 1633 to any loops. */ | |
| 1634 if (sb.nb_pbbs_in_loops (scop) == 0) | |
| 1635 { | |
| 1636 DEBUG_PRINT (dp << "[scop-detection-fail] no data references.\n"); | |
| 1637 free_scop (scop); | |
| 1638 continue; | |
| 1639 } | |
| 1640 | |
| 145 | 1641 unsigned max_arrays = param_graphite_max_arrays_per_scop; |
| 111 | 1642 if (max_arrays > 0 |
| 1643 && scop->drs.length () >= max_arrays) | |
| 1644 { | |
| 1645 DEBUG_PRINT (dp << "[scop-detection-fail] too many data references: " | |
| 1646 << scop->drs.length () | |
| 1647 << " is larger than --param graphite-max-arrays-per-scop=" | |
| 1648 << max_arrays << ".\n"); | |
| 1649 free_scop (scop); | |
| 1650 continue; | |
| 1651 } | |
| 1652 | |
| 1653 find_scop_parameters (scop); | |
| 145 | 1654 graphite_dim_t max_dim = param_graphite_max_nb_scop_params; |
| 111 | 1655 if (max_dim > 0 |
| 1656 && scop_nb_params (scop) > max_dim) | |
| 1657 { | |
| 1658 DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: " | |
| 1659 << scop_nb_params (scop) | |
| 1660 << " larger than --param graphite-max-nb-scop-params=" | |
| 1661 << max_dim << ".\n"); | |
| 1662 free_scop (scop); | |
| 1663 continue; | |
| 1664 } | |
| 1665 | |
| 1666 scops->safe_push (scop); | |
| 1667 } | |
| 1668 | |
| 1669 free (bb_to_rpo); | |
| 131 | 1670 bb_to_rpo = NULL; |
| 111 | 1671 DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0);); |
| 1672 } | |
| 1673 | |
| 1674 #endif /* HAVE_isl */ |