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