858fa0936233dc2810a8dbc58fc7206cae686133
[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 /// A map used to walk the AST in reverse:
24 ///  maps VarDecl to the to parent DeclStmt.
25 typedef llvm::DenseMap<const VarDecl*, const DeclStmt*> DeclParentMap;
26 /// A map used to track which variables have been removed by a refactoring pass.
27 /// It maps the parent ForStmt to the removed index variable's VarDecl.
28 typedef llvm::DenseMap<const ForStmt*, const VarDecl *> ReplacedVarsMap;
29 /// A map used to remember the variable names generated in a Stmt
30 typedef llvm::DenseMap<const Stmt*, std::string> StmtGeneratedVarNameMap;
31 /// A vector used to store the AST subtrees of an Expr.
32 typedef llvm::SmallVector<const Expr *, 16> ComponentVector;
33
34 /// \brief Class used build the reverse AST properties needed to detect
35 /// name conflicts and free variables.
36 class StmtAncestorASTVisitor :
37   public RecursiveASTVisitor<StmtAncestorASTVisitor> {
38  public:
39   StmtAncestorASTVisitor() {
40     StmtStack.push_back(NULL);
41   }
42
43   /// \brief Run the analysis on the TranslationUnitDecl.
44   ///
45   /// In case we're running this analysis multiple times, don't repeat the
46   /// work unless RunEvenIfNotEmpty is set to true.
47   void gatherAncestors(const TranslationUnitDecl *TUD, bool RunEvenIfNotEmpty) {
48     if (RunEvenIfNotEmpty || StmtAncestors.empty()) {
49       TraverseDecl(const_cast<TranslationUnitDecl *>(TUD));
50     }
51   }
52
53   /// Accessor for StmtAncestors.
54   const StmtParentMap &getStmtToParentStmtMap() {
55     return StmtAncestors;
56   }
57
58   /// Accessor for DeclParents.
59   const DeclParentMap &getDeclToParentStmtMap() {
60     return DeclParents;
61   }
62
63   friend class RecursiveASTVisitor<StmtAncestorASTVisitor>;
64
65  private:
66   StmtParentMap StmtAncestors;
67   DeclParentMap DeclParents;
68   llvm::SmallVector<const Stmt *, 16> StmtStack;
69
70   bool TraverseStmt(Stmt *Statement);
71   bool VisitDeclStmt(DeclStmt *Statement);
72 };
73
74 /// Class used to find the variables and member expressions on which an
75 /// arbitrary expression depends.
76 class ComponentFinderASTVisitor :
77   public RecursiveASTVisitor<ComponentFinderASTVisitor> {
78  public:
79   ComponentFinderASTVisitor() { }
80
81   /// Find the components of an expression and place them in a ComponentVector.
82   void findExprComponents(const Expr *SourceExpr) {
83     Expr *E = const_cast<Expr *>(SourceExpr);
84     RecursiveASTVisitor<ComponentFinderASTVisitor>::TraverseStmt(E);
85   }
86
87   /// Accessor for Components.
88   const ComponentVector &getComponents() {
89     return Components;
90   }
91
92   friend class RecursiveASTVisitor<ComponentFinderASTVisitor>;
93
94  private:
95   ComponentVector Components;
96
97   bool VisitDeclRefExpr(DeclRefExpr *E);
98   bool VisitMemberExpr(MemberExpr *Member);
99 };
100
101 /// Class used to determine if an expression is dependent on a variable declared
102 /// inside of the loop where it would be used.
103 class DependencyFinderASTVisitor :
104   public RecursiveASTVisitor<DependencyFinderASTVisitor> {
105  public:
106   DependencyFinderASTVisitor(const StmtParentMap *StmtParents,
107                              const DeclParentMap *DeclParents,
108                              const ReplacedVarsMap *ReplacedVars,
109                              const Stmt *ContainingStmt) :
110     StmtParents(StmtParents), DeclParents(DeclParents),
111     ContainingStmt(ContainingStmt), ReplacedVars(ReplacedVars) { }
112
113   /// Run the analysis on Body, and return true iff the expression depends on
114   /// some variable declared within ContainingStmt.
115   bool dependsOnOutsideVariable(const Stmt *Body) {
116     DependsOnOutsideVariable = false;
117     TraverseStmt(const_cast<Stmt *>(Body));
118     return DependsOnOutsideVariable;
119   }
120
121   friend class RecursiveASTVisitor<DependencyFinderASTVisitor>;
122
123  private:
124   const StmtParentMap *StmtParents;
125   const DeclParentMap *DeclParents;
126   const Stmt *ContainingStmt;
127   const ReplacedVarsMap *ReplacedVars;
128   bool DependsOnOutsideVariable;
129
130   bool VisitVarDecl(VarDecl *VD);
131   bool VisitDeclRefExpr(DeclRefExpr *DRE);
132 };
133
134 /// Class used to determine if any declarations used in a Stmt would conflict
135 /// with a particular identifier. This search includes the names that don't
136 /// actually appear in the AST (i.e. created by a refactoring tool) by including
137 /// a map from Stmts to generated names associated with those stmts.
138 class DeclFinderASTVisitor : public RecursiveASTVisitor<DeclFinderASTVisitor> {
139  public:
140   DeclFinderASTVisitor(const std::string &Name,
141                        const StmtGeneratedVarNameMap *GeneratedDecls) :
142     Name(Name), GeneratedDecls(GeneratedDecls), Found(false) { }
143
144   /// Attempts to find any usages of variables name Name in Body, returning
145   /// true when it is used in Body. This includes the generated loop variables
146   /// of ForStmts which have already been transformed.
147   bool findUsages(const Stmt *Body) {
148     Found = false;
149     TraverseStmt(const_cast<Stmt *>(Body));
150     return Found;
151   }
152
153   friend class RecursiveASTVisitor<DeclFinderASTVisitor>;
154
155  private:
156   std::string Name;
157   /// GeneratedDecls keeps track of ForStmts which have been tranformed, mapping
158   /// each modified ForStmt to the variable generated in the loop.
159   const StmtGeneratedVarNameMap *GeneratedDecls;
160   bool Found;
161
162   bool VisitForStmt(ForStmt *FS);
163   bool VisitNamedDecl(NamedDecl *ND);
164   bool VisitDeclRefExpr(DeclRefExpr *DRE);
165 };
166
167 } // namespace for_migrate
168 } // namespace clang
169 #endif //_LLVM_TOOLS_CLANG_TOOLS_LOOP_CONVERT_STMT_ANCESTOR_H_