Outlining pass
- Dominant language
- C++
- Stars
- 1.9k
- Forks
- 283
- Avg merge
- 2d 10h
- Merged PRs (30d)
- 135
Description
For II > 1 we'll need the ability to merge together entire blocks of code, not just single nodes (as we do in the current `mutual_exclusion_pass`). To do this, we should outline (opposite of inlining) functions from the code before running the `mutual_exclusion_pass`, and then inline them afterward.
First, we'll define _antiunification_ to be a process in which we match two nodes against each other as deeply as possible. For example, the antiunification of `x + (5 * y)` and `3 + (4 * (p + q))` would be `a + (b * c)`. The technical definition is that the antiunification is the largest term that can be instantiated to yield each of the given terms. We can swap the operands of commutative ops and reassociate associative ops to make the antiunification bigger, though this is not essential. Antiunification is itself commutative and associative, so the antiunification of a set of nodes is the same no matter how you decompose it into pairwise applications of antiunification.
The _collision-avoiding antiunification_ of two nodes in a dataflow graph is the largest pair of matching subgraphs such that the two subgraphs are nonoverlapping. For example, if you had `x = a + b * c; y = d + e * x; z = f + g * y;`, then the antiunification of `y` with `z` would be `_ + (_ * (_ + _ * _))`, but the collision-avoiding antiunification would be `_ + _ * _`, because the two subgraphs that are shaped like `_ + (_ * (_ + _ * _))` overlap. From here on, when we refer to antiunification, assume that it is collision-avoiding.
In our outlining pass, we will repeatedly (greedily) try to outline the best possible single function for a given dataflow graph. To do this, we will first compute the antiunification of every pair of nodes in the dataflow graph, cataloging the antiunifiers in a table of quadratic size. This table can be computed using dynamic programming. If two nodes have no antiunifier, this fact is also cataloged in the table. Then, our goal is to choose a subset of size `n` of nodes that when antiunified generate a term of size `k`, such that `n * k` is maximized. If we consider the table of antiunifiers to be a graph where edges are weighted by the size of the pairwise antiunifier of two nodes if it exists, then we want to choose a clique such that the minimum edge weight in the clique is maximized. This may be a simplification, though I can't come up with an example where it would perform worse.
This problem can be greedily solved in the following way. First, remove the lowest weight edges until the graph is a disjoint union of cliques (which can be recognized by checking if the complement of each connected component contains no edges). Then execute the following algorithm on each clique:
```
// Take all the minimum edge weight edges and remove one of their endpoints.
// The endpoint chosen is based on the following rule: if at least one of the endpoints has been
// removed already, skip that edge, otherwise remove the node that has the smaller minimum
// incident edge weight.
// This function returns the optimal value; returning the optimal clique only requires small changes.
int64_t AblateClique(absl::flat_hash_set clique, std::function edge_weight) {
// Find all edges whose edge weight is equal to the minimum edge weight in the clique
absl::flat_hash_set> minimum_edge_weight_edges = ...;
for (const auto& [a, b] : minimum_edge_weight_edges) {
if (!clique.contains(a) || !clique.contains(b)) { continue; }
int64_t minimum_incident_edge_weight_a = 0, minimum_incident_edge_weight_b = 0;
for (Node* node : clique) {
if ((node == a) || (node == b)) { continue; }
minimum_incident_edge_weight_a = std::min(minimum_incident_edge_weight_a, edge_weight(node, a));
minimum_incident_edge_weight_b = std::min(minimum_incident_edge_weight_b, edge_weight(node, b));
}
if (minimum_incident_edge_weight_a < minimum_incident_edge_weight_b) {
clique.erase(a);
} else {
clique.erase(b);
}
}
int64_t number_of_nodes_saved = (clique.size() - 1) * Antiunify(clique).size();
return std::max(number_of_nodes_saved, AblateClique(clique, edge_weight));
}
```
cc @meheff
Contributor guide
Assessment
This issue has not been assessed yet.