== Points-To Analysis==
**The Flow-Insensitive Representation 
* {{{AssignmentIF}}} :  A flow-insensitive representation of a program is a set of {{{AssignmentIF}}}.  An {{{AssignmentIF}}} instance represents an assignment in the program which is one of the following forms:
 * Base: {{{ lhs = &rhs }}}
 * Simple: {{{ lhs = rhs }}}
 * Complex 1: {{{ *lhs = rhs }}}
 * Complex 2: {{{ lhs = *rhs }}}

  For the case of {{{ *lhs = *rhs }}}, an auxiliary variable {{{tmp}}} is introduced: {{{ tmp = *rhs }}}, {{{ *rhs = tmp }}}. 

  For now, structs and array elements are all invisible for the flow-insensitive representation: so {{{ expr.id }}} is abstracted to {{{expr}}};   {{{expr->id}}} is abstracted to {{{*expr}}};  {{{a[I]}}} is abstracted to {{{a}}};   {{{*(p + i)}}}, where {{{I}}} is an integer, is abstracted to {{{*p}}}.
  
  For the case of {{{lhs =  a op b}}} (or `*lhs = a op b`), it is abstracted to `lhs = a` (or `*lhs = a`) and `lhs = b` (or `*lhs = b`)

** Intra-Procedural Points-To Analysis 
* Reference :  	Ben Hardekopf & Calvin Lin  "The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code"
* `PointsToGraph` : A points-to graph represents an over-approximation of "what pointers are point to" information in a function.
  * In the graph, nodes are the objects that are reachable from the function associated with the points-to graph.
  * The graph also maintains a set of objects,  which is the "points-to set" of a node, for every node.
  * In the graph, edges are the subset-of relations between different nodes.
  * A client of `PointsToGraph`  can
    1. ask answers for the question "what a variable points to ?"
    2. add additional points-to information to the graph. Modification to a graph will cause a re-computation of the graph.

** Inter-Procedural Points-To Analysis
  * Reference:  Emami, Maryam and Ghiya, Rakesh and Hendren, Laurie J. "Context-sensitive inter-procedural points-to analysis in the presence of function pointers"
  * `InvocationGraphNode`:  a node represents a lexical function call in the program.  An invocation graph consists of nodes for all lexical function calls in a program.  
    * A node `n` has multiple children, each of which represents a lexical function call in the function body of the function associated with `n`.  
    * A node `n` also has parent node which represents a lexical call to a function whose body contains the call represented by `n`.  
    * A node `n`  has no child if there is no lexical call in the function body associated with it or it represents a recursive call (i.e., an ancestor of `n` is associated with the same function as `n`).
    * Every `InvocationGraphNode` is associated with a unique instance of a `PointsToGraph`
    * The  inter-procedural analysis traverses the invocation graph and keeps updating the `PointsToGraph` of each node until a fix-point is reached


== Read / Write Analysis ==
*  A read / write record consists of 1) an `entity` or an `allocation/string`;  2) an optional `subscript-indices`
*  Taking use of the result of the points-to analysis, all collected read / write records satisfy the following conditions:
  * if a record contains a meaningful `subscript-indices`, then the `entity` or `allocation/string` in this record must be an array (allocated object and string can be considered as arrays)
  * for the case of `a[x]` where `a` is a pointer,  there are a number of records correspond to `a[x]` each of which contains an `entity` or `allocation/string` that is referred by `a`
  * for now, read / write sets of a function call is over-approximated: a function can read / write everything visible from its function body.

== Todo List ==
* generalizes the two analysis above and puts them into ABC
* extends the points-to analysis for being aware of array elements and struct fields
* extends the read / write analysis with corresponds to the extension of the points-to analysis
* extends the read / write analysis with more precise analysis for function calls