google / google/xls

Proc inlining can introduce deadlocks

Open
#949 0 comments 0 reactions 1 assignee Claimed by @grebe View on GitHub
bug ir
Dominant language
C++
Stars
1.9k
Forks
283
Avg merge
2d 10h
Merged PRs (30d)
135

Description

If an inlined proc includes a receive on an external channel, proc inlining can introduce a deadlock.

Consider to procs A and B where B has an external receive. Before inlining, if the receive in B blocks then only the operations in B are blocked. After inlining where the operations of A and B are inside a single proc, the inlined receive from B blocks all operations of A and B. This change in behavior can result in deadlock.

Example below. `C` and `D` are external channels where a send on `C` triggers a send on `D` via some external mechanism:

```
// Initial state is false.
proc A(st: bool) {
send_if(C, st, 42)
next(true)
}

proc B() {
receive(D)
}
```

After inlining A and B into the same proc you'll get something like:

```
proc top(A_st: bool) {
send_if(C, A_st, 42)
receve(D)
next(true)
}
```

This will deadlock on the first tick because the send on `C` does not fire but the receive on `D` does.

A fix is to convert receives on external channels to non-blocking receives. The non-blocking receive only passes its activatoin bit along if data was actually received. This shouldn't be too difficult, but there is a metaissue of how much we want to further invest in proc inlining vs multiproc codegen.

@grebe FYI

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.