From 61e96cd04cf67182f81330cfbb76b9b2c5c7b892 Mon Sep 17 00:00:00 2001 From: Pierre Guillou Date: Tue, 11 Feb 2014 11:42:57 +0100 Subject: [PATCH] added content of Serge Guelton's thesis transformations glossary --- pipstransfo.tex | 153 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 153 insertions(+) diff --git a/pipstransfo.tex b/pipstransfo.tex index e69de29..4cef713 100644 --- a/pipstransfo.tex +++ b/pipstransfo.tex @@ -0,0 +1,153 @@ +\documentclass[pdftex, a4paper, 11pt]{report} + +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +\usepackage[english]{babel} + +\usepackage{listings} +\usepackage{hyperref} + + +\title{PIPS - List of code transformations} + + + +\begin{document} + + +\chapter{List of Pips transformations} + +\section{Memory allocation alteration} + +\section{Loop transformations} + +\section{Inter-procedural transformations} + +\section{Base blocs transformations} + +\section{Dead code removal} + + + + +\begin{description} +\item[loop unrolling]{ + is a loop transformation. Unrolling a loop by a factor of $n$ consists in the substitution of a loop + body by itself, replicated $n$ times. A prelude and/or postlude are + added to preserve the number of iteration.} + +\item[inlining]{ + is a function transformation. Inlining a function + \texttt{foo} in its caller \texttt{bar} consists in the substitution + of the calls to \texttt{foo} in \texttt{bar} by the function body + after replacement of the formal parameters by their effective + parameters. +} + +\item[forward substitution]{ + is the process of replacing a reference read in an + expression by the latest expression affected to it.} + +\item[loop fusion]{ + is a loop transformation that replaces two loops by a single loops whose + body is the concatenation of the bodies of the two initial loops.} + +\item[loop tiling]{ + is a loop nest transformation that changes the loop execution order + through a partitions of the iteration space into + chunks, so that the iteration is performed over each chunk and in the + chunks.} + +\item[reduction detection]{ + is an analysis that identifies statements that perform a reduction over a + variable.} + +\item[parallelism detection]{ + is a common name for analysis that detect if a loop can be run in parallel.} + +\item[parallelism extraction]{ + is a common name for code transformations that modifies loop nest to make it legal to + run them in parallel.} + +\item[directive generation]{ + is a common name for code transformations that annotate the code with directives.} + +\item[constant propagation]{ + is a pass that replaces a variable by its value when this value is + known at compile time.} + +\item[instruction selection]{ + is the process of mapping parts of the IR to machine instructions.} + +\item[goto elimination]{ + is the process of replacing \texttt{goto} instructions by a hierarchical control flow + graph.} +\item[outlining]{ + is the process of extracting part of a function body into a new function + and replacing it in the initial function by a function call.} + +\item[common subexpression elimination]{ + is the process of replacing similar expressions by a variable that holds + the result of their evaluation.} + +\item[loop interchange]{is a loop transformation that permutes two + loops from a loop nest.} + +\item[loop unswitching]{is a loop transformation that replaces a + loop containing a test independent from the loop execution by a test + containing the loop without the test in both true and false branch.} + +\item[statement isolation]{is the process of replacing all + variables referenced in a statement by newly declared variables. A + prologue + and an epilogue are added to copy old variable values to new variable, back + and forth.} + +\item[dead code elimination]{is the process of pruning from a + function all the statements whose results are + never used.} + +\item[array linearization]{is the process of converting + multidimensional array into unidimensional arrays, possibly with a + conversion from array to pointer.} + +\item[privatization]{is the process of detecting variables that + are private to a loop body, i.e.\ written first, then read.} + +\item[loop normalization]{is a loop transformation that changes + the loop initial increment value or the loop range to enforce certain values, generally + 1.} + +\item[iteration clamping]{is a loop transformation that extends + the loop range but guards the loop body with the former range.} + +\item[flatten code]{is the process of pruning a function body from + declaration blocks so that all declarations are made at the top level.} + +\item[strength reduction]{is the process of replacing an operation + by an operation of lower cost.} + +\item[split update operator]{is the process of replacing an update + operator by its expanded form.} + +\item[n address code generation]{is the process of splitting + complex expression in simpler ones that take at most $n$ operands.} + +\item[memory footprint reduction]{is the process of tiling a loop + to make sure the iteration over the tile has a memory footprint bounded by + a given value.} + +\item[redundant load-store elimination]{is an inter procedural transformation + that optimizes data transfers by delaying and merging them.} + +\item[invariant code motion]{is a loop transformation that moves outside + of the loop + the code from its body that is independent from the iteration.} + + + +\item[loop rerolling]{finds manually unrolled loop and replace + them by their non-unrolled version.} +\end{description} + +\end{document} -- 2.20.1