1 /*
2  * Copyright (C) 2014 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef ART_COMPILER_DEX_PASS_ME_H_
18 #define ART_COMPILER_DEX_PASS_ME_H_
19 
20 #include <string>
21 
22 #include "base/logging.h"
23 #include "pass.h"
24 #include "compiler_ir.h"
25 #include "safe_map.h"
26 
27 namespace art {
28 
29 // Forward declarations.
30 class BasicBlock;
31 struct CompilationUnit;
32 
33 /**
34  * @brief OptimizationFlag is an enumeration to perform certain tasks for a given pass.
35  * @details Each enum should be a power of 2 to be correctly used.
36  */
37 enum OptimizationFlag {
38   kOptimizationBasicBlockChange = 1,  /// @brief Has there been a change to a BasicBlock?
39   kOptimizationDefUsesChange = 2,     /// @brief Has there been a change to a def-use?
40   kLoopStructureChange = 4,           /// @brief Has there been a loop structural change?
41 };
42 std::ostream& operator<<(std::ostream& os, const OptimizationFlag& rhs);
43 
44 // Data holder class.
45 class PassMEDataHolder: public PassDataHolder {
46  public:
47   CompilationUnit* c_unit;
48   BasicBlock* bb;
49   void* data;               /**< @brief Any data the pass wants to use */
50   bool dirty;               /**< @brief Has the pass rendered the CFG dirty, requiring post-opt? */
51 };
52 
53 enum DataFlowAnalysisMode {
54   kAllNodes = 0,                           /// @brief All nodes.
55   kPreOrderDFSTraversal,                   /// @brief Depth-First-Search / Pre-Order.
56   kRepeatingPreOrderDFSTraversal,          /// @brief Depth-First-Search / Repeating Pre-Order.
57   kReversePostOrderDFSTraversal,           /// @brief Depth-First-Search / Reverse Post-Order.
58   kRepeatingPostOrderDFSTraversal,         /// @brief Depth-First-Search / Repeating Post-Order.
59   kRepeatingReversePostOrderDFSTraversal,  /// @brief Depth-First-Search / Repeating Reverse Post-Order.
60   kPostOrderDOMTraversal,                  /// @brief Dominator tree / Post-Order.
61   kTopologicalSortTraversal,               /// @brief Topological Order traversal.
62   kLoopRepeatingTopologicalSortTraversal,  /// @brief Loop-repeating Topological Order traversal.
63   kNoNodes,                                /// @brief Skip BasicBlock traversal.
64 };
65 std::ostream& operator<<(std::ostream& os, const DataFlowAnalysisMode& rhs);
66 
67 /**
68  * @class Pass
69  * @brief Pass is the Pass structure for the optimizations.
70  * @details The following structure has the different optimization passes that we are going to do.
71  */
72 class PassME : public Pass {
73  public:
74   explicit PassME(const char* name, DataFlowAnalysisMode type = kAllNodes,
75           unsigned int flags = 0u, const char* dump = "")
Pass(name)76     : Pass(name), traversal_type_(type), flags_(flags), dump_cfg_folder_(dump) {
77   }
78 
PassME(const char * name,DataFlowAnalysisMode type,const char * dump)79   PassME(const char* name, DataFlowAnalysisMode type, const char* dump)
80     : Pass(name), traversal_type_(type), flags_(0), dump_cfg_folder_(dump) {
81   }
82 
PassME(const char * name,const char * dump)83   PassME(const char* name, const char* dump)
84     : Pass(name), traversal_type_(kAllNodes), flags_(0), dump_cfg_folder_(dump) {
85   }
86 
~PassME()87   ~PassME() {
88     default_options_.clear();
89   }
90 
GetTraversal()91   virtual DataFlowAnalysisMode GetTraversal() const {
92     return traversal_type_;
93   }
94 
95   /**
96    * @return Returns whether the pass has any configurable options.
97    */
HasOptions()98   bool HasOptions() const {
99     return default_options_.size() != 0;
100   }
101 
102   /**
103    * @brief Prints the pass options along with default settings if there are any.
104    * @details The printing is done using LOG(INFO).
105    */
PrintPassDefaultOptions()106   void PrintPassDefaultOptions() const {
107     for (const auto& option : default_options_) {
108       LOG(INFO) << "\t" << option.first << ":" << option.second;
109     }
110   }
111 
112   /**
113    * @brief Prints the pass options along with either default or overridden setting.
114    * @param overridden_options The overridden settings for this pass.
115    */
PrintPassOptions(SafeMap<const std::string,const OptionContent> & overridden_options)116   void PrintPassOptions(SafeMap<const std::string, const OptionContent>& overridden_options) const {
117     // We walk through the default options only to get the pass names. We use GetPassOption to
118     // also consider the overridden ones.
119     for (const auto& option : default_options_) {
120       LOG(INFO) << "\t" << option.first << ":"
121                 << GetPassOption(option.first, overridden_options);
122     }
123   }
124 
125   /**
126    * @brief Used to obtain the option structure for a pass.
127    * @details Will return the overridden option if it exists or default one otherwise.
128    * @param option_name The name of option whose setting to look for.
129    * @param c_unit The compilation unit currently being handled.
130    * @return Returns the option structure containing the option value.
131   */
GetPassOption(const char * option_name,CompilationUnit * c_unit)132   const OptionContent& GetPassOption(const char* option_name, CompilationUnit* c_unit) const {
133     return GetPassOption(option_name, c_unit->overridden_pass_options);
134   }
135 
136   /**
137    * @brief Used to obtain the option for a pass as a string.
138    * @details Will return the overridden option if it exists or default one otherwise.
139    * It will return nullptr if the required option value is not a string.
140    * @param option_name The name of option whose setting to look for.
141    * @param c_unit The compilation unit currently being handled.
142    * @return Returns the overridden option if it exists or the default one otherwise.
143   */
GetStringPassOption(const char * option_name,CompilationUnit * c_unit)144   const char* GetStringPassOption(const char* option_name, CompilationUnit* c_unit) const {
145     return GetStringPassOption(option_name, c_unit->overridden_pass_options);
146   }
147 
148   /**
149     * @brief Used to obtain the pass option value as an integer.
150     * @details Will return the overridden option if it exists or default one otherwise.
151     * It will return 0 if the required option value is not an integer.
152     * @param c_unit The compilation unit currently being handled.
153     * @return Returns the overriden option if it exists or the default one otherwise.
154    */
GetIntegerPassOption(const char * option_name,CompilationUnit * c_unit)155   int64_t GetIntegerPassOption(const char* option_name, CompilationUnit* c_unit) const {
156     return GetIntegerPassOption(option_name, c_unit->overridden_pass_options);
157   }
158 
GetDumpCFGFolder()159   const char* GetDumpCFGFolder() const {
160     return dump_cfg_folder_;
161   }
162 
GetFlag(OptimizationFlag flag)163   bool GetFlag(OptimizationFlag flag) const {
164     return (flags_ & flag);
165   }
166 
167  protected:
GetPassOption(const char * option_name,const SafeMap<const std::string,const OptionContent> & overridden_options)168   const OptionContent& GetPassOption(const char* option_name,
169         const SafeMap<const std::string, const OptionContent>& overridden_options) const {
170     DCHECK(option_name != nullptr);
171 
172     // First check if there are any overridden settings.
173     auto overridden_it = overridden_options.find(std::string(option_name));
174     if (overridden_it != overridden_options.end()) {
175       return overridden_it->second;
176     } else {
177       // Otherwise, there must be a default value for this option name.
178       auto default_it = default_options_.find(option_name);
179       // An invalid option is being requested.
180       if (default_it == default_options_.end()) {
181         LOG(FATAL) << "Fatal: Cannot find an option named \"" << option_name << "\"";
182       }
183 
184       return default_it->second;
185     }
186   }
187 
GetStringPassOption(const char * option_name,const SafeMap<const std::string,const OptionContent> & overridden_options)188   const char* GetStringPassOption(const char* option_name,
189         const SafeMap<const std::string, const OptionContent>& overridden_options) const {
190     const OptionContent& option_content = GetPassOption(option_name, overridden_options);
191     if (option_content.type != OptionContent::kString) {
192       return nullptr;
193     }
194 
195     return option_content.GetString();
196   }
197 
GetIntegerPassOption(const char * option_name,const SafeMap<const std::string,const OptionContent> & overridden_options)198   int64_t GetIntegerPassOption(const char* option_name,
199           const SafeMap<const std::string, const OptionContent>& overridden_options) const {
200     const OptionContent& option_content = GetPassOption(option_name, overridden_options);
201     if (option_content.type != OptionContent::kInteger) {
202       return 0;
203     }
204 
205     return option_content.GetInteger();
206   }
207 
208   /** @brief Type of traversal: determines the order to execute the pass on the BasicBlocks. */
209   const DataFlowAnalysisMode traversal_type_;
210 
211   /** @brief Flags for additional directives: used to determine if a particular
212     * post-optimization pass is necessary. */
213   const unsigned int flags_;
214 
215   /** @brief CFG Dump Folder: what sub-folder to use for dumping the CFGs post pass. */
216   const char* const dump_cfg_folder_;
217 
218   /**
219    * @brief Contains a map of options with the default settings.
220    * @details The constructor of the specific pass instance should fill this
221    * with default options.
222    * */
223   SafeMap<const char*, const OptionContent> default_options_;
224 };
225 }  // namespace art
226 #endif  // ART_COMPILER_DEX_PASS_ME_H_
227