]>
Commit | Line | Data |
---|---|---|
92fc4a2f | 1 | /* Loop unswitching. |
d1e082c2 | 2 | Copyright (C) 2004-2013 Free Software Foundation, Inc. |
b8698a0f | 3 | |
92fc4a2f | 4 | This file is part of GCC. |
b8698a0f | 5 | |
92fc4a2f ZD |
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 | |
9dcd6f09 | 8 | Free Software Foundation; either version 3, or (at your option) any |
92fc4a2f | 9 | later version. |
b8698a0f | 10 | |
92fc4a2f ZD |
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. | |
b8698a0f | 15 | |
92fc4a2f | 16 | You should have received a copy of the GNU General Public License |
9dcd6f09 NC |
17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
92fc4a2f ZD |
19 | |
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
23 | #include "tm.h" | |
24 | #include "tree.h" | |
92fc4a2f | 25 | #include "tm_p.h" |
92fc4a2f | 26 | #include "basic-block.h" |
7a300452 | 27 | #include "tree-ssa.h" |
92fc4a2f | 28 | #include "cfgloop.h" |
92fc4a2f ZD |
29 | #include "params.h" |
30 | #include "tree-pass.h" | |
7f9bc51b | 31 | #include "tree-inline.h" |
92fc4a2f ZD |
32 | |
33 | /* This file implements the loop unswitching, i.e. transformation of loops like | |
34 | ||
35 | while (A) | |
36 | { | |
37 | if (inv) | |
38 | B; | |
39 | ||
40 | X; | |
41 | ||
42 | if (!inv) | |
43 | C; | |
44 | } | |
45 | ||
46 | where inv is the loop invariant, into | |
47 | ||
48 | if (inv) | |
49 | { | |
50 | while (A) | |
51 | { | |
52 | B; | |
53 | X; | |
54 | } | |
55 | } | |
56 | else | |
57 | { | |
58 | while (A) | |
59 | { | |
60 | X; | |
61 | C; | |
62 | } | |
63 | } | |
64 | ||
65 | Inv is considered invariant iff the values it compares are both invariant; | |
66 | tree-ssa-loop-im.c ensures that all the suitable conditions are in this | |
67 | shape. */ | |
68 | ||
d73be268 ZD |
69 | static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree); |
70 | static bool tree_unswitch_single_loop (struct loop *, int); | |
92fc4a2f ZD |
71 | static tree tree_may_unswitch_on (basic_block, struct loop *); |
72 | ||
d73be268 | 73 | /* Main entry point. Perform loop unswitching on all suitable loops. */ |
92fc4a2f | 74 | |
c7f965b6 | 75 | unsigned int |
d73be268 | 76 | tree_ssa_unswitch_loops (void) |
92fc4a2f | 77 | { |
42fd6772 | 78 | loop_iterator li; |
92fc4a2f ZD |
79 | struct loop *loop; |
80 | bool changed = false; | |
e3a8f1fa | 81 | HOST_WIDE_INT iterations; |
92fc4a2f ZD |
82 | |
83 | /* Go through inner loops (only original ones). */ | |
677cc14d | 84 | FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST) |
92fc4a2f | 85 | { |
dc5ee869 JY |
86 | if (dump_file && (dump_flags & TDF_DETAILS)) |
87 | fprintf (dump_file, ";; Considering loop %d\n", loop->num); | |
88 | ||
89 | /* Do not unswitch in cold regions. */ | |
90 | if (optimize_loop_for_size_p (loop)) | |
91 | { | |
92 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
93 | fprintf (dump_file, ";; Not unswitching cold loops\n"); | |
94 | continue; | |
95 | } | |
96 | ||
97 | /* The loop should not be too large, to limit code growth. */ | |
98 | if (tree_num_loop_insns (loop, &eni_size_weights) | |
99 | > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS)) | |
100 | { | |
101 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
102 | fprintf (dump_file, ";; Not unswitching, loop too big\n"); | |
103 | continue; | |
104 | } | |
105 | ||
e3a8f1fa JH |
106 | /* If the loop is not expected to iterate, there is no need |
107 | for unswitching. */ | |
108 | iterations = estimated_loop_iterations_int (loop); | |
109 | if (iterations >= 0 && iterations <= 1) | |
110 | { | |
111 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
112 | fprintf (dump_file, ";; Not unswitching, loop is not expected to iterate\n"); | |
113 | continue; | |
114 | } | |
115 | ||
d73be268 | 116 | changed |= tree_unswitch_single_loop (loop, 0); |
92fc4a2f ZD |
117 | } |
118 | ||
92fc4a2f | 119 | if (changed) |
c7f965b6 AP |
120 | return TODO_cleanup_cfg; |
121 | return 0; | |
92fc4a2f ZD |
122 | } |
123 | ||
124 | /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its | |
125 | basic blocks (for what it means see comments below). */ | |
126 | ||
127 | static tree | |
128 | tree_may_unswitch_on (basic_block bb, struct loop *loop) | |
129 | { | |
726a989a RB |
130 | gimple stmt, def; |
131 | tree cond, use; | |
92fc4a2f | 132 | basic_block def_bb; |
f47c96aa | 133 | ssa_op_iter iter; |
92fc4a2f ZD |
134 | |
135 | /* BB must end in a simple conditional jump. */ | |
136 | stmt = last_stmt (bb); | |
726a989a | 137 | if (!stmt || gimple_code (stmt) != GIMPLE_COND) |
92fc4a2f ZD |
138 | return NULL_TREE; |
139 | ||
7a2eceff JJ |
140 | /* To keep the things simple, we do not directly remove the conditions, |
141 | but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite | |
142 | loop where we would unswitch again on such a condition. */ | |
143 | if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt)) | |
144 | return NULL_TREE; | |
145 | ||
92fc4a2f | 146 | /* Condition must be invariant. */ |
f47c96aa | 147 | FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) |
92fc4a2f | 148 | { |
f47c96aa | 149 | def = SSA_NAME_DEF_STMT (use); |
726a989a | 150 | def_bb = gimple_bb (def); |
92fc4a2f ZD |
151 | if (def_bb |
152 | && flow_bb_inside_loop_p (loop, def_bb)) | |
153 | return NULL_TREE; | |
154 | } | |
155 | ||
12aea97a RG |
156 | cond = build2 (gimple_cond_code (stmt), boolean_type_node, |
157 | gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); | |
726a989a | 158 | |
92fc4a2f ZD |
159 | return cond; |
160 | } | |
161 | ||
162 | /* Simplifies COND using checks in front of the entry of the LOOP. Just very | |
163 | simplish (sufficient to prevent us from duplicating loop in unswitching | |
e75220c8 | 164 | unnecessarily). */ |
92fc4a2f ZD |
165 | |
166 | static tree | |
167 | simplify_using_entry_checks (struct loop *loop, tree cond) | |
168 | { | |
169 | edge e = loop_preheader_edge (loop); | |
726a989a | 170 | gimple stmt; |
92fc4a2f ZD |
171 | |
172 | while (1) | |
173 | { | |
174 | stmt = last_stmt (e->src); | |
175 | if (stmt | |
726a989a RB |
176 | && gimple_code (stmt) == GIMPLE_COND |
177 | && gimple_cond_code (stmt) == TREE_CODE (cond) | |
178 | && operand_equal_p (gimple_cond_lhs (stmt), | |
179 | TREE_OPERAND (cond, 0), 0) | |
180 | && operand_equal_p (gimple_cond_rhs (stmt), | |
181 | TREE_OPERAND (cond, 1), 0)) | |
92fc4a2f ZD |
182 | return (e->flags & EDGE_TRUE_VALUE |
183 | ? boolean_true_node | |
184 | : boolean_false_node); | |
185 | ||
c5cbcccf | 186 | if (!single_pred_p (e->src)) |
92fc4a2f ZD |
187 | return cond; |
188 | ||
c5cbcccf | 189 | e = single_pred_edge (e->src); |
92fc4a2f ZD |
190 | if (e->src == ENTRY_BLOCK_PTR) |
191 | return cond; | |
192 | } | |
193 | } | |
194 | ||
195 | /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow | |
196 | it to grow too much, it is too easy to create example on that the code would | |
197 | grow exponentially. */ | |
198 | ||
199 | static bool | |
d73be268 | 200 | tree_unswitch_single_loop (struct loop *loop, int num) |
92fc4a2f ZD |
201 | { |
202 | basic_block *bbs; | |
203 | struct loop *nloop; | |
7a2eceff | 204 | unsigned i, found; |
726a989a RB |
205 | tree cond = NULL_TREE; |
206 | gimple stmt; | |
92fc4a2f ZD |
207 | bool changed = false; |
208 | ||
92fc4a2f ZD |
209 | i = 0; |
210 | bbs = get_loop_body (loop); | |
7a2eceff | 211 | found = loop->num_nodes; |
b8698a0f | 212 | |
92fc4a2f ZD |
213 | while (1) |
214 | { | |
215 | /* Find a bb to unswitch on. */ | |
216 | for (; i < loop->num_nodes; i++) | |
217 | if ((cond = tree_may_unswitch_on (bbs[i], loop))) | |
218 | break; | |
219 | ||
220 | if (i == loop->num_nodes) | |
221 | { | |
7a2eceff JJ |
222 | if (dump_file |
223 | && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL) | |
224 | && (dump_flags & TDF_DETAILS)) | |
225 | fprintf (dump_file, ";; Not unswitching anymore, hit max level\n"); | |
226 | ||
227 | if (found == loop->num_nodes) | |
228 | { | |
229 | free (bbs); | |
230 | return changed; | |
231 | } | |
232 | break; | |
92fc4a2f ZD |
233 | } |
234 | ||
235 | cond = simplify_using_entry_checks (loop, cond); | |
236 | stmt = last_stmt (bbs[i]); | |
237 | if (integer_nonzerop (cond)) | |
238 | { | |
239 | /* Remove false path. */ | |
726a989a | 240 | gimple_cond_set_condition_from_tree (stmt, boolean_true_node); |
92fc4a2f ZD |
241 | changed = true; |
242 | } | |
243 | else if (integer_zerop (cond)) | |
244 | { | |
245 | /* Remove true path. */ | |
726a989a | 246 | gimple_cond_set_condition_from_tree (stmt, boolean_false_node); |
92fc4a2f ZD |
247 | changed = true; |
248 | } | |
7a2eceff JJ |
249 | /* Do not unswitch too much. */ |
250 | else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) | |
251 | { | |
252 | i++; | |
253 | continue; | |
254 | } | |
255 | /* In nested tree_unswitch_single_loop first optimize all conditions | |
256 | using entry checks, then discover still reachable blocks in the | |
257 | loop and find the condition only among those still reachable bbs. */ | |
258 | else if (num != 0) | |
259 | { | |
260 | if (found == loop->num_nodes) | |
261 | found = i; | |
262 | i++; | |
263 | continue; | |
264 | } | |
92fc4a2f | 265 | else |
7a2eceff JJ |
266 | { |
267 | found = i; | |
268 | break; | |
269 | } | |
92fc4a2f | 270 | |
f430bae8 | 271 | update_stmt (stmt); |
92fc4a2f ZD |
272 | i++; |
273 | } | |
274 | ||
7a2eceff JJ |
275 | if (num != 0) |
276 | { | |
277 | basic_block *tos, *worklist; | |
278 | ||
279 | /* When called recursively, first do a quick discovery | |
280 | of reachable bbs after the above changes and only | |
281 | consider conditions in still reachable bbs. */ | |
282 | tos = worklist = XNEWVEC (basic_block, loop->num_nodes); | |
283 | ||
284 | for (i = 0; i < loop->num_nodes; i++) | |
285 | bbs[i]->flags &= ~BB_REACHABLE; | |
286 | ||
287 | /* Start with marking header. */ | |
288 | *tos++ = bbs[0]; | |
289 | bbs[0]->flags |= BB_REACHABLE; | |
290 | ||
291 | /* Iterate: find everything reachable from what we've already seen | |
292 | within the same innermost loop. Don't look through false edges | |
293 | if condition is always true or true edges if condition is | |
294 | always false. */ | |
295 | while (tos != worklist) | |
296 | { | |
297 | basic_block b = *--tos; | |
298 | edge e; | |
299 | edge_iterator ei; | |
300 | int flags = 0; | |
301 | ||
302 | if (EDGE_COUNT (b->succs) == 2) | |
303 | { | |
304 | gimple stmt = last_stmt (b); | |
305 | if (stmt | |
306 | && gimple_code (stmt) == GIMPLE_COND) | |
307 | { | |
308 | if (gimple_cond_true_p (stmt)) | |
309 | flags = EDGE_FALSE_VALUE; | |
310 | else if (gimple_cond_false_p (stmt)) | |
311 | flags = EDGE_TRUE_VALUE; | |
312 | } | |
313 | } | |
314 | ||
315 | FOR_EACH_EDGE (e, ei, b->succs) | |
316 | { | |
317 | basic_block dest = e->dest; | |
318 | ||
319 | if (dest->loop_father == loop | |
320 | && !(dest->flags & BB_REACHABLE) | |
321 | && !(e->flags & flags)) | |
322 | { | |
323 | *tos++ = dest; | |
324 | dest->flags |= BB_REACHABLE; | |
325 | } | |
326 | } | |
327 | } | |
328 | ||
329 | free (worklist); | |
330 | ||
331 | /* Find a bb to unswitch on. */ | |
332 | for (; found < loop->num_nodes; found++) | |
333 | if ((bbs[found]->flags & BB_REACHABLE) | |
334 | && (cond = tree_may_unswitch_on (bbs[found], loop))) | |
335 | break; | |
336 | ||
337 | if (found == loop->num_nodes) | |
338 | { | |
339 | free (bbs); | |
340 | return changed; | |
341 | } | |
342 | } | |
343 | ||
92fc4a2f ZD |
344 | if (dump_file && (dump_flags & TDF_DETAILS)) |
345 | fprintf (dump_file, ";; Unswitching loop\n"); | |
346 | ||
6580ee77 | 347 | initialize_original_copy_tables (); |
92fc4a2f | 348 | /* Unswitch the loop on this condition. */ |
7a2eceff | 349 | nloop = tree_unswitch_loop (loop, bbs[found], cond); |
92fc4a2f | 350 | if (!nloop) |
094bb856 JH |
351 | { |
352 | free_original_copy_tables (); | |
77f6ec05 | 353 | free (bbs); |
094bb856 JH |
354 | return changed; |
355 | } | |
92fc4a2f | 356 | |
84d65814 DN |
357 | /* Update the SSA form after unswitching. */ |
358 | update_ssa (TODO_update_ssa); | |
6580ee77 | 359 | free_original_copy_tables (); |
84d65814 | 360 | |
92fc4a2f | 361 | /* Invoke itself on modified loops. */ |
d73be268 ZD |
362 | tree_unswitch_single_loop (nloop, num + 1); |
363 | tree_unswitch_single_loop (loop, num + 1); | |
77f6ec05 | 364 | free (bbs); |
92fc4a2f ZD |
365 | return true; |
366 | } | |
367 | ||
368 | /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support | |
369 | unswitching of innermost loops. COND is the condition determining which | |
370 | loop is entered -- the new loop is entered if COND is true. Returns NULL | |
371 | if impossible, new loop otherwise. */ | |
372 | ||
373 | static struct loop * | |
d73be268 | 374 | tree_unswitch_loop (struct loop *loop, |
92fc4a2f ZD |
375 | basic_block unswitch_on, tree cond) |
376 | { | |
03cb2019 ZD |
377 | unsigned prob_true; |
378 | edge edge_true, edge_false; | |
92fc4a2f ZD |
379 | |
380 | /* Some sanity checking. */ | |
381 | gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on)); | |
628f6a4e | 382 | gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2); |
92fc4a2f ZD |
383 | gcc_assert (loop->inner == NULL); |
384 | ||
03cb2019 ZD |
385 | extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false); |
386 | prob_true = edge_true->probability; | |
b8698a0f | 387 | return loop_version (loop, unshare_expr (cond), |
03cb2019 ZD |
388 | NULL, prob_true, prob_true, |
389 | REG_BR_PROB_BASE - prob_true, false); | |
92fc4a2f | 390 | } |