tree-ssa-loop-ch.cc File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "cfghooks.h"
#include "tree-pass.h"
#include "gimple-ssa.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "tree-into-ssa.h"
#include "cfgloop.h"
#include "tree-inline.h"
#include "tree-ssa-threadedge.h"
#include "tree-ssa-sccvn.h"
#include "tree-phinodes.h"
#include "ssa-iterators.h"
#include "value-range.h"
#include "gimple-range.h"
#include "gimple-range-path.h"
#include "gimple-pretty-print.h"
#include "cfganal.h"
#include "tree-ssa-loop-manip.h"
#include "tree-ssa-loop-niter.h"
#include "tree-scalar-evolution.h"

Include dependency graph for tree-ssa-loop-ch.cc:

Enumerations
enum	ch_decision {   ch_impossible , ch_possible , ch_possible_zero_cost , ch_win ,   ch_win_invariant_exit }

Functions
static path_range_query *	get_range_query (class loop *loop, basic_block bb, gimple_ranger &ranger)
static edge	static_loop_exit (class loop *l, basic_block bb, gimple_ranger &ranger, path_range_query *&query)
static bool	loop_static_stmt_p (class loop *loop, gimple_ranger &ranger, path_range_query *&query, gimple *stmt)
static bool	loop_invariant_op_p (class loop *loop, tree op)
static bool	loop_static_op_p (class loop *loop, tree op)
static bool	loop_combined_static_and_iv_p (class loop *loop, tree op)
static ch_decision	should_duplicate_loop_header_p (basic_block header, class loop *loop, gimple_ranger *ranger, int *limit, hash_set< edge > *invariant_exits, hash_set< edge > *static_exits)
static bool	do_while_loop_p (class loop *loop)
static void	update_profile_after_ch (class loop *loop, basic_block *region, basic_block *region_copy, unsigned n_region, hash_set< edge > *invariant_exits, hash_set< edge > *static_exits, profile_count entry_count)
gimple_opt_pass *	make_pass_ch_vect (gcc::context *ctxt)
gimple_opt_pass *	make_pass_ch (gcc::context *ctxt)

Enumeration Type Documentation

ch_decision

enum ch_decision

Decision about posibility of copying a given header.   

Enumerator
ch_impossible
ch_possible
ch_possible_zero_cost
ch_win
ch_win_invariant_exit

Function Documentation

do_while_loop_p()

static bool do_while_loop_p ( class loop * loop )

static

Checks whether LOOP is a do-while style loop.   

References boolean_false_node, boolean_true_node, dump_file, dump_flags, gimple_cond_lhs(), gimple_cond_rhs(), gsi_last_bb(), last, last_nondebug_stmt(), loop::latch, loop_exits_from_bb_p(), loop::num, safe_dyn_cast(), single_pred(), single_pred_p(), and TDF_DETAILS.

get_range_query()

static path_range_query * get_range_query ( class loop * loop, basic_block bb, gimple_ranger & ranger )

static

Loop header copying on trees.
   Copyright (C) 2004-2024 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/>.   

Return path query insteance for testing ranges of statements
in headers of LOOP contained in basic block BB.
Use RANGER instance.   

References loop::header, loop_preheader_edge(), path, ranger, and single_pred_edge().

Referenced by alloca_call_type(), assume_query::calculate_phi(), check_bounds_or_overlap(), check_nul_terminated_array(), determine_value_range(), dr_step_indicator(), dump_strlen_info(), tree_switch_conversion::bit_test_cluster::emit(), execute_fast_vrp(), expr_not_equal_to(), expr_to_aff_combination(), find_var_cmp_const(), find_what_p_points_to(), fur_source::fur_source(), strlen_pass::get_len_or_size(), get_range(), get_ref_base_and_extent(), get_size_range(), gori_on_edge(), strlen_pass::handle_integral_assign(), infer_loop_bounds_from_signedness(), insert_into_preds_of_block(), ipa_compute_jump_functions_for_edge(), iv_can_overflow_p(), loop_static_stmt_p(), maybe_diag_stxncpy_trunc(), minmax_from_comparison(), optimize_range_tests_to_bit_test(), assume_query::process_stmts(), fold_using_range::range_of_ssa_name_with_loop_info(), record_nonwrapping_iv(), refine_value_range_using_guard(), scev_var_range_cant_overflow(), set_strlen_range(), set_switch_stmt_execution_predicate(), simplify_conversion_using_ranges(), simplify_rotate(), size_must_be_zero_p(), skip_a_safe_conversion_op(), split_constant_offset(), ssa_name_has_boolean_range(), static_loop_exit(), vect_get_range_info(), and vect_recog_divmod_pattern().

loop_combined_static_and_iv_p()

static bool loop_combined_static_and_iv_p ( class loop * loop, tree op )

static

Return true if OP combines outcome of static and
loop invariant conditional.   

References flow_bb_inside_loop_p(), gcc_checking_assert, gimple_bb(), gimple_uid(), is_gimple_min_invariant(), SSA_NAME_DEF_STMT, and SSA_NAME_IS_DEFAULT_DEF.

Referenced by should_duplicate_loop_header_p().

loop_invariant_op_p()

static bool loop_invariant_op_p ( class loop * loop, tree op )

static

Return true if OP is invariant.   

References flow_bb_inside_loop_p(), gimple_bb(), gimple_uid(), is_gimple_min_invariant(), SSA_NAME_DEF_STMT, and SSA_NAME_IS_DEFAULT_DEF.

Referenced by should_duplicate_loop_header_p().

loop_static_op_p()

static bool loop_static_op_p ( class loop * loop, tree op )

static

Return true if OP combines outcome of static and
loop invariant conditional.   

References flow_bb_inside_loop_p(), gcc_checking_assert, gimple_bb(), gimple_uid(), is_gimple_min_invariant(), SSA_NAME_DEF_STMT, and SSA_NAME_IS_DEFAULT_DEF.

Referenced by should_duplicate_loop_header_p().

loop_static_stmt_p()

static bool loop_static_stmt_p ( class loop * loop, gimple_ranger & ranger, path_range_query *& query, gimple * stmt )

static

Return true if STMT is static in LOOP.  This means that its value
is constant in the first iteration.
Use RANGER and formulate query cached in QUERY.   

References get_range_query(), gimple_bb(), gimple_range_type(), r, path_range_query::range_of_stmt(), ranger, and value_range::supports_type_p().

Referenced by should_duplicate_loop_header_p().

make_pass_ch()

gimple_opt_pass * make_pass_ch

(

gcc::context *

ctxt

)

make_pass_ch_vect()

gimple_opt_pass * make_pass_ch_vect

(

gcc::context *

ctxt

)

should_duplicate_loop_header_p()

static ch_decision should_duplicate_loop_header_p ( basic_block header, class loop * loop, gimple_ranger * ranger, int * limit, hash_set< edge > * invariant_exits, hash_set< edge > * static_exits )

static

Check whether we should duplicate HEADER of LOOP.  At most *LIMIT
instructions should be duplicated, limit is decreased by the actual
amount.   

References hash_set< KeyId, Lazy, Traits >::add(), as_a(), ch_impossible, ch_possible, ch_possible_zero_cost, ch_win, ch_win_invariant_exit, dump_file, dump_flags, ECF_CONST, EDGE_COUNT, EDGE_SUCC, eni_size_weights, estimate_num_insns(), flow_bb_inside_loop_p(), FOR_EACH_EDGE, FOR_EACH_SSA_TREE_OPERAND, gcc_assert, gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_call_flags(), gimple_call_internal_p(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_inexpensive_call_p(), gimple_phi_result(), gimple_set_uid(), gimple_vuse(), gsi_end_p(), gsi_last_bb(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), header, loop::header, i, insns, is_gimple_debug(), last, loop_combined_static_and_iv_p(), loop_exit_edge_p(), loop_invariant_op_p(), loop_static_op_p(), loop_static_stmt_p(), NULL, loop::num, print_gimple_stmt(), ranger, safe_dyn_cast(), single_pred_p(), single_succ_p(), SSA_OP_USE, static_loop_exit(), static_p, TDF_DETAILS, TDF_SLIM, and virtual_operand_p().

static_loop_exit()

static edge static_loop_exit ( class loop * l, basic_block bb, gimple_ranger & ranger, path_range_query *& query )

static

Return edge that is true in the first iteration of the loop
and NULL otherwise.
Formulate corrent ranger query to RANGER.   

References extract_true_false_edges_from_block(), get_range_query(), gimple_bb(), gsi_last_bb(), last, loop_exit_edge_p(), NULL, r, range_false(), path_range_query::range_of_stmt(), range_true(), ranger, and safe_dyn_cast().

Referenced by should_duplicate_loop_header_p().

update_profile_after_ch()

static void update_profile_after_ch ( class loop * loop, basic_block * region, basic_block * region_copy, unsigned n_region, hash_set< edge > * invariant_exits, hash_set< edge > * static_exits, profile_count entry_count )

static

Update profile after header copying of LOOP.
REGION is the original (in loop) sequence, REGION_COPY is the
duplicated header (now outside of loop). N_REGION is number of
bbs duplicated.
ELIMINATED_EDGE is edge to be removed from duplicated sequence.
INVARIANT_EXITS are edges in the loop body to be elimianted
since they are loop invariants

So We expect the following:

   // region_copy_start entry will be scaled to entry_count
      if (cond1)         <- this condition will become false
                       and we update probabilities
        goto loop_exit;
      if (cond2)         <- this condition is loop invariant
        goto loop_exit;
      goto loop_header   <- this will be redirected to loop.
    // region_copy_end
  loop:
            <body>
    // region start
  loop_header:
            if (cond1)   <- we need to update probability here
         goto loop_exit;
            if (cond2)   <- and determine scaling factor here.
                       moreover cond2 is now always true
         goto loop_exit;
            else
         goto loop;
    // region end

  Adding support for more exits can be done similarly,
  but only consumer so far is tree-ssa-loop-ch and it uses only this
  to handle the common case of peeling headers which have
  conditionals known to be always true upon entry.   

References profile_probability::always(), as_a(), hash_set< KeyId, Lazy, Traits >::contains(), basic_block_def::count, EDGE_COUNT, EDGE_SUCC, gcc_assert, gcc_checking_assert, gimple_cond_make_false(), gimple_cond_make_true(), gsi_last_bb(), i, hash_set< KeyId, Lazy, Traits >::is_empty(), loop_exit_edge_p(), profile_probability::never(), profile_count::nonzero_p(), profile_count::probability_in(), hash_set< KeyId, Lazy, Traits >::remove(), set_edge_probability_and_rescale_others(), update_bb_profile_for_threading(), and update_stmt().