nodes.h revision 18efde5017369e005f1e8bcd3bbfb04e85053640
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 "locations.h" 21#include "offsets.h" 22#include "primitive.h" 23#include "utils/allocation.h" 24#include "utils/arena_bit_vector.h" 25#include "utils/growable_array.h" 26 27namespace art { 28 29class HBasicBlock; 30class HEnvironment; 31class HInstruction; 32class HIntConstant; 33class HGraphVisitor; 34class HPhi; 35class LiveInterval; 36class LocationSummary; 37 38static const int kDefaultNumberOfBlocks = 8; 39static const int kDefaultNumberOfSuccessors = 2; 40static const int kDefaultNumberOfPredecessors = 2; 41static const int kDefaultNumberOfDominatedBlocks = 1; 42static const int kDefaultNumberOfBackEdges = 1; 43 44enum IfCondition { 45 kCondEQ, 46 kCondNE, 47 kCondLT, 48 kCondLE, 49 kCondGT, 50 kCondGE, 51}; 52 53class HInstructionList { 54 public: 55 HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {} 56 57 void AddInstruction(HInstruction* instruction); 58 void RemoveInstruction(HInstruction* instruction); 59 60 // Return true if `instruction1` is found before `instruction2` in 61 // this instruction list and false otherwise. Abort if none 62 // of these instructions is found. 63 bool FoundBefore(const HInstruction* instruction1, 64 const HInstruction* instruction2) const; 65 66 private: 67 HInstruction* first_instruction_; 68 HInstruction* last_instruction_; 69 70 friend class HBasicBlock; 71 friend class HInstructionIterator; 72 friend class HBackwardInstructionIterator; 73 74 DISALLOW_COPY_AND_ASSIGN(HInstructionList); 75}; 76 77// Control-flow graph of a method. Contains a list of basic blocks. 78class HGraph : public ArenaObject { 79 public: 80 explicit HGraph(ArenaAllocator* arena) 81 : arena_(arena), 82 blocks_(arena, kDefaultNumberOfBlocks), 83 reverse_post_order_(arena, kDefaultNumberOfBlocks), 84 maximum_number_of_out_vregs_(0), 85 number_of_vregs_(0), 86 number_of_in_vregs_(0), 87 number_of_temporaries_(0), 88 current_instruction_id_(0) {} 89 90 ArenaAllocator* GetArena() const { return arena_; } 91 const GrowableArray<HBasicBlock*>& GetBlocks() const { return blocks_; } 92 93 HBasicBlock* GetEntryBlock() const { return entry_block_; } 94 HBasicBlock* GetExitBlock() const { return exit_block_; } 95 96 void SetEntryBlock(HBasicBlock* block) { entry_block_ = block; } 97 void SetExitBlock(HBasicBlock* block) { exit_block_ = block; } 98 99 void AddBlock(HBasicBlock* block); 100 101 void BuildDominatorTree(); 102 void TransformToSSA(); 103 void SimplifyCFG(); 104 105 // Find all natural loops in this graph. Aborts computation and returns false 106 // if one loop is not natural, that is the header does not dominate the back 107 // edge. 108 bool FindNaturalLoops() const; 109 110 void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor); 111 void SimplifyLoop(HBasicBlock* header); 112 113 int GetNextInstructionId() { 114 return current_instruction_id_++; 115 } 116 117 uint16_t GetMaximumNumberOfOutVRegs() const { 118 return maximum_number_of_out_vregs_; 119 } 120 121 void UpdateMaximumNumberOfOutVRegs(uint16_t new_value) { 122 maximum_number_of_out_vregs_ = std::max(new_value, maximum_number_of_out_vregs_); 123 } 124 125 void UpdateNumberOfTemporaries(size_t count) { 126 number_of_temporaries_ = std::max(count, number_of_temporaries_); 127 } 128 129 size_t GetNumberOfTemporaries() const { 130 return number_of_temporaries_; 131 } 132 133 void SetNumberOfVRegs(uint16_t number_of_vregs) { 134 number_of_vregs_ = number_of_vregs; 135 } 136 137 uint16_t GetNumberOfVRegs() const { 138 return number_of_vregs_; 139 } 140 141 void SetNumberOfInVRegs(uint16_t value) { 142 number_of_in_vregs_ = value; 143 } 144 145 uint16_t GetNumberOfInVRegs() const { 146 return number_of_in_vregs_; 147 } 148 149 uint16_t GetNumberOfLocalVRegs() const { 150 return number_of_vregs_ - number_of_in_vregs_; 151 } 152 153 const GrowableArray<HBasicBlock*>& GetReversePostOrder() const { 154 return reverse_post_order_; 155 } 156 157 private: 158 HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const; 159 void VisitBlockForDominatorTree(HBasicBlock* block, 160 HBasicBlock* predecessor, 161 GrowableArray<size_t>* visits); 162 void FindBackEdges(ArenaBitVector* visited); 163 void VisitBlockForBackEdges(HBasicBlock* block, 164 ArenaBitVector* visited, 165 ArenaBitVector* visiting); 166 void RemoveDeadBlocks(const ArenaBitVector& visited) const; 167 168 ArenaAllocator* const arena_; 169 170 // List of blocks in insertion order. 171 GrowableArray<HBasicBlock*> blocks_; 172 173 // List of blocks to perform a reverse post order tree traversal. 174 GrowableArray<HBasicBlock*> reverse_post_order_; 175 176 HBasicBlock* entry_block_; 177 HBasicBlock* exit_block_; 178 179 // The maximum number of virtual registers arguments passed to a HInvoke in this graph. 180 uint16_t maximum_number_of_out_vregs_; 181 182 // The number of virtual registers in this method. Contains the parameters. 183 uint16_t number_of_vregs_; 184 185 // The number of virtual registers used by parameters of this method. 186 uint16_t number_of_in_vregs_; 187 188 // The number of temporaries that will be needed for the baseline compiler. 189 size_t number_of_temporaries_; 190 191 // The current id to assign to a newly added instruction. See HInstruction.id_. 192 int current_instruction_id_; 193 194 DISALLOW_COPY_AND_ASSIGN(HGraph); 195}; 196 197class HLoopInformation : public ArenaObject { 198 public: 199 HLoopInformation(HBasicBlock* header, HGraph* graph) 200 : header_(header), 201 back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges), 202 // Make bit vector growable, as the number of blocks may change. 203 blocks_(graph->GetArena(), graph->GetBlocks().Size(), true) {} 204 205 HBasicBlock* GetHeader() const { 206 return header_; 207 } 208 209 void AddBackEdge(HBasicBlock* back_edge) { 210 back_edges_.Add(back_edge); 211 } 212 213 void RemoveBackEdge(HBasicBlock* back_edge) { 214 back_edges_.Delete(back_edge); 215 } 216 217 bool IsBackEdge(HBasicBlock* block) { 218 for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) { 219 if (back_edges_.Get(i) == block) return true; 220 } 221 return false; 222 } 223 224 int NumberOfBackEdges() const { 225 return back_edges_.Size(); 226 } 227 228 HBasicBlock* GetPreHeader() const; 229 230 const GrowableArray<HBasicBlock*>& GetBackEdges() const { 231 return back_edges_; 232 } 233 234 void ClearBackEdges() { 235 back_edges_.Reset(); 236 } 237 238 // Find blocks that are part of this loop. Returns whether the loop is a natural loop, 239 // that is the header dominates the back edge. 240 bool Populate(); 241 242 // Returns whether this loop information contains `block`. 243 // Note that this loop information *must* be populated before entering this function. 244 bool Contains(const HBasicBlock& block) const; 245 246 // Returns whether this loop information is an inner loop of `other`. 247 // Note that `other` *must* be populated before entering this function. 248 bool IsIn(const HLoopInformation& other) const; 249 250 const ArenaBitVector& GetBlocks() const { return blocks_; } 251 252 private: 253 // Internal recursive implementation of `Populate`. 254 void PopulateRecursive(HBasicBlock* block); 255 256 HBasicBlock* header_; 257 GrowableArray<HBasicBlock*> back_edges_; 258 ArenaBitVector blocks_; 259 260 DISALLOW_COPY_AND_ASSIGN(HLoopInformation); 261}; 262 263static constexpr size_t kNoLifetime = -1; 264 265// A block in a method. Contains the list of instructions represented 266// as a double linked list. Each block knows its predecessors and 267// successors. 268class HBasicBlock : public ArenaObject { 269 public: 270 explicit HBasicBlock(HGraph* graph) 271 : graph_(graph), 272 predecessors_(graph->GetArena(), kDefaultNumberOfPredecessors), 273 successors_(graph->GetArena(), kDefaultNumberOfSuccessors), 274 loop_information_(nullptr), 275 dominator_(nullptr), 276 dominated_blocks_(graph->GetArena(), kDefaultNumberOfDominatedBlocks), 277 block_id_(-1), 278 lifetime_start_(kNoLifetime), 279 lifetime_end_(kNoLifetime) {} 280 281 const GrowableArray<HBasicBlock*>& GetPredecessors() const { 282 return predecessors_; 283 } 284 285 const GrowableArray<HBasicBlock*>& GetSuccessors() const { 286 return successors_; 287 } 288 289 const GrowableArray<HBasicBlock*>& GetDominatedBlocks() const { 290 return dominated_blocks_; 291 } 292 293 void AddBackEdge(HBasicBlock* back_edge) { 294 if (loop_information_ == nullptr) { 295 loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_); 296 } 297 DCHECK_EQ(loop_information_->GetHeader(), this); 298 loop_information_->AddBackEdge(back_edge); 299 } 300 301 HGraph* GetGraph() const { return graph_; } 302 303 int GetBlockId() const { return block_id_; } 304 void SetBlockId(int id) { block_id_ = id; } 305 306 HBasicBlock* GetDominator() const { return dominator_; } 307 void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; } 308 void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); } 309 310 int NumberOfBackEdges() const { 311 return loop_information_ == nullptr 312 ? 0 313 : loop_information_->NumberOfBackEdges(); 314 } 315 316 HInstruction* GetFirstInstruction() const { return instructions_.first_instruction_; } 317 HInstruction* GetLastInstruction() const { return instructions_.last_instruction_; } 318 const HInstructionList& GetInstructions() const { return instructions_; } 319 const HInstructionList& GetPhis() const { return phis_; } 320 HInstruction* GetFirstPhi() const { return phis_.first_instruction_; } 321 322 void AddSuccessor(HBasicBlock* block) { 323 successors_.Add(block); 324 block->predecessors_.Add(this); 325 } 326 327 void ReplaceSuccessor(HBasicBlock* existing, HBasicBlock* new_block) { 328 size_t successor_index = GetSuccessorIndexOf(existing); 329 DCHECK_NE(successor_index, static_cast<size_t>(-1)); 330 existing->RemovePredecessor(this); 331 new_block->predecessors_.Add(this); 332 successors_.Put(successor_index, new_block); 333 } 334 335 void RemovePredecessor(HBasicBlock* block) { 336 predecessors_.Delete(block); 337 } 338 339 void ClearAllPredecessors() { 340 predecessors_.Reset(); 341 } 342 343 void AddPredecessor(HBasicBlock* block) { 344 predecessors_.Add(block); 345 block->successors_.Add(this); 346 } 347 348 void SwapPredecessors() { 349 DCHECK_EQ(predecessors_.Size(), 2u); 350 HBasicBlock* temp = predecessors_.Get(0); 351 predecessors_.Put(0, predecessors_.Get(1)); 352 predecessors_.Put(1, temp); 353 } 354 355 size_t GetPredecessorIndexOf(HBasicBlock* predecessor) { 356 for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) { 357 if (predecessors_.Get(i) == predecessor) { 358 return i; 359 } 360 } 361 return -1; 362 } 363 364 size_t GetSuccessorIndexOf(HBasicBlock* successor) { 365 for (size_t i = 0, e = successors_.Size(); i < e; ++i) { 366 if (successors_.Get(i) == successor) { 367 return i; 368 } 369 } 370 return -1; 371 } 372 373 void AddInstruction(HInstruction* instruction); 374 void RemoveInstruction(HInstruction* instruction); 375 void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); 376 // Replace instruction `initial` with `replacement` within this block. 377 void ReplaceAndRemoveInstructionWith(HInstruction* initial, 378 HInstruction* replacement); 379 void AddPhi(HPhi* phi); 380 void RemovePhi(HPhi* phi); 381 382 bool IsLoopHeader() const { 383 return (loop_information_ != nullptr) && (loop_information_->GetHeader() == this); 384 } 385 386 HLoopInformation* GetLoopInformation() const { 387 return loop_information_; 388 } 389 390 // Set the loop_information_ on this block. This method overrides the current 391 // loop_information if it is an outer loop of the passed loop information. 392 void SetInLoop(HLoopInformation* info) { 393 if (IsLoopHeader()) { 394 // Nothing to do. This just means `info` is an outer loop. 395 } else if (loop_information_ == nullptr) { 396 loop_information_ = info; 397 } else if (loop_information_->Contains(*info->GetHeader())) { 398 // Block is currently part of an outer loop. Make it part of this inner loop. 399 // Note that a non loop header having a loop information means this loop information 400 // has already been populated 401 loop_information_ = info; 402 } else { 403 // Block is part of an inner loop. Do not update the loop information. 404 // Note that we cannot do the check `info->Contains(loop_information_)->GetHeader()` 405 // at this point, because this method is being called while populating `info`. 406 } 407 } 408 409 bool IsInLoop() const { return loop_information_ != nullptr; } 410 411 // Returns wheter this block dominates the blocked passed as parameter. 412 bool Dominates(HBasicBlock* block) const; 413 414 size_t GetLifetimeStart() const { return lifetime_start_; } 415 size_t GetLifetimeEnd() const { return lifetime_end_; } 416 417 void SetLifetimeStart(size_t start) { lifetime_start_ = start; } 418 void SetLifetimeEnd(size_t end) { lifetime_end_ = end; } 419 420 private: 421 HGraph* const graph_; 422 GrowableArray<HBasicBlock*> predecessors_; 423 GrowableArray<HBasicBlock*> successors_; 424 HInstructionList instructions_; 425 HInstructionList phis_; 426 HLoopInformation* loop_information_; 427 HBasicBlock* dominator_; 428 GrowableArray<HBasicBlock*> dominated_blocks_; 429 int block_id_; 430 size_t lifetime_start_; 431 size_t lifetime_end_; 432 433 DISALLOW_COPY_AND_ASSIGN(HBasicBlock); 434}; 435 436#define FOR_EACH_CONCRETE_INSTRUCTION(M) \ 437 M(Add) \ 438 M(Condition) \ 439 M(Equal) \ 440 M(NotEqual) \ 441 M(LessThan) \ 442 M(LessThanOrEqual) \ 443 M(GreaterThan) \ 444 M(GreaterThanOrEqual) \ 445 M(Exit) \ 446 M(Goto) \ 447 M(If) \ 448 M(IntConstant) \ 449 M(InvokeStatic) \ 450 M(InvokeVirtual) \ 451 M(LoadLocal) \ 452 M(Local) \ 453 M(LongConstant) \ 454 M(NewInstance) \ 455 M(Not) \ 456 M(ParameterValue) \ 457 M(ParallelMove) \ 458 M(Phi) \ 459 M(Return) \ 460 M(ReturnVoid) \ 461 M(StoreLocal) \ 462 M(Sub) \ 463 M(Compare) \ 464 M(InstanceFieldGet) \ 465 M(InstanceFieldSet) \ 466 M(ArrayGet) \ 467 M(ArraySet) \ 468 M(ArrayLength) \ 469 M(BoundsCheck) \ 470 M(NullCheck) \ 471 M(Temporary) \ 472 M(SuspendCheck) \ 473 474#define FOR_EACH_INSTRUCTION(M) \ 475 FOR_EACH_CONCRETE_INSTRUCTION(M) \ 476 M(Constant) \ 477 M(BinaryOperation) 478 479#define FORWARD_DECLARATION(type) class H##type; 480FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) 481#undef FORWARD_DECLARATION 482 483#define DECLARE_INSTRUCTION(type) \ 484 virtual InstructionKind GetKind() const { return k##type; } \ 485 virtual const char* DebugName() const { return #type; } \ 486 virtual const H##type* As##type() const OVERRIDE { return this; } \ 487 virtual H##type* As##type() OVERRIDE { return this; } \ 488 virtual bool InstructionTypeEquals(HInstruction* other) const { \ 489 return other->Is##type(); \ 490 } \ 491 virtual void Accept(HGraphVisitor* visitor) 492 493template <typename T> 494class HUseListNode : public ArenaObject { 495 public: 496 HUseListNode(T* user, size_t index, HUseListNode* tail) 497 : user_(user), index_(index), tail_(tail) {} 498 499 HUseListNode* GetTail() const { return tail_; } 500 T* GetUser() const { return user_; } 501 size_t GetIndex() const { return index_; } 502 503 void SetTail(HUseListNode<T>* node) { tail_ = node; } 504 505 private: 506 T* const user_; 507 const size_t index_; 508 HUseListNode<T>* tail_; 509 510 DISALLOW_COPY_AND_ASSIGN(HUseListNode); 511}; 512 513// Represents the side effects an instruction may have. 514class SideEffects : public ValueObject { 515 public: 516 SideEffects() : flags_(0) {} 517 518 static SideEffects None() { 519 return SideEffects(0); 520 } 521 522 static SideEffects All() { 523 return SideEffects(ChangesSomething().flags_ | DependsOnSomething().flags_); 524 } 525 526 static SideEffects ChangesSomething() { 527 return SideEffects((1 << kFlagChangesCount) - 1); 528 } 529 530 static SideEffects DependsOnSomething() { 531 int count = kFlagDependsOnCount - kFlagChangesCount; 532 return SideEffects(((1 << count) - 1) << kFlagChangesCount); 533 } 534 535 SideEffects Union(SideEffects other) const { 536 return SideEffects(flags_ | other.flags_); 537 } 538 539 bool HasSideEffects() const { 540 size_t all_bits_set = (1 << kFlagChangesCount) - 1; 541 return (flags_ & all_bits_set) != 0; 542 } 543 544 bool HasAllSideEffects() const { 545 size_t all_bits_set = (1 << kFlagChangesCount) - 1; 546 return all_bits_set == (flags_ & all_bits_set); 547 } 548 549 bool DependsOn(SideEffects other) const { 550 size_t depends_flags = other.ComputeDependsFlags(); 551 return (flags_ & depends_flags) != 0; 552 } 553 554 bool HasDependencies() const { 555 int count = kFlagDependsOnCount - kFlagChangesCount; 556 size_t all_bits_set = (1 << count) - 1; 557 return ((flags_ >> kFlagChangesCount) & all_bits_set) != 0; 558 } 559 560 private: 561 static constexpr int kFlagChangesSomething = 0; 562 static constexpr int kFlagChangesCount = kFlagChangesSomething + 1; 563 564 static constexpr int kFlagDependsOnSomething = kFlagChangesCount; 565 static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1; 566 567 explicit SideEffects(size_t flags) : flags_(flags) {} 568 569 size_t ComputeDependsFlags() const { 570 return flags_ << kFlagChangesCount; 571 } 572 573 size_t flags_; 574}; 575 576class HInstruction : public ArenaObject { 577 public: 578 explicit HInstruction(SideEffects side_effects) 579 : previous_(nullptr), 580 next_(nullptr), 581 block_(nullptr), 582 id_(-1), 583 ssa_index_(-1), 584 uses_(nullptr), 585 env_uses_(nullptr), 586 environment_(nullptr), 587 locations_(nullptr), 588 live_interval_(nullptr), 589 lifetime_position_(kNoLifetime), 590 side_effects_(side_effects) {} 591 592 virtual ~HInstruction() {} 593 594#define DECLARE_KIND(type) k##type, 595 enum InstructionKind { 596 FOR_EACH_INSTRUCTION(DECLARE_KIND) 597 }; 598#undef DECLARE_KIND 599 600 HInstruction* GetNext() const { return next_; } 601 HInstruction* GetPrevious() const { return previous_; } 602 603 HBasicBlock* GetBlock() const { return block_; } 604 void SetBlock(HBasicBlock* block) { block_ = block; } 605 bool IsInBlock() const { return block_ != nullptr; } 606 bool IsInLoop() const { return block_->IsInLoop(); } 607 bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); } 608 609 virtual size_t InputCount() const = 0; 610 virtual HInstruction* InputAt(size_t i) const = 0; 611 612 virtual void Accept(HGraphVisitor* visitor) = 0; 613 virtual const char* DebugName() const = 0; 614 615 virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; } 616 virtual void SetRawInputAt(size_t index, HInstruction* input) = 0; 617 618 virtual bool NeedsEnvironment() const { return false; } 619 virtual bool IsControlFlow() const { return false; } 620 bool HasSideEffects() const { return side_effects_.HasSideEffects(); } 621 622 void AddUseAt(HInstruction* user, size_t index) { 623 uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HInstruction>(user, index, uses_); 624 } 625 626 void AddEnvUseAt(HEnvironment* user, size_t index) { 627 env_uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HEnvironment>( 628 user, index, env_uses_); 629 } 630 631 void RemoveUser(HInstruction* user, size_t index); 632 633 HUseListNode<HInstruction>* GetUses() const { return uses_; } 634 HUseListNode<HEnvironment>* GetEnvUses() const { return env_uses_; } 635 636 bool HasUses() const { return uses_ != nullptr || env_uses_ != nullptr; } 637 bool HasEnvironmentUses() const { return env_uses_ != nullptr; } 638 639 size_t NumberOfUses() const { 640 // TODO: Optimize this method if it is used outside of the HGraphVisualizer. 641 size_t result = 0; 642 HUseListNode<HInstruction>* current = uses_; 643 while (current != nullptr) { 644 current = current->GetTail(); 645 ++result; 646 } 647 return result; 648 } 649 650 // Does this instruction dominate `other_instruction`? Aborts if 651 // this instruction and `other_instruction` are both phis. 652 bool Dominates(HInstruction* other_instruction) const; 653 654 int GetId() const { return id_; } 655 void SetId(int id) { id_ = id; } 656 657 int GetSsaIndex() const { return ssa_index_; } 658 void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; } 659 bool HasSsaIndex() const { return ssa_index_ != -1; } 660 661 bool HasEnvironment() const { return environment_ != nullptr; } 662 HEnvironment* GetEnvironment() const { return environment_; } 663 void SetEnvironment(HEnvironment* environment) { environment_ = environment; } 664 665 // Returns the number of entries in the environment. Typically, that is the 666 // number of dex registers in a method. It could be more in case of inlining. 667 size_t EnvironmentSize() const; 668 669 LocationSummary* GetLocations() const { return locations_; } 670 void SetLocations(LocationSummary* locations) { locations_ = locations; } 671 672 void ReplaceWith(HInstruction* instruction); 673 674 bool HasOnlyOneUse() const { 675 return uses_ != nullptr && uses_->GetTail() == nullptr; 676 } 677 678#define INSTRUCTION_TYPE_CHECK(type) \ 679 bool Is##type() const { return (As##type() != nullptr); } \ 680 virtual const H##type* As##type() const { return nullptr; } \ 681 virtual H##type* As##type() { return nullptr; } 682 683 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 684#undef INSTRUCTION_TYPE_CHECK 685 686 // Returns whether the instruction can be moved within the graph. 687 virtual bool CanBeMoved() const { return false; } 688 689 // Returns whether the two instructions are of the same kind. 690 virtual bool InstructionTypeEquals(HInstruction* other) const { return false; } 691 692 // Returns whether any data encoded in the two instructions is equal. 693 // This method does not look at the inputs. Both instructions must be 694 // of the same type, otherwise the method has undefined behavior. 695 virtual bool InstructionDataEquals(HInstruction* other) const { return false; } 696 697 // Returns whether two instructions are equal, that is: 698 // 1) They have the same type and contain the same data, 699 // 2) Their inputs are identical. 700 bool Equals(HInstruction* other) const; 701 702 virtual InstructionKind GetKind() const = 0; 703 704 virtual size_t ComputeHashCode() const { 705 size_t result = GetKind(); 706 for (size_t i = 0, e = InputCount(); i < e; ++i) { 707 result = (result * 31) + InputAt(i)->GetId(); 708 } 709 return result; 710 } 711 712 SideEffects GetSideEffects() const { return side_effects_; } 713 714 size_t GetLifetimePosition() const { return lifetime_position_; } 715 void SetLifetimePosition(size_t position) { lifetime_position_ = position; } 716 LiveInterval* GetLiveInterval() const { return live_interval_; } 717 void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; } 718 bool HasLiveInterval() const { return live_interval_ != nullptr; } 719 720 private: 721 HInstruction* previous_; 722 HInstruction* next_; 723 HBasicBlock* block_; 724 725 // An instruction gets an id when it is added to the graph. 726 // It reflects creation order. A negative id means the instruction 727 // has not been added to the graph. 728 int id_; 729 730 // When doing liveness analysis, instructions that have uses get an SSA index. 731 int ssa_index_; 732 733 // List of instructions that have this instruction as input. 734 HUseListNode<HInstruction>* uses_; 735 736 // List of environments that contain this instruction. 737 HUseListNode<HEnvironment>* env_uses_; 738 739 // The environment associated with this instruction. Not null if the instruction 740 // might jump out of the method. 741 HEnvironment* environment_; 742 743 // Set by the code generator. 744 LocationSummary* locations_; 745 746 // Set by the liveness analysis. 747 LiveInterval* live_interval_; 748 749 // Set by the liveness analysis, this is the position in a linear 750 // order of blocks where this instruction's live interval start. 751 size_t lifetime_position_; 752 753 const SideEffects side_effects_; 754 755 friend class HBasicBlock; 756 friend class HInstructionList; 757 758 DISALLOW_COPY_AND_ASSIGN(HInstruction); 759}; 760 761template<typename T> 762class HUseIterator : public ValueObject { 763 public: 764 explicit HUseIterator(HUseListNode<T>* uses) : current_(uses) {} 765 766 bool Done() const { return current_ == nullptr; } 767 768 void Advance() { 769 DCHECK(!Done()); 770 current_ = current_->GetTail(); 771 } 772 773 HUseListNode<T>* Current() const { 774 DCHECK(!Done()); 775 return current_; 776 } 777 778 private: 779 HUseListNode<T>* current_; 780 781 friend class HValue; 782}; 783 784// A HEnvironment object contains the values of virtual registers at a given location. 785class HEnvironment : public ArenaObject { 786 public: 787 HEnvironment(ArenaAllocator* arena, size_t number_of_vregs) : vregs_(arena, number_of_vregs) { 788 vregs_.SetSize(number_of_vregs); 789 for (size_t i = 0; i < number_of_vregs; i++) { 790 vregs_.Put(i, nullptr); 791 } 792 } 793 794 void Populate(const GrowableArray<HInstruction*>& env) { 795 for (size_t i = 0; i < env.Size(); i++) { 796 HInstruction* instruction = env.Get(i); 797 vregs_.Put(i, instruction); 798 if (instruction != nullptr) { 799 instruction->AddEnvUseAt(this, i); 800 } 801 } 802 } 803 804 void SetRawEnvAt(size_t index, HInstruction* instruction) { 805 vregs_.Put(index, instruction); 806 } 807 808 HInstruction* GetInstructionAt(size_t index) const { 809 return vregs_.Get(index); 810 } 811 812 GrowableArray<HInstruction*>* GetVRegs() { 813 return &vregs_; 814 } 815 816 size_t Size() const { return vregs_.Size(); } 817 818 private: 819 GrowableArray<HInstruction*> vregs_; 820 821 DISALLOW_COPY_AND_ASSIGN(HEnvironment); 822}; 823 824class HInputIterator : public ValueObject { 825 public: 826 explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {} 827 828 bool Done() const { return index_ == instruction_->InputCount(); } 829 HInstruction* Current() const { return instruction_->InputAt(index_); } 830 void Advance() { index_++; } 831 832 private: 833 HInstruction* instruction_; 834 size_t index_; 835 836 DISALLOW_COPY_AND_ASSIGN(HInputIterator); 837}; 838 839class HInstructionIterator : public ValueObject { 840 public: 841 explicit HInstructionIterator(const HInstructionList& instructions) 842 : instruction_(instructions.first_instruction_) { 843 next_ = Done() ? nullptr : instruction_->GetNext(); 844 } 845 846 bool Done() const { return instruction_ == nullptr; } 847 HInstruction* Current() const { return instruction_; } 848 void Advance() { 849 instruction_ = next_; 850 next_ = Done() ? nullptr : instruction_->GetNext(); 851 } 852 853 private: 854 HInstruction* instruction_; 855 HInstruction* next_; 856 857 DISALLOW_COPY_AND_ASSIGN(HInstructionIterator); 858}; 859 860class HBackwardInstructionIterator : public ValueObject { 861 public: 862 explicit HBackwardInstructionIterator(const HInstructionList& instructions) 863 : instruction_(instructions.last_instruction_) { 864 next_ = Done() ? nullptr : instruction_->GetPrevious(); 865 } 866 867 bool Done() const { return instruction_ == nullptr; } 868 HInstruction* Current() const { return instruction_; } 869 void Advance() { 870 instruction_ = next_; 871 next_ = Done() ? nullptr : instruction_->GetPrevious(); 872 } 873 874 private: 875 HInstruction* instruction_; 876 HInstruction* next_; 877 878 DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator); 879}; 880 881// An embedded container with N elements of type T. Used (with partial 882// specialization for N=0) because embedded arrays cannot have size 0. 883template<typename T, intptr_t N> 884class EmbeddedArray { 885 public: 886 EmbeddedArray() : elements_() {} 887 888 intptr_t GetLength() const { return N; } 889 890 const T& operator[](intptr_t i) const { 891 DCHECK_LT(i, GetLength()); 892 return elements_[i]; 893 } 894 895 T& operator[](intptr_t i) { 896 DCHECK_LT(i, GetLength()); 897 return elements_[i]; 898 } 899 900 const T& At(intptr_t i) const { 901 return (*this)[i]; 902 } 903 904 void SetAt(intptr_t i, const T& val) { 905 (*this)[i] = val; 906 } 907 908 private: 909 T elements_[N]; 910}; 911 912template<typename T> 913class EmbeddedArray<T, 0> { 914 public: 915 intptr_t length() const { return 0; } 916 const T& operator[](intptr_t i) const { 917 LOG(FATAL) << "Unreachable"; 918 static T sentinel = 0; 919 return sentinel; 920 } 921 T& operator[](intptr_t i) { 922 LOG(FATAL) << "Unreachable"; 923 static T sentinel = 0; 924 return sentinel; 925 } 926}; 927 928template<intptr_t N> 929class HTemplateInstruction: public HInstruction { 930 public: 931 HTemplateInstruction<N>(SideEffects side_effects) 932 : HInstruction(side_effects), inputs_() {} 933 virtual ~HTemplateInstruction() {} 934 935 virtual size_t InputCount() const { return N; } 936 virtual HInstruction* InputAt(size_t i) const { return inputs_[i]; } 937 938 protected: 939 virtual void SetRawInputAt(size_t i, HInstruction* instruction) { 940 inputs_[i] = instruction; 941 } 942 943 private: 944 EmbeddedArray<HInstruction*, N> inputs_; 945 946 friend class SsaBuilder; 947}; 948 949template<intptr_t N> 950class HExpression : public HTemplateInstruction<N> { 951 public: 952 HExpression<N>(Primitive::Type type, SideEffects side_effects) 953 : HTemplateInstruction<N>(side_effects), type_(type) {} 954 virtual ~HExpression() {} 955 956 virtual Primitive::Type GetType() const { return type_; } 957 958 private: 959 const Primitive::Type type_; 960}; 961 962// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow 963// instruction that branches to the exit block. 964class HReturnVoid : public HTemplateInstruction<0> { 965 public: 966 HReturnVoid() : HTemplateInstruction(SideEffects::None()) {} 967 968 virtual bool IsControlFlow() const { return true; } 969 970 DECLARE_INSTRUCTION(ReturnVoid); 971 972 private: 973 DISALLOW_COPY_AND_ASSIGN(HReturnVoid); 974}; 975 976// Represents dex's RETURN opcodes. A HReturn is a control flow 977// instruction that branches to the exit block. 978class HReturn : public HTemplateInstruction<1> { 979 public: 980 explicit HReturn(HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 981 SetRawInputAt(0, value); 982 } 983 984 virtual bool IsControlFlow() const { return true; } 985 986 DECLARE_INSTRUCTION(Return); 987 988 private: 989 DISALLOW_COPY_AND_ASSIGN(HReturn); 990}; 991 992// The exit instruction is the only instruction of the exit block. 993// Instructions aborting the method (HTrow and HReturn) must branch to the 994// exit block. 995class HExit : public HTemplateInstruction<0> { 996 public: 997 HExit() : HTemplateInstruction(SideEffects::None()) {} 998 999 virtual bool IsControlFlow() const { return true; } 1000 1001 DECLARE_INSTRUCTION(Exit); 1002 1003 private: 1004 DISALLOW_COPY_AND_ASSIGN(HExit); 1005}; 1006 1007// Jumps from one block to another. 1008class HGoto : public HTemplateInstruction<0> { 1009 public: 1010 HGoto() : HTemplateInstruction(SideEffects::None()) {} 1011 1012 virtual bool IsControlFlow() const { return true; } 1013 1014 HBasicBlock* GetSuccessor() const { 1015 return GetBlock()->GetSuccessors().Get(0); 1016 } 1017 1018 DECLARE_INSTRUCTION(Goto); 1019 1020 private: 1021 DISALLOW_COPY_AND_ASSIGN(HGoto); 1022}; 1023 1024 1025// Conditional branch. A block ending with an HIf instruction must have 1026// two successors. 1027class HIf : public HTemplateInstruction<1> { 1028 public: 1029 explicit HIf(HInstruction* input) : HTemplateInstruction(SideEffects::None()) { 1030 SetRawInputAt(0, input); 1031 } 1032 1033 virtual bool IsControlFlow() const { return true; } 1034 1035 HBasicBlock* IfTrueSuccessor() const { 1036 return GetBlock()->GetSuccessors().Get(0); 1037 } 1038 1039 HBasicBlock* IfFalseSuccessor() const { 1040 return GetBlock()->GetSuccessors().Get(1); 1041 } 1042 1043 DECLARE_INSTRUCTION(If); 1044 1045 virtual bool IsIfInstruction() const { return true; } 1046 1047 private: 1048 DISALLOW_COPY_AND_ASSIGN(HIf); 1049}; 1050 1051class HBinaryOperation : public HExpression<2> { 1052 public: 1053 HBinaryOperation(Primitive::Type result_type, 1054 HInstruction* left, 1055 HInstruction* right) : HExpression(result_type, SideEffects::None()) { 1056 SetRawInputAt(0, left); 1057 SetRawInputAt(1, right); 1058 } 1059 1060 HInstruction* GetLeft() const { return InputAt(0); } 1061 HInstruction* GetRight() const { return InputAt(1); } 1062 Primitive::Type GetResultType() const { return GetType(); } 1063 1064 virtual bool IsCommutative() { return false; } 1065 1066 virtual bool CanBeMoved() const { return true; } 1067 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1068 1069 // Try to statically evaluate `operation` and return an HConstant 1070 // containing the result of this evaluation. If `operation` cannot 1071 // be evaluated as a constant, return nullptr. 1072 HConstant* TryStaticEvaluation(ArenaAllocator* allocator) const; 1073 1074 // Apply this operation to `x` and `y`. 1075 virtual int32_t Evaluate(int32_t x, int32_t y) const = 0; 1076 virtual int64_t Evaluate(int64_t x, int64_t y) const = 0; 1077 1078 DECLARE_INSTRUCTION(BinaryOperation); 1079 1080 private: 1081 DISALLOW_COPY_AND_ASSIGN(HBinaryOperation); 1082}; 1083 1084class HCondition : public HBinaryOperation { 1085 public: 1086 HCondition(HInstruction* first, HInstruction* second) 1087 : HBinaryOperation(Primitive::kPrimBoolean, first, second) {} 1088 1089 virtual bool IsCommutative() { return true; } 1090 1091 // For register allocation purposes, returns whether this instruction needs to be 1092 // materialized (that is, not just be in the processor flags). 1093 bool NeedsMaterialization() const; 1094 1095 // For code generation purposes, returns whether this instruction is just before 1096 // `if_`, and disregard moves in between. 1097 bool IsBeforeWhenDisregardMoves(HIf* if_) const; 1098 1099 DECLARE_INSTRUCTION(Condition); 1100 1101 virtual IfCondition GetCondition() const = 0; 1102 1103 private: 1104 DISALLOW_COPY_AND_ASSIGN(HCondition); 1105}; 1106 1107// Instruction to check if two inputs are equal to each other. 1108class HEqual : public HCondition { 1109 public: 1110 HEqual(HInstruction* first, HInstruction* second) 1111 : HCondition(first, second) {} 1112 1113 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x == y; } 1114 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x == y; } 1115 1116 DECLARE_INSTRUCTION(Equal); 1117 1118 virtual IfCondition GetCondition() const { 1119 return kCondEQ; 1120 } 1121 1122 private: 1123 DISALLOW_COPY_AND_ASSIGN(HEqual); 1124}; 1125 1126class HNotEqual : public HCondition { 1127 public: 1128 HNotEqual(HInstruction* first, HInstruction* second) 1129 : HCondition(first, second) {} 1130 1131 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x != y; } 1132 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x != y; } 1133 1134 DECLARE_INSTRUCTION(NotEqual); 1135 1136 virtual IfCondition GetCondition() const { 1137 return kCondNE; 1138 } 1139 1140 private: 1141 DISALLOW_COPY_AND_ASSIGN(HNotEqual); 1142}; 1143 1144class HLessThan : public HCondition { 1145 public: 1146 HLessThan(HInstruction* first, HInstruction* second) 1147 : HCondition(first, second) {} 1148 1149 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x < y; } 1150 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x < y; } 1151 1152 DECLARE_INSTRUCTION(LessThan); 1153 1154 virtual IfCondition GetCondition() const { 1155 return kCondLT; 1156 } 1157 1158 private: 1159 DISALLOW_COPY_AND_ASSIGN(HLessThan); 1160}; 1161 1162class HLessThanOrEqual : public HCondition { 1163 public: 1164 HLessThanOrEqual(HInstruction* first, HInstruction* second) 1165 : HCondition(first, second) {} 1166 1167 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x <= y; } 1168 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x <= y; } 1169 1170 DECLARE_INSTRUCTION(LessThanOrEqual); 1171 1172 virtual IfCondition GetCondition() const { 1173 return kCondLE; 1174 } 1175 1176 private: 1177 DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual); 1178}; 1179 1180class HGreaterThan : public HCondition { 1181 public: 1182 HGreaterThan(HInstruction* first, HInstruction* second) 1183 : HCondition(first, second) {} 1184 1185 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x > y; } 1186 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x > y; } 1187 1188 DECLARE_INSTRUCTION(GreaterThan); 1189 1190 virtual IfCondition GetCondition() const { 1191 return kCondGT; 1192 } 1193 1194 private: 1195 DISALLOW_COPY_AND_ASSIGN(HGreaterThan); 1196}; 1197 1198class HGreaterThanOrEqual : public HCondition { 1199 public: 1200 HGreaterThanOrEqual(HInstruction* first, HInstruction* second) 1201 : HCondition(first, second) {} 1202 1203 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x >= y; } 1204 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x >= y; } 1205 1206 DECLARE_INSTRUCTION(GreaterThanOrEqual); 1207 1208 virtual IfCondition GetCondition() const { 1209 return kCondGE; 1210 } 1211 1212 private: 1213 DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual); 1214}; 1215 1216 1217// Instruction to check how two inputs compare to each other. 1218// Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1. 1219class HCompare : public HBinaryOperation { 1220 public: 1221 HCompare(Primitive::Type type, HInstruction* first, HInstruction* second) 1222 : HBinaryOperation(Primitive::kPrimInt, first, second) { 1223 DCHECK_EQ(type, first->GetType()); 1224 DCHECK_EQ(type, second->GetType()); 1225 } 1226 1227 virtual int32_t Evaluate(int32_t x, int32_t y) const { 1228 return 1229 x == y ? 0 : 1230 x > y ? 1 : 1231 -1; 1232 } 1233 virtual int64_t Evaluate(int64_t x, int64_t y) const { 1234 return 1235 x == y ? 0 : 1236 x > y ? 1 : 1237 -1; 1238 } 1239 1240 DECLARE_INSTRUCTION(Compare); 1241 1242 private: 1243 DISALLOW_COPY_AND_ASSIGN(HCompare); 1244}; 1245 1246// A local in the graph. Corresponds to a Dex register. 1247class HLocal : public HTemplateInstruction<0> { 1248 public: 1249 explicit HLocal(uint16_t reg_number) 1250 : HTemplateInstruction(SideEffects::None()), reg_number_(reg_number) {} 1251 1252 DECLARE_INSTRUCTION(Local); 1253 1254 uint16_t GetRegNumber() const { return reg_number_; } 1255 1256 private: 1257 // The Dex register number. 1258 const uint16_t reg_number_; 1259 1260 DISALLOW_COPY_AND_ASSIGN(HLocal); 1261}; 1262 1263// Load a given local. The local is an input of this instruction. 1264class HLoadLocal : public HExpression<1> { 1265 public: 1266 explicit HLoadLocal(HLocal* local, Primitive::Type type) 1267 : HExpression(type, SideEffects::None()) { 1268 SetRawInputAt(0, local); 1269 } 1270 1271 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 1272 1273 DECLARE_INSTRUCTION(LoadLocal); 1274 1275 private: 1276 DISALLOW_COPY_AND_ASSIGN(HLoadLocal); 1277}; 1278 1279// Store a value in a given local. This instruction has two inputs: the value 1280// and the local. 1281class HStoreLocal : public HTemplateInstruction<2> { 1282 public: 1283 HStoreLocal(HLocal* local, HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 1284 SetRawInputAt(0, local); 1285 SetRawInputAt(1, value); 1286 } 1287 1288 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 1289 1290 DECLARE_INSTRUCTION(StoreLocal); 1291 1292 private: 1293 DISALLOW_COPY_AND_ASSIGN(HStoreLocal); 1294}; 1295 1296class HConstant : public HExpression<0> { 1297 public: 1298 explicit HConstant(Primitive::Type type) : HExpression(type, SideEffects::None()) {} 1299 1300 virtual bool CanBeMoved() const { return true; } 1301 1302 DECLARE_INSTRUCTION(Constant); 1303 1304 private: 1305 DISALLOW_COPY_AND_ASSIGN(HConstant); 1306}; 1307 1308// Constants of the type int. Those can be from Dex instructions, or 1309// synthesized (for example with the if-eqz instruction). 1310class HIntConstant : public HConstant { 1311 public: 1312 explicit HIntConstant(int32_t value) : HConstant(Primitive::kPrimInt), value_(value) {} 1313 1314 int32_t GetValue() const { return value_; } 1315 1316 virtual bool InstructionDataEquals(HInstruction* other) const { 1317 return other->AsIntConstant()->value_ == value_; 1318 } 1319 1320 virtual size_t ComputeHashCode() const { return GetValue(); } 1321 1322 DECLARE_INSTRUCTION(IntConstant); 1323 1324 private: 1325 const int32_t value_; 1326 1327 DISALLOW_COPY_AND_ASSIGN(HIntConstant); 1328}; 1329 1330class HLongConstant : public HConstant { 1331 public: 1332 explicit HLongConstant(int64_t value) : HConstant(Primitive::kPrimLong), value_(value) {} 1333 1334 int64_t GetValue() const { return value_; } 1335 1336 virtual bool InstructionDataEquals(HInstruction* other) const { 1337 return other->AsLongConstant()->value_ == value_; 1338 } 1339 1340 virtual size_t ComputeHashCode() const { return static_cast<size_t>(GetValue()); } 1341 1342 DECLARE_INSTRUCTION(LongConstant); 1343 1344 private: 1345 const int64_t value_; 1346 1347 DISALLOW_COPY_AND_ASSIGN(HLongConstant); 1348}; 1349 1350class HInvoke : public HInstruction { 1351 public: 1352 HInvoke(ArenaAllocator* arena, 1353 uint32_t number_of_arguments, 1354 Primitive::Type return_type, 1355 uint32_t dex_pc) 1356 : HInstruction(SideEffects::All()), 1357 inputs_(arena, number_of_arguments), 1358 return_type_(return_type), 1359 dex_pc_(dex_pc) { 1360 inputs_.SetSize(number_of_arguments); 1361 } 1362 1363 virtual size_t InputCount() const { return inputs_.Size(); } 1364 virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); } 1365 1366 // Runtime needs to walk the stack, so Dex -> Dex calls need to 1367 // know their environment. 1368 virtual bool NeedsEnvironment() const { return true; } 1369 1370 void SetArgumentAt(size_t index, HInstruction* argument) { 1371 SetRawInputAt(index, argument); 1372 } 1373 1374 virtual void SetRawInputAt(size_t index, HInstruction* input) { 1375 inputs_.Put(index, input); 1376 } 1377 1378 virtual Primitive::Type GetType() const { return return_type_; } 1379 1380 uint32_t GetDexPc() const { return dex_pc_; } 1381 1382 protected: 1383 GrowableArray<HInstruction*> inputs_; 1384 const Primitive::Type return_type_; 1385 const uint32_t dex_pc_; 1386 1387 private: 1388 DISALLOW_COPY_AND_ASSIGN(HInvoke); 1389}; 1390 1391class HInvokeStatic : public HInvoke { 1392 public: 1393 HInvokeStatic(ArenaAllocator* arena, 1394 uint32_t number_of_arguments, 1395 Primitive::Type return_type, 1396 uint32_t dex_pc, 1397 uint32_t index_in_dex_cache) 1398 : HInvoke(arena, number_of_arguments, return_type, dex_pc), 1399 index_in_dex_cache_(index_in_dex_cache) {} 1400 1401 uint32_t GetIndexInDexCache() const { return index_in_dex_cache_; } 1402 1403 DECLARE_INSTRUCTION(InvokeStatic); 1404 1405 private: 1406 const uint32_t index_in_dex_cache_; 1407 1408 DISALLOW_COPY_AND_ASSIGN(HInvokeStatic); 1409}; 1410 1411class HInvokeVirtual : public HInvoke { 1412 public: 1413 HInvokeVirtual(ArenaAllocator* arena, 1414 uint32_t number_of_arguments, 1415 Primitive::Type return_type, 1416 uint32_t dex_pc, 1417 uint32_t vtable_index) 1418 : HInvoke(arena, number_of_arguments, return_type, dex_pc), 1419 vtable_index_(vtable_index) {} 1420 1421 uint32_t GetVTableIndex() const { return vtable_index_; } 1422 1423 DECLARE_INSTRUCTION(InvokeVirtual); 1424 1425 private: 1426 const uint32_t vtable_index_; 1427 1428 DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual); 1429}; 1430 1431class HNewInstance : public HExpression<0> { 1432 public: 1433 HNewInstance(uint32_t dex_pc, uint16_t type_index) 1434 : HExpression(Primitive::kPrimNot, SideEffects::None()), 1435 dex_pc_(dex_pc), 1436 type_index_(type_index) {} 1437 1438 uint32_t GetDexPc() const { return dex_pc_; } 1439 uint16_t GetTypeIndex() const { return type_index_; } 1440 1441 // Calls runtime so needs an environment. 1442 virtual bool NeedsEnvironment() const { return true; } 1443 1444 DECLARE_INSTRUCTION(NewInstance); 1445 1446 private: 1447 const uint32_t dex_pc_; 1448 const uint16_t type_index_; 1449 1450 DISALLOW_COPY_AND_ASSIGN(HNewInstance); 1451}; 1452 1453class HAdd : public HBinaryOperation { 1454 public: 1455 HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 1456 : HBinaryOperation(result_type, left, right) {} 1457 1458 virtual bool IsCommutative() { return true; } 1459 1460 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x + y; } 1461 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x + y; } 1462 1463 DECLARE_INSTRUCTION(Add); 1464 1465 private: 1466 DISALLOW_COPY_AND_ASSIGN(HAdd); 1467}; 1468 1469class HSub : public HBinaryOperation { 1470 public: 1471 HSub(Primitive::Type result_type, HInstruction* left, HInstruction* right) 1472 : HBinaryOperation(result_type, left, right) {} 1473 1474 virtual bool IsCommutative() { return false; } 1475 1476 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x + y; } 1477 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x + y; } 1478 1479 DECLARE_INSTRUCTION(Sub); 1480 1481 private: 1482 DISALLOW_COPY_AND_ASSIGN(HSub); 1483}; 1484 1485// The value of a parameter in this method. Its location depends on 1486// the calling convention. 1487class HParameterValue : public HExpression<0> { 1488 public: 1489 HParameterValue(uint8_t index, Primitive::Type parameter_type) 1490 : HExpression(parameter_type, SideEffects::None()), index_(index) {} 1491 1492 uint8_t GetIndex() const { return index_; } 1493 1494 DECLARE_INSTRUCTION(ParameterValue); 1495 1496 private: 1497 // The index of this parameter in the parameters list. Must be less 1498 // than HGraph::number_of_in_vregs_; 1499 const uint8_t index_; 1500 1501 DISALLOW_COPY_AND_ASSIGN(HParameterValue); 1502}; 1503 1504class HNot : public HExpression<1> { 1505 public: 1506 explicit HNot(HInstruction* input) : HExpression(Primitive::kPrimBoolean, SideEffects::None()) { 1507 SetRawInputAt(0, input); 1508 } 1509 1510 virtual bool CanBeMoved() const { return true; } 1511 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1512 1513 DECLARE_INSTRUCTION(Not); 1514 1515 private: 1516 DISALLOW_COPY_AND_ASSIGN(HNot); 1517}; 1518 1519class HPhi : public HInstruction { 1520 public: 1521 HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type) 1522 : HInstruction(SideEffects::None()), 1523 inputs_(arena, number_of_inputs), 1524 reg_number_(reg_number), 1525 type_(type), 1526 is_live_(false) { 1527 inputs_.SetSize(number_of_inputs); 1528 } 1529 1530 virtual size_t InputCount() const { return inputs_.Size(); } 1531 virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); } 1532 1533 virtual void SetRawInputAt(size_t index, HInstruction* input) { 1534 inputs_.Put(index, input); 1535 } 1536 1537 void AddInput(HInstruction* input); 1538 1539 virtual Primitive::Type GetType() const { return type_; } 1540 void SetType(Primitive::Type type) { type_ = type; } 1541 1542 uint32_t GetRegNumber() const { return reg_number_; } 1543 1544 void SetDead() { is_live_ = false; } 1545 void SetLive() { is_live_ = true; } 1546 bool IsDead() const { return !is_live_; } 1547 bool IsLive() const { return is_live_; } 1548 1549 DECLARE_INSTRUCTION(Phi); 1550 1551 private: 1552 GrowableArray<HInstruction*> inputs_; 1553 const uint32_t reg_number_; 1554 Primitive::Type type_; 1555 bool is_live_; 1556 1557 DISALLOW_COPY_AND_ASSIGN(HPhi); 1558}; 1559 1560class HNullCheck : public HExpression<1> { 1561 public: 1562 HNullCheck(HInstruction* value, uint32_t dex_pc) 1563 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 1564 SetRawInputAt(0, value); 1565 } 1566 1567 virtual bool CanBeMoved() const { return true; } 1568 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1569 1570 virtual bool NeedsEnvironment() const { return true; } 1571 1572 uint32_t GetDexPc() const { return dex_pc_; } 1573 1574 DECLARE_INSTRUCTION(NullCheck); 1575 1576 private: 1577 const uint32_t dex_pc_; 1578 1579 DISALLOW_COPY_AND_ASSIGN(HNullCheck); 1580}; 1581 1582class FieldInfo : public ValueObject { 1583 public: 1584 explicit FieldInfo(MemberOffset field_offset, Primitive::Type field_type) 1585 : field_offset_(field_offset), field_type_(field_type) {} 1586 1587 MemberOffset GetFieldOffset() const { return field_offset_; } 1588 Primitive::Type GetFieldType() const { return field_type_; } 1589 1590 private: 1591 const MemberOffset field_offset_; 1592 const Primitive::Type field_type_; 1593}; 1594 1595class HInstanceFieldGet : public HExpression<1> { 1596 public: 1597 HInstanceFieldGet(HInstruction* value, 1598 Primitive::Type field_type, 1599 MemberOffset field_offset) 1600 : HExpression(field_type, SideEffects::DependsOnSomething()), 1601 field_info_(field_offset, field_type) { 1602 SetRawInputAt(0, value); 1603 } 1604 1605 virtual bool CanBeMoved() const { return true; } 1606 virtual bool InstructionDataEquals(HInstruction* other) const { 1607 size_t other_offset = other->AsInstanceFieldGet()->GetFieldOffset().SizeValue(); 1608 return other_offset == GetFieldOffset().SizeValue(); 1609 } 1610 1611 virtual size_t ComputeHashCode() const { 1612 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 1613 } 1614 1615 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 1616 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 1617 1618 DECLARE_INSTRUCTION(InstanceFieldGet); 1619 1620 private: 1621 const FieldInfo field_info_; 1622 1623 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet); 1624}; 1625 1626class HInstanceFieldSet : public HTemplateInstruction<2> { 1627 public: 1628 HInstanceFieldSet(HInstruction* object, 1629 HInstruction* value, 1630 Primitive::Type field_type, 1631 MemberOffset field_offset) 1632 : HTemplateInstruction(SideEffects::ChangesSomething()), 1633 field_info_(field_offset, field_type) { 1634 SetRawInputAt(0, object); 1635 SetRawInputAt(1, value); 1636 } 1637 1638 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 1639 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 1640 1641 DECLARE_INSTRUCTION(InstanceFieldSet); 1642 1643 private: 1644 const FieldInfo field_info_; 1645 1646 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet); 1647}; 1648 1649class HArrayGet : public HExpression<2> { 1650 public: 1651 HArrayGet(HInstruction* array, HInstruction* index, Primitive::Type type) 1652 : HExpression(type, SideEffects::DependsOnSomething()) { 1653 SetRawInputAt(0, array); 1654 SetRawInputAt(1, index); 1655 } 1656 1657 virtual bool CanBeMoved() const { return true; } 1658 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1659 1660 DECLARE_INSTRUCTION(ArrayGet); 1661 1662 private: 1663 DISALLOW_COPY_AND_ASSIGN(HArrayGet); 1664}; 1665 1666class HArraySet : public HTemplateInstruction<3> { 1667 public: 1668 HArraySet(HInstruction* array, 1669 HInstruction* index, 1670 HInstruction* value, 1671 Primitive::Type component_type, 1672 uint32_t dex_pc) 1673 : HTemplateInstruction(SideEffects::ChangesSomething()), 1674 dex_pc_(dex_pc), 1675 component_type_(component_type) { 1676 SetRawInputAt(0, array); 1677 SetRawInputAt(1, index); 1678 SetRawInputAt(2, value); 1679 } 1680 1681 virtual bool NeedsEnvironment() const { 1682 // We currently always call a runtime method to catch array store 1683 // exceptions. 1684 return InputAt(2)->GetType() == Primitive::kPrimNot; 1685 } 1686 1687 uint32_t GetDexPc() const { return dex_pc_; } 1688 1689 Primitive::Type GetComponentType() const { return component_type_; } 1690 1691 DECLARE_INSTRUCTION(ArraySet); 1692 1693 private: 1694 const uint32_t dex_pc_; 1695 const Primitive::Type component_type_; 1696 1697 DISALLOW_COPY_AND_ASSIGN(HArraySet); 1698}; 1699 1700class HArrayLength : public HExpression<1> { 1701 public: 1702 explicit HArrayLength(HInstruction* array) 1703 : HExpression(Primitive::kPrimInt, SideEffects::None()) { 1704 // Note that arrays do not change length, so the instruction does not 1705 // depend on any write. 1706 SetRawInputAt(0, array); 1707 } 1708 1709 virtual bool CanBeMoved() const { return true; } 1710 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1711 1712 DECLARE_INSTRUCTION(ArrayLength); 1713 1714 private: 1715 DISALLOW_COPY_AND_ASSIGN(HArrayLength); 1716}; 1717 1718class HBoundsCheck : public HExpression<2> { 1719 public: 1720 HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc) 1721 : HExpression(index->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 1722 DCHECK(index->GetType() == Primitive::kPrimInt); 1723 SetRawInputAt(0, index); 1724 SetRawInputAt(1, length); 1725 } 1726 1727 virtual bool CanBeMoved() const { return true; } 1728 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1729 1730 virtual bool NeedsEnvironment() const { return true; } 1731 1732 uint32_t GetDexPc() const { return dex_pc_; } 1733 1734 DECLARE_INSTRUCTION(BoundsCheck); 1735 1736 private: 1737 const uint32_t dex_pc_; 1738 1739 DISALLOW_COPY_AND_ASSIGN(HBoundsCheck); 1740}; 1741 1742/** 1743 * Some DEX instructions are folded into multiple HInstructions that need 1744 * to stay live until the last HInstruction. This class 1745 * is used as a marker for the baseline compiler to ensure its preceding 1746 * HInstruction stays live. `index` is the temporary number that is used 1747 * for knowing the stack offset where to store the instruction. 1748 */ 1749class HTemporary : public HTemplateInstruction<0> { 1750 public: 1751 explicit HTemporary(size_t index) : HTemplateInstruction(SideEffects::None()), index_(index) {} 1752 1753 size_t GetIndex() const { return index_; } 1754 1755 DECLARE_INSTRUCTION(Temporary); 1756 1757 private: 1758 const size_t index_; 1759 1760 DISALLOW_COPY_AND_ASSIGN(HTemporary); 1761}; 1762 1763class HSuspendCheck : public HTemplateInstruction<0> { 1764 public: 1765 explicit HSuspendCheck(uint32_t dex_pc) 1766 : HTemplateInstruction(SideEffects::ChangesSomething()), dex_pc_(dex_pc) {} 1767 1768 virtual bool NeedsEnvironment() const { 1769 return true; 1770 } 1771 1772 uint32_t GetDexPc() const { return dex_pc_; } 1773 1774 DECLARE_INSTRUCTION(SuspendCheck); 1775 1776 private: 1777 const uint32_t dex_pc_; 1778 1779 DISALLOW_COPY_AND_ASSIGN(HSuspendCheck); 1780}; 1781 1782class MoveOperands : public ArenaObject { 1783 public: 1784 MoveOperands(Location source, Location destination) 1785 : source_(source), destination_(destination) {} 1786 1787 Location GetSource() const { return source_; } 1788 Location GetDestination() const { return destination_; } 1789 1790 void SetSource(Location value) { source_ = value; } 1791 void SetDestination(Location value) { destination_ = value; } 1792 1793 // The parallel move resolver marks moves as "in-progress" by clearing the 1794 // destination (but not the source). 1795 Location MarkPending() { 1796 DCHECK(!IsPending()); 1797 Location dest = destination_; 1798 destination_ = Location::NoLocation(); 1799 return dest; 1800 } 1801 1802 void ClearPending(Location dest) { 1803 DCHECK(IsPending()); 1804 destination_ = dest; 1805 } 1806 1807 bool IsPending() const { 1808 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 1809 return destination_.IsInvalid() && !source_.IsInvalid(); 1810 } 1811 1812 // True if this blocks a move from the given location. 1813 bool Blocks(Location loc) const { 1814 return !IsEliminated() && source_.Equals(loc); 1815 } 1816 1817 // A move is redundant if it's been eliminated, if its source and 1818 // destination are the same, or if its destination is unneeded. 1819 bool IsRedundant() const { 1820 return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_); 1821 } 1822 1823 // We clear both operands to indicate move that's been eliminated. 1824 void Eliminate() { 1825 source_ = destination_ = Location::NoLocation(); 1826 } 1827 1828 bool IsEliminated() const { 1829 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 1830 return source_.IsInvalid(); 1831 } 1832 1833 private: 1834 Location source_; 1835 Location destination_; 1836 1837 DISALLOW_COPY_AND_ASSIGN(MoveOperands); 1838}; 1839 1840static constexpr size_t kDefaultNumberOfMoves = 4; 1841 1842class HParallelMove : public HTemplateInstruction<0> { 1843 public: 1844 explicit HParallelMove(ArenaAllocator* arena) 1845 : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {} 1846 1847 void AddMove(MoveOperands* move) { 1848 moves_.Add(move); 1849 } 1850 1851 MoveOperands* MoveOperandsAt(size_t index) const { 1852 return moves_.Get(index); 1853 } 1854 1855 size_t NumMoves() const { return moves_.Size(); } 1856 1857 DECLARE_INSTRUCTION(ParallelMove); 1858 1859 private: 1860 GrowableArray<MoveOperands*> moves_; 1861 1862 DISALLOW_COPY_AND_ASSIGN(HParallelMove); 1863}; 1864 1865class HGraphVisitor : public ValueObject { 1866 public: 1867 explicit HGraphVisitor(HGraph* graph) : graph_(graph) {} 1868 virtual ~HGraphVisitor() {} 1869 1870 virtual void VisitInstruction(HInstruction* instruction) {} 1871 virtual void VisitBasicBlock(HBasicBlock* block); 1872 1873 void VisitInsertionOrder(); 1874 1875 HGraph* GetGraph() const { return graph_; } 1876 1877 // Visit functions for instruction classes. 1878#define DECLARE_VISIT_INSTRUCTION(name) \ 1879 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } 1880 1881 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 1882 1883#undef DECLARE_VISIT_INSTRUCTION 1884 1885 private: 1886 HGraph* graph_; 1887 1888 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); 1889}; 1890 1891class HInsertionOrderIterator : public ValueObject { 1892 public: 1893 explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 1894 1895 bool Done() const { return index_ == graph_.GetBlocks().Size(); } 1896 HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); } 1897 void Advance() { ++index_; } 1898 1899 private: 1900 const HGraph& graph_; 1901 size_t index_; 1902 1903 DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator); 1904}; 1905 1906class HReversePostOrderIterator : public ValueObject { 1907 public: 1908 explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 1909 1910 bool Done() const { return index_ == graph_.GetReversePostOrder().Size(); } 1911 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_); } 1912 void Advance() { ++index_; } 1913 1914 private: 1915 const HGraph& graph_; 1916 size_t index_; 1917 1918 DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator); 1919}; 1920 1921class HPostOrderIterator : public ValueObject { 1922 public: 1923 explicit HPostOrderIterator(const HGraph& graph) 1924 : graph_(graph), index_(graph_.GetReversePostOrder().Size()) {} 1925 1926 bool Done() const { return index_ == 0; } 1927 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_ - 1); } 1928 void Advance() { --index_; } 1929 1930 private: 1931 const HGraph& graph_; 1932 size_t index_; 1933 1934 DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); 1935}; 1936 1937} // namespace art 1938 1939#endif // ART_COMPILER_OPTIMIZING_NODES_H_ 1940