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