Home | History | Annotate | Download | only in dex 
      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_COMPILER_DEX_DATAFLOW_ITERATOR_H_
     18 #define ART_COMPILER_DEX_DATAFLOW_ITERATOR_H_
     19 
     20 #include "compiler_ir.h"
     21 #include "mir_graph.h"
     22 
     23 namespace 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       virtual ~DataflowIterator() {}
     45 
     46       // Return the next BasicBlock* to visit.
     47       BasicBlock* Next() {
     48         DCHECK(!is_iterative_);
     49         return NextBody(false);
     50       }
     51 
     52       /*
     53        * Return the next BasicBlock* to visit, and tell the iterator whether any change
     54        * has occurred that requires another full pass over the block list.
     55        */
     56       BasicBlock* Next(bool had_change) {
     57         DCHECK(is_iterative_);
     58         return NextBody(had_change);
     59       }
     60 
     61     protected:
     62       DataflowIterator(MIRGraph* mir_graph, bool is_iterative, int start_idx, int end_idx,
     63                        bool reverse)
     64           : mir_graph_(mir_graph),
     65             is_iterative_(is_iterative),
     66             start_idx_(start_idx),
     67             end_idx_(end_idx),
     68             reverse_(reverse),
     69             block_id_list_(NULL),
     70             idx_(0),
     71             changed_(false) {}
     72 
     73       virtual BasicBlock* NextBody(bool had_change) ALWAYS_INLINE;
     74 
     75       MIRGraph* const mir_graph_;
     76       const bool is_iterative_;
     77       const int start_idx_;
     78       const int end_idx_;
     79       const bool reverse_;
     80       GrowableArray<int>* block_id_list_;
     81       int idx_;
     82       bool changed_;
     83   };  // DataflowIterator
     84 
     85   class ReachableNodesIterator : public DataflowIterator {
     86     public:
     87       ReachableNodesIterator(MIRGraph* mir_graph, bool is_iterative)
     88           : DataflowIterator(mir_graph, is_iterative, 0,
     89                              mir_graph->GetNumReachableBlocks(), false) {
     90         idx_ = start_idx_;
     91         block_id_list_ = mir_graph->GetDfsOrder();
     92       }
     93   };
     94 
     95   class PreOrderDfsIterator : public DataflowIterator {
     96     public:
     97       PreOrderDfsIterator(MIRGraph* mir_graph, bool is_iterative)
     98           : DataflowIterator(mir_graph, is_iterative, 0,
     99                              mir_graph->GetNumReachableBlocks(), false) {
    100         idx_ = start_idx_;
    101         block_id_list_ = mir_graph->GetDfsOrder();
    102       }
    103   };
    104 
    105   class PostOrderDfsIterator : public DataflowIterator {
    106     public:
    107       PostOrderDfsIterator(MIRGraph* mir_graph, bool is_iterative)
    108           : DataflowIterator(mir_graph, is_iterative, 0,
    109                              mir_graph->GetNumReachableBlocks(), false) {
    110         idx_ = start_idx_;
    111         block_id_list_ = mir_graph->GetDfsPostOrder();
    112       }
    113   };
    114 
    115   class ReversePostOrderDfsIterator : public DataflowIterator {
    116     public:
    117       ReversePostOrderDfsIterator(MIRGraph* mir_graph, bool is_iterative)
    118           : DataflowIterator(mir_graph, is_iterative,
    119                              mir_graph->GetNumReachableBlocks() -1, 0, true) {
    120         idx_ = start_idx_;
    121         block_id_list_ = mir_graph->GetDfsPostOrder();
    122       }
    123   };
    124 
    125   class PostOrderDOMIterator : public DataflowIterator {
    126     public:
    127       PostOrderDOMIterator(MIRGraph* mir_graph, bool is_iterative)
    128           : DataflowIterator(mir_graph, is_iterative, 0,
    129                              mir_graph->GetNumReachableBlocks(), false) {
    130         idx_ = start_idx_;
    131         block_id_list_ = mir_graph->GetDomPostOrder();
    132       }
    133   };
    134 
    135   class AllNodesIterator : public DataflowIterator {
    136     public:
    137       AllNodesIterator(MIRGraph* mir_graph, bool is_iterative)
    138           : DataflowIterator(mir_graph, is_iterative, 0, 0, false) {
    139         all_nodes_iterator_ =
    140             new (mir_graph->GetArena()) GrowableArray<BasicBlock*>::Iterator(mir_graph->GetBlockList());
    141       }
    142 
    143       void Reset() {
    144         all_nodes_iterator_->Reset();
    145       }
    146 
    147       BasicBlock* NextBody(bool had_change) ALWAYS_INLINE;
    148 
    149     private:
    150       GrowableArray<BasicBlock*>::Iterator* all_nodes_iterator_;
    151   };
    152 
    153 }  // namespace art
    154 
    155 #endif  // ART_COMPILER_DEX_DATAFLOW_ITERATOR_H_
    156