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