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