1//===--- VarBypassDetector.cpp - 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 "CodeGenModule.h"
12#include "clang/AST/Decl.h"
13#include "clang/AST/Expr.h"
14#include "clang/AST/Stmt.h"
15
16using namespace clang;
17using namespace CodeGen;
18
19/// True if the body contains a goto, switch, indirect goto, or asm goto. Lets
20/// Init() skip scope building for the common jump-free function, this is a
21/// minor optimization win.
22static bool hasJumpStmts(const Stmt *Body) {
23 llvm::SmallVector<const Stmt *, 32> Worklist;
24 Worklist.push_back(Elt: Body);
25 while (!Worklist.empty()) {
26 const Stmt *S = Worklist.pop_back_val();
27 if (!S)
28 continue;
29 switch (S->getStmtClass()) {
30 case Stmt::GotoStmtClass:
31 case Stmt::SwitchStmtClass:
32 case Stmt::IndirectGotoStmtClass:
33 return true;
34 case Stmt::GCCAsmStmtClass:
35 if (cast<GCCAsmStmt>(Val: S)->isAsmGoto())
36 return true;
37 break;
38 default:
39 break;
40 }
41 for (const Stmt *Child : S->children())
42 Worklist.push_back(Elt: Child);
43 }
44 return false;
45}
46
47/// Clear the object and pre-process for the given statement, usually function
48/// body statement.
49void VarBypassDetector::Init(CodeGenModule &CGM, const Stmt *Body) {
50 FromScopes.clear();
51 ToScopes.clear();
52 Bypasses.clear();
53 BypassedVarsAtSource.clear();
54 Scopes = {{~0U, nullptr}};
55 AlwaysBypassed = false;
56 if (!hasJumpStmts(Body))
57 return;
58 unsigned ParentScope = 0;
59 AlwaysBypassed = !BuildScopeInformation(CGM, S: Body, origParentScope&: ParentScope);
60 if (!AlwaysBypassed)
61 Detect();
62}
63
64/// Build scope information for a declaration that is part of a DeclStmt.
65/// Returns false if we failed to build scope information and can't tell for
66/// which vars are being bypassed.
67bool VarBypassDetector::BuildScopeInformation(CodeGenModule &CGM, const Decl *D,
68 unsigned &ParentScope) {
69 const VarDecl *VD = dyn_cast<VarDecl>(Val: D);
70 if (VD && VD->hasLocalStorage()) {
71 Scopes.push_back(Elt: {ParentScope, VD});
72 ParentScope = Scopes.size() - 1;
73 }
74
75 if (const VarDecl *VD = dyn_cast<VarDecl>(Val: D))
76 if (const Expr *Init = VD->getInit())
77 return BuildScopeInformation(CGM, S: Init, origParentScope&: ParentScope);
78
79 return true;
80}
81
82/// Walk through the statements, adding any labels or gotos to
83/// LabelAndGotoScopes and recursively walking the AST as needed.
84/// Returns false if we failed to build scope information and can't tell for
85/// which vars are being bypassed.
86bool VarBypassDetector::BuildScopeInformation(CodeGenModule &CGM, const Stmt *S,
87 unsigned &origParentScope) {
88 // If this is a statement, rather than an expression, scopes within it don't
89 // propagate out into the enclosing scope. Otherwise we have to worry about
90 // block literals, which have the lifetime of their enclosing statement.
91 unsigned independentParentScope = origParentScope;
92 unsigned &ParentScope =
93 ((isa<Expr>(Val: S) && !isa<StmtExpr>(Val: S)) ? origParentScope
94 : independentParentScope);
95
96 unsigned StmtsToSkip = 0u;
97
98 switch (S->getStmtClass()) {
99 case Stmt::IndirectGotoStmtClass:
100 return false;
101
102 case Stmt::SwitchStmtClass:
103 if (const Stmt *Init = cast<SwitchStmt>(Val: S)->getInit()) {
104 if (!BuildScopeInformation(CGM, S: Init, origParentScope&: ParentScope))
105 return false;
106 ++StmtsToSkip;
107 }
108 if (const VarDecl *Var = cast<SwitchStmt>(Val: S)->getConditionVariable()) {
109 if (!BuildScopeInformation(CGM, D: Var, ParentScope))
110 return false;
111 ++StmtsToSkip;
112 }
113 [[fallthrough]];
114
115 case Stmt::GotoStmtClass:
116 FromScopes.push_back(Elt: {S, ParentScope});
117 break;
118
119 case Stmt::DeclStmtClass: {
120 const DeclStmt *DS = cast<DeclStmt>(Val: S);
121 for (auto *I : DS->decls())
122 if (!BuildScopeInformation(CGM, D: I, ParentScope&: origParentScope))
123 return false;
124 return true;
125 }
126
127 case Stmt::CaseStmtClass:
128 case Stmt::DefaultStmtClass:
129 case Stmt::LabelStmtClass:
130 llvm_unreachable("the loop below handles labels and cases");
131 break;
132
133 default:
134 break;
135 }
136
137 for (const Stmt *SubStmt : S->children()) {
138 if (!SubStmt)
139 continue;
140 if (StmtsToSkip) {
141 --StmtsToSkip;
142 continue;
143 }
144
145 // Cases, labels, and defaults aren't "scope parents". It's also
146 // important to handle these iteratively instead of recursively in
147 // order to avoid blowing out the stack.
148 while (true) {
149 const Stmt *Next;
150 if (const SwitchCase *SC = dyn_cast<SwitchCase>(Val: SubStmt))
151 Next = SC->getSubStmt();
152 else if (const LabelStmt *LS = dyn_cast<LabelStmt>(Val: SubStmt))
153 Next = LS->getSubStmt();
154 else
155 break;
156
157 ToScopes[SubStmt] = ParentScope;
158 SubStmt = Next;
159 }
160
161 // Recursively walk the AST.
162 bool Result;
163 CGM.runWithSufficientStackSpace(Loc: S->getEndLoc(), Fn: [&] {
164 Result = BuildScopeInformation(CGM, S: SubStmt, origParentScope&: ParentScope);
165 });
166 if (!Result)
167 return false;
168 }
169
170 if (const auto *GAS = dyn_cast<GCCAsmStmt>(Val: S); GAS && GAS->isAsmGoto())
171 FromScopes.push_back(Elt: {S, ParentScope});
172
173 return true;
174}
175
176/// Checks each jump and stores each variable declaration they bypass.
177void VarBypassDetector::Detect() {
178 for (const auto &S : FromScopes) {
179 const Stmt *St = S.first;
180 unsigned from = S.second;
181 if (const GotoStmt *GS = dyn_cast<GotoStmt>(Val: St)) {
182 if (const LabelStmt *LS = GS->getLabel()->getStmt())
183 Detect(From: from, To: ToScopes[LS], Source: GS);
184 } else if (const SwitchStmt *SS = dyn_cast<SwitchStmt>(Val: St)) {
185 // Keyed by the switch, not by each case: the dispatch is the jump
186 // source, and that is where the initialization is emitted.
187 for (const SwitchCase *SC = SS->getSwitchCaseList(); SC;
188 SC = SC->getNextSwitchCase()) {
189 Detect(From: from, To: ToScopes[SC], Source: SS);
190 }
191 } else if (const GCCAsmStmt *GAS = dyn_cast<GCCAsmStmt>(Val: St)) {
192 for (const AddrLabelExpr *L : GAS->labels())
193 if (const LabelStmt *LS = L->getLabel()->getStmt())
194 Detect(From: from, To: ToScopes[LS], Source: GAS);
195 } else {
196 llvm_unreachable("goto, switch, or asm goto was expected");
197 }
198 }
199}
200
201/// Checks the jump and stores each variable declaration it bypasses.
202void VarBypassDetector::Detect(unsigned From, unsigned To, const Stmt *Source) {
203 while (From != To) {
204 if (From < To) {
205 assert(Scopes[To].first < To);
206 const auto &ScopeTo = Scopes[To];
207 To = ScopeTo.first;
208 Bypasses.insert(V: ScopeTo.second);
209 if (ScopeTo.second)
210 BypassedVarsAtSource[Source].insert(X: ScopeTo.second);
211 } else {
212 assert(Scopes[From].first < From);
213 From = Scopes[From].first;
214 }
215 }
216}
217