source: Deliverables/D6.3/report.tex @ 3120

\documentclass[11pt, epsf, a4wide]{article}

\usepackage{../style/cerco}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb} 
\usepackage[english]{babel}
\usepackage{graphicx}
\usepackage[utf8x]{inputenc}
\usepackage{listings}
\usepackage{stmaryrd}
\usepackage{url}
\usepackage{bbm}

\title{
INFORMATION AND COMMUNICATION TECHNOLOGIES\\
(ICT)\\
PROGRAMME\\
\vspace*{1cm}Project FP7-ICT-2009-C-243881 \cerco{}}

\lstdefinelanguage{matita-ocaml}
  {keywords={ndefinition,ncoercion,nlemma,ntheorem,nremark,ninductive,nrecord,nqed,nlet,let,in,rec,match,return,with,Type,try},
   morekeywords={[2]nwhd,nnormalize,nelim,ncases,ndestruct},
   morekeywords={[3]type,of},
   mathescape=true,
  }

\lstset{language=matita-ocaml,basicstyle=\small\tt,columns=flexible,breaklines=false,
        keywordstyle=\color{red}\bfseries,
        keywordstyle=[2]\color{blue},
        keywordstyle=[3]\color{blue}\bfseries,
        commentstyle=\color{green},
        stringstyle=\color{blue},
        showspaces=false,showstringspaces=false}

\lstset{extendedchars=false}
\lstset{inputencoding=utf8x}
\DeclareUnicodeCharacter{8797}{:=}
\DeclareUnicodeCharacter{10746}{++}
\DeclareUnicodeCharacter{9001}{\ensuremath{\langle}}
\DeclareUnicodeCharacter{9002}{\ensuremath{\rangle}}

\date{}
\author{}

\begin{document}

\thispagestyle{empty}

\vspace*{-1cm}
\begin{center}
\includegraphics[width=0.6\textwidth]{../style/cerco_logo.png}
\end{center}

\begin{minipage}{\textwidth}
\maketitle
\end{minipage}

\vspace*{0.5cm}
\begin{center}
\begin{LARGE}
\textbf{
Report n. D6.3\\
Final Report on User Validation}
\end{LARGE} 
\end{center}

\vspace*{2cm}
\begin{center}
\begin{large}
Version 1.0
\end{large}
\end{center}

\vspace*{0.5cm}
\begin{center}
\begin{large}
Main Authors:\\
XXXX %Dominic P. Mulligan and Claudio Sacerdoti Coen
\end{large}
\end{center}

\vspace*{\fill}

\noindent
Project Acronym: \cerco{}\\
Project full title: Certified Complexity\\
Proposal/Contract no.: FP7-ICT-2009-C-243881 \cerco{}\\

\clearpage
\pagestyle{myheadings}
\markright{\cerco{}, FP7-ICT-2009-C-243881}

\newpage

\vspace*{7cm}
\paragraph{Abstract}
xxx

\newpage

\tableofcontents

\newpage

\section{Task}
\label{sect.task}

The Grant Agreement describes deliverable D6.3 as follows:
\begin{quotation}
\textbf{Final Report on User Validation}: An articulated analysis and critics of the user validation experiences. In particular we will review the effectiveness of the techniques for cost annotation exploitement that have been employed in the project and that have been validated on simple and non trivial examples. We will also identify additional techniques that could be exploited in the middle and long term to bring the CerCo compiler to its full potentialities.

\end{quotation}

\section{Middle and Long Term Improvements}
In order to identify the middle and long term improvements, we briefly review
here the premises and goals of the CerCo approach to resource analysis.
\begin{itemize}
 \item There is a lot of recent and renewed activity in the formal method
   community to accomodate resource analysis using techniques derived from
   functional analysis (type systems, logics, abstract interpretation,
   amortized analysis applied to data structures, etc.)
 \item Most of this work, which currently remains at theoretical level,
   is focused on high level languages and it assumes the existence of correct
   and compositional resource cost models.
 \item High level languages are compiled to object code by compilers that
   should respect the functional properties of the program. However, because
   of optimizations and the inherently non compositional nature of compilation,
   compilers do not respect compositional cost models that are imposed a priori
   on the source language. By controlling the compiler and coupling it with a
   WCET analyser, it is actually possible to
   choose the cost model in such a way that the cost bounds are high enough
   to bound the cost of every produced code. This was attempted for instance
   in the EmBounded project with good success. However, we believe that bounds
   obtained in this way have few possibilities of being tight.
 \item Therefore our approach consists in having the compiler generate the
   cost model for the user by combining tracking of basic blocks during code
   transformations with a static resource analysis on the object code for basic
   blocks. We formally prove the compiler to respect the cost model that is
   induced on the source level based on a very few assumptions: basically the
   cost of a sequence of instructions should be associative and commutative
   and it should not depend on the machine status, except its program counter.
   Commutativity can be relaxed at the price of introducing more cost updates
   in the instrumented source code.
 \item The cost model for basic blocks induced on the source language must then
   be exploited to derive cost invariants and to prove them automatically.
   In CerCo we have shown how even simple invariant generations techniques
   are sufficient to enable the fully automatic proving of parametric WCET
   bounds for simple C programs and for Lustre programs of arbitrary complexity.
\end{itemize}

Compared to traditional WCET techniques, our approach currently has many
similarities, some advantages and some limitations. Both techniques need to
perform data flow analysis on the control flow graph of the program and both
techniques need to estimate the cost of control blocks of instructions.

\subsection{Control flow analysis}

The first main difference is in the control flow analysis. Traditional WCET
starts from object code and reconstructs the control flow graph from it.
Moreover, abstract interpretation is heavily employed to bound the number of
executions of cycles. In order to improve the accuracy of estimation, control
flow constraints are provided by the user, usually as systems of (linear)
inequalities. In order to do this, the user, helped by the system, needs to
relate the object code control flow graph with the source one, because it is
on the latter that the bounds can be figured out and be understood. This
operations is untrusted and potentially error prone for complex optimizations
(like aggressive loop optimizations). Efficient tools from linear algebra are
then used to solve the systems of inequations obtained by the abstract
interpreter and from the user constraints.

In CerCo, instead, we assume full control on the compiler that
is able to relate, even in non trivial ways, the object code control flow graph
onto the source code control flow graph. A clear disadvantage is the
impossibility of applying the tool on the object code produced by third party
compilers. On the other hand, we get rid of the possibility of errors
in the reconstruction of the control flow graph and in the translation of
high level constraints into low level constraints. The second potentially
important advantage is that, once we are dealing with the source language,
we can augment the precision of our dataflow analysis by combining together
functional and non functional invariants. This is what we attempted with
the CerCo Cost Annotating Frama-C Plug-In. The Frama-C architecture allows
several plug-ins to perform all kind of static analisys on the source code,
reusing results from other plug-ins and augmenting the source code with their
results. The techniques are absolutely not limited to linear algebra and
abstract interpretation, and the most important plug-ins call domain specific
and general purpose automated theorem provers to close proof obligations of
arbitrary shape and complexity.

In principle, the extended flexibility of the analysis should allow for a major
advantage of our technique in terms of precision, also
considering that all analysis used in traditional WCET can still be implemented
as plug-ins. In particular, the target we have in mind are systems that are
both (hard) real time and safety critical. Being safety critical, we can already
expect them to be fully or partially specified at the functional level.
Therefore we expect that the additional functional invariants should allow to
augment the precision of the cost bounds, up to the point where the parametric
cost bound is fully precise.
In practice, we have not had the time to perform extensive
comparisons on the kind of code used by industry in production systems.
The first middle term improvement of CerCo would then consist in this kind
of analysis, to support or disprove our expectations. It seems that the
newborn TACLe Cost Action (Timing Analysis on Code Level) would be the
best framework to achieve this improvement.
In the case where our
technique remains promising, the next long term improvement would consist in
integrating in the Frama-C plug-in ad-hoc analysis and combinations of analysis
that would augment the coverage of the efficiency of the cost estimation
techniques.

\subsection{Static analysis of costs of basic blocks}
At the beginning of the project we have deliberately decided to focus our
attention on the control flow preservation, the cost model propagation and
the exploitation of the cost model induced on the high level code. For this
reason we have devoted almost no attention to the static analysis of basic
blocks. This was achieved by picking a very simple hardware architecture
(the 8051 microprocessor family) whose cost model is fully predictable and
compositional: the cost of every instruction --- except those that deal with
I/O --- is constant, i.e. it does not depend on the machine status.
We do not regret this choice because, with the limited amount of man power
available in the project, it would have been difficult to also consider this
aspect. However, without showing if the approach can scale to most complex
architectures, our methodology remains of limited interest for the industry.
Therefore, the next important middle term improvement will be the extension
of our methodology to cover pipelines and simple caches. We will now present our
ideas on how we intend to address the problem. The obvious long term
improvement would be to take in consideration multicores system and complex
memory architectures like the ones currently in use in networks on chips.
The problem of execution time analysis for these systems is currently
considered extremely hard or even unfeasible and at the moments it seems
unlikely that our methodology could contribute to the solution of the problem.

\subsubsection{Static analysis of costs of basic blocks revisited}
We will now describe what currently seems to be the most interesting technique
for the static analysis of the cost of basic blocks in presence of complex
hardware architectures that do not have non compositional cost models.

We start presenting an idealized model of the execution of a generic
microprocessor (with caches) that has all interrupts disabled and no I/O
instructions. We then classify the models according to some properties of
their cost model. Then we show how to extend the labelling approach of CerCo
to cover models that are classified in a certain way. 

\paragraph{The microprocessor model}

Let $\sigma,\sigma_1,\ldots$ range over $\Sigma$, the set of the fragments of
the microprocessor states that hold the program counter, the program status word and
all the data manipulated by the object code program, i.e. registers and
memory cells. We call these fragments the \emph{data states}.

Let $\delta,\delta_1,\ldots$ range over $\Delta$, the set of the
fragments of the microprocessor state that holds the \emph{internal state} of the
microprocessor (e.g. the content of the pipeline and caches, the status of
the branch prediction unit, etc.).
The internal state of the microprocessor influences the execution cost of the
next instruction, but it has no effect on the functional behaviour of the
processor. The whole state of the processor is represented by a pair
$(\sigma,\delta)$.

Let $I,I_1,\ldots$ range over $\mathcal{I}$, the
the set of \emph{instructions} of the processor and let
$\gamma,\gamma_1,\ldots$ range over $\Gamma$, the set of \emph{operands}
of instructions after the fetching and decoding passes.
Thus a pair $(I,\gamma)$ represents a \emph{decoded instruction} and already contains
the data required for execution. Execution needs to access the data state only
to write the result.

Let $fetch: \Sigma \to \mathcal{I} \times \Gamma$ be the function that
performs the fetching and execution phases, returning the decoded instruction
ready for execution. This is not meant to be the real fetch-decode function,
that exploits the internal state too to speed up execution (e.g. by retrieving
the instruction arguments from caches) and that, in case of pipelines, works
in several stages. However, such a function exists and
it is observationally equivalent to the real fetch-decode.

We capture the semantics of the microprocessor with the following set of
functions:
\begin{itemize}
 \item The \emph{functional transition} function $\longrightarrow : \Sigma \to \Sigma$
   over data states. This is the only part of the semantics that is relevant
   to functional analysis.
 \item The \emph{internal state transition} function
   $\Longrightarrow : \Sigma \times \Delta \to \Delta$ that updates the internal
   state.
 \item The \emph{cost function} $K: \mathcal{I} \times \Gamma \times \Delta \to \mathbb{N}$
   that assigns a cost to transitions. Since decoded instructions hold the data
   they act on, the cost of an instruction may depend both on the data being
   manipulated and on the internal state.
\end{itemize}

Given a processor state $(\sigma,\delta)$, the processor evolves in the
new state $(\sigma',\delta')$ in $n$ cost units if
$\sigma \longrightarrow \sigma'$ and $(\sigma,\delta) \Longrightarrow \delta'$
and $fetch(\sigma) = (I,\gamma)$ and $K(I,\gamma,\delta) = n$.

An \emph{execution history} is a stream of states and transitions
$\sigma_0 \longrightarrow \sigma_1 \longrightarrow \sigma_2 \ldots$
that can be either finite or infinite. Given an execution history, the
corresponding \emph{execution path} is the stream of program counters
obtained from the execution history by forgetting all the remaining information.
The execution path of the history $\sigma_0 \longrightarrow \sigma_1 \longrightarrow \sigma_2 \ldots$ is $pc_0,pc_1,\ldots$ where each $pc_i$ is the program
counter of $\sigma_i$. We denote the set of finite execution paths with $EP$.

We claim this simple model to be generic enough to cover real world
architectures.

\paragraph{Classification of cost models}
A cost function is \emph{exact} if it assigns to transitions the real cost
incurred. It is \emph{approximated} if it returns an upper bound of the real
cost.

A cost function is \emph{operand insensitive} if it does not depend on the
operands of the instructions to be executed. Formally, $K$ is operand insensitive
if there exists a $K': \mathcal{I} \times \Delta \to \mathbb{N}$ such that
$K(I,\gamma,\delta) = K'(I,\delta)$. In this case, with an abuse of terminology,
we will identify $K$ with $K'$.

The cost functions of simple hardware architectures, in particular RISC ones,
are naturally operand insensitive. In the other cases an exact operand sensitive
cost function can always be turned into an approximated operand insensitive one
by taking $K'(I,\delta) = \max\{K(I,\gamma,\delta)~|~\gamma \in \Gamma\}$.
The question when one performs these approximation is how severe the
approsimation is. A measure is given by the \emph{jitter}, which is defined
as the difference between the best and worst cases. In our case, the jitter
of the approximation $K'$ would be $\max\{K(I,\gamma,\delta)~|~\gamma \in \Gamma\} - \min\{K(I,\gamma,\delta)~|~\gamma \in \Gamma\}$. According to experts
of WCET analysis, the jitters relative to operand sensitivity in modern
architectures are small enough to make WCET estimations still useful.
Therefore, in the sequel we will focus on operand insensitive cost models only.

Note that cost model that are operand insensitive may still have significant
dependencies over the data manipulated by the instructions, because of the
dependency over internal states. For example, an instruction that reads data
from the memory may change the state of the cache and thus greatly affect the
execution time of successive instructions.

Nevertheless, operand insensitivity is an important property for the labelling
approach. In~\cite{tranquilli} we introduced \emph{dependent labels} and
\emph{dependent costs}, which are the possibility of assigning costs to basic
blocks of instructions which are also dependent on the state of the high level
program at the beginning of the block. The idea we will now try to pursue is
to exploit dependent costs to capture cost models that are sensitive to
the internal states of the microprocessor. Operand sensitivity, however, is
a major issue in presence of dependent labels: to lift a data sensitive cost
model from the object code to the source language, we need a function that
maps high level states to the operands of the instructions to be executed,
and we need these functions to be simple enough to allow reasoning over them.
Complex optimizations performed by the compiler, however, make the mappings
extremely cumbersomes and history dependent. Moreover, keeping
track of status transformations during compilation would be a significant
departure from classical compilation models which we are not willing to
undertake. By assuming or removing operand sensitivity, we get rid of part
of the problem: we only need to make our costs dependent on the internal
state of the microprocessor. The latter, however, is not at all visible
in the high level code. Our next step is to make it visible.

In general, the value of the internal state at a certain point in the program
history is affected by all the preceding history. For instance, the
pipeline stages either hold operands of instructions in execution or bubbles
\footnote{A bubble is formed in the pipeline stage $n$ when an instruction is stucked in the pipeline stage $n-1$, waiting for some data which is not available yet.}. The execution history contains data states that in turn contain the
object code data which we do not know how to relate simply to the source code
data. We therefore introduce a new classification. 

A \emph{view} over internal states is a pair $(\mathcal{V},|.|)$ where
$\mathcal{V}$ is a finite non empty set and $|.|:\Delta \to \mathcal{V}$ is
a forgetful function over internal states.

The operand insensitive cost function $K$ is \emph{dependent on the view
$\mathcal{V}$} if there exists a $K': \mathcal{I} \times \mathcal{V} \to \mathbb{N}$ such that $K(I,\delta) = K'(I,|\delta|)$. In this case, with an abuse of terminology, we will identify $K$ with $K'$.

Among the possible views, the ones that we will easily be able to work
with in the labelling approach are the \emph{execution history dependent views}.
A view $(\mathcal{V},|.|)$ is execution history dependent with a lookahead
of length $n$ when there exists
a transition function $\hookrightarrow : PC^n \times \mathcal{V} \to \mathcal{V}$
such that for all $(\sigma,\delta)$ and $pc_1,\ldots,pc_n$ such that every
$pc_i$ is the program counter of $\sigma_i$ defined by $\sigma \longrightarrow^i \sigma_i$, we have $(\sigma,\delta) \Longrightarrow \delta'$ iff
$((pc_1,\ldots,pc_n),|\delta|) \hookrightarrow |\delta'|$.

Less formally, a view is
dependent on the execution history if the evolution of the views is fully
determined by the evolution of the program counters. To better understand
the definition, consider the case where the next instruction to be executed
is a conditional jump. Without knowing the values of the registers, it is
impossible to determine if the true or false branches will be taken. Therefore
it is likely to be impossible to determine the value of the view the follows
the current one. On the other hand, knowing the program counter that will be
reached executing the conditional branch, we also know which
branch will be taken and this may be sufficient to compute the new view.
Lookaheads longer then 1 will be used in case of pipelines: when executing
one instruction in a system with a pipeline of length $n$, the internal state
of the pipeline already holds information on the next $n$ instructions to
be executed.

The reference to execution historys in the names is due to the following
fact: every execution history dependent transition function $\hookrightarrow$
can be lifted to the type $EP \times \mathcal{V} \to \mathcal{V}$ by folding
the definition over the path trace:
$((pc_0,\ldots,pc_m),v_0) \hookrightarrow v_n$ iff for all $i \leq m - n$,
$((pc_i,\ldots,pc_{i+n}),v_i) \hookrightarrow v_{i+1}$.
Moreover, the folding is clearly associative:
$(\tau_1 @ \tau_2, v) \hookrightarrow v''$ iff
$(\tau_1,v) \hookrightarrow v'$ and $(\tau_2,v') \hookrightarrow v''$.

As a final definition, we say that a cost function $K$ is
\emph{data independent} if it is dependent on a view that is execution path
dependent. In two paragraphs we will show how we can extend the
labelling approach to deal with data independent cost models.

Before that, we show that the class of data independent cost functions
is not too restricted to be interesting. In particular, at least simple
pipeline models admit data independent cost functions.

\paragraph{A data independent cost function for simple pipelines}
We consider here a simple model for a pipeline with $n$ stages without branch
prediction and hazards. We also assume that the actual value of the operands
of the instruction that is being read have no influence on stalls (i.e. the
creation of bubbles) nor on the execution cost. The type of operands, however,
can. For example, reading the value 4 from a register may stall a pipeline
if the register has not been written yet, while reading 4 from a different
register may not stall the pipeline.

The internal states $\Delta$ of the pipeline are $n$-tuples of decoded
instructions or bubbles:
$\Delta = (\mathcal{I} \times \Gamma \cup \mathbbm{1})^n$.
This representation is not meant to describe the real data structures used
in the pipeline: in the implementation the operands are not present in every
stage of the pipeline, but are progressively fetched. A state
$(x_1,x_2,\ldots,(I,\gamma))$ represents the state of the pipeline just before
the completion of instruction $(I,\gamma)$. The first $n-1$ instructions that
follow $I$ may already be stored in the pipeline, unless bubbles have delayed
one or more of them.

We introduce the following view over internal states:
$(\{0,1\}^n,|.|)$ where $\mathbb{N}_n = {0,\ldots,2^n-1}$ and
$|(x_1,\ldots,x_n)| = (y_1,\ldots,y_n)$ where $y_i$ is 1 iff $x_i$ is a bubble.
Thus the view only remembers which stages of the pipelines are stuck.
The view holds enough information to reconstruct the internal state given
the current data state: from the data state we can fetch the program counter
of the current and the next $n-1$ instructions and, by simulating at most
$n$ execution steps and by knowing where the bubbles were, we can fill up
the internal state of the pipeline.

The assumptions on the lack of influence of operands values on stalls and
execution times ensures the existence of the data independent cost function
$K: PC \times \{0,1\}^n \to \mathbb{N}$. The transition function for a
pipeline with $n$ stages may require $n$ lookaheads:
$\hookrightarrow : PC^n \times \{0,1\}^n \to \{0,1\}^n$.

While the model is a bit simplicistic, it can nevertheless be used to describe
existing pipelines. It is also simple to be convinced that the same model
also captures static branch prediction: speculative execution of conditional
jumps is performed by always taking the same branch which does not depend on
the execution history. In order to take in account jumpt predictions based on
the execution history, we just need to incorporate in the status and the view
statistical informations on the last executions of the branch.

\paragraph{The labelling appraoch for data independent cost models}
We now describe how the labelling approach can be slightly modified to deal
with a data independent cost model $(\hookrightarrow,K)$ built over
$(\mathcal{V},|.|)$. 

In the labelling approach, every basic block in the object code is identified
with a unique label $L$ which is also associated to the corresponding
basic block in the source level. Let us assume that labels are also inserted
after every function call and that this property is preserved during
compilation. Adding labels after calls makes the instrumented code heavier
to read and it generates more proof obligations on the instrumented code, but
it does not create any additional problems. The preservation during compilation
creates some significant technical complications in the proof of correctness
of the compiler, but those can be solved.

The static analysis performed in the last step of the basic labelling approach
analyses the object code in order to assign a cost to every label or,
equivalently, to every basic block. The cost is simply the sum of the cost
of very instruction in the basic block.

In our scenario, instructions no longer have a cost, because the cost function
$K$ takes in input a program counter but also a view $v$. Therefore we
replace the static analysis with the computation, for every basic block and
every $v \in \mathcal{V}$, of the sum of the costs of the instructions in the
block, starting in the initial view $v$. Formally, let the sequence of the
program counters of the basic block form the execution path $pc_0,\ldots,pc_n$.
The cost $K(v_0,L)$ associated to the block labelled with
$L$ and the initial view $v_0$ is
$K(pc_0,v_0) + K(pc_1,v_1) + \ldots + K(pc_n,v_n)$ where for every $i < n$,
$((pc_i,\ldots,pc_{i+l}),v_i) \hookrightarrow v_{k+1}$ where $l$ is the
lookahead required. When the lookahead requires program counters outside the
block under analysis, we are free to use dummy ones because the parts of the
view that deal with future behaviour have no impact on the cost of the
previous operations by assumption. 

The static analysis can be performed
in linear time in the size of the program because the cardinality of the sets
of labels (i.e. the number of basic blocks) is bounded by the size of the
program and because the set $V$ is finite. In the case of the pipelines of
the previous paragraph, the static analysis is $2^n$ times more expensive
than the one of the basic labelling approach, where $n$ is the number of
pipeline stages.

The first imporant theorem in the labelling approach is the correctness of the
static analysis: if the (dependent) cost associated to a label $L$ is $k$,
then executing a program from the beginning of the basic block to the end
of the basic block should take exactly $k$ cost units. The proof only relies
on associativity and commutativity of the composition of costs. Commutativity
is only required if basic blocks can be nested, i.e. if a basic block does not
terminate when it reaches a call, but it continues after the called function
returns. By assuming to have a cost label after each block, we do not need
commutativity any longer, which does not hold for the definition of $K$ we
just gave. The reason is that, if $pc_i$ is a function call executed in
the view (state) $v_i$, it is not true that, after return, the state
will be $v_i+1$ defined by $(pc_i,pc_{i+1},v_i) \hookrightarrow v_{i+1}$
(assuming a lookahead of 1, which is already problematic).
Indeed $pc_{i+1}$ is the program counter of the instruction that follows
the call, whereas the next program counter to be reached is the one of the
body of the call. Moreover, even if the computation would make sense,
$v_{i+1}$ would be the state at the beginning of the execution of the body of
the call, while we should know the state after the function returns.
The latter cannot be
statically predicted. That's why we had to impose labels after calls.
Associativity, on the other hand, trivially holds. Therefore the proof
of correctness of the static analysis can be reused without any change.

So far, we have computed the dependent cost $K: \mathcal{V} \times \mathcal{L} \to \mathbb{N}$ that associates a cost to basic blocks and views.
The second step consists in statically computing the transition function
$\hookrightarrow : \mathcal{L} \times \mathcal{L} \times \mathcal{V} \to \mathcal{V}$ that
associates to each pair of consecutively executed basic blocks and input view
the view obtained at the end of the execution of the first block.

The definition is the following:
$(L,L',v) \hookrightarrow v'$ iff $((pc_0,\ldots,pc_n,pc'_0,\ldots,pc'_m),v) \hookrightarrow v'$ where $(pc_0,\ldots,pc_n)$ are the program counters of the block labelled by $L$ and $(pc'_0,\ldots,pc'_m)$ are those of the block labelled
with $L'$. We assume here that $m$ is always longer or equal to the lookahead
required by the transition function $\hookrightarrow$ over execution paths.
When this is not the case we could make the new transition function take in
input a longer lookahead of labels. Or we may assume to introduce enough
\texttt{NOP}s at the beginning of the block $L'$ to enforce the property.
In the rest of the paragraph we assume to have followed the second approach
to simplify the presentation.

The extended transition function over labels is not present in the basic labelling approach. Actually, the basic labelling
approach can be understood as the generalized approach where the view $\mathcal{V} = \mathbbm{1}$.
The computation of the extended $\hookrightarrow$ transition function
is again linear in the size of the program.

Both the versions of $K$ and $\hookrightarrow$ defined over labels can be
lifted to work over traces by folding them over the list of labels in the
trace: for $K$ we have $K((L_1,\ldots,L_n),v) = K(L_1,v) + K((L_2,\ldots,L_n),v')$ where
$(L_1,L_2,v) \hookrightarrow v'$;  for $\hookrightarrow$ we have
$((L_1,\ldots,L_n),v) \hookrightarrow v''$ iff $(L_1,L_2,v) \hookrightarrow v'$ and $((L_2,\ldots,L_n),v') \hookrightarrow v''$. The two definitions are also
clearly associative.

The second main theorem of the labelling approach is trace preservation:
the trace produced by the object code is the same as the trace produced by
the source code. Without any need to change the proof, we immediately obtain
as a corollary that for every view $v$, the cost $K(\tau,v)$ computed from
the source code trace $\tau$ is the same than the cost $K(\tau,v)$ computed
on the object code trace, which is again $\tau$.

The final step of the labelling approach is source code instrumentation.
In the basic labelling approach it consists in adding a global variable
\texttt{\_\_cost}, initialized with 0, which is incremented at the beginning
of every basic block with the cost of the label of the basic block.
Here we just need a more complex instrumentation that keeps track of the
values of the views during execution:
\begin{itemize}
 \item We define three global variables \texttt{\_\_cost}, initialized at 0,
   \texttt{\_\_label}, initialized with \texttt{NULL}, and
   \texttt{\_\_view}, uninitialized.
 \item At the beginning of every basic block labelled by $L$ we add the
  following code fragment:

  \begin{tabular}{l}
  \texttt{\_\_view = \_\_next(\_\_label,}$L$\texttt{,\_\_view);}\\
  \texttt{\_\_cost += }$K(\mbox{\texttt{\_\_view}},L)$\texttt{;}\\
  \texttt{\_\_label = }$L$\texttt{;}
  \end{tabular}

  where \texttt{\_\_next(}$L_1,L_2,v$\texttt{)} = $v'$ iff
  $(L_1,L_2,v) \hookrightarrow v'$ unless $L_1$ is \texttt{NULL}.
  In that case \texttt{(\_\_next(NULL,}$L$\texttt{)} = $v_0$ where
  $v_0 = |\delta_0|$ and $\delta_0$ is the initial value of the internal stat
  at the beginning of program execution.
  
  The first line of the code fragment computes the view at the beginning of
  the execution of the block from the view at the end of the previous block.
  Then we update the cost function with the cost of the block. Finally we
  remember the current block to use it for the computation of the next view
  at the beginning of the next block.
\end{itemize}

\paragraph{An example of instrumentation in presence of a pipeline}
In Figure~\ref{factprogi} we show how the instrumentationof a program
that computes the factorial of 10 would look like in presence of a pipeline.
The instrumentation has been manually produced. The \texttt{\_\_next}
function says that the body of the internal loop of the \texttt{fact}
function can be executed in two different internal states, summarized by the
views 2 and 3. The view 2 holds at the beginning of even iterations,
while the view 3 holds at the beginning of odd ones. Therefore even and odd
iterations are assigned a different cost. Also the code after the loop can
be executed in two different states, depending on the oddness of the last
loop iteration.

\begin{figure}[t]
\begin{center}
\begin{verbatim}
int fact (int n) {
  int i, res = 1;
  for (i = 1 ; i <= n ; i++) res *= i;
  return res;
}

int main () {
  return (fact(10));
}
\end{verbatim}
\end{center}
\caption{A simple program that computes the factorial of 10.\label{factprog}}
\end{figure}

The definitions of \texttt{\_\_next} and \texttt{\_\_K} are just examples.
For instance, it is possible as well that each one of the 10 iterations
is executed in a different internal state.

\begin{figure}[t]
\begin{tiny}
\begin{verbatim}
int __cost = 8;
int __label = 0;
int __view;

void __cost_incr(int incr) {
  __cost = __cost + incr;
}

int __next(int label1, int label2, int view) {
       if (label1 == 0)                             return 0;
  else if (label1 == 0 && label2 == 1)              return 1;
  else if (label1 == 1 && label2 == 2)              return 2;
  else if (label1 == 2 && label2 == 2 && view == 2) return 3;
  else if (label1 == 2 && label2 == 2 && view == 3) return 2;
  else if (label1 == 2 && label2 == 3 && view == 2) return 1;
  else if (label1 == 2 && label2 == 3 && view == 3) return 0;
  else if (label1 == 3 && label2 == 4 && view == 0) return 0;
  else if (label1 == 3 && label2 == 4 && view == 1) return 0;
}

int __K(int view, int label) {
       if (view == 0 && label == 0) return 3;
  else if (view == 1 && label == 1) return 14;
  else if (view == 2 && label == 2) return 35;
  else if (view == 3 && label == 2) return 26;
  else if (view == 0 && label == 3) return 6;
  else if (view == 1 && label == 3) return 8;
  else if (view == 0 && label == 4) return 6;
}

int fact(int n)
{
  int i;
  int res;
  int k;
  __view = __next(__label,1,__view);
  k = __K(__view,1);
  __cost_incr(k);
  __label = 1;
  res = 1;
  for (i = 1; i <= n; i = i + 1) {
     __view = __next(__label,2,__view);
     __cost_incr(__K(__view,2));
     __label = 2;
    res = res * i;
  }
  __view = __next(__label,3,__view);
  k = __K(__view,3);
  __cost_incr(k);
  __label = 3;
  return res;
}

int main(void)
{
  int t;
  int k;
  __view = __next(__label,0,__view);
  k = __K(__view,0);
  __cost_incr(k);
  __label = 0;
  t = fact(10);
  __view = __next(__label,4,__view);
  k = __K(__view,4);
  __cost_incr(k);
  __label = 4;
  return t;
}
\end{verbatim}
\end{tiny}
\caption{The instrumented version of the program in Figure~\ref{factprog}.\label{factprogi}}
\end{figure}


\end{document}