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.
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.
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.
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.
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.
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