src/OpenGL/compiler/ValidateLimitations.cpp

   1 //
   2 // Copyright (c) 2002-2012 The ANGLE Project Authors. All rights reserved.
   3 // Use of this source code is governed by a BSD-style license that can be
   4 // found in the LICENSE file.
   5 //
   6
   7 #include "ValidateLimitations.h"
   8 #include "InfoSink.h"
   9 #include "InitializeParseContext.h"
  10 #include "ParseHelper.h"
  11
  12 namespace {
  13 bool IsLoopIndex(const TIntermSymbol* symbol, const TLoopStack& stack) {
  14     for (TLoopStack::const_iterator i = stack.begin(); i != stack.end(); ++i) {
  15         if (i->index.id == symbol->getId())
  16             return true;
  17     }
  18     return false;
  19 }
  20
  21 void MarkLoopForUnroll(const TIntermSymbol* symbol, TLoopStack& stack) {
  22     for (TLoopStack::iterator i = stack.begin(); i != stack.end(); ++i) {
  23         if (i->index.id == symbol->getId()) {
  24             ASSERT(i->loop != NULL);
  25             i->loop->setUnrollFlag(true);
  26             return;
  27         }
  28     }
  29     UNREACHABLE();
  30 }
  31
  32 // Traverses a node to check if it represents a constant index expression.
  33 // Definition:
  34 // constant-index-expressions are a superset of constant-expressions.
  35 // Constant-index-expressions can include loop indices as defined in
  36 // GLSL ES 1.0 spec, Appendix A, section 4.
  37 // The following are constant-index-expressions:
  38 // - Constant expressions
  39 // - Loop indices as defined in section 4
  40 // - Expressions composed of both of the above
  41 class ValidateConstIndexExpr : public TIntermTraverser {
  42 public:
  43     ValidateConstIndexExpr(const TLoopStack& stack)
  44         : mValid(true), mLoopStack(stack) {}
  45
  46     // Returns true if the parsed node represents a constant index expression.
  47     bool isValid() const { return mValid; }
  48
  49     virtual void visitSymbol(TIntermSymbol* symbol) {
  50         // Only constants and loop indices are allowed in a
  51         // constant index expression.
  52         if (mValid) {
  53             mValid = (symbol->getQualifier() == EvqConst) ||
  54                      IsLoopIndex(symbol, mLoopStack);
  55         }
  56     }
  57
  58 private:
  59     bool mValid;
  60     const TLoopStack& mLoopStack;
  61 };
  62
  63 // Traverses a node to check if it uses a loop index.
  64 // If an int loop index is used in its body as a sampler array index,
  65 // mark the loop for unroll.
  66 class ValidateLoopIndexExpr : public TIntermTraverser {
  67 public:
  68     ValidateLoopIndexExpr(TLoopStack& stack)
  69         : mUsesFloatLoopIndex(false),
  70           mUsesIntLoopIndex(false),
  71           mLoopStack(stack) {}
  72
  73     bool usesFloatLoopIndex() const { return mUsesFloatLoopIndex; }
  74     bool usesIntLoopIndex() const { return mUsesIntLoopIndex; }
  75
  76     virtual void visitSymbol(TIntermSymbol* symbol) {
  77         if (IsLoopIndex(symbol, mLoopStack)) {
  78             switch (symbol->getBasicType()) {
  79               case EbtFloat:
  80                 mUsesFloatLoopIndex = true;
  81                 break;
  82               case EbtInt:
  83                 mUsesIntLoopIndex = true;
  84                 MarkLoopForUnroll(symbol, mLoopStack);
  85                 break;
  86               default:
  87                 UNREACHABLE();
  88             }
  89         }
  90     }
  91
  92 private:
  93     bool mUsesFloatLoopIndex;
  94     bool mUsesIntLoopIndex;
  95     TLoopStack& mLoopStack;
  96 };
  97 }  // namespace
  98
  99 ValidateLimitations::ValidateLimitations(ShShaderType shaderType,
 100                                          TInfoSinkBase& sink)
 101     : mShaderType(shaderType),
 102       mSink(sink),
 103       mNumErrors(0)
 104 {
 105 }
 106
 107 bool ValidateLimitations::visitBinary(Visit, TIntermBinary* node)
 108 {
 109     // Check if loop index is modified in the loop body.
 110     validateOperation(node, node->getLeft());
 111
 112     // Check indexing.
 113     switch (node->getOp()) {
 114       case EOpIndexDirect:
 115         validateIndexing(node);
 116         break;
 117       case EOpIndexIndirect:
 118 #if defined(__APPLE__)
 119         // Loop unrolling is a work-around for a Mac Cg compiler bug where it
 120         // crashes when a sampler array's index is also the loop index.
 121         // Once Apple fixes this bug, we should remove the code in this CL.
 122         // See http://codereview.appspot.com/4331048/.
 123         if ((node->getLeft() != NULL) && (node->getRight() != NULL) &&
 124             (node->getLeft()->getAsSymbolNode())) {
 125             TIntermSymbol* symbol = node->getLeft()->getAsSymbolNode();
 126             if (IsSampler(symbol->getBasicType()) && symbol->isArray()) {
 127                 ValidateLoopIndexExpr validate(mLoopStack);
 128                 node->getRight()->traverse(&validate);
 129                 if (validate.usesFloatLoopIndex()) {
 130                     error(node->getLine(),
 131                           "sampler array index is float loop index",
 132                           "for");
 133                 }
 134             }
 135         }
 136 #endif
 137         validateIndexing(node);
 138         break;
 139       default: break;
 140     }
 141     return true;
 142 }
 143
 144 bool ValidateLimitations::visitUnary(Visit, TIntermUnary* node)
 145 {
 146     // Check if loop index is modified in the loop body.
 147     validateOperation(node, node->getOperand());
 148
 149     return true;
 150 }
 151
 152 bool ValidateLimitations::visitAggregate(Visit, TIntermAggregate* node)
 153 {
 154     switch (node->getOp()) {
 155       case EOpFunctionCall:
 156         validateFunctionCall(node);
 157         break;
 158       default:
 159         break;
 160     }
 161     return true;
 162 }
 163
 164 bool ValidateLimitations::visitLoop(Visit, TIntermLoop* node)
 165 {
 166     if (!validateLoopType(node))
 167         return false;
 168
 169     TLoopInfo info;
 170     memset(&info, 0, sizeof(TLoopInfo));
 171     info.loop = node;
 172     if (!validateForLoopHeader(node, &info))
 173         return false;
 174
 175     TIntermNode* body = node->getBody();
 176     if (body != NULL) {
 177         mLoopStack.push_back(info);
 178         body->traverse(this);
 179         mLoopStack.pop_back();
 180     }
 181
 182     // The loop is fully processed - no need to visit children.
 183     return false;
 184 }
 185
 186 void ValidateLimitations::error(TSourceLoc loc,
 187                                 const char *reason, const char* token)
 188 {
 189     mSink.prefix(EPrefixError);
 190     mSink.location(loc);
 191     mSink << "'" << token << "' : " << reason << "\n";
 192     ++mNumErrors;
 193 }
 194
 195 bool ValidateLimitations::withinLoopBody() const
 196 {
 197     return !mLoopStack.empty();
 198 }
 199
 200 bool ValidateLimitations::isLoopIndex(const TIntermSymbol* symbol) const
 201 {
 202     return IsLoopIndex(symbol, mLoopStack);
 203 }
 204
 205 bool ValidateLimitations::validateLoopType(TIntermLoop* node) {
 206     TLoopType type = node->getType();
 207     if (type == ELoopFor)
 208         return true;
 209
 210     // Reject while and do-while loops.
 211     error(node->getLine(),
 212           "This type of loop is not allowed",
 213           type == ELoopWhile ? "while" : "do");
 214     return false;
 215 }
 216
 217 bool ValidateLimitations::validateForLoopHeader(TIntermLoop* node,
 218                                                 TLoopInfo* info)
 219 {
 220     ASSERT(node->getType() == ELoopFor);
 221
 222     //
 223     // The for statement has the form:
 224     //    for ( init-declaration ; condition ; expression ) statement
 225     //
 226     if (!validateForLoopInit(node, info))
 227         return false;
 228     if (!validateForLoopCond(node, info))
 229         return false;
 230     if (!validateForLoopExpr(node, info))
 231         return false;
 232
 233     return true;
 234 }
 235
 236 bool ValidateLimitations::validateForLoopInit(TIntermLoop* node,
 237                                               TLoopInfo* info)
 238 {
 239     TIntermNode* init = node->getInit();
 240     if (init == NULL) {
 241         error(node->getLine(), "Missing init declaration", "for");
 242         return false;
 243     }
 244
 245     //
 246     // init-declaration has the form:
 247     //     type-specifier identifier = constant-expression
 248     //
 249     TIntermAggregate* decl = init->getAsAggregate();
 250     if ((decl == NULL) || (decl->getOp() != EOpDeclaration)) {
 251         error(init->getLine(), "Invalid init declaration", "for");
 252         return false;
 253     }
 254     // To keep things simple do not allow declaration list.
 255     TIntermSequence& declSeq = decl->getSequence();
 256     if (declSeq.size() != 1) {
 257         error(decl->getLine(), "Invalid init declaration", "for");
 258         return false;
 259     }
 260     TIntermBinary* declInit = declSeq[0]->getAsBinaryNode();
 261     if ((declInit == NULL) || (declInit->getOp() != EOpInitialize)) {
 262         error(decl->getLine(), "Invalid init declaration", "for");
 263         return false;
 264     }
 265     TIntermSymbol* symbol = declInit->getLeft()->getAsSymbolNode();
 266     if (symbol == NULL) {
 267         error(declInit->getLine(), "Invalid init declaration", "for");
 268         return false;
 269     }
 270     // The loop index has type int or float.
 271     TBasicType type = symbol->getBasicType();
 272     if ((type != EbtInt) && (type != EbtFloat)) {
 273         error(symbol->getLine(),
 274               "Invalid type for loop index", getBasicString(type));
 275         return false;
 276     }
 277     // The loop index is initialized with constant expression.
 278     if (!isConstExpr(declInit->getRight())) {
 279         error(declInit->getLine(),
 280               "Loop index cannot be initialized with non-constant expression",
 281               symbol->getSymbol().c_str());
 282         return false;
 283     }
 284
 285     info->index.id = symbol->getId();
 286     return true;
 287 }
 288
 289 bool ValidateLimitations::validateForLoopCond(TIntermLoop* node,
 290                                               TLoopInfo* info)
 291 {
 292     TIntermNode* cond = node->getCondition();
 293     if (cond == NULL) {
 294         error(node->getLine(), "Missing condition", "for");
 295         return false;
 296     }
 297     //
 298     // condition has the form:
 299     //     loop_index relational_operator constant_expression
 300     //
 301     TIntermBinary* binOp = cond->getAsBinaryNode();
 302     if (binOp == NULL) {
 303         error(node->getLine(), "Invalid condition", "for");
 304         return false;
 305     }
 306     // Loop index should be to the left of relational operator.
 307     TIntermSymbol* symbol = binOp->getLeft()->getAsSymbolNode();
 308     if (symbol == NULL) {
 309         error(binOp->getLine(), "Invalid condition", "for");
 310         return false;
 311     }
 312     if (symbol->getId() != info->index.id) {
 313         error(symbol->getLine(),
 314               "Expected loop index", symbol->getSymbol().c_str());
 315         return false;
 316     }
 317     // Relational operator is one of: > >= < <= == or !=.
 318     switch (binOp->getOp()) {
 319       case EOpEqual:
 320       case EOpNotEqual:
 321       case EOpLessThan:
 322       case EOpGreaterThan:
 323       case EOpLessThanEqual:
 324       case EOpGreaterThanEqual:
 325         break;
 326       default:
 327         error(binOp->getLine(),
 328               "Invalid relational operator",
 329               getOperatorString(binOp->getOp()));
 330         break;
 331     }
 332     // Loop index must be compared with a constant.
 333     if (!isConstExpr(binOp->getRight())) {
 334         error(binOp->getLine(),
 335               "Loop index cannot be compared with non-constant expression",
 336               symbol->getSymbol().c_str());
 337         return false;
 338     }
 339
 340     return true;
 341 }
 342
 343 bool ValidateLimitations::validateForLoopExpr(TIntermLoop* node,
 344                                               TLoopInfo* info)
 345 {
 346     TIntermNode* expr = node->getExpression();
 347     if (expr == NULL) {
 348         error(node->getLine(), "Missing expression", "for");
 349         return false;
 350     }
 351
 352     // for expression has one of the following forms:
 353     //     loop_index++
 354     //     loop_index--
 355     //     loop_index += constant_expression
 356     //     loop_index -= constant_expression
 357     //     ++loop_index
 358     //     --loop_index
 359     // The last two forms are not specified in the spec, but I am assuming
 360     // its an oversight.
 361     TIntermUnary* unOp = expr->getAsUnaryNode();
 362     TIntermBinary* binOp = unOp ? NULL : expr->getAsBinaryNode();
 363
 364     TOperator op = EOpNull;
 365     TIntermSymbol* symbol = NULL;
 366     if (unOp != NULL) {
 367         op = unOp->getOp();
 368         symbol = unOp->getOperand()->getAsSymbolNode();
 369     } else if (binOp != NULL) {
 370         op = binOp->getOp();
 371         symbol = binOp->getLeft()->getAsSymbolNode();
 372     }
 373
 374     // The operand must be loop index.
 375     if (symbol == NULL) {
 376         error(expr->getLine(), "Invalid expression", "for");
 377         return false;
 378     }
 379     if (symbol->getId() != info->index.id) {
 380         error(symbol->getLine(),
 381               "Expected loop index", symbol->getSymbol().c_str());
 382         return false;
 383     }
 384
 385     // The operator is one of: ++ -- += -=.
 386     switch (op) {
 387         case EOpPostIncrement:
 388         case EOpPostDecrement:
 389         case EOpPreIncrement:
 390         case EOpPreDecrement:
 391             ASSERT((unOp != NULL) && (binOp == NULL));
 392             break;
 393         case EOpAddAssign:
 394         case EOpSubAssign:
 395             ASSERT((unOp == NULL) && (binOp != NULL));
 396             break;
 397         default:
 398             error(expr->getLine(), "Invalid operator", getOperatorString(op));
 399             return false;
 400     }
 401
 402     // Loop index must be incremented/decremented with a constant.
 403     if (binOp != NULL) {
 404         if (!isConstExpr(binOp->getRight())) {
 405             error(binOp->getLine(),
 406                   "Loop index cannot be modified by non-constant expression",
 407                   symbol->getSymbol().c_str());
 408             return false;
 409         }
 410     }
 411
 412     return true;
 413 }
 414
 415 bool ValidateLimitations::validateFunctionCall(TIntermAggregate* node)
 416 {
 417     ASSERT(node->getOp() == EOpFunctionCall);
 418
 419     // If not within loop body, there is nothing to check.
 420     if (!withinLoopBody())
 421         return true;
 422
 423     // List of param indices for which loop indices are used as argument.
 424     typedef std::vector<int> ParamIndex;
 425     ParamIndex pIndex;
 426     TIntermSequence& params = node->getSequence();
 427     for (TIntermSequence::size_type i = 0; i < params.size(); ++i) {
 428         TIntermSymbol* symbol = params[i]->getAsSymbolNode();
 429         if (symbol && isLoopIndex(symbol))
 430             pIndex.push_back(i);
 431     }
 432     // If none of the loop indices are used as arguments,
 433     // there is nothing to check.
 434     if (pIndex.empty())
 435         return true;
 436
 437     bool valid = true;
 438     TSymbolTable& symbolTable = GetGlobalParseContext()->symbolTable;
 439     TSymbol* symbol = symbolTable.find(node->getName());
 440     ASSERT(symbol && symbol->isFunction());
 441     TFunction* function = static_cast<TFunction*>(symbol);
 442     for (ParamIndex::const_iterator i = pIndex.begin();
 443          i != pIndex.end(); ++i) {
 444         const TParameter& param = function->getParam(*i);
 445         TQualifier qual = param.type->getQualifier();
 446         if ((qual == EvqOut) || (qual == EvqInOut)) {
 447             error(params[*i]->getLine(),
 448                   "Loop index cannot be used as argument to a function out or inout parameter",
 449                   params[*i]->getAsSymbolNode()->getSymbol().c_str());
 450             valid = false;
 451         }
 452     }
 453
 454     return valid;
 455 }
 456
 457 bool ValidateLimitations::validateOperation(TIntermOperator* node,
 458                                             TIntermNode* operand) {
 459     // Check if loop index is modified in the loop body.
 460     if (!withinLoopBody() || !node->modifiesState())
 461         return true;
 462
 463     const TIntermSymbol* symbol = operand->getAsSymbolNode();
 464     if (symbol && isLoopIndex(symbol)) {
 465         error(node->getLine(),
 466               "Loop index cannot be statically assigned to within the body of the loop",
 467               symbol->getSymbol().c_str());
 468     }
 469     return true;
 470 }
 471
 472 bool ValidateLimitations::isConstExpr(TIntermNode* node)
 473 {
 474     ASSERT(node != NULL);
 475     return node->getAsConstantUnion() != NULL;
 476 }
 477
 478 bool ValidateLimitations::isConstIndexExpr(TIntermNode* node)
 479 {
 480     ASSERT(node != NULL);
 481
 482     ValidateConstIndexExpr validate(mLoopStack);
 483     node->traverse(&validate);
 484     return validate.isValid();
 485 }
 486
 487 bool ValidateLimitations::validateIndexing(TIntermBinary* node)
 488 {
 489     ASSERT((node->getOp() == EOpIndexDirect) ||
 490            (node->getOp() == EOpIndexIndirect));
 491
 492     bool valid = true;
 493     TIntermTyped* index = node->getRight();
 494     // The index expression must have integral type.
 495     if (!index->isScalar() || (index->getBasicType() != EbtInt)) {
 496         error(index->getLine(),
 497               "Index expression must have integral type",
 498               index->getCompleteString().c_str());
 499         valid = false;
 500     }
 501     // The index expession must be a constant-index-expression unless
 502     // the operand is a uniform in a vertex shader.
 503     TIntermTyped* operand = node->getLeft();
 504     bool skip = (mShaderType == SH_VERTEX_SHADER) &&
 505                 (operand->getQualifier() == EvqUniform);
 506     if (!skip && !isConstIndexExpr(index)) {
 507         error(index->getLine(), "Index expression must be constant", "[]");
 508         valid = false;
 509     }
 510     return valid;
 511 }
 512