google / google/xls

Mutually exclusive side effects with a token relationship can cause (avoidable?) scheduling problems

Open
#1,017 2 comments 0 reactions 0 assignees View on GitHub
ir optimizer
Dominant language
C++
Stars
1.9k
Forks
283
Avg merge
2d 10h
Merged PRs (30d)
135

Description

If two side-effecting operations that are ordered by a token relationship have mutually exclusive predicates, the token relationship can be removed.

Removing this token can be useful in scheduling. For example

```
send0: token = send(tok, state, channel_id=0)
rcv0: (token, bits[32]) = receive(send0, channel_id=1)
rcv0_token: token = tuple_index(rcv0, index=0)
send1: token = send(rcv0_token, send_data, pred=p, channel_id=2)
rcv1: (token, bits[32]) = receive(send1, pred=not_p, channel_id=3)
next_state: bits[32] = tuple_index(rcv1, index=1)
```

Note that a token relationship exists between send1 and rcv1, but they have mutually exclusive predicates. If rcv0->send1 has a long IO constraint, this IR could be infeasible to schedule because of the long state backedge. Rewriting `rcv1: (token, bits[32]) = receive(rcv0_token, pred=not_p, channel_id=3)` is legal because `send1` and `rcv1` have mutually exclusive predicates and makes this IR schedulable.

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.