137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines//===- StratifiedSets.h - Abstract stratified sets implementation. --------===// 237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// 337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// The LLVM Compiler Infrastructure 437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// 537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// This file is distributed under the University of Illinois Open Source 637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// License. See LICENSE.TXT for details. 737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// 837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines//===----------------------------------------------------------------------===// 937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 1037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#ifndef LLVM_ADT_STRATIFIEDSETS_H 1137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#define LLVM_ADT_STRATIFIEDSETS_H 1237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 13de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "AliasAnalysisSummary.h" 1437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/ADT/DenseMap.h" 1537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/ADT/Optional.h" 1637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/ADT/SmallSet.h" 1737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/ADT/SmallVector.h" 1837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include <bitset> 1937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include <cassert> 2037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include <cmath> 2137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include <type_traits> 2237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include <utility> 2337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include <vector> 2437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 2537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesnamespace llvm { 26de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarnamespace cflaa { 27de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// An index into Stratified Sets. 2837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypedef unsigned StratifiedIndex; 29de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// NOTE: ^ This can't be a short -- bootstrapping clang has a case where 30de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// ~1M sets exist. 3137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 3237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// \brief Container of information related to a value in a StratifiedSet. 3337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesstruct StratifiedInfo { 3437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratifiedIndex Index; 35de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// For field sensitivity, etc. we can tack fields on here. 3637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines}; 3737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 38de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// A "link" between two StratifiedSets. 3937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesstruct StratifiedLink { 40de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \brief This is a value used to signify "does not exist" where the 41de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// StratifiedIndex type is used. 42de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// 43de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// This is used instead of Optional<StratifiedIndex> because 44de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Optional<StratifiedIndex> would eat up a considerable amount of extra 45de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// memory, after struct padding/alignment is taken into account. 4637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines static const StratifiedIndex SetSentinel; 4737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 48de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// The index for the set "above" current 4937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratifiedIndex Above; 5037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 51de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// The link for the set "below" current 5237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratifiedIndex Below; 5337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 54de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Attributes for these StratifiedSets. 55de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AliasAttrs Attrs; 5637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 5737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratifiedLink() : Above(SetSentinel), Below(SetSentinel) {} 5837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 5937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool hasBelow() const { return Below != SetSentinel; } 6037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool hasAbove() const { return Above != SetSentinel; } 6137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 6237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void clearBelow() { Below = SetSentinel; } 6337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void clearAbove() { Above = SetSentinel; } 6437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines}; 6537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 66de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// \brief These are stratified sets, as described in "Fast algorithms for 67de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// Dyck-CFL-reachability with applications to Alias Analysis" by Zhang Q, Lyu M 68de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// R, Yuan H, and Su Z. -- in short, this is meant to represent different sets 69de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// of Value*s. If two Value*s are in the same set, or if both sets have 70de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// overlapping attributes, then the Value*s are said to alias. 71de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// 72de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// Sets may be related by position, meaning that one set may be considered as 73de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// above or below another. In CFL Alias Analysis, this gives us an indication 74de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// of how two variables are related; if the set of variable A is below a set 75de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// containing variable B, then at some point, a variable that has interacted 76de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// with B (or B itself) was either used in order to extract the variable A, or 77de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// was used as storage of variable A. 78de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// 79de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// Sets may also have attributes (as noted above). These attributes are 80de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// generally used for noting whether a variable in the set has interacted with 81de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// a variable whose origins we don't quite know (i.e. globals/arguments), or if 82de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// the variable may have had operations performed on it (modified in a function 83de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// call). All attributes that exist in a set A must exist in all sets marked as 84de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// below set A. 8537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <typename T> class StratifiedSets { 8637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinespublic: 87de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar StratifiedSets() = default; 8837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 89de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // TODO: Figure out how to make MSVC not call the copy ctor here, and delete 90de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // it. 9137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 92de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Can't default these due to compile errors in MSVC2013 93de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar StratifiedSets(StratifiedSets &&Other) { *this = std::move(Other); } 94de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar StratifiedSets &operator=(StratifiedSets &&Other) { 9537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Values = std::move(Other.Values); 9637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Links = std::move(Other.Links); 9737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return *this; 9837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 9937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 100de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar StratifiedSets(DenseMap<T, StratifiedInfo> Map, 101de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::vector<StratifiedLink> Links) 102de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : Values(std::move(Map)), Links(std::move(Links)) {} 103de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 10437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Optional<StratifiedInfo> find(const T &Elem) const { 10537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto Iter = Values.find(Elem); 106de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Iter == Values.end()) 107de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return None; 10837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Iter->second; 10937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 11037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 11137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const StratifiedLink &getLink(StratifiedIndex Index) const { 11237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(inbounds(Index)); 11337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Links[Index]; 11437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 11537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 11637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesprivate: 11737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines DenseMap<T, StratifiedInfo> Values; 11837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines std::vector<StratifiedLink> Links; 11937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 12037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool inbounds(StratifiedIndex Idx) const { return Idx < Links.size(); } 12137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines}; 12237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 123de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// Generic Builder class that produces StratifiedSets instances. 124de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// 125de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// The goal of this builder is to efficiently produce correct StratifiedSets 126de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// instances. To this end, we use a few tricks: 127de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// > Set chains (A method for linking sets together) 128de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// > Set remaps (A method for marking a set as an alias [irony?] of another) 129de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// 130de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// ==== Set chains ==== 131de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// This builder has a notion of some value A being above, below, or with some 132de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// other value B: 133de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// > The `A above B` relationship implies that there is a reference edge 134de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// going from A to B. Namely, it notes that A can store anything in B's set. 135de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// > The `A below B` relationship is the opposite of `A above B`. It implies 136de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// that there's a dereference edge going from A to B. 137de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// > The `A with B` relationship states that there's an assignment edge going 138de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// from A to B, and that A and B should be treated as equals. 139de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// 140de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// As an example, take the following code snippet: 141de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// 142de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// %a = alloca i32, align 4 143de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// %ap = alloca i32*, align 8 144de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// %app = alloca i32**, align 8 145de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// store %a, %ap 146de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// store %ap, %app 147de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// %aw = getelementptr %ap, i32 0 148de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// 149de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// Given this, the following relations exist: 150de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// - %a below %ap & %ap above %a 151de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// - %ap below %app & %app above %ap 152de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// - %aw with %ap & %ap with %aw 153de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// 154de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// These relations produce the following sets: 155de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// [{%a}, {%ap, %aw}, {%app}] 156de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// 157de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// ...Which state that the only MayAlias relationship in the above program is 158de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// between %ap and %aw. 159de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// 160de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// Because LLVM allows arbitrary casts, code like the following needs to be 161de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// supported: 162de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// %ip = alloca i64, align 8 163de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// %ipp = alloca i64*, align 8 164de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// %i = bitcast i64** ipp to i64 165de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// store i64* %ip, i64** %ipp 166de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// store i64 %i, i64* %ip 167de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// 168de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// Which, because %ipp ends up *both* above and below %ip, is fun. 169de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// 170de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// This is solved by merging %i and %ipp into a single set (...which is the 171de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// only way to solve this, since their bit patterns are equivalent). Any sets 172de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// that ended up in between %i and %ipp at the time of merging (in this case, 173de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// the set containing %ip) also get conservatively merged into the set of %i 174de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// and %ipp. In short, the resulting StratifiedSet from the above code would be 175de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// {%ip, %ipp, %i}. 176de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// 177de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// ==== Set remaps ==== 178de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// More of an implementation detail than anything -- when merging sets, we need 179de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// to update the numbers of all of the elements mapped to those sets. Rather 180de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// than doing this at each merge, we note in the BuilderLink structure that a 181de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// remap has occurred, and use this information so we can defer renumbering set 182de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// elements until build time. 18337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <typename T> class StratifiedSetsBuilder { 184de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \brief Represents a Stratified Set, with information about the Stratified 185de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Set above it, the set below it, and whether the current set has been 186de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// remapped to another. 18737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines struct BuilderLink { 18837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const StratifiedIndex Number; 18937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 19037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BuilderLink(StratifiedIndex N) : Number(N) { 19137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Remap = StratifiedLink::SetSentinel; 19237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 19337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 19437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool hasAbove() const { 19537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(!isRemapped()); 19637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Link.hasAbove(); 19737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 19837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 19937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool hasBelow() const { 20037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(!isRemapped()); 20137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Link.hasBelow(); 20237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 20337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 20437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void setBelow(StratifiedIndex I) { 20537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(!isRemapped()); 20637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Link.Below = I; 20737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 20837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 20937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void setAbove(StratifiedIndex I) { 21037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(!isRemapped()); 21137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Link.Above = I; 21237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 21337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 21437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void clearBelow() { 21537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(!isRemapped()); 21637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Link.clearBelow(); 21737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 21837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 21937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void clearAbove() { 22037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(!isRemapped()); 22137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Link.clearAbove(); 22237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 22337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 22437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratifiedIndex getBelow() const { 22537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(!isRemapped()); 22637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(hasBelow()); 22737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Link.Below; 22837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 22937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 23037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratifiedIndex getAbove() const { 23137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(!isRemapped()); 23237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(hasAbove()); 23337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Link.Above; 23437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 23537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 236de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AliasAttrs getAttrs() { 23737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(!isRemapped()); 23837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Link.Attrs; 23937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 24037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 241de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void setAttrs(AliasAttrs Other) { 24237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(!isRemapped()); 243de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Link.Attrs |= Other; 24437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 24537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 24637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool isRemapped() const { return Remap != StratifiedLink::SetSentinel; } 24737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 248de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// For initial remapping to another set 24937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void remapTo(StratifiedIndex Other) { 25037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(!isRemapped()); 25137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Remap = Other; 25237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 25337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 25437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratifiedIndex getRemapIndex() const { 25537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(isRemapped()); 25637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Remap; 25737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 25837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 259de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Should only be called when we're already remapped. 26037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void updateRemap(StratifiedIndex Other) { 26137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(isRemapped()); 26237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Remap = Other; 26337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 26437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 265de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Prefer the above functions to calling things directly on what's returned 266de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// from this -- they guard against unexpected calls when the current 267de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// BuilderLink is remapped. 26837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const StratifiedLink &getLink() const { return Link; } 26937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 27037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines private: 27137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratifiedLink Link; 27237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratifiedIndex Remap; 27337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines }; 27437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 275de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \brief This function performs all of the set unioning/value renumbering 276de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// that we've been putting off, and generates a vector<StratifiedLink> that 277de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// may be placed in a StratifiedSets instance. 27837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void finalizeSets(std::vector<StratifiedLink> &StratLinks) { 27937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines DenseMap<StratifiedIndex, StratifiedIndex> Remaps; 28037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (auto &Link : Links) { 281de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Link.isRemapped()) 28237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines continue; 28337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 28437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratifiedIndex Number = StratLinks.size(); 28537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Remaps.insert(std::make_pair(Link.Number, Number)); 28637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratLinks.push_back(Link.getLink()); 28737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 28837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 28937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (auto &Link : StratLinks) { 29037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Link.hasAbove()) { 29137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto &Above = linksAt(Link.Above); 29237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto Iter = Remaps.find(Above.Number); 29337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(Iter != Remaps.end()); 29437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Link.Above = Iter->second; 29537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 29637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 29737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Link.hasBelow()) { 29837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto &Below = linksAt(Link.Below); 29937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto Iter = Remaps.find(Below.Number); 30037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(Iter != Remaps.end()); 30137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Link.Below = Iter->second; 30237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 30337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 30437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 30537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (auto &Pair : Values) { 30637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto &Info = Pair.second; 30737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto &Link = linksAt(Info.Index); 30837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto Iter = Remaps.find(Link.Number); 30937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(Iter != Remaps.end()); 31037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Info.Index = Iter->second; 31137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 31237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 31337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 314de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \brief There's a guarantee in StratifiedLink where all bits set in a 315de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Link.externals will be set in all Link.externals "below" it. 31637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines static void propagateAttrs(std::vector<StratifiedLink> &Links) { 31737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const auto getHighestParentAbove = [&Links](StratifiedIndex Idx) { 31837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const auto *Link = &Links[Idx]; 31937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (Link->hasAbove()) { 32037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Idx = Link->Above; 32137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Link = &Links[Idx]; 32237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 32337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Idx; 32437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines }; 32537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 32637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SmallSet<StratifiedIndex, 16> Visited; 32737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (unsigned I = 0, E = Links.size(); I < E; ++I) { 32837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto CurrentIndex = getHighestParentAbove(I); 329de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Visited.insert(CurrentIndex).second) 33037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines continue; 33137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 33237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (Links[CurrentIndex].hasBelow()) { 33337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto &CurrentBits = Links[CurrentIndex].Attrs; 33437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto NextIndex = Links[CurrentIndex].Below; 33537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto &NextBits = Links[NextIndex].Attrs; 33637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines NextBits |= CurrentBits; 33737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines CurrentIndex = NextIndex; 33837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 33937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 34037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 34137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 34237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinespublic: 343de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Builds a StratifiedSet from the information we've been given since either 344de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// construction or the prior build() call. 34537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratifiedSets<T> build() { 34637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines std::vector<StratifiedLink> StratLinks; 34737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines finalizeSets(StratLinks); 34837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines propagateAttrs(StratLinks); 34937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Links.clear(); 35037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return StratifiedSets<T>(std::move(Values), std::move(StratLinks)); 35137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 35237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 35337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool has(const T &Elem) const { return get(Elem).hasValue(); } 35437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 35537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool add(const T &Main) { 35637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (get(Main).hasValue()) 35737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return false; 35837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 35937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto NewIndex = getNewUnlinkedIndex(); 36037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return addAtMerging(Main, NewIndex); 36137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 36237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 363de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \brief Restructures the stratified sets as necessary to make "ToAdd" in a 364de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// set above "Main". There are some cases where this is not possible (see 365de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// above), so we merge them such that ToAdd and Main are in the same set. 36637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool addAbove(const T &Main, const T &ToAdd) { 36737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(has(Main)); 36837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto Index = *indexOf(Main); 36937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!linksAt(Index).hasAbove()) 37037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines addLinkAbove(Index); 37137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 37237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto Above = linksAt(Index).getAbove(); 37337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return addAtMerging(ToAdd, Above); 37437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 37537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 376de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \brief Restructures the stratified sets as necessary to make "ToAdd" in a 377de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// set below "Main". There are some cases where this is not possible (see 378de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// above), so we merge them such that ToAdd and Main are in the same set. 37937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool addBelow(const T &Main, const T &ToAdd) { 38037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(has(Main)); 38137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto Index = *indexOf(Main); 38237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!linksAt(Index).hasBelow()) 38337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines addLinkBelow(Index); 38437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 38537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto Below = linksAt(Index).getBelow(); 38637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return addAtMerging(ToAdd, Below); 38737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 38837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 38937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool addWith(const T &Main, const T &ToAdd) { 39037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(has(Main)); 39137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto MainIndex = *indexOf(Main); 39237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return addAtMerging(ToAdd, MainIndex); 39337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 39437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 395de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void noteAttributes(const T &Main, AliasAttrs NewAttrs) { 39637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(has(Main)); 39737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto *Info = *get(Main); 39837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto &Link = linksAt(Info->Index); 39937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Link.setAttrs(NewAttrs); 40037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 40137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 40237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesprivate: 40337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines DenseMap<T, StratifiedInfo> Values; 40437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines std::vector<BuilderLink> Links; 40537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 406de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Adds the given element at the given index, merging sets if necessary. 40737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool addAtMerging(const T &ToAdd, StratifiedIndex Index) { 40837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratifiedInfo Info = {Index}; 40937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto Pair = Values.insert(std::make_pair(ToAdd, Info)); 41037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Pair.second) 41137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return true; 41237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 41337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto &Iter = Pair.first; 41437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto &IterSet = linksAt(Iter->second.Index); 41537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto &ReqSet = linksAt(Index); 41637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 41737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Failed to add where we wanted to. Merge the sets. 41837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (&IterSet != &ReqSet) 41937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines merge(IterSet.Number, ReqSet.Number); 42037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 42137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return false; 42237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 42337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 424de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Gets the BuilderLink at the given index, taking set remapping into 425de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// account. 42637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BuilderLink &linksAt(StratifiedIndex Index) { 42737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto *Start = &Links[Index]; 42837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!Start->isRemapped()) 42937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return *Start; 43037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 43137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto *Current = Start; 43237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (Current->isRemapped()) 43337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Current = &Links[Current->getRemapIndex()]; 43437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 43537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto NewRemap = Current->Number; 43637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 43737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Run through everything that has yet to be updated, and update them to 43837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // remap to NewRemap 43937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Current = Start; 44037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (Current->isRemapped()) { 44137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto *Next = &Links[Current->getRemapIndex()]; 44237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Current->updateRemap(NewRemap); 44337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Current = Next; 44437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 44537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 44637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return *Current; 44737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 44837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 449de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \brief Merges two sets into one another. Assumes that these sets are not 450de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// already one in the same. 45137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void merge(StratifiedIndex Idx1, StratifiedIndex Idx2) { 45237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(inbounds(Idx1) && inbounds(Idx2)); 45337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(&linksAt(Idx1) != &linksAt(Idx2) && 45437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines "Merging a set into itself is not allowed"); 45537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 45637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // CASE 1: If the set at `Idx1` is above or below `Idx2`, we need to merge 45737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // both the 45837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // given sets, and all sets between them, into one. 45937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (tryMergeUpwards(Idx1, Idx2)) 46037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return; 46137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 46237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (tryMergeUpwards(Idx2, Idx1)) 46337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return; 46437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 46537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // CASE 2: The set at `Idx1` is not in the same chain as the set at `Idx2`. 46637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // We therefore need to merge the two chains together. 46737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines mergeDirect(Idx1, Idx2); 46837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 46937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 470de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \brief Merges two sets assuming that the set at `Idx1` is unreachable from 471de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// traversing above or below the set at `Idx2`. 47237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void mergeDirect(StratifiedIndex Idx1, StratifiedIndex Idx2) { 47337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(inbounds(Idx1) && inbounds(Idx2)); 47437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 47537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto *LinksInto = &linksAt(Idx1); 47637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto *LinksFrom = &linksAt(Idx2); 47737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Merging everything above LinksInto then proceeding to merge everything 47837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // below LinksInto becomes problematic, so we go as far "up" as possible! 47937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (LinksInto->hasAbove() && LinksFrom->hasAbove()) { 48037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LinksInto = &linksAt(LinksInto->getAbove()); 48137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LinksFrom = &linksAt(LinksFrom->getAbove()); 48237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 48337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 48437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (LinksFrom->hasAbove()) { 48537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LinksInto->setAbove(LinksFrom->getAbove()); 48637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto &NewAbove = linksAt(LinksInto->getAbove()); 48737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines NewAbove.setBelow(LinksInto->Number); 48837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 48937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 49037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Merging strategy: 49137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // > If neither has links below, stop. 49237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // > If only `LinksInto` has links below, stop. 49337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // > If only `LinksFrom` has links below, reset `LinksInto.Below` to 49437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // match `LinksFrom.Below` 49537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // > If both have links above, deal with those next. 49637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (LinksInto->hasBelow() && LinksFrom->hasBelow()) { 497de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto FromAttrs = LinksFrom->getAttrs(); 49837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LinksInto->setAttrs(FromAttrs); 49937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 50037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Remap needs to happen after getBelow(), but before 50137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // assignment of LinksFrom 50237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto *NewLinksFrom = &linksAt(LinksFrom->getBelow()); 50337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LinksFrom->remapTo(LinksInto->Number); 50437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LinksFrom = NewLinksFrom; 50537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LinksInto = &linksAt(LinksInto->getBelow()); 50637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 50737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 50837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (LinksFrom->hasBelow()) { 50937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LinksInto->setBelow(LinksFrom->getBelow()); 51037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto &NewBelow = linksAt(LinksInto->getBelow()); 51137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines NewBelow.setAbove(LinksInto->Number); 51237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 51337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 514de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LinksInto->setAttrs(LinksFrom->getAttrs()); 51537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LinksFrom->remapTo(LinksInto->Number); 51637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 51737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 518de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Checks to see if lowerIndex is at a level lower than upperIndex. If so, it 519de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// will merge lowerIndex with upperIndex (and all of the sets between) and 520de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// return true. Otherwise, it will return false. 52137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool tryMergeUpwards(StratifiedIndex LowerIndex, StratifiedIndex UpperIndex) { 52237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(inbounds(LowerIndex) && inbounds(UpperIndex)); 52337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto *Lower = &linksAt(LowerIndex); 52437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto *Upper = &linksAt(UpperIndex); 52537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Lower == Upper) 52637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return true; 52737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 52837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SmallVector<BuilderLink *, 8> Found; 52937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto *Current = Lower; 53037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto Attrs = Current->getAttrs(); 53137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (Current->hasAbove() && Current != Upper) { 53237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Found.push_back(Current); 53337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Attrs |= Current->getAttrs(); 53437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Current = &linksAt(Current->getAbove()); 53537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 53637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 53737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Current != Upper) 53837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return false; 53937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 54037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Upper->setAttrs(Attrs); 54137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 54237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Lower->hasBelow()) { 54337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto NewBelowIndex = Lower->getBelow(); 54437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Upper->setBelow(NewBelowIndex); 54537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto &NewBelow = linksAt(NewBelowIndex); 54637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines NewBelow.setAbove(UpperIndex); 54737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } else { 54837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Upper->clearBelow(); 54937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 55037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 55137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (const auto &Ptr : Found) 55237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Ptr->remapTo(Upper->Number); 55337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 55437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return true; 55537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 55637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 55737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Optional<const StratifiedInfo *> get(const T &Val) const { 55837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto Result = Values.find(Val); 55937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Result == Values.end()) 560de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return None; 56137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return &Result->second; 56237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 56337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 56437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Optional<StratifiedInfo *> get(const T &Val) { 56537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto Result = Values.find(Val); 56637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Result == Values.end()) 567de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return None; 56837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return &Result->second; 56937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 57037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 57137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Optional<StratifiedIndex> indexOf(const T &Val) { 57237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto MaybeVal = get(Val); 57337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!MaybeVal.hasValue()) 574de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return None; 57537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto *Info = *MaybeVal; 57637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto &Link = linksAt(Info->Index); 57737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Link.Number; 57837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 57937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 58037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratifiedIndex addLinkBelow(StratifiedIndex Set) { 58137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto At = addLinks(); 58237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Links[Set].setBelow(At); 58337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Links[At].setAbove(Set); 58437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return At; 58537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 58637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 58737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratifiedIndex addLinkAbove(StratifiedIndex Set) { 58837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto At = addLinks(); 58937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Links[At].setBelow(Set); 59037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Links[Set].setAbove(At); 59137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return At; 59237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 59337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 59437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratifiedIndex getNewUnlinkedIndex() { return addLinks(); } 59537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 59637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StratifiedIndex addLinks() { 59737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto Link = Links.size(); 59837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Links.push_back(BuilderLink(Link)); 59937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Link; 60037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 60137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 60237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool inbounds(StratifiedIndex N) const { return N < Links.size(); } 60337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines}; 60437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 605de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 60637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#endif // LLVM_ADT_STRATIFIEDSETS_H 607