kc3-lang/angle/src/libANGLE/VaryingPacking.cpp

Branch : - branch - main - tag -

• Show log

  Commit

• Author : Shahbaz Youssefi
  Date : 2020-12-01 15:43:13
  Hash : bb3adfa4
  Message : Rename ShaderVariable::structName to structOrBlockName Bug: angleproject:3580 Change-Id: Ic53a5267972f153dad2e20948e493e9767a45d16 Reviewed-on: https://chromium-review.googlesource.com/c/angle/angle/+/2568247 Commit-Queue: Shahbaz Youssefi <syoussefi@chromium.org> Reviewed-by: Jamie Madill <jmadill@chromium.org>

• src/libANGLE/VaryingPacking.cpp

• //
  // Copyright 2015 The ANGLE Project Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style license that can be
  // found in the LICENSE file.
  //
  // VaryingPacking:
  //   Class which describes a mapping from varyings to registers, according
  //   to the spec, or using custom packing algorithms. We also keep a register
  //   allocation list for the D3D renderer.
  //
  
  #include "libANGLE/VaryingPacking.h"
  
  #include "common/utilities.h"
  #include "libANGLE/Program.h"
  #include "libANGLE/Shader.h"
  
  namespace gl
  {
  
  namespace
  {
  
  // true if varying x has a higher priority in packing than y
  bool ComparePackedVarying(const PackedVarying &x, const PackedVarying &y)
  {
      // If the PackedVarying 'x' or 'y' to be compared is an array element for transform feedback,
      // this clones an equivalent non-array shader variable 'vx' or 'vy' for actual comparison
      // instead.  For I/O block arrays, the array index is used in the comparison.
      sh::ShaderVariable vx, vy;
      const sh::ShaderVariable *px, *py;
  
      px = &x.varying();
      py = &y.varying();
  
      if (x.isTransformFeedbackArrayElement())
      {
          vx = *px;
          vx.arraySizes.clear();
          px = &vx;
      }
  
      if (y.isTransformFeedbackArrayElement())
      {
          vy = *py;
          vy.arraySizes.clear();
          py = &vy;
      }
  
      // Make sure struct fields end up together.
      if (x.isStructField() != y.isStructField())
      {
          return x.isStructField();
      }
  
      if (x.isStructField())
      {
          ASSERT(y.isStructField());
  
          if (x.getParentStructName() != y.getParentStructName())
          {
              return x.getParentStructName() < y.getParentStructName();
          }
      }
  
      // For I/O block fields, order first by array index:
      if (!x.isTransformFeedbackArrayElement() && !y.isTransformFeedbackArrayElement())
      {
          if (x.arrayIndex != y.arrayIndex)
          {
              return x.arrayIndex < y.arrayIndex;
          }
      }
  
      // Then order by field index
      if (x.fieldIndex != y.fieldIndex)
      {
          return x.fieldIndex < y.fieldIndex;
      }
  
      // Then order by secondary field index
      if (x.secondaryFieldIndex != y.secondaryFieldIndex)
      {
          return x.secondaryFieldIndex < y.secondaryFieldIndex;
      }
  
      // Otherwise order by variable
      return gl::CompareShaderVar(*px, *py);
  }
  
  bool InterfaceVariablesMatch(const sh::ShaderVariable &front, const sh::ShaderVariable &back)
  {
      // Matching ruels from 7.4.1 Shader Interface Matching from the GLES 3.2 spec:
      // - the two variables match in name, type, and qualification; or
      // - the two variables are declared with the same location qualifier and match in type and
      // qualification. Note that we use a more permissive check here thanks to front-end validation.
      if (back.location != -1 && back.location == front.location)
      {
          return true;
      }
  
      if (front.isShaderIOBlock != back.isShaderIOBlock)
      {
          return false;
      }
  
      // Compare names, or if shader I/O blocks, block names.
      const std::string &backName  = back.isShaderIOBlock ? back.structOrBlockName : back.name;
      const std::string &frontName = front.isShaderIOBlock ? front.structOrBlockName : front.name;
      return backName == frontName;
  }
  
  GLint GetMaxShaderInputVectors(const Caps &caps, ShaderType shaderStage)
  {
      switch (shaderStage)
      {
          case ShaderType::TessControl:
              return caps.maxTessControlInputComponents / 4;
          case ShaderType::TessEvaluation:
              return caps.maxTessEvaluationInputComponents / 4;
          case ShaderType::Geometry:
              return caps.maxGeometryInputComponents / 4;
          case ShaderType::Fragment:
              return caps.maxFragmentInputComponents / 4;
          default:
              return std::numeric_limits<GLint>::max();
      }
  }
  
  GLint GetMaxShaderOutputVectors(const Caps &caps, ShaderType shaderStage)
  {
      switch (shaderStage)
      {
          case ShaderType::Vertex:
              return caps.maxVertexOutputComponents / 4;
          case ShaderType::TessControl:
              return caps.maxTessControlOutputComponents / 4;
          case ShaderType::TessEvaluation:
              return caps.maxTessEvaluationOutputComponents / 4;
          case ShaderType::Geometry:
              return caps.maxGeometryOutputComponents / 4;
          default:
              return std::numeric_limits<GLint>::max();
      }
  }
  
  bool ShouldSkipPackedVarying(const sh::ShaderVariable &varying, PackMode packMode)
  {
      // Don't pack gl_Position. Also don't count gl_PointSize for D3D9.
      return varying.name == "gl_Position" ||
             (varying.name == "gl_PointSize" && packMode == PackMode::ANGLE_NON_CONFORMANT_D3D9);
  }
  
  std::vector<unsigned int> StripVaryingArrayDimension(const sh::ShaderVariable *frontVarying,
                                                       ShaderType frontShaderStage,
                                                       const sh::ShaderVariable *backVarying,
                                                       ShaderType backShaderStage,
                                                       bool isStructField)
  {
      // "Geometry shader inputs, tessellation control shader inputs and outputs, and tessellation
      // evaluation inputs all have an additional level of arrayness relative to other shader inputs
      // and outputs. This outer array level is removed from the type before considering how many
      // locations the type consumes."
  
      if (backVarying && backVarying->isArray() && !backVarying->isPatch && !isStructField &&
          (backShaderStage == ShaderType::Geometry || backShaderStage == ShaderType::TessEvaluation ||
           backShaderStage == ShaderType::TessControl))
      {
          std::vector<unsigned int> arr = backVarying->arraySizes;
          arr.pop_back();
          return arr;
      }
  
      if (frontVarying && frontVarying->isArray() && !frontVarying->isPatch && !isStructField &&
          frontShaderStage == ShaderType::TessControl)
      {
          std::vector<unsigned int> arr = frontVarying->arraySizes;
          arr.pop_back();
          return arr;
      }
  
      return frontVarying ? frontVarying->arraySizes : backVarying->arraySizes;
  }
  }  // anonymous namespace
  
  // Implementation of VaryingInShaderRef
  VaryingInShaderRef::VaryingInShaderRef(ShaderType stageIn, const sh::ShaderVariable *varyingIn)
      : varying(varyingIn), stage(stageIn)
  {}
  
  VaryingInShaderRef::~VaryingInShaderRef() = default;
  
  VaryingInShaderRef::VaryingInShaderRef(VaryingInShaderRef &&other)
      : varying(other.varying),
        stage(other.stage),
        parentStructName(std::move(other.parentStructName)),
        parentStructMappedName(std::move(other.parentStructMappedName))
  {}
  
  VaryingInShaderRef &VaryingInShaderRef::operator=(VaryingInShaderRef &&other)
  {
      std::swap(varying, other.varying);
      std::swap(stage, other.stage);
      std::swap(parentStructName, other.parentStructName);
      std::swap(parentStructMappedName, other.parentStructMappedName);
  
      return *this;
  }
  
  // Implementation of PackedVarying
  PackedVarying::PackedVarying(VaryingInShaderRef &&frontVaryingIn,
                               VaryingInShaderRef &&backVaryingIn,
                               sh::InterpolationType interpolationIn)
      : PackedVarying(std::move(frontVaryingIn),
                      std::move(backVaryingIn),
                      interpolationIn,
                      GL_INVALID_INDEX,
                      0,
                      0)
  {}
  
  PackedVarying::PackedVarying(VaryingInShaderRef &&frontVaryingIn,
                               VaryingInShaderRef &&backVaryingIn,
                               sh::InterpolationType interpolationIn,
                               GLuint arrayIndexIn,
                               GLuint fieldIndexIn,
                               GLuint secondaryFieldIndexIn)
      : frontVarying(std::move(frontVaryingIn)),
        backVarying(std::move(backVaryingIn)),
        interpolation(interpolationIn),
        arrayIndex(arrayIndexIn),
        isTransformFeedback(false),
        fieldIndex(fieldIndexIn),
        secondaryFieldIndex(secondaryFieldIndexIn)
  {}
  
  PackedVarying::~PackedVarying() = default;
  
  PackedVarying::PackedVarying(PackedVarying &&other)
      : frontVarying(std::move(other.frontVarying)),
        backVarying(std::move(other.backVarying)),
        interpolation(other.interpolation),
        arrayIndex(other.arrayIndex),
        isTransformFeedback(other.isTransformFeedback),
        fieldIndex(other.fieldIndex),
        secondaryFieldIndex(other.secondaryFieldIndex)
  {}
  
  PackedVarying &PackedVarying::operator=(PackedVarying &&other)
  {
      std::swap(frontVarying, other.frontVarying);
      std::swap(backVarying, other.backVarying);
      std::swap(interpolation, other.interpolation);
      std::swap(arrayIndex, other.arrayIndex);
      std::swap(isTransformFeedback, other.isTransformFeedback);
      std::swap(fieldIndex, other.fieldIndex);
      std::swap(secondaryFieldIndex, other.secondaryFieldIndex);
  
      return *this;
  }
  
  unsigned int PackedVarying::getBasicTypeElementCount() const
  {
      // "Geometry shader inputs, tessellation control shader inputs and outputs, and tessellation
      // evaluation inputs all have an additional level of arrayness relative to other shader inputs
      // and outputs. This outer array level is removed from the type before considering how many
      // locations the type consumes."
      std::vector<unsigned int> arr =
          StripVaryingArrayDimension(frontVarying.varying, frontVarying.stage, backVarying.varying,
                                     backVarying.stage, isStructField());
      return arr.empty() ? 1u : arr.back();
  }
  
  // Implementation of VaryingPacking
  VaryingPacking::VaryingPacking() = default;
  
  VaryingPacking::~VaryingPacking() = default;
  
  void VaryingPacking::reset()
  {
      clearRegisterMap();
      mRegisterList.clear();
      mPackedVaryings.clear();
  
      for (std::vector<std::string> &inactiveVaryingMappedNames : mInactiveVaryingMappedNames)
      {
          inactiveVaryingMappedNames.clear();
      }
  
      for (std::vector<std::string> &activeBuiltIns : mActiveOutputBuiltIns)
      {
          activeBuiltIns.clear();
      }
  }
  
  void VaryingPacking::clearRegisterMap()
  {
      std::fill(mRegisterMap.begin(), mRegisterMap.end(), Register());
  }
  
  // Packs varyings into generic varying registers, using the algorithm from
  // See [OpenGL ES Shading Language 1.00 rev. 17] appendix A section 7 page 111
  // Also [OpenGL ES Shading Language 3.00 rev. 4] Section 11 page 119
  // Returns false if unsuccessful.
  bool VaryingPacking::packVaryingIntoRegisterMap(PackMode packMode,
                                                  const PackedVarying &packedVarying)
  {
      const sh::ShaderVariable &varying = packedVarying.varying();
  
      // "Non - square matrices of type matCxR consume the same space as a square matrix of type matN
      // where N is the greater of C and R."
      // Here we are a bit more conservative and allow packing non-square matrices more tightly.
      // Make sure we use transposed matrix types to count registers correctly.
      ASSERT(!varying.isStruct());
      GLenum transposedType       = gl::TransposeMatrixType(varying.type);
      unsigned int varyingRows    = gl::VariableRowCount(transposedType);
      unsigned int varyingColumns = gl::VariableColumnCount(transposedType);
  
      // Special pack mode for D3D9. Each varying takes a full register, no sharing.
      // TODO(jmadill): Implement more sophisticated component packing in D3D9.
      if (packMode == PackMode::ANGLE_NON_CONFORMANT_D3D9)
      {
          varyingColumns = 4;
      }
  
      // "Variables of type mat2 occupies 2 complete rows."
      // For non-WebGL contexts, we allow mat2 to occupy only two columns per row.
      else if (packMode == PackMode::WEBGL_STRICT && varying.type == GL_FLOAT_MAT2)
      {
          varyingColumns = 4;
      }
  
      // "Arrays of size N are assumed to take N times the size of the base type"
      // GLSL ES 3.10 section 4.3.6: Output variables cannot be arrays of arrays or arrays of
      // structures, so we may use getBasicTypeElementCount().
      const unsigned int elementCount = packedVarying.getBasicTypeElementCount();
      varyingRows *= (packedVarying.isTransformFeedbackArrayElement() ? 1 : elementCount);
  
      unsigned int maxVaryingVectors = static_cast<unsigned int>(mRegisterMap.size());
  
      // Fail if we are packing a single over-large varying.
      if (varyingRows > maxVaryingVectors)
      {
          return false;
      }
  
      // "For 2, 3 and 4 component variables packing is started using the 1st column of the 1st row.
      // Variables are then allocated to successive rows, aligning them to the 1st column."
      if (varyingColumns >= 2 && varyingColumns <= 4)
      {
          for (unsigned int row = 0; row <= maxVaryingVectors - varyingRows; ++row)
          {
              if (isRegisterRangeFree(row, 0, varyingRows, varyingColumns))
              {
                  insertVaryingIntoRegisterMap(row, 0, varyingColumns, packedVarying);
                  return true;
              }
          }
  
          // "For 2 component variables, when there are no spare rows, the strategy is switched to
          // using the highest numbered row and the lowest numbered column where the variable will
          // fit."
          if (varyingColumns == 2)
          {
              for (unsigned int r = maxVaryingVectors - varyingRows + 1; r-- >= 1;)
              {
                  if (isRegisterRangeFree(r, 2, varyingRows, 2))
                  {
                      insertVaryingIntoRegisterMap(r, 2, varyingColumns, packedVarying);
                      return true;
                  }
              }
          }
  
          return false;
      }
  
      // "1 component variables have their own packing rule. They are packed in order of size, largest
      // first. Each variable is placed in the column that leaves the least amount of space in the
      // column and aligned to the lowest available rows within that column."
      ASSERT(varyingColumns == 1);
      unsigned int contiguousSpace[4]     = {0};
      unsigned int bestContiguousSpace[4] = {0};
      unsigned int totalSpace[4]          = {0};
  
      for (unsigned int row = 0; row < maxVaryingVectors; ++row)
      {
          for (unsigned int column = 0; column < 4; ++column)
          {
              if (mRegisterMap[row][column])
              {
                  contiguousSpace[column] = 0;
              }
              else
              {
                  contiguousSpace[column]++;
                  totalSpace[column]++;
  
                  if (contiguousSpace[column] > bestContiguousSpace[column])
                  {
                      bestContiguousSpace[column] = contiguousSpace[column];
                  }
              }
          }
      }
  
      unsigned int bestColumn = 0;
      for (unsigned int column = 1; column < 4; ++column)
      {
          if (bestContiguousSpace[column] >= varyingRows &&
              (bestContiguousSpace[bestColumn] < varyingRows ||
               totalSpace[column] < totalSpace[bestColumn]))
          {
              bestColumn = column;
          }
      }
  
      if (bestContiguousSpace[bestColumn] >= varyingRows)
      {
          for (unsigned int row = 0; row < maxVaryingVectors; row++)
          {
              if (isRegisterRangeFree(row, bestColumn, varyingRows, 1))
              {
                  for (unsigned int arrayIndex = 0; arrayIndex < varyingRows; ++arrayIndex)
                  {
                      // If varyingRows > 1, it must be an array.
                      PackedVaryingRegister registerInfo;
                      registerInfo.packedVarying  = &packedVarying;
                      registerInfo.registerRow    = row + arrayIndex;
                      registerInfo.registerColumn = bestColumn;
                      registerInfo.varyingArrayIndex =
                          (packedVarying.isTransformFeedbackArrayElement() ? packedVarying.arrayIndex
                                                                           : arrayIndex);
                      registerInfo.varyingRowIndex = 0;
                      // Do not record register info for builtins.
                      // TODO(jmadill): Clean this up.
                      if (!varying.isBuiltIn())
                      {
                          mRegisterList.push_back(registerInfo);
                      }
                      mRegisterMap[row + arrayIndex][bestColumn] = true;
                  }
                  break;
              }
          }
          return true;
      }
  
      return false;
  }
  
  bool VaryingPacking::isRegisterRangeFree(unsigned int registerRow,
                                           unsigned int registerColumn,
                                           unsigned int varyingRows,
                                           unsigned int varyingColumns) const
  {
      for (unsigned int row = 0; row < varyingRows; ++row)
      {
          ASSERT(registerRow + row < mRegisterMap.size());
          for (unsigned int column = 0; column < varyingColumns; ++column)
          {
              ASSERT(registerColumn + column < 4);
              if (mRegisterMap[registerRow + row][registerColumn + column])
              {
                  return false;
              }
          }
      }
  
      return true;
  }
  
  void VaryingPacking::insertVaryingIntoRegisterMap(unsigned int registerRow,
                                                    unsigned int registerColumn,
                                                    unsigned int varyingColumns,
                                                    const PackedVarying &packedVarying)
  {
      unsigned int varyingRows = 0;
  
      const sh::ShaderVariable &varying = packedVarying.varying();
      ASSERT(!varying.isStruct());
      GLenum transposedType = gl::TransposeMatrixType(varying.type);
      varyingRows           = gl::VariableRowCount(transposedType);
  
      PackedVaryingRegister registerInfo;
      registerInfo.packedVarying  = &packedVarying;
      registerInfo.registerColumn = registerColumn;
  
      // GLSL ES 3.10 section 4.3.6: Output variables cannot be arrays of arrays or arrays of
      // structures, so we may use getBasicTypeElementCount().
      const unsigned int arrayElementCount = packedVarying.getBasicTypeElementCount();
      for (unsigned int arrayElement = 0; arrayElement < arrayElementCount; ++arrayElement)
      {
          if (packedVarying.isTransformFeedbackArrayElement() &&
              arrayElement != packedVarying.arrayIndex)
          {
              continue;
          }
          for (unsigned int varyingRow = 0; varyingRow < varyingRows; ++varyingRow)
          {
              registerInfo.registerRow     = registerRow + (arrayElement * varyingRows) + varyingRow;
              registerInfo.varyingRowIndex = varyingRow;
              registerInfo.varyingArrayIndex = arrayElement;
              // Do not record register info for builtins.
              // TODO(jmadill): Clean this up.
              if (!varying.isBuiltIn())
              {
                  mRegisterList.push_back(registerInfo);
              }
  
              for (unsigned int columnIndex = 0; columnIndex < varyingColumns; ++columnIndex)
              {
                  mRegisterMap[registerInfo.registerRow][registerColumn + columnIndex] = true;
              }
          }
      }
  }
  
  void VaryingPacking::collectUserVarying(const ProgramVaryingRef &ref,
                                          VaryingUniqueFullNames *uniqueFullNames)
  {
      const sh::ShaderVariable *input  = ref.frontShader;
      const sh::ShaderVariable *output = ref.backShader;
  
      // Will get the vertex shader interpolation by default.
      sh::InterpolationType interpolation = input ? input->interpolation : output->interpolation;
  
      VaryingInShaderRef frontVarying(ref.frontShaderStage, input);
      VaryingInShaderRef backVarying(ref.backShaderStage, output);
  
      mPackedVaryings.emplace_back(std::move(frontVarying), std::move(backVarying), interpolation);
      if (input && !input->isBuiltIn())
      {
          (*uniqueFullNames)[ref.frontShaderStage].insert(
              mPackedVaryings.back().fullName(ref.frontShaderStage));
      }
      if (output && !output->isBuiltIn())
      {
          (*uniqueFullNames)[ref.backShaderStage].insert(
              mPackedVaryings.back().fullName(ref.backShaderStage));
      }
  }
  
  void VaryingPacking::collectUserVaryingField(const ProgramVaryingRef &ref,
                                               GLuint arrayIndex,
                                               GLuint fieldIndex,
                                               GLuint secondaryFieldIndex,
                                               VaryingUniqueFullNames *uniqueFullNames)
  {
      const sh::ShaderVariable *input  = ref.frontShader;
      const sh::ShaderVariable *output = ref.backShader;
  
      // Will get the vertex shader interpolation by default.
      sh::InterpolationType interpolation = input ? input->interpolation : output->interpolation;
  
      const sh::ShaderVariable *frontField = input ? &input->fields[fieldIndex] : nullptr;
      const sh::ShaderVariable *backField  = output ? &output->fields[fieldIndex] : nullptr;
  
      if (secondaryFieldIndex != GL_INVALID_INDEX)
      {
          frontField = frontField ? &frontField->fields[secondaryFieldIndex] : nullptr;
          backField  = backField ? &backField->fields[secondaryFieldIndex] : nullptr;
      }
  
      VaryingInShaderRef frontVarying(ref.frontShaderStage, frontField);
      VaryingInShaderRef backVarying(ref.backShaderStage, backField);
  
      if (input)
      {
          if (frontField->isShaderIOBlock)
          {
              frontVarying.parentStructName       = input->structOrBlockName;
              frontVarying.parentStructMappedName = input->mappedStructOrBlockName;
          }
          else
          {
              ASSERT(!frontField->isStruct() && !frontField->isArray());
              frontVarying.parentStructName       = input->name;
              frontVarying.parentStructMappedName = input->mappedName;
          }
      }
      if (output)
      {
          if (backField->isShaderIOBlock)
          {
              backVarying.parentStructName       = output->structOrBlockName;
              backVarying.parentStructMappedName = output->mappedStructOrBlockName;
          }
          else
          {
              ASSERT(!backField->isStruct() && !backField->isArray());
              backVarying.parentStructName       = output->name;
              backVarying.parentStructMappedName = output->mappedName;
          }
      }
  
      mPackedVaryings.emplace_back(std::move(frontVarying), std::move(backVarying), interpolation,
                                   arrayIndex, fieldIndex,
                                   secondaryFieldIndex == GL_INVALID_INDEX ? 0 : secondaryFieldIndex);
  
      if (input)
      {
          (*uniqueFullNames)[ref.frontShaderStage].insert(
              mPackedVaryings.back().fullName(ref.frontShaderStage));
      }
      if (output)
      {
          (*uniqueFullNames)[ref.backShaderStage].insert(
              mPackedVaryings.back().fullName(ref.backShaderStage));
      }
  }
  
  void VaryingPacking::collectUserVaryingTF(const ProgramVaryingRef &ref, size_t subscript)
  {
      const sh::ShaderVariable *input = ref.frontShader;
  
      VaryingInShaderRef frontVarying(ref.frontShaderStage, input);
      VaryingInShaderRef backVarying(ref.backShaderStage, nullptr);
  
      mPackedVaryings.emplace_back(std::move(frontVarying), std::move(backVarying),
                                   input->interpolation);
      mPackedVaryings.back().arrayIndex          = static_cast<GLuint>(subscript);
      mPackedVaryings.back().isTransformFeedback = true;
  }
  
  void VaryingPacking::collectUserVaryingFieldTF(const ProgramVaryingRef &ref,
                                                 const sh::ShaderVariable &field,
                                                 GLuint fieldIndex,
                                                 GLuint secondaryFieldIndex)
  {
      const sh::ShaderVariable *input = ref.frontShader;
  
      const sh::ShaderVariable *frontField = &field;
      if (secondaryFieldIndex != GL_INVALID_INDEX)
      {
          frontField = &frontField->fields[secondaryFieldIndex];
      }
  
      VaryingInShaderRef frontVarying(ref.frontShaderStage, frontField);
      VaryingInShaderRef backVarying(ref.backShaderStage, nullptr);
  
      if (frontField->isShaderIOBlock)
      {
          frontVarying.parentStructName       = input->structOrBlockName;
          frontVarying.parentStructMappedName = input->mappedStructOrBlockName;
      }
      else
      {
          ASSERT(!frontField->isStruct() && !frontField->isArray());
          frontVarying.parentStructName       = input->name;
          frontVarying.parentStructMappedName = input->mappedName;
      }
  
      mPackedVaryings.emplace_back(std::move(frontVarying), std::move(backVarying),
                                   input->interpolation, GL_INVALID_INDEX, fieldIndex,
                                   secondaryFieldIndex == GL_INVALID_INDEX ? 0 : secondaryFieldIndex);
  }
  
  void VaryingPacking::collectVarying(const sh::ShaderVariable &varying,
                                      const ProgramVaryingRef &ref,
                                      PackMode packMode,
                                      VaryingUniqueFullNames *uniqueFullNames)
  {
      const sh::ShaderVariable *input  = ref.frontShader;
      const sh::ShaderVariable *output = ref.backShader;
  
      if (varying.isStruct())
      {
          std::vector<unsigned int> arraySizes = StripVaryingArrayDimension(
              ref.frontShader, ref.frontShaderStage, ref.backShader, ref.backShaderStage, false);
          const bool isArray     = !arraySizes.empty();
          const GLuint arraySize = isArray ? arraySizes[0] : 1;
  
          for (GLuint arrayIndex = 0; arrayIndex < arraySize; ++arrayIndex)
          {
              const GLuint effectiveArrayIndex = isArray ? arrayIndex : GL_INVALID_INDEX;
              for (GLuint fieldIndex = 0; fieldIndex < varying.fields.size(); ++fieldIndex)
              {
                  const sh::ShaderVariable &fieldVarying = varying.fields[fieldIndex];
                  if (ShouldSkipPackedVarying(fieldVarying, packMode))
                  {
                      continue;
                  }
  
                  if (fieldVarying.isStruct())
                  {
                      if (fieldVarying.isArray())
                      {
                          unsigned int structFieldArraySize = fieldVarying.arraySizes[0];
                          for (unsigned int fieldArrayIndex = 0;
                               fieldArrayIndex < structFieldArraySize; ++fieldArrayIndex)
                          {
                              for (GLuint nestedIndex = 0; nestedIndex < fieldVarying.fields.size();
                                   nestedIndex++)
                              {
                                  collectUserVaryingField(ref, effectiveArrayIndex, fieldIndex,
                                                          nestedIndex, uniqueFullNames);
                              }
                          }
                      }
                      else
                      {
                          for (GLuint nestedIndex = 0; nestedIndex < fieldVarying.fields.size();
                               nestedIndex++)
                          {
                              collectUserVaryingField(ref, effectiveArrayIndex, fieldIndex,
                                                      nestedIndex, uniqueFullNames);
                          }
                      }
                  }
                  else
                  {
                      collectUserVaryingField(ref, effectiveArrayIndex, fieldIndex, GL_INVALID_INDEX,
                                              uniqueFullNames);
                  }
              }
          }
          if (input)
          {
              (*uniqueFullNames)[ref.frontShaderStage].insert(input->name);
              if (input->isShaderIOBlock)
              {
                  (*uniqueFullNames)[ref.frontShaderStage].insert(input->structOrBlockName);
              }
          }
          if (output)
          {
              (*uniqueFullNames)[ref.backShaderStage].insert(output->name);
          }
      }
      else
      {
          collectUserVarying(ref, uniqueFullNames);
      }
  }
  
  void VaryingPacking::collectTFVarying(const std::string &tfVarying,
                                        const ProgramVaryingRef &ref,
                                        VaryingUniqueFullNames *uniqueFullNames)
  {
      const sh::ShaderVariable *input = ref.frontShader;
  
      std::vector<unsigned int> subscripts;
      std::string baseName = ParseResourceName(tfVarying, &subscripts);
  
      // Already packed as active varying.
      if ((*uniqueFullNames)[ref.frontShaderStage].count(tfVarying) > 0 ||
          (*uniqueFullNames)[ref.frontShaderStage].count(baseName) > 0 ||
          (input->isShaderIOBlock &&
           (*uniqueFullNames)[ref.frontShaderStage].count(input->structOrBlockName) > 0))
      {
          return;
      }
  
      if (input->isStruct())
      {
          GLuint fieldIndex               = 0;
          const sh::ShaderVariable *field = input->findField(tfVarying, &fieldIndex);
          if (field != nullptr)
          {
              ASSERT(input->isShaderIOBlock || (!field->isStruct() && !field->isArray()));
  
              // If it's an I/O block whose member is being captured, pack every member of the
              // block.  Currently, we pack either all or none of an I/O block.
              if (input->isShaderIOBlock)
              {
                  for (fieldIndex = 0; fieldIndex < input->fields.size(); ++fieldIndex)
                  {
                      if (input->fields[fieldIndex].isStruct())
                      {
  
                          for (GLuint nestedIndex = 0;
                               nestedIndex < input->fields[fieldIndex].fields.size(); nestedIndex++)
                          {
                              collectUserVaryingFieldTF(ref, input->fields[fieldIndex], fieldIndex,
                                                        nestedIndex);
                          }
                      }
                      else
                      {
                          collectUserVaryingFieldTF(ref, input->fields[fieldIndex], fieldIndex,
                                                    GL_INVALID_INDEX);
                      }
                  }
  
                  (*uniqueFullNames)[ref.frontShaderStage].insert(input->structOrBlockName);
              }
              else
              {
                  collectUserVaryingFieldTF(ref, *field, fieldIndex, GL_INVALID_INDEX);
              }
              (*uniqueFullNames)[ref.frontShaderStage].insert(tfVarying);
          }
          (*uniqueFullNames)[ref.frontShaderStage].insert(input->name);
      }
      // Array as a whole and array element conflict has already been checked in
      // linkValidateTransformFeedback.
      else if (baseName == input->name)
      {
          size_t subscript = GL_INVALID_INDEX;
          if (!subscripts.empty())
          {
              subscript = subscripts.back();
          }
  
          // only pack varyings that are not builtins.
          if (tfVarying.compare(0, 3, "gl_") != 0)
          {
              collectUserVaryingTF(ref, subscript);
              (*uniqueFullNames)[ref.frontShaderStage].insert(tfVarying);
          }
      }
  }
  
  bool VaryingPacking::collectAndPackUserVaryings(gl::InfoLog &infoLog,
                                                  GLint maxVaryingVectors,
                                                  PackMode packMode,
                                                  ShaderType frontShaderStage,
                                                  ShaderType backShaderStage,
                                                  const ProgramMergedVaryings &mergedVaryings,
                                                  const std::vector<std::string> &tfVaryings,
                                                  const bool isSeparableProgram)
  {
      VaryingUniqueFullNames uniqueFullNames;
  
      reset();
  
      for (const ProgramVaryingRef &ref : mergedVaryings)
      {
          const sh::ShaderVariable *input  = ref.frontShader;
          const sh::ShaderVariable *output = ref.backShader;
  
          if ((input && ref.frontShaderStage != frontShaderStage) ||
              (output && ref.backShaderStage != backShaderStage))
          {
              continue;
          }
  
          const bool isActiveBuiltInInput  = input && input->isBuiltIn() && input->active;
          const bool isActiveBuiltInOutput = output && output->isBuiltIn() && output->active;
  
          // Keep track of output builtins that are used by the shader, such as gl_Position,
          // gl_PointSize etc.
          if (isActiveBuiltInInput)
          {
              mActiveOutputBuiltIns[ref.frontShaderStage].push_back(input->name);
          }
  
          // Only pack statically used varyings that have a matched input or output, plus special
          // builtins. Note that we pack all statically used user-defined varyings even if they are
          // not active. GLES specs are a bit vague on whether it's allowed to only pack active
          // varyings, though GLES 3.1 spec section 11.1.2.1 says that "device-dependent
          // optimizations" may be used to make vertex shader outputs fit.
          if ((input && output && output->staticUse) || isActiveBuiltInInput ||
              isActiveBuiltInOutput ||
              (isSeparableProgram && ((input && input->active) || (output && output->active))))
          {
              const sh::ShaderVariable *varying = output ? output : input;
  
              if (!ShouldSkipPackedVarying(*varying, packMode))
              {
                  collectVarying(*varying, ref, packMode, &uniqueFullNames);
                  continue;
              }
          }
  
          // If the varying is not used in the input, we know it is inactive, unless it's a separable
          // program, in which case the input shader may not exist in this program.
          if (!input && !isSeparableProgram)
          {
              if (!output->isBuiltIn())
              {
                  mInactiveVaryingMappedNames[ref.backShaderStage].push_back(output->mappedName);
              }
              continue;
          }
  
          // Keep Transform FB varyings in the merged list always.
          for (const std::string &tfVarying : tfVaryings)
          {
              collectTFVarying(tfVarying, ref, &uniqueFullNames);
          }
  
          if (input && !input->isBuiltIn() &&
              uniqueFullNames[ref.frontShaderStage].count(input->name) == 0)
          {
              mInactiveVaryingMappedNames[ref.frontShaderStage].push_back(input->mappedName);
          }
          if (output && !output->isBuiltIn() &&
              uniqueFullNames[ref.backShaderStage].count(output->name) == 0)
          {
              mInactiveVaryingMappedNames[ref.backShaderStage].push_back(output->mappedName);
          }
      }
  
      std::sort(mPackedVaryings.begin(), mPackedVaryings.end(), ComparePackedVarying);
  
      return packUserVaryings(infoLog, maxVaryingVectors, packMode, mPackedVaryings);
  }
  
  // See comment on packVarying.
  bool VaryingPacking::packUserVaryings(gl::InfoLog &infoLog,
                                        GLint maxVaryingVectors,
                                        PackMode packMode,
                                        const std::vector<PackedVarying> &packedVaryings)
  {
      clearRegisterMap();
      mRegisterMap.resize(maxVaryingVectors);
  
      // "Variables are packed into the registers one at a time so that they each occupy a contiguous
      // subrectangle. No splitting of variables is permitted."
      for (const PackedVarying &packedVarying : packedVaryings)
      {
          if (!packVaryingIntoRegisterMap(packMode, packedVarying))
          {
              ShaderType eitherStage = packedVarying.frontVarying.varying
                                           ? packedVarying.frontVarying.stage
                                           : packedVarying.backVarying.stage;
              infoLog << "Could not pack varying " << packedVarying.fullName(eitherStage);
  
              // TODO(jmadill): Implement more sophisticated component packing in D3D9.
              if (packMode == PackMode::ANGLE_NON_CONFORMANT_D3D9)
              {
                  infoLog << "Note: Additional non-conformant packing restrictions are enforced on "
                             "D3D9.";
              }
  
              return false;
          }
      }
  
      // Sort the packed register list
      std::sort(mRegisterList.begin(), mRegisterList.end());
  
      return true;
  }
  
  // ProgramVaryingPacking implementation.
  ProgramVaryingPacking::ProgramVaryingPacking() = default;
  
  ProgramVaryingPacking::~ProgramVaryingPacking() = default;
  
  const VaryingPacking &ProgramVaryingPacking::getInputPacking(ShaderType backShaderStage) const
  {
      ShaderType frontShaderStage = mBackToFrontStageMap[backShaderStage];
  
      // If there's a missing shader stage, return the compute shader packing which is always empty.
      if (frontShaderStage == ShaderType::InvalidEnum)
      {
          ASSERT(mVaryingPackings[ShaderType::Compute].getMaxSemanticIndex() == 0);
          return mVaryingPackings[ShaderType::Compute];
      }
  
      return mVaryingPackings[frontShaderStage];
  }
  
  const VaryingPacking &ProgramVaryingPacking::getOutputPacking(ShaderType frontShaderStage) const
  {
      return mVaryingPackings[frontShaderStage];
  }
  
  bool ProgramVaryingPacking::collectAndPackUserVaryings(InfoLog &infoLog,
                                                         const Caps &caps,
                                                         PackMode packMode,
                                                         const ShaderBitSet &attachedShadersMask,
                                                         const ProgramMergedVaryings &mergedVaryings,
                                                         const std::vector<std::string> &tfVaryings,
                                                         bool isSeparableProgram)
  {
      mBackToFrontStageMap.fill(ShaderType::InvalidEnum);
  
      ShaderBitSet attachedShaders = attachedShadersMask;
  
      ShaderType frontShaderStage       = attachedShaders.first();
      attachedShaders[frontShaderStage] = false;
  
      // Special case for start-after-vertex.
      if (frontShaderStage != ShaderType::Vertex)
      {
          ASSERT(isSeparableProgram);
  
          ShaderType emulatedFrontShaderStage = ShaderType::Vertex;
          ShaderType backShaderStage          = frontShaderStage;
  
          if (!mVaryingPackings[emulatedFrontShaderStage].collectAndPackUserVaryings(
                  infoLog, GetMaxShaderInputVectors(caps, backShaderStage), packMode,
                  ShaderType::InvalidEnum, backShaderStage, mergedVaryings, tfVaryings,
                  isSeparableProgram))
          {
              return false;
          }
          mBackToFrontStageMap[backShaderStage] = emulatedFrontShaderStage;
      }
  
      // Process input/output shader pairs.
      for (ShaderType backShaderStage : attachedShaders)
      {
          GLint maxVaryingVectors;
          if (frontShaderStage == ShaderType::Vertex && backShaderStage == ShaderType::Fragment)
          {
              maxVaryingVectors = caps.maxVaryingVectors;
          }
          else
          {
              GLint outputVaryingsMax = GetMaxShaderOutputVectors(caps, frontShaderStage);
              GLint inputVaryingsMax  = GetMaxShaderInputVectors(caps, backShaderStage);
              maxVaryingVectors       = std::min(inputVaryingsMax, outputVaryingsMax);
          }
  
          ASSERT(maxVaryingVectors > 0 && maxVaryingVectors < std::numeric_limits<GLint>::max());
  
          if (!mVaryingPackings[frontShaderStage].collectAndPackUserVaryings(
                  infoLog, maxVaryingVectors, packMode, frontShaderStage, backShaderStage,
                  mergedVaryings, tfVaryings, isSeparableProgram))
          {
              return false;
          }
  
          mBackToFrontStageMap[backShaderStage] = frontShaderStage;
          frontShaderStage                      = backShaderStage;
      }
  
      // Special case for stop-before-fragment.
      if (frontShaderStage != ShaderType::Fragment)
      {
          ASSERT(isSeparableProgram);
  
          if (!mVaryingPackings[frontShaderStage].collectAndPackUserVaryings(
                  infoLog, GetMaxShaderOutputVectors(caps, frontShaderStage), packMode,
                  frontShaderStage, ShaderType::InvalidEnum, mergedVaryings, tfVaryings,
                  isSeparableProgram))
          {
              return false;
          }
  
          ShaderType emulatedBackShaderStage            = ShaderType::Fragment;
          mBackToFrontStageMap[emulatedBackShaderStage] = frontShaderStage;
      }
  
      return true;
  }
  
  ProgramMergedVaryings GetMergedVaryingsFromShaders(const HasAttachedShaders &programOrPipeline)
  {
      Shader *frontShader = nullptr;
      ProgramMergedVaryings merged;
  
      for (ShaderType shaderType : kAllGraphicsShaderTypes)
      {
          Shader *backShader = programOrPipeline.getAttachedShader(shaderType);
          if (!backShader)
          {
              continue;
          }
  
          ASSERT(backShader->getType() != ShaderType::Compute);
  
          // Add outputs. These are always unmatched since we walk shader stages sequentially.
          for (const sh::ShaderVariable &frontVarying : backShader->getOutputVaryings())
          {
              ProgramVaryingRef ref;
              ref.frontShader      = &frontVarying;
              ref.frontShaderStage = backShader->getType();
              merged.push_back(ref);
          }
  
          if (!frontShader)
          {
              // If this is our first shader stage, and not a VS, we might have unmatched inputs.
              for (const sh::ShaderVariable &backVarying : backShader->getInputVaryings())
              {
                  ProgramVaryingRef ref;
                  ref.backShader      = &backVarying;
                  ref.backShaderStage = backShader->getType();
                  merged.push_back(ref);
              }
          }
          else
          {
              // Match inputs with the prior shader stage outputs.
              for (const sh::ShaderVariable &backVarying : backShader->getInputVaryings())
              {
                  bool found = false;
                  for (ProgramVaryingRef &ref : merged)
                  {
                      if (ref.frontShader && ref.frontShaderStage == frontShader->getType() &&
                          InterfaceVariablesMatch(*ref.frontShader, backVarying))
                      {
                          ASSERT(ref.backShader == nullptr);
  
                          ref.backShader      = &backVarying;
                          ref.backShaderStage = backShader->getType();
                          found               = true;
                          break;
                      }
                  }
  
                  // Some outputs are never matched, e.g. some builtin variables.
                  if (!found)
                  {
                      ProgramVaryingRef ref;
                      ref.backShader      = &backVarying;
                      ref.backShaderStage = backShader->getType();
                      merged.push_back(ref);
                  }
              }
          }
  
          // Save the current back shader to use as the next front shader.
          frontShader = backShader;
      }
  
      return merged;
  }
  }  // namespace gl