Line data Source code
1 : /* High-level loop manipulation functions.
2 : Copyright (C) 2004-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
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.
10 :
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.
15 :
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"
23 : #include "backend.h"
24 : #include "tree.h"
25 : #include "gimple.h"
26 : #include "cfghooks.h"
27 : #include "tree-pass.h" /* ??? for TODO_update_ssa but this isn't a pass. */
28 : #include "ssa.h"
29 : #include "gimple-pretty-print.h"
30 : #include "fold-const.h"
31 : #include "cfganal.h"
32 : #include "gimplify.h"
33 : #include "gimple-iterator.h"
34 : #include "gimplify-me.h"
35 : #include "tree-cfg.h"
36 : #include "tree-ssa-loop-ivopts.h"
37 : #include "tree-ssa-loop-manip.h"
38 : #include "tree-ssa-loop-niter.h"
39 : #include "tree-ssa-loop.h"
40 : #include "tree-into-ssa.h"
41 : #include "tree-ssa.h"
42 : #include "cfgloop.h"
43 : #include "tree-scalar-evolution.h"
44 : #include "tree-inline.h"
45 :
46 : /* All bitmaps for rewriting into loop-closed SSA go on this obstack,
47 : so that we can free them all at once. */
48 : static bitmap_obstack loop_renamer_obstack;
49 :
50 : /* Reset debug binds outside LOOP that use values defined in the NUM_NODES
51 : basic blocks in BBS. */
52 :
53 : void
54 34597 : reset_debug_uses_outside_loop (class loop *loop, basic_block *bbs,
55 : unsigned num_nodes)
56 : {
57 106115 : for (unsigned i = 0; i < num_nodes; ++i)
58 : {
59 71518 : basic_block bb = bbs[i];
60 71518 : imm_use_iterator ui;
61 71518 : gimple *use_stmt;
62 169589 : for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
63 98071 : gsi_next (&gpi))
64 : {
65 310710 : FOR_EACH_IMM_USE_STMT (use_stmt, ui,
66 : gimple_phi_result (gpi.phi ()))
67 234455 : if (gimple_debug_bind_p (use_stmt)
68 21816 : && loop != gimple_bb (use_stmt)->loop_father
69 21832 : && !flow_loop_nested_p (loop,
70 16 : gimple_bb (use_stmt)->loop_father))
71 : {
72 2 : gimple_debug_bind_reset_value (use_stmt);
73 2 : update_stmt (use_stmt);
74 98071 : }
75 : }
76 657759 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
77 514723 : gsi_next (&gsi))
78 : {
79 514723 : ssa_op_iter op_iter;
80 514723 : def_operand_p def_p;
81 833072 : FOR_EACH_SSA_DEF_OPERAND (def_p, gsi_stmt (gsi), op_iter, SSA_OP_DEF)
82 794102 : FOR_EACH_IMM_USE_STMT (use_stmt, ui, DEF_FROM_PTR (def_p))
83 512834 : if (gimple_debug_bind_p (use_stmt)
84 37081 : && loop != gimple_bb (use_stmt)->loop_father
85 37109 : && !flow_loop_nested_p (loop,
86 28 : gimple_bb (use_stmt)->loop_father))
87 : {
88 1 : gimple_debug_bind_reset_value (use_stmt);
89 1 : update_stmt (use_stmt);
90 318349 : }
91 : }
92 : }
93 34597 : }
94 :
95 : /* Insert IV increment statements STMTS before or after INCR_POS;
96 : AFTER selects which. INCR_POS and AFTER can be computed using
97 : standard_iv_increment_position. */
98 :
99 : void
100 1056994 : insert_iv_increment (gimple_stmt_iterator *incr_pos, bool after,
101 : gimple_seq stmts)
102 : {
103 : /* Prevent the increment from inheriting a bogus location if it is not put
104 : immediately after a statement whose location is known. */
105 1056994 : if (after)
106 : {
107 12353 : gimple_stmt_iterator gsi = *incr_pos;
108 12353 : if (!gsi_end_p (gsi))
109 10856 : gsi_next_nondebug (&gsi);
110 12353 : if (gsi_end_p (gsi))
111 : {
112 12353 : edge e = single_succ_edge (gsi_bb (*incr_pos));
113 12353 : gimple_seq_set_location (stmts, e->goto_locus);
114 : }
115 12353 : gsi_insert_seq_after (incr_pos, stmts, GSI_NEW_STMT);
116 : }
117 : else
118 : {
119 1044641 : gimple_stmt_iterator gsi = *incr_pos;
120 1044641 : if (!gsi_end_p (gsi) && is_gimple_debug (gsi_stmt (gsi)))
121 0 : gsi_next_nondebug (&gsi);
122 1044641 : if (!gsi_end_p (gsi))
123 1044137 : gimple_seq_set_location (stmts, gimple_location (gsi_stmt (gsi)));
124 1044641 : gsi_insert_seq_before (incr_pos, stmts, GSI_NEW_STMT);
125 : }
126 1056994 : }
127 :
128 : /* Creates an induction variable with value BASE (+/-) STEP * iteration in LOOP.
129 : If INCR_OP is PLUS_EXPR, the induction variable is BASE + STEP * iteration.
130 : If INCR_OP is MINUS_EXPR, the induction variable is BASE - STEP * iteration.
131 : It is expected that neither BASE nor STEP are shared with other expressions
132 : (unless the sharing rules allow this). Use VAR as a base var_decl for it
133 : (if NULL, a new temporary will be created). The increment will occur at
134 : INCR_POS (after it if AFTER is true, before it otherwise). INCR_POS and
135 : AFTER can be computed using standard_iv_increment_position. The ssa versions
136 : of the variable before and after increment will be stored in VAR_BEFORE and
137 : VAR_AFTER (unless they are NULL). If LOOP_INVARIANT is true then the
138 : calculation step will be added to the pre-header. Otherwise, the step
139 : calculation is added to incr_pos. */
140 :
141 : void
142 1040327 : create_iv (tree base, tree_code incr_op, tree step, tree var, class loop *loop,
143 : gimple_stmt_iterator *incr_pos, bool after, tree *var_before,
144 : tree *var_after, bool loop_invariant)
145 : {
146 1040327 : gphi *phi;
147 1040327 : tree initial, step1;
148 1040327 : gimple_seq stmts;
149 1040327 : tree vb, va;
150 1040327 : gcc_assert (incr_op == PLUS_EXPR || incr_op == MINUS_EXPR);
151 1040327 : edge pe = loop_preheader_edge (loop);
152 :
153 1040327 : if (var != NULL_TREE)
154 : {
155 641547 : vb = make_ssa_name (var);
156 641547 : va = make_ssa_name (var);
157 : }
158 : else
159 : {
160 398780 : vb = make_temp_ssa_name (TREE_TYPE (base), NULL, "ivtmp");
161 398780 : va = make_temp_ssa_name (TREE_TYPE (base), NULL, "ivtmp");
162 : }
163 1040327 : if (var_before)
164 715033 : *var_before = vb;
165 1040327 : if (var_after)
166 1032731 : *var_after = va;
167 :
168 : /* For easier readability of the created code, produce MINUS_EXPRs
169 : when suitable. */
170 1040327 : if (TREE_CODE (step) == INTEGER_CST)
171 : {
172 976828 : if (TYPE_UNSIGNED (TREE_TYPE (step)))
173 : {
174 974796 : step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
175 974796 : if (tree_int_cst_lt (step1, step))
176 : {
177 341800 : incr_op = (incr_op == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR);
178 : step = step1;
179 : }
180 : }
181 : else
182 : {
183 2032 : if (!tree_expr_nonnegative_p (step)
184 2032 : && may_negate_without_overflow_p (step))
185 : {
186 21 : incr_op = (incr_op == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR);
187 21 : step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
188 : }
189 : }
190 : }
191 1040327 : if (POINTER_TYPE_P (TREE_TYPE (base)))
192 : {
193 140505 : if (TREE_CODE (base) == ADDR_EXPR)
194 50631 : mark_addressable (TREE_OPERAND (base, 0));
195 140505 : step = convert_to_ptrofftype (step);
196 140505 : if (incr_op == MINUS_EXPR)
197 3028 : step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
198 : incr_op = POINTER_PLUS_EXPR;
199 : }
200 :
201 1040327 : gimple_seq incr_stmts = nullptr;
202 : /* Gimplify the step if necessary. */
203 1040327 : if (loop_invariant)
204 : {
205 1040327 : step = force_gimple_operand (step, &stmts, true, NULL_TREE);
206 1040327 : if (stmts)
207 0 : gsi_insert_seq_on_edge_immediate (pe, stmts);
208 : }
209 : else
210 0 : step = force_gimple_operand (step, &incr_stmts, true, NULL_TREE);
211 :
212 1040327 : gimple_seq_add_stmt (&incr_stmts,
213 1040327 : gimple_build_assign (va, incr_op, vb, step));
214 1040327 : insert_iv_increment (incr_pos, after, incr_stmts);
215 :
216 1040327 : initial = force_gimple_operand (base, &stmts, true, var);
217 1040327 : if (stmts)
218 280512 : gsi_insert_seq_on_edge_immediate (pe, stmts);
219 :
220 1040327 : phi = create_phi_node (vb, loop->header);
221 1040327 : add_phi_arg (phi, initial, loop_preheader_edge (loop), UNKNOWN_LOCATION);
222 1040327 : add_phi_arg (phi, va, loop_latch_edge (loop), UNKNOWN_LOCATION);
223 1040327 : }
224 :
225 : /* Return the innermost superloop LOOP of USE_LOOP that is a superloop of
226 : both DEF_LOOP and USE_LOOP. */
227 :
228 : static inline class loop *
229 148222 : find_sibling_superloop (class loop *use_loop, class loop *def_loop)
230 : {
231 148222 : unsigned ud = loop_depth (use_loop);
232 148222 : unsigned dd = loop_depth (def_loop);
233 148222 : gcc_assert (ud > 0 && dd > 0);
234 148222 : if (ud > dd)
235 18852 : use_loop = superloop_at_depth (use_loop, dd);
236 148222 : if (ud < dd)
237 27742 : def_loop = superloop_at_depth (def_loop, ud);
238 150993 : while (loop_outer (use_loop) != loop_outer (def_loop))
239 : {
240 2771 : use_loop = loop_outer (use_loop);
241 2771 : def_loop = loop_outer (def_loop);
242 2771 : gcc_assert (use_loop && def_loop);
243 : }
244 148222 : return use_loop;
245 : }
246 :
247 : /* DEF_BB is a basic block containing a DEF that needs rewriting into
248 : loop-closed SSA form. USE_BLOCKS is the set of basic blocks containing
249 : uses of DEF that "escape" from the loop containing DEF_BB (i.e. blocks in
250 : USE_BLOCKS are dominated by DEF_BB but not in the loop father of DEF_BB).
251 : ALL_EXITS[I] is the set of all basic blocks that exit loop I.
252 : DEF_LOOP_EXITS is a bitmap of loop exit blocks that exit the loop
253 : containing DEF_BB or its outer loops.
254 :
255 : Compute the subset of loop exit destinations that exit the loop
256 : containing DEF_BB or one of its loop fathers, in which DEF is live.
257 : This set is returned in the bitmap LIVE_EXITS.
258 :
259 : Instead of computing the complete livein set of the def, we use the loop
260 : nesting tree as a form of poor man's structure analysis. This greatly
261 : speeds up the analysis, which is important because this function may be
262 : called on all SSA names that need rewriting, one at a time. */
263 :
264 : static void
265 3247368 : compute_live_loop_exits (bitmap live_exits, bitmap use_blocks,
266 : basic_block def_bb, bitmap def_loop_exits)
267 : {
268 3247368 : unsigned i;
269 3247368 : bitmap_iterator bi;
270 3247368 : class loop *def_loop = def_bb->loop_father;
271 3247368 : unsigned def_loop_depth = loop_depth (def_loop);
272 :
273 : /* Normally the work list size is bounded by the number of basic
274 : blocks in the largest loop. We don't know this number, but we
275 : can be fairly sure that it will be relatively small. */
276 3247368 : auto_vec<basic_block, 8> worklist (MAX (8, n_basic_blocks_for_fn (cfun) / 128));
277 :
278 7818044 : EXECUTE_IF_SET_IN_BITMAP (use_blocks, 0, i, bi)
279 : {
280 4570676 : basic_block use_bb = BASIC_BLOCK_FOR_FN (cfun, i);
281 4570676 : class loop *use_loop = use_bb->loop_father;
282 4570676 : gcc_checking_assert (def_loop != use_loop
283 : && ! flow_loop_nested_p (def_loop, use_loop));
284 4570676 : if (! flow_loop_nested_p (use_loop, def_loop))
285 124190 : use_bb = find_sibling_superloop (use_loop, def_loop)->header;
286 4570676 : if (bitmap_set_bit (live_exits, use_bb->index))
287 4527023 : worklist.safe_push (use_bb);
288 : }
289 :
290 : /* Iterate until the worklist is empty. */
291 10037496 : while (! worklist.is_empty ())
292 : {
293 6790128 : edge e;
294 6790128 : edge_iterator ei;
295 :
296 : /* Pull a block off the worklist. */
297 6790128 : basic_block bb = worklist.pop ();
298 :
299 : /* Make sure we have at least enough room in the work list
300 : for all predecessors of this block. */
301 6790128 : worklist.reserve (EDGE_COUNT (bb->preds));
302 :
303 : /* For each predecessor block. */
304 14653035 : FOR_EACH_EDGE (e, ei, bb->preds)
305 : {
306 7862907 : basic_block pred = e->src;
307 7862907 : class loop *pred_loop = pred->loop_father;
308 7862907 : unsigned pred_loop_depth = loop_depth (pred_loop);
309 7862907 : bool pred_visited;
310 :
311 : /* We should have met DEF_BB along the way. */
312 7862907 : gcc_assert (pred != ENTRY_BLOCK_PTR_FOR_FN (cfun));
313 :
314 7862907 : if (pred_loop_depth >= def_loop_depth)
315 : {
316 4785444 : if (pred_loop_depth > def_loop_depth)
317 155485 : pred_loop = superloop_at_depth (pred_loop, def_loop_depth);
318 : /* If we've reached DEF_LOOP, our train ends here. */
319 4785444 : if (pred_loop == def_loop)
320 5599802 : continue;
321 : }
322 3077463 : else if (! flow_loop_nested_p (pred_loop, def_loop))
323 24032 : pred = find_sibling_superloop (pred_loop, def_loop)->header;
324 :
325 : /* Add PRED to the LIVEIN set. PRED_VISITED is true if
326 : we had already added PRED to LIVEIN before. */
327 3929434 : pred_visited = !bitmap_set_bit (live_exits, pred->index);
328 :
329 : /* If we have visited PRED before, don't add it to the worklist.
330 : If BB dominates PRED, then we're probably looking at a loop.
331 : We're only interested in looking up in the dominance tree
332 : because DEF_BB dominates all the uses. */
333 3929434 : if (pred_visited || dominated_by_p (CDI_DOMINATORS, pred, bb))
334 1666329 : continue;
335 :
336 2263105 : worklist.quick_push (pred);
337 : }
338 : }
339 :
340 3247368 : bitmap_and_into (live_exits, def_loop_exits);
341 3247368 : }
342 :
343 : /* Add a loop-closing PHI for VAR in basic block EXIT. */
344 :
345 : static void
346 3850817 : add_exit_phi (basic_block exit, tree var)
347 : {
348 3850817 : gphi *phi;
349 3850817 : edge e;
350 3850817 : edge_iterator ei;
351 :
352 : /* Check that at least one of the edges entering the EXIT block exits
353 : the loop, or a superloop of that loop, that VAR is defined in. */
354 3850817 : if (flag_checking)
355 : {
356 3850715 : gimple *def_stmt = SSA_NAME_DEF_STMT (var);
357 3850715 : basic_block def_bb = gimple_bb (def_stmt);
358 3860272 : FOR_EACH_EDGE (e, ei, exit->preds)
359 : {
360 7720544 : class loop *aloop = find_common_loop (def_bb->loop_father,
361 3860272 : e->src->loop_father);
362 3860272 : if (!flow_bb_inside_loop_p (aloop, e->dest))
363 : break;
364 : }
365 3850715 : gcc_assert (e);
366 : }
367 :
368 3850817 : phi = create_phi_node (NULL_TREE, exit);
369 3850817 : create_new_def_for (var, phi, gimple_phi_result_ptr (phi));
370 7907925 : FOR_EACH_EDGE (e, ei, exit->preds)
371 4057108 : add_phi_arg (phi, var, e, UNKNOWN_LOCATION);
372 :
373 3850817 : if (dump_file && (dump_flags & TDF_DETAILS))
374 : {
375 1854 : fprintf (dump_file, ";; Created LCSSA PHI: ");
376 1854 : print_gimple_stmt (dump_file, phi, 0, dump_flags);
377 : }
378 3850817 : }
379 :
380 : /* Add exit phis for VAR that is used in LIVEIN.
381 : Exits of the loops are stored in LOOP_EXITS. Returns the number
382 : of PHIs added for VAR. */
383 :
384 : static unsigned
385 3247368 : add_exit_phis_var (tree var, bitmap use_blocks, bitmap def_loop_exits)
386 : {
387 3247368 : unsigned index;
388 3247368 : bitmap_iterator bi;
389 3247368 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
390 :
391 3247368 : gcc_checking_assert (! bitmap_bit_p (use_blocks, def_bb->index));
392 :
393 3247368 : auto_bitmap live_exits (&loop_renamer_obstack);
394 3247368 : compute_live_loop_exits (live_exits, use_blocks, def_bb, def_loop_exits);
395 :
396 3247368 : unsigned cnt = 0;
397 7098185 : EXECUTE_IF_SET_IN_BITMAP (live_exits, 0, index, bi)
398 : {
399 3850817 : add_exit_phi (BASIC_BLOCK_FOR_FN (cfun, index), var);
400 3850817 : cnt++;
401 : }
402 3247368 : return cnt;
403 3247368 : }
404 :
405 : static int
406 48311587 : loop_name_cmp (const void *p1, const void *p2)
407 : {
408 48311587 : auto l1 = (const std::pair<int, int> *)p1;
409 48311587 : auto l2 = (const std::pair<int, int> *)p2;
410 48311587 : if (l1->first < l2->first)
411 : return -1;
412 29060024 : else if (l1->first > l2->first)
413 18106701 : return 1;
414 : return 0;
415 : }
416 :
417 : /* Add exit phis for the names marked in NAMES_TO_RENAME.
418 : Exits of the loops are stored in EXITS. Sets of blocks where the ssa
419 : names are used are stored in USE_BLOCKS. Returns whether any name
420 : required multiple LC PHI nodes. */
421 :
422 : static bool
423 748240 : add_exit_phis (bitmap names_to_rename, bitmap *use_blocks)
424 : {
425 748240 : unsigned i;
426 748240 : bitmap_iterator bi;
427 748240 : bool multiple_p = false;
428 :
429 : /* Sort names_to_rename after definition loop so we can avoid re-computing
430 : def_loop_exits. */
431 748240 : auto_vec<std::pair<int, int> > names (bitmap_count_bits (names_to_rename));
432 3995608 : EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
433 : {
434 3247368 : tree name = ssa_name (i);
435 3247368 : loop_p def_loop = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father;
436 3247368 : names.quick_push (std::make_pair (def_loop->num, i));
437 : }
438 748240 : names.qsort (loop_name_cmp);
439 :
440 748240 : auto_bitmap def_loop_exits (&loop_renamer_obstack);
441 748240 : loop_p last_def_loop = NULL;
442 5492088 : for (auto p : names)
443 : {
444 3247368 : loop_p def_loop = get_loop (cfun, p.first);
445 3247368 : if (def_loop != last_def_loop)
446 : {
447 1794756 : bitmap_clear (def_loop_exits);
448 1794756 : last_def_loop = def_loop;
449 6004107 : for (class loop *loop = def_loop; loop != current_loops->tree_root;
450 2414595 : loop = loop_outer (loop))
451 8824378 : for (auto exit = loop->exits->next; exit->e; exit = exit->next)
452 6409783 : bitmap_set_bit (def_loop_exits, exit->e->dest->index);
453 : }
454 3247368 : if (add_exit_phis_var (ssa_name (p.second), use_blocks[p.second],
455 : def_loop_exits) > 1)
456 359472 : multiple_p = true;
457 : }
458 :
459 748240 : return multiple_p;
460 748240 : }
461 :
462 : /* For USE in BB, if it is used outside of the loop it is defined in,
463 : mark it for rewrite. Record basic block BB where it is used
464 : to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap.
465 : Note that for USEs in phis, BB should be the src of the edge corresponding to
466 : the use, rather than the bb containing the phi. */
467 :
468 : static void
469 166658040 : find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks,
470 : bitmap need_phis)
471 : {
472 166658040 : unsigned ver;
473 166658040 : basic_block def_bb;
474 166658040 : class loop *def_loop;
475 :
476 166658040 : if (TREE_CODE (use) != SSA_NAME)
477 : return;
478 :
479 160672202 : ver = SSA_NAME_VERSION (use);
480 160672202 : def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
481 160672202 : if (!def_bb)
482 : return;
483 149114334 : def_loop = def_bb->loop_father;
484 :
485 : /* If the definition is not inside a loop, it is not interesting. */
486 149114334 : if (!loop_outer (def_loop))
487 : return;
488 :
489 : /* If the use is not outside of the loop it is defined in, it is not
490 : interesting. */
491 78081678 : if (flow_bb_inside_loop_p (def_loop, bb))
492 : return;
493 :
494 : /* If we're seeing VER for the first time, we still have to allocate
495 : a bitmap for its uses. */
496 5224565 : if (bitmap_set_bit (need_phis, ver))
497 3247368 : use_blocks[ver] = BITMAP_ALLOC (&loop_renamer_obstack);
498 5224565 : bitmap_set_bit (use_blocks[ver], bb->index);
499 : }
500 :
501 : /* For uses matching USE_FLAGS in STMT, mark names that are used outside of the
502 : loop they are defined to rewrite. Record the set of blocks in which the ssa
503 : names are used to USE_BLOCKS, and the ssa names themselves to NEED_PHIS. */
504 :
505 : static void
506 222550250 : find_uses_to_rename_stmt (gimple *stmt, bitmap *use_blocks, bitmap need_phis,
507 : int use_flags)
508 : {
509 222550250 : ssa_op_iter iter;
510 222550250 : tree var;
511 222550250 : basic_block bb = gimple_bb (stmt);
512 :
513 222550250 : if (is_gimple_debug (stmt))
514 131397526 : return;
515 :
516 : /* FOR_EACH_SSA_TREE_OPERAND iterator does not allows SSA_OP_VIRTUAL_USES
517 : only. */
518 91152724 : if (use_flags == SSA_OP_VIRTUAL_USES)
519 : {
520 91152724 : tree vuse = gimple_vuse (stmt);
521 0 : if (vuse != NULL_TREE)
522 0 : find_uses_to_rename_use (bb, gimple_vuse (stmt), use_blocks, need_phis);
523 : }
524 : else
525 220030620 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, use_flags)
526 128877896 : find_uses_to_rename_use (bb, var, use_blocks, need_phis);
527 : }
528 :
529 : /* Marks names matching USE_FLAGS that are used in BB and outside of the loop
530 : they are defined in for rewrite. Records the set of blocks in which the ssa
531 : names are used to USE_BLOCKS. Record the SSA names that will
532 : need exit PHIs in NEED_PHIS. */
533 :
534 : static void
535 30919104 : find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis,
536 : int use_flags)
537 : {
538 30919104 : edge e;
539 30919104 : edge_iterator ei;
540 30919104 : bool do_virtuals = (use_flags & SSA_OP_VIRTUAL_USES) != 0;
541 30919104 : bool do_nonvirtuals = (use_flags & SSA_OP_USE) != 0;
542 :
543 74925578 : FOR_EACH_EDGE (e, ei, bb->succs)
544 81786618 : for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi);
545 37780144 : gsi_next (&bsi))
546 : {
547 37780144 : gphi *phi = bsi.phi ();
548 37780144 : bool virtual_p = virtual_operand_p (gimple_phi_result (phi));
549 37780144 : if ((virtual_p && do_virtuals)
550 22480295 : || (!virtual_p && do_nonvirtuals))
551 37780144 : find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
552 : use_blocks, need_phis);
553 : }
554 :
555 284388458 : for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
556 222550250 : gsi_next (&bsi))
557 222550250 : find_uses_to_rename_stmt (gsi_stmt (bsi), use_blocks, need_phis,
558 : use_flags);
559 30919104 : }
560 :
561 : /* Marks names matching USE_FLAGS that are used outside of the loop they are
562 : defined in for rewrite. Records the set of blocks in which the ssa names are
563 : used to USE_BLOCKS. Record the SSA names that will need exit PHIs in
564 : NEED_PHIS. If CHANGED_BBS is not NULL, scan only blocks in this set. */
565 :
566 : static void
567 1070301 : find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis,
568 : int use_flags)
569 : {
570 1070301 : basic_block bb;
571 1070301 : unsigned index;
572 1070301 : bitmap_iterator bi;
573 :
574 1070301 : if (changed_bbs)
575 29418 : EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi)
576 : {
577 21561 : bb = BASIC_BLOCK_FOR_FN (cfun, index);
578 21561 : if (bb)
579 21561 : find_uses_to_rename_bb (bb, use_blocks, need_phis, use_flags);
580 : }
581 : else
582 31959987 : FOR_EACH_BB_FN (bb, cfun)
583 30897543 : find_uses_to_rename_bb (bb, use_blocks, need_phis, use_flags);
584 1070301 : }
585 :
586 : /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
587 : phi nodes to ensure that no variable is used outside the loop it is
588 : defined in.
589 :
590 : This strengthening of the basic ssa form has several advantages:
591 :
592 : 1) Updating it during unrolling/peeling/versioning is trivial, since
593 : we do not need to care about the uses outside of the loop.
594 : The same applies to virtual operands which are also rewritten into
595 : loop closed SSA form. Note that virtual operands are always live
596 : until function exit.
597 : 2) The behavior of all uses of an induction variable is the same.
598 : Without this, you need to distinguish the case when the variable
599 : is used outside of the loop it is defined in, for example
600 :
601 : for (i = 0; i < 100; i++)
602 : {
603 : for (j = 0; j < 100; j++)
604 : {
605 : k = i + j;
606 : use1 (k);
607 : }
608 : use2 (k);
609 : }
610 :
611 : Looking from the outer loop with the normal SSA form, the first use of k
612 : is not well-behaved, while the second one is an induction variable with
613 : base 99 and step 1.
614 :
615 : If CHANGED_BBS is not NULL, we look for uses outside loops only in the
616 : basic blocks in this set.
617 :
618 : USE_FLAGS allows us to specify whether we want virtual, non-virtual or
619 : both variables rewritten.
620 :
621 : UPDATE_FLAG is used in the call to update_ssa. See
622 : TODO_update_ssa* for documentation. */
623 :
624 : static void
625 4724951 : rewrite_into_loop_closed_ssa_1 (bitmap changed_bbs, unsigned update_flag,
626 : int use_flags)
627 : {
628 4724951 : bitmap *use_blocks;
629 4724951 : bitmap names_to_rename;
630 :
631 4724951 : loops_state_set (LOOP_CLOSED_SSA);
632 4724951 : if (number_of_loops (cfun) <= 1)
633 : return;
634 :
635 : /* If the pass has caused the SSA form to be out-of-date, update it
636 : now. */
637 1070301 : if (update_flag != 0)
638 1069915 : update_ssa (update_flag);
639 386 : else if (flag_checking)
640 386 : verify_ssa (true, true);
641 :
642 1070301 : bitmap_obstack_initialize (&loop_renamer_obstack);
643 :
644 1070301 : names_to_rename = BITMAP_ALLOC (&loop_renamer_obstack);
645 :
646 : /* Uses of names to rename. We don't have to initialize this array,
647 : because we know that we will only have entries for the SSA names
648 : in NAMES_TO_RENAME. */
649 2140602 : use_blocks = XNEWVEC (bitmap, num_ssa_names);
650 1070301 : find_uses_to_rename (changed_bbs, use_blocks, names_to_rename, use_flags);
651 :
652 1070301 : if (!bitmap_empty_p (names_to_rename))
653 : {
654 748240 : bool release_recorded_exits_p = false;
655 748240 : if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
656 : {
657 : /* Doing one scan over the whole function is cheaper than
658 : traversing the loop tree and gathering BBs of each loop. */
659 0 : record_loop_exits ();
660 0 : release_recorded_exits_p = true;
661 : }
662 :
663 : /* Add the PHI nodes on exits of the loops for the names we need to
664 : rewrite. When no variable required multiple LC PHI nodes to be
665 : inserted then we know that all uses outside of the loop are
666 : dominated by the single LC SSA definition and no further PHI
667 : node insertions are required. */
668 748240 : bool need_phis_p = add_exit_phis (names_to_rename, use_blocks);
669 :
670 748240 : if (release_recorded_exits_p)
671 0 : release_recorded_exits (cfun);
672 :
673 : /* Fix up all the names found to be used outside their original
674 : loops. */
675 1348641 : update_ssa (need_phis_p ? TODO_update_ssa : TODO_update_ssa_no_phi);
676 : }
677 :
678 1070301 : bitmap_obstack_release (&loop_renamer_obstack);
679 1070301 : free (use_blocks);
680 : }
681 :
682 : /* Rewrites the defs and uses into a loop closed ssa form.
683 : If CHANGED_BBS is not NULL, we look for uses outside loops only in the basic
684 : blocks in this set. UPDATE_FLAG is used in the call to update_ssa. See
685 : TODO_update_ssa* for documentation. */
686 :
687 : void
688 4724951 : rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
689 : {
690 4724951 : rewrite_into_loop_closed_ssa_1 (changed_bbs, update_flag, SSA_OP_ALL_USES);
691 4724951 : }
692 :
693 : /* Check invariants of the loop closed ssa form for the def in DEF_BB. */
694 :
695 : static void
696 180761557 : check_loop_closed_ssa_def (basic_block def_bb, tree def)
697 : {
698 180761557 : use_operand_p use_p;
699 180761557 : imm_use_iterator iterator;
700 532068347 : FOR_EACH_IMM_USE_FAST (use_p, iterator, def)
701 : {
702 351306790 : if (is_gimple_debug (USE_STMT (use_p)))
703 46243799 : continue;
704 :
705 305062991 : basic_block use_bb = gimple_bb (USE_STMT (use_p));
706 305062991 : if (is_a <gphi *> (USE_STMT (use_p)))
707 81746300 : use_bb = EDGE_PRED (use_bb, PHI_ARG_INDEX_FROM_USE (use_p))->src;
708 :
709 305062991 : gcc_assert (flow_bb_inside_loop_p (def_bb->loop_father, use_bb));
710 180761557 : }
711 180761557 : }
712 :
713 : /* Checks invariants of loop closed ssa form in BB. */
714 :
715 : static void
716 52639795 : check_loop_closed_ssa_bb (basic_block bb)
717 : {
718 95839691 : for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
719 43199896 : gsi_next (&bsi))
720 : {
721 43199896 : gphi *phi = bsi.phi ();
722 :
723 43199896 : check_loop_closed_ssa_def (bb, PHI_RESULT (phi));
724 : }
725 :
726 215012058 : for (gimple_stmt_iterator bsi = gsi_start_nondebug_bb (bb); !gsi_end_p (bsi);
727 162372263 : gsi_next_nondebug (&bsi))
728 : {
729 162372263 : ssa_op_iter iter;
730 162372263 : tree var;
731 162372263 : gimple *stmt = gsi_stmt (bsi);
732 :
733 299933924 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_DEFS)
734 137561661 : check_loop_closed_ssa_def (bb, var);
735 : }
736 52639795 : }
737 :
738 : /* Checks that invariants of the loop closed ssa form are preserved.
739 : Call verify_ssa when VERIFY_SSA_P is true. Note all loops are checked
740 : if LOOP is NULL, otherwise, only LOOP is checked. */
741 :
742 : DEBUG_FUNCTION void
743 4018499 : verify_loop_closed_ssa (bool verify_ssa_p, class loop *loop)
744 : {
745 8036998 : if (number_of_loops (cfun) <= 1)
746 : return;
747 :
748 4018499 : timevar_push (TV_VERIFY_LOOP_CLOSED);
749 :
750 4018499 : if (loop == NULL)
751 : {
752 4016754 : basic_block bb;
753 :
754 4016754 : if (verify_ssa_p)
755 35309 : verify_ssa (false, true);
756 :
757 132845697 : FOR_EACH_BB_FN (bb, cfun)
758 128828943 : if (bb->loop_father && bb->loop_father->num > 0)
759 52631476 : check_loop_closed_ssa_bb (bb);
760 : }
761 : else
762 : {
763 1745 : basic_block *bbs = get_loop_body (loop);
764 :
765 : /* We do not have loop-local SSA verification so just
766 : check there's no update queued. */
767 1745 : if (verify_ssa_p)
768 1745 : gcc_assert (!need_ssa_update_p (cfun));
769 :
770 10064 : for (unsigned i = 0; i < loop->num_nodes; ++i)
771 8319 : check_loop_closed_ssa_bb (bbs[i]);
772 :
773 1745 : free (bbs);
774 : }
775 :
776 4018499 : timevar_pop (TV_VERIFY_LOOP_CLOSED);
777 : }
778 :
779 : /* Split loop exit edge EXIT. The things are a bit complicated by a need to
780 : preserve the loop closed ssa form. If COPY_CONSTANTS_P is true then
781 : forwarder PHIs are also created for constant arguments.
782 : The newly created block is returned. */
783 :
784 : basic_block
785 66523 : split_loop_exit_edge (edge exit, bool copy_constants_p)
786 : {
787 66523 : basic_block dest = exit->dest;
788 66523 : basic_block bb = split_edge (exit);
789 66523 : gphi *phi, *new_phi;
790 66523 : tree new_name, name;
791 66523 : use_operand_p op_p;
792 66523 : gphi_iterator psi;
793 66523 : location_t locus;
794 :
795 157911 : for (psi = gsi_start_phis (dest); !gsi_end_p (psi); gsi_next (&psi))
796 : {
797 91388 : phi = psi.phi ();
798 91388 : op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb));
799 91388 : locus = gimple_phi_arg_location_from_edge (phi, single_succ_edge (bb));
800 :
801 91388 : name = USE_FROM_PTR (op_p);
802 :
803 : /* If the argument of the PHI node is a constant, we do not need
804 : to keep it inside loop. */
805 91388 : if (TREE_CODE (name) != SSA_NAME
806 2621 : && !copy_constants_p)
807 2507 : continue;
808 :
809 : /* Otherwise create an auxiliary phi node that will copy the value
810 : of the SSA name out of the loop. */
811 88881 : new_name = duplicate_ssa_name (PHI_RESULT (phi), NULL);
812 88881 : new_phi = create_phi_node (new_name, bb);
813 88881 : add_phi_arg (new_phi, name, exit, locus);
814 88881 : SET_USE (op_p, new_name);
815 : }
816 :
817 66523 : return bb;
818 : }
819 :
820 : /* Returns the basic block in that statements should be emitted for induction
821 : variables incremented at the end of the LOOP. */
822 :
823 : basic_block
824 24492720 : ip_end_pos (class loop *loop)
825 : {
826 24492720 : return loop->latch;
827 : }
828 :
829 : /* Returns the basic block in that statements should be emitted for induction
830 : variables incremented just before exit condition of a LOOP. */
831 :
832 : basic_block
833 50497410 : ip_normal_pos (class loop *loop)
834 : {
835 50497410 : basic_block bb;
836 50497410 : edge exit;
837 :
838 50497410 : if (!single_pred_p (loop->latch))
839 : return NULL;
840 :
841 50345448 : bb = single_pred (loop->latch);
842 100690896 : if (!safe_is_a <gcond *> (*gsi_last_bb (bb)))
843 : return NULL;
844 :
845 50332632 : exit = EDGE_SUCC (bb, 0);
846 50332632 : if (exit->dest == loop->latch)
847 38022451 : exit = EDGE_SUCC (bb, 1);
848 :
849 50332632 : if (flow_bb_inside_loop_p (loop, exit->dest))
850 58616 : return NULL;
851 :
852 : return bb;
853 : }
854 :
855 : /* Stores the standard position for induction variable increment in LOOP
856 : (just before the exit condition if it is available and latch block is empty,
857 : end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if
858 : the increment should be inserted after *BSI. */
859 :
860 : void
861 222261 : standard_iv_increment_position (class loop *loop, gimple_stmt_iterator *bsi,
862 : bool *insert_after)
863 : {
864 222261 : basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
865 222261 : gimple *last = last_nondebug_stmt (latch);
866 :
867 222261 : if (!bb
868 222261 : || (last && gimple_code (last) != GIMPLE_LABEL))
869 : {
870 117 : *bsi = gsi_last_bb (latch);
871 117 : *insert_after = true;
872 : }
873 : else
874 : {
875 222144 : *bsi = gsi_last_bb (bb);
876 222144 : *insert_after = false;
877 : }
878 222261 : }
879 :
880 : /* Copies phi node arguments for duplicated blocks. The index of the first
881 : duplicated block is FIRST_NEW_BLOCK. */
882 :
883 : static void
884 153903 : copy_phi_node_args (unsigned first_new_block)
885 : {
886 153903 : unsigned i;
887 :
888 1382216 : for (i = first_new_block; i < (unsigned) last_basic_block_for_fn (cfun); i++)
889 1228313 : BASIC_BLOCK_FOR_FN (cfun, i)->flags |= BB_DUPLICATED;
890 :
891 1382216 : for (i = first_new_block; i < (unsigned) last_basic_block_for_fn (cfun); i++)
892 1228313 : add_phi_args_after_copy_bb (BASIC_BLOCK_FOR_FN (cfun, i));
893 :
894 1382216 : for (i = first_new_block; i < (unsigned) last_basic_block_for_fn (cfun); i++)
895 1228313 : BASIC_BLOCK_FOR_FN (cfun, i)->flags &= ~BB_DUPLICATED;
896 153903 : }
897 :
898 :
899 : /* The same as cfgloopmanip.cc:duplicate_loop_body_to_header_edge, but also
900 : updates the PHI nodes at start of the copied region. In order to
901 : achieve this, only loops whose exits all lead to the same location
902 : are handled.
903 :
904 : Notice that we do not completely update the SSA web after
905 : duplication. The caller is responsible for calling update_ssa
906 : after the loop has been duplicated. */
907 :
908 : bool
909 153920 : gimple_duplicate_loop_body_to_header_edge (class loop *loop, edge e,
910 : unsigned int ndupl,
911 : sbitmap wont_exit, edge orig,
912 : vec<edge> *to_remove, int flags)
913 : {
914 153920 : unsigned first_new_block;
915 :
916 153920 : if (!loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
917 : return false;
918 153920 : if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS))
919 : return false;
920 :
921 153920 : first_new_block = last_basic_block_for_fn (cfun);
922 153920 : if (!duplicate_loop_body_to_header_edge (loop, e, ndupl, wont_exit, orig,
923 : to_remove, flags))
924 : return false;
925 :
926 : /* Readd the removed phi args for e. */
927 153903 : flush_pending_stmts (e);
928 :
929 : /* Copy the phi node arguments. */
930 153903 : copy_phi_node_args (first_new_block);
931 :
932 153903 : scev_reset ();
933 :
934 153903 : return true;
935 : }
936 :
937 : /* Returns true if we can unroll LOOP FACTOR times. Number
938 : of iterations of the loop is returned in NITER. */
939 :
940 : bool
941 930 : can_unroll_loop_p (class loop *loop, unsigned factor,
942 : class tree_niter_desc *niter)
943 : {
944 930 : edge exit;
945 :
946 : /* Check whether unrolling is possible. We only want to unroll loops
947 : for that we are able to determine number of iterations. We also
948 : want to split the extra iterations of the loop from its end,
949 : therefore we require that the loop has precisely one
950 : exit. */
951 :
952 930 : exit = single_dom_exit (loop);
953 930 : if (!exit)
954 : return false;
955 :
956 909 : if (!number_of_iterations_exit (loop, exit, niter, false)
957 908 : || niter->cmp == ERROR_MARK
958 : /* Scalar evolutions analysis might have copy propagated
959 : the abnormal ssa names into these expressions, hence
960 : emitting the computations based on them during loop
961 : unrolling might create overlapping life ranges for
962 : them, and failures in out-of-ssa. */
963 906 : || contains_abnormal_ssa_name_p (niter->may_be_zero)
964 906 : || contains_abnormal_ssa_name_p (niter->control.base)
965 906 : || contains_abnormal_ssa_name_p (niter->control.step)
966 1815 : || contains_abnormal_ssa_name_p (niter->bound))
967 : return false;
968 :
969 : /* And of course, we must be able to duplicate the loop. */
970 906 : if (!can_duplicate_loop_p (loop))
971 : return false;
972 :
973 : /* The final loop should be small enough. */
974 906 : if (tree_num_loop_insns (loop, &eni_size_weights) * factor
975 906 : > (unsigned) param_max_unrolled_insns)
976 6 : return false;
977 :
978 : return true;
979 : }
980 :
981 : /* Determines the conditions that control execution of LOOP unrolled FACTOR
982 : times. DESC is number of iterations of LOOP. ENTER_COND is set to
983 : condition that must be true if the main loop can be entered.
984 : If the loop does not always iterate an exact multiple of FACTOR times,
985 : EXIT_BASE, EXIT_STEP, EXIT_CMP and EXIT_BOUND are set to values describing
986 : how the exit from the unrolled loop should be controlled. Otherwise,
987 : the trees are set to null and EXIT_CMP is set to ERROR_MARK. */
988 :
989 : static void
990 889 : determine_exit_conditions (class loop *loop, class tree_niter_desc *desc,
991 : unsigned factor, tree *enter_cond,
992 : tree *exit_base, tree *exit_step,
993 : enum tree_code *exit_cmp, tree *exit_bound)
994 : {
995 889 : gimple_seq stmts;
996 889 : tree base = desc->control.base;
997 889 : tree step = desc->control.step;
998 889 : tree bound = desc->bound;
999 889 : tree type = TREE_TYPE (step);
1000 889 : tree bigstep, delta;
1001 889 : tree min = lower_bound_in_type (type, type);
1002 889 : tree max = upper_bound_in_type (type, type);
1003 889 : enum tree_code cmp = desc->cmp;
1004 889 : tree cond = boolean_true_node, assum;
1005 :
1006 : /* For pointers, do the arithmetics in the type of step. */
1007 889 : base = fold_convert (type, base);
1008 889 : bound = fold_convert (type, bound);
1009 :
1010 889 : *enter_cond = boolean_false_node;
1011 889 : *exit_base = NULL_TREE;
1012 889 : *exit_step = NULL_TREE;
1013 889 : *exit_cmp = ERROR_MARK;
1014 889 : *exit_bound = NULL_TREE;
1015 889 : gcc_assert (cmp != ERROR_MARK);
1016 :
1017 : /* We only need to be correct when we answer question
1018 : "Do at least FACTOR more iterations remain?" in the unrolled loop.
1019 : Thus, transforming BASE + STEP * i <> BOUND to
1020 : BASE + STEP * i < BOUND is ok. */
1021 889 : if (cmp == NE_EXPR)
1022 : {
1023 89 : if (tree_int_cst_sign_bit (step))
1024 : cmp = GT_EXPR;
1025 : else
1026 889 : cmp = LT_EXPR;
1027 : }
1028 800 : else if (cmp == LT_EXPR)
1029 : {
1030 798 : gcc_assert (!tree_int_cst_sign_bit (step));
1031 : }
1032 2 : else if (cmp == GT_EXPR)
1033 : {
1034 2 : gcc_assert (tree_int_cst_sign_bit (step));
1035 : }
1036 : else
1037 0 : gcc_unreachable ();
1038 :
1039 : /* The main body of the loop may be entered iff:
1040 :
1041 : 1) desc->may_be_zero is false.
1042 : 2) it is possible to check that there are at least FACTOR iterations
1043 : of the loop, i.e., BOUND - step * FACTOR does not overflow.
1044 : 3) # of iterations is at least FACTOR */
1045 :
1046 889 : if (!integer_zerop (desc->may_be_zero))
1047 5 : cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1048 : invert_truthvalue (desc->may_be_zero),
1049 : cond);
1050 :
1051 889 : bigstep = fold_build2 (MULT_EXPR, type, step,
1052 : build_int_cst_type (type, factor));
1053 889 : delta = fold_build2 (MINUS_EXPR, type, bigstep, step);
1054 889 : if (cmp == LT_EXPR)
1055 835 : assum = fold_build2 (GE_EXPR, boolean_type_node,
1056 : bound,
1057 : fold_build2 (PLUS_EXPR, type, min, delta));
1058 : else
1059 54 : assum = fold_build2 (LE_EXPR, boolean_type_node,
1060 : bound,
1061 : fold_build2 (PLUS_EXPR, type, max, delta));
1062 889 : cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
1063 :
1064 889 : bound = fold_build2 (MINUS_EXPR, type, bound, delta);
1065 889 : assum = fold_build2 (cmp, boolean_type_node, base, bound);
1066 889 : cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
1067 :
1068 889 : if (integer_nonzerop (cond)
1069 889 : && integer_zerop (desc->may_be_zero))
1070 : {
1071 : /* When the iteration count is an exact multiple of factor we're done. */
1072 164 : if (TREE_CODE (desc->niter) == INTEGER_CST
1073 164 : && wi::multiple_of_p (wi::to_widest (desc->niter) + 1,
1074 : factor, UNSIGNED))
1075 33 : return;
1076 : }
1077 :
1078 856 : cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE);
1079 856 : if (stmts)
1080 19 : gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1081 : /* cond now may be a gimple comparison, which would be OK, but also any
1082 : other gimple rhs (say a && b). In this case we need to force it to
1083 : operand. */
1084 856 : if (!is_gimple_condexpr_for_cond (cond))
1085 : {
1086 14 : cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
1087 14 : if (stmts)
1088 14 : gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1089 : }
1090 856 : *enter_cond = cond;
1091 :
1092 856 : base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE);
1093 856 : if (stmts)
1094 30 : gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1095 856 : bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE);
1096 856 : if (stmts)
1097 774 : gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1098 :
1099 856 : *exit_base = base;
1100 856 : *exit_step = bigstep;
1101 856 : *exit_cmp = cmp;
1102 856 : *exit_bound = bound;
1103 : }
1104 :
1105 : /* Unroll LOOP FACTOR times. LOOP is known to have a single exit edge
1106 : whose source block dominates the latch. DESC describes the number of
1107 : iterations of LOOP.
1108 :
1109 : If N is number of iterations of the loop and MAY_BE_ZERO is the condition
1110 : under that loop exits in the first iteration even if N != 0,
1111 :
1112 : while (1)
1113 : {
1114 : x = phi (init, next);
1115 :
1116 : pre;
1117 : if (st)
1118 : break;
1119 : post;
1120 : }
1121 :
1122 : becomes (with possibly the exit conditions formulated a bit differently,
1123 : avoiding the need to create a new iv):
1124 :
1125 : if (MAY_BE_ZERO || N < FACTOR)
1126 : goto rest;
1127 :
1128 : do
1129 : {
1130 : x = phi (init, next);
1131 :
1132 : pre;
1133 : post;
1134 : pre;
1135 : post;
1136 : ...
1137 : pre;
1138 : post;
1139 : N -= FACTOR;
1140 :
1141 : } while (N >= FACTOR);
1142 :
1143 : rest:
1144 : init' = phi (init, x);
1145 :
1146 : while (1)
1147 : {
1148 : x = phi (init', next);
1149 :
1150 : pre;
1151 : if (st)
1152 : break;
1153 : post;
1154 : }
1155 :
1156 : Before the loop is unrolled, TRANSFORM is called for it (only for the
1157 : unrolled loop, but not for its versioned copy). DATA is passed to
1158 : TRANSFORM. */
1159 :
1160 : /* Probability in % that the unrolled loop is entered. Just a guess. */
1161 : #define PROB_UNROLLED_LOOP_ENTERED 90
1162 :
1163 : void
1164 889 : tree_transform_and_unroll_loop (class loop *loop, unsigned factor,
1165 : class tree_niter_desc *desc,
1166 : transform_callback transform,
1167 : void *data)
1168 : {
1169 889 : unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
1170 :
1171 889 : enum tree_code exit_cmp;
1172 889 : tree enter_main_cond, exit_base, exit_step, exit_bound;
1173 889 : bool flat = maybe_flat_loop_profile (loop);
1174 889 : determine_exit_conditions (loop, desc, factor,
1175 : &enter_main_cond, &exit_base, &exit_step,
1176 : &exit_cmp, &exit_bound);
1177 889 : bool single_loop_p = !exit_base;
1178 :
1179 889 : gcond *exit_if = nullptr;
1180 889 : class loop *new_loop = nullptr;
1181 889 : edge new_exit;
1182 889 : if (!single_loop_p)
1183 : {
1184 856 : profile_count entry_count = loop_preheader_edge (loop)->src->count;
1185 : /* Let us assume that the unrolled loop is quite likely to be entered. */
1186 856 : profile_probability prob_entry;
1187 856 : if (integer_nonzerop (enter_main_cond))
1188 49 : prob_entry = profile_probability::always ();
1189 : else
1190 807 : prob_entry = profile_probability::guessed_always ()
1191 807 : .apply_scale (PROB_UNROLLED_LOOP_ENTERED, 100);
1192 :
1193 :
1194 : /* The values for scales should keep profile consistent, and somewhat
1195 : close to correct. */
1196 856 : new_loop = loop_version (loop, enter_main_cond, NULL, prob_entry,
1197 : prob_entry.invert (),
1198 : prob_entry,
1199 : /* We will later redirect exit from vectorized
1200 : loop to new_loop. */
1201 : profile_probability::always (),
1202 : true);
1203 856 : gcc_assert (new_loop != NULL);
1204 856 : update_ssa (TODO_update_ssa_no_phi);
1205 :
1206 : /* Prepare the cfg and update the phi nodes. Move the loop exit to the
1207 : loop latch (and make its condition dummy, for the moment). */
1208 856 : basic_block rest = loop_preheader_edge (new_loop)->src;
1209 856 : edge precond_edge = single_pred_edge (rest);
1210 856 : split_edge (loop_latch_edge (loop));
1211 856 : basic_block exit_bb = single_pred (loop->latch);
1212 856 : edge exit = single_dom_exit (loop);
1213 :
1214 : /* Since the exit edge will be removed, the frequency of all the blocks
1215 : in the loop that are dominated by it must be scaled. */
1216 856 : if (exit->probability.initialized_p ())
1217 856 : scale_dominated_blocks_in_loop (loop, exit->src,
1218 : /* We are scaling up here so
1219 : probability does not fit. */
1220 856 : exit->src->count,
1221 1712 : exit->src->count - exit->count ());
1222 :
1223 856 : gimple_stmt_iterator bsi = gsi_last_bb (exit_bb);
1224 856 : exit_if = gimple_build_cond (EQ_EXPR, integer_zero_node,
1225 : integer_zero_node,
1226 : NULL_TREE, NULL_TREE);
1227 :
1228 856 : gsi_insert_after (&bsi, exit_if, GSI_NEW_STMT);
1229 856 : new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
1230 856 : rescan_loop_exit (new_exit, true, false);
1231 :
1232 : /* Set the probability of new exit to the same of the old one. Fix
1233 : the count of the latch block. */
1234 856 : new_exit->probability = exit->probability;
1235 856 : edge new_nonexit = single_pred_edge (loop->latch);
1236 856 : new_nonexit->probability = exit->probability.invert ();
1237 856 : new_nonexit->flags = EDGE_TRUE_VALUE;
1238 856 : set_edge_probability_and_rescale_others
1239 856 : (exit, profile_probability::never ());
1240 856 : loop->latch->count = new_nonexit->count ();
1241 :
1242 856 : edge old_entry = loop_preheader_edge (loop);
1243 856 : edge new_entry = loop_preheader_edge (new_loop);
1244 856 : edge old_latch = loop_latch_edge (loop);
1245 856 : for (gphi_iterator psi_old_loop = gsi_start_phis (loop->header),
1246 856 : psi_new_loop = gsi_start_phis (new_loop->header);
1247 2677 : !gsi_end_p (psi_old_loop);
1248 1821 : gsi_next (&psi_old_loop), gsi_next (&psi_new_loop))
1249 : {
1250 1821 : gphi *phi_old_loop = psi_old_loop.phi ();
1251 1821 : gphi *phi_new_loop = psi_new_loop.phi ();
1252 :
1253 1821 : tree init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry);
1254 1821 : use_operand_p op
1255 1821 : = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry);
1256 1821 : gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
1257 1821 : tree next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch);
1258 :
1259 : /* Prefer using original variable as a base for the new ssa name.
1260 : This is necessary for virtual ops, and useful in order to avoid
1261 : losing debug info for real ops. */
1262 1821 : tree new_init;
1263 1821 : if (TREE_CODE (next) == SSA_NAME
1264 3642 : && useless_type_conversion_p (TREE_TYPE (next),
1265 1821 : TREE_TYPE (init)))
1266 1821 : new_init = copy_ssa_name (next);
1267 0 : else if (TREE_CODE (init) == SSA_NAME
1268 0 : && useless_type_conversion_p (TREE_TYPE (init),
1269 0 : TREE_TYPE (next)))
1270 0 : new_init = copy_ssa_name (init);
1271 0 : else if (useless_type_conversion_p (TREE_TYPE (next),
1272 0 : TREE_TYPE (init)))
1273 0 : new_init = make_temp_ssa_name (TREE_TYPE (next), NULL,
1274 : "unrinittmp");
1275 : else
1276 0 : new_init = make_temp_ssa_name (TREE_TYPE (init), NULL,
1277 : "unrinittmp");
1278 :
1279 1821 : gphi *phi_rest = create_phi_node (new_init, rest);
1280 1821 : add_phi_arg (phi_rest, init, precond_edge, UNKNOWN_LOCATION);
1281 1821 : add_phi_arg (phi_rest, next, new_exit, UNKNOWN_LOCATION);
1282 1821 : SET_USE (op, new_init);
1283 : }
1284 :
1285 856 : remove_path (exit);
1286 : /* We will later redirect exit from vectorized loop to new_loop. */
1287 856 : loop_preheader_edge (new_loop)->src->count = entry_count;
1288 :
1289 : /* The epilog loop latch executes at most factor - 1 times.
1290 : Since the epilog is entered unconditionally it will need to handle
1291 : up to factor executions of its body.
1292 :
1293 : That however relies on ENTER_MAIN_COND being false implying that
1294 : less than factor iterations are left. determine_exit_conditions
1295 : derives ENTER_MAIN_COND from a LT_EXPR/GT_EXPR comparison of the
1296 : control IV, which for a NE_EXPR exit test is only valid if that IV
1297 : does not wrap. When it may wrap the main loop can be skipped (the
1298 : condition may even be constant false) while the epilog still runs
1299 : all iterations of the original loop, so keep the bound we inherited
1300 : from it. */
1301 856 : if (desc->cmp != NE_EXPR || desc->control.no_overflow)
1302 : {
1303 854 : new_loop->any_upper_bound = true;
1304 854 : new_loop->nb_iterations_upper_bound = factor - 1;
1305 : /* We do not really know estimate on number of iterations, since we
1306 : do not track any estimates modulo unroll factor.
1307 : Scale loop profile. It may be more realistic to scale loop
1308 : profile to factor / 2 - 1, but vectorizer also uses factor - 1. */
1309 854 : scale_loop_profile (new_loop, profile_probability::always (),
1310 : factor - 1);
1311 : }
1312 : /* Drop estimate from loop_info, see above. */
1313 856 : new_loop->any_estimate = false;
1314 : }
1315 : else
1316 33 : new_exit = single_dom_exit (loop);
1317 :
1318 : /* Transform the loop. */
1319 889 : if (transform)
1320 795 : (*transform) (loop, data);
1321 :
1322 : /* Unroll the loop and remove the exits in all iterations except for the
1323 : last one. */
1324 889 : auto_sbitmap wont_exit (factor);
1325 889 : bitmap_ones (wont_exit);
1326 889 : bitmap_clear_bit (wont_exit, factor - 1);
1327 :
1328 889 : auto_vec<edge> to_remove;
1329 889 : bool ok
1330 : = gimple_duplicate_loop_body_to_header_edge
1331 963 : (loop, loop_latch_edge (loop), factor - 1, wont_exit,
1332 : new_exit, &to_remove,
1333 : DLTHE_FLAG_UPDATE_FREQ | (flat ? DLTHE_FLAG_FLAT_PROFILE : 0));
1334 889 : gcc_assert (ok);
1335 :
1336 3828 : for (edge e : to_remove)
1337 : {
1338 1161 : ok = remove_path (e);
1339 1161 : gcc_assert (ok);
1340 : }
1341 889 : update_ssa (TODO_update_ssa);
1342 :
1343 889 : new_exit = single_dom_exit (loop);
1344 : /* gimple_duplicate_loop_body_to_header_edge depending on
1345 : DLTHE_FLAG_UPDATE_FREQ either keeps original frequency of the loop header
1346 : or scales it down accordingly.
1347 : However exit edge probability is kept as original. Fix it if needed
1348 : and compensate. */
1349 889 : update_loop_exit_probability_scale_dom_bbs (loop, new_exit);
1350 889 : if (!single_loop_p)
1351 : {
1352 : /* Finally create the new counter for number of iterations and add
1353 : the new exit instruction. */
1354 856 : tree ctr_before, ctr_after;
1355 856 : gimple_stmt_iterator bsi = gsi_last_nondebug_bb (new_exit->src);
1356 856 : exit_if = as_a <gcond *> (gsi_stmt (bsi));
1357 856 : create_iv (exit_base, PLUS_EXPR, exit_step, NULL_TREE, loop,
1358 : &bsi, false, &ctr_before, &ctr_after);
1359 856 : gimple_cond_set_code (exit_if, exit_cmp);
1360 856 : gimple_cond_set_lhs (exit_if, ctr_after);
1361 856 : gimple_cond_set_rhs (exit_if, exit_bound);
1362 856 : update_stmt (exit_if);
1363 : }
1364 889 : if (loop->any_upper_bound)
1365 1756 : loop->nb_iterations_upper_bound = wi::udiv_floor
1366 878 : (loop->nb_iterations_upper_bound + 1, factor) - 1;
1367 889 : if (loop->any_likely_upper_bound)
1368 1756 : loop->nb_iterations_likely_upper_bound = wi::udiv_floor
1369 878 : (loop->nb_iterations_likely_upper_bound + 1, factor) - 1;
1370 889 : if (loop->any_estimate)
1371 182 : loop->nb_iterations_estimate = wi::udiv_floor
1372 91 : (loop->nb_iterations_estimate + 1, factor) - 1;
1373 :
1374 889 : checking_verify_flow_info ();
1375 889 : checking_verify_loop_structure ();
1376 889 : checking_verify_loop_closed_ssa (true, loop);
1377 889 : if (new_loop)
1378 1745 : checking_verify_loop_closed_ssa (true, new_loop);
1379 889 : }
1380 :
1381 : /* Wrapper over tree_transform_and_unroll_loop for case we do not
1382 : want to transform the loop before unrolling. The meaning
1383 : of the arguments is the same as for tree_transform_and_unroll_loop. */
1384 :
1385 : void
1386 94 : tree_unroll_loop (class loop *loop, unsigned factor,
1387 : class tree_niter_desc *desc)
1388 : {
1389 94 : tree_transform_and_unroll_loop (loop, factor, desc, NULL, NULL);
1390 94 : }
1391 :
1392 : /* Rewrite the phi node at position PSI in function of the main
1393 : induction variable MAIN_IV and insert the generated code at GSI. */
1394 :
1395 : static void
1396 2025 : rewrite_phi_with_iv (loop_p loop,
1397 : gphi_iterator *psi,
1398 : gimple_stmt_iterator *gsi,
1399 : tree main_iv)
1400 : {
1401 2025 : affine_iv iv;
1402 2025 : gassign *stmt;
1403 2025 : gphi *phi = psi->phi ();
1404 2025 : tree atype, mtype, val, res = PHI_RESULT (phi);
1405 :
1406 4050 : if (virtual_operand_p (res) || res == main_iv)
1407 : {
1408 1155 : gsi_next (psi);
1409 1237 : return;
1410 : }
1411 :
1412 870 : if (!simple_iv (loop, loop, res, &iv, true))
1413 : {
1414 82 : gsi_next (psi);
1415 82 : return;
1416 : }
1417 :
1418 788 : remove_phi_node (psi, false);
1419 :
1420 788 : atype = TREE_TYPE (res);
1421 788 : mtype = POINTER_TYPE_P (atype) ? sizetype : atype;
1422 788 : val = fold_build2 (MULT_EXPR, mtype, unshare_expr (iv.step),
1423 : fold_convert (mtype, main_iv));
1424 1574 : val = fold_build2 (POINTER_TYPE_P (atype)
1425 : ? POINTER_PLUS_EXPR : PLUS_EXPR,
1426 : atype, unshare_expr (iv.base), val);
1427 788 : val = force_gimple_operand_gsi (gsi, val, false, NULL_TREE, true,
1428 : GSI_SAME_STMT);
1429 788 : stmt = gimple_build_assign (res, val);
1430 788 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1431 : }
1432 :
1433 : /* Rewrite all the phi nodes of LOOP in function of the main induction
1434 : variable MAIN_IV. */
1435 :
1436 : static void
1437 580 : rewrite_all_phi_nodes_with_iv (loop_p loop, tree main_iv)
1438 : {
1439 580 : unsigned i;
1440 580 : basic_block *bbs = get_loop_body_in_dom_order (loop);
1441 580 : gphi_iterator psi;
1442 :
1443 2634 : for (i = 0; i < loop->num_nodes; i++)
1444 : {
1445 1474 : basic_block bb = bbs[i];
1446 1474 : gimple_stmt_iterator gsi = gsi_after_labels (bb);
1447 :
1448 1474 : if (bb->loop_father != loop)
1449 97 : continue;
1450 :
1451 3402 : for (psi = gsi_start_phis (bb); !gsi_end_p (psi); )
1452 2025 : rewrite_phi_with_iv (loop, &psi, &gsi, main_iv);
1453 : }
1454 :
1455 580 : free (bbs);
1456 580 : }
1457 :
1458 : /* Bases all the induction variables in LOOP on a single induction variable
1459 : (with base 0 and step 1), whose final value is compared with *NIT. When the
1460 : IV type precision has to be larger than *NIT type precision, *NIT is
1461 : converted to the larger type, the conversion code is inserted before the
1462 : loop, and *NIT is updated to the new definition. When BUMP_IN_LATCH is true,
1463 : the induction variable is incremented in the loop latch, otherwise it is
1464 : incremented in the loop header. Return the induction variable that was
1465 : created. */
1466 :
1467 : tree
1468 580 : canonicalize_loop_ivs (class loop *loop, tree *nit, bool bump_in_latch)
1469 : {
1470 580 : unsigned precision = TYPE_PRECISION (TREE_TYPE (*nit));
1471 580 : unsigned original_precision = precision;
1472 580 : tree type, var_before;
1473 580 : gimple_stmt_iterator gsi;
1474 580 : gphi_iterator psi;
1475 580 : gcond *stmt;
1476 580 : edge exit = single_dom_exit (loop);
1477 580 : gimple_seq stmts;
1478 580 : bool unsigned_p = false;
1479 :
1480 580 : for (psi = gsi_start_phis (loop->header);
1481 1925 : !gsi_end_p (psi); gsi_next (&psi))
1482 : {
1483 1345 : gphi *phi = psi.phi ();
1484 1345 : tree res = PHI_RESULT (phi);
1485 1345 : bool uns;
1486 :
1487 1345 : type = TREE_TYPE (res);
1488 1345 : if (virtual_operand_p (res)
1489 853 : || (!INTEGRAL_TYPE_P (type)
1490 21 : && !POINTER_TYPE_P (type))
1491 2183 : || TYPE_PRECISION (type) < precision)
1492 529 : continue;
1493 :
1494 816 : uns = POINTER_TYPE_P (type) | TYPE_UNSIGNED (type);
1495 :
1496 816 : if (TYPE_PRECISION (type) > precision)
1497 : unsigned_p = uns;
1498 : else
1499 812 : unsigned_p |= uns;
1500 :
1501 816 : precision = TYPE_PRECISION (type);
1502 : }
1503 :
1504 580 : scalar_int_mode mode = smallest_int_mode_for_size (precision).require ();
1505 580 : precision = GET_MODE_PRECISION (mode);
1506 580 : type = build_nonstandard_integer_type (precision, unsigned_p);
1507 :
1508 580 : if (original_precision != precision
1509 580 : || TYPE_UNSIGNED (TREE_TYPE (*nit)) != unsigned_p)
1510 : {
1511 298 : *nit = fold_convert (type, *nit);
1512 298 : *nit = force_gimple_operand (*nit, &stmts, true, NULL_TREE);
1513 298 : if (stmts)
1514 112 : gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1515 : }
1516 :
1517 580 : if (bump_in_latch)
1518 1160 : gsi = gsi_last_bb (loop->latch);
1519 : else
1520 0 : gsi = gsi_last_nondebug_bb (loop->header);
1521 580 : create_iv (build_int_cst_type (type, 0), PLUS_EXPR, build_int_cst (type, 1),
1522 : NULL_TREE, loop, &gsi, bump_in_latch, &var_before, NULL);
1523 :
1524 580 : rewrite_all_phi_nodes_with_iv (loop, var_before);
1525 :
1526 1160 : stmt = as_a <gcond *> (*gsi_last_bb (exit->src));
1527 : /* Make the loop exit if the control condition is not satisfied. */
1528 580 : if (exit->flags & EDGE_TRUE_VALUE)
1529 : {
1530 100 : edge te, fe;
1531 :
1532 100 : extract_true_false_edges_from_block (exit->src, &te, &fe);
1533 100 : te->flags = EDGE_FALSE_VALUE;
1534 100 : fe->flags = EDGE_TRUE_VALUE;
1535 : }
1536 580 : gimple_cond_set_code (stmt, LT_EXPR);
1537 580 : gimple_cond_set_lhs (stmt, var_before);
1538 580 : gimple_cond_set_rhs (stmt, *nit);
1539 580 : update_stmt (stmt);
1540 :
1541 580 : return var_before;
1542 : }
|