tree-ssa-ifcombine.cc File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "cfghooks.h"
#include "tree-pass.h"
#include "memmodel.h"
#include "tm_p.h"
#include "ssa.h"
#include "tree-pretty-print.h"
#include "fold-const.h"
#include "cfganal.h"
#include "gimple-iterator.h"
#include "gimple-fold.h"
#include "gimplify-me.h"
#include "tree-cfg.h"
#include "tree-ssa.h"
#include "attribs.h"
#include "asan.h"
#include "bitmap.h"

Include dependency graph for tree-ssa-ifcombine.cc:

Data Structures
struct	ifcombine_mark_ssa_name_t

Macros
#define	LOGICAL_OP_NON_SHORT_CIRCUIT

Functions
static bool	known_succ_p (basic_block cond_bb)
static bool	recognize_if_then_else (basic_block cond_bb, basic_block *then_bb, basic_block *else_bb, bool succs_any=false)
static bool	bb_no_side_effects_p (basic_block bb)
static bool	forwarder_block_to (basic_block bb, basic_block to_bb)
static bool	same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
static tree	get_name_for_bit_test (tree candidate)
static bool	recognize_single_bit_test (gcond *cond, tree *name, tree *bit, bool inv)
static bool	recognize_bits_test (gcond *cond, tree *name, tree *bits, bool inv)
static void	update_profile_after_ifcombine (basic_block inner_cond_bb, basic_block outer_cond_bb)
static void	ifcombine_mark_ssa_name (bitmap used, tree name, basic_block outer)
static tree	ifcombine_mark_ssa_name_walk (tree *t, int *, void *data_)
static void	ifcombine_rewrite_to_defined_overflow (gimple_stmt_iterator gsi)
static bool	ifcombine_replace_cond (gcond *inner_cond, bool inner_inv, gcond *outer_cond, bool outer_inv, tree cond, bool must_canon, tree cond2)
static bool	can_combine_bbs_with_short_circuit (basic_block inner_cond_bb, tree lhs, tree rhs)
static bool	ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv, basic_block outer_cond_bb, bool outer_inv)
static bool	tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb, basic_block then_bb, basic_block else_bb, basic_block phi_pred_bb, basic_block outer_succ_bb)
static bool	tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
gimple_opt_pass *	make_pass_tree_ifcombine (gcc::context *ctxt)

Macro Definition Documentation

LOGICAL_OP_NON_SHORT_CIRCUIT

#define LOGICAL_OP_NON_SHORT_CIRCUIT

Value:

  (BRANCH_COST (optimize_function_for_speed_p (cfun), \
                false) >= 2)

Combining of if-expressions on trees.
   Copyright (C) 2007-2024 Free Software Foundation, Inc.
   Contributed by Richard Guenther <rguenther@suse.de>

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/>.   

rtl is needed only because arm back-end requires it for
BRANCH_COST.   

Referenced by ifcombine_ifandif().

Function Documentation

bb_no_side_effects_p()

static bool bb_no_side_effects_p ( basic_block bb )

static

Verify if the basic block BB does not have side-effects.  Return
true in this case, else false.   

References dyn_cast(), FOR_EACH_SSA_TREE_OPERAND, gimple_assign_lhs(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_could_trap_p(), gimple_has_side_effects(), gimple_vdef(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), integer_minus_onep(), INTEGRAL_TYPE_P, is_gimple_call(), is_gimple_debug(), ssa_name_maybe_undef_p(), SSA_OP_USE, TREE_CODE, TREE_TYPE, and TYPE_OVERFLOW_UNDEFINED.

Referenced by tree_ssa_ifcombine_bb().

can_combine_bbs_with_short_circuit()

static bool can_combine_bbs_with_short_circuit ( basic_block inner_cond_bb, tree lhs, tree rhs )

static

Returns true if inner_cond_bb contains just the condition or 1/2 statements
that define lhs or rhs with an integer conversion.  

References CONVERT_EXPR_CODE_P, gimple_assign_lhs(), gimple_assign_rhs_code(), gsi_next_nondebug(), gsi_one_before_end_p(), gsi_start_nondebug_after_labels_bb(), gsi_stmt(), i, and is_gimple_assign().

Referenced by ifcombine_ifandif().

forwarder_block_to()

static bool forwarder_block_to ( basic_block bb, basic_block to_bb )

static

Return true if BB is an empty forwarder block to TO_BB.   

References empty_block_p(), single_succ(), and single_succ_p().

Referenced by tree_ssa_ifcombine_bb().

get_name_for_bit_test()

static tree get_name_for_bit_test ( tree candidate )

static

Return the best representative SSA name for CANDIDATE which is used
in a bit test.   

References candidate(), CONVERT_EXPR_CODE_P, gimple_assign_rhs1(), gimple_assign_rhs_code(), has_single_use(), is_gimple_assign(), SSA_NAME_DEF_STMT, TREE_CODE, TREE_TYPE, and TYPE_PRECISION.

Referenced by recognize_bits_test(), and recognize_single_bit_test().

ifcombine_ifandif()

static bool ifcombine_ifandif ( basic_block inner_cond_bb, bool inner_inv, basic_block outer_cond_bb, bool outer_inv )

static

If-convert on a and pattern with a common else block.  The inner
if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
inner_inv, outer_inv indicate whether the conditions are inverted.
Returns true if the edges to the common else basic-block were merged.   

References boolean_type_node, build_int_cst(), can_combine_bbs_with_short_circuit(), dump_file, fold_build2, fold_build2_loc(), fold_convert, fold_truth_andor_for_ifcombine(), force_gimple_operand_gsi(), gimple_bb(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_location(), gsi_for_stmt(), gsi_last_bb(), GSI_SAME_STMT, HONOR_NANS(), ifcombine_replace_cond(), invert_tree_comparison(), LOGICAL_OP_NON_SHORT_CIRCUIT, maybe_fold_and_comparisons(), NULL_TREE, print_generic_expr(), recognize_bits_test(), recognize_single_bit_test(), safe_dyn_cast(), sanitize_coverage_p(), single_pred(), SSA_NAME_OCCURS_IN_ABNORMAL_PHI, tcc_comparison, TREE_CODE, TREE_CODE_CLASS, TREE_TYPE, TYPE_PRECISION, and unsigned_type_for().

Referenced by tree_ssa_ifcombine_bb_1().

ifcombine_mark_ssa_name()

static void ifcombine_mark_ssa_name ( bitmap used, tree name, basic_block outer )

static

Set NAME's bit in USED if OUTER dominates it.   

References bitmap_set_bit, CDI_DOMINATORS, dominated_by_p(), gimple_bb(), SSA_NAME_DEF_STMT, SSA_NAME_IS_DEFAULT_DEF, and SSA_NAME_VERSION.

Referenced by ifcombine_mark_ssa_name_walk(), and ifcombine_replace_cond().

ifcombine_mark_ssa_name_walk()

static tree ifcombine_mark_ssa_name_walk ( tree * t, int * , void * data_ )

static

Mark in DATA->used any SSA_NAMEs used in *t.   

References ifcombine_mark_ssa_name(), NULL, and TREE_CODE.

Referenced by ifcombine_replace_cond().

ifcombine_replace_cond()

static bool ifcombine_replace_cond ( gcond * inner_cond, bool inner_inv, gcond * outer_cond, bool outer_inv, tree cond, bool must_canon, tree cond2 )

static

Replace the conditions in INNER_COND and OUTER_COND with COND and COND2.
COND and COND2 are computed for insertion at INNER_COND, with OUTER_COND
replaced with a constant, but if there are intervening blocks, it's best to
adjust COND for insertion at OUTER_COND, placing COND2 at INNER_COND.   

References a, bitmap_bit_p, bitmap_empty_p(), bitmap_tree_view(), boolean_false_node, boolean_true_node, canonicalize_cond_expr_cond(), dyn_cast(), end(), fold_build1, FOR_EACH_PHI_ARG, FOR_EACH_SSA_TREE_OPERAND, FOR_EACH_VEC_ELT, force_gimple_operand_gsi_1(), gcc_assert, gimple_bb(), gimple_build_assign(), gimple_cond_set_condition_from_tree(), gimple_phi_arg_def(), gimple_phi_arg_location(), gimple_phi_num_args(), gimple_phi_result(), gimple_set_location(), gsi_end_p(), gsi_for_phi(), gsi_for_stmt(), gsi_insert_before(), gsi_last_bb(), gsi_move_before(), GSI_NEW_STMT, gsi_next(), gsi_prev(), GSI_SAME_STMT, gsi_start_bb(), gsi_start_phis(), gsi_stmt(), i, ifcombine_mark_ssa_name(), ifcombine_mark_ssa_name_walk(), ifcombine_rewrite_to_defined_overflow(), is_gimple_condexpr_for_cond(), NULL, remove_phi_node(), reset_flow_sensitive_info(), reset_flow_sensitive_info_in_bb(), single_pred(), SSA_NAME_VERSION, SSA_OP_DEF, SSA_OP_USE, TREE_CODE, TREE_OPERAND, TREE_TYPE, update_profile_after_ifcombine(), update_stmt(), USE_FROM_PTR, and walk_tree.

Referenced by ifcombine_ifandif().

ifcombine_rewrite_to_defined_overflow()

static void ifcombine_rewrite_to_defined_overflow ( gimple_stmt_iterator gsi )

inlinestatic

Rewrite a stmt, that presumably used to be guarded by conditions that could
avoid undefined overflow, into one that has well-defined overflow, so that
it won't invoke undefined behavior once the guarding conditions change.   

References arith_code_with_undefined_signed_overflow(), dyn_cast(), gimple_assign_lhs(), gimple_assign_rhs_code(), gsi_stmt(), INTEGRAL_TYPE_P, POINTER_TYPE_P, rewrite_to_defined_overflow(), and TREE_TYPE.

Referenced by ifcombine_replace_cond().

known_succ_p()

static bool known_succ_p ( basic_block cond_bb )

static

Return FALSE iff the COND_BB ends with a conditional whose result is not a
known constant.   

References CONSTANT_CLASS_P, gimple_cond_lhs(), gimple_cond_rhs(), gsi_last_bb(), and safe_dyn_cast().

Referenced by recognize_if_then_else(), tree_ssa_ifcombine_bb(), and update_profile_after_ifcombine().

make_pass_tree_ifcombine()

gimple_opt_pass * make_pass_tree_ifcombine

(

gcc::context *

ctxt

)

recognize_bits_test()

static bool recognize_bits_test ( gcond * cond, tree * name, tree * bits, bool inv )

static

Recognize a bit test pattern in a GIMPLE_COND and its defining
statements.  Store the name being tested in *NAME and the bits
in *BITS.  The COND_EXPR computes *NAME & *BITS.
Returns true if the pattern matched, false otherwise.   

References get_name_for_bit_test(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), integer_zerop(), is_gimple_assign(), SSA_NAME_DEF_STMT, and TREE_CODE.

Referenced by ifcombine_ifandif().

recognize_if_then_else()

static bool recognize_if_then_else ( basic_block cond_bb, basic_block * then_bb, basic_block * else_bb, bool succs_any = false )

static

This pass combines COND_EXPRs to simplify control flow.  It
currently recognizes bit tests and comparisons in chains that
represent logical and or logical or of two COND_EXPRs.

It does so by walking basic blocks in a approximate reverse
post-dominator order and trying to match CFG patterns that
represent logical and or logical or of two COND_EXPRs.
Transformations are done if the COND_EXPR conditions match
either

  1. two single bit tests X & (1 << Yn) (for logical and)

  2. two bit tests X & Yn (for logical or)

  3. two comparisons X OPn Y (for logical or)

To simplify this pass, removing basic blocks and dead code
is left to CFG cleanup and DCE.   

Recognize a if-then-else CFG pattern starting to match with the COND_BB
basic-block containing the COND_EXPR.  If !SUCCS_ANY, the condition must not
resolve to a constant for a match.  Returns true if the pattern matched,
false otherwise.  In case of a !SUCCS_ANY match, the recognized then end
else blocks are stored to *THEN_BB and *ELSE_BB.  If *THEN_BB and/or
*ELSE_BB are already set, they are required to match the then and else
basic-blocks to make the pattern match.  If SUCCS_ANY, *THEN_BB and *ELSE_BB
will not be filled in, and they will be found to match even if reversed.   

References EDGE_COUNT, EDGE_SUCC, known_succ_p(), and basic_block_def::succs.

Referenced by tree_ssa_ifcombine_bb(), and tree_ssa_ifcombine_bb_1().

recognize_single_bit_test()

static bool recognize_single_bit_test ( gcond * cond, tree * name, tree * bit, bool inv )

static

Recognize a single bit test pattern in GIMPLE_COND and its defining
statements.  Store the name being tested in *NAME and the bit
in *BIT.  The GIMPLE_COND computes *NAME & (1 << *BIT).
Returns true if the pattern matched, false otherwise.   

References build_int_cst(), CONVERT_EXPR_CODE_P, get_name_for_bit_test(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_assign_ssa_name_copy_p(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), integer_onep(), integer_pow2p(), integer_type_node, integer_zero_node, integer_zerop(), is_gimple_assign(), SSA_NAME_DEF_STMT, TREE_CODE, tree_log2(), TREE_TYPE, and TYPE_PRECISION.

Referenced by ifcombine_ifandif().

same_phi_args_p()

static bool same_phi_args_p ( basic_block bb1, basic_block bb2, basic_block dest )

static

Verify if all PHI node arguments in DEST for edges from BB1 or
BB2 to DEST are the same.  This makes the CFG merge point
free from side-effects.  Return true in this case, else false.   

References find_edge(), gsi_end_p(), gsi_next(), gsi_start_phis(), operand_equal_p(), gphi_iterator::phi(), and PHI_ARG_DEF_FROM_EDGE.

Referenced by tree_ssa_ifcombine_bb(), and tree_ssa_ifcombine_bb_1().

tree_ssa_ifcombine_bb()

static bool tree_ssa_ifcombine_bb ( basic_block inner_cond_bb )

static

Recognize a CFG pattern and dispatch to the appropriate
if-conversion helper.  We start with BB as the innermost
worker basic-block.  Returns true if a transformation was done.   

References bb_no_side_effects_p(), changed, forwarder_block_to(), known_succ_p(), NULL, recognize_if_then_else(), same_phi_args_p(), single_pred(), single_pred_p(), single_succ_p(), and tree_ssa_ifcombine_bb_1().

tree_ssa_ifcombine_bb_1()

static bool tree_ssa_ifcombine_bb_1 ( basic_block inner_cond_bb, basic_block outer_cond_bb, basic_block then_bb, basic_block else_bb, basic_block phi_pred_bb, basic_block outer_succ_bb )

static

Helper function for tree_ssa_ifcombine_bb.  Recognize a CFG pattern and
dispatch to the appropriate if-conversion helper for a particular
set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB.
PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB.
OUTER_SUCC_BB is the successor of OUTER_COND_BB on the path towards
INNER_COND_BB.   

References ifcombine_ifandif(), recognize_if_then_else(), and same_phi_args_p().

Referenced by tree_ssa_ifcombine_bb().

update_profile_after_ifcombine()

static void update_profile_after_ifcombine ( basic_block inner_cond_bb, basic_block outer_cond_bb )

static

Update profile after code in either outer_cond_bb or inner_cond_bb was
adjusted so that it has no condition.   

References profile_probability::always(), basic_block_def::count, EDGE_SUCC, profile_probability::even(), find_edge(), gcc_assert, known_succ_p(), profile_probability::never(), single_pred(), and single_pred_p().

Referenced by ifcombine_replace_cond().