[PATCH] Bound number of recursive compute_control_dep_chain calls with a param (PR tree-optimization/56490)

[Jakub Jelinek <jakub at redhat dot com>]

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?

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