[PATCH] Mark irreducible regions in the backwards threader

Richard Biener rguenther@suse.de
Mon Jun 14 14:04:02 GMT 2021


The same issue that arises in PR100934 can happen in the backward
threader now (Aldy?) - we eventually run into mark_irreducible_loops
for non-FSM thread paths checking for paths crossing irreducible
region boundaries.

The following thus initializes irreducible regions and makes
irreducible region discovery handle multiple latches.

Bootstrap & regtest pending.

2021-06-14  Richard Biener  <rguenther@suse.de>

	* cfgloopanal.c (mark_irreducible_loops): Use a dominance
	check to identify loop latches.
	* cfgloop.c (verify_loop_structure): Likewise.
	* loop-init.c (apply_loop_flags): Allow marked irreducible
	regions even with multiple latches.
	* predict.c (rebuild_frequencies): Simplify.
	* tree-ssa-threadbackward.c (pass_thread_jumps::execute):
	Mark irreducible regions.
	(pass_early_thread_jumps::execute): Likewise.
	* tree-ssa-threadupdate.c
	(jump_thread_path_registry::mark_threaded_blocks): Assert
	we have irreducible regions marked.
---
 gcc/cfgloop.c                 | 14 ++++++++++----
 gcc/cfgloopanal.c             |  2 +-
 gcc/loop-init.c               |  3 ++-
 gcc/predict.c                 |  3 +--
 gcc/tree-ssa-threadbackward.c |  6 ++++--
 gcc/tree-ssa-threadupdate.c   |  2 ++
 6 files changed, 20 insertions(+), 10 deletions(-)

diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c
index 4e227cd0891..f094538b9ff 100644
--- a/gcc/cfgloop.c
+++ b/gcc/cfgloop.c
@@ -1555,11 +1555,17 @@ verify_loop_structure (void)
 	  error ("loop %d%'s header does not belong directly to it", i);
 	  err = 1;
 	}
-      if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
-	  && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
+      if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
 	{
-	  error ("loop %d%'s latch is marked as part of irreducible region", i);
-	  err = 1;
+	  edge_iterator ei;
+	  FOR_EACH_EDGE (e, ei, loop->header->preds)
+	    if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header)
+		&& e->flags & EDGE_IRREDUCIBLE_LOOP)
+	      {
+		error ("loop %d%'s latch is marked as part of irreducible"
+		       " region", i);
+		err = 1;
+	      }
 	}
     }
 
diff --git a/gcc/cfgloopanal.c b/gcc/cfgloopanal.c
index d0eade3dd34..54426b54881 100644
--- a/gcc/cfgloopanal.c
+++ b/gcc/cfgloopanal.c
@@ -113,7 +113,7 @@ mark_irreducible_loops (void)
 
 	/* Ignore latch edges.  */
 	if (e->dest->loop_father->header == e->dest
-	    && e->dest->loop_father->latch == act)
+	    && dominated_by_p (CDI_DOMINATORS, act, e->dest))
 	  continue;
 
 	/* Edges inside a single loop should be left where they are.  Edges
diff --git a/gcc/loop-init.c b/gcc/loop-init.c
index 17f14075f62..1fde0ede441 100644
--- a/gcc/loop-init.c
+++ b/gcc/loop-init.c
@@ -48,7 +48,8 @@ apply_loop_flags (unsigned flags)
 	 not work).  However, we avoid modifying cfg, which some
 	 passes may want.  */
       gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
-			     | LOOPS_HAVE_RECORDED_EXITS)) == 0);
+			     | LOOPS_HAVE_RECORDED_EXITS
+			     | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)) == 0);
       loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
     }
   else
diff --git a/gcc/predict.c b/gcc/predict.c
index 5d0cae5c4a4..d751e6cecce 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -4287,8 +4287,7 @@ rebuild_frequencies (void)
 
   if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
     {
-      loop_optimizer_init (0);
-      mark_irreducible_loops ();
+      loop_optimizer_init (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
       connect_infinite_loops_to_exit ();
       estimate_bb_frequencies (true);
       remove_fake_exit_edges ();
diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index 7dd8594e3d4..1a5deafc463 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -887,7 +887,8 @@ pass_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED)
 unsigned int
 pass_thread_jumps::execute (function *fun)
 {
-  loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
+  loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES
+		       | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
 
   /* Try to thread each block with more than one successor.  */
   thread_jumps threader;
@@ -948,7 +949,8 @@ pass_early_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED)
 unsigned int
 pass_early_thread_jumps::execute (function *fun)
 {
-  loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
+  loop_optimizer_init (AVOID_CFG_MODIFICATIONS
+		       | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
 
   /* Try to thread each block with more than one successor.  */
   thread_jumps threader (/*speed_p=*/false);
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index a86302be18e..387994fd882 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -1917,6 +1917,8 @@ jump_thread_path_registry::mark_threaded_blocks (bitmap threaded_blocks)
   edge e;
   edge_iterator ei;
 
+  gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS));
+
   /* It is possible to have jump threads in which one is a subpath
      of the other.  ie, (A, B), (B, C), (C, D) where B is a joiner
      block and (B, C), (C, D) where no joiner block exists.
-- 
2.26.2


More information about the Gcc-patches mailing list