1//===- HLSLBinding.cpp - Representation for resource bindings in HLSL -----===//
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/Frontend/HLSL/HLSLBinding.h"
10#include "llvm/ADT/STLExtras.h"
11
12using namespace llvm;
13using namespace hlsl;
14
15std::optional<uint32_t>
16BindingInfo::findAvailableBinding(dxil::ResourceClass RC, uint32_t Space,
17 int32_t Size) {
18 BindingSpaces &BS = getBindingSpaces(RC);
19 RegisterSpace &RS = BS.getOrInsertSpace(Space);
20 return RS.findAvailableBinding(Size);
21}
22
23BindingInfo::RegisterSpace &
24BindingInfo::BindingSpaces::getOrInsertSpace(uint32_t Space) {
25 for (auto It = Spaces.begin(), End = Spaces.end(); It != End; ++It) {
26 if (It->Space == Space)
27 return *It;
28 if (It->Space < Space)
29 continue;
30 return *Spaces.insert(I: It, Elt: Space);
31 }
32 return Spaces.emplace_back(Args&: Space);
33}
34
35std::optional<uint32_t>
36BindingInfo::RegisterSpace::findAvailableBinding(int32_t Size) {
37 assert((Size == -1 || Size > 0) && "invalid size");
38
39 if (FreeRanges.empty())
40 return std::nullopt;
41
42 // unbounded array
43 if (Size == -1) {
44 BindingRange &Last = FreeRanges.back();
45 if (Last.UpperBound != ~0u)
46 // this space is already occupied by an unbounded array
47 return std::nullopt;
48 uint32_t RegSlot = Last.LowerBound;
49 FreeRanges.pop_back();
50 return RegSlot;
51 }
52
53 // single resource or fixed-size array
54 for (BindingRange &R : FreeRanges) {
55 // compare the size as uint64_t to prevent overflow for range (0, ~0u)
56 if ((uint64_t)R.UpperBound - R.LowerBound + 1 < (uint64_t)Size)
57 continue;
58 uint32_t RegSlot = R.LowerBound;
59 // This might create a range where (LowerBound == UpperBound + 1). When
60 // that happens, the next time this function is called the range will
61 // skipped over by the check above (at this point Size is always > 0).
62 R.LowerBound += Size;
63 return RegSlot;
64 }
65
66 return std::nullopt;
67}
68
69BindingInfo BindingInfoBuilder::calculateBindingInfo(
70 llvm::function_ref<void(const BindingInfoBuilder &Builder,
71 const Binding &Overlapping)>
72 ReportOverlap) {
73 // sort all the collected bindings
74 llvm::stable_sort(Range&: Bindings);
75
76 // remove duplicates
77 Binding *NewEnd = llvm::unique(R&: Bindings);
78 if (NewEnd != Bindings.end())
79 Bindings.erase(CS: NewEnd, CE: Bindings.end());
80
81 BindingInfo Info;
82
83 // Go over the sorted bindings and build up lists of free register ranges
84 // for each binding type and used spaces. Bindings are sorted by resource
85 // class, space, and lower bound register slot.
86 BindingInfo::BindingSpaces *BS =
87 &Info.getBindingSpaces(RC: dxil::ResourceClass::SRV);
88 for (const Binding &B : Bindings) {
89 if (BS->RC != B.RC)
90 // move to the next resource class spaces
91 BS = &Info.getBindingSpaces(RC: B.RC);
92
93 BindingInfo::RegisterSpace *S = BS->Spaces.empty()
94 ? &BS->Spaces.emplace_back(Args: B.Space)
95 : &BS->Spaces.back();
96 assert(S->Space <= B.Space && "bindings not sorted correctly?");
97 if (B.Space != S->Space)
98 // add new space
99 S = &BS->Spaces.emplace_back(Args: B.Space);
100
101 // The space is full - there are no free slots left, or the rest of the
102 // slots are taken by an unbounded array. Report the overlapping to the
103 // caller.
104 if (S->FreeRanges.empty() || S->FreeRanges.back().UpperBound < ~0u) {
105 ReportOverlap(*this, B);
106 continue;
107 }
108 // adjust the last free range lower bound, split it in two, or remove it
109 BindingInfo::BindingRange &LastFreeRange = S->FreeRanges.back();
110 if (LastFreeRange.LowerBound == B.LowerBound) {
111 if (B.UpperBound < ~0u)
112 LastFreeRange.LowerBound = B.UpperBound + 1;
113 else
114 S->FreeRanges.pop_back();
115 } else if (LastFreeRange.LowerBound < B.LowerBound) {
116 LastFreeRange.UpperBound = B.LowerBound - 1;
117 if (B.UpperBound < ~0u)
118 S->FreeRanges.emplace_back(Args: B.UpperBound + 1, Args: ~0u);
119 } else {
120 // We don't have room here. Report the overlapping binding to the caller
121 // and mark any extra space this binding would use as unavailable.
122 ReportOverlap(*this, B);
123 if (B.UpperBound < ~0u)
124 LastFreeRange.LowerBound =
125 std::max(a: LastFreeRange.LowerBound, b: B.UpperBound + 1);
126 else
127 S->FreeRanges.pop_back();
128 }
129 }
130
131 return Info;
132}
133
134const Binding &
135BindingInfoBuilder::findOverlapping(const Binding &ReportedBinding) const {
136 for (const Binding &Other : Bindings)
137 if (ReportedBinding.LowerBound <= Other.UpperBound &&
138 Other.LowerBound <= ReportedBinding.UpperBound)
139 return Other;
140
141 llvm_unreachable("Searching for overlap for binding that does not overlap");
142}
143