Merge pull request #109 from HansKristian-Work/post-dominates-any-work

Rewrite check for post_dominates_any_work() to work with ladder merges.

3 files changed, 42 insertions, 15 deletions

diff --git a/cfg_structurizer.cpp b/cfg_structurizer.cpp
index d181834..08ab20a 100644
--- a/cfg_structurizer.cpp
+++ b/cfg_structurizer.cpp
@@ -1845,20 +1845,6 @@ bool CFGStructurizer::control_flow_is_escaping(const CFGNode *node, const CFGNod
 
 	if (escaping_path && node->ir.operations.empty() && node->ir.phi.empty())
 	{
-		bool post_dominates_nothing = true;
-		for (auto *pred : node->pred)
-		{
-			// Skip completely useless ladder blocks when we consider this case.
-			while (pred->pred.size() == 1 && pred->ir.operations.empty() && pred->ir.phi.empty())
-				pred = pred->pred.front();
-
-			if (node->post_dominates(pred))
-			{
-				post_dominates_nothing = false;
-				break;
-			}
-		}
-
 		// If we post-dominate nothing useful or do nothing useful ourselves,
 		// this is a good indication we're a common escape edge ladder block.
 		// This can happen if we have a graph of:
@@ -1870,7 +1856,7 @@ bool CFGStructurizer::control_flow_is_escaping(const CFGNode *node, const CFGNod
 		// C -> node
 		// node -> merge
 		// This super jank diamond pattern will break the heuristics.
-		if (post_dominates_nothing)
+		if (!node->post_dominates_any_work())
 			return true;
 	}
 
diff --git a/node.cpp b/node.cpp
index 8581532..d66f293 100644
--- a/node.cpp
+++ b/node.cpp
@@ -154,6 +154,45 @@ bool CFGNode::can_backtrace_to(const CFGNode *parent) const
 	return can_backtrace_to(parent, node_cache);
 }
 
+bool CFGNode::post_dominates_any_work(const CFGNode *parent, UnorderedSet<const CFGNode *> &node_cache) const
+{
+	// If we reached this node before and didn't terminate, it must have returned false.
+	if (node_cache.count(parent))
+		return false;
+	node_cache.insert(parent);
+
+	// This is not a dummy block, we have an answer.
+	if (!parent->ir.operations.empty() || !parent->ir.phi.empty())
+		return post_dominates(parent);
+
+	for (auto *p : parent->pred)
+		if (post_dominates_any_work(p, node_cache))
+			return true;
+
+	return false;
+}
+
+bool CFGNode::post_dominates_any_work() const
+{
+	auto *start_node = this;
+	// Trivial back-trace as far as we can go.
+	while (start_node->pred.size() == 1 &&
+	       start_node->ir.operations.empty() && start_node->ir.phi.empty() &&
+	       start_node->post_dominates(start_node->pred.front()))
+	{
+		start_node = start_node->pred.front();
+	}
+
+	if (!start_node->ir.operations.empty() || !start_node->ir.phi.empty())
+		return true;
+
+	UnorderedSet<const CFGNode *> node_cache;
+	for (auto *p : start_node->pred)
+		if (start_node->post_dominates_any_work(p, node_cache))
+			return true;
+	return false;
+}
+
 const CFGNode *CFGNode::get_innermost_loop_header_for(const CFGNode *other) const
 {
 	while (this != other)
diff --git a/node.hpp b/node.hpp
index de729f3..34d4d9f 100644
--- a/node.hpp
+++ b/node.hpp
@@ -99,6 +99,8 @@ private:
 	CFGNode *get_immediate_dominator_loop_header();
 	bool can_backtrace_to(const CFGNode *parent) const;
 	bool can_backtrace_to(const CFGNode *parent, UnorderedSet<const CFGNode *> &node_cache) const;
+	bool post_dominates_any_work() const;
+	bool post_dominates_any_work(const CFGNode *parent, UnorderedSet<const CFGNode *> &node_cache) const;
 
 	void retarget_branch(CFGNode *to_prev, CFGNode *to_next);
 	void retarget_branch_with_intermediate_node(CFGNode *to_prev, CFGNode *to_next);