Support for using GNU g++ demangler, rationalize use of libiberty

[dyninst.git] / depGraphAPI / doc / analyzeDDG.tex

\documentclass[11pt]{article}
\title{Design document for DyninstAPI DDG Analysis}
\author{Andrew R. Bernat}
\begin{document}

The purpose of this document is to explain the data dependence graph
(DDG) analysis used by the DDG component of the DyninstAPI binary
analysis and instrumentation suite. Our DDG closely follows the
conventional definition and is built using an analysis optimized for
binary code.

\section*{Definitions}

This work uses the following terms:

\begin{description}
\item[Memory Region] A memory region is a contiguous range of memory
  locations beginning at 0 and ending at some maximal value $n$. We
  assume that memory regions to not overlap. Our current approach
  defines two memory regions for each function: the \emph{global}
  region and the \emph{stack}. 
\item[Abstract Location] An \emph{abstract location} (or absloc) represents a
  register or memory location. A memory location is a (region, offset)
  pair that identifies a unique location within a memory region.
\item[Abstract Region] An \emph{abstract region} refers to multiple
  offsets within a memory region. Currently an abstract region refers
  to the entire region; this may become more precise in the future.
\item[Aliasing] Imprecision in memory analysis may lead to us not
  being able to determine the offset within a region that an
  instruction uses or defines. This leads to the existence of
  \emph{aliases} - multiple abstractions for the same offset. In
  particular, an abstract region is an alias of all abstract locations
  within its set of offsets and vice versa. Aliasing leads to the
  following issue: if an instruction defines an abstract region it
  \emph{possibly defines} all abstract locations within that region;
  however, we do not know which location was actually defined.
\item[Operation] Instructions may define multiple abstract
  locations. For example, consider the IA-32 \emph{push}
  instruction. Let $SP$ represent the stack pointer, and $*SP$ the top
  of the stack. Then \emph{push eax} has the following effects: $SP = SP -
  4$ and $*SP = eax$. Note that although there are two definitions
  they are independent; the definition of $SP$ does not depend on
  $eax$. We represent this by splitting instructions into
  single-definition \emph{operations} represented by an (instruction,
  absloc) pair. 
\item[Gen Set] The \emph{gen set} (short for \emph{generated set}) for
  an absloc is the set of operations that definitely define and
  possibly define (see aliasing, above) that absloc.
\item[Kill Set] The \emph{kill set} for an absloc is the set of
  operations to remove from the gen set. 
\item[Candidate Node] The analysis may create a number of nodes that
  are not necessary in the finished DDG. We refer to these as
  \emph{candidate} nodes (cNodes), and any candidate nodes that are not added
  to the DDG are discarded. 
\end{description}

\section*{Data Dependence Graph}

A data dependence graph (DDG) is a graph $DDG = (V, E)$. The set of
vertices $V$ consists of the following types of nodes:
\begin{description}
\item[Operation Nodes] Represent operations as defined above.
\item[Virtual Node] Any operation that uses no abstract locations is
  instead given an in edge from a unique \emph{virtual node}. We do
  this to insure that all operations are reachable in the graph.
\item[Formal Parameter Nodes] These represent definitions of abstract
  locations that occur prior to the function being executed. These
  include both ``expected'' parameters (as provided in registers or
  the stack), definitions to global variables, and so on.
\item[Formal Return Nodes] These represent definitions of abstract
  locations that persist after the function completes. This includes
  the ``expected'' return value as well as definitions to caller-saved
  registers, the stack, and so on.
\item[Actual Parameter Nodes] These summarize abstract locations used
  by a called function.
\item[Actual Return Nodes] These summarize abstract locations defined
  during execution of a called function.
\end{description}

Nodes are connected with edges that represent use-def
chains. Let $i, j$ be instructions and $a, b$ be abstract
locations. Let $o = (i,a)$ and $p = (j,b)$ be two operations: $o$
represents the definition of $a$ by $i$ and $p$ similarly represents
the definition of $b$ by $j$. Then an edge $e = (o,p)$ indicates the following:
\begin{itemize}
\item $i$ defines an abstract location $a$.
\item $j$ uses $a$ to define $b$.
\item There exists an execution path from $i$ to $j$ such that no
  redefinition of $a$ occurs on that path.
\end{itemize}

Operation nodes, the immediate node, formal parameter nodes, and
actual return nodes all define abstract locations and thus have
out-edges. Operation nodes, formal return nodes, and actual parameter
nodes all use abstract locations and thus have in-edges. We also
define \emph{virtual} edges between actual parameter and actual return
nodes to represent dependences within the called function. 

\section*{Analysis}

Our analysis is somewhat complex. This section describes both the
intuition between each phase of the analysis and the results of the
phase. It should be kept in sync with any changes to function names,
etc.

\subsection*{Overview}

The goal of the DDG analysis is to construct an accurate and
reasonably precise intraprocedural DDG for a provided function. The
DDG is calculated with a fixpoint loop over a CFG. We note that CFGs
are not highly connected; instead, they are very \emph{lumpy} as
described by basic blocks. Therefore, instead of using a generalized
fixpoint we divide the analysis into three phases:
\begin{description}
\item[Block Summarization] This phase summarizes the gen set and kill
  set for each block in the program. The results of this phase is the
  following information for each block and absloc:
\begin{itemize}
\item Gen set: the last operation $o$ to definitely define that absloc,
  plus all operations that possibly define that absloc after $o$. 
\item Kill set: a boolean; true if there exists a definite definition
  to the absloc and false otherwise.
\end{itemize}
\item[Inter-Block Reaching Definitions] This phase uses the gen and
  kill set information determined in Phase 1 to determine the set of
  reaching definitions at the entry of each block. This is determined
  over blocks in the classic way. The following equations are per-absloc:
  \begin{itemize}
    \item $IN(B) = \bigcup_{C \in pred(B)} OUT(C)$;
    \item $OUT(B) = GEN(B) \cup (IN(B) - KILL(B))$
  \end{itemize}
  We optimize this as follows. The kill set can be compactly
  represented as a boolean; if true, then $OUT(B) = GEN(B)$;
  otherwise, $OUT(B) = GEN(B) \cup IN(B)$. 
\item[Node Creation] Once reaching definitions have been calculated
  for the entry to each block we can determine the reaching defs to
  each instruction within the block and create the graph. 
\end{description}

\subsection*{Block Summarization}

The first phase summarizes gen and kill set information for each
block. Since we are only interested in the \emph{last} operation that
definitely defines a particular absloc, plus any possible definitions
that occur after that, we do this with a backwards iteration. This
algorithm operates as follows:

\begin{verbatim}

updateDefSet(GenSet blockGens, Absloc A, cNode N)
  blockGens[A] += N
  For each alias A' of A:
    blockGens[A] += N

updateKillSet(KillSet blockKills, Absloc A) 
  if isPrecise(A)
    blockKills[A] = true

localize(Absloc A)
  If isStack(A)
    Let off = A.offset
    Let height = current stack height
    return A' = (stack region, off + height)
  Return A

summarizeCallGenKill(GenSet blockGens, KillSet blockKills,
                     Function callee) 
  Let cDDG = callee DDG
  Let fR = cDDG.formalReturnNodes
  For each absloc D in fR, do:
    Let D' = localize(D)
    Let cNode C = ActualReturnNode(callee, D')
    updateDefSet(blockGens, D', C)
    updateKillSet(blockKills, D')

summarizeBlockGenKill(Block B)
  Let blockGens = globalGens[B]
  Let blockKills = globalKills[B]
  For i = B.last to B.first, do: 
    For each absloc D defined by i, do:
      If blockKills(D), continue       
      Let cNode C = (i, D)
      updateDefSet(blockGens, D, C)
      updateKillSet(blockKills, D)
    If isCall(i)
      summarizeCallGenKill(blockGens, blockKills, i.callee)

summarizeGenKillSets
  For each block B in blocks
    summarizeBlockGenKill(B)

\end{verbatim}
                
\subsection*{Inter-Block Reaching Definitions}

This phase is relatively straightforward. The only complication is
created by the need to handle an unknown set of initial definitions
from outside the function (parameters). Any absloc that is used before
being defined is assumed to have an initial definition, represented by
a parameter node, from the caller function. However, we don't want to
have to enumerate all possible parameter nodes. Instead, we create
them on the fly. 

Consider the following case. Let $B_1, B_2, B_3$ be basic blocks, with
$B_1, B_2$ being predecessors of $B_3$ and $B_2$ being an entry
block. Let $A$ be an absloc defined in $B_1$ and used in $B_3$; $A$ is
\emph{not} defined in $B_2$. In this case the use of $A$ in $B_3$ has
a reaching definition from both $B_1$ (due to the definition) and a
parameter definition from $B_2$. 

We can lazily create these parameter definitions by creating a
\emph{virtual parameter definition} for all abstract locations not
defined in the block itself. 

These virtual parameter definitions are lazily created during the
merge phase of reaching definitions analysis, as follows:

\begin{verbatim}
merge(BlockSet blocks)
  For each absloc A
    Let IN[A] = {}
    For each B in blocks
      If B.defines(A)
        IN[A] += B.defs(A)
      Else
        IN[A] += Parameter(A)
\end{verbatim}

However, we still have a problem with alias definitions. Suppose that
$B_1$ defines $S$, the stack region (a possible definition of all
locations in the stack), and that $B_2$ defines $S_1$. When we merge
$B_1, B_2$, there will be no information that $B_1$ possibly defined
$S_1$ (as we create abstract locations lazily. We thus augment our
definition of merge, as follows:

\begin{verbatim}
merge(BlockSet blocks) 
  For each absloc A
    Let IN[A] = {}
    For each B in blocks
      If B.defs(A) != 0
        IN[A] += B.defs(A)
      Else 
        IN[A] += Parameter(A)
        For each D in A.aliases
          IN[A] += B.defs(D)
\end{verbatim}

The problem with this definition is that we must know all abstract
locations a priori, which means a iterating over all abslocs (even
those not defined by previous blocks). This is inefficient. However,
we note the following. Parameter nodes are unique and idempotent; we
insert a parameter node for absloc $A$ if there exists at least one
path along which $A$ is not defined. 

We therefore use the following definition of merge:

\begin{verbatim}
merge (BlockSet blocks)
  Let counts be a map absloc -> integer
  For each block B in blocks
    For each absloc A in B.defSet
      IN[A] += B.defs(A)
      counts[A]++;
    If NOT A.isPrecise
      For each D in A.aliases
        If B.defs(D) == 0
          IN[A] += B.defs(D)
  For each absloc A in counts
    If counts[A] != blocks.size()
      IN[A] += Parameter(A)
\end{verbatim}


The remainder of the fixpoint analysis operates as expected, with the
modification of the kill set being represented as booleans rather than
sets of elements:

\begin{verbatim}
calcNewOut(Absloc A,
           DefSet in,
           DefSet gens,
           KillSet kills,
           DefSet &out) 
  If (kills[A])
    out = gens
  Else
    out = gens + in
\end{verbatim}


\subsection*{Node Creation}

Once we have the set of reaching definitions at the entry point of
each block we can continue to create the graph. This is done in a
straightforward iteration over each block and instruction within the
block. 

We call the set of reaching definitions to the start of the block the
\emph{local reaching definitions} of the block. We then calculate the
reaching definitions to each instruction (and operation) as follows:

\begin{verbatim}
createNodes
  For each block B
    Let localReachingDefs = IN set of B
    For each instruction I in B
      For each absloc D defined by I
        Let node TARGET = (I, D)
        Let USE be the set of abslocs used by I to define D
          For each U in USE
            Let RD = localReachingDefs[U]
              For each cNode N in RD
                Let node SOURCE = N
                  Insert (S,T) into DDG
      For each absloc D defined by I
        If D.isPrecise
          localReachingDefs[D] = (I,D)
      If I.isCall()
        createCallNodes(I)
      If I.isReturn()
        createReturnNodes(I)
\end{verbatim}

The creation of edges in the DDG is straightforward. Given a
definition $D$ (and thus an operation $(I,D)$ and a node $T = (I,D)$):
\begin{itemize}
\item Find the abstract locations used to define $D$;
\item For each $U$ in this set, find the reaching definitions of $U$;
\item Create an edge from each such reaching definition $S$ to $T$.
\end{itemize}

However, once an instruction defines an abstract location it kills all
such previous definitions. We thus iterate over all defined locations
a second time and remove all appropriate previous definitions of
$D$. This is done in a second iteration rather than during the first
to insure parallelism of operations. 

We must also create actual parameter nodes and formal return nodes for
calls and returns. Call parameter nodes are created in the same way as
instructions, except instead of the used set of the instruction we use
the formal parameter nodes of the call. Formal return nodes are
created for every reaching definition to the end of the block. These
are handled in a straightforward way by the \texttt{createCallNodes}
and \texttt{createReturnNodes} functions.