From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from nikam.ms.mff.cuni.cz (nikam.ms.mff.cuni.cz [195.113.20.16]) by sourceware.org (Postfix) with ESMTPS id CB0BD3858D1E for ; Mon, 30 Jan 2023 14:45:00 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org CB0BD3858D1E Authentication-Results: sourceware.org; dmarc=fail (p=none dis=none) header.from=ucw.cz Authentication-Results: sourceware.org; spf=none smtp.mailfrom=kam.mff.cuni.cz Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id 157592803B1; Mon, 30 Jan 2023 15:44:59 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ucw.cz; s=gen1; t=1675089899; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=Kq1ZMmo0Ohe3EDar28sloChUQbEUNdDi6Z5kOXVwD2w=; b=W3P3SnQepjc8LN1mqFiu/iwHh9GWOhp9vixXMmJHw2SAhQJhsfIX2Rv9vvcyaYiG4YjA6C IFHTPIg1IQAwVmpYrtAKSJGWhgipyaV4WXj2KXS49+5HR/pkI8Id4nycLHl4k8hU6CL7jj JPyIkZPi/IhGf1q4bkz+IXVdrGyrdMs= Date: Mon, 30 Jan 2023 15:44:59 +0100 From: Jan Hubicka To: Alexander Monakov Cc: gcc-patches@gcc.gnu.org, mjambor@suse.de Subject: Re: Fix wrong code issues with ipa-sra Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: X-Spam-Status: No, score=-11.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,GIT_PATCH_0,HEADER_FROM_DIFFERENT_DOMAINS,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: > Hello, > > Coverity flagged a real issue in this patch: > > On Mon, 16 Jan 2023, Jan Hubicka via Gcc-patches wrote: > > --- a/gcc/ipa-utils.cc > > +++ b/gcc/ipa-utils.cc > [...] > > +bitmap > > +find_always_executed_bbs (function *fun, bool assume_return_or_eh) > > +{ > > + auto_vec stack; > > + auto_vec terminating_bbs; > > + hash_set visited; > > + edge e; > > + edge_iterator ei; > > + > > + /* First walk all BBs reachable from entry stopping on statements that may > > + terminate execution. Everything past this statement is not going to be executed > > + each invocation. */ > > + stack.safe_push (ENTRY_BLOCK_PTR_FOR_FN (fun)); > > + while (!stack.is_empty ()) > > + { > > + basic_block bb = stack.pop (); > > + bool found = false, found_exit = false; > > + if (!assume_return_or_eh > > + && (EDGE_COUNT (bb->succs) == 0 || (bb->flags & BB_IRREDUCIBLE_LOOP))) > > + found = true; > > + FOR_EACH_EDGE (e, ei, bb->succs) > > + { > > + if (e->dest == EXIT_BLOCK_PTR_FOR_FN (fun)) > > + { > > + found_exit = true; > > + break; > > + } > > + /* Watch for infinite loops. */ > > + if (!found && (assume_return_or_eh & EDGE_DFS_BACK) > ^^^^^^^^^^^^^^^ > This bitwise 'and' always evaluates to zero, making the entire clause always-false. Hi, that is a good catch. This patch fixes the stupid typo info find_always_executed_bbs which made all edges to be considered as ones closing infinite loops. This fix has somewhat snowballed as, comparing it to finite_function_p, I noticed a divergence in handling of volatile asms (find_always_executed_bbs is conservative and thinks that volatile statement may return or do EH, but it is really impossible and elsewhere we expects that we dont) and I also noticed a bug in handling early returns which made some loops to be missed. I also noticed that function assumes that irreducible loops are marked in CFG which is not necessarily true and it is easy to detect them during the walk. Bootstrapped/regtested x86_64-linux, comitted. gcc/ChangeLog: 2023-01-29 Jan Hubicka * ipa-utils.cc: Include calls.h, cfgloop.h and cfganal.h (stmt_may_terminate_function_p): If assuming return or EH volatile asm is safe. (find_always_executed_bbs): Fix handling of terminating BBS and infinite loops; add debug output. * tree-ssa-alias.cc (stmt_kills_ref_p): Fix debug output gcc/testsuite/ChangeLog: 2023-01-29 Jan Hubicka * gcc.dg/ipa/ipa-sra-30.c: New test. * gcc.dg/ipa/ipa-sra-31.c: New test. * gcc.dg/tree-ssa/modref-dse-7.c: New test. diff --git a/gcc/ipa-utils.cc b/gcc/ipa-utils.cc index 3d5633340f1..8badcc2c110 100644 --- a/gcc/ipa-utils.cc +++ b/gcc/ipa-utils.cc @@ -40,6 +40,9 @@ along with GCC; see the file COPYING3. If not see #include "ipa-modref-tree.h" #include "ipa-modref.h" #include "tree-ssa-loop-niter.h" +#include "calls.h" +#include "cfgloop.h" +#include "cfganal.h" /* Debugging function for postorder and inorder code. NOTE is a string that is printed before the nodes are printed. ORDER is an array of @@ -796,11 +799,11 @@ stmt_may_terminate_function_p (function *fun, gimple *stmt, bool assume_return_o { if (stmt_can_throw_external (fun, stmt)) return true; + if (assume_return_or_eh) + return false; gasm *astmt = dyn_cast (stmt); if (astmt && gimple_asm_volatile_p (astmt)) return true; - if (assume_return_or_eh) - return false; if (gimple_could_trap_p (stmt)) return true; if (gcall *call = dyn_cast (stmt)) @@ -832,8 +835,14 @@ find_always_executed_bbs (function *fun, bool assume_return_or_eh) auto_vec stack; auto_vec terminating_bbs; hash_set visited; + hash_set terminating_bbs_set; edge e; edge_iterator ei; + int flags = flags_from_decl_or_type (fun->decl); + /* PUre and const functions always return. */ + assume_return_or_eh |= (flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE); + if (!assume_return_or_eh) + mark_dfs_back_edges (fun); /* First walk all BBs reachable from entry stopping on statements that may terminate execution. Everything past this statement is not going to be executed @@ -843,9 +852,8 @@ find_always_executed_bbs (function *fun, bool assume_return_or_eh) { basic_block bb = stack.pop (); bool found = false, found_exit = false; - if (!assume_return_or_eh - && (EDGE_COUNT (bb->succs) == 0 || (bb->flags & BB_IRREDUCIBLE_LOOP))) - found = true; + if (bb->index == EXIT_BLOCK) + continue; FOR_EACH_EDGE (e, ei, bb->succs) { if (e->dest == EXIT_BLOCK_PTR_FOR_FN (fun)) @@ -854,10 +862,28 @@ find_always_executed_bbs (function *fun, bool assume_return_or_eh) break; } /* Watch for infinite loops. */ - if (!found && (assume_return_or_eh & EDGE_DFS_BACK) - && !finite_loop_p (e->src->loop_father)) - found = true; + if (!found + && !assume_return_or_eh && (e->flags & EDGE_DFS_BACK)) + { + if (!dom_info_available_p (CDI_DOMINATORS)) + calculate_dominance_info (CDI_DOMINATORS); + /* If this is not a loop latch edge it is an irreducible region. + Assume that it is infinite. + TODO: with C++ forced progression we can still walk the + irreducible region and see if it contains any side effects. + Similarly for loops. -ffinite-loops does not really imply + this since we allow inlining across -ffinite-loops bondary + and thus it can be used only as a loop flag. */ + if (e->dest->loop_father->header != e->dest + || !dominated_by_p (CDI_DOMINATORS, bb, e->dest)) + found = true; + else if (!finite_loop_p (e->dest->loop_father)) + found = true; + } } + if (!assume_return_or_eh + && (EDGE_COUNT (bb->succs) == 0 || (bb->flags & BB_IRREDUCIBLE_LOOP))) + found = true; for (gimple_stmt_iterator si = gsi_start_nondebug_after_labels_bb (bb); !gsi_end_p (si) && !found; gsi_next_nondebug (&si)) if (stmt_may_terminate_function_p (fun, gsi_stmt (si), assume_return_or_eh)) @@ -869,7 +895,10 @@ find_always_executed_bbs (function *fun, bool assume_return_or_eh) { visited.add (EXIT_BLOCK_PTR_FOR_FN (fun)); if (!found_exit) - terminating_bbs.safe_push (bb); + { + terminating_bbs.safe_push (bb); + terminating_bbs_set.add (bb); + } } else FOR_EACH_EDGE (e, ei, bb->succs) @@ -883,8 +912,7 @@ find_always_executed_bbs (function *fun, bool assume_return_or_eh) bitmap ret = BITMAP_ALLOC (NULL); /* A degenerated case when there is no path to exit. */ - if (!visited.contains (EXIT_BLOCK_PTR_FOR_FN (fun)) - && terminating_bbs.is_empty ()) + if (!visited.contains (EXIT_BLOCK_PTR_FOR_FN (fun))) { bitmap_set_bit (ret, single_succ_edge @@ -945,7 +973,7 @@ find_always_executed_bbs (function *fun, bool assume_return_or_eh) } /* DFS is visiting BB for first time. */ *slot = cstate = XOBNEW (&state_obstack, struct astate); - cstate->low = cstate->dfs_preorder = next_dfs_num++; + cstate->low = cstate->high = cstate->dfs_preorder = next_dfs_num++; w.cstate = cstate; /* Exit block is special; process all fake edges we identified. */ if (bb == EXIT_BLOCK_PTR_FOR_FN (fun)) @@ -981,25 +1009,38 @@ find_always_executed_bbs (function *fun, bool assume_return_or_eh) if (!cstate2) { if (e->src != ENTRY_BLOCK_PTR_FOR_FN (fun)) - cstate->low = 0; + cstate->low = 0; continue; } cstate->low = MIN (cstate->low, (*cstate2)->low); cstate->high = MAX (cstate->high, (*cstate2)->high); } + if (dump_file && (dump_flags & TDF_DETAILS) && bb != EXIT_BLOCK_PTR_FOR_FN (fun)) + fprintf (dump_file, "BB %i %s preorder %i posorder %i low %i high %i\n", + bb->index, terminating_bbs_set.contains (bb) ? "(terminating)": "", + cstate->dfs_preorder, cstate->dfs_postorder, cstate->low, cstate->high); if (cstate->low == cstate->dfs_preorder && cstate->high == cstate->dfs_postorder && bb != EXIT_BLOCK_PTR_FOR_FN (fun)) bitmap_set_bit (ret, bb->index); - FOR_EACH_EDGE (e, ei, bb->succs) - { - astate **cstate2 = state.get (e->dest); - if (!cstate2) - continue; - cstate->low = MIN (cstate->low, (*cstate2)->low); - cstate->high = MAX (cstate->high, (*cstate2)->high); - } - } + if (terminating_bbs_set.contains (bb)) + cstate->low = 0; + else + FOR_EACH_EDGE (e, ei, bb->succs) + { + astate **cstate2 = state.get (e->dest); + if (!cstate2) + continue; + cstate->low = MIN (cstate->low, (*cstate2)->low); + cstate->high = MAX (cstate->high, (*cstate2)->high); + } + } obstack_free (&state_obstack, NULL); + if (dump_file) + { + fprintf (dump_file, "Always executed bbbs %s: ", + assume_return_or_eh ? "(assuming return or EH)": ""); + bitmap_print (dump_file, ret, "", "\n"); + } return ret; } diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-sra-30.c b/gcc/testsuite/gcc.dg/ipa/ipa-sra-30.c new file mode 100644 index 00000000000..5c8e8ed8ca1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/ipa-sra-30.c @@ -0,0 +1,31 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-ipa-sra" } */ +struct list +{ + struct list *next; + int val; +}; +__attribute__ ((noinline)) +static int reta (int *a) +{ + return *a; +} +__attribute__ ((noinline)) +static int +kill(struct list *l, int *a) +{ + int v; + while (l) + { + v = l->val; + l=l->next; + } + return reta (a) + v; +} +int +test(struct list *l, int *a) +{ + return kill (l, a); +} +/* Loop in kill may be infinite; do not SRA. */ +/* { dg-final { scan-ipa-dump-not "Created new node kill.isra" "sra" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-sra-31.c b/gcc/testsuite/gcc.dg/ipa/ipa-sra-31.c new file mode 100644 index 00000000000..0a636d66872 --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/ipa-sra-31.c @@ -0,0 +1,4 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-ipa-sra -ffinite-loops" } */ +#include "ipa-sra-30.c" +/* { dg-final { scan-ipa-dump "Created new node kill.isra" "sra" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modref-dse-7.c b/gcc/testsuite/gcc.dg/tree-ssa/modref-dse-7.c new file mode 100644 index 00000000000..85a01d30cea --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/modref-dse-7.c @@ -0,0 +1,22 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +struct list +{ + struct list *next; +}; +__attribute__ ((noinline)) +void +kill(struct list *l, int *a) +{ + while (l) + l=l->next; + *a = 0; +} +void +test(struct list *l, int *a) +{ + *a=12345; + kill (l, a); + return; +} +/* { dg-final { scan-tree-dump-not "12345" "optimized"} } */ diff --git a/gcc/tree-ssa-alias.cc b/gcc/tree-ssa-alias.cc index b8f107dfa52..7089e8b5bf3 100644 --- a/gcc/tree-ssa-alias.cc +++ b/gcc/tree-ssa-alias.cc @@ -3522,6 +3522,7 @@ stmt_kills_ref_p (gimple *stmt, ao_ref *ref) "ipa-modref: call to %s kills ", node->dump_name ()); print_generic_expr (dump_file, ref->base); + fprintf (dump_file, "\n"); } ++alias_stats.modref_kill_yes; return true;