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