glslang/MachineIndependent/linkValidate.cpp

   1 //
   2 //Copyright (C) 2013 LunarG, Inc.
   3 //
   4 //All rights reserved.
   5 //
   6 //Redistribution and use in source and binary forms, with or without
   7 //modification, are permitted provided that the following conditions
   8 //are met:
   9 //
  10 //    Redistributions of source code must retain the above copyright
  11 //    notice, this list of conditions and the following disclaimer.
  12 //
  13 //    Redistributions in binary form must reproduce the above
  14 //    copyright notice, this list of conditions and the following
  15 //    disclaimer in the documentation and/or other materials provided
  16 //    with the distribution.
  17 //
  18 //    Neither the name of 3Dlabs Inc. Ltd. nor the names of its
  19 //    contributors may be used to endorse or promote products derived
  20 //    from this software without specific prior written permission.
  21 //
  22 //THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  23 //"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  24 //LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  25 //FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  26 //COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  27 //INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  28 //BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  29 //LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  30 //CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31 //LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  32 //ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  33 //POSSIBILITY OF SUCH DAMAGE.
  34 //
  35
  36 //
  37 // Do link-time merging and validation of intermediate representations.
  38 //
  39 // Basic model is that during compilation, each compilation unit (shader) is
  40 // compiled into one TIntermediate instance.  Then, at link time, multiple
  41 // units for the same stage can be merged together, which can generate errors.
  42 // Then, after all merging, a single instance of TIntermediate represents
  43 // the whole stage.  A final error check can be done on the resulting stage,
  44 // even if no merging was done (i.e., the stage was only one compilation unit).
  45 //
  46
  47 #include "localintermediate.h"
  48 #include "../Include/InfoSink.h"
  49
  50 namespace glslang {
  51
  52 //
  53 // Link-time error emitter.
  54 //
  55 void TIntermediate::error(TInfoSink& infoSink, const char* message)
  56 {
  57     infoSink.info.prefix(EPrefixError);
  58     infoSink.info << "Linking " << StageName(language) << " stage: " << message << "\n";
  59
  60     ++numErrors;
  61 }
  62
  63 // TODO: 4.4 offset/align:  "Two blocks linked together in the same program with the same block
  64 // name must have the exact same set of members qualified with offset and their integral-constant
  65 // expression values must be the same, or a link-time error results."
  66
  67 //
  68 // Merge the information from 'unit' into 'this'
  69 //
  70 void TIntermediate::merge(TInfoSink& infoSink, TIntermediate& unit)
  71 {
  72     if (source == EShSourceNone)
  73         source = unit.source;
  74
  75     if (source != unit.source)
  76         error(infoSink, "can't link compilation units from different source languages");
  77
  78     if (source == EShSourceHlsl && unit.entryPoint.size() > 0) {
  79         if (entryPoint.size() > 0)
  80             error(infoSink, "can't handle multiple entry points per stage");
  81         else
  82             entryPoint = unit.entryPoint;
  83     }
  84     numMains += unit.numMains;
  85     numErrors += unit.numErrors;
  86     numPushConstants += unit.numPushConstants;
  87     callGraph.insert(callGraph.end(), unit.callGraph.begin(), unit.callGraph.end());
  88
  89     if (originUpperLeft != unit.originUpperLeft || pixelCenterInteger != unit.pixelCenterInteger)
  90         error(infoSink, "gl_FragCoord redeclarations must match across shaders\n");
  91
  92     if (! earlyFragmentTests)
  93         earlyFragmentTests = unit.earlyFragmentTests;
  94
  95     if (depthLayout == EldNone)
  96         depthLayout = unit.depthLayout;
  97     else if (depthLayout != unit.depthLayout)
  98         error(infoSink, "Contradictory depth layouts");
  99
 100     blendEquations |= unit.blendEquations;
 101
 102     if (inputPrimitive == ElgNone)
 103         inputPrimitive = unit.inputPrimitive;
 104     else if (inputPrimitive != unit.inputPrimitive)
 105         error(infoSink, "Contradictory input layout primitives");
 106
 107     if (outputPrimitive == ElgNone)
 108         outputPrimitive = unit.outputPrimitive;
 109     else if (outputPrimitive != unit.outputPrimitive)
 110         error(infoSink, "Contradictory output layout primitives");
 111
 112     if (vertices == TQualifier::layoutNotSet)
 113         vertices = unit.vertices;
 114     else if (vertices != unit.vertices) {
 115         if (language == EShLangGeometry)
 116             error(infoSink, "Contradictory layout max_vertices values");
 117         else if (language == EShLangTessControl)
 118             error(infoSink, "Contradictory layout vertices values");
 119         else
 120             assert(0);
 121     }
 122
 123     if (vertexSpacing == EvsNone)
 124         vertexSpacing = unit.vertexSpacing;
 125     else if (vertexSpacing != unit.vertexSpacing)
 126         error(infoSink, "Contradictory input vertex spacing");
 127
 128     if (vertexOrder == EvoNone)
 129         vertexOrder = unit.vertexOrder;
 130     else if (vertexOrder != unit.vertexOrder)
 131         error(infoSink, "Contradictory triangle ordering");
 132
 133     if (unit.pointMode)
 134         pointMode = true;
 135
 136     for (int i = 0; i < 3; ++i) {
 137         if (localSize[i] > 1)
 138             localSize[i] = unit.localSize[i];
 139         else if (localSize[i] != unit.localSize[i])
 140             error(infoSink, "Contradictory local size");
 141
 142         if (localSizeSpecId[i] != TQualifier::layoutNotSet)
 143             localSizeSpecId[i] = unit.localSizeSpecId[i];
 144         else if (localSizeSpecId[i] != unit.localSizeSpecId[i])
 145             error(infoSink, "Contradictory local size specialization ids");
 146     }
 147
 148     if (unit.xfbMode)
 149         xfbMode = true;
 150     for (size_t b = 0; b < xfbBuffers.size(); ++b) {
 151         if (xfbBuffers[b].stride == TQualifier::layoutXfbStrideEnd)
 152             xfbBuffers[b].stride = unit.xfbBuffers[b].stride;
 153         else if (xfbBuffers[b].stride != unit.xfbBuffers[b].stride)
 154             error(infoSink, "Contradictory xfb_stride");
 155         xfbBuffers[b].implicitStride = std::max(xfbBuffers[b].implicitStride, unit.xfbBuffers[b].implicitStride);
 156         if (unit.xfbBuffers[b].containsDouble)
 157             xfbBuffers[b].containsDouble = true;
 158         // TODO: 4.4 link: enhanced layouts: compare ranges
 159     }
 160
 161     if (unit.treeRoot == 0)
 162         return;
 163
 164     if (treeRoot == 0) {
 165         treeRoot = unit.treeRoot;
 166         version = unit.version;
 167         requestedExtensions = unit.requestedExtensions;
 168         return;
 169     }
 170
 171     // Getting this far means we have two existing trees to merge...
 172
 173     version = std::max(version, unit.version);
 174     requestedExtensions.insert(unit.requestedExtensions.begin(), unit.requestedExtensions.end());
 175
 176     // Get the top-level globals of each unit
 177     TIntermSequence& globals = treeRoot->getAsAggregate()->getSequence();
 178     TIntermSequence& unitGlobals = unit.treeRoot->getAsAggregate()->getSequence();
 179
 180     // Get the linker-object lists
 181     TIntermSequence& linkerObjects = findLinkerObjects();
 182     TIntermSequence& unitLinkerObjects = unit.findLinkerObjects();
 183
 184     mergeBodies(infoSink, globals, unitGlobals);
 185     mergeLinkerObjects(infoSink, linkerObjects, unitLinkerObjects);
 186
 187     ioAccessed.insert(unit.ioAccessed.begin(), unit.ioAccessed.end());
 188 }
 189
 190 //
 191 // Merge the function bodies and global-level initializers from unitGlobals into globals.
 192 // Will error check duplication of function bodies for the same signature.
 193 //
 194 void TIntermediate::mergeBodies(TInfoSink& infoSink, TIntermSequence& globals, const TIntermSequence& unitGlobals)
 195 {
 196     // TODO: link-time performance: Processing in alphabetical order will be faster
 197
 198     // Error check the global objects, not including the linker objects
 199     for (unsigned int child = 0; child < globals.size() - 1; ++child) {
 200         for (unsigned int unitChild = 0; unitChild < unitGlobals.size() - 1; ++unitChild) {
 201             TIntermAggregate* body = globals[child]->getAsAggregate();
 202             TIntermAggregate* unitBody = unitGlobals[unitChild]->getAsAggregate();
 203             if (body && unitBody && body->getOp() == EOpFunction && unitBody->getOp() == EOpFunction && body->getName() == unitBody->getName()) {
 204                 error(infoSink, "Multiple function bodies in multiple compilation units for the same signature in the same stage:");
 205                 infoSink.info << "    " << globals[child]->getAsAggregate()->getName() << "\n";
 206             }
 207         }
 208     }
 209
 210     // Merge the global objects, just in front of the linker objects
 211     globals.insert(globals.end() - 1, unitGlobals.begin(), unitGlobals.end() - 1);
 212 }
 213
 214 //
 215 // Merge the linker objects from unitLinkerObjects into linkerObjects.
 216 // Duplication is expected and filtered out, but contradictions are an error.
 217 //
 218 void TIntermediate::mergeLinkerObjects(TInfoSink& infoSink, TIntermSequence& linkerObjects, const TIntermSequence& unitLinkerObjects)
 219 {
 220     // Error check and merge the linker objects (duplicates should not be created)
 221     std::size_t initialNumLinkerObjects = linkerObjects.size();
 222     for (unsigned int unitLinkObj = 0; unitLinkObj < unitLinkerObjects.size(); ++unitLinkObj) {
 223         bool merge = true;
 224         for (std::size_t linkObj = 0; linkObj < initialNumLinkerObjects; ++linkObj) {
 225             TIntermSymbol* symbol = linkerObjects[linkObj]->getAsSymbolNode();
 226             TIntermSymbol* unitSymbol = unitLinkerObjects[unitLinkObj]->getAsSymbolNode();
 227             assert(symbol && unitSymbol);
 228             if (symbol->getName() == unitSymbol->getName()) {
 229                 // filter out copy
 230                 merge = false;
 231
 232                 // but if one has an initializer and the other does not, update
 233                 // the initializer
 234                 if (symbol->getConstArray().empty() && ! unitSymbol->getConstArray().empty())
 235                     symbol->setConstArray(unitSymbol->getConstArray());
 236
 237                 // Similarly for binding
 238                 if (! symbol->getQualifier().hasBinding() && unitSymbol->getQualifier().hasBinding())
 239                     symbol->getQualifier().layoutBinding = unitSymbol->getQualifier().layoutBinding;
 240
 241                 // Update implicit array sizes
 242                 mergeImplicitArraySizes(symbol->getWritableType(), unitSymbol->getType());
 243
 244                 // Check for consistent types/qualification/initializers etc.
 245                 mergeErrorCheck(infoSink, *symbol, *unitSymbol, false);
 246             }
 247         }
 248         if (merge)
 249             linkerObjects.push_back(unitLinkerObjects[unitLinkObj]);
 250     }
 251 }
 252
 253 // TODO 4.5 link functionality: cull distance array size checking
 254
 255 // Recursively merge the implicit array sizes through the objects' respective type trees.
 256 void TIntermediate::mergeImplicitArraySizes(TType& type, const TType& unitType)
 257 {
 258     if (type.isImplicitlySizedArray() && unitType.isArray()) {
 259         int newImplicitArraySize = unitType.isImplicitlySizedArray() ? unitType.getImplicitArraySize() : unitType.getOuterArraySize();
 260         if (newImplicitArraySize > type.getImplicitArraySize ())
 261             type.setImplicitArraySize(newImplicitArraySize);
 262     }
 263
 264     // Type mismatches are caught and reported after this, just be careful for now.
 265     if (! type.isStruct() || ! unitType.isStruct() || type.getStruct()->size() != unitType.getStruct()->size())
 266         return;
 267
 268     for (int i = 0; i < (int)type.getStruct()->size(); ++i)
 269         mergeImplicitArraySizes(*(*type.getStruct())[i].type, *(*unitType.getStruct())[i].type);
 270 }
 271
 272 //
 273 // Compare two global objects from two compilation units and see if they match
 274 // well enough.  Rules can be different for intra- vs. cross-stage matching.
 275 //
 276 // This function only does one of intra- or cross-stage matching per call.
 277 //
 278 void TIntermediate::mergeErrorCheck(TInfoSink& infoSink, const TIntermSymbol& symbol, const TIntermSymbol& unitSymbol, bool crossStage)
 279 {
 280     bool writeTypeComparison = false;
 281
 282     // Types have to match
 283     if (symbol.getType() != unitSymbol.getType()) {
 284         error(infoSink, "Types must match:");
 285         writeTypeComparison = true;
 286     }
 287
 288     // Qualifiers have to (almost) match
 289
 290     // Storage...
 291     if (symbol.getQualifier().storage != unitSymbol.getQualifier().storage) {
 292         error(infoSink, "Storage qualifiers must match:");
 293         writeTypeComparison = true;
 294     }
 295
 296     // Precision...
 297     if (symbol.getQualifier().precision != unitSymbol.getQualifier().precision) {
 298         error(infoSink, "Precision qualifiers must match:");
 299         writeTypeComparison = true;
 300     }
 301
 302     // Invariance...
 303     if (! crossStage && symbol.getQualifier().invariant != unitSymbol.getQualifier().invariant) {
 304         error(infoSink, "Presence of invariant qualifier must match:");
 305         writeTypeComparison = true;
 306     }
 307
 308     // Precise...
 309     if (! crossStage && symbol.getQualifier().noContraction != unitSymbol.getQualifier().noContraction) {
 310         error(infoSink, "Presence of precise qualifier must match:");
 311         writeTypeComparison = true;
 312     }
 313
 314     // Auxiliary and interpolation...
 315     if (symbol.getQualifier().centroid  != unitSymbol.getQualifier().centroid ||
 316         symbol.getQualifier().smooth    != unitSymbol.getQualifier().smooth ||
 317         symbol.getQualifier().flat      != unitSymbol.getQualifier().flat ||
 318         symbol.getQualifier().sample    != unitSymbol.getQualifier().sample ||
 319         symbol.getQualifier().patch     != unitSymbol.getQualifier().patch ||
 320         symbol.getQualifier().nopersp   != unitSymbol.getQualifier().nopersp) {
 321         error(infoSink, "Interpolation and auxiliary storage qualifiers must match:");
 322         writeTypeComparison = true;
 323     }
 324
 325     // Memory...
 326     if (symbol.getQualifier().coherent  != unitSymbol.getQualifier().coherent ||
 327         symbol.getQualifier().volatil   != unitSymbol.getQualifier().volatil ||
 328         symbol.getQualifier().restrict  != unitSymbol.getQualifier().restrict ||
 329         symbol.getQualifier().readonly  != unitSymbol.getQualifier().readonly ||
 330         symbol.getQualifier().writeonly != unitSymbol.getQualifier().writeonly) {
 331         error(infoSink, "Memory qualifiers must match:");
 332         writeTypeComparison = true;
 333     }
 334
 335     // Layouts...
 336     // TODO: 4.4 enhanced layouts: Generalize to include offset/align: current spec
 337     //       requires separate user-supplied offset from actual computed offset, but
 338     //       current implementation only has one offset.
 339     if (symbol.getQualifier().layoutMatrix    != unitSymbol.getQualifier().layoutMatrix ||
 340         symbol.getQualifier().layoutPacking   != unitSymbol.getQualifier().layoutPacking ||
 341         symbol.getQualifier().layoutLocation  != unitSymbol.getQualifier().layoutLocation ||
 342         symbol.getQualifier().layoutComponent != unitSymbol.getQualifier().layoutComponent ||
 343         symbol.getQualifier().layoutIndex     != unitSymbol.getQualifier().layoutIndex ||
 344         symbol.getQualifier().layoutBinding   != unitSymbol.getQualifier().layoutBinding ||
 345         (symbol.getQualifier().hasBinding() && (symbol.getQualifier().layoutOffset != unitSymbol.getQualifier().layoutOffset))) {
 346         error(infoSink, "Layout qualification must match:");
 347         writeTypeComparison = true;
 348     }
 349
 350     // Initializers have to match, if both are present, and if we don't already know the types don't match
 351     if (! writeTypeComparison) {
 352         if (! symbol.getConstArray().empty() && ! unitSymbol.getConstArray().empty()) {
 353             if (symbol.getConstArray() != unitSymbol.getConstArray()) {
 354                 error(infoSink, "Initializers must match:");
 355                 infoSink.info << "    " << symbol.getName() << "\n";
 356             }
 357         }
 358     }
 359
 360     if (writeTypeComparison)
 361         infoSink.info << "    " << symbol.getName() << ": \"" << symbol.getType().getCompleteString() << "\" versus \"" <<
 362                                                              unitSymbol.getType().getCompleteString() << "\"\n";
 363 }
 364
 365 //
 366 // Do final link-time error checking of a complete (merged) intermediate representation.
 367 // (Much error checking was done during merging).
 368 //
 369 // Also, lock in defaults of things not set, including array sizes.
 370 //
 371 void TIntermediate::finalCheck(TInfoSink& infoSink)
 372 {
 373     if (source == EShSourceGlsl && numMains < 1)
 374         error(infoSink, "Missing entry point: Each stage requires one \"void main()\" entry point");
 375
 376     if (numPushConstants > 1)
 377         error(infoSink, "Only one push_constant block is allowed per stage");
 378
 379     // recursion checking
 380     checkCallGraphCycles(infoSink);
 381
 382     // overlap/alias/missing I/O, etc.
 383     inOutLocationCheck(infoSink);
 384
 385     // invocations
 386     if (invocations == TQualifier::layoutNotSet)
 387         invocations = 1;
 388
 389     if (inIoAccessed("gl_ClipDistance") && inIoAccessed("gl_ClipVertex"))
 390         error(infoSink, "Can only use one of gl_ClipDistance or gl_ClipVertex (gl_ClipDistance is preferred)");
 391     if (inIoAccessed("gl_CullDistance") && inIoAccessed("gl_ClipVertex"))
 392         error(infoSink, "Can only use one of gl_CullDistance or gl_ClipVertex (gl_ClipDistance is preferred)");
 393
 394     if (userOutputUsed() && (inIoAccessed("gl_FragColor") || inIoAccessed("gl_FragData")))
 395         error(infoSink, "Cannot use gl_FragColor or gl_FragData when using user-defined outputs");
 396     if (inIoAccessed("gl_FragColor") && inIoAccessed("gl_FragData"))
 397         error(infoSink, "Cannot use both gl_FragColor and gl_FragData");
 398
 399     for (size_t b = 0; b < xfbBuffers.size(); ++b) {
 400         if (xfbBuffers[b].containsDouble)
 401             RoundToPow2(xfbBuffers[b].implicitStride, 8);
 402
 403         // "It is a compile-time or link-time error to have
 404         // any xfb_offset that overflows xfb_stride, whether stated on declarations before or after the xfb_stride, or
 405         // in different compilation units. While xfb_stride can be declared multiple times for the same buffer, it is a
 406         // compile-time or link-time error to have different values specified for the stride for the same buffer."
 407         if (xfbBuffers[b].stride != TQualifier::layoutXfbStrideEnd && xfbBuffers[b].implicitStride > xfbBuffers[b].stride) {
 408             error(infoSink, "xfb_stride is too small to hold all buffer entries:");
 409             infoSink.info.prefix(EPrefixError);
 410             infoSink.info << "    xfb_buffer " << (unsigned int)b << ", xfb_stride " << xfbBuffers[b].stride << ", minimum stride needed: " << xfbBuffers[b].implicitStride << "\n";
 411         }
 412         if (xfbBuffers[b].stride == TQualifier::layoutXfbStrideEnd)
 413             xfbBuffers[b].stride = xfbBuffers[b].implicitStride;
 414
 415         // "If the buffer is capturing any
 416         // outputs with double-precision components, the stride must be a multiple of 8, otherwise it must be a
 417         // multiple of 4, or a compile-time or link-time error results."
 418         if (xfbBuffers[b].containsDouble && ! IsMultipleOfPow2(xfbBuffers[b].stride, 8)) {
 419             error(infoSink, "xfb_stride must be multiple of 8 for buffer holding a double:");
 420             infoSink.info.prefix(EPrefixError);
 421             infoSink.info << "    xfb_buffer " << (unsigned int)b << ", xfb_stride " << xfbBuffers[b].stride << "\n";
 422         } else if (! IsMultipleOfPow2(xfbBuffers[b].stride, 4)) {
 423             error(infoSink, "xfb_stride must be multiple of 4:");
 424             infoSink.info.prefix(EPrefixError);
 425             infoSink.info << "    xfb_buffer " << (unsigned int)b << ", xfb_stride " << xfbBuffers[b].stride << "\n";
 426         }
 427
 428         // "The resulting stride (implicit or explicit), when divided by 4, must be less than or equal to the
 429         // implementation-dependent constant gl_MaxTransformFeedbackInterleavedComponents."
 430         if (xfbBuffers[b].stride > (unsigned int)(4 * resources.maxTransformFeedbackInterleavedComponents)) {
 431             error(infoSink, "xfb_stride is too large:");
 432             infoSink.info.prefix(EPrefixError);
 433             infoSink.info << "    xfb_buffer " << (unsigned int)b << ", components (1/4 stride) needed are " << xfbBuffers[b].stride/4 << ", gl_MaxTransformFeedbackInterleavedComponents is " << resources.maxTransformFeedbackInterleavedComponents << "\n";
 434         }
 435     }
 436
 437     switch (language) {
 438     case EShLangVertex:
 439         break;
 440     case EShLangTessControl:
 441         if (vertices == TQualifier::layoutNotSet)
 442             error(infoSink, "At least one shader must specify an output layout(vertices=...)");
 443         break;
 444     case EShLangTessEvaluation:
 445         if (inputPrimitive == ElgNone)
 446             error(infoSink, "At least one shader must specify an input layout primitive");
 447         if (vertexSpacing == EvsNone)
 448             vertexSpacing = EvsEqual;
 449         if (vertexOrder == EvoNone)
 450             vertexOrder = EvoCcw;
 451         break;
 452     case EShLangGeometry:
 453         if (inputPrimitive == ElgNone)
 454             error(infoSink, "At least one shader must specify an input layout primitive");
 455         if (outputPrimitive == ElgNone)
 456             error(infoSink, "At least one shader must specify an output layout primitive");
 457         if (vertices == TQualifier::layoutNotSet)
 458             error(infoSink, "At least one shader must specify a layout(max_vertices = value)");
 459         break;
 460     case EShLangFragment:
 461         break;
 462     case EShLangCompute:
 463         break;
 464     default:
 465         error(infoSink, "Unknown Stage.");
 466         break;
 467     }
 468
 469     // Process the tree for any node-specific work.
 470     class TFinalLinkTraverser : public TIntermTraverser {
 471     public:
 472         TFinalLinkTraverser() { }
 473         virtual ~TFinalLinkTraverser() { }
 474
 475         virtual void visitSymbol(TIntermSymbol* symbol)
 476         {
 477             // Implicitly size arrays.
 478             symbol->getWritableType().adoptImplicitArraySizes();
 479         }
 480     } finalLinkTraverser;
 481
 482     treeRoot->traverse(&finalLinkTraverser);
 483 }
 484
 485 //
 486 // See if the call graph contains any static recursion, which is disallowed
 487 // by the specification.
 488 //
 489 void TIntermediate::checkCallGraphCycles(TInfoSink& infoSink)
 490 {
 491     // Reset everything, once.
 492     for (TGraph::iterator call = callGraph.begin(); call != callGraph.end(); ++call) {
 493         call->visited = false;
 494         call->currentPath = false;
 495         call->errorGiven = false;
 496     }
 497
 498     //
 499     // Loop, looking for a new connected subgraph.  One subgraph is handled per loop iteration.
 500     //
 501
 502     TCall* newRoot;
 503     do {
 504         // See if we have unvisited parts of the graph.
 505         newRoot = 0;
 506         for (TGraph::iterator call = callGraph.begin(); call != callGraph.end(); ++call) {
 507             if (! call->visited) {
 508                 newRoot = &(*call);
 509                 break;
 510             }
 511         }
 512
 513         // If not, we are done.
 514         if (! newRoot)
 515             break;
 516
 517         // Otherwise, we found a new subgraph, process it:
 518         // See what all can be reached by this new root, and if any of
 519         // that is recursive.  This is done by depth-first traversals, seeing
 520         // if a new call is found that was already in the currentPath (a back edge),
 521         // thereby detecting recursion.
 522         std::list<TCall*> stack;
 523         newRoot->currentPath = true; // currentPath will be true iff it is on the stack
 524         stack.push_back(newRoot);
 525         while (! stack.empty()) {
 526             // get a caller
 527             TCall* call = stack.back();
 528
 529             // Add to the stack just one callee.
 530             // This algorithm always terminates, because only !visited and !currentPath causes a push
 531             // and all pushes change currentPath to true, and all pops change visited to true.
 532             TGraph::iterator child = callGraph.begin();
 533             for (; child != callGraph.end(); ++child) {
 534
 535                 // If we already visited this node, its whole subgraph has already been processed, so skip it.
 536                 if (child->visited)
 537                     continue;
 538
 539                 if (call->callee == child->caller) {
 540                     if (child->currentPath) {
 541                         // Then, we found a back edge
 542                         if (! child->errorGiven) {
 543                             error(infoSink, "Recursion detected:");
 544                             infoSink.info << "    " << call->callee << " calling " << child->callee << "\n";
 545                             child->errorGiven = true;
 546                             recursive = true;
 547                         }
 548                     } else {
 549                         child->currentPath = true;
 550                         stack.push_back(&(*child));
 551                         break;
 552                     }
 553                 }
 554             }
 555             if (child == callGraph.end()) {
 556                 // no more callees, we bottomed out, never look at this node again
 557                 stack.back()->currentPath = false;
 558                 stack.back()->visited = true;
 559                 stack.pop_back();
 560             }
 561         }  // end while, meaning nothing left to process in this subtree
 562
 563     } while (newRoot);  // redundant loop check; should always exit via the 'break' above
 564 }
 565
 566 //
 567 // Satisfy rules for location qualifiers on inputs and outputs
 568 //
 569 void TIntermediate::inOutLocationCheck(TInfoSink& infoSink)
 570 {
 571     // ES 3.0 requires all outputs to have location qualifiers if there is more than one output
 572     bool fragOutWithNoLocation = false;
 573     int numFragOut = 0;
 574
 575     // TODO: linker functionality: location collision checking
 576
 577     TIntermSequence& linkObjects = findLinkerObjects();
 578     for (size_t i = 0; i < linkObjects.size(); ++i) {
 579         const TType& type = linkObjects[i]->getAsTyped()->getType();
 580         const TQualifier& qualifier = type.getQualifier();
 581         if (language == EShLangFragment) {
 582             if (qualifier.storage == EvqVaryingOut && qualifier.builtIn == EbvNone) {
 583                 ++numFragOut;
 584                 if (!qualifier.hasAnyLocation())
 585                     fragOutWithNoLocation = true;
 586             }
 587         }
 588     }
 589
 590     if (profile == EEsProfile) {
 591         if (numFragOut > 1 && fragOutWithNoLocation)
 592             error(infoSink, "when more than one fragment shader output, all must have location qualifiers");
 593     }
 594 }
 595
 596 TIntermSequence& TIntermediate::findLinkerObjects() const
 597 {
 598     // Get the top-level globals
 599     TIntermSequence& globals = treeRoot->getAsAggregate()->getSequence();
 600
 601     // Get the last member of the sequences, expected to be the linker-object lists
 602     assert(globals.back()->getAsAggregate()->getOp() == EOpLinkerObjects);
 603
 604     return globals.back()->getAsAggregate()->getSequence();
 605 }
 606
 607 // See if a variable was both a user-declared output and used.
 608 // Note: the spec discusses writing to one, but this looks at read or write, which
 609 // is more useful, and perhaps the spec should be changed to reflect that.
 610 bool TIntermediate::userOutputUsed() const
 611 {
 612     const TIntermSequence& linkerObjects = findLinkerObjects();
 613
 614     bool found = false;
 615     for (size_t i = 0; i < linkerObjects.size(); ++i) {
 616         const TIntermSymbol& symbolNode = *linkerObjects[i]->getAsSymbolNode();
 617         if (symbolNode.getQualifier().storage == EvqVaryingOut &&
 618             symbolNode.getName().compare(0, 3, "gl_") != 0 &&
 619             inIoAccessed(symbolNode.getName())) {
 620             found = true;
 621             break;
 622         }
 623     }
 624
 625     return found;
 626 }
 627
 628 // Accumulate locations used for inputs, outputs, and uniforms, and check for collisions
 629 // as the accumulation is done.
 630 //
 631 // Returns < 0 if no collision, >= 0 if collision and the value returned is a colliding value.
 632 //
 633 // typeCollision is set to true if there is no direct collision, but the types in the same location
 634 // are different.
 635 //
 636 int TIntermediate::addUsedLocation(const TQualifier& qualifier, const TType& type, bool& typeCollision)
 637 {
 638     typeCollision = false;
 639
 640     int set;
 641     if (qualifier.isPipeInput())
 642         set = 0;
 643     else if (qualifier.isPipeOutput())
 644         set = 1;
 645     else if (qualifier.storage == EvqUniform)
 646         set = 2;
 647     else if (qualifier.storage == EvqBuffer)
 648         set = 3;
 649     else
 650         return -1;
 651
 652     int size;
 653     if (qualifier.isUniformOrBuffer()) {
 654         if (type.isArray())
 655             size = type.getCumulativeArraySize();
 656         else
 657             size = 1;
 658     } else {
 659         // Strip off the outer array dimension for those having an extra one.
 660         if (type.isArray() && qualifier.isArrayedIo(language)) {
 661             TType elementType(type, 0);
 662             size = computeTypeLocationSize(elementType);
 663         } else
 664             size = computeTypeLocationSize(type);
 665     }
 666
 667     TRange locationRange(qualifier.layoutLocation, qualifier.layoutLocation + size - 1);
 668     TRange componentRange(0, 3);
 669     if (qualifier.hasComponent()) {
 670         componentRange.start = qualifier.layoutComponent;
 671         componentRange.last = componentRange.start + type.getVectorSize() - 1;
 672     }
 673     TIoRange range(locationRange, componentRange, type.getBasicType(), qualifier.hasIndex() ? qualifier.layoutIndex : 0);
 674
 675     // check for collisions, except for vertex inputs on desktop
 676     if (! (profile != EEsProfile && language == EShLangVertex && qualifier.isPipeInput())) {
 677         for (size_t r = 0; r < usedIo[set].size(); ++r) {
 678             if (range.overlap(usedIo[set][r])) {
 679                 // there is a collision; pick one
 680                 return std::max(locationRange.start, usedIo[set][r].location.start);
 681             } else if (locationRange.overlap(usedIo[set][r].location) && type.getBasicType() != usedIo[set][r].basicType) {
 682                 // aliased-type mismatch
 683                 typeCollision = true;
 684                 return std::max(locationRange.start, usedIo[set][r].location.start);
 685             }
 686         }
 687     }
 688
 689     usedIo[set].push_back(range);
 690
 691     return -1; // no collision
 692 }
 693
 694 // Accumulate locations used for inputs, outputs, and uniforms, and check for collisions
 695 // as the accumulation is done.
 696 //
 697 // Returns < 0 if no collision, >= 0 if collision and the value returned is a colliding value.
 698 //
 699 int TIntermediate::addUsedOffsets(int binding, int offset, int numOffsets)
 700 {
 701     TRange bindingRange(binding, binding);
 702     TRange offsetRange(offset, offset + numOffsets - 1);
 703     TOffsetRange range(bindingRange, offsetRange);
 704
 705     // check for collisions, except for vertex inputs on desktop
 706     for (size_t r = 0; r < usedAtomics.size(); ++r) {
 707         if (range.overlap(usedAtomics[r])) {
 708             // there is a collision; pick one
 709             return std::max(offset, usedAtomics[r].offset.start);
 710         }
 711     }
 712
 713     usedAtomics.push_back(range);
 714
 715     return -1; // no collision
 716 }
 717
 718 // Accumulate used constant_id values.
 719 //
 720 // Return false is one was already used.
 721 bool TIntermediate::addUsedConstantId(int id)
 722 {
 723     if (usedConstantId.find(id) != usedConstantId.end())
 724         return false;
 725
 726     usedConstantId.insert(id);
 727
 728     return true;
 729 }
 730
 731 // Recursively figure out how many locations are used up by an input or output type.
 732 // Return the size of type, as measured by "locations".
 733 int TIntermediate::computeTypeLocationSize(const TType& type) const
 734 {
 735     // "If the declared input is an array of size n and each element takes m locations, it will be assigned m * n
 736     // consecutive locations..."
 737     if (type.isArray()) {
 738         // TODO: perf: this can be flattened by using getCumulativeArraySize(), and a deref that discards all arrayness
 739         TType elementType(type, 0);
 740         if (type.isImplicitlySizedArray()) {
 741             // TODO: are there valid cases of having an implicitly-sized array with a location?  If so, running this code too early.
 742             return computeTypeLocationSize(elementType);
 743         } else
 744             return type.getOuterArraySize() * computeTypeLocationSize(elementType);
 745     }
 746
 747     // "The locations consumed by block and structure members are determined by applying the rules above
 748     // recursively..."
 749     if (type.isStruct()) {
 750         int size = 0;
 751         for (int member = 0; member < (int)type.getStruct()->size(); ++member) {
 752             TType memberType(type, member);
 753             size += computeTypeLocationSize(memberType);
 754         }
 755         return size;
 756     }
 757
 758     // ES: "If a shader input is any scalar or vector type, it will consume a single location."
 759
 760     // Desktop: "If a vertex shader input is any scalar or vector type, it will consume a single location. If a non-vertex
 761     // shader input is a scalar or vector type other than dvec3 or dvec4, it will consume a single location, while
 762     // types dvec3 or dvec4 will consume two consecutive locations. Inputs of type double and dvec2 will
 763     // consume only a single location, in all stages."
 764     if (type.isScalar())
 765         return 1;
 766     if (type.isVector()) {
 767         if (language == EShLangVertex && type.getQualifier().isPipeInput())
 768             return 1;
 769         if (type.getBasicType() == EbtDouble && type.getVectorSize() > 2)
 770             return 2;
 771         else
 772             return 1;
 773     }
 774
 775     // "If the declared input is an n x m single- or double-precision matrix, ...
 776     // The number of locations assigned for each matrix will be the same as
 777     // for an n-element array of m-component vectors..."
 778     if (type.isMatrix()) {
 779         TType columnType(type, 0);
 780         return type.getMatrixCols() * computeTypeLocationSize(columnType);
 781     }
 782
 783     assert(0);
 784     return 1;
 785 }
 786
 787 // Accumulate xfb buffer ranges and check for collisions as the accumulation is done.
 788 //
 789 // Returns < 0 if no collision, >= 0 if collision and the value returned is a colliding value.
 790 //
 791 int TIntermediate::addXfbBufferOffset(const TType& type)
 792 {
 793     const TQualifier& qualifier = type.getQualifier();
 794
 795     assert(qualifier.hasXfbOffset() && qualifier.hasXfbBuffer());
 796     TXfbBuffer& buffer = xfbBuffers[qualifier.layoutXfbBuffer];
 797
 798     // compute the range
 799     unsigned int size = computeTypeXfbSize(type, buffer.containsDouble);
 800     buffer.implicitStride = std::max(buffer.implicitStride, qualifier.layoutXfbOffset + size);
 801     TRange range(qualifier.layoutXfbOffset, qualifier.layoutXfbOffset + size - 1);
 802
 803     // check for collisions
 804     for (size_t r = 0; r < buffer.ranges.size(); ++r) {
 805         if (range.overlap(buffer.ranges[r])) {
 806             // there is a collision; pick an example to return
 807             return std::max(range.start, buffer.ranges[r].start);
 808         }
 809     }
 810
 811     buffer.ranges.push_back(range);
 812
 813     return -1;  // no collision
 814 }
 815
 816 // Recursively figure out how many bytes of xfb buffer are used by the given type.
 817 // Return the size of type, in bytes.
 818 // Sets containsDouble to true if the type contains a double.
 819 // N.B. Caller must set containsDouble to false before calling.
 820 unsigned int TIntermediate::computeTypeXfbSize(const TType& type, bool& containsDouble) const
 821 {
 822     // "...if applied to an aggregate containing a double, the offset must also be a multiple of 8,
 823     // and the space taken in the buffer will be a multiple of 8.
 824     // ...within the qualified entity, subsequent components are each
 825     // assigned, in order, to the next available offset aligned to a multiple of
 826     // that component's size.  Aggregate types are flattened down to the component
 827     // level to get this sequence of components."
 828
 829     if (type.isArray()) {
 830         // TODO: perf: this can be flattened by using getCumulativeArraySize(), and a deref that discards all arrayness
 831         assert(type.isExplicitlySizedArray());
 832         TType elementType(type, 0);
 833         return type.getOuterArraySize() * computeTypeXfbSize(elementType, containsDouble);
 834     }
 835
 836     if (type.isStruct()) {
 837         unsigned int size = 0;
 838         bool structContainsDouble = false;
 839         for (int member = 0; member < (int)type.getStruct()->size(); ++member) {
 840             TType memberType(type, member);
 841             // "... if applied to
 842             // an aggregate containing a double, the offset must also be a multiple of 8,
 843             // and the space taken in the buffer will be a multiple of 8."
 844             bool memberContainsDouble = false;
 845             int memberSize = computeTypeXfbSize(memberType, memberContainsDouble);
 846             if (memberContainsDouble) {
 847                 structContainsDouble = true;
 848                 RoundToPow2(size, 8);
 849             }
 850             size += memberSize;
 851         }
 852
 853         if (structContainsDouble) {
 854             containsDouble = true;
 855             RoundToPow2(size, 8);
 856         }
 857         return size;
 858     }
 859
 860     int numComponents;
 861     if (type.isScalar())
 862         numComponents = 1;
 863     else if (type.isVector())
 864         numComponents = type.getVectorSize();
 865     else if (type.isMatrix())
 866         numComponents = type.getMatrixCols() * type.getMatrixRows();
 867     else {
 868         assert(0);
 869         numComponents = 1;
 870     }
 871
 872     if (type.getBasicType() == EbtDouble) {
 873         containsDouble = true;
 874         return 8 * numComponents;
 875     } else
 876         return 4 * numComponents;
 877 }
 878
 879 const int baseAlignmentVec4Std140 = 16;
 880
 881 // Return the size and alignment of a scalar.
 882 // The size is returned in the 'size' parameter
 883 // Return value is the alignment of the type.
 884 int TIntermediate::getBaseAlignmentScalar(const TType& type, int& size)
 885 {
 886     switch (type.getBasicType()) {
 887     case EbtInt64:
 888     case EbtUint64:
 889     case EbtDouble:  size = 8; return 8;
 890     default:         size = 4; return 4;
 891     }
 892 }
 893
 894 // Implement base-alignment and size rules from section 7.6.2.2 Standard Uniform Block Layout
 895 // Operates recursively.
 896 //
 897 // If std140 is true, it does the rounding up to vec4 size required by std140,
 898 // otherwise it does not, yielding std430 rules.
 899 //
 900 // The size is returned in the 'size' parameter
 901 //
 902 // The stride is only non-0 for arrays or matrices, and is the stride of the
 903 // top-level object nested within the type.  E.g., for an array of matrices,
 904 // it is the distances needed between matrices, despite the rules saying the
 905 // stride comes from the flattening down to vectors.
 906 //
 907 // Return value is the alignment of the type.
 908 int TIntermediate::getBaseAlignment(const TType& type, int& size, int& stride, bool std140, bool rowMajor)
 909 {
 910     int alignment;
 911
 912     // When using the std140 storage layout, structures will be laid out in buffer
 913     // storage with its members stored in monotonically increasing order based on their
 914     // location in the declaration. A structure and each structure member have a base
 915     // offset and a base alignment, from which an aligned offset is computed by rounding
 916     // the base offset up to a multiple of the base alignment. The base offset of the first
 917     // member of a structure is taken from the aligned offset of the structure itself. The
 918     // base offset of all other structure members is derived by taking the offset of the
 919     // last basic machine unit consumed by the previous member and adding one. Each
 920     // structure member is stored in memory at its aligned offset. The members of a top-
 921     // level uniform block are laid out in buffer storage by treating the uniform block as
 922     // a structure with a base offset of zero.
 923     //
 924     //   1. If the member is a scalar consuming N basic machine units, the base alignment is N.
 925     //
 926     //   2. If the member is a two- or four-component vector with components consuming N basic
 927     //      machine units, the base alignment is 2N or 4N, respectively.
 928     //
 929     //   3. If the member is a three-component vector with components consuming N
 930     //      basic machine units, the base alignment is 4N.
 931     //
 932     //   4. If the member is an array of scalars or vectors, the base alignment and array
 933     //      stride are set to match the base alignment of a single array element, according
 934     //      to rules (1), (2), and (3), and rounded up to the base alignment of a vec4. The
 935     //      array may have padding at the end; the base offset of the member following
 936     //      the array is rounded up to the next multiple of the base alignment.
 937     //
 938     //   5. If the member is a column-major matrix with C columns and R rows, the
 939     //      matrix is stored identically to an array of C column vectors with R
 940     //      components each, according to rule (4).
 941     //
 942     //   6. If the member is an array of S column-major matrices with C columns and
 943     //      R rows, the matrix is stored identically to a row of S \ 2 C column vectors
 944     //      with R components each, according to rule (4).
 945     //
 946     //   7. If the member is a row-major matrix with C columns and R rows, the matrix
 947     //      is stored identically to an array of R row vectors with C components each,
 948     //      according to rule (4).
 949     //
 950     //   8. If the member is an array of S row-major matrices with C columns and R
 951     //      rows, the matrix is stored identically to a row of S \ 2 R row vectors with C
 952     //      components each, according to rule (4).
 953     //
 954     //   9. If the member is a structure, the base alignment of the structure is N , where
 955     //      N is the largest base alignment value of any    of its members, and rounded
 956     //      up to the base alignment of a vec4. The individual members of this substructure
 957     //      are then assigned offsets by applying this set of rules recursively,
 958     //      where the base offset of the first member of the sub-structure is equal to the
 959     //      aligned offset of the structure. The structure may have padding at the end;
 960     //      the base offset of the member following the sub-structure is rounded up to
 961     //      the next multiple of the base alignment of the structure.
 962     //
 963     //   10. If the member is an array of S structures, the S elements of the array are laid
 964     //       out in order, according to rule (9).
 965     //
 966     //   Assuming, for rule 10:  The stride is the same as the size of an element.
 967
 968     stride = 0;
 969     int dummyStride;
 970
 971     // rules 4, 6, 8, and 10
 972     if (type.isArray()) {
 973         // TODO: perf: this might be flattened by using getCumulativeArraySize(), and a deref that discards all arrayness
 974         TType derefType(type, 0);
 975         alignment = getBaseAlignment(derefType, size, dummyStride, std140, rowMajor);
 976         if (std140)
 977             alignment = std::max(baseAlignmentVec4Std140, alignment);
 978         RoundToPow2(size, alignment);
 979         stride = size;  // uses full matrix size for stride of an array of matrices (not quite what rule 6/8, but what's expected)
 980                         // uses the assumption for rule 10 in the comment above
 981         size = stride * type.getOuterArraySize();
 982         return alignment;
 983     }
 984
 985     // rule 9
 986     if (type.getBasicType() == EbtStruct) {
 987         const TTypeList& memberList = *type.getStruct();
 988
 989         size = 0;
 990         int maxAlignment = std140 ? baseAlignmentVec4Std140 : 0;
 991         for (size_t m = 0; m < memberList.size(); ++m) {
 992             int memberSize;
 993             // modify just the children's view of matrix layout, if there is one for this member
 994             TLayoutMatrix subMatrixLayout = memberList[m].type->getQualifier().layoutMatrix;
 995             int memberAlignment = getBaseAlignment(*memberList[m].type, memberSize, dummyStride, std140,
 996                                                    (subMatrixLayout != ElmNone) ? (subMatrixLayout == ElmRowMajor) : rowMajor);
 997             maxAlignment = std::max(maxAlignment, memberAlignment);
 998             RoundToPow2(size, memberAlignment);
 999             size += memberSize;
1000         }
1001
1002         // The structure may have padding at the end; the base offset of
1003         // the member following the sub-structure is rounded up to the next
1004         // multiple of the base alignment of the structure.
1005         RoundToPow2(size, maxAlignment);
1006
1007         return maxAlignment;
1008     }
1009
1010     // rule 1
1011     if (type.isScalar())
1012         return getBaseAlignmentScalar(type, size);
1013
1014     // rules 2 and 3
1015     if (type.isVector()) {
1016         int scalarAlign = getBaseAlignmentScalar(type, size);
1017         switch (type.getVectorSize()) {
1018         case 2:
1019             size *= 2;
1020             return 2 * scalarAlign;
1021         default:
1022             size *= type.getVectorSize();
1023             return 4 * scalarAlign;
1024         }
1025     }
1026
1027     // rules 5 and 7
1028     if (type.isMatrix()) {
1029         // rule 5: deref to row, not to column, meaning the size of vector is num columns instead of num rows
1030         TType derefType(type, 0, rowMajor);
1031
1032         alignment = getBaseAlignment(derefType, size, dummyStride, std140, rowMajor);
1033         if (std140)
1034             alignment = std::max(baseAlignmentVec4Std140, alignment);
1035         RoundToPow2(size, alignment);
1036         stride = size;  // use intra-matrix stride for stride of a just a matrix
1037         if (rowMajor)
1038             size = stride * type.getMatrixRows();
1039         else
1040             size = stride * type.getMatrixCols();
1041
1042         return alignment;
1043     }
1044
1045     assert(0);  // all cases should be covered above
1046     size = baseAlignmentVec4Std140;
1047     return baseAlignmentVec4Std140;
1048 }
1049
1050 } // end namespace glslang