1 /* Loop manipulation code for GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
26 #include "basic-block.h"
28 #include "tree-flow.h"
31 static void copy_loops_to (struct loop
**, int,
33 static void loop_redirect_edge (edge
, basic_block
);
34 static void remove_bbs (basic_block
*, int);
35 static bool rpe_enum_p (const_basic_block
, const void *);
36 static int find_path (edge
, basic_block
**);
37 static void fix_loop_placements (struct loop
*, bool *);
38 static bool fix_bb_placement (basic_block
);
39 static void fix_bb_placements (basic_block
, bool *);
40 static void unloop (struct loop
*, bool *);
42 /* Checks whether basic block BB is dominated by DATA. */
44 rpe_enum_p (const_basic_block bb
, const void *data
)
46 return dominated_by_p (CDI_DOMINATORS
, bb
, (const_basic_block
) data
);
49 /* Remove basic blocks BBS. NBBS is the number of the basic blocks. */
52 remove_bbs (basic_block
*bbs
, int nbbs
)
56 for (i
= 0; i
< nbbs
; i
++)
57 delete_basic_block (bbs
[i
]);
60 /* Find path -- i.e. the basic blocks dominated by edge E and put them
61 into array BBS, that will be allocated large enough to contain them.
62 E->dest must have exactly one predecessor for this to work (it is
63 easy to achieve and we do not put it here because we do not want to
64 alter anything by this function). The number of basic blocks in the
67 find_path (edge e
, basic_block
**bbs
)
69 gcc_assert (EDGE_COUNT (e
->dest
->preds
) <= 1);
71 /* Find bbs in the path. */
72 *bbs
= XNEWVEC (basic_block
, n_basic_blocks
);
73 return dfs_enumerate_from (e
->dest
, 0, rpe_enum_p
, *bbs
,
74 n_basic_blocks
, e
->dest
);
77 /* Fix placement of basic block BB inside loop hierarchy --
78 Let L be a loop to that BB belongs. Then every successor of BB must either
79 1) belong to some superloop of loop L, or
80 2) be a header of loop K such that K->outer is superloop of L
81 Returns true if we had to move BB into other loop to enforce this condition,
82 false if the placement of BB was already correct (provided that placements
83 of its successors are correct). */
85 fix_bb_placement (basic_block bb
)
89 struct loop
*loop
= current_loops
->tree_root
, *act
;
91 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
93 if (e
->dest
== EXIT_BLOCK_PTR
)
96 act
= e
->dest
->loop_father
;
97 if (act
->header
== e
->dest
)
98 act
= loop_outer (act
);
100 if (flow_loop_nested_p (loop
, act
))
104 if (loop
== bb
->loop_father
)
107 remove_bb_from_loops (bb
);
108 add_bb_to_loop (bb
, loop
);
113 /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
114 of LOOP to that leads at least one exit edge of LOOP, and set it
115 as the immediate superloop of LOOP. Return true if the immediate superloop
119 fix_loop_placement (struct loop
*loop
)
123 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
124 struct loop
*father
= current_loops
->tree_root
, *act
;
127 FOR_EACH_VEC_ELT (edge
, exits
, i
, e
)
129 act
= find_common_loop (loop
, e
->dest
->loop_father
);
130 if (flow_loop_nested_p (father
, act
))
134 if (father
!= loop_outer (loop
))
136 for (act
= loop_outer (loop
); act
!= father
; act
= loop_outer (act
))
137 act
->num_nodes
-= loop
->num_nodes
;
138 flow_loop_tree_node_remove (loop
);
139 flow_loop_tree_node_add (father
, loop
);
141 /* The exit edges of LOOP no longer exits its original immediate
142 superloops; remove them from the appropriate exit lists. */
143 FOR_EACH_VEC_ELT (edge
, exits
, i
, e
)
144 rescan_loop_exit (e
, false, false);
149 VEC_free (edge
, heap
, exits
);
153 /* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
154 enforce condition condition stated in description of fix_bb_placement. We
155 start from basic block FROM that had some of its successors removed, so that
156 his placement no longer has to be correct, and iteratively fix placement of
157 its predecessors that may change if placement of FROM changed. Also fix
158 placement of subloops of FROM->loop_father, that might also be altered due
159 to this change; the condition for them is similar, except that instead of
160 successors we consider edges coming out of the loops.
162 If the changes may invalidate the information about irreducible regions,
163 IRRED_INVALIDATED is set to true. */
166 fix_bb_placements (basic_block from
,
167 bool *irred_invalidated
)
170 basic_block
*queue
, *qtop
, *qbeg
, *qend
;
171 struct loop
*base_loop
, *target_loop
;
174 /* We pass through blocks back-reachable from FROM, testing whether some
175 of their successors moved to outer loop. It may be necessary to
176 iterate several times, but it is finite, as we stop unless we move
177 the basic block up the loop structure. The whole story is a bit
178 more complicated due to presence of subloops, those are moved using
179 fix_loop_placement. */
181 base_loop
= from
->loop_father
;
182 /* If we are already in the outermost loop, the basic blocks cannot be moved
183 outside of it. If FROM is the header of the base loop, it cannot be moved
184 outside of it, either. In both cases, we can end now. */
185 if (base_loop
== current_loops
->tree_root
186 || from
== base_loop
->header
)
189 in_queue
= sbitmap_alloc (last_basic_block
);
190 sbitmap_zero (in_queue
);
191 SET_BIT (in_queue
, from
->index
);
192 /* Prevent us from going out of the base_loop. */
193 SET_BIT (in_queue
, base_loop
->header
->index
);
195 queue
= XNEWVEC (basic_block
, base_loop
->num_nodes
+ 1);
196 qtop
= queue
+ base_loop
->num_nodes
+ 1;
208 RESET_BIT (in_queue
, from
->index
);
210 if (from
->loop_father
->header
== from
)
212 /* Subloop header, maybe move the loop upward. */
213 if (!fix_loop_placement (from
->loop_father
))
215 target_loop
= loop_outer (from
->loop_father
);
219 /* Ordinary basic block. */
220 if (!fix_bb_placement (from
))
222 target_loop
= from
->loop_father
;
225 FOR_EACH_EDGE (e
, ei
, from
->succs
)
227 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
228 *irred_invalidated
= true;
231 /* Something has changed, insert predecessors into queue. */
232 FOR_EACH_EDGE (e
, ei
, from
->preds
)
234 basic_block pred
= e
->src
;
237 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
238 *irred_invalidated
= true;
240 if (TEST_BIT (in_queue
, pred
->index
))
243 /* If it is subloop, then it either was not moved, or
244 the path up the loop tree from base_loop do not contain
246 nca
= find_common_loop (pred
->loop_father
, base_loop
);
247 if (pred
->loop_father
!= base_loop
249 || nca
!= pred
->loop_father
))
250 pred
= pred
->loop_father
->header
;
251 else if (!flow_loop_nested_p (target_loop
, pred
->loop_father
))
253 /* If PRED is already higher in the loop hierarchy than the
254 TARGET_LOOP to that we moved FROM, the change of the position
255 of FROM does not affect the position of PRED, so there is no
256 point in processing it. */
260 if (TEST_BIT (in_queue
, pred
->index
))
263 /* Schedule the basic block. */
268 SET_BIT (in_queue
, pred
->index
);
275 /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E
276 and update loop structures and dominators. Return true if we were able
277 to remove the path, false otherwise (and nothing is affected then). */
282 basic_block
*rem_bbs
, *bord_bbs
, from
, bb
;
283 VEC (basic_block
, heap
) *dom_bbs
;
284 int i
, nrem
, n_bord_bbs
;
286 bool irred_invalidated
= false;
290 if (!can_remove_branch_p (e
))
293 /* Keep track of whether we need to update information about irreducible
294 regions. This is the case if the removed area is a part of the
295 irreducible region, or if the set of basic blocks that belong to a loop
296 that is inside an irreducible region is changed, or if such a loop is
298 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
299 irred_invalidated
= true;
301 /* We need to check whether basic blocks are dominated by the edge
302 e, but we only have basic block dominators. This is easy to
303 fix -- when e->dest has exactly one predecessor, this corresponds
304 to blocks dominated by e->dest, if not, split the edge. */
305 if (!single_pred_p (e
->dest
))
306 e
= single_pred_edge (split_edge (e
));
308 /* It may happen that by removing path we remove one or more loops
309 we belong to. In this case first unloop the loops, then proceed
310 normally. We may assume that e->dest is not a header of any loop,
311 as it now has exactly one predecessor. */
312 for (l
= e
->src
->loop_father
; loop_outer (l
); l
= f
)
315 if (dominated_by_p (CDI_DOMINATORS
, l
->latch
, e
->dest
))
316 unloop (l
, &irred_invalidated
);
319 /* Identify the path. */
320 nrem
= find_path (e
, &rem_bbs
);
323 bord_bbs
= XNEWVEC (basic_block
, n_basic_blocks
);
324 seen
= sbitmap_alloc (last_basic_block
);
327 /* Find "border" hexes -- i.e. those with predecessor in removed path. */
328 for (i
= 0; i
< nrem
; i
++)
329 SET_BIT (seen
, rem_bbs
[i
]->index
);
330 if (!irred_invalidated
)
331 FOR_EACH_EDGE (ae
, ei
, e
->src
->succs
)
332 if (ae
!= e
&& ae
->dest
!= EXIT_BLOCK_PTR
&& !TEST_BIT (seen
, ae
->dest
->index
)
333 && ae
->flags
& EDGE_IRREDUCIBLE_LOOP
)
334 irred_invalidated
= true;
335 for (i
= 0; i
< nrem
; i
++)
338 FOR_EACH_EDGE (ae
, ei
, rem_bbs
[i
]->succs
)
339 if (ae
->dest
!= EXIT_BLOCK_PTR
&& !TEST_BIT (seen
, ae
->dest
->index
))
341 SET_BIT (seen
, ae
->dest
->index
);
342 bord_bbs
[n_bord_bbs
++] = ae
->dest
;
344 if (ae
->flags
& EDGE_IRREDUCIBLE_LOOP
)
345 irred_invalidated
= true;
349 /* Remove the path. */
354 /* Cancel loops contained in the path. */
355 for (i
= 0; i
< nrem
; i
++)
356 if (rem_bbs
[i
]->loop_father
->header
== rem_bbs
[i
])
357 cancel_loop_tree (rem_bbs
[i
]->loop_father
);
359 remove_bbs (rem_bbs
, nrem
);
362 /* Find blocks whose dominators may be affected. */
364 for (i
= 0; i
< n_bord_bbs
; i
++)
368 bb
= get_immediate_dominator (CDI_DOMINATORS
, bord_bbs
[i
]);
369 if (TEST_BIT (seen
, bb
->index
))
371 SET_BIT (seen
, bb
->index
);
373 for (ldom
= first_dom_son (CDI_DOMINATORS
, bb
);
375 ldom
= next_dom_son (CDI_DOMINATORS
, ldom
))
376 if (!dominated_by_p (CDI_DOMINATORS
, from
, ldom
))
377 VEC_safe_push (basic_block
, heap
, dom_bbs
, ldom
);
382 /* Recount dominators. */
383 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, true);
384 VEC_free (basic_block
, heap
, dom_bbs
);
387 /* Fix placements of basic blocks inside loops and the placement of
388 loops in the loop tree. */
389 fix_bb_placements (from
, &irred_invalidated
);
390 fix_loop_placements (from
->loop_father
, &irred_invalidated
);
392 if (irred_invalidated
393 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
394 mark_irreducible_loops ();
399 /* Creates place for a new LOOP in loops structure. */
402 place_new_loop (struct loop
*loop
)
404 loop
->num
= number_of_loops ();
405 VEC_safe_push (loop_p
, gc
, current_loops
->larray
, loop
);
408 /* Given LOOP structure with filled header and latch, find the body of the
409 corresponding loop and add it to loops tree. Insert the LOOP as a son of
413 add_loop (struct loop
*loop
, struct loop
*outer
)
417 struct loop
*subloop
;
421 /* Add it to loop structure. */
422 place_new_loop (loop
);
423 flow_loop_tree_node_add (outer
, loop
);
425 /* Find its nodes. */
426 bbs
= XNEWVEC (basic_block
, n_basic_blocks
);
427 n
= get_loop_body_with_size (loop
, bbs
, n_basic_blocks
);
429 for (i
= 0; i
< n
; i
++)
431 if (bbs
[i
]->loop_father
== outer
)
433 remove_bb_from_loops (bbs
[i
]);
434 add_bb_to_loop (bbs
[i
], loop
);
440 /* If we find a direct subloop of OUTER, move it to LOOP. */
441 subloop
= bbs
[i
]->loop_father
;
442 if (loop_outer (subloop
) == outer
443 && subloop
->header
== bbs
[i
])
445 flow_loop_tree_node_remove (subloop
);
446 flow_loop_tree_node_add (loop
, subloop
);
450 /* Update the information about loop exit edges. */
451 for (i
= 0; i
< n
; i
++)
453 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
455 rescan_loop_exit (e
, false, false);
462 /* Multiply all frequencies in LOOP by NUM/DEN. */
465 scale_loop_frequencies (struct loop
*loop
, int num
, int den
)
469 bbs
= get_loop_body (loop
);
470 scale_bbs_frequencies_int (bbs
, loop
->num_nodes
, num
, den
);
474 /* Multiply all frequencies in LOOP by SCALE/REG_BR_PROB_BASE.
475 If ITERATION_BOUND is non-zero, scale even further if loop is predicted
476 to iterate too many times. */
479 scale_loop_profile (struct loop
*loop
, int scale
, int iteration_bound
)
481 gcov_type iterations
= expected_loop_iterations_unbounded (loop
);
485 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
486 fprintf (dump_file
, ";; Scaling loop %i with scale %f, "
487 "bounding iterations to %i from guessed %i\n",
488 loop
->num
, (double)scale
/ REG_BR_PROB_BASE
,
489 iteration_bound
, (int)iterations
);
491 /* See if loop is predicted to iterate too many times. */
492 if (iteration_bound
&& iterations
> 0
493 && RDIV (iterations
* scale
, REG_BR_PROB_BASE
) > iteration_bound
)
495 /* Fixing loop profile for different trip count is not trivial; the exit
496 probabilities has to be updated to match and frequencies propagated down
499 We fully update only the simple case of loop with single exit that is
500 either from the latch or BB just before latch and leads from BB with
501 simple conditional jump. This is OK for use in vectorizer. */
502 e
= single_exit (loop
);
507 gcov_type count_delta
;
509 FOR_EACH_EDGE (other_e
, ei
, e
->src
->succs
)
510 if (!(other_e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
))
514 /* Probability of exit must be 1/iterations. */
515 freq_delta
= EDGE_FREQUENCY (e
);
516 e
->probability
= REG_BR_PROB_BASE
/ iteration_bound
;
517 other_e
->probability
= inverse_probability (e
->probability
);
518 freq_delta
-= EDGE_FREQUENCY (e
);
520 /* Adjust counts accordingly. */
521 count_delta
= e
->count
;
522 e
->count
= apply_probability (e
->src
->count
, e
->probability
);
523 other_e
->count
= apply_probability (e
->src
->count
, other_e
->probability
);
524 count_delta
-= e
->count
;
526 /* If latch exists, change its frequency and count, since we changed
527 probability of exit. Theoretically we should update everything from
528 source of exit edge to latch, but for vectorizer this is enough. */
530 && loop
->latch
!= e
->src
)
532 loop
->latch
->frequency
+= freq_delta
;
533 if (loop
->latch
->frequency
< 0)
534 loop
->latch
->frequency
= 0;
535 loop
->latch
->count
+= count_delta
;
536 if (loop
->latch
->count
< 0)
537 loop
->latch
->count
= 0;
541 /* Roughly speaking we want to reduce the loop body profile by the
542 the difference of loop iterations. We however can do better if
543 we look at the actual profile, if it is available. */
544 scale
= RDIV (iteration_bound
* scale
, iterations
);
545 if (loop
->header
->count
)
547 gcov_type count_in
= 0;
549 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
550 if (e
->src
!= loop
->latch
)
551 count_in
+= e
->count
;
554 scale
= RDIV (count_in
* iteration_bound
* REG_BR_PROB_BASE
, loop
->header
->count
);
556 else if (loop
->header
->frequency
)
560 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
561 if (e
->src
!= loop
->latch
)
562 freq_in
+= EDGE_FREQUENCY (e
);
565 scale
= RDIV (freq_in
* iteration_bound
* REG_BR_PROB_BASE
, loop
->header
->frequency
);
571 if (scale
== REG_BR_PROB_BASE
)
574 /* Scale the actual probabilities. */
575 scale_loop_frequencies (loop
, scale
, REG_BR_PROB_BASE
);
576 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
577 fprintf (dump_file
, ";; guessed iterations are now %i\n",
578 (int)expected_loop_iterations_unbounded (loop
));
581 /* Recompute dominance information for basic blocks outside LOOP. */
584 update_dominators_in_loop (struct loop
*loop
)
586 VEC (basic_block
, heap
) *dom_bbs
= NULL
;
591 seen
= sbitmap_alloc (last_basic_block
);
593 body
= get_loop_body (loop
);
595 for (i
= 0; i
< loop
->num_nodes
; i
++)
596 SET_BIT (seen
, body
[i
]->index
);
598 for (i
= 0; i
< loop
->num_nodes
; i
++)
602 for (ldom
= first_dom_son (CDI_DOMINATORS
, body
[i
]);
604 ldom
= next_dom_son (CDI_DOMINATORS
, ldom
))
605 if (!TEST_BIT (seen
, ldom
->index
))
607 SET_BIT (seen
, ldom
->index
);
608 VEC_safe_push (basic_block
, heap
, dom_bbs
, ldom
);
612 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, false);
615 VEC_free (basic_block
, heap
, dom_bbs
);
618 /* Creates an if region as shown above. CONDITION is used to create
622 | ------------- -------------
623 | | pred_bb | | pred_bb |
624 | ------------- -------------
628 | | ====> -------------
633 | ------------- e_false / \ e_true
635 | ------------- ----------- -----------
636 | | false_bb | | true_bb |
637 | ----------- -----------
644 | | exit_edge (result)
653 create_empty_if_region_on_edge (edge entry_edge
, tree condition
)
656 basic_block cond_bb
, true_bb
, false_bb
, join_bb
;
657 edge e_true
, e_false
, exit_edge
;
660 gimple_stmt_iterator gsi
;
662 cond_bb
= split_edge (entry_edge
);
664 /* Insert condition in cond_bb. */
665 gsi
= gsi_last_bb (cond_bb
);
667 force_gimple_operand_gsi (&gsi
, condition
, true, NULL
,
668 false, GSI_NEW_STMT
);
669 cond_stmt
= gimple_build_cond_from_tree (simple_cond
, NULL_TREE
, NULL_TREE
);
670 gsi
= gsi_last_bb (cond_bb
);
671 gsi_insert_after (&gsi
, cond_stmt
, GSI_NEW_STMT
);
673 join_bb
= split_edge (single_succ_edge (cond_bb
));
675 e_true
= single_succ_edge (cond_bb
);
676 true_bb
= split_edge (e_true
);
678 e_false
= make_edge (cond_bb
, join_bb
, 0);
679 false_bb
= split_edge (e_false
);
681 e_true
->flags
&= ~EDGE_FALLTHRU
;
682 e_true
->flags
|= EDGE_TRUE_VALUE
;
683 e_false
->flags
&= ~EDGE_FALLTHRU
;
684 e_false
->flags
|= EDGE_FALSE_VALUE
;
686 set_immediate_dominator (CDI_DOMINATORS
, cond_bb
, entry_edge
->src
);
687 set_immediate_dominator (CDI_DOMINATORS
, true_bb
, cond_bb
);
688 set_immediate_dominator (CDI_DOMINATORS
, false_bb
, cond_bb
);
689 set_immediate_dominator (CDI_DOMINATORS
, join_bb
, cond_bb
);
691 exit_edge
= single_succ_edge (join_bb
);
693 if (single_pred_p (exit_edge
->dest
))
694 set_immediate_dominator (CDI_DOMINATORS
, exit_edge
->dest
, join_bb
);
699 /* create_empty_loop_on_edge
701 | - pred_bb - ------ pred_bb ------
702 | | | | iv0 = initial_value |
703 | -----|----- ---------|-----------
704 | | ______ | entry_edge
706 | | ====> | -V---V- loop_header -------------
707 | V | | iv_before = phi (iv0, iv_after) |
708 | - succ_bb - | ---|-----------------------------
710 | ----------- | ---V--- loop_body ---------------
711 | | | iv_after = iv_before + stride |
712 | | | if (iv_before < upper_bound) |
713 | | ---|--------------\--------------
716 | | - loop_latch - V- succ_bb -
718 | | /------------- -----------
721 Creates an empty loop as shown above, the IV_BEFORE is the SSA_NAME
722 that is used before the increment of IV. IV_BEFORE should be used for
723 adding code to the body that uses the IV. OUTER is the outer loop in
724 which the new loop should be inserted.
726 Both INITIAL_VALUE and UPPER_BOUND expressions are gimplified and
727 inserted on the loop entry edge. This implies that this function
728 should be used only when the UPPER_BOUND expression is a loop
732 create_empty_loop_on_edge (edge entry_edge
,
734 tree stride
, tree upper_bound
,
740 basic_block loop_header
, loop_latch
, succ_bb
, pred_bb
;
742 gimple_stmt_iterator gsi
;
749 gcc_assert (entry_edge
&& initial_value
&& stride
&& upper_bound
&& iv
);
751 /* Create header, latch and wire up the loop. */
752 pred_bb
= entry_edge
->src
;
753 loop_header
= split_edge (entry_edge
);
754 loop_latch
= split_edge (single_succ_edge (loop_header
));
755 succ_bb
= single_succ (loop_latch
);
756 make_edge (loop_header
, succ_bb
, 0);
757 redirect_edge_succ_nodup (single_succ_edge (loop_latch
), loop_header
);
759 /* Set immediate dominator information. */
760 set_immediate_dominator (CDI_DOMINATORS
, loop_header
, pred_bb
);
761 set_immediate_dominator (CDI_DOMINATORS
, loop_latch
, loop_header
);
762 set_immediate_dominator (CDI_DOMINATORS
, succ_bb
, loop_header
);
764 /* Initialize a loop structure and put it in a loop hierarchy. */
765 loop
= alloc_loop ();
766 loop
->header
= loop_header
;
767 loop
->latch
= loop_latch
;
768 add_loop (loop
, outer
);
770 /* TODO: Fix frequencies and counts. */
771 prob
= REG_BR_PROB_BASE
/ 2;
773 scale_loop_frequencies (loop
, REG_BR_PROB_BASE
- prob
, REG_BR_PROB_BASE
);
775 /* Update dominators. */
776 update_dominators_in_loop (loop
);
778 /* Modify edge flags. */
779 exit_e
= single_exit (loop
);
780 exit_e
->flags
= EDGE_LOOP_EXIT
| EDGE_FALSE_VALUE
;
781 single_pred_edge (loop_latch
)->flags
= EDGE_TRUE_VALUE
;
783 /* Construct IV code in loop. */
784 initial_value
= force_gimple_operand (initial_value
, &stmts
, true, iv
);
787 gsi_insert_seq_on_edge (loop_preheader_edge (loop
), stmts
);
788 gsi_commit_edge_inserts ();
791 upper_bound
= force_gimple_operand (upper_bound
, &stmts
, true, NULL
);
794 gsi_insert_seq_on_edge (loop_preheader_edge (loop
), stmts
);
795 gsi_commit_edge_inserts ();
798 gsi
= gsi_last_bb (loop_header
);
799 create_iv (initial_value
, stride
, iv
, loop
, &gsi
, false,
800 iv_before
, iv_after
);
802 /* Insert loop exit condition. */
803 cond_expr
= gimple_build_cond
804 (LT_EXPR
, *iv_before
, upper_bound
, NULL_TREE
, NULL_TREE
);
806 exit_test
= gimple_cond_lhs (cond_expr
);
807 exit_test
= force_gimple_operand_gsi (&gsi
, exit_test
, true, NULL
,
808 false, GSI_NEW_STMT
);
809 gimple_cond_set_lhs (cond_expr
, exit_test
);
810 gsi
= gsi_last_bb (exit_e
->src
);
811 gsi_insert_after (&gsi
, cond_expr
, GSI_NEW_STMT
);
813 split_block_after_labels (loop_header
);
818 /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
819 latch to header and update loop tree and dominators
820 accordingly. Everything between them plus LATCH_EDGE destination must
821 be dominated by HEADER_EDGE destination, and back-reachable from
822 LATCH_EDGE source. HEADER_EDGE is redirected to basic block SWITCH_BB,
823 FALSE_EDGE of SWITCH_BB to original destination of HEADER_EDGE and
824 TRUE_EDGE of SWITCH_BB to original destination of LATCH_EDGE.
825 Returns the newly created loop. Frequencies and counts in the new loop
826 are scaled by FALSE_SCALE and in the old one by TRUE_SCALE. */
829 loopify (edge latch_edge
, edge header_edge
,
830 basic_block switch_bb
, edge true_edge
, edge false_edge
,
831 bool redirect_all_edges
, unsigned true_scale
, unsigned false_scale
)
833 basic_block succ_bb
= latch_edge
->dest
;
834 basic_block pred_bb
= header_edge
->src
;
835 struct loop
*loop
= alloc_loop ();
836 struct loop
*outer
= loop_outer (succ_bb
->loop_father
);
842 loop
->header
= header_edge
->dest
;
843 loop
->latch
= latch_edge
->src
;
845 freq
= EDGE_FREQUENCY (header_edge
);
846 cnt
= header_edge
->count
;
848 /* Redirect edges. */
849 loop_redirect_edge (latch_edge
, loop
->header
);
850 loop_redirect_edge (true_edge
, succ_bb
);
852 /* During loop versioning, one of the switch_bb edge is already properly
853 set. Do not redirect it again unless redirect_all_edges is true. */
854 if (redirect_all_edges
)
856 loop_redirect_edge (header_edge
, switch_bb
);
857 loop_redirect_edge (false_edge
, loop
->header
);
859 /* Update dominators. */
860 set_immediate_dominator (CDI_DOMINATORS
, switch_bb
, pred_bb
);
861 set_immediate_dominator (CDI_DOMINATORS
, loop
->header
, switch_bb
);
864 set_immediate_dominator (CDI_DOMINATORS
, succ_bb
, switch_bb
);
866 /* Compute new loop. */
867 add_loop (loop
, outer
);
869 /* Add switch_bb to appropriate loop. */
870 if (switch_bb
->loop_father
)
871 remove_bb_from_loops (switch_bb
);
872 add_bb_to_loop (switch_bb
, outer
);
874 /* Fix frequencies. */
875 if (redirect_all_edges
)
877 switch_bb
->frequency
= freq
;
878 switch_bb
->count
= cnt
;
879 FOR_EACH_EDGE (e
, ei
, switch_bb
->succs
)
881 e
->count
= RDIV (switch_bb
->count
* e
->probability
, REG_BR_PROB_BASE
);
884 scale_loop_frequencies (loop
, false_scale
, REG_BR_PROB_BASE
);
885 scale_loop_frequencies (succ_bb
->loop_father
, true_scale
, REG_BR_PROB_BASE
);
886 update_dominators_in_loop (loop
);
891 /* Remove the latch edge of a LOOP and update loops to indicate that
892 the LOOP was removed. After this function, original loop latch will
893 have no successor, which caller is expected to fix somehow.
895 If this may cause the information about irreducible regions to become
896 invalid, IRRED_INVALIDATED is set to true. */
899 unloop (struct loop
*loop
, bool *irred_invalidated
)
904 basic_block latch
= loop
->latch
;
907 if (loop_preheader_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
)
908 *irred_invalidated
= true;
910 /* This is relatively straightforward. The dominators are unchanged, as
911 loop header dominates loop latch, so the only thing we have to care of
912 is the placement of loops and basic blocks inside the loop tree. We
913 move them all to the loop->outer, and then let fix_bb_placements do
916 body
= get_loop_body (loop
);
918 for (i
= 0; i
< n
; i
++)
919 if (body
[i
]->loop_father
== loop
)
921 remove_bb_from_loops (body
[i
]);
922 add_bb_to_loop (body
[i
], loop_outer (loop
));
929 flow_loop_tree_node_remove (ploop
);
930 flow_loop_tree_node_add (loop_outer (loop
), ploop
);
933 /* Remove the loop and free its data. */
936 remove_edge (single_succ_edge (latch
));
938 /* We do not pass IRRED_INVALIDATED to fix_bb_placements here, as even if
939 there is an irreducible region inside the cancelled loop, the flags will
941 fix_bb_placements (latch
, &dummy
);
944 /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
945 condition stated in description of fix_loop_placement holds for them.
946 It is used in case when we removed some edges coming out of LOOP, which
947 may cause the right placement of LOOP inside loop tree to change.
949 IRRED_INVALIDATED is set to true if a change in the loop structures might
950 invalidate the information about irreducible regions. */
953 fix_loop_placements (struct loop
*loop
, bool *irred_invalidated
)
957 while (loop_outer (loop
))
959 outer
= loop_outer (loop
);
960 if (!fix_loop_placement (loop
))
963 /* Changing the placement of a loop in the loop tree may alter the
964 validity of condition 2) of the description of fix_bb_placement
965 for its preheader, because the successor is the header and belongs
966 to the loop. So call fix_bb_placements to fix up the placement
967 of the preheader and (possibly) of its predecessors. */
968 fix_bb_placements (loop_preheader_edge (loop
)->src
,
974 /* Copies copy of LOOP as subloop of TARGET loop, placing newly
975 created loop into loops structure. */
977 duplicate_loop (struct loop
*loop
, struct loop
*target
)
980 cloop
= alloc_loop ();
981 place_new_loop (cloop
);
983 /* Mark the new loop as copy of LOOP. */
984 set_loop_copy (loop
, cloop
);
986 /* Add it to target. */
987 flow_loop_tree_node_add (target
, cloop
);
992 /* Copies structure of subloops of LOOP into TARGET loop, placing
993 newly created loops into loop tree. */
995 duplicate_subloops (struct loop
*loop
, struct loop
*target
)
997 struct loop
*aloop
, *cloop
;
999 for (aloop
= loop
->inner
; aloop
; aloop
= aloop
->next
)
1001 cloop
= duplicate_loop (aloop
, target
);
1002 duplicate_subloops (aloop
, cloop
);
1006 /* Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
1007 into TARGET loop, placing newly created loops into loop tree. */
1009 copy_loops_to (struct loop
**copied_loops
, int n
, struct loop
*target
)
1014 for (i
= 0; i
< n
; i
++)
1016 aloop
= duplicate_loop (copied_loops
[i
], target
);
1017 duplicate_subloops (copied_loops
[i
], aloop
);
1021 /* Redirects edge E to basic block DEST. */
1023 loop_redirect_edge (edge e
, basic_block dest
)
1025 if (e
->dest
== dest
)
1028 redirect_edge_and_branch_force (e
, dest
);
1031 /* Check whether LOOP's body can be duplicated. */
1033 can_duplicate_loop_p (const struct loop
*loop
)
1036 basic_block
*bbs
= get_loop_body (loop
);
1038 ret
= can_copy_bbs_p (bbs
, loop
->num_nodes
);
1044 /* Sets probability and count of edge E to zero. The probability and count
1045 is redistributed evenly to the remaining edges coming from E->src. */
1048 set_zero_probability (edge e
)
1050 basic_block bb
= e
->src
;
1052 edge ae
, last
= NULL
;
1053 unsigned n
= EDGE_COUNT (bb
->succs
);
1054 gcov_type cnt
= e
->count
, cnt1
;
1055 unsigned prob
= e
->probability
, prob1
;
1058 cnt1
= cnt
/ (n
- 1);
1059 prob1
= prob
/ (n
- 1);
1061 FOR_EACH_EDGE (ae
, ei
, bb
->succs
)
1066 ae
->probability
+= prob1
;
1071 /* Move the rest to one of the edges. */
1072 last
->probability
+= prob
% (n
- 1);
1073 last
->count
+= cnt
% (n
- 1);
1079 /* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating
1080 loop structure and dominators. E's destination must be LOOP header for
1081 this to work, i.e. it must be entry or latch edge of this loop; these are
1082 unique, as the loops must have preheaders for this function to work
1083 correctly (in case E is latch, the function unrolls the loop, if E is entry
1084 edge, it peels the loop). Store edges created by copying ORIG edge from
1085 copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to
1086 original LOOP body, the other copies are numbered in order given by control
1087 flow through them) into TO_REMOVE array. Returns false if duplication is
1091 duplicate_loop_to_header_edge (struct loop
*loop
, edge e
,
1092 unsigned int ndupl
, sbitmap wont_exit
,
1093 edge orig
, VEC (edge
, heap
) **to_remove
,
1096 struct loop
*target
, *aloop
;
1097 struct loop
**orig_loops
;
1098 unsigned n_orig_loops
;
1099 basic_block header
= loop
->header
, latch
= loop
->latch
;
1100 basic_block
*new_bbs
, *bbs
, *first_active
;
1101 basic_block new_bb
, bb
, first_active_latch
= NULL
;
1102 edge ae
, latch_edge
;
1103 edge spec_edges
[2], new_spec_edges
[2];
1107 int is_latch
= (latch
== e
->src
);
1108 int scale_act
= 0, *scale_step
= NULL
, scale_main
= 0;
1109 int scale_after_exit
= 0;
1110 int p
, freq_in
, freq_le
, freq_out_orig
;
1111 int prob_pass_thru
, prob_pass_wont_exit
, prob_pass_main
;
1112 int add_irreducible_flag
;
1113 basic_block place_after
;
1114 bitmap bbs_to_scale
= NULL
;
1117 gcc_assert (e
->dest
== loop
->header
);
1118 gcc_assert (ndupl
> 0);
1122 /* Orig must be edge out of the loop. */
1123 gcc_assert (flow_bb_inside_loop_p (loop
, orig
->src
));
1124 gcc_assert (!flow_bb_inside_loop_p (loop
, orig
->dest
));
1127 n
= loop
->num_nodes
;
1128 bbs
= get_loop_body_in_dom_order (loop
);
1129 gcc_assert (bbs
[0] == loop
->header
);
1130 gcc_assert (bbs
[n
- 1] == loop
->latch
);
1132 /* Check whether duplication is possible. */
1133 if (!can_copy_bbs_p (bbs
, loop
->num_nodes
))
1138 new_bbs
= XNEWVEC (basic_block
, loop
->num_nodes
);
1140 /* In case we are doing loop peeling and the loop is in the middle of
1141 irreducible region, the peeled copies will be inside it too. */
1142 add_irreducible_flag
= e
->flags
& EDGE_IRREDUCIBLE_LOOP
;
1143 gcc_assert (!is_latch
|| !add_irreducible_flag
);
1145 /* Find edge from latch. */
1146 latch_edge
= loop_latch_edge (loop
);
1148 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
1150 /* Calculate coefficients by that we have to scale frequencies
1151 of duplicated loop bodies. */
1152 freq_in
= header
->frequency
;
1153 freq_le
= EDGE_FREQUENCY (latch_edge
);
1156 if (freq_in
< freq_le
)
1158 freq_out_orig
= orig
? EDGE_FREQUENCY (orig
) : freq_in
- freq_le
;
1159 if (freq_out_orig
> freq_in
- freq_le
)
1160 freq_out_orig
= freq_in
- freq_le
;
1161 prob_pass_thru
= RDIV (REG_BR_PROB_BASE
* freq_le
, freq_in
);
1162 prob_pass_wont_exit
=
1163 RDIV (REG_BR_PROB_BASE
* (freq_le
+ freq_out_orig
), freq_in
);
1166 && REG_BR_PROB_BASE
- orig
->probability
!= 0)
1168 /* The blocks that are dominated by a removed exit edge ORIG have
1169 frequencies scaled by this. */
1170 scale_after_exit
= RDIV (REG_BR_PROB_BASE
* REG_BR_PROB_BASE
,
1171 REG_BR_PROB_BASE
- orig
->probability
);
1172 bbs_to_scale
= BITMAP_ALLOC (NULL
);
1173 for (i
= 0; i
< n
; i
++)
1175 if (bbs
[i
] != orig
->src
1176 && dominated_by_p (CDI_DOMINATORS
, bbs
[i
], orig
->src
))
1177 bitmap_set_bit (bbs_to_scale
, i
);
1181 scale_step
= XNEWVEC (int, ndupl
);
1183 for (i
= 1; i
<= ndupl
; i
++)
1184 scale_step
[i
- 1] = TEST_BIT (wont_exit
, i
)
1185 ? prob_pass_wont_exit
1188 /* Complete peeling is special as the probability of exit in last
1190 if (flags
& DLTHE_FLAG_COMPLETTE_PEEL
)
1192 int wanted_freq
= EDGE_FREQUENCY (e
);
1194 if (wanted_freq
> freq_in
)
1195 wanted_freq
= freq_in
;
1197 gcc_assert (!is_latch
);
1198 /* First copy has frequency of incoming edge. Each subsequent
1199 frequency should be reduced by prob_pass_wont_exit. Caller
1200 should've managed the flags so all except for original loop
1201 has won't exist set. */
1202 scale_act
= RDIV (wanted_freq
* REG_BR_PROB_BASE
, freq_in
);
1203 /* Now simulate the duplication adjustments and compute header
1204 frequency of the last copy. */
1205 for (i
= 0; i
< ndupl
; i
++)
1206 wanted_freq
= RDIV (wanted_freq
* scale_step
[i
], REG_BR_PROB_BASE
);
1207 scale_main
= RDIV (wanted_freq
* REG_BR_PROB_BASE
, freq_in
);
1211 prob_pass_main
= TEST_BIT (wont_exit
, 0)
1212 ? prob_pass_wont_exit
1215 scale_main
= REG_BR_PROB_BASE
;
1216 for (i
= 0; i
< ndupl
; i
++)
1219 p
= RDIV (p
* scale_step
[i
], REG_BR_PROB_BASE
);
1221 scale_main
= RDIV (REG_BR_PROB_BASE
* REG_BR_PROB_BASE
, scale_main
);
1222 scale_act
= RDIV (scale_main
* prob_pass_main
, REG_BR_PROB_BASE
);
1226 scale_main
= REG_BR_PROB_BASE
;
1227 for (i
= 0; i
< ndupl
; i
++)
1228 scale_main
= RDIV (scale_main
* scale_step
[i
], REG_BR_PROB_BASE
);
1229 scale_act
= REG_BR_PROB_BASE
- prob_pass_thru
;
1231 for (i
= 0; i
< ndupl
; i
++)
1232 gcc_assert (scale_step
[i
] >= 0 && scale_step
[i
] <= REG_BR_PROB_BASE
);
1233 gcc_assert (scale_main
>= 0 && scale_main
<= REG_BR_PROB_BASE
1234 && scale_act
>= 0 && scale_act
<= REG_BR_PROB_BASE
);
1237 /* Loop the new bbs will belong to. */
1238 target
= e
->src
->loop_father
;
1240 /* Original loops. */
1242 for (aloop
= loop
->inner
; aloop
; aloop
= aloop
->next
)
1244 orig_loops
= XNEWVEC (struct loop
*, n_orig_loops
);
1245 for (aloop
= loop
->inner
, i
= 0; aloop
; aloop
= aloop
->next
, i
++)
1246 orig_loops
[i
] = aloop
;
1248 set_loop_copy (loop
, target
);
1250 first_active
= XNEWVEC (basic_block
, n
);
1253 memcpy (first_active
, bbs
, n
* sizeof (basic_block
));
1254 first_active_latch
= latch
;
1257 spec_edges
[SE_ORIG
] = orig
;
1258 spec_edges
[SE_LATCH
] = latch_edge
;
1260 place_after
= e
->src
;
1261 for (j
= 0; j
< ndupl
; j
++)
1264 copy_loops_to (orig_loops
, n_orig_loops
, target
);
1267 copy_bbs (bbs
, n
, new_bbs
, spec_edges
, 2, new_spec_edges
, loop
,
1269 place_after
= new_spec_edges
[SE_LATCH
]->src
;
1271 if (flags
& DLTHE_RECORD_COPY_NUMBER
)
1272 for (i
= 0; i
< n
; i
++)
1274 gcc_assert (!new_bbs
[i
]->aux
);
1275 new_bbs
[i
]->aux
= (void *)(size_t)(j
+ 1);
1278 /* Note whether the blocks and edges belong to an irreducible loop. */
1279 if (add_irreducible_flag
)
1281 for (i
= 0; i
< n
; i
++)
1282 new_bbs
[i
]->flags
|= BB_DUPLICATED
;
1283 for (i
= 0; i
< n
; i
++)
1286 new_bb
= new_bbs
[i
];
1287 if (new_bb
->loop_father
== target
)
1288 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
1290 FOR_EACH_EDGE (ae
, ei
, new_bb
->succs
)
1291 if ((ae
->dest
->flags
& BB_DUPLICATED
)
1292 && (ae
->src
->loop_father
== target
1293 || ae
->dest
->loop_father
== target
))
1294 ae
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1296 for (i
= 0; i
< n
; i
++)
1297 new_bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1300 /* Redirect the special edges. */
1303 redirect_edge_and_branch_force (latch_edge
, new_bbs
[0]);
1304 redirect_edge_and_branch_force (new_spec_edges
[SE_LATCH
],
1306 set_immediate_dominator (CDI_DOMINATORS
, new_bbs
[0], latch
);
1307 latch
= loop
->latch
= new_bbs
[n
- 1];
1308 e
= latch_edge
= new_spec_edges
[SE_LATCH
];
1312 redirect_edge_and_branch_force (new_spec_edges
[SE_LATCH
],
1314 redirect_edge_and_branch_force (e
, new_bbs
[0]);
1315 set_immediate_dominator (CDI_DOMINATORS
, new_bbs
[0], e
->src
);
1316 e
= new_spec_edges
[SE_LATCH
];
1319 /* Record exit edge in this copy. */
1320 if (orig
&& TEST_BIT (wont_exit
, j
+ 1))
1323 VEC_safe_push (edge
, heap
, *to_remove
, new_spec_edges
[SE_ORIG
]);
1324 set_zero_probability (new_spec_edges
[SE_ORIG
]);
1326 /* Scale the frequencies of the blocks dominated by the exit. */
1329 EXECUTE_IF_SET_IN_BITMAP (bbs_to_scale
, 0, i
, bi
)
1331 scale_bbs_frequencies_int (new_bbs
+ i
, 1, scale_after_exit
,
1337 /* Record the first copy in the control flow order if it is not
1338 the original loop (i.e. in case of peeling). */
1339 if (!first_active_latch
)
1341 memcpy (first_active
, new_bbs
, n
* sizeof (basic_block
));
1342 first_active_latch
= new_bbs
[n
- 1];
1345 /* Set counts and frequencies. */
1346 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
1348 scale_bbs_frequencies_int (new_bbs
, n
, scale_act
, REG_BR_PROB_BASE
);
1349 scale_act
= RDIV (scale_act
* scale_step
[j
], REG_BR_PROB_BASE
);
1355 /* Record the exit edge in the original loop body, and update the frequencies. */
1356 if (orig
&& TEST_BIT (wont_exit
, 0))
1359 VEC_safe_push (edge
, heap
, *to_remove
, orig
);
1360 set_zero_probability (orig
);
1362 /* Scale the frequencies of the blocks dominated by the exit. */
1365 EXECUTE_IF_SET_IN_BITMAP (bbs_to_scale
, 0, i
, bi
)
1367 scale_bbs_frequencies_int (bbs
+ i
, 1, scale_after_exit
,
1373 /* Update the original loop. */
1375 set_immediate_dominator (CDI_DOMINATORS
, e
->dest
, e
->src
);
1376 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
1378 scale_bbs_frequencies_int (bbs
, n
, scale_main
, REG_BR_PROB_BASE
);
1382 /* Update dominators of outer blocks if affected. */
1383 for (i
= 0; i
< n
; i
++)
1385 basic_block dominated
, dom_bb
;
1386 VEC (basic_block
, heap
) *dom_bbs
;
1392 dom_bbs
= get_dominated_by (CDI_DOMINATORS
, bb
);
1393 FOR_EACH_VEC_ELT (basic_block
, dom_bbs
, j
, dominated
)
1395 if (flow_bb_inside_loop_p (loop
, dominated
))
1397 dom_bb
= nearest_common_dominator (
1398 CDI_DOMINATORS
, first_active
[i
], first_active_latch
);
1399 set_immediate_dominator (CDI_DOMINATORS
, dominated
, dom_bb
);
1401 VEC_free (basic_block
, heap
, dom_bbs
);
1403 free (first_active
);
1406 BITMAP_FREE (bbs_to_scale
);
1411 /* A callback for make_forwarder block, to redirect all edges except for
1412 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
1413 whether to redirect it. */
1417 mfb_keep_just (edge e
)
1419 return e
!= mfb_kj_edge
;
1422 /* True when a candidate preheader BLOCK has predecessors from LOOP. */
1425 has_preds_from_loop (basic_block block
, struct loop
*loop
)
1430 FOR_EACH_EDGE (e
, ei
, block
->preds
)
1431 if (e
->src
->loop_father
== loop
)
1436 /* Creates a pre-header for a LOOP. Returns newly created block. Unless
1437 CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
1438 entry; otherwise we also force preheader block to have only one successor.
1439 When CP_FALLTHRU_PREHEADERS is set in FLAGS, we force the preheader block
1440 to be a fallthru predecessor to the loop header and to have only
1441 predecessors from outside of the loop.
1442 The function also updates dominators. */
1445 create_preheader (struct loop
*loop
, int flags
)
1451 bool latch_edge_was_fallthru
;
1452 edge one_succ_pred
= NULL
, single_entry
= NULL
;
1455 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1457 if (e
->src
== loop
->latch
)
1459 irred
|= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
1462 if (single_succ_p (e
->src
))
1465 gcc_assert (nentry
);
1468 bool need_forwarder_block
= false;
1470 /* We do not allow entry block to be the loop preheader, since we
1471 cannot emit code there. */
1472 if (single_entry
->src
== ENTRY_BLOCK_PTR
)
1473 need_forwarder_block
= true;
1476 /* If we want simple preheaders, also force the preheader to have
1477 just a single successor. */
1478 if ((flags
& CP_SIMPLE_PREHEADERS
)
1479 && !single_succ_p (single_entry
->src
))
1480 need_forwarder_block
= true;
1481 /* If we want fallthru preheaders, also create forwarder block when
1482 preheader ends with a jump or has predecessors from loop. */
1483 else if ((flags
& CP_FALLTHRU_PREHEADERS
)
1484 && (JUMP_P (BB_END (single_entry
->src
))
1485 || has_preds_from_loop (single_entry
->src
, loop
)))
1486 need_forwarder_block
= true;
1488 if (! need_forwarder_block
)
1492 mfb_kj_edge
= loop_latch_edge (loop
);
1493 latch_edge_was_fallthru
= (mfb_kj_edge
->flags
& EDGE_FALLTHRU
) != 0;
1494 fallthru
= make_forwarder_block (loop
->header
, mfb_keep_just
, NULL
);
1495 dummy
= fallthru
->src
;
1496 loop
->header
= fallthru
->dest
;
1498 /* Try to be clever in placing the newly created preheader. The idea is to
1499 avoid breaking any "fallthruness" relationship between blocks.
1501 The preheader was created just before the header and all incoming edges
1502 to the header were redirected to the preheader, except the latch edge.
1503 So the only problematic case is when this latch edge was a fallthru
1504 edge: it is not anymore after the preheader creation so we have broken
1505 the fallthruness. We're therefore going to look for a better place. */
1506 if (latch_edge_was_fallthru
)
1511 e
= EDGE_PRED (dummy
, 0);
1513 move_block_after (dummy
, e
->src
);
1518 dummy
->flags
|= BB_IRREDUCIBLE_LOOP
;
1519 single_succ_edge (dummy
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1523 fprintf (dump_file
, "Created preheader block for loop %i\n",
1526 if (flags
& CP_FALLTHRU_PREHEADERS
)
1527 gcc_assert ((single_succ_edge (dummy
)->flags
& EDGE_FALLTHRU
)
1528 && !JUMP_P (BB_END (dummy
)));
1533 /* Create preheaders for each loop; for meaning of FLAGS see create_preheader. */
1536 create_preheaders (int flags
)
1544 FOR_EACH_LOOP (li
, loop
, 0)
1545 create_preheader (loop
, flags
);
1546 loops_state_set (LOOPS_HAVE_PREHEADERS
);
1549 /* Forces all loop latches to have only single successor. */
1552 force_single_succ_latches (void)
1558 FOR_EACH_LOOP (li
, loop
, 0)
1560 if (loop
->latch
!= loop
->header
&& single_succ_p (loop
->latch
))
1563 e
= find_edge (loop
->latch
, loop
->header
);
1567 loops_state_set (LOOPS_HAVE_SIMPLE_LATCHES
);
1570 /* This function is called from loop_version. It splits the entry edge
1571 of the loop we want to version, adds the versioning condition, and
1572 adjust the edges to the two versions of the loop appropriately.
1573 e is an incoming edge. Returns the basic block containing the
1576 --- edge e ---- > [second_head]
1578 Split it and insert new conditional expression and adjust edges.
1580 --- edge e ---> [cond expr] ---> [first_head]
1582 +---------> [second_head]
1584 THEN_PROB is the probability of then branch of the condition. */
1587 lv_adjust_loop_entry_edge (basic_block first_head
, basic_block second_head
,
1588 edge e
, void *cond_expr
, unsigned then_prob
)
1590 basic_block new_head
= NULL
;
1593 gcc_assert (e
->dest
== second_head
);
1595 /* Split edge 'e'. This will create a new basic block, where we can
1596 insert conditional expr. */
1597 new_head
= split_edge (e
);
1599 lv_add_condition_to_bb (first_head
, second_head
, new_head
,
1602 /* Don't set EDGE_TRUE_VALUE in RTL mode, as it's invalid there. */
1603 e
= single_succ_edge (new_head
);
1604 e1
= make_edge (new_head
, first_head
,
1605 current_ir_type () == IR_GIMPLE
? EDGE_TRUE_VALUE
: 0);
1606 e1
->probability
= then_prob
;
1607 e
->probability
= REG_BR_PROB_BASE
- then_prob
;
1608 e1
->count
= RDIV (e
->count
* e1
->probability
, REG_BR_PROB_BASE
);
1609 e
->count
= RDIV (e
->count
* e
->probability
, REG_BR_PROB_BASE
);
1611 set_immediate_dominator (CDI_DOMINATORS
, first_head
, new_head
);
1612 set_immediate_dominator (CDI_DOMINATORS
, second_head
, new_head
);
1614 /* Adjust loop header phi nodes. */
1615 lv_adjust_loop_header_phi (first_head
, second_head
, new_head
, e1
);
1620 /* Main entry point for Loop Versioning transformation.
1622 This transformation given a condition and a loop, creates
1623 -if (condition) { loop_copy1 } else { loop_copy2 },
1624 where loop_copy1 is the loop transformed in one way, and loop_copy2
1625 is the loop transformed in another way (or unchanged). 'condition'
1626 may be a run time test for things that were not resolved by static
1627 analysis (overlapping ranges (anti-aliasing), alignment, etc.).
1629 THEN_PROB is the probability of the then edge of the if. THEN_SCALE
1630 is the ratio by that the frequencies in the original loop should
1631 be scaled. ELSE_SCALE is the ratio by that the frequencies in the
1632 new loop should be scaled.
1634 If PLACE_AFTER is true, we place the new loop after LOOP in the
1635 instruction stream, otherwise it is placed before LOOP. */
1638 loop_version (struct loop
*loop
,
1639 void *cond_expr
, basic_block
*condition_bb
,
1640 unsigned then_prob
, unsigned then_scale
, unsigned else_scale
,
1643 basic_block first_head
, second_head
;
1644 edge entry
, latch_edge
, true_edge
, false_edge
;
1647 basic_block cond_bb
;
1649 /* Record entry and latch edges for the loop */
1650 entry
= loop_preheader_edge (loop
);
1651 irred_flag
= entry
->flags
& EDGE_IRREDUCIBLE_LOOP
;
1652 entry
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
1654 /* Note down head of loop as first_head. */
1655 first_head
= entry
->dest
;
1657 /* Duplicate loop. */
1658 if (!cfg_hook_duplicate_loop_to_header_edge (loop
, entry
, 1,
1659 NULL
, NULL
, NULL
, 0))
1661 entry
->flags
|= irred_flag
;
1665 /* After duplication entry edge now points to new loop head block.
1666 Note down new head as second_head. */
1667 second_head
= entry
->dest
;
1669 /* Split loop entry edge and insert new block with cond expr. */
1670 cond_bb
= lv_adjust_loop_entry_edge (first_head
, second_head
,
1671 entry
, cond_expr
, then_prob
);
1673 *condition_bb
= cond_bb
;
1677 entry
->flags
|= irred_flag
;
1681 latch_edge
= single_succ_edge (get_bb_copy (loop
->latch
));
1683 extract_cond_bb_edges (cond_bb
, &true_edge
, &false_edge
);
1684 nloop
= loopify (latch_edge
,
1685 single_pred_edge (get_bb_copy (loop
->header
)),
1686 cond_bb
, true_edge
, false_edge
,
1687 false /* Do not redirect all edges. */,
1688 then_scale
, else_scale
);
1690 /* loopify redirected latch_edge. Update its PENDING_STMTS. */
1691 lv_flush_pending_stmts (latch_edge
);
1693 /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */
1694 extract_cond_bb_edges (cond_bb
, &true_edge
, &false_edge
);
1695 lv_flush_pending_stmts (false_edge
);
1696 /* Adjust irreducible flag. */
1699 cond_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
1700 loop_preheader_edge (loop
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1701 loop_preheader_edge (nloop
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1702 single_pred_edge (cond_bb
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1707 basic_block
*bbs
= get_loop_body_in_dom_order (nloop
), after
;
1710 after
= loop
->latch
;
1712 for (i
= 0; i
< nloop
->num_nodes
; i
++)
1714 move_block_after (bbs
[i
], after
);
1720 /* At this point condition_bb is loop preheader with two successors,
1721 first_head and second_head. Make sure that loop preheader has only
1723 split_edge (loop_preheader_edge (loop
));
1724 split_edge (loop_preheader_edge (nloop
));
1729 /* The structure of loops might have changed. Some loops might get removed
1730 (and their headers and latches were set to NULL), loop exists might get
1731 removed (thus the loop nesting may be wrong), and some blocks and edges
1732 were changed (so the information about bb --> loop mapping does not have
1733 to be correct). But still for the remaining loops the header dominates
1734 the latch, and loops did not get new subloops (new loops might possibly
1735 get created, but we are not interested in them). Fix up the mess.
1737 If CHANGED_BBS is not NULL, basic blocks whose loop has changed are
1741 fix_loop_structure (bitmap changed_bbs
)
1744 struct loop
*loop
, *ploop
;
1746 bool record_exits
= false;
1747 struct loop
**superloop
= XNEWVEC (struct loop
*, number_of_loops ());
1749 /* We need exact and fast dominance info to be available. */
1750 gcc_assert (dom_info_state (CDI_DOMINATORS
) == DOM_OK
);
1752 /* Remove the old bb -> loop mapping. Remember the depth of the blocks in
1753 the loop hierarchy, so that we can recognize blocks whose loop nesting
1754 relationship has changed. */
1758 bb
->aux
= (void *) (size_t) loop_depth (bb
->loop_father
);
1759 bb
->loop_father
= current_loops
->tree_root
;
1762 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1764 release_recorded_exits ();
1765 record_exits
= true;
1768 /* Remove the dead loops from structures. We start from the innermost
1769 loops, so that when we remove the loops, we know that the loops inside
1770 are preserved, and do not waste time relinking loops that will be
1772 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1779 ploop
= loop
->inner
;
1780 flow_loop_tree_node_remove (ploop
);
1781 flow_loop_tree_node_add (loop_outer (loop
), ploop
);
1784 /* Remove the loop and free its data. */
1788 /* Rescan the bodies of loops, starting from the outermost ones. We assume
1789 that no optimization interchanges the order of the loops, i.e., it cannot
1790 happen that L1 was superloop of L2 before and it is subloop of L2 now
1791 (without explicitly updating loop information). At the same time, we also
1792 determine the new loop structure. */
1793 current_loops
->tree_root
->num_nodes
= n_basic_blocks
;
1794 FOR_EACH_LOOP (li
, loop
, 0)
1796 superloop
[loop
->num
] = loop
->header
->loop_father
;
1797 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
1800 /* Now fix the loop nesting. */
1801 FOR_EACH_LOOP (li
, loop
, 0)
1803 ploop
= superloop
[loop
->num
];
1804 if (ploop
!= loop_outer (loop
))
1806 flow_loop_tree_node_remove (loop
);
1807 flow_loop_tree_node_add (ploop
, loop
);
1812 /* Mark the blocks whose loop has changed. */
1817 if ((void *) (size_t) loop_depth (bb
->loop_father
) != bb
->aux
)
1818 bitmap_set_bit (changed_bbs
, bb
->index
);
1824 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
))
1825 create_preheaders (CP_SIMPLE_PREHEADERS
);
1827 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
1828 force_single_succ_latches ();
1830 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1831 mark_irreducible_loops ();
1834 record_loop_exits ();
1836 loops_state_clear (LOOPS_NEED_FIXUP
);
1838 #ifdef ENABLE_CHECKING
1839 verify_loop_structure ();