nodes.h revision 641547a5f18ca2ea54469cceadcfef64f132e5e0
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 CanDoImplicitNullCheckOn(HInstruction* obj) const { 1162 UNUSED(obj); 1163 return false; 1164 } 1165 1166 void SetReferenceTypeInfo(ReferenceTypeInfo reference_type_info) { 1167 DCHECK_EQ(GetType(), Primitive::kPrimNot); 1168 reference_type_info_ = reference_type_info; 1169 } 1170 1171 ReferenceTypeInfo GetReferenceTypeInfo() const { 1172 DCHECK_EQ(GetType(), Primitive::kPrimNot); 1173 return reference_type_info_; 1174 } 1175 1176 void AddUseAt(HInstruction* user, size_t index) { 1177 DCHECK(user != nullptr); 1178 HUseListNode<HInstruction*>* use = 1179 uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); 1180 user->SetRawInputRecordAt(index, HUserRecord<HInstruction*>(user->InputRecordAt(index), use)); 1181 } 1182 1183 void AddEnvUseAt(HEnvironment* user, size_t index) { 1184 DCHECK(user != nullptr); 1185 HUseListNode<HEnvironment*>* env_use = 1186 env_uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); 1187 user->RecordEnvUse(env_use); 1188 } 1189 1190 void RemoveAsUserOfInput(size_t input) { 1191 HUserRecord<HInstruction*> input_use = InputRecordAt(input); 1192 input_use.GetInstruction()->uses_.Remove(input_use.GetUseNode()); 1193 } 1194 1195 const HUseList<HInstruction*>& GetUses() const { return uses_; } 1196 const HUseList<HEnvironment*>& GetEnvUses() const { return env_uses_; } 1197 1198 bool HasUses() const { return !uses_.IsEmpty() || !env_uses_.IsEmpty(); } 1199 bool HasEnvironmentUses() const { return !env_uses_.IsEmpty(); } 1200 bool HasNonEnvironmentUses() const { return !uses_.IsEmpty(); } 1201 bool HasOnlyOneNonEnvironmentUse() const { 1202 return !HasEnvironmentUses() && GetUses().HasOnlyOneUse(); 1203 } 1204 1205 // Does this instruction strictly dominate `other_instruction`? 1206 // Returns false if this instruction and `other_instruction` are the same. 1207 // Aborts if this instruction and `other_instruction` are both phis. 1208 bool StrictlyDominates(HInstruction* other_instruction) const; 1209 1210 int GetId() const { return id_; } 1211 void SetId(int id) { id_ = id; } 1212 1213 int GetSsaIndex() const { return ssa_index_; } 1214 void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; } 1215 bool HasSsaIndex() const { return ssa_index_ != -1; } 1216 1217 bool HasEnvironment() const { return environment_ != nullptr; } 1218 HEnvironment* GetEnvironment() const { return environment_; } 1219 // Set the `environment_` field. Raw because this method does not 1220 // update the uses lists. 1221 void SetRawEnvironment(HEnvironment* environment) { environment_ = environment; } 1222 1223 // Set the environment of this instruction, copying it from `environment`. While 1224 // copying, the uses lists are being updated. 1225 void CopyEnvironmentFrom(HEnvironment* environment) { 1226 ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena(); 1227 environment_ = new (allocator) HEnvironment(allocator, environment->Size()); 1228 environment_->CopyFrom(environment); 1229 } 1230 1231 // Returns the number of entries in the environment. Typically, that is the 1232 // number of dex registers in a method. It could be more in case of inlining. 1233 size_t EnvironmentSize() const; 1234 1235 LocationSummary* GetLocations() const { return locations_; } 1236 void SetLocations(LocationSummary* locations) { locations_ = locations; } 1237 1238 void ReplaceWith(HInstruction* instruction); 1239 void ReplaceInput(HInstruction* replacement, size_t index); 1240 1241 // This is almost the same as doing `ReplaceWith()`. But in this helper, the 1242 // uses of this instruction by `other` are *not* updated. 1243 void ReplaceWithExceptInReplacementAtIndex(HInstruction* other, size_t use_index) { 1244 ReplaceWith(other); 1245 other->ReplaceInput(this, use_index); 1246 } 1247 1248 // Move `this` instruction before `cursor`. 1249 void MoveBefore(HInstruction* cursor); 1250 1251#define INSTRUCTION_TYPE_CHECK(type, super) \ 1252 bool Is##type() const { return (As##type() != nullptr); } \ 1253 virtual const H##type* As##type() const { return nullptr; } \ 1254 virtual H##type* As##type() { return nullptr; } 1255 1256 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 1257#undef INSTRUCTION_TYPE_CHECK 1258 1259 // Returns whether the instruction can be moved within the graph. 1260 virtual bool CanBeMoved() const { return false; } 1261 1262 // Returns whether the two instructions are of the same kind. 1263 virtual bool InstructionTypeEquals(HInstruction* other) const { 1264 UNUSED(other); 1265 return false; 1266 } 1267 1268 // Returns whether any data encoded in the two instructions is equal. 1269 // This method does not look at the inputs. Both instructions must be 1270 // of the same type, otherwise the method has undefined behavior. 1271 virtual bool InstructionDataEquals(HInstruction* other) const { 1272 UNUSED(other); 1273 return false; 1274 } 1275 1276 // Returns whether two instructions are equal, that is: 1277 // 1) They have the same type and contain the same data (InstructionDataEquals). 1278 // 2) Their inputs are identical. 1279 bool Equals(HInstruction* other) const; 1280 1281 virtual InstructionKind GetKind() const = 0; 1282 1283 virtual size_t ComputeHashCode() const { 1284 size_t result = GetKind(); 1285 for (size_t i = 0, e = InputCount(); i < e; ++i) { 1286 result = (result * 31) + InputAt(i)->GetId(); 1287 } 1288 return result; 1289 } 1290 1291 SideEffects GetSideEffects() const { return side_effects_; } 1292 1293 size_t GetLifetimePosition() const { return lifetime_position_; } 1294 void SetLifetimePosition(size_t position) { lifetime_position_ = position; } 1295 LiveInterval* GetLiveInterval() const { return live_interval_; } 1296 void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; } 1297 bool HasLiveInterval() const { return live_interval_ != nullptr; } 1298 1299 bool IsSuspendCheckEntry() const { return IsSuspendCheck() && GetBlock()->IsEntryBlock(); } 1300 1301 // Returns whether the code generation of the instruction will require to have access 1302 // to the current method. Such instructions are: 1303 // (1): Instructions that require an environment, as calling the runtime requires 1304 // to walk the stack and have the current method stored at a specific stack address. 1305 // (2): Object literals like classes and strings, that are loaded from the dex cache 1306 // fields of the current method. 1307 bool NeedsCurrentMethod() const { 1308 return NeedsEnvironment() || IsLoadClass() || IsLoadString(); 1309 } 1310 1311 virtual bool NeedsDexCache() const { return false; } 1312 1313 protected: 1314 virtual const HUserRecord<HInstruction*> InputRecordAt(size_t i) const = 0; 1315 virtual void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) = 0; 1316 1317 private: 1318 void RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use_node) { env_uses_.Remove(use_node); } 1319 1320 HInstruction* previous_; 1321 HInstruction* next_; 1322 HBasicBlock* block_; 1323 1324 // An instruction gets an id when it is added to the graph. 1325 // It reflects creation order. A negative id means the instruction 1326 // has not been added to the graph. 1327 int id_; 1328 1329 // When doing liveness analysis, instructions that have uses get an SSA index. 1330 int ssa_index_; 1331 1332 // List of instructions that have this instruction as input. 1333 HUseList<HInstruction*> uses_; 1334 1335 // List of environments that contain this instruction. 1336 HUseList<HEnvironment*> env_uses_; 1337 1338 // The environment associated with this instruction. Not null if the instruction 1339 // might jump out of the method. 1340 HEnvironment* environment_; 1341 1342 // Set by the code generator. 1343 LocationSummary* locations_; 1344 1345 // Set by the liveness analysis. 1346 LiveInterval* live_interval_; 1347 1348 // Set by the liveness analysis, this is the position in a linear 1349 // order of blocks where this instruction's live interval start. 1350 size_t lifetime_position_; 1351 1352 const SideEffects side_effects_; 1353 1354 // TODO: for primitive types this should be marked as invalid. 1355 ReferenceTypeInfo reference_type_info_; 1356 1357 friend class GraphChecker; 1358 friend class HBasicBlock; 1359 friend class HEnvironment; 1360 friend class HGraph; 1361 friend class HInstructionList; 1362 1363 DISALLOW_COPY_AND_ASSIGN(HInstruction); 1364}; 1365std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs); 1366 1367class HInputIterator : public ValueObject { 1368 public: 1369 explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {} 1370 1371 bool Done() const { return index_ == instruction_->InputCount(); } 1372 HInstruction* Current() const { return instruction_->InputAt(index_); } 1373 void Advance() { index_++; } 1374 1375 private: 1376 HInstruction* instruction_; 1377 size_t index_; 1378 1379 DISALLOW_COPY_AND_ASSIGN(HInputIterator); 1380}; 1381 1382class HInstructionIterator : public ValueObject { 1383 public: 1384 explicit HInstructionIterator(const HInstructionList& instructions) 1385 : instruction_(instructions.first_instruction_) { 1386 next_ = Done() ? nullptr : instruction_->GetNext(); 1387 } 1388 1389 bool Done() const { return instruction_ == nullptr; } 1390 HInstruction* Current() const { return instruction_; } 1391 void Advance() { 1392 instruction_ = next_; 1393 next_ = Done() ? nullptr : instruction_->GetNext(); 1394 } 1395 1396 private: 1397 HInstruction* instruction_; 1398 HInstruction* next_; 1399 1400 DISALLOW_COPY_AND_ASSIGN(HInstructionIterator); 1401}; 1402 1403class HBackwardInstructionIterator : public ValueObject { 1404 public: 1405 explicit HBackwardInstructionIterator(const HInstructionList& instructions) 1406 : instruction_(instructions.last_instruction_) { 1407 next_ = Done() ? nullptr : instruction_->GetPrevious(); 1408 } 1409 1410 bool Done() const { return instruction_ == nullptr; } 1411 HInstruction* Current() const { return instruction_; } 1412 void Advance() { 1413 instruction_ = next_; 1414 next_ = Done() ? nullptr : instruction_->GetPrevious(); 1415 } 1416 1417 private: 1418 HInstruction* instruction_; 1419 HInstruction* next_; 1420 1421 DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator); 1422}; 1423 1424// An embedded container with N elements of type T. Used (with partial 1425// specialization for N=0) because embedded arrays cannot have size 0. 1426template<typename T, intptr_t N> 1427class EmbeddedArray { 1428 public: 1429 EmbeddedArray() : elements_() {} 1430 1431 intptr_t GetLength() const { return N; } 1432 1433 const T& operator[](intptr_t i) const { 1434 DCHECK_LT(i, GetLength()); 1435 return elements_[i]; 1436 } 1437 1438 T& operator[](intptr_t i) { 1439 DCHECK_LT(i, GetLength()); 1440 return elements_[i]; 1441 } 1442 1443 const T& At(intptr_t i) const { 1444 return (*this)[i]; 1445 } 1446 1447 void SetAt(intptr_t i, const T& val) { 1448 (*this)[i] = val; 1449 } 1450 1451 private: 1452 T elements_[N]; 1453}; 1454 1455template<typename T> 1456class EmbeddedArray<T, 0> { 1457 public: 1458 intptr_t length() const { return 0; } 1459 const T& operator[](intptr_t i) const { 1460 UNUSED(i); 1461 LOG(FATAL) << "Unreachable"; 1462 UNREACHABLE(); 1463 } 1464 T& operator[](intptr_t i) { 1465 UNUSED(i); 1466 LOG(FATAL) << "Unreachable"; 1467 UNREACHABLE(); 1468 } 1469}; 1470 1471template<intptr_t N> 1472class HTemplateInstruction: public HInstruction { 1473 public: 1474 HTemplateInstruction<N>(SideEffects side_effects) 1475 : HInstruction(side_effects), inputs_() {} 1476 virtual ~HTemplateInstruction() {} 1477 1478 size_t InputCount() const OVERRIDE { return N; } 1479 1480 protected: 1481 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_[i]; } 1482 1483 void SetRawInputRecordAt(size_t i, const HUserRecord<HInstruction*>& input) OVERRIDE { 1484 inputs_[i] = input; 1485 } 1486 1487 private: 1488 EmbeddedArray<HUserRecord<HInstruction*>, N> inputs_; 1489 1490 friend class SsaBuilder; 1491}; 1492 1493template<intptr_t N> 1494class HExpression : public HTemplateInstruction<N> { 1495 public: 1496 HExpression<N>(Primitive::Type type, SideEffects side_effects) 1497 : HTemplateInstruction<N>(side_effects), type_(type) {} 1498 virtual ~HExpression() {} 1499 1500 Primitive::Type GetType() const OVERRIDE { return type_; } 1501 1502 protected: 1503 Primitive::Type type_; 1504}; 1505 1506// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow 1507// instruction that branches to the exit block. 1508class HReturnVoid : public HTemplateInstruction<0> { 1509 public: 1510 HReturnVoid() : HTemplateInstruction(SideEffects::None()) {} 1511 1512 bool IsControlFlow() const OVERRIDE { return true; } 1513 1514 DECLARE_INSTRUCTION(ReturnVoid); 1515 1516 private: 1517 DISALLOW_COPY_AND_ASSIGN(HReturnVoid); 1518}; 1519 1520// Represents dex's RETURN opcodes. A HReturn is a control flow 1521// instruction that branches to the exit block. 1522class HReturn : public HTemplateInstruction<1> { 1523 public: 1524 explicit HReturn(HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 1525 SetRawInputAt(0, value); 1526 } 1527 1528 bool IsControlFlow() const OVERRIDE { return true; } 1529 1530 DECLARE_INSTRUCTION(Return); 1531 1532 private: 1533 DISALLOW_COPY_AND_ASSIGN(HReturn); 1534}; 1535 1536// The exit instruction is the only instruction of the exit block. 1537// Instructions aborting the method (HThrow and HReturn) must branch to the 1538// exit block. 1539class HExit : public HTemplateInstruction<0> { 1540 public: 1541 HExit() : HTemplateInstruction(SideEffects::None()) {} 1542 1543 bool IsControlFlow() const OVERRIDE { return true; } 1544 1545 DECLARE_INSTRUCTION(Exit); 1546 1547 private: 1548 DISALLOW_COPY_AND_ASSIGN(HExit); 1549}; 1550 1551// Jumps from one block to another. 1552class HGoto : public HTemplateInstruction<0> { 1553 public: 1554 HGoto() : HTemplateInstruction(SideEffects::None()) {} 1555 1556 bool IsControlFlow() const OVERRIDE { return true; } 1557 1558 HBasicBlock* GetSuccessor() const { 1559 return GetBlock()->GetSuccessors().Get(0); 1560 } 1561 1562 DECLARE_INSTRUCTION(Goto); 1563 1564 private: 1565 DISALLOW_COPY_AND_ASSIGN(HGoto); 1566}; 1567 1568 1569// Conditional branch. A block ending with an HIf instruction must have 1570// two successors. 1571class HIf : public HTemplateInstruction<1> { 1572 public: 1573 explicit HIf(HInstruction* input) : HTemplateInstruction(SideEffects::None()) { 1574 SetRawInputAt(0, input); 1575 } 1576 1577 bool IsControlFlow() const OVERRIDE { return true; } 1578 1579 HBasicBlock* IfTrueSuccessor() const { 1580 return GetBlock()->GetSuccessors().Get(0); 1581 } 1582 1583 HBasicBlock* IfFalseSuccessor() const { 1584 return GetBlock()->GetSuccessors().Get(1); 1585 } 1586 1587 DECLARE_INSTRUCTION(If); 1588 1589 private: 1590 DISALLOW_COPY_AND_ASSIGN(HIf); 1591}; 1592 1593// Deoptimize to interpreter, upon checking a condition. 1594class HDeoptimize : public HTemplateInstruction<1> { 1595 public: 1596 HDeoptimize(HInstruction* cond, uint32_t dex_pc) 1597 : HTemplateInstruction(SideEffects::None()), 1598 dex_pc_(dex_pc) { 1599 SetRawInputAt(0, cond); 1600 } 1601 1602 bool NeedsEnvironment() const OVERRIDE { return true; } 1603 bool CanThrow() const OVERRIDE { return true; } 1604 uint32_t GetDexPc() const { return dex_pc_; } 1605 1606 DECLARE_INSTRUCTION(Deoptimize); 1607 1608 private: 1609 uint32_t dex_pc_; 1610 1611 DISALLOW_COPY_AND_ASSIGN(HDeoptimize); 1612}; 1613 1614class HUnaryOperation : public HExpression<1> { 1615 public: 1616 HUnaryOperation(Primitive::Type result_type, HInstruction* input) 1617 : HExpression(result_type, SideEffects::None()) { 1618 SetRawInputAt(0, input); 1619 } 1620 1621 HInstruction* GetInput() const { return InputAt(0); } 1622 Primitive::Type GetResultType() const { return GetType(); } 1623 1624 bool CanBeMoved() const OVERRIDE { return true; } 1625 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 1626 UNUSED(other); 1627 return true; 1628 } 1629 1630 // Try to statically evaluate `operation` and return a HConstant 1631 // containing the result of this evaluation. If `operation` cannot 1632 // be evaluated as a constant, return nullptr. 1633 HConstant* TryStaticEvaluation() const; 1634 1635 // Apply this operation to `x`. 1636 virtual int32_t Evaluate(int32_t x) const = 0; 1637 virtual int64_t Evaluate(int64_t x) const = 0; 1638 1639 DECLARE_INSTRUCTION(UnaryOperation); 1640 1641 private: 1642 DISALLOW_COPY_AND_ASSIGN(HUnaryOperation); 1643}; 1644 1645class HBinaryOperation : public HExpression<2> { 1646 public: 1647 HBinaryOperation(Primitive::Type result_type, 1648 HInstruction* left, 1649 HInstruction* right) : HExpression(result_type, SideEffects::None()) { 1650 SetRawInputAt(0, left); 1651 SetRawInputAt(1, right); 1652 } 1653 1654 HInstruction* GetLeft() const { return InputAt(0); } 1655 HInstruction* GetRight() const { return InputAt(1); } 1656 Primitive::Type GetResultType() const { return GetType(); } 1657 1658 virtual bool IsCommutative() const { return false; } 1659 1660 // Put constant on the right. 1661 // Returns whether order is changed. 1662 bool OrderInputsWithConstantOnTheRight() { 1663 HInstruction* left = InputAt(0); 1664 HInstruction* right = InputAt(1); 1665 if (left->IsConstant() && !right->IsConstant()) { 1666 ReplaceInput(right, 0); 1667 ReplaceInput(left, 1); 1668 return true; 1669 } 1670 return false; 1671 } 1672 1673 // Order inputs by instruction id, but favor constant on the right side. 1674 // This helps GVN for commutative ops. 1675 void OrderInputs() { 1676 DCHECK(IsCommutative()); 1677 HInstruction* left = InputAt(0); 1678 HInstruction* right = InputAt(1); 1679 if (left == right || (!left->IsConstant() && right->IsConstant())) { 1680 return; 1681 } 1682 if (OrderInputsWithConstantOnTheRight()) { 1683 return; 1684 } 1685 // Order according to instruction id. 1686 if (left->GetId() > right->GetId()) { 1687 ReplaceInput(right, 0); 1688 ReplaceInput(left, 1); 1689 } 1690 } 1691 1692 bool CanBeMoved() const OVERRIDE { return true; } 1693 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 1694 UNUSED(other); 1695 return true; 1696 } 1697 1698 // Try to statically evaluate `operation` and return a HConstant 1699 // containing the result of this evaluation. If `operation` cannot 1700 // be evaluated as a constant, return nullptr. 1701 HConstant* TryStaticEvaluation() const; 1702 1703 // Apply this operation to `x` and `y`. 1704 virtual int32_t Evaluate(int32_t x, int32_t y) const = 0; 1705 virtual int64_t Evaluate(int64_t x, int64_t y) const = 0; 1706 1707 // Returns an input that can legally be used as the right input and is 1708 // constant, or nullptr. 1709 HConstant* GetConstantRight() const; 1710 1711 // If `GetConstantRight()` returns one of the input, this returns the other 1712 // one. Otherwise it returns nullptr. 1713 HInstruction* GetLeastConstantLeft() const; 1714 1715 DECLARE_INSTRUCTION(BinaryOperation); 1716 1717 private: 1718 DISALLOW_COPY_AND_ASSIGN(HBinaryOperation); 1719}; 1720 1721class HCondition : public HBinaryOperation { 1722 public: 1723 HCondition(HInstruction* first, HInstruction* second) 1724 : HBinaryOperation(Primitive::kPrimBoolean, first, second), 1725 needs_materialization_(true) {} 1726 1727 bool NeedsMaterialization() const { return needs_materialization_; } 1728 void ClearNeedsMaterialization() { needs_materialization_ = false; } 1729 1730 // For code generation purposes, returns whether this instruction is just before 1731 // `instruction`, and disregard moves in between. 1732 bool IsBeforeWhenDisregardMoves(HInstruction* instruction) const; 1733 1734 DECLARE_INSTRUCTION(Condition); 1735 1736 virtual IfCondition GetCondition() const = 0; 1737 1738 private: 1739 // For register allocation purposes, returns whether this instruction needs to be 1740 // materialized (that is, not just be in the processor flags). 1741 bool needs_materialization_; 1742 1743 DISALLOW_COPY_AND_ASSIGN(HCondition); 1744}; 1745 1746// Instruction to check if two inputs are equal to each other. 1747class HEqual : public HCondition { 1748 public: 1749 HEqual(HInstruction* first, HInstruction* second) 1750 : HCondition(first, second) {} 1751 1752 bool IsCommutative() const OVERRIDE { return true; } 1753 1754 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1755 return x == y ? 1 : 0; 1756 } 1757 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1758 return x == y ? 1 : 0; 1759 } 1760 1761 DECLARE_INSTRUCTION(Equal); 1762 1763 IfCondition GetCondition() const OVERRIDE { 1764 return kCondEQ; 1765 } 1766 1767 private: 1768 DISALLOW_COPY_AND_ASSIGN(HEqual); 1769}; 1770 1771class HNotEqual : public HCondition { 1772 public: 1773 HNotEqual(HInstruction* first, HInstruction* second) 1774 : HCondition(first, second) {} 1775 1776 bool IsCommutative() const OVERRIDE { return true; } 1777 1778 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1779 return x != y ? 1 : 0; 1780 } 1781 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1782 return x != y ? 1 : 0; 1783 } 1784 1785 DECLARE_INSTRUCTION(NotEqual); 1786 1787 IfCondition GetCondition() const OVERRIDE { 1788 return kCondNE; 1789 } 1790 1791 private: 1792 DISALLOW_COPY_AND_ASSIGN(HNotEqual); 1793}; 1794 1795class HLessThan : public HCondition { 1796 public: 1797 HLessThan(HInstruction* first, HInstruction* second) 1798 : HCondition(first, second) {} 1799 1800 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1801 return x < y ? 1 : 0; 1802 } 1803 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1804 return x < y ? 1 : 0; 1805 } 1806 1807 DECLARE_INSTRUCTION(LessThan); 1808 1809 IfCondition GetCondition() const OVERRIDE { 1810 return kCondLT; 1811 } 1812 1813 private: 1814 DISALLOW_COPY_AND_ASSIGN(HLessThan); 1815}; 1816 1817class HLessThanOrEqual : public HCondition { 1818 public: 1819 HLessThanOrEqual(HInstruction* first, HInstruction* second) 1820 : HCondition(first, second) {} 1821 1822 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1823 return x <= y ? 1 : 0; 1824 } 1825 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1826 return x <= y ? 1 : 0; 1827 } 1828 1829 DECLARE_INSTRUCTION(LessThanOrEqual); 1830 1831 IfCondition GetCondition() const OVERRIDE { 1832 return kCondLE; 1833 } 1834 1835 private: 1836 DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual); 1837}; 1838 1839class HGreaterThan : public HCondition { 1840 public: 1841 HGreaterThan(HInstruction* first, HInstruction* second) 1842 : HCondition(first, second) {} 1843 1844 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1845 return x > y ? 1 : 0; 1846 } 1847 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1848 return x > y ? 1 : 0; 1849 } 1850 1851 DECLARE_INSTRUCTION(GreaterThan); 1852 1853 IfCondition GetCondition() const OVERRIDE { 1854 return kCondGT; 1855 } 1856 1857 private: 1858 DISALLOW_COPY_AND_ASSIGN(HGreaterThan); 1859}; 1860 1861class HGreaterThanOrEqual : public HCondition { 1862 public: 1863 HGreaterThanOrEqual(HInstruction* first, HInstruction* second) 1864 : HCondition(first, second) {} 1865 1866 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1867 return x >= y ? 1 : 0; 1868 } 1869 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1870 return x >= y ? 1 : 0; 1871 } 1872 1873 DECLARE_INSTRUCTION(GreaterThanOrEqual); 1874 1875 IfCondition GetCondition() const OVERRIDE { 1876 return kCondGE; 1877 } 1878 1879 private: 1880 DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual); 1881}; 1882 1883 1884// Instruction to check how two inputs compare to each other. 1885// Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1. 1886class HCompare : public HBinaryOperation { 1887 public: 1888 // The bias applies for floating point operations and indicates how NaN 1889 // comparisons are treated: 1890 enum Bias { 1891 kNoBias, // bias is not applicable (i.e. for long operation) 1892 kGtBias, // return 1 for NaN comparisons 1893 kLtBias, // return -1 for NaN comparisons 1894 }; 1895 1896 HCompare(Primitive::Type type, HInstruction* first, HInstruction* second, Bias bias) 1897 : HBinaryOperation(Primitive::kPrimInt, first, second), bias_(bias) { 1898 DCHECK_EQ(type, first->GetType()); 1899 DCHECK_EQ(type, second->GetType()); 1900 } 1901 1902 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1903 return 1904 x == y ? 0 : 1905 x > y ? 1 : 1906 -1; 1907 } 1908 1909 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1910 return 1911 x == y ? 0 : 1912 x > y ? 1 : 1913 -1; 1914 } 1915 1916 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 1917 return bias_ == other->AsCompare()->bias_; 1918 } 1919 1920 bool IsGtBias() { return bias_ == kGtBias; } 1921 1922 DECLARE_INSTRUCTION(Compare); 1923 1924 private: 1925 const Bias bias_; 1926 1927 DISALLOW_COPY_AND_ASSIGN(HCompare); 1928}; 1929 1930// A local in the graph. Corresponds to a Dex register. 1931class HLocal : public HTemplateInstruction<0> { 1932 public: 1933 explicit HLocal(uint16_t reg_number) 1934 : HTemplateInstruction(SideEffects::None()), reg_number_(reg_number) {} 1935 1936 DECLARE_INSTRUCTION(Local); 1937 1938 uint16_t GetRegNumber() const { return reg_number_; } 1939 1940 private: 1941 // The Dex register number. 1942 const uint16_t reg_number_; 1943 1944 DISALLOW_COPY_AND_ASSIGN(HLocal); 1945}; 1946 1947// Load a given local. The local is an input of this instruction. 1948class HLoadLocal : public HExpression<1> { 1949 public: 1950 HLoadLocal(HLocal* local, Primitive::Type type) 1951 : HExpression(type, SideEffects::None()) { 1952 SetRawInputAt(0, local); 1953 } 1954 1955 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 1956 1957 DECLARE_INSTRUCTION(LoadLocal); 1958 1959 private: 1960 DISALLOW_COPY_AND_ASSIGN(HLoadLocal); 1961}; 1962 1963// Store a value in a given local. This instruction has two inputs: the value 1964// and the local. 1965class HStoreLocal : public HTemplateInstruction<2> { 1966 public: 1967 HStoreLocal(HLocal* local, HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 1968 SetRawInputAt(0, local); 1969 SetRawInputAt(1, value); 1970 } 1971 1972 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 1973 1974 DECLARE_INSTRUCTION(StoreLocal); 1975 1976 private: 1977 DISALLOW_COPY_AND_ASSIGN(HStoreLocal); 1978}; 1979 1980class HConstant : public HExpression<0> { 1981 public: 1982 explicit HConstant(Primitive::Type type) : HExpression(type, SideEffects::None()) {} 1983 1984 bool CanBeMoved() const OVERRIDE { return true; } 1985 1986 virtual bool IsMinusOne() const { return false; } 1987 virtual bool IsZero() const { return false; } 1988 virtual bool IsOne() const { return false; } 1989 1990 DECLARE_INSTRUCTION(Constant); 1991 1992 private: 1993 DISALLOW_COPY_AND_ASSIGN(HConstant); 1994}; 1995 1996class HFloatConstant : public HConstant { 1997 public: 1998 float GetValue() const { return value_; } 1999 2000 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2001 return bit_cast<uint32_t, float>(other->AsFloatConstant()->value_) == 2002 bit_cast<uint32_t, float>(value_); 2003 } 2004 2005 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2006 2007 bool IsMinusOne() const OVERRIDE { 2008 return bit_cast<uint32_t, float>(AsFloatConstant()->GetValue()) == 2009 bit_cast<uint32_t, float>((-1.0f)); 2010 } 2011 bool IsZero() const OVERRIDE { 2012 return AsFloatConstant()->GetValue() == 0.0f; 2013 } 2014 bool IsOne() const OVERRIDE { 2015 return bit_cast<uint32_t, float>(AsFloatConstant()->GetValue()) == 2016 bit_cast<uint32_t, float>(1.0f); 2017 } 2018 2019 DECLARE_INSTRUCTION(FloatConstant); 2020 2021 private: 2022 explicit HFloatConstant(float value) : HConstant(Primitive::kPrimFloat), value_(value) {} 2023 2024 const float value_; 2025 2026 // Only the SsaBuilder can currently create floating-point constants. If we 2027 // ever need to create them later in the pipeline, we will have to handle them 2028 // the same way as integral constants. 2029 friend class SsaBuilder; 2030 DISALLOW_COPY_AND_ASSIGN(HFloatConstant); 2031}; 2032 2033class HDoubleConstant : public HConstant { 2034 public: 2035 double GetValue() const { return value_; } 2036 2037 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2038 return bit_cast<uint64_t, double>(other->AsDoubleConstant()->value_) == 2039 bit_cast<uint64_t, double>(value_); 2040 } 2041 2042 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2043 2044 bool IsMinusOne() const OVERRIDE { 2045 return bit_cast<uint64_t, double>(AsDoubleConstant()->GetValue()) == 2046 bit_cast<uint64_t, double>((-1.0)); 2047 } 2048 bool IsZero() const OVERRIDE { 2049 return AsDoubleConstant()->GetValue() == 0.0; 2050 } 2051 bool IsOne() const OVERRIDE { 2052 return bit_cast<uint64_t, double>(AsDoubleConstant()->GetValue()) == 2053 bit_cast<uint64_t, double>(1.0); 2054 } 2055 2056 DECLARE_INSTRUCTION(DoubleConstant); 2057 2058 private: 2059 explicit HDoubleConstant(double value) : HConstant(Primitive::kPrimDouble), value_(value) {} 2060 2061 const double value_; 2062 2063 // Only the SsaBuilder can currently create floating-point constants. If we 2064 // ever need to create them later in the pipeline, we will have to handle them 2065 // the same way as integral constants. 2066 friend class SsaBuilder; 2067 DISALLOW_COPY_AND_ASSIGN(HDoubleConstant); 2068}; 2069 2070class HNullConstant : public HConstant { 2071 public: 2072 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2073 return true; 2074 } 2075 2076 size_t ComputeHashCode() const OVERRIDE { return 0; } 2077 2078 bool ActAsNullConstant() const OVERRIDE { return true; } 2079 2080 DECLARE_INSTRUCTION(NullConstant); 2081 2082 private: 2083 HNullConstant() : HConstant(Primitive::kPrimNot) {} 2084 2085 friend class HGraph; 2086 DISALLOW_COPY_AND_ASSIGN(HNullConstant); 2087}; 2088 2089// Constants of the type int. Those can be from Dex instructions, or 2090// synthesized (for example with the if-eqz instruction). 2091class HIntConstant : public HConstant { 2092 public: 2093 int32_t GetValue() const { return value_; } 2094 2095 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2096 return other->AsIntConstant()->value_ == value_; 2097 } 2098 2099 size_t ComputeHashCode() const OVERRIDE { return GetValue(); } 2100 2101 // TODO: Null is represented by the `0` constant. In most cases we replace it 2102 // with a HNullConstant but we don't do it when comparing (a != null). This 2103 // method is an workaround until we fix the above. 2104 bool ActAsNullConstant() const OVERRIDE { return value_ == 0; } 2105 2106 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2107 bool IsZero() const OVERRIDE { return GetValue() == 0; } 2108 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2109 2110 DECLARE_INSTRUCTION(IntConstant); 2111 2112 private: 2113 explicit HIntConstant(int32_t value) : HConstant(Primitive::kPrimInt), value_(value) {} 2114 2115 const int32_t value_; 2116 2117 friend class HGraph; 2118 ART_FRIEND_TEST(GraphTest, InsertInstructionBefore); 2119 ART_FRIEND_TYPED_TEST(ParallelMoveTest, ConstantLast); 2120 DISALLOW_COPY_AND_ASSIGN(HIntConstant); 2121}; 2122 2123class HLongConstant : public HConstant { 2124 public: 2125 int64_t GetValue() const { return value_; } 2126 2127 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2128 return other->AsLongConstant()->value_ == value_; 2129 } 2130 2131 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2132 2133 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2134 bool IsZero() const OVERRIDE { return GetValue() == 0; } 2135 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2136 2137 DECLARE_INSTRUCTION(LongConstant); 2138 2139 private: 2140 explicit HLongConstant(int64_t value) : HConstant(Primitive::kPrimLong), value_(value) {} 2141 2142 const int64_t value_; 2143 2144 friend class HGraph; 2145 DISALLOW_COPY_AND_ASSIGN(HLongConstant); 2146}; 2147 2148enum class Intrinsics { 2149#define OPTIMIZING_INTRINSICS(Name, IsStatic) k ## Name, 2150#include "intrinsics_list.h" 2151 kNone, 2152 INTRINSICS_LIST(OPTIMIZING_INTRINSICS) 2153#undef INTRINSICS_LIST 2154#undef OPTIMIZING_INTRINSICS 2155}; 2156std::ostream& operator<<(std::ostream& os, const Intrinsics& intrinsic); 2157 2158class HInvoke : public HInstruction { 2159 public: 2160 size_t InputCount() const OVERRIDE { return inputs_.Size(); } 2161 2162 // Runtime needs to walk the stack, so Dex -> Dex calls need to 2163 // know their environment. 2164 bool NeedsEnvironment() const OVERRIDE { return true; } 2165 2166 void SetArgumentAt(size_t index, HInstruction* argument) { 2167 SetRawInputAt(index, argument); 2168 } 2169 2170 Primitive::Type GetType() const OVERRIDE { return return_type_; } 2171 2172 uint32_t GetDexPc() const { return dex_pc_; } 2173 2174 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 2175 2176 Intrinsics GetIntrinsic() const { 2177 return intrinsic_; 2178 } 2179 2180 void SetIntrinsic(Intrinsics intrinsic) { 2181 intrinsic_ = intrinsic; 2182 } 2183 2184 DECLARE_INSTRUCTION(Invoke); 2185 2186 protected: 2187 HInvoke(ArenaAllocator* arena, 2188 uint32_t number_of_arguments, 2189 Primitive::Type return_type, 2190 uint32_t dex_pc, 2191 uint32_t dex_method_index) 2192 : HInstruction(SideEffects::All()), 2193 inputs_(arena, number_of_arguments), 2194 return_type_(return_type), 2195 dex_pc_(dex_pc), 2196 dex_method_index_(dex_method_index), 2197 intrinsic_(Intrinsics::kNone) { 2198 inputs_.SetSize(number_of_arguments); 2199 } 2200 2201 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); } 2202 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE { 2203 inputs_.Put(index, input); 2204 } 2205 2206 GrowableArray<HUserRecord<HInstruction*> > inputs_; 2207 const Primitive::Type return_type_; 2208 const uint32_t dex_pc_; 2209 const uint32_t dex_method_index_; 2210 Intrinsics intrinsic_; 2211 2212 private: 2213 DISALLOW_COPY_AND_ASSIGN(HInvoke); 2214}; 2215 2216class HInvokeStaticOrDirect : public HInvoke { 2217 public: 2218 HInvokeStaticOrDirect(ArenaAllocator* arena, 2219 uint32_t number_of_arguments, 2220 Primitive::Type return_type, 2221 uint32_t dex_pc, 2222 uint32_t dex_method_index, 2223 bool is_recursive, 2224 InvokeType original_invoke_type, 2225 InvokeType invoke_type) 2226 : HInvoke(arena, number_of_arguments, return_type, dex_pc, dex_method_index), 2227 original_invoke_type_(original_invoke_type), 2228 invoke_type_(invoke_type), 2229 is_recursive_(is_recursive) {} 2230 2231 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2232 UNUSED(obj); 2233 // We access the method via the dex cache so we can't do an implicit null check. 2234 // TODO: for intrinsics we can generate implicit null checks. 2235 return false; 2236 } 2237 2238 InvokeType GetOriginalInvokeType() const { return original_invoke_type_; } 2239 InvokeType GetInvokeType() const { return invoke_type_; } 2240 bool IsRecursive() const { return is_recursive_; } 2241 bool NeedsDexCache() const OVERRIDE { return !IsRecursive(); } 2242 2243 DECLARE_INSTRUCTION(InvokeStaticOrDirect); 2244 2245 private: 2246 const InvokeType original_invoke_type_; 2247 const InvokeType invoke_type_; 2248 const bool is_recursive_; 2249 2250 DISALLOW_COPY_AND_ASSIGN(HInvokeStaticOrDirect); 2251}; 2252 2253class HInvokeVirtual : public HInvoke { 2254 public: 2255 HInvokeVirtual(ArenaAllocator* arena, 2256 uint32_t number_of_arguments, 2257 Primitive::Type return_type, 2258 uint32_t dex_pc, 2259 uint32_t dex_method_index, 2260 uint32_t vtable_index) 2261 : HInvoke(arena, number_of_arguments, return_type, dex_pc, dex_method_index), 2262 vtable_index_(vtable_index) {} 2263 2264 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2265 // TODO: Add implicit null checks in intrinsics. 2266 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 2267 } 2268 2269 uint32_t GetVTableIndex() const { return vtable_index_; } 2270 2271 DECLARE_INSTRUCTION(InvokeVirtual); 2272 2273 private: 2274 const uint32_t vtable_index_; 2275 2276 DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual); 2277}; 2278 2279class HInvokeInterface : public HInvoke { 2280 public: 2281 HInvokeInterface(ArenaAllocator* arena, 2282 uint32_t number_of_arguments, 2283 Primitive::Type return_type, 2284 uint32_t dex_pc, 2285 uint32_t dex_method_index, 2286 uint32_t imt_index) 2287 : HInvoke(arena, number_of_arguments, return_type, dex_pc, dex_method_index), 2288 imt_index_(imt_index) {} 2289 2290 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2291 // TODO: Add implicit null checks in intrinsics. 2292 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 2293 } 2294 2295 uint32_t GetImtIndex() const { return imt_index_; } 2296 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 2297 2298 DECLARE_INSTRUCTION(InvokeInterface); 2299 2300 private: 2301 const uint32_t imt_index_; 2302 2303 DISALLOW_COPY_AND_ASSIGN(HInvokeInterface); 2304}; 2305 2306class HNewInstance : public HExpression<0> { 2307 public: 2308 HNewInstance(uint32_t dex_pc, uint16_t type_index, QuickEntrypointEnum entrypoint) 2309 : HExpression(Primitive::kPrimNot, SideEffects::None()), 2310 dex_pc_(dex_pc), 2311 type_index_(type_index), 2312 entrypoint_(entrypoint) {} 2313 2314 uint32_t GetDexPc() const { return dex_pc_; } 2315 uint16_t GetTypeIndex() const { return type_index_; } 2316 2317 // Calls runtime so needs an environment. 2318 bool NeedsEnvironment() const OVERRIDE { return true; } 2319 // It may throw when called on: 2320 // - interfaces 2321 // - abstract/innaccessible/unknown classes 2322 // TODO: optimize when possible. 2323 bool CanThrow() const OVERRIDE { return true; } 2324 2325 bool CanBeNull() const OVERRIDE { return false; } 2326 2327 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 2328 2329 DECLARE_INSTRUCTION(NewInstance); 2330 2331 private: 2332 const uint32_t dex_pc_; 2333 const uint16_t type_index_; 2334 const QuickEntrypointEnum entrypoint_; 2335 2336 DISALLOW_COPY_AND_ASSIGN(HNewInstance); 2337}; 2338 2339class HNeg : public HUnaryOperation { 2340 public: 2341 explicit HNeg(Primitive::Type result_type, HInstruction* input) 2342 : HUnaryOperation(result_type, input) {} 2343 2344 int32_t Evaluate(int32_t x) const OVERRIDE { return -x; } 2345 int64_t Evaluate(int64_t x) const OVERRIDE { return -x; } 2346 2347 DECLARE_INSTRUCTION(Neg); 2348 2349 private: 2350 DISALLOW_COPY_AND_ASSIGN(HNeg); 2351}; 2352 2353class HNewArray : public HExpression<1> { 2354 public: 2355 HNewArray(HInstruction* length, 2356 uint32_t dex_pc, 2357 uint16_t type_index, 2358 QuickEntrypointEnum entrypoint) 2359 : HExpression(Primitive::kPrimNot, SideEffects::None()), 2360 dex_pc_(dex_pc), 2361 type_index_(type_index), 2362 entrypoint_(entrypoint) { 2363 SetRawInputAt(0, length); 2364 } 2365 2366 uint32_t GetDexPc() const { return dex_pc_; } 2367 uint16_t GetTypeIndex() const { return type_index_; } 2368 2369 // Calls runtime so needs an environment. 2370 bool NeedsEnvironment() const OVERRIDE { return true; } 2371 2372 // May throw NegativeArraySizeException, OutOfMemoryError, etc. 2373 bool CanThrow() const OVERRIDE { return true; } 2374 2375 bool CanBeNull() const OVERRIDE { return false; } 2376 2377 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 2378 2379 DECLARE_INSTRUCTION(NewArray); 2380 2381 private: 2382 const uint32_t dex_pc_; 2383 const uint16_t type_index_; 2384 const QuickEntrypointEnum entrypoint_; 2385 2386 DISALLOW_COPY_AND_ASSIGN(HNewArray); 2387}; 2388 2389class HAdd : public HBinaryOperation { 2390 public: 2391 HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2392 : HBinaryOperation(result_type, left, right) {} 2393 2394 bool IsCommutative() const OVERRIDE { return true; } 2395 2396 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2397 return x + y; 2398 } 2399 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2400 return x + y; 2401 } 2402 2403 DECLARE_INSTRUCTION(Add); 2404 2405 private: 2406 DISALLOW_COPY_AND_ASSIGN(HAdd); 2407}; 2408 2409class HSub : public HBinaryOperation { 2410 public: 2411 HSub(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2412 : HBinaryOperation(result_type, left, right) {} 2413 2414 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2415 return x - y; 2416 } 2417 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2418 return x - y; 2419 } 2420 2421 DECLARE_INSTRUCTION(Sub); 2422 2423 private: 2424 DISALLOW_COPY_AND_ASSIGN(HSub); 2425}; 2426 2427class HMul : public HBinaryOperation { 2428 public: 2429 HMul(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2430 : HBinaryOperation(result_type, left, right) {} 2431 2432 bool IsCommutative() const OVERRIDE { return true; } 2433 2434 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x * y; } 2435 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x * y; } 2436 2437 DECLARE_INSTRUCTION(Mul); 2438 2439 private: 2440 DISALLOW_COPY_AND_ASSIGN(HMul); 2441}; 2442 2443class HDiv : public HBinaryOperation { 2444 public: 2445 HDiv(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc) 2446 : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {} 2447 2448 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2449 // Our graph structure ensures we never have 0 for `y` during constant folding. 2450 DCHECK_NE(y, 0); 2451 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2452 return (y == -1) ? -x : x / y; 2453 } 2454 2455 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2456 DCHECK_NE(y, 0); 2457 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2458 return (y == -1) ? -x : x / y; 2459 } 2460 2461 uint32_t GetDexPc() const { return dex_pc_; } 2462 2463 DECLARE_INSTRUCTION(Div); 2464 2465 private: 2466 const uint32_t dex_pc_; 2467 2468 DISALLOW_COPY_AND_ASSIGN(HDiv); 2469}; 2470 2471class HRem : public HBinaryOperation { 2472 public: 2473 HRem(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc) 2474 : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {} 2475 2476 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2477 DCHECK_NE(y, 0); 2478 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2479 return (y == -1) ? 0 : x % y; 2480 } 2481 2482 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2483 DCHECK_NE(y, 0); 2484 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2485 return (y == -1) ? 0 : x % y; 2486 } 2487 2488 uint32_t GetDexPc() const { return dex_pc_; } 2489 2490 DECLARE_INSTRUCTION(Rem); 2491 2492 private: 2493 const uint32_t dex_pc_; 2494 2495 DISALLOW_COPY_AND_ASSIGN(HRem); 2496}; 2497 2498class HDivZeroCheck : public HExpression<1> { 2499 public: 2500 HDivZeroCheck(HInstruction* value, uint32_t dex_pc) 2501 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 2502 SetRawInputAt(0, value); 2503 } 2504 2505 bool CanBeMoved() const OVERRIDE { return true; } 2506 2507 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2508 UNUSED(other); 2509 return true; 2510 } 2511 2512 bool NeedsEnvironment() const OVERRIDE { return true; } 2513 bool CanThrow() const OVERRIDE { return true; } 2514 2515 uint32_t GetDexPc() const { return dex_pc_; } 2516 2517 DECLARE_INSTRUCTION(DivZeroCheck); 2518 2519 private: 2520 const uint32_t dex_pc_; 2521 2522 DISALLOW_COPY_AND_ASSIGN(HDivZeroCheck); 2523}; 2524 2525class HShl : public HBinaryOperation { 2526 public: 2527 HShl(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2528 : HBinaryOperation(result_type, left, right) {} 2529 2530 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x << (y & kMaxIntShiftValue); } 2531 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x << (y & kMaxLongShiftValue); } 2532 2533 DECLARE_INSTRUCTION(Shl); 2534 2535 private: 2536 DISALLOW_COPY_AND_ASSIGN(HShl); 2537}; 2538 2539class HShr : public HBinaryOperation { 2540 public: 2541 HShr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2542 : HBinaryOperation(result_type, left, right) {} 2543 2544 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x >> (y & kMaxIntShiftValue); } 2545 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x >> (y & kMaxLongShiftValue); } 2546 2547 DECLARE_INSTRUCTION(Shr); 2548 2549 private: 2550 DISALLOW_COPY_AND_ASSIGN(HShr); 2551}; 2552 2553class HUShr : public HBinaryOperation { 2554 public: 2555 HUShr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2556 : HBinaryOperation(result_type, left, right) {} 2557 2558 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2559 uint32_t ux = static_cast<uint32_t>(x); 2560 uint32_t uy = static_cast<uint32_t>(y) & kMaxIntShiftValue; 2561 return static_cast<int32_t>(ux >> uy); 2562 } 2563 2564 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2565 uint64_t ux = static_cast<uint64_t>(x); 2566 uint64_t uy = static_cast<uint64_t>(y) & kMaxLongShiftValue; 2567 return static_cast<int64_t>(ux >> uy); 2568 } 2569 2570 DECLARE_INSTRUCTION(UShr); 2571 2572 private: 2573 DISALLOW_COPY_AND_ASSIGN(HUShr); 2574}; 2575 2576class HAnd : public HBinaryOperation { 2577 public: 2578 HAnd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2579 : HBinaryOperation(result_type, left, right) {} 2580 2581 bool IsCommutative() const OVERRIDE { return true; } 2582 2583 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x & y; } 2584 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x & y; } 2585 2586 DECLARE_INSTRUCTION(And); 2587 2588 private: 2589 DISALLOW_COPY_AND_ASSIGN(HAnd); 2590}; 2591 2592class HOr : public HBinaryOperation { 2593 public: 2594 HOr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2595 : HBinaryOperation(result_type, left, right) {} 2596 2597 bool IsCommutative() const OVERRIDE { return true; } 2598 2599 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x | y; } 2600 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x | y; } 2601 2602 DECLARE_INSTRUCTION(Or); 2603 2604 private: 2605 DISALLOW_COPY_AND_ASSIGN(HOr); 2606}; 2607 2608class HXor : public HBinaryOperation { 2609 public: 2610 HXor(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2611 : HBinaryOperation(result_type, left, right) {} 2612 2613 bool IsCommutative() const OVERRIDE { return true; } 2614 2615 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x ^ y; } 2616 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x ^ y; } 2617 2618 DECLARE_INSTRUCTION(Xor); 2619 2620 private: 2621 DISALLOW_COPY_AND_ASSIGN(HXor); 2622}; 2623 2624// The value of a parameter in this method. Its location depends on 2625// the calling convention. 2626class HParameterValue : public HExpression<0> { 2627 public: 2628 HParameterValue(uint8_t index, Primitive::Type parameter_type, bool is_this = false) 2629 : HExpression(parameter_type, SideEffects::None()), index_(index), is_this_(is_this) {} 2630 2631 uint8_t GetIndex() const { return index_; } 2632 2633 bool CanBeNull() const OVERRIDE { return !is_this_; } 2634 2635 DECLARE_INSTRUCTION(ParameterValue); 2636 2637 private: 2638 // The index of this parameter in the parameters list. Must be less 2639 // than HGraph::number_of_in_vregs_. 2640 const uint8_t index_; 2641 2642 // Whether or not the parameter value corresponds to 'this' argument. 2643 const bool is_this_; 2644 2645 DISALLOW_COPY_AND_ASSIGN(HParameterValue); 2646}; 2647 2648class HNot : public HUnaryOperation { 2649 public: 2650 explicit HNot(Primitive::Type result_type, HInstruction* input) 2651 : HUnaryOperation(result_type, input) {} 2652 2653 bool CanBeMoved() const OVERRIDE { return true; } 2654 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2655 UNUSED(other); 2656 return true; 2657 } 2658 2659 int32_t Evaluate(int32_t x) const OVERRIDE { return ~x; } 2660 int64_t Evaluate(int64_t x) const OVERRIDE { return ~x; } 2661 2662 DECLARE_INSTRUCTION(Not); 2663 2664 private: 2665 DISALLOW_COPY_AND_ASSIGN(HNot); 2666}; 2667 2668class HBooleanNot : public HUnaryOperation { 2669 public: 2670 explicit HBooleanNot(HInstruction* input) 2671 : HUnaryOperation(Primitive::Type::kPrimBoolean, input) {} 2672 2673 bool CanBeMoved() const OVERRIDE { return true; } 2674 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2675 UNUSED(other); 2676 return true; 2677 } 2678 2679 int32_t Evaluate(int32_t x) const OVERRIDE { 2680 DCHECK(IsUint<1>(x)); 2681 return !x; 2682 } 2683 2684 int64_t Evaluate(int64_t x ATTRIBUTE_UNUSED) const OVERRIDE { 2685 LOG(FATAL) << DebugName() << " cannot be used with 64-bit values"; 2686 UNREACHABLE(); 2687 } 2688 2689 DECLARE_INSTRUCTION(BooleanNot); 2690 2691 private: 2692 DISALLOW_COPY_AND_ASSIGN(HBooleanNot); 2693}; 2694 2695class HTypeConversion : public HExpression<1> { 2696 public: 2697 // Instantiate a type conversion of `input` to `result_type`. 2698 HTypeConversion(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc) 2699 : HExpression(result_type, SideEffects::None()), dex_pc_(dex_pc) { 2700 SetRawInputAt(0, input); 2701 DCHECK_NE(input->GetType(), result_type); 2702 } 2703 2704 HInstruction* GetInput() const { return InputAt(0); } 2705 Primitive::Type GetInputType() const { return GetInput()->GetType(); } 2706 Primitive::Type GetResultType() const { return GetType(); } 2707 2708 // Required by the x86 and ARM code generators when producing calls 2709 // to the runtime. 2710 uint32_t GetDexPc() const { return dex_pc_; } 2711 2712 bool CanBeMoved() const OVERRIDE { return true; } 2713 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { return true; } 2714 2715 DECLARE_INSTRUCTION(TypeConversion); 2716 2717 private: 2718 const uint32_t dex_pc_; 2719 2720 DISALLOW_COPY_AND_ASSIGN(HTypeConversion); 2721}; 2722 2723static constexpr uint32_t kNoRegNumber = -1; 2724 2725class HPhi : public HInstruction { 2726 public: 2727 HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type) 2728 : HInstruction(SideEffects::None()), 2729 inputs_(arena, number_of_inputs), 2730 reg_number_(reg_number), 2731 type_(type), 2732 is_live_(false), 2733 can_be_null_(true) { 2734 inputs_.SetSize(number_of_inputs); 2735 } 2736 2737 // Returns a type equivalent to the given `type`, but that a `HPhi` can hold. 2738 static Primitive::Type ToPhiType(Primitive::Type type) { 2739 switch (type) { 2740 case Primitive::kPrimBoolean: 2741 case Primitive::kPrimByte: 2742 case Primitive::kPrimShort: 2743 case Primitive::kPrimChar: 2744 return Primitive::kPrimInt; 2745 default: 2746 return type; 2747 } 2748 } 2749 2750 size_t InputCount() const OVERRIDE { return inputs_.Size(); } 2751 2752 void AddInput(HInstruction* input); 2753 2754 Primitive::Type GetType() const OVERRIDE { return type_; } 2755 void SetType(Primitive::Type type) { type_ = type; } 2756 2757 bool CanBeNull() const OVERRIDE { return can_be_null_; } 2758 void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; } 2759 2760 uint32_t GetRegNumber() const { return reg_number_; } 2761 2762 void SetDead() { is_live_ = false; } 2763 void SetLive() { is_live_ = true; } 2764 bool IsDead() const { return !is_live_; } 2765 bool IsLive() const { return is_live_; } 2766 2767 // Returns the next equivalent phi (starting from the current one) or null if there is none. 2768 // An equivalent phi is a phi having the same dex register and type. 2769 // It assumes that phis with the same dex register are adjacent. 2770 HPhi* GetNextEquivalentPhiWithSameType() { 2771 HInstruction* next = GetNext(); 2772 while (next != nullptr && next->AsPhi()->GetRegNumber() == reg_number_) { 2773 if (next->GetType() == GetType()) { 2774 return next->AsPhi(); 2775 } 2776 next = next->GetNext(); 2777 } 2778 return nullptr; 2779 } 2780 2781 DECLARE_INSTRUCTION(Phi); 2782 2783 protected: 2784 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); } 2785 2786 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE { 2787 inputs_.Put(index, input); 2788 } 2789 2790 private: 2791 GrowableArray<HUserRecord<HInstruction*> > inputs_; 2792 const uint32_t reg_number_; 2793 Primitive::Type type_; 2794 bool is_live_; 2795 bool can_be_null_; 2796 2797 DISALLOW_COPY_AND_ASSIGN(HPhi); 2798}; 2799 2800class HNullCheck : public HExpression<1> { 2801 public: 2802 HNullCheck(HInstruction* value, uint32_t dex_pc) 2803 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 2804 SetRawInputAt(0, value); 2805 } 2806 2807 bool CanBeMoved() const OVERRIDE { return true; } 2808 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2809 UNUSED(other); 2810 return true; 2811 } 2812 2813 bool NeedsEnvironment() const OVERRIDE { return true; } 2814 2815 bool CanThrow() const OVERRIDE { return true; } 2816 2817 bool CanBeNull() const OVERRIDE { return false; } 2818 2819 uint32_t GetDexPc() const { return dex_pc_; } 2820 2821 DECLARE_INSTRUCTION(NullCheck); 2822 2823 private: 2824 const uint32_t dex_pc_; 2825 2826 DISALLOW_COPY_AND_ASSIGN(HNullCheck); 2827}; 2828 2829class FieldInfo : public ValueObject { 2830 public: 2831 FieldInfo(MemberOffset field_offset, Primitive::Type field_type, bool is_volatile) 2832 : field_offset_(field_offset), field_type_(field_type), is_volatile_(is_volatile) {} 2833 2834 MemberOffset GetFieldOffset() const { return field_offset_; } 2835 Primitive::Type GetFieldType() const { return field_type_; } 2836 bool IsVolatile() const { return is_volatile_; } 2837 2838 private: 2839 const MemberOffset field_offset_; 2840 const Primitive::Type field_type_; 2841 const bool is_volatile_; 2842}; 2843 2844class HInstanceFieldGet : public HExpression<1> { 2845 public: 2846 HInstanceFieldGet(HInstruction* value, 2847 Primitive::Type field_type, 2848 MemberOffset field_offset, 2849 bool is_volatile) 2850 : HExpression(field_type, SideEffects::DependsOnSomething()), 2851 field_info_(field_offset, field_type, is_volatile) { 2852 SetRawInputAt(0, value); 2853 } 2854 2855 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 2856 2857 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2858 HInstanceFieldGet* other_get = other->AsInstanceFieldGet(); 2859 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 2860 } 2861 2862 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2863 return (obj == InputAt(0)) && GetFieldOffset().Uint32Value() < kPageSize; 2864 } 2865 2866 size_t ComputeHashCode() const OVERRIDE { 2867 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 2868 } 2869 2870 const FieldInfo& GetFieldInfo() const { return field_info_; } 2871 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 2872 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 2873 bool IsVolatile() const { return field_info_.IsVolatile(); } 2874 2875 DECLARE_INSTRUCTION(InstanceFieldGet); 2876 2877 private: 2878 const FieldInfo field_info_; 2879 2880 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet); 2881}; 2882 2883class HInstanceFieldSet : public HTemplateInstruction<2> { 2884 public: 2885 HInstanceFieldSet(HInstruction* object, 2886 HInstruction* value, 2887 Primitive::Type field_type, 2888 MemberOffset field_offset, 2889 bool is_volatile) 2890 : HTemplateInstruction(SideEffects::ChangesSomething()), 2891 field_info_(field_offset, field_type, is_volatile) { 2892 SetRawInputAt(0, object); 2893 SetRawInputAt(1, value); 2894 } 2895 2896 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2897 return (obj == InputAt(0)) && GetFieldOffset().Uint32Value() < kPageSize; 2898 } 2899 2900 const FieldInfo& GetFieldInfo() const { return field_info_; } 2901 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 2902 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 2903 bool IsVolatile() const { return field_info_.IsVolatile(); } 2904 HInstruction* GetValue() const { return InputAt(1); } 2905 2906 DECLARE_INSTRUCTION(InstanceFieldSet); 2907 2908 private: 2909 const FieldInfo field_info_; 2910 2911 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet); 2912}; 2913 2914class HArrayGet : public HExpression<2> { 2915 public: 2916 HArrayGet(HInstruction* array, HInstruction* index, Primitive::Type type) 2917 : HExpression(type, SideEffects::DependsOnSomething()) { 2918 SetRawInputAt(0, array); 2919 SetRawInputAt(1, index); 2920 } 2921 2922 bool CanBeMoved() const OVERRIDE { return true; } 2923 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2924 UNUSED(other); 2925 return true; 2926 } 2927 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2928 UNUSED(obj); 2929 // TODO: We can be smarter here. 2930 // Currently, the array access is always preceded by an ArrayLength or a NullCheck 2931 // which generates the implicit null check. There are cases when these can be removed 2932 // to produce better code. If we ever add optimizations to do so we should allow an 2933 // implicit check here (as long as the address falls in the first page). 2934 return false; 2935 } 2936 2937 void SetType(Primitive::Type type) { type_ = type; } 2938 2939 HInstruction* GetArray() const { return InputAt(0); } 2940 HInstruction* GetIndex() const { return InputAt(1); } 2941 2942 DECLARE_INSTRUCTION(ArrayGet); 2943 2944 private: 2945 DISALLOW_COPY_AND_ASSIGN(HArrayGet); 2946}; 2947 2948class HArraySet : public HTemplateInstruction<3> { 2949 public: 2950 HArraySet(HInstruction* array, 2951 HInstruction* index, 2952 HInstruction* value, 2953 Primitive::Type expected_component_type, 2954 uint32_t dex_pc) 2955 : HTemplateInstruction(SideEffects::ChangesSomething()), 2956 dex_pc_(dex_pc), 2957 expected_component_type_(expected_component_type), 2958 needs_type_check_(value->GetType() == Primitive::kPrimNot) { 2959 SetRawInputAt(0, array); 2960 SetRawInputAt(1, index); 2961 SetRawInputAt(2, value); 2962 } 2963 2964 bool NeedsEnvironment() const OVERRIDE { 2965 // We currently always call a runtime method to catch array store 2966 // exceptions. 2967 return needs_type_check_; 2968 } 2969 2970 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2971 UNUSED(obj); 2972 // TODO: Same as for ArrayGet. 2973 return false; 2974 } 2975 2976 void ClearNeedsTypeCheck() { 2977 needs_type_check_ = false; 2978 } 2979 2980 bool NeedsTypeCheck() const { return needs_type_check_; } 2981 2982 uint32_t GetDexPc() const { return dex_pc_; } 2983 2984 HInstruction* GetArray() const { return InputAt(0); } 2985 HInstruction* GetIndex() const { return InputAt(1); } 2986 HInstruction* GetValue() const { return InputAt(2); } 2987 2988 Primitive::Type GetComponentType() const { 2989 // The Dex format does not type floating point index operations. Since the 2990 // `expected_component_type_` is set during building and can therefore not 2991 // be correct, we also check what is the value type. If it is a floating 2992 // point type, we must use that type. 2993 Primitive::Type value_type = GetValue()->GetType(); 2994 return ((value_type == Primitive::kPrimFloat) || (value_type == Primitive::kPrimDouble)) 2995 ? value_type 2996 : expected_component_type_; 2997 } 2998 2999 DECLARE_INSTRUCTION(ArraySet); 3000 3001 private: 3002 const uint32_t dex_pc_; 3003 const Primitive::Type expected_component_type_; 3004 bool needs_type_check_; 3005 3006 DISALLOW_COPY_AND_ASSIGN(HArraySet); 3007}; 3008 3009class HArrayLength : public HExpression<1> { 3010 public: 3011 explicit HArrayLength(HInstruction* array) 3012 : HExpression(Primitive::kPrimInt, SideEffects::None()) { 3013 // Note that arrays do not change length, so the instruction does not 3014 // depend on any write. 3015 SetRawInputAt(0, array); 3016 } 3017 3018 bool CanBeMoved() const OVERRIDE { return true; } 3019 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3020 UNUSED(other); 3021 return true; 3022 } 3023 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3024 return obj == InputAt(0); 3025 } 3026 3027 DECLARE_INSTRUCTION(ArrayLength); 3028 3029 private: 3030 DISALLOW_COPY_AND_ASSIGN(HArrayLength); 3031}; 3032 3033class HBoundsCheck : public HExpression<2> { 3034 public: 3035 HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc) 3036 : HExpression(index->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 3037 DCHECK(index->GetType() == Primitive::kPrimInt); 3038 SetRawInputAt(0, index); 3039 SetRawInputAt(1, length); 3040 } 3041 3042 bool CanBeMoved() const OVERRIDE { return true; } 3043 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3044 UNUSED(other); 3045 return true; 3046 } 3047 3048 bool NeedsEnvironment() const OVERRIDE { return true; } 3049 3050 bool CanThrow() const OVERRIDE { return true; } 3051 3052 uint32_t GetDexPc() const { return dex_pc_; } 3053 3054 DECLARE_INSTRUCTION(BoundsCheck); 3055 3056 private: 3057 const uint32_t dex_pc_; 3058 3059 DISALLOW_COPY_AND_ASSIGN(HBoundsCheck); 3060}; 3061 3062/** 3063 * Some DEX instructions are folded into multiple HInstructions that need 3064 * to stay live until the last HInstruction. This class 3065 * is used as a marker for the baseline compiler to ensure its preceding 3066 * HInstruction stays live. `index` represents the stack location index of the 3067 * instruction (the actual offset is computed as index * vreg_size). 3068 */ 3069class HTemporary : public HTemplateInstruction<0> { 3070 public: 3071 explicit HTemporary(size_t index) : HTemplateInstruction(SideEffects::None()), index_(index) {} 3072 3073 size_t GetIndex() const { return index_; } 3074 3075 Primitive::Type GetType() const OVERRIDE { 3076 // The previous instruction is the one that will be stored in the temporary location. 3077 DCHECK(GetPrevious() != nullptr); 3078 return GetPrevious()->GetType(); 3079 } 3080 3081 DECLARE_INSTRUCTION(Temporary); 3082 3083 private: 3084 const size_t index_; 3085 3086 DISALLOW_COPY_AND_ASSIGN(HTemporary); 3087}; 3088 3089class HSuspendCheck : public HTemplateInstruction<0> { 3090 public: 3091 explicit HSuspendCheck(uint32_t dex_pc) 3092 : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc) {} 3093 3094 bool NeedsEnvironment() const OVERRIDE { 3095 return true; 3096 } 3097 3098 uint32_t GetDexPc() const { return dex_pc_; } 3099 3100 DECLARE_INSTRUCTION(SuspendCheck); 3101 3102 private: 3103 const uint32_t dex_pc_; 3104 3105 DISALLOW_COPY_AND_ASSIGN(HSuspendCheck); 3106}; 3107 3108/** 3109 * Instruction to load a Class object. 3110 */ 3111class HLoadClass : public HExpression<0> { 3112 public: 3113 HLoadClass(uint16_t type_index, 3114 bool is_referrers_class, 3115 uint32_t dex_pc) 3116 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3117 type_index_(type_index), 3118 is_referrers_class_(is_referrers_class), 3119 dex_pc_(dex_pc), 3120 generate_clinit_check_(false), 3121 loaded_class_rti_(ReferenceTypeInfo::CreateTop(/* is_exact */ false)) {} 3122 3123 bool CanBeMoved() const OVERRIDE { return true; } 3124 3125 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3126 return other->AsLoadClass()->type_index_ == type_index_; 3127 } 3128 3129 size_t ComputeHashCode() const OVERRIDE { return type_index_; } 3130 3131 uint32_t GetDexPc() const { return dex_pc_; } 3132 uint16_t GetTypeIndex() const { return type_index_; } 3133 bool IsReferrersClass() const { return is_referrers_class_; } 3134 3135 bool NeedsEnvironment() const OVERRIDE { 3136 // Will call runtime and load the class if the class is not loaded yet. 3137 // TODO: finer grain decision. 3138 return !is_referrers_class_; 3139 } 3140 3141 bool MustGenerateClinitCheck() const { 3142 return generate_clinit_check_; 3143 } 3144 3145 void SetMustGenerateClinitCheck() { 3146 generate_clinit_check_ = true; 3147 } 3148 3149 bool CanCallRuntime() const { 3150 return MustGenerateClinitCheck() || !is_referrers_class_; 3151 } 3152 3153 bool CanThrow() const OVERRIDE { 3154 // May call runtime and and therefore can throw. 3155 // TODO: finer grain decision. 3156 return !is_referrers_class_; 3157 } 3158 3159 ReferenceTypeInfo GetLoadedClassRTI() { 3160 return loaded_class_rti_; 3161 } 3162 3163 void SetLoadedClassRTI(ReferenceTypeInfo rti) { 3164 // Make sure we only set exact types (the loaded class should never be merged). 3165 DCHECK(rti.IsExact()); 3166 loaded_class_rti_ = rti; 3167 } 3168 3169 bool IsResolved() { 3170 return loaded_class_rti_.IsExact(); 3171 } 3172 3173 bool NeedsDexCache() const OVERRIDE { return !is_referrers_class_; } 3174 3175 DECLARE_INSTRUCTION(LoadClass); 3176 3177 private: 3178 const uint16_t type_index_; 3179 const bool is_referrers_class_; 3180 const uint32_t dex_pc_; 3181 // Whether this instruction must generate the initialization check. 3182 // Used for code generation. 3183 bool generate_clinit_check_; 3184 3185 ReferenceTypeInfo loaded_class_rti_; 3186 3187 DISALLOW_COPY_AND_ASSIGN(HLoadClass); 3188}; 3189 3190class HLoadString : public HExpression<0> { 3191 public: 3192 HLoadString(uint32_t string_index, uint32_t dex_pc) 3193 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3194 string_index_(string_index), 3195 dex_pc_(dex_pc) {} 3196 3197 bool CanBeMoved() const OVERRIDE { return true; } 3198 3199 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3200 return other->AsLoadString()->string_index_ == string_index_; 3201 } 3202 3203 size_t ComputeHashCode() const OVERRIDE { return string_index_; } 3204 3205 uint32_t GetDexPc() const { return dex_pc_; } 3206 uint32_t GetStringIndex() const { return string_index_; } 3207 3208 // TODO: Can we deopt or debug when we resolve a string? 3209 bool NeedsEnvironment() const OVERRIDE { return false; } 3210 bool NeedsDexCache() const OVERRIDE { return true; } 3211 3212 DECLARE_INSTRUCTION(LoadString); 3213 3214 private: 3215 const uint32_t string_index_; 3216 const uint32_t dex_pc_; 3217 3218 DISALLOW_COPY_AND_ASSIGN(HLoadString); 3219}; 3220 3221// TODO: Pass this check to HInvokeStaticOrDirect nodes. 3222/** 3223 * Performs an initialization check on its Class object input. 3224 */ 3225class HClinitCheck : public HExpression<1> { 3226 public: 3227 explicit HClinitCheck(HLoadClass* constant, uint32_t dex_pc) 3228 : HExpression(Primitive::kPrimNot, SideEffects::ChangesSomething()), 3229 dex_pc_(dex_pc) { 3230 SetRawInputAt(0, constant); 3231 } 3232 3233 bool CanBeMoved() const OVERRIDE { return true; } 3234 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3235 UNUSED(other); 3236 return true; 3237 } 3238 3239 bool NeedsEnvironment() const OVERRIDE { 3240 // May call runtime to initialize the class. 3241 return true; 3242 } 3243 3244 uint32_t GetDexPc() const { return dex_pc_; } 3245 3246 HLoadClass* GetLoadClass() const { return InputAt(0)->AsLoadClass(); } 3247 3248 DECLARE_INSTRUCTION(ClinitCheck); 3249 3250 private: 3251 const uint32_t dex_pc_; 3252 3253 DISALLOW_COPY_AND_ASSIGN(HClinitCheck); 3254}; 3255 3256class HStaticFieldGet : public HExpression<1> { 3257 public: 3258 HStaticFieldGet(HInstruction* cls, 3259 Primitive::Type field_type, 3260 MemberOffset field_offset, 3261 bool is_volatile) 3262 : HExpression(field_type, SideEffects::DependsOnSomething()), 3263 field_info_(field_offset, field_type, is_volatile) { 3264 SetRawInputAt(0, cls); 3265 } 3266 3267 3268 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 3269 3270 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3271 HStaticFieldGet* other_get = other->AsStaticFieldGet(); 3272 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 3273 } 3274 3275 size_t ComputeHashCode() const OVERRIDE { 3276 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 3277 } 3278 3279 const FieldInfo& GetFieldInfo() const { return field_info_; } 3280 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3281 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3282 bool IsVolatile() const { return field_info_.IsVolatile(); } 3283 3284 DECLARE_INSTRUCTION(StaticFieldGet); 3285 3286 private: 3287 const FieldInfo field_info_; 3288 3289 DISALLOW_COPY_AND_ASSIGN(HStaticFieldGet); 3290}; 3291 3292class HStaticFieldSet : public HTemplateInstruction<2> { 3293 public: 3294 HStaticFieldSet(HInstruction* cls, 3295 HInstruction* value, 3296 Primitive::Type field_type, 3297 MemberOffset field_offset, 3298 bool is_volatile) 3299 : HTemplateInstruction(SideEffects::ChangesSomething()), 3300 field_info_(field_offset, field_type, is_volatile) { 3301 SetRawInputAt(0, cls); 3302 SetRawInputAt(1, value); 3303 } 3304 3305 const FieldInfo& GetFieldInfo() const { return field_info_; } 3306 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3307 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3308 bool IsVolatile() const { return field_info_.IsVolatile(); } 3309 3310 HInstruction* GetValue() const { return InputAt(1); } 3311 3312 DECLARE_INSTRUCTION(StaticFieldSet); 3313 3314 private: 3315 const FieldInfo field_info_; 3316 3317 DISALLOW_COPY_AND_ASSIGN(HStaticFieldSet); 3318}; 3319 3320// Implement the move-exception DEX instruction. 3321class HLoadException : public HExpression<0> { 3322 public: 3323 HLoadException() : HExpression(Primitive::kPrimNot, SideEffects::None()) {} 3324 3325 DECLARE_INSTRUCTION(LoadException); 3326 3327 private: 3328 DISALLOW_COPY_AND_ASSIGN(HLoadException); 3329}; 3330 3331class HThrow : public HTemplateInstruction<1> { 3332 public: 3333 HThrow(HInstruction* exception, uint32_t dex_pc) 3334 : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc) { 3335 SetRawInputAt(0, exception); 3336 } 3337 3338 bool IsControlFlow() const OVERRIDE { return true; } 3339 3340 bool NeedsEnvironment() const OVERRIDE { return true; } 3341 3342 bool CanThrow() const OVERRIDE { return true; } 3343 3344 uint32_t GetDexPc() const { return dex_pc_; } 3345 3346 DECLARE_INSTRUCTION(Throw); 3347 3348 private: 3349 const uint32_t dex_pc_; 3350 3351 DISALLOW_COPY_AND_ASSIGN(HThrow); 3352}; 3353 3354class HInstanceOf : public HExpression<2> { 3355 public: 3356 HInstanceOf(HInstruction* object, 3357 HLoadClass* constant, 3358 bool class_is_final, 3359 uint32_t dex_pc) 3360 : HExpression(Primitive::kPrimBoolean, SideEffects::None()), 3361 class_is_final_(class_is_final), 3362 dex_pc_(dex_pc) { 3363 SetRawInputAt(0, object); 3364 SetRawInputAt(1, constant); 3365 } 3366 3367 bool CanBeMoved() const OVERRIDE { return true; } 3368 3369 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 3370 return true; 3371 } 3372 3373 bool NeedsEnvironment() const OVERRIDE { 3374 return false; 3375 } 3376 3377 uint32_t GetDexPc() const { return dex_pc_; } 3378 3379 bool IsClassFinal() const { return class_is_final_; } 3380 3381 DECLARE_INSTRUCTION(InstanceOf); 3382 3383 private: 3384 const bool class_is_final_; 3385 const uint32_t dex_pc_; 3386 3387 DISALLOW_COPY_AND_ASSIGN(HInstanceOf); 3388}; 3389 3390class HBoundType : public HExpression<1> { 3391 public: 3392 HBoundType(HInstruction* input, ReferenceTypeInfo bound_type) 3393 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3394 bound_type_(bound_type) { 3395 DCHECK_EQ(input->GetType(), Primitive::kPrimNot); 3396 SetRawInputAt(0, input); 3397 } 3398 3399 const ReferenceTypeInfo& GetBoundType() const { return bound_type_; } 3400 3401 bool CanBeNull() const OVERRIDE { 3402 // `null instanceof ClassX` always return false so we can't be null. 3403 return false; 3404 } 3405 3406 DECLARE_INSTRUCTION(BoundType); 3407 3408 private: 3409 // Encodes the most upper class that this instruction can have. In other words 3410 // it is always the case that GetBoundType().IsSupertypeOf(GetReferenceType()). 3411 // It is used to bound the type in cases like `if (x instanceof ClassX) {}` 3412 const ReferenceTypeInfo bound_type_; 3413 3414 DISALLOW_COPY_AND_ASSIGN(HBoundType); 3415}; 3416 3417class HCheckCast : public HTemplateInstruction<2> { 3418 public: 3419 HCheckCast(HInstruction* object, 3420 HLoadClass* constant, 3421 bool class_is_final, 3422 uint32_t dex_pc) 3423 : HTemplateInstruction(SideEffects::None()), 3424 class_is_final_(class_is_final), 3425 dex_pc_(dex_pc) { 3426 SetRawInputAt(0, object); 3427 SetRawInputAt(1, constant); 3428 } 3429 3430 bool CanBeMoved() const OVERRIDE { return true; } 3431 3432 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 3433 return true; 3434 } 3435 3436 bool NeedsEnvironment() const OVERRIDE { 3437 // Instruction may throw a CheckCastError. 3438 return true; 3439 } 3440 3441 bool CanThrow() const OVERRIDE { return true; } 3442 3443 uint32_t GetDexPc() const { return dex_pc_; } 3444 3445 bool IsClassFinal() const { return class_is_final_; } 3446 3447 DECLARE_INSTRUCTION(CheckCast); 3448 3449 private: 3450 const bool class_is_final_; 3451 const uint32_t dex_pc_; 3452 3453 DISALLOW_COPY_AND_ASSIGN(HCheckCast); 3454}; 3455 3456class HMemoryBarrier : public HTemplateInstruction<0> { 3457 public: 3458 explicit HMemoryBarrier(MemBarrierKind barrier_kind) 3459 : HTemplateInstruction(SideEffects::None()), 3460 barrier_kind_(barrier_kind) {} 3461 3462 MemBarrierKind GetBarrierKind() { return barrier_kind_; } 3463 3464 DECLARE_INSTRUCTION(MemoryBarrier); 3465 3466 private: 3467 const MemBarrierKind barrier_kind_; 3468 3469 DISALLOW_COPY_AND_ASSIGN(HMemoryBarrier); 3470}; 3471 3472class HMonitorOperation : public HTemplateInstruction<1> { 3473 public: 3474 enum OperationKind { 3475 kEnter, 3476 kExit, 3477 }; 3478 3479 HMonitorOperation(HInstruction* object, OperationKind kind, uint32_t dex_pc) 3480 : HTemplateInstruction(SideEffects::None()), kind_(kind), dex_pc_(dex_pc) { 3481 SetRawInputAt(0, object); 3482 } 3483 3484 // Instruction may throw a Java exception, so we need an environment. 3485 bool NeedsEnvironment() const OVERRIDE { return true; } 3486 bool CanThrow() const OVERRIDE { return true; } 3487 3488 uint32_t GetDexPc() const { return dex_pc_; } 3489 3490 bool IsEnter() const { return kind_ == kEnter; } 3491 3492 DECLARE_INSTRUCTION(MonitorOperation); 3493 3494 private: 3495 const OperationKind kind_; 3496 const uint32_t dex_pc_; 3497 3498 private: 3499 DISALLOW_COPY_AND_ASSIGN(HMonitorOperation); 3500}; 3501 3502class MoveOperands : public ArenaObject<kArenaAllocMisc> { 3503 public: 3504 MoveOperands(Location source, 3505 Location destination, 3506 Primitive::Type type, 3507 HInstruction* instruction) 3508 : source_(source), destination_(destination), type_(type), instruction_(instruction) {} 3509 3510 Location GetSource() const { return source_; } 3511 Location GetDestination() const { return destination_; } 3512 3513 void SetSource(Location value) { source_ = value; } 3514 void SetDestination(Location value) { destination_ = value; } 3515 3516 // The parallel move resolver marks moves as "in-progress" by clearing the 3517 // destination (but not the source). 3518 Location MarkPending() { 3519 DCHECK(!IsPending()); 3520 Location dest = destination_; 3521 destination_ = Location::NoLocation(); 3522 return dest; 3523 } 3524 3525 void ClearPending(Location dest) { 3526 DCHECK(IsPending()); 3527 destination_ = dest; 3528 } 3529 3530 bool IsPending() const { 3531 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 3532 return destination_.IsInvalid() && !source_.IsInvalid(); 3533 } 3534 3535 // True if this blocks a move from the given location. 3536 bool Blocks(Location loc) const { 3537 return !IsEliminated() && source_.OverlapsWith(loc); 3538 } 3539 3540 // A move is redundant if it's been eliminated, if its source and 3541 // destination are the same, or if its destination is unneeded. 3542 bool IsRedundant() const { 3543 return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_); 3544 } 3545 3546 // We clear both operands to indicate move that's been eliminated. 3547 void Eliminate() { 3548 source_ = destination_ = Location::NoLocation(); 3549 } 3550 3551 bool IsEliminated() const { 3552 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 3553 return source_.IsInvalid(); 3554 } 3555 3556 bool Is64BitMove() const { 3557 return Primitive::Is64BitType(type_); 3558 } 3559 3560 HInstruction* GetInstruction() const { return instruction_; } 3561 3562 private: 3563 Location source_; 3564 Location destination_; 3565 // The type this move is for. 3566 Primitive::Type type_; 3567 // The instruction this move is assocatied with. Null when this move is 3568 // for moving an input in the expected locations of user (including a phi user). 3569 // This is only used in debug mode, to ensure we do not connect interval siblings 3570 // in the same parallel move. 3571 HInstruction* instruction_; 3572}; 3573 3574static constexpr size_t kDefaultNumberOfMoves = 4; 3575 3576class HParallelMove : public HTemplateInstruction<0> { 3577 public: 3578 explicit HParallelMove(ArenaAllocator* arena) 3579 : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {} 3580 3581 void AddMove(Location source, 3582 Location destination, 3583 Primitive::Type type, 3584 HInstruction* instruction) { 3585 DCHECK(source.IsValid()); 3586 DCHECK(destination.IsValid()); 3587 if (kIsDebugBuild) { 3588 if (instruction != nullptr) { 3589 for (size_t i = 0, e = moves_.Size(); i < e; ++i) { 3590 if (moves_.Get(i).GetInstruction() == instruction) { 3591 // Special case the situation where the move is for the spill slot 3592 // of the instruction. 3593 if ((GetPrevious() == instruction) 3594 || ((GetPrevious() == nullptr) 3595 && instruction->IsPhi() 3596 && instruction->GetBlock() == GetBlock())) { 3597 DCHECK_NE(destination.GetKind(), moves_.Get(i).GetDestination().GetKind()) 3598 << "Doing parallel moves for the same instruction."; 3599 } else { 3600 DCHECK(false) << "Doing parallel moves for the same instruction."; 3601 } 3602 } 3603 } 3604 } 3605 for (size_t i = 0, e = moves_.Size(); i < e; ++i) { 3606 DCHECK(!destination.OverlapsWith(moves_.Get(i).GetDestination())) 3607 << "Overlapped destination for two moves in a parallel move."; 3608 } 3609 } 3610 moves_.Add(MoveOperands(source, destination, type, instruction)); 3611 } 3612 3613 MoveOperands* MoveOperandsAt(size_t index) const { 3614 return moves_.GetRawStorage() + index; 3615 } 3616 3617 size_t NumMoves() const { return moves_.Size(); } 3618 3619 DECLARE_INSTRUCTION(ParallelMove); 3620 3621 private: 3622 GrowableArray<MoveOperands> moves_; 3623 3624 DISALLOW_COPY_AND_ASSIGN(HParallelMove); 3625}; 3626 3627class HGraphVisitor : public ValueObject { 3628 public: 3629 explicit HGraphVisitor(HGraph* graph) : graph_(graph) {} 3630 virtual ~HGraphVisitor() {} 3631 3632 virtual void VisitInstruction(HInstruction* instruction) { UNUSED(instruction); } 3633 virtual void VisitBasicBlock(HBasicBlock* block); 3634 3635 // Visit the graph following basic block insertion order. 3636 void VisitInsertionOrder(); 3637 3638 // Visit the graph following dominator tree reverse post-order. 3639 void VisitReversePostOrder(); 3640 3641 HGraph* GetGraph() const { return graph_; } 3642 3643 // Visit functions for instruction classes. 3644#define DECLARE_VISIT_INSTRUCTION(name, super) \ 3645 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } 3646 3647 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 3648 3649#undef DECLARE_VISIT_INSTRUCTION 3650 3651 private: 3652 HGraph* const graph_; 3653 3654 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); 3655}; 3656 3657class HGraphDelegateVisitor : public HGraphVisitor { 3658 public: 3659 explicit HGraphDelegateVisitor(HGraph* graph) : HGraphVisitor(graph) {} 3660 virtual ~HGraphDelegateVisitor() {} 3661 3662 // Visit functions that delegate to to super class. 3663#define DECLARE_VISIT_INSTRUCTION(name, super) \ 3664 void Visit##name(H##name* instr) OVERRIDE { Visit##super(instr); } 3665 3666 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 3667 3668#undef DECLARE_VISIT_INSTRUCTION 3669 3670 private: 3671 DISALLOW_COPY_AND_ASSIGN(HGraphDelegateVisitor); 3672}; 3673 3674class HInsertionOrderIterator : public ValueObject { 3675 public: 3676 explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 3677 3678 bool Done() const { return index_ == graph_.GetBlocks().Size(); } 3679 HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); } 3680 void Advance() { ++index_; } 3681 3682 private: 3683 const HGraph& graph_; 3684 size_t index_; 3685 3686 DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator); 3687}; 3688 3689class HReversePostOrderIterator : public ValueObject { 3690 public: 3691 explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) { 3692 // Check that reverse post order of the graph has been built. 3693 DCHECK(!graph.GetReversePostOrder().IsEmpty()); 3694 } 3695 3696 bool Done() const { return index_ == graph_.GetReversePostOrder().Size(); } 3697 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_); } 3698 void Advance() { ++index_; } 3699 3700 private: 3701 const HGraph& graph_; 3702 size_t index_; 3703 3704 DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator); 3705}; 3706 3707class HPostOrderIterator : public ValueObject { 3708 public: 3709 explicit HPostOrderIterator(const HGraph& graph) 3710 : graph_(graph), index_(graph_.GetReversePostOrder().Size()) { 3711 // Check that reverse post order of the graph has been built. 3712 DCHECK(!graph.GetReversePostOrder().IsEmpty()); 3713 } 3714 3715 bool Done() const { return index_ == 0; } 3716 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_ - 1); } 3717 void Advance() { --index_; } 3718 3719 private: 3720 const HGraph& graph_; 3721 size_t index_; 3722 3723 DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); 3724}; 3725 3726class HLinearPostOrderIterator : public ValueObject { 3727 public: 3728 explicit HLinearPostOrderIterator(const HGraph& graph) 3729 : order_(graph.GetLinearOrder()), index_(graph.GetLinearOrder().Size()) {} 3730 3731 bool Done() const { return index_ == 0; } 3732 3733 HBasicBlock* Current() const { return order_.Get(index_ -1); } 3734 3735 void Advance() { 3736 --index_; 3737 DCHECK_GE(index_, 0U); 3738 } 3739 3740 private: 3741 const GrowableArray<HBasicBlock*>& order_; 3742 size_t index_; 3743 3744 DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator); 3745}; 3746 3747class HLinearOrderIterator : public ValueObject { 3748 public: 3749 explicit HLinearOrderIterator(const HGraph& graph) 3750 : order_(graph.GetLinearOrder()), index_(0) {} 3751 3752 bool Done() const { return index_ == order_.Size(); } 3753 HBasicBlock* Current() const { return order_.Get(index_); } 3754 void Advance() { ++index_; } 3755 3756 private: 3757 const GrowableArray<HBasicBlock*>& order_; 3758 size_t index_; 3759 3760 DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator); 3761}; 3762 3763// Iterator over the blocks that art part of the loop. Includes blocks part 3764// of an inner loop. The order in which the blocks are iterated is on their 3765// block id. 3766class HBlocksInLoopIterator : public ValueObject { 3767 public: 3768 explicit HBlocksInLoopIterator(const HLoopInformation& info) 3769 : blocks_in_loop_(info.GetBlocks()), 3770 blocks_(info.GetHeader()->GetGraph()->GetBlocks()), 3771 index_(0) { 3772 if (!blocks_in_loop_.IsBitSet(index_)) { 3773 Advance(); 3774 } 3775 } 3776 3777 bool Done() const { return index_ == blocks_.Size(); } 3778 HBasicBlock* Current() const { return blocks_.Get(index_); } 3779 void Advance() { 3780 ++index_; 3781 for (size_t e = blocks_.Size(); index_ < e; ++index_) { 3782 if (blocks_in_loop_.IsBitSet(index_)) { 3783 break; 3784 } 3785 } 3786 } 3787 3788 private: 3789 const BitVector& blocks_in_loop_; 3790 const GrowableArray<HBasicBlock*>& blocks_; 3791 size_t index_; 3792 3793 DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopIterator); 3794}; 3795 3796inline int64_t Int64FromConstant(HConstant* constant) { 3797 DCHECK(constant->IsIntConstant() || constant->IsLongConstant()); 3798 return constant->IsIntConstant() ? constant->AsIntConstant()->GetValue() 3799 : constant->AsLongConstant()->GetValue(); 3800} 3801 3802} // namespace art 3803 3804#endif // ART_COMPILER_OPTIMIZING_NODES_H_ 3805