Understanding the need for additional metadata – Advanced IR Generation-2

With these definitions, we can now define a relation on the access tags, which is used to evaluate if two pointers may alias each other or not. Let’s take a closer look at the options for the immediate parent of a (base type, offset) tuple:

1. If the base type is a scalar type and the offset is 0, then the immediate parent is (parent type, 0), with the parent type being the type of the parent node, as defined in the type hierarchy. If the offset is not 0, then the immediate parent is undefined.
2. If the base type is an aggregate type, then the immediate parent of the (base type, offset) tuple is the (new type, new offset) tuple, with the new type being the type of the member at offset. The new offset is the offset of the new type, adjusted to its new start.

The transitive closure of this relation is the parent relation. Two memory accesses, (base type 1, access type 1, offset 1) and (base type 2, access type 2, offset 2), may alias one another if (base type 1, offset 1) and (base type 2, offset 2) or vice versa are related in the parent relation.

Let’s illustrate this with an example:
struct Point { float x, y; }
void func(struct Point *p, float *x, int *i, char *c) {
  p->x = 0; p->y = 0; *x = 0.0; *i = 0; *c = 0;
}

When using the memory access tag definition for scalar types, the access tag for the i parameter is (int, int, 0), while for the c parameter, it is (char, char, 0). In the type hierarchy, the parent of the node for the int type is the char node. Therefore, the immediate parent of (int, 0) is (char, 0) and both pointers can alias. The same is true for the x and c parameters. However, the x and i parameters are not related, so they do not alias each other. The access for the y member of struct Point is (Point, float, 4), with 4 being the offset of the y member in the struct. The immediate parent of (Point, 4) is (float, 0), so the access to p->y and x may alias, and with the same reasoning also with the c parameter.