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_BB_OPTIMIZATIONS_H_
18 #define ART_COMPILER_DEX_BB_OPTIMIZATIONS_H_
19 
20 #include "base/casts.h"
21 #include "compiler_ir.h"
22 #include "dex_flags.h"
23 #include "pass_me.h"
24 #include "mir_graph.h"
25 
26 namespace art {
27 
28 /**
29  * @class String Change
30  * @brief Converts calls to String.<init> to StringFactory instead.
31  */
32 class StringChange : public PassME {
33  public:
StringChange()34   StringChange() : PassME("StringChange", kNoNodes) {
35   }
36 
Start(PassDataHolder * data)37   void Start(PassDataHolder* data) const {
38     DCHECK(data != nullptr);
39     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
40     DCHECK(c_unit != nullptr);
41     c_unit->mir_graph->StringChange();
42   }
43 
Gate(const PassDataHolder * data)44   bool Gate(const PassDataHolder* data) const {
45     DCHECK(data != nullptr);
46     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
47     DCHECK(c_unit != nullptr);
48     return c_unit->mir_graph->HasInvokes();
49   }
50 };
51 
52 /**
53  * @class CacheFieldLoweringInfo
54  * @brief Cache the lowering info for fields used by IGET/IPUT/SGET/SPUT insns.
55  */
56 class CacheFieldLoweringInfo : public PassME {
57  public:
CacheFieldLoweringInfo()58   CacheFieldLoweringInfo() : PassME("CacheFieldLoweringInfo", kNoNodes) {
59   }
60 
Start(PassDataHolder * data)61   void Start(PassDataHolder* data) const {
62     DCHECK(data != nullptr);
63     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
64     DCHECK(c_unit != nullptr);
65     c_unit->mir_graph->DoCacheFieldLoweringInfo();
66   }
67 
Gate(const PassDataHolder * data)68   bool Gate(const PassDataHolder* data) const {
69     DCHECK(data != nullptr);
70     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
71     DCHECK(c_unit != nullptr);
72     return c_unit->mir_graph->HasFieldAccess();
73   }
74 };
75 
76 /**
77  * @class CacheMethodLoweringInfo
78  * @brief Cache the lowering info for methods called by INVOKEs.
79  */
80 class CacheMethodLoweringInfo : public PassME {
81  public:
CacheMethodLoweringInfo()82   CacheMethodLoweringInfo() : PassME("CacheMethodLoweringInfo", kNoNodes) {
83   }
84 
Start(PassDataHolder * data)85   void Start(PassDataHolder* data) const {
86     DCHECK(data != nullptr);
87     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
88     DCHECK(c_unit != nullptr);
89     c_unit->mir_graph->DoCacheMethodLoweringInfo();
90   }
91 
Gate(const PassDataHolder * data)92   bool Gate(const PassDataHolder* data) const {
93     DCHECK(data != nullptr);
94     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
95     DCHECK(c_unit != nullptr);
96     return c_unit->mir_graph->HasInvokes();
97   }
98 };
99 
100 /**
101  * @class SpecialMethodInliner
102  * @brief Performs method inlining pass on special kinds of methods.
103  * @details Special methods are methods that fall in one of the following categories:
104  * empty, instance getter, instance setter, argument return, and constant return.
105  */
106 class SpecialMethodInliner : public PassME {
107  public:
SpecialMethodInliner()108   SpecialMethodInliner() : PassME("SpecialMethodInliner") {
109   }
110 
Gate(const PassDataHolder * data)111   bool Gate(const PassDataHolder* data) const {
112     DCHECK(data != nullptr);
113     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
114     DCHECK(c_unit != nullptr);
115     return c_unit->mir_graph->InlineSpecialMethodsGate();
116   }
117 
Start(PassDataHolder * data)118   void Start(PassDataHolder* data) const {
119     DCHECK(data != nullptr);
120     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
121     DCHECK(c_unit != nullptr);
122     c_unit->mir_graph->InlineSpecialMethodsStart();
123   }
124 
Worker(PassDataHolder * data)125   bool Worker(PassDataHolder* data) const {
126     DCHECK(data != nullptr);
127     PassMEDataHolder* pass_me_data_holder = down_cast<PassMEDataHolder*>(data);
128     CompilationUnit* c_unit = pass_me_data_holder->c_unit;
129     DCHECK(c_unit != nullptr);
130     BasicBlock* bb = pass_me_data_holder->bb;
131     DCHECK(bb != nullptr);
132     c_unit->mir_graph->InlineSpecialMethods(bb);
133     // No need of repeating, so just return false.
134     return false;
135   }
136 
End(PassDataHolder * data)137   void End(PassDataHolder* data) const {
138     DCHECK(data != nullptr);
139     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
140     DCHECK(c_unit != nullptr);
141     c_unit->mir_graph->InlineSpecialMethodsEnd();
142   }
143 };
144 
145 /**
146  * @class CodeLayout
147  * @brief Perform the code layout pass.
148  */
149 class CodeLayout : public PassME {
150  public:
CodeLayout()151   CodeLayout() : PassME("CodeLayout", kAllNodes, kOptimizationBasicBlockChange, "2_post_layout_cfg") {
152   }
153 
Start(PassDataHolder * data)154   void Start(PassDataHolder* data) const {
155     DCHECK(data != nullptr);
156     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
157     DCHECK(c_unit != nullptr);
158     c_unit->mir_graph->VerifyDataflow();
159     c_unit->mir_graph->ClearAllVisitedFlags();
160   }
161 
162   bool Worker(PassDataHolder* data) const;
163 };
164 
165 /**
166  * @class NullCheckElimination
167  * @brief Null check elimination pass.
168  */
169 class NullCheckElimination : public PassME {
170  public:
NullCheckElimination()171   NullCheckElimination()
172     : PassME("NCE", kRepeatingPreOrderDFSTraversal, "3_post_nce_cfg") {
173   }
174 
Gate(const PassDataHolder * data)175   bool Gate(const PassDataHolder* data) const {
176     DCHECK(data != nullptr);
177     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
178     DCHECK(c_unit != nullptr);
179     return c_unit->mir_graph->EliminateNullChecksGate();
180   }
181 
Worker(PassDataHolder * data)182   bool Worker(PassDataHolder* data) const {
183     DCHECK(data != nullptr);
184     PassMEDataHolder* pass_me_data_holder = down_cast<PassMEDataHolder*>(data);
185     CompilationUnit* c_unit = pass_me_data_holder->c_unit;
186     DCHECK(c_unit != nullptr);
187     BasicBlock* bb = pass_me_data_holder->bb;
188     DCHECK(bb != nullptr);
189     return c_unit->mir_graph->EliminateNullChecks(bb);
190   }
191 
End(PassDataHolder * data)192   void End(PassDataHolder* data) const {
193     DCHECK(data != nullptr);
194     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
195     DCHECK(c_unit != nullptr);
196     c_unit->mir_graph->EliminateNullChecksEnd();
197   }
198 };
199 
200 class ClassInitCheckElimination : public PassME {
201  public:
ClassInitCheckElimination()202   ClassInitCheckElimination()
203     : PassME("ClInitCheckElimination", kRepeatingPreOrderDFSTraversal) {
204   }
205 
Gate(const PassDataHolder * data)206   bool Gate(const PassDataHolder* data) const {
207     DCHECK(data != nullptr);
208     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
209     DCHECK(c_unit != nullptr);
210     return c_unit->mir_graph->EliminateClassInitChecksGate();
211   }
212 
Worker(PassDataHolder * data)213   bool Worker(PassDataHolder* data) const {
214     DCHECK(data != nullptr);
215     PassMEDataHolder* pass_me_data_holder = down_cast<PassMEDataHolder*>(data);
216     CompilationUnit* c_unit = pass_me_data_holder->c_unit;
217     DCHECK(c_unit != nullptr);
218     BasicBlock* bb = pass_me_data_holder->bb;
219     DCHECK(bb != nullptr);
220     return c_unit->mir_graph->EliminateClassInitChecks(bb);
221   }
222 
End(PassDataHolder * data)223   void End(PassDataHolder* data) const {
224     DCHECK(data != nullptr);
225     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
226     DCHECK(c_unit != nullptr);
227     c_unit->mir_graph->EliminateClassInitChecksEnd();
228   }
229 };
230 
231 /**
232  * @class GlobalValueNumberingPass
233  * @brief Performs the global value numbering pass.
234  */
235 class GlobalValueNumberingPass : public PassME {
236  public:
GlobalValueNumberingPass()237   GlobalValueNumberingPass()
238     : PassME("GVN", kLoopRepeatingTopologicalSortTraversal, "4_post_gvn_cfg") {
239   }
240 
Gate(const PassDataHolder * data)241   bool Gate(const PassDataHolder* data) const OVERRIDE {
242     DCHECK(data != nullptr);
243     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
244     DCHECK(c_unit != nullptr);
245     return c_unit->mir_graph->ApplyGlobalValueNumberingGate();
246   }
247 
Worker(PassDataHolder * data)248   bool Worker(PassDataHolder* data) const {
249     DCHECK(data != nullptr);
250     PassMEDataHolder* pass_me_data_holder = down_cast<PassMEDataHolder*>(data);
251     CompilationUnit* c_unit = pass_me_data_holder->c_unit;
252     DCHECK(c_unit != nullptr);
253     BasicBlock* bb = pass_me_data_holder->bb;
254     DCHECK(bb != nullptr);
255     return c_unit->mir_graph->ApplyGlobalValueNumbering(bb);
256   }
257 
End(PassDataHolder * data)258   void End(PassDataHolder* data) const OVERRIDE {
259     DCHECK(data != nullptr);
260     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
261     DCHECK(c_unit != nullptr);
262     c_unit->mir_graph->ApplyGlobalValueNumberingEnd();
263   }
264 };
265 
266 /**
267  * @class DeadCodeEliminationPass
268  * @brief Performs the GVN-based dead code elimination pass.
269  */
270 class DeadCodeEliminationPass : public PassME {
271  public:
DeadCodeEliminationPass()272   DeadCodeEliminationPass() : PassME("DCE", kPreOrderDFSTraversal, "4_post_dce_cfg") {
273   }
274 
Gate(const PassDataHolder * data)275   bool Gate(const PassDataHolder* data) const OVERRIDE {
276     DCHECK(data != nullptr);
277     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
278     DCHECK(c_unit != nullptr);
279     return c_unit->mir_graph->EliminateDeadCodeGate();
280   }
281 
Worker(PassDataHolder * data)282   bool Worker(PassDataHolder* data) const {
283     DCHECK(data != nullptr);
284     PassMEDataHolder* pass_me_data_holder = down_cast<PassMEDataHolder*>(data);
285     CompilationUnit* c_unit = pass_me_data_holder->c_unit;
286     DCHECK(c_unit != nullptr);
287     BasicBlock* bb = pass_me_data_holder->bb;
288     DCHECK(bb != nullptr);
289     return c_unit->mir_graph->EliminateDeadCode(bb);
290   }
291 
End(PassDataHolder * data)292   void End(PassDataHolder* data) const OVERRIDE {
293     DCHECK(data != nullptr);
294     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
295     DCHECK(c_unit != nullptr);
296     c_unit->mir_graph->EliminateDeadCodeEnd();
297   }
298 };
299 
300 /**
301  * @class GlobalValueNumberingCleanupPass
302  * @brief Performs the cleanup after global value numbering pass and the dependent
303  *        dead code elimination pass that needs the GVN data.
304  */
305 class GlobalValueNumberingCleanupPass : public PassME {
306  public:
GlobalValueNumberingCleanupPass()307   GlobalValueNumberingCleanupPass()
308     : PassME("GVNCleanup", kNoNodes, "") {
309   }
310 
Start(PassDataHolder * data)311   void Start(PassDataHolder* data) const OVERRIDE {
312     DCHECK(data != nullptr);
313     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
314     DCHECK(c_unit != nullptr);
315     return c_unit->mir_graph->GlobalValueNumberingCleanup();
316   }
317 };
318 
319 /**
320  * @class BBCombine
321  * @brief Perform the basic block combination pass.
322  */
323 class BBCombine : public PassME {
324  public:
BBCombine()325   BBCombine() : PassME("BBCombine", kPreOrderDFSTraversal, "5_post_bbcombine_cfg") {
326   }
327 
Gate(const PassDataHolder * data)328   bool Gate(const PassDataHolder* data) const {
329     DCHECK(data != nullptr);
330     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
331     DCHECK(c_unit != nullptr);
332     return c_unit->mir_graph->HasTryCatchBlocks() ||
333         ((c_unit->disable_opt & (1 << kSuppressExceptionEdges)) != 0);
334   }
335 
336   bool Worker(PassDataHolder* data) const;
337 };
338 
339 /**
340  * @class ConstantPropagation
341  * @brief Perform a constant propagation pass.
342  */
343 class ConstantPropagation : public PassME {
344  public:
ConstantPropagation()345   ConstantPropagation() : PassME("ConstantPropagation") {
346   }
347 
Start(PassDataHolder * data)348   void Start(PassDataHolder* data) const {
349     DCHECK(data != nullptr);
350     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
351     DCHECK(c_unit != nullptr);
352     c_unit->mir_graph->InitializeConstantPropagation();
353   }
354 
Worker(PassDataHolder * data)355   bool Worker(PassDataHolder* data) const {
356     DCHECK(data != nullptr);
357     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
358     DCHECK(c_unit != nullptr);
359     BasicBlock* bb = down_cast<PassMEDataHolder*>(data)->bb;
360     DCHECK(bb != nullptr);
361     c_unit->mir_graph->DoConstantPropagation(bb);
362     // No need of repeating, so just return false.
363     return false;
364   }
365 };
366 
367 /**
368  * @class MethodUseCount
369  * @brief Count the register uses of the method
370  */
371 class MethodUseCount : public PassME {
372  public:
MethodUseCount()373   MethodUseCount() : PassME("UseCount") {
374   }
375 
376   bool Worker(PassDataHolder* data) const;
377 
378   bool Gate(const PassDataHolder* data) const;
379 };
380 
381 /**
382  * @class BasicBlock Optimizations
383  * @brief Any simple BasicBlock optimization can be put here.
384  */
385 class BBOptimizations : public PassME {
386  public:
BBOptimizations()387   BBOptimizations()
388       : PassME("BBOptimizations", kNoNodes, kOptimizationBasicBlockChange, "5_post_bbo_cfg") {
389   }
390 
Gate(const PassDataHolder * data)391   bool Gate(const PassDataHolder* data) const {
392     DCHECK(data != nullptr);
393     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
394     DCHECK(c_unit != nullptr);
395     return ((c_unit->disable_opt & (1 << kBBOpt)) == 0);
396   }
397 
Start(PassDataHolder * data)398   void Start(PassDataHolder* data) const {
399     DCHECK(data != nullptr);
400     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
401     DCHECK(c_unit != nullptr);
402     c_unit->mir_graph->BasicBlockOptimizationStart();
403 
404     /*
405      * This pass has a different ordering depending on the suppress exception,
406      * so do the pass here for now:
407      *   - Later, the Start should just change the ordering and we can move the extended
408      *     creation into the pass driver's main job with a new iterator
409      */
410     c_unit->mir_graph->BasicBlockOptimization();
411   }
412 
End(PassDataHolder * data)413   void End(PassDataHolder* data) const {
414     DCHECK(data != nullptr);
415     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
416     DCHECK(c_unit != nullptr);
417     c_unit->mir_graph->BasicBlockOptimizationEnd();
418     down_cast<PassMEDataHolder*>(data)->dirty = !c_unit->mir_graph->DfsOrdersUpToDate();
419   }
420 };
421 
422 /**
423  * @class SuspendCheckElimination
424  * @brief Any simple BasicBlock optimization can be put here.
425  */
426 class SuspendCheckElimination : public PassME {
427  public:
SuspendCheckElimination()428   SuspendCheckElimination()
429     : PassME("SuspendCheckElimination", kTopologicalSortTraversal, "6_post_sce_cfg") {
430   }
431 
Gate(const PassDataHolder * data)432   bool Gate(const PassDataHolder* data) const {
433     DCHECK(data != nullptr);
434     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
435     DCHECK(c_unit != nullptr);
436     return c_unit->mir_graph->EliminateSuspendChecksGate();
437   }
438 
Worker(PassDataHolder * data)439   bool Worker(PassDataHolder* data) const {
440     DCHECK(data != nullptr);
441     PassMEDataHolder* pass_me_data_holder = down_cast<PassMEDataHolder*>(data);
442     CompilationUnit* c_unit = pass_me_data_holder->c_unit;
443     DCHECK(c_unit != nullptr);
444     BasicBlock* bb = pass_me_data_holder->bb;
445     DCHECK(bb != nullptr);
446     return c_unit->mir_graph->EliminateSuspendChecks(bb);
447   }
448 };
449 
450 }  // namespace art
451 
452 #endif  // ART_COMPILER_DEX_BB_OPTIMIZATIONS_H_
453