OSDN Git Service

[Dominators] Add DFS number verification
authorJakub Kuderski <kubakuderski@gmail.com>
Tue, 3 Oct 2017 14:33:41 +0000 (14:33 +0000)
committerJakub Kuderski <kubakuderski@gmail.com>
Tue, 3 Oct 2017 14:33:41 +0000 (14:33 +0000)
commit7083930287fa87dbb94af6c931d36996468a0a6f
tree56fab6ec4eca6d15ae29127ca3703a784bcb37f4
parent4d5b9d65b5490d421a5c207aa0bbc025edce2e29
[Dominators] Add DFS number verification

Summary:
This patch teaches the DominatorTree verifier to check DFS In/Out numbers which are used to answer dominance queries.
DFS number verification is done in O(nlogn), so it shouldn't add much overhead on top of the O(n^3) sibling property verification.
This check should detect errors like the one spotted in PR34466 and related bug reports.

The patch also cleans up the DFS calculation a bit, as all constructed trees should have a single root now.

I see 2 new test failures when running check-all after this change:

```
Failing Tests (2):
    Polly :: Isl/CodeGen/OpenMP/reference-argument-from-non-affine-region.ll
    Polly :: Isl/CodeGen/OpenMP/two-parallel-loops-reference-outer-indvar.ll

```
which seem to happen just after `Create LLVM-IR from SCoPs` -- I XFAILed them in r314800.

Reviewers: dberlin, grosser, davide, zhendongsu, bollu

Reviewed By: dberlin

Subscribers: nandini12396, bollu, Meinersbur, brzycki, llvm-commits

Differential Revision: https://reviews.llvm.org/D38331

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@314801 91177308-0d34-0410-b5e6-96231b3b80d8
include/llvm/Support/GenericDomTree.h
include/llvm/Support/GenericDomTreeConstruction.h