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