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 "art_method-inl.h" 21 #include "base/bit_utils.h" 22 #include "base/bit_vector-inl.h" 23 #include "base/logging.h" 24 #include "base/stl_util.h" 25 #include "class_linker-inl.h" 26 #include "class_root.h" 27 #include "code_generator.h" 28 #include "common_dominator.h" 29 #include "intrinsics.h" 30 #include "mirror/class-inl.h" 31 #include "scoped_thread_state_change-inl.h" 32 #include "ssa_builder.h" 33 34 namespace art { 35 36 // Enable floating-point static evaluation during constant folding 37 // only if all floating-point operations and constants evaluate in the 38 // range and precision of the type used (i.e., 32-bit float, 64-bit 39 // double). 40 static constexpr bool kEnableFloatingPointStaticEvaluation = (FLT_EVAL_METHOD == 0); 41 42 void HGraph::InitializeInexactObjectRTI(VariableSizedHandleScope* handles) { 43 ScopedObjectAccess soa(Thread::Current()); 44 // Create the inexact Object reference type and store it in the HGraph. 45 inexact_object_rti_ = ReferenceTypeInfo::Create( 46 handles->NewHandle(GetClassRoot<mirror::Object>()), 47 /* is_exact= */ false); 48 } 49 50 void HGraph::AddBlock(HBasicBlock* block) { 51 block->SetBlockId(blocks_.size()); 52 blocks_.push_back(block); 53 } 54 55 void HGraph::FindBackEdges(ArenaBitVector* visited) { 56 // "visited" must be empty on entry, it's an output argument for all visited (i.e. live) blocks. 57 DCHECK_EQ(visited->GetHighestBitSet(), -1); 58 59 // Allocate memory from local ScopedArenaAllocator. 60 ScopedArenaAllocator allocator(GetArenaStack()); 61 // Nodes that we're currently visiting, indexed by block id. 62 ArenaBitVector visiting( 63 &allocator, blocks_.size(), /* expandable= */ false, kArenaAllocGraphBuilder); 64 visiting.ClearAllBits(); 65 // Number of successors visited from a given node, indexed by block id. 66 ScopedArenaVector<size_t> successors_visited(blocks_.size(), 67 0u, 68 allocator.Adapter(kArenaAllocGraphBuilder)); 69 // Stack of nodes that we're currently visiting (same as marked in "visiting" above). 70 ScopedArenaVector<HBasicBlock*> worklist(allocator.Adapter(kArenaAllocGraphBuilder)); 71 constexpr size_t kDefaultWorklistSize = 8; 72 worklist.reserve(kDefaultWorklistSize); 73 visited->SetBit(entry_block_->GetBlockId()); 74 visiting.SetBit(entry_block_->GetBlockId()); 75 worklist.push_back(entry_block_); 76 77 while (!worklist.empty()) { 78 HBasicBlock* current = worklist.back(); 79 uint32_t current_id = current->GetBlockId(); 80 if (successors_visited[current_id] == current->GetSuccessors().size()) { 81 visiting.ClearBit(current_id); 82 worklist.pop_back(); 83 } else { 84 HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++]; 85 uint32_t successor_id = successor->GetBlockId(); 86 if (visiting.IsBitSet(successor_id)) { 87 DCHECK(ContainsElement(worklist, successor)); 88 successor->AddBackEdge(current); 89 } else if (!visited->IsBitSet(successor_id)) { 90 visited->SetBit(successor_id); 91 visiting.SetBit(successor_id); 92 worklist.push_back(successor); 93 } 94 } 95 } 96 } 97 98 // Remove the environment use records of the instruction for users. 99 void RemoveEnvironmentUses(HInstruction* instruction) { 100 for (HEnvironment* environment = instruction->GetEnvironment(); 101 environment != nullptr; 102 environment = environment->GetParent()) { 103 for (size_t i = 0, e = environment->Size(); i < e; ++i) { 104 if (environment->GetInstructionAt(i) != nullptr) { 105 environment->RemoveAsUserOfInput(i); 106 } 107 } 108 } 109 } 110 111 // Return whether the instruction has an environment and it's used by others. 112 bool HasEnvironmentUsedByOthers(HInstruction* instruction) { 113 for (HEnvironment* environment = instruction->GetEnvironment(); 114 environment != nullptr; 115 environment = environment->GetParent()) { 116 for (size_t i = 0, e = environment->Size(); i < e; ++i) { 117 HInstruction* user = environment->GetInstructionAt(i); 118 if (user != nullptr) { 119 return true; 120 } 121 } 122 } 123 return false; 124 } 125 126 // Reset environment records of the instruction itself. 127 void ResetEnvironmentInputRecords(HInstruction* instruction) { 128 for (HEnvironment* environment = instruction->GetEnvironment(); 129 environment != nullptr; 130 environment = environment->GetParent()) { 131 for (size_t i = 0, e = environment->Size(); i < e; ++i) { 132 DCHECK(environment->GetHolder() == instruction); 133 if (environment->GetInstructionAt(i) != nullptr) { 134 environment->SetRawEnvAt(i, nullptr); 135 } 136 } 137 } 138 } 139 140 static void RemoveAsUser(HInstruction* instruction) { 141 instruction->RemoveAsUserOfAllInputs(); 142 RemoveEnvironmentUses(instruction); 143 } 144 145 void HGraph::RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const { 146 for (size_t i = 0; i < blocks_.size(); ++i) { 147 if (!visited.IsBitSet(i)) { 148 HBasicBlock* block = blocks_[i]; 149 if (block == nullptr) continue; 150 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 151 RemoveAsUser(it.Current()); 152 } 153 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 154 RemoveAsUser(it.Current()); 155 } 156 } 157 } 158 } 159 160 void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) { 161 for (size_t i = 0; i < blocks_.size(); ++i) { 162 if (!visited.IsBitSet(i)) { 163 HBasicBlock* block = blocks_[i]; 164 if (block == nullptr) continue; 165 // We only need to update the successor, which might be live. 166 for (HBasicBlock* successor : block->GetSuccessors()) { 167 successor->RemovePredecessor(block); 168 } 169 // Remove the block from the list of blocks, so that further analyses 170 // never see it. 171 blocks_[i] = nullptr; 172 if (block->IsExitBlock()) { 173 SetExitBlock(nullptr); 174 } 175 // Mark the block as removed. This is used by the HGraphBuilder to discard 176 // the block as a branch target. 177 block->SetGraph(nullptr); 178 } 179 } 180 } 181 182 GraphAnalysisResult HGraph::BuildDominatorTree() { 183 // Allocate memory from local ScopedArenaAllocator. 184 ScopedArenaAllocator allocator(GetArenaStack()); 185 186 ArenaBitVector visited(&allocator, blocks_.size(), false, kArenaAllocGraphBuilder); 187 visited.ClearAllBits(); 188 189 // (1) Find the back edges in the graph doing a DFS traversal. 190 FindBackEdges(&visited); 191 192 // (2) Remove instructions and phis from blocks not visited during 193 // the initial DFS as users from other instructions, so that 194 // users can be safely removed before uses later. 195 RemoveInstructionsAsUsersFromDeadBlocks(visited); 196 197 // (3) Remove blocks not visited during the initial DFS. 198 // Step (5) requires dead blocks to be removed from the 199 // predecessors list of live blocks. 200 RemoveDeadBlocks(visited); 201 202 // (4) Simplify the CFG now, so that we don't need to recompute 203 // dominators and the reverse post order. 204 SimplifyCFG(); 205 206 // (5) Compute the dominance information and the reverse post order. 207 ComputeDominanceInformation(); 208 209 // (6) Analyze loops discovered through back edge analysis, and 210 // set the loop information on each block. 211 GraphAnalysisResult result = AnalyzeLoops(); 212 if (result != kAnalysisSuccess) { 213 return result; 214 } 215 216 // (7) Precompute per-block try membership before entering the SSA builder, 217 // which needs the information to build catch block phis from values of 218 // locals at throwing instructions inside try blocks. 219 ComputeTryBlockInformation(); 220 221 return kAnalysisSuccess; 222 } 223 224 void HGraph::ClearDominanceInformation() { 225 for (HBasicBlock* block : GetReversePostOrder()) { 226 block->ClearDominanceInformation(); 227 } 228 reverse_post_order_.clear(); 229 } 230 231 void HGraph::ClearLoopInformation() { 232 SetHasIrreducibleLoops(false); 233 for (HBasicBlock* block : GetReversePostOrder()) { 234 block->SetLoopInformation(nullptr); 235 } 236 } 237 238 void HBasicBlock::ClearDominanceInformation() { 239 dominated_blocks_.clear(); 240 dominator_ = nullptr; 241 } 242 243 HInstruction* HBasicBlock::GetFirstInstructionDisregardMoves() const { 244 HInstruction* instruction = GetFirstInstruction(); 245 while (instruction->IsParallelMove()) { 246 instruction = instruction->GetNext(); 247 } 248 return instruction; 249 } 250 251 static bool UpdateDominatorOfSuccessor(HBasicBlock* block, HBasicBlock* successor) { 252 DCHECK(ContainsElement(block->GetSuccessors(), successor)); 253 254 HBasicBlock* old_dominator = successor->GetDominator(); 255 HBasicBlock* new_dominator = 256 (old_dominator == nullptr) ? block 257 : CommonDominator::ForPair(old_dominator, block); 258 259 if (old_dominator == new_dominator) { 260 return false; 261 } else { 262 successor->SetDominator(new_dominator); 263 return true; 264 } 265 } 266 267 void HGraph::ComputeDominanceInformation() { 268 DCHECK(reverse_post_order_.empty()); 269 reverse_post_order_.reserve(blocks_.size()); 270 reverse_post_order_.push_back(entry_block_); 271 272 // Allocate memory from local ScopedArenaAllocator. 273 ScopedArenaAllocator allocator(GetArenaStack()); 274 // Number of visits of a given node, indexed by block id. 275 ScopedArenaVector<size_t> visits(blocks_.size(), 0u, allocator.Adapter(kArenaAllocGraphBuilder)); 276 // Number of successors visited from a given node, indexed by block id. 277 ScopedArenaVector<size_t> successors_visited(blocks_.size(), 278 0u, 279 allocator.Adapter(kArenaAllocGraphBuilder)); 280 // Nodes for which we need to visit successors. 281 ScopedArenaVector<HBasicBlock*> worklist(allocator.Adapter(kArenaAllocGraphBuilder)); 282 constexpr size_t kDefaultWorklistSize = 8; 283 worklist.reserve(kDefaultWorklistSize); 284 worklist.push_back(entry_block_); 285 286 while (!worklist.empty()) { 287 HBasicBlock* current = worklist.back(); 288 uint32_t current_id = current->GetBlockId(); 289 if (successors_visited[current_id] == current->GetSuccessors().size()) { 290 worklist.pop_back(); 291 } else { 292 HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++]; 293 UpdateDominatorOfSuccessor(current, successor); 294 295 // Once all the forward edges have been visited, we know the immediate 296 // dominator of the block. We can then start visiting its successors. 297 if (++visits[successor->GetBlockId()] == 298 successor->GetPredecessors().size() - successor->NumberOfBackEdges()) { 299 reverse_post_order_.push_back(successor); 300 worklist.push_back(successor); 301 } 302 } 303 } 304 305 // Check if the graph has back edges not dominated by their respective headers. 306 // If so, we need to update the dominators of those headers and recursively of 307 // their successors. We do that with a fix-point iteration over all blocks. 308 // The algorithm is guaranteed to terminate because it loops only if the sum 309 // of all dominator chains has decreased in the current iteration. 310 bool must_run_fix_point = false; 311 for (HBasicBlock* block : blocks_) { 312 if (block != nullptr && 313 block->IsLoopHeader() && 314 block->GetLoopInformation()->HasBackEdgeNotDominatedByHeader()) { 315 must_run_fix_point = true; 316 break; 317 } 318 } 319 if (must_run_fix_point) { 320 bool update_occurred = true; 321 while (update_occurred) { 322 update_occurred = false; 323 for (HBasicBlock* block : GetReversePostOrder()) { 324 for (HBasicBlock* successor : block->GetSuccessors()) { 325 update_occurred |= UpdateDominatorOfSuccessor(block, successor); 326 } 327 } 328 } 329 } 330 331 // Make sure that there are no remaining blocks whose dominator information 332 // needs to be updated. 333 if (kIsDebugBuild) { 334 for (HBasicBlock* block : GetReversePostOrder()) { 335 for (HBasicBlock* successor : block->GetSuccessors()) { 336 DCHECK(!UpdateDominatorOfSuccessor(block, successor)); 337 } 338 } 339 } 340 341 // Populate `dominated_blocks_` information after computing all dominators. 342 // The potential presence of irreducible loops requires to do it after. 343 for (HBasicBlock* block : GetReversePostOrder()) { 344 if (!block->IsEntryBlock()) { 345 block->GetDominator()->AddDominatedBlock(block); 346 } 347 } 348 } 349 350 HBasicBlock* HGraph::SplitEdge(HBasicBlock* block, HBasicBlock* successor) { 351 HBasicBlock* new_block = new (allocator_) HBasicBlock(this, successor->GetDexPc()); 352 AddBlock(new_block); 353 // Use `InsertBetween` to ensure the predecessor index and successor index of 354 // `block` and `successor` are preserved. 355 new_block->InsertBetween(block, successor); 356 return new_block; 357 } 358 359 void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) { 360 // Insert a new node between `block` and `successor` to split the 361 // critical edge. 362 HBasicBlock* new_block = SplitEdge(block, successor); 363 new_block->AddInstruction(new (allocator_) HGoto(successor->GetDexPc())); 364 if (successor->IsLoopHeader()) { 365 // If we split at a back edge boundary, make the new block the back edge. 366 HLoopInformation* info = successor->GetLoopInformation(); 367 if (info->IsBackEdge(*block)) { 368 info->RemoveBackEdge(block); 369 info->AddBackEdge(new_block); 370 } 371 } 372 } 373 374 // Reorder phi inputs to match reordering of the block's predecessors. 375 static void FixPhisAfterPredecessorsReodering(HBasicBlock* block, size_t first, size_t second) { 376 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 377 HPhi* phi = it.Current()->AsPhi(); 378 HInstruction* first_instr = phi->InputAt(first); 379 HInstruction* second_instr = phi->InputAt(second); 380 phi->ReplaceInput(first_instr, second); 381 phi->ReplaceInput(second_instr, first); 382 } 383 } 384 385 // Make sure that the first predecessor of a loop header is the incoming block. 386 void HGraph::OrderLoopHeaderPredecessors(HBasicBlock* header) { 387 DCHECK(header->IsLoopHeader()); 388 HLoopInformation* info = header->GetLoopInformation(); 389 if (info->IsBackEdge(*header->GetPredecessors()[0])) { 390 HBasicBlock* to_swap = header->GetPredecessors()[0]; 391 for (size_t pred = 1, e = header->GetPredecessors().size(); pred < e; ++pred) { 392 HBasicBlock* predecessor = header->GetPredecessors()[pred]; 393 if (!info->IsBackEdge(*predecessor)) { 394 header->predecessors_[pred] = to_swap; 395 header->predecessors_[0] = predecessor; 396 FixPhisAfterPredecessorsReodering(header, 0, pred); 397 break; 398 } 399 } 400 } 401 } 402 403 // Transform control flow of the loop to a single preheader format (don't touch the data flow). 404 // New_preheader can be already among the header predecessors - this situation will be correctly 405 // processed. 406 static void FixControlForNewSinglePreheader(HBasicBlock* header, HBasicBlock* new_preheader) { 407 HLoopInformation* loop_info = header->GetLoopInformation(); 408 for (size_t pred = 0; pred < header->GetPredecessors().size(); ++pred) { 409 HBasicBlock* predecessor = header->GetPredecessors()[pred]; 410 if (!loop_info->IsBackEdge(*predecessor) && predecessor != new_preheader) { 411 predecessor->ReplaceSuccessor(header, new_preheader); 412 pred--; 413 } 414 } 415 } 416 417 // == Before == == After == 418 // _________ _________ _________ _________ 419 // | B0 | | B1 | (old preheaders) | B0 | | B1 | 420 // |=========| |=========| |=========| |=========| 421 // | i0 = .. | | i1 = .. | | i0 = .. | | i1 = .. | 422 // |_________| |_________| |_________| |_________| 423 // \ / \ / 424 // \ / ___v____________v___ 425 // \ / (new preheader) | B20 <- B0, B1 | 426 // | | |====================| 427 // | | | i20 = phi(i0, i1) | 428 // | | |____________________| 429 // | | | 430 // /\ | | /\ /\ | /\ 431 // / v_______v_________v_______v \ / v___________v_____________v \ 432 // | | B10 <- B0, B1, B2, B3 | | | | B10 <- B20, B2, B3 | | 433 // | |===========================| | (header) | |===========================| | 434 // | | i10 = phi(i0, i1, i2, i3) | | | | i10 = phi(i20, i2, i3) | | 435 // | |___________________________| | | |___________________________| | 436 // | / \ | | / \ | 437 // | ... ... | | ... ... | 438 // | _________ _________ | | _________ _________ | 439 // | | B2 | | B3 | | | | B2 | | B3 | | 440 // | |=========| |=========| | (back edges) | |=========| |=========| | 441 // | | i2 = .. | | i3 = .. | | | | i2 = .. | | i3 = .. | | 442 // | |_________| |_________| | | |_________| |_________| | 443 // \ / \ / \ / \ / 444 // \___/ \___/ \___/ \___/ 445 // 446 void HGraph::TransformLoopToSinglePreheaderFormat(HBasicBlock* header) { 447 HLoopInformation* loop_info = header->GetLoopInformation(); 448 449 HBasicBlock* preheader = new (allocator_) HBasicBlock(this, header->GetDexPc()); 450 AddBlock(preheader); 451 preheader->AddInstruction(new (allocator_) HGoto(header->GetDexPc())); 452 453 // If the old header has no Phis then we only need to fix the control flow. 454 if (header->GetPhis().IsEmpty()) { 455 FixControlForNewSinglePreheader(header, preheader); 456 preheader->AddSuccessor(header); 457 return; 458 } 459 460 // Find the first non-back edge block in the header's predecessors list. 461 size_t first_nonbackedge_pred_pos = 0; 462 bool found = false; 463 for (size_t pred = 0; pred < header->GetPredecessors().size(); ++pred) { 464 HBasicBlock* predecessor = header->GetPredecessors()[pred]; 465 if (!loop_info->IsBackEdge(*predecessor)) { 466 first_nonbackedge_pred_pos = pred; 467 found = true; 468 break; 469 } 470 } 471 472 DCHECK(found); 473 474 // Fix the data-flow. 475 for (HInstructionIterator it(header->GetPhis()); !it.Done(); it.Advance()) { 476 HPhi* header_phi = it.Current()->AsPhi(); 477 478 HPhi* preheader_phi = new (GetAllocator()) HPhi(GetAllocator(), 479 header_phi->GetRegNumber(), 480 0, 481 header_phi->GetType()); 482 if (header_phi->GetType() == DataType::Type::kReference) { 483 preheader_phi->SetReferenceTypeInfo(header_phi->GetReferenceTypeInfo()); 484 } 485 preheader->AddPhi(preheader_phi); 486 487 HInstruction* orig_input = header_phi->InputAt(first_nonbackedge_pred_pos); 488 header_phi->ReplaceInput(preheader_phi, first_nonbackedge_pred_pos); 489 preheader_phi->AddInput(orig_input); 490 491 for (size_t input_pos = first_nonbackedge_pred_pos + 1; 492 input_pos < header_phi->InputCount(); 493 input_pos++) { 494 HInstruction* input = header_phi->InputAt(input_pos); 495 HBasicBlock* pred_block = header->GetPredecessors()[input_pos]; 496 497 if (loop_info->Contains(*pred_block)) { 498 DCHECK(loop_info->IsBackEdge(*pred_block)); 499 } else { 500 preheader_phi->AddInput(input); 501 header_phi->RemoveInputAt(input_pos); 502 input_pos--; 503 } 504 } 505 } 506 507 // Fix the control-flow. 508 HBasicBlock* first_pred = header->GetPredecessors()[first_nonbackedge_pred_pos]; 509 preheader->InsertBetween(first_pred, header); 510 511 FixControlForNewSinglePreheader(header, preheader); 512 } 513 514 void HGraph::SimplifyLoop(HBasicBlock* header) { 515 HLoopInformation* info = header->GetLoopInformation(); 516 517 // Make sure the loop has only one pre header. This simplifies SSA building by having 518 // to just look at the pre header to know which locals are initialized at entry of the 519 // loop. Also, don't allow the entry block to be a pre header: this simplifies inlining 520 // this graph. 521 size_t number_of_incomings = header->GetPredecessors().size() - info->NumberOfBackEdges(); 522 if (number_of_incomings != 1 || (GetEntryBlock()->GetSingleSuccessor() == header)) { 523 TransformLoopToSinglePreheaderFormat(header); 524 } 525 526 OrderLoopHeaderPredecessors(header); 527 528 HInstruction* first_instruction = header->GetFirstInstruction(); 529 if (first_instruction != nullptr && first_instruction->IsSuspendCheck()) { 530 // Called from DeadBlockElimination. Update SuspendCheck pointer. 531 info->SetSuspendCheck(first_instruction->AsSuspendCheck()); 532 } 533 } 534 535 void HGraph::ComputeTryBlockInformation() { 536 // Iterate in reverse post order to propagate try membership information from 537 // predecessors to their successors. 538 for (HBasicBlock* block : GetReversePostOrder()) { 539 if (block->IsEntryBlock() || block->IsCatchBlock()) { 540 // Catch blocks after simplification have only exceptional predecessors 541 // and hence are never in tries. 542 continue; 543 } 544 545 // Infer try membership from the first predecessor. Having simplified loops, 546 // the first predecessor can never be a back edge and therefore it must have 547 // been visited already and had its try membership set. 548 HBasicBlock* first_predecessor = block->GetPredecessors()[0]; 549 DCHECK(!block->IsLoopHeader() || !block->GetLoopInformation()->IsBackEdge(*first_predecessor)); 550 const HTryBoundary* try_entry = first_predecessor->ComputeTryEntryOfSuccessors(); 551 if (try_entry != nullptr && 552 (block->GetTryCatchInformation() == nullptr || 553 try_entry != &block->GetTryCatchInformation()->GetTryEntry())) { 554 // We are either setting try block membership for the first time or it 555 // has changed. 556 block->SetTryCatchInformation(new (allocator_) TryCatchInformation(*try_entry)); 557 } 558 } 559 } 560 561 void HGraph::SimplifyCFG() { 562 // Simplify the CFG for future analysis, and code generation: 563 // (1): Split critical edges. 564 // (2): Simplify loops by having only one preheader. 565 // NOTE: We're appending new blocks inside the loop, so we need to use index because iterators 566 // can be invalidated. We remember the initial size to avoid iterating over the new blocks. 567 for (size_t block_id = 0u, end = blocks_.size(); block_id != end; ++block_id) { 568 HBasicBlock* block = blocks_[block_id]; 569 if (block == nullptr) continue; 570 if (block->GetSuccessors().size() > 1) { 571 // Only split normal-flow edges. We cannot split exceptional edges as they 572 // are synthesized (approximate real control flow), and we do not need to 573 // anyway. Moves that would be inserted there are performed by the runtime. 574 ArrayRef<HBasicBlock* const> normal_successors = block->GetNormalSuccessors(); 575 for (size_t j = 0, e = normal_successors.size(); j < e; ++j) { 576 HBasicBlock* successor = normal_successors[j]; 577 DCHECK(!successor->IsCatchBlock()); 578 if (successor == exit_block_) { 579 // (Throw/Return/ReturnVoid)->TryBoundary->Exit. Special case which we 580 // do not want to split because Goto->Exit is not allowed. 581 DCHECK(block->IsSingleTryBoundary()); 582 } else if (successor->GetPredecessors().size() > 1) { 583 SplitCriticalEdge(block, successor); 584 // SplitCriticalEdge could have invalidated the `normal_successors` 585 // ArrayRef. We must re-acquire it. 586 normal_successors = block->GetNormalSuccessors(); 587 DCHECK_EQ(normal_successors[j]->GetSingleSuccessor(), successor); 588 DCHECK_EQ(e, normal_successors.size()); 589 } 590 } 591 } 592 if (block->IsLoopHeader()) { 593 SimplifyLoop(block); 594 } else if (!block->IsEntryBlock() && 595 block->GetFirstInstruction() != nullptr && 596 block->GetFirstInstruction()->IsSuspendCheck()) { 597 // We are being called by the dead code elimiation pass, and what used to be 598 // a loop got dismantled. Just remove the suspend check. 599 block->RemoveInstruction(block->GetFirstInstruction()); 600 } 601 } 602 } 603 604 GraphAnalysisResult HGraph::AnalyzeLoops() const { 605 // We iterate post order to ensure we visit inner loops before outer loops. 606 // `PopulateRecursive` needs this guarantee to know whether a natural loop 607 // contains an irreducible loop. 608 for (HBasicBlock* block : GetPostOrder()) { 609 if (block->IsLoopHeader()) { 610 if (block->IsCatchBlock()) { 611 // TODO: Dealing with exceptional back edges could be tricky because 612 // they only approximate the real control flow. Bail out for now. 613 VLOG(compiler) << "Not compiled: Exceptional back edges"; 614 return kAnalysisFailThrowCatchLoop; 615 } 616 block->GetLoopInformation()->Populate(); 617 } 618 } 619 return kAnalysisSuccess; 620 } 621 622 void HLoopInformation::Dump(std::ostream& os) { 623 os << "header: " << header_->GetBlockId() << std::endl; 624 os << "pre header: " << GetPreHeader()->GetBlockId() << std::endl; 625 for (HBasicBlock* block : back_edges_) { 626 os << "back edge: " << block->GetBlockId() << std::endl; 627 } 628 for (HBasicBlock* block : header_->GetPredecessors()) { 629 os << "predecessor: " << block->GetBlockId() << std::endl; 630 } 631 for (uint32_t idx : blocks_.Indexes()) { 632 os << " in loop: " << idx << std::endl; 633 } 634 } 635 636 void HGraph::InsertConstant(HConstant* constant) { 637 // New constants are inserted before the SuspendCheck at the bottom of the 638 // entry block. Note that this method can be called from the graph builder and 639 // the entry block therefore may not end with SuspendCheck->Goto yet. 640 HInstruction* insert_before = nullptr; 641 642 HInstruction* gota = entry_block_->GetLastInstruction(); 643 if (gota != nullptr && gota->IsGoto()) { 644 HInstruction* suspend_check = gota->GetPrevious(); 645 if (suspend_check != nullptr && suspend_check->IsSuspendCheck()) { 646 insert_before = suspend_check; 647 } else { 648 insert_before = gota; 649 } 650 } 651 652 if (insert_before == nullptr) { 653 entry_block_->AddInstruction(constant); 654 } else { 655 entry_block_->InsertInstructionBefore(constant, insert_before); 656 } 657 } 658 659 HNullConstant* HGraph::GetNullConstant(uint32_t dex_pc) { 660 // For simplicity, don't bother reviving the cached null constant if it is 661 // not null and not in a block. Otherwise, we need to clear the instruction 662 // id and/or any invariants the graph is assuming when adding new instructions. 663 if ((cached_null_constant_ == nullptr) || (cached_null_constant_->GetBlock() == nullptr)) { 664 cached_null_constant_ = new (allocator_) HNullConstant(dex_pc); 665 cached_null_constant_->SetReferenceTypeInfo(inexact_object_rti_); 666 InsertConstant(cached_null_constant_); 667 } 668 if (kIsDebugBuild) { 669 ScopedObjectAccess soa(Thread::Current()); 670 DCHECK(cached_null_constant_->GetReferenceTypeInfo().IsValid()); 671 } 672 return cached_null_constant_; 673 } 674 675 HCurrentMethod* HGraph::GetCurrentMethod() { 676 // For simplicity, don't bother reviving the cached current method if it is 677 // not null and not in a block. Otherwise, we need to clear the instruction 678 // id and/or any invariants the graph is assuming when adding new instructions. 679 if ((cached_current_method_ == nullptr) || (cached_current_method_->GetBlock() == nullptr)) { 680 cached_current_method_ = new (allocator_) HCurrentMethod( 681 Is64BitInstructionSet(instruction_set_) ? DataType::Type::kInt64 : DataType::Type::kInt32, 682 entry_block_->GetDexPc()); 683 if (entry_block_->GetFirstInstruction() == nullptr) { 684 entry_block_->AddInstruction(cached_current_method_); 685 } else { 686 entry_block_->InsertInstructionBefore( 687 cached_current_method_, entry_block_->GetFirstInstruction()); 688 } 689 } 690 return cached_current_method_; 691 } 692 693 const char* HGraph::GetMethodName() const { 694 const dex::MethodId& method_id = dex_file_.GetMethodId(method_idx_); 695 return dex_file_.GetMethodName(method_id); 696 } 697 698 std::string HGraph::PrettyMethod(bool with_signature) const { 699 return dex_file_.PrettyMethod(method_idx_, with_signature); 700 } 701 702 HConstant* HGraph::GetConstant(DataType::Type type, int64_t value, uint32_t dex_pc) { 703 switch (type) { 704 case DataType::Type::kBool: 705 DCHECK(IsUint<1>(value)); 706 FALLTHROUGH_INTENDED; 707 case DataType::Type::kUint8: 708 case DataType::Type::kInt8: 709 case DataType::Type::kUint16: 710 case DataType::Type::kInt16: 711 case DataType::Type::kInt32: 712 DCHECK(IsInt(DataType::Size(type) * kBitsPerByte, value)); 713 return GetIntConstant(static_cast<int32_t>(value), dex_pc); 714 715 case DataType::Type::kInt64: 716 return GetLongConstant(value, dex_pc); 717 718 default: 719 LOG(FATAL) << "Unsupported constant type"; 720 UNREACHABLE(); 721 } 722 } 723 724 void HGraph::CacheFloatConstant(HFloatConstant* constant) { 725 int32_t value = bit_cast<int32_t, float>(constant->GetValue()); 726 DCHECK(cached_float_constants_.find(value) == cached_float_constants_.end()); 727 cached_float_constants_.Overwrite(value, constant); 728 } 729 730 void HGraph::CacheDoubleConstant(HDoubleConstant* constant) { 731 int64_t value = bit_cast<int64_t, double>(constant->GetValue()); 732 DCHECK(cached_double_constants_.find(value) == cached_double_constants_.end()); 733 cached_double_constants_.Overwrite(value, constant); 734 } 735 736 void HLoopInformation::Add(HBasicBlock* block) { 737 blocks_.SetBit(block->GetBlockId()); 738 } 739 740 void HLoopInformation::Remove(HBasicBlock* block) { 741 blocks_.ClearBit(block->GetBlockId()); 742 } 743 744 void HLoopInformation::PopulateRecursive(HBasicBlock* block) { 745 if (blocks_.IsBitSet(block->GetBlockId())) { 746 return; 747 } 748 749 blocks_.SetBit(block->GetBlockId()); 750 block->SetInLoop(this); 751 if (block->IsLoopHeader()) { 752 // We're visiting loops in post-order, so inner loops must have been 753 // populated already. 754 DCHECK(block->GetLoopInformation()->IsPopulated()); 755 if (block->GetLoopInformation()->IsIrreducible()) { 756 contains_irreducible_loop_ = true; 757 } 758 } 759 for (HBasicBlock* predecessor : block->GetPredecessors()) { 760 PopulateRecursive(predecessor); 761 } 762 } 763 764 void HLoopInformation::PopulateIrreducibleRecursive(HBasicBlock* block, ArenaBitVector* finalized) { 765 size_t block_id = block->GetBlockId(); 766 767 // If `block` is in `finalized`, we know its membership in the loop has been 768 // decided and it does not need to be revisited. 769 if (finalized->IsBitSet(block_id)) { 770 return; 771 } 772 773 bool is_finalized = false; 774 if (block->IsLoopHeader()) { 775 // If we hit a loop header in an irreducible loop, we first check if the 776 // pre header of that loop belongs to the currently analyzed loop. If it does, 777 // then we visit the back edges. 778 // Note that we cannot use GetPreHeader, as the loop may have not been populated 779 // yet. 780 HBasicBlock* pre_header = block->GetPredecessors()[0]; 781 PopulateIrreducibleRecursive(pre_header, finalized); 782 if (blocks_.IsBitSet(pre_header->GetBlockId())) { 783 block->SetInLoop(this); 784 blocks_.SetBit(block_id); 785 finalized->SetBit(block_id); 786 is_finalized = true; 787 788 HLoopInformation* info = block->GetLoopInformation(); 789 for (HBasicBlock* back_edge : info->GetBackEdges()) { 790 PopulateIrreducibleRecursive(back_edge, finalized); 791 } 792 } 793 } else { 794 // Visit all predecessors. If one predecessor is part of the loop, this 795 // block is also part of this loop. 796 for (HBasicBlock* predecessor : block->GetPredecessors()) { 797 PopulateIrreducibleRecursive(predecessor, finalized); 798 if (!is_finalized && blocks_.IsBitSet(predecessor->GetBlockId())) { 799 block->SetInLoop(this); 800 blocks_.SetBit(block_id); 801 finalized->SetBit(block_id); 802 is_finalized = true; 803 } 804 } 805 } 806 807 // All predecessors have been recursively visited. Mark finalized if not marked yet. 808 if (!is_finalized) { 809 finalized->SetBit(block_id); 810 } 811 } 812 813 void HLoopInformation::Populate() { 814 DCHECK_EQ(blocks_.NumSetBits(), 0u) << "Loop information has already been populated"; 815 // Populate this loop: starting with the back edge, recursively add predecessors 816 // that are not already part of that loop. Set the header as part of the loop 817 // to end the recursion. 818 // This is a recursive implementation of the algorithm described in 819 // "Advanced Compiler Design & Implementation" (Muchnick) p192. 820 HGraph* graph = header_->GetGraph(); 821 blocks_.SetBit(header_->GetBlockId()); 822 header_->SetInLoop(this); 823 824 bool is_irreducible_loop = HasBackEdgeNotDominatedByHeader(); 825 826 if (is_irreducible_loop) { 827 // Allocate memory from local ScopedArenaAllocator. 828 ScopedArenaAllocator allocator(graph->GetArenaStack()); 829 ArenaBitVector visited(&allocator, 830 graph->GetBlocks().size(), 831 /* expandable= */ false, 832 kArenaAllocGraphBuilder); 833 visited.ClearAllBits(); 834 // Stop marking blocks at the loop header. 835 visited.SetBit(header_->GetBlockId()); 836 837 for (HBasicBlock* back_edge : GetBackEdges()) { 838 PopulateIrreducibleRecursive(back_edge, &visited); 839 } 840 } else { 841 for (HBasicBlock* back_edge : GetBackEdges()) { 842 PopulateRecursive(back_edge); 843 } 844 } 845 846 if (!is_irreducible_loop && graph->IsCompilingOsr()) { 847 // When compiling in OSR mode, all loops in the compiled method may be entered 848 // from the interpreter. We treat this OSR entry point just like an extra entry 849 // to an irreducible loop, so we need to mark the method's loops as irreducible. 850 // This does not apply to inlined loops which do not act as OSR entry points. 851 if (suspend_check_ == nullptr) { 852 // Just building the graph in OSR mode, this loop is not inlined. We never build an 853 // inner graph in OSR mode as we can do OSR transition only from the outer method. 854 is_irreducible_loop = true; 855 } else { 856 // Look at the suspend check's environment to determine if the loop was inlined. 857 DCHECK(suspend_check_->HasEnvironment()); 858 if (!suspend_check_->GetEnvironment()->IsFromInlinedInvoke()) { 859 is_irreducible_loop = true; 860 } 861 } 862 } 863 if (is_irreducible_loop) { 864 irreducible_ = true; 865 contains_irreducible_loop_ = true; 866 graph->SetHasIrreducibleLoops(true); 867 } 868 graph->SetHasLoops(true); 869 } 870 871 void HLoopInformation::PopulateInnerLoopUpwards(HLoopInformation* inner_loop) { 872 DCHECK(inner_loop->GetPreHeader()->GetLoopInformation() == this); 873 blocks_.Union(&inner_loop->blocks_); 874 HLoopInformation* outer_loop = GetPreHeader()->GetLoopInformation(); 875 if (outer_loop != nullptr) { 876 outer_loop->PopulateInnerLoopUpwards(this); 877 } 878 } 879 880 HBasicBlock* HLoopInformation::GetPreHeader() const { 881 HBasicBlock* block = header_->GetPredecessors()[0]; 882 DCHECK(irreducible_ || (block == header_->GetDominator())); 883 return block; 884 } 885 886 bool HLoopInformation::Contains(const HBasicBlock& block) const { 887 return blocks_.IsBitSet(block.GetBlockId()); 888 } 889 890 bool HLoopInformation::IsIn(const HLoopInformation& other) const { 891 return other.blocks_.IsBitSet(header_->GetBlockId()); 892 } 893 894 bool HLoopInformation::IsDefinedOutOfTheLoop(HInstruction* instruction) const { 895 return !blocks_.IsBitSet(instruction->GetBlock()->GetBlockId()); 896 } 897 898 size_t HLoopInformation::GetLifetimeEnd() const { 899 size_t last_position = 0; 900 for (HBasicBlock* back_edge : GetBackEdges()) { 901 last_position = std::max(back_edge->GetLifetimeEnd(), last_position); 902 } 903 return last_position; 904 } 905 906 bool HLoopInformation::HasBackEdgeNotDominatedByHeader() const { 907 for (HBasicBlock* back_edge : GetBackEdges()) { 908 DCHECK(back_edge->GetDominator() != nullptr); 909 if (!header_->Dominates(back_edge)) { 910 return true; 911 } 912 } 913 return false; 914 } 915 916 bool HLoopInformation::DominatesAllBackEdges(HBasicBlock* block) { 917 for (HBasicBlock* back_edge : GetBackEdges()) { 918 if (!block->Dominates(back_edge)) { 919 return false; 920 } 921 } 922 return true; 923 } 924 925 926 bool HLoopInformation::HasExitEdge() const { 927 // Determine if this loop has at least one exit edge. 928 HBlocksInLoopReversePostOrderIterator it_loop(*this); 929 for (; !it_loop.Done(); it_loop.Advance()) { 930 for (HBasicBlock* successor : it_loop.Current()->GetSuccessors()) { 931 if (!Contains(*successor)) { 932 return true; 933 } 934 } 935 } 936 return false; 937 } 938 939 bool HBasicBlock::Dominates(HBasicBlock* other) const { 940 // Walk up the dominator tree from `other`, to find out if `this` 941 // is an ancestor. 942 HBasicBlock* current = other; 943 while (current != nullptr) { 944 if (current == this) { 945 return true; 946 } 947 current = current->GetDominator(); 948 } 949 return false; 950 } 951 952 static void UpdateInputsUsers(HInstruction* instruction) { 953 HInputsRef inputs = instruction->GetInputs(); 954 for (size_t i = 0; i < inputs.size(); ++i) { 955 inputs[i]->AddUseAt(instruction, i); 956 } 957 // Environment should be created later. 958 DCHECK(!instruction->HasEnvironment()); 959 } 960 961 void HBasicBlock::ReplaceAndRemovePhiWith(HPhi* initial, HPhi* replacement) { 962 DCHECK(initial->GetBlock() == this); 963 InsertPhiAfter(replacement, initial); 964 initial->ReplaceWith(replacement); 965 RemovePhi(initial); 966 } 967 968 void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial, 969 HInstruction* replacement) { 970 DCHECK(initial->GetBlock() == this); 971 if (initial->IsControlFlow()) { 972 // We can only replace a control flow instruction with another control flow instruction. 973 DCHECK(replacement->IsControlFlow()); 974 DCHECK_EQ(replacement->GetId(), -1); 975 DCHECK_EQ(replacement->GetType(), DataType::Type::kVoid); 976 DCHECK_EQ(initial->GetBlock(), this); 977 DCHECK_EQ(initial->GetType(), DataType::Type::kVoid); 978 DCHECK(initial->GetUses().empty()); 979 DCHECK(initial->GetEnvUses().empty()); 980 replacement->SetBlock(this); 981 replacement->SetId(GetGraph()->GetNextInstructionId()); 982 instructions_.InsertInstructionBefore(replacement, initial); 983 UpdateInputsUsers(replacement); 984 } else { 985 InsertInstructionBefore(replacement, initial); 986 initial->ReplaceWith(replacement); 987 } 988 RemoveInstruction(initial); 989 } 990 991 static void Add(HInstructionList* instruction_list, 992 HBasicBlock* block, 993 HInstruction* instruction) { 994 DCHECK(instruction->GetBlock() == nullptr); 995 DCHECK_EQ(instruction->GetId(), -1); 996 instruction->SetBlock(block); 997 instruction->SetId(block->GetGraph()->GetNextInstructionId()); 998 UpdateInputsUsers(instruction); 999 instruction_list->AddInstruction(instruction); 1000 } 1001 1002 void HBasicBlock::AddInstruction(HInstruction* instruction) { 1003 Add(&instructions_, this, instruction); 1004 } 1005 1006 void HBasicBlock::AddPhi(HPhi* phi) { 1007 Add(&phis_, this, phi); 1008 } 1009 1010 void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { 1011 DCHECK(!cursor->IsPhi()); 1012 DCHECK(!instruction->IsPhi()); 1013 DCHECK_EQ(instruction->GetId(), -1); 1014 DCHECK_NE(cursor->GetId(), -1); 1015 DCHECK_EQ(cursor->GetBlock(), this); 1016 DCHECK(!instruction->IsControlFlow()); 1017 instruction->SetBlock(this); 1018 instruction->SetId(GetGraph()->GetNextInstructionId()); 1019 UpdateInputsUsers(instruction); 1020 instructions_.InsertInstructionBefore(instruction, cursor); 1021 } 1022 1023 void HBasicBlock::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) { 1024 DCHECK(!cursor->IsPhi()); 1025 DCHECK(!instruction->IsPhi()); 1026 DCHECK_EQ(instruction->GetId(), -1); 1027 DCHECK_NE(cursor->GetId(), -1); 1028 DCHECK_EQ(cursor->GetBlock(), this); 1029 DCHECK(!instruction->IsControlFlow()); 1030 DCHECK(!cursor->IsControlFlow()); 1031 instruction->SetBlock(this); 1032 instruction->SetId(GetGraph()->GetNextInstructionId()); 1033 UpdateInputsUsers(instruction); 1034 instructions_.InsertInstructionAfter(instruction, cursor); 1035 } 1036 1037 void HBasicBlock::InsertPhiAfter(HPhi* phi, HPhi* cursor) { 1038 DCHECK_EQ(phi->GetId(), -1); 1039 DCHECK_NE(cursor->GetId(), -1); 1040 DCHECK_EQ(cursor->GetBlock(), this); 1041 phi->SetBlock(this); 1042 phi->SetId(GetGraph()->GetNextInstructionId()); 1043 UpdateInputsUsers(phi); 1044 phis_.InsertInstructionAfter(phi, cursor); 1045 } 1046 1047 static void Remove(HInstructionList* instruction_list, 1048 HBasicBlock* block, 1049 HInstruction* instruction, 1050 bool ensure_safety) { 1051 DCHECK_EQ(block, instruction->GetBlock()); 1052 instruction->SetBlock(nullptr); 1053 instruction_list->RemoveInstruction(instruction); 1054 if (ensure_safety) { 1055 DCHECK(instruction->GetUses().empty()); 1056 DCHECK(instruction->GetEnvUses().empty()); 1057 RemoveAsUser(instruction); 1058 } 1059 } 1060 1061 void HBasicBlock::RemoveInstruction(HInstruction* instruction, bool ensure_safety) { 1062 DCHECK(!instruction->IsPhi()); 1063 Remove(&instructions_, this, instruction, ensure_safety); 1064 } 1065 1066 void HBasicBlock::RemovePhi(HPhi* phi, bool ensure_safety) { 1067 Remove(&phis_, this, phi, ensure_safety); 1068 } 1069 1070 void HBasicBlock::RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety) { 1071 if (instruction->IsPhi()) { 1072 RemovePhi(instruction->AsPhi(), ensure_safety); 1073 } else { 1074 RemoveInstruction(instruction, ensure_safety); 1075 } 1076 } 1077 1078 void HEnvironment::CopyFrom(ArrayRef<HInstruction* const> locals) { 1079 for (size_t i = 0; i < locals.size(); i++) { 1080 HInstruction* instruction = locals[i]; 1081 SetRawEnvAt(i, instruction); 1082 if (instruction != nullptr) { 1083 instruction->AddEnvUseAt(this, i); 1084 } 1085 } 1086 } 1087 1088 void HEnvironment::CopyFrom(HEnvironment* env) { 1089 for (size_t i = 0; i < env->Size(); i++) { 1090 HInstruction* instruction = env->GetInstructionAt(i); 1091 SetRawEnvAt(i, instruction); 1092 if (instruction != nullptr) { 1093 instruction->AddEnvUseAt(this, i); 1094 } 1095 } 1096 } 1097 1098 void HEnvironment::CopyFromWithLoopPhiAdjustment(HEnvironment* env, 1099 HBasicBlock* loop_header) { 1100 DCHECK(loop_header->IsLoopHeader()); 1101 for (size_t i = 0; i < env->Size(); i++) { 1102 HInstruction* instruction = env->GetInstructionAt(i); 1103 SetRawEnvAt(i, instruction); 1104 if (instruction == nullptr) { 1105 continue; 1106 } 1107 if (instruction->IsLoopHeaderPhi() && (instruction->GetBlock() == loop_header)) { 1108 // At the end of the loop pre-header, the corresponding value for instruction 1109 // is the first input of the phi. 1110 HInstruction* initial = instruction->AsPhi()->InputAt(0); 1111 SetRawEnvAt(i, initial); 1112 initial->AddEnvUseAt(this, i); 1113 } else { 1114 instruction->AddEnvUseAt(this, i); 1115 } 1116 } 1117 } 1118 1119 void HEnvironment::RemoveAsUserOfInput(size_t index) const { 1120 const HUserRecord<HEnvironment*>& env_use = vregs_[index]; 1121 HInstruction* user = env_use.GetInstruction(); 1122 auto before_env_use_node = env_use.GetBeforeUseNode(); 1123 user->env_uses_.erase_after(before_env_use_node); 1124 user->FixUpUserRecordsAfterEnvUseRemoval(before_env_use_node); 1125 } 1126 1127 void HEnvironment::ReplaceInput(HInstruction* replacement, size_t index) { 1128 const HUserRecord<HEnvironment*>& env_use_record = vregs_[index]; 1129 HInstruction* orig_instr = env_use_record.GetInstruction(); 1130 1131 DCHECK(orig_instr != replacement); 1132 1133 HUseList<HEnvironment*>::iterator before_use_node = env_use_record.GetBeforeUseNode(); 1134 // Note: fixup_end remains valid across splice_after(). 1135 auto fixup_end = replacement->env_uses_.empty() ? replacement->env_uses_.begin() 1136 : ++replacement->env_uses_.begin(); 1137 replacement->env_uses_.splice_after(replacement->env_uses_.before_begin(), 1138 env_use_record.GetInstruction()->env_uses_, 1139 before_use_node); 1140 replacement->FixUpUserRecordsAfterEnvUseInsertion(fixup_end); 1141 orig_instr->FixUpUserRecordsAfterEnvUseRemoval(before_use_node); 1142 } 1143 1144 HInstruction* HInstruction::GetNextDisregardingMoves() const { 1145 HInstruction* next = GetNext(); 1146 while (next != nullptr && next->IsParallelMove()) { 1147 next = next->GetNext(); 1148 } 1149 return next; 1150 } 1151 1152 HInstruction* HInstruction::GetPreviousDisregardingMoves() const { 1153 HInstruction* previous = GetPrevious(); 1154 while (previous != nullptr && previous->IsParallelMove()) { 1155 previous = previous->GetPrevious(); 1156 } 1157 return previous; 1158 } 1159 1160 void HInstructionList::AddInstruction(HInstruction* instruction) { 1161 if (first_instruction_ == nullptr) { 1162 DCHECK(last_instruction_ == nullptr); 1163 first_instruction_ = last_instruction_ = instruction; 1164 } else { 1165 DCHECK(last_instruction_ != nullptr); 1166 last_instruction_->next_ = instruction; 1167 instruction->previous_ = last_instruction_; 1168 last_instruction_ = instruction; 1169 } 1170 } 1171 1172 void HInstructionList::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { 1173 DCHECK(Contains(cursor)); 1174 if (cursor == first_instruction_) { 1175 cursor->previous_ = instruction; 1176 instruction->next_ = cursor; 1177 first_instruction_ = instruction; 1178 } else { 1179 instruction->previous_ = cursor->previous_; 1180 instruction->next_ = cursor; 1181 cursor->previous_ = instruction; 1182 instruction->previous_->next_ = instruction; 1183 } 1184 } 1185 1186 void HInstructionList::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) { 1187 DCHECK(Contains(cursor)); 1188 if (cursor == last_instruction_) { 1189 cursor->next_ = instruction; 1190 instruction->previous_ = cursor; 1191 last_instruction_ = instruction; 1192 } else { 1193 instruction->next_ = cursor->next_; 1194 instruction->previous_ = cursor; 1195 cursor->next_ = instruction; 1196 instruction->next_->previous_ = instruction; 1197 } 1198 } 1199 1200 void HInstructionList::RemoveInstruction(HInstruction* instruction) { 1201 if (instruction->previous_ != nullptr) { 1202 instruction->previous_->next_ = instruction->next_; 1203 } 1204 if (instruction->next_ != nullptr) { 1205 instruction->next_->previous_ = instruction->previous_; 1206 } 1207 if (instruction == first_instruction_) { 1208 first_instruction_ = instruction->next_; 1209 } 1210 if (instruction == last_instruction_) { 1211 last_instruction_ = instruction->previous_; 1212 } 1213 } 1214 1215 bool HInstructionList::Contains(HInstruction* instruction) const { 1216 for (HInstructionIterator it(*this); !it.Done(); it.Advance()) { 1217 if (it.Current() == instruction) { 1218 return true; 1219 } 1220 } 1221 return false; 1222 } 1223 1224 bool HInstructionList::FoundBefore(const HInstruction* instruction1, 1225 const HInstruction* instruction2) const { 1226 DCHECK_EQ(instruction1->GetBlock(), instruction2->GetBlock()); 1227 for (HInstructionIterator it(*this); !it.Done(); it.Advance()) { 1228 if (it.Current() == instruction1) { 1229 return true; 1230 } 1231 if (it.Current() == instruction2) { 1232 return false; 1233 } 1234 } 1235 LOG(FATAL) << "Did not find an order between two instructions of the same block."; 1236 UNREACHABLE(); 1237 } 1238 1239 bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const { 1240 if (other_instruction == this) { 1241 // An instruction does not strictly dominate itself. 1242 return false; 1243 } 1244 HBasicBlock* block = GetBlock(); 1245 HBasicBlock* other_block = other_instruction->GetBlock(); 1246 if (block != other_block) { 1247 return GetBlock()->Dominates(other_instruction->GetBlock()); 1248 } else { 1249 // If both instructions are in the same block, ensure this 1250 // instruction comes before `other_instruction`. 1251 if (IsPhi()) { 1252 if (!other_instruction->IsPhi()) { 1253 // Phis appear before non phi-instructions so this instruction 1254 // dominates `other_instruction`. 1255 return true; 1256 } else { 1257 // There is no order among phis. 1258 LOG(FATAL) << "There is no dominance between phis of a same block."; 1259 UNREACHABLE(); 1260 } 1261 } else { 1262 // `this` is not a phi. 1263 if (other_instruction->IsPhi()) { 1264 // Phis appear before non phi-instructions so this instruction 1265 // does not dominate `other_instruction`. 1266 return false; 1267 } else { 1268 // Check whether this instruction comes before 1269 // `other_instruction` in the instruction list. 1270 return block->GetInstructions().FoundBefore(this, other_instruction); 1271 } 1272 } 1273 } 1274 } 1275 1276 void HInstruction::RemoveEnvironment() { 1277 RemoveEnvironmentUses(this); 1278 environment_ = nullptr; 1279 } 1280 1281 void HInstruction::ReplaceWith(HInstruction* other) { 1282 DCHECK(other != nullptr); 1283 // Note: fixup_end remains valid across splice_after(). 1284 auto fixup_end = other->uses_.empty() ? other->uses_.begin() : ++other->uses_.begin(); 1285 other->uses_.splice_after(other->uses_.before_begin(), uses_); 1286 other->FixUpUserRecordsAfterUseInsertion(fixup_end); 1287 1288 // Note: env_fixup_end remains valid across splice_after(). 1289 auto env_fixup_end = 1290 other->env_uses_.empty() ? other->env_uses_.begin() : ++other->env_uses_.begin(); 1291 other->env_uses_.splice_after(other->env_uses_.before_begin(), env_uses_); 1292 other->FixUpUserRecordsAfterEnvUseInsertion(env_fixup_end); 1293 1294 DCHECK(uses_.empty()); 1295 DCHECK(env_uses_.empty()); 1296 } 1297 1298 void HInstruction::ReplaceUsesDominatedBy(HInstruction* dominator, HInstruction* replacement) { 1299 const HUseList<HInstruction*>& uses = GetUses(); 1300 for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) { 1301 HInstruction* user = it->GetUser(); 1302 size_t index = it->GetIndex(); 1303 // Increment `it` now because `*it` may disappear thanks to user->ReplaceInput(). 1304 ++it; 1305 if (dominator->StrictlyDominates(user)) { 1306 user->ReplaceInput(replacement, index); 1307 } else if (user->IsPhi() && !user->AsPhi()->IsCatchPhi()) { 1308 // If the input flows from a block dominated by `dominator`, we can replace it. 1309 // We do not perform this for catch phis as we don't have control flow support 1310 // for their inputs. 1311 const ArenaVector<HBasicBlock*>& predecessors = user->GetBlock()->GetPredecessors(); 1312 HBasicBlock* predecessor = predecessors[index]; 1313 if (dominator->GetBlock()->Dominates(predecessor)) { 1314 user->ReplaceInput(replacement, index); 1315 } 1316 } 1317 } 1318 } 1319 1320 void HInstruction::ReplaceEnvUsesDominatedBy(HInstruction* dominator, HInstruction* replacement) { 1321 const HUseList<HEnvironment*>& uses = GetEnvUses(); 1322 for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) { 1323 HEnvironment* user = it->GetUser(); 1324 size_t index = it->GetIndex(); 1325 // Increment `it` now because `*it` may disappear thanks to user->ReplaceInput(). 1326 ++it; 1327 if (dominator->StrictlyDominates(user->GetHolder())) { 1328 user->ReplaceInput(replacement, index); 1329 } 1330 } 1331 } 1332 1333 void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) { 1334 HUserRecord<HInstruction*> input_use = InputRecordAt(index); 1335 if (input_use.GetInstruction() == replacement) { 1336 // Nothing to do. 1337 return; 1338 } 1339 HUseList<HInstruction*>::iterator before_use_node = input_use.GetBeforeUseNode(); 1340 // Note: fixup_end remains valid across splice_after(). 1341 auto fixup_end = 1342 replacement->uses_.empty() ? replacement->uses_.begin() : ++replacement->uses_.begin(); 1343 replacement->uses_.splice_after(replacement->uses_.before_begin(), 1344 input_use.GetInstruction()->uses_, 1345 before_use_node); 1346 replacement->FixUpUserRecordsAfterUseInsertion(fixup_end); 1347 input_use.GetInstruction()->FixUpUserRecordsAfterUseRemoval(before_use_node); 1348 } 1349 1350 size_t HInstruction::EnvironmentSize() const { 1351 return HasEnvironment() ? environment_->Size() : 0; 1352 } 1353 1354 void HVariableInputSizeInstruction::AddInput(HInstruction* input) { 1355 DCHECK(input->GetBlock() != nullptr); 1356 inputs_.push_back(HUserRecord<HInstruction*>(input)); 1357 input->AddUseAt(this, inputs_.size() - 1); 1358 } 1359 1360 void HVariableInputSizeInstruction::InsertInputAt(size_t index, HInstruction* input) { 1361 inputs_.insert(inputs_.begin() + index, HUserRecord<HInstruction*>(input)); 1362 input->AddUseAt(this, index); 1363 // Update indexes in use nodes of inputs that have been pushed further back by the insert(). 1364 for (size_t i = index + 1u, e = inputs_.size(); i < e; ++i) { 1365 DCHECK_EQ(inputs_[i].GetUseNode()->GetIndex(), i - 1u); 1366 inputs_[i].GetUseNode()->SetIndex(i); 1367 } 1368 } 1369 1370 void HVariableInputSizeInstruction::RemoveInputAt(size_t index) { 1371 RemoveAsUserOfInput(index); 1372 inputs_.erase(inputs_.begin() + index); 1373 // Update indexes in use nodes of inputs that have been pulled forward by the erase(). 1374 for (size_t i = index, e = inputs_.size(); i < e; ++i) { 1375 DCHECK_EQ(inputs_[i].GetUseNode()->GetIndex(), i + 1u); 1376 inputs_[i].GetUseNode()->SetIndex(i); 1377 } 1378 } 1379 1380 void HVariableInputSizeInstruction::RemoveAllInputs() { 1381 RemoveAsUserOfAllInputs(); 1382 DCHECK(!HasNonEnvironmentUses()); 1383 1384 inputs_.clear(); 1385 DCHECK_EQ(0u, InputCount()); 1386 } 1387 1388 size_t HConstructorFence::RemoveConstructorFences(HInstruction* instruction) { 1389 DCHECK(instruction->GetBlock() != nullptr); 1390 // Removing constructor fences only makes sense for instructions with an object return type. 1391 DCHECK_EQ(DataType::Type::kReference, instruction->GetType()); 1392 1393 // Return how many instructions were removed for statistic purposes. 1394 size_t remove_count = 0; 1395 1396 // Efficient implementation that simultaneously (in one pass): 1397 // * Scans the uses list for all constructor fences. 1398 // * Deletes that constructor fence from the uses list of `instruction`. 1399 // * Deletes `instruction` from the constructor fence's inputs. 1400 // * Deletes the constructor fence if it now has 0 inputs. 1401 1402 const HUseList<HInstruction*>& uses = instruction->GetUses(); 1403 // Warning: Although this is "const", we might mutate the list when calling RemoveInputAt. 1404 for (auto it = uses.begin(), end = uses.end(); it != end; ) { 1405 const HUseListNode<HInstruction*>& use_node = *it; 1406 HInstruction* const use_instruction = use_node.GetUser(); 1407 1408 // Advance the iterator immediately once we fetch the use_node. 1409 // Warning: If the input is removed, the current iterator becomes invalid. 1410 ++it; 1411 1412 if (use_instruction->IsConstructorFence()) { 1413 HConstructorFence* ctor_fence = use_instruction->AsConstructorFence(); 1414 size_t input_index = use_node.GetIndex(); 1415 1416 // Process the candidate instruction for removal 1417 // from the graph. 1418 1419 // Constructor fence instructions are never 1420 // used by other instructions. 1421 // 1422 // If we wanted to make this more generic, it 1423 // could be a runtime if statement. 1424 DCHECK(!ctor_fence->HasUses()); 1425 1426 // A constructor fence's return type is "kPrimVoid" 1427 // and therefore it can't have any environment uses. 1428 DCHECK(!ctor_fence->HasEnvironmentUses()); 1429 1430 // Remove the inputs first, otherwise removing the instruction 1431 // will try to remove its uses while we are already removing uses 1432 // and this operation will fail. 1433 DCHECK_EQ(instruction, ctor_fence->InputAt(input_index)); 1434 1435 // Removing the input will also remove the `use_node`. 1436 // (Do not look at `use_node` after this, it will be a dangling reference). 1437 ctor_fence->RemoveInputAt(input_index); 1438 1439 // Once all inputs are removed, the fence is considered dead and 1440 // is removed. 1441 if (ctor_fence->InputCount() == 0u) { 1442 ctor_fence->GetBlock()->RemoveInstruction(ctor_fence); 1443 ++remove_count; 1444 } 1445 } 1446 } 1447 1448 if (kIsDebugBuild) { 1449 // Post-condition checks: 1450 // * None of the uses of `instruction` are a constructor fence. 1451 // * The `instruction` itself did not get removed from a block. 1452 for (const HUseListNode<HInstruction*>& use_node : instruction->GetUses()) { 1453 CHECK(!use_node.GetUser()->IsConstructorFence()); 1454 } 1455 CHECK(instruction->GetBlock() != nullptr); 1456 } 1457 1458 return remove_count; 1459 } 1460 1461 void HConstructorFence::Merge(HConstructorFence* other) { 1462 // Do not delete yourself from the graph. 1463 DCHECK(this != other); 1464 // Don't try to merge with an instruction not associated with a block. 1465 DCHECK(other->GetBlock() != nullptr); 1466 // A constructor fence's return type is "kPrimVoid" 1467 // and therefore it cannot have any environment uses. 1468 DCHECK(!other->HasEnvironmentUses()); 1469 1470 auto has_input = [](HInstruction* haystack, HInstruction* needle) { 1471 // Check if `haystack` has `needle` as any of its inputs. 1472 for (size_t input_count = 0; input_count < haystack->InputCount(); ++input_count) { 1473 if (haystack->InputAt(input_count) == needle) { 1474 return true; 1475 } 1476 } 1477 return false; 1478 }; 1479 1480 // Add any inputs from `other` into `this` if it wasn't already an input. 1481 for (size_t input_count = 0; input_count < other->InputCount(); ++input_count) { 1482 HInstruction* other_input = other->InputAt(input_count); 1483 if (!has_input(this, other_input)) { 1484 AddInput(other_input); 1485 } 1486 } 1487 1488 other->GetBlock()->RemoveInstruction(other); 1489 } 1490 1491 HInstruction* HConstructorFence::GetAssociatedAllocation(bool ignore_inputs) { 1492 HInstruction* new_instance_inst = GetPrevious(); 1493 // Check if the immediately preceding instruction is a new-instance/new-array. 1494 // Otherwise this fence is for protecting final fields. 1495 if (new_instance_inst != nullptr && 1496 (new_instance_inst->IsNewInstance() || new_instance_inst->IsNewArray())) { 1497 if (ignore_inputs) { 1498 // If inputs are ignored, simply check if the predecessor is 1499 // *any* HNewInstance/HNewArray. 1500 // 1501 // Inputs are normally only ignored for prepare_for_register_allocation, 1502 // at which point *any* prior HNewInstance/Array can be considered 1503 // associated. 1504 return new_instance_inst; 1505 } else { 1506 // Normal case: There must be exactly 1 input and the previous instruction 1507 // must be that input. 1508 if (InputCount() == 1u && InputAt(0) == new_instance_inst) { 1509 return new_instance_inst; 1510 } 1511 } 1512 } 1513 return nullptr; 1514 } 1515 1516 #define DEFINE_ACCEPT(name, super) \ 1517 void H##name::Accept(HGraphVisitor* visitor) { \ 1518 visitor->Visit##name(this); \ 1519 } 1520 1521 FOR_EACH_CONCRETE_INSTRUCTION(DEFINE_ACCEPT) 1522 1523 #undef DEFINE_ACCEPT 1524 1525 void HGraphVisitor::VisitInsertionOrder() { 1526 const ArenaVector<HBasicBlock*>& blocks = graph_->GetBlocks(); 1527 for (HBasicBlock* block : blocks) { 1528 if (block != nullptr) { 1529 VisitBasicBlock(block); 1530 } 1531 } 1532 } 1533 1534 void HGraphVisitor::VisitReversePostOrder() { 1535 for (HBasicBlock* block : graph_->GetReversePostOrder()) { 1536 VisitBasicBlock(block); 1537 } 1538 } 1539 1540 void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) { 1541 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 1542 it.Current()->Accept(this); 1543 } 1544 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 1545 it.Current()->Accept(this); 1546 } 1547 } 1548 1549 HConstant* HTypeConversion::TryStaticEvaluation() const { 1550 HGraph* graph = GetBlock()->GetGraph(); 1551 if (GetInput()->IsIntConstant()) { 1552 int32_t value = GetInput()->AsIntConstant()->GetValue(); 1553 switch (GetResultType()) { 1554 case DataType::Type::kInt8: 1555 return graph->GetIntConstant(static_cast<int8_t>(value), GetDexPc()); 1556 case DataType::Type::kUint8: 1557 return graph->GetIntConstant(static_cast<uint8_t>(value), GetDexPc()); 1558 case DataType::Type::kInt16: 1559 return graph->GetIntConstant(static_cast<int16_t>(value), GetDexPc()); 1560 case DataType::Type::kUint16: 1561 return graph->GetIntConstant(static_cast<uint16_t>(value), GetDexPc()); 1562 case DataType::Type::kInt64: 1563 return graph->GetLongConstant(static_cast<int64_t>(value), GetDexPc()); 1564 case DataType::Type::kFloat32: 1565 return graph->GetFloatConstant(static_cast<float>(value), GetDexPc()); 1566 case DataType::Type::kFloat64: 1567 return graph->GetDoubleConstant(static_cast<double>(value), GetDexPc()); 1568 default: 1569 return nullptr; 1570 } 1571 } else if (GetInput()->IsLongConstant()) { 1572 int64_t value = GetInput()->AsLongConstant()->GetValue(); 1573 switch (GetResultType()) { 1574 case DataType::Type::kInt8: 1575 return graph->GetIntConstant(static_cast<int8_t>(value), GetDexPc()); 1576 case DataType::Type::kUint8: 1577 return graph->GetIntConstant(static_cast<uint8_t>(value), GetDexPc()); 1578 case DataType::Type::kInt16: 1579 return graph->GetIntConstant(static_cast<int16_t>(value), GetDexPc()); 1580 case DataType::Type::kUint16: 1581 return graph->GetIntConstant(static_cast<uint16_t>(value), GetDexPc()); 1582 case DataType::Type::kInt32: 1583 return graph->GetIntConstant(static_cast<int32_t>(value), GetDexPc()); 1584 case DataType::Type::kFloat32: 1585 return graph->GetFloatConstant(static_cast<float>(value), GetDexPc()); 1586 case DataType::Type::kFloat64: 1587 return graph->GetDoubleConstant(static_cast<double>(value), GetDexPc()); 1588 default: 1589 return nullptr; 1590 } 1591 } else if (GetInput()->IsFloatConstant()) { 1592 float value = GetInput()->AsFloatConstant()->GetValue(); 1593 switch (GetResultType()) { 1594 case DataType::Type::kInt32: 1595 if (std::isnan(value)) 1596 return graph->GetIntConstant(0, GetDexPc()); 1597 if (value >= kPrimIntMax) 1598 return graph->GetIntConstant(kPrimIntMax, GetDexPc()); 1599 if (value <= kPrimIntMin) 1600 return graph->GetIntConstant(kPrimIntMin, GetDexPc()); 1601 return graph->GetIntConstant(static_cast<int32_t>(value), GetDexPc()); 1602 case DataType::Type::kInt64: 1603 if (std::isnan(value)) 1604 return graph->GetLongConstant(0, GetDexPc()); 1605 if (value >= kPrimLongMax) 1606 return graph->GetLongConstant(kPrimLongMax, GetDexPc()); 1607 if (value <= kPrimLongMin) 1608 return graph->GetLongConstant(kPrimLongMin, GetDexPc()); 1609 return graph->GetLongConstant(static_cast<int64_t>(value), GetDexPc()); 1610 case DataType::Type::kFloat64: 1611 return graph->GetDoubleConstant(static_cast<double>(value), GetDexPc()); 1612 default: 1613 return nullptr; 1614 } 1615 } else if (GetInput()->IsDoubleConstant()) { 1616 double value = GetInput()->AsDoubleConstant()->GetValue(); 1617 switch (GetResultType()) { 1618 case DataType::Type::kInt32: 1619 if (std::isnan(value)) 1620 return graph->GetIntConstant(0, GetDexPc()); 1621 if (value >= kPrimIntMax) 1622 return graph->GetIntConstant(kPrimIntMax, GetDexPc()); 1623 if (value <= kPrimLongMin) 1624 return graph->GetIntConstant(kPrimIntMin, GetDexPc()); 1625 return graph->GetIntConstant(static_cast<int32_t>(value), GetDexPc()); 1626 case DataType::Type::kInt64: 1627 if (std::isnan(value)) 1628 return graph->GetLongConstant(0, GetDexPc()); 1629 if (value >= kPrimLongMax) 1630 return graph->GetLongConstant(kPrimLongMax, GetDexPc()); 1631 if (value <= kPrimLongMin) 1632 return graph->GetLongConstant(kPrimLongMin, GetDexPc()); 1633 return graph->GetLongConstant(static_cast<int64_t>(value), GetDexPc()); 1634 case DataType::Type::kFloat32: 1635 return graph->GetFloatConstant(static_cast<float>(value), GetDexPc()); 1636 default: 1637 return nullptr; 1638 } 1639 } 1640 return nullptr; 1641 } 1642 1643 HConstant* HUnaryOperation::TryStaticEvaluation() const { 1644 if (GetInput()->IsIntConstant()) { 1645 return Evaluate(GetInput()->AsIntConstant()); 1646 } else if (GetInput()->IsLongConstant()) { 1647 return Evaluate(GetInput()->AsLongConstant()); 1648 } else if (kEnableFloatingPointStaticEvaluation) { 1649 if (GetInput()->IsFloatConstant()) { 1650 return Evaluate(GetInput()->AsFloatConstant()); 1651 } else if (GetInput()->IsDoubleConstant()) { 1652 return Evaluate(GetInput()->AsDoubleConstant()); 1653 } 1654 } 1655 return nullptr; 1656 } 1657 1658 HConstant* HBinaryOperation::TryStaticEvaluation() const { 1659 if (GetLeft()->IsIntConstant() && GetRight()->IsIntConstant()) { 1660 return Evaluate(GetLeft()->AsIntConstant(), GetRight()->AsIntConstant()); 1661 } else if (GetLeft()->IsLongConstant()) { 1662 if (GetRight()->IsIntConstant()) { 1663 // The binop(long, int) case is only valid for shifts and rotations. 1664 DCHECK(IsShl() || IsShr() || IsUShr() || IsRor()) << DebugName(); 1665 return Evaluate(GetLeft()->AsLongConstant(), GetRight()->AsIntConstant()); 1666 } else if (GetRight()->IsLongConstant()) { 1667 return Evaluate(GetLeft()->AsLongConstant(), GetRight()->AsLongConstant()); 1668 } 1669 } else if (GetLeft()->IsNullConstant() && GetRight()->IsNullConstant()) { 1670 // The binop(null, null) case is only valid for equal and not-equal conditions. 1671 DCHECK(IsEqual() || IsNotEqual()) << DebugName(); 1672 return Evaluate(GetLeft()->AsNullConstant(), GetRight()->AsNullConstant()); 1673 } else if (kEnableFloatingPointStaticEvaluation) { 1674 if (GetLeft()->IsFloatConstant() && GetRight()->IsFloatConstant()) { 1675 return Evaluate(GetLeft()->AsFloatConstant(), GetRight()->AsFloatConstant()); 1676 } else if (GetLeft()->IsDoubleConstant() && GetRight()->IsDoubleConstant()) { 1677 return Evaluate(GetLeft()->AsDoubleConstant(), GetRight()->AsDoubleConstant()); 1678 } 1679 } 1680 return nullptr; 1681 } 1682 1683 HConstant* HBinaryOperation::GetConstantRight() const { 1684 if (GetRight()->IsConstant()) { 1685 return GetRight()->AsConstant(); 1686 } else if (IsCommutative() && GetLeft()->IsConstant()) { 1687 return GetLeft()->AsConstant(); 1688 } else { 1689 return nullptr; 1690 } 1691 } 1692 1693 // If `GetConstantRight()` returns one of the input, this returns the other 1694 // one. Otherwise it returns null. 1695 HInstruction* HBinaryOperation::GetLeastConstantLeft() const { 1696 HInstruction* most_constant_right = GetConstantRight(); 1697 if (most_constant_right == nullptr) { 1698 return nullptr; 1699 } else if (most_constant_right == GetLeft()) { 1700 return GetRight(); 1701 } else { 1702 return GetLeft(); 1703 } 1704 } 1705 1706 std::ostream& operator<<(std::ostream& os, const ComparisonBias& rhs) { 1707 switch (rhs) { 1708 case ComparisonBias::kNoBias: 1709 return os << "no_bias"; 1710 case ComparisonBias::kGtBias: 1711 return os << "gt_bias"; 1712 case ComparisonBias::kLtBias: 1713 return os << "lt_bias"; 1714 default: 1715 LOG(FATAL) << "Unknown ComparisonBias: " << static_cast<int>(rhs); 1716 UNREACHABLE(); 1717 } 1718 } 1719 1720 bool HCondition::IsBeforeWhenDisregardMoves(HInstruction* instruction) const { 1721 return this == instruction->GetPreviousDisregardingMoves(); 1722 } 1723 1724 bool HInstruction::Equals(const HInstruction* other) const { 1725 if (GetKind() != other->GetKind()) return false; 1726 if (GetType() != other->GetType()) return false; 1727 if (!InstructionDataEquals(other)) return false; 1728 HConstInputsRef inputs = GetInputs(); 1729 HConstInputsRef other_inputs = other->GetInputs(); 1730 if (inputs.size() != other_inputs.size()) return false; 1731 for (size_t i = 0; i != inputs.size(); ++i) { 1732 if (inputs[i] != other_inputs[i]) return false; 1733 } 1734 1735 DCHECK_EQ(ComputeHashCode(), other->ComputeHashCode()); 1736 return true; 1737 } 1738 1739 std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs) { 1740 #define DECLARE_CASE(type, super) case HInstruction::k##type: os << #type; break; 1741 switch (rhs) { 1742 FOR_EACH_CONCRETE_INSTRUCTION(DECLARE_CASE) 1743 default: 1744 os << "Unknown instruction kind " << static_cast<int>(rhs); 1745 break; 1746 } 1747 #undef DECLARE_CASE 1748 return os; 1749 } 1750 1751 void HInstruction::MoveBefore(HInstruction* cursor, bool do_checks) { 1752 if (do_checks) { 1753 DCHECK(!IsPhi()); 1754 DCHECK(!IsControlFlow()); 1755 DCHECK(CanBeMoved() || 1756 // HShouldDeoptimizeFlag can only be moved by CHAGuardOptimization. 1757 IsShouldDeoptimizeFlag()); 1758 DCHECK(!cursor->IsPhi()); 1759 } 1760 1761 next_->previous_ = previous_; 1762 if (previous_ != nullptr) { 1763 previous_->next_ = next_; 1764 } 1765 if (block_->instructions_.first_instruction_ == this) { 1766 block_->instructions_.first_instruction_ = next_; 1767 } 1768 DCHECK_NE(block_->instructions_.last_instruction_, this); 1769 1770 previous_ = cursor->previous_; 1771 if (previous_ != nullptr) { 1772 previous_->next_ = this; 1773 } 1774 next_ = cursor; 1775 cursor->previous_ = this; 1776 block_ = cursor->block_; 1777 1778 if (block_->instructions_.first_instruction_ == cursor) { 1779 block_->instructions_.first_instruction_ = this; 1780 } 1781 } 1782 1783 void HInstruction::MoveBeforeFirstUserAndOutOfLoops() { 1784 DCHECK(!CanThrow()); 1785 DCHECK(!HasSideEffects()); 1786 DCHECK(!HasEnvironmentUses()); 1787 DCHECK(HasNonEnvironmentUses()); 1788 DCHECK(!IsPhi()); // Makes no sense for Phi. 1789 DCHECK_EQ(InputCount(), 0u); 1790 1791 // Find the target block. 1792 auto uses_it = GetUses().begin(); 1793 auto uses_end = GetUses().end(); 1794 HBasicBlock* target_block = uses_it->GetUser()->GetBlock(); 1795 ++uses_it; 1796 while (uses_it != uses_end && uses_it->GetUser()->GetBlock() == target_block) { 1797 ++uses_it; 1798 } 1799 if (uses_it != uses_end) { 1800 // This instruction has uses in two or more blocks. Find the common dominator. 1801 CommonDominator finder(target_block); 1802 for (; uses_it != uses_end; ++uses_it) { 1803 finder.Update(uses_it->GetUser()->GetBlock()); 1804 } 1805 target_block = finder.Get(); 1806 DCHECK(target_block != nullptr); 1807 } 1808 // Move to the first dominator not in a loop. 1809 while (target_block->IsInLoop()) { 1810 target_block = target_block->GetDominator(); 1811 DCHECK(target_block != nullptr); 1812 } 1813 1814 // Find insertion position. 1815 HInstruction* insert_pos = nullptr; 1816 for (const HUseListNode<HInstruction*>& use : GetUses()) { 1817 if (use.GetUser()->GetBlock() == target_block && 1818 (insert_pos == nullptr || use.GetUser()->StrictlyDominates(insert_pos))) { 1819 insert_pos = use.GetUser(); 1820 } 1821 } 1822 if (insert_pos == nullptr) { 1823 // No user in `target_block`, insert before the control flow instruction. 1824 insert_pos = target_block->GetLastInstruction(); 1825 DCHECK(insert_pos->IsControlFlow()); 1826 // Avoid splitting HCondition from HIf to prevent unnecessary materialization. 1827 if (insert_pos->IsIf()) { 1828 HInstruction* if_input = insert_pos->AsIf()->InputAt(0); 1829 if (if_input == insert_pos->GetPrevious()) { 1830 insert_pos = if_input; 1831 } 1832 } 1833 } 1834 MoveBefore(insert_pos); 1835 } 1836 1837 HBasicBlock* HBasicBlock::SplitBefore(HInstruction* cursor) { 1838 DCHECK(!graph_->IsInSsaForm()) << "Support for SSA form not implemented."; 1839 DCHECK_EQ(cursor->GetBlock(), this); 1840 1841 HBasicBlock* new_block = 1842 new (GetGraph()->GetAllocator()) HBasicBlock(GetGraph(), cursor->GetDexPc()); 1843 new_block->instructions_.first_instruction_ = cursor; 1844 new_block->instructions_.last_instruction_ = instructions_.last_instruction_; 1845 instructions_.last_instruction_ = cursor->previous_; 1846 if (cursor->previous_ == nullptr) { 1847 instructions_.first_instruction_ = nullptr; 1848 } else { 1849 cursor->previous_->next_ = nullptr; 1850 cursor->previous_ = nullptr; 1851 } 1852 1853 new_block->instructions_.SetBlockOfInstructions(new_block); 1854 AddInstruction(new (GetGraph()->GetAllocator()) HGoto(new_block->GetDexPc())); 1855 1856 for (HBasicBlock* successor : GetSuccessors()) { 1857 successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block; 1858 } 1859 new_block->successors_.swap(successors_); 1860 DCHECK(successors_.empty()); 1861 AddSuccessor(new_block); 1862 1863 GetGraph()->AddBlock(new_block); 1864 return new_block; 1865 } 1866 1867 HBasicBlock* HBasicBlock::CreateImmediateDominator() { 1868 DCHECK(!graph_->IsInSsaForm()) << "Support for SSA form not implemented."; 1869 DCHECK(!IsCatchBlock()) << "Support for updating try/catch information not implemented."; 1870 1871 HBasicBlock* new_block = new (GetGraph()->GetAllocator()) HBasicBlock(GetGraph(), GetDexPc()); 1872 1873 for (HBasicBlock* predecessor : GetPredecessors()) { 1874 predecessor->successors_[predecessor->GetSuccessorIndexOf(this)] = new_block; 1875 } 1876 new_block->predecessors_.swap(predecessors_); 1877 DCHECK(predecessors_.empty()); 1878 AddPredecessor(new_block); 1879 1880 GetGraph()->AddBlock(new_block); 1881 return new_block; 1882 } 1883 1884 HBasicBlock* HBasicBlock::SplitBeforeForInlining(HInstruction* cursor) { 1885 DCHECK_EQ(cursor->GetBlock(), this); 1886 1887 HBasicBlock* new_block = 1888 new (GetGraph()->GetAllocator()) HBasicBlock(GetGraph(), cursor->GetDexPc()); 1889 new_block->instructions_.first_instruction_ = cursor; 1890 new_block->instructions_.last_instruction_ = instructions_.last_instruction_; 1891 instructions_.last_instruction_ = cursor->previous_; 1892 if (cursor->previous_ == nullptr) { 1893 instructions_.first_instruction_ = nullptr; 1894 } else { 1895 cursor->previous_->next_ = nullptr; 1896 cursor->previous_ = nullptr; 1897 } 1898 1899 new_block->instructions_.SetBlockOfInstructions(new_block); 1900 1901 for (HBasicBlock* successor : GetSuccessors()) { 1902 successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block; 1903 } 1904 new_block->successors_.swap(successors_); 1905 DCHECK(successors_.empty()); 1906 1907 for (HBasicBlock* dominated : GetDominatedBlocks()) { 1908 dominated->dominator_ = new_block; 1909 } 1910 new_block->dominated_blocks_.swap(dominated_blocks_); 1911 DCHECK(dominated_blocks_.empty()); 1912 return new_block; 1913 } 1914 1915 HBasicBlock* HBasicBlock::SplitAfterForInlining(HInstruction* cursor) { 1916 DCHECK(!cursor->IsControlFlow()); 1917 DCHECK_NE(instructions_.last_instruction_, cursor); 1918 DCHECK_EQ(cursor->GetBlock(), this); 1919 1920 HBasicBlock* new_block = new (GetGraph()->GetAllocator()) HBasicBlock(GetGraph(), GetDexPc()); 1921 new_block->instructions_.first_instruction_ = cursor->GetNext(); 1922 new_block->instructions_.last_instruction_ = instructions_.last_instruction_; 1923 cursor->next_->previous_ = nullptr; 1924 cursor->next_ = nullptr; 1925 instructions_.last_instruction_ = cursor; 1926 1927 new_block->instructions_.SetBlockOfInstructions(new_block); 1928 for (HBasicBlock* successor : GetSuccessors()) { 1929 successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block; 1930 } 1931 new_block->successors_.swap(successors_); 1932 DCHECK(successors_.empty()); 1933 1934 for (HBasicBlock* dominated : GetDominatedBlocks()) { 1935 dominated->dominator_ = new_block; 1936 } 1937 new_block->dominated_blocks_.swap(dominated_blocks_); 1938 DCHECK(dominated_blocks_.empty()); 1939 return new_block; 1940 } 1941 1942 const HTryBoundary* HBasicBlock::ComputeTryEntryOfSuccessors() const { 1943 if (EndsWithTryBoundary()) { 1944 HTryBoundary* try_boundary = GetLastInstruction()->AsTryBoundary(); 1945 if (try_boundary->IsEntry()) { 1946 DCHECK(!IsTryBlock()); 1947 return try_boundary; 1948 } else { 1949 DCHECK(IsTryBlock()); 1950 DCHECK(try_catch_information_->GetTryEntry().HasSameExceptionHandlersAs(*try_boundary)); 1951 return nullptr; 1952 } 1953 } else if (IsTryBlock()) { 1954 return &try_catch_information_->GetTryEntry(); 1955 } else { 1956 return nullptr; 1957 } 1958 } 1959 1960 bool HBasicBlock::HasThrowingInstructions() const { 1961 for (HInstructionIterator it(GetInstructions()); !it.Done(); it.Advance()) { 1962 if (it.Current()->CanThrow()) { 1963 return true; 1964 } 1965 } 1966 return false; 1967 } 1968 1969 static bool HasOnlyOneInstruction(const HBasicBlock& block) { 1970 return block.GetPhis().IsEmpty() 1971 && !block.GetInstructions().IsEmpty() 1972 && block.GetFirstInstruction() == block.GetLastInstruction(); 1973 } 1974 1975 bool HBasicBlock::IsSingleGoto() const { 1976 return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsGoto(); 1977 } 1978 1979 bool HBasicBlock::IsSingleReturn() const { 1980 return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsReturn(); 1981 } 1982 1983 bool HBasicBlock::IsSingleReturnOrReturnVoidAllowingPhis() const { 1984 return (GetFirstInstruction() == GetLastInstruction()) && 1985 (GetLastInstruction()->IsReturn() || GetLastInstruction()->IsReturnVoid()); 1986 } 1987 1988 bool HBasicBlock::IsSingleTryBoundary() const { 1989 return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsTryBoundary(); 1990 } 1991 1992 bool HBasicBlock::EndsWithControlFlowInstruction() const { 1993 return !GetInstructions().IsEmpty() && GetLastInstruction()->IsControlFlow(); 1994 } 1995 1996 bool HBasicBlock::EndsWithReturn() const { 1997 return !GetInstructions().IsEmpty() && 1998 (GetLastInstruction()->IsReturn() || GetLastInstruction()->IsReturnVoid()); 1999 } 2000 2001 bool HBasicBlock::EndsWithIf() const { 2002 return !GetInstructions().IsEmpty() && GetLastInstruction()->IsIf(); 2003 } 2004 2005 bool HBasicBlock::EndsWithTryBoundary() const { 2006 return !GetInstructions().IsEmpty() && GetLastInstruction()->IsTryBoundary(); 2007 } 2008 2009 bool HBasicBlock::HasSinglePhi() const { 2010 return !GetPhis().IsEmpty() && GetFirstPhi()->GetNext() == nullptr; 2011 } 2012 2013 ArrayRef<HBasicBlock* const> HBasicBlock::GetNormalSuccessors() const { 2014 if (EndsWithTryBoundary()) { 2015 // The normal-flow successor of HTryBoundary is always stored at index zero. 2016 DCHECK_EQ(successors_[0], GetLastInstruction()->AsTryBoundary()->GetNormalFlowSuccessor()); 2017 return ArrayRef<HBasicBlock* const>(successors_).SubArray(0u, 1u); 2018 } else { 2019 // All successors of blocks not ending with TryBoundary are normal. 2020 return ArrayRef<HBasicBlock* const>(successors_); 2021 } 2022 } 2023 2024 ArrayRef<HBasicBlock* const> HBasicBlock::GetExceptionalSuccessors() const { 2025 if (EndsWithTryBoundary()) { 2026 return GetLastInstruction()->AsTryBoundary()->GetExceptionHandlers(); 2027 } else { 2028 // Blocks not ending with TryBoundary do not have exceptional successors. 2029 return ArrayRef<HBasicBlock* const>(); 2030 } 2031 } 2032 2033 bool HTryBoundary::HasSameExceptionHandlersAs(const HTryBoundary& other) const { 2034 ArrayRef<HBasicBlock* const> handlers1 = GetExceptionHandlers(); 2035 ArrayRef<HBasicBlock* const> handlers2 = other.GetExceptionHandlers(); 2036 2037 size_t length = handlers1.size(); 2038 if (length != handlers2.size()) { 2039 return false; 2040 } 2041 2042 // Exception handlers need to be stored in the same order. 2043 for (size_t i = 0; i < length; ++i) { 2044 if (handlers1[i] != handlers2[i]) { 2045 return false; 2046 } 2047 } 2048 return true; 2049 } 2050 2051 size_t HInstructionList::CountSize() const { 2052 size_t size = 0; 2053 HInstruction* current = first_instruction_; 2054 for (; current != nullptr; current = current->GetNext()) { 2055 size++; 2056 } 2057 return size; 2058 } 2059 2060 void HInstructionList::SetBlockOfInstructions(HBasicBlock* block) const { 2061 for (HInstruction* current = first_instruction_; 2062 current != nullptr; 2063 current = current->GetNext()) { 2064 current->SetBlock(block); 2065 } 2066 } 2067 2068 void HInstructionList::AddAfter(HInstruction* cursor, const HInstructionList& instruction_list) { 2069 DCHECK(Contains(cursor)); 2070 if (!instruction_list.IsEmpty()) { 2071 if (cursor == last_instruction_) { 2072 last_instruction_ = instruction_list.last_instruction_; 2073 } else { 2074 cursor->next_->previous_ = instruction_list.last_instruction_; 2075 } 2076 instruction_list.last_instruction_->next_ = cursor->next_; 2077 cursor->next_ = instruction_list.first_instruction_; 2078 instruction_list.first_instruction_->previous_ = cursor; 2079 } 2080 } 2081 2082 void HInstructionList::AddBefore(HInstruction* cursor, const HInstructionList& instruction_list) { 2083 DCHECK(Contains(cursor)); 2084 if (!instruction_list.IsEmpty()) { 2085 if (cursor == first_instruction_) { 2086 first_instruction_ = instruction_list.first_instruction_; 2087 } else { 2088 cursor->previous_->next_ = instruction_list.first_instruction_; 2089 } 2090 instruction_list.last_instruction_->next_ = cursor; 2091 instruction_list.first_instruction_->previous_ = cursor->previous_; 2092 cursor->previous_ = instruction_list.last_instruction_; 2093 } 2094 } 2095 2096 void HInstructionList::Add(const HInstructionList& instruction_list) { 2097 if (IsEmpty()) { 2098 first_instruction_ = instruction_list.first_instruction_; 2099 last_instruction_ = instruction_list.last_instruction_; 2100 } else { 2101 AddAfter(last_instruction_, instruction_list); 2102 } 2103 } 2104 2105 // Should be called on instructions in a dead block in post order. This method 2106 // assumes `insn` has been removed from all users with the exception of catch 2107 // phis because of missing exceptional edges in the graph. It removes the 2108 // instruction from catch phi uses, together with inputs of other catch phis in 2109 // the catch block at the same index, as these must be dead too. 2110 static void RemoveUsesOfDeadInstruction(HInstruction* insn) { 2111 DCHECK(!insn->HasEnvironmentUses()); 2112 while (insn->HasNonEnvironmentUses()) { 2113 const HUseListNode<HInstruction*>& use = insn->GetUses().front(); 2114 size_t use_index = use.GetIndex(); 2115 HBasicBlock* user_block = use.GetUser()->GetBlock(); 2116 DCHECK(use.GetUser()->IsPhi() && user_block->IsCatchBlock()); 2117 for (HInstructionIterator phi_it(user_block->GetPhis()); !phi_it.Done(); phi_it.Advance()) { 2118 phi_it.Current()->AsPhi()->RemoveInputAt(use_index); 2119 } 2120 } 2121 } 2122 2123 void HBasicBlock::DisconnectAndDelete() { 2124 // Dominators must be removed after all the blocks they dominate. This way 2125 // a loop header is removed last, a requirement for correct loop information 2126 // iteration. 2127 DCHECK(dominated_blocks_.empty()); 2128 2129 // The following steps gradually remove the block from all its dependants in 2130 // post order (b/27683071). 2131 2132 // (1) Store a basic block that we'll use in step (5) to find loops to be updated. 2133 // We need to do this before step (4) which destroys the predecessor list. 2134 HBasicBlock* loop_update_start = this; 2135 if (IsLoopHeader()) { 2136 HLoopInformation* loop_info = GetLoopInformation(); 2137 // All other blocks in this loop should have been removed because the header 2138 // was their dominator. 2139 // Note that we do not remove `this` from `loop_info` as it is unreachable. 2140 DCHECK(!loop_info->IsIrreducible()); 2141 DCHECK_EQ(loop_info->GetBlocks().NumSetBits(), 1u); 2142 DCHECK_EQ(static_cast<uint32_t>(loop_info->GetBlocks().GetHighestBitSet()), GetBlockId()); 2143 loop_update_start = loop_info->GetPreHeader(); 2144 } 2145 2146 // (2) Disconnect the block from its successors and update their phis. 2147 for (HBasicBlock* successor : successors_) { 2148 // Delete this block from the list of predecessors. 2149 size_t this_index = successor->GetPredecessorIndexOf(this); 2150 successor->predecessors_.erase(successor->predecessors_.begin() + this_index); 2151 2152 // Check that `successor` has other predecessors, otherwise `this` is the 2153 // dominator of `successor` which violates the order DCHECKed at the top. 2154 DCHECK(!successor->predecessors_.empty()); 2155 2156 // Remove this block's entries in the successor's phis. Skip exceptional 2157 // successors because catch phi inputs do not correspond to predecessor 2158 // blocks but throwing instructions. The inputs of the catch phis will be 2159 // updated in step (3). 2160 if (!successor->IsCatchBlock()) { 2161 if (successor->predecessors_.size() == 1u) { 2162 // The successor has just one predecessor left. Replace phis with the only 2163 // remaining input. 2164 for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) { 2165 HPhi* phi = phi_it.Current()->AsPhi(); 2166 phi->ReplaceWith(phi->InputAt(1 - this_index)); 2167 successor->RemovePhi(phi); 2168 } 2169 } else { 2170 for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) { 2171 phi_it.Current()->AsPhi()->RemoveInputAt(this_index); 2172 } 2173 } 2174 } 2175 } 2176 successors_.clear(); 2177 2178 // (3) Remove instructions and phis. Instructions should have no remaining uses 2179 // except in catch phis. If an instruction is used by a catch phi at `index`, 2180 // remove `index`-th input of all phis in the catch block since they are 2181 // guaranteed dead. Note that we may miss dead inputs this way but the 2182 // graph will always remain consistent. 2183 for (HBackwardInstructionIterator it(GetInstructions()); !it.Done(); it.Advance()) { 2184 HInstruction* insn = it.Current(); 2185 RemoveUsesOfDeadInstruction(insn); 2186 RemoveInstruction(insn); 2187 } 2188 for (HInstructionIterator it(GetPhis()); !it.Done(); it.Advance()) { 2189 HPhi* insn = it.Current()->AsPhi(); 2190 RemoveUsesOfDeadInstruction(insn); 2191 RemovePhi(insn); 2192 } 2193 2194 // (4) Disconnect the block from its predecessors and update their 2195 // control-flow instructions. 2196 for (HBasicBlock* predecessor : predecessors_) { 2197 // We should not see any back edges as they would have been removed by step (3). 2198 DCHECK(!IsInLoop() || !GetLoopInformation()->IsBackEdge(*predecessor)); 2199 2200 HInstruction* last_instruction = predecessor->GetLastInstruction(); 2201 if (last_instruction->IsTryBoundary() && !IsCatchBlock()) { 2202 // This block is the only normal-flow successor of the TryBoundary which 2203 // makes `predecessor` dead. Since DCE removes blocks in post order, 2204 // exception handlers of this TryBoundary were already visited and any 2205 // remaining handlers therefore must be live. We remove `predecessor` from 2206 // their list of predecessors. 2207 DCHECK_EQ(last_instruction->AsTryBoundary()->GetNormalFlowSuccessor(), this); 2208 while (predecessor->GetSuccessors().size() > 1) { 2209 HBasicBlock* handler = predecessor->GetSuccessors()[1]; 2210 DCHECK(handler->IsCatchBlock()); 2211 predecessor->RemoveSuccessor(handler); 2212 handler->RemovePredecessor(predecessor); 2213 } 2214 } 2215 2216 predecessor->RemoveSuccessor(this); 2217 uint32_t num_pred_successors = predecessor->GetSuccessors().size(); 2218 if (num_pred_successors == 1u) { 2219 // If we have one successor after removing one, then we must have 2220 // had an HIf, HPackedSwitch or HTryBoundary, as they have more than one 2221 // successor. Replace those with a HGoto. 2222 DCHECK(last_instruction->IsIf() || 2223 last_instruction->IsPackedSwitch() || 2224 (last_instruction->IsTryBoundary() && IsCatchBlock())); 2225 predecessor->RemoveInstruction(last_instruction); 2226 predecessor->AddInstruction(new (graph_->GetAllocator()) HGoto(last_instruction->GetDexPc())); 2227 } else if (num_pred_successors == 0u) { 2228 // The predecessor has no remaining successors and therefore must be dead. 2229 // We deliberately leave it without a control-flow instruction so that the 2230 // GraphChecker fails unless it is not removed during the pass too. 2231 predecessor->RemoveInstruction(last_instruction); 2232 } else { 2233 // There are multiple successors left. The removed block might be a successor 2234 // of a PackedSwitch which will be completely removed (perhaps replaced with 2235 // a Goto), or we are deleting a catch block from a TryBoundary. In either 2236 // case, leave `last_instruction` as is for now. 2237 DCHECK(last_instruction->IsPackedSwitch() || 2238 (last_instruction->IsTryBoundary() && IsCatchBlock())); 2239 } 2240 } 2241 predecessors_.clear(); 2242 2243 // (5) Remove the block from all loops it is included in. Skip the inner-most 2244 // loop if this is the loop header (see definition of `loop_update_start`) 2245 // because the loop header's predecessor list has been destroyed in step (4). 2246 for (HLoopInformationOutwardIterator it(*loop_update_start); !it.Done(); it.Advance()) { 2247 HLoopInformation* loop_info = it.Current(); 2248 loop_info->Remove(this); 2249 if (loop_info->IsBackEdge(*this)) { 2250 // If this was the last back edge of the loop, we deliberately leave the 2251 // loop in an inconsistent state and will fail GraphChecker unless the 2252 // entire loop is removed during the pass. 2253 loop_info->RemoveBackEdge(this); 2254 } 2255 } 2256 2257 // (6) Disconnect from the dominator. 2258 dominator_->RemoveDominatedBlock(this); 2259 SetDominator(nullptr); 2260 2261 // (7) Delete from the graph, update reverse post order. 2262 graph_->DeleteDeadEmptyBlock(this); 2263 SetGraph(nullptr); 2264 } 2265 2266 void HBasicBlock::MergeInstructionsWith(HBasicBlock* other) { 2267 DCHECK(EndsWithControlFlowInstruction()); 2268 RemoveInstruction(GetLastInstruction()); 2269 instructions_.Add(other->GetInstructions()); 2270 other->instructions_.SetBlockOfInstructions(this); 2271 other->instructions_.Clear(); 2272 } 2273 2274 void HBasicBlock::MergeWith(HBasicBlock* other) { 2275 DCHECK_EQ(GetGraph(), other->GetGraph()); 2276 DCHECK(ContainsElement(dominated_blocks_, other)); 2277 DCHECK_EQ(GetSingleSuccessor(), other); 2278 DCHECK_EQ(other->GetSinglePredecessor(), this); 2279 DCHECK(other->GetPhis().IsEmpty()); 2280 2281 // Move instructions from `other` to `this`. 2282 MergeInstructionsWith(other); 2283 2284 // Remove `other` from the loops it is included in. 2285 for (HLoopInformationOutwardIterator it(*other); !it.Done(); it.Advance()) { 2286 HLoopInformation* loop_info = it.Current(); 2287 loop_info->Remove(other); 2288 if (loop_info->IsBackEdge(*other)) { 2289 loop_info->ReplaceBackEdge(other, this); 2290 } 2291 } 2292 2293 // Update links to the successors of `other`. 2294 successors_.clear(); 2295 for (HBasicBlock* successor : other->GetSuccessors()) { 2296 successor->predecessors_[successor->GetPredecessorIndexOf(other)] = this; 2297 } 2298 successors_.swap(other->successors_); 2299 DCHECK(other->successors_.empty()); 2300 2301 // Update the dominator tree. 2302 RemoveDominatedBlock(other); 2303 for (HBasicBlock* dominated : other->GetDominatedBlocks()) { 2304 dominated->SetDominator(this); 2305 } 2306 dominated_blocks_.insert( 2307 dominated_blocks_.end(), other->dominated_blocks_.begin(), other->dominated_blocks_.end()); 2308 other->dominated_blocks_.clear(); 2309 other->dominator_ = nullptr; 2310 2311 // Clear the list of predecessors of `other` in preparation of deleting it. 2312 other->predecessors_.clear(); 2313 2314 // Delete `other` from the graph. The function updates reverse post order. 2315 graph_->DeleteDeadEmptyBlock(other); 2316 other->SetGraph(nullptr); 2317 } 2318 2319 void HBasicBlock::MergeWithInlined(HBasicBlock* other) { 2320 DCHECK_NE(GetGraph(), other->GetGraph()); 2321 DCHECK(GetDominatedBlocks().empty()); 2322 DCHECK(GetSuccessors().empty()); 2323 DCHECK(!EndsWithControlFlowInstruction()); 2324 DCHECK(other->GetSinglePredecessor()->IsEntryBlock()); 2325 DCHECK(other->GetPhis().IsEmpty()); 2326 DCHECK(!other->IsInLoop()); 2327 2328 // Move instructions from `other` to `this`. 2329 instructions_.Add(other->GetInstructions()); 2330 other->instructions_.SetBlockOfInstructions(this); 2331 2332 // Update links to the successors of `other`. 2333 successors_.clear(); 2334 for (HBasicBlock* successor : other->GetSuccessors()) { 2335 successor->predecessors_[successor->GetPredecessorIndexOf(other)] = this; 2336 } 2337 successors_.swap(other->successors_); 2338 DCHECK(other->successors_.empty()); 2339 2340 // Update the dominator tree. 2341 for (HBasicBlock* dominated : other->GetDominatedBlocks()) { 2342 dominated->SetDominator(this); 2343 } 2344 dominated_blocks_.insert( 2345 dominated_blocks_.end(), other->dominated_blocks_.begin(), other->dominated_blocks_.end()); 2346 other->dominated_blocks_.clear(); 2347 other->dominator_ = nullptr; 2348 other->graph_ = nullptr; 2349 } 2350 2351 void HBasicBlock::ReplaceWith(HBasicBlock* other) { 2352 while (!GetPredecessors().empty()) { 2353 HBasicBlock* predecessor = GetPredecessors()[0]; 2354 predecessor->ReplaceSuccessor(this, other); 2355 } 2356 while (!GetSuccessors().empty()) { 2357 HBasicBlock* successor = GetSuccessors()[0]; 2358 successor->ReplacePredecessor(this, other); 2359 } 2360 for (HBasicBlock* dominated : GetDominatedBlocks()) { 2361 other->AddDominatedBlock(dominated); 2362 } 2363 GetDominator()->ReplaceDominatedBlock(this, other); 2364 other->SetDominator(GetDominator()); 2365 dominator_ = nullptr; 2366 graph_ = nullptr; 2367 } 2368 2369 void HGraph::DeleteDeadEmptyBlock(HBasicBlock* block) { 2370 DCHECK_EQ(block->GetGraph(), this); 2371 DCHECK(block->GetSuccessors().empty()); 2372 DCHECK(block->GetPredecessors().empty()); 2373 DCHECK(block->GetDominatedBlocks().empty()); 2374 DCHECK(block->GetDominator() == nullptr); 2375 DCHECK(block->GetInstructions().IsEmpty()); 2376 DCHECK(block->GetPhis().IsEmpty()); 2377 2378 if (block->IsExitBlock()) { 2379 SetExitBlock(nullptr); 2380 } 2381 2382 RemoveElement(reverse_post_order_, block); 2383 blocks_[block->GetBlockId()] = nullptr; 2384 block->SetGraph(nullptr); 2385 } 2386 2387 void HGraph::UpdateLoopAndTryInformationOfNewBlock(HBasicBlock* block, 2388 HBasicBlock* reference, 2389 bool replace_if_back_edge) { 2390 if (block->IsLoopHeader()) { 2391 // Clear the information of which blocks are contained in that loop. Since the 2392 // information is stored as a bit vector based on block ids, we have to update 2393 // it, as those block ids were specific to the callee graph and we are now adding 2394 // these blocks to the caller graph. 2395 block->GetLoopInformation()->ClearAllBlocks(); 2396 } 2397 2398 // If not already in a loop, update the loop information. 2399 if (!block->IsInLoop()) { 2400 block->SetLoopInformation(reference->GetLoopInformation()); 2401 } 2402 2403 // If the block is in a loop, update all its outward loops. 2404 HLoopInformation* loop_info = block->GetLoopInformation(); 2405 if (loop_info != nullptr) { 2406 for (HLoopInformationOutwardIterator loop_it(*block); 2407 !loop_it.Done(); 2408 loop_it.Advance()) { 2409 loop_it.Current()->Add(block); 2410 } 2411 if (replace_if_back_edge && loop_info->IsBackEdge(*reference)) { 2412 loop_info->ReplaceBackEdge(reference, block); 2413 } 2414 } 2415 2416 // Copy TryCatchInformation if `reference` is a try block, not if it is a catch block. 2417 TryCatchInformation* try_catch_info = reference->IsTryBlock() 2418 ? reference->GetTryCatchInformation() 2419 : nullptr; 2420 block->SetTryCatchInformation(try_catch_info); 2421 } 2422 2423 HInstruction* HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { 2424 DCHECK(HasExitBlock()) << "Unimplemented scenario"; 2425 // Update the environments in this graph to have the invoke's environment 2426 // as parent. 2427 { 2428 // Skip the entry block, we do not need to update the entry's suspend check. 2429 for (HBasicBlock* block : GetReversePostOrderSkipEntryBlock()) { 2430 for (HInstructionIterator instr_it(block->GetInstructions()); 2431 !instr_it.Done(); 2432 instr_it.Advance()) { 2433 HInstruction* current = instr_it.Current(); 2434 if (current->NeedsEnvironment()) { 2435 DCHECK(current->HasEnvironment()); 2436 current->GetEnvironment()->SetAndCopyParentChain( 2437 outer_graph->GetAllocator(), invoke->GetEnvironment()); 2438 } 2439 } 2440 } 2441 } 2442 outer_graph->UpdateMaximumNumberOfOutVRegs(GetMaximumNumberOfOutVRegs()); 2443 2444 if (HasBoundsChecks()) { 2445 outer_graph->SetHasBoundsChecks(true); 2446 } 2447 if (HasLoops()) { 2448 outer_graph->SetHasLoops(true); 2449 } 2450 if (HasIrreducibleLoops()) { 2451 outer_graph->SetHasIrreducibleLoops(true); 2452 } 2453 if (HasTryCatch()) { 2454 outer_graph->SetHasTryCatch(true); 2455 } 2456 if (HasSIMD()) { 2457 outer_graph->SetHasSIMD(true); 2458 } 2459 2460 HInstruction* return_value = nullptr; 2461 if (GetBlocks().size() == 3) { 2462 // Inliner already made sure we don't inline methods that always throw. 2463 DCHECK(!GetBlocks()[1]->GetLastInstruction()->IsThrow()); 2464 // Simple case of an entry block, a body block, and an exit block. 2465 // Put the body block's instruction into `invoke`'s block. 2466 HBasicBlock* body = GetBlocks()[1]; 2467 DCHECK(GetBlocks()[0]->IsEntryBlock()); 2468 DCHECK(GetBlocks()[2]->IsExitBlock()); 2469 DCHECK(!body->IsExitBlock()); 2470 DCHECK(!body->IsInLoop()); 2471 HInstruction* last = body->GetLastInstruction(); 2472 2473 // Note that we add instructions before the invoke only to simplify polymorphic inlining. 2474 invoke->GetBlock()->instructions_.AddBefore(invoke, body->GetInstructions()); 2475 body->GetInstructions().SetBlockOfInstructions(invoke->GetBlock()); 2476 2477 // Replace the invoke with the return value of the inlined graph. 2478 if (last->IsReturn()) { 2479 return_value = last->InputAt(0); 2480 } else { 2481 DCHECK(last->IsReturnVoid()); 2482 } 2483 2484 invoke->GetBlock()->RemoveInstruction(last); 2485 } else { 2486 // Need to inline multiple blocks. We split `invoke`'s block 2487 // into two blocks, merge the first block of the inlined graph into 2488 // the first half, and replace the exit block of the inlined graph 2489 // with the second half. 2490 ArenaAllocator* allocator = outer_graph->GetAllocator(); 2491 HBasicBlock* at = invoke->GetBlock(); 2492 // Note that we split before the invoke only to simplify polymorphic inlining. 2493 HBasicBlock* to = at->SplitBeforeForInlining(invoke); 2494 2495 HBasicBlock* first = entry_block_->GetSuccessors()[0]; 2496 DCHECK(!first->IsInLoop()); 2497 at->MergeWithInlined(first); 2498 exit_block_->ReplaceWith(to); 2499 2500 // Update the meta information surrounding blocks: 2501 // (1) the graph they are now in, 2502 // (2) the reverse post order of that graph, 2503 // (3) their potential loop information, inner and outer, 2504 // (4) try block membership. 2505 // Note that we do not need to update catch phi inputs because they 2506 // correspond to the register file of the outer method which the inlinee 2507 // cannot modify. 2508 2509 // We don't add the entry block, the exit block, and the first block, which 2510 // has been merged with `at`. 2511 static constexpr int kNumberOfSkippedBlocksInCallee = 3; 2512 2513 // We add the `to` block. 2514 static constexpr int kNumberOfNewBlocksInCaller = 1; 2515 size_t blocks_added = (reverse_post_order_.size() - kNumberOfSkippedBlocksInCallee) 2516 + kNumberOfNewBlocksInCaller; 2517 2518 // Find the location of `at` in the outer graph's reverse post order. The new 2519 // blocks will be added after it. 2520 size_t index_of_at = IndexOfElement(outer_graph->reverse_post_order_, at); 2521 MakeRoomFor(&outer_graph->reverse_post_order_, blocks_added, index_of_at); 2522 2523 // Do a reverse post order of the blocks in the callee and do (1), (2), (3) 2524 // and (4) to the blocks that apply. 2525 for (HBasicBlock* current : GetReversePostOrder()) { 2526 if (current != exit_block_ && current != entry_block_ && current != first) { 2527 DCHECK(current->GetTryCatchInformation() == nullptr); 2528 DCHECK(current->GetGraph() == this); 2529 current->SetGraph(outer_graph); 2530 outer_graph->AddBlock(current); 2531 outer_graph->reverse_post_order_[++index_of_at] = current; 2532 UpdateLoopAndTryInformationOfNewBlock(current, at, /* replace_if_back_edge= */ false); 2533 } 2534 } 2535 2536 // Do (1), (2), (3) and (4) to `to`. 2537 to->SetGraph(outer_graph); 2538 outer_graph->AddBlock(to); 2539 outer_graph->reverse_post_order_[++index_of_at] = to; 2540 // Only `to` can become a back edge, as the inlined blocks 2541 // are predecessors of `to`. 2542 UpdateLoopAndTryInformationOfNewBlock(to, at, /* replace_if_back_edge= */ true); 2543 2544 // Update all predecessors of the exit block (now the `to` block) 2545 // to not `HReturn` but `HGoto` instead. Special case throwing blocks 2546 // to now get the outer graph exit block as successor. Note that the inliner 2547 // currently doesn't support inlining methods with try/catch. 2548 HPhi* return_value_phi = nullptr; 2549 bool rerun_dominance = false; 2550 bool rerun_loop_analysis = false; 2551 for (size_t pred = 0; pred < to->GetPredecessors().size(); ++pred) { 2552 HBasicBlock* predecessor = to->GetPredecessors()[pred]; 2553 HInstruction* last = predecessor->GetLastInstruction(); 2554 if (last->IsThrow()) { 2555 DCHECK(!at->IsTryBlock()); 2556 predecessor->ReplaceSuccessor(to, outer_graph->GetExitBlock()); 2557 --pred; 2558 // We need to re-run dominance information, as the exit block now has 2559 // a new dominator. 2560 rerun_dominance = true; 2561 if (predecessor->GetLoopInformation() != nullptr) { 2562 // The exit block and blocks post dominated by the exit block do not belong 2563 // to any loop. Because we do not compute the post dominators, we need to re-run 2564 // loop analysis to get the loop information correct. 2565 rerun_loop_analysis = true; 2566 } 2567 } else { 2568 if (last->IsReturnVoid()) { 2569 DCHECK(return_value == nullptr); 2570 DCHECK(return_value_phi == nullptr); 2571 } else { 2572 DCHECK(last->IsReturn()); 2573 if (return_value_phi != nullptr) { 2574 return_value_phi->AddInput(last->InputAt(0)); 2575 } else if (return_value == nullptr) { 2576 return_value = last->InputAt(0); 2577 } else { 2578 // There will be multiple returns. 2579 return_value_phi = new (allocator) HPhi( 2580 allocator, kNoRegNumber, 0, HPhi::ToPhiType(invoke->GetType()), to->GetDexPc()); 2581 to->AddPhi(return_value_phi); 2582 return_value_phi->AddInput(return_value); 2583 return_value_phi->AddInput(last->InputAt(0)); 2584 return_value = return_value_phi; 2585 } 2586 } 2587 predecessor->AddInstruction(new (allocator) HGoto(last->GetDexPc())); 2588 predecessor->RemoveInstruction(last); 2589 } 2590 } 2591 if (rerun_loop_analysis) { 2592 DCHECK(!outer_graph->HasIrreducibleLoops()) 2593 << "Recomputing loop information in graphs with irreducible loops " 2594 << "is unsupported, as it could lead to loop header changes"; 2595 outer_graph->ClearLoopInformation(); 2596 outer_graph->ClearDominanceInformation(); 2597 outer_graph->BuildDominatorTree(); 2598 } else if (rerun_dominance) { 2599 outer_graph->ClearDominanceInformation(); 2600 outer_graph->ComputeDominanceInformation(); 2601 } 2602 } 2603 2604 // Walk over the entry block and: 2605 // - Move constants from the entry block to the outer_graph's entry block, 2606 // - Replace HParameterValue instructions with their real value. 2607 // - Remove suspend checks, that hold an environment. 2608 // We must do this after the other blocks have been inlined, otherwise ids of 2609 // constants could overlap with the inner graph. 2610 size_t parameter_index = 0; 2611 for (HInstructionIterator it(entry_block_->GetInstructions()); !it.Done(); it.Advance()) { 2612 HInstruction* current = it.Current(); 2613 HInstruction* replacement = nullptr; 2614 if (current->IsNullConstant()) { 2615 replacement = outer_graph->GetNullConstant(current->GetDexPc()); 2616 } else if (current->IsIntConstant()) { 2617 replacement = outer_graph->GetIntConstant( 2618 current->AsIntConstant()->GetValue(), current->GetDexPc()); 2619 } else if (current->IsLongConstant()) { 2620 replacement = outer_graph->GetLongConstant( 2621 current->AsLongConstant()->GetValue(), current->GetDexPc()); 2622 } else if (current->IsFloatConstant()) { 2623 replacement = outer_graph->GetFloatConstant( 2624 current->AsFloatConstant()->GetValue(), current->GetDexPc()); 2625 } else if (current->IsDoubleConstant()) { 2626 replacement = outer_graph->GetDoubleConstant( 2627 current->AsDoubleConstant()->GetValue(), current->GetDexPc()); 2628 } else if (current->IsParameterValue()) { 2629 if (kIsDebugBuild 2630 && invoke->IsInvokeStaticOrDirect() 2631 && invoke->AsInvokeStaticOrDirect()->IsStaticWithExplicitClinitCheck()) { 2632 // Ensure we do not use the last input of `invoke`, as it 2633 // contains a clinit check which is not an actual argument. 2634 size_t last_input_index = invoke->InputCount() - 1; 2635 DCHECK(parameter_index != last_input_index); 2636 } 2637 replacement = invoke->InputAt(parameter_index++); 2638 } else if (current->IsCurrentMethod()) { 2639 replacement = outer_graph->GetCurrentMethod(); 2640 } else { 2641 DCHECK(current->IsGoto() || current->IsSuspendCheck()); 2642 entry_block_->RemoveInstruction(current); 2643 } 2644 if (replacement != nullptr) { 2645 current->ReplaceWith(replacement); 2646 // If the current is the return value then we need to update the latter. 2647 if (current == return_value) { 2648 DCHECK_EQ(entry_block_, return_value->GetBlock()); 2649 return_value = replacement; 2650 } 2651 } 2652 } 2653 2654 return return_value; 2655 } 2656 2657 /* 2658 * Loop will be transformed to: 2659 * old_pre_header 2660 * | 2661 * if_block 2662 * / \ 2663 * true_block false_block 2664 * \ / 2665 * new_pre_header 2666 * | 2667 * header 2668 */ 2669 void HGraph::TransformLoopHeaderForBCE(HBasicBlock* header) { 2670 DCHECK(header->IsLoopHeader()); 2671 HBasicBlock* old_pre_header = header->GetDominator(); 2672 2673 // Need extra block to avoid critical edge. 2674 HBasicBlock* if_block = new (allocator_) HBasicBlock(this, header->GetDexPc()); 2675 HBasicBlock* true_block = new (allocator_) HBasicBlock(this, header->GetDexPc()); 2676 HBasicBlock* false_block = new (allocator_) HBasicBlock(this, header->GetDexPc()); 2677 HBasicBlock* new_pre_header = new (allocator_) HBasicBlock(this, header->GetDexPc()); 2678 AddBlock(if_block); 2679 AddBlock(true_block); 2680 AddBlock(false_block); 2681 AddBlock(new_pre_header); 2682 2683 header->ReplacePredecessor(old_pre_header, new_pre_header); 2684 old_pre_header->successors_.clear(); 2685 old_pre_header->dominated_blocks_.clear(); 2686 2687 old_pre_header->AddSuccessor(if_block); 2688 if_block->AddSuccessor(true_block); // True successor 2689 if_block->AddSuccessor(false_block); // False successor 2690 true_block->AddSuccessor(new_pre_header); 2691 false_block->AddSuccessor(new_pre_header); 2692 2693 old_pre_header->dominated_blocks_.push_back(if_block); 2694 if_block->SetDominator(old_pre_header); 2695 if_block->dominated_blocks_.push_back(true_block); 2696 true_block->SetDominator(if_block); 2697 if_block->dominated_blocks_.push_back(false_block); 2698 false_block->SetDominator(if_block); 2699 if_block->dominated_blocks_.push_back(new_pre_header); 2700 new_pre_header->SetDominator(if_block); 2701 new_pre_header->dominated_blocks_.push_back(header); 2702 header->SetDominator(new_pre_header); 2703 2704 // Fix reverse post order. 2705 size_t index_of_header = IndexOfElement(reverse_post_order_, header); 2706 MakeRoomFor(&reverse_post_order_, 4, index_of_header - 1); 2707 reverse_post_order_[index_of_header++] = if_block; 2708 reverse_post_order_[index_of_header++] = true_block; 2709 reverse_post_order_[index_of_header++] = false_block; 2710 reverse_post_order_[index_of_header++] = new_pre_header; 2711 2712 // The pre_header can never be a back edge of a loop. 2713 DCHECK((old_pre_header->GetLoopInformation() == nullptr) || 2714 !old_pre_header->GetLoopInformation()->IsBackEdge(*old_pre_header)); 2715 UpdateLoopAndTryInformationOfNewBlock( 2716 if_block, old_pre_header, /* replace_if_back_edge= */ false); 2717 UpdateLoopAndTryInformationOfNewBlock( 2718 true_block, old_pre_header, /* replace_if_back_edge= */ false); 2719 UpdateLoopAndTryInformationOfNewBlock( 2720 false_block, old_pre_header, /* replace_if_back_edge= */ false); 2721 UpdateLoopAndTryInformationOfNewBlock( 2722 new_pre_header, old_pre_header, /* replace_if_back_edge= */ false); 2723 } 2724 2725 HBasicBlock* HGraph::TransformLoopForVectorization(HBasicBlock* header, 2726 HBasicBlock* body, 2727 HBasicBlock* exit) { 2728 DCHECK(header->IsLoopHeader()); 2729 HLoopInformation* loop = header->GetLoopInformation(); 2730 2731 // Add new loop blocks. 2732 HBasicBlock* new_pre_header = new (allocator_) HBasicBlock(this, header->GetDexPc()); 2733 HBasicBlock* new_header = new (allocator_) HBasicBlock(this, header->GetDexPc()); 2734 HBasicBlock* new_body = new (allocator_) HBasicBlock(this, header->GetDexPc()); 2735 AddBlock(new_pre_header); 2736 AddBlock(new_header); 2737 AddBlock(new_body); 2738 2739 // Set up control flow. 2740 header->ReplaceSuccessor(exit, new_pre_header); 2741 new_pre_header->AddSuccessor(new_header); 2742 new_header->AddSuccessor(exit); 2743 new_header->AddSuccessor(new_body); 2744 new_body->AddSuccessor(new_header); 2745 2746 // Set up dominators. 2747 header->ReplaceDominatedBlock(exit, new_pre_header); 2748 new_pre_header->SetDominator(header); 2749 new_pre_header->dominated_blocks_.push_back(new_header); 2750 new_header->SetDominator(new_pre_header); 2751 new_header->dominated_blocks_.push_back(new_body); 2752 new_body->SetDominator(new_header); 2753 new_header->dominated_blocks_.push_back(exit); 2754 exit->SetDominator(new_header); 2755 2756 // Fix reverse post order. 2757 size_t index_of_header = IndexOfElement(reverse_post_order_, header); 2758 MakeRoomFor(&reverse_post_order_, 2, index_of_header); 2759 reverse_post_order_[++index_of_header] = new_pre_header; 2760 reverse_post_order_[++index_of_header] = new_header; 2761 size_t index_of_body = IndexOfElement(reverse_post_order_, body); 2762 MakeRoomFor(&reverse_post_order_, 1, index_of_body - 1); 2763 reverse_post_order_[index_of_body] = new_body; 2764 2765 // Add gotos and suspend check (client must add conditional in header). 2766 new_pre_header->AddInstruction(new (allocator_) HGoto()); 2767 HSuspendCheck* suspend_check = new (allocator_) HSuspendCheck(header->GetDexPc()); 2768 new_header->AddInstruction(suspend_check); 2769 new_body->AddInstruction(new (allocator_) HGoto()); 2770 suspend_check->CopyEnvironmentFromWithLoopPhiAdjustment( 2771 loop->GetSuspendCheck()->GetEnvironment(), header); 2772 2773 // Update loop information. 2774 new_header->AddBackEdge(new_body); 2775 new_header->GetLoopInformation()->SetSuspendCheck(suspend_check); 2776 new_header->GetLoopInformation()->Populate(); 2777 new_pre_header->SetLoopInformation(loop->GetPreHeader()->GetLoopInformation()); // outward 2778 HLoopInformationOutwardIterator it(*new_header); 2779 for (it.Advance(); !it.Done(); it.Advance()) { 2780 it.Current()->Add(new_pre_header); 2781 it.Current()->Add(new_header); 2782 it.Current()->Add(new_body); 2783 } 2784 return new_pre_header; 2785 } 2786 2787 static void CheckAgainstUpperBound(ReferenceTypeInfo rti, ReferenceTypeInfo upper_bound_rti) 2788 REQUIRES_SHARED(Locks::mutator_lock_) { 2789 if (rti.IsValid()) { 2790 DCHECK(upper_bound_rti.IsSupertypeOf(rti)) 2791 << " upper_bound_rti: " << upper_bound_rti 2792 << " rti: " << rti; 2793 DCHECK(!upper_bound_rti.GetTypeHandle()->CannotBeAssignedFromOtherTypes() || rti.IsExact()) 2794 << " upper_bound_rti: " << upper_bound_rti 2795 << " rti: " << rti; 2796 } 2797 } 2798 2799 void HInstruction::SetReferenceTypeInfo(ReferenceTypeInfo rti) { 2800 if (kIsDebugBuild) { 2801 DCHECK_EQ(GetType(), DataType::Type::kReference); 2802 ScopedObjectAccess soa(Thread::Current()); 2803 DCHECK(rti.IsValid()) << "Invalid RTI for " << DebugName(); 2804 if (IsBoundType()) { 2805 // Having the test here spares us from making the method virtual just for 2806 // the sake of a DCHECK. 2807 CheckAgainstUpperBound(rti, AsBoundType()->GetUpperBound()); 2808 } 2809 } 2810 reference_type_handle_ = rti.GetTypeHandle(); 2811 SetPackedFlag<kFlagReferenceTypeIsExact>(rti.IsExact()); 2812 } 2813 2814 bool HBoundType::InstructionDataEquals(const HInstruction* other) const { 2815 const HBoundType* other_bt = other->AsBoundType(); 2816 ScopedObjectAccess soa(Thread::Current()); 2817 return GetUpperBound().IsEqual(other_bt->GetUpperBound()) && 2818 GetUpperCanBeNull() == other_bt->GetUpperCanBeNull() && 2819 CanBeNull() == other_bt->CanBeNull(); 2820 } 2821 2822 void HBoundType::SetUpperBound(const ReferenceTypeInfo& upper_bound, bool can_be_null) { 2823 if (kIsDebugBuild) { 2824 ScopedObjectAccess soa(Thread::Current()); 2825 DCHECK(upper_bound.IsValid()); 2826 DCHECK(!upper_bound_.IsValid()) << "Upper bound should only be set once."; 2827 CheckAgainstUpperBound(GetReferenceTypeInfo(), upper_bound); 2828 } 2829 upper_bound_ = upper_bound; 2830 SetPackedFlag<kFlagUpperCanBeNull>(can_be_null); 2831 } 2832 2833 ReferenceTypeInfo ReferenceTypeInfo::Create(TypeHandle type_handle, bool is_exact) { 2834 if (kIsDebugBuild) { 2835 ScopedObjectAccess soa(Thread::Current()); 2836 DCHECK(IsValidHandle(type_handle)); 2837 if (!is_exact) { 2838 DCHECK(!type_handle->CannotBeAssignedFromOtherTypes()) 2839 << "Callers of ReferenceTypeInfo::Create should ensure is_exact is properly computed"; 2840 } 2841 } 2842 return ReferenceTypeInfo(type_handle, is_exact); 2843 } 2844 2845 std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs) { 2846 ScopedObjectAccess soa(Thread::Current()); 2847 os << "[" 2848 << " is_valid=" << rhs.IsValid() 2849 << " type=" << (!rhs.IsValid() ? "?" : mirror::Class::PrettyClass(rhs.GetTypeHandle().Get())) 2850 << " is_exact=" << rhs.IsExact() 2851 << " ]"; 2852 return os; 2853 } 2854 2855 bool HInstruction::HasAnyEnvironmentUseBefore(HInstruction* other) { 2856 // For now, assume that instructions in different blocks may use the 2857 // environment. 2858 // TODO: Use the control flow to decide if this is true. 2859 if (GetBlock() != other->GetBlock()) { 2860 return true; 2861 } 2862 2863 // We know that we are in the same block. Walk from 'this' to 'other', 2864 // checking to see if there is any instruction with an environment. 2865 HInstruction* current = this; 2866 for (; current != other && current != nullptr; current = current->GetNext()) { 2867 // This is a conservative check, as the instruction result may not be in 2868 // the referenced environment. 2869 if (current->HasEnvironment()) { 2870 return true; 2871 } 2872 } 2873 2874 // We should have been called with 'this' before 'other' in the block. 2875 // Just confirm this. 2876 DCHECK(current != nullptr); 2877 return false; 2878 } 2879 2880 void HInvoke::SetIntrinsic(Intrinsics intrinsic, 2881 IntrinsicNeedsEnvironmentOrCache needs_env_or_cache, 2882 IntrinsicSideEffects side_effects, 2883 IntrinsicExceptions exceptions) { 2884 intrinsic_ = intrinsic; 2885 IntrinsicOptimizations opt(this); 2886 2887 // Adjust method's side effects from intrinsic table. 2888 switch (side_effects) { 2889 case kNoSideEffects: SetSideEffects(SideEffects::None()); break; 2890 case kReadSideEffects: SetSideEffects(SideEffects::AllReads()); break; 2891 case kWriteSideEffects: SetSideEffects(SideEffects::AllWrites()); break; 2892 case kAllSideEffects: SetSideEffects(SideEffects::AllExceptGCDependency()); break; 2893 } 2894 2895 if (needs_env_or_cache == kNoEnvironmentOrCache) { 2896 opt.SetDoesNotNeedDexCache(); 2897 opt.SetDoesNotNeedEnvironment(); 2898 } else { 2899 // If we need an environment, that means there will be a call, which can trigger GC. 2900 SetSideEffects(GetSideEffects().Union(SideEffects::CanTriggerGC())); 2901 } 2902 // Adjust method's exception status from intrinsic table. 2903 SetCanThrow(exceptions == kCanThrow); 2904 } 2905 2906 bool HNewInstance::IsStringAlloc() const { 2907 return GetEntrypoint() == kQuickAllocStringObject; 2908 } 2909 2910 bool HInvoke::NeedsEnvironment() const { 2911 if (!IsIntrinsic()) { 2912 return true; 2913 } 2914 IntrinsicOptimizations opt(*this); 2915 return !opt.GetDoesNotNeedEnvironment(); 2916 } 2917 2918 const DexFile& HInvokeStaticOrDirect::GetDexFileForPcRelativeDexCache() const { 2919 ArtMethod* caller = GetEnvironment()->GetMethod(); 2920 ScopedObjectAccess soa(Thread::Current()); 2921 // `caller` is null for a top-level graph representing a method whose declaring 2922 // class was not resolved. 2923 return caller == nullptr ? GetBlock()->GetGraph()->GetDexFile() : *caller->GetDexFile(); 2924 } 2925 2926 bool HInvokeStaticOrDirect::NeedsDexCacheOfDeclaringClass() const { 2927 if (GetMethodLoadKind() != MethodLoadKind::kRuntimeCall) { 2928 return false; 2929 } 2930 if (!IsIntrinsic()) { 2931 return true; 2932 } 2933 IntrinsicOptimizations opt(*this); 2934 return !opt.GetDoesNotNeedDexCache(); 2935 } 2936 2937 std::ostream& operator<<(std::ostream& os, HInvokeStaticOrDirect::MethodLoadKind rhs) { 2938 switch (rhs) { 2939 case HInvokeStaticOrDirect::MethodLoadKind::kStringInit: 2940 return os << "StringInit"; 2941 case HInvokeStaticOrDirect::MethodLoadKind::kRecursive: 2942 return os << "Recursive"; 2943 case HInvokeStaticOrDirect::MethodLoadKind::kBootImageLinkTimePcRelative: 2944 return os << "BootImageLinkTimePcRelative"; 2945 case HInvokeStaticOrDirect::MethodLoadKind::kBootImageRelRo: 2946 return os << "BootImageRelRo"; 2947 case HInvokeStaticOrDirect::MethodLoadKind::kBssEntry: 2948 return os << "BssEntry"; 2949 case HInvokeStaticOrDirect::MethodLoadKind::kJitDirectAddress: 2950 return os << "JitDirectAddress"; 2951 case HInvokeStaticOrDirect::MethodLoadKind::kRuntimeCall: 2952 return os << "RuntimeCall"; 2953 default: 2954 LOG(FATAL) << "Unknown MethodLoadKind: " << static_cast<int>(rhs); 2955 UNREACHABLE(); 2956 } 2957 } 2958 2959 std::ostream& operator<<(std::ostream& os, HInvokeStaticOrDirect::ClinitCheckRequirement rhs) { 2960 switch (rhs) { 2961 case HInvokeStaticOrDirect::ClinitCheckRequirement::kExplicit: 2962 return os << "explicit"; 2963 case HInvokeStaticOrDirect::ClinitCheckRequirement::kImplicit: 2964 return os << "implicit"; 2965 case HInvokeStaticOrDirect::ClinitCheckRequirement::kNone: 2966 return os << "none"; 2967 default: 2968 LOG(FATAL) << "Unknown ClinitCheckRequirement: " << static_cast<int>(rhs); 2969 UNREACHABLE(); 2970 } 2971 } 2972 2973 bool HLoadClass::InstructionDataEquals(const HInstruction* other) const { 2974 const HLoadClass* other_load_class = other->AsLoadClass(); 2975 // TODO: To allow GVN for HLoadClass from different dex files, we should compare the type 2976 // names rather than type indexes. However, we shall also have to re-think the hash code. 2977 if (type_index_ != other_load_class->type_index_ || 2978 GetPackedFields() != other_load_class->GetPackedFields()) { 2979 return false; 2980 } 2981 switch (GetLoadKind()) { 2982 case LoadKind::kBootImageRelRo: 2983 case LoadKind::kJitBootImageAddress: 2984 case LoadKind::kJitTableAddress: { 2985 ScopedObjectAccess soa(Thread::Current()); 2986 return GetClass().Get() == other_load_class->GetClass().Get(); 2987 } 2988 default: 2989 DCHECK(HasTypeReference(GetLoadKind())); 2990 return IsSameDexFile(GetDexFile(), other_load_class->GetDexFile()); 2991 } 2992 } 2993 2994 std::ostream& operator<<(std::ostream& os, HLoadClass::LoadKind rhs) { 2995 switch (rhs) { 2996 case HLoadClass::LoadKind::kReferrersClass: 2997 return os << "ReferrersClass"; 2998 case HLoadClass::LoadKind::kBootImageLinkTimePcRelative: 2999 return os << "BootImageLinkTimePcRelative"; 3000 case HLoadClass::LoadKind::kBootImageRelRo: 3001 return os << "BootImageRelRo"; 3002 case HLoadClass::LoadKind::kBssEntry: 3003 return os << "BssEntry"; 3004 case HLoadClass::LoadKind::kJitBootImageAddress: 3005 return os << "JitBootImageAddress"; 3006 case HLoadClass::LoadKind::kJitTableAddress: 3007 return os << "JitTableAddress"; 3008 case HLoadClass::LoadKind::kRuntimeCall: 3009 return os << "RuntimeCall"; 3010 default: 3011 LOG(FATAL) << "Unknown HLoadClass::LoadKind: " << static_cast<int>(rhs); 3012 UNREACHABLE(); 3013 } 3014 } 3015 3016 bool HLoadString::InstructionDataEquals(const HInstruction* other) const { 3017 const HLoadString* other_load_string = other->AsLoadString(); 3018 // TODO: To allow GVN for HLoadString from different dex files, we should compare the strings 3019 // rather than their indexes. However, we shall also have to re-think the hash code. 3020 if (string_index_ != other_load_string->string_index_ || 3021 GetPackedFields() != other_load_string->GetPackedFields()) { 3022 return false; 3023 } 3024 switch (GetLoadKind()) { 3025 case LoadKind::kBootImageRelRo: 3026 case LoadKind::kJitBootImageAddress: 3027 case LoadKind::kJitTableAddress: { 3028 ScopedObjectAccess soa(Thread::Current()); 3029 return GetString().Get() == other_load_string->GetString().Get(); 3030 } 3031 default: 3032 return IsSameDexFile(GetDexFile(), other_load_string->GetDexFile()); 3033 } 3034 } 3035 3036 std::ostream& operator<<(std::ostream& os, HLoadString::LoadKind rhs) { 3037 switch (rhs) { 3038 case HLoadString::LoadKind::kBootImageLinkTimePcRelative: 3039 return os << "BootImageLinkTimePcRelative"; 3040 case HLoadString::LoadKind::kBootImageRelRo: 3041 return os << "BootImageRelRo"; 3042 case HLoadString::LoadKind::kBssEntry: 3043 return os << "BssEntry"; 3044 case HLoadString::LoadKind::kJitBootImageAddress: 3045 return os << "JitBootImageAddress"; 3046 case HLoadString::LoadKind::kJitTableAddress: 3047 return os << "JitTableAddress"; 3048 case HLoadString::LoadKind::kRuntimeCall: 3049 return os << "RuntimeCall"; 3050 default: 3051 LOG(FATAL) << "Unknown HLoadString::LoadKind: " << static_cast<int>(rhs); 3052 UNREACHABLE(); 3053 } 3054 } 3055 3056 void HInstruction::RemoveEnvironmentUsers() { 3057 for (const HUseListNode<HEnvironment*>& use : GetEnvUses()) { 3058 HEnvironment* user = use.GetUser(); 3059 user->SetRawEnvAt(use.GetIndex(), nullptr); 3060 } 3061 env_uses_.clear(); 3062 } 3063 3064 HInstruction* ReplaceInstrOrPhiByClone(HInstruction* instr) { 3065 HInstruction* clone = instr->Clone(instr->GetBlock()->GetGraph()->GetAllocator()); 3066 HBasicBlock* block = instr->GetBlock(); 3067 3068 if (instr->IsPhi()) { 3069 HPhi* phi = instr->AsPhi(); 3070 DCHECK(!phi->HasEnvironment()); 3071 HPhi* phi_clone = clone->AsPhi(); 3072 block->ReplaceAndRemovePhiWith(phi, phi_clone); 3073 } else { 3074 block->ReplaceAndRemoveInstructionWith(instr, clone); 3075 if (instr->HasEnvironment()) { 3076 clone->CopyEnvironmentFrom(instr->GetEnvironment()); 3077 HLoopInformation* loop_info = block->GetLoopInformation(); 3078 if (instr->IsSuspendCheck() && loop_info != nullptr) { 3079 loop_info->SetSuspendCheck(clone->AsSuspendCheck()); 3080 } 3081 } 3082 } 3083 return clone; 3084 } 3085 3086 // Returns an instruction with the opposite Boolean value from 'cond'. 3087 HInstruction* HGraph::InsertOppositeCondition(HInstruction* cond, HInstruction* cursor) { 3088 ArenaAllocator* allocator = GetAllocator(); 3089 3090 if (cond->IsCondition() && 3091 !DataType::IsFloatingPointType(cond->InputAt(0)->GetType())) { 3092 // Can't reverse floating point conditions. We have to use HBooleanNot in that case. 3093 HInstruction* lhs = cond->InputAt(0); 3094 HInstruction* rhs = cond->InputAt(1); 3095 HInstruction* replacement = nullptr; 3096 switch (cond->AsCondition()->GetOppositeCondition()) { // get *opposite* 3097 case kCondEQ: replacement = new (allocator) HEqual(lhs, rhs); break; 3098 case kCondNE: replacement = new (allocator) HNotEqual(lhs, rhs); break; 3099 case kCondLT: replacement = new (allocator) HLessThan(lhs, rhs); break; 3100 case kCondLE: replacement = new (allocator) HLessThanOrEqual(lhs, rhs); break; 3101 case kCondGT: replacement = new (allocator) HGreaterThan(lhs, rhs); break; 3102 case kCondGE: replacement = new (allocator) HGreaterThanOrEqual(lhs, rhs); break; 3103 case kCondB: replacement = new (allocator) HBelow(lhs, rhs); break; 3104 case kCondBE: replacement = new (allocator) HBelowOrEqual(lhs, rhs); break; 3105 case kCondA: replacement = new (allocator) HAbove(lhs, rhs); break; 3106 case kCondAE: replacement = new (allocator) HAboveOrEqual(lhs, rhs); break; 3107 default: 3108 LOG(FATAL) << "Unexpected condition"; 3109 UNREACHABLE(); 3110 } 3111 cursor->GetBlock()->InsertInstructionBefore(replacement, cursor); 3112 return replacement; 3113 } else if (cond->IsIntConstant()) { 3114 HIntConstant* int_const = cond->AsIntConstant(); 3115 if (int_const->IsFalse()) { 3116 return GetIntConstant(1); 3117 } else { 3118 DCHECK(int_const->IsTrue()) << int_const->GetValue(); 3119 return GetIntConstant(0); 3120 } 3121 } else { 3122 HInstruction* replacement = new (allocator) HBooleanNot(cond); 3123 cursor->GetBlock()->InsertInstructionBefore(replacement, cursor); 3124 return replacement; 3125 } 3126 } 3127 3128 std::ostream& operator<<(std::ostream& os, const MoveOperands& rhs) { 3129 os << "[" 3130 << " source=" << rhs.GetSource() 3131 << " destination=" << rhs.GetDestination() 3132 << " type=" << rhs.GetType() 3133 << " instruction="; 3134 if (rhs.GetInstruction() != nullptr) { 3135 os << rhs.GetInstruction()->DebugName() << ' ' << rhs.GetInstruction()->GetId(); 3136 } else { 3137 os << "null"; 3138 } 3139 os << " ]"; 3140 return os; 3141 } 3142 3143 std::ostream& operator<<(std::ostream& os, TypeCheckKind rhs) { 3144 switch (rhs) { 3145 case TypeCheckKind::kUnresolvedCheck: 3146 return os << "unresolved_check"; 3147 case TypeCheckKind::kExactCheck: 3148 return os << "exact_check"; 3149 case TypeCheckKind::kClassHierarchyCheck: 3150 return os << "class_hierarchy_check"; 3151 case TypeCheckKind::kAbstractClassCheck: 3152 return os << "abstract_class_check"; 3153 case TypeCheckKind::kInterfaceCheck: 3154 return os << "interface_check"; 3155 case TypeCheckKind::kArrayObjectCheck: 3156 return os << "array_object_check"; 3157 case TypeCheckKind::kArrayCheck: 3158 return os << "array_check"; 3159 case TypeCheckKind::kBitstringCheck: 3160 return os << "bitstring_check"; 3161 default: 3162 LOG(FATAL) << "Unknown TypeCheckKind: " << static_cast<int>(rhs); 3163 UNREACHABLE(); 3164 } 3165 } 3166 3167 std::ostream& operator<<(std::ostream& os, const MemBarrierKind& kind) { 3168 switch (kind) { 3169 case MemBarrierKind::kAnyStore: 3170 return os << "AnyStore"; 3171 case MemBarrierKind::kLoadAny: 3172 return os << "LoadAny"; 3173 case MemBarrierKind::kStoreStore: 3174 return os << "StoreStore"; 3175 case MemBarrierKind::kAnyAny: 3176 return os << "AnyAny"; 3177 case MemBarrierKind::kNTStoreStore: 3178 return os << "NTStoreStore"; 3179 3180 default: 3181 LOG(FATAL) << "Unknown MemBarrierKind: " << static_cast<int>(kind); 3182 UNREACHABLE(); 3183 } 3184 } 3185 3186 // Check that intrinsic enum values fit within space set aside in ArtMethod modifier flags. 3187 #define CHECK_INTRINSICS_ENUM_VALUES(Name, InvokeType, _, SideEffects, Exceptions, ...) \ 3188 static_assert( \ 3189 static_cast<uint32_t>(Intrinsics::k ## Name) <= (kAccIntrinsicBits >> CTZ(kAccIntrinsicBits)), \ 3190 "Instrinsics enumeration space overflow."); 3191 #include "intrinsics_list.h" 3192 INTRINSICS_LIST(CHECK_INTRINSICS_ENUM_VALUES) 3193 #undef INTRINSICS_LIST 3194 #undef CHECK_INTRINSICS_ENUM_VALUES 3195 3196 // Function that returns whether an intrinsic needs an environment or not. 3197 static inline IntrinsicNeedsEnvironmentOrCache NeedsEnvironmentOrCacheIntrinsic(Intrinsics i) { 3198 switch (i) { 3199 case Intrinsics::kNone: 3200 return kNeedsEnvironmentOrCache; // Non-sensical for intrinsic. 3201 #define OPTIMIZING_INTRINSICS(Name, InvokeType, NeedsEnvOrCache, SideEffects, Exceptions, ...) \ 3202 case Intrinsics::k ## Name: \ 3203 return NeedsEnvOrCache; 3204 #include "intrinsics_list.h" 3205 INTRINSICS_LIST(OPTIMIZING_INTRINSICS) 3206 #undef INTRINSICS_LIST 3207 #undef OPTIMIZING_INTRINSICS 3208 } 3209 return kNeedsEnvironmentOrCache; 3210 } 3211 3212 // Function that returns whether an intrinsic has side effects. 3213 static inline IntrinsicSideEffects GetSideEffectsIntrinsic(Intrinsics i) { 3214 switch (i) { 3215 case Intrinsics::kNone: 3216 return kAllSideEffects; 3217 #define OPTIMIZING_INTRINSICS(Name, InvokeType, NeedsEnvOrCache, SideEffects, Exceptions, ...) \ 3218 case Intrinsics::k ## Name: \ 3219 return SideEffects; 3220 #include "intrinsics_list.h" 3221 INTRINSICS_LIST(OPTIMIZING_INTRINSICS) 3222 #undef INTRINSICS_LIST 3223 #undef OPTIMIZING_INTRINSICS 3224 } 3225 return kAllSideEffects; 3226 } 3227 3228 // Function that returns whether an intrinsic can throw exceptions. 3229 static inline IntrinsicExceptions GetExceptionsIntrinsic(Intrinsics i) { 3230 switch (i) { 3231 case Intrinsics::kNone: 3232 return kCanThrow; 3233 #define OPTIMIZING_INTRINSICS(Name, InvokeType, NeedsEnvOrCache, SideEffects, Exceptions, ...) \ 3234 case Intrinsics::k ## Name: \ 3235 return Exceptions; 3236 #include "intrinsics_list.h" 3237 INTRINSICS_LIST(OPTIMIZING_INTRINSICS) 3238 #undef INTRINSICS_LIST 3239 #undef OPTIMIZING_INTRINSICS 3240 } 3241 return kCanThrow; 3242 } 3243 3244 void HInvoke::SetResolvedMethod(ArtMethod* method) { 3245 // TODO: b/65872996 The intent is that polymorphic signature methods should 3246 // be compiler intrinsics. At present, they are only interpreter intrinsics. 3247 if (method != nullptr && 3248 method->IsIntrinsic() && 3249 !method->IsPolymorphicSignature()) { 3250 Intrinsics intrinsic = static_cast<Intrinsics>(method->GetIntrinsic()); 3251 SetIntrinsic(intrinsic, 3252 NeedsEnvironmentOrCacheIntrinsic(intrinsic), 3253 GetSideEffectsIntrinsic(intrinsic), 3254 GetExceptionsIntrinsic(intrinsic)); 3255 } 3256 resolved_method_ = method; 3257 } 3258 3259 } // namespace art 3260