LLVM  6.0.0svn
Classes | Public Member Functions | List of all members
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. 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:

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.

Member Function Documentation

◆ add()

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

◆ addAbove()

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

References assert(), and llvm::cflaa::StratifiedInfo::Index.

◆ addBelow()

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

References assert(), and llvm::cflaa::StratifiedInfo::Index.

Referenced by llvm::CFLSteensAAResult::FunctionInfo::FunctionInfo().

◆ addWith()

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

Definition at line 380 of file StratifiedSets.h.

References assert().

Referenced by llvm::CFLSteensAAResult::FunctionInfo::FunctionInfo().

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

Referenced by llvm::CFLSteensAAResult::FunctionInfo::FunctionInfo().

◆ has()

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

Definition at line 344 of file StratifiedSets.h.

◆ noteAttributes()

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

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