Statement/Branch coverage for all tests by dobios · Pull Request #263 · chipsalliance/treadle

dobios · 2020-11-03T14:48:20Z

Adding Statement/Branch Coverage to Treadle

The idea was to modify the treadle tester so that it would make certain modifications to the given FIRRTL source code in order to track the line coverage. Once that was done, we needed to check these additional ports and compile the results in a line coverage report. The modifications related to this work can be found here. Note that coverage can be enabled using the EnableCoverage annotation.

Modifying the input FIRRTL code

The first thing that needed to be done was to add ports to the given design. This is done depending on the amount of multiplexers that are in the design, since any code that isn't in a multiplexer is executed by default. The idea would thus be to do the following:

Parse the input FIRRTL code to find:
1. The location of the i/o declaration
2. The locations of every multiplexer in the design
3. The total number of multiplexers
Add additional coverage validator outputs in the i/o declaration part of the code. The idea is to add 2 additional 1-bit ports per multiplexer.

At each multiplexer use in the FIRRTL source, output the path taken to 2 coverage validators as follows:

out_a <= mux(cond, in_a, in_b)  //Example use of a multiplexer  
io_cov_valid_1 <= cond  
io_cov_valid_2 <= not(cond)  //Use of coverage validators to keep track of the path that was taken

These are all of the modifications that are needed to keep track of line coverage during a simulation.

Generating a Coverage report

The main work here was interpreting the meaning of the outputs added to the FIRRTL source. The idea here was to do a second pass of the coverage parser once a given test was done. The big difference now is that we have access to the values of the different coverage validators, which allows us to know which multiplexer paths were taken during the different tests. So we can compile the data retrieved from the coverage validators througout an entire test suite to find out which paths were taken and which were skipped. The results are then shown in a coverage report that has the following structure:

COVERAGE: 50.0% of multiplexer paths tested
COVERAGE REPORT:

+ circuit Test_1 :
+   module Test_1 :
+     input io_a : UInt<1>
+     input io_b_0 : UInt<2>
+     input io_b_1 : UInt<2>
+     input clock : Clock
+     output io_cov_valid_0 : UInt<1>
+     output io_cov_valid_1 : UInt<1>
+     output out : UInt<2>
+   
+     io_cov_valid_0 <= io_a
-     io_cov_valid_1 <= not(io_a)
+     out <= mux(io_a, io_b_0, io_b_1)

Here the first line gives a general percentage of how many of the possible control paths were taken and then the COVERAGE REPORT shows a modified version of the FIRRTL source with coverage prefixes added to each line:

+ means that the line was covered by a test in the test suite.
- means that the line was missed during all of the test suite's tests.

Interpreting the Coverage Report

What this report tells us (in the above example) is that one of our artificially added FIRRTL lines wasn't covered. This information can be used to deduce which path of our multiplexer was taken. For example, the above COVERAGE REPORT:

+     io_cov_valid_0 <= io_a
-     io_cov_valid_1 <= not(io_a)
+     out <= mux(io_a, io_b_0, io_b_1)

actually tells us that the case where io_a == 0 was never tested and thus one of our potential outputs was never tested.

Mapping loFIRRTL to Chisel

One could discuss the usefulness of having line coverage on Chisel code. One main case where this would not be as helpful would be when writing hardware generators, since there the notion of coverage isn't as clear: Has the hardware generator been tested? or more interestingly Has the generated hardware been tested?. I think that this question is open to discussion. This coverage report is thus given at the FIRRTL level but an other interesting report would contain the same line coverage information, shown directly in our original source description.

Future work on this part of the project could thus be to find a way to map the results to the original Chisel source using source locators. An other version of the coverage report would thus be:

COVERAGE: 50.0% of multiplexer paths tested
COVERAGE REPORT:

+ circuit Test_1 :
+   module Test_1 :
+     input io_a : UInt<1>
+     input io_b_0 : UInt<2>
+     input io_b_1 : UInt<2>
+     input clock : Clock
+     output io_cov_valid_0 : UInt<1>
+     output io_cov_valid_1 : UInt<1>
+     output out : UInt<2>
+   
+     io_cov_valid_0 <= io_a
-     io_cov_valid_1 <= not(io_a)
+     out <= mux(io_a, io_b_0, io_b_1)

NEW REPORT:

+ class Test_1 extends Module {
+    val io = IO(new Bundle {
+        val a = Input(UInt(1.W))
+        val b = Input(Vec(2, UInt(2.W)))
+        val out = Output(UInt(2.W))  
+    })
+    when(io.a) {
+        out := io.b(0)
-    }.otherwise {
-        out := io.b(1)
+    }
+ }

CLAassistant · 2020-11-03T14:48:25Z

All committers have signed the CLA.

ekiwi · 2020-11-03T17:32:02Z

Thanks for the PR Andrew, this is great!

I really like the thought you put into how to communicate the coverage results back to the user.

Some notes on how this could be improved:

Ideally you should try to write a firrtl pass over the firrtl compiler data structures instead of working on the string representation directly. This will make some of the current short comings much easier to solve.
Currently you name the outputs without checking whether that name is already used in the module. The firrtl compiler provides a Namespace class to help you automatically resolve any potential name clashes.
You seem to connect the coverage information to outputs of the module, however, how is this going to work for a design that has a module hierarchy? Here the firrtl compiler also features some helpers (namely the WiringTransform which can connect arbitrary wires/outputs throughout the module hierarchy).
An interesting variation on your current approach for connecting the coverage signals might be to use the new cover statement. This way you would not have to worry about finding a unique name (cover statements are not named) or wiring things through the hierarchy. Unfortunately, treadle does not have support for cover statements yet, however, it is on the radar to implement and I think it would be great if you could give @chick some feedback on what you would expect from an implementation. For example, assuming that you have a pass to insert cover statements for all mux conditions, in which format would you expect treadle to report the results so that you can then use them to generate your coverage report?

For high firrtl / Chisel coverage it might be interesting to consider the pass that Daniel Kasza has been working on: https://github.com/danielkasza/dank-formal/blob/main/src/main/scala/transforms.scala#L13 He is essentially adding cover statements for all branches in high firrtl. This information should be enough to calculate the line and branch coverage and you could try to map it back to the Chisel source using the FileInfo that is attached to every firrtl statement.

dobios · 2020-11-03T18:18:42Z

Thanks a lot for the quick response!

I completely agree with the comments, this solution felt a bit brute-force-y when I implemented it.
I'll try to change my solution so that it uses the firrtl compiler rather than string parsing, as you suggested.Once that's done hopefully other problems will be easier to solve.

Thanks again for the review!

ekiwi · 2020-11-03T19:11:16Z

Thanks a lot for the quick response!

Thanks for the PR!

I completely agree with the comments, this solution felt a bit brute-force-y when I implemented it.
I'll try to change my solution so that it uses the firrtl compiler rather than string parsing, as you suggested.Once that's done hopefully other problems will be easier to solve.

I know that writing your first firrtl pass is hard since there is very little documentation. Feel free to ask any questions that come up on the firrtl gitter: https://gitter.im/freechipsproject/firrtl

chick

This looks great to me. Thanks for effort, it looks like a great contribution.
I will defer to Kevin on the technical analysis. I'd also like to maintain the scalafmt
formatting also.

dobios · 2020-11-12T13:42:36Z

New Version of the Statement Coverage PR

As per the request, the coverage parser that was used to add additional coverage ports to the source code, via string parsing, was converted into a firrtl pass.

FIRRTL pass

A firrtl pass AddCoverageExpressions was created, which takes care of adding the additional coverage ports that were previously done using brute-force string parsing.
This now uses the Namespace of the module it's working on to make sure that no name collisions can occur and also handles multi-module circuits.

Coverage package object

The coverage package object defines a new Info child class that allows us to store the names of the newly added ports in the circuit's info. These names are then used when compiling the final report (which is still done by modifying the original source code's string for printing purposes).
The package also defines a Ledger class, similar to the one shown in the firrtl wiki. This class is used to keep track of the number of multiplexers in the design as well as maintaining references to the ports that were added in order to add them to the circuit's info at the end of the pass.

Coverage

The Coverage class, which was previously named CoverageReporter, now uses the information stored in the circuit's info field to generate the final coverage report rather than parsing the source string a bunch of times.

Let me know if ever there's anything that still needs to be changed/improved ( @chick @ekiwi )!

dobios · 2020-11-12T21:20:05Z

Thanks a lot for the review @ekiwi , your comments make a lot of sense, I'll get right to it!

chick

This is looking pretty good. Check out my suggestions in comments for GetFirrtlAst

chick · 2020-11-13T17:52:48Z

I missed one other suggestion for how to schedule and run the pass. I think you should add this to AddCoverageExpressions

  /** Only run this pass if there is an EnableCoverageAnnotation present
    *
    * @param state
    * @return
    */
  override def execute(state: CircuitState): CircuitState = {
    if(state.annotations.contains(EnableCoverageAnnotation)) {
      state.copy(circuit = run(state.circuit))
    } else {
      state
    }
  }

dobios · 2020-11-13T18:16:40Z

Thanks for the comments @chick ! Does this current state look good?

chick

One last quibble on GetFirrtlAst.scala.
Fix that and I will approve.
Otherwise looks great.
@ekiwi any other thoughts

ekiwi · 2020-11-13T20:15:53Z

@ekiwi any other thoughts

I think it is a fine implementation for the time being. Maybe we could mark it as experimental to allow for future API breaks.

The next step would require us to implement support for the cover statement in treadle. This way we can replace the output ports with cover statements which would almost automatically make this work for submodules as well. @dobios work can serve as a good use-case example to see how a custom coverage report generator might want to plug into a generic cover statement implementation. I.e., the idea would be that treadle can load coverage report generator classes that analyze the coverage and turn it into a human readable report.

dobios · 2020-11-13T21:12:00Z

@ekiwi any other thoughts

I think it is a fine implementation for the time being. Maybe we could mark it as experimental to allow for future API breaks.

Nice thanks!

The next step would require us to implement support for the cover statement in treadle. This way we can replace the output ports with cover statements which would almost automatically make this work for submodules as well. @dobios work can serve as a good use-case example to see how a custom coverage report generator might want to plug into a generic cover statement implementation. I.e., the idea would be that treadle can load coverage report generator classes that analyze the coverage and turn it into a human readable report.

I did see that since I've implemented the first version of this the cover statement was added to Chisel, it does seem like a more elegant solution. Is anyone currently working on adding it to Treadle?

jackkoenig · 2020-11-17T19:29:22Z

To backport this to 1.3.x, we should tweak the change to TreadleOptions to use https://github.com/alexarchambault/data-class

Basically, define the copy and unapply methods as they exist today (well, before this change), and then change it from a case class to @data.

ekiwi · 2020-11-17T20:06:25Z

To backport this to 1.3.x, we should tweak the change to TreadleOptions to use https://github.com/alexarchambault/data-class

I don't think this needs to be backported. This is more of a technology demo and not really ready for production usage anyways. Like currently it only works if you only have a single module in your design.

jackkoenig · 2020-11-17T20:29:21Z

Makes sense, fair enough. Getting the SNAPSHOT autopublishing in will be nice so people can try it out using the SNAPSHOT.

dobios added 17 commits September 24, 2020 15:15

added test coverage and FIRRLT line coverage info

96be935

Added Coverage text to README

6173788

Colors

923abf9

Update README.md

6063b30

typos

7cafa59

Update README.md

ba6d0e9

Update README.md

3edabd0

inlined private functions

289eeeb

Merge branch 'master' of github.com:chisel-uvm/treadle

5b1a5c5

Update README.md

e46bff7

Update README.md

6c108e4

Update README.md

8bdbdb9

added options to toggle coverage

3555d88

Update README.md

700be0c

newline at eof

37e4a50

newline at eof

18e5af3

names

d3d5341

dobios requested a review from a team as a code owner November 3, 2020 14:48

dobios added 2 commits November 3, 2020 16:58

doc bug

3d00da2

removed illegal inner function documentation

fe7eb8c

chick suggested changes Nov 6, 2020

View reviewed changes

Comment thread src/main/scala/treadle/Driver.scala

Comment thread README.md Outdated

removed whitespace and moved new annotation to end of list

c757fc2

dobios marked this pull request as draft November 10, 2020 19:06

Andrew Dobis added 3 commits November 10, 2020 20:09

WIP: coverage firrtl pass

ce6d99a

WIP: Added additional coverage ports in firrtl pass

23fb284

removed useless imports

0649e3c

ekiwi reviewed Nov 12, 2020

View reviewed changes

dobios added 2 commits November 13, 2020 14:49

Converted report into a case class

29aaad0

removed unused imports

2eb068e

chick suggested changes Nov 13, 2020

View reviewed changes

Comment thread src/main/scala/treadle/stage/phases/GetFirrtlAst.scala Outdated

Replaced explicit annotation check with dependencies

fe67463

dobios requested review from chick and ekiwi November 13, 2020 18:15

removed unused imports

a500e04

chick suggested changes Nov 13, 2020

View reviewed changes

Comment thread src/main/scala/treadle/stage/phases/GetFirrtlAst.scala Outdated

removed useless comments

3b4e25a

dobios requested a review from chick November 13, 2020 21:06

chick approved these changes Nov 13, 2020

View reviewed changes

chick merged commit 925687a into chipsalliance:master Nov 13, 2020

jackkoenig added this to the 1.3.x milestone Nov 17, 2020

jackkoenig modified the milestones: 1.3.x, 1.4.0, 1.5.0 Nov 19, 2020

This was referenced Jan 4, 2021

DependencyAPI Phase 1 ucb-bar/chiseltest#247

Closed

Dependencyapi phase1 ucb-bar/chiseltest#253

Closed

dobios mentioned this pull request Oct 10, 2022

Coverage report chiselverify/chiselverify#44

Closed

Conversation

dobios commented Nov 3, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Adding Statement/Branch Coverage to Treadle

Modifying the input FIRRTL code

Generating a Coverage report

Interpreting the Coverage Report

Mapping loFIRRTL to Chisel

Uh oh!

CLAassistant commented Nov 3, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ekiwi commented Nov 3, 2020

Uh oh!

dobios commented Nov 3, 2020

Uh oh!

ekiwi commented Nov 3, 2020

Uh oh!

chick left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

dobios commented Nov 12, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

New Version of the Statement Coverage PR

FIRRTL pass

Coverage package object

Coverage

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

dobios commented Nov 12, 2020

Uh oh!

chick left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

chick commented Nov 13, 2020

Uh oh!

dobios commented Nov 13, 2020

Uh oh!

chick left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

ekiwi commented Nov 13, 2020

Uh oh!

dobios commented Nov 13, 2020

Uh oh!

jackkoenig commented Nov 17, 2020

Uh oh!

ekiwi commented Nov 17, 2020

Uh oh!

jackkoenig commented Nov 17, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

dobios commented Nov 3, 2020 •

edited

Loading

CLAassistant commented Nov 3, 2020 •

edited

Loading

dobios commented Nov 12, 2020 •

edited

Loading