1 /* High-level loop manipulation functions.
2 Copyright (C) 2004, 2005, 2006, 2007 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
))
90 if (!tree_expr_nonnegative_warnv_p (step
, &ovf
)
91 && may_negate_without_overflow_p (step
))
94 step
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (step
), step
);
99 /* Gimplify the step if necessary. We put the computations in front of the
100 loop (i.e. the step should be loop invariant). */
101 step
= force_gimple_operand (step
, &stmts
, true, var
);
103 bsi_insert_on_edge_immediate_loop (pe
, stmts
);
105 stmt
= build2 (MODIFY_EXPR
, void_type_node
, va
,
106 build2 (incr_op
, TREE_TYPE (base
),
108 SSA_NAME_DEF_STMT (va
) = stmt
;
110 bsi_insert_after (incr_pos
, stmt
, BSI_NEW_STMT
);
112 bsi_insert_before (incr_pos
, stmt
, BSI_NEW_STMT
);
114 initial
= force_gimple_operand (base
, &stmts
, true, var
);
116 bsi_insert_on_edge_immediate_loop (pe
, stmts
);
118 stmt
= create_phi_node (vb
, loop
->header
);
119 SSA_NAME_DEF_STMT (vb
) = stmt
;
120 add_phi_arg (stmt
, initial
, loop_preheader_edge (loop
));
121 add_phi_arg (stmt
, va
, loop_latch_edge (loop
));
124 /* Add exit phis for the USE on EXIT. */
127 add_exit_phis_edge (basic_block exit
, tree use
)
129 tree phi
, def_stmt
= SSA_NAME_DEF_STMT (use
);
130 basic_block def_bb
= bb_for_stmt (def_stmt
);
131 struct loop
*def_loop
;
135 /* Check that some of the edges entering the EXIT block exits a loop in
136 that USE is defined. */
137 FOR_EACH_EDGE (e
, ei
, exit
->preds
)
139 def_loop
= find_common_loop (def_bb
->loop_father
, e
->src
->loop_father
);
140 if (!flow_bb_inside_loop_p (def_loop
, e
->dest
))
147 phi
= create_phi_node (use
, exit
);
148 create_new_def_for (PHI_RESULT (phi
), phi
, PHI_RESULT_PTR (phi
));
149 FOR_EACH_EDGE (e
, ei
, exit
->preds
)
150 add_phi_arg (phi
, use
, e
);
153 /* Add exit phis for VAR that is used in LIVEIN.
154 Exits of the loops are stored in EXITS. */
157 add_exit_phis_var (tree var
, bitmap livein
, bitmap exits
)
161 basic_block def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (var
));
164 if (is_gimple_reg (var
))
165 bitmap_clear_bit (livein
, def_bb
->index
);
167 bitmap_set_bit (livein
, def_bb
->index
);
169 def
= BITMAP_ALLOC (NULL
);
170 bitmap_set_bit (def
, def_bb
->index
);
171 compute_global_livein (livein
, def
);
174 EXECUTE_IF_AND_IN_BITMAP (exits
, livein
, 0, index
, bi
)
176 add_exit_phis_edge (BASIC_BLOCK (index
), var
);
180 /* Add exit phis for the names marked in NAMES_TO_RENAME.
181 Exits of the loops are stored in EXITS. Sets of blocks where the ssa
182 names are used are stored in USE_BLOCKS. */
185 add_exit_phis (bitmap names_to_rename
, bitmap
*use_blocks
, bitmap loop_exits
)
190 EXECUTE_IF_SET_IN_BITMAP (names_to_rename
, 0, i
, bi
)
192 add_exit_phis_var (ssa_name (i
), use_blocks
[i
], loop_exits
);
196 /* Returns a bitmap of all loop exit edge targets. */
199 get_loops_exits (void)
201 bitmap exits
= BITMAP_ALLOC (NULL
);
208 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
209 if (e
->src
!= ENTRY_BLOCK_PTR
210 && !flow_bb_inside_loop_p (e
->src
->loop_father
, bb
))
212 bitmap_set_bit (exits
, bb
->index
);
220 /* For USE in BB, if it is used outside of the loop it is defined in,
221 mark it for rewrite. Record basic block BB where it is used
222 to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap. */
225 find_uses_to_rename_use (basic_block bb
, tree use
, bitmap
*use_blocks
,
230 struct loop
*def_loop
;
232 if (TREE_CODE (use
) != SSA_NAME
)
235 /* We don't need to keep virtual operands in loop-closed form. */
236 if (!is_gimple_reg (use
))
239 ver
= SSA_NAME_VERSION (use
);
240 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (use
));
243 def_loop
= def_bb
->loop_father
;
245 /* If the definition is not inside loop, it is not interesting. */
246 if (!def_loop
->outer
)
249 if (!use_blocks
[ver
])
250 use_blocks
[ver
] = BITMAP_ALLOC (NULL
);
251 bitmap_set_bit (use_blocks
[ver
], bb
->index
);
253 bitmap_set_bit (need_phis
, ver
);
256 /* For uses in STMT, mark names that are used outside of the loop they are
257 defined to rewrite. Record the set of blocks in that the ssa
258 names are defined to USE_BLOCKS and the ssa names themselves to
262 find_uses_to_rename_stmt (tree stmt
, bitmap
*use_blocks
, bitmap need_phis
)
266 basic_block bb
= bb_for_stmt (stmt
);
268 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_ALL_USES
| SSA_OP_ALL_KILLS
)
269 find_uses_to_rename_use (bb
, var
, use_blocks
, need_phis
);
272 /* Marks names that are used in BB and outside of the loop they are
273 defined in for rewrite. Records the set of blocks in that the ssa
274 names are defined to USE_BLOCKS. Record the SSA names that will
275 need exit PHIs in NEED_PHIS. */
278 find_uses_to_rename_bb (basic_block bb
, bitmap
*use_blocks
, bitmap need_phis
)
280 block_stmt_iterator bsi
;
285 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
286 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
287 find_uses_to_rename_use (bb
, PHI_ARG_DEF_FROM_EDGE (phi
, e
),
288 use_blocks
, need_phis
);
290 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
291 find_uses_to_rename_stmt (bsi_stmt (bsi
), use_blocks
, need_phis
);
294 /* Marks names that are used outside of the loop they are defined in
295 for rewrite. Records the set of blocks in that the ssa
296 names are defined to USE_BLOCKS. If CHANGED_BBS is not NULL,
297 scan only blocks in this set. */
300 find_uses_to_rename (bitmap changed_bbs
, bitmap
*use_blocks
, bitmap need_phis
)
306 if (changed_bbs
&& !bitmap_empty_p (changed_bbs
))
308 EXECUTE_IF_SET_IN_BITMAP (changed_bbs
, 0, index
, bi
)
310 find_uses_to_rename_bb (BASIC_BLOCK (index
), use_blocks
, need_phis
);
317 find_uses_to_rename_bb (bb
, use_blocks
, need_phis
);
322 /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
323 phi nodes to ensure that no variable is used outside the loop it is
326 This strengthening of the basic ssa form has several advantages:
328 1) Updating it during unrolling/peeling/versioning is trivial, since
329 we do not need to care about the uses outside of the loop.
330 2) The behavior of all uses of an induction variable is the same.
331 Without this, you need to distinguish the case when the variable
332 is used outside of the loop it is defined in, for example
334 for (i = 0; i < 100; i++)
336 for (j = 0; j < 100; j++)
344 Looking from the outer loop with the normal SSA form, the first use of k
345 is not well-behaved, while the second one is an induction variable with
348 If CHANGED_BBS is not NULL, we look for uses outside loops only in
349 the basic blocks in this set.
351 UPDATE_FLAG is used in the call to update_ssa. See
352 TODO_update_ssa* for documentation. */
355 rewrite_into_loop_closed_ssa (bitmap changed_bbs
, unsigned update_flag
)
357 bitmap loop_exits
= get_loops_exits ();
359 unsigned i
, old_num_ssa_names
;
360 bitmap names_to_rename
= BITMAP_ALLOC (NULL
);
362 /* If the pass has caused the SSA form to be out-of-date, update it
364 update_ssa (update_flag
);
366 old_num_ssa_names
= num_ssa_names
;
367 use_blocks
= XCNEWVEC (bitmap
, old_num_ssa_names
);
369 /* Find the uses outside loops. */
370 find_uses_to_rename (changed_bbs
, use_blocks
, names_to_rename
);
372 /* Add the PHI nodes on exits of the loops for the names we need to
374 add_exit_phis (names_to_rename
, use_blocks
, loop_exits
);
376 for (i
= 0; i
< old_num_ssa_names
; i
++)
377 BITMAP_FREE (use_blocks
[i
]);
379 BITMAP_FREE (loop_exits
);
380 BITMAP_FREE (names_to_rename
);
382 /* Fix up all the names found to be used outside their original
384 update_ssa (TODO_update_ssa
);
387 /* Check invariants of the loop closed ssa form for the USE in BB. */
390 check_loop_closed_ssa_use (basic_block bb
, tree use
)
395 if (TREE_CODE (use
) != SSA_NAME
|| !is_gimple_reg (use
))
398 def
= SSA_NAME_DEF_STMT (use
);
399 def_bb
= bb_for_stmt (def
);
401 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
404 /* Checks invariants of loop closed ssa form in statement STMT in BB. */
407 check_loop_closed_ssa_stmt (basic_block bb
, tree stmt
)
412 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_ALL_USES
| SSA_OP_ALL_KILLS
)
413 check_loop_closed_ssa_use (bb
, var
);
416 /* Checks that invariants of the loop closed ssa form are preserved. */
419 verify_loop_closed_ssa (void)
422 block_stmt_iterator bsi
;
426 if (current_loops
== NULL
)
433 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
434 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
435 check_loop_closed_ssa_use (PHI_ARG_EDGE (phi
, i
)->src
,
436 PHI_ARG_DEF (phi
, i
));
438 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
439 check_loop_closed_ssa_stmt (bb
, bsi_stmt (bsi
));
443 /* Split loop exit edge EXIT. The things are a bit complicated by a need to
444 preserve the loop closed ssa form. */
447 split_loop_exit_edge (edge exit
)
449 basic_block dest
= exit
->dest
;
450 basic_block bb
= loop_split_edge_with (exit
, NULL
);
451 tree phi
, new_phi
, new_name
, name
;
454 for (phi
= phi_nodes (dest
); phi
; phi
= PHI_CHAIN (phi
))
456 op_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, single_succ_edge (bb
));
458 name
= USE_FROM_PTR (op_p
);
460 /* If the argument of the phi node is a constant, we do not need
461 to keep it inside loop. */
462 if (TREE_CODE (name
) != SSA_NAME
)
465 /* Otherwise create an auxiliary phi node that will copy the value
466 of the ssa name out of the loop. */
467 new_name
= duplicate_ssa_name (name
, NULL
);
468 new_phi
= create_phi_node (new_name
, bb
);
469 SSA_NAME_DEF_STMT (new_name
) = new_phi
;
470 add_phi_arg (new_phi
, name
, exit
);
471 SET_USE (op_p
, new_name
);
475 /* Insert statement STMT to the edge E and update the loop structures.
476 Returns the newly created block (if any). */
479 bsi_insert_on_edge_immediate_loop (edge e
, tree stmt
)
481 basic_block src
, dest
, new_bb
;
487 loop_c
= find_common_loop (src
->loop_father
, dest
->loop_father
);
489 new_bb
= bsi_insert_on_edge_immediate (e
, stmt
);
494 add_bb_to_loop (new_bb
, loop_c
);
495 if (dest
->loop_father
->latch
== src
)
496 dest
->loop_father
->latch
= new_bb
;
501 /* Returns the basic block in that statements should be emitted for induction
502 variables incremented at the end of the LOOP. */
505 ip_end_pos (struct loop
*loop
)
510 /* Returns the basic block in that statements should be emitted for induction
511 variables incremented just before exit condition of a LOOP. */
514 ip_normal_pos (struct loop
*loop
)
520 if (!single_pred_p (loop
->latch
))
523 bb
= single_pred (loop
->latch
);
524 last
= last_stmt (bb
);
525 if (TREE_CODE (last
) != COND_EXPR
)
528 exit
= EDGE_SUCC (bb
, 0);
529 if (exit
->dest
== loop
->latch
)
530 exit
= EDGE_SUCC (bb
, 1);
532 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
538 /* Stores the standard position for induction variable increment in LOOP
539 (just before the exit condition if it is available and latch block is empty,
540 end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if
541 the increment should be inserted after *BSI. */
544 standard_iv_increment_position (struct loop
*loop
, block_stmt_iterator
*bsi
,
547 basic_block bb
= ip_normal_pos (loop
), latch
= ip_end_pos (loop
);
548 tree last
= last_stmt (latch
);
551 || (last
&& TREE_CODE (last
) != LABEL_EXPR
))
553 *bsi
= bsi_last (latch
);
554 *insert_after
= true;
558 *bsi
= bsi_last (bb
);
559 *insert_after
= false;
563 /* Copies phi node arguments for duplicated blocks. The index of the first
564 duplicated block is FIRST_NEW_BLOCK. */
567 copy_phi_node_args (unsigned first_new_block
)
571 for (i
= first_new_block
; i
< (unsigned) last_basic_block
; i
++)
572 BASIC_BLOCK (i
)->flags
|= BB_DUPLICATED
;
574 for (i
= first_new_block
; i
< (unsigned) last_basic_block
; i
++)
575 add_phi_args_after_copy_bb (BASIC_BLOCK (i
));
577 for (i
= first_new_block
; i
< (unsigned) last_basic_block
; i
++)
578 BASIC_BLOCK (i
)->flags
&= ~BB_DUPLICATED
;
582 /* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also
583 updates the PHI nodes at start of the copied region. In order to
584 achieve this, only loops whose exits all lead to the same location
587 Notice that we do not completely update the SSA web after
588 duplication. The caller is responsible for calling update_ssa
589 after the loop has been duplicated. */
592 tree_duplicate_loop_to_header_edge (struct loop
*loop
, edge e
,
594 unsigned int ndupl
, sbitmap wont_exit
,
595 edge orig
, edge
*to_remove
,
596 unsigned int *n_to_remove
, int flags
)
598 unsigned first_new_block
;
600 if (!(loops
->state
& LOOPS_HAVE_SIMPLE_LATCHES
))
602 if (!(loops
->state
& LOOPS_HAVE_PREHEADERS
))
605 #ifdef ENABLE_CHECKING
606 verify_loop_closed_ssa ();
609 first_new_block
= last_basic_block
;
610 if (!duplicate_loop_to_header_edge (loop
, e
, loops
, ndupl
, wont_exit
,
611 orig
, to_remove
, n_to_remove
, flags
))
614 /* Readd the removed phi args for e. */
615 flush_pending_stmts (e
);
617 /* Copy the phi node arguments. */
618 copy_phi_node_args (first_new_block
);
625 /* Build if (COND) goto THEN_LABEL; else goto ELSE_LABEL; */
628 build_if_stmt (tree cond
, tree then_label
, tree else_label
)
630 return build3 (COND_EXPR
, void_type_node
,
632 build1 (GOTO_EXPR
, void_type_node
, then_label
),
633 build1 (GOTO_EXPR
, void_type_node
, else_label
));
636 /* Returns true if we can unroll LOOP FACTOR times. Number
637 of iterations of the loop is returned in NITER. */
640 can_unroll_loop_p (struct loop
*loop
, unsigned factor
,
641 struct tree_niter_desc
*niter
)
645 /* Check whether unrolling is possible. We only want to unroll loops
646 for that we are able to determine number of iterations. We also
647 want to split the extra iterations of the loop from its end,
648 therefore we require that the loop has precisely one
651 exit
= single_dom_exit (loop
);
655 if (!number_of_iterations_exit (loop
, exit
, niter
, false)
656 || niter
->cmp
== ERROR_MARK
657 /* Scalar evolutions analysis might have copy propagated
658 the abnormal ssa names into these expressions, hence
659 emiting the computations based on them during loop
660 unrolling might create overlapping life ranges for
661 them, and failures in out-of-ssa. */
662 || contains_abnormal_ssa_name_p (niter
->may_be_zero
)
663 || contains_abnormal_ssa_name_p (niter
->control
.base
)
664 || contains_abnormal_ssa_name_p (niter
->control
.step
)
665 || contains_abnormal_ssa_name_p (niter
->bound
))
668 /* And of course, we must be able to duplicate the loop. */
669 if (!can_duplicate_loop_p (loop
))
672 /* The final loop should be small enough. */
673 if (tree_num_loop_insns (loop
) * factor
674 > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
))
680 /* Determines the conditions that control execution of LOOP unrolled FACTOR
681 times. DESC is number of iterations of LOOP. ENTER_COND is set to
682 condition that must be true if the main loop can be entered.
683 EXIT_BASE, EXIT_STEP, EXIT_CMP and EXIT_BOUND are set to values describing
684 how the exit from the unrolled loop should be controlled. */
687 determine_exit_conditions (struct loop
*loop
, struct tree_niter_desc
*desc
,
688 unsigned factor
, tree
*enter_cond
,
689 tree
*exit_base
, tree
*exit_step
,
690 enum tree_code
*exit_cmp
, tree
*exit_bound
)
693 tree base
= desc
->control
.base
;
694 tree step
= desc
->control
.step
;
695 tree bound
= desc
->bound
;
696 tree type
= TREE_TYPE (base
);
698 tree min
= lower_bound_in_type (type
, type
);
699 tree max
= upper_bound_in_type (type
, type
);
700 enum tree_code cmp
= desc
->cmp
;
701 tree cond
= boolean_true_node
, assum
;
703 *enter_cond
= boolean_false_node
;
704 *exit_base
= NULL_TREE
;
705 *exit_step
= NULL_TREE
;
706 *exit_cmp
= ERROR_MARK
;
707 *exit_bound
= NULL_TREE
;
708 gcc_assert (cmp
!= ERROR_MARK
);
710 /* We only need to be correct when we answer question
711 "Do at least FACTOR more iterations remain?" in the unrolled loop.
712 Thus, transforming BASE + STEP * i <> BOUND to
713 BASE + STEP * i < BOUND is ok. */
716 if (tree_int_cst_sign_bit (step
))
721 else if (cmp
== LT_EXPR
)
723 gcc_assert (!tree_int_cst_sign_bit (step
));
725 else if (cmp
== GT_EXPR
)
727 gcc_assert (tree_int_cst_sign_bit (step
));
732 /* The main body of the loop may be entered iff:
734 1) desc->may_be_zero is false.
735 2) it is possible to check that there are at least FACTOR iterations
736 of the loop, i.e., BOUND - step * FACTOR does not overflow.
737 3) # of iterations is at least FACTOR */
739 if (!zero_p (desc
->may_be_zero
))
740 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
741 invert_truthvalue (desc
->may_be_zero
),
744 bigstep
= fold_build2 (MULT_EXPR
, type
, step
,
745 build_int_cst_type (type
, factor
));
746 delta
= fold_build2 (MINUS_EXPR
, type
, bigstep
, step
);
748 assum
= fold_build2 (GE_EXPR
, boolean_type_node
,
750 fold_build2 (PLUS_EXPR
, type
, min
, delta
));
752 assum
= fold_build2 (LE_EXPR
, boolean_type_node
,
754 fold_build2 (PLUS_EXPR
, type
, max
, delta
));
755 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
, assum
, cond
);
757 bound
= fold_build2 (MINUS_EXPR
, type
, bound
, delta
);
758 assum
= fold_build2 (cmp
, boolean_type_node
, base
, bound
);
759 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
, assum
, cond
);
761 cond
= force_gimple_operand (unshare_expr (cond
), &stmts
, false, NULL_TREE
);
763 bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop
), stmts
);
764 /* cond now may be a gimple comparison, which would be OK, but also any
765 other gimple rhs (say a && b). In this case we need to force it to
767 if (!is_gimple_condexpr (cond
))
769 cond
= force_gimple_operand (cond
, &stmts
, true, NULL_TREE
);
771 bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop
), stmts
);
775 base
= force_gimple_operand (unshare_expr (base
), &stmts
, true, NULL_TREE
);
777 bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop
), stmts
);
778 bound
= force_gimple_operand (unshare_expr (bound
), &stmts
, true, NULL_TREE
);
780 bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop
), stmts
);
783 *exit_step
= bigstep
;
788 /* Unroll LOOP FACTOR times. LOOPS is the loops tree. DESC describes
789 number of iterations of LOOP. EXIT is the exit of the loop to that
792 If N is number of iterations of the loop and MAY_BE_ZERO is the condition
793 under that loop exits in the first iteration even if N != 0,
797 x = phi (init, next);
805 becomes (with possibly the exit conditions formulated a bit differently,
806 avoiding the need to create a new iv):
808 if (MAY_BE_ZERO || N < FACTOR)
813 x = phi (init, next);
824 } while (N >= FACTOR);
827 init' = phi (init, x);
831 x = phi (init', next);
840 tree_unroll_loop (struct loops
*loops
, struct loop
*loop
, unsigned factor
,
841 edge exit
, struct tree_niter_desc
*desc
)
843 tree dont_exit
, exit_if
, ctr_before
, ctr_after
;
844 tree enter_main_cond
, exit_base
, exit_step
, exit_bound
;
845 enum tree_code exit_cmp
;
846 tree phi_old_loop
, phi_new_loop
, phi_rest
, init
, next
, new_init
, var
;
847 struct loop
*new_loop
;
848 basic_block rest
, exit_bb
;
849 edge old_entry
, new_entry
, old_latch
, precond_edge
, new_exit
;
850 edge nonexit
, new_nonexit
;
851 block_stmt_iterator bsi
;
855 unsigned irr
= loop_preheader_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
;
858 est_niter
= expected_loop_iterations (loop
);
859 determine_exit_conditions (loop
, desc
, factor
,
860 &enter_main_cond
, &exit_base
, &exit_step
,
861 &exit_cmp
, &exit_bound
);
863 new_loop
= loop_version (loops
, loop
, enter_main_cond
, NULL
, true);
864 gcc_assert (new_loop
!= NULL
);
865 update_ssa (TODO_update_ssa
);
867 /* Unroll the loop and remove the old exits. */
868 dont_exit
= ((exit
->flags
& EDGE_TRUE_VALUE
)
870 : boolean_true_node
);
871 if (exit
== EDGE_SUCC (exit
->src
, 0))
872 nonexit
= EDGE_SUCC (exit
->src
, 1);
874 nonexit
= EDGE_SUCC (exit
->src
, 0);
875 nonexit
->probability
= REG_BR_PROB_BASE
;
876 exit
->probability
= 0;
877 nonexit
->count
+= exit
->count
;
879 exit_if
= last_stmt (exit
->src
);
880 COND_EXPR_COND (exit_if
) = dont_exit
;
881 update_stmt (exit_if
);
883 wont_exit
= sbitmap_alloc (factor
);
884 sbitmap_ones (wont_exit
);
885 ok
= tree_duplicate_loop_to_header_edge
886 (loop
, loop_latch_edge (loop
), loops
, factor
- 1,
887 wont_exit
, NULL
, NULL
, NULL
, DLTHE_FLAG_UPDATE_FREQ
);
890 update_ssa (TODO_update_ssa
);
892 /* Prepare the cfg and update the phi nodes. */
893 rest
= loop_preheader_edge (new_loop
)->src
;
894 precond_edge
= single_pred_edge (rest
);
895 loop_split_edge_with (loop_latch_edge (loop
), NULL
);
896 exit_bb
= single_pred (loop
->latch
);
898 new_exit
= make_edge (exit_bb
, rest
, EDGE_FALSE_VALUE
| irr
);
899 new_exit
->count
= loop_preheader_edge (loop
)->count
;
900 est_niter
= est_niter
/ factor
+ 1;
901 new_exit
->probability
= REG_BR_PROB_BASE
/ est_niter
;
903 new_nonexit
= single_pred_edge (loop
->latch
);
904 new_nonexit
->flags
= EDGE_TRUE_VALUE
;
905 new_nonexit
->probability
= REG_BR_PROB_BASE
- new_exit
->probability
;
907 old_entry
= loop_preheader_edge (loop
);
908 new_entry
= loop_preheader_edge (new_loop
);
909 old_latch
= loop_latch_edge (loop
);
910 for (phi_old_loop
= phi_nodes (loop
->header
),
911 phi_new_loop
= phi_nodes (new_loop
->header
);
913 phi_old_loop
= PHI_CHAIN (phi_old_loop
),
914 phi_new_loop
= PHI_CHAIN (phi_new_loop
))
916 init
= PHI_ARG_DEF_FROM_EDGE (phi_old_loop
, old_entry
);
917 op
= PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop
, new_entry
);
918 gcc_assert (operand_equal_for_phi_arg_p (init
, USE_FROM_PTR (op
)));
919 next
= PHI_ARG_DEF_FROM_EDGE (phi_old_loop
, old_latch
);
921 /* Prefer using original variable as a base for the new ssa name.
922 This is necessary for virtual ops, and useful in order to avoid
923 losing debug info for real ops. */
924 if (TREE_CODE (next
) == SSA_NAME
)
925 var
= SSA_NAME_VAR (next
);
926 else if (TREE_CODE (init
) == SSA_NAME
)
927 var
= SSA_NAME_VAR (init
);
930 var
= create_tmp_var (TREE_TYPE (init
), "unrinittmp");
931 add_referenced_var (var
);
934 new_init
= make_ssa_name (var
, NULL_TREE
);
935 phi_rest
= create_phi_node (new_init
, rest
);
936 SSA_NAME_DEF_STMT (new_init
) = phi_rest
;
938 add_phi_arg (phi_rest
, init
, precond_edge
);
939 add_phi_arg (phi_rest
, next
, new_exit
);
940 SET_USE (op
, new_init
);
943 /* Finally create the new counter for number of iterations and add the new
945 bsi
= bsi_last (exit_bb
);
946 create_iv (exit_base
, exit_step
, NULL_TREE
, loop
,
947 &bsi
, true, &ctr_before
, &ctr_after
);
948 exit_if
= build_if_stmt (build2 (exit_cmp
, boolean_type_node
, ctr_after
,
950 tree_block_label (loop
->latch
),
951 tree_block_label (rest
));
952 bsi_insert_after (&bsi
, exit_if
, BSI_NEW_STMT
);
955 verify_dominators (CDI_DOMINATORS
);
956 verify_loop_structure (loops
);
957 verify_loop_closed_ssa ();