1 //===-- IntervalSet.h -------------------------------------------*- C++ -*-===// 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 FORTRAN_LOWER_INTERVALSET_H 10 #define FORTRAN_LOWER_INTERVALSET_H 11 12 #include <cassert> 13 #include <map> 14 15 namespace Fortran::lower { 16 17 //===----------------------------------------------------------------------===// 18 // Interval set 19 //===----------------------------------------------------------------------===// 20 21 /// Interval set to keep track of intervals, merging them when they overlap one 22 /// another. Used to refine the pseudo-offset ranges of the front-end symbols 23 /// into groups of aliasing variables. 24 struct IntervalSet { 25 using MAP = std::map<std::size_t, std::size_t>; 26 using Iterator = MAP::const_iterator; 27 28 // Handles the merging of overlapping intervals correctly, efficiently. mergeIntervalSet29 void merge(std::size_t lo, std::size_t up) { 30 assert(lo <= up); 31 if (empty()) { 32 m.insert({lo, up}); 33 return; 34 } 35 auto i = m.lower_bound(lo); 36 // i->first >= lo 37 if (i == begin()) { 38 if (up < i->first) { 39 // [lo..up] < i->first 40 m.insert({lo, up}); 41 return; 42 } 43 // up >= i->first 44 if (i->second > up) 45 up = i->second; 46 fuse(lo, up, i); 47 return; 48 } 49 auto i1 = i; 50 if (i == end() || i->first > lo) 51 i = std::prev(i); 52 // i->first <= lo 53 if (i->second >= up) { 54 // i->first <= lo && up <= i->second, keep i 55 return; 56 } 57 // i->second < up 58 if (i->second < lo) { 59 if (i1 == end() || i1->first > up) { 60 // i < [lo..up] < i1 61 m.insert({lo, up}); 62 return; 63 } 64 // i < [lo..up], i1->first <= up --> [lo..up] union [i1..?] 65 i = i1; 66 } else { 67 // i->first <= lo, lo <= i->second --> [i->first..up] union [i..?] 68 lo = i->first; 69 } 70 fuse(lo, up, i); 71 } 72 findIntervalSet73 Iterator find(std::size_t pt) const { 74 auto i = m.lower_bound(pt); 75 if (i != end() && i->first == pt) 76 return i; 77 if (i == begin()) 78 return end(); 79 i = std::prev(i); 80 if (i->second < pt) 81 return end(); 82 return i; 83 } 84 beginIntervalSet85 Iterator begin() const { return m.begin(); } endIntervalSet86 Iterator end() const { return m.end(); } emptyIntervalSet87 bool empty() const { return m.empty(); } sizeIntervalSet88 std::size_t size() const { return m.size(); } 89 90 private: 91 // Find and fuse overlapping sets. fuseIntervalSet92 void fuse(std::size_t lo, std::size_t up, Iterator i) { 93 auto j = m.upper_bound(up); 94 // up < j->first 95 std::size_t cu = std::prev(j)->second; 96 // cu < j->first 97 if (cu > up) 98 up = cu; 99 m.erase(i, j); 100 // merge [i .. j) with [i->first, max(up, cu)] 101 m.insert({lo, up}); 102 } 103 104 MAP m{}; 105 }; 106 107 } // namespace Fortran::lower 108 109 #endif // FORTRAN_LOWER_INTERVALSET_H 110