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