diff options
Diffstat (limited to 'gcc/tree-ssa-loop-unswitch.c')
| -rw-r--r-- | gcc/tree-ssa-loop-unswitch.c | 1042 |
1 files changed, 0 insertions, 1042 deletions
diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c deleted file mode 100644 index 46a6ff5..0000000 --- a/gcc/tree-ssa-loop-unswitch.c +++ /dev/null @@ -1,1042 +0,0 @@ -/* Loop unswitching. - Copyright (C) 2004-2022 Free Software Foundation, Inc. - -This file is part of GCC. - -GCC is free software; you can redistribute it and/or modify it -under the terms of the GNU General Public License as published by the -Free Software Foundation; either version 3, or (at your option) any -later version. - -GCC is distributed in the hope that it will be useful, but WITHOUT -ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or -FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License -for more details. - -You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING3. If not see -<http://www.gnu.org/licenses/>. */ - -#include "config.h" -#include "system.h" -#include "coretypes.h" -#include "backend.h" -#include "tree.h" -#include "gimple.h" -#include "tree-pass.h" -#include "ssa.h" -#include "fold-const.h" -#include "gimplify.h" -#include "tree-cfg.h" -#include "tree-ssa.h" -#include "tree-ssa-loop-niter.h" -#include "tree-ssa-loop.h" -#include "tree-into-ssa.h" -#include "cfgloop.h" -#include "tree-inline.h" -#include "gimple-iterator.h" -#include "cfghooks.h" -#include "tree-ssa-loop-manip.h" -#include "tree-vectorizer.h" - -/* This file implements the loop unswitching, i.e. transformation of loops like - - while (A) - { - if (inv) - B; - - X; - - if (!inv) - C; - } - - where inv is the loop invariant, into - - if (inv) - { - while (A) - { - B; - X; - } - } - else - { - while (A) - { - X; - C; - } - } - - Inv is considered invariant iff the values it compares are both invariant; - tree-ssa-loop-im.c ensures that all the suitable conditions are in this - shape. */ - -static class loop *tree_unswitch_loop (class loop *, basic_block, tree); -static bool tree_unswitch_single_loop (class loop *, int); -static tree tree_may_unswitch_on (basic_block, class loop *); -static bool tree_unswitch_outer_loop (class loop *); -static edge find_loop_guard (class loop *); -static bool empty_bb_without_guard_p (class loop *, basic_block); -static bool used_outside_loop_p (class loop *, tree); -static void hoist_guard (class loop *, edge); -static bool check_exit_phi (class loop *); -static tree get_vop_from_header (class loop *); - -/* Main entry point. Perform loop unswitching on all suitable loops. */ - -unsigned int -tree_ssa_unswitch_loops (void) -{ - bool changed = false; - - /* Go through all loops starting from innermost. */ - for (auto loop : loops_list (cfun, LI_FROM_INNERMOST)) - { - if (!loop->inner) - /* Unswitch innermost loop. */ - changed |= tree_unswitch_single_loop (loop, 0); - else - changed |= tree_unswitch_outer_loop (loop); - } - - if (changed) - return TODO_cleanup_cfg; - return 0; -} - -/* Return TRUE if an SSA_NAME maybe undefined and is therefore - unsuitable for unswitching. STMT is the statement we are - considering for unswitching and LOOP is the loop it appears in. */ - -static bool -is_maybe_undefined (const tree name, gimple *stmt, class loop *loop) -{ - /* The loop header is the only block we can trivially determine that - will always be executed. If the comparison is in the loop - header, we know it's OK to unswitch on it. */ - if (gimple_bb (stmt) == loop->header) - return false; - - auto_bitmap visited_ssa; - auto_vec<tree> worklist; - worklist.safe_push (name); - bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name)); - while (!worklist.is_empty ()) - { - tree t = worklist.pop (); - - /* If it's obviously undefined, avoid further computations. */ - if (ssa_undefined_value_p (t, true)) - return true; - - if (ssa_defined_default_def_p (t)) - continue; - - gimple *def = SSA_NAME_DEF_STMT (t); - - /* Check that all the PHI args are fully defined. */ - if (gphi *phi = dyn_cast <gphi *> (def)) - { - for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i) - { - tree t = gimple_phi_arg_def (phi, i); - /* If an SSA has already been seen, it may be a loop, - but we can continue and ignore this use. Otherwise, - add the SSA_NAME to the queue and visit it later. */ - if (TREE_CODE (t) == SSA_NAME - && bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t))) - worklist.safe_push (t); - } - continue; - } - - /* Uses in stmts always executed when the region header executes - are fine. */ - if (dominated_by_p (CDI_DOMINATORS, loop->header, gimple_bb (def))) - continue; - - /* Handle calls and memory loads conservatively. */ - if (!is_gimple_assign (def) - || (gimple_assign_single_p (def) - && gimple_vuse (def))) - return true; - - /* Check that any SSA names used to define NAME are also fully - defined. */ - use_operand_p use_p; - ssa_op_iter iter; - FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE) - { - tree t = USE_FROM_PTR (use_p); - /* If an SSA has already been seen, it may be a loop, - but we can continue and ignore this use. Otherwise, - add the SSA_NAME to the queue and visit it later. */ - if (bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t))) - worklist.safe_push (t); - } - } - return false; -} - -/* Checks whether we can unswitch LOOP on condition at end of BB -- one of its - basic blocks (for what it means see comments below). */ - -static tree -tree_may_unswitch_on (basic_block bb, class loop *loop) -{ - gimple *last, *def; - gcond *stmt; - tree cond, use; - basic_block def_bb; - ssa_op_iter iter; - - /* BB must end in a simple conditional jump. */ - last = last_stmt (bb); - if (!last || gimple_code (last) != GIMPLE_COND) - return NULL_TREE; - stmt = as_a <gcond *> (last); - - /* To keep the things simple, we do not directly remove the conditions, - but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite - loop where we would unswitch again on such a condition. */ - if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt)) - return NULL_TREE; - - /* Condition must be invariant. */ - FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) - { - def = SSA_NAME_DEF_STMT (use); - def_bb = gimple_bb (def); - if (def_bb - && flow_bb_inside_loop_p (loop, def_bb)) - return NULL_TREE; - /* Unswitching on undefined values would introduce undefined - behavior that the original program might never exercise. */ - if (is_maybe_undefined (use, stmt, loop)) - return NULL_TREE; - } - - cond = build2 (gimple_cond_code (stmt), boolean_type_node, - gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); - - return cond; -} - -/* Simplifies COND using checks in front of the entry of the LOOP. Just very - simplish (sufficient to prevent us from duplicating loop in unswitching - unnecessarily). */ - -static tree -simplify_using_entry_checks (class loop *loop, tree cond) -{ - edge e = loop_preheader_edge (loop); - gimple *stmt; - - while (1) - { - stmt = last_stmt (e->src); - if (stmt - && gimple_code (stmt) == GIMPLE_COND - && gimple_cond_code (stmt) == TREE_CODE (cond) - && operand_equal_p (gimple_cond_lhs (stmt), - TREE_OPERAND (cond, 0), 0) - && operand_equal_p (gimple_cond_rhs (stmt), - TREE_OPERAND (cond, 1), 0)) - return (e->flags & EDGE_TRUE_VALUE - ? boolean_true_node - : boolean_false_node); - - if (!single_pred_p (e->src)) - return cond; - - e = single_pred_edge (e->src); - if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) - return cond; - } -} - -/* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow - it to grow too much, it is too easy to create example on that the code would - grow exponentially. */ - -static bool -tree_unswitch_single_loop (class loop *loop, int num) -{ - basic_block *bbs; - class loop *nloop; - unsigned i, found; - tree cond = NULL_TREE; - gimple *stmt; - bool changed = false; - HOST_WIDE_INT iterations; - - dump_user_location_t loc = find_loop_location (loop); - - /* Perform initial tests if unswitch is eligible. */ - if (num == 0) - { - /* Do not unswitch in cold regions. */ - if (optimize_loop_for_size_p (loop)) - { - if (dump_enabled_p ()) - dump_printf_loc (MSG_NOTE, loc, - "Not unswitching cold loops\n"); - return false; - } - - /* The loop should not be too large, to limit code growth. */ - if (tree_num_loop_insns (loop, &eni_size_weights) - > (unsigned) param_max_unswitch_insns) - { - if (dump_enabled_p ()) - dump_printf_loc (MSG_NOTE, loc, - "Not unswitching, loop too big\n"); - return false; - } - - /* If the loop is not expected to iterate, there is no need - for unswitching. */ - iterations = estimated_loop_iterations_int (loop); - if (iterations < 0) - iterations = likely_max_loop_iterations_int (loop); - if (iterations >= 0 && iterations <= 1) - { - if (dump_enabled_p ()) - dump_printf_loc (MSG_NOTE, loc, - "Not unswitching, loop is not expected" - " to iterate\n"); - return false; - } - } - - i = 0; - bbs = get_loop_body (loop); - found = loop->num_nodes; - - while (1) - { - /* Find a bb to unswitch on. */ - for (; i < loop->num_nodes; i++) - if ((cond = tree_may_unswitch_on (bbs[i], loop))) - break; - - if (i == loop->num_nodes) - { - if (dump_enabled_p () - && num > param_max_unswitch_level) - dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, - "Not unswitching anymore, hit max level\n"); - - if (found == loop->num_nodes) - { - free (bbs); - return changed; - } - break; - } - - cond = simplify_using_entry_checks (loop, cond); - stmt = last_stmt (bbs[i]); - if (integer_nonzerop (cond)) - { - /* Remove false path. */ - gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt), - boolean_true_node); - changed = true; - } - else if (integer_zerop (cond)) - { - /* Remove true path. */ - gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt), - boolean_false_node); - changed = true; - } - /* Do not unswitch too much. */ - else if (num > param_max_unswitch_level) - { - i++; - continue; - } - /* In nested tree_unswitch_single_loop first optimize all conditions - using entry checks, then discover still reachable blocks in the - loop and find the condition only among those still reachable bbs. */ - else if (num != 0) - { - if (found == loop->num_nodes) - found = i; - i++; - continue; - } - else - { - found = i; - break; - } - - update_stmt (stmt); - i++; - } - - if (num != 0) - { - basic_block *tos, *worklist; - - /* When called recursively, first do a quick discovery - of reachable bbs after the above changes and only - consider conditions in still reachable bbs. */ - tos = worklist = XNEWVEC (basic_block, loop->num_nodes); - - for (i = 0; i < loop->num_nodes; i++) - bbs[i]->flags &= ~BB_REACHABLE; - - /* Start with marking header. */ - *tos++ = bbs[0]; - bbs[0]->flags |= BB_REACHABLE; - - /* Iterate: find everything reachable from what we've already seen - within the same innermost loop. Don't look through false edges - if condition is always true or true edges if condition is - always false. */ - while (tos != worklist) - { - basic_block b = *--tos; - edge e; - edge_iterator ei; - int flags = 0; - - if (EDGE_COUNT (b->succs) == 2) - { - gimple *stmt = last_stmt (b); - if (stmt - && gimple_code (stmt) == GIMPLE_COND) - { - gcond *cond_stmt = as_a <gcond *> (stmt); - if (gimple_cond_true_p (cond_stmt)) - flags = EDGE_FALSE_VALUE; - else if (gimple_cond_false_p (cond_stmt)) - flags = EDGE_TRUE_VALUE; - } - } - - FOR_EACH_EDGE (e, ei, b->succs) - { - basic_block dest = e->dest; - - if (dest->loop_father == loop - && !(dest->flags & BB_REACHABLE) - && !(e->flags & flags)) - { - *tos++ = dest; - dest->flags |= BB_REACHABLE; - } - } - } - - free (worklist); - - /* Find a bb to unswitch on. */ - for (; found < loop->num_nodes; found++) - if ((bbs[found]->flags & BB_REACHABLE) - && (cond = tree_may_unswitch_on (bbs[found], loop))) - break; - - if (found == loop->num_nodes) - { - free (bbs); - return changed; - } - } - - if (dump_enabled_p ()) - dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc, - "Unswitching loop on condition: %G\n", - last_stmt (bbs[found])); - - initialize_original_copy_tables (); - /* Unswitch the loop on this condition. */ - nloop = tree_unswitch_loop (loop, bbs[found], cond); - if (!nloop) - { - free_original_copy_tables (); - free (bbs); - return changed; - } - - /* Update the SSA form after unswitching. */ - update_ssa (TODO_update_ssa); - free_original_copy_tables (); - - /* Invoke itself on modified loops. */ - tree_unswitch_single_loop (nloop, num + 1); - tree_unswitch_single_loop (loop, num + 1); - free (bbs); - return true; -} - -/* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support - unswitching of innermost loops. COND is the condition determining which - loop is entered -- the new loop is entered if COND is true. Returns NULL - if impossible, new loop otherwise. */ - -static class loop * -tree_unswitch_loop (class loop *loop, - basic_block unswitch_on, tree cond) -{ - profile_probability prob_true; - edge edge_true, edge_false; - - /* Some sanity checking. */ - gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on)); - gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2); - gcc_assert (loop->inner == NULL); - - extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false); - prob_true = edge_true->probability; - return loop_version (loop, unshare_expr (cond), - NULL, prob_true, - prob_true.invert (), - prob_true, prob_true.invert (), - false); -} - -/* Unswitch outer loops by hoisting invariant guard on - inner loop without code duplication. */ -static bool -tree_unswitch_outer_loop (class loop *loop) -{ - edge exit, guard; - HOST_WIDE_INT iterations; - - gcc_assert (loop->inner); - if (loop->inner->next) - return false; - /* Accept loops with single exit only which is not from inner loop. */ - exit = single_exit (loop); - if (!exit || exit->src->loop_father != loop) - return false; - /* Check that phi argument of exit edge is not defined inside loop. */ - if (!check_exit_phi (loop)) - return false; - /* If the loop is not expected to iterate, there is no need - for unswitching. */ - iterations = estimated_loop_iterations_int (loop); - if (iterations < 0) - iterations = likely_max_loop_iterations_int (loop); - if (iterations >= 0 && iterations <= 1) - { - if (dump_enabled_p ()) - dump_printf_loc (MSG_MISSED_OPTIMIZATION, find_loop_location (loop), - "Not unswitching, loop is not expected" - " to iterate\n"); - return false; - } - - bool changed = false; - while ((guard = find_loop_guard (loop))) - { - if (! changed) - rewrite_virtuals_into_loop_closed_ssa (loop); - hoist_guard (loop, guard); - changed = true; - } - return changed; -} - -/* Checks if the body of the LOOP is within an invariant guard. If this - is the case, returns the edge that jumps over the real body of the loop, - otherwise returns NULL. */ - -static edge -find_loop_guard (class loop *loop) -{ - basic_block header = loop->header; - edge guard_edge, te, fe; - basic_block *body = NULL; - unsigned i; - tree use; - ssa_op_iter iter; - - /* We check for the following situation: - - while (1) - { - [header]] - loop_phi_nodes; - something1; - if (cond1) - body; - nvar = phi(orig, bvar) ... for all variables changed in body; - [guard_end] - something2; - if (cond2) - break; - something3; - } - - where: - - 1) cond1 is loop invariant - 2) If cond1 is false, then the loop is essentially empty; i.e., - a) nothing in something1, something2 and something3 has side - effects - b) anything defined in something1, something2 and something3 - is not used outside of the loop. */ - - gcond *cond; - do - { - basic_block next = NULL; - if (single_succ_p (header)) - next = single_succ (header); - else - { - cond = safe_dyn_cast <gcond *> (last_stmt (header)); - if (! cond) - return NULL; - extract_true_false_edges_from_block (header, &te, &fe); - /* Make sure to skip earlier hoisted guards that are left - in place as if (true). */ - if (gimple_cond_true_p (cond)) - next = te->dest; - else if (gimple_cond_false_p (cond)) - next = fe->dest; - else - break; - } - /* Never traverse a backedge. */ - if (header->loop_father->header == next) - return NULL; - header = next; - } - while (1); - if (!flow_bb_inside_loop_p (loop, te->dest) - || !flow_bb_inside_loop_p (loop, fe->dest)) - return NULL; - - if (just_once_each_iteration_p (loop, te->dest) - || (single_succ_p (te->dest) - && just_once_each_iteration_p (loop, single_succ (te->dest)))) - { - if (just_once_each_iteration_p (loop, fe->dest)) - return NULL; - guard_edge = te; - } - else if (just_once_each_iteration_p (loop, fe->dest) - || (single_succ_p (fe->dest) - && just_once_each_iteration_p (loop, single_succ (fe->dest)))) - guard_edge = fe; - else - return NULL; - - dump_user_location_t loc = find_loop_location (loop); - - /* Guard edge must skip inner loop. */ - if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header, - guard_edge == fe ? te->dest : fe->dest)) - { - if (dump_enabled_p ()) - dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, - "Guard edge %d --> %d is not around the loop!\n", - guard_edge->src->index, guard_edge->dest->index); - return NULL; - } - if (guard_edge->dest == loop->latch) - { - if (dump_enabled_p ()) - dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, - "Guard edge destination is loop latch.\n"); - return NULL; - } - - if (dump_enabled_p ()) - dump_printf_loc (MSG_NOTE, loc, - "Considering guard %d -> %d in loop %d\n", - guard_edge->src->index, guard_edge->dest->index, - loop->num); - /* Check if condition operands do not have definitions inside loop since - any bb copying is not performed. */ - FOR_EACH_SSA_TREE_OPERAND (use, cond, iter, SSA_OP_USE) - { - gimple *def = SSA_NAME_DEF_STMT (use); - basic_block def_bb = gimple_bb (def); - if (def_bb - && flow_bb_inside_loop_p (loop, def_bb)) - { - if (dump_enabled_p ()) - dump_printf_loc (MSG_NOTE, loc, "guard operands have definitions" - " inside loop\n"); - return NULL; - } - } - - body = get_loop_body (loop); - for (i = 0; i < loop->num_nodes; i++) - { - basic_block bb = body[i]; - if (bb->loop_father != loop) - continue; - if (bb->flags & BB_IRREDUCIBLE_LOOP) - { - if (dump_enabled_p ()) - dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, - "Block %d is marked as irreducible in loop\n", - bb->index); - guard_edge = NULL; - goto end; - } - if (!empty_bb_without_guard_p (loop, bb)) - { - if (dump_enabled_p ()) - dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, - "Block %d has side effects\n", bb->index); - guard_edge = NULL; - goto end; - } - } - - if (dump_enabled_p ()) - dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc, - "suitable to hoist\n"); -end: - if (body) - free (body); - return guard_edge; -} - -/* Returns true if - 1) no statement in BB has side effects - 2) assuming that edge GUARD is always taken, all definitions in BB - are noy used outside of the loop. - KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and - PROCESSED is a set of ssa names for that we already tested whether they - are invariant or not. */ - -static bool -empty_bb_without_guard_p (class loop *loop, basic_block bb) -{ - basic_block exit_bb = single_exit (loop)->src; - bool may_be_used_outside = (bb == exit_bb - || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)); - tree name; - ssa_op_iter op_iter; - - /* Phi nodes do not have side effects, but their results might be used - outside of the loop. */ - if (may_be_used_outside) - { - for (gphi_iterator gsi = gsi_start_phis (bb); - !gsi_end_p (gsi); gsi_next (&gsi)) - { - gphi *phi = gsi.phi (); - name = PHI_RESULT (phi); - if (virtual_operand_p (name)) - continue; - - if (used_outside_loop_p (loop, name)) - return false; - } - } - - for (gimple_stmt_iterator gsi = gsi_start_bb (bb); - !gsi_end_p (gsi); gsi_next (&gsi)) - { - gimple *stmt = gsi_stmt (gsi); - if (gimple_has_side_effects (stmt)) - return false; - - if (gimple_vdef(stmt)) - return false; - - FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF) - { - if (may_be_used_outside - && used_outside_loop_p (loop, name)) - return false; - } - } - return true; -} - -/* Return true if NAME is used outside of LOOP. */ - -static bool -used_outside_loop_p (class loop *loop, tree name) -{ - imm_use_iterator it; - use_operand_p use; - - FOR_EACH_IMM_USE_FAST (use, it, name) - { - gimple *stmt = USE_STMT (use); - if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt))) - return true; - } - - return false; -} - -/* Return argument for loop preheader edge in header virtual phi if any. */ - -static tree -get_vop_from_header (class loop *loop) -{ - for (gphi_iterator gsi = gsi_start_phis (loop->header); - !gsi_end_p (gsi); gsi_next (&gsi)) - { - gphi *phi = gsi.phi (); - if (!virtual_operand_p (gimple_phi_result (phi))) - continue; - return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); - } - return NULL_TREE; -} - -/* Move the check of GUARD outside of LOOP. */ - -static void -hoist_guard (class loop *loop, edge guard) -{ - edge exit = single_exit (loop); - edge preh = loop_preheader_edge (loop); - basic_block pre_header = preh->src; - basic_block bb; - edge te, fe, e, new_edge; - gimple *stmt; - basic_block guard_bb = guard->src; - edge not_guard; - gimple_stmt_iterator gsi; - int flags = 0; - bool fix_dom_of_exit; - gcond *cond_stmt, *new_cond_stmt; - - bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest); - fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb); - gsi = gsi_last_bb (guard_bb); - stmt = gsi_stmt (gsi); - gcc_assert (gimple_code (stmt) == GIMPLE_COND); - cond_stmt = as_a <gcond *> (stmt); - extract_true_false_edges_from_block (guard_bb, &te, &fe); - /* Insert guard to PRE_HEADER. */ - if (!empty_block_p (pre_header)) - gsi = gsi_last_bb (pre_header); - else - gsi = gsi_start_bb (pre_header); - /* Create copy of COND_STMT. */ - new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt), - gimple_cond_lhs (cond_stmt), - gimple_cond_rhs (cond_stmt), - NULL_TREE, NULL_TREE); - gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT); - /* Convert COND_STMT to true/false conditional. */ - if (guard == te) - gimple_cond_make_false (cond_stmt); - else - gimple_cond_make_true (cond_stmt); - update_stmt (cond_stmt); - /* Create new loop pre-header. */ - e = split_block (pre_header, last_stmt (pre_header)); - - dump_user_location_t loc = find_loop_location (loop); - - if (dump_enabled_p ()) - { - char buffer[64]; - guard->probability.dump (buffer); - - dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc, - "Moving guard %i->%i (prob %s) to bb %i, " - "new preheader is %i\n", - guard->src->index, guard->dest->index, - buffer, e->src->index, e->dest->index); - } - - gcc_assert (loop_preheader_edge (loop)->src == e->dest); - - if (guard == fe) - { - e->flags = EDGE_TRUE_VALUE; - flags |= EDGE_FALSE_VALUE; - not_guard = te; - } - else - { - e->flags = EDGE_FALSE_VALUE; - flags |= EDGE_TRUE_VALUE; - not_guard = fe; - } - new_edge = make_edge (pre_header, exit->dest, flags); - - /* Determine the probability that we skip the loop. Assume that loop has - same average number of iterations regardless outcome of guard. */ - new_edge->probability = guard->probability; - profile_count skip_count = guard->src->count.nonzero_p () - ? guard->count ().apply_scale (pre_header->count, - guard->src->count) - : guard->count ().apply_probability (new_edge->probability); - - if (skip_count > e->count ()) - { - fprintf (dump_file, " Capping count; expect profile inconsistency\n"); - skip_count = e->count (); - } - if (dump_enabled_p ()) - { - char buffer[64]; - new_edge->probability.dump (buffer); - - dump_printf_loc (MSG_NOTE, loc, - "Estimated probability of skipping loop is %s\n", - buffer); - } - - /* Update profile after the transform: - - First decrease count of path from newly hoisted loop guard - to loop header... */ - e->probability = new_edge->probability.invert (); - e->dest->count = e->count (); - - /* ... now update profile to represent that original guard will be optimized - away ... */ - guard->probability = profile_probability::never (); - not_guard->probability = profile_probability::always (); - - /* ... finally scale everything in the loop except for guarded basic blocks - where profile does not change. */ - basic_block *body = get_loop_body (loop); - - for (unsigned int i = 0; i < loop->num_nodes; i++) - { - basic_block bb = body[i]; - if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest)) - { - if (dump_enabled_p ()) - dump_printf_loc (MSG_NOTE, loc, - "Scaling nonguarded BBs in loop: %i\n", - bb->index); - if (e->probability.initialized_p ()) - scale_bbs_frequencies (&bb, 1, e->probability); - } - } - - if (fix_dom_of_exit) - set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header); - /* Add NEW_ADGE argument for all phi in post-header block. */ - bb = exit->dest; - for (gphi_iterator gsi = gsi_start_phis (bb); - !gsi_end_p (gsi); gsi_next (&gsi)) - { - gphi *phi = gsi.phi (); - tree arg; - if (virtual_operand_p (gimple_phi_result (phi))) - { - arg = get_vop_from_header (loop); - if (arg == NULL_TREE) - /* Use exit edge argument. */ - arg = PHI_ARG_DEF_FROM_EDGE (phi, exit); - add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION); - } - else - { - /* Use exit edge argument. */ - arg = PHI_ARG_DEF_FROM_EDGE (phi, exit); - add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION); - } - } - - if (dump_enabled_p ()) - dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, - "Guard hoisted\n"); - - free (body); -} - -/* Return true if phi argument for exit edge can be used - for edge around loop. */ - -static bool -check_exit_phi (class loop *loop) -{ - edge exit = single_exit (loop); - basic_block pre_header = loop_preheader_edge (loop)->src; - - for (gphi_iterator gsi = gsi_start_phis (exit->dest); - !gsi_end_p (gsi); gsi_next (&gsi)) - { - gphi *phi = gsi.phi (); - tree arg; - gimple *def; - basic_block def_bb; - if (virtual_operand_p (gimple_phi_result (phi))) - continue; - arg = PHI_ARG_DEF_FROM_EDGE (phi, exit); - if (TREE_CODE (arg) != SSA_NAME) - continue; - def = SSA_NAME_DEF_STMT (arg); - if (!def) - continue; - def_bb = gimple_bb (def); - if (!def_bb) - continue; - if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb)) - /* Definition inside loop! */ - return false; - /* Check loop closed phi invariant. */ - if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header)) - return false; - } - return true; -} - -/* Loop unswitching pass. */ - -namespace { - -const pass_data pass_data_tree_unswitch = -{ - GIMPLE_PASS, /* type */ - "unswitch", /* name */ - OPTGROUP_LOOP, /* optinfo_flags */ - TV_TREE_LOOP_UNSWITCH, /* tv_id */ - PROP_cfg, /* properties_required */ - 0, /* properties_provided */ - 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - 0, /* todo_flags_finish */ -}; - -class pass_tree_unswitch : public gimple_opt_pass -{ -public: - pass_tree_unswitch (gcc::context *ctxt) - : gimple_opt_pass (pass_data_tree_unswitch, ctxt) - {} - - /* opt_pass methods: */ - virtual bool gate (function *) { return flag_unswitch_loops != 0; } - virtual unsigned int execute (function *); - -}; // class pass_tree_unswitch - -unsigned int -pass_tree_unswitch::execute (function *fun) -{ - if (number_of_loops (fun) <= 1) - return 0; - - return tree_ssa_unswitch_loops (); -} - -} // anon namespace - -gimple_opt_pass * -make_pass_tree_unswitch (gcc::context *ctxt) -{ - return new pass_tree_unswitch (ctxt); -} - - |