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