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

Member Variables

private DenseMap<T, llvm::cflaa::StratifiedInfo> Values

private std::vector<BuilderLink> Links

Method Overview

• public bool add(const T & Main)
• public bool addAbove(const T & Main, const T & ToAdd)
• private bool addAtMerging(const T & ToAdd, llvm::cflaa::StratifiedIndex Index)
• public bool addBelow(const T & Main, const T & ToAdd)
• private llvm::cflaa::StratifiedIndex addLinkAbove(llvm::cflaa::StratifiedIndex Set)
• private llvm::cflaa::StratifiedIndex addLinkBelow(llvm::cflaa::StratifiedIndex Set)
• private llvm::cflaa::StratifiedIndex addLinks()
• public bool addWith(const T & Main, const T & ToAdd)
• public StratifiedSets<T> build()
• private void finalizeSets(std::vector<StratifiedLink> & StratLinks)
• private Optional<const llvm::cflaa::StratifiedInfo *> get(const T & Val) const
• private Optional<llvm::cflaa::StratifiedInfo *> get(const T & Val)
• private llvm::cflaa::StratifiedIndex getNewUnlinkedIndex()
• public bool has(const T & Elem) const
• private bool inbounds(llvm::cflaa::StratifiedIndex N) const
• private Optional<llvm::cflaa::StratifiedIndex> indexOf(const T & Val)
• private llvm::cflaa::StratifiedSetsBuilder::BuilderLink & linksAt(llvm::cflaa::StratifiedIndex Index)
• private void merge(llvm::cflaa::StratifiedIndex Idx1, llvm::cflaa::StratifiedIndex Idx2)
• private void mergeDirect(llvm::cflaa::StratifiedIndex Idx1, llvm::cflaa::StratifiedIndex Idx2)
• public void noteAttributes(const T & Main, llvm::cflaa::AliasAttrs NewAttrs)
• private static void propagateAttrs(std::vector<StratifiedLink> & Links)
• private bool tryMergeUpwards(llvm::cflaa::StratifiedIndex LowerIndex, llvm::cflaa::StratifiedIndex UpperIndex)

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 addAtMerging(
    const T& ToAdd,
    llvm::cflaa::StratifiedIndex Index)

Description

Adds the given element at the given index, merging sets if necessary.

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

Parameters

const T& ToAdd

llvm::cflaa::StratifiedIndex Index

¶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

¶llvm::cflaa::StratifiedIndex addLinkAbove(
    llvm::cflaa::StratifiedIndex Set)

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

Parameters

llvm::cflaa::StratifiedIndex Set

¶llvm::cflaa::StratifiedIndex addLinkBelow(
    llvm::cflaa::StratifiedIndex Set)

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

Parameters

llvm::cflaa::StratifiedIndex Set

¶llvm::cflaa::StratifiedIndex addLinks()

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

¶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

¶void finalizeSets(
    std::vector<StratifiedLink>& StratLinks)

Description

This function performs all of the set unioning/value renumbering that we've been putting off, and generates a vector <StratifiedLink > that may be placed in a StratifiedSets instance.

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

Parameters

std::vector<StratifiedLink>& StratLinks

¶Optional<const llvm::cflaa::StratifiedInfo*> get(
    const T& Val) const

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

Parameters

const T& Val

¶Optional<llvm::cflaa::StratifiedInfo*> get(
    const T& Val)

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

Parameters

const T& Val

¶llvm::cflaa::StratifiedIndex getNewUnlinkedIndex()

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

¶bool has(const T& Elem) const

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

Parameters

const T& Elem

¶bool inbounds(
    llvm::cflaa::StratifiedIndex N) const

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

Parameters

llvm::cflaa::StratifiedIndex N

¶Optional<llvm::cflaa::StratifiedIndex> indexOf(
    const T& Val)

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

Parameters

const T& Val

¶llvm::cflaa::StratifiedSetsBuilder::BuilderLink&
linksAt(llvm::cflaa::StratifiedIndex Index)

Description

Gets the BuilderLink at the given index, taking set remapping into account.

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

Parameters

llvm::cflaa::StratifiedIndex Index

¶void merge(llvm::cflaa::StratifiedIndex Idx1,
           llvm::cflaa::StratifiedIndex Idx2)

Description

Merges two sets into one another. Assumes that these sets are not already one in the same.

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

Parameters

llvm::cflaa::StratifiedIndex Idx1

llvm::cflaa::StratifiedIndex Idx2

¶void mergeDirect(
    llvm::cflaa::StratifiedIndex Idx1,
    llvm::cflaa::StratifiedIndex Idx2)

Description

Merges two sets assuming that the set at `Idx1` is unreachable from traversing above or below the set at `Idx2`.

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

Parameters

llvm::cflaa::StratifiedIndex Idx1

llvm::cflaa::StratifiedIndex Idx2

¶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

¶static void propagateAttrs(
    std::vector<StratifiedLink>& Links)

Description

There's a guarantee in StratifiedLink where all bits set in a Link.externals will be set in all Link.externals "below" it.

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

Parameters

std::vector<StratifiedLink>& Links

¶bool tryMergeUpwards(
    llvm::cflaa::StratifiedIndex LowerIndex,
    llvm::cflaa::StratifiedIndex UpperIndex)

Description

Checks to see if lowerIndex is at a level lower than upperIndex. If so, it will merge lowerIndex with upperIndex (and all of the sets between) and return true. Otherwise, it will return false.

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

Parameters

llvm::cflaa::StratifiedIndex LowerIndex

llvm::cflaa::StratifiedIndex UpperIndex