Szelethus created this revision.
Szelethus added reviewers: NoQ, kuhar, xazax.hun, rnkovacs, dcoughlin,
baloghadamsoftware, Charusso.
Szelethus added a project: clang.
Herald added subscribers: cfe-commits, gamesh411, dkrupp, donat.nagy,
mikhail.ramalho, a.sidorin, szepet, whisperity.
Szelethus added a parent revision: D62507: [Dominators] PR42041: Skip
nullpointer successors.
Transform `clang::DominatorTree` to be able to also calculate post dominators.
- Tidy up the documentation
- Rename `clang::DominatorTree` to `clang::CFGDominatorTree`
- Make it a template class, similarly to `llvm::DominatorTreeBase`
- Add a lot of asserts to the `dump()` function
- Create a new checker to test the functionality
Repository:
rC Clang
https://reviews.llvm.org/D62551
Files:
clang/include/clang/Analysis/Analyses/Dominators.h
clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
clang/lib/Analysis/Dominators.cpp
clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
clang/test/Analysis/domtest.c
clang/test/Analysis/domtest.cpp
Index: clang/test/Analysis/domtest.cpp
===================================================================
--- clang/test/Analysis/domtest.cpp
+++ clang/test/Analysis/domtest.cpp
@@ -1,6 +1,7 @@
// RUN: %clang_analyze_cc1 %s \
// RUN: -analyzer-checker=debug.DumpCFG \
// RUN: -analyzer-checker=debug.DumpDominators \
+// RUN: -analyzer-checker=debug.DumpPostDominators \
// RUN: 2>&1 | FileCheck %s
namespace pr42041_unreachable_cfg_successor {
@@ -44,3 +45,8 @@
// CHECK-NEXT: (1,3)
// CHECK-NEXT: (2,1)
// CHECK-NEXT: (3,3)
+// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,0)
+// CHECK-NEXT: (1,2)
+// CHECK-NEXT: (2,0)
+// CHECK-NEXT: (3,1)
Index: clang/test/Analysis/domtest.c
===================================================================
--- clang/test/Analysis/domtest.c
+++ clang/test/Analysis/domtest.c
@@ -1,6 +1,8 @@
-// RUN: rm -f %t
-// RUN: %clang_analyze_cc1 -analyzer-checker=debug.DumpDominators %s > %t 2>&1
-// RUN: FileCheck --input-file=%t %s
+// RUN: %clang_analyze_cc1 %s \
+// RUN: -analyzer-checker=debug.DumpCFG \
+// RUN: -analyzer-checker=debug.DumpDominators \
+// RUN: -analyzer-checker=debug.DumpPostDominators \
+// RUN: 2>&1 | FileCheck %s
// Test the DominatorsTree implementation with various control flows
int test1()
@@ -24,17 +26,130 @@
return 0;
}
-// CHECK: Immediate dominance tree (Node#,IDom#):
-// CHECK: (0,1)
-// CHECK: (1,7)
-// CHECK: (2,3)
-// CHECK: (3,6)
-// CHECK: (4,6)
-// CHECK: (5,6)
-// CHECK: (6,7)
-// CHECK: (7,8)
-// CHECK: (8,9)
-// CHECK: (9,9)
+// CHECK: int test1()
+// CHECK-NEXT: [B9 (ENTRY)]
+// CHECK-NEXT: Succs (1): B8
+//
+// CHECK: [B1]
+// CHECK-NEXT: 1: x
+// CHECK-NEXT: 2: [B1.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: y
+// CHECK-NEXT: 4: [B1.3] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 5: [B1.2] + [B1.4]
+// CHECK-NEXT: 6: z
+// CHECK-NEXT: 7: [B1.6] = [B1.5]
+// CHECK-NEXT: 8: 3
+// CHECK-NEXT: 9: z
+// CHECK-NEXT: 10: [B1.9] = [B1.8]
+// CHECK-NEXT: 11: 0
+// CHECK-NEXT: 12: return [B1.11];
+// CHECK-NEXT: Preds (1): B7
+// CHECK-NEXT: Succs (1): B0
+//
+// CHECK: [B2]
+// CHECK-NEXT: Preds (1): B3
+// CHECK-NEXT: Succs (1): B7
+//
+// CHECK: [B3]
+// CHECK-NEXT: 1: x
+// CHECK-NEXT: 2: [B3.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 1
+// CHECK-NEXT: 4: [B3.2] - [B3.3]
+// CHECK-NEXT: 5: x
+// CHECK-NEXT: 6: [B3.5] = [B3.4]
+// CHECK-NEXT: 7: x
+// CHECK-NEXT: 8: [B3.7] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 9: 1
+// CHECK-NEXT: 10: [B3.8] - [B3.9]
+// CHECK-NEXT: 11: x
+// CHECK-NEXT: 12: [B3.11] = [B3.10]
+// CHECK-NEXT: Preds (2): B4 B5
+// CHECK-NEXT: Succs (1): B2
+//
+// CHECK: [B4]
+// CHECK-NEXT: 1: x
+// CHECK-NEXT: 2: [B4.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: y
+// CHECK-NEXT: 4: [B4.3] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 5: [B4.2] - [B4.4]
+// CHECK-NEXT: 6: z
+// CHECK-NEXT: 7: [B4.6] = [B4.5]
+// CHECK-NEXT: Preds (1): B6
+// CHECK-NEXT: Succs (1): B3
+//
+// CHECK: [B5]
+// CHECK-NEXT: 1: x
+// CHECK-NEXT: 2: [B5.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: y
+// CHECK-NEXT: 4: [B5.3] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 5: [B5.2] / [B5.4]
+// CHECK-NEXT: 6: x
+// CHECK-NEXT: 7: [B5.6] = [B5.5]
+// CHECK-NEXT: 8: y
+// CHECK-NEXT: 9: [B5.8] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 10: 1
+// CHECK-NEXT: 11: [B5.9] - [B5.10]
+// CHECK-NEXT: 12: y
+// CHECK-NEXT: 13: [B5.12] = [B5.11]
+// CHECK-NEXT: Preds (1): B6
+// CHECK-NEXT: Succs (1): B3
+//
+// CHECK: [B6]
+// CHECK-NEXT: 1: y
+// CHECK-NEXT: 2: [B6.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: x
+// CHECK-NEXT: 4: [B6.3] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 5: [B6.2] < [B6.4]
+// CHECK-NEXT: T: if [B6.5]
+// CHECK-NEXT: Preds (1): B7
+// CHECK-NEXT: Succs (2): B5 B4
+//
+// CHECK: [B7]
+// CHECK-NEXT: 1: y
+// CHECK-NEXT: 2: [B7.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 0
+// CHECK-NEXT: 4: [B7.2] > [B7.3]
+// CHECK-NEXT: T: while [B7.4]
+// CHECK-NEXT: Preds (2): B2 B8
+// CHECK-NEXT: Succs (2): B6 B1
+//
+// CHECK: [B8]
+// CHECK-NEXT: 1: 6
+// CHECK-NEXT: 2: int x = 6;
+// CHECK-NEXT: 3: x
+// CHECK-NEXT: 4: [B8.3] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 5: 2
+// CHECK-NEXT: 6: [B8.4] / [B8.5]
+// CHECK-NEXT: 7: int y = x / 2;
+// CHECK-NEXT: 8: int z;
+// CHECK-NEXT: Preds (1): B9
+// CHECK-NEXT: Succs (1): B7
+//
+// CHECK: [B0 (EXIT)]
+// CHECK-NEXT: Preds (1): B1
+
+// CHECK: Immediate dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,1)
+// CHECK-NEXT: (1,7)
+// CHECK-NEXT: (2,3)
+// CHECK-NEXT: (3,6)
+// CHECK-NEXT: (4,6)
+// CHECK-NEXT: (5,6)
+// CHECK-NEXT: (6,7)
+// CHECK-NEXT: (7,8)
+// CHECK-NEXT: (8,9)
+// CHECK-NEXT: (9,9)
+// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,0)
+// CHECK-NEXT: (1,0)
+// CHECK-NEXT: (2,7)
+// CHECK-NEXT: (3,2)
+// CHECK-NEXT: (4,3)
+// CHECK-NEXT: (5,3)
+// CHECK-NEXT: (6,3)
+// CHECK-NEXT: (7,1)
+// CHECK-NEXT: (8,7)
+// CHECK-NEXT: (9,8)
int test2()
{
@@ -54,15 +169,87 @@
return 0;
}
-// CHECK: Immediate dominance tree (Node#,IDom#):
-// CHECK: (0,1)
-// CHECK: (1,6)
-// CHECK: (2,3)
-// CHECK: (3,4)
-// CHECK: (4,6)
-// CHECK: (5,6)
-// CHECK: (6,7)
-// CHECK: (7,7)
+// CHECK: int test2()
+// CHECK-NEXT: [B7 (ENTRY)]
+// CHECK-NEXT: Succs (1): B6
+//
+// CHECK: [B1]
+// CHECK-NEXT: 1: y
+// CHECK-NEXT: 2: [B1.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: z
+// CHECK-NEXT: 4: [B1.3] = [B1.2]
+// CHECK-NEXT: 5: 0
+// CHECK-NEXT: 6: return [B1.5];
+// CHECK-NEXT: Preds (2): B4 B5
+// CHECK-NEXT: Succs (1): B0
+//
+// CHECK: [B2]
+// CHECK-NEXT: Preds (1): B3
+// CHECK-NEXT: Succs (1): B4
+//
+// CHECK: [B3]
+// CHECK-NEXT: 1: x
+// CHECK-NEXT: 2: [B3.1]++
+// CHECK-NEXT: 3: y
+// CHECK-NEXT: 4: [B3.3]++
+// CHECK-NEXT: Preds (1): B4
+// CHECK-NEXT: Succs (1): B2
+//
+// CHECK: [B4]
+// CHECK-NEXT: 1: x
+// CHECK-NEXT: 2: [B4.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 0
+// CHECK-NEXT: 4: [B4.2] <= [B4.3]
+// CHECK-NEXT: T: while [B4.4]
+// CHECK-NEXT: Preds (2): B2 B6
+// CHECK-NEXT: Succs (2): B3 B1
+//
+// CHECK: [B5]
+// CHECK-NEXT: 1: 1
+// CHECK-NEXT: 2: y
+// CHECK-NEXT: 3: [B5.2] = [B5.1]
+// CHECK-NEXT: Preds (1): B6
+// CHECK-NEXT: Succs (1): B1
+//
+// CHECK: [B6]
+// CHECK-NEXT: 1: int x;
+// CHECK-NEXT: 2: int y;
+// CHECK-NEXT: 3: int z;
+// CHECK-NEXT: 4: 10
+// CHECK-NEXT: 5: x
+// CHECK-NEXT: 6: [B6.5] = [B6.4]
+// CHECK-NEXT: 7: 100
+// CHECK-NEXT: 8: y
+// CHECK-NEXT: 9: [B6.8] = [B6.7]
+// CHECK-NEXT: 10: x
+// CHECK-NEXT: 11: [B6.10] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 12: 0
+// CHECK-NEXT: 13: [B6.11] > [B6.12]
+// CHECK-NEXT: T: if [B6.13]
+// CHECK-NEXT: Preds (1): B7
+// CHECK-NEXT: Succs (2): B5 B4
+//
+// CHECK: [B0 (EXIT)]
+// CHECK-NEXT: Preds (1): B1
+
+// CHECK: Immediate dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,1)
+// CHECK-NEXT: (1,6)
+// CHECK-NEXT: (2,3)
+// CHECK-NEXT: (3,4)
+// CHECK-NEXT: (4,6)
+// CHECK-NEXT: (5,6)
+// CHECK-NEXT: (6,7)
+// CHECK-NEXT: (7,7)
+// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,0)
+// CHECK-NEXT: (1,0)
+// CHECK-NEXT: (2,4)
+// CHECK-NEXT: (3,2)
+// CHECK-NEXT: (4,1)
+// CHECK-NEXT: (5,1)
+// CHECK-NEXT: (6,1)
+// CHECK-NEXT: (7,6)
int test3()
{
@@ -82,16 +269,105 @@
return 0;
}
-// CHECK: Immediate dominance tree (Node#,IDom#):
-// CHECK: (0,1)
-// CHECK: (1,7)
-// CHECK: (2,5)
-// CHECK: (3,4)
-// CHECK: (4,5)
-// CHECK: (5,6)
-// CHECK: (6,7)
-// CHECK: (7,8)
-// CHECK: (8,8)
+// CHECK: int test3()
+// CHECK-NEXT: [B8 (ENTRY)]
+// CHECK-NEXT: Succs (1): B7
+//
+// CHECK: [B1]
+// CHECK-NEXT: 1: y
+// CHECK-NEXT: 2: [B1.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: z
+// CHECK-NEXT: 4: [B1.3] = [B1.2]
+// CHECK-NEXT: 5: 0
+// CHECK-NEXT: 6: return [B1.5];
+// CHECK-NEXT: Preds (2): B6 B7
+// CHECK-NEXT: Succs (1): B0
+//
+// CHECK: [B2]
+// CHECK-NEXT: Preds (1): B5
+// CHECK-NEXT: Succs (1): B6
+//
+// CHECK: [B3]
+// CHECK-NEXT: Preds (1): B4
+// CHECK-NEXT: Succs (1): B5
+//
+// CHECK: [B4]
+// CHECK-NEXT: 1: x
+// CHECK-NEXT: 2: [B4.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 1
+// CHECK-NEXT: 4: [B4.2] - [B4.3]
+// CHECK-NEXT: 5: x
+// CHECK-NEXT: 6: [B4.5] = [B4.4]
+// CHECK-NEXT: 7: y
+// CHECK-NEXT: 8: [B4.7] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 9: 2
+// CHECK-NEXT: 10: [B4.8] / [B4.9]
+// CHECK-NEXT: 11: y
+// CHECK-NEXT: 12: [B4.11] = [B4.10]
+// CHECK-NEXT: Preds (1): B5
+// CHECK-NEXT: Succs (1): B3
+//
+// CHECK: [B5]
+// CHECK-NEXT: 1: y
+// CHECK-NEXT: 2: [B5.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: x
+// CHECK-NEXT: 4: [B5.3] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 5: [B5.2] >= [B5.4]
+// CHECK-NEXT: T: while [B5.5]
+// CHECK-NEXT: Preds (2): B3 B6
+// CHECK-NEXT: Succs (2): B4 B2
+//
+// CHECK: [B6]
+// CHECK-NEXT: 1: x
+// CHECK-NEXT: 2: [B6.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 0
+// CHECK-NEXT: 4: [B6.2] >= [B6.3]
+// CHECK-NEXT: T: while [B6.4]
+// CHECK-NEXT: Preds (2): B2 B7
+// CHECK-NEXT: Succs (2): B5 B1
+//
+// CHECK: [B7]
+// CHECK-NEXT: 1: int x;
+// CHECK-NEXT: 2: int y;
+// CHECK-NEXT: 3: int z;
+// CHECK-NEXT: 4: 1
+// CHECK-NEXT: 5: z
+// CHECK-NEXT: 6: [B7.5] = [B7.4]
+// CHECK-NEXT: 7: y
+// CHECK-NEXT: 8: [B7.7] = [B7.6]
+// CHECK-NEXT: 9: x
+// CHECK-NEXT: 10: [B7.9] = [B7.8]
+// CHECK-NEXT: 11: x
+// CHECK-NEXT: 12: [B7.11] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 13: 0
+// CHECK-NEXT: 14: [B7.12] > [B7.13]
+// CHECK-NEXT: T: if [B7.14]
+// CHECK-NEXT: Preds (1): B8
+// CHECK-NEXT: Succs (2): B6 B1
+//
+// CHECK: [B0 (EXIT)]
+// CHECK-NEXT: Preds (1): B1
+
+// CHECK: Immediate dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,1)
+// CHECK-NEXT: (1,7)
+// CHECK-NEXT: (2,5)
+// CHECK-NEXT: (3,4)
+// CHECK-NEXT: (4,5)
+// CHECK-NEXT: (5,6)
+// CHECK-NEXT: (6,7)
+// CHECK-NEXT: (7,8)
+// CHECK-NEXT: (8,8)
+// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,0)
+// CHECK-NEXT: (1,0)
+// CHECK-NEXT: (2,6)
+// CHECK-NEXT: (3,5)
+// CHECK-NEXT: (4,3)
+// CHECK-NEXT: (5,2)
+// CHECK-NEXT: (6,1)
+// CHECK-NEXT: (7,1)
+// CHECK-NEXT: (8,7)
int test4()
{
@@ -108,20 +384,113 @@
return 0;
}
-// CHECK: Immediate dominance tree (Node#,IDom#):
-// CHECK: (0,1)
-// CHECK: (1,10)
-// CHECK: (2,9)
-// CHECK: (3,4)
-// CHECK: (4,5)
-// CHECK: (5,9)
-// CHECK: (6,7)
-// CHECK: (7,8)
-// CHECK: (8,9)
-// CHECK: (9,10)
-// CHECK: (10,11)
-// CHECK: (11,12)
-// CHECK: (12,12)
+// CHECK: int test4()
+// CHECK-NEXT: [B12 (ENTRY)]
+// CHECK-NEXT: Succs (1): B11
+//
+// CHECK: [B1]
+// CHECK-NEXT: 1: 0
+// CHECK-NEXT: 2: return [B1.1];
+// CHECK-NEXT: Preds (1): B10
+// CHECK-NEXT: Succs (1): B0
+//
+// CHECK: [B2]
+// CHECK-NEXT: Preds (2): B5 B8
+// CHECK-NEXT: Succs (1): B10
+//
+// CHECK: [B3]
+// CHECK-NEXT: Preds (1): B4
+// CHECK-NEXT: Succs (1): B5
+//
+// CHECK: [B4]
+// CHECK-NEXT: 1: y
+// CHECK-NEXT: 2: [B4.1]++
+// CHECK-NEXT: Preds (1): B5
+// CHECK-NEXT: Succs (1): B3
+//
+// CHECK: [B5]
+// CHECK-NEXT: 1: y
+// CHECK-NEXT: 2: [B5.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 10
+// CHECK-NEXT: 4: [B5.2] < [B5.3]
+// CHECK-NEXT: T: while [B5.4]
+// CHECK-NEXT: Preds (2): B3 B9
+// CHECK-NEXT: Succs (2): B4 B2
+//
+// CHECK: [B6]
+// CHECK-NEXT: Preds (1): B7
+// CHECK-NEXT: Succs (1): B8
+//
+// CHECK: [B7]
+// CHECK-NEXT: 1: y
+// CHECK-NEXT: 2: [B7.1]++
+// CHECK-NEXT: Preds (1): B8
+// CHECK-NEXT: Succs (1): B6
+//
+// CHECK: [B8]
+// CHECK-NEXT: 1: y
+// CHECK-NEXT: 2: [B8.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 0
+// CHECK-NEXT: 4: [B8.2] > [B8.3]
+// CHECK-NEXT: T: while [B8.4]
+// CHECK-NEXT: Preds (2): B6 B9
+// CHECK-NEXT: Succs (2): B7 B2
+//
+// CHECK: [B9]
+// CHECK-NEXT: 1: y
+// CHECK-NEXT: 2: [B9.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 3
+// CHECK-NEXT: 4: [B9.2] < [B9.3]
+// CHECK-NEXT: T: if [B9.4]
+// CHECK-NEXT: Preds (1): B10
+// CHECK-NEXT: Succs (2): B8 B5
+//
+// CHECK: [B10]
+// CHECK-NEXT: 1: y
+// CHECK-NEXT: 2: [B10.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 0
+// CHECK-NEXT: 4: [B10.2] > [B10.3]
+// CHECK-NEXT: T: while [B10.4]
+// CHECK-NEXT: Preds (2): B2 B11
+// CHECK-NEXT: Succs (2): B9 B1
+//
+// CHECK: [B11]
+// CHECK-NEXT: 1: 3
+// CHECK-NEXT: 2: int y = 3;
+// CHECK-NEXT: Preds (1): B12
+// CHECK-NEXT: Succs (1): B10
+//
+// CHECK: [B0 (EXIT)]
+// CHECK-NEXT: Preds (1): B1
+
+// CHECK: Immediate dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,1)
+// CHECK-NEXT: (1,10)
+// CHECK-NEXT: (2,9)
+// CHECK-NEXT: (3,4)
+// CHECK-NEXT: (4,5)
+// CHECK-NEXT: (5,9)
+// CHECK-NEXT: (6,7)
+// CHECK-NEXT: (7,8)
+// CHECK-NEXT: (8,9)
+// CHECK-NEXT: (9,10)
+// CHECK-NEXT: (10,11)
+// CHECK-NEXT: (11,12)
+// CHECK-NEXT: (12,12)
+// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,0)
+// CHECK-NEXT: (1,0)
+// CHECK-NEXT: (2,10)
+// CHECK-NEXT: (3,5)
+// CHECK-NEXT: (4,3)
+// CHECK-NEXT: (5,2)
+// CHECK-NEXT: (6,8)
+// CHECK-NEXT: (7,6)
+// CHECK-NEXT: (8,2)
+// CHECK-NEXT: (9,2)
+// CHECK-NEXT: (10,1)
+// CHECK-NEXT: (11,10)
+// CHECK-NEXT: (12,11)
int test5()
{
@@ -151,18 +520,138 @@
return 0;
}
-// CHECK: Immediate dominance tree (Node#,IDom#):
-// CHECK: (0,1)
-// CHECK: (1,10)
-// CHECK: (2,10)
-// CHECK: (3,9)
-// CHECK: (4,9)
-// CHECK: (5,8)
-// CHECK: (6,8)
-// CHECK: (7,8)
-// CHECK: (8,9)
-// CHECK: (9,10)
-// CHECK: (10,11)
-// CHECK: (11,11)
-
+// CHECK: int test5()
+// CHECK-NEXT: [B11 (ENTRY)]
+// CHECK-NEXT: Succs (1): B10
+//
+// CHECK: [B1]
+// CHECK-NEXT: 1: 11
+// CHECK-NEXT: 2: c
+// CHECK-NEXT: 3: [B1.2] = [B1.1]
+// CHECK-NEXT: 4: 0
+// CHECK-NEXT: 5: return [B1.4];
+// CHECK-NEXT: Preds (2): B2 B3
+// CHECK-NEXT: Succs (1): B0
+//
+// CHECK: [B2]
+// CHECK-NEXT: 1: 7
+// CHECK-NEXT: 2: x
+// CHECK-NEXT: 3: [B2.2] = [B2.1]
+// CHECK-NEXT: Preds (1): B10
+// CHECK-NEXT: Succs (1): B1
+//
+// CHECK: [B3]
+// CHECK-NEXT: 1: 10
+// CHECK-NEXT: 2: b
+// CHECK-NEXT: 3: [B3.2] = [B3.1]
+// CHECK-NEXT: Preds (2): B4 B5
+// CHECK-NEXT: Succs (1): B1
+//
+// CHECK: [B4]
+// CHECK-NEXT: 1: 6
+// CHECK-NEXT: 2: x
+// CHECK-NEXT: 3: [B4.2] = [B4.1]
+// CHECK-NEXT: Preds (1): B9
+// CHECK-NEXT: Succs (1): B3
+//
+// CHECK: [B5]
+// CHECK-NEXT: 1: 10
+// CHECK-NEXT: 2: a
+// CHECK-NEXT: 3: [B5.2] = [B5.1]
+// CHECK-NEXT: Preds (2): B6 B7
+// CHECK-NEXT: Succs (1): B3
+//
+// CHECK: [B6]
+// CHECK-NEXT: 1: 5
+// CHECK-NEXT: 2: x
+// CHECK-NEXT: 3: [B6.2] = [B6.1]
+// CHECK-NEXT: Preds (1): B8
+// CHECK-NEXT: Succs (1): B5
+//
+// CHECK: [B7]
+// CHECK-NEXT: 1: 4
+// CHECK-NEXT: 2: x
+// CHECK-NEXT: 3: [B7.2] = [B7.1]
+// CHECK-NEXT: Preds (1): B8
+// CHECK-NEXT: Succs (1): B5
+//
+// CHECK: [B8]
+// CHECK-NEXT: 1: z
+// CHECK-NEXT: 2: [B8.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 10
+// CHECK-NEXT: 4: [B8.2] < [B8.3]
+// CHECK-NEXT: T: if [B8.4]
+// CHECK-NEXT: Preds (1): B9
+// CHECK-NEXT: Succs (2): B7 B6
+//
+// CHECK: [B9]
+// CHECK-NEXT: 1: y
+// CHECK-NEXT: 2: [B9.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 10
+// CHECK-NEXT: 4: [B9.2] < [B9.3]
+// CHECK-NEXT: T: if [B9.4]
+// CHECK-NEXT: Preds (1): B10
+// CHECK-NEXT: Succs (2): B8 B4
+//
+// CHECK: [B10]
+// CHECK-NEXT: 1: int x;
+// CHECK-NEXT: 2: int y;
+// CHECK-NEXT: 3: int z;
+// CHECK-NEXT: 4: int a;
+// CHECK-NEXT: 5: int b;
+// CHECK-NEXT: 6: int c;
+// CHECK-NEXT: 7: 1
+// CHECK-NEXT: 8: x
+// CHECK-NEXT: 9: [B10.8] = [B10.7]
+// CHECK-NEXT: 10: 2
+// CHECK-NEXT: 11: y
+// CHECK-NEXT: 12: [B10.11] = [B10.10]
+// CHECK-NEXT: 13: 3
+// CHECK-NEXT: 14: z
+// CHECK-NEXT: 15: [B10.14] = [B10.13]
+// CHECK-NEXT: 16: 4
+// CHECK-NEXT: 17: a
+// CHECK-NEXT: 18: [B10.17] = [B10.16]
+// CHECK-NEXT: 19: 5
+// CHECK-NEXT: 20: b
+// CHECK-NEXT: 21: [B10.20] = [B10.19]
+// CHECK-NEXT: 22: 6
+// CHECK-NEXT: 23: c
+// CHECK-NEXT: 24: [B10.23] = [B10.22]
+// CHECK-NEXT: 25: x
+// CHECK-NEXT: 26: [B10.25] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 27: 10
+// CHECK-NEXT: 28: [B10.26] < [B10.27]
+// CHECK-NEXT: T: if [B10.28]
+// CHECK-NEXT: Preds (1): B11
+// CHECK-NEXT: Succs (2): B9 B2
+//
+// CHECK: [B0 (EXIT)]
+// CHECK-NEXT: Preds (1): B1
+// CHECK: Immediate dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,1)
+// CHECK-NEXT: (1,10)
+// CHECK-NEXT: (2,10)
+// CHECK-NEXT: (3,9)
+// CHECK-NEXT: (4,9)
+// CHECK-NEXT: (5,8)
+// CHECK-NEXT: (6,8)
+// CHECK-NEXT: (7,8)
+// CHECK-NEXT: (8,9)
+// CHECK-NEXT: (9,10)
+// CHECK-NEXT: (10,11)
+// CHECK-NEXT: (11,11)
+// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,0)
+// CHECK-NEXT: (1,0)
+// CHECK-NEXT: (2,1)
+// CHECK-NEXT: (3,1)
+// CHECK-NEXT: (4,3)
+// CHECK-NEXT: (5,3)
+// CHECK-NEXT: (6,5)
+// CHECK-NEXT: (7,5)
+// CHECK-NEXT: (8,5)
+// CHECK-NEXT: (9,3)
+// CHECK-NEXT: (10,1)
+// CHECK-NEXT: (11,10)
Index: clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
+++ clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
@@ -36,7 +36,7 @@
BugReporter &BR) const {
if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) {
DominatorTree dom;
- dom.buildDominatorTree(*AC);
+ dom.buildDominatorTree(AC->getCFG());
dom.dump();
}
}
@@ -51,6 +51,32 @@
return true;
}
+//===----------------------------------------------------------------------===//
+// PostDominatorsTreeDumper
+//===----------------------------------------------------------------------===//
+
+namespace {
+class PostDominatorsTreeDumper : public Checker<check::ASTCodeBody> {
+public:
+ void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
+ BugReporter &BR) const {
+ if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) {
+ PostDominatorTree dom;
+ dom.buildDominatorTree(AC->getCFG());
+ dom.dump();
+ }
+ }
+};
+}
+
+void ento::registerPostDominatorsTreeDumper(CheckerManager &mgr) {
+ mgr.registerChecker<PostDominatorsTreeDumper>();
+}
+
+bool ento::shouldRegisterPostDominatorsTreeDumper(const LangOptions &LO) {
+ return true;
+}
+
//===----------------------------------------------------------------------===//
// LiveVariablesDumper
//===----------------------------------------------------------------------===//
Index: clang/lib/Analysis/Dominators.cpp
===================================================================
--- clang/lib/Analysis/Dominators.cpp
+++ clang/lib/Analysis/Dominators.cpp
@@ -10,4 +10,8 @@
using namespace clang;
-void DominatorTree::anchor() {}
+template <>
+void CFGDominatorTree</*IsPostDom=*/true>::anchor() {}
+
+template <>
+void CFGDominatorTree</*IsPostDom=*/false>::anchor() {}
Index: clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
===================================================================
--- clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
+++ clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
@@ -1229,6 +1229,10 @@
HelpText<"Print the dominance tree for a given CFG">,
Documentation<NotDocumented>;
+def PostDominatorsTreeDumper : Checker<"DumpPostDominators">,
+ HelpText<"Print the post dominance tree for a given CFG">,
+ Documentation<NotDocumented>;
+
def LiveVariablesDumper : Checker<"DumpLiveVars">,
HelpText<"Print results of live variable analysis">,
Documentation<NotDocumented>;
Index: clang/include/clang/Analysis/Analyses/Dominators.h
===================================================================
--- clang/include/clang/Analysis/Analyses/Dominators.h
+++ clang/include/clang/Analysis/Analyses/Dominators.h
@@ -39,35 +39,37 @@
/// Concrete subclass of DominatorTreeBase for Clang
/// This class implements the dominators tree functionality given a Clang CFG.
///
-class DominatorTree : public ManagedAnalysis {
+template <bool IsPostDom>
+class CFGDominatorTree : public ManagedAnalysis {
virtual void anchor();
public:
- llvm::DomTreeBase<CFGBlock> *DT;
+ using DomTreeBase = llvm::DominatorTreeBase<CFGBlock, IsPostDom>;
- DominatorTree() {
- DT = new llvm::DomTreeBase<CFGBlock>();
+ DomTreeBase *DT;
+
+ CFGDominatorTree() {
+ DT = new DomTreeBase();
}
- ~DominatorTree() override { delete DT; }
+ ~CFGDominatorTree() override { delete DT; }
- llvm::DomTreeBase<CFGBlock>& getBase() { return *DT; }
+ DomTreeBase& getBase() { return *DT; }
- /// This method returns the root CFGBlock of the dominators tree.
+ /// \returns the root CFGBlock of the dominators tree.
CFGBlock *getRoot() const {
return DT->getRoot();
}
- /// This method returns the root DomTreeNode, which is the wrapper
- /// for CFGBlock.
+ /// \returns the root DomTreeNode, which is the wrapper for CFGBlock.
DomTreeNode *getRootNode() const {
return DT->getRootNode();
}
- /// This method compares two dominator trees.
- /// The method returns false if the other dominator tree matches this
- /// dominator tree, otherwise returns true.
- bool compare(DominatorTree &Other) const {
+ /// Compares two dominator trees.
+ /// \returns false if the other dominator tree matches this dominator tree,
+ /// false otherwise.
+ bool compare(CFGDominatorTree &Other) const {
DomTreeNode *R = getRootNode();
DomTreeNode *OtherR = Other.getRootNode();
@@ -80,44 +82,61 @@
return false;
}
- /// This method builds the dominator tree for a given CFG
- /// The CFG information is passed via AnalysisDeclContext
- void buildDominatorTree(AnalysisDeclContext &AC) {
- cfg = AC.getCFG();
+ /// Builds the dominator tree for a given CFG.
+ void buildDominatorTree(CFG *cfg) {
+ assert(cfg);
+ this->cfg = cfg;
DT->recalculate(*cfg);
}
- /// This method dumps immediate dominators for each block,
- /// mainly used for debug purposes.
+ /// Dumps immediate dominators for each block.
void dump() {
- llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n";
- for (CFG::const_iterator I = cfg->begin(),
- E = cfg->end(); I != E; ++I) {
- if(DT->getNode(*I)->getIDom())
- llvm::errs() << "(" << (*I)->getBlockID()
- << ","
- << DT->getNode(*I)->getIDom()->getBlock()->getBlockID()
- << ")\n";
- else llvm::errs() << "(" << (*I)->getBlockID()
- << "," << (*I)->getBlockID() << ")\n";
+ llvm::errs() << "Immediate " << (IsPostDom ? "post " : "")
+ << "dominance tree (Node#,IDom#):\n";
+ for (CFG::const_iterator I = cfg->begin(),
+ E = cfg->end(); I != E; ++I) {
+
+ assert(*I &&
+ "LLVM's Dominator tree builder uses nullpointers to signify the "
+ "virtual root!");
+
+ DomTreeNode *IDom = DT->getNode(*I)->getIDom();
+ if (IDom && IDom->getBlock())
+ llvm::errs() << "(" << (*I)->getBlockID()
+ << ","
+ << IDom->getBlock()->getBlockID()
+ << ")\n";
+ else {
+ assert(
+ (IDom && !IDom->getBlock() && *I == &(*I)->getParent()->getExit() &&
+ IsPostDom) ||
+ (!IDom && *I == &(*I)->getParent()->getEntry() && !IsPostDom) &&
+ "If the immediate dominator node is nullptr, the CFG block should be"
+ "the exit point (since it's the root of the dominator tree), or if"
+ "the CFG block it refers to is a nullpointer, it must be the entry"
+ "block (since it's the root of the post dominator tree)");
+
+ llvm::errs() << "(" << (*I)->getBlockID()
+ << "," << (*I)->getBlockID() << ")\n";
}
}
+}
- /// This method tests if one CFGBlock dominates the other.
- /// The method return true if A dominates B, false otherwise.
+ /// Tests whether \p A dominates \p B.
/// Note a block always dominates itself.
bool dominates(const CFGBlock *A, const CFGBlock *B) const {
return DT->dominates(A, B);
}
- /// This method tests if one CFGBlock properly dominates the other.
- /// The method return true if A properly dominates B, false otherwise.
+ /// Tests whether \p A properly dominates \p B.
+ /// \returns false if \p A is the same block as \p B, otherwise whether A
+ /// dominates B.
bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const {
return DT->properlyDominates(A, B);
}
- /// This method finds the nearest common dominator CFG block
- /// for CFG block A and B. If there is no such block then return NULL.
+ /// \returns the nearest common dominator CFG block for CFG block \p A and \p
+ /// B. If there is no such block then return NULL.
CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) {
return DT->findNearestCommonDominator(A, B);
}
@@ -127,24 +146,23 @@
return DT->findNearestCommonDominator(A, B);
}
- /// This method is used to update the dominator
- /// tree information when a node's immediate dominator changes.
+ /// Update the dominator tree information when a node's immediate dominator
+ /// changes.
void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {
DT->changeImmediateDominator(N, NewIDom);
}
- /// This method tests if the given CFGBlock can be reachable from root.
- /// Returns true if reachable, false otherwise.
+ /// Tests whether \p A is reachable from the entry block.
bool isReachableFromEntry(const CFGBlock *A) {
return DT->isReachableFromEntry(A);
}
- /// This method releases the memory held by the dominator tree.
+ /// Releases the memory held by the dominator tree.
virtual void releaseMemory() {
DT->releaseMemory();
}
- /// This method converts the dominator tree to human readable form.
+ /// Converts the dominator tree to human readable form.
virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
DT->print(OS);
}
@@ -153,6 +171,9 @@
CFG *cfg;
};
+using DominatorTree = CFGDominatorTree</*IsPostDom*/ false>;
+using PostDominatorTree = CFGDominatorTree</*IsPostDom*/ true>;
+
} // namespace clang
namespace llvm {
@@ -167,7 +188,8 @@
namespace DomTreeBuilder {
using ClangCFGDomChildrenGetter =
-SemiNCAInfo<DomTreeBase<clang::CFGBlock>>::ChildrenGetter</*Inverse=*/false>;
+SemiNCAInfo<clang::DominatorTree::DomTreeBase>::ChildrenGetter<
+ /*Inverse=*/false>;
template <>
template <>
@@ -180,7 +202,8 @@
}
using ClangCFGDomReverseChildrenGetter =
-SemiNCAInfo<DomTreeBase<clang::CFGBlock>>::ChildrenGetter</*Inverse=*/true>;
+SemiNCAInfo<clang::DominatorTree::DomTreeBase>::ChildrenGetter<
+ /*Inverse=*/true>;
template <>
template <>
@@ -193,6 +216,35 @@
return Ret;
}
+using ClangCFGPostDomChildrenGetter =
+SemiNCAInfo<clang::PostDominatorTree::DomTreeBase>::ChildrenGetter<
+ /*Inverse=*/false>;
+
+template <>
+template <>
+ClangCFGPostDomChildrenGetter::ResultTy ClangCFGPostDomChildrenGetter::Get(
+ clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/false>) {
+ auto RChildren = reverse(children<NodePtr>(N));
+ ResultTy Ret(RChildren.begin(), RChildren.end());
+ Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
+ return Ret;
+}
+
+using ClangCFGPostDomReverseChildrenGetter =
+SemiNCAInfo<clang::PostDominatorTree::DomTreeBase>::ChildrenGetter<
+ /*Inverse=*/true>;
+
+template <>
+template <>
+ClangCFGPostDomReverseChildrenGetter::ResultTy
+ClangCFGPostDomReverseChildrenGetter::Get(
+ clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) {
+ auto IChildren = inverse_children<NodePtr>(N);
+ ResultTy Ret(IChildren.begin(), IChildren.end());
+ Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
+ return Ret;
+}
+
} // end of namespace DomTreeBuilder
//===-------------------------------------
@@ -219,17 +271,17 @@
}
};
-template <> struct GraphTraits< ::clang::DominatorTree* >
+template <> struct GraphTraits<clang::DominatorTree *>
: public GraphTraits< ::clang::DomTreeNode* > {
- static NodeRef getEntryNode(::clang::DominatorTree *DT) {
+ static NodeRef getEntryNode(clang::DominatorTree *DT) {
return DT->getRootNode();
}
- static nodes_iterator nodes_begin(::clang::DominatorTree *N) {
+ static nodes_iterator nodes_begin(clang::DominatorTree *N) {
return nodes_iterator(df_begin(getEntryNode(N)));
}
- static nodes_iterator nodes_end(::clang::DominatorTree *N) {
+ static nodes_iterator nodes_end(clang::DominatorTree *N) {
return nodes_iterator(df_end(getEntryNode(N)));
}
};
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
