Use pseudo entry and pseudo exit blocks for dominance.
authorDavid Neto <dneto@google.com>
Fri, 24 Jun 2016 06:14:16 +0000 (02:14 -0400)
committerDavid Neto <dneto@google.com>
Fri, 24 Jun 2016 21:08:20 +0000 (17:08 -0400)
commit50652277481d5b858c6c5e4de8ddbcc741451c1d
treeaa739e6cde9fe5c83d962f378fbfcaa2aa41140c
parent1a050b10692e07e5efd4892d968df904791baaaa
Use pseudo entry and pseudo exit blocks for dominance.

For dominance calculations we use an "augmented" CFG
where we always add a pseudo-entry node that is the predecessor
in the augmented CFG to any nodes that have no predecessors in the
regular CFG.  Similarly, we add a pseudo-exit node that is the
predecessor in the augmented CFG that is a successor to any
node that has no successors in the regular CFG.

Pseudo entry and exit blocks live in the Function object.

Fixes a subtle problem where we were implicitly creating
the block_details for the pseudo-exit node since it didn't
appear in the idoms map, and yet we referenced it.  In such a case the
contents of the block details could be garbage, or zero-initialized.
That sometimes caused incorrect calculation of immediate dominators
and post-dominators.  For example, on a debug build where the details
could be zero-initialized, the dominator of an unreachable block would
be given as the pseudo-exit node.  Bizarre.

Also, enforce the rule that you must have an OpFunctionEnd to close off
the last function.
source/val/BasicBlock.cpp
source/val/BasicBlock.h
source/val/Function.cpp
source/val/Function.h
source/val/ValidationState.cpp
source/validate.cpp
source/validate.h
source/validate_cfg.cpp
test/Validate.CFG.cpp
test/Validate.Layout.cpp