Fixes according to code review comments
[lldb.git] / clang-tools-extra / loop-convert / StmtAncestor.h
1 //===-- loop-convert/StmtAncestor.h - AST property visitors -----*- 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 // This file contains the declaration several RecursiveASTVisitors used to build
11 // and check data structures used in loop migration.
12 //
13 //===----------------------------------------------------------------------===//
14 #ifndef _LLVM_TOOLS_CLANG_TOOLS_LOOP_CONVERT_STMT_ANCESTOR_H_
15 #define _LLVM_TOOLS_CLANG_TOOLS_LOOP_CONVERT_STMT_ANCESTOR_H_
16 #include "clang/AST/RecursiveASTVisitor.h"
17
18 namespace clang {
19 namespace loop_migrate {
20
21 /// A map used to walk the AST in reverse: maps child Stmt to parent Stmt.
22 typedef llvm::DenseMap<const Stmt*, const Stmt*> StmtParentMap;
23
24 /// A map used to walk the AST in reverse:
25 ///  maps VarDecl to the to parent DeclStmt.
26 typedef llvm::DenseMap<const VarDecl*, const DeclStmt*> DeclParentMap;
27
28 /// A map used to track which variables have been removed by a refactoring pass.
29 /// It maps the parent ForStmt to the removed index variable's VarDecl.
30 typedef llvm::DenseMap<const ForStmt*, const VarDecl *> ReplacedVarsMap;
31
32 /// A map used to remember the variable names generated in a Stmt
33 typedef llvm::DenseMap<const Stmt*, std::string> StmtGeneratedVarNameMap;
34
35 /// A vector used to store the AST subtrees of an Expr.
36 typedef llvm::SmallVector<const Expr *, 16> ComponentVector;
37
38 /// \brief Class used build the reverse AST properties needed to detect
39 /// name conflicts and free variables.
40 class StmtAncestorASTVisitor :
41   public RecursiveASTVisitor<StmtAncestorASTVisitor> {
42  public:
43   StmtAncestorASTVisitor() {
44     StmtStack.push_back(NULL);
45   }
46
47   /// \brief Run the analysis on the TranslationUnitDecl.
48   ///
49   /// In case we're running this analysis multiple times, don't repeat the work.
50   void gatherAncestors(const TranslationUnitDecl *TUD) {
51     if (StmtAncestors.empty())
52       TraverseDecl(const_cast<TranslationUnitDecl *>(TUD));
53   }
54
55   /// Accessor for StmtAncestors.
56   const StmtParentMap &getStmtToParentStmtMap() {
57     return StmtAncestors;
58   }
59
60   /// Accessor for DeclParents.
61   const DeclParentMap &getDeclToParentStmtMap() {
62     return DeclParents;
63   }
64
65   friend class RecursiveASTVisitor<StmtAncestorASTVisitor>;
66
67  private:
68   StmtParentMap StmtAncestors;
69   DeclParentMap DeclParents;
70   llvm::SmallVector<const Stmt *, 16> StmtStack;
71
72   bool TraverseStmt(Stmt *Statement);
73   bool VisitDeclStmt(DeclStmt *Statement);
74 };
75
76 /// Class used to find the variables and member expressions on which an
77 /// arbitrary expression depends.
78 class ComponentFinderASTVisitor :
79   public RecursiveASTVisitor<ComponentFinderASTVisitor> {
80  public:
81   ComponentFinderASTVisitor() { }
82
83   /// Find the components of an expression and place them in a ComponentVector.
84   void findExprComponents(const Expr *SourceExpr) {
85     Expr *E = const_cast<Expr *>(SourceExpr);
86     RecursiveASTVisitor<ComponentFinderASTVisitor>::TraverseStmt(E);
87   }
88
89   /// Accessor for Components.
90   const ComponentVector &getComponents() {
91     return Components;
92   }
93
94   friend class RecursiveASTVisitor<ComponentFinderASTVisitor>;
95
96  private:
97   ComponentVector Components;
98
99   bool VisitDeclRefExpr(DeclRefExpr *E);
100   bool VisitMemberExpr(MemberExpr *Member);
101 };
102
103 /// Class used to determine if an expression is dependent on a variable declared
104 /// inside of the loop where it would be used.
105 class DependencyFinderASTVisitor :
106   public RecursiveASTVisitor<DependencyFinderASTVisitor> {
107  public:
108   DependencyFinderASTVisitor(const StmtParentMap *StmtParents,
109                              const DeclParentMap *DeclParents,
110                              const ReplacedVarsMap *ReplacedVars,
111                              const Stmt *ContainingStmt) :
112     StmtParents(StmtParents), DeclParents(DeclParents),
113     ContainingStmt(ContainingStmt), ReplacedVars(ReplacedVars) { }
114
115   /// \brief Run the analysis on Body, and return true iff the expression
116   /// depends on some variable declared within ContainingStmt.
117   ///
118   /// This is intended to protect against hoisting the container expression
119   /// outside of an inner context if part of that expression is declared in that
120   /// inner context.
121   ///
122   /// For example,
123   ///   const int N = 10, M = 20;
124   ///   int arr[N][M];
125   ///   int getRow();
126   ///
127   ///   for (int i = 0; i < M; ++i) {
128   ///     int k = getRow();
129   ///     printf("%d:", arr[k][i]);
130   ///   }
131   ///
132   /// At first glance, this loop looks like it could be changed to
133   ///   for (int elem : arr[k]) {
134   ///     int k = getIndex();
135   ///     printf("%d:", elem);
136   ///   }
137   /// But this is malformed, since `k` is used before it is defined!
138   ///
139   /// In order to avoid this, this class looks at the container expression
140   /// `arr[k]` and decides whether or not it contains a sub-expression declared
141   /// within the the loop body.
142   bool dependsOnOutsideVariable(const Stmt *Body) {
143     DependsOnOutsideVariable = false;
144     TraverseStmt(const_cast<Stmt *>(Body));
145     return DependsOnOutsideVariable;
146   }
147
148   friend class RecursiveASTVisitor<DependencyFinderASTVisitor>;
149
150  private:
151   const StmtParentMap *StmtParents;
152   const DeclParentMap *DeclParents;
153   const Stmt *ContainingStmt;
154   const ReplacedVarsMap *ReplacedVars;
155   bool DependsOnOutsideVariable;
156
157   bool VisitVarDecl(VarDecl *VD);
158   bool VisitDeclRefExpr(DeclRefExpr *DRE);
159 };
160
161 /// Class used to determine if any declarations used in a Stmt would conflict
162 /// with a particular identifier. This search includes the names that don't
163 /// actually appear in the AST (i.e. created by a refactoring tool) by including
164 /// a map from Stmts to generated names associated with those stmts.
165 class DeclFinderASTVisitor : public RecursiveASTVisitor<DeclFinderASTVisitor> {
166  public:
167   DeclFinderASTVisitor(const std::string &Name,
168                        const StmtGeneratedVarNameMap *GeneratedDecls) :
169     Name(Name), GeneratedDecls(GeneratedDecls), Found(false) { }
170
171   /// Attempts to find any usages of variables name Name in Body, returning
172   /// true when it is used in Body. This includes the generated loop variables
173   /// of ForStmts which have already been transformed.
174   bool findUsages(const Stmt *Body) {
175     Found = false;
176     TraverseStmt(const_cast<Stmt *>(Body));
177     return Found;
178   }
179
180   friend class RecursiveASTVisitor<DeclFinderASTVisitor>;
181
182  private:
183   std::string Name;
184   /// GeneratedDecls keeps track of ForStmts which have been tranformed, mapping
185   /// each modified ForStmt to the variable generated in the loop.
186   const StmtGeneratedVarNameMap *GeneratedDecls;
187   bool Found;
188
189   bool VisitForStmt(ForStmt *FS);
190   bool VisitNamedDecl(NamedDecl *ND);
191   bool VisitDeclRefExpr(DeclRefExpr *DRE);
192 };
193
194 } // namespace for_migrate
195 } // namespace clang
196 #endif //_LLVM_TOOLS_CLANG_TOOLS_LOOP_CONVERT_STMT_ANCESTOR_H_