Remove unused rpc/xdr references.
[dyninst.git] / dataflowAPI / doc / Abstractions.tex
1 \section{Abstractions}
2 \label{sec:abstractions}
3
4 DataflowAPI starts from the control flow graphs generated by ParseAPI and the instructions generated by InstructionAPI.
5 From these, it provides dataflow facts in a variety of forms. The key abstractions used by DataflowAPI are:
6
7 \begin{itemize}[leftmargin=0pt,label=$\circ$]
8 {\item {\scshape Abstract Location}
9 represents a register or memory location in the program.
10 DataflowAPI provides three types of abstract locations: register, stack, and
11 heap. A register abstract location represents a register, and the same register at two
12 different program locations is treated as the same abstract location. 
13 A stack abstract location consists of the stack frame to which it belongs and
14 the offset within the stack frame. 
15 A heap abstract location consists of the virtual address of the heap variable.
16 }
17
18 {\item {\scshape Abstract Region}
19 represents a set of abstract locations of the same type. 
20 If an abstract region contains only a single abstract location, the
21 abstract location is precisely represented. 
22 If an abstract region contains more than one abstract location, the region
23 contains the type of the locations. In the cases where it represents memory
24 (either heap or stack), an abstract region also contains 
25 the memory address calculation that gives rise to this region. 
26 }
27
28 {\item {\scshape Abstract Syntax Tree (AST)}
29 represents a symbolic expression of an instruction's semantics.
30 Specifically, an AST specifies how the value of an abstract location is modified by the
31 instruction.
32 }
33
34 {\item {\scshape Assignment}
35 represents a single data dependency of abstract regions in an instruction. For example, \texttt{xchg eax, ebx} creates two assignments: one from pre-instruction \texttt{eax} to post-instruction \texttt{ebx}, and one from pre-instruction \texttt{ebx} to post-instruction \texttt{eax}.
36 }
37
38 {\item {\scshape Stack Height}
39 represents the difference between a value in an abstract location and the stack pointer at a function's call site.
40 }
41 \end{itemize}
42
43