Pointer analysis and store forwarding (remove loads after writes)

[rtjoa]

Key types and relations

PtrPointees represents where a single pointer can point. The List<i64+IntInterval> is used as an association list; the i64 keys (corresponding to alloc ids) are always unique and sorted, the IntInterval values correspond to offset ranges.

(datatype PtrPointees
  (PointsTo List<i64+IntInterval>)
  (PointsAnywhere))

Pointees represents where an Expr can point to.

(datatype Pointees
  (TuplePointsTo List<PtrPointees>)
  (PtrPointsTo PtrPointees))

As an example: (TuplePointsTo [(PointsTo {0->[4,5], 1->[0,0]}), (PointsAnywhere)]) indicates a tuple with two components.

• The first component might point to Alloc 0 at offset 4 or 5 or Alloc 1 at offset 0.
• The second component might point anywhere.

The key function of the pointer analysis is:

(function PointsToCells (Expr Pointees) Pointees)

(= pointees (PointsToCells e arg-pointees)) indicates that when the (Arg) contained in e points to arg-pointees, e points to pointees.

Example optimization

This corresponds to test pqrs_deep_loop_swap:

p = alloc(alloc_id, 4, int*)
q = ptradd(p, 1)
r = ptradd(p, 2)
s = ptradd(p, 3)
// Note (p, r), (p, s), (q, r), (q, s) don't alias
do {
  do {
    p, q = q, p
  } while true;
  r, s = r, s
} while true;
// (p, r), (p, s), (q, r), (q, s) still shouldn't alias
*p = 10
*r = 20

return *p // should be unioned with 10, as p and r don't alias