diff --git a/flang/lib/Lower/IntervalSet.h b/flang/lib/Lower/IntervalSet.h deleted file mode 100644 --- a/flang/lib/Lower/IntervalSet.h +++ /dev/null @@ -1,109 +0,0 @@ -//===-- 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 -#include - -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; - 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