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