2 Copyright (C) 2015-2020 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
26 #include "tree-pass.h"
28 #include "fold-const.h"
31 #include "tree-ssa-loop-niter.h"
32 #include "tree-ssa-loop.h"
33 #include "tree-ssa-loop-manip.h"
34 #include "tree-into-ssa.h"
35 #include "tree-inline.h"
36 #include "tree-cfgcleanup.h"
38 #include "tree-scalar-evolution.h"
39 #include "gimple-iterator.h"
40 #include "gimple-pretty-print.h"
42 #include "gimple-fold.h"
43 #include "gimplify-me.h"
45 /* This file implements two kinds of loop splitting.
47 One transformation of loops like:
49 for (i = 0; i < 100; i++)
59 for (i = 0; i < 50; i++)
70 /* Return true when BB inside LOOP is a potential iteration space
71 split point, i.e. ends with a condition like "IV < comp", which
72 is true on one side of the iteration space and false on the other,
73 and the split point can be computed. If so, also return the border
74 point in *BORDER and the comparison induction variable in IV. */
77 split_at_bb_p (class loop
*loop
, basic_block bb
, tree
*border
, affine_iv
*iv
)
83 /* BB must end in a simple conditional jump. */
84 last
= last_stmt (bb
);
85 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
87 stmt
= as_a
<gcond
*> (last
);
89 enum tree_code code
= gimple_cond_code (stmt
);
91 /* Only handle relational comparisons, for equality and non-equality
92 we'd have to split the loop into two loops and a middle statement. */
104 if (loop_exits_from_bb_p (loop
, bb
))
107 tree op0
= gimple_cond_lhs (stmt
);
108 tree op1
= gimple_cond_rhs (stmt
);
109 class loop
*useloop
= loop_containing_stmt (stmt
);
111 if (!simple_iv (loop
, useloop
, op0
, iv
, false))
113 if (!simple_iv (loop
, useloop
, op1
, &iv2
, false))
116 /* Make it so that the first argument of the condition is
118 if (!integer_zerop (iv2
.step
))
120 std::swap (op0
, op1
);
121 std::swap (*iv
, iv2
);
122 code
= swap_tree_comparison (code
);
123 gimple_cond_set_condition (stmt
, code
, op0
, op1
);
126 else if (integer_zerop (iv
->step
))
128 if (!integer_zerop (iv2
.step
))
130 if (!iv
->no_overflow
)
133 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
135 fprintf (dump_file
, "Found potential split point: ");
136 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
137 fprintf (dump_file
, " { ");
138 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
139 fprintf (dump_file
, " + I*");
140 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
141 fprintf (dump_file
, " } %s ", get_tree_code_name (code
));
142 print_generic_expr (dump_file
, iv2
.base
, TDF_SLIM
);
143 fprintf (dump_file
, "\n");
150 /* Given a GUARD conditional stmt inside LOOP, which we want to make always
151 true or false depending on INITIAL_TRUE, and adjusted values NEXTVAL
152 (a post-increment IV) and NEWBOUND (the comparator) adjust the loop
153 exit test statement to loop back only if the GUARD statement will
154 also be true/false in the next iteration. */
157 patch_loop_exit (class loop
*loop
, gcond
*guard
, tree nextval
, tree newbound
,
160 edge exit
= single_exit (loop
);
161 gcond
*stmt
= as_a
<gcond
*> (last_stmt (exit
->src
));
162 gimple_cond_set_condition (stmt
, gimple_cond_code (guard
),
166 edge stay
= EDGE_SUCC (exit
->src
, EDGE_SUCC (exit
->src
, 0) == exit
);
168 exit
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
169 stay
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
173 exit
->flags
|= EDGE_FALSE_VALUE
;
174 stay
->flags
|= EDGE_TRUE_VALUE
;
178 exit
->flags
|= EDGE_TRUE_VALUE
;
179 stay
->flags
|= EDGE_FALSE_VALUE
;
183 /* Give an induction variable GUARD_IV, and its affine descriptor IV,
184 find the loop phi node in LOOP defining it directly, or create
185 such phi node. Return that phi node. */
188 find_or_create_guard_phi (class loop
*loop
, tree guard_iv
, affine_iv
* /*iv*/)
190 gimple
*def
= SSA_NAME_DEF_STMT (guard_iv
);
192 if ((phi
= dyn_cast
<gphi
*> (def
))
193 && gimple_bb (phi
) == loop
->header
)
196 /* XXX Create the PHI instead. */
200 /* Returns true if the exit values of all loop phi nodes can be
201 determined easily (i.e. that connect_loop_phis can determine them). */
204 easy_exit_values (class loop
*loop
)
206 edge exit
= single_exit (loop
);
207 edge latch
= loop_latch_edge (loop
);
210 /* Currently we regard the exit values as easy if they are the same
211 as the value over the backedge. Which is the case if the definition
212 of the backedge value dominates the exit edge. */
213 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
215 gphi
*phi
= psi
.phi ();
216 tree next
= PHI_ARG_DEF_FROM_EDGE (phi
, latch
);
218 if (TREE_CODE (next
) == SSA_NAME
219 && (bb
= gimple_bb (SSA_NAME_DEF_STMT (next
)))
220 && !dominated_by_p (CDI_DOMINATORS
, exit
->src
, bb
))
227 /* This function updates the SSA form after connect_loops made a new
228 edge NEW_E leading from LOOP1 exit to LOOP2 (via in intermediate
229 conditional). I.e. the second loop can now be entered either
230 via the original entry or via NEW_E, so the entry values of LOOP2
231 phi nodes are either the original ones or those at the exit
232 of LOOP1. Insert new phi nodes in LOOP2 pre-header reflecting
233 this. The loops need to fulfill easy_exit_values(). */
236 connect_loop_phis (class loop
*loop1
, class loop
*loop2
, edge new_e
)
238 basic_block rest
= loop_preheader_edge (loop2
)->src
;
239 gcc_assert (new_e
->dest
== rest
);
240 edge skip_first
= EDGE_PRED (rest
, EDGE_PRED (rest
, 0) == new_e
);
242 edge firste
= loop_preheader_edge (loop1
);
243 edge seconde
= loop_preheader_edge (loop2
);
244 edge firstn
= loop_latch_edge (loop1
);
245 gphi_iterator psi_first
, psi_second
;
246 for (psi_first
= gsi_start_phis (loop1
->header
),
247 psi_second
= gsi_start_phis (loop2
->header
);
248 !gsi_end_p (psi_first
);
249 gsi_next (&psi_first
), gsi_next (&psi_second
))
251 tree init
, next
, new_init
;
253 gphi
*phi_first
= psi_first
.phi ();
254 gphi
*phi_second
= psi_second
.phi ();
256 init
= PHI_ARG_DEF_FROM_EDGE (phi_first
, firste
);
257 next
= PHI_ARG_DEF_FROM_EDGE (phi_first
, firstn
);
258 op
= PHI_ARG_DEF_PTR_FROM_EDGE (phi_second
, seconde
);
259 gcc_assert (operand_equal_for_phi_arg_p (init
, USE_FROM_PTR (op
)));
261 /* Prefer using original variable as a base for the new ssa name.
262 This is necessary for virtual ops, and useful in order to avoid
263 losing debug info for real ops. */
264 if (TREE_CODE (next
) == SSA_NAME
265 && useless_type_conversion_p (TREE_TYPE (next
),
267 new_init
= copy_ssa_name (next
);
268 else if (TREE_CODE (init
) == SSA_NAME
269 && useless_type_conversion_p (TREE_TYPE (init
),
271 new_init
= copy_ssa_name (init
);
272 else if (useless_type_conversion_p (TREE_TYPE (next
),
274 new_init
= make_temp_ssa_name (TREE_TYPE (next
), NULL
,
277 new_init
= make_temp_ssa_name (TREE_TYPE (init
), NULL
,
280 gphi
* newphi
= create_phi_node (new_init
, rest
);
281 add_phi_arg (newphi
, init
, skip_first
, UNKNOWN_LOCATION
);
282 add_phi_arg (newphi
, next
, new_e
, UNKNOWN_LOCATION
);
283 SET_USE (op
, new_init
);
287 /* The two loops LOOP1 and LOOP2 were just created by loop versioning,
288 they are still equivalent and placed in two arms of a diamond, like so:
290 .------if (cond)------.
303 This function transforms the program such that LOOP1 is conditionally
304 falling through to LOOP2, or skipping it. This is done by splitting
305 the ex1->join edge at X in the diagram above, and inserting a condition
306 whose one arm goes to pre2, resulting in this situation:
308 .------if (cond)------.
310 pre1 .---------->pre2
314 | ex1---. | .---ex2 |
316 '---l1 skip---' | l2---'
322 The condition used is the exit condition of LOOP1, which effectively means
323 that when the first loop exits (for whatever reason) but the real original
324 exit expression is still false the second loop will be entered.
325 The function returns the new edge cond->pre2.
327 This doesn't update the SSA form, see connect_loop_phis for that. */
330 connect_loops (class loop
*loop1
, class loop
*loop2
)
332 edge exit
= single_exit (loop1
);
333 basic_block skip_bb
= split_edge (exit
);
335 gimple_stmt_iterator gsi
;
338 gimple
*stmt
= last_stmt (exit
->src
);
339 skip_stmt
= gimple_build_cond (gimple_cond_code (stmt
),
340 gimple_cond_lhs (stmt
),
341 gimple_cond_rhs (stmt
),
342 NULL_TREE
, NULL_TREE
);
343 gsi
= gsi_last_bb (skip_bb
);
344 gsi_insert_after (&gsi
, skip_stmt
, GSI_NEW_STMT
);
346 skip_e
= EDGE_SUCC (skip_bb
, 0);
347 skip_e
->flags
&= ~EDGE_FALLTHRU
;
348 new_e
= make_edge (skip_bb
, loop_preheader_edge (loop2
)->src
, 0);
349 if (exit
->flags
& EDGE_TRUE_VALUE
)
351 skip_e
->flags
|= EDGE_TRUE_VALUE
;
352 new_e
->flags
|= EDGE_FALSE_VALUE
;
356 skip_e
->flags
|= EDGE_FALSE_VALUE
;
357 new_e
->flags
|= EDGE_TRUE_VALUE
;
360 new_e
->probability
= profile_probability::likely ();
361 skip_e
->probability
= new_e
->probability
.invert ();
366 /* This returns the new bound for iterations given the original iteration
367 space in NITER, an arbitrary new bound BORDER, assumed to be some
368 comparison value with a different IV, the initial value GUARD_INIT of
369 that other IV, and the comparison code GUARD_CODE that compares
370 that other IV with BORDER. We return an SSA name, and place any
371 necessary statements for that computation into *STMTS.
373 For example for such a loop:
375 for (i = beg, j = guard_init; i < end; i++, j++)
376 if (j < border) // this is supposed to be true/false
379 we want to return a new bound (on j) that makes the loop iterate
380 as long as the condition j < border stays true. We also don't want
381 to iterate more often than the original loop, so we have to introduce
382 some cut-off as well (via min/max), effectively resulting in:
384 newend = min (end+guard_init-beg, border)
385 for (i = beg; j = guard_init; j < newend; i++, j++)
389 Depending on the direction of the IVs and if the exit tests
390 are strict or non-strict we need to use MIN or MAX,
391 and add or subtract 1. This routine computes newend above. */
394 compute_new_first_bound (gimple_seq
*stmts
, class tree_niter_desc
*niter
,
396 enum tree_code guard_code
, tree guard_init
)
398 /* The niter structure contains the after-increment IV, we need
399 the loop-enter base, so subtract STEP once. */
400 tree controlbase
= force_gimple_operand (niter
->control
.base
,
401 stmts
, true, NULL_TREE
);
402 tree controlstep
= niter
->control
.step
;
404 if (POINTER_TYPE_P (TREE_TYPE (controlbase
)))
406 controlstep
= gimple_build (stmts
, NEGATE_EXPR
,
407 TREE_TYPE (controlstep
), controlstep
);
408 enddiff
= gimple_build (stmts
, POINTER_PLUS_EXPR
,
409 TREE_TYPE (controlbase
),
410 controlbase
, controlstep
);
413 enddiff
= gimple_build (stmts
, MINUS_EXPR
,
414 TREE_TYPE (controlbase
),
415 controlbase
, controlstep
);
417 /* Compute end-beg. */
419 tree end
= force_gimple_operand (niter
->bound
, &stmts2
,
421 gimple_seq_add_seq_without_update (stmts
, stmts2
);
422 if (POINTER_TYPE_P (TREE_TYPE (enddiff
)))
424 tree tem
= gimple_convert (stmts
, sizetype
, enddiff
);
425 tem
= gimple_build (stmts
, NEGATE_EXPR
, sizetype
, tem
);
426 enddiff
= gimple_build (stmts
, POINTER_PLUS_EXPR
,
431 enddiff
= gimple_build (stmts
, MINUS_EXPR
, TREE_TYPE (enddiff
),
434 /* Compute guard_init + (end-beg). */
436 enddiff
= gimple_convert (stmts
, TREE_TYPE (guard_init
), enddiff
);
437 if (POINTER_TYPE_P (TREE_TYPE (guard_init
)))
439 enddiff
= gimple_convert (stmts
, sizetype
, enddiff
);
440 newbound
= gimple_build (stmts
, POINTER_PLUS_EXPR
,
441 TREE_TYPE (guard_init
),
442 guard_init
, enddiff
);
445 newbound
= gimple_build (stmts
, PLUS_EXPR
, TREE_TYPE (guard_init
),
446 guard_init
, enddiff
);
448 /* Depending on the direction of the IVs the new bound for the first
449 loop is the minimum or maximum of old bound and border.
450 Also, if the guard condition isn't strictly less or greater,
451 we need to adjust the bound. */
453 enum tree_code minmax
;
454 if (niter
->cmp
== LT_EXPR
)
456 /* GT and LE are the same, inverted. */
457 if (guard_code
== GT_EXPR
|| guard_code
== LE_EXPR
)
463 gcc_assert (niter
->cmp
== GT_EXPR
);
464 if (guard_code
== GE_EXPR
|| guard_code
== LT_EXPR
)
471 tree type2
= TREE_TYPE (newbound
);
472 if (POINTER_TYPE_P (type2
))
474 newbound
= gimple_build (stmts
,
475 POINTER_TYPE_P (TREE_TYPE (newbound
))
476 ? POINTER_PLUS_EXPR
: PLUS_EXPR
,
477 TREE_TYPE (newbound
),
479 build_int_cst (type2
, addbound
));
482 tree newend
= gimple_build (stmts
, minmax
, TREE_TYPE (border
),
487 /* Checks if LOOP contains an conditional block whose condition
488 depends on which side in the iteration space it is, and if so
489 splits the iteration space into two loops. Returns true if the
490 loop was split. NITER must contain the iteration descriptor for the
491 single exit of LOOP. */
494 split_loop (class loop
*loop1
)
496 class tree_niter_desc niter
;
499 bool changed
= false;
501 tree border
= NULL_TREE
;
504 if (!single_exit (loop1
)
505 /* ??? We could handle non-empty latches when we split the latch edge
506 (not the exit edge), and put the new exit condition in the new block.
507 OTOH this executes some code unconditionally that might have been
508 skipped by the original exit before. */
509 || !empty_block_p (loop1
->latch
)
510 || !easy_exit_values (loop1
)
511 || !number_of_iterations_exit (loop1
, single_exit (loop1
), &niter
,
513 || niter
.cmp
== ERROR_MARK
514 /* We can't yet handle loops controlled by a != predicate. */
515 || niter
.cmp
== NE_EXPR
)
518 bbs
= get_loop_body (loop1
);
520 if (!can_copy_bbs_p (bbs
, loop1
->num_nodes
))
526 /* Find a splitting opportunity. */
527 for (i
= 0; i
< loop1
->num_nodes
; i
++)
528 if ((guard_iv
= split_at_bb_p (loop1
, bbs
[i
], &border
, &iv
)))
530 /* Handling opposite steps is not implemented yet. Neither
531 is handling different step sizes. */
532 if ((tree_int_cst_sign_bit (iv
.step
)
533 != tree_int_cst_sign_bit (niter
.control
.step
))
534 || !tree_int_cst_equal (iv
.step
, niter
.control
.step
))
537 /* Find a loop PHI node that defines guard_iv directly,
538 or create one doing that. */
539 gphi
*phi
= find_or_create_guard_phi (loop1
, guard_iv
, &iv
);
542 gcond
*guard_stmt
= as_a
<gcond
*> (last_stmt (bbs
[i
]));
543 tree guard_init
= PHI_ARG_DEF_FROM_EDGE (phi
,
544 loop_preheader_edge (loop1
));
545 enum tree_code guard_code
= gimple_cond_code (guard_stmt
);
547 /* Loop splitting is implemented by versioning the loop, placing
548 the new loop after the old loop, make the first loop iterate
549 as long as the conditional stays true (or false) and let the
550 second (new) loop handle the rest of the iterations.
552 First we need to determine if the condition will start being true
553 or false in the first loop. */
559 initial_true
= !tree_int_cst_sign_bit (iv
.step
);
563 initial_true
= tree_int_cst_sign_bit (iv
.step
);
569 /* Build a condition that will skip the first loop when the
570 guard condition won't ever be true (or false). */
572 border
= force_gimple_operand (border
, &stmts2
, true, NULL_TREE
);
574 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1
),
576 tree cond
= build2 (guard_code
, boolean_type_node
, guard_init
, border
);
578 cond
= fold_build1 (TRUTH_NOT_EXPR
, boolean_type_node
, cond
);
580 /* Now version the loop, placing loop2 after loop1 connecting
581 them, and fix up SSA form for that. */
582 initialize_original_copy_tables ();
585 class loop
*loop2
= loop_version (loop1
, cond
, &cond_bb
,
586 profile_probability::always (),
587 profile_probability::always (),
588 profile_probability::always (),
589 profile_probability::always (),
592 update_ssa (TODO_update_ssa
);
594 edge new_e
= connect_loops (loop1
, loop2
);
595 connect_loop_phis (loop1
, loop2
, new_e
);
597 /* The iterations of the second loop is now already
598 exactly those that the first loop didn't do, but the
599 iteration space of the first loop is still the original one.
600 Compute the new bound for the guarding IV and patch the
601 loop exit to use it instead of original IV and bound. */
602 gimple_seq stmts
= NULL
;
603 tree newend
= compute_new_first_bound (&stmts
, &niter
, border
,
604 guard_code
, guard_init
);
606 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1
),
608 tree guard_next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop1
));
609 patch_loop_exit (loop1
, guard_stmt
, guard_next
, newend
, initial_true
);
611 /* Finally patch out the two copies of the condition to be always
612 true/false (or opposite). */
613 gcond
*force_true
= as_a
<gcond
*> (last_stmt (bbs
[i
]));
614 gcond
*force_false
= as_a
<gcond
*> (last_stmt (get_bb_copy (bbs
[i
])));
616 std::swap (force_true
, force_false
);
617 gimple_cond_make_true (force_true
);
618 gimple_cond_make_false (force_false
);
619 update_stmt (force_true
);
620 update_stmt (force_false
);
622 free_original_copy_tables ();
624 /* We destroyed LCSSA form above. Eventually we might be able
625 to fix it on the fly, for now simply punt and use the helper. */
626 rewrite_into_loop_closed_ssa_1 (NULL
, 0, SSA_OP_USE
, loop1
);
629 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
630 fprintf (dump_file
, ";; Loop split.\n");
632 /* Only deal with the first opportunity. */
640 /* Another transformation of loops like:
642 for (i = INIT (); CHECK (i); i = NEXT ())
644 if (expr (a_1, a_2, ..., a_n)) // expr is pure
645 a_j = ...; // change at least one a_j
647 S; // not change any a_j
652 for (i = INIT (); CHECK (i); i = NEXT ())
654 if (expr (a_1, a_2, ..., a_n))
664 for (; CHECK (i); i = NEXT ())
671 /* Data structure to hold temporary information during loop split upon
672 semi-invariant conditional statement. */
675 /* Array of all basic blocks in a loop, returned by get_loop_body(). */
678 /* All memory store/clobber statements in a loop. */
679 auto_vec
<gimple
*> memory_stores
;
681 /* Whether above memory stores vector has been filled. */
684 /* Control dependencies of basic blocks in a loop. */
685 auto_vec
<hash_set
<basic_block
> *> control_deps
;
687 split_info () : bbs (NULL
), need_init (true) { }
694 for (unsigned i
= 0; i
< control_deps
.length (); i
++)
695 delete control_deps
[i
];
699 /* Find all statements with memory-write effect in LOOP, including memory
700 store and non-pure function call, and keep those in a vector. This work
701 is only done one time, for the vector should be constant during analysis
702 stage of semi-invariant condition. */
705 find_vdef_in_loop (struct loop
*loop
)
707 split_info
*info
= (split_info
*) loop
->aux
;
708 gphi
*vphi
= get_virtual_phi (loop
->header
);
710 /* Indicate memory store vector has been filled. */
711 info
->need_init
= false;
713 /* If loop contains memory operation, there must be a virtual PHI node in
714 loop header basic block. */
718 /* All virtual SSA names inside the loop are connected to be a cyclic
719 graph via virtual PHI nodes. The virtual PHI node in loop header just
720 links the first and the last virtual SSA names, by using the last as
721 PHI operand to define the first. */
722 const edge latch
= loop_latch_edge (loop
);
723 const tree first
= gimple_phi_result (vphi
);
724 const tree last
= PHI_ARG_DEF_FROM_EDGE (vphi
, latch
);
726 /* The virtual SSA cyclic graph might consist of only one SSA name, who
727 is defined by itself.
729 .MEM_1 = PHI <.MEM_2(loop entry edge), .MEM_1(latch edge)>
731 This means the loop contains only memory loads, so we can skip it. */
735 auto_vec
<gimple
*> other_stores
;
736 auto_vec
<tree
> worklist
;
739 bitmap_set_bit (visited
, SSA_NAME_VERSION (first
));
740 bitmap_set_bit (visited
, SSA_NAME_VERSION (last
));
741 worklist
.safe_push (last
);
745 tree vuse
= worklist
.pop ();
746 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
748 /* We mark the first and last SSA names as visited at the beginning,
749 and reversely start the process from the last SSA name towards the
750 first, which ensures that this do-while will not touch SSA names
751 defined outside the loop. */
752 gcc_assert (gimple_bb (stmt
)
753 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)));
755 if (gimple_code (stmt
) == GIMPLE_PHI
)
757 gphi
*phi
= as_a
<gphi
*> (stmt
);
759 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); ++i
)
761 tree arg
= gimple_phi_arg_def (stmt
, i
);
763 if (bitmap_set_bit (visited
, SSA_NAME_VERSION (arg
)))
764 worklist
.safe_push (arg
);
769 tree prev
= gimple_vuse (stmt
);
771 /* Non-pure call statement is conservatively assumed to impact all
772 memory locations. So place call statements ahead of other memory
773 stores in the vector with an idea of using them as shortcut
774 terminators to memory alias analysis. */
775 if (gimple_code (stmt
) == GIMPLE_CALL
)
776 info
->memory_stores
.safe_push (stmt
);
778 other_stores
.safe_push (stmt
);
780 if (bitmap_set_bit (visited
, SSA_NAME_VERSION (prev
)))
781 worklist
.safe_push (prev
);
783 } while (!worklist
.is_empty ());
785 info
->memory_stores
.safe_splice (other_stores
);
788 /* Two basic blocks have equivalent control dependency if one dominates to
789 the other, and it is post-dominated by the latter. Given a basic block
790 BB in LOOP, find farest equivalent dominating basic block. For BB, there
791 is a constraint that BB does not post-dominate loop header of LOOP, this
792 means BB is control-dependent on at least one basic block in LOOP. */
795 get_control_equiv_head_block (struct loop
*loop
, basic_block bb
)
799 basic_block dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
801 gcc_checking_assert (dom_bb
&& flow_bb_inside_loop_p (loop
, dom_bb
));
803 if (!dominated_by_p (CDI_POST_DOMINATORS
, dom_bb
, bb
))
811 /* Given a BB in LOOP, find out all basic blocks in LOOP that BB is control-
814 static hash_set
<basic_block
> *
815 find_control_dep_blocks (struct loop
*loop
, basic_block bb
)
817 /* BB has same control dependency as loop header, then it is not control-
818 dependent on any basic block in LOOP. */
819 if (dominated_by_p (CDI_POST_DOMINATORS
, loop
->header
, bb
))
822 basic_block equiv_head
= get_control_equiv_head_block (loop
, bb
);
826 /* There is a basic block containing control dependency equivalent
827 to BB. No need to recompute that, and also set this information
828 to other equivalent basic blocks. */
829 for (; bb
!= equiv_head
;
830 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
831 bb
->aux
= equiv_head
->aux
;
832 return (hash_set
<basic_block
> *) equiv_head
->aux
;
835 /* A basic block X is control-dependent on another Y iff there exists
836 a path from X to Y, in which every basic block other than X and Y
837 is post-dominated by Y, but X is not post-dominated by Y.
839 According to this rule, traverse basic blocks in the loop backwards
840 starting from BB, if a basic block is post-dominated by BB, extend
841 current post-dominating path to this block, otherwise it is another
842 one that BB is control-dependent on. */
844 auto_vec
<basic_block
> pdom_worklist
;
845 hash_set
<basic_block
> pdom_visited
;
846 hash_set
<basic_block
> *dep_bbs
= new hash_set
<basic_block
>;
848 pdom_worklist
.safe_push (equiv_head
);
852 basic_block pdom_bb
= pdom_worklist
.pop ();
856 if (pdom_visited
.add (pdom_bb
))
859 FOR_EACH_EDGE (e
, ei
, pdom_bb
->preds
)
861 basic_block pred_bb
= e
->src
;
863 if (!dominated_by_p (CDI_POST_DOMINATORS
, pred_bb
, bb
))
865 dep_bbs
->add (pred_bb
);
869 pred_bb
= get_control_equiv_head_block (loop
, pred_bb
);
871 if (pdom_visited
.contains (pred_bb
))
876 pdom_worklist
.safe_push (pred_bb
);
880 /* If control dependency of basic block is available, fast extend
881 post-dominating path using the information instead of advancing
882 forward step-by-step. */
883 hash_set
<basic_block
> *pred_dep_bbs
884 = (hash_set
<basic_block
> *) pred_bb
->aux
;
886 for (hash_set
<basic_block
>::iterator iter
= pred_dep_bbs
->begin ();
887 iter
!= pred_dep_bbs
->end (); ++iter
)
889 basic_block pred_dep_bb
= *iter
;
891 /* Basic blocks can either be in control dependency of BB, or
892 must be post-dominated by BB, if so, extend the path from
893 these basic blocks. */
894 if (!dominated_by_p (CDI_POST_DOMINATORS
, pred_dep_bb
, bb
))
895 dep_bbs
->add (pred_dep_bb
);
896 else if (!pdom_visited
.contains (pred_dep_bb
))
897 pdom_worklist
.safe_push (pred_dep_bb
);
900 } while (!pdom_worklist
.is_empty ());
902 /* Record computed control dependencies in loop so that we can reach them
903 when reclaiming resources. */
904 ((split_info
*) loop
->aux
)->control_deps
.safe_push (dep_bbs
);
906 /* Associate control dependence with related equivalent basic blocks. */
907 for (equiv_head
->aux
= dep_bbs
; bb
!= equiv_head
;
908 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
914 /* Forward declaration */
917 stmt_semi_invariant_p_1 (struct loop
*loop
, gimple
*stmt
,
918 const_basic_block skip_head
,
919 hash_map
<gimple
*, bool> &stmt_stat
);
921 /* Given STMT, memory load or pure call statement, check whether it is impacted
922 by some memory store in LOOP, excluding trace starting from SKIP_HEAD (the
923 trace is composed of SKIP_HEAD and those basic block dominated by it, always
924 corresponds to one branch of a conditional statement). If SKIP_HEAD is
925 NULL, all basic blocks of LOOP are checked. */
928 vuse_semi_invariant_p (struct loop
*loop
, gimple
*stmt
,
929 const_basic_block skip_head
)
931 split_info
*info
= (split_info
*) loop
->aux
;
932 tree rhs
= NULL_TREE
;
937 /* Collect memory store/clobber statements if haven't done that. */
939 find_vdef_in_loop (loop
);
941 if (is_gimple_assign (stmt
))
942 rhs
= gimple_assign_rhs1 (stmt
);
944 ao_ref_init (&ref
, rhs
);
946 FOR_EACH_VEC_ELT (info
->memory_stores
, i
, store
)
948 /* Skip basic blocks dominated by SKIP_HEAD, if non-NULL. */
950 && dominated_by_p (CDI_DOMINATORS
, gimple_bb (store
), skip_head
))
953 if (!ref
.ref
|| stmt_may_clobber_ref_p_1 (store
, &ref
))
960 /* Suppose one condition branch, led by SKIP_HEAD, is not executed since
961 certain iteration of LOOP, check whether an SSA name (NAME) remains
962 unchanged in next iteration. We call this characteristic semi-
963 invariantness. SKIP_HEAD might be NULL, if so, nothing excluded, all basic
964 blocks and control flows in the loop will be considered. Semi-invariant
965 state of checked statement is cached in hash map STMT_STAT to avoid
966 redundant computation in possible following re-check. */
969 ssa_semi_invariant_p (struct loop
*loop
, tree name
,
970 const_basic_block skip_head
,
971 hash_map
<gimple
*, bool> &stmt_stat
)
973 gimple
*def
= SSA_NAME_DEF_STMT (name
);
974 const_basic_block def_bb
= gimple_bb (def
);
976 /* An SSA name defined outside loop is definitely semi-invariant. */
977 if (!def_bb
|| !flow_bb_inside_loop_p (loop
, def_bb
))
980 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name
))
983 return stmt_semi_invariant_p_1 (loop
, def
, skip_head
, stmt_stat
);
986 /* Check whether a loop iteration PHI node (LOOP_PHI) defines a value that is
987 semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL),
988 are excluded from LOOP. */
991 loop_iter_phi_semi_invariant_p (struct loop
*loop
, gphi
*loop_phi
,
992 const_basic_block skip_head
)
994 const_edge latch
= loop_latch_edge (loop
);
995 tree name
= gimple_phi_result (loop_phi
);
996 tree from
= PHI_ARG_DEF_FROM_EDGE (loop_phi
, latch
);
998 gcc_checking_assert (from
);
1000 /* Loop iteration PHI node locates in loop header, and it has two source
1001 operands, one is an initial value coming from outside the loop, the other
1002 is a value through latch of the loop, which is derived in last iteration,
1003 we call the latter latch value. From the PHI node to definition of latch
1004 value, if excluding branch trace starting from SKIP_HEAD, except copy-
1005 assignment or likewise, there is no other kind of value redefinition, SSA
1006 name defined by the PHI node is semi-invariant.
1012 x_1 = PHI <x_0, x_3> |
1015 .------- if (cond) -------. |
1021 '---- T ---->.<---- F ----' |
1024 x_3 = PHI <x_1, x_2> |
1026 '----------------------'
1028 Suppose in certain iteration, execution flow in above graph goes through
1029 true branch, which means that one source value to define x_3 in false
1030 branch (x_2) is skipped, x_3 only comes from x_1, and x_1 in next
1031 iterations is defined by x_3, we know that x_1 will never changed if COND
1032 always chooses true branch from then on. */
1034 while (from
!= name
)
1036 /* A new value comes from a CONSTANT. */
1037 if (TREE_CODE (from
) != SSA_NAME
)
1040 gimple
*stmt
= SSA_NAME_DEF_STMT (from
);
1041 const_basic_block bb
= gimple_bb (stmt
);
1043 /* A new value comes from outside the loop. */
1044 if (!bb
|| !flow_bb_inside_loop_p (loop
, bb
))
1049 if (gimple_code (stmt
) == GIMPLE_PHI
)
1051 gphi
*phi
= as_a
<gphi
*> (stmt
);
1053 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); ++i
)
1057 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1059 /* Don't consider redefinitions in excluded basic blocks. */
1060 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, skip_head
))
1064 tree arg
= gimple_phi_arg_def (phi
, i
);
1068 else if (!operand_equal_p (from
, arg
, 0))
1069 /* There are more than one source operands that provide
1070 different values to the SSA name, it is variant. */
1074 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
1076 /* For simple value copy, check its rhs instead. */
1077 if (gimple_assign_ssa_name_copy_p (stmt
))
1078 from
= gimple_assign_rhs1 (stmt
);
1081 /* Any other kind of definition is deemed to introduce a new value
1089 /* Check whether conditional predicates that BB is control-dependent on, are
1090 semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL),
1091 are excluded from LOOP. Semi-invariant state of checked statement is cached
1092 in hash map STMT_STAT. */
1095 control_dep_semi_invariant_p (struct loop
*loop
, basic_block bb
,
1096 const_basic_block skip_head
,
1097 hash_map
<gimple
*, bool> &stmt_stat
)
1099 hash_set
<basic_block
> *dep_bbs
= find_control_dep_blocks (loop
, bb
);
1104 for (hash_set
<basic_block
>::iterator iter
= dep_bbs
->begin ();
1105 iter
!= dep_bbs
->end (); ++iter
)
1107 gimple
*last
= last_stmt (*iter
);
1112 /* Only check condition predicates. */
1113 if (gimple_code (last
) != GIMPLE_COND
1114 && gimple_code (last
) != GIMPLE_SWITCH
)
1117 if (!stmt_semi_invariant_p_1 (loop
, last
, skip_head
, stmt_stat
))
1124 /* Check whether STMT is semi-invariant in LOOP, iff all its operands are
1125 semi-invariant, consequently, all its defined values are semi-invariant.
1126 Basic blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP.
1127 Semi-invariant state of checked statement is cached in hash map
1131 stmt_semi_invariant_p_1 (struct loop
*loop
, gimple
*stmt
,
1132 const_basic_block skip_head
,
1133 hash_map
<gimple
*, bool> &stmt_stat
)
1136 bool &invar
= stmt_stat
.get_or_insert (stmt
, &existed
);
1141 /* A statement might depend on itself, which is treated as variant. So set
1142 state of statement under check to be variant to ensure that. */
1145 if (gimple_code (stmt
) == GIMPLE_PHI
)
1147 gphi
*phi
= as_a
<gphi
*> (stmt
);
1149 if (gimple_bb (stmt
) == loop
->header
)
1151 /* If the entry value is subject to abnormal coalescing
1152 avoid the transform since we're going to duplicate the
1153 loop header and thus likely introduce overlapping life-ranges
1154 between the PHI def and the entry on the path when the
1155 first loop is skipped. */
1157 = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1158 if (TREE_CODE (entry_def
) == SSA_NAME
1159 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (entry_def
))
1161 invar
= loop_iter_phi_semi_invariant_p (loop
, phi
, skip_head
);
1165 /* For a loop PHI node that does not locate in loop header, it is semi-
1166 invariant only if two conditions are met. The first is its source
1167 values are derived from CONSTANT (including loop-invariant value), or
1168 from SSA name defined by semi-invariant loop iteration PHI node. The
1169 second is its source incoming edges are control-dependent on semi-
1170 invariant conditional predicates. */
1171 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); ++i
)
1173 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1174 tree arg
= gimple_phi_arg_def (phi
, i
);
1176 if (TREE_CODE (arg
) == SSA_NAME
)
1178 if (!ssa_semi_invariant_p (loop
, arg
, skip_head
, stmt_stat
))
1181 /* If source value is defined in location from where the source
1182 edge comes in, no need to check control dependency again
1183 since this has been done in above SSA name check stage. */
1184 if (e
->src
== gimple_bb (SSA_NAME_DEF_STMT (arg
)))
1188 if (!control_dep_semi_invariant_p (loop
, e
->src
, skip_head
,
1198 /* Volatile memory load or return of normal (non-const/non-pure) call
1199 should not be treated as constant in each iteration of loop. */
1200 if (gimple_has_side_effects (stmt
))
1203 /* Check if any memory store may kill memory load at this place. */
1204 if (gimple_vuse (stmt
) && !vuse_semi_invariant_p (loop
, stmt
, skip_head
))
1207 /* Although operand of a statement might be SSA name, CONSTANT or
1208 VARDECL, here we only need to check SSA name operands. This is
1209 because check on VARDECL operands, which involve memory loads,
1210 must have been done prior to invocation of this function in
1211 vuse_semi_invariant_p. */
1212 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
1213 if (!ssa_semi_invariant_p (loop
, use
, skip_head
, stmt_stat
))
1217 if (!control_dep_semi_invariant_p (loop
, gimple_bb (stmt
), skip_head
,
1221 /* Here we SHOULD NOT use invar = true, since hash map might be changed due
1222 to new insertion, and thus invar may point to invalid memory. */
1223 stmt_stat
.put (stmt
, true);
1227 /* A helper function to check whether STMT is semi-invariant in LOOP. Basic
1228 blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP. */
1231 stmt_semi_invariant_p (struct loop
*loop
, gimple
*stmt
,
1232 const_basic_block skip_head
)
1234 hash_map
<gimple
*, bool> stmt_stat
;
1235 return stmt_semi_invariant_p_1 (loop
, stmt
, skip_head
, stmt_stat
);
1238 /* Determine when conditional statement never transfers execution to one of its
1239 branch, whether we can remove the branch's leading basic block (BRANCH_BB)
1240 and those basic blocks dominated by BRANCH_BB. */
1243 branch_removable_p (basic_block branch_bb
)
1248 if (single_pred_p (branch_bb
))
1251 FOR_EACH_EDGE (e
, ei
, branch_bb
->preds
)
1253 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, branch_bb
))
1256 if (dominated_by_p (CDI_DOMINATORS
, branch_bb
, e
->src
))
1259 /* The branch can be reached from opposite branch, or from some
1260 statement not dominated by the conditional statement. */
1267 /* Find out which branch of a conditional statement (COND) is invariant in the
1268 execution context of LOOP. That is: once the branch is selected in certain
1269 iteration of the loop, any operand that contributes to computation of the
1270 conditional statement remains unchanged in all following iterations. */
1273 get_cond_invariant_branch (struct loop
*loop
, gcond
*cond
)
1275 basic_block cond_bb
= gimple_bb (cond
);
1276 basic_block targ_bb
[2];
1278 unsigned invar_checks
= 0;
1280 for (unsigned i
= 0; i
< 2; i
++)
1282 targ_bb
[i
] = EDGE_SUCC (cond_bb
, i
)->dest
;
1284 /* One branch directs to loop exit, no need to perform loop split upon
1285 this conditional statement. Firstly, it is trivial if the exit branch
1286 is semi-invariant, for the statement is just to break loop. Secondly,
1287 if the opposite branch is semi-invariant, it means that the statement
1288 is real loop-invariant, which is covered by loop unswitch. */
1289 if (!flow_bb_inside_loop_p (loop
, targ_bb
[i
]))
1293 for (unsigned i
= 0; i
< 2; i
++)
1297 if (!branch_removable_p (targ_bb
[i
]))
1300 /* Given a semi-invariant branch, if its opposite branch dominates
1301 loop latch, it and its following trace will only be executed in
1302 final iteration of loop, namely it is not part of repeated body
1303 of the loop. Similar to the above case that the branch is loop
1304 exit, no need to split loop. */
1305 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, targ_bb
[i
]))
1308 invar
[!i
] = stmt_semi_invariant_p (loop
, cond
, targ_bb
[i
]);
1312 /* With both branches being invariant (handled by loop unswitch) or
1313 variant is not what we want. */
1314 if (invar
[0] ^ !invar
[1])
1317 /* Found a real loop-invariant condition, do nothing. */
1318 if (invar_checks
< 2 && stmt_semi_invariant_p (loop
, cond
, NULL
))
1321 return EDGE_SUCC (cond_bb
, invar
[0] ? 0 : 1);
1324 /* Calculate increased code size measured by estimated insn number if applying
1325 loop split upon certain branch (BRANCH_EDGE) of a conditional statement. */
1328 compute_added_num_insns (struct loop
*loop
, const_edge branch_edge
)
1330 basic_block cond_bb
= branch_edge
->src
;
1331 unsigned branch
= EDGE_SUCC (cond_bb
, 1) == branch_edge
;
1332 basic_block opposite_bb
= EDGE_SUCC (cond_bb
, !branch
)->dest
;
1333 basic_block
*bbs
= ((split_info
*) loop
->aux
)->bbs
;
1336 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
1338 /* Do no count basic blocks only in opposite branch. */
1339 if (dominated_by_p (CDI_DOMINATORS
, bbs
[i
], opposite_bb
))
1342 num
+= estimate_num_insns_seq (bb_seq (bbs
[i
]), &eni_size_weights
);
1345 /* It is unnecessary to evaluate expression of the conditional statement
1346 in new loop that contains only invariant branch. This expression should
1347 be constant value (either true or false). Exclude code size of insns
1348 that contribute to computation of the expression. */
1350 auto_vec
<gimple
*> worklist
;
1351 hash_set
<gimple
*> removed
;
1352 gimple
*stmt
= last_stmt (cond_bb
);
1354 worklist
.safe_push (stmt
);
1356 num
-= estimate_num_insns (stmt
, &eni_size_weights
);
1360 ssa_op_iter opnd_iter
;
1361 use_operand_p opnd_p
;
1363 stmt
= worklist
.pop ();
1364 FOR_EACH_PHI_OR_STMT_USE (opnd_p
, stmt
, opnd_iter
, SSA_OP_USE
)
1366 tree opnd
= USE_FROM_PTR (opnd_p
);
1368 if (TREE_CODE (opnd
) != SSA_NAME
|| SSA_NAME_IS_DEFAULT_DEF (opnd
))
1371 gimple
*opnd_stmt
= SSA_NAME_DEF_STMT (opnd
);
1372 use_operand_p use_p
;
1373 imm_use_iterator use_iter
;
1375 if (removed
.contains (opnd_stmt
)
1376 || !flow_bb_inside_loop_p (loop
, gimple_bb (opnd_stmt
)))
1379 FOR_EACH_IMM_USE_FAST (use_p
, use_iter
, opnd
)
1381 gimple
*use_stmt
= USE_STMT (use_p
);
1383 if (!is_gimple_debug (use_stmt
) && !removed
.contains (use_stmt
))
1392 worklist
.safe_push (opnd_stmt
);
1393 removed
.add (opnd_stmt
);
1394 num
-= estimate_num_insns (opnd_stmt
, &eni_size_weights
);
1397 } while (!worklist
.is_empty ());
1399 gcc_assert (num
>= 0);
1403 /* Find out loop-invariant branch of a conditional statement (COND) if it has,
1404 and check whether it is eligible and profitable to perform loop split upon
1405 this branch in LOOP. */
1408 get_cond_branch_to_split_loop (struct loop
*loop
, gcond
*cond
)
1410 edge invar_branch
= get_cond_invariant_branch (loop
, cond
);
1414 /* When accurate profile information is available, and execution
1415 frequency of the branch is too low, just let it go. */
1416 profile_probability prob
= invar_branch
->probability
;
1417 if (prob
.reliable_p ())
1419 int thres
= param_min_loop_cond_split_prob
;
1421 if (prob
< profile_probability::always ().apply_scale (thres
, 100))
1425 /* Add a threshold for increased code size to disable loop split. */
1426 if (compute_added_num_insns (loop
, invar_branch
) > param_max_peeled_insns
)
1429 return invar_branch
;
1432 /* Given a loop (LOOP1) with a loop-invariant branch (INVAR_BRANCH) of some
1433 conditional statement, perform loop split transformation illustrated
1434 as the following graph.
1436 .-------T------ if (true) ------F------.
1437 | .---------------. |
1440 pre-header | pre-header
1441 | .------------. | | .------------.
1446 .--- if (cond) ---. | | .--- if (true) ---. |
1448 invariant | | | invariant | |
1450 '---T--->.<---F---' | | '---T--->.<---F---' |
1455 .-------* * [ if (cond) ] .-------* * |
1459 | '------------' | '------------'
1460 '------------------------. .-----------'
1465 In the graph, loop1 represents the part derived from original one, and
1466 loop2 is duplicated using loop_version (), which corresponds to the part
1467 of original one being splitted out. In original latch edge of loop1, we
1468 insert a new conditional statement duplicated from the semi-invariant cond,
1469 and one of its branch goes back to loop1 header as a latch edge, and the
1470 other branch goes to loop2 pre-header as an entry edge. And also in loop2,
1471 we abandon the variant branch of the conditional statement by setting a
1472 constant bool condition, based on which branch is semi-invariant. */
1475 do_split_loop_on_cond (struct loop
*loop1
, edge invar_branch
)
1477 basic_block cond_bb
= invar_branch
->src
;
1478 bool true_invar
= !!(invar_branch
->flags
& EDGE_TRUE_VALUE
);
1479 gcond
*cond
= as_a
<gcond
*> (last_stmt (cond_bb
));
1481 gcc_assert (cond_bb
->loop_father
== loop1
);
1483 if (dump_enabled_p ())
1484 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, cond
,
1485 "loop split on semi-invariant condition at %s branch\n",
1486 true_invar
? "true" : "false");
1488 initialize_original_copy_tables ();
1490 struct loop
*loop2
= loop_version (loop1
, boolean_true_node
, NULL
,
1491 profile_probability::always (),
1492 profile_probability::never (),
1493 profile_probability::always (),
1494 profile_probability::always (),
1498 free_original_copy_tables ();
1502 basic_block cond_bb_copy
= get_bb_copy (cond_bb
);
1503 gcond
*cond_copy
= as_a
<gcond
*> (last_stmt (cond_bb_copy
));
1505 /* Replace the condition in loop2 with a bool constant to let PassManager
1506 remove the variant branch after current pass completes. */
1508 gimple_cond_make_true (cond_copy
);
1510 gimple_cond_make_false (cond_copy
);
1512 update_stmt (cond_copy
);
1514 /* Insert a new conditional statement on latch edge of loop1, its condition
1515 is duplicated from the semi-invariant. This statement acts as a switch
1516 to transfer execution from loop1 to loop2, when loop1 enters into
1518 basic_block latch_bb
= split_edge (loop_latch_edge (loop1
));
1519 basic_block break_bb
= split_edge (single_pred_edge (latch_bb
));
1520 gimple
*break_cond
= gimple_build_cond (gimple_cond_code(cond
),
1521 gimple_cond_lhs (cond
),
1522 gimple_cond_rhs (cond
),
1523 NULL_TREE
, NULL_TREE
);
1525 gimple_stmt_iterator gsi
= gsi_last_bb (break_bb
);
1526 gsi_insert_after (&gsi
, break_cond
, GSI_NEW_STMT
);
1528 edge to_loop1
= single_succ_edge (break_bb
);
1529 edge to_loop2
= make_edge (break_bb
, loop_preheader_edge (loop2
)->src
, 0);
1531 to_loop1
->flags
&= ~EDGE_FALLTHRU
;
1532 to_loop1
->flags
|= true_invar
? EDGE_FALSE_VALUE
: EDGE_TRUE_VALUE
;
1533 to_loop2
->flags
|= true_invar
? EDGE_TRUE_VALUE
: EDGE_FALSE_VALUE
;
1535 update_ssa (TODO_update_ssa
);
1537 /* Due to introduction of a control flow edge from loop1 latch to loop2
1538 pre-header, we should update PHIs in loop2 to reflect this connection
1539 between loop1 and loop2. */
1540 connect_loop_phis (loop1
, loop2
, to_loop2
);
1542 free_original_copy_tables ();
1544 rewrite_into_loop_closed_ssa_1 (NULL
, 0, SSA_OP_USE
, loop1
);
1549 /* Traverse all conditional statements in LOOP, to find out a good candidate
1550 upon which we can do loop split. */
1553 split_loop_on_cond (struct loop
*loop
)
1555 split_info
*info
= new split_info ();
1556 basic_block
*bbs
= info
->bbs
= get_loop_body (loop
);
1557 bool do_split
= false;
1559 /* Allocate an area to keep temporary info, and associate its address
1560 with loop aux field. */
1563 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
1566 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
1568 basic_block bb
= bbs
[i
];
1570 /* We only consider conditional statement, which be executed at most once
1571 in each iteration of the loop. So skip statements in inner loops. */
1572 if ((bb
->loop_father
!= loop
) || (bb
->flags
& BB_IRREDUCIBLE_LOOP
))
1575 /* Actually this check is not a must constraint. With it, we can ensure
1576 conditional statement will always be executed in each iteration. */
1577 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1580 gimple
*last
= last_stmt (bb
);
1582 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
1585 gcond
*cond
= as_a
<gcond
*> (last
);
1586 edge branch_edge
= get_cond_branch_to_split_loop (loop
, cond
);
1590 do_split_loop_on_cond (loop
, branch_edge
);
1602 /* Main entry point. Perform loop splitting on all suitable loops. */
1605 tree_ssa_split_loops (void)
1608 bool changed
= false;
1610 gcc_assert (scev_initialized_p ());
1612 calculate_dominance_info (CDI_POST_DOMINATORS
);
1614 FOR_EACH_LOOP (loop
, LI_INCLUDE_ROOT
)
1617 /* Go through all loops starting from innermost. */
1618 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1622 /* If any of our inner loops was split, don't split us,
1623 and mark our containing loop as having had splits as well. */
1624 loop_outer (loop
)->aux
= loop
;
1628 if (optimize_loop_for_size_p (loop
))
1631 if (split_loop (loop
) || split_loop_on_cond (loop
))
1633 /* Mark our containing loop as having had some split inner loops. */
1634 loop_outer (loop
)->aux
= loop
;
1639 FOR_EACH_LOOP (loop
, LI_INCLUDE_ROOT
)
1642 clear_aux_for_blocks ();
1644 free_dominance_info (CDI_POST_DOMINATORS
);
1647 return TODO_cleanup_cfg
;
1651 /* Loop splitting pass. */
1655 const pass_data pass_data_loop_split
=
1657 GIMPLE_PASS
, /* type */
1658 "lsplit", /* name */
1659 OPTGROUP_LOOP
, /* optinfo_flags */
1660 TV_LOOP_SPLIT
, /* tv_id */
1661 PROP_cfg
, /* properties_required */
1662 0, /* properties_provided */
1663 0, /* properties_destroyed */
1664 0, /* todo_flags_start */
1665 0, /* todo_flags_finish */
1668 class pass_loop_split
: public gimple_opt_pass
1671 pass_loop_split (gcc::context
*ctxt
)
1672 : gimple_opt_pass (pass_data_loop_split
, ctxt
)
1675 /* opt_pass methods: */
1676 virtual bool gate (function
*) { return flag_split_loops
!= 0; }
1677 virtual unsigned int execute (function
*);
1679 }; // class pass_loop_split
1682 pass_loop_split::execute (function
*fun
)
1684 if (number_of_loops (fun
) <= 1)
1687 return tree_ssa_split_loops ();
1693 make_pass_loop_split (gcc::context
*ctxt
)
1695 return new pass_loop_split (ctxt
);