Increase GetLoopUnrollInfo loop-count limit to 100,000.
To do this with a clean conscience, I needed to convert the unroll-
counting logic from a linear time algorithm to constant-time. Getting
all the edge cases correct requires a lot of care, and there are now
plenty of unit tests.
Change-Id: I620909d069ac425b7310e345bf80ec844fe035f8
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/445643
Auto-Submit: John Stiles <johnstiles@google.com>
Reviewed-by: Brian Osman <brianosman@google.com>
Commit-Queue: John Stiles <johnstiles@google.com>
diff --git a/resources/sksl/runtime_errors/LoopStructureErrors.rts b/resources/sksl/runtime_errors/LoopStructureErrors.rts
index dd288c9..e71e4b6 100644
--- a/resources/sksl/runtime_errors/LoopStructureErrors.rts
+++ b/resources/sksl/runtime_errors/LoopStructureErrors.rts
@@ -1,10 +1,12 @@
// Expect 15 errors
-void loop_length_128() { for (int i = 0; i < 128; i++) {} } // OK, under kMaxUnrollableLoopLength
-void loop_length_129() { for (int i = 0; i < 129; i++) {} }
-void loop_length_99999() { for (int i = 0; i < 99999; i++) {} }
+void loop_length_128() { for (int i = 0; i < 128; i++) {} } // OK, under kLoopTerminationLimit
+void loop_length_129() { for (int i = 0; i < 129; i++) {} } // OK, under kLoopTerminationLimit
+void loop_length_99999() { for (int i = 0; i < 99999; i++) {} } // OK, under kLoopTerminationLimit
void loop_length_100000() { for (int i = 0; i < 100000; i++) {} }
-void infinite_loop() { for (int i = 0; i < 1; i += 0) {} }
+void infinite_loop1() { for (int i = 0; i < 1; i += 0) {} }
+void infinite_loop2() { for (int i = 3; i >= 3; i += 0) {} }
+void infinite_loop3() { for (float i = 3; i >= 3; i += 1e-20) {} }
void set(out int x) { x = 1; }
void inc(inout int x) { x++; }
diff --git a/src/sksl/SkSLAnalysis.cpp b/src/sksl/SkSLAnalysis.cpp
index c7b0bed..fae0953 100644
--- a/src/sksl/SkSLAnalysis.cpp
+++ b/src/sksl/SkSLAnalysis.cpp
@@ -7,6 +7,7 @@
#include "src/sksl/SkSLAnalysis.h"
+#include "include/private/SkFloatingPoint.h"
#include "include/private/SkSLModifiers.h"
#include "include/private/SkSLProgramElement.h"
#include "include/private/SkSLSampleUsage.h"
@@ -1165,30 +1166,83 @@
}
// Finally, compute the iteration count, based on the bounds, and the termination operator.
- constexpr int kMaxUnrollableLoopLength = 128;
+ static constexpr int kLoopTerminationLimit = 100000;
loopInfo.fCount = 0;
- double val = loopInfo.fStart;
- auto evalCond = [&]() {
- switch (cond.getOperator().kind()) {
- case Token::Kind::TK_GT: return val > loopEnd;
- case Token::Kind::TK_GTEQ: return val >= loopEnd;
- case Token::Kind::TK_LT: return val < loopEnd;
- case Token::Kind::TK_LTEQ: return val <= loopEnd;
- case Token::Kind::TK_EQEQ: return val == loopEnd;
- case Token::Kind::TK_NEQ: return val != loopEnd;
- default: SkUNREACHABLE;
+ auto calculateCount = [](double start, double end, double delta,
+ bool forwards, bool inclusive) -> int {
+ if (forwards != (start < end)) {
+ // The loop starts in a completed state (the start has already advanced past the end).
+ return 0;
}
+ if ((delta == 0.0) || forwards != (delta > 0.0)) {
+ // The loop does not progress toward a completed state, and will never terminate.
+ return kLoopTerminationLimit;
+ }
+ double iterations = sk_ieee_double_divide(end - start, delta);
+ double count = std::ceil(iterations);
+ if (inclusive && (count == iterations)) {
+ count += 1.0;
+ }
+ if (count > kLoopTerminationLimit || !std::isfinite(count)) {
+ // The loop runs for more iterations than we can safely unroll.
+ return kLoopTerminationLimit;
+ }
+ return (int)count;
};
- for (loopInfo.fCount = 0; loopInfo.fCount <= kMaxUnrollableLoopLength; ++loopInfo.fCount) {
- if (!evalCond()) {
+ switch (cond.getOperator().kind()) {
+ case Token::Kind::TK_LT:
+ loopInfo.fCount = calculateCount(loopInfo.fStart, loopEnd, loopInfo.fDelta,
+ /*forwards=*/true, /*inclusive=*/false);
+ break;
+
+ case Token::Kind::TK_GT:
+ loopInfo.fCount = calculateCount(loopInfo.fStart, loopEnd, loopInfo.fDelta,
+ /*forwards=*/false, /*inclusive=*/false);
+ break;
+
+ case Token::Kind::TK_LTEQ:
+ loopInfo.fCount = calculateCount(loopInfo.fStart, loopEnd, loopInfo.fDelta,
+ /*forwards=*/true, /*inclusive=*/true);
+ break;
+
+ case Token::Kind::TK_GTEQ:
+ loopInfo.fCount = calculateCount(loopInfo.fStart, loopEnd, loopInfo.fDelta,
+ /*forwards=*/false, /*inclusive=*/true);
+ break;
+
+ case Token::Kind::TK_NEQ: {
+ float iterations = sk_ieee_double_divide(loopEnd - loopInfo.fStart, loopInfo.fDelta);
+ loopInfo.fCount = std::ceil(iterations);
+ if (loopInfo.fCount < 0 || loopInfo.fCount != iterations ||
+ !std::isfinite(iterations)) {
+ // The loop doesn't reach the exact endpoint and so will never terminate.
+ loopInfo.fCount = kLoopTerminationLimit;
+ }
break;
}
- val += loopInfo.fDelta;
+ case Token::Kind::TK_EQEQ: {
+ if (loopInfo.fStart == loopEnd) {
+ // Start and end begin in the same place, so we can run one iteration...
+ if (loopInfo.fDelta) {
+ // ... and then they diverge, so the loop terminates.
+ loopInfo.fCount = 1;
+ } else {
+ // ... but they never diverge, so the loop runs forever.
+ loopInfo.fCount = kLoopTerminationLimit;
+ }
+ } else {
+ // Start never equals end, so the loop will not run a single iteration.
+ loopInfo.fCount = 0;
+ }
+ break;
+ }
+ default: SkUNREACHABLE;
}
- if (loopInfo.fCount > kMaxUnrollableLoopLength) {
+ SkASSERT(loopInfo.fCount >= 0);
+ if (loopInfo.fCount >= kLoopTerminationLimit) {
return "loop must guarantee termination in fewer iterations";
}
diff --git a/tests/sksl/runtime_errors/LoopStructureErrors.skvm b/tests/sksl/runtime_errors/LoopStructureErrors.skvm
index abd7c5f..ecc5560 100644
--- a/tests/sksl/runtime_errors/LoopStructureErrors.skvm
+++ b/tests/sksl/runtime_errors/LoopStructureErrors.skvm
@@ -1,18 +1,18 @@
### Compilation failed:
-error: 4: loop must guarantee termination in fewer iterations
-error: 5: loop must guarantee termination in fewer iterations
error: 6: loop must guarantee termination in fewer iterations
error: 7: invalid loop expression
-error: 12: loop index must not be modified within body of the loop
-error: 13: loop index must not be modified within body of the loop
+error: 8: invalid loop expression
+error: 9: loop must guarantee termination in fewer iterations
error: 14: loop index must not be modified within body of the loop
-error: 16: loop must guarantee termination in fewer iterations
-error: 17: loop must guarantee termination in fewer iterations
+error: 15: loop index must not be modified within body of the loop
+error: 16: loop index must not be modified within body of the loop
error: 18: loop must guarantee termination in fewer iterations
error: 19: loop must guarantee termination in fewer iterations
-error: 20: invalid loop expression
-error: 21: invalid loop expression
-error: 22: loop must guarantee termination in fewer iterations
-error: 23: loop must guarantee termination in fewer iterations
+error: 20: loop must guarantee termination in fewer iterations
+error: 21: loop must guarantee termination in fewer iterations
+error: 22: invalid loop expression
+error: 23: invalid loop expression
+error: 24: loop must guarantee termination in fewer iterations
+error: 25: loop must guarantee termination in fewer iterations
15 errors