From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qk1-x731.google.com (mail-qk1-x731.google.com [IPv6:2607:f8b0:4864:20::731]) by sourceware.org (Postfix) with ESMTPS id 07B883959E68 for ; Thu, 2 Jun 2022 09:23:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 07B883959E68 Received: by mail-qk1-x731.google.com with SMTP id m68so3221628qkb.9 for ; Thu, 02 Jun 2022 02:23:41 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=T1lGrIZWTx6Em0P5ezzzwELdHaieXxSuCzYwiryVmsE=; b=Y7/blUIc55g9YmPoHSsJgv0/sK7VqmW6MMlGKBk97UfjkEK+MhsqEbTlTcHxZuYNcv vY/lzn1eJ+zwBu4wbEB9cLudYu1LH4KSa9IeIa8Ivv/i7n4MKzVfBz6S7/WQvtKMwkIR u/nwe2Qn77MesRwYnMbAu5MBoELWk+18wz0tlMBAQkx0YgCdEC6kKDGXBPnFdofo/cih 1CgkuW4XZUiqXO24hQu8oPFu1C7BC4JaSoZFNb4hUBl4mjeJSOa5fnUv4Kp8ZDZf8vB9 DTaJWG/wBomNqhQSF72Jrp2Cpno2+2o1IFWFxsF8qKuXFOHL1OiiRDwYB1Rc5LwxnyeI /ALQ== X-Gm-Message-State: AOAM533NWn/r3TFHxRNYgyJhLReCTHlSgAyfC/fQZcg+Ddqwog55rvqA wBIO5QjeRGWA42B7UjDxs4hf6+GpEeQ8/qW3ShZcaelDOO8= X-Google-Smtp-Source: ABdhPJwqchnDxrx0HtzWq4UyVamkQ/ikHRXk7K8zxE8fazgE+Yt/GfLkTSEFq/fiRAfLUrd7Nh6Z4CIpv/y1IAFzBh8= X-Received: by 2002:a05:620a:190e:b0:6a6:2de8:8eba with SMTP id bj14-20020a05620a190e00b006a62de88ebamr2335958qkb.627.1654161820356; Thu, 02 Jun 2022 02:23:40 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Richard Biener Date: Thu, 2 Jun 2022 11:23:29 +0200 Message-ID: Subject: Re: [PATCH] [PR105665] ivopts: check defs of names in base for undefs To: Alexandre Oliva Cc: GCC Patches , Bin Cheng Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-7.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, 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-List-Received-Date: Thu, 02 Jun 2022 09:23:43 -0000 On Thu, Jun 2, 2022 at 9:10 AM Alexandre Oliva wrote: > > On Jun 1, 2022, Alexandre Oliva wrote: > > > Now I'm thinking we can go for an even stricter predicate to disable > > the optimization: if a non-PHI use of a maybe-undefined dominates the > > loop, then we can still perform the optimization: > > Here it is. > > > [PR105665] ivopts: check defs of names in base for undefs > > From: Alexandre Oliva > > The patch for PR 100810 tested for undefined SSA_NAMEs appearing > directly in the base expression of the potential IV candidate, but > that's not enough. The testcase for PR105665 shows an undefined > SSA_NAME has the same ill effect if it's referenced as an PHI_NODE arg > in the referenced SSA_NAME. The variant of that test shows it can be > further removed from the referenced SSA_NAME. > > To avoid deep recursion, precompute maybe-undefined SSA_NAMEs: start > from known-undefined nonvirtual default defs, and propagate them to > any PHI nodes reached by a maybe-undefined arg, as long as there > aren't intervening non-PHI uses, that would imply the maybe-undefined > name must be defined at that point, otherwise it would invoke > undefined behavior. Also test for intervening non-PHI uses of DEFs in > the base expr. > > The test for intervening uses implemented herein relies on dominance; > this could be further extended, regarding conditional uses in every > path leading to a point as an unconditional use dominating that point, > but I haven't implemented that. > > > for gcc/ChangeLog > > PR tree-optimization/105665 > PR tree-optimization/100810 > * tree-ssa-loop-ivopts.cc > (ssa_name_maybe_undef_p, ssa_name_set_maybe_undef): New. > (ssa_name_any_use_dominates_bb_p, mark_ssa_maybe_undefs): New. > (find_ssa_undef): Check precomputed flag and intervening uses. > (tree_ssa_iv_optimize): Call mark_ssa_maybe_undefs. > > for gcc/testsuite/ChangeLog > > PR tree-optimization/105665 > PR tree-optimization/100810 > * gcc.dg/torture/pr105665.c: New. > --- > gcc/testsuite/gcc.dg/torture/pr105665.c | 20 +++++ > gcc/tree-ssa-loop-ivopts.cc | 124 ++++++++++++++++++++++++++++++- > 2 files changed, 140 insertions(+), 4 deletions(-) > create mode 100644 gcc/testsuite/gcc.dg/torture/pr105665.c > > diff --git a/gcc/testsuite/gcc.dg/torture/pr105665.c b/gcc/testsuite/gcc.dg/torture/pr105665.c > new file mode 100644 > index 0000000000000..34cfc65843495 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/torture/pr105665.c > @@ -0,0 +1,20 @@ > +/* { dg-do run } */ > + > +int a, b, c[1], d[2], *e = c; > +int main() { > + int f = 0; > + for (; b < 2; b++) { > + int g; > + if (f) > + g++, b = 40; > + a = d[b * b]; > + for (f = 0; f < 3; f++) { > + if (e) > + break; > + g--; > + if (a) > + a = g; > + } > + } > + return 0; > +} > diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc > index 81b536f930415..f20a985d7ca22 100644 > --- a/gcc/tree-ssa-loop-ivopts.cc > +++ b/gcc/tree-ssa-loop-ivopts.cc > @@ -3071,13 +3071,128 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr) > return *slot; > } > > -/* Find the first undefined SSA name in *TP. */ > +/* Return TRUE iff VAR is marked as maybe-undefined. See > + mark_ssa_maybe_undefs. */ > + > +static inline bool > +ssa_name_maybe_undef_p (tree var) > +{ > + gcc_checking_assert (TREE_CODE (var) == SSA_NAME); > + return TREE_VISITED (var); > +} > + > +/* Set (or clear, depending on VALUE) VAR's maybe-undefined mark. */ > + > +static inline void > +ssa_name_set_maybe_undef (tree var, bool value = true) > +{ > + gcc_checking_assert (TREE_CODE (var) == SSA_NAME); > + TREE_VISITED (var) = value; > +} > + > +/* Return TRUE iff there are any non-PHI uses of VAR that dominate the > + end of BB. If we return TRUE and BB is a loop header, then VAR we > + be assumed to be defined within the loop, even if it is marked as > + maybe-undefined. */ > + > +static inline bool > +ssa_name_any_use_dominates_bb_p (tree var, basic_block bb) > +{ > + imm_use_iterator iter; > + use_operand_p use_p; > + FOR_EACH_IMM_USE_FAST (use_p, iter, var) > + { > + if (is_a (USE_STMT (use_p))) I think you also want to skip debug stmts here? > + continue; > + basic_block dombb = gimple_bb (USE_STMT (use_p)); > + if (dominated_by_p (CDI_DOMINATORS, bb, dombb)) > + return true; > + } > + > + return false; > +} > + > +/* Mark as maybe_undef any SSA_NAMEs that are unsuitable as ivopts > + candidates for potentially involving undefined behavior. */ > + > +static void > +mark_ssa_maybe_undefs (void) > +{ > + auto_vec queue; > + > + /* Scan all SSA_NAMEs, marking the definitely-undefined ones as > + maybe-undefined and queuing them for propagation, while clearing > + the mark on others. */ > + unsigned int i; > + tree var; > + FOR_EACH_SSA_NAME (i, var, cfun) > + { > + if (SSA_NAME_IS_VIRTUAL_OPERAND (var) > + || !ssa_undefined_value_p (var, false)) > + ssa_name_set_maybe_undef (var, false); > + else > + { > + ssa_name_set_maybe_undef (var); > + queue.safe_push (var); > + if (dump_file) && (dump_flags & TDF_DETAILS) please > + fprintf (dump_file, "marking _%i as maybe-undef\n", > + SSA_NAME_VERSION (var)); > + } > + } > + > + /* Now propagate maybe-undefined from a DEF to any other PHI that > + uses it, as long as there isn't any intervening use of DEF. */ > + while (!queue.is_empty ()) > + { > + var = queue.pop (); > + imm_use_iterator iter; > + use_operand_p use_p; > + FOR_EACH_IMM_USE_FAST (use_p, iter, var) > + { > + /* Any uses of VAR that aren't PHI args imply VAR must be > + defined, otherwise undefined behavior would have been > + definitely invoked. Only PHI args may hold > + maybe-undefined values without invoking undefined > + behavior for that reason alone. */ > + if (!is_a (USE_STMT (use_p))) > + continue; > + gphi *phi = as_a (USE_STMT (use_p)); > + > + tree def = gimple_phi_result (phi); > + if (ssa_name_maybe_undef_p (def)) > + continue; > + > + /* Look for any uses of the maybe-unused SSA_NAME that > + dominates the block that reaches the incoming block > + corresponding to the PHI arg in which it is mentioned. > + That means we can assume the SSA_NAME is defined in that > + path, so we only mark a PHI result as maybe-undef if we > + find an unused reaching SSA_NAME. */ > + int idx = phi_arg_index_from_use (use_p); > + basic_block bb = gimple_phi_arg_edge (phi, idx)->src; > + if (ssa_name_any_use_dominates_bb_p (var, bb)) > + continue; > + > + ssa_name_set_maybe_undef (def); > + queue.safe_push (def); > + if (dump_file) likewise OK with those changes. Thanks, Richard. > + fprintf (dump_file, "marking _%i as maybe-undef because of _%i\n", > + SSA_NAME_VERSION (def), SSA_NAME_VERSION (var)); > + } > + } > +} > + > +/* Return *TP if it is an SSA_NAME marked with TREE_VISITED, i.e., as > + unsuitable as ivopts candidates for potentially involving undefined > + behavior. */ > > static tree > -find_ssa_undef (tree *tp, int *walk_subtrees, void *) > +find_ssa_undef (tree *tp, int *walk_subtrees, void *bb_) > { > + basic_block bb = (basic_block) bb_; > if (TREE_CODE (*tp) == SSA_NAME > - && ssa_undefined_value_p (*tp, false)) > + && ssa_name_maybe_undef_p (*tp) > + && !ssa_name_any_use_dominates_bb_p (*tp, bb)) > return *tp; > if (!EXPR_P (*tp)) > *walk_subtrees = 0; > @@ -3114,7 +3229,7 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important, > /* If BASE contains undefined SSA names make sure we only record > the original IV. */ > bool involves_undefs = false; > - if (walk_tree (&base, find_ssa_undef, NULL, NULL)) > + if (walk_tree (&base, find_ssa_undef, data->current_loop->header, NULL)) > { > if (pos != IP_ORIGINAL) > return NULL; > @@ -8192,6 +8307,7 @@ tree_ssa_iv_optimize (void) > auto_bitmap toremove; > > tree_ssa_iv_optimize_init (&data); > + mark_ssa_maybe_undefs (); > > /* Optimize the loops starting with the innermost ones. */ > for (auto loop : loops_list (cfun, LI_FROM_INNERMOST)) > > > -- > Alexandre Oliva, happy hacker https://FSFLA.org/blogs/lxo/ > Free Software Activist GNU Toolchain Engineer > Disinformation flourishes because many people care deeply about injustice > but very few check the facts. Ask me about