1 /* High-level loop manipulation functions.
2 Copyright (C) 2004-2016 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
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/>. */
22 #include "coretypes.h"
27 #include "tree-pass.h" /* ??? for TODO_update_ssa but this isn't a pass. */
29 #include "gimple-pretty-print.h"
30 #include "fold-const.h"
33 #include "gimple-iterator.h"
34 #include "gimplify-me.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"
43 #include "tree-scalar-evolution.h"
45 #include "tree-inline.h"
47 /* All bitmaps for rewriting into loop-closed SSA go on this obstack,
48 so that we can free them all at once. */
49 static bitmap_obstack loop_renamer_obstack;
51 /* Creates an induction variable with value BASE + STEP * iteration in LOOP.
52 It is expected that neither BASE nor STEP are shared with other expressions
53 (unless the sharing rules allow this). Use VAR as a base var_decl for it
54 (if NULL, a new temporary will be created). The increment will occur at
55 INCR_POS (after it if AFTER is true, before it otherwise). INCR_POS and
56 AFTER can be computed using standard_iv_increment_position. The ssa versions
57 of the variable before and after increment will be stored in VAR_BEFORE and
58 VAR_AFTER (unless they are NULL). */
61 create_iv (tree base, tree step, tree var, struct loop *loop,
62 gimple_stmt_iterator *incr_pos, bool after,
63 tree *var_before, tree *var_after)
70 enum tree_code incr_op = PLUS_EXPR;
71 edge pe = loop_preheader_edge (loop);
75 vb = make_ssa_name (var);
76 va = make_ssa_name (var);
80 vb = make_temp_ssa_name (TREE_TYPE (base), NULL, "ivtmp");
81 va = make_temp_ssa_name (TREE_TYPE (base), NULL, "ivtmp");
88 /* For easier readability of the created code, produce MINUS_EXPRs
90 if (TREE_CODE (step) == INTEGER_CST)
92 if (TYPE_UNSIGNED (TREE_TYPE (step)))
94 step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
95 if (tree_int_cst_lt (step1, step))
105 if (!tree_expr_nonnegative_warnv_p (step, &ovf)
106 && may_negate_without_overflow_p (step))
108 incr_op = MINUS_EXPR;
109 step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
113 if (POINTER_TYPE_P (TREE_TYPE (base)))
115 if (TREE_CODE (base) == ADDR_EXPR)
116 mark_addressable (TREE_OPERAND (base, 0));
117 step = convert_to_ptrofftype (step);
118 if (incr_op == MINUS_EXPR)
119 step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
120 incr_op = POINTER_PLUS_EXPR;
122 /* Gimplify the step if necessary. We put the computations in front of the
123 loop (i.e. the step should be loop invariant). */
124 step = force_gimple_operand (step, &stmts, true, NULL_TREE);
126 gsi_insert_seq_on_edge_immediate (pe, stmts);
128 stmt = gimple_build_assign (va, incr_op, vb, step);
130 gsi_insert_after (incr_pos, stmt, GSI_NEW_STMT);
132 gsi_insert_before (incr_pos, stmt, GSI_NEW_STMT);
134 initial = force_gimple_operand (base, &stmts, true, var);
136 gsi_insert_seq_on_edge_immediate (pe, stmts);
138 phi = create_phi_node (vb, loop->header);
139 add_phi_arg (phi, initial, loop_preheader_edge (loop), UNKNOWN_LOCATION);
140 add_phi_arg (phi, va, loop_latch_edge (loop), UNKNOWN_LOCATION);
143 /* Return the innermost superloop LOOP of USE_LOOP that is a superloop of
144 both DEF_LOOP and USE_LOOP. */
146 static inline struct loop *
147 find_sibling_superloop (struct loop *use_loop, struct loop *def_loop)
149 unsigned ud = loop_depth (use_loop);
150 unsigned dd = loop_depth (def_loop);
151 gcc_assert (ud > 0 && dd > 0);
153 use_loop = superloop_at_depth (use_loop, dd);
155 def_loop = superloop_at_depth (def_loop, ud);
156 while (loop_outer (use_loop) != loop_outer (def_loop))
158 use_loop = loop_outer (use_loop);
159 def_loop = loop_outer (def_loop);
160 gcc_assert (use_loop && def_loop);
165 /* DEF_BB is a basic block containing a DEF that needs rewriting into
166 loop-closed SSA form. USE_BLOCKS is the set of basic blocks containing
167 uses of DEF that "escape" from the loop containing DEF_BB (i.e. blocks in
168 USE_BLOCKS are dominated by DEF_BB but not in the loop father of DEF_B).
169 ALL_EXITS[I] is the set of all basic blocks that exit loop I.
171 Compute the subset of LOOP_EXITS that exit the loop containing DEF_BB
172 or one of its loop fathers, in which DEF is live. This set is returned
173 in the bitmap LIVE_EXITS.
175 Instead of computing the complete livein set of the def, we use the loop
176 nesting tree as a form of poor man's structure analysis. This greatly
177 speeds up the analysis, which is important because this function may be
178 called on all SSA names that need rewriting, one at a time. */
181 compute_live_loop_exits (bitmap live_exits, bitmap use_blocks,
182 bitmap *loop_exits, basic_block def_bb)
186 struct loop *def_loop = def_bb->loop_father;
187 unsigned def_loop_depth = loop_depth (def_loop);
188 bitmap def_loop_exits;
190 /* Normally the work list size is bounded by the number of basic
191 blocks in the largest loop. We don't know this number, but we
192 can be fairly sure that it will be relatively small. */
193 auto_vec<basic_block> worklist (MAX (8, n_basic_blocks_for_fn (cfun) / 128));
195 EXECUTE_IF_SET_IN_BITMAP (use_blocks, 0, i, bi)
197 basic_block use_bb = BASIC_BLOCK_FOR_FN (cfun, i);
198 struct loop *use_loop = use_bb->loop_father;
199 gcc_checking_assert (def_loop != use_loop
200 && ! flow_loop_nested_p (def_loop, use_loop));
201 if (! flow_loop_nested_p (use_loop, def_loop))
202 use_bb = find_sibling_superloop (use_loop, def_loop)->header;
203 if (bitmap_set_bit (live_exits, use_bb->index))
204 worklist.safe_push (use_bb);
207 /* Iterate until the worklist is empty. */
208 while (! worklist.is_empty ())
213 /* Pull a block off the worklist. */
214 basic_block bb = worklist.pop ();
216 /* Make sure we have at least enough room in the work list
217 for all predecessors of this block. */
218 worklist.reserve (EDGE_COUNT (bb->preds));
220 /* For each predecessor block. */
221 FOR_EACH_EDGE (e, ei, bb->preds)
223 basic_block pred = e->src;
224 struct loop *pred_loop = pred->loop_father;
225 unsigned pred_loop_depth = loop_depth (pred_loop);
228 /* We should have met DEF_BB along the way. */
229 gcc_assert (pred != ENTRY_BLOCK_PTR_FOR_FN (cfun));
231 if (pred_loop_depth >= def_loop_depth)
233 if (pred_loop_depth > def_loop_depth)
234 pred_loop = superloop_at_depth (pred_loop, def_loop_depth);
235 /* If we've reached DEF_LOOP, our train ends here. */
236 if (pred_loop == def_loop)
239 else if (! flow_loop_nested_p (pred_loop, def_loop))
240 pred = find_sibling_superloop (pred_loop, def_loop)->header;
242 /* Add PRED to the LIVEIN set. PRED_VISITED is true if
243 we had already added PRED to LIVEIN before. */
244 pred_visited = !bitmap_set_bit (live_exits, pred->index);
246 /* If we have visited PRED before, don't add it to the worklist.
247 If BB dominates PRED, then we're probably looking at a loop.
248 We're only interested in looking up in the dominance tree
249 because DEF_BB dominates all the uses. */
250 if (pred_visited || dominated_by_p (CDI_DOMINATORS, pred, bb))
253 worklist.quick_push (pred);
257 def_loop_exits = BITMAP_ALLOC (&loop_renamer_obstack);
258 for (struct loop *loop = def_loop;
259 loop != current_loops->tree_root;
260 loop = loop_outer (loop))
261 bitmap_ior_into (def_loop_exits, loop_exits[loop->num]);
262 bitmap_and_into (live_exits, def_loop_exits);
263 BITMAP_FREE (def_loop_exits);
266 /* Add a loop-closing PHI for VAR in basic block EXIT. */
269 add_exit_phi (basic_block exit, tree var)
275 /* Check that at least one of the edges entering the EXIT block exits
276 the loop, or a superloop of that loop, that VAR is defined in. */
279 gimple *def_stmt = SSA_NAME_DEF_STMT (var);
280 basic_block def_bb = gimple_bb (def_stmt);
281 FOR_EACH_EDGE (e, ei, exit->preds)
283 struct loop *aloop = find_common_loop (def_bb->loop_father,
284 e->src->loop_father);
285 if (!flow_bb_inside_loop_p (aloop, e->dest))
291 phi = create_phi_node (NULL_TREE, exit);
292 create_new_def_for (var, phi, gimple_phi_result_ptr (phi));
293 FOR_EACH_EDGE (e, ei, exit->preds)
294 add_phi_arg (phi, var, e, UNKNOWN_LOCATION);
296 if (dump_file && (dump_flags & TDF_DETAILS))
298 fprintf (dump_file, ";; Created LCSSA PHI: ");
299 print_gimple_stmt (dump_file, phi, 0, dump_flags);
303 /* Add exit phis for VAR that is used in LIVEIN.
304 Exits of the loops are stored in LOOP_EXITS. */
307 add_exit_phis_var (tree var, bitmap use_blocks, bitmap *loop_exits)
311 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
312 bitmap live_exits = BITMAP_ALLOC (&loop_renamer_obstack);
314 gcc_checking_assert (! bitmap_bit_p (use_blocks, def_bb->index));
316 compute_live_loop_exits (live_exits, use_blocks, loop_exits, def_bb);
318 EXECUTE_IF_SET_IN_BITMAP (live_exits, 0, index, bi)
320 add_exit_phi (BASIC_BLOCK_FOR_FN (cfun, index), var);
323 BITMAP_FREE (live_exits);
326 /* Add exit phis for the names marked in NAMES_TO_RENAME.
327 Exits of the loops are stored in EXITS. Sets of blocks where the ssa
328 names are used are stored in USE_BLOCKS. */
331 add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap *loop_exits)
336 EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
338 add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
342 /* Fill the array of bitmaps LOOP_EXITS with all loop exit edge targets. */
345 get_loops_exits (bitmap *loop_exits)
351 FOR_EACH_LOOP (loop, 0)
353 vec<edge> exit_edges = get_loop_exit_edges (loop);
354 loop_exits[loop->num] = BITMAP_ALLOC (&loop_renamer_obstack);
355 FOR_EACH_VEC_ELT (exit_edges, j, e)
356 bitmap_set_bit (loop_exits[loop->num], e->dest->index);
357 exit_edges.release ();
361 /* For USE in BB, if it is used outside of the loop it is defined in,
362 mark it for rewrite. Record basic block BB where it is used
363 to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap.
364 Note that for USEs in phis, BB should be the src of the edge corresponding to
365 the use, rather than the bb containing the phi. */
368 find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks,
373 struct loop *def_loop;
375 if (TREE_CODE (use) != SSA_NAME)
378 ver = SSA_NAME_VERSION (use);
379 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
382 def_loop = def_bb->loop_father;
384 /* If the definition is not inside a loop, it is not interesting. */
385 if (!loop_outer (def_loop))
388 /* If the use is not outside of the loop it is defined in, it is not
390 if (flow_bb_inside_loop_p (def_loop, bb))
393 /* If we're seeing VER for the first time, we still have to allocate
394 a bitmap for its uses. */
395 if (bitmap_set_bit (need_phis, ver))
396 use_blocks[ver] = BITMAP_ALLOC (&loop_renamer_obstack);
397 bitmap_set_bit (use_blocks[ver], bb->index);
400 /* For uses matching USE_FLAGS in STMT, mark names that are used outside of the
401 loop they are defined to rewrite. Record the set of blocks in which the ssa
402 names are used to USE_BLOCKS, and the ssa names themselves to NEED_PHIS. */
405 find_uses_to_rename_stmt (gimple *stmt, bitmap *use_blocks, bitmap need_phis,
410 basic_block bb = gimple_bb (stmt);
412 if (is_gimple_debug (stmt))
415 /* FOR_EACH_SSA_TREE_OPERAND iterator does not allows SSA_OP_VIRTUAL_USES
417 if (use_flags == SSA_OP_VIRTUAL_USES)
419 tree vuse = gimple_vuse (stmt);
420 if (vuse != NULL_TREE)
421 find_uses_to_rename_use (bb, gimple_vuse (stmt), use_blocks, need_phis);
424 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, use_flags)
425 find_uses_to_rename_use (bb, var, use_blocks, need_phis);
428 /* Marks names matching USE_FLAGS that are used in BB and outside of the loop
429 they are defined in for rewrite. Records the set of blocks in which the ssa
430 names are used to USE_BLOCKS. Record the SSA names that will
431 need exit PHIs in NEED_PHIS. */
434 find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis,
439 bool do_virtuals = (use_flags & SSA_OP_VIRTUAL_USES) != 0;
440 bool do_nonvirtuals = (use_flags & SSA_OP_USE) != 0;
442 FOR_EACH_EDGE (e, ei, bb->succs)
443 for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi);
446 gphi *phi = bsi.phi ();
447 bool virtual_p = virtual_operand_p (gimple_phi_result (phi));
448 if ((virtual_p && do_virtuals)
449 || (!virtual_p && do_nonvirtuals))
450 find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
451 use_blocks, need_phis);
454 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
456 find_uses_to_rename_stmt (gsi_stmt (bsi), use_blocks, need_phis,
460 /* Marks names matching USE_FLAGS that are used outside of the loop they are
461 defined in for rewrite. Records the set of blocks in which the ssa names are
462 used to USE_BLOCKS. Record the SSA names that will need exit PHIs in
463 NEED_PHIS. If CHANGED_BBS is not NULL, scan only blocks in this set. */
466 find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis,
474 EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi)
475 find_uses_to_rename_bb (BASIC_BLOCK_FOR_FN (cfun, index), use_blocks,
476 need_phis, use_flags);
478 FOR_EACH_BB_FN (bb, cfun)
479 find_uses_to_rename_bb (bb, use_blocks, need_phis, use_flags);
482 /* Mark uses of DEF that are used outside of the loop they are defined in for
483 rewrite. Record the set of blocks in which the ssa names are used to
484 USE_BLOCKS. Record the SSA names that will need exit PHIs in NEED_PHIS. */
487 find_uses_to_rename_def (tree def, bitmap *use_blocks, bitmap need_phis)
490 imm_use_iterator imm_iter;
492 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
494 basic_block use_bb = gimple_bb (use_stmt);
497 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
499 if (gimple_code (use_stmt) == GIMPLE_PHI)
501 edge e = gimple_phi_arg_edge (as_a <gphi *> (use_stmt),
502 PHI_ARG_INDEX_FROM_USE (use_p));
505 find_uses_to_rename_use (use_bb, USE_FROM_PTR (use_p), use_blocks,
511 /* Marks names matching USE_FLAGS that are defined in LOOP and used outside of
512 it for rewrite. Records the set of blocks in which the ssa names are used to
513 USE_BLOCKS. Record the SSA names that will need exit PHIs in NEED_PHIS. */
516 find_uses_to_rename_in_loop (struct loop *loop, bitmap *use_blocks,
517 bitmap need_phis, int use_flags)
519 bool do_virtuals = (use_flags & SSA_OP_VIRTUAL_USES) != 0;
520 bool do_nonvirtuals = (use_flags & SSA_OP_USE) != 0;
521 int def_flags = ((do_virtuals ? SSA_OP_VIRTUAL_DEFS : 0)
522 | (do_nonvirtuals ? SSA_OP_DEF : 0));
525 basic_block *bbs = get_loop_body (loop);
527 for (unsigned int i = 0; i < loop->num_nodes; i++)
529 basic_block bb = bbs[i];
531 for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
534 gphi *phi = bsi.phi ();
535 tree res = gimple_phi_result (phi);
536 bool virtual_p = virtual_operand_p (res);
537 if ((virtual_p && do_virtuals)
538 || (!virtual_p && do_nonvirtuals))
539 find_uses_to_rename_def (res, use_blocks, need_phis);
542 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
545 gimple *stmt = gsi_stmt (bsi);
546 /* FOR_EACH_SSA_TREE_OPERAND iterator does not allows
547 SSA_OP_VIRTUAL_DEFS only. */
548 if (def_flags == SSA_OP_VIRTUAL_DEFS)
550 tree vdef = gimple_vdef (stmt);
552 find_uses_to_rename_def (vdef, use_blocks, need_phis);
558 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, def_flags)
559 find_uses_to_rename_def (var, use_blocks, need_phis);
567 /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
568 phi nodes to ensure that no variable is used outside the loop it is
571 This strengthening of the basic ssa form has several advantages:
573 1) Updating it during unrolling/peeling/versioning is trivial, since
574 we do not need to care about the uses outside of the loop.
575 The same applies to virtual operands which are also rewritten into
576 loop closed SSA form. Note that virtual operands are always live
578 2) The behavior of all uses of an induction variable is the same.
579 Without this, you need to distinguish the case when the variable
580 is used outside of the loop it is defined in, for example
582 for (i = 0; i < 100; i++)
584 for (j = 0; j < 100; j++)
592 Looking from the outer loop with the normal SSA form, the first use of k
593 is not well-behaved, while the second one is an induction variable with
596 If LOOP is non-null, only rewrite uses that have defs in LOOP. Otherwise,
597 if CHANGED_BBS is not NULL, we look for uses outside loops only in the
598 basic blocks in this set.
600 USE_FLAGS allows us to specify whether we want virtual, non-virtual or
601 both variables rewritten.
603 UPDATE_FLAG is used in the call to update_ssa. See
604 TODO_update_ssa* for documentation. */
607 rewrite_into_loop_closed_ssa_1 (bitmap changed_bbs, unsigned update_flag,
608 int use_flags, struct loop *loop)
611 bitmap names_to_rename;
613 loops_state_set (LOOP_CLOSED_SSA);
614 if (number_of_loops (cfun) <= 1)
617 /* If the pass has caused the SSA form to be out-of-date, update it
619 if (update_flag != 0)
620 update_ssa (update_flag);
621 else if (flag_checking)
622 verify_ssa (true, true);
624 bitmap_obstack_initialize (&loop_renamer_obstack);
626 names_to_rename = BITMAP_ALLOC (&loop_renamer_obstack);
628 /* Uses of names to rename. We don't have to initialize this array,
629 because we know that we will only have entries for the SSA names
630 in NAMES_TO_RENAME. */
631 use_blocks = XNEWVEC (bitmap, num_ssa_names);
635 gcc_assert (changed_bbs == NULL);
636 find_uses_to_rename_in_loop (loop, use_blocks, names_to_rename,
641 gcc_assert (loop == NULL);
642 find_uses_to_rename (changed_bbs, use_blocks, names_to_rename, use_flags);
645 if (!bitmap_empty_p (names_to_rename))
647 /* An array of bitmaps where LOOP_EXITS[I] is the set of basic blocks
648 that are the destination of an edge exiting loop number I. */
649 bitmap *loop_exits = XNEWVEC (bitmap, number_of_loops (cfun));
650 get_loops_exits (loop_exits);
652 /* Add the PHI nodes on exits of the loops for the names we need to
654 add_exit_phis (names_to_rename, use_blocks, loop_exits);
658 /* Fix up all the names found to be used outside their original
660 update_ssa (TODO_update_ssa);
663 bitmap_obstack_release (&loop_renamer_obstack);
667 /* Rewrites the non-virtual defs and uses into a loop closed ssa form. If
668 CHANGED_BBS is not NULL, we look for uses outside loops only in the basic
669 blocks in this set. UPDATE_FLAG is used in the call to update_ssa. See
670 TODO_update_ssa* for documentation. */
673 rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
675 rewrite_into_loop_closed_ssa_1 (changed_bbs, update_flag, SSA_OP_USE, NULL);
678 /* Rewrites virtual defs and uses with def in LOOP into loop closed ssa
682 rewrite_virtuals_into_loop_closed_ssa (struct loop *loop)
684 rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_VIRTUAL_USES, loop);
687 /* Check invariants of the loop closed ssa form for the USE in BB. */
690 check_loop_closed_ssa_use (basic_block bb, tree use)
695 if (TREE_CODE (use) != SSA_NAME || virtual_operand_p (use))
698 def = SSA_NAME_DEF_STMT (use);
699 def_bb = gimple_bb (def);
701 || flow_bb_inside_loop_p (def_bb->loop_father, bb));
704 /* Checks invariants of loop closed ssa form in statement STMT in BB. */
707 check_loop_closed_ssa_stmt (basic_block bb, gimple *stmt)
712 if (is_gimple_debug (stmt))
715 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
716 check_loop_closed_ssa_use (bb, var);
719 /* Checks that invariants of the loop closed ssa form are preserved.
720 Call verify_ssa when VERIFY_SSA_P is true. */
723 verify_loop_closed_ssa (bool verify_ssa_p)
729 if (number_of_loops (cfun) <= 1)
733 verify_ssa (false, true);
735 timevar_push (TV_VERIFY_LOOP_CLOSED);
737 FOR_EACH_BB_FN (bb, cfun)
739 for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
742 gphi *phi = bsi.phi ();
743 FOR_EACH_EDGE (e, ei, bb->preds)
744 check_loop_closed_ssa_use (e->src,
745 PHI_ARG_DEF_FROM_EDGE (phi, e));
748 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
750 check_loop_closed_ssa_stmt (bb, gsi_stmt (bsi));
753 timevar_pop (TV_VERIFY_LOOP_CLOSED);
756 /* Split loop exit edge EXIT. The things are a bit complicated by a need to
757 preserve the loop closed ssa form. The newly created block is returned. */
760 split_loop_exit_edge (edge exit)
762 basic_block dest = exit->dest;
763 basic_block bb = split_edge (exit);
768 source_location locus;
770 for (psi = gsi_start_phis (dest); !gsi_end_p (psi); gsi_next (&psi))
773 op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb));
774 locus = gimple_phi_arg_location_from_edge (phi, single_succ_edge (bb));
776 name = USE_FROM_PTR (op_p);
778 /* If the argument of the PHI node is a constant, we do not need
779 to keep it inside loop. */
780 if (TREE_CODE (name) != SSA_NAME)
783 /* Otherwise create an auxiliary phi node that will copy the value
784 of the SSA name out of the loop. */
785 new_name = duplicate_ssa_name (name, NULL);
786 new_phi = create_phi_node (new_name, bb);
787 add_phi_arg (new_phi, name, exit, locus);
788 SET_USE (op_p, new_name);
794 /* Returns the basic block in that statements should be emitted for induction
795 variables incremented at the end of the LOOP. */
798 ip_end_pos (struct loop *loop)
803 /* Returns the basic block in that statements should be emitted for induction
804 variables incremented just before exit condition of a LOOP. */
807 ip_normal_pos (struct loop *loop)
813 if (!single_pred_p (loop->latch))
816 bb = single_pred (loop->latch);
817 last = last_stmt (bb);
819 || gimple_code (last) != GIMPLE_COND)
822 exit = EDGE_SUCC (bb, 0);
823 if (exit->dest == loop->latch)
824 exit = EDGE_SUCC (bb, 1);
826 if (flow_bb_inside_loop_p (loop, exit->dest))
832 /* Stores the standard position for induction variable increment in LOOP
833 (just before the exit condition if it is available and latch block is empty,
834 end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if
835 the increment should be inserted after *BSI. */
838 standard_iv_increment_position (struct loop *loop, gimple_stmt_iterator *bsi,
841 basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
842 gimple *last = last_stmt (latch);
845 || (last && gimple_code (last) != GIMPLE_LABEL))
847 *bsi = gsi_last_bb (latch);
848 *insert_after = true;
852 *bsi = gsi_last_bb (bb);
853 *insert_after = false;
857 /* Copies phi node arguments for duplicated blocks. The index of the first
858 duplicated block is FIRST_NEW_BLOCK. */
861 copy_phi_node_args (unsigned first_new_block)
865 for (i = first_new_block; i < (unsigned) last_basic_block_for_fn (cfun); i++)
866 BASIC_BLOCK_FOR_FN (cfun, i)->flags |= BB_DUPLICATED;
868 for (i = first_new_block; i < (unsigned) last_basic_block_for_fn (cfun); i++)
869 add_phi_args_after_copy_bb (BASIC_BLOCK_FOR_FN (cfun, i));
871 for (i = first_new_block; i < (unsigned) last_basic_block_for_fn (cfun); i++)
872 BASIC_BLOCK_FOR_FN (cfun, i)->flags &= ~BB_DUPLICATED;
876 /* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also
877 updates the PHI nodes at start of the copied region. In order to
878 achieve this, only loops whose exits all lead to the same location
881 Notice that we do not completely update the SSA web after
882 duplication. The caller is responsible for calling update_ssa
883 after the loop has been duplicated. */
886 gimple_duplicate_loop_to_header_edge (struct loop *loop, edge e,
887 unsigned int ndupl, sbitmap wont_exit,
888 edge orig, vec<edge> *to_remove,
891 unsigned first_new_block;
893 if (!loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
895 if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS))
898 first_new_block = last_basic_block_for_fn (cfun);
899 if (!duplicate_loop_to_header_edge (loop, e, ndupl, wont_exit,
900 orig, to_remove, flags))
903 /* Readd the removed phi args for e. */
904 flush_pending_stmts (e);
906 /* Copy the phi node arguments. */
907 copy_phi_node_args (first_new_block);
914 /* Returns true if we can unroll LOOP FACTOR times. Number
915 of iterations of the loop is returned in NITER. */
918 can_unroll_loop_p (struct loop *loop, unsigned factor,
919 struct tree_niter_desc *niter)
923 /* Check whether unrolling is possible. We only want to unroll loops
924 for that we are able to determine number of iterations. We also
925 want to split the extra iterations of the loop from its end,
926 therefore we require that the loop has precisely one
929 exit = single_dom_exit (loop);
933 if (!number_of_iterations_exit (loop, exit, niter, false)
934 || niter->cmp == ERROR_MARK
935 /* Scalar evolutions analysis might have copy propagated
936 the abnormal ssa names into these expressions, hence
937 emitting the computations based on them during loop
938 unrolling might create overlapping life ranges for
939 them, and failures in out-of-ssa. */
940 || contains_abnormal_ssa_name_p (niter->may_be_zero)
941 || contains_abnormal_ssa_name_p (niter->control.base)
942 || contains_abnormal_ssa_name_p (niter->control.step)
943 || contains_abnormal_ssa_name_p (niter->bound))
946 /* And of course, we must be able to duplicate the loop. */
947 if (!can_duplicate_loop_p (loop))
950 /* The final loop should be small enough. */
951 if (tree_num_loop_insns (loop, &eni_size_weights) * factor
952 > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS))
958 /* Determines the conditions that control execution of LOOP unrolled FACTOR
959 times. DESC is number of iterations of LOOP. ENTER_COND is set to
960 condition that must be true if the main loop can be entered.
961 EXIT_BASE, EXIT_STEP, EXIT_CMP and EXIT_BOUND are set to values describing
962 how the exit from the unrolled loop should be controlled. */
965 determine_exit_conditions (struct loop *loop, struct tree_niter_desc *desc,
966 unsigned factor, tree *enter_cond,
967 tree *exit_base, tree *exit_step,
968 enum tree_code *exit_cmp, tree *exit_bound)
971 tree base = desc->control.base;
972 tree step = desc->control.step;
973 tree bound = desc->bound;
974 tree type = TREE_TYPE (step);
976 tree min = lower_bound_in_type (type, type);
977 tree max = upper_bound_in_type (type, type);
978 enum tree_code cmp = desc->cmp;
979 tree cond = boolean_true_node, assum;
981 /* For pointers, do the arithmetics in the type of step. */
982 base = fold_convert (type, base);
983 bound = fold_convert (type, bound);
985 *enter_cond = boolean_false_node;
986 *exit_base = NULL_TREE;
987 *exit_step = NULL_TREE;
988 *exit_cmp = ERROR_MARK;
989 *exit_bound = NULL_TREE;
990 gcc_assert (cmp != ERROR_MARK);
992 /* We only need to be correct when we answer question
993 "Do at least FACTOR more iterations remain?" in the unrolled loop.
994 Thus, transforming BASE + STEP * i <> BOUND to
995 BASE + STEP * i < BOUND is ok. */
998 if (tree_int_cst_sign_bit (step))
1003 else if (cmp == LT_EXPR)
1005 gcc_assert (!tree_int_cst_sign_bit (step));
1007 else if (cmp == GT_EXPR)
1009 gcc_assert (tree_int_cst_sign_bit (step));
1014 /* The main body of the loop may be entered iff:
1016 1) desc->may_be_zero is false.
1017 2) it is possible to check that there are at least FACTOR iterations
1018 of the loop, i.e., BOUND - step * FACTOR does not overflow.
1019 3) # of iterations is at least FACTOR */
1021 if (!integer_zerop (desc->may_be_zero))
1022 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1023 invert_truthvalue (desc->may_be_zero),
1026 bigstep = fold_build2 (MULT_EXPR, type, step,
1027 build_int_cst_type (type, factor));
1028 delta = fold_build2 (MINUS_EXPR, type, bigstep, step);
1030 assum = fold_build2 (GE_EXPR, boolean_type_node,
1032 fold_build2 (PLUS_EXPR, type, min, delta));
1034 assum = fold_build2 (LE_EXPR, boolean_type_node,
1036 fold_build2 (PLUS_EXPR, type, max, delta));
1037 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
1039 bound = fold_build2 (MINUS_EXPR, type, bound, delta);
1040 assum = fold_build2 (cmp, boolean_type_node, base, bound);
1041 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
1043 cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE);
1045 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1046 /* cond now may be a gimple comparison, which would be OK, but also any
1047 other gimple rhs (say a && b). In this case we need to force it to
1049 if (!is_gimple_condexpr (cond))
1051 cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
1053 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1057 base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE);
1059 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1060 bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE);
1062 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1065 *exit_step = bigstep;
1067 *exit_bound = bound;
1070 /* Scales the frequencies of all basic blocks in LOOP that are strictly
1071 dominated by BB by NUM/DEN. */
1074 scale_dominated_blocks_in_loop (struct loop *loop, basic_block bb,
1082 for (son = first_dom_son (CDI_DOMINATORS, bb);
1084 son = next_dom_son (CDI_DOMINATORS, son))
1086 if (!flow_bb_inside_loop_p (loop, son))
1088 scale_bbs_frequencies_int (&son, 1, num, den);
1089 scale_dominated_blocks_in_loop (loop, son, num, den);
1093 /* Unroll LOOP FACTOR times. DESC describes number of iterations of LOOP.
1094 EXIT is the exit of the loop to that DESC corresponds.
1096 If N is number of iterations of the loop and MAY_BE_ZERO is the condition
1097 under that loop exits in the first iteration even if N != 0,
1101 x = phi (init, next);
1109 becomes (with possibly the exit conditions formulated a bit differently,
1110 avoiding the need to create a new iv):
1112 if (MAY_BE_ZERO || N < FACTOR)
1117 x = phi (init, next);
1128 } while (N >= FACTOR);
1131 init' = phi (init, x);
1135 x = phi (init', next);
1143 Before the loop is unrolled, TRANSFORM is called for it (only for the
1144 unrolled loop, but not for its versioned copy). DATA is passed to
1147 /* Probability in % that the unrolled loop is entered. Just a guess. */
1148 #define PROB_UNROLLED_LOOP_ENTERED 90
1151 tree_transform_and_unroll_loop (struct loop *loop, unsigned factor,
1152 edge exit, struct tree_niter_desc *desc,
1153 transform_callback transform,
1157 tree ctr_before, ctr_after;
1158 tree enter_main_cond, exit_base, exit_step, exit_bound;
1159 enum tree_code exit_cmp;
1160 gphi *phi_old_loop, *phi_new_loop, *phi_rest;
1161 gphi_iterator psi_old_loop, psi_new_loop;
1162 tree init, next, new_init;
1163 struct loop *new_loop;
1164 basic_block rest, exit_bb;
1165 edge old_entry, new_entry, old_latch, precond_edge, new_exit;
1166 edge new_nonexit, e;
1167 gimple_stmt_iterator bsi;
1170 unsigned est_niter, prob_entry, scale_unrolled, scale_rest, freq_e, freq_h;
1171 unsigned new_est_niter, i, prob;
1172 unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
1174 auto_vec<edge> to_remove;
1176 est_niter = expected_loop_iterations (loop);
1177 determine_exit_conditions (loop, desc, factor,
1178 &enter_main_cond, &exit_base, &exit_step,
1179 &exit_cmp, &exit_bound);
1181 /* Let us assume that the unrolled loop is quite likely to be entered. */
1182 if (integer_nonzerop (enter_main_cond))
1183 prob_entry = REG_BR_PROB_BASE;
1185 prob_entry = PROB_UNROLLED_LOOP_ENTERED * REG_BR_PROB_BASE / 100;
1187 /* The values for scales should keep profile consistent, and somewhat close
1190 TODO: The current value of SCALE_REST makes it appear that the loop that
1191 is created by splitting the remaining iterations of the unrolled loop is
1192 executed the same number of times as the original loop, and with the same
1193 frequencies, which is obviously wrong. This does not appear to cause
1194 problems, so we do not bother with fixing it for now. To make the profile
1195 correct, we would need to change the probability of the exit edge of the
1196 loop, and recompute the distribution of frequencies in its body because
1197 of this change (scale the frequencies of blocks before and after the exit
1198 by appropriate factors). */
1199 scale_unrolled = prob_entry;
1200 scale_rest = REG_BR_PROB_BASE;
1202 new_loop = loop_version (loop, enter_main_cond, NULL,
1203 prob_entry, scale_unrolled, scale_rest, true);
1204 gcc_assert (new_loop != NULL);
1205 update_ssa (TODO_update_ssa);
1207 /* Determine the probability of the exit edge of the unrolled loop. */
1208 new_est_niter = est_niter / factor;
1210 /* Without profile feedback, loops for that we do not know a better estimate
1211 are assumed to roll 10 times. When we unroll such loop, it appears to
1212 roll too little, and it may even seem to be cold. To avoid this, we
1213 ensure that the created loop appears to roll at least 5 times (but at
1214 most as many times as before unrolling). */
1215 if (new_est_niter < 5)
1218 new_est_niter = est_niter;
1223 /* Prepare the cfg and update the phi nodes. Move the loop exit to the
1224 loop latch (and make its condition dummy, for the moment). */
1225 rest = loop_preheader_edge (new_loop)->src;
1226 precond_edge = single_pred_edge (rest);
1227 split_edge (loop_latch_edge (loop));
1228 exit_bb = single_pred (loop->latch);
1230 /* Since the exit edge will be removed, the frequency of all the blocks
1231 in the loop that are dominated by it must be scaled by
1232 1 / (1 - exit->probability). */
1233 scale_dominated_blocks_in_loop (loop, exit->src,
1235 REG_BR_PROB_BASE - exit->probability);
1237 bsi = gsi_last_bb (exit_bb);
1238 exit_if = gimple_build_cond (EQ_EXPR, integer_zero_node,
1240 NULL_TREE, NULL_TREE);
1242 gsi_insert_after (&bsi, exit_if, GSI_NEW_STMT);
1243 new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
1244 rescan_loop_exit (new_exit, true, false);
1246 /* Set the probability of new exit to the same of the old one. Fix
1247 the frequency of the latch block, by scaling it back by
1248 1 - exit->probability. */
1249 new_exit->count = exit->count;
1250 new_exit->probability = exit->probability;
1251 new_nonexit = single_pred_edge (loop->latch);
1252 new_nonexit->probability = REG_BR_PROB_BASE - exit->probability;
1253 new_nonexit->flags = EDGE_TRUE_VALUE;
1254 new_nonexit->count -= exit->count;
1255 if (new_nonexit->count < 0)
1256 new_nonexit->count = 0;
1257 scale_bbs_frequencies_int (&loop->latch, 1, new_nonexit->probability,
1260 old_entry = loop_preheader_edge (loop);
1261 new_entry = loop_preheader_edge (new_loop);
1262 old_latch = loop_latch_edge (loop);
1263 for (psi_old_loop = gsi_start_phis (loop->header),
1264 psi_new_loop = gsi_start_phis (new_loop->header);
1265 !gsi_end_p (psi_old_loop);
1266 gsi_next (&psi_old_loop), gsi_next (&psi_new_loop))
1268 phi_old_loop = psi_old_loop.phi ();
1269 phi_new_loop = psi_new_loop.phi ();
1271 init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry);
1272 op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry);
1273 gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
1274 next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch);
1276 /* Prefer using original variable as a base for the new ssa name.
1277 This is necessary for virtual ops, and useful in order to avoid
1278 losing debug info for real ops. */
1279 if (TREE_CODE (next) == SSA_NAME
1280 && useless_type_conversion_p (TREE_TYPE (next),
1282 new_init = copy_ssa_name (next);
1283 else if (TREE_CODE (init) == SSA_NAME
1284 && useless_type_conversion_p (TREE_TYPE (init),
1286 new_init = copy_ssa_name (init);
1287 else if (useless_type_conversion_p (TREE_TYPE (next), TREE_TYPE (init)))
1288 new_init = make_temp_ssa_name (TREE_TYPE (next), NULL, "unrinittmp");
1290 new_init = make_temp_ssa_name (TREE_TYPE (init), NULL, "unrinittmp");
1292 phi_rest = create_phi_node (new_init, rest);
1294 add_phi_arg (phi_rest, init, precond_edge, UNKNOWN_LOCATION);
1295 add_phi_arg (phi_rest, next, new_exit, UNKNOWN_LOCATION);
1296 SET_USE (op, new_init);
1301 /* Transform the loop. */
1303 (*transform) (loop, data);
1305 /* Unroll the loop and remove the exits in all iterations except for the
1307 wont_exit = sbitmap_alloc (factor);
1308 bitmap_ones (wont_exit);
1309 bitmap_clear_bit (wont_exit, factor - 1);
1311 ok = gimple_duplicate_loop_to_header_edge
1312 (loop, loop_latch_edge (loop), factor - 1,
1313 wont_exit, new_exit, &to_remove, DLTHE_FLAG_UPDATE_FREQ);
1317 FOR_EACH_VEC_ELT (to_remove, i, e)
1319 ok = remove_path (e);
1322 update_ssa (TODO_update_ssa);
1324 /* Ensure that the frequencies in the loop match the new estimated
1325 number of iterations, and change the probability of the new
1327 freq_h = loop->header->frequency;
1328 freq_e = EDGE_FREQUENCY (loop_preheader_edge (loop));
1330 scale_loop_frequencies (loop, freq_e * (new_est_niter + 1), freq_h);
1332 exit_bb = single_pred (loop->latch);
1333 new_exit = find_edge (exit_bb, rest);
1334 new_exit->count = loop_preheader_edge (loop)->count;
1335 new_exit->probability = REG_BR_PROB_BASE / (new_est_niter + 1);
1337 rest->count += new_exit->count;
1338 rest->frequency += EDGE_FREQUENCY (new_exit);
1340 new_nonexit = single_pred_edge (loop->latch);
1341 prob = new_nonexit->probability;
1342 new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability;
1343 new_nonexit->count = exit_bb->count - new_exit->count;
1344 if (new_nonexit->count < 0)
1345 new_nonexit->count = 0;
1347 scale_bbs_frequencies_int (&loop->latch, 1, new_nonexit->probability,
1350 /* Finally create the new counter for number of iterations and add the new
1351 exit instruction. */
1352 bsi = gsi_last_nondebug_bb (exit_bb);
1353 exit_if = as_a <gcond *> (gsi_stmt (bsi));
1354 create_iv (exit_base, exit_step, NULL_TREE, loop,
1355 &bsi, false, &ctr_before, &ctr_after);
1356 gimple_cond_set_code (exit_if, exit_cmp);
1357 gimple_cond_set_lhs (exit_if, ctr_after);
1358 gimple_cond_set_rhs (exit_if, exit_bound);
1359 update_stmt (exit_if);
1361 checking_verify_flow_info ();
1362 checking_verify_loop_structure ();
1363 checking_verify_loop_closed_ssa (true);
1366 /* Wrapper over tree_transform_and_unroll_loop for case we do not
1367 want to transform the loop before unrolling. The meaning
1368 of the arguments is the same as for tree_transform_and_unroll_loop. */
1371 tree_unroll_loop (struct loop *loop, unsigned factor,
1372 edge exit, struct tree_niter_desc *desc)
1374 tree_transform_and_unroll_loop (loop, factor, exit, desc,
1378 /* Rewrite the phi node at position PSI in function of the main
1379 induction variable MAIN_IV and insert the generated code at GSI. */
1382 rewrite_phi_with_iv (loop_p loop,
1384 gimple_stmt_iterator *gsi,
1389 gphi *phi = psi->phi ();
1390 tree atype, mtype, val, res = PHI_RESULT (phi);
1392 if (virtual_operand_p (res) || res == main_iv)
1398 if (!simple_iv (loop, loop, res, &iv, true))
1404 remove_phi_node (psi, false);
1406 atype = TREE_TYPE (res);
1407 mtype = POINTER_TYPE_P (atype) ? sizetype : atype;
1408 val = fold_build2 (MULT_EXPR, mtype, unshare_expr (iv.step),
1409 fold_convert (mtype, main_iv));
1410 val = fold_build2 (POINTER_TYPE_P (atype)
1411 ? POINTER_PLUS_EXPR : PLUS_EXPR,
1412 atype, unshare_expr (iv.base), val);
1413 val = force_gimple_operand_gsi (gsi, val, false, NULL_TREE, true,
1415 stmt = gimple_build_assign (res, val);
1416 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1419 /* Rewrite all the phi nodes of LOOP in function of the main induction
1420 variable MAIN_IV. */
1423 rewrite_all_phi_nodes_with_iv (loop_p loop, tree main_iv)
1426 basic_block *bbs = get_loop_body_in_dom_order (loop);
1429 for (i = 0; i < loop->num_nodes; i++)
1431 basic_block bb = bbs[i];
1432 gimple_stmt_iterator gsi = gsi_after_labels (bb);
1434 if (bb->loop_father != loop)
1437 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); )
1438 rewrite_phi_with_iv (loop, &psi, &gsi, main_iv);
1444 /* Bases all the induction variables in LOOP on a single induction variable
1445 (with base 0 and step 1), whose final value is compared with *NIT. When the
1446 IV type precision has to be larger than *NIT type precision, *NIT is
1447 converted to the larger type, the conversion code is inserted before the
1448 loop, and *NIT is updated to the new definition. When BUMP_IN_LATCH is true,
1449 the induction variable is incremented in the loop latch, otherwise it is
1450 incremented in the loop header. Return the induction variable that was
1454 canonicalize_loop_ivs (struct loop *loop, tree *nit, bool bump_in_latch)
1456 unsigned precision = TYPE_PRECISION (TREE_TYPE (*nit));
1457 unsigned original_precision = precision;
1458 tree type, var_before;
1459 gimple_stmt_iterator gsi;
1462 edge exit = single_dom_exit (loop);
1465 bool unsigned_p = false;
1467 for (psi = gsi_start_phis (loop->header);
1468 !gsi_end_p (psi); gsi_next (&psi))
1470 gphi *phi = psi.phi ();
1471 tree res = PHI_RESULT (phi);
1474 type = TREE_TYPE (res);
1475 if (virtual_operand_p (res)
1476 || (!INTEGRAL_TYPE_P (type)
1477 && !POINTER_TYPE_P (type))
1478 || TYPE_PRECISION (type) < precision)
1481 uns = POINTER_TYPE_P (type) | TYPE_UNSIGNED (type);
1483 if (TYPE_PRECISION (type) > precision)
1488 precision = TYPE_PRECISION (type);
1491 mode = smallest_mode_for_size (precision, MODE_INT);
1492 precision = GET_MODE_PRECISION (mode);
1493 type = build_nonstandard_integer_type (precision, unsigned_p);
1495 if (original_precision != precision)
1497 *nit = fold_convert (type, *nit);
1498 *nit = force_gimple_operand (*nit, &stmts, true, NULL_TREE);
1500 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1504 gsi = gsi_last_bb (loop->latch);
1506 gsi = gsi_last_nondebug_bb (loop->header);
1507 create_iv (build_int_cst_type (type, 0), build_int_cst (type, 1), NULL_TREE,
1508 loop, &gsi, bump_in_latch, &var_before, NULL);
1510 rewrite_all_phi_nodes_with_iv (loop, var_before);
1512 stmt = as_a <gcond *> (last_stmt (exit->src));
1513 /* Make the loop exit if the control condition is not satisfied. */
1514 if (exit->flags & EDGE_TRUE_VALUE)
1518 extract_true_false_edges_from_block (exit->src, &te, &fe);
1519 te->flags = EDGE_FALSE_VALUE;
1520 fe->flags = EDGE_TRUE_VALUE;
1522 gimple_cond_set_code (stmt, LT_EXPR);
1523 gimple_cond_set_lhs (stmt, var_before);
1524 gimple_cond_set_rhs (stmt, *nit);