Hi Martin, Your below patch broke linux kernel build on 32-bit ARM. Is this on your radar? Do you need help reproducing this?
Regards, -- Maxim Kuvyrkov https://www.linaro.org > On 21 Sep 2021, at 05:11, ci_not...@linaro.org wrote: > > [TCWG CI] Regression caused by gcc: Factor predidacte analysis out of > tree-ssa-uninit.c into its own module.: > commit 94c12ffac234b29a702aa7b6730f2678265857c8 > Author: Martin Sebor <mse...@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-defconfig/26/artifact/artifacts/build-94c12ffac234b29a702aa7b6730f2678265857c8/ > Last_good build: > https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-defconfig/26/artifact/artifacts/build-51166eb2c534692c3c7779def24f83c8c3811b98/ > Baseline build: > https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-defconfig/26/artifact/artifacts/build-baseline/ > Even more details: > https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-defconfig/26/artifact/artifacts/ > > 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-defconfig/26/artifact/artifacts/manifests/build-baseline.sh > --fail > curl -o artifacts/manifests/build-parameters.sh > https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-defconfig/26/artifact/artifacts/manifests/build-parameters.sh > --fail > curl -o artifacts/test.sh > https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-defconfig/26/artifact/artifacts/test.sh > --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 <mse...@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 <davi...@google.com> > + Generalized by Martin Sebor <mse...@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> _______________________________________________ linaro-toolchain mailing list linaro-toolchain@lists.linaro.org https://lists.linaro.org/mailman/listinfo/linaro-toolchain
