Fix dominance calculation
authorDavid Neto <dneto@google.com>
Fri, 5 Aug 2016 14:09:06 +0000 (10:09 -0400)
committerDavid Neto <dneto@google.com>
Fri, 5 Aug 2016 15:09:29 +0000 (11:09 -0400)
commit3184687714d76d920224e761a05c9598de64ad7f
tree8d277c25f3d0b603b2e138c5d61e3fc3a3874832
parent5be1ee173f3496b3a4209663f56580c61fd9742c
Fix dominance calculation

Fixes dominance calculation when there is a forward arc from an
unreachable block A to a reachable block B.  Before this fix, we would
say that B is not dominated by the graph entry node, and instead say
that the immediate dominator of B is the psuedo-entry node of the
augmented CFG.

The fix:

- Dominance is defined in terms of a traversal from the entry block
  of the CFG.  So the forward DFS should start from the function
  entry block, not the pseudo-entry-block.

- When following edges backward during dominance calculations, only go to
  nodes that are actually reachable in the forward traversal.
  Important: the sense of reachability flips around when computing
  post-dominance.

Fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/297
source/validate_cfg.cpp
test/Validate.CFG.cpp