Mercurial > hg > CbC > CbC_gcc
annotate gcc/graphite.c @ 130:e108057fa461
merge
author | mir3636 |
---|---|
date | Thu, 25 Oct 2018 08:08:40 +0900 |
parents | 04ced10e8804 |
children | 84e7813d76e9 |
rev | line source |
---|---|
0 | 1 /* Gimple Represented as Polyhedra. |
111 | 2 Copyright (C) 2006-2017 Free Software Foundation, Inc. |
0 | 3 Contributed by Sebastian Pop <sebastian.pop@inria.fr>. |
4 | |
5 This file is part of GCC. | |
6 | |
7 GCC is free software; you can redistribute it and/or modify | |
8 it under the terms of the GNU General Public License as published by | |
9 the Free Software Foundation; either version 3, or (at your option) | |
10 any later version. | |
11 | |
12 GCC is distributed in the hope that it will be useful, | |
13 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 GNU General Public License for more details. | |
16 | |
17 You should have received a copy of the GNU General Public License | |
18 along with GCC; see the file COPYING3. If not see | |
19 <http://www.gnu.org/licenses/>. */ | |
20 | |
21 /* This pass converts GIMPLE to GRAPHITE, performs some loop | |
22 transformations and then converts the resulting representation back | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
23 to GIMPLE. |
0 | 24 |
25 An early description of this pass can be found in the GCC Summit'06 | |
26 paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC". | |
27 The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to | |
111 | 28 the related work. */ |
0 | 29 |
111 | 30 #define USES_ISL |
0 | 31 |
32 #include "config.h" | |
33 #include "system.h" | |
34 #include "coretypes.h" | |
111 | 35 #include "backend.h" |
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
|
36 #include "diagnostic-core.h" |
0 | 37 #include "cfgloop.h" |
111 | 38 #include "tree-pass.h" |
39 #include "params.h" | |
40 #include "pretty-print.h" | |
41 | |
42 #ifdef HAVE_isl | |
43 #include "cfghooks.h" | |
44 #include "tree.h" | |
45 #include "gimple.h" | |
46 #include "ssa.h" | |
47 #include "fold-const.h" | |
48 #include "gimple-iterator.h" | |
49 #include "tree-cfg.h" | |
50 #include "tree-ssa-loop.h" | |
0 | 51 #include "tree-data-ref.h" |
52 #include "tree-scalar-evolution.h" | |
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
|
53 #include "dbgcnt.h" |
111 | 54 #include "tree-parloops.h" |
55 #include "tree-cfgcleanup.h" | |
56 #include "tree-vectorizer.h" | |
57 #include "tree-ssa-loop-manip.h" | |
58 #include "tree-ssa.h" | |
59 #include "tree-into-ssa.h" | |
60 #include "graphite.h" | |
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
|
61 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
62 /* Print global statistics to FILE. */ |
0 | 63 |
64 static void | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
65 print_global_statistics (FILE* file) |
0 | 66 { |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
67 long n_bbs = 0; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
68 long n_loops = 0; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
69 long n_stmts = 0; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
70 long n_conditions = 0; |
111 | 71 profile_count n_p_bbs = profile_count::zero (); |
72 profile_count n_p_loops = profile_count::zero (); | |
73 profile_count n_p_stmts = profile_count::zero (); | |
74 profile_count n_p_conditions = profile_count::zero (); | |
0 | 75 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
76 basic_block bb; |
0 | 77 |
111 | 78 FOR_ALL_BB_FN (bb, cfun) |
0 | 79 { |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
80 gimple_stmt_iterator psi; |
0 | 81 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
82 n_bbs++; |
111 | 83 if (bb->count.initialized_p ()) |
84 n_p_bbs += bb->count; | |
0 | 85 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
86 /* Ignore artificial surrounding loop. */ |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
87 if (bb == bb->loop_father->header |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
88 && bb->index != 0) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
89 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
90 n_loops++; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
91 n_p_loops += bb->count; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
92 } |
0 | 93 |
111 | 94 if (EDGE_COUNT (bb->succs) > 1) |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
95 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
96 n_conditions++; |
111 | 97 if (bb->count.initialized_p ()) |
98 n_p_conditions += bb->count; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
99 } |
0 | 100 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
101 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) |
0 | 102 { |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
103 n_stmts++; |
111 | 104 if (bb->count.initialized_p ()) |
105 n_p_stmts += bb->count; | |
0 | 106 } |
107 } | |
108 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
109 fprintf (file, "\nGlobal statistics ("); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
110 fprintf (file, "BBS:%ld, ", n_bbs); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
111 fprintf (file, "LOOPS:%ld, ", n_loops); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
112 fprintf (file, "CONDITIONS:%ld, ", n_conditions); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
113 fprintf (file, "STMTS:%ld)\n", n_stmts); |
111 | 114 fprintf (file, "Global profiling statistics ("); |
115 fprintf (file, "BBS:"); | |
116 n_p_bbs.dump (file); | |
117 fprintf (file, ", LOOPS:"); | |
118 n_p_loops.dump (file); | |
119 fprintf (file, ", CONDITIONS:"); | |
120 n_p_conditions.dump (file); | |
121 fprintf (file, ", STMTS:"); | |
122 n_p_stmts.dump (file); | |
123 fprintf (file, ")\n\n"); | |
0 | 124 } |
125 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
126 /* Print statistics for SCOP to FILE. */ |
0 | 127 |
128 static void | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
129 print_graphite_scop_statistics (FILE* file, scop_p scop) |
0 | 130 { |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
131 long n_bbs = 0; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
132 long n_loops = 0; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
133 long n_stmts = 0; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
134 long n_conditions = 0; |
111 | 135 profile_count n_p_bbs = profile_count::zero (); |
136 profile_count n_p_loops = profile_count::zero (); | |
137 profile_count n_p_stmts = profile_count::zero (); | |
138 profile_count n_p_conditions = profile_count::zero (); | |
0 | 139 |
140 basic_block bb; | |
141 | |
111 | 142 FOR_ALL_BB_FN (bb, cfun) |
0 | 143 { |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
144 gimple_stmt_iterator psi; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
145 loop_p loop = bb->loop_father; |
0 | 146 |
111 | 147 if (!bb_in_sese_p (bb, scop->scop_info->region)) |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
148 continue; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
149 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
150 n_bbs++; |
111 | 151 if (bb->count.initialized_p ()) |
152 n_p_bbs += bb->count; | |
0 | 153 |
111 | 154 if (EDGE_COUNT (bb->succs) > 1) |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
155 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
156 n_conditions++; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
157 n_p_conditions += bb->count; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
158 } |
0 | 159 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
160 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
161 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
162 n_stmts++; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
163 n_p_stmts += bb->count; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
164 } |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
165 |
111 | 166 if (loop->header == bb && loop_in_sese_p (loop, scop->scop_info->region)) |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
167 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
168 n_loops++; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
169 n_p_loops += bb->count; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
170 } |
0 | 171 } |
172 | |
111 | 173 fprintf (file, "\nFunction Name: %s\n", current_function_name ()); |
174 | |
175 edge scop_begin = scop->scop_info->region.entry; | |
176 edge scop_end = scop->scop_info->region.exit; | |
177 | |
178 fprintf (file, "\nSCoP (entry_edge (bb_%d, bb_%d), ", | |
179 scop_begin->src->index, scop_begin->dest->index); | |
180 fprintf (file, "exit_edge (bb_%d, bb_%d))", | |
181 scop_end->src->index, scop_end->dest->index); | |
182 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
183 fprintf (file, "\nSCoP statistics ("); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
184 fprintf (file, "BBS:%ld, ", n_bbs); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
185 fprintf (file, "LOOPS:%ld, ", n_loops); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
186 fprintf (file, "CONDITIONS:%ld, ", n_conditions); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
187 fprintf (file, "STMTS:%ld)\n", n_stmts); |
111 | 188 fprintf (file, "SCoP profiling statistics ("); |
189 fprintf (file, "BBS:"); | |
190 n_p_bbs.dump (file); | |
191 fprintf (file, ", LOOPS:"); | |
192 n_p_loops.dump (file); | |
193 fprintf (file, ", CONDITIONS:"); | |
194 n_p_conditions.dump (file); | |
195 fprintf (file, ", STMTS:"); | |
196 n_p_stmts.dump (file); | |
197 fprintf (file, ")\n\n"); | |
0 | 198 } |
199 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
200 /* Print statistics for SCOPS to FILE. */ |
0 | 201 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
202 static void |
111 | 203 print_graphite_statistics (FILE* file, vec<scop_p> scops) |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
204 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
205 int i; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
206 scop_p scop; |
0 | 207 |
111 | 208 FOR_EACH_VEC_ELT (scops, i, scop) |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
209 print_graphite_scop_statistics (file, scop); |
0 | 210 } |
211 | |
111 | 212 /* Deletes all scops in SCOPS. */ |
213 | |
214 static void | |
215 free_scops (vec<scop_p> scops) | |
216 { | |
217 int i; | |
218 scop_p scop; | |
219 | |
220 FOR_EACH_VEC_ELT (scops, i, scop) | |
221 free_scop (scop); | |
222 | |
223 scops.release (); | |
224 } | |
0 | 225 |
111 | 226 /* Transforms LOOP to the canonical loop closed SSA form. */ |
227 | |
228 static void | |
229 canonicalize_loop_closed_ssa (loop_p loop) | |
0 | 230 { |
111 | 231 edge e = single_exit (loop); |
232 basic_block bb; | |
233 gphi_iterator psi; | |
234 | |
235 if (!e || (e->flags & EDGE_COMPLEX)) | |
236 return; | |
237 | |
238 bb = e->dest; | |
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
|
239 |
111 | 240 /* Make the loop-close PHI node BB contain only PHIs and have a |
241 single predecessor. */ | |
242 if (single_pred_p (bb)) | |
243 { | |
244 e = split_block_after_labels (bb); | |
245 bb = e->src; | |
246 } | |
247 else | |
0 | 248 { |
111 | 249 basic_block close = split_edge (e); |
250 e = single_succ_edge (close); | |
251 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) | |
252 { | |
253 gphi *phi = psi.phi (); | |
254 use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e); | |
255 tree arg = USE_FROM_PTR (use_p); | |
0 | 256 |
111 | 257 /* Only add close phi nodes for SSA_NAMEs defined in LOOP. */ |
258 if (TREE_CODE (arg) != SSA_NAME | |
259 || SSA_NAME_IS_DEFAULT_DEF (arg) | |
260 || ! flow_bb_inside_loop_p (loop, | |
261 gimple_bb (SSA_NAME_DEF_STMT (arg)))) | |
262 continue; | |
263 | |
264 tree res = copy_ssa_name (arg); | |
265 gphi *close_phi = create_phi_node (res, close); | |
266 add_phi_arg (close_phi, arg, gimple_phi_arg_edge (close_phi, 0), | |
267 UNKNOWN_LOCATION); | |
268 SET_USE (use_p, res); | |
269 } | |
270 bb = close; | |
0 | 271 } |
272 | |
111 | 273 /* Eliminate duplicates. This relies on processing loops from |
274 innermost to outer. */ | |
275 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) | |
276 { | |
277 gphi_iterator gsi = psi; | |
278 gphi *phi = psi.phi (); | |
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
|
279 |
111 | 280 /* At this point, PHI should be a close phi in normal form. */ |
281 gcc_assert (gimple_phi_num_args (phi) == 1); | |
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
|
282 |
111 | 283 /* Iterate over the next phis and remove duplicates. */ |
284 gsi_next (&gsi); | |
285 while (!gsi_end_p (gsi)) | |
286 if (gimple_phi_arg_def (phi, 0) == gimple_phi_arg_def (gsi.phi (), 0)) | |
287 { | |
288 replace_uses_by (gimple_phi_result (gsi.phi ()), | |
289 gimple_phi_result (phi)); | |
290 remove_phi_node (&gsi, true); | |
291 } | |
292 else | |
293 gsi_next (&gsi); | |
294 } | |
0 | 295 } |
296 | |
111 | 297 /* Converts the current loop closed SSA form to a canonical form |
298 expected by the Graphite code generation. | |
299 | |
300 The loop closed SSA form has the following invariant: a variable | |
301 defined in a loop that is used outside the loop appears only in the | |
302 phi nodes in the destination of the loop exit. These phi nodes are | |
303 called close phi nodes. | |
304 | |
305 The canonical loop closed SSA form contains the extra invariants: | |
306 | |
307 - when the loop contains only one exit, the close phi nodes contain | |
308 only one argument. That implies that the basic block that contains | |
309 the close phi nodes has only one predecessor, that is a basic block | |
310 in the loop. | |
311 | |
312 - the basic block containing the close phi nodes does not contain | |
313 other statements. | |
314 | |
315 - there exist only one phi node per definition in the loop. | |
316 */ | |
0 | 317 |
318 static void | |
111 | 319 canonicalize_loop_closed_ssa_form (void) |
0 | 320 { |
111 | 321 loop_p loop; |
322 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) | |
323 canonicalize_loop_closed_ssa (loop); | |
0 | 324 |
111 | 325 checking_verify_loop_closed_ssa (true); |
326 } | |
0 | 327 |
111 | 328 isl_ctx *the_isl_ctx; |
0 | 329 |
330 /* Perform a set of linear transforms on the loops of the current | |
331 function. */ | |
332 | |
333 void | |
334 graphite_transform_loops (void) | |
335 { | |
336 int i; | |
337 scop_p scop; | |
111 | 338 bool changed = false; |
339 vec<scop_p> scops = vNULL; | |
340 isl_ctx *ctx; | |
0 | 341 |
111 | 342 /* If a function is parallel it was most probably already run through graphite |
343 once. No need to run again. */ | |
344 if (parallelized_function_p (cfun->decl)) | |
0 | 345 return; |
346 | |
111 | 347 calculate_dominance_info (CDI_DOMINATORS); |
348 | |
349 ctx = isl_ctx_alloc (); | |
350 isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT); | |
351 the_isl_ctx = ctx; | |
352 | |
353 sort_sibling_loops (cfun); | |
354 canonicalize_loop_closed_ssa_form (); | |
355 | |
356 /* Print the loop structure. */ | |
357 if (dump_file && (dump_flags & TDF_DETAILS)) | |
358 { | |
359 print_loops (dump_file, 2); | |
360 print_loops (dump_file, 3); | |
361 } | |
362 | |
363 calculate_dominance_info (CDI_POST_DOMINATORS); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
364 build_scops (&scops); |
111 | 365 free_dominance_info (CDI_POST_DOMINATORS); |
0 | 366 |
367 if (dump_file && (dump_flags & TDF_DETAILS)) | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
368 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
369 print_graphite_statistics (dump_file, scops); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
370 print_global_statistics (dump_file); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
371 } |
0 | 372 |
111 | 373 FOR_EACH_VEC_ELT (scops, i, scop) |
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
|
374 if (dbg_cnt (graphite_scop)) |
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
|
375 { |
111 | 376 scop->isl_context = ctx; |
377 if (!build_poly_scop (scop)) | |
378 continue; | |
379 | |
380 if (!apply_poly_transforms (scop)) | |
381 continue; | |
0 | 382 |
111 | 383 changed = true; |
384 if (graphite_regenerate_ast_isl (scop)) | |
385 { | |
386 location_t loc = find_loop_location | |
387 (scops[i]->scop_info->region.entry->dest->loop_father); | |
388 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc, | |
389 "loop nest optimized\n"); | |
390 } | |
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
|
391 } |
0 | 392 |
111 | 393 if (changed) |
394 { | |
395 mark_virtual_operands_for_renaming (cfun); | |
396 update_ssa (TODO_update_ssa); | |
397 checking_verify_ssa (true, true); | |
398 rewrite_into_loop_closed_ssa (NULL, 0); | |
399 scev_reset (); | |
400 checking_verify_loop_structure (); | |
401 } | |
402 | |
403 if (dump_file && (dump_flags & TDF_DETAILS)) | |
404 { | |
405 loop_p loop; | |
406 int num_no_dependency = 0; | |
407 | |
408 FOR_EACH_LOOP (loop, 0) | |
409 if (loop->can_be_parallel) | |
410 num_no_dependency++; | |
411 | |
412 fprintf (dump_file, "%d loops carried no dependency.\n", | |
413 num_no_dependency); | |
414 } | |
415 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
416 free_scops (scops); |
111 | 417 the_isl_ctx = NULL; |
418 isl_ctx_free (ctx); | |
419 | |
420 if (changed) | |
421 { | |
422 cleanup_tree_cfg (); | |
423 profile_status_for_fn (cfun) = PROFILE_ABSENT; | |
424 release_recorded_exits (cfun); | |
425 tree_estimate_probability (false); | |
426 } | |
427 | |
0 | 428 } |
429 | |
111 | 430 #else /* If isl is not available: #ifndef HAVE_isl. */ |
0 | 431 |
111 | 432 static void |
0 | 433 graphite_transform_loops (void) |
434 { | |
111 | 435 sorry ("Graphite loop optimizations cannot be used (isl is not available)."); |
0 | 436 } |
437 | |
438 #endif | |
111 | 439 |
440 | |
441 static unsigned int | |
442 graphite_transforms (struct function *fun) | |
443 { | |
444 if (number_of_loops (fun) <= 1) | |
445 return 0; | |
446 | |
447 graphite_transform_loops (); | |
448 | |
449 return 0; | |
450 } | |
451 | |
452 static bool | |
453 gate_graphite_transforms (void) | |
454 { | |
455 /* Enable -fgraphite pass if any one of the graphite optimization flags | |
456 is turned on. */ | |
457 if (flag_graphite_identity | |
458 || flag_loop_parallelize_all | |
459 || flag_loop_nest_optimize) | |
460 flag_graphite = 1; | |
461 | |
462 return flag_graphite != 0; | |
463 } | |
464 | |
465 namespace { | |
466 | |
467 const pass_data pass_data_graphite = | |
468 { | |
469 GIMPLE_PASS, /* type */ | |
470 "graphite0", /* name */ | |
471 OPTGROUP_LOOP, /* optinfo_flags */ | |
472 TV_GRAPHITE, /* tv_id */ | |
473 ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
474 0, /* properties_provided */ | |
475 0, /* properties_destroyed */ | |
476 0, /* todo_flags_start */ | |
477 0, /* todo_flags_finish */ | |
478 }; | |
479 | |
480 class pass_graphite : public gimple_opt_pass | |
481 { | |
482 public: | |
483 pass_graphite (gcc::context *ctxt) | |
484 : gimple_opt_pass (pass_data_graphite, ctxt) | |
485 {} | |
486 | |
487 /* opt_pass methods: */ | |
488 virtual bool gate (function *) { return gate_graphite_transforms (); } | |
489 | |
490 }; // class pass_graphite | |
491 | |
492 } // anon namespace | |
493 | |
494 gimple_opt_pass * | |
495 make_pass_graphite (gcc::context *ctxt) | |
496 { | |
497 return new pass_graphite (ctxt); | |
498 } | |
499 | |
500 namespace { | |
501 | |
502 const pass_data pass_data_graphite_transforms = | |
503 { | |
504 GIMPLE_PASS, /* type */ | |
505 "graphite", /* name */ | |
506 OPTGROUP_LOOP, /* optinfo_flags */ | |
507 TV_GRAPHITE_TRANSFORMS, /* tv_id */ | |
508 ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
509 0, /* properties_provided */ | |
510 0, /* properties_destroyed */ | |
511 0, /* todo_flags_start */ | |
512 0, /* todo_flags_finish */ | |
513 }; | |
514 | |
515 class pass_graphite_transforms : public gimple_opt_pass | |
516 { | |
517 public: | |
518 pass_graphite_transforms (gcc::context *ctxt) | |
519 : gimple_opt_pass (pass_data_graphite_transforms, ctxt) | |
520 {} | |
521 | |
522 /* opt_pass methods: */ | |
523 virtual bool gate (function *) { return gate_graphite_transforms (); } | |
524 virtual unsigned int execute (function *fun) { return graphite_transforms (fun); } | |
525 | |
526 }; // class pass_graphite_transforms | |
527 | |
528 } // anon namespace | |
529 | |
530 gimple_opt_pass * | |
531 make_pass_graphite_transforms (gcc::context *ctxt) | |
532 { | |
533 return new pass_graphite_transforms (ctxt); | |
534 } | |
535 | |
536 |