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