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