Module rules 

Matching a set of rules against a term.

Design: spec/10-backend.md section 10.2 and spec/optimizer/13-rewrite-rules.md. The rules themselves are rule files, one per rule set, and the automaton they compile into is generated by rucc-rules when the crate that owns the file is built. What is here is the walk over that automaton, which is the same walk for every rule set and is written once.

Why this is at the bottom of the stack

Two crates match with a generated table and neither can see the other. rucc-codegen lowers IR to machine terms and rucc-opt rewrites IR to IR, and a lowering and a rewrite are the same claim about two terms, so they are the same trie and the same walk. Putting the walk here rather than in either of them is what keeps that true rather than merely intended, and it costs nothing: none of this knows what an instruction is, what a value is, or what C is.

What a subject is

A rule matches a term, and the compiler does not have terms: it has a function full of instructions, and what a pattern is about is one of them and whatever it was computed from. So the walk is written against Subject, which is the three questions the automaton asks of whatever it is matching, and a caller answers them out of the IR without building a term to be thrown away. A test can answer them out of anything at all, which is what the tests at the bottom of this file do.

What a match gives back

The rule that fired and what its pattern bound, in the order the pattern binds it. The bindings are positions rather than names because that is what the walk has, and the rule carries the names for anything that has to say what it did. Building the replacement out of Piece belongs to the caller rather than to this file, because what a replacement becomes is a machine instruction in one crate and an IR instruction in the other, and this module is about matching.

A name written twice

A pattern may write one name in two places, which is how x & x is said. The second place becomes a branch in Node::same rather than a hole, and it asks the subject whether the two are the same thing rather than comparing nodes, because a node is a place and two places can hold one value. It is a concrete test, so it is tried before the wildcard for the same reason every other test is: a rule about one value in both operands is more specific than a rule about any two.

Order

At every node the concrete tests are tried before the branch that takes anything, so a rule naming an operand is tried before a rule taking whatever is there. That is the maximal munch spec/10-backend.md asks for, and it falls out of the shape of the trie rather than being sorted for. Among rules that are equally specific the first one written wins.

The concrete tests are three kinds of question and they are asked in this order: the head of the term, then its value as a constant, then whether it is what an earlier binding took. spec/optimizer/36-lowering-and-isel.md section 36.5 asks that the order be stated rather than left to be read out of what the matcher does, so it is stated here, next to the walk that applies it. It decides nothing in any rule set shipped today, because deciding something would need one node to ask two kinds of question about one place and none does, which is a number rucc-rules prints in the header of every table it generates.

Finding a branch

A term has one head and a constant has one value, so at most one head branch and at most one value branch can match, and the two lists are sorted by the thing they are asked about. That makes finding the branch a binary search rather than a walk over the node, which is the difference section 36.5 is about: the widest node of the x86-64 rule set has a hundred and sixty seven heads on it, and the selector reaches that node once for every instruction in the program. A repeat of an earlier binding is not searchable, because two of them can hold the same value, so those stay in the order the rules were written and there are never many.

A guard is part of deciding whether a rule fires, so a rule whose guard is false is a rule that did not match, and the walk carries on looking rather than giving up. What that costs is the search from where the guard failed, which is the price of a guard being allowed to be about the values rather than only about the shape.

Structs

Match

What a successful match found.

Node

One node of the trie over the patterns.

Rule

One rule, as much of it as matching needs.

Table

A set of rules, as an automaton over their patterns.

Enums

Piece

One piece of a replacement, in the pre-order that builds it.

Traits

Subject

The bits of a term the automaton asks about.

Type Aliases

Guard

A condition on the constants a pattern matched.