Page MenuHomePhabricator

[analyzer][Liveness][NFC] Remove an unneeded pass to collect variables that appear in an assignment
ClosedPublic

Authored by Szelethus on Sep 11 2020, 9:02 AM.

Details

Summary

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, and after finding an assignment, it notes that the LHS appears in the context of an assignemnt. 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

Diff Detail

Event Timeline

Szelethus created this revision.Sep 11 2020, 9:02 AM
Szelethus requested review of this revision.Sep 11 2020, 9:02 AM
Szelethus edited the summary of this revision. (Show Details)
xazax.hun added inline comments.Sep 11 2020, 10:50 AM
clang/lib/Analysis/LiveVariables.cpp
328

Do we actually need to specially handle BO_Assign? What about += and other assignment operators? I know that the original code did not consider them, but I do not have a good intuition why.

xazax.hun added inline comments.Sep 11 2020, 10:51 AM
clang/lib/Analysis/LiveVariables.cpp
328

Never mind, I those operators are reads too :)

xazax.hun accepted this revision.Sep 11 2020, 10:52 AM

LGTM! Looks a lot cleaner this way.

This revision is now accepted and ready to land.Sep 11 2020, 10:52 AM
xazax.hun added inline comments.Sep 11 2020, 10:54 AM
clang/lib/Analysis/LiveVariables.cpp
334

Nit: Maybe moving this to the front of the function would simplify the code a bit.

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.

Should this patch depend on https://reviews.llvm.org/D87519?

clang/include/clang/Analysis/CFG.h
1311

Do we convert this to CFGBlock *Entry here? If yes, please comment it there in the code, so others should not be forced to dig up the first data member. (If no then this code is hard to understand.)

Even better, why not return *Entry?

martong added inline comments.Sep 14 2020, 5:59 AM
clang/include/clang/Analysis/CFG.h
1311

Uuups, okay, so we use begin and end here, my bad. But then perhaps it is better to explicitly write this down. E.g. return {begin(), end()}, would be much cleaner IMHO.

This revision was landed with ongoing or failed builds.Feb 12 2021, 7:20 AM
This revision was automatically updated to reflect the committed changes.