Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-loop-unswitch.c @ 158:494b0b89df80 default tip
...
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 25 May 2020 18:13:55 +0900 |
parents | 1830386684a0 |
children |
rev | line source |
---|---|
0 | 1 /* Loop unswitching. |
145 | 2 Copyright (C) 2004-2020 Free Software Foundation, Inc. |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
3 |
0 | 4 This file is part of GCC. |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
5 |
0 | 6 GCC is free software; you can redistribute it and/or modify it |
7 under the terms of the GNU General Public License as published by the | |
8 Free Software Foundation; either version 3, or (at your option) any | |
9 later version. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
10 |
0 | 11 GCC is distributed in the hope that it will be useful, but WITHOUT |
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 for more details. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
15 |
0 | 16 You should have received a copy of the GNU General Public License |
17 along with GCC; see the file COPYING3. If not see | |
18 <http://www.gnu.org/licenses/>. */ | |
19 | |
20 #include "config.h" | |
21 #include "system.h" | |
22 #include "coretypes.h" | |
111 | 23 #include "backend.h" |
0 | 24 #include "tree.h" |
111 | 25 #include "gimple.h" |
26 #include "tree-pass.h" | |
27 #include "ssa.h" | |
28 #include "fold-const.h" | |
29 #include "gimplify.h" | |
30 #include "tree-cfg.h" | |
31 #include "tree-ssa.h" | |
32 #include "tree-ssa-loop-niter.h" | |
33 #include "tree-ssa-loop.h" | |
34 #include "tree-into-ssa.h" | |
0 | 35 #include "cfgloop.h" |
36 #include "tree-inline.h" | |
111 | 37 #include "gimple-iterator.h" |
38 #include "cfghooks.h" | |
39 #include "tree-ssa-loop-manip.h" | |
0 | 40 |
41 /* This file implements the loop unswitching, i.e. transformation of loops like | |
42 | |
43 while (A) | |
44 { | |
45 if (inv) | |
46 B; | |
47 | |
48 X; | |
49 | |
50 if (!inv) | |
51 C; | |
52 } | |
53 | |
54 where inv is the loop invariant, into | |
55 | |
56 if (inv) | |
57 { | |
58 while (A) | |
59 { | |
60 B; | |
61 X; | |
62 } | |
63 } | |
64 else | |
65 { | |
66 while (A) | |
67 { | |
68 X; | |
69 C; | |
70 } | |
71 } | |
72 | |
73 Inv is considered invariant iff the values it compares are both invariant; | |
74 tree-ssa-loop-im.c ensures that all the suitable conditions are in this | |
75 shape. */ | |
76 | |
145 | 77 static class loop *tree_unswitch_loop (class loop *, basic_block, tree); |
78 static bool tree_unswitch_single_loop (class loop *, int); | |
79 static tree tree_may_unswitch_on (basic_block, class loop *); | |
80 static bool tree_unswitch_outer_loop (class loop *); | |
81 static edge find_loop_guard (class loop *); | |
82 static bool empty_bb_without_guard_p (class loop *, basic_block); | |
83 static bool used_outside_loop_p (class loop *, tree); | |
84 static void hoist_guard (class loop *, edge); | |
85 static bool check_exit_phi (class loop *); | |
86 static tree get_vop_from_header (class loop *); | |
0 | 87 |
88 /* Main entry point. Perform loop unswitching on all suitable loops. */ | |
89 | |
90 unsigned int | |
91 tree_ssa_unswitch_loops (void) | |
92 { | |
145 | 93 class loop *loop; |
0 | 94 bool changed = false; |
95 | |
111 | 96 /* Go through all loops starting from innermost. */ |
97 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) | |
0 | 98 { |
111 | 99 if (!loop->inner) |
100 /* Unswitch innermost loop. */ | |
101 changed |= tree_unswitch_single_loop (loop, 0); | |
102 else | |
103 changed |= tree_unswitch_outer_loop (loop); | |
0 | 104 } |
105 | |
106 if (changed) | |
107 return TODO_cleanup_cfg; | |
108 return 0; | |
109 } | |
110 | |
111 | 111 /* Return TRUE if an SSA_NAME maybe undefined and is therefore |
112 unsuitable for unswitching. STMT is the statement we are | |
113 considering for unswitching and LOOP is the loop it appears in. */ | |
114 | |
115 static bool | |
145 | 116 is_maybe_undefined (const tree name, gimple *stmt, class loop *loop) |
111 | 117 { |
118 /* The loop header is the only block we can trivially determine that | |
119 will always be executed. If the comparison is in the loop | |
120 header, we know it's OK to unswitch on it. */ | |
121 if (gimple_bb (stmt) == loop->header) | |
122 return false; | |
123 | |
124 auto_bitmap visited_ssa; | |
125 auto_vec<tree> worklist; | |
126 worklist.safe_push (name); | |
127 bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name)); | |
128 while (!worklist.is_empty ()) | |
129 { | |
130 tree t = worklist.pop (); | |
131 | |
132 /* If it's obviously undefined, avoid further computations. */ | |
133 if (ssa_undefined_value_p (t, true)) | |
134 return true; | |
135 | |
136 if (ssa_defined_default_def_p (t)) | |
137 continue; | |
138 | |
139 gimple *def = SSA_NAME_DEF_STMT (t); | |
140 | |
141 /* Check that all the PHI args are fully defined. */ | |
142 if (gphi *phi = dyn_cast <gphi *> (def)) | |
143 { | |
144 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i) | |
145 { | |
146 tree t = gimple_phi_arg_def (phi, i); | |
147 /* If an SSA has already been seen, it may be a loop, | |
148 but we can continue and ignore this use. Otherwise, | |
149 add the SSA_NAME to the queue and visit it later. */ | |
150 if (TREE_CODE (t) == SSA_NAME | |
151 && bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t))) | |
152 worklist.safe_push (t); | |
153 } | |
154 continue; | |
155 } | |
156 | |
157 /* Uses in stmts always executed when the region header executes | |
158 are fine. */ | |
159 if (dominated_by_p (CDI_DOMINATORS, loop->header, gimple_bb (def))) | |
160 continue; | |
161 | |
162 /* Handle calls and memory loads conservatively. */ | |
163 if (!is_gimple_assign (def) | |
164 || (gimple_assign_single_p (def) | |
165 && gimple_vuse (def))) | |
166 return true; | |
167 | |
168 /* Check that any SSA names used to define NAME are also fully | |
169 defined. */ | |
170 use_operand_p use_p; | |
171 ssa_op_iter iter; | |
172 FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE) | |
173 { | |
174 tree t = USE_FROM_PTR (use_p); | |
175 /* If an SSA has already been seen, it may be a loop, | |
176 but we can continue and ignore this use. Otherwise, | |
177 add the SSA_NAME to the queue and visit it later. */ | |
178 if (bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t))) | |
179 worklist.safe_push (t); | |
180 } | |
181 } | |
182 return false; | |
183 } | |
184 | |
0 | 185 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its |
186 basic blocks (for what it means see comments below). */ | |
187 | |
188 static tree | |
145 | 189 tree_may_unswitch_on (basic_block bb, class loop *loop) |
0 | 190 { |
111 | 191 gimple *last, *def; |
192 gcond *stmt; | |
0 | 193 tree cond, use; |
194 basic_block def_bb; | |
195 ssa_op_iter iter; | |
196 | |
197 /* BB must end in a simple conditional jump. */ | |
111 | 198 last = last_stmt (bb); |
199 if (!last || gimple_code (last) != GIMPLE_COND) | |
0 | 200 return NULL_TREE; |
111 | 201 stmt = as_a <gcond *> (last); |
0 | 202 |
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
|
203 /* To keep the things simple, we do not directly remove the conditions, |
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
|
204 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite |
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
|
205 loop where we would unswitch again on such a condition. */ |
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
|
206 if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt)) |
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
|
207 return NULL_TREE; |
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
|
208 |
0 | 209 /* Condition must be invariant. */ |
210 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) | |
211 { | |
212 def = SSA_NAME_DEF_STMT (use); | |
213 def_bb = gimple_bb (def); | |
214 if (def_bb | |
215 && flow_bb_inside_loop_p (loop, def_bb)) | |
216 return NULL_TREE; | |
111 | 217 /* Unswitching on undefined values would introduce undefined |
218 behavior that the original program might never exercise. */ | |
219 if (is_maybe_undefined (use, stmt, loop)) | |
220 return NULL_TREE; | |
0 | 221 } |
222 | |
223 cond = build2 (gimple_cond_code (stmt), boolean_type_node, | |
224 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); | |
225 | |
226 return cond; | |
227 } | |
228 | |
229 /* Simplifies COND using checks in front of the entry of the LOOP. Just very | |
230 simplish (sufficient to prevent us from duplicating loop in unswitching | |
231 unnecessarily). */ | |
232 | |
233 static tree | |
145 | 234 simplify_using_entry_checks (class loop *loop, tree cond) |
0 | 235 { |
236 edge e = loop_preheader_edge (loop); | |
111 | 237 gimple *stmt; |
0 | 238 |
239 while (1) | |
240 { | |
241 stmt = last_stmt (e->src); | |
242 if (stmt | |
243 && gimple_code (stmt) == GIMPLE_COND | |
244 && gimple_cond_code (stmt) == TREE_CODE (cond) | |
245 && operand_equal_p (gimple_cond_lhs (stmt), | |
246 TREE_OPERAND (cond, 0), 0) | |
247 && operand_equal_p (gimple_cond_rhs (stmt), | |
248 TREE_OPERAND (cond, 1), 0)) | |
249 return (e->flags & EDGE_TRUE_VALUE | |
250 ? boolean_true_node | |
251 : boolean_false_node); | |
252 | |
253 if (!single_pred_p (e->src)) | |
254 return cond; | |
255 | |
256 e = single_pred_edge (e->src); | |
111 | 257 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) |
0 | 258 return cond; |
259 } | |
260 } | |
261 | |
262 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow | |
263 it to grow too much, it is too easy to create example on that the code would | |
264 grow exponentially. */ | |
265 | |
266 static bool | |
145 | 267 tree_unswitch_single_loop (class loop *loop, int num) |
0 | 268 { |
269 basic_block *bbs; | |
145 | 270 class loop *nloop; |
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
|
271 unsigned i, found; |
0 | 272 tree cond = NULL_TREE; |
111 | 273 gimple *stmt; |
0 | 274 bool changed = false; |
111 | 275 HOST_WIDE_INT iterations; |
276 | |
277 /* Perform initial tests if unswitch is eligible. */ | |
278 if (num == 0) | |
279 { | |
280 /* Do not unswitch in cold regions. */ | |
281 if (optimize_loop_for_size_p (loop)) | |
282 { | |
283 if (dump_file && (dump_flags & TDF_DETAILS)) | |
284 fprintf (dump_file, ";; Not unswitching cold loops\n"); | |
285 return false; | |
286 } | |
287 | |
288 /* The loop should not be too large, to limit code growth. */ | |
289 if (tree_num_loop_insns (loop, &eni_size_weights) | |
145 | 290 > (unsigned) param_max_unswitch_insns) |
111 | 291 { |
292 if (dump_file && (dump_flags & TDF_DETAILS)) | |
293 fprintf (dump_file, ";; Not unswitching, loop too big\n"); | |
294 return false; | |
295 } | |
296 | |
297 /* If the loop is not expected to iterate, there is no need | |
298 for unswitching. */ | |
299 iterations = estimated_loop_iterations_int (loop); | |
300 if (iterations < 0) | |
301 iterations = likely_max_loop_iterations_int (loop); | |
302 if (iterations >= 0 && iterations <= 1) | |
303 { | |
304 if (dump_file && (dump_flags & TDF_DETAILS)) | |
305 fprintf (dump_file, ";; Not unswitching, loop is not expected" | |
306 " to iterate\n"); | |
307 return false; | |
308 } | |
309 } | |
0 | 310 |
311 i = 0; | |
312 bbs = get_loop_body (loop); | |
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
|
313 found = loop->num_nodes; |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
314 |
0 | 315 while (1) |
316 { | |
317 /* Find a bb to unswitch on. */ | |
318 for (; i < loop->num_nodes; i++) | |
319 if ((cond = tree_may_unswitch_on (bbs[i], loop))) | |
320 break; | |
321 | |
322 if (i == loop->num_nodes) | |
323 { | |
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
|
324 if (dump_file |
145 | 325 && num > param_max_unswitch_level |
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
|
326 && (dump_flags & TDF_DETAILS)) |
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
|
327 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n"); |
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
|
328 |
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
|
329 if (found == loop->num_nodes) |
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
|
330 { |
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
|
331 free (bbs); |
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
|
332 return changed; |
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
|
333 } |
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
|
334 break; |
0 | 335 } |
336 | |
337 cond = simplify_using_entry_checks (loop, cond); | |
338 stmt = last_stmt (bbs[i]); | |
339 if (integer_nonzerop (cond)) | |
340 { | |
341 /* Remove false path. */ | |
111 | 342 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt), |
343 boolean_true_node); | |
0 | 344 changed = true; |
345 } | |
346 else if (integer_zerop (cond)) | |
347 { | |
348 /* Remove true path. */ | |
111 | 349 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt), |
350 boolean_false_node); | |
0 | 351 changed = true; |
352 } | |
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
|
353 /* Do not unswitch too much. */ |
145 | 354 else if (num > param_max_unswitch_level) |
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
|
355 { |
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
|
356 i++; |
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
|
357 continue; |
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
|
358 } |
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
|
359 /* In nested tree_unswitch_single_loop first optimize all conditions |
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
|
360 using entry checks, then discover still reachable blocks in the |
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
|
361 loop and find the condition only among those still reachable bbs. */ |
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
|
362 else if (num != 0) |
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
|
363 { |
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
|
364 if (found == loop->num_nodes) |
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
|
365 found = i; |
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
|
366 i++; |
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
|
367 continue; |
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
|
368 } |
0 | 369 else |
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
|
370 { |
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
|
371 found = i; |
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
|
372 break; |
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
|
373 } |
0 | 374 |
375 update_stmt (stmt); | |
376 i++; | |
377 } | |
378 | |
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
|
379 if (num != 0) |
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
|
380 { |
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
|
381 basic_block *tos, *worklist; |
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
|
382 |
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
|
383 /* When called recursively, first do a quick discovery |
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
|
384 of reachable bbs after the above changes and only |
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
|
385 consider conditions in still reachable bbs. */ |
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
|
386 tos = worklist = XNEWVEC (basic_block, loop->num_nodes); |
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
|
387 |
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
|
388 for (i = 0; i < loop->num_nodes; i++) |
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
|
389 bbs[i]->flags &= ~BB_REACHABLE; |
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
|
390 |
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 /* Start with marking header. */ |
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
|
392 *tos++ = bbs[0]; |
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
|
393 bbs[0]->flags |= BB_REACHABLE; |
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
|
394 |
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
|
395 /* Iterate: find everything reachable from what we've already seen |
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
|
396 within the same innermost loop. Don't look through false edges |
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
|
397 if condition is always true or true edges if condition is |
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
|
398 always false. */ |
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
|
399 while (tos != worklist) |
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
|
400 { |
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
|
401 basic_block b = *--tos; |
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
|
402 edge e; |
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
|
403 edge_iterator ei; |
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
|
404 int flags = 0; |
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
|
405 |
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
|
406 if (EDGE_COUNT (b->succs) == 2) |
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
|
407 { |
111 | 408 gimple *stmt = last_stmt (b); |
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
|
409 if (stmt |
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
|
410 && gimple_code (stmt) == GIMPLE_COND) |
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
|
411 { |
111 | 412 gcond *cond_stmt = as_a <gcond *> (stmt); |
413 if (gimple_cond_true_p (cond_stmt)) | |
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
|
414 flags = EDGE_FALSE_VALUE; |
111 | 415 else if (gimple_cond_false_p (cond_stmt)) |
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
|
416 flags = EDGE_TRUE_VALUE; |
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
|
417 } |
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
|
418 } |
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
|
419 |
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
|
420 FOR_EACH_EDGE (e, ei, b->succs) |
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
|
421 { |
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
|
422 basic_block dest = e->dest; |
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
|
423 |
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
|
424 if (dest->loop_father == loop |
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
|
425 && !(dest->flags & BB_REACHABLE) |
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
|
426 && !(e->flags & flags)) |
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
|
427 { |
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
|
428 *tos++ = dest; |
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
|
429 dest->flags |= BB_REACHABLE; |
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
|
430 } |
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
|
431 } |
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
|
432 } |
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
|
433 |
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
|
434 free (worklist); |
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
|
435 |
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
|
436 /* Find a bb to unswitch on. */ |
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
|
437 for (; found < loop->num_nodes; found++) |
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
|
438 if ((bbs[found]->flags & BB_REACHABLE) |
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
|
439 && (cond = tree_may_unswitch_on (bbs[found], loop))) |
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
|
440 break; |
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
|
441 |
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
|
442 if (found == loop->num_nodes) |
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
|
443 { |
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
|
444 free (bbs); |
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
|
445 return changed; |
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
|
446 } |
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
|
447 } |
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
|
448 |
0 | 449 if (dump_file && (dump_flags & TDF_DETAILS)) |
450 fprintf (dump_file, ";; Unswitching loop\n"); | |
451 | |
452 initialize_original_copy_tables (); | |
453 /* Unswitch the loop on this condition. */ | |
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
|
454 nloop = tree_unswitch_loop (loop, bbs[found], cond); |
0 | 455 if (!nloop) |
456 { | |
457 free_original_copy_tables (); | |
458 free (bbs); | |
459 return changed; | |
460 } | |
461 | |
462 /* Update the SSA form after unswitching. */ | |
463 update_ssa (TODO_update_ssa); | |
464 free_original_copy_tables (); | |
465 | |
466 /* Invoke itself on modified loops. */ | |
467 tree_unswitch_single_loop (nloop, num + 1); | |
468 tree_unswitch_single_loop (loop, num + 1); | |
469 free (bbs); | |
470 return true; | |
471 } | |
472 | |
473 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support | |
474 unswitching of innermost loops. COND is the condition determining which | |
475 loop is entered -- the new loop is entered if COND is true. Returns NULL | |
476 if impossible, new loop otherwise. */ | |
477 | |
145 | 478 static class loop * |
479 tree_unswitch_loop (class loop *loop, | |
0 | 480 basic_block unswitch_on, tree cond) |
481 { | |
111 | 482 profile_probability prob_true; |
0 | 483 edge edge_true, edge_false; |
484 | |
485 /* Some sanity checking. */ | |
486 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on)); | |
487 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2); | |
488 gcc_assert (loop->inner == NULL); | |
489 | |
490 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false); | |
491 prob_true = edge_true->probability; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
492 return loop_version (loop, unshare_expr (cond), |
111 | 493 NULL, prob_true, |
494 prob_true.invert (), | |
495 prob_true, prob_true.invert (), | |
496 false); | |
497 } | |
498 | |
499 /* Unswitch outer loops by hoisting invariant guard on | |
500 inner loop without code duplication. */ | |
501 static bool | |
145 | 502 tree_unswitch_outer_loop (class loop *loop) |
111 | 503 { |
504 edge exit, guard; | |
505 HOST_WIDE_INT iterations; | |
506 | |
507 gcc_assert (loop->inner); | |
508 if (loop->inner->next) | |
509 return false; | |
510 /* Accept loops with single exit only which is not from inner loop. */ | |
511 exit = single_exit (loop); | |
512 if (!exit || exit->src->loop_father != loop) | |
513 return false; | |
514 /* Check that phi argument of exit edge is not defined inside loop. */ | |
515 if (!check_exit_phi (loop)) | |
516 return false; | |
517 /* If the loop is not expected to iterate, there is no need | |
518 for unswitching. */ | |
519 iterations = estimated_loop_iterations_int (loop); | |
520 if (iterations < 0) | |
521 iterations = likely_max_loop_iterations_int (loop); | |
522 if (iterations >= 0 && iterations <= 1) | |
523 { | |
524 if (dump_file && (dump_flags & TDF_DETAILS)) | |
525 fprintf (dump_file, ";; Not unswitching, loop is not expected" | |
526 " to iterate\n"); | |
527 return false; | |
528 } | |
529 | |
530 bool changed = false; | |
531 while ((guard = find_loop_guard (loop))) | |
532 { | |
533 if (! changed) | |
534 rewrite_virtuals_into_loop_closed_ssa (loop); | |
535 hoist_guard (loop, guard); | |
536 changed = true; | |
537 } | |
538 return changed; | |
539 } | |
540 | |
541 /* Checks if the body of the LOOP is within an invariant guard. If this | |
542 is the case, returns the edge that jumps over the real body of the loop, | |
543 otherwise returns NULL. */ | |
544 | |
545 static edge | |
145 | 546 find_loop_guard (class loop *loop) |
111 | 547 { |
548 basic_block header = loop->header; | |
549 edge guard_edge, te, fe; | |
550 basic_block *body = NULL; | |
551 unsigned i; | |
552 tree use; | |
553 ssa_op_iter iter; | |
554 | |
555 /* We check for the following situation: | |
556 | |
557 while (1) | |
558 { | |
559 [header]] | |
560 loop_phi_nodes; | |
561 something1; | |
562 if (cond1) | |
563 body; | |
564 nvar = phi(orig, bvar) ... for all variables changed in body; | |
565 [guard_end] | |
566 something2; | |
567 if (cond2) | |
568 break; | |
569 something3; | |
570 } | |
571 | |
572 where: | |
573 | |
574 1) cond1 is loop invariant | |
575 2) If cond1 is false, then the loop is essentially empty; i.e., | |
576 a) nothing in something1, something2 and something3 has side | |
577 effects | |
578 b) anything defined in something1, something2 and something3 | |
579 is not used outside of the loop. */ | |
580 | |
581 gcond *cond; | |
582 do | |
583 { | |
584 basic_block next = NULL; | |
585 if (single_succ_p (header)) | |
586 next = single_succ (header); | |
587 else | |
588 { | |
145 | 589 cond = safe_dyn_cast <gcond *> (last_stmt (header)); |
111 | 590 if (! cond) |
591 return NULL; | |
592 extract_true_false_edges_from_block (header, &te, &fe); | |
593 /* Make sure to skip earlier hoisted guards that are left | |
594 in place as if (true). */ | |
595 if (gimple_cond_true_p (cond)) | |
596 next = te->dest; | |
597 else if (gimple_cond_false_p (cond)) | |
598 next = fe->dest; | |
599 else | |
600 break; | |
601 } | |
602 /* Never traverse a backedge. */ | |
603 if (header->loop_father->header == next) | |
604 return NULL; | |
605 header = next; | |
606 } | |
607 while (1); | |
608 if (!flow_bb_inside_loop_p (loop, te->dest) | |
609 || !flow_bb_inside_loop_p (loop, fe->dest)) | |
610 return NULL; | |
611 | |
612 if (just_once_each_iteration_p (loop, te->dest) | |
613 || (single_succ_p (te->dest) | |
614 && just_once_each_iteration_p (loop, single_succ (te->dest)))) | |
615 { | |
616 if (just_once_each_iteration_p (loop, fe->dest)) | |
617 return NULL; | |
618 guard_edge = te; | |
619 } | |
620 else if (just_once_each_iteration_p (loop, fe->dest) | |
621 || (single_succ_p (fe->dest) | |
622 && just_once_each_iteration_p (loop, single_succ (fe->dest)))) | |
623 guard_edge = fe; | |
624 else | |
625 return NULL; | |
626 | |
627 /* Guard edge must skip inner loop. */ | |
628 if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header, | |
629 guard_edge == fe ? te->dest : fe->dest)) | |
630 { | |
631 if (dump_file && (dump_flags & TDF_DETAILS)) | |
632 fprintf (dump_file, "Guard edge %d --> %d is not around the loop!\n", | |
633 guard_edge->src->index, guard_edge->dest->index); | |
634 return NULL; | |
635 } | |
636 if (guard_edge->dest == loop->latch) | |
637 { | |
638 if (dump_file && (dump_flags & TDF_DETAILS)) | |
639 fprintf (dump_file, "Guard edge destination is loop latch.\n"); | |
640 return NULL; | |
641 } | |
642 | |
643 if (dump_file && (dump_flags & TDF_DETAILS)) | |
644 fprintf (dump_file, | |
645 "Considering guard %d -> %d in loop %d\n", | |
646 guard_edge->src->index, guard_edge->dest->index, loop->num); | |
647 /* Check if condition operands do not have definitions inside loop since | |
648 any bb copying is not performed. */ | |
649 FOR_EACH_SSA_TREE_OPERAND (use, cond, iter, SSA_OP_USE) | |
650 { | |
651 gimple *def = SSA_NAME_DEF_STMT (use); | |
652 basic_block def_bb = gimple_bb (def); | |
653 if (def_bb | |
654 && flow_bb_inside_loop_p (loop, def_bb)) | |
655 { | |
656 if (dump_file && (dump_flags & TDF_DETAILS)) | |
657 fprintf (dump_file, " guard operands have definitions" | |
658 " inside loop\n"); | |
659 return NULL; | |
660 } | |
661 } | |
662 | |
663 body = get_loop_body (loop); | |
664 for (i = 0; i < loop->num_nodes; i++) | |
665 { | |
666 basic_block bb = body[i]; | |
667 if (bb->loop_father != loop) | |
668 continue; | |
669 if (bb->flags & BB_IRREDUCIBLE_LOOP) | |
670 { | |
671 if (dump_file && (dump_flags & TDF_DETAILS)) | |
672 fprintf (dump_file, "Block %d is marked as irreducible in loop\n", | |
673 bb->index); | |
674 guard_edge = NULL; | |
675 goto end; | |
676 } | |
677 if (!empty_bb_without_guard_p (loop, bb)) | |
678 { | |
679 if (dump_file && (dump_flags & TDF_DETAILS)) | |
680 fprintf (dump_file, " block %d has side effects\n", bb->index); | |
681 guard_edge = NULL; | |
682 goto end; | |
683 } | |
684 } | |
685 | |
686 if (dump_file && (dump_flags & TDF_DETAILS)) | |
687 fprintf (dump_file, " suitable to hoist\n"); | |
688 end: | |
689 if (body) | |
690 free (body); | |
691 return guard_edge; | |
692 } | |
693 | |
694 /* Returns true if | |
695 1) no statement in BB has side effects | |
696 2) assuming that edge GUARD is always taken, all definitions in BB | |
697 are noy used outside of the loop. | |
698 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and | |
699 PROCESSED is a set of ssa names for that we already tested whether they | |
700 are invariant or not. */ | |
701 | |
702 static bool | |
145 | 703 empty_bb_without_guard_p (class loop *loop, basic_block bb) |
111 | 704 { |
705 basic_block exit_bb = single_exit (loop)->src; | |
706 bool may_be_used_outside = (bb == exit_bb | |
707 || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)); | |
708 tree name; | |
709 ssa_op_iter op_iter; | |
710 | |
711 /* Phi nodes do not have side effects, but their results might be used | |
712 outside of the loop. */ | |
713 if (may_be_used_outside) | |
714 { | |
715 for (gphi_iterator gsi = gsi_start_phis (bb); | |
716 !gsi_end_p (gsi); gsi_next (&gsi)) | |
717 { | |
718 gphi *phi = gsi.phi (); | |
719 name = PHI_RESULT (phi); | |
720 if (virtual_operand_p (name)) | |
721 continue; | |
722 | |
723 if (used_outside_loop_p (loop, name)) | |
724 return false; | |
725 } | |
726 } | |
727 | |
728 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); | |
729 !gsi_end_p (gsi); gsi_next (&gsi)) | |
730 { | |
731 gimple *stmt = gsi_stmt (gsi); | |
732 if (gimple_has_side_effects (stmt)) | |
733 return false; | |
734 | |
735 if (gimple_vdef(stmt)) | |
736 return false; | |
737 | |
738 FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF) | |
739 { | |
740 if (may_be_used_outside | |
741 && used_outside_loop_p (loop, name)) | |
742 return false; | |
743 } | |
744 } | |
745 return true; | |
0 | 746 } |
111 | 747 |
748 /* Return true if NAME is used outside of LOOP. */ | |
749 | |
750 static bool | |
145 | 751 used_outside_loop_p (class loop *loop, tree name) |
111 | 752 { |
753 imm_use_iterator it; | |
754 use_operand_p use; | |
755 | |
756 FOR_EACH_IMM_USE_FAST (use, it, name) | |
757 { | |
758 gimple *stmt = USE_STMT (use); | |
759 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt))) | |
760 return true; | |
761 } | |
762 | |
763 return false; | |
764 } | |
765 | |
766 /* Return argument for loop preheader edge in header virtual phi if any. */ | |
767 | |
768 static tree | |
145 | 769 get_vop_from_header (class loop *loop) |
111 | 770 { |
771 for (gphi_iterator gsi = gsi_start_phis (loop->header); | |
772 !gsi_end_p (gsi); gsi_next (&gsi)) | |
773 { | |
774 gphi *phi = gsi.phi (); | |
775 if (!virtual_operand_p (gimple_phi_result (phi))) | |
776 continue; | |
777 return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); | |
778 } | |
779 return NULL_TREE; | |
780 } | |
781 | |
782 /* Move the check of GUARD outside of LOOP. */ | |
783 | |
784 static void | |
145 | 785 hoist_guard (class loop *loop, edge guard) |
111 | 786 { |
787 edge exit = single_exit (loop); | |
788 edge preh = loop_preheader_edge (loop); | |
789 basic_block pre_header = preh->src; | |
790 basic_block bb; | |
791 edge te, fe, e, new_edge; | |
792 gimple *stmt; | |
793 basic_block guard_bb = guard->src; | |
794 edge not_guard; | |
795 gimple_stmt_iterator gsi; | |
796 int flags = 0; | |
797 bool fix_dom_of_exit; | |
798 gcond *cond_stmt, *new_cond_stmt; | |
799 | |
800 bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest); | |
801 fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb); | |
802 gsi = gsi_last_bb (guard_bb); | |
803 stmt = gsi_stmt (gsi); | |
804 gcc_assert (gimple_code (stmt) == GIMPLE_COND); | |
805 cond_stmt = as_a <gcond *> (stmt); | |
806 extract_true_false_edges_from_block (guard_bb, &te, &fe); | |
807 /* Insert guard to PRE_HEADER. */ | |
808 if (!empty_block_p (pre_header)) | |
809 gsi = gsi_last_bb (pre_header); | |
810 else | |
811 gsi = gsi_start_bb (pre_header); | |
812 /* Create copy of COND_STMT. */ | |
813 new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt), | |
814 gimple_cond_lhs (cond_stmt), | |
815 gimple_cond_rhs (cond_stmt), | |
816 NULL_TREE, NULL_TREE); | |
817 gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT); | |
818 /* Convert COND_STMT to true/false conditional. */ | |
819 if (guard == te) | |
820 gimple_cond_make_false (cond_stmt); | |
821 else | |
822 gimple_cond_make_true (cond_stmt); | |
823 update_stmt (cond_stmt); | |
824 /* Create new loop pre-header. */ | |
825 e = split_block (pre_header, last_stmt (pre_header)); | |
826 if (dump_file && (dump_flags & TDF_DETAILS)) | |
827 { | |
828 fprintf (dump_file, " Moving guard %i->%i (prob ", | |
829 guard->src->index, guard->dest->index); | |
830 guard->probability.dump (dump_file); | |
831 fprintf (dump_file, ") to bb %i, new preheader is %i\n", | |
832 e->src->index, e->dest->index); | |
833 } | |
834 | |
835 gcc_assert (loop_preheader_edge (loop)->src == e->dest); | |
836 | |
837 if (guard == fe) | |
838 { | |
839 e->flags = EDGE_TRUE_VALUE; | |
840 flags |= EDGE_FALSE_VALUE; | |
841 not_guard = te; | |
842 } | |
843 else | |
844 { | |
845 e->flags = EDGE_FALSE_VALUE; | |
846 flags |= EDGE_TRUE_VALUE; | |
847 not_guard = fe; | |
848 } | |
849 new_edge = make_edge (pre_header, exit->dest, flags); | |
850 | |
851 /* Determine the probability that we skip the loop. Assume that loop has | |
852 same average number of iterations regardless outcome of guard. */ | |
853 new_edge->probability = guard->probability; | |
131 | 854 profile_count skip_count = guard->src->count.nonzero_p () |
111 | 855 ? guard->count ().apply_scale (pre_header->count, |
856 guard->src->count) | |
857 : guard->count ().apply_probability (new_edge->probability); | |
858 | |
859 if (skip_count > e->count ()) | |
860 { | |
861 fprintf (dump_file, " Capping count; expect profile inconsistency\n"); | |
862 skip_count = e->count (); | |
863 } | |
864 if (dump_file && (dump_flags & TDF_DETAILS)) | |
865 { | |
866 fprintf (dump_file, " Estimated probability of skipping loop is "); | |
867 new_edge->probability.dump (dump_file); | |
868 fprintf (dump_file, "\n"); | |
869 } | |
870 | |
871 /* Update profile after the transform: | |
872 | |
873 First decrease count of path from newly hoisted loop guard | |
874 to loop header... */ | |
875 e->probability = new_edge->probability.invert (); | |
876 e->dest->count = e->count (); | |
877 | |
878 /* ... now update profile to represent that original guard will be optimized | |
879 away ... */ | |
880 guard->probability = profile_probability::never (); | |
881 not_guard->probability = profile_probability::always (); | |
882 | |
883 /* ... finally scale everything in the loop except for guarded basic blocks | |
884 where profile does not change. */ | |
885 basic_block *body = get_loop_body (loop); | |
886 | |
887 if (dump_file && (dump_flags & TDF_DETAILS)) | |
888 fprintf (dump_file, " Scaling nonguarded BBs in loop:"); | |
889 for (unsigned int i = 0; i < loop->num_nodes; i++) | |
890 { | |
891 basic_block bb = body[i]; | |
892 if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest)) | |
893 { | |
894 if (dump_file && (dump_flags & TDF_DETAILS)) | |
895 fprintf (dump_file, " %i", bb->index); | |
896 if (e->probability.initialized_p ()) | |
897 scale_bbs_frequencies (&bb, 1, e->probability); | |
898 } | |
899 } | |
900 | |
901 if (fix_dom_of_exit) | |
902 set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header); | |
903 /* Add NEW_ADGE argument for all phi in post-header block. */ | |
904 bb = exit->dest; | |
905 for (gphi_iterator gsi = gsi_start_phis (bb); | |
906 !gsi_end_p (gsi); gsi_next (&gsi)) | |
907 { | |
908 gphi *phi = gsi.phi (); | |
909 tree arg; | |
910 if (virtual_operand_p (gimple_phi_result (phi))) | |
911 { | |
912 arg = get_vop_from_header (loop); | |
913 if (arg == NULL_TREE) | |
914 /* Use exit edge argument. */ | |
915 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit); | |
916 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION); | |
917 } | |
918 else | |
919 { | |
920 /* Use exit edge argument. */ | |
921 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit); | |
922 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION); | |
923 } | |
924 } | |
925 | |
926 if (dump_file && (dump_flags & TDF_DETAILS)) | |
927 fprintf (dump_file, "\n guard hoisted.\n"); | |
928 | |
929 free (body); | |
930 } | |
931 | |
932 /* Return true if phi argument for exit edge can be used | |
933 for edge around loop. */ | |
934 | |
935 static bool | |
145 | 936 check_exit_phi (class loop *loop) |
111 | 937 { |
938 edge exit = single_exit (loop); | |
939 basic_block pre_header = loop_preheader_edge (loop)->src; | |
940 | |
941 for (gphi_iterator gsi = gsi_start_phis (exit->dest); | |
942 !gsi_end_p (gsi); gsi_next (&gsi)) | |
943 { | |
944 gphi *phi = gsi.phi (); | |
945 tree arg; | |
946 gimple *def; | |
947 basic_block def_bb; | |
948 if (virtual_operand_p (gimple_phi_result (phi))) | |
949 continue; | |
950 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit); | |
951 if (TREE_CODE (arg) != SSA_NAME) | |
952 continue; | |
953 def = SSA_NAME_DEF_STMT (arg); | |
954 if (!def) | |
955 continue; | |
956 def_bb = gimple_bb (def); | |
957 if (!def_bb) | |
958 continue; | |
959 if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb)) | |
960 /* Definition inside loop! */ | |
961 return false; | |
962 /* Check loop closed phi invariant. */ | |
963 if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header)) | |
964 return false; | |
965 } | |
966 return true; | |
967 } | |
968 | |
969 /* Loop unswitching pass. */ | |
970 | |
971 namespace { | |
972 | |
973 const pass_data pass_data_tree_unswitch = | |
974 { | |
975 GIMPLE_PASS, /* type */ | |
976 "unswitch", /* name */ | |
977 OPTGROUP_LOOP, /* optinfo_flags */ | |
978 TV_TREE_LOOP_UNSWITCH, /* tv_id */ | |
979 PROP_cfg, /* properties_required */ | |
980 0, /* properties_provided */ | |
981 0, /* properties_destroyed */ | |
982 0, /* todo_flags_start */ | |
983 0, /* todo_flags_finish */ | |
984 }; | |
985 | |
986 class pass_tree_unswitch : public gimple_opt_pass | |
987 { | |
988 public: | |
989 pass_tree_unswitch (gcc::context *ctxt) | |
990 : gimple_opt_pass (pass_data_tree_unswitch, ctxt) | |
991 {} | |
992 | |
993 /* opt_pass methods: */ | |
994 virtual bool gate (function *) { return flag_unswitch_loops != 0; } | |
995 virtual unsigned int execute (function *); | |
996 | |
997 }; // class pass_tree_unswitch | |
998 | |
999 unsigned int | |
1000 pass_tree_unswitch::execute (function *fun) | |
1001 { | |
1002 if (number_of_loops (fun) <= 1) | |
1003 return 0; | |
1004 | |
1005 return tree_ssa_unswitch_loops (); | |
1006 } | |
1007 | |
1008 } // anon namespace | |
1009 | |
1010 gimple_opt_pass * | |
1011 make_pass_tree_unswitch (gcc::context *ctxt) | |
1012 { | |
1013 return new pass_tree_unswitch (ctxt); | |
1014 } | |
1015 | |
1016 |