| 1 | //===- SemanticSignaturePacking.cpp - HLSL signature packing helpers -----===// |
| 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 | /// \file This file implements helpers for packing HLSL semantic signatures. |
| 10 | /// |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "llvm/Frontend/HLSL/SemanticSignaturePacking.h" |
| 14 | #include "llvm/ADT/STLExtras.h" |
| 15 | #include "llvm/ADT/Sequence.h" |
| 16 | #include "llvm/ADT/SmallVector.h" |
| 17 | #include "llvm/ADT/bit.h" |
| 18 | #include <algorithm> |
| 19 | #include <array> |
| 20 | #include <cassert> |
| 21 | #include <cstdint> |
| 22 | #include <limits> |
| 23 | #include <optional> |
| 24 | |
| 25 | using namespace llvm; |
| 26 | using namespace llvm::hlsl; |
| 27 | |
| 28 | char SignaturePackingError::ID; |
| 29 | |
| 30 | namespace { |
| 31 | |
| 32 | // The range of rows covered by a dynamically indexable element. Only an |
| 33 | // element that covers multiple rows is dynamically indexable, so a single-row |
| 34 | // element has an empty range. |
| 35 | struct IndexedRowRange { |
| 36 | uint8_t Begin = 0; |
| 37 | uint8_t End = 0; |
| 38 | |
| 39 | static IndexedRowRange of(unsigned StartRow, unsigned RowCount) { |
| 40 | if (RowCount < 2) |
| 41 | return {}; |
| 42 | return {.Begin: static_cast<uint8_t>(StartRow), |
| 43 | .End: static_cast<uint8_t>(StartRow + RowCount)}; |
| 44 | } |
| 45 | |
| 46 | bool isEmpty() const { return Begin == End; } |
| 47 | |
| 48 | // An empty range is contained by every range. |
| 49 | bool contains(IndexedRowRange Other) const { |
| 50 | return Other.isEmpty() || (Begin <= Other.Begin && Other.End <= End); |
| 51 | } |
| 52 | |
| 53 | IndexedRowRange unionWith(IndexedRowRange Other) const { |
| 54 | if (isEmpty()) |
| 55 | return Other; |
| 56 | if (Other.isEmpty()) |
| 57 | return *this; |
| 58 | return {.Begin: std::min(a: Begin, b: Other.Begin), .End: std::max(a: End, b: Other.End)}; |
| 59 | } |
| 60 | |
| 61 | bool operator==(IndexedRowRange Other) const { |
| 62 | return Begin == Other.Begin && End == Other.End; |
| 63 | } |
| 64 | }; |
| 65 | |
| 66 | static_assert(SemanticInterpretation::Arbitrary < SemanticInterpretation::SV && |
| 67 | SemanticInterpretation::SV < SemanticInterpretation::SGV && |
| 68 | SemanticInterpretation::SGV < |
| 69 | SemanticInterpretation::ClipCull && |
| 70 | SemanticInterpretation::ClipCull < |
| 71 | SemanticInterpretation::TessFactor, |
| 72 | "semantic interpretations must be in component packing order" ); |
| 73 | |
| 74 | struct SignatureRow { |
| 75 | uint8_t OccupiedColumns = 0; |
| 76 | IndexedRowRange IndexedRange; |
| 77 | bool IndexedRangeFixed = false; |
| 78 | unsigned ComponentWidth = 0; |
| 79 | dxbc::PSV::InterpolationMode InterpMode = |
| 80 | dxbc::PSV::InterpolationMode::Undefined; |
| 81 | SemanticInterpretation RightmostInterpretation = |
| 82 | SemanticInterpretation::Arbitrary; |
| 83 | }; |
| 84 | |
| 85 | using SignatureRows = std::array<SignatureRow, MaxSignatureRows>; |
| 86 | |
| 87 | struct ElementPlacement { |
| 88 | unsigned Rows; |
| 89 | unsigned Cols; |
| 90 | unsigned ComponentWidth; |
| 91 | dxbc::PSV::InterpolationMode InterpMode; |
| 92 | SemanticInterpretation Interpretation; |
| 93 | }; |
| 94 | |
| 95 | struct ElementLocation { |
| 96 | uint32_t Row = UnallocatedRow; |
| 97 | uint8_t Col = UnallocatedCol; |
| 98 | }; |
| 99 | |
| 100 | struct OptimizedClipCullElement { |
| 101 | unsigned Index; |
| 102 | ElementPlacement Placement; |
| 103 | ElementLocation Location; |
| 104 | }; |
| 105 | |
| 106 | // Clip/cull elements are first packed into an independent two-row grid. Each |
| 107 | // row used in that grid maps to a whole reserved row in the signature. |
| 108 | struct ClipCullState { |
| 109 | std::array<SignatureRow, MaxClipCullRows> Rows; |
| 110 | std::array<unsigned, MaxClipCullRows> SignatureRows = {UnallocatedRow, |
| 111 | UnallocatedRow}; |
| 112 | unsigned RowsUsed = 0; |
| 113 | }; |
| 114 | |
| 115 | enum class PackingGroup : unsigned { |
| 116 | FullRegister, |
| 117 | IndexedTessFactor, |
| 118 | Arbitrary, |
| 119 | SystemValue, |
| 120 | ClipCull, |
| 121 | SystemGenerated, |
| 122 | NotAllocated, |
| 123 | }; |
| 124 | |
| 125 | } // namespace |
| 126 | |
| 127 | static uint8_t getStartColumn(uint8_t ColumnMask) { |
| 128 | assert(ColumnMask != 0 && "expected at least one occupied column" ); |
| 129 | return countr_zero(Val: ColumnMask); |
| 130 | } |
| 131 | |
| 132 | static PackingGroup |
| 133 | getOptimizedPackingGroup(const SemanticSignatureElement &Element, |
| 134 | Triple::EnvironmentType ShaderStage, IOType IOTy) { |
| 135 | const SemanticInterpretation Interpretation = |
| 136 | getInterpretationKind(SemanticKind: Element.SemanticKind, ShaderStage, IOTy); |
| 137 | assert((Interpretation != SemanticInterpretation::Invalid && |
| 138 | Interpretation != SemanticInterpretation::Target) && |
| 139 | "unexpected semantic interpretation for optimized packing, " |
| 140 | "should have been diagnosed by Sema" ); |
| 141 | |
| 142 | if (Element.Cols == MaxSignatureCols && |
| 143 | (Interpretation == SemanticInterpretation::Arbitrary || |
| 144 | Interpretation == SemanticInterpretation::SV)) |
| 145 | return PackingGroup::FullRegister; |
| 146 | |
| 147 | if (Interpretation == SemanticInterpretation::TessFactor && Element.Rows > 1) |
| 148 | return PackingGroup::IndexedTessFactor; |
| 149 | |
| 150 | switch (Interpretation) { |
| 151 | case SemanticInterpretation::Arbitrary: |
| 152 | return PackingGroup::Arbitrary; |
| 153 | case SemanticInterpretation::SV: |
| 154 | case SemanticInterpretation::TessFactor: |
| 155 | return PackingGroup::SystemValue; |
| 156 | case SemanticInterpretation::ClipCull: |
| 157 | return PackingGroup::ClipCull; |
| 158 | case SemanticInterpretation::SGV: |
| 159 | return PackingGroup::SystemGenerated; |
| 160 | case SemanticInterpretation::NotAllocated: |
| 161 | case SemanticInterpretation::NotPacked: |
| 162 | return PackingGroup::NotAllocated; |
| 163 | case SemanticInterpretation::Invalid: |
| 164 | case SemanticInterpretation::Target: |
| 165 | break; |
| 166 | } |
| 167 | llvm_unreachable("unexpected semantic interpretation for optimized packing" ); |
| 168 | } |
| 169 | |
| 170 | static unsigned getComponentWidth(dxil::ElementType ComponentType, |
| 171 | bool UseNative16BitTypes) { |
| 172 | assert(ComponentType != dxil::ElementType::I64 && |
| 173 | ComponentType != dxil::ElementType::U64 && |
| 174 | ComponentType != dxil::ElementType::F64 && |
| 175 | ComponentType != dxil::ElementType::SNormF64 && |
| 176 | ComponentType != dxil::ElementType::UNormF64 && |
| 177 | "64-bit types cannot be used in a signature" ); |
| 178 | |
| 179 | switch (ComponentType) { |
| 180 | case dxil::ElementType::F16: |
| 181 | case dxil::ElementType::I16: |
| 182 | case dxil::ElementType::U16: |
| 183 | case dxil::ElementType::SNormF16: |
| 184 | case dxil::ElementType::UNormF16: |
| 185 | // Without native 16-bit types these are min-precision types that occupy a |
| 186 | // whole 32-bit component. |
| 187 | return UseNative16BitTypes ? 16 : 32; |
| 188 | default: |
| 189 | // A boolean is loaded and stored as a 32-bit value. |
| 190 | return 32; |
| 191 | } |
| 192 | } |
| 193 | |
| 194 | static ElementPlacement |
| 195 | getElementPlacement(const SemanticSignatureElement &Element, |
| 196 | SemanticInterpretation Interpretation, |
| 197 | bool UseNative16BitTypes) { |
| 198 | // Only indexed tessellation factors need the reserved last column. |
| 199 | if (Interpretation == SemanticInterpretation::TessFactor && Element.Rows == 1) |
| 200 | Interpretation = SemanticInterpretation::SV; |
| 201 | return {.Rows: Element.Rows, .Cols: Element.Cols, |
| 202 | .ComponentWidth: getComponentWidth(ComponentType: Element.CompType, UseNative16BitTypes), |
| 203 | .InterpMode: Element.InterpMode, .Interpretation: Interpretation}; |
| 204 | } |
| 205 | |
| 206 | static SemanticInterpretation |
| 207 | getComponentOrder(SemanticInterpretation Interpretation) { |
| 208 | // Clip/cull values have system-value component ordering, but may be indexed. |
| 209 | return Interpretation == SemanticInterpretation::ClipCull |
| 210 | ? SemanticInterpretation::SV |
| 211 | : Interpretation; |
| 212 | } |
| 213 | |
| 214 | // Returns whether Placement may be co-packed into a Row that it covers, where |
| 215 | // IndexedRange is the range of rows that it is dynamically indexed over. |
| 216 | static bool canCoPack(const SignatureRow &Row, |
| 217 | const ElementPlacement &Placement, |
| 218 | IndexedRowRange IndexedRange) { |
| 219 | const bool IsSystemValue = |
| 220 | Placement.Interpretation == SemanticInterpretation::SV || |
| 221 | Placement.Interpretation == SemanticInterpretation::SGV; |
| 222 | |
| 223 | // A system value is never dynamically indexable, so it cannot be placed in a |
| 224 | // row that is. |
| 225 | if (IsSystemValue && !Row.IndexedRange.isEmpty()) |
| 226 | return false; |
| 227 | |
| 228 | // A row whose indexed range is fixed only accepts elements that are indexed |
| 229 | // within that range. |
| 230 | if (Row.IndexedRangeFixed && !Row.IndexedRange.contains(Other: IndexedRange)) |
| 231 | return false; |
| 232 | |
| 233 | // A tess factor fixes the indexed range of the rows it is reserved in, so it |
| 234 | // may only extend the range that those rows already have. |
| 235 | if (Placement.Interpretation == SemanticInterpretation::TessFactor && |
| 236 | !IndexedRange.contains(Other: Row.IndexedRange)) |
| 237 | return false; |
| 238 | |
| 239 | if (Row.OccupiedColumns && Row.ComponentWidth != Placement.ComponentWidth) |
| 240 | return false; |
| 241 | if (Row.InterpMode != dxbc::PSV::InterpolationMode::Undefined && |
| 242 | Row.InterpMode != Placement.InterpMode) |
| 243 | return false; |
| 244 | // Do not append an earlier semantic category after a later one in a row. |
| 245 | // Indexed tess factors are reserved in the last column, so arbitrary values |
| 246 | // may still fill the columns to their left without violating that ordering. |
| 247 | if (Row.OccupiedColumns && |
| 248 | getComponentOrder(Interpretation: Placement.Interpretation) < |
| 249 | getComponentOrder(Interpretation: Row.RightmostInterpretation) && |
| 250 | !(Placement.Interpretation == SemanticInterpretation::Arbitrary && |
| 251 | Row.RightmostInterpretation == SemanticInterpretation::TessFactor)) |
| 252 | return false; |
| 253 | return true; |
| 254 | } |
| 255 | |
| 256 | // Returns the columns that Placement would occupy if it was placed at StartRow, |
| 257 | // or nullopt if it cannot be placed there. |
| 258 | static std::optional<uint8_t> canPlaceAt(ArrayRef<SignatureRow> Rows, |
| 259 | unsigned StartRow, |
| 260 | const ElementPlacement &Placement) { |
| 261 | if (StartRow >= Rows.size() || Placement.Rows > Rows.size() - StartRow) |
| 262 | return std::nullopt; |
| 263 | |
| 264 | const IndexedRowRange IndexedRange = |
| 265 | IndexedRowRange::of(StartRow, RowCount: Placement.Rows); |
| 266 | uint8_t OccupiedColumns = 0; |
| 267 | for (unsigned ElementRow = 0; ElementRow != Placement.Rows; ++ElementRow) { |
| 268 | const SignatureRow &Row = Rows[StartRow + ElementRow]; |
| 269 | if (!canCoPack(Row, Placement, IndexedRange)) |
| 270 | return std::nullopt; |
| 271 | OccupiedColumns |= Row.OccupiedColumns; |
| 272 | } |
| 273 | |
| 274 | // An indexed tess factor is reserved in the last column so that other |
| 275 | // elements can still be co-packed into the rows that it covers. |
| 276 | if (Placement.Interpretation == SemanticInterpretation::TessFactor) { |
| 277 | constexpr uint8_t LastColumn = 1U << (MaxSignatureCols - 1); |
| 278 | if (Placement.Cols != 1 || (OccupiedColumns & LastColumn)) |
| 279 | return std::nullopt; |
| 280 | return LastColumn; |
| 281 | } |
| 282 | |
| 283 | for (unsigned StartCol = 0; StartCol + Placement.Cols <= MaxSignatureCols; |
| 284 | ++StartCol) { |
| 285 | const uint8_t ColumnMask = static_cast<uint8_t>( |
| 286 | ((1U << Placement.Cols) - 1U) << static_cast<unsigned>(StartCol)); |
| 287 | if (!(OccupiedColumns & ColumnMask)) |
| 288 | return ColumnMask; |
| 289 | } |
| 290 | return std::nullopt; |
| 291 | } |
| 292 | |
| 293 | static void placeRowsAt(MutableArrayRef<SignatureRow> Rows, unsigned StartRow, |
| 294 | const ElementPlacement &Placement, uint8_t ColumnMask) { |
| 295 | const IndexedRowRange IndexedRange = |
| 296 | IndexedRowRange::of(StartRow, RowCount: Placement.Rows); |
| 297 | for (unsigned ElementRow = 0; ElementRow != Placement.Rows; ++ElementRow) { |
| 298 | SignatureRow &Row = Rows[StartRow + ElementRow]; |
| 299 | assert(!(Row.OccupiedColumns & ColumnMask) && |
| 300 | "cannot overlap signature elements" ); |
| 301 | const uint8_t PreviousOccupiedColumns = Row.OccupiedColumns; |
| 302 | if (!PreviousOccupiedColumns) |
| 303 | Row.ComponentWidth = Placement.ComponentWidth; |
| 304 | Row.OccupiedColumns |= ColumnMask; |
| 305 | if (Row.InterpMode == dxbc::PSV::InterpolationMode::Undefined) |
| 306 | Row.InterpMode = Placement.InterpMode; |
| 307 | // Non-overlapping masks compare according to their rightmost set bit. |
| 308 | if (!PreviousOccupiedColumns || ColumnMask > PreviousOccupiedColumns) |
| 309 | Row.RightmostInterpretation = Placement.Interpretation; |
| 310 | |
| 311 | Row.IndexedRange = Row.IndexedRange.unionWith(Other: IndexedRange); |
| 312 | if (Placement.Interpretation == SemanticInterpretation::SV || |
| 313 | Placement.Interpretation == SemanticInterpretation::SGV || |
| 314 | Placement.Interpretation == SemanticInterpretation::TessFactor) { |
| 315 | assert(Row.IndexedRange == IndexedRange && "incompatible index range" ); |
| 316 | Row.IndexedRangeFixed = true; |
| 317 | } |
| 318 | } |
| 319 | } |
| 320 | |
| 321 | static void placeAt(MutableArrayRef<SignatureRow> Rows, unsigned StartRow, |
| 322 | const ElementPlacement &Placement, uint8_t ColumnMask, |
| 323 | ElementLocation &Location) { |
| 324 | placeRowsAt(Rows, StartRow, Placement, ColumnMask); |
| 325 | Location.Row = StartRow; |
| 326 | Location.Col = getStartColumn(ColumnMask); |
| 327 | } |
| 328 | |
| 329 | static bool prefixPackElement(ElementLocation &Location, |
| 330 | MutableArrayRef<SignatureRow> Rows, |
| 331 | const ElementPlacement &Placement) { |
| 332 | for (unsigned StartRow = 0; StartRow != Rows.size(); ++StartRow) { |
| 333 | std::optional<uint8_t> ColumnMask = canPlaceAt(Rows, StartRow, Placement); |
| 334 | if (!ColumnMask) |
| 335 | continue; |
| 336 | placeAt(Rows, StartRow, Placement, ColumnMask: *ColumnMask, Location); |
| 337 | return true; |
| 338 | } |
| 339 | return false; |
| 340 | } |
| 341 | |
| 342 | // A clip/cull grid row is backed by a whole reserved signature row. |
| 343 | static ElementPlacement |
| 344 | getClipCullReservation(const ElementPlacement &Placement, unsigned RowCount) { |
| 345 | ElementPlacement Reservation = Placement; |
| 346 | Reservation.Rows = RowCount; |
| 347 | Reservation.Cols = MaxSignatureCols; |
| 348 | return Reservation; |
| 349 | } |
| 350 | |
| 351 | static bool reserveClipCullRows(MutableArrayRef<SignatureRow> Rows, |
| 352 | unsigned StartRow, |
| 353 | const ElementPlacement &Reservation) { |
| 354 | std::optional<uint8_t> ColumnMask = canPlaceAt(Rows, StartRow, Placement: Reservation); |
| 355 | if (!ColumnMask) |
| 356 | return false; |
| 357 | placeRowsAt(Rows, StartRow, Placement: Reservation, ColumnMask: *ColumnMask); |
| 358 | return true; |
| 359 | } |
| 360 | |
| 361 | static std::optional<unsigned> |
| 362 | reserveNextClipCullRows(MutableArrayRef<SignatureRow> Rows, |
| 363 | const ElementPlacement &Reservation) { |
| 364 | for (unsigned StartRow = 0; StartRow != Rows.size(); ++StartRow) |
| 365 | if (reserveClipCullRows(Rows, StartRow, Reservation)) |
| 366 | return StartRow; |
| 367 | return std::nullopt; |
| 368 | } |
| 369 | |
| 370 | // Reserves the whole signature rows that back the clip/cull grid rows that the |
| 371 | // element is packed into. Existing rows cannot be moved without breaking |
| 372 | // prefix stability, so an indexed element requires them to be adjacent. |
| 373 | static std::optional<SignaturePackingError::ErrorKind> |
| 374 | reserveClipCullSignatureRows(MutableArrayRef<SignatureRow> SignatureRows, |
| 375 | ClipCullState &State, |
| 376 | const ElementPlacement &Placement, |
| 377 | unsigned NewRowsUsed) { |
| 378 | if (Placement.Rows == 1) { |
| 379 | const ElementPlacement Reservation = getClipCullReservation(Placement, RowCount: 1); |
| 380 | for (unsigned Row = State.RowsUsed; Row < NewRowsUsed; ++Row) { |
| 381 | std::optional<unsigned> StartRow = |
| 382 | reserveNextClipCullRows(Rows: SignatureRows, Reservation); |
| 383 | if (!StartRow) |
| 384 | return SignaturePackingError::SignatureOverflow; |
| 385 | State.SignatureRows[Row] = *StartRow; |
| 386 | } |
| 387 | return std::nullopt; |
| 388 | } |
| 389 | |
| 390 | if (State.RowsUsed == 0) { |
| 391 | std::optional<unsigned> StartRow = reserveNextClipCullRows( |
| 392 | Rows: SignatureRows, Reservation: getClipCullReservation(Placement, RowCount: MaxClipCullRows)); |
| 393 | if (!StartRow) |
| 394 | return SignaturePackingError::SignatureOverflow; |
| 395 | State.SignatureRows[0] = *StartRow; |
| 396 | State.SignatureRows[1] = *StartRow + 1; |
| 397 | return std::nullopt; |
| 398 | } |
| 399 | |
| 400 | if (State.RowsUsed == 1) { |
| 401 | const unsigned StartRow = State.SignatureRows[0] + 1; |
| 402 | if (StartRow >= SignatureRows.size()) |
| 403 | return SignaturePackingError::SignatureOverflow; |
| 404 | if (!reserveClipCullRows(Rows: SignatureRows, StartRow, |
| 405 | Reservation: getClipCullReservation(Placement, RowCount: 1))) |
| 406 | return SignaturePackingError::ClipCullNotAdjacent; |
| 407 | State.SignatureRows[1] = StartRow; |
| 408 | return std::nullopt; |
| 409 | } |
| 410 | |
| 411 | if (State.SignatureRows[0] + 1 != State.SignatureRows[1]) |
| 412 | return SignaturePackingError::ClipCullNotAdjacent; |
| 413 | return std::nullopt; |
| 414 | } |
| 415 | |
| 416 | static std::optional<SignaturePackingError::ErrorKind> |
| 417 | packClipCullElement(ElementLocation &Location, |
| 418 | MutableArrayRef<SignatureRow> SignatureRows, |
| 419 | ClipCullState &State, const ElementPlacement &Placement) { |
| 420 | std::optional<uint8_t> ColumnMask; |
| 421 | unsigned ClipCullStartRow = 0; |
| 422 | while (ClipCullStartRow + Placement.Rows <= MaxClipCullRows) { |
| 423 | ColumnMask = canPlaceAt(Rows: State.Rows, StartRow: ClipCullStartRow, Placement); |
| 424 | if (ColumnMask) |
| 425 | break; |
| 426 | ++ClipCullStartRow; |
| 427 | } |
| 428 | if (!ColumnMask) |
| 429 | return SignaturePackingError::ClipCullOverflow; |
| 430 | |
| 431 | const unsigned NewRowsUsed = ClipCullStartRow + Placement.Rows; |
| 432 | if (std::optional<SignaturePackingError::ErrorKind> Kind = |
| 433 | reserveClipCullSignatureRows(SignatureRows, State, Placement, |
| 434 | NewRowsUsed)) |
| 435 | return Kind; |
| 436 | |
| 437 | placeRowsAt(Rows: State.Rows, StartRow: ClipCullStartRow, Placement, ColumnMask: *ColumnMask); |
| 438 | State.RowsUsed = std::max(a: State.RowsUsed, b: NewRowsUsed); |
| 439 | Location.Row = State.SignatureRows[ClipCullStartRow]; |
| 440 | Location.Col = getStartColumn(ColumnMask: *ColumnMask); |
| 441 | return std::nullopt; |
| 442 | } |
| 443 | |
| 444 | // Work only on scratch rows and locations. The caller commits the entire |
| 445 | // clip/cull phase after every stream succeeds. |
| 446 | static Error |
| 447 | packOptimizedClipCullStream(MutableArrayRef<OptimizedClipCullElement> Elements, |
| 448 | MutableArrayRef<SignatureRow> Rows) { |
| 449 | if (Elements.empty()) |
| 450 | return Error::success(); |
| 451 | |
| 452 | std::array<SignatureRow, MaxClipCullRows> LocalRows; |
| 453 | bool HasIndexed = false; |
| 454 | for (auto &Element : Elements) { |
| 455 | if (!prefixPackElement(Location&: Element.Location, Rows: LocalRows, Placement: Element.Placement)) |
| 456 | return make_error<SignaturePackingError>( |
| 457 | Args: SignaturePackingError::ClipCullOverflow, Args&: Element.Index); |
| 458 | HasIndexed |= Element.Placement.Rows > 1; |
| 459 | } |
| 460 | |
| 461 | if (!HasIndexed) { |
| 462 | // Keep single-row elements grouped into at most two rows, rather than |
| 463 | // scattering individual distances across unrelated signature gaps. |
| 464 | std::array<ElementLocation, MaxClipCullRows> Destinations; |
| 465 | for (unsigned Row = 0; Row != MaxClipCullRows; ++Row) { |
| 466 | auto First = llvm::find_if(Range&: Elements, P: [Row](const auto &Element) { |
| 467 | return Element.Location.Row == Row; |
| 468 | }); |
| 469 | if (First == Elements.end()) |
| 470 | continue; |
| 471 | ElementPlacement Bundle = First->Placement; |
| 472 | Bundle.Cols = popcount(Value: LocalRows[Row].OccupiedColumns); |
| 473 | if (!prefixPackElement(Location&: Destinations[Row], Rows, Placement: Bundle)) |
| 474 | return make_error<SignaturePackingError>( |
| 475 | Args: SignaturePackingError::SignatureOverflow, Args&: First->Index); |
| 476 | // Later elements can establish an initially undefined interpolation mode. |
| 477 | Rows[Destinations[Row].Row].InterpMode = LocalRows[Row].InterpMode; |
| 478 | } |
| 479 | for (auto &Element : Elements) { |
| 480 | ElementLocation Destination = Destinations[Element.Location.Row]; |
| 481 | Element.Location = { |
| 482 | .Row: Destination.Row, |
| 483 | .Col: static_cast<uint8_t>(Destination.Col + Element.Location.Col)}; |
| 484 | } |
| 485 | return Error::success(); |
| 486 | } |
| 487 | |
| 488 | // Try the whole indexed group in each adjacent pair. Preserve absolute row |
| 489 | // coordinates for existing indexed ranges, even those extending beyond it. |
| 490 | for (unsigned Row = 0; Row + MaxClipCullRows <= Rows.size(); ++Row) { |
| 491 | SmallVector<SignatureRow, MaxSignatureRows> CandidateRows(Rows.begin(), |
| 492 | Rows.end()); |
| 493 | bool Fits = true; |
| 494 | for (auto &Element : Elements) { |
| 495 | Element.Location = {}; |
| 496 | for (unsigned Start = Row; |
| 497 | Start + Element.Placement.Rows <= Row + MaxClipCullRows; ++Start) { |
| 498 | if (auto Mask = canPlaceAt(Rows: CandidateRows, StartRow: Start, Placement: Element.Placement)) { |
| 499 | placeAt(Rows: CandidateRows, StartRow: Start, Placement: Element.Placement, ColumnMask: *Mask, |
| 500 | Location&: Element.Location); |
| 501 | break; |
| 502 | } |
| 503 | } |
| 504 | if (Element.Location.Row == UnallocatedRow) { |
| 505 | Fits = false; |
| 506 | break; |
| 507 | } |
| 508 | } |
| 509 | if (Fits) { |
| 510 | llvm::copy(Range: ArrayRef(CandidateRows).slice(N: Row, M: MaxClipCullRows), |
| 511 | Out: Rows.begin() + Row); |
| 512 | return Error::success(); |
| 513 | } |
| 514 | } |
| 515 | // No element alone necessarily caused this failure; identify the group. |
| 516 | return make_error<SignaturePackingError>( |
| 517 | Args: SignaturePackingError::SignatureOverflow, Args&: Elements.front().Index); |
| 518 | } |
| 519 | |
| 520 | static Expected<unsigned> |
| 521 | packOptimizedClipCull(MutableArrayRef<SemanticSignatureElement> Elements, |
| 522 | ArrayRef<unsigned> Order, |
| 523 | MutableArrayRef<SignatureRows> Rows, |
| 524 | bool UseNative16BitTypes) { |
| 525 | if (Order.empty()) |
| 526 | return 0; |
| 527 | SmallVector<SmallVector<OptimizedClipCullElement>, MaxGeometryStreams> |
| 528 | Streams(Rows.size()); |
| 529 | for (unsigned Index : Order) { |
| 530 | const auto &Element = Elements[Index]; |
| 531 | assert(Element.StartRow == UnallocatedRow && |
| 532 | Element.StartCol == UnallocatedCol && "already allocated?" ); |
| 533 | assert(Element.Rows > 0 && "signature element must have at least one row" ); |
| 534 | assert(Element.Cols > 0 && Element.Cols <= MaxSignatureCols && |
| 535 | "signature element must have between 1 and 4 columns" ); |
| 536 | if (Element.GSStream >= Rows.size()) |
| 537 | return make_error<SignaturePackingError>( |
| 538 | Args: SignaturePackingError::InvalidGeometryStream, Args&: Index); |
| 539 | Streams[Element.GSStream].push_back( |
| 540 | Elt: {.Index: Index, |
| 541 | .Placement: getElementPlacement(Element, Interpretation: SemanticInterpretation::ClipCull, |
| 542 | UseNative16BitTypes), |
| 543 | .Location: {}}); |
| 544 | } |
| 545 | |
| 546 | SmallVector<SignatureRows, MaxGeometryStreams> CandidateRows(Rows.begin(), |
| 547 | Rows.end()); |
| 548 | for (unsigned Stream = 0; Stream != Streams.size(); ++Stream) |
| 549 | if (Error Err = |
| 550 | packOptimizedClipCullStream(Elements: Streams[Stream], Rows: CandidateRows[Stream])) |
| 551 | return std::move(Err); |
| 552 | |
| 553 | // Publish only after every stream succeeds. No rollback or partial-prefix |
| 554 | // recovery is needed, and preceding non-clip/cull allocations remain intact. |
| 555 | llvm::copy(Range&: CandidateRows, Out: Rows.begin()); |
| 556 | unsigned NumRows = 0; |
| 557 | for (const auto &Stream : Streams) |
| 558 | for (const auto &Element : Stream) { |
| 559 | Elements[Element.Index].StartRow = Element.Location.Row; |
| 560 | Elements[Element.Index].StartCol = Element.Location.Col; |
| 561 | NumRows = |
| 562 | std::max(a: NumRows, b: Element.Location.Row + Element.Placement.Rows); |
| 563 | } |
| 564 | return NumRows; |
| 565 | } |
| 566 | |
| 567 | void SignaturePackingError::log(raw_ostream &OS) const { |
| 568 | switch (Kind) { |
| 569 | case SignatureOverflow: |
| 570 | OS << "signature elements do not fit in " << MaxSignatureRows << " rows" ; |
| 571 | break; |
| 572 | case SemanticIndexOutOfRange: |
| 573 | OS << "semantic index must be less than " << MaxSignatureRows; |
| 574 | break; |
| 575 | case ClipCullOverflow: |
| 576 | OS << "clip/cull elements do not fit in " << MaxClipCullRows << " rows" ; |
| 577 | break; |
| 578 | case ClipCullNotAdjacent: |
| 579 | OS << "indexed clip/cull elements require adjacent signature rows" ; |
| 580 | break; |
| 581 | case InvalidGeometryStream: |
| 582 | OS << "signature element has an invalid geometry stream: expected an index " |
| 583 | "less than " |
| 584 | << MaxGeometryStreams << " for geometry outputs, or zero otherwise" ; |
| 585 | break; |
| 586 | } |
| 587 | OS << " (element " << ElementIndex << ")" ; |
| 588 | } |
| 589 | |
| 590 | Expected<unsigned> llvm::hlsl::packSignatureStacked( |
| 591 | MutableArrayRef<SemanticSignatureElement> Elements, |
| 592 | Triple::EnvironmentType ShaderStage, IOType IOTy) { |
| 593 | assert(ShaderStage == Triple::Vertex && IOTy == IOType::In && |
| 594 | "stacked packing is only valid for a vertex shader input signature" ); |
| 595 | |
| 596 | unsigned NextRow = 0; |
| 597 | for (auto &&[Index, Element] : enumerate(First&: Elements)) { |
| 598 | assert(Element.StartRow == UnallocatedRow && |
| 599 | Element.StartCol == UnallocatedCol && "already allocated?" ); |
| 600 | assert(Element.Rows > 0 && "signature element must have at least one row" ); |
| 601 | assert(Element.Cols > 0 && Element.Cols <= MaxSignatureCols && |
| 602 | "signature element must have between 1 and 4 columns" ); |
| 603 | |
| 604 | SemanticInterpretation Interpretation = |
| 605 | getInterpretationKind(SemanticKind: Element.SemanticKind, ShaderStage, IOTy); |
| 606 | if (Interpretation == SemanticInterpretation::NotAllocated || |
| 607 | Interpretation == SemanticInterpretation::NotPacked) |
| 608 | continue; |
| 609 | |
| 610 | assert((Interpretation == SemanticInterpretation::Arbitrary || |
| 611 | Interpretation == SemanticInterpretation::SV || |
| 612 | Interpretation == SemanticInterpretation::SGV) && |
| 613 | "unexpected semantic interpretation for stacked packing, should " |
| 614 | "have been diagnosed by Sema" ); |
| 615 | |
| 616 | if (Element.Rows > MaxSignatureRows - NextRow) |
| 617 | return make_error<SignaturePackingError>( |
| 618 | Args: SignaturePackingError::SignatureOverflow, |
| 619 | Args: static_cast<unsigned>(Index)); |
| 620 | |
| 621 | Element.StartRow = NextRow; |
| 622 | Element.StartCol = 0; |
| 623 | NextRow += Element.Rows; |
| 624 | } |
| 625 | |
| 626 | return NextRow; |
| 627 | } |
| 628 | |
| 629 | template <typename IndexRange> |
| 630 | static Expected<unsigned> packSignatureInOrder( |
| 631 | MutableArrayRef<SemanticSignatureElement> Elements, const IndexRange &Order, |
| 632 | Triple::EnvironmentType ShaderStage, IOType IOTy, bool UseNative16BitTypes, |
| 633 | MutableArrayRef<SignatureRows> Rows) { |
| 634 | SmallVector<ClipCullState, 1> ClipCullStates(Rows.size()); |
| 635 | unsigned NumRows = 0; |
| 636 | for (unsigned Index : Order) { |
| 637 | const SemanticSignatureElement &Element = Elements[Index]; |
| 638 | assert(Element.StartRow == UnallocatedRow && |
| 639 | Element.StartCol == UnallocatedCol && "already allocated?" ); |
| 640 | assert(Element.Rows > 0 && "signature element must have at least one row" ); |
| 641 | assert(Element.Cols > 0 && Element.Cols <= MaxSignatureCols && |
| 642 | "signature element must have between 1 and 4 columns" ); |
| 643 | if (Element.GSStream >= Rows.size()) |
| 644 | return make_error<SignaturePackingError>( |
| 645 | Args: SignaturePackingError::InvalidGeometryStream, |
| 646 | Args: static_cast<unsigned>(Index)); |
| 647 | |
| 648 | SemanticInterpretation Interpretation = |
| 649 | getInterpretationKind(SemanticKind: Element.SemanticKind, ShaderStage, IOTy); |
| 650 | if (Interpretation == SemanticInterpretation::NotAllocated || |
| 651 | Interpretation == SemanticInterpretation::NotPacked) |
| 652 | continue; |
| 653 | |
| 654 | assert((Interpretation == SemanticInterpretation::Arbitrary || |
| 655 | Interpretation == SemanticInterpretation::SV || |
| 656 | Interpretation == SemanticInterpretation::SGV || |
| 657 | Interpretation == SemanticInterpretation::ClipCull || |
| 658 | Interpretation == SemanticInterpretation::TessFactor) && |
| 659 | "unexpected semantic interpretation for prefix-stable packing, " |
| 660 | "should have been diagnosed by Sema" ); |
| 661 | |
| 662 | const ElementPlacement Placement = |
| 663 | getElementPlacement(Element, Interpretation, UseNative16BitTypes); |
| 664 | |
| 665 | const unsigned StreamIndex = Element.GSStream; |
| 666 | MutableArrayRef<SignatureRow> StreamRows = Rows[StreamIndex]; |
| 667 | ElementLocation Location; |
| 668 | |
| 669 | if (Interpretation == SemanticInterpretation::ClipCull) { |
| 670 | if (std::optional<SignaturePackingError::ErrorKind> Kind = |
| 671 | packClipCullElement(Location, SignatureRows: StreamRows, |
| 672 | State&: ClipCullStates[StreamIndex], Placement)) |
| 673 | return make_error<SignaturePackingError>(Args&: *Kind, Args&: Index); |
| 674 | } else if (!prefixPackElement(Location, Rows: StreamRows, Placement)) { |
| 675 | return make_error<SignaturePackingError>( |
| 676 | Args: SignaturePackingError::SignatureOverflow, |
| 677 | Args: static_cast<unsigned>(Index)); |
| 678 | } |
| 679 | |
| 680 | Elements[Index].StartRow = Location.Row; |
| 681 | Elements[Index].StartCol = Location.Col; |
| 682 | NumRows = std::max(a: NumRows, b: Location.Row + Element.Rows); |
| 683 | } |
| 684 | |
| 685 | return NumRows; |
| 686 | } |
| 687 | |
| 688 | Expected<unsigned> llvm::hlsl::packSignaturePrefixStable( |
| 689 | MutableArrayRef<SemanticSignatureElement> Elements, |
| 690 | Triple::EnvironmentType ShaderStage, IOType IOTy, |
| 691 | bool UseNative16BitTypes) { |
| 692 | assert(!(ShaderStage == Triple::Vertex && IOTy == IOType::In) && |
| 693 | !(ShaderStage == Triple::Pixel && IOTy == IOType::Out) && |
| 694 | "prefix-stable packing is not valid for vertex inputs or pixel " |
| 695 | "outputs" ); |
| 696 | const unsigned StreamCount = |
| 697 | ShaderStage == Triple::Geometry && IOTy == IOType::Out |
| 698 | ? MaxGeometryStreams |
| 699 | : 1; |
| 700 | SmallVector<SignatureRows, 1> Rows(StreamCount); |
| 701 | return packSignatureInOrder(Elements, Order: llvm::seq<unsigned>(Begin: 0, End: Elements.size()), |
| 702 | ShaderStage, IOTy, UseNative16BitTypes, Rows); |
| 703 | } |
| 704 | |
| 705 | Expected<unsigned> llvm::hlsl::packSignatureIndexed( |
| 706 | MutableArrayRef<SemanticSignatureElement> Elements, |
| 707 | Triple::EnvironmentType ShaderStage, IOType IOTy) { |
| 708 | assert(ShaderStage == Triple::Pixel && IOTy == IOType::Out && |
| 709 | "indexed packing is only valid for a pixel shader output signature" ); |
| 710 | |
| 711 | static_assert(MaxSignatureRows <= std::numeric_limits<uint32_t>::digits, |
| 712 | "row allocation mask is too small" ); |
| 713 | [[maybe_unused]] uint32_t AllocatedRows = 0; |
| 714 | unsigned NumRows = 0; |
| 715 | for (auto &&[Index, Element] : enumerate(First&: Elements)) { |
| 716 | assert(Element.StartRow == UnallocatedRow && |
| 717 | Element.StartCol == UnallocatedCol && "already allocated?" ); |
| 718 | assert(Element.Rows > 0 && "signature element must have at least one row" ); |
| 719 | assert(Element.Cols > 0 && Element.Cols <= MaxSignatureCols && |
| 720 | "signature element must have between 1 and 4 columns" ); |
| 721 | |
| 722 | SemanticInterpretation Interpretation = |
| 723 | getInterpretationKind(SemanticKind: Element.SemanticKind, ShaderStage, IOTy); |
| 724 | if (Interpretation == SemanticInterpretation::NotAllocated || |
| 725 | Interpretation == SemanticInterpretation::NotPacked) |
| 726 | continue; |
| 727 | |
| 728 | assert(Interpretation == SemanticInterpretation::Target && |
| 729 | "unexpected semantic interpretation for indexed packing, should " |
| 730 | "have been diagnosed by Sema" ); |
| 731 | assert(Element.Rows == 1 && Element.SemanticIndices.size() == 1 && |
| 732 | "target elements must occupy one semantic row" ); |
| 733 | |
| 734 | const uint32_t Row = Element.SemanticIndices.front(); |
| 735 | if (Row >= MaxSignatureRows) |
| 736 | return make_error<SignaturePackingError>( |
| 737 | Args: SignaturePackingError::SemanticIndexOutOfRange, |
| 738 | Args: static_cast<unsigned>(Index)); |
| 739 | |
| 740 | const uint32_t RowMask = uint32_t{1} << Row; |
| 741 | assert(!(AllocatedRows & RowMask) && |
| 742 | "target semantic indices must be unique, verified in SemaHLSL" ); |
| 743 | AllocatedRows |= RowMask; |
| 744 | |
| 745 | Element.StartRow = Row; |
| 746 | Element.StartCol = 0; |
| 747 | NumRows = std::max(a: NumRows, b: Row + 1); |
| 748 | } |
| 749 | |
| 750 | return NumRows; |
| 751 | } |
| 752 | |
| 753 | Expected<unsigned> llvm::hlsl::packSignatureOptimized( |
| 754 | MutableArrayRef<SemanticSignatureElement> Elements, |
| 755 | Triple::EnvironmentType ShaderStage, IOType IOTy, |
| 756 | bool UseNative16BitTypes) { |
| 757 | assert(!(ShaderStage == Triple::Vertex && IOTy == IOType::In) && |
| 758 | !(ShaderStage == Triple::Pixel && IOTy == IOType::Out) && |
| 759 | "optimized packing is not valid for vertex inputs or pixel outputs" ); |
| 760 | |
| 761 | struct SortKey { |
| 762 | PackingGroup Group; |
| 763 | dxbc::PSV::InterpolationMode InterpMode; |
| 764 | uint32_t Rows; |
| 765 | uint8_t Cols; |
| 766 | uint32_t SigId; |
| 767 | unsigned OriginalIndex; |
| 768 | }; |
| 769 | SmallVector<SortKey> SortedKeys; |
| 770 | SortedKeys.reserve(N: Elements.size()); |
| 771 | for (auto [Index, Element] : enumerate(First&: Elements)) |
| 772 | SortedKeys.push_back(Elt: {.Group: getOptimizedPackingGroup(Element, ShaderStage, IOTy), |
| 773 | .InterpMode: Element.InterpMode, .Rows: Element.Rows, .Cols: Element.Cols, |
| 774 | .SigId: Element.SigId, .OriginalIndex: static_cast<unsigned>(Index)}); |
| 775 | |
| 776 | llvm::sort(C&: SortedKeys, Comp: [](const SortKey &Left, const SortKey &Right) { |
| 777 | if (Left.Group != Right.Group) |
| 778 | return Left.Group < Right.Group; |
| 779 | if (Left.InterpMode != Right.InterpMode) |
| 780 | return Left.InterpMode < Right.InterpMode; |
| 781 | if (Left.Rows != Right.Rows) |
| 782 | return Left.Rows > Right.Rows; |
| 783 | if (Left.Cols != Right.Cols) |
| 784 | return Left.Cols > Right.Cols; |
| 785 | return Left.SigId < Right.SigId; |
| 786 | }); |
| 787 | |
| 788 | const unsigned StreamCount = |
| 789 | ShaderStage == Triple::Geometry && IOTy == IOType::Out |
| 790 | ? MaxGeometryStreams |
| 791 | : 1; |
| 792 | SmallVector<SignatureRows, 1> Rows(StreamCount); |
| 793 | auto ClipBegin = llvm::partition_point(Range&: SortedKeys, P: [](const SortKey &Key) { |
| 794 | return Key.Group < PackingGroup::ClipCull; |
| 795 | }); |
| 796 | auto ClipEnd = llvm::partition_point( |
| 797 | Range: make_range(x: ClipBegin, y: SortedKeys.end()), |
| 798 | P: [](const SortKey &Key) { return Key.Group == PackingGroup::ClipCull; }); |
| 799 | |
| 800 | auto Pack = [&](auto Begin, auto End) { |
| 801 | auto Order = map_range(make_range(Begin, End), [](const SortKey &Key) { |
| 802 | return Key.OriginalIndex; |
| 803 | }); |
| 804 | return packSignatureInOrder(Elements, Order, ShaderStage, IOTy, |
| 805 | UseNative16BitTypes, Rows); |
| 806 | }; |
| 807 | |
| 808 | Expected<unsigned> Before = Pack(SortedKeys.begin(), ClipBegin); |
| 809 | if (!Before) |
| 810 | return Before.takeError(); |
| 811 | SmallVector<unsigned> ClipCullOrder; |
| 812 | for (const SortKey &Key : make_range(x: ClipBegin, y: ClipEnd)) |
| 813 | ClipCullOrder.push_back(Elt: Key.OriginalIndex); |
| 814 | Expected<unsigned> ClipCull = |
| 815 | packOptimizedClipCull(Elements, Order: ClipCullOrder, Rows, UseNative16BitTypes); |
| 816 | if (!ClipCull) |
| 817 | return ClipCull.takeError(); |
| 818 | Expected<unsigned> After = Pack(ClipEnd, SortedKeys.end()); |
| 819 | if (!After) |
| 820 | return After.takeError(); |
| 821 | return std::max(l: {*Before, *ClipCull, *After}); |
| 822 | } |
| 823 | |