Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2014 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 | #include "nodes.h" |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 18 | #include "ssa_builder.h" |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 19 | #include "utils/growable_array.h" |
| 20 | |
| 21 | namespace art { |
| 22 | |
| 23 | void HGraph::AddBlock(HBasicBlock* block) { |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 24 | block->SetBlockId(blocks_.Size()); |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 25 | blocks_.Add(block); |
| 26 | } |
| 27 | |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 28 | void HGraph::FindBackEdges(ArenaBitVector* visited) { |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 29 | ArenaBitVector visiting(arena_, blocks_.Size(), false); |
Nicolas Geoffray | d4dd255 | 2014-02-28 10:23:58 +0000 | [diff] [blame] | 30 | VisitBlockForBackEdges(entry_block_, visited, &visiting); |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 31 | } |
| 32 | |
| 33 | void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const { |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 34 | for (size_t i = 0; i < blocks_.Size(); ++i) { |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 35 | if (!visited.IsBitSet(i)) { |
| 36 | HBasicBlock* block = blocks_.Get(i); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 37 | for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 38 | block->GetSuccessors().Get(j)->RemovePredecessor(block); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 39 | } |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 40 | for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 41 | block->RemovePhi(it.Current()->AsPhi()); |
| 42 | } |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 43 | for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 44 | block->RemoveInstruction(it.Current()); |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 45 | } |
| 46 | } |
| 47 | } |
| 48 | } |
| 49 | |
| 50 | void HGraph::VisitBlockForBackEdges(HBasicBlock* block, |
| 51 | ArenaBitVector* visited, |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 52 | ArenaBitVector* visiting) { |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 53 | int id = block->GetBlockId(); |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 54 | if (visited->IsBitSet(id)) return; |
| 55 | |
| 56 | visited->SetBit(id); |
| 57 | visiting->SetBit(id); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 58 | for (size_t i = 0; i < block->GetSuccessors().Size(); i++) { |
| 59 | HBasicBlock* successor = block->GetSuccessors().Get(i); |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 60 | if (visiting->IsBitSet(successor->GetBlockId())) { |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 61 | successor->AddBackEdge(block); |
| 62 | } else { |
| 63 | VisitBlockForBackEdges(successor, visited, visiting); |
| 64 | } |
| 65 | } |
| 66 | visiting->ClearBit(id); |
| 67 | } |
| 68 | |
| 69 | void HGraph::BuildDominatorTree() { |
| 70 | ArenaBitVector visited(arena_, blocks_.Size(), false); |
| 71 | |
| 72 | // (1) Find the back edges in the graph doing a DFS traversal. |
| 73 | FindBackEdges(&visited); |
| 74 | |
| 75 | // (2) Remove blocks not visited during the initial DFS. |
| 76 | // Step (3) requires dead blocks to be removed from the |
| 77 | // predecessors list of live blocks. |
| 78 | RemoveDeadBlocks(visited); |
| 79 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 80 | // (3) Simplify the CFG now, so that we don't need to recompute |
| 81 | // dominators and the reverse post order. |
| 82 | SimplifyCFG(); |
| 83 | |
| 84 | // (4) Compute the immediate dominator of each block. We visit |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 85 | // the successors of a block only when all its forward branches |
| 86 | // have been processed. |
| 87 | GrowableArray<size_t> visits(arena_, blocks_.Size()); |
| 88 | visits.SetSize(blocks_.Size()); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 89 | reverse_post_order_.Add(entry_block_); |
| 90 | for (size_t i = 0; i < entry_block_->GetSuccessors().Size(); i++) { |
| 91 | VisitBlockForDominatorTree(entry_block_->GetSuccessors().Get(i), entry_block_, &visits); |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 92 | } |
| 93 | } |
| 94 | |
| 95 | HBasicBlock* HGraph::FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const { |
| 96 | ArenaBitVector visited(arena_, blocks_.Size(), false); |
| 97 | // Walk the dominator tree of the first block and mark the visited blocks. |
| 98 | while (first != nullptr) { |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 99 | visited.SetBit(first->GetBlockId()); |
| 100 | first = first->GetDominator(); |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 101 | } |
| 102 | // Walk the dominator tree of the second block until a marked block is found. |
| 103 | while (second != nullptr) { |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 104 | if (visited.IsBitSet(second->GetBlockId())) { |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 105 | return second; |
| 106 | } |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 107 | second = second->GetDominator(); |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 108 | } |
| 109 | LOG(ERROR) << "Could not find common dominator"; |
| 110 | return nullptr; |
| 111 | } |
| 112 | |
| 113 | void HGraph::VisitBlockForDominatorTree(HBasicBlock* block, |
| 114 | HBasicBlock* predecessor, |
| 115 | GrowableArray<size_t>* visits) { |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 116 | if (block->GetDominator() == nullptr) { |
| 117 | block->SetDominator(predecessor); |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 118 | } else { |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 119 | block->SetDominator(FindCommonDominator(block->GetDominator(), predecessor)); |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 120 | } |
| 121 | |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 122 | visits->Increment(block->GetBlockId()); |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 123 | // Once all the forward edges have been visited, we know the immediate |
| 124 | // dominator of the block. We can then start visiting its successors. |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 125 | if (visits->Get(block->GetBlockId()) == |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 126 | block->GetPredecessors().Size() - block->NumberOfBackEdges()) { |
| 127 | reverse_post_order_.Add(block); |
| 128 | for (size_t i = 0; i < block->GetSuccessors().Size(); i++) { |
| 129 | VisitBlockForDominatorTree(block->GetSuccessors().Get(i), block, visits); |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 130 | } |
| 131 | } |
| 132 | } |
| 133 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 134 | void HGraph::TransformToSSA() { |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 135 | DCHECK(!reverse_post_order_.IsEmpty()); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 136 | SsaBuilder ssa_builder(this); |
| 137 | ssa_builder.BuildSsa(); |
| 138 | } |
| 139 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 140 | void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) { |
| 141 | // Insert a new node between `block` and `successor` to split the |
| 142 | // critical edge. |
| 143 | HBasicBlock* new_block = new (arena_) HBasicBlock(this); |
| 144 | AddBlock(new_block); |
| 145 | new_block->AddInstruction(new (arena_) HGoto()); |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 146 | block->ReplaceSuccessor(successor, new_block); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 147 | new_block->AddSuccessor(successor); |
| 148 | if (successor->IsLoopHeader()) { |
| 149 | // If we split at a back edge boundary, make the new block the back edge. |
| 150 | HLoopInformation* info = successor->GetLoopInformation(); |
| 151 | if (info->IsBackEdge(block)) { |
| 152 | info->RemoveBackEdge(block); |
| 153 | info->AddBackEdge(new_block); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 154 | } |
| 155 | } |
| 156 | } |
| 157 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 158 | void HGraph::SimplifyLoop(HBasicBlock* header) { |
| 159 | HLoopInformation* info = header->GetLoopInformation(); |
| 160 | |
| 161 | // If there are more than one back edge, make them branch to the same block that |
| 162 | // will become the only back edge. This simplifies finding natural loops in the |
| 163 | // graph. |
| 164 | if (info->NumberOfBackEdges() > 1) { |
| 165 | HBasicBlock* new_back_edge = new (arena_) HBasicBlock(this); |
| 166 | AddBlock(new_back_edge); |
| 167 | new_back_edge->AddInstruction(new (arena_) HGoto()); |
| 168 | for (size_t pred = 0, e = info->GetBackEdges().Size(); pred < e; ++pred) { |
| 169 | HBasicBlock* back_edge = info->GetBackEdges().Get(pred); |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 170 | back_edge->ReplaceSuccessor(header, new_back_edge); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 171 | } |
| 172 | info->ClearBackEdges(); |
| 173 | info->AddBackEdge(new_back_edge); |
| 174 | new_back_edge->AddSuccessor(header); |
| 175 | } |
| 176 | |
| 177 | // Make sure the loop has only one pre header. This simplifies SSA building by having |
| 178 | // to just look at the pre header to know which locals are initialized at entry of the |
| 179 | // loop. |
| 180 | size_t number_of_incomings = header->GetPredecessors().Size() - info->NumberOfBackEdges(); |
| 181 | if (number_of_incomings != 1) { |
| 182 | HBasicBlock* pre_header = new (arena_) HBasicBlock(this); |
| 183 | AddBlock(pre_header); |
| 184 | pre_header->AddInstruction(new (arena_) HGoto()); |
| 185 | |
| 186 | ArenaBitVector back_edges(arena_, GetBlocks().Size(), false); |
| 187 | HBasicBlock* back_edge = info->GetBackEdges().Get(0); |
| 188 | for (size_t pred = 0; pred < header->GetPredecessors().Size(); ++pred) { |
| 189 | HBasicBlock* predecessor = header->GetPredecessors().Get(pred); |
| 190 | if (predecessor != back_edge) { |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 191 | predecessor->ReplaceSuccessor(header, pre_header); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 192 | pred--; |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 193 | } |
| 194 | } |
| 195 | pre_header->AddSuccessor(header); |
| 196 | } |
| 197 | } |
| 198 | |
| 199 | void HGraph::SimplifyCFG() { |
| 200 | // Simplify the CFG for future analysis, and code generation: |
| 201 | // (1): Split critical edges. |
| 202 | // (2): Simplify loops by having only one back edge, and one preheader. |
| 203 | for (size_t i = 0; i < blocks_.Size(); ++i) { |
| 204 | HBasicBlock* block = blocks_.Get(i); |
| 205 | if (block->GetSuccessors().Size() > 1) { |
| 206 | for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { |
| 207 | HBasicBlock* successor = block->GetSuccessors().Get(j); |
| 208 | if (successor->GetPredecessors().Size() > 1) { |
| 209 | SplitCriticalEdge(block, successor); |
| 210 | --j; |
| 211 | } |
| 212 | } |
| 213 | } |
| 214 | if (block->IsLoopHeader()) { |
| 215 | SimplifyLoop(block); |
| 216 | } |
| 217 | } |
| 218 | } |
| 219 | |
| 220 | bool HGraph::FindNaturalLoops() const { |
| 221 | for (size_t i = 0; i < blocks_.Size(); ++i) { |
| 222 | HBasicBlock* block = blocks_.Get(i); |
| 223 | if (block->IsLoopHeader()) { |
| 224 | HLoopInformation* info = block->GetLoopInformation(); |
| 225 | if (!info->Populate()) { |
| 226 | // Abort if the loop is non natural. We currently bailout in such cases. |
| 227 | return false; |
| 228 | } |
| 229 | } |
| 230 | } |
| 231 | return true; |
| 232 | } |
| 233 | |
| 234 | void HLoopInformation::PopulateRecursive(HBasicBlock* block) { |
| 235 | if (blocks_.IsBitSet(block->GetBlockId())) { |
| 236 | return; |
| 237 | } |
| 238 | |
| 239 | blocks_.SetBit(block->GetBlockId()); |
| 240 | block->SetInLoop(this); |
| 241 | for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { |
| 242 | PopulateRecursive(block->GetPredecessors().Get(i)); |
| 243 | } |
| 244 | } |
| 245 | |
| 246 | bool HLoopInformation::Populate() { |
| 247 | DCHECK_EQ(GetBackEdges().Size(), 1u); |
| 248 | HBasicBlock* back_edge = GetBackEdges().Get(0); |
| 249 | DCHECK(back_edge->GetDominator() != nullptr); |
| 250 | if (!header_->Dominates(back_edge)) { |
| 251 | // This loop is not natural. Do not bother going further. |
| 252 | return false; |
| 253 | } |
| 254 | |
| 255 | // Populate this loop: starting with the back edge, recursively add predecessors |
| 256 | // that are not already part of that loop. Set the header as part of the loop |
| 257 | // to end the recursion. |
| 258 | // This is a recursive implementation of the algorithm described in |
| 259 | // "Advanced Compiler Design & Implementation" (Muchnick) p192. |
| 260 | blocks_.SetBit(header_->GetBlockId()); |
| 261 | PopulateRecursive(back_edge); |
| 262 | return true; |
| 263 | } |
| 264 | |
| 265 | HBasicBlock* HLoopInformation::GetPreHeader() const { |
| 266 | DCHECK_EQ(header_->GetPredecessors().Size(), 2u); |
| 267 | return header_->GetDominator(); |
| 268 | } |
| 269 | |
| 270 | bool HLoopInformation::Contains(const HBasicBlock& block) const { |
| 271 | return blocks_.IsBitSet(block.GetBlockId()); |
| 272 | } |
| 273 | |
| 274 | bool HLoopInformation::IsIn(const HLoopInformation& other) const { |
| 275 | return other.blocks_.IsBitSet(header_->GetBlockId()); |
| 276 | } |
| 277 | |
| 278 | bool HBasicBlock::Dominates(HBasicBlock* other) const { |
| 279 | // Walk up the dominator tree from `other`, to find out if `this` |
| 280 | // is an ancestor. |
| 281 | HBasicBlock* current = other; |
| 282 | while (current != nullptr) { |
| 283 | if (current == this) { |
| 284 | return true; |
| 285 | } |
| 286 | current = current->GetDominator(); |
| 287 | } |
| 288 | return false; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 289 | } |
| 290 | |
Nicolas Geoffray | 4e3d23a | 2014-05-22 18:32:45 +0100 | [diff] [blame] | 291 | void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { |
| 292 | DCHECK(cursor->AsPhi() == nullptr); |
| 293 | DCHECK(instruction->AsPhi() == nullptr); |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 294 | DCHECK_EQ(instruction->GetId(), -1); |
| 295 | DCHECK_NE(cursor->GetId(), -1); |
| 296 | DCHECK_EQ(cursor->GetBlock(), this); |
| 297 | DCHECK(!instruction->IsControlFlow()); |
Nicolas Geoffray | 4e3d23a | 2014-05-22 18:32:45 +0100 | [diff] [blame] | 298 | instruction->next_ = cursor; |
| 299 | instruction->previous_ = cursor->previous_; |
| 300 | cursor->previous_ = instruction; |
| 301 | if (GetFirstInstruction() == cursor) { |
| 302 | instructions_.first_instruction_ = instruction; |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 303 | } else { |
| 304 | instruction->previous_->next_ = instruction; |
Nicolas Geoffray | 4e3d23a | 2014-05-22 18:32:45 +0100 | [diff] [blame] | 305 | } |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 306 | instruction->SetBlock(this); |
| 307 | instruction->SetId(GetGraph()->GetNextInstructionId()); |
Nicolas Geoffray | 4e3d23a | 2014-05-22 18:32:45 +0100 | [diff] [blame] | 308 | } |
| 309 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 310 | static void Add(HInstructionList* instruction_list, |
| 311 | HBasicBlock* block, |
| 312 | HInstruction* instruction) { |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 313 | DCHECK(instruction->GetBlock() == nullptr); |
Nicolas Geoffray | 43c8642 | 2014-03-18 11:58:24 +0000 | [diff] [blame] | 314 | DCHECK_EQ(instruction->GetId(), -1); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 315 | instruction->SetBlock(block); |
| 316 | instruction->SetId(block->GetGraph()->GetNextInstructionId()); |
| 317 | instruction_list->AddInstruction(instruction); |
| 318 | } |
| 319 | |
| 320 | void HBasicBlock::AddInstruction(HInstruction* instruction) { |
| 321 | Add(&instructions_, this, instruction); |
| 322 | } |
| 323 | |
| 324 | void HBasicBlock::AddPhi(HPhi* phi) { |
| 325 | Add(&phis_, this, phi); |
| 326 | } |
| 327 | |
| 328 | static void Remove(HInstructionList* instruction_list, |
| 329 | HBasicBlock* block, |
| 330 | HInstruction* instruction) { |
| 331 | DCHECK_EQ(block, instruction->GetBlock()); |
| 332 | DCHECK(instruction->GetUses() == nullptr); |
| 333 | DCHECK(instruction->GetEnvUses() == nullptr); |
| 334 | instruction->SetBlock(nullptr); |
| 335 | instruction_list->RemoveInstruction(instruction); |
| 336 | |
| 337 | for (size_t i = 0; i < instruction->InputCount(); i++) { |
| 338 | instruction->InputAt(i)->RemoveUser(instruction, i); |
| 339 | } |
| 340 | } |
| 341 | |
| 342 | void HBasicBlock::RemoveInstruction(HInstruction* instruction) { |
| 343 | Remove(&instructions_, this, instruction); |
| 344 | } |
| 345 | |
| 346 | void HBasicBlock::RemovePhi(HPhi* phi) { |
| 347 | Remove(&phis_, this, phi); |
| 348 | } |
| 349 | |
| 350 | void HInstruction::RemoveUser(HInstruction* user, size_t input_index) { |
| 351 | HUseListNode<HInstruction>* previous = nullptr; |
| 352 | HUseListNode<HInstruction>* current = uses_; |
| 353 | while (current != nullptr) { |
| 354 | if (current->GetUser() == user && current->GetIndex() == input_index) { |
| 355 | if (previous == NULL) { |
| 356 | uses_ = current->GetTail(); |
| 357 | } else { |
| 358 | previous->SetTail(current->GetTail()); |
| 359 | } |
| 360 | } |
| 361 | previous = current; |
| 362 | current = current->GetTail(); |
| 363 | } |
| 364 | } |
| 365 | |
| 366 | void HInstructionList::AddInstruction(HInstruction* instruction) { |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 367 | if (first_instruction_ == nullptr) { |
| 368 | DCHECK(last_instruction_ == nullptr); |
| 369 | first_instruction_ = last_instruction_ = instruction; |
| 370 | } else { |
| 371 | last_instruction_->next_ = instruction; |
| 372 | instruction->previous_ = last_instruction_; |
| 373 | last_instruction_ = instruction; |
| 374 | } |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 375 | for (size_t i = 0; i < instruction->InputCount(); i++) { |
| 376 | instruction->InputAt(i)->AddUseAt(instruction, i); |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 377 | } |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 378 | } |
| 379 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 380 | void HInstructionList::RemoveInstruction(HInstruction* instruction) { |
| 381 | if (instruction->previous_ != nullptr) { |
| 382 | instruction->previous_->next_ = instruction->next_; |
| 383 | } |
| 384 | if (instruction->next_ != nullptr) { |
| 385 | instruction->next_->previous_ = instruction->previous_; |
| 386 | } |
| 387 | if (instruction == first_instruction_) { |
| 388 | first_instruction_ = instruction->next_; |
| 389 | } |
| 390 | if (instruction == last_instruction_) { |
| 391 | last_instruction_ = instruction->previous_; |
| 392 | } |
| 393 | } |
| 394 | |
| 395 | void HInstruction::ReplaceWith(HInstruction* other) { |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 396 | DCHECK(other != nullptr); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 397 | for (HUseIterator<HInstruction> it(GetUses()); !it.Done(); it.Advance()) { |
| 398 | HUseListNode<HInstruction>* current = it.Current(); |
| 399 | HInstruction* user = current->GetUser(); |
| 400 | size_t input_index = current->GetIndex(); |
| 401 | user->SetRawInputAt(input_index, other); |
| 402 | other->AddUseAt(user, input_index); |
| 403 | } |
| 404 | |
| 405 | for (HUseIterator<HEnvironment> it(GetEnvUses()); !it.Done(); it.Advance()) { |
| 406 | HUseListNode<HEnvironment>* current = it.Current(); |
| 407 | HEnvironment* user = current->GetUser(); |
| 408 | size_t input_index = current->GetIndex(); |
| 409 | user->SetRawEnvAt(input_index, other); |
| 410 | other->AddEnvUseAt(user, input_index); |
| 411 | } |
| 412 | |
| 413 | uses_ = nullptr; |
| 414 | env_uses_ = nullptr; |
| 415 | } |
| 416 | |
| 417 | void HPhi::AddInput(HInstruction* input) { |
| 418 | DCHECK(input->GetBlock() != nullptr); |
| 419 | inputs_.Add(input); |
| 420 | input->AddUseAt(this, inputs_.Size() - 1); |
| 421 | } |
| 422 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 423 | #define DEFINE_ACCEPT(name) \ |
| 424 | void H##name::Accept(HGraphVisitor* visitor) { \ |
| 425 | visitor->Visit##name(this); \ |
| 426 | } |
| 427 | |
| 428 | FOR_EACH_INSTRUCTION(DEFINE_ACCEPT) |
| 429 | |
| 430 | #undef DEFINE_ACCEPT |
| 431 | |
| 432 | void HGraphVisitor::VisitInsertionOrder() { |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 433 | const GrowableArray<HBasicBlock*>& blocks = graph_->GetBlocks(); |
| 434 | for (size_t i = 0 ; i < blocks.Size(); i++) { |
| 435 | VisitBasicBlock(blocks.Get(i)); |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 436 | } |
| 437 | } |
| 438 | |
| 439 | void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) { |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 440 | for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 441 | it.Current()->Accept(this); |
| 442 | } |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 443 | for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 444 | it.Current()->Accept(this); |
| 445 | } |
| 446 | } |
| 447 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame^] | 448 | |
| 449 | bool HCondition::NeedsMaterialization() const { |
| 450 | if (!HasOnlyOneUse()) { |
| 451 | return true; |
| 452 | } |
| 453 | HUseListNode<HInstruction>* uses = GetUses(); |
| 454 | HInstruction* user = uses->GetUser(); |
| 455 | if (!user->IsIf()) { |
| 456 | return true; |
| 457 | } |
| 458 | |
| 459 | // TODO: should we allow intervening instructions with no side-effect between this condition |
| 460 | // and the If instruction? |
| 461 | if (GetNext() != user) { |
| 462 | return true; |
| 463 | } |
| 464 | return false; |
| 465 | } |
| 466 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 467 | } // namespace art |