This is an archive of the discontinued LLVM Phabricator instance.

Differential D150748

[Analysis] Remove AliasAnalysisSummary.cpp
ClosedPublic

Authored by kazu on May 16 2023, 7:49 PM.

Details

Reviewers
nikic
Commits
rG7f3047219cf5: [Analysis] Remove AliasAnalysisSummary.cpp
Summary

The last use was removed by:

commit 8005332835246c54a4a6b026eede930ed559deb4
Author: Nikita Popov <npopov@redhat.com>
Date:   Fri Dec 9 11:57:50 2022 +0100

Diff Detail

Event Timeline

kazu created this revision.May 16 2023, 7:49 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 16 2023, 7:49 PM
Herald added subscribers: jeroen.dobbelaere, hiraditya. · View Herald Transcript
kazu requested review of this revision.May 16 2023, 7:49 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 16 2023, 7:49 PM
Herald added a subscriber: llvm-commits. · View Herald Transcript
kazu added a reviewer: nikic.May 16 2023, 7:49 PM
Herald added a subscriber: StephenFan. · View Herald TranscriptMay 16 2023, 7:49 PM
Harbormaster completed remote builds in B232492: Diff 522885.May 16 2023, 8:26 PM
nikic accepted this revision.May 17 2023, 1:36 AM

LGTM

This revision is now accepted and ready to land.May 17 2023, 1:36 AM
Closed by commit rG7f3047219cf5: [Analysis] Remove AliasAnalysisSummary.cpp (authored by kazu). · Explain WhyMay 17 2023, 8:40 AM
This revision was automatically updated to reflect the committed changes.
kazu added a commit: rG7f3047219cf5: [Analysis] Remove AliasAnalysisSummary.cpp.

Revision Contents

Diff 523066

llvm/lib/Analysis/AliasAnalysisSummary.h

  • This file was deleted.
//=====- CFLSummary.h - Abstract stratified sets implementation. --------=====//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
/// \file
/// This file defines various utility types and functions useful to
/// summary-based alias analysis.
///
/// Summary-based analysis, also known as bottom-up analysis, is a style of
/// interprocedrual static analysis that tries to analyze the callees before the
/// callers get analyzed. The key idea of summary-based analysis is to first
/// process each function independently, outline its behavior in a condensed
/// summary, and then instantiate the summary at the callsite when the said
/// function is called elsewhere. This is often in contrast to another style
/// called top-down analysis, in which callers are always analyzed first before
/// the callees.
///
/// In a summary-based analysis, functions must be examined independently and
/// out-of-context. We have no information on the state of the memory, the
/// arguments, the global values, and anything else external to the function. To
/// carry out the analysis conservative assumptions have to be made about those
/// external states. In exchange for the potential loss of precision, the
/// summary we obtain this way is highly reusable, which makes the analysis
/// easier to scale to large programs even if carried out context-sensitively.
///
/// Currently, all CFL-based alias analyses adopt the summary-based approach
/// and therefore heavily rely on this header.
///
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_ALIASANALYSISSUMMARY_H
#define LLVM_ANALYSIS_ALIASANALYSISSUMMARY_H
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/SmallVector.h"
#include <bitset>
#include <optional>
namespace llvm {
class CallBase;
class Value;
namespace cflaa {
//===----------------------------------------------------------------------===//
// AliasAttr related stuffs
//===----------------------------------------------------------------------===//
/// The number of attributes that AliasAttr should contain. Attributes are
/// described below, and 32 was an arbitrary choice because it fits nicely in 32
/// bits (because we use a bitset for AliasAttr).
static const unsigned NumAliasAttrs = 32;
/// These are attributes that an alias analysis can use to mark certain special
/// properties of a given pointer. Refer to the related functions below to see
/// what kinds of attributes are currently defined.
typedef std::bitset<NumAliasAttrs> AliasAttrs;
/// Attr represent whether the said pointer comes from an unknown source
/// (such as opaque memory or an integer cast).
AliasAttrs getAttrNone();
/// AttrUnknown represent whether the said pointer comes from a source not known
/// to alias analyses (such as opaque memory or an integer cast).
AliasAttrs getAttrUnknown();
bool hasUnknownAttr(AliasAttrs);
/// AttrCaller represent whether the said pointer comes from a source not known
/// to the current function but known to the caller. Values pointed to by the
/// arguments of the current function have this attribute set
AliasAttrs getAttrCaller();
bool hasCallerAttr(AliasAttrs);
bool hasUnknownOrCallerAttr(AliasAttrs);
/// AttrEscaped represent whether the said pointer comes from a known source but
/// escapes to the unknown world (e.g. casted to an integer, or passed as an
/// argument to opaque function). Unlike non-escaped pointers, escaped ones may
/// alias pointers coming from unknown sources.
AliasAttrs getAttrEscaped();
bool hasEscapedAttr(AliasAttrs);
/// AttrGlobal represent whether the said pointer is a global value.
/// AttrArg represent whether the said pointer is an argument, and if so, what
/// index the argument has.
AliasAttrs getGlobalOrArgAttrFromValue(const Value &);
bool isGlobalOrArgAttr(AliasAttrs);
/// Given an AliasAttrs, return a new AliasAttrs that only contains attributes
/// meaningful to the caller. This function is primarily used for
/// interprocedural analysis
/// Currently, externally visible AliasAttrs include AttrUnknown, AttrGlobal,
/// and AttrEscaped
AliasAttrs getExternallyVisibleAttrs(AliasAttrs);
//===----------------------------------------------------------------------===//
// Function summary related stuffs
//===----------------------------------------------------------------------===//
/// The maximum number of arguments we can put into a summary.
static const unsigned MaxSupportedArgsInSummary = 50;
/// We use InterfaceValue to describe parameters/return value, as well as
/// potential memory locations that are pointed to by parameters/return value,
/// of a function.
/// Index is an integer which represents a single parameter or a return value.
/// When the index is 0, it refers to the return value. Non-zero index i refers
/// to the i-th parameter.
/// DerefLevel indicates the number of dereferences one must perform on the
/// parameter/return value to get this InterfaceValue.
struct InterfaceValue {
unsigned Index;
unsigned DerefLevel;
};
inline bool operator==(InterfaceValue LHS, InterfaceValue RHS) {
return LHS.Index == RHS.Index && LHS.DerefLevel == RHS.DerefLevel;
}
inline bool operator!=(InterfaceValue LHS, InterfaceValue RHS) {
return !(LHS == RHS);
}
inline bool operator<(InterfaceValue LHS, InterfaceValue RHS) {
return LHS.Index < RHS.Index ||
(LHS.Index == RHS.Index && LHS.DerefLevel < RHS.DerefLevel);
}
inline bool operator>(InterfaceValue LHS, InterfaceValue RHS) {
return RHS < LHS;
}
inline bool operator<=(InterfaceValue LHS, InterfaceValue RHS) {
return !(RHS < LHS);
}
inline bool operator>=(InterfaceValue LHS, InterfaceValue RHS) {
return !(LHS < RHS);
}
// We use UnknownOffset to represent pointer offsets that cannot be determined
// at compile time. Note that MemoryLocation::UnknownSize cannot be used here
// because we require a signed value.
static const int64_t UnknownOffset = INT64_MAX;
inline int64_t addOffset(int64_t LHS, int64_t RHS) {
if (LHS == UnknownOffset || RHS == UnknownOffset)
return UnknownOffset;
// FIXME: Do we need to guard against integer overflow here?
return LHS + RHS;
}
/// We use ExternalRelation to describe an externally visible aliasing relations
/// between parameters/return value of a function.
struct ExternalRelation {
InterfaceValue From, To;
int64_t Offset;
};
inline bool operator==(ExternalRelation LHS, ExternalRelation RHS) {
return LHS.From == RHS.From && LHS.To == RHS.To && LHS.Offset == RHS.Offset;
}
inline bool operator!=(ExternalRelation LHS, ExternalRelation RHS) {
return !(LHS == RHS);
}
inline bool operator<(ExternalRelation LHS, ExternalRelation RHS) {
if (LHS.From < RHS.From)
return true;
if (LHS.From > RHS.From)
return false;
if (LHS.To < RHS.To)
return true;
if (LHS.To > RHS.To)
return false;
return LHS.Offset < RHS.Offset;
}
inline bool operator>(ExternalRelation LHS, ExternalRelation RHS) {
return RHS < LHS;
}
inline bool operator<=(ExternalRelation LHS, ExternalRelation RHS) {
return !(RHS < LHS);
}
inline bool operator>=(ExternalRelation LHS, ExternalRelation RHS) {
return !(LHS < RHS);
}
/// We use ExternalAttribute to describe an externally visible AliasAttrs
/// for parameters/return value.
struct ExternalAttribute {
InterfaceValue IValue;
AliasAttrs Attr;
};
/// AliasSummary is just a collection of ExternalRelation and ExternalAttribute
struct AliasSummary {
// RetParamRelations is a collection of ExternalRelations.
SmallVector<ExternalRelation, 8> RetParamRelations;
// RetParamAttributes is a collection of ExternalAttributes.
SmallVector<ExternalAttribute, 8> RetParamAttributes;
};
/// This is the result of instantiating InterfaceValue at a particular call
struct InstantiatedValue {
Value *Val;
unsigned DerefLevel;
};
std::optional<InstantiatedValue>
instantiateInterfaceValue(InterfaceValue IValue, CallBase &Call);
inline bool operator==(InstantiatedValue LHS, InstantiatedValue RHS) {
return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
}
inline bool operator!=(InstantiatedValue LHS, InstantiatedValue RHS) {
return !(LHS == RHS);
}
inline bool operator<(InstantiatedValue LHS, InstantiatedValue RHS) {
return std::less<Value *>()(LHS.Val, RHS.Val) ||
(LHS.Val == RHS.Val && LHS.DerefLevel < RHS.DerefLevel);
}
inline bool operator>(InstantiatedValue LHS, InstantiatedValue RHS) {
return RHS < LHS;
}
inline bool operator<=(InstantiatedValue LHS, InstantiatedValue RHS) {
return !(RHS < LHS);
}
inline bool operator>=(InstantiatedValue LHS, InstantiatedValue RHS) {
return !(LHS < RHS);
}
/// This is the result of instantiating ExternalRelation at a particular
/// callsite
struct InstantiatedRelation {
InstantiatedValue From, To;
int64_t Offset;
};
std::optional<InstantiatedRelation>
instantiateExternalRelation(ExternalRelation ERelation, CallBase &Call);
/// This is the result of instantiating ExternalAttribute at a particular
/// callsite
struct InstantiatedAttr {
InstantiatedValue IValue;
AliasAttrs Attr;
};
std::optional<InstantiatedAttr>
instantiateExternalAttribute(ExternalAttribute EAttr, CallBase &Call);
}
template <> struct DenseMapInfo<cflaa::InstantiatedValue> {
static inline cflaa::InstantiatedValue getEmptyKey() {
return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getEmptyKey(),
DenseMapInfo<unsigned>::getEmptyKey()};
}
static inline cflaa::InstantiatedValue getTombstoneKey() {
return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getTombstoneKey(),
DenseMapInfo<unsigned>::getTombstoneKey()};
}
static unsigned getHashValue(const cflaa::InstantiatedValue &IV) {
return DenseMapInfo<std::pair<Value *, unsigned>>::getHashValue(
std::make_pair(IV.Val, IV.DerefLevel));
}
static bool isEqual(const cflaa::InstantiatedValue &LHS,
const cflaa::InstantiatedValue &RHS) {
return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
}
};
}
#endif

llvm/lib/Analysis/AliasAnalysisSummary.cpp

  • This file was deleted.
#include "AliasAnalysisSummary.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Type.h"
#include "llvm/Support/Compiler.h"
namespace llvm {
namespace cflaa {
namespace {
const unsigned AttrEscapedIndex = 0;
const unsigned AttrUnknownIndex = 1;
const unsigned AttrGlobalIndex = 2;
const unsigned AttrCallerIndex = 3;
const unsigned AttrFirstArgIndex = 4;
const unsigned AttrLastArgIndex = NumAliasAttrs;
const unsigned AttrMaxNumArgs = AttrLastArgIndex - AttrFirstArgIndex;
// It would be *slightly* prettier if we changed these to AliasAttrs, but it
// seems that both GCC and MSVC emit dynamic initializers for const bitsets.
using AliasAttr = unsigned;
const AliasAttr AttrNone = 0;
const AliasAttr AttrEscaped = 1 << AttrEscapedIndex;
const AliasAttr AttrUnknown = 1 << AttrUnknownIndex;
const AliasAttr AttrGlobal = 1 << AttrGlobalIndex;
const AliasAttr AttrCaller = 1 << AttrCallerIndex;
const AliasAttr ExternalAttrMask = AttrEscaped | AttrUnknown | AttrGlobal;
}
AliasAttrs getAttrNone() { return AttrNone; }
AliasAttrs getAttrUnknown() { return AttrUnknown; }
bool hasUnknownAttr(AliasAttrs Attr) { return Attr.test(AttrUnknownIndex); }
AliasAttrs getAttrCaller() { return AttrCaller; }
bool hasCallerAttr(AliasAttrs Attr) { return Attr.test(AttrCaller); }
bool hasUnknownOrCallerAttr(AliasAttrs Attr) {
return Attr.test(AttrUnknownIndex) || Attr.test(AttrCallerIndex);
}
AliasAttrs getAttrEscaped() { return AttrEscaped; }
bool hasEscapedAttr(AliasAttrs Attr) { return Attr.test(AttrEscapedIndex); }
static AliasAttr argNumberToAttr(unsigned ArgNum) {
if (ArgNum >= AttrMaxNumArgs)
return AttrUnknown;
// N.B. MSVC complains if we use `1U` here, since AliasAttr' ctor takes
// an unsigned long long.
return AliasAttr(1ULL << (ArgNum + AttrFirstArgIndex));
}
AliasAttrs getGlobalOrArgAttrFromValue(const Value &Val) {
if (isa<GlobalValue>(Val))
return AttrGlobal;
if (auto *Arg = dyn_cast<Argument>(&Val))
// Only pointer arguments should have the argument attribute,
// because things can't escape through scalars without us seeing a
// cast, and thus, interaction with them doesn't matter.
if (!Arg->hasNoAliasAttr() && Arg->getType()->isPointerTy())
return argNumberToAttr(Arg->getArgNo());
return AttrNone;
}
bool isGlobalOrArgAttr(AliasAttrs Attr) {
return Attr.reset(AttrEscapedIndex)
.reset(AttrUnknownIndex)
.reset(AttrCallerIndex)
.any();
}
AliasAttrs getExternallyVisibleAttrs(AliasAttrs Attr) {
return Attr & AliasAttrs(ExternalAttrMask);
}
std::optional<InstantiatedValue>
instantiateInterfaceValue(InterfaceValue IValue, CallBase &Call) {
auto Index = IValue.Index;
auto *V = (Index == 0) ? &Call : Call.getArgOperand(Index - 1);
if (V->getType()->isPointerTy())
return InstantiatedValue{V, IValue.DerefLevel};
return std::nullopt;
}
std::optional<InstantiatedRelation>
instantiateExternalRelation(ExternalRelation ERelation, CallBase &Call) {
auto From = instantiateInterfaceValue(ERelation.From, Call);
if (!From)
return std::nullopt;
auto To = instantiateInterfaceValue(ERelation.To, Call);
if (!To)
return std::nullopt;
return InstantiatedRelation{*From, *To, ERelation.Offset};
}
std::optional<InstantiatedAttr>
instantiateExternalAttribute(ExternalAttribute EAttr, CallBase &Call) {
auto Value = instantiateInterfaceValue(EAttr.IValue, Call);
if (!Value)
return std::nullopt;
return InstantiatedAttr{*Value, EAttr.Attr};
}
}
}

llvm/lib/Analysis/CMakeLists.txt

Show All 20 Lines if (LLVM_HAVE_TFLITE)
list(APPEND MLLinkDeps list(APPEND MLLinkDeps
tensorflow-lite::tensorflow-lite) tensorflow-lite::tensorflow-lite)
endif() endif()
endif() endif()
add_llvm_component_library(LLVMAnalysis add_llvm_component_library(LLVMAnalysis
AliasAnalysis.cpp AliasAnalysis.cpp
AliasAnalysisEvaluator.cpp AliasAnalysisEvaluator.cpp
AliasAnalysisSummary.cpp
AliasSetTracker.cpp AliasSetTracker.cpp
Analysis.cpp Analysis.cpp
AssumeBundleQueries.cpp AssumeBundleQueries.cpp
AssumptionCache.cpp AssumptionCache.cpp
BasicAliasAnalysis.cpp BasicAliasAnalysis.cpp
BlockFrequencyInfo.cpp BlockFrequencyInfo.cpp
BlockFrequencyInfoImpl.cpp BlockFrequencyInfoImpl.cpp
BranchProbabilityInfo.cpp BranchProbabilityInfo.cpp
▲ Show 20 Lines • Show All 127 Lines • Show Last 20 Lines

llvm/lib/Analysis/StratifiedSets.h

  • This file was deleted.
//===- StratifiedSets.h - Abstract stratified sets implementation. --------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ADT_STRATIFIEDSETS_H
#define LLVM_ADT_STRATIFIEDSETS_H
#include "AliasAnalysisSummary.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include <bitset>
#include <cassert>
#include <cmath>
#include <type_traits>
#include <utility>
#include <vector>
namespace llvm {
namespace cflaa {
/// An index into Stratified Sets.
typedef unsigned StratifiedIndex;
/// NOTE: ^ This can't be a short -- bootstrapping clang has a case where
/// ~1M sets exist.
// Container of information related to a value in a StratifiedSet.
struct StratifiedInfo {
StratifiedIndex Index;
/// For field sensitivity, etc. we can tack fields on here.
};
/// A "link" between two StratifiedSets.
struct StratifiedLink {
/// This is a value used to signify "does not exist" where the
/// StratifiedIndex type is used.
///
/// This is used instead of std::optional<StratifiedIndex> because
/// std::optional<StratifiedIndex> would eat up a considerable amount of extra
/// memory, after struct padding/alignment is taken into account.
static const StratifiedIndex SetSentinel;
/// The index for the set "above" current
StratifiedIndex Above;
/// The link for the set "below" current
StratifiedIndex Below;
/// Attributes for these StratifiedSets.
AliasAttrs Attrs;
StratifiedLink() : Above(SetSentinel), Below(SetSentinel) {}
bool hasBelow() const { return Below != SetSentinel; }
bool hasAbove() const { return Above != SetSentinel; }
void clearBelow() { Below = SetSentinel; }
void clearAbove() { Above = SetSentinel; }
};
/// These are stratified sets, as described in "Fast algorithms for
/// Dyck-CFL-reachability with applications to Alias Analysis" by Zhang Q, Lyu M
/// R, Yuan H, and Su Z. -- in short, this is meant to represent different sets
/// of Value*s. If two Value*s are in the same set, or if both sets have
/// overlapping attributes, then the Value*s are said to alias.
///
/// Sets may be related by position, meaning that one set may be considered as
/// above or below another. In CFL Alias Analysis, this gives us an indication
/// of how two variables are related; if the set of variable A is below a set
/// containing variable B, then at some point, a variable that has interacted
/// with B (or B itself) was either used in order to extract the variable A, or
/// was used as storage of variable A.
///
/// Sets may also have attributes (as noted above). These attributes are
/// generally used for noting whether a variable in the set has interacted with
/// a variable whose origins we don't quite know (i.e. globals/arguments), or if
/// the variable may have had operations performed on it (modified in a function
/// call). All attributes that exist in a set A must exist in all sets marked as
/// below set A.
template <typename T> class StratifiedSets {
public:
StratifiedSets() = default;
StratifiedSets(StratifiedSets &&) = default;
StratifiedSets &operator=(StratifiedSets &&) = default;
StratifiedSets(DenseMap<T, StratifiedInfo> Map,
std::vector<StratifiedLink> Links)
: Values(std::move(Map)), Links(std::move(Links)) {}
std::optional<StratifiedInfo> find(const T &Elem) const {
auto Iter = Values.find(Elem);
if (Iter == Values.end())
return std::nullopt;
return Iter->second;
}
const StratifiedLink &getLink(StratifiedIndex Index) const {
assert(inbounds(Index));
return Links[Index];
}
private:
DenseMap<T, StratifiedInfo> Values;
std::vector<StratifiedLink> Links;
bool inbounds(StratifiedIndex Idx) const { return Idx < Links.size(); }
};
/// 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.
template <typename T> class StratifiedSetsBuilder {
/// Represents a Stratified Set, with information about the Stratified
/// Set above it, the set below it, and whether the current set has been
/// remapped to another.
struct BuilderLink {
const StratifiedIndex Number;
BuilderLink(StratifiedIndex N) : Number(N) {
Remap = StratifiedLink::SetSentinel;
}
bool hasAbove() const {
assert(!isRemapped());
return Link.hasAbove();
}
bool hasBelow() const {
assert(!isRemapped());
return Link.hasBelow();
}
void setBelow(StratifiedIndex I) {
assert(!isRemapped());
Link.Below = I;
}
void setAbove(StratifiedIndex I) {
assert(!isRemapped());
Link.Above = I;
}
void clearBelow() {
assert(!isRemapped());
Link.clearBelow();
}
void clearAbove() {
assert(!isRemapped());
Link.clearAbove();
}
StratifiedIndex getBelow() const {
assert(!isRemapped());
assert(hasBelow());
return Link.Below;
}
StratifiedIndex getAbove() const {
assert(!isRemapped());
assert(hasAbove());
return Link.Above;
}
AliasAttrs getAttrs() {
assert(!isRemapped());
return Link.Attrs;
}
void setAttrs(AliasAttrs Other) {
assert(!isRemapped());
Link.Attrs |= Other;
}
bool isRemapped() const { return Remap != StratifiedLink::SetSentinel; }
/// For initial remapping to another set
void remapTo(StratifiedIndex Other) {
assert(!isRemapped());
Remap = Other;
}
StratifiedIndex getRemapIndex() const {
assert(isRemapped());
return Remap;
}
/// Should only be called when we're already remapped.
void updateRemap(StratifiedIndex Other) {
assert(isRemapped());
Remap = Other;
}
/// Prefer the above functions to calling things directly on what's returned
/// from this -- they guard against unexpected calls when the current
/// BuilderLink is remapped.
const StratifiedLink &getLink() const { return Link; }
private:
StratifiedLink Link;
StratifiedIndex Remap;
};
/// 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.
void finalizeSets(std::vector<StratifiedLink> &StratLinks) {
DenseMap<StratifiedIndex, StratifiedIndex> Remaps;
for (auto &Link : Links) {
if (Link.isRemapped())
continue;
StratifiedIndex Number = StratLinks.size();
Remaps.insert(std::make_pair(Link.Number, Number));
StratLinks.push_back(Link.getLink());
}
for (auto &Link : StratLinks) {
if (Link.hasAbove()) {
auto &Above = linksAt(Link.Above);
auto Iter = Remaps.find(Above.Number);
assert(Iter != Remaps.end());
Link.Above = Iter->second;
}
if (Link.hasBelow()) {
auto &Below = linksAt(Link.Below);
auto Iter = Remaps.find(Below.Number);
assert(Iter != Remaps.end());
Link.Below = Iter->second;
}
}
for (auto &Pair : Values) {
auto &Info = Pair.second;
auto &Link = linksAt(Info.Index);
auto Iter = Remaps.find(Link.Number);
assert(Iter != Remaps.end());
Info.Index = Iter->second;
}
}
/// There's a guarantee in StratifiedLink where all bits set in a
/// Link.externals will be set in all Link.externals "below" it.
static void propagateAttrs(std::vector<StratifiedLink> &Links) {
const auto getHighestParentAbove = [&Links](StratifiedIndex Idx) {
const auto *Link = &Links[Idx];
while (Link->hasAbove()) {
Idx = Link->Above;
Link = &Links[Idx];
}
return Idx;
};
SmallSet<StratifiedIndex, 16> Visited;
for (unsigned I = 0, E = Links.size(); I < E; ++I) {
auto CurrentIndex = getHighestParentAbove(I);
if (!Visited.insert(CurrentIndex).second)
continue;
while (Links[CurrentIndex].hasBelow()) {
auto &CurrentBits = Links[CurrentIndex].Attrs;
auto NextIndex = Links[CurrentIndex].Below;
auto &NextBits = Links[NextIndex].Attrs;
NextBits |= CurrentBits;
CurrentIndex = NextIndex;
}
}
}
public:
/// Builds a StratifiedSet from the information we've been given since either
/// construction or the prior build() call.
StratifiedSets<T> build() {
std::vector<StratifiedLink> StratLinks;
finalizeSets(StratLinks);
propagateAttrs(StratLinks);
Links.clear();
return StratifiedSets<T>(std::move(Values), std::move(StratLinks));
}
bool has(const T &Elem) const { return get(Elem).has_value(); }
bool add(const T &Main) {
if (get(Main))
return false;
auto NewIndex = getNewUnlinkedIndex();
return addAtMerging(Main, NewIndex);
}
/// 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.
bool addAbove(const T &Main, const T &ToAdd) {
assert(has(Main));
auto Index = *indexOf(Main);
if (!linksAt(Index).hasAbove())
addLinkAbove(Index);
auto Above = linksAt(Index).getAbove();
return addAtMerging(ToAdd, Above);
}
/// 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.
bool addBelow(const T &Main, const T &ToAdd) {
assert(has(Main));
auto Index = *indexOf(Main);
if (!linksAt(Index).hasBelow())
addLinkBelow(Index);
auto Below = linksAt(Index).getBelow();
return addAtMerging(ToAdd, Below);
}
bool addWith(const T &Main, const T &ToAdd) {
assert(has(Main));
auto MainIndex = *indexOf(Main);
return addAtMerging(ToAdd, MainIndex);
}
void noteAttributes(const T &Main, AliasAttrs NewAttrs) {
assert(has(Main));
auto *Info = *get(Main);
auto &Link = linksAt(Info->Index);
Link.setAttrs(NewAttrs);
}
private:
DenseMap<T, StratifiedInfo> Values;
std::vector<BuilderLink> Links;
/// Adds the given element at the given index, merging sets if necessary.
bool addAtMerging(const T &ToAdd, StratifiedIndex Index) {
StratifiedInfo Info = {Index};
auto Pair = Values.insert(std::make_pair(ToAdd, Info));
if (Pair.second)
return true;
auto &Iter = Pair.first;
auto &IterSet = linksAt(Iter->second.Index);
auto &ReqSet = linksAt(Index);
// Failed to add where we wanted to. Merge the sets.
if (&IterSet != &ReqSet)
merge(IterSet.Number, ReqSet.Number);
return false;
}
/// Gets the BuilderLink at the given index, taking set remapping into
/// account.
BuilderLink &linksAt(StratifiedIndex Index) {
auto *Start = &Links[Index];
if (!Start->isRemapped())
return *Start;
auto *Current = Start;
while (Current->isRemapped())
Current = &Links[Current->getRemapIndex()];
auto NewRemap = Current->Number;
// Run through everything that has yet to be updated, and update them to
// remap to NewRemap
Current = Start;
while (Current->isRemapped()) {
auto *Next = &Links[Current->getRemapIndex()];
Current->updateRemap(NewRemap);
Current = Next;
}
return *Current;
}
/// Merges two sets into one another. Assumes that these sets are not
/// already one in the same.
void merge(StratifiedIndex Idx1, StratifiedIndex Idx2) {
assert(inbounds(Idx1) && inbounds(Idx2));
assert(&linksAt(Idx1) != &linksAt(Idx2) &&
"Merging a set into itself is not allowed");
// CASE 1: If the set at `Idx1` is above or below `Idx2`, we need to merge
// both the
// given sets, and all sets between them, into one.
if (tryMergeUpwards(Idx1, Idx2))
return;
if (tryMergeUpwards(Idx2, Idx1))
return;
// CASE 2: The set at `Idx1` is not in the same chain as the set at `Idx2`.
// We therefore need to merge the two chains together.
mergeDirect(Idx1, Idx2);
}
/// Merges two sets assuming that the set at `Idx1` is unreachable from
/// traversing above or below the set at `Idx2`.
void mergeDirect(StratifiedIndex Idx1, StratifiedIndex Idx2) {
assert(inbounds(Idx1) && inbounds(Idx2));
auto *LinksInto = &linksAt(Idx1);
auto *LinksFrom = &linksAt(Idx2);
// Merging everything above LinksInto then proceeding to merge everything
// below LinksInto becomes problematic, so we go as far "up" as possible!
while (LinksInto->hasAbove() && LinksFrom->hasAbove()) {
LinksInto = &linksAt(LinksInto->getAbove());
LinksFrom = &linksAt(LinksFrom->getAbove());
}
if (LinksFrom->hasAbove()) {
LinksInto->setAbove(LinksFrom->getAbove());
auto &NewAbove = linksAt(LinksInto->getAbove());
NewAbove.setBelow(LinksInto->Number);
}
// Merging strategy:
// > If neither has links below, stop.
// > If only `LinksInto` has links below, stop.
// > If only `LinksFrom` has links below, reset `LinksInto.Below` to
// match `LinksFrom.Below`
// > If both have links above, deal with those next.
while (LinksInto->hasBelow() && LinksFrom->hasBelow()) {
auto FromAttrs = LinksFrom->getAttrs();
LinksInto->setAttrs(FromAttrs);
// Remap needs to happen after getBelow(), but before
// assignment of LinksFrom
auto *NewLinksFrom = &linksAt(LinksFrom->getBelow());
LinksFrom->remapTo(LinksInto->Number);
LinksFrom = NewLinksFrom;
LinksInto = &linksAt(LinksInto->getBelow());
}
if (LinksFrom->hasBelow()) {
LinksInto->setBelow(LinksFrom->getBelow());
auto &NewBelow = linksAt(LinksInto->getBelow());
NewBelow.setAbove(LinksInto->Number);
}
LinksInto->setAttrs(LinksFrom->getAttrs());
LinksFrom->remapTo(LinksInto->Number);
}
/// 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.
bool tryMergeUpwards(StratifiedIndex LowerIndex, StratifiedIndex UpperIndex) {
assert(inbounds(LowerIndex) && inbounds(UpperIndex));
auto *Lower = &linksAt(LowerIndex);
auto *Upper = &linksAt(UpperIndex);
if (Lower == Upper)
return true;
SmallVector<BuilderLink *, 8> Found;
auto *Current = Lower;
auto Attrs = Current->getAttrs();
while (Current->hasAbove() && Current != Upper) {
Found.push_back(Current);
Attrs |= Current->getAttrs();
Current = &linksAt(Current->getAbove());
}
if (Current != Upper)
return false;
Upper->setAttrs(Attrs);
if (Lower->hasBelow()) {
auto NewBelowIndex = Lower->getBelow();
Upper->setBelow(NewBelowIndex);
auto &NewBelow = linksAt(NewBelowIndex);
NewBelow.setAbove(UpperIndex);
} else {
Upper->clearBelow();
}
for (const auto &Ptr : Found)
Ptr->remapTo(Upper->Number);
return true;
}
std::optional<const StratifiedInfo *> get(const T &Val) const {
auto Result = Values.find(Val);
if (Result == Values.end())
return std::nullopt;
return &Result->second;
}
std::optional<StratifiedInfo *> get(const T &Val) {
auto Result = Values.find(Val);
if (Result == Values.end())
return std::nullopt;
return &Result->second;
}
std::optional<StratifiedIndex> indexOf(const T &Val) {
auto MaybeVal = get(Val);
if (!MaybeVal)
return std::nullopt;
auto *Info = *MaybeVal;
auto &Link = linksAt(Info->Index);
return Link.Number;
}
StratifiedIndex addLinkBelow(StratifiedIndex Set) {
auto At = addLinks();
Links[Set].setBelow(At);
Links[At].setAbove(Set);
return At;
}
StratifiedIndex addLinkAbove(StratifiedIndex Set) {
auto At = addLinks();
Links[At].setBelow(Set);
Links[Set].setAbove(At);
return At;
}
StratifiedIndex getNewUnlinkedIndex() { return addLinks(); }
StratifiedIndex addLinks() {
auto Link = Links.size();
Links.push_back(BuilderLink(Link));
return Link;
}
bool inbounds(StratifiedIndex N) const { return N < Links.size(); }
};
}
}
#endif // LLVM_ADT_STRATIFIEDSETS_H
llvm/lib/Analysis/AliasAnalysisSummary.cpp