nodes.cc revision a83a54d7f2322060f08480f8aabac5eb07268912
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" 18 19#include "code_generator.h" 20#include "ssa_builder.h" 21#include "base/bit_vector-inl.h" 22#include "base/bit_utils.h" 23#include "base/stl_util.h" 24#include "intrinsics.h" 25#include "mirror/class-inl.h" 26#include "scoped_thread_state_change.h" 27 28namespace art { 29 30void HGraph::AddBlock(HBasicBlock* block) { 31 block->SetBlockId(blocks_.size()); 32 blocks_.push_back(block); 33} 34 35void HGraph::FindBackEdges(ArenaBitVector* visited) { 36 // "visited" must be empty on entry, it's an output argument for all visited (i.e. live) blocks. 37 DCHECK_EQ(visited->GetHighestBitSet(), -1); 38 39 // Nodes that we're currently visiting, indexed by block id. 40 ArenaBitVector visiting(arena_, blocks_.size(), false); 41 // Number of successors visited from a given node, indexed by block id. 42 ArenaVector<size_t> successors_visited(blocks_.size(), 0u, arena_->Adapter()); 43 // Stack of nodes that we're currently visiting (same as marked in "visiting" above). 44 ArenaVector<HBasicBlock*> worklist(arena_->Adapter()); 45 constexpr size_t kDefaultWorklistSize = 8; 46 worklist.reserve(kDefaultWorklistSize); 47 visited->SetBit(entry_block_->GetBlockId()); 48 visiting.SetBit(entry_block_->GetBlockId()); 49 worklist.push_back(entry_block_); 50 51 while (!worklist.empty()) { 52 HBasicBlock* current = worklist.back(); 53 uint32_t current_id = current->GetBlockId(); 54 if (successors_visited[current_id] == current->GetSuccessors().size()) { 55 visiting.ClearBit(current_id); 56 worklist.pop_back(); 57 } else { 58 DCHECK_LT(successors_visited[current_id], current->GetSuccessors().size()); 59 HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++]; 60 uint32_t successor_id = successor->GetBlockId(); 61 if (visiting.IsBitSet(successor_id)) { 62 DCHECK(ContainsElement(worklist, successor)); 63 successor->AddBackEdge(current); 64 } else if (!visited->IsBitSet(successor_id)) { 65 visited->SetBit(successor_id); 66 visiting.SetBit(successor_id); 67 worklist.push_back(successor); 68 } 69 } 70 } 71} 72 73static void RemoveAsUser(HInstruction* instruction) { 74 for (size_t i = 0; i < instruction->InputCount(); i++) { 75 instruction->RemoveAsUserOfInput(i); 76 } 77 78 for (HEnvironment* environment = instruction->GetEnvironment(); 79 environment != nullptr; 80 environment = environment->GetParent()) { 81 for (size_t i = 0, e = environment->Size(); i < e; ++i) { 82 if (environment->GetInstructionAt(i) != nullptr) { 83 environment->RemoveAsUserOfInput(i); 84 } 85 } 86 } 87} 88 89void HGraph::RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const { 90 for (size_t i = 0; i < blocks_.size(); ++i) { 91 if (!visited.IsBitSet(i)) { 92 HBasicBlock* block = GetBlock(i); 93 DCHECK(block->GetPhis().IsEmpty()) << "Phis are not inserted at this stage"; 94 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 95 RemoveAsUser(it.Current()); 96 } 97 } 98 } 99} 100 101void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) { 102 for (size_t i = 0; i < blocks_.size(); ++i) { 103 if (!visited.IsBitSet(i)) { 104 HBasicBlock* block = GetBlock(i); 105 // We only need to update the successor, which might be live. 106 for (HBasicBlock* successor : block->GetSuccessors()) { 107 successor->RemovePredecessor(block); 108 } 109 // Remove the block from the list of blocks, so that further analyses 110 // never see it. 111 blocks_[i] = nullptr; 112 } 113 } 114} 115 116void HGraph::BuildDominatorTree() { 117 // (1) Simplify the CFG so that catch blocks have only exceptional incoming 118 // edges. This invariant simplifies building SSA form because Phis cannot 119 // collect both normal- and exceptional-flow values at the same time. 120 SimplifyCatchBlocks(); 121 122 ArenaBitVector visited(arena_, blocks_.size(), false); 123 124 // (2) Find the back edges in the graph doing a DFS traversal. 125 FindBackEdges(&visited); 126 127 // (3) Remove instructions and phis from blocks not visited during 128 // the initial DFS as users from other instructions, so that 129 // users can be safely removed before uses later. 130 RemoveInstructionsAsUsersFromDeadBlocks(visited); 131 132 // (4) Remove blocks not visited during the initial DFS. 133 // Step (4) requires dead blocks to be removed from the 134 // predecessors list of live blocks. 135 RemoveDeadBlocks(visited); 136 137 // (5) Simplify the CFG now, so that we don't need to recompute 138 // dominators and the reverse post order. 139 SimplifyCFG(); 140 141 // (6) Compute the dominance information and the reverse post order. 142 ComputeDominanceInformation(); 143} 144 145void HGraph::ClearDominanceInformation() { 146 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { 147 it.Current()->ClearDominanceInformation(); 148 } 149 reverse_post_order_.clear(); 150} 151 152void HBasicBlock::ClearDominanceInformation() { 153 dominated_blocks_.clear(); 154 dominator_ = nullptr; 155} 156 157void HGraph::ComputeDominanceInformation() { 158 DCHECK(reverse_post_order_.empty()); 159 reverse_post_order_.reserve(blocks_.size()); 160 reverse_post_order_.push_back(entry_block_); 161 162 // Number of visits of a given node, indexed by block id. 163 ArenaVector<size_t> visits(blocks_.size(), 0u, arena_->Adapter()); 164 // Number of successors visited from a given node, indexed by block id. 165 ArenaVector<size_t> successors_visited(blocks_.size(), 0u, arena_->Adapter()); 166 // Nodes for which we need to visit successors. 167 ArenaVector<HBasicBlock*> worklist(arena_->Adapter()); 168 constexpr size_t kDefaultWorklistSize = 8; 169 worklist.reserve(kDefaultWorklistSize); 170 worklist.push_back(entry_block_); 171 172 while (!worklist.empty()) { 173 HBasicBlock* current = worklist.back(); 174 uint32_t current_id = current->GetBlockId(); 175 if (successors_visited[current_id] == current->GetSuccessors().size()) { 176 worklist.pop_back(); 177 } else { 178 DCHECK_LT(successors_visited[current_id], current->GetSuccessors().size()); 179 HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++]; 180 181 if (successor->GetDominator() == nullptr) { 182 successor->SetDominator(current); 183 } else { 184 successor->SetDominator(FindCommonDominator(successor->GetDominator(), current)); 185 } 186 187 // Once all the forward edges have been visited, we know the immediate 188 // dominator of the block. We can then start visiting its successors. 189 DCHECK_LT(successor->GetBlockId(), visits.size()); 190 if (++visits[successor->GetBlockId()] == 191 successor->GetPredecessors().size() - successor->NumberOfBackEdges()) { 192 successor->GetDominator()->AddDominatedBlock(successor); 193 reverse_post_order_.push_back(successor); 194 worklist.push_back(successor); 195 } 196 } 197 } 198} 199 200HBasicBlock* HGraph::FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const { 201 ArenaBitVector visited(arena_, blocks_.size(), false); 202 // Walk the dominator tree of the first block and mark the visited blocks. 203 while (first != nullptr) { 204 visited.SetBit(first->GetBlockId()); 205 first = first->GetDominator(); 206 } 207 // Walk the dominator tree of the second block until a marked block is found. 208 while (second != nullptr) { 209 if (visited.IsBitSet(second->GetBlockId())) { 210 return second; 211 } 212 second = second->GetDominator(); 213 } 214 LOG(ERROR) << "Could not find common dominator"; 215 return nullptr; 216} 217 218void HGraph::TransformToSsa() { 219 DCHECK(!reverse_post_order_.empty()); 220 SsaBuilder ssa_builder(this); 221 ssa_builder.BuildSsa(); 222} 223 224HBasicBlock* HGraph::SplitEdge(HBasicBlock* block, HBasicBlock* successor) { 225 HBasicBlock* new_block = new (arena_) HBasicBlock(this, successor->GetDexPc()); 226 AddBlock(new_block); 227 // Use `InsertBetween` to ensure the predecessor index and successor index of 228 // `block` and `successor` are preserved. 229 new_block->InsertBetween(block, successor); 230 return new_block; 231} 232 233void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) { 234 // Insert a new node between `block` and `successor` to split the 235 // critical edge. 236 HBasicBlock* new_block = SplitEdge(block, successor); 237 new_block->AddInstruction(new (arena_) HGoto(successor->GetDexPc())); 238 if (successor->IsLoopHeader()) { 239 // If we split at a back edge boundary, make the new block the back edge. 240 HLoopInformation* info = successor->GetLoopInformation(); 241 if (info->IsBackEdge(*block)) { 242 info->RemoveBackEdge(block); 243 info->AddBackEdge(new_block); 244 } 245 } 246} 247 248void HGraph::SimplifyLoop(HBasicBlock* header) { 249 HLoopInformation* info = header->GetLoopInformation(); 250 251 // Make sure the loop has only one pre header. This simplifies SSA building by having 252 // to just look at the pre header to know which locals are initialized at entry of the 253 // loop. 254 size_t number_of_incomings = header->GetPredecessors().size() - info->NumberOfBackEdges(); 255 if (number_of_incomings != 1) { 256 HBasicBlock* pre_header = new (arena_) HBasicBlock(this, header->GetDexPc()); 257 AddBlock(pre_header); 258 pre_header->AddInstruction(new (arena_) HGoto(header->GetDexPc())); 259 260 for (size_t pred = 0; pred < header->GetPredecessors().size(); ++pred) { 261 HBasicBlock* predecessor = header->GetPredecessor(pred); 262 if (!info->IsBackEdge(*predecessor)) { 263 predecessor->ReplaceSuccessor(header, pre_header); 264 pred--; 265 } 266 } 267 pre_header->AddSuccessor(header); 268 } 269 270 // Make sure the first predecessor of a loop header is the incoming block. 271 if (info->IsBackEdge(*header->GetPredecessor(0))) { 272 HBasicBlock* to_swap = header->GetPredecessor(0); 273 for (size_t pred = 1, e = header->GetPredecessors().size(); pred < e; ++pred) { 274 HBasicBlock* predecessor = header->GetPredecessor(pred); 275 if (!info->IsBackEdge(*predecessor)) { 276 header->predecessors_[pred] = to_swap; 277 header->predecessors_[0] = predecessor; 278 break; 279 } 280 } 281 } 282 283 // Place the suspend check at the beginning of the header, so that live registers 284 // will be known when allocating registers. Note that code generation can still 285 // generate the suspend check at the back edge, but needs to be careful with 286 // loop phi spill slots (which are not written to at back edge). 287 HInstruction* first_instruction = header->GetFirstInstruction(); 288 if (!first_instruction->IsSuspendCheck()) { 289 HSuspendCheck* check = new (arena_) HSuspendCheck(header->GetDexPc()); 290 header->InsertInstructionBefore(check, first_instruction); 291 first_instruction = check; 292 } 293 info->SetSuspendCheck(first_instruction->AsSuspendCheck()); 294} 295 296static bool CheckIfPredecessorAtIsExceptional(const HBasicBlock& block, size_t pred_idx) { 297 HBasicBlock* predecessor = block.GetPredecessor(pred_idx); 298 if (!predecessor->EndsWithTryBoundary()) { 299 // Only edges from HTryBoundary can be exceptional. 300 return false; 301 } 302 HTryBoundary* try_boundary = predecessor->GetLastInstruction()->AsTryBoundary(); 303 if (try_boundary->GetNormalFlowSuccessor() == &block) { 304 // This block is the normal-flow successor of `try_boundary`, but it could 305 // also be one of its exception handlers if catch blocks have not been 306 // simplified yet. Predecessors are unordered, so we will consider the first 307 // occurrence to be the normal edge and a possible second occurrence to be 308 // the exceptional edge. 309 return !block.IsFirstIndexOfPredecessor(predecessor, pred_idx); 310 } else { 311 // This is not the normal-flow successor of `try_boundary`, hence it must be 312 // one of its exception handlers. 313 DCHECK(try_boundary->HasExceptionHandler(block)); 314 return true; 315 } 316} 317 318void HGraph::SimplifyCatchBlocks() { 319 // NOTE: We're appending new blocks inside the loop, so we need to use index because iterators 320 // can be invalidated. We remember the initial size to avoid iterating over the new blocks. 321 for (size_t block_id = 0u, end = blocks_.size(); block_id != end; ++block_id) { 322 HBasicBlock* catch_block = blocks_[block_id]; 323 if (!catch_block->IsCatchBlock()) { 324 continue; 325 } 326 327 bool exceptional_predecessors_only = true; 328 for (size_t j = 0; j < catch_block->GetPredecessors().size(); ++j) { 329 if (!CheckIfPredecessorAtIsExceptional(*catch_block, j)) { 330 exceptional_predecessors_only = false; 331 break; 332 } 333 } 334 335 if (!exceptional_predecessors_only) { 336 // Catch block has normal-flow predecessors and needs to be simplified. 337 // Splitting the block before its first instruction moves all its 338 // instructions into `normal_block` and links the two blocks with a Goto. 339 // Afterwards, incoming normal-flow edges are re-linked to `normal_block`, 340 // leaving `catch_block` with the exceptional edges only. 341 // Note that catch blocks with normal-flow predecessors cannot begin with 342 // a MOVE_EXCEPTION instruction, as guaranteed by the verifier. 343 DCHECK(!catch_block->GetFirstInstruction()->IsLoadException()); 344 HBasicBlock* normal_block = catch_block->SplitBefore(catch_block->GetFirstInstruction()); 345 for (size_t j = 0; j < catch_block->GetPredecessors().size(); ++j) { 346 if (!CheckIfPredecessorAtIsExceptional(*catch_block, j)) { 347 catch_block->GetPredecessor(j)->ReplaceSuccessor(catch_block, normal_block); 348 --j; 349 } 350 } 351 } 352 } 353} 354 355void HGraph::ComputeTryBlockInformation() { 356 // Iterate in reverse post order to propagate try membership information from 357 // predecessors to their successors. 358 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { 359 HBasicBlock* block = it.Current(); 360 if (block->IsEntryBlock() || block->IsCatchBlock()) { 361 // Catch blocks after simplification have only exceptional predecessors 362 // and hence are never in tries. 363 continue; 364 } 365 366 // Infer try membership from the first predecessor. Having simplified loops, 367 // the first predecessor can never be a back edge and therefore it must have 368 // been visited already and had its try membership set. 369 HBasicBlock* first_predecessor = block->GetPredecessor(0); 370 DCHECK(!block->IsLoopHeader() || !block->GetLoopInformation()->IsBackEdge(*first_predecessor)); 371 const HTryBoundary* try_entry = first_predecessor->ComputeTryEntryOfSuccessors(); 372 if (try_entry != nullptr) { 373 block->SetTryCatchInformation(new (arena_) TryCatchInformation(*try_entry)); 374 } 375 } 376} 377 378void HGraph::SimplifyCFG() { 379 // Simplify the CFG for future analysis, and code generation: 380 // (1): Split critical edges. 381 // (2): Simplify loops by having only one back edge, and one preheader. 382 // NOTE: We're appending new blocks inside the loop, so we need to use index because iterators 383 // can be invalidated. We remember the initial size to avoid iterating over the new blocks. 384 for (size_t block_id = 0u, end = blocks_.size(); block_id != end; ++block_id) { 385 HBasicBlock* block = blocks_[block_id]; 386 if (block == nullptr) continue; 387 if (block->NumberOfNormalSuccessors() > 1) { 388 for (size_t j = 0; j < block->GetSuccessors().size(); ++j) { 389 HBasicBlock* successor = block->GetSuccessor(j); 390 DCHECK(!successor->IsCatchBlock()); 391 if (successor->GetPredecessors().size() > 1) { 392 SplitCriticalEdge(block, successor); 393 --j; 394 } 395 } 396 } 397 if (block->IsLoopHeader()) { 398 SimplifyLoop(block); 399 } 400 } 401} 402 403bool HGraph::AnalyzeNaturalLoops() const { 404 // Order does not matter. 405 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { 406 HBasicBlock* block = it.Current(); 407 if (block->IsLoopHeader()) { 408 if (block->IsCatchBlock()) { 409 // TODO: Dealing with exceptional back edges could be tricky because 410 // they only approximate the real control flow. Bail out for now. 411 return false; 412 } 413 HLoopInformation* info = block->GetLoopInformation(); 414 if (!info->Populate()) { 415 // Abort if the loop is non natural. We currently bailout in such cases. 416 return false; 417 } 418 } 419 } 420 return true; 421} 422 423void HGraph::InsertConstant(HConstant* constant) { 424 // New constants are inserted before the final control-flow instruction 425 // of the graph, or at its end if called from the graph builder. 426 if (entry_block_->EndsWithControlFlowInstruction()) { 427 entry_block_->InsertInstructionBefore(constant, entry_block_->GetLastInstruction()); 428 } else { 429 entry_block_->AddInstruction(constant); 430 } 431} 432 433HNullConstant* HGraph::GetNullConstant(uint32_t dex_pc) { 434 // For simplicity, don't bother reviving the cached null constant if it is 435 // not null and not in a block. Otherwise, we need to clear the instruction 436 // id and/or any invariants the graph is assuming when adding new instructions. 437 if ((cached_null_constant_ == nullptr) || (cached_null_constant_->GetBlock() == nullptr)) { 438 cached_null_constant_ = new (arena_) HNullConstant(dex_pc); 439 InsertConstant(cached_null_constant_); 440 } 441 return cached_null_constant_; 442} 443 444HCurrentMethod* HGraph::GetCurrentMethod() { 445 // For simplicity, don't bother reviving the cached current method if it is 446 // not null and not in a block. Otherwise, we need to clear the instruction 447 // id and/or any invariants the graph is assuming when adding new instructions. 448 if ((cached_current_method_ == nullptr) || (cached_current_method_->GetBlock() == nullptr)) { 449 cached_current_method_ = new (arena_) HCurrentMethod( 450 Is64BitInstructionSet(instruction_set_) ? Primitive::kPrimLong : Primitive::kPrimInt, 451 entry_block_->GetDexPc()); 452 if (entry_block_->GetFirstInstruction() == nullptr) { 453 entry_block_->AddInstruction(cached_current_method_); 454 } else { 455 entry_block_->InsertInstructionBefore( 456 cached_current_method_, entry_block_->GetFirstInstruction()); 457 } 458 } 459 return cached_current_method_; 460} 461 462HConstant* HGraph::GetConstant(Primitive::Type type, int64_t value, uint32_t dex_pc) { 463 switch (type) { 464 case Primitive::Type::kPrimBoolean: 465 DCHECK(IsUint<1>(value)); 466 FALLTHROUGH_INTENDED; 467 case Primitive::Type::kPrimByte: 468 case Primitive::Type::kPrimChar: 469 case Primitive::Type::kPrimShort: 470 case Primitive::Type::kPrimInt: 471 DCHECK(IsInt(Primitive::ComponentSize(type) * kBitsPerByte, value)); 472 return GetIntConstant(static_cast<int32_t>(value), dex_pc); 473 474 case Primitive::Type::kPrimLong: 475 return GetLongConstant(value, dex_pc); 476 477 default: 478 LOG(FATAL) << "Unsupported constant type"; 479 UNREACHABLE(); 480 } 481} 482 483void HGraph::CacheFloatConstant(HFloatConstant* constant) { 484 int32_t value = bit_cast<int32_t, float>(constant->GetValue()); 485 DCHECK(cached_float_constants_.find(value) == cached_float_constants_.end()); 486 cached_float_constants_.Overwrite(value, constant); 487} 488 489void HGraph::CacheDoubleConstant(HDoubleConstant* constant) { 490 int64_t value = bit_cast<int64_t, double>(constant->GetValue()); 491 DCHECK(cached_double_constants_.find(value) == cached_double_constants_.end()); 492 cached_double_constants_.Overwrite(value, constant); 493} 494 495void HLoopInformation::Add(HBasicBlock* block) { 496 blocks_.SetBit(block->GetBlockId()); 497} 498 499void HLoopInformation::Remove(HBasicBlock* block) { 500 blocks_.ClearBit(block->GetBlockId()); 501} 502 503void HLoopInformation::PopulateRecursive(HBasicBlock* block) { 504 if (blocks_.IsBitSet(block->GetBlockId())) { 505 return; 506 } 507 508 blocks_.SetBit(block->GetBlockId()); 509 block->SetInLoop(this); 510 for (HBasicBlock* predecessor : block->GetPredecessors()) { 511 PopulateRecursive(predecessor); 512 } 513} 514 515bool HLoopInformation::Populate() { 516 DCHECK_EQ(blocks_.NumSetBits(), 0u) << "Loop information has already been populated"; 517 for (HBasicBlock* back_edge : GetBackEdges()) { 518 DCHECK(back_edge->GetDominator() != nullptr); 519 if (!header_->Dominates(back_edge)) { 520 // This loop is not natural. Do not bother going further. 521 return false; 522 } 523 524 // Populate this loop: starting with the back edge, recursively add predecessors 525 // that are not already part of that loop. Set the header as part of the loop 526 // to end the recursion. 527 // This is a recursive implementation of the algorithm described in 528 // "Advanced Compiler Design & Implementation" (Muchnick) p192. 529 blocks_.SetBit(header_->GetBlockId()); 530 PopulateRecursive(back_edge); 531 } 532 return true; 533} 534 535void HLoopInformation::Update() { 536 HGraph* graph = header_->GetGraph(); 537 for (uint32_t id : blocks_.Indexes()) { 538 HBasicBlock* block = graph->GetBlock(id); 539 // Reset loop information of non-header blocks inside the loop, except 540 // members of inner nested loops because those should already have been 541 // updated by their own LoopInformation. 542 if (block->GetLoopInformation() == this && block != header_) { 543 block->SetLoopInformation(nullptr); 544 } 545 } 546 blocks_.ClearAllBits(); 547 548 if (back_edges_.empty()) { 549 // The loop has been dismantled, delete its suspend check and remove info 550 // from the header. 551 DCHECK(HasSuspendCheck()); 552 header_->RemoveInstruction(suspend_check_); 553 header_->SetLoopInformation(nullptr); 554 header_ = nullptr; 555 suspend_check_ = nullptr; 556 } else { 557 if (kIsDebugBuild) { 558 for (HBasicBlock* back_edge : back_edges_) { 559 DCHECK(header_->Dominates(back_edge)); 560 } 561 } 562 // This loop still has reachable back edges. Repopulate the list of blocks. 563 bool populate_successful = Populate(); 564 DCHECK(populate_successful); 565 } 566} 567 568HBasicBlock* HLoopInformation::GetPreHeader() const { 569 return header_->GetDominator(); 570} 571 572bool HLoopInformation::Contains(const HBasicBlock& block) const { 573 return blocks_.IsBitSet(block.GetBlockId()); 574} 575 576bool HLoopInformation::IsIn(const HLoopInformation& other) const { 577 return other.blocks_.IsBitSet(header_->GetBlockId()); 578} 579 580size_t HLoopInformation::GetLifetimeEnd() const { 581 size_t last_position = 0; 582 for (HBasicBlock* back_edge : GetBackEdges()) { 583 last_position = std::max(back_edge->GetLifetimeEnd(), last_position); 584 } 585 return last_position; 586} 587 588bool HBasicBlock::Dominates(HBasicBlock* other) const { 589 // Walk up the dominator tree from `other`, to find out if `this` 590 // is an ancestor. 591 HBasicBlock* current = other; 592 while (current != nullptr) { 593 if (current == this) { 594 return true; 595 } 596 current = current->GetDominator(); 597 } 598 return false; 599} 600 601static void UpdateInputsUsers(HInstruction* instruction) { 602 for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) { 603 instruction->InputAt(i)->AddUseAt(instruction, i); 604 } 605 // Environment should be created later. 606 DCHECK(!instruction->HasEnvironment()); 607} 608 609void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial, 610 HInstruction* replacement) { 611 DCHECK(initial->GetBlock() == this); 612 InsertInstructionBefore(replacement, initial); 613 initial->ReplaceWith(replacement); 614 RemoveInstruction(initial); 615} 616 617static void Add(HInstructionList* instruction_list, 618 HBasicBlock* block, 619 HInstruction* instruction) { 620 DCHECK(instruction->GetBlock() == nullptr); 621 DCHECK_EQ(instruction->GetId(), -1); 622 instruction->SetBlock(block); 623 instruction->SetId(block->GetGraph()->GetNextInstructionId()); 624 UpdateInputsUsers(instruction); 625 instruction_list->AddInstruction(instruction); 626} 627 628void HBasicBlock::AddInstruction(HInstruction* instruction) { 629 Add(&instructions_, this, instruction); 630} 631 632void HBasicBlock::AddPhi(HPhi* phi) { 633 Add(&phis_, this, phi); 634} 635 636void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { 637 DCHECK(!cursor->IsPhi()); 638 DCHECK(!instruction->IsPhi()); 639 DCHECK_EQ(instruction->GetId(), -1); 640 DCHECK_NE(cursor->GetId(), -1); 641 DCHECK_EQ(cursor->GetBlock(), this); 642 DCHECK(!instruction->IsControlFlow()); 643 instruction->SetBlock(this); 644 instruction->SetId(GetGraph()->GetNextInstructionId()); 645 UpdateInputsUsers(instruction); 646 instructions_.InsertInstructionBefore(instruction, cursor); 647} 648 649void HBasicBlock::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) { 650 DCHECK(!cursor->IsPhi()); 651 DCHECK(!instruction->IsPhi()); 652 DCHECK_EQ(instruction->GetId(), -1); 653 DCHECK_NE(cursor->GetId(), -1); 654 DCHECK_EQ(cursor->GetBlock(), this); 655 DCHECK(!instruction->IsControlFlow()); 656 DCHECK(!cursor->IsControlFlow()); 657 instruction->SetBlock(this); 658 instruction->SetId(GetGraph()->GetNextInstructionId()); 659 UpdateInputsUsers(instruction); 660 instructions_.InsertInstructionAfter(instruction, cursor); 661} 662 663void HBasicBlock::InsertPhiAfter(HPhi* phi, HPhi* cursor) { 664 DCHECK_EQ(phi->GetId(), -1); 665 DCHECK_NE(cursor->GetId(), -1); 666 DCHECK_EQ(cursor->GetBlock(), this); 667 phi->SetBlock(this); 668 phi->SetId(GetGraph()->GetNextInstructionId()); 669 UpdateInputsUsers(phi); 670 phis_.InsertInstructionAfter(phi, cursor); 671} 672 673static void Remove(HInstructionList* instruction_list, 674 HBasicBlock* block, 675 HInstruction* instruction, 676 bool ensure_safety) { 677 DCHECK_EQ(block, instruction->GetBlock()); 678 instruction->SetBlock(nullptr); 679 instruction_list->RemoveInstruction(instruction); 680 if (ensure_safety) { 681 DCHECK(instruction->GetUses().IsEmpty()); 682 DCHECK(instruction->GetEnvUses().IsEmpty()); 683 RemoveAsUser(instruction); 684 } 685} 686 687void HBasicBlock::RemoveInstruction(HInstruction* instruction, bool ensure_safety) { 688 DCHECK(!instruction->IsPhi()); 689 Remove(&instructions_, this, instruction, ensure_safety); 690} 691 692void HBasicBlock::RemovePhi(HPhi* phi, bool ensure_safety) { 693 Remove(&phis_, this, phi, ensure_safety); 694} 695 696void HBasicBlock::RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety) { 697 if (instruction->IsPhi()) { 698 RemovePhi(instruction->AsPhi(), ensure_safety); 699 } else { 700 RemoveInstruction(instruction, ensure_safety); 701 } 702} 703 704void HEnvironment::CopyFrom(const ArenaVector<HInstruction*>& locals) { 705 for (size_t i = 0; i < locals.size(); i++) { 706 HInstruction* instruction = locals[i]; 707 SetRawEnvAt(i, instruction); 708 if (instruction != nullptr) { 709 instruction->AddEnvUseAt(this, i); 710 } 711 } 712} 713 714void HEnvironment::CopyFrom(HEnvironment* env) { 715 for (size_t i = 0; i < env->Size(); i++) { 716 HInstruction* instruction = env->GetInstructionAt(i); 717 SetRawEnvAt(i, instruction); 718 if (instruction != nullptr) { 719 instruction->AddEnvUseAt(this, i); 720 } 721 } 722} 723 724void HEnvironment::CopyFromWithLoopPhiAdjustment(HEnvironment* env, 725 HBasicBlock* loop_header) { 726 DCHECK(loop_header->IsLoopHeader()); 727 for (size_t i = 0; i < env->Size(); i++) { 728 HInstruction* instruction = env->GetInstructionAt(i); 729 SetRawEnvAt(i, instruction); 730 if (instruction == nullptr) { 731 continue; 732 } 733 if (instruction->IsLoopHeaderPhi() && (instruction->GetBlock() == loop_header)) { 734 // At the end of the loop pre-header, the corresponding value for instruction 735 // is the first input of the phi. 736 HInstruction* initial = instruction->AsPhi()->InputAt(0); 737 DCHECK(initial->GetBlock()->Dominates(loop_header)); 738 SetRawEnvAt(i, initial); 739 initial->AddEnvUseAt(this, i); 740 } else { 741 instruction->AddEnvUseAt(this, i); 742 } 743 } 744} 745 746void HEnvironment::RemoveAsUserOfInput(size_t index) const { 747 DCHECK_LT(index, Size()); 748 const HUserRecord<HEnvironment*>& user_record = vregs_[index]; 749 user_record.GetInstruction()->RemoveEnvironmentUser(user_record.GetUseNode()); 750} 751 752HInstruction* HInstruction::GetNextDisregardingMoves() const { 753 HInstruction* next = GetNext(); 754 while (next != nullptr && next->IsParallelMove()) { 755 next = next->GetNext(); 756 } 757 return next; 758} 759 760HInstruction* HInstruction::GetPreviousDisregardingMoves() const { 761 HInstruction* previous = GetPrevious(); 762 while (previous != nullptr && previous->IsParallelMove()) { 763 previous = previous->GetPrevious(); 764 } 765 return previous; 766} 767 768void HInstructionList::AddInstruction(HInstruction* instruction) { 769 if (first_instruction_ == nullptr) { 770 DCHECK(last_instruction_ == nullptr); 771 first_instruction_ = last_instruction_ = instruction; 772 } else { 773 last_instruction_->next_ = instruction; 774 instruction->previous_ = last_instruction_; 775 last_instruction_ = instruction; 776 } 777} 778 779void HInstructionList::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { 780 DCHECK(Contains(cursor)); 781 if (cursor == first_instruction_) { 782 cursor->previous_ = instruction; 783 instruction->next_ = cursor; 784 first_instruction_ = instruction; 785 } else { 786 instruction->previous_ = cursor->previous_; 787 instruction->next_ = cursor; 788 cursor->previous_ = instruction; 789 instruction->previous_->next_ = instruction; 790 } 791} 792 793void HInstructionList::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) { 794 DCHECK(Contains(cursor)); 795 if (cursor == last_instruction_) { 796 cursor->next_ = instruction; 797 instruction->previous_ = cursor; 798 last_instruction_ = instruction; 799 } else { 800 instruction->next_ = cursor->next_; 801 instruction->previous_ = cursor; 802 cursor->next_ = instruction; 803 instruction->next_->previous_ = instruction; 804 } 805} 806 807void HInstructionList::RemoveInstruction(HInstruction* instruction) { 808 if (instruction->previous_ != nullptr) { 809 instruction->previous_->next_ = instruction->next_; 810 } 811 if (instruction->next_ != nullptr) { 812 instruction->next_->previous_ = instruction->previous_; 813 } 814 if (instruction == first_instruction_) { 815 first_instruction_ = instruction->next_; 816 } 817 if (instruction == last_instruction_) { 818 last_instruction_ = instruction->previous_; 819 } 820} 821 822bool HInstructionList::Contains(HInstruction* instruction) const { 823 for (HInstructionIterator it(*this); !it.Done(); it.Advance()) { 824 if (it.Current() == instruction) { 825 return true; 826 } 827 } 828 return false; 829} 830 831bool HInstructionList::FoundBefore(const HInstruction* instruction1, 832 const HInstruction* instruction2) const { 833 DCHECK_EQ(instruction1->GetBlock(), instruction2->GetBlock()); 834 for (HInstructionIterator it(*this); !it.Done(); it.Advance()) { 835 if (it.Current() == instruction1) { 836 return true; 837 } 838 if (it.Current() == instruction2) { 839 return false; 840 } 841 } 842 LOG(FATAL) << "Did not find an order between two instructions of the same block."; 843 return true; 844} 845 846bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const { 847 if (other_instruction == this) { 848 // An instruction does not strictly dominate itself. 849 return false; 850 } 851 HBasicBlock* block = GetBlock(); 852 HBasicBlock* other_block = other_instruction->GetBlock(); 853 if (block != other_block) { 854 return GetBlock()->Dominates(other_instruction->GetBlock()); 855 } else { 856 // If both instructions are in the same block, ensure this 857 // instruction comes before `other_instruction`. 858 if (IsPhi()) { 859 if (!other_instruction->IsPhi()) { 860 // Phis appear before non phi-instructions so this instruction 861 // dominates `other_instruction`. 862 return true; 863 } else { 864 // There is no order among phis. 865 LOG(FATAL) << "There is no dominance between phis of a same block."; 866 return false; 867 } 868 } else { 869 // `this` is not a phi. 870 if (other_instruction->IsPhi()) { 871 // Phis appear before non phi-instructions so this instruction 872 // does not dominate `other_instruction`. 873 return false; 874 } else { 875 // Check whether this instruction comes before 876 // `other_instruction` in the instruction list. 877 return block->GetInstructions().FoundBefore(this, other_instruction); 878 } 879 } 880 } 881} 882 883void HInstruction::ReplaceWith(HInstruction* other) { 884 DCHECK(other != nullptr); 885 for (HUseIterator<HInstruction*> it(GetUses()); !it.Done(); it.Advance()) { 886 HUseListNode<HInstruction*>* current = it.Current(); 887 HInstruction* user = current->GetUser(); 888 size_t input_index = current->GetIndex(); 889 user->SetRawInputAt(input_index, other); 890 other->AddUseAt(user, input_index); 891 } 892 893 for (HUseIterator<HEnvironment*> it(GetEnvUses()); !it.Done(); it.Advance()) { 894 HUseListNode<HEnvironment*>* current = it.Current(); 895 HEnvironment* user = current->GetUser(); 896 size_t input_index = current->GetIndex(); 897 user->SetRawEnvAt(input_index, other); 898 other->AddEnvUseAt(user, input_index); 899 } 900 901 uses_.Clear(); 902 env_uses_.Clear(); 903} 904 905void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) { 906 RemoveAsUserOfInput(index); 907 SetRawInputAt(index, replacement); 908 replacement->AddUseAt(this, index); 909} 910 911size_t HInstruction::EnvironmentSize() const { 912 return HasEnvironment() ? environment_->Size() : 0; 913} 914 915void HPhi::AddInput(HInstruction* input) { 916 DCHECK(input->GetBlock() != nullptr); 917 inputs_.push_back(HUserRecord<HInstruction*>(input)); 918 input->AddUseAt(this, inputs_.size() - 1); 919} 920 921void HPhi::RemoveInputAt(size_t index) { 922 RemoveAsUserOfInput(index); 923 inputs_.erase(inputs_.begin() + index); 924 for (size_t i = index, e = InputCount(); i < e; ++i) { 925 DCHECK_EQ(InputRecordAt(i).GetUseNode()->GetIndex(), i + 1u); 926 InputRecordAt(i).GetUseNode()->SetIndex(i); 927 } 928} 929 930#define DEFINE_ACCEPT(name, super) \ 931void H##name::Accept(HGraphVisitor* visitor) { \ 932 visitor->Visit##name(this); \ 933} 934 935FOR_EACH_INSTRUCTION(DEFINE_ACCEPT) 936 937#undef DEFINE_ACCEPT 938 939void HGraphVisitor::VisitInsertionOrder() { 940 const ArenaVector<HBasicBlock*>& blocks = graph_->GetBlocks(); 941 for (HBasicBlock* block : blocks) { 942 if (block != nullptr) { 943 VisitBasicBlock(block); 944 } 945 } 946} 947 948void HGraphVisitor::VisitReversePostOrder() { 949 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 950 VisitBasicBlock(it.Current()); 951 } 952} 953 954void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) { 955 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 956 it.Current()->Accept(this); 957 } 958 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 959 it.Current()->Accept(this); 960 } 961} 962 963HConstant* HTypeConversion::TryStaticEvaluation() const { 964 HGraph* graph = GetBlock()->GetGraph(); 965 if (GetInput()->IsIntConstant()) { 966 int32_t value = GetInput()->AsIntConstant()->GetValue(); 967 switch (GetResultType()) { 968 case Primitive::kPrimLong: 969 return graph->GetLongConstant(static_cast<int64_t>(value), GetDexPc()); 970 case Primitive::kPrimFloat: 971 return graph->GetFloatConstant(static_cast<float>(value), GetDexPc()); 972 case Primitive::kPrimDouble: 973 return graph->GetDoubleConstant(static_cast<double>(value), GetDexPc()); 974 default: 975 return nullptr; 976 } 977 } else if (GetInput()->IsLongConstant()) { 978 int64_t value = GetInput()->AsLongConstant()->GetValue(); 979 switch (GetResultType()) { 980 case Primitive::kPrimInt: 981 return graph->GetIntConstant(static_cast<int32_t>(value), GetDexPc()); 982 case Primitive::kPrimFloat: 983 return graph->GetFloatConstant(static_cast<float>(value), GetDexPc()); 984 case Primitive::kPrimDouble: 985 return graph->GetDoubleConstant(static_cast<double>(value), GetDexPc()); 986 default: 987 return nullptr; 988 } 989 } else if (GetInput()->IsFloatConstant()) { 990 float value = GetInput()->AsFloatConstant()->GetValue(); 991 switch (GetResultType()) { 992 case Primitive::kPrimInt: 993 if (std::isnan(value)) 994 return graph->GetIntConstant(0, GetDexPc()); 995 if (value >= kPrimIntMax) 996 return graph->GetIntConstant(kPrimIntMax, GetDexPc()); 997 if (value <= kPrimIntMin) 998 return graph->GetIntConstant(kPrimIntMin, GetDexPc()); 999 return graph->GetIntConstant(static_cast<int32_t>(value), GetDexPc()); 1000 case Primitive::kPrimLong: 1001 if (std::isnan(value)) 1002 return graph->GetLongConstant(0, GetDexPc()); 1003 if (value >= kPrimLongMax) 1004 return graph->GetLongConstant(kPrimLongMax, GetDexPc()); 1005 if (value <= kPrimLongMin) 1006 return graph->GetLongConstant(kPrimLongMin, GetDexPc()); 1007 return graph->GetLongConstant(static_cast<int64_t>(value), GetDexPc()); 1008 case Primitive::kPrimDouble: 1009 return graph->GetDoubleConstant(static_cast<double>(value), GetDexPc()); 1010 default: 1011 return nullptr; 1012 } 1013 } else if (GetInput()->IsDoubleConstant()) { 1014 double value = GetInput()->AsDoubleConstant()->GetValue(); 1015 switch (GetResultType()) { 1016 case Primitive::kPrimInt: 1017 if (std::isnan(value)) 1018 return graph->GetIntConstant(0, GetDexPc()); 1019 if (value >= kPrimIntMax) 1020 return graph->GetIntConstant(kPrimIntMax, GetDexPc()); 1021 if (value <= kPrimLongMin) 1022 return graph->GetIntConstant(kPrimIntMin, GetDexPc()); 1023 return graph->GetIntConstant(static_cast<int32_t>(value), GetDexPc()); 1024 case Primitive::kPrimLong: 1025 if (std::isnan(value)) 1026 return graph->GetLongConstant(0, GetDexPc()); 1027 if (value >= kPrimLongMax) 1028 return graph->GetLongConstant(kPrimLongMax, GetDexPc()); 1029 if (value <= kPrimLongMin) 1030 return graph->GetLongConstant(kPrimLongMin, GetDexPc()); 1031 return graph->GetLongConstant(static_cast<int64_t>(value), GetDexPc()); 1032 case Primitive::kPrimFloat: 1033 return graph->GetFloatConstant(static_cast<float>(value), GetDexPc()); 1034 default: 1035 return nullptr; 1036 } 1037 } 1038 return nullptr; 1039} 1040 1041HConstant* HUnaryOperation::TryStaticEvaluation() const { 1042 if (GetInput()->IsIntConstant()) { 1043 return Evaluate(GetInput()->AsIntConstant()); 1044 } else if (GetInput()->IsLongConstant()) { 1045 return Evaluate(GetInput()->AsLongConstant()); 1046 } 1047 return nullptr; 1048} 1049 1050HConstant* HBinaryOperation::TryStaticEvaluation() const { 1051 if (GetLeft()->IsIntConstant()) { 1052 if (GetRight()->IsIntConstant()) { 1053 return Evaluate(GetLeft()->AsIntConstant(), GetRight()->AsIntConstant()); 1054 } else if (GetRight()->IsLongConstant()) { 1055 return Evaluate(GetLeft()->AsIntConstant(), GetRight()->AsLongConstant()); 1056 } 1057 } else if (GetLeft()->IsLongConstant()) { 1058 if (GetRight()->IsIntConstant()) { 1059 return Evaluate(GetLeft()->AsLongConstant(), GetRight()->AsIntConstant()); 1060 } else if (GetRight()->IsLongConstant()) { 1061 return Evaluate(GetLeft()->AsLongConstant(), GetRight()->AsLongConstant()); 1062 } 1063 } 1064 return nullptr; 1065} 1066 1067HConstant* HBinaryOperation::GetConstantRight() const { 1068 if (GetRight()->IsConstant()) { 1069 return GetRight()->AsConstant(); 1070 } else if (IsCommutative() && GetLeft()->IsConstant()) { 1071 return GetLeft()->AsConstant(); 1072 } else { 1073 return nullptr; 1074 } 1075} 1076 1077// If `GetConstantRight()` returns one of the input, this returns the other 1078// one. Otherwise it returns null. 1079HInstruction* HBinaryOperation::GetLeastConstantLeft() const { 1080 HInstruction* most_constant_right = GetConstantRight(); 1081 if (most_constant_right == nullptr) { 1082 return nullptr; 1083 } else if (most_constant_right == GetLeft()) { 1084 return GetRight(); 1085 } else { 1086 return GetLeft(); 1087 } 1088} 1089 1090bool HCondition::IsBeforeWhenDisregardMoves(HInstruction* instruction) const { 1091 return this == instruction->GetPreviousDisregardingMoves(); 1092} 1093 1094bool HInstruction::Equals(HInstruction* other) const { 1095 if (!InstructionTypeEquals(other)) return false; 1096 DCHECK_EQ(GetKind(), other->GetKind()); 1097 if (!InstructionDataEquals(other)) return false; 1098 if (GetType() != other->GetType()) return false; 1099 if (InputCount() != other->InputCount()) return false; 1100 1101 for (size_t i = 0, e = InputCount(); i < e; ++i) { 1102 if (InputAt(i) != other->InputAt(i)) return false; 1103 } 1104 DCHECK_EQ(ComputeHashCode(), other->ComputeHashCode()); 1105 return true; 1106} 1107 1108std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs) { 1109#define DECLARE_CASE(type, super) case HInstruction::k##type: os << #type; break; 1110 switch (rhs) { 1111 FOR_EACH_INSTRUCTION(DECLARE_CASE) 1112 default: 1113 os << "Unknown instruction kind " << static_cast<int>(rhs); 1114 break; 1115 } 1116#undef DECLARE_CASE 1117 return os; 1118} 1119 1120void HInstruction::MoveBefore(HInstruction* cursor) { 1121 next_->previous_ = previous_; 1122 if (previous_ != nullptr) { 1123 previous_->next_ = next_; 1124 } 1125 if (block_->instructions_.first_instruction_ == this) { 1126 block_->instructions_.first_instruction_ = next_; 1127 } 1128 DCHECK_NE(block_->instructions_.last_instruction_, this); 1129 1130 previous_ = cursor->previous_; 1131 if (previous_ != nullptr) { 1132 previous_->next_ = this; 1133 } 1134 next_ = cursor; 1135 cursor->previous_ = this; 1136 block_ = cursor->block_; 1137 1138 if (block_->instructions_.first_instruction_ == cursor) { 1139 block_->instructions_.first_instruction_ = this; 1140 } 1141} 1142 1143HBasicBlock* HBasicBlock::SplitBefore(HInstruction* cursor) { 1144 DCHECK(!graph_->IsInSsaForm()) << "Support for SSA form not implemented"; 1145 DCHECK_EQ(cursor->GetBlock(), this); 1146 1147 HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), 1148 cursor->GetDexPc()); 1149 new_block->instructions_.first_instruction_ = cursor; 1150 new_block->instructions_.last_instruction_ = instructions_.last_instruction_; 1151 instructions_.last_instruction_ = cursor->previous_; 1152 if (cursor->previous_ == nullptr) { 1153 instructions_.first_instruction_ = nullptr; 1154 } else { 1155 cursor->previous_->next_ = nullptr; 1156 cursor->previous_ = nullptr; 1157 } 1158 1159 new_block->instructions_.SetBlockOfInstructions(new_block); 1160 AddInstruction(new (GetGraph()->GetArena()) HGoto(new_block->GetDexPc())); 1161 1162 for (HBasicBlock* successor : GetSuccessors()) { 1163 new_block->successors_.push_back(successor); 1164 successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block; 1165 } 1166 successors_.clear(); 1167 AddSuccessor(new_block); 1168 1169 GetGraph()->AddBlock(new_block); 1170 return new_block; 1171} 1172 1173HBasicBlock* HBasicBlock::CreateImmediateDominator() { 1174 DCHECK(!graph_->IsInSsaForm()) << "Support for SSA form not implemented"; 1175 DCHECK(!IsCatchBlock()) << "Support for updating try/catch information not implemented."; 1176 1177 HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), GetDexPc()); 1178 1179 for (HBasicBlock* predecessor : GetPredecessors()) { 1180 new_block->predecessors_.push_back(predecessor); 1181 predecessor->successors_[predecessor->GetSuccessorIndexOf(this)] = new_block; 1182 } 1183 predecessors_.clear(); 1184 AddPredecessor(new_block); 1185 1186 GetGraph()->AddBlock(new_block); 1187 return new_block; 1188} 1189 1190HBasicBlock* HBasicBlock::SplitAfter(HInstruction* cursor) { 1191 DCHECK(!cursor->IsControlFlow()); 1192 DCHECK_NE(instructions_.last_instruction_, cursor); 1193 DCHECK_EQ(cursor->GetBlock(), this); 1194 1195 HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), GetDexPc()); 1196 new_block->instructions_.first_instruction_ = cursor->GetNext(); 1197 new_block->instructions_.last_instruction_ = instructions_.last_instruction_; 1198 cursor->next_->previous_ = nullptr; 1199 cursor->next_ = nullptr; 1200 instructions_.last_instruction_ = cursor; 1201 1202 new_block->instructions_.SetBlockOfInstructions(new_block); 1203 for (HBasicBlock* successor : GetSuccessors()) { 1204 new_block->successors_.push_back(successor); 1205 successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block; 1206 } 1207 successors_.clear(); 1208 1209 for (HBasicBlock* dominated : GetDominatedBlocks()) { 1210 dominated->dominator_ = new_block; 1211 new_block->dominated_blocks_.push_back(dominated); 1212 } 1213 dominated_blocks_.clear(); 1214 return new_block; 1215} 1216 1217const HTryBoundary* HBasicBlock::ComputeTryEntryOfSuccessors() const { 1218 if (EndsWithTryBoundary()) { 1219 HTryBoundary* try_boundary = GetLastInstruction()->AsTryBoundary(); 1220 if (try_boundary->IsEntry()) { 1221 DCHECK(!IsTryBlock()); 1222 return try_boundary; 1223 } else { 1224 DCHECK(IsTryBlock()); 1225 DCHECK(try_catch_information_->GetTryEntry().HasSameExceptionHandlersAs(*try_boundary)); 1226 return nullptr; 1227 } 1228 } else if (IsTryBlock()) { 1229 return &try_catch_information_->GetTryEntry(); 1230 } else { 1231 return nullptr; 1232 } 1233} 1234 1235bool HBasicBlock::HasThrowingInstructions() const { 1236 for (HInstructionIterator it(GetInstructions()); !it.Done(); it.Advance()) { 1237 if (it.Current()->CanThrow()) { 1238 return true; 1239 } 1240 } 1241 return false; 1242} 1243 1244static bool HasOnlyOneInstruction(const HBasicBlock& block) { 1245 return block.GetPhis().IsEmpty() 1246 && !block.GetInstructions().IsEmpty() 1247 && block.GetFirstInstruction() == block.GetLastInstruction(); 1248} 1249 1250bool HBasicBlock::IsSingleGoto() const { 1251 return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsGoto(); 1252} 1253 1254bool HBasicBlock::IsSingleTryBoundary() const { 1255 return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsTryBoundary(); 1256} 1257 1258bool HBasicBlock::EndsWithControlFlowInstruction() const { 1259 return !GetInstructions().IsEmpty() && GetLastInstruction()->IsControlFlow(); 1260} 1261 1262bool HBasicBlock::EndsWithIf() const { 1263 return !GetInstructions().IsEmpty() && GetLastInstruction()->IsIf(); 1264} 1265 1266bool HBasicBlock::EndsWithTryBoundary() const { 1267 return !GetInstructions().IsEmpty() && GetLastInstruction()->IsTryBoundary(); 1268} 1269 1270bool HBasicBlock::HasSinglePhi() const { 1271 return !GetPhis().IsEmpty() && GetFirstPhi()->GetNext() == nullptr; 1272} 1273 1274bool HTryBoundary::HasSameExceptionHandlersAs(const HTryBoundary& other) const { 1275 if (GetBlock()->GetSuccessors().size() != other.GetBlock()->GetSuccessors().size()) { 1276 return false; 1277 } 1278 1279 // Exception handlers need to be stored in the same order. 1280 for (HExceptionHandlerIterator it1(*this), it2(other); 1281 !it1.Done(); 1282 it1.Advance(), it2.Advance()) { 1283 DCHECK(!it2.Done()); 1284 if (it1.Current() != it2.Current()) { 1285 return false; 1286 } 1287 } 1288 return true; 1289} 1290 1291size_t HInstructionList::CountSize() const { 1292 size_t size = 0; 1293 HInstruction* current = first_instruction_; 1294 for (; current != nullptr; current = current->GetNext()) { 1295 size++; 1296 } 1297 return size; 1298} 1299 1300void HInstructionList::SetBlockOfInstructions(HBasicBlock* block) const { 1301 for (HInstruction* current = first_instruction_; 1302 current != nullptr; 1303 current = current->GetNext()) { 1304 current->SetBlock(block); 1305 } 1306} 1307 1308void HInstructionList::AddAfter(HInstruction* cursor, const HInstructionList& instruction_list) { 1309 DCHECK(Contains(cursor)); 1310 if (!instruction_list.IsEmpty()) { 1311 if (cursor == last_instruction_) { 1312 last_instruction_ = instruction_list.last_instruction_; 1313 } else { 1314 cursor->next_->previous_ = instruction_list.last_instruction_; 1315 } 1316 instruction_list.last_instruction_->next_ = cursor->next_; 1317 cursor->next_ = instruction_list.first_instruction_; 1318 instruction_list.first_instruction_->previous_ = cursor; 1319 } 1320} 1321 1322void HInstructionList::Add(const HInstructionList& instruction_list) { 1323 if (IsEmpty()) { 1324 first_instruction_ = instruction_list.first_instruction_; 1325 last_instruction_ = instruction_list.last_instruction_; 1326 } else { 1327 AddAfter(last_instruction_, instruction_list); 1328 } 1329} 1330 1331void HBasicBlock::DisconnectAndDelete() { 1332 // Dominators must be removed after all the blocks they dominate. This way 1333 // a loop header is removed last, a requirement for correct loop information 1334 // iteration. 1335 DCHECK(dominated_blocks_.empty()); 1336 1337 // Remove the block from all loops it is included in. 1338 for (HLoopInformationOutwardIterator it(*this); !it.Done(); it.Advance()) { 1339 HLoopInformation* loop_info = it.Current(); 1340 loop_info->Remove(this); 1341 if (loop_info->IsBackEdge(*this)) { 1342 // If this was the last back edge of the loop, we deliberately leave the 1343 // loop in an inconsistent state and will fail SSAChecker unless the 1344 // entire loop is removed during the pass. 1345 loop_info->RemoveBackEdge(this); 1346 } 1347 } 1348 1349 // Disconnect the block from its predecessors and update their control-flow 1350 // instructions. 1351 for (HBasicBlock* predecessor : predecessors_) { 1352 HInstruction* last_instruction = predecessor->GetLastInstruction(); 1353 predecessor->RemoveSuccessor(this); 1354 uint32_t num_pred_successors = predecessor->GetSuccessors().size(); 1355 if (num_pred_successors == 1u) { 1356 // If we have one successor after removing one, then we must have 1357 // had an HIf or HPackedSwitch, as they have more than one successor. 1358 // Replace those with a HGoto. 1359 DCHECK(last_instruction->IsIf() || last_instruction->IsPackedSwitch()); 1360 predecessor->RemoveInstruction(last_instruction); 1361 predecessor->AddInstruction(new (graph_->GetArena()) HGoto(last_instruction->GetDexPc())); 1362 } else if (num_pred_successors == 0u) { 1363 // The predecessor has no remaining successors and therefore must be dead. 1364 // We deliberately leave it without a control-flow instruction so that the 1365 // SSAChecker fails unless it is not removed during the pass too. 1366 predecessor->RemoveInstruction(last_instruction); 1367 } else { 1368 // There are multiple successors left. This must come from a HPackedSwitch 1369 // and we are in the middle of removing the HPackedSwitch. Like above, leave 1370 // this alone, and the SSAChecker will fail if it is not removed as well. 1371 DCHECK(last_instruction->IsPackedSwitch()); 1372 } 1373 } 1374 predecessors_.clear(); 1375 1376 // Disconnect the block from its successors and update their phis. 1377 for (HBasicBlock* successor : successors_) { 1378 // Delete this block from the list of predecessors. 1379 size_t this_index = successor->GetPredecessorIndexOf(this); 1380 successor->predecessors_.erase(successor->predecessors_.begin() + this_index); 1381 1382 // Check that `successor` has other predecessors, otherwise `this` is the 1383 // dominator of `successor` which violates the order DCHECKed at the top. 1384 DCHECK(!successor->predecessors_.empty()); 1385 1386 // Remove this block's entries in the successor's phis. 1387 if (successor->predecessors_.size() == 1u) { 1388 // The successor has just one predecessor left. Replace phis with the only 1389 // remaining input. 1390 for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) { 1391 HPhi* phi = phi_it.Current()->AsPhi(); 1392 phi->ReplaceWith(phi->InputAt(1 - this_index)); 1393 successor->RemovePhi(phi); 1394 } 1395 } else { 1396 for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) { 1397 phi_it.Current()->AsPhi()->RemoveInputAt(this_index); 1398 } 1399 } 1400 } 1401 successors_.clear(); 1402 1403 // Disconnect from the dominator. 1404 dominator_->RemoveDominatedBlock(this); 1405 SetDominator(nullptr); 1406 1407 // Delete from the graph. The function safely deletes remaining instructions 1408 // and updates the reverse post order. 1409 graph_->DeleteDeadBlock(this); 1410 SetGraph(nullptr); 1411} 1412 1413void HBasicBlock::MergeWith(HBasicBlock* other) { 1414 DCHECK_EQ(GetGraph(), other->GetGraph()); 1415 DCHECK(ContainsElement(dominated_blocks_, other)); 1416 DCHECK_EQ(GetSingleSuccessor(), other); 1417 DCHECK_EQ(other->GetSinglePredecessor(), this); 1418 DCHECK(other->GetPhis().IsEmpty()); 1419 1420 // Move instructions from `other` to `this`. 1421 DCHECK(EndsWithControlFlowInstruction()); 1422 RemoveInstruction(GetLastInstruction()); 1423 instructions_.Add(other->GetInstructions()); 1424 other->instructions_.SetBlockOfInstructions(this); 1425 other->instructions_.Clear(); 1426 1427 // Remove `other` from the loops it is included in. 1428 for (HLoopInformationOutwardIterator it(*other); !it.Done(); it.Advance()) { 1429 HLoopInformation* loop_info = it.Current(); 1430 loop_info->Remove(other); 1431 if (loop_info->IsBackEdge(*other)) { 1432 loop_info->ReplaceBackEdge(other, this); 1433 } 1434 } 1435 1436 // Update links to the successors of `other`. 1437 successors_.clear(); 1438 while (!other->successors_.empty()) { 1439 HBasicBlock* successor = other->GetSuccessor(0); 1440 successor->ReplacePredecessor(other, this); 1441 } 1442 1443 // Update the dominator tree. 1444 RemoveDominatedBlock(other); 1445 for (HBasicBlock* dominated : other->GetDominatedBlocks()) { 1446 dominated_blocks_.push_back(dominated); 1447 dominated->SetDominator(this); 1448 } 1449 other->dominated_blocks_.clear(); 1450 other->dominator_ = nullptr; 1451 1452 // Clear the list of predecessors of `other` in preparation of deleting it. 1453 other->predecessors_.clear(); 1454 1455 // Delete `other` from the graph. The function updates reverse post order. 1456 graph_->DeleteDeadBlock(other); 1457 other->SetGraph(nullptr); 1458} 1459 1460void HBasicBlock::MergeWithInlined(HBasicBlock* other) { 1461 DCHECK_NE(GetGraph(), other->GetGraph()); 1462 DCHECK(GetDominatedBlocks().empty()); 1463 DCHECK(GetSuccessors().empty()); 1464 DCHECK(!EndsWithControlFlowInstruction()); 1465 DCHECK(other->GetSinglePredecessor()->IsEntryBlock()); 1466 DCHECK(other->GetPhis().IsEmpty()); 1467 DCHECK(!other->IsInLoop()); 1468 1469 // Move instructions from `other` to `this`. 1470 instructions_.Add(other->GetInstructions()); 1471 other->instructions_.SetBlockOfInstructions(this); 1472 1473 // Update links to the successors of `other`. 1474 successors_.clear(); 1475 while (!other->successors_.empty()) { 1476 HBasicBlock* successor = other->GetSuccessor(0); 1477 successor->ReplacePredecessor(other, this); 1478 } 1479 1480 // Update the dominator tree. 1481 for (HBasicBlock* dominated : other->GetDominatedBlocks()) { 1482 dominated_blocks_.push_back(dominated); 1483 dominated->SetDominator(this); 1484 } 1485 other->dominated_blocks_.clear(); 1486 other->dominator_ = nullptr; 1487 other->graph_ = nullptr; 1488} 1489 1490void HBasicBlock::ReplaceWith(HBasicBlock* other) { 1491 while (!GetPredecessors().empty()) { 1492 HBasicBlock* predecessor = GetPredecessor(0); 1493 predecessor->ReplaceSuccessor(this, other); 1494 } 1495 while (!GetSuccessors().empty()) { 1496 HBasicBlock* successor = GetSuccessor(0); 1497 successor->ReplacePredecessor(this, other); 1498 } 1499 for (HBasicBlock* dominated : GetDominatedBlocks()) { 1500 other->AddDominatedBlock(dominated); 1501 } 1502 GetDominator()->ReplaceDominatedBlock(this, other); 1503 other->SetDominator(GetDominator()); 1504 dominator_ = nullptr; 1505 graph_ = nullptr; 1506} 1507 1508// Create space in `blocks` for adding `number_of_new_blocks` entries 1509// starting at location `at`. Blocks after `at` are moved accordingly. 1510static void MakeRoomFor(ArenaVector<HBasicBlock*>* blocks, 1511 size_t number_of_new_blocks, 1512 size_t after) { 1513 DCHECK_LT(after, blocks->size()); 1514 size_t old_size = blocks->size(); 1515 size_t new_size = old_size + number_of_new_blocks; 1516 blocks->resize(new_size); 1517 std::copy_backward(blocks->begin() + after + 1u, blocks->begin() + old_size, blocks->end()); 1518} 1519 1520void HGraph::DeleteDeadBlock(HBasicBlock* block) { 1521 DCHECK_EQ(block->GetGraph(), this); 1522 DCHECK(block->GetSuccessors().empty()); 1523 DCHECK(block->GetPredecessors().empty()); 1524 DCHECK(block->GetDominatedBlocks().empty()); 1525 DCHECK(block->GetDominator() == nullptr); 1526 1527 for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 1528 block->RemoveInstruction(it.Current()); 1529 } 1530 for (HBackwardInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 1531 block->RemovePhi(it.Current()->AsPhi()); 1532 } 1533 1534 if (block->IsExitBlock()) { 1535 exit_block_ = nullptr; 1536 } 1537 1538 RemoveElement(reverse_post_order_, block); 1539 blocks_[block->GetBlockId()] = nullptr; 1540} 1541 1542HInstruction* HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { 1543 DCHECK(HasExitBlock()) << "Unimplemented scenario"; 1544 // Update the environments in this graph to have the invoke's environment 1545 // as parent. 1546 { 1547 HReversePostOrderIterator it(*this); 1548 it.Advance(); // Skip the entry block, we do not need to update the entry's suspend check. 1549 for (; !it.Done(); it.Advance()) { 1550 HBasicBlock* block = it.Current(); 1551 for (HInstructionIterator instr_it(block->GetInstructions()); 1552 !instr_it.Done(); 1553 instr_it.Advance()) { 1554 HInstruction* current = instr_it.Current(); 1555 if (current->NeedsEnvironment()) { 1556 current->GetEnvironment()->SetAndCopyParentChain( 1557 outer_graph->GetArena(), invoke->GetEnvironment()); 1558 } 1559 } 1560 } 1561 } 1562 outer_graph->UpdateMaximumNumberOfOutVRegs(GetMaximumNumberOfOutVRegs()); 1563 if (HasBoundsChecks()) { 1564 outer_graph->SetHasBoundsChecks(true); 1565 } 1566 1567 HInstruction* return_value = nullptr; 1568 if (GetBlocks().size() == 3) { 1569 // Simple case of an entry block, a body block, and an exit block. 1570 // Put the body block's instruction into `invoke`'s block. 1571 HBasicBlock* body = GetBlock(1); 1572 DCHECK(GetBlock(0)->IsEntryBlock()); 1573 DCHECK(GetBlock(2)->IsExitBlock()); 1574 DCHECK(!body->IsExitBlock()); 1575 HInstruction* last = body->GetLastInstruction(); 1576 1577 invoke->GetBlock()->instructions_.AddAfter(invoke, body->GetInstructions()); 1578 body->GetInstructions().SetBlockOfInstructions(invoke->GetBlock()); 1579 1580 // Replace the invoke with the return value of the inlined graph. 1581 if (last->IsReturn()) { 1582 return_value = last->InputAt(0); 1583 invoke->ReplaceWith(return_value); 1584 } else { 1585 DCHECK(last->IsReturnVoid()); 1586 } 1587 1588 invoke->GetBlock()->RemoveInstruction(last); 1589 } else { 1590 // Need to inline multiple blocks. We split `invoke`'s block 1591 // into two blocks, merge the first block of the inlined graph into 1592 // the first half, and replace the exit block of the inlined graph 1593 // with the second half. 1594 ArenaAllocator* allocator = outer_graph->GetArena(); 1595 HBasicBlock* at = invoke->GetBlock(); 1596 HBasicBlock* to = at->SplitAfter(invoke); 1597 1598 HBasicBlock* first = entry_block_->GetSuccessor(0); 1599 DCHECK(!first->IsInLoop()); 1600 at->MergeWithInlined(first); 1601 exit_block_->ReplaceWith(to); 1602 1603 // Update all predecessors of the exit block (now the `to` block) 1604 // to not `HReturn` but `HGoto` instead. 1605 bool returns_void = to->GetPredecessor(0)->GetLastInstruction()->IsReturnVoid(); 1606 if (to->GetPredecessors().size() == 1) { 1607 HBasicBlock* predecessor = to->GetPredecessor(0); 1608 HInstruction* last = predecessor->GetLastInstruction(); 1609 if (!returns_void) { 1610 return_value = last->InputAt(0); 1611 } 1612 predecessor->AddInstruction(new (allocator) HGoto(last->GetDexPc())); 1613 predecessor->RemoveInstruction(last); 1614 } else { 1615 if (!returns_void) { 1616 // There will be multiple returns. 1617 return_value = new (allocator) HPhi( 1618 allocator, kNoRegNumber, 0, HPhi::ToPhiType(invoke->GetType()), to->GetDexPc()); 1619 to->AddPhi(return_value->AsPhi()); 1620 } 1621 for (HBasicBlock* predecessor : to->GetPredecessors()) { 1622 HInstruction* last = predecessor->GetLastInstruction(); 1623 if (!returns_void) { 1624 return_value->AsPhi()->AddInput(last->InputAt(0)); 1625 } 1626 predecessor->AddInstruction(new (allocator) HGoto(last->GetDexPc())); 1627 predecessor->RemoveInstruction(last); 1628 } 1629 } 1630 1631 if (return_value != nullptr) { 1632 invoke->ReplaceWith(return_value); 1633 } 1634 1635 // Update the meta information surrounding blocks: 1636 // (1) the graph they are now in, 1637 // (2) the reverse post order of that graph, 1638 // (3) the potential loop information they are now in. 1639 1640 // We don't add the entry block, the exit block, and the first block, which 1641 // has been merged with `at`. 1642 static constexpr int kNumberOfSkippedBlocksInCallee = 3; 1643 1644 // We add the `to` block. 1645 static constexpr int kNumberOfNewBlocksInCaller = 1; 1646 size_t blocks_added = (reverse_post_order_.size() - kNumberOfSkippedBlocksInCallee) 1647 + kNumberOfNewBlocksInCaller; 1648 1649 // Find the location of `at` in the outer graph's reverse post order. The new 1650 // blocks will be added after it. 1651 size_t index_of_at = IndexOfElement(outer_graph->reverse_post_order_, at); 1652 MakeRoomFor(&outer_graph->reverse_post_order_, blocks_added, index_of_at); 1653 1654 // Do a reverse post order of the blocks in the callee and do (1), (2), 1655 // and (3) to the blocks that apply. 1656 HLoopInformation* info = at->GetLoopInformation(); 1657 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { 1658 HBasicBlock* current = it.Current(); 1659 if (current != exit_block_ && current != entry_block_ && current != first) { 1660 DCHECK(!current->IsInLoop()); 1661 DCHECK(current->GetGraph() == this); 1662 current->SetGraph(outer_graph); 1663 outer_graph->AddBlock(current); 1664 outer_graph->reverse_post_order_[++index_of_at] = current; 1665 if (info != nullptr) { 1666 current->SetLoopInformation(info); 1667 for (HLoopInformationOutwardIterator loop_it(*at); !loop_it.Done(); loop_it.Advance()) { 1668 loop_it.Current()->Add(current); 1669 } 1670 } 1671 } 1672 } 1673 1674 // Do (1), (2), and (3) to `to`. 1675 to->SetGraph(outer_graph); 1676 outer_graph->AddBlock(to); 1677 outer_graph->reverse_post_order_[++index_of_at] = to; 1678 if (info != nullptr) { 1679 to->SetLoopInformation(info); 1680 for (HLoopInformationOutwardIterator loop_it(*at); !loop_it.Done(); loop_it.Advance()) { 1681 loop_it.Current()->Add(to); 1682 } 1683 if (info->IsBackEdge(*at)) { 1684 // Only `to` can become a back edge, as the inlined blocks 1685 // are predecessors of `to`. 1686 info->ReplaceBackEdge(at, to); 1687 } 1688 } 1689 } 1690 1691 // Update the next instruction id of the outer graph, so that instructions 1692 // added later get bigger ids than those in the inner graph. 1693 outer_graph->SetCurrentInstructionId(GetNextInstructionId()); 1694 1695 // Walk over the entry block and: 1696 // - Move constants from the entry block to the outer_graph's entry block, 1697 // - Replace HParameterValue instructions with their real value. 1698 // - Remove suspend checks, that hold an environment. 1699 // We must do this after the other blocks have been inlined, otherwise ids of 1700 // constants could overlap with the inner graph. 1701 size_t parameter_index = 0; 1702 for (HInstructionIterator it(entry_block_->GetInstructions()); !it.Done(); it.Advance()) { 1703 HInstruction* current = it.Current(); 1704 if (current->IsNullConstant()) { 1705 current->ReplaceWith(outer_graph->GetNullConstant(current->GetDexPc())); 1706 } else if (current->IsIntConstant()) { 1707 current->ReplaceWith(outer_graph->GetIntConstant( 1708 current->AsIntConstant()->GetValue(), current->GetDexPc())); 1709 } else if (current->IsLongConstant()) { 1710 current->ReplaceWith(outer_graph->GetLongConstant( 1711 current->AsLongConstant()->GetValue(), current->GetDexPc())); 1712 } else if (current->IsFloatConstant()) { 1713 current->ReplaceWith(outer_graph->GetFloatConstant( 1714 current->AsFloatConstant()->GetValue(), current->GetDexPc())); 1715 } else if (current->IsDoubleConstant()) { 1716 current->ReplaceWith(outer_graph->GetDoubleConstant( 1717 current->AsDoubleConstant()->GetValue(), current->GetDexPc())); 1718 } else if (current->IsParameterValue()) { 1719 if (kIsDebugBuild 1720 && invoke->IsInvokeStaticOrDirect() 1721 && invoke->AsInvokeStaticOrDirect()->IsStaticWithExplicitClinitCheck()) { 1722 // Ensure we do not use the last input of `invoke`, as it 1723 // contains a clinit check which is not an actual argument. 1724 size_t last_input_index = invoke->InputCount() - 1; 1725 DCHECK(parameter_index != last_input_index); 1726 } 1727 current->ReplaceWith(invoke->InputAt(parameter_index++)); 1728 } else if (current->IsCurrentMethod()) { 1729 current->ReplaceWith(outer_graph->GetCurrentMethod()); 1730 } else { 1731 DCHECK(current->IsGoto() || current->IsSuspendCheck()); 1732 entry_block_->RemoveInstruction(current); 1733 } 1734 } 1735 1736 // Finally remove the invoke from the caller. 1737 invoke->GetBlock()->RemoveInstruction(invoke); 1738 1739 return return_value; 1740} 1741 1742/* 1743 * Loop will be transformed to: 1744 * old_pre_header 1745 * | 1746 * if_block 1747 * / \ 1748 * dummy_block deopt_block 1749 * \ / 1750 * new_pre_header 1751 * | 1752 * header 1753 */ 1754void HGraph::TransformLoopHeaderForBCE(HBasicBlock* header) { 1755 DCHECK(header->IsLoopHeader()); 1756 HBasicBlock* pre_header = header->GetDominator(); 1757 1758 // Need this to avoid critical edge. 1759 HBasicBlock* if_block = new (arena_) HBasicBlock(this, header->GetDexPc()); 1760 // Need this to avoid critical edge. 1761 HBasicBlock* dummy_block = new (arena_) HBasicBlock(this, header->GetDexPc()); 1762 HBasicBlock* deopt_block = new (arena_) HBasicBlock(this, header->GetDexPc()); 1763 HBasicBlock* new_pre_header = new (arena_) HBasicBlock(this, header->GetDexPc()); 1764 AddBlock(if_block); 1765 AddBlock(dummy_block); 1766 AddBlock(deopt_block); 1767 AddBlock(new_pre_header); 1768 1769 header->ReplacePredecessor(pre_header, new_pre_header); 1770 pre_header->successors_.clear(); 1771 pre_header->dominated_blocks_.clear(); 1772 1773 pre_header->AddSuccessor(if_block); 1774 if_block->AddSuccessor(dummy_block); // True successor 1775 if_block->AddSuccessor(deopt_block); // False successor 1776 dummy_block->AddSuccessor(new_pre_header); 1777 deopt_block->AddSuccessor(new_pre_header); 1778 1779 pre_header->dominated_blocks_.push_back(if_block); 1780 if_block->SetDominator(pre_header); 1781 if_block->dominated_blocks_.push_back(dummy_block); 1782 dummy_block->SetDominator(if_block); 1783 if_block->dominated_blocks_.push_back(deopt_block); 1784 deopt_block->SetDominator(if_block); 1785 if_block->dominated_blocks_.push_back(new_pre_header); 1786 new_pre_header->SetDominator(if_block); 1787 new_pre_header->dominated_blocks_.push_back(header); 1788 header->SetDominator(new_pre_header); 1789 1790 size_t index_of_header = IndexOfElement(reverse_post_order_, header); 1791 MakeRoomFor(&reverse_post_order_, 4, index_of_header - 1); 1792 reverse_post_order_[index_of_header++] = if_block; 1793 reverse_post_order_[index_of_header++] = dummy_block; 1794 reverse_post_order_[index_of_header++] = deopt_block; 1795 reverse_post_order_[index_of_header++] = new_pre_header; 1796 1797 HLoopInformation* info = pre_header->GetLoopInformation(); 1798 if (info != nullptr) { 1799 if_block->SetLoopInformation(info); 1800 dummy_block->SetLoopInformation(info); 1801 deopt_block->SetLoopInformation(info); 1802 new_pre_header->SetLoopInformation(info); 1803 for (HLoopInformationOutwardIterator loop_it(*pre_header); 1804 !loop_it.Done(); 1805 loop_it.Advance()) { 1806 loop_it.Current()->Add(if_block); 1807 loop_it.Current()->Add(dummy_block); 1808 loop_it.Current()->Add(deopt_block); 1809 loop_it.Current()->Add(new_pre_header); 1810 } 1811 } 1812} 1813 1814void HInstruction::SetReferenceTypeInfo(ReferenceTypeInfo rti) { 1815 if (kIsDebugBuild) { 1816 DCHECK_EQ(GetType(), Primitive::kPrimNot); 1817 ScopedObjectAccess soa(Thread::Current()); 1818 DCHECK(rti.IsValid()) << "Invalid RTI for " << DebugName(); 1819 if (IsBoundType()) { 1820 // Having the test here spares us from making the method virtual just for 1821 // the sake of a DCHECK. 1822 ReferenceTypeInfo upper_bound_rti = AsBoundType()->GetUpperBound(); 1823 DCHECK(upper_bound_rti.IsSupertypeOf(rti)) 1824 << " upper_bound_rti: " << upper_bound_rti 1825 << " rti: " << rti; 1826 DCHECK(!upper_bound_rti.GetTypeHandle()->CannotBeAssignedFromOtherTypes() || rti.IsExact()); 1827 } 1828 } 1829 reference_type_info_ = rti; 1830} 1831 1832ReferenceTypeInfo::ReferenceTypeInfo() : type_handle_(TypeHandle()), is_exact_(false) {} 1833 1834ReferenceTypeInfo::ReferenceTypeInfo(TypeHandle type_handle, bool is_exact) 1835 : type_handle_(type_handle), is_exact_(is_exact) { 1836 if (kIsDebugBuild) { 1837 ScopedObjectAccess soa(Thread::Current()); 1838 DCHECK(IsValidHandle(type_handle)); 1839 } 1840} 1841 1842std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs) { 1843 ScopedObjectAccess soa(Thread::Current()); 1844 os << "[" 1845 << " is_valid=" << rhs.IsValid() 1846 << " type=" << (!rhs.IsValid() ? "?" : PrettyClass(rhs.GetTypeHandle().Get())) 1847 << " is_exact=" << rhs.IsExact() 1848 << " ]"; 1849 return os; 1850} 1851 1852bool HInstruction::HasAnyEnvironmentUseBefore(HInstruction* other) { 1853 // For now, assume that instructions in different blocks may use the 1854 // environment. 1855 // TODO: Use the control flow to decide if this is true. 1856 if (GetBlock() != other->GetBlock()) { 1857 return true; 1858 } 1859 1860 // We know that we are in the same block. Walk from 'this' to 'other', 1861 // checking to see if there is any instruction with an environment. 1862 HInstruction* current = this; 1863 for (; current != other && current != nullptr; current = current->GetNext()) { 1864 // This is a conservative check, as the instruction result may not be in 1865 // the referenced environment. 1866 if (current->HasEnvironment()) { 1867 return true; 1868 } 1869 } 1870 1871 // We should have been called with 'this' before 'other' in the block. 1872 // Just confirm this. 1873 DCHECK(current != nullptr); 1874 return false; 1875} 1876 1877void HInvoke::SetIntrinsic(Intrinsics intrinsic, 1878 IntrinsicNeedsEnvironmentOrCache needs_env_or_cache) { 1879 intrinsic_ = intrinsic; 1880 IntrinsicOptimizations opt(this); 1881 if (needs_env_or_cache == kNoEnvironmentOrCache) { 1882 opt.SetDoesNotNeedDexCache(); 1883 opt.SetDoesNotNeedEnvironment(); 1884 } 1885} 1886 1887bool HInvoke::NeedsEnvironment() const { 1888 if (!IsIntrinsic()) { 1889 return true; 1890 } 1891 IntrinsicOptimizations opt(*this); 1892 return !opt.GetDoesNotNeedEnvironment(); 1893} 1894 1895bool HInvokeStaticOrDirect::NeedsDexCache() const { 1896 if (IsRecursive() || IsStringInit()) { 1897 return false; 1898 } 1899 if (!IsIntrinsic()) { 1900 return true; 1901 } 1902 IntrinsicOptimizations opt(*this); 1903 return !opt.GetDoesNotNeedDexCache(); 1904} 1905 1906void HInstruction::RemoveEnvironmentUsers() { 1907 for (HUseIterator<HEnvironment*> use_it(GetEnvUses()); !use_it.Done(); use_it.Advance()) { 1908 HUseListNode<HEnvironment*>* user_node = use_it.Current(); 1909 HEnvironment* user = user_node->GetUser(); 1910 user->SetRawEnvAt(user_node->GetIndex(), nullptr); 1911 } 1912 env_uses_.Clear(); 1913} 1914 1915} // namespace art 1916