Szelethus created this revision.
Szelethus added reviewers: xazax.hun, NoQ, vsavchenko, martong, balazske,
baloghadamsoftware, steakhal.
Szelethus added a project: clang.
Herald added subscribers: cfe-commits, ASDenysPetrov, Charusso, gamesh411,
dkrupp, donat.nagy, mikhail.ramalho, a.sidorin, rnkovacs, szepet, whisperity.
Szelethus requested review of this revision.
Suppose you stumble across a `DeclRefExpr` in the AST, that references a
`VarDecl`. How would you know that that variable is written in the containing
statement, or not? One trick would be to ascend the AST through
`Stmt::getParent`, and see whether the variable appears on the left hand side
of the assignment.
Liveness does something similar, but instead of //ascending// the AST, it
//descends// into it with a `StmtVisitor`. However, as [1] demonstrates, the
analysis isn't ran on the AST of an entire function, but rather on CFG, where
the order of the statements, visited in order, would make it impossible to know
this information by descending.
void f() {
int i;
i = 5;
}
`-FunctionDecl 0x55a6e1b070b8 <test.cpp:1:1, line:5:1> line:1:6 f 'void ()'
`-CompoundStmt 0x55a6e1b07298 <col:10, line:5:1>
|-DeclStmt 0x55a6e1b07220 <line:2:3, col:8>
| `-VarDecl 0x55a6e1b071b8 <col:3, col:7> col:7 used i 'int'
`-BinaryOperator 0x55a6e1b07278 <line:4:3, col:7> 'int' lvalue '='
|-DeclRefExpr 0x55a6e1b07238 <col:3> 'int' lvalue Var 0x55a6e1b071b8
'i' 'int'
`-IntegerLiteral 0x55a6e1b07258 <col:7> 'int' 5
void f()
[B2 (ENTRY)]
Succs (1): B1
[B1]
1: int i;
2: 5
3: i
4: [B1.3] = [B1.2]
Preds (1): B2
Succs (1): B0
[B0 (EXIT)]
Preds (1): B1
You can see that the arguments (rightfully so, they need to be evaluated first)
precede the assignment operator. For this reason, Liveness implemented a pass
to scan the CFG and note which variables appear in an assignment.
BUT.
This problem only exists if we traverse a CFGBlock in order. And Liveness in
fact does it reverse order. So a distinct pass is indeed unnecessary, we can
note the appearance of the assignment by the time we reach the variable.
[1] http://lists.llvm.org/pipermail/cfe-dev/2020-July/066330.html
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D87518
Files:
clang/include/clang/Analysis/CFG.h
clang/lib/Analysis/LiveVariables.cpp
Index: clang/lib/Analysis/LiveVariables.cpp
===================================================================
--- clang/lib/Analysis/LiveVariables.cpp
+++ clang/lib/Analysis/LiveVariables.cpp
@@ -323,6 +323,11 @@
}
void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
+ if (LV.killAtAssign && B->getOpcode() == BO_Assign) {
+ if (const auto *DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParens())) {
+ LV.inAssignment[DR] = 1;
+ }
+ }
if (B->isAssignmentOp()) {
if (!LV.killAtAssign)
return;
@@ -511,29 +516,8 @@
llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
// FIXME: we should enqueue using post order.
- for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
{
- const CFGBlock *block = *it;
- worklist.enqueueBlock(block);
-
- // FIXME: Scan for DeclRefExprs using in the LHS of an assignment.
- // We need to do this because we lack context in the reverse analysis
- // to determine if a DeclRefExpr appears in such a context, and thus
- // doesn't constitute a "use".
- if (killAtAssign)
- for (CFGBlock::const_iterator bi = block->begin(), be = block->end();
- bi != be; ++bi) {
- if (Optional<CFGStmt> cs = bi->getAs<CFGStmt>()) {
- const Stmt* stmt = cs->getStmt();
- if (const auto *BO = dyn_cast<BinaryOperator>(stmt)) {
- if (BO->getOpcode() == BO_Assign) {
- if (const auto *DR =
- dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) {
- LV->inAssignment[DR] = 1;
- }
- }
- }
- }
- }
+ for (const CFGBlock *B : cfg->nodes()) {
+ worklist.enqueueBlock(B);
}
while (const CFGBlock *block = worklist.dequeue()) {
Index: clang/include/clang/Analysis/CFG.h
===================================================================
--- clang/include/clang/Analysis/CFG.h
+++ clang/include/clang/Analysis/CFG.h
@@ -1307,6 +1307,10 @@
iterator nodes_begin() { return iterator(Blocks.begin()); }
iterator nodes_end() { return iterator(Blocks.end()); }
+
+ llvm::iterator_range<iterator> nodes() { return *this; }
+ llvm::iterator_range<const_iterator> const_nodes() const { return *this; }
+
const_iterator nodes_begin() const { return const_iterator(Blocks.begin()); }
const_iterator nodes_end() const { return const_iterator(Blocks.end()); }
@@ -1315,6 +1319,13 @@
const_reverse_iterator rbegin() const { return Blocks.rbegin(); }
const_reverse_iterator rend() const { return Blocks.rend(); }
+ llvm::iterator_range<reverse_iterator> reverse_nodes() {
+ return {rbegin(), rend()};
+ }
+ llvm::iterator_range<const_reverse_iterator> const_reverse_nodes() const {
+ return {rbegin(), rend()};
+ }
+
CFGBlock & getEntry() { return *Entry; }
const CFGBlock & getEntry() const { return *Entry; }
CFGBlock & getExit() { return *Exit; }
Index: clang/lib/Analysis/LiveVariables.cpp
===================================================================
--- clang/lib/Analysis/LiveVariables.cpp
+++ clang/lib/Analysis/LiveVariables.cpp
@@ -323,6 +323,11 @@
}
void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
+ if (LV.killAtAssign && B->getOpcode() == BO_Assign) {
+ if (const auto *DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParens())) {
+ LV.inAssignment[DR] = 1;
+ }
+ }
if (B->isAssignmentOp()) {
if (!LV.killAtAssign)
return;
@@ -511,29 +516,8 @@
llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
// FIXME: we should enqueue using post order.
- for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
- const CFGBlock *block = *it;
- worklist.enqueueBlock(block);
-
- // FIXME: Scan for DeclRefExprs using in the LHS of an assignment.
- // We need to do this because we lack context in the reverse analysis
- // to determine if a DeclRefExpr appears in such a context, and thus
- // doesn't constitute a "use".
- if (killAtAssign)
- for (CFGBlock::const_iterator bi = block->begin(), be = block->end();
- bi != be; ++bi) {
- if (Optional<CFGStmt> cs = bi->getAs<CFGStmt>()) {
- const Stmt* stmt = cs->getStmt();
- if (const auto *BO = dyn_cast<BinaryOperator>(stmt)) {
- if (BO->getOpcode() == BO_Assign) {
- if (const auto *DR =
- dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) {
- LV->inAssignment[DR] = 1;
- }
- }
- }
- }
- }
+ for (const CFGBlock *B : cfg->nodes()) {
+ worklist.enqueueBlock(B);
}
while (const CFGBlock *block = worklist.dequeue()) {
Index: clang/include/clang/Analysis/CFG.h
===================================================================
--- clang/include/clang/Analysis/CFG.h
+++ clang/include/clang/Analysis/CFG.h
@@ -1307,6 +1307,10 @@
iterator nodes_begin() { return iterator(Blocks.begin()); }
iterator nodes_end() { return iterator(Blocks.end()); }
+
+ llvm::iterator_range<iterator> nodes() { return *this; }
+ llvm::iterator_range<const_iterator> const_nodes() const { return *this; }
+
const_iterator nodes_begin() const { return const_iterator(Blocks.begin()); }
const_iterator nodes_end() const { return const_iterator(Blocks.end()); }
@@ -1315,6 +1319,13 @@
const_reverse_iterator rbegin() const { return Blocks.rbegin(); }
const_reverse_iterator rend() const { return Blocks.rend(); }
+ llvm::iterator_range<reverse_iterator> reverse_nodes() {
+ return {rbegin(), rend()};
+ }
+ llvm::iterator_range<const_reverse_iterator> const_reverse_nodes() const {
+ return {rbegin(), rend()};
+ }
+
CFGBlock & getEntry() { return *Entry; }
const CFGBlock & getEntry() const { return *Entry; }
CFGBlock & getExit() { return *Exit; }
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
