[HLSL][Sema] Use hlsl::BindingInfoBuilder instead of RangeInfo. NFC (#150634)

Clean up some duplicated logic. We had two ways to do the same thing
here, and BindingInfoBuilder is more flexible.

4 files changed, 0 insertions, 420 deletions

diff --git a/llvm/include/llvm/Frontend/HLSL/RootSignatureValidations.h b/llvm/include/llvm/Frontend/HLSL/RootSignatureValidations.h
index f1e223d..fde32a1 100644
--- a/llvm/include/llvm/Frontend/HLSL/RootSignatureValidations.h
+++ b/llvm/include/llvm/Frontend/HLSL/RootSignatureValidations.h
@@ -41,114 +41,6 @@ LLVM_ABI bool verifyComparisonFunc(uint32_t ComparisonFunc);
 LLVM_ABI bool verifyBorderColor(uint32_t BorderColor);
 LLVM_ABI bool verifyLOD(float LOD);
 
-struct RangeInfo {
-  const static uint32_t Unbounded = ~0u;
-
-  // Interval information
-  uint32_t LowerBound;
-  uint32_t UpperBound;
-
-  // Information retained for determining overlap
-  llvm::dxil::ResourceClass Class;
-  uint32_t Space;
-  llvm::dxbc::ShaderVisibility Visibility;
-
-  bool operator==(const RangeInfo &RHS) const {
-    return std::tie(LowerBound, UpperBound, Class, Space, Visibility) ==
-           std::tie(RHS.LowerBound, RHS.UpperBound, RHS.Class, RHS.Space,
-                    RHS.Visibility);
-  }
-
-  bool operator<(const RangeInfo &RHS) const {
-    return std::tie(Class, Space, LowerBound, UpperBound, Visibility) <
-           std::tie(RHS.Class, RHS.Space, RHS.LowerBound, RHS.UpperBound,
-                    RHS.Visibility);
-  }
-};
-
-class ResourceRange {
-public:
-  using MapT = llvm::IntervalMap<uint32_t, const RangeInfo *, 16,
-                                 llvm::IntervalMapInfo<uint32_t>>;
-
-private:
-  MapT Intervals;
-
-public:
-  ResourceRange(MapT::Allocator &Allocator) : Intervals(MapT(Allocator)) {}
-
-  // Returns a reference to the first RangeInfo that overlaps with
-  // [Info.LowerBound;Info.UpperBound], or, std::nullopt if there is no overlap
-  LLVM_ABI std::optional<const RangeInfo *>
-  getOverlapping(const RangeInfo &Info) const;
-
-  // Return the mapped RangeInfo at X or nullptr if no mapping exists
-  LLVM_ABI const RangeInfo *lookup(uint32_t X) const;
-
-  // Removes all entries of the ResourceRange
-  LLVM_ABI void clear();
-
-  // Insert the required (sub-)intervals such that the interval of [a;b] =
-  // [Info.LowerBound, Info.UpperBound] is covered and points to a valid
-  // RangeInfo &.
-  //
-  // For instance consider the following chain of inserting RangeInfos with the
-  // intervals denoting the Lower/Upper-bounds:
-  //
-  // A = [0;2]
-  //   insert(A) -> false
-  //   intervals: [0;2] -> &A
-  // B = [5;7]
-  //   insert(B) -> false
-  //   intervals: [0;2] -> &A, [5;7] -> &B
-  // C = [4;7]
-  //   insert(C) -> true
-  //   intervals: [0;2] -> &A, [4;7] -> &C
-  // D = [1;5]
-  //   insert(D) -> true
-  //   intervals: [0;2] -> &A, [3;3] -> &D, [4;7] -> &C
-  // E = [0;unbounded]
-  //   insert(E) -> true
-  //   intervals: [0;unbounded] -> E
-  //
-  // Returns a reference to the first RangeInfo that overlaps with
-  // [Info.LowerBound;Info.UpperBound], or, std::nullopt if there is no overlap
-  // (equivalent to getOverlapping)
-  LLVM_ABI std::optional<const RangeInfo *> insert(const RangeInfo &Info);
-};
-
-struct OverlappingRanges {
-  const RangeInfo *A;
-  const RangeInfo *B;
-
-  OverlappingRanges(const RangeInfo *A, const RangeInfo *B) : A(A), B(B) {}
-};
-
-/// The following conducts analysis on resource ranges to detect and report
-/// any overlaps in resource ranges.
-///
-/// A resource range overlaps with another resource range if they have:
-/// - equivalent ResourceClass (SRV, UAV, CBuffer, Sampler)
-/// - equivalent resource space
-/// - overlapping visbility
-///
-/// The algorithm is implemented in the following steps:
-///
-/// 1. The user will collect RangeInfo from relevant RootElements:
-///   - RangeInfo will retain the interval, ResourceClass, Space and Visibility
-///   - It will also contain an index so that it can be associated to
-/// additional diagnostic information
-/// 2. The user is required to sort the RangeInfo's such that they are grouped
-/// together by ResourceClass and Space
-/// 3. Iterate through the collected RangeInfos by their groups
-///   - For each group we will have a ResourceRange for each visibility
-///   - As we iterate through we will:
-///      A: Insert the current RangeInfo into the corresponding Visibility
-///   ResourceRange
-///      B: Check for overlap with any overlapping Visibility ResourceRange
-LLVM_ABI llvm::SmallVector<OverlappingRanges>
-findOverlappingRanges(ArrayRef<RangeInfo> Infos);
-
 } // namespace rootsig
 } // namespace hlsl
 } // namespace llvm
diff --git a/llvm/lib/Frontend/HLSL/RootSignatureValidations.cpp b/llvm/lib/Frontend/HLSL/RootSignatureValidations.cpp
index f11c7d2..9d84aa8 100644
--- a/llvm/lib/Frontend/HLSL/RootSignatureValidations.cpp
+++ b/llvm/lib/Frontend/HLSL/RootSignatureValidations.cpp
@@ -180,140 +180,6 @@ bool verifyBorderColor(uint32_t BorderColor) {
 
 bool verifyLOD(float LOD) { return !std::isnan(LOD); }
 
-std::optional<const RangeInfo *>
-ResourceRange::getOverlapping(const RangeInfo &Info) const {
-  MapT::const_iterator Interval = Intervals.find(Info.LowerBound);
-  if (!Interval.valid() || Info.UpperBound < Interval.start())
-    return std::nullopt;
-  return Interval.value();
-}
-
-const RangeInfo *ResourceRange::lookup(uint32_t X) const {
-  return Intervals.lookup(X, nullptr);
-}
-
-void ResourceRange::clear() { return Intervals.clear(); }
-
-std::optional<const RangeInfo *> ResourceRange::insert(const RangeInfo &Info) {
-  uint32_t LowerBound = Info.LowerBound;
-  uint32_t UpperBound = Info.UpperBound;
-
-  std::optional<const RangeInfo *> Res = std::nullopt;
-  MapT::iterator Interval = Intervals.begin();
-
-  while (true) {
-    if (UpperBound < LowerBound)
-      break;
-
-    Interval.advanceTo(LowerBound);
-    if (!Interval.valid()) // No interval found
-      break;
-
-    // Let Interval = [x;y] and [LowerBound;UpperBound] = [a;b] and note that
-    // a <= y implicitly from Intervals.find(LowerBound)
-    if (UpperBound < Interval.start())
-      break; // found interval does not overlap with inserted one
-
-    if (!Res.has_value()) // Update to be the first found intersection
-      Res = Interval.value();
-
-    if (Interval.start() <= LowerBound && UpperBound <= Interval.stop()) {
-      // x <= a <= b <= y implies that [a;b] is covered by [x;y]
-      //  -> so we don't need to insert this, report an overlap
-      return Res;
-    } else if (LowerBound <= Interval.start() &&
-               Interval.stop() <= UpperBound) {
-      // a <= x <= y <= b implies that [x;y] is covered by [a;b]
-      //  -> so remove the existing interval that we will cover with the
-      //  overwrite
-      Interval.erase();
-    } else if (LowerBound < Interval.start() && UpperBound <= Interval.stop()) {
-      // a < x <= b <= y implies that [a; x] is not covered but [x;b] is
-      //  -> so set b = x - 1 such that [a;x-1] is now the interval to insert
-      UpperBound = Interval.start() - 1;
-    } else if (Interval.start() <= LowerBound && Interval.stop() < UpperBound) {
-      // a < x <= b <= y implies that [y; b] is not covered but [a;y] is
-      //  -> so set a = y + 1 such that [y+1;b] is now the interval to insert
-      LowerBound = Interval.stop() + 1;
-    }
-  }
-
-  assert(LowerBound <= UpperBound && "Attempting to insert an empty interval");
-  Intervals.insert(LowerBound, UpperBound, &Info);
-  return Res;
-}
-
-llvm::SmallVector<OverlappingRanges>
-findOverlappingRanges(ArrayRef<RangeInfo> Infos) {
-  // It is expected that Infos is filled with valid RangeInfos and that
-  // they are sorted with respect to the RangeInfo <operator
-  assert(llvm::is_sorted(Infos) && "Ranges must be sorted");
-
-  llvm::SmallVector<OverlappingRanges> Overlaps;
-  using GroupT = std::pair<dxil::ResourceClass, /*Space*/ uint32_t>;
-
-  // First we will init our state to track:
-  if (Infos.size() == 0)
-    return Overlaps; // No ranges to overlap
-  GroupT CurGroup = {Infos[0].Class, Infos[0].Space};
-
-  // Create a ResourceRange for each Visibility
-  ResourceRange::MapT::Allocator Allocator;
-  std::array<ResourceRange, 8> Ranges = {
-      ResourceRange(Allocator), // All
-      ResourceRange(Allocator), // Vertex
-      ResourceRange(Allocator), // Hull
-      ResourceRange(Allocator), // Domain
-      ResourceRange(Allocator), // Geometry
-      ResourceRange(Allocator), // Pixel
-      ResourceRange(Allocator), // Amplification
-      ResourceRange(Allocator), // Mesh
-  };
-
-  // Reset the ResourceRanges for when we iterate through a new group
-  auto ClearRanges = [&Ranges]() {
-    for (ResourceRange &Range : Ranges)
-      Range.clear();
-  };
-
-  // Iterate through collected RangeInfos
-  for (const RangeInfo &Info : Infos) {
-    GroupT InfoGroup = {Info.Class, Info.Space};
-    // Reset our ResourceRanges when we enter a new group
-    if (CurGroup != InfoGroup) {
-      ClearRanges();
-      CurGroup = InfoGroup;
-    }
-
-    // Insert range info into corresponding Visibility ResourceRange
-    ResourceRange &VisRange = Ranges[llvm::to_underlying(Info.Visibility)];
-    if (std::optional<const RangeInfo *> Overlapping = VisRange.insert(Info))
-      Overlaps.push_back(OverlappingRanges(&Info, Overlapping.value()));
-
-    // Check for overlap in all overlapping Visibility ResourceRanges
-    //
-    // If the range that we are inserting has ShaderVisiblity::All it needs to
-    // check for an overlap in all other visibility types as well.
-    // Otherwise, the range that is inserted needs to check that it does not
-    // overlap with ShaderVisibility::All.
-    //
-    // OverlapRanges will be an ArrayRef to all non-all visibility
-    // ResourceRanges in the former case and it will be an ArrayRef to just the
-    // all visiblity ResourceRange in the latter case.
-    ArrayRef<ResourceRange> OverlapRanges =
-        Info.Visibility == llvm::dxbc::ShaderVisibility::All
-            ? ArrayRef<ResourceRange>{Ranges}.drop_front()
-            : ArrayRef<ResourceRange>{Ranges}.take_front();
-
-    for (const ResourceRange &Range : OverlapRanges)
-      if (std::optional<const RangeInfo *> Overlapping =
-              Range.getOverlapping(Info))
-        Overlaps.push_back(OverlappingRanges(&Info, Overlapping.value()));
-  }
-
-  return Overlaps;
-}
-
 } // namespace rootsig
 } // namespace hlsl
 } // namespace llvm
diff --git a/llvm/unittests/Frontend/CMakeLists.txt b/llvm/unittests/Frontend/CMakeLists.txt
index cd7abb7..836a844 100644
--- a/llvm/unittests/Frontend/CMakeLists.txt
+++ b/llvm/unittests/Frontend/CMakeLists.txt
@@ -14,7 +14,6 @@ set(LLVM_LINK_COMPONENTS
 add_llvm_unittest(LLVMFrontendTests
   HLSLBindingTest.cpp
   HLSLRootSignatureDumpTest.cpp
-  HLSLRootSignatureRangesTest.cpp
   OpenACCTest.cpp
   OpenMPContextTest.cpp
   OpenMPIRBuilderTest.cpp
diff --git a/llvm/unittests/Frontend/HLSLRootSignatureRangesTest.cpp b/llvm/unittests/Frontend/HLSLRootSignatureRangesTest.cpp
deleted file mode 100644
index be3f51e..0000000
--- a/llvm/unittests/Frontend/HLSLRootSignatureRangesTest.cpp
+++ /dev/null
@@ -1,177 +0,0 @@
-//===------ HLSLRootSignatureRangeTest.cpp - RootSignature Range tests ----===//
-//
-// 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
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Frontend/HLSL/RootSignatureValidations.h"
-#include "gtest/gtest.h"
-
-using namespace llvm::hlsl::rootsig;
-
-namespace {
-
-TEST(HLSLRootSignatureTest, NoOverlappingInsertTests) {
-  // Ensures that there is never a reported overlap
-  ResourceRange::MapT::Allocator Allocator;
-  ResourceRange Range(Allocator);
-
-  RangeInfo A;
-  A.LowerBound = 0;
-  A.UpperBound = 3;
-  EXPECT_EQ(Range.insert(A), std::nullopt);
-
-  RangeInfo B;
-  B.LowerBound = 4;
-  B.UpperBound = 7;
-  EXPECT_EQ(Range.insert(B), std::nullopt);
-
-  RangeInfo C;
-  C.LowerBound = 10;
-  C.UpperBound = RangeInfo::Unbounded;
-  EXPECT_EQ(Range.insert(C), std::nullopt);
-
-  // A = [0;3]
-  EXPECT_EQ(Range.lookup(0), &A);
-  EXPECT_EQ(Range.lookup(2), &A);
-  EXPECT_EQ(Range.lookup(3), &A);
-
-  // B = [4;7]
-  EXPECT_EQ(Range.lookup(4), &B);
-  EXPECT_EQ(Range.lookup(5), &B);
-  EXPECT_EQ(Range.lookup(7), &B);
-
-  EXPECT_EQ(Range.lookup(8), nullptr);
-  EXPECT_EQ(Range.lookup(9), nullptr);
-
-  // C = [10;unbounded]
-  EXPECT_EQ(Range.lookup(10), &C);
-  EXPECT_EQ(Range.lookup(42), &C);
-  EXPECT_EQ(Range.lookup(98237423), &C);
-  EXPECT_EQ(Range.lookup(RangeInfo::Unbounded), &C);
-}
-
-TEST(HLSLRootSignatureTest, SingleOverlappingInsertTests) {
-  // Ensures that we correctly report an overlap when we insert a range that
-  // overlaps with one other range but does not cover (replace) it
-  ResourceRange::MapT::Allocator Allocator;
-  ResourceRange Range(Allocator);
-
-  RangeInfo A;
-  A.LowerBound = 1;
-  A.UpperBound = 5;
-  EXPECT_EQ(Range.insert(A), std::nullopt);
-
-  RangeInfo B;
-  B.LowerBound = 0;
-  B.UpperBound = 2;
-  EXPECT_EQ(Range.insert(B).value(), &A);
-
-  RangeInfo C;
-  C.LowerBound = 4;
-  C.UpperBound = RangeInfo::Unbounded;
-  EXPECT_EQ(Range.insert(C).value(), &A);
-
-  // A = [1;5]
-  EXPECT_EQ(Range.lookup(1), &A);
-  EXPECT_EQ(Range.lookup(2), &A);
-  EXPECT_EQ(Range.lookup(3), &A);
-  EXPECT_EQ(Range.lookup(4), &A);
-  EXPECT_EQ(Range.lookup(5), &A);
-
-  // B = [0;0]
-  EXPECT_EQ(Range.lookup(0), &B);
-
-  // C = [6; unbounded]
-  EXPECT_EQ(Range.lookup(6), &C);
-  EXPECT_EQ(Range.lookup(RangeInfo::Unbounded), &C);
-}
-
-TEST(HLSLRootSignatureTest, MultipleOverlappingInsertTests) {
-  // Ensures that we correctly report an overlap when inserted range
-  // overlaps more than one range and it does not cover (replace) either
-  // range. In this case it will just fill in the interval between the two
-  ResourceRange::MapT::Allocator Allocator;
-  ResourceRange Range(Allocator);
-
-  RangeInfo A;
-  A.LowerBound = 0;
-  A.UpperBound = 2;
-  EXPECT_EQ(Range.insert(A), std::nullopt);
-
-  RangeInfo B;
-  B.LowerBound = 4;
-  B.UpperBound = 6;
-  EXPECT_EQ(Range.insert(B), std::nullopt);
-
-  RangeInfo C;
-  C.LowerBound = 1;
-  C.UpperBound = 5;
-  EXPECT_EQ(Range.insert(C).value(), &A);
-
-  // A = [0;2]
-  EXPECT_EQ(Range.lookup(0), &A);
-  EXPECT_EQ(Range.lookup(1), &A);
-  EXPECT_EQ(Range.lookup(2), &A);
-
-  // B = [4;6]
-  EXPECT_EQ(Range.lookup(4), &B);
-  EXPECT_EQ(Range.lookup(5), &B);
-  EXPECT_EQ(Range.lookup(6), &B);
-
-  // C = [3;3]
-  EXPECT_EQ(Range.lookup(3), &C);
-}
-
-TEST(HLSLRootSignatureTest, CoverInsertTests) {
-  // Ensures that we correctly report an overlap when inserted range
-  // covers one or more ranges
-  ResourceRange::MapT::Allocator Allocator;
-  ResourceRange Range(Allocator);
-
-  RangeInfo A;
-  A.LowerBound = 0;
-  A.UpperBound = 2;
-  EXPECT_EQ(Range.insert(A), std::nullopt);
-
-  RangeInfo B;
-  B.LowerBound = 4;
-  B.UpperBound = 5;
-  EXPECT_EQ(Range.insert(B), std::nullopt);
-
-  // Covers B
-  RangeInfo C;
-  C.LowerBound = 4;
-  C.UpperBound = 6;
-  EXPECT_EQ(Range.insert(C).value(), &B);
-
-  // A = [0;2]
-  // C = [4;6] <- covers reference to B
-  EXPECT_EQ(Range.lookup(0), &A);
-  EXPECT_EQ(Range.lookup(1), &A);
-  EXPECT_EQ(Range.lookup(2), &A);
-  EXPECT_EQ(Range.lookup(3), nullptr);
-  EXPECT_EQ(Range.lookup(4), &C);
-  EXPECT_EQ(Range.lookup(5), &C);
-  EXPECT_EQ(Range.lookup(6), &C);
-
-  // Covers all other ranges
-  RangeInfo D;
-  D.LowerBound = 0;
-  D.UpperBound = 7;
-  EXPECT_EQ(Range.insert(D).value(), &A);
-
-  // D = [0;7] <- Covers reference to A and C
-  EXPECT_EQ(Range.lookup(0), &D);
-  EXPECT_EQ(Range.lookup(1), &D);
-  EXPECT_EQ(Range.lookup(2), &D);
-  EXPECT_EQ(Range.lookup(3), &D);
-  EXPECT_EQ(Range.lookup(4), &D);
-  EXPECT_EQ(Range.lookup(5), &D);
-  EXPECT_EQ(Range.lookup(6), &D);
-  EXPECT_EQ(Range.lookup(7), &D);
-}
-
-} // namespace