Generic Builder class that produces StratifiedSets instances. More...

#include "Analysis/StratifiedSets.h"

Public Member Functions
StratifiedSets< T >	build ()
	Builds a StratifiedSet from the information we've been given since either construction or the prior build() call. More...

bool	has (const T &Elem) const

bool	add (const T &Main)

bool	addAbove (const T &Main, const T &ToAdd)
	Restructures the stratified sets as necessary to make "ToAdd" in a set above "Main". More...

bool	addBelow (const T &Main, const T &ToAdd)
	Restructures the stratified sets as necessary to make "ToAdd" in a set below "Main". More...

bool	addWith (const T &Main, const T &ToAdd)

void	noteAttributes (const T &Main, AliasAttrs NewAttrs)

Detailed Description

template<typename T>
class llvm::cflaa::StratifiedSetsBuilder< T >

Generic Builder class that produces StratifiedSets instances.

The goal of this builder is to efficiently produce correct StratifiedSets instances. To this end, we use a few tricks:

Set chains (A method for linking sets together) Set remaps (A method for marking a set as an alias [irony?] of another)

==== Set chains ==== This builder has a notion of some value A being above, below, or with some other value B:

The A above B relationship implies that there is a reference edge

going from A to B. Namely, it notes that A can store anything in B's set.

The A below B relationship is the opposite of A above B. It implies

that there's a dereference edge going from A to B.

The A with B relationship states that there's an assignment edge going

from A to B, and that A and B should be treated as equals.

As an example, take the following code snippet:

a = alloca i32, align 4 ap = alloca i32*, align 8 app = alloca i32**, align 8 store a, ap store ap, app aw = getelementptr ap, i32 0

Given this, the following relations exist:

a below ap & ap above a
ap below app & app above ap
aw with ap & ap with aw

These relations produce the following sets: [{a}, {ap, aw}, {app}]

...Which state that the only MayAlias relationship in the above program is between ap and aw.

Because LLVM allows arbitrary casts, code like the following needs to be supported: ip = alloca i64, align 8 ipp = alloca i64*, align 8 i = bitcast i64** ipp to i64 store i64* ip, i64** ipp store i64 i, i64* ip

Which, because ipp ends up both above and below ip, is fun.

This is solved by merging i and ipp into a single set (...which is the only way to solve this, since their bit patterns are equivalent). Any sets that ended up in between i and ipp at the time of merging (in this case, the set containing ip) also get conservatively merged into the set of i and ipp. In short, the resulting StratifiedSet from the above code would be {ip, ipp, i}.

==== Set remaps ==== More of an implementation detail than anything – when merging sets, we need to update the numbers of all of the elements mapped to those sets. Rather than doing this at each merge, we note in the BuilderLink structure that a remap has occurred, and use this information so we can defer renumbering set elements until build time.

Definition at line 174 of file StratifiedSets.h.