This module implements a simple MIR-path-based alias analysis. Path-based means that the analysis is local and thus that pointer indirections are not followed.
MIR aliases are followed, however. So that the comparison can be implemented efficiently, the path expression is first compiled into a Path object via computePath.
Two compiled Path objects can then be passed to comparePaths. Since there are oftentimes multiple facts one wants to know about when comparing two paths, comparePaths only gathers the necessary information for deriving all the facts.
Whether two lvalues refer to overlapping locations is not always statically known (e.g. when accessing an array with a value only known at run-time) -- if it is not, the uncertainity is communicated via the maybe result.
Types
CmpLocsResult = object endA, endB: bool ## whether the `last` operation of the provided sequences ## was reached overlaps: Ternary
- Source Edit
Path = object root*: NodePosition ## the root node of the path. short: array[6, PathInstr] ## short-sequence-optimization: no dynamic sequence is allocated for ## short paths (which many of them are). shortLen: int ## the number of items in `short`. Zero if the dynamic sequence is used. long: seq[PathInstr]
- Acceleration structure for representing a path expression. This allows for more efficient comparison of paths. Source Edit
Procs
proc compare(body: MirTree; a, b: Path): CmpLocsResult {....raises: [], tags: [].}
- Compares the paths a and b and returns the information to later derive the facts from (e.g.: is A a part B). Source Edit
proc computePath(tree: MirTree; at: NodePosition): Path {....raises: [], tags: [].}
-
Computes the Path for the given expression. The expression not being a path expression is allowed too.
- Locals view are followed as far as possible. Given:
- bind _1 = x.a y = _1.b
the collected path will be x.a.b.
Source Edit proc getRoot(tree: MirTree; n: OpValue): OpValue {....raises: [], tags: [].}
- If n doesn't point to a path expression, returns n, the root of the path otherwise. Aliases are followed. Source Edit
func isAPartOfB(r: CmpLocsResult): Ternary {.inline, ...raises: [], tags: [].}
- Source Edit
func isBPartOfA(r: CmpLocsResult): Ternary {.inline, ...raises: [], tags: [].}
- Source Edit
func isPartOf(tree: MirTree; a, b: Path): Ternary {.inline, ...raises: [], tags: [].}
- Computes if the location named by a is part of b. Also evaluates to 'yes' if both name the exact same location Source Edit
func isSame(r: CmpLocsResult): bool {.inline, ...raises: [], tags: [].}
- Returns whether A and B refer to the exact same location (ignoring the type) Source Edit