* [PATCH] tree-optimization/106722 - uninit analysis with long def -> use path
@ 2022-08-23 13:20 Richard Biener
0 siblings, 0 replies; 2+ messages in thread
From: Richard Biener @ 2022-08-23 13:20 UTC (permalink / raw)
To: gcc-patches
The following applies similar measures as r13-2133-ge66cf626c72d58
to the computation of the use predicate when the path from PHI def
to use is too long and we run into compute_control_dep_chain limits.
It also moves the preprocessor define limits internal.
This resolves the reduced testcase but not the original one.
Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.
PR tree-optimization/106722
* gimple-predicate-analysis.h (MAX_NUM_CHAINS, MAX_CHAIN_LEN,
MAX_POSTDOM_CHECK, MAX_SWITCH_CASES): Move ...
* gimple-predicate-analysis.cc: ... here and document.
(simple_control_dep_chain): New function, factored from
predicate::use_cannot_happen.
(predicate::use_cannot_happen): Adjust.
(predicate::predicate): Use simple_control_dep_chain as fallback.
* g++.dg/uninit-pr106722-1.C: New testcase.
---
gcc/gimple-predicate-analysis.cc | 68 ++++++++++++++++++------
gcc/gimple-predicate-analysis.h | 4 --
gcc/testsuite/g++.dg/uninit-pr106722-1.C | 65 ++++++++++++++++++++++
3 files changed, 117 insertions(+), 20 deletions(-)
create mode 100644 gcc/testsuite/g++.dg/uninit-pr106722-1.C
diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc
index e8e2dbf7034..a4291657d0b 100644
--- a/gcc/gimple-predicate-analysis.cc
+++ b/gcc/gimple-predicate-analysis.cc
@@ -46,6 +46,19 @@
#define DEBUG_PREDICATE_ANALYZER 1
+/* In our predicate normal form we have MAX_NUM_CHAINS or predicates
+ and in those MAX_CHAIN_LEN (inverted) and predicates. */
+#define MAX_NUM_CHAINS 8
+#define MAX_CHAIN_LEN 5
+
+/* When enumerating paths between two blocks this limits the number of
+ post-dominator skips between two edges possibly defining a predicate. */
+#define MAX_POSTDOM_CHECK 8
+
+/* The limit for the number of switch cases when we do the linear search
+ for the case corresponding to an edge. */
+#define MAX_SWITCH_CASES 40
+
/* Return true if, when BB1 is postdominating BB2, BB1 is a loop exit. */
static bool
@@ -1034,6 +1047,36 @@ is_degenerate_phi (gimple *phi, pred_info *pred)
return true;
}
+/* 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. */
+
+static void
+simple_control_dep_chain (vec<edge>& chain, basic_block from, basic_block to)
+{
+ if (!dominated_by_p (CDI_DOMINATORS, to, from))
+ return;
+
+ basic_block src = to;
+ while (src != from
+ && chain.length () <= MAX_CHAIN_LEN)
+ {
+ basic_block dest = src;
+ src = get_immediate_dominator (CDI_DOMINATORS, src);
+ edge pred_e;
+ if (single_pred_p (dest)
+ && (pred_e = find_edge (src, dest)))
+ chain.safe_push (pred_e);
+ }
+}
+
+static void
+simple_control_dep_chain (vec<edge>& chain, basic_block from, edge to)
+{
+ chain.safe_push (to);
+ simple_control_dep_chain (chain, from, to->src);
+}
+
/* 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),
@@ -1273,20 +1316,8 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
/* If compute_control_dep_chain bailed out due to limits
build a partial sparse path using dominators. Collect
only edges whose predicates are always true when reaching E. */
- cur_chain.truncate (0);
- cur_chain.quick_push (e);
- basic_block src = e->src;
- while (src->index != ENTRY_BLOCK
- && cur_chain.length () <= MAX_CHAIN_LEN)
- {
- basic_block dest = src;
- src = get_immediate_dominator (CDI_DOMINATORS, src);
- edge pred_e;
- if (single_pred_p (dest)
- && (pred_e = find_edge (src, dest)))
- cur_chain.quick_push (pred_e);
- }
- dep_chains[0] = cur_chain.copy ();
+ simple_control_dep_chain (dep_chains[0],
+ ENTRY_BLOCK_PTR_FOR_FN (cfun), e);
num_chains++;
}
@@ -1737,8 +1768,13 @@ predicate::predicate (basic_block def_bb, basic_block use_bb, func_t &eval)
auto_vec<edge> dep_chains[MAX_NUM_CHAINS];
auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
- compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
- cur_chain, &num_calls);
+ if (!compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
+ cur_chain, &num_calls))
+ {
+ gcc_assert (num_chains == 0);
+ simple_control_dep_chain (dep_chains[0], cd_root, use_bb);
+ num_chains++;
+ }
if (DEBUG_PREDICATE_ANALYZER && dump_file)
{
diff --git a/gcc/gimple-predicate-analysis.h b/gcc/gimple-predicate-analysis.h
index 204cdbccfc7..77672291c36 100644
--- a/gcc/gimple-predicate-analysis.h
+++ b/gcc/gimple-predicate-analysis.h
@@ -22,10 +22,6 @@
#ifndef GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED
#define GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED
-#define MAX_NUM_CHAINS 8
-#define MAX_CHAIN_LEN 5
-#define MAX_POSTDOM_CHECK 8
-#define MAX_SWITCH_CASES 40
/* Represents a simple Boolean predicate. */
struct pred_info
diff --git a/gcc/testsuite/g++.dg/uninit-pr106722-1.C b/gcc/testsuite/g++.dg/uninit-pr106722-1.C
new file mode 100644
index 00000000000..a10f8dd88c7
--- /dev/null
+++ b/gcc/testsuite/g++.dg/uninit-pr106722-1.C
@@ -0,0 +1,65 @@
+// { dg-do compile }
+// { dg-require-effective-target c++11 }
+// { dg-options "-O2 -Wmaybe-uninitialized --param logical-op-non-short-circuit=0" }
+long pow2p_hwi_x;
+bool exact_log2___trans_tmp_5, exact_log2___trans_tmp_4;
+int exact_log2(long x) {
+ exact_log2___trans_tmp_5 = pow2p_hwi_x && exact_log2___trans_tmp_4;
+ return exact_log2___trans_tmp_5 ? x : 1;
+}
+enum signop {};
+template <typename T1, typename T2> void rshift(T1, T2, signop);
+struct generic_wide_int {
+ template <typename T> generic_wide_int(T);
+};
+template <unsigned N, typename> struct poly_int_pod {
+ bool is_constant() const;
+ template <typename T> bool is_constant(T *) const;
+ int coeffs[N];
+};
+template <unsigned N, typename C>
+template <typename T>
+bool poly_int_pod<N, C>::is_constant(T *const_value) const {
+ if (is_constant()) {
+ *const_value = coeffs[0];
+ return true;
+ }
+ return false;
+}
+struct poly_int : poly_int_pod<1, int> {
+ template <typename C0> poly_int(C0);
+};
+enum tree_code_class {} tree_code_type;
+void tree_class_check_failed(int *, tree_code_class, char *, int, char *)
+ __attribute__((__noreturn__));
+int tree_class_check___t, tree_class_check___l,
+ vect_gen_vector_loop_niters_loop_vinfo;
+char tree_class_check___f, tree_class_check___g;
+tree_code_class tree_class_check___class;
+int *tree_class_check() {
+ if (tree_code_type)
+ tree_class_check_failed(&tree_class_check___t, tree_class_check___class,
+ &tree_class_check___f, tree_class_check___l,
+ &tree_class_check___g);
+ return &tree_class_check___t;
+}
+int *build_int_cst(int, long);
+bool is_gimple_val(int);
+void force_gimple_operand(int, int *, bool, int);
+void vect_gen_vector_loop_niters(bool niters_no_overflow) {
+ poly_int vf(vect_gen_vector_loop_niters_loop_vinfo);
+ int *log_vf = nullptr;
+ long const_vf;
+ if (vf.is_constant(&const_vf))
+ log_vf = build_int_cst(0, 0);
+ if (is_gimple_val(0)) {
+ int stmts;
+ force_gimple_operand(0, &stmts, true, 0);
+ if (stmts && log_vf)
+ if (niters_no_overflow) {
+ generic_wide_int __trans_tmp_1(tree_class_check());
+ int __trans_tmp_2 = exact_log2(const_vf); // { dg-bogus "uninitialized" }
+ rshift(__trans_tmp_1, __trans_tmp_2, (signop)0);
+ }
+ }
+}
--
2.35.3
^ permalink raw reply [flat|nested] 2+ messages in thread
* [PATCH] tree-optimization/106722 - uninit analysis with long def -> use path
@ 2022-08-23 13:20 Richard Biener
0 siblings, 0 replies; 2+ messages in thread
From: Richard Biener @ 2022-08-23 13:20 UTC (permalink / raw)
To: gcc-patches
The following applies similar measures as r13-2133-ge66cf626c72d58
to the computation of the use predicate when the path from PHI def
to use is too long and we run into compute_control_dep_chain limits.
It also moves the preprocessor define limits internal.
This resolves the reduced testcase but not the original one.
Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.
PR tree-optimization/106722
* gimple-predicate-analysis.h (MAX_NUM_CHAINS, MAX_CHAIN_LEN,
MAX_POSTDOM_CHECK, MAX_SWITCH_CASES): Move ...
* gimple-predicate-analysis.cc: ... here and document.
(simple_control_dep_chain): New function, factored from
predicate::use_cannot_happen.
(predicate::use_cannot_happen): Adjust.
(predicate::predicate): Use simple_control_dep_chain as fallback.
* g++.dg/uninit-pr106722-1.C: New testcase.
---
gcc/gimple-predicate-analysis.cc | 68 ++++++++++++++++++------
gcc/gimple-predicate-analysis.h | 4 --
gcc/testsuite/g++.dg/uninit-pr106722-1.C | 65 ++++++++++++++++++++++
3 files changed, 117 insertions(+), 20 deletions(-)
create mode 100644 gcc/testsuite/g++.dg/uninit-pr106722-1.C
diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc
index e8e2dbf7034..a4291657d0b 100644
--- a/gcc/gimple-predicate-analysis.cc
+++ b/gcc/gimple-predicate-analysis.cc
@@ -46,6 +46,19 @@
#define DEBUG_PREDICATE_ANALYZER 1
+/* In our predicate normal form we have MAX_NUM_CHAINS or predicates
+ and in those MAX_CHAIN_LEN (inverted) and predicates. */
+#define MAX_NUM_CHAINS 8
+#define MAX_CHAIN_LEN 5
+
+/* When enumerating paths between two blocks this limits the number of
+ post-dominator skips between two edges possibly defining a predicate. */
+#define MAX_POSTDOM_CHECK 8
+
+/* The limit for the number of switch cases when we do the linear search
+ for the case corresponding to an edge. */
+#define MAX_SWITCH_CASES 40
+
/* Return true if, when BB1 is postdominating BB2, BB1 is a loop exit. */
static bool
@@ -1034,6 +1047,36 @@ is_degenerate_phi (gimple *phi, pred_info *pred)
return true;
}
+/* 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. */
+
+static void
+simple_control_dep_chain (vec<edge>& chain, basic_block from, basic_block to)
+{
+ if (!dominated_by_p (CDI_DOMINATORS, to, from))
+ return;
+
+ basic_block src = to;
+ while (src != from
+ && chain.length () <= MAX_CHAIN_LEN)
+ {
+ basic_block dest = src;
+ src = get_immediate_dominator (CDI_DOMINATORS, src);
+ edge pred_e;
+ if (single_pred_p (dest)
+ && (pred_e = find_edge (src, dest)))
+ chain.safe_push (pred_e);
+ }
+}
+
+static void
+simple_control_dep_chain (vec<edge>& chain, basic_block from, edge to)
+{
+ chain.safe_push (to);
+ simple_control_dep_chain (chain, from, to->src);
+}
+
/* 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),
@@ -1273,20 +1316,8 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
/* If compute_control_dep_chain bailed out due to limits
build a partial sparse path using dominators. Collect
only edges whose predicates are always true when reaching E. */
- cur_chain.truncate (0);
- cur_chain.quick_push (e);
- basic_block src = e->src;
- while (src->index != ENTRY_BLOCK
- && cur_chain.length () <= MAX_CHAIN_LEN)
- {
- basic_block dest = src;
- src = get_immediate_dominator (CDI_DOMINATORS, src);
- edge pred_e;
- if (single_pred_p (dest)
- && (pred_e = find_edge (src, dest)))
- cur_chain.quick_push (pred_e);
- }
- dep_chains[0] = cur_chain.copy ();
+ simple_control_dep_chain (dep_chains[0],
+ ENTRY_BLOCK_PTR_FOR_FN (cfun), e);
num_chains++;
}
@@ -1737,8 +1768,13 @@ predicate::predicate (basic_block def_bb, basic_block use_bb, func_t &eval)
auto_vec<edge> dep_chains[MAX_NUM_CHAINS];
auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
- compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
- cur_chain, &num_calls);
+ if (!compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
+ cur_chain, &num_calls))
+ {
+ gcc_assert (num_chains == 0);
+ simple_control_dep_chain (dep_chains[0], cd_root, use_bb);
+ num_chains++;
+ }
if (DEBUG_PREDICATE_ANALYZER && dump_file)
{
diff --git a/gcc/gimple-predicate-analysis.h b/gcc/gimple-predicate-analysis.h
index 204cdbccfc7..77672291c36 100644
--- a/gcc/gimple-predicate-analysis.h
+++ b/gcc/gimple-predicate-analysis.h
@@ -22,10 +22,6 @@
#ifndef GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED
#define GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED
-#define MAX_NUM_CHAINS 8
-#define MAX_CHAIN_LEN 5
-#define MAX_POSTDOM_CHECK 8
-#define MAX_SWITCH_CASES 40
/* Represents a simple Boolean predicate. */
struct pred_info
diff --git a/gcc/testsuite/g++.dg/uninit-pr106722-1.C b/gcc/testsuite/g++.dg/uninit-pr106722-1.C
new file mode 100644
index 00000000000..a10f8dd88c7
--- /dev/null
+++ b/gcc/testsuite/g++.dg/uninit-pr106722-1.C
@@ -0,0 +1,65 @@
+// { dg-do compile }
+// { dg-require-effective-target c++11 }
+// { dg-options "-O2 -Wmaybe-uninitialized --param logical-op-non-short-circuit=0" }
+long pow2p_hwi_x;
+bool exact_log2___trans_tmp_5, exact_log2___trans_tmp_4;
+int exact_log2(long x) {
+ exact_log2___trans_tmp_5 = pow2p_hwi_x && exact_log2___trans_tmp_4;
+ return exact_log2___trans_tmp_5 ? x : 1;
+}
+enum signop {};
+template <typename T1, typename T2> void rshift(T1, T2, signop);
+struct generic_wide_int {
+ template <typename T> generic_wide_int(T);
+};
+template <unsigned N, typename> struct poly_int_pod {
+ bool is_constant() const;
+ template <typename T> bool is_constant(T *) const;
+ int coeffs[N];
+};
+template <unsigned N, typename C>
+template <typename T>
+bool poly_int_pod<N, C>::is_constant(T *const_value) const {
+ if (is_constant()) {
+ *const_value = coeffs[0];
+ return true;
+ }
+ return false;
+}
+struct poly_int : poly_int_pod<1, int> {
+ template <typename C0> poly_int(C0);
+};
+enum tree_code_class {} tree_code_type;
+void tree_class_check_failed(int *, tree_code_class, char *, int, char *)
+ __attribute__((__noreturn__));
+int tree_class_check___t, tree_class_check___l,
+ vect_gen_vector_loop_niters_loop_vinfo;
+char tree_class_check___f, tree_class_check___g;
+tree_code_class tree_class_check___class;
+int *tree_class_check() {
+ if (tree_code_type)
+ tree_class_check_failed(&tree_class_check___t, tree_class_check___class,
+ &tree_class_check___f, tree_class_check___l,
+ &tree_class_check___g);
+ return &tree_class_check___t;
+}
+int *build_int_cst(int, long);
+bool is_gimple_val(int);
+void force_gimple_operand(int, int *, bool, int);
+void vect_gen_vector_loop_niters(bool niters_no_overflow) {
+ poly_int vf(vect_gen_vector_loop_niters_loop_vinfo);
+ int *log_vf = nullptr;
+ long const_vf;
+ if (vf.is_constant(&const_vf))
+ log_vf = build_int_cst(0, 0);
+ if (is_gimple_val(0)) {
+ int stmts;
+ force_gimple_operand(0, &stmts, true, 0);
+ if (stmts && log_vf)
+ if (niters_no_overflow) {
+ generic_wide_int __trans_tmp_1(tree_class_check());
+ int __trans_tmp_2 = exact_log2(const_vf); // { dg-bogus "uninitialized" }
+ rshift(__trans_tmp_1, __trans_tmp_2, (signop)0);
+ }
+ }
+}
--
2.35.3
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2022-08-23 13:20 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-08-23 13:20 [PATCH] tree-optimization/106722 - uninit analysis with long def -> use path Richard Biener
2022-08-23 13:20 Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).