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