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