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