InstrProf: Avoid repeated linear searches in a hot path
When generating coverage regions, we were doing a linear search
through the existing regions in order to try to merge related ones.
Most of the time this would find what it was looking for in a small
number of steps and it wasn't a big deal, but in cases with many
regions and few mergeable ones this leads to an absurd compile time
regression.
This changes the coverage mapping logic to do a single sort and then
merge as we go, which is a bit simpler and about 100 times faster.
I've also added FIXMEs on a couple of behaviours that seem a little
suspect, while keeping them behaving as they were - I'll look into
these soon.
The test changes here are mostly tedious reorganization, because the
ordering of regions we output has become slightly (but not completely)
more consistent from the almost completely arbitrary ordering we got
before.
llvm-svn: 218738
diff --git a/clang/test/CoverageMapping/macroception.c b/clang/test/CoverageMapping/macroception.c
index 7db02be..edbd84a 100644
--- a/clang/test/CoverageMapping/macroception.c
+++ b/clang/test/CoverageMapping/macroception.c
@@ -5,33 +5,36 @@
#define M22 }
#define M11 M22
- // CHECK: main
- // CHECK-NEXT: File 0, 3:12 -> 3:13 = #0 (HasCodeBefore = 0)
- // CHECK-NEXT: Expansion,File 1, 4:12 -> 4:14 = #0 (HasCodeBefore = 0, Expanded file = 0)
-int main() M1 // CHECK-NEXT: Expansion,File 2, [[@LINE]]:12 -> [[@LINE]]:14 = #0 (HasCodeBefore = 0, Expanded file = 1)
- return 0; // CHECK-NEXT: File 2, [[@LINE]]:3 -> [[@LINE+1]]:2 = #0 (HasCodeBefore = 0)
+// CHECK-LABEL: main:
+int main() M1 // CHECK-NEXT: Expansion,File 0, [[@LINE]]:12 -> [[@LINE]]:14 = #0 (HasCodeBefore = 0, Expanded file = 2)
+ return 0; // CHECK-NEXT: File 0, [[@LINE]]:3 -> [[@LINE+1]]:2 = #0 (HasCodeBefore = 0)
}
+// CHECK-NEXT: File 1, 3:12 -> 3:13 = #0 (HasCodeBefore = 0)
+// CHECK-NEXT: Expansion,File 2, 4:12 -> 4:14 = #0 (HasCodeBefore = 0, Expanded file = 1)
- // CHECK-NEXT: func2
+
+// CHECK-LABEL: func2:
void func2() { // CHECK-NEXT: File 0, [[@LINE]]:14 -> [[@LINE+1]]:12 = #0 (HasCodeBefore = 0)
int x = 0;
M11 // CHECK-NEXT: Expansion,File 0, [[@LINE]]:1 -> [[@LINE]]:4 = #0 (HasCodeBefore = 0, Expanded file = 2)
- // CHECK-NEXT: File 1, 5:13 -> 5:14 = #0 (HasCodeBefore = 0)
- // CHECK-NEXT: Expansion,File 2, 6:13 -> 6:16 = #0 (HasCodeBefore = 0, Expanded file = 1)
+// CHECK-NEXT: File 1, 5:13 -> 5:14 = #0 (HasCodeBefore = 0)
+// CHECK-NEXT: Expansion,File 2, 6:13 -> 6:16 = #0 (HasCodeBefore = 0, Expanded file = 1)
- // CHECK-NEXT: func3
- // CHECK-NEXT: File 0, 3:12 -> 3:13 = #0 (HasCodeBefore = 0)
- // CHECK-NEXT: Expansion,File 1, 4:12 -> 4:14 = #0 (HasCodeBefore = 0, Expanded file = 0)
-void func3() M1 // CHECK-NEXT: Expansion,File 2, [[@LINE]]:14 -> [[@LINE]]:16 = #0 (HasCodeBefore = 0, Expanded file = 1)
- int x = 0; // CHECK-NEXT: File 2, [[@LINE]]:3 -> [[@LINE]]:12 = #0 (HasCodeBefore = 0)
-M11 // CHECK-NEXT: Expansion,File 2, [[@LINE]]:1 -> [[@LINE]]:4 = #0 (HasCodeBefore = 0, Expanded file = 4)
- // CHECK-NEXT: File 3, 5:13 -> 5:14 = #0 (HasCodeBefore = 0)
- // CHECK-NEXT: Expansion,File 4, 6:13 -> 6:16 = #0 (HasCodeBefore = 0, Expanded file = 3)
+// CHECK-LABEL: func3:
+void func3() M1 // CHECK-NEXT: Expansion,File 0, [[@LINE]]:14 -> [[@LINE]]:16 = #0 (HasCodeBefore = 0, Expanded file = 2)
+ int x = 0; // CHECK-NEXT: File 0, [[@LINE]]:3 -> [[@LINE]]:12 = #0 (HasCodeBefore = 0)
+M11 // CHECK-NEXT: Expansion,File 0, [[@LINE]]:1 -> [[@LINE]]:4 = #0 (HasCodeBefore = 0, Expanded file = 4)
- // CHECK-NEXT: func4
- // CHECK-NEXT: File 0, 3:12 -> 3:13 = #0 (HasCodeBefore = 0)
- // CHECK-NEXT: Expansion,File 1, 4:12 -> 4:14 = #0 (HasCodeBefore = 0, Expanded file = 0)
- // CHECK-NEXT: Expansion,File 2, [[@LINE+1]]:14 -> [[@LINE+1]]:16 = #0 (HasCodeBefore = 0, Expanded file = 1)
-void func4() M1 M11 // CHECK-NEXT: Expansion,File 2, [[@LINE]]:17 -> [[@LINE]]:20 = #0 (HasCodeBefore = 0, Expanded file = 4)
- // CHECK-NEXT: File 3, 5:13 -> 5:14 = #0 (HasCodeBefore = 0)
- // CHECK-NEXT: Expansion,File 4, 6:13 -> 6:16 = #0 (HasCodeBefore = 0, Expanded file = 3)
+// CHECK-NEXT: File 1, 3:12 -> 3:13 = #0 (HasCodeBefore = 0)
+// CHECK-NEXT: Expansion,File 2, 4:12 -> 4:14 = #0 (HasCodeBefore = 0, Expanded file = 1)
+// CHECK-NEXT: File 3, 5:13 -> 5:14 = #0 (HasCodeBefore = 0)
+// CHECK-NEXT: Expansion,File 4, 6:13 -> 6:16 = #0 (HasCodeBefore = 0, Expanded file = 3)
+
+// CHECK-LABEL: func4:
+// CHECK-NEXT: File 0, 3:12 -> 3:13 = #0 (HasCodeBefore = 0)
+// CHECK-NEXT: Expansion,File 1, 4:12 -> 4:14 = #0 (HasCodeBefore = 0, Expanded file = 0)
+void func4() M1 M11
+// CHECK-NEXT: Expansion,File 2, [[@LINE-1]]:14 -> [[@LINE-1]]:16 = #0 (HasCodeBefore = 0, Expanded file = 1)
+// CHECK-NEXT: Expansion,File 2, [[@LINE-2]]:17 -> [[@LINE-2]]:20 = #0 (HasCodeBefore = 0, Expanded file = 4)
+// CHECK-NEXT: File 3, 5:13 -> 5:14 = #0 (HasCodeBefore = 0)
+// CHECK-NEXT: Expansion,File 4, 6:13 -> 6:16 = #0 (HasCodeBefore = 0, Expanded file = 3)