class StratifiedSetsBuilder

Declaration

template <typename T>
class StratifiedSetsBuilder { /* full declaration omitted */ };

Description

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.

Declared at: llvm/lib/Analysis/StratifiedSets.h:173

Templates

T

Method Overview

• public bool add(const T & Main)
• public bool addAbove(const T & Main, const T & ToAdd)
• public bool addBelow(const T & Main, const T & ToAdd)
• public bool addWith(const T & Main, const T & ToAdd)
• public StratifiedSets<T> build()
• public bool has(const T & Elem) const
• public void noteAttributes(const T & Main, llvm::cflaa::AliasAttrs NewAttrs)

Methods

¶bool add(const T& Main)

Declared at: llvm/lib/Analysis/StratifiedSets.h:345

Parameters

const T& Main

¶bool addAbove(const T& Main, const T& ToAdd)

Description

Restructures the stratified sets as necessary to make "ToAdd" in a set above "Main". There are some cases where this is not possible (see above), so we merge them such that ToAdd and Main are in the same set.

Declared at: llvm/lib/Analysis/StratifiedSets.h:356

Parameters

const T& Main

const T& ToAdd

¶bool addBelow(const T& Main, const T& ToAdd)

Description

Restructures the stratified sets as necessary to make "ToAdd" in a set below "Main". There are some cases where this is not possible (see above), so we merge them such that ToAdd and Main are in the same set.

Declared at: llvm/lib/Analysis/StratifiedSets.h:369

Parameters

const T& Main

const T& ToAdd

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

Declared at: llvm/lib/Analysis/StratifiedSets.h:379

Parameters

const T& Main

const T& ToAdd

¶StratifiedSets<T> build()

Description

Builds a StratifiedSet from the information we've been given since either construction or the prior build() call.

Declared at: llvm/lib/Analysis/StratifiedSets.h:335

¶bool has(const T& Elem) const

Declared at: llvm/lib/Analysis/StratifiedSets.h:343

Parameters

const T& Elem

¶void noteAttributes(
    const T& Main,
    llvm::cflaa::AliasAttrs NewAttrs)

Declared at: llvm/lib/Analysis/StratifiedSets.h:385

Parameters

const T& Main

llvm::cflaa::AliasAttrs NewAttrs