Join Operation

The join algorithm on PCGs takes as input PCGs $\mathcal{G}$ and ${\mathcal{G}}^{\prime }$ and mutates $\mathcal{G}$ to join in ${\mathcal{G}}^{\prime }$.

The algorithm proceeds in the follow steps:

1. The Owned PCG of ${\mathcal{G}}^{\prime }$ is joined into the Owned PCG of $\mathcal{G}$ (this may also change the capabilities of $\mathcal{G}$)
2. The capabilities of ${\mathcal{G}}^{\prime }$ are joined into the capabilities of $\mathcal{G}$.
3. The Borrow State of ${\mathcal{G}}^{\prime }$ is joined into the Borrow State of $\mathcal{G}$

We now describe each step in detail:

Owned PCG Join

Let $\mathcal{O}$ be the owned PCG of $\mathcal{G}$ and ${\mathcal{O}}^{\prime }$ the PCG of ${\mathcal{G}}^{\prime }$.

1. For each local $v$ in the MIR body:
   1. If $v$ is allocated in both $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$:
      1. Join the place expansions rooted at ${\mathcal{O}}^{\prime }[v]$ into $\mathcal{O}[v]$
   2. Otherwise, if $v$ is allocated in $\mathcal{O}$, it should be deallocated in $\mathcal{O}$

The algorithm $joi{n}_{\mathcal{E}}(\mathcal{E},{\mathcal{E}}^{\prime },\mathcal{C},{\mathcal{C}}^{\prime })$ joins a set of place expansions ${\mathcal{E}}^{\prime }$ into a set of place expansions $\mathcal{E}$, and makes corresponding changes to capabilities $\mathcal{C}$.

1. Let ${\mathcal{E}}^{\prime \prime }$ be an ordered list of the expansions in ${\mathcal{E}}^{\prime }$ sorted in order of ascending length of the projections of their base place
2. For each $\overline{p^{\prime }}$ in ${\mathcal{E}}^{\prime \prime }$:
   1. Let $p^{\prime }$ be the base of $\overline{p^{\prime }}$.
   2. If there exists a $\overline{p}\in \mathcal{E}$ where the base of $\overline{p}$ is $p^{\prime }$:
      1. If $\overline{p}\ne \overline{p^{\prime }}$
         1. Perform collapse($p^{\prime }$, $\mathcal{E}$, $\mathcal{C}$)
         2. Otherwise do nothing (go back to the top of the loop)
   3. Otherwise, if $\mathcal{E}$ contains an expansion $\overline{p}$ and $p^{\prime }\in \overline{p}$:
      1. Add $\overline{p^{\prime }}$ to $\mathcal{E}$
      2. If $p^{\prime }\in {\mathcal{C}}^{\prime }$:
         1. Assign capability ${\mathcal{C}}^{\prime }[p^{\prime }]$ to $p^{\prime }$ in $\mathcal{C}$
         2. Otherwise, remove capability to $p^{\prime }$ in $\mathcal{C}$
      3. For each $p^{\prime \prime }\in \overline{p^{\prime }}$:
         1. If $p^{\prime \prime }\in {\mathcal{C}}^{\prime }$:
            1. Assign capability ${\mathcal{C}}^{\prime }[p^{\prime \prime }]$ to $p^{\prime \prime }$ in $\mathcal{C}$
         2. Otherwise, remove capability to $p^{\prime \prime }$ in $\mathcal{C}$

Place Capabilitiies Join

The algorithm join($\mathcal{C},{\mathcal{C}}^{\prime }$) is defined as:

1. For each p: c in $\mathcal{C}$:
   1. If $p\notin {\mathcal{C}}^{\prime }$:
      1. Remove capability to $p$ in $\mathcal{C}$
   2. Otherwise:
      1. If $min(c,{\mathcal{C}}^{\prime }[p])$ is defined:
         1. Assign capability $min(c,{\mathcal{C}}^{\prime }[p])$ to $p$ in $\mathcal{C}$
      2. Otherwise, remove capability to $p$ in $\mathcal{C}$

Borrow State Join

1. The borrow graphs are joined
2. The latest maps are joined
3. The validity conditions are joined

Borrow PCG Join

Joining ${\mathcal{B}}^{\prime }$ into $\mathcal{B}$, where $b$ is the block for $\mathcal{B}$ and $b^{\prime }$ is the block for ${\mathcal{B}}^{\prime }$.

Update the validity conditions for each edge $e$ in ${\mathcal{B}}^{\prime }$ to require the branch condition $b^{\prime }\to b$.

Update the validity

1. If $b$ is a loop head perform the loop join algorithm as described here.
2. Otherwise:
   1. For each edge $e^{\prime }$ in ${\mathcal{B}}^{\prime }$:
      1. If there exists an edge $e$ of the same kind in $\mathcal{B}$
         1. Join the validity conditions associated with $e$ in ${\mathcal{B}}^{\prime }$ to the validity conditions associated with $e$ in $\mathcal{B}$
      2. Otherwise, add $e$ to $\mathcal{B}$
   2. For all placeholder lifetime projections $\hat{p}\downarrow r\text{at}\text{FUTURE}$ in $\mathcal{B}$:
      1. Label all lifetime projection nodes of the form $\hat{p}\downarrow r$ in $\mathcal{B}$ with $\text{FUTURE}$