| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
Now that pointers and integers have been disambiguated from irange,
and all the pointer range temporaries use prange, we can reclaim
value_range as a general purpose range container.
This patch removes the typedef, in favor of int_range_max, thus
providing slightly better ranges in places. I have also used
int_range<1> or <2> when it's known ahead of time how big the range will
be, thus saving a few words.
In a follow-up patch I will rename the Value_Range temporary to
value_range.
No change in performance.
gcc/ChangeLog:
* builtins.cc (expand_builtin_strnlen): Replace value_range use
with int_range_max or irange when appropriate.
(determine_block_size): Same.
* fold-const.cc (minmax_from_comparison): Same.
* gimple-array-bounds.cc (check_out_of_bounds_and_warn): Same.
(array_bounds_checker::check_array_ref): Same.
* gimple-fold.cc (size_must_be_zero_p): Same.
* gimple-predicate-analysis.cc (find_var_cmp_const): Same.
* gimple-ssa-sprintf.cc (get_int_range): Same.
(format_integer): Same.
(try_substitute_return_value): Same.
(handle_printf_call): Same.
* gimple-ssa-warn-restrict.cc
(builtin_memref::extend_offset_range): Same.
* graphite-sese-to-poly.cc (add_param_constraints): Same.
* internal-fn.cc (get_min_precision): Same.
* match.pd: Same.
* pointer-query.cc (get_size_range): Same.
* range-op.cc (get_shift_range): Same.
(operator_trunc_mod::op1_range): Same.
(operator_trunc_mod::op2_range): Same.
* range.cc (range_negatives): Same.
* range.h (range_positives): Same.
(range_negatives): Same.
* tree-affine.cc (expr_to_aff_combination): Same.
* tree-data-ref.cc (compute_distributive_range): Same.
(nop_conversion_for_offset_p): Same.
(split_constant_offset): Same.
(split_constant_offset_1): Same.
(dr_step_indicator): Same.
* tree-dfa.cc (get_ref_base_and_extent): Same.
* tree-scalar-evolution.cc (iv_can_overflow_p): Same.
* tree-ssa-math-opts.cc (optimize_spaceship): Same.
* tree-ssa-pre.cc (insert_into_preds_of_block): Same.
* tree-ssa-reassoc.cc (optimize_range_tests_to_bit_test): Same.
* tree-ssa-strlen.cc (compare_nonzero_chars): Same.
(dump_strlen_info): Same.
(get_range_strlen_dynamic): Same.
(set_strlen_range): Same.
(maybe_diag_stxncpy_trunc): Same.
(strlen_pass::get_len_or_size): Same.
(strlen_pass::handle_builtin_string_cmp): Same.
(strlen_pass::count_nonzero_bytes_addr): Same.
(strlen_pass::handle_integral_assign): Same.
* tree-switch-conversion.cc (bit_test_cluster::emit): Same.
* tree-vect-loop-manip.cc (vect_gen_vector_loop_niters): Same.
(vect_do_peeling): Same.
* tree-vect-patterns.cc (vect_get_range_info): Same.
(vect_recog_divmod_pattern): Same.
* tree.cc (get_range_pos_neg): Same.
* value-range.cc (debug): Remove value_range variants.
* value-range.h (value_range): Remove typedef.
* vr-values.cc
(simplify_using_ranges::op_with_boolean_value_range_p): Replace
value_range use with int_range_max or irange when appropriate.
(check_for_binary_op_overflow): Same.
(simplify_using_ranges::legacy_fold_cond_overflow): Same.
(find_case_label_ranges): Same.
(simplify_using_ranges::simplify_abs_using_ranges): Same.
(test_for_singularity): Same.
(simplify_using_ranges::simplify_compare_using_ranges_1): Same.
(simplify_using_ranges::simplify_casted_compare): Same.
(simplify_using_ranges::simplify_switch_using_ranges): Same.
(simplify_conversion_using_ranges): Same.
(simplify_using_ranges::two_valued_val_range_p): Same.
|
|
|
|
Uninit diagnostics has code to prune based on incoming PHI args
that prove the uninit code is never executed. But that only
looks at the first found flag candidate while in the PRs case
only the second candidate would be the one to prune on. The
following patch makes us consider all of the flag candidates
which is cycles well spent IMHO.
PR tree-optimization/112766
* gimple-predicate-analysis.cc (find_var_cmp_const):
Support continuing the iteration and report every candidate.
(uninit_analysis::overlap): Iterate over all flag var
candidates.
* g++.dg/torture/uninit-pr112766.C: New testcase.
|
|
The following turns MAX_NUM_CHAINS and MAX_CHAIN_LEN to params which
allows to experiment with raising them. For the testcase in PR111489
raising MAX_CHAIN_LEN from 5 to 8 avoids the bogus diagnostics
at -O2, at -O3 we need a MAX_CHAIN_LEN of 6.
PR tree-optimization/111489
* doc/invoke.texi (--param uninit-max-chain-len): Document.
(--param uninit-max-num-chains): Likewise.
* params.opt (-param=uninit-max-chain-len=): New.
(-param=uninit-max-num-chains=): Likewise.
* gimple-predicate-analysis.cc (MAX_NUM_CHAINS): Define to
param_uninit_max_num_chains.
(MAX_CHAIN_LEN): Define to param_uninit_max_chain_len.
(uninit_analysis::init_use_preds): Avoid VLA.
(uninit_analysis::init_from_phi_def): Likewise.
(compute_control_dep_chain): Avoid using MAX_CHAIN_LEN in
template parameter.
|
|
Feeding not optimized IL can result in predicate normalization
to simplify things so a predicate can get true or false. The
following re-orders the early exit in that case to come after
simplification and normalization to take care of that.
PR tree-optimization/110392
* gimple-predicate-analysis.cc (uninit_analysis::is_use_guarded):
Do early exits on true/false predicate only after normalization.
|
|
gcc/ChangeLog:
* builtins.cc (expand_builtin_strnlen): Rewrite deprecated irange
API uses to new API.
* gimple-predicate-analysis.cc (find_var_cmp_const): Same.
* internal-fn.cc (get_min_precision): Same.
* match.pd: Same.
* tree-affine.cc (expr_to_aff_combination): Same.
* tree-data-ref.cc (dr_step_indicator): Same.
* tree-dfa.cc (get_ref_base_and_extent): Same.
* tree-scalar-evolution.cc (iv_can_overflow_p): Same.
* tree-ssa-phiopt.cc (two_value_replacement): Same.
* tree-ssa-pre.cc (insert_into_preds_of_block): Same.
* tree-ssa-reassoc.cc (optimize_range_tests_to_bit_test): Same.
* tree-ssa-strlen.cc (compare_nonzero_chars): Same.
* tree-switch-conversion.cc (bit_test_cluster::emit): Same.
* tree-vect-patterns.cc (vect_recog_divmod_pattern): Same.
* tree.cc (get_range_pos_neg): Same.
|
|
There are quite some cases which want to access the control stmt
ending a basic-block. Since there cannot be debug stmts after
such stmt there's no point in using last_stmt which skips debug
stmts and can be a compile-time hog for larger testcases.
* gimple-ssa-split-paths.cc (is_feasible_trace): Avoid
last_stmt.
* graphite-scop-detection.cc (single_pred_cond_non_loop_exit):
Likewise.
* ipa-fnsummary.cc (set_cond_stmt_execution_predicate): Likewise.
(set_switch_stmt_execution_predicate): Likewise.
(phi_result_unknown_predicate): Likewise.
* ipa-prop.cc (compute_complex_ancestor_jump_func): Likewise.
(ipa_analyze_indirect_call_uses): Likewise.
* predict.cc (predict_iv_comparison): Likewise.
(predict_extra_loop_exits): Likewise.
(predict_loops): Likewise.
(tree_predict_by_opcode): Likewise.
* gimple-predicate-analysis.cc (predicate::init_from_control_deps):
Likewise.
* gimple-pretty-print.cc (dump_implicit_edges): Likewise.
* tree-ssa-phiopt.cc (tree_ssa_phiopt_worker): Likewise.
(replace_phi_edge_with_variable): Likewise.
(two_value_replacement): Likewise.
(value_replacement): Likewise.
(minmax_replacement): Likewise.
(spaceship_replacement): Likewise.
(cond_removal_in_builtin_zero_pattern): Likewise.
* tree-ssa-reassoc.cc (maybe_optimize_range_tests): Likewise.
* tree-ssa-sccvn.cc (vn_phi_eq): Likewise.
(vn_phi_lookup): Likewise.
(vn_phi_insert): Likewise.
* tree-ssa-structalias.cc (compute_points_to_sets): Likewise.
* tree-ssa-threadbackward.cc (back_threader::maybe_thread_block):
Likewise.
(back_threader_profitability::possibly_profitable_path_p):
Likewise.
* tree-ssa-threadedge.cc (jump_threader::thread_outgoing_edges):
Likewise.
* tree-switch-conversion.cc (pass_convert_switch::execute):
Likewise.
(pass_lower_switch<O0>::execute): Likewise.
* tree-tailcall.cc (tree_optimize_tail_calls_1): Likewise.
* tree-vect-loop-manip.cc (vect_loop_versioning): Likewise.
* tree-vect-slp.cc (vect_slp_function): Likewise.
* tree-vect-stmts.cc (cfun_returns): Likewise.
* tree-vectorizer.cc (vect_loop_vectorized_call): Likewise.
(vect_loop_dist_alias_call): Likewise.
|
|
Predicate analysis, when looking through casts doesn't bother to
convert boundary constants to the type of the bounded variables.
The following robustifies value_sat_pred_p to use widest_ints
to deal with this, like other code in predicate analysis.
PR tree-optimization/108547
* gimple-predicate-analysis.cc (value_sat_pred_p):
Use widest_int.
* gcc.dg/uninit-pr108547.c: New testcase.
|
|
|
|
The following changes the predicate representation to record the
value of a predicate with an empty set of AND predicates. That's
necessary to properly represent the conservative fallback for the
def vs use predicates. Since simplification now can result in
such an empty set this distinction becomes important and we need
to check for this as we otherwise ICE.
PR tree-optimization/107937
* gimple-predicate-analysis.h (predicate::is_true): New.
(predicate::is_false): Likewise.
(predicate::empty_val): Likewise.
(uninit_analysis::uninit_analysis): Properly initialize
def_preds.
* gimple-predicate-analysis.cc (simplify_1b): Indicate
whether the chain became empty.
(predicate::simplify): Release emptied chain before removing it.
(predicate::normalize): Replace temporary object with assertion.
(uninit_analysis::is_use_guarded): Deal with predicates
that simplify to true/false.
* gcc.dg/pr107937.c: New testcase.
|
|
The testcase from the PR at -O2 shows
((_277 == 2) AND (_79 == 0))
OR ((NOT (_277 == 0)) AND (NOT (_277 > 2)) AND (NOT (_277 == 2)) AND (_79 == 0))
OR ((NOT (pretmp_300 == 255)) AND (_277 == 0) AND (NOT (_277 > 2)) AND (NOT (_277 == 2)) AND (_79 == 0))
which we fail to simplify. The following patch makes us simplify
the relations on _277, producing
((_79 == 0) AND (_277 == 2))
OR ((_79 == 0) AND (_277 <= 1) AND (NOT (_277 == 0)))
OR ((_79 == 0) AND (_277 == 0) AND (NOT (pretmp_300 == 255)))
which might be an incremental step to resolve a bogus uninit
diagnostic at -O2. The patch uses maybe_fold_and_comparison for this.
PR tree-optimization/107919
* gimple-predicate-analysis.cc (simplify_1): Rename to ...
(simplify_1a): .. this.
(simplify_1b): New.
(predicate::simplify): Call both simplify_1a and simplify_1b.
|
|
We fail to simplify
((_145 != 0B) AND (_531 == 2) AND (_109 == 0))
OR ((NOT (_145 != 0B)) AND (_531 == 2) AND (_109 == 0))
OR ((NOT (_531 == 2)) AND (_109 == 0))
because the existing simplification of !A && B || A && B is implemented
too simplistic. The following re-implements that which fixes the
bogus uninit diagnostic when using -O1 but not yet at -O2.
PR tree-optimization/107919
* gimple-predicate-analysis.cc (predicate::simplify_2):
Handle predicates of arbitrary length.
* g++.dg/warn/Wuninitialized-pr107919-1.C: New testcase.
|
|
When looking at tree-inline.cc I've noticed a comment typo and grepped
for similar typos elsewhere.
2022-10-07 Jakub Jelinek <jakub@redhat.com>
* ipa-prop.h (ipa_constant_data): Fix comment typo.
* value-range.cc (irange::irange_contains_p): Likewise.
* value-relation.cc (dom_oracle::set_one_relation): Likewise.
* gimple-predicate-analysis.cc (predicate::simplify_4): Likewise.
* tree-inline.cc (remap_ssa_name): Likewise.
|
|
This adjusts simple_control_dep_chain in the same way I adjusted
compute_control_dep_chain_pdom to avoid adding fallthru edges to
the predicate chain.
PR tree-optimization/106881
* gimple-predicate-analysis.cc (simple_control_dep_chain):
Add only non-fallthru edges and avoid the same set of edges
as compute_control_dep_chain_pdom does.
|
|
The following avoids adding fallthru edges to the control chain from
the post-dominator walk.
PR tree-optimization/106881
* gimple-predicate-analysis.cc (compute_control_dep_chain_pdom):
Add only non-fallthru edges and avoid the same set of edges
as the caller does.
* gcc.dg/uninit-pr106881.c: New testcase.
|
|
The following makes sure to mark the dominating region also for
USE predicate discovery, avoiding compute_control_dep_chain to
walk to unrelated areas, eating up walking budget.
* gimple-predicate-analysis.cc (dfs_mark_dominating_region):
Adjust to take the region exit source as argument.
(uninit_analysis::init_from_phi_def): Adjust.
(uninit_analysis::init_use_preds): Mark the dominating region
before computing control dependences.
|
|
The following handles the situation of a loop exit along the
control path to the PHI def or from there to the use in a different
way, aoviding premature abort of the walks as noticed in the two
cases where the exit is outermost (gcc.dg/uninit-pred-11.c) or
wrapped in a condition that is on the path (gcc.dg/uninit-pred-12.c).
Instead of handling such exits during recursion we now pick them
up in the parent when walking post-dominators. That requires an
additional post-dominator walk at the outermost level which is
facilitated by splitting out the walk to a helper function and
the existing wrapper added earlier.
The patch also removes the bogus early exit from
uninit_analysis::init_use_preds, fixing a simplified version
of the PR106155 testcase.
PR tree-optimization/106754
* gimple-predicate-analysis.cc (compute_control_dep_chain_pdom):
New function, split out from compute_control_dep_chain. Handle
loop-exit like conditions here by pushing to the control vector.
(compute_control_dep_chain): Adjust and streamline dumping.
In the wrapper perform a post-dominator walk as well.
(uninit_analysis::init_use_preds): Remove premature early exit.
* gcc.dg/uninit-pred-12.c: New testcase.
* gcc.dg/uninit-pr106155-1.c: Likewise.
|
|
In uninit analysis we try to prove that a use is always properly guarded
so it is never reached when the used value is not initialized. This
fails to be conservative when during the computation of the use
predicate components of the || .. || .. chain are dropped so we have
to detect this case and fall back to the conservative computation.
* gimple-predicate-analysis.cc (compute_control_dep_chain):
Add output flag to indicate whether we possibly have dropped
any chains. Return whether the info is complete from the
wrapping overload.
(uninit_analysis::init_use_preds): Adjust accordingly, with
a workaround for PR106754.
(uninit_analysis::init_from_phi_def): Properly guard the
case where we complete an empty chain.
|
|
The following fixes an oversight in the last change to
compute_control_dep_chain where we have to return whether we found
a chain.
PR tree-optimization/106844
* gimple-predicate-analysis.cc (compute_control_dep_chain):
Return whether we found a chain.
* gcc.dg/pr106844.c: New testcase.
|
|
The following removes the MAX_SWITCH_CASES limit to fight quadraticness
when looking up case labels from edges. Instead use the
{start,end}_recording_case_labels facility for that. For it to be
usable I've exported get_cases_for_edge from tree-cfg.cc.
* tree-cfg.h (get_cases_for_edge): Declare.
* tree-cfg.cc (get_cases_for_edge): Export.
* tree-ssa-uninit.cc (execute_late_warn_uninitialized):
Start and end recording case labels.
* gimple-predicate-analysis.cc (MAX_SWITCH_CASES): Remove.
(predicate::init_from_control_deps): Use get_cases_for_edge.
|
|
The following unifies both limits, in particular the MAX_POSTDOM_CHECK
tends to be too low and is not user-controllable.
* gimple-predicate-analysis.cc (MAX_POSTDOM_CHECK): Remove.
(compute_control_dep_chain): Move uninit-control-dep-attempts
checking where it also counts the post-dominator check
invocations.
|
|
The following adds a debug () member to the predicate class.
* gimple-predicate-analysis.h (predicate::debug): New.
(predicate::dump): Add FILE * argument, add base overload.
* gimple-predicate-analysis.cc (debug): New.
(dump_pred_info): Add FILE * argument.
(dump_pred_chain): Likewise.
(predicate::dump): Split out preamble into overload. Add
FILE * argument.
(predicate::debug): New.
(predicate::simplify): Adjust.
(predicate::normalize): Likewise.
(predicate::init_from_control_deps): Likewise.
|
|
Now that we have DFS_BACK_EDGE marks we can simply avoid walking
those instead of repeatedly looking for a cycle on the current chain.
* gimple-predicate-analysis.cc (compute_control_dep_chain):
Remove cycle detection, instead avoid walking backedges.
|
|
The following hides some internal details of compute_control_dep_chain.
* gimple-predicate-analysis.cc (compute_control_dep_chain):
New wrapping overload.
(uninit_analysis::init_use_preds): Simplify.
(uninit_analysis::init_from_phi_def): Likewise.
|
|
When processing USE predicates we can drop from the AND chain,
when procsssing DEF predicates we can drop from the OR chain. Do
that instead of giving up completely. This also removes cases
that should never trigger.
* gimple-predicate-analysis.cc (predicate::init_from_control_deps):
Assert the guard_bb isn't empty and has more than one successor.
Drop appropriate parts of the predicate when an edge fails to
register a predicate.
(predicate::dump): Dump empty predicate as TRUE.
|
|
r12-3640-g94c12ffac234b2 sneaked in a hack to avoid the diagnostic
for the testcase in PR90994 which sees non-call EH control flow
confusing predicate analysis. The following patch instead adjusts
the existing code handling EH to handle non-calls and do what I
think was intented.
PR tree-optimization/90994
* gimple-predicate-analysis.cc (predicate::init_from_control_deps):
Ignore exceptional control flow and skip the edge for the purpose of
predicate generation also for non-calls.
* g++.dg/torture/pr90994.C: New testcase.
|
|
When uninit computes the actual predicates from the control dependence
edges it currently skips those that are assert-like (where one edge
leads to a block which ends in a noreturn call). That leads to
bogus uninit diagnostics when applied on the USE side.
PR tree-optimization/65244
* gimple-predicate-analysis.h (predicate::init_from_control_deps):
Add argument to specify whether the predicate is for the USE.
* gimple-predicate-analysis.cc (predicate::init_from_control_deps):
Also include predicates effective fallthru control edges when
the predicate is for the USE.
* gcc.dg/uninit-pr65244-2.c: New testcase.
|
|
The following makes predicate analysis handle case labels with
a non-singleton contiguous range.
PR tree-optimization/73550
* gimple-predicate-analysis.cc (predicate::init_from_control_deps):
Sanitize debug dumping. Handle case labels with a CASE_HIGH.
(predicate::dump): Adjust for better readability.
|
|
The MAX_NUM_CHAINS is applied once with <= and once with < which
results in the chains not limited but analyis dropped completely.
That's one issue in the PR.
PR tree-optimization/73550
* gimple-predicate-analysis.cc (predicate::init_from_control_deps):
Do not apply MAX_NUM_CHAINS again.
|
|
This produces less redundancy and more complete info dumping
the control dependence chains.
* gimple-predicate-analysis.cc (format_edge_vec): Dump
both source and destination.
(dump_dep_chains): Remove.
(uninit_analysis::init_use_preds): Remove redundant
dumping of chains.
|
|
The following makes sure to have use predicates simplified and
normalized before doing uninit_analysis::overlap because that
otherwise cannot pick up all flag setting cases. This fixes
half of the issue in PR67196 and conveniently resolves the
XFAIL in gcc.dg/uninit-pred-7_a.c.
PR tree-optimization/67196
* gimple-predicate-analysis.cc (uninit_analysis::is_use_guarded):
Simplify and normalize use prediates before first use.
* gcc.dg/uninit-pred-7_a.c: Un-XFAIL.
|
|
The following removes duplicate dumping and makes the predicate
dumping more readable. That makes the GENERIC predicate build
routines unused which is also nice.
* gimple-predicate-analysis.cc (dump_pred_chain): Fix
parentizing and AND prepending.
(predicate::dump): Do not dump the GENERIC expanded
predicate, properly parentize and prepend ORs to the
piecewise predicate dump.
(build_pred_expr): Remove.
|
|
Currently the main working of the maybe-uninit pass is to scan over
all PHIs with possibly undefined arguments, diagnosing whether there's
a direct not guarded use. For not guarded uses in PHIs those are queued for
later processing and to make the uninit analysis PHI def handling work,
mark the PHI def as possibly uninitialized. But this happens only
for those PHI uses that happen to be seen before a direct not guarded
use and whether all arguments of a PHI node which are defined by a PHI
are properly marked as maybe uninitialized depends on the processing
order.
The following changes the uninit pass to perform an RPO walk over
the function, ensuring that PHI argument defs are visited before
the PHI node (besides backedge uses which we ignore already),
getting rid of the worklist. It also makes sure to process all
PHI uses, but recording those that are properly guarded so they
are not treated as maybe undefined when processing the PHI use
later.
Overall this should make behavior more consistent, avoid some
false negative because of the previous early out and order issue,
and avoid some false positive because of the missed recording
of guarded PHI uses.
The patch correctly diagnoses an uninitalized use of 'regnum'
in store_bit_field_1 and also diagnoses an uninitialized use of
best_match::m_best_candidate_len in c-decl.cc which I've chosen to
silence by initializing m_best_candidate_len. The warning is
a false positive but GCC cannot see that m_best_candidate_len is
initialized when m_best_candidate is not NULL so from this
perspective this was a false negative. I've added
g++.dg/uninit-pred-5.C with a reduced testcase that nicely shows
how the previous behavior missed the diagnostic because the
worklist ended up visiting the PHI with the dependend uninit
value before visiting the PHIs producing it.
* gimple-predicate-analysis.h (uninit_analysis::operator()):
Remove.
* gimple-predicate-analysis.cc
(uninit_analysis::collect_phi_def_edges): Use phi_arg_set,
simplify a bit.
* tree-ssa-uninit.cc (defined_args): New global.
(compute_uninit_opnds_pos): Mask with the recorded set
of guarded maybe-uninitialized uses.
(uninit_undef_val_t::operator()): Remove.
(find_uninit_use): Process all PHI uses, recording the
guarded ones and marking the PHI result as uninitialized
consistently.
(warn_uninitialized_phi): Adjust.
(execute_late_warn_uninitialized): Get rid of the PHI worklist
and instead walk the function in RPO order.
* spellcheck.h (best_match::m_best_candidate_len): Initialize.
* g++.dg/uninit-pred-5.C: New testcase.
|
|
The following inlines find_control_equiv_block and is_loop_exit
into init_use_preds and refactors that for better readability and
similarity with the post-dominator walk in compute_control_dep_chain.
* gimple-predicate-analysis.cc (is_loop_exit,
find_control_equiv_block): Inline into single caller ...
(uninit_analysis::init_use_preds): ... here and refactor.
|
|
The following refactors compute_control_dep_chain slightly by
inlining is_loop_exit and factoring the check on the loop
invariant condition. It also adds a comment as of how I
understand the code and it's current problem.
* gimple-predicate-analysis.cc (compute_control_dep_chain):
Inline is_loop_exit and refactor, add comment about
loop exits.
|
|
As written earlier uninit_analysis::use_cannot_happen is duplicate
functionality implemented in a complement way, not adhering to
the idea of disproving a may-uninit use and eventually (I have not
yet found a testcase it helps to avoid false positives) avoiding
false positives because of this or different ways it imposes limits
on the predicate computations.
This patch removes it.
* gimple-predicate-analysis.h
(uninit_analysis::use_cannot_happen): Remove.
* gimple-predicate-analysis.cc (can_be_invalidated_p): Remove.
(uninit_analysis::use_cannot_happen): Likewise.
(uninit_analysis::is_use_guarded): Do not call
use_cannot_happen.
(dump_predicates): Remove.
(simple_control_dep_chain): Remove edge overload.
|
|
This improves the compute_control_dep_chain path finding by first
marking the dominating region we search and then making sure to
not walk outside if it when enumerating all paths from the dominating
block to the interesting PHI edge source. I have limited the DFS
walk done for the marking in similar ways as we limit the walking
in compute_control_dep_chain, more careful limiting might be
necessary though - the --param uninit-control-dep-attempts param
I re-use has a rather high default of 1000 which we might be able
to reduce with this patch as well (I think we'll usually hit some of the
other limits before ever reaching this).
* gimple-predicate-analysis.cc (dfs_mark_dominating_region):
New helper.
(compute_control_dep_chain): Adjust to honor marked region
if provided.
(uninit_analysis::init_from_phi_def): Pre-mark the dominating
region to improve compute_control_dep_chain walking.
* vec.h (vec<T, va_heap, vl_ptr>::allocated): Add forwarder.
|
|
This avoids expanding an edge to those of a PHI def if it is not
may-undefined, reducing the number of compute_control_dep_chain calls.
* gimple-predicate-analysis.cc
(uninit_analysis::collect_phi_def_edges): Only expand a
PHI def edge when it is possibly undefined.
|
|
This moves a few functions, notably normalization after a big comment
documenting it. I've left the rest unorganized for now.
* gimple-predicate-analysis.cc: Move predicate normalization
after the comment documenting it.
|
|
This splits the API collected in gimple-predicate-analysis.h into
what I'd call a predicate and assorted functionality plus utility
used by the uninit pass that happens to use that. I've tried to
be minimalistic with refactoring, there's still recursive
instantiation of uninit_analysis, the new class encapsulating a
series of uninit analysis queries from the uninit pass. But it
at least should make the predicate part actually reusable and
what predicate is dealt with is a little bit more clear in the
uninit_analysis part.
I will followup with moving the predicate implementation bits
together in the gimple-predicate-analysis.cc file.
* gimple-predicate-analysis.h (predicate): Split out
non-predicate related functionality into ..
(uninit_analysis): .. this new class.
* gimple-predicate-analysis.cc: Refactor into two classes.
* tree-ssa-uninit.cc (find_uninit_use): Use uninit_analysis.
|
|
This limits the simple control dep also to the cd_root plus avoids
filling the lazily computed PHI def predicate in the early out path
which would leave it not simplified and normalized if it were
re-used. It also avoids computing the use predicates when the
post-dominance early out doesn't need it. It also syncs
predicate::use_cannot_happen with init_from_phi_def, adding the
missing PHI edge to the computed chains (the simple control dep
code already adds it).
* gimple-predicate-analysis.cc (predicate::use_cannot_happen):
Do simple_control_dep_chain only up to cd_root, add the PHI
operand edge to the chains like init_from_phi_def does.
(predicate::is_use_guarded): Speedup early out, avoid half-way
initializing the PHI def predicate.
|
|
The following reverts a hunk from r8-5789-g11ef0b22d68cd1 that
made compute_control_dep_chain start from function entry rather
than the immediate dominator of the source block of the edge with
the undefined value on the PHI node. Reverting at that point
does not reveal any testsuite FAIL, in particular the added
testcase still passes. The following adjusts this to the other
function that computes predicates that hold on the PHI incoming
edges with undefined values, predicate::init_from_phi_def, which
starts at the immediate dominator of the PHI. That's much less
likely to run into the CFG walking limit.
* gimple-predicate-analysis.cc (predicate::use_cannot_happen):
Start the compute_control_dep_chain walk from the immediate
dominator of the PHI.
|
|
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.
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.
|
|
That's a weird function in predicate analysis that currently looks like
/* 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;
}
One can refactor this to
return (dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1)
&& !(single_pred_p (bb1) && !single_succ_p (bb2)));
Notable is that the comment refers to BB1 with respect to a loop
exit but the test seems to be written with an exit edge bb1 -> bb2
in mind. None of the three callers are guaranteed to have bb1 and
bb2 connected directly with an edge.
The patch now introduces a is_loop_exit function and inlines
the post-dominance check which makes the find_control_equiv_block
case simpler because the post-dominance check can be elided.
It also avoids the double negation in compute_control_dep_chain
and makes it obvious this is the case where we do look at an edge.
For the main is_use_guarded API I chose to elide the loop exit
test, if the use block post-dominates the definition block of the
PHI node the use is always unconditional. I don't quite understand
the loop exit special-casing of the remaining two uses though.
* gimple-predicate-analysis.cc (is_loop_exit): Split out
from ...
(is_non_loop_exit_postdominating): ... here. Remove after
inlining ...
(find_control_equiv_block): ... here.
(compute_control_dep_chain): ... and here.
(predicate::is_use_guarded): Do not excempt loop exits
from short-cutting the case of the use post-dominating the
PHI definition.
|
|
The following removes the unused def_expr, use_expr and expr APIs
from the predicate class including the unconditional build of the
GENERIC use_expr on each uninit analysis run.
* gimple-predicate-analysis.h (predicate::m_use_expr): Remove.
(predicate::def_expr): Likewise.
(predicate::use_expr): Likewise.
(predicate::expr): Likewise.
* gimple-predicate-analysis.cc (predicate::def_expr): Remove.
(predicate::use_expr): Likewise.
(predicate::expr): Likewise.
(predicate::is_use_guarded): Do not build m_use_expr.
|
|
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.
* 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.
|
|
|
|
This restores the semantics of can_be_invalidated_p to the original
semantics of the function this was split out from tree-ssa-uninit.c.
The current semantics only ever look at the first predicate which
cannot be correct.
2021-11-26 Richard Biener <rguenther@suse.de>
* gimple-predicate-analysis.cc (can_be_invalidated_p):
Restore semantics to the one before the split from
tree-ssa-uninit.c.
|
|
PR tree-optimization/102497
gcc/ChangeLog:
* gimple-predicate-analysis.cc (add_pred): Remove unused
function:
|
|
This removes now useless wrappers around get_immediate_dominator.
2021-11-11 Richard Biener <rguenther@suse.de>
* cfganal.c (find_pdom): Remove.
(control_dependences::find_control_dependence): Remove
special-casing of entry block, call get_immediate_dominator
directly.
* gimple-predicate-analysis.cc (find_pdom): Remove.
(find_dom): Likewise.
(find_control_equiv_block): Call get_immediate_dominator
directly.
(compute_control_dep_chain): Likewise.
(predicate::init_from_phi_def): Likewise.
|
