| 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 | |
| 16 | using namespace clang; |
| 17 | using namespace CodeGen; |
| 18 | |
| 19 | /// True if the body contains a goto, switch, indirect goto, or asm goto. Lets |
| 20 | /// Init() skip scope building for the common jump-free function, this is a |
| 21 | /// minor optimization win. |
| 22 | static bool hasJumpStmts(const Stmt *Body) { |
| 23 | llvm::SmallVector<const Stmt *, 32> Worklist; |
| 24 | Worklist.push_back(Elt: Body); |
| 25 | while (!Worklist.empty()) { |
| 26 | const Stmt *S = Worklist.pop_back_val(); |
| 27 | if (!S) |
| 28 | continue; |
| 29 | switch (S->getStmtClass()) { |
| 30 | case Stmt::GotoStmtClass: |
| 31 | case Stmt::SwitchStmtClass: |
| 32 | case Stmt::IndirectGotoStmtClass: |
| 33 | return true; |
| 34 | case Stmt::GCCAsmStmtClass: |
| 35 | if (cast<GCCAsmStmt>(Val: S)->isAsmGoto()) |
| 36 | return true; |
| 37 | break; |
| 38 | default: |
| 39 | break; |
| 40 | } |
| 41 | for (const Stmt *Child : S->children()) |
| 42 | Worklist.push_back(Elt: Child); |
| 43 | } |
| 44 | return false; |
| 45 | } |
| 46 | |
| 47 | /// Clear the object and pre-process for the given statement, usually function |
| 48 | /// body statement. |
| 49 | void VarBypassDetector::Init(CodeGenModule &CGM, const Stmt *Body) { |
| 50 | FromScopes.clear(); |
| 51 | ToScopes.clear(); |
| 52 | Bypasses.clear(); |
| 53 | BypassedVarsAtSource.clear(); |
| 54 | Scopes = {{~0U, nullptr}}; |
| 55 | AlwaysBypassed = false; |
| 56 | if (!hasJumpStmts(Body)) |
| 57 | return; |
| 58 | unsigned ParentScope = 0; |
| 59 | AlwaysBypassed = !BuildScopeInformation(CGM, S: Body, origParentScope&: ParentScope); |
| 60 | if (!AlwaysBypassed) |
| 61 | Detect(); |
| 62 | } |
| 63 | |
| 64 | /// Build scope information for a declaration that is part of a DeclStmt. |
| 65 | /// Returns false if we failed to build scope information and can't tell for |
| 66 | /// which vars are being bypassed. |
| 67 | bool VarBypassDetector::BuildScopeInformation(CodeGenModule &CGM, const Decl *D, |
| 68 | unsigned &ParentScope) { |
| 69 | const VarDecl *VD = dyn_cast<VarDecl>(Val: D); |
| 70 | if (VD && VD->hasLocalStorage()) { |
| 71 | Scopes.push_back(Elt: {ParentScope, VD}); |
| 72 | ParentScope = Scopes.size() - 1; |
| 73 | } |
| 74 | |
| 75 | if (const VarDecl *VD = dyn_cast<VarDecl>(Val: D)) |
| 76 | if (const Expr *Init = VD->getInit()) |
| 77 | return BuildScopeInformation(CGM, S: Init, origParentScope&: ParentScope); |
| 78 | |
| 79 | return true; |
| 80 | } |
| 81 | |
| 82 | /// Walk through the statements, adding any labels or gotos to |
| 83 | /// LabelAndGotoScopes and recursively walking the AST as needed. |
| 84 | /// Returns false if we failed to build scope information and can't tell for |
| 85 | /// which vars are being bypassed. |
| 86 | bool VarBypassDetector::BuildScopeInformation(CodeGenModule &CGM, const Stmt *S, |
| 87 | unsigned &origParentScope) { |
| 88 | // If this is a statement, rather than an expression, scopes within it don't |
| 89 | // propagate out into the enclosing scope. Otherwise we have to worry about |
| 90 | // block literals, which have the lifetime of their enclosing statement. |
| 91 | unsigned independentParentScope = origParentScope; |
| 92 | unsigned &ParentScope = |
| 93 | ((isa<Expr>(Val: S) && !isa<StmtExpr>(Val: S)) ? origParentScope |
| 94 | : independentParentScope); |
| 95 | |
| 96 | unsigned StmtsToSkip = 0u; |
| 97 | |
| 98 | switch (S->getStmtClass()) { |
| 99 | case Stmt::IndirectGotoStmtClass: |
| 100 | return false; |
| 101 | |
| 102 | case Stmt::SwitchStmtClass: |
| 103 | if (const Stmt *Init = cast<SwitchStmt>(Val: S)->getInit()) { |
| 104 | if (!BuildScopeInformation(CGM, S: Init, origParentScope&: ParentScope)) |
| 105 | return false; |
| 106 | ++StmtsToSkip; |
| 107 | } |
| 108 | if (const VarDecl *Var = cast<SwitchStmt>(Val: S)->getConditionVariable()) { |
| 109 | if (!BuildScopeInformation(CGM, D: Var, ParentScope)) |
| 110 | return false; |
| 111 | ++StmtsToSkip; |
| 112 | } |
| 113 | [[fallthrough]]; |
| 114 | |
| 115 | case Stmt::GotoStmtClass: |
| 116 | FromScopes.push_back(Elt: {S, ParentScope}); |
| 117 | break; |
| 118 | |
| 119 | case Stmt::DeclStmtClass: { |
| 120 | const DeclStmt *DS = cast<DeclStmt>(Val: S); |
| 121 | for (auto *I : DS->decls()) |
| 122 | if (!BuildScopeInformation(CGM, D: I, ParentScope&: origParentScope)) |
| 123 | return false; |
| 124 | return true; |
| 125 | } |
| 126 | |
| 127 | case Stmt::CaseStmtClass: |
| 128 | case Stmt::DefaultStmtClass: |
| 129 | case Stmt::LabelStmtClass: |
| 130 | llvm_unreachable("the loop below handles labels and cases" ); |
| 131 | break; |
| 132 | |
| 133 | default: |
| 134 | break; |
| 135 | } |
| 136 | |
| 137 | for (const Stmt *SubStmt : S->children()) { |
| 138 | if (!SubStmt) |
| 139 | continue; |
| 140 | if (StmtsToSkip) { |
| 141 | --StmtsToSkip; |
| 142 | continue; |
| 143 | } |
| 144 | |
| 145 | // Cases, labels, and defaults aren't "scope parents". It's also |
| 146 | // important to handle these iteratively instead of recursively in |
| 147 | // order to avoid blowing out the stack. |
| 148 | while (true) { |
| 149 | const Stmt *Next; |
| 150 | if (const SwitchCase *SC = dyn_cast<SwitchCase>(Val: SubStmt)) |
| 151 | Next = SC->getSubStmt(); |
| 152 | else if (const LabelStmt *LS = dyn_cast<LabelStmt>(Val: SubStmt)) |
| 153 | Next = LS->getSubStmt(); |
| 154 | else |
| 155 | break; |
| 156 | |
| 157 | ToScopes[SubStmt] = ParentScope; |
| 158 | SubStmt = Next; |
| 159 | } |
| 160 | |
| 161 | // Recursively walk the AST. |
| 162 | bool Result; |
| 163 | CGM.runWithSufficientStackSpace(Loc: S->getEndLoc(), Fn: [&] { |
| 164 | Result = BuildScopeInformation(CGM, S: SubStmt, origParentScope&: ParentScope); |
| 165 | }); |
| 166 | if (!Result) |
| 167 | return false; |
| 168 | } |
| 169 | |
| 170 | if (const auto *GAS = dyn_cast<GCCAsmStmt>(Val: S); GAS && GAS->isAsmGoto()) |
| 171 | FromScopes.push_back(Elt: {S, ParentScope}); |
| 172 | |
| 173 | return true; |
| 174 | } |
| 175 | |
| 176 | /// Checks each jump and stores each variable declaration they bypass. |
| 177 | void VarBypassDetector::Detect() { |
| 178 | for (const auto &S : FromScopes) { |
| 179 | const Stmt *St = S.first; |
| 180 | unsigned from = S.second; |
| 181 | if (const GotoStmt *GS = dyn_cast<GotoStmt>(Val: St)) { |
| 182 | if (const LabelStmt *LS = GS->getLabel()->getStmt()) |
| 183 | Detect(From: from, To: ToScopes[LS], Source: GS); |
| 184 | } else if (const SwitchStmt *SS = dyn_cast<SwitchStmt>(Val: St)) { |
| 185 | // Keyed by the switch, not by each case: the dispatch is the jump |
| 186 | // source, and that is where the initialization is emitted. |
| 187 | for (const SwitchCase *SC = SS->getSwitchCaseList(); SC; |
| 188 | SC = SC->getNextSwitchCase()) { |
| 189 | Detect(From: from, To: ToScopes[SC], Source: SS); |
| 190 | } |
| 191 | } else if (const GCCAsmStmt *GAS = dyn_cast<GCCAsmStmt>(Val: St)) { |
| 192 | for (const AddrLabelExpr *L : GAS->labels()) |
| 193 | if (const LabelStmt *LS = L->getLabel()->getStmt()) |
| 194 | Detect(From: from, To: ToScopes[LS], Source: GAS); |
| 195 | } else { |
| 196 | llvm_unreachable("goto, switch, or asm goto was expected" ); |
| 197 | } |
| 198 | } |
| 199 | } |
| 200 | |
| 201 | /// Checks the jump and stores each variable declaration it bypasses. |
| 202 | void VarBypassDetector::Detect(unsigned From, unsigned To, const Stmt *Source) { |
| 203 | while (From != To) { |
| 204 | if (From < To) { |
| 205 | assert(Scopes[To].first < To); |
| 206 | const auto &ScopeTo = Scopes[To]; |
| 207 | To = ScopeTo.first; |
| 208 | Bypasses.insert(V: ScopeTo.second); |
| 209 | if (ScopeTo.second) |
| 210 | BypassedVarsAtSource[Source].insert(X: ScopeTo.second); |
| 211 | } else { |
| 212 | assert(Scopes[From].first < From); |
| 213 | From = Scopes[From].first; |
| 214 | } |
| 215 | } |
| 216 | } |
| 217 | |