From: Jan Hubicka <hubicka@ucw.cz>
To: Alexander Monakov <amonakov@ispras.ru>
Cc: gcc-patches@gcc.gnu.org, mjambor@suse.de
Subject: Re: Fix wrong code issues with ipa-sra
Date: Mon, 30 Jan 2023 15:44:59 +0100 [thread overview]
Message-ID: <Y9fX6x28SgKh31yg@kam.mff.cuni.cz> (raw)
In-Reply-To: <f00b4f43-8c85-35c2-8eb1-40118d7b5bbc@ispras.ru>
> 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<basic_block, 20> stack;
> > + auto_vec<basic_block, 20> terminating_bbs;
> > + hash_set<basic_block> 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 <hubicka@ucw.cz>
* 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 <hubicka@ucw.cz>
* 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 <gasm *> (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 <gcall *> (stmt))
@@ -832,8 +835,14 @@ find_always_executed_bbs (function *fun, bool assume_return_or_eh)
auto_vec<basic_block, 20> stack;
auto_vec<basic_block, 20> terminating_bbs;
hash_set<basic_block> visited;
+ hash_set<basic_block> 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;
prev parent reply other threads:[~2023-01-30 14:45 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-01-16 17:18 Jan Hubicka
2023-01-21 21:13 ` Alexander Monakov
2023-01-30 14:44 ` Jan Hubicka [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Y9fX6x28SgKh31yg@kam.mff.cuni.cz \
--to=hubicka@ucw.cz \
--cc=amonakov@ispras.ru \
--cc=gcc-patches@gcc.gnu.org \
--cc=mjambor@suse.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).