| File: | root/firefox-clang/obj-x86_64-pc-linux-gnu/gfx/skia/./../../../gfx/skia/skia/src/sksl/analysis/SkSLGetLoopUnrollInfo.cpp |
| Warning: | line 358, column 17 Value stored to 'cond' is never read |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | /* |
| 2 | * Copyright 2021 Google LLC |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
| 6 | */ |
| 7 | |
| 8 | #include "include/core/SkTypes.h" |
| 9 | #include "include/private/base/SkFloatingPoint.h" |
| 10 | #include "src/base/SkSafeMath.h" |
| 11 | #include "src/sksl/SkSLAnalysis.h" |
| 12 | #include "src/sksl/SkSLConstantFolder.h" |
| 13 | #include "src/sksl/SkSLErrorReporter.h" |
| 14 | #include "src/sksl/SkSLOperator.h" |
| 15 | #include "src/sksl/SkSLPosition.h" |
| 16 | #include "src/sksl/analysis/SkSLNoOpErrorReporter.h" |
| 17 | #include "src/sksl/ir/SkSLBinaryExpression.h" |
| 18 | #include "src/sksl/ir/SkSLExpression.h" |
| 19 | #include "src/sksl/ir/SkSLForStatement.h" |
| 20 | #include "src/sksl/ir/SkSLIRNode.h" |
| 21 | #include "src/sksl/ir/SkSLPostfixExpression.h" |
| 22 | #include "src/sksl/ir/SkSLPrefixExpression.h" |
| 23 | #include "src/sksl/ir/SkSLStatement.h" |
| 24 | #include "src/sksl/ir/SkSLType.h" |
| 25 | #include "src/sksl/ir/SkSLVarDeclarations.h" |
| 26 | #include "src/sksl/ir/SkSLVariable.h" |
| 27 | #include "src/sksl/ir/SkSLVariableReference.h" |
| 28 | |
| 29 | #include <cmath> |
| 30 | #include <memory> |
| 31 | |
| 32 | namespace SkSL { |
| 33 | |
| 34 | class Context; |
| 35 | |
| 36 | // Loops that run for 100000+ iterations will exceed our program size limit. |
| 37 | static constexpr int kLoopTerminationLimit = 100000; |
| 38 | |
| 39 | enum class Direction { |
| 40 | kBackwards, |
| 41 | kForwards, |
| 42 | }; |
| 43 | |
| 44 | enum class Inclusive : bool { |
| 45 | kNo = false, |
| 46 | kYes = true, |
| 47 | }; |
| 48 | |
| 49 | enum class LoopType { |
| 50 | kFloat, |
| 51 | kInt, |
| 52 | }; |
| 53 | |
| 54 | static int calculate_count_float(double start, double end, double delta, |
| 55 | Inclusive inclusive) { |
| 56 | double iterations = sk_ieee_double_divide(end - start, delta); |
| 57 | double count = std::ceil(iterations); |
| 58 | if (inclusive == Inclusive::kYes && (count == iterations)) { |
| 59 | count += 1.0; |
| 60 | } |
| 61 | if (count > kLoopTerminationLimit || !std::isfinite(count)) { |
| 62 | // The loop runs for more iterations than we can safely unroll. |
| 63 | return kLoopTerminationLimit; |
| 64 | } |
| 65 | return sk_double_saturate2int(count); |
| 66 | } |
| 67 | |
| 68 | static int calculate_count_int(int32_t start, int32_t end, int32_t delta, |
| 69 | Inclusive inclusive) { |
| 70 | if (delta == 0) { |
| 71 | return kLoopTerminationLimit; |
| 72 | } |
| 73 | SkSafeMath math; |
| 74 | int roundUp = delta > 0 ? math.subInt(delta, 1) : math.addInt(delta, 1); |
| 75 | int width = math.subInt(end, start); |
| 76 | int iterations = math.addInt(width, roundUp) / delta; |
| 77 | if (inclusive == Inclusive::kYes && width % delta == 0) { |
| 78 | iterations = math.addInt(iterations, 1); |
| 79 | } |
| 80 | // Check that we won't overflow while looping |
| 81 | math.addInt(start, math.mulInt(delta, iterations)); |
| 82 | if (!math || iterations < 0 || iterations > kLoopTerminationLimit) { |
| 83 | return kLoopTerminationLimit; |
| 84 | } |
| 85 | return iterations; |
| 86 | } |
| 87 | |
| 88 | static int calculate_count(double start, double end, double delta, Direction dir, |
| 89 | Inclusive inclusive, LoopType loop) { |
| 90 | if ((dir == Direction::kForwards && start > end) || |
| 91 | (dir == Direction::kBackwards && start < end)) { |
| 92 | // The loop starts in a completed state (the start has already advanced past the end). |
| 93 | return 0; |
| 94 | } |
| 95 | if ((delta == 0.0) || |
| 96 | (delta > 0.0 && dir == Direction::kBackwards) || |
| 97 | (delta < 0.0 && dir == Direction::kForwards)) { |
| 98 | // The loop does not progress toward a completed state, and will never terminate. |
| 99 | return kLoopTerminationLimit; |
| 100 | } |
| 101 | if (loop == LoopType::kInt) { |
| 102 | return calculate_count_int((int32_t)start, (int32_t)end, (int32_t)delta, inclusive); |
| 103 | } |
| 104 | return calculate_count_float(start, end, delta, inclusive); |
| 105 | } |
| 106 | |
| 107 | static int calculate_count_neq_int(int32_t start, int32_t end, int32_t delta) { |
| 108 | if (delta == 0) { |
| 109 | return kLoopTerminationLimit; |
| 110 | } |
| 111 | SkSafeMath math; |
| 112 | int iterations = math.subInt(end, start) / delta; |
| 113 | // Check that we won't overflow while looping and that we actually hit end. |
| 114 | int lastValue = math.addInt(start, math.mulInt(delta, iterations)); |
| 115 | if (!math || lastValue != end || iterations < 0 || iterations > kLoopTerminationLimit) { |
| 116 | return kLoopTerminationLimit; |
| 117 | } |
| 118 | return iterations; |
| 119 | } |
| 120 | |
| 121 | static int calculate_count_neq_float(double start, double end, double delta) { |
| 122 | if (delta == 0.0) { |
| 123 | return kLoopTerminationLimit; |
| 124 | } |
| 125 | double iterations = sk_ieee_double_divide(end - start, delta); |
| 126 | double count = std::ceil(iterations); |
| 127 | if (count < 0 || count != iterations || !std::isfinite(iterations)) { |
| 128 | // The loop doesn't reach the exact endpoint and so will never terminate. |
| 129 | return kLoopTerminationLimit; |
| 130 | } |
| 131 | return sk_double_saturate2int(count); |
| 132 | } |
| 133 | |
| 134 | static int calculate_count_neq(double start, double end, double delta, LoopType loop) { |
| 135 | if (loop == LoopType::kInt) { |
| 136 | return calculate_count_neq_int((int32_t)start, (int32_t)end, (int32_t)delta); |
| 137 | } |
| 138 | return calculate_count_neq_float(start, end, delta); |
| 139 | } |
| 140 | |
| 141 | std::unique_ptr<LoopUnrollInfo> Analysis::GetLoopUnrollInfo(const Context& context, |
| 142 | Position loopPos, |
| 143 | const ForLoopPositions& positions, |
| 144 | const Statement* loopInitializer, |
| 145 | std::unique_ptr<Expression>* loopTest, |
| 146 | const Expression* loopNext, |
| 147 | const Statement* loopStatement, |
| 148 | ErrorReporter* errorPtr) { |
| 149 | NoOpErrorReporter unused; |
| 150 | ErrorReporter& errors = errorPtr ? *errorPtr : unused; |
| 151 | |
| 152 | auto loopInfo = std::make_unique<LoopUnrollInfo>(); |
| 153 | |
| 154 | // |
| 155 | // init_declaration has the form: type_specifier identifier = constant_expression |
| 156 | // |
| 157 | if (!loopInitializer) { |
| 158 | Position pos = positions.initPosition.valid() ? positions.initPosition : loopPos; |
| 159 | errors.error(pos, "missing init declaration"); |
| 160 | return nullptr; |
| 161 | } |
| 162 | if (!loopInitializer->is<VarDeclaration>()) { |
| 163 | errors.error(loopInitializer->fPosition, "invalid init declaration"); |
| 164 | return nullptr; |
| 165 | } |
| 166 | const VarDeclaration& initDecl = loopInitializer->as<VarDeclaration>(); |
| 167 | if (!initDecl.baseType().isNumber()) { |
| 168 | errors.error(loopInitializer->fPosition, "invalid type for loop index"); |
| 169 | return nullptr; |
| 170 | } |
| 171 | if (initDecl.arraySize() != 0) { |
| 172 | errors.error(loopInitializer->fPosition, "invalid type for loop index"); |
| 173 | return nullptr; |
| 174 | } |
| 175 | if (!initDecl.value()) { |
| 176 | errors.error(loopInitializer->fPosition, "missing loop index initializer"); |
| 177 | return nullptr; |
| 178 | } |
| 179 | if (!ConstantFolder::GetConstantValue(*initDecl.value(), &loopInfo->fStart)) { |
| 180 | errors.error(loopInitializer->fPosition, |
| 181 | "loop index initializer must be a constant expression"); |
| 182 | return nullptr; |
| 183 | } |
| 184 | |
| 185 | loopInfo->fIndex = initDecl.var(); |
| 186 | |
| 187 | auto is_loop_index = [&](const std::unique_ptr<Expression>& expr) { |
| 188 | return expr->is<VariableReference>() && |
| 189 | expr->as<VariableReference>().variable() == loopInfo->fIndex; |
| 190 | }; |
| 191 | |
| 192 | // |
| 193 | // condition has the form: loop_index relational_operator constant_expression |
| 194 | // |
| 195 | if (!loopTest || !*loopTest) { |
| 196 | Position pos = positions.conditionPosition.valid() ? positions.conditionPosition : loopPos; |
| 197 | errors.error(pos, "missing condition"); |
| 198 | return nullptr; |
| 199 | } |
| 200 | if (!loopTest->get()->is<BinaryExpression>()) { |
| 201 | errors.error(loopTest->get()->fPosition, "invalid condition"); |
| 202 | return nullptr; |
| 203 | } |
| 204 | const BinaryExpression* cond = &loopTest->get()->as<BinaryExpression>(); |
| 205 | if (!is_loop_index(cond->left())) { |
| 206 | errors.error(cond->fPosition, "expected loop index on left hand side of condition"); |
| 207 | return nullptr; |
| 208 | } |
| 209 | // relational_operator is one of: > >= < <= == or != |
| 210 | switch (cond->getOperator().kind()) { |
| 211 | case Operator::Kind::GT: |
| 212 | case Operator::Kind::GTEQ: |
| 213 | case Operator::Kind::LT: |
| 214 | case Operator::Kind::LTEQ: |
| 215 | case Operator::Kind::EQEQ: |
| 216 | case Operator::Kind::NEQ: |
| 217 | break; |
| 218 | default: |
| 219 | errors.error(cond->fPosition, "invalid relational operator"); |
| 220 | return nullptr; |
| 221 | } |
| 222 | double loopEnd = 0; |
| 223 | if (!ConstantFolder::GetConstantValue(*cond->right(), &loopEnd)) { |
| 224 | errors.error(cond->fPosition, "loop index must be compared with a constant expression"); |
| 225 | return nullptr; |
| 226 | } |
| 227 | |
| 228 | // |
| 229 | // expression has one of the following forms: |
| 230 | // loop_index++ |
| 231 | // loop_index-- |
| 232 | // loop_index += constant_expression |
| 233 | // loop_index -= constant_expression |
| 234 | // The spec doesn't mention prefix increment and decrement, but there is some consensus that |
| 235 | // it's an oversight, so we allow those as well. |
| 236 | // |
| 237 | if (!loopNext) { |
| 238 | Position pos = positions.nextPosition.valid() ? positions.nextPosition : loopPos; |
| 239 | errors.error(pos, "missing loop expression"); |
| 240 | return nullptr; |
| 241 | } |
| 242 | switch (loopNext->kind()) { |
| 243 | case Expression::Kind::kBinary: { |
| 244 | const BinaryExpression& next = loopNext->as<BinaryExpression>(); |
| 245 | if (!is_loop_index(next.left())) { |
| 246 | errors.error(loopNext->fPosition, "expected loop index in loop expression"); |
| 247 | return nullptr; |
| 248 | } |
| 249 | if (!ConstantFolder::GetConstantValue(*next.right(), &loopInfo->fDelta)) { |
| 250 | errors.error(loopNext->fPosition, |
| 251 | "loop index must be modified by a constant expression"); |
| 252 | return nullptr; |
| 253 | } |
| 254 | switch (next.getOperator().kind()) { |
| 255 | case Operator::Kind::PLUSEQ: break; |
| 256 | case Operator::Kind::MINUSEQ: loopInfo->fDelta = -loopInfo->fDelta; break; |
| 257 | default: |
| 258 | errors.error(loopNext->fPosition, "invalid operator in loop expression"); |
| 259 | return nullptr; |
| 260 | } |
| 261 | break; |
| 262 | } |
| 263 | case Expression::Kind::kPrefix: { |
| 264 | const PrefixExpression& next = loopNext->as<PrefixExpression>(); |
| 265 | if (!is_loop_index(next.operand())) { |
| 266 | errors.error(loopNext->fPosition, "expected loop index in loop expression"); |
| 267 | return nullptr; |
| 268 | } |
| 269 | switch (next.getOperator().kind()) { |
| 270 | case Operator::Kind::PLUSPLUS: loopInfo->fDelta = 1; break; |
| 271 | case Operator::Kind::MINUSMINUS: loopInfo->fDelta = -1; break; |
| 272 | default: |
| 273 | errors.error(loopNext->fPosition, "invalid operator in loop expression"); |
| 274 | return nullptr; |
| 275 | } |
| 276 | break; |
| 277 | } |
| 278 | case Expression::Kind::kPostfix: { |
| 279 | const PostfixExpression& next = loopNext->as<PostfixExpression>(); |
| 280 | if (!is_loop_index(next.operand())) { |
| 281 | errors.error(loopNext->fPosition, "expected loop index in loop expression"); |
| 282 | return nullptr; |
| 283 | } |
| 284 | switch (next.getOperator().kind()) { |
| 285 | case Operator::Kind::PLUSPLUS: loopInfo->fDelta = 1; break; |
| 286 | case Operator::Kind::MINUSMINUS: loopInfo->fDelta = -1; break; |
| 287 | default: |
| 288 | errors.error(loopNext->fPosition, "invalid operator in loop expression"); |
| 289 | return nullptr; |
| 290 | } |
| 291 | break; |
| 292 | } |
| 293 | default: |
| 294 | errors.error(loopNext->fPosition, "invalid loop expression"); |
| 295 | return nullptr; |
| 296 | } |
| 297 | |
| 298 | // |
| 299 | // Within the body of the loop, the loop index is not statically assigned to, nor is it used as |
| 300 | // argument to a function 'out' or 'inout' parameter. |
| 301 | // |
| 302 | if (Analysis::StatementWritesToVariable(*loopStatement, *initDecl.var())) { |
| 303 | errors.error(loopStatement->fPosition, |
| 304 | "loop index must not be modified within body of the loop"); |
| 305 | return nullptr; |
| 306 | } |
| 307 | |
| 308 | // Finally, compute the iteration count, based on the bounds, and the termination operator. |
| 309 | loopInfo->fCount = 0; |
| 310 | |
| 311 | // Strict ES2 requires loop induction variables to be either 'int' or 'float'. For 'int' |
| 312 | // variables, we simulate the loop using 32-bit signed math to correctly detect the integer |
| 313 | // wraparound behavior that would occur at runtime on the GPU. (For 'float' variables, |
| 314 | // the existing double-precision calculation is sufficient.) |
| 315 | LoopType loop; |
| 316 | if (initDecl.baseType().isSigned()) { |
| 317 | SkASSERT(initDecl.baseType().bitWidth() == 32)static_cast<void>( __builtin_expect(static_cast<bool >(initDecl.baseType().bitWidth() == 32), 1) ? static_cast< void>(0) : []{ do { if (sk_abort_is_enabled()) { do { SkDebugf ("%s:%d" ": fatal error: \"" "check(%s)" "\"\n", "./../../../gfx/skia/skia/src/sksl/analysis/SkSLGetLoopUnrollInfo.cpp" , 317, "initDecl.baseType().bitWidth() == 32"); ; sk_abort_no_print (); } while (false); } } while(false); }() ); |
| 318 | loop = LoopType::kInt; |
| 319 | } else { |
| 320 | SkASSERT(initDecl.baseType().isFloat())static_cast<void>( __builtin_expect(static_cast<bool >(initDecl.baseType().isFloat()), 1) ? static_cast<void >(0) : []{ do { if (sk_abort_is_enabled()) { do { SkDebugf ("%s:%d" ": fatal error: \"" "check(%s)" "\"\n", "./../../../gfx/skia/skia/src/sksl/analysis/SkSLGetLoopUnrollInfo.cpp" , 320, "initDecl.baseType().isFloat()"); ; sk_abort_no_print( ); } while (false); } } while(false); }() ); |
| 321 | loop = LoopType::kFloat; |
| 322 | } |
| 323 | |
| 324 | switch (cond->getOperator().kind()) { |
| 325 | case Operator::Kind::LT: |
| 326 | loopInfo->fCount = calculate_count(loopInfo->fStart, loopEnd, loopInfo->fDelta, |
| 327 | Direction::kForwards, Inclusive::kNo, loop); |
| 328 | break; |
| 329 | |
| 330 | case Operator::Kind::GT: |
| 331 | loopInfo->fCount = calculate_count(loopInfo->fStart, loopEnd, loopInfo->fDelta, |
| 332 | Direction::kBackwards, Inclusive::kNo, loop); |
| 333 | break; |
| 334 | |
| 335 | case Operator::Kind::LTEQ: |
| 336 | loopInfo->fCount = calculate_count(loopInfo->fStart, loopEnd, loopInfo->fDelta, |
| 337 | Direction::kForwards, Inclusive::kYes, loop); |
| 338 | break; |
| 339 | |
| 340 | case Operator::Kind::GTEQ: |
| 341 | loopInfo->fCount = calculate_count(loopInfo->fStart, loopEnd, loopInfo->fDelta, |
| 342 | Direction::kBackwards, Inclusive::kYes, loop); |
| 343 | break; |
| 344 | |
| 345 | case Operator::Kind::NEQ: { |
| 346 | loopInfo->fCount = calculate_count_neq(loopInfo->fStart, loopEnd, loopInfo->fDelta, |
| 347 | loop); |
| 348 | if (loopInfo->fIndex->type().componentType().isFloat()) { |
| 349 | // Rewrite `x != n` tests as `x < n` or `x > n` depending on the loop direction. |
| 350 | // Less-than and greater-than tests avoid infinite loops caused by rounding error. |
| 351 | Operator::Kind op = (loopInfo->fDelta > 0) ? Operator::Kind::LT |
| 352 | : Operator::Kind::GT; |
| 353 | *loopTest = BinaryExpression::Make(context, |
| 354 | cond->fPosition, |
| 355 | cond->left()->clone(), |
| 356 | op, |
| 357 | cond->right()->clone()); |
| 358 | cond = &loopTest->get()->as<BinaryExpression>(); |
Value stored to 'cond' is never read | |
| 359 | } |
| 360 | break; |
| 361 | } |
| 362 | case Operator::Kind::EQEQ: { |
| 363 | if (loopInfo->fStart == loopEnd) { |
| 364 | // Start and end begin in the same place, so we can run one iteration... |
| 365 | if (loopInfo->fDelta) { |
| 366 | // ... and then they diverge, so the loop terminates. |
| 367 | loopInfo->fCount = 1; |
| 368 | } else { |
| 369 | // ... but they never diverge, so the loop runs forever. |
| 370 | loopInfo->fCount = kLoopTerminationLimit; |
| 371 | } |
| 372 | } else { |
| 373 | // Start never equals end, so the loop will not run a single iteration. |
| 374 | loopInfo->fCount = 0; |
| 375 | } |
| 376 | break; |
| 377 | } |
| 378 | default: SkUNREACHABLE__builtin_trap(); |
| 379 | } |
| 380 | |
| 381 | SkASSERT(loopInfo->fCount >= 0)static_cast<void>( __builtin_expect(static_cast<bool >(loopInfo->fCount >= 0), 1) ? static_cast<void> (0) : []{ do { if (sk_abort_is_enabled()) { do { SkDebugf("%s:%d" ": fatal error: \"" "check(%s)" "\"\n", "./../../../gfx/skia/skia/src/sksl/analysis/SkSLGetLoopUnrollInfo.cpp" , 381, "loopInfo->fCount >= 0"); ; sk_abort_no_print(); } while (false); } } while(false); }() ); |
| 382 | if (loopInfo->fCount >= kLoopTerminationLimit) { |
| 383 | errors.error(loopPos, "loop must guarantee termination in fewer iterations"); |
| 384 | return nullptr; |
| 385 | } |
| 386 | |
| 387 | return loopInfo; |
| 388 | } |
| 389 | |
| 390 | } // namespace SkSL |