dataflow_iterator.h revision 7940e44f4517de5e2634a7e07d58d0fb26160513 
1/*
2 * Copyright (C) 2013 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_SRC_COMPILER_DEX_DATAFLOW_ITERATOR_H_
18#define ART_SRC_COMPILER_DEX_DATAFLOW_ITERATOR_H_
19
20#include "compiler_ir.h"
21#include "mir_graph.h"
22
23namespace art {
24
25  /*
26   * This class supports iterating over lists of basic blocks in various
27   * interesting orders.  Note that for efficiency, the visit orders have been pre-computed.
28   * The order itself will not change during the iteration.  However, for some uses,
29   * auxiliary data associated with the basic blocks may be changed during the iteration,
30   * necessitating another pass over the list.
31   *
32   * To support this usage, we have is_iterative_.  If false, the iteration is a one-shot
33   * pass through the pre-computed list using Next().  If true, the caller must tell the
34   * iterator whether a change has been made that necessitates another pass.  Use
35   * Next(had_change) for this.  The general idea is that the iterative_ use case means
36   * that the iterator will keep repeating the full basic block list until a complete pass
37   * is made through it with no changes.  Note that calling Next(true) does not affect
38   * the iteration order or short-curcuit the current pass - it simply tells the iterator
39   * that once it has finished walking through the block list it should reset and do another
40   * full pass through the list.
41   */
42  class DataflowIterator {
43    public:
44
45      virtual ~DataflowIterator(){}
46
47      // Return the next BasicBlock* to visit.
48      BasicBlock* Next() {
49        DCHECK(!is_iterative_);
50        return NextBody(false);
51      }
52
53      /*
54       * Return the next BasicBlock* to visit, and tell the iterator whether any change
55       * has occurred that requires another full pass over the block list.
56       */
57      BasicBlock* Next(bool had_change) {
58        DCHECK(is_iterative_);
59        return NextBody(had_change);
60      }
61
62    protected:
63      DataflowIterator(MIRGraph* mir_graph, bool is_iterative, int start_idx, int end_idx,
64                       bool reverse)
65          : mir_graph_(mir_graph),
66            is_iterative_(is_iterative),
67            start_idx_(start_idx),
68            end_idx_(end_idx),
69            reverse_(reverse),
70            block_id_list_(NULL),
71            idx_(0),
72            changed_(false) {}
73
74      virtual BasicBlock* NextBody(bool had_change) ALWAYS_INLINE;
75
76      MIRGraph* const mir_graph_;
77      const bool is_iterative_;
78      const int start_idx_;
79      const int end_idx_;
80      const bool reverse_;
81      GrowableArray<int>* block_id_list_;
82      int idx_;
83      bool changed_;
84
85  }; // DataflowIterator
86
87  class ReachableNodesIterator : public DataflowIterator {
88    public:
89      ReachableNodesIterator(MIRGraph* mir_graph, bool is_iterative)
90          : DataflowIterator(mir_graph, is_iterative, 0,
91                             mir_graph->GetNumReachableBlocks(), false) {
92        idx_ = start_idx_;
93        block_id_list_ = mir_graph->GetDfsOrder();
94      }
95  };
96
97  class PreOrderDfsIterator : public DataflowIterator {
98    public:
99      PreOrderDfsIterator(MIRGraph* mir_graph, bool is_iterative)
100          : DataflowIterator(mir_graph, is_iterative, 0,
101                             mir_graph->GetNumReachableBlocks(), false) {
102        idx_ = start_idx_;
103        block_id_list_ = mir_graph->GetDfsOrder();
104      }
105  };
106
107  class PostOrderDfsIterator : public DataflowIterator {
108    public:
109
110      PostOrderDfsIterator(MIRGraph* mir_graph, bool is_iterative)
111          : DataflowIterator(mir_graph, is_iterative, 0,
112                             mir_graph->GetNumReachableBlocks(), false) {
113        idx_ = start_idx_;
114        block_id_list_ = mir_graph->GetDfsPostOrder();
115      }
116  };
117
118  class ReversePostOrderDfsIterator : public DataflowIterator {
119    public:
120      ReversePostOrderDfsIterator(MIRGraph* mir_graph, bool is_iterative)
121          : DataflowIterator(mir_graph, is_iterative,
122                             mir_graph->GetNumReachableBlocks() -1, 0, true) {
123        idx_ = start_idx_;
124        block_id_list_ = mir_graph->GetDfsPostOrder();
125      }
126  };
127
128  class PostOrderDOMIterator : public DataflowIterator {
129    public:
130      PostOrderDOMIterator(MIRGraph* mir_graph, bool is_iterative)
131          : DataflowIterator(mir_graph, is_iterative, 0,
132                             mir_graph->GetNumReachableBlocks(), false) {
133        idx_ = start_idx_;
134        block_id_list_ = mir_graph->GetDomPostOrder();
135      }
136  };
137
138  class AllNodesIterator : public DataflowIterator {
139    public:
140      AllNodesIterator(MIRGraph* mir_graph, bool is_iterative)
141          : DataflowIterator(mir_graph, is_iterative, 0, 0, false) {
142        all_nodes_iterator_ =
143            new (mir_graph->GetArena()) GrowableArray<BasicBlock*>::Iterator (mir_graph->GetBlockList());
144      }
145
146      void Reset() {
147        all_nodes_iterator_->Reset();
148      }
149
150      BasicBlock* NextBody(bool had_change) ALWAYS_INLINE;
151
152    private:
153      GrowableArray<BasicBlock*>::Iterator* all_nodes_iterator_;
154  };
155
156}  // namespace art
157
158#endif // ART_SRC_COMPILER_DEX_DATAFLOW_ITERATOR_H_
159