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, bool *canbe_neverexecuted)
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 possibility 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()

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, do_while_loop_p(), dump_file, dump_flags, gimple_cond_lhs(), gimple_cond_rhs(), gsi_last_bb(), last_nondebug_stmt(), loop::latch, loop_exits_from_bb_p(), loop::num, safe_dyn_cast(), single_pred(), single_pred_p(), and TDF_DETAILS.

Referenced by do_while_loop_p().

get_range_query()

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

static

Loop header copying on trees.
   Copyright (C) 2004-2026 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 instance for testing ranges of statements
in headers of LOOP contained in basic block BB.
Use RANGER instance.   

References get_range_query(), loop::header, loop_preheader_edge(), path_range_query::path_range_query(), and single_pred_edge().

loop_combined_static_and_iv_p()

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(), loop_combined_static_and_iv_p(), SSA_NAME_DEF_STMT, and SSA_NAME_IS_DEFAULT_DEF.

Referenced by loop_combined_static_and_iv_p(), and should_duplicate_loop_header_p().

loop_invariant_op_p()

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(), loop_invariant_op_p(), SSA_NAME_DEF_STMT, and SSA_NAME_IS_DEFAULT_DEF.

Referenced by loop_invariant_op_p(), and should_duplicate_loop_header_p().

loop_static_op_p()

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(), loop_static_op_p(), SSA_NAME_DEF_STMT, and SSA_NAME_IS_DEFAULT_DEF.

Referenced by loop_static_op_p(), and should_duplicate_loop_header_p().

loop_static_stmt_p()

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(), loop_static_stmt_p(), r, path_range_query::range_of_stmt(), and value_range::supports_type_p().

Referenced by loop_static_stmt_p(), and should_duplicate_loop_header_p().

make_pass_ch()

gimple_opt_pass * make_pass_ch

(

gcc::context *

ctxt

)

References make_pass_ch().

Referenced by make_pass_ch(), and make_pass_empty_loop().

make_pass_ch_vect()

gimple_opt_pass * make_pass_ch_vect

(

gcc::context *

ctxt

)

References make_pass_ch_vect().

Referenced by make_pass_ch_vect(), and make_pass_empty_loop().

should_duplicate_loop_header_p()

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, bool * canbe_neverexecuted )

static

Check whether we should duplicate HEADER of LOOP.  At most *LIMIT
instructions should be duplicated, limit is decreased by the actual
amount.  In the case of *CANBE_NEVEREXECUTED, if there is a exit edge
of the HEADER that is most likely never executed then consider that
as invariant and continue. Set *CANBE_NEVEREXECUTED to false otherwise.   

References hash_set< KeyId, Lazy, Traits >::add(), as_a(), basic_block_def::aux, cfun, 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(), loop::header, i, basic_block_def::index, is_gimple_debug(), 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(), probably_never_executed_edge_p(), safe_dyn_cast(), should_duplicate_loop_header_p(), single_pred_p(), single_succ_p(), SSA_OP_USE, static_loop_exit(), basic_block_def::succs, TDF_DETAILS, TDF_SLIM, and virtual_operand_p().

Referenced by should_duplicate_loop_header_p().

static_loop_exit()

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(), loop_exit_edge_p(), NULL, r, range_false(), path_range_query::range_of_stmt(), range_true(), safe_dyn_cast(), and static_loop_exit().

Referenced by should_duplicate_loop_header_p(), and static_loop_exit().

update_profile_after_ch()

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(), update_profile_after_ch(), and update_stmt().

Referenced by update_profile_after_ch().