nodes.h revision 19a19cffd197a28ae4c9c3e59eff6352fd392241
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(LoadClass, Instruction) \ 493 M(LessThan, Condition) \ 494 M(LessThanOrEqual, Condition) \ 495 M(LoadLocal, Instruction) \ 496 M(Local, Instruction) \ 497 M(LongConstant, Constant) \ 498 M(Mul, BinaryOperation) \ 499 M(Neg, UnaryOperation) \ 500 M(NewArray, Instruction) \ 501 M(NewInstance, Instruction) \ 502 M(Not, UnaryOperation) \ 503 M(NotEqual, Condition) \ 504 M(NullCheck, Instruction) \ 505 M(ParallelMove, Instruction) \ 506 M(ParameterValue, Instruction) \ 507 M(Phi, Instruction) \ 508 M(Return, Instruction) \ 509 M(ReturnVoid, Instruction) \ 510 M(StaticFieldGet, Instruction) \ 511 M(StaticFieldSet, Instruction) \ 512 M(StoreLocal, Instruction) \ 513 M(Sub, BinaryOperation) \ 514 M(SuspendCheck, Instruction) \ 515 M(Temporary, Instruction) \ 516 517#define FOR_EACH_INSTRUCTION(M) \ 518 FOR_EACH_CONCRETE_INSTRUCTION(M) \ 519 M(Constant, Instruction) \ 520 M(UnaryOperation, Instruction) \ 521 M(BinaryOperation, Instruction) \ 522 M(Invoke, Instruction) 523 524#define FORWARD_DECLARATION(type, super) class H##type; 525FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) 526#undef FORWARD_DECLARATION 527 528#define DECLARE_INSTRUCTION(type) \ 529 virtual InstructionKind GetKind() const { return k##type; } \ 530 virtual const char* DebugName() const { return #type; } \ 531 virtual const H##type* As##type() const OVERRIDE { return this; } \ 532 virtual H##type* As##type() OVERRIDE { return this; } \ 533 virtual bool InstructionTypeEquals(HInstruction* other) const { \ 534 return other->Is##type(); \ 535 } \ 536 virtual void Accept(HGraphVisitor* visitor) 537 538template <typename T> 539class HUseListNode : public ArenaObject { 540 public: 541 HUseListNode(T* user, size_t index, HUseListNode* tail) 542 : user_(user), index_(index), tail_(tail) {} 543 544 HUseListNode* GetTail() const { return tail_; } 545 T* GetUser() const { return user_; } 546 size_t GetIndex() const { return index_; } 547 548 void SetTail(HUseListNode<T>* node) { tail_ = node; } 549 550 private: 551 T* const user_; 552 const size_t index_; 553 HUseListNode<T>* tail_; 554 555 DISALLOW_COPY_AND_ASSIGN(HUseListNode); 556}; 557 558// Represents the side effects an instruction may have. 559class SideEffects : public ValueObject { 560 public: 561 SideEffects() : flags_(0) {} 562 563 static SideEffects None() { 564 return SideEffects(0); 565 } 566 567 static SideEffects All() { 568 return SideEffects(ChangesSomething().flags_ | DependsOnSomething().flags_); 569 } 570 571 static SideEffects ChangesSomething() { 572 return SideEffects((1 << kFlagChangesCount) - 1); 573 } 574 575 static SideEffects DependsOnSomething() { 576 int count = kFlagDependsOnCount - kFlagChangesCount; 577 return SideEffects(((1 << count) - 1) << kFlagChangesCount); 578 } 579 580 SideEffects Union(SideEffects other) const { 581 return SideEffects(flags_ | other.flags_); 582 } 583 584 bool HasSideEffects() const { 585 size_t all_bits_set = (1 << kFlagChangesCount) - 1; 586 return (flags_ & all_bits_set) != 0; 587 } 588 589 bool HasAllSideEffects() const { 590 size_t all_bits_set = (1 << kFlagChangesCount) - 1; 591 return all_bits_set == (flags_ & all_bits_set); 592 } 593 594 bool DependsOn(SideEffects other) const { 595 size_t depends_flags = other.ComputeDependsFlags(); 596 return (flags_ & depends_flags) != 0; 597 } 598 599 bool HasDependencies() const { 600 int count = kFlagDependsOnCount - kFlagChangesCount; 601 size_t all_bits_set = (1 << count) - 1; 602 return ((flags_ >> kFlagChangesCount) & all_bits_set) != 0; 603 } 604 605 private: 606 static constexpr int kFlagChangesSomething = 0; 607 static constexpr int kFlagChangesCount = kFlagChangesSomething + 1; 608 609 static constexpr int kFlagDependsOnSomething = kFlagChangesCount; 610 static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1; 611 612 explicit SideEffects(size_t flags) : flags_(flags) {} 613 614 size_t ComputeDependsFlags() const { 615 return flags_ << kFlagChangesCount; 616 } 617 618 size_t flags_; 619}; 620 621class HInstruction : public ArenaObject { 622 public: 623 explicit HInstruction(SideEffects side_effects) 624 : previous_(nullptr), 625 next_(nullptr), 626 block_(nullptr), 627 id_(-1), 628 ssa_index_(-1), 629 uses_(nullptr), 630 env_uses_(nullptr), 631 environment_(nullptr), 632 locations_(nullptr), 633 live_interval_(nullptr), 634 lifetime_position_(kNoLifetime), 635 side_effects_(side_effects) {} 636 637 virtual ~HInstruction() {} 638 639#define DECLARE_KIND(type, super) k##type, 640 enum InstructionKind { 641 FOR_EACH_INSTRUCTION(DECLARE_KIND) 642 }; 643#undef DECLARE_KIND 644 645 HInstruction* GetNext() const { return next_; } 646 HInstruction* GetPrevious() const { return previous_; } 647 648 HBasicBlock* GetBlock() const { return block_; } 649 void SetBlock(HBasicBlock* block) { block_ = block; } 650 bool IsInBlock() const { return block_ != nullptr; } 651 bool IsInLoop() const { return block_->IsInLoop(); } 652 bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); } 653 654 virtual size_t InputCount() const = 0; 655 virtual HInstruction* InputAt(size_t i) const = 0; 656 657 virtual void Accept(HGraphVisitor* visitor) = 0; 658 virtual const char* DebugName() const = 0; 659 660 virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; } 661 virtual void SetRawInputAt(size_t index, HInstruction* input) = 0; 662 663 virtual bool NeedsEnvironment() const { return false; } 664 virtual bool IsControlFlow() const { return false; } 665 virtual bool CanThrow() const { return false; } 666 bool HasSideEffects() const { return side_effects_.HasSideEffects(); } 667 668 void AddUseAt(HInstruction* user, size_t index) { 669 uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HInstruction>(user, index, uses_); 670 } 671 672 void AddEnvUseAt(HEnvironment* user, size_t index) { 673 DCHECK(user != nullptr); 674 env_uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HEnvironment>( 675 user, index, env_uses_); 676 } 677 678 void RemoveUser(HInstruction* user, size_t index); 679 void RemoveEnvironmentUser(HEnvironment* user, size_t index); 680 681 HUseListNode<HInstruction>* GetUses() const { return uses_; } 682 HUseListNode<HEnvironment>* GetEnvUses() const { return env_uses_; } 683 684 bool HasUses() const { return uses_ != nullptr || env_uses_ != nullptr; } 685 bool HasEnvironmentUses() const { return env_uses_ != nullptr; } 686 687 size_t NumberOfUses() const { 688 // TODO: Optimize this method if it is used outside of the HGraphVisualizer. 689 size_t result = 0; 690 HUseListNode<HInstruction>* current = uses_; 691 while (current != nullptr) { 692 current = current->GetTail(); 693 ++result; 694 } 695 return result; 696 } 697 698 // Does this instruction strictly dominate `other_instruction`? 699 // Returns false if this instruction and `other_instruction` are the same. 700 // Aborts if this instruction and `other_instruction` are both phis. 701 bool StrictlyDominates(HInstruction* other_instruction) const; 702 703 int GetId() const { return id_; } 704 void SetId(int id) { id_ = id; } 705 706 int GetSsaIndex() const { return ssa_index_; } 707 void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; } 708 bool HasSsaIndex() const { return ssa_index_ != -1; } 709 710 bool HasEnvironment() const { return environment_ != nullptr; } 711 HEnvironment* GetEnvironment() const { return environment_; } 712 void SetEnvironment(HEnvironment* environment) { environment_ = environment; } 713 714 // Returns the number of entries in the environment. Typically, that is the 715 // number of dex registers in a method. It could be more in case of inlining. 716 size_t EnvironmentSize() const; 717 718 LocationSummary* GetLocations() const { return locations_; } 719 void SetLocations(LocationSummary* locations) { locations_ = locations; } 720 721 void ReplaceWith(HInstruction* instruction); 722 void ReplaceInput(HInstruction* replacement, size_t index); 723 724 bool HasOnlyOneUse() const { 725 return uses_ != nullptr && uses_->GetTail() == nullptr; 726 } 727 728#define INSTRUCTION_TYPE_CHECK(type, super) \ 729 bool Is##type() const { return (As##type() != nullptr); } \ 730 virtual const H##type* As##type() const { return nullptr; } \ 731 virtual H##type* As##type() { return nullptr; } 732 733 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 734#undef INSTRUCTION_TYPE_CHECK 735 736 // Returns whether the instruction can be moved within the graph. 737 virtual bool CanBeMoved() const { return false; } 738 739 // Returns whether the two instructions are of the same kind. 740 virtual bool InstructionTypeEquals(HInstruction* other) const { return false; } 741 742 // Returns whether any data encoded in the two instructions is equal. 743 // This method does not look at the inputs. Both instructions must be 744 // of the same type, otherwise the method has undefined behavior. 745 virtual bool InstructionDataEquals(HInstruction* other) const { return false; } 746 747 // Returns whether two instructions are equal, that is: 748 // 1) They have the same type and contain the same data, 749 // 2) Their inputs are identical. 750 bool Equals(HInstruction* other) const; 751 752 virtual InstructionKind GetKind() const = 0; 753 754 virtual size_t ComputeHashCode() const { 755 size_t result = GetKind(); 756 for (size_t i = 0, e = InputCount(); i < e; ++i) { 757 result = (result * 31) + InputAt(i)->GetId(); 758 } 759 return result; 760 } 761 762 SideEffects GetSideEffects() const { return side_effects_; } 763 764 size_t GetLifetimePosition() const { return lifetime_position_; } 765 void SetLifetimePosition(size_t position) { lifetime_position_ = position; } 766 LiveInterval* GetLiveInterval() const { return live_interval_; } 767 void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; } 768 bool HasLiveInterval() const { return live_interval_ != nullptr; } 769 770 private: 771 HInstruction* previous_; 772 HInstruction* next_; 773 HBasicBlock* block_; 774 775 // An instruction gets an id when it is added to the graph. 776 // It reflects creation order. A negative id means the instruction 777 // has not been added to the graph. 778 int id_; 779 780 // When doing liveness analysis, instructions that have uses get an SSA index. 781 int ssa_index_; 782 783 // List of instructions that have this instruction as input. 784 HUseListNode<HInstruction>* uses_; 785 786 // List of environments that contain this instruction. 787 HUseListNode<HEnvironment>* env_uses_; 788 789 // The environment associated with this instruction. Not null if the instruction 790 // might jump out of the method. 791 HEnvironment* environment_; 792 793 // Set by the code generator. 794 LocationSummary* locations_; 795 796 // Set by the liveness analysis. 797 LiveInterval* live_interval_; 798 799 // Set by the liveness analysis, this is the position in a linear 800 // order of blocks where this instruction's live interval start. 801 size_t lifetime_position_; 802 803 const SideEffects side_effects_; 804 805 friend class HBasicBlock; 806 friend class HInstructionList; 807 808 DISALLOW_COPY_AND_ASSIGN(HInstruction); 809}; 810 811template<typename T> 812class HUseIterator : public ValueObject { 813 public: 814 explicit HUseIterator(HUseListNode<T>* uses) : current_(uses) {} 815 816 bool Done() const { return current_ == nullptr; } 817 818 void Advance() { 819 DCHECK(!Done()); 820 current_ = current_->GetTail(); 821 } 822 823 HUseListNode<T>* Current() const { 824 DCHECK(!Done()); 825 return current_; 826 } 827 828 private: 829 HUseListNode<T>* current_; 830 831 friend class HValue; 832}; 833 834// A HEnvironment object contains the values of virtual registers at a given location. 835class HEnvironment : public ArenaObject { 836 public: 837 HEnvironment(ArenaAllocator* arena, size_t number_of_vregs) : vregs_(arena, number_of_vregs) { 838 vregs_.SetSize(number_of_vregs); 839 for (size_t i = 0; i < number_of_vregs; i++) { 840 vregs_.Put(i, nullptr); 841 } 842 } 843 844 void Populate(const GrowableArray<HInstruction*>& env) { 845 for (size_t i = 0; i < env.Size(); i++) { 846 HInstruction* instruction = env.Get(i); 847 vregs_.Put(i, instruction); 848 if (instruction != nullptr) { 849 instruction->AddEnvUseAt(this, i); 850 } 851 } 852 } 853 854 void SetRawEnvAt(size_t index, HInstruction* instruction) { 855 vregs_.Put(index, instruction); 856 } 857 858 HInstruction* GetInstructionAt(size_t index) const { 859 return vregs_.Get(index); 860 } 861 862 GrowableArray<HInstruction*>* GetVRegs() { 863 return &vregs_; 864 } 865 866 size_t Size() const { return vregs_.Size(); } 867 868 private: 869 GrowableArray<HInstruction*> vregs_; 870 871 DISALLOW_COPY_AND_ASSIGN(HEnvironment); 872}; 873 874class HInputIterator : public ValueObject { 875 public: 876 explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {} 877 878 bool Done() const { return index_ == instruction_->InputCount(); } 879 HInstruction* Current() const { return instruction_->InputAt(index_); } 880 void Advance() { index_++; } 881 882 private: 883 HInstruction* instruction_; 884 size_t index_; 885 886 DISALLOW_COPY_AND_ASSIGN(HInputIterator); 887}; 888 889class HInstructionIterator : public ValueObject { 890 public: 891 explicit HInstructionIterator(const HInstructionList& instructions) 892 : instruction_(instructions.first_instruction_) { 893 next_ = Done() ? nullptr : instruction_->GetNext(); 894 } 895 896 bool Done() const { return instruction_ == nullptr; } 897 HInstruction* Current() const { return instruction_; } 898 void Advance() { 899 instruction_ = next_; 900 next_ = Done() ? nullptr : instruction_->GetNext(); 901 } 902 903 private: 904 HInstruction* instruction_; 905 HInstruction* next_; 906 907 DISALLOW_COPY_AND_ASSIGN(HInstructionIterator); 908}; 909 910class HBackwardInstructionIterator : public ValueObject { 911 public: 912 explicit HBackwardInstructionIterator(const HInstructionList& instructions) 913 : instruction_(instructions.last_instruction_) { 914 next_ = Done() ? nullptr : instruction_->GetPrevious(); 915 } 916 917 bool Done() const { return instruction_ == nullptr; } 918 HInstruction* Current() const { return instruction_; } 919 void Advance() { 920 instruction_ = next_; 921 next_ = Done() ? nullptr : instruction_->GetPrevious(); 922 } 923 924 private: 925 HInstruction* instruction_; 926 HInstruction* next_; 927 928 DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator); 929}; 930 931// An embedded container with N elements of type T. Used (with partial 932// specialization for N=0) because embedded arrays cannot have size 0. 933template<typename T, intptr_t N> 934class EmbeddedArray { 935 public: 936 EmbeddedArray() : elements_() {} 937 938 intptr_t GetLength() const { return N; } 939 940 const T& operator[](intptr_t i) const { 941 DCHECK_LT(i, GetLength()); 942 return elements_[i]; 943 } 944 945 T& operator[](intptr_t i) { 946 DCHECK_LT(i, GetLength()); 947 return elements_[i]; 948 } 949 950 const T& At(intptr_t i) const { 951 return (*this)[i]; 952 } 953 954 void SetAt(intptr_t i, const T& val) { 955 (*this)[i] = val; 956 } 957 958 private: 959 T elements_[N]; 960}; 961 962template<typename T> 963class EmbeddedArray<T, 0> { 964 public: 965 intptr_t length() const { return 0; } 966 const T& operator[](intptr_t i) const { 967 LOG(FATAL) << "Unreachable"; 968 static T sentinel = 0; 969 return sentinel; 970 } 971 T& operator[](intptr_t i) { 972 LOG(FATAL) << "Unreachable"; 973 static T sentinel = 0; 974 return sentinel; 975 } 976}; 977 978template<intptr_t N> 979class HTemplateInstruction: public HInstruction { 980 public: 981 HTemplateInstruction<N>(SideEffects side_effects) 982 : HInstruction(side_effects), inputs_() {} 983 virtual ~HTemplateInstruction() {} 984 985 virtual size_t InputCount() const { return N; } 986 virtual HInstruction* InputAt(size_t i) const { return inputs_[i]; } 987 988 protected: 989 virtual void SetRawInputAt(size_t i, HInstruction* instruction) { 990 inputs_[i] = instruction; 991 } 992 993 private: 994 EmbeddedArray<HInstruction*, N> inputs_; 995 996 friend class SsaBuilder; 997}; 998 999template<intptr_t N> 1000class HExpression : public HTemplateInstruction<N> { 1001 public: 1002 HExpression<N>(Primitive::Type type, SideEffects side_effects) 1003 : HTemplateInstruction<N>(side_effects), type_(type) {} 1004 virtual ~HExpression() {} 1005 1006 virtual Primitive::Type GetType() const { return type_; } 1007 1008 protected: 1009 Primitive::Type type_; 1010}; 1011 1012// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow 1013// instruction that branches to the exit block. 1014class HReturnVoid : public HTemplateInstruction<0> { 1015 public: 1016 HReturnVoid() : HTemplateInstruction(SideEffects::None()) {} 1017 1018 virtual bool IsControlFlow() const { return true; } 1019 1020 DECLARE_INSTRUCTION(ReturnVoid); 1021 1022 private: 1023 DISALLOW_COPY_AND_ASSIGN(HReturnVoid); 1024}; 1025 1026// Represents dex's RETURN opcodes. A HReturn is a control flow 1027// instruction that branches to the exit block. 1028class HReturn : public HTemplateInstruction<1> { 1029 public: 1030 explicit HReturn(HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 1031 SetRawInputAt(0, value); 1032 } 1033 1034 virtual bool IsControlFlow() const { return true; } 1035 1036 DECLARE_INSTRUCTION(Return); 1037 1038 private: 1039 DISALLOW_COPY_AND_ASSIGN(HReturn); 1040}; 1041 1042// The exit instruction is the only instruction of the exit block. 1043// Instructions aborting the method (HTrow and HReturn) must branch to the 1044// exit block. 1045class HExit : public HTemplateInstruction<0> { 1046 public: 1047 HExit() : HTemplateInstruction(SideEffects::None()) {} 1048 1049 virtual bool IsControlFlow() const { return true; } 1050 1051 DECLARE_INSTRUCTION(Exit); 1052 1053 private: 1054 DISALLOW_COPY_AND_ASSIGN(HExit); 1055}; 1056 1057// Jumps from one block to another. 1058class HGoto : public HTemplateInstruction<0> { 1059 public: 1060 HGoto() : HTemplateInstruction(SideEffects::None()) {} 1061 1062 virtual bool IsControlFlow() const { return true; } 1063 1064 HBasicBlock* GetSuccessor() const { 1065 return GetBlock()->GetSuccessors().Get(0); 1066 } 1067 1068 DECLARE_INSTRUCTION(Goto); 1069 1070 private: 1071 DISALLOW_COPY_AND_ASSIGN(HGoto); 1072}; 1073 1074 1075// Conditional branch. A block ending with an HIf instruction must have 1076// two successors. 1077class HIf : public HTemplateInstruction<1> { 1078 public: 1079 explicit HIf(HInstruction* input) : HTemplateInstruction(SideEffects::None()) { 1080 SetRawInputAt(0, input); 1081 } 1082 1083 virtual bool IsControlFlow() const { return true; } 1084 1085 HBasicBlock* IfTrueSuccessor() const { 1086 return GetBlock()->GetSuccessors().Get(0); 1087 } 1088 1089 HBasicBlock* IfFalseSuccessor() const { 1090 return GetBlock()->GetSuccessors().Get(1); 1091 } 1092 1093 DECLARE_INSTRUCTION(If); 1094 1095 virtual bool IsIfInstruction() const { return true; } 1096 1097 private: 1098 DISALLOW_COPY_AND_ASSIGN(HIf); 1099}; 1100 1101class HUnaryOperation : public HExpression<1> { 1102 public: 1103 HUnaryOperation(Primitive::Type result_type, HInstruction* input) 1104 : HExpression(result_type, SideEffects::None()) { 1105 SetRawInputAt(0, input); 1106 } 1107 1108 HInstruction* GetInput() const { return InputAt(0); } 1109 Primitive::Type GetResultType() const { return GetType(); } 1110 1111 virtual bool CanBeMoved() const { return true; } 1112 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1113 1114 // Try to statically evaluate `operation` and return a HConstant 1115 // containing the result of this evaluation. If `operation` cannot 1116 // be evaluated as a constant, return nullptr. 1117 HConstant* TryStaticEvaluation() const; 1118 1119 // Apply this operation to `x`. 1120 virtual int32_t Evaluate(int32_t x) const = 0; 1121 virtual int64_t Evaluate(int64_t x) const = 0; 1122 1123 DECLARE_INSTRUCTION(UnaryOperation); 1124 1125 private: 1126 DISALLOW_COPY_AND_ASSIGN(HUnaryOperation); 1127}; 1128 1129class HBinaryOperation : public HExpression<2> { 1130 public: 1131 HBinaryOperation(Primitive::Type result_type, 1132 HInstruction* left, 1133 HInstruction* right) : HExpression(result_type, SideEffects::None()) { 1134 SetRawInputAt(0, left); 1135 SetRawInputAt(1, right); 1136 } 1137 1138 HInstruction* GetLeft() const { return InputAt(0); } 1139 HInstruction* GetRight() const { return InputAt(1); } 1140 Primitive::Type GetResultType() const { return GetType(); } 1141 1142 virtual bool IsCommutative() { return false; } 1143 1144 virtual bool CanBeMoved() const { return true; } 1145 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1146 1147 // Try to statically evaluate `operation` and return a HConstant 1148 // containing the result of this evaluation. If `operation` cannot 1149 // be evaluated as a constant, return nullptr. 1150 HConstant* TryStaticEvaluation() const; 1151 1152 // Apply this operation to `x` and `y`. 1153 virtual int32_t Evaluate(int32_t x, int32_t y) const = 0; 1154 virtual int64_t Evaluate(int64_t x, int64_t y) const = 0; 1155 1156 DECLARE_INSTRUCTION(BinaryOperation); 1157 1158 private: 1159 DISALLOW_COPY_AND_ASSIGN(HBinaryOperation); 1160}; 1161 1162class HCondition : public HBinaryOperation { 1163 public: 1164 HCondition(HInstruction* first, HInstruction* second) 1165 : HBinaryOperation(Primitive::kPrimBoolean, first, second), 1166 needs_materialization_(true) {} 1167 1168 virtual bool IsCommutative() { return true; } 1169 1170 bool NeedsMaterialization() const { return needs_materialization_; } 1171 void ClearNeedsMaterialization() { needs_materialization_ = false; } 1172 1173 // For code generation purposes, returns whether this instruction is just before 1174 // `if_`, and disregard moves in between. 1175 bool IsBeforeWhenDisregardMoves(HIf* if_) const; 1176 1177 DECLARE_INSTRUCTION(Condition); 1178 1179 virtual IfCondition GetCondition() const = 0; 1180 1181 private: 1182 // For register allocation purposes, returns whether this instruction needs to be 1183 // materialized (that is, not just be in the processor flags). 1184 bool needs_materialization_; 1185 1186 DISALLOW_COPY_AND_ASSIGN(HCondition); 1187}; 1188 1189// Instruction to check if two inputs are equal to each other. 1190class HEqual : public HCondition { 1191 public: 1192 HEqual(HInstruction* first, HInstruction* second) 1193 : HCondition(first, second) {} 1194 1195 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1196 return x == y ? 1 : 0; 1197 } 1198 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1199 return x == y ? 1 : 0; 1200 } 1201 1202 DECLARE_INSTRUCTION(Equal); 1203 1204 virtual IfCondition GetCondition() const { 1205 return kCondEQ; 1206 } 1207 1208 private: 1209 DISALLOW_COPY_AND_ASSIGN(HEqual); 1210}; 1211 1212class HNotEqual : public HCondition { 1213 public: 1214 HNotEqual(HInstruction* first, HInstruction* second) 1215 : HCondition(first, second) {} 1216 1217 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1218 return x != y ? 1 : 0; 1219 } 1220 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1221 return x != y ? 1 : 0; 1222 } 1223 1224 DECLARE_INSTRUCTION(NotEqual); 1225 1226 virtual IfCondition GetCondition() const { 1227 return kCondNE; 1228 } 1229 1230 private: 1231 DISALLOW_COPY_AND_ASSIGN(HNotEqual); 1232}; 1233 1234class HLessThan : public HCondition { 1235 public: 1236 HLessThan(HInstruction* first, HInstruction* second) 1237 : HCondition(first, second) {} 1238 1239 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1240 return x < y ? 1 : 0; 1241 } 1242 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1243 return x < y ? 1 : 0; 1244 } 1245 1246 DECLARE_INSTRUCTION(LessThan); 1247 1248 virtual IfCondition GetCondition() const { 1249 return kCondLT; 1250 } 1251 1252 private: 1253 DISALLOW_COPY_AND_ASSIGN(HLessThan); 1254}; 1255 1256class HLessThanOrEqual : public HCondition { 1257 public: 1258 HLessThanOrEqual(HInstruction* first, HInstruction* second) 1259 : HCondition(first, second) {} 1260 1261 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1262 return x <= y ? 1 : 0; 1263 } 1264 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1265 return x <= y ? 1 : 0; 1266 } 1267 1268 DECLARE_INSTRUCTION(LessThanOrEqual); 1269 1270 virtual IfCondition GetCondition() const { 1271 return kCondLE; 1272 } 1273 1274 private: 1275 DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual); 1276}; 1277 1278class HGreaterThan : public HCondition { 1279 public: 1280 HGreaterThan(HInstruction* first, HInstruction* second) 1281 : HCondition(first, second) {} 1282 1283 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1284 return x > y ? 1 : 0; 1285 } 1286 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1287 return x > y ? 1 : 0; 1288 } 1289 1290 DECLARE_INSTRUCTION(GreaterThan); 1291 1292 virtual IfCondition GetCondition() const { 1293 return kCondGT; 1294 } 1295 1296 private: 1297 DISALLOW_COPY_AND_ASSIGN(HGreaterThan); 1298}; 1299 1300class HGreaterThanOrEqual : public HCondition { 1301 public: 1302 HGreaterThanOrEqual(HInstruction* first, HInstruction* second) 1303 : HCondition(first, second) {} 1304 1305 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1306 return x >= y ? 1 : 0; 1307 } 1308 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1309 return x >= y ? 1 : 0; 1310 } 1311 1312 DECLARE_INSTRUCTION(GreaterThanOrEqual); 1313 1314 virtual IfCondition GetCondition() const { 1315 return kCondGE; 1316 } 1317 1318 private: 1319 DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual); 1320}; 1321 1322 1323// Instruction to check how two inputs compare to each other. 1324// Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1. 1325class HCompare : public HBinaryOperation { 1326 public: 1327 HCompare(Primitive::Type type, HInstruction* first, HInstruction* second) 1328 : HBinaryOperation(Primitive::kPrimInt, first, second) { 1329 DCHECK_EQ(type, first->GetType()); 1330 DCHECK_EQ(type, second->GetType()); 1331 } 1332 1333 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1334 return 1335 x == y ? 0 : 1336 x > y ? 1 : 1337 -1; 1338 } 1339 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1340 return 1341 x == y ? 0 : 1342 x > y ? 1 : 1343 -1; 1344 } 1345 1346 DECLARE_INSTRUCTION(Compare); 1347 1348 private: 1349 DISALLOW_COPY_AND_ASSIGN(HCompare); 1350}; 1351 1352// A local in the graph. Corresponds to a Dex register. 1353class HLocal : public HTemplateInstruction<0> { 1354 public: 1355 explicit HLocal(uint16_t reg_number) 1356 : HTemplateInstruction(SideEffects::None()), reg_number_(reg_number) {} 1357 1358 DECLARE_INSTRUCTION(Local); 1359 1360 uint16_t GetRegNumber() const { return reg_number_; } 1361 1362 private: 1363 // The Dex register number. 1364 const uint16_t reg_number_; 1365 1366 DISALLOW_COPY_AND_ASSIGN(HLocal); 1367}; 1368 1369// Load a given local. The local is an input of this instruction. 1370class HLoadLocal : public HExpression<1> { 1371 public: 1372 HLoadLocal(HLocal* local, Primitive::Type type) 1373 : HExpression(type, SideEffects::None()) { 1374 SetRawInputAt(0, local); 1375 } 1376 1377 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 1378 1379 DECLARE_INSTRUCTION(LoadLocal); 1380 1381 private: 1382 DISALLOW_COPY_AND_ASSIGN(HLoadLocal); 1383}; 1384 1385// Store a value in a given local. This instruction has two inputs: the value 1386// and the local. 1387class HStoreLocal : public HTemplateInstruction<2> { 1388 public: 1389 HStoreLocal(HLocal* local, HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 1390 SetRawInputAt(0, local); 1391 SetRawInputAt(1, value); 1392 } 1393 1394 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 1395 1396 DECLARE_INSTRUCTION(StoreLocal); 1397 1398 private: 1399 DISALLOW_COPY_AND_ASSIGN(HStoreLocal); 1400}; 1401 1402class HConstant : public HExpression<0> { 1403 public: 1404 explicit HConstant(Primitive::Type type) : HExpression(type, SideEffects::None()) {} 1405 1406 virtual bool CanBeMoved() const { return true; } 1407 1408 DECLARE_INSTRUCTION(Constant); 1409 1410 private: 1411 DISALLOW_COPY_AND_ASSIGN(HConstant); 1412}; 1413 1414class HFloatConstant : public HConstant { 1415 public: 1416 explicit HFloatConstant(float value) : HConstant(Primitive::kPrimFloat), value_(value) {} 1417 1418 float GetValue() const { return value_; } 1419 1420 virtual bool InstructionDataEquals(HInstruction* other) const { 1421 return bit_cast<float, int32_t>(other->AsFloatConstant()->value_) == 1422 bit_cast<float, int32_t>(value_); 1423 } 1424 1425 virtual size_t ComputeHashCode() const { return static_cast<size_t>(GetValue()); } 1426 1427 DECLARE_INSTRUCTION(FloatConstant); 1428 1429 private: 1430 const float value_; 1431 1432 DISALLOW_COPY_AND_ASSIGN(HFloatConstant); 1433}; 1434 1435class HDoubleConstant : public HConstant { 1436 public: 1437 explicit HDoubleConstant(double value) : HConstant(Primitive::kPrimDouble), value_(value) {} 1438 1439 double GetValue() const { return value_; } 1440 1441 virtual bool InstructionDataEquals(HInstruction* other) const { 1442 return bit_cast<double, int64_t>(other->AsDoubleConstant()->value_) == 1443 bit_cast<double, int64_t>(value_); 1444 } 1445 1446 virtual size_t ComputeHashCode() const { return static_cast<size_t>(GetValue()); } 1447 1448 DECLARE_INSTRUCTION(DoubleConstant); 1449 1450 private: 1451 const double value_; 1452 1453 DISALLOW_COPY_AND_ASSIGN(HDoubleConstant); 1454}; 1455 1456// Constants of the type int. Those can be from Dex instructions, or 1457// synthesized (for example with the if-eqz instruction). 1458class HIntConstant : public HConstant { 1459 public: 1460 explicit HIntConstant(int32_t value) : HConstant(Primitive::kPrimInt), value_(value) {} 1461 1462 int32_t GetValue() const { return value_; } 1463 1464 virtual bool InstructionDataEquals(HInstruction* other) const { 1465 return other->AsIntConstant()->value_ == value_; 1466 } 1467 1468 virtual size_t ComputeHashCode() const { return GetValue(); } 1469 1470 DECLARE_INSTRUCTION(IntConstant); 1471 1472 private: 1473 const int32_t value_; 1474 1475 DISALLOW_COPY_AND_ASSIGN(HIntConstant); 1476}; 1477 1478class HLongConstant : public HConstant { 1479 public: 1480 explicit HLongConstant(int64_t value) : HConstant(Primitive::kPrimLong), value_(value) {} 1481 1482 int64_t GetValue() const { return value_; } 1483 1484 virtual bool InstructionDataEquals(HInstruction* other) const { 1485 return other->AsLongConstant()->value_ == value_; 1486 } 1487 1488 virtual size_t ComputeHashCode() const { return static_cast<size_t>(GetValue()); } 1489 1490 DECLARE_INSTRUCTION(LongConstant); 1491 1492 private: 1493 const int64_t value_; 1494 1495 DISALLOW_COPY_AND_ASSIGN(HLongConstant); 1496}; 1497 1498class HInvoke : public HInstruction { 1499 public: 1500 HInvoke(ArenaAllocator* arena, 1501 uint32_t number_of_arguments, 1502 Primitive::Type return_type, 1503 uint32_t dex_pc) 1504 : HInstruction(SideEffects::All()), 1505 inputs_(arena, number_of_arguments), 1506 return_type_(return_type), 1507 dex_pc_(dex_pc) { 1508 inputs_.SetSize(number_of_arguments); 1509 } 1510 1511 virtual size_t InputCount() const { return inputs_.Size(); } 1512 virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); } 1513 1514 // Runtime needs to walk the stack, so Dex -> Dex calls need to 1515 // know their environment. 1516 virtual bool NeedsEnvironment() const { return true; } 1517 1518 void SetArgumentAt(size_t index, HInstruction* argument) { 1519 SetRawInputAt(index, argument); 1520 } 1521 1522 virtual void SetRawInputAt(size_t index, HInstruction* input) { 1523 inputs_.Put(index, input); 1524 } 1525 1526 virtual Primitive::Type GetType() const { return return_type_; } 1527 1528 uint32_t GetDexPc() const { return dex_pc_; } 1529 1530 DECLARE_INSTRUCTION(Invoke); 1531 1532 protected: 1533 GrowableArray<HInstruction*> inputs_; 1534 const Primitive::Type return_type_; 1535 const uint32_t dex_pc_; 1536 1537 private: 1538 DISALLOW_COPY_AND_ASSIGN(HInvoke); 1539}; 1540 1541class HInvokeStatic : public HInvoke { 1542 public: 1543 HInvokeStatic(ArenaAllocator* arena, 1544 uint32_t number_of_arguments, 1545 Primitive::Type return_type, 1546 uint32_t dex_pc, 1547 uint32_t index_in_dex_cache) 1548 : HInvoke(arena, number_of_arguments, return_type, dex_pc), 1549 index_in_dex_cache_(index_in_dex_cache) {} 1550 1551 uint32_t GetIndexInDexCache() const { return index_in_dex_cache_; } 1552 1553 DECLARE_INSTRUCTION(InvokeStatic); 1554 1555 private: 1556 const uint32_t index_in_dex_cache_; 1557 1558 DISALLOW_COPY_AND_ASSIGN(HInvokeStatic); 1559}; 1560 1561class HInvokeVirtual : public HInvoke { 1562 public: 1563 HInvokeVirtual(ArenaAllocator* arena, 1564 uint32_t number_of_arguments, 1565 Primitive::Type return_type, 1566 uint32_t dex_pc, 1567 uint32_t vtable_index) 1568 : HInvoke(arena, number_of_arguments, return_type, dex_pc), 1569 vtable_index_(vtable_index) {} 1570 1571 uint32_t GetVTableIndex() const { return vtable_index_; } 1572 1573 DECLARE_INSTRUCTION(InvokeVirtual); 1574 1575 private: 1576 const uint32_t vtable_index_; 1577 1578 DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual); 1579}; 1580 1581class HNewInstance : public HExpression<0> { 1582 public: 1583 HNewInstance(uint32_t dex_pc, uint16_t type_index) 1584 : HExpression(Primitive::kPrimNot, SideEffects::None()), 1585 dex_pc_(dex_pc), 1586 type_index_(type_index) {} 1587 1588 uint32_t GetDexPc() const { return dex_pc_; } 1589 uint16_t GetTypeIndex() const { return type_index_; } 1590 1591 // Calls runtime so needs an environment. 1592 virtual bool NeedsEnvironment() const { return true; } 1593 1594 DECLARE_INSTRUCTION(NewInstance); 1595 1596 private: 1597 const uint32_t dex_pc_; 1598 const uint16_t type_index_; 1599 1600 DISALLOW_COPY_AND_ASSIGN(HNewInstance); 1601}; 1602 1603class HNeg : public HUnaryOperation { 1604 public: 1605 explicit HNeg(Primitive::Type result_type, HInstruction* input) 1606 : HUnaryOperation(result_type, input) {} 1607 1608 virtual int32_t Evaluate(int32_t x) const OVERRIDE { return -x; } 1609 virtual int64_t Evaluate(int64_t x) const OVERRIDE { return -x; } 1610 1611 DECLARE_INSTRUCTION(Neg); 1612 1613 private: 1614 DISALLOW_COPY_AND_ASSIGN(HNeg); 1615}; 1616 1617class HNewArray : public HExpression<1> { 1618 public: 1619 HNewArray(HInstruction* length, uint32_t dex_pc, uint16_t type_index) 1620 : HExpression(Primitive::kPrimNot, SideEffects::None()), 1621 dex_pc_(dex_pc), 1622 type_index_(type_index) { 1623 SetRawInputAt(0, length); 1624 } 1625 1626 uint32_t GetDexPc() const { return dex_pc_; } 1627 uint16_t GetTypeIndex() const { return type_index_; } 1628 1629 // Calls runtime so needs an environment. 1630 virtual bool NeedsEnvironment() const { return true; } 1631 1632 DECLARE_INSTRUCTION(NewArray); 1633 1634 private: 1635 const uint32_t dex_pc_; 1636 const uint16_t type_index_; 1637 1638 DISALLOW_COPY_AND_ASSIGN(HNewArray); 1639}; 1640 1641class HAdd : public HBinaryOperation { 1642 public: 1643 HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 1644 : HBinaryOperation(result_type, left, right) {} 1645 1646 virtual bool IsCommutative() { return true; } 1647 1648 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1649 return x + y; 1650 } 1651 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1652 return x + y; 1653 } 1654 1655 DECLARE_INSTRUCTION(Add); 1656 1657 private: 1658 DISALLOW_COPY_AND_ASSIGN(HAdd); 1659}; 1660 1661class HSub : public HBinaryOperation { 1662 public: 1663 HSub(Primitive::Type result_type, HInstruction* left, HInstruction* right) 1664 : HBinaryOperation(result_type, left, right) {} 1665 1666 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1667 return x - y; 1668 } 1669 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1670 return x - y; 1671 } 1672 1673 DECLARE_INSTRUCTION(Sub); 1674 1675 private: 1676 DISALLOW_COPY_AND_ASSIGN(HSub); 1677}; 1678 1679class HMul : public HBinaryOperation { 1680 public: 1681 HMul(Primitive::Type result_type, HInstruction* left, HInstruction* right) 1682 : HBinaryOperation(result_type, left, right) {} 1683 1684 virtual bool IsCommutative() { return true; } 1685 1686 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x * y; } 1687 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x * y; } 1688 1689 DECLARE_INSTRUCTION(Mul); 1690 1691 private: 1692 DISALLOW_COPY_AND_ASSIGN(HMul); 1693}; 1694 1695class HDiv : public HBinaryOperation { 1696 public: 1697 HDiv(Primitive::Type result_type, HInstruction* left, HInstruction* right) 1698 : HBinaryOperation(result_type, left, right) {} 1699 1700 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x / y; } 1701 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x / y; } 1702 1703 DECLARE_INSTRUCTION(Div); 1704 1705 private: 1706 DISALLOW_COPY_AND_ASSIGN(HDiv); 1707}; 1708 1709// The value of a parameter in this method. Its location depends on 1710// the calling convention. 1711class HParameterValue : public HExpression<0> { 1712 public: 1713 HParameterValue(uint8_t index, Primitive::Type parameter_type) 1714 : HExpression(parameter_type, SideEffects::None()), index_(index) {} 1715 1716 uint8_t GetIndex() const { return index_; } 1717 1718 DECLARE_INSTRUCTION(ParameterValue); 1719 1720 private: 1721 // The index of this parameter in the parameters list. Must be less 1722 // than HGraph::number_of_in_vregs_; 1723 const uint8_t index_; 1724 1725 DISALLOW_COPY_AND_ASSIGN(HParameterValue); 1726}; 1727 1728class HNot : public HUnaryOperation { 1729 public: 1730 explicit HNot(Primitive::Type result_type, HInstruction* input) 1731 : HUnaryOperation(result_type, input) {} 1732 1733 virtual bool CanBeMoved() const { return true; } 1734 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1735 1736 virtual int32_t Evaluate(int32_t x) const OVERRIDE { return ~x; } 1737 virtual int64_t Evaluate(int64_t x) const OVERRIDE { return ~x; } 1738 1739 DECLARE_INSTRUCTION(Not); 1740 1741 private: 1742 DISALLOW_COPY_AND_ASSIGN(HNot); 1743}; 1744 1745class HPhi : public HInstruction { 1746 public: 1747 HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type) 1748 : HInstruction(SideEffects::None()), 1749 inputs_(arena, number_of_inputs), 1750 reg_number_(reg_number), 1751 type_(type), 1752 is_live_(false) { 1753 inputs_.SetSize(number_of_inputs); 1754 } 1755 1756 virtual size_t InputCount() const { return inputs_.Size(); } 1757 virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); } 1758 1759 virtual void SetRawInputAt(size_t index, HInstruction* input) { 1760 inputs_.Put(index, input); 1761 } 1762 1763 void AddInput(HInstruction* input); 1764 1765 virtual Primitive::Type GetType() const { return type_; } 1766 void SetType(Primitive::Type type) { type_ = type; } 1767 1768 uint32_t GetRegNumber() const { return reg_number_; } 1769 1770 void SetDead() { is_live_ = false; } 1771 void SetLive() { is_live_ = true; } 1772 bool IsDead() const { return !is_live_; } 1773 bool IsLive() const { return is_live_; } 1774 1775 DECLARE_INSTRUCTION(Phi); 1776 1777 private: 1778 GrowableArray<HInstruction*> inputs_; 1779 const uint32_t reg_number_; 1780 Primitive::Type type_; 1781 bool is_live_; 1782 1783 DISALLOW_COPY_AND_ASSIGN(HPhi); 1784}; 1785 1786class HNullCheck : public HExpression<1> { 1787 public: 1788 HNullCheck(HInstruction* value, uint32_t dex_pc) 1789 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 1790 SetRawInputAt(0, value); 1791 } 1792 1793 virtual bool CanBeMoved() const { return true; } 1794 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1795 1796 virtual bool NeedsEnvironment() const { return true; } 1797 1798 virtual bool CanThrow() const { return true; } 1799 1800 uint32_t GetDexPc() const { return dex_pc_; } 1801 1802 DECLARE_INSTRUCTION(NullCheck); 1803 1804 private: 1805 const uint32_t dex_pc_; 1806 1807 DISALLOW_COPY_AND_ASSIGN(HNullCheck); 1808}; 1809 1810class FieldInfo : public ValueObject { 1811 public: 1812 FieldInfo(MemberOffset field_offset, Primitive::Type field_type) 1813 : field_offset_(field_offset), field_type_(field_type) {} 1814 1815 MemberOffset GetFieldOffset() const { return field_offset_; } 1816 Primitive::Type GetFieldType() const { return field_type_; } 1817 1818 private: 1819 const MemberOffset field_offset_; 1820 const Primitive::Type field_type_; 1821}; 1822 1823class HInstanceFieldGet : public HExpression<1> { 1824 public: 1825 HInstanceFieldGet(HInstruction* value, 1826 Primitive::Type field_type, 1827 MemberOffset field_offset) 1828 : HExpression(field_type, SideEffects::DependsOnSomething()), 1829 field_info_(field_offset, field_type) { 1830 SetRawInputAt(0, value); 1831 } 1832 1833 virtual bool CanBeMoved() const { return true; } 1834 virtual bool InstructionDataEquals(HInstruction* other) const { 1835 size_t other_offset = other->AsInstanceFieldGet()->GetFieldOffset().SizeValue(); 1836 return other_offset == GetFieldOffset().SizeValue(); 1837 } 1838 1839 virtual size_t ComputeHashCode() const { 1840 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 1841 } 1842 1843 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 1844 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 1845 1846 DECLARE_INSTRUCTION(InstanceFieldGet); 1847 1848 private: 1849 const FieldInfo field_info_; 1850 1851 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet); 1852}; 1853 1854class HInstanceFieldSet : public HTemplateInstruction<2> { 1855 public: 1856 HInstanceFieldSet(HInstruction* object, 1857 HInstruction* value, 1858 Primitive::Type field_type, 1859 MemberOffset field_offset) 1860 : HTemplateInstruction(SideEffects::ChangesSomething()), 1861 field_info_(field_offset, field_type) { 1862 SetRawInputAt(0, object); 1863 SetRawInputAt(1, value); 1864 } 1865 1866 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 1867 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 1868 1869 DECLARE_INSTRUCTION(InstanceFieldSet); 1870 1871 private: 1872 const FieldInfo field_info_; 1873 1874 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet); 1875}; 1876 1877class HArrayGet : public HExpression<2> { 1878 public: 1879 HArrayGet(HInstruction* array, HInstruction* index, Primitive::Type type) 1880 : HExpression(type, SideEffects::DependsOnSomething()) { 1881 SetRawInputAt(0, array); 1882 SetRawInputAt(1, index); 1883 } 1884 1885 virtual bool CanBeMoved() const { return true; } 1886 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1887 void SetType(Primitive::Type type) { type_ = type; } 1888 1889 DECLARE_INSTRUCTION(ArrayGet); 1890 1891 private: 1892 DISALLOW_COPY_AND_ASSIGN(HArrayGet); 1893}; 1894 1895class HArraySet : public HTemplateInstruction<3> { 1896 public: 1897 HArraySet(HInstruction* array, 1898 HInstruction* index, 1899 HInstruction* value, 1900 Primitive::Type expected_component_type, 1901 uint32_t dex_pc) 1902 : HTemplateInstruction(SideEffects::ChangesSomething()), 1903 dex_pc_(dex_pc), 1904 expected_component_type_(expected_component_type) { 1905 SetRawInputAt(0, array); 1906 SetRawInputAt(1, index); 1907 SetRawInputAt(2, value); 1908 } 1909 1910 virtual bool NeedsEnvironment() const { 1911 // We currently always call a runtime method to catch array store 1912 // exceptions. 1913 return InputAt(2)->GetType() == Primitive::kPrimNot; 1914 } 1915 1916 uint32_t GetDexPc() const { return dex_pc_; } 1917 1918 HInstruction* GetValue() const { return InputAt(2); } 1919 1920 Primitive::Type GetComponentType() const { 1921 // The Dex format does not type floating point index operations. Since the 1922 // `expected_component_type_` is set during building and can therefore not 1923 // be correct, we also check what is the value type. If it is a floating 1924 // point type, we must use that type. 1925 Primitive::Type value_type = GetValue()->GetType(); 1926 return ((value_type == Primitive::kPrimFloat) || (value_type == Primitive::kPrimDouble)) 1927 ? value_type 1928 : expected_component_type_; 1929 } 1930 1931 DECLARE_INSTRUCTION(ArraySet); 1932 1933 private: 1934 const uint32_t dex_pc_; 1935 const Primitive::Type expected_component_type_; 1936 1937 DISALLOW_COPY_AND_ASSIGN(HArraySet); 1938}; 1939 1940class HArrayLength : public HExpression<1> { 1941 public: 1942 explicit HArrayLength(HInstruction* array) 1943 : HExpression(Primitive::kPrimInt, SideEffects::None()) { 1944 // Note that arrays do not change length, so the instruction does not 1945 // depend on any write. 1946 SetRawInputAt(0, array); 1947 } 1948 1949 virtual bool CanBeMoved() const { return true; } 1950 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1951 1952 DECLARE_INSTRUCTION(ArrayLength); 1953 1954 private: 1955 DISALLOW_COPY_AND_ASSIGN(HArrayLength); 1956}; 1957 1958class HBoundsCheck : public HExpression<2> { 1959 public: 1960 HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc) 1961 : HExpression(index->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 1962 DCHECK(index->GetType() == Primitive::kPrimInt); 1963 SetRawInputAt(0, index); 1964 SetRawInputAt(1, length); 1965 } 1966 1967 virtual bool CanBeMoved() const { return true; } 1968 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1969 1970 virtual bool NeedsEnvironment() const { return true; } 1971 1972 virtual bool CanThrow() const { return true; } 1973 1974 uint32_t GetDexPc() const { return dex_pc_; } 1975 1976 DECLARE_INSTRUCTION(BoundsCheck); 1977 1978 private: 1979 const uint32_t dex_pc_; 1980 1981 DISALLOW_COPY_AND_ASSIGN(HBoundsCheck); 1982}; 1983 1984/** 1985 * Some DEX instructions are folded into multiple HInstructions that need 1986 * to stay live until the last HInstruction. This class 1987 * is used as a marker for the baseline compiler to ensure its preceding 1988 * HInstruction stays live. `index` is the temporary number that is used 1989 * for knowing the stack offset where to store the instruction. 1990 */ 1991class HTemporary : public HTemplateInstruction<0> { 1992 public: 1993 explicit HTemporary(size_t index) : HTemplateInstruction(SideEffects::None()), index_(index) {} 1994 1995 size_t GetIndex() const { return index_; } 1996 1997 DECLARE_INSTRUCTION(Temporary); 1998 1999 private: 2000 const size_t index_; 2001 2002 DISALLOW_COPY_AND_ASSIGN(HTemporary); 2003}; 2004 2005class HSuspendCheck : public HTemplateInstruction<0> { 2006 public: 2007 explicit HSuspendCheck(uint32_t dex_pc) 2008 : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc) {} 2009 2010 virtual bool NeedsEnvironment() const { 2011 return true; 2012 } 2013 2014 uint32_t GetDexPc() const { return dex_pc_; } 2015 2016 DECLARE_INSTRUCTION(SuspendCheck); 2017 2018 private: 2019 const uint32_t dex_pc_; 2020 2021 DISALLOW_COPY_AND_ASSIGN(HSuspendCheck); 2022}; 2023 2024// TODO: Make this class handle the case the load is null (dex cache 2025// is null). 2026/** 2027 * Instruction to load a Class object. 2028 */ 2029class HLoadClass : public HExpression<0> { 2030 public: 2031 HLoadClass(uint16_t type_index, 2032 bool is_referrers_class, 2033 bool is_initialized, 2034 uint32_t dex_pc) 2035 : HExpression(Primitive::kPrimNot, SideEffects::None()), 2036 type_index_(type_index), 2037 is_referrers_class_(is_referrers_class), 2038 is_initialized_(is_initialized), 2039 dex_pc_(dex_pc) {} 2040 2041 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2042 return other->AsLoadClass()->type_index_ == type_index_; 2043 } 2044 2045 size_t ComputeHashCode() const OVERRIDE { return type_index_; } 2046 2047 uint32_t GetDexPc() const { return dex_pc_; } 2048 uint16_t GetTypeIndex() const { return type_index_; } 2049 2050 bool NeedsInitialization() const { 2051 return !is_initialized_ && !is_referrers_class_; 2052 } 2053 2054 bool IsReferrersClass() const { return is_referrers_class_; } 2055 2056 DECLARE_INSTRUCTION(LoadClass); 2057 2058 private: 2059 const uint16_t type_index_; 2060 const bool is_referrers_class_; 2061 const bool is_initialized_; 2062 const uint32_t dex_pc_; 2063 2064 DISALLOW_COPY_AND_ASSIGN(HLoadClass); 2065}; 2066 2067// TODO: Pass this check to HInvokeStatic nodes. 2068/** 2069 * Performs an initialization check on its Class object input. 2070 */ 2071class HClinitCheck : public HExpression<1> { 2072 public: 2073 explicit HClinitCheck(HLoadClass* constant, uint32_t dex_pc) 2074 : HExpression(Primitive::kPrimNot, SideEffects::All()), 2075 dex_pc_(dex_pc) { 2076 SetRawInputAt(0, constant); 2077 } 2078 2079 bool NeedsEnvironment() const OVERRIDE { 2080 // May call runtime to initialize the class. 2081 return true; 2082 } 2083 2084 uint32_t GetDexPc() const { return dex_pc_; } 2085 2086 HLoadClass* GetLoadClass() const { return InputAt(0)->AsLoadClass(); } 2087 2088 DECLARE_INSTRUCTION(ClinitCheck); 2089 2090 private: 2091 const uint32_t dex_pc_; 2092 2093 DISALLOW_COPY_AND_ASSIGN(HClinitCheck); 2094}; 2095 2096class HStaticFieldGet : public HExpression<1> { 2097 public: 2098 HStaticFieldGet(HInstruction* cls, 2099 Primitive::Type field_type, 2100 MemberOffset field_offset) 2101 : HExpression(field_type, SideEffects::DependsOnSomething()), 2102 field_info_(field_offset, field_type) { 2103 SetRawInputAt(0, cls); 2104 } 2105 2106 bool CanBeMoved() const OVERRIDE { return true; } 2107 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2108 size_t other_offset = other->AsStaticFieldGet()->GetFieldOffset().SizeValue(); 2109 return other_offset == GetFieldOffset().SizeValue(); 2110 } 2111 2112 size_t ComputeHashCode() const OVERRIDE { 2113 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 2114 } 2115 2116 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 2117 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 2118 2119 DECLARE_INSTRUCTION(StaticFieldGet); 2120 2121 private: 2122 const FieldInfo field_info_; 2123 2124 DISALLOW_COPY_AND_ASSIGN(HStaticFieldGet); 2125}; 2126 2127class HStaticFieldSet : public HTemplateInstruction<2> { 2128 public: 2129 HStaticFieldSet(HInstruction* cls, 2130 HInstruction* value, 2131 Primitive::Type field_type, 2132 MemberOffset field_offset) 2133 : HTemplateInstruction(SideEffects::ChangesSomething()), 2134 field_info_(field_offset, field_type) { 2135 SetRawInputAt(0, cls); 2136 SetRawInputAt(1, value); 2137 } 2138 2139 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 2140 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 2141 2142 DECLARE_INSTRUCTION(StaticFieldSet); 2143 2144 private: 2145 const FieldInfo field_info_; 2146 2147 DISALLOW_COPY_AND_ASSIGN(HStaticFieldSet); 2148}; 2149 2150class MoveOperands : public ArenaObject { 2151 public: 2152 MoveOperands(Location source, Location destination, HInstruction* instruction) 2153 : source_(source), destination_(destination), instruction_(instruction) {} 2154 2155 Location GetSource() const { return source_; } 2156 Location GetDestination() const { return destination_; } 2157 2158 void SetSource(Location value) { source_ = value; } 2159 void SetDestination(Location value) { destination_ = value; } 2160 2161 // The parallel move resolver marks moves as "in-progress" by clearing the 2162 // destination (but not the source). 2163 Location MarkPending() { 2164 DCHECK(!IsPending()); 2165 Location dest = destination_; 2166 destination_ = Location::NoLocation(); 2167 return dest; 2168 } 2169 2170 void ClearPending(Location dest) { 2171 DCHECK(IsPending()); 2172 destination_ = dest; 2173 } 2174 2175 bool IsPending() const { 2176 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 2177 return destination_.IsInvalid() && !source_.IsInvalid(); 2178 } 2179 2180 // True if this blocks a move from the given location. 2181 bool Blocks(Location loc) const { 2182 return !IsEliminated() && source_.Equals(loc); 2183 } 2184 2185 // A move is redundant if it's been eliminated, if its source and 2186 // destination are the same, or if its destination is unneeded. 2187 bool IsRedundant() const { 2188 return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_); 2189 } 2190 2191 // We clear both operands to indicate move that's been eliminated. 2192 void Eliminate() { 2193 source_ = destination_ = Location::NoLocation(); 2194 } 2195 2196 bool IsEliminated() const { 2197 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 2198 return source_.IsInvalid(); 2199 } 2200 2201 HInstruction* GetInstruction() const { return instruction_; } 2202 2203 private: 2204 Location source_; 2205 Location destination_; 2206 // The instruction this move is assocatied with. Null when this move is 2207 // for moving an input in the expected locations of user (including a phi user). 2208 // This is only used in debug mode, to ensure we do not connect interval siblings 2209 // in the same parallel move. 2210 HInstruction* instruction_; 2211 2212 DISALLOW_COPY_AND_ASSIGN(MoveOperands); 2213}; 2214 2215static constexpr size_t kDefaultNumberOfMoves = 4; 2216 2217class HParallelMove : public HTemplateInstruction<0> { 2218 public: 2219 explicit HParallelMove(ArenaAllocator* arena) 2220 : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {} 2221 2222 void AddMove(MoveOperands* move) { 2223 if (kIsDebugBuild && move->GetInstruction() != nullptr) { 2224 for (size_t i = 0, e = moves_.Size(); i < e; ++i) { 2225 DCHECK_NE(moves_.Get(i)->GetInstruction(), move->GetInstruction()) 2226 << "Doing parallel moves for the same instruction."; 2227 } 2228 } 2229 moves_.Add(move); 2230 } 2231 2232 MoveOperands* MoveOperandsAt(size_t index) const { 2233 return moves_.Get(index); 2234 } 2235 2236 size_t NumMoves() const { return moves_.Size(); } 2237 2238 DECLARE_INSTRUCTION(ParallelMove); 2239 2240 private: 2241 GrowableArray<MoveOperands*> moves_; 2242 2243 DISALLOW_COPY_AND_ASSIGN(HParallelMove); 2244}; 2245 2246class HGraphVisitor : public ValueObject { 2247 public: 2248 explicit HGraphVisitor(HGraph* graph) : graph_(graph) {} 2249 virtual ~HGraphVisitor() {} 2250 2251 virtual void VisitInstruction(HInstruction* instruction) {} 2252 virtual void VisitBasicBlock(HBasicBlock* block); 2253 2254 // Visit the graph following basic block insertion order. 2255 void VisitInsertionOrder(); 2256 2257 // Visit the graph following dominator tree reverse post-order. 2258 void VisitReversePostOrder(); 2259 2260 HGraph* GetGraph() const { return graph_; } 2261 2262 // Visit functions for instruction classes. 2263#define DECLARE_VISIT_INSTRUCTION(name, super) \ 2264 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } 2265 2266 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 2267 2268#undef DECLARE_VISIT_INSTRUCTION 2269 2270 private: 2271 HGraph* const graph_; 2272 2273 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); 2274}; 2275 2276class HGraphDelegateVisitor : public HGraphVisitor { 2277 public: 2278 explicit HGraphDelegateVisitor(HGraph* graph) : HGraphVisitor(graph) {} 2279 virtual ~HGraphDelegateVisitor() {} 2280 2281 // Visit functions that delegate to to super class. 2282#define DECLARE_VISIT_INSTRUCTION(name, super) \ 2283 virtual void Visit##name(H##name* instr) OVERRIDE { Visit##super(instr); } 2284 2285 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 2286 2287#undef DECLARE_VISIT_INSTRUCTION 2288 2289 private: 2290 DISALLOW_COPY_AND_ASSIGN(HGraphDelegateVisitor); 2291}; 2292 2293class HInsertionOrderIterator : public ValueObject { 2294 public: 2295 explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 2296 2297 bool Done() const { return index_ == graph_.GetBlocks().Size(); } 2298 HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); } 2299 void Advance() { ++index_; } 2300 2301 private: 2302 const HGraph& graph_; 2303 size_t index_; 2304 2305 DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator); 2306}; 2307 2308class HReversePostOrderIterator : public ValueObject { 2309 public: 2310 explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 2311 2312 bool Done() const { return index_ == graph_.GetReversePostOrder().Size(); } 2313 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_); } 2314 void Advance() { ++index_; } 2315 2316 private: 2317 const HGraph& graph_; 2318 size_t index_; 2319 2320 DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator); 2321}; 2322 2323class HPostOrderIterator : public ValueObject { 2324 public: 2325 explicit HPostOrderIterator(const HGraph& graph) 2326 : graph_(graph), index_(graph_.GetReversePostOrder().Size()) {} 2327 2328 bool Done() const { return index_ == 0; } 2329 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_ - 1); } 2330 void Advance() { --index_; } 2331 2332 private: 2333 const HGraph& graph_; 2334 size_t index_; 2335 2336 DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); 2337}; 2338 2339} // namespace art 2340 2341#endif // ART_COMPILER_OPTIMIZING_NODES_H_ 2342