[TCWG CI] Regression caused by gcc: Factor predidacte analysis out of tree-ssa-uninit.c into its own module.: commit 94c12ffac234b29a702aa7b6730f2678265857c8 Author: Martin Sebor msebor@redhat.com
Factor predidacte analysis out of tree-ssa-uninit.c into its own module.
Results regressed to # reset_artifacts: -10 # build_abe binutils: -9 # build_abe stage1: -5 # build_abe qemu: -2 # linux_n_obj: 6240 # First few build errors in logs:
from # reset_artifacts: -10 # build_abe binutils: -9 # build_abe stage1: -5 # build_abe qemu: -2 # linux_n_obj: 6999 # linux build successful: all # linux boot successful: boot
THIS IS THE END OF INTERESTING STUFF. BELOW ARE LINKS TO BUILDS, REPRODUCTION INSTRUCTIONS, AND THE RAW COMMIT.
This commit has regressed these CI configurations: - tcwg_kernel/gnu-master-arm-mainline-defconfig
First_bad build: https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-def... Last_good build: https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-def... Baseline build: https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-def... Even more details: https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-def...
Reproduce builds: <cut> mkdir investigate-gcc-94c12ffac234b29a702aa7b6730f2678265857c8 cd investigate-gcc-94c12ffac234b29a702aa7b6730f2678265857c8
# Fetch scripts git clone https://git.linaro.org/toolchain/jenkins-scripts
# Fetch manifests and test.sh script mkdir -p artifacts/manifests curl -o artifacts/manifests/build-baseline.sh https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-def... --fail curl -o artifacts/manifests/build-parameters.sh https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-def... --fail curl -o artifacts/test.sh https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-def... --fail chmod +x artifacts/test.sh
# Reproduce the baseline build (build all pre-requisites) ./jenkins-scripts/tcwg_kernel-build.sh @@ artifacts/manifests/build-baseline.sh
# Save baseline build state (which is then restored in artifacts/test.sh) mkdir -p ./bisect rsync -a --del --delete-excluded --exclude /bisect/ --exclude /artifacts/ --exclude /gcc/ ./ ./bisect/baseline/
cd gcc
# Reproduce first_bad build git checkout --detach 94c12ffac234b29a702aa7b6730f2678265857c8 ../artifacts/test.sh
# Reproduce last_good build git checkout --detach 51166eb2c534692c3c7779def24f83c8c3811b98 ../artifacts/test.sh
cd .. </cut>
Full commit (up to 1000 lines): <cut> commit 94c12ffac234b29a702aa7b6730f2678265857c8 Author: Martin Sebor msebor@redhat.com Date: Fri Sep 17 15:39:13 2021 -0600
Factor predidacte analysis out of tree-ssa-uninit.c into its own module.
gcc/ChangeLog:
* Makefile.in (OBJS): Add gimple-predicate-analysis.o. * tree-ssa-uninit.c (max_phi_args): Move to gimple-predicate-analysis. (MASK_SET_BIT, MASK_TEST_BIT, MASK_EMPTY): Same. (check_defs): Add comment. (can_skip_redundant_opnd): Update comment. (compute_uninit_opnds_pos): Adjust to namespace change. (find_pdom): Move to gimple-predicate-analysis.cc. (find_dom): Same. (struct uninit_undef_val_t): New. (is_non_loop_exit_postdominating): Move to gimple-predicate-analysis.cc. (find_control_equiv_block): Same. (MAX_NUM_CHAINS, MAX_CHAIN_LEN, MAX_POSTDOM_CHECK): Same. (MAX_SWITCH_CASES): Same. (compute_control_dep_chain): Same. (find_uninit_use): Use predicate analyzer. (struct pred_info): Move to gimple-predicate-analysis. (convert_control_dep_chain_into_preds): Same. (find_predicates): Same. (collect_phi_def_edges): Same. (warn_uninitialized_phi): Use predicate analyzer. (find_def_preds): Move to gimple-predicate-analysis. (dump_pred_info): Same. (dump_pred_chain): Same. (dump_predicates): Same. (destroy_predicate_vecs): Remove. (execute_late_warn_uninitialized): New. (get_cmp_code): Move to gimple-predicate-analysis. (is_value_included_in): Same. (value_sat_pred_p): Same. (find_matching_predicate_in_rest_chains): Same. (is_use_properly_guarded): Same. (prune_uninit_phi_opnds): Same. (find_var_cmp_const): Same. (use_pred_not_overlap_with_undef_path_pred): Same. (pred_equal_p): Same. (is_neq_relop_p): Same. (is_neq_zero_form_p): Same. (pred_expr_equal_p): Same. (is_pred_expr_subset_of): Same. (is_pred_chain_subset_of): Same. (is_included_in): Same. (is_superset_of): Same. (pred_neg_p): Same. (simplify_pred): Same. (simplify_preds_2): Same. (simplify_preds_3): Same. (simplify_preds_4): Same. (simplify_preds): Same. (push_pred): Same. (push_to_worklist): Same. (get_pred_info_from_cmp): Same. (is_degenerated_phi): Same. (normalize_one_pred_1): Same. (normalize_one_pred): Same. (normalize_one_pred_chain): Same. (normalize_preds): Same. (can_one_predicate_be_invalidated_p): Same. (can_chain_union_be_invalidated_p): Same. (uninit_uses_cannot_happen): Same. (pass_late_warn_uninitialized::execute): Define. * gimple-predicate-analysis.cc: New file. * gimple-predicate-analysis.h: New file. --- gcc/Makefile.in | 1 + gcc/gimple-predicate-analysis.cc | 2400 +++++++++++++++++++++++++++++++++++++ gcc/gimple-predicate-analysis.h | 158 +++ gcc/tree-ssa-uninit.c | 2431 +++----------------------------------- 4 files changed, 2741 insertions(+), 2249 deletions(-)
diff --git a/gcc/Makefile.in b/gcc/Makefile.in index b8229adf580..f36ffa4740b 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1394,6 +1394,7 @@ OBJS = \ gimple-loop-jam.o \ gimple-loop-versioning.o \ gimple-low.o \ + gimple-predicate-analysis.o \ gimple-pretty-print.o \ gimple-range.o \ gimple-range-cache.o \ diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc new file mode 100644 index 00000000000..3404f2d630a --- /dev/null +++ b/gcc/gimple-predicate-analysis.cc @@ -0,0 +1,2400 @@ +/* Support for simple predicate analysis. + + Copyright (C) 2001-2021 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/. */ + +#define INCLUDE_STRING +#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 "gimple-predicate-analysis.h" + +#define DEBUG_PREDICATE_ANALYZER 1 + +/* Find the immediate postdominator of the specified basic block BB. */ + +static inline basic_block +find_pdom (basic_block bb) +{ + basic_block exit_bb = EXIT_BLOCK_PTR_FOR_FN (cfun); + if (bb == exit_bb) + return exit_bb; + + if (basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, bb)) + return pdom; + + return exit_bb; +} + +/* Find the immediate dominator of the specified basic block BB. */ + +static inline basic_block +find_dom (basic_block bb) +{ + basic_block entry_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun); + if (bb == entry_bb) + return entry_bb; + + if (basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb)) + return dom; + + return entry_bb; +} + +/* Return true if BB1 is postdominating BB2 and BB1 is not a loop exit + bb. The loop exit bb check is simple and does not cover all cases. */ + +static bool +is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2) +{ + if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1)) + return false; + + if (single_pred_p (bb1) && !single_succ_p (bb2)) + return false; + + return true; +} + +/* Find BB's closest postdominator that is its control equivalent (i.e., + that's controlled by the same predicate). */ + +static inline basic_block +find_control_equiv_block (basic_block bb) +{ + basic_block pdom = find_pdom (bb); + + /* Skip the postdominating bb that is also a loop exit. */ + if (!is_non_loop_exit_postdominating (pdom, bb)) + return NULL; + + /* If the postdominator is dominated by BB, return it. */ + if (dominated_by_p (CDI_DOMINATORS, pdom, bb)) + return pdom; + + return NULL; +} + +/* Return true if X1 is the negation of X2. */ + +static inline bool +pred_neg_p (const pred_info &x1, const pred_info &x2) +{ + if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0) + || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0)) + return false; + + tree_code c1 = x1.cond_code, c2; + if (x1.invert == x2.invert) + c2 = invert_tree_comparison (x2.cond_code, false); + else + c2 = x2.cond_code; + + return c1 == c2; +} + +/* Return whether the condition (VAL CMPC BOUNDARY) is true. */ + +static bool +is_value_included_in (tree val, tree boundary, tree_code cmpc) +{ + /* Only handle integer constant here. */ + if (TREE_CODE (val) != INTEGER_CST || TREE_CODE (boundary) != INTEGER_CST) + return true; + + bool inverted = false; + if (cmpc == GE_EXPR || cmpc == GT_EXPR || cmpc == NE_EXPR) + { + cmpc = invert_tree_comparison (cmpc, false); + inverted = true; + } + + bool result; + if (cmpc == EQ_EXPR) + result = tree_int_cst_equal (val, boundary); + else if (cmpc == LT_EXPR) + result = tree_int_cst_lt (val, boundary); + else + { + gcc_assert (cmpc == LE_EXPR); + result = tree_int_cst_le (val, boundary); + } + + if (inverted) + result ^= 1; + + return result; +} + +/* Format the vector of edges EV as a string. */ + +static std::string +format_edge_vec (const vec<edge> &ev) +{ + std::string str; + + unsigned n = ev.length (); + for (unsigned i = 0; i < n; ++i) + { + char es[32]; + const_edge e = ev[i]; + sprintf (es, "%u", e->src->index); + str += es; + if (i + 1 < n) + str += " -> "; + } + return str; +} + +/* Format the first N elements of the array of vector of edges EVA as + a string. */ + +static std::string +format_edge_vecs (const vec<edge> eva[], unsigned n) +{ + std::string str; + + for (unsigned i = 0; i != n; ++i) + { + str += '{'; + str += format_edge_vec (eva[i]); + str += '}'; + if (i + 1 < n) + str += ", "; + } + return str; +} + +/* Dump a single pred_info to DUMP_FILE. */ + +static void +dump_pred_info (const pred_info &pred) +{ + if (pred.invert) + fprintf (dump_file, "NOT ("); + print_generic_expr (dump_file, pred.pred_lhs); + fprintf (dump_file, " %s ", op_symbol_code (pred.cond_code)); + print_generic_expr (dump_file, pred.pred_rhs); + if (pred.invert) + fputc (')', dump_file); +} + +/* Dump a pred_chain to DUMP_FILE. */ + +static void +dump_pred_chain (const pred_chain &chain) +{ + unsigned np = chain.length (); + if (np > 1) + fprintf (dump_file, "AND ("); + + for (unsigned j = 0; j < np; j++) + { + dump_pred_info (chain[j]); + if (j < np - 1) + fprintf (dump_file, ", "); + else if (j > 0) + fputc (')', dump_file); + } +} + +/* Dump the predicate chain PREDS for STMT, prefixed by MSG. */ + +static void +dump_predicates (gimple *stmt, const pred_chain_union &preds, const char *msg) +{ + fprintf (dump_file, "%s", msg); + if (stmt) + { + print_gimple_stmt (dump_file, stmt, 0); + fprintf (dump_file, "is guarded by:\n"); + } + + unsigned np = preds.length (); + if (np > 1) + fprintf (dump_file, "OR ("); + for (unsigned i = 0; i < np; i++) + { + dump_pred_chain (preds[i]); + if (i < np - 1) + fprintf (dump_file, ", "); + else if (i > 0) + fputc (')', dump_file); + } + fputc ('\n', dump_file); +} + +/* Dump the first NCHAINS elements of the DEP_CHAINS array into DUMP_FILE. */ + +static void +dump_dep_chains (const auto_vec<edge> dep_chains[], unsigned nchains) +{ + if (!dump_file) + return; + + for (unsigned i = 0; i != nchains; ++i) + { + const auto_vec<edge> &v = dep_chains[i]; + unsigned n = v.length (); + for (unsigned j = 0; j != n; ++j) + { + fprintf (dump_file, "%u", v[j]->src->index); + if (j + 1 < n) + fprintf (dump_file, " -> "); + } + fputc ('\n', dump_file); + } +} + +/* Return the 'normalized' conditional code with operand swapping + and condition inversion controlled by SWAP_COND and INVERT. */ + +static tree_code +get_cmp_code (tree_code orig_cmp_code, bool swap_cond, bool invert) +{ + tree_code tc = orig_cmp_code; + + if (swap_cond) + tc = swap_tree_comparison (orig_cmp_code); + if (invert) + tc = invert_tree_comparison (tc, false); + + switch (tc) + { + case LT_EXPR: + case LE_EXPR: + case GT_EXPR: + case GE_EXPR: + case EQ_EXPR: + case NE_EXPR: + break; + default: + return ERROR_MARK; + } + return tc; +} + +/* Return true if PRED is common among all predicate chains in PREDS + (and therefore can be factored out). */ + +static bool +find_matching_predicate_in_rest_chains (const pred_info &pred, + const pred_chain_union &preds) +{ + /* Trival case. */ + if (preds.length () == 1) + return true; + + for (unsigned i = 1; i < preds.length (); i++) + { + bool found = false; + const pred_chain &chain = preds[i]; + unsigned n = chain.length (); + for (unsigned j = 0; j < n; j++) + { + const pred_info &pred2 = chain[j]; + /* Can relax the condition comparison to not use address + comparison. However, the most common case is that + multiple control dependent paths share a common path + prefix, so address comparison should be ok. */ + if (operand_equal_p (pred2.pred_lhs, pred.pred_lhs, 0) + && operand_equal_p (pred2.pred_rhs, pred.pred_rhs, 0) + && pred2.invert == pred.invert) + { + found = true; + break; + } + } + if (!found) + return false; + } + return true; +} + +/* 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. */ + +static tree_code +find_var_cmp_const (pred_chain_union preds, gphi *phi, gimple **flag_def, + tree *boundary_cst) +{ + tree_code vrinfo_code = ERROR_MARK; + gimple *vrinfo_def = NULL; + tree vrinfo_cst = NULL; + + gcc_assert (preds.length () > 0); + pred_chain chain = preds[0]; + for (unsigned i = 0; i < chain.length (); i++) + { + bool use_vrinfo_p = false; + const pred_info &pred = chain[i]; + tree cond_lhs = pred.pred_lhs; + tree cond_rhs = pred.pred_rhs; + if (cond_lhs == NULL_TREE || cond_rhs == NULL_TREE) + continue; + + tree_code code = get_cmp_code (pred.cond_code, false, pred.invert); + if (code == ERROR_MARK) + continue; + + /* Convert to the canonical form SSA_NAME CMP CONSTANT. */ + if (TREE_CODE (cond_lhs) == SSA_NAME + && is_gimple_constant (cond_rhs)) + ; + else if (TREE_CODE (cond_rhs) == SSA_NAME + && is_gimple_constant (cond_lhs)) + { + std::swap (cond_lhs, cond_rhs); + if ((code = get_cmp_code (code, true, false)) == ERROR_MARK) + continue; + } + /* Check if we can take advantage of FLAG_VAR COMP FLAG_VAR predicate + with value range info. Note only first of such case is handled. */ + else if (vrinfo_code == ERROR_MARK + && TREE_CODE (cond_lhs) == SSA_NAME + && TREE_CODE (cond_rhs) == SSA_NAME) + { + gimple* lhs_def = SSA_NAME_DEF_STMT (cond_lhs); + if (!lhs_def || gimple_code (lhs_def) != GIMPLE_PHI + || gimple_bb (lhs_def) != gimple_bb (phi)) + { + std::swap (cond_lhs, cond_rhs); + if ((code = get_cmp_code (code, true, false)) == ERROR_MARK) + continue; + } + + /* Check value range info of rhs, do following transforms: + flag_var < [min, max] -> flag_var < max + flag_var > [min, max] -> flag_var > min + + We can also transform LE_EXPR/GE_EXPR to LT_EXPR/GT_EXPR: + flag_var <= [min, max] -> flag_var < [min, max+1] + flag_var >= [min, max] -> flag_var > [min-1, max] + if no overflow/wrap. */ + tree type = TREE_TYPE (cond_lhs); + value_range r; + if (!INTEGRAL_TYPE_P (type) + || !get_range_query (cfun)->range_of_expr (r, cond_rhs) + || r.kind () != VR_RANGE) + continue; + + wide_int min = r.lower_bound (); + wide_int max = r.upper_bound (); + if (code == LE_EXPR + && max != wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type))) + { + code = LT_EXPR; + max = max + 1; + } + if (code == GE_EXPR + && min != wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type))) + { + code = GT_EXPR; + min = min - 1; + } + if (code == LT_EXPR) + cond_rhs = wide_int_to_tree (type, max); + else if (code == GT_EXPR) + cond_rhs = wide_int_to_tree (type, min); + else + continue; + + use_vrinfo_p = true; + } + else + continue; + + if ((*flag_def = SSA_NAME_DEF_STMT (cond_lhs)) == NULL) + continue; + + if (gimple_code (*flag_def) != GIMPLE_PHI + || gimple_bb (*flag_def) != gimple_bb (phi) + || !find_matching_predicate_in_rest_chains (pred, preds)) + continue; + + /* Return if any "flag_var comp const" predicate is found. */ + if (!use_vrinfo_p) + { + *boundary_cst = cond_rhs; + return code; + } + /* Record if any "flag_var comp flag_var[vinfo]" predicate is found. */ + else if (vrinfo_code == ERROR_MARK) + { + vrinfo_code = code; + vrinfo_def = *flag_def; + vrinfo_cst = cond_rhs; + } + } + /* Return the "flag_var cmp flag_var[vinfo]" predicate we found. */ + if (vrinfo_code != ERROR_MARK) + { + *flag_def = vrinfo_def; + *boundary_cst = vrinfo_cst; + } + return vrinfo_code; +} + +/* Return true if all interesting opnds are pruned, false otherwise. + PHI is the phi node with interesting operands, OPNDS is the bitmap + of the interesting operand positions, FLAG_DEF is the statement + defining the flag guarding the use of the PHI output, BOUNDARY_CST + is the const value used in the predicate associated with the flag, + CMP_CODE is the comparison code used in the predicate, VISITED_PHIS + is the pointer set of phis visited, and VISITED_FLAG_PHIS is + the pointer to the pointer set of flag definitions that are also + phis. + + Example scenario: + + BB1: + flag_1 = phi <0, 1> // (1) + var_1 = phi <undef, some_val> + + + BB2: + flag_2 = phi <0, flag_1, flag_1> // (2) + var_2 = phi <undef, var_1, var_1> + if (flag_2 == 1) + goto BB3; + + BB3: + use of var_2 // (3) + + Because some flag arg in (1) is not constant, if we do not look into + the flag phis recursively, it is conservatively treated as unknown and + var_1 is thought to flow into use at (3). Since var_1 is potentially + uninitialized a false warning will be emitted. + Checking recursively into (1), the compiler can find out that only + some_val (which is defined) can flow into (3) which is OK. */ + +static bool +prune_phi_opnds (gphi *phi, unsigned opnds, gphi *flag_def, + tree boundary_cst, tree_code cmp_code, + predicate::func_t &eval, + hash_set<gphi *> *visited_phis, + bitmap *visited_flag_phis) +{ + /* The Boolean predicate guarding the PHI definition. Initialized + lazily from PHI in the first call to is_use_guarded() and cached + for subsequent iterations. */ + predicate def_preds (eval); + + unsigned n = MIN (eval.max_phi_args, gimple_phi_num_args (flag_def)); + for (unsigned i = 0; i < n; i++) + { + if (!MASK_TEST_BIT (opnds, i)) + continue; + + tree flag_arg = gimple_phi_arg_def (flag_def, i); + if (!is_gimple_constant (flag_arg)) + { + if (TREE_CODE (flag_arg) != SSA_NAME) + return false; + + gphi *flag_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (flag_arg)); + if (!flag_arg_def) + return false; + + tree phi_arg = gimple_phi_arg_def (phi, i); + if (TREE_CODE (phi_arg) != SSA_NAME) + return false; + + gphi *phi_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (phi_arg)); + if (!phi_arg_def) + return false; + + if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def)) + return false; + + if (!*visited_flag_phis) + *visited_flag_phis = BITMAP_ALLOC (NULL); + + tree phi_result = gimple_phi_result (flag_arg_def); + if (bitmap_bit_p (*visited_flag_phis, SSA_NAME_VERSION (phi_result))) + return false; + + bitmap_set_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result)); + + /* Now recursively try to prune the interesting phi args. */ + unsigned opnds_arg_phi = eval.phi_arg_set (phi_arg_def); + if (!prune_phi_opnds (phi_arg_def, opnds_arg_phi, flag_arg_def, + boundary_cst, cmp_code, eval, visited_phis, + visited_flag_phis)) + return false; + + bitmap_clear_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result)); + continue; + } + + /* Now check if the constant is in the guarded range. */ + if (is_value_included_in (flag_arg, boundary_cst, cmp_code)) + { + /* Now that we know that this undefined edge is not pruned. + If the operand is defined by another phi, we can further + prune the incoming edges of that phi by checking + the predicates of this operands. */ + + tree opnd = gimple_phi_arg_def (phi, i); + gimple *opnd_def = SSA_NAME_DEF_STMT (opnd); + if (gphi *opnd_def_phi = dyn_cast <gphi *> (opnd_def)) + { + unsigned opnds2 = eval.phi_arg_set (opnd_def_phi); + if (!MASK_EMPTY (opnds2)) + { + edge opnd_edge = gimple_phi_arg_edge (phi, i); + if (def_preds.is_use_guarded (phi, opnd_edge->src, + opnd_def_phi, opnds2, + visited_phis)) + return false; + } + } + else + return false; + } + } + + return true; +} + +/* Recursively compute the set PHI's incoming edges with "uninteresting" + operands of a phi chain, i.e., those for which EVAL returns false. + CD_ROOT is the control dependence root from which edges are collected + up the CFG nodes that it's dominated by. *EDGES holds the result, and + VISITED is used for detecting cycles. */ + +static void +collect_phi_def_edges (gphi *phi, basic_block cd_root, auto_vec<edge> *edges, + predicate::func_t &eval, hash_set<gimple *> *visited) +{ + if (visited->elements () == 0 + && DEBUG_PREDICATE_ANALYZER + && dump_file) + { + fprintf (dump_file, "%s for cd_root %u and ", + __func__, cd_root->index); + print_gimple_stmt (dump_file, phi, 0); + + } + + if (visited->add (phi)) + return; + + unsigned n = gimple_phi_num_args (phi); + for (unsigned i = 0; i < n; i++) + { + edge opnd_edge = gimple_phi_arg_edge (phi, i); + tree opnd = gimple_phi_arg_def (phi, i); + + if (TREE_CODE (opnd) == SSA_NAME) + { + gimple *def = SSA_NAME_DEF_STMT (opnd); + + if (gimple_code (def) == GIMPLE_PHI + && dominated_by_p (CDI_DOMINATORS, gimple_bb (def), cd_root)) + collect_phi_def_edges (as_a<gphi *> (def), cd_root, edges, eval, + visited); + else if (!eval (opnd)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, + "\tFound def edge %i -> %i for cd_root %i " + "and operand %u of: ", + opnd_edge->src->index, opnd_edge->dest->index, + cd_root->index, i); + print_gimple_stmt (dump_file, phi, 0); + } + edges->safe_push (opnd_edge); + } + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, + "\tFound def edge %i -> %i for cd_root %i " + "and operand %u of: ", + opnd_edge->src->index, opnd_edge->dest->index, + cd_root->index, i); + print_gimple_stmt (dump_file, phi, 0); + } + + if (!eval (opnd)) + edges->safe_push (opnd_edge); + } + } +} + +/* Return an expression corresponding to the predicate PRED. */ + +static tree +build_pred_expr (const pred_info &pred) +{ + tree_code cond_code = pred.cond_code; + tree lhs = pred.pred_lhs; + tree rhs = pred.pred_rhs; + + if (pred.invert) + cond_code = invert_tree_comparison (cond_code, false); + + return build2 (cond_code, TREE_TYPE (lhs), lhs, rhs); +} + +/* Return an expression corresponding to PREDS. */ + +static tree +build_pred_expr (const pred_chain_union &preds, bool invert = false) +{ + tree_code code = invert ? TRUTH_AND_EXPR : TRUTH_OR_EXPR; + tree_code subcode = invert ? TRUTH_OR_EXPR : TRUTH_AND_EXPR; + + tree expr = NULL_TREE; + for (unsigned i = 0; i != preds.length (); ++i) + { + tree subexpr = NULL_TREE; + for (unsigned j = 0; j != preds[i].length (); ++j) + { + const pred_info &pi = preds[i][j]; + tree cond = build_pred_expr (pi); + if (invert) + cond = invert_truthvalue (cond); + subexpr = subexpr ? build2 (subcode, boolean_type_node, + subexpr, cond) : cond; + } + if (expr) + expr = build2 (code, boolean_type_node, expr, subexpr); + else + expr = subexpr; + } + + return expr; +} + +/* Return a bitset of all PHI arguments or zero if there are too many. */ + +unsigned +predicate::func_t::phi_arg_set (gphi *phi) +{ + unsigned n = gimple_phi_num_args (phi); + + if (max_phi_args < n) + return 0; + + /* Set the least significant N bits. */ + return (1U << n) - 1; +} + +/* Determine if the predicate set of the use does not overlap with that + of the interesting paths. The most common senario of guarded use is + in Example 1: + Example 1: + if (some_cond) + { + x = ...; // set x to valid + flag = true; + } + + ... some code ... + + if (flag) + use (x); // use when x is valid + + The real world examples are usually more complicated, but similar + and usually result from inlining: + + bool init_func (int * x) + { + if (some_cond) + return false; + *x = ...; // set *x to valid + return true; + } + + void foo (..) + { + int x; + + if (!init_func (&x)) + return; + + .. some_code ... + use (x); // use when x is valid + } + + Another possible use scenario is in the following trivial example: + + Example 2: + if (n > 0) + x = 1; + ... + if (n > 0) + { + if (m < 2) + ... = x; + } + + Predicate analysis needs to compute the composite predicate: + + 1) 'x' use predicate: (n > 0) .AND. (m < 2) + 2) 'x' default value (non-def) predicate: .NOT. (n > 0) + (the predicate chain for phi operand defs can be computed + starting from a bb that is control equivalent to the phi's + bb and is dominating the operand def.) + + and check overlapping: + (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0)) + <==> false + + This implementation provides a framework that can handle different + scenarios. (Note that many simple cases are handled properly without + the predicate analysis if jump threading eliminates the merge point + thus makes path-sensitive analysis unnecessary.) + + PHI is the phi node whose incoming (undefined) paths need to be + pruned, and OPNDS is the bitmap holding interesting operand + positions. VISITED is the pointer set of phi stmts being + checked. */ + +bool +predicate::overlap (gphi *phi, unsigned opnds, hash_set<gphi *> *visited) +{ + gimple *flag_def = NULL; + tree boundary_cst = NULL_TREE; + bitmap visited_flag_phis = NULL; + + /* Find within the common prefix of multiple predicate chains + a predicate that is a comparison of a flag variable against + a constant. */ + tree_code cmp_code = find_var_cmp_const (m_preds, phi, &flag_def, + &boundary_cst); + if (cmp_code == ERROR_MARK) + return true; + + /* Now check all the uninit incoming edges have a constant flag + value that is in conflict with the use guard/predicate. */ + gphi *phi_def = as_a<gphi *> (flag_def); + bool all_pruned = prune_phi_opnds (phi, opnds, phi_def, boundary_cst, + cmp_code, m_eval, visited, + &visited_flag_phis); + + if (visited_flag_phis) + BITMAP_FREE (visited_flag_phis); + + return !all_pruned; +} + +/* Return true if two predicates PRED1 and X2 are equivalent. Assume + the expressions have already properly re-associated. */ + +static inline bool +pred_equal_p (const pred_info &pred1, const pred_info &pred2) +{ + if (!operand_equal_p (pred1.pred_lhs, pred2.pred_lhs, 0) + || !operand_equal_p (pred1.pred_rhs, pred2.pred_rhs, 0)) + return false; + + tree_code c1 = pred1.cond_code, c2; + if (pred1.invert != pred2.invert + && TREE_CODE_CLASS (pred2.cond_code) == tcc_comparison) + c2 = invert_tree_comparison (pred2.cond_code, false); + else + c2 = pred2.cond_code; + + return c1 == c2; +} + +/* Return true if PRED tests inequality (i.e., X != Y). */ + +static inline bool +is_neq_relop_p (const pred_info &pred) +{ + + return ((pred.cond_code == NE_EXPR && !pred.invert) + || (pred.cond_code == EQ_EXPR && pred.invert)); +} + +/* Returns true if PRED is of the form X != 0. */ + +static inline bool +is_neq_zero_form_p (const pred_info &pred) +{ + if (!is_neq_relop_p (pred) || !integer_zerop (pred.pred_rhs) + || TREE_CODE (pred.pred_lhs) != SSA_NAME) + return false; + return true; +} + +/* Return true if PRED is equivalent to X != 0. */ + +static inline bool +pred_expr_equal_p (const pred_info &pred, tree expr) +{ + if (!is_neq_zero_form_p (pred)) + return false; + + return operand_equal_p (pred.pred_lhs, expr, 0); +} + +/* 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. */ + +static bool +value_sat_pred_p (tree val, tree boundary, tree_code cmpc, + bool exact_p = false) +{ + if (cmpc != BIT_AND_EXPR) + return is_value_included_in (val, boundary, cmpc); + + wide_int andw = wi::to_wide (val) & wi::to_wide (boundary); + if (exact_p) + return andw == wi::to_wide (val); + + return andw.to_uhwi (); +} + +/* Return true if the domain of single predicate expression PRED1 + is a subset of that of PRED2, and false if it cannot be proved. */ + +static bool +subset_of (const pred_info &pred1, const pred_info &pred2) +{ + if (pred_equal_p (pred1, pred2)) + return true; + </cut>