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