* [PATCH] Improve uninit analysis
@ 2022-08-18 14:05 Richard Biener
0 siblings, 0 replies; 3+ messages in thread
From: Richard Biener @ 2022-08-18 14:05 UTC (permalink / raw)
To: gcc-patches
The following reduces the number of false positives in uninit analysis
by providing fallback for situations the current analysis gives up
and thus warns because it cannot prove initialization.
The first situation is when compute_control_dep_chain gives up walking
because it runs into either param_uninit_control_dep_attempts or
MAX_CHAIN_LEN. If in the process it did not collect a single path
from function entry to the interesting PHI edge then we'll give up
and diagnose. The following patch insteads provides a sparse path
including only those predicates that always hold when the PHI edge
is reached in that case. That's cheap to produce but may in some
odd cases prove less precise than what the code tries now (enumerating
all possible paths from function entry to the PHI edge, but only
use the first N of those and only require unreachability of those N).
The second situation is when the set of predicates computed to hold
on the use stmt was formed from multiple paths (there's a similar
enumeration of all paths and their predicates from the PHI def to the
use). In that case use_preds.use_cannot_happen gives up because
it doesn't know which of the predicates from which path from PHI to
the use it can use to prove unreachability of the PHI edge that has
the uninitialized def. The patch for this case simply computes
the intersection of the predicates and uses that for further analysis,
but in a crude way since the predicate vectors are not sorted.
Fortunately the total size is limited - we have max MAX_NUM_CHAINS
number of predicates each of length MAX_CHAIN_LEN so the brute
force intersection code should behave quite reasonable in practice.
Bootstrap and regtest running on x86_64-unknown-linux-gnu.
The testcase that made me produce this is tree-ssa-math-opts.cc
compiled with the backward jump threading limit increased by
a factor of two, so I don't have any testcase, not even one
with some --param adjustment (because that also affects DOM).
* gimple-predicate-analysis.cc (predicate::use_cannot_happen):
If the use is guarded with multiple predicate paths compute
the predicates intersection before going forward. When
compute_control_dep_chain wasn't able to come up with at
least one path from function entry to the PHI edge compute
a conservative sparse path instead.
---
gcc/gimple-predicate-analysis.cc | 64 ++++++++++++++++++++++++++++----
1 file changed, 56 insertions(+), 8 deletions(-)
diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc
index b8221d3fb8d..820a9bde28a 100644
--- a/gcc/gimple-predicate-analysis.cc
+++ b/gcc/gimple-predicate-analysis.cc
@@ -40,6 +40,7 @@
#include "builtins.h"
#include "calls.h"
#include "value-query.h"
+#include "cfganal.h"
#include "gimple-predicate-analysis.h"
@@ -1224,13 +1225,36 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
/* PHI_USE_GUARDS are OR'ed together. If we have more than one
possible guard, there's no way of knowing which guard was true.
- Since we need to be absolutely sure that the uninitialized
- operands will be invalidated, bail. */
+ In that case compute the intersection of all use predicates
+ and use that. */
const pred_chain_union &phi_use_guards = m_preds;
+ const pred_chain *use_guard = &phi_use_guards[0];
+ pred_chain phi_use_guard_intersection = vNULL;
if (phi_use_guards.length () != 1)
- return false;
-
- const pred_chain &use_guard = phi_use_guards[0];
+ {
+ phi_use_guard_intersection = use_guard->copy ();
+ for (unsigned i = 1; i < phi_use_guards.length (); ++i)
+ {
+ for (unsigned j = 0; j < phi_use_guard_intersection.length ();)
+ {
+ unsigned k;
+ for (k = 0; k < phi_use_guards[i].length (); ++k)
+ if (pred_equal_p (phi_use_guards[i][k],
+ phi_use_guard_intersection[j]))
+ break;
+ if (k == phi_use_guards[i].length ())
+ phi_use_guard_intersection.unordered_remove (j);
+ else
+ j++;
+ }
+ }
+ if (phi_use_guard_intersection.is_empty ())
+ {
+ phi_use_guard_intersection.release ();
+ return false;
+ }
+ use_guard = &phi_use_guard_intersection;
+ }
/* Look for the control dependencies of all the interesting operands
and build guard predicates describing them. */
@@ -1250,7 +1274,27 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun),
e->src, dep_chains, &num_chains,
cur_chain, &num_calls))
- return false;
+ {
+ gcc_assert (num_chains == 0);
+ /* 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 ();
+ num_chains++;
+ }
if (DEBUG_PREDICATE_ANALYZER && dump_file)
{
@@ -1272,10 +1316,14 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
/* Can the guard for this PHI argument be negated by the one
guarding the PHI use? */
- if (!can_be_invalidated_p (def_preds.chain (), use_guard))
- return false;
+ if (!can_be_invalidated_p (def_preds.chain (), *use_guard))
+ {
+ phi_use_guard_intersection.release ();
+ return false;
+ }
}
+ phi_use_guard_intersection.release ();
return true;
}
--
2.35.3
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH] Improve uninit analysis
@ 2022-08-18 14:05 Richard Biener
0 siblings, 0 replies; 3+ messages in thread
From: Richard Biener @ 2022-08-18 14:05 UTC (permalink / raw)
To: gcc-patches
The following reduces the number of false positives in uninit analysis
by providing fallback for situations the current analysis gives up
and thus warns because it cannot prove initialization.
The first situation is when compute_control_dep_chain gives up walking
because it runs into either param_uninit_control_dep_attempts or
MAX_CHAIN_LEN. If in the process it did not collect a single path
from function entry to the interesting PHI edge then we'll give up
and diagnose. The following patch insteads provides a sparse path
including only those predicates that always hold when the PHI edge
is reached in that case. That's cheap to produce but may in some
odd cases prove less precise than what the code tries now (enumerating
all possible paths from function entry to the PHI edge, but only
use the first N of those and only require unreachability of those N).
The second situation is when the set of predicates computed to hold
on the use stmt was formed from multiple paths (there's a similar
enumeration of all paths and their predicates from the PHI def to the
use). In that case use_preds.use_cannot_happen gives up because
it doesn't know which of the predicates from which path from PHI to
the use it can use to prove unreachability of the PHI edge that has
the uninitialized def. The patch for this case simply computes
the intersection of the predicates and uses that for further analysis,
but in a crude way since the predicate vectors are not sorted.
Fortunately the total size is limited - we have max MAX_NUM_CHAINS
number of predicates each of length MAX_CHAIN_LEN so the brute
force intersection code should behave quite reasonable in practice.
Bootstrap and regtest running on x86_64-unknown-linux-gnu.
The testcase that made me produce this is tree-ssa-math-opts.cc
compiled with the backward jump threading limit increased by
a factor of two, so I don't have any testcase, not even one
with some --param adjustment (because that also affects DOM).
* gimple-predicate-analysis.cc (predicate::use_cannot_happen):
If the use is guarded with multiple predicate paths compute
the predicates intersection before going forward. When
compute_control_dep_chain wasn't able to come up with at
least one path from function entry to the PHI edge compute
a conservative sparse path instead.
---
gcc/gimple-predicate-analysis.cc | 64 ++++++++++++++++++++++++++++----
1 file changed, 56 insertions(+), 8 deletions(-)
diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc
index b8221d3fb8d..820a9bde28a 100644
--- a/gcc/gimple-predicate-analysis.cc
+++ b/gcc/gimple-predicate-analysis.cc
@@ -40,6 +40,7 @@
#include "builtins.h"
#include "calls.h"
#include "value-query.h"
+#include "cfganal.h"
#include "gimple-predicate-analysis.h"
@@ -1224,13 +1225,36 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
/* PHI_USE_GUARDS are OR'ed together. If we have more than one
possible guard, there's no way of knowing which guard was true.
- Since we need to be absolutely sure that the uninitialized
- operands will be invalidated, bail. */
+ In that case compute the intersection of all use predicates
+ and use that. */
const pred_chain_union &phi_use_guards = m_preds;
+ const pred_chain *use_guard = &phi_use_guards[0];
+ pred_chain phi_use_guard_intersection = vNULL;
if (phi_use_guards.length () != 1)
- return false;
-
- const pred_chain &use_guard = phi_use_guards[0];
+ {
+ phi_use_guard_intersection = use_guard->copy ();
+ for (unsigned i = 1; i < phi_use_guards.length (); ++i)
+ {
+ for (unsigned j = 0; j < phi_use_guard_intersection.length ();)
+ {
+ unsigned k;
+ for (k = 0; k < phi_use_guards[i].length (); ++k)
+ if (pred_equal_p (phi_use_guards[i][k],
+ phi_use_guard_intersection[j]))
+ break;
+ if (k == phi_use_guards[i].length ())
+ phi_use_guard_intersection.unordered_remove (j);
+ else
+ j++;
+ }
+ }
+ if (phi_use_guard_intersection.is_empty ())
+ {
+ phi_use_guard_intersection.release ();
+ return false;
+ }
+ use_guard = &phi_use_guard_intersection;
+ }
/* Look for the control dependencies of all the interesting operands
and build guard predicates describing them. */
@@ -1250,7 +1274,27 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun),
e->src, dep_chains, &num_chains,
cur_chain, &num_calls))
- return false;
+ {
+ gcc_assert (num_chains == 0);
+ /* 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 ();
+ num_chains++;
+ }
if (DEBUG_PREDICATE_ANALYZER && dump_file)
{
@@ -1272,10 +1316,14 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
/* Can the guard for this PHI argument be negated by the one
guarding the PHI use? */
- if (!can_be_invalidated_p (def_preds.chain (), use_guard))
- return false;
+ if (!can_be_invalidated_p (def_preds.chain (), *use_guard))
+ {
+ phi_use_guard_intersection.release ();
+ return false;
+ }
}
+ phi_use_guard_intersection.release ();
return true;
}
--
2.35.3
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH] Improve uninit analysis
@ 2022-08-18 14:05 Richard Biener
0 siblings, 0 replies; 3+ messages in thread
From: Richard Biener @ 2022-08-18 14:05 UTC (permalink / raw)
To: gcc-patches
The following reduces the number of false positives in uninit analysis
by providing fallback for situations the current analysis gives up
and thus warns because it cannot prove initialization.
The first situation is when compute_control_dep_chain gives up walking
because it runs into either param_uninit_control_dep_attempts or
MAX_CHAIN_LEN. If in the process it did not collect a single path
from function entry to the interesting PHI edge then we'll give up
and diagnose. The following patch insteads provides a sparse path
including only those predicates that always hold when the PHI edge
is reached in that case. That's cheap to produce but may in some
odd cases prove less precise than what the code tries now (enumerating
all possible paths from function entry to the PHI edge, but only
use the first N of those and only require unreachability of those N).
The second situation is when the set of predicates computed to hold
on the use stmt was formed from multiple paths (there's a similar
enumeration of all paths and their predicates from the PHI def to the
use). In that case use_preds.use_cannot_happen gives up because
it doesn't know which of the predicates from which path from PHI to
the use it can use to prove unreachability of the PHI edge that has
the uninitialized def. The patch for this case simply computes
the intersection of the predicates and uses that for further analysis,
but in a crude way since the predicate vectors are not sorted.
Fortunately the total size is limited - we have max MAX_NUM_CHAINS
number of predicates each of length MAX_CHAIN_LEN so the brute
force intersection code should behave quite reasonable in practice.
Bootstrap and regtest running on x86_64-unknown-linux-gnu.
The testcase that made me produce this is tree-ssa-math-opts.cc
compiled with the backward jump threading limit increased by
a factor of two, so I don't have any testcase, not even one
with some --param adjustment (because that also affects DOM).
* gimple-predicate-analysis.cc (predicate::use_cannot_happen):
If the use is guarded with multiple predicate paths compute
the predicates intersection before going forward. When
compute_control_dep_chain wasn't able to come up with at
least one path from function entry to the PHI edge compute
a conservative sparse path instead.
---
gcc/gimple-predicate-analysis.cc | 64 ++++++++++++++++++++++++++++----
1 file changed, 56 insertions(+), 8 deletions(-)
diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc
index b8221d3fb8d..820a9bde28a 100644
--- a/gcc/gimple-predicate-analysis.cc
+++ b/gcc/gimple-predicate-analysis.cc
@@ -40,6 +40,7 @@
#include "builtins.h"
#include "calls.h"
#include "value-query.h"
+#include "cfganal.h"
#include "gimple-predicate-analysis.h"
@@ -1224,13 +1225,36 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
/* PHI_USE_GUARDS are OR'ed together. If we have more than one
possible guard, there's no way of knowing which guard was true.
- Since we need to be absolutely sure that the uninitialized
- operands will be invalidated, bail. */
+ In that case compute the intersection of all use predicates
+ and use that. */
const pred_chain_union &phi_use_guards = m_preds;
+ const pred_chain *use_guard = &phi_use_guards[0];
+ pred_chain phi_use_guard_intersection = vNULL;
if (phi_use_guards.length () != 1)
- return false;
-
- const pred_chain &use_guard = phi_use_guards[0];
+ {
+ phi_use_guard_intersection = use_guard->copy ();
+ for (unsigned i = 1; i < phi_use_guards.length (); ++i)
+ {
+ for (unsigned j = 0; j < phi_use_guard_intersection.length ();)
+ {
+ unsigned k;
+ for (k = 0; k < phi_use_guards[i].length (); ++k)
+ if (pred_equal_p (phi_use_guards[i][k],
+ phi_use_guard_intersection[j]))
+ break;
+ if (k == phi_use_guards[i].length ())
+ phi_use_guard_intersection.unordered_remove (j);
+ else
+ j++;
+ }
+ }
+ if (phi_use_guard_intersection.is_empty ())
+ {
+ phi_use_guard_intersection.release ();
+ return false;
+ }
+ use_guard = &phi_use_guard_intersection;
+ }
/* Look for the control dependencies of all the interesting operands
and build guard predicates describing them. */
@@ -1250,7 +1274,27 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun),
e->src, dep_chains, &num_chains,
cur_chain, &num_calls))
- return false;
+ {
+ gcc_assert (num_chains == 0);
+ /* 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 ();
+ num_chains++;
+ }
if (DEBUG_PREDICATE_ANALYZER && dump_file)
{
@@ -1272,10 +1316,14 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
/* Can the guard for this PHI argument be negated by the one
guarding the PHI use? */
- if (!can_be_invalidated_p (def_preds.chain (), use_guard))
- return false;
+ if (!can_be_invalidated_p (def_preds.chain (), *use_guard))
+ {
+ phi_use_guard_intersection.release ();
+ return false;
+ }
}
+ phi_use_guard_intersection.release ();
return true;
}
--
2.35.3
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2022-08-18 14:05 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-08-18 14:05 [PATCH] Improve uninit analysis Richard Biener
-- strict thread matches above, loose matches on Subject: below --
2022-08-18 14:05 Richard Biener
2022-08-18 14:05 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).