nodes.h revision 8909bafa5d64e12eb53f3d37b984f53e7a632224
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>(value_) == bit_cast<uint32_t, float>((-1.0f)); 2201 } 2202 bool IsZero() const OVERRIDE { 2203 return value_ == 0.0f; 2204 } 2205 bool IsOne() const OVERRIDE { 2206 return bit_cast<uint32_t, float>(value_) == bit_cast<uint32_t, float>(1.0f); 2207 } 2208 bool IsNaN() const { 2209 return std::isnan(value_); 2210 } 2211 2212 DECLARE_INSTRUCTION(FloatConstant); 2213 2214 private: 2215 explicit HFloatConstant(float value) : HConstant(Primitive::kPrimFloat), value_(value) {} 2216 explicit HFloatConstant(int32_t value) 2217 : HConstant(Primitive::kPrimFloat), value_(bit_cast<float, int32_t>(value)) {} 2218 2219 const float value_; 2220 2221 // Only the SsaBuilder and HGraph can create floating-point constants. 2222 friend class SsaBuilder; 2223 friend class HGraph; 2224 DISALLOW_COPY_AND_ASSIGN(HFloatConstant); 2225}; 2226 2227class HDoubleConstant : public HConstant { 2228 public: 2229 double GetValue() const { return value_; } 2230 2231 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2232 return bit_cast<uint64_t, double>(other->AsDoubleConstant()->value_) == 2233 bit_cast<uint64_t, double>(value_); 2234 } 2235 2236 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2237 2238 bool IsMinusOne() const OVERRIDE { 2239 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>((-1.0)); 2240 } 2241 bool IsZero() const OVERRIDE { 2242 return value_ == 0.0; 2243 } 2244 bool IsOne() const OVERRIDE { 2245 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>(1.0); 2246 } 2247 bool IsNaN() const { 2248 return std::isnan(value_); 2249 } 2250 2251 DECLARE_INSTRUCTION(DoubleConstant); 2252 2253 private: 2254 explicit HDoubleConstant(double value) : HConstant(Primitive::kPrimDouble), value_(value) {} 2255 explicit HDoubleConstant(int64_t value) 2256 : HConstant(Primitive::kPrimDouble), value_(bit_cast<double, int64_t>(value)) {} 2257 2258 const double value_; 2259 2260 // Only the SsaBuilder and HGraph can create floating-point constants. 2261 friend class SsaBuilder; 2262 friend class HGraph; 2263 DISALLOW_COPY_AND_ASSIGN(HDoubleConstant); 2264}; 2265 2266class HNullConstant : public HConstant { 2267 public: 2268 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2269 return true; 2270 } 2271 2272 size_t ComputeHashCode() const OVERRIDE { return 0; } 2273 2274 DECLARE_INSTRUCTION(NullConstant); 2275 2276 private: 2277 HNullConstant() : HConstant(Primitive::kPrimNot) {} 2278 2279 friend class HGraph; 2280 DISALLOW_COPY_AND_ASSIGN(HNullConstant); 2281}; 2282 2283// Constants of the type int. Those can be from Dex instructions, or 2284// synthesized (for example with the if-eqz instruction). 2285class HIntConstant : public HConstant { 2286 public: 2287 int32_t GetValue() const { return value_; } 2288 2289 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2290 return other->AsIntConstant()->value_ == value_; 2291 } 2292 2293 size_t ComputeHashCode() const OVERRIDE { return GetValue(); } 2294 2295 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2296 bool IsZero() const OVERRIDE { return GetValue() == 0; } 2297 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2298 2299 DECLARE_INSTRUCTION(IntConstant); 2300 2301 private: 2302 explicit HIntConstant(int32_t value) : HConstant(Primitive::kPrimInt), value_(value) {} 2303 2304 const int32_t value_; 2305 2306 friend class HGraph; 2307 ART_FRIEND_TEST(GraphTest, InsertInstructionBefore); 2308 ART_FRIEND_TYPED_TEST(ParallelMoveTest, ConstantLast); 2309 DISALLOW_COPY_AND_ASSIGN(HIntConstant); 2310}; 2311 2312class HLongConstant : public HConstant { 2313 public: 2314 int64_t GetValue() const { return value_; } 2315 2316 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2317 return other->AsLongConstant()->value_ == value_; 2318 } 2319 2320 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2321 2322 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2323 bool IsZero() const OVERRIDE { return GetValue() == 0; } 2324 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2325 2326 DECLARE_INSTRUCTION(LongConstant); 2327 2328 private: 2329 explicit HLongConstant(int64_t value) : HConstant(Primitive::kPrimLong), value_(value) {} 2330 2331 const int64_t value_; 2332 2333 friend class HGraph; 2334 DISALLOW_COPY_AND_ASSIGN(HLongConstant); 2335}; 2336 2337enum class Intrinsics { 2338#define OPTIMIZING_INTRINSICS(Name, IsStatic) k ## Name, 2339#include "intrinsics_list.h" 2340 kNone, 2341 INTRINSICS_LIST(OPTIMIZING_INTRINSICS) 2342#undef INTRINSICS_LIST 2343#undef OPTIMIZING_INTRINSICS 2344}; 2345std::ostream& operator<<(std::ostream& os, const Intrinsics& intrinsic); 2346 2347class HInvoke : public HInstruction { 2348 public: 2349 size_t InputCount() const OVERRIDE { return inputs_.Size(); } 2350 2351 // Runtime needs to walk the stack, so Dex -> Dex calls need to 2352 // know their environment. 2353 bool NeedsEnvironment() const OVERRIDE { return true; } 2354 2355 void SetArgumentAt(size_t index, HInstruction* argument) { 2356 SetRawInputAt(index, argument); 2357 } 2358 2359 // Return the number of arguments. This number can be lower than 2360 // the number of inputs returned by InputCount(), as some invoke 2361 // instructions (e.g. HInvokeStaticOrDirect) can have non-argument 2362 // inputs at the end of their list of inputs. 2363 uint32_t GetNumberOfArguments() const { return number_of_arguments_; } 2364 2365 Primitive::Type GetType() const OVERRIDE { return return_type_; } 2366 2367 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2368 2369 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 2370 2371 Intrinsics GetIntrinsic() const { 2372 return intrinsic_; 2373 } 2374 2375 void SetIntrinsic(Intrinsics intrinsic) { 2376 intrinsic_ = intrinsic; 2377 } 2378 2379 DECLARE_INSTRUCTION(Invoke); 2380 2381 protected: 2382 HInvoke(ArenaAllocator* arena, 2383 uint32_t number_of_arguments, 2384 uint32_t number_of_other_inputs, 2385 Primitive::Type return_type, 2386 uint32_t dex_pc, 2387 uint32_t dex_method_index) 2388 : HInstruction(SideEffects::All()), 2389 number_of_arguments_(number_of_arguments), 2390 inputs_(arena, number_of_arguments), 2391 return_type_(return_type), 2392 dex_pc_(dex_pc), 2393 dex_method_index_(dex_method_index), 2394 intrinsic_(Intrinsics::kNone) { 2395 uint32_t number_of_inputs = number_of_arguments + number_of_other_inputs; 2396 inputs_.SetSize(number_of_inputs); 2397 } 2398 2399 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); } 2400 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE { 2401 inputs_.Put(index, input); 2402 } 2403 2404 uint32_t number_of_arguments_; 2405 GrowableArray<HUserRecord<HInstruction*> > inputs_; 2406 const Primitive::Type return_type_; 2407 const uint32_t dex_pc_; 2408 const uint32_t dex_method_index_; 2409 Intrinsics intrinsic_; 2410 2411 private: 2412 DISALLOW_COPY_AND_ASSIGN(HInvoke); 2413}; 2414 2415class HInvokeStaticOrDirect : public HInvoke { 2416 public: 2417 // Requirements of this method call regarding the class 2418 // initialization (clinit) check of its declaring class. 2419 enum class ClinitCheckRequirement { 2420 kNone, // Class already initialized. 2421 kExplicit, // Static call having explicit clinit check as last input. 2422 kImplicit, // Static call implicitly requiring a clinit check. 2423 }; 2424 2425 HInvokeStaticOrDirect(ArenaAllocator* arena, 2426 uint32_t number_of_arguments, 2427 Primitive::Type return_type, 2428 uint32_t dex_pc, 2429 uint32_t dex_method_index, 2430 bool is_recursive, 2431 int32_t string_init_offset, 2432 InvokeType original_invoke_type, 2433 InvokeType invoke_type, 2434 ClinitCheckRequirement clinit_check_requirement) 2435 : HInvoke(arena, 2436 number_of_arguments, 2437 clinit_check_requirement == ClinitCheckRequirement::kExplicit ? 1u : 0u, 2438 return_type, 2439 dex_pc, 2440 dex_method_index), 2441 original_invoke_type_(original_invoke_type), 2442 invoke_type_(invoke_type), 2443 is_recursive_(is_recursive), 2444 clinit_check_requirement_(clinit_check_requirement), 2445 string_init_offset_(string_init_offset) {} 2446 2447 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2448 UNUSED(obj); 2449 // We access the method via the dex cache so we can't do an implicit null check. 2450 // TODO: for intrinsics we can generate implicit null checks. 2451 return false; 2452 } 2453 2454 InvokeType GetOriginalInvokeType() const { return original_invoke_type_; } 2455 InvokeType GetInvokeType() const { return invoke_type_; } 2456 bool IsRecursive() const { return is_recursive_; } 2457 bool NeedsDexCache() const OVERRIDE { return !IsRecursive(); } 2458 bool IsStringInit() const { return string_init_offset_ != 0; } 2459 int32_t GetStringInitOffset() const { return string_init_offset_; } 2460 2461 // Is this instruction a call to a static method? 2462 bool IsStatic() const { 2463 return GetInvokeType() == kStatic; 2464 } 2465 2466 // Remove the art::HLoadClass instruction set as last input by 2467 // art::PrepareForRegisterAllocation::VisitClinitCheck in lieu of 2468 // the initial art::HClinitCheck instruction (only relevant for 2469 // static calls with explicit clinit check). 2470 void RemoveLoadClassAsLastInput() { 2471 DCHECK(IsStaticWithExplicitClinitCheck()); 2472 size_t last_input_index = InputCount() - 1; 2473 HInstruction* last_input = InputAt(last_input_index); 2474 DCHECK(last_input != nullptr); 2475 DCHECK(last_input->IsLoadClass()) << last_input->DebugName(); 2476 RemoveAsUserOfInput(last_input_index); 2477 inputs_.DeleteAt(last_input_index); 2478 clinit_check_requirement_ = ClinitCheckRequirement::kImplicit; 2479 DCHECK(IsStaticWithImplicitClinitCheck()); 2480 } 2481 2482 // Is this a call to a static method whose declaring class has an 2483 // explicit intialization check in the graph? 2484 bool IsStaticWithExplicitClinitCheck() const { 2485 return IsStatic() && (clinit_check_requirement_ == ClinitCheckRequirement::kExplicit); 2486 } 2487 2488 // Is this a call to a static method whose declaring class has an 2489 // implicit intialization check requirement? 2490 bool IsStaticWithImplicitClinitCheck() const { 2491 return IsStatic() && (clinit_check_requirement_ == ClinitCheckRequirement::kImplicit); 2492 } 2493 2494 DECLARE_INSTRUCTION(InvokeStaticOrDirect); 2495 2496 protected: 2497 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { 2498 const HUserRecord<HInstruction*> input_record = HInvoke::InputRecordAt(i); 2499 if (kIsDebugBuild && IsStaticWithExplicitClinitCheck() && (i == InputCount() - 1)) { 2500 HInstruction* input = input_record.GetInstruction(); 2501 // `input` is the last input of a static invoke marked as having 2502 // an explicit clinit check. It must either be: 2503 // - an art::HClinitCheck instruction, set by art::HGraphBuilder; or 2504 // - an art::HLoadClass instruction, set by art::PrepareForRegisterAllocation. 2505 DCHECK(input != nullptr); 2506 DCHECK(input->IsClinitCheck() || input->IsLoadClass()) << input->DebugName(); 2507 } 2508 return input_record; 2509 } 2510 2511 private: 2512 const InvokeType original_invoke_type_; 2513 const InvokeType invoke_type_; 2514 const bool is_recursive_; 2515 ClinitCheckRequirement clinit_check_requirement_; 2516 // Thread entrypoint offset for string init method if this is a string init invoke. 2517 // Note that there are multiple string init methods, each having its own offset. 2518 int32_t string_init_offset_; 2519 2520 DISALLOW_COPY_AND_ASSIGN(HInvokeStaticOrDirect); 2521}; 2522 2523class HInvokeVirtual : public HInvoke { 2524 public: 2525 HInvokeVirtual(ArenaAllocator* arena, 2526 uint32_t number_of_arguments, 2527 Primitive::Type return_type, 2528 uint32_t dex_pc, 2529 uint32_t dex_method_index, 2530 uint32_t vtable_index) 2531 : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index), 2532 vtable_index_(vtable_index) {} 2533 2534 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2535 // TODO: Add implicit null checks in intrinsics. 2536 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 2537 } 2538 2539 uint32_t GetVTableIndex() const { return vtable_index_; } 2540 2541 DECLARE_INSTRUCTION(InvokeVirtual); 2542 2543 private: 2544 const uint32_t vtable_index_; 2545 2546 DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual); 2547}; 2548 2549class HInvokeInterface : public HInvoke { 2550 public: 2551 HInvokeInterface(ArenaAllocator* arena, 2552 uint32_t number_of_arguments, 2553 Primitive::Type return_type, 2554 uint32_t dex_pc, 2555 uint32_t dex_method_index, 2556 uint32_t imt_index) 2557 : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index), 2558 imt_index_(imt_index) {} 2559 2560 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2561 // TODO: Add implicit null checks in intrinsics. 2562 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 2563 } 2564 2565 uint32_t GetImtIndex() const { return imt_index_; } 2566 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 2567 2568 DECLARE_INSTRUCTION(InvokeInterface); 2569 2570 private: 2571 const uint32_t imt_index_; 2572 2573 DISALLOW_COPY_AND_ASSIGN(HInvokeInterface); 2574}; 2575 2576class HNewInstance : public HExpression<0> { 2577 public: 2578 HNewInstance(uint32_t dex_pc, uint16_t type_index, QuickEntrypointEnum entrypoint) 2579 : HExpression(Primitive::kPrimNot, SideEffects::None()), 2580 dex_pc_(dex_pc), 2581 type_index_(type_index), 2582 entrypoint_(entrypoint) {} 2583 2584 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2585 uint16_t GetTypeIndex() const { return type_index_; } 2586 2587 // Calls runtime so needs an environment. 2588 bool NeedsEnvironment() const OVERRIDE { return true; } 2589 // It may throw when called on: 2590 // - interfaces 2591 // - abstract/innaccessible/unknown classes 2592 // TODO: optimize when possible. 2593 bool CanThrow() const OVERRIDE { return true; } 2594 2595 bool CanBeNull() const OVERRIDE { return false; } 2596 2597 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 2598 2599 DECLARE_INSTRUCTION(NewInstance); 2600 2601 private: 2602 const uint32_t dex_pc_; 2603 const uint16_t type_index_; 2604 const QuickEntrypointEnum entrypoint_; 2605 2606 DISALLOW_COPY_AND_ASSIGN(HNewInstance); 2607}; 2608 2609class HNeg : public HUnaryOperation { 2610 public: 2611 explicit HNeg(Primitive::Type result_type, HInstruction* input) 2612 : HUnaryOperation(result_type, input) {} 2613 2614 int32_t Evaluate(int32_t x) const OVERRIDE { return -x; } 2615 int64_t Evaluate(int64_t x) const OVERRIDE { return -x; } 2616 2617 DECLARE_INSTRUCTION(Neg); 2618 2619 private: 2620 DISALLOW_COPY_AND_ASSIGN(HNeg); 2621}; 2622 2623class HNewArray : public HExpression<1> { 2624 public: 2625 HNewArray(HInstruction* length, 2626 uint32_t dex_pc, 2627 uint16_t type_index, 2628 QuickEntrypointEnum entrypoint) 2629 : HExpression(Primitive::kPrimNot, SideEffects::None()), 2630 dex_pc_(dex_pc), 2631 type_index_(type_index), 2632 entrypoint_(entrypoint) { 2633 SetRawInputAt(0, length); 2634 } 2635 2636 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2637 uint16_t GetTypeIndex() const { return type_index_; } 2638 2639 // Calls runtime so needs an environment. 2640 bool NeedsEnvironment() const OVERRIDE { return true; } 2641 2642 // May throw NegativeArraySizeException, OutOfMemoryError, etc. 2643 bool CanThrow() const OVERRIDE { return true; } 2644 2645 bool CanBeNull() const OVERRIDE { return false; } 2646 2647 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 2648 2649 DECLARE_INSTRUCTION(NewArray); 2650 2651 private: 2652 const uint32_t dex_pc_; 2653 const uint16_t type_index_; 2654 const QuickEntrypointEnum entrypoint_; 2655 2656 DISALLOW_COPY_AND_ASSIGN(HNewArray); 2657}; 2658 2659class HAdd : public HBinaryOperation { 2660 public: 2661 HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2662 : HBinaryOperation(result_type, left, right) {} 2663 2664 bool IsCommutative() const OVERRIDE { return true; } 2665 2666 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2667 return x + y; 2668 } 2669 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2670 return x + y; 2671 } 2672 2673 DECLARE_INSTRUCTION(Add); 2674 2675 private: 2676 DISALLOW_COPY_AND_ASSIGN(HAdd); 2677}; 2678 2679class HSub : public HBinaryOperation { 2680 public: 2681 HSub(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2682 : HBinaryOperation(result_type, left, right) {} 2683 2684 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2685 return x - y; 2686 } 2687 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2688 return x - y; 2689 } 2690 2691 DECLARE_INSTRUCTION(Sub); 2692 2693 private: 2694 DISALLOW_COPY_AND_ASSIGN(HSub); 2695}; 2696 2697class HMul : public HBinaryOperation { 2698 public: 2699 HMul(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2700 : HBinaryOperation(result_type, left, right) {} 2701 2702 bool IsCommutative() const OVERRIDE { return true; } 2703 2704 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x * y; } 2705 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x * y; } 2706 2707 DECLARE_INSTRUCTION(Mul); 2708 2709 private: 2710 DISALLOW_COPY_AND_ASSIGN(HMul); 2711}; 2712 2713class HDiv : public HBinaryOperation { 2714 public: 2715 HDiv(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc) 2716 : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {} 2717 2718 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2719 // Our graph structure ensures we never have 0 for `y` during constant folding. 2720 DCHECK_NE(y, 0); 2721 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2722 return (y == -1) ? -x : x / y; 2723 } 2724 2725 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2726 DCHECK_NE(y, 0); 2727 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2728 return (y == -1) ? -x : x / y; 2729 } 2730 2731 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2732 2733 DECLARE_INSTRUCTION(Div); 2734 2735 private: 2736 const uint32_t dex_pc_; 2737 2738 DISALLOW_COPY_AND_ASSIGN(HDiv); 2739}; 2740 2741class HRem : public HBinaryOperation { 2742 public: 2743 HRem(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc) 2744 : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {} 2745 2746 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2747 DCHECK_NE(y, 0); 2748 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2749 return (y == -1) ? 0 : x % y; 2750 } 2751 2752 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2753 DCHECK_NE(y, 0); 2754 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2755 return (y == -1) ? 0 : x % y; 2756 } 2757 2758 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2759 2760 DECLARE_INSTRUCTION(Rem); 2761 2762 private: 2763 const uint32_t dex_pc_; 2764 2765 DISALLOW_COPY_AND_ASSIGN(HRem); 2766}; 2767 2768class HDivZeroCheck : public HExpression<1> { 2769 public: 2770 HDivZeroCheck(HInstruction* value, uint32_t dex_pc) 2771 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 2772 SetRawInputAt(0, value); 2773 } 2774 2775 bool CanBeMoved() const OVERRIDE { return true; } 2776 2777 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2778 UNUSED(other); 2779 return true; 2780 } 2781 2782 bool NeedsEnvironment() const OVERRIDE { return true; } 2783 bool CanThrow() const OVERRIDE { return true; } 2784 2785 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2786 2787 DECLARE_INSTRUCTION(DivZeroCheck); 2788 2789 private: 2790 const uint32_t dex_pc_; 2791 2792 DISALLOW_COPY_AND_ASSIGN(HDivZeroCheck); 2793}; 2794 2795class HShl : public HBinaryOperation { 2796 public: 2797 HShl(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2798 : HBinaryOperation(result_type, left, right) {} 2799 2800 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x << (y & kMaxIntShiftValue); } 2801 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x << (y & kMaxLongShiftValue); } 2802 2803 DECLARE_INSTRUCTION(Shl); 2804 2805 private: 2806 DISALLOW_COPY_AND_ASSIGN(HShl); 2807}; 2808 2809class HShr : public HBinaryOperation { 2810 public: 2811 HShr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2812 : HBinaryOperation(result_type, left, right) {} 2813 2814 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x >> (y & kMaxIntShiftValue); } 2815 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x >> (y & kMaxLongShiftValue); } 2816 2817 DECLARE_INSTRUCTION(Shr); 2818 2819 private: 2820 DISALLOW_COPY_AND_ASSIGN(HShr); 2821}; 2822 2823class HUShr : public HBinaryOperation { 2824 public: 2825 HUShr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2826 : HBinaryOperation(result_type, left, right) {} 2827 2828 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2829 uint32_t ux = static_cast<uint32_t>(x); 2830 uint32_t uy = static_cast<uint32_t>(y) & kMaxIntShiftValue; 2831 return static_cast<int32_t>(ux >> uy); 2832 } 2833 2834 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2835 uint64_t ux = static_cast<uint64_t>(x); 2836 uint64_t uy = static_cast<uint64_t>(y) & kMaxLongShiftValue; 2837 return static_cast<int64_t>(ux >> uy); 2838 } 2839 2840 DECLARE_INSTRUCTION(UShr); 2841 2842 private: 2843 DISALLOW_COPY_AND_ASSIGN(HUShr); 2844}; 2845 2846class HAnd : public HBinaryOperation { 2847 public: 2848 HAnd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2849 : HBinaryOperation(result_type, left, right) {} 2850 2851 bool IsCommutative() const OVERRIDE { return true; } 2852 2853 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x & y; } 2854 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x & y; } 2855 2856 DECLARE_INSTRUCTION(And); 2857 2858 private: 2859 DISALLOW_COPY_AND_ASSIGN(HAnd); 2860}; 2861 2862class HOr : public HBinaryOperation { 2863 public: 2864 HOr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2865 : HBinaryOperation(result_type, left, right) {} 2866 2867 bool IsCommutative() const OVERRIDE { return true; } 2868 2869 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x | y; } 2870 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x | y; } 2871 2872 DECLARE_INSTRUCTION(Or); 2873 2874 private: 2875 DISALLOW_COPY_AND_ASSIGN(HOr); 2876}; 2877 2878class HXor : public HBinaryOperation { 2879 public: 2880 HXor(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2881 : HBinaryOperation(result_type, left, right) {} 2882 2883 bool IsCommutative() const OVERRIDE { return true; } 2884 2885 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x ^ y; } 2886 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x ^ y; } 2887 2888 DECLARE_INSTRUCTION(Xor); 2889 2890 private: 2891 DISALLOW_COPY_AND_ASSIGN(HXor); 2892}; 2893 2894// The value of a parameter in this method. Its location depends on 2895// the calling convention. 2896class HParameterValue : public HExpression<0> { 2897 public: 2898 HParameterValue(uint8_t index, Primitive::Type parameter_type, bool is_this = false) 2899 : HExpression(parameter_type, SideEffects::None()), index_(index), is_this_(is_this) {} 2900 2901 uint8_t GetIndex() const { return index_; } 2902 2903 bool CanBeNull() const OVERRIDE { return !is_this_; } 2904 2905 DECLARE_INSTRUCTION(ParameterValue); 2906 2907 private: 2908 // The index of this parameter in the parameters list. Must be less 2909 // than HGraph::number_of_in_vregs_. 2910 const uint8_t index_; 2911 2912 // Whether or not the parameter value corresponds to 'this' argument. 2913 const bool is_this_; 2914 2915 DISALLOW_COPY_AND_ASSIGN(HParameterValue); 2916}; 2917 2918class HNot : public HUnaryOperation { 2919 public: 2920 explicit HNot(Primitive::Type result_type, HInstruction* input) 2921 : HUnaryOperation(result_type, input) {} 2922 2923 bool CanBeMoved() const OVERRIDE { return true; } 2924 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2925 UNUSED(other); 2926 return true; 2927 } 2928 2929 int32_t Evaluate(int32_t x) const OVERRIDE { return ~x; } 2930 int64_t Evaluate(int64_t x) const OVERRIDE { return ~x; } 2931 2932 DECLARE_INSTRUCTION(Not); 2933 2934 private: 2935 DISALLOW_COPY_AND_ASSIGN(HNot); 2936}; 2937 2938class HBooleanNot : public HUnaryOperation { 2939 public: 2940 explicit HBooleanNot(HInstruction* input) 2941 : HUnaryOperation(Primitive::Type::kPrimBoolean, input) {} 2942 2943 bool CanBeMoved() const OVERRIDE { return true; } 2944 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2945 UNUSED(other); 2946 return true; 2947 } 2948 2949 int32_t Evaluate(int32_t x) const OVERRIDE { 2950 DCHECK(IsUint<1>(x)); 2951 return !x; 2952 } 2953 2954 int64_t Evaluate(int64_t x ATTRIBUTE_UNUSED) const OVERRIDE { 2955 LOG(FATAL) << DebugName() << " cannot be used with 64-bit values"; 2956 UNREACHABLE(); 2957 } 2958 2959 DECLARE_INSTRUCTION(BooleanNot); 2960 2961 private: 2962 DISALLOW_COPY_AND_ASSIGN(HBooleanNot); 2963}; 2964 2965class HTypeConversion : public HExpression<1> { 2966 public: 2967 // Instantiate a type conversion of `input` to `result_type`. 2968 HTypeConversion(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc) 2969 : HExpression(result_type, SideEffects::None()), dex_pc_(dex_pc) { 2970 SetRawInputAt(0, input); 2971 DCHECK_NE(input->GetType(), result_type); 2972 } 2973 2974 HInstruction* GetInput() const { return InputAt(0); } 2975 Primitive::Type GetInputType() const { return GetInput()->GetType(); } 2976 Primitive::Type GetResultType() const { return GetType(); } 2977 2978 // Required by the x86 and ARM code generators when producing calls 2979 // to the runtime. 2980 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2981 2982 bool CanBeMoved() const OVERRIDE { return true; } 2983 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { return true; } 2984 2985 // Try to statically evaluate the conversion and return a HConstant 2986 // containing the result. If the input cannot be converted, return nullptr. 2987 HConstant* TryStaticEvaluation() const; 2988 2989 DECLARE_INSTRUCTION(TypeConversion); 2990 2991 private: 2992 const uint32_t dex_pc_; 2993 2994 DISALLOW_COPY_AND_ASSIGN(HTypeConversion); 2995}; 2996 2997static constexpr uint32_t kNoRegNumber = -1; 2998 2999class HPhi : public HInstruction { 3000 public: 3001 HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type) 3002 : HInstruction(SideEffects::None()), 3003 inputs_(arena, number_of_inputs), 3004 reg_number_(reg_number), 3005 type_(type), 3006 is_live_(false), 3007 can_be_null_(true) { 3008 inputs_.SetSize(number_of_inputs); 3009 } 3010 3011 // Returns a type equivalent to the given `type`, but that a `HPhi` can hold. 3012 static Primitive::Type ToPhiType(Primitive::Type type) { 3013 switch (type) { 3014 case Primitive::kPrimBoolean: 3015 case Primitive::kPrimByte: 3016 case Primitive::kPrimShort: 3017 case Primitive::kPrimChar: 3018 return Primitive::kPrimInt; 3019 default: 3020 return type; 3021 } 3022 } 3023 3024 size_t InputCount() const OVERRIDE { return inputs_.Size(); } 3025 3026 void AddInput(HInstruction* input); 3027 void RemoveInputAt(size_t index); 3028 3029 Primitive::Type GetType() const OVERRIDE { return type_; } 3030 void SetType(Primitive::Type type) { type_ = type; } 3031 3032 bool CanBeNull() const OVERRIDE { return can_be_null_; } 3033 void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; } 3034 3035 uint32_t GetRegNumber() const { return reg_number_; } 3036 3037 void SetDead() { is_live_ = false; } 3038 void SetLive() { is_live_ = true; } 3039 bool IsDead() const { return !is_live_; } 3040 bool IsLive() const { return is_live_; } 3041 3042 // Returns the next equivalent phi (starting from the current one) or null if there is none. 3043 // An equivalent phi is a phi having the same dex register and type. 3044 // It assumes that phis with the same dex register are adjacent. 3045 HPhi* GetNextEquivalentPhiWithSameType() { 3046 HInstruction* next = GetNext(); 3047 while (next != nullptr && next->AsPhi()->GetRegNumber() == reg_number_) { 3048 if (next->GetType() == GetType()) { 3049 return next->AsPhi(); 3050 } 3051 next = next->GetNext(); 3052 } 3053 return nullptr; 3054 } 3055 3056 DECLARE_INSTRUCTION(Phi); 3057 3058 protected: 3059 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); } 3060 3061 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE { 3062 inputs_.Put(index, input); 3063 } 3064 3065 private: 3066 GrowableArray<HUserRecord<HInstruction*> > inputs_; 3067 const uint32_t reg_number_; 3068 Primitive::Type type_; 3069 bool is_live_; 3070 bool can_be_null_; 3071 3072 DISALLOW_COPY_AND_ASSIGN(HPhi); 3073}; 3074 3075class HNullCheck : public HExpression<1> { 3076 public: 3077 HNullCheck(HInstruction* value, uint32_t dex_pc) 3078 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 3079 SetRawInputAt(0, value); 3080 } 3081 3082 bool CanBeMoved() const OVERRIDE { return true; } 3083 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3084 UNUSED(other); 3085 return true; 3086 } 3087 3088 bool NeedsEnvironment() const OVERRIDE { return true; } 3089 3090 bool CanThrow() const OVERRIDE { return true; } 3091 3092 bool CanBeNull() const OVERRIDE { return false; } 3093 3094 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3095 3096 DECLARE_INSTRUCTION(NullCheck); 3097 3098 private: 3099 const uint32_t dex_pc_; 3100 3101 DISALLOW_COPY_AND_ASSIGN(HNullCheck); 3102}; 3103 3104class FieldInfo : public ValueObject { 3105 public: 3106 FieldInfo(MemberOffset field_offset, Primitive::Type field_type, bool is_volatile) 3107 : field_offset_(field_offset), field_type_(field_type), is_volatile_(is_volatile) {} 3108 3109 MemberOffset GetFieldOffset() const { return field_offset_; } 3110 Primitive::Type GetFieldType() const { return field_type_; } 3111 bool IsVolatile() const { return is_volatile_; } 3112 3113 private: 3114 const MemberOffset field_offset_; 3115 const Primitive::Type field_type_; 3116 const bool is_volatile_; 3117}; 3118 3119class HInstanceFieldGet : public HExpression<1> { 3120 public: 3121 HInstanceFieldGet(HInstruction* value, 3122 Primitive::Type field_type, 3123 MemberOffset field_offset, 3124 bool is_volatile) 3125 : HExpression(field_type, SideEffects::DependsOnSomething()), 3126 field_info_(field_offset, field_type, is_volatile) { 3127 SetRawInputAt(0, value); 3128 } 3129 3130 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 3131 3132 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3133 HInstanceFieldGet* other_get = other->AsInstanceFieldGet(); 3134 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 3135 } 3136 3137 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3138 return (obj == InputAt(0)) && GetFieldOffset().Uint32Value() < kPageSize; 3139 } 3140 3141 size_t ComputeHashCode() const OVERRIDE { 3142 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 3143 } 3144 3145 const FieldInfo& GetFieldInfo() const { return field_info_; } 3146 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3147 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3148 bool IsVolatile() const { return field_info_.IsVolatile(); } 3149 3150 DECLARE_INSTRUCTION(InstanceFieldGet); 3151 3152 private: 3153 const FieldInfo field_info_; 3154 3155 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet); 3156}; 3157 3158class HInstanceFieldSet : public HTemplateInstruction<2> { 3159 public: 3160 HInstanceFieldSet(HInstruction* object, 3161 HInstruction* value, 3162 Primitive::Type field_type, 3163 MemberOffset field_offset, 3164 bool is_volatile) 3165 : HTemplateInstruction(SideEffects::ChangesSomething()), 3166 field_info_(field_offset, field_type, is_volatile) { 3167 SetRawInputAt(0, object); 3168 SetRawInputAt(1, value); 3169 } 3170 3171 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3172 return (obj == InputAt(0)) && GetFieldOffset().Uint32Value() < kPageSize; 3173 } 3174 3175 const FieldInfo& GetFieldInfo() const { return field_info_; } 3176 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3177 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3178 bool IsVolatile() const { return field_info_.IsVolatile(); } 3179 HInstruction* GetValue() const { return InputAt(1); } 3180 3181 DECLARE_INSTRUCTION(InstanceFieldSet); 3182 3183 private: 3184 const FieldInfo field_info_; 3185 3186 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet); 3187}; 3188 3189class HArrayGet : public HExpression<2> { 3190 public: 3191 HArrayGet(HInstruction* array, HInstruction* index, Primitive::Type type) 3192 : HExpression(type, SideEffects::DependsOnSomething()) { 3193 SetRawInputAt(0, array); 3194 SetRawInputAt(1, index); 3195 } 3196 3197 bool CanBeMoved() const OVERRIDE { return true; } 3198 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3199 UNUSED(other); 3200 return true; 3201 } 3202 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3203 UNUSED(obj); 3204 // TODO: We can be smarter here. 3205 // Currently, the array access is always preceded by an ArrayLength or a NullCheck 3206 // which generates the implicit null check. There are cases when these can be removed 3207 // to produce better code. If we ever add optimizations to do so we should allow an 3208 // implicit check here (as long as the address falls in the first page). 3209 return false; 3210 } 3211 3212 void SetType(Primitive::Type type) { type_ = type; } 3213 3214 HInstruction* GetArray() const { return InputAt(0); } 3215 HInstruction* GetIndex() const { return InputAt(1); } 3216 3217 DECLARE_INSTRUCTION(ArrayGet); 3218 3219 private: 3220 DISALLOW_COPY_AND_ASSIGN(HArrayGet); 3221}; 3222 3223class HArraySet : public HTemplateInstruction<3> { 3224 public: 3225 HArraySet(HInstruction* array, 3226 HInstruction* index, 3227 HInstruction* value, 3228 Primitive::Type expected_component_type, 3229 uint32_t dex_pc) 3230 : HTemplateInstruction(SideEffects::ChangesSomething()), 3231 dex_pc_(dex_pc), 3232 expected_component_type_(expected_component_type), 3233 needs_type_check_(value->GetType() == Primitive::kPrimNot) { 3234 SetRawInputAt(0, array); 3235 SetRawInputAt(1, index); 3236 SetRawInputAt(2, value); 3237 } 3238 3239 bool NeedsEnvironment() const OVERRIDE { 3240 // We currently always call a runtime method to catch array store 3241 // exceptions. 3242 return needs_type_check_; 3243 } 3244 3245 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3246 UNUSED(obj); 3247 // TODO: Same as for ArrayGet. 3248 return false; 3249 } 3250 3251 void ClearNeedsTypeCheck() { 3252 needs_type_check_ = false; 3253 } 3254 3255 bool NeedsTypeCheck() const { return needs_type_check_; } 3256 3257 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3258 3259 HInstruction* GetArray() const { return InputAt(0); } 3260 HInstruction* GetIndex() const { return InputAt(1); } 3261 HInstruction* GetValue() const { return InputAt(2); } 3262 3263 Primitive::Type GetComponentType() const { 3264 // The Dex format does not type floating point index operations. Since the 3265 // `expected_component_type_` is set during building and can therefore not 3266 // be correct, we also check what is the value type. If it is a floating 3267 // point type, we must use that type. 3268 Primitive::Type value_type = GetValue()->GetType(); 3269 return ((value_type == Primitive::kPrimFloat) || (value_type == Primitive::kPrimDouble)) 3270 ? value_type 3271 : expected_component_type_; 3272 } 3273 3274 DECLARE_INSTRUCTION(ArraySet); 3275 3276 private: 3277 const uint32_t dex_pc_; 3278 const Primitive::Type expected_component_type_; 3279 bool needs_type_check_; 3280 3281 DISALLOW_COPY_AND_ASSIGN(HArraySet); 3282}; 3283 3284class HArrayLength : public HExpression<1> { 3285 public: 3286 explicit HArrayLength(HInstruction* array) 3287 : HExpression(Primitive::kPrimInt, SideEffects::None()) { 3288 // Note that arrays do not change length, so the instruction does not 3289 // depend on any write. 3290 SetRawInputAt(0, array); 3291 } 3292 3293 bool CanBeMoved() const OVERRIDE { return true; } 3294 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3295 UNUSED(other); 3296 return true; 3297 } 3298 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3299 return obj == InputAt(0); 3300 } 3301 3302 DECLARE_INSTRUCTION(ArrayLength); 3303 3304 private: 3305 DISALLOW_COPY_AND_ASSIGN(HArrayLength); 3306}; 3307 3308class HBoundsCheck : public HExpression<2> { 3309 public: 3310 HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc) 3311 : HExpression(index->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 3312 DCHECK(index->GetType() == Primitive::kPrimInt); 3313 SetRawInputAt(0, index); 3314 SetRawInputAt(1, length); 3315 } 3316 3317 bool CanBeMoved() const OVERRIDE { return true; } 3318 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3319 UNUSED(other); 3320 return true; 3321 } 3322 3323 bool NeedsEnvironment() const OVERRIDE { return true; } 3324 3325 bool CanThrow() const OVERRIDE { return true; } 3326 3327 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3328 3329 DECLARE_INSTRUCTION(BoundsCheck); 3330 3331 private: 3332 const uint32_t dex_pc_; 3333 3334 DISALLOW_COPY_AND_ASSIGN(HBoundsCheck); 3335}; 3336 3337/** 3338 * Some DEX instructions are folded into multiple HInstructions that need 3339 * to stay live until the last HInstruction. This class 3340 * is used as a marker for the baseline compiler to ensure its preceding 3341 * HInstruction stays live. `index` represents the stack location index of the 3342 * instruction (the actual offset is computed as index * vreg_size). 3343 */ 3344class HTemporary : public HTemplateInstruction<0> { 3345 public: 3346 explicit HTemporary(size_t index) : HTemplateInstruction(SideEffects::None()), index_(index) {} 3347 3348 size_t GetIndex() const { return index_; } 3349 3350 Primitive::Type GetType() const OVERRIDE { 3351 // The previous instruction is the one that will be stored in the temporary location. 3352 DCHECK(GetPrevious() != nullptr); 3353 return GetPrevious()->GetType(); 3354 } 3355 3356 DECLARE_INSTRUCTION(Temporary); 3357 3358 private: 3359 const size_t index_; 3360 3361 DISALLOW_COPY_AND_ASSIGN(HTemporary); 3362}; 3363 3364class HSuspendCheck : public HTemplateInstruction<0> { 3365 public: 3366 explicit HSuspendCheck(uint32_t dex_pc) 3367 : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc), slow_path_(nullptr) {} 3368 3369 bool NeedsEnvironment() const OVERRIDE { 3370 return true; 3371 } 3372 3373 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3374 void SetSlowPath(SlowPathCode* slow_path) { slow_path_ = slow_path; } 3375 SlowPathCode* GetSlowPath() const { return slow_path_; } 3376 3377 DECLARE_INSTRUCTION(SuspendCheck); 3378 3379 private: 3380 const uint32_t dex_pc_; 3381 3382 // Only used for code generation, in order to share the same slow path between back edges 3383 // of a same loop. 3384 SlowPathCode* slow_path_; 3385 3386 DISALLOW_COPY_AND_ASSIGN(HSuspendCheck); 3387}; 3388 3389/** 3390 * Instruction to load a Class object. 3391 */ 3392class HLoadClass : public HExpression<0> { 3393 public: 3394 HLoadClass(uint16_t type_index, 3395 bool is_referrers_class, 3396 uint32_t dex_pc) 3397 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3398 type_index_(type_index), 3399 is_referrers_class_(is_referrers_class), 3400 dex_pc_(dex_pc), 3401 generate_clinit_check_(false), 3402 loaded_class_rti_(ReferenceTypeInfo::CreateTop(/* is_exact */ false)) {} 3403 3404 bool CanBeMoved() const OVERRIDE { return true; } 3405 3406 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3407 return other->AsLoadClass()->type_index_ == type_index_; 3408 } 3409 3410 size_t ComputeHashCode() const OVERRIDE { return type_index_; } 3411 3412 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3413 uint16_t GetTypeIndex() const { return type_index_; } 3414 bool IsReferrersClass() const { return is_referrers_class_; } 3415 3416 bool NeedsEnvironment() const OVERRIDE { 3417 // Will call runtime and load the class if the class is not loaded yet. 3418 // TODO: finer grain decision. 3419 return !is_referrers_class_; 3420 } 3421 3422 bool MustGenerateClinitCheck() const { 3423 return generate_clinit_check_; 3424 } 3425 3426 void SetMustGenerateClinitCheck() { 3427 generate_clinit_check_ = true; 3428 } 3429 3430 bool CanCallRuntime() const { 3431 return MustGenerateClinitCheck() || !is_referrers_class_; 3432 } 3433 3434 bool CanThrow() const OVERRIDE { 3435 // May call runtime and and therefore can throw. 3436 // TODO: finer grain decision. 3437 return !is_referrers_class_; 3438 } 3439 3440 ReferenceTypeInfo GetLoadedClassRTI() { 3441 return loaded_class_rti_; 3442 } 3443 3444 void SetLoadedClassRTI(ReferenceTypeInfo rti) { 3445 // Make sure we only set exact types (the loaded class should never be merged). 3446 DCHECK(rti.IsExact()); 3447 loaded_class_rti_ = rti; 3448 } 3449 3450 bool IsResolved() { 3451 return loaded_class_rti_.IsExact(); 3452 } 3453 3454 bool NeedsDexCache() const OVERRIDE { return !is_referrers_class_; } 3455 3456 DECLARE_INSTRUCTION(LoadClass); 3457 3458 private: 3459 const uint16_t type_index_; 3460 const bool is_referrers_class_; 3461 const uint32_t dex_pc_; 3462 // Whether this instruction must generate the initialization check. 3463 // Used for code generation. 3464 bool generate_clinit_check_; 3465 3466 ReferenceTypeInfo loaded_class_rti_; 3467 3468 DISALLOW_COPY_AND_ASSIGN(HLoadClass); 3469}; 3470 3471class HLoadString : public HExpression<0> { 3472 public: 3473 HLoadString(uint32_t string_index, uint32_t dex_pc) 3474 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3475 string_index_(string_index), 3476 dex_pc_(dex_pc) {} 3477 3478 bool CanBeMoved() const OVERRIDE { return true; } 3479 3480 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3481 return other->AsLoadString()->string_index_ == string_index_; 3482 } 3483 3484 size_t ComputeHashCode() const OVERRIDE { return string_index_; } 3485 3486 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3487 uint32_t GetStringIndex() const { return string_index_; } 3488 3489 // TODO: Can we deopt or debug when we resolve a string? 3490 bool NeedsEnvironment() const OVERRIDE { return false; } 3491 bool NeedsDexCache() const OVERRIDE { return true; } 3492 3493 DECLARE_INSTRUCTION(LoadString); 3494 3495 private: 3496 const uint32_t string_index_; 3497 const uint32_t dex_pc_; 3498 3499 DISALLOW_COPY_AND_ASSIGN(HLoadString); 3500}; 3501 3502/** 3503 * Performs an initialization check on its Class object input. 3504 */ 3505class HClinitCheck : public HExpression<1> { 3506 public: 3507 explicit HClinitCheck(HLoadClass* constant, uint32_t dex_pc) 3508 : HExpression(Primitive::kPrimNot, SideEffects::ChangesSomething()), 3509 dex_pc_(dex_pc) { 3510 SetRawInputAt(0, constant); 3511 } 3512 3513 bool CanBeMoved() const OVERRIDE { return true; } 3514 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3515 UNUSED(other); 3516 return true; 3517 } 3518 3519 bool NeedsEnvironment() const OVERRIDE { 3520 // May call runtime to initialize the class. 3521 return true; 3522 } 3523 3524 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3525 3526 HLoadClass* GetLoadClass() const { return InputAt(0)->AsLoadClass(); } 3527 3528 DECLARE_INSTRUCTION(ClinitCheck); 3529 3530 private: 3531 const uint32_t dex_pc_; 3532 3533 DISALLOW_COPY_AND_ASSIGN(HClinitCheck); 3534}; 3535 3536class HStaticFieldGet : public HExpression<1> { 3537 public: 3538 HStaticFieldGet(HInstruction* cls, 3539 Primitive::Type field_type, 3540 MemberOffset field_offset, 3541 bool is_volatile) 3542 : HExpression(field_type, SideEffects::DependsOnSomething()), 3543 field_info_(field_offset, field_type, is_volatile) { 3544 SetRawInputAt(0, cls); 3545 } 3546 3547 3548 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 3549 3550 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3551 HStaticFieldGet* other_get = other->AsStaticFieldGet(); 3552 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 3553 } 3554 3555 size_t ComputeHashCode() const OVERRIDE { 3556 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 3557 } 3558 3559 const FieldInfo& GetFieldInfo() const { return field_info_; } 3560 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3561 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3562 bool IsVolatile() const { return field_info_.IsVolatile(); } 3563 3564 DECLARE_INSTRUCTION(StaticFieldGet); 3565 3566 private: 3567 const FieldInfo field_info_; 3568 3569 DISALLOW_COPY_AND_ASSIGN(HStaticFieldGet); 3570}; 3571 3572class HStaticFieldSet : public HTemplateInstruction<2> { 3573 public: 3574 HStaticFieldSet(HInstruction* cls, 3575 HInstruction* value, 3576 Primitive::Type field_type, 3577 MemberOffset field_offset, 3578 bool is_volatile) 3579 : HTemplateInstruction(SideEffects::ChangesSomething()), 3580 field_info_(field_offset, field_type, is_volatile) { 3581 SetRawInputAt(0, cls); 3582 SetRawInputAt(1, value); 3583 } 3584 3585 const FieldInfo& GetFieldInfo() const { return field_info_; } 3586 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3587 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3588 bool IsVolatile() const { return field_info_.IsVolatile(); } 3589 3590 HInstruction* GetValue() const { return InputAt(1); } 3591 3592 DECLARE_INSTRUCTION(StaticFieldSet); 3593 3594 private: 3595 const FieldInfo field_info_; 3596 3597 DISALLOW_COPY_AND_ASSIGN(HStaticFieldSet); 3598}; 3599 3600// Implement the move-exception DEX instruction. 3601class HLoadException : public HExpression<0> { 3602 public: 3603 HLoadException() : HExpression(Primitive::kPrimNot, SideEffects::None()) {} 3604 3605 DECLARE_INSTRUCTION(LoadException); 3606 3607 private: 3608 DISALLOW_COPY_AND_ASSIGN(HLoadException); 3609}; 3610 3611class HThrow : public HTemplateInstruction<1> { 3612 public: 3613 HThrow(HInstruction* exception, uint32_t dex_pc) 3614 : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc) { 3615 SetRawInputAt(0, exception); 3616 } 3617 3618 bool IsControlFlow() const OVERRIDE { return true; } 3619 3620 bool NeedsEnvironment() const OVERRIDE { return true; } 3621 3622 bool CanThrow() const OVERRIDE { return true; } 3623 3624 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3625 3626 DECLARE_INSTRUCTION(Throw); 3627 3628 private: 3629 const uint32_t dex_pc_; 3630 3631 DISALLOW_COPY_AND_ASSIGN(HThrow); 3632}; 3633 3634class HInstanceOf : public HExpression<2> { 3635 public: 3636 HInstanceOf(HInstruction* object, 3637 HLoadClass* constant, 3638 bool class_is_final, 3639 uint32_t dex_pc) 3640 : HExpression(Primitive::kPrimBoolean, SideEffects::None()), 3641 class_is_final_(class_is_final), 3642 must_do_null_check_(true), 3643 dex_pc_(dex_pc) { 3644 SetRawInputAt(0, object); 3645 SetRawInputAt(1, constant); 3646 } 3647 3648 bool CanBeMoved() const OVERRIDE { return true; } 3649 3650 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 3651 return true; 3652 } 3653 3654 bool NeedsEnvironment() const OVERRIDE { 3655 return false; 3656 } 3657 3658 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3659 3660 bool IsClassFinal() const { return class_is_final_; } 3661 3662 // Used only in code generation. 3663 bool MustDoNullCheck() const { return must_do_null_check_; } 3664 void ClearMustDoNullCheck() { must_do_null_check_ = false; } 3665 3666 DECLARE_INSTRUCTION(InstanceOf); 3667 3668 private: 3669 const bool class_is_final_; 3670 bool must_do_null_check_; 3671 const uint32_t dex_pc_; 3672 3673 DISALLOW_COPY_AND_ASSIGN(HInstanceOf); 3674}; 3675 3676class HBoundType : public HExpression<1> { 3677 public: 3678 HBoundType(HInstruction* input, ReferenceTypeInfo bound_type) 3679 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3680 bound_type_(bound_type) { 3681 DCHECK_EQ(input->GetType(), Primitive::kPrimNot); 3682 SetRawInputAt(0, input); 3683 } 3684 3685 const ReferenceTypeInfo& GetBoundType() const { return bound_type_; } 3686 3687 bool CanBeNull() const OVERRIDE { 3688 // `null instanceof ClassX` always return false so we can't be null. 3689 return false; 3690 } 3691 3692 DECLARE_INSTRUCTION(BoundType); 3693 3694 private: 3695 // Encodes the most upper class that this instruction can have. In other words 3696 // it is always the case that GetBoundType().IsSupertypeOf(GetReferenceType()). 3697 // It is used to bound the type in cases like `if (x instanceof ClassX) {}` 3698 const ReferenceTypeInfo bound_type_; 3699 3700 DISALLOW_COPY_AND_ASSIGN(HBoundType); 3701}; 3702 3703class HCheckCast : public HTemplateInstruction<2> { 3704 public: 3705 HCheckCast(HInstruction* object, 3706 HLoadClass* constant, 3707 bool class_is_final, 3708 uint32_t dex_pc) 3709 : HTemplateInstruction(SideEffects::None()), 3710 class_is_final_(class_is_final), 3711 must_do_null_check_(true), 3712 dex_pc_(dex_pc) { 3713 SetRawInputAt(0, object); 3714 SetRawInputAt(1, constant); 3715 } 3716 3717 bool CanBeMoved() const OVERRIDE { return true; } 3718 3719 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 3720 return true; 3721 } 3722 3723 bool NeedsEnvironment() const OVERRIDE { 3724 // Instruction may throw a CheckCastError. 3725 return true; 3726 } 3727 3728 bool CanThrow() const OVERRIDE { return true; } 3729 3730 bool MustDoNullCheck() const { return must_do_null_check_; } 3731 void ClearMustDoNullCheck() { must_do_null_check_ = false; } 3732 3733 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3734 3735 bool IsClassFinal() const { return class_is_final_; } 3736 3737 DECLARE_INSTRUCTION(CheckCast); 3738 3739 private: 3740 const bool class_is_final_; 3741 bool must_do_null_check_; 3742 const uint32_t dex_pc_; 3743 3744 DISALLOW_COPY_AND_ASSIGN(HCheckCast); 3745}; 3746 3747class HMemoryBarrier : public HTemplateInstruction<0> { 3748 public: 3749 explicit HMemoryBarrier(MemBarrierKind barrier_kind) 3750 : HTemplateInstruction(SideEffects::None()), 3751 barrier_kind_(barrier_kind) {} 3752 3753 MemBarrierKind GetBarrierKind() { return barrier_kind_; } 3754 3755 DECLARE_INSTRUCTION(MemoryBarrier); 3756 3757 private: 3758 const MemBarrierKind barrier_kind_; 3759 3760 DISALLOW_COPY_AND_ASSIGN(HMemoryBarrier); 3761}; 3762 3763class HMonitorOperation : public HTemplateInstruction<1> { 3764 public: 3765 enum OperationKind { 3766 kEnter, 3767 kExit, 3768 }; 3769 3770 HMonitorOperation(HInstruction* object, OperationKind kind, uint32_t dex_pc) 3771 : HTemplateInstruction(SideEffects::None()), kind_(kind), dex_pc_(dex_pc) { 3772 SetRawInputAt(0, object); 3773 } 3774 3775 // Instruction may throw a Java exception, so we need an environment. 3776 bool NeedsEnvironment() const OVERRIDE { return true; } 3777 bool CanThrow() const OVERRIDE { return true; } 3778 3779 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3780 3781 bool IsEnter() const { return kind_ == kEnter; } 3782 3783 DECLARE_INSTRUCTION(MonitorOperation); 3784 3785 private: 3786 const OperationKind kind_; 3787 const uint32_t dex_pc_; 3788 3789 private: 3790 DISALLOW_COPY_AND_ASSIGN(HMonitorOperation); 3791}; 3792 3793class MoveOperands : public ArenaObject<kArenaAllocMisc> { 3794 public: 3795 MoveOperands(Location source, 3796 Location destination, 3797 Primitive::Type type, 3798 HInstruction* instruction) 3799 : source_(source), destination_(destination), type_(type), instruction_(instruction) {} 3800 3801 Location GetSource() const { return source_; } 3802 Location GetDestination() const { return destination_; } 3803 3804 void SetSource(Location value) { source_ = value; } 3805 void SetDestination(Location value) { destination_ = value; } 3806 3807 // The parallel move resolver marks moves as "in-progress" by clearing the 3808 // destination (but not the source). 3809 Location MarkPending() { 3810 DCHECK(!IsPending()); 3811 Location dest = destination_; 3812 destination_ = Location::NoLocation(); 3813 return dest; 3814 } 3815 3816 void ClearPending(Location dest) { 3817 DCHECK(IsPending()); 3818 destination_ = dest; 3819 } 3820 3821 bool IsPending() const { 3822 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 3823 return destination_.IsInvalid() && !source_.IsInvalid(); 3824 } 3825 3826 // True if this blocks a move from the given location. 3827 bool Blocks(Location loc) const { 3828 return !IsEliminated() && source_.OverlapsWith(loc); 3829 } 3830 3831 // A move is redundant if it's been eliminated, if its source and 3832 // destination are the same, or if its destination is unneeded. 3833 bool IsRedundant() const { 3834 return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_); 3835 } 3836 3837 // We clear both operands to indicate move that's been eliminated. 3838 void Eliminate() { 3839 source_ = destination_ = Location::NoLocation(); 3840 } 3841 3842 bool IsEliminated() const { 3843 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 3844 return source_.IsInvalid(); 3845 } 3846 3847 bool Is64BitMove() const { 3848 return Primitive::Is64BitType(type_); 3849 } 3850 3851 HInstruction* GetInstruction() const { return instruction_; } 3852 3853 private: 3854 Location source_; 3855 Location destination_; 3856 // The type this move is for. 3857 Primitive::Type type_; 3858 // The instruction this move is assocatied with. Null when this move is 3859 // for moving an input in the expected locations of user (including a phi user). 3860 // This is only used in debug mode, to ensure we do not connect interval siblings 3861 // in the same parallel move. 3862 HInstruction* instruction_; 3863}; 3864 3865static constexpr size_t kDefaultNumberOfMoves = 4; 3866 3867class HParallelMove : public HTemplateInstruction<0> { 3868 public: 3869 explicit HParallelMove(ArenaAllocator* arena) 3870 : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {} 3871 3872 void AddMove(Location source, 3873 Location destination, 3874 Primitive::Type type, 3875 HInstruction* instruction) { 3876 DCHECK(source.IsValid()); 3877 DCHECK(destination.IsValid()); 3878 if (kIsDebugBuild) { 3879 if (instruction != nullptr) { 3880 for (size_t i = 0, e = moves_.Size(); i < e; ++i) { 3881 if (moves_.Get(i).GetInstruction() == instruction) { 3882 // Special case the situation where the move is for the spill slot 3883 // of the instruction. 3884 if ((GetPrevious() == instruction) 3885 || ((GetPrevious() == nullptr) 3886 && instruction->IsPhi() 3887 && instruction->GetBlock() == GetBlock())) { 3888 DCHECK_NE(destination.GetKind(), moves_.Get(i).GetDestination().GetKind()) 3889 << "Doing parallel moves for the same instruction."; 3890 } else { 3891 DCHECK(false) << "Doing parallel moves for the same instruction."; 3892 } 3893 } 3894 } 3895 } 3896 for (size_t i = 0, e = moves_.Size(); i < e; ++i) { 3897 DCHECK(!destination.OverlapsWith(moves_.Get(i).GetDestination())) 3898 << "Overlapped destination for two moves in a parallel move: " 3899 << moves_.Get(i).GetSource() << " ==> " << moves_.Get(i).GetDestination() << " and " 3900 << source << " ==> " << destination; 3901 } 3902 } 3903 moves_.Add(MoveOperands(source, destination, type, instruction)); 3904 } 3905 3906 MoveOperands* MoveOperandsAt(size_t index) const { 3907 return moves_.GetRawStorage() + index; 3908 } 3909 3910 size_t NumMoves() const { return moves_.Size(); } 3911 3912 DECLARE_INSTRUCTION(ParallelMove); 3913 3914 private: 3915 GrowableArray<MoveOperands> moves_; 3916 3917 DISALLOW_COPY_AND_ASSIGN(HParallelMove); 3918}; 3919 3920class HGraphVisitor : public ValueObject { 3921 public: 3922 explicit HGraphVisitor(HGraph* graph) : graph_(graph) {} 3923 virtual ~HGraphVisitor() {} 3924 3925 virtual void VisitInstruction(HInstruction* instruction) { UNUSED(instruction); } 3926 virtual void VisitBasicBlock(HBasicBlock* block); 3927 3928 // Visit the graph following basic block insertion order. 3929 void VisitInsertionOrder(); 3930 3931 // Visit the graph following dominator tree reverse post-order. 3932 void VisitReversePostOrder(); 3933 3934 HGraph* GetGraph() const { return graph_; } 3935 3936 // Visit functions for instruction classes. 3937#define DECLARE_VISIT_INSTRUCTION(name, super) \ 3938 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } 3939 3940 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 3941 3942#undef DECLARE_VISIT_INSTRUCTION 3943 3944 private: 3945 HGraph* const graph_; 3946 3947 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); 3948}; 3949 3950class HGraphDelegateVisitor : public HGraphVisitor { 3951 public: 3952 explicit HGraphDelegateVisitor(HGraph* graph) : HGraphVisitor(graph) {} 3953 virtual ~HGraphDelegateVisitor() {} 3954 3955 // Visit functions that delegate to to super class. 3956#define DECLARE_VISIT_INSTRUCTION(name, super) \ 3957 void Visit##name(H##name* instr) OVERRIDE { Visit##super(instr); } 3958 3959 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 3960 3961#undef DECLARE_VISIT_INSTRUCTION 3962 3963 private: 3964 DISALLOW_COPY_AND_ASSIGN(HGraphDelegateVisitor); 3965}; 3966 3967class HInsertionOrderIterator : public ValueObject { 3968 public: 3969 explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 3970 3971 bool Done() const { return index_ == graph_.GetBlocks().Size(); } 3972 HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); } 3973 void Advance() { ++index_; } 3974 3975 private: 3976 const HGraph& graph_; 3977 size_t index_; 3978 3979 DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator); 3980}; 3981 3982class HReversePostOrderIterator : public ValueObject { 3983 public: 3984 explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) { 3985 // Check that reverse post order of the graph has been built. 3986 DCHECK(!graph.GetReversePostOrder().IsEmpty()); 3987 } 3988 3989 bool Done() const { return index_ == graph_.GetReversePostOrder().Size(); } 3990 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_); } 3991 void Advance() { ++index_; } 3992 3993 private: 3994 const HGraph& graph_; 3995 size_t index_; 3996 3997 DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator); 3998}; 3999 4000class HPostOrderIterator : public ValueObject { 4001 public: 4002 explicit HPostOrderIterator(const HGraph& graph) 4003 : graph_(graph), index_(graph_.GetReversePostOrder().Size()) { 4004 // Check that reverse post order of the graph has been built. 4005 DCHECK(!graph.GetReversePostOrder().IsEmpty()); 4006 } 4007 4008 bool Done() const { return index_ == 0; } 4009 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_ - 1); } 4010 void Advance() { --index_; } 4011 4012 private: 4013 const HGraph& graph_; 4014 size_t index_; 4015 4016 DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); 4017}; 4018 4019class HLinearPostOrderIterator : public ValueObject { 4020 public: 4021 explicit HLinearPostOrderIterator(const HGraph& graph) 4022 : order_(graph.GetLinearOrder()), index_(graph.GetLinearOrder().Size()) {} 4023 4024 bool Done() const { return index_ == 0; } 4025 4026 HBasicBlock* Current() const { return order_.Get(index_ -1); } 4027 4028 void Advance() { 4029 --index_; 4030 DCHECK_GE(index_, 0U); 4031 } 4032 4033 private: 4034 const GrowableArray<HBasicBlock*>& order_; 4035 size_t index_; 4036 4037 DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator); 4038}; 4039 4040class HLinearOrderIterator : public ValueObject { 4041 public: 4042 explicit HLinearOrderIterator(const HGraph& graph) 4043 : order_(graph.GetLinearOrder()), index_(0) {} 4044 4045 bool Done() const { return index_ == order_.Size(); } 4046 HBasicBlock* Current() const { return order_.Get(index_); } 4047 void Advance() { ++index_; } 4048 4049 private: 4050 const GrowableArray<HBasicBlock*>& order_; 4051 size_t index_; 4052 4053 DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator); 4054}; 4055 4056// Iterator over the blocks that art part of the loop. Includes blocks part 4057// of an inner loop. The order in which the blocks are iterated is on their 4058// block id. 4059class HBlocksInLoopIterator : public ValueObject { 4060 public: 4061 explicit HBlocksInLoopIterator(const HLoopInformation& info) 4062 : blocks_in_loop_(info.GetBlocks()), 4063 blocks_(info.GetHeader()->GetGraph()->GetBlocks()), 4064 index_(0) { 4065 if (!blocks_in_loop_.IsBitSet(index_)) { 4066 Advance(); 4067 } 4068 } 4069 4070 bool Done() const { return index_ == blocks_.Size(); } 4071 HBasicBlock* Current() const { return blocks_.Get(index_); } 4072 void Advance() { 4073 ++index_; 4074 for (size_t e = blocks_.Size(); index_ < e; ++index_) { 4075 if (blocks_in_loop_.IsBitSet(index_)) { 4076 break; 4077 } 4078 } 4079 } 4080 4081 private: 4082 const BitVector& blocks_in_loop_; 4083 const GrowableArray<HBasicBlock*>& blocks_; 4084 size_t index_; 4085 4086 DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopIterator); 4087}; 4088 4089inline int64_t Int64FromConstant(HConstant* constant) { 4090 DCHECK(constant->IsIntConstant() || constant->IsLongConstant()); 4091 return constant->IsIntConstant() ? constant->AsIntConstant()->GetValue() 4092 : constant->AsLongConstant()->GetValue(); 4093} 4094 4095} // namespace art 4096 4097#endif // ART_COMPILER_OPTIMIZING_NODES_H_ 4098