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