/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/StratifiedSets.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- StratifiedSets.h - Abstract stratified sets implementation. --------===// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | |
9 | | #ifndef LLVM_ADT_STRATIFIEDSETS_H |
10 | | #define LLVM_ADT_STRATIFIEDSETS_H |
11 | | |
12 | | #include "AliasAnalysisSummary.h" |
13 | | #include "llvm/ADT/DenseMap.h" |
14 | | #include "llvm/ADT/Optional.h" |
15 | | #include "llvm/ADT/SmallSet.h" |
16 | | #include "llvm/ADT/SmallVector.h" |
17 | | #include <bitset> |
18 | | #include <cassert> |
19 | | #include <cmath> |
20 | | #include <type_traits> |
21 | | #include <utility> |
22 | | #include <vector> |
23 | | |
24 | | namespace llvm { |
25 | | namespace cflaa { |
26 | | /// An index into Stratified Sets. |
27 | | typedef unsigned StratifiedIndex; |
28 | | /// NOTE: ^ This can't be a short -- bootstrapping clang has a case where |
29 | | /// ~1M sets exist. |
30 | | |
31 | | // Container of information related to a value in a StratifiedSet. |
32 | | struct StratifiedInfo { |
33 | | StratifiedIndex Index; |
34 | | /// For field sensitivity, etc. we can tack fields on here. |
35 | | }; |
36 | | |
37 | | /// A "link" between two StratifiedSets. |
38 | | struct StratifiedLink { |
39 | | /// This is a value used to signify "does not exist" where the |
40 | | /// StratifiedIndex type is used. |
41 | | /// |
42 | | /// This is used instead of Optional<StratifiedIndex> because |
43 | | /// Optional<StratifiedIndex> would eat up a considerable amount of extra |
44 | | /// memory, after struct padding/alignment is taken into account. |
45 | | static const StratifiedIndex SetSentinel; |
46 | | |
47 | | /// The index for the set "above" current |
48 | | StratifiedIndex Above; |
49 | | |
50 | | /// The link for the set "below" current |
51 | | StratifiedIndex Below; |
52 | | |
53 | | /// Attributes for these StratifiedSets. |
54 | | AliasAttrs Attrs; |
55 | | |
56 | 982 | StratifiedLink() : Above(SetSentinel), Below(SetSentinel) {} |
57 | | |
58 | 2.54k | bool hasBelow() const { return Below != SetSentinel; } |
59 | 3.63k | bool hasAbove() const { return Above != SetSentinel; } |
60 | | |
61 | 0 | void clearBelow() { Below = SetSentinel; } |
62 | 0 | void clearAbove() { Above = SetSentinel; } |
63 | | }; |
64 | | |
65 | | /// These are stratified sets, as described in "Fast algorithms for |
66 | | /// Dyck-CFL-reachability with applications to Alias Analysis" by Zhang Q, Lyu M |
67 | | /// R, Yuan H, and Su Z. -- in short, this is meant to represent different sets |
68 | | /// of Value*s. If two Value*s are in the same set, or if both sets have |
69 | | /// overlapping attributes, then the Value*s are said to alias. |
70 | | /// |
71 | | /// Sets may be related by position, meaning that one set may be considered as |
72 | | /// above or below another. In CFL Alias Analysis, this gives us an indication |
73 | | /// of how two variables are related; if the set of variable A is below a set |
74 | | /// containing variable B, then at some point, a variable that has interacted |
75 | | /// with B (or B itself) was either used in order to extract the variable A, or |
76 | | /// was used as storage of variable A. |
77 | | /// |
78 | | /// Sets may also have attributes (as noted above). These attributes are |
79 | | /// generally used for noting whether a variable in the set has interacted with |
80 | | /// a variable whose origins we don't quite know (i.e. globals/arguments), or if |
81 | | /// the variable may have had operations performed on it (modified in a function |
82 | | /// call). All attributes that exist in a set A must exist in all sets marked as |
83 | | /// below set A. |
84 | | template <typename T> class StratifiedSets { |
85 | | public: |
86 | | StratifiedSets() = default; |
87 | 232 | StratifiedSets(StratifiedSets &&) = default; |
88 | 0 | StratifiedSets &operator=(StratifiedSets &&) = default; |
89 | | |
90 | | StratifiedSets(DenseMap<T, StratifiedInfo> Map, |
91 | | std::vector<StratifiedLink> Links) |
92 | 116 | : Values(std::move(Map)), Links(std::move(Links)) {} |
93 | | |
94 | 5.74k | Optional<StratifiedInfo> find(const T &Elem) const { |
95 | 5.74k | auto Iter = Values.find(Elem); |
96 | 5.74k | if (Iter == Values.end()) |
97 | 6 | return None; |
98 | 5.74k | return Iter->second; |
99 | 5.74k | } |
100 | | |
101 | 5.86k | const StratifiedLink &getLink(StratifiedIndex Index) const { |
102 | 5.86k | assert(inbounds(Index)); |
103 | 5.86k | return Links[Index]; |
104 | 5.86k | } |
105 | | |
106 | | private: |
107 | | DenseMap<T, StratifiedInfo> Values; |
108 | | std::vector<StratifiedLink> Links; |
109 | | |
110 | | bool inbounds(StratifiedIndex Idx) const { return Idx < Links.size(); } |
111 | | }; |
112 | | |
113 | | /// Generic Builder class that produces StratifiedSets instances. |
114 | | /// |
115 | | /// The goal of this builder is to efficiently produce correct StratifiedSets |
116 | | /// instances. To this end, we use a few tricks: |
117 | | /// > Set chains (A method for linking sets together) |
118 | | /// > Set remaps (A method for marking a set as an alias [irony?] of another) |
119 | | /// |
120 | | /// ==== Set chains ==== |
121 | | /// This builder has a notion of some value A being above, below, or with some |
122 | | /// other value B: |
123 | | /// > The `A above B` relationship implies that there is a reference edge |
124 | | /// going from A to B. Namely, it notes that A can store anything in B's set. |
125 | | /// > The `A below B` relationship is the opposite of `A above B`. It implies |
126 | | /// that there's a dereference edge going from A to B. |
127 | | /// > The `A with B` relationship states that there's an assignment edge going |
128 | | /// from A to B, and that A and B should be treated as equals. |
129 | | /// |
130 | | /// As an example, take the following code snippet: |
131 | | /// |
132 | | /// %a = alloca i32, align 4 |
133 | | /// %ap = alloca i32*, align 8 |
134 | | /// %app = alloca i32**, align 8 |
135 | | /// store %a, %ap |
136 | | /// store %ap, %app |
137 | | /// %aw = getelementptr %ap, i32 0 |
138 | | /// |
139 | | /// Given this, the following relations exist: |
140 | | /// - %a below %ap & %ap above %a |
141 | | /// - %ap below %app & %app above %ap |
142 | | /// - %aw with %ap & %ap with %aw |
143 | | /// |
144 | | /// These relations produce the following sets: |
145 | | /// [{%a}, {%ap, %aw}, {%app}] |
146 | | /// |
147 | | /// ...Which state that the only MayAlias relationship in the above program is |
148 | | /// between %ap and %aw. |
149 | | /// |
150 | | /// Because LLVM allows arbitrary casts, code like the following needs to be |
151 | | /// supported: |
152 | | /// %ip = alloca i64, align 8 |
153 | | /// %ipp = alloca i64*, align 8 |
154 | | /// %i = bitcast i64** ipp to i64 |
155 | | /// store i64* %ip, i64** %ipp |
156 | | /// store i64 %i, i64* %ip |
157 | | /// |
158 | | /// Which, because %ipp ends up *both* above and below %ip, is fun. |
159 | | /// |
160 | | /// This is solved by merging %i and %ipp into a single set (...which is the |
161 | | /// only way to solve this, since their bit patterns are equivalent). Any sets |
162 | | /// that ended up in between %i and %ipp at the time of merging (in this case, |
163 | | /// the set containing %ip) also get conservatively merged into the set of %i |
164 | | /// and %ipp. In short, the resulting StratifiedSet from the above code would be |
165 | | /// {%ip, %ipp, %i}. |
166 | | /// |
167 | | /// ==== Set remaps ==== |
168 | | /// More of an implementation detail than anything -- when merging sets, we need |
169 | | /// to update the numbers of all of the elements mapped to those sets. Rather |
170 | | /// than doing this at each merge, we note in the BuilderLink structure that a |
171 | | /// remap has occurred, and use this information so we can defer renumbering set |
172 | | /// elements until build time. |
173 | | template <typename T> class StratifiedSetsBuilder { |
174 | | /// Represents a Stratified Set, with information about the Stratified |
175 | | /// Set above it, the set below it, and whether the current set has been |
176 | | /// remapped to another. |
177 | | struct BuilderLink { |
178 | | const StratifiedIndex Number; |
179 | | |
180 | 982 | BuilderLink(StratifiedIndex N) : Number(N) { |
181 | 982 | Remap = StratifiedLink::SetSentinel; |
182 | 982 | } |
183 | | |
184 | 2.42k | bool hasAbove() const { |
185 | 2.42k | assert(!isRemapped()); |
186 | 2.42k | return Link.hasAbove(); |
187 | 2.42k | } |
188 | | |
189 | 1.30k | bool hasBelow() const { |
190 | 1.30k | assert(!isRemapped()); |
191 | 1.30k | return Link.hasBelow(); |
192 | 1.30k | } |
193 | | |
194 | 648 | void setBelow(StratifiedIndex I) { |
195 | 648 | assert(!isRemapped()); |
196 | 648 | Link.Below = I; |
197 | 648 | } |
198 | | |
199 | 648 | void setAbove(StratifiedIndex I) { |
200 | 648 | assert(!isRemapped()); |
201 | 648 | Link.Above = I; |
202 | 648 | } |
203 | | |
204 | 0 | void clearBelow() { |
205 | 0 | assert(!isRemapped()); |
206 | 0 | Link.clearBelow(); |
207 | 0 | } |
208 | | |
209 | | void clearAbove() { |
210 | | assert(!isRemapped()); |
211 | | Link.clearAbove(); |
212 | | } |
213 | | |
214 | 444 | StratifiedIndex getBelow() const { |
215 | 444 | assert(!isRemapped()); |
216 | 444 | assert(hasBelow()); |
217 | 444 | return Link.Below; |
218 | 444 | } |
219 | | |
220 | 1.12k | StratifiedIndex getAbove() const { |
221 | 1.12k | assert(!isRemapped()); |
222 | 1.12k | assert(hasAbove()); |
223 | 1.12k | return Link.Above; |
224 | 1.12k | } |
225 | | |
226 | 1.90k | AliasAttrs getAttrs() { |
227 | 1.90k | assert(!isRemapped()); |
228 | 1.90k | return Link.Attrs; |
229 | 1.90k | } |
230 | | |
231 | 1.23k | void setAttrs(AliasAttrs Other) { |
232 | 1.23k | assert(!isRemapped()); |
233 | 1.23k | Link.Attrs |= Other; |
234 | 1.23k | } |
235 | | |
236 | 10.0k | bool isRemapped() const { return Remap != StratifiedLink::SetSentinel; } |
237 | | |
238 | | /// For initial remapping to another set |
239 | 510 | void remapTo(StratifiedIndex Other) { |
240 | 510 | assert(!isRemapped()); |
241 | 510 | Remap = Other; |
242 | 510 | } |
243 | | |
244 | 852 | StratifiedIndex getRemapIndex() const { |
245 | 852 | assert(isRemapped()); |
246 | 852 | return Remap; |
247 | 852 | } |
248 | | |
249 | | /// Should only be called when we're already remapped. |
250 | 426 | void updateRemap(StratifiedIndex Other) { |
251 | 426 | assert(isRemapped()); |
252 | 426 | Remap = Other; |
253 | 426 | } |
254 | | |
255 | | /// Prefer the above functions to calling things directly on what's returned |
256 | | /// from this -- they guard against unexpected calls when the current |
257 | | /// BuilderLink is remapped. |
258 | 472 | const StratifiedLink &getLink() const { return Link; } |
259 | | |
260 | | private: |
261 | | StratifiedLink Link; |
262 | | StratifiedIndex Remap; |
263 | | }; |
264 | | |
265 | | /// This function performs all of the set unioning/value renumbering |
266 | | /// that we've been putting off, and generates a vector<StratifiedLink> that |
267 | | /// may be placed in a StratifiedSets instance. |
268 | 116 | void finalizeSets(std::vector<StratifiedLink> &StratLinks) { |
269 | 116 | DenseMap<StratifiedIndex, StratifiedIndex> Remaps; |
270 | 982 | for (auto &Link : Links) { |
271 | 982 | if (Link.isRemapped()) |
272 | 510 | continue; |
273 | 472 | |
274 | 472 | StratifiedIndex Number = StratLinks.size(); |
275 | 472 | Remaps.insert(std::make_pair(Link.Number, Number)); |
276 | 472 | StratLinks.push_back(Link.getLink()); |
277 | 472 | } |
278 | 116 | |
279 | 472 | for (auto &Link : StratLinks) { |
280 | 472 | if (Link.hasAbove()) { |
281 | 223 | auto &Above = linksAt(Link.Above); |
282 | 223 | auto Iter = Remaps.find(Above.Number); |
283 | 223 | assert(Iter != Remaps.end()); |
284 | 223 | Link.Above = Iter->second; |
285 | 223 | } |
286 | 472 | |
287 | 472 | if (Link.hasBelow()) { |
288 | 223 | auto &Below = linksAt(Link.Below); |
289 | 223 | auto Iter = Remaps.find(Below.Number); |
290 | 223 | assert(Iter != Remaps.end()); |
291 | 223 | Link.Below = Iter->second; |
292 | 223 | } |
293 | 472 | } |
294 | 116 | |
295 | 724 | for (auto &Pair : Values) { |
296 | 724 | auto &Info = Pair.second; |
297 | 724 | auto &Link = linksAt(Info.Index); |
298 | 724 | auto Iter = Remaps.find(Link.Number); |
299 | 724 | assert(Iter != Remaps.end()); |
300 | 724 | Info.Index = Iter->second; |
301 | 724 | } |
302 | 116 | } |
303 | | |
304 | | /// There's a guarantee in StratifiedLink where all bits set in a |
305 | | /// Link.externals will be set in all Link.externals "below" it. |
306 | 116 | static void propagateAttrs(std::vector<StratifiedLink> &Links) { |
307 | 472 | const auto getHighestParentAbove = [&Links](StratifiedIndex Idx) { |
308 | 472 | const auto *Link = &Links[Idx]; |
309 | 744 | while (Link->hasAbove()) { |
310 | 272 | Idx = Link->Above; |
311 | 272 | Link = &Links[Idx]; |
312 | 272 | } |
313 | 472 | return Idx; |
314 | 472 | }; |
315 | 116 | |
316 | 116 | SmallSet<StratifiedIndex, 16> Visited; |
317 | 588 | for (unsigned I = 0, E = Links.size(); I < E; ++I472 ) { |
318 | 472 | auto CurrentIndex = getHighestParentAbove(I); |
319 | 472 | if (!Visited.insert(CurrentIndex).second) |
320 | 223 | continue; |
321 | 249 | |
322 | 472 | while (249 Links[CurrentIndex].hasBelow()) { |
323 | 223 | auto &CurrentBits = Links[CurrentIndex].Attrs; |
324 | 223 | auto NextIndex = Links[CurrentIndex].Below; |
325 | 223 | auto &NextBits = Links[NextIndex].Attrs; |
326 | 223 | NextBits |= CurrentBits; |
327 | 223 | CurrentIndex = NextIndex; |
328 | 223 | } |
329 | 249 | } |
330 | 116 | } |
331 | | |
332 | | public: |
333 | | /// Builds a StratifiedSet from the information we've been given since either |
334 | | /// construction or the prior build() call. |
335 | 116 | StratifiedSets<T> build() { |
336 | 116 | std::vector<StratifiedLink> StratLinks; |
337 | 116 | finalizeSets(StratLinks); |
338 | 116 | propagateAttrs(StratLinks); |
339 | 116 | Links.clear(); |
340 | 116 | return StratifiedSets<T>(std::move(Values), std::move(StratLinks)); |
341 | 116 | } |
342 | | |
343 | | bool has(const T &Elem) const { return get(Elem).hasValue(); } |
344 | | |
345 | 724 | bool add(const T &Main) { |
346 | 724 | if (get(Main).hasValue()) |
347 | 0 | return false; |
348 | 724 | |
349 | 724 | auto NewIndex = getNewUnlinkedIndex(); |
350 | 724 | return addAtMerging(Main, NewIndex); |
351 | 724 | } |
352 | | |
353 | | /// Restructures the stratified sets as necessary to make "ToAdd" in a |
354 | | /// set above "Main". There are some cases where this is not possible (see |
355 | | /// above), so we merge them such that ToAdd and Main are in the same set. |
356 | | bool addAbove(const T &Main, const T &ToAdd) { |
357 | | assert(has(Main)); |
358 | | auto Index = *indexOf(Main); |
359 | | if (!linksAt(Index).hasAbove()) |
360 | | addLinkAbove(Index); |
361 | | |
362 | | auto Above = linksAt(Index).getAbove(); |
363 | | return addAtMerging(ToAdd, Above); |
364 | | } |
365 | | |
366 | | /// Restructures the stratified sets as necessary to make "ToAdd" in a |
367 | | /// set below "Main". There are some cases where this is not possible (see |
368 | | /// above), so we merge them such that ToAdd and Main are in the same set. |
369 | 258 | bool addBelow(const T &Main, const T &ToAdd) { |
370 | 258 | assert(has(Main)); |
371 | 258 | auto Index = *indexOf(Main); |
372 | 258 | if (!linksAt(Index).hasBelow()) |
373 | 258 | addLinkBelow(Index); |
374 | 258 | |
375 | 258 | auto Below = linksAt(Index).getBelow(); |
376 | 258 | return addAtMerging(ToAdd, Below); |
377 | 258 | } |
378 | | |
379 | 219 | bool addWith(const T &Main, const T &ToAdd) { |
380 | 219 | assert(has(Main)); |
381 | 219 | auto MainIndex = *indexOf(Main); |
382 | 219 | return addAtMerging(ToAdd, MainIndex); |
383 | 219 | } |
384 | | |
385 | 724 | void noteAttributes(const T &Main, AliasAttrs NewAttrs) { |
386 | 724 | assert(has(Main)); |
387 | 724 | auto *Info = *get(Main); |
388 | 724 | auto &Link = linksAt(Info->Index); |
389 | 724 | Link.setAttrs(NewAttrs); |
390 | 724 | } |
391 | | |
392 | | private: |
393 | | DenseMap<T, StratifiedInfo> Values; |
394 | | std::vector<BuilderLink> Links; |
395 | | |
396 | | /// Adds the given element at the given index, merging sets if necessary. |
397 | 1.20k | bool addAtMerging(const T &ToAdd, StratifiedIndex Index) { |
398 | 1.20k | StratifiedInfo Info = {Index}; |
399 | 1.20k | auto Pair = Values.insert(std::make_pair(ToAdd, Info)); |
400 | 1.20k | if (Pair.second) |
401 | 724 | return true; |
402 | 477 | |
403 | 477 | auto &Iter = Pair.first; |
404 | 477 | auto &IterSet = linksAt(Iter->second.Index); |
405 | 477 | auto &ReqSet = linksAt(Index); |
406 | 477 | |
407 | 477 | // Failed to add where we wanted to. Merge the sets. |
408 | 477 | if (&IterSet != &ReqSet) |
409 | 475 | merge(IterSet.Number, ReqSet.Number); |
410 | 477 | |
411 | 477 | return false; |
412 | 477 | } |
413 | | |
414 | | /// Gets the BuilderLink at the given index, taking set remapping into |
415 | | /// account. |
416 | 7.61k | BuilderLink &linksAt(StratifiedIndex Index) { |
417 | 7.61k | auto *Start = &Links[Index]; |
418 | 7.61k | if (!Start->isRemapped()) |
419 | 7.29k | return *Start; |
420 | 321 | |
421 | 321 | auto *Current = Start; |
422 | 747 | while (Current->isRemapped()) |
423 | 426 | Current = &Links[Current->getRemapIndex()]; |
424 | 321 | |
425 | 321 | auto NewRemap = Current->Number; |
426 | 321 | |
427 | 321 | // Run through everything that has yet to be updated, and update them to |
428 | 321 | // remap to NewRemap |
429 | 321 | Current = Start; |
430 | 747 | while (Current->isRemapped()) { |
431 | 426 | auto *Next = &Links[Current->getRemapIndex()]; |
432 | 426 | Current->updateRemap(NewRemap); |
433 | 426 | Current = Next; |
434 | 426 | } |
435 | 321 | |
436 | 321 | return *Current; |
437 | 321 | } |
438 | | |
439 | | /// Merges two sets into one another. Assumes that these sets are not |
440 | | /// already one in the same. |
441 | 475 | void merge(StratifiedIndex Idx1, StratifiedIndex Idx2) { |
442 | 475 | assert(inbounds(Idx1) && inbounds(Idx2)); |
443 | 475 | assert(&linksAt(Idx1) != &linksAt(Idx2) && |
444 | 475 | "Merging a set into itself is not allowed"); |
445 | 475 | |
446 | 475 | // CASE 1: If the set at `Idx1` is above or below `Idx2`, we need to merge |
447 | 475 | // both the |
448 | 475 | // given sets, and all sets between them, into one. |
449 | 475 | if (tryMergeUpwards(Idx1, Idx2)) |
450 | 0 | return; |
451 | 475 | |
452 | 475 | if (tryMergeUpwards(Idx2, Idx1)) |
453 | 0 | return; |
454 | 475 | |
455 | 475 | // CASE 2: The set at `Idx1` is not in the same chain as the set at `Idx2`. |
456 | 475 | // We therefore need to merge the two chains together. |
457 | 475 | mergeDirect(Idx1, Idx2); |
458 | 475 | } |
459 | | |
460 | | /// Merges two sets assuming that the set at `Idx1` is unreachable from |
461 | | /// traversing above or below the set at `Idx2`. |
462 | 475 | void mergeDirect(StratifiedIndex Idx1, StratifiedIndex Idx2) { |
463 | 475 | assert(inbounds(Idx1) && inbounds(Idx2)); |
464 | 475 | |
465 | 475 | auto *LinksInto = &linksAt(Idx1); |
466 | 475 | auto *LinksFrom = &linksAt(Idx2); |
467 | 475 | // Merging everything above LinksInto then proceeding to merge everything |
468 | 475 | // below LinksInto becomes problematic, so we go as far "up" as possible! |
469 | 484 | while (LinksInto->hasAbove() && LinksFrom->hasAbove()70 ) { |
470 | 9 | LinksInto = &linksAt(LinksInto->getAbove()); |
471 | 9 | LinksFrom = &linksAt(LinksFrom->getAbove()); |
472 | 9 | } |
473 | 475 | |
474 | 475 | if (LinksFrom->hasAbove()) { |
475 | 332 | LinksInto->setAbove(LinksFrom->getAbove()); |
476 | 332 | auto &NewAbove = linksAt(LinksInto->getAbove()); |
477 | 332 | NewAbove.setBelow(LinksInto->Number); |
478 | 332 | } |
479 | 475 | |
480 | 475 | // Merging strategy: |
481 | 475 | // > If neither has links below, stop. |
482 | 475 | // > If only `LinksInto` has links below, stop. |
483 | 475 | // > If only `LinksFrom` has links below, reset `LinksInto.Below` to |
484 | 475 | // match `LinksFrom.Below` |
485 | 475 | // > If both have links above, deal with those next. |
486 | 510 | while (LinksInto->hasBelow() && LinksFrom->hasBelow()65 ) { |
487 | 35 | auto FromAttrs = LinksFrom->getAttrs(); |
488 | 35 | LinksInto->setAttrs(FromAttrs); |
489 | 35 | |
490 | 35 | // Remap needs to happen after getBelow(), but before |
491 | 35 | // assignment of LinksFrom |
492 | 35 | auto *NewLinksFrom = &linksAt(LinksFrom->getBelow()); |
493 | 35 | LinksFrom->remapTo(LinksInto->Number); |
494 | 35 | LinksFrom = NewLinksFrom; |
495 | 35 | LinksInto = &linksAt(LinksInto->getBelow()); |
496 | 35 | } |
497 | 475 | |
498 | 475 | if (LinksFrom->hasBelow()) { |
499 | 58 | LinksInto->setBelow(LinksFrom->getBelow()); |
500 | 58 | auto &NewBelow = linksAt(LinksInto->getBelow()); |
501 | 58 | NewBelow.setAbove(LinksInto->Number); |
502 | 58 | } |
503 | 475 | |
504 | 475 | LinksInto->setAttrs(LinksFrom->getAttrs()); |
505 | 475 | LinksFrom->remapTo(LinksInto->Number); |
506 | 475 | } |
507 | | |
508 | | /// Checks to see if lowerIndex is at a level lower than upperIndex. If so, it |
509 | | /// will merge lowerIndex with upperIndex (and all of the sets between) and |
510 | | /// return true. Otherwise, it will return false. |
511 | 950 | bool tryMergeUpwards(StratifiedIndex LowerIndex, StratifiedIndex UpperIndex) { |
512 | 950 | assert(inbounds(LowerIndex) && inbounds(UpperIndex)); |
513 | 950 | auto *Lower = &linksAt(LowerIndex); |
514 | 950 | auto *Upper = &linksAt(UpperIndex); |
515 | 950 | if (Lower == Upper) |
516 | 0 | return true; |
517 | 950 | |
518 | 950 | SmallVector<BuilderLink *, 8> Found; |
519 | 950 | auto *Current = Lower; |
520 | 950 | auto Attrs = Current->getAttrs(); |
521 | 1.39k | while (Current->hasAbove() && Current != Upper442 ) { |
522 | 442 | Found.push_back(Current); |
523 | 442 | Attrs |= Current->getAttrs(); |
524 | 442 | Current = &linksAt(Current->getAbove()); |
525 | 442 | } |
526 | 950 | |
527 | 950 | if (Current != Upper) |
528 | 950 | return false; |
529 | 0 | |
530 | 0 | Upper->setAttrs(Attrs); |
531 | 0 |
|
532 | 0 | if (Lower->hasBelow()) { |
533 | 0 | auto NewBelowIndex = Lower->getBelow(); |
534 | 0 | Upper->setBelow(NewBelowIndex); |
535 | 0 | auto &NewBelow = linksAt(NewBelowIndex); |
536 | 0 | NewBelow.setAbove(UpperIndex); |
537 | 0 | } else { |
538 | 0 | Upper->clearBelow(); |
539 | 0 | } |
540 | 0 |
|
541 | 0 | for (const auto &Ptr : Found) |
542 | 0 | Ptr->remapTo(Upper->Number); |
543 | 0 |
|
544 | 0 | return true; |
545 | 0 | } |
546 | | |
547 | | Optional<const StratifiedInfo *> get(const T &Val) const { |
548 | | auto Result = Values.find(Val); |
549 | | if (Result == Values.end()) |
550 | | return None; |
551 | | return &Result->second; |
552 | | } |
553 | | |
554 | 1.92k | Optional<StratifiedInfo *> get(const T &Val) { |
555 | 1.92k | auto Result = Values.find(Val); |
556 | 1.92k | if (Result == Values.end()) |
557 | 724 | return None; |
558 | 1.20k | return &Result->second; |
559 | 1.20k | } |
560 | | |
561 | 477 | Optional<StratifiedIndex> indexOf(const T &Val) { |
562 | 477 | auto MaybeVal = get(Val); |
563 | 477 | if (!MaybeVal.hasValue()) |
564 | 0 | return None; |
565 | 477 | auto *Info = *MaybeVal; |
566 | 477 | auto &Link = linksAt(Info->Index); |
567 | 477 | return Link.Number; |
568 | 477 | } |
569 | | |
570 | 258 | StratifiedIndex addLinkBelow(StratifiedIndex Set) { |
571 | 258 | auto At = addLinks(); |
572 | 258 | Links[Set].setBelow(At); |
573 | 258 | Links[At].setAbove(Set); |
574 | 258 | return At; |
575 | 258 | } |
576 | | |
577 | | StratifiedIndex addLinkAbove(StratifiedIndex Set) { |
578 | | auto At = addLinks(); |
579 | | Links[At].setBelow(Set); |
580 | | Links[Set].setAbove(At); |
581 | | return At; |
582 | | } |
583 | | |
584 | 724 | StratifiedIndex getNewUnlinkedIndex() { return addLinks(); } |
585 | | |
586 | 982 | StratifiedIndex addLinks() { |
587 | 982 | auto Link = Links.size(); |
588 | 982 | Links.push_back(BuilderLink(Link)); |
589 | 982 | return Link; |
590 | 982 | } |
591 | | |
592 | | bool inbounds(StratifiedIndex N) const { return N < Links.size(); } |
593 | | }; |
594 | | } |
595 | | } |
596 | | #endif // LLVM_ADT_STRATIFIEDSETS_H |