Data Flow

Data Flow Criteria

Definition(def) - a location where a value for a variable is stored into memory

Use - a location where a variable's value is accessed

def(n) or def(e) - The sets of variables that are defined by node n or edge e

use(n) or use(e) - The set of variables that are used by node n or edge e

• Node n1 reaches n2 if there is a path in between the two

DU pair - a pair of locations $(l_i, l_j)$ such that a variable $v$ that is defined at $l_i$ and used at $l_j$

// Example

x = 5; // def(x)
...
print(x) // use(x)

Def-clear - a path $p$ from $l_i$ to $l_i$ is def-clear with respect to variable $v$ if for every node $n_k$ and every edge $e_k$ on $p$ from $l_i$ to $l_j$, where $k\neq i$ and $k\neq j$, $v$ is not in def($n_k$) or in def($e_k$).

• The variable is not declared in the path

Reach - if there is a def-clear path from $l_i$ to $l_j$ with respect to $v$, the def of $v$ at $l_i$ reaches the use at $l_j$.

DU-path - a simple path that is def-clear with respect to $v$ from a def of $v$ to a use of $v$

• Associated with a variable
• Simple
• May be any numbe rof uses in a du-path

Def-pair set - $du(n_i,n_j,v)$ - the set of du-paths from $n_i$ to $n_j$

Def-path set - $du(n_i, v)$ - the set of du-paths that start at $n_i$

Coverages

• Assume every def reaches a use

All-Defs Coverage (ADC) - For each set of du-paths $S=du(n, v)$, TR
contains at least one path $d$ in $S$

• Contains one path from all instances of definition

All-Uses Coverage (AUC) - For each set of du-paths to uses $S=du(n_i, n_j, v)$, TR contains at least one path $d$ in $S$

• Contains one path from all instances of definition to usage

All-du-Paths Coverage (ADUPC) - For each set $S=du(n_i, n_j, v)$, TR contains every path $d$ in $S$

• Contains every path from all instances of definition to usage
• Even if they are subpaths of one another

Touring DU-Paths

• A test path $p$ du-tours subpath $d$ with respect to $v$ if $p$ tours $d$ and the subpath taken is def-clear with respect to $v$

• Side trips can be used

Best effort touring

• Use every def
• Get to every use
• Follow all du-paths

Definitions and Uses

Definitions

• Direct assignment: x=5
• Implicit definition: foo(T x){...}
• C++ reference param: bar(x)

Uses

• x is used when it occurs in an expression that the program evaluates

Basic Blocks

• Can be used to rule out some def and uses as irrelevant

Defs

• Consider the last definition of a variable in a basic block
• If we are not sure whether x and y are aliased keep both of them

Uses

• Consider only uses that aren't dominated by a definition of the same variable in the same basic block

  // Not interesting
  y = 5;
  use(y);
  

Graph Coverage Criteria Subsumption

AUC & EC

• For every node with multiple outgoing edges, at least one variable is used on each out edge

• The same variables are used on each out edge

• Assume test set T satisfies AUC

• Each edge e1 must be either a branch edge or not
• If e1 is a branch edge, then it has a use, thus it must be covered by T
• If e1 is not a branch edge, the closest branch edge before e1, denoted as e2, should be covered by T, and if e2 is covered by a test, e1 must also be; If the closed branch edge doesn't exit, then the program has no branch edges. Therefore e1 must be covered by T

Interprocedural Data Flow

• When values are passed they change "names"

Caller - a unit that invokes another unit

Callee - the unit that is called

Callsite - statement or node where the call appears

Actual parameter - variable in the caller

Formal parameter - variable in the callee

Interprocedural DU Pairs

• In integration testing, we only care about the interface
• We just need to consider the last definitions of variables before calls and returns first uses inside units after calls

Last-def - the set of nodes that define a variable x and has a def-clear path from the node through a callsite to a use in the other unit

• Can be from a caller to callee (param or shared variable)
• Can be from a callee to caller (return variable)

First-use - the set of nodes that have uses of a variable y and for which there is a def-clear and use-clear path from the call site to the nodes