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
15using namespace clang;
16using namespace CodeGen;
17
18/// Clear the object and pre-process for the given statement, usually function
19/// body statement.
20void 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.
34bool 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.
53bool 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.
136void 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.
155void 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