Update SPIRV-Cross

Change-Id: I15dbf83057b5aa435b87b80e219b113987735cad
Reviewed-by: Christian Strømme <christian.stromme@qt.io>

1 files changed, 183 insertions, 12 deletions

diff --git a/src/3rdparty/SPIRV-Cross/spirv_cfg.cpp b/src/3rdparty/SPIRV-Cross/spirv_cfg.cpp
index 2f3cf25..463c756 100644
--- a/src/3rdparty/SPIRV-Cross/spirv_cfg.cpp
+++ b/src/3rdparty/SPIRV-Cross/spirv_cfg.cpp
@@ -61,7 +61,7 @@ void CFG::build_immediate_dominators()
 			if (immediate_dominators[block])
 			{
 				assert(immediate_dominators[edge]);
-				immediate_dominators[block] = find_common_dominator(block, edge);
+				immediate_dominators[block] = find_common_dominator(immediate_dominators[block], edge);
 			}
 			else
 				immediate_dominators[block] = edge;
@@ -74,8 +74,14 @@ bool CFG::is_back_edge(uint32_t to) const
 	// We have a back edge if the visit order is set with the temporary magic value 0.
 	// Crossing edges will have already been recorded with a visit order.
 	auto itr = visit_order.find(to);
-	assert(itr != end(visit_order));
-	return itr->second.get() == 0;
+	return itr != end(visit_order) && itr->second.get() == 0;
+}
+
+bool CFG::has_visited_forward_edge(uint32_t to) const
+{
+	// If > 0, we have visited the edge already, and this is not a back edge branch.
+	auto itr = visit_order.find(to);
+	return itr != end(visit_order) && itr->second.get() > 0;
 }
 
 bool CFG::post_order_visit(uint32_t block_id)
@@ -83,14 +89,30 @@ bool CFG::post_order_visit(uint32_t block_id)
 	// If we have already branched to this block (back edge), stop recursion.
 	// If our branches are back-edges, we do not record them.
 	// We have to record crossing edges however.
-	if (visit_order[block_id].get() >= 0)
-		return !is_back_edge(block_id);
+	if (has_visited_forward_edge(block_id))
+		return true;
+	else if (is_back_edge(block_id))
+		return false;
 
 	// Block back-edges from recursively revisiting ourselves.
 	visit_order[block_id].get() = 0;
 
-	// First visit our branch targets.
 	auto &block = compiler.get<SPIRBlock>(block_id);
+
+	// If this is a loop header, add an implied branch to the merge target.
+	// This is needed to avoid annoying cases with do { ... } while(false) loops often generated by inliners.
+	// To the CFG, this is linear control flow, but we risk picking the do/while scope as our dominating block.
+	// This makes sure that if we are accessing a variable outside the do/while, we choose the loop header as dominator.
+	// We could use has_visited_forward_edge, but this break code-gen where the merge block is unreachable in the CFG.
+
+	// Make a point out of visiting merge target first. This is to make sure that post visit order outside the loop
+	// is lower than inside the loop, which is going to be key for some traversal algorithms like post-dominance analysis.
+	// For selection constructs true/false blocks will end up visiting the merge block directly and it works out fine,
+	// but for loops, only the header might end up actually branching to merge block.
+	if (block.merge == SPIRBlock::MergeLoop && post_order_visit(block.merge_block))
+		add_branch(block_id, block.merge_block);
+
+	// First visit our branch targets.
 	switch (block.terminator)
 	{
 	case SPIRBlock::Direct:
@@ -119,12 +141,56 @@ bool CFG::post_order_visit(uint32_t block_id)
 		break;
 	}
 
-	// If this is a loop header, add an implied branch to the merge target.
-	// This is needed to avoid annoying cases with do { ... } while(false) loops often generated by inliners.
-	// To the CFG, this is linear control flow, but we risk picking the do/while scope as our dominating block.
-	// This makes sure that if we are accessing a variable outside the do/while, we choose the loop header as dominator.
-	if (block.merge == SPIRBlock::MergeLoop)
-		add_branch(block_id, block.merge_block);
+	// If this is a selection merge, add an implied branch to the merge target.
+	// This is needed to avoid cases where an inner branch dominates the outer branch.
+	// This can happen if one of the branches exit early, e.g.:
+	// if (cond) { ...; break; } else { var = 100 } use_var(var);
+	// We can use the variable without a Phi since there is only one possible parent here.
+	// However, in this case, we need to hoist out the inner variable to outside the branch.
+	// Use same strategy as loops.
+	if (block.merge == SPIRBlock::MergeSelection && post_order_visit(block.next_block))
+	{
+		// If there is only one preceding edge to the merge block and it's not ourselves, we need a fixup.
+		// Add a fake branch so any dominator in either the if (), or else () block, or a lone case statement
+		// will be hoisted out to outside the selection merge.
+		// If size > 1, the variable will be automatically hoisted, so we should not mess with it.
+		// The exception here is switch blocks, where we can have multiple edges to merge block,
+		// all coming from same scope, so be more conservative in this case.
+		// Adding fake branches unconditionally breaks parameter preservation analysis,
+		// which looks at how variables are accessed through the CFG.
+		auto pred_itr = preceding_edges.find(block.next_block);
+		if (pred_itr != end(preceding_edges))
+		{
+			auto &pred = pred_itr->second;
+			auto succ_itr = succeeding_edges.find(block_id);
+			size_t num_succeeding_edges = 0;
+			if (succ_itr != end(succeeding_edges))
+				num_succeeding_edges = succ_itr->second.size();
+
+			if (block.terminator == SPIRBlock::MultiSelect && num_succeeding_edges == 1)
+			{
+				// Multiple branches can come from the same scope due to "break;", so we need to assume that all branches
+				// come from same case scope in worst case, even if there are multiple preceding edges.
+				// If we have more than one succeeding edge from the block header, it should be impossible
+				// to have a dominator be inside the block.
+				// Only case this can go wrong is if we have 2 or more edges from block header and
+				// 2 or more edges to merge block, and still have dominator be inside a case label.
+				if (!pred.empty())
+					add_branch(block_id, block.next_block);
+			}
+			else
+			{
+				if (pred.size() == 1 && *pred.begin() != block_id)
+					add_branch(block_id, block.next_block);
+			}
+		}
+		else
+		{
+			// If the merge block does not have any preceding edges, i.e. unreachable, hallucinate it.
+			// We're going to do code-gen for it, and domination analysis requires that we have at least one preceding edge.
+			add_branch(block_id, block.next_block);
+		}
+	}
 
 	// Then visit ourselves. Start counting at one, to let 0 be a magic value for testing back vs. crossing edges.
 	visit_order[block_id].get() = ++visit_count;
@@ -152,6 +218,111 @@ void CFG::add_branch(uint32_t from, uint32_t to)
 	add_unique(succeeding_edges[from], to);
 }
 
+uint32_t CFG::find_loop_dominator(uint32_t block_id) const
+{
+	while (block_id != SPIRBlock::NoDominator)
+	{
+		auto itr = preceding_edges.find(block_id);
+		if (itr == end(preceding_edges))
+			return SPIRBlock::NoDominator;
+		if (itr->second.empty())
+			return SPIRBlock::NoDominator;
+
+		uint32_t pred_block_id = SPIRBlock::NoDominator;
+		bool ignore_loop_header = false;
+
+		// If we are a merge block, go directly to the header block.
+		// Only consider a loop dominator if we are branching from inside a block to a loop header.
+		// NOTE: In the CFG we forced an edge from header to merge block always to support variable scopes properly.
+		for (auto &pred : itr->second)
+		{
+			auto &pred_block = compiler.get<SPIRBlock>(pred);
+			if (pred_block.merge == SPIRBlock::MergeLoop && pred_block.merge_block == ID(block_id))
+			{
+				pred_block_id = pred;
+				ignore_loop_header = true;
+				break;
+			}
+			else if (pred_block.merge == SPIRBlock::MergeSelection && pred_block.next_block == ID(block_id))
+			{
+				pred_block_id = pred;
+				break;
+			}
+		}
+
+		// No merge block means we can just pick any edge. Loop headers dominate the inner loop, so any path we
+		// take will lead there.
+		if (pred_block_id == SPIRBlock::NoDominator)
+			pred_block_id = itr->second.front();
+
+		block_id = pred_block_id;
+
+		if (!ignore_loop_header && block_id)
+		{
+			auto &block = compiler.get<SPIRBlock>(block_id);
+			if (block.merge == SPIRBlock::MergeLoop)
+				return block_id;
+		}
+	}
+
+	return block_id;
+}
+
+bool CFG::node_terminates_control_flow_in_sub_graph(BlockID from, BlockID to) const
+{
+	// Walk backwards, starting from "to" block.
+	// Only follow pred edges if they have a 1:1 relationship, or a merge relationship.
+	// If we cannot find a path to "from", we must assume that to is inside control flow in some way.
+
+	auto &from_block = compiler.get<SPIRBlock>(from);
+	BlockID ignore_block_id = 0;
+	if (from_block.merge == SPIRBlock::MergeLoop)
+		ignore_block_id = from_block.merge_block;
+
+	while (to != from)
+	{
+		auto pred_itr = preceding_edges.find(to);
+		if (pred_itr == end(preceding_edges))
+			return false;
+
+		DominatorBuilder builder(*this);
+		for (auto &edge : pred_itr->second)
+			builder.add_block(edge);
+
+		uint32_t dominator = builder.get_dominator();
+		if (dominator == 0)
+			return false;
+
+		auto &dom = compiler.get<SPIRBlock>(dominator);
+
+		bool true_path_ignore = false;
+		bool false_path_ignore = false;
+		if (ignore_block_id && dom.terminator == SPIRBlock::Select)
+		{
+			auto &true_block = compiler.get<SPIRBlock>(dom.true_block);
+			auto &false_block = compiler.get<SPIRBlock>(dom.false_block);
+			auto &ignore_block = compiler.get<SPIRBlock>(ignore_block_id);
+			true_path_ignore = compiler.execution_is_branchless(true_block, ignore_block);
+			false_path_ignore = compiler.execution_is_branchless(false_block, ignore_block);
+		}
+
+		if ((dom.merge == SPIRBlock::MergeSelection && dom.next_block == to) ||
+		    (dom.merge == SPIRBlock::MergeLoop && dom.merge_block == to) ||
+		    (dom.terminator == SPIRBlock::Direct && dom.next_block == to) ||
+		    (dom.terminator == SPIRBlock::Select && dom.true_block == to && false_path_ignore) ||
+		    (dom.terminator == SPIRBlock::Select && dom.false_block == to && true_path_ignore))
+		{
+			// Allow walking selection constructs if the other branch reaches out of a loop construct.
+			// It cannot be in-scope anymore.
+			to = dominator;
+		}
+		else
+			return false;
+	}
+
+	return true;
+}
+
 DominatorBuilder::DominatorBuilder(const CFG &cfg_)
     : cfg(cfg_)
 {