llvm/ADT/AddressRanges.h

0001 //===- AddressRanges.h ------------------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_ADT_ADDRESSRANGES_H
0010 #define LLVM_ADT_ADDRESSRANGES_H
0011
0012 #include "llvm/ADT/STLExtras.h"
0013 #include "llvm/ADT/SmallVector.h"
0014 #include <cassert>
0015 #include <optional>
0016 #include <stdint.h>
0017
0018 namespace llvm {
0019
0020 /// A class that represents an address range. The range is specified using
0021 /// a start and an end address: [Start, End).
0022 class AddressRange {
0023 public:
0024   AddressRange() {}
0025   AddressRange(uint64_t S, uint64_t E) : Start(S), End(E) {
0026     assert(Start <= End);
0027   }
0028   uint64_t start() const { return Start; }
0029   uint64_t end() const { return End; }
0030   uint64_t size() const { return End - Start; }
0031   uint64_t empty() const { return size() == 0; }
0032   bool contains(uint64_t Addr) const { return Start <= Addr && Addr < End; }
0033   bool contains(const AddressRange &R) const {
0034     return Start <= R.Start && R.End <= End;
0035   }
0036   bool intersects(const AddressRange &R) const {
0037     return Start < R.End && R.Start < End;
0038   }
0039   bool operator==(const AddressRange &R) const {
0040     return Start == R.Start && End == R.End;
0041   }
0042   bool operator!=(const AddressRange &R) const { return !(*this == R); }
0043   bool operator<(const AddressRange &R) const {
0044     return std::make_pair(Start, End) < std::make_pair(R.Start, R.End);
0045   }
0046
0047 private:
0048   uint64_t Start = 0;
0049   uint64_t End = 0;
0050 };
0051
0052 /// The AddressRangesBase class presents the base functionality for the
0053 /// normalized address ranges collection. This class keeps a sorted vector
0054 /// of AddressRange-like objects and can perform searches efficiently.
0055 /// The address ranges are always sorted and never contain any invalid,
0056 /// empty or intersected address ranges.
0057
0058 template <typename T> class AddressRangesBase {
0059 protected:
0060   using Collection = SmallVector<T>;
0061   Collection Ranges;
0062
0063 public:
0064   void clear() { Ranges.clear(); }
0065   bool empty() const { return Ranges.empty(); }
0066   bool contains(uint64_t Addr) const {
0067     return find(Addr, Addr + 1) != Ranges.end();
0068   }
0069   bool contains(AddressRange Range) const {
0070     return find(Range.start(), Range.end()) != Ranges.end();
0071   }
0072   void reserve(size_t Capacity) { Ranges.reserve(Capacity); }
0073   size_t size() const { return Ranges.size(); }
0074
0075   std::optional<T> getRangeThatContains(uint64_t Addr) const {
0076     typename Collection::const_iterator It = find(Addr, Addr + 1);
0077     if (It == Ranges.end())
0078       return std::nullopt;
0079
0080     return *It;
0081   }
0082
0083   typename Collection::const_iterator begin() const { return Ranges.begin(); }
0084   typename Collection::const_iterator end() const { return Ranges.end(); }
0085
0086   const T &operator[](size_t i) const {
0087     assert(i < Ranges.size());
0088     return Ranges[i];
0089   }
0090
0091   bool operator==(const AddressRangesBase<T> &RHS) const {
0092     return Ranges == RHS.Ranges;
0093   }
0094
0095 protected:
0096   typename Collection::const_iterator find(uint64_t Start, uint64_t End) const {
0097     if (Start >= End)
0098       return Ranges.end();
0099
0100     auto It =
0101         std::partition_point(Ranges.begin(), Ranges.end(), [=](const T &R) {
0102           return AddressRange(R).start() <= Start;
0103         });
0104
0105     if (It == Ranges.begin())
0106       return Ranges.end();
0107
0108     --It;
0109     if (End > AddressRange(*It).end())
0110       return Ranges.end();
0111
0112     return It;
0113   }
0114 };
0115
0116 /// The AddressRanges class helps normalize address range collections.
0117 /// This class keeps a sorted vector of AddressRange objects and can perform
0118 /// insertions and searches efficiently. Intersecting([100,200), [150,300))
0119 /// and adjacent([100,200), [200,300)) address ranges are combined during
0120 /// insertion.
0121 class AddressRanges : public AddressRangesBase<AddressRange> {
0122 public:
0123   Collection::const_iterator insert(AddressRange Range) {
0124     if (Range.empty())
0125       return Ranges.end();
0126
0127     auto It = llvm::upper_bound(Ranges, Range);
0128     auto It2 = It;
0129     while (It2 != Ranges.end() && It2->start() <= Range.end())
0130       ++It2;
0131     if (It != It2) {
0132       Range = {Range.start(), std::max(Range.end(), std::prev(It2)->end())};
0133       It = Ranges.erase(It, It2);
0134     }
0135     if (It != Ranges.begin() && Range.start() <= std::prev(It)->end()) {
0136       --It;
0137       *It = {It->start(), std::max(It->end(), Range.end())};
0138       return It;
0139     }
0140
0141     return Ranges.insert(It, Range);
0142   }
0143 };
0144
0145 class AddressRangeValuePair {
0146 public:
0147   operator AddressRange() const { return Range; }
0148
0149   AddressRange Range;
0150   int64_t Value = 0;
0151 };
0152
0153 inline bool operator==(const AddressRangeValuePair &LHS,
0154                        const AddressRangeValuePair &RHS) {
0155   return LHS.Range == RHS.Range && LHS.Value == RHS.Value;
0156 }
0157
0158 /// AddressRangesMap class maps values to the address ranges.
0159 /// It keeps normalized address ranges and corresponding values.
0160 /// This class keeps a sorted vector of AddressRangeValuePair objects
0161 /// and can perform insertions and searches efficiently.
0162 /// Intersecting([100,200), [150,300)) ranges splitted into non-conflicting
0163 /// parts([100,200), [200,300)). Adjacent([100,200), [200,300)) address
0164 /// ranges are not combined during insertion.
0165 class AddressRangesMap : public AddressRangesBase<AddressRangeValuePair> {
0166 public:
0167   void insert(AddressRange Range, int64_t Value) {
0168     if (Range.empty())
0169       return;
0170
0171     // Search for range which is less than or equal incoming Range.
0172     auto It = std::partition_point(Ranges.begin(), Ranges.end(),
0173                                    [=](const AddressRangeValuePair &R) {
0174                                      return R.Range.start() <= Range.start();
0175                                    });
0176
0177     if (It != Ranges.begin())
0178       It--;
0179
0180     while (!Range.empty()) {
0181       // Inserted range does not overlap with any range.
0182       // Store it into the Ranges collection.
0183       if (It == Ranges.end() || Range.end() <= It->Range.start()) {
0184         Ranges.insert(It, {Range, Value});
0185         return;
0186       }
0187
0188       // Inserted range partially overlaps with current range.
0189       // Store not overlapped part of inserted range.
0190       if (Range.start() < It->Range.start()) {
0191         It = Ranges.insert(It, {{Range.start(), It->Range.start()}, Value});
0192         It++;
0193         Range = {It->Range.start(), Range.end()};
0194         continue;
0195       }
0196
0197       // Inserted range fully overlaps with current range.
0198       if (Range.end() <= It->Range.end())
0199         return;
0200
0201       // Inserted range partially overlaps with current range.
0202       // Remove overlapped part from the inserted range.
0203       if (Range.start() < It->Range.end())
0204         Range = {It->Range.end(), Range.end()};
0205
0206       It++;
0207     }
0208   }
0209 };
0210
0211 } // namespace llvm
0212
0213 #endif // LLVM_ADT_ADDRESSRANGES_H