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 <ja...@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 <rguent...@suse.de> SUSE / SUSE Labs SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 GF: Jeff Hawn, Jennifer Guild, Felix Imend"orffer