[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
