From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1666) id E212C385117E; Tue, 6 Sep 2022 12:56:00 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E212C385117E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1662468960; bh=heXaj9Wdl3ujD3PBu770W+Hz2mJ3aOxOt32gW4UHOCo=; h=From:To:Subject:Date:From; b=bTzob4JEzbzA+ppO2TK+cc+j92kESmx/OtMC+cls2quuRJrwAdHAIJGGhFyMCwxFd cinhz7qSMmWuioqIut4aaGKj97nStS7JI2KjjbkzClGHF3Uu6Hm61xnaoiWtikB7zo wgK1QCrqCM4HjpKSKD0s0C6fBhOLAm9zHKsIRb44= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Richard Biener To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-2500] tree-optimization/106754 - fix compute_control_dep_chain defect X-Act-Checkin: gcc X-Git-Author: Richard Biener X-Git-Refname: refs/heads/master X-Git-Oldrev: 9e0c2696724d4d004ea189a69f15781c7baa68e1 X-Git-Newrev: 0a4a2667dc115ca73b552fcabf8570620dfbe55f Message-Id: <20220906125600.E212C385117E@sourceware.org> Date: Tue, 6 Sep 2022 12:56:00 +0000 (GMT) List-Id: https://gcc.gnu.org/g:0a4a2667dc115ca73b552fcabf8570620dfbe55f commit r13-2500-g0a4a2667dc115ca73b552fcabf8570620dfbe55f Author: Richard Biener Date: Tue Sep 6 13:46:00 2022 +0200 tree-optimization/106754 - fix compute_control_dep_chain defect The following handles the situation of a loop exit along the control path to the PHI def or from there to the use in a different way, aoviding premature abort of the walks as noticed in the two cases where the exit is outermost (gcc.dg/uninit-pred-11.c) or wrapped in a condition that is on the path (gcc.dg/uninit-pred-12.c). Instead of handling such exits during recursion we now pick them up in the parent when walking post-dominators. That requires an additional post-dominator walk at the outermost level which is facilitated by splitting out the walk to a helper function and the existing wrapper added earlier. The patch also removes the bogus early exit from uninit_analysis::init_use_preds, fixing a simplified version of the PR106155 testcase. PR tree-optimization/106754 * gimple-predicate-analysis.cc (compute_control_dep_chain_pdom): New function, split out from compute_control_dep_chain. Handle loop-exit like conditions here by pushing to the control vector. (compute_control_dep_chain): Adjust and streamline dumping. In the wrapper perform a post-dominator walk as well. (uninit_analysis::init_use_preds): Remove premature early exit. * gcc.dg/uninit-pred-12.c: New testcase. * gcc.dg/uninit-pr106155-1.c: Likewise. Diff: --- gcc/gimple-predicate-analysis.cc | 186 ++++++++++++++++++------------- gcc/testsuite/gcc.dg/uninit-pr106155-1.c | 40 +++++++ gcc/testsuite/gcc.dg/uninit-pred-12.c | 34 ++++++ 3 files changed, 180 insertions(+), 80 deletions(-) diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc index ac34b7007a6..5dade458947 100644 --- a/gcc/gimple-predicate-analysis.cc +++ b/gcc/gimple-predicate-analysis.cc @@ -981,6 +981,94 @@ dfs_mark_dominating_region (edge exit, basic_block dom, int flag, return true; } +static bool +compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb, + vec cd_chains[], unsigned *num_chains, + vec &cur_cd_chain, unsigned *num_calls, + unsigned in_region, unsigned depth, + bool *complete_p); + +/* Helper for compute_control_dep_chain that walks the post-dominator + chain from CD_BB up unto TARGET_BB looking for paths to DEP_BB. */ + +static bool +compute_control_dep_chain_pdom (basic_block cd_bb, const_basic_block dep_bb, + basic_block target_bb, + vec cd_chains[], unsigned *num_chains, + vec &cur_cd_chain, unsigned *num_calls, + unsigned in_region, unsigned depth, + bool *complete_p) +{ + bool found_cd_chain = false; + while (cd_bb != target_bb) + { + if (cd_bb == dep_bb) + { + /* Found a direct control dependence. */ + if (*num_chains < MAX_NUM_CHAINS) + { + if (DEBUG_PREDICATE_ANALYZER && dump_file) + fprintf (dump_file, "%*s pushing { %s }\n", + depth, "", format_edge_vec (cur_cd_chain).c_str ()); + cd_chains[*num_chains] = cur_cd_chain.copy (); + (*num_chains)++; + } + found_cd_chain = true; + /* Check path from next edge. */ + break; + } + + /* If the dominating region has been marked avoid walking outside. */ + if (in_region != 0 && !(cd_bb->flags & in_region)) + break; + + /* Count the number of steps we perform to limit compile-time. + This should cover both recursion and the post-dominator walk. */ + if (*num_calls > (unsigned)param_uninit_control_dep_attempts) + { + if (dump_file) + fprintf (dump_file, "param_uninit_control_dep_attempts " + "exceeded: %u\n", *num_calls); + *complete_p = false; + break; + } + ++*num_calls; + + /* 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, + num_calls, in_region, depth + 1, + complete_p)) + { + found_cd_chain = true; + break; + } + + /* The post-dominator walk will reach a backedge only + from a forwarder, otherwise it should choose to exit + the SCC. */ + if (single_succ_p (cd_bb) + && single_succ_edge (cd_bb)->flags & EDGE_DFS_BACK) + break; + basic_block prev_cd_bb = cd_bb; + cd_bb = get_immediate_dominator (CDI_POST_DOMINATORS, cd_bb); + if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) + break; + /* Pick up conditions toward the post dominator such like + loop exit conditions. See gcc.dg/uninit-pred-11.c and + gcc.dg/unninit-pred-12.c and PR106754. */ + if (single_pred_p (cd_bb)) + { + edge e2 = find_edge (prev_cd_bb, cd_bb); + gcc_assert (e2); + cur_cd_chain.safe_push (e2); + } + } + return found_cd_chain; +} + + /* Recursively compute the control dependence chains (paths of edges) from the dependent basic block, DEP_BB, up to the dominating basic block, DOM_BB (the head node of a chain should be dominated by it), @@ -1024,9 +1112,10 @@ compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb, if (DEBUG_PREDICATE_ANALYZER && dump_file) fprintf (dump_file, - "%*s%s (dom_bb = %u, dep_bb = %u, cd_chains = { %s }, ...)\n", + "%*s%s (dom_bb = %u, dep_bb = %u, ..., " + "cur_cd_chain = { %s }, ...)\n", depth, "", __func__, dom_bb->index, dep_bb->index, - format_edge_vecs (cd_chains, *num_chains).c_str ()); + format_edge_vec (cur_cd_chain).c_str ()); bool found_cd_chain = false; @@ -1039,75 +1128,17 @@ compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb, continue; basic_block cd_bb = e->dest; + unsigned pop_mark = cur_cd_chain.length (); cur_cd_chain.safe_push (e); - while (!dominated_by_p (CDI_POST_DOMINATORS, dom_bb, cd_bb) - /* We want to stop when the CFG merges back from the - branch in dom_bb. The post-dominance check alone - falls foul of the case of a loop exit test branch - where the path on the loop exit post-dominates - the branch block. - The following catches this but will not allow - exploring the post-dom path further. For the - outermost recursion this means we will fail to - reach dep_bb while for others it means at least - dropping the loop exit predicate from the path - which is problematic as it increases the domain - spanned by the resulting predicate. - See gcc.dg/uninit-pred-11.c for the first case - and PR106754 for the second. */ - || single_pred_p (cd_bb)) - { - if (cd_bb == dep_bb) - { - /* Found a direct control dependence. */ - if (*num_chains < MAX_NUM_CHAINS) - { - cd_chains[*num_chains] = cur_cd_chain.copy (); - (*num_chains)++; - } - found_cd_chain = true; - /* Check path from next edge. */ - break; - } - - /* If the dominating region has been marked avoid walking outside. */ - if (in_region != 0 && !(cd_bb->flags & in_region)) - break; - - /* Count the number of steps we perform to limit compile-time. - This should cover both recursion and the post-dominator walk. */ - if (*num_calls > (unsigned)param_uninit_control_dep_attempts) - { - if (dump_file) - fprintf (dump_file, "param_uninit_control_dep_attempts " - "exceeded: %u\n", *num_calls); - *complete_p = false; - break; - } - ++*num_calls; - - /* 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, - num_calls, in_region, depth + 1, - complete_p)) - { - found_cd_chain = true; - break; - } - - /* The post-dominator walk will reach a backedge only - from a forwarder, otherwise it should choose to exit - the SCC. */ - if (single_succ_p (cd_bb) - && single_succ_edge (cd_bb)->flags & EDGE_DFS_BACK) - break; - cd_bb = get_immediate_dominator (CDI_POST_DOMINATORS, cd_bb); - if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) - break; - } - cur_cd_chain.pop (); + basic_block target_bb + = get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb); + /* Walk the post-dominator chain up to the CFG merge. */ + found_cd_chain + |= compute_control_dep_chain_pdom (cd_bb, dep_bb, target_bb, + cd_chains, num_chains, + cur_cd_chain, num_calls, + in_region, depth, complete_p); + cur_cd_chain.truncate (pop_mark); gcc_assert (cur_cd_chain.length () == cur_chain_len); } @@ -1127,9 +1158,10 @@ compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb, unsigned num_calls = 0; unsigned depth = 0; bool complete_p = true; - compute_control_dep_chain (dom_bb, dep_bb, cd_chains, num_chains, - cur_cd_chain, &num_calls, in_region, depth, - &complete_p); + /* Walk the post-dominator chain. */ + compute_control_dep_chain_pdom (dom_bb, dep_bb, NULL, cd_chains, + num_chains, cur_cd_chain, &num_calls, + in_region, depth, &complete_p); return complete_p; } @@ -1935,9 +1967,7 @@ uninit_analysis::init_use_preds (predicate &use_preds, basic_block def_bb, unsigned num_chains = 0; auto_vec dep_chains[MAX_NUM_CHAINS]; - if (!compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains) - /* ??? Workaround PR106754. */ - || num_chains == 0) + if (!compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains)) { /* If the info in dep_chains is not complete we need to use a conservative approximation for the use predicate. */ @@ -2099,10 +2129,6 @@ uninit_analysis::is_use_guarded (gimple *use_stmt, basic_block use_bb, /* The basic block where the PHI is defined. */ basic_block def_bb = gimple_bb (phi); - if (dominated_by_p (CDI_POST_DOMINATORS, def_bb, use_bb)) - /* The use is not guarded. */ - return false; - /* Try to build the predicate expression under which the PHI flows into its use. This will be empty if the PHI is defined and used in the same bb. */ diff --git a/gcc/testsuite/gcc.dg/uninit-pr106155-1.c b/gcc/testsuite/gcc.dg/uninit-pr106155-1.c new file mode 100644 index 00000000000..5c4410deec8 --- /dev/null +++ b/gcc/testsuite/gcc.dg/uninit-pr106155-1.c @@ -0,0 +1,40 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fno-ivopts -Wuninitialized" } */ + +int *e; +int f1 (void); +void f2 (int); +long f3 (void *, long, int *); +void f4 (void *); +int *fh; + +void tst (void) +{ + int status; + unsigned char badData[3][3] = { { 7 }, { 16 }, { 23 } }; + int badDataSize[3] = { 1, 1, 1 }; + int i; + + for (i = 0; i < 3; i++) + { + int emax; + if (i == 2) + emax = f1 (); + status = f3 (&badData[i][0], badDataSize[i], fh); + if (status) + { + f1 (); + f1 (); + f1 (); + } + f4 (fh); + *e = 0; + f1 (); + /* When threading the following out of the loop uninit + analysis needs to pick up the loop exit condition + to match up with this guard. + ??? This doesn't work reliably when IVOPTs is run. */ + if (i == 2) + f2 (emax); /* { dg-bogus "uninitialized" } */ + } +} diff --git a/gcc/testsuite/gcc.dg/uninit-pred-12.c b/gcc/testsuite/gcc.dg/uninit-pred-12.c new file mode 100644 index 00000000000..ebf0288af1f --- /dev/null +++ b/gcc/testsuite/gcc.dg/uninit-pred-12.c @@ -0,0 +1,34 @@ +/* { dg-do compile } */ +/* { dg-options "-O -Wmaybe-uninitialized -fdump-tree-uninit1" } */ + +extern unsigned bar (void); +extern void quux (void); +int z; +unsigned foo (unsigned v, int y, int w) +{ + unsigned u; + if (v != 1) + u = bar (); + + // Prevent the "dom" pass from changing the CFG layout based on the inference + // 'if (v != 1) is false then (v != 2) is true'. (Now it would have to + // duplicate the loop in order to do so, which is deemed expensive.) + for (int i = 0; i < 10; i++) + quux (); + + // This variantion from uninit-pred-11.c caused compute_control_dep_chain + // to run into a defect, producing z != 0 && v != 1, omitting !(i<10) + // from the path predicate + if (w) + { + if (y) + z = 1; + if (v != 1) + return u; /* { dg-bogus "may be used uninitialized" } */ + } + + return 0; +} + +/* Make sure predicate analysis picked up the loop exit condition. */ +/* { dg-final { scan-tree-dump "AND \\(NOT \\(ivtmp" "uninit1" } } */