llvm/unittests/Support/AddressRangeTest.cpp

   1 //===- llvm/unittest/Support/AddresRangeTest.cpp --------------------------===//
   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 #include "llvm/ADT/AddressRanges.h"
  10 #include "llvm/Testing/Support/Error.h"
  11
  12 #include "gmock/gmock.h"
  13 #include "gtest/gtest.h"
  14 #include <string>
  15
  16 using namespace llvm;
  17
  18 TEST(AddressRangeTest, TestRanges) {
  19   // test llvm::AddressRange.
  20   const uint64_t StartAddr = 0x1000;
  21   const uint64_t EndAddr = 0x2000;
  22   // Verify constructor and API to ensure it takes start and end address.
  23   const AddressRange Range(StartAddr, EndAddr);
  24   EXPECT_EQ(Range.size(), EndAddr - StartAddr);
  25
  26   // Verify llvm::AddressRange::contains().
  27   EXPECT_FALSE(Range.contains(0));
  28   EXPECT_FALSE(Range.contains(StartAddr - 1));
  29   EXPECT_TRUE(Range.contains(StartAddr));
  30   EXPECT_TRUE(Range.contains(EndAddr - 1));
  31   EXPECT_FALSE(Range.contains(EndAddr));
  32   EXPECT_FALSE(Range.contains(UINT64_MAX));
  33
  34   const AddressRange RangeSame(StartAddr, EndAddr);
  35   const AddressRange RangeDifferentStart(StartAddr + 1, EndAddr);
  36   const AddressRange RangeDifferentEnd(StartAddr, EndAddr + 1);
  37   const AddressRange RangeDifferentStartEnd(StartAddr + 1, EndAddr + 1);
  38   // Test == and != with values that are the same
  39   EXPECT_EQ(Range, RangeSame);
  40   EXPECT_FALSE(Range != RangeSame);
  41   // Test == and != with values that are the different
  42   EXPECT_NE(Range, RangeDifferentStart);
  43   EXPECT_NE(Range, RangeDifferentEnd);
  44   EXPECT_NE(Range, RangeDifferentStartEnd);
  45   EXPECT_FALSE(Range == RangeDifferentStart);
  46   EXPECT_FALSE(Range == RangeDifferentEnd);
  47   EXPECT_FALSE(Range == RangeDifferentStartEnd);
  48
  49   // Test "bool operator<(const AddressRange &, const AddressRange &)".
  50   EXPECT_FALSE(Range < RangeSame);
  51   EXPECT_FALSE(RangeSame < Range);
  52   EXPECT_LT(Range, RangeDifferentStart);
  53   EXPECT_LT(Range, RangeDifferentEnd);
  54   EXPECT_LT(Range, RangeDifferentStartEnd);
  55   // Test "bool operator<(const AddressRange &, uint64_t)"
  56   EXPECT_LT(Range.start(), StartAddr + 1);
  57   // Test "bool operator<(uint64_t, const AddressRange &)"
  58   EXPECT_LT(StartAddr - 1, Range.start());
  59
  60   // Verify llvm::AddressRange::isContiguousWith() and
  61   // llvm::AddressRange::intersects().
  62   const AddressRange EndsBeforeRangeStart(0, StartAddr - 1);
  63   const AddressRange EndsAtRangeStart(0, StartAddr);
  64   const AddressRange OverlapsRangeStart(StartAddr - 1, StartAddr + 1);
  65   const AddressRange InsideRange(StartAddr + 1, EndAddr - 1);
  66   const AddressRange OverlapsRangeEnd(EndAddr - 1, EndAddr + 1);
  67   const AddressRange StartsAtRangeEnd(EndAddr, EndAddr + 0x100);
  68   const AddressRange StartsAfterRangeEnd(EndAddr + 1, EndAddr + 0x100);
  69
  70   EXPECT_FALSE(Range.intersects(EndsBeforeRangeStart));
  71   EXPECT_FALSE(Range.intersects(EndsAtRangeStart));
  72   EXPECT_TRUE(Range.intersects(OverlapsRangeStart));
  73   EXPECT_TRUE(Range.intersects(InsideRange));
  74   EXPECT_TRUE(Range.intersects(OverlapsRangeEnd));
  75   EXPECT_FALSE(Range.intersects(StartsAtRangeEnd));
  76   EXPECT_FALSE(Range.intersects(StartsAfterRangeEnd));
  77
  78   // Test the functions that maintain address ranges:
  79   //  "bool AddressRange::contains(uint64_t Addr) const;"
  80   //  "void AddressRanges::insert(const AddressRange &R);"
  81   AddressRanges Ranges;
  82   Ranges.insert(AddressRange(0x1000, 0x2000));
  83   Ranges.insert(AddressRange(0x2000, 0x3000));
  84   Ranges.insert(AddressRange(0x4000, 0x5000));
  85
  86   EXPECT_FALSE(Ranges.contains(0));
  87   EXPECT_FALSE(Ranges.contains(0x1000 - 1));
  88   EXPECT_TRUE(Ranges.contains(0x1000));
  89   EXPECT_TRUE(Ranges.contains(0x2000));
  90   EXPECT_TRUE(Ranges.contains(0x4000));
  91   EXPECT_TRUE(Ranges.contains(0x2000 - 1));
  92   EXPECT_TRUE(Ranges.contains(0x3000 - 1));
  93   EXPECT_FALSE(Ranges.contains(0x3000 + 1));
  94   EXPECT_TRUE(Ranges.contains(0x5000 - 1));
  95   EXPECT_FALSE(Ranges.contains(0x5000 + 1));
  96   EXPECT_FALSE(Ranges.contains(UINT64_MAX));
  97
  98   EXPECT_FALSE(Ranges.contains(AddressRange()));
  99   EXPECT_FALSE(Ranges.contains(AddressRange(0x1000 - 1, 0x1000)));
 100   EXPECT_FALSE(Ranges.contains(AddressRange(0x1000, 0x1000)));
 101   EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x1000 + 1)));
 102   EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x2000)));
 103   EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x2001)));
 104   EXPECT_TRUE(Ranges.contains(AddressRange(0x2000, 0x3000)));
 105   EXPECT_FALSE(Ranges.contains(AddressRange(0x2000, 0x3001)));
 106   EXPECT_FALSE(Ranges.contains(AddressRange(0x3000, 0x3001)));
 107   EXPECT_FALSE(Ranges.contains(AddressRange(0x1500, 0x4500)));
 108   EXPECT_FALSE(Ranges.contains(AddressRange(0x5000, 0x5001)));
 109
 110   // Verify that intersecting ranges get combined
 111   Ranges.clear();
 112   Ranges.insert(AddressRange(0x1100, 0x1F00));
 113   // Verify a wholy contained range that is added doesn't do anything.
 114   Ranges.insert(AddressRange(0x1500, 0x1F00));
 115   EXPECT_EQ(Ranges.size(), 1u);
 116   EXPECT_EQ(Ranges[0], AddressRange(0x1100, 0x1F00));
 117
 118   // Verify a range that starts before and intersects gets combined.
 119   Ranges.insert(AddressRange(0x1000, Ranges[0].start() + 1));
 120   EXPECT_EQ(Ranges.size(), 1u);
 121   EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x1F00));
 122
 123   // Verify a range that starts inside and extends ranges gets combined.
 124   Ranges.insert(AddressRange(Ranges[0].end() - 1, 0x2000));
 125   EXPECT_EQ(Ranges.size(), 1u);
 126   EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2000));
 127
 128   // Verify that adjacent ranges get combined
 129   Ranges.insert(AddressRange(0x2000, 0x2fff));
 130   EXPECT_EQ(Ranges.size(), 1u);
 131   EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2fff));
 132
 133   // Verify that ranges having 1 byte gap do not get combined
 134   Ranges.insert(AddressRange(0x3000, 0x4000));
 135   EXPECT_EQ(Ranges.size(), 2u);
 136   EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2fff));
 137   EXPECT_EQ(Ranges[1], AddressRange(0x3000, 0x4000));
 138
 139   // Verify if we add an address range that intersects two ranges
 140   // that they get combined
 141   Ranges.insert(AddressRange(Ranges[0].end() - 1, Ranges[1].start() + 1));
 142   EXPECT_EQ(Ranges.size(), 1u);
 143   EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x4000));
 144
 145   Ranges.insert(AddressRange(0x3000, 0x4000));
 146   Ranges.insert(AddressRange(0x4000, 0x5000));
 147   Ranges.insert(AddressRange(0x2000, 0x4500));
 148   EXPECT_EQ(Ranges.size(), 1u);
 149   EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x5000));
 150 }
 151
 152 TEST(AddressRangeTest, TestRangesMap) {
 153   AddressRangesMap<int> Ranges;
 154
 155   EXPECT_EQ(Ranges.size(), 0u);
 156   EXPECT_TRUE(Ranges.empty());
 157
 158   // Add single range.
 159   Ranges.insert(AddressRange(0x1000, 0x2000), 0xfe);
 160   EXPECT_EQ(Ranges.size(), 1u);
 161   EXPECT_FALSE(Ranges.empty());
 162   EXPECT_TRUE(Ranges.contains(0x1500));
 163   EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x2000)));
 164
 165   // Clear ranges.
 166   Ranges.clear();
 167   EXPECT_EQ(Ranges.size(), 0u);
 168   EXPECT_TRUE(Ranges.empty());
 169
 170   // Add range and check value.
 171   Ranges.insert(AddressRange(0x1000, 0x2000), 0xfe);
 172   EXPECT_EQ(Ranges.size(), 1u);
 173   EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0xfe);
 174
 175   // Add adjacent range and check value.
 176   Ranges.insert(AddressRange(0x2000, 0x3000), 0xfc);
 177   EXPECT_EQ(Ranges.size(), 1u);
 178   EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0xfc);
 179   EXPECT_EQ(Ranges.getRangeValueThatContains(0x2000)->second, 0xfc);
 180   EXPECT_EQ(Ranges.getRangeValueThatContains(0x2900)->second, 0xfc);
 181   EXPECT_FALSE(Ranges.getRangeValueThatContains(0x3000));
 182
 183   // Add intersecting range and check value.
 184   Ranges.insert(AddressRange(0x2000, 0x3000), 0xff);
 185   EXPECT_EQ(Ranges.size(), 1u);
 186   EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0xff);
 187
 188   // Add second range and check values.
 189   Ranges.insert(AddressRange(0x4000, 0x5000), 0x0);
 190   EXPECT_EQ(Ranges.size(), 2u);
 191   EXPECT_EQ(Ranges[0].second, 0xff);
 192   EXPECT_EQ(Ranges[1].second, 0x0);
 193   EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0xff);
 194   EXPECT_EQ(Ranges.getRangeValueThatContains(0x4000)->second, 0x0);
 195
 196   // Add intersecting range and check value.
 197   Ranges.insert(AddressRange(0x0, 0x6000), 0x1);
 198   EXPECT_EQ(Ranges.size(), 1u);
 199   EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0x1);
 200
 201   // Check that values are correctly preserved for combined ranges.
 202   Ranges.clear();
 203   Ranges.insert(AddressRange(0x0, 0xff), 0x1);
 204   Ranges.insert(AddressRange(0x100, 0x1ff), 0x2);
 205   Ranges.insert(AddressRange(0x200, 0x2ff), 0x3);
 206   Ranges.insert(AddressRange(0x300, 0x3ff), 0x4);
 207   Ranges.insert(AddressRange(0x400, 0x4ff), 0x5);
 208   Ranges.insert(AddressRange(0x500, 0x5ff), 0x6);
 209   Ranges.insert(AddressRange(0x600, 0x6ff), 0x7);
 210
 211   Ranges.insert(AddressRange(0x150, 0x350), 0xff);
 212   EXPECT_EQ(Ranges.size(), 5u);
 213   EXPECT_EQ(Ranges[0].first, AddressRange(0x0, 0xff));
 214   EXPECT_EQ(Ranges[0].second, 0x1);
 215   EXPECT_EQ(Ranges[1].first, AddressRange(0x100, 0x3ff));
 216   EXPECT_EQ(Ranges[1].second, 0xff);
 217   EXPECT_EQ(Ranges[2].first, AddressRange(0x400, 0x4ff));
 218   EXPECT_EQ(Ranges[2].second, 0x5);
 219   EXPECT_EQ(Ranges[3].first, AddressRange(0x500, 0x5ff));
 220   EXPECT_EQ(Ranges[3].second, 0x6);
 221   EXPECT_EQ(Ranges[4].first, AddressRange(0x600, 0x6ff));
 222   EXPECT_EQ(Ranges[4].second, 0x7);
 223
 224   Ranges.insert(AddressRange(0x3ff, 0x400), 0x5);
 225   EXPECT_EQ(Ranges.size(), 4u);
 226   EXPECT_EQ(Ranges[0].first, AddressRange(0x0, 0xff));
 227   EXPECT_EQ(Ranges[0].second, 0x1);
 228   EXPECT_EQ(Ranges[1].first, AddressRange(0x100, 0x4ff));
 229   EXPECT_EQ(Ranges[1].second, 0x5);
 230   EXPECT_EQ(Ranges[2].first, AddressRange(0x500, 0x5ff));
 231   EXPECT_EQ(Ranges[2].second, 0x6);
 232   EXPECT_EQ(Ranges[3].first, AddressRange(0x600, 0x6ff));
 233   EXPECT_EQ(Ranges[3].second, 0x7);
 234 }