\documentclass{article}
\usepackage[T1]{fontenc}
\usepackage[margin=1.5in]{geometry}
\usepackage{parskip}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{float}

\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\usetikzlibrary{patterns}

\setlength{\parindent}{0mm}
\renewcommand{\familydefault}{\sfdefault}

\newcommand{\D}[2]{\delta(#1,#2)}
\newcommand{\Dp}[1]{\D{#1}{\cdot}}

\newcommand{\Dt}[2]{$\D{#1}{#2}$}
\newcommand{\Dpt}[1]{$\Dp{#1}$}

\newcommand{\txt}[1]{\text{#1~}}

\newcommand{\FIXME}[0]{\colorbox{red!25}{\textcolor{red!75!black}{\small FIXME}}}

\def\Left{\text{Left}}
\def\Right{\text{Right}}
\def\Replace{\text{Replace}}
\def\old{\text{old}}
\def\new{\text{new}}

\def\mycup{\raisebox{-.4mm}{\text{\large U}}\;}

\begin{document}
  \section{Interactions entre passes}

  \textbf{Programmes et diffs}

  Soient $p_1 \dots p_n$ des optimisations et $\pi$ un programme. Pour abréger,
  on note $p_n \dots p_1(\pi)$ (comme un mot) le sortie de la séquence d'optis
  sur $\pi$, c'est-à-dire $(p_n \circ \dots \circ p_1)(\pi)$. S'il n'y a pas
  d'ambiguité alors $\pi$ est omis.

  Pour deux séquences d'optis $s_1$ and $s_2$, on note $\D{s_1}{s_2}$ le
  diff entre $s_2(\pi)$ et $s_1s_2(\pi)$, c'est-à-dire le diff produit
  par l'action de $s_1$ sur le programme déjà optimisé par $s_2$. On note
  $\cdot$ la séquence vide.

  \textbf{Interactions}

  On veut alors comparer des diffs pour savoir si deux optimizations $p$ et $q$
  interagissent sur le même programme. On définit deux types d'interactions:

  \begin{center}
    \begin{tikzpicture}[scale=3]
      \node at (0,0) (PQ) {$\D pq$};
      \node at (1,0) (QP) {$\D qp$};
      \node at (0,1) (PB) {$\D p\cdot$};
      \node at (1,1) (QB) {$\D q\cdot$};

      \draw (PB) -- node[fill=white] {$\cap$}
                    node[above,yshift=0.2cm] {conflit} (QB);
      \draw (PB) -- node[fill=white] {$\neq$}
                    node[left,xshift=-0.2cm] {\parbox{2cm}{\raggedleft contribution de $q$ à $p$}} (PQ);
      \draw (QB) -- node[fill=white] {$\neq$}
                    node[right,xshift=0.2cm] {\parbox{2cm}{contribution de $p$ à $q$}} (QP);
    \end{tikzpicture}
  \end{center}

  \textbf{Contributions}

  Une \textit{contribution} de $q$ à $p$ se produit si $q$ génère du code qui
  est ensuite remanié par $p$. Cela revient à dire que $p$ effectue sur
  $q(\pi)$ des modifications qu'il n'effectuait pas sur $\pi$.

  Pour évaluer ce prédicat, il faut renuméroter les position de \Dpt p, qui
  sont indexées sur $\pi$, car celles de \Dt pq sont indexées sur $q(\pi)$. Il
  faut donc déplacer les numéros de positions de \Dpt p suivant les insertions
  et suppressions faites par $q$. Cette opération s'appelle \textit{rebasage}
  et est là aussi courante dans les gestionnaires de version. Elle n'est
  définie de façon unique que si $p$ et $q$ ne sont pas en conflit.

  Il convient de noter qu'une partie des modifications de \Dpt p pourrait ne
  pas être présente dans \Dt pq si $q$ a supprimé les positions où elles se
  produisent. Toutefois cela serait un conflit ; on a donc nécessairement tout
  \Dpt p dans \Dt pq. La contribution est donc notée $\Dp p \neq \D pq$.

  \textbf{Lien avec la commutativité}

  On dit que $p$ et $q$ commutent si $pq(\pi) = qp(\pi)$. Cela revient à
  \[ \Dp p \circ \D qp = \Dp q \circ \D qp. \]
  S'il n'y a ni conflit ni contribution entre $p$ et $q$, alors elles
  commutent. En effet l'absence de contribution revient à avoir $\D pq = \Dp p$
  et $\D qp = \Dp q$. La commutativité se ramène donc à
  \[ \Dp p \circ \Dp q = \Dp q \circ \Dp p. \]
  Or il n'y a pas de conflit entre $p$ et $q$, donc la fusion des deux diffs
  est définie de façon unique. La composition commute donc, d'où l'égalité.

  % Il y a des situations où $p$ et $q$ commutent mais contribuent l'un à
  % l'autre, par exemple :

  % There are situations where $p$ and $q$ commute but they contribute to each
  % other, for instance:
  %   \[ \left\{ \begin{array}{l}p(a) = b \\ p(b) = c \end{array}\right.
  %      \quad\quad
  %      \left\{ \begin{array}{l}q(a) = b \\ q(b) = c \end{array}\right. \]

  Il y a des situations où $q$ et $q$ commutent mais sont en conflit, par
  exemple avec le système de réécriture :
    \[ p(a) = b \quad\quad q(a) = b \]
  Ce genre de commutation ne montre pas une indépendance entre $p$ et $q$, au
  contraire. On considère donc ça comme une interaction, ce qui de toute façon
  ne fait que surestimer la quantité d'interactions. C'est sound.

  %

  \newpage

  %

  \section{Description des algorithmes de llvm-diff}

  Tout est dans \texttt{/llvm/tools/llvm-diff/DifferenceEngine.cpp}.

  \textbf{Unification triviale de deux blocs :}
  \texttt{diff(BasickBlock *L, BasicBlock *R)}.

  \begin{itemize}
    \item Prendre toutes les instructions dans l'ordre et les unifier une par
          une. Les matchings entres les instructions sont stockés dans
          \texttt{TentativeValues}.
    \item Si l'unification progresse jusqu'à la fin du bloc, on unifie tout
          pour de bon.
    \item Si des instructions diffèrent avant la fin du bloc,
          \texttt{TentativeValues} est vidé et on passe sur l'unification non
          triviale.
  \end{itemize}

  \textbf{Unification non triviale de deux blocs :}
  \texttt{runBlockDiff()}.

  \begin{itemize}
    \item Calcule la distance de Levenshtein entre les deux blocs. Une
          suppression correspond à un \texttt{DC\_Left} tandis qu'une insertion
          correspond à un \texttt{DC\_Right}. Ces deux opérations ont un coût
          fixé à 2.
    \item Unifie de façon gloutonne et laisse \texttt{TentativeValues} se
          remplir pour chaque match trouvé, et s'autoriser à unifier la même
          instruction plusieurs fois.

          \FIXME{} Cela unifie des valeurs pas nécessairement identifiables
          et crée des erreurs d'\texttt{assert()} lorsque le chemin est
          déroulé.

    \item Déroule le chemin et renvoie un optimal en distance de Levensthein
          sur l'ensemble des renommages... sauf si une erreur se produit.
  \end{itemize}

  %

  \newpage

  %

  \section{Définitions uniques}

  \subsection*{Représentation intermédiaire LLVM}

  On s'intéresse uniquement à des fonctions. La représentation intermédiaire
  d'une fonction est vue comme un graphe de flot de contrôle dont les n\oe{}uds
  sont des blocs basiques identifiés par un nom, et dont les contenus sont
  comparés à $\alpha$-équivalence près.

  On formalise l'idée d'un bloc $\beta$ par un ensemble de lignes muni d'un
  ordre total $\le_\beta$ donnant l'ordre des lignes. (C'est plus souple dit
  comme ça qu'avec une séquence.)

  \subsection*{Format du diff}

  Le diff de deux programmes a deux niveaux : celui des blocs basiques et celui
  du code à l'intérieur d'un bloc basique commun. Il résulte d'une unification
  entre la structure du graphe de flot de contrôle, et est composé de
  suppressions, ajouts, et éditions de blocs basiques.

  Le type des diffs est défini par
  \[ D \equiv \{ \txt{Remove} \beta ~|~ \text{Add} ~|~
     \txt{Diff} \beta~\delta,~\dots \}. \]
  \FIXME{}
  Les contenus des blocs insérés ou supprimés ne sont pas retenus. Les blocs
  insérés sont toujours considérés comme ayant une identité nouvelle et jamais
  unifiés entre deux diffs car il faudrait étendre l'algorithme. Seuls les
  anciens noms des blocs supprimés et modifiés compte.

  Pour chaque bloc modifié, on adjoint un diff de son contenu, qui se calcule
  avec une liste d'intervalles maximaux soit communs, soit présents uniquement
  à gauche (supprimés par le patch), soit présents uniquement à droite (ajoutés
  par le patch). Cette liste est choisie de façon à maximiser le nombre de
  lignes communes.

  \begin{figure}[H]
    \begin{center}
      \begin{tikzpicture}[xscale=1.3,yscale=0.3]
        \draw (1,4) node {\textbf{Original}};
        \draw (3,4) node {Type};
        \draw (5,4) node {\textbf{New}};

        \draw (0,0) rectangle node{Left $L$} ++(2,2);
        \node (RM) at (3,1) {Remove};
        \draw[->] (RM) -- (2,1);

        \draw[pattern=north east lines] (0,-2) rectangle ++(6,1);

        \draw (4,-5) rectangle node{Right $R$ $C$} ++(2,2);
        \node (IN) at (3,-4) {Insert};
        \draw[->] (IN) -- (4,-4);

        \draw[pattern=north east lines] (0,-7) rectangle ++(6,1);

        \draw (0,-10) rectangle node{$L$} ++(2,2);
        \draw (4,-10) rectangle node{$R$} ++(2,2);
        \draw[->] (2,-9) -- node[fill=white] {Replace} ++(2,0);
      \end{tikzpicture}
    \end{center}

    \caption{Extrait de la comparaison de deux programmes.}
  \end{figure}

  Le diff contient alors l'ensemble des blocs Left, pour lesquels on indique
  les ligne supprimées, des blocs Right, pour lesquels on indique les lignes
  insérées et leur position, et des blocs Replace, avec les anciennes et
  nouvelles lignes. La position d'un bloc Right est notée par le contexte (ou
  <<coupure>>) $C$ qui est l'ensemble des lignes du programme source qui
  précèdent le bloc inséré.

  Le type des diffs de blocs est noté $B$ et se restreint aux intervalles pris
  maximaux dans le bloc source $\beta$ : on note $B_\text{max}$ le prédicat de
  maximalité.

  \[ B \equiv \{ \delta \in (\Left~L ~|~ \Right~R~C ~|~ \Replace~L~R)^+ :
     B_\text{max}(\beta, \delta) \}\]

  \textbf{Proposition.} \textit{Pour un ensemble de lignes communes fixé, le
  diff d'un bloc est unique.}

  Soient $\beta_\pi$ et $\beta_\rho$ deux blocs, et $A \subseteq \beta_\pi \cap
  \beta_\rho$. Il existe une unique façon de partitionner $A$ en intervalles
  maximaux dans $\beta_\pi$ et $\beta_\rho$. (La clé est que deux intervalles
  sont fusionnables ssi ils sont adjacents dans les deux programmes.) On note
  encore $A = \{ A_1 \dots A_n \}$ cette partition, ordonnée par l'ordre
  commun.

  Soit $0 \le i \le n$, on note $L_i$ l'intervalle de $\beta_\pi$ situé entre
  $A_i$ et $A_{i+1}$, et $R_i$ celui de $\beta_\rho$. Le diff doit alors être
  \[ \{ f(L_i, R_i, C_i) : L_i \cup R_i \neq \varnothing \} \]
  avec
  \[ f(L, R, C) = \left\{ \begin{array}{ll}
     \Left~L      & \text{ si } R = \varnothing \\
     \Right~R~C   & \text{ si } L = \varnothing \\
     \Replace~L~R & \text{ sinon} \\
     \end{array}\right. \]
  où $C_i = \bigcup_{j < i} A_j$.

  $\square$

  On note $\old(\delta)$ et $\new(\delta)$ l'ensemble des intervalles retirés
  et ajoutés produits par $\delta$ :
  \[ \begin{aligned}
       \old(\delta)
       &= \{ L : \Replace~L~R \in \delta \vee \Left~L \in \delta \} \\
       \new(\delta)
       &= \{ R : \Replace~L~R \in \delta \vee \Right~R~C \in \delta \} \\
     \end{aligned} \]

  \subsection*{Application d'un patch}

  Étant donné un bloc $\beta$ et un diff $\delta$, on dit que $\beta'$ est un
  patch de $\beta$ par $\delta$ si:

  \begin{enumerate}
    \item[$(P_1)$]
          L'ordre de $\beta$ est préservé dans $\beta'$ :
          \[ \left( \le_{\beta'} \right)_{| \beta \cap \beta'} =
             \left( \le_\beta \right)_{| \beta \cap \beta'}. \]
    \item[$(P_2)$]
          Les intervalles supprimées par $\delta$ sont absents de $\beta'$ :
          \[ \forall L \in \old(\delta), \beta' \cap L =\varnothing. \]
    \item[$(P_3)$]
          Les nouveaux intervalles de $\delta$ sont des intervalles de
          $\beta'$ :
          \[ \forall R \in \new(\delta), R \text{ est un intervalle pour }
             \le_{\beta'}. \]
    \item[$(P_4)$]
          La position des lignes insérées par $\delta$ par rapport à $\beta$
          est préservée :
          \[ \forall (\Right~R~C) \in \delta,
             \{ \ell \in \beta' : \ell \le_{\beta'} R) = C \cap \beta'. \]
    \item[$(P_5)$]
          La position des lignes remplacées est préservée :
          \[ \forall (\Replace~L~R) \in \delta,
             \forall \ell \in \beta \cap \beta',
             (\ell \le_\beta L \iff \ell \le_{\beta'} R). \]
  \end{enumerate}

  \textbf{Proposition.} \textit{Il existe un unique patch de $\beta$ par
  $\delta$ ayant pour ensemble de lignes}
    \[ \beta' = \beta~\setminus~\bigcup \old(\delta)
                     ~\cup     ~\bigcup \new(\delta). \]

  L'ensemble des lignes est fixé, l'ordre des éléments de $\beta$ dans $\beta'$
  doit être égal à celui de $\beta$, et tous les intervalles insérés doivent
  rester des intervalles.

  Seule la position des blocs insérés peut varier, or $(P_4)$ et $(P_5)$
  garantissent leur unicité. En effet, l'unique ligne après laquelle il est
  légal d'insérer $\Right~R~C$ est
  \[ \text{max}_{\beta'}~(C \cap \beta'). \]
  et l'unique ligne après laquelle il est légal d'insérer $\Replace~L~R$ est
  \[ \text{max}_{\beta'}~\{ \ell \in \beta \cap \beta' : \ell \le_\beta L \}. \]
  $\square$

  \subsection*{\FIXME{} Congruence de diffs}

  Il faudrait unifier les blocs ajoutés dans chacun des deux diffs pour
  vérifier que les contenus correspondent. Mais c'est tordu car ça dépend de si
  les blocs ajoutés ont la même position dans le CFG... et peut-être de s'ils
  le sont par les mêmes instructions.

  \subsection*{Conflit}

  Deux diffs $\Delta_1$ et $\Delta_2$ sont en conflit si :

  \begin{itemize}
    \item[$(i)$] L'un d'entre eux supprime un bloc que l'autre modifie, ou
    \item[$(ii)$] Les deux induisent sur le même bloc $\beta$ des diffs
                  $\delta_1$ et $\delta_2$ qui sont en conflit.
  \end{itemize}

  Deux diffs d'un même bloc $\delta_1$ et $\delta_2$ sont en conflit si :

  \begin{itemize}
    \item[$(i)$]   L'un deux remplace un bloc $L$ et l'autre supprime une
                   partie de $L$ :
                   \[ \Replace~L~\_ \in \delta_1 \wedge L \cap \bigcup
                      \old(\delta_2) \neq \varnothing, \text{ou} \]
    \item[$(ii)$]  L'un deux remplace un bloc $L$ et l'autre insère à
                   l'intérieur de $L$ :
                   \[ \Replace~L~\_ \in \delta_1 \wedge \Right~R~C \in
                      \delta_2 \wedge C \cap L \notin \{ \varnothing, L \},
                      \text{ou} \]
    \item[$(iii)$] Les deux insèrent au même endroit après suppression :
                   \[ \Replace~\_~\ell_1 \in \delta_1 \wedge \Replace~\_~\ell_2
                      \in \delta_2 \wedge \forall \ell \in \beta \cap \beta',
                      (\ell \le_\beta \ell_1 \iff \ell \le_\beta \ell_2). \]
  \end{itemize}

  \subsection*{Union de patchs sur un bloc}

  Soit $\beta$ un bloc, et $\delta_1$ et $\delta_2$ deux patchs sur $\beta$. On
  note $\beta'$ l'ensemble
  \[ \beta~\setminus~\bigcup \old(\delta_1 \cup \delta_2)
          ~\cup     ~\bigcup \new(\delta_1 \cup \delta_2) \]
  qui est l'ensemble des lignes que l'on veut voir apparaître dans le résultat
  d'une fusion.

  \textbf{Proposition.} \textit{Si $\delta_1$ et $\delta_2$ ne sont pas en
  conflit alors il existe un unique patch de $\beta$ par $\delta_1$ et
  $\delta_2$ ayant pour ensemble de lignes $\beta'$.}

  \FIXME{}

  $\square$

  \subsection*{\FIXME{} Rebasage et contributions}

  Très casse-pieds à cause du fait que les deux sources n'ont pas les mêmes
  noms d'instructions. Nécessite la congruence.

\end{document}
