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