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