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