1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/angle/src/compiler/ValidateLimitations.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,512 @@
1.4 +//
1.5 +// Copyright (c) 2002-2010 The ANGLE Project Authors. All rights reserved.
1.6 +// Use of this source code is governed by a BSD-style license that can be
1.7 +// found in the LICENSE file.
1.8 +//
1.9 +
1.10 +#include "compiler/ValidateLimitations.h"
1.11 +#include "compiler/InfoSink.h"
1.12 +#include "compiler/InitializeParseContext.h"
1.13 +#include "compiler/ParseHelper.h"
1.14 +
1.15 +namespace {
1.16 +bool IsLoopIndex(const TIntermSymbol* symbol, const TLoopStack& stack) {
1.17 + for (TLoopStack::const_iterator i = stack.begin(); i != stack.end(); ++i) {
1.18 + if (i->index.id == symbol->getId())
1.19 + return true;
1.20 + }
1.21 + return false;
1.22 +}
1.23 +
1.24 +void MarkLoopForUnroll(const TIntermSymbol* symbol, TLoopStack& stack) {
1.25 + for (TLoopStack::iterator i = stack.begin(); i != stack.end(); ++i) {
1.26 + if (i->index.id == symbol->getId()) {
1.27 + ASSERT(i->loop != NULL);
1.28 + i->loop->setUnrollFlag(true);
1.29 + return;
1.30 + }
1.31 + }
1.32 + UNREACHABLE();
1.33 +}
1.34 +
1.35 +// Traverses a node to check if it represents a constant index expression.
1.36 +// Definition:
1.37 +// constant-index-expressions are a superset of constant-expressions.
1.38 +// Constant-index-expressions can include loop indices as defined in
1.39 +// GLSL ES 1.0 spec, Appendix A, section 4.
1.40 +// The following are constant-index-expressions:
1.41 +// - Constant expressions
1.42 +// - Loop indices as defined in section 4
1.43 +// - Expressions composed of both of the above
1.44 +class ValidateConstIndexExpr : public TIntermTraverser {
1.45 +public:
1.46 + ValidateConstIndexExpr(const TLoopStack& stack)
1.47 + : mValid(true), mLoopStack(stack) {}
1.48 +
1.49 + // Returns true if the parsed node represents a constant index expression.
1.50 + bool isValid() const { return mValid; }
1.51 +
1.52 + virtual void visitSymbol(TIntermSymbol* symbol) {
1.53 + // Only constants and loop indices are allowed in a
1.54 + // constant index expression.
1.55 + if (mValid) {
1.56 + mValid = (symbol->getQualifier() == EvqConst) ||
1.57 + IsLoopIndex(symbol, mLoopStack);
1.58 + }
1.59 + }
1.60 +
1.61 +private:
1.62 + bool mValid;
1.63 + const TLoopStack& mLoopStack;
1.64 +};
1.65 +
1.66 +// Traverses a node to check if it uses a loop index.
1.67 +// If an int loop index is used in its body as a sampler array index,
1.68 +// mark the loop for unroll.
1.69 +class ValidateLoopIndexExpr : public TIntermTraverser {
1.70 +public:
1.71 + ValidateLoopIndexExpr(TLoopStack& stack)
1.72 + : mUsesFloatLoopIndex(false),
1.73 + mUsesIntLoopIndex(false),
1.74 + mLoopStack(stack) {}
1.75 +
1.76 + bool usesFloatLoopIndex() const { return mUsesFloatLoopIndex; }
1.77 + bool usesIntLoopIndex() const { return mUsesIntLoopIndex; }
1.78 +
1.79 + virtual void visitSymbol(TIntermSymbol* symbol) {
1.80 + if (IsLoopIndex(symbol, mLoopStack)) {
1.81 + switch (symbol->getBasicType()) {
1.82 + case EbtFloat:
1.83 + mUsesFloatLoopIndex = true;
1.84 + break;
1.85 + case EbtInt:
1.86 + mUsesIntLoopIndex = true;
1.87 + MarkLoopForUnroll(symbol, mLoopStack);
1.88 + break;
1.89 + default:
1.90 + UNREACHABLE();
1.91 + }
1.92 + }
1.93 + }
1.94 +
1.95 +private:
1.96 + bool mUsesFloatLoopIndex;
1.97 + bool mUsesIntLoopIndex;
1.98 + TLoopStack& mLoopStack;
1.99 +};
1.100 +} // namespace
1.101 +
1.102 +ValidateLimitations::ValidateLimitations(ShShaderType shaderType,
1.103 + TInfoSinkBase& sink)
1.104 + : mShaderType(shaderType),
1.105 + mSink(sink),
1.106 + mNumErrors(0)
1.107 +{
1.108 +}
1.109 +
1.110 +bool ValidateLimitations::visitBinary(Visit, TIntermBinary* node)
1.111 +{
1.112 + // Check if loop index is modified in the loop body.
1.113 + validateOperation(node, node->getLeft());
1.114 +
1.115 + // Check indexing.
1.116 + switch (node->getOp()) {
1.117 + case EOpIndexDirect:
1.118 + validateIndexing(node);
1.119 + break;
1.120 + case EOpIndexIndirect:
1.121 +#if defined(__APPLE__)
1.122 + // Loop unrolling is a work-around for a Mac Cg compiler bug where it
1.123 + // crashes when a sampler array's index is also the loop index.
1.124 + // Once Apple fixes this bug, we should remove the code in this CL.
1.125 + // See http://codereview.appspot.com/4331048/.
1.126 + if ((node->getLeft() != NULL) && (node->getRight() != NULL) &&
1.127 + (node->getLeft()->getAsSymbolNode())) {
1.128 + TIntermSymbol* symbol = node->getLeft()->getAsSymbolNode();
1.129 + if (IsSampler(symbol->getBasicType()) && symbol->isArray()) {
1.130 + ValidateLoopIndexExpr validate(mLoopStack);
1.131 + node->getRight()->traverse(&validate);
1.132 + if (validate.usesFloatLoopIndex()) {
1.133 + error(node->getLine(),
1.134 + "sampler array index is float loop index",
1.135 + "for");
1.136 + }
1.137 + }
1.138 + }
1.139 +#endif
1.140 + validateIndexing(node);
1.141 + break;
1.142 + default: break;
1.143 + }
1.144 + return true;
1.145 +}
1.146 +
1.147 +bool ValidateLimitations::visitUnary(Visit, TIntermUnary* node)
1.148 +{
1.149 + // Check if loop index is modified in the loop body.
1.150 + validateOperation(node, node->getOperand());
1.151 +
1.152 + return true;
1.153 +}
1.154 +
1.155 +bool ValidateLimitations::visitAggregate(Visit, TIntermAggregate* node)
1.156 +{
1.157 + switch (node->getOp()) {
1.158 + case EOpFunctionCall:
1.159 + validateFunctionCall(node);
1.160 + break;
1.161 + default:
1.162 + break;
1.163 + }
1.164 + return true;
1.165 +}
1.166 +
1.167 +bool ValidateLimitations::visitLoop(Visit, TIntermLoop* node)
1.168 +{
1.169 + if (!validateLoopType(node))
1.170 + return false;
1.171 +
1.172 + TLoopInfo info;
1.173 + memset(&info, 0, sizeof(TLoopInfo));
1.174 + info.loop = node;
1.175 + if (!validateForLoopHeader(node, &info))
1.176 + return false;
1.177 +
1.178 + TIntermNode* body = node->getBody();
1.179 + if (body != NULL) {
1.180 + mLoopStack.push_back(info);
1.181 + body->traverse(this);
1.182 + mLoopStack.pop_back();
1.183 + }
1.184 +
1.185 + // The loop is fully processed - no need to visit children.
1.186 + return false;
1.187 +}
1.188 +
1.189 +void ValidateLimitations::error(TSourceLoc loc,
1.190 + const char *reason, const char* token)
1.191 +{
1.192 + mSink.prefix(EPrefixError);
1.193 + mSink.location(loc);
1.194 + mSink << "'" << token << "' : " << reason << "\n";
1.195 + ++mNumErrors;
1.196 +}
1.197 +
1.198 +bool ValidateLimitations::withinLoopBody() const
1.199 +{
1.200 + return !mLoopStack.empty();
1.201 +}
1.202 +
1.203 +bool ValidateLimitations::isLoopIndex(const TIntermSymbol* symbol) const
1.204 +{
1.205 + return IsLoopIndex(symbol, mLoopStack);
1.206 +}
1.207 +
1.208 +bool ValidateLimitations::validateLoopType(TIntermLoop* node) {
1.209 + TLoopType type = node->getType();
1.210 + if (type == ELoopFor)
1.211 + return true;
1.212 +
1.213 + // Reject while and do-while loops.
1.214 + error(node->getLine(),
1.215 + "This type of loop is not allowed",
1.216 + type == ELoopWhile ? "while" : "do");
1.217 + return false;
1.218 +}
1.219 +
1.220 +bool ValidateLimitations::validateForLoopHeader(TIntermLoop* node,
1.221 + TLoopInfo* info)
1.222 +{
1.223 + ASSERT(node->getType() == ELoopFor);
1.224 +
1.225 + //
1.226 + // The for statement has the form:
1.227 + // for ( init-declaration ; condition ; expression ) statement
1.228 + //
1.229 + if (!validateForLoopInit(node, info))
1.230 + return false;
1.231 + if (!validateForLoopCond(node, info))
1.232 + return false;
1.233 + if (!validateForLoopExpr(node, info))
1.234 + return false;
1.235 +
1.236 + return true;
1.237 +}
1.238 +
1.239 +bool ValidateLimitations::validateForLoopInit(TIntermLoop* node,
1.240 + TLoopInfo* info)
1.241 +{
1.242 + TIntermNode* init = node->getInit();
1.243 + if (init == NULL) {
1.244 + error(node->getLine(), "Missing init declaration", "for");
1.245 + return false;
1.246 + }
1.247 +
1.248 + //
1.249 + // init-declaration has the form:
1.250 + // type-specifier identifier = constant-expression
1.251 + //
1.252 + TIntermAggregate* decl = init->getAsAggregate();
1.253 + if ((decl == NULL) || (decl->getOp() != EOpDeclaration)) {
1.254 + error(init->getLine(), "Invalid init declaration", "for");
1.255 + return false;
1.256 + }
1.257 + // To keep things simple do not allow declaration list.
1.258 + TIntermSequence& declSeq = decl->getSequence();
1.259 + if (declSeq.size() != 1) {
1.260 + error(decl->getLine(), "Invalid init declaration", "for");
1.261 + return false;
1.262 + }
1.263 + TIntermBinary* declInit = declSeq[0]->getAsBinaryNode();
1.264 + if ((declInit == NULL) || (declInit->getOp() != EOpInitialize)) {
1.265 + error(decl->getLine(), "Invalid init declaration", "for");
1.266 + return false;
1.267 + }
1.268 + TIntermSymbol* symbol = declInit->getLeft()->getAsSymbolNode();
1.269 + if (symbol == NULL) {
1.270 + error(declInit->getLine(), "Invalid init declaration", "for");
1.271 + return false;
1.272 + }
1.273 + // The loop index has type int or float.
1.274 + TBasicType type = symbol->getBasicType();
1.275 + if ((type != EbtInt) && (type != EbtFloat)) {
1.276 + error(symbol->getLine(),
1.277 + "Invalid type for loop index", getBasicString(type));
1.278 + return false;
1.279 + }
1.280 + // The loop index is initialized with constant expression.
1.281 + if (!isConstExpr(declInit->getRight())) {
1.282 + error(declInit->getLine(),
1.283 + "Loop index cannot be initialized with non-constant expression",
1.284 + symbol->getSymbol().c_str());
1.285 + return false;
1.286 + }
1.287 +
1.288 + info->index.id = symbol->getId();
1.289 + return true;
1.290 +}
1.291 +
1.292 +bool ValidateLimitations::validateForLoopCond(TIntermLoop* node,
1.293 + TLoopInfo* info)
1.294 +{
1.295 + TIntermNode* cond = node->getCondition();
1.296 + if (cond == NULL) {
1.297 + error(node->getLine(), "Missing condition", "for");
1.298 + return false;
1.299 + }
1.300 + //
1.301 + // condition has the form:
1.302 + // loop_index relational_operator constant_expression
1.303 + //
1.304 + TIntermBinary* binOp = cond->getAsBinaryNode();
1.305 + if (binOp == NULL) {
1.306 + error(node->getLine(), "Invalid condition", "for");
1.307 + return false;
1.308 + }
1.309 + // Loop index should be to the left of relational operator.
1.310 + TIntermSymbol* symbol = binOp->getLeft()->getAsSymbolNode();
1.311 + if (symbol == NULL) {
1.312 + error(binOp->getLine(), "Invalid condition", "for");
1.313 + return false;
1.314 + }
1.315 + if (symbol->getId() != info->index.id) {
1.316 + error(symbol->getLine(),
1.317 + "Expected loop index", symbol->getSymbol().c_str());
1.318 + return false;
1.319 + }
1.320 + // Relational operator is one of: > >= < <= == or !=.
1.321 + switch (binOp->getOp()) {
1.322 + case EOpEqual:
1.323 + case EOpNotEqual:
1.324 + case EOpLessThan:
1.325 + case EOpGreaterThan:
1.326 + case EOpLessThanEqual:
1.327 + case EOpGreaterThanEqual:
1.328 + break;
1.329 + default:
1.330 + error(binOp->getLine(),
1.331 + "Invalid relational operator",
1.332 + getOperatorString(binOp->getOp()));
1.333 + break;
1.334 + }
1.335 + // Loop index must be compared with a constant.
1.336 + if (!isConstExpr(binOp->getRight())) {
1.337 + error(binOp->getLine(),
1.338 + "Loop index cannot be compared with non-constant expression",
1.339 + symbol->getSymbol().c_str());
1.340 + return false;
1.341 + }
1.342 +
1.343 + return true;
1.344 +}
1.345 +
1.346 +bool ValidateLimitations::validateForLoopExpr(TIntermLoop* node,
1.347 + TLoopInfo* info)
1.348 +{
1.349 + TIntermNode* expr = node->getExpression();
1.350 + if (expr == NULL) {
1.351 + error(node->getLine(), "Missing expression", "for");
1.352 + return false;
1.353 + }
1.354 +
1.355 + // for expression has one of the following forms:
1.356 + // loop_index++
1.357 + // loop_index--
1.358 + // loop_index += constant_expression
1.359 + // loop_index -= constant_expression
1.360 + // ++loop_index
1.361 + // --loop_index
1.362 + // The last two forms are not specified in the spec, but I am assuming
1.363 + // its an oversight.
1.364 + TIntermUnary* unOp = expr->getAsUnaryNode();
1.365 + TIntermBinary* binOp = unOp ? NULL : expr->getAsBinaryNode();
1.366 +
1.367 + TOperator op = EOpNull;
1.368 + TIntermSymbol* symbol = NULL;
1.369 + if (unOp != NULL) {
1.370 + op = unOp->getOp();
1.371 + symbol = unOp->getOperand()->getAsSymbolNode();
1.372 + } else if (binOp != NULL) {
1.373 + op = binOp->getOp();
1.374 + symbol = binOp->getLeft()->getAsSymbolNode();
1.375 + }
1.376 +
1.377 + // The operand must be loop index.
1.378 + if (symbol == NULL) {
1.379 + error(expr->getLine(), "Invalid expression", "for");
1.380 + return false;
1.381 + }
1.382 + if (symbol->getId() != info->index.id) {
1.383 + error(symbol->getLine(),
1.384 + "Expected loop index", symbol->getSymbol().c_str());
1.385 + return false;
1.386 + }
1.387 +
1.388 + // The operator is one of: ++ -- += -=.
1.389 + switch (op) {
1.390 + case EOpPostIncrement:
1.391 + case EOpPostDecrement:
1.392 + case EOpPreIncrement:
1.393 + case EOpPreDecrement:
1.394 + ASSERT((unOp != NULL) && (binOp == NULL));
1.395 + break;
1.396 + case EOpAddAssign:
1.397 + case EOpSubAssign:
1.398 + ASSERT((unOp == NULL) && (binOp != NULL));
1.399 + break;
1.400 + default:
1.401 + error(expr->getLine(), "Invalid operator", getOperatorString(op));
1.402 + return false;
1.403 + }
1.404 +
1.405 + // Loop index must be incremented/decremented with a constant.
1.406 + if (binOp != NULL) {
1.407 + if (!isConstExpr(binOp->getRight())) {
1.408 + error(binOp->getLine(),
1.409 + "Loop index cannot be modified by non-constant expression",
1.410 + symbol->getSymbol().c_str());
1.411 + return false;
1.412 + }
1.413 + }
1.414 +
1.415 + return true;
1.416 +}
1.417 +
1.418 +bool ValidateLimitations::validateFunctionCall(TIntermAggregate* node)
1.419 +{
1.420 + ASSERT(node->getOp() == EOpFunctionCall);
1.421 +
1.422 + // If not within loop body, there is nothing to check.
1.423 + if (!withinLoopBody())
1.424 + return true;
1.425 +
1.426 + // List of param indices for which loop indices are used as argument.
1.427 + typedef std::vector<size_t> ParamIndex;
1.428 + ParamIndex pIndex;
1.429 + TIntermSequence& params = node->getSequence();
1.430 + for (TIntermSequence::size_type i = 0; i < params.size(); ++i) {
1.431 + TIntermSymbol* symbol = params[i]->getAsSymbolNode();
1.432 + if (symbol && isLoopIndex(symbol))
1.433 + pIndex.push_back(i);
1.434 + }
1.435 + // If none of the loop indices are used as arguments,
1.436 + // there is nothing to check.
1.437 + if (pIndex.empty())
1.438 + return true;
1.439 +
1.440 + bool valid = true;
1.441 + TSymbolTable& symbolTable = GetGlobalParseContext()->symbolTable;
1.442 + TSymbol* symbol = symbolTable.find(node->getName());
1.443 + ASSERT(symbol && symbol->isFunction());
1.444 + TFunction* function = static_cast<TFunction*>(symbol);
1.445 + for (ParamIndex::const_iterator i = pIndex.begin();
1.446 + i != pIndex.end(); ++i) {
1.447 + const TParameter& param = function->getParam(*i);
1.448 + TQualifier qual = param.type->getQualifier();
1.449 + if ((qual == EvqOut) || (qual == EvqInOut)) {
1.450 + error(params[*i]->getLine(),
1.451 + "Loop index cannot be used as argument to a function out or inout parameter",
1.452 + params[*i]->getAsSymbolNode()->getSymbol().c_str());
1.453 + valid = false;
1.454 + }
1.455 + }
1.456 +
1.457 + return valid;
1.458 +}
1.459 +
1.460 +bool ValidateLimitations::validateOperation(TIntermOperator* node,
1.461 + TIntermNode* operand) {
1.462 + // Check if loop index is modified in the loop body.
1.463 + if (!withinLoopBody() || !node->modifiesState())
1.464 + return true;
1.465 +
1.466 + const TIntermSymbol* symbol = operand->getAsSymbolNode();
1.467 + if (symbol && isLoopIndex(symbol)) {
1.468 + error(node->getLine(),
1.469 + "Loop index cannot be statically assigned to within the body of the loop",
1.470 + symbol->getSymbol().c_str());
1.471 + }
1.472 + return true;
1.473 +}
1.474 +
1.475 +bool ValidateLimitations::isConstExpr(TIntermNode* node)
1.476 +{
1.477 + ASSERT(node != NULL);
1.478 + return node->getAsConstantUnion() != NULL;
1.479 +}
1.480 +
1.481 +bool ValidateLimitations::isConstIndexExpr(TIntermNode* node)
1.482 +{
1.483 + ASSERT(node != NULL);
1.484 +
1.485 + ValidateConstIndexExpr validate(mLoopStack);
1.486 + node->traverse(&validate);
1.487 + return validate.isValid();
1.488 +}
1.489 +
1.490 +bool ValidateLimitations::validateIndexing(TIntermBinary* node)
1.491 +{
1.492 + ASSERT((node->getOp() == EOpIndexDirect) ||
1.493 + (node->getOp() == EOpIndexIndirect));
1.494 +
1.495 + bool valid = true;
1.496 + TIntermTyped* index = node->getRight();
1.497 + // The index expression must have integral type.
1.498 + if (!index->isScalar() || (index->getBasicType() != EbtInt)) {
1.499 + error(index->getLine(),
1.500 + "Index expression must have integral type",
1.501 + index->getCompleteString().c_str());
1.502 + valid = false;
1.503 + }
1.504 + // The index expession must be a constant-index-expression unless
1.505 + // the operand is a uniform in a vertex shader.
1.506 + TIntermTyped* operand = node->getLeft();
1.507 + bool skip = (mShaderType == SH_VERTEX_SHADER) &&
1.508 + (operand->getQualifier() == EvqUniform);
1.509 + if (!skip && !isConstIndexExpr(index)) {
1.510 + error(index->getLine(), "Index expression must be constant", "[]");
1.511 + valid = false;
1.512 + }
1.513 + return valid;
1.514 +}
1.515 +
