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_POST_OPT_PASSES_H_
18 #define ART_COMPILER_DEX_POST_OPT_PASSES_H_
19 
20 #include "base/casts.h"
21 #include "base/logging.h"
22 #include "compiler_ir.h"
23 #include "dex_flags.h"
24 #include "mir_graph.h"
25 #include "pass_me.h"
26 
27 namespace art {
28 
29 /**
30  * @class PassMEMirSsaRep
31  * @brief Convenience class for passes that check MIRGraph::MirSsaRepUpToDate().
32  */
33 class PassMEMirSsaRep : public PassME {
34  public:
35   PassMEMirSsaRep(const char* name, DataFlowAnalysisMode type = kAllNodes)
PassME(name,type)36       : PassME(name, type) {
37   }
38 
Gate(const PassDataHolder * data)39   bool Gate(const PassDataHolder* data) const OVERRIDE {
40     DCHECK(data != nullptr);
41     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
42     DCHECK(c_unit != nullptr);
43     return !c_unit->mir_graph->MirSsaRepUpToDate();
44   }
45 };
46 
47 /**
48  * @class InitializeSSATransformation
49  * @brief There is some data that needs to be initialized before performing
50  * the post optimization passes.
51  */
52 class InitializeSSATransformation : public PassMEMirSsaRep {
53  public:
InitializeSSATransformation()54   InitializeSSATransformation() : PassMEMirSsaRep("InitializeSSATransformation", kNoNodes) {
55   }
56 
Start(PassDataHolder * data)57   void Start(PassDataHolder* data) const {
58     // New blocks may have been inserted so the first thing we do is ensure that
59     // the c_unit's number of blocks matches the actual count of basic blocks.
60     DCHECK(data != nullptr);
61     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
62     DCHECK(c_unit != nullptr);
63     c_unit->mir_graph->SSATransformationStart();
64     c_unit->mir_graph->CompilerInitializeSSAConversion();
65   }
66 };
67 
68 /**
69  * @class ClearPhiInformation
70  * @brief Clear the PHI nodes from the CFG.
71  */
72 class ClearPhiInstructions : public PassMEMirSsaRep {
73  public:
ClearPhiInstructions()74   ClearPhiInstructions() : PassMEMirSsaRep("ClearPhiInstructions") {
75   }
76 
77   bool Worker(PassDataHolder* data) const;
78 };
79 
80 /**
81  * @class CalculatePredecessors
82  * @brief Calculate the predecessor BitVector of each Basicblock.
83  */
84 class CalculatePredecessors : public PassME {
85  public:
CalculatePredecessors()86   CalculatePredecessors() : PassME("CalculatePredecessors", kNoNodes) {
87   }
88 
89   void Start(PassDataHolder* data) const;
90 };
91 
92 /**
93  * @class DFSOrders
94  * @brief Compute the DFS order of the MIR graph
95  */
96 class DFSOrders : public PassME {
97  public:
DFSOrders()98   DFSOrders() : PassME("DFSOrders", kNoNodes) {
99   }
100 
Gate(const PassDataHolder * data)101   bool Gate(const PassDataHolder* data) const {
102     DCHECK(data != nullptr);
103     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
104     DCHECK(c_unit != nullptr);
105     return !c_unit->mir_graph->DfsOrdersUpToDate();
106   }
107 
Start(PassDataHolder * data)108   void Start(PassDataHolder* data) const {
109     DCHECK(data != nullptr);
110     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
111     DCHECK(c_unit != nullptr);
112     c_unit->mir_graph.get()->ComputeDFSOrders();
113   }
114 };
115 
116 /**
117  * @class BuildDomination
118  * @brief Build the domination information of the MIR Graph
119  */
120 class BuildDomination : public PassME {
121  public:
BuildDomination()122   BuildDomination() : PassME("BuildDomination", kNoNodes) {
123   }
124 
Gate(const PassDataHolder * data)125   bool Gate(const PassDataHolder* data) const {
126     DCHECK(data != nullptr);
127     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
128     DCHECK(c_unit != nullptr);
129     return !c_unit->mir_graph->DominationUpToDate();
130   }
131 
Start(PassDataHolder * data)132   void Start(PassDataHolder* data) const {
133     DCHECK(data != nullptr);
134     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
135     DCHECK(c_unit != nullptr);
136     c_unit->mir_graph->ComputeDominators();
137   }
138 
End(PassDataHolder * data)139   void End(PassDataHolder* data) const {
140     DCHECK(data != nullptr);
141     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
142     DCHECK(c_unit != nullptr);
143     // Verify the dataflow information after the pass.
144     if (c_unit->enable_debug & (1 << kDebugVerifyDataflow)) {
145       c_unit->mir_graph->VerifyDataflow();
146     }
147   }
148 };
149 
150 /**
151  * @class TopologicalSortOrders
152  * @brief Compute the topological sort order of the MIR graph
153  */
154 class TopologicalSortOrders : public PassME {
155  public:
TopologicalSortOrders()156   TopologicalSortOrders() : PassME("TopologicalSortOrders", kNoNodes) {
157   }
158 
Gate(const PassDataHolder * data)159   bool Gate(const PassDataHolder* data) const {
160     DCHECK(data != nullptr);
161     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
162     DCHECK(c_unit != nullptr);
163     return !c_unit->mir_graph->TopologicalOrderUpToDate();
164   }
165 
Start(PassDataHolder * data)166   void Start(PassDataHolder* data) const {
167     DCHECK(data != nullptr);
168     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
169     DCHECK(c_unit != nullptr);
170     c_unit->mir_graph.get()->ComputeTopologicalSortOrder();
171   }
172 };
173 
174 /**
175  * @class DefBlockMatrix
176  * @brief Calculate the matrix of definition per basic block
177  */
178 class DefBlockMatrix : public PassMEMirSsaRep {
179  public:
DefBlockMatrix()180   DefBlockMatrix() : PassMEMirSsaRep("DefBlockMatrix", kNoNodes) {
181   }
182 
Start(PassDataHolder * data)183   void Start(PassDataHolder* data) const {
184     DCHECK(data != nullptr);
185     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
186     DCHECK(c_unit != nullptr);
187     c_unit->mir_graph.get()->ComputeDefBlockMatrix();
188   }
189 };
190 
191 /**
192  * @class FindPhiNodeBlocksPass
193  * @brief Pass to find out where we need to insert the phi nodes for the SSA conversion.
194  */
195 class FindPhiNodeBlocksPass : public PassMEMirSsaRep {
196  public:
FindPhiNodeBlocksPass()197   FindPhiNodeBlocksPass() : PassMEMirSsaRep("FindPhiNodeBlocks", kNoNodes) {
198   }
199 
Start(PassDataHolder * data)200   void Start(PassDataHolder* data) const {
201     DCHECK(data != nullptr);
202     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
203     DCHECK(c_unit != nullptr);
204     c_unit->mir_graph.get()->FindPhiNodeBlocks();
205   }
206 };
207 
208 /**
209  * @class SSAConversion
210  * @brief Pass for SSA conversion of MIRs
211  */
212 class SSAConversion : public PassMEMirSsaRep {
213  public:
SSAConversion()214   SSAConversion() : PassMEMirSsaRep("SSAConversion", kNoNodes) {
215   }
216 
Start(PassDataHolder * data)217   void Start(PassDataHolder* data) const {
218     DCHECK(data != nullptr);
219     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
220     DCHECK(c_unit != nullptr);
221     MIRGraph *mir_graph = c_unit->mir_graph.get();
222     mir_graph->ClearAllVisitedFlags();
223     mir_graph->DoDFSPreOrderSSARename(mir_graph->GetEntryBlock());
224   }
225 };
226 
227 /**
228  * @class PhiNodeOperands
229  * @brief Pass to insert the Phi node operands to basic blocks
230  */
231 class PhiNodeOperands : public PassMEMirSsaRep {
232  public:
PhiNodeOperands()233   PhiNodeOperands() : PassMEMirSsaRep("PhiNodeOperands", kPreOrderDFSTraversal) {
234   }
235 
Worker(PassDataHolder * data)236   bool Worker(PassDataHolder* data) const {
237     DCHECK(data != nullptr);
238     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
239     DCHECK(c_unit != nullptr);
240     BasicBlock* bb = down_cast<PassMEDataHolder*>(data)->bb;
241     DCHECK(bb != nullptr);
242     c_unit->mir_graph->InsertPhiNodeOperands(bb);
243     // No need of repeating, so just return false.
244     return false;
245   }
246 };
247 
248 /**
249  * @class InitRegLocations
250  * @brief Initialize Register Locations.
251  */
252 class PerformInitRegLocations : public PassMEMirSsaRep {
253  public:
PerformInitRegLocations()254   PerformInitRegLocations() : PassMEMirSsaRep("PerformInitRegLocation", kNoNodes) {
255   }
256 
Start(PassDataHolder * data)257   void Start(PassDataHolder* data) const {
258     DCHECK(data != nullptr);
259     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
260     DCHECK(c_unit != nullptr);
261     c_unit->mir_graph->InitRegLocations();
262   }
263 };
264 
265 /**
266  * @class TypeInferencePass
267  * @brief Type inference pass.
268  */
269 class TypeInferencePass : public PassMEMirSsaRep {
270  public:
TypeInferencePass()271   TypeInferencePass() : PassMEMirSsaRep("TypeInference", kRepeatingPreOrderDFSTraversal) {
272   }
273 
Start(PassDataHolder * data)274   void Start(PassDataHolder* data) const {
275     DCHECK(data != nullptr);
276     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
277     DCHECK(c_unit != nullptr);
278     c_unit->mir_graph->InferTypesStart();
279   }
280 
Worker(PassDataHolder * data)281   bool Worker(PassDataHolder* data) const {
282     DCHECK(data != nullptr);
283     PassMEDataHolder* pass_me_data_holder = down_cast<PassMEDataHolder*>(data);
284     CompilationUnit* c_unit = pass_me_data_holder->c_unit;
285     DCHECK(c_unit != nullptr);
286     BasicBlock* bb = pass_me_data_holder->bb;
287     DCHECK(bb != nullptr);
288     return c_unit->mir_graph->InferTypes(bb);
289   }
290 
End(PassDataHolder * data)291   void End(PassDataHolder* data) const {
292     DCHECK(data != nullptr);
293     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
294     DCHECK(c_unit != nullptr);
295     c_unit->mir_graph.get()->InferTypesEnd();
296   }
297 };
298 
299 /**
300  * @class FinishSSATransformation
301  * @brief There is some data that needs to be freed after performing the post optimization passes.
302  */
303 class FinishSSATransformation : public PassMEMirSsaRep {
304  public:
FinishSSATransformation()305   FinishSSATransformation() : PassMEMirSsaRep("FinishSSATransformation", kNoNodes) {
306   }
307 
End(PassDataHolder * data)308   void End(PassDataHolder* data) const {
309     DCHECK(data != nullptr);
310     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
311     DCHECK(c_unit != nullptr);
312     c_unit->mir_graph.get()->SSATransformationEnd();
313   }
314 };
315 
316 }  // namespace art
317 
318 #endif  // ART_COMPILER_DEX_POST_OPT_PASSES_H_
319