glslang/MachineIndependent/linkValidate.cpp

   1 //
   2 // Copyright (C) 2013 LunarG, Inc.
   3 // Copyright (C) 2017 ARM Limited.
   4 // Copyright (C) 2015-2018 Google, Inc.
   5 //
   6 // All rights reserved.
   7 //
   8 // Redistribution and use in source and binary forms, with or without
   9 // modification, are permitted provided that the following conditions
  10 // are met:
  11 //
  12 //    Redistributions of source code must retain the above copyright
  13 //    notice, this list of conditions and the following disclaimer.
  14 //
  15 //    Redistributions in binary form must reproduce the above
  16 //    copyright notice, this list of conditions and the following
  17 //    disclaimer in the documentation and/or other materials provided
  18 //    with the distribution.
  19 //
  20 //    Neither the name of 3Dlabs Inc. Ltd. nor the names of its
  21 //    contributors may be used to endorse or promote products derived
  22 //    from this software without specific prior written permission.
  23 //
  24 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  25 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  26 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  27 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  28 // COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  29 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  30 // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  31 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  32 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  33 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  34 // ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  35 // POSSIBILITY OF SUCH DAMAGE.
  36 //
  37
  38 //
  39 // Do link-time merging and validation of intermediate representations.
  40 //
  41 // Basic model is that during compilation, each compilation unit (shader) is
  42 // compiled into one TIntermediate instance.  Then, at link time, multiple
  43 // units for the same stage can be merged together, which can generate errors.
  44 // Then, after all merging, a single instance of TIntermediate represents
  45 // the whole stage.  A final error check can be done on the resulting stage,
  46 // even if no merging was done (i.e., the stage was only one compilation unit).
  47 //
  48
  49 #include "localintermediate.h"
  50 #include "../Include/InfoSink.h"
  51 #include "SymbolTable.h"
  52
  53 namespace glslang {
  54
  55 //
  56 // Link-time error emitter.
  57 //
  58 void TIntermediate::error(TInfoSink& infoSink, const char* message, EShLanguage unitStage)
  59 {
  60 #ifndef GLSLANG_WEB
  61     infoSink.info.prefix(EPrefixError);
  62     if (unitStage < EShLangCount)
  63         infoSink.info << "Linking " << StageName(getStage()) << " and " << StageName(unitStage) << " stages: " << message << "\n";
  64     else
  65         infoSink.info << "Linking " << StageName(language) << " stage: " << message << "\n";
  66 #endif
  67
  68     ++numErrors;
  69 }
  70
  71 // Link-time warning.
  72 void TIntermediate::warn(TInfoSink& infoSink, const char* message, EShLanguage unitStage)
  73 {
  74 #ifndef GLSLANG_WEB
  75     infoSink.info.prefix(EPrefixWarning);
  76     if (unitStage < EShLangCount)
  77         infoSink.info << "Linking " << StageName(language) << " and " << StageName(unitStage) << " stages: " << message << "\n";
  78     else
  79         infoSink.info << "Linking " << StageName(language) << " stage: " << message << "\n";
  80 #endif
  81 }
  82
  83 // TODO: 4.4 offset/align:  "Two blocks linked together in the same program with the same block
  84 // name must have the exact same set of members qualified with offset and their integral-constant
  85 // expression values must be the same, or a link-time error results."
  86
  87 //
  88 // Merge the information from 'unit' into 'this'
  89 //
  90 void TIntermediate::merge(TInfoSink& infoSink, TIntermediate& unit)
  91 {
  92 #if !defined(GLSLANG_WEB) && !defined(GLSLANG_ANGLE)
  93     mergeCallGraphs(infoSink, unit);
  94     mergeModes(infoSink, unit);
  95     mergeTrees(infoSink, unit);
  96 #endif
  97 }
  98
  99 //
 100 // check that link objects between stages
 101 //
 102 void TIntermediate::mergeUniformObjects(TInfoSink& infoSink, TIntermediate& unit) {
 103     if (unit.treeRoot == nullptr || treeRoot == nullptr)
 104         return;
 105
 106     // Get the linker-object lists
 107     TIntermSequence& linkerObjects = findLinkerObjects()->getSequence();
 108     TIntermSequence unitLinkerObjects = unit.findLinkerObjects()->getSequence();
 109
 110     // filter unitLinkerObjects to only contain uniforms
 111     auto end = std::remove_if(unitLinkerObjects.begin(), unitLinkerObjects.end(),
 112         [](TIntermNode* node) {return node->getAsSymbolNode()->getQualifier().storage != EvqUniform &&
 113                                       node->getAsSymbolNode()->getQualifier().storage != EvqBuffer; });
 114     unitLinkerObjects.resize(end - unitLinkerObjects.begin());
 115
 116     // merge uniforms and do error checking
 117     bool mergeExistingOnly = false;
 118     mergeGlobalUniformBlocks(infoSink, unit, mergeExistingOnly);
 119     mergeLinkerObjects(infoSink, linkerObjects, unitLinkerObjects, unit.getStage());
 120 }
 121
 122 //
 123 // do error checking on the shader boundary in / out vars
 124 //
 125 void TIntermediate::checkStageIO(TInfoSink& infoSink, TIntermediate& unit) {
 126     if (unit.treeRoot == nullptr || treeRoot == nullptr)
 127         return;
 128
 129     // Get copies of the linker-object lists
 130     TIntermSequence linkerObjects = findLinkerObjects()->getSequence();
 131     TIntermSequence unitLinkerObjects = unit.findLinkerObjects()->getSequence();
 132
 133     // filter linkerObjects to only contain out variables
 134     auto end = std::remove_if(linkerObjects.begin(), linkerObjects.end(),
 135         [](TIntermNode* node) {return node->getAsSymbolNode()->getQualifier().storage != EvqVaryingOut; });
 136     linkerObjects.resize(end - linkerObjects.begin());
 137
 138     // filter unitLinkerObjects to only contain in variables
 139     auto unitEnd = std::remove_if(unitLinkerObjects.begin(), unitLinkerObjects.end(),
 140         [](TIntermNode* node) {return node->getAsSymbolNode()->getQualifier().storage != EvqVaryingIn; });
 141     unitLinkerObjects.resize(unitEnd - unitLinkerObjects.begin());
 142
 143     // do matching and error checking
 144     mergeLinkerObjects(infoSink, linkerObjects, unitLinkerObjects, unit.getStage());
 145
 146     // TODO: final check; make sure that any statically used `in` have matching `out` written to
 147 }
 148
 149 void TIntermediate::mergeCallGraphs(TInfoSink& infoSink, TIntermediate& unit)
 150 {
 151     if (unit.getNumEntryPoints() > 0) {
 152         if (getNumEntryPoints() > 0)
 153             error(infoSink, "can't handle multiple entry points per stage");
 154         else {
 155             entryPointName = unit.getEntryPointName();
 156             entryPointMangledName = unit.getEntryPointMangledName();
 157         }
 158     }
 159     numEntryPoints += unit.getNumEntryPoints();
 160
 161     callGraph.insert(callGraph.end(), unit.callGraph.begin(), unit.callGraph.end());
 162 }
 163
 164 #if !defined(GLSLANG_WEB) && !defined(GLSLANG_ANGLE)
 165
 166 #define MERGE_MAX(member) member = std::max(member, unit.member)
 167 #define MERGE_TRUE(member) if (unit.member) member = unit.member;
 168
 169 void TIntermediate::mergeModes(TInfoSink& infoSink, TIntermediate& unit)
 170 {
 171     if (language != unit.language)
 172         error(infoSink, "stages must match when linking into a single stage");
 173
 174     if (getSource() == EShSourceNone)
 175         setSource(unit.getSource());
 176     if (getSource() != unit.getSource())
 177         error(infoSink, "can't link compilation units from different source languages");
 178
 179     if (treeRoot == nullptr) {
 180         profile = unit.profile;
 181         version = unit.version;
 182         requestedExtensions = unit.requestedExtensions;
 183     } else {
 184         if ((isEsProfile()) != (unit.isEsProfile()))
 185             error(infoSink, "Cannot cross link ES and desktop profiles");
 186         else if (unit.profile == ECompatibilityProfile)
 187             profile = ECompatibilityProfile;
 188         version = std::max(version, unit.version);
 189         requestedExtensions.insert(unit.requestedExtensions.begin(), unit.requestedExtensions.end());
 190     }
 191
 192     MERGE_MAX(spvVersion.spv);
 193     MERGE_MAX(spvVersion.vulkanGlsl);
 194     MERGE_MAX(spvVersion.vulkan);
 195     MERGE_MAX(spvVersion.openGl);
 196     MERGE_TRUE(spvVersion.vulkanRelaxed);
 197
 198     numErrors += unit.getNumErrors();
 199     // Only one push_constant is allowed, mergeLinkerObjects() will ensure the push_constant
 200     // is the same for all units.
 201     if (numPushConstants > 1 || unit.numPushConstants > 1)
 202         error(infoSink, "Only one push_constant block is allowed per stage");
 203     numPushConstants = std::min(numPushConstants + unit.numPushConstants, 1);
 204
 205     if (unit.invocations != TQualifier::layoutNotSet) {
 206         if (invocations == TQualifier::layoutNotSet)
 207             invocations = unit.invocations;
 208         else if (invocations != unit.invocations)
 209             error(infoSink, "number of invocations must match between compilation units");
 210     }
 211
 212     if (vertices == TQualifier::layoutNotSet)
 213         vertices = unit.vertices;
 214     else if (unit.vertices != TQualifier::layoutNotSet && vertices != unit.vertices) {
 215         if (language == EShLangGeometry || language == EShLangMesh)
 216             error(infoSink, "Contradictory layout max_vertices values");
 217         else if (language == EShLangTessControl)
 218             error(infoSink, "Contradictory layout vertices values");
 219         else
 220             assert(0);
 221     }
 222     if (primitives == TQualifier::layoutNotSet)
 223         primitives = unit.primitives;
 224     else if (primitives != unit.primitives) {
 225         if (language == EShLangMesh)
 226             error(infoSink, "Contradictory layout max_primitives values");
 227         else
 228             assert(0);
 229     }
 230
 231     if (inputPrimitive == ElgNone)
 232         inputPrimitive = unit.inputPrimitive;
 233     else if (unit.inputPrimitive != ElgNone && inputPrimitive != unit.inputPrimitive)
 234         error(infoSink, "Contradictory input layout primitives");
 235
 236     if (outputPrimitive == ElgNone)
 237         outputPrimitive = unit.outputPrimitive;
 238     else if (unit.outputPrimitive != ElgNone && outputPrimitive != unit.outputPrimitive)
 239         error(infoSink, "Contradictory output layout primitives");
 240
 241     if (originUpperLeft != unit.originUpperLeft || pixelCenterInteger != unit.pixelCenterInteger)
 242         error(infoSink, "gl_FragCoord redeclarations must match across shaders");
 243
 244     if (vertexSpacing == EvsNone)
 245         vertexSpacing = unit.vertexSpacing;
 246     else if (vertexSpacing != unit.vertexSpacing)
 247         error(infoSink, "Contradictory input vertex spacing");
 248
 249     if (vertexOrder == EvoNone)
 250         vertexOrder = unit.vertexOrder;
 251     else if (vertexOrder != unit.vertexOrder)
 252         error(infoSink, "Contradictory triangle ordering");
 253
 254     MERGE_TRUE(pointMode);
 255
 256     for (int i = 0; i < 3; ++i) {
 257         if (unit.localSizeNotDefault[i]) {
 258             if (!localSizeNotDefault[i]) {
 259                 localSize[i] = unit.localSize[i];
 260                 localSizeNotDefault[i] = true;
 261             }
 262             else if (localSize[i] != unit.localSize[i])
 263                 error(infoSink, "Contradictory local size");
 264         }
 265
 266         if (localSizeSpecId[i] == TQualifier::layoutNotSet)
 267             localSizeSpecId[i] = unit.localSizeSpecId[i];
 268         else if (localSizeSpecId[i] != unit.localSizeSpecId[i])
 269             error(infoSink, "Contradictory local size specialization ids");
 270     }
 271
 272     MERGE_TRUE(earlyFragmentTests);
 273     MERGE_TRUE(postDepthCoverage);
 274
 275     if (depthLayout == EldNone)
 276         depthLayout = unit.depthLayout;
 277     else if (depthLayout != unit.depthLayout)
 278         error(infoSink, "Contradictory depth layouts");
 279
 280     MERGE_TRUE(depthReplacing);
 281     MERGE_TRUE(hlslFunctionality1);
 282
 283     blendEquations |= unit.blendEquations;
 284
 285     MERGE_TRUE(xfbMode);
 286
 287     for (size_t b = 0; b < xfbBuffers.size(); ++b) {
 288         if (xfbBuffers[b].stride == TQualifier::layoutXfbStrideEnd)
 289             xfbBuffers[b].stride = unit.xfbBuffers[b].stride;
 290         else if (xfbBuffers[b].stride != unit.xfbBuffers[b].stride)
 291             error(infoSink, "Contradictory xfb_stride");
 292         xfbBuffers[b].implicitStride = std::max(xfbBuffers[b].implicitStride, unit.xfbBuffers[b].implicitStride);
 293         if (unit.xfbBuffers[b].contains64BitType)
 294             xfbBuffers[b].contains64BitType = true;
 295         if (unit.xfbBuffers[b].contains32BitType)
 296             xfbBuffers[b].contains32BitType = true;
 297         if (unit.xfbBuffers[b].contains16BitType)
 298             xfbBuffers[b].contains16BitType = true;
 299         // TODO: 4.4 link: enhanced layouts: compare ranges
 300     }
 301
 302     MERGE_TRUE(multiStream);
 303     MERGE_TRUE(layoutOverrideCoverage);
 304     MERGE_TRUE(geoPassthroughEXT);
 305
 306     for (unsigned int i = 0; i < unit.shiftBinding.size(); ++i) {
 307         if (unit.shiftBinding[i] > 0)
 308             setShiftBinding((TResourceType)i, unit.shiftBinding[i]);
 309     }
 310
 311     for (unsigned int i = 0; i < unit.shiftBindingForSet.size(); ++i) {
 312         for (auto it = unit.shiftBindingForSet[i].begin(); it != unit.shiftBindingForSet[i].end(); ++it)
 313             setShiftBindingForSet((TResourceType)i, it->second, it->first);
 314     }
 315
 316     resourceSetBinding.insert(resourceSetBinding.end(), unit.resourceSetBinding.begin(), unit.resourceSetBinding.end());
 317
 318     MERGE_TRUE(autoMapBindings);
 319     MERGE_TRUE(autoMapLocations);
 320     MERGE_TRUE(invertY);
 321     MERGE_TRUE(dxPositionW);
 322     MERGE_TRUE(debugInfo);
 323     MERGE_TRUE(flattenUniformArrays);
 324     MERGE_TRUE(useUnknownFormat);
 325     MERGE_TRUE(hlslOffsets);
 326     MERGE_TRUE(useStorageBuffer);
 327     MERGE_TRUE(invariantAll);
 328     MERGE_TRUE(hlslIoMapping);
 329
 330     // TODO: sourceFile
 331     // TODO: sourceText
 332     // TODO: processes
 333
 334     MERGE_TRUE(needToLegalize);
 335     MERGE_TRUE(binaryDoubleOutput);
 336     MERGE_TRUE(usePhysicalStorageBuffer);
 337 }
 338
 339 //
 340 // Merge the 'unit' AST into 'this' AST.
 341 // That includes rationalizing the unique IDs, which were set up independently,
 342 // and might have overlaps that are not the same symbol, or might have different
 343 // IDs for what should be the same shared symbol.
 344 //
 345 void TIntermediate::mergeTrees(TInfoSink& infoSink, TIntermediate& unit)
 346 {
 347     if (unit.treeRoot == nullptr)
 348         return;
 349
 350     if (treeRoot == nullptr) {
 351         treeRoot = unit.treeRoot;
 352         return;
 353     }
 354
 355     // Getting this far means we have two existing trees to merge...
 356     numShaderRecordBlocks += unit.numShaderRecordBlocks;
 357     numTaskNVBlocks += unit.numTaskNVBlocks;
 358
 359     // Get the top-level globals of each unit
 360     TIntermSequence& globals = treeRoot->getAsAggregate()->getSequence();
 361     TIntermSequence& unitGlobals = unit.treeRoot->getAsAggregate()->getSequence();
 362
 363     // Get the linker-object lists
 364     TIntermSequence& linkerObjects = findLinkerObjects()->getSequence();
 365     const TIntermSequence& unitLinkerObjects = unit.findLinkerObjects()->getSequence();
 366
 367     // Map by global name to unique ID to rationalize the same object having
 368     // differing IDs in different trees.
 369     TIdMaps idMaps;
 370     long long idShift;
 371     seedIdMap(idMaps, idShift);
 372     remapIds(idMaps, idShift + 1, unit);
 373
 374     mergeBodies(infoSink, globals, unitGlobals);
 375     bool mergeExistingOnly = false;
 376     mergeGlobalUniformBlocks(infoSink, unit, mergeExistingOnly);
 377     mergeLinkerObjects(infoSink, linkerObjects, unitLinkerObjects, unit.getStage());
 378     ioAccessed.insert(unit.ioAccessed.begin(), unit.ioAccessed.end());
 379 }
 380
 381 #endif
 382
 383 static const TString& getNameForIdMap(TIntermSymbol* symbol)
 384 {
 385     TShaderInterface si = symbol->getType().getShaderInterface();
 386     if (si == EsiNone)
 387         return symbol->getName();
 388     else
 389         return symbol->getType().getTypeName();
 390 }
 391
 392
 393
 394 // Traverser that seeds an ID map with all built-ins, and tracks the
 395 // maximum ID used, currently using (maximum ID + 1) as new symbol id shift seed.
 396 // Level id will keep same after shifting.
 397 // (It would be nice to put this in a function, but that causes warnings
 398 // on having no bodies for the copy-constructor/operator=.)
 399 class TBuiltInIdTraverser : public TIntermTraverser {
 400 public:
 401     TBuiltInIdTraverser(TIdMaps& idMaps) : idMaps(idMaps), idShift(0) { }
 402     // If it's a built in, add it to the map.
 403     virtual void visitSymbol(TIntermSymbol* symbol)
 404     {
 405         const TQualifier& qualifier = symbol->getType().getQualifier();
 406         if (qualifier.builtIn != EbvNone) {
 407             TShaderInterface si = symbol->getType().getShaderInterface();
 408             idMaps[si][getNameForIdMap(symbol)] = symbol->getId();
 409         }
 410         idShift = (symbol->getId() & ~TSymbolTable::uniqueIdMask) |
 411                 std::max(idShift & TSymbolTable::uniqueIdMask,
 412                          symbol->getId() & TSymbolTable::uniqueIdMask);
 413     }
 414     long long getIdShift() const { return idShift; }
 415 protected:
 416     TBuiltInIdTraverser(TBuiltInIdTraverser&);
 417     TBuiltInIdTraverser& operator=(TBuiltInIdTraverser&);
 418     TIdMaps& idMaps;
 419     long long idShift;
 420 };
 421
 422 // Traverser that seeds an ID map with non-builtins.
 423 // (It would be nice to put this in a function, but that causes warnings
 424 // on having no bodies for the copy-constructor/operator=.)
 425 class TUserIdTraverser : public TIntermTraverser {
 426 public:
 427     TUserIdTraverser(TIdMaps& idMaps) : idMaps(idMaps) { }
 428     // If its a non-built-in global, add it to the map.
 429     virtual void visitSymbol(TIntermSymbol* symbol)
 430     {
 431         const TQualifier& qualifier = symbol->getType().getQualifier();
 432         if (qualifier.builtIn == EbvNone) {
 433             TShaderInterface si = symbol->getType().getShaderInterface();
 434             idMaps[si][getNameForIdMap(symbol)] = symbol->getId();
 435         }
 436     }
 437
 438 protected:
 439     TUserIdTraverser(TUserIdTraverser&);
 440     TUserIdTraverser& operator=(TUserIdTraverser&);
 441     TIdMaps& idMaps; // over biggest id
 442 };
 443
 444 // Initialize the the ID map with what we know of 'this' AST.
 445 void TIntermediate::seedIdMap(TIdMaps& idMaps, long long& idShift)
 446 {
 447     // all built-ins everywhere need to align on IDs and contribute to the max ID
 448     TBuiltInIdTraverser builtInIdTraverser(idMaps);
 449     treeRoot->traverse(&builtInIdTraverser);
 450     idShift = builtInIdTraverser.getIdShift() & TSymbolTable::uniqueIdMask;
 451
 452     // user variables in the linker object list need to align on ids
 453     TUserIdTraverser userIdTraverser(idMaps);
 454     findLinkerObjects()->traverse(&userIdTraverser);
 455 }
 456
 457 // Traverser to map an AST ID to what was known from the seeding AST.
 458 // (It would be nice to put this in a function, but that causes warnings
 459 // on having no bodies for the copy-constructor/operator=.)
 460 class TRemapIdTraverser : public TIntermTraverser {
 461 public:
 462     TRemapIdTraverser(const TIdMaps& idMaps, long long idShift) : idMaps(idMaps), idShift(idShift) { }
 463     // Do the mapping:
 464     //  - if the same symbol, adopt the 'this' ID
 465     //  - otherwise, ensure a unique ID by shifting to a new space
 466     virtual void visitSymbol(TIntermSymbol* symbol)
 467     {
 468         const TQualifier& qualifier = symbol->getType().getQualifier();
 469         bool remapped = false;
 470         if (qualifier.isLinkable() || qualifier.builtIn != EbvNone) {
 471             TShaderInterface si = symbol->getType().getShaderInterface();
 472             auto it = idMaps[si].find(getNameForIdMap(symbol));
 473             if (it != idMaps[si].end()) {
 474                 uint64_t id = (symbol->getId() & ~TSymbolTable::uniqueIdMask) |
 475                     (it->second & TSymbolTable::uniqueIdMask);
 476                 symbol->changeId(id);
 477                 remapped = true;
 478             }
 479         }
 480         if (!remapped)
 481             symbol->changeId(symbol->getId() + idShift);
 482     }
 483 protected:
 484     TRemapIdTraverser(TRemapIdTraverser&);
 485     TRemapIdTraverser& operator=(TRemapIdTraverser&);
 486     const TIdMaps& idMaps;
 487     long long idShift;
 488 };
 489
 490 void TIntermediate::remapIds(const TIdMaps& idMaps, long long idShift, TIntermediate& unit)
 491 {
 492     // Remap all IDs to either share or be unique, as dictated by the idMap and idShift.
 493     TRemapIdTraverser idTraverser(idMaps, idShift);
 494     unit.getTreeRoot()->traverse(&idTraverser);
 495 }
 496
 497 //
 498 // Merge the function bodies and global-level initializers from unitGlobals into globals.
 499 // Will error check duplication of function bodies for the same signature.
 500 //
 501 void TIntermediate::mergeBodies(TInfoSink& infoSink, TIntermSequence& globals, const TIntermSequence& unitGlobals)
 502 {
 503     // TODO: link-time performance: Processing in alphabetical order will be faster
 504
 505     // Error check the global objects, not including the linker objects
 506     for (unsigned int child = 0; child < globals.size() - 1; ++child) {
 507         for (unsigned int unitChild = 0; unitChild < unitGlobals.size() - 1; ++unitChild) {
 508             TIntermAggregate* body = globals[child]->getAsAggregate();
 509             TIntermAggregate* unitBody = unitGlobals[unitChild]->getAsAggregate();
 510             if (body && unitBody && body->getOp() == EOpFunction && unitBody->getOp() == EOpFunction && body->getName() == unitBody->getName()) {
 511                 error(infoSink, "Multiple function bodies in multiple compilation units for the same signature in the same stage:");
 512                 infoSink.info << "    " << globals[child]->getAsAggregate()->getName() << "\n";
 513             }
 514         }
 515     }
 516
 517     // Merge the global objects, just in front of the linker objects
 518     globals.insert(globals.end() - 1, unitGlobals.begin(), unitGlobals.end() - 1);
 519 }
 520
 521 static inline bool isSameInterface(TIntermSymbol* symbol, EShLanguage stage, TIntermSymbol* unitSymbol, EShLanguage unitStage) {
 522     return // 1) same stage and same shader interface
 523         (stage == unitStage && symbol->getType().getShaderInterface() == unitSymbol->getType().getShaderInterface()) ||
 524         // 2) accross stages and both are uniform or buffer
 525         (symbol->getQualifier().storage == EvqUniform  && unitSymbol->getQualifier().storage == EvqUniform) ||
 526         (symbol->getQualifier().storage == EvqBuffer   && unitSymbol->getQualifier().storage == EvqBuffer) ||
 527         // 3) in/out matched across stage boundary
 528         (stage < unitStage && symbol->getQualifier().storage == EvqVaryingOut  && unitSymbol->getQualifier().storage == EvqVaryingIn) ||
 529         (unitStage < stage && symbol->getQualifier().storage == EvqVaryingIn && unitSymbol->getQualifier().storage == EvqVaryingOut);
 530 }
 531
 532 //
 533 // Global Unfiform block stores any default uniforms (i.e. uniforms without a block)
 534 // If two linked stages declare the same member, they are meant to be the same uniform
 535 // and need to be in the same block
 536 // merge the members of different stages to allow them to be linked properly
 537 // as a single block
 538 //
 539 void TIntermediate::mergeGlobalUniformBlocks(TInfoSink& infoSink, TIntermediate& unit, bool mergeExistingOnly)
 540 {
 541     TIntermSequence& linkerObjects = findLinkerObjects()->getSequence();
 542     TIntermSequence& unitLinkerObjects = unit.findLinkerObjects()->getSequence();
 543
 544     // build lists of default blocks from the intermediates
 545     TIntermSequence defaultBlocks;
 546     TIntermSequence unitDefaultBlocks;
 547
 548     auto filter = [](TIntermSequence& list, TIntermNode* node) {
 549         if (node->getAsSymbolNode()->getQualifier().defaultBlock) {
 550             list.push_back(node);
 551         }
 552     };
 553
 554     std::for_each(linkerObjects.begin(), linkerObjects.end(),
 555         [&defaultBlocks, &filter](TIntermNode* node) {
 556             filter(defaultBlocks, node);
 557         });
 558     std::for_each(unitLinkerObjects.begin(), unitLinkerObjects.end(),
 559         [&unitDefaultBlocks, &filter](TIntermNode* node) {
 560             filter(unitDefaultBlocks, node);
 561     });
 562
 563     auto itUnitBlock = unitDefaultBlocks.begin();
 564     for (; itUnitBlock != unitDefaultBlocks.end(); itUnitBlock++) {
 565
 566         bool add = !mergeExistingOnly;
 567         auto itBlock = defaultBlocks.begin();
 568
 569         for (; itBlock != defaultBlocks.end(); itBlock++) {
 570             TIntermSymbol* block = (*itBlock)->getAsSymbolNode();
 571             TIntermSymbol* unitBlock = (*itUnitBlock)->getAsSymbolNode();
 572
 573             assert(block && unitBlock);
 574
 575             // if the two default blocks match, then merge their definitions
 576             if (block->getType().getTypeName() == unitBlock->getType().getTypeName() &&
 577                 block->getQualifier().storage == unitBlock->getQualifier().storage) {
 578                 add = false;
 579                 mergeBlockDefinitions(infoSink, block, unitBlock, &unit);
 580             }
 581         }
 582         if (add) {
 583             // push back on original list; won't change the size of the list we're iterating over
 584             linkerObjects.push_back(*itUnitBlock);
 585         }
 586     }
 587 }
 588
 589 void TIntermediate::mergeBlockDefinitions(TInfoSink& infoSink, TIntermSymbol* block, TIntermSymbol* unitBlock, TIntermediate* unit) {
 590
 591     if (block->getType().getTypeName() != unitBlock->getType().getTypeName() ||
 592         block->getType().getBasicType() != unitBlock->getType().getBasicType() ||
 593         block->getQualifier().storage != unitBlock->getQualifier().storage ||
 594         block->getQualifier().layoutSet != unitBlock->getQualifier().layoutSet) {
 595         // different block names likely means different blocks
 596         return;
 597     }
 598
 599     // merge the struct
 600     // order of declarations doesn't matter and they matched based on member name
 601     TTypeList* memberList = block->getType().getWritableStruct();
 602     TTypeList* unitMemberList = unitBlock->getType().getWritableStruct();
 603
 604     // keep track of which members have changed position
 605     // so we don't have to search the array again
 606     std::map<unsigned int, unsigned int> memberIndexUpdates;
 607
 608     size_t memberListStartSize = memberList->size();
 609     for (unsigned int i = 0; i < unitMemberList->size(); ++i) {
 610         bool merge = true;
 611         for (unsigned int j = 0; j < memberListStartSize; ++j) {
 612             if ((*memberList)[j].type->getFieldName() == (*unitMemberList)[i].type->getFieldName()) {
 613                 merge = false;
 614                 const TType* memberType = (*memberList)[j].type;
 615                 const TType* unitMemberType = (*unitMemberList)[i].type;
 616
 617                 // compare types
 618                 // don't need as many checks as when merging symbols, since
 619                 // initializers and most qualifiers are stripped when the member is moved into the block
 620                 if ((*memberType) != (*unitMemberType)) {
 621                     error(infoSink, "Types must match:");
 622                     infoSink.info << "    " << memberType->getFieldName() << ": ";
 623                     infoSink.info << "\"" << memberType->getCompleteString() << "\" versus ";
 624                     infoSink.info << "\"" << unitMemberType->getCompleteString() << "\"\n";
 625                 }
 626
 627                 memberIndexUpdates[i] = j;
 628             }
 629         }
 630         if (merge) {
 631             memberList->push_back((*unitMemberList)[i]);
 632             memberIndexUpdates[i] = (unsigned int)memberList->size() - 1;
 633         }
 634     }
 635
 636     // update symbol node in unit tree,
 637     // and other nodes that may reference it
 638     class TMergeBlockTraverser : public TIntermTraverser {
 639     public:
 640         TMergeBlockTraverser(const TIntermSymbol* newSym)
 641             : newSymbol(newSym), unitType(nullptr), unit(nullptr), memberIndexUpdates(nullptr)
 642         {
 643         }
 644         TMergeBlockTraverser(const TIntermSymbol* newSym, const glslang::TType* unitType, glslang::TIntermediate* unit,
 645                              const std::map<unsigned int, unsigned int>* memberIdxUpdates)
 646             : TIntermTraverser(false, true), newSymbol(newSym), unitType(unitType), unit(unit), memberIndexUpdates(memberIdxUpdates)
 647         {
 648         }
 649         virtual ~TMergeBlockTraverser() {}
 650
 651         const TIntermSymbol* newSymbol;
 652         const glslang::TType* unitType; // copy of original type
 653         glslang::TIntermediate* unit;   // intermediate that is being updated
 654         const std::map<unsigned int, unsigned int>* memberIndexUpdates;
 655
 656         virtual void visitSymbol(TIntermSymbol* symbol)
 657         {
 658             if (newSymbol->getAccessName() == symbol->getAccessName() &&
 659                 newSymbol->getQualifier().getBlockStorage() == symbol->getQualifier().getBlockStorage()) {
 660                 // Each symbol node may have a local copy of the block structure.
 661                 // Update those structures to match the new one post-merge
 662                 *(symbol->getWritableType().getWritableStruct()) = *(newSymbol->getType().getStruct());
 663             }
 664         }
 665
 666         virtual bool visitBinary(TVisit, glslang::TIntermBinary* node)
 667         {
 668             if (!unit || !unitType || !memberIndexUpdates || memberIndexUpdates->empty())
 669                 return true;
 670
 671             if (node->getOp() == EOpIndexDirectStruct && node->getLeft()->getType() == *unitType) {
 672                 // this is a dereference to a member of the block since the
 673                 // member list changed, need to update this to point to the
 674                 // right index
 675                 assert(node->getRight()->getAsConstantUnion());
 676
 677                 glslang::TIntermConstantUnion* constNode = node->getRight()->getAsConstantUnion();
 678                 unsigned int memberIdx = constNode->getConstArray()[0].getUConst();
 679                 unsigned int newIdx = memberIndexUpdates->at(memberIdx);
 680                 TIntermTyped* newConstNode = unit->addConstantUnion(newIdx, node->getRight()->getLoc());
 681
 682                 node->setRight(newConstNode);
 683                 delete constNode;
 684
 685                 return true;
 686             }
 687             return true;
 688         }
 689     };
 690
 691     // 'this' may have symbols that are using the old block structure, so traverse the tree to update those
 692     // in 'visitSymbol'
 693     TMergeBlockTraverser finalLinkTraverser(block);
 694     getTreeRoot()->traverse(&finalLinkTraverser);
 695
 696     // The 'unit' intermediate needs the block structures update, but also structure entry indices
 697     // may have changed from the old block to the new one that it was merged into, so update those
 698     // in 'visitBinary'
 699     TType unitType;
 700     unitType.shallowCopy(unitBlock->getType());
 701     TMergeBlockTraverser unitFinalLinkTraverser(block, &unitType, unit, &memberIndexUpdates);
 702     unit->getTreeRoot()->traverse(&unitFinalLinkTraverser);
 703
 704     // update the member list
 705     (*unitMemberList) = (*memberList);
 706 }
 707
 708 //
 709 // Merge the linker objects from unitLinkerObjects into linkerObjects.
 710 // Duplication is expected and filtered out, but contradictions are an error.
 711 //
 712 void TIntermediate::mergeLinkerObjects(TInfoSink& infoSink, TIntermSequence& linkerObjects, const TIntermSequence& unitLinkerObjects, EShLanguage unitStage)
 713 {
 714     // Error check and merge the linker objects (duplicates should not be created)
 715     std::size_t initialNumLinkerObjects = linkerObjects.size();
 716     for (unsigned int unitLinkObj = 0; unitLinkObj < unitLinkerObjects.size(); ++unitLinkObj) {
 717         bool merge = true;
 718         for (std::size_t linkObj = 0; linkObj < initialNumLinkerObjects; ++linkObj) {
 719             TIntermSymbol* symbol = linkerObjects[linkObj]->getAsSymbolNode();
 720             TIntermSymbol* unitSymbol = unitLinkerObjects[unitLinkObj]->getAsSymbolNode();
 721             assert(symbol && unitSymbol);
 722
 723             bool isSameSymbol = false;
 724             // If they are both blocks in the same shader interface,
 725             // match by the block-name, not the identifier name.
 726             if (symbol->getType().getBasicType() == EbtBlock && unitSymbol->getType().getBasicType() == EbtBlock) {
 727                 if (isSameInterface(symbol, getStage(), unitSymbol, unitStage)) {
 728                     isSameSymbol = symbol->getType().getTypeName() == unitSymbol->getType().getTypeName();
 729                 }
 730             }
 731             else if (symbol->getName() == unitSymbol->getName())
 732                 isSameSymbol = true;
 733
 734             if (isSameSymbol) {
 735                 // filter out copy
 736                 merge = false;
 737
 738                 // but if one has an initializer and the other does not, update
 739                 // the initializer
 740                 if (symbol->getConstArray().empty() && ! unitSymbol->getConstArray().empty())
 741                     symbol->setConstArray(unitSymbol->getConstArray());
 742
 743                 // Similarly for binding
 744                 if (! symbol->getQualifier().hasBinding() && unitSymbol->getQualifier().hasBinding())
 745                     symbol->getQualifier().layoutBinding = unitSymbol->getQualifier().layoutBinding;
 746
 747                 // Similarly for location
 748                 if (!symbol->getQualifier().hasLocation() && unitSymbol->getQualifier().hasLocation()) {
 749                     symbol->getQualifier().layoutLocation = unitSymbol->getQualifier().layoutLocation;
 750                 }
 751
 752                 // Update implicit array sizes
 753                 mergeImplicitArraySizes(symbol->getWritableType(), unitSymbol->getType());
 754
 755                 // Check for consistent types/qualification/initializers etc.
 756                 mergeErrorCheck(infoSink, *symbol, *unitSymbol, unitStage);
 757             }
 758             // If different symbols, verify they arn't push_constant since there can only be one per stage
 759             else if (symbol->getQualifier().isPushConstant() && unitSymbol->getQualifier().isPushConstant() && getStage() == unitStage)
 760                 error(infoSink, "Only one push_constant block is allowed per stage");
 761         }
 762         if (merge) {
 763             linkerObjects.push_back(unitLinkerObjects[unitLinkObj]);
 764
 765             // for anonymous blocks, check that their members don't conflict with other names
 766             if (unitLinkerObjects[unitLinkObj]->getAsSymbolNode()->getBasicType() == EbtBlock &&
 767                 IsAnonymous(unitLinkerObjects[unitLinkObj]->getAsSymbolNode()->getName())) {
 768                 for (std::size_t linkObj = 0; linkObj < initialNumLinkerObjects; ++linkObj) {
 769                     TIntermSymbol* symbol = linkerObjects[linkObj]->getAsSymbolNode();
 770                     TIntermSymbol* unitSymbol = unitLinkerObjects[unitLinkObj]->getAsSymbolNode();
 771                     assert(symbol && unitSymbol);
 772
 773                     auto checkName = [this, unitSymbol, &infoSink](const TString& name) {
 774                         for (unsigned int i = 0; i < unitSymbol->getType().getStruct()->size(); ++i) {
 775                             if (name == (*unitSymbol->getType().getStruct())[i].type->getFieldName()
 776                                 && !((*unitSymbol->getType().getStruct())[i].type->getQualifier().hasLocation()
 777                                     || unitSymbol->getType().getQualifier().hasLocation())
 778                                 ) {
 779                                 error(infoSink, "Anonymous member name used for global variable or other anonymous member: ");
 780                                 infoSink.info << (*unitSymbol->getType().getStruct())[i].type->getCompleteString() << "\n";
 781                             }
 782                         }
 783                     };
 784
 785                     if (isSameInterface(symbol, getStage(), unitSymbol, unitStage)) {
 786                         checkName(symbol->getName());
 787
 788                         // check members of other anonymous blocks
 789                         if (symbol->getBasicType() == EbtBlock && IsAnonymous(symbol->getName())) {
 790                             for (unsigned int i = 0; i < symbol->getType().getStruct()->size(); ++i) {
 791                                 checkName((*symbol->getType().getStruct())[i].type->getFieldName());
 792                             }
 793                         }
 794                     }
 795                 }
 796             }
 797         }
 798     }
 799 }
 800
 801 // TODO 4.5 link functionality: cull distance array size checking
 802
 803 // Recursively merge the implicit array sizes through the objects' respective type trees.
 804 void TIntermediate::mergeImplicitArraySizes(TType& type, const TType& unitType)
 805 {
 806     if (type.isUnsizedArray()) {
 807         if (unitType.isUnsizedArray()) {
 808             type.updateImplicitArraySize(unitType.getImplicitArraySize());
 809             if (unitType.isArrayVariablyIndexed())
 810                 type.setArrayVariablyIndexed();
 811         } else if (unitType.isSizedArray())
 812             type.changeOuterArraySize(unitType.getOuterArraySize());
 813     }
 814
 815     // Type mismatches are caught and reported after this, just be careful for now.
 816     if (! type.isStruct() || ! unitType.isStruct() || type.getStruct()->size() != unitType.getStruct()->size())
 817         return;
 818
 819     for (int i = 0; i < (int)type.getStruct()->size(); ++i)
 820         mergeImplicitArraySizes(*(*type.getStruct())[i].type, *(*unitType.getStruct())[i].type);
 821 }
 822
 823 //
 824 // Compare two global objects from two compilation units and see if they match
 825 // well enough.  Rules can be different for intra- vs. cross-stage matching.
 826 //
 827 // This function only does one of intra- or cross-stage matching per call.
 828 //
 829 void TIntermediate::mergeErrorCheck(TInfoSink& infoSink, const TIntermSymbol& symbol, const TIntermSymbol& unitSymbol, EShLanguage unitStage)
 830 {
 831 #if !defined(GLSLANG_WEB) && !defined(GLSLANG_ANGLE)
 832     bool crossStage = getStage() != unitStage;
 833     bool writeTypeComparison = false;
 834     bool errorReported = false;
 835     bool printQualifiers = false;
 836     bool printPrecision = false;
 837     bool printType = false;
 838
 839     // Types have to match
 840     {
 841         // but, we make an exception if one is an implicit array and the other is sized
 842         // or if the array sizes differ because of the extra array dimension on some in/out boundaries
 843         bool arraysMatch = false;
 844         if (isIoResizeArray(symbol.getType(), getStage()) || isIoResizeArray(unitSymbol.getType(), unitStage)) {
 845             // if the arrays have an extra dimension because of the stage.
 846             // compare dimensions while ignoring the outer dimension
 847             unsigned int firstDim = isIoResizeArray(symbol.getType(), getStage()) ? 1 : 0;
 848             unsigned int numDim = symbol.getArraySizes()
 849                 ? symbol.getArraySizes()->getNumDims() : 0;
 850             unsigned int unitFirstDim = isIoResizeArray(unitSymbol.getType(), unitStage) ? 1 : 0;
 851             unsigned int unitNumDim = unitSymbol.getArraySizes()
 852                 ? unitSymbol.getArraySizes()->getNumDims() : 0;
 853             arraysMatch = (numDim - firstDim) == (unitNumDim - unitFirstDim);
 854             // check that array sizes match as well
 855             for (unsigned int i = 0; i < (numDim - firstDim) && arraysMatch; i++) {
 856                 if (symbol.getArraySizes()->getDimSize(firstDim + i) !=
 857                     unitSymbol.getArraySizes()->getDimSize(unitFirstDim + i)) {
 858                     arraysMatch = false;
 859                     break;
 860                 }
 861             }
 862         }
 863         else {
 864             arraysMatch = symbol.getType().sameArrayness(unitSymbol.getType()) ||
 865                 (symbol.getType().isArray() && unitSymbol.getType().isArray() &&
 866                 (symbol.getType().isUnsizedArray() || unitSymbol.getType().isUnsizedArray()));
 867         }
 868
 869         int lpidx = -1;
 870         int rpidx = -1;
 871         if (!symbol.getType().sameElementType(unitSymbol.getType(), &lpidx, &rpidx)) {
 872             if (lpidx >= 0 && rpidx >= 0) {
 873                 error(infoSink, "Member names and types must match:", unitStage);
 874                 infoSink.info << "    Block: " << symbol.getType().getTypeName() << "\n";
 875                 infoSink.info << "        " << StageName(getStage()) << " stage: \""
 876                               << (*symbol.getType().getStruct())[lpidx].type->getCompleteString(true, false, false, true,
 877                                       (*symbol.getType().getStruct())[lpidx].type->getFieldName()) << "\"\n";
 878                 infoSink.info << "        " << StageName(unitStage) << " stage: \""
 879                               << (*unitSymbol.getType().getStruct())[rpidx].type->getCompleteString(true, false, false, true,
 880                                       (*unitSymbol.getType().getStruct())[rpidx].type->getFieldName()) << "\"\n";
 881                 errorReported = true;
 882             } else if (lpidx >= 0 && rpidx == -1) {
 883                   TString errmsg = StageName(getStage());
 884                   errmsg.append(" block member has no corresponding member in ").append(StageName(unitStage)).append(" block:");
 885                   error(infoSink, errmsg.c_str(), unitStage);
 886                   infoSink.info << "    " << StageName(getStage()) << " stage: Block: " << symbol.getType().getTypeName() << ", Member: "
 887                     << (*symbol.getType().getStruct())[lpidx].type->getFieldName() << "\n";
 888                   infoSink.info << "    " << StageName(unitStage) << " stage: Block: " << unitSymbol.getType().getTypeName() << ", Member: n/a \n";
 889                   errorReported = true;
 890             } else if (lpidx == -1 && rpidx >= 0) {
 891                   TString errmsg = StageName(unitStage);
 892                   errmsg.append(" block member has no corresponding member in ").append(StageName(getStage())).append(" block:");
 893                   error(infoSink, errmsg.c_str(), unitStage);
 894                   infoSink.info << "    " << StageName(unitStage) << " stage: Block: " << unitSymbol.getType().getTypeName() << ", Member: "
 895                     << (*unitSymbol.getType().getStruct())[rpidx].type->getFieldName() << "\n";
 896                   infoSink.info << "    " << StageName(getStage()) << " stage: Block: " << symbol.getType().getTypeName() << ", Member: n/a \n";
 897                   errorReported = true;
 898             } else {
 899                   error(infoSink, "Types must match:", unitStage);
 900                   writeTypeComparison = true;
 901                   printType = true;
 902             }
 903         } else if (!arraysMatch) {
 904             error(infoSink, "Array sizes must be compatible:", unitStage);
 905             writeTypeComparison = true;
 906             printType = true;
 907         } else if (!symbol.getType().sameTypeParameters(unitSymbol.getType())) {
 908             error(infoSink, "Type parameters must match:", unitStage);
 909             writeTypeComparison = true;
 910             printType = true;
 911         }
 912     }
 913
 914     // Interface block  member-wise layout qualifiers have to match
 915     if (symbol.getType().getBasicType() == EbtBlock && unitSymbol.getType().getBasicType() == EbtBlock &&
 916         symbol.getType().getStruct() && unitSymbol.getType().getStruct() &&
 917         symbol.getType().sameStructType(unitSymbol.getType())) {
 918         unsigned int li = 0;
 919         unsigned int ri = 0;
 920         while (li < symbol.getType().getStruct()->size() && ri < unitSymbol.getType().getStruct()->size()) {
 921             if ((*symbol.getType().getStruct())[li].type->hiddenMember()) {
 922                 ++li;
 923                 continue;
 924             }
 925             if ((*unitSymbol.getType().getStruct())[ri].type->hiddenMember()) {
 926                 ++ri;
 927                 continue;
 928             }
 929             const TQualifier& qualifier = (*symbol.getType().getStruct())[li].type->getQualifier();
 930             const TQualifier & unitQualifier = (*unitSymbol.getType().getStruct())[ri].type->getQualifier();
 931             bool layoutQualifierError = false;
 932             if (qualifier.layoutMatrix != unitQualifier.layoutMatrix) {
 933                 error(infoSink, "Interface block member layout matrix qualifier must match:", unitStage);
 934                 layoutQualifierError = true;
 935             }
 936             if (qualifier.layoutOffset != unitQualifier.layoutOffset) {
 937                 error(infoSink, "Interface block member layout offset qualifier must match:", unitStage);
 938                 layoutQualifierError = true;
 939             }
 940             if (qualifier.layoutAlign != unitQualifier.layoutAlign) {
 941                 error(infoSink, "Interface block member layout align qualifier must match:", unitStage);
 942                 layoutQualifierError = true;
 943             }
 944             if (qualifier.layoutLocation != unitQualifier.layoutLocation) {
 945                 error(infoSink, "Interface block member layout location qualifier must match:", unitStage);
 946                 layoutQualifierError = true;
 947             }
 948             if (qualifier.layoutComponent != unitQualifier.layoutComponent) {
 949                 error(infoSink, "Interface block member layout component qualifier must match:", unitStage);
 950                 layoutQualifierError = true;
 951             }
 952             if (layoutQualifierError) {
 953                 infoSink.info << "    " << StageName(getStage()) << " stage: Block: " << symbol.getType().getTypeName() << ", Member: "
 954                               << (*symbol.getType().getStruct())[li].type->getFieldName() << " \""
 955                               << (*symbol.getType().getStruct())[li].type->getCompleteString(true, true, false, false) << "\"\n";
 956                 infoSink.info << "    " << StageName(unitStage) << " stage: Block: " << unitSymbol.getType().getTypeName() << ", Member: "
 957                               << (*unitSymbol.getType().getStruct())[ri].type->getFieldName() << " \""
 958                               << (*unitSymbol.getType().getStruct())[ri].type->getCompleteString(true, true, false, false) << "\"\n";
 959                 errorReported = true;
 960             }
 961             ++li;
 962             ++ri;
 963         }
 964     }
 965
 966     bool isInOut = crossStage &&
 967                    ((symbol.getQualifier().storage == EvqVaryingIn && unitSymbol.getQualifier().storage == EvqVaryingOut) ||
 968                    (symbol.getQualifier().storage == EvqVaryingOut && unitSymbol.getQualifier().storage == EvqVaryingIn));
 969
 970     // Qualifiers have to (almost) match
 971     // Storage...
 972     if (!isInOut && symbol.getQualifier().storage != unitSymbol.getQualifier().storage) {
 973         error(infoSink, "Storage qualifiers must match:", unitStage);
 974         writeTypeComparison = true;
 975         printQualifiers = true;
 976     }
 977
 978     // Uniform and buffer blocks must either both have an instance name, or
 979     // must both be anonymous. The names don't need to match though.
 980     if (symbol.getQualifier().isUniformOrBuffer() &&
 981         (IsAnonymous(symbol.getName()) != IsAnonymous(unitSymbol.getName()))) {
 982         error(infoSink, "Matched Uniform or Storage blocks must all be anonymous,"
 983                         " or all be named:", unitStage);
 984         writeTypeComparison = true;
 985     }
 986
 987     if (symbol.getQualifier().storage == unitSymbol.getQualifier().storage &&
 988         (IsAnonymous(symbol.getName()) != IsAnonymous(unitSymbol.getName()) ||
 989          (!IsAnonymous(symbol.getName()) && symbol.getName() != unitSymbol.getName()))) {
 990         warn(infoSink, "Matched shader interfaces are using different instance names.", unitStage);
 991         writeTypeComparison = true;
 992     }
 993
 994     // Precision...
 995     if (!isInOut && symbol.getQualifier().precision != unitSymbol.getQualifier().precision) {
 996         error(infoSink, "Precision qualifiers must match:", unitStage);
 997         writeTypeComparison = true;
 998         printPrecision = true;
 999     }
1000
1001     // Invariance...
1002     if (! crossStage && symbol.getQualifier().invariant != unitSymbol.getQualifier().invariant) {
1003         error(infoSink, "Presence of invariant qualifier must match:", unitStage);
1004         writeTypeComparison = true;
1005         printQualifiers = true;
1006     }
1007
1008     // Precise...
1009     if (! crossStage && symbol.getQualifier().isNoContraction() != unitSymbol.getQualifier().isNoContraction()) {
1010         error(infoSink, "Presence of precise qualifier must match:", unitStage);
1011         writeTypeComparison = true;
1012         printPrecision = true;
1013     }
1014
1015     // Auxiliary and interpolation...
1016     // "interpolation qualification (e.g., flat) and auxiliary qualification (e.g. centroid) may differ.
1017     //  These mismatches are allowed between any pair of stages ...
1018     //  those provided in the fragment shader supersede those provided in previous stages."
1019     if (!crossStage &&
1020         (symbol.getQualifier().centroid  != unitSymbol.getQualifier().centroid ||
1021         symbol.getQualifier().smooth    != unitSymbol.getQualifier().smooth ||
1022         symbol.getQualifier().flat      != unitSymbol.getQualifier().flat ||
1023         symbol.getQualifier().isSample()!= unitSymbol.getQualifier().isSample() ||
1024         symbol.getQualifier().isPatch() != unitSymbol.getQualifier().isPatch() ||
1025         symbol.getQualifier().isNonPerspective() != unitSymbol.getQualifier().isNonPerspective())) {
1026         error(infoSink, "Interpolation and auxiliary storage qualifiers must match:", unitStage);
1027         writeTypeComparison = true;
1028         printQualifiers = true;
1029     }
1030
1031     // Memory...
1032     bool memoryQualifierError = false;
1033     if (symbol.getQualifier().coherent != unitSymbol.getQualifier().coherent) {
1034         error(infoSink, "Memory coherent qualifier must match:", unitStage);
1035         memoryQualifierError = true;
1036     }
1037     if (symbol.getQualifier().devicecoherent != unitSymbol.getQualifier().devicecoherent) {
1038         error(infoSink, "Memory devicecoherent qualifier must match:", unitStage);
1039         memoryQualifierError = true;
1040     }
1041     if (symbol.getQualifier().queuefamilycoherent != unitSymbol.getQualifier().queuefamilycoherent) {
1042         error(infoSink, "Memory queuefamilycoherent qualifier must match:", unitStage);
1043         memoryQualifierError = true;
1044     }
1045     if (symbol.getQualifier().workgroupcoherent != unitSymbol.getQualifier().workgroupcoherent) {
1046         error(infoSink, "Memory workgroupcoherent qualifier must match:", unitStage);
1047         memoryQualifierError = true;
1048     }
1049     if (symbol.getQualifier().subgroupcoherent != unitSymbol.getQualifier().subgroupcoherent) {
1050         error(infoSink, "Memory subgroupcoherent qualifier must match:", unitStage);
1051         memoryQualifierError = true;
1052     }
1053     if (symbol.getQualifier().shadercallcoherent != unitSymbol.getQualifier().shadercallcoherent) {
1054         error(infoSink, "Memory shadercallcoherent qualifier must match:", unitStage);
1055         memoryQualifierError = true;
1056     }
1057     if (symbol.getQualifier().nonprivate != unitSymbol.getQualifier().nonprivate) {
1058         error(infoSink, "Memory nonprivate qualifier must match:", unitStage);
1059         memoryQualifierError = true;
1060     }
1061     if (symbol.getQualifier().volatil != unitSymbol.getQualifier().volatil) {
1062         error(infoSink, "Memory volatil qualifier must match:", unitStage);
1063         memoryQualifierError = true;
1064     }
1065     if (symbol.getQualifier().restrict != unitSymbol.getQualifier().restrict) {
1066         error(infoSink, "Memory restrict qualifier must match:", unitStage);
1067         memoryQualifierError = true;
1068     }
1069     if (symbol.getQualifier().readonly != unitSymbol.getQualifier().readonly) {
1070         error(infoSink, "Memory readonly qualifier must match:", unitStage);
1071         memoryQualifierError = true;
1072     }
1073     if (symbol.getQualifier().writeonly != unitSymbol.getQualifier().writeonly) {
1074         error(infoSink, "Memory writeonly qualifier must match:", unitStage);
1075         memoryQualifierError = true;
1076     }
1077     if (memoryQualifierError) {
1078           writeTypeComparison = true;
1079           printQualifiers = true;
1080     }
1081
1082     // Layouts...
1083     // TODO: 4.4 enhanced layouts: Generalize to include offset/align: current spec
1084     //       requires separate user-supplied offset from actual computed offset, but
1085     //       current implementation only has one offset.
1086     bool layoutQualifierError = false;
1087     if (symbol.getQualifier().layoutMatrix != unitSymbol.getQualifier().layoutMatrix) {
1088         error(infoSink, "Layout matrix qualifier must match:", unitStage);
1089         layoutQualifierError = true;
1090     }
1091     if (symbol.getQualifier().layoutPacking != unitSymbol.getQualifier().layoutPacking) {
1092         error(infoSink, "Layout packing qualifier must match:", unitStage);
1093         layoutQualifierError = true;
1094     }
1095     if (symbol.getQualifier().hasLocation() && unitSymbol.getQualifier().hasLocation() && symbol.getQualifier().layoutLocation != unitSymbol.getQualifier().layoutLocation) {
1096         error(infoSink, "Layout location qualifier must match:", unitStage);
1097         layoutQualifierError = true;
1098     }
1099     if (symbol.getQualifier().layoutComponent != unitSymbol.getQualifier().layoutComponent) {
1100         error(infoSink, "Layout component qualifier must match:", unitStage);
1101         layoutQualifierError = true;
1102     }
1103     if (symbol.getQualifier().layoutIndex != unitSymbol.getQualifier().layoutIndex) {
1104         error(infoSink, "Layout index qualifier must match:", unitStage);
1105         layoutQualifierError = true;
1106     }
1107     if (symbol.getQualifier().hasBinding() && unitSymbol.getQualifier().hasBinding() && symbol.getQualifier().layoutBinding != unitSymbol.getQualifier().layoutBinding) {
1108         error(infoSink, "Layout binding qualifier must match:", unitStage);
1109         layoutQualifierError = true;
1110     }
1111     if (symbol.getQualifier().hasBinding() && (symbol.getQualifier().layoutOffset != unitSymbol.getQualifier().layoutOffset)) {
1112         error(infoSink, "Layout offset qualifier must match:", unitStage);
1113         layoutQualifierError = true;
1114     }
1115     if (layoutQualifierError) {
1116         writeTypeComparison = true;
1117         printQualifiers = true;
1118     }
1119
1120     // Initializers have to match, if both are present, and if we don't already know the types don't match
1121     if (! writeTypeComparison && ! errorReported) {
1122         if (! symbol.getConstArray().empty() && ! unitSymbol.getConstArray().empty()) {
1123             if (symbol.getConstArray() != unitSymbol.getConstArray()) {
1124                 error(infoSink, "Initializers must match:", unitStage);
1125                 infoSink.info << "    " << symbol.getName() << "\n";
1126             }
1127         }
1128     }
1129
1130     if (writeTypeComparison) {
1131         if (symbol.getType().getBasicType() == EbtBlock && unitSymbol.getType().getBasicType() == EbtBlock &&
1132             symbol.getType().getStruct() && unitSymbol.getType().getStruct()) {
1133           if (printType) {
1134             infoSink.info << "    " << StageName(getStage()) << " stage: \"" << symbol.getType().getCompleteString(true, printQualifiers, printPrecision,
1135                                                     printType, symbol.getName(), symbol.getType().getTypeName()) << "\"\n";
1136             infoSink.info << "    " << StageName(unitStage) << " stage: \"" << unitSymbol.getType().getCompleteString(true, printQualifiers, printPrecision,
1137                                                     printType, unitSymbol.getName(), unitSymbol.getType().getTypeName()) << "\"\n";
1138           } else {
1139             infoSink.info << "    " << StageName(getStage()) << " stage: Block: " << symbol.getType().getTypeName() << " Instance: " << symbol.getName()
1140               << ": \"" << symbol.getType().getCompleteString(true, printQualifiers, printPrecision, printType) << "\"\n";
1141             infoSink.info << "    " << StageName(unitStage) << " stage: Block: " << unitSymbol.getType().getTypeName() << " Instance: " << unitSymbol.getName()
1142               << ": \"" << unitSymbol.getType().getCompleteString(true, printQualifiers, printPrecision, printType) << "\"\n";
1143           }
1144         } else {
1145           if (printType) {
1146             infoSink.info << "    " << StageName(getStage()) << " stage: \""
1147               << symbol.getType().getCompleteString(true, printQualifiers, printPrecision, printType, symbol.getName()) << "\"\n";
1148             infoSink.info << "    " << StageName(unitStage) << " stage: \""
1149               << unitSymbol.getType().getCompleteString(true, printQualifiers, printPrecision, printType, unitSymbol.getName()) << "\"\n";
1150           } else {
1151             infoSink.info << "    " << StageName(getStage()) << " stage: " << symbol.getName() << " \""
1152               << symbol.getType().getCompleteString(true, printQualifiers, printPrecision, printType) << "\"\n";
1153             infoSink.info << "    " << StageName(unitStage) << " stage: " << unitSymbol.getName() << " \""
1154               << unitSymbol.getType().getCompleteString(true, printQualifiers, printPrecision, printType) << "\"\n";
1155           }
1156         }
1157     }
1158 #endif
1159 }
1160
1161 void TIntermediate::sharedBlockCheck(TInfoSink& infoSink)
1162 {
1163     bool has_shared_block = false;
1164     bool has_shared_non_block = false;
1165     TIntermSequence& linkObjects = findLinkerObjects()->getSequence();
1166     for (size_t i = 0; i < linkObjects.size(); ++i) {
1167         const TType& type = linkObjects[i]->getAsTyped()->getType();
1168         const TQualifier& qualifier = type.getQualifier();
1169         if (qualifier.storage == glslang::EvqShared) {
1170             if (type.getBasicType() == glslang::EbtBlock)
1171                 has_shared_block = true;
1172             else
1173                 has_shared_non_block = true;
1174         }
1175     }
1176     if (has_shared_block && has_shared_non_block)
1177         error(infoSink, "cannot mix use of shared variables inside and outside blocks");
1178 }
1179
1180 //
1181 // Do final link-time error checking of a complete (merged) intermediate representation.
1182 // (Much error checking was done during merging).
1183 //
1184 // Also, lock in defaults of things not set, including array sizes.
1185 //
1186 void TIntermediate::finalCheck(TInfoSink& infoSink, bool keepUncalled)
1187 {
1188     if (getTreeRoot() == nullptr)
1189         return;
1190
1191     if (numEntryPoints < 1) {
1192         if (getSource() == EShSourceGlsl)
1193             error(infoSink, "Missing entry point: Each stage requires one entry point");
1194         else
1195             warn(infoSink, "Entry point not found");
1196     }
1197
1198     // recursion and missing body checking
1199     checkCallGraphCycles(infoSink);
1200     checkCallGraphBodies(infoSink, keepUncalled);
1201
1202     // overlap/alias/missing I/O, etc.
1203     inOutLocationCheck(infoSink);
1204
1205 #ifndef GLSLANG_WEB
1206     if (getNumPushConstants() > 1)
1207         error(infoSink, "Only one push_constant block is allowed per stage");
1208
1209     // invocations
1210     if (invocations == TQualifier::layoutNotSet)
1211         invocations = 1;
1212
1213     if (inIoAccessed("gl_ClipDistance") && inIoAccessed("gl_ClipVertex"))
1214         error(infoSink, "Can only use one of gl_ClipDistance or gl_ClipVertex (gl_ClipDistance is preferred)");
1215     if (inIoAccessed("gl_CullDistance") && inIoAccessed("gl_ClipVertex"))
1216         error(infoSink, "Can only use one of gl_CullDistance or gl_ClipVertex (gl_ClipDistance is preferred)");
1217
1218     if (userOutputUsed() && (inIoAccessed("gl_FragColor") || inIoAccessed("gl_FragData")))
1219         error(infoSink, "Cannot use gl_FragColor or gl_FragData when using user-defined outputs");
1220     if (inIoAccessed("gl_FragColor") && inIoAccessed("gl_FragData"))
1221         error(infoSink, "Cannot use both gl_FragColor and gl_FragData");
1222
1223     for (size_t b = 0; b < xfbBuffers.size(); ++b) {
1224         if (xfbBuffers[b].contains64BitType)
1225             RoundToPow2(xfbBuffers[b].implicitStride, 8);
1226         else if (xfbBuffers[b].contains32BitType)
1227             RoundToPow2(xfbBuffers[b].implicitStride, 4);
1228         else if (xfbBuffers[b].contains16BitType)
1229             RoundToPow2(xfbBuffers[b].implicitStride, 2);
1230
1231         // "It is a compile-time or link-time error to have
1232         // any xfb_offset that overflows xfb_stride, whether stated on declarations before or after the xfb_stride, or
1233         // in different compilation units. While xfb_stride can be declared multiple times for the same buffer, it is a
1234         // compile-time or link-time error to have different values specified for the stride for the same buffer."
1235         if (xfbBuffers[b].stride != TQualifier::layoutXfbStrideEnd && xfbBuffers[b].implicitStride > xfbBuffers[b].stride) {
1236             error(infoSink, "xfb_stride is too small to hold all buffer entries:");
1237             infoSink.info.prefix(EPrefixError);
1238             infoSink.info << "    xfb_buffer " << (unsigned int)b << ", xfb_stride " << xfbBuffers[b].stride << ", minimum stride needed: " << xfbBuffers[b].implicitStride << "\n";
1239         }
1240         if (xfbBuffers[b].stride == TQualifier::layoutXfbStrideEnd)
1241             xfbBuffers[b].stride = xfbBuffers[b].implicitStride;
1242
1243         // "If the buffer is capturing any
1244         // outputs with double-precision or 64-bit integer components, the stride must be a multiple of 8, otherwise it must be a
1245         // multiple of 4, or a compile-time or link-time error results."
1246         if (xfbBuffers[b].contains64BitType && ! IsMultipleOfPow2(xfbBuffers[b].stride, 8)) {
1247             error(infoSink, "xfb_stride must be multiple of 8 for buffer holding a double or 64-bit integer:");
1248             infoSink.info.prefix(EPrefixError);
1249             infoSink.info << "    xfb_buffer " << (unsigned int)b << ", xfb_stride " << xfbBuffers[b].stride << "\n";
1250         } else if (xfbBuffers[b].contains32BitType && ! IsMultipleOfPow2(xfbBuffers[b].stride, 4)) {
1251             error(infoSink, "xfb_stride must be multiple of 4:");
1252             infoSink.info.prefix(EPrefixError);
1253             infoSink.info << "    xfb_buffer " << (unsigned int)b << ", xfb_stride " << xfbBuffers[b].stride << "\n";
1254         }
1255         // "If the buffer is capturing any
1256         // outputs with half-precision or 16-bit integer components, the stride must be a multiple of 2"
1257         else if (xfbBuffers[b].contains16BitType && ! IsMultipleOfPow2(xfbBuffers[b].stride, 2)) {
1258             error(infoSink, "xfb_stride must be multiple of 2 for buffer holding a half float or 16-bit integer:");
1259             infoSink.info.prefix(EPrefixError);
1260             infoSink.info << "    xfb_buffer " << (unsigned int)b << ", xfb_stride " << xfbBuffers[b].stride << "\n";
1261         }
1262
1263         // "The resulting stride (implicit or explicit), when divided by 4, must be less than or equal to the
1264         // implementation-dependent constant gl_MaxTransformFeedbackInterleavedComponents."
1265         if (xfbBuffers[b].stride > (unsigned int)(4 * resources->maxTransformFeedbackInterleavedComponents)) {
1266             error(infoSink, "xfb_stride is too large:");
1267             infoSink.info.prefix(EPrefixError);
1268             infoSink.info << "    xfb_buffer " << (unsigned int)b << ", components (1/4 stride) needed are " << xfbBuffers[b].stride/4 << ", gl_MaxTransformFeedbackInterleavedComponents is " << resources->maxTransformFeedbackInterleavedComponents << "\n";
1269         }
1270     }
1271
1272     switch (language) {
1273     case EShLangVertex:
1274         break;
1275     case EShLangTessControl:
1276         if (vertices == TQualifier::layoutNotSet)
1277             error(infoSink, "At least one shader must specify an output layout(vertices=...)");
1278         break;
1279     case EShLangTessEvaluation:
1280         if (getSource() == EShSourceGlsl) {
1281             if (inputPrimitive == ElgNone)
1282                 error(infoSink, "At least one shader must specify an input layout primitive");
1283             if (vertexSpacing == EvsNone)
1284                 vertexSpacing = EvsEqual;
1285             if (vertexOrder == EvoNone)
1286                 vertexOrder = EvoCcw;
1287         }
1288         break;
1289     case EShLangGeometry:
1290         if (inputPrimitive == ElgNone)
1291             error(infoSink, "At least one shader must specify an input layout primitive");
1292         if (outputPrimitive == ElgNone)
1293             error(infoSink, "At least one shader must specify an output layout primitive");
1294         if (vertices == TQualifier::layoutNotSet)
1295             error(infoSink, "At least one shader must specify a layout(max_vertices = value)");
1296         break;
1297     case EShLangFragment:
1298         // for GL_ARB_post_depth_coverage, EarlyFragmentTest is set automatically in
1299         // ParseHelper.cpp. So if we reach here, this must be GL_EXT_post_depth_coverage
1300         // requiring explicit early_fragment_tests
1301         if (getPostDepthCoverage() && !getEarlyFragmentTests())
1302             error(infoSink, "post_depth_coverage requires early_fragment_tests");
1303         break;
1304     case EShLangCompute:
1305         sharedBlockCheck(infoSink);
1306         break;
1307     case EShLangRayGen:
1308     case EShLangIntersect:
1309     case EShLangAnyHit:
1310     case EShLangClosestHit:
1311     case EShLangMiss:
1312     case EShLangCallable:
1313         if (numShaderRecordBlocks > 1)
1314             error(infoSink, "Only one shaderRecordNV buffer block is allowed per stage");
1315         break;
1316     case EShLangMesh:
1317         // NV_mesh_shader doesn't allow use of both single-view and per-view builtins.
1318         if (inIoAccessed("gl_Position") && inIoAccessed("gl_PositionPerViewNV"))
1319             error(infoSink, "Can only use one of gl_Position or gl_PositionPerViewNV");
1320         if (inIoAccessed("gl_ClipDistance") && inIoAccessed("gl_ClipDistancePerViewNV"))
1321             error(infoSink, "Can only use one of gl_ClipDistance or gl_ClipDistancePerViewNV");
1322         if (inIoAccessed("gl_CullDistance") && inIoAccessed("gl_CullDistancePerViewNV"))
1323             error(infoSink, "Can only use one of gl_CullDistance or gl_CullDistancePerViewNV");
1324         if (inIoAccessed("gl_Layer") && inIoAccessed("gl_LayerPerViewNV"))
1325             error(infoSink, "Can only use one of gl_Layer or gl_LayerPerViewNV");
1326         if (inIoAccessed("gl_ViewportMask") && inIoAccessed("gl_ViewportMaskPerViewNV"))
1327             error(infoSink, "Can only use one of gl_ViewportMask or gl_ViewportMaskPerViewNV");
1328         if (outputPrimitive == ElgNone)
1329             error(infoSink, "At least one shader must specify an output layout primitive");
1330         if (vertices == TQualifier::layoutNotSet)
1331             error(infoSink, "At least one shader must specify a layout(max_vertices = value)");
1332         if (primitives == TQualifier::layoutNotSet)
1333             error(infoSink, "At least one shader must specify a layout(max_primitives = value)");
1334         // fall through
1335     case EShLangTask:
1336         if (numTaskNVBlocks > 1)
1337             error(infoSink, "Only one taskNV interface block is allowed per shader");
1338         if (numTaskEXTPayloads > 1)
1339             error(infoSink, "Only single variable of type taskPayloadSharedEXT is allowed per shader");
1340         sharedBlockCheck(infoSink);
1341         break;
1342     default:
1343         error(infoSink, "Unknown Stage.");
1344         break;
1345     }
1346
1347     // Process the tree for any node-specific work.
1348     class TFinalLinkTraverser : public TIntermTraverser {
1349     public:
1350         TFinalLinkTraverser() { }
1351         virtual ~TFinalLinkTraverser() { }
1352
1353         virtual void visitSymbol(TIntermSymbol* symbol)
1354         {
1355             // Implicitly size arrays.
1356             // If an unsized array is left as unsized, it effectively
1357             // becomes run-time sized.
1358             symbol->getWritableType().adoptImplicitArraySizes(false);
1359         }
1360     } finalLinkTraverser;
1361
1362     treeRoot->traverse(&finalLinkTraverser);
1363 #endif
1364 }
1365
1366 //
1367 // See if the call graph contains any static recursion, which is disallowed
1368 // by the specification.
1369 //
1370 void TIntermediate::checkCallGraphCycles(TInfoSink& infoSink)
1371 {
1372     // Clear fields we'll use for this.
1373     for (TGraph::iterator call = callGraph.begin(); call != callGraph.end(); ++call) {
1374         call->visited = false;
1375         call->currentPath = false;
1376         call->errorGiven = false;
1377     }
1378
1379     //
1380     // Loop, looking for a new connected subgraph.  One subgraph is handled per loop iteration.
1381     //
1382
1383     TCall* newRoot;
1384     do {
1385         // See if we have unvisited parts of the graph.
1386         newRoot = 0;
1387         for (TGraph::iterator call = callGraph.begin(); call != callGraph.end(); ++call) {
1388             if (! call->visited) {
1389                 newRoot = &(*call);
1390                 break;
1391             }
1392         }
1393
1394         // If not, we are done.
1395         if (! newRoot)
1396             break;
1397
1398         // Otherwise, we found a new subgraph, process it:
1399         // See what all can be reached by this new root, and if any of
1400         // that is recursive.  This is done by depth-first traversals, seeing
1401         // if a new call is found that was already in the currentPath (a back edge),
1402         // thereby detecting recursion.
1403         std::list<TCall*> stack;
1404         newRoot->currentPath = true; // currentPath will be true iff it is on the stack
1405         stack.push_back(newRoot);
1406         while (! stack.empty()) {
1407             // get a caller
1408             TCall* call = stack.back();
1409
1410             // Add to the stack just one callee.
1411             // This algorithm always terminates, because only !visited and !currentPath causes a push
1412             // and all pushes change currentPath to true, and all pops change visited to true.
1413             TGraph::iterator child = callGraph.begin();
1414             for (; child != callGraph.end(); ++child) {
1415
1416                 // If we already visited this node, its whole subgraph has already been processed, so skip it.
1417                 if (child->visited)
1418                     continue;
1419
1420                 if (call->callee == child->caller) {
1421                     if (child->currentPath) {
1422                         // Then, we found a back edge
1423                         if (! child->errorGiven) {
1424                             error(infoSink, "Recursion detected:");
1425                             infoSink.info << "    " << call->callee << " calling " << child->callee << "\n";
1426                             child->errorGiven = true;
1427                             recursive = true;
1428                         }
1429                     } else {
1430                         child->currentPath = true;
1431                         stack.push_back(&(*child));
1432                         break;
1433                     }
1434                 }
1435             }
1436             if (child == callGraph.end()) {
1437                 // no more callees, we bottomed out, never look at this node again
1438                 stack.back()->currentPath = false;
1439                 stack.back()->visited = true;
1440                 stack.pop_back();
1441             }
1442         }  // end while, meaning nothing left to process in this subtree
1443
1444     } while (newRoot);  // redundant loop check; should always exit via the 'break' above
1445 }
1446
1447 //
1448 // See which functions are reachable from the entry point and which have bodies.
1449 // Reachable ones with missing bodies are errors.
1450 // Unreachable bodies are dead code.
1451 //
1452 void TIntermediate::checkCallGraphBodies(TInfoSink& infoSink, bool keepUncalled)
1453 {
1454     // Clear fields we'll use for this.
1455     for (TGraph::iterator call = callGraph.begin(); call != callGraph.end(); ++call) {
1456         call->visited = false;
1457         call->calleeBodyPosition = -1;
1458     }
1459
1460     // The top level of the AST includes function definitions (bodies).
1461     // Compare these to function calls in the call graph.
1462     // We'll end up knowing which have bodies, and if so,
1463     // how to map the call-graph node to the location in the AST.
1464     TIntermSequence &functionSequence = getTreeRoot()->getAsAggregate()->getSequence();
1465     std::vector<bool> reachable(functionSequence.size(), true); // so that non-functions are reachable
1466     for (int f = 0; f < (int)functionSequence.size(); ++f) {
1467         glslang::TIntermAggregate* node = functionSequence[f]->getAsAggregate();
1468         if (node && (node->getOp() == glslang::EOpFunction)) {
1469             if (node->getName().compare(getEntryPointMangledName().c_str()) != 0)
1470                 reachable[f] = false; // so that function bodies are unreachable, until proven otherwise
1471             for (TGraph::iterator call = callGraph.begin(); call != callGraph.end(); ++call) {
1472                 if (call->callee == node->getName())
1473                     call->calleeBodyPosition = f;
1474             }
1475         }
1476     }
1477
1478     // Start call-graph traversal by visiting the entry point nodes.
1479     for (TGraph::iterator call = callGraph.begin(); call != callGraph.end(); ++call) {
1480         if (call->caller.compare(getEntryPointMangledName().c_str()) == 0)
1481             call->visited = true;
1482     }
1483
1484     // Propagate 'visited' through the call-graph to every part of the graph it
1485     // can reach (seeded with the entry-point setting above).
1486     bool changed;
1487     do {
1488         changed = false;
1489         for (auto call1 = callGraph.begin(); call1 != callGraph.end(); ++call1) {
1490             if (call1->visited) {
1491                 for (TGraph::iterator call2 = callGraph.begin(); call2 != callGraph.end(); ++call2) {
1492                     if (! call2->visited) {
1493                         if (call1->callee == call2->caller) {
1494                             changed = true;
1495                             call2->visited = true;
1496                         }
1497                     }
1498                 }
1499             }
1500         }
1501     } while (changed);
1502
1503     // Any call-graph node set to visited but without a callee body is an error.
1504     for (TGraph::iterator call = callGraph.begin(); call != callGraph.end(); ++call) {
1505         if (call->visited) {
1506             if (call->calleeBodyPosition == -1) {
1507                 error(infoSink, "No function definition (body) found: ");
1508                 infoSink.info << "    " << call->callee << "\n";
1509             } else
1510                 reachable[call->calleeBodyPosition] = true;
1511         }
1512     }
1513
1514     // Bodies in the AST not reached by the call graph are dead;
1515     // clear them out, since they can't be reached and also can't
1516     // be translated further due to possibility of being ill defined.
1517     if (! keepUncalled) {
1518         for (int f = 0; f < (int)functionSequence.size(); ++f) {
1519             if (! reachable[f])
1520                 functionSequence[f] = nullptr;
1521         }
1522         functionSequence.erase(std::remove(functionSequence.begin(), functionSequence.end(), nullptr), functionSequence.end());
1523     }
1524 }
1525
1526 //
1527 // Satisfy rules for location qualifiers on inputs and outputs
1528 //
1529 void TIntermediate::inOutLocationCheck(TInfoSink& infoSink)
1530 {
1531     // ES 3.0 requires all outputs to have location qualifiers if there is more than one output
1532     bool fragOutWithNoLocation = false;
1533     int numFragOut = 0;
1534
1535     // TODO: linker functionality: location collision checking
1536
1537     TIntermSequence& linkObjects = findLinkerObjects()->getSequence();
1538     for (size_t i = 0; i < linkObjects.size(); ++i) {
1539         const TType& type = linkObjects[i]->getAsTyped()->getType();
1540         const TQualifier& qualifier = type.getQualifier();
1541         if (language == EShLangFragment) {
1542             if (qualifier.storage == EvqVaryingOut && qualifier.builtIn == EbvNone) {
1543                 ++numFragOut;
1544                 if (!qualifier.hasAnyLocation())
1545                     fragOutWithNoLocation = true;
1546             }
1547         }
1548     }
1549
1550     if (isEsProfile()) {
1551         if (numFragOut > 1 && fragOutWithNoLocation)
1552             error(infoSink, "when more than one fragment shader output, all must have location qualifiers");
1553     }
1554 }
1555
1556 TIntermAggregate* TIntermediate::findLinkerObjects() const
1557 {
1558     // Get the top-level globals
1559     TIntermSequence& globals = treeRoot->getAsAggregate()->getSequence();
1560
1561     // Get the last member of the sequences, expected to be the linker-object lists
1562     assert(globals.back()->getAsAggregate()->getOp() == EOpLinkerObjects);
1563
1564     return globals.back()->getAsAggregate();
1565 }
1566
1567 // See if a variable was both a user-declared output and used.
1568 // Note: the spec discusses writing to one, but this looks at read or write, which
1569 // is more useful, and perhaps the spec should be changed to reflect that.
1570 bool TIntermediate::userOutputUsed() const
1571 {
1572     const TIntermSequence& linkerObjects = findLinkerObjects()->getSequence();
1573
1574     bool found = false;
1575     for (size_t i = 0; i < linkerObjects.size(); ++i) {
1576         const TIntermSymbol& symbolNode = *linkerObjects[i]->getAsSymbolNode();
1577         if (symbolNode.getQualifier().storage == EvqVaryingOut &&
1578             symbolNode.getName().compare(0, 3, "gl_") != 0 &&
1579             inIoAccessed(symbolNode.getName())) {
1580             found = true;
1581             break;
1582         }
1583     }
1584
1585     return found;
1586 }
1587
1588 // Accumulate locations used for inputs, outputs, and uniforms, payload and callable data
1589 // and check for collisions as the accumulation is done.
1590 //
1591 // Returns < 0 if no collision, >= 0 if collision and the value returned is a colliding value.
1592 //
1593 // typeCollision is set to true if there is no direct collision, but the types in the same location
1594 // are different.
1595 //
1596 int TIntermediate::addUsedLocation(const TQualifier& qualifier, const TType& type, bool& typeCollision)
1597 {
1598     typeCollision = false;
1599
1600     int set;
1601     int setRT;
1602     if (qualifier.isPipeInput())
1603         set = 0;
1604     else if (qualifier.isPipeOutput())
1605         set = 1;
1606     else if (qualifier.storage == EvqUniform)
1607         set = 2;
1608     else if (qualifier.storage == EvqBuffer)
1609         set = 3;
1610     else if (qualifier.isAnyPayload())
1611         setRT = 0;
1612     else if (qualifier.isAnyCallable())
1613         setRT = 1;
1614     else
1615         return -1;
1616
1617     int size;
1618     if (qualifier.isAnyPayload() || qualifier.isAnyCallable()) {
1619         size = 1;
1620     } else if (qualifier.isUniformOrBuffer() || qualifier.isTaskMemory()) {
1621         if (type.isSizedArray())
1622             size = type.getCumulativeArraySize();
1623         else
1624             size = 1;
1625     } else {
1626         // Strip off the outer array dimension for those having an extra one.
1627         if (type.isArray() && qualifier.isArrayedIo(language)) {
1628             TType elementType(type, 0);
1629             size = computeTypeLocationSize(elementType, language);
1630         } else
1631             size = computeTypeLocationSize(type, language);
1632     }
1633
1634     // Locations, and components within locations.
1635     //
1636     // Almost always, dealing with components means a single location is involved.
1637     // The exception is a dvec3. From the spec:
1638     //
1639     // "A dvec3 will consume all four components of the first location and components 0 and 1 of
1640     // the second location. This leaves components 2 and 3 available for other component-qualified
1641     // declarations."
1642     //
1643     // That means, without ever mentioning a component, a component range
1644     // for a different location gets specified, if it's not a vertex shader input. (!)
1645     // (A vertex shader input will show using only one location, even for a dvec3/4.)
1646     //
1647     // So, for the case of dvec3, we need two independent ioRanges.
1648     //
1649     // For raytracing IO (payloads and callabledata) each declaration occupies a single
1650     // slot irrespective of type.
1651     int collision = -1; // no collision
1652 #ifndef GLSLANG_WEB
1653     if (qualifier.isAnyPayload() || qualifier.isAnyCallable()) {
1654         TRange range(qualifier.layoutLocation, qualifier.layoutLocation);
1655         collision = checkLocationRT(setRT, qualifier.layoutLocation);
1656         if (collision < 0)
1657             usedIoRT[setRT].push_back(range);
1658     } else if (size == 2 && type.getBasicType() == EbtDouble && type.getVectorSize() == 3 &&
1659         (qualifier.isPipeInput() || qualifier.isPipeOutput())) {
1660         // Dealing with dvec3 in/out split across two locations.
1661         // Need two io-ranges.
1662         // The case where the dvec3 doesn't start at component 0 was previously caught as overflow.
1663
1664         // First range:
1665         TRange locationRange(qualifier.layoutLocation, qualifier.layoutLocation);
1666         TRange componentRange(0, 3);
1667         TIoRange range(locationRange, componentRange, type.getBasicType(), 0);
1668
1669         // check for collisions
1670         collision = checkLocationRange(set, range, type, typeCollision);
1671         if (collision < 0) {
1672             usedIo[set].push_back(range);
1673
1674             // Second range:
1675             TRange locationRange2(qualifier.layoutLocation + 1, qualifier.layoutLocation + 1);
1676             TRange componentRange2(0, 1);
1677             TIoRange range2(locationRange2, componentRange2, type.getBasicType(), 0);
1678
1679             // check for collisions
1680             collision = checkLocationRange(set, range2, type, typeCollision);
1681             if (collision < 0)
1682                 usedIo[set].push_back(range2);
1683         }
1684     } else
1685 #endif
1686     {
1687         // Not a dvec3 in/out split across two locations, generic path.
1688         // Need a single IO-range block.
1689
1690         TRange locationRange(qualifier.layoutLocation, qualifier.layoutLocation + size - 1);
1691         TRange componentRange(0, 3);
1692         if (qualifier.hasComponent() || type.getVectorSize() > 0) {
1693             int consumedComponents = type.getVectorSize() * (type.getBasicType() == EbtDouble ? 2 : 1);
1694             if (qualifier.hasComponent())
1695                 componentRange.start = qualifier.layoutComponent;
1696             componentRange.last  = componentRange.start + consumedComponents - 1;
1697         }
1698
1699         // combine location and component ranges
1700         TIoRange range(locationRange, componentRange, type.getBasicType(), qualifier.hasIndex() ? qualifier.getIndex() : 0);
1701
1702         // check for collisions, except for vertex inputs on desktop targeting OpenGL
1703         if (! (!isEsProfile() && language == EShLangVertex && qualifier.isPipeInput()) || spvVersion.vulkan > 0)
1704             collision = checkLocationRange(set, range, type, typeCollision);
1705
1706         if (collision < 0)
1707             usedIo[set].push_back(range);
1708     }
1709
1710     return collision;
1711 }
1712
1713 // Compare a new (the passed in) 'range' against the existing set, and see
1714 // if there are any collisions.
1715 //
1716 // Returns < 0 if no collision, >= 0 if collision and the value returned is a colliding value.
1717 //
1718 int TIntermediate::checkLocationRange(int set, const TIoRange& range, const TType& type, bool& typeCollision)
1719 {
1720     for (size_t r = 0; r < usedIo[set].size(); ++r) {
1721         if (range.overlap(usedIo[set][r])) {
1722             // there is a collision; pick one
1723             return std::max(range.location.start, usedIo[set][r].location.start);
1724         } else if (range.location.overlap(usedIo[set][r].location) && type.getBasicType() != usedIo[set][r].basicType) {
1725             // aliased-type mismatch
1726             typeCollision = true;
1727             return std::max(range.location.start, usedIo[set][r].location.start);
1728         }
1729     }
1730
1731     return -1; // no collision
1732 }
1733
1734 int TIntermediate::checkLocationRT(int set, int location) {
1735     TRange range(location, location);
1736     for (size_t r = 0; r < usedIoRT[set].size(); ++r) {
1737         if (range.overlap(usedIoRT[set][r])) {
1738             return range.start;
1739         }
1740     }
1741     return -1; // no collision
1742 }
1743
1744 // Accumulate bindings and offsets, and check for collisions
1745 // as the accumulation is done.
1746 //
1747 // Returns < 0 if no collision, >= 0 if collision and the value returned is a colliding value.
1748 //
1749 int TIntermediate::addUsedOffsets(int binding, int offset, int numOffsets)
1750 {
1751     TRange bindingRange(binding, binding);
1752     TRange offsetRange(offset, offset + numOffsets - 1);
1753     TOffsetRange range(bindingRange, offsetRange);
1754
1755     // check for collisions, except for vertex inputs on desktop
1756     for (size_t r = 0; r < usedAtomics.size(); ++r) {
1757         if (range.overlap(usedAtomics[r])) {
1758             // there is a collision; pick one
1759             return std::max(offset, usedAtomics[r].offset.start);
1760         }
1761     }
1762
1763     usedAtomics.push_back(range);
1764
1765     return -1; // no collision
1766 }
1767
1768 // Accumulate used constant_id values.
1769 //
1770 // Return false is one was already used.
1771 bool TIntermediate::addUsedConstantId(int id)
1772 {
1773     if (usedConstantId.find(id) != usedConstantId.end())
1774         return false;
1775
1776     usedConstantId.insert(id);
1777
1778     return true;
1779 }
1780
1781 // Recursively figure out how many locations are used up by an input or output type.
1782 // Return the size of type, as measured by "locations".
1783 int TIntermediate::computeTypeLocationSize(const TType& type, EShLanguage stage)
1784 {
1785     // "If the declared input is an array of size n and each element takes m locations, it will be assigned m * n
1786     // consecutive locations..."
1787     if (type.isArray()) {
1788         // TODO: perf: this can be flattened by using getCumulativeArraySize(), and a deref that discards all arrayness
1789         // TODO: are there valid cases of having an unsized array with a location?  If so, running this code too early.
1790         TType elementType(type, 0);
1791         if (type.isSizedArray() && !type.getQualifier().isPerView())
1792             return type.getOuterArraySize() * computeTypeLocationSize(elementType, stage);
1793         else {
1794 #ifndef GLSLANG_WEB
1795             // unset perViewNV attributes for arrayed per-view outputs: "perviewNV vec4 v[MAX_VIEWS][3];"
1796             elementType.getQualifier().perViewNV = false;
1797 #endif
1798             return computeTypeLocationSize(elementType, stage);
1799         }
1800     }
1801
1802     // "The locations consumed by block and structure members are determined by applying the rules above
1803     // recursively..."
1804     if (type.isStruct()) {
1805         int size = 0;
1806         for (int member = 0; member < (int)type.getStruct()->size(); ++member) {
1807             TType memberType(type, member);
1808             size += computeTypeLocationSize(memberType, stage);
1809         }
1810         return size;
1811     }
1812
1813     // ES: "If a shader input is any scalar or vector type, it will consume a single location."
1814
1815     // Desktop: "If a vertex shader input is any scalar or vector type, it will consume a single location. If a non-vertex
1816     // shader input is a scalar or vector type other than dvec3 or dvec4, it will consume a single location, while
1817     // types dvec3 or dvec4 will consume two consecutive locations. Inputs of type double and dvec2 will
1818     // consume only a single location, in all stages."
1819     if (type.isScalar())
1820         return 1;
1821     if (type.isVector()) {
1822         if (stage == EShLangVertex && type.getQualifier().isPipeInput())
1823             return 1;
1824         if (type.getBasicType() == EbtDouble && type.getVectorSize() > 2)
1825             return 2;
1826         else
1827             return 1;
1828     }
1829
1830     // "If the declared input is an n x m single- or double-precision matrix, ...
1831     // The number of locations assigned for each matrix will be the same as
1832     // for an n-element array of m-component vectors..."
1833     if (type.isMatrix()) {
1834         TType columnType(type, 0);
1835         return type.getMatrixCols() * computeTypeLocationSize(columnType, stage);
1836     }
1837
1838     assert(0);
1839     return 1;
1840 }
1841
1842 // Same as computeTypeLocationSize but for uniforms
1843 int TIntermediate::computeTypeUniformLocationSize(const TType& type)
1844 {
1845     // "Individual elements of a uniform array are assigned
1846     // consecutive locations with the first element taking location
1847     // location."
1848     if (type.isArray()) {
1849         // TODO: perf: this can be flattened by using getCumulativeArraySize(), and a deref that discards all arrayness
1850         TType elementType(type, 0);
1851         if (type.isSizedArray()) {
1852             return type.getOuterArraySize() * computeTypeUniformLocationSize(elementType);
1853         } else {
1854             // TODO: are there valid cases of having an implicitly-sized array with a location?  If so, running this code too early.
1855             return computeTypeUniformLocationSize(elementType);
1856         }
1857     }
1858
1859     // "Each subsequent inner-most member or element gets incremental
1860     // locations for the entire structure or array."
1861     if (type.isStruct()) {
1862         int size = 0;
1863         for (int member = 0; member < (int)type.getStruct()->size(); ++member) {
1864             TType memberType(type, member);
1865             size += computeTypeUniformLocationSize(memberType);
1866         }
1867         return size;
1868     }
1869
1870     return 1;
1871 }
1872
1873 #ifndef GLSLANG_WEB
1874
1875 // Accumulate xfb buffer ranges and check for collisions as the accumulation is done.
1876 //
1877 // Returns < 0 if no collision, >= 0 if collision and the value returned is a colliding value.
1878 //
1879 int TIntermediate::addXfbBufferOffset(const TType& type)
1880 {
1881     const TQualifier& qualifier = type.getQualifier();
1882
1883     assert(qualifier.hasXfbOffset() && qualifier.hasXfbBuffer());
1884     TXfbBuffer& buffer = xfbBuffers[qualifier.layoutXfbBuffer];
1885
1886     // compute the range
1887     unsigned int size = computeTypeXfbSize(type, buffer.contains64BitType, buffer.contains32BitType, buffer.contains16BitType);
1888     buffer.implicitStride = std::max(buffer.implicitStride, qualifier.layoutXfbOffset + size);
1889     TRange range(qualifier.layoutXfbOffset, qualifier.layoutXfbOffset + size - 1);
1890
1891     // check for collisions
1892     for (size_t r = 0; r < buffer.ranges.size(); ++r) {
1893         if (range.overlap(buffer.ranges[r])) {
1894             // there is a collision; pick an example to return
1895             return std::max(range.start, buffer.ranges[r].start);
1896         }
1897     }
1898
1899     buffer.ranges.push_back(range);
1900
1901     return -1;  // no collision
1902 }
1903
1904 // Recursively figure out how many bytes of xfb buffer are used by the given type.
1905 // Return the size of type, in bytes.
1906 // Sets contains64BitType to true if the type contains a 64-bit data type.
1907 // Sets contains32BitType to true if the type contains a 32-bit data type.
1908 // Sets contains16BitType to true if the type contains a 16-bit data type.
1909 // N.B. Caller must set contains64BitType, contains32BitType, and contains16BitType to false before calling.
1910 unsigned int TIntermediate::computeTypeXfbSize(const TType& type, bool& contains64BitType, bool& contains32BitType, bool& contains16BitType) const
1911 {
1912     // "...if applied to an aggregate containing a double or 64-bit integer, the offset must also be a multiple of 8,
1913     // and the space taken in the buffer will be a multiple of 8.
1914     // ...within the qualified entity, subsequent components are each
1915     // assigned, in order, to the next available offset aligned to a multiple of
1916     // that component's size.  Aggregate types are flattened down to the component
1917     // level to get this sequence of components."
1918
1919     if (type.isSizedArray()) {
1920         // TODO: perf: this can be flattened by using getCumulativeArraySize(), and a deref that discards all arrayness
1921         // Unsized array use to xfb should be a compile error.
1922         TType elementType(type, 0);
1923         return type.getOuterArraySize() * computeTypeXfbSize(elementType, contains64BitType, contains16BitType, contains16BitType);
1924     }
1925
1926     if (type.isStruct()) {
1927         unsigned int size = 0;
1928         bool structContains64BitType = false;
1929         bool structContains32BitType = false;
1930         bool structContains16BitType = false;
1931         for (int member = 0; member < (int)type.getStruct()->size(); ++member) {
1932             TType memberType(type, member);
1933             // "... if applied to
1934             // an aggregate containing a double or 64-bit integer, the offset must also be a multiple of 8,
1935             // and the space taken in the buffer will be a multiple of 8."
1936             bool memberContains64BitType = false;
1937             bool memberContains32BitType = false;
1938             bool memberContains16BitType = false;
1939             int memberSize = computeTypeXfbSize(memberType, memberContains64BitType, memberContains32BitType, memberContains16BitType);
1940             if (memberContains64BitType) {
1941                 structContains64BitType = true;
1942                 RoundToPow2(size, 8);
1943             } else if (memberContains32BitType) {
1944                 structContains32BitType = true;
1945                 RoundToPow2(size, 4);
1946             } else if (memberContains16BitType) {
1947                 structContains16BitType = true;
1948                 RoundToPow2(size, 2);
1949             }
1950             size += memberSize;
1951         }
1952
1953         if (structContains64BitType) {
1954             contains64BitType = true;
1955             RoundToPow2(size, 8);
1956         } else if (structContains32BitType) {
1957             contains32BitType = true;
1958             RoundToPow2(size, 4);
1959         } else if (structContains16BitType) {
1960             contains16BitType = true;
1961             RoundToPow2(size, 2);
1962         }
1963         return size;
1964     }
1965
1966     int numComponents {0};
1967     if (type.isScalar())
1968         numComponents = 1;
1969     else if (type.isVector())
1970         numComponents = type.getVectorSize();
1971     else if (type.isMatrix())
1972         numComponents = type.getMatrixCols() * type.getMatrixRows();
1973     else {
1974         assert(0);
1975         numComponents = 1;
1976     }
1977
1978     if (type.getBasicType() == EbtDouble || type.getBasicType() == EbtInt64 || type.getBasicType() == EbtUint64) {
1979         contains64BitType = true;
1980         return 8 * numComponents;
1981     } else if (type.getBasicType() == EbtFloat16 || type.getBasicType() == EbtInt16 || type.getBasicType() == EbtUint16) {
1982         contains16BitType = true;
1983         return 2 * numComponents;
1984     } else if (type.getBasicType() == EbtInt8 || type.getBasicType() == EbtUint8)
1985         return numComponents;
1986     else {
1987         contains32BitType = true;
1988         return 4 * numComponents;
1989     }
1990 }
1991
1992 #endif
1993
1994 const int baseAlignmentVec4Std140 = 16;
1995
1996 // Return the size and alignment of a component of the given type.
1997 // The size is returned in the 'size' parameter
1998 // Return value is the alignment..
1999 int TIntermediate::getBaseAlignmentScalar(const TType& type, int& size)
2000 {
2001 #ifdef GLSLANG_WEB
2002     size = 4; return 4;
2003 #endif
2004
2005     switch (type.getBasicType()) {
2006     case EbtInt64:
2007     case EbtUint64:
2008     case EbtDouble:  size = 8; return 8;
2009     case EbtFloat16: size = 2; return 2;
2010     case EbtInt8:
2011     case EbtUint8:   size = 1; return 1;
2012     case EbtInt16:
2013     case EbtUint16:  size = 2; return 2;
2014     case EbtReference: size = 8; return 8;
2015     default:         size = 4; return 4;
2016     }
2017 }
2018
2019 // Implement base-alignment and size rules from section 7.6.2.2 Standard Uniform Block Layout
2020 // Operates recursively.
2021 //
2022 // If std140 is true, it does the rounding up to vec4 size required by std140,
2023 // otherwise it does not, yielding std430 rules.
2024 //
2025 // The size is returned in the 'size' parameter
2026 //
2027 // The stride is only non-0 for arrays or matrices, and is the stride of the
2028 // top-level object nested within the type.  E.g., for an array of matrices,
2029 // it is the distances needed between matrices, despite the rules saying the
2030 // stride comes from the flattening down to vectors.
2031 //
2032 // Return value is the alignment of the type.
2033 int TIntermediate::getBaseAlignment(const TType& type, int& size, int& stride, TLayoutPacking layoutPacking, bool rowMajor)
2034 {
2035     int alignment;
2036
2037     bool std140 = layoutPacking == glslang::ElpStd140;
2038     // When using the std140 storage layout, structures will be laid out in buffer
2039     // storage with its members stored in monotonically increasing order based on their
2040     // location in the declaration. A structure and each structure member have a base
2041     // offset and a base alignment, from which an aligned offset is computed by rounding
2042     // the base offset up to a multiple of the base alignment. The base offset of the first
2043     // member of a structure is taken from the aligned offset of the structure itself. The
2044     // base offset of all other structure members is derived by taking the offset of the
2045     // last basic machine unit consumed by the previous member and adding one. Each
2046     // structure member is stored in memory at its aligned offset. The members of a top-
2047     // level uniform block are laid out in buffer storage by treating the uniform block as
2048     // a structure with a base offset of zero.
2049     //
2050     //   1. If the member is a scalar consuming N basic machine units, the base alignment is N.
2051     //
2052     //   2. If the member is a two- or four-component vector with components consuming N basic
2053     //      machine units, the base alignment is 2N or 4N, respectively.
2054     //
2055     //   3. If the member is a three-component vector with components consuming N
2056     //      basic machine units, the base alignment is 4N.
2057     //
2058     //   4. If the member is an array of scalars or vectors, the base alignment and array
2059     //      stride are set to match the base alignment of a single array element, according
2060     //      to rules (1), (2), and (3), and rounded up to the base alignment of a vec4. The
2061     //      array may have padding at the end; the base offset of the member following
2062     //      the array is rounded up to the next multiple of the base alignment.
2063     //
2064     //   5. If the member is a column-major matrix with C columns and R rows, the
2065     //      matrix is stored identically to an array of C column vectors with R
2066     //      components each, according to rule (4).
2067     //
2068     //   6. If the member is an array of S column-major matrices with C columns and
2069     //      R rows, the matrix is stored identically to a row of S X C column vectors
2070     //      with R components each, according to rule (4).
2071     //
2072     //   7. If the member is a row-major matrix with C columns and R rows, the matrix
2073     //      is stored identically to an array of R row vectors with C components each,
2074     //      according to rule (4).
2075     //
2076     //   8. If the member is an array of S row-major matrices with C columns and R
2077     //      rows, the matrix is stored identically to a row of S X R row vectors with C
2078     //      components each, according to rule (4).
2079     //
2080     //   9. If the member is a structure, the base alignment of the structure is N , where
2081     //      N is the largest base alignment value of any    of its members, and rounded
2082     //      up to the base alignment of a vec4. The individual members of this substructure
2083     //      are then assigned offsets by applying this set of rules recursively,
2084     //      where the base offset of the first member of the sub-structure is equal to the
2085     //      aligned offset of the structure. The structure may have padding at the end;
2086     //      the base offset of the member following the sub-structure is rounded up to
2087     //      the next multiple of the base alignment of the structure.
2088     //
2089     //   10. If the member is an array of S structures, the S elements of the array are laid
2090     //       out in order, according to rule (9).
2091     //
2092     //   Assuming, for rule 10:  The stride is the same as the size of an element.
2093
2094     stride = 0;
2095     int dummyStride;
2096
2097     // rules 4, 6, 8, and 10
2098     if (type.isArray()) {
2099         // TODO: perf: this might be flattened by using getCumulativeArraySize(), and a deref that discards all arrayness
2100         TType derefType(type, 0);
2101         alignment = getBaseAlignment(derefType, size, dummyStride, layoutPacking, rowMajor);
2102         if (std140)
2103             alignment = std::max(baseAlignmentVec4Std140, alignment);
2104         RoundToPow2(size, alignment);
2105         stride = size;  // uses full matrix size for stride of an array of matrices (not quite what rule 6/8, but what's expected)
2106                         // uses the assumption for rule 10 in the comment above
2107         // use one element to represent the last member of SSBO which is unsized array
2108         int arraySize = (type.isUnsizedArray() && (type.getOuterArraySize() == 0)) ? 1 : type.getOuterArraySize();
2109         size = stride * arraySize;
2110         return alignment;
2111     }
2112
2113     // rule 9
2114     if (type.getBasicType() == EbtStruct || type.getBasicType() == EbtBlock) {
2115         const TTypeList& memberList = *type.getStruct();
2116
2117         size = 0;
2118         int maxAlignment = std140 ? baseAlignmentVec4Std140 : 0;
2119         for (size_t m = 0; m < memberList.size(); ++m) {
2120             int memberSize;
2121             // modify just the children's view of matrix layout, if there is one for this member
2122             TLayoutMatrix subMatrixLayout = memberList[m].type->getQualifier().layoutMatrix;
2123             int memberAlignment = getBaseAlignment(*memberList[m].type, memberSize, dummyStride, layoutPacking,
2124                                                    (subMatrixLayout != ElmNone) ? (subMatrixLayout == ElmRowMajor) : rowMajor);
2125             maxAlignment = std::max(maxAlignment, memberAlignment);
2126             RoundToPow2(size, memberAlignment);
2127             size += memberSize;
2128         }
2129
2130         // The structure may have padding at the end; the base offset of
2131         // the member following the sub-structure is rounded up to the next
2132         // multiple of the base alignment of the structure.
2133         RoundToPow2(size, maxAlignment);
2134
2135         return maxAlignment;
2136     }
2137
2138     // rule 1
2139     if (type.isScalar())
2140         return getBaseAlignmentScalar(type, size);
2141
2142     // rules 2 and 3
2143     if (type.isVector()) {
2144         int scalarAlign = getBaseAlignmentScalar(type, size);
2145         switch (type.getVectorSize()) {
2146         case 1: // HLSL has this, GLSL does not
2147             return scalarAlign;
2148         case 2:
2149             size *= 2;
2150             return 2 * scalarAlign;
2151         default:
2152             size *= type.getVectorSize();
2153             return 4 * scalarAlign;
2154         }
2155     }
2156
2157     // rules 5 and 7
2158     if (type.isMatrix()) {
2159         // rule 5: deref to row, not to column, meaning the size of vector is num columns instead of num rows
2160         TType derefType(type, 0, rowMajor);
2161
2162         alignment = getBaseAlignment(derefType, size, dummyStride, layoutPacking, rowMajor);
2163         if (std140)
2164             alignment = std::max(baseAlignmentVec4Std140, alignment);
2165         RoundToPow2(size, alignment);
2166         stride = size;  // use intra-matrix stride for stride of a just a matrix
2167         if (rowMajor)
2168             size = stride * type.getMatrixRows();
2169         else
2170             size = stride * type.getMatrixCols();
2171
2172         return alignment;
2173     }
2174
2175     assert(0);  // all cases should be covered above
2176     size = baseAlignmentVec4Std140;
2177     return baseAlignmentVec4Std140;
2178 }
2179
2180 // To aid the basic HLSL rule about crossing vec4 boundaries.
2181 bool TIntermediate::improperStraddle(const TType& type, int size, int offset)
2182 {
2183     if (! type.isVector() || type.isArray())
2184         return false;
2185
2186     return size <= 16 ? offset / 16 != (offset + size - 1) / 16
2187                       : offset % 16 != 0;
2188 }
2189
2190 int TIntermediate::getScalarAlignment(const TType& type, int& size, int& stride, bool rowMajor)
2191 {
2192     int alignment;
2193
2194     stride = 0;
2195     int dummyStride;
2196
2197     if (type.isArray()) {
2198         TType derefType(type, 0);
2199         alignment = getScalarAlignment(derefType, size, dummyStride, rowMajor);
2200
2201         stride = size;
2202         RoundToPow2(stride, alignment);
2203
2204         size = stride * (type.getOuterArraySize() - 1) + size;
2205         return alignment;
2206     }
2207
2208     if (type.getBasicType() == EbtStruct) {
2209         const TTypeList& memberList = *type.getStruct();
2210
2211         size = 0;
2212         int maxAlignment = 0;
2213         for (size_t m = 0; m < memberList.size(); ++m) {
2214             int memberSize;
2215             // modify just the children's view of matrix layout, if there is one for this member
2216             TLayoutMatrix subMatrixLayout = memberList[m].type->getQualifier().layoutMatrix;
2217             int memberAlignment = getScalarAlignment(*memberList[m].type, memberSize, dummyStride,
2218                                                      (subMatrixLayout != ElmNone) ? (subMatrixLayout == ElmRowMajor) : rowMajor);
2219             maxAlignment = std::max(maxAlignment, memberAlignment);
2220             RoundToPow2(size, memberAlignment);
2221             size += memberSize;
2222         }
2223
2224         return maxAlignment;
2225     }
2226
2227     if (type.isScalar())
2228         return getBaseAlignmentScalar(type, size);
2229
2230     if (type.isVector()) {
2231         int scalarAlign = getBaseAlignmentScalar(type, size);
2232
2233         size *= type.getVectorSize();
2234         return scalarAlign;
2235     }
2236
2237     if (type.isMatrix()) {
2238         TType derefType(type, 0, rowMajor);
2239
2240         alignment = getScalarAlignment(derefType, size, dummyStride, rowMajor);
2241
2242         stride = size;  // use intra-matrix stride for stride of a just a matrix
2243         if (rowMajor)
2244             size = stride * type.getMatrixRows();
2245         else
2246             size = stride * type.getMatrixCols();
2247
2248         return alignment;
2249     }
2250
2251     assert(0);  // all cases should be covered above
2252     size = 1;
2253     return 1;
2254 }
2255
2256 int TIntermediate::getMemberAlignment(const TType& type, int& size, int& stride, TLayoutPacking layoutPacking, bool rowMajor)
2257 {
2258     if (layoutPacking == glslang::ElpScalar) {
2259         return getScalarAlignment(type, size, stride, rowMajor);
2260     } else {
2261         return getBaseAlignment(type, size, stride, layoutPacking, rowMajor);
2262     }
2263 }
2264
2265 // shared calculation by getOffset and getOffsets
2266 void TIntermediate::updateOffset(const TType& parentType, const TType& memberType, int& offset, int& memberSize)
2267 {
2268     int dummyStride;
2269
2270     // modify just the children's view of matrix layout, if there is one for this member
2271     TLayoutMatrix subMatrixLayout = memberType.getQualifier().layoutMatrix;
2272     int memberAlignment = getMemberAlignment(memberType, memberSize, dummyStride,
2273                                              parentType.getQualifier().layoutPacking,
2274                                              subMatrixLayout != ElmNone
2275                                                  ? subMatrixLayout == ElmRowMajor
2276                                                  : parentType.getQualifier().layoutMatrix == ElmRowMajor);
2277     RoundToPow2(offset, memberAlignment);
2278 }
2279
2280 // Lookup or calculate the offset of a block member, using the recursively
2281 // defined block offset rules.
2282 int TIntermediate::getOffset(const TType& type, int index)
2283 {
2284     const TTypeList& memberList = *type.getStruct();
2285
2286     // Don't calculate offset if one is present, it could be user supplied
2287     // and different than what would be calculated.  That is, this is faster,
2288     // but not just an optimization.
2289     if (memberList[index].type->getQualifier().hasOffset())
2290         return memberList[index].type->getQualifier().layoutOffset;
2291
2292     int memberSize = 0;
2293     int offset = 0;
2294     for (int m = 0; m <= index; ++m) {
2295         updateOffset(type, *memberList[m].type, offset, memberSize);
2296
2297         if (m < index)
2298             offset += memberSize;
2299     }
2300
2301     return offset;
2302 }
2303
2304 // Calculate the block data size.
2305 // Block arrayness is not taken into account, each element is backed by a separate buffer.
2306 int TIntermediate::getBlockSize(const TType& blockType)
2307 {
2308     const TTypeList& memberList = *blockType.getStruct();
2309     int lastIndex = (int)memberList.size() - 1;
2310     int lastOffset = getOffset(blockType, lastIndex);
2311
2312     int lastMemberSize;
2313     int dummyStride;
2314     getMemberAlignment(*memberList[lastIndex].type, lastMemberSize, dummyStride,
2315                        blockType.getQualifier().layoutPacking,
2316                        blockType.getQualifier().layoutMatrix == ElmRowMajor);
2317
2318     return lastOffset + lastMemberSize;
2319 }
2320
2321 int TIntermediate::computeBufferReferenceTypeSize(const TType& type)
2322 {
2323     assert(type.isReference());
2324     int size = getBlockSize(*type.getReferentType());
2325
2326     int align = type.getBufferReferenceAlignment();
2327
2328     if (align) {
2329         size = (size + align - 1) & ~(align-1);
2330     }
2331
2332     return size;
2333 }
2334
2335 #ifndef GLSLANG_WEB
2336 bool TIntermediate::isIoResizeArray(const TType& type, EShLanguage language) {
2337     return type.isArray() &&
2338             ((language == EShLangGeometry    && type.getQualifier().storage == EvqVaryingIn) ||
2339             (language == EShLangTessControl && (type.getQualifier().storage == EvqVaryingIn || type.getQualifier().storage == EvqVaryingOut) &&
2340                 ! type.getQualifier().patch) ||
2341             (language == EShLangTessEvaluation && type.getQualifier().storage == EvqVaryingIn) ||
2342             (language == EShLangFragment && type.getQualifier().storage == EvqVaryingIn &&
2343              (type.getQualifier().pervertexNV || type.getQualifier().pervertexEXT)) ||
2344             (language == EShLangMesh && type.getQualifier().storage == EvqVaryingOut &&
2345                 !type.getQualifier().perTaskNV));
2346 }
2347 #endif // not GLSLANG_WEB
2348
2349 } // end namespace glslang