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 = nullptr; 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_)[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 = nullptr; 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_)[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 = nullptr; 65 66 // Are we not yet at the end? 67 if (idx_ >= 0) { 68 // Get the BasicBlockId. 69 BasicBlockId bb_id = (*block_id_list_)[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 = nullptr; 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_)[idx_]; 93 res = mir_graph_->GetBasicBlock(bb_id); 94 idx_--; 95 } 96 97 return res; 98 } 99 100 // AllNodes uses the existing block list, and should be considered unordered. 101 inline BasicBlock* AllNodesIterator::Next(bool had_change) { 102 // Update changed: if had_changed is true, we remember it for the whole iteration. 103 changed_ |= had_change; 104 105 BasicBlock* res = nullptr; 106 while (idx_ != end_idx_) { 107 BasicBlock* bb = mir_graph_->GetBlockList()[idx_++]; 108 DCHECK(bb != nullptr); 109 if (!bb->hidden) { 110 res = bb; 111 break; 112 } 113 } 114 115 return res; 116 } 117 118 inline BasicBlock* TopologicalSortIterator::Next(bool had_change) { 119 // Update changed: if had_changed is true, we remember it for the whole iteration. 120 changed_ |= had_change; 121 122 while (loop_head_stack_->size() != 0u && 123 (*loop_ends_)[loop_head_stack_->back().first] == idx_) { 124 loop_head_stack_->pop_back(); 125 } 126 127 if (idx_ == end_idx_) { 128 return nullptr; 129 } 130 131 // Get next block and return it. 132 BasicBlockId idx = idx_; 133 idx_ += 1; 134 BasicBlock* bb = mir_graph_->GetBasicBlock((*block_id_list_)[idx]); 135 DCHECK(bb != nullptr); 136 if ((*loop_ends_)[idx] != 0u) { 137 loop_head_stack_->push_back(std::make_pair(idx, false)); // Not recalculating. 138 } 139 return bb; 140 } 141 142 inline BasicBlock* LoopRepeatingTopologicalSortIterator::Next(bool had_change) { 143 if (idx_ != 0) { 144 // Mark last processed block visited. 145 BasicBlock* bb = mir_graph_->GetBasicBlock((*block_id_list_)[idx_ - 1]); 146 bb->visited = true; 147 if (had_change) { 148 // If we had a change we need to revisit the children. 149 ChildBlockIterator iter(bb, mir_graph_); 150 for (BasicBlock* child_bb = iter.Next(); child_bb != nullptr; child_bb = iter.Next()) { 151 child_bb->visited = false; 152 } 153 } 154 } 155 156 while (true) { 157 // Pop loops we have left and check if we need to recalculate one of them. 158 // NOTE: We need to do this even if idx_ == end_idx_. 159 while (loop_head_stack_->size() != 0u && 160 (*loop_ends_)[loop_head_stack_->back().first] == idx_) { 161 auto top = loop_head_stack_->back(); 162 uint16_t loop_head_idx = top.first; 163 bool recalculated = top.second; 164 loop_head_stack_->pop_back(); 165 BasicBlock* loop_head = mir_graph_->GetBasicBlock((*block_id_list_)[loop_head_idx]); 166 DCHECK(loop_head != nullptr); 167 if (!recalculated || !loop_head->visited) { 168 // Recalculating this loop. 169 loop_head_stack_->push_back(std::make_pair(loop_head_idx, true)); 170 idx_ = loop_head_idx + 1; 171 return loop_head; 172 } 173 } 174 175 if (idx_ == end_idx_) { 176 return nullptr; 177 } 178 179 // Get next block and return it if unvisited. 180 BasicBlockId idx = idx_; 181 idx_ += 1; 182 BasicBlock* bb = mir_graph_->GetBasicBlock((*block_id_list_)[idx]); 183 DCHECK(bb != nullptr); 184 if ((*loop_ends_)[idx] != 0u) { 185 // If bb->visited is false, the loop needs to be processed from scratch. 186 // Otherwise we mark it as recalculating; for a natural loop we will not 187 // need to recalculate any block in the loop anyway, and for unnatural 188 // loops we will recalculate the loop head only if one of its predecessors 189 // actually changes. 190 bool recalculating = bb->visited; 191 loop_head_stack_->push_back(std::make_pair(idx, recalculating)); 192 } 193 if (!bb->visited) { 194 return bb; 195 } 196 } 197 } 198 199 } // namespace art 200 201 #endif // ART_COMPILER_DEX_DATAFLOW_ITERATOR_INL_H_ 202