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_INL_H_ 18 #define ART_COMPILER_DEX_DATAFLOW_ITERATOR_INL_H_ 19 20 #include "dataflow_iterator.h" 21 22 namespace art { 23 24 // Single forward pass over the nodes. 25 inline BasicBlock* DataflowIterator::ForwardSingleNext() { 26 BasicBlock* res = NULL; 27 28 // Are we not yet at the end? 29 if (idx_ < end_idx_) { 30 // Get the next index. 31 BasicBlockId bb_id = block_id_list_->Get(idx_); 32 res = mir_graph_->GetBasicBlock(bb_id); 33 idx_++; 34 } 35 36 return res; 37 } 38 39 // Repeat full forward passes over all nodes until no change occurs during a complete pass. 40 inline BasicBlock* DataflowIterator::ForwardRepeatNext() { 41 BasicBlock* res = NULL; 42 43 // Are we at the end and have we changed something? 44 if ((idx_ >= end_idx_) && changed_ == true) { 45 // Reset the index. 46 idx_ = start_idx_; 47 repeats_++; 48 changed_ = false; 49 } 50 51 // Are we not yet at the end? 52 if (idx_ < end_idx_) { 53 // Get the BasicBlockId. 54 BasicBlockId bb_id = block_id_list_->Get(idx_); 55 res = mir_graph_->GetBasicBlock(bb_id); 56 idx_++; 57 } 58 59 return res; 60 } 61 62 // Single reverse pass over the nodes. 63 inline BasicBlock* DataflowIterator::ReverseSingleNext() { 64 BasicBlock* res = NULL; 65 66 // Are we not yet at the end? 67 if (idx_ >= 0) { 68 // Get the BasicBlockId. 69 BasicBlockId bb_id = block_id_list_->Get(idx_); 70 res = mir_graph_->GetBasicBlock(bb_id); 71 idx_--; 72 } 73 74 return res; 75 } 76 77 // Repeat full backwards passes over all nodes until no change occurs during a complete pass. 78 inline BasicBlock* DataflowIterator::ReverseRepeatNext() { 79 BasicBlock* res = NULL; 80 81 // Are we done and we changed something during the last iteration? 82 if ((idx_ < 0) && changed_) { 83 // Reset the index. 84 idx_ = start_idx_; 85 repeats_++; 86 changed_ = false; 87 } 88 89 // Are we not yet done? 90 if (idx_ >= 0) { 91 // Get the BasicBlockId. 92 BasicBlockId bb_id = block_id_list_->Get(idx_); 93 res = mir_graph_->GetBasicBlock(bb_id); 94 idx_--; 95 } 96 97 return res; 98 } 99 100 // AllNodes uses the existing GrowableArray iterator, and should be considered unordered. 101 inline BasicBlock* AllNodesIterator::Next(bool had_change) { 102 BasicBlock* res = NULL; 103 104 // Suppose we want to keep looking. 105 bool keep_looking = true; 106 107 // Find the next BasicBlock. 108 while (keep_looking == true) { 109 // Get next BasicBlock. 110 res = all_nodes_iterator_.Next(); 111 112 // Are we done or is the BasicBlock not hidden? 113 if ((res == NULL) || (res->hidden == false)) { 114 keep_looking = false; 115 } 116 } 117 118 // Update changed: if had_changed is true, we remember it for the whole iteration. 119 changed_ |= had_change; 120 121 return res; 122 } 123 124 inline BasicBlock* LoopRepeatingTopologicalSortIterator::Next(bool had_change) { 125 if (idx_ != 0) { 126 // Mark last processed block visited. 127 BasicBlock* bb = mir_graph_->GetBasicBlock(block_id_list_->Get(idx_ - 1)); 128 bb->visited = true; 129 if (had_change) { 130 // If we had a change we need to revisit the children. 131 ChildBlockIterator iter(bb, mir_graph_); 132 for (BasicBlock* child_bb = iter.Next(); child_bb != nullptr; child_bb = iter.Next()) { 133 child_bb->visited = false; 134 } 135 } 136 } 137 138 while (true) { 139 // Pop loops we have left and check if we need to recalculate one of them. 140 // NOTE: We need to do this even if idx_ == end_idx_. 141 while (loop_head_stack_->Size() != 0u && 142 loop_ends_->Get(loop_head_stack_->Peek().first) == idx_) { 143 auto top = loop_head_stack_->Peek(); 144 uint16_t loop_head_idx = top.first; 145 bool recalculated = top.second; 146 loop_head_stack_->Pop(); 147 BasicBlock* loop_head = mir_graph_->GetBasicBlock(block_id_list_->Get(loop_head_idx)); 148 DCHECK(loop_head != nullptr); 149 if (!recalculated || !loop_head->visited) { 150 loop_head_stack_->Insert(std::make_pair(loop_head_idx, true)); // Recalculating this loop. 151 idx_ = loop_head_idx + 1; 152 return loop_head; 153 } 154 } 155 156 if (idx_ == end_idx_) { 157 return nullptr; 158 } 159 160 // Get next block and return it if unvisited. 161 BasicBlockId idx = idx_; 162 idx_ += 1; 163 BasicBlock* bb = mir_graph_->GetBasicBlock(block_id_list_->Get(idx)); 164 DCHECK(bb != nullptr); 165 if (!bb->visited) { 166 if (loop_ends_->Get(idx) != 0u) { 167 loop_head_stack_->Insert(std::make_pair(idx, false)); // Not recalculating. 168 } 169 return bb; 170 } 171 } 172 } 173 174 } // namespace art 175 176 #endif // ART_COMPILER_DEX_DATAFLOW_ITERATOR_INL_H_ 177
