lib/CodeGen/VarBypassDetector.cpp

   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 below 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 }