7 use debug::{DebugCounters, NESTED_INDENT};
8 use graph::{BasicCoverageBlock, BcbBranch, CoverageGraph, TraverseCoverageGraphWithLoops};
9 use spans::CoverageSpan;
11 use rustc_data_structures::graph::WithNumNodes;
12 use rustc_index::bit_set::BitSet;
13 use rustc_middle::mir::coverage::*;
15 /// Manages the counter and expression indexes/IDs to generate `CoverageKind` components for MIR
16 /// `Coverage` statements.
17 pub(super) struct CoverageCounters {
18 function_source_hash: u64,
21 pub debug_counters: DebugCounters,
24 impl CoverageCounters {
25 pub fn new(function_source_hash: u64) -> Self {
28 next_counter_id: CounterValueReference::START.as_u32(),
30 debug_counters: DebugCounters::new(),
34 /// Activate the `DebugCounters` data structures, to provide additional debug formatting
35 /// features when formatting `CoverageKind` (counter) values.
36 pub fn enable_debug(&mut self) {
37 self.debug_counters.enable();
40 /// Makes `CoverageKind` `Counter`s and `Expressions` for the `BasicCoverageBlock`s directly or
41 /// indirectly associated with `CoverageSpans`, and returns additional `Expression`s
42 /// representing intermediate values.
43 pub fn make_bcb_counters(
45 basic_coverage_blocks: &mut CoverageGraph,
46 coverage_spans: &Vec<CoverageSpan>,
47 ) -> Result<Vec<CoverageKind>, Error> {
48 let mut bcb_counters = BcbCounters::new(self, basic_coverage_blocks);
49 bcb_counters.make_bcb_counters(coverage_spans)
52 fn make_counter<F>(&mut self, debug_block_label_fn: F) -> CoverageKind
54 F: Fn() -> Option<String>,
56 let counter = CoverageKind::Counter {
57 function_source_hash: self.function_source_hash,
58 id: self.next_counter(),
60 if self.debug_counters.is_enabled() {
61 self.debug_counters.add_counter(&counter, (debug_block_label_fn)());
66 fn make_expression<F>(
68 lhs: ExpressionOperandId,
70 rhs: ExpressionOperandId,
71 debug_block_label_fn: F,
74 F: Fn() -> Option<String>,
76 let id = self.next_expression();
77 let expression = CoverageKind::Expression { id, lhs, op, rhs };
78 if self.debug_counters.is_enabled() {
79 self.debug_counters.add_counter(&expression, (debug_block_label_fn)());
84 pub fn make_identity_counter(&mut self, counter_operand: ExpressionOperandId) -> CoverageKind {
85 let some_debug_block_label = if self.debug_counters.is_enabled() {
86 self.debug_counters.some_block_label(counter_operand).cloned()
90 self.make_expression(counter_operand, Op::Add, ExpressionOperandId::ZERO, || {
91 some_debug_block_label.clone()
95 /// Counter IDs start from one and go up.
96 fn next_counter(&mut self) -> CounterValueReference {
97 assert!(self.next_counter_id < u32::MAX - self.num_expressions);
98 let next = self.next_counter_id;
99 self.next_counter_id += 1;
100 CounterValueReference::from(next)
103 /// Expression IDs start from u32::MAX and go down because an Expression can reference
104 /// (add or subtract counts) of both Counter regions and Expression regions. The counter
105 /// expression operand IDs must be unique across both types.
106 fn next_expression(&mut self) -> InjectedExpressionId {
107 assert!(self.next_counter_id < u32::MAX - self.num_expressions);
108 let next = u32::MAX - self.num_expressions;
109 self.num_expressions += 1;
110 InjectedExpressionId::from(next)
114 /// Traverse the `CoverageGraph` and add either a `Counter` or `Expression` to every BCB, to be
115 /// injected with `CoverageSpan`s. `Expressions` have no runtime overhead, so if a viable expression
116 /// (adding or subtracting two other counters or expressions) can compute the same result as an
117 /// embedded counter, an `Expression` should be used.
118 struct BcbCounters<'a> {
119 coverage_counters: &'a mut CoverageCounters,
120 basic_coverage_blocks: &'a mut CoverageGraph,
123 impl<'a> BcbCounters<'a> {
125 coverage_counters: &'a mut CoverageCounters,
126 basic_coverage_blocks: &'a mut CoverageGraph,
128 Self { coverage_counters, basic_coverage_blocks }
131 /// If two `BasicCoverageBlock`s branch from another `BasicCoverageBlock`, one of the branches
132 /// can be counted by `Expression` by subtracting the other branch from the branching
133 /// block. Otherwise, the `BasicCoverageBlock` executed the least should have the `Counter`.
134 /// One way to predict which branch executes the least is by considering loops. A loop is exited
135 /// at a branch, so the branch that jumps to a `BasicCoverageBlock` outside the loop is almost
136 /// always executed less than the branch that does not exit the loop.
138 /// Returns any non-code-span expressions created to represent intermediate values (such as to
139 /// add two counters so the result can be subtracted from another counter), or an Error with
140 /// message for subsequent debugging.
141 fn make_bcb_counters(
143 coverage_spans: &[CoverageSpan],
144 ) -> Result<Vec<CoverageKind>, Error> {
145 debug!("make_bcb_counters(): adding a counter or expression to each BasicCoverageBlock");
146 let num_bcbs = self.basic_coverage_blocks.num_nodes();
147 let mut collect_intermediate_expressions = Vec::with_capacity(num_bcbs);
149 let mut bcbs_with_coverage = BitSet::new_empty(num_bcbs);
150 for covspan in coverage_spans {
151 bcbs_with_coverage.insert(covspan.bcb);
154 // Walk the `CoverageGraph`. For each `BasicCoverageBlock` node with an associated
155 // `CoverageSpan`, add a counter. If the `BasicCoverageBlock` branches, add a counter or
156 // expression to each branch `BasicCoverageBlock` (if the branch BCB has only one incoming
157 // edge) or edge from the branching BCB to the branch BCB (if the branch BCB has multiple
160 // The `TraverseCoverageGraphWithLoops` traversal ensures that, when a loop is encountered,
161 // all `BasicCoverageBlock` nodes in the loop are visited before visiting any node outside
162 // the loop. The `traversal` state includes a `context_stack`, providing a way to know if
163 // the current BCB is in one or more nested loops or not.
164 let mut traversal = TraverseCoverageGraphWithLoops::new(&self.basic_coverage_blocks);
165 while let Some(bcb) = traversal.next(self.basic_coverage_blocks) {
166 if bcbs_with_coverage.contains(bcb) {
167 debug!("{:?} has at least one `CoverageSpan`. Get or make its counter", bcb);
168 let branching_counter_operand =
169 self.get_or_make_counter_operand(bcb, &mut collect_intermediate_expressions)?;
171 if self.bcb_needs_branch_counters(bcb) {
172 self.make_branch_counters(
175 branching_counter_operand,
176 &mut collect_intermediate_expressions,
181 "{:?} does not have any `CoverageSpan`s. A counter will only be added if \
182 and when a covered BCB has an expression dependency.",
188 if traversal.is_complete() {
189 Ok(collect_intermediate_expressions)
191 Error::from_string(format!(
192 "`TraverseCoverageGraphWithLoops` missed some `BasicCoverageBlock`s: {:?}",
193 traversal.unvisited(),
198 fn make_branch_counters(
200 traversal: &mut TraverseCoverageGraphWithLoops,
201 branching_bcb: BasicCoverageBlock,
202 branching_counter_operand: ExpressionOperandId,
203 collect_intermediate_expressions: &mut Vec<CoverageKind>,
204 ) -> Result<(), Error> {
205 let branches = self.bcb_branches(branching_bcb);
207 "{:?} has some branch(es) without counters:\n {}",
212 format!("{:?}: {:?}", branch, branch.counter(&self.basic_coverage_blocks))
218 // Use the `traversal` state to decide if a subset of the branches exit a loop, making it
219 // likely that branch is executed less than branches that do not exit the same loop. In this
220 // case, any branch that does not exit the loop (and has not already been assigned a
221 // counter) should be counted by expression, if possible. (If a preferred expression branch
222 // is not selected based on the loop context, select any branch without an existing
224 let expression_branch = self.choose_preferred_expression_branch(traversal, &branches);
226 // Assign a Counter or Expression to each branch, plus additional `Expression`s, as needed,
227 // to sum up intermediate results.
228 let mut some_sumup_counter_operand = None;
229 for branch in branches {
230 // Skip the selected `expression_branch`, if any. It's expression will be assigned after
232 if branch != expression_branch {
233 let branch_counter_operand = if branch.is_only_path_to_target() {
235 " {:?} has only one incoming edge (from {:?}), so adding a \
237 branch, branching_bcb
239 self.get_or_make_counter_operand(
241 collect_intermediate_expressions,
244 debug!(" {:?} has multiple incoming edges, so adding an edge counter", branch);
245 self.get_or_make_edge_counter_operand(
248 collect_intermediate_expressions,
251 if let Some(sumup_counter_operand) =
252 some_sumup_counter_operand.replace(branch_counter_operand)
254 let intermediate_expression = self.coverage_counters.make_expression(
255 branch_counter_operand,
257 sumup_counter_operand,
261 " [new intermediate expression: {}]",
262 self.format_counter(&intermediate_expression)
264 let intermediate_expression_operand = intermediate_expression.as_operand_id();
265 collect_intermediate_expressions.push(intermediate_expression);
266 some_sumup_counter_operand.replace(intermediate_expression_operand);
271 // Assign the final expression to the `expression_branch` by subtracting the total of all
272 // other branches from the counter of the branching BCB.
273 let sumup_counter_operand =
274 some_sumup_counter_operand.expect("sumup_counter_operand should have a value");
276 "Making an expression for the selected expression_branch: {:?} \
277 (expression_branch predecessors: {:?})",
279 self.bcb_predecessors(expression_branch.target_bcb),
281 let expression = self.coverage_counters.make_expression(
282 branching_counter_operand,
284 sumup_counter_operand,
285 || Some(format!("{:?}", expression_branch)),
287 debug!("{:?} gets an expression: {}", expression_branch, self.format_counter(&expression));
288 let bcb = expression_branch.target_bcb;
289 if expression_branch.is_only_path_to_target() {
290 self.basic_coverage_blocks[bcb].set_counter(expression)?;
292 self.basic_coverage_blocks[bcb].set_edge_counter_from(branching_bcb, expression)?;
297 fn get_or_make_counter_operand(
299 bcb: BasicCoverageBlock,
300 collect_intermediate_expressions: &mut Vec<CoverageKind>,
301 ) -> Result<ExpressionOperandId, Error> {
302 self.recursive_get_or_make_counter_operand(bcb, collect_intermediate_expressions, 1)
305 fn recursive_get_or_make_counter_operand(
307 bcb: BasicCoverageBlock,
308 collect_intermediate_expressions: &mut Vec<CoverageKind>,
309 debug_indent_level: usize,
310 ) -> Result<ExpressionOperandId, Error> {
311 // If the BCB already has a counter, return it.
312 if let Some(counter_kind) = self.basic_coverage_blocks[bcb].counter() {
314 "{}{:?} already has a counter: {}",
315 NESTED_INDENT.repeat(debug_indent_level),
317 self.format_counter(counter_kind),
319 return Ok(counter_kind.as_operand_id());
322 // A BCB with only one incoming edge gets a simple `Counter` (via `make_counter()`).
323 // Also, a BCB that loops back to itself gets a simple `Counter`. This may indicate the
324 // program results in a tight infinite loop, but it should still compile.
325 let one_path_to_target = self.bcb_has_one_path_to_target(bcb);
326 if one_path_to_target || self.bcb_predecessors(bcb).contains(&bcb) {
327 let counter_kind = self.coverage_counters.make_counter(|| Some(format!("{:?}", bcb)));
328 if one_path_to_target {
330 "{}{:?} gets a new counter: {}",
331 NESTED_INDENT.repeat(debug_indent_level),
333 self.format_counter(&counter_kind),
337 "{}{:?} has itself as its own predecessor. It can't be part of its own \
338 Expression sum, so it will get its own new counter: {}. (Note, the compiled \
339 code will generate an infinite loop.)",
340 NESTED_INDENT.repeat(debug_indent_level),
342 self.format_counter(&counter_kind),
345 return self.basic_coverage_blocks[bcb].set_counter(counter_kind);
348 // A BCB with multiple incoming edges can compute its count by `Expression`, summing up the
349 // counters and/or expressions of its incoming edges. This will recursively get or create
350 // counters for those incoming edges first, then call `make_expression()` to sum them up,
351 // with additional intermediate expressions as needed.
352 let mut predecessors = self.bcb_predecessors(bcb).clone().into_iter();
354 "{}{:?} has multiple incoming edges and will get an expression that sums them up...",
355 NESTED_INDENT.repeat(debug_indent_level),
358 let first_edge_counter_operand = self.recursive_get_or_make_edge_counter_operand(
359 predecessors.next().unwrap(),
361 collect_intermediate_expressions,
362 debug_indent_level + 1,
364 let mut some_sumup_edge_counter_operand = None;
365 for predecessor in predecessors {
366 let edge_counter_operand = self.recursive_get_or_make_edge_counter_operand(
369 collect_intermediate_expressions,
370 debug_indent_level + 1,
372 if let Some(sumup_edge_counter_operand) =
373 some_sumup_edge_counter_operand.replace(edge_counter_operand)
375 let intermediate_expression = self.coverage_counters.make_expression(
376 sumup_edge_counter_operand,
378 edge_counter_operand,
382 "{}new intermediate expression: {}",
383 NESTED_INDENT.repeat(debug_indent_level),
384 self.format_counter(&intermediate_expression)
386 let intermediate_expression_operand = intermediate_expression.as_operand_id();
387 collect_intermediate_expressions.push(intermediate_expression);
388 some_sumup_edge_counter_operand.replace(intermediate_expression_operand);
391 let counter_kind = self.coverage_counters.make_expression(
392 first_edge_counter_operand,
394 some_sumup_edge_counter_operand.unwrap(),
395 || Some(format!("{:?}", bcb)),
398 "{}{:?} gets a new counter (sum of predecessor counters): {}",
399 NESTED_INDENT.repeat(debug_indent_level),
401 self.format_counter(&counter_kind)
403 self.basic_coverage_blocks[bcb].set_counter(counter_kind)
406 fn get_or_make_edge_counter_operand(
408 from_bcb: BasicCoverageBlock,
409 to_bcb: BasicCoverageBlock,
410 collect_intermediate_expressions: &mut Vec<CoverageKind>,
411 ) -> Result<ExpressionOperandId, Error> {
412 self.recursive_get_or_make_edge_counter_operand(
415 collect_intermediate_expressions,
420 fn recursive_get_or_make_edge_counter_operand(
422 from_bcb: BasicCoverageBlock,
423 to_bcb: BasicCoverageBlock,
424 collect_intermediate_expressions: &mut Vec<CoverageKind>,
425 debug_indent_level: usize,
426 ) -> Result<ExpressionOperandId, Error> {
427 // If the source BCB has only one successor (assumed to be the given target), an edge
428 // counter is unnecessary. Just get or make a counter for the source BCB.
429 let successors = self.bcb_successors(from_bcb).iter();
430 if successors.len() == 1 {
431 return self.recursive_get_or_make_counter_operand(
433 collect_intermediate_expressions,
434 debug_indent_level + 1,
438 // If the edge already has a counter, return it.
439 if let Some(counter_kind) = self.basic_coverage_blocks[to_bcb].edge_counter_from(from_bcb) {
441 "{}Edge {:?}->{:?} already has a counter: {}",
442 NESTED_INDENT.repeat(debug_indent_level),
445 self.format_counter(counter_kind)
447 return Ok(counter_kind.as_operand_id());
450 // Make a new counter to count this edge.
452 self.coverage_counters.make_counter(|| Some(format!("{:?}->{:?}", from_bcb, to_bcb)));
454 "{}Edge {:?}->{:?} gets a new counter: {}",
455 NESTED_INDENT.repeat(debug_indent_level),
458 self.format_counter(&counter_kind)
460 self.basic_coverage_blocks[to_bcb].set_edge_counter_from(from_bcb, counter_kind)
463 /// Select a branch for the expression, either the recommended `reloop_branch`, or if none was
464 /// found, select any branch.
465 fn choose_preferred_expression_branch(
467 traversal: &TraverseCoverageGraphWithLoops,
468 branches: &[BcbBranch],
470 let branch_needs_a_counter =
471 |branch: &BcbBranch| branch.counter(&self.basic_coverage_blocks).is_none();
473 let some_reloop_branch = self.find_some_reloop_branch(traversal, &branches);
474 if let Some(reloop_branch_without_counter) =
475 some_reloop_branch.filter(branch_needs_a_counter)
478 "Selecting reloop_branch={:?} that still needs a counter, to get the \
480 reloop_branch_without_counter
482 reloop_branch_without_counter
484 let &branch_without_counter = branches
486 .find(|&&branch| branch.counter(&self.basic_coverage_blocks).is_none())
488 "needs_branch_counters was `true` so there should be at least one \
492 "Selecting any branch={:?} that still needs a counter, to get the \
493 `Expression` because there was no `reloop_branch`, or it already had a \
495 branch_without_counter
497 branch_without_counter
501 /// At most, one of the branches (or its edge, from the branching_bcb, if the branch has
502 /// multiple incoming edges) can have a counter computed by expression.
504 /// If at least one of the branches leads outside of a loop (`found_loop_exit` is
505 /// true), and at least one other branch does not exit the loop (the first of which
506 /// is captured in `some_reloop_branch`), it's likely any reloop branch will be
507 /// executed far more often than loop exit branch, making the reloop branch a better
508 /// candidate for an expression.
509 fn find_some_reloop_branch(
511 traversal: &TraverseCoverageGraphWithLoops,
512 branches: &[BcbBranch],
513 ) -> Option<BcbBranch> {
514 let branch_needs_a_counter =
515 |branch: &BcbBranch| branch.counter(&self.basic_coverage_blocks).is_none();
517 let mut some_reloop_branch: Option<BcbBranch> = None;
518 for context in traversal.context_stack.iter().rev() {
519 if let Some((backedge_from_bcbs, _)) = &context.loop_backedges {
520 let mut found_loop_exit = false;
521 for &branch in branches.iter() {
522 if backedge_from_bcbs.iter().any(|&backedge_from_bcb| {
523 self.bcb_is_dominated_by(backedge_from_bcb, branch.target_bcb)
525 if let Some(reloop_branch) = some_reloop_branch {
526 if reloop_branch.counter(&self.basic_coverage_blocks).is_none() {
527 // we already found a candidate reloop_branch that still
532 // The path from branch leads back to the top of the loop. Set this
533 // branch as the `reloop_branch`. If this branch already has a
534 // counter, and we find another reloop branch that doesn't have a
535 // counter yet, that branch will be selected as the `reloop_branch`
537 some_reloop_branch = Some(branch);
539 // The path from branch leads outside this loop
540 found_loop_exit = true;
543 && some_reloop_branch.filter(branch_needs_a_counter).is_some()
545 // Found both a branch that exits the loop and a branch that returns
546 // to the top of the loop (`reloop_branch`), and the `reloop_branch`
547 // doesn't already have a counter.
551 if !found_loop_exit {
553 "No branches exit the loop, so any branch without an existing \
554 counter can have the `Expression`."
558 if some_reloop_branch.is_some() {
560 "Found a branch that exits the loop and a branch the loops back to \
561 the top of the loop (`reloop_branch`). The `reloop_branch` will \
562 get the `Expression`, as long as it still needs a counter."
566 // else all branches exited this loop context, so run the same checks with
574 fn bcb_predecessors(&self, bcb: BasicCoverageBlock) -> &Vec<BasicCoverageBlock> {
575 &self.basic_coverage_blocks.predecessors[bcb]
579 fn bcb_successors(&self, bcb: BasicCoverageBlock) -> &Vec<BasicCoverageBlock> {
580 &self.basic_coverage_blocks.successors[bcb]
584 fn bcb_branches(&self, from_bcb: BasicCoverageBlock) -> Vec<BcbBranch> {
585 self.bcb_successors(from_bcb)
587 .map(|&to_bcb| BcbBranch::from_to(from_bcb, to_bcb, &self.basic_coverage_blocks))
591 fn bcb_needs_branch_counters(&self, bcb: BasicCoverageBlock) -> bool {
592 let branch_needs_a_counter =
593 |branch: &BcbBranch| branch.counter(&self.basic_coverage_blocks).is_none();
594 let branches = self.bcb_branches(bcb);
595 branches.len() > 1 && branches.iter().any(branch_needs_a_counter)
598 /// Returns true if the BasicCoverageBlock has zero or one incoming edge. (If zero, it should be
599 /// the entry point for the function.)
601 fn bcb_has_one_path_to_target(&self, bcb: BasicCoverageBlock) -> bool {
602 self.bcb_predecessors(bcb).len() <= 1
606 fn bcb_is_dominated_by(&self, node: BasicCoverageBlock, dom: BasicCoverageBlock) -> bool {
607 self.basic_coverage_blocks.is_dominated_by(node, dom)
611 fn format_counter(&self, counter_kind: &CoverageKind) -> String {
612 self.coverage_counters.debug_counters.format_counter(counter_kind)