nodes.h revision d23eeef3492b53102eb8093524cf37e2b4c296db
1/* 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#ifndef ART_COMPILER_OPTIMIZING_NODES_H_ 18#define ART_COMPILER_OPTIMIZING_NODES_H_ 19 20#include "base/arena_containers.h" 21#include "base/arena_object.h" 22#include "dex/compiler_enums.h" 23#include "entrypoints/quick/quick_entrypoints_enum.h" 24#include "handle.h" 25#include "handle_scope.h" 26#include "invoke_type.h" 27#include "locations.h" 28#include "mirror/class.h" 29#include "offsets.h" 30#include "primitive.h" 31#include "utils/arena_bit_vector.h" 32#include "utils/growable_array.h" 33 34namespace art { 35 36class GraphChecker; 37class HBasicBlock; 38class HCurrentMethod; 39class HDoubleConstant; 40class HEnvironment; 41class HFloatConstant; 42class HGraphVisitor; 43class HInstruction; 44class HIntConstant; 45class HInvoke; 46class HLongConstant; 47class HNullConstant; 48class HPhi; 49class HSuspendCheck; 50class LiveInterval; 51class LocationSummary; 52class SlowPathCode; 53class SsaBuilder; 54 55static const int kDefaultNumberOfBlocks = 8; 56static const int kDefaultNumberOfSuccessors = 2; 57static const int kDefaultNumberOfPredecessors = 2; 58static const int kDefaultNumberOfDominatedBlocks = 1; 59static const int kDefaultNumberOfBackEdges = 1; 60 61static constexpr uint32_t kMaxIntShiftValue = 0x1f; 62static constexpr uint64_t kMaxLongShiftValue = 0x3f; 63 64static constexpr InvokeType kInvalidInvokeType = static_cast<InvokeType>(-1); 65 66enum IfCondition { 67 kCondEQ, 68 kCondNE, 69 kCondLT, 70 kCondLE, 71 kCondGT, 72 kCondGE, 73}; 74 75class HInstructionList { 76 public: 77 HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {} 78 79 void AddInstruction(HInstruction* instruction); 80 void RemoveInstruction(HInstruction* instruction); 81 82 // Insert `instruction` before/after an existing instruction `cursor`. 83 void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); 84 void InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor); 85 86 // Return true if this list contains `instruction`. 87 bool Contains(HInstruction* instruction) const; 88 89 // Return true if `instruction1` is found before `instruction2` in 90 // this instruction list and false otherwise. Abort if none 91 // of these instructions is found. 92 bool FoundBefore(const HInstruction* instruction1, 93 const HInstruction* instruction2) const; 94 95 bool IsEmpty() const { return first_instruction_ == nullptr; } 96 void Clear() { first_instruction_ = last_instruction_ = nullptr; } 97 98 // Update the block of all instructions to be `block`. 99 void SetBlockOfInstructions(HBasicBlock* block) const; 100 101 void AddAfter(HInstruction* cursor, const HInstructionList& instruction_list); 102 void Add(const HInstructionList& instruction_list); 103 104 // Return the number of instructions in the list. This is an expensive operation. 105 size_t CountSize() const; 106 107 private: 108 HInstruction* first_instruction_; 109 HInstruction* last_instruction_; 110 111 friend class HBasicBlock; 112 friend class HGraph; 113 friend class HInstruction; 114 friend class HInstructionIterator; 115 friend class HBackwardInstructionIterator; 116 117 DISALLOW_COPY_AND_ASSIGN(HInstructionList); 118}; 119 120// Control-flow graph of a method. Contains a list of basic blocks. 121class HGraph : public ArenaObject<kArenaAllocMisc> { 122 public: 123 HGraph(ArenaAllocator* arena, 124 const DexFile& dex_file, 125 uint32_t method_idx, 126 bool should_generate_constructor_barrier, 127 InvokeType invoke_type = kInvalidInvokeType, 128 bool debuggable = false, 129 int start_instruction_id = 0) 130 : arena_(arena), 131 blocks_(arena, kDefaultNumberOfBlocks), 132 reverse_post_order_(arena, kDefaultNumberOfBlocks), 133 linear_order_(arena, kDefaultNumberOfBlocks), 134 entry_block_(nullptr), 135 exit_block_(nullptr), 136 maximum_number_of_out_vregs_(0), 137 number_of_vregs_(0), 138 number_of_in_vregs_(0), 139 temporaries_vreg_slots_(0), 140 has_bounds_checks_(false), 141 debuggable_(debuggable), 142 current_instruction_id_(start_instruction_id), 143 dex_file_(dex_file), 144 method_idx_(method_idx), 145 invoke_type_(invoke_type), 146 in_ssa_form_(false), 147 should_generate_constructor_barrier_(should_generate_constructor_barrier), 148 cached_null_constant_(nullptr), 149 cached_int_constants_(std::less<int32_t>(), arena->Adapter()), 150 cached_float_constants_(std::less<int32_t>(), arena->Adapter()), 151 cached_long_constants_(std::less<int64_t>(), arena->Adapter()), 152 cached_double_constants_(std::less<int64_t>(), arena->Adapter()), 153 cached_current_method_(nullptr) {} 154 155 ArenaAllocator* GetArena() const { return arena_; } 156 const GrowableArray<HBasicBlock*>& GetBlocks() const { return blocks_; } 157 HBasicBlock* GetBlock(size_t id) const { return blocks_.Get(id); } 158 159 HBasicBlock* GetEntryBlock() const { return entry_block_; } 160 HBasicBlock* GetExitBlock() const { return exit_block_; } 161 bool HasExitBlock() const { return exit_block_ != nullptr; } 162 163 void SetEntryBlock(HBasicBlock* block) { entry_block_ = block; } 164 void SetExitBlock(HBasicBlock* block) { exit_block_ = block; } 165 166 void AddBlock(HBasicBlock* block); 167 168 // Try building the SSA form of this graph, with dominance computation and loop 169 // recognition. Returns whether it was successful in doing all these steps. 170 bool TryBuildingSsa() { 171 BuildDominatorTree(); 172 // The SSA builder requires loops to all be natural. Specifically, the dead phi 173 // elimination phase checks the consistency of the graph when doing a post-order 174 // visit for eliminating dead phis: a dead phi can only have loop header phi 175 // users remaining when being visited. 176 if (!AnalyzeNaturalLoops()) return false; 177 TransformToSsa(); 178 in_ssa_form_ = true; 179 return true; 180 } 181 182 void BuildDominatorTree(); 183 void TransformToSsa(); 184 void SimplifyCFG(); 185 186 // Analyze all natural loops in this graph. Returns false if one 187 // loop is not natural, that is the header does not dominate the 188 // back edge. 189 bool AnalyzeNaturalLoops() const; 190 191 // Inline this graph in `outer_graph`, replacing the given `invoke` instruction. 192 void InlineInto(HGraph* outer_graph, HInvoke* invoke); 193 194 // Removes `block` from the graph. 195 void DeleteDeadBlock(HBasicBlock* block); 196 197 void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor); 198 void SimplifyLoop(HBasicBlock* header); 199 200 int32_t GetNextInstructionId() { 201 DCHECK_NE(current_instruction_id_, INT32_MAX); 202 return current_instruction_id_++; 203 } 204 205 int32_t GetCurrentInstructionId() const { 206 return current_instruction_id_; 207 } 208 209 void SetCurrentInstructionId(int32_t id) { 210 current_instruction_id_ = id; 211 } 212 213 uint16_t GetMaximumNumberOfOutVRegs() const { 214 return maximum_number_of_out_vregs_; 215 } 216 217 void SetMaximumNumberOfOutVRegs(uint16_t new_value) { 218 maximum_number_of_out_vregs_ = new_value; 219 } 220 221 void UpdateMaximumNumberOfOutVRegs(uint16_t other_value) { 222 maximum_number_of_out_vregs_ = std::max(maximum_number_of_out_vregs_, other_value); 223 } 224 225 void UpdateTemporariesVRegSlots(size_t slots) { 226 temporaries_vreg_slots_ = std::max(slots, temporaries_vreg_slots_); 227 } 228 229 size_t GetTemporariesVRegSlots() const { 230 DCHECK(!in_ssa_form_); 231 return temporaries_vreg_slots_; 232 } 233 234 void SetNumberOfVRegs(uint16_t number_of_vregs) { 235 number_of_vregs_ = number_of_vregs; 236 } 237 238 uint16_t GetNumberOfVRegs() const { 239 DCHECK(!in_ssa_form_); 240 return number_of_vregs_; 241 } 242 243 void SetNumberOfInVRegs(uint16_t value) { 244 number_of_in_vregs_ = value; 245 } 246 247 uint16_t GetNumberOfLocalVRegs() const { 248 DCHECK(!in_ssa_form_); 249 return number_of_vregs_ - number_of_in_vregs_; 250 } 251 252 const GrowableArray<HBasicBlock*>& GetReversePostOrder() const { 253 return reverse_post_order_; 254 } 255 256 const GrowableArray<HBasicBlock*>& GetLinearOrder() const { 257 return linear_order_; 258 } 259 260 bool HasBoundsChecks() const { 261 return has_bounds_checks_; 262 } 263 264 void SetHasBoundsChecks(bool value) { 265 has_bounds_checks_ = value; 266 } 267 268 bool ShouldGenerateConstructorBarrier() const { 269 return should_generate_constructor_barrier_; 270 } 271 272 bool IsDebuggable() const { return debuggable_; } 273 274 // Returns a constant of the given type and value. If it does not exist 275 // already, it is created and inserted into the graph. This method is only for 276 // integral types. 277 HConstant* GetConstant(Primitive::Type type, int64_t value); 278 HNullConstant* GetNullConstant(); 279 HIntConstant* GetIntConstant(int32_t value) { 280 return CreateConstant(value, &cached_int_constants_); 281 } 282 HLongConstant* GetLongConstant(int64_t value) { 283 return CreateConstant(value, &cached_long_constants_); 284 } 285 HFloatConstant* GetFloatConstant(float value) { 286 return CreateConstant(bit_cast<int32_t, float>(value), &cached_float_constants_); 287 } 288 HDoubleConstant* GetDoubleConstant(double value) { 289 return CreateConstant(bit_cast<int64_t, double>(value), &cached_double_constants_); 290 } 291 292 HCurrentMethod* GetCurrentMethod(); 293 294 HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const; 295 296 const DexFile& GetDexFile() const { 297 return dex_file_; 298 } 299 300 uint32_t GetMethodIdx() const { 301 return method_idx_; 302 } 303 304 InvokeType GetInvokeType() const { 305 return invoke_type_; 306 } 307 308 private: 309 void VisitBlockForDominatorTree(HBasicBlock* block, 310 HBasicBlock* predecessor, 311 GrowableArray<size_t>* visits); 312 void FindBackEdges(ArenaBitVector* visited); 313 void VisitBlockForBackEdges(HBasicBlock* block, 314 ArenaBitVector* visited, 315 ArenaBitVector* visiting); 316 void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const; 317 void RemoveDeadBlocks(const ArenaBitVector& visited); 318 319 template <class InstructionType, typename ValueType> 320 InstructionType* CreateConstant(ValueType value, 321 ArenaSafeMap<ValueType, InstructionType*>* cache) { 322 // Try to find an existing constant of the given value. 323 InstructionType* constant = nullptr; 324 auto cached_constant = cache->find(value); 325 if (cached_constant != cache->end()) { 326 constant = cached_constant->second; 327 } 328 329 // If not found or previously deleted, create and cache a new instruction. 330 if (constant == nullptr || constant->GetBlock() == nullptr) { 331 constant = new (arena_) InstructionType(value); 332 cache->Overwrite(value, constant); 333 InsertConstant(constant); 334 } 335 return constant; 336 } 337 338 void InsertConstant(HConstant* instruction); 339 340 // Cache a float constant into the graph. This method should only be 341 // called by the SsaBuilder when creating "equivalent" instructions. 342 void CacheFloatConstant(HFloatConstant* constant); 343 344 // See CacheFloatConstant comment. 345 void CacheDoubleConstant(HDoubleConstant* constant); 346 347 ArenaAllocator* const arena_; 348 349 // List of blocks in insertion order. 350 GrowableArray<HBasicBlock*> blocks_; 351 352 // List of blocks to perform a reverse post order tree traversal. 353 GrowableArray<HBasicBlock*> reverse_post_order_; 354 355 // List of blocks to perform a linear order tree traversal. 356 GrowableArray<HBasicBlock*> linear_order_; 357 358 HBasicBlock* entry_block_; 359 HBasicBlock* exit_block_; 360 361 // The maximum number of virtual registers arguments passed to a HInvoke in this graph. 362 uint16_t maximum_number_of_out_vregs_; 363 364 // The number of virtual registers in this method. Contains the parameters. 365 uint16_t number_of_vregs_; 366 367 // The number of virtual registers used by parameters of this method. 368 uint16_t number_of_in_vregs_; 369 370 // Number of vreg size slots that the temporaries use (used in baseline compiler). 371 size_t temporaries_vreg_slots_; 372 373 // Has bounds checks. We can totally skip BCE if it's false. 374 bool has_bounds_checks_; 375 376 // Indicates whether the graph should be compiled in a way that 377 // ensures full debuggability. If false, we can apply more 378 // aggressive optimizations that may limit the level of debugging. 379 const bool debuggable_; 380 381 // The current id to assign to a newly added instruction. See HInstruction.id_. 382 int32_t current_instruction_id_; 383 384 // The dex file from which the method is from. 385 const DexFile& dex_file_; 386 387 // The method index in the dex file. 388 const uint32_t method_idx_; 389 390 // If inlined, this encodes how the callee is being invoked. 391 const InvokeType invoke_type_; 392 393 // Whether the graph has been transformed to SSA form. Only used 394 // in debug mode to ensure we are not using properties only valid 395 // for non-SSA form (like the number of temporaries). 396 bool in_ssa_form_; 397 398 const bool should_generate_constructor_barrier_; 399 400 // Cached constants. 401 HNullConstant* cached_null_constant_; 402 ArenaSafeMap<int32_t, HIntConstant*> cached_int_constants_; 403 ArenaSafeMap<int32_t, HFloatConstant*> cached_float_constants_; 404 ArenaSafeMap<int64_t, HLongConstant*> cached_long_constants_; 405 ArenaSafeMap<int64_t, HDoubleConstant*> cached_double_constants_; 406 407 HCurrentMethod* cached_current_method_; 408 409 friend class SsaBuilder; // For caching constants. 410 friend class SsaLivenessAnalysis; // For the linear order. 411 ART_FRIEND_TEST(GraphTest, IfSuccessorSimpleJoinBlock1); 412 DISALLOW_COPY_AND_ASSIGN(HGraph); 413}; 414 415class HLoopInformation : public ArenaObject<kArenaAllocMisc> { 416 public: 417 HLoopInformation(HBasicBlock* header, HGraph* graph) 418 : header_(header), 419 suspend_check_(nullptr), 420 back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges), 421 // Make bit vector growable, as the number of blocks may change. 422 blocks_(graph->GetArena(), graph->GetBlocks().Size(), true) {} 423 424 HBasicBlock* GetHeader() const { 425 return header_; 426 } 427 428 void SetHeader(HBasicBlock* block) { 429 header_ = block; 430 } 431 432 HSuspendCheck* GetSuspendCheck() const { return suspend_check_; } 433 void SetSuspendCheck(HSuspendCheck* check) { suspend_check_ = check; } 434 bool HasSuspendCheck() const { return suspend_check_ != nullptr; } 435 436 void AddBackEdge(HBasicBlock* back_edge) { 437 back_edges_.Add(back_edge); 438 } 439 440 void RemoveBackEdge(HBasicBlock* back_edge) { 441 back_edges_.Delete(back_edge); 442 } 443 444 bool IsBackEdge(const HBasicBlock& block) const { 445 for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) { 446 if (back_edges_.Get(i) == &block) return true; 447 } 448 return false; 449 } 450 451 size_t NumberOfBackEdges() const { 452 return back_edges_.Size(); 453 } 454 455 HBasicBlock* GetPreHeader() const; 456 457 const GrowableArray<HBasicBlock*>& GetBackEdges() const { 458 return back_edges_; 459 } 460 461 // Returns the lifetime position of the back edge that has the 462 // greatest lifetime position. 463 size_t GetLifetimeEnd() const; 464 465 void ReplaceBackEdge(HBasicBlock* existing, HBasicBlock* new_back_edge) { 466 for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) { 467 if (back_edges_.Get(i) == existing) { 468 back_edges_.Put(i, new_back_edge); 469 return; 470 } 471 } 472 UNREACHABLE(); 473 } 474 475 // Finds blocks that are part of this loop. Returns whether the loop is a natural loop, 476 // that is the header dominates the back edge. 477 bool Populate(); 478 479 // Reanalyzes the loop by removing loop info from its blocks and re-running 480 // Populate(). If there are no back edges left, the loop info is completely 481 // removed as well as its SuspendCheck instruction. It must be run on nested 482 // inner loops first. 483 void Update(); 484 485 // Returns whether this loop information contains `block`. 486 // Note that this loop information *must* be populated before entering this function. 487 bool Contains(const HBasicBlock& block) const; 488 489 // Returns whether this loop information is an inner loop of `other`. 490 // Note that `other` *must* be populated before entering this function. 491 bool IsIn(const HLoopInformation& other) const; 492 493 const ArenaBitVector& GetBlocks() const { return blocks_; } 494 495 void Add(HBasicBlock* block); 496 void Remove(HBasicBlock* block); 497 498 private: 499 // Internal recursive implementation of `Populate`. 500 void PopulateRecursive(HBasicBlock* block); 501 502 HBasicBlock* header_; 503 HSuspendCheck* suspend_check_; 504 GrowableArray<HBasicBlock*> back_edges_; 505 ArenaBitVector blocks_; 506 507 DISALLOW_COPY_AND_ASSIGN(HLoopInformation); 508}; 509 510static constexpr size_t kNoLifetime = -1; 511static constexpr uint32_t kNoDexPc = -1; 512 513// A block in a method. Contains the list of instructions represented 514// as a double linked list. Each block knows its predecessors and 515// successors. 516 517class HBasicBlock : public ArenaObject<kArenaAllocMisc> { 518 public: 519 explicit HBasicBlock(HGraph* graph, uint32_t dex_pc = kNoDexPc) 520 : graph_(graph), 521 predecessors_(graph->GetArena(), kDefaultNumberOfPredecessors), 522 successors_(graph->GetArena(), kDefaultNumberOfSuccessors), 523 loop_information_(nullptr), 524 dominator_(nullptr), 525 dominated_blocks_(graph->GetArena(), kDefaultNumberOfDominatedBlocks), 526 block_id_(-1), 527 dex_pc_(dex_pc), 528 lifetime_start_(kNoLifetime), 529 lifetime_end_(kNoLifetime), 530 is_catch_block_(false) {} 531 532 const GrowableArray<HBasicBlock*>& GetPredecessors() const { 533 return predecessors_; 534 } 535 536 const GrowableArray<HBasicBlock*>& GetSuccessors() const { 537 return successors_; 538 } 539 540 const GrowableArray<HBasicBlock*>& GetDominatedBlocks() const { 541 return dominated_blocks_; 542 } 543 544 bool IsEntryBlock() const { 545 return graph_->GetEntryBlock() == this; 546 } 547 548 bool IsExitBlock() const { 549 return graph_->GetExitBlock() == this; 550 } 551 552 bool IsSingleGoto() const; 553 554 void AddBackEdge(HBasicBlock* back_edge) { 555 if (loop_information_ == nullptr) { 556 loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_); 557 } 558 DCHECK_EQ(loop_information_->GetHeader(), this); 559 loop_information_->AddBackEdge(back_edge); 560 } 561 562 HGraph* GetGraph() const { return graph_; } 563 void SetGraph(HGraph* graph) { graph_ = graph; } 564 565 int GetBlockId() const { return block_id_; } 566 void SetBlockId(int id) { block_id_ = id; } 567 568 HBasicBlock* GetDominator() const { return dominator_; } 569 void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; } 570 void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); } 571 void RemoveDominatedBlock(HBasicBlock* block) { dominated_blocks_.Delete(block); } 572 void ReplaceDominatedBlock(HBasicBlock* existing, HBasicBlock* new_block) { 573 for (size_t i = 0, e = dominated_blocks_.Size(); i < e; ++i) { 574 if (dominated_blocks_.Get(i) == existing) { 575 dominated_blocks_.Put(i, new_block); 576 return; 577 } 578 } 579 LOG(FATAL) << "Unreachable"; 580 UNREACHABLE(); 581 } 582 583 int NumberOfBackEdges() const { 584 return loop_information_ == nullptr 585 ? 0 586 : loop_information_->NumberOfBackEdges(); 587 } 588 589 HInstruction* GetFirstInstruction() const { return instructions_.first_instruction_; } 590 HInstruction* GetLastInstruction() const { return instructions_.last_instruction_; } 591 const HInstructionList& GetInstructions() const { return instructions_; } 592 HInstruction* GetFirstPhi() const { return phis_.first_instruction_; } 593 HInstruction* GetLastPhi() const { return phis_.last_instruction_; } 594 const HInstructionList& GetPhis() const { return phis_; } 595 596 void AddSuccessor(HBasicBlock* block) { 597 successors_.Add(block); 598 block->predecessors_.Add(this); 599 } 600 601 void ReplaceSuccessor(HBasicBlock* existing, HBasicBlock* new_block) { 602 size_t successor_index = GetSuccessorIndexOf(existing); 603 DCHECK_NE(successor_index, static_cast<size_t>(-1)); 604 existing->RemovePredecessor(this); 605 new_block->predecessors_.Add(this); 606 successors_.Put(successor_index, new_block); 607 } 608 609 void ReplacePredecessor(HBasicBlock* existing, HBasicBlock* new_block) { 610 size_t predecessor_index = GetPredecessorIndexOf(existing); 611 DCHECK_NE(predecessor_index, static_cast<size_t>(-1)); 612 existing->RemoveSuccessor(this); 613 new_block->successors_.Add(this); 614 predecessors_.Put(predecessor_index, new_block); 615 } 616 617 void RemovePredecessor(HBasicBlock* block) { 618 predecessors_.Delete(block); 619 } 620 621 void RemoveSuccessor(HBasicBlock* block) { 622 successors_.Delete(block); 623 } 624 625 void ClearAllPredecessors() { 626 predecessors_.Reset(); 627 } 628 629 void AddPredecessor(HBasicBlock* block) { 630 predecessors_.Add(block); 631 block->successors_.Add(this); 632 } 633 634 void SwapPredecessors() { 635 DCHECK_EQ(predecessors_.Size(), 2u); 636 HBasicBlock* temp = predecessors_.Get(0); 637 predecessors_.Put(0, predecessors_.Get(1)); 638 predecessors_.Put(1, temp); 639 } 640 641 void SwapSuccessors() { 642 DCHECK_EQ(successors_.Size(), 2u); 643 HBasicBlock* temp = successors_.Get(0); 644 successors_.Put(0, successors_.Get(1)); 645 successors_.Put(1, temp); 646 } 647 648 size_t GetPredecessorIndexOf(HBasicBlock* predecessor) { 649 for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) { 650 if (predecessors_.Get(i) == predecessor) { 651 return i; 652 } 653 } 654 return -1; 655 } 656 657 size_t GetSuccessorIndexOf(HBasicBlock* successor) { 658 for (size_t i = 0, e = successors_.Size(); i < e; ++i) { 659 if (successors_.Get(i) == successor) { 660 return i; 661 } 662 } 663 return -1; 664 } 665 666 // Split the block into two blocks just after `cursor`. Returns the newly 667 // created block. Note that this method just updates raw block information, 668 // like predecessors, successors, dominators, and instruction list. It does not 669 // update the graph, reverse post order, loop information, nor make sure the 670 // blocks are consistent (for example ending with a control flow instruction). 671 HBasicBlock* SplitAfter(HInstruction* cursor); 672 673 // Merge `other` at the end of `this`. Successors and dominated blocks of 674 // `other` are changed to be successors and dominated blocks of `this`. Note 675 // that this method does not update the graph, reverse post order, loop 676 // information, nor make sure the blocks are consistent (for example ending 677 // with a control flow instruction). 678 void MergeWithInlined(HBasicBlock* other); 679 680 // Replace `this` with `other`. Predecessors, successors, and dominated blocks 681 // of `this` are moved to `other`. 682 // Note that this method does not update the graph, reverse post order, loop 683 // information, nor make sure the blocks are consistent (for example ending 684 // with a control flow instruction). 685 void ReplaceWith(HBasicBlock* other); 686 687 // Merge `other` at the end of `this`. This method updates loops, reverse post 688 // order, links to predecessors, successors, dominators and deletes the block 689 // from the graph. The two blocks must be successive, i.e. `this` the only 690 // predecessor of `other` and vice versa. 691 void MergeWith(HBasicBlock* other); 692 693 // Disconnects `this` from all its predecessors, successors and dominator, 694 // removes it from all loops it is included in and eventually from the graph. 695 // The block must not dominate any other block. Predecessors and successors 696 // are safely updated. 697 void DisconnectAndDelete(); 698 699 void AddInstruction(HInstruction* instruction); 700 // Insert `instruction` before/after an existing instruction `cursor`. 701 void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); 702 void InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor); 703 // Replace instruction `initial` with `replacement` within this block. 704 void ReplaceAndRemoveInstructionWith(HInstruction* initial, 705 HInstruction* replacement); 706 void AddPhi(HPhi* phi); 707 void InsertPhiAfter(HPhi* instruction, HPhi* cursor); 708 // RemoveInstruction and RemovePhi delete a given instruction from the respective 709 // instruction list. With 'ensure_safety' set to true, it verifies that the 710 // instruction is not in use and removes it from the use lists of its inputs. 711 void RemoveInstruction(HInstruction* instruction, bool ensure_safety = true); 712 void RemovePhi(HPhi* phi, bool ensure_safety = true); 713 void RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety = true); 714 715 bool IsLoopHeader() const { 716 return IsInLoop() && (loop_information_->GetHeader() == this); 717 } 718 719 bool IsLoopPreHeaderFirstPredecessor() const { 720 DCHECK(IsLoopHeader()); 721 DCHECK(!GetPredecessors().IsEmpty()); 722 return GetPredecessors().Get(0) == GetLoopInformation()->GetPreHeader(); 723 } 724 725 HLoopInformation* GetLoopInformation() const { 726 return loop_information_; 727 } 728 729 // Set the loop_information_ on this block. Overrides the current 730 // loop_information if it is an outer loop of the passed loop information. 731 // Note that this method is called while creating the loop information. 732 void SetInLoop(HLoopInformation* info) { 733 if (IsLoopHeader()) { 734 // Nothing to do. This just means `info` is an outer loop. 735 } else if (!IsInLoop()) { 736 loop_information_ = info; 737 } else if (loop_information_->Contains(*info->GetHeader())) { 738 // Block is currently part of an outer loop. Make it part of this inner loop. 739 // Note that a non loop header having a loop information means this loop information 740 // has already been populated 741 loop_information_ = info; 742 } else { 743 // Block is part of an inner loop. Do not update the loop information. 744 // Note that we cannot do the check `info->Contains(loop_information_)->GetHeader()` 745 // at this point, because this method is being called while populating `info`. 746 } 747 } 748 749 // Raw update of the loop information. 750 void SetLoopInformation(HLoopInformation* info) { 751 loop_information_ = info; 752 } 753 754 bool IsInLoop() const { return loop_information_ != nullptr; } 755 756 // Returns whether this block dominates the blocked passed as parameter. 757 bool Dominates(HBasicBlock* block) const; 758 759 size_t GetLifetimeStart() const { return lifetime_start_; } 760 size_t GetLifetimeEnd() const { return lifetime_end_; } 761 762 void SetLifetimeStart(size_t start) { lifetime_start_ = start; } 763 void SetLifetimeEnd(size_t end) { lifetime_end_ = end; } 764 765 uint32_t GetDexPc() const { return dex_pc_; } 766 767 bool IsCatchBlock() const { return is_catch_block_; } 768 void SetIsCatchBlock() { is_catch_block_ = true; } 769 770 bool EndsWithControlFlowInstruction() const; 771 bool EndsWithIf() const; 772 bool HasSinglePhi() const; 773 774 private: 775 HGraph* graph_; 776 GrowableArray<HBasicBlock*> predecessors_; 777 GrowableArray<HBasicBlock*> successors_; 778 HInstructionList instructions_; 779 HInstructionList phis_; 780 HLoopInformation* loop_information_; 781 HBasicBlock* dominator_; 782 GrowableArray<HBasicBlock*> dominated_blocks_; 783 int block_id_; 784 // The dex program counter of the first instruction of this block. 785 const uint32_t dex_pc_; 786 size_t lifetime_start_; 787 size_t lifetime_end_; 788 bool is_catch_block_; 789 790 friend class HGraph; 791 friend class HInstruction; 792 793 DISALLOW_COPY_AND_ASSIGN(HBasicBlock); 794}; 795 796// Iterates over the LoopInformation of all loops which contain 'block' 797// from the innermost to the outermost. 798class HLoopInformationOutwardIterator : public ValueObject { 799 public: 800 explicit HLoopInformationOutwardIterator(const HBasicBlock& block) 801 : current_(block.GetLoopInformation()) {} 802 803 bool Done() const { return current_ == nullptr; } 804 805 void Advance() { 806 DCHECK(!Done()); 807 current_ = current_->GetPreHeader()->GetLoopInformation(); 808 } 809 810 HLoopInformation* Current() const { 811 DCHECK(!Done()); 812 return current_; 813 } 814 815 private: 816 HLoopInformation* current_; 817 818 DISALLOW_COPY_AND_ASSIGN(HLoopInformationOutwardIterator); 819}; 820 821#define FOR_EACH_CONCRETE_INSTRUCTION(M) \ 822 M(Add, BinaryOperation) \ 823 M(And, BinaryOperation) \ 824 M(ArrayGet, Instruction) \ 825 M(ArrayLength, Instruction) \ 826 M(ArraySet, Instruction) \ 827 M(BooleanNot, UnaryOperation) \ 828 M(BoundsCheck, Instruction) \ 829 M(BoundType, Instruction) \ 830 M(CheckCast, Instruction) \ 831 M(ClinitCheck, Instruction) \ 832 M(Compare, BinaryOperation) \ 833 M(Condition, BinaryOperation) \ 834 M(CurrentMethod, Instruction) \ 835 M(Deoptimize, Instruction) \ 836 M(Div, BinaryOperation) \ 837 M(DivZeroCheck, Instruction) \ 838 M(DoubleConstant, Constant) \ 839 M(Equal, Condition) \ 840 M(Exit, Instruction) \ 841 M(FloatConstant, Constant) \ 842 M(Goto, Instruction) \ 843 M(GreaterThan, Condition) \ 844 M(GreaterThanOrEqual, Condition) \ 845 M(If, Instruction) \ 846 M(InstanceFieldGet, Instruction) \ 847 M(InstanceFieldSet, Instruction) \ 848 M(InstanceOf, Instruction) \ 849 M(IntConstant, Constant) \ 850 M(InvokeInterface, Invoke) \ 851 M(InvokeStaticOrDirect, Invoke) \ 852 M(InvokeVirtual, Invoke) \ 853 M(LessThan, Condition) \ 854 M(LessThanOrEqual, Condition) \ 855 M(LoadClass, Instruction) \ 856 M(LoadException, Instruction) \ 857 M(LoadLocal, Instruction) \ 858 M(LoadString, Instruction) \ 859 M(Local, Instruction) \ 860 M(LongConstant, Constant) \ 861 M(MemoryBarrier, Instruction) \ 862 M(MonitorOperation, Instruction) \ 863 M(Mul, BinaryOperation) \ 864 M(Neg, UnaryOperation) \ 865 M(NewArray, Instruction) \ 866 M(NewInstance, Instruction) \ 867 M(Not, UnaryOperation) \ 868 M(NotEqual, Condition) \ 869 M(NullConstant, Instruction) \ 870 M(NullCheck, Instruction) \ 871 M(Or, BinaryOperation) \ 872 M(ParallelMove, Instruction) \ 873 M(ParameterValue, Instruction) \ 874 M(Phi, Instruction) \ 875 M(Rem, BinaryOperation) \ 876 M(Return, Instruction) \ 877 M(ReturnVoid, Instruction) \ 878 M(Shl, BinaryOperation) \ 879 M(Shr, BinaryOperation) \ 880 M(StaticFieldGet, Instruction) \ 881 M(StaticFieldSet, Instruction) \ 882 M(StoreLocal, Instruction) \ 883 M(Sub, BinaryOperation) \ 884 M(SuspendCheck, Instruction) \ 885 M(Temporary, Instruction) \ 886 M(Throw, Instruction) \ 887 M(TypeConversion, Instruction) \ 888 M(UShr, BinaryOperation) \ 889 M(Xor, BinaryOperation) \ 890 891#define FOR_EACH_INSTRUCTION(M) \ 892 FOR_EACH_CONCRETE_INSTRUCTION(M) \ 893 M(Constant, Instruction) \ 894 M(UnaryOperation, Instruction) \ 895 M(BinaryOperation, Instruction) \ 896 M(Invoke, Instruction) 897 898#define FORWARD_DECLARATION(type, super) class H##type; 899FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) 900#undef FORWARD_DECLARATION 901 902#define DECLARE_INSTRUCTION(type) \ 903 InstructionKind GetKind() const OVERRIDE { return k##type; } \ 904 const char* DebugName() const OVERRIDE { return #type; } \ 905 const H##type* As##type() const OVERRIDE { return this; } \ 906 H##type* As##type() OVERRIDE { return this; } \ 907 bool InstructionTypeEquals(HInstruction* other) const OVERRIDE { \ 908 return other->Is##type(); \ 909 } \ 910 void Accept(HGraphVisitor* visitor) OVERRIDE 911 912template <typename T> class HUseList; 913 914template <typename T> 915class HUseListNode : public ArenaObject<kArenaAllocMisc> { 916 public: 917 HUseListNode* GetPrevious() const { return prev_; } 918 HUseListNode* GetNext() const { return next_; } 919 T GetUser() const { return user_; } 920 size_t GetIndex() const { return index_; } 921 void SetIndex(size_t index) { index_ = index; } 922 923 private: 924 HUseListNode(T user, size_t index) 925 : user_(user), index_(index), prev_(nullptr), next_(nullptr) {} 926 927 T const user_; 928 size_t index_; 929 HUseListNode<T>* prev_; 930 HUseListNode<T>* next_; 931 932 friend class HUseList<T>; 933 934 DISALLOW_COPY_AND_ASSIGN(HUseListNode); 935}; 936 937template <typename T> 938class HUseList : public ValueObject { 939 public: 940 HUseList() : first_(nullptr) {} 941 942 void Clear() { 943 first_ = nullptr; 944 } 945 946 // Adds a new entry at the beginning of the use list and returns 947 // the newly created node. 948 HUseListNode<T>* AddUse(T user, size_t index, ArenaAllocator* arena) { 949 HUseListNode<T>* new_node = new (arena) HUseListNode<T>(user, index); 950 if (IsEmpty()) { 951 first_ = new_node; 952 } else { 953 first_->prev_ = new_node; 954 new_node->next_ = first_; 955 first_ = new_node; 956 } 957 return new_node; 958 } 959 960 HUseListNode<T>* GetFirst() const { 961 return first_; 962 } 963 964 void Remove(HUseListNode<T>* node) { 965 DCHECK(node != nullptr); 966 DCHECK(Contains(node)); 967 968 if (node->prev_ != nullptr) { 969 node->prev_->next_ = node->next_; 970 } 971 if (node->next_ != nullptr) { 972 node->next_->prev_ = node->prev_; 973 } 974 if (node == first_) { 975 first_ = node->next_; 976 } 977 } 978 979 bool Contains(const HUseListNode<T>* node) const { 980 if (node == nullptr) { 981 return false; 982 } 983 for (HUseListNode<T>* current = first_; current != nullptr; current = current->GetNext()) { 984 if (current == node) { 985 return true; 986 } 987 } 988 return false; 989 } 990 991 bool IsEmpty() const { 992 return first_ == nullptr; 993 } 994 995 bool HasOnlyOneUse() const { 996 return first_ != nullptr && first_->next_ == nullptr; 997 } 998 999 size_t SizeSlow() const { 1000 size_t count = 0; 1001 for (HUseListNode<T>* current = first_; current != nullptr; current = current->GetNext()) { 1002 ++count; 1003 } 1004 return count; 1005 } 1006 1007 private: 1008 HUseListNode<T>* first_; 1009}; 1010 1011template<typename T> 1012class HUseIterator : public ValueObject { 1013 public: 1014 explicit HUseIterator(const HUseList<T>& uses) : current_(uses.GetFirst()) {} 1015 1016 bool Done() const { return current_ == nullptr; } 1017 1018 void Advance() { 1019 DCHECK(!Done()); 1020 current_ = current_->GetNext(); 1021 } 1022 1023 HUseListNode<T>* Current() const { 1024 DCHECK(!Done()); 1025 return current_; 1026 } 1027 1028 private: 1029 HUseListNode<T>* current_; 1030 1031 friend class HValue; 1032}; 1033 1034// This class is used by HEnvironment and HInstruction classes to record the 1035// instructions they use and pointers to the corresponding HUseListNodes kept 1036// by the used instructions. 1037template <typename T> 1038class HUserRecord : public ValueObject { 1039 public: 1040 HUserRecord() : instruction_(nullptr), use_node_(nullptr) {} 1041 explicit HUserRecord(HInstruction* instruction) : instruction_(instruction), use_node_(nullptr) {} 1042 1043 HUserRecord(const HUserRecord<T>& old_record, HUseListNode<T>* use_node) 1044 : instruction_(old_record.instruction_), use_node_(use_node) { 1045 DCHECK(instruction_ != nullptr); 1046 DCHECK(use_node_ != nullptr); 1047 DCHECK(old_record.use_node_ == nullptr); 1048 } 1049 1050 HInstruction* GetInstruction() const { return instruction_; } 1051 HUseListNode<T>* GetUseNode() const { return use_node_; } 1052 1053 private: 1054 // Instruction used by the user. 1055 HInstruction* instruction_; 1056 1057 // Corresponding entry in the use list kept by 'instruction_'. 1058 HUseListNode<T>* use_node_; 1059}; 1060 1061// TODO: Add better documentation to this class and maybe refactor with more suggestive names. 1062// - Has(All)SideEffects suggests that all the side effects are present but only ChangesSomething 1063// flag is consider. 1064// - DependsOn suggests that there is a real dependency between side effects but it only 1065// checks DependendsOnSomething flag. 1066// 1067// Represents the side effects an instruction may have. 1068class SideEffects : public ValueObject { 1069 public: 1070 SideEffects() : flags_(0) {} 1071 1072 static SideEffects None() { 1073 return SideEffects(0); 1074 } 1075 1076 static SideEffects All() { 1077 return SideEffects(ChangesSomething().flags_ | DependsOnSomething().flags_); 1078 } 1079 1080 static SideEffects ChangesSomething() { 1081 return SideEffects((1 << kFlagChangesCount) - 1); 1082 } 1083 1084 static SideEffects DependsOnSomething() { 1085 int count = kFlagDependsOnCount - kFlagChangesCount; 1086 return SideEffects(((1 << count) - 1) << kFlagChangesCount); 1087 } 1088 1089 SideEffects Union(SideEffects other) const { 1090 return SideEffects(flags_ | other.flags_); 1091 } 1092 1093 bool HasSideEffects() const { 1094 size_t all_bits_set = (1 << kFlagChangesCount) - 1; 1095 return (flags_ & all_bits_set) != 0; 1096 } 1097 1098 bool HasAllSideEffects() const { 1099 size_t all_bits_set = (1 << kFlagChangesCount) - 1; 1100 return all_bits_set == (flags_ & all_bits_set); 1101 } 1102 1103 bool DependsOn(SideEffects other) const { 1104 size_t depends_flags = other.ComputeDependsFlags(); 1105 return (flags_ & depends_flags) != 0; 1106 } 1107 1108 bool HasDependencies() const { 1109 int count = kFlagDependsOnCount - kFlagChangesCount; 1110 size_t all_bits_set = (1 << count) - 1; 1111 return ((flags_ >> kFlagChangesCount) & all_bits_set) != 0; 1112 } 1113 1114 private: 1115 static constexpr int kFlagChangesSomething = 0; 1116 static constexpr int kFlagChangesCount = kFlagChangesSomething + 1; 1117 1118 static constexpr int kFlagDependsOnSomething = kFlagChangesCount; 1119 static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1; 1120 1121 explicit SideEffects(size_t flags) : flags_(flags) {} 1122 1123 size_t ComputeDependsFlags() const { 1124 return flags_ << kFlagChangesCount; 1125 } 1126 1127 size_t flags_; 1128}; 1129 1130// A HEnvironment object contains the values of virtual registers at a given location. 1131class HEnvironment : public ArenaObject<kArenaAllocMisc> { 1132 public: 1133 HEnvironment(ArenaAllocator* arena, 1134 size_t number_of_vregs, 1135 const DexFile& dex_file, 1136 uint32_t method_idx, 1137 uint32_t dex_pc, 1138 InvokeType invoke_type, 1139 HInstruction* holder) 1140 : vregs_(arena, number_of_vregs), 1141 locations_(arena, number_of_vregs), 1142 parent_(nullptr), 1143 dex_file_(dex_file), 1144 method_idx_(method_idx), 1145 dex_pc_(dex_pc), 1146 invoke_type_(invoke_type), 1147 holder_(holder) { 1148 vregs_.SetSize(number_of_vregs); 1149 for (size_t i = 0; i < number_of_vregs; i++) { 1150 vregs_.Put(i, HUserRecord<HEnvironment*>()); 1151 } 1152 1153 locations_.SetSize(number_of_vregs); 1154 for (size_t i = 0; i < number_of_vregs; ++i) { 1155 locations_.Put(i, Location()); 1156 } 1157 } 1158 1159 HEnvironment(ArenaAllocator* arena, const HEnvironment& to_copy, HInstruction* holder) 1160 : HEnvironment(arena, 1161 to_copy.Size(), 1162 to_copy.GetDexFile(), 1163 to_copy.GetMethodIdx(), 1164 to_copy.GetDexPc(), 1165 to_copy.GetInvokeType(), 1166 holder) {} 1167 1168 void SetAndCopyParentChain(ArenaAllocator* allocator, HEnvironment* parent) { 1169 if (parent_ != nullptr) { 1170 parent_->SetAndCopyParentChain(allocator, parent); 1171 } else { 1172 parent_ = new (allocator) HEnvironment(allocator, *parent, holder_); 1173 parent_->CopyFrom(parent); 1174 if (parent->GetParent() != nullptr) { 1175 parent_->SetAndCopyParentChain(allocator, parent->GetParent()); 1176 } 1177 } 1178 } 1179 1180 void CopyFrom(const GrowableArray<HInstruction*>& locals); 1181 void CopyFrom(HEnvironment* environment); 1182 1183 // Copy from `env`. If it's a loop phi for `loop_header`, copy the first 1184 // input to the loop phi instead. This is for inserting instructions that 1185 // require an environment (like HDeoptimization) in the loop pre-header. 1186 void CopyFromWithLoopPhiAdjustment(HEnvironment* env, HBasicBlock* loop_header); 1187 1188 void SetRawEnvAt(size_t index, HInstruction* instruction) { 1189 vregs_.Put(index, HUserRecord<HEnvironment*>(instruction)); 1190 } 1191 1192 HInstruction* GetInstructionAt(size_t index) const { 1193 return vregs_.Get(index).GetInstruction(); 1194 } 1195 1196 void RemoveAsUserOfInput(size_t index) const; 1197 1198 size_t Size() const { return vregs_.Size(); } 1199 1200 HEnvironment* GetParent() const { return parent_; } 1201 1202 void SetLocationAt(size_t index, Location location) { 1203 locations_.Put(index, location); 1204 } 1205 1206 Location GetLocationAt(size_t index) const { 1207 return locations_.Get(index); 1208 } 1209 1210 uint32_t GetDexPc() const { 1211 return dex_pc_; 1212 } 1213 1214 uint32_t GetMethodIdx() const { 1215 return method_idx_; 1216 } 1217 1218 InvokeType GetInvokeType() const { 1219 return invoke_type_; 1220 } 1221 1222 const DexFile& GetDexFile() const { 1223 return dex_file_; 1224 } 1225 1226 HInstruction* GetHolder() const { 1227 return holder_; 1228 } 1229 1230 private: 1231 // Record instructions' use entries of this environment for constant-time removal. 1232 // It should only be called by HInstruction when a new environment use is added. 1233 void RecordEnvUse(HUseListNode<HEnvironment*>* env_use) { 1234 DCHECK(env_use->GetUser() == this); 1235 size_t index = env_use->GetIndex(); 1236 vregs_.Put(index, HUserRecord<HEnvironment*>(vregs_.Get(index), env_use)); 1237 } 1238 1239 GrowableArray<HUserRecord<HEnvironment*> > vregs_; 1240 GrowableArray<Location> locations_; 1241 HEnvironment* parent_; 1242 const DexFile& dex_file_; 1243 const uint32_t method_idx_; 1244 const uint32_t dex_pc_; 1245 const InvokeType invoke_type_; 1246 1247 // The instruction that holds this environment. Only used in debug mode 1248 // to ensure the graph is consistent. 1249 HInstruction* const holder_; 1250 1251 friend class HInstruction; 1252 1253 DISALLOW_COPY_AND_ASSIGN(HEnvironment); 1254}; 1255 1256class ReferenceTypeInfo : ValueObject { 1257 public: 1258 typedef Handle<mirror::Class> TypeHandle; 1259 1260 static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact) 1261 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 1262 if (type_handle->IsObjectClass()) { 1263 // Override the type handle to be consistent with the case when we get to 1264 // Top but don't have the Object class available. It avoids having to guess 1265 // what value the type_handle has when it's Top. 1266 return ReferenceTypeInfo(TypeHandle(), is_exact, true); 1267 } else { 1268 return ReferenceTypeInfo(type_handle, is_exact, false); 1269 } 1270 } 1271 1272 static ReferenceTypeInfo CreateTop(bool is_exact) { 1273 return ReferenceTypeInfo(TypeHandle(), is_exact, true); 1274 } 1275 1276 bool IsExact() const { return is_exact_; } 1277 bool IsTop() const { return is_top_; } 1278 1279 Handle<mirror::Class> GetTypeHandle() const { return type_handle_; } 1280 1281 bool IsSupertypeOf(ReferenceTypeInfo rti) const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 1282 if (IsTop()) { 1283 // Top (equivalent for java.lang.Object) is supertype of anything. 1284 return true; 1285 } 1286 if (rti.IsTop()) { 1287 // If we get here `this` is not Top() so it can't be a supertype. 1288 return false; 1289 } 1290 return GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get()); 1291 } 1292 1293 // Returns true if the type information provide the same amount of details. 1294 // Note that it does not mean that the instructions have the same actual type 1295 // (e.g. tops are equal but they can be the result of a merge). 1296 bool IsEqual(ReferenceTypeInfo rti) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 1297 if (IsExact() != rti.IsExact()) { 1298 return false; 1299 } 1300 if (IsTop() && rti.IsTop()) { 1301 // `Top` means java.lang.Object, so the types are equivalent. 1302 return true; 1303 } 1304 if (IsTop() || rti.IsTop()) { 1305 // If only one is top or object than they are not equivalent. 1306 // NB: We need this extra check because the type_handle of `Top` is invalid 1307 // and we cannot inspect its reference. 1308 return false; 1309 } 1310 1311 // Finally check the types. 1312 return GetTypeHandle().Get() == rti.GetTypeHandle().Get(); 1313 } 1314 1315 private: 1316 ReferenceTypeInfo() : ReferenceTypeInfo(TypeHandle(), false, true) {} 1317 ReferenceTypeInfo(TypeHandle type_handle, bool is_exact, bool is_top) 1318 : type_handle_(type_handle), is_exact_(is_exact), is_top_(is_top) {} 1319 1320 // The class of the object. 1321 TypeHandle type_handle_; 1322 // Whether or not the type is exact or a superclass of the actual type. 1323 // Whether or not we have any information about this type. 1324 bool is_exact_; 1325 // A true value here means that the object type should be java.lang.Object. 1326 // We don't have access to the corresponding mirror object every time so this 1327 // flag acts as a substitute. When true, the TypeHandle refers to a null 1328 // pointer and should not be used. 1329 bool is_top_; 1330}; 1331 1332std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs); 1333 1334class HInstruction : public ArenaObject<kArenaAllocMisc> { 1335 public: 1336 explicit HInstruction(SideEffects side_effects) 1337 : previous_(nullptr), 1338 next_(nullptr), 1339 block_(nullptr), 1340 id_(-1), 1341 ssa_index_(-1), 1342 environment_(nullptr), 1343 locations_(nullptr), 1344 live_interval_(nullptr), 1345 lifetime_position_(kNoLifetime), 1346 side_effects_(side_effects), 1347 reference_type_info_(ReferenceTypeInfo::CreateTop(/* is_exact */ false)) {} 1348 1349 virtual ~HInstruction() {} 1350 1351#define DECLARE_KIND(type, super) k##type, 1352 enum InstructionKind { 1353 FOR_EACH_INSTRUCTION(DECLARE_KIND) 1354 }; 1355#undef DECLARE_KIND 1356 1357 HInstruction* GetNext() const { return next_; } 1358 HInstruction* GetPrevious() const { return previous_; } 1359 1360 HInstruction* GetNextDisregardingMoves() const; 1361 HInstruction* GetPreviousDisregardingMoves() const; 1362 1363 HBasicBlock* GetBlock() const { return block_; } 1364 void SetBlock(HBasicBlock* block) { block_ = block; } 1365 bool IsInBlock() const { return block_ != nullptr; } 1366 bool IsInLoop() const { return block_->IsInLoop(); } 1367 bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); } 1368 1369 virtual size_t InputCount() const = 0; 1370 HInstruction* InputAt(size_t i) const { return InputRecordAt(i).GetInstruction(); } 1371 1372 virtual void Accept(HGraphVisitor* visitor) = 0; 1373 virtual const char* DebugName() const = 0; 1374 1375 virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; } 1376 void SetRawInputAt(size_t index, HInstruction* input) { 1377 SetRawInputRecordAt(index, HUserRecord<HInstruction*>(input)); 1378 } 1379 1380 virtual bool NeedsEnvironment() const { return false; } 1381 virtual uint32_t GetDexPc() const { 1382 LOG(FATAL) << "GetDexPc() cannot be called on an instruction that" 1383 " does not need an environment"; 1384 UNREACHABLE(); 1385 } 1386 virtual bool IsControlFlow() const { return false; } 1387 virtual bool CanThrow() const { return false; } 1388 bool HasSideEffects() const { return side_effects_.HasSideEffects(); } 1389 1390 // Does not apply for all instructions, but having this at top level greatly 1391 // simplifies the null check elimination. 1392 virtual bool CanBeNull() const { 1393 DCHECK_EQ(GetType(), Primitive::kPrimNot) << "CanBeNull only applies to reference types"; 1394 return true; 1395 } 1396 1397 virtual bool CanDoImplicitNullCheckOn(HInstruction* obj) const { 1398 UNUSED(obj); 1399 return false; 1400 } 1401 1402 void SetReferenceTypeInfo(ReferenceTypeInfo reference_type_info) { 1403 DCHECK_EQ(GetType(), Primitive::kPrimNot); 1404 reference_type_info_ = reference_type_info; 1405 } 1406 1407 ReferenceTypeInfo GetReferenceTypeInfo() const { 1408 DCHECK_EQ(GetType(), Primitive::kPrimNot); 1409 return reference_type_info_; 1410 } 1411 1412 void AddUseAt(HInstruction* user, size_t index) { 1413 DCHECK(user != nullptr); 1414 HUseListNode<HInstruction*>* use = 1415 uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); 1416 user->SetRawInputRecordAt(index, HUserRecord<HInstruction*>(user->InputRecordAt(index), use)); 1417 } 1418 1419 void AddEnvUseAt(HEnvironment* user, size_t index) { 1420 DCHECK(user != nullptr); 1421 HUseListNode<HEnvironment*>* env_use = 1422 env_uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); 1423 user->RecordEnvUse(env_use); 1424 } 1425 1426 void RemoveAsUserOfInput(size_t input) { 1427 HUserRecord<HInstruction*> input_use = InputRecordAt(input); 1428 input_use.GetInstruction()->uses_.Remove(input_use.GetUseNode()); 1429 } 1430 1431 const HUseList<HInstruction*>& GetUses() const { return uses_; } 1432 const HUseList<HEnvironment*>& GetEnvUses() const { return env_uses_; } 1433 1434 bool HasUses() const { return !uses_.IsEmpty() || !env_uses_.IsEmpty(); } 1435 bool HasEnvironmentUses() const { return !env_uses_.IsEmpty(); } 1436 bool HasNonEnvironmentUses() const { return !uses_.IsEmpty(); } 1437 bool HasOnlyOneNonEnvironmentUse() const { 1438 return !HasEnvironmentUses() && GetUses().HasOnlyOneUse(); 1439 } 1440 1441 // Does this instruction strictly dominate `other_instruction`? 1442 // Returns false if this instruction and `other_instruction` are the same. 1443 // Aborts if this instruction and `other_instruction` are both phis. 1444 bool StrictlyDominates(HInstruction* other_instruction) const; 1445 1446 int GetId() const { return id_; } 1447 void SetId(int id) { id_ = id; } 1448 1449 int GetSsaIndex() const { return ssa_index_; } 1450 void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; } 1451 bool HasSsaIndex() const { return ssa_index_ != -1; } 1452 1453 bool HasEnvironment() const { return environment_ != nullptr; } 1454 HEnvironment* GetEnvironment() const { return environment_; } 1455 // Set the `environment_` field. Raw because this method does not 1456 // update the uses lists. 1457 void SetRawEnvironment(HEnvironment* environment) { 1458 DCHECK(environment_ == nullptr); 1459 DCHECK_EQ(environment->GetHolder(), this); 1460 environment_ = environment; 1461 } 1462 1463 // Set the environment of this instruction, copying it from `environment`. While 1464 // copying, the uses lists are being updated. 1465 void CopyEnvironmentFrom(HEnvironment* environment) { 1466 DCHECK(environment_ == nullptr); 1467 ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena(); 1468 environment_ = new (allocator) HEnvironment(allocator, *environment, this); 1469 environment_->CopyFrom(environment); 1470 if (environment->GetParent() != nullptr) { 1471 environment_->SetAndCopyParentChain(allocator, environment->GetParent()); 1472 } 1473 } 1474 1475 void CopyEnvironmentFromWithLoopPhiAdjustment(HEnvironment* environment, 1476 HBasicBlock* block) { 1477 DCHECK(environment_ == nullptr); 1478 ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena(); 1479 environment_ = new (allocator) HEnvironment(allocator, *environment, this); 1480 environment_->CopyFromWithLoopPhiAdjustment(environment, block); 1481 if (environment->GetParent() != nullptr) { 1482 environment_->SetAndCopyParentChain(allocator, environment->GetParent()); 1483 } 1484 } 1485 1486 // Returns the number of entries in the environment. Typically, that is the 1487 // number of dex registers in a method. It could be more in case of inlining. 1488 size_t EnvironmentSize() const; 1489 1490 LocationSummary* GetLocations() const { return locations_; } 1491 void SetLocations(LocationSummary* locations) { locations_ = locations; } 1492 1493 void ReplaceWith(HInstruction* instruction); 1494 void ReplaceInput(HInstruction* replacement, size_t index); 1495 1496 // This is almost the same as doing `ReplaceWith()`. But in this helper, the 1497 // uses of this instruction by `other` are *not* updated. 1498 void ReplaceWithExceptInReplacementAtIndex(HInstruction* other, size_t use_index) { 1499 ReplaceWith(other); 1500 other->ReplaceInput(this, use_index); 1501 } 1502 1503 // Move `this` instruction before `cursor`. 1504 void MoveBefore(HInstruction* cursor); 1505 1506#define INSTRUCTION_TYPE_CHECK(type, super) \ 1507 bool Is##type() const { return (As##type() != nullptr); } \ 1508 virtual const H##type* As##type() const { return nullptr; } \ 1509 virtual H##type* As##type() { return nullptr; } 1510 1511 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 1512#undef INSTRUCTION_TYPE_CHECK 1513 1514 // Returns whether the instruction can be moved within the graph. 1515 virtual bool CanBeMoved() const { return false; } 1516 1517 // Returns whether the two instructions are of the same kind. 1518 virtual bool InstructionTypeEquals(HInstruction* other) const { 1519 UNUSED(other); 1520 return false; 1521 } 1522 1523 // Returns whether any data encoded in the two instructions is equal. 1524 // This method does not look at the inputs. Both instructions must be 1525 // of the same type, otherwise the method has undefined behavior. 1526 virtual bool InstructionDataEquals(HInstruction* other) const { 1527 UNUSED(other); 1528 return false; 1529 } 1530 1531 // Returns whether two instructions are equal, that is: 1532 // 1) They have the same type and contain the same data (InstructionDataEquals). 1533 // 2) Their inputs are identical. 1534 bool Equals(HInstruction* other) const; 1535 1536 virtual InstructionKind GetKind() const = 0; 1537 1538 virtual size_t ComputeHashCode() const { 1539 size_t result = GetKind(); 1540 for (size_t i = 0, e = InputCount(); i < e; ++i) { 1541 result = (result * 31) + InputAt(i)->GetId(); 1542 } 1543 return result; 1544 } 1545 1546 SideEffects GetSideEffects() const { return side_effects_; } 1547 1548 size_t GetLifetimePosition() const { return lifetime_position_; } 1549 void SetLifetimePosition(size_t position) { lifetime_position_ = position; } 1550 LiveInterval* GetLiveInterval() const { return live_interval_; } 1551 void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; } 1552 bool HasLiveInterval() const { return live_interval_ != nullptr; } 1553 1554 bool IsSuspendCheckEntry() const { return IsSuspendCheck() && GetBlock()->IsEntryBlock(); } 1555 1556 // Returns whether the code generation of the instruction will require to have access 1557 // to the current method. Such instructions are: 1558 // (1): Instructions that require an environment, as calling the runtime requires 1559 // to walk the stack and have the current method stored at a specific stack address. 1560 // (2): Object literals like classes and strings, that are loaded from the dex cache 1561 // fields of the current method. 1562 bool NeedsCurrentMethod() const { 1563 return NeedsEnvironment() || IsLoadClass() || IsLoadString(); 1564 } 1565 1566 virtual bool NeedsDexCache() const { return false; } 1567 1568 protected: 1569 virtual const HUserRecord<HInstruction*> InputRecordAt(size_t i) const = 0; 1570 virtual void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) = 0; 1571 1572 private: 1573 void RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use_node) { env_uses_.Remove(use_node); } 1574 1575 HInstruction* previous_; 1576 HInstruction* next_; 1577 HBasicBlock* block_; 1578 1579 // An instruction gets an id when it is added to the graph. 1580 // It reflects creation order. A negative id means the instruction 1581 // has not been added to the graph. 1582 int id_; 1583 1584 // When doing liveness analysis, instructions that have uses get an SSA index. 1585 int ssa_index_; 1586 1587 // List of instructions that have this instruction as input. 1588 HUseList<HInstruction*> uses_; 1589 1590 // List of environments that contain this instruction. 1591 HUseList<HEnvironment*> env_uses_; 1592 1593 // The environment associated with this instruction. Not null if the instruction 1594 // might jump out of the method. 1595 HEnvironment* environment_; 1596 1597 // Set by the code generator. 1598 LocationSummary* locations_; 1599 1600 // Set by the liveness analysis. 1601 LiveInterval* live_interval_; 1602 1603 // Set by the liveness analysis, this is the position in a linear 1604 // order of blocks where this instruction's live interval start. 1605 size_t lifetime_position_; 1606 1607 const SideEffects side_effects_; 1608 1609 // TODO: for primitive types this should be marked as invalid. 1610 ReferenceTypeInfo reference_type_info_; 1611 1612 friend class GraphChecker; 1613 friend class HBasicBlock; 1614 friend class HEnvironment; 1615 friend class HGraph; 1616 friend class HInstructionList; 1617 1618 DISALLOW_COPY_AND_ASSIGN(HInstruction); 1619}; 1620std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs); 1621 1622class HInputIterator : public ValueObject { 1623 public: 1624 explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {} 1625 1626 bool Done() const { return index_ == instruction_->InputCount(); } 1627 HInstruction* Current() const { return instruction_->InputAt(index_); } 1628 void Advance() { index_++; } 1629 1630 private: 1631 HInstruction* instruction_; 1632 size_t index_; 1633 1634 DISALLOW_COPY_AND_ASSIGN(HInputIterator); 1635}; 1636 1637class HInstructionIterator : public ValueObject { 1638 public: 1639 explicit HInstructionIterator(const HInstructionList& instructions) 1640 : instruction_(instructions.first_instruction_) { 1641 next_ = Done() ? nullptr : instruction_->GetNext(); 1642 } 1643 1644 bool Done() const { return instruction_ == nullptr; } 1645 HInstruction* Current() const { return instruction_; } 1646 void Advance() { 1647 instruction_ = next_; 1648 next_ = Done() ? nullptr : instruction_->GetNext(); 1649 } 1650 1651 private: 1652 HInstruction* instruction_; 1653 HInstruction* next_; 1654 1655 DISALLOW_COPY_AND_ASSIGN(HInstructionIterator); 1656}; 1657 1658class HBackwardInstructionIterator : public ValueObject { 1659 public: 1660 explicit HBackwardInstructionIterator(const HInstructionList& instructions) 1661 : instruction_(instructions.last_instruction_) { 1662 next_ = Done() ? nullptr : instruction_->GetPrevious(); 1663 } 1664 1665 bool Done() const { return instruction_ == nullptr; } 1666 HInstruction* Current() const { return instruction_; } 1667 void Advance() { 1668 instruction_ = next_; 1669 next_ = Done() ? nullptr : instruction_->GetPrevious(); 1670 } 1671 1672 private: 1673 HInstruction* instruction_; 1674 HInstruction* next_; 1675 1676 DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator); 1677}; 1678 1679// An embedded container with N elements of type T. Used (with partial 1680// specialization for N=0) because embedded arrays cannot have size 0. 1681template<typename T, intptr_t N> 1682class EmbeddedArray { 1683 public: 1684 EmbeddedArray() : elements_() {} 1685 1686 intptr_t GetLength() const { return N; } 1687 1688 const T& operator[](intptr_t i) const { 1689 DCHECK_LT(i, GetLength()); 1690 return elements_[i]; 1691 } 1692 1693 T& operator[](intptr_t i) { 1694 DCHECK_LT(i, GetLength()); 1695 return elements_[i]; 1696 } 1697 1698 const T& At(intptr_t i) const { 1699 return (*this)[i]; 1700 } 1701 1702 void SetAt(intptr_t i, const T& val) { 1703 (*this)[i] = val; 1704 } 1705 1706 private: 1707 T elements_[N]; 1708}; 1709 1710template<typename T> 1711class EmbeddedArray<T, 0> { 1712 public: 1713 intptr_t length() const { return 0; } 1714 const T& operator[](intptr_t i) const { 1715 UNUSED(i); 1716 LOG(FATAL) << "Unreachable"; 1717 UNREACHABLE(); 1718 } 1719 T& operator[](intptr_t i) { 1720 UNUSED(i); 1721 LOG(FATAL) << "Unreachable"; 1722 UNREACHABLE(); 1723 } 1724}; 1725 1726template<intptr_t N> 1727class HTemplateInstruction: public HInstruction { 1728 public: 1729 HTemplateInstruction<N>(SideEffects side_effects) 1730 : HInstruction(side_effects), inputs_() {} 1731 virtual ~HTemplateInstruction() {} 1732 1733 size_t InputCount() const OVERRIDE { return N; } 1734 1735 protected: 1736 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_[i]; } 1737 1738 void SetRawInputRecordAt(size_t i, const HUserRecord<HInstruction*>& input) OVERRIDE { 1739 inputs_[i] = input; 1740 } 1741 1742 private: 1743 EmbeddedArray<HUserRecord<HInstruction*>, N> inputs_; 1744 1745 friend class SsaBuilder; 1746}; 1747 1748template<intptr_t N> 1749class HExpression : public HTemplateInstruction<N> { 1750 public: 1751 HExpression<N>(Primitive::Type type, SideEffects side_effects) 1752 : HTemplateInstruction<N>(side_effects), type_(type) {} 1753 virtual ~HExpression() {} 1754 1755 Primitive::Type GetType() const OVERRIDE { return type_; } 1756 1757 protected: 1758 Primitive::Type type_; 1759}; 1760 1761// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow 1762// instruction that branches to the exit block. 1763class HReturnVoid : public HTemplateInstruction<0> { 1764 public: 1765 HReturnVoid() : HTemplateInstruction(SideEffects::None()) {} 1766 1767 bool IsControlFlow() const OVERRIDE { return true; } 1768 1769 DECLARE_INSTRUCTION(ReturnVoid); 1770 1771 private: 1772 DISALLOW_COPY_AND_ASSIGN(HReturnVoid); 1773}; 1774 1775// Represents dex's RETURN opcodes. A HReturn is a control flow 1776// instruction that branches to the exit block. 1777class HReturn : public HTemplateInstruction<1> { 1778 public: 1779 explicit HReturn(HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 1780 SetRawInputAt(0, value); 1781 } 1782 1783 bool IsControlFlow() const OVERRIDE { return true; } 1784 1785 DECLARE_INSTRUCTION(Return); 1786 1787 private: 1788 DISALLOW_COPY_AND_ASSIGN(HReturn); 1789}; 1790 1791// The exit instruction is the only instruction of the exit block. 1792// Instructions aborting the method (HThrow and HReturn) must branch to the 1793// exit block. 1794class HExit : public HTemplateInstruction<0> { 1795 public: 1796 HExit() : HTemplateInstruction(SideEffects::None()) {} 1797 1798 bool IsControlFlow() const OVERRIDE { return true; } 1799 1800 DECLARE_INSTRUCTION(Exit); 1801 1802 private: 1803 DISALLOW_COPY_AND_ASSIGN(HExit); 1804}; 1805 1806// Jumps from one block to another. 1807class HGoto : public HTemplateInstruction<0> { 1808 public: 1809 HGoto() : HTemplateInstruction(SideEffects::None()) {} 1810 1811 bool IsControlFlow() const OVERRIDE { return true; } 1812 1813 HBasicBlock* GetSuccessor() const { 1814 return GetBlock()->GetSuccessors().Get(0); 1815 } 1816 1817 DECLARE_INSTRUCTION(Goto); 1818 1819 private: 1820 DISALLOW_COPY_AND_ASSIGN(HGoto); 1821}; 1822 1823 1824// Conditional branch. A block ending with an HIf instruction must have 1825// two successors. 1826class HIf : public HTemplateInstruction<1> { 1827 public: 1828 explicit HIf(HInstruction* input) : HTemplateInstruction(SideEffects::None()) { 1829 SetRawInputAt(0, input); 1830 } 1831 1832 bool IsControlFlow() const OVERRIDE { return true; } 1833 1834 HBasicBlock* IfTrueSuccessor() const { 1835 return GetBlock()->GetSuccessors().Get(0); 1836 } 1837 1838 HBasicBlock* IfFalseSuccessor() const { 1839 return GetBlock()->GetSuccessors().Get(1); 1840 } 1841 1842 DECLARE_INSTRUCTION(If); 1843 1844 private: 1845 DISALLOW_COPY_AND_ASSIGN(HIf); 1846}; 1847 1848// Deoptimize to interpreter, upon checking a condition. 1849class HDeoptimize : public HTemplateInstruction<1> { 1850 public: 1851 HDeoptimize(HInstruction* cond, uint32_t dex_pc) 1852 : HTemplateInstruction(SideEffects::None()), 1853 dex_pc_(dex_pc) { 1854 SetRawInputAt(0, cond); 1855 } 1856 1857 bool NeedsEnvironment() const OVERRIDE { return true; } 1858 bool CanThrow() const OVERRIDE { return true; } 1859 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 1860 1861 DECLARE_INSTRUCTION(Deoptimize); 1862 1863 private: 1864 uint32_t dex_pc_; 1865 1866 DISALLOW_COPY_AND_ASSIGN(HDeoptimize); 1867}; 1868 1869// Represents the ArtMethod that was passed as a first argument to 1870// the method. It is used by instructions that depend on it, like 1871// instructions that work with the dex cache. 1872class HCurrentMethod : public HExpression<0> { 1873 public: 1874 HCurrentMethod() : HExpression(Primitive::kPrimNot, SideEffects::None()) {} 1875 1876 DECLARE_INSTRUCTION(CurrentMethod); 1877 1878 private: 1879 DISALLOW_COPY_AND_ASSIGN(HCurrentMethod); 1880}; 1881 1882class HUnaryOperation : public HExpression<1> { 1883 public: 1884 HUnaryOperation(Primitive::Type result_type, HInstruction* input) 1885 : HExpression(result_type, SideEffects::None()) { 1886 SetRawInputAt(0, input); 1887 } 1888 1889 HInstruction* GetInput() const { return InputAt(0); } 1890 Primitive::Type GetResultType() const { return GetType(); } 1891 1892 bool CanBeMoved() const OVERRIDE { return true; } 1893 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 1894 UNUSED(other); 1895 return true; 1896 } 1897 1898 // Try to statically evaluate `operation` and return a HConstant 1899 // containing the result of this evaluation. If `operation` cannot 1900 // be evaluated as a constant, return null. 1901 HConstant* TryStaticEvaluation() const; 1902 1903 // Apply this operation to `x`. 1904 virtual int32_t Evaluate(int32_t x) const = 0; 1905 virtual int64_t Evaluate(int64_t x) const = 0; 1906 1907 DECLARE_INSTRUCTION(UnaryOperation); 1908 1909 private: 1910 DISALLOW_COPY_AND_ASSIGN(HUnaryOperation); 1911}; 1912 1913class HBinaryOperation : public HExpression<2> { 1914 public: 1915 HBinaryOperation(Primitive::Type result_type, 1916 HInstruction* left, 1917 HInstruction* right) : HExpression(result_type, SideEffects::None()) { 1918 SetRawInputAt(0, left); 1919 SetRawInputAt(1, right); 1920 } 1921 1922 HInstruction* GetLeft() const { return InputAt(0); } 1923 HInstruction* GetRight() const { return InputAt(1); } 1924 Primitive::Type GetResultType() const { return GetType(); } 1925 1926 virtual bool IsCommutative() const { return false; } 1927 1928 // Put constant on the right. 1929 // Returns whether order is changed. 1930 bool OrderInputsWithConstantOnTheRight() { 1931 HInstruction* left = InputAt(0); 1932 HInstruction* right = InputAt(1); 1933 if (left->IsConstant() && !right->IsConstant()) { 1934 ReplaceInput(right, 0); 1935 ReplaceInput(left, 1); 1936 return true; 1937 } 1938 return false; 1939 } 1940 1941 // Order inputs by instruction id, but favor constant on the right side. 1942 // This helps GVN for commutative ops. 1943 void OrderInputs() { 1944 DCHECK(IsCommutative()); 1945 HInstruction* left = InputAt(0); 1946 HInstruction* right = InputAt(1); 1947 if (left == right || (!left->IsConstant() && right->IsConstant())) { 1948 return; 1949 } 1950 if (OrderInputsWithConstantOnTheRight()) { 1951 return; 1952 } 1953 // Order according to instruction id. 1954 if (left->GetId() > right->GetId()) { 1955 ReplaceInput(right, 0); 1956 ReplaceInput(left, 1); 1957 } 1958 } 1959 1960 bool CanBeMoved() const OVERRIDE { return true; } 1961 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 1962 UNUSED(other); 1963 return true; 1964 } 1965 1966 // Try to statically evaluate `operation` and return a HConstant 1967 // containing the result of this evaluation. If `operation` cannot 1968 // be evaluated as a constant, return null. 1969 HConstant* TryStaticEvaluation() const; 1970 1971 // Apply this operation to `x` and `y`. 1972 virtual int32_t Evaluate(int32_t x, int32_t y) const = 0; 1973 virtual int64_t Evaluate(int64_t x, int64_t y) const = 0; 1974 1975 // Returns an input that can legally be used as the right input and is 1976 // constant, or null. 1977 HConstant* GetConstantRight() const; 1978 1979 // If `GetConstantRight()` returns one of the input, this returns the other 1980 // one. Otherwise it returns null. 1981 HInstruction* GetLeastConstantLeft() const; 1982 1983 DECLARE_INSTRUCTION(BinaryOperation); 1984 1985 private: 1986 DISALLOW_COPY_AND_ASSIGN(HBinaryOperation); 1987}; 1988 1989class HCondition : public HBinaryOperation { 1990 public: 1991 HCondition(HInstruction* first, HInstruction* second) 1992 : HBinaryOperation(Primitive::kPrimBoolean, first, second), 1993 needs_materialization_(true) {} 1994 1995 bool NeedsMaterialization() const { return needs_materialization_; } 1996 void ClearNeedsMaterialization() { needs_materialization_ = false; } 1997 1998 // For code generation purposes, returns whether this instruction is just before 1999 // `instruction`, and disregard moves in between. 2000 bool IsBeforeWhenDisregardMoves(HInstruction* instruction) const; 2001 2002 DECLARE_INSTRUCTION(Condition); 2003 2004 virtual IfCondition GetCondition() const = 0; 2005 2006 private: 2007 // For register allocation purposes, returns whether this instruction needs to be 2008 // materialized (that is, not just be in the processor flags). 2009 bool needs_materialization_; 2010 2011 DISALLOW_COPY_AND_ASSIGN(HCondition); 2012}; 2013 2014// Instruction to check if two inputs are equal to each other. 2015class HEqual : public HCondition { 2016 public: 2017 HEqual(HInstruction* first, HInstruction* second) 2018 : HCondition(first, second) {} 2019 2020 bool IsCommutative() const OVERRIDE { return true; } 2021 2022 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2023 return x == y ? 1 : 0; 2024 } 2025 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2026 return x == y ? 1 : 0; 2027 } 2028 2029 DECLARE_INSTRUCTION(Equal); 2030 2031 IfCondition GetCondition() const OVERRIDE { 2032 return kCondEQ; 2033 } 2034 2035 private: 2036 DISALLOW_COPY_AND_ASSIGN(HEqual); 2037}; 2038 2039class HNotEqual : public HCondition { 2040 public: 2041 HNotEqual(HInstruction* first, HInstruction* second) 2042 : HCondition(first, second) {} 2043 2044 bool IsCommutative() const OVERRIDE { return true; } 2045 2046 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2047 return x != y ? 1 : 0; 2048 } 2049 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2050 return x != y ? 1 : 0; 2051 } 2052 2053 DECLARE_INSTRUCTION(NotEqual); 2054 2055 IfCondition GetCondition() const OVERRIDE { 2056 return kCondNE; 2057 } 2058 2059 private: 2060 DISALLOW_COPY_AND_ASSIGN(HNotEqual); 2061}; 2062 2063class HLessThan : public HCondition { 2064 public: 2065 HLessThan(HInstruction* first, HInstruction* second) 2066 : HCondition(first, second) {} 2067 2068 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2069 return x < y ? 1 : 0; 2070 } 2071 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2072 return x < y ? 1 : 0; 2073 } 2074 2075 DECLARE_INSTRUCTION(LessThan); 2076 2077 IfCondition GetCondition() const OVERRIDE { 2078 return kCondLT; 2079 } 2080 2081 private: 2082 DISALLOW_COPY_AND_ASSIGN(HLessThan); 2083}; 2084 2085class HLessThanOrEqual : public HCondition { 2086 public: 2087 HLessThanOrEqual(HInstruction* first, HInstruction* second) 2088 : HCondition(first, second) {} 2089 2090 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2091 return x <= y ? 1 : 0; 2092 } 2093 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2094 return x <= y ? 1 : 0; 2095 } 2096 2097 DECLARE_INSTRUCTION(LessThanOrEqual); 2098 2099 IfCondition GetCondition() const OVERRIDE { 2100 return kCondLE; 2101 } 2102 2103 private: 2104 DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual); 2105}; 2106 2107class HGreaterThan : public HCondition { 2108 public: 2109 HGreaterThan(HInstruction* first, HInstruction* second) 2110 : HCondition(first, second) {} 2111 2112 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2113 return x > y ? 1 : 0; 2114 } 2115 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2116 return x > y ? 1 : 0; 2117 } 2118 2119 DECLARE_INSTRUCTION(GreaterThan); 2120 2121 IfCondition GetCondition() const OVERRIDE { 2122 return kCondGT; 2123 } 2124 2125 private: 2126 DISALLOW_COPY_AND_ASSIGN(HGreaterThan); 2127}; 2128 2129class HGreaterThanOrEqual : public HCondition { 2130 public: 2131 HGreaterThanOrEqual(HInstruction* first, HInstruction* second) 2132 : HCondition(first, second) {} 2133 2134 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2135 return x >= y ? 1 : 0; 2136 } 2137 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2138 return x >= y ? 1 : 0; 2139 } 2140 2141 DECLARE_INSTRUCTION(GreaterThanOrEqual); 2142 2143 IfCondition GetCondition() const OVERRIDE { 2144 return kCondGE; 2145 } 2146 2147 private: 2148 DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual); 2149}; 2150 2151 2152// Instruction to check how two inputs compare to each other. 2153// Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1. 2154class HCompare : public HBinaryOperation { 2155 public: 2156 // The bias applies for floating point operations and indicates how NaN 2157 // comparisons are treated: 2158 enum Bias { 2159 kNoBias, // bias is not applicable (i.e. for long operation) 2160 kGtBias, // return 1 for NaN comparisons 2161 kLtBias, // return -1 for NaN comparisons 2162 }; 2163 2164 HCompare(Primitive::Type type, HInstruction* first, HInstruction* second, Bias bias) 2165 : HBinaryOperation(Primitive::kPrimInt, first, second), bias_(bias) { 2166 DCHECK_EQ(type, first->GetType()); 2167 DCHECK_EQ(type, second->GetType()); 2168 } 2169 2170 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2171 return 2172 x == y ? 0 : 2173 x > y ? 1 : 2174 -1; 2175 } 2176 2177 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2178 return 2179 x == y ? 0 : 2180 x > y ? 1 : 2181 -1; 2182 } 2183 2184 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2185 return bias_ == other->AsCompare()->bias_; 2186 } 2187 2188 bool IsGtBias() { return bias_ == kGtBias; } 2189 2190 DECLARE_INSTRUCTION(Compare); 2191 2192 private: 2193 const Bias bias_; 2194 2195 DISALLOW_COPY_AND_ASSIGN(HCompare); 2196}; 2197 2198// A local in the graph. Corresponds to a Dex register. 2199class HLocal : public HTemplateInstruction<0> { 2200 public: 2201 explicit HLocal(uint16_t reg_number) 2202 : HTemplateInstruction(SideEffects::None()), reg_number_(reg_number) {} 2203 2204 DECLARE_INSTRUCTION(Local); 2205 2206 uint16_t GetRegNumber() const { return reg_number_; } 2207 2208 private: 2209 // The Dex register number. 2210 const uint16_t reg_number_; 2211 2212 DISALLOW_COPY_AND_ASSIGN(HLocal); 2213}; 2214 2215// Load a given local. The local is an input of this instruction. 2216class HLoadLocal : public HExpression<1> { 2217 public: 2218 HLoadLocal(HLocal* local, Primitive::Type type) 2219 : HExpression(type, SideEffects::None()) { 2220 SetRawInputAt(0, local); 2221 } 2222 2223 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 2224 2225 DECLARE_INSTRUCTION(LoadLocal); 2226 2227 private: 2228 DISALLOW_COPY_AND_ASSIGN(HLoadLocal); 2229}; 2230 2231// Store a value in a given local. This instruction has two inputs: the value 2232// and the local. 2233class HStoreLocal : public HTemplateInstruction<2> { 2234 public: 2235 HStoreLocal(HLocal* local, HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 2236 SetRawInputAt(0, local); 2237 SetRawInputAt(1, value); 2238 } 2239 2240 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 2241 2242 DECLARE_INSTRUCTION(StoreLocal); 2243 2244 private: 2245 DISALLOW_COPY_AND_ASSIGN(HStoreLocal); 2246}; 2247 2248class HConstant : public HExpression<0> { 2249 public: 2250 explicit HConstant(Primitive::Type type) : HExpression(type, SideEffects::None()) {} 2251 2252 bool CanBeMoved() const OVERRIDE { return true; } 2253 2254 virtual bool IsMinusOne() const { return false; } 2255 virtual bool IsZero() const { return false; } 2256 virtual bool IsOne() const { return false; } 2257 2258 DECLARE_INSTRUCTION(Constant); 2259 2260 private: 2261 DISALLOW_COPY_AND_ASSIGN(HConstant); 2262}; 2263 2264class HFloatConstant : public HConstant { 2265 public: 2266 float GetValue() const { return value_; } 2267 2268 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2269 return bit_cast<uint32_t, float>(other->AsFloatConstant()->value_) == 2270 bit_cast<uint32_t, float>(value_); 2271 } 2272 2273 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2274 2275 bool IsMinusOne() const OVERRIDE { 2276 return bit_cast<uint32_t, float>(value_) == bit_cast<uint32_t, float>((-1.0f)); 2277 } 2278 bool IsZero() const OVERRIDE { 2279 return value_ == 0.0f; 2280 } 2281 bool IsOne() const OVERRIDE { 2282 return bit_cast<uint32_t, float>(value_) == bit_cast<uint32_t, float>(1.0f); 2283 } 2284 bool IsNaN() const { 2285 return std::isnan(value_); 2286 } 2287 2288 DECLARE_INSTRUCTION(FloatConstant); 2289 2290 private: 2291 explicit HFloatConstant(float value) : HConstant(Primitive::kPrimFloat), value_(value) {} 2292 explicit HFloatConstant(int32_t value) 2293 : HConstant(Primitive::kPrimFloat), value_(bit_cast<float, int32_t>(value)) {} 2294 2295 const float value_; 2296 2297 // Only the SsaBuilder and HGraph can create floating-point constants. 2298 friend class SsaBuilder; 2299 friend class HGraph; 2300 DISALLOW_COPY_AND_ASSIGN(HFloatConstant); 2301}; 2302 2303class HDoubleConstant : public HConstant { 2304 public: 2305 double GetValue() const { return value_; } 2306 2307 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2308 return bit_cast<uint64_t, double>(other->AsDoubleConstant()->value_) == 2309 bit_cast<uint64_t, double>(value_); 2310 } 2311 2312 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2313 2314 bool IsMinusOne() const OVERRIDE { 2315 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>((-1.0)); 2316 } 2317 bool IsZero() const OVERRIDE { 2318 return value_ == 0.0; 2319 } 2320 bool IsOne() const OVERRIDE { 2321 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>(1.0); 2322 } 2323 bool IsNaN() const { 2324 return std::isnan(value_); 2325 } 2326 2327 DECLARE_INSTRUCTION(DoubleConstant); 2328 2329 private: 2330 explicit HDoubleConstant(double value) : HConstant(Primitive::kPrimDouble), value_(value) {} 2331 explicit HDoubleConstant(int64_t value) 2332 : HConstant(Primitive::kPrimDouble), value_(bit_cast<double, int64_t>(value)) {} 2333 2334 const double value_; 2335 2336 // Only the SsaBuilder and HGraph can create floating-point constants. 2337 friend class SsaBuilder; 2338 friend class HGraph; 2339 DISALLOW_COPY_AND_ASSIGN(HDoubleConstant); 2340}; 2341 2342class HNullConstant : public HConstant { 2343 public: 2344 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2345 return true; 2346 } 2347 2348 size_t ComputeHashCode() const OVERRIDE { return 0; } 2349 2350 DECLARE_INSTRUCTION(NullConstant); 2351 2352 private: 2353 HNullConstant() : HConstant(Primitive::kPrimNot) {} 2354 2355 friend class HGraph; 2356 DISALLOW_COPY_AND_ASSIGN(HNullConstant); 2357}; 2358 2359// Constants of the type int. Those can be from Dex instructions, or 2360// synthesized (for example with the if-eqz instruction). 2361class HIntConstant : public HConstant { 2362 public: 2363 int32_t GetValue() const { return value_; } 2364 2365 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2366 return other->AsIntConstant()->value_ == value_; 2367 } 2368 2369 size_t ComputeHashCode() const OVERRIDE { return GetValue(); } 2370 2371 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2372 bool IsZero() const OVERRIDE { return GetValue() == 0; } 2373 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2374 2375 DECLARE_INSTRUCTION(IntConstant); 2376 2377 private: 2378 explicit HIntConstant(int32_t value) : HConstant(Primitive::kPrimInt), value_(value) {} 2379 2380 const int32_t value_; 2381 2382 friend class HGraph; 2383 ART_FRIEND_TEST(GraphTest, InsertInstructionBefore); 2384 ART_FRIEND_TYPED_TEST(ParallelMoveTest, ConstantLast); 2385 DISALLOW_COPY_AND_ASSIGN(HIntConstant); 2386}; 2387 2388class HLongConstant : public HConstant { 2389 public: 2390 int64_t GetValue() const { return value_; } 2391 2392 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2393 return other->AsLongConstant()->value_ == value_; 2394 } 2395 2396 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2397 2398 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2399 bool IsZero() const OVERRIDE { return GetValue() == 0; } 2400 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2401 2402 DECLARE_INSTRUCTION(LongConstant); 2403 2404 private: 2405 explicit HLongConstant(int64_t value) : HConstant(Primitive::kPrimLong), value_(value) {} 2406 2407 const int64_t value_; 2408 2409 friend class HGraph; 2410 DISALLOW_COPY_AND_ASSIGN(HLongConstant); 2411}; 2412 2413enum class Intrinsics { 2414#define OPTIMIZING_INTRINSICS(Name, IsStatic) k ## Name, 2415#include "intrinsics_list.h" 2416 kNone, 2417 INTRINSICS_LIST(OPTIMIZING_INTRINSICS) 2418#undef INTRINSICS_LIST 2419#undef OPTIMIZING_INTRINSICS 2420}; 2421std::ostream& operator<<(std::ostream& os, const Intrinsics& intrinsic); 2422 2423class HInvoke : public HInstruction { 2424 public: 2425 size_t InputCount() const OVERRIDE { return inputs_.Size(); } 2426 2427 // Runtime needs to walk the stack, so Dex -> Dex calls need to 2428 // know their environment. 2429 bool NeedsEnvironment() const OVERRIDE { return true; } 2430 2431 void SetArgumentAt(size_t index, HInstruction* argument) { 2432 SetRawInputAt(index, argument); 2433 } 2434 2435 // Return the number of arguments. This number can be lower than 2436 // the number of inputs returned by InputCount(), as some invoke 2437 // instructions (e.g. HInvokeStaticOrDirect) can have non-argument 2438 // inputs at the end of their list of inputs. 2439 uint32_t GetNumberOfArguments() const { return number_of_arguments_; } 2440 2441 Primitive::Type GetType() const OVERRIDE { return return_type_; } 2442 2443 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2444 2445 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 2446 const DexFile& GetDexFile() const { return GetEnvironment()->GetDexFile(); } 2447 2448 InvokeType GetOriginalInvokeType() const { return original_invoke_type_; } 2449 2450 Intrinsics GetIntrinsic() const { 2451 return intrinsic_; 2452 } 2453 2454 void SetIntrinsic(Intrinsics intrinsic) { 2455 intrinsic_ = intrinsic; 2456 } 2457 2458 bool IsInlined() const { 2459 return GetEnvironment()->GetParent() != nullptr; 2460 } 2461 2462 bool CanThrow() const OVERRIDE { return true; } 2463 2464 DECLARE_INSTRUCTION(Invoke); 2465 2466 protected: 2467 HInvoke(ArenaAllocator* arena, 2468 uint32_t number_of_arguments, 2469 uint32_t number_of_other_inputs, 2470 Primitive::Type return_type, 2471 uint32_t dex_pc, 2472 uint32_t dex_method_index, 2473 InvokeType original_invoke_type) 2474 : HInstruction(SideEffects::All()), 2475 number_of_arguments_(number_of_arguments), 2476 inputs_(arena, number_of_arguments), 2477 return_type_(return_type), 2478 dex_pc_(dex_pc), 2479 dex_method_index_(dex_method_index), 2480 original_invoke_type_(original_invoke_type), 2481 intrinsic_(Intrinsics::kNone) { 2482 uint32_t number_of_inputs = number_of_arguments + number_of_other_inputs; 2483 inputs_.SetSize(number_of_inputs); 2484 } 2485 2486 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); } 2487 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE { 2488 inputs_.Put(index, input); 2489 } 2490 2491 uint32_t number_of_arguments_; 2492 GrowableArray<HUserRecord<HInstruction*> > inputs_; 2493 const Primitive::Type return_type_; 2494 const uint32_t dex_pc_; 2495 const uint32_t dex_method_index_; 2496 const InvokeType original_invoke_type_; 2497 Intrinsics intrinsic_; 2498 2499 private: 2500 DISALLOW_COPY_AND_ASSIGN(HInvoke); 2501}; 2502 2503class HInvokeStaticOrDirect : public HInvoke { 2504 public: 2505 // Requirements of this method call regarding the class 2506 // initialization (clinit) check of its declaring class. 2507 enum class ClinitCheckRequirement { 2508 kNone, // Class already initialized. 2509 kExplicit, // Static call having explicit clinit check as last input. 2510 kImplicit, // Static call implicitly requiring a clinit check. 2511 }; 2512 2513 HInvokeStaticOrDirect(ArenaAllocator* arena, 2514 uint32_t number_of_arguments, 2515 Primitive::Type return_type, 2516 uint32_t dex_pc, 2517 uint32_t dex_method_index, 2518 bool is_recursive, 2519 int32_t string_init_offset, 2520 InvokeType original_invoke_type, 2521 InvokeType invoke_type, 2522 ClinitCheckRequirement clinit_check_requirement) 2523 : HInvoke(arena, 2524 number_of_arguments, 2525 clinit_check_requirement == ClinitCheckRequirement::kExplicit ? 1u : 0u, 2526 return_type, 2527 dex_pc, 2528 dex_method_index, 2529 original_invoke_type), 2530 invoke_type_(invoke_type), 2531 is_recursive_(is_recursive), 2532 clinit_check_requirement_(clinit_check_requirement), 2533 string_init_offset_(string_init_offset) {} 2534 2535 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2536 UNUSED(obj); 2537 // We access the method via the dex cache so we can't do an implicit null check. 2538 // TODO: for intrinsics we can generate implicit null checks. 2539 return false; 2540 } 2541 2542 InvokeType GetInvokeType() const { return invoke_type_; } 2543 bool IsRecursive() const { return is_recursive_; } 2544 bool NeedsDexCache() const OVERRIDE { return !IsRecursive(); } 2545 bool IsStringInit() const { return string_init_offset_ != 0; } 2546 int32_t GetStringInitOffset() const { return string_init_offset_; } 2547 2548 // Is this instruction a call to a static method? 2549 bool IsStatic() const { 2550 return GetInvokeType() == kStatic; 2551 } 2552 2553 // Remove the art::HLoadClass instruction set as last input by 2554 // art::PrepareForRegisterAllocation::VisitClinitCheck in lieu of 2555 // the initial art::HClinitCheck instruction (only relevant for 2556 // static calls with explicit clinit check). 2557 void RemoveLoadClassAsLastInput() { 2558 DCHECK(IsStaticWithExplicitClinitCheck()); 2559 size_t last_input_index = InputCount() - 1; 2560 HInstruction* last_input = InputAt(last_input_index); 2561 DCHECK(last_input != nullptr); 2562 DCHECK(last_input->IsLoadClass()) << last_input->DebugName(); 2563 RemoveAsUserOfInput(last_input_index); 2564 inputs_.DeleteAt(last_input_index); 2565 clinit_check_requirement_ = ClinitCheckRequirement::kImplicit; 2566 DCHECK(IsStaticWithImplicitClinitCheck()); 2567 } 2568 2569 // Is this a call to a static method whose declaring class has an 2570 // explicit intialization check in the graph? 2571 bool IsStaticWithExplicitClinitCheck() const { 2572 return IsStatic() && (clinit_check_requirement_ == ClinitCheckRequirement::kExplicit); 2573 } 2574 2575 // Is this a call to a static method whose declaring class has an 2576 // implicit intialization check requirement? 2577 bool IsStaticWithImplicitClinitCheck() const { 2578 return IsStatic() && (clinit_check_requirement_ == ClinitCheckRequirement::kImplicit); 2579 } 2580 2581 DECLARE_INSTRUCTION(InvokeStaticOrDirect); 2582 2583 protected: 2584 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { 2585 const HUserRecord<HInstruction*> input_record = HInvoke::InputRecordAt(i); 2586 if (kIsDebugBuild && IsStaticWithExplicitClinitCheck() && (i == InputCount() - 1)) { 2587 HInstruction* input = input_record.GetInstruction(); 2588 // `input` is the last input of a static invoke marked as having 2589 // an explicit clinit check. It must either be: 2590 // - an art::HClinitCheck instruction, set by art::HGraphBuilder; or 2591 // - an art::HLoadClass instruction, set by art::PrepareForRegisterAllocation. 2592 DCHECK(input != nullptr); 2593 DCHECK(input->IsClinitCheck() || input->IsLoadClass()) << input->DebugName(); 2594 } 2595 return input_record; 2596 } 2597 2598 private: 2599 const InvokeType invoke_type_; 2600 const bool is_recursive_; 2601 ClinitCheckRequirement clinit_check_requirement_; 2602 // Thread entrypoint offset for string init method if this is a string init invoke. 2603 // Note that there are multiple string init methods, each having its own offset. 2604 int32_t string_init_offset_; 2605 2606 DISALLOW_COPY_AND_ASSIGN(HInvokeStaticOrDirect); 2607}; 2608 2609class HInvokeVirtual : public HInvoke { 2610 public: 2611 HInvokeVirtual(ArenaAllocator* arena, 2612 uint32_t number_of_arguments, 2613 Primitive::Type return_type, 2614 uint32_t dex_pc, 2615 uint32_t dex_method_index, 2616 uint32_t vtable_index) 2617 : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index, kVirtual), 2618 vtable_index_(vtable_index) {} 2619 2620 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2621 // TODO: Add implicit null checks in intrinsics. 2622 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 2623 } 2624 2625 uint32_t GetVTableIndex() const { return vtable_index_; } 2626 2627 DECLARE_INSTRUCTION(InvokeVirtual); 2628 2629 private: 2630 const uint32_t vtable_index_; 2631 2632 DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual); 2633}; 2634 2635class HInvokeInterface : public HInvoke { 2636 public: 2637 HInvokeInterface(ArenaAllocator* arena, 2638 uint32_t number_of_arguments, 2639 Primitive::Type return_type, 2640 uint32_t dex_pc, 2641 uint32_t dex_method_index, 2642 uint32_t imt_index) 2643 : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index, kInterface), 2644 imt_index_(imt_index) {} 2645 2646 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2647 // TODO: Add implicit null checks in intrinsics. 2648 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 2649 } 2650 2651 uint32_t GetImtIndex() const { return imt_index_; } 2652 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 2653 2654 DECLARE_INSTRUCTION(InvokeInterface); 2655 2656 private: 2657 const uint32_t imt_index_; 2658 2659 DISALLOW_COPY_AND_ASSIGN(HInvokeInterface); 2660}; 2661 2662class HNewInstance : public HExpression<0> { 2663 public: 2664 HNewInstance(uint32_t dex_pc, 2665 uint16_t type_index, 2666 const DexFile& dex_file, 2667 QuickEntrypointEnum entrypoint) 2668 : HExpression(Primitive::kPrimNot, SideEffects::None()), 2669 dex_pc_(dex_pc), 2670 type_index_(type_index), 2671 dex_file_(dex_file), 2672 entrypoint_(entrypoint) {} 2673 2674 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2675 uint16_t GetTypeIndex() const { return type_index_; } 2676 const DexFile& GetDexFile() const { return dex_file_; } 2677 2678 // Calls runtime so needs an environment. 2679 bool NeedsEnvironment() const OVERRIDE { return true; } 2680 // It may throw when called on: 2681 // - interfaces 2682 // - abstract/innaccessible/unknown classes 2683 // TODO: optimize when possible. 2684 bool CanThrow() const OVERRIDE { return true; } 2685 2686 bool CanBeNull() const OVERRIDE { return false; } 2687 2688 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 2689 2690 DECLARE_INSTRUCTION(NewInstance); 2691 2692 private: 2693 const uint32_t dex_pc_; 2694 const uint16_t type_index_; 2695 const DexFile& dex_file_; 2696 const QuickEntrypointEnum entrypoint_; 2697 2698 DISALLOW_COPY_AND_ASSIGN(HNewInstance); 2699}; 2700 2701class HNeg : public HUnaryOperation { 2702 public: 2703 explicit HNeg(Primitive::Type result_type, HInstruction* input) 2704 : HUnaryOperation(result_type, input) {} 2705 2706 int32_t Evaluate(int32_t x) const OVERRIDE { return -x; } 2707 int64_t Evaluate(int64_t x) const OVERRIDE { return -x; } 2708 2709 DECLARE_INSTRUCTION(Neg); 2710 2711 private: 2712 DISALLOW_COPY_AND_ASSIGN(HNeg); 2713}; 2714 2715class HNewArray : public HExpression<1> { 2716 public: 2717 HNewArray(HInstruction* length, 2718 uint32_t dex_pc, 2719 uint16_t type_index, 2720 const DexFile& dex_file, 2721 QuickEntrypointEnum entrypoint) 2722 : HExpression(Primitive::kPrimNot, SideEffects::None()), 2723 dex_pc_(dex_pc), 2724 type_index_(type_index), 2725 dex_file_(dex_file), 2726 entrypoint_(entrypoint) { 2727 SetRawInputAt(0, length); 2728 } 2729 2730 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2731 uint16_t GetTypeIndex() const { return type_index_; } 2732 const DexFile& GetDexFile() const { return dex_file_; } 2733 2734 // Calls runtime so needs an environment. 2735 bool NeedsEnvironment() const OVERRIDE { return true; } 2736 2737 // May throw NegativeArraySizeException, OutOfMemoryError, etc. 2738 bool CanThrow() const OVERRIDE { return true; } 2739 2740 bool CanBeNull() const OVERRIDE { return false; } 2741 2742 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 2743 2744 DECLARE_INSTRUCTION(NewArray); 2745 2746 private: 2747 const uint32_t dex_pc_; 2748 const uint16_t type_index_; 2749 const DexFile& dex_file_; 2750 const QuickEntrypointEnum entrypoint_; 2751 2752 DISALLOW_COPY_AND_ASSIGN(HNewArray); 2753}; 2754 2755class HAdd : public HBinaryOperation { 2756 public: 2757 HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2758 : HBinaryOperation(result_type, left, right) {} 2759 2760 bool IsCommutative() const OVERRIDE { return true; } 2761 2762 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2763 return x + y; 2764 } 2765 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2766 return x + y; 2767 } 2768 2769 DECLARE_INSTRUCTION(Add); 2770 2771 private: 2772 DISALLOW_COPY_AND_ASSIGN(HAdd); 2773}; 2774 2775class HSub : public HBinaryOperation { 2776 public: 2777 HSub(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2778 : HBinaryOperation(result_type, left, right) {} 2779 2780 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2781 return x - y; 2782 } 2783 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2784 return x - y; 2785 } 2786 2787 DECLARE_INSTRUCTION(Sub); 2788 2789 private: 2790 DISALLOW_COPY_AND_ASSIGN(HSub); 2791}; 2792 2793class HMul : public HBinaryOperation { 2794 public: 2795 HMul(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2796 : HBinaryOperation(result_type, left, right) {} 2797 2798 bool IsCommutative() const OVERRIDE { return true; } 2799 2800 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x * y; } 2801 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x * y; } 2802 2803 DECLARE_INSTRUCTION(Mul); 2804 2805 private: 2806 DISALLOW_COPY_AND_ASSIGN(HMul); 2807}; 2808 2809class HDiv : public HBinaryOperation { 2810 public: 2811 HDiv(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc) 2812 : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {} 2813 2814 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2815 // Our graph structure ensures we never have 0 for `y` during constant folding. 2816 DCHECK_NE(y, 0); 2817 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2818 return (y == -1) ? -x : x / y; 2819 } 2820 2821 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2822 DCHECK_NE(y, 0); 2823 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2824 return (y == -1) ? -x : x / y; 2825 } 2826 2827 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2828 2829 DECLARE_INSTRUCTION(Div); 2830 2831 private: 2832 const uint32_t dex_pc_; 2833 2834 DISALLOW_COPY_AND_ASSIGN(HDiv); 2835}; 2836 2837class HRem : public HBinaryOperation { 2838 public: 2839 HRem(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc) 2840 : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {} 2841 2842 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2843 DCHECK_NE(y, 0); 2844 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2845 return (y == -1) ? 0 : x % y; 2846 } 2847 2848 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2849 DCHECK_NE(y, 0); 2850 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2851 return (y == -1) ? 0 : x % y; 2852 } 2853 2854 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2855 2856 DECLARE_INSTRUCTION(Rem); 2857 2858 private: 2859 const uint32_t dex_pc_; 2860 2861 DISALLOW_COPY_AND_ASSIGN(HRem); 2862}; 2863 2864class HDivZeroCheck : public HExpression<1> { 2865 public: 2866 HDivZeroCheck(HInstruction* value, uint32_t dex_pc) 2867 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 2868 SetRawInputAt(0, value); 2869 } 2870 2871 bool CanBeMoved() const OVERRIDE { return true; } 2872 2873 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2874 UNUSED(other); 2875 return true; 2876 } 2877 2878 bool NeedsEnvironment() const OVERRIDE { return true; } 2879 bool CanThrow() const OVERRIDE { return true; } 2880 2881 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2882 2883 DECLARE_INSTRUCTION(DivZeroCheck); 2884 2885 private: 2886 const uint32_t dex_pc_; 2887 2888 DISALLOW_COPY_AND_ASSIGN(HDivZeroCheck); 2889}; 2890 2891class HShl : public HBinaryOperation { 2892 public: 2893 HShl(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2894 : HBinaryOperation(result_type, left, right) {} 2895 2896 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x << (y & kMaxIntShiftValue); } 2897 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x << (y & kMaxLongShiftValue); } 2898 2899 DECLARE_INSTRUCTION(Shl); 2900 2901 private: 2902 DISALLOW_COPY_AND_ASSIGN(HShl); 2903}; 2904 2905class HShr : public HBinaryOperation { 2906 public: 2907 HShr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2908 : HBinaryOperation(result_type, left, right) {} 2909 2910 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x >> (y & kMaxIntShiftValue); } 2911 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x >> (y & kMaxLongShiftValue); } 2912 2913 DECLARE_INSTRUCTION(Shr); 2914 2915 private: 2916 DISALLOW_COPY_AND_ASSIGN(HShr); 2917}; 2918 2919class HUShr : public HBinaryOperation { 2920 public: 2921 HUShr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2922 : HBinaryOperation(result_type, left, right) {} 2923 2924 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2925 uint32_t ux = static_cast<uint32_t>(x); 2926 uint32_t uy = static_cast<uint32_t>(y) & kMaxIntShiftValue; 2927 return static_cast<int32_t>(ux >> uy); 2928 } 2929 2930 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2931 uint64_t ux = static_cast<uint64_t>(x); 2932 uint64_t uy = static_cast<uint64_t>(y) & kMaxLongShiftValue; 2933 return static_cast<int64_t>(ux >> uy); 2934 } 2935 2936 DECLARE_INSTRUCTION(UShr); 2937 2938 private: 2939 DISALLOW_COPY_AND_ASSIGN(HUShr); 2940}; 2941 2942class HAnd : public HBinaryOperation { 2943 public: 2944 HAnd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2945 : HBinaryOperation(result_type, left, right) {} 2946 2947 bool IsCommutative() const OVERRIDE { return true; } 2948 2949 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x & y; } 2950 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x & y; } 2951 2952 DECLARE_INSTRUCTION(And); 2953 2954 private: 2955 DISALLOW_COPY_AND_ASSIGN(HAnd); 2956}; 2957 2958class HOr : public HBinaryOperation { 2959 public: 2960 HOr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2961 : HBinaryOperation(result_type, left, right) {} 2962 2963 bool IsCommutative() const OVERRIDE { return true; } 2964 2965 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x | y; } 2966 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x | y; } 2967 2968 DECLARE_INSTRUCTION(Or); 2969 2970 private: 2971 DISALLOW_COPY_AND_ASSIGN(HOr); 2972}; 2973 2974class HXor : public HBinaryOperation { 2975 public: 2976 HXor(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2977 : HBinaryOperation(result_type, left, right) {} 2978 2979 bool IsCommutative() const OVERRIDE { return true; } 2980 2981 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x ^ y; } 2982 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x ^ y; } 2983 2984 DECLARE_INSTRUCTION(Xor); 2985 2986 private: 2987 DISALLOW_COPY_AND_ASSIGN(HXor); 2988}; 2989 2990// The value of a parameter in this method. Its location depends on 2991// the calling convention. 2992class HParameterValue : public HExpression<0> { 2993 public: 2994 HParameterValue(uint8_t index, Primitive::Type parameter_type, bool is_this = false) 2995 : HExpression(parameter_type, SideEffects::None()), index_(index), is_this_(is_this) {} 2996 2997 uint8_t GetIndex() const { return index_; } 2998 2999 bool CanBeNull() const OVERRIDE { return !is_this_; } 3000 3001 bool IsThis() const { return is_this_; } 3002 3003 DECLARE_INSTRUCTION(ParameterValue); 3004 3005 private: 3006 // The index of this parameter in the parameters list. Must be less 3007 // than HGraph::number_of_in_vregs_. 3008 const uint8_t index_; 3009 3010 // Whether or not the parameter value corresponds to 'this' argument. 3011 const bool is_this_; 3012 3013 DISALLOW_COPY_AND_ASSIGN(HParameterValue); 3014}; 3015 3016class HNot : public HUnaryOperation { 3017 public: 3018 explicit HNot(Primitive::Type result_type, HInstruction* input) 3019 : HUnaryOperation(result_type, input) {} 3020 3021 bool CanBeMoved() const OVERRIDE { return true; } 3022 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3023 UNUSED(other); 3024 return true; 3025 } 3026 3027 int32_t Evaluate(int32_t x) const OVERRIDE { return ~x; } 3028 int64_t Evaluate(int64_t x) const OVERRIDE { return ~x; } 3029 3030 DECLARE_INSTRUCTION(Not); 3031 3032 private: 3033 DISALLOW_COPY_AND_ASSIGN(HNot); 3034}; 3035 3036class HBooleanNot : public HUnaryOperation { 3037 public: 3038 explicit HBooleanNot(HInstruction* input) 3039 : HUnaryOperation(Primitive::Type::kPrimBoolean, input) {} 3040 3041 bool CanBeMoved() const OVERRIDE { return true; } 3042 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3043 UNUSED(other); 3044 return true; 3045 } 3046 3047 int32_t Evaluate(int32_t x) const OVERRIDE { 3048 DCHECK(IsUint<1>(x)); 3049 return !x; 3050 } 3051 3052 int64_t Evaluate(int64_t x ATTRIBUTE_UNUSED) const OVERRIDE { 3053 LOG(FATAL) << DebugName() << " cannot be used with 64-bit values"; 3054 UNREACHABLE(); 3055 } 3056 3057 DECLARE_INSTRUCTION(BooleanNot); 3058 3059 private: 3060 DISALLOW_COPY_AND_ASSIGN(HBooleanNot); 3061}; 3062 3063class HTypeConversion : public HExpression<1> { 3064 public: 3065 // Instantiate a type conversion of `input` to `result_type`. 3066 HTypeConversion(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc) 3067 : HExpression(result_type, SideEffects::None()), dex_pc_(dex_pc) { 3068 SetRawInputAt(0, input); 3069 DCHECK_NE(input->GetType(), result_type); 3070 } 3071 3072 HInstruction* GetInput() const { return InputAt(0); } 3073 Primitive::Type GetInputType() const { return GetInput()->GetType(); } 3074 Primitive::Type GetResultType() const { return GetType(); } 3075 3076 // Required by the x86 and ARM code generators when producing calls 3077 // to the runtime. 3078 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3079 3080 bool CanBeMoved() const OVERRIDE { return true; } 3081 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { return true; } 3082 3083 // Try to statically evaluate the conversion and return a HConstant 3084 // containing the result. If the input cannot be converted, return nullptr. 3085 HConstant* TryStaticEvaluation() const; 3086 3087 DECLARE_INSTRUCTION(TypeConversion); 3088 3089 private: 3090 const uint32_t dex_pc_; 3091 3092 DISALLOW_COPY_AND_ASSIGN(HTypeConversion); 3093}; 3094 3095static constexpr uint32_t kNoRegNumber = -1; 3096 3097class HPhi : public HInstruction { 3098 public: 3099 HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type) 3100 : HInstruction(SideEffects::None()), 3101 inputs_(arena, number_of_inputs), 3102 reg_number_(reg_number), 3103 type_(type), 3104 is_live_(false), 3105 can_be_null_(true) { 3106 inputs_.SetSize(number_of_inputs); 3107 } 3108 3109 // Returns a type equivalent to the given `type`, but that a `HPhi` can hold. 3110 static Primitive::Type ToPhiType(Primitive::Type type) { 3111 switch (type) { 3112 case Primitive::kPrimBoolean: 3113 case Primitive::kPrimByte: 3114 case Primitive::kPrimShort: 3115 case Primitive::kPrimChar: 3116 return Primitive::kPrimInt; 3117 default: 3118 return type; 3119 } 3120 } 3121 3122 size_t InputCount() const OVERRIDE { return inputs_.Size(); } 3123 3124 void AddInput(HInstruction* input); 3125 void RemoveInputAt(size_t index); 3126 3127 Primitive::Type GetType() const OVERRIDE { return type_; } 3128 void SetType(Primitive::Type type) { type_ = type; } 3129 3130 bool CanBeNull() const OVERRIDE { return can_be_null_; } 3131 void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; } 3132 3133 uint32_t GetRegNumber() const { return reg_number_; } 3134 3135 void SetDead() { is_live_ = false; } 3136 void SetLive() { is_live_ = true; } 3137 bool IsDead() const { return !is_live_; } 3138 bool IsLive() const { return is_live_; } 3139 3140 // Returns the next equivalent phi (starting from the current one) or null if there is none. 3141 // An equivalent phi is a phi having the same dex register and type. 3142 // It assumes that phis with the same dex register are adjacent. 3143 HPhi* GetNextEquivalentPhiWithSameType() { 3144 HInstruction* next = GetNext(); 3145 while (next != nullptr && next->AsPhi()->GetRegNumber() == reg_number_) { 3146 if (next->GetType() == GetType()) { 3147 return next->AsPhi(); 3148 } 3149 next = next->GetNext(); 3150 } 3151 return nullptr; 3152 } 3153 3154 DECLARE_INSTRUCTION(Phi); 3155 3156 protected: 3157 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); } 3158 3159 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE { 3160 inputs_.Put(index, input); 3161 } 3162 3163 private: 3164 GrowableArray<HUserRecord<HInstruction*> > inputs_; 3165 const uint32_t reg_number_; 3166 Primitive::Type type_; 3167 bool is_live_; 3168 bool can_be_null_; 3169 3170 DISALLOW_COPY_AND_ASSIGN(HPhi); 3171}; 3172 3173class HNullCheck : public HExpression<1> { 3174 public: 3175 HNullCheck(HInstruction* value, uint32_t dex_pc) 3176 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 3177 SetRawInputAt(0, value); 3178 } 3179 3180 bool CanBeMoved() const OVERRIDE { return true; } 3181 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3182 UNUSED(other); 3183 return true; 3184 } 3185 3186 bool NeedsEnvironment() const OVERRIDE { return true; } 3187 3188 bool CanThrow() const OVERRIDE { return true; } 3189 3190 bool CanBeNull() const OVERRIDE { return false; } 3191 3192 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3193 3194 DECLARE_INSTRUCTION(NullCheck); 3195 3196 private: 3197 const uint32_t dex_pc_; 3198 3199 DISALLOW_COPY_AND_ASSIGN(HNullCheck); 3200}; 3201 3202class FieldInfo : public ValueObject { 3203 public: 3204 FieldInfo(MemberOffset field_offset, Primitive::Type field_type, bool is_volatile) 3205 : field_offset_(field_offset), field_type_(field_type), is_volatile_(is_volatile) {} 3206 3207 MemberOffset GetFieldOffset() const { return field_offset_; } 3208 Primitive::Type GetFieldType() const { return field_type_; } 3209 bool IsVolatile() const { return is_volatile_; } 3210 3211 private: 3212 const MemberOffset field_offset_; 3213 const Primitive::Type field_type_; 3214 const bool is_volatile_; 3215}; 3216 3217class HInstanceFieldGet : public HExpression<1> { 3218 public: 3219 HInstanceFieldGet(HInstruction* value, 3220 Primitive::Type field_type, 3221 MemberOffset field_offset, 3222 bool is_volatile) 3223 : HExpression(field_type, SideEffects::DependsOnSomething()), 3224 field_info_(field_offset, field_type, is_volatile) { 3225 SetRawInputAt(0, value); 3226 } 3227 3228 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 3229 3230 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3231 HInstanceFieldGet* other_get = other->AsInstanceFieldGet(); 3232 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 3233 } 3234 3235 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3236 return (obj == InputAt(0)) && GetFieldOffset().Uint32Value() < kPageSize; 3237 } 3238 3239 size_t ComputeHashCode() const OVERRIDE { 3240 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 3241 } 3242 3243 const FieldInfo& GetFieldInfo() const { return field_info_; } 3244 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3245 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3246 bool IsVolatile() const { return field_info_.IsVolatile(); } 3247 3248 DECLARE_INSTRUCTION(InstanceFieldGet); 3249 3250 private: 3251 const FieldInfo field_info_; 3252 3253 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet); 3254}; 3255 3256class HInstanceFieldSet : public HTemplateInstruction<2> { 3257 public: 3258 HInstanceFieldSet(HInstruction* object, 3259 HInstruction* value, 3260 Primitive::Type field_type, 3261 MemberOffset field_offset, 3262 bool is_volatile) 3263 : HTemplateInstruction(SideEffects::ChangesSomething()), 3264 field_info_(field_offset, field_type, is_volatile), 3265 value_can_be_null_(true) { 3266 SetRawInputAt(0, object); 3267 SetRawInputAt(1, value); 3268 } 3269 3270 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3271 return (obj == InputAt(0)) && GetFieldOffset().Uint32Value() < kPageSize; 3272 } 3273 3274 const FieldInfo& GetFieldInfo() const { return field_info_; } 3275 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3276 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3277 bool IsVolatile() const { return field_info_.IsVolatile(); } 3278 HInstruction* GetValue() const { return InputAt(1); } 3279 bool GetValueCanBeNull() const { return value_can_be_null_; } 3280 void ClearValueCanBeNull() { value_can_be_null_ = false; } 3281 3282 DECLARE_INSTRUCTION(InstanceFieldSet); 3283 3284 private: 3285 const FieldInfo field_info_; 3286 bool value_can_be_null_; 3287 3288 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet); 3289}; 3290 3291class HArrayGet : public HExpression<2> { 3292 public: 3293 HArrayGet(HInstruction* array, HInstruction* index, Primitive::Type type) 3294 : HExpression(type, SideEffects::DependsOnSomething()) { 3295 SetRawInputAt(0, array); 3296 SetRawInputAt(1, index); 3297 } 3298 3299 bool CanBeMoved() const OVERRIDE { return true; } 3300 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3301 UNUSED(other); 3302 return true; 3303 } 3304 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3305 UNUSED(obj); 3306 // TODO: We can be smarter here. 3307 // Currently, the array access is always preceded by an ArrayLength or a NullCheck 3308 // which generates the implicit null check. There are cases when these can be removed 3309 // to produce better code. If we ever add optimizations to do so we should allow an 3310 // implicit check here (as long as the address falls in the first page). 3311 return false; 3312 } 3313 3314 void SetType(Primitive::Type type) { type_ = type; } 3315 3316 HInstruction* GetArray() const { return InputAt(0); } 3317 HInstruction* GetIndex() const { return InputAt(1); } 3318 3319 DECLARE_INSTRUCTION(ArrayGet); 3320 3321 private: 3322 DISALLOW_COPY_AND_ASSIGN(HArrayGet); 3323}; 3324 3325class HArraySet : public HTemplateInstruction<3> { 3326 public: 3327 HArraySet(HInstruction* array, 3328 HInstruction* index, 3329 HInstruction* value, 3330 Primitive::Type expected_component_type, 3331 uint32_t dex_pc) 3332 : HTemplateInstruction(SideEffects::ChangesSomething()), 3333 dex_pc_(dex_pc), 3334 expected_component_type_(expected_component_type), 3335 needs_type_check_(value->GetType() == Primitive::kPrimNot), 3336 value_can_be_null_(true) { 3337 SetRawInputAt(0, array); 3338 SetRawInputAt(1, index); 3339 SetRawInputAt(2, value); 3340 } 3341 3342 bool NeedsEnvironment() const OVERRIDE { 3343 // We currently always call a runtime method to catch array store 3344 // exceptions. 3345 return needs_type_check_; 3346 } 3347 3348 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3349 UNUSED(obj); 3350 // TODO: Same as for ArrayGet. 3351 return false; 3352 } 3353 3354 void ClearNeedsTypeCheck() { 3355 needs_type_check_ = false; 3356 } 3357 3358 void ClearValueCanBeNull() { 3359 value_can_be_null_ = false; 3360 } 3361 3362 bool GetValueCanBeNull() const { return value_can_be_null_; } 3363 bool NeedsTypeCheck() const { return needs_type_check_; } 3364 3365 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3366 3367 HInstruction* GetArray() const { return InputAt(0); } 3368 HInstruction* GetIndex() const { return InputAt(1); } 3369 HInstruction* GetValue() const { return InputAt(2); } 3370 3371 Primitive::Type GetComponentType() const { 3372 // The Dex format does not type floating point index operations. Since the 3373 // `expected_component_type_` is set during building and can therefore not 3374 // be correct, we also check what is the value type. If it is a floating 3375 // point type, we must use that type. 3376 Primitive::Type value_type = GetValue()->GetType(); 3377 return ((value_type == Primitive::kPrimFloat) || (value_type == Primitive::kPrimDouble)) 3378 ? value_type 3379 : expected_component_type_; 3380 } 3381 3382 DECLARE_INSTRUCTION(ArraySet); 3383 3384 private: 3385 const uint32_t dex_pc_; 3386 const Primitive::Type expected_component_type_; 3387 bool needs_type_check_; 3388 bool value_can_be_null_; 3389 3390 DISALLOW_COPY_AND_ASSIGN(HArraySet); 3391}; 3392 3393class HArrayLength : public HExpression<1> { 3394 public: 3395 explicit HArrayLength(HInstruction* array) 3396 : HExpression(Primitive::kPrimInt, SideEffects::None()) { 3397 // Note that arrays do not change length, so the instruction does not 3398 // depend on any write. 3399 SetRawInputAt(0, array); 3400 } 3401 3402 bool CanBeMoved() const OVERRIDE { return true; } 3403 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3404 UNUSED(other); 3405 return true; 3406 } 3407 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3408 return obj == InputAt(0); 3409 } 3410 3411 DECLARE_INSTRUCTION(ArrayLength); 3412 3413 private: 3414 DISALLOW_COPY_AND_ASSIGN(HArrayLength); 3415}; 3416 3417class HBoundsCheck : public HExpression<2> { 3418 public: 3419 HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc) 3420 : HExpression(index->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 3421 DCHECK(index->GetType() == Primitive::kPrimInt); 3422 SetRawInputAt(0, index); 3423 SetRawInputAt(1, length); 3424 } 3425 3426 bool CanBeMoved() const OVERRIDE { return true; } 3427 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3428 UNUSED(other); 3429 return true; 3430 } 3431 3432 bool NeedsEnvironment() const OVERRIDE { return true; } 3433 3434 bool CanThrow() const OVERRIDE { return true; } 3435 3436 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3437 3438 DECLARE_INSTRUCTION(BoundsCheck); 3439 3440 private: 3441 const uint32_t dex_pc_; 3442 3443 DISALLOW_COPY_AND_ASSIGN(HBoundsCheck); 3444}; 3445 3446/** 3447 * Some DEX instructions are folded into multiple HInstructions that need 3448 * to stay live until the last HInstruction. This class 3449 * is used as a marker for the baseline compiler to ensure its preceding 3450 * HInstruction stays live. `index` represents the stack location index of the 3451 * instruction (the actual offset is computed as index * vreg_size). 3452 */ 3453class HTemporary : public HTemplateInstruction<0> { 3454 public: 3455 explicit HTemporary(size_t index) : HTemplateInstruction(SideEffects::None()), index_(index) {} 3456 3457 size_t GetIndex() const { return index_; } 3458 3459 Primitive::Type GetType() const OVERRIDE { 3460 // The previous instruction is the one that will be stored in the temporary location. 3461 DCHECK(GetPrevious() != nullptr); 3462 return GetPrevious()->GetType(); 3463 } 3464 3465 DECLARE_INSTRUCTION(Temporary); 3466 3467 private: 3468 const size_t index_; 3469 3470 DISALLOW_COPY_AND_ASSIGN(HTemporary); 3471}; 3472 3473class HSuspendCheck : public HTemplateInstruction<0> { 3474 public: 3475 explicit HSuspendCheck(uint32_t dex_pc) 3476 : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc), slow_path_(nullptr) {} 3477 3478 bool NeedsEnvironment() const OVERRIDE { 3479 return true; 3480 } 3481 3482 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3483 void SetSlowPath(SlowPathCode* slow_path) { slow_path_ = slow_path; } 3484 SlowPathCode* GetSlowPath() const { return slow_path_; } 3485 3486 DECLARE_INSTRUCTION(SuspendCheck); 3487 3488 private: 3489 const uint32_t dex_pc_; 3490 3491 // Only used for code generation, in order to share the same slow path between back edges 3492 // of a same loop. 3493 SlowPathCode* slow_path_; 3494 3495 DISALLOW_COPY_AND_ASSIGN(HSuspendCheck); 3496}; 3497 3498/** 3499 * Instruction to load a Class object. 3500 */ 3501class HLoadClass : public HExpression<1> { 3502 public: 3503 HLoadClass(HCurrentMethod* current_method, 3504 uint16_t type_index, 3505 const DexFile& dex_file, 3506 bool is_referrers_class, 3507 uint32_t dex_pc) 3508 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3509 type_index_(type_index), 3510 dex_file_(dex_file), 3511 is_referrers_class_(is_referrers_class), 3512 dex_pc_(dex_pc), 3513 generate_clinit_check_(false), 3514 loaded_class_rti_(ReferenceTypeInfo::CreateTop(/* is_exact */ false)) { 3515 SetRawInputAt(0, current_method); 3516 } 3517 3518 bool CanBeMoved() const OVERRIDE { return true; } 3519 3520 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3521 return other->AsLoadClass()->type_index_ == type_index_; 3522 } 3523 3524 size_t ComputeHashCode() const OVERRIDE { return type_index_; } 3525 3526 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3527 uint16_t GetTypeIndex() const { return type_index_; } 3528 bool IsReferrersClass() const { return is_referrers_class_; } 3529 3530 bool NeedsEnvironment() const OVERRIDE { 3531 // Will call runtime and load the class if the class is not loaded yet. 3532 // TODO: finer grain decision. 3533 return !is_referrers_class_; 3534 } 3535 3536 bool MustGenerateClinitCheck() const { 3537 return generate_clinit_check_; 3538 } 3539 3540 void SetMustGenerateClinitCheck(bool generate_clinit_check) { 3541 generate_clinit_check_ = generate_clinit_check; 3542 } 3543 3544 bool CanCallRuntime() const { 3545 return MustGenerateClinitCheck() || !is_referrers_class_; 3546 } 3547 3548 bool CanThrow() const OVERRIDE { 3549 // May call runtime and and therefore can throw. 3550 // TODO: finer grain decision. 3551 return !is_referrers_class_; 3552 } 3553 3554 ReferenceTypeInfo GetLoadedClassRTI() { 3555 return loaded_class_rti_; 3556 } 3557 3558 void SetLoadedClassRTI(ReferenceTypeInfo rti) { 3559 // Make sure we only set exact types (the loaded class should never be merged). 3560 DCHECK(rti.IsExact()); 3561 loaded_class_rti_ = rti; 3562 } 3563 3564 bool IsResolved() { 3565 return loaded_class_rti_.IsExact(); 3566 } 3567 3568 const DexFile& GetDexFile() { return dex_file_; } 3569 3570 bool NeedsDexCache() const OVERRIDE { return !is_referrers_class_; } 3571 3572 DECLARE_INSTRUCTION(LoadClass); 3573 3574 private: 3575 const uint16_t type_index_; 3576 const DexFile& dex_file_; 3577 const bool is_referrers_class_; 3578 const uint32_t dex_pc_; 3579 // Whether this instruction must generate the initialization check. 3580 // Used for code generation. 3581 bool generate_clinit_check_; 3582 3583 ReferenceTypeInfo loaded_class_rti_; 3584 3585 DISALLOW_COPY_AND_ASSIGN(HLoadClass); 3586}; 3587 3588class HLoadString : public HExpression<1> { 3589 public: 3590 HLoadString(HCurrentMethod* current_method, uint32_t string_index, uint32_t dex_pc) 3591 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3592 string_index_(string_index), 3593 dex_pc_(dex_pc) { 3594 SetRawInputAt(0, current_method); 3595 } 3596 3597 bool CanBeMoved() const OVERRIDE { return true; } 3598 3599 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3600 return other->AsLoadString()->string_index_ == string_index_; 3601 } 3602 3603 size_t ComputeHashCode() const OVERRIDE { return string_index_; } 3604 3605 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3606 uint32_t GetStringIndex() const { return string_index_; } 3607 3608 // TODO: Can we deopt or debug when we resolve a string? 3609 bool NeedsEnvironment() const OVERRIDE { return false; } 3610 bool NeedsDexCache() const OVERRIDE { return true; } 3611 3612 DECLARE_INSTRUCTION(LoadString); 3613 3614 private: 3615 const uint32_t string_index_; 3616 const uint32_t dex_pc_; 3617 3618 DISALLOW_COPY_AND_ASSIGN(HLoadString); 3619}; 3620 3621/** 3622 * Performs an initialization check on its Class object input. 3623 */ 3624class HClinitCheck : public HExpression<1> { 3625 public: 3626 explicit HClinitCheck(HLoadClass* constant, uint32_t dex_pc) 3627 : HExpression(Primitive::kPrimNot, SideEffects::ChangesSomething()), 3628 dex_pc_(dex_pc) { 3629 SetRawInputAt(0, constant); 3630 } 3631 3632 bool CanBeMoved() const OVERRIDE { return true; } 3633 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3634 UNUSED(other); 3635 return true; 3636 } 3637 3638 bool NeedsEnvironment() const OVERRIDE { 3639 // May call runtime to initialize the class. 3640 return true; 3641 } 3642 3643 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3644 3645 HLoadClass* GetLoadClass() const { return InputAt(0)->AsLoadClass(); } 3646 3647 DECLARE_INSTRUCTION(ClinitCheck); 3648 3649 private: 3650 const uint32_t dex_pc_; 3651 3652 DISALLOW_COPY_AND_ASSIGN(HClinitCheck); 3653}; 3654 3655class HStaticFieldGet : public HExpression<1> { 3656 public: 3657 HStaticFieldGet(HInstruction* cls, 3658 Primitive::Type field_type, 3659 MemberOffset field_offset, 3660 bool is_volatile) 3661 : HExpression(field_type, SideEffects::DependsOnSomething()), 3662 field_info_(field_offset, field_type, is_volatile) { 3663 SetRawInputAt(0, cls); 3664 } 3665 3666 3667 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 3668 3669 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3670 HStaticFieldGet* other_get = other->AsStaticFieldGet(); 3671 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 3672 } 3673 3674 size_t ComputeHashCode() const OVERRIDE { 3675 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 3676 } 3677 3678 const FieldInfo& GetFieldInfo() const { return field_info_; } 3679 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3680 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3681 bool IsVolatile() const { return field_info_.IsVolatile(); } 3682 3683 DECLARE_INSTRUCTION(StaticFieldGet); 3684 3685 private: 3686 const FieldInfo field_info_; 3687 3688 DISALLOW_COPY_AND_ASSIGN(HStaticFieldGet); 3689}; 3690 3691class HStaticFieldSet : public HTemplateInstruction<2> { 3692 public: 3693 HStaticFieldSet(HInstruction* cls, 3694 HInstruction* value, 3695 Primitive::Type field_type, 3696 MemberOffset field_offset, 3697 bool is_volatile) 3698 : HTemplateInstruction(SideEffects::ChangesSomething()), 3699 field_info_(field_offset, field_type, is_volatile), 3700 value_can_be_null_(true) { 3701 SetRawInputAt(0, cls); 3702 SetRawInputAt(1, value); 3703 } 3704 3705 const FieldInfo& GetFieldInfo() const { return field_info_; } 3706 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3707 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3708 bool IsVolatile() const { return field_info_.IsVolatile(); } 3709 3710 HInstruction* GetValue() const { return InputAt(1); } 3711 bool GetValueCanBeNull() const { return value_can_be_null_; } 3712 void ClearValueCanBeNull() { value_can_be_null_ = false; } 3713 3714 DECLARE_INSTRUCTION(StaticFieldSet); 3715 3716 private: 3717 const FieldInfo field_info_; 3718 bool value_can_be_null_; 3719 3720 DISALLOW_COPY_AND_ASSIGN(HStaticFieldSet); 3721}; 3722 3723// Implement the move-exception DEX instruction. 3724class HLoadException : public HExpression<0> { 3725 public: 3726 HLoadException() : HExpression(Primitive::kPrimNot, SideEffects::None()) {} 3727 3728 DECLARE_INSTRUCTION(LoadException); 3729 3730 private: 3731 DISALLOW_COPY_AND_ASSIGN(HLoadException); 3732}; 3733 3734class HThrow : public HTemplateInstruction<1> { 3735 public: 3736 HThrow(HInstruction* exception, uint32_t dex_pc) 3737 : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc) { 3738 SetRawInputAt(0, exception); 3739 } 3740 3741 bool IsControlFlow() const OVERRIDE { return true; } 3742 3743 bool NeedsEnvironment() const OVERRIDE { return true; } 3744 3745 bool CanThrow() const OVERRIDE { return true; } 3746 3747 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3748 3749 DECLARE_INSTRUCTION(Throw); 3750 3751 private: 3752 const uint32_t dex_pc_; 3753 3754 DISALLOW_COPY_AND_ASSIGN(HThrow); 3755}; 3756 3757class HInstanceOf : public HExpression<2> { 3758 public: 3759 HInstanceOf(HInstruction* object, 3760 HLoadClass* constant, 3761 bool class_is_final, 3762 uint32_t dex_pc) 3763 : HExpression(Primitive::kPrimBoolean, SideEffects::None()), 3764 class_is_final_(class_is_final), 3765 must_do_null_check_(true), 3766 dex_pc_(dex_pc) { 3767 SetRawInputAt(0, object); 3768 SetRawInputAt(1, constant); 3769 } 3770 3771 bool CanBeMoved() const OVERRIDE { return true; } 3772 3773 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 3774 return true; 3775 } 3776 3777 bool NeedsEnvironment() const OVERRIDE { 3778 return false; 3779 } 3780 3781 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3782 3783 bool IsClassFinal() const { return class_is_final_; } 3784 3785 // Used only in code generation. 3786 bool MustDoNullCheck() const { return must_do_null_check_; } 3787 void ClearMustDoNullCheck() { must_do_null_check_ = false; } 3788 3789 DECLARE_INSTRUCTION(InstanceOf); 3790 3791 private: 3792 const bool class_is_final_; 3793 bool must_do_null_check_; 3794 const uint32_t dex_pc_; 3795 3796 DISALLOW_COPY_AND_ASSIGN(HInstanceOf); 3797}; 3798 3799class HBoundType : public HExpression<1> { 3800 public: 3801 HBoundType(HInstruction* input, ReferenceTypeInfo bound_type) 3802 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3803 bound_type_(bound_type) { 3804 DCHECK_EQ(input->GetType(), Primitive::kPrimNot); 3805 SetRawInputAt(0, input); 3806 } 3807 3808 const ReferenceTypeInfo& GetBoundType() const { return bound_type_; } 3809 3810 bool CanBeNull() const OVERRIDE { 3811 // `null instanceof ClassX` always return false so we can't be null. 3812 return false; 3813 } 3814 3815 DECLARE_INSTRUCTION(BoundType); 3816 3817 private: 3818 // Encodes the most upper class that this instruction can have. In other words 3819 // it is always the case that GetBoundType().IsSupertypeOf(GetReferenceType()). 3820 // It is used to bound the type in cases like `if (x instanceof ClassX) {}` 3821 const ReferenceTypeInfo bound_type_; 3822 3823 DISALLOW_COPY_AND_ASSIGN(HBoundType); 3824}; 3825 3826class HCheckCast : public HTemplateInstruction<2> { 3827 public: 3828 HCheckCast(HInstruction* object, 3829 HLoadClass* constant, 3830 bool class_is_final, 3831 uint32_t dex_pc) 3832 : HTemplateInstruction(SideEffects::None()), 3833 class_is_final_(class_is_final), 3834 must_do_null_check_(true), 3835 dex_pc_(dex_pc) { 3836 SetRawInputAt(0, object); 3837 SetRawInputAt(1, constant); 3838 } 3839 3840 bool CanBeMoved() const OVERRIDE { return true; } 3841 3842 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 3843 return true; 3844 } 3845 3846 bool NeedsEnvironment() const OVERRIDE { 3847 // Instruction may throw a CheckCastError. 3848 return true; 3849 } 3850 3851 bool CanThrow() const OVERRIDE { return true; } 3852 3853 bool MustDoNullCheck() const { return must_do_null_check_; } 3854 void ClearMustDoNullCheck() { must_do_null_check_ = false; } 3855 3856 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3857 3858 bool IsClassFinal() const { return class_is_final_; } 3859 3860 DECLARE_INSTRUCTION(CheckCast); 3861 3862 private: 3863 const bool class_is_final_; 3864 bool must_do_null_check_; 3865 const uint32_t dex_pc_; 3866 3867 DISALLOW_COPY_AND_ASSIGN(HCheckCast); 3868}; 3869 3870class HMemoryBarrier : public HTemplateInstruction<0> { 3871 public: 3872 explicit HMemoryBarrier(MemBarrierKind barrier_kind) 3873 : HTemplateInstruction(SideEffects::None()), 3874 barrier_kind_(barrier_kind) {} 3875 3876 MemBarrierKind GetBarrierKind() { return barrier_kind_; } 3877 3878 DECLARE_INSTRUCTION(MemoryBarrier); 3879 3880 private: 3881 const MemBarrierKind barrier_kind_; 3882 3883 DISALLOW_COPY_AND_ASSIGN(HMemoryBarrier); 3884}; 3885 3886class HMonitorOperation : public HTemplateInstruction<1> { 3887 public: 3888 enum OperationKind { 3889 kEnter, 3890 kExit, 3891 }; 3892 3893 HMonitorOperation(HInstruction* object, OperationKind kind, uint32_t dex_pc) 3894 : HTemplateInstruction(SideEffects::None()), kind_(kind), dex_pc_(dex_pc) { 3895 SetRawInputAt(0, object); 3896 } 3897 3898 // Instruction may throw a Java exception, so we need an environment. 3899 bool NeedsEnvironment() const OVERRIDE { return true; } 3900 bool CanThrow() const OVERRIDE { return true; } 3901 3902 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3903 3904 bool IsEnter() const { return kind_ == kEnter; } 3905 3906 DECLARE_INSTRUCTION(MonitorOperation); 3907 3908 private: 3909 const OperationKind kind_; 3910 const uint32_t dex_pc_; 3911 3912 private: 3913 DISALLOW_COPY_AND_ASSIGN(HMonitorOperation); 3914}; 3915 3916class MoveOperands : public ArenaObject<kArenaAllocMisc> { 3917 public: 3918 MoveOperands(Location source, 3919 Location destination, 3920 Primitive::Type type, 3921 HInstruction* instruction) 3922 : source_(source), destination_(destination), type_(type), instruction_(instruction) {} 3923 3924 Location GetSource() const { return source_; } 3925 Location GetDestination() const { return destination_; } 3926 3927 void SetSource(Location value) { source_ = value; } 3928 void SetDestination(Location value) { destination_ = value; } 3929 3930 // The parallel move resolver marks moves as "in-progress" by clearing the 3931 // destination (but not the source). 3932 Location MarkPending() { 3933 DCHECK(!IsPending()); 3934 Location dest = destination_; 3935 destination_ = Location::NoLocation(); 3936 return dest; 3937 } 3938 3939 void ClearPending(Location dest) { 3940 DCHECK(IsPending()); 3941 destination_ = dest; 3942 } 3943 3944 bool IsPending() const { 3945 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 3946 return destination_.IsInvalid() && !source_.IsInvalid(); 3947 } 3948 3949 // True if this blocks a move from the given location. 3950 bool Blocks(Location loc) const { 3951 return !IsEliminated() && source_.OverlapsWith(loc); 3952 } 3953 3954 // A move is redundant if it's been eliminated, if its source and 3955 // destination are the same, or if its destination is unneeded. 3956 bool IsRedundant() const { 3957 return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_); 3958 } 3959 3960 // We clear both operands to indicate move that's been eliminated. 3961 void Eliminate() { 3962 source_ = destination_ = Location::NoLocation(); 3963 } 3964 3965 bool IsEliminated() const { 3966 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 3967 return source_.IsInvalid(); 3968 } 3969 3970 bool Is64BitMove() const { 3971 return Primitive::Is64BitType(type_); 3972 } 3973 3974 HInstruction* GetInstruction() const { return instruction_; } 3975 3976 private: 3977 Location source_; 3978 Location destination_; 3979 // The type this move is for. 3980 Primitive::Type type_; 3981 // The instruction this move is assocatied with. Null when this move is 3982 // for moving an input in the expected locations of user (including a phi user). 3983 // This is only used in debug mode, to ensure we do not connect interval siblings 3984 // in the same parallel move. 3985 HInstruction* instruction_; 3986}; 3987 3988static constexpr size_t kDefaultNumberOfMoves = 4; 3989 3990class HParallelMove : public HTemplateInstruction<0> { 3991 public: 3992 explicit HParallelMove(ArenaAllocator* arena) 3993 : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {} 3994 3995 void AddMove(Location source, 3996 Location destination, 3997 Primitive::Type type, 3998 HInstruction* instruction) { 3999 DCHECK(source.IsValid()); 4000 DCHECK(destination.IsValid()); 4001 if (kIsDebugBuild) { 4002 if (instruction != nullptr) { 4003 for (size_t i = 0, e = moves_.Size(); i < e; ++i) { 4004 if (moves_.Get(i).GetInstruction() == instruction) { 4005 // Special case the situation where the move is for the spill slot 4006 // of the instruction. 4007 if ((GetPrevious() == instruction) 4008 || ((GetPrevious() == nullptr) 4009 && instruction->IsPhi() 4010 && instruction->GetBlock() == GetBlock())) { 4011 DCHECK_NE(destination.GetKind(), moves_.Get(i).GetDestination().GetKind()) 4012 << "Doing parallel moves for the same instruction."; 4013 } else { 4014 DCHECK(false) << "Doing parallel moves for the same instruction."; 4015 } 4016 } 4017 } 4018 } 4019 for (size_t i = 0, e = moves_.Size(); i < e; ++i) { 4020 DCHECK(!destination.OverlapsWith(moves_.Get(i).GetDestination())) 4021 << "Overlapped destination for two moves in a parallel move: " 4022 << moves_.Get(i).GetSource() << " ==> " << moves_.Get(i).GetDestination() << " and " 4023 << source << " ==> " << destination; 4024 } 4025 } 4026 moves_.Add(MoveOperands(source, destination, type, instruction)); 4027 } 4028 4029 MoveOperands* MoveOperandsAt(size_t index) const { 4030 return moves_.GetRawStorage() + index; 4031 } 4032 4033 size_t NumMoves() const { return moves_.Size(); } 4034 4035 DECLARE_INSTRUCTION(ParallelMove); 4036 4037 private: 4038 GrowableArray<MoveOperands> moves_; 4039 4040 DISALLOW_COPY_AND_ASSIGN(HParallelMove); 4041}; 4042 4043class HGraphVisitor : public ValueObject { 4044 public: 4045 explicit HGraphVisitor(HGraph* graph) : graph_(graph) {} 4046 virtual ~HGraphVisitor() {} 4047 4048 virtual void VisitInstruction(HInstruction* instruction) { UNUSED(instruction); } 4049 virtual void VisitBasicBlock(HBasicBlock* block); 4050 4051 // Visit the graph following basic block insertion order. 4052 void VisitInsertionOrder(); 4053 4054 // Visit the graph following dominator tree reverse post-order. 4055 void VisitReversePostOrder(); 4056 4057 HGraph* GetGraph() const { return graph_; } 4058 4059 // Visit functions for instruction classes. 4060#define DECLARE_VISIT_INSTRUCTION(name, super) \ 4061 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } 4062 4063 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 4064 4065#undef DECLARE_VISIT_INSTRUCTION 4066 4067 private: 4068 HGraph* const graph_; 4069 4070 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); 4071}; 4072 4073class HGraphDelegateVisitor : public HGraphVisitor { 4074 public: 4075 explicit HGraphDelegateVisitor(HGraph* graph) : HGraphVisitor(graph) {} 4076 virtual ~HGraphDelegateVisitor() {} 4077 4078 // Visit functions that delegate to to super class. 4079#define DECLARE_VISIT_INSTRUCTION(name, super) \ 4080 void Visit##name(H##name* instr) OVERRIDE { Visit##super(instr); } 4081 4082 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 4083 4084#undef DECLARE_VISIT_INSTRUCTION 4085 4086 private: 4087 DISALLOW_COPY_AND_ASSIGN(HGraphDelegateVisitor); 4088}; 4089 4090class HInsertionOrderIterator : public ValueObject { 4091 public: 4092 explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 4093 4094 bool Done() const { return index_ == graph_.GetBlocks().Size(); } 4095 HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); } 4096 void Advance() { ++index_; } 4097 4098 private: 4099 const HGraph& graph_; 4100 size_t index_; 4101 4102 DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator); 4103}; 4104 4105class HReversePostOrderIterator : public ValueObject { 4106 public: 4107 explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) { 4108 // Check that reverse post order of the graph has been built. 4109 DCHECK(!graph.GetReversePostOrder().IsEmpty()); 4110 } 4111 4112 bool Done() const { return index_ == graph_.GetReversePostOrder().Size(); } 4113 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_); } 4114 void Advance() { ++index_; } 4115 4116 private: 4117 const HGraph& graph_; 4118 size_t index_; 4119 4120 DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator); 4121}; 4122 4123class HPostOrderIterator : public ValueObject { 4124 public: 4125 explicit HPostOrderIterator(const HGraph& graph) 4126 : graph_(graph), index_(graph_.GetReversePostOrder().Size()) { 4127 // Check that reverse post order of the graph has been built. 4128 DCHECK(!graph.GetReversePostOrder().IsEmpty()); 4129 } 4130 4131 bool Done() const { return index_ == 0; } 4132 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_ - 1); } 4133 void Advance() { --index_; } 4134 4135 private: 4136 const HGraph& graph_; 4137 size_t index_; 4138 4139 DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); 4140}; 4141 4142class HLinearPostOrderIterator : public ValueObject { 4143 public: 4144 explicit HLinearPostOrderIterator(const HGraph& graph) 4145 : order_(graph.GetLinearOrder()), index_(graph.GetLinearOrder().Size()) {} 4146 4147 bool Done() const { return index_ == 0; } 4148 4149 HBasicBlock* Current() const { return order_.Get(index_ -1); } 4150 4151 void Advance() { 4152 --index_; 4153 DCHECK_GE(index_, 0U); 4154 } 4155 4156 private: 4157 const GrowableArray<HBasicBlock*>& order_; 4158 size_t index_; 4159 4160 DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator); 4161}; 4162 4163class HLinearOrderIterator : public ValueObject { 4164 public: 4165 explicit HLinearOrderIterator(const HGraph& graph) 4166 : order_(graph.GetLinearOrder()), index_(0) {} 4167 4168 bool Done() const { return index_ == order_.Size(); } 4169 HBasicBlock* Current() const { return order_.Get(index_); } 4170 void Advance() { ++index_; } 4171 4172 private: 4173 const GrowableArray<HBasicBlock*>& order_; 4174 size_t index_; 4175 4176 DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator); 4177}; 4178 4179// Iterator over the blocks that art part of the loop. Includes blocks part 4180// of an inner loop. The order in which the blocks are iterated is on their 4181// block id. 4182class HBlocksInLoopIterator : public ValueObject { 4183 public: 4184 explicit HBlocksInLoopIterator(const HLoopInformation& info) 4185 : blocks_in_loop_(info.GetBlocks()), 4186 blocks_(info.GetHeader()->GetGraph()->GetBlocks()), 4187 index_(0) { 4188 if (!blocks_in_loop_.IsBitSet(index_)) { 4189 Advance(); 4190 } 4191 } 4192 4193 bool Done() const { return index_ == blocks_.Size(); } 4194 HBasicBlock* Current() const { return blocks_.Get(index_); } 4195 void Advance() { 4196 ++index_; 4197 for (size_t e = blocks_.Size(); index_ < e; ++index_) { 4198 if (blocks_in_loop_.IsBitSet(index_)) { 4199 break; 4200 } 4201 } 4202 } 4203 4204 private: 4205 const BitVector& blocks_in_loop_; 4206 const GrowableArray<HBasicBlock*>& blocks_; 4207 size_t index_; 4208 4209 DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopIterator); 4210}; 4211 4212inline int64_t Int64FromConstant(HConstant* constant) { 4213 DCHECK(constant->IsIntConstant() || constant->IsLongConstant()); 4214 return constant->IsIntConstant() ? constant->AsIntConstant()->GetValue() 4215 : constant->AsLongConstant()->GetValue(); 4216} 4217 4218} // namespace art 4219 4220#endif // ART_COMPILER_OPTIMIZING_NODES_H_ 4221