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