code.vuplus.com Git - vuplus_webkit/blob - Source/ThirdParty/ANGLE/src/compiler/ValidateLimitations.cpp

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