Remove recursion from SkVM dead-code elimination.
Previously, deeply-nested loops could lead to stack overflow during SkVM
dead-code elimination. The DCE algorithm in SkVM now stores its worklist
on the heap and does not rely on recursion. Since we now enforce an
upper bound on maximum program size within SkSL, this worklist's size
should always be reasonable and bounded.
Change-Id: I8b7955298b2540a9f600fc5d94d3bc804c68632c
Bug: skia:12396, oss-fuzz:37827, oss-fuzz:37837
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/445597
Reviewed-by: Brian Osman <brianosman@google.com>
Commit-Queue: Brian Osman <brianosman@google.com>
Auto-Submit: John Stiles <johnstiles@google.com>
diff --git a/src/core/SkVM.cpp b/src/core/SkVM.cpp
index 967b593..8ac3248 100644
--- a/src/core/SkVM.cpp
+++ b/src/core/SkVM.cpp
@@ -441,18 +441,21 @@
std::vector<Instruction> eliminate_dead_code(std::vector<Instruction> program) {
// Determine which Instructions are live by working back from side effects.
std::vector<bool> live(program.size(), false);
- auto mark_live = [&](Val id, auto& recurse) -> void {
- if (live[id] == false) {
- live[id] = true;
- Instruction inst = program[id];
- for (Val arg : {inst.x, inst.y, inst.z, inst.w}) {
- if (arg != NA) { recurse(arg, recurse); }
- }
- }
- };
- for (Val id = 0; id < (Val)program.size(); id++) {
- if (has_side_effect(program[id].op)) {
- mark_live(id, mark_live);
+ std::vector<Val> worklist;
+ for (Val v = 0; v < (Val)program.size(); v++) {
+ if (has_side_effect(program[v].op)) {
+ worklist.push_back(v);
+ do {
+ Val id = worklist.back();
+ worklist.pop_back();
+ if (live[id] == false) {
+ live[id] = true;
+ const Instruction& inst = program[id];
+ for (Val arg : {inst.x, inst.y, inst.z, inst.w}) {
+ if (arg != NA) { worklist.push_back(arg); }
+ }
+ }
+ } while (!worklist.empty());
}
}
diff --git a/tests/SkRuntimeEffectTest.cpp b/tests/SkRuntimeEffectTest.cpp
index 297254e..e80ec15 100644
--- a/tests/SkRuntimeEffectTest.cpp
+++ b/tests/SkRuntimeEffectTest.cpp
@@ -69,6 +69,26 @@
"unknown identifier 'sk_Caps'");
}
+DEF_TEST(SkRuntimeEffect_DeadCodeEliminationStackOverflow, r) {
+ // Verify that a deeply-nested loop does not cause stack overflow during SkVM dead-code
+ // elimination.
+ auto [effect, errorText] = SkRuntimeEffect::MakeForColorFilter(SkString(R"(
+ half4 main(half4 color) {
+ half value = color.r;
+
+ for (int a=0; a<10; ++a) { // 10
+ for (int b=0; b<10; ++b) { // 100
+ for (int c=0; c<10; ++c) { // 1000
+ for (int d=0; d<10; ++d) { // 10000
+ ++value;
+ }}}}
+
+ return value.xxxx;
+ }
+ )"));
+ REPORTER_ASSERT(r, effect, "%s", errorText.c_str());
+}
+
DEF_TEST(SkRuntimeEffectCanDisableES2Restrictions, r) {
auto test_valid_es3 = [](skiatest::Reporter* r, const char* sksl) {
SkRuntimeEffect::Options opt = SkRuntimeEffectPriv::ES3Options();