next up previous
Next: Graph pruning Up: Reduced Set of RSGs Previous: Reduced Set of RSGs


Graph division

The division operation takes place for the $ x\rightarrow sel = NULL$, $ x\rightarrow sel = y$ and $ y = x \rightarrow sel$. The goal of this operation is to split the input $ rsg$ into several graphs, such that for each one of these graphs, the node directly pointed to by $ x$ points to a single node by selector $ sel$. Going back to Fig. 1 (a) and (b), we can see how the $ rsg$ is divided into graphs $ rsg\prime_1$ and $ rsg\prime_2$.

The original graph is presented in Fig. 1(a). Note that the node directly pointed to by $ x$, $ n_1$, points to two different nodes by selector $ nxt$. Therefore, we divide this graph into two different ones in such a way that in each resulting graph, $ n_1$ points to a single node by $ nxt$. We see these two graphs in Fig. 1(b), where in $ rsg\prime_1$ the node $ n_1$ only points to node $ n_2$ and in $ rsg\prime_2$ this node only points to node $ n_3$.

Basically, with the division, we try to recover the individual characteristics of memory configurations that were fused into a single RSG in a previous sentence. However, this division can generate redundant or inexistent nodes, and links which should be removed by the subsequent PRUNE operation (described next). This way, we separate several memory configurations that were represented by the same RSG, achieving a more precise representation.

Taking this into account, we define DIVIDE $ (rsg, x, sel) =
\{rsg_1, .., rsg_n\}$ which divides the $ rsg$ in the set $ \{rsg_1,
.., rsg_n\}$ regarding the pvar $ x$ and selector $ sel$. This division is carried out in the following way. If $ n\in N(rsg) \vert
<x, n> \in PL(rsg)$, then, $ \forall <n, sel, n_i> \in NL(rsg)$, we create a $ rsg\prime_i$ such that $ N(rsg\prime_i) = N(rsg)$, $ PL(rsg\prime_i) = PL(rsg)$ and $ NL(rsg\prime_i) = NL(rsg)
\setminus \{<n, sel, n_j> \in NL(rsg),$ $ \forall n_j \neq n_i\}$. Each $ rsg\prime_i$ can contain a single node $ n_i$ pointed to by $ n$ by selector $ sel$. This $ rsg\prime_i$ is subsequently pruned to obtain the definitive $ rsg_i =$ PRUNE $ (rsg\prime_i)$ for the DIVIDE function. This pruning process is described next.


next up previous
Next: Graph pruning Up: Reduced Set of RSGs Previous: Reduced Set of RSGs
Rafael Asenjo Plaza 2002-02-19