@@ -15537,6 +15537,9 @@ when comparing to the number of (scaled) blocks.
Maximum number of nested calls to search for control dependencies
during uninitialized variable analysis.
+@item uninit-max-predicate-size
+The maximum size of a predicate recorded during uninitialized variable analysis.
+
@item fsm-scale-path-blocks
Scale factor to apply to the number of blocks in a threading path
when comparing to the number of (scaled) statements.
@@ -47,10 +47,13 @@
#define DEBUG_PREDICATE_ANALYZER 1
-/* In our predicate normal form we have MAX_NUM_CHAINS or predicates
- and in those MAX_CHAIN_LEN (inverted) and predicates. */
-#define MAX_NUM_CHAINS 8
-#define MAX_CHAIN_LEN 5
+/* In our predicate normal form we have a vector of OR predicates
+ and in those a vector of (inverted) AND predicates. Limit the
+ total amount of predicates to --param uninit-max-predicate-size
+ since we do O(n^2) operations on them. Note we apply this limit
+ only after discovering the first sub-predicate, the whole
+ discovery process is limited by --param uninit-control-dep-attempts
+ which limits the computational work done during discovery. */
/* Return true if X1 is the negation of X2. */
@@ -123,20 +126,19 @@ format_edge_vec (const vec<edge> &ev)
return str;
}
-/* Format the first N elements of the array of vector of edges EVA as
- a string. */
+/* Format the elements of the array of vector of edges EVA as a string. */
static std::string
-format_edge_vecs (const vec<edge> eva[], unsigned n)
+format_edge_vecs (const vec<vec<edge> > &eva)
{
std::string str;
- for (unsigned i = 0; i != n; ++i)
+ for (unsigned i = 0; i != eva.length (); ++i)
{
str += '{';
str += format_edge_vec (eva[i]);
str += '}';
- if (i + 1 < n)
+ if (i + 1 < eva.length ())
str += ", ";
}
return str;
@@ -921,8 +923,7 @@ simple_control_dep_chain (vec<edge>& chain, basic_block from, basic_block to)
return;
basic_block src = to;
- while (src != from
- && chain.length () <= MAX_CHAIN_LEN)
+ while (src != from)
{
basic_block dest = src;
src = get_immediate_dominator (CDI_DOMINATORS, src);
@@ -994,7 +995,7 @@ dfs_mark_dominating_region (edge exit, basic_block dom, int flag,
static bool
compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
- vec<edge> cd_chains[], unsigned *num_chains,
+ vec<vec<edge> > &cd_chains, unsigned *chains_size,
vec<edge> &cur_cd_chain, unsigned *num_calls,
unsigned in_region = 0, unsigned depth = 0)
{
@@ -1004,25 +1005,12 @@ compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
/* FIXME: Use a set instead. */
unsigned cur_chain_len = cur_cd_chain.length ();
- if (cur_chain_len > MAX_CHAIN_LEN)
- {
- if (dump_file)
- fprintf (dump_file, "MAX_CHAIN_LEN exceeded: %u\n", cur_chain_len);
-
- return false;
- }
-
- if (cur_chain_len > 5)
- {
- if (dump_file)
- fprintf (dump_file, "chain length exceeds 5: %u\n", cur_chain_len);
- }
if (DEBUG_PREDICATE_ANALYZER && dump_file)
fprintf (dump_file,
"%*s%s (dom_bb = %u, dep_bb = %u, cd_chains = { %s }, ...)\n",
depth, "", __func__, dom_bb->index, dep_bb->index,
- format_edge_vecs (cd_chains, *num_chains).c_str ());
+ format_edge_vecs (cd_chains).c_str ());
bool found_cd_chain = false;
@@ -1056,10 +1044,13 @@ compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
if (cd_bb == dep_bb)
{
/* Found a direct control dependence. */
- if (*num_chains < MAX_NUM_CHAINS)
+ cd_chains.safe_push (cur_cd_chain.copy ());
+ *chains_size += cur_cd_chain.length ();
+ if (*chains_size >= param_uninit_max_predicate_size)
{
- cd_chains[*num_chains] = cur_cd_chain.copy ();
- (*num_chains)++;
+ if (dump_file)
+ fprintf (dump_file, "--param uninit-max-predicate-size "
+ "reached: %u\n", cur_chain_len);
}
found_cd_chain = true;
/* Check path from next edge. */
@@ -1084,12 +1075,15 @@ compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
/* Check if DEP_BB is indirectly control-dependent on DOM_BB. */
if (!single_succ_p (cd_bb)
&& compute_control_dep_chain (cd_bb, dep_bb, cd_chains,
- num_chains, cur_cd_chain,
+ chains_size, cur_cd_chain,
num_calls, in_region, depth + 1))
{
found_cd_chain = true;
break;
}
+ /* Quickly terminate the walk. */
+ if (*chains_size >= param_uninit_max_predicate_size)
+ break;
/* The post-dominator walk will reach a backedge only
from a forwarder, otherwise it should choose to exit
@@ -1103,6 +1097,10 @@ compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
}
cur_cd_chain.pop ();
gcc_assert (cur_cd_chain.length () == cur_chain_len);
+
+ /* Quickly terminate the walk. */
+ if (*chains_size >= param_uninit_max_predicate_size)
+ break;
}
gcc_assert (cur_cd_chain.length () == cur_chain_len);
@@ -1111,13 +1109,13 @@ compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
static bool
compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
- vec<edge> cd_chains[], unsigned *num_chains,
- unsigned in_region = 0)
+ vec<vec<edge> > &cd_chains, unsigned in_region = 0)
{
- auto_vec<edge, MAX_CHAIN_LEN + 1> cur_cd_chain;
+ auto_vec<edge, 10> cur_cd_chain;
unsigned num_calls = 0;
+ unsigned chains_size = 0;
unsigned depth = 0;
- return compute_control_dep_chain (dom_bb, dep_bb, cd_chains, num_chains,
+ return compute_control_dep_chain (dom_bb, dep_bb, cd_chains, &chains_size,
cur_cd_chain, &num_calls, in_region, depth);
}
@@ -1655,7 +1653,7 @@ predicate::normalize (gimple *use_or_def, bool is_use)
/* Convert the chains of control dependence edges into a set of predicates.
A control dependence chain is represented by a vector edges. DEP_CHAINS
- points to an array of NUM_CHAINS dependence chains. One edge in
+ is an array of dependence chains. One edge in
a dependence chain is mapped to predicate expression represented by
pred_info type. One dependence chain is converted to a composite
predicate that is the result of AND operation of pred_info mapped to
@@ -1663,18 +1661,19 @@ predicate::normalize (gimple *use_or_def, bool is_use)
pred_info. Sets M_PREDS to the resulting composite predicates. */
void
-predicate::init_from_control_deps (const vec<edge> *dep_chains,
- unsigned num_chains, bool is_use)
+predicate::init_from_control_deps (const vec<vec<edge> > &dep_chains,
+ bool is_use)
{
gcc_assert (is_empty ());
+ unsigned num_chains = dep_chains.length ();
if (num_chains == 0)
return;
if (DEBUG_PREDICATE_ANALYZER && dump_file)
fprintf (dump_file, "init_from_control_deps [%s] {%s}:\n",
is_use ? "USE" : "DEF",
- format_edge_vecs (dep_chains, num_chains).c_str ());
+ format_edge_vecs (dep_chains).c_str ());
/* Convert the control dependency chain into a set of predicates. */
m_preds.reserve (num_chains);
@@ -1768,9 +1767,8 @@ predicate::init_from_control_deps (const vec<edge> *dep_chains,
else
{
/* Support a case label with a range with
- two predicates. We're overcommitting on
- the MAX_CHAIN_LEN budget by at most a factor
- of two here. */
+ two predicates. This at most doubles the
+ number of predicates. */
pred_info one_pred;
one_pred.pred_lhs = gimple_switch_index (gs);
one_pred.pred_rhs = CASE_LOW (l);
@@ -1916,14 +1914,13 @@ uninit_analysis::init_use_preds (predicate &use_preds, basic_block def_bb,
Each DEP_CHAINS element is a series of edges whose conditions
are logical conjunctions. Together, the DEP_CHAINS vector is
used below to initialize an OR expression of the conjunctions. */
- unsigned num_chains = 0;
- auto_vec<edge> dep_chains[MAX_NUM_CHAINS];
+ auto_vec<vec<edge>, 8> dep_chains;
- if (!compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains))
+ if (!compute_control_dep_chain (cd_root, use_bb, dep_chains))
{
- gcc_assert (num_chains == 0);
+ gcc_assert (dep_chains.length () == 0);
+ dep_chains.safe_push (vNULL);
simple_control_dep_chain (dep_chains[0], cd_root, use_bb);
- num_chains++;
}
if (DEBUG_PREDICATE_ANALYZER && dump_file)
@@ -1934,7 +1931,11 @@ uninit_analysis::init_use_preds (predicate &use_preds, basic_block def_bb,
condition under which the definition in DEF_BB is used in USE_BB.
Each OR subexpression is represented by one element of DEP_CHAINS,
where each element consists of a series of AND subexpressions. */
- use_preds.init_from_control_deps (dep_chains, num_chains, true);
+ use_preds.init_from_control_deps (dep_chains, true);
+
+ for (auto v : dep_chains)
+ v.release ();
+
return !use_preds.is_empty ();
}
@@ -2015,21 +2016,19 @@ uninit_analysis::init_from_phi_def (gphi *phi)
if (!dfs_mark_dominating_region (def_edges[i], cd_root, in_region, region))
break;
- unsigned num_chains = 0;
- auto_vec<edge> dep_chains[MAX_NUM_CHAINS];
+ auto_vec<vec<edge>, 8> dep_chains;
for (unsigned i = 0; i < nedges; i++)
{
edge e = def_edges[i];
- unsigned prev_nc = num_chains;
- compute_control_dep_chain (cd_root, e->src, dep_chains,
- &num_chains, in_region);
+ unsigned prev_nc = dep_chains.length ();
+ compute_control_dep_chain (cd_root, e->src, dep_chains, in_region);
/* Update the newly added chains with the phi operand edge. */
if (EDGE_COUNT (e->src->succs) > 1)
{
- if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS)
- dep_chains[num_chains++] = vNULL;
- for (unsigned j = prev_nc; j < num_chains; j++)
+ if (prev_nc == dep_chains.length ())
+ dep_chains.safe_push (vNULL);
+ for (unsigned j = prev_nc; j < dep_chains.length (); j++)
dep_chains[j].safe_push (e);
}
}
@@ -2041,7 +2040,9 @@ uninit_analysis::init_from_phi_def (gphi *phi)
/* Convert control dependence chains to the predicate in *THIS under
which the PHI operands are defined to values for which M_EVAL is
false. */
- m_phi_def_preds.init_from_control_deps (dep_chains, num_chains, false);
+ m_phi_def_preds.init_from_control_deps (dep_chains, false);
+ for (auto v : dep_chains)
+ v.release ();
return !m_phi_def_preds.is_empty ();
}
@@ -65,7 +65,7 @@ class predicate
return m_preds;
}
- void init_from_control_deps (const vec<edge> *, unsigned, bool);
+ void init_from_control_deps (const vec<vec<edge> >&, bool);
void dump (FILE *) const;
void dump (FILE *, gimple *, const char *) const;
@@ -1097,6 +1097,10 @@ Emit instrumentation calls to __tsan_func_entry() and __tsan_func_exit().
Common Joined UInteger Var(param_uninit_control_dep_attempts) Init(1000) IntegerRange(1, 65536) Param Optimization
Maximum number of nested calls to search for control dependencies during uninitialized variable analysis.
+-param=uninit-max-predicate-size=
+Common Joined UInteger Var(param_uninit_max_predicate_size) Init(40) IntegerRange(1, 65536) Param Optimization
+Maximum size of a predicate recorded during uninitialized variable analysis.
+
-param=uninlined-function-insns=
Common Joined UInteger Var(param_uninlined_function_insns) Init(2) Optimization IntegerRange(0, 1000000) Param
Instruction accounted for function prologue, epilogue and other overhead.