From patchwork Mon Sep 5 13:25:13 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 57365 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 6DDC9385702B for ; Mon, 5 Sep 2022 13:25:46 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6DDC9385702B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1662384346; bh=NaucDD+SM5Sz9nNbuAlxitK7ZKMrcWfRtOb1k+PChO0=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=wBdQvHMOi50gYB0rw2ReUQXJU1neUuKgjTvGgClOSRayMy3R0nL7TXnXCZQEPtPE2 aPC6S8AHh80LWyY/2plAz5v3IAucRmbyC1ev0THJdLNDkirLum3aBUMSlAsoI8h71G UMWX7S+mEWWa1ZXrHDCKoOQhTIVzwVsSmtYX7z/M= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id A817E385701F for ; Mon, 5 Sep 2022 13:25:14 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A817E385701F Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id D7B8133BCD for ; Mon, 5 Sep 2022 13:25:13 +0000 (UTC) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id C7928139C7 for ; Mon, 5 Sep 2022 13:25:13 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id oUC0L7n4FWPjHQAAMHmgww (envelope-from ) for ; Mon, 05 Sep 2022 13:25:13 +0000 Date: Mon, 5 Sep 2022 15:25:13 +0200 (CEST) To: gcc-patches@gcc.gnu.org Subject: [PATCH][RFC] Unify MAX_NUM_CHAINS and MAX_CHAIN_LEN to --param uninit-max-predicate-size MIME-Version: 1.0 Message-Id: <20220905132513.C7928139C7@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" The following exposes the MAX_NUM_CHAINS and MAX_CHAIN_LEN to the user by adding a --param uninit-max-predicate-size and re-doing the limits on the whole predicate expression size rather than limiting the number of OR and AND elements separately. The following goes a step further and for a single AND chain allows an arbitrary size, limiting that only with the computational --param uninit-control-dep-attempts parameter. That might be a bit high in practice, but it seems odd to continue searching for smaller and smaller paths until we exhaust the search space or uninit-control-dep-attempts. I'm testing this on x86_64-unknown-linux-gnu at the moment. Any comments? Thanks, Richard. * params.opt (uninit-max-predicate-size): New. * doc/invoke.texi (--param uninit-max-predicate-size): Document. * gimple-predicate-analysis.h (predicate::init_from_control_deps): Adjust. * gimple-predicate-analysis.cc (MAX_NUM_CHAINS, MAX_CHAIN_LEN): Remove. (format_edge_vecs): Adjust. (simple_control_dep_chain): Do not limit. (compute_control_dep_chain): Adjust limiting to the overall predicate expression size _after_ adding an element to the vector of AND chains. (predicate::init_from_control_deps): Adjust. (uninit_analysis::init_use_preds): Likewise. (uninit_analysis::init_from_phi_def): Likewise. --- gcc/doc/invoke.texi | 3 + gcc/gimple-predicate-analysis.cc | 113 ++++++++++++++++--------------- gcc/gimple-predicate-analysis.h | 2 +- gcc/params.opt | 4 ++ 4 files changed, 65 insertions(+), 57 deletions(-) diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 9d662e35316..f7e791224dc 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -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. diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc index 681047deee7..3b92bc5f505 100644 --- a/gcc/gimple-predicate-analysis.cc +++ b/gcc/gimple-predicate-analysis.cc @@ -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 &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 eva[], unsigned n) +format_edge_vecs (const vec > &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& 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 cd_chains[], unsigned *num_chains, + vec > &cd_chains, unsigned *chains_size, vec &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 cd_chains[], unsigned *num_chains, - unsigned in_region = 0) + vec > &cd_chains, unsigned in_region = 0) { - auto_vec cur_cd_chain; + auto_vec 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 *dep_chains, - unsigned num_chains, bool is_use) +predicate::init_from_control_deps (const vec > &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 *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 dep_chains[MAX_NUM_CHAINS]; + auto_vec, 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 dep_chains[MAX_NUM_CHAINS]; + auto_vec, 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 (); } diff --git a/gcc/gimple-predicate-analysis.h b/gcc/gimple-predicate-analysis.h index 972af5e0b2d..6474eaf3afb 100644 --- a/gcc/gimple-predicate-analysis.h +++ b/gcc/gimple-predicate-analysis.h @@ -65,7 +65,7 @@ class predicate return m_preds; } - void init_from_control_deps (const vec *, unsigned, bool); + void init_from_control_deps (const vec >&, bool); void dump (FILE *) const; void dump (FILE *, gimple *, const char *) const; diff --git a/gcc/params.opt b/gcc/params.opt index 3001566e641..e8e264dcb45 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -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.