1 //===--- VarBypassDetector.h - Bypass jumps detector --------------*- C++ -*-=//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "VarBypassDetector.h"
11 
12 #include "clang/AST/Decl.h"
13 #include "clang/AST/Expr.h"
14 #include "clang/AST/Stmt.h"
15 
16 using namespace clang;
17 using namespace CodeGen;
18 
19 /// Clear the object and pre-process for the given statement, usually function
20 /// body statement.
21 void VarBypassDetector::Init(const Stmt *Body) {
22   FromScopes.clear();
23   ToScopes.clear();
24   Bypasses.clear();
25   Scopes = {{~0U, nullptr}};
26   unsigned ParentScope = 0;
27   AlwaysBypassed = !BuildScopeInformation(Body, 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.
35 bool VarBypassDetector::BuildScopeInformation(const Decl *D,
36                                               unsigned &ParentScope) {
37   const VarDecl *VD = dyn_cast<VarDecl>(D);
38   if (VD && VD->hasLocalStorage()) {
39     Scopes.push_back({ParentScope, VD});
40     ParentScope = Scopes.size() - 1;
41   }
42 
43   if (const VarDecl *VD = dyn_cast<VarDecl>(D))
44     if (const Expr *Init = VD->getInit())
45       return BuildScopeInformation(Init, 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.
54 bool VarBypassDetector::BuildScopeInformation(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>(S) && !isa<StmtExpr>(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>(S)->getInit()) {
72       if (!BuildScopeInformation(Init, ParentScope))
73         return false;
74       ++StmtsToSkip;
75     }
76     if (const VarDecl *Var = cast<SwitchStmt>(S)->getConditionVariable()) {
77       if (!BuildScopeInformation(Var, ParentScope))
78         return false;
79       ++StmtsToSkip;
80     }
81   // Fall through
82 
83   case Stmt::GotoStmtClass:
84     FromScopes.push_back({S, ParentScope});
85     break;
86 
87   case Stmt::DeclStmtClass: {
88     const DeclStmt *DS = cast<DeclStmt>(S);
89     for (auto *I : DS->decls())
90       if (!BuildScopeInformation(I, 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 bellow 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>(SubStmt))
119         Next = SC->getSubStmt();
120       else if (const LabelStmt *LS = dyn_cast<LabelStmt>(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     if (!BuildScopeInformation(SubStmt, ParentScope))
131       return false;
132   }
133   return true;
134 }
135 
136 /// Checks each jump and stores each variable declaration they bypass.
137 void VarBypassDetector::Detect() {
138   for (const auto &S : FromScopes) {
139     const Stmt *St = S.first;
140     unsigned from = S.second;
141     if (const GotoStmt *GS = dyn_cast<GotoStmt>(St)) {
142       if (const LabelStmt *LS = GS->getLabel()->getStmt())
143         Detect(from, ToScopes[LS]);
144     } else if (const SwitchStmt *SS = dyn_cast<SwitchStmt>(St)) {
145       for (const SwitchCase *SC = SS->getSwitchCaseList(); SC;
146            SC = SC->getNextSwitchCase()) {
147         Detect(from, ToScopes[SC]);
148       }
149     } else {
150       llvm_unreachable("goto or switch was expected");
151     }
152   }
153 }
154 
155 /// Checks the jump and stores each variable declaration it bypasses.
156 void VarBypassDetector::Detect(unsigned From, unsigned To) {
157   while (From != To) {
158     if (From < To) {
159       assert(Scopes[To].first < To);
160       const auto &ScopeTo = Scopes[To];
161       To = ScopeTo.first;
162       Bypasses.insert(ScopeTo.second);
163     } else {
164       assert(Scopes[From].first < From);
165       From = Scopes[From].first;
166     }
167   }
168 }
169