dataflow_iterator.h revision 2ce745c06271d5223d57dbf08117b20d5b60694a
1311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* 2311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Copyright (C) 2013 The Android Open Source Project 3311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 4311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Licensed under the Apache License, Version 2.0 (the "License"); 5311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * you may not use this file except in compliance with the License. 6311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * You may obtain a copy of the License at 7311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 8311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * http://www.apache.org/licenses/LICENSE-2.0 9311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 10311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Unless required by applicable law or agreed to in writing, software 11311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * distributed under the License is distributed on an "AS IS" BASIS, 12311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * See the License for the specific language governing permissions and 14311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * limitations under the License. 15311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 16311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 17fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#ifndef ART_COMPILER_DEX_DATAFLOW_ITERATOR_H_ 18fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#define ART_COMPILER_DEX_DATAFLOW_ITERATOR_H_ 19311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 20311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee#include "compiler_ir.h" 21311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee#include "mir_graph.h" 22311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 23311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeenamespace art { 24311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 250665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee /* 260665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * This class supports iterating over lists of basic blocks in various 270665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * interesting orders. Note that for efficiency, the visit orders have been pre-computed. 280665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * The order itself will not change during the iteration. However, for some uses, 290665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * auxiliary data associated with the basic blocks may be changed during the iteration, 300665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * necessitating another pass over the list. 310665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * 320665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * To support this usage, we have is_iterative_. If false, the iteration is a one-shot 330665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * pass through the pre-computed list using Next(). If true, the caller must tell the 340665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * iterator whether a change has been made that necessitates another pass. Use 350665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * Next(had_change) for this. The general idea is that the iterative_ use case means 360665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * that the iterator will keep repeating the full basic block list until a complete pass 370665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * is made through it with no changes. Note that calling Next(true) does not affect 380665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * the iteration order or short-curcuit the current pass - it simply tells the iterator 390665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * that once it has finished walking through the block list it should reset and do another 400665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * full pass through the list. 410665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee */ 42311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee class DataflowIterator { 43311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee public: 44311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 452ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom virtual ~DataflowIterator() {} 46311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 470665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee // Return the next BasicBlock* to visit. 480665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee BasicBlock* Next() { 490665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee DCHECK(!is_iterative_); 500665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee return NextBody(false); 510665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee } 520665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 530665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee /* 540665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * Return the next BasicBlock* to visit, and tell the iterator whether any change 550665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * has occurred that requires another full pass over the block list. 560665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee */ 570665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee BasicBlock* Next(bool had_change) { 580665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee DCHECK(is_iterative_); 590665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee return NextBody(had_change); 600665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee } 610665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 620665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee protected: 630665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee DataflowIterator(MIRGraph* mir_graph, bool is_iterative, int start_idx, int end_idx, 640665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee bool reverse) 650665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee : mir_graph_(mir_graph), 660665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee is_iterative_(is_iterative), 670665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee start_idx_(start_idx), 680665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee end_idx_(end_idx), 69e7a5b7d3fcc3af100fec13af057eecaff1037f2cIan Rogers reverse_(reverse), 70e7a5b7d3fcc3af100fec13af057eecaff1037f2cIan Rogers block_id_list_(NULL), 71e7a5b7d3fcc3af100fec13af057eecaff1037f2cIan Rogers idx_(0), 72e7a5b7d3fcc3af100fec13af057eecaff1037f2cIan Rogers changed_(false) {} 730665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 748d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers virtual BasicBlock* NextBody(bool had_change) ALWAYS_INLINE; 750665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 760665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee MIRGraph* const mir_graph_; 770665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee const bool is_iterative_; 780665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee const int start_idx_; 790665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee const int end_idx_; 800665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee const bool reverse_; 81862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray<int>* block_id_list_; 820665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee int idx_; 830665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee bool changed_; 84311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 85311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee }; // DataflowIterator 860665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 870665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee class ReachableNodesIterator : public DataflowIterator { 880665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee public: 890665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee ReachableNodesIterator(MIRGraph* mir_graph, bool is_iterative) 900665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee : DataflowIterator(mir_graph, is_iterative, 0, 910665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee mir_graph->GetNumReachableBlocks(), false) { 920665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee idx_ = start_idx_; 930665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee block_id_list_ = mir_graph->GetDfsOrder(); 940665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee } 950665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee }; 960665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 970665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee class PreOrderDfsIterator : public DataflowIterator { 980665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee public: 990665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee PreOrderDfsIterator(MIRGraph* mir_graph, bool is_iterative) 1000665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee : DataflowIterator(mir_graph, is_iterative, 0, 1010665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee mir_graph->GetNumReachableBlocks(), false) { 1020665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee idx_ = start_idx_; 1030665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee block_id_list_ = mir_graph->GetDfsOrder(); 1040665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee } 1050665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee }; 1060665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 1070665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee class PostOrderDfsIterator : public DataflowIterator { 1080665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee public: 1090665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 1100665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee PostOrderDfsIterator(MIRGraph* mir_graph, bool is_iterative) 1110665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee : DataflowIterator(mir_graph, is_iterative, 0, 1120665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee mir_graph->GetNumReachableBlocks(), false) { 1130665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee idx_ = start_idx_; 1140665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee block_id_list_ = mir_graph->GetDfsPostOrder(); 1150665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee } 1160665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee }; 1170665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 1180665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee class ReversePostOrderDfsIterator : public DataflowIterator { 1190665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee public: 1200665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee ReversePostOrderDfsIterator(MIRGraph* mir_graph, bool is_iterative) 1210665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee : DataflowIterator(mir_graph, is_iterative, 1220665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee mir_graph->GetNumReachableBlocks() -1, 0, true) { 1230665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee idx_ = start_idx_; 1240665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee block_id_list_ = mir_graph->GetDfsPostOrder(); 1250665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee } 1260665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee }; 1270665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 1280665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee class PostOrderDOMIterator : public DataflowIterator { 1290665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee public: 1300665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee PostOrderDOMIterator(MIRGraph* mir_graph, bool is_iterative) 1310665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee : DataflowIterator(mir_graph, is_iterative, 0, 1320665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee mir_graph->GetNumReachableBlocks(), false) { 1330665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee idx_ = start_idx_; 1340665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee block_id_list_ = mir_graph->GetDomPostOrder(); 1350665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee } 1360665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee }; 1370665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 1380665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee class AllNodesIterator : public DataflowIterator { 1390665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee public: 1400665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee AllNodesIterator(MIRGraph* mir_graph, bool is_iterative) 1410665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee : DataflowIterator(mir_graph, is_iterative, 0, 0, false) { 142862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee all_nodes_iterator_ = 143862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee new (mir_graph->GetArena()) GrowableArray<BasicBlock*>::Iterator (mir_graph->GetBlockList()); 144862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 145862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 1468d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers void Reset() { 147862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee all_nodes_iterator_->Reset(); 1480665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee } 1490665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 1508d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers BasicBlock* NextBody(bool had_change) ALWAYS_INLINE; 151862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 152862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee private: 153862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray<BasicBlock*>::Iterator* all_nodes_iterator_; 1540665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee }; 1550665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 156311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} // namespace art 157311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 158fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#endif // ART_COMPILER_DEX_DATAFLOW_ITERATOR_H_ 159