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