# FSM-Based Coverage

`generate-fsm` creates state-coverage-enhanced C++ testbenches for sequential designs with finite state machines (FSMs). Instead of random input patterns, it uses **depth-first search (DFS)** over the FSM state graph to reach every state and transition.

## When to Use It

- **Sequential designs with FSMs** (clocks, resets, internal state)
- **Random testing misses states** because reaching them requires specific input sequences
- **Designs with internal timers/counters** that gate transitions

Traditional `stg generate` relies on random inputs, which often fails to hit states like `S_PED_WALK` that need multi-cycle sequences. `generate-fsm` discovers the FSM structure and generates targeted tests.

## Quick Start

### Without LLM (Deterministic)

```bash
stg generate-fsm design.sv \
  --golden golden.sv \
  --out tb.cpp \
  --out-exe tb \
  --fsm-method deterministic
```

### With LLM (More Flexible)

Requires an API key (`GOOGLE_API_KEY`, `OPENAI_API_KEY`, or `OPENROUTER_API_KEY` in `.env` or environment):

```bash
stg generate-fsm design.sv \
  --golden golden.sv \
  --out tb.cpp \
  --out-exe tb \
  --fsm-method lm \
  --lm-provider gemini
```

## FSM Extraction Methods

| Method | Description | Requirements |
|--------|-------------|--------------|
| `deterministic` | Parser-based (iverilog/sv-parser) | None |
| `lm` | LLM identifies FSM from source | API key, `uv` installed |

- **deterministic**: Fast and reliable. Works for standard FSM coding styles.
- **lm**: Better for complex or unusual FSMs. Uses an LLM to interpret the RTL.

## State Analysis Caching

Use `--state-analysis` to save and reuse FSM analysis:

```bash
# First run: analyze design and save to fsm.json
stg generate-fsm design.sv --golden golden.sv --out tb.cpp \
  --state-analysis fsm.json

# Later runs: load from fsm.json (skips analysis)
stg generate-fsm design.sv --golden golden.sv --out tb.cpp \
  --state-analysis fsm.json
```

- If the file **exists**: load it and skip FSM identification.
- If it **does not exist**: run analysis and save to that path.

## Examples

### Traffic Light (Deterministic)

```bash
cd examples/traffic_light

stg generate-fsm traffic_light_controller.sv \
  --golden traffic_light_controller_golden.sv \
  --out tb.cpp \
  --out-exe tb \
  --clock clk \
  --reset rst_n \
  --reset-active low \
  --fsm-method deterministic \
  --verilator-coverage

./tb
```

### Sequence Detector (LM-Based)

```bash
cd examples/seq_detector

# Set API key: export GOOGLE_API_KEY="..."
stg generate-fsm seq_detector.sv \
  --golden seq_detector_golden.sv \
  --out tb.cpp \
  --out-exe tb \
  --fsm-method lm \
  --lm-provider gemini \
  --state-analysis state_analysis.json

./tb
```

## Output

- **Testbench**: C++ file using Verilator
- **State analysis JSON**: FSM states, transitions, control/data signals
- **Executable** (with `--out-exe`): Compiled testbench binary

The testbench traverses the FSM via DFS, applies inputs that satisfy transition conditions, and compares DUT outputs to the golden model.

## Transition Verification Model

For each attempted transition edge:

1. Apply `input_condition` to controllable inputs.
2. Wait up to `--transition-timeout` cycles for `wait_condition`.
3. Compare DUT outputs against golden outputs.
4. Read DUT internal FSM state and verify expected `to_state`.

By default, a transition is considered successful when steps 2-4 pass.

## Optional Line Execution Check

Use `--line-coverage-check` to add an extra verification gate based on Verilator runtime counters (`getCounters()`):

```bash
stg generate-fsm design.sv \
  --golden golden.sv \
  --out tb.cpp \
  --out-exe tb \
  --fsm-method deterministic \
  --line-coverage-check
```

When enabled:

- STG auto-enables Verilator `--coverage` for `generate-fsm` compilation.
- The generated testbench snapshots coverage counters before/after each transition attempt.
- A transition passes only if:
  - wait-condition succeeds,
  - state reaches expected target,
  - and at least one relevant line/block counter increased.

This helps distinguish "state appeared correct" from "transition logic actually executed."

## Edge Status in Statistics

`test_stats.json` includes per-edge `status` and `lines_executed`:

- `covered`: transition verified successfully
- `impossible`: input condition unsatisfiable
- `timeout`: wait condition did not become true in time
- `state_mismatch`: wait succeeded but target state mismatched
- `no_lines_executed`: state/wait checks passed but no line counter increase (only when line check enabled)
- `unreachable`: DFS did not reach/close the edge

Summary fields include:

- `line_coverage_check_enabled`
- `line_check_passed_transitions`
- `line_check_failed_transitions`

## Verilator Binary Selection

For Verilator-based compilation, STG uses:

- Default: `verilator` from your `PATH`
- Override: set `STG_VERILATOR_PATH` to another Verilator binary

## Troubleshooting

### "No state machines found"

The design may have no detectable FSM, or the coding style is not recognized. Try `--fsm-method lm` for LLM-based extraction.

### LM method fails

- Ensure `uv` is installed: <https://docs.astral.sh/uv/>
- Check API keys in `.env` or environment
- Supported keys: `GOOGLE_API_KEY`, `OPENAI_API_KEY`, `OPENROUTER_API_KEY`

### Missed states in coverage

- Increase `--dfs-passes` for more edge coverage
- Increase `--transition-timeout` if internal conditions take many cycles
- Use `--state-analysis` to inspect the extracted FSM; fix or adjust if extraction is wrong

## See Also

- [Modes Overview](modes_overview.md) — General STG modes and design types
- [CLI Reference](../reference/cli.md) — Full `generate-fsm` flag reference
- [Advanced Features](advanced.md) — Coverage analysis with Verilator