LoopOptTutorial.tex

% !TeX encoding = UTF-8
% !TeX program = lualatex
% !TeX spellcheck = en_US


\documentclass[presentation,english,aspectratio=169]{beamer}
\include{macros}

\author[Author, Another] % {optional, use only with lots of authors
       {Kit Barton\inst{1} \and \\
        Johannes Doerfert\inst{2} \and \\
        Hal Finkel\inst{2} \and \\
        Michael Kruse\inst{2} \and \\
        Ettore Tiotto\inst{1}}

% Give the names in the same order as they appear in the paper.
% Use the \inst{?} command only if the authors have different
% affiliation.
\institute[IBM Canada and ANL] % (optional, but mostly needed)
{
  \inst{1}
  IBM Canada\\
  \inst{2}
  Argonne National Laboratory
}

% Pick the date.
% Hard code it or pick a floating date based on day the PDF was built.
% Can also be a string
%\date[August 15, 2019]{Name of Conference here}
\date{October 23, 2019}

\title{Writing Loop Optimizations in LLVM}

% Autogenerated by org export to beamer.tex file
\hypersetup{
 pdfauthor={Kit Barton},
 pdftitle={Beamer Template},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={},
 pdflang={English}}

%\subject{Theoretical Computer Science}
% This is only inserted into the PDF information catalog. Can be left
% out.



% If you have a file called "university-logo-filename.xxx", where xxx
% is a graphic format that can be processed by latex or pdflatex,
% resp., then you can add a logo as follows:

\pgfdeclareimage[height=0.5cm]{ibm-logo}{figures/IBMLogo}
\pgfdeclareimage[height=0.5cm]{anl-logo}{figures/anl-symbol} % MK: Feel free to replace with smaller logo
\logo{\pgfuseimage{anl-logo}\hspace*{.9\linewidth}\pgfuseimage{ibm-logo}}

\setbeamercovered{transparent}

\begin{document}

% Create the title page
\begin{frame}
  \titlepage
\end{frame}

% Create an outline slide
\begin{frame}{Outline}
  \tableofcontents
  % You might wish to add the option [pausesections]
\end{frame}

% Create a section; comment out if not desired.
\section{Terminology}
\label{sec:terminology}

\begin{frame}[label={sec:org8787e08}]{Loop Representation in LLVM}

  % KB: I will clean this slide up and make it into a proper beamer slide, with
  % animations, if everyone is OK with how it looks.
  \includegraphics[width=\textwidth]{figures/LoopRepresentation.pdf}
\end{frame}


\begin{comment}
\begin{frame}[label=loopnormalform,fragile]{Canonical Loop Form} %MK
%%\framesubtitle{MK: Feel free to re-use/eliminate this slide; maybe it's useful}
\begin{columns}
\begin{column}{0.6\textwidth}
\begin{itemize}
\item Loop identified by header
\item Preheader
\item Single backedge/latch
\item Exits only from loop
\item Loop-rotated form\\(at least one iteration / loop guard)
    \begin{itemize}
    \item Can hoist invariant loads
    \end{itemize}
\item Loop-Closed SSA

%\item Responsible passes
%\begin{itemize}
%\item LoopRotate
%\item LoopSimplify
%\item IndVarSimplify
%\item LCSSA
%\end{itemize}
\end{itemize}


\end{column}
\begin{column}{0.4\textwidth}
\begin{tightcenter}
\begin{scaleenv}{0.7}
\begin{tikzpicture}
\tikzset{tight/.style={inner sep=0pt,outer sep=0pt,minimum size=0pt}}
\tikzset{invisible/.style={draw=none,fill=none,text=white}}

\tikzset{node/.style={line width=1.2pt,rounded corners,bottom color=white,shading angle=15,drop shadow}}
\tikzset{bb/.style={node,draw=teal,top color=teal!50}}

\graph [layered layout,edges={->},sibling distance=2cm,level distance=12mm]{
    enter1[as={}];
    enter2[as={}];
    guard[bb,as={Guard}];
    preheader[bb,as={Preheader}];
    header[bb,as={Header}];
    exiting[bb,as={Exiting}];
    exit[bb,as={Exit}];
    merge[bb,as={\phantom{MMM}}];
    latch[bb,as={Latch}];
    afterexit[as={}];
    {[edge={draw=none}]
      header->latch,
      latch->exiting
    };
};

\path (latch) edge[draw=none,decorate,decoration={text along path,text={Backedge}},out=90,in=180] (header);
\path (exiting) edge[->,in=270,out=180] (latch);
\end{tikzpicture}
\end{scaleenv}
\end{tightcenter}
\end{column}
\end{columns}
\end{frame}
\end{comment}


\begin{frame}[label={sec:orgac3eb21}]{Other Terminology}
  \begin{itemize}
  \item Loop predecessor
  \item Backedge taken count
  \item Iteration count
  \item Loop guard
  \item Irreducible loops (not covered)
  \end{itemize}
  Documented at: \url{https://llvm.org/docs/LoopTerminology.html}
\end{frame}

%% \begin{frame}[label={sec:rotated}]{Rotated Loops}
%%   \includegraphics[width=\textwidth]{figures/LoopRotationSimplified.pdf}
%% \end{frame}

\begin{frame}[fragile,shrink=0]{Rotated Loops}
  \begin{columns}
    \begin{column}{0.75\textwidth}
      \begin{itemize}
      \item Convert a loop into a \mintinline{c}{do/while} style loop
      \item Canonicalize loop latch to have a single predecessor
      \end{itemize}
    \end{column}
    \begin{column}<2->{0.25\textwidth}
      \begin{minted}[frame=single,fontsize=\tiny]{c}
int A[100];
int B[100];
void example() {
  for (int i = 0; i < 100; ++i)
    A[i] = i;
}
      \end{minted}
    \end{column}
  \end{columns}
  \begin{columns}
    \begin{column}<3->{0.5\textwidth}
      \includegraphics<3->[width=\textwidth]{examples/LoopRotate/loop-rotate-example-before-rotate.pdf}
    \end{column}
    \begin{column}<4->{0.5\textwidth}
      \includegraphics<4->[width=\textwidth]{examples/LoopRotate/loop-rotate-example-after-rotate.pdf}
    \end{column}
  \end{columns}
\end{frame}

%% \Begin{frame}[label={sec:rotated}]{Rotated Loops - Guarded Loops}
%%   \includegraphics[width=\textwidth]{figures/LoopRotationGuardedSimplified.pdf}
%% \end{frame}

\begin{frame}[fragile,shrink=10]{Rotated Loops - Guarded Loops}
  \begin{columns}
    \begin{column}{0.75\textwidth}
      \begin{itemize}
      \item When the compiler cannot prove loop body will execute at least once,
        it inserts a \emph{guard}
      \item It also inserts a loop epilogue, that will be executed once after
        the body is finished executing
      \end{itemize}
    \end{column}
    \begin{column}<2->{0.25\textwidth}
      \begin{minted}[frame=single,fontsize=\tiny]{c}
int A[100];
int B[100];
void example(long N) {
  for (long i = 0; i < N; ++i)
    A[i] = i;
}
      \end{minted}
    \end{column}
  \end{columns}
  \begin{columns}
    \begin{column}<3->{0.5\textwidth}
      \includegraphics<3->[width=\textwidth]{examples/LoopRotate/loop-rotate-example2-before-rotate.pdf}
    \end{column}
    \begin{column}<4->{0.5\textwidth}
      \includegraphics<4->[width=\textwidth]{examples/LoopRotate/loop-rotate-example2-after-rotate.pdf}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}[label={sec:SimplifyForm}]{Simplify Form}
  \begin{itemize}
    \item Loop has a preheader
    \item Loop has a latch
    \item Loop has dedicated exits (no exit block for the loop has a predecessor
      that is outside the loop)
  \end{itemize}
\end{frame}


\begin{frame}[fragile,label={sec:lcssa}]{Loop-Closed SSA Form}
\begin{tikzpicture}
\tikzset{indent/.style={xshift=5mm}}]
\tikzset{lcssa/.style={subgraph text none,bottom color=teal!30,top color=teal!15,shading angle=15,rounded corners,draw=teal,very thick}}
\tikzset{ssa/.style={subgraph text none,bottom color=red!30,top color=red!15,shading angle=15,rounded corners,draw=red,very thick}}

\matrix[matrix of nodes,nodes={anchor=west,inner ysep=0.4ex}] {
                      \llvminline{loop:}                                                       \\
|(indvar) [indent]|     \llvminline{%indvar = phi i64 [%indvar.next, %loop], [0, %preheader]}  \\[1.5ex]
|(sum) [indent]|        \llvminline{%sum = phi i64 [%sum.next, %loop], [0, %preheader]}        \\
|(sumnext) [indent]|    \llvminline{%sum.next = add i64 %sum, %indvar}                         \\[1.5ex]
|(indvarnext) [indent]| \llvminline{%indvar.next = add i64 %indvar, 1}                         \\
|(cond) [indent]|       \llvminline{%cond = icmp ne i64 %indvar.next, 64}                      \\
|(br) [indent]|         \llvminline{br i1 %cond, label %loop, label %exit}                     \\[1.5ex]
 
                     \llvminline{exit:}        \\
|(sumresult) [indent,visible on=<2->]| \llvminline{%sum.result = phi i64 [%sum.next, %loop]}        \\[3ex]
\node[anchor=west,inner ysep=0.4ex,indent](dots1){\dots};
\node[right=0pt of dots1](use){\texttt{\alt<1>{\%sum.next}{\%sum.result}}}; 
\node[right=0pt of use]{\dots};  \\
};

\begin{pgfonlayer}{background}
\node[fit={(sum) (sumnext)},ssa] {};
\node<1>[fit={(use)},ssa] {};
\node<2->[fit={(sumresult)},lcssa] {};
\node<2->[fit={(use)},lcssa] {};
\end{pgfonlayer}
\end{tikzpicture}%
\begin{locate}<only@3->[anchor=center]{page cs:x=0.5,y=0.5}
\begin{minipage}{0.75\textwidth}
\begin{block}{Workflow}
\begin{itemize}
\item Added by LCSSA pass
    \begin{itemize}
    \item Automatically added by LoopPassManager
    \end{itemize}
\item Must be preserved by loop passes
    \begin{itemize}
    \item Helper: \cppinline{llvm::formLCSSA(Loop &L, ...)}
    \end{itemize}
\item Removed again by InstCombine
\end{itemize}
\end{block}
\bigskip
\begin{exampleblock}{Advantages}
\begin{itemize}
\item Loop transformations change only the LCSSA node
\item No need to pass scope to ScalarEvolution 
\end{itemize}
\end{exampleblock}
\end{minipage}
\end{locate}
\end{frame}


\begin{frame}{Available Infrastructure} %MK
\begin{columns}
\begin{column}[t]{0.45\textwidth}
\begin{itemize}
\item Analysis passes
\begin{itemize}
\item \textbf<2->{LoopInfo (LoopAnalysis)}
\item MemoryDependenceAnalysis
\item LoopAccessAnalysis
\item (Predicated)ScalarEvolution
\item PolyhedralInfo
\item DivergenceAnalysis
\item BlockFrequencyInfo
\end{itemize}
\end{itemize}
\end{column}


\begin{column}[t]{0.45\textwidth}
\begin{itemize}
\item Canonicalization passes
\begin{itemize}
\item LoopSimplifyCFG
\item LoopInstSimplifyPass
\item \textbf<2->{LoopSimplify}
\item LoopRotate
\item \textbf<2->{LoopClosedSSA (LCSSA)}
\item IndVarSimplify
\end{itemize}
\end{itemize}
\end{column}
\end{columns}

\bigskip

\begin{columns}
\begin{column}[t]{0.45\textwidth}
\begin{itemize}
\item Utilities
\begin{itemize}
\item IVUsers
%\item LoopInterchangeLegality
%\item LoopInterchangeCodeModel
%\item LoopVectorizationCostModel
%\item UnrolledInstAnalyzer
\item LoopVersioning
\item SCEVExpander
\item OptimizationRemarkEmitter
%\iem LazyBlockFrequencyInfoPass
\item IrreducibleGraph
\end{itemize}
\end{itemize}
\end{column}



\begin{column}[t]{0.45\textwidth}
\begin{itemize}
\item Verification
\begin{itemize}
\item LCSSAVerificationPass
\end{itemize}
\end{itemize}
\end{column}
\end{columns}

\end{frame}

\section{Loop Optimization Pipeline}

\begin{comment}
%MK: Not sure whether I am going to need this; for now it's for testing whether tikzpicture works
\begin{frame}[fragile]{Clang/LLVM/Polly Compiler Pipeline} %MK
\begin{resizepar}
\begin{tikzpicture}
\tikzset{tight/.style={inner sep=0pt,outer sep=0pt,minimum size=0pt}}
\tikzset{node/.style={draw=teal,line width=1.2pt,rounded corners,top color=teal!50,bottom color=white,shading angle=15,drop shadow}}
\tikzset{supernode/.style={subgraph text none,bottom color=teal!30,top color=teal!05,shading angle=15,rounded corners}}
\tikzset{edge/.style={->}}

\graph[layered layout,edges={edge,rounded corners},level sep=5mm,sibling sep=10mm]{
	c[as={\minibox{\texttt{void f() \{}\\\hspace*{4mm}\texttt{for (int i=...)}\\\hspace*{4mm}\dots}},grow=right,draw,shape=file,fill=white,label={source.c}];
	ir[as={IR},shape=file,draw,fill=white,nudge=(up:10mm)];
	asm[as={Assembly},shape=file,draw,fill=white];

	clang [subgraph text none,label={[font=\Large\sffamily]above:Clang}] // [sibling sep=2mm,grow=down,layered layout] {
		lexer [as={Lexer},node];
		parser [as={Parser},node,grow=down];
		preprocessor [as={Preprocessor},node];
		sema [as={Semantic Analyzer},node];
		codegen [as={IR Generation},node];
		%
		lexer->preprocessor->parser->sema->codegen;
	};

	llvm [subgraph text none,label={[font=\Large\sffamily]above:LLVM}] // [sibling sep=2mm,grow=down,layered layout] {
		canonicalization [as={Canonicalization passes},node];
		loopopts [as={Loop optimization passes},node];
		polly [as={Polly},node];
		vectorization [as={LoopVectorize},node];
		latepasses [as={Late Mid-End passes},node];
		backend [as={Target Backend},node];
		%
		canonicalization->loopopts->vectorization->latepasses->backend;
		loopopts->polly->vectorization;
	};

	c->[in=180]lexer;
	codegen->[out=0,in=-90]ir;
	ir->[out=90,in=180]canonicalization;
	backend->[out=0,in=-90]asm;
};

\begin{pgfonlayer}{background}
\node[tight,fit={(clang)},supernode]{};
\node[tight,fit={(llvm)},supernode]{};
\end{pgfonlayer}

%	\path (preprocessor) edge[edge,densely dotted,bend left=50,draw=blue!50!black] node[midway,right,font=\ttfamily,blue!50!black] {\#pragma} (sema);
%	\path (preprocessor) edge[edge,densely dotted,bend right=80,draw=blue!50!black] node[pos=0.7,left,font=\ttfamily,blue!50!black] {\#pragma} (codegen);

	\path (codegen) edge[edge,dashed,bend right=80,draw=blue!50!black,postaction={decorate,decoration={text along path,text={|\color{blue!50!black}|Loop metadata},raise=-1.7ex,pre=moveto,pre length=13mm}}] (ir);
	\path (ir) edge[edge,dashed,draw=blue!50!black] (loopopts);
%	\path (ir) edge[edge,dashed,draw=blue!50!black] (polly);1
	\path (ir) edge[edge,dashed,draw=blue!50!black,bend right=10] (vectorization);
%	\path (polly) edge[edge,dashed,draw=blue!50!black,bend right=10] (vectorization);
\end{tikzpicture}
\end{resizepar}
\end{frame}
\end{comment}




\begin{frame}[fragile,shrink=5]{Loop Transformation Passes} %MK
%\begin{itemize}
%\item Transformation passes:
\begin{columns}
\begin{column}[t]{0.5\textwidth}
\makeatletter
\patchcmd{\@listI}{\itemsep3\p@}{\itemsep0em}{}{}
\makeatother
\begin{itemize}
\item \textbf<2->{LoopSinkPass}
\item LoopDataPrefech
\item \textbf<2->{LoopLoadElimination}
\item LoopFuse
\item \textbf<2->{LoopDistribution}
\item \textbf<2->{LoopVectorize}
\item \textbf<2->{LoopInvariantCodeMotion (LICM)}
\item VersioningLICM
\item \textbf<2->{LoopIdiomRecognize}
\item \textbf<2->{LoopDeletion}
\item LoopExtractor
\item LoopDataPrefetch
\item Polly
\end{itemize}
\end{column}
\begin{column}[t]{0.5\textwidth}
\makeatletter
\patchcmd{\@listI}{\itemsep3\p@}{\itemsep0em}{}{}
\makeatother
\begin{itemize}
\item LoopReroll
\item LoopStrengthReduction
\item InductiveRangeCheckElimination (IRCE)
\item LoopUnrollAndJam
\item Loop(Full/Partial)Unroll
\item LoopPredication
\item GuardWidening
\item \textbf<2->{(Simple)LoopUnswitch}
\item LoopInterchange
\item MachinePipeliner/SwingSchedulerDAG
\item StructurizeCFG 
\item WebAssemblyFixIrreducibleControlFlow
\end{itemize}
\end{column}
\end{columns}
\end{frame}











\begin{frame}[fragile]{Default Loop Pipeline} %MK
\vspace*{-8mm}
\begin{columns}
\begin{column}[t]{0.2\textwidth}
\begin{tightcenter}
\hspace*{-5mm}{\tiny Legacy PassManager}
\begin{scalepar}{0.45}
\begin{tikzpicture}
\tikzset{tight/.style={inner sep=0pt,outer sep=0pt,minimum size=0pt}}
\tikzset{looppass/.style={draw=teal,line width=1.2pt,rounded corners,top color=teal!50,bottom color=white,shading angle=15,drop shadow}}
\tikzset{nodenoop/.style={draw=teal,line width=1.2pt,rounded corners,top color=gray!50,bottom color=white,shading angle=15,drop shadow}}
\tikzset{nodedisabled/.style={draw=gray,line width=1.2pt,rounded corners,top color=gray!50,bottom color=white,shading angle=15,drop shadow,text=gray}}
\tikzset{supernode/.style={subgraph text none,bottom color=teal!30,top color=teal!05,shading angle=15,rounded corners}}
\tikzset{edge/.style={->,rounded corners}}

\graph[layered layout,edges={edge},level sep=3mm]{
  codegen[looppass,as={Clang}],
  ir[as={IR},shape=file,draw,fill=white];
  LoopUnswitch[as={(Simple-)LoopUnswitch},looppass];
  LoopDeletion[looppass];
  LoopIdiom[looppass]; 
  LoopInterchange[nodedisabled]; 
  LoopFullUnroll[looppass];
  LoopReroll[nodedisabled];
  LoopVersioningLICM[nodedisabled];
  LoopDistribute[nodenoop];
  LoopVectorize[looppass];
  LoopLoadElimination[looppass]; 
  LoopUnrollAndJam[nodedisabled];
  LoopUnroll[looppass];
  WarnMissedTransformations[looppass];
  backend[as={\dots}];

  codegen -> ir -> LoopUnswitch -> LoopIdiom -> LoopDeletion -> LoopInterchange -> LoopFullUnroll -> LoopReroll -> LoopVersioningLICM -> LoopDistribute -> LoopVectorize -> LoopLoadElimination -> LoopUnrollAndJam -> LoopUnroll -> WarnMissedTransformations -> backend;
};
\end{tikzpicture}
\end{scalepar}
\end{tightcenter}
\end{column}
\begin{column}[t]{0.2\textwidth}
\begin{tightcenter}
\hspace*{-7mm}{\tiny New PassManager}
\begin{scalepar}{0.32}
\begin{tikzpicture}
\tikzset{tight/.style={inner sep=0pt,outer sep=0pt,minimum size=0pt}}
\tikzset{looppass/.style={draw=teal,line width=1.2pt,rounded corners,top color=teal!50,bottom color=white,shading angle=15,drop shadow}}
\tikzset{nodenoop/.style={draw=teal,line width=1.2pt,rounded corners,top color=gray!50,bottom color=white,shading angle=15,drop shadow}}
\tikzset{nodedisabled/.style={draw=gray,line width=1.2pt,rounded corners,top color=gray!50,bottom color=white,shading angle=15,drop shadow,text=gray}}
\tikzset{nodecallback/.style={}}
\tikzset{supernode/.style={subgraph text none,bottom color=teal!30,top color=teal!10,shading angle=15,rounded corners}}
\tikzset{edge/.style={->,rounded corners}}

\graph[layered layout,edges={edge},level sep=1mm]{
  codegen[looppass,as={Clang}],
  ir[as={IR},shape=file,draw,fill=white];
  backend[as={\dots}];
  
  % Simplification
  % LPM1
  %   LoopSimplifyPass
  %   LCSSAPass
  LoopInstSimplify[looppass];
  LoopSimplifyCFG[looppass];
  LoopRotate[looppass];
  LICM1[as={LICM},looppass];
  LoopUnswitch[as={SimpleLoopUnswitch},looppass];
  
  % SimplifyCFGPass
  % InstCombinePass
  
  % LPM2
  %   LoopSimplifyPass
  %   LCSSAPass
  % IndVarSimplify
  LoopIdiom[as={LoopIdiomRecognize},looppass]; 
  LateLoopOptimizationsEPCallbacks[nodecallback];
  LoopDeletion[looppass];
  LoopFullUnroll[looppass];
  LoopOptimizerEndEPCallbacks[nodecallback];
  
  % LPM?
  %  LoopSimplifyPass
  %  LCSSAPass
  LICM2[as={LICM},looppass];
  
  % LPM?
  %  LoopSimplifyPass
  %  LCSSAPass
  LoopDistribute[nodenoop];
  LoopVectorize[looppass];
  LoopLoadElimination[looppass]; 
  % InstCombinePass
  % SimplifyCFGPass
  % InstCombinePass
  LoopUnrollAndJam[nodedisabled];
  LoopUnroll[looppass];
  WarnMissedTransformations[looppass];
  LICM3[as={LICM},looppass];
  
  % LPM?
  %  LoopSimplifyPass
  %  LCSSAPass
  LoopSink[looppass]
  
  backend[as={\dots}];

  codegen -> ir -> LoopInstSimplify -> LoopSimplifyCFG -> LoopRotate -> LICM1 -> LoopUnswitch -> 
  LoopIdiom -> LateLoopOptimizationsEPCallbacks -> LoopDeletion -> LoopFullUnroll -> LoopOptimizerEndEPCallbacks ->
  LICM2 -> 
  LoopDistribute -> LoopVectorize -> LoopLoadElimination -> LoopUnrollAndJam -> LoopUnroll -> WarnMissedTransformations ->
  LICM3 -> 
  LoopSink -> backend;
};

\begin{pgfonlayer}{background}
\node[fit={(LoopInstSimplify) (LoopSimplifyCFG) (LoopRotate) (LICM1) (LoopUnswitch)},supernode,label={right:LPM1}](LPM1) {};
\node[tight,fit={(LoopIdiom) (LateLoopOptimizationsEPCallbacks) (LoopDeletion) (LoopFullUnroll) (LoopOptimizerEndEPCallbacks)},supernode,label={right:LPM2}](LPM2) {};
\end{pgfonlayer}

\end{tikzpicture}
\end{scalepar}
\end{tightcenter}
\end{column}
\begin{column}[t]{0.6\textwidth}
\begin{itemize}
\item<1-> Pipeline builder (Legacy/New)
    \begin{itemize}
    \item<2-> Passes enabled by switches\\
        {\tiny (UnrollAndJam)}
    \item<3-> Added passes, but do-nothing by default\\
           {\tiny (LoopDistribute; LoopVectorize, LoopUnroll if disabled)}
    \item<4-> Passes added in EP callbacks\\
          {\tiny (Polly)}
    \item<5-> Passes never added by pass builder
    \end{itemize}
\item<6-> Transformation order follows pass pipeline
    \begin{itemize}
    \item Fixpoint within \texttt{LoopPassManager} using \texttt{Updater}
    \end{itemize}
\item<7-> Non-loop passes in-between
\item<8-> Some passes are \texttt{FunctionPasse}s
\end{itemize}
\end{column}
\end{columns}
\end{frame}


\begin{comment}
\begin{frame}{Non-Loop Passes Between Loop Passes} %MK
\begin{columns}
\begin{column}{0.1\textwidth}
\begin{scalepar}{0.45}
\begin{tightcenter}
\begin{tikzpicture}
\tikzset{tight/.style={inner sep=0pt,outer sep=0pt,minimum size=0pt}}

\tikzset{scalarpass/.style={draw=none,line width=1.2pt,rounded corners,top color=gray!50,bottom color=white,shading angle=15,drop shadow}}
\tikzset{loopcanon/.style={draw=red,line width=1.2pt,rounded corners,top color=darkspringgreen!50,bottom color=white,shading angle=15,drop shadow}}
\tikzset{loopanalysis/.style={draw=none,line width=1.2pt,rounded corners,top color=teal!50,bottom color=white,shading angle=15,drop shadow}}
\tikzset{looppass/.style={draw=teal,line width=1.2pt,rounded corners,top color=teal!50,bottom color=white,shading angle=15,drop shadow}}

\tikzset{edge/.style={->,rounded corners}}

% -loops -loop-simplify -lcssa-verification -lcssa -basicaa -aa -scalar-evolution -loop-rotate -licm -loop-unswitch -simplifycfg -domtree -basicaa -aa -loops -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -instcombine -loop-simplify -lcssa-verification -lcssa -scalar-evolution -indvars -loop-idiom -loop-deletion
\graph[layered layout,edges={edge},level sep=-1mm]{
  ir[as={\dots},tight];
  SimplifyCFG1[scalarpass,as={SimplifyCFG}];
  Reassociate[scalarpass];
  LoopInfo1[loopanalysis,as={LoopInfo}];
  LoopSimplify1[loopcanon,as={LoopSimplify}];
  LCSSA1[loopcanon,as={LCSSA}];
  LoopRotate[loopcanon];
  LICM[scalarpass];
  LoopUnswitch[looppass];
  SimplifyCFG2[scalarpass,as={SimplifyCFG}];
  LoopInfo2[loopanalysis,as={LoopInfo}];
  InstCombine[scalarpass];
  LoopSimplify2[loopcanon,as={LoopSimplify}];
  LCSSA2[loopcanon,as={LCSSA}];
  IndVarSimplify[loopcanon];
  LoopIdiom[looppass];
  LoopDeletion[looppass];
  dots[as={\dots}];

  ir -> SimplifyCFG1 -> Reassociate ->  LoopInfo1 -> LoopSimplify1 -> LCSSA1 -> LoopRotate -> LICM -> LoopUnswitch -> SimplifyCFG2 -> LoopInfo2 -> InstCombine -> LoopSimplify2 -> LCSSA2 ->  IndVarSimplify -> LoopIdiom -> LoopDeletion -> dots;
};
\end{tikzpicture}
\end{tightcenter}
\end{scalepar}
\end{column}
\begin{column}{0.9\textwidth}
\begin{itemize}
\item Non-loop passes may destroy canonical loop structure
\begin{itemize}
\item SimplifyCFG removes empty loop (pre-)headers
    \begin{itemize}
    \item Keeps a list of loop headers
    \item LoopSimplifyCFG only merges blocks within loop
    \item Fixed in r343816
    \end{itemize}
\item JumpThreading skips exiting block
    \begin{itemize}
    \item Has an integrated loop header detection
    \item Makes ScalarEvolution not recognize the loop
    \item Fixed in r312664(?)
    \end{itemize}
\item Bit-operations created by InstCombine must be understood by ScalarEvolution
\item LCSSA removed
\end{itemize}

\item Analysis invalidation / Extra work in non-loop passes
\end{itemize}
\end{column}
\end{columns}
\end{frame}
\end{comment}




%% \begin{frame}[label={sec:auxdatastruct}]{Auxiliary Data Structures}
%%     \begin{itemize}
%%     \item Dominator/PostDominator trees
%%     \item Data dependence graph (DDG)
%%     \item Others??
%%     \end{itemize}
%% \end{frame}


\begin{frame}[fragile,label={sec:looppass}]{Function Pass}

\begin{block}{LoopVectorize}
\begin{minted}[fontsize=\small]{cpp}
struct LoopVectorizePass : public PassInfoMixin<LoopVectorizePass> {

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
  auto &LI = AM.getResult<LoopAnalysis>(F);
  for (auto &L : *LI) { // recursive
    simplifyLoop(L, DT, LI, SE, AC, nullptr, false);
    Worklist.push_back(&L); 
  }
  while (!Worklist.empty()) 
    processLoop(L);
  return PA:
}
\end{minted}
\end{block}
%
%\begin{block}{Loop Pass}
%\begin{minted}{cpp}
%PreservedAnalyses LoopSimplifyCFGPass::run(Loop &L, LoopAnalysisManager &AM,
%                                           LoopStandardAnalysisResults &AR,
%                                           LPMUpdater &LPMU) {
%\end{minted}
%\end{block}
\end{frame}



\begin{frame}[fragile,label={sec:looppass}]{Loop Pass vs. Function Pass}

\begin{exampleblock}<1->{Recommendation: Consider a FunctionPass First}
\begin{itemize}
\item Better maintained
\item No LoopPassManager needed
    \begin{itemize}
    \item May require adding function analyses by proxy
    \end{itemize}
\item No requirement to preserve DominatorTree,LoopAnalysis,LoopSimplify,LCSSA
\item Control over loop processing order / reprocessing behavior
\end{itemize}
\end{exampleblock}


\begin{exampleblock}<2->{Reasons to Write a LoopPass}
\begin{itemize}
\item Apply multiple passes on same loop before processing nest
\begin{itemize}
\item {\footnotesize i.a. Improved locality}
\end{itemize}
\item Share reprocessing behavior with other loop passes
\item Add pass at the Loop EP Callbacks
\item Analysis used by other loop passes
\end{itemize}
\end{exampleblock}

\begin{comment}
\begin{itemize}
\item<3-> A function pass can use loop analyses / vice versa
\item<3-> A loop pass can be added to a FunctionPassManager using \cppinline{createFunctionToLoopPassAdaptor(...)}
\end{itemize}
\end{comment}

\end{frame}



\begin{comment}
\begin{frame}[label={sec:passmanager}]{Pass Managers}
  \begin{itemize}
    \item New Pass Manager
    \item Legacy Pass Manager %% (JD: I would only mention: use the new one)
    \item Where to put loop optimizations in the loop opt pipeline (maybe on new slide)
  \end{itemize}
\end{frame}
\end{comment}

\section{Simple Loop Optimization Pass}
\begin{frame}[label=step1]{\textbf{Demo}: Basic Loop Optimization Pass using New Pass
    Manager}

  \begin{itemize}
  \item<1-> Step 1: Basic loop optimization template [https://github.com/kitbarton/llvm-project/pull/1]
  \item<2-> Step 2: Select/Filter candidate loops    [https://github.com/kitbarton/llvm-project/pull/2]
  \item<3-> Step 3: Add code to split a candidate loop [https://github.com/kitbarton/llvm-project/pull/3]
  \item<4-> Step 4: Use DomTreeUpdater to update the dominator tree [https://github.com/kitbarton/llvm-project/pull/4]
  \item<5-> Step 5: Use STATISTICS and OpmizationRemarkEmitter to report outcome [https://github.com/kitbarton/llvm-project/pull/5]
  \end{itemize}
\end{frame}

%% \begin{frame}[fragile]{Preserved Analysis in Loop Passes}
%%   \begin{columns}
%%     \begin{column}{0.45\textwidth}
%%       \begin{minted}[fontsize=\tiny,linenos]{c}
%% PreservedAnalyses llvm::getLoopPassPreservedAnalyses() {
%%   PreservedAnalyses PA;
%%   PA.preserve<DominatorTreeAnalysis>();
%%   PA.preserve<LoopAnalysis>();
%%   PA.preserve<LoopAnalysisManagerFunctionProxy>();
%%   PA.preserve<ScalarEvolutionAnalysis>();r
%%   // FIXME: What we really want to do here is preserve
%%   // an AA category, but that concept doesn't exist yet.
%%   PA.preserve<AAManager>();
%%   PA.preserve<BasicAA>();
%%   PA.preserve<GlobalsAA>();
%%   PA.preserve<SCEVAA>();
%%   return PA;
%% }
%%       \end{minted}
%%     \end{column}
%%     \begin{column}{0.45\textwidth}
%%       Need to say something here
%%     \end{column}
%%   \end{columns}
%% \end{frame}

%% \begin{frame}[label=step2]{Checking For Valid Candidates}{\textbf{Kit to do}}
%% \end{frame}

%% \begin{frame}[label=step3]{Splitting a loop using cloning}{\textbf{Ettore to do}}
%% \end{frame}

%% \begin{frame}[label=step4]{Updating data structures - dominator tree and
%%     SCEV}{\textbf{Kit to do}}
%% \end{frame}

%% \begin{frame}[label=step5]{Reporting Success and failure}{\textbf{Ettore to do}}
%% \end{frame}

%% \section{Other Useful Tools}
%% \begin{frame}[label=reports]{Reporting success and failure}
%%   \begin{itemize}
%%     \item STATISTICS
%%     \item Optimization Remark Emitter
%%   \end{itemize}
%% \end{frame}

%% \begin{frame}[label={sec:datastructs}]{Updating Data Structures}
%%     \begin{itemize}
%%       \item DominatorTreeUpdater
%%       \item SCEV
%%       \item Other??
%%     \end{itemize}
%% \end{frame}

\section{Ongoing Work}
\begin{frame}[fragile,label={sec:DepGraphs}]{Dependence Graphs}
  \begin{exampleblock}<1->{Data Dependency Graphs Theory}
  \begin{itemize}
    \item Represents data dependencies between program elements (instructions)
    \item Ideas: 
    \begin{itemize}
      \item D.J. Kuck, R.H. Kuhn, D.A. Padua, B. Leasure, and M. Wolfe (1981). Deendence Graphs and Compiler Optimizations. 
      \item J. Ferrante, K.J. Ottenstein and Joe D. Warren (1987). The Program Dependence Graph and Its Use in Optimizations.
    \end{itemize}
  \end{itemize}
  \end{exampleblock}

  \begin{exampleblock}<2->{Dependency Graphs Types}
  \begin{itemize}
    \item Data Dependence Graph (DDG): hierarchical representation, nodes that are part of an SCC grouped into pi-blocks
    \item Program Dependence Graph (PDG): capable of representing both data dependencies and control-flow dependencies
  \end{itemize}
  \end{exampleblock}
\end{frame}

\begin{frame}[fragile,label=DDGExample1]{Data Dependence Graph Example}
 \begin{minipage}[t][0.3\textheight][t]{\textwidth}
  \begin{exampleblock}{\small Loop with a loop carried data dependence}
    \begin{itemize}
      \item \tiny Example code contains a statement that has a loop carried data dependence on itself
      \item \tiny Instructions (nodes) are connected by edges to represent dependencies (def-use and memory)
      \item \tiny Def-use relations and a memory access dependency form a cycle representing the loop carried dependence.
    \end{itemize}
    \end{exampleblock}
  \end{minipage}
  \begin{minipage}[b][0.7\textheight][t]{\textwidth}
    \includegraphics[width=\textwidth]{figures/DDG1.png}
  \end{minipage}
\end{frame}

\begin{frame}[fragile,label=DDGExample2]{Data Dependence Graphs Example}
  \begin{minipage}[t][0.2\textheight][t]{\textwidth}
    \begin{exampleblock}{\small Pi Block in the data dependence graph}
    \begin{itemize}
      \item \tiny The DDG corresponding to the example contains a pi-block 
      \item \tiny The pi-block groups the nodes that participate in the dependency cycle. The resulting graph is acyclic.
    \end{itemize}
    \end{exampleblock}
  \end{minipage}
  \begin{minipage}[b][0.7\textheight][t]{\textwidth}
    \begin{figure}[h]
      \includegraphics[width=0.55\textwidth]{figures/cycle_pi.png}
    \end{figure}
  \end{minipage}
\end{frame}

\begin{frame}[label=DDGLLVM]{Data Dependence Graphs in LLVM}
  \begin{itemize}
  \item Directed Graph: D64088 (base class for various dependence graphs)
  \item Data Dependence Graph (DDG): D65350 (basic framework), D67970 (root-node), ...  
  \item Program Dependence Graph (PDG): will follow after DDG (leverage common graph builder)
  \item<2-> Potential Future Consumers for DDG/PDG:
    \begin{itemize}
    \item Loop Fission/Distribution (definetely)
    \item Loop Fusion (maybe)
    \item Consider using this infrastructure in your pass
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}[label=Questions]{Questions?}
\end{frame}

\end{document}