Transpose loops where we break to infinite continue.

2 files changed, 60 insertions, 3 deletions

diff --git a/cfg_structurizer.cpp b/cfg_structurizer.cpp
index ef486a1..8d5168f 100644
--- a/cfg_structurizer.cpp
+++ b/cfg_structurizer.cpp
@@ -2992,7 +2992,24 @@ CFGStructurizer::LoopExitType CFGStructurizer::get_loop_exit_type(const CFGNode
 		{
 			// Even if we dominate node, we might not be able to merge to it.
 			if (!header.can_loop_merge_to(&node))
-				return LoopExitType::Escape;
+			{
+				// This is an escape we dominate, but this could also be a case where we break
+				// to a continue construct in the outer loop which is not reachable through back traversal.
+				// This will confuse loop analysis, since this kind of double continue will not resolve properly.
+				// In this case we need to rendezvous at this block with a ladder to avoid
+				// double-continue.
+
+				auto *outer_infinite_loop = get_innermost_loop_header_for(entry_block,
+				                                                          innermost_loop_header->immediate_dominator);
+				if (outer_infinite_loop && outer_infinite_loop->pred_back_edge &&
+				    outer_infinite_loop->pred_back_edge->succ.empty() &&
+				    outer_infinite_loop->pred_back_edge->post_dominates(&node))
+				{
+					return LoopExitType::MergeToInfiniteLoop;
+				}
+				else
+					return LoopExitType::Escape;
+			}
 
 			return LoopExitType::Merge;
 		}
@@ -3343,8 +3360,12 @@ bool CFGStructurizer::rewrite_transposed_loops()
 
 		// We call this an "inner" transposed loop here since merge block cannot reach this block.
 
-		CFGNode *impossible_merge_target = nullptr;
-		if (!result.non_dominated_exit.empty())
+		// Always resolve infinite continue ladders. This is where we break to
+		// an outer infinite loop. We must resolve the scopes by making this ladder the
+		// merge point, then we can break further.
+		CFGNode *impossible_merge_target = merge_result.infinite_continue_ladder;
+
+		if (!impossible_merge_target && !result.non_dominated_exit.empty())
 		{
 			auto *common_break_target = find_common_post_dominator(result.non_dominated_exit);
 			if (common_break_target && common_break_target != merge &&
@@ -3471,6 +3492,29 @@ CFGStructurizer::LoopAnalysis CFGStructurizer::analyze_loop(CFGNode *node) const
 		case LoopExitType::Escape:
 			result.non_dominated_exit.push_back(loop_exit);
 			break;
+
+		case LoopExitType::MergeToInfiniteLoop:
+			result.dominated_continue_exit.push_back(loop_exit);
+			break;
+		}
+	}
+
+	if (result.dominated_continue_exit.size() > 1)
+	{
+		// If we have multiple continue exit candidates, they better merge into a single clean candidate that we
+		// still dominate, otherwise, ignore this case and treat them all as normal Escape nodes.
+		auto *common = find_common_post_dominator(result.dominated_continue_exit);
+		if (common && node->dominates(common))
+		{
+			result.dominated_continue_exit.clear();
+			result.dominated_continue_exit.push_back(common);
+		}
+		else
+		{
+			result.non_dominated_exit.insert(result.non_dominated_exit.end(),
+			                                 result.dominated_continue_exit.begin(),
+			                                 result.dominated_continue_exit.end());
+			result.dominated_continue_exit.clear();
 		}
 	}
 
@@ -3565,6 +3609,13 @@ CFGStructurizer::LoopMergeAnalysis CFGStructurizer::analyze_loop_merge(CFGNode *
 	LoopMergeAnalysis merge_result = {};
 	merge_result.merge = merge;
 	merge_result.dominated_merge = dominated_merge;
+
+	if (!analysis.dominated_continue_exit.empty())
+	{
+		assert(analysis.dominated_continue_exit.size() == 1);
+		merge_result.infinite_continue_ladder = analysis.dominated_continue_exit.front();
+	}
+
 	return merge_result;
 }
 
@@ -3598,6 +3649,9 @@ void CFGStructurizer::find_loops()
 		auto &inner_dominated_exit = result.inner_dominated_exit;
 		auto &non_dominated_exit = result.non_dominated_exit;
 
+		// This should not come up here, and must be handled in transpose loops.
+		assert(result.dominated_continue_exit.empty());
+
 		// Detect infinite loop with an exit which is only in inner loop construct.
 		// It is impossible to construct a merge block in this case since the merge targets,
 		// so just merge to unreachable.
diff --git a/cfg_structurizer.hpp b/cfg_structurizer.hpp
index ed3c00d..106f9e8 100644
--- a/cfg_structurizer.hpp
+++ b/cfg_structurizer.hpp
@@ -87,6 +87,7 @@ private:
 		Vector<CFGNode *> dominated_exit;
 		Vector<CFGNode *> inner_dominated_exit;
 		Vector<CFGNode *> non_dominated_exit;
+		Vector<CFGNode *> dominated_continue_exit;
 	};
 	LoopAnalysis analyze_loop(CFGNode *node) const;
 
@@ -94,6 +95,7 @@ private:
 	{
 		CFGNode *merge;
 		CFGNode *dominated_merge;
+		CFGNode *infinite_continue_ladder;
 	};
 	LoopMergeAnalysis analyze_loop_merge(CFGNode *node, const LoopAnalysis &analysis);
 	void rewrite_transposed_loop_inner(CFGNode *node, CFGNode *impossible_merge_target,
@@ -151,6 +153,7 @@ private:
 		Exit,
 		Merge,
 		Escape,
+		MergeToInfiniteLoop,
 		InnerLoopExit,
 		InnerLoopMerge,
 		InnerLoopFalsePositive