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.
Init(const Stmt * Body)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.
BuildScopeInformation(const Decl * D,unsigned & ParentScope)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.
BuildScopeInformation(const Stmt * S,unsigned & origParentScope)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 LLVM_FALLTHROUGH;
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 below 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.
Detect()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.
Detect(unsigned From,unsigned To)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 }
169