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/// Clear the object and pre-process for the given statement, usually function
20/// body statement.
21void VarBypassDetector::Init(CodeGenModule &CGM, const Stmt *Body) {
22 FromScopes.clear();
23 ToScopes.clear();
24 Bypasses.clear();
25 Scopes = {{~0U, nullptr}};
26 unsigned ParentScope = 0;
27 AlwaysBypassed = !BuildScopeInformation(CGM, S: Body, origParentScope&: 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.
35bool VarBypassDetector::BuildScopeInformation(CodeGenModule &CGM, const Decl *D,
36 unsigned &ParentScope) {
37 const VarDecl *VD = dyn_cast<VarDecl>(Val: D);
38 if (VD && VD->hasLocalStorage()) {
39 Scopes.push_back(Elt: {ParentScope, VD});
40 ParentScope = Scopes.size() - 1;
41 }
42
43 if (const VarDecl *VD = dyn_cast<VarDecl>(Val: D))
44 if (const Expr *Init = VD->getInit())
45 return BuildScopeInformation(CGM, S: Init, origParentScope&: 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.
54bool VarBypassDetector::BuildScopeInformation(CodeGenModule &CGM, 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>(Val: S) && !isa<StmtExpr>(Val: 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>(Val: S)->getInit()) {
72 if (!BuildScopeInformation(CGM, S: Init, origParentScope&: ParentScope))
73 return false;
74 ++StmtsToSkip;
75 }
76 if (const VarDecl *Var = cast<SwitchStmt>(Val: S)->getConditionVariable()) {
77 if (!BuildScopeInformation(CGM, D: Var, ParentScope))
78 return false;
79 ++StmtsToSkip;
80 }
81 [[fallthrough]];
82
83 case Stmt::GotoStmtClass:
84 FromScopes.push_back(Elt: {S, ParentScope});
85 break;
86
87 case Stmt::DeclStmtClass: {
88 const DeclStmt *DS = cast<DeclStmt>(Val: S);
89 for (auto *I : DS->decls())
90 if (!BuildScopeInformation(CGM, D: I, ParentScope&: 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>(Val: SubStmt))
119 Next = SC->getSubStmt();
120 else if (const LabelStmt *LS = dyn_cast<LabelStmt>(Val: 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 bool Result;
131 CGM.runWithSufficientStackSpace(Loc: S->getEndLoc(), Fn: [&] {
132 Result = BuildScopeInformation(CGM, S: SubStmt, origParentScope&: ParentScope);
133 });
134 if (!Result)
135 return false;
136 }
137 return true;
138}
139
140/// Checks each jump and stores each variable declaration they bypass.
141void VarBypassDetector::Detect() {
142 for (const auto &S : FromScopes) {
143 const Stmt *St = S.first;
144 unsigned from = S.second;
145 if (const GotoStmt *GS = dyn_cast<GotoStmt>(Val: St)) {
146 if (const LabelStmt *LS = GS->getLabel()->getStmt())
147 Detect(From: from, To: ToScopes[LS]);
148 } else if (const SwitchStmt *SS = dyn_cast<SwitchStmt>(Val: St)) {
149 for (const SwitchCase *SC = SS->getSwitchCaseList(); SC;
150 SC = SC->getNextSwitchCase()) {
151 Detect(From: from, To: ToScopes[SC]);
152 }
153 } else {
154 llvm_unreachable("goto or switch was expected");
155 }
156 }
157}
158
159/// Checks the jump and stores each variable declaration it bypasses.
160void VarBypassDetector::Detect(unsigned From, unsigned To) {
161 while (From != To) {
162 if (From < To) {
163 assert(Scopes[To].first < To);
164 const auto &ScopeTo = Scopes[To];
165 To = ScopeTo.first;
166 Bypasses.insert(V: ScopeTo.second);
167 } else {
168 assert(Scopes[From].first < From);
169 From = Scopes[From].first;
170 }
171 }
172}
173