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