From 494330d4941ccaf50e07ef309fd783c2f44a492e Mon Sep 17 00:00:00 2001 From: Tim Foley Date: Thu, 3 May 2018 17:40:26 -0700 Subject: Add a pass for computing dominator trees (#541) This code is currently not used by anything, but I wanted to check in a first pass at an implementation of dominator tree construction so that we don't have to keep avoiding implementing algorithms that rely on having dominator information available. The algorithm used to construct the dominator tree is taken from "A Simple, Fast Dominance Algorithm" by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy. This is not the "best" algorithm in terms of asymptotic performance, but it is among the simplest algorithms for computing a dominator tree that still outperforms naive iterative set-based methods. The actual data structure and API for the dominator tree has a bit of "cleverness" in it to try to make the common queries reasonably fast (e.g., you can check whether A dominates B in constant time). My hope is that even if we implement a more advanced algorithm for constructing the dominator tree, we can retain compatibility with passes that might make use of this API. Because no code is currently using this logic, I have done only minimal testing by stepping through this code and validating the results on paper for some very small CFGs. More serious testing/debugging may need to wait until we have an optimization pass that needs the dominator tree we compute here. One open question I have is how best to introduce traditional unit testing into Slang, since this is an example of code that would benefit greatly from being unit tested. --- source/slang/ir-ssa.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'source/slang/ir-ssa.cpp') diff --git a/source/slang/ir-ssa.cpp b/source/slang/ir-ssa.cpp index 6c4cfa8ff..b2d336507 100644 --- a/source/slang/ir-ssa.cpp +++ b/source/slang/ir-ssa.cpp @@ -595,7 +595,7 @@ IRInst* readVarRec( // it predecessor list, and use that to decide what to do. auto predecessors = blockInfo->block->getPredecessors(); - // + // IRBlock* firstPred = nullptr; bool multiplePreds = false; for (auto pp : predecessors) -- cgit v1.2.3