Rollup merge of #133849 - Zalathar:replay, r=oli-obk

coverage: Use a separate counter type and simplification step during counter creation

When instrumenting a function's MIR for coverage, there is a point where we need to decide, for each node in the control-flow graph, whether its execution count will be tracked by a physical counter, or by an expression that combines physical counters from other parts of the graph.

Currently the code for doing that is heavily tied to the final form of the LLVM coverage mapping format, and performs some important simplification steps on-the-fly. These factors make the code extremely difficult to modify without breaking or massively worsening the resulting coverage-instrumentation metadata.

---

This PR aims to improve that situation somewhat by adding an extra intermediate representation between the code that chooses how each node will be counted, and the code that converts those decisions into actual tables of physical counters and trees of counter expressions.

As part of doing that, some of the simplifications that are currently performed during the main counter creation step have been pulled out into a separate step.

In most cases the resulting coverage metadata is equivalent, slightly better, or slightly worse. The biggest outlier is `counters.rs`, where the coverage metadata ends up about 10% larger. This seems to be the result of the new approach having less subexpression sharing (because it relies on flatten-sort-cancel), and therefore being less effective at taking advantage of MIR optimizations to replace counters for unused control-flow with zeroes. I think the modest downside is acceptable in light of the future possibilities opened up by this decoupling.

1 files changed, 85 insertions, 85 deletions

diff --git a/tests/coverage/branch/lazy-boolean.cov-map b/tests/coverage/branch/lazy-boolean.cov-map
index c2b6a5b8df2..decb847f60e 100644
--- a/tests/coverage/branch/lazy-boolean.cov-map
+++ b/tests/coverage/branch/lazy-boolean.cov-map
@@ -34,39 +34,49 @@ Number of file 0 mappings: 6
 Highest counter ID seen: c2
 
 Function name: lazy_boolean::chain
-Raw bytes (149): 0x[01, 01, 13, 11, 07, 0b, 16, 15, 1a, 09, 0d, 05, 09, 05, 09, 09, 0d, 47, 25, 4b, 21, 19, 1d, 03, 19, 03, 19, 3e, 1d, 03, 19, 3e, 1d, 03, 19, 47, 25, 4b, 21, 19, 1d, 13, 01, 24, 01, 01, 10, 03, 04, 09, 00, 0a, 05, 00, 0d, 00, 12, 20, 09, 16, 00, 0d, 00, 12, 09, 00, 16, 00, 1b, 20, 0d, 1a, 00, 16, 00, 1b, 0d, 00, 1f, 00, 24, 20, 11, 15, 00, 1f, 00, 24, 11, 00, 28, 00, 2d, 03, 01, 05, 00, 11, 43, 03, 09, 00, 0a, 03, 00, 0d, 00, 12, 20, 19, 3e, 00, 0d, 00, 12, 3e, 00, 16, 00, 1b, 20, 1d, 3a, 00, 16, 00, 1b, 3a, 00, 1f, 00, 24, 20, 21, 25, 00, 1f, 00, 24, 25, 00, 28, 00, 2d, 43, 01, 05, 01, 02]
+Raw bytes (169): 0x[01, 01, 1d, 5b, 0d, 5f, 15, 05, 11, 05, 09, 09, 0d, 6f, 25, 73, 21, 19, 1d, 5b, 67, 5f, 15, 05, 11, 0d, 19, 5b, 67, 5f, 15, 05, 11, 0d, 19, 5b, 63, 5f, 15, 05, 11, 67, 1d, 0d, 19, 5b, 63, 5f, 15, 05, 11, 67, 1d, 0d, 19, 6f, 25, 73, 21, 19, 1d, 13, 01, 24, 01, 01, 10, 02, 04, 09, 00, 0a, 05, 00, 0d, 00, 12, 20, 09, 0e, 00, 0d, 00, 12, 09, 00, 16, 00, 1b, 20, 0d, 12, 00, 16, 00, 1b, 0d, 00, 1f, 00, 24, 20, 11, 15, 00, 1f, 00, 24, 11, 00, 28, 00, 2d, 02, 01, 05, 00, 11, 6b, 03, 09, 00, 0a, 02, 00, 0d, 00, 12, 20, 19, 32, 00, 0d, 00, 12, 32, 00, 16, 00, 1b, 20, 1d, 56, 00, 16, 00, 1b, 56, 00, 1f, 00, 24, 20, 21, 25, 00, 1f, 00, 24, 25, 00, 28, 00, 2d, 6b, 01, 05, 01, 02]
 Number of files: 1
 - file 0 => global file 1
-Number of expressions: 19
-- expression 0 operands: lhs = Counter(4), rhs = Expression(1, Add)
-- expression 1 operands: lhs = Expression(2, Add), rhs = Expression(5, Sub)
-- expression 2 operands: lhs = Counter(5), rhs = Expression(6, Sub)
-- expression 3 operands: lhs = Counter(2), rhs = Counter(3)
-- expression 4 operands: lhs = Counter(1), rhs = Counter(2)
-- expression 5 operands: lhs = Counter(1), rhs = Counter(2)
-- expression 6 operands: lhs = Counter(2), rhs = Counter(3)
-- expression 7 operands: lhs = Expression(17, Add), rhs = Counter(9)
-- expression 8 operands: lhs = Expression(18, Add), rhs = Counter(8)
-- expression 9 operands: lhs = Counter(6), rhs = Counter(7)
-- expression 10 operands: lhs = Expression(0, Add), rhs = Counter(6)
-- expression 11 operands: lhs = Expression(0, Add), rhs = Counter(6)
-- expression 12 operands: lhs = Expression(15, Sub), rhs = Counter(7)
-- expression 13 operands: lhs = Expression(0, Add), rhs = Counter(6)
-- expression 14 operands: lhs = Expression(15, Sub), rhs = Counter(7)
-- expression 15 operands: lhs = Expression(0, Add), rhs = Counter(6)
-- expression 16 operands: lhs = Expression(17, Add), rhs = Counter(9)
-- expression 17 operands: lhs = Expression(18, Add), rhs = Counter(8)
-- expression 18 operands: lhs = Counter(6), rhs = Counter(7)
+Number of expressions: 29
+- expression 0 operands: lhs = Expression(22, Add), rhs = Counter(3)
+- expression 1 operands: lhs = Expression(23, Add), rhs = Counter(5)
+- expression 2 operands: lhs = Counter(1), rhs = Counter(4)
+- expression 3 operands: lhs = Counter(1), rhs = Counter(2)
+- expression 4 operands: lhs = Counter(2), rhs = Counter(3)
+- expression 5 operands: lhs = Expression(27, Add), rhs = Counter(9)
+- expression 6 operands: lhs = Expression(28, Add), rhs = Counter(8)
+- expression 7 operands: lhs = Counter(6), rhs = Counter(7)
+- expression 8 operands: lhs = Expression(22, Add), rhs = Expression(25, Add)
+- expression 9 operands: lhs = Expression(23, Add), rhs = Counter(5)
+- expression 10 operands: lhs = Counter(1), rhs = Counter(4)
+- expression 11 operands: lhs = Counter(3), rhs = Counter(6)
+- expression 12 operands: lhs = Expression(22, Add), rhs = Expression(25, Add)
+- expression 13 operands: lhs = Expression(23, Add), rhs = Counter(5)
+- expression 14 operands: lhs = Counter(1), rhs = Counter(4)
+- expression 15 operands: lhs = Counter(3), rhs = Counter(6)
+- expression 16 operands: lhs = Expression(22, Add), rhs = Expression(24, Add)
+- expression 17 operands: lhs = Expression(23, Add), rhs = Counter(5)
+- expression 18 operands: lhs = Counter(1), rhs = Counter(4)
+- expression 19 operands: lhs = Expression(25, Add), rhs = Counter(7)
+- expression 20 operands: lhs = Counter(3), rhs = Counter(6)
+- expression 21 operands: lhs = Expression(22, Add), rhs = Expression(24, Add)
+- expression 22 operands: lhs = Expression(23, Add), rhs = Counter(5)
+- expression 23 operands: lhs = Counter(1), rhs = Counter(4)
+- expression 24 operands: lhs = Expression(25, Add), rhs = Counter(7)
+- expression 25 operands: lhs = Counter(3), rhs = Counter(6)
+- expression 26 operands: lhs = Expression(27, Add), rhs = Counter(9)
+- expression 27 operands: lhs = Expression(28, Add), rhs = Counter(8)
+- expression 28 operands: lhs = Counter(6), rhs = Counter(7)
 Number of file 0 mappings: 19
 - Code(Counter(0)) at (prev + 36, 1) to (start + 1, 16)
-- Code(Expression(0, Add)) at (prev + 4, 9) to (start + 0, 10)
-    = (c4 + ((c5 + (c2 - c3)) + (c1 - c2)))
+- Code(Expression(0, Sub)) at (prev + 4, 9) to (start + 0, 10)
+    = (((c1 + c4) + c5) - c3)
 - Code(Counter(1)) at (prev + 0, 13) to (start + 0, 18)
-- Branch { true: Counter(2), false: Expression(5, Sub) } at (prev + 0, 13) to (start + 0, 18)
+- Branch { true: Counter(2), false: Expression(3, Sub) } at (prev + 0, 13) to (start + 0, 18)
     true  = c2
     false = (c1 - c2)
 - Code(Counter(2)) at (prev + 0, 22) to (start + 0, 27)
-- Branch { true: Counter(3), false: Expression(6, Sub) } at (prev + 0, 22) to (start + 0, 27)
+- Branch { true: Counter(3), false: Expression(4, Sub) } at (prev + 0, 22) to (start + 0, 27)
     true  = c3
     false = (c2 - c3)
 - Code(Counter(3)) at (prev + 0, 31) to (start + 0, 36)
@@ -74,97 +84,87 @@ Number of file 0 mappings: 19
     true  = c4
     false = c5
 - Code(Counter(4)) at (prev + 0, 40) to (start + 0, 45)
-- Code(Expression(0, Add)) at (prev + 1, 5) to (start + 0, 17)
-    = (c4 + ((c5 + (c2 - c3)) + (c1 - c2)))
-- Code(Expression(16, Add)) at (prev + 3, 9) to (start + 0, 10)
+- Code(Expression(0, Sub)) at (prev + 1, 5) to (start + 0, 17)
+    = (((c1 + c4) + c5) - c3)
+- Code(Expression(26, Add)) at (prev + 3, 9) to (start + 0, 10)
     = (((c6 + c7) + c8) + c9)
-- Code(Expression(0, Add)) at (prev + 0, 13) to (start + 0, 18)
-    = (c4 + ((c5 + (c2 - c3)) + (c1 - c2)))
-- Branch { true: Counter(6), false: Expression(15, Sub) } at (prev + 0, 13) to (start + 0, 18)
+- Code(Expression(0, Sub)) at (prev + 0, 13) to (start + 0, 18)
+    = (((c1 + c4) + c5) - c3)
+- Branch { true: Counter(6), false: Expression(12, Sub) } at (prev + 0, 13) to (start + 0, 18)
     true  = c6
-    false = ((c4 + ((c5 + (c2 - c3)) + (c1 - c2))) - c6)
-- Code(Expression(15, Sub)) at (prev + 0, 22) to (start + 0, 27)
-    = ((c4 + ((c5 + (c2 - c3)) + (c1 - c2))) - c6)
-- Branch { true: Counter(7), false: Expression(14, Sub) } at (prev + 0, 22) to (start + 0, 27)
+    false = (((c1 + c4) + c5) - (c3 + c6))
+- Code(Expression(12, Sub)) at (prev + 0, 22) to (start + 0, 27)
+    = (((c1 + c4) + c5) - (c3 + c6))
+- Branch { true: Counter(7), false: Expression(21, Sub) } at (prev + 0, 22) to (start + 0, 27)
     true  = c7
-    false = (((c4 + ((c5 + (c2 - c3)) + (c1 - c2))) - c6) - c7)
-- Code(Expression(14, Sub)) at (prev + 0, 31) to (start + 0, 36)
-    = (((c4 + ((c5 + (c2 - c3)) + (c1 - c2))) - c6) - c7)
+    false = (((c1 + c4) + c5) - ((c3 + c6) + c7))
+- Code(Expression(21, Sub)) at (prev + 0, 31) to (start + 0, 36)
+    = (((c1 + c4) + c5) - ((c3 + c6) + c7))
 - Branch { true: Counter(8), false: Counter(9) } at (prev + 0, 31) to (start + 0, 36)
     true  = c8
     false = c9
 - Code(Counter(9)) at (prev + 0, 40) to (start + 0, 45)
-- Code(Expression(16, Add)) at (prev + 1, 5) to (start + 1, 2)
+- Code(Expression(26, Add)) at (prev + 1, 5) to (start + 1, 2)
     = (((c6 + c7) + c8) + c9)
 Highest counter ID seen: c9
 
 Function name: lazy_boolean::nested_mixed
-Raw bytes (155): 0x[01, 01, 16, 33, 1a, 09, 0d, 1e, 0d, 05, 09, 05, 09, 05, 09, 1e, 0d, 05, 09, 09, 0d, 33, 11, 09, 0d, 33, 11, 09, 0d, 19, 57, 1d, 21, 03, 15, 15, 19, 4a, 4e, 15, 19, 03, 15, 19, 57, 1d, 21, 13, 01, 31, 01, 01, 10, 03, 04, 09, 00, 0a, 05, 00, 0e, 00, 13, 20, 09, 1e, 00, 0e, 00, 13, 1e, 00, 17, 00, 1d, 20, 0d, 1a, 00, 17, 00, 1d, 33, 00, 23, 00, 28, 20, 11, 2e, 00, 23, 00, 28, 2e, 00, 2c, 00, 33, 03, 01, 05, 00, 11, 53, 03, 09, 00, 0a, 03, 00, 0e, 00, 13, 20, 15, 4e, 00, 0e, 00, 13, 15, 00, 17, 00, 1c, 20, 19, 4a, 00, 17, 00, 1c, 47, 00, 22, 00, 28, 20, 1d, 21, 00, 22, 00, 28, 1d, 00, 2c, 00, 33, 53, 01, 05, 01, 02]
+Raw bytes (141): 0x[01, 01, 0f, 05, 09, 05, 1f, 09, 0d, 09, 0d, 1f, 11, 09, 0d, 1f, 11, 09, 0d, 3b, 21, 19, 1d, 05, 15, 15, 19, 05, 19, 3b, 21, 19, 1d, 13, 01, 31, 01, 01, 10, 05, 04, 09, 00, 0a, 05, 00, 0e, 00, 13, 20, 09, 02, 00, 0e, 00, 13, 02, 00, 17, 00, 1d, 20, 0d, 06, 00, 17, 00, 1d, 1f, 00, 23, 00, 28, 20, 11, 1a, 00, 23, 00, 28, 1a, 00, 2c, 00, 33, 05, 01, 05, 00, 11, 37, 03, 09, 00, 0a, 05, 00, 0e, 00, 13, 20, 15, 2a, 00, 0e, 00, 13, 15, 00, 17, 00, 1c, 20, 19, 2e, 00, 17, 00, 1c, 32, 00, 22, 00, 28, 20, 1d, 21, 00, 22, 00, 28, 1d, 00, 2c, 00, 33, 37, 01, 05, 01, 02]
 Number of files: 1
 - file 0 => global file 1
-Number of expressions: 22
-- expression 0 operands: lhs = Expression(12, Add), rhs = Expression(6, Sub)
-- expression 1 operands: lhs = Counter(2), rhs = Counter(3)
-- expression 2 operands: lhs = Expression(7, Sub), rhs = Counter(3)
-- expression 3 operands: lhs = Counter(1), rhs = Counter(2)
-- expression 4 operands: lhs = Counter(1), rhs = Counter(2)
-- expression 5 operands: lhs = Counter(1), rhs = Counter(2)
-- expression 6 operands: lhs = Expression(7, Sub), rhs = Counter(3)
-- expression 7 operands: lhs = Counter(1), rhs = Counter(2)
-- expression 8 operands: lhs = Counter(2), rhs = Counter(3)
-- expression 9 operands: lhs = Expression(12, Add), rhs = Counter(4)
-- expression 10 operands: lhs = Counter(2), rhs = Counter(3)
-- expression 11 operands: lhs = Expression(12, Add), rhs = Counter(4)
-- expression 12 operands: lhs = Counter(2), rhs = Counter(3)
-- expression 13 operands: lhs = Counter(6), rhs = Expression(21, Add)
-- expression 14 operands: lhs = Counter(7), rhs = Counter(8)
-- expression 15 operands: lhs = Expression(0, Add), rhs = Counter(5)
-- expression 16 operands: lhs = Counter(5), rhs = Counter(6)
-- expression 17 operands: lhs = Expression(18, Sub), rhs = Expression(19, Sub)
-- expression 18 operands: lhs = Counter(5), rhs = Counter(6)
-- expression 19 operands: lhs = Expression(0, Add), rhs = Counter(5)
-- expression 20 operands: lhs = Counter(6), rhs = Expression(21, Add)
-- expression 21 operands: lhs = Counter(7), rhs = Counter(8)
+Number of expressions: 15
+- expression 0 operands: lhs = Counter(1), rhs = Counter(2)
+- expression 1 operands: lhs = Counter(1), rhs = Expression(7, Add)
+- expression 2 operands: lhs = Counter(2), rhs = Counter(3)
+- expression 3 operands: lhs = Counter(2), rhs = Counter(3)
+- expression 4 operands: lhs = Expression(7, Add), rhs = Counter(4)
+- expression 5 operands: lhs = Counter(2), rhs = Counter(3)
+- expression 6 operands: lhs = Expression(7, Add), rhs = Counter(4)
+- expression 7 operands: lhs = Counter(2), rhs = Counter(3)
+- expression 8 operands: lhs = Expression(14, Add), rhs = Counter(8)
+- expression 9 operands: lhs = Counter(6), rhs = Counter(7)
+- expression 10 operands: lhs = Counter(1), rhs = Counter(5)
+- expression 11 operands: lhs = Counter(5), rhs = Counter(6)
+- expression 12 operands: lhs = Counter(1), rhs = Counter(6)
+- expression 13 operands: lhs = Expression(14, Add), rhs = Counter(8)
+- expression 14 operands: lhs = Counter(6), rhs = Counter(7)
 Number of file 0 mappings: 19
 - Code(Counter(0)) at (prev + 49, 1) to (start + 1, 16)
-- Code(Expression(0, Add)) at (prev + 4, 9) to (start + 0, 10)
-    = ((c2 + c3) + ((c1 - c2) - c3))
+- Code(Counter(1)) at (prev + 4, 9) to (start + 0, 10)
 - Code(Counter(1)) at (prev + 0, 14) to (start + 0, 19)
-- Branch { true: Counter(2), false: Expression(7, Sub) } at (prev + 0, 14) to (start + 0, 19)
+- Branch { true: Counter(2), false: Expression(0, Sub) } at (prev + 0, 14) to (start + 0, 19)
     true  = c2
     false = (c1 - c2)
-- Code(Expression(7, Sub)) at (prev + 0, 23) to (start + 0, 29)
+- Code(Expression(0, Sub)) at (prev + 0, 23) to (start + 0, 29)
     = (c1 - c2)
-- Branch { true: Counter(3), false: Expression(6, Sub) } at (prev + 0, 23) to (start + 0, 29)
+- Branch { true: Counter(3), false: Expression(1, Sub) } at (prev + 0, 23) to (start + 0, 29)
     true  = c3
-    false = ((c1 - c2) - c3)
-- Code(Expression(12, Add)) at (prev + 0, 35) to (start + 0, 40)
+    false = (c1 - (c2 + c3))
+- Code(Expression(7, Add)) at (prev + 0, 35) to (start + 0, 40)
     = (c2 + c3)
-- Branch { true: Counter(4), false: Expression(11, Sub) } at (prev + 0, 35) to (start + 0, 40)
+- Branch { true: Counter(4), false: Expression(6, Sub) } at (prev + 0, 35) to (start + 0, 40)
     true  = c4
     false = ((c2 + c3) - c4)
-- Code(Expression(11, Sub)) at (prev + 0, 44) to (start + 0, 51)
+- Code(Expression(6, Sub)) at (prev + 0, 44) to (start + 0, 51)
     = ((c2 + c3) - c4)
-- Code(Expression(0, Add)) at (prev + 1, 5) to (start + 0, 17)
-    = ((c2 + c3) + ((c1 - c2) - c3))
-- Code(Expression(20, Add)) at (prev + 3, 9) to (start + 0, 10)
-    = (c6 + (c7 + c8))
-- Code(Expression(0, Add)) at (prev + 0, 14) to (start + 0, 19)
-    = ((c2 + c3) + ((c1 - c2) - c3))
-- Branch { true: Counter(5), false: Expression(19, Sub) } at (prev + 0, 14) to (start + 0, 19)
+- Code(Counter(1)) at (prev + 1, 5) to (start + 0, 17)
+- Code(Expression(13, Add)) at (prev + 3, 9) to (start + 0, 10)
+    = ((c6 + c7) + c8)
+- Code(Counter(1)) at (prev + 0, 14) to (start + 0, 19)
+- Branch { true: Counter(5), false: Expression(10, Sub) } at (prev + 0, 14) to (start + 0, 19)
     true  = c5
-    false = (((c2 + c3) + ((c1 - c2) - c3)) - c5)
+    false = (c1 - c5)
 - Code(Counter(5)) at (prev + 0, 23) to (start + 0, 28)
-- Branch { true: Counter(6), false: Expression(18, Sub) } at (prev + 0, 23) to (start + 0, 28)
+- Branch { true: Counter(6), false: Expression(11, Sub) } at (prev + 0, 23) to (start + 0, 28)
     true  = c6
     false = (c5 - c6)
-- Code(Expression(17, Add)) at (prev + 0, 34) to (start + 0, 40)
-    = ((c5 - c6) + (((c2 + c3) + ((c1 - c2) - c3)) - c5))
+- Code(Expression(12, Sub)) at (prev + 0, 34) to (start + 0, 40)
+    = (c1 - c6)
 - Branch { true: Counter(7), false: Counter(8) } at (prev + 0, 34) to (start + 0, 40)
     true  = c7
     false = c8
 - Code(Counter(7)) at (prev + 0, 44) to (start + 0, 51)
-- Code(Expression(20, Add)) at (prev + 1, 5) to (start + 1, 2)
-    = (c6 + (c7 + c8))
+- Code(Expression(13, Add)) at (prev + 1, 5) to (start + 1, 2)
+    = ((c6 + c7) + c8)
 Highest counter ID seen: c8