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