6
$\begingroup$

In the context of an unusual compiler problem, I have a graph in which the vertices are variables, and the edges correspond to whether the instruction set has an instruction that copies the source vertex to the target vertex. The instruction set also has the unusual property that the instructions may destroy (overwrite with non-predictable values) the contents of some of the variables. Hence the edges are labeled with sets: subsets of the (fixed) set of all variables that are destroyed by the instruction.

So for example, I might have instructions like the following:

  • a -> b, clobber set = {d}
  • b -> c, clobber set = {}
  • a -> c, clobber set = {d,f}

Note that there is a direct path from a -> c, but that there is also an indirect path from a -> b -> c, where the union of the clobber sets is {d}, i.e., a strict subset of the clobber set from the direct path, namely {d,f}. Hence the path a -> b -> c should be preferred as it has a lesser effect on the other variables.

Consider the following variation on the above example:

  • a -> b, clobber set = {e}
  • b -> c, clobber set = {}
  • a -> c, clobber set = {d,f}

By similar reasoning, we have two paths from a -> c: the direct one, which clobbers {d,f} and the indirect one a -> b -> c which clobbers {e}. Given that {d,f} and {e} are incomparable subsets of the variable set, we would like to retain information about both of these paths.

So the problem is as follows: given such a directed graph with edges labeled with sets, compute all "minimal" paths through the graph with respect to the clobber sets. For the first example, we should return a -> b: {d}, b -> c: {}, a -> c: {d}. For the second example, we should return a -> b: {e}, b -> c: {}, a -> c: {d,f}, a -> c: {e} (where this last fact was derived from the other edges).

The problem has some flavor of a shortest-paths problem, but given the weaker partial ordering rather than the stricter total ordering on the edge labels, the existing algorithms are inapplicable.

References to literature would also be appreciated.

$\endgroup$
4
$\begingroup$

I suggest you use a fixpoint algorithm, using a worklist implementation. I'll start by providing an intuitive, English-language description of an algorithm for this problem; then a more formal presentation.


Intuitive algorithm. Basically, we'll apply the following closure rules to the graph as many times as possible, until they don't produce anything new:

  • If there is an edge $u\to v$ with clobber set $S$ and an edge $v\to w$ with clobber set $T$, then add an edge $u\to w$ with clobber set $S\cup T$.

  • If there is an edge $u \to v$ with clobber set $S$ and an edge $u \to v$ with clobber set $T$, where $S \subset T$, then remove the edge with clobber set $T$.

Intuitively, we'd like to keep applying these in all possible ways until the graph doesn't get any bigger; then you're done. Note that I'm treating the graph as a multigraph, so there can be multiple edges between any pair of vertices.

In practice, you need to implement this carefully (you don't want to add an edge that would be immediately removed by the other closure rule). So, here is an algorithm that applies the above idea, in a reasonable way:

  1. Initially, mark all of the edges of the graph.

  2. While there exists at least one marked edge:

    a. Pick any marked edge; suppose it is $u \to v$ with clobber set $S$. Remove the mark on this edge.

    b. For each edge $v\to w$ with clobber set $T$, call $\text{MaybeAddEdge}(u,w,S\cup T)$.

Here the subroutine $\text{MaybeAddEdge}(u,v,S)$ is defined to do the following steps:

  1. For each edge $u \to v$ with clobber set $T$:

    a. If $T \subseteq S$, return immediately (without adding any edges).

    b. If $S \subset T$, remove the edge with clobber set $T$.

  2. Add an edge $u \to v$ with clobber set $S$, and mark it.

At the end of execution, after we've finished applying the closure rules, the set of clobber sets on all of the edges from $u$ to $v$ gives the set of minimal clobber sets for all paths from $u$ to $v$. This is effectively a worklist/fixpoint algorithm, and it follows pretty directly from the problem statement.

If you prefer a more formal treatment of this problem, see below.


Notation. Let $V$ denote the set of variables. Define a partial order $\mathcal{L}$ as follows: Consider the pre-order $(2^{2^V},\le)$, where an element $\ell \in 2^{2^V}$ is a set of clobber sets, and we define $\ell \le \ell'$ iff for every clobber set $S \in \ell$, there exists a clobber set $S' \in \ell'$ such that $S' \subseteq S$. Now we can define the equivalence relation $\equiv$ by $\ell \equiv \ell'$ iff $\ell \le \ell'$ and $\ell' \le \ell$. Modding out by $\equiv$ yields a partial order $(\mathcal{L},\le) = (2^{2^V},\le)/\equiv$. In other words: every set $\ell \in 2^{2^V}$ of clobber sets is equivalent to one where there is no pair of sets $S,S' \in \ell$ such that $S \subset S'$ and $S\ne S'$ (if there is such a pair of sets, we can remove $S'$ from $\ell$ and get another equivalent set), so we let $\mathcal{L}$ denote the set of elements $\ell$ that are in this canonical form.

As it happens, $\mathcal{L}$ is a meet semi-lattice with a meet operation $\wedge$. In particular, the join operation is defined by $\ell \vee \ell' \equiv \ell \cup \ell'$. Let $\bot = \{2^V\}$ denote the bottom element in this lattice and $\top = \{\emptyset\}$ denote the top element. Of course, if $S$ is a clobber set (i.e., $S \subseteq V$), then $\{S\}$ is a lattice element of $\mathcal{L}$ (corresponding to the single clobber set $S$).

Notice that a lattice element $\ell \in \mathcal{L}$ corresponds to a set of minimal clobber sets. Thus, the lattice will be helpful for recording this kind of information as the algorithm progresses.

Define the binary operation $\circ$ by $\ell \circ \ell' \equiv \{S \cup S : S \in \ell, S' \in \ell'\}$. Conceptually, this is going to represent the effect of concatenating two paths (where $\ell$ is the set of minimal clobber sets for some path $u\to v$ and $\ell'$ is the set for some path $v \to w$).

Approach. We are going to build a 2-dimensional table $T[\cdot,\cdot]$. At any point in the algorithm, for each pair of variables $u,v \in V$, $T[u,v]$ will hold an element of $\mathcal{L}$ that denotes an over-approximation of the desired set of minimal clobber sets for all paths from $u$ to $v$.

If $u,v \in V$ are variables, at the end of the algorithm $T[u,v]$ will contain the set of all minimal clobber sets for all paths from $u$ to $v$. We'll find a least fixpoint for $T[\cdot,\cdot]$, subject to the following condition:

  • For all vertices $u$ and all edges $v\to w$ (with clobber set $S$), $T[u,v] \circ \{S\} \le T[u,w]$.

  • For all vertices $u$, $T[u,u] = \top$.

To find the least fixpoint, we'll use a standard worklist approach.

Algorithm. Let $W$ denote a set data structure that can hold pairs of vertices. Then the algorithm is as follows:

  1. Initialize $T[u,v] \gets \{S\}$ for each edge $u\to v$ with clobber set $S$ in the graph, $T[u,u] \gets \top$ for each vertex $v \in V$, and otherwise $T[u,v] \gets \bot$. Initialize $W$ to contain the set of pairs $(u,v)$ such that there is an edge $u\to v$ in the graph together with the set of pairs $(u,u)$ such that $u$ is a vertex in the graph.

  2. While $W \ne \emptyset$, do:

    a. Pop an arbitrary vertex-pair $(u,v)$ from $W$.

    b. For all edges $v \to w$ (with clobber set $S$) out of $v$, do:

    • Let $o \gets T[u,w]$. Set $T[u,w] \gets T[u,w] \vee (T[u,v] \circ \{S\})$. If $o \le T[u,w]$, insert $(u,w)$ into $W$.

The final value of $T[\cdot,\cdot]$ will have the desired form (it is a minimal fixpoint subject to all of the conditions above), and thus will be a valid solution to your problem. Each $T[u,v]$ contains the set of minimal clobber sets, taken over all paths from $u$ to $v$.

Notice that the above algorithm does not specify the order in which you pull items out of the worklist. Good scheduling algorithms can improve the performance of this scheme. One standard heuristic is to use reverse post-order (derived from a DFS on the graph) to prioritize which elements to pull out of the worklist.

Also note that the running time of this algorithm could be exponential, if your graph is unfortunate. This is unavoidable: there might be exponentially many clobber sets, so the output size might be exponential in the size of the input in the worst case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.