1 /* Loop manipulation code for GNU compiler.
2 Copyright (C) 2002-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
30 #include "gimple-iterator.h"
31 #include "gimplify-me.h"
32 #include "tree-ssa-loop-manip.h"
35 static void copy_loops_to (struct loop
**, int,
37 static void loop_redirect_edge (edge
, basic_block
);
38 static void remove_bbs (basic_block
*, int);
39 static bool rpe_enum_p (const_basic_block
, const void *);
40 static int find_path (edge
, basic_block
**);
41 static void fix_loop_placements (struct loop
*, bool *);
42 static bool fix_bb_placement (basic_block
);
43 static void fix_bb_placements (basic_block
, bool *, bitmap
);
45 /* Checks whether basic block BB is dominated by DATA. */
47 rpe_enum_p (const_basic_block bb
, const void *data
)
49 return dominated_by_p (CDI_DOMINATORS
, bb
, (const_basic_block
) data
);
52 /* Remove basic blocks BBS. NBBS is the number of the basic blocks. */
55 remove_bbs (basic_block
*bbs
, int nbbs
)
59 for (i
= 0; i
< nbbs
; i
++)
60 delete_basic_block (bbs
[i
]);
63 /* Find path -- i.e. the basic blocks dominated by edge E and put them
64 into array BBS, that will be allocated large enough to contain them.
65 E->dest must have exactly one predecessor for this to work (it is
66 easy to achieve and we do not put it here because we do not want to
67 alter anything by this function). The number of basic blocks in the
70 find_path (edge e
, basic_block
**bbs
)
72 gcc_assert (EDGE_COUNT (e
->dest
->preds
) <= 1);
74 /* Find bbs in the path. */
75 *bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
76 return dfs_enumerate_from (e
->dest
, 0, rpe_enum_p
, *bbs
,
77 n_basic_blocks_for_fn (cfun
), e
->dest
);
80 /* Fix placement of basic block BB inside loop hierarchy --
81 Let L be a loop to that BB belongs. Then every successor of BB must either
82 1) belong to some superloop of loop L, or
83 2) be a header of loop K such that K->outer is superloop of L
84 Returns true if we had to move BB into other loop to enforce this condition,
85 false if the placement of BB was already correct (provided that placements
86 of its successors are correct). */
88 fix_bb_placement (basic_block bb
)
92 struct loop
*loop
= current_loops
->tree_root
, *act
;
94 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
96 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
99 act
= e
->dest
->loop_father
;
100 if (act
->header
== e
->dest
)
101 act
= loop_outer (act
);
103 if (flow_loop_nested_p (loop
, act
))
107 if (loop
== bb
->loop_father
)
110 remove_bb_from_loops (bb
);
111 add_bb_to_loop (bb
, loop
);
116 /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
117 of LOOP to that leads at least one exit edge of LOOP, and set it
118 as the immediate superloop of LOOP. Return true if the immediate superloop
121 IRRED_INVALIDATED is set to true if a change in the loop structures might
122 invalidate the information about irreducible regions. */
125 fix_loop_placement (struct loop
*loop
, bool *irred_invalidated
)
129 vec
<edge
> exits
= get_loop_exit_edges (loop
);
130 struct loop
*father
= current_loops
->tree_root
, *act
;
133 FOR_EACH_VEC_ELT (exits
, i
, e
)
135 act
= find_common_loop (loop
, e
->dest
->loop_father
);
136 if (flow_loop_nested_p (father
, act
))
140 if (father
!= loop_outer (loop
))
142 for (act
= loop_outer (loop
); act
!= father
; act
= loop_outer (act
))
143 act
->num_nodes
-= loop
->num_nodes
;
144 flow_loop_tree_node_remove (loop
);
145 flow_loop_tree_node_add (father
, loop
);
147 /* The exit edges of LOOP no longer exits its original immediate
148 superloops; remove them from the appropriate exit lists. */
149 FOR_EACH_VEC_ELT (exits
, i
, e
)
151 /* We may need to recompute irreducible loops. */
152 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
153 *irred_invalidated
= true;
154 rescan_loop_exit (e
, false, false);
164 /* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
165 enforce condition stated in description of fix_bb_placement. We
166 start from basic block FROM that had some of its successors removed, so that
167 his placement no longer has to be correct, and iteratively fix placement of
168 its predecessors that may change if placement of FROM changed. Also fix
169 placement of subloops of FROM->loop_father, that might also be altered due
170 to this change; the condition for them is similar, except that instead of
171 successors we consider edges coming out of the loops.
173 If the changes may invalidate the information about irreducible regions,
174 IRRED_INVALIDATED is set to true.
176 If LOOP_CLOSED_SSA_INVLIDATED is non-zero then all basic blocks with
177 changed loop_father are collected there. */
180 fix_bb_placements (basic_block from
,
181 bool *irred_invalidated
,
182 bitmap loop_closed_ssa_invalidated
)
185 basic_block
*queue
, *qtop
, *qbeg
, *qend
;
186 struct loop
*base_loop
, *target_loop
;
189 /* We pass through blocks back-reachable from FROM, testing whether some
190 of their successors moved to outer loop. It may be necessary to
191 iterate several times, but it is finite, as we stop unless we move
192 the basic block up the loop structure. The whole story is a bit
193 more complicated due to presence of subloops, those are moved using
194 fix_loop_placement. */
196 base_loop
= from
->loop_father
;
197 /* If we are already in the outermost loop, the basic blocks cannot be moved
198 outside of it. If FROM is the header of the base loop, it cannot be moved
199 outside of it, either. In both cases, we can end now. */
200 if (base_loop
== current_loops
->tree_root
201 || from
== base_loop
->header
)
204 in_queue
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
205 bitmap_clear (in_queue
);
206 bitmap_set_bit (in_queue
, from
->index
);
207 /* Prevent us from going out of the base_loop. */
208 bitmap_set_bit (in_queue
, base_loop
->header
->index
);
210 queue
= XNEWVEC (basic_block
, base_loop
->num_nodes
+ 1);
211 qtop
= queue
+ base_loop
->num_nodes
+ 1;
223 bitmap_clear_bit (in_queue
, from
->index
);
225 if (from
->loop_father
->header
== from
)
227 /* Subloop header, maybe move the loop upward. */
228 if (!fix_loop_placement (from
->loop_father
, irred_invalidated
))
230 target_loop
= loop_outer (from
->loop_father
);
231 if (loop_closed_ssa_invalidated
)
233 basic_block
*bbs
= get_loop_body (from
->loop_father
);
234 for (unsigned i
= 0; i
< from
->loop_father
->num_nodes
; ++i
)
235 bitmap_set_bit (loop_closed_ssa_invalidated
, bbs
[i
]->index
);
241 /* Ordinary basic block. */
242 if (!fix_bb_placement (from
))
244 target_loop
= from
->loop_father
;
245 if (loop_closed_ssa_invalidated
)
246 bitmap_set_bit (loop_closed_ssa_invalidated
, from
->index
);
249 FOR_EACH_EDGE (e
, ei
, from
->succs
)
251 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
252 *irred_invalidated
= true;
255 /* Something has changed, insert predecessors into queue. */
256 FOR_EACH_EDGE (e
, ei
, from
->preds
)
258 basic_block pred
= e
->src
;
261 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
262 *irred_invalidated
= true;
264 if (bitmap_bit_p (in_queue
, pred
->index
))
267 /* If it is subloop, then it either was not moved, or
268 the path up the loop tree from base_loop do not contain
270 nca
= find_common_loop (pred
->loop_father
, base_loop
);
271 if (pred
->loop_father
!= base_loop
273 || nca
!= pred
->loop_father
))
274 pred
= pred
->loop_father
->header
;
275 else if (!flow_loop_nested_p (target_loop
, pred
->loop_father
))
277 /* If PRED is already higher in the loop hierarchy than the
278 TARGET_LOOP to that we moved FROM, the change of the position
279 of FROM does not affect the position of PRED, so there is no
280 point in processing it. */
284 if (bitmap_bit_p (in_queue
, pred
->index
))
287 /* Schedule the basic block. */
292 bitmap_set_bit (in_queue
, pred
->index
);
299 /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E
300 and update loop structures and dominators. Return true if we were able
301 to remove the path, false otherwise (and nothing is affected then). */
306 basic_block
*rem_bbs
, *bord_bbs
, from
, bb
;
307 vec
<basic_block
> dom_bbs
;
308 int i
, nrem
, n_bord_bbs
;
310 bool irred_invalidated
= false;
314 if (!can_remove_branch_p (e
))
317 /* Keep track of whether we need to update information about irreducible
318 regions. This is the case if the removed area is a part of the
319 irreducible region, or if the set of basic blocks that belong to a loop
320 that is inside an irreducible region is changed, or if such a loop is
322 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
323 irred_invalidated
= true;
325 /* We need to check whether basic blocks are dominated by the edge
326 e, but we only have basic block dominators. This is easy to
327 fix -- when e->dest has exactly one predecessor, this corresponds
328 to blocks dominated by e->dest, if not, split the edge. */
329 if (!single_pred_p (e
->dest
))
330 e
= single_pred_edge (split_edge (e
));
332 /* It may happen that by removing path we remove one or more loops
333 we belong to. In this case first unloop the loops, then proceed
334 normally. We may assume that e->dest is not a header of any loop,
335 as it now has exactly one predecessor. */
336 for (l
= e
->src
->loop_father
; loop_outer (l
); l
= f
)
339 if (dominated_by_p (CDI_DOMINATORS
, l
->latch
, e
->dest
))
340 unloop (l
, &irred_invalidated
, NULL
);
343 /* Identify the path. */
344 nrem
= find_path (e
, &rem_bbs
);
347 bord_bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
348 seen
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
351 /* Find "border" hexes -- i.e. those with predecessor in removed path. */
352 for (i
= 0; i
< nrem
; i
++)
353 bitmap_set_bit (seen
, rem_bbs
[i
]->index
);
354 if (!irred_invalidated
)
355 FOR_EACH_EDGE (ae
, ei
, e
->src
->succs
)
356 if (ae
!= e
&& ae
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
357 && !bitmap_bit_p (seen
, ae
->dest
->index
)
358 && ae
->flags
& EDGE_IRREDUCIBLE_LOOP
)
360 irred_invalidated
= true;
364 for (i
= 0; i
< nrem
; i
++)
367 FOR_EACH_EDGE (ae
, ei
, rem_bbs
[i
]->succs
)
368 if (ae
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
369 && !bitmap_bit_p (seen
, ae
->dest
->index
))
371 bitmap_set_bit (seen
, ae
->dest
->index
);
372 bord_bbs
[n_bord_bbs
++] = ae
->dest
;
374 if (ae
->flags
& EDGE_IRREDUCIBLE_LOOP
)
375 irred_invalidated
= true;
379 /* Remove the path. */
384 /* Cancel loops contained in the path. */
385 for (i
= 0; i
< nrem
; i
++)
386 if (rem_bbs
[i
]->loop_father
->header
== rem_bbs
[i
])
387 cancel_loop_tree (rem_bbs
[i
]->loop_father
);
389 remove_bbs (rem_bbs
, nrem
);
392 /* Find blocks whose dominators may be affected. */
394 for (i
= 0; i
< n_bord_bbs
; i
++)
398 bb
= get_immediate_dominator (CDI_DOMINATORS
, bord_bbs
[i
]);
399 if (bitmap_bit_p (seen
, bb
->index
))
401 bitmap_set_bit (seen
, bb
->index
);
403 for (ldom
= first_dom_son (CDI_DOMINATORS
, bb
);
405 ldom
= next_dom_son (CDI_DOMINATORS
, ldom
))
406 if (!dominated_by_p (CDI_DOMINATORS
, from
, ldom
))
407 dom_bbs
.safe_push (ldom
);
412 /* Recount dominators. */
413 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, true);
417 /* Fix placements of basic blocks inside loops and the placement of
418 loops in the loop tree. */
419 fix_bb_placements (from
, &irred_invalidated
, NULL
);
420 fix_loop_placements (from
->loop_father
, &irred_invalidated
);
422 if (irred_invalidated
423 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
424 mark_irreducible_loops ();
429 /* Creates place for a new LOOP in loops structure of FN. */
432 place_new_loop (struct function
*fn
, struct loop
*loop
)
434 loop
->num
= number_of_loops (fn
);
435 vec_safe_push (loops_for_fn (fn
)->larray
, loop
);
438 /* Given LOOP structure with filled header and latch, find the body of the
439 corresponding loop and add it to loops tree. Insert the LOOP as a son of
443 add_loop (struct loop
*loop
, struct loop
*outer
)
447 struct loop
*subloop
;
451 /* Add it to loop structure. */
452 place_new_loop (cfun
, loop
);
453 flow_loop_tree_node_add (outer
, loop
);
455 /* Find its nodes. */
456 bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
457 n
= get_loop_body_with_size (loop
, bbs
, n_basic_blocks_for_fn (cfun
));
459 for (i
= 0; i
< n
; i
++)
461 if (bbs
[i
]->loop_father
== outer
)
463 remove_bb_from_loops (bbs
[i
]);
464 add_bb_to_loop (bbs
[i
], loop
);
470 /* If we find a direct subloop of OUTER, move it to LOOP. */
471 subloop
= bbs
[i
]->loop_father
;
472 if (loop_outer (subloop
) == outer
473 && subloop
->header
== bbs
[i
])
475 flow_loop_tree_node_remove (subloop
);
476 flow_loop_tree_node_add (loop
, subloop
);
480 /* Update the information about loop exit edges. */
481 for (i
= 0; i
< n
; i
++)
483 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
485 rescan_loop_exit (e
, false, false);
492 /* Multiply all frequencies in LOOP by NUM/DEN. */
495 scale_loop_frequencies (struct loop
*loop
, int num
, int den
)
499 bbs
= get_loop_body (loop
);
500 scale_bbs_frequencies_int (bbs
, loop
->num_nodes
, num
, den
);
504 /* Multiply all frequencies in LOOP by SCALE/REG_BR_PROB_BASE.
505 If ITERATION_BOUND is non-zero, scale even further if loop is predicted
506 to iterate too many times. */
509 scale_loop_profile (struct loop
*loop
, int scale
, gcov_type iteration_bound
)
511 gcov_type iterations
= expected_loop_iterations_unbounded (loop
);
515 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
516 fprintf (dump_file
, ";; Scaling loop %i with scale %f, "
517 "bounding iterations to %i from guessed %i\n",
518 loop
->num
, (double)scale
/ REG_BR_PROB_BASE
,
519 (int)iteration_bound
, (int)iterations
);
521 /* See if loop is predicted to iterate too many times. */
522 if (iteration_bound
&& iterations
> 0
523 && apply_probability (iterations
, scale
) > iteration_bound
)
525 /* Fixing loop profile for different trip count is not trivial; the exit
526 probabilities has to be updated to match and frequencies propagated down
529 We fully update only the simple case of loop with single exit that is
530 either from the latch or BB just before latch and leads from BB with
531 simple conditional jump. This is OK for use in vectorizer. */
532 e
= single_exit (loop
);
537 gcov_type count_delta
;
539 FOR_EACH_EDGE (other_e
, ei
, e
->src
->succs
)
540 if (!(other_e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
))
544 /* Probability of exit must be 1/iterations. */
545 freq_delta
= EDGE_FREQUENCY (e
);
546 e
->probability
= REG_BR_PROB_BASE
/ iteration_bound
;
547 other_e
->probability
= inverse_probability (e
->probability
);
548 freq_delta
-= EDGE_FREQUENCY (e
);
550 /* Adjust counts accordingly. */
551 count_delta
= e
->count
;
552 e
->count
= apply_probability (e
->src
->count
, e
->probability
);
553 other_e
->count
= apply_probability (e
->src
->count
, other_e
->probability
);
554 count_delta
-= e
->count
;
556 /* If latch exists, change its frequency and count, since we changed
557 probability of exit. Theoretically we should update everything from
558 source of exit edge to latch, but for vectorizer this is enough. */
560 && loop
->latch
!= e
->src
)
562 loop
->latch
->frequency
+= freq_delta
;
563 if (loop
->latch
->frequency
< 0)
564 loop
->latch
->frequency
= 0;
565 loop
->latch
->count
+= count_delta
;
566 if (loop
->latch
->count
< 0)
567 loop
->latch
->count
= 0;
571 /* Roughly speaking we want to reduce the loop body profile by the
572 the difference of loop iterations. We however can do better if
573 we look at the actual profile, if it is available. */
574 scale
= RDIV (iteration_bound
* scale
, iterations
);
575 if (loop
->header
->count
)
577 gcov_type count_in
= 0;
579 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
580 if (e
->src
!= loop
->latch
)
581 count_in
+= e
->count
;
584 scale
= GCOV_COMPUTE_SCALE (count_in
* iteration_bound
,
585 loop
->header
->count
);
587 else if (loop
->header
->frequency
)
591 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
592 if (e
->src
!= loop
->latch
)
593 freq_in
+= EDGE_FREQUENCY (e
);
596 scale
= GCOV_COMPUTE_SCALE (freq_in
* iteration_bound
,
597 loop
->header
->frequency
);
603 if (scale
== REG_BR_PROB_BASE
)
606 /* Scale the actual probabilities. */
607 scale_loop_frequencies (loop
, scale
, REG_BR_PROB_BASE
);
608 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
609 fprintf (dump_file
, ";; guessed iterations are now %i\n",
610 (int)expected_loop_iterations_unbounded (loop
));
613 /* Recompute dominance information for basic blocks outside LOOP. */
616 update_dominators_in_loop (struct loop
*loop
)
618 vec
<basic_block
> dom_bbs
= vNULL
;
623 seen
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
625 body
= get_loop_body (loop
);
627 for (i
= 0; i
< loop
->num_nodes
; i
++)
628 bitmap_set_bit (seen
, body
[i
]->index
);
630 for (i
= 0; i
< loop
->num_nodes
; i
++)
634 for (ldom
= first_dom_son (CDI_DOMINATORS
, body
[i
]);
636 ldom
= next_dom_son (CDI_DOMINATORS
, ldom
))
637 if (!bitmap_bit_p (seen
, ldom
->index
))
639 bitmap_set_bit (seen
, ldom
->index
);
640 dom_bbs
.safe_push (ldom
);
644 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, false);
650 /* Creates an if region as shown above. CONDITION is used to create
654 | ------------- -------------
655 | | pred_bb | | pred_bb |
656 | ------------- -------------
660 | | ====> -------------
665 | ------------- e_false / \ e_true
667 | ------------- ----------- -----------
668 | | false_bb | | true_bb |
669 | ----------- -----------
676 | | exit_edge (result)
685 create_empty_if_region_on_edge (edge entry_edge
, tree condition
)
688 basic_block cond_bb
, true_bb
, false_bb
, join_bb
;
689 edge e_true
, e_false
, exit_edge
;
692 gimple_stmt_iterator gsi
;
694 cond_bb
= split_edge (entry_edge
);
696 /* Insert condition in cond_bb. */
697 gsi
= gsi_last_bb (cond_bb
);
699 force_gimple_operand_gsi (&gsi
, condition
, true, NULL
,
700 false, GSI_NEW_STMT
);
701 cond_stmt
= gimple_build_cond_from_tree (simple_cond
, NULL_TREE
, NULL_TREE
);
702 gsi
= gsi_last_bb (cond_bb
);
703 gsi_insert_after (&gsi
, cond_stmt
, GSI_NEW_STMT
);
705 join_bb
= split_edge (single_succ_edge (cond_bb
));
707 e_true
= single_succ_edge (cond_bb
);
708 true_bb
= split_edge (e_true
);
710 e_false
= make_edge (cond_bb
, join_bb
, 0);
711 false_bb
= split_edge (e_false
);
713 e_true
->flags
&= ~EDGE_FALLTHRU
;
714 e_true
->flags
|= EDGE_TRUE_VALUE
;
715 e_false
->flags
&= ~EDGE_FALLTHRU
;
716 e_false
->flags
|= EDGE_FALSE_VALUE
;
718 set_immediate_dominator (CDI_DOMINATORS
, cond_bb
, entry_edge
->src
);
719 set_immediate_dominator (CDI_DOMINATORS
, true_bb
, cond_bb
);
720 set_immediate_dominator (CDI_DOMINATORS
, false_bb
, cond_bb
);
721 set_immediate_dominator (CDI_DOMINATORS
, join_bb
, cond_bb
);
723 exit_edge
= single_succ_edge (join_bb
);
725 if (single_pred_p (exit_edge
->dest
))
726 set_immediate_dominator (CDI_DOMINATORS
, exit_edge
->dest
, join_bb
);
731 /* create_empty_loop_on_edge
733 | - pred_bb - ------ pred_bb ------
734 | | | | iv0 = initial_value |
735 | -----|----- ---------|-----------
736 | | ______ | entry_edge
738 | | ====> | -V---V- loop_header -------------
739 | V | | iv_before = phi (iv0, iv_after) |
740 | - succ_bb - | ---|-----------------------------
742 | ----------- | ---V--- loop_body ---------------
743 | | | iv_after = iv_before + stride |
744 | | | if (iv_before < upper_bound) |
745 | | ---|--------------\--------------
748 | | - loop_latch - V- succ_bb -
750 | | /------------- -----------
753 Creates an empty loop as shown above, the IV_BEFORE is the SSA_NAME
754 that is used before the increment of IV. IV_BEFORE should be used for
755 adding code to the body that uses the IV. OUTER is the outer loop in
756 which the new loop should be inserted.
758 Both INITIAL_VALUE and UPPER_BOUND expressions are gimplified and
759 inserted on the loop entry edge. This implies that this function
760 should be used only when the UPPER_BOUND expression is a loop
764 create_empty_loop_on_edge (edge entry_edge
,
766 tree stride
, tree upper_bound
,
772 basic_block loop_header
, loop_latch
, succ_bb
, pred_bb
;
774 gimple_stmt_iterator gsi
;
781 gcc_assert (entry_edge
&& initial_value
&& stride
&& upper_bound
&& iv
);
783 /* Create header, latch and wire up the loop. */
784 pred_bb
= entry_edge
->src
;
785 loop_header
= split_edge (entry_edge
);
786 loop_latch
= split_edge (single_succ_edge (loop_header
));
787 succ_bb
= single_succ (loop_latch
);
788 make_edge (loop_header
, succ_bb
, 0);
789 redirect_edge_succ_nodup (single_succ_edge (loop_latch
), loop_header
);
791 /* Set immediate dominator information. */
792 set_immediate_dominator (CDI_DOMINATORS
, loop_header
, pred_bb
);
793 set_immediate_dominator (CDI_DOMINATORS
, loop_latch
, loop_header
);
794 set_immediate_dominator (CDI_DOMINATORS
, succ_bb
, loop_header
);
796 /* Initialize a loop structure and put it in a loop hierarchy. */
797 loop
= alloc_loop ();
798 loop
->header
= loop_header
;
799 loop
->latch
= loop_latch
;
800 add_loop (loop
, outer
);
802 /* TODO: Fix frequencies and counts. */
803 prob
= REG_BR_PROB_BASE
/ 2;
805 scale_loop_frequencies (loop
, REG_BR_PROB_BASE
- prob
, REG_BR_PROB_BASE
);
807 /* Update dominators. */
808 update_dominators_in_loop (loop
);
810 /* Modify edge flags. */
811 exit_e
= single_exit (loop
);
812 exit_e
->flags
= EDGE_LOOP_EXIT
| EDGE_FALSE_VALUE
;
813 single_pred_edge (loop_latch
)->flags
= EDGE_TRUE_VALUE
;
815 /* Construct IV code in loop. */
816 initial_value
= force_gimple_operand (initial_value
, &stmts
, true, iv
);
819 gsi_insert_seq_on_edge (loop_preheader_edge (loop
), stmts
);
820 gsi_commit_edge_inserts ();
823 upper_bound
= force_gimple_operand (upper_bound
, &stmts
, true, NULL
);
826 gsi_insert_seq_on_edge (loop_preheader_edge (loop
), stmts
);
827 gsi_commit_edge_inserts ();
830 gsi
= gsi_last_bb (loop_header
);
831 create_iv (initial_value
, stride
, iv
, loop
, &gsi
, false,
832 iv_before
, iv_after
);
834 /* Insert loop exit condition. */
835 cond_expr
= gimple_build_cond
836 (LT_EXPR
, *iv_before
, upper_bound
, NULL_TREE
, NULL_TREE
);
838 exit_test
= gimple_cond_lhs (cond_expr
);
839 exit_test
= force_gimple_operand_gsi (&gsi
, exit_test
, true, NULL
,
840 false, GSI_NEW_STMT
);
841 gimple_cond_set_lhs (cond_expr
, exit_test
);
842 gsi
= gsi_last_bb (exit_e
->src
);
843 gsi_insert_after (&gsi
, cond_expr
, GSI_NEW_STMT
);
845 split_block_after_labels (loop_header
);
850 /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
851 latch to header and update loop tree and dominators
852 accordingly. Everything between them plus LATCH_EDGE destination must
853 be dominated by HEADER_EDGE destination, and back-reachable from
854 LATCH_EDGE source. HEADER_EDGE is redirected to basic block SWITCH_BB,
855 FALSE_EDGE of SWITCH_BB to original destination of HEADER_EDGE and
856 TRUE_EDGE of SWITCH_BB to original destination of LATCH_EDGE.
857 Returns the newly created loop. Frequencies and counts in the new loop
858 are scaled by FALSE_SCALE and in the old one by TRUE_SCALE. */
861 loopify (edge latch_edge
, edge header_edge
,
862 basic_block switch_bb
, edge true_edge
, edge false_edge
,
863 bool redirect_all_edges
, unsigned true_scale
, unsigned false_scale
)
865 basic_block succ_bb
= latch_edge
->dest
;
866 basic_block pred_bb
= header_edge
->src
;
867 struct loop
*loop
= alloc_loop ();
868 struct loop
*outer
= loop_outer (succ_bb
->loop_father
);
874 loop
->header
= header_edge
->dest
;
875 loop
->latch
= latch_edge
->src
;
877 freq
= EDGE_FREQUENCY (header_edge
);
878 cnt
= header_edge
->count
;
880 /* Redirect edges. */
881 loop_redirect_edge (latch_edge
, loop
->header
);
882 loop_redirect_edge (true_edge
, succ_bb
);
884 /* During loop versioning, one of the switch_bb edge is already properly
885 set. Do not redirect it again unless redirect_all_edges is true. */
886 if (redirect_all_edges
)
888 loop_redirect_edge (header_edge
, switch_bb
);
889 loop_redirect_edge (false_edge
, loop
->header
);
891 /* Update dominators. */
892 set_immediate_dominator (CDI_DOMINATORS
, switch_bb
, pred_bb
);
893 set_immediate_dominator (CDI_DOMINATORS
, loop
->header
, switch_bb
);
896 set_immediate_dominator (CDI_DOMINATORS
, succ_bb
, switch_bb
);
898 /* Compute new loop. */
899 add_loop (loop
, outer
);
901 /* Add switch_bb to appropriate loop. */
902 if (switch_bb
->loop_father
)
903 remove_bb_from_loops (switch_bb
);
904 add_bb_to_loop (switch_bb
, outer
);
906 /* Fix frequencies. */
907 if (redirect_all_edges
)
909 switch_bb
->frequency
= freq
;
910 switch_bb
->count
= cnt
;
911 FOR_EACH_EDGE (e
, ei
, switch_bb
->succs
)
913 e
->count
= apply_probability (switch_bb
->count
, e
->probability
);
916 scale_loop_frequencies (loop
, false_scale
, REG_BR_PROB_BASE
);
917 scale_loop_frequencies (succ_bb
->loop_father
, true_scale
, REG_BR_PROB_BASE
);
918 update_dominators_in_loop (loop
);
923 /* Remove the latch edge of a LOOP and update loops to indicate that
924 the LOOP was removed. After this function, original loop latch will
925 have no successor, which caller is expected to fix somehow.
927 If this may cause the information about irreducible regions to become
928 invalid, IRRED_INVALIDATED is set to true.
930 LOOP_CLOSED_SSA_INVALIDATED, if non-NULL, is a bitmap where we store
931 basic blocks that had non-trivial update on their loop_father.*/
934 unloop (struct loop
*loop
, bool *irred_invalidated
,
935 bitmap loop_closed_ssa_invalidated
)
940 basic_block latch
= loop
->latch
;
943 if (loop_preheader_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
)
944 *irred_invalidated
= true;
946 /* This is relatively straightforward. The dominators are unchanged, as
947 loop header dominates loop latch, so the only thing we have to care of
948 is the placement of loops and basic blocks inside the loop tree. We
949 move them all to the loop->outer, and then let fix_bb_placements do
952 body
= get_loop_body (loop
);
954 for (i
= 0; i
< n
; i
++)
955 if (body
[i
]->loop_father
== loop
)
957 remove_bb_from_loops (body
[i
]);
958 add_bb_to_loop (body
[i
], loop_outer (loop
));
965 flow_loop_tree_node_remove (ploop
);
966 flow_loop_tree_node_add (loop_outer (loop
), ploop
);
969 /* Remove the loop and free its data. */
972 remove_edge (single_succ_edge (latch
));
974 /* We do not pass IRRED_INVALIDATED to fix_bb_placements here, as even if
975 there is an irreducible region inside the cancelled loop, the flags will
977 fix_bb_placements (latch
, &dummy
, loop_closed_ssa_invalidated
);
980 /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
981 condition stated in description of fix_loop_placement holds for them.
982 It is used in case when we removed some edges coming out of LOOP, which
983 may cause the right placement of LOOP inside loop tree to change.
985 IRRED_INVALIDATED is set to true if a change in the loop structures might
986 invalidate the information about irreducible regions. */
989 fix_loop_placements (struct loop
*loop
, bool *irred_invalidated
)
993 while (loop_outer (loop
))
995 outer
= loop_outer (loop
);
996 if (!fix_loop_placement (loop
, irred_invalidated
))
999 /* Changing the placement of a loop in the loop tree may alter the
1000 validity of condition 2) of the description of fix_bb_placement
1001 for its preheader, because the successor is the header and belongs
1002 to the loop. So call fix_bb_placements to fix up the placement
1003 of the preheader and (possibly) of its predecessors. */
1004 fix_bb_placements (loop_preheader_edge (loop
)->src
,
1005 irred_invalidated
, NULL
);
1010 /* Duplicate loop bounds and other information we store about
1011 the loop into its duplicate. */
1014 copy_loop_info (struct loop
*loop
, struct loop
*target
)
1016 gcc_checking_assert (!target
->any_upper_bound
&& !target
->any_estimate
);
1017 target
->any_upper_bound
= loop
->any_upper_bound
;
1018 target
->nb_iterations_upper_bound
= loop
->nb_iterations_upper_bound
;
1019 target
->any_estimate
= loop
->any_estimate
;
1020 target
->nb_iterations_estimate
= loop
->nb_iterations_estimate
;
1021 target
->estimate_state
= loop
->estimate_state
;
1022 target
->warned_aggressive_loop_optimizations
1023 |= loop
->warned_aggressive_loop_optimizations
;
1026 /* Copies copy of LOOP as subloop of TARGET loop, placing newly
1027 created loop into loops structure. */
1029 duplicate_loop (struct loop
*loop
, struct loop
*target
)
1032 cloop
= alloc_loop ();
1033 place_new_loop (cfun
, cloop
);
1035 copy_loop_info (loop
, cloop
);
1037 /* Mark the new loop as copy of LOOP. */
1038 set_loop_copy (loop
, cloop
);
1040 /* Add it to target. */
1041 flow_loop_tree_node_add (target
, cloop
);
1046 /* Copies structure of subloops of LOOP into TARGET loop, placing
1047 newly created loops into loop tree. */
1049 duplicate_subloops (struct loop
*loop
, struct loop
*target
)
1051 struct loop
*aloop
, *cloop
;
1053 for (aloop
= loop
->inner
; aloop
; aloop
= aloop
->next
)
1055 cloop
= duplicate_loop (aloop
, target
);
1056 duplicate_subloops (aloop
, cloop
);
1060 /* Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
1061 into TARGET loop, placing newly created loops into loop tree. */
1063 copy_loops_to (struct loop
**copied_loops
, int n
, struct loop
*target
)
1068 for (i
= 0; i
< n
; i
++)
1070 aloop
= duplicate_loop (copied_loops
[i
], target
);
1071 duplicate_subloops (copied_loops
[i
], aloop
);
1075 /* Redirects edge E to basic block DEST. */
1077 loop_redirect_edge (edge e
, basic_block dest
)
1079 if (e
->dest
== dest
)
1082 redirect_edge_and_branch_force (e
, dest
);
1085 /* Check whether LOOP's body can be duplicated. */
1087 can_duplicate_loop_p (const struct loop
*loop
)
1090 basic_block
*bbs
= get_loop_body (loop
);
1092 ret
= can_copy_bbs_p (bbs
, loop
->num_nodes
);
1098 /* Sets probability and count of edge E to zero. The probability and count
1099 is redistributed evenly to the remaining edges coming from E->src. */
1102 set_zero_probability (edge e
)
1104 basic_block bb
= e
->src
;
1106 edge ae
, last
= NULL
;
1107 unsigned n
= EDGE_COUNT (bb
->succs
);
1108 gcov_type cnt
= e
->count
, cnt1
;
1109 unsigned prob
= e
->probability
, prob1
;
1112 cnt1
= cnt
/ (n
- 1);
1113 prob1
= prob
/ (n
- 1);
1115 FOR_EACH_EDGE (ae
, ei
, bb
->succs
)
1120 ae
->probability
+= prob1
;
1125 /* Move the rest to one of the edges. */
1126 last
->probability
+= prob
% (n
- 1);
1127 last
->count
+= cnt
% (n
- 1);
1133 /* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating
1134 loop structure and dominators. E's destination must be LOOP header for
1135 this to work, i.e. it must be entry or latch edge of this loop; these are
1136 unique, as the loops must have preheaders for this function to work
1137 correctly (in case E is latch, the function unrolls the loop, if E is entry
1138 edge, it peels the loop). Store edges created by copying ORIG edge from
1139 copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to
1140 original LOOP body, the other copies are numbered in order given by control
1141 flow through them) into TO_REMOVE array. Returns false if duplication is
1145 duplicate_loop_to_header_edge (struct loop
*loop
, edge e
,
1146 unsigned int ndupl
, sbitmap wont_exit
,
1147 edge orig
, vec
<edge
> *to_remove
,
1150 struct loop
*target
, *aloop
;
1151 struct loop
**orig_loops
;
1152 unsigned n_orig_loops
;
1153 basic_block header
= loop
->header
, latch
= loop
->latch
;
1154 basic_block
*new_bbs
, *bbs
, *first_active
;
1155 basic_block new_bb
, bb
, first_active_latch
= NULL
;
1156 edge ae
, latch_edge
;
1157 edge spec_edges
[2], new_spec_edges
[2];
1161 int is_latch
= (latch
== e
->src
);
1162 int scale_act
= 0, *scale_step
= NULL
, scale_main
= 0;
1163 int scale_after_exit
= 0;
1164 int p
, freq_in
, freq_le
, freq_out_orig
;
1165 int prob_pass_thru
, prob_pass_wont_exit
, prob_pass_main
;
1166 int add_irreducible_flag
;
1167 basic_block place_after
;
1168 bitmap bbs_to_scale
= NULL
;
1171 gcc_assert (e
->dest
== loop
->header
);
1172 gcc_assert (ndupl
> 0);
1176 /* Orig must be edge out of the loop. */
1177 gcc_assert (flow_bb_inside_loop_p (loop
, orig
->src
));
1178 gcc_assert (!flow_bb_inside_loop_p (loop
, orig
->dest
));
1181 n
= loop
->num_nodes
;
1182 bbs
= get_loop_body_in_dom_order (loop
);
1183 gcc_assert (bbs
[0] == loop
->header
);
1184 gcc_assert (bbs
[n
- 1] == loop
->latch
);
1186 /* Check whether duplication is possible. */
1187 if (!can_copy_bbs_p (bbs
, loop
->num_nodes
))
1192 new_bbs
= XNEWVEC (basic_block
, loop
->num_nodes
);
1194 /* In case we are doing loop peeling and the loop is in the middle of
1195 irreducible region, the peeled copies will be inside it too. */
1196 add_irreducible_flag
= e
->flags
& EDGE_IRREDUCIBLE_LOOP
;
1197 gcc_assert (!is_latch
|| !add_irreducible_flag
);
1199 /* Find edge from latch. */
1200 latch_edge
= loop_latch_edge (loop
);
1202 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
1204 /* Calculate coefficients by that we have to scale frequencies
1205 of duplicated loop bodies. */
1206 freq_in
= header
->frequency
;
1207 freq_le
= EDGE_FREQUENCY (latch_edge
);
1210 if (freq_in
< freq_le
)
1212 freq_out_orig
= orig
? EDGE_FREQUENCY (orig
) : freq_in
- freq_le
;
1213 if (freq_out_orig
> freq_in
- freq_le
)
1214 freq_out_orig
= freq_in
- freq_le
;
1215 prob_pass_thru
= RDIV (REG_BR_PROB_BASE
* freq_le
, freq_in
);
1216 prob_pass_wont_exit
=
1217 RDIV (REG_BR_PROB_BASE
* (freq_le
+ freq_out_orig
), freq_in
);
1220 && REG_BR_PROB_BASE
- orig
->probability
!= 0)
1222 /* The blocks that are dominated by a removed exit edge ORIG have
1223 frequencies scaled by this. */
1225 = GCOV_COMPUTE_SCALE (REG_BR_PROB_BASE
,
1226 REG_BR_PROB_BASE
- orig
->probability
);
1227 bbs_to_scale
= BITMAP_ALLOC (NULL
);
1228 for (i
= 0; i
< n
; i
++)
1230 if (bbs
[i
] != orig
->src
1231 && dominated_by_p (CDI_DOMINATORS
, bbs
[i
], orig
->src
))
1232 bitmap_set_bit (bbs_to_scale
, i
);
1236 scale_step
= XNEWVEC (int, ndupl
);
1238 for (i
= 1; i
<= ndupl
; i
++)
1239 scale_step
[i
- 1] = bitmap_bit_p (wont_exit
, i
)
1240 ? prob_pass_wont_exit
1243 /* Complete peeling is special as the probability of exit in last
1245 if (flags
& DLTHE_FLAG_COMPLETTE_PEEL
)
1247 int wanted_freq
= EDGE_FREQUENCY (e
);
1249 if (wanted_freq
> freq_in
)
1250 wanted_freq
= freq_in
;
1252 gcc_assert (!is_latch
);
1253 /* First copy has frequency of incoming edge. Each subsequent
1254 frequency should be reduced by prob_pass_wont_exit. Caller
1255 should've managed the flags so all except for original loop
1256 has won't exist set. */
1257 scale_act
= GCOV_COMPUTE_SCALE (wanted_freq
, freq_in
);
1258 /* Now simulate the duplication adjustments and compute header
1259 frequency of the last copy. */
1260 for (i
= 0; i
< ndupl
; i
++)
1261 wanted_freq
= combine_probabilities (wanted_freq
, scale_step
[i
]);
1262 scale_main
= GCOV_COMPUTE_SCALE (wanted_freq
, freq_in
);
1266 prob_pass_main
= bitmap_bit_p (wont_exit
, 0)
1267 ? prob_pass_wont_exit
1270 scale_main
= REG_BR_PROB_BASE
;
1271 for (i
= 0; i
< ndupl
; i
++)
1274 p
= combine_probabilities (p
, scale_step
[i
]);
1276 scale_main
= GCOV_COMPUTE_SCALE (REG_BR_PROB_BASE
, scale_main
);
1277 scale_act
= combine_probabilities (scale_main
, prob_pass_main
);
1281 scale_main
= REG_BR_PROB_BASE
;
1282 for (i
= 0; i
< ndupl
; i
++)
1283 scale_main
= combine_probabilities (scale_main
, scale_step
[i
]);
1284 scale_act
= REG_BR_PROB_BASE
- prob_pass_thru
;
1286 for (i
= 0; i
< ndupl
; i
++)
1287 gcc_assert (scale_step
[i
] >= 0 && scale_step
[i
] <= REG_BR_PROB_BASE
);
1288 gcc_assert (scale_main
>= 0 && scale_main
<= REG_BR_PROB_BASE
1289 && scale_act
>= 0 && scale_act
<= REG_BR_PROB_BASE
);
1292 /* Loop the new bbs will belong to. */
1293 target
= e
->src
->loop_father
;
1295 /* Original loops. */
1297 for (aloop
= loop
->inner
; aloop
; aloop
= aloop
->next
)
1299 orig_loops
= XNEWVEC (struct loop
*, n_orig_loops
);
1300 for (aloop
= loop
->inner
, i
= 0; aloop
; aloop
= aloop
->next
, i
++)
1301 orig_loops
[i
] = aloop
;
1303 set_loop_copy (loop
, target
);
1305 first_active
= XNEWVEC (basic_block
, n
);
1308 memcpy (first_active
, bbs
, n
* sizeof (basic_block
));
1309 first_active_latch
= latch
;
1312 spec_edges
[SE_ORIG
] = orig
;
1313 spec_edges
[SE_LATCH
] = latch_edge
;
1315 place_after
= e
->src
;
1316 for (j
= 0; j
< ndupl
; j
++)
1319 copy_loops_to (orig_loops
, n_orig_loops
, target
);
1322 copy_bbs (bbs
, n
, new_bbs
, spec_edges
, 2, new_spec_edges
, loop
,
1324 place_after
= new_spec_edges
[SE_LATCH
]->src
;
1326 if (flags
& DLTHE_RECORD_COPY_NUMBER
)
1327 for (i
= 0; i
< n
; i
++)
1329 gcc_assert (!new_bbs
[i
]->aux
);
1330 new_bbs
[i
]->aux
= (void *)(size_t)(j
+ 1);
1333 /* Note whether the blocks and edges belong to an irreducible loop. */
1334 if (add_irreducible_flag
)
1336 for (i
= 0; i
< n
; i
++)
1337 new_bbs
[i
]->flags
|= BB_DUPLICATED
;
1338 for (i
= 0; i
< n
; i
++)
1341 new_bb
= new_bbs
[i
];
1342 if (new_bb
->loop_father
== target
)
1343 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
1345 FOR_EACH_EDGE (ae
, ei
, new_bb
->succs
)
1346 if ((ae
->dest
->flags
& BB_DUPLICATED
)
1347 && (ae
->src
->loop_father
== target
1348 || ae
->dest
->loop_father
== target
))
1349 ae
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1351 for (i
= 0; i
< n
; i
++)
1352 new_bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1355 /* Redirect the special edges. */
1358 redirect_edge_and_branch_force (latch_edge
, new_bbs
[0]);
1359 redirect_edge_and_branch_force (new_spec_edges
[SE_LATCH
],
1361 set_immediate_dominator (CDI_DOMINATORS
, new_bbs
[0], latch
);
1362 latch
= loop
->latch
= new_bbs
[n
- 1];
1363 e
= latch_edge
= new_spec_edges
[SE_LATCH
];
1367 redirect_edge_and_branch_force (new_spec_edges
[SE_LATCH
],
1369 redirect_edge_and_branch_force (e
, new_bbs
[0]);
1370 set_immediate_dominator (CDI_DOMINATORS
, new_bbs
[0], e
->src
);
1371 e
= new_spec_edges
[SE_LATCH
];
1374 /* Record exit edge in this copy. */
1375 if (orig
&& bitmap_bit_p (wont_exit
, j
+ 1))
1378 to_remove
->safe_push (new_spec_edges
[SE_ORIG
]);
1379 set_zero_probability (new_spec_edges
[SE_ORIG
]);
1381 /* Scale the frequencies of the blocks dominated by the exit. */
1384 EXECUTE_IF_SET_IN_BITMAP (bbs_to_scale
, 0, i
, bi
)
1386 scale_bbs_frequencies_int (new_bbs
+ i
, 1, scale_after_exit
,
1392 /* Record the first copy in the control flow order if it is not
1393 the original loop (i.e. in case of peeling). */
1394 if (!first_active_latch
)
1396 memcpy (first_active
, new_bbs
, n
* sizeof (basic_block
));
1397 first_active_latch
= new_bbs
[n
- 1];
1400 /* Set counts and frequencies. */
1401 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
1403 scale_bbs_frequencies_int (new_bbs
, n
, scale_act
, REG_BR_PROB_BASE
);
1404 scale_act
= combine_probabilities (scale_act
, scale_step
[j
]);
1410 /* Record the exit edge in the original loop body, and update the frequencies. */
1411 if (orig
&& bitmap_bit_p (wont_exit
, 0))
1414 to_remove
->safe_push (orig
);
1415 set_zero_probability (orig
);
1417 /* Scale the frequencies of the blocks dominated by the exit. */
1420 EXECUTE_IF_SET_IN_BITMAP (bbs_to_scale
, 0, i
, bi
)
1422 scale_bbs_frequencies_int (bbs
+ i
, 1, scale_after_exit
,
1428 /* Update the original loop. */
1430 set_immediate_dominator (CDI_DOMINATORS
, e
->dest
, e
->src
);
1431 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
1433 scale_bbs_frequencies_int (bbs
, n
, scale_main
, REG_BR_PROB_BASE
);
1437 /* Update dominators of outer blocks if affected. */
1438 for (i
= 0; i
< n
; i
++)
1440 basic_block dominated
, dom_bb
;
1441 vec
<basic_block
> dom_bbs
;
1447 dom_bbs
= get_dominated_by (CDI_DOMINATORS
, bb
);
1448 FOR_EACH_VEC_ELT (dom_bbs
, j
, dominated
)
1450 if (flow_bb_inside_loop_p (loop
, dominated
))
1452 dom_bb
= nearest_common_dominator (
1453 CDI_DOMINATORS
, first_active
[i
], first_active_latch
);
1454 set_immediate_dominator (CDI_DOMINATORS
, dominated
, dom_bb
);
1458 free (first_active
);
1461 BITMAP_FREE (bbs_to_scale
);
1466 /* A callback for make_forwarder block, to redirect all edges except for
1467 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
1468 whether to redirect it. */
1472 mfb_keep_just (edge e
)
1474 return e
!= mfb_kj_edge
;
1477 /* True when a candidate preheader BLOCK has predecessors from LOOP. */
1480 has_preds_from_loop (basic_block block
, struct loop
*loop
)
1485 FOR_EACH_EDGE (e
, ei
, block
->preds
)
1486 if (e
->src
->loop_father
== loop
)
1491 /* Creates a pre-header for a LOOP. Returns newly created block. Unless
1492 CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
1493 entry; otherwise we also force preheader block to have only one successor.
1494 When CP_FALLTHRU_PREHEADERS is set in FLAGS, we force the preheader block
1495 to be a fallthru predecessor to the loop header and to have only
1496 predecessors from outside of the loop.
1497 The function also updates dominators. */
1500 create_preheader (struct loop
*loop
, int flags
)
1506 bool latch_edge_was_fallthru
;
1507 edge one_succ_pred
= NULL
, single_entry
= NULL
;
1510 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1512 if (e
->src
== loop
->latch
)
1514 irred
|= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
1517 if (single_succ_p (e
->src
))
1520 gcc_assert (nentry
);
1523 bool need_forwarder_block
= false;
1525 /* We do not allow entry block to be the loop preheader, since we
1526 cannot emit code there. */
1527 if (single_entry
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1528 need_forwarder_block
= true;
1531 /* If we want simple preheaders, also force the preheader to have
1532 just a single successor. */
1533 if ((flags
& CP_SIMPLE_PREHEADERS
)
1534 && !single_succ_p (single_entry
->src
))
1535 need_forwarder_block
= true;
1536 /* If we want fallthru preheaders, also create forwarder block when
1537 preheader ends with a jump or has predecessors from loop. */
1538 else if ((flags
& CP_FALLTHRU_PREHEADERS
)
1539 && (JUMP_P (BB_END (single_entry
->src
))
1540 || has_preds_from_loop (single_entry
->src
, loop
)))
1541 need_forwarder_block
= true;
1543 if (! need_forwarder_block
)
1547 mfb_kj_edge
= loop_latch_edge (loop
);
1548 latch_edge_was_fallthru
= (mfb_kj_edge
->flags
& EDGE_FALLTHRU
) != 0;
1549 fallthru
= make_forwarder_block (loop
->header
, mfb_keep_just
, NULL
);
1550 dummy
= fallthru
->src
;
1551 loop
->header
= fallthru
->dest
;
1553 /* Try to be clever in placing the newly created preheader. The idea is to
1554 avoid breaking any "fallthruness" relationship between blocks.
1556 The preheader was created just before the header and all incoming edges
1557 to the header were redirected to the preheader, except the latch edge.
1558 So the only problematic case is when this latch edge was a fallthru
1559 edge: it is not anymore after the preheader creation so we have broken
1560 the fallthruness. We're therefore going to look for a better place. */
1561 if (latch_edge_was_fallthru
)
1566 e
= EDGE_PRED (dummy
, 0);
1568 move_block_after (dummy
, e
->src
);
1573 dummy
->flags
|= BB_IRREDUCIBLE_LOOP
;
1574 single_succ_edge (dummy
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1578 fprintf (dump_file
, "Created preheader block for loop %i\n",
1581 if (flags
& CP_FALLTHRU_PREHEADERS
)
1582 gcc_assert ((single_succ_edge (dummy
)->flags
& EDGE_FALLTHRU
)
1583 && !JUMP_P (BB_END (dummy
)));
1588 /* Create preheaders for each loop; for meaning of FLAGS see create_preheader. */
1591 create_preheaders (int flags
)
1598 FOR_EACH_LOOP (loop
, 0)
1599 create_preheader (loop
, flags
);
1600 loops_state_set (LOOPS_HAVE_PREHEADERS
);
1603 /* Forces all loop latches to have only single successor. */
1606 force_single_succ_latches (void)
1611 FOR_EACH_LOOP (loop
, 0)
1613 if (loop
->latch
!= loop
->header
&& single_succ_p (loop
->latch
))
1616 e
= find_edge (loop
->latch
, loop
->header
);
1617 gcc_checking_assert (e
!= NULL
);
1621 loops_state_set (LOOPS_HAVE_SIMPLE_LATCHES
);
1624 /* This function is called from loop_version. It splits the entry edge
1625 of the loop we want to version, adds the versioning condition, and
1626 adjust the edges to the two versions of the loop appropriately.
1627 e is an incoming edge. Returns the basic block containing the
1630 --- edge e ---- > [second_head]
1632 Split it and insert new conditional expression and adjust edges.
1634 --- edge e ---> [cond expr] ---> [first_head]
1636 +---------> [second_head]
1638 THEN_PROB is the probability of then branch of the condition. */
1641 lv_adjust_loop_entry_edge (basic_block first_head
, basic_block second_head
,
1642 edge e
, void *cond_expr
, unsigned then_prob
)
1644 basic_block new_head
= NULL
;
1647 gcc_assert (e
->dest
== second_head
);
1649 /* Split edge 'e'. This will create a new basic block, where we can
1650 insert conditional expr. */
1651 new_head
= split_edge (e
);
1653 lv_add_condition_to_bb (first_head
, second_head
, new_head
,
1656 /* Don't set EDGE_TRUE_VALUE in RTL mode, as it's invalid there. */
1657 e
= single_succ_edge (new_head
);
1658 e1
= make_edge (new_head
, first_head
,
1659 current_ir_type () == IR_GIMPLE
? EDGE_TRUE_VALUE
: 0);
1660 e1
->probability
= then_prob
;
1661 e
->probability
= REG_BR_PROB_BASE
- then_prob
;
1662 e1
->count
= apply_probability (e
->count
, e1
->probability
);
1663 e
->count
= apply_probability (e
->count
, e
->probability
);
1665 set_immediate_dominator (CDI_DOMINATORS
, first_head
, new_head
);
1666 set_immediate_dominator (CDI_DOMINATORS
, second_head
, new_head
);
1668 /* Adjust loop header phi nodes. */
1669 lv_adjust_loop_header_phi (first_head
, second_head
, new_head
, e1
);
1674 /* Main entry point for Loop Versioning transformation.
1676 This transformation given a condition and a loop, creates
1677 -if (condition) { loop_copy1 } else { loop_copy2 },
1678 where loop_copy1 is the loop transformed in one way, and loop_copy2
1679 is the loop transformed in another way (or unchanged). 'condition'
1680 may be a run time test for things that were not resolved by static
1681 analysis (overlapping ranges (anti-aliasing), alignment, etc.).
1683 THEN_PROB is the probability of the then edge of the if. THEN_SCALE
1684 is the ratio by that the frequencies in the original loop should
1685 be scaled. ELSE_SCALE is the ratio by that the frequencies in the
1686 new loop should be scaled.
1688 If PLACE_AFTER is true, we place the new loop after LOOP in the
1689 instruction stream, otherwise it is placed before LOOP. */
1692 loop_version (struct loop
*loop
,
1693 void *cond_expr
, basic_block
*condition_bb
,
1694 unsigned then_prob
, unsigned then_scale
, unsigned else_scale
,
1697 basic_block first_head
, second_head
;
1698 edge entry
, latch_edge
, true_edge
, false_edge
;
1701 basic_block cond_bb
;
1703 /* Record entry and latch edges for the loop */
1704 entry
= loop_preheader_edge (loop
);
1705 irred_flag
= entry
->flags
& EDGE_IRREDUCIBLE_LOOP
;
1706 entry
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
1708 /* Note down head of loop as first_head. */
1709 first_head
= entry
->dest
;
1711 /* Duplicate loop. */
1712 if (!cfg_hook_duplicate_loop_to_header_edge (loop
, entry
, 1,
1713 NULL
, NULL
, NULL
, 0))
1715 entry
->flags
|= irred_flag
;
1719 /* After duplication entry edge now points to new loop head block.
1720 Note down new head as second_head. */
1721 second_head
= entry
->dest
;
1723 /* Split loop entry edge and insert new block with cond expr. */
1724 cond_bb
= lv_adjust_loop_entry_edge (first_head
, second_head
,
1725 entry
, cond_expr
, then_prob
);
1727 *condition_bb
= cond_bb
;
1731 entry
->flags
|= irred_flag
;
1735 latch_edge
= single_succ_edge (get_bb_copy (loop
->latch
));
1737 extract_cond_bb_edges (cond_bb
, &true_edge
, &false_edge
);
1738 nloop
= loopify (latch_edge
,
1739 single_pred_edge (get_bb_copy (loop
->header
)),
1740 cond_bb
, true_edge
, false_edge
,
1741 false /* Do not redirect all edges. */,
1742 then_scale
, else_scale
);
1744 copy_loop_info (loop
, nloop
);
1746 /* loopify redirected latch_edge. Update its PENDING_STMTS. */
1747 lv_flush_pending_stmts (latch_edge
);
1749 /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */
1750 extract_cond_bb_edges (cond_bb
, &true_edge
, &false_edge
);
1751 lv_flush_pending_stmts (false_edge
);
1752 /* Adjust irreducible flag. */
1755 cond_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
1756 loop_preheader_edge (loop
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1757 loop_preheader_edge (nloop
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1758 single_pred_edge (cond_bb
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1763 basic_block
*bbs
= get_loop_body_in_dom_order (nloop
), after
;
1766 after
= loop
->latch
;
1768 for (i
= 0; i
< nloop
->num_nodes
; i
++)
1770 move_block_after (bbs
[i
], after
);
1776 /* At this point condition_bb is loop preheader with two successors,
1777 first_head and second_head. Make sure that loop preheader has only
1779 split_edge (loop_preheader_edge (loop
));
1780 split_edge (loop_preheader_edge (nloop
));