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#include "nodes.h" 17 18#include <cfloat> 19 20#include "code_generator.h" 21#include "common_dominator.h" 22#include "ssa_builder.h" 23#include "base/bit_vector-inl.h" 24#include "base/bit_utils.h" 25#include "base/stl_util.h" 26#include "intrinsics.h" 27#include "mirror/class-inl.h" 28#include "scoped_thread_state_change.h" 29 30namespace art { 31 32// Enable floating-point static evaluation during constant folding 33// only if all floating-point operations and constants evaluate in the 34// range and precision of the type used (i.e., 32-bit float, 64-bit 35// double). 36static constexpr bool kEnableFloatingPointStaticEvaluation = (FLT_EVAL_METHOD == 0); 37 38void HGraph::InitializeInexactObjectRTI(StackHandleScopeCollection* handles) { 39 ScopedObjectAccess soa(Thread::Current()); 40 // Create the inexact Object reference type and store it in the HGraph. 41 ClassLinker* linker = Runtime::Current()->GetClassLinker(); 42 inexact_object_rti_ = ReferenceTypeInfo::Create( 43 handles->NewHandle(linker->GetClassRoot(ClassLinker::kJavaLangObject)), 44 /* is_exact */ false); 45} 46 47void HGraph::AddBlock(HBasicBlock* block) { 48 block->SetBlockId(blocks_.size()); 49 blocks_.push_back(block); 50} 51 52void HGraph::FindBackEdges(ArenaBitVector* visited) { 53 // "visited" must be empty on entry, it's an output argument for all visited (i.e. live) blocks. 54 DCHECK_EQ(visited->GetHighestBitSet(), -1); 55 56 // Nodes that we're currently visiting, indexed by block id. 57 ArenaBitVector visiting(arena_, blocks_.size(), false, kArenaAllocGraphBuilder); 58 // Number of successors visited from a given node, indexed by block id. 59 ArenaVector<size_t> successors_visited(blocks_.size(), 60 0u, 61 arena_->Adapter(kArenaAllocGraphBuilder)); 62 // Stack of nodes that we're currently visiting (same as marked in "visiting" above). 63 ArenaVector<HBasicBlock*> worklist(arena_->Adapter(kArenaAllocGraphBuilder)); 64 constexpr size_t kDefaultWorklistSize = 8; 65 worklist.reserve(kDefaultWorklistSize); 66 visited->SetBit(entry_block_->GetBlockId()); 67 visiting.SetBit(entry_block_->GetBlockId()); 68 worklist.push_back(entry_block_); 69 70 while (!worklist.empty()) { 71 HBasicBlock* current = worklist.back(); 72 uint32_t current_id = current->GetBlockId(); 73 if (successors_visited[current_id] == current->GetSuccessors().size()) { 74 visiting.ClearBit(current_id); 75 worklist.pop_back(); 76 } else { 77 HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++]; 78 uint32_t successor_id = successor->GetBlockId(); 79 if (visiting.IsBitSet(successor_id)) { 80 DCHECK(ContainsElement(worklist, successor)); 81 successor->AddBackEdge(current); 82 } else if (!visited->IsBitSet(successor_id)) { 83 visited->SetBit(successor_id); 84 visiting.SetBit(successor_id); 85 worklist.push_back(successor); 86 } 87 } 88 } 89} 90 91static void RemoveEnvironmentUses(HInstruction* instruction) { 92 for (HEnvironment* environment = instruction->GetEnvironment(); 93 environment != nullptr; 94 environment = environment->GetParent()) { 95 for (size_t i = 0, e = environment->Size(); i < e; ++i) { 96 if (environment->GetInstructionAt(i) != nullptr) { 97 environment->RemoveAsUserOfInput(i); 98 } 99 } 100 } 101} 102 103static void RemoveAsUser(HInstruction* instruction) { 104 for (size_t i = 0; i < instruction->InputCount(); i++) { 105 instruction->RemoveAsUserOfInput(i); 106 } 107 108 RemoveEnvironmentUses(instruction); 109} 110 111void HGraph::RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const { 112 for (size_t i = 0; i < blocks_.size(); ++i) { 113 if (!visited.IsBitSet(i)) { 114 HBasicBlock* block = blocks_[i]; 115 if (block == nullptr) continue; 116 DCHECK(block->GetPhis().IsEmpty()) << "Phis are not inserted at this stage"; 117 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 118 RemoveAsUser(it.Current()); 119 } 120 } 121 } 122} 123 124void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) { 125 for (size_t i = 0; i < blocks_.size(); ++i) { 126 if (!visited.IsBitSet(i)) { 127 HBasicBlock* block = blocks_[i]; 128 if (block == nullptr) continue; 129 // We only need to update the successor, which might be live. 130 for (HBasicBlock* successor : block->GetSuccessors()) { 131 successor->RemovePredecessor(block); 132 } 133 // Remove the block from the list of blocks, so that further analyses 134 // never see it. 135 blocks_[i] = nullptr; 136 if (block->IsExitBlock()) { 137 SetExitBlock(nullptr); 138 } 139 // Mark the block as removed. This is used by the HGraphBuilder to discard 140 // the block as a branch target. 141 block->SetGraph(nullptr); 142 } 143 } 144} 145 146GraphAnalysisResult HGraph::BuildDominatorTree() { 147 ArenaBitVector visited(arena_, blocks_.size(), false, kArenaAllocGraphBuilder); 148 149 // (1) Find the back edges in the graph doing a DFS traversal. 150 FindBackEdges(&visited); 151 152 // (2) Remove instructions and phis from blocks not visited during 153 // the initial DFS as users from other instructions, so that 154 // users can be safely removed before uses later. 155 RemoveInstructionsAsUsersFromDeadBlocks(visited); 156 157 // (3) Remove blocks not visited during the initial DFS. 158 // Step (5) requires dead blocks to be removed from the 159 // predecessors list of live blocks. 160 RemoveDeadBlocks(visited); 161 162 // (4) Simplify the CFG now, so that we don't need to recompute 163 // dominators and the reverse post order. 164 SimplifyCFG(); 165 166 // (5) Compute the dominance information and the reverse post order. 167 ComputeDominanceInformation(); 168 169 // (6) Analyze loops discovered through back edge analysis, and 170 // set the loop information on each block. 171 GraphAnalysisResult result = AnalyzeLoops(); 172 if (result != kAnalysisSuccess) { 173 return result; 174 } 175 176 // (7) Precompute per-block try membership before entering the SSA builder, 177 // which needs the information to build catch block phis from values of 178 // locals at throwing instructions inside try blocks. 179 ComputeTryBlockInformation(); 180 181 return kAnalysisSuccess; 182} 183 184void HGraph::ClearDominanceInformation() { 185 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { 186 it.Current()->ClearDominanceInformation(); 187 } 188 reverse_post_order_.clear(); 189} 190 191void HGraph::ClearLoopInformation() { 192 SetHasIrreducibleLoops(false); 193 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { 194 it.Current()->SetLoopInformation(nullptr); 195 } 196} 197 198void HBasicBlock::ClearDominanceInformation() { 199 dominated_blocks_.clear(); 200 dominator_ = nullptr; 201} 202 203HInstruction* HBasicBlock::GetFirstInstructionDisregardMoves() const { 204 HInstruction* instruction = GetFirstInstruction(); 205 while (instruction->IsParallelMove()) { 206 instruction = instruction->GetNext(); 207 } 208 return instruction; 209} 210 211static bool UpdateDominatorOfSuccessor(HBasicBlock* block, HBasicBlock* successor) { 212 DCHECK(ContainsElement(block->GetSuccessors(), successor)); 213 214 HBasicBlock* old_dominator = successor->GetDominator(); 215 HBasicBlock* new_dominator = 216 (old_dominator == nullptr) ? block 217 : CommonDominator::ForPair(old_dominator, block); 218 219 if (old_dominator == new_dominator) { 220 return false; 221 } else { 222 successor->SetDominator(new_dominator); 223 return true; 224 } 225} 226 227void HGraph::ComputeDominanceInformation() { 228 DCHECK(reverse_post_order_.empty()); 229 reverse_post_order_.reserve(blocks_.size()); 230 reverse_post_order_.push_back(entry_block_); 231 232 // Number of visits of a given node, indexed by block id. 233 ArenaVector<size_t> visits(blocks_.size(), 0u, arena_->Adapter(kArenaAllocGraphBuilder)); 234 // Number of successors visited from a given node, indexed by block id. 235 ArenaVector<size_t> successors_visited(blocks_.size(), 236 0u, 237 arena_->Adapter(kArenaAllocGraphBuilder)); 238 // Nodes for which we need to visit successors. 239 ArenaVector<HBasicBlock*> worklist(arena_->Adapter(kArenaAllocGraphBuilder)); 240 constexpr size_t kDefaultWorklistSize = 8; 241 worklist.reserve(kDefaultWorklistSize); 242 worklist.push_back(entry_block_); 243 244 while (!worklist.empty()) { 245 HBasicBlock* current = worklist.back(); 246 uint32_t current_id = current->GetBlockId(); 247 if (successors_visited[current_id] == current->GetSuccessors().size()) { 248 worklist.pop_back(); 249 } else { 250 HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++]; 251 UpdateDominatorOfSuccessor(current, successor); 252 253 // Once all the forward edges have been visited, we know the immediate 254 // dominator of the block. We can then start visiting its successors. 255 if (++visits[successor->GetBlockId()] == 256 successor->GetPredecessors().size() - successor->NumberOfBackEdges()) { 257 reverse_post_order_.push_back(successor); 258 worklist.push_back(successor); 259 } 260 } 261 } 262 263 // Check if the graph has back edges not dominated by their respective headers. 264 // If so, we need to update the dominators of those headers and recursively of 265 // their successors. We do that with a fix-point iteration over all blocks. 266 // The algorithm is guaranteed to terminate because it loops only if the sum 267 // of all dominator chains has decreased in the current iteration. 268 bool must_run_fix_point = false; 269 for (HBasicBlock* block : blocks_) { 270 if (block != nullptr && 271 block->IsLoopHeader() && 272 block->GetLoopInformation()->HasBackEdgeNotDominatedByHeader()) { 273 must_run_fix_point = true; 274 break; 275 } 276 } 277 if (must_run_fix_point) { 278 bool update_occurred = true; 279 while (update_occurred) { 280 update_occurred = false; 281 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { 282 HBasicBlock* block = it.Current(); 283 for (HBasicBlock* successor : block->GetSuccessors()) { 284 update_occurred |= UpdateDominatorOfSuccessor(block, successor); 285 } 286 } 287 } 288 } 289 290 // Make sure that there are no remaining blocks whose dominator information 291 // needs to be updated. 292 if (kIsDebugBuild) { 293 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { 294 HBasicBlock* block = it.Current(); 295 for (HBasicBlock* successor : block->GetSuccessors()) { 296 DCHECK(!UpdateDominatorOfSuccessor(block, successor)); 297 } 298 } 299 } 300 301 // Populate `dominated_blocks_` information after computing all dominators. 302 // The potential presence of irreducible loops requires to do it after. 303 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { 304 HBasicBlock* block = it.Current(); 305 if (!block->IsEntryBlock()) { 306 block->GetDominator()->AddDominatedBlock(block); 307 } 308 } 309} 310 311HBasicBlock* HGraph::SplitEdge(HBasicBlock* block, HBasicBlock* successor) { 312 HBasicBlock* new_block = new (arena_) HBasicBlock(this, successor->GetDexPc()); 313 AddBlock(new_block); 314 // Use `InsertBetween` to ensure the predecessor index and successor index of 315 // `block` and `successor` are preserved. 316 new_block->InsertBetween(block, successor); 317 return new_block; 318} 319 320void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) { 321 // Insert a new node between `block` and `successor` to split the 322 // critical edge. 323 HBasicBlock* new_block = SplitEdge(block, successor); 324 new_block->AddInstruction(new (arena_) HGoto(successor->GetDexPc())); 325 if (successor->IsLoopHeader()) { 326 // If we split at a back edge boundary, make the new block the back edge. 327 HLoopInformation* info = successor->GetLoopInformation(); 328 if (info->IsBackEdge(*block)) { 329 info->RemoveBackEdge(block); 330 info->AddBackEdge(new_block); 331 } 332 } 333} 334 335void HGraph::SimplifyLoop(HBasicBlock* header) { 336 HLoopInformation* info = header->GetLoopInformation(); 337 338 // Make sure the loop has only one pre header. This simplifies SSA building by having 339 // to just look at the pre header to know which locals are initialized at entry of the 340 // loop. Also, don't allow the entry block to be a pre header: this simplifies inlining 341 // this graph. 342 size_t number_of_incomings = header->GetPredecessors().size() - info->NumberOfBackEdges(); 343 if (number_of_incomings != 1 || (GetEntryBlock()->GetSingleSuccessor() == header)) { 344 HBasicBlock* pre_header = new (arena_) HBasicBlock(this, header->GetDexPc()); 345 AddBlock(pre_header); 346 pre_header->AddInstruction(new (arena_) HGoto(header->GetDexPc())); 347 348 for (size_t pred = 0; pred < header->GetPredecessors().size(); ++pred) { 349 HBasicBlock* predecessor = header->GetPredecessors()[pred]; 350 if (!info->IsBackEdge(*predecessor)) { 351 predecessor->ReplaceSuccessor(header, pre_header); 352 pred--; 353 } 354 } 355 pre_header->AddSuccessor(header); 356 } 357 358 // Make sure the first predecessor of a loop header is the incoming block. 359 if (info->IsBackEdge(*header->GetPredecessors()[0])) { 360 HBasicBlock* to_swap = header->GetPredecessors()[0]; 361 for (size_t pred = 1, e = header->GetPredecessors().size(); pred < e; ++pred) { 362 HBasicBlock* predecessor = header->GetPredecessors()[pred]; 363 if (!info->IsBackEdge(*predecessor)) { 364 header->predecessors_[pred] = to_swap; 365 header->predecessors_[0] = predecessor; 366 break; 367 } 368 } 369 } 370 371 HInstruction* first_instruction = header->GetFirstInstruction(); 372 if (first_instruction != nullptr && first_instruction->IsSuspendCheck()) { 373 // Called from DeadBlockElimination. Update SuspendCheck pointer. 374 info->SetSuspendCheck(first_instruction->AsSuspendCheck()); 375 } 376} 377 378void HGraph::ComputeTryBlockInformation() { 379 // Iterate in reverse post order to propagate try membership information from 380 // predecessors to their successors. 381 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { 382 HBasicBlock* block = it.Current(); 383 if (block->IsEntryBlock() || block->IsCatchBlock()) { 384 // Catch blocks after simplification have only exceptional predecessors 385 // and hence are never in tries. 386 continue; 387 } 388 389 // Infer try membership from the first predecessor. Having simplified loops, 390 // the first predecessor can never be a back edge and therefore it must have 391 // been visited already and had its try membership set. 392 HBasicBlock* first_predecessor = block->GetPredecessors()[0]; 393 DCHECK(!block->IsLoopHeader() || !block->GetLoopInformation()->IsBackEdge(*first_predecessor)); 394 const HTryBoundary* try_entry = first_predecessor->ComputeTryEntryOfSuccessors(); 395 if (try_entry != nullptr && 396 (block->GetTryCatchInformation() == nullptr || 397 try_entry != &block->GetTryCatchInformation()->GetTryEntry())) { 398 // We are either setting try block membership for the first time or it 399 // has changed. 400 block->SetTryCatchInformation(new (arena_) TryCatchInformation(*try_entry)); 401 } 402 } 403} 404 405void HGraph::SimplifyCFG() { 406// Simplify the CFG for future analysis, and code generation: 407 // (1): Split critical edges. 408 // (2): Simplify loops by having only one preheader. 409 // NOTE: We're appending new blocks inside the loop, so we need to use index because iterators 410 // can be invalidated. We remember the initial size to avoid iterating over the new blocks. 411 for (size_t block_id = 0u, end = blocks_.size(); block_id != end; ++block_id) { 412 HBasicBlock* block = blocks_[block_id]; 413 if (block == nullptr) continue; 414 if (block->GetSuccessors().size() > 1) { 415 // Only split normal-flow edges. We cannot split exceptional edges as they 416 // are synthesized (approximate real control flow), and we do not need to 417 // anyway. Moves that would be inserted there are performed by the runtime. 418 ArrayRef<HBasicBlock* const> normal_successors = block->GetNormalSuccessors(); 419 for (size_t j = 0, e = normal_successors.size(); j < e; ++j) { 420 HBasicBlock* successor = normal_successors[j]; 421 DCHECK(!successor->IsCatchBlock()); 422 if (successor == exit_block_) { 423 // (Throw/Return/ReturnVoid)->TryBoundary->Exit. Special case which we 424 // do not want to split because Goto->Exit is not allowed. 425 DCHECK(block->IsSingleTryBoundary()); 426 } else if (successor->GetPredecessors().size() > 1) { 427 SplitCriticalEdge(block, successor); 428 // SplitCriticalEdge could have invalidated the `normal_successors` 429 // ArrayRef. We must re-acquire it. 430 normal_successors = block->GetNormalSuccessors(); 431 DCHECK_EQ(normal_successors[j]->GetSingleSuccessor(), successor); 432 DCHECK_EQ(e, normal_successors.size()); 433 } 434 } 435 } 436 if (block->IsLoopHeader()) { 437 SimplifyLoop(block); 438 } else if (!block->IsEntryBlock() && 439 block->GetFirstInstruction() != nullptr && 440 block->GetFirstInstruction()->IsSuspendCheck()) { 441 // We are being called by the dead code elimiation pass, and what used to be 442 // a loop got dismantled. Just remove the suspend check. 443 block->RemoveInstruction(block->GetFirstInstruction()); 444 } 445 } 446} 447 448GraphAnalysisResult HGraph::AnalyzeLoops() const { 449 // We iterate post order to ensure we visit inner loops before outer loops. 450 // `PopulateRecursive` needs this guarantee to know whether a natural loop 451 // contains an irreducible loop. 452 for (HPostOrderIterator it(*this); !it.Done(); it.Advance()) { 453 HBasicBlock* block = it.Current(); 454 if (block->IsLoopHeader()) { 455 if (block->IsCatchBlock()) { 456 // TODO: Dealing with exceptional back edges could be tricky because 457 // they only approximate the real control flow. Bail out for now. 458 return kAnalysisFailThrowCatchLoop; 459 } 460 block->GetLoopInformation()->Populate(); 461 } 462 } 463 return kAnalysisSuccess; 464} 465 466void HLoopInformation::Dump(std::ostream& os) { 467 os << "header: " << header_->GetBlockId() << std::endl; 468 os << "pre header: " << GetPreHeader()->GetBlockId() << std::endl; 469 for (HBasicBlock* block : back_edges_) { 470 os << "back edge: " << block->GetBlockId() << std::endl; 471 } 472 for (HBasicBlock* block : header_->GetPredecessors()) { 473 os << "predecessor: " << block->GetBlockId() << std::endl; 474 } 475 for (uint32_t idx : blocks_.Indexes()) { 476 os << " in loop: " << idx << std::endl; 477 } 478} 479 480void HGraph::InsertConstant(HConstant* constant) { 481 // New constants are inserted before the SuspendCheck at the bottom of the 482 // entry block. Note that this method can be called from the graph builder and 483 // the entry block therefore may not end with SuspendCheck->Goto yet. 484 HInstruction* insert_before = nullptr; 485 486 HInstruction* gota = entry_block_->GetLastInstruction(); 487 if (gota != nullptr && gota->IsGoto()) { 488 HInstruction* suspend_check = gota->GetPrevious(); 489 if (suspend_check != nullptr && suspend_check->IsSuspendCheck()) { 490 insert_before = suspend_check; 491 } else { 492 insert_before = gota; 493 } 494 } 495 496 if (insert_before == nullptr) { 497 entry_block_->AddInstruction(constant); 498 } else { 499 entry_block_->InsertInstructionBefore(constant, insert_before); 500 } 501} 502 503HNullConstant* HGraph::GetNullConstant(uint32_t dex_pc) { 504 // For simplicity, don't bother reviving the cached null constant if it is 505 // not null and not in a block. Otherwise, we need to clear the instruction 506 // id and/or any invariants the graph is assuming when adding new instructions. 507 if ((cached_null_constant_ == nullptr) || (cached_null_constant_->GetBlock() == nullptr)) { 508 cached_null_constant_ = new (arena_) HNullConstant(dex_pc); 509 cached_null_constant_->SetReferenceTypeInfo(inexact_object_rti_); 510 InsertConstant(cached_null_constant_); 511 } 512 if (kIsDebugBuild) { 513 ScopedObjectAccess soa(Thread::Current()); 514 DCHECK(cached_null_constant_->GetReferenceTypeInfo().IsValid()); 515 } 516 return cached_null_constant_; 517} 518 519HCurrentMethod* HGraph::GetCurrentMethod() { 520 // For simplicity, don't bother reviving the cached current method if it is 521 // not null and not in a block. Otherwise, we need to clear the instruction 522 // id and/or any invariants the graph is assuming when adding new instructions. 523 if ((cached_current_method_ == nullptr) || (cached_current_method_->GetBlock() == nullptr)) { 524 cached_current_method_ = new (arena_) HCurrentMethod( 525 Is64BitInstructionSet(instruction_set_) ? Primitive::kPrimLong : Primitive::kPrimInt, 526 entry_block_->GetDexPc()); 527 if (entry_block_->GetFirstInstruction() == nullptr) { 528 entry_block_->AddInstruction(cached_current_method_); 529 } else { 530 entry_block_->InsertInstructionBefore( 531 cached_current_method_, entry_block_->GetFirstInstruction()); 532 } 533 } 534 return cached_current_method_; 535} 536 537HConstant* HGraph::GetConstant(Primitive::Type type, int64_t value, uint32_t dex_pc) { 538 switch (type) { 539 case Primitive::Type::kPrimBoolean: 540 DCHECK(IsUint<1>(value)); 541 FALLTHROUGH_INTENDED; 542 case Primitive::Type::kPrimByte: 543 case Primitive::Type::kPrimChar: 544 case Primitive::Type::kPrimShort: 545 case Primitive::Type::kPrimInt: 546 DCHECK(IsInt(Primitive::ComponentSize(type) * kBitsPerByte, value)); 547 return GetIntConstant(static_cast<int32_t>(value), dex_pc); 548 549 case Primitive::Type::kPrimLong: 550 return GetLongConstant(value, dex_pc); 551 552 default: 553 LOG(FATAL) << "Unsupported constant type"; 554 UNREACHABLE(); 555 } 556} 557 558void HGraph::CacheFloatConstant(HFloatConstant* constant) { 559 int32_t value = bit_cast<int32_t, float>(constant->GetValue()); 560 DCHECK(cached_float_constants_.find(value) == cached_float_constants_.end()); 561 cached_float_constants_.Overwrite(value, constant); 562} 563 564void HGraph::CacheDoubleConstant(HDoubleConstant* constant) { 565 int64_t value = bit_cast<int64_t, double>(constant->GetValue()); 566 DCHECK(cached_double_constants_.find(value) == cached_double_constants_.end()); 567 cached_double_constants_.Overwrite(value, constant); 568} 569 570void HLoopInformation::Add(HBasicBlock* block) { 571 blocks_.SetBit(block->GetBlockId()); 572} 573 574void HLoopInformation::Remove(HBasicBlock* block) { 575 blocks_.ClearBit(block->GetBlockId()); 576} 577 578void HLoopInformation::PopulateRecursive(HBasicBlock* block) { 579 if (blocks_.IsBitSet(block->GetBlockId())) { 580 return; 581 } 582 583 blocks_.SetBit(block->GetBlockId()); 584 block->SetInLoop(this); 585 if (block->IsLoopHeader()) { 586 // We're visiting loops in post-order, so inner loops must have been 587 // populated already. 588 DCHECK(block->GetLoopInformation()->IsPopulated()); 589 if (block->GetLoopInformation()->IsIrreducible()) { 590 contains_irreducible_loop_ = true; 591 } 592 } 593 for (HBasicBlock* predecessor : block->GetPredecessors()) { 594 PopulateRecursive(predecessor); 595 } 596} 597 598void HLoopInformation::PopulateIrreducibleRecursive(HBasicBlock* block, ArenaBitVector* finalized) { 599 size_t block_id = block->GetBlockId(); 600 601 // If `block` is in `finalized`, we know its membership in the loop has been 602 // decided and it does not need to be revisited. 603 if (finalized->IsBitSet(block_id)) { 604 return; 605 } 606 607 bool is_finalized = false; 608 if (block->IsLoopHeader()) { 609 // If we hit a loop header in an irreducible loop, we first check if the 610 // pre header of that loop belongs to the currently analyzed loop. If it does, 611 // then we visit the back edges. 612 // Note that we cannot use GetPreHeader, as the loop may have not been populated 613 // yet. 614 HBasicBlock* pre_header = block->GetPredecessors()[0]; 615 PopulateIrreducibleRecursive(pre_header, finalized); 616 if (blocks_.IsBitSet(pre_header->GetBlockId())) { 617 block->SetInLoop(this); 618 blocks_.SetBit(block_id); 619 finalized->SetBit(block_id); 620 is_finalized = true; 621 622 HLoopInformation* info = block->GetLoopInformation(); 623 for (HBasicBlock* back_edge : info->GetBackEdges()) { 624 PopulateIrreducibleRecursive(back_edge, finalized); 625 } 626 } 627 } else { 628 // Visit all predecessors. If one predecessor is part of the loop, this 629 // block is also part of this loop. 630 for (HBasicBlock* predecessor : block->GetPredecessors()) { 631 PopulateIrreducibleRecursive(predecessor, finalized); 632 if (!is_finalized && blocks_.IsBitSet(predecessor->GetBlockId())) { 633 block->SetInLoop(this); 634 blocks_.SetBit(block_id); 635 finalized->SetBit(block_id); 636 is_finalized = true; 637 } 638 } 639 } 640 641 // All predecessors have been recursively visited. Mark finalized if not marked yet. 642 if (!is_finalized) { 643 finalized->SetBit(block_id); 644 } 645} 646 647void HLoopInformation::Populate() { 648 DCHECK_EQ(blocks_.NumSetBits(), 0u) << "Loop information has already been populated"; 649 // Populate this loop: starting with the back edge, recursively add predecessors 650 // that are not already part of that loop. Set the header as part of the loop 651 // to end the recursion. 652 // This is a recursive implementation of the algorithm described in 653 // "Advanced Compiler Design & Implementation" (Muchnick) p192. 654 HGraph* graph = header_->GetGraph(); 655 blocks_.SetBit(header_->GetBlockId()); 656 header_->SetInLoop(this); 657 658 bool is_irreducible_loop = HasBackEdgeNotDominatedByHeader(); 659 660 if (is_irreducible_loop) { 661 ArenaBitVector visited(graph->GetArena(), 662 graph->GetBlocks().size(), 663 /* expandable */ false, 664 kArenaAllocGraphBuilder); 665 // Stop marking blocks at the loop header. 666 visited.SetBit(header_->GetBlockId()); 667 668 for (HBasicBlock* back_edge : GetBackEdges()) { 669 PopulateIrreducibleRecursive(back_edge, &visited); 670 } 671 } else { 672 for (HBasicBlock* back_edge : GetBackEdges()) { 673 PopulateRecursive(back_edge); 674 } 675 } 676 677 if (!is_irreducible_loop && graph->IsCompilingOsr()) { 678 // When compiling in OSR mode, all loops in the compiled method may be entered 679 // from the interpreter. We treat this OSR entry point just like an extra entry 680 // to an irreducible loop, so we need to mark the method's loops as irreducible. 681 // This does not apply to inlined loops which do not act as OSR entry points. 682 if (suspend_check_ == nullptr) { 683 // Just building the graph in OSR mode, this loop is not inlined. We never build an 684 // inner graph in OSR mode as we can do OSR transition only from the outer method. 685 is_irreducible_loop = true; 686 } else { 687 // Look at the suspend check's environment to determine if the loop was inlined. 688 DCHECK(suspend_check_->HasEnvironment()); 689 if (!suspend_check_->GetEnvironment()->IsFromInlinedInvoke()) { 690 is_irreducible_loop = true; 691 } 692 } 693 } 694 if (is_irreducible_loop) { 695 irreducible_ = true; 696 contains_irreducible_loop_ = true; 697 graph->SetHasIrreducibleLoops(true); 698 } 699} 700 701HBasicBlock* HLoopInformation::GetPreHeader() const { 702 HBasicBlock* block = header_->GetPredecessors()[0]; 703 DCHECK(irreducible_ || (block == header_->GetDominator())); 704 return block; 705} 706 707bool HLoopInformation::Contains(const HBasicBlock& block) const { 708 return blocks_.IsBitSet(block.GetBlockId()); 709} 710 711bool HLoopInformation::IsIn(const HLoopInformation& other) const { 712 return other.blocks_.IsBitSet(header_->GetBlockId()); 713} 714 715bool HLoopInformation::IsDefinedOutOfTheLoop(HInstruction* instruction) const { 716 return !blocks_.IsBitSet(instruction->GetBlock()->GetBlockId()); 717} 718 719size_t HLoopInformation::GetLifetimeEnd() const { 720 size_t last_position = 0; 721 for (HBasicBlock* back_edge : GetBackEdges()) { 722 last_position = std::max(back_edge->GetLifetimeEnd(), last_position); 723 } 724 return last_position; 725} 726 727bool HLoopInformation::HasBackEdgeNotDominatedByHeader() const { 728 for (HBasicBlock* back_edge : GetBackEdges()) { 729 DCHECK(back_edge->GetDominator() != nullptr); 730 if (!header_->Dominates(back_edge)) { 731 return true; 732 } 733 } 734 return false; 735} 736 737bool HLoopInformation::DominatesAllBackEdges(HBasicBlock* block) { 738 for (HBasicBlock* back_edge : GetBackEdges()) { 739 if (!block->Dominates(back_edge)) { 740 return false; 741 } 742 } 743 return true; 744} 745 746bool HBasicBlock::Dominates(HBasicBlock* other) const { 747 // Walk up the dominator tree from `other`, to find out if `this` 748 // is an ancestor. 749 HBasicBlock* current = other; 750 while (current != nullptr) { 751 if (current == this) { 752 return true; 753 } 754 current = current->GetDominator(); 755 } 756 return false; 757} 758 759static void UpdateInputsUsers(HInstruction* instruction) { 760 for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) { 761 instruction->InputAt(i)->AddUseAt(instruction, i); 762 } 763 // Environment should be created later. 764 DCHECK(!instruction->HasEnvironment()); 765} 766 767void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial, 768 HInstruction* replacement) { 769 DCHECK(initial->GetBlock() == this); 770 if (initial->IsControlFlow()) { 771 // We can only replace a control flow instruction with another control flow instruction. 772 DCHECK(replacement->IsControlFlow()); 773 DCHECK_EQ(replacement->GetId(), -1); 774 DCHECK_EQ(replacement->GetType(), Primitive::kPrimVoid); 775 DCHECK_EQ(initial->GetBlock(), this); 776 DCHECK_EQ(initial->GetType(), Primitive::kPrimVoid); 777 DCHECK(initial->GetUses().empty()); 778 DCHECK(initial->GetEnvUses().empty()); 779 replacement->SetBlock(this); 780 replacement->SetId(GetGraph()->GetNextInstructionId()); 781 instructions_.InsertInstructionBefore(replacement, initial); 782 UpdateInputsUsers(replacement); 783 } else { 784 InsertInstructionBefore(replacement, initial); 785 initial->ReplaceWith(replacement); 786 } 787 RemoveInstruction(initial); 788} 789 790void HBasicBlock::MoveInstructionBefore(HInstruction* insn, HInstruction* cursor) { 791 DCHECK(!cursor->IsPhi()); 792 DCHECK(!insn->IsPhi()); 793 DCHECK(!insn->IsControlFlow()); 794 DCHECK(insn->CanBeMoved()); 795 DCHECK(!insn->HasSideEffects()); 796 797 HBasicBlock* from_block = insn->GetBlock(); 798 HBasicBlock* to_block = cursor->GetBlock(); 799 DCHECK(from_block != to_block); 800 801 from_block->RemoveInstruction(insn, /* ensure_safety */ false); 802 insn->SetBlock(to_block); 803 to_block->instructions_.InsertInstructionBefore(insn, cursor); 804} 805 806static void Add(HInstructionList* instruction_list, 807 HBasicBlock* block, 808 HInstruction* instruction) { 809 DCHECK(instruction->GetBlock() == nullptr); 810 DCHECK_EQ(instruction->GetId(), -1); 811 instruction->SetBlock(block); 812 instruction->SetId(block->GetGraph()->GetNextInstructionId()); 813 UpdateInputsUsers(instruction); 814 instruction_list->AddInstruction(instruction); 815} 816 817void HBasicBlock::AddInstruction(HInstruction* instruction) { 818 Add(&instructions_, this, instruction); 819} 820 821void HBasicBlock::AddPhi(HPhi* phi) { 822 Add(&phis_, this, phi); 823} 824 825void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { 826 DCHECK(!cursor->IsPhi()); 827 DCHECK(!instruction->IsPhi()); 828 DCHECK_EQ(instruction->GetId(), -1); 829 DCHECK_NE(cursor->GetId(), -1); 830 DCHECK_EQ(cursor->GetBlock(), this); 831 DCHECK(!instruction->IsControlFlow()); 832 instruction->SetBlock(this); 833 instruction->SetId(GetGraph()->GetNextInstructionId()); 834 UpdateInputsUsers(instruction); 835 instructions_.InsertInstructionBefore(instruction, cursor); 836} 837 838void HBasicBlock::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) { 839 DCHECK(!cursor->IsPhi()); 840 DCHECK(!instruction->IsPhi()); 841 DCHECK_EQ(instruction->GetId(), -1); 842 DCHECK_NE(cursor->GetId(), -1); 843 DCHECK_EQ(cursor->GetBlock(), this); 844 DCHECK(!instruction->IsControlFlow()); 845 DCHECK(!cursor->IsControlFlow()); 846 instruction->SetBlock(this); 847 instruction->SetId(GetGraph()->GetNextInstructionId()); 848 UpdateInputsUsers(instruction); 849 instructions_.InsertInstructionAfter(instruction, cursor); 850} 851 852void HBasicBlock::InsertPhiAfter(HPhi* phi, HPhi* cursor) { 853 DCHECK_EQ(phi->GetId(), -1); 854 DCHECK_NE(cursor->GetId(), -1); 855 DCHECK_EQ(cursor->GetBlock(), this); 856 phi->SetBlock(this); 857 phi->SetId(GetGraph()->GetNextInstructionId()); 858 UpdateInputsUsers(phi); 859 phis_.InsertInstructionAfter(phi, cursor); 860} 861 862static void Remove(HInstructionList* instruction_list, 863 HBasicBlock* block, 864 HInstruction* instruction, 865 bool ensure_safety) { 866 DCHECK_EQ(block, instruction->GetBlock()); 867 instruction->SetBlock(nullptr); 868 instruction_list->RemoveInstruction(instruction); 869 if (ensure_safety) { 870 DCHECK(instruction->GetUses().empty()); 871 DCHECK(instruction->GetEnvUses().empty()); 872 RemoveAsUser(instruction); 873 } 874} 875 876void HBasicBlock::RemoveInstruction(HInstruction* instruction, bool ensure_safety) { 877 DCHECK(!instruction->IsPhi()); 878 Remove(&instructions_, this, instruction, ensure_safety); 879} 880 881void HBasicBlock::RemovePhi(HPhi* phi, bool ensure_safety) { 882 Remove(&phis_, this, phi, ensure_safety); 883} 884 885void HBasicBlock::RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety) { 886 if (instruction->IsPhi()) { 887 RemovePhi(instruction->AsPhi(), ensure_safety); 888 } else { 889 RemoveInstruction(instruction, ensure_safety); 890 } 891} 892 893void HEnvironment::CopyFrom(const ArenaVector<HInstruction*>& locals) { 894 for (size_t i = 0; i < locals.size(); i++) { 895 HInstruction* instruction = locals[i]; 896 SetRawEnvAt(i, instruction); 897 if (instruction != nullptr) { 898 instruction->AddEnvUseAt(this, i); 899 } 900 } 901} 902 903void HEnvironment::CopyFrom(HEnvironment* env) { 904 for (size_t i = 0; i < env->Size(); i++) { 905 HInstruction* instruction = env->GetInstructionAt(i); 906 SetRawEnvAt(i, instruction); 907 if (instruction != nullptr) { 908 instruction->AddEnvUseAt(this, i); 909 } 910 } 911} 912 913void HEnvironment::CopyFromWithLoopPhiAdjustment(HEnvironment* env, 914 HBasicBlock* loop_header) { 915 DCHECK(loop_header->IsLoopHeader()); 916 for (size_t i = 0; i < env->Size(); i++) { 917 HInstruction* instruction = env->GetInstructionAt(i); 918 SetRawEnvAt(i, instruction); 919 if (instruction == nullptr) { 920 continue; 921 } 922 if (instruction->IsLoopHeaderPhi() && (instruction->GetBlock() == loop_header)) { 923 // At the end of the loop pre-header, the corresponding value for instruction 924 // is the first input of the phi. 925 HInstruction* initial = instruction->AsPhi()->InputAt(0); 926 SetRawEnvAt(i, initial); 927 initial->AddEnvUseAt(this, i); 928 } else { 929 instruction->AddEnvUseAt(this, i); 930 } 931 } 932} 933 934void HEnvironment::RemoveAsUserOfInput(size_t index) const { 935 const HUserRecord<HEnvironment*>& env_use = vregs_[index]; 936 HInstruction* user = env_use.GetInstruction(); 937 auto before_env_use_node = env_use.GetBeforeUseNode(); 938 user->env_uses_.erase_after(before_env_use_node); 939 user->FixUpUserRecordsAfterEnvUseRemoval(before_env_use_node); 940} 941 942HInstruction::InstructionKind HInstruction::GetKind() const { 943 return GetKindInternal(); 944} 945 946HInstruction* HInstruction::GetNextDisregardingMoves() const { 947 HInstruction* next = GetNext(); 948 while (next != nullptr && next->IsParallelMove()) { 949 next = next->GetNext(); 950 } 951 return next; 952} 953 954HInstruction* HInstruction::GetPreviousDisregardingMoves() const { 955 HInstruction* previous = GetPrevious(); 956 while (previous != nullptr && previous->IsParallelMove()) { 957 previous = previous->GetPrevious(); 958 } 959 return previous; 960} 961 962void HInstructionList::AddInstruction(HInstruction* instruction) { 963 if (first_instruction_ == nullptr) { 964 DCHECK(last_instruction_ == nullptr); 965 first_instruction_ = last_instruction_ = instruction; 966 } else { 967 last_instruction_->next_ = instruction; 968 instruction->previous_ = last_instruction_; 969 last_instruction_ = instruction; 970 } 971} 972 973void HInstructionList::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { 974 DCHECK(Contains(cursor)); 975 if (cursor == first_instruction_) { 976 cursor->previous_ = instruction; 977 instruction->next_ = cursor; 978 first_instruction_ = instruction; 979 } else { 980 instruction->previous_ = cursor->previous_; 981 instruction->next_ = cursor; 982 cursor->previous_ = instruction; 983 instruction->previous_->next_ = instruction; 984 } 985} 986 987void HInstructionList::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) { 988 DCHECK(Contains(cursor)); 989 if (cursor == last_instruction_) { 990 cursor->next_ = instruction; 991 instruction->previous_ = cursor; 992 last_instruction_ = instruction; 993 } else { 994 instruction->next_ = cursor->next_; 995 instruction->previous_ = cursor; 996 cursor->next_ = instruction; 997 instruction->next_->previous_ = instruction; 998 } 999} 1000 1001void HInstructionList::RemoveInstruction(HInstruction* instruction) { 1002 if (instruction->previous_ != nullptr) { 1003 instruction->previous_->next_ = instruction->next_; 1004 } 1005 if (instruction->next_ != nullptr) { 1006 instruction->next_->previous_ = instruction->previous_; 1007 } 1008 if (instruction == first_instruction_) { 1009 first_instruction_ = instruction->next_; 1010 } 1011 if (instruction == last_instruction_) { 1012 last_instruction_ = instruction->previous_; 1013 } 1014} 1015 1016bool HInstructionList::Contains(HInstruction* instruction) const { 1017 for (HInstructionIterator it(*this); !it.Done(); it.Advance()) { 1018 if (it.Current() == instruction) { 1019 return true; 1020 } 1021 } 1022 return false; 1023} 1024 1025bool HInstructionList::FoundBefore(const HInstruction* instruction1, 1026 const HInstruction* instruction2) const { 1027 DCHECK_EQ(instruction1->GetBlock(), instruction2->GetBlock()); 1028 for (HInstructionIterator it(*this); !it.Done(); it.Advance()) { 1029 if (it.Current() == instruction1) { 1030 return true; 1031 } 1032 if (it.Current() == instruction2) { 1033 return false; 1034 } 1035 } 1036 LOG(FATAL) << "Did not find an order between two instructions of the same block."; 1037 return true; 1038} 1039 1040bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const { 1041 if (other_instruction == this) { 1042 // An instruction does not strictly dominate itself. 1043 return false; 1044 } 1045 HBasicBlock* block = GetBlock(); 1046 HBasicBlock* other_block = other_instruction->GetBlock(); 1047 if (block != other_block) { 1048 return GetBlock()->Dominates(other_instruction->GetBlock()); 1049 } else { 1050 // If both instructions are in the same block, ensure this 1051 // instruction comes before `other_instruction`. 1052 if (IsPhi()) { 1053 if (!other_instruction->IsPhi()) { 1054 // Phis appear before non phi-instructions so this instruction 1055 // dominates `other_instruction`. 1056 return true; 1057 } else { 1058 // There is no order among phis. 1059 LOG(FATAL) << "There is no dominance between phis of a same block."; 1060 return false; 1061 } 1062 } else { 1063 // `this` is not a phi. 1064 if (other_instruction->IsPhi()) { 1065 // Phis appear before non phi-instructions so this instruction 1066 // does not dominate `other_instruction`. 1067 return false; 1068 } else { 1069 // Check whether this instruction comes before 1070 // `other_instruction` in the instruction list. 1071 return block->GetInstructions().FoundBefore(this, other_instruction); 1072 } 1073 } 1074 } 1075} 1076 1077void HInstruction::RemoveEnvironment() { 1078 RemoveEnvironmentUses(this); 1079 environment_ = nullptr; 1080} 1081 1082void HInstruction::ReplaceWith(HInstruction* other) { 1083 DCHECK(other != nullptr); 1084 // Note: fixup_end remains valid across splice_after(). 1085 auto fixup_end = other->uses_.empty() ? other->uses_.begin() : ++other->uses_.begin(); 1086 other->uses_.splice_after(other->uses_.before_begin(), uses_); 1087 other->FixUpUserRecordsAfterUseInsertion(fixup_end); 1088 1089 // Note: env_fixup_end remains valid across splice_after(). 1090 auto env_fixup_end = 1091 other->env_uses_.empty() ? other->env_uses_.begin() : ++other->env_uses_.begin(); 1092 other->env_uses_.splice_after(other->env_uses_.before_begin(), env_uses_); 1093 other->FixUpUserRecordsAfterEnvUseInsertion(env_fixup_end); 1094 1095 DCHECK(uses_.empty()); 1096 DCHECK(env_uses_.empty()); 1097} 1098 1099void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) { 1100 HUserRecord<HInstruction*> input_use = InputRecordAt(index); 1101 if (input_use.GetInstruction() == replacement) { 1102 // Nothing to do. 1103 return; 1104 } 1105 HUseList<HInstruction*>::iterator before_use_node = input_use.GetBeforeUseNode(); 1106 // Note: fixup_end remains valid across splice_after(). 1107 auto fixup_end = 1108 replacement->uses_.empty() ? replacement->uses_.begin() : ++replacement->uses_.begin(); 1109 replacement->uses_.splice_after(replacement->uses_.before_begin(), 1110 input_use.GetInstruction()->uses_, 1111 before_use_node); 1112 replacement->FixUpUserRecordsAfterUseInsertion(fixup_end); 1113 input_use.GetInstruction()->FixUpUserRecordsAfterUseRemoval(before_use_node); 1114} 1115 1116size_t HInstruction::EnvironmentSize() const { 1117 return HasEnvironment() ? environment_->Size() : 0; 1118} 1119 1120void HPhi::AddInput(HInstruction* input) { 1121 DCHECK(input->GetBlock() != nullptr); 1122 inputs_.push_back(HUserRecord<HInstruction*>(input)); 1123 input->AddUseAt(this, inputs_.size() - 1); 1124} 1125 1126void HPhi::RemoveInputAt(size_t index) { 1127 RemoveAsUserOfInput(index); 1128 inputs_.erase(inputs_.begin() + index); 1129 for (size_t i = index, e = InputCount(); i < e; ++i) { 1130 DCHECK_EQ(InputRecordAt(i).GetUseNode()->GetIndex(), i + 1u); 1131 InputRecordAt(i).GetUseNode()->SetIndex(i); 1132 } 1133} 1134 1135#define DEFINE_ACCEPT(name, super) \ 1136void H##name::Accept(HGraphVisitor* visitor) { \ 1137 visitor->Visit##name(this); \ 1138} 1139 1140FOR_EACH_CONCRETE_INSTRUCTION(DEFINE_ACCEPT) 1141 1142#undef DEFINE_ACCEPT 1143 1144void HGraphVisitor::VisitInsertionOrder() { 1145 const ArenaVector<HBasicBlock*>& blocks = graph_->GetBlocks(); 1146 for (HBasicBlock* block : blocks) { 1147 if (block != nullptr) { 1148 VisitBasicBlock(block); 1149 } 1150 } 1151} 1152 1153void HGraphVisitor::VisitReversePostOrder() { 1154 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 1155 VisitBasicBlock(it.Current()); 1156 } 1157} 1158 1159void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) { 1160 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 1161 it.Current()->Accept(this); 1162 } 1163 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 1164 it.Current()->Accept(this); 1165 } 1166} 1167 1168HConstant* HTypeConversion::TryStaticEvaluation() const { 1169 HGraph* graph = GetBlock()->GetGraph(); 1170 if (GetInput()->IsIntConstant()) { 1171 int32_t value = GetInput()->AsIntConstant()->GetValue(); 1172 switch (GetResultType()) { 1173 case Primitive::kPrimLong: 1174 return graph->GetLongConstant(static_cast<int64_t>(value), GetDexPc()); 1175 case Primitive::kPrimFloat: 1176 return graph->GetFloatConstant(static_cast<float>(value), GetDexPc()); 1177 case Primitive::kPrimDouble: 1178 return graph->GetDoubleConstant(static_cast<double>(value), GetDexPc()); 1179 default: 1180 return nullptr; 1181 } 1182 } else if (GetInput()->IsLongConstant()) { 1183 int64_t value = GetInput()->AsLongConstant()->GetValue(); 1184 switch (GetResultType()) { 1185 case Primitive::kPrimInt: 1186 return graph->GetIntConstant(static_cast<int32_t>(value), GetDexPc()); 1187 case Primitive::kPrimFloat: 1188 return graph->GetFloatConstant(static_cast<float>(value), GetDexPc()); 1189 case Primitive::kPrimDouble: 1190 return graph->GetDoubleConstant(static_cast<double>(value), GetDexPc()); 1191 default: 1192 return nullptr; 1193 } 1194 } else if (GetInput()->IsFloatConstant()) { 1195 float value = GetInput()->AsFloatConstant()->GetValue(); 1196 switch (GetResultType()) { 1197 case Primitive::kPrimInt: 1198 if (std::isnan(value)) 1199 return graph->GetIntConstant(0, GetDexPc()); 1200 if (value >= kPrimIntMax) 1201 return graph->GetIntConstant(kPrimIntMax, GetDexPc()); 1202 if (value <= kPrimIntMin) 1203 return graph->GetIntConstant(kPrimIntMin, GetDexPc()); 1204 return graph->GetIntConstant(static_cast<int32_t>(value), GetDexPc()); 1205 case Primitive::kPrimLong: 1206 if (std::isnan(value)) 1207 return graph->GetLongConstant(0, GetDexPc()); 1208 if (value >= kPrimLongMax) 1209 return graph->GetLongConstant(kPrimLongMax, GetDexPc()); 1210 if (value <= kPrimLongMin) 1211 return graph->GetLongConstant(kPrimLongMin, GetDexPc()); 1212 return graph->GetLongConstant(static_cast<int64_t>(value), GetDexPc()); 1213 case Primitive::kPrimDouble: 1214 return graph->GetDoubleConstant(static_cast<double>(value), GetDexPc()); 1215 default: 1216 return nullptr; 1217 } 1218 } else if (GetInput()->IsDoubleConstant()) { 1219 double value = GetInput()->AsDoubleConstant()->GetValue(); 1220 switch (GetResultType()) { 1221 case Primitive::kPrimInt: 1222 if (std::isnan(value)) 1223 return graph->GetIntConstant(0, GetDexPc()); 1224 if (value >= kPrimIntMax) 1225 return graph->GetIntConstant(kPrimIntMax, GetDexPc()); 1226 if (value <= kPrimLongMin) 1227 return graph->GetIntConstant(kPrimIntMin, GetDexPc()); 1228 return graph->GetIntConstant(static_cast<int32_t>(value), GetDexPc()); 1229 case Primitive::kPrimLong: 1230 if (std::isnan(value)) 1231 return graph->GetLongConstant(0, GetDexPc()); 1232 if (value >= kPrimLongMax) 1233 return graph->GetLongConstant(kPrimLongMax, GetDexPc()); 1234 if (value <= kPrimLongMin) 1235 return graph->GetLongConstant(kPrimLongMin, GetDexPc()); 1236 return graph->GetLongConstant(static_cast<int64_t>(value), GetDexPc()); 1237 case Primitive::kPrimFloat: 1238 return graph->GetFloatConstant(static_cast<float>(value), GetDexPc()); 1239 default: 1240 return nullptr; 1241 } 1242 } 1243 return nullptr; 1244} 1245 1246HConstant* HUnaryOperation::TryStaticEvaluation() const { 1247 if (GetInput()->IsIntConstant()) { 1248 return Evaluate(GetInput()->AsIntConstant()); 1249 } else if (GetInput()->IsLongConstant()) { 1250 return Evaluate(GetInput()->AsLongConstant()); 1251 } else if (kEnableFloatingPointStaticEvaluation) { 1252 if (GetInput()->IsFloatConstant()) { 1253 return Evaluate(GetInput()->AsFloatConstant()); 1254 } else if (GetInput()->IsDoubleConstant()) { 1255 return Evaluate(GetInput()->AsDoubleConstant()); 1256 } 1257 } 1258 return nullptr; 1259} 1260 1261HConstant* HBinaryOperation::TryStaticEvaluation() const { 1262 if (GetLeft()->IsIntConstant() && GetRight()->IsIntConstant()) { 1263 return Evaluate(GetLeft()->AsIntConstant(), GetRight()->AsIntConstant()); 1264 } else if (GetLeft()->IsLongConstant()) { 1265 if (GetRight()->IsIntConstant()) { 1266 // The binop(long, int) case is only valid for shifts and rotations. 1267 DCHECK(IsShl() || IsShr() || IsUShr() || IsRor()) << DebugName(); 1268 return Evaluate(GetLeft()->AsLongConstant(), GetRight()->AsIntConstant()); 1269 } else if (GetRight()->IsLongConstant()) { 1270 return Evaluate(GetLeft()->AsLongConstant(), GetRight()->AsLongConstant()); 1271 } 1272 } else if (GetLeft()->IsNullConstant() && GetRight()->IsNullConstant()) { 1273 // The binop(null, null) case is only valid for equal and not-equal conditions. 1274 DCHECK(IsEqual() || IsNotEqual()) << DebugName(); 1275 return Evaluate(GetLeft()->AsNullConstant(), GetRight()->AsNullConstant()); 1276 } else if (kEnableFloatingPointStaticEvaluation) { 1277 if (GetLeft()->IsFloatConstant() && GetRight()->IsFloatConstant()) { 1278 return Evaluate(GetLeft()->AsFloatConstant(), GetRight()->AsFloatConstant()); 1279 } else if (GetLeft()->IsDoubleConstant() && GetRight()->IsDoubleConstant()) { 1280 return Evaluate(GetLeft()->AsDoubleConstant(), GetRight()->AsDoubleConstant()); 1281 } 1282 } 1283 return nullptr; 1284} 1285 1286HConstant* HBinaryOperation::GetConstantRight() const { 1287 if (GetRight()->IsConstant()) { 1288 return GetRight()->AsConstant(); 1289 } else if (IsCommutative() && GetLeft()->IsConstant()) { 1290 return GetLeft()->AsConstant(); 1291 } else { 1292 return nullptr; 1293 } 1294} 1295 1296// If `GetConstantRight()` returns one of the input, this returns the other 1297// one. Otherwise it returns null. 1298HInstruction* HBinaryOperation::GetLeastConstantLeft() const { 1299 HInstruction* most_constant_right = GetConstantRight(); 1300 if (most_constant_right == nullptr) { 1301 return nullptr; 1302 } else if (most_constant_right == GetLeft()) { 1303 return GetRight(); 1304 } else { 1305 return GetLeft(); 1306 } 1307} 1308 1309std::ostream& operator<<(std::ostream& os, const ComparisonBias& rhs) { 1310 switch (rhs) { 1311 case ComparisonBias::kNoBias: 1312 return os << "no_bias"; 1313 case ComparisonBias::kGtBias: 1314 return os << "gt_bias"; 1315 case ComparisonBias::kLtBias: 1316 return os << "lt_bias"; 1317 default: 1318 LOG(FATAL) << "Unknown ComparisonBias: " << static_cast<int>(rhs); 1319 UNREACHABLE(); 1320 } 1321} 1322 1323bool HCondition::IsBeforeWhenDisregardMoves(HInstruction* instruction) const { 1324 return this == instruction->GetPreviousDisregardingMoves(); 1325} 1326 1327bool HInstruction::Equals(HInstruction* other) const { 1328 if (!InstructionTypeEquals(other)) return false; 1329 DCHECK_EQ(GetKind(), other->GetKind()); 1330 if (!InstructionDataEquals(other)) return false; 1331 if (GetType() != other->GetType()) return false; 1332 if (InputCount() != other->InputCount()) return false; 1333 1334 for (size_t i = 0, e = InputCount(); i < e; ++i) { 1335 if (InputAt(i) != other->InputAt(i)) return false; 1336 } 1337 DCHECK_EQ(ComputeHashCode(), other->ComputeHashCode()); 1338 return true; 1339} 1340 1341std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs) { 1342#define DECLARE_CASE(type, super) case HInstruction::k##type: os << #type; break; 1343 switch (rhs) { 1344 FOR_EACH_INSTRUCTION(DECLARE_CASE) 1345 default: 1346 os << "Unknown instruction kind " << static_cast<int>(rhs); 1347 break; 1348 } 1349#undef DECLARE_CASE 1350 return os; 1351} 1352 1353void HInstruction::MoveBefore(HInstruction* cursor) { 1354 next_->previous_ = previous_; 1355 if (previous_ != nullptr) { 1356 previous_->next_ = next_; 1357 } 1358 if (block_->instructions_.first_instruction_ == this) { 1359 block_->instructions_.first_instruction_ = next_; 1360 } 1361 DCHECK_NE(block_->instructions_.last_instruction_, this); 1362 1363 previous_ = cursor->previous_; 1364 if (previous_ != nullptr) { 1365 previous_->next_ = this; 1366 } 1367 next_ = cursor; 1368 cursor->previous_ = this; 1369 block_ = cursor->block_; 1370 1371 if (block_->instructions_.first_instruction_ == cursor) { 1372 block_->instructions_.first_instruction_ = this; 1373 } 1374} 1375 1376void HInstruction::MoveBeforeFirstUserAndOutOfLoops() { 1377 DCHECK(!CanThrow()); 1378 DCHECK(!HasSideEffects()); 1379 DCHECK(!HasEnvironmentUses()); 1380 DCHECK(HasNonEnvironmentUses()); 1381 DCHECK(!IsPhi()); // Makes no sense for Phi. 1382 DCHECK_EQ(InputCount(), 0u); 1383 1384 // Find the target block. 1385 auto uses_it = GetUses().begin(); 1386 auto uses_end = GetUses().end(); 1387 HBasicBlock* target_block = uses_it->GetUser()->GetBlock(); 1388 ++uses_it; 1389 while (uses_it != uses_end && uses_it->GetUser()->GetBlock() == target_block) { 1390 ++uses_it; 1391 } 1392 if (uses_it != uses_end) { 1393 // This instruction has uses in two or more blocks. Find the common dominator. 1394 CommonDominator finder(target_block); 1395 for (; uses_it != uses_end; ++uses_it) { 1396 finder.Update(uses_it->GetUser()->GetBlock()); 1397 } 1398 target_block = finder.Get(); 1399 DCHECK(target_block != nullptr); 1400 } 1401 // Move to the first dominator not in a loop. 1402 while (target_block->IsInLoop()) { 1403 target_block = target_block->GetDominator(); 1404 DCHECK(target_block != nullptr); 1405 } 1406 1407 // Find insertion position. 1408 HInstruction* insert_pos = nullptr; 1409 for (const HUseListNode<HInstruction*>& use : GetUses()) { 1410 if (use.GetUser()->GetBlock() == target_block && 1411 (insert_pos == nullptr || use.GetUser()->StrictlyDominates(insert_pos))) { 1412 insert_pos = use.GetUser(); 1413 } 1414 } 1415 if (insert_pos == nullptr) { 1416 // No user in `target_block`, insert before the control flow instruction. 1417 insert_pos = target_block->GetLastInstruction(); 1418 DCHECK(insert_pos->IsControlFlow()); 1419 // Avoid splitting HCondition from HIf to prevent unnecessary materialization. 1420 if (insert_pos->IsIf()) { 1421 HInstruction* if_input = insert_pos->AsIf()->InputAt(0); 1422 if (if_input == insert_pos->GetPrevious()) { 1423 insert_pos = if_input; 1424 } 1425 } 1426 } 1427 MoveBefore(insert_pos); 1428} 1429 1430HBasicBlock* HBasicBlock::SplitBefore(HInstruction* cursor) { 1431 DCHECK(!graph_->IsInSsaForm()) << "Support for SSA form not implemented."; 1432 DCHECK_EQ(cursor->GetBlock(), this); 1433 1434 HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), 1435 cursor->GetDexPc()); 1436 new_block->instructions_.first_instruction_ = cursor; 1437 new_block->instructions_.last_instruction_ = instructions_.last_instruction_; 1438 instructions_.last_instruction_ = cursor->previous_; 1439 if (cursor->previous_ == nullptr) { 1440 instructions_.first_instruction_ = nullptr; 1441 } else { 1442 cursor->previous_->next_ = nullptr; 1443 cursor->previous_ = nullptr; 1444 } 1445 1446 new_block->instructions_.SetBlockOfInstructions(new_block); 1447 AddInstruction(new (GetGraph()->GetArena()) HGoto(new_block->GetDexPc())); 1448 1449 for (HBasicBlock* successor : GetSuccessors()) { 1450 new_block->successors_.push_back(successor); 1451 successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block; 1452 } 1453 successors_.clear(); 1454 AddSuccessor(new_block); 1455 1456 GetGraph()->AddBlock(new_block); 1457 return new_block; 1458} 1459 1460HBasicBlock* HBasicBlock::CreateImmediateDominator() { 1461 DCHECK(!graph_->IsInSsaForm()) << "Support for SSA form not implemented."; 1462 DCHECK(!IsCatchBlock()) << "Support for updating try/catch information not implemented."; 1463 1464 HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), GetDexPc()); 1465 1466 for (HBasicBlock* predecessor : GetPredecessors()) { 1467 new_block->predecessors_.push_back(predecessor); 1468 predecessor->successors_[predecessor->GetSuccessorIndexOf(this)] = new_block; 1469 } 1470 predecessors_.clear(); 1471 AddPredecessor(new_block); 1472 1473 GetGraph()->AddBlock(new_block); 1474 return new_block; 1475} 1476 1477HBasicBlock* HBasicBlock::SplitBeforeForInlining(HInstruction* cursor) { 1478 DCHECK_EQ(cursor->GetBlock(), this); 1479 1480 HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), 1481 cursor->GetDexPc()); 1482 new_block->instructions_.first_instruction_ = cursor; 1483 new_block->instructions_.last_instruction_ = instructions_.last_instruction_; 1484 instructions_.last_instruction_ = cursor->previous_; 1485 if (cursor->previous_ == nullptr) { 1486 instructions_.first_instruction_ = nullptr; 1487 } else { 1488 cursor->previous_->next_ = nullptr; 1489 cursor->previous_ = nullptr; 1490 } 1491 1492 new_block->instructions_.SetBlockOfInstructions(new_block); 1493 1494 for (HBasicBlock* successor : GetSuccessors()) { 1495 new_block->successors_.push_back(successor); 1496 successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block; 1497 } 1498 successors_.clear(); 1499 1500 for (HBasicBlock* dominated : GetDominatedBlocks()) { 1501 dominated->dominator_ = new_block; 1502 new_block->dominated_blocks_.push_back(dominated); 1503 } 1504 dominated_blocks_.clear(); 1505 return new_block; 1506} 1507 1508HBasicBlock* HBasicBlock::SplitAfterForInlining(HInstruction* cursor) { 1509 DCHECK(!cursor->IsControlFlow()); 1510 DCHECK_NE(instructions_.last_instruction_, cursor); 1511 DCHECK_EQ(cursor->GetBlock(), this); 1512 1513 HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), GetDexPc()); 1514 new_block->instructions_.first_instruction_ = cursor->GetNext(); 1515 new_block->instructions_.last_instruction_ = instructions_.last_instruction_; 1516 cursor->next_->previous_ = nullptr; 1517 cursor->next_ = nullptr; 1518 instructions_.last_instruction_ = cursor; 1519 1520 new_block->instructions_.SetBlockOfInstructions(new_block); 1521 for (HBasicBlock* successor : GetSuccessors()) { 1522 new_block->successors_.push_back(successor); 1523 successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block; 1524 } 1525 successors_.clear(); 1526 1527 for (HBasicBlock* dominated : GetDominatedBlocks()) { 1528 dominated->dominator_ = new_block; 1529 new_block->dominated_blocks_.push_back(dominated); 1530 } 1531 dominated_blocks_.clear(); 1532 return new_block; 1533} 1534 1535const HTryBoundary* HBasicBlock::ComputeTryEntryOfSuccessors() const { 1536 if (EndsWithTryBoundary()) { 1537 HTryBoundary* try_boundary = GetLastInstruction()->AsTryBoundary(); 1538 if (try_boundary->IsEntry()) { 1539 DCHECK(!IsTryBlock()); 1540 return try_boundary; 1541 } else { 1542 DCHECK(IsTryBlock()); 1543 DCHECK(try_catch_information_->GetTryEntry().HasSameExceptionHandlersAs(*try_boundary)); 1544 return nullptr; 1545 } 1546 } else if (IsTryBlock()) { 1547 return &try_catch_information_->GetTryEntry(); 1548 } else { 1549 return nullptr; 1550 } 1551} 1552 1553bool HBasicBlock::HasThrowingInstructions() const { 1554 for (HInstructionIterator it(GetInstructions()); !it.Done(); it.Advance()) { 1555 if (it.Current()->CanThrow()) { 1556 return true; 1557 } 1558 } 1559 return false; 1560} 1561 1562static bool HasOnlyOneInstruction(const HBasicBlock& block) { 1563 return block.GetPhis().IsEmpty() 1564 && !block.GetInstructions().IsEmpty() 1565 && block.GetFirstInstruction() == block.GetLastInstruction(); 1566} 1567 1568bool HBasicBlock::IsSingleGoto() const { 1569 return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsGoto(); 1570} 1571 1572bool HBasicBlock::IsSingleTryBoundary() const { 1573 return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsTryBoundary(); 1574} 1575 1576bool HBasicBlock::EndsWithControlFlowInstruction() const { 1577 return !GetInstructions().IsEmpty() && GetLastInstruction()->IsControlFlow(); 1578} 1579 1580bool HBasicBlock::EndsWithIf() const { 1581 return !GetInstructions().IsEmpty() && GetLastInstruction()->IsIf(); 1582} 1583 1584bool HBasicBlock::EndsWithTryBoundary() const { 1585 return !GetInstructions().IsEmpty() && GetLastInstruction()->IsTryBoundary(); 1586} 1587 1588bool HBasicBlock::HasSinglePhi() const { 1589 return !GetPhis().IsEmpty() && GetFirstPhi()->GetNext() == nullptr; 1590} 1591 1592ArrayRef<HBasicBlock* const> HBasicBlock::GetNormalSuccessors() const { 1593 if (EndsWithTryBoundary()) { 1594 // The normal-flow successor of HTryBoundary is always stored at index zero. 1595 DCHECK_EQ(successors_[0], GetLastInstruction()->AsTryBoundary()->GetNormalFlowSuccessor()); 1596 return ArrayRef<HBasicBlock* const>(successors_).SubArray(0u, 1u); 1597 } else { 1598 // All successors of blocks not ending with TryBoundary are normal. 1599 return ArrayRef<HBasicBlock* const>(successors_); 1600 } 1601} 1602 1603ArrayRef<HBasicBlock* const> HBasicBlock::GetExceptionalSuccessors() const { 1604 if (EndsWithTryBoundary()) { 1605 return GetLastInstruction()->AsTryBoundary()->GetExceptionHandlers(); 1606 } else { 1607 // Blocks not ending with TryBoundary do not have exceptional successors. 1608 return ArrayRef<HBasicBlock* const>(); 1609 } 1610} 1611 1612bool HTryBoundary::HasSameExceptionHandlersAs(const HTryBoundary& other) const { 1613 ArrayRef<HBasicBlock* const> handlers1 = GetExceptionHandlers(); 1614 ArrayRef<HBasicBlock* const> handlers2 = other.GetExceptionHandlers(); 1615 1616 size_t length = handlers1.size(); 1617 if (length != handlers2.size()) { 1618 return false; 1619 } 1620 1621 // Exception handlers need to be stored in the same order. 1622 for (size_t i = 0; i < length; ++i) { 1623 if (handlers1[i] != handlers2[i]) { 1624 return false; 1625 } 1626 } 1627 return true; 1628} 1629 1630size_t HInstructionList::CountSize() const { 1631 size_t size = 0; 1632 HInstruction* current = first_instruction_; 1633 for (; current != nullptr; current = current->GetNext()) { 1634 size++; 1635 } 1636 return size; 1637} 1638 1639void HInstructionList::SetBlockOfInstructions(HBasicBlock* block) const { 1640 for (HInstruction* current = first_instruction_; 1641 current != nullptr; 1642 current = current->GetNext()) { 1643 current->SetBlock(block); 1644 } 1645} 1646 1647void HInstructionList::AddAfter(HInstruction* cursor, const HInstructionList& instruction_list) { 1648 DCHECK(Contains(cursor)); 1649 if (!instruction_list.IsEmpty()) { 1650 if (cursor == last_instruction_) { 1651 last_instruction_ = instruction_list.last_instruction_; 1652 } else { 1653 cursor->next_->previous_ = instruction_list.last_instruction_; 1654 } 1655 instruction_list.last_instruction_->next_ = cursor->next_; 1656 cursor->next_ = instruction_list.first_instruction_; 1657 instruction_list.first_instruction_->previous_ = cursor; 1658 } 1659} 1660 1661void HInstructionList::AddBefore(HInstruction* cursor, const HInstructionList& instruction_list) { 1662 DCHECK(Contains(cursor)); 1663 if (!instruction_list.IsEmpty()) { 1664 if (cursor == first_instruction_) { 1665 first_instruction_ = instruction_list.first_instruction_; 1666 } else { 1667 cursor->previous_->next_ = instruction_list.first_instruction_; 1668 } 1669 instruction_list.last_instruction_->next_ = cursor; 1670 instruction_list.first_instruction_->previous_ = cursor->previous_; 1671 cursor->previous_ = instruction_list.last_instruction_; 1672 } 1673} 1674 1675void HInstructionList::Add(const HInstructionList& instruction_list) { 1676 if (IsEmpty()) { 1677 first_instruction_ = instruction_list.first_instruction_; 1678 last_instruction_ = instruction_list.last_instruction_; 1679 } else { 1680 AddAfter(last_instruction_, instruction_list); 1681 } 1682} 1683 1684// Should be called on instructions in a dead block in post order. This method 1685// assumes `insn` has been removed from all users with the exception of catch 1686// phis because of missing exceptional edges in the graph. It removes the 1687// instruction from catch phi uses, together with inputs of other catch phis in 1688// the catch block at the same index, as these must be dead too. 1689static void RemoveUsesOfDeadInstruction(HInstruction* insn) { 1690 DCHECK(!insn->HasEnvironmentUses()); 1691 while (insn->HasNonEnvironmentUses()) { 1692 const HUseListNode<HInstruction*>& use = insn->GetUses().front(); 1693 size_t use_index = use.GetIndex(); 1694 HBasicBlock* user_block = use.GetUser()->GetBlock(); 1695 DCHECK(use.GetUser()->IsPhi() && user_block->IsCatchBlock()); 1696 for (HInstructionIterator phi_it(user_block->GetPhis()); !phi_it.Done(); phi_it.Advance()) { 1697 phi_it.Current()->AsPhi()->RemoveInputAt(use_index); 1698 } 1699 } 1700} 1701 1702void HBasicBlock::DisconnectAndDelete() { 1703 // Dominators must be removed after all the blocks they dominate. This way 1704 // a loop header is removed last, a requirement for correct loop information 1705 // iteration. 1706 DCHECK(dominated_blocks_.empty()); 1707 1708 // The following steps gradually remove the block from all its dependants in 1709 // post order (b/27683071). 1710 1711 // (1) Store a basic block that we'll use in step (5) to find loops to be updated. 1712 // We need to do this before step (4) which destroys the predecessor list. 1713 HBasicBlock* loop_update_start = this; 1714 if (IsLoopHeader()) { 1715 HLoopInformation* loop_info = GetLoopInformation(); 1716 // All other blocks in this loop should have been removed because the header 1717 // was their dominator. 1718 // Note that we do not remove `this` from `loop_info` as it is unreachable. 1719 DCHECK(!loop_info->IsIrreducible()); 1720 DCHECK_EQ(loop_info->GetBlocks().NumSetBits(), 1u); 1721 DCHECK_EQ(static_cast<uint32_t>(loop_info->GetBlocks().GetHighestBitSet()), GetBlockId()); 1722 loop_update_start = loop_info->GetPreHeader(); 1723 } 1724 1725 // (2) Disconnect the block from its successors and update their phis. 1726 for (HBasicBlock* successor : successors_) { 1727 // Delete this block from the list of predecessors. 1728 size_t this_index = successor->GetPredecessorIndexOf(this); 1729 successor->predecessors_.erase(successor->predecessors_.begin() + this_index); 1730 1731 // Check that `successor` has other predecessors, otherwise `this` is the 1732 // dominator of `successor` which violates the order DCHECKed at the top. 1733 DCHECK(!successor->predecessors_.empty()); 1734 1735 // Remove this block's entries in the successor's phis. Skip exceptional 1736 // successors because catch phi inputs do not correspond to predecessor 1737 // blocks but throwing instructions. The inputs of the catch phis will be 1738 // updated in step (3). 1739 if (!successor->IsCatchBlock()) { 1740 if (successor->predecessors_.size() == 1u) { 1741 // The successor has just one predecessor left. Replace phis with the only 1742 // remaining input. 1743 for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) { 1744 HPhi* phi = phi_it.Current()->AsPhi(); 1745 phi->ReplaceWith(phi->InputAt(1 - this_index)); 1746 successor->RemovePhi(phi); 1747 } 1748 } else { 1749 for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) { 1750 phi_it.Current()->AsPhi()->RemoveInputAt(this_index); 1751 } 1752 } 1753 } 1754 } 1755 successors_.clear(); 1756 1757 // (3) Remove instructions and phis. Instructions should have no remaining uses 1758 // except in catch phis. If an instruction is used by a catch phi at `index`, 1759 // remove `index`-th input of all phis in the catch block since they are 1760 // guaranteed dead. Note that we may miss dead inputs this way but the 1761 // graph will always remain consistent. 1762 for (HBackwardInstructionIterator it(GetInstructions()); !it.Done(); it.Advance()) { 1763 HInstruction* insn = it.Current(); 1764 RemoveUsesOfDeadInstruction(insn); 1765 RemoveInstruction(insn); 1766 } 1767 for (HInstructionIterator it(GetPhis()); !it.Done(); it.Advance()) { 1768 HPhi* insn = it.Current()->AsPhi(); 1769 RemoveUsesOfDeadInstruction(insn); 1770 RemovePhi(insn); 1771 } 1772 1773 // (4) Disconnect the block from its predecessors and update their 1774 // control-flow instructions. 1775 for (HBasicBlock* predecessor : predecessors_) { 1776 // We should not see any back edges as they would have been removed by step (3). 1777 DCHECK(!IsInLoop() || !GetLoopInformation()->IsBackEdge(*predecessor)); 1778 1779 HInstruction* last_instruction = predecessor->GetLastInstruction(); 1780 if (last_instruction->IsTryBoundary() && !IsCatchBlock()) { 1781 // This block is the only normal-flow successor of the TryBoundary which 1782 // makes `predecessor` dead. Since DCE removes blocks in post order, 1783 // exception handlers of this TryBoundary were already visited and any 1784 // remaining handlers therefore must be live. We remove `predecessor` from 1785 // their list of predecessors. 1786 DCHECK_EQ(last_instruction->AsTryBoundary()->GetNormalFlowSuccessor(), this); 1787 while (predecessor->GetSuccessors().size() > 1) { 1788 HBasicBlock* handler = predecessor->GetSuccessors()[1]; 1789 DCHECK(handler->IsCatchBlock()); 1790 predecessor->RemoveSuccessor(handler); 1791 handler->RemovePredecessor(predecessor); 1792 } 1793 } 1794 1795 predecessor->RemoveSuccessor(this); 1796 uint32_t num_pred_successors = predecessor->GetSuccessors().size(); 1797 if (num_pred_successors == 1u) { 1798 // If we have one successor after removing one, then we must have 1799 // had an HIf, HPackedSwitch or HTryBoundary, as they have more than one 1800 // successor. Replace those with a HGoto. 1801 DCHECK(last_instruction->IsIf() || 1802 last_instruction->IsPackedSwitch() || 1803 (last_instruction->IsTryBoundary() && IsCatchBlock())); 1804 predecessor->RemoveInstruction(last_instruction); 1805 predecessor->AddInstruction(new (graph_->GetArena()) HGoto(last_instruction->GetDexPc())); 1806 } else if (num_pred_successors == 0u) { 1807 // The predecessor has no remaining successors and therefore must be dead. 1808 // We deliberately leave it without a control-flow instruction so that the 1809 // GraphChecker fails unless it is not removed during the pass too. 1810 predecessor->RemoveInstruction(last_instruction); 1811 } else { 1812 // There are multiple successors left. The removed block might be a successor 1813 // of a PackedSwitch which will be completely removed (perhaps replaced with 1814 // a Goto), or we are deleting a catch block from a TryBoundary. In either 1815 // case, leave `last_instruction` as is for now. 1816 DCHECK(last_instruction->IsPackedSwitch() || 1817 (last_instruction->IsTryBoundary() && IsCatchBlock())); 1818 } 1819 } 1820 predecessors_.clear(); 1821 1822 // (5) Remove the block from all loops it is included in. Skip the inner-most 1823 // loop if this is the loop header (see definition of `loop_update_start`) 1824 // because the loop header's predecessor list has been destroyed in step (4). 1825 for (HLoopInformationOutwardIterator it(*loop_update_start); !it.Done(); it.Advance()) { 1826 HLoopInformation* loop_info = it.Current(); 1827 loop_info->Remove(this); 1828 if (loop_info->IsBackEdge(*this)) { 1829 // If this was the last back edge of the loop, we deliberately leave the 1830 // loop in an inconsistent state and will fail GraphChecker unless the 1831 // entire loop is removed during the pass. 1832 loop_info->RemoveBackEdge(this); 1833 } 1834 } 1835 1836 // (6) Disconnect from the dominator. 1837 dominator_->RemoveDominatedBlock(this); 1838 SetDominator(nullptr); 1839 1840 // (7) Delete from the graph, update reverse post order. 1841 graph_->DeleteDeadEmptyBlock(this); 1842 SetGraph(nullptr); 1843} 1844 1845void HBasicBlock::MergeWith(HBasicBlock* other) { 1846 DCHECK_EQ(GetGraph(), other->GetGraph()); 1847 DCHECK(ContainsElement(dominated_blocks_, other)); 1848 DCHECK_EQ(GetSingleSuccessor(), other); 1849 DCHECK_EQ(other->GetSinglePredecessor(), this); 1850 DCHECK(other->GetPhis().IsEmpty()); 1851 1852 // Move instructions from `other` to `this`. 1853 DCHECK(EndsWithControlFlowInstruction()); 1854 RemoveInstruction(GetLastInstruction()); 1855 instructions_.Add(other->GetInstructions()); 1856 other->instructions_.SetBlockOfInstructions(this); 1857 other->instructions_.Clear(); 1858 1859 // Remove `other` from the loops it is included in. 1860 for (HLoopInformationOutwardIterator it(*other); !it.Done(); it.Advance()) { 1861 HLoopInformation* loop_info = it.Current(); 1862 loop_info->Remove(other); 1863 if (loop_info->IsBackEdge(*other)) { 1864 loop_info->ReplaceBackEdge(other, this); 1865 } 1866 } 1867 1868 // Update links to the successors of `other`. 1869 successors_.clear(); 1870 while (!other->successors_.empty()) { 1871 HBasicBlock* successor = other->GetSuccessors()[0]; 1872 successor->ReplacePredecessor(other, this); 1873 } 1874 1875 // Update the dominator tree. 1876 RemoveDominatedBlock(other); 1877 for (HBasicBlock* dominated : other->GetDominatedBlocks()) { 1878 dominated_blocks_.push_back(dominated); 1879 dominated->SetDominator(this); 1880 } 1881 other->dominated_blocks_.clear(); 1882 other->dominator_ = nullptr; 1883 1884 // Clear the list of predecessors of `other` in preparation of deleting it. 1885 other->predecessors_.clear(); 1886 1887 // Delete `other` from the graph. The function updates reverse post order. 1888 graph_->DeleteDeadEmptyBlock(other); 1889 other->SetGraph(nullptr); 1890} 1891 1892void HBasicBlock::MergeWithInlined(HBasicBlock* other) { 1893 DCHECK_NE(GetGraph(), other->GetGraph()); 1894 DCHECK(GetDominatedBlocks().empty()); 1895 DCHECK(GetSuccessors().empty()); 1896 DCHECK(!EndsWithControlFlowInstruction()); 1897 DCHECK(other->GetSinglePredecessor()->IsEntryBlock()); 1898 DCHECK(other->GetPhis().IsEmpty()); 1899 DCHECK(!other->IsInLoop()); 1900 1901 // Move instructions from `other` to `this`. 1902 instructions_.Add(other->GetInstructions()); 1903 other->instructions_.SetBlockOfInstructions(this); 1904 1905 // Update links to the successors of `other`. 1906 successors_.clear(); 1907 while (!other->successors_.empty()) { 1908 HBasicBlock* successor = other->GetSuccessors()[0]; 1909 successor->ReplacePredecessor(other, this); 1910 } 1911 1912 // Update the dominator tree. 1913 for (HBasicBlock* dominated : other->GetDominatedBlocks()) { 1914 dominated_blocks_.push_back(dominated); 1915 dominated->SetDominator(this); 1916 } 1917 other->dominated_blocks_.clear(); 1918 other->dominator_ = nullptr; 1919 other->graph_ = nullptr; 1920} 1921 1922void HBasicBlock::ReplaceWith(HBasicBlock* other) { 1923 while (!GetPredecessors().empty()) { 1924 HBasicBlock* predecessor = GetPredecessors()[0]; 1925 predecessor->ReplaceSuccessor(this, other); 1926 } 1927 while (!GetSuccessors().empty()) { 1928 HBasicBlock* successor = GetSuccessors()[0]; 1929 successor->ReplacePredecessor(this, other); 1930 } 1931 for (HBasicBlock* dominated : GetDominatedBlocks()) { 1932 other->AddDominatedBlock(dominated); 1933 } 1934 GetDominator()->ReplaceDominatedBlock(this, other); 1935 other->SetDominator(GetDominator()); 1936 dominator_ = nullptr; 1937 graph_ = nullptr; 1938} 1939 1940void HGraph::DeleteDeadEmptyBlock(HBasicBlock* block) { 1941 DCHECK_EQ(block->GetGraph(), this); 1942 DCHECK(block->GetSuccessors().empty()); 1943 DCHECK(block->GetPredecessors().empty()); 1944 DCHECK(block->GetDominatedBlocks().empty()); 1945 DCHECK(block->GetDominator() == nullptr); 1946 DCHECK(block->GetInstructions().IsEmpty()); 1947 DCHECK(block->GetPhis().IsEmpty()); 1948 1949 if (block->IsExitBlock()) { 1950 SetExitBlock(nullptr); 1951 } 1952 1953 RemoveElement(reverse_post_order_, block); 1954 blocks_[block->GetBlockId()] = nullptr; 1955 block->SetGraph(nullptr); 1956} 1957 1958void HGraph::UpdateLoopAndTryInformationOfNewBlock(HBasicBlock* block, 1959 HBasicBlock* reference, 1960 bool replace_if_back_edge) { 1961 if (block->IsLoopHeader()) { 1962 // Clear the information of which blocks are contained in that loop. Since the 1963 // information is stored as a bit vector based on block ids, we have to update 1964 // it, as those block ids were specific to the callee graph and we are now adding 1965 // these blocks to the caller graph. 1966 block->GetLoopInformation()->ClearAllBlocks(); 1967 } 1968 1969 // If not already in a loop, update the loop information. 1970 if (!block->IsInLoop()) { 1971 block->SetLoopInformation(reference->GetLoopInformation()); 1972 } 1973 1974 // If the block is in a loop, update all its outward loops. 1975 HLoopInformation* loop_info = block->GetLoopInformation(); 1976 if (loop_info != nullptr) { 1977 for (HLoopInformationOutwardIterator loop_it(*block); 1978 !loop_it.Done(); 1979 loop_it.Advance()) { 1980 loop_it.Current()->Add(block); 1981 } 1982 if (replace_if_back_edge && loop_info->IsBackEdge(*reference)) { 1983 loop_info->ReplaceBackEdge(reference, block); 1984 } 1985 } 1986 1987 // Copy TryCatchInformation if `reference` is a try block, not if it is a catch block. 1988 TryCatchInformation* try_catch_info = reference->IsTryBlock() 1989 ? reference->GetTryCatchInformation() 1990 : nullptr; 1991 block->SetTryCatchInformation(try_catch_info); 1992} 1993 1994HInstruction* HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { 1995 DCHECK(HasExitBlock()) << "Unimplemented scenario"; 1996 // Update the environments in this graph to have the invoke's environment 1997 // as parent. 1998 { 1999 HReversePostOrderIterator it(*this); 2000 it.Advance(); // Skip the entry block, we do not need to update the entry's suspend check. 2001 for (; !it.Done(); it.Advance()) { 2002 HBasicBlock* block = it.Current(); 2003 for (HInstructionIterator instr_it(block->GetInstructions()); 2004 !instr_it.Done(); 2005 instr_it.Advance()) { 2006 HInstruction* current = instr_it.Current(); 2007 if (current->NeedsEnvironment()) { 2008 DCHECK(current->HasEnvironment()); 2009 current->GetEnvironment()->SetAndCopyParentChain( 2010 outer_graph->GetArena(), invoke->GetEnvironment()); 2011 } 2012 } 2013 } 2014 } 2015 outer_graph->UpdateMaximumNumberOfOutVRegs(GetMaximumNumberOfOutVRegs()); 2016 if (HasBoundsChecks()) { 2017 outer_graph->SetHasBoundsChecks(true); 2018 } 2019 2020 HInstruction* return_value = nullptr; 2021 if (GetBlocks().size() == 3) { 2022 // Simple case of an entry block, a body block, and an exit block. 2023 // Put the body block's instruction into `invoke`'s block. 2024 HBasicBlock* body = GetBlocks()[1]; 2025 DCHECK(GetBlocks()[0]->IsEntryBlock()); 2026 DCHECK(GetBlocks()[2]->IsExitBlock()); 2027 DCHECK(!body->IsExitBlock()); 2028 DCHECK(!body->IsInLoop()); 2029 HInstruction* last = body->GetLastInstruction(); 2030 2031 // Note that we add instructions before the invoke only to simplify polymorphic inlining. 2032 invoke->GetBlock()->instructions_.AddBefore(invoke, body->GetInstructions()); 2033 body->GetInstructions().SetBlockOfInstructions(invoke->GetBlock()); 2034 2035 // Replace the invoke with the return value of the inlined graph. 2036 if (last->IsReturn()) { 2037 return_value = last->InputAt(0); 2038 } else { 2039 DCHECK(last->IsReturnVoid()); 2040 } 2041 2042 invoke->GetBlock()->RemoveInstruction(last); 2043 } else { 2044 // Need to inline multiple blocks. We split `invoke`'s block 2045 // into two blocks, merge the first block of the inlined graph into 2046 // the first half, and replace the exit block of the inlined graph 2047 // with the second half. 2048 ArenaAllocator* allocator = outer_graph->GetArena(); 2049 HBasicBlock* at = invoke->GetBlock(); 2050 // Note that we split before the invoke only to simplify polymorphic inlining. 2051 HBasicBlock* to = at->SplitBeforeForInlining(invoke); 2052 2053 HBasicBlock* first = entry_block_->GetSuccessors()[0]; 2054 DCHECK(!first->IsInLoop()); 2055 at->MergeWithInlined(first); 2056 exit_block_->ReplaceWith(to); 2057 2058 // Update the meta information surrounding blocks: 2059 // (1) the graph they are now in, 2060 // (2) the reverse post order of that graph, 2061 // (3) their potential loop information, inner and outer, 2062 // (4) try block membership. 2063 // Note that we do not need to update catch phi inputs because they 2064 // correspond to the register file of the outer method which the inlinee 2065 // cannot modify. 2066 2067 // We don't add the entry block, the exit block, and the first block, which 2068 // has been merged with `at`. 2069 static constexpr int kNumberOfSkippedBlocksInCallee = 3; 2070 2071 // We add the `to` block. 2072 static constexpr int kNumberOfNewBlocksInCaller = 1; 2073 size_t blocks_added = (reverse_post_order_.size() - kNumberOfSkippedBlocksInCallee) 2074 + kNumberOfNewBlocksInCaller; 2075 2076 // Find the location of `at` in the outer graph's reverse post order. The new 2077 // blocks will be added after it. 2078 size_t index_of_at = IndexOfElement(outer_graph->reverse_post_order_, at); 2079 MakeRoomFor(&outer_graph->reverse_post_order_, blocks_added, index_of_at); 2080 2081 // Do a reverse post order of the blocks in the callee and do (1), (2), (3) 2082 // and (4) to the blocks that apply. 2083 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { 2084 HBasicBlock* current = it.Current(); 2085 if (current != exit_block_ && current != entry_block_ && current != first) { 2086 DCHECK(current->GetTryCatchInformation() == nullptr); 2087 DCHECK(current->GetGraph() == this); 2088 current->SetGraph(outer_graph); 2089 outer_graph->AddBlock(current); 2090 outer_graph->reverse_post_order_[++index_of_at] = current; 2091 UpdateLoopAndTryInformationOfNewBlock(current, at, /* replace_if_back_edge */ false); 2092 } 2093 } 2094 2095 // Do (1), (2), (3) and (4) to `to`. 2096 to->SetGraph(outer_graph); 2097 outer_graph->AddBlock(to); 2098 outer_graph->reverse_post_order_[++index_of_at] = to; 2099 // Only `to` can become a back edge, as the inlined blocks 2100 // are predecessors of `to`. 2101 UpdateLoopAndTryInformationOfNewBlock(to, at, /* replace_if_back_edge */ true); 2102 2103 // Update all predecessors of the exit block (now the `to` block) 2104 // to not `HReturn` but `HGoto` instead. 2105 bool returns_void = to->GetPredecessors()[0]->GetLastInstruction()->IsReturnVoid(); 2106 if (to->GetPredecessors().size() == 1) { 2107 HBasicBlock* predecessor = to->GetPredecessors()[0]; 2108 HInstruction* last = predecessor->GetLastInstruction(); 2109 if (!returns_void) { 2110 return_value = last->InputAt(0); 2111 } 2112 predecessor->AddInstruction(new (allocator) HGoto(last->GetDexPc())); 2113 predecessor->RemoveInstruction(last); 2114 } else { 2115 if (!returns_void) { 2116 // There will be multiple returns. 2117 return_value = new (allocator) HPhi( 2118 allocator, kNoRegNumber, 0, HPhi::ToPhiType(invoke->GetType()), to->GetDexPc()); 2119 to->AddPhi(return_value->AsPhi()); 2120 } 2121 for (HBasicBlock* predecessor : to->GetPredecessors()) { 2122 HInstruction* last = predecessor->GetLastInstruction(); 2123 if (!returns_void) { 2124 DCHECK(last->IsReturn()); 2125 return_value->AsPhi()->AddInput(last->InputAt(0)); 2126 } 2127 predecessor->AddInstruction(new (allocator) HGoto(last->GetDexPc())); 2128 predecessor->RemoveInstruction(last); 2129 } 2130 } 2131 } 2132 2133 // Walk over the entry block and: 2134 // - Move constants from the entry block to the outer_graph's entry block, 2135 // - Replace HParameterValue instructions with their real value. 2136 // - Remove suspend checks, that hold an environment. 2137 // We must do this after the other blocks have been inlined, otherwise ids of 2138 // constants could overlap with the inner graph. 2139 size_t parameter_index = 0; 2140 for (HInstructionIterator it(entry_block_->GetInstructions()); !it.Done(); it.Advance()) { 2141 HInstruction* current = it.Current(); 2142 HInstruction* replacement = nullptr; 2143 if (current->IsNullConstant()) { 2144 replacement = outer_graph->GetNullConstant(current->GetDexPc()); 2145 } else if (current->IsIntConstant()) { 2146 replacement = outer_graph->GetIntConstant( 2147 current->AsIntConstant()->GetValue(), current->GetDexPc()); 2148 } else if (current->IsLongConstant()) { 2149 replacement = outer_graph->GetLongConstant( 2150 current->AsLongConstant()->GetValue(), current->GetDexPc()); 2151 } else if (current->IsFloatConstant()) { 2152 replacement = outer_graph->GetFloatConstant( 2153 current->AsFloatConstant()->GetValue(), current->GetDexPc()); 2154 } else if (current->IsDoubleConstant()) { 2155 replacement = outer_graph->GetDoubleConstant( 2156 current->AsDoubleConstant()->GetValue(), current->GetDexPc()); 2157 } else if (current->IsParameterValue()) { 2158 if (kIsDebugBuild 2159 && invoke->IsInvokeStaticOrDirect() 2160 && invoke->AsInvokeStaticOrDirect()->IsStaticWithExplicitClinitCheck()) { 2161 // Ensure we do not use the last input of `invoke`, as it 2162 // contains a clinit check which is not an actual argument. 2163 size_t last_input_index = invoke->InputCount() - 1; 2164 DCHECK(parameter_index != last_input_index); 2165 } 2166 replacement = invoke->InputAt(parameter_index++); 2167 } else if (current->IsCurrentMethod()) { 2168 replacement = outer_graph->GetCurrentMethod(); 2169 } else { 2170 DCHECK(current->IsGoto() || current->IsSuspendCheck()); 2171 entry_block_->RemoveInstruction(current); 2172 } 2173 if (replacement != nullptr) { 2174 current->ReplaceWith(replacement); 2175 // If the current is the return value then we need to update the latter. 2176 if (current == return_value) { 2177 DCHECK_EQ(entry_block_, return_value->GetBlock()); 2178 return_value = replacement; 2179 } 2180 } 2181 } 2182 2183 return return_value; 2184} 2185 2186/* 2187 * Loop will be transformed to: 2188 * old_pre_header 2189 * | 2190 * if_block 2191 * / \ 2192 * true_block false_block 2193 * \ / 2194 * new_pre_header 2195 * | 2196 * header 2197 */ 2198void HGraph::TransformLoopHeaderForBCE(HBasicBlock* header) { 2199 DCHECK(header->IsLoopHeader()); 2200 HBasicBlock* old_pre_header = header->GetDominator(); 2201 2202 // Need extra block to avoid critical edge. 2203 HBasicBlock* if_block = new (arena_) HBasicBlock(this, header->GetDexPc()); 2204 HBasicBlock* true_block = new (arena_) HBasicBlock(this, header->GetDexPc()); 2205 HBasicBlock* false_block = new (arena_) HBasicBlock(this, header->GetDexPc()); 2206 HBasicBlock* new_pre_header = new (arena_) HBasicBlock(this, header->GetDexPc()); 2207 AddBlock(if_block); 2208 AddBlock(true_block); 2209 AddBlock(false_block); 2210 AddBlock(new_pre_header); 2211 2212 header->ReplacePredecessor(old_pre_header, new_pre_header); 2213 old_pre_header->successors_.clear(); 2214 old_pre_header->dominated_blocks_.clear(); 2215 2216 old_pre_header->AddSuccessor(if_block); 2217 if_block->AddSuccessor(true_block); // True successor 2218 if_block->AddSuccessor(false_block); // False successor 2219 true_block->AddSuccessor(new_pre_header); 2220 false_block->AddSuccessor(new_pre_header); 2221 2222 old_pre_header->dominated_blocks_.push_back(if_block); 2223 if_block->SetDominator(old_pre_header); 2224 if_block->dominated_blocks_.push_back(true_block); 2225 true_block->SetDominator(if_block); 2226 if_block->dominated_blocks_.push_back(false_block); 2227 false_block->SetDominator(if_block); 2228 if_block->dominated_blocks_.push_back(new_pre_header); 2229 new_pre_header->SetDominator(if_block); 2230 new_pre_header->dominated_blocks_.push_back(header); 2231 header->SetDominator(new_pre_header); 2232 2233 // Fix reverse post order. 2234 size_t index_of_header = IndexOfElement(reverse_post_order_, header); 2235 MakeRoomFor(&reverse_post_order_, 4, index_of_header - 1); 2236 reverse_post_order_[index_of_header++] = if_block; 2237 reverse_post_order_[index_of_header++] = true_block; 2238 reverse_post_order_[index_of_header++] = false_block; 2239 reverse_post_order_[index_of_header++] = new_pre_header; 2240 2241 // The pre_header can never be a back edge of a loop. 2242 DCHECK((old_pre_header->GetLoopInformation() == nullptr) || 2243 !old_pre_header->GetLoopInformation()->IsBackEdge(*old_pre_header)); 2244 UpdateLoopAndTryInformationOfNewBlock( 2245 if_block, old_pre_header, /* replace_if_back_edge */ false); 2246 UpdateLoopAndTryInformationOfNewBlock( 2247 true_block, old_pre_header, /* replace_if_back_edge */ false); 2248 UpdateLoopAndTryInformationOfNewBlock( 2249 false_block, old_pre_header, /* replace_if_back_edge */ false); 2250 UpdateLoopAndTryInformationOfNewBlock( 2251 new_pre_header, old_pre_header, /* replace_if_back_edge */ false); 2252} 2253 2254static void CheckAgainstUpperBound(ReferenceTypeInfo rti, ReferenceTypeInfo upper_bound_rti) 2255 SHARED_REQUIRES(Locks::mutator_lock_) { 2256 if (rti.IsValid()) { 2257 DCHECK(upper_bound_rti.IsSupertypeOf(rti)) 2258 << " upper_bound_rti: " << upper_bound_rti 2259 << " rti: " << rti; 2260 DCHECK(!upper_bound_rti.GetTypeHandle()->CannotBeAssignedFromOtherTypes() || rti.IsExact()) 2261 << " upper_bound_rti: " << upper_bound_rti 2262 << " rti: " << rti; 2263 } 2264} 2265 2266void HInstruction::SetReferenceTypeInfo(ReferenceTypeInfo rti) { 2267 if (kIsDebugBuild) { 2268 DCHECK_EQ(GetType(), Primitive::kPrimNot); 2269 ScopedObjectAccess soa(Thread::Current()); 2270 DCHECK(rti.IsValid()) << "Invalid RTI for " << DebugName(); 2271 if (IsBoundType()) { 2272 // Having the test here spares us from making the method virtual just for 2273 // the sake of a DCHECK. 2274 CheckAgainstUpperBound(rti, AsBoundType()->GetUpperBound()); 2275 } 2276 } 2277 reference_type_handle_ = rti.GetTypeHandle(); 2278 SetPackedFlag<kFlagReferenceTypeIsExact>(rti.IsExact()); 2279} 2280 2281void HBoundType::SetUpperBound(const ReferenceTypeInfo& upper_bound, bool can_be_null) { 2282 if (kIsDebugBuild) { 2283 ScopedObjectAccess soa(Thread::Current()); 2284 DCHECK(upper_bound.IsValid()); 2285 DCHECK(!upper_bound_.IsValid()) << "Upper bound should only be set once."; 2286 CheckAgainstUpperBound(GetReferenceTypeInfo(), upper_bound); 2287 } 2288 upper_bound_ = upper_bound; 2289 SetPackedFlag<kFlagUpperCanBeNull>(can_be_null); 2290} 2291 2292ReferenceTypeInfo ReferenceTypeInfo::Create(TypeHandle type_handle, bool is_exact) { 2293 if (kIsDebugBuild) { 2294 ScopedObjectAccess soa(Thread::Current()); 2295 DCHECK(IsValidHandle(type_handle)); 2296 if (!is_exact) { 2297 DCHECK(!type_handle->CannotBeAssignedFromOtherTypes()) 2298 << "Callers of ReferenceTypeInfo::Create should ensure is_exact is properly computed"; 2299 } 2300 } 2301 return ReferenceTypeInfo(type_handle, is_exact); 2302} 2303 2304std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs) { 2305 ScopedObjectAccess soa(Thread::Current()); 2306 os << "[" 2307 << " is_valid=" << rhs.IsValid() 2308 << " type=" << (!rhs.IsValid() ? "?" : PrettyClass(rhs.GetTypeHandle().Get())) 2309 << " is_exact=" << rhs.IsExact() 2310 << " ]"; 2311 return os; 2312} 2313 2314bool HInstruction::HasAnyEnvironmentUseBefore(HInstruction* other) { 2315 // For now, assume that instructions in different blocks may use the 2316 // environment. 2317 // TODO: Use the control flow to decide if this is true. 2318 if (GetBlock() != other->GetBlock()) { 2319 return true; 2320 } 2321 2322 // We know that we are in the same block. Walk from 'this' to 'other', 2323 // checking to see if there is any instruction with an environment. 2324 HInstruction* current = this; 2325 for (; current != other && current != nullptr; current = current->GetNext()) { 2326 // This is a conservative check, as the instruction result may not be in 2327 // the referenced environment. 2328 if (current->HasEnvironment()) { 2329 return true; 2330 } 2331 } 2332 2333 // We should have been called with 'this' before 'other' in the block. 2334 // Just confirm this. 2335 DCHECK(current != nullptr); 2336 return false; 2337} 2338 2339void HInvoke::SetIntrinsic(Intrinsics intrinsic, 2340 IntrinsicNeedsEnvironmentOrCache needs_env_or_cache, 2341 IntrinsicSideEffects side_effects, 2342 IntrinsicExceptions exceptions) { 2343 intrinsic_ = intrinsic; 2344 IntrinsicOptimizations opt(this); 2345 2346 // Adjust method's side effects from intrinsic table. 2347 switch (side_effects) { 2348 case kNoSideEffects: SetSideEffects(SideEffects::None()); break; 2349 case kReadSideEffects: SetSideEffects(SideEffects::AllReads()); break; 2350 case kWriteSideEffects: SetSideEffects(SideEffects::AllWrites()); break; 2351 case kAllSideEffects: SetSideEffects(SideEffects::AllExceptGCDependency()); break; 2352 } 2353 2354 if (needs_env_or_cache == kNoEnvironmentOrCache) { 2355 opt.SetDoesNotNeedDexCache(); 2356 opt.SetDoesNotNeedEnvironment(); 2357 } else { 2358 // If we need an environment, that means there will be a call, which can trigger GC. 2359 SetSideEffects(GetSideEffects().Union(SideEffects::CanTriggerGC())); 2360 } 2361 // Adjust method's exception status from intrinsic table. 2362 SetCanThrow(exceptions == kCanThrow); 2363} 2364 2365bool HNewInstance::IsStringAlloc() const { 2366 ScopedObjectAccess soa(Thread::Current()); 2367 return GetReferenceTypeInfo().IsStringClass(); 2368} 2369 2370bool HInvoke::NeedsEnvironment() const { 2371 if (!IsIntrinsic()) { 2372 return true; 2373 } 2374 IntrinsicOptimizations opt(*this); 2375 return !opt.GetDoesNotNeedEnvironment(); 2376} 2377 2378bool HInvokeStaticOrDirect::NeedsDexCacheOfDeclaringClass() const { 2379 if (GetMethodLoadKind() != MethodLoadKind::kDexCacheViaMethod) { 2380 return false; 2381 } 2382 if (!IsIntrinsic()) { 2383 return true; 2384 } 2385 IntrinsicOptimizations opt(*this); 2386 return !opt.GetDoesNotNeedDexCache(); 2387} 2388 2389void HInvokeStaticOrDirect::InsertInputAt(size_t index, HInstruction* input) { 2390 inputs_.insert(inputs_.begin() + index, HUserRecord<HInstruction*>(input)); 2391 input->AddUseAt(this, index); 2392 // Update indexes in use nodes of inputs that have been pushed further back by the insert(). 2393 for (size_t i = index + 1u, size = inputs_.size(); i != size; ++i) { 2394 DCHECK_EQ(InputRecordAt(i).GetUseNode()->GetIndex(), i - 1u); 2395 InputRecordAt(i).GetUseNode()->SetIndex(i); 2396 } 2397} 2398 2399void HInvokeStaticOrDirect::RemoveInputAt(size_t index) { 2400 RemoveAsUserOfInput(index); 2401 inputs_.erase(inputs_.begin() + index); 2402 // Update indexes in use nodes of inputs that have been pulled forward by the erase(). 2403 for (size_t i = index, e = InputCount(); i < e; ++i) { 2404 DCHECK_EQ(InputRecordAt(i).GetUseNode()->GetIndex(), i + 1u); 2405 InputRecordAt(i).GetUseNode()->SetIndex(i); 2406 } 2407} 2408 2409std::ostream& operator<<(std::ostream& os, HInvokeStaticOrDirect::MethodLoadKind rhs) { 2410 switch (rhs) { 2411 case HInvokeStaticOrDirect::MethodLoadKind::kStringInit: 2412 return os << "string_init"; 2413 case HInvokeStaticOrDirect::MethodLoadKind::kRecursive: 2414 return os << "recursive"; 2415 case HInvokeStaticOrDirect::MethodLoadKind::kDirectAddress: 2416 return os << "direct"; 2417 case HInvokeStaticOrDirect::MethodLoadKind::kDirectAddressWithFixup: 2418 return os << "direct_fixup"; 2419 case HInvokeStaticOrDirect::MethodLoadKind::kDexCachePcRelative: 2420 return os << "dex_cache_pc_relative"; 2421 case HInvokeStaticOrDirect::MethodLoadKind::kDexCacheViaMethod: 2422 return os << "dex_cache_via_method"; 2423 default: 2424 LOG(FATAL) << "Unknown MethodLoadKind: " << static_cast<int>(rhs); 2425 UNREACHABLE(); 2426 } 2427} 2428 2429std::ostream& operator<<(std::ostream& os, HInvokeStaticOrDirect::ClinitCheckRequirement rhs) { 2430 switch (rhs) { 2431 case HInvokeStaticOrDirect::ClinitCheckRequirement::kExplicit: 2432 return os << "explicit"; 2433 case HInvokeStaticOrDirect::ClinitCheckRequirement::kImplicit: 2434 return os << "implicit"; 2435 case HInvokeStaticOrDirect::ClinitCheckRequirement::kNone: 2436 return os << "none"; 2437 default: 2438 LOG(FATAL) << "Unknown ClinitCheckRequirement: " << static_cast<int>(rhs); 2439 UNREACHABLE(); 2440 } 2441} 2442 2443bool HLoadString::InstructionDataEquals(HInstruction* other) const { 2444 HLoadString* other_load_string = other->AsLoadString(); 2445 if (string_index_ != other_load_string->string_index_ || 2446 GetPackedFields() != other_load_string->GetPackedFields()) { 2447 return false; 2448 } 2449 LoadKind load_kind = GetLoadKind(); 2450 if (HasAddress(load_kind)) { 2451 return GetAddress() == other_load_string->GetAddress(); 2452 } else if (HasStringReference(load_kind)) { 2453 return IsSameDexFile(GetDexFile(), other_load_string->GetDexFile()); 2454 } else { 2455 DCHECK(HasDexCacheReference(load_kind)) << load_kind; 2456 // If the string indexes and dex files are the same, dex cache element offsets 2457 // must also be the same, so we don't need to compare them. 2458 return IsSameDexFile(GetDexFile(), other_load_string->GetDexFile()); 2459 } 2460} 2461 2462void HLoadString::SetLoadKindInternal(LoadKind load_kind) { 2463 // Once sharpened, the load kind should not be changed again. 2464 DCHECK_EQ(GetLoadKind(), LoadKind::kDexCacheViaMethod); 2465 SetPackedField<LoadKindField>(load_kind); 2466 2467 if (load_kind != LoadKind::kDexCacheViaMethod) { 2468 RemoveAsUserOfInput(0u); 2469 SetRawInputAt(0u, nullptr); 2470 } 2471 if (!NeedsEnvironment()) { 2472 RemoveEnvironment(); 2473 SetSideEffects(SideEffects::None()); 2474 } 2475} 2476 2477std::ostream& operator<<(std::ostream& os, HLoadString::LoadKind rhs) { 2478 switch (rhs) { 2479 case HLoadString::LoadKind::kBootImageLinkTimeAddress: 2480 return os << "BootImageLinkTimeAddress"; 2481 case HLoadString::LoadKind::kBootImageLinkTimePcRelative: 2482 return os << "BootImageLinkTimePcRelative"; 2483 case HLoadString::LoadKind::kBootImageAddress: 2484 return os << "BootImageAddress"; 2485 case HLoadString::LoadKind::kDexCacheAddress: 2486 return os << "DexCacheAddress"; 2487 case HLoadString::LoadKind::kDexCachePcRelative: 2488 return os << "DexCachePcRelative"; 2489 case HLoadString::LoadKind::kDexCacheViaMethod: 2490 return os << "DexCacheViaMethod"; 2491 default: 2492 LOG(FATAL) << "Unknown HLoadString::LoadKind: " << static_cast<int>(rhs); 2493 UNREACHABLE(); 2494 } 2495} 2496 2497void HInstruction::RemoveEnvironmentUsers() { 2498 for (const HUseListNode<HEnvironment*>& use : GetEnvUses()) { 2499 HEnvironment* user = use.GetUser(); 2500 user->SetRawEnvAt(use.GetIndex(), nullptr); 2501 } 2502 env_uses_.clear(); 2503} 2504 2505// Returns an instruction with the opposite Boolean value from 'cond'. 2506HInstruction* HGraph::InsertOppositeCondition(HInstruction* cond, HInstruction* cursor) { 2507 ArenaAllocator* allocator = GetArena(); 2508 2509 if (cond->IsCondition() && 2510 !Primitive::IsFloatingPointType(cond->InputAt(0)->GetType())) { 2511 // Can't reverse floating point conditions. We have to use HBooleanNot in that case. 2512 HInstruction* lhs = cond->InputAt(0); 2513 HInstruction* rhs = cond->InputAt(1); 2514 HInstruction* replacement = nullptr; 2515 switch (cond->AsCondition()->GetOppositeCondition()) { // get *opposite* 2516 case kCondEQ: replacement = new (allocator) HEqual(lhs, rhs); break; 2517 case kCondNE: replacement = new (allocator) HNotEqual(lhs, rhs); break; 2518 case kCondLT: replacement = new (allocator) HLessThan(lhs, rhs); break; 2519 case kCondLE: replacement = new (allocator) HLessThanOrEqual(lhs, rhs); break; 2520 case kCondGT: replacement = new (allocator) HGreaterThan(lhs, rhs); break; 2521 case kCondGE: replacement = new (allocator) HGreaterThanOrEqual(lhs, rhs); break; 2522 case kCondB: replacement = new (allocator) HBelow(lhs, rhs); break; 2523 case kCondBE: replacement = new (allocator) HBelowOrEqual(lhs, rhs); break; 2524 case kCondA: replacement = new (allocator) HAbove(lhs, rhs); break; 2525 case kCondAE: replacement = new (allocator) HAboveOrEqual(lhs, rhs); break; 2526 default: 2527 LOG(FATAL) << "Unexpected condition"; 2528 UNREACHABLE(); 2529 } 2530 cursor->GetBlock()->InsertInstructionBefore(replacement, cursor); 2531 return replacement; 2532 } else if (cond->IsIntConstant()) { 2533 HIntConstant* int_const = cond->AsIntConstant(); 2534 if (int_const->IsFalse()) { 2535 return GetIntConstant(1); 2536 } else { 2537 DCHECK(int_const->IsTrue()) << int_const->GetValue(); 2538 return GetIntConstant(0); 2539 } 2540 } else { 2541 HInstruction* replacement = new (allocator) HBooleanNot(cond); 2542 cursor->GetBlock()->InsertInstructionBefore(replacement, cursor); 2543 return replacement; 2544 } 2545} 2546 2547std::ostream& operator<<(std::ostream& os, const MoveOperands& rhs) { 2548 os << "[" 2549 << " source=" << rhs.GetSource() 2550 << " destination=" << rhs.GetDestination() 2551 << " type=" << rhs.GetType() 2552 << " instruction="; 2553 if (rhs.GetInstruction() != nullptr) { 2554 os << rhs.GetInstruction()->DebugName() << ' ' << rhs.GetInstruction()->GetId(); 2555 } else { 2556 os << "null"; 2557 } 2558 os << " ]"; 2559 return os; 2560} 2561 2562std::ostream& operator<<(std::ostream& os, TypeCheckKind rhs) { 2563 switch (rhs) { 2564 case TypeCheckKind::kUnresolvedCheck: 2565 return os << "unresolved_check"; 2566 case TypeCheckKind::kExactCheck: 2567 return os << "exact_check"; 2568 case TypeCheckKind::kClassHierarchyCheck: 2569 return os << "class_hierarchy_check"; 2570 case TypeCheckKind::kAbstractClassCheck: 2571 return os << "abstract_class_check"; 2572 case TypeCheckKind::kInterfaceCheck: 2573 return os << "interface_check"; 2574 case TypeCheckKind::kArrayObjectCheck: 2575 return os << "array_object_check"; 2576 case TypeCheckKind::kArrayCheck: 2577 return os << "array_check"; 2578 default: 2579 LOG(FATAL) << "Unknown TypeCheckKind: " << static_cast<int>(rhs); 2580 UNREACHABLE(); 2581 } 2582} 2583 2584} // namespace art 2585