2 Copyright (C) 2004-2024 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/>. */
21 #define INCLUDE_MEMORY
23 #include "coretypes.h"
27 #include "tree-pass.h"
29 #include "fold-const.h"
33 #include "tree-ssa-loop-niter.h"
34 #include "tree-ssa-loop.h"
35 #include "tree-into-ssa.h"
37 #include "tree-inline.h"
38 #include "gimple-iterator.h"
40 #include "tree-ssa-loop-manip.h"
41 #include "tree-vectorizer.h"
42 #include "tree-pretty-print.h"
43 #include "gimple-range.h"
47 /* This file implements the loop unswitching, i.e. transformation of loops like
60 where inv is the loop invariant, into
79 Inv is considered invariant iff the values it compares are both invariant;
80 tree-ssa-loop-im.cc ensures that all the suitable conditions are in this
83 /* Loop unswitching algorithm for innermost loops works in the following steps:
85 1) Number of instructions is estimated for each BB that belongs to a loop.
86 2) Unswitching candidates are found for gcond and gswitch statements
87 (note that an unswitching predicate for a gswitch actually corresponds
88 to a non-default edge so it can contain multiple cases).
89 3) The so called unswitch predicates are stored in a cache where the
90 gimple_uid of the last stmt in a basic-block is an index to the cache.
91 4) We consider one by one the unswitching candidates and calculate BBs that
92 will be reachable in the unswitch version.
93 5) A selected predicate is chosen and we simplify the CFG (dead edges) in
94 both versions of the loop. We utilize both Ranger for condition
95 simplification and also symbol equivalence. The folded if conditions
96 are replaced with true/false values, while for gswitch we mark the
97 corresponding edges with a pass-defined unreachable flag.
98 6) Every time we unswitch a loop, we save unswitch_predicate to a vector
99 together with information if true or false edge was taken. Doing that
100 we have a so called PREDICATE_PATH that is utilized for simplification
102 7) The process is repeated until we reach a growth threshold or all
103 unswitching opportunities are taken. */
105 /* A tuple that holds a GENERIC condition and value range for an unswitching
108 struct unswitch_predicate
110 /* CTOR for a switch edge predicate. */
111 unswitch_predicate (tree cond
, tree lhs_
, int edge_index_
, edge e
,
112 const int_range_max
& edge_range
)
113 : condition (cond
), lhs (lhs_
),
114 true_range (edge_range
), edge_index (edge_index_
), switch_p (true)
116 gcc_assert (!(e
->flags
& (EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
))
117 && irange::supports_p (TREE_TYPE (lhs
)));
118 false_range
= true_range
;
119 if (!false_range
.varying_p ()
120 && !false_range
.undefined_p ())
121 false_range
.invert ();
123 num
= predicates
->length ();
124 predicates
->safe_push (this);
127 /* CTOR for a GIMPLE condition statement. */
128 unswitch_predicate (gcond
*stmt
)
131 basic_block bb
= gimple_bb (stmt
);
132 if (EDGE_SUCC (bb
, 0)->flags
& EDGE_TRUE_VALUE
)
136 lhs
= gimple_cond_lhs (stmt
);
137 tree rhs
= gimple_cond_rhs (stmt
);
138 enum tree_code code
= gimple_cond_code (stmt
);
139 condition
= build2 (code
, boolean_type_node
, lhs
, rhs
);
140 count
= EDGE_SUCC (bb
, 0)->count ().max (EDGE_SUCC (bb
, 1)->count ());
141 if (irange::supports_p (TREE_TYPE (lhs
)))
143 auto range_op
= range_op_handler (code
);
144 int_range
<2> rhs_range (TREE_TYPE (rhs
));
145 if (CONSTANT_CLASS_P (rhs
))
147 wide_int w
= wi::to_wide (rhs
);
148 rhs_range
.set (TREE_TYPE (rhs
), w
, w
);
150 if (!range_op
.op1_range (true_range
, TREE_TYPE (lhs
),
151 range_true (), rhs_range
)
152 || !range_op
.op1_range (false_range
, TREE_TYPE (lhs
),
153 range_false (), rhs_range
))
155 true_range
.set_varying (TREE_TYPE (lhs
));
156 false_range
.set_varying (TREE_TYPE (lhs
));
159 num
= predicates
->length ();
160 predicates
->safe_push (this);
163 /* Copy ranges for purpose of usage in predicate path. */
166 copy_merged_ranges ()
168 merged_true_range
= true_range
;
169 merged_false_range
= false_range
;
172 /* GENERIC unswitching expression testing LHS against CONSTANT. */
175 /* LHS of the expression. */
178 /* Initial ranges (when the expression is true/false) for the expression. */
179 int_range_max true_range
= {}, false_range
= {};
181 /* Modified range that is part of a predicate path. */
182 int_range_max merged_true_range
= {}, merged_false_range
= {};
184 /* Index of the edge the predicate belongs to in the successor vector. */
187 /* The profile count of this predicate. */
190 /* Whether the predicate was created from a switch statement. */
193 /* The number of the predicate in the predicates vector below. */
196 /* Vector of all used predicates, used for assigning a unique id that
197 can be used for bitmap operations. */
198 static vec
<unswitch_predicate
*> *predicates
;
201 vec
<unswitch_predicate
*> *unswitch_predicate::predicates
;
203 /* Ranger instance used in the pass. */
204 static gimple_ranger
*ranger
= NULL
;
206 /* Cache storage for unswitch_predicate belonging to a basic block. */
207 static vec
<vec
<unswitch_predicate
*>> *bb_predicates
;
209 /* The type represents a predicate path leading to a basic block. */
210 typedef vec
<std::pair
<unswitch_predicate
*, bool>> predicate_vector
;
212 static class loop
*tree_unswitch_loop (class loop
*, edge
, tree
);
213 static bool tree_unswitch_single_loop (class loop
*, dump_user_location_t
,
214 predicate_vector
&predicate_path
,
215 unsigned loop_size
, unsigned &budget
,
216 int ignored_edge_flag
, bitmap
,
217 unswitch_predicate
* = NULL
,
220 find_unswitching_predicates_for_bb (basic_block bb
, class loop
*loop
,
221 class loop
*&outer_loop
,
222 vec
<unswitch_predicate
*> &candidates
,
223 unswitch_predicate
*&hottest
,
224 basic_block
&hottest_bb
);
225 static bool tree_unswitch_outer_loop (class loop
*);
226 static edge
find_loop_guard (class loop
*, vec
<gimple
*>&);
227 static bool empty_bb_without_guard_p (class loop
*, basic_block
,
229 static bool used_outside_loop_p (class loop
*, tree
, vec
<gimple
*>&);
230 static void hoist_guard (class loop
*, edge
);
231 static bool check_exit_phi (class loop
*);
232 static tree
get_vop_from_header (class loop
*);
233 static void clean_up_after_unswitching (int);
235 /* Return vector of predicates that belong to a basic block. */
237 static vec
<unswitch_predicate
*> &
238 get_predicates_for_bb (basic_block bb
)
240 gimple
*last
= last_nondebug_stmt (bb
);
241 return (*bb_predicates
)[last
== NULL
? 0 : gimple_uid (last
)];
244 /* Save predicates that belong to a basic block. */
247 set_predicates_for_bb (basic_block bb
, vec
<unswitch_predicate
*> predicates
)
249 gimple_set_uid (last_nondebug_stmt (bb
), bb_predicates
->length ());
250 bb_predicates
->safe_push (predicates
);
253 /* Initialize LOOP information reused during the unswitching pass.
254 Return total number of instructions in the loop. Adjusts LOOP to
255 the outermost loop all candidates are invariant in. */
258 init_loop_unswitch_info (class loop
*&loop
, unswitch_predicate
*&hottest
,
259 basic_block
&hottest_bb
)
261 unsigned total_insns
= 0;
263 basic_block
*bbs
= get_loop_body (loop
);
265 /* Unswitch only nests with no sibling loops. */
266 class loop
*outer_loop
= loop
;
267 unsigned max_depth
= param_max_unswitch_depth
;
268 while (loop_outer (outer_loop
)->num
!= 0
269 && !loop_outer (outer_loop
)->inner
->next
271 outer_loop
= loop_outer (outer_loop
);
274 /* Find all unswitching candidates in the innermost loop. */
275 for (unsigned i
= 0; i
!= loop
->num_nodes
; i
++)
277 /* Find a bb to unswitch on. */
278 vec
<unswitch_predicate
*> candidates
;
279 candidates
.create (1);
280 find_unswitching_predicates_for_bb (bbs
[i
], loop
, outer_loop
, candidates
,
281 hottest
, hottest_bb
);
282 if (!candidates
.is_empty ())
283 set_predicates_for_bb (bbs
[i
], candidates
);
286 candidates
.release ();
287 gimple
*last
= last_nondebug_stmt (bbs
[i
]);
289 gimple_set_uid (last
, 0);
293 if (outer_loop
!= loop
)
296 bbs
= get_loop_body (outer_loop
);
299 /* Calculate instruction count. */
300 for (unsigned i
= 0; i
< outer_loop
->num_nodes
; i
++)
303 for (gimple_stmt_iterator gsi
= gsi_start_bb (bbs
[i
]); !gsi_end_p (gsi
);
305 insns
+= estimate_num_insns (gsi_stmt (gsi
), &eni_size_weights
);
306 /* No predicates to unswitch on in the outer loops. */
307 if (!flow_bb_inside_loop_p (loop
, bbs
[i
]))
309 gimple
*last
= last_nondebug_stmt (bbs
[i
]);
311 gimple_set_uid (last
, 0);
314 bbs
[i
]->aux
= (void *)(uintptr_t)insns
;
315 total_insns
+= insns
;
324 /* Main entry point. Perform loop unswitching on all suitable loops. */
327 tree_ssa_unswitch_loops (function
*fun
)
329 bool changed_unswitch
= false;
330 bool changed_hoist
= false;
331 auto_edge_flag
ignored_edge_flag (fun
);
333 ranger
= enable_ranger (fun
);
335 /* Go through all loops starting from innermost, hoisting guards. */
336 for (auto loop
: loops_list (fun
, LI_FROM_INNERMOST
))
339 changed_hoist
|= tree_unswitch_outer_loop (loop
);
342 /* Go through innermost loops, unswitching on invariant predicates
344 for (auto loop
: loops_list (fun
, LI_ONLY_INNERMOST
))
346 /* Perform initial tests if unswitch is eligible. */
347 dump_user_location_t loc
= find_loop_location (loop
);
349 /* Do not unswitch in cold regions. */
350 if (optimize_loop_for_size_p (loop
))
352 if (dump_enabled_p ())
353 dump_printf_loc (MSG_NOTE
, loc
,
354 "Not unswitching cold loops\n");
358 /* If the loop is not expected to iterate, there is no need
360 HOST_WIDE_INT iterations
= estimated_loop_iterations_int (loop
);
362 iterations
= likely_max_loop_iterations_int (loop
);
363 if (iterations
>= 0 && iterations
<= 1)
365 if (dump_enabled_p ())
366 dump_printf_loc (MSG_NOTE
, loc
,
367 "Not unswitching, loop is not expected"
372 bb_predicates
= new vec
<vec
<unswitch_predicate
*>> ();
373 bb_predicates
->safe_push (vec
<unswitch_predicate
*> ());
374 unswitch_predicate::predicates
= new vec
<unswitch_predicate
*> ();
377 unswitch_predicate
*hottest
;
378 basic_block hottest_bb
;
379 unsigned int loop_size
= init_loop_unswitch_info (loop
, hottest
,
381 unsigned int budget
= loop_size
+ param_max_unswitch_insns
;
383 predicate_vector predicate_path
;
384 predicate_path
.create (8);
386 changed_unswitch
|= tree_unswitch_single_loop (loop
, loc
, predicate_path
,
388 ignored_edge_flag
, handled
,
389 hottest
, hottest_bb
);
390 predicate_path
.release ();
392 for (auto predlist
: bb_predicates
)
394 bb_predicates
->release ();
395 delete bb_predicates
;
396 bb_predicates
= NULL
;
398 for (auto pred
: unswitch_predicate::predicates
)
400 unswitch_predicate::predicates
->release ();
401 delete unswitch_predicate::predicates
;
402 unswitch_predicate::predicates
= NULL
;
405 disable_ranger (fun
);
406 clear_aux_for_blocks ();
408 if (changed_unswitch
)
409 clean_up_after_unswitching (ignored_edge_flag
);
411 if (changed_unswitch
|| changed_hoist
)
412 return TODO_cleanup_cfg
;
417 /* Return TRUE if an SSA_NAME maybe undefined and is therefore
418 unsuitable for unswitching. STMT is the statement we are
419 considering for unswitching and LOOP is the loop it appears in. */
422 is_maybe_undefined (const tree name
, gimple
*stmt
, class loop
*loop
)
424 /* The loop header is the only block we can trivially determine that
425 will always be executed. If the comparison is in the loop
426 header, we know it's OK to unswitch on it. */
427 if (gimple_bb (stmt
) == loop
->header
)
430 auto_bitmap visited_ssa
;
431 auto_vec
<tree
> worklist
;
432 worklist
.safe_push (name
);
433 bitmap_set_bit (visited_ssa
, SSA_NAME_VERSION (name
));
434 while (!worklist
.is_empty ())
436 tree t
= worklist
.pop ();
438 /* If it's obviously undefined, avoid further computations. */
439 if (ssa_undefined_value_p (t
, true))
442 if (ssa_defined_default_def_p (t
))
445 gimple
*def
= SSA_NAME_DEF_STMT (t
);
447 /* Check that all the PHI args are fully defined. */
448 if (gphi
*phi
= dyn_cast
<gphi
*> (def
))
450 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); ++i
)
452 tree t
= gimple_phi_arg_def (phi
, i
);
453 /* If an SSA has already been seen, it may be a loop,
454 but we can continue and ignore this use. Otherwise,
455 add the SSA_NAME to the queue and visit it later. */
456 if (TREE_CODE (t
) == SSA_NAME
457 && bitmap_set_bit (visited_ssa
, SSA_NAME_VERSION (t
)))
458 worklist
.safe_push (t
);
463 /* Uses in stmts always executed when the region header executes
465 if (dominated_by_p (CDI_DOMINATORS
, loop
->header
, gimple_bb (def
)))
468 /* Handle calls and memory loads conservatively. */
469 if (!is_gimple_assign (def
)
470 || (gimple_assign_single_p (def
)
471 && gimple_vuse (def
)))
474 /* Check that any SSA names used to define NAME are also fully
478 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
480 tree t
= USE_FROM_PTR (use_p
);
481 /* If an SSA has already been seen, it may be a loop,
482 but we can continue and ignore this use. Otherwise,
483 add the SSA_NAME to the queue and visit it later. */
484 if (bitmap_set_bit (visited_ssa
, SSA_NAME_VERSION (t
)))
485 worklist
.safe_push (t
);
491 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
492 basic blocks (for what it means see comments below).
493 All candidates all filled to the provided vector CANDIDATES.
494 OUTER_LOOP is updated to the innermost loop all found candidates are
498 find_unswitching_predicates_for_bb (basic_block bb
, class loop
*loop
,
499 class loop
*&outer_loop
,
500 vec
<unswitch_predicate
*> &candidates
,
501 unswitch_predicate
*&hottest
,
502 basic_block
&hottest_bb
)
509 /* BB must end in a simple conditional jump. */
510 last
= *gsi_last_bb (bb
);
514 if (gcond
*stmt
= safe_dyn_cast
<gcond
*> (last
))
516 /* To keep the things simple, we do not directly remove the conditions,
517 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite
518 loop where we would unswitch again on such a condition. */
519 if (gimple_cond_true_p (stmt
) || gimple_cond_false_p (stmt
))
522 /* At least the LHS needs to be symbolic. */
523 if (TREE_CODE (gimple_cond_lhs (stmt
)) != SSA_NAME
)
526 /* Condition must be invariant. */
527 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
529 def
= SSA_NAME_DEF_STMT (use
);
530 def_bb
= gimple_bb (def
);
532 && flow_bb_inside_loop_p (loop
, def_bb
))
534 /* Unswitching on undefined values would introduce undefined
535 behavior that the original program might never exercise. */
536 if (is_maybe_undefined (use
, stmt
, loop
))
539 /* Narrow OUTER_LOOP. */
540 if (outer_loop
!= loop
)
541 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
543 def
= SSA_NAME_DEF_STMT (use
);
544 def_bb
= gimple_bb (def
);
545 while (outer_loop
!= loop
546 && ((def_bb
&& flow_bb_inside_loop_p (outer_loop
, def_bb
))
547 || is_maybe_undefined (use
, stmt
, outer_loop
)))
548 outer_loop
= superloop_at_depth (loop
,
549 loop_depth (outer_loop
) + 1);
552 unswitch_predicate
*predicate
= new unswitch_predicate (stmt
);
553 candidates
.safe_push (predicate
);
554 /* If we unswitch on this predicate we isolate both paths, so
555 pick the highest count for updating of the hottest predicate
556 to unswitch on first. */
557 if (!hottest
|| predicate
->count
> hottest
->count
)
563 else if (gswitch
*stmt
= safe_dyn_cast
<gswitch
*> (last
))
565 unsigned nlabels
= gimple_switch_num_labels (stmt
);
566 tree idx
= gimple_switch_index (stmt
);
567 tree idx_type
= TREE_TYPE (idx
);
568 if (!gimple_range_ssa_p (idx
) || nlabels
< 1)
570 /* Index must be invariant. */
571 def
= SSA_NAME_DEF_STMT (idx
);
572 def_bb
= gimple_bb (def
);
574 && flow_bb_inside_loop_p (loop
, def_bb
))
576 /* Unswitching on undefined values would introduce undefined
577 behavior that the original program might never exercise. */
578 if (is_maybe_undefined (idx
, stmt
, loop
))
580 /* Narrow OUTER_LOOP. */
581 while (outer_loop
!= loop
582 && ((def_bb
&& flow_bb_inside_loop_p (outer_loop
, def_bb
))
583 || is_maybe_undefined (idx
, stmt
, outer_loop
)))
584 outer_loop
= superloop_at_depth (loop
,
585 loop_depth (outer_loop
) + 1);
587 /* Build compound expression for all outgoing edges of the switch. */
588 auto_vec
<tree
, 16> preds
;
589 auto_vec
<int_range_max
> edge_range
;
590 preds
.safe_grow_cleared (EDGE_COUNT (gimple_bb (stmt
)->succs
), true);
591 edge_range
.safe_grow_cleared (EDGE_COUNT (gimple_bb (stmt
)->succs
), true);
594 unsigned edge_index
= 0;
595 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
596 e
->aux
= (void *)(uintptr_t)edge_index
++;
597 for (unsigned i
= 1; i
< gimple_switch_num_labels (stmt
); ++i
)
599 tree lab
= gimple_switch_label (stmt
, i
);
601 int_range
<2> lab_range
;
602 tree low
= fold_convert (idx_type
, CASE_LOW (lab
));
603 if (CASE_HIGH (lab
) != NULL_TREE
)
605 tree high
= fold_convert (idx_type
, CASE_HIGH (lab
));
606 tree cmp1
= fold_build2 (GE_EXPR
, boolean_type_node
, idx
, low
);
607 tree cmp2
= fold_build2 (LE_EXPR
, boolean_type_node
, idx
, high
);
608 cmp
= fold_build2 (BIT_AND_EXPR
, boolean_type_node
, cmp1
, cmp2
);
609 lab_range
.set (idx_type
, wi::to_wide (low
), wi::to_wide (high
));
613 cmp
= fold_build2 (EQ_EXPR
, boolean_type_node
, idx
, low
);
614 wide_int w
= wi::to_wide (low
);
615 lab_range
.set (idx_type
, w
, w
);
618 /* Combine the expression with the existing one. */
619 basic_block dest
= label_to_block (cfun
, CASE_LABEL (lab
));
620 e
= find_edge (gimple_bb (stmt
), dest
);
621 tree
&expr
= preds
[(uintptr_t)e
->aux
];
622 if (expr
== NULL_TREE
)
625 expr
= fold_build2 (BIT_IOR_EXPR
, boolean_type_node
, expr
, cmp
);
626 edge_range
[(uintptr_t)e
->aux
].union_ (lab_range
);
629 /* Now register the predicates. */
630 for (edge_index
= 0; edge_index
< preds
.length (); ++edge_index
)
632 edge e
= EDGE_SUCC (gimple_bb (stmt
), edge_index
);
634 if (preds
[edge_index
] != NULL_TREE
)
636 unswitch_predicate
*predicate
637 = new unswitch_predicate (preds
[edge_index
], idx
,
639 edge_range
[edge_index
]);
640 candidates
.safe_push (predicate
);
641 if (!hottest
|| predicate
->count
> hottest
->count
)
651 /* Merge ranges for the last item of PREDICATE_PATH with a predicate
652 that shared the same LHS. */
655 merge_last (predicate_vector
&predicate_path
)
657 unswitch_predicate
*last_predicate
= predicate_path
.last ().first
;
659 for (int i
= predicate_path
.length () - 2; i
>= 0; i
--)
661 unswitch_predicate
*predicate
= predicate_path
[i
].first
;
662 bool true_edge
= predicate_path
[i
].second
;
664 if (operand_equal_p (predicate
->lhs
, last_predicate
->lhs
, 0))
666 irange
&other
= (true_edge
? predicate
->merged_true_range
667 : predicate
->merged_false_range
);
668 last_predicate
->merged_true_range
.intersect (other
);
669 last_predicate
->merged_false_range
.intersect (other
);
675 /* Add PREDICATE to PREDICATE_PATH on TRUE_EDGE. */
678 add_predicate_to_path (predicate_vector
&predicate_path
,
679 unswitch_predicate
*predicate
, bool true_edge
)
681 predicate
->copy_merged_ranges ();
682 predicate_path
.safe_push (std::make_pair (predicate
, true_edge
));
683 merge_last (predicate_path
);
687 find_range_for_lhs (predicate_vector
&predicate_path
, tree lhs
,
688 int_range_max
&range
)
690 for (int i
= predicate_path
.length () - 1; i
>= 0; i
--)
692 unswitch_predicate
*predicate
= predicate_path
[i
].first
;
693 bool true_edge
= predicate_path
[i
].second
;
695 if (operand_equal_p (predicate
->lhs
, lhs
, 0))
697 range
= (true_edge
? predicate
->merged_true_range
698 : predicate
->merged_false_range
);
699 return !range
.undefined_p ();
706 /* Simplifies STMT using the predicate we unswitched on which is the last
707 in PREDICATE_PATH. For switch statements add newly unreachable edges
708 to IGNORED_EDGES (but do not set IGNORED_EDGE_FLAG on them). */
711 evaluate_control_stmt_using_entry_checks (gimple
*stmt
,
712 predicate_vector
&predicate_path
,
713 int ignored_edge_flag
,
714 hash_set
<edge
> *ignored_edges
)
716 unswitch_predicate
*last_predicate
= predicate_path
.last ().first
;
717 bool true_edge
= predicate_path
.last ().second
;
719 if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
721 tree lhs
= gimple_cond_lhs (cond
);
722 if (!operand_equal_p (lhs
, last_predicate
->lhs
))
724 /* Try a symbolic match which works for floating point and fully
725 symbolic conditions. */
726 if (gimple_cond_code (cond
) == TREE_CODE (last_predicate
->condition
)
727 && operand_equal_p (gimple_cond_rhs (cond
),
728 TREE_OPERAND (last_predicate
->condition
, 1)))
729 return true_edge
? boolean_true_node
: boolean_false_node
;
730 /* Else try ranger if it supports LHS. */
731 else if (irange::supports_p (TREE_TYPE (lhs
)))
734 int_range_max path_range
;
736 if (find_range_for_lhs (predicate_path
, lhs
, path_range
)
737 && fold_range (r
, cond
, path_range
)
739 return r
.zero_p () ? boolean_false_node
: boolean_true_node
;
742 else if (gswitch
*swtch
= dyn_cast
<gswitch
*> (stmt
))
744 unsigned nlabels
= gimple_switch_num_labels (swtch
);
746 tree idx
= gimple_switch_index (swtch
);
748 /* Already folded switch. */
749 if (TREE_CONSTANT (idx
))
752 int_range_max path_range
;
753 if (!find_range_for_lhs (predicate_path
, idx
, path_range
))
756 tree result
= NULL_TREE
;
757 edge single_edge
= NULL
;
758 for (unsigned i
= 0; i
< nlabels
; ++i
)
760 tree lab
= gimple_switch_label (swtch
, i
);
761 basic_block dest
= label_to_block (cfun
, CASE_LABEL (lab
));
762 edge e
= find_edge (gimple_bb (stmt
), dest
);
763 if (e
->flags
& ignored_edge_flag
)
767 if (!ranger
->gori ().edge_range_p (r
, e
, idx
,
768 *get_global_range_query ()))
770 r
.intersect (path_range
);
771 if (r
.undefined_p ())
772 ignored_edges
->add (e
);
778 result
= CASE_LOW (lab
);
780 else if (single_edge
!= e
)
785 /* Only one edge from the switch is alive. */
786 if (single_edge
&& result
)
793 /* Simplify LOOP based on PREDICATE_PATH where dead edges are properly
797 simplify_loop_version (class loop
*loop
, predicate_vector
&predicate_path
,
798 int ignored_edge_flag
, bitmap handled
)
800 bool changed
= false;
801 basic_block
*bbs
= get_loop_body (loop
);
803 hash_set
<edge
> ignored_edges
;
804 for (unsigned i
= 0; i
!= loop
->num_nodes
; i
++)
806 vec
<unswitch_predicate
*> &predicates
= get_predicates_for_bb (bbs
[i
]);
807 if (predicates
.is_empty ())
810 gimple
*stmt
= *gsi_last_bb (bbs
[i
]);
811 tree folded
= evaluate_control_stmt_using_entry_checks (stmt
,
816 if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
821 if (integer_nonzerop (folded
))
822 gimple_cond_set_condition_from_tree (cond
, boolean_true_node
);
824 gimple_cond_set_condition_from_tree (cond
, boolean_false_node
);
826 gcc_assert (predicates
.length () == 1);
827 bitmap_set_bit (handled
, predicates
[0]->num
);
833 else if (gswitch
*swtch
= dyn_cast
<gswitch
*> (stmt
))
837 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
838 if (ignored_edges
.contains (e
))
839 e
->flags
|= ignored_edge_flag
;
841 for (unsigned j
= 0; j
< predicates
.length (); j
++)
843 edge e
= EDGE_SUCC (bbs
[i
], predicates
[j
]->edge_index
);
844 if (ignored_edges
.contains (e
))
845 bitmap_set_bit (handled
, predicates
[j
]->num
);
850 gimple_switch_set_index (swtch
, folded
);
861 /* Evaluate reachable blocks in LOOP and call VISIT on them, aborting the
862 DFS walk if VISIT returns true. When PREDICATE_PATH is specified then
863 take into account that when computing reachability, otherwise just
864 look at the simplified state and IGNORED_EDGE_FLAG. */
866 template <typename VisitOp
>
868 evaluate_bbs (class loop
*loop
, predicate_vector
*predicate_path
,
869 int ignored_edge_flag
, VisitOp visit
)
871 auto_bb_flag
reachable_flag (cfun
);
872 auto_vec
<basic_block
, 10> worklist (loop
->num_nodes
);
873 auto_vec
<basic_block
, 10> reachable (loop
->num_nodes
);
874 hash_set
<edge
> ignored_edges
;
876 loop
->header
->flags
|= reachable_flag
;
877 worklist
.quick_push (loop
->header
);
878 reachable
.safe_push (loop
->header
);
880 while (!worklist
.is_empty ())
884 int flags
= ignored_edge_flag
;
885 basic_block bb
= worklist
.pop ();
890 gimple
*last
= *gsi_last_bb (bb
);
891 if (gcond
*cond
= safe_dyn_cast
<gcond
*> (last
))
893 if (gimple_cond_true_p (cond
))
894 flags
= EDGE_FALSE_VALUE
;
895 else if (gimple_cond_false_p (cond
))
896 flags
= EDGE_TRUE_VALUE
;
897 else if (predicate_path
)
900 if (!get_predicates_for_bb (bb
).is_empty ()
901 && (res
= evaluate_control_stmt_using_entry_checks
902 (cond
, *predicate_path
, ignored_edge_flag
,
904 flags
= (integer_nonzerop (res
)
905 ? EDGE_FALSE_VALUE
: EDGE_TRUE_VALUE
);
908 else if (gswitch
*swtch
= safe_dyn_cast
<gswitch
*> (last
))
910 && !get_predicates_for_bb (bb
).is_empty ())
911 evaluate_control_stmt_using_entry_checks (swtch
, *predicate_path
,
915 /* Note that for the moment we do not account reachable conditions
916 which are simplified to take a known edge as zero size nor
917 are we accounting for the required addition of the versioning
918 condition. Those should cancel out conservatively. */
920 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
922 basic_block dest
= e
->dest
;
924 if (flow_bb_inside_loop_p (loop
, dest
)
925 && !(dest
->flags
& reachable_flag
)
926 && !(e
->flags
& flags
)
927 && !ignored_edges
.contains (e
))
929 dest
->flags
|= reachable_flag
;
930 worklist
.safe_push (dest
);
931 reachable
.safe_push (dest
);
936 /* Clear the flag from basic blocks. */
937 while (!reachable
.is_empty ())
938 reachable
.pop ()->flags
&= ~reachable_flag
;
941 /* Evaluate how many instruction will we have if we unswitch LOOP (with BBS)
942 based on PREDICATE predicate (using PREDICATE_PATH). Store the
943 result in TRUE_SIZE and FALSE_SIZE. */
946 evaluate_loop_insns_for_predicate (class loop
*loop
,
947 predicate_vector
&predicate_path
,
948 unswitch_predicate
*predicate
,
949 int ignored_edge_flag
,
950 unsigned *true_size
, unsigned *false_size
)
953 auto sum_size
= [&](basic_block bb
) -> bool
954 { size
+= (uintptr_t)bb
->aux
; return false; };
956 add_predicate_to_path (predicate_path
, predicate
, true);
957 evaluate_bbs (loop
, &predicate_path
, ignored_edge_flag
, sum_size
);
958 predicate_path
.pop ();
959 unsigned true_loop_cost
= size
;
962 add_predicate_to_path (predicate_path
, predicate
, false);
963 evaluate_bbs (loop
, &predicate_path
, ignored_edge_flag
, sum_size
);
964 predicate_path
.pop ();
965 unsigned false_loop_cost
= size
;
967 *true_size
= true_loop_cost
;
968 *false_size
= false_loop_cost
;
971 /* Unswitch single LOOP. PREDICATE_PATH contains so far used predicates
972 for unswitching. BUDGET is number of instruction for which we can increase
973 the loop and is updated when unswitching occurs. If HOTTEST is not
974 NULL then pick this candidate as the one to unswitch on. */
977 tree_unswitch_single_loop (class loop
*loop
, dump_user_location_t loc
,
978 predicate_vector
&predicate_path
,
979 unsigned loop_size
, unsigned &budget
,
980 int ignored_edge_flag
, bitmap handled
,
981 unswitch_predicate
*hottest
, basic_block hottest_bb
)
984 bool changed
= false;
985 unswitch_predicate
*predicate
= NULL
;
986 basic_block predicate_bb
= NULL
;
987 unsigned true_size
= 0, false_size
= 0;
989 auto check_predicates
= [&](basic_block bb
) -> bool
991 for (auto pred
: get_predicates_for_bb (bb
))
993 if (bitmap_bit_p (handled
, pred
->num
))
996 evaluate_loop_insns_for_predicate (loop
, predicate_path
,
997 pred
, ignored_edge_flag
,
998 &true_size
, &false_size
);
1000 /* We'll get LOOP replaced with a simplified version according
1001 to PRED estimated to TRUE_SIZE and a copy simplified
1002 according to the inverted PRED estimated to FALSE_SIZE. */
1003 if (true_size
+ false_size
< budget
+ loop_size
)
1008 /* There are cases where true_size and false_size add up to
1009 less than the original loop_size. We do not want to
1010 grow the remaining budget because of that. */
1011 if (true_size
+ false_size
> loop_size
)
1012 budget
-= (true_size
+ false_size
- loop_size
);
1014 /* FIXME: right now we select first candidate, but we can
1015 choose the cheapest or hottest one. */
1018 else if (dump_enabled_p ())
1019 dump_printf_loc (MSG_NOTE
, loc
,
1020 "not unswitching condition, cost too big "
1021 "(%u insns copied to %u and %u)\n", loop_size
,
1022 true_size
, false_size
);
1029 predicate
= hottest
;
1030 predicate_bb
= hottest_bb
;
1033 /* Check predicates of reachable blocks. */
1034 evaluate_bbs (loop
, NULL
, ignored_edge_flag
, check_predicates
);
1036 if (predicate
!= NULL
)
1038 if (!dbg_cnt (loop_unswitch
))
1041 if (dump_enabled_p ())
1043 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
1044 "unswitching %sloop %d on %qs with condition: %T\n",
1045 loop
->inner
? "outer " : "",
1046 loop
->num
, predicate
->switch_p
? "switch" : "if",
1047 predicate
->condition
);
1048 dump_printf_loc (MSG_NOTE
, loc
,
1049 "optimized sizes estimated to %u (true) "
1050 "and %u (false) from original size %u\n",
1051 true_size
, false_size
, loop_size
);
1054 bitmap_set_bit (handled
, predicate
->num
);
1055 initialize_original_copy_tables ();
1056 /* Unswitch the loop on this condition. */
1057 nloop
= tree_unswitch_loop (loop
, EDGE_SUCC (predicate_bb
,
1058 predicate
->edge_index
),
1059 predicate
->condition
);
1062 free_original_copy_tables ();
1066 /* Copy BB costs. */
1067 basic_block
*bbs2
= get_loop_body (nloop
);
1068 for (unsigned i
= 0; i
< nloop
->num_nodes
; i
++)
1069 bbs2
[i
]->aux
= get_bb_original (bbs2
[i
])->aux
;
1072 free_original_copy_tables ();
1074 /* Update the SSA form after unswitching. */
1075 update_ssa (TODO_update_ssa_no_phi
);
1077 /* Invoke itself on modified loops. */
1078 bitmap handled_copy
= BITMAP_ALLOC (NULL
);
1079 bitmap_copy (handled_copy
, handled
);
1080 add_predicate_to_path (predicate_path
, predicate
, false);
1081 changed
|= simplify_loop_version (nloop
, predicate_path
,
1082 ignored_edge_flag
, handled_copy
);
1083 tree_unswitch_single_loop (nloop
, loc
, predicate_path
,
1085 ignored_edge_flag
, handled_copy
);
1086 predicate_path
.pop ();
1087 BITMAP_FREE (handled_copy
);
1089 /* FIXME: After unwinding above we have to reset all ->handled
1090 flags as otherwise we fail to realize unswitching opportunities
1091 in the below recursion. See gcc.dg/loop-unswitch-16.c */
1092 add_predicate_to_path (predicate_path
, predicate
, true);
1093 changed
|= simplify_loop_version (loop
, predicate_path
,
1094 ignored_edge_flag
, handled
);
1095 tree_unswitch_single_loop (loop
, loc
, predicate_path
,
1097 ignored_edge_flag
, handled
);
1098 predicate_path
.pop ();
1106 /* Unswitch a LOOP w.r. to given EDGE_TRUE. We only support unswitching of
1107 innermost loops. COND is the condition determining which loop is entered;
1108 the new loop is entered if COND is true. Returns NULL if impossible, new
1112 tree_unswitch_loop (class loop
*loop
, edge edge_true
, tree cond
)
1114 /* Some sanity checking. */
1115 gcc_assert (flow_bb_inside_loop_p (loop
, edge_true
->src
));
1116 gcc_assert (EDGE_COUNT (edge_true
->src
->succs
) >= 2);
1118 profile_probability prob_true
= edge_true
->probability
;
1119 return loop_version (loop
, unshare_expr (cond
),
1121 prob_true
.invert (),
1122 prob_true
, prob_true
.invert (),
1126 /* Unswitch outer loops by hoisting invariant guard on
1127 inner loop without code duplication. */
1129 tree_unswitch_outer_loop (class loop
*loop
)
1132 HOST_WIDE_INT iterations
;
1134 gcc_assert (loop
->inner
);
1135 if (loop
->inner
->next
)
1137 /* Accept loops with single exit only which is not from inner loop. */
1138 exit
= single_exit (loop
);
1139 if (!exit
|| exit
->src
->loop_father
!= loop
)
1141 /* Check that phi argument of exit edge is not defined inside loop. */
1142 if (!check_exit_phi (loop
))
1144 /* If the loop is not expected to iterate, there is no need
1146 iterations
= estimated_loop_iterations_int (loop
);
1148 iterations
= likely_max_loop_iterations_int (loop
);
1149 if (iterations
>= 0 && iterations
<= 1)
1151 if (dump_enabled_p ())
1152 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, find_loop_location (loop
),
1153 "Not unswitching, loop is not expected"
1158 bool changed
= false;
1159 auto_vec
<gimple
*> dbg_to_reset
;
1160 while ((guard
= find_loop_guard (loop
, dbg_to_reset
)))
1162 hoist_guard (loop
, guard
);
1163 for (gimple
*debug_stmt
: dbg_to_reset
)
1165 gimple_debug_bind_reset_value (debug_stmt
);
1166 update_stmt (debug_stmt
);
1168 dbg_to_reset
.truncate (0);
1174 /* Checks if the body of the LOOP is within an invariant guard. If this
1175 is the case, returns the edge that jumps over the real body of the loop,
1176 otherwise returns NULL. */
1179 find_loop_guard (class loop
*loop
, vec
<gimple
*> &dbg_to_reset
)
1181 basic_block header
= loop
->header
;
1182 edge guard_edge
, te
, fe
;
1183 basic_block
*body
= NULL
;
1188 /* We check for the following situation:
1197 nvar = phi(orig, bvar) ... for all variables changed in body;
1207 1) cond1 is loop invariant
1208 2) If cond1 is false, then the loop is essentially empty; i.e.,
1209 a) nothing in something1, something2 and something3 has side
1211 b) anything defined in something1, something2 and something3
1212 is not used outside of the loop. */
1217 basic_block next
= NULL
;
1218 if (single_succ_p (header
))
1219 next
= single_succ (header
);
1222 cond
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (header
));
1225 extract_true_false_edges_from_block (header
, &te
, &fe
);
1226 /* Make sure to skip earlier hoisted guards that are left
1227 in place as if (true). */
1228 if (gimple_cond_true_p (cond
))
1230 else if (gimple_cond_false_p (cond
))
1235 /* Never traverse a backedge. */
1236 if (header
->loop_father
->header
== next
)
1241 if (!flow_bb_inside_loop_p (loop
, te
->dest
)
1242 || !flow_bb_inside_loop_p (loop
, fe
->dest
))
1245 if (just_once_each_iteration_p (loop
, te
->dest
)
1246 || (single_succ_p (te
->dest
)
1247 && just_once_each_iteration_p (loop
, single_succ (te
->dest
))))
1249 if (just_once_each_iteration_p (loop
, fe
->dest
))
1253 else if (just_once_each_iteration_p (loop
, fe
->dest
)
1254 || (single_succ_p (fe
->dest
)
1255 && just_once_each_iteration_p (loop
, single_succ (fe
->dest
))))
1260 dump_user_location_t loc
= find_loop_location (loop
);
1262 /* Guard edge must skip inner loop. */
1263 if (!dominated_by_p (CDI_DOMINATORS
, loop
->inner
->header
,
1264 guard_edge
== fe
? te
->dest
: fe
->dest
))
1266 if (dump_enabled_p ())
1267 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1268 "Guard edge %d --> %d is not around the loop!\n",
1269 guard_edge
->src
->index
, guard_edge
->dest
->index
);
1272 if (guard_edge
->dest
== loop
->latch
)
1274 if (dump_enabled_p ())
1275 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1276 "Guard edge destination is loop latch.\n");
1280 if (dump_enabled_p ())
1281 dump_printf_loc (MSG_NOTE
, loc
,
1282 "Considering guard %d -> %d in loop %d\n",
1283 guard_edge
->src
->index
, guard_edge
->dest
->index
,
1285 /* Check if condition operands do not have definitions inside loop since
1286 any bb copying is not performed. */
1287 FOR_EACH_SSA_TREE_OPERAND (use
, cond
, iter
, SSA_OP_USE
)
1289 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1290 basic_block def_bb
= gimple_bb (def
);
1292 && flow_bb_inside_loop_p (loop
, def_bb
))
1294 if (dump_enabled_p ())
1295 dump_printf_loc (MSG_NOTE
, loc
, "guard operands have definitions"
1301 body
= get_loop_body (loop
);
1302 for (i
= 0; i
< loop
->num_nodes
; i
++)
1304 basic_block bb
= body
[i
];
1305 if (bb
->loop_father
!= loop
)
1307 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1309 if (dump_enabled_p ())
1310 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1311 "Block %d is marked as irreducible in loop\n",
1316 if (!empty_bb_without_guard_p (loop
, bb
, dbg_to_reset
))
1318 if (dump_enabled_p ())
1319 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1320 "Block %d has side effects\n", bb
->index
);
1326 if (dump_enabled_p ())
1327 dump_printf_loc (MSG_NOTE
, loc
,
1328 "suitable to hoist\n");
1336 1) no statement in BB has side effects
1337 2) assuming that edge GUARD is always taken, all definitions in BB
1338 are noy used outside of the loop.
1339 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
1340 PROCESSED is a set of ssa names for that we already tested whether they
1341 are invariant or not. Uses in debug stmts outside of the loop are
1342 pushed to DBG_TO_RESET. */
1345 empty_bb_without_guard_p (class loop
*loop
, basic_block bb
,
1346 vec
<gimple
*> &dbg_to_reset
)
1348 basic_block exit_bb
= single_exit (loop
)->src
;
1349 bool may_be_used_outside
= (bb
== exit_bb
1350 || !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
));
1352 ssa_op_iter op_iter
;
1354 /* Phi nodes do not have side effects, but their results might be used
1355 outside of the loop. */
1356 if (may_be_used_outside
)
1358 for (gphi_iterator gsi
= gsi_start_phis (bb
);
1359 !gsi_end_p (gsi
); gsi_next (&gsi
))
1361 gphi
*phi
= gsi
.phi ();
1362 name
= PHI_RESULT (phi
);
1363 if (virtual_operand_p (name
))
1366 if (used_outside_loop_p (loop
, name
, dbg_to_reset
))
1371 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
1372 !gsi_end_p (gsi
); gsi_next (&gsi
))
1374 gimple
*stmt
= gsi_stmt (gsi
);
1375 if (is_gimple_debug (stmt
))
1378 if (gimple_has_side_effects (stmt
))
1381 if (gimple_vdef(stmt
))
1384 FOR_EACH_SSA_TREE_OPERAND (name
, stmt
, op_iter
, SSA_OP_DEF
)
1386 if (may_be_used_outside
1387 && used_outside_loop_p (loop
, name
, dbg_to_reset
))
1394 /* Return true if NAME is used outside of LOOP. Pushes debug stmts that
1395 have such uses to DBG_TO_RESET but do not consider such uses. */
1398 used_outside_loop_p (class loop
*loop
, tree name
, vec
<gimple
*> &dbg_to_reset
)
1400 imm_use_iterator it
;
1403 FOR_EACH_IMM_USE_FAST (use
, it
, name
)
1405 gimple
*stmt
= USE_STMT (use
);
1406 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1408 if (!is_gimple_debug (stmt
))
1410 dbg_to_reset
.safe_push (stmt
);
1417 /* Return argument for loop preheader edge in header virtual phi if any. */
1420 get_vop_from_header (class loop
*loop
)
1422 for (gphi_iterator gsi
= gsi_start_phis (loop
->header
);
1423 !gsi_end_p (gsi
); gsi_next (&gsi
))
1425 gphi
*phi
= gsi
.phi ();
1426 if (!virtual_operand_p (gimple_phi_result (phi
)))
1428 return PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1433 /* Move the check of GUARD outside of LOOP. */
1436 hoist_guard (class loop
*loop
, edge guard
)
1438 edge exit
= single_exit (loop
);
1439 edge preh
= loop_preheader_edge (loop
);
1440 basic_block pre_header
= preh
->src
;
1442 edge te
, fe
, e
, new_edge
;
1444 basic_block guard_bb
= guard
->src
;
1446 gimple_stmt_iterator gsi
;
1448 bool fix_dom_of_exit
;
1449 gcond
*cond_stmt
, *new_cond_stmt
;
1451 bb
= get_immediate_dominator (CDI_DOMINATORS
, exit
->dest
);
1452 fix_dom_of_exit
= flow_bb_inside_loop_p (loop
, bb
);
1453 gsi
= gsi_last_bb (guard_bb
);
1454 stmt
= gsi_stmt (gsi
);
1455 gcc_assert (gimple_code (stmt
) == GIMPLE_COND
);
1456 cond_stmt
= as_a
<gcond
*> (stmt
);
1457 extract_true_false_edges_from_block (guard_bb
, &te
, &fe
);
1458 /* Insert guard to PRE_HEADER. */
1459 gsi
= gsi_last_bb (pre_header
);
1460 /* Create copy of COND_STMT. */
1461 new_cond_stmt
= gimple_build_cond (gimple_cond_code (cond_stmt
),
1462 gimple_cond_lhs (cond_stmt
),
1463 gimple_cond_rhs (cond_stmt
),
1464 NULL_TREE
, NULL_TREE
);
1465 gsi_insert_after (&gsi
, new_cond_stmt
, GSI_NEW_STMT
);
1466 /* Convert COND_STMT to true/false conditional. */
1468 gimple_cond_make_false (cond_stmt
);
1470 gimple_cond_make_true (cond_stmt
);
1471 update_stmt (cond_stmt
);
1472 /* Create new loop pre-header. */
1473 e
= split_block (pre_header
, last_nondebug_stmt (pre_header
));
1475 dump_user_location_t loc
= find_loop_location (loop
);
1477 if (dump_enabled_p ())
1480 guard
->probability
.dump (buffer
);
1482 dump_printf_loc (MSG_NOTE
, loc
,
1483 "Moving guard %i->%i (prob %s) to bb %i, "
1484 "new preheader is %i\n",
1485 guard
->src
->index
, guard
->dest
->index
,
1486 buffer
, e
->src
->index
, e
->dest
->index
);
1489 gcc_assert (loop_preheader_edge (loop
)->src
== e
->dest
);
1493 e
->flags
= EDGE_TRUE_VALUE
;
1494 flags
|= EDGE_FALSE_VALUE
;
1499 e
->flags
= EDGE_FALSE_VALUE
;
1500 flags
|= EDGE_TRUE_VALUE
;
1503 new_edge
= make_edge (pre_header
, exit
->dest
, flags
);
1505 /* Determine the probability that we skip the loop. Assume that loop has
1506 same average number of iterations regardless outcome of guard. */
1507 new_edge
->probability
= guard
->probability
;
1508 profile_count skip_count
= guard
->src
->count
.nonzero_p ()
1509 ? guard
->count ().apply_scale (pre_header
->count
,
1511 : guard
->count ().apply_probability (new_edge
->probability
);
1513 if (skip_count
> e
->count ())
1515 fprintf (dump_file
, " Capping count; expect profile inconsistency\n");
1516 skip_count
= e
->count ();
1518 if (dump_enabled_p ())
1521 new_edge
->probability
.dump (buffer
);
1523 dump_printf_loc (MSG_NOTE
, loc
,
1524 "Estimated probability of skipping loop is %s\n",
1528 /* Update profile after the transform:
1530 First decrease count of path from newly hoisted loop guard
1531 to loop header... */
1532 e
->probability
= new_edge
->probability
.invert ();
1533 e
->dest
->count
= e
->count ();
1535 /* ... now update profile to represent that original guard will be optimized
1537 guard
->probability
= profile_probability::never ();
1538 not_guard
->probability
= profile_probability::always ();
1540 /* ... finally scale everything in the loop except for guarded basic blocks
1541 where profile does not change. */
1542 basic_block
*body
= get_loop_body (loop
);
1544 for (unsigned int i
= 0; i
< loop
->num_nodes
; i
++)
1546 basic_block bb
= body
[i
];
1547 if (!dominated_by_p (CDI_DOMINATORS
, bb
, not_guard
->dest
))
1549 if (dump_enabled_p ())
1550 dump_printf_loc (MSG_NOTE
, loc
,
1551 "Scaling nonguarded BBs in loop: %i\n",
1553 if (e
->probability
.initialized_p ())
1554 scale_bbs_frequencies (&bb
, 1, e
->probability
);
1558 if (fix_dom_of_exit
)
1559 set_immediate_dominator (CDI_DOMINATORS
, exit
->dest
, pre_header
);
1560 /* Add NEW_ADGE argument for all phi in post-header block. */
1562 for (gphi_iterator gsi
= gsi_start_phis (bb
);
1563 !gsi_end_p (gsi
); gsi_next (&gsi
))
1565 gphi
*phi
= gsi
.phi ();
1567 if (virtual_operand_p (gimple_phi_result (phi
)))
1569 arg
= get_vop_from_header (loop
);
1570 if (arg
== NULL_TREE
)
1571 /* Use exit edge argument. */
1572 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1573 add_phi_arg (phi
, arg
, new_edge
, UNKNOWN_LOCATION
);
1577 /* Use exit edge argument. */
1578 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1579 add_phi_arg (phi
, arg
, new_edge
, UNKNOWN_LOCATION
);
1583 if (dump_enabled_p ())
1584 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
1590 /* Return true if phi argument for exit edge can be used
1591 for edge around loop. */
1594 check_exit_phi (class loop
*loop
)
1596 edge exit
= single_exit (loop
);
1597 basic_block pre_header
= loop_preheader_edge (loop
)->src
;
1599 for (gphi_iterator gsi
= gsi_start_phis (exit
->dest
);
1600 !gsi_end_p (gsi
); gsi_next (&gsi
))
1602 gphi
*phi
= gsi
.phi ();
1606 if (virtual_operand_p (gimple_phi_result (phi
)))
1608 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1609 if (TREE_CODE (arg
) != SSA_NAME
)
1611 def
= SSA_NAME_DEF_STMT (arg
);
1614 def_bb
= gimple_bb (def
);
1617 if (!dominated_by_p (CDI_DOMINATORS
, pre_header
, def_bb
))
1618 /* Definition inside loop! */
1620 /* Check loop closed phi invariant. */
1621 if (!flow_bb_inside_loop_p (def_bb
->loop_father
, pre_header
))
1627 /* Remove all dead cases from switches that are unswitched. */
1630 clean_up_after_unswitching (int ignored_edge_flag
)
1635 bool removed_edge
= false;
1637 FOR_EACH_BB_FN (bb
, cfun
)
1639 gswitch
*stmt
= safe_dyn_cast
<gswitch
*> (*gsi_last_bb (bb
));
1640 if (stmt
&& !CONSTANT_CLASS_P (gimple_switch_index (stmt
)))
1642 unsigned nlabels
= gimple_switch_num_labels (stmt
);
1644 tree lab
= gimple_switch_default_label (stmt
);
1645 edge default_e
= find_edge (gimple_bb (stmt
),
1646 label_to_block (cfun
, CASE_LABEL (lab
)));
1647 for (unsigned i
= 1; i
< nlabels
; ++i
)
1649 tree lab
= gimple_switch_label (stmt
, i
);
1650 basic_block dest
= label_to_block (cfun
, CASE_LABEL (lab
));
1651 edge e
= find_edge (gimple_bb (stmt
), dest
);
1653 ; /* The edge is already removed. */
1654 else if (e
->flags
& ignored_edge_flag
)
1656 /* We may not remove the default label so we also have
1657 to preserve its edge. But we can remove the
1658 non-default CASE sharing the edge. */
1662 removed_edge
= true;
1667 gimple_switch_set_label (stmt
, index
, lab
);
1672 if (index
!= nlabels
)
1673 gimple_switch_set_num_labels (stmt
, index
);
1676 /* Clean up the ignored_edge_flag from edges. */
1677 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1678 e
->flags
&= ~ignored_edge_flag
;
1681 /* If we removed an edge we possibly have to recompute dominators. */
1683 free_dominance_info (CDI_DOMINATORS
);
1686 /* Loop unswitching pass. */
1690 const pass_data pass_data_tree_unswitch
=
1692 GIMPLE_PASS
, /* type */
1693 "unswitch", /* name */
1694 OPTGROUP_LOOP
, /* optinfo_flags */
1695 TV_TREE_LOOP_UNSWITCH
, /* tv_id */
1696 PROP_cfg
, /* properties_required */
1697 0, /* properties_provided */
1698 0, /* properties_destroyed */
1699 0, /* todo_flags_start */
1700 0, /* todo_flags_finish */
1703 class pass_tree_unswitch
: public gimple_opt_pass
1706 pass_tree_unswitch (gcc::context
*ctxt
)
1707 : gimple_opt_pass (pass_data_tree_unswitch
, ctxt
)
1710 /* opt_pass methods: */
1711 bool gate (function
*) final override
{ return flag_unswitch_loops
!= 0; }
1712 unsigned int execute (function
*) final override
;
1714 }; // class pass_tree_unswitch
1717 pass_tree_unswitch::execute (function
*fun
)
1719 if (number_of_loops (fun
) <= 1)
1722 return tree_ssa_unswitch_loops (fun
);
1728 make_pass_tree_unswitch (gcc::context
*ctxt
)
1730 return new pass_tree_unswitch (ctxt
);