Home | History | Annotate | Line # | Download | only in CodeGen 
      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