1 /* High-level loop manipulation functions.
2 Copyright (C) 2004, 2005 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 2, 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 COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
36 #include "tree-pass.h"
37 #include "cfglayout.h"
38 #include "tree-scalar-evolution.h"
41 /* Creates an induction variable with value BASE + STEP * iteration in LOOP.
42 It is expected that neither BASE nor STEP are shared with other expressions
43 (unless the sharing rules allow this). Use VAR as a base var_decl for it
44 (if NULL, a new temporary will be created). The increment will occur at
45 INCR_POS (after it if AFTER is true, before it otherwise). INCR_POS and
46 AFTER can be computed using standard_iv_increment_position. The ssa versions
47 of the variable before and after increment will be stored in VAR_BEFORE and
48 VAR_AFTER (unless they are NULL). */
51 create_iv (tree base, tree step, tree var, struct loop *loop,
52 block_stmt_iterator *incr_pos, bool after,
53 tree *var_before, tree *var_after)
55 tree stmt, initial, step1, stmts;
57 enum tree_code incr_op = PLUS_EXPR;
58 edge pe = loop_preheader_edge (loop);
62 var = create_tmp_var (TREE_TYPE (base), "ivtmp");
63 add_referenced_var (var);
66 vb = make_ssa_name (var, NULL_TREE);
69 va = make_ssa_name (var, NULL_TREE);
73 /* For easier readability of the created code, produce MINUS_EXPRs
75 if (TREE_CODE (step) == INTEGER_CST)
77 if (TYPE_UNSIGNED (TREE_TYPE (step)))
79 step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
80 if (tree_int_cst_lt (step1, step))
88 if (!tree_expr_nonnegative_p (step)
89 && may_negate_without_overflow_p (step))
92 step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
97 /* Gimplify the step if necessary. We put the computations in front of the
98 loop (i.e. the step should be loop invariant). */
99 step = force_gimple_operand (step, &stmts, true, var);
101 bsi_insert_on_edge_immediate (pe, stmts);
103 stmt = build2_gimple (GIMPLE_MODIFY_STMT, va,
104 build2 (incr_op, TREE_TYPE (base), vb, step));
105 SSA_NAME_DEF_STMT (va) = stmt;
107 bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT);
109 bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT);
111 initial = force_gimple_operand (base, &stmts, true, var);
113 bsi_insert_on_edge_immediate (pe, stmts);
115 stmt = create_phi_node (vb, loop->header);
116 SSA_NAME_DEF_STMT (vb) = stmt;
117 add_phi_arg (stmt, initial, loop_preheader_edge (loop));
118 add_phi_arg (stmt, va, loop_latch_edge (loop));
121 /* Add exit phis for the USE on EXIT. */
124 add_exit_phis_edge (basic_block exit, tree use)
126 tree phi, def_stmt = SSA_NAME_DEF_STMT (use);
127 basic_block def_bb = bb_for_stmt (def_stmt);
128 struct loop *def_loop;
132 /* Check that some of the edges entering the EXIT block exits a loop in
133 that USE is defined. */
134 FOR_EACH_EDGE (e, ei, exit->preds)
136 def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
137 if (!flow_bb_inside_loop_p (def_loop, e->dest))
144 phi = create_phi_node (use, exit);
145 create_new_def_for (PHI_RESULT (phi), phi, PHI_RESULT_PTR (phi));
146 FOR_EACH_EDGE (e, ei, exit->preds)
147 add_phi_arg (phi, use, e);
150 /* Add exit phis for VAR that is used in LIVEIN.
151 Exits of the loops are stored in EXITS. */
154 add_exit_phis_var (tree var, bitmap livein, bitmap exits)
158 basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
161 if (is_gimple_reg (var))
162 bitmap_clear_bit (livein, def_bb->index);
164 bitmap_set_bit (livein, def_bb->index);
166 def = BITMAP_ALLOC (NULL);
167 bitmap_set_bit (def, def_bb->index);
168 compute_global_livein (livein, def);
171 EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi)
173 add_exit_phis_edge (BASIC_BLOCK (index), var);
177 /* Add exit phis for the names marked in NAMES_TO_RENAME.
178 Exits of the loops are stored in EXITS. Sets of blocks where the ssa
179 names are used are stored in USE_BLOCKS. */
182 add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
187 EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
189 add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
193 /* Returns a bitmap of all loop exit edge targets. */
196 get_loops_exits (void)
198 bitmap exits = BITMAP_ALLOC (NULL);
205 FOR_EACH_EDGE (e, ei, bb->preds)
206 if (e->src != ENTRY_BLOCK_PTR
207 && !flow_bb_inside_loop_p (e->src->loop_father, bb))
209 bitmap_set_bit (exits, bb->index);
217 /* For USE in BB, if it is used outside of the loop it is defined in,
218 mark it for rewrite. Record basic block BB where it is used
219 to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap. */
222 find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks,
227 struct loop *def_loop;
229 if (TREE_CODE (use) != SSA_NAME)
232 /* We don't need to keep virtual operands in loop-closed form. */
233 if (!is_gimple_reg (use))
236 ver = SSA_NAME_VERSION (use);
237 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
240 def_loop = def_bb->loop_father;
242 /* If the definition is not inside loop, it is not interesting. */
243 if (!def_loop->outer)
246 if (!use_blocks[ver])
247 use_blocks[ver] = BITMAP_ALLOC (NULL);
248 bitmap_set_bit (use_blocks[ver], bb->index);
250 bitmap_set_bit (need_phis, ver);
253 /* For uses in STMT, mark names that are used outside of the loop they are
254 defined to rewrite. Record the set of blocks in that the ssa
255 names are defined to USE_BLOCKS and the ssa names themselves to
259 find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks, bitmap need_phis)
263 basic_block bb = bb_for_stmt (stmt);
265 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
266 find_uses_to_rename_use (bb, var, use_blocks, need_phis);
269 /* Marks names that are used in BB and outside of the loop they are
270 defined in for rewrite. Records the set of blocks in that the ssa
271 names are defined to USE_BLOCKS. Record the SSA names that will
272 need exit PHIs in NEED_PHIS. */
275 find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis)
277 block_stmt_iterator bsi;
282 FOR_EACH_EDGE (e, ei, bb->succs)
283 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
284 find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
285 use_blocks, need_phis);
287 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
288 find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks, need_phis);
291 /* Marks names that are used outside of the loop they are defined in
292 for rewrite. Records the set of blocks in that the ssa
293 names are defined to USE_BLOCKS. If CHANGED_BBS is not NULL,
294 scan only blocks in this set. */
297 find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis)
303 if (changed_bbs && !bitmap_empty_p (changed_bbs))
305 EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi)
307 find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks, need_phis);
314 find_uses_to_rename_bb (bb, use_blocks, need_phis);
319 /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
320 phi nodes to ensure that no variable is used outside the loop it is
323 This strengthening of the basic ssa form has several advantages:
325 1) Updating it during unrolling/peeling/versioning is trivial, since
326 we do not need to care about the uses outside of the loop.
327 2) The behavior of all uses of an induction variable is the same.
328 Without this, you need to distinguish the case when the variable
329 is used outside of the loop it is defined in, for example
331 for (i = 0; i < 100; i++)
333 for (j = 0; j < 100; j++)
341 Looking from the outer loop with the normal SSA form, the first use of k
342 is not well-behaved, while the second one is an induction variable with
345 If CHANGED_BBS is not NULL, we look for uses outside loops only in
346 the basic blocks in this set.
348 UPDATE_FLAG is used in the call to update_ssa. See
349 TODO_update_ssa* for documentation. */
352 rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
354 bitmap loop_exits = get_loops_exits ();
356 unsigned i, old_num_ssa_names;
357 bitmap names_to_rename = BITMAP_ALLOC (NULL);
359 /* If the pass has caused the SSA form to be out-of-date, update it
361 update_ssa (update_flag);
363 old_num_ssa_names = num_ssa_names;
364 use_blocks = XCNEWVEC (bitmap, old_num_ssa_names);
366 /* Find the uses outside loops. */
367 find_uses_to_rename (changed_bbs, use_blocks, names_to_rename);
369 /* Add the PHI nodes on exits of the loops for the names we need to
371 add_exit_phis (names_to_rename, use_blocks, loop_exits);
373 for (i = 0; i < old_num_ssa_names; i++)
374 BITMAP_FREE (use_blocks[i]);
376 BITMAP_FREE (loop_exits);
377 BITMAP_FREE (names_to_rename);
379 /* Fix up all the names found to be used outside their original
381 update_ssa (TODO_update_ssa);
384 /* Check invariants of the loop closed ssa form for the USE in BB. */
387 check_loop_closed_ssa_use (basic_block bb, tree use)
392 if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use))
395 def = SSA_NAME_DEF_STMT (use);
396 def_bb = bb_for_stmt (def);
398 || flow_bb_inside_loop_p (def_bb->loop_father, bb));
401 /* Checks invariants of loop closed ssa form in statement STMT in BB. */
404 check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
409 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
410 check_loop_closed_ssa_use (bb, var);
413 /* Checks that invariants of the loop closed ssa form are preserved. */
416 verify_loop_closed_ssa (void)
419 block_stmt_iterator bsi;
423 if (current_loops == NULL)
430 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
431 for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
432 check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
433 PHI_ARG_DEF (phi, i));
435 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
436 check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
440 /* Split loop exit edge EXIT. The things are a bit complicated by a need to
441 preserve the loop closed ssa form. */
444 split_loop_exit_edge (edge exit)
446 basic_block dest = exit->dest;
447 basic_block bb = split_edge (exit);
448 tree phi, new_phi, new_name, name;
451 for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
453 op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb));
455 name = USE_FROM_PTR (op_p);
457 /* If the argument of the PHI node is a constant, we do not need
458 to keep it inside loop. */
459 if (TREE_CODE (name) != SSA_NAME)
462 /* Otherwise create an auxiliary phi node that will copy the value
463 of the SSA name out of the loop. */
464 new_name = duplicate_ssa_name (name, NULL);
465 new_phi = create_phi_node (new_name, bb);
466 SSA_NAME_DEF_STMT (new_name) = new_phi;
467 add_phi_arg (new_phi, name, exit);
468 SET_USE (op_p, new_name);
472 /* Returns the basic block in that statements should be emitted for induction
473 variables incremented at the end of the LOOP. */
476 ip_end_pos (struct loop *loop)
481 /* Returns the basic block in that statements should be emitted for induction
482 variables incremented just before exit condition of a LOOP. */
485 ip_normal_pos (struct loop *loop)
491 if (!single_pred_p (loop->latch))
494 bb = single_pred (loop->latch);
495 last = last_stmt (bb);
496 if (TREE_CODE (last) != COND_EXPR)
499 exit = EDGE_SUCC (bb, 0);
500 if (exit->dest == loop->latch)
501 exit = EDGE_SUCC (bb, 1);
503 if (flow_bb_inside_loop_p (loop, exit->dest))
509 /* Stores the standard position for induction variable increment in LOOP
510 (just before the exit condition if it is available and latch block is empty,
511 end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if
512 the increment should be inserted after *BSI. */
515 standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
518 basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
519 tree last = last_stmt (latch);
522 || (last && TREE_CODE (last) != LABEL_EXPR))
524 *bsi = bsi_last (latch);
525 *insert_after = true;
529 *bsi = bsi_last (bb);
530 *insert_after = false;
534 /* Copies phi node arguments for duplicated blocks. The index of the first
535 duplicated block is FIRST_NEW_BLOCK. */
538 copy_phi_node_args (unsigned first_new_block)
542 for (i = first_new_block; i < (unsigned) last_basic_block; i++)
543 BASIC_BLOCK (i)->flags |= BB_DUPLICATED;
545 for (i = first_new_block; i < (unsigned) last_basic_block; i++)
546 add_phi_args_after_copy_bb (BASIC_BLOCK (i));
548 for (i = first_new_block; i < (unsigned) last_basic_block; i++)
549 BASIC_BLOCK (i)->flags &= ~BB_DUPLICATED;
553 /* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also
554 updates the PHI nodes at start of the copied region. In order to
555 achieve this, only loops whose exits all lead to the same location
558 Notice that we do not completely update the SSA web after
559 duplication. The caller is responsible for calling update_ssa
560 after the loop has been duplicated. */
563 tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
564 unsigned int ndupl, sbitmap wont_exit,
565 edge orig, VEC (edge, heap) **to_remove,
568 unsigned first_new_block;
570 if (!(current_loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
572 if (!(current_loops->state & LOOPS_HAVE_PREHEADERS))
575 #ifdef ENABLE_CHECKING
576 verify_loop_closed_ssa ();
579 first_new_block = last_basic_block;
580 if (!duplicate_loop_to_header_edge (loop, e, ndupl, wont_exit,
581 orig, to_remove, flags))
584 /* Readd the removed phi args for e. */
585 flush_pending_stmts (e);
587 /* Copy the phi node arguments. */
588 copy_phi_node_args (first_new_block);
595 /* Build if (COND) goto THEN_LABEL; else goto ELSE_LABEL; */
598 build_if_stmt (tree cond, tree then_label, tree else_label)
600 return build3 (COND_EXPR, void_type_node,
602 build1 (GOTO_EXPR, void_type_node, then_label),
603 build1 (GOTO_EXPR, void_type_node, else_label));
606 /* Returns true if we can unroll LOOP FACTOR times. Number
607 of iterations of the loop is returned in NITER. */
610 can_unroll_loop_p (struct loop *loop, unsigned factor,
611 struct tree_niter_desc *niter)
615 /* Check whether unrolling is possible. We only want to unroll loops
616 for that we are able to determine number of iterations. We also
617 want to split the extra iterations of the loop from its end,
618 therefore we require that the loop has precisely one
621 exit = single_dom_exit (loop);
625 if (!number_of_iterations_exit (loop, exit, niter, false)
626 || niter->cmp == ERROR_MARK
627 /* Scalar evolutions analysis might have copy propagated
628 the abnormal ssa names into these expressions, hence
629 emitting the computations based on them during loop
630 unrolling might create overlapping life ranges for
631 them, and failures in out-of-ssa. */
632 || contains_abnormal_ssa_name_p (niter->may_be_zero)
633 || contains_abnormal_ssa_name_p (niter->control.base)
634 || contains_abnormal_ssa_name_p (niter->control.step)
635 || contains_abnormal_ssa_name_p (niter->bound))
638 /* And of course, we must be able to duplicate the loop. */
639 if (!can_duplicate_loop_p (loop))
642 /* The final loop should be small enough. */
643 if (tree_num_loop_insns (loop) * factor
644 > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS))
650 /* Determines the conditions that control execution of LOOP unrolled FACTOR
651 times. DESC is number of iterations of LOOP. ENTER_COND is set to
652 condition that must be true if the main loop can be entered.
653 EXIT_BASE, EXIT_STEP, EXIT_CMP and EXIT_BOUND are set to values describing
654 how the exit from the unrolled loop should be controlled. */
657 determine_exit_conditions (struct loop *loop, struct tree_niter_desc *desc,
658 unsigned factor, tree *enter_cond,
659 tree *exit_base, tree *exit_step,
660 enum tree_code *exit_cmp, tree *exit_bound)
663 tree base = desc->control.base;
664 tree step = desc->control.step;
665 tree bound = desc->bound;
666 tree type = TREE_TYPE (base);
668 tree min = lower_bound_in_type (type, type);
669 tree max = upper_bound_in_type (type, type);
670 enum tree_code cmp = desc->cmp;
671 tree cond = boolean_true_node, assum;
673 *enter_cond = boolean_false_node;
674 *exit_base = NULL_TREE;
675 *exit_step = NULL_TREE;
676 *exit_cmp = ERROR_MARK;
677 *exit_bound = NULL_TREE;
678 gcc_assert (cmp != ERROR_MARK);
680 /* We only need to be correct when we answer question
681 "Do at least FACTOR more iterations remain?" in the unrolled loop.
682 Thus, transforming BASE + STEP * i <> BOUND to
683 BASE + STEP * i < BOUND is ok. */
686 if (tree_int_cst_sign_bit (step))
691 else if (cmp == LT_EXPR)
693 gcc_assert (!tree_int_cst_sign_bit (step));
695 else if (cmp == GT_EXPR)
697 gcc_assert (tree_int_cst_sign_bit (step));
702 /* The main body of the loop may be entered iff:
704 1) desc->may_be_zero is false.
705 2) it is possible to check that there are at least FACTOR iterations
706 of the loop, i.e., BOUND - step * FACTOR does not overflow.
707 3) # of iterations is at least FACTOR */
709 if (!integer_zerop (desc->may_be_zero))
710 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
711 invert_truthvalue (desc->may_be_zero),
714 bigstep = fold_build2 (MULT_EXPR, type, step,
715 build_int_cst_type (type, factor));
716 delta = fold_build2 (MINUS_EXPR, type, bigstep, step);
718 assum = fold_build2 (GE_EXPR, boolean_type_node,
720 fold_build2 (PLUS_EXPR, type, min, delta));
722 assum = fold_build2 (LE_EXPR, boolean_type_node,
724 fold_build2 (PLUS_EXPR, type, max, delta));
725 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
727 bound = fold_build2 (MINUS_EXPR, type, bound, delta);
728 assum = fold_build2 (cmp, boolean_type_node, base, bound);
729 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
731 cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE);
733 bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
734 /* cond now may be a gimple comparison, which would be OK, but also any
735 other gimple rhs (say a && b). In this case we need to force it to
737 if (!is_gimple_condexpr (cond))
739 cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
741 bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
745 base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE);
747 bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
748 bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE);
750 bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
753 *exit_step = bigstep;
758 /* Unroll LOOP FACTOR times. DESC describes number of iterations of LOOP.
759 EXIT is the exit of the loop to that DESC corresponds.
761 If N is number of iterations of the loop and MAY_BE_ZERO is the condition
762 under that loop exits in the first iteration even if N != 0,
766 x = phi (init, next);
774 becomes (with possibly the exit conditions formulated a bit differently,
775 avoiding the need to create a new iv):
777 if (MAY_BE_ZERO || N < FACTOR)
782 x = phi (init, next);
793 } while (N >= FACTOR);
796 init' = phi (init, x);
800 x = phi (init', next);
808 Before the loop is unrolled, TRANSFORM is called for it (only for the
809 unrolled loop, but not for its versioned copy). DATA is passed to
812 /* Probability in % that the unrolled loop is entered. Just a guess. */
813 #define PROB_UNROLLED_LOOP_ENTERED 90
816 tree_transform_and_unroll_loop (struct loop *loop, unsigned factor,
817 edge exit, struct tree_niter_desc *desc,
818 transform_callback transform,
821 tree dont_exit, exit_if, ctr_before, ctr_after;
822 tree enter_main_cond, exit_base, exit_step, exit_bound;
823 enum tree_code exit_cmp;
824 tree phi_old_loop, phi_new_loop, phi_rest, init, next, new_init, var;
825 struct loop *new_loop;
826 basic_block rest, exit_bb;
827 edge old_entry, new_entry, old_latch, precond_edge, new_exit;
829 block_stmt_iterator bsi;
832 unsigned est_niter, prob_entry, scale_unrolled, scale_rest, freq_e, freq_h;
833 unsigned new_est_niter;
834 unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
837 est_niter = expected_loop_iterations (loop);
838 determine_exit_conditions (loop, desc, factor,
839 &enter_main_cond, &exit_base, &exit_step,
840 &exit_cmp, &exit_bound);
842 /* Let us assume that the unrolled loop is quite likely to be entered. */
843 if (integer_nonzerop (enter_main_cond))
844 prob_entry = REG_BR_PROB_BASE;
846 prob_entry = PROB_UNROLLED_LOOP_ENTERED * REG_BR_PROB_BASE / 100;
848 /* The values for scales should keep profile consistent, and somewhat close
851 TODO: The current value of SCALE_REST makes it appear that the loop that
852 is created by splitting the remaining iterations of the unrolled loop is
853 executed the same number of times as the original loop, and with the same
854 frequencies, which is obviously wrong. This does not appear to cause
855 problems, so we do not bother with fixing it for now. To make the profile
856 correct, we would need to change the probability of the exit edge of the
857 loop, and recompute the distribution of frequencies in its body because
858 of this change (scale the frequencies of blocks before and after the exit
859 by appropriate factors). */
860 scale_unrolled = prob_entry;
861 scale_rest = REG_BR_PROB_BASE;
863 new_loop = loop_version (loop, enter_main_cond, NULL,
864 prob_entry, scale_unrolled, scale_rest, true);
865 gcc_assert (new_loop != NULL);
866 update_ssa (TODO_update_ssa);
868 /* Determine the probability of the exit edge of the unrolled loop. */
869 new_est_niter = est_niter / factor;
871 /* Without profile feedback, loops for that we do not know a better estimate
872 are assumed to roll 10 times. When we unroll such loop, it appears to
873 roll too little, and it may even seem to be cold. To avoid this, we
874 ensure that the created loop appears to roll at least 5 times (but at
875 most as many times as before unrolling). */
876 if (new_est_niter < 5)
879 new_est_niter = est_niter;
884 /* Prepare the cfg and update the phi nodes. */
885 rest = loop_preheader_edge (new_loop)->src;
886 precond_edge = single_pred_edge (rest);
887 split_edge (loop_latch_edge (loop));
888 exit_bb = single_pred (loop->latch);
890 /* For the moment, make it appear that the new exit edge cannot
892 bsi = bsi_last (exit_bb);
893 exit_if = build_if_stmt (boolean_true_node,
894 tree_block_label (loop->latch),
895 tree_block_label (rest));
896 bsi_insert_after (&bsi, exit_if, BSI_NEW_STMT);
897 new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
898 rescan_loop_exit (new_exit, true, false);
900 new_exit->probability = 0;
901 new_nonexit = single_pred_edge (loop->latch);
902 new_nonexit->flags = EDGE_TRUE_VALUE;
904 old_entry = loop_preheader_edge (loop);
905 new_entry = loop_preheader_edge (new_loop);
906 old_latch = loop_latch_edge (loop);
907 for (phi_old_loop = phi_nodes (loop->header),
908 phi_new_loop = phi_nodes (new_loop->header);
910 phi_old_loop = PHI_CHAIN (phi_old_loop),
911 phi_new_loop = PHI_CHAIN (phi_new_loop))
913 init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry);
914 op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry);
915 gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
916 next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch);
918 /* Prefer using original variable as a base for the new ssa name.
919 This is necessary for virtual ops, and useful in order to avoid
920 losing debug info for real ops. */
921 if (TREE_CODE (next) == SSA_NAME)
922 var = SSA_NAME_VAR (next);
923 else if (TREE_CODE (init) == SSA_NAME)
924 var = SSA_NAME_VAR (init);
927 var = create_tmp_var (TREE_TYPE (init), "unrinittmp");
928 add_referenced_var (var);
931 new_init = make_ssa_name (var, NULL_TREE);
932 phi_rest = create_phi_node (new_init, rest);
933 SSA_NAME_DEF_STMT (new_init) = phi_rest;
935 add_phi_arg (phi_rest, init, precond_edge);
936 add_phi_arg (phi_rest, next, new_exit);
937 SET_USE (op, new_init);
940 /* Transform the loop. */
942 (*transform) (loop, data);
944 /* Unroll the loop and remove the old exits. */
945 dont_exit = ((exit->flags & EDGE_TRUE_VALUE)
947 : boolean_true_node);
948 exit_if = last_stmt (exit->src);
949 COND_EXPR_COND (exit_if) = dont_exit;
950 update_stmt (exit_if);
952 wont_exit = sbitmap_alloc (factor);
953 sbitmap_ones (wont_exit);
954 ok = tree_duplicate_loop_to_header_edge
955 (loop, loop_latch_edge (loop), factor - 1,
956 wont_exit, exit, NULL, DLTHE_FLAG_UPDATE_FREQ);
959 update_ssa (TODO_update_ssa);
961 /* Ensure that the frequencies in the loop match the new estimated
962 number of iterations, and change the probability of the new
964 freq_h = loop->header->frequency;
965 freq_e = EDGE_FREQUENCY (loop_preheader_edge (loop));
967 scale_loop_frequencies (loop, freq_e * (new_est_niter + 1), freq_h);
969 exit_bb = single_pred (loop->latch);
970 new_exit = find_edge (exit_bb, rest);
971 new_exit->count = loop_preheader_edge (loop)->count;
972 new_exit->probability = REG_BR_PROB_BASE / (new_est_niter + 1);
974 rest->count += new_exit->count;
975 rest->frequency += EDGE_FREQUENCY (new_exit);
977 new_nonexit = single_pred_edge (loop->latch);
978 new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability;
979 scale_bbs_frequencies_int (&loop->latch, 1, new_nonexit->probability,
982 /* Finally create the new counter for number of iterations and add the new
984 bsi = bsi_last (exit_bb);
985 exit_if = bsi_stmt (bsi);
986 create_iv (exit_base, exit_step, NULL_TREE, loop,
987 &bsi, false, &ctr_before, &ctr_after);
988 COND_EXPR_COND (exit_if) = build2 (exit_cmp, boolean_type_node, ctr_after,
990 update_stmt (exit_if);
992 #ifdef ENABLE_CHECKING
994 verify_dominators (CDI_DOMINATORS);
995 verify_loop_structure ();
996 verify_loop_closed_ssa ();
1000 /* Wrapper over tree_transform_and_unroll_loop for case we do not
1001 want to transform the loop before unrolling. The meaning
1002 of the arguments is the same as for tree_transform_and_unroll_loop. */
1005 tree_unroll_loop (struct loop *loop, unsigned factor,
1006 edge exit, struct tree_niter_desc *desc)
1008 tree_transform_and_unroll_loop (loop, factor, exit, desc,