From 7f3047219cf557fd161c3cd0dd32e7713438dc38 Mon Sep 17 00:00:00 2001 From: Kazu Hirata Date: Wed, 17 May 2023 08:39:48 -0700 Subject: [PATCH] [Analysis] Remove AliasAnalysisSummary.cpp The last use was removed by: commit 8005332835246c54a4a6b026eede930ed559deb4 Author: Nikita Popov Date: Fri Dec 9 11:57:50 2022 +0100 Differential Revision: https://reviews.llvm.org/D150748 --- llvm/lib/Analysis/AliasAnalysisSummary.cpp | 104 ----- llvm/lib/Analysis/AliasAnalysisSummary.h | 268 ------------- llvm/lib/Analysis/CMakeLists.txt | 1 - llvm/lib/Analysis/StratifiedSets.h | 595 ----------------------------- 4 files changed, 968 deletions(-) delete mode 100644 llvm/lib/Analysis/AliasAnalysisSummary.cpp delete mode 100644 llvm/lib/Analysis/AliasAnalysisSummary.h delete mode 100644 llvm/lib/Analysis/StratifiedSets.h diff --git a/llvm/lib/Analysis/AliasAnalysisSummary.cpp b/llvm/lib/Analysis/AliasAnalysisSummary.cpp deleted file mode 100644 index a91791c..0000000 --- a/llvm/lib/Analysis/AliasAnalysisSummary.cpp +++ /dev/null @@ -1,104 +0,0 @@ -#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(Val)) - return AttrGlobal; - - if (auto *Arg = dyn_cast(&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 -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 -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 -instantiateExternalAttribute(ExternalAttribute EAttr, CallBase &Call) { - auto Value = instantiateInterfaceValue(EAttr.IValue, Call); - if (!Value) - return std::nullopt; - return InstantiatedAttr{*Value, EAttr.Attr}; -} -} -} diff --git a/llvm/lib/Analysis/AliasAnalysisSummary.h b/llvm/lib/Analysis/AliasAnalysisSummary.h deleted file mode 100644 index ab337ba..0000000 --- a/llvm/lib/Analysis/AliasAnalysisSummary.h +++ /dev/null @@ -1,268 +0,0 @@ -//=====- 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 -#include - -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 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 RetParamRelations; - - // RetParamAttributes is a collection of ExternalAttributes. - SmallVector RetParamAttributes; -}; - -/// This is the result of instantiating InterfaceValue at a particular call -struct InstantiatedValue { - Value *Val; - unsigned DerefLevel; -}; -std::optional -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()(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 -instantiateExternalRelation(ExternalRelation ERelation, CallBase &Call); - -/// This is the result of instantiating ExternalAttribute at a particular -/// callsite -struct InstantiatedAttr { - InstantiatedValue IValue; - AliasAttrs Attr; -}; -std::optional -instantiateExternalAttribute(ExternalAttribute EAttr, CallBase &Call); -} - -template <> struct DenseMapInfo { - static inline cflaa::InstantiatedValue getEmptyKey() { - return cflaa::InstantiatedValue{DenseMapInfo::getEmptyKey(), - DenseMapInfo::getEmptyKey()}; - } - static inline cflaa::InstantiatedValue getTombstoneKey() { - return cflaa::InstantiatedValue{DenseMapInfo::getTombstoneKey(), - DenseMapInfo::getTombstoneKey()}; - } - static unsigned getHashValue(const cflaa::InstantiatedValue &IV) { - return DenseMapInfo>::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 diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt index 2f684e6..166a83e 100644 --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -26,7 +26,6 @@ endif() add_llvm_component_library(LLVMAnalysis AliasAnalysis.cpp AliasAnalysisEvaluator.cpp - AliasAnalysisSummary.cpp AliasSetTracker.cpp Analysis.cpp AssumeBundleQueries.cpp diff --git a/llvm/lib/Analysis/StratifiedSets.h b/llvm/lib/Analysis/StratifiedSets.h deleted file mode 100644 index 193e4a4..0000000 --- a/llvm/lib/Analysis/StratifiedSets.h +++ /dev/null @@ -1,595 +0,0 @@ -//===- 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 -#include -#include -#include -#include -#include - -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 because - /// std::optional 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 class StratifiedSets { -public: - StratifiedSets() = default; - StratifiedSets(StratifiedSets &&) = default; - StratifiedSets &operator=(StratifiedSets &&) = default; - - StratifiedSets(DenseMap Map, - std::vector Links) - : Values(std::move(Map)), Links(std::move(Links)) {} - - std::optional 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 Values; - std::vector 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 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 that - /// may be placed in a StratifiedSets instance. - void finalizeSets(std::vector &StratLinks) { - DenseMap 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 &Links) { - const auto getHighestParentAbove = [&Links](StratifiedIndex Idx) { - const auto *Link = &Links[Idx]; - while (Link->hasAbove()) { - Idx = Link->Above; - Link = &Links[Idx]; - } - return Idx; - }; - - SmallSet 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 build() { - std::vector StratLinks; - finalizeSets(StratLinks); - propagateAttrs(StratLinks); - Links.clear(); - return StratifiedSets(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 Values; - std::vector 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 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 get(const T &Val) const { - auto Result = Values.find(Val); - if (Result == Values.end()) - return std::nullopt; - return &Result->second; - } - - std::optional get(const T &Val) { - auto Result = Values.find(Val); - if (Result == Values.end()) - return std::nullopt; - return &Result->second; - } - - std::optional 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 -- 2.7.4