[clang] Use a Worklist for some CodeGenFunctions #115395
Conversation
|
Thank you for submitting a Pull Request (PR) to the LLVM Project! This PR will be automatically labeled and the relevant teams will be notified. If you wish to, you can add reviewers by using the "Reviewers" section on this page. If this is not working for you, it is probably because you do not have write permissions for the repository. In which case you can instead tag reviewers by name in a comment by using If you have received no comments on your PR for a week, you can request a review by "ping"ing the PR by adding a comment “Ping”. The common courtesy "ping" rate is once a week. Please remember that you are asking for valuable time from other developers. If you have further questions, they may be answered by the LLVM GitHub User Guide. You can also ask questions in a comment on this PR, on the LLVM Discord or on the forums. |
llvmbot
added
clang
|
@llvm/pr-subscribers-clang-codegen Author: Stephen Verderame (stephenverderame) ChangesThis converts some codegen functions that are called when emitting switch statements to be iterative. The recursive implementations of functions used to determine when certain cases can be omitted causes a stack overflow when attempting to generate IR for deeply nested branches or switch cases. There is a use case that was running into this and causing the compiler to crash. Full diff: https://github.com/llvm/llvm-project/pull/115395.diff 2 Files Affected:
diff --git a/clang/lib/CodeGen/CodeGenFunction.cpp b/clang/lib/CodeGen/CodeGenFunction.cpp
index 6ead45793742d6..8b6d7c6b5746c3 100644
--- a/clang/lib/CodeGen/CodeGenFunction.cpp
+++ b/clang/lib/CodeGen/CodeGenFunction.cpp
@@ -1619,31 +1619,38 @@ void CodeGenFunction::GenerateCode(GlobalDecl GD, llvm::Function *Fn,
/// this statement is not executed normally, it not containing a label means
/// that we can just remove the code.
bool CodeGenFunction::ContainsLabel(const Stmt *S, bool IgnoreCaseStmts) {
- // Null statement, not a label!
- if (!S) return false;
+ llvm::SmallVector<std::pair<const Stmt *, bool>, 32> WorkList;
+ WorkList.emplace_back(S, IgnoreCaseStmts);
- // If this is a label, we have to emit the code, consider something like:
- // if (0) { ... foo: bar(); } goto foo;
- //
- // TODO: If anyone cared, we could track __label__'s, since we know that you
- // can't jump to one from outside their declared region.
- if (isa<LabelStmt>(S))
- return true;
+ while (!WorkList.empty()) {
+ auto [CurStmt, CurIgnoreCaseStmts] = WorkList.pop_back_val();
- // If this is a case/default statement, and we haven't seen a switch, we have
- // to emit the code.
- if (isa<SwitchCase>(S) && !IgnoreCaseStmts)
- return true;
+ // Null statement, not a label!
+ if (!CurStmt)
+ continue;
- // If this is a switch statement, we want to ignore cases below it.
- if (isa<SwitchStmt>(S))
- IgnoreCaseStmts = true;
+ // If this is a label, we have to emit the code, consider something like:
+ // if (0) { ... foo: bar(); } goto foo;
+ //
+ // TODO: If anyone cared, we could track __label__'s, since we know that you
+ // can't jump to one from outside their declared region.
+ if (isa<LabelStmt>(CurStmt))
+ return true;
- // Scan subexpressions for verboten labels.
- for (const Stmt *SubStmt : S->children())
- if (ContainsLabel(SubStmt, IgnoreCaseStmts))
+ // If this is a case/default statement, and we haven't seen a switch, we
+ // have to emit the code.
+ if (isa<SwitchCase>(CurStmt) && !CurIgnoreCaseStmts)
return true;
+ // If this is a switch statement, we want to ignore cases below it.
+ if (isa<SwitchStmt>(CurStmt))
+ CurIgnoreCaseStmts = true;
+
+ // Scan subexpressions for verboten labels.
+ for (const Stmt *SubStmt : CurStmt->children())
+ WorkList.emplace_back(SubStmt, CurIgnoreCaseStmts);
+ }
+
return false;
}
@@ -1651,46 +1658,57 @@ bool CodeGenFunction::ContainsLabel(const Stmt *S, bool IgnoreCaseStmts) {
/// If the statement (recursively) contains a switch or loop with a break
/// inside of it, this is fine.
bool CodeGenFunction::containsBreak(const Stmt *S) {
- // Null statement, not a label!
- if (!S) return false;
+ llvm::SmallVector<const Stmt *, 32> WorkList;
+ WorkList.push_back(S);
+ while (!WorkList.empty()) {
+ const Stmt *CurStmt = WorkList.pop_back_val();
- // If this is a switch or loop that defines its own break scope, then we can
- // include it and anything inside of it.
- if (isa<SwitchStmt>(S) || isa<WhileStmt>(S) || isa<DoStmt>(S) ||
- isa<ForStmt>(S))
- return false;
+ // Null statement, not a label!
+ if (!CurStmt)
+ continue;
- if (isa<BreakStmt>(S))
- return true;
+ // If this is a switch or loop that defines its own break scope, then we can
+ // include it and anything inside of it.
+ if (isa<SwitchStmt>(CurStmt) || isa<WhileStmt>(CurStmt) ||
+ isa<DoStmt>(CurStmt) || isa<ForStmt>(CurStmt))
+ continue;
- // Scan subexpressions for verboten breaks.
- for (const Stmt *SubStmt : S->children())
- if (containsBreak(SubStmt))
+ if (isa<BreakStmt>(CurStmt))
return true;
+ // Scan subexpressions for verboten breaks.
+ for (const Stmt *SubStmt : CurStmt->children())
+ WorkList.push_back(SubStmt);
+ }
return false;
}
bool CodeGenFunction::mightAddDeclToScope(const Stmt *S) {
- if (!S) return false;
-
- // Some statement kinds add a scope and thus never add a decl to the current
- // scope. Note, this list is longer than the list of statements that might
- // have an unscoped decl nested within them, but this way is conservatively
- // correct even if more statement kinds are added.
- if (isa<IfStmt>(S) || isa<SwitchStmt>(S) || isa<WhileStmt>(S) ||
- isa<DoStmt>(S) || isa<ForStmt>(S) || isa<CompoundStmt>(S) ||
- isa<CXXForRangeStmt>(S) || isa<CXXTryStmt>(S) ||
- isa<ObjCForCollectionStmt>(S) || isa<ObjCAtTryStmt>(S))
- return false;
+ llvm::SmallVector<const Stmt *, 32> WorkList;
+ WorkList.push_back(S);
+ while (!WorkList.empty()) {
+ const Stmt *CurStmt = WorkList.pop_back_val();
- if (isa<DeclStmt>(S))
- return true;
+ if (!CurStmt)
+ continue;
- for (const Stmt *SubStmt : S->children())
- if (mightAddDeclToScope(SubStmt))
+ // Some statement kinds add a scope and thus never add a decl to the current
+ // scope. Note, this list is longer than the list of statements that might
+ // have an unscoped decl nested within them, but this way is conservatively
+ // correct even if more statement kinds are added.
+ if (isa<IfStmt>(CurStmt) || isa<SwitchStmt>(CurStmt) ||
+ isa<WhileStmt>(CurStmt) || isa<DoStmt>(CurStmt) ||
+ isa<ForStmt>(CurStmt) || isa<CompoundStmt>(CurStmt) ||
+ isa<CXXForRangeStmt>(CurStmt) || isa<CXXTryStmt>(CurStmt) ||
+ isa<ObjCForCollectionStmt>(CurStmt) || isa<ObjCAtTryStmt>(CurStmt))
+ continue;
+
+ if (isa<DeclStmt>(CurStmt))
return true;
+ for (const Stmt *SubStmt : CurStmt->children())
+ WorkList.push_back(SubStmt);
+ }
return false;
}
diff --git a/clang/test/CodeGen/switch-case-overflow.c b/clang/test/CodeGen/switch-case-overflow.c
new file mode 100644
index 00000000000000..88c21310fc8c7d
--- /dev/null
+++ b/clang/test/CodeGen/switch-case-overflow.c
@@ -0,0 +1,37 @@
+// RUN: split-file %s %t
+// RUN: python %t/gen.py %t/switch-overflow.c %t/tmp.c && %clang_cc1 -emit-llvm %t/tmp.c -o - | FileCheck %t/tmp.c
+
+//--- gen.py
+
+import sys
+file = sys.argv[1]
+out = sys.argv[2]
+with open(file) as f:
+ text = f.read()
+ replacement = ''
+ for i in range(0, 32000):
+ replacement += " case {}:\n".format(i + 1500)
+ text = text.replace("INSERT_CASES_HERE\n", replacement)
+ with open(out, 'w') as of:
+ of.write(text)
+
+//--- switch-overflow.c
+
+// Check this doesn't cause the compiler to crash
+void foo() {
+ // CHECK-LABEL: @foo
+ // CHECK-NOT: switch{{ }}
+ // CHECK-NOT: br{{ }}
+
+ // 1337 does not match a switch case
+ switch (1337) {
+INSERT_CASES_HERE
+ break;
+ }
+
+ // 2000 matches a switch case
+ switch(2000) {
+INSERT_CASES_HERE
+ break;
+ }
+}
|
|
@llvm/pr-subscribers-clang Author: Stephen Verderame (stephenverderame) ChangesThis converts some codegen functions that are called when emitting switch statements to be iterative. The recursive implementations of functions used to determine when certain cases can be omitted causes a stack overflow when attempting to generate IR for deeply nested branches or switch cases. There is a use case that was running into this and causing the compiler to crash. Full diff: https://github.com/llvm/llvm-project/pull/115395.diff 2 Files Affected:
diff --git a/clang/lib/CodeGen/CodeGenFunction.cpp b/clang/lib/CodeGen/CodeGenFunction.cpp
index 6ead45793742d6..8b6d7c6b5746c3 100644
--- a/clang/lib/CodeGen/CodeGenFunction.cpp
+++ b/clang/lib/CodeGen/CodeGenFunction.cpp
@@ -1619,31 +1619,38 @@ void CodeGenFunction::GenerateCode(GlobalDecl GD, llvm::Function *Fn,
/// this statement is not executed normally, it not containing a label means
/// that we can just remove the code.
bool CodeGenFunction::ContainsLabel(const Stmt *S, bool IgnoreCaseStmts) {
- // Null statement, not a label!
- if (!S) return false;
+ llvm::SmallVector<std::pair<const Stmt *, bool>, 32> WorkList;
+ WorkList.emplace_back(S, IgnoreCaseStmts);
- // If this is a label, we have to emit the code, consider something like:
- // if (0) { ... foo: bar(); } goto foo;
- //
- // TODO: If anyone cared, we could track __label__'s, since we know that you
- // can't jump to one from outside their declared region.
- if (isa<LabelStmt>(S))
- return true;
+ while (!WorkList.empty()) {
+ auto [CurStmt, CurIgnoreCaseStmts] = WorkList.pop_back_val();
- // If this is a case/default statement, and we haven't seen a switch, we have
- // to emit the code.
- if (isa<SwitchCase>(S) && !IgnoreCaseStmts)
- return true;
+ // Null statement, not a label!
+ if (!CurStmt)
+ continue;
- // If this is a switch statement, we want to ignore cases below it.
- if (isa<SwitchStmt>(S))
- IgnoreCaseStmts = true;
+ // If this is a label, we have to emit the code, consider something like:
+ // if (0) { ... foo: bar(); } goto foo;
+ //
+ // TODO: If anyone cared, we could track __label__'s, since we know that you
+ // can't jump to one from outside their declared region.
+ if (isa<LabelStmt>(CurStmt))
+ return true;
- // Scan subexpressions for verboten labels.
- for (const Stmt *SubStmt : S->children())
- if (ContainsLabel(SubStmt, IgnoreCaseStmts))
+ // If this is a case/default statement, and we haven't seen a switch, we
+ // have to emit the code.
+ if (isa<SwitchCase>(CurStmt) && !CurIgnoreCaseStmts)
return true;
+ // If this is a switch statement, we want to ignore cases below it.
+ if (isa<SwitchStmt>(CurStmt))
+ CurIgnoreCaseStmts = true;
+
+ // Scan subexpressions for verboten labels.
+ for (const Stmt *SubStmt : CurStmt->children())
+ WorkList.emplace_back(SubStmt, CurIgnoreCaseStmts);
+ }
+
return false;
}
@@ -1651,46 +1658,57 @@ bool CodeGenFunction::ContainsLabel(const Stmt *S, bool IgnoreCaseStmts) {
/// If the statement (recursively) contains a switch or loop with a break
/// inside of it, this is fine.
bool CodeGenFunction::containsBreak(const Stmt *S) {
- // Null statement, not a label!
- if (!S) return false;
+ llvm::SmallVector<const Stmt *, 32> WorkList;
+ WorkList.push_back(S);
+ while (!WorkList.empty()) {
+ const Stmt *CurStmt = WorkList.pop_back_val();
- // If this is a switch or loop that defines its own break scope, then we can
- // include it and anything inside of it.
- if (isa<SwitchStmt>(S) || isa<WhileStmt>(S) || isa<DoStmt>(S) ||
- isa<ForStmt>(S))
- return false;
+ // Null statement, not a label!
+ if (!CurStmt)
+ continue;
- if (isa<BreakStmt>(S))
- return true;
+ // If this is a switch or loop that defines its own break scope, then we can
+ // include it and anything inside of it.
+ if (isa<SwitchStmt>(CurStmt) || isa<WhileStmt>(CurStmt) ||
+ isa<DoStmt>(CurStmt) || isa<ForStmt>(CurStmt))
+ continue;
- // Scan subexpressions for verboten breaks.
- for (const Stmt *SubStmt : S->children())
- if (containsBreak(SubStmt))
+ if (isa<BreakStmt>(CurStmt))
return true;
+ // Scan subexpressions for verboten breaks.
+ for (const Stmt *SubStmt : CurStmt->children())
+ WorkList.push_back(SubStmt);
+ }
return false;
}
bool CodeGenFunction::mightAddDeclToScope(const Stmt *S) {
- if (!S) return false;
-
- // Some statement kinds add a scope and thus never add a decl to the current
- // scope. Note, this list is longer than the list of statements that might
- // have an unscoped decl nested within them, but this way is conservatively
- // correct even if more statement kinds are added.
- if (isa<IfStmt>(S) || isa<SwitchStmt>(S) || isa<WhileStmt>(S) ||
- isa<DoStmt>(S) || isa<ForStmt>(S) || isa<CompoundStmt>(S) ||
- isa<CXXForRangeStmt>(S) || isa<CXXTryStmt>(S) ||
- isa<ObjCForCollectionStmt>(S) || isa<ObjCAtTryStmt>(S))
- return false;
+ llvm::SmallVector<const Stmt *, 32> WorkList;
+ WorkList.push_back(S);
+ while (!WorkList.empty()) {
+ const Stmt *CurStmt = WorkList.pop_back_val();
- if (isa<DeclStmt>(S))
- return true;
+ if (!CurStmt)
+ continue;
- for (const Stmt *SubStmt : S->children())
- if (mightAddDeclToScope(SubStmt))
+ // Some statement kinds add a scope and thus never add a decl to the current
+ // scope. Note, this list is longer than the list of statements that might
+ // have an unscoped decl nested within them, but this way is conservatively
+ // correct even if more statement kinds are added.
+ if (isa<IfStmt>(CurStmt) || isa<SwitchStmt>(CurStmt) ||
+ isa<WhileStmt>(CurStmt) || isa<DoStmt>(CurStmt) ||
+ isa<ForStmt>(CurStmt) || isa<CompoundStmt>(CurStmt) ||
+ isa<CXXForRangeStmt>(CurStmt) || isa<CXXTryStmt>(CurStmt) ||
+ isa<ObjCForCollectionStmt>(CurStmt) || isa<ObjCAtTryStmt>(CurStmt))
+ continue;
+
+ if (isa<DeclStmt>(CurStmt))
return true;
+ for (const Stmt *SubStmt : CurStmt->children())
+ WorkList.push_back(SubStmt);
+ }
return false;
}
diff --git a/clang/test/CodeGen/switch-case-overflow.c b/clang/test/CodeGen/switch-case-overflow.c
new file mode 100644
index 00000000000000..88c21310fc8c7d
--- /dev/null
+++ b/clang/test/CodeGen/switch-case-overflow.c
@@ -0,0 +1,37 @@
+// RUN: split-file %s %t
+// RUN: python %t/gen.py %t/switch-overflow.c %t/tmp.c && %clang_cc1 -emit-llvm %t/tmp.c -o - | FileCheck %t/tmp.c
+
+//--- gen.py
+
+import sys
+file = sys.argv[1]
+out = sys.argv[2]
+with open(file) as f:
+ text = f.read()
+ replacement = ''
+ for i in range(0, 32000):
+ replacement += " case {}:\n".format(i + 1500)
+ text = text.replace("INSERT_CASES_HERE\n", replacement)
+ with open(out, 'w') as of:
+ of.write(text)
+
+//--- switch-overflow.c
+
+// Check this doesn't cause the compiler to crash
+void foo() {
+ // CHECK-LABEL: @foo
+ // CHECK-NOT: switch{{ }}
+ // CHECK-NOT: br{{ }}
+
+ // 1337 does not match a switch case
+ switch (1337) {
+INSERT_CASES_HERE
+ break;
+ }
+
+ // 2000 matches a switch case
+ switch(2000) {
+INSERT_CASES_HERE
+ break;
+ }
+}
|
|
There is obviously a lot of recursion in different parts of the frontend so I suppose there's a question of whether this is something a user should avoid. |
efriedma-quic
left a comment
efriedma-quic
left a comment
There was a problem hiding this comment.
In general, it's hard to avoid recursion: an AST is fundamentally a tree, and the most natural way to walk a tree is recursive, which is why we have issues in the first place. This usually isn't an issue because people don't write deeply nested code, but unfortunately it's easy to get extreme nesting with switch cases. (Also with template instantiation, but that's not relevant in this context.)
A more targeted hack specifically targeting CaseStmt would probably be sufficient, but I guess making the whole thing iterative is also fine.
| // RUN: split-file %s %t | ||
| // RUN: python %t/gen.py %t/switch-overflow.c %t/tmp.c && %clang_cc1 -emit-llvm %t/tmp.c -o - | FileCheck %t/tmp.c | ||
|
|
||
| //--- gen.py |
There was a problem hiding this comment.
I guess 32000 is small enough that a test won't be that expensive, but a python script seems like overkill. Maybe use a bit of C preprocessor trickery like the following:
#define CASES1(n) case n: case n+1: case n+2 case n+3:
#define CASES2(n) CASES1(n) CASES1(n+4) CASES1(n+8) CASES1(n+12)
#define CASES3(n) CASES2(n) CASES2(n+16) CASES2(n+32) CASES2(n+48)
void foo() {
switch (1337) {
CASES3(0)
break;
}
}
There was a problem hiding this comment.
Yeah, we've had to add a bunch of recursion hacks around CaseStmt throughout the compiler over the years, so another one would hardly be unprecedented.
Frankly, we should probably just change the representation in the AST. There are a lot of things in the C grammar that are formally recursive that we fold into flat arrays, like call arguments. This is less self-evident than most of those, but these ubiquitous recursion hacks are a real problem, and we can easily avoid it with a better representation. I feel that argument is pretty compelling. We could just collect sequences of adjacent cases into a single Stmt. There might be places that use CaseStmt* today in a way that assumes it represents a single case, but we can just update those to store a CaseStmt* and an index.
There was a problem hiding this comment.
On my local machine, 32,000 seems to work alright and it seems to crash at somewhere around 60,000. I increased the test size bc of this, but I can change it back if that's too much.
Frankly, we should probably just change the representation in the AST
Should I do this as part of this PR?
There was a problem hiding this comment.
If you don't mind working on the representation issue, I think that would be a reasonable path forward. I can sympathize if you'd rather fix the narrow issue, though.
There was a problem hiding this comment.
Sounds good, I can do that.
This converts some CodeGenFunctions that are called when emitting switch statements to be iterative. Recursive implementations of functions used to determine when certain cases can be omitted can cause a stack overflow when attempting to generate IR for deeply nested branches or switch cases.
stephenverderame
force-pushed
the
switch-crash
branch
from
4ee9ed2 to
71702ac
Compare
4 participants
This converts some codegen functions that are called when emitting switch statements to be iterative. The recursive implementations of functions used to determine when certain cases can be omitted causes a stack overflow when attempting to generate IR for deeply nested branches or switch cases.
There is a use case that was running into this and causing the compiler to crash.