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