]>
Commit | Line | Data |
---|---|---|
c913f08a | 1 | /* High-level loop manipulation functions. |
5624e564 | 2 | Copyright (C) 2004-2015 Free Software Foundation, Inc. |
b8698a0f | 3 | |
c913f08a | 4 | This file is part of GCC. |
b8698a0f | 5 | |
c913f08a 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 |
c913f08a | 9 | later version. |
b8698a0f | 10 | |
c913f08a 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 | |
c913f08a | 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/>. */ | |
c913f08a ZD |
19 | |
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
c7131fb2 | 23 | #include "backend.h" |
c913f08a | 24 | #include "tree.h" |
c7131fb2 AM |
25 | #include "gimple.h" |
26 | #include "hard-reg-set.h" | |
27 | #include "ssa.h" | |
28 | #include "alias.h" | |
40e23961 | 29 | #include "fold-const.h" |
c913f08a | 30 | #include "tm_p.h" |
60393bbc | 31 | #include "cfganal.h" |
2fb9a547 | 32 | #include "internal-fn.h" |
45b0be94 | 33 | #include "gimplify.h" |
5be5c238 | 34 | #include "gimple-iterator.h" |
18f429e2 | 35 | #include "gimplify-me.h" |
442b4905 | 36 | #include "tree-cfg.h" |
e28030cf AM |
37 | #include "tree-ssa-loop-ivopts.h" |
38 | #include "tree-ssa-loop-manip.h" | |
39 | #include "tree-ssa-loop-niter.h" | |
442b4905 AM |
40 | #include "tree-ssa-loop.h" |
41 | #include "tree-into-ssa.h" | |
7a300452 | 42 | #include "tree-ssa.h" |
7ee2468b | 43 | #include "dumpfile.h" |
01273677 | 44 | #include "gimple-pretty-print.h" |
c913f08a | 45 | #include "cfgloop.h" |
7ee2468b | 46 | #include "tree-pass.h" /* ??? for TODO_update_ssa but this isn't a pass. */ |
c913f08a | 47 | #include "tree-scalar-evolution.h" |
17684618 | 48 | #include "params.h" |
7f9bc51b | 49 | #include "tree-inline.h" |
08dab97a | 50 | #include "langhooks.h" |
c913f08a | 51 | |
c302207e SB |
52 | /* All bitmaps for rewriting into loop-closed SSA go on this obstack, |
53 | so that we can free them all at once. */ | |
54 | static bitmap_obstack loop_renamer_obstack; | |
55 | ||
82b85a85 ZD |
56 | /* Creates an induction variable with value BASE + STEP * iteration in LOOP. |
57 | It is expected that neither BASE nor STEP are shared with other expressions | |
58 | (unless the sharing rules allow this). Use VAR as a base var_decl for it | |
59 | (if NULL, a new temporary will be created). The increment will occur at | |
b8698a0f | 60 | INCR_POS (after it if AFTER is true, before it otherwise). INCR_POS and |
92d2b330 | 61 | AFTER can be computed using standard_iv_increment_position. The ssa versions |
82b85a85 ZD |
62 | of the variable before and after increment will be stored in VAR_BEFORE and |
63 | VAR_AFTER (unless they are NULL). */ | |
64 | ||
65 | void | |
66 | create_iv (tree base, tree step, tree var, struct loop *loop, | |
726a989a | 67 | gimple_stmt_iterator *incr_pos, bool after, |
82b85a85 ZD |
68 | tree *var_before, tree *var_after) |
69 | { | |
538dd0b7 DM |
70 | gassign *stmt; |
71 | gphi *phi; | |
726a989a RB |
72 | tree initial, step1; |
73 | gimple_seq stmts; | |
82b85a85 ZD |
74 | tree vb, va; |
75 | enum tree_code incr_op = PLUS_EXPR; | |
9be872b7 | 76 | edge pe = loop_preheader_edge (loop); |
82b85a85 | 77 | |
83d5977e RG |
78 | if (var != NULL_TREE) |
79 | { | |
b731b390 JJ |
80 | vb = make_ssa_name (var); |
81 | va = make_ssa_name (var); | |
83d5977e RG |
82 | } |
83 | else | |
84 | { | |
85 | vb = make_temp_ssa_name (TREE_TYPE (base), NULL, "ivtmp"); | |
86 | va = make_temp_ssa_name (TREE_TYPE (base), NULL, "ivtmp"); | |
87 | } | |
82b85a85 ZD |
88 | if (var_before) |
89 | *var_before = vb; | |
82b85a85 ZD |
90 | if (var_after) |
91 | *var_after = va; | |
92 | ||
93 | /* For easier readability of the created code, produce MINUS_EXPRs | |
94 | when suitable. */ | |
95 | if (TREE_CODE (step) == INTEGER_CST) | |
96 | { | |
97 | if (TYPE_UNSIGNED (TREE_TYPE (step))) | |
98 | { | |
987b67bc | 99 | step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); |
82b85a85 ZD |
100 | if (tree_int_cst_lt (step1, step)) |
101 | { | |
102 | incr_op = MINUS_EXPR; | |
103 | step = step1; | |
104 | } | |
105 | } | |
106 | else | |
107 | { | |
6ac01510 ILT |
108 | bool ovf; |
109 | ||
110 | if (!tree_expr_nonnegative_warnv_p (step, &ovf) | |
82b85a85 ZD |
111 | && may_negate_without_overflow_p (step)) |
112 | { | |
113 | incr_op = MINUS_EXPR; | |
987b67bc | 114 | step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); |
82b85a85 ZD |
115 | } |
116 | } | |
117 | } | |
5be014d5 AP |
118 | if (POINTER_TYPE_P (TREE_TYPE (base))) |
119 | { | |
628c189e RG |
120 | if (TREE_CODE (base) == ADDR_EXPR) |
121 | mark_addressable (TREE_OPERAND (base, 0)); | |
0d82a1c8 | 122 | step = convert_to_ptrofftype (step); |
5be014d5 | 123 | if (incr_op == MINUS_EXPR) |
0d82a1c8 | 124 | step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); |
5be014d5 AP |
125 | incr_op = POINTER_PLUS_EXPR; |
126 | } | |
9be872b7 ZD |
127 | /* Gimplify the step if necessary. We put the computations in front of the |
128 | loop (i.e. the step should be loop invariant). */ | |
1ffe34d9 | 129 | step = force_gimple_operand (step, &stmts, true, NULL_TREE); |
9be872b7 | 130 | if (stmts) |
726a989a | 131 | gsi_insert_seq_on_edge_immediate (pe, stmts); |
9be872b7 | 132 | |
0d0e4a03 | 133 | stmt = gimple_build_assign (va, incr_op, vb, step); |
82b85a85 | 134 | if (after) |
726a989a | 135 | gsi_insert_after (incr_pos, stmt, GSI_NEW_STMT); |
82b85a85 | 136 | else |
726a989a | 137 | gsi_insert_before (incr_pos, stmt, GSI_NEW_STMT); |
82b85a85 | 138 | |
8b11a64c ZD |
139 | initial = force_gimple_operand (base, &stmts, true, var); |
140 | if (stmts) | |
726a989a | 141 | gsi_insert_seq_on_edge_immediate (pe, stmts); |
82b85a85 | 142 | |
538dd0b7 DM |
143 | phi = create_phi_node (vb, loop->header); |
144 | add_phi_arg (phi, initial, loop_preheader_edge (loop), UNKNOWN_LOCATION); | |
145 | add_phi_arg (phi, va, loop_latch_edge (loop), UNKNOWN_LOCATION); | |
82b85a85 ZD |
146 | } |
147 | ||
3f9b14ff | 148 | /* Return the innermost superloop LOOP of USE_LOOP that is a superloop of |
01273677 SB |
149 | both DEF_LOOP and USE_LOOP. */ |
150 | ||
151 | static inline struct loop * | |
152 | find_sibling_superloop (struct loop *use_loop, struct loop *def_loop) | |
153 | { | |
154 | unsigned ud = loop_depth (use_loop); | |
155 | unsigned dd = loop_depth (def_loop); | |
156 | gcc_assert (ud > 0 && dd > 0); | |
157 | if (ud > dd) | |
158 | use_loop = superloop_at_depth (use_loop, dd); | |
159 | if (ud < dd) | |
160 | def_loop = superloop_at_depth (def_loop, ud); | |
161 | while (loop_outer (use_loop) != loop_outer (def_loop)) | |
162 | { | |
163 | use_loop = loop_outer (use_loop); | |
164 | def_loop = loop_outer (def_loop); | |
165 | gcc_assert (use_loop && def_loop); | |
166 | } | |
167 | return use_loop; | |
168 | } | |
169 | ||
170 | /* DEF_BB is a basic block containing a DEF that needs rewriting into | |
171 | loop-closed SSA form. USE_BLOCKS is the set of basic blocks containing | |
172 | uses of DEF that "escape" from the loop containing DEF_BB (i.e. blocks in | |
173 | USE_BLOCKS are dominated by DEF_BB but not in the loop father of DEF_B). | |
174 | ALL_EXITS[I] is the set of all basic blocks that exit loop I. | |
175 | ||
176 | Compute the subset of LOOP_EXITS that exit the loop containing DEF_BB | |
177 | or one of its loop fathers, in which DEF is live. This set is returned | |
178 | in the bitmap LIVE_EXITS. | |
179 | ||
180 | Instead of computing the complete livein set of the def, we use the loop | |
181 | nesting tree as a form of poor man's structure analysis. This greatly | |
182 | speeds up the analysis, which is important because this function may be | |
183 | called on all SSA names that need rewriting, one at a time. */ | |
c913f08a ZD |
184 | |
185 | static void | |
01273677 SB |
186 | compute_live_loop_exits (bitmap live_exits, bitmap use_blocks, |
187 | bitmap *loop_exits, basic_block def_bb) | |
c913f08a | 188 | { |
01273677 SB |
189 | unsigned i; |
190 | bitmap_iterator bi; | |
01273677 SB |
191 | struct loop *def_loop = def_bb->loop_father; |
192 | unsigned def_loop_depth = loop_depth (def_loop); | |
193 | bitmap def_loop_exits; | |
194 | ||
195 | /* Normally the work list size is bounded by the number of basic | |
196 | blocks in the largest loop. We don't know this number, but we | |
197 | can be fairly sure that it will be relatively small. */ | |
ef062b13 | 198 | auto_vec<basic_block> worklist (MAX (8, n_basic_blocks_for_fn (cfun) / 128)); |
01273677 SB |
199 | |
200 | EXECUTE_IF_SET_IN_BITMAP (use_blocks, 0, i, bi) | |
201 | { | |
06e28de2 | 202 | basic_block use_bb = BASIC_BLOCK_FOR_FN (cfun, i); |
01273677 SB |
203 | struct loop *use_loop = use_bb->loop_father; |
204 | gcc_checking_assert (def_loop != use_loop | |
205 | && ! flow_loop_nested_p (def_loop, use_loop)); | |
206 | if (! flow_loop_nested_p (use_loop, def_loop)) | |
207 | use_bb = find_sibling_superloop (use_loop, def_loop)->header; | |
208 | if (bitmap_set_bit (live_exits, use_bb->index)) | |
9771b263 | 209 | worklist.safe_push (use_bb); |
01273677 SB |
210 | } |
211 | ||
212 | /* Iterate until the worklist is empty. */ | |
9771b263 | 213 | while (! worklist.is_empty ()) |
01273677 SB |
214 | { |
215 | edge e; | |
216 | edge_iterator ei; | |
217 | ||
218 | /* Pull a block off the worklist. */ | |
9771b263 | 219 | basic_block bb = worklist.pop (); |
01273677 SB |
220 | |
221 | /* Make sure we have at least enough room in the work list | |
222 | for all predecessors of this block. */ | |
9771b263 | 223 | worklist.reserve (EDGE_COUNT (bb->preds)); |
01273677 SB |
224 | |
225 | /* For each predecessor block. */ | |
226 | FOR_EACH_EDGE (e, ei, bb->preds) | |
227 | { | |
228 | basic_block pred = e->src; | |
229 | struct loop *pred_loop = pred->loop_father; | |
230 | unsigned pred_loop_depth = loop_depth (pred_loop); | |
231 | bool pred_visited; | |
232 | ||
233 | /* We should have met DEF_BB along the way. */ | |
fefa31b5 | 234 | gcc_assert (pred != ENTRY_BLOCK_PTR_FOR_FN (cfun)); |
01273677 SB |
235 | |
236 | if (pred_loop_depth >= def_loop_depth) | |
237 | { | |
238 | if (pred_loop_depth > def_loop_depth) | |
239 | pred_loop = superloop_at_depth (pred_loop, def_loop_depth); | |
240 | /* If we've reached DEF_LOOP, our train ends here. */ | |
241 | if (pred_loop == def_loop) | |
242 | continue; | |
243 | } | |
244 | else if (! flow_loop_nested_p (pred_loop, def_loop)) | |
245 | pred = find_sibling_superloop (pred_loop, def_loop)->header; | |
246 | ||
247 | /* Add PRED to the LIVEIN set. PRED_VISITED is true if | |
248 | we had already added PRED to LIVEIN before. */ | |
249 | pred_visited = !bitmap_set_bit (live_exits, pred->index); | |
250 | ||
251 | /* If we have visited PRED before, don't add it to the worklist. | |
252 | If BB dominates PRED, then we're probably looking at a loop. | |
253 | We're only interested in looking up in the dominance tree | |
254 | because DEF_BB dominates all the uses. */ | |
255 | if (pred_visited || dominated_by_p (CDI_DOMINATORS, pred, bb)) | |
256 | continue; | |
257 | ||
9771b263 | 258 | worklist.quick_push (pred); |
01273677 SB |
259 | } |
260 | } | |
01273677 SB |
261 | |
262 | def_loop_exits = BITMAP_ALLOC (&loop_renamer_obstack); | |
263 | for (struct loop *loop = def_loop; | |
264 | loop != current_loops->tree_root; | |
265 | loop = loop_outer (loop)) | |
266 | bitmap_ior_into (def_loop_exits, loop_exits[loop->num]); | |
267 | bitmap_and_into (live_exits, def_loop_exits); | |
268 | BITMAP_FREE (def_loop_exits); | |
269 | } | |
270 | ||
271 | /* Add a loop-closing PHI for VAR in basic block EXIT. */ | |
272 | ||
273 | static void | |
274 | add_exit_phi (basic_block exit, tree var) | |
275 | { | |
538dd0b7 | 276 | gphi *phi; |
c913f08a | 277 | edge e; |
628f6a4e | 278 | edge_iterator ei; |
c913f08a | 279 | |
01273677 SB |
280 | #ifdef ENABLE_CHECKING |
281 | /* Check that at least one of the edges entering the EXIT block exits | |
282 | the loop, or a superloop of that loop, that VAR is defined in. */ | |
283 | gimple def_stmt = SSA_NAME_DEF_STMT (var); | |
284 | basic_block def_bb = gimple_bb (def_stmt); | |
628f6a4e | 285 | FOR_EACH_EDGE (e, ei, exit->preds) |
c913f08a | 286 | { |
01273677 SB |
287 | struct loop *aloop = find_common_loop (def_bb->loop_father, |
288 | e->src->loop_father); | |
289 | if (!flow_bb_inside_loop_p (aloop, e->dest)) | |
c913f08a ZD |
290 | break; |
291 | } | |
292 | ||
01273677 SB |
293 | gcc_checking_assert (e); |
294 | #endif | |
c913f08a | 295 | |
dcc748dd | 296 | phi = create_phi_node (NULL_TREE, exit); |
01273677 | 297 | create_new_def_for (var, phi, gimple_phi_result_ptr (phi)); |
628f6a4e | 298 | FOR_EACH_EDGE (e, ei, exit->preds) |
01273677 SB |
299 | add_phi_arg (phi, var, e, UNKNOWN_LOCATION); |
300 | ||
301 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
302 | { | |
303 | fprintf (dump_file, ";; Created LCSSA PHI: "); | |
304 | print_gimple_stmt (dump_file, phi, 0, dump_flags); | |
305 | } | |
c913f08a ZD |
306 | } |
307 | ||
308 | /* Add exit phis for VAR that is used in LIVEIN. | |
01273677 | 309 | Exits of the loops are stored in LOOP_EXITS. */ |
c913f08a ZD |
310 | |
311 | static void | |
01273677 | 312 | add_exit_phis_var (tree var, bitmap use_blocks, bitmap *loop_exits) |
c913f08a | 313 | { |
3cd8c58a | 314 | unsigned index; |
87c476a2 | 315 | bitmap_iterator bi; |
01273677 SB |
316 | basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var)); |
317 | bitmap live_exits = BITMAP_ALLOC (&loop_renamer_obstack); | |
c913f08a | 318 | |
ceb16be3 | 319 | gcc_checking_assert (! bitmap_bit_p (use_blocks, def_bb->index)); |
c913f08a | 320 | |
01273677 | 321 | compute_live_loop_exits (live_exits, use_blocks, loop_exits, def_bb); |
c913f08a | 322 | |
01273677 | 323 | EXECUTE_IF_SET_IN_BITMAP (live_exits, 0, index, bi) |
87c476a2 | 324 | { |
06e28de2 | 325 | add_exit_phi (BASIC_BLOCK_FOR_FN (cfun, index), var); |
87c476a2 | 326 | } |
c302207e | 327 | |
01273677 | 328 | BITMAP_FREE (live_exits); |
c913f08a ZD |
329 | } |
330 | ||
331 | /* Add exit phis for the names marked in NAMES_TO_RENAME. | |
332 | Exits of the loops are stored in EXITS. Sets of blocks where the ssa | |
333 | names are used are stored in USE_BLOCKS. */ | |
334 | ||
335 | static void | |
01273677 | 336 | add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap *loop_exits) |
c913f08a ZD |
337 | { |
338 | unsigned i; | |
87c476a2 | 339 | bitmap_iterator bi; |
c913f08a | 340 | |
87c476a2 | 341 | EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi) |
c913f08a ZD |
342 | { |
343 | add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits); | |
87c476a2 | 344 | } |
c913f08a ZD |
345 | } |
346 | ||
01273677 | 347 | /* Fill the array of bitmaps LOOP_EXITS with all loop exit edge targets. */ |
c913f08a | 348 | |
01273677 SB |
349 | static void |
350 | get_loops_exits (bitmap *loop_exits) | |
c913f08a | 351 | { |
01273677 SB |
352 | struct loop *loop; |
353 | unsigned j; | |
c913f08a ZD |
354 | edge e; |
355 | ||
f0bd40b1 | 356 | FOR_EACH_LOOP (loop, 0) |
c913f08a | 357 | { |
9771b263 | 358 | vec<edge> exit_edges = get_loop_exit_edges (loop); |
01273677 | 359 | loop_exits[loop->num] = BITMAP_ALLOC (&loop_renamer_obstack); |
9771b263 | 360 | FOR_EACH_VEC_ELT (exit_edges, j, e) |
01273677 | 361 | bitmap_set_bit (loop_exits[loop->num], e->dest->index); |
9771b263 | 362 | exit_edges.release (); |
c913f08a | 363 | } |
c913f08a ZD |
364 | } |
365 | ||
366 | /* For USE in BB, if it is used outside of the loop it is defined in, | |
367 | mark it for rewrite. Record basic block BB where it is used | |
84d65814 | 368 | to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap. */ |
c913f08a ZD |
369 | |
370 | static void | |
84d65814 DN |
371 | find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks, |
372 | bitmap need_phis) | |
c913f08a ZD |
373 | { |
374 | unsigned ver; | |
375 | basic_block def_bb; | |
376 | struct loop *def_loop; | |
377 | ||
378 | if (TREE_CODE (use) != SSA_NAME) | |
379 | return; | |
380 | ||
381 | ver = SSA_NAME_VERSION (use); | |
726a989a | 382 | def_bb = gimple_bb (SSA_NAME_DEF_STMT (use)); |
c913f08a ZD |
383 | if (!def_bb) |
384 | return; | |
385 | def_loop = def_bb->loop_father; | |
386 | ||
d6e840ee | 387 | /* If the definition is not inside a loop, it is not interesting. */ |
9ba025a2 | 388 | if (!loop_outer (def_loop)) |
c913f08a ZD |
389 | return; |
390 | ||
d6e840ee RG |
391 | /* If the use is not outside of the loop it is defined in, it is not |
392 | interesting. */ | |
393 | if (flow_bb_inside_loop_p (def_loop, bb)) | |
394 | return; | |
395 | ||
c302207e SB |
396 | /* If we're seeing VER for the first time, we still have to allocate |
397 | a bitmap for its uses. */ | |
398 | if (bitmap_set_bit (need_phis, ver)) | |
399 | use_blocks[ver] = BITMAP_ALLOC (&loop_renamer_obstack); | |
c913f08a | 400 | bitmap_set_bit (use_blocks[ver], bb->index); |
c913f08a ZD |
401 | } |
402 | ||
403 | /* For uses in STMT, mark names that are used outside of the loop they are | |
404 | defined to rewrite. Record the set of blocks in that the ssa | |
84d65814 DN |
405 | names are defined to USE_BLOCKS and the ssa names themselves to |
406 | NEED_PHIS. */ | |
c913f08a ZD |
407 | |
408 | static void | |
726a989a | 409 | find_uses_to_rename_stmt (gimple stmt, bitmap *use_blocks, bitmap need_phis) |
c913f08a | 410 | { |
4c124b4c AM |
411 | ssa_op_iter iter; |
412 | tree var; | |
726a989a | 413 | basic_block bb = gimple_bb (stmt); |
c913f08a | 414 | |
b5b8b0ac AO |
415 | if (is_gimple_debug (stmt)) |
416 | return; | |
417 | ||
636f59cf | 418 | FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) |
84d65814 | 419 | find_uses_to_rename_use (bb, var, use_blocks, need_phis); |
c913f08a ZD |
420 | } |
421 | ||
2b271002 ZD |
422 | /* Marks names that are used in BB and outside of the loop they are |
423 | defined in for rewrite. Records the set of blocks in that the ssa | |
84d65814 DN |
424 | names are defined to USE_BLOCKS. Record the SSA names that will |
425 | need exit PHIs in NEED_PHIS. */ | |
c913f08a ZD |
426 | |
427 | static void | |
84d65814 | 428 | find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis) |
c913f08a | 429 | { |
2b271002 ZD |
430 | edge e; |
431 | edge_iterator ei; | |
c913f08a | 432 | |
2b271002 | 433 | FOR_EACH_EDGE (e, ei, bb->succs) |
538dd0b7 DM |
434 | for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); |
435 | gsi_next (&bsi)) | |
01273677 | 436 | { |
538dd0b7 | 437 | gphi *phi = bsi.phi (); |
636f59cf RB |
438 | if (! virtual_operand_p (gimple_phi_result (phi))) |
439 | find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e), | |
440 | use_blocks, need_phis); | |
01273677 | 441 | } |
b8698a0f | 442 | |
538dd0b7 DM |
443 | for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); |
444 | gsi_next (&bsi)) | |
726a989a | 445 | find_uses_to_rename_stmt (gsi_stmt (bsi), use_blocks, need_phis); |
2b271002 | 446 | } |
b8698a0f | 447 | |
2b271002 ZD |
448 | /* Marks names that are used outside of the loop they are defined in |
449 | for rewrite. Records the set of blocks in that the ssa | |
450 | names are defined to USE_BLOCKS. If CHANGED_BBS is not NULL, | |
451 | scan only blocks in this set. */ | |
452 | ||
453 | static void | |
84d65814 | 454 | find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis) |
2b271002 ZD |
455 | { |
456 | basic_block bb; | |
457 | unsigned index; | |
458 | bitmap_iterator bi; | |
c913f08a | 459 | |
789c34e3 RB |
460 | if (changed_bbs) |
461 | EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi) | |
06e28de2 | 462 | find_uses_to_rename_bb (BASIC_BLOCK_FOR_FN (cfun, index), use_blocks, need_phis); |
2b271002 | 463 | else |
11cd3bed | 464 | FOR_EACH_BB_FN (bb, cfun) |
789c34e3 | 465 | find_uses_to_rename_bb (bb, use_blocks, need_phis); |
c913f08a ZD |
466 | } |
467 | ||
468 | /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra | |
469 | phi nodes to ensure that no variable is used outside the loop it is | |
470 | defined in. | |
471 | ||
472 | This strengthening of the basic ssa form has several advantages: | |
473 | ||
474 | 1) Updating it during unrolling/peeling/versioning is trivial, since | |
475 | we do not need to care about the uses outside of the loop. | |
ceb16be3 RG |
476 | The same applies to virtual operands which are also rewritten into |
477 | loop closed SSA form. Note that virtual operands are always live | |
478 | until function exit. | |
c913f08a ZD |
479 | 2) The behavior of all uses of an induction variable is the same. |
480 | Without this, you need to distinguish the case when the variable | |
481 | is used outside of the loop it is defined in, for example | |
482 | ||
483 | for (i = 0; i < 100; i++) | |
484 | { | |
485 | for (j = 0; j < 100; j++) | |
486 | { | |
487 | k = i + j; | |
488 | use1 (k); | |
489 | } | |
490 | use2 (k); | |
491 | } | |
492 | ||
493 | Looking from the outer loop with the normal SSA form, the first use of k | |
494 | is not well-behaved, while the second one is an induction variable with | |
2b271002 | 495 | base 99 and step 1. |
b8698a0f | 496 | |
2b271002 | 497 | If CHANGED_BBS is not NULL, we look for uses outside loops only in |
84d65814 DN |
498 | the basic blocks in this set. |
499 | ||
500 | UPDATE_FLAG is used in the call to update_ssa. See | |
501 | TODO_update_ssa* for documentation. */ | |
c913f08a ZD |
502 | |
503 | void | |
84d65814 | 504 | rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag) |
c913f08a | 505 | { |
c913f08a | 506 | bitmap *use_blocks; |
c7b852c8 ZD |
507 | bitmap names_to_rename; |
508 | ||
f87000d0 | 509 | loops_state_set (LOOP_CLOSED_SSA); |
0fc822d0 | 510 | if (number_of_loops (cfun) <= 1) |
c7b852c8 ZD |
511 | return; |
512 | ||
01273677 SB |
513 | /* If the pass has caused the SSA form to be out-of-date, update it |
514 | now. */ | |
515 | update_ssa (update_flag); | |
516 | ||
c302207e SB |
517 | bitmap_obstack_initialize (&loop_renamer_obstack); |
518 | ||
c302207e | 519 | names_to_rename = BITMAP_ALLOC (&loop_renamer_obstack); |
c913f08a | 520 | |
c302207e SB |
521 | /* Uses of names to rename. We don't have to initialize this array, |
522 | because we know that we will only have entries for the SSA names | |
523 | in NAMES_TO_RENAME. */ | |
0fc4dd09 | 524 | use_blocks = XNEWVEC (bitmap, num_ssa_names); |
c913f08a ZD |
525 | |
526 | /* Find the uses outside loops. */ | |
84d65814 | 527 | find_uses_to_rename (changed_bbs, use_blocks, names_to_rename); |
2b271002 | 528 | |
3d741091 RB |
529 | if (!bitmap_empty_p (names_to_rename)) |
530 | { | |
531 | /* An array of bitmaps where LOOP_EXITS[I] is the set of basic blocks | |
532 | that are the destination of an edge exiting loop number I. */ | |
0fc822d0 | 533 | bitmap *loop_exits = XNEWVEC (bitmap, number_of_loops (cfun)); |
3d741091 RB |
534 | get_loops_exits (loop_exits); |
535 | ||
536 | /* Add the PHI nodes on exits of the loops for the names we need to | |
537 | rewrite. */ | |
538 | add_exit_phis (names_to_rename, use_blocks, loop_exits); | |
539 | ||
540 | free (loop_exits); | |
541 | ||
542 | /* Fix up all the names found to be used outside their original | |
543 | loops. */ | |
544 | update_ssa (TODO_update_ssa); | |
545 | } | |
c913f08a | 546 | |
c302207e | 547 | bitmap_obstack_release (&loop_renamer_obstack); |
c913f08a | 548 | free (use_blocks); |
c913f08a ZD |
549 | } |
550 | ||
338392ed TV |
551 | /* Replace uses of OLD_VAL with NEW_VAL in bbs dominated by BB. */ |
552 | ||
553 | static void | |
554 | replace_uses_in_dominated_bbs (tree old_val, tree new_val, basic_block bb) | |
555 | { | |
556 | gimple use_stmt; | |
557 | imm_use_iterator imm_iter; | |
558 | ||
559 | FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, old_val) | |
560 | { | |
561 | if (!dominated_by_p (CDI_DOMINATORS, gimple_bb (use_stmt), bb)) | |
562 | continue; | |
563 | ||
564 | use_operand_p use_p; | |
565 | FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) | |
566 | SET_USE (use_p, new_val); | |
567 | } | |
568 | } | |
569 | ||
570 | /* Ensure a virtual phi is present in the exit block, if LOOP contains a vdef. | |
571 | In other words, ensure loop-closed ssa normal form for virtuals. Handles | |
572 | only loops with a single exit that dominates the latch. */ | |
573 | ||
574 | void | |
575 | rewrite_virtuals_into_loop_closed_ssa (struct loop *loop) | |
576 | { | |
577 | gphi *phi; | |
578 | /* TODO: Handle !single_dom_exit loops. */ | |
579 | edge exit = single_dom_exit (loop); | |
580 | gcc_assert (exit != NULL); | |
581 | ||
582 | phi = get_virtual_phi (loop->header); | |
583 | if (phi == NULL) | |
584 | return; | |
585 | ||
586 | tree final_loop = PHI_ARG_DEF_FROM_EDGE (phi, single_succ_edge (loop->latch)); | |
587 | ||
588 | phi = get_virtual_phi (exit->dest); | |
589 | if (phi != NULL) | |
590 | { | |
591 | tree final_exit = PHI_ARG_DEF_FROM_EDGE (phi, exit); | |
592 | gcc_assert (operand_equal_p (final_loop, final_exit, 0)); | |
593 | return; | |
594 | } | |
595 | ||
596 | tree res_new = copy_ssa_name (final_loop, NULL); | |
597 | gphi *nphi = create_phi_node (res_new, exit->dest); | |
598 | replace_uses_in_dominated_bbs (final_loop, res_new, exit->dest); | |
599 | add_phi_arg (nphi, final_loop, exit, UNKNOWN_LOCATION); | |
600 | } | |
601 | ||
c913f08a ZD |
602 | /* Check invariants of the loop closed ssa form for the USE in BB. */ |
603 | ||
604 | static void | |
605 | check_loop_closed_ssa_use (basic_block bb, tree use) | |
606 | { | |
726a989a | 607 | gimple def; |
c913f08a | 608 | basic_block def_bb; |
b8698a0f | 609 | |
ea057359 | 610 | if (TREE_CODE (use) != SSA_NAME || virtual_operand_p (use)) |
c913f08a ZD |
611 | return; |
612 | ||
613 | def = SSA_NAME_DEF_STMT (use); | |
726a989a | 614 | def_bb = gimple_bb (def); |
1e128c5f GB |
615 | gcc_assert (!def_bb |
616 | || flow_bb_inside_loop_p (def_bb->loop_father, bb)); | |
c913f08a ZD |
617 | } |
618 | ||
619 | /* Checks invariants of loop closed ssa form in statement STMT in BB. */ | |
620 | ||
621 | static void | |
726a989a | 622 | check_loop_closed_ssa_stmt (basic_block bb, gimple stmt) |
c913f08a | 623 | { |
4c124b4c AM |
624 | ssa_op_iter iter; |
625 | tree var; | |
c913f08a | 626 | |
b5b8b0ac AO |
627 | if (is_gimple_debug (stmt)) |
628 | return; | |
629 | ||
c302207e | 630 | FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) |
4c124b4c | 631 | check_loop_closed_ssa_use (bb, var); |
c913f08a ZD |
632 | } |
633 | ||
a3b9e73c SP |
634 | /* Checks that invariants of the loop closed ssa form are preserved. |
635 | Call verify_ssa when VERIFY_SSA_P is true. */ | |
c913f08a | 636 | |
24e47c76 | 637 | DEBUG_FUNCTION void |
a3b9e73c | 638 | verify_loop_closed_ssa (bool verify_ssa_p) |
c913f08a ZD |
639 | { |
640 | basic_block bb; | |
726a989a RB |
641 | edge e; |
642 | edge_iterator ei; | |
c913f08a | 643 | |
0fc822d0 | 644 | if (number_of_loops (cfun) <= 1) |
84d65814 DN |
645 | return; |
646 | ||
a3b9e73c | 647 | if (verify_ssa_p) |
e9ff9caf | 648 | verify_ssa (false, true); |
c913f08a | 649 | |
a222c01a MM |
650 | timevar_push (TV_VERIFY_LOOP_CLOSED); |
651 | ||
11cd3bed | 652 | FOR_EACH_BB_FN (bb, cfun) |
c913f08a | 653 | { |
538dd0b7 DM |
654 | for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi); |
655 | gsi_next (&bsi)) | |
726a989a | 656 | { |
538dd0b7 | 657 | gphi *phi = bsi.phi (); |
726a989a RB |
658 | FOR_EACH_EDGE (e, ei, bb->preds) |
659 | check_loop_closed_ssa_use (e->src, | |
660 | PHI_ARG_DEF_FROM_EDGE (phi, e)); | |
661 | } | |
c913f08a | 662 | |
538dd0b7 DM |
663 | for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); |
664 | gsi_next (&bsi)) | |
726a989a | 665 | check_loop_closed_ssa_stmt (bb, gsi_stmt (bsi)); |
c913f08a | 666 | } |
a222c01a MM |
667 | |
668 | timevar_pop (TV_VERIFY_LOOP_CLOSED); | |
c913f08a | 669 | } |
8b11a64c ZD |
670 | |
671 | /* Split loop exit edge EXIT. The things are a bit complicated by a need to | |
5f40b3cb | 672 | preserve the loop closed ssa form. The newly created block is returned. */ |
8b11a64c | 673 | |
5f40b3cb | 674 | basic_block |
8b11a64c ZD |
675 | split_loop_exit_edge (edge exit) |
676 | { | |
677 | basic_block dest = exit->dest; | |
598ec7bd | 678 | basic_block bb = split_edge (exit); |
538dd0b7 | 679 | gphi *phi, *new_phi; |
726a989a | 680 | tree new_name, name; |
8b11a64c | 681 | use_operand_p op_p; |
538dd0b7 | 682 | gphi_iterator psi; |
f5045c96 | 683 | source_location locus; |
8b11a64c | 684 | |
726a989a | 685 | for (psi = gsi_start_phis (dest); !gsi_end_p (psi); gsi_next (&psi)) |
8b11a64c | 686 | { |
538dd0b7 | 687 | phi = psi.phi (); |
c5cbcccf | 688 | op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb)); |
f5045c96 | 689 | locus = gimple_phi_arg_location_from_edge (phi, single_succ_edge (bb)); |
8b11a64c | 690 | |
7fac6722 ZD |
691 | name = USE_FROM_PTR (op_p); |
692 | ||
38635499 | 693 | /* If the argument of the PHI node is a constant, we do not need |
7fac6722 ZD |
694 | to keep it inside loop. */ |
695 | if (TREE_CODE (name) != SSA_NAME) | |
696 | continue; | |
697 | ||
698 | /* Otherwise create an auxiliary phi node that will copy the value | |
38635499 | 699 | of the SSA name out of the loop. */ |
7fac6722 | 700 | new_name = duplicate_ssa_name (name, NULL); |
8b11a64c | 701 | new_phi = create_phi_node (new_name, bb); |
9e227d60 | 702 | add_phi_arg (new_phi, name, exit, locus); |
8b11a64c ZD |
703 | SET_USE (op_p, new_name); |
704 | } | |
5f40b3cb ZD |
705 | |
706 | return bb; | |
8b11a64c ZD |
707 | } |
708 | ||
8b11a64c ZD |
709 | /* Returns the basic block in that statements should be emitted for induction |
710 | variables incremented at the end of the LOOP. */ | |
711 | ||
712 | basic_block | |
713 | ip_end_pos (struct loop *loop) | |
714 | { | |
715 | return loop->latch; | |
716 | } | |
717 | ||
718 | /* Returns the basic block in that statements should be emitted for induction | |
719 | variables incremented just before exit condition of a LOOP. */ | |
720 | ||
721 | basic_block | |
722 | ip_normal_pos (struct loop *loop) | |
723 | { | |
726a989a | 724 | gimple last; |
8b11a64c ZD |
725 | basic_block bb; |
726 | edge exit; | |
727 | ||
c5cbcccf | 728 | if (!single_pred_p (loop->latch)) |
8b11a64c ZD |
729 | return NULL; |
730 | ||
c5cbcccf | 731 | bb = single_pred (loop->latch); |
8b11a64c | 732 | last = last_stmt (bb); |
ae2cf11b | 733 | if (!last |
726a989a | 734 | || gimple_code (last) != GIMPLE_COND) |
8b11a64c ZD |
735 | return NULL; |
736 | ||
628f6a4e | 737 | exit = EDGE_SUCC (bb, 0); |
8b11a64c | 738 | if (exit->dest == loop->latch) |
628f6a4e | 739 | exit = EDGE_SUCC (bb, 1); |
8b11a64c ZD |
740 | |
741 | if (flow_bb_inside_loop_p (loop, exit->dest)) | |
742 | return NULL; | |
743 | ||
744 | return bb; | |
745 | } | |
746 | ||
747 | /* Stores the standard position for induction variable increment in LOOP | |
748 | (just before the exit condition if it is available and latch block is empty, | |
749 | end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if | |
750 | the increment should be inserted after *BSI. */ | |
751 | ||
752 | void | |
726a989a | 753 | standard_iv_increment_position (struct loop *loop, gimple_stmt_iterator *bsi, |
8b11a64c ZD |
754 | bool *insert_after) |
755 | { | |
756 | basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop); | |
726a989a | 757 | gimple last = last_stmt (latch); |
8b11a64c ZD |
758 | |
759 | if (!bb | |
726a989a | 760 | || (last && gimple_code (last) != GIMPLE_LABEL)) |
8b11a64c | 761 | { |
726a989a | 762 | *bsi = gsi_last_bb (latch); |
8b11a64c ZD |
763 | *insert_after = true; |
764 | } | |
765 | else | |
766 | { | |
726a989a | 767 | *bsi = gsi_last_bb (bb); |
8b11a64c ZD |
768 | *insert_after = false; |
769 | } | |
770 | } | |
92fc4a2f ZD |
771 | |
772 | /* Copies phi node arguments for duplicated blocks. The index of the first | |
773 | duplicated block is FIRST_NEW_BLOCK. */ | |
774 | ||
775 | static void | |
776 | copy_phi_node_args (unsigned first_new_block) | |
777 | { | |
778 | unsigned i; | |
779 | ||
8b1c6fd7 | 780 | for (i = first_new_block; i < (unsigned) last_basic_block_for_fn (cfun); i++) |
06e28de2 | 781 | BASIC_BLOCK_FOR_FN (cfun, i)->flags |= BB_DUPLICATED; |
92fc4a2f | 782 | |
8b1c6fd7 | 783 | for (i = first_new_block; i < (unsigned) last_basic_block_for_fn (cfun); i++) |
06e28de2 | 784 | add_phi_args_after_copy_bb (BASIC_BLOCK_FOR_FN (cfun, i)); |
92fc4a2f | 785 | |
8b1c6fd7 | 786 | for (i = first_new_block; i < (unsigned) last_basic_block_for_fn (cfun); i++) |
06e28de2 | 787 | BASIC_BLOCK_FOR_FN (cfun, i)->flags &= ~BB_DUPLICATED; |
92fc4a2f ZD |
788 | } |
789 | ||
92fc4a2f | 790 | |
84d65814 DN |
791 | /* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also |
792 | updates the PHI nodes at start of the copied region. In order to | |
793 | achieve this, only loops whose exits all lead to the same location | |
794 | are handled. | |
92fc4a2f | 795 | |
84d65814 DN |
796 | Notice that we do not completely update the SSA web after |
797 | duplication. The caller is responsible for calling update_ssa | |
798 | after the loop has been duplicated. */ | |
92fc4a2f ZD |
799 | |
800 | bool | |
726a989a | 801 | gimple_duplicate_loop_to_header_edge (struct loop *loop, edge e, |
92fc4a2f | 802 | unsigned int ndupl, sbitmap wont_exit, |
9771b263 | 803 | edge orig, vec<edge> *to_remove, |
ee8c1b05 | 804 | int flags) |
92fc4a2f ZD |
805 | { |
806 | unsigned first_new_block; | |
92fc4a2f | 807 | |
f87000d0 | 808 | if (!loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES)) |
92fc4a2f | 809 | return false; |
f87000d0 | 810 | if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)) |
92fc4a2f ZD |
811 | return false; |
812 | ||
8b1c6fd7 | 813 | first_new_block = last_basic_block_for_fn (cfun); |
d73be268 | 814 | if (!duplicate_loop_to_header_edge (loop, e, ndupl, wont_exit, |
ee8c1b05 | 815 | orig, to_remove, flags)) |
92fc4a2f ZD |
816 | return false; |
817 | ||
818 | /* Readd the removed phi args for e. */ | |
71882046 | 819 | flush_pending_stmts (e); |
92fc4a2f ZD |
820 | |
821 | /* Copy the phi node arguments. */ | |
822 | copy_phi_node_args (first_new_block); | |
823 | ||
92fc4a2f | 824 | scev_reset (); |
92fc4a2f ZD |
825 | |
826 | return true; | |
827 | } | |
17684618 | 828 | |
17684618 ZD |
829 | /* Returns true if we can unroll LOOP FACTOR times. Number |
830 | of iterations of the loop is returned in NITER. */ | |
831 | ||
832 | bool | |
833 | can_unroll_loop_p (struct loop *loop, unsigned factor, | |
834 | struct tree_niter_desc *niter) | |
835 | { | |
836 | edge exit; | |
837 | ||
838 | /* Check whether unrolling is possible. We only want to unroll loops | |
839 | for that we are able to determine number of iterations. We also | |
840 | want to split the extra iterations of the loop from its end, | |
841 | therefore we require that the loop has precisely one | |
842 | exit. */ | |
843 | ||
844 | exit = single_dom_exit (loop); | |
845 | if (!exit) | |
846 | return false; | |
847 | ||
848 | if (!number_of_iterations_exit (loop, exit, niter, false) | |
bf8dbe38 ZD |
849 | || niter->cmp == ERROR_MARK |
850 | /* Scalar evolutions analysis might have copy propagated | |
851 | the abnormal ssa names into these expressions, hence | |
2f8e468b | 852 | emitting the computations based on them during loop |
bf8dbe38 ZD |
853 | unrolling might create overlapping life ranges for |
854 | them, and failures in out-of-ssa. */ | |
855 | || contains_abnormal_ssa_name_p (niter->may_be_zero) | |
856 | || contains_abnormal_ssa_name_p (niter->control.base) | |
857 | || contains_abnormal_ssa_name_p (niter->control.step) | |
858 | || contains_abnormal_ssa_name_p (niter->bound)) | |
17684618 ZD |
859 | return false; |
860 | ||
861 | /* And of course, we must be able to duplicate the loop. */ | |
862 | if (!can_duplicate_loop_p (loop)) | |
863 | return false; | |
864 | ||
865 | /* The final loop should be small enough. */ | |
7f9bc51b | 866 | if (tree_num_loop_insns (loop, &eni_size_weights) * factor |
17684618 ZD |
867 | > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS)) |
868 | return false; | |
869 | ||
870 | return true; | |
871 | } | |
872 | ||
873 | /* Determines the conditions that control execution of LOOP unrolled FACTOR | |
874 | times. DESC is number of iterations of LOOP. ENTER_COND is set to | |
875 | condition that must be true if the main loop can be entered. | |
876 | EXIT_BASE, EXIT_STEP, EXIT_CMP and EXIT_BOUND are set to values describing | |
877 | how the exit from the unrolled loop should be controlled. */ | |
878 | ||
879 | static void | |
880 | determine_exit_conditions (struct loop *loop, struct tree_niter_desc *desc, | |
881 | unsigned factor, tree *enter_cond, | |
882 | tree *exit_base, tree *exit_step, | |
883 | enum tree_code *exit_cmp, tree *exit_bound) | |
884 | { | |
726a989a | 885 | gimple_seq stmts; |
17684618 ZD |
886 | tree base = desc->control.base; |
887 | tree step = desc->control.step; | |
888 | tree bound = desc->bound; | |
d24a32a1 | 889 | tree type = TREE_TYPE (step); |
17684618 ZD |
890 | tree bigstep, delta; |
891 | tree min = lower_bound_in_type (type, type); | |
892 | tree max = upper_bound_in_type (type, type); | |
893 | enum tree_code cmp = desc->cmp; | |
894 | tree cond = boolean_true_node, assum; | |
895 | ||
0d82a1c8 | 896 | /* For pointers, do the arithmetics in the type of step. */ |
d24a32a1 ZD |
897 | base = fold_convert (type, base); |
898 | bound = fold_convert (type, bound); | |
899 | ||
17684618 ZD |
900 | *enter_cond = boolean_false_node; |
901 | *exit_base = NULL_TREE; | |
902 | *exit_step = NULL_TREE; | |
903 | *exit_cmp = ERROR_MARK; | |
904 | *exit_bound = NULL_TREE; | |
905 | gcc_assert (cmp != ERROR_MARK); | |
906 | ||
907 | /* We only need to be correct when we answer question | |
908 | "Do at least FACTOR more iterations remain?" in the unrolled loop. | |
909 | Thus, transforming BASE + STEP * i <> BOUND to | |
910 | BASE + STEP * i < BOUND is ok. */ | |
911 | if (cmp == NE_EXPR) | |
912 | { | |
913 | if (tree_int_cst_sign_bit (step)) | |
914 | cmp = GT_EXPR; | |
915 | else | |
916 | cmp = LT_EXPR; | |
917 | } | |
918 | else if (cmp == LT_EXPR) | |
919 | { | |
920 | gcc_assert (!tree_int_cst_sign_bit (step)); | |
921 | } | |
922 | else if (cmp == GT_EXPR) | |
923 | { | |
924 | gcc_assert (tree_int_cst_sign_bit (step)); | |
925 | } | |
926 | else | |
927 | gcc_unreachable (); | |
928 | ||
929 | /* The main body of the loop may be entered iff: | |
930 | ||
931 | 1) desc->may_be_zero is false. | |
932 | 2) it is possible to check that there are at least FACTOR iterations | |
933 | of the loop, i.e., BOUND - step * FACTOR does not overflow. | |
934 | 3) # of iterations is at least FACTOR */ | |
935 | ||
6e682d7e | 936 | if (!integer_zerop (desc->may_be_zero)) |
17684618 ZD |
937 | cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, |
938 | invert_truthvalue (desc->may_be_zero), | |
939 | cond); | |
940 | ||
941 | bigstep = fold_build2 (MULT_EXPR, type, step, | |
942 | build_int_cst_type (type, factor)); | |
943 | delta = fold_build2 (MINUS_EXPR, type, bigstep, step); | |
944 | if (cmp == LT_EXPR) | |
945 | assum = fold_build2 (GE_EXPR, boolean_type_node, | |
946 | bound, | |
947 | fold_build2 (PLUS_EXPR, type, min, delta)); | |
948 | else | |
949 | assum = fold_build2 (LE_EXPR, boolean_type_node, | |
950 | bound, | |
951 | fold_build2 (PLUS_EXPR, type, max, delta)); | |
952 | cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond); | |
953 | ||
954 | bound = fold_build2 (MINUS_EXPR, type, bound, delta); | |
955 | assum = fold_build2 (cmp, boolean_type_node, base, bound); | |
956 | cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond); | |
957 | ||
958 | cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE); | |
959 | if (stmts) | |
726a989a | 960 | gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts); |
17684618 ZD |
961 | /* cond now may be a gimple comparison, which would be OK, but also any |
962 | other gimple rhs (say a && b). In this case we need to force it to | |
963 | operand. */ | |
964 | if (!is_gimple_condexpr (cond)) | |
965 | { | |
966 | cond = force_gimple_operand (cond, &stmts, true, NULL_TREE); | |
967 | if (stmts) | |
726a989a | 968 | gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts); |
17684618 ZD |
969 | } |
970 | *enter_cond = cond; | |
971 | ||
972 | base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE); | |
973 | if (stmts) | |
726a989a | 974 | gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts); |
17684618 ZD |
975 | bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE); |
976 | if (stmts) | |
726a989a | 977 | gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts); |
17684618 ZD |
978 | |
979 | *exit_base = base; | |
980 | *exit_step = bigstep; | |
981 | *exit_cmp = cmp; | |
982 | *exit_bound = bound; | |
983 | } | |
984 | ||
14fa2cc0 ZD |
985 | /* Scales the frequencies of all basic blocks in LOOP that are strictly |
986 | dominated by BB by NUM/DEN. */ | |
987 | ||
988 | static void | |
989 | scale_dominated_blocks_in_loop (struct loop *loop, basic_block bb, | |
990 | int num, int den) | |
991 | { | |
992 | basic_block son; | |
993 | ||
994 | if (den == 0) | |
995 | return; | |
996 | ||
997 | for (son = first_dom_son (CDI_DOMINATORS, bb); | |
998 | son; | |
999 | son = next_dom_son (CDI_DOMINATORS, son)) | |
1000 | { | |
1001 | if (!flow_bb_inside_loop_p (loop, son)) | |
1002 | continue; | |
1003 | scale_bbs_frequencies_int (&son, 1, num, den); | |
1004 | scale_dominated_blocks_in_loop (loop, son, num, den); | |
1005 | } | |
1006 | } | |
1007 | ||
d73be268 ZD |
1008 | /* Unroll LOOP FACTOR times. DESC describes number of iterations of LOOP. |
1009 | EXIT is the exit of the loop to that DESC corresponds. | |
1010 | ||
17684618 ZD |
1011 | If N is number of iterations of the loop and MAY_BE_ZERO is the condition |
1012 | under that loop exits in the first iteration even if N != 0, | |
b8698a0f | 1013 | |
17684618 ZD |
1014 | while (1) |
1015 | { | |
1016 | x = phi (init, next); | |
1017 | ||
1018 | pre; | |
1019 | if (st) | |
1020 | break; | |
1021 | post; | |
1022 | } | |
1023 | ||
1024 | becomes (with possibly the exit conditions formulated a bit differently, | |
1025 | avoiding the need to create a new iv): | |
b8698a0f | 1026 | |
17684618 ZD |
1027 | if (MAY_BE_ZERO || N < FACTOR) |
1028 | goto rest; | |
1029 | ||
1030 | do | |
1031 | { | |
1032 | x = phi (init, next); | |
1033 | ||
1034 | pre; | |
1035 | post; | |
1036 | pre; | |
1037 | post; | |
1038 | ... | |
1039 | pre; | |
1040 | post; | |
1041 | N -= FACTOR; | |
b8698a0f | 1042 | |
17684618 ZD |
1043 | } while (N >= FACTOR); |
1044 | ||
1045 | rest: | |
1046 | init' = phi (init, x); | |
1047 | ||
1048 | while (1) | |
1049 | { | |
1050 | x = phi (init', next); | |
1051 | ||
1052 | pre; | |
1053 | if (st) | |
1054 | break; | |
1055 | post; | |
567b96ed | 1056 | } |
b8698a0f | 1057 | |
567b96ed ZD |
1058 | Before the loop is unrolled, TRANSFORM is called for it (only for the |
1059 | unrolled loop, but not for its versioned copy). DATA is passed to | |
1060 | TRANSFORM. */ | |
17684618 | 1061 | |
03cb2019 ZD |
1062 | /* Probability in % that the unrolled loop is entered. Just a guess. */ |
1063 | #define PROB_UNROLLED_LOOP_ENTERED 90 | |
1064 | ||
17684618 | 1065 | void |
567b96ed ZD |
1066 | tree_transform_and_unroll_loop (struct loop *loop, unsigned factor, |
1067 | edge exit, struct tree_niter_desc *desc, | |
1068 | transform_callback transform, | |
1069 | void *data) | |
17684618 | 1070 | { |
538dd0b7 | 1071 | gcond *exit_if; |
726a989a | 1072 | tree ctr_before, ctr_after; |
17684618 ZD |
1073 | tree enter_main_cond, exit_base, exit_step, exit_bound; |
1074 | enum tree_code exit_cmp; | |
538dd0b7 DM |
1075 | gphi *phi_old_loop, *phi_new_loop, *phi_rest; |
1076 | gphi_iterator psi_old_loop, psi_new_loop; | |
70b5e7dc | 1077 | tree init, next, new_init; |
17684618 ZD |
1078 | struct loop *new_loop; |
1079 | basic_block rest, exit_bb; | |
1080 | edge old_entry, new_entry, old_latch, precond_edge, new_exit; | |
14fa2cc0 | 1081 | edge new_nonexit, e; |
726a989a | 1082 | gimple_stmt_iterator bsi; |
17684618 ZD |
1083 | use_operand_p op; |
1084 | bool ok; | |
03cb2019 | 1085 | unsigned est_niter, prob_entry, scale_unrolled, scale_rest, freq_e, freq_h; |
14fa2cc0 | 1086 | unsigned new_est_niter, i, prob; |
8e08deeb | 1087 | unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP; |
17684618 | 1088 | sbitmap wont_exit; |
ef062b13 | 1089 | auto_vec<edge> to_remove; |
17684618 ZD |
1090 | |
1091 | est_niter = expected_loop_iterations (loop); | |
1092 | determine_exit_conditions (loop, desc, factor, | |
1093 | &enter_main_cond, &exit_base, &exit_step, | |
1094 | &exit_cmp, &exit_bound); | |
1095 | ||
03cb2019 ZD |
1096 | /* Let us assume that the unrolled loop is quite likely to be entered. */ |
1097 | if (integer_nonzerop (enter_main_cond)) | |
1098 | prob_entry = REG_BR_PROB_BASE; | |
1099 | else | |
1100 | prob_entry = PROB_UNROLLED_LOOP_ENTERED * REG_BR_PROB_BASE / 100; | |
1101 | ||
1102 | /* The values for scales should keep profile consistent, and somewhat close | |
1103 | to correct. | |
1104 | ||
1105 | TODO: The current value of SCALE_REST makes it appear that the loop that | |
1106 | is created by splitting the remaining iterations of the unrolled loop is | |
1107 | executed the same number of times as the original loop, and with the same | |
1108 | frequencies, which is obviously wrong. This does not appear to cause | |
1109 | problems, so we do not bother with fixing it for now. To make the profile | |
1110 | correct, we would need to change the probability of the exit edge of the | |
1111 | loop, and recompute the distribution of frequencies in its body because | |
1112 | of this change (scale the frequencies of blocks before and after the exit | |
1113 | by appropriate factors). */ | |
1114 | scale_unrolled = prob_entry; | |
1115 | scale_rest = REG_BR_PROB_BASE; | |
1116 | ||
1117 | new_loop = loop_version (loop, enter_main_cond, NULL, | |
1118 | prob_entry, scale_unrolled, scale_rest, true); | |
17684618 ZD |
1119 | gcc_assert (new_loop != NULL); |
1120 | update_ssa (TODO_update_ssa); | |
1121 | ||
567b96ed | 1122 | /* Determine the probability of the exit edge of the unrolled loop. */ |
03cb2019 ZD |
1123 | new_est_niter = est_niter / factor; |
1124 | ||
1125 | /* Without profile feedback, loops for that we do not know a better estimate | |
1126 | are assumed to roll 10 times. When we unroll such loop, it appears to | |
1127 | roll too little, and it may even seem to be cold. To avoid this, we | |
1128 | ensure that the created loop appears to roll at least 5 times (but at | |
1129 | most as many times as before unrolling). */ | |
1130 | if (new_est_niter < 5) | |
1131 | { | |
1132 | if (est_niter < 5) | |
1133 | new_est_niter = est_niter; | |
1134 | else | |
1135 | new_est_niter = 5; | |
1136 | } | |
1137 | ||
14fa2cc0 ZD |
1138 | /* Prepare the cfg and update the phi nodes. Move the loop exit to the |
1139 | loop latch (and make its condition dummy, for the moment). */ | |
17684618 ZD |
1140 | rest = loop_preheader_edge (new_loop)->src; |
1141 | precond_edge = single_pred_edge (rest); | |
598ec7bd | 1142 | split_edge (loop_latch_edge (loop)); |
17684618 ZD |
1143 | exit_bb = single_pred (loop->latch); |
1144 | ||
14fa2cc0 ZD |
1145 | /* Since the exit edge will be removed, the frequency of all the blocks |
1146 | in the loop that are dominated by it must be scaled by | |
1147 | 1 / (1 - exit->probability). */ | |
1148 | scale_dominated_blocks_in_loop (loop, exit->src, | |
1149 | REG_BR_PROB_BASE, | |
1150 | REG_BR_PROB_BASE - exit->probability); | |
1151 | ||
726a989a RB |
1152 | bsi = gsi_last_bb (exit_bb); |
1153 | exit_if = gimple_build_cond (EQ_EXPR, integer_zero_node, | |
1154 | integer_zero_node, | |
1155 | NULL_TREE, NULL_TREE); | |
a9b77cd1 | 1156 | |
726a989a | 1157 | gsi_insert_after (&bsi, exit_if, GSI_NEW_STMT); |
8e08deeb | 1158 | new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr); |
6270df4c | 1159 | rescan_loop_exit (new_exit, true, false); |
14fa2cc0 ZD |
1160 | |
1161 | /* Set the probability of new exit to the same of the old one. Fix | |
1162 | the frequency of the latch block, by scaling it back by | |
1163 | 1 - exit->probability. */ | |
1164 | new_exit->count = exit->count; | |
1165 | new_exit->probability = exit->probability; | |
17684618 | 1166 | new_nonexit = single_pred_edge (loop->latch); |
14fa2cc0 | 1167 | new_nonexit->probability = REG_BR_PROB_BASE - exit->probability; |
17684618 | 1168 | new_nonexit->flags = EDGE_TRUE_VALUE; |
14fa2cc0 ZD |
1169 | new_nonexit->count -= exit->count; |
1170 | if (new_nonexit->count < 0) | |
1171 | new_nonexit->count = 0; | |
1172 | scale_bbs_frequencies_int (&loop->latch, 1, new_nonexit->probability, | |
1173 | REG_BR_PROB_BASE); | |
17684618 ZD |
1174 | |
1175 | old_entry = loop_preheader_edge (loop); | |
1176 | new_entry = loop_preheader_edge (new_loop); | |
1177 | old_latch = loop_latch_edge (loop); | |
726a989a RB |
1178 | for (psi_old_loop = gsi_start_phis (loop->header), |
1179 | psi_new_loop = gsi_start_phis (new_loop->header); | |
1180 | !gsi_end_p (psi_old_loop); | |
1181 | gsi_next (&psi_old_loop), gsi_next (&psi_new_loop)) | |
17684618 | 1182 | { |
538dd0b7 DM |
1183 | phi_old_loop = psi_old_loop.phi (); |
1184 | phi_new_loop = psi_new_loop.phi (); | |
726a989a | 1185 | |
17684618 ZD |
1186 | init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry); |
1187 | op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry); | |
1188 | gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op))); | |
1189 | next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch); | |
1190 | ||
1191 | /* Prefer using original variable as a base for the new ssa name. | |
1192 | This is necessary for virtual ops, and useful in order to avoid | |
1193 | losing debug info for real ops. */ | |
182e00b1 RG |
1194 | if (TREE_CODE (next) == SSA_NAME |
1195 | && useless_type_conversion_p (TREE_TYPE (next), | |
1196 | TREE_TYPE (init))) | |
b731b390 | 1197 | new_init = copy_ssa_name (next); |
182e00b1 RG |
1198 | else if (TREE_CODE (init) == SSA_NAME |
1199 | && useless_type_conversion_p (TREE_TYPE (init), | |
1200 | TREE_TYPE (next))) | |
b731b390 | 1201 | new_init = copy_ssa_name (init); |
182e00b1 | 1202 | else if (useless_type_conversion_p (TREE_TYPE (next), TREE_TYPE (init))) |
70b5e7dc | 1203 | new_init = make_temp_ssa_name (TREE_TYPE (next), NULL, "unrinittmp"); |
17684618 | 1204 | else |
70b5e7dc | 1205 | new_init = make_temp_ssa_name (TREE_TYPE (init), NULL, "unrinittmp"); |
17684618 | 1206 | |
17684618 | 1207 | phi_rest = create_phi_node (new_init, rest); |
17684618 | 1208 | |
9e227d60 DC |
1209 | add_phi_arg (phi_rest, init, precond_edge, UNKNOWN_LOCATION); |
1210 | add_phi_arg (phi_rest, next, new_exit, UNKNOWN_LOCATION); | |
17684618 ZD |
1211 | SET_USE (op, new_init); |
1212 | } | |
1213 | ||
14fa2cc0 ZD |
1214 | remove_path (exit); |
1215 | ||
567b96ed ZD |
1216 | /* Transform the loop. */ |
1217 | if (transform) | |
1218 | (*transform) (loop, data); | |
1219 | ||
14fa2cc0 ZD |
1220 | /* Unroll the loop and remove the exits in all iterations except for the |
1221 | last one. */ | |
567b96ed | 1222 | wont_exit = sbitmap_alloc (factor); |
f61e445a | 1223 | bitmap_ones (wont_exit); |
d7c028c0 | 1224 | bitmap_clear_bit (wont_exit, factor - 1); |
14fa2cc0 | 1225 | |
726a989a | 1226 | ok = gimple_duplicate_loop_to_header_edge |
567b96ed | 1227 | (loop, loop_latch_edge (loop), factor - 1, |
14fa2cc0 | 1228 | wont_exit, new_exit, &to_remove, DLTHE_FLAG_UPDATE_FREQ); |
567b96ed ZD |
1229 | free (wont_exit); |
1230 | gcc_assert (ok); | |
14fa2cc0 | 1231 | |
9771b263 | 1232 | FOR_EACH_VEC_ELT (to_remove, i, e) |
14fa2cc0 ZD |
1233 | { |
1234 | ok = remove_path (e); | |
1235 | gcc_assert (ok); | |
1236 | } | |
567b96ed ZD |
1237 | update_ssa (TODO_update_ssa); |
1238 | ||
1239 | /* Ensure that the frequencies in the loop match the new estimated | |
1240 | number of iterations, and change the probability of the new | |
1241 | exit edge. */ | |
1242 | freq_h = loop->header->frequency; | |
1243 | freq_e = EDGE_FREQUENCY (loop_preheader_edge (loop)); | |
1244 | if (freq_h != 0) | |
1245 | scale_loop_frequencies (loop, freq_e * (new_est_niter + 1), freq_h); | |
1246 | ||
1247 | exit_bb = single_pred (loop->latch); | |
1248 | new_exit = find_edge (exit_bb, rest); | |
1249 | new_exit->count = loop_preheader_edge (loop)->count; | |
1250 | new_exit->probability = REG_BR_PROB_BASE / (new_est_niter + 1); | |
1251 | ||
1252 | rest->count += new_exit->count; | |
1253 | rest->frequency += EDGE_FREQUENCY (new_exit); | |
1254 | ||
1255 | new_nonexit = single_pred_edge (loop->latch); | |
14fa2cc0 | 1256 | prob = new_nonexit->probability; |
567b96ed | 1257 | new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability; |
14fa2cc0 ZD |
1258 | new_nonexit->count = exit_bb->count - new_exit->count; |
1259 | if (new_nonexit->count < 0) | |
1260 | new_nonexit->count = 0; | |
87621e5f SE |
1261 | if (prob > 0) |
1262 | scale_bbs_frequencies_int (&loop->latch, 1, new_nonexit->probability, | |
1263 | prob); | |
567b96ed | 1264 | |
17684618 ZD |
1265 | /* Finally create the new counter for number of iterations and add the new |
1266 | exit instruction. */ | |
22963fee | 1267 | bsi = gsi_last_nondebug_bb (exit_bb); |
538dd0b7 | 1268 | exit_if = as_a <gcond *> (gsi_stmt (bsi)); |
17684618 | 1269 | create_iv (exit_base, exit_step, NULL_TREE, loop, |
567b96ed | 1270 | &bsi, false, &ctr_before, &ctr_after); |
726a989a RB |
1271 | gimple_cond_set_code (exit_if, exit_cmp); |
1272 | gimple_cond_set_lhs (exit_if, ctr_after); | |
1273 | gimple_cond_set_rhs (exit_if, exit_bound); | |
567b96ed | 1274 | update_stmt (exit_if); |
17684618 | 1275 | |
c0493b13 | 1276 | #ifdef ENABLE_CHECKING |
17684618 | 1277 | verify_flow_info (); |
d73be268 | 1278 | verify_loop_structure (); |
a3b9e73c | 1279 | verify_loop_closed_ssa (true); |
c0493b13 | 1280 | #endif |
17684618 | 1281 | } |
567b96ed ZD |
1282 | |
1283 | /* Wrapper over tree_transform_and_unroll_loop for case we do not | |
1284 | want to transform the loop before unrolling. The meaning | |
1285 | of the arguments is the same as for tree_transform_and_unroll_loop. */ | |
1286 | ||
1287 | void | |
1288 | tree_unroll_loop (struct loop *loop, unsigned factor, | |
1289 | edge exit, struct tree_niter_desc *desc) | |
1290 | { | |
1291 | tree_transform_and_unroll_loop (loop, factor, exit, desc, | |
1292 | NULL, NULL); | |
1293 | } | |
08dab97a RL |
1294 | |
1295 | /* Rewrite the phi node at position PSI in function of the main | |
1296 | induction variable MAIN_IV and insert the generated code at GSI. */ | |
1297 | ||
1298 | static void | |
1299 | rewrite_phi_with_iv (loop_p loop, | |
538dd0b7 | 1300 | gphi_iterator *psi, |
08dab97a RL |
1301 | gimple_stmt_iterator *gsi, |
1302 | tree main_iv) | |
1303 | { | |
1304 | affine_iv iv; | |
538dd0b7 DM |
1305 | gassign *stmt; |
1306 | gphi *phi = psi->phi (); | |
08dab97a RL |
1307 | tree atype, mtype, val, res = PHI_RESULT (phi); |
1308 | ||
ea057359 | 1309 | if (virtual_operand_p (res) || res == main_iv) |
08dab97a RL |
1310 | { |
1311 | gsi_next (psi); | |
1312 | return; | |
1313 | } | |
1314 | ||
1315 | if (!simple_iv (loop, loop, res, &iv, true)) | |
1316 | { | |
1317 | gsi_next (psi); | |
1318 | return; | |
1319 | } | |
1320 | ||
1321 | remove_phi_node (psi, false); | |
1322 | ||
1323 | atype = TREE_TYPE (res); | |
1324 | mtype = POINTER_TYPE_P (atype) ? sizetype : atype; | |
1325 | val = fold_build2 (MULT_EXPR, mtype, unshare_expr (iv.step), | |
1326 | fold_convert (mtype, main_iv)); | |
1327 | val = fold_build2 (POINTER_TYPE_P (atype) | |
1328 | ? POINTER_PLUS_EXPR : PLUS_EXPR, | |
1329 | atype, unshare_expr (iv.base), val); | |
1330 | val = force_gimple_operand_gsi (gsi, val, false, NULL_TREE, true, | |
1331 | GSI_SAME_STMT); | |
1332 | stmt = gimple_build_assign (res, val); | |
1333 | gsi_insert_before (gsi, stmt, GSI_SAME_STMT); | |
08dab97a RL |
1334 | } |
1335 | ||
1336 | /* Rewrite all the phi nodes of LOOP in function of the main induction | |
1337 | variable MAIN_IV. */ | |
1338 | ||
1339 | static void | |
1340 | rewrite_all_phi_nodes_with_iv (loop_p loop, tree main_iv) | |
1341 | { | |
1342 | unsigned i; | |
1343 | basic_block *bbs = get_loop_body_in_dom_order (loop); | |
538dd0b7 | 1344 | gphi_iterator psi; |
08dab97a RL |
1345 | |
1346 | for (i = 0; i < loop->num_nodes; i++) | |
1347 | { | |
1348 | basic_block bb = bbs[i]; | |
1349 | gimple_stmt_iterator gsi = gsi_after_labels (bb); | |
1350 | ||
1351 | if (bb->loop_father != loop) | |
1352 | continue; | |
1353 | ||
1354 | for (psi = gsi_start_phis (bb); !gsi_end_p (psi); ) | |
1355 | rewrite_phi_with_iv (loop, &psi, &gsi, main_iv); | |
1356 | } | |
1357 | ||
1358 | free (bbs); | |
1359 | } | |
1360 | ||
b092fe39 TV |
1361 | /* Bases all the induction variables in LOOP on a single induction variable |
1362 | (with base 0 and step 1), whose final value is compared with *NIT. When the | |
1363 | IV type precision has to be larger than *NIT type precision, *NIT is | |
1364 | converted to the larger type, the conversion code is inserted before the | |
1365 | loop, and *NIT is updated to the new definition. When BUMP_IN_LATCH is true, | |
1366 | the induction variable is incremented in the loop latch, otherwise it is | |
1367 | incremented in the loop header. Return the induction variable that was | |
1368 | created. */ | |
08dab97a RL |
1369 | |
1370 | tree | |
c80a5403 | 1371 | canonicalize_loop_ivs (struct loop *loop, tree *nit, bool bump_in_latch) |
08dab97a RL |
1372 | { |
1373 | unsigned precision = TYPE_PRECISION (TREE_TYPE (*nit)); | |
1374 | unsigned original_precision = precision; | |
1375 | tree type, var_before; | |
538dd0b7 DM |
1376 | gimple_stmt_iterator gsi; |
1377 | gphi_iterator psi; | |
1378 | gcond *stmt; | |
08dab97a RL |
1379 | edge exit = single_dom_exit (loop); |
1380 | gimple_seq stmts; | |
ef4bddc2 | 1381 | machine_mode mode; |
3689198d | 1382 | bool unsigned_p = false; |
08dab97a RL |
1383 | |
1384 | for (psi = gsi_start_phis (loop->header); | |
1385 | !gsi_end_p (psi); gsi_next (&psi)) | |
1386 | { | |
538dd0b7 | 1387 | gphi *phi = psi.phi (); |
08dab97a | 1388 | tree res = PHI_RESULT (phi); |
3689198d | 1389 | bool uns; |
08dab97a | 1390 | |
3689198d | 1391 | type = TREE_TYPE (res); |
ea057359 | 1392 | if (virtual_operand_p (res) |
3689198d SP |
1393 | || (!INTEGRAL_TYPE_P (type) |
1394 | && !POINTER_TYPE_P (type)) | |
1395 | || TYPE_PRECISION (type) < precision) | |
1396 | continue; | |
1397 | ||
1398 | uns = POINTER_TYPE_P (type) | TYPE_UNSIGNED (type); | |
1399 | ||
1400 | if (TYPE_PRECISION (type) > precision) | |
1401 | unsigned_p = uns; | |
1402 | else | |
1403 | unsigned_p |= uns; | |
1404 | ||
1405 | precision = TYPE_PRECISION (type); | |
08dab97a RL |
1406 | } |
1407 | ||
3689198d SP |
1408 | mode = smallest_mode_for_size (precision, MODE_INT); |
1409 | precision = GET_MODE_PRECISION (mode); | |
1410 | type = build_nonstandard_integer_type (precision, unsigned_p); | |
08dab97a RL |
1411 | |
1412 | if (original_precision != precision) | |
1413 | { | |
1414 | *nit = fold_convert (type, *nit); | |
1415 | *nit = force_gimple_operand (*nit, &stmts, true, NULL_TREE); | |
1416 | if (stmts) | |
1417 | gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts); | |
1418 | } | |
1419 | ||
f5b77e7d JJ |
1420 | if (bump_in_latch) |
1421 | gsi = gsi_last_bb (loop->latch); | |
1422 | else | |
1423 | gsi = gsi_last_nondebug_bb (loop->header); | |
08dab97a | 1424 | create_iv (build_int_cst_type (type, 0), build_int_cst (type, 1), NULL_TREE, |
c80a5403 | 1425 | loop, &gsi, bump_in_latch, &var_before, NULL); |
08dab97a RL |
1426 | |
1427 | rewrite_all_phi_nodes_with_iv (loop, var_before); | |
1428 | ||
538dd0b7 | 1429 | stmt = as_a <gcond *> (last_stmt (exit->src)); |
08dab97a RL |
1430 | /* Make the loop exit if the control condition is not satisfied. */ |
1431 | if (exit->flags & EDGE_TRUE_VALUE) | |
1432 | { | |
1433 | edge te, fe; | |
1434 | ||
1435 | extract_true_false_edges_from_block (exit->src, &te, &fe); | |
1436 | te->flags = EDGE_FALSE_VALUE; | |
1437 | fe->flags = EDGE_TRUE_VALUE; | |
1438 | } | |
1439 | gimple_cond_set_code (stmt, LT_EXPR); | |
1440 | gimple_cond_set_lhs (stmt, var_before); | |
1441 | gimple_cond_set_rhs (stmt, *nit); | |
1442 | update_stmt (stmt); | |
1443 | ||
1444 | return var_before; | |
1445 | } |