clang/lib/CodeGen/VarBypassDetector.cpp

   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 }