[PATCH] Bound number of recursive compute_control_dep_chain calls with a param (PR tree-optimization/56490)
Richard Biener
rguenther@suse.de
Fri Feb 21 09:16:00 GMT 2014
On Fri, 21 Feb 2014, Jakub Jelinek wrote:
> Hi!
>
> As discussed in the PR, on larger functions we can end up with
> over 3 million of compute_control_dep_chain nested calls from
> a single compute_control_dep_chain call, on that testcase all that
> effort just to get zero or at most one (useless) control dep path.
> The problem is that the function is really unbound, even with the
> 6 element path length limitation (recursion depth) and the limit of 8
> find_pdom calls - everything still iterates on all the successor edges at
> each level. And, the function is often called on the same basic block
> again and again, even at a particular depth level (e.g. over 200000 times
> same bb same depth level). But the preceeding edge list is slightly
> different in each case and in theory it could give different answers.
>
> Fixed by bounding the total number of nested calls.
>
> Additionally, I've made a couple of cleanups, heap allocating 8 field array
> instead of using an automatic array makes no sense, the chain length is at
> most 6 and thus we can use a stack vector, etc.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
Ok.
Thanks,
Richard.
> 2014-02-21 Jakub Jelinek <jakub@redhat.com>
>
> PR tree-optimization/56490
> * params.def (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS): New param.
> * tree-ssa-uninit.c: Include params.h.
> (compute_control_dep_chain): Add num_calls argument, return false
> if it exceed PARAM_UNINIT_CONTROL_DEP_ATTEMPTS param, pass
> num_calls to recursive call.
> (find_predicates): Change dep_chain into normal array,
> cur_chain into auto_vec<edge, MAX_CHAIN_LEN + 1>, add num_calls
> variable and adjust compute_control_dep_chain caller.
> (find_def_preds): Likewise.
>
> --- gcc/params.def.jj 2014-01-09 19:09:47.000000000 +0100
> +++ gcc/params.def 2014-02-20 19:30:37.467597338 +0100
> @@ -1078,6 +1078,12 @@ DEFPARAM (PARAM_ASAN_USE_AFTER_RETURN,
> "asan-use-after-return",
> "Enable asan builtin functions protection",
> 1, 0, 1)
> +
> +DEFPARAM (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS,
> + "uninit-control-dep-attempts",
> + "Maximum number of nested calls to search for control dependencies "
> + "during uninitialized variable analysis",
> + 1000, 1, 0)
> /*
>
> Local variables:
> --- gcc/tree-ssa-uninit.c.jj 2014-02-04 01:35:58.000000000 +0100
> +++ gcc/tree-ssa-uninit.c 2014-02-20 19:31:14.198385817 +0100
> @@ -44,6 +44,7 @@ along with GCC; see the file COPYING3.
> #include "hashtab.h"
> #include "tree-pass.h"
> #include "diagnostic-core.h"
> +#include "params.h"
>
> /* This implements the pass that does predicate aware warning on uses of
> possibly uninitialized variables. The pass first collects the set of
> @@ -390,8 +391,8 @@ find_control_equiv_block (basic_block bb
>
> /* Computes the control dependence chains (paths of edges)
> for DEP_BB up to the dominating basic block BB (the head node of a
> - chain should be dominated by it). CD_CHAINS is pointer to a
> - dynamic array holding the result chains. CUR_CD_CHAIN is the current
> + chain should be dominated by it). CD_CHAINS is pointer to an
> + array holding the result chains. CUR_CD_CHAIN is the current
> chain being computed. *NUM_CHAINS is total number of chains. The
> function returns true if the information is successfully computed,
> return false if there is no control dependence or not computed. */
> @@ -400,7 +401,8 @@ static bool
> compute_control_dep_chain (basic_block bb, basic_block dep_bb,
> vec<edge> *cd_chains,
> size_t *num_chains,
> - vec<edge> *cur_cd_chain)
> + vec<edge> *cur_cd_chain,
> + int *num_calls)
> {
> edge_iterator ei;
> edge e;
> @@ -411,6 +413,10 @@ compute_control_dep_chain (basic_block b
> if (EDGE_COUNT (bb->succs) < 2)
> return false;
>
> + if (*num_calls > PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS))
> + return false;
> + ++*num_calls;
> +
> /* Could use a set instead. */
> cur_chain_len = cur_cd_chain->length ();
> if (cur_chain_len > MAX_CHAIN_LEN)
> @@ -450,7 +456,7 @@ compute_control_dep_chain (basic_block b
>
> /* Now check if DEP_BB is indirectly control dependent on BB. */
> if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains,
> - num_chains, cur_cd_chain))
> + num_chains, cur_cd_chain, num_calls))
> {
> found_cd_chain = true;
> break;
> @@ -595,14 +601,12 @@ find_predicates (pred_chain_union *preds
> basic_block use_bb)
> {
> size_t num_chains = 0, i;
> - vec<edge> *dep_chains = 0;
> - vec<edge> cur_chain = vNULL;
> + int num_calls = 0;
> + vec<edge> dep_chains[MAX_NUM_CHAINS];
> + auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
> bool has_valid_pred = false;
> basic_block cd_root = 0;
>
> - typedef vec<edge> vec_edge_heap;
> - dep_chains = XCNEWVEC (vec_edge_heap, MAX_NUM_CHAINS);
> -
> /* First find the closest bb that is control equivalent to PHI_BB
> that also dominates USE_BB. */
> cd_root = phi_bb;
> @@ -615,19 +619,13 @@ find_predicates (pred_chain_union *preds
> break;
> }
>
> - compute_control_dep_chain (cd_root, use_bb,
> - dep_chains, &num_chains,
> - &cur_chain);
> + compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
> + &cur_chain, &num_calls);
>
> has_valid_pred
> - = convert_control_dep_chain_into_preds (dep_chains,
> - num_chains,
> - preds);
> - /* Free individual chain */
> - cur_chain.release ();
> + = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
> for (i = 0; i < num_chains; i++)
> dep_chains[i].release ();
> - free (dep_chains);
> return has_valid_pred;
> }
>
> @@ -694,16 +692,13 @@ static bool
> find_def_preds (pred_chain_union *preds, gimple phi)
> {
> size_t num_chains = 0, i, n;
> - vec<edge> *dep_chains = 0;
> - vec<edge> cur_chain = vNULL;
> + vec<edge> dep_chains[MAX_NUM_CHAINS];
> + auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
> vec<edge> def_edges = vNULL;
> bool has_valid_pred = false;
> basic_block phi_bb, cd_root = 0;
> pointer_set_t *visited_phis;
>
> - typedef vec<edge> vec_edge_heap;
> - dep_chains = XCNEWVEC (vec_edge_heap, MAX_NUM_CHAINS);
> -
> phi_bb = gimple_bb (phi);
> /* First find the closest dominating bb to be
> the control dependence root */
> @@ -722,37 +717,29 @@ find_def_preds (pred_chain_union *preds,
> for (i = 0; i < n; i++)
> {
> size_t prev_nc, j;
> + int num_calls = 0;
> edge opnd_edge;
>
> opnd_edge = def_edges[i];
> prev_nc = num_chains;
> - compute_control_dep_chain (cd_root, opnd_edge->src,
> - dep_chains, &num_chains,
> - &cur_chain);
> - /* Free individual chain */
> - cur_chain.release ();
> + compute_control_dep_chain (cd_root, opnd_edge->src, dep_chains,
> + &num_chains, &cur_chain, &num_calls);
>
> /* Now update the newly added chains with
> the phi operand edge: */
> if (EDGE_COUNT (opnd_edge->src->succs) > 1)
> {
> - if (prev_nc == num_chains
> - && num_chains < MAX_NUM_CHAINS)
> - num_chains++;
> + if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS)
> + dep_chains[num_chains++] = vNULL;
> for (j = prev_nc; j < num_chains; j++)
> - {
> - dep_chains[j].safe_push (opnd_edge);
> - }
> + dep_chains[j].safe_push (opnd_edge);
> }
> }
>
> has_valid_pred
> - = convert_control_dep_chain_into_preds (dep_chains,
> - num_chains,
> - preds);
> + = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
> for (i = 0; i < num_chains; i++)
> dep_chains[i].release ();
> - free (dep_chains);
> return has_valid_pred;
> }
>
>
> Jakub
>
>
--
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend"orffer
More information about the Gcc-patches
mailing list