Type-Based Alias Analysis
Alias analysis allows compilers to determine which pointers may (or must) refer to the same memory location. This is most useful for the purpose of instruction reordering; if a compiler knows that two memory instructions refer to different memory locations, it can switch the order of the instructions. In Type-Based Alias Analysis, Diwan, McKinley, and Moss propose and evaluate alias analyses for Modula-3 (a type-safe object-oriented language with inheritance) that use type information instead of assignment tracking. Each analysis successively refines the previous: TypeDecl uses only type/subtype compatibility, FieldTypeDecl additionally considers field names and other properties, and SMFieldTypeRefs augments the former with a single pass through the instructions to pick up assignment information. The analyses all do a may-alias analysis; all alias pairs calculated are possible aliases, but all other pairs are confirmed to not be aliases.
Algorithms
The TypeDecl analysis relies on a simple predicate: two memory references
p and q may be aliases if and only if there exists a type that subtypes
both the type of p and the type of q. If such a type did not exist, for
example, then if p and q were aliases, the object they refer to would
have two different, incompatible types.
FieldTypeDecl takes this further by
adding checks for field names, array accesses, and pointer dereferences. For
example, field accesses p.f and q.g may be aliases only if the field
names f and g are exactly the same and p and q themselves may be
aliases. Additionally, a pointer dereference q^ (similar to *q in C) may
alias a field p.f or an array access p[i] only if its address was ever
taken by the program (since otherwise no pointer to it could exist). The
authors define similar checks for combinations of field accesses (or
qualifications), dereferences, and array subscripts, nonempty strings of
which they call access paths, and; these checks may evaluate some condition
on the last memory reference in the access paths and recursively call
FieldTypeDecl or resort to TypeDecl to compare simple pointers (with no
qualifications, dereferences, or subscripts).
Finally, SMFieldTypeRefs uses a simple flow-insensitive pass through the
program’s instructions to merge types that might become aliases. It uses a
table that tracks the equivalence classes for a given type (such that for a
type T with entry {T1, T2, …}, an access path of type T may be a
reference to any T1, T2, …). Upon encountering an assignment from type T1
to a pointer of type T2, it adds T1’s entry to T2’s equivalence class.
Notably, this is an asymmetric operation; the assignment does not change
T1’s equivalence class. This is a more refined version of TypeDecl above,
so by replacing TypeDecl with lookups from this table (called SMTypeRefs
in the paper, for “Selectively Merge Type References”), we have the final
algorithm SMFieldTypeRefs.
Evaluation
The paper does a surprisingly thorough evaluation job considering the paper was written in 1998. The authors observe that previous alias analyses were evaluated by their static properties, like the size of the set of alias pairs, and their dynamic properties, such as the impact of an alias analysis on a compiler optimization that uses it. The static evaluation, performed over a selection of 10 benchmarks, finds that TypeDecl performs much worse than FieldTypeDecl in terms of alias set size, but SMFieldTypeRefs barely improves on FieldTypeDecl at all. It also shows that applying type-based alias analysis interprocedurally generates huge numbers of aliases, rendering this type of analysis infeasible for program-wide optimization.
The authors then proceed to measure the impact of the three different analyses on redundant load elimination, which moves invariant memory references out of loops. They found that the number of redundant loads removed did increase with the power of the analysis and that the amount of optimization improvement between analyses was correlated with how much smaller the alias set became in the static evaluation. On the other hand, when they considered the execution time post-redundant-load-elimination, they found that all three analyses performed similarly, averaging a 4% speedup from RLE. Thus, perhaps counterintuitively, more precision in the alias analysis doesn’t necessarily yield significant gains in runtime speed.
However, the authors note that static properties don’t directly correlate with performance benefits, and don’t lend themselves to comparing two different alias analyses – in both cases, it’s hard to tell whether the disambiguated pointers will be relevant for the intended use case. Dynamic properties, on the other hand, suffer from overspecificity – it’s difficult to evaluate general efficacy of an alias analysis from performance improvements on a few specific optimizations and benchmarks. Worst of all, neither evaluation can give an idea of how much better an analysis could be.
To alleviate these problems, the paper introduces the concept of limit evaluation to figure out whether there were missed optimization opportunities due to undetected aliases. The authors instrumented their benchmarks to record the address and value of every load, allowing them to observe exactly how many aliases there actually are in an execution. This extra step indicated that the TBAA-assisted RLE removed between 37% and 87% of redundant loads, and for 6 out of 8 of the benchmarks only 5% of the remaining loads were redundancies that could be eliminated. Pushing further, the authors even noted that, in the other two benchmarks, the majority of the remaining loads were due to limitations in the RLE implementation, and not a single missed opportunity was due to TBAA failing to disambiguate references. 2.5% of the remaining loads were due to unknown causes, making that an upper bound for the possible improvement.
Ultimately, the evaluations show that though it is easy to come up with examples in which TBAA fails to properly differentiate references, in practice it has very little room for improvement with respect to redundant load elimination. By evaluating on four metrics, the authors were able to draw more nuanced conclusions; for example, a runtime-only evaluation might conclude that TypeDecl is sufficient, but FieldTypeDecl actually yields significantly more opportunities for RLE. The authors also do not state their results in a vacuum; they clearly state that the results are only with respect to one optimization (RLE) and the set of benchmarks they used. However, benchmark diversity and, in this case, optimization diversity is still lacking; the evaluation metrics reveal deep insight about this case, but are not broadly applied.
The significance of this work is not to be understated; alias analyses over types instead of instructions run much more efficiently due to the vastly reduced search space, and the results in paper indicate that the precision tradeoff could be minimal for some applications. From a modern perspective, it seems that compiler developers have come to the same conclusion; many modern compilers implement and support type-based alias analyses for many of their optimization passes. Among these compilers are GCC and LLVM, showing that the benefits have even extended outside the paper’s original realm of type-safe languages.
Discussion
- What are some other ways types can influence and enhance compiler design?
- Are there other useful metrics for evaluating alias or other analyses? How can these metrics be more generally applied?
- How do compilers make tradeoffs between efficiency and efficacy?
- How do researchers make tradeoffs between experimental depth and breadth?