#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 "gimple-pretty-print.h"
#include "diagnostic-core.h"
#include "fold-const.h"
#include "gimple-iterator.h"
#include "tree-ssa.h"
#include "tree-cfg.h"
#include "cfghooks.h"
#include "attribs.h"
#include "builtins.h"
#include "calls.h"
#include "value-query.h"
#include "cfganal.h"
#include "tree-eh.h"
#include "gimple-fold.h"
#include "gimple-predicate-analysis.h"

Include dependency graph for gimple-predicate-analysis.cc:

Macros
#define	INCLUDE_STRING

#define	DEBUG_PREDICATE_ANALYZER 1

#define	MAX_NUM_CHAINS (unsigned)param_uninit_max_num_chains

#define	MAX_CHAIN_LEN (unsigned)param_uninit_max_chain_len

Functions
static bool	pred_neg_p (const pred_info &x1, const pred_info &x2)

static bool	is_value_included_in (tree val, tree boundary, tree_code cmpc)

static std::string	format_edge_vec (const vec< edge > &ev)

static std::string	format_edge_vecs (const vec< edge > eva[], unsigned n)

static void	dump_pred_info (FILE *f, const pred_info &pred)

static void	dump_pred_chain (FILE *f, const pred_chain &chain)

static tree_code	get_cmp_code (tree_code orig_cmp_code, bool swap_cond, bool invert)

static bool	find_matching_predicate_in_rest_chains (const pred_info &pred, const pred_chain_union &preds)

static tree_code	find_var_cmp_const (pred_chain_union preds, gphi phi, gimple flag_def, tree boundary_cst, unsigned &i)

static bool	pred_equal_p (const pred_info &pred1, const pred_info &pred2)

static bool	is_neq_relop_p (const pred_info &pred)

static bool	is_neq_zero_form_p (const pred_info &pred)

static bool	pred_expr_equal_p (const pred_info &pred, tree expr)

static bool	value_sat_pred_p (tree val, tree boundary, tree_code cmpc, bool exact_p=false)

static bool	subset_of (const pred_info &pred1, const pred_info &pred2)

static bool	subset_of (const pred_chain &chain1, const pred_chain &chain2)

static void	push_to_worklist (tree op, pred_chain chain, hash_set< tree > mark_set)

static pred_info	get_pred_info_from_cmp (const gimple *cmp_assign)

static bool	is_degenerate_phi (gimple phi, pred_info pred)

static void	simple_control_dep_chain (vec< edge > &chain, basic_block from, basic_block to)

static bool	dfs_mark_dominating_region (basic_block exit_src, basic_block dom, int flag, vec< basic_block > &bbs)

static bool	compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb, vec< edge > cd_chains[], unsigned num_chains, vec< edge > &cur_cd_chain, unsigned num_calls, unsigned in_region, unsigned depth, bool *complete_p)

static bool	compute_control_dep_chain_pdom (basic_block cd_bb, const_basic_block dep_bb, basic_block target_bb, vec< edge > cd_chains[], unsigned num_chains, vec< edge > &cur_cd_chain, unsigned num_calls, unsigned in_region, unsigned depth, bool *complete_p)

static bool	compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb, vec< edge > cd_chains[], unsigned *num_chains, unsigned in_region=0)

static void	simplify_1a (pred_chain &chain)

static bool	simplify_1b (pred_chain &chain)

Macro Definition Documentation

◆ DEBUG_PREDICATE_ANALYZER

#define DEBUG_PREDICATE_ANALYZER 1

Referenced by uninit_analysis::collect_phi_def_edges(), compute_control_dep_chain(), compute_control_dep_chain_pdom(), predicate::init_from_control_deps(), uninit_analysis::init_use_preds(), and uninit_analysis::is_use_guarded().

◆ INCLUDE_STRING

#define INCLUDE_STRING

Support for simple predicate analysis.

Copyright (C) 2001-2024 Free Software Foundation, Inc.
Contributed by Xinliang David Li <davidxl@google.com>
Generalized by Martin Sebor <msebor@redhat.com>

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

◆ MAX_CHAIN_LEN

#define MAX_CHAIN_LEN (unsigned)param_uninit_max_chain_len

Referenced by compute_control_dep_chain(), compute_control_dep_chain(), and simple_control_dep_chain().

◆ MAX_NUM_CHAINS

#define MAX_NUM_CHAINS (unsigned)param_uninit_max_num_chains

In our predicate normal form we have MAX_NUM_CHAINS or predicates
and in those MAX_CHAIN_LEN (inverted) and predicates.

Referenced by compute_control_dep_chain_pdom(), uninit_analysis::init_from_phi_def(), and uninit_analysis::init_use_preds().

Function Documentation

◆ compute_control_dep_chain() [1/2]

static bool compute_control_dep_chain	(	basic_block	dom_bb,
		const_basic_block	dep_bb,
		vec< edge >	cd_chains[],
		unsigned *	num_chains,
		unsigned	in_region = 0 )

static

Wrapper around the compute_control_dep_chain worker above.  Returns
true when the collected set of chains in CD_CHAINS is complete.

References compute_control_dep_chain_pdom(), ggc_alloc(), MAX_CHAIN_LEN, NULL, and num_calls().

◆ compute_control_dep_chain() [2/2]

static bool compute_control_dep_chain	(	basic_block	dom_bb,
		const_basic_block	dep_bb,
		vec< edge >	cd_chains[],
		unsigned *	num_chains,
		vec< edge > &	cur_cd_chain,
		unsigned *	num_calls,
		unsigned	in_region,
		unsigned	depth,
		bool *	complete_p )

static

Recursively compute the control dependence chains (paths of edges)
from the dependent basic block, DEP_BB, up to the dominating basic
block, DOM_BB (the head node of a chain should be dominated by it),
storing them in the CD_CHAINS array.
CUR_CD_CHAIN is the current chain being computed.
*NUM_CHAINS is total number of chains in the CD_CHAINS array.
*NUM_CALLS is the number of recursive calls to control unbounded
recursion.
Return true if the information is successfully computed, false if
there is no control dependence or not computed.
*COMPLETE_P is set to false if we stopped walking due to limits.
In this case there might be missing chains.

References CDI_POST_DOMINATORS, compute_control_dep_chain_pdom(), DEBUG_PREDICATE_ANALYZER, dump_file, FOR_EACH_EDGE, format_edge_vec(), gcc_assert, get_immediate_dominator(), ggc_alloc(), basic_block_def::index, MAX_CHAIN_LEN, num_calls(), and single_succ_p().

Referenced by compute_control_dep_chain_pdom(), uninit_analysis::init_from_phi_def(), and uninit_analysis::init_use_preds().

◆ compute_control_dep_chain_pdom()

static bool compute_control_dep_chain_pdom	(	basic_block	cd_bb,
		const_basic_block	dep_bb,
		basic_block	target_bb,
		vec< edge >	cd_chains[],
		unsigned *	num_chains,
		vec< edge > &	cur_cd_chain,
		unsigned *	num_calls,
		unsigned	in_region,
		unsigned	depth,
		bool *	complete_p )

static

Helper for compute_control_dep_chain that walks the post-dominator
chain from CD_BB up unto TARGET_BB looking for paths to DEP_BB.

References CDI_POST_DOMINATORS, cfun, compute_control_dep_chain(), DEBUG_PREDICATE_ANALYZER, dump_file, EXIT_BLOCK_PTR_FOR_FN, format_edge_vec(), gcc_assert, get_immediate_dominator(), ggc_alloc(), MAX_NUM_CHAINS, num_calls(), single_pred_edge(), single_pred_p(), single_succ_edge(), and single_succ_p().

Referenced by compute_control_dep_chain(), and compute_control_dep_chain().

◆ dfs_mark_dominating_region()

static bool dfs_mark_dominating_region	(	basic_block	exit_src,
		basic_block	dom,
		int	flag,
		vec< basic_block > &	bbs )

static

Perform a DFS walk on predecessor edges to mark the region denoted
by the EXIT_SRC block and DOM which dominates EXIT_SRC, including DOM.
Blocks in the region are marked with FLAG and added to BBS.  BBS is
filled up to its capacity only after which the walk is terminated
and false is returned.  If the whole region was marked, true is returned.

References EDGE_COUNT, ei_edge(), ei_next(), ei_one_before_end_p(), ei_start, basic_block_def::flags, ggc_alloc(), and basic_block_def::preds.

Referenced by uninit_analysis::init_from_phi_def(), and uninit_analysis::init_use_preds().

◆ dump_pred_chain()

static void dump_pred_chain	(	FILE *	f,
		const pred_chain &	chain )

static

Dump a pred_chain to F.

References dump_pred_info(), fputc(), ggc_alloc(), and chain::length.

Referenced by predicate::dump().

◆ dump_pred_info()

static void dump_pred_info	(	FILE *	f,
		const pred_info &	pred )

static

Dump a single pred_info to F.

References pred_info::cond_code, fputc(), ggc_alloc(), pred_info::invert, op_symbol_code(), pred_info::pred_lhs, pred_info::pred_rhs, and print_generic_expr().

Referenced by dump_pred_chain(), and predicate::init_from_control_deps().

◆ find_matching_predicate_in_rest_chains()

static bool find_matching_predicate_in_rest_chains	(	const pred_info &	pred,
		const pred_chain_union &	preds )

static

Return true if PRED is common among all predicate chains in PREDS
(and therefore can be factored out).

References ggc_alloc(), i, pred_info::invert, chain::length, operand_equal_p(), pred_info::pred_lhs, and pred_info::pred_rhs.

Referenced by find_var_cmp_const().

◆ find_var_cmp_const()

static tree_code find_var_cmp_const	(	pred_chain_union	preds,
		gphi *	phi,
		gimple **	flag_def,
		tree *	boundary_cst,
		unsigned &	i )

static

Find a predicate to examine against paths of interest.  If there
is no predicate of the "FLAG_VAR CMP CONST" form, try to find one
of that's the form "FLAG_VAR CMP FLAG_VAR" with value range info.
PHI is the phi node whose incoming (interesting) paths need to be
examined.  On success, return the comparison code, set defintion
gimple of FLAG_DEF and BOUNDARY_CST.  Otherwise return ERROR_MARK.
I is the running iterator so the function can be called repeatedly
to gather all candidates.

References cfun, pred_info::cond_code, find_matching_predicate_in_rest_chains(), gcc_assert, get_cmp_code(), get_range_query(), ggc_alloc(), gimple_bb(), i, INTEGRAL_TYPE_P, pred_info::invert, is_gimple_constant(), chain::length, wi::max_value(), wi::min_value(), NULL, NULL_TREE, pred_info::pred_lhs, pred_info::pred_rhs, r, SSA_NAME_DEF_STMT, TREE_CODE, TREE_TYPE, TYPE_PRECISION, TYPE_SIGN, and wide_int_to_tree().

Referenced by uninit_analysis::overlap().

◆ format_edge_vec()

static std::string format_edge_vec ( const vec< edge > & ev )

static

Format the vector of edges EV as a string.

References ggc_alloc(), and i.

Referenced by compute_control_dep_chain(), compute_control_dep_chain_pdom(), and format_edge_vecs().

◆ format_edge_vecs()

static std::string format_edge_vecs	(	const vec< edge >	eva[],
		unsigned	n )

static

Format the first N elements of the array of vector of edges EVA as
a string.

References format_edge_vec(), ggc_alloc(), and i.

Referenced by predicate::init_from_control_deps().

◆ get_cmp_code()

static tree_code get_cmp_code	(	tree_code	orig_cmp_code,
		bool	swap_cond,
		bool	invert )

static

Return the 'normalized' conditional code with operand swapping
and condition inversion controlled by SWAP_COND and INVERT.

References ggc_alloc(), invert_tree_comparison(), and swap_tree_comparison().

Referenced by find_var_cmp_const().

◆ get_pred_info_from_cmp()

static pred_info get_pred_info_from_cmp ( const gimple * cmp_assign )

static

Return a pred_info for a gimple assignment CMP_ASSIGN with comparison
rhs.

References pred_info::cond_code, ggc_alloc(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), pred_info::invert, pred_info::pred_lhs, and pred_info::pred_rhs.

Referenced by is_degenerate_phi(), predicate::normalize(), and predicate::normalize().

◆ is_degenerate_phi()

static bool is_degenerate_phi	(	gimple *	phi,
		pred_info *	pred )

static

If PHI is a degenerate phi with all operands having the same value (relop)
update *PRED to that value and return true.  Otherwise return false.

References get_pred_info_from_cmp(), ggc_alloc(), gimple_assign_rhs_code(), gimple_phi_arg_def(), gimple_phi_num_args(), i, pred_equal_p(), SSA_NAME_DEF_STMT, tcc_comparison, TREE_CODE, and TREE_CODE_CLASS.

Referenced by predicate::normalize().

◆ is_neq_relop_p()

static bool is_neq_relop_p ( const pred_info & pred )

inlinestatic

Return true if PRED tests inequality (i.e., X != Y).

References pred_info::cond_code, ggc_alloc(), and pred_info::invert.

Referenced by is_neq_zero_form_p().

◆ is_neq_zero_form_p()

static bool is_neq_zero_form_p ( const pred_info & pred )

inlinestatic

Returns true if PRED is of the form X != 0.

References integer_zerop(), is_neq_relop_p(), pred_info::pred_lhs, pred_info::pred_rhs, and TREE_CODE.

Referenced by predicate::normalize(), predicate::normalize(), pred_expr_equal_p(), simplify_1a(), and predicate::simplify_4().

◆ is_value_included_in()

static bool is_value_included_in	(	tree	val,
		tree	boundary,
		tree_code	cmpc )

static

Return whether the condition (VAL CMPC BOUNDARY) is true.

References gcc_assert, ggc_alloc(), invert_tree_comparison(), TREE_CODE, tree_int_cst_equal(), tree_int_cst_le(), and tree_int_cst_lt().

Referenced by uninit_analysis::prune_phi_opnds(), and value_sat_pred_p().

◆ pred_equal_p()

static bool pred_equal_p	(	const pred_info &	pred1,
		const pred_info &	pred2 )

inlinestatic

Return true if two predicates PRED1 and X2 are equivalent.  Assume
the expressions have already properly re-associated.

References ggc_alloc(), invert_tree_comparison(), operand_equal_p(), tcc_comparison, and TREE_CODE_CLASS.

Referenced by is_degenerate_phi(), predicate::simplify_2(), and subset_of().

◆ pred_expr_equal_p()

static bool pred_expr_equal_p	(	const pred_info &	pred,
		tree	expr )

inlinestatic

Return true if PRED is equivalent to X != 0.

References is_neq_zero_form_p(), operand_equal_p(), and pred_info::pred_lhs.

Referenced by simplify_1a(), and predicate::simplify_4().

◆ pred_neg_p()

static bool pred_neg_p	(	const pred_info &	x1,
		const pred_info &	x2 )

inlinestatic

Return true if X1 is the negation of X2.

References ggc_alloc(), invert_tree_comparison(), and operand_equal_p().

Referenced by predicate::simplify_2(), and predicate::simplify_3().

◆ push_to_worklist()

static void push_to_worklist	(	tree	op,
		pred_chain *	chain,
		hash_set< tree > *	mark_set )

static

Create a predicate of the form OP != 0 and push it the work list CHAIN.

References ggc_alloc(), and integer_zero_node.

Referenced by predicate::normalize().

◆ simple_control_dep_chain()

static void simple_control_dep_chain	(	vec< edge > &	chain,
		basic_block	from,
		basic_block	to )

static

If compute_control_dep_chain bailed out due to limits this routine
tries to build a partial sparse path using dominators.  Returns
path edges whose predicates are always true when reaching E.

References CDI_DOMINATORS, dominated_by_p(), gcc_assert, get_immediate_dominator(), ggc_alloc(), chain::length, MAX_CHAIN_LEN, single_pred_edge(), single_pred_p(), and single_succ_p().

Referenced by uninit_analysis::init_use_preds().

◆ simplify_1a()

static void simplify_1a ( pred_chain & chain )

static

Implemented simplifications:

1a) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1b) [!](X rel y) AND [!](X rel y') where y == y' or both constant
    can possibly be simplified
2) (X AND Y) OR (!X AND Y) is equivalent to Y;
3) X OR (!X AND Y) is equivalent to (X OR Y);
4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
   (x != 0 AND y != 0)
5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
   (X AND Y) OR Z

PREDS is the predicate chains, and N is the number of chains.

Implement rule 1a above.  PREDS is the AND predicate to simplify
in place.

References ggc_alloc(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), i, is_neq_zero_form_p(), chain::length, NULL, pred_expr_equal_p(), SSA_NAME_DEF_STMT, and vNULL.

Referenced by predicate::simplify().

◆ simplify_1b()

static bool simplify_1b ( pred_chain & chain )

static

Implement rule 1b above.  PREDS is the AND predicate to simplify
in place.  Returns true if CHAIN simplifies to true or false.

References boolean_type_node, COMPARISON_CLASS_P, CONSTANT_CLASS_P, ggc_alloc(), i, integer_truep(), integer_zerop(), invert_tree_comparison(), chain::length, maybe_fold_and_comparisons(), NULL, operand_equal_p(), TREE_CODE, and TREE_OPERAND.

Referenced by predicate::simplify().

◆ subset_of() [1/2]

static bool subset_of	(	const pred_chain &	chain1,
		const pred_chain &	chain2 )

static

Return true if the domain of CHAIN1 is a subset of that of CHAIN2.
Return false if it cannot be proven so.

References ggc_alloc(), i1, i2, and subset_of().

◆ subset_of() [2/2]

static bool subset_of	(	const pred_info &	pred1,
		const pred_info &	pred2 )

static

Return true if the domain of single predicate expression PRED1
is a subset of that of PRED2, and false if it cannot be proved.

References ggc_alloc(), invert_tree_comparison(), operand_equal_p(), pred_equal_p(), TREE_CODE, and value_sat_pred_p().

Referenced by predicate::includes(), and subset_of().

◆ value_sat_pred_p()

static bool value_sat_pred_p	(	tree	val,
		tree	boundary,
		tree_code	cmpc,
		bool	exact_p = false )

static

Return true if VAL satisfies (x CMPC BOUNDARY) predicate.  CMPC can
be either one of the range comparison codes ({GE,LT,EQ,NE}_EXPR and
the like), or BIT_AND_EXPR.  EXACT_P is only meaningful for the latter.
Modify the question from VAL & BOUNDARY != 0 to VAL & BOUNDARY == VAL.
For other values of CMPC, EXACT_P is ignored.

References ggc_alloc(), is_value_included_in(), wi::ne_p(), and wi::to_widest().

Referenced by subset_of().

Macros

Functions

Macro Definition Documentation

◆ DEBUG_PREDICATE_ANALYZER

◆ INCLUDE_STRING

◆ MAX_CHAIN_LEN

◆ MAX_NUM_CHAINS

Function Documentation

◆ compute_control_dep_chain() [1/2]

◆ compute_control_dep_chain() [2/2]

◆ compute_control_dep_chain_pdom()

◆ dfs_mark_dominating_region()

◆ dump_pred_chain()

◆ dump_pred_info()

◆ find_matching_predicate_in_rest_chains()

◆ find_var_cmp_const()

◆ format_edge_vec()

◆ format_edge_vecs()

◆ get_cmp_code()

◆ get_pred_info_from_cmp()

◆ is_degenerate_phi()

◆ is_neq_relop_p()

◆ is_neq_zero_form_p()

◆ is_value_included_in()

◆ pred_equal_p()

◆ pred_expr_equal_p()

◆ pred_neg_p()

◆ push_to_worklist()

◆ simple_control_dep_chain()

◆ simplify_1a()

◆ simplify_1b()

◆ subset_of() [1/2]

◆ subset_of() [2/2]

◆ value_sat_pred_p()