LLVM 17.0.0git
llvm::cflaa::StratifiedSetsBuilder< T > Class Template Reference

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

#include "Analysis/StratifiedSets.h"

## Public Member Functions

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

bool has (const T &Elem) const

Restructures the stratified sets as necessary to make "ToAdd" in a set above "Main".

Restructures the stratified sets as necessary to make "ToAdd" in a set below "Main".

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 172 of file StratifiedSets.h.

## Member Function Documentation

template<typename T >
 bool llvm::cflaa::StratifiedSetsBuilder< T >::add ( const T & Main )
inline

Definition at line 344 of file StratifiedSets.h.

template<typename T >
 bool llvm::cflaa::StratifiedSetsBuilder< T >::addAbove ( const T & Main, const T & ToAdd )
inline

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.

Definition at line 355 of file StratifiedSets.h.

References assert(), and llvm::cflaa::StratifiedSetsBuilder< T >::has().

template<typename T >
 bool llvm::cflaa::StratifiedSetsBuilder< T >::addBelow ( const T & Main, const T & ToAdd )
inline

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.

Definition at line 368 of file StratifiedSets.h.

References assert(), and llvm::cflaa::StratifiedSetsBuilder< T >::has().

template<typename T >
 bool llvm::cflaa::StratifiedSetsBuilder< T >::addWith ( const T & Main, const T & ToAdd )
inline

Definition at line 378 of file StratifiedSets.h.

References assert(), and llvm::cflaa::StratifiedSetsBuilder< T >::has().

## ◆ build()

template<typename T >
 StratifiedSets< T > llvm::cflaa::StratifiedSetsBuilder< T >::build ( )
inline

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

Definition at line 334 of file StratifiedSets.h.

## ◆ has()

template<typename T >
 bool llvm::cflaa::StratifiedSetsBuilder< T >::has ( const T & Elem ) const
inline

## ◆ noteAttributes()

template<typename T >
 void llvm::cflaa::StratifiedSetsBuilder< T >::noteAttributes ( const T & Main, AliasAttrs NewAttrs )
inline

Definition at line 384 of file StratifiedSets.h.

References assert(), llvm::cflaa::StratifiedSetsBuilder< T >::has(), and Info.

The documentation for this class was generated from the following file: