clang  9.0.0svn
VarBypassDetector.cpp
Go to the documentation of this file.
1 //===--- VarBypassDetector.h - Bypass jumps detector --------------*- C++ -*-=//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "VarBypassDetector.h"
10 
11 #include "clang/AST/Decl.h"
12 #include "clang/AST/Expr.h"
13 #include "clang/AST/Stmt.h"
14 
15 using namespace clang;
16 using namespace CodeGen;
17 
18 /// Clear the object and pre-process for the given statement, usually function
19 /// body statement.
20 void VarBypassDetector::Init(const Stmt *Body) {
21  FromScopes.clear();
22  ToScopes.clear();
23  Bypasses.clear();
24  Scopes = {{~0U, nullptr}};
25  unsigned ParentScope = 0;
26  AlwaysBypassed = !BuildScopeInformation(Body, ParentScope);
27  if (!AlwaysBypassed)
28  Detect();
29 }
30 
31 /// Build scope information for a declaration that is part of a DeclStmt.
32 /// Returns false if we failed to build scope information and can't tell for
33 /// which vars are being bypassed.
34 bool VarBypassDetector::BuildScopeInformation(const Decl *D,
35  unsigned &ParentScope) {
36  const VarDecl *VD = dyn_cast<VarDecl>(D);
37  if (VD && VD->hasLocalStorage()) {
38  Scopes.push_back({ParentScope, VD});
39  ParentScope = Scopes.size() - 1;
40  }
41 
42  if (const VarDecl *VD = dyn_cast<VarDecl>(D))
43  if (const Expr *Init = VD->getInit())
44  return BuildScopeInformation(Init, ParentScope);
45 
46  return true;
47 }
48 
49 /// Walk through the statements, adding any labels or gotos to
50 /// LabelAndGotoScopes and recursively walking the AST as needed.
51 /// Returns false if we failed to build scope information and can't tell for
52 /// which vars are being bypassed.
53 bool VarBypassDetector::BuildScopeInformation(const Stmt *S,
54  unsigned &origParentScope) {
55  // If this is a statement, rather than an expression, scopes within it don't
56  // propagate out into the enclosing scope. Otherwise we have to worry about
57  // block literals, which have the lifetime of their enclosing statement.
58  unsigned independentParentScope = origParentScope;
59  unsigned &ParentScope =
60  ((isa<Expr>(S) && !isa<StmtExpr>(S)) ? origParentScope
61  : independentParentScope);
62 
63  unsigned StmtsToSkip = 0u;
64 
65  switch (S->getStmtClass()) {
66  case Stmt::IndirectGotoStmtClass:
67  return false;
68 
69  case Stmt::SwitchStmtClass:
70  if (const Stmt *Init = cast<SwitchStmt>(S)->getInit()) {
71  if (!BuildScopeInformation(Init, ParentScope))
72  return false;
73  ++StmtsToSkip;
74  }
75  if (const VarDecl *Var = cast<SwitchStmt>(S)->getConditionVariable()) {
76  if (!BuildScopeInformation(Var, ParentScope))
77  return false;
78  ++StmtsToSkip;
79  }
80  LLVM_FALLTHROUGH;
81 
82  case Stmt::GotoStmtClass:
83  FromScopes.push_back({S, ParentScope});
84  break;
85 
86  case Stmt::DeclStmtClass: {
87  const DeclStmt *DS = cast<DeclStmt>(S);
88  for (auto *I : DS->decls())
89  if (!BuildScopeInformation(I, origParentScope))
90  return false;
91  return true;
92  }
93 
94  case Stmt::CaseStmtClass:
95  case Stmt::DefaultStmtClass:
96  case Stmt::LabelStmtClass:
97  llvm_unreachable("the loop below handles labels and cases");
98  break;
99 
100  default:
101  break;
102  }
103 
104  for (const Stmt *SubStmt : S->children()) {
105  if (!SubStmt)
106  continue;
107  if (StmtsToSkip) {
108  --StmtsToSkip;
109  continue;
110  }
111 
112  // Cases, labels, and defaults aren't "scope parents". It's also
113  // important to handle these iteratively instead of recursively in
114  // order to avoid blowing out the stack.
115  while (true) {
116  const Stmt *Next;
117  if (const SwitchCase *SC = dyn_cast<SwitchCase>(SubStmt))
118  Next = SC->getSubStmt();
119  else if (const LabelStmt *LS = dyn_cast<LabelStmt>(SubStmt))
120  Next = LS->getSubStmt();
121  else
122  break;
123 
124  ToScopes[SubStmt] = ParentScope;
125  SubStmt = Next;
126  }
127 
128  // Recursively walk the AST.
129  if (!BuildScopeInformation(SubStmt, ParentScope))
130  return false;
131  }
132  return true;
133 }
134 
135 /// Checks each jump and stores each variable declaration they bypass.
136 void VarBypassDetector::Detect() {
137  for (const auto &S : FromScopes) {
138  const Stmt *St = S.first;
139  unsigned from = S.second;
140  if (const GotoStmt *GS = dyn_cast<GotoStmt>(St)) {
141  if (const LabelStmt *LS = GS->getLabel()->getStmt())
142  Detect(from, ToScopes[LS]);
143  } else if (const SwitchStmt *SS = dyn_cast<SwitchStmt>(St)) {
144  for (const SwitchCase *SC = SS->getSwitchCaseList(); SC;
145  SC = SC->getNextSwitchCase()) {
146  Detect(from, ToScopes[SC]);
147  }
148  } else {
149  llvm_unreachable("goto or switch was expected");
150  }
151  }
152 }
153 
154 /// Checks the jump and stores each variable declaration it bypasses.
155 void VarBypassDetector::Detect(unsigned From, unsigned To) {
156  while (From != To) {
157  if (From < To) {
158  assert(Scopes[To].first < To);
159  const auto &ScopeTo = Scopes[To];
160  To = ScopeTo.first;
161  Bypasses.insert(ScopeTo.second);
162  } else {
163  assert(Scopes[From].first < From);
164  From = Scopes[From].first;
165  }
166  }
167 }
Stmt - This represents one statement.
Definition: Stmt.h:65
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:87
Represents a variable declaration or definition.
Definition: Decl.h:812
LabelStmt - Represents a label, which has a substatement.
Definition: Stmt.h:1650
child_range children()
Definition: Stmt.cpp:212
This represents one expression.
Definition: Expr.h:108
bool hasLocalStorage() const
Returns true if a variable with function scope is a non-static local variable.
Definition: Decl.h:1035
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
Definition: Stmt.h:1158
Dataflow Directional Tag Classes.
void Init(const Stmt *Body)
Clear the object and pre-process for the given statement, usually function body statement.
const Expr * getInit() const
Definition: Decl.h:1219
StmtClass getStmtClass() const
Definition: Stmt.h:1041
SwitchStmt - This represents a &#39;switch&#39; stmt.
Definition: Stmt.h:1957
decl_range decls()
Definition: Stmt.h:1206
GotoStmt - This represents a direct goto.
Definition: Stmt.h:2395
const SwitchCase * getNextSwitchCase() const
Definition: Stmt.h:1393