262 lines · cpp
1//===- ConstantRangeListTest.cpp - ConstantRangeList tests ----------------===//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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/IR/ConstantRangeList.h"10#include "gtest/gtest.h"11 12using namespace llvm;13 14namespace {15 16using ConstantRangeListTest = ::testing::Test;17 18TEST_F(ConstantRangeListTest, Basics) {19 ConstantRangeList CRL1a;20 CRL1a.insert(0, 12);21 EXPECT_FALSE(CRL1a.empty());22 23 ConstantRangeList CRL1b;24 CRL1b.insert(0, 4);25 CRL1b.insert(4, 8);26 CRL1b.insert(8, 12);27 EXPECT_TRUE(CRL1a == CRL1b);28 29 ConstantRangeList CRL1c;30 CRL1c.insert(0, 4);31 CRL1c.insert(8, 12);32 CRL1c.insert(4, 8);33 EXPECT_TRUE(CRL1a == CRL1c);34 35 ConstantRangeList CRL2;36 CRL2.insert(-4, 0);37 CRL2.insert(8, 12);38 EXPECT_TRUE(CRL1a != CRL2);39}40 41TEST_F(ConstantRangeListTest, getConstantRangeList) {42 SmallVector<ConstantRange, 2> Empty;43 EXPECT_TRUE(ConstantRangeList::getConstantRangeList(Empty).has_value());44 45 SmallVector<ConstantRange, 2> Valid;46 Valid.push_back(ConstantRange(APInt(64, 0, true), APInt(64, 4, true)));47 Valid.push_back(ConstantRange(APInt(64, 8, true), APInt(64, 12, true)));48 EXPECT_TRUE(ConstantRangeList::getConstantRangeList(Valid).has_value());49 50 SmallVector<ConstantRange, 2> Invalid1;51 Invalid1.push_back(ConstantRange(APInt(64, 4, true), APInt(64, 0, true)));52 EXPECT_EQ(ConstantRangeList::getConstantRangeList(Invalid1), std::nullopt);53 54 SmallVector<ConstantRange, 2> Invalid2;55 Invalid2.push_back(ConstantRange(APInt(64, 0, true), APInt(64, 4, true)));56 Invalid2.push_back(ConstantRange(APInt(64, 12, true), APInt(64, 8, true)));57 EXPECT_EQ(ConstantRangeList::getConstantRangeList(Invalid2), std::nullopt);58 59 SmallVector<ConstantRange, 2> Invalid3;60 Invalid3.push_back(ConstantRange(APInt(64, 0, true), APInt(64, 4, true)));61 Invalid3.push_back(ConstantRange(APInt(64, 4, true), APInt(64, 8, true)));62 EXPECT_EQ(ConstantRangeList::getConstantRangeList(Invalid3), std::nullopt);63 64 SmallVector<ConstantRange, 2> Invalid4;65 Invalid4.push_back(ConstantRange(APInt(64, 0, true), APInt(64, 12, true)));66 Invalid4.push_back(ConstantRange(APInt(64, 8, true), APInt(64, 16, true)));67 EXPECT_EQ(ConstantRangeList::getConstantRangeList(Invalid4), std::nullopt);68}69 70TEST_F(ConstantRangeListTest, Insert) {71 ConstantRangeList CRL;72 CRL.insert(0, 4);73 CRL.insert(8, 12);74 // No overlap, left75 CRL.insert(-8, -4);76 // No overlap, right77 CRL.insert(16, 20);78 // No overlap, middle79 CRL.insert(13, 15);80 // Overlap with left81 CRL.insert(-6, -2);82 // Overlap with right83 CRL.insert(5, 9);84 // Overlap with left and right85 CRL.insert(14, 18);86 // Overlap cross ranges87 CRL.insert(2, 14);88 // An existing range89 CRL.insert(0, 20);90 91 ConstantRangeList Expected;92 Expected.insert(-8, -2);93 Expected.insert(0, 20);94 EXPECT_TRUE(CRL == Expected);95}96 97ConstantRangeList GetCRL(ArrayRef<std::pair<APInt, APInt>> Pairs) {98 SmallVector<ConstantRange, 2> Ranges;99 for (auto &[Start, End] : Pairs)100 Ranges.push_back(ConstantRange(Start, End));101 return ConstantRangeList(Ranges);102}103 104TEST_F(ConstantRangeListTest, Subtract) {105 APInt AP0 = APInt(64, 0, /*isSigned=*/true);106 APInt AP2 = APInt(64, 2, /*isSigned=*/true);107 APInt AP3 = APInt(64, 3, /*isSigned=*/true);108 APInt AP4 = APInt(64, 4, /*isSigned=*/true);109 APInt AP8 = APInt(64, 8, /*isSigned=*/true);110 APInt AP10 = APInt(64, 10, /*isSigned=*/true);111 APInt AP11 = APInt(64, 11, /*isSigned=*/true);112 APInt AP12 = APInt(64, 12, /*isSigned=*/true);113 ConstantRangeList CRL = GetCRL({{AP0, AP4}, {AP8, AP12}});114 115 // Execute ConstantRangeList::subtract(ConstantRange) and check the result116 // is expected. Pass "CRL" by value so that subtract() does not affect the117 // argument in caller.118 auto SubtractAndCheck = [](ConstantRangeList CRL,119 const std::pair<int64_t, int64_t> &Range,120 const ConstantRangeList &ExpectedCRL) {121 CRL.subtract(ConstantRange(APInt(64, Range.first, /*isSigned=*/true),122 APInt(64, Range.second, /*isSigned=*/true)));123 EXPECT_EQ(CRL, ExpectedCRL);124 };125 126 // No overlap127 SubtractAndCheck(CRL, {-4, 0}, CRL);128 SubtractAndCheck(CRL, {4, 8}, CRL);129 SubtractAndCheck(CRL, {12, 16}, CRL);130 131 // Overlap (left, right, or both)132 SubtractAndCheck(CRL, {-4, 2}, GetCRL({{AP2, AP4}, {AP8, AP12}}));133 SubtractAndCheck(CRL, {-4, 4}, GetCRL({{AP8, AP12}}));134 SubtractAndCheck(CRL, {-4, 8}, GetCRL({{AP8, AP12}}));135 SubtractAndCheck(CRL, {0, 2}, GetCRL({{AP2, AP4}, {AP8, AP12}}));136 SubtractAndCheck(CRL, {0, 4}, GetCRL({{AP8, AP12}}));137 SubtractAndCheck(CRL, {0, 8}, GetCRL({{AP8, AP12}}));138 SubtractAndCheck(CRL, {10, 12}, GetCRL({{AP0, AP4}, {AP8, AP10}}));139 SubtractAndCheck(CRL, {8, 12}, GetCRL({{AP0, AP4}}));140 SubtractAndCheck(CRL, {6, 12}, GetCRL({{AP0, AP4}}));141 SubtractAndCheck(CRL, {10, 16}, GetCRL({{AP0, AP4}, {AP8, AP10}}));142 SubtractAndCheck(CRL, {8, 16}, GetCRL({{AP0, AP4}}));143 SubtractAndCheck(CRL, {6, 16}, GetCRL({{AP0, AP4}}));144 SubtractAndCheck(CRL, {2, 10}, GetCRL({{AP0, AP2}, {AP10, AP12}}));145 146 // Subset147 SubtractAndCheck(CRL, {2, 3}, GetCRL({{AP0, AP2}, {AP3, AP4}, {AP8, AP12}}));148 SubtractAndCheck(CRL, {10, 11},149 GetCRL({{AP0, AP4}, {AP8, AP10}, {AP11, AP12}}));150 151 // Superset152 SubtractAndCheck(CRL, {0, 12}, GetCRL({}));153 SubtractAndCheck(CRL, {-4, 16}, GetCRL({}));154}155 156TEST_F(ConstantRangeListTest, Union) {157 APInt APN4 = APInt(64, -4, /*isSigned=*/true);158 APInt APN2 = APInt(64, -2, /*isSigned=*/true);159 APInt AP0 = APInt(64, 0, /*isSigned=*/true);160 APInt AP2 = APInt(64, 2, /*isSigned=*/true);161 APInt AP4 = APInt(64, 4, /*isSigned=*/true);162 APInt AP6 = APInt(64, 6, /*isSigned=*/true);163 APInt AP7 = APInt(64, 7, /*isSigned=*/true);164 APInt AP8 = APInt(64, 8, /*isSigned=*/true);165 APInt AP10 = APInt(64, 10, /*isSigned=*/true);166 APInt AP11 = APInt(64, 11, /*isSigned=*/true);167 APInt AP12 = APInt(64, 12, /*isSigned=*/true);168 APInt AP16 = APInt(64, 16, /*isSigned=*/true);169 APInt AP18 = APInt(64, 18, /*isSigned=*/true);170 ConstantRangeList CRL = GetCRL({{AP0, AP4}, {AP8, AP12}});171 172 // Union with a subset.173 ConstantRangeList Empty;174 EXPECT_EQ(CRL.unionWith(Empty), CRL);175 EXPECT_EQ(Empty.unionWith(CRL), CRL);176 177 EXPECT_EQ(CRL.unionWith(GetCRL({{AP0, AP2}})), CRL);178 EXPECT_EQ(CRL.unionWith(GetCRL({{AP10, AP12}})), CRL);179 180 EXPECT_EQ(CRL.unionWith(GetCRL({{AP0, AP2}, {AP8, AP10}})), CRL);181 EXPECT_EQ(CRL.unionWith(GetCRL({{AP0, AP2}, {AP10, AP12}})), CRL);182 EXPECT_EQ(CRL.unionWith(GetCRL({{AP2, AP4}, {AP8, AP10}})), CRL);183 EXPECT_EQ(CRL.unionWith(GetCRL({{AP2, AP4}, {AP10, AP12}})), CRL);184 185 EXPECT_EQ(CRL.unionWith(GetCRL({{AP0, AP4}, {AP8, AP10}, {AP11, AP12}})),186 CRL);187 188 EXPECT_EQ(CRL.unionWith(CRL), CRL);189 190 // Union with new ranges.191 EXPECT_EQ(CRL.unionWith(GetCRL({{APN4, APN2}})),192 GetCRL({{APN4, APN2}, {AP0, AP4}, {AP8, AP12}}));193 EXPECT_EQ(CRL.unionWith(GetCRL({{AP6, AP7}})),194 GetCRL({{AP0, AP4}, {AP6, AP7}, {AP8, AP12}}));195 EXPECT_EQ(CRL.unionWith(GetCRL({{AP16, AP18}})),196 GetCRL({{AP0, AP4}, {AP8, AP12}, {AP16, AP18}}));197 198 EXPECT_EQ(CRL.unionWith(GetCRL({{APN2, AP2}})),199 GetCRL({{APN2, AP4}, {AP8, AP12}}));200 EXPECT_EQ(CRL.unionWith(GetCRL({{AP2, AP6}})),201 GetCRL({{AP0, AP6}, {AP8, AP12}}));202 EXPECT_EQ(CRL.unionWith(GetCRL({{AP10, AP16}})),203 GetCRL({{AP0, AP4}, {AP8, AP16}}));204 205 EXPECT_EQ(CRL.unionWith(GetCRL({{APN2, AP10}})), GetCRL({{APN2, AP12}}));206 EXPECT_EQ(CRL.unionWith(GetCRL({{AP2, AP10}})), GetCRL({{AP0, AP12}}));207 EXPECT_EQ(CRL.unionWith(GetCRL({{AP4, AP16}})), GetCRL({{AP0, AP16}}));208 EXPECT_EQ(CRL.unionWith(GetCRL({{APN2, AP16}})), GetCRL({{APN2, AP16}}));209}210 211TEST_F(ConstantRangeListTest, Intersect) {212 APInt APN2 = APInt(64, -2, /*isSigned=*/true);213 APInt AP0 = APInt(64, 0, /*isSigned=*/true);214 APInt AP2 = APInt(64, 2, /*isSigned=*/true);215 APInt AP4 = APInt(64, 4, /*isSigned=*/true);216 APInt AP6 = APInt(64, 6, /*isSigned=*/true);217 APInt AP7 = APInt(64, 7, /*isSigned=*/true);218 APInt AP8 = APInt(64, 8, /*isSigned=*/true);219 APInt AP10 = APInt(64, 10, /*isSigned=*/true);220 APInt AP11 = APInt(64, 11, /*isSigned=*/true);221 APInt AP12 = APInt(64, 12, /*isSigned=*/true);222 APInt AP16 = APInt(64, 16, /*isSigned=*/true);223 ConstantRangeList CRL = GetCRL({{AP0, AP4}, {AP8, AP12}});224 225 // No intersection.226 ConstantRangeList Empty;227 EXPECT_EQ(CRL.intersectWith(Empty), Empty);228 EXPECT_EQ(Empty.intersectWith(CRL), Empty);229 230 EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP0}})), Empty);231 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP6, AP8}})), Empty);232 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP12, AP16}})), Empty);233 234 // Single intersect range.235 EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP2}})), GetCRL({{AP0, AP2}}));236 EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP6}})), GetCRL({{AP0, AP4}}));237 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP2, AP4}})), GetCRL({{AP2, AP4}}));238 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP2, AP6}})), GetCRL({{AP2, AP4}}));239 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP6, AP10}})), GetCRL({{AP8, AP10}}));240 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP6, AP16}})), GetCRL({{AP8, AP12}}));241 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP10, AP12}})), GetCRL({{AP10, AP12}}));242 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP10, AP16}})), GetCRL({{AP10, AP12}}));243 244 // Multiple intersect ranges.245 EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP10}})),246 GetCRL({{AP0, AP4}, {AP8, AP10}}));247 EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP16}})), CRL);248 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP2, AP10}})),249 GetCRL({{AP2, AP4}, {AP8, AP10}}));250 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP2, AP16}})),251 GetCRL({{AP2, AP4}, {AP8, AP12}}));252 EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP2}, {AP6, AP10}})),253 GetCRL({{AP0, AP2}, {AP8, AP10}}));254 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP2, AP6}, {AP10, AP16}})),255 GetCRL({{AP2, AP4}, {AP10, AP12}}));256 EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP2}, {AP7, AP10}, {AP11, AP16}})),257 GetCRL({{AP0, AP2}, {AP8, AP10}, {AP11, AP12}}));258 EXPECT_EQ(CRL.intersectWith(CRL), CRL);259}260 261} // anonymous namespace262