nodes.h revision fb8464ae5f5194dc16278e528cfcbff71498c767
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 <algorithm> 21#include <array> 22#include <type_traits> 23 24#include "base/arena_bit_vector.h" 25#include "base/arena_containers.h" 26#include "base/arena_object.h" 27#include "base/stl_util.h" 28#include "dex/compiler_enums.h" 29#include "entrypoints/quick/quick_entrypoints_enum.h" 30#include "handle.h" 31#include "handle_scope.h" 32#include "invoke_type.h" 33#include "locations.h" 34#include "method_reference.h" 35#include "mirror/class.h" 36#include "offsets.h" 37#include "primitive.h" 38#include "utils/array_ref.h" 39 40namespace art { 41 42class GraphChecker; 43class HBasicBlock; 44class HCurrentMethod; 45class HDoubleConstant; 46class HEnvironment; 47class HFakeString; 48class HFloatConstant; 49class HGraphBuilder; 50class HGraphVisitor; 51class HInstruction; 52class HIntConstant; 53class HInvoke; 54class HLongConstant; 55class HNullConstant; 56class HPhi; 57class HSuspendCheck; 58class HTryBoundary; 59class LiveInterval; 60class LocationSummary; 61class SlowPathCode; 62class SsaBuilder; 63 64namespace mirror { 65class DexCache; 66} // namespace mirror 67 68static const int kDefaultNumberOfBlocks = 8; 69static const int kDefaultNumberOfSuccessors = 2; 70static const int kDefaultNumberOfPredecessors = 2; 71static const int kDefaultNumberOfExceptionalPredecessors = 0; 72static const int kDefaultNumberOfDominatedBlocks = 1; 73static const int kDefaultNumberOfBackEdges = 1; 74 75static constexpr uint32_t kMaxIntShiftValue = 0x1f; 76static constexpr uint64_t kMaxLongShiftValue = 0x3f; 77 78static constexpr uint32_t kUnknownFieldIndex = static_cast<uint32_t>(-1); 79static constexpr uint16_t kUnknownClassDefIndex = static_cast<uint16_t>(-1); 80 81static constexpr InvokeType kInvalidInvokeType = static_cast<InvokeType>(-1); 82 83static constexpr uint32_t kNoDexPc = -1; 84 85enum IfCondition { 86 // All types. 87 kCondEQ, // == 88 kCondNE, // != 89 // Signed integers and floating-point numbers. 90 kCondLT, // < 91 kCondLE, // <= 92 kCondGT, // > 93 kCondGE, // >= 94 // Unsigned integers. 95 kCondB, // < 96 kCondBE, // <= 97 kCondA, // > 98 kCondAE, // >= 99}; 100 101class HInstructionList : public ValueObject { 102 public: 103 HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {} 104 105 void AddInstruction(HInstruction* instruction); 106 void RemoveInstruction(HInstruction* instruction); 107 108 // Insert `instruction` before/after an existing instruction `cursor`. 109 void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); 110 void InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor); 111 112 // Return true if this list contains `instruction`. 113 bool Contains(HInstruction* instruction) const; 114 115 // Return true if `instruction1` is found before `instruction2` in 116 // this instruction list and false otherwise. Abort if none 117 // of these instructions is found. 118 bool FoundBefore(const HInstruction* instruction1, 119 const HInstruction* instruction2) const; 120 121 bool IsEmpty() const { return first_instruction_ == nullptr; } 122 void Clear() { first_instruction_ = last_instruction_ = nullptr; } 123 124 // Update the block of all instructions to be `block`. 125 void SetBlockOfInstructions(HBasicBlock* block) const; 126 127 void AddAfter(HInstruction* cursor, const HInstructionList& instruction_list); 128 void Add(const HInstructionList& instruction_list); 129 130 // Return the number of instructions in the list. This is an expensive operation. 131 size_t CountSize() const; 132 133 private: 134 HInstruction* first_instruction_; 135 HInstruction* last_instruction_; 136 137 friend class HBasicBlock; 138 friend class HGraph; 139 friend class HInstruction; 140 friend class HInstructionIterator; 141 friend class HBackwardInstructionIterator; 142 143 DISALLOW_COPY_AND_ASSIGN(HInstructionList); 144}; 145 146// Control-flow graph of a method. Contains a list of basic blocks. 147class HGraph : public ArenaObject<kArenaAllocGraph> { 148 public: 149 HGraph(ArenaAllocator* arena, 150 const DexFile& dex_file, 151 uint32_t method_idx, 152 bool should_generate_constructor_barrier, 153 InstructionSet instruction_set, 154 InvokeType invoke_type = kInvalidInvokeType, 155 bool debuggable = false, 156 int start_instruction_id = 0) 157 : arena_(arena), 158 blocks_(arena->Adapter(kArenaAllocBlockList)), 159 reverse_post_order_(arena->Adapter(kArenaAllocReversePostOrder)), 160 linear_order_(arena->Adapter(kArenaAllocLinearOrder)), 161 entry_block_(nullptr), 162 exit_block_(nullptr), 163 maximum_number_of_out_vregs_(0), 164 number_of_vregs_(0), 165 number_of_in_vregs_(0), 166 temporaries_vreg_slots_(0), 167 has_bounds_checks_(false), 168 has_try_catch_(false), 169 debuggable_(debuggable), 170 current_instruction_id_(start_instruction_id), 171 dex_file_(dex_file), 172 method_idx_(method_idx), 173 invoke_type_(invoke_type), 174 in_ssa_form_(false), 175 should_generate_constructor_barrier_(should_generate_constructor_barrier), 176 instruction_set_(instruction_set), 177 cached_null_constant_(nullptr), 178 cached_int_constants_(std::less<int32_t>(), arena->Adapter(kArenaAllocConstantsMap)), 179 cached_float_constants_(std::less<int32_t>(), arena->Adapter(kArenaAllocConstantsMap)), 180 cached_long_constants_(std::less<int64_t>(), arena->Adapter(kArenaAllocConstantsMap)), 181 cached_double_constants_(std::less<int64_t>(), arena->Adapter(kArenaAllocConstantsMap)), 182 cached_current_method_(nullptr) { 183 blocks_.reserve(kDefaultNumberOfBlocks); 184 } 185 186 ArenaAllocator* GetArena() const { return arena_; } 187 const ArenaVector<HBasicBlock*>& GetBlocks() const { return blocks_; } 188 189 bool IsInSsaForm() const { return in_ssa_form_; } 190 191 HBasicBlock* GetEntryBlock() const { return entry_block_; } 192 HBasicBlock* GetExitBlock() const { return exit_block_; } 193 bool HasExitBlock() const { return exit_block_ != nullptr; } 194 195 void SetEntryBlock(HBasicBlock* block) { entry_block_ = block; } 196 void SetExitBlock(HBasicBlock* block) { exit_block_ = block; } 197 198 void AddBlock(HBasicBlock* block); 199 200 // Try building the SSA form of this graph, with dominance computation and loop 201 // recognition. Returns whether it was successful in doing all these steps. 202 bool TryBuildingSsa() { 203 BuildDominatorTree(); 204 // The SSA builder requires loops to all be natural. Specifically, the dead phi 205 // elimination phase checks the consistency of the graph when doing a post-order 206 // visit for eliminating dead phis: a dead phi can only have loop header phi 207 // users remaining when being visited. 208 if (!AnalyzeNaturalLoops()) return false; 209 // Precompute per-block try membership before entering the SSA builder, 210 // which needs the information to build catch block phis from values of 211 // locals at throwing instructions inside try blocks. 212 ComputeTryBlockInformation(); 213 TransformToSsa(); 214 in_ssa_form_ = true; 215 return true; 216 } 217 218 void ComputeDominanceInformation(); 219 void ClearDominanceInformation(); 220 221 void BuildDominatorTree(); 222 void TransformToSsa(); 223 void SimplifyCFG(); 224 void SimplifyCatchBlocks(); 225 226 // Analyze all natural loops in this graph. Returns false if one 227 // loop is not natural, that is the header does not dominate the 228 // back edge. 229 bool AnalyzeNaturalLoops() const; 230 231 // Iterate over blocks to compute try block membership. Needs reverse post 232 // order and loop information. 233 void ComputeTryBlockInformation(); 234 235 // Inline this graph in `outer_graph`, replacing the given `invoke` instruction. 236 // Returns the instruction used to replace the invoke expression or null if the 237 // invoke is for a void method. 238 HInstruction* InlineInto(HGraph* outer_graph, HInvoke* invoke); 239 240 // Need to add a couple of blocks to test if the loop body is entered and 241 // put deoptimization instructions, etc. 242 void TransformLoopHeaderForBCE(HBasicBlock* header); 243 244 // Removes `block` from the graph. Assumes `block` has been disconnected from 245 // other blocks and has no instructions or phis. 246 void DeleteDeadEmptyBlock(HBasicBlock* block); 247 248 // Splits the edge between `block` and `successor` while preserving the 249 // indices in the predecessor/successor lists. If there are multiple edges 250 // between the blocks, the lowest indices are used. 251 // Returns the new block which is empty and has the same dex pc as `successor`. 252 HBasicBlock* SplitEdge(HBasicBlock* block, HBasicBlock* successor); 253 254 void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor); 255 void SimplifyLoop(HBasicBlock* header); 256 257 int32_t GetNextInstructionId() { 258 DCHECK_NE(current_instruction_id_, INT32_MAX); 259 return current_instruction_id_++; 260 } 261 262 int32_t GetCurrentInstructionId() const { 263 return current_instruction_id_; 264 } 265 266 void SetCurrentInstructionId(int32_t id) { 267 current_instruction_id_ = id; 268 } 269 270 uint16_t GetMaximumNumberOfOutVRegs() const { 271 return maximum_number_of_out_vregs_; 272 } 273 274 void SetMaximumNumberOfOutVRegs(uint16_t new_value) { 275 maximum_number_of_out_vregs_ = new_value; 276 } 277 278 void UpdateMaximumNumberOfOutVRegs(uint16_t other_value) { 279 maximum_number_of_out_vregs_ = std::max(maximum_number_of_out_vregs_, other_value); 280 } 281 282 void UpdateTemporariesVRegSlots(size_t slots) { 283 temporaries_vreg_slots_ = std::max(slots, temporaries_vreg_slots_); 284 } 285 286 size_t GetTemporariesVRegSlots() const { 287 DCHECK(!in_ssa_form_); 288 return temporaries_vreg_slots_; 289 } 290 291 void SetNumberOfVRegs(uint16_t number_of_vregs) { 292 number_of_vregs_ = number_of_vregs; 293 } 294 295 uint16_t GetNumberOfVRegs() const { 296 return number_of_vregs_; 297 } 298 299 void SetNumberOfInVRegs(uint16_t value) { 300 number_of_in_vregs_ = value; 301 } 302 303 uint16_t GetNumberOfLocalVRegs() const { 304 DCHECK(!in_ssa_form_); 305 return number_of_vregs_ - number_of_in_vregs_; 306 } 307 308 const ArenaVector<HBasicBlock*>& GetReversePostOrder() const { 309 return reverse_post_order_; 310 } 311 312 const ArenaVector<HBasicBlock*>& GetLinearOrder() const { 313 return linear_order_; 314 } 315 316 bool HasBoundsChecks() const { 317 return has_bounds_checks_; 318 } 319 320 void SetHasBoundsChecks(bool value) { 321 has_bounds_checks_ = value; 322 } 323 324 bool ShouldGenerateConstructorBarrier() const { 325 return should_generate_constructor_barrier_; 326 } 327 328 bool IsDebuggable() const { return debuggable_; } 329 330 // Returns a constant of the given type and value. If it does not exist 331 // already, it is created and inserted into the graph. This method is only for 332 // integral types. 333 HConstant* GetConstant(Primitive::Type type, int64_t value, uint32_t dex_pc = kNoDexPc); 334 335 // TODO: This is problematic for the consistency of reference type propagation 336 // because it can be created anytime after the pass and thus it will be left 337 // with an invalid type. 338 HNullConstant* GetNullConstant(uint32_t dex_pc = kNoDexPc); 339 340 HIntConstant* GetIntConstant(int32_t value, uint32_t dex_pc = kNoDexPc) { 341 return CreateConstant(value, &cached_int_constants_, dex_pc); 342 } 343 HLongConstant* GetLongConstant(int64_t value, uint32_t dex_pc = kNoDexPc) { 344 return CreateConstant(value, &cached_long_constants_, dex_pc); 345 } 346 HFloatConstant* GetFloatConstant(float value, uint32_t dex_pc = kNoDexPc) { 347 return CreateConstant(bit_cast<int32_t, float>(value), &cached_float_constants_, dex_pc); 348 } 349 HDoubleConstant* GetDoubleConstant(double value, uint32_t dex_pc = kNoDexPc) { 350 return CreateConstant(bit_cast<int64_t, double>(value), &cached_double_constants_, dex_pc); 351 } 352 353 HCurrentMethod* GetCurrentMethod(); 354 355 const DexFile& GetDexFile() const { 356 return dex_file_; 357 } 358 359 uint32_t GetMethodIdx() const { 360 return method_idx_; 361 } 362 363 InvokeType GetInvokeType() const { 364 return invoke_type_; 365 } 366 367 InstructionSet GetInstructionSet() const { 368 return instruction_set_; 369 } 370 371 bool HasTryCatch() const { return has_try_catch_; } 372 void SetHasTryCatch(bool value) { has_try_catch_ = value; } 373 374 private: 375 void FindBackEdges(ArenaBitVector* visited); 376 void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const; 377 void RemoveDeadBlocks(const ArenaBitVector& visited); 378 379 template <class InstructionType, typename ValueType> 380 InstructionType* CreateConstant(ValueType value, 381 ArenaSafeMap<ValueType, InstructionType*>* cache, 382 uint32_t dex_pc = kNoDexPc) { 383 // Try to find an existing constant of the given value. 384 InstructionType* constant = nullptr; 385 auto cached_constant = cache->find(value); 386 if (cached_constant != cache->end()) { 387 constant = cached_constant->second; 388 } 389 390 // If not found or previously deleted, create and cache a new instruction. 391 // Don't bother reviving a previously deleted instruction, for simplicity. 392 if (constant == nullptr || constant->GetBlock() == nullptr) { 393 constant = new (arena_) InstructionType(value, dex_pc); 394 cache->Overwrite(value, constant); 395 InsertConstant(constant); 396 } 397 return constant; 398 } 399 400 void InsertConstant(HConstant* instruction); 401 402 // Cache a float constant into the graph. This method should only be 403 // called by the SsaBuilder when creating "equivalent" instructions. 404 void CacheFloatConstant(HFloatConstant* constant); 405 406 // See CacheFloatConstant comment. 407 void CacheDoubleConstant(HDoubleConstant* constant); 408 409 ArenaAllocator* const arena_; 410 411 // List of blocks in insertion order. 412 ArenaVector<HBasicBlock*> blocks_; 413 414 // List of blocks to perform a reverse post order tree traversal. 415 ArenaVector<HBasicBlock*> reverse_post_order_; 416 417 // List of blocks to perform a linear order tree traversal. 418 ArenaVector<HBasicBlock*> linear_order_; 419 420 HBasicBlock* entry_block_; 421 HBasicBlock* exit_block_; 422 423 // The maximum number of virtual registers arguments passed to a HInvoke in this graph. 424 uint16_t maximum_number_of_out_vregs_; 425 426 // The number of virtual registers in this method. Contains the parameters. 427 uint16_t number_of_vregs_; 428 429 // The number of virtual registers used by parameters of this method. 430 uint16_t number_of_in_vregs_; 431 432 // Number of vreg size slots that the temporaries use (used in baseline compiler). 433 size_t temporaries_vreg_slots_; 434 435 // Has bounds checks. We can totally skip BCE if it's false. 436 bool has_bounds_checks_; 437 438 // Flag whether there are any try/catch blocks in the graph. We will skip 439 // try/catch-related passes if false. 440 bool has_try_catch_; 441 442 // Indicates whether the graph should be compiled in a way that 443 // ensures full debuggability. If false, we can apply more 444 // aggressive optimizations that may limit the level of debugging. 445 const bool debuggable_; 446 447 // The current id to assign to a newly added instruction. See HInstruction.id_. 448 int32_t current_instruction_id_; 449 450 // The dex file from which the method is from. 451 const DexFile& dex_file_; 452 453 // The method index in the dex file. 454 const uint32_t method_idx_; 455 456 // If inlined, this encodes how the callee is being invoked. 457 const InvokeType invoke_type_; 458 459 // Whether the graph has been transformed to SSA form. Only used 460 // in debug mode to ensure we are not using properties only valid 461 // for non-SSA form (like the number of temporaries). 462 bool in_ssa_form_; 463 464 const bool should_generate_constructor_barrier_; 465 466 const InstructionSet instruction_set_; 467 468 // Cached constants. 469 HNullConstant* cached_null_constant_; 470 ArenaSafeMap<int32_t, HIntConstant*> cached_int_constants_; 471 ArenaSafeMap<int32_t, HFloatConstant*> cached_float_constants_; 472 ArenaSafeMap<int64_t, HLongConstant*> cached_long_constants_; 473 ArenaSafeMap<int64_t, HDoubleConstant*> cached_double_constants_; 474 475 HCurrentMethod* cached_current_method_; 476 477 friend class SsaBuilder; // For caching constants. 478 friend class SsaLivenessAnalysis; // For the linear order. 479 ART_FRIEND_TEST(GraphTest, IfSuccessorSimpleJoinBlock1); 480 DISALLOW_COPY_AND_ASSIGN(HGraph); 481}; 482 483class HLoopInformation : public ArenaObject<kArenaAllocLoopInfo> { 484 public: 485 HLoopInformation(HBasicBlock* header, HGraph* graph) 486 : header_(header), 487 suspend_check_(nullptr), 488 back_edges_(graph->GetArena()->Adapter(kArenaAllocLoopInfoBackEdges)), 489 // Make bit vector growable, as the number of blocks may change. 490 blocks_(graph->GetArena(), graph->GetBlocks().size(), true) { 491 back_edges_.reserve(kDefaultNumberOfBackEdges); 492 } 493 494 HBasicBlock* GetHeader() const { 495 return header_; 496 } 497 498 void SetHeader(HBasicBlock* block) { 499 header_ = block; 500 } 501 502 HSuspendCheck* GetSuspendCheck() const { return suspend_check_; } 503 void SetSuspendCheck(HSuspendCheck* check) { suspend_check_ = check; } 504 bool HasSuspendCheck() const { return suspend_check_ != nullptr; } 505 506 void AddBackEdge(HBasicBlock* back_edge) { 507 back_edges_.push_back(back_edge); 508 } 509 510 void RemoveBackEdge(HBasicBlock* back_edge) { 511 RemoveElement(back_edges_, back_edge); 512 } 513 514 bool IsBackEdge(const HBasicBlock& block) const { 515 return ContainsElement(back_edges_, &block); 516 } 517 518 size_t NumberOfBackEdges() const { 519 return back_edges_.size(); 520 } 521 522 HBasicBlock* GetPreHeader() const; 523 524 const ArenaVector<HBasicBlock*>& GetBackEdges() const { 525 return back_edges_; 526 } 527 528 // Returns the lifetime position of the back edge that has the 529 // greatest lifetime position. 530 size_t GetLifetimeEnd() const; 531 532 void ReplaceBackEdge(HBasicBlock* existing, HBasicBlock* new_back_edge) { 533 ReplaceElement(back_edges_, existing, new_back_edge); 534 } 535 536 // Finds blocks that are part of this loop. Returns whether the loop is a natural loop, 537 // that is the header dominates the back edge. 538 bool Populate(); 539 540 // Reanalyzes the loop by removing loop info from its blocks and re-running 541 // Populate(). If there are no back edges left, the loop info is completely 542 // removed as well as its SuspendCheck instruction. It must be run on nested 543 // inner loops first. 544 void Update(); 545 546 // Returns whether this loop information contains `block`. 547 // Note that this loop information *must* be populated before entering this function. 548 bool Contains(const HBasicBlock& block) const; 549 550 // Returns whether this loop information is an inner loop of `other`. 551 // Note that `other` *must* be populated before entering this function. 552 bool IsIn(const HLoopInformation& other) const; 553 554 // Returns true if instruction is not defined within this loop or any loop nested inside 555 // this loop. If must_dominate is set, only definitions that actually dominate the loop 556 // header can be invariant. Otherwise, any definition outside the loop, including 557 // definitions that appear after the loop, is invariant. 558 bool IsLoopInvariant(HInstruction* instruction, bool must_dominate) const; 559 560 const ArenaBitVector& GetBlocks() const { return blocks_; } 561 562 void Add(HBasicBlock* block); 563 void Remove(HBasicBlock* block); 564 565 private: 566 // Internal recursive implementation of `Populate`. 567 void PopulateRecursive(HBasicBlock* block); 568 569 HBasicBlock* header_; 570 HSuspendCheck* suspend_check_; 571 ArenaVector<HBasicBlock*> back_edges_; 572 ArenaBitVector blocks_; 573 574 DISALLOW_COPY_AND_ASSIGN(HLoopInformation); 575}; 576 577// Stores try/catch information for basic blocks. 578// Note that HGraph is constructed so that catch blocks cannot simultaneously 579// be try blocks. 580class TryCatchInformation : public ArenaObject<kArenaAllocTryCatchInfo> { 581 public: 582 // Try block information constructor. 583 explicit TryCatchInformation(const HTryBoundary& try_entry) 584 : try_entry_(&try_entry), 585 catch_dex_file_(nullptr), 586 catch_type_index_(DexFile::kDexNoIndex16) { 587 DCHECK(try_entry_ != nullptr); 588 } 589 590 // Catch block information constructor. 591 TryCatchInformation(uint16_t catch_type_index, const DexFile& dex_file) 592 : try_entry_(nullptr), 593 catch_dex_file_(&dex_file), 594 catch_type_index_(catch_type_index) {} 595 596 bool IsTryBlock() const { return try_entry_ != nullptr; } 597 598 const HTryBoundary& GetTryEntry() const { 599 DCHECK(IsTryBlock()); 600 return *try_entry_; 601 } 602 603 bool IsCatchBlock() const { return catch_dex_file_ != nullptr; } 604 605 bool IsCatchAllTypeIndex() const { 606 DCHECK(IsCatchBlock()); 607 return catch_type_index_ == DexFile::kDexNoIndex16; 608 } 609 610 uint16_t GetCatchTypeIndex() const { 611 DCHECK(IsCatchBlock()); 612 return catch_type_index_; 613 } 614 615 const DexFile& GetCatchDexFile() const { 616 DCHECK(IsCatchBlock()); 617 return *catch_dex_file_; 618 } 619 620 private: 621 // One of possibly several TryBoundary instructions entering the block's try. 622 // Only set for try blocks. 623 const HTryBoundary* try_entry_; 624 625 // Exception type information. Only set for catch blocks. 626 const DexFile* catch_dex_file_; 627 const uint16_t catch_type_index_; 628}; 629 630static constexpr size_t kNoLifetime = -1; 631static constexpr uint32_t kInvalidBlockId = static_cast<uint32_t>(-1); 632 633// A block in a method. Contains the list of instructions represented 634// as a double linked list. Each block knows its predecessors and 635// successors. 636 637class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> { 638 public: 639 HBasicBlock(HGraph* graph, uint32_t dex_pc = kNoDexPc) 640 : graph_(graph), 641 predecessors_(graph->GetArena()->Adapter(kArenaAllocPredecessors)), 642 successors_(graph->GetArena()->Adapter(kArenaAllocSuccessors)), 643 loop_information_(nullptr), 644 dominator_(nullptr), 645 dominated_blocks_(graph->GetArena()->Adapter(kArenaAllocDominated)), 646 block_id_(kInvalidBlockId), 647 dex_pc_(dex_pc), 648 lifetime_start_(kNoLifetime), 649 lifetime_end_(kNoLifetime), 650 try_catch_information_(nullptr) { 651 predecessors_.reserve(kDefaultNumberOfPredecessors); 652 successors_.reserve(kDefaultNumberOfSuccessors); 653 dominated_blocks_.reserve(kDefaultNumberOfDominatedBlocks); 654 } 655 656 const ArenaVector<HBasicBlock*>& GetPredecessors() const { 657 return predecessors_; 658 } 659 660 const ArenaVector<HBasicBlock*>& GetSuccessors() const { 661 return successors_; 662 } 663 664 ArrayRef<HBasicBlock* const> GetNormalSuccessors() const; 665 ArrayRef<HBasicBlock* const> GetExceptionalSuccessors() const; 666 667 bool HasSuccessor(const HBasicBlock* block, size_t start_from = 0u) { 668 return ContainsElement(successors_, block, start_from); 669 } 670 671 const ArenaVector<HBasicBlock*>& GetDominatedBlocks() const { 672 return dominated_blocks_; 673 } 674 675 bool IsEntryBlock() const { 676 return graph_->GetEntryBlock() == this; 677 } 678 679 bool IsExitBlock() const { 680 return graph_->GetExitBlock() == this; 681 } 682 683 bool IsSingleGoto() const; 684 bool IsSingleTryBoundary() const; 685 686 // Returns true if this block emits nothing but a jump. 687 bool IsSingleJump() const { 688 HLoopInformation* loop_info = GetLoopInformation(); 689 return (IsSingleGoto() || IsSingleTryBoundary()) 690 // Back edges generate a suspend check. 691 && (loop_info == nullptr || !loop_info->IsBackEdge(*this)); 692 } 693 694 void AddBackEdge(HBasicBlock* back_edge) { 695 if (loop_information_ == nullptr) { 696 loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_); 697 } 698 DCHECK_EQ(loop_information_->GetHeader(), this); 699 loop_information_->AddBackEdge(back_edge); 700 } 701 702 HGraph* GetGraph() const { return graph_; } 703 void SetGraph(HGraph* graph) { graph_ = graph; } 704 705 uint32_t GetBlockId() const { return block_id_; } 706 void SetBlockId(int id) { block_id_ = id; } 707 uint32_t GetDexPc() const { return dex_pc_; } 708 709 HBasicBlock* GetDominator() const { return dominator_; } 710 void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; } 711 void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.push_back(block); } 712 713 void RemoveDominatedBlock(HBasicBlock* block) { 714 RemoveElement(dominated_blocks_, block); 715 } 716 717 void ReplaceDominatedBlock(HBasicBlock* existing, HBasicBlock* new_block) { 718 ReplaceElement(dominated_blocks_, existing, new_block); 719 } 720 721 void ClearDominanceInformation(); 722 723 int NumberOfBackEdges() const { 724 return IsLoopHeader() ? loop_information_->NumberOfBackEdges() : 0; 725 } 726 727 HInstruction* GetFirstInstruction() const { return instructions_.first_instruction_; } 728 HInstruction* GetLastInstruction() const { return instructions_.last_instruction_; } 729 const HInstructionList& GetInstructions() const { return instructions_; } 730 HInstruction* GetFirstPhi() const { return phis_.first_instruction_; } 731 HInstruction* GetLastPhi() const { return phis_.last_instruction_; } 732 const HInstructionList& GetPhis() const { return phis_; } 733 734 void AddSuccessor(HBasicBlock* block) { 735 successors_.push_back(block); 736 block->predecessors_.push_back(this); 737 } 738 739 void ReplaceSuccessor(HBasicBlock* existing, HBasicBlock* new_block) { 740 size_t successor_index = GetSuccessorIndexOf(existing); 741 existing->RemovePredecessor(this); 742 new_block->predecessors_.push_back(this); 743 successors_[successor_index] = new_block; 744 } 745 746 void ReplacePredecessor(HBasicBlock* existing, HBasicBlock* new_block) { 747 size_t predecessor_index = GetPredecessorIndexOf(existing); 748 existing->RemoveSuccessor(this); 749 new_block->successors_.push_back(this); 750 predecessors_[predecessor_index] = new_block; 751 } 752 753 // Insert `this` between `predecessor` and `successor. This method 754 // preserves the indicies, and will update the first edge found between 755 // `predecessor` and `successor`. 756 void InsertBetween(HBasicBlock* predecessor, HBasicBlock* successor) { 757 size_t predecessor_index = successor->GetPredecessorIndexOf(predecessor); 758 size_t successor_index = predecessor->GetSuccessorIndexOf(successor); 759 successor->predecessors_[predecessor_index] = this; 760 predecessor->successors_[successor_index] = this; 761 successors_.push_back(successor); 762 predecessors_.push_back(predecessor); 763 } 764 765 void RemovePredecessor(HBasicBlock* block) { 766 predecessors_.erase(predecessors_.begin() + GetPredecessorIndexOf(block)); 767 } 768 769 void RemoveSuccessor(HBasicBlock* block) { 770 successors_.erase(successors_.begin() + GetSuccessorIndexOf(block)); 771 } 772 773 void ClearAllPredecessors() { 774 predecessors_.clear(); 775 } 776 777 void AddPredecessor(HBasicBlock* block) { 778 predecessors_.push_back(block); 779 block->successors_.push_back(this); 780 } 781 782 void SwapPredecessors() { 783 DCHECK_EQ(predecessors_.size(), 2u); 784 std::swap(predecessors_[0], predecessors_[1]); 785 } 786 787 void SwapSuccessors() { 788 DCHECK_EQ(successors_.size(), 2u); 789 std::swap(successors_[0], successors_[1]); 790 } 791 792 size_t GetPredecessorIndexOf(HBasicBlock* predecessor) const { 793 return IndexOfElement(predecessors_, predecessor); 794 } 795 796 size_t GetSuccessorIndexOf(HBasicBlock* successor) const { 797 return IndexOfElement(successors_, successor); 798 } 799 800 HBasicBlock* GetSinglePredecessor() const { 801 DCHECK_EQ(GetPredecessors().size(), 1u); 802 return GetPredecessors()[0]; 803 } 804 805 HBasicBlock* GetSingleSuccessor() const { 806 DCHECK_EQ(GetSuccessors().size(), 1u); 807 return GetSuccessors()[0]; 808 } 809 810 // Returns whether the first occurrence of `predecessor` in the list of 811 // predecessors is at index `idx`. 812 bool IsFirstIndexOfPredecessor(HBasicBlock* predecessor, size_t idx) const { 813 DCHECK_EQ(GetPredecessors()[idx], predecessor); 814 return GetPredecessorIndexOf(predecessor) == idx; 815 } 816 817 // Create a new block between this block and its predecessors. The new block 818 // is added to the graph, all predecessor edges are relinked to it and an edge 819 // is created to `this`. Returns the new empty block. Reverse post order or 820 // loop and try/catch information are not updated. 821 HBasicBlock* CreateImmediateDominator(); 822 823 // Split the block into two blocks just before `cursor`. Returns the newly 824 // created, latter block. Note that this method will add the block to the 825 // graph, create a Goto at the end of the former block and will create an edge 826 // between the blocks. It will not, however, update the reverse post order or 827 // loop and try/catch information. 828 HBasicBlock* SplitBefore(HInstruction* cursor); 829 830 // Split the block into two blocks just after `cursor`. Returns the newly 831 // created block. Note that this method just updates raw block information, 832 // like predecessors, successors, dominators, and instruction list. It does not 833 // update the graph, reverse post order, loop information, nor make sure the 834 // blocks are consistent (for example ending with a control flow instruction). 835 HBasicBlock* SplitAfter(HInstruction* cursor); 836 837 // Split catch block into two blocks after the original move-exception bytecode 838 // instruction, or at the beginning if not present. Returns the newly created, 839 // latter block, or nullptr if such block could not be created (must be dead 840 // in that case). Note that this method just updates raw block information, 841 // like predecessors, successors, dominators, and instruction list. It does not 842 // update the graph, reverse post order, loop information, nor make sure the 843 // blocks are consistent (for example ending with a control flow instruction). 844 HBasicBlock* SplitCatchBlockAfterMoveException(); 845 846 // Merge `other` at the end of `this`. Successors and dominated blocks of 847 // `other` are changed to be successors and dominated blocks of `this`. Note 848 // that this method does not update the graph, reverse post order, loop 849 // information, nor make sure the blocks are consistent (for example ending 850 // with a control flow instruction). 851 void MergeWithInlined(HBasicBlock* other); 852 853 // Replace `this` with `other`. Predecessors, successors, and dominated blocks 854 // of `this` are moved to `other`. 855 // Note that this method does not update the graph, reverse post order, loop 856 // information, nor make sure the blocks are consistent (for example ending 857 // with a control flow instruction). 858 void ReplaceWith(HBasicBlock* other); 859 860 // Merge `other` at the end of `this`. This method updates loops, reverse post 861 // order, links to predecessors, successors, dominators and deletes the block 862 // from the graph. The two blocks must be successive, i.e. `this` the only 863 // predecessor of `other` and vice versa. 864 void MergeWith(HBasicBlock* other); 865 866 // Disconnects `this` from all its predecessors, successors and dominator, 867 // removes it from all loops it is included in and eventually from the graph. 868 // The block must not dominate any other block. Predecessors and successors 869 // are safely updated. 870 void DisconnectAndDelete(); 871 872 void AddInstruction(HInstruction* instruction); 873 // Insert `instruction` before/after an existing instruction `cursor`. 874 void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); 875 void InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor); 876 // Replace instruction `initial` with `replacement` within this block. 877 void ReplaceAndRemoveInstructionWith(HInstruction* initial, 878 HInstruction* replacement); 879 void AddPhi(HPhi* phi); 880 void InsertPhiAfter(HPhi* instruction, HPhi* cursor); 881 // RemoveInstruction and RemovePhi delete a given instruction from the respective 882 // instruction list. With 'ensure_safety' set to true, it verifies that the 883 // instruction is not in use and removes it from the use lists of its inputs. 884 void RemoveInstruction(HInstruction* instruction, bool ensure_safety = true); 885 void RemovePhi(HPhi* phi, bool ensure_safety = true); 886 void RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety = true); 887 888 bool IsLoopHeader() const { 889 return IsInLoop() && (loop_information_->GetHeader() == this); 890 } 891 892 bool IsLoopPreHeaderFirstPredecessor() const { 893 DCHECK(IsLoopHeader()); 894 return GetPredecessors()[0] == GetLoopInformation()->GetPreHeader(); 895 } 896 897 HLoopInformation* GetLoopInformation() const { 898 return loop_information_; 899 } 900 901 // Set the loop_information_ on this block. Overrides the current 902 // loop_information if it is an outer loop of the passed loop information. 903 // Note that this method is called while creating the loop information. 904 void SetInLoop(HLoopInformation* info) { 905 if (IsLoopHeader()) { 906 // Nothing to do. This just means `info` is an outer loop. 907 } else if (!IsInLoop()) { 908 loop_information_ = info; 909 } else if (loop_information_->Contains(*info->GetHeader())) { 910 // Block is currently part of an outer loop. Make it part of this inner loop. 911 // Note that a non loop header having a loop information means this loop information 912 // has already been populated 913 loop_information_ = info; 914 } else { 915 // Block is part of an inner loop. Do not update the loop information. 916 // Note that we cannot do the check `info->Contains(loop_information_)->GetHeader()` 917 // at this point, because this method is being called while populating `info`. 918 } 919 } 920 921 // Raw update of the loop information. 922 void SetLoopInformation(HLoopInformation* info) { 923 loop_information_ = info; 924 } 925 926 bool IsInLoop() const { return loop_information_ != nullptr; } 927 928 TryCatchInformation* GetTryCatchInformation() const { return try_catch_information_; } 929 930 void SetTryCatchInformation(TryCatchInformation* try_catch_information) { 931 try_catch_information_ = try_catch_information; 932 } 933 934 bool IsTryBlock() const { 935 return try_catch_information_ != nullptr && try_catch_information_->IsTryBlock(); 936 } 937 938 bool IsCatchBlock() const { 939 return try_catch_information_ != nullptr && try_catch_information_->IsCatchBlock(); 940 } 941 942 // Returns the try entry that this block's successors should have. They will 943 // be in the same try, unless the block ends in a try boundary. In that case, 944 // the appropriate try entry will be returned. 945 const HTryBoundary* ComputeTryEntryOfSuccessors() const; 946 947 bool HasThrowingInstructions() const; 948 949 // Returns whether this block dominates the blocked passed as parameter. 950 bool Dominates(HBasicBlock* block) const; 951 952 size_t GetLifetimeStart() const { return lifetime_start_; } 953 size_t GetLifetimeEnd() const { return lifetime_end_; } 954 955 void SetLifetimeStart(size_t start) { lifetime_start_ = start; } 956 void SetLifetimeEnd(size_t end) { lifetime_end_ = end; } 957 958 bool EndsWithControlFlowInstruction() const; 959 bool EndsWithIf() const; 960 bool EndsWithTryBoundary() const; 961 bool HasSinglePhi() const; 962 963 private: 964 HGraph* graph_; 965 ArenaVector<HBasicBlock*> predecessors_; 966 ArenaVector<HBasicBlock*> successors_; 967 HInstructionList instructions_; 968 HInstructionList phis_; 969 HLoopInformation* loop_information_; 970 HBasicBlock* dominator_; 971 ArenaVector<HBasicBlock*> dominated_blocks_; 972 uint32_t block_id_; 973 // The dex program counter of the first instruction of this block. 974 const uint32_t dex_pc_; 975 size_t lifetime_start_; 976 size_t lifetime_end_; 977 TryCatchInformation* try_catch_information_; 978 979 friend class HGraph; 980 friend class HInstruction; 981 982 DISALLOW_COPY_AND_ASSIGN(HBasicBlock); 983}; 984 985// Iterates over the LoopInformation of all loops which contain 'block' 986// from the innermost to the outermost. 987class HLoopInformationOutwardIterator : public ValueObject { 988 public: 989 explicit HLoopInformationOutwardIterator(const HBasicBlock& block) 990 : current_(block.GetLoopInformation()) {} 991 992 bool Done() const { return current_ == nullptr; } 993 994 void Advance() { 995 DCHECK(!Done()); 996 current_ = current_->GetPreHeader()->GetLoopInformation(); 997 } 998 999 HLoopInformation* Current() const { 1000 DCHECK(!Done()); 1001 return current_; 1002 } 1003 1004 private: 1005 HLoopInformation* current_; 1006 1007 DISALLOW_COPY_AND_ASSIGN(HLoopInformationOutwardIterator); 1008}; 1009 1010#define FOR_EACH_CONCRETE_INSTRUCTION_COMMON(M) \ 1011 M(Above, Condition) \ 1012 M(AboveOrEqual, Condition) \ 1013 M(Add, BinaryOperation) \ 1014 M(And, BinaryOperation) \ 1015 M(ArrayGet, Instruction) \ 1016 M(ArrayLength, Instruction) \ 1017 M(ArraySet, Instruction) \ 1018 M(Below, Condition) \ 1019 M(BelowOrEqual, Condition) \ 1020 M(BooleanNot, UnaryOperation) \ 1021 M(BoundsCheck, Instruction) \ 1022 M(BoundType, Instruction) \ 1023 M(CheckCast, Instruction) \ 1024 M(ClearException, Instruction) \ 1025 M(ClinitCheck, Instruction) \ 1026 M(Compare, BinaryOperation) \ 1027 M(Condition, BinaryOperation) \ 1028 M(CurrentMethod, Instruction) \ 1029 M(Deoptimize, Instruction) \ 1030 M(Div, BinaryOperation) \ 1031 M(DivZeroCheck, Instruction) \ 1032 M(DoubleConstant, Constant) \ 1033 M(Equal, Condition) \ 1034 M(Exit, Instruction) \ 1035 M(FakeString, Instruction) \ 1036 M(FloatConstant, Constant) \ 1037 M(Goto, Instruction) \ 1038 M(GreaterThan, Condition) \ 1039 M(GreaterThanOrEqual, Condition) \ 1040 M(If, Instruction) \ 1041 M(InstanceFieldGet, Instruction) \ 1042 M(InstanceFieldSet, Instruction) \ 1043 M(InstanceOf, Instruction) \ 1044 M(IntConstant, Constant) \ 1045 M(InvokeUnresolved, Invoke) \ 1046 M(InvokeInterface, Invoke) \ 1047 M(InvokeStaticOrDirect, Invoke) \ 1048 M(InvokeVirtual, Invoke) \ 1049 M(LessThan, Condition) \ 1050 M(LessThanOrEqual, Condition) \ 1051 M(LoadClass, Instruction) \ 1052 M(LoadException, Instruction) \ 1053 M(LoadLocal, Instruction) \ 1054 M(LoadString, Instruction) \ 1055 M(Local, Instruction) \ 1056 M(LongConstant, Constant) \ 1057 M(MemoryBarrier, Instruction) \ 1058 M(MonitorOperation, Instruction) \ 1059 M(Mul, BinaryOperation) \ 1060 M(Neg, UnaryOperation) \ 1061 M(NewArray, Instruction) \ 1062 M(NewInstance, Instruction) \ 1063 M(Not, UnaryOperation) \ 1064 M(NotEqual, Condition) \ 1065 M(NullConstant, Instruction) \ 1066 M(NullCheck, Instruction) \ 1067 M(Or, BinaryOperation) \ 1068 M(PackedSwitch, Instruction) \ 1069 M(ParallelMove, Instruction) \ 1070 M(ParameterValue, Instruction) \ 1071 M(Phi, Instruction) \ 1072 M(Rem, BinaryOperation) \ 1073 M(Return, Instruction) \ 1074 M(ReturnVoid, Instruction) \ 1075 M(Shl, BinaryOperation) \ 1076 M(Shr, BinaryOperation) \ 1077 M(StaticFieldGet, Instruction) \ 1078 M(StaticFieldSet, Instruction) \ 1079 M(UnresolvedInstanceFieldGet, Instruction) \ 1080 M(UnresolvedInstanceFieldSet, Instruction) \ 1081 M(UnresolvedStaticFieldGet, Instruction) \ 1082 M(UnresolvedStaticFieldSet, Instruction) \ 1083 M(StoreLocal, Instruction) \ 1084 M(Sub, BinaryOperation) \ 1085 M(SuspendCheck, Instruction) \ 1086 M(Temporary, Instruction) \ 1087 M(Throw, Instruction) \ 1088 M(TryBoundary, Instruction) \ 1089 M(TypeConversion, Instruction) \ 1090 M(UShr, BinaryOperation) \ 1091 M(Xor, BinaryOperation) \ 1092 1093#define FOR_EACH_CONCRETE_INSTRUCTION_ARM(M) 1094 1095#ifndef ART_ENABLE_CODEGEN_arm64 1096#define FOR_EACH_CONCRETE_INSTRUCTION_ARM64(M) 1097#else 1098#define FOR_EACH_CONCRETE_INSTRUCTION_ARM64(M) \ 1099 M(Arm64IntermediateAddress, Instruction) 1100#endif 1101 1102#define FOR_EACH_CONCRETE_INSTRUCTION_MIPS(M) 1103 1104#define FOR_EACH_CONCRETE_INSTRUCTION_MIPS64(M) 1105 1106#ifndef ART_ENABLE_CODEGEN_x86 1107#define FOR_EACH_CONCRETE_INSTRUCTION_X86(M) 1108#else 1109#define FOR_EACH_CONCRETE_INSTRUCTION_X86(M) \ 1110 M(X86ComputeBaseMethodAddress, Instruction) \ 1111 M(X86LoadFromConstantTable, Instruction) \ 1112 M(X86PackedSwitch, Instruction) 1113#endif 1114 1115#define FOR_EACH_CONCRETE_INSTRUCTION_X86_64(M) 1116 1117#define FOR_EACH_CONCRETE_INSTRUCTION(M) \ 1118 FOR_EACH_CONCRETE_INSTRUCTION_COMMON(M) \ 1119 FOR_EACH_CONCRETE_INSTRUCTION_ARM(M) \ 1120 FOR_EACH_CONCRETE_INSTRUCTION_ARM64(M) \ 1121 FOR_EACH_CONCRETE_INSTRUCTION_MIPS(M) \ 1122 FOR_EACH_CONCRETE_INSTRUCTION_MIPS64(M) \ 1123 FOR_EACH_CONCRETE_INSTRUCTION_X86(M) \ 1124 FOR_EACH_CONCRETE_INSTRUCTION_X86_64(M) 1125 1126#define FOR_EACH_INSTRUCTION(M) \ 1127 FOR_EACH_CONCRETE_INSTRUCTION(M) \ 1128 M(Constant, Instruction) \ 1129 M(UnaryOperation, Instruction) \ 1130 M(BinaryOperation, Instruction) \ 1131 M(Invoke, Instruction) 1132 1133#define FORWARD_DECLARATION(type, super) class H##type; 1134FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) 1135#undef FORWARD_DECLARATION 1136 1137#define DECLARE_INSTRUCTION(type) \ 1138 InstructionKind GetKind() const OVERRIDE { return k##type; } \ 1139 const char* DebugName() const OVERRIDE { return #type; } \ 1140 const H##type* As##type() const OVERRIDE { return this; } \ 1141 H##type* As##type() OVERRIDE { return this; } \ 1142 bool InstructionTypeEquals(HInstruction* other) const OVERRIDE { \ 1143 return other->Is##type(); \ 1144 } \ 1145 void Accept(HGraphVisitor* visitor) OVERRIDE 1146 1147template <typename T> class HUseList; 1148 1149template <typename T> 1150class HUseListNode : public ArenaObject<kArenaAllocUseListNode> { 1151 public: 1152 HUseListNode* GetPrevious() const { return prev_; } 1153 HUseListNode* GetNext() const { return next_; } 1154 T GetUser() const { return user_; } 1155 size_t GetIndex() const { return index_; } 1156 void SetIndex(size_t index) { index_ = index; } 1157 1158 private: 1159 HUseListNode(T user, size_t index) 1160 : user_(user), index_(index), prev_(nullptr), next_(nullptr) {} 1161 1162 T const user_; 1163 size_t index_; 1164 HUseListNode<T>* prev_; 1165 HUseListNode<T>* next_; 1166 1167 friend class HUseList<T>; 1168 1169 DISALLOW_COPY_AND_ASSIGN(HUseListNode); 1170}; 1171 1172template <typename T> 1173class HUseList : public ValueObject { 1174 public: 1175 HUseList() : first_(nullptr) {} 1176 1177 void Clear() { 1178 first_ = nullptr; 1179 } 1180 1181 // Adds a new entry at the beginning of the use list and returns 1182 // the newly created node. 1183 HUseListNode<T>* AddUse(T user, size_t index, ArenaAllocator* arena) { 1184 HUseListNode<T>* new_node = new (arena) HUseListNode<T>(user, index); 1185 if (IsEmpty()) { 1186 first_ = new_node; 1187 } else { 1188 first_->prev_ = new_node; 1189 new_node->next_ = first_; 1190 first_ = new_node; 1191 } 1192 return new_node; 1193 } 1194 1195 HUseListNode<T>* GetFirst() const { 1196 return first_; 1197 } 1198 1199 void Remove(HUseListNode<T>* node) { 1200 DCHECK(node != nullptr); 1201 DCHECK(Contains(node)); 1202 1203 if (node->prev_ != nullptr) { 1204 node->prev_->next_ = node->next_; 1205 } 1206 if (node->next_ != nullptr) { 1207 node->next_->prev_ = node->prev_; 1208 } 1209 if (node == first_) { 1210 first_ = node->next_; 1211 } 1212 } 1213 1214 bool Contains(const HUseListNode<T>* node) const { 1215 if (node == nullptr) { 1216 return false; 1217 } 1218 for (HUseListNode<T>* current = first_; current != nullptr; current = current->GetNext()) { 1219 if (current == node) { 1220 return true; 1221 } 1222 } 1223 return false; 1224 } 1225 1226 bool IsEmpty() const { 1227 return first_ == nullptr; 1228 } 1229 1230 bool HasOnlyOneUse() const { 1231 return first_ != nullptr && first_->next_ == nullptr; 1232 } 1233 1234 size_t SizeSlow() const { 1235 size_t count = 0; 1236 for (HUseListNode<T>* current = first_; current != nullptr; current = current->GetNext()) { 1237 ++count; 1238 } 1239 return count; 1240 } 1241 1242 private: 1243 HUseListNode<T>* first_; 1244}; 1245 1246template<typename T> 1247class HUseIterator : public ValueObject { 1248 public: 1249 explicit HUseIterator(const HUseList<T>& uses) : current_(uses.GetFirst()) {} 1250 1251 bool Done() const { return current_ == nullptr; } 1252 1253 void Advance() { 1254 DCHECK(!Done()); 1255 current_ = current_->GetNext(); 1256 } 1257 1258 HUseListNode<T>* Current() const { 1259 DCHECK(!Done()); 1260 return current_; 1261 } 1262 1263 private: 1264 HUseListNode<T>* current_; 1265 1266 friend class HValue; 1267}; 1268 1269// This class is used by HEnvironment and HInstruction classes to record the 1270// instructions they use and pointers to the corresponding HUseListNodes kept 1271// by the used instructions. 1272template <typename T> 1273class HUserRecord : public ValueObject { 1274 public: 1275 HUserRecord() : instruction_(nullptr), use_node_(nullptr) {} 1276 explicit HUserRecord(HInstruction* instruction) : instruction_(instruction), use_node_(nullptr) {} 1277 1278 HUserRecord(const HUserRecord<T>& old_record, HUseListNode<T>* use_node) 1279 : instruction_(old_record.instruction_), use_node_(use_node) { 1280 DCHECK(instruction_ != nullptr); 1281 DCHECK(use_node_ != nullptr); 1282 DCHECK(old_record.use_node_ == nullptr); 1283 } 1284 1285 HInstruction* GetInstruction() const { return instruction_; } 1286 HUseListNode<T>* GetUseNode() const { return use_node_; } 1287 1288 private: 1289 // Instruction used by the user. 1290 HInstruction* instruction_; 1291 1292 // Corresponding entry in the use list kept by 'instruction_'. 1293 HUseListNode<T>* use_node_; 1294}; 1295 1296/** 1297 * Side-effects representation. 1298 * 1299 * For write/read dependences on fields/arrays, the dependence analysis uses 1300 * type disambiguation (e.g. a float field write cannot modify the value of an 1301 * integer field read) and the access type (e.g. a reference array write cannot 1302 * modify the value of a reference field read [although it may modify the 1303 * reference fetch prior to reading the field, which is represented by its own 1304 * write/read dependence]). The analysis makes conservative points-to 1305 * assumptions on reference types (e.g. two same typed arrays are assumed to be 1306 * the same, and any reference read depends on any reference read without 1307 * further regard of its type). 1308 * 1309 * The internal representation uses 38-bit and is described in the table below. 1310 * The first line indicates the side effect, and for field/array accesses the 1311 * second line indicates the type of the access (in the order of the 1312 * Primitive::Type enum). 1313 * The two numbered lines below indicate the bit position in the bitfield (read 1314 * vertically). 1315 * 1316 * |Depends on GC|ARRAY-R |FIELD-R |Can trigger GC|ARRAY-W |FIELD-W | 1317 * +-------------+---------+---------+--------------+---------+---------+ 1318 * | |DFJISCBZL|DFJISCBZL| |DFJISCBZL|DFJISCBZL| 1319 * | 3 |333333322|222222221| 1 |111111110|000000000| 1320 * | 7 |654321098|765432109| 8 |765432109|876543210| 1321 * 1322 * Note that, to ease the implementation, 'changes' bits are least significant 1323 * bits, while 'dependency' bits are most significant bits. 1324 */ 1325class SideEffects : public ValueObject { 1326 public: 1327 SideEffects() : flags_(0) {} 1328 1329 static SideEffects None() { 1330 return SideEffects(0); 1331 } 1332 1333 static SideEffects All() { 1334 return SideEffects(kAllChangeBits | kAllDependOnBits); 1335 } 1336 1337 static SideEffects AllChanges() { 1338 return SideEffects(kAllChangeBits); 1339 } 1340 1341 static SideEffects AllDependencies() { 1342 return SideEffects(kAllDependOnBits); 1343 } 1344 1345 static SideEffects AllExceptGCDependency() { 1346 return AllWritesAndReads().Union(SideEffects::CanTriggerGC()); 1347 } 1348 1349 static SideEffects AllWritesAndReads() { 1350 return SideEffects(kAllWrites | kAllReads); 1351 } 1352 1353 static SideEffects AllWrites() { 1354 return SideEffects(kAllWrites); 1355 } 1356 1357 static SideEffects AllReads() { 1358 return SideEffects(kAllReads); 1359 } 1360 1361 static SideEffects FieldWriteOfType(Primitive::Type type, bool is_volatile) { 1362 return is_volatile 1363 ? AllWritesAndReads() 1364 : SideEffects(TypeFlagWithAlias(type, kFieldWriteOffset)); 1365 } 1366 1367 static SideEffects ArrayWriteOfType(Primitive::Type type) { 1368 return SideEffects(TypeFlagWithAlias(type, kArrayWriteOffset)); 1369 } 1370 1371 static SideEffects FieldReadOfType(Primitive::Type type, bool is_volatile) { 1372 return is_volatile 1373 ? AllWritesAndReads() 1374 : SideEffects(TypeFlagWithAlias(type, kFieldReadOffset)); 1375 } 1376 1377 static SideEffects ArrayReadOfType(Primitive::Type type) { 1378 return SideEffects(TypeFlagWithAlias(type, kArrayReadOffset)); 1379 } 1380 1381 static SideEffects CanTriggerGC() { 1382 return SideEffects(1ULL << kCanTriggerGCBit); 1383 } 1384 1385 static SideEffects DependsOnGC() { 1386 return SideEffects(1ULL << kDependsOnGCBit); 1387 } 1388 1389 // Combines the side-effects of this and the other. 1390 SideEffects Union(SideEffects other) const { 1391 return SideEffects(flags_ | other.flags_); 1392 } 1393 1394 SideEffects Exclusion(SideEffects other) const { 1395 return SideEffects(flags_ & ~other.flags_); 1396 } 1397 1398 void Add(SideEffects other) { 1399 flags_ |= other.flags_; 1400 } 1401 1402 bool Includes(SideEffects other) const { 1403 return (other.flags_ & flags_) == other.flags_; 1404 } 1405 1406 bool HasSideEffects() const { 1407 return (flags_ & kAllChangeBits); 1408 } 1409 1410 bool HasDependencies() const { 1411 return (flags_ & kAllDependOnBits); 1412 } 1413 1414 // Returns true if there are no side effects or dependencies. 1415 bool DoesNothing() const { 1416 return flags_ == 0; 1417 } 1418 1419 // Returns true if something is written. 1420 bool DoesAnyWrite() const { 1421 return (flags_ & kAllWrites); 1422 } 1423 1424 // Returns true if something is read. 1425 bool DoesAnyRead() const { 1426 return (flags_ & kAllReads); 1427 } 1428 1429 // Returns true if potentially everything is written and read 1430 // (every type and every kind of access). 1431 bool DoesAllReadWrite() const { 1432 return (flags_ & (kAllWrites | kAllReads)) == (kAllWrites | kAllReads); 1433 } 1434 1435 bool DoesAll() const { 1436 return flags_ == (kAllChangeBits | kAllDependOnBits); 1437 } 1438 1439 // Returns true if `this` may read something written by `other`. 1440 bool MayDependOn(SideEffects other) const { 1441 const uint64_t depends_on_flags = (flags_ & kAllDependOnBits) >> kChangeBits; 1442 return (other.flags_ & depends_on_flags); 1443 } 1444 1445 // Returns string representation of flags (for debugging only). 1446 // Format: |x|DFJISCBZL|DFJISCBZL|y|DFJISCBZL|DFJISCBZL| 1447 std::string ToString() const { 1448 std::string flags = "|"; 1449 for (int s = kLastBit; s >= 0; s--) { 1450 bool current_bit_is_set = ((flags_ >> s) & 1) != 0; 1451 if ((s == kDependsOnGCBit) || (s == kCanTriggerGCBit)) { 1452 // This is a bit for the GC side effect. 1453 if (current_bit_is_set) { 1454 flags += "GC"; 1455 } 1456 flags += "|"; 1457 } else { 1458 // This is a bit for the array/field analysis. 1459 // The underscore character stands for the 'can trigger GC' bit. 1460 static const char *kDebug = "LZBCSIJFDLZBCSIJFD_LZBCSIJFDLZBCSIJFD"; 1461 if (current_bit_is_set) { 1462 flags += kDebug[s]; 1463 } 1464 if ((s == kFieldWriteOffset) || (s == kArrayWriteOffset) || 1465 (s == kFieldReadOffset) || (s == kArrayReadOffset)) { 1466 flags += "|"; 1467 } 1468 } 1469 } 1470 return flags; 1471 } 1472 1473 bool Equals(const SideEffects& other) const { return flags_ == other.flags_; } 1474 1475 private: 1476 static constexpr int kFieldArrayAnalysisBits = 9; 1477 1478 static constexpr int kFieldWriteOffset = 0; 1479 static constexpr int kArrayWriteOffset = kFieldWriteOffset + kFieldArrayAnalysisBits; 1480 static constexpr int kLastBitForWrites = kArrayWriteOffset + kFieldArrayAnalysisBits - 1; 1481 static constexpr int kCanTriggerGCBit = kLastBitForWrites + 1; 1482 1483 static constexpr int kChangeBits = kCanTriggerGCBit + 1; 1484 1485 static constexpr int kFieldReadOffset = kCanTriggerGCBit + 1; 1486 static constexpr int kArrayReadOffset = kFieldReadOffset + kFieldArrayAnalysisBits; 1487 static constexpr int kLastBitForReads = kArrayReadOffset + kFieldArrayAnalysisBits - 1; 1488 static constexpr int kDependsOnGCBit = kLastBitForReads + 1; 1489 1490 static constexpr int kLastBit = kDependsOnGCBit; 1491 static constexpr int kDependOnBits = kLastBit + 1 - kChangeBits; 1492 1493 // Aliases. 1494 1495 static_assert(kChangeBits == kDependOnBits, 1496 "the 'change' bits should match the 'depend on' bits."); 1497 1498 static constexpr uint64_t kAllChangeBits = ((1ULL << kChangeBits) - 1); 1499 static constexpr uint64_t kAllDependOnBits = ((1ULL << kDependOnBits) - 1) << kChangeBits; 1500 static constexpr uint64_t kAllWrites = 1501 ((1ULL << (kLastBitForWrites + 1 - kFieldWriteOffset)) - 1) << kFieldWriteOffset; 1502 static constexpr uint64_t kAllReads = 1503 ((1ULL << (kLastBitForReads + 1 - kFieldReadOffset)) - 1) << kFieldReadOffset; 1504 1505 // Work around the fact that HIR aliases I/F and J/D. 1506 // TODO: remove this interceptor once HIR types are clean 1507 static uint64_t TypeFlagWithAlias(Primitive::Type type, int offset) { 1508 switch (type) { 1509 case Primitive::kPrimInt: 1510 case Primitive::kPrimFloat: 1511 return TypeFlag(Primitive::kPrimInt, offset) | 1512 TypeFlag(Primitive::kPrimFloat, offset); 1513 case Primitive::kPrimLong: 1514 case Primitive::kPrimDouble: 1515 return TypeFlag(Primitive::kPrimLong, offset) | 1516 TypeFlag(Primitive::kPrimDouble, offset); 1517 default: 1518 return TypeFlag(type, offset); 1519 } 1520 } 1521 1522 // Translates type to bit flag. 1523 static uint64_t TypeFlag(Primitive::Type type, int offset) { 1524 CHECK_NE(type, Primitive::kPrimVoid); 1525 const uint64_t one = 1; 1526 const int shift = type; // 0-based consecutive enum 1527 DCHECK_LE(kFieldWriteOffset, shift); 1528 DCHECK_LT(shift, kArrayWriteOffset); 1529 return one << (type + offset); 1530 } 1531 1532 // Private constructor on direct flags value. 1533 explicit SideEffects(uint64_t flags) : flags_(flags) {} 1534 1535 uint64_t flags_; 1536}; 1537 1538// A HEnvironment object contains the values of virtual registers at a given location. 1539class HEnvironment : public ArenaObject<kArenaAllocEnvironment> { 1540 public: 1541 HEnvironment(ArenaAllocator* arena, 1542 size_t number_of_vregs, 1543 const DexFile& dex_file, 1544 uint32_t method_idx, 1545 uint32_t dex_pc, 1546 InvokeType invoke_type, 1547 HInstruction* holder) 1548 : vregs_(number_of_vregs, arena->Adapter(kArenaAllocEnvironmentVRegs)), 1549 locations_(number_of_vregs, arena->Adapter(kArenaAllocEnvironmentLocations)), 1550 parent_(nullptr), 1551 dex_file_(dex_file), 1552 method_idx_(method_idx), 1553 dex_pc_(dex_pc), 1554 invoke_type_(invoke_type), 1555 holder_(holder) { 1556 } 1557 1558 HEnvironment(ArenaAllocator* arena, const HEnvironment& to_copy, HInstruction* holder) 1559 : HEnvironment(arena, 1560 to_copy.Size(), 1561 to_copy.GetDexFile(), 1562 to_copy.GetMethodIdx(), 1563 to_copy.GetDexPc(), 1564 to_copy.GetInvokeType(), 1565 holder) {} 1566 1567 void SetAndCopyParentChain(ArenaAllocator* allocator, HEnvironment* parent) { 1568 if (parent_ != nullptr) { 1569 parent_->SetAndCopyParentChain(allocator, parent); 1570 } else { 1571 parent_ = new (allocator) HEnvironment(allocator, *parent, holder_); 1572 parent_->CopyFrom(parent); 1573 if (parent->GetParent() != nullptr) { 1574 parent_->SetAndCopyParentChain(allocator, parent->GetParent()); 1575 } 1576 } 1577 } 1578 1579 void CopyFrom(const ArenaVector<HInstruction*>& locals); 1580 void CopyFrom(HEnvironment* environment); 1581 1582 // Copy from `env`. If it's a loop phi for `loop_header`, copy the first 1583 // input to the loop phi instead. This is for inserting instructions that 1584 // require an environment (like HDeoptimization) in the loop pre-header. 1585 void CopyFromWithLoopPhiAdjustment(HEnvironment* env, HBasicBlock* loop_header); 1586 1587 void SetRawEnvAt(size_t index, HInstruction* instruction) { 1588 vregs_[index] = HUserRecord<HEnvironment*>(instruction); 1589 } 1590 1591 HInstruction* GetInstructionAt(size_t index) const { 1592 return vregs_[index].GetInstruction(); 1593 } 1594 1595 void RemoveAsUserOfInput(size_t index) const; 1596 1597 size_t Size() const { return vregs_.size(); } 1598 1599 HEnvironment* GetParent() const { return parent_; } 1600 1601 void SetLocationAt(size_t index, Location location) { 1602 locations_[index] = location; 1603 } 1604 1605 Location GetLocationAt(size_t index) const { 1606 return locations_[index]; 1607 } 1608 1609 uint32_t GetDexPc() const { 1610 return dex_pc_; 1611 } 1612 1613 uint32_t GetMethodIdx() const { 1614 return method_idx_; 1615 } 1616 1617 InvokeType GetInvokeType() const { 1618 return invoke_type_; 1619 } 1620 1621 const DexFile& GetDexFile() const { 1622 return dex_file_; 1623 } 1624 1625 HInstruction* GetHolder() const { 1626 return holder_; 1627 } 1628 1629 private: 1630 // Record instructions' use entries of this environment for constant-time removal. 1631 // It should only be called by HInstruction when a new environment use is added. 1632 void RecordEnvUse(HUseListNode<HEnvironment*>* env_use) { 1633 DCHECK(env_use->GetUser() == this); 1634 size_t index = env_use->GetIndex(); 1635 vregs_[index] = HUserRecord<HEnvironment*>(vregs_[index], env_use); 1636 } 1637 1638 ArenaVector<HUserRecord<HEnvironment*>> vregs_; 1639 ArenaVector<Location> locations_; 1640 HEnvironment* parent_; 1641 const DexFile& dex_file_; 1642 const uint32_t method_idx_; 1643 const uint32_t dex_pc_; 1644 const InvokeType invoke_type_; 1645 1646 // The instruction that holds this environment. 1647 HInstruction* const holder_; 1648 1649 friend class HInstruction; 1650 1651 DISALLOW_COPY_AND_ASSIGN(HEnvironment); 1652}; 1653 1654class ReferenceTypeInfo : ValueObject { 1655 public: 1656 typedef Handle<mirror::Class> TypeHandle; 1657 1658 static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact) { 1659 // The constructor will check that the type_handle is valid. 1660 return ReferenceTypeInfo(type_handle, is_exact); 1661 } 1662 1663 static ReferenceTypeInfo CreateInvalid() { return ReferenceTypeInfo(); } 1664 1665 static bool IsValidHandle(TypeHandle handle) SHARED_REQUIRES(Locks::mutator_lock_) { 1666 return handle.GetReference() != nullptr; 1667 } 1668 1669 bool IsValid() const SHARED_REQUIRES(Locks::mutator_lock_) { 1670 return IsValidHandle(type_handle_); 1671 } 1672 1673 bool IsExact() const { return is_exact_; } 1674 1675 bool IsObjectClass() const SHARED_REQUIRES(Locks::mutator_lock_) { 1676 DCHECK(IsValid()); 1677 return GetTypeHandle()->IsObjectClass(); 1678 } 1679 1680 bool IsStringClass() const SHARED_REQUIRES(Locks::mutator_lock_) { 1681 DCHECK(IsValid()); 1682 return GetTypeHandle()->IsStringClass(); 1683 } 1684 1685 bool IsObjectArray() const SHARED_REQUIRES(Locks::mutator_lock_) { 1686 DCHECK(IsValid()); 1687 return IsArrayClass() && GetTypeHandle()->GetComponentType()->IsObjectClass(); 1688 } 1689 1690 bool IsInterface() const SHARED_REQUIRES(Locks::mutator_lock_) { 1691 DCHECK(IsValid()); 1692 return GetTypeHandle()->IsInterface(); 1693 } 1694 1695 bool IsArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) { 1696 DCHECK(IsValid()); 1697 return GetTypeHandle()->IsArrayClass(); 1698 } 1699 1700 bool IsPrimitiveArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) { 1701 DCHECK(IsValid()); 1702 return GetTypeHandle()->IsPrimitiveArray(); 1703 } 1704 1705 bool IsNonPrimitiveArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) { 1706 DCHECK(IsValid()); 1707 return GetTypeHandle()->IsArrayClass() && !GetTypeHandle()->IsPrimitiveArray(); 1708 } 1709 1710 bool CanArrayHold(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { 1711 DCHECK(IsValid()); 1712 if (!IsExact()) return false; 1713 if (!IsArrayClass()) return false; 1714 return GetTypeHandle()->GetComponentType()->IsAssignableFrom(rti.GetTypeHandle().Get()); 1715 } 1716 1717 bool CanArrayHoldValuesOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { 1718 DCHECK(IsValid()); 1719 if (!IsExact()) return false; 1720 if (!IsArrayClass()) return false; 1721 if (!rti.IsArrayClass()) return false; 1722 return GetTypeHandle()->GetComponentType()->IsAssignableFrom( 1723 rti.GetTypeHandle()->GetComponentType()); 1724 } 1725 1726 Handle<mirror::Class> GetTypeHandle() const { return type_handle_; } 1727 1728 bool IsSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { 1729 DCHECK(IsValid()); 1730 DCHECK(rti.IsValid()); 1731 return GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get()); 1732 } 1733 1734 bool IsStrictSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { 1735 DCHECK(IsValid()); 1736 DCHECK(rti.IsValid()); 1737 return GetTypeHandle().Get() != rti.GetTypeHandle().Get() && 1738 GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get()); 1739 } 1740 1741 // Returns true if the type information provide the same amount of details. 1742 // Note that it does not mean that the instructions have the same actual type 1743 // (because the type can be the result of a merge). 1744 bool IsEqual(ReferenceTypeInfo rti) SHARED_REQUIRES(Locks::mutator_lock_) { 1745 if (!IsValid() && !rti.IsValid()) { 1746 // Invalid types are equal. 1747 return true; 1748 } 1749 if (!IsValid() || !rti.IsValid()) { 1750 // One is valid, the other not. 1751 return false; 1752 } 1753 return IsExact() == rti.IsExact() 1754 && GetTypeHandle().Get() == rti.GetTypeHandle().Get(); 1755 } 1756 1757 private: 1758 ReferenceTypeInfo(); 1759 ReferenceTypeInfo(TypeHandle type_handle, bool is_exact); 1760 1761 // The class of the object. 1762 TypeHandle type_handle_; 1763 // Whether or not the type is exact or a superclass of the actual type. 1764 // Whether or not we have any information about this type. 1765 bool is_exact_; 1766}; 1767 1768std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs); 1769 1770class HInstruction : public ArenaObject<kArenaAllocInstruction> { 1771 public: 1772 HInstruction(SideEffects side_effects, uint32_t dex_pc) 1773 : previous_(nullptr), 1774 next_(nullptr), 1775 block_(nullptr), 1776 dex_pc_(dex_pc), 1777 id_(-1), 1778 ssa_index_(-1), 1779 environment_(nullptr), 1780 locations_(nullptr), 1781 live_interval_(nullptr), 1782 lifetime_position_(kNoLifetime), 1783 side_effects_(side_effects), 1784 reference_type_info_(ReferenceTypeInfo::CreateInvalid()) {} 1785 1786 virtual ~HInstruction() {} 1787 1788#define DECLARE_KIND(type, super) k##type, 1789 enum InstructionKind { 1790 FOR_EACH_INSTRUCTION(DECLARE_KIND) 1791 }; 1792#undef DECLARE_KIND 1793 1794 HInstruction* GetNext() const { return next_; } 1795 HInstruction* GetPrevious() const { return previous_; } 1796 1797 HInstruction* GetNextDisregardingMoves() const; 1798 HInstruction* GetPreviousDisregardingMoves() const; 1799 1800 HBasicBlock* GetBlock() const { return block_; } 1801 ArenaAllocator* GetArena() const { return block_->GetGraph()->GetArena(); } 1802 void SetBlock(HBasicBlock* block) { block_ = block; } 1803 bool IsInBlock() const { return block_ != nullptr; } 1804 bool IsInLoop() const { return block_->IsInLoop(); } 1805 bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); } 1806 1807 virtual size_t InputCount() const = 0; 1808 HInstruction* InputAt(size_t i) const { return InputRecordAt(i).GetInstruction(); } 1809 1810 virtual void Accept(HGraphVisitor* visitor) = 0; 1811 virtual const char* DebugName() const = 0; 1812 1813 virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; } 1814 void SetRawInputAt(size_t index, HInstruction* input) { 1815 SetRawInputRecordAt(index, HUserRecord<HInstruction*>(input)); 1816 } 1817 1818 virtual bool NeedsEnvironment() const { return false; } 1819 1820 uint32_t GetDexPc() const { return dex_pc_; } 1821 1822 virtual bool IsControlFlow() const { return false; } 1823 1824 virtual bool CanThrow() const { return false; } 1825 bool CanThrowIntoCatchBlock() const { return CanThrow() && block_->IsTryBlock(); } 1826 1827 bool HasSideEffects() const { return side_effects_.HasSideEffects(); } 1828 bool DoesAnyWrite() const { return side_effects_.DoesAnyWrite(); } 1829 1830 // Does not apply for all instructions, but having this at top level greatly 1831 // simplifies the null check elimination. 1832 // TODO: Consider merging can_be_null into ReferenceTypeInfo. 1833 virtual bool CanBeNull() const { 1834 DCHECK_EQ(GetType(), Primitive::kPrimNot) << "CanBeNull only applies to reference types"; 1835 return true; 1836 } 1837 1838 virtual bool CanDoImplicitNullCheckOn(HInstruction* obj ATTRIBUTE_UNUSED) const { 1839 return false; 1840 } 1841 1842 void SetReferenceTypeInfo(ReferenceTypeInfo rti); 1843 1844 ReferenceTypeInfo GetReferenceTypeInfo() const { 1845 DCHECK_EQ(GetType(), Primitive::kPrimNot); 1846 return reference_type_info_; 1847 } 1848 1849 void AddUseAt(HInstruction* user, size_t index) { 1850 DCHECK(user != nullptr); 1851 HUseListNode<HInstruction*>* use = 1852 uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); 1853 user->SetRawInputRecordAt(index, HUserRecord<HInstruction*>(user->InputRecordAt(index), use)); 1854 } 1855 1856 void AddEnvUseAt(HEnvironment* user, size_t index) { 1857 DCHECK(user != nullptr); 1858 HUseListNode<HEnvironment*>* env_use = 1859 env_uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); 1860 user->RecordEnvUse(env_use); 1861 } 1862 1863 void RemoveAsUserOfInput(size_t input) { 1864 HUserRecord<HInstruction*> input_use = InputRecordAt(input); 1865 input_use.GetInstruction()->uses_.Remove(input_use.GetUseNode()); 1866 } 1867 1868 const HUseList<HInstruction*>& GetUses() const { return uses_; } 1869 const HUseList<HEnvironment*>& GetEnvUses() const { return env_uses_; } 1870 1871 bool HasUses() const { return !uses_.IsEmpty() || !env_uses_.IsEmpty(); } 1872 bool HasEnvironmentUses() const { return !env_uses_.IsEmpty(); } 1873 bool HasNonEnvironmentUses() const { return !uses_.IsEmpty(); } 1874 bool HasOnlyOneNonEnvironmentUse() const { 1875 return !HasEnvironmentUses() && GetUses().HasOnlyOneUse(); 1876 } 1877 1878 // Does this instruction strictly dominate `other_instruction`? 1879 // Returns false if this instruction and `other_instruction` are the same. 1880 // Aborts if this instruction and `other_instruction` are both phis. 1881 bool StrictlyDominates(HInstruction* other_instruction) const; 1882 1883 int GetId() const { return id_; } 1884 void SetId(int id) { id_ = id; } 1885 1886 int GetSsaIndex() const { return ssa_index_; } 1887 void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; } 1888 bool HasSsaIndex() const { return ssa_index_ != -1; } 1889 1890 bool HasEnvironment() const { return environment_ != nullptr; } 1891 HEnvironment* GetEnvironment() const { return environment_; } 1892 // Set the `environment_` field. Raw because this method does not 1893 // update the uses lists. 1894 void SetRawEnvironment(HEnvironment* environment) { 1895 DCHECK(environment_ == nullptr); 1896 DCHECK_EQ(environment->GetHolder(), this); 1897 environment_ = environment; 1898 } 1899 1900 // Set the environment of this instruction, copying it from `environment`. While 1901 // copying, the uses lists are being updated. 1902 void CopyEnvironmentFrom(HEnvironment* environment) { 1903 DCHECK(environment_ == nullptr); 1904 ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena(); 1905 environment_ = new (allocator) HEnvironment(allocator, *environment, this); 1906 environment_->CopyFrom(environment); 1907 if (environment->GetParent() != nullptr) { 1908 environment_->SetAndCopyParentChain(allocator, environment->GetParent()); 1909 } 1910 } 1911 1912 void CopyEnvironmentFromWithLoopPhiAdjustment(HEnvironment* environment, 1913 HBasicBlock* block) { 1914 DCHECK(environment_ == nullptr); 1915 ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena(); 1916 environment_ = new (allocator) HEnvironment(allocator, *environment, this); 1917 environment_->CopyFromWithLoopPhiAdjustment(environment, block); 1918 if (environment->GetParent() != nullptr) { 1919 environment_->SetAndCopyParentChain(allocator, environment->GetParent()); 1920 } 1921 } 1922 1923 // Returns the number of entries in the environment. Typically, that is the 1924 // number of dex registers in a method. It could be more in case of inlining. 1925 size_t EnvironmentSize() const; 1926 1927 LocationSummary* GetLocations() const { return locations_; } 1928 void SetLocations(LocationSummary* locations) { locations_ = locations; } 1929 1930 void ReplaceWith(HInstruction* instruction); 1931 void ReplaceInput(HInstruction* replacement, size_t index); 1932 1933 // This is almost the same as doing `ReplaceWith()`. But in this helper, the 1934 // uses of this instruction by `other` are *not* updated. 1935 void ReplaceWithExceptInReplacementAtIndex(HInstruction* other, size_t use_index) { 1936 ReplaceWith(other); 1937 other->ReplaceInput(this, use_index); 1938 } 1939 1940 // Move `this` instruction before `cursor`. 1941 void MoveBefore(HInstruction* cursor); 1942 1943#define INSTRUCTION_TYPE_CHECK(type, super) \ 1944 bool Is##type() const { return (As##type() != nullptr); } \ 1945 virtual const H##type* As##type() const { return nullptr; } \ 1946 virtual H##type* As##type() { return nullptr; } 1947 1948 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 1949#undef INSTRUCTION_TYPE_CHECK 1950 1951 // Returns whether the instruction can be moved within the graph. 1952 virtual bool CanBeMoved() const { return false; } 1953 1954 // Returns whether the two instructions are of the same kind. 1955 virtual bool InstructionTypeEquals(HInstruction* other ATTRIBUTE_UNUSED) const { 1956 return false; 1957 } 1958 1959 // Returns whether any data encoded in the two instructions is equal. 1960 // This method does not look at the inputs. Both instructions must be 1961 // of the same type, otherwise the method has undefined behavior. 1962 virtual bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const { 1963 return false; 1964 } 1965 1966 // Returns whether two instructions are equal, that is: 1967 // 1) They have the same type and contain the same data (InstructionDataEquals). 1968 // 2) Their inputs are identical. 1969 bool Equals(HInstruction* other) const; 1970 1971 virtual InstructionKind GetKind() const = 0; 1972 1973 virtual size_t ComputeHashCode() const { 1974 size_t result = GetKind(); 1975 for (size_t i = 0, e = InputCount(); i < e; ++i) { 1976 result = (result * 31) + InputAt(i)->GetId(); 1977 } 1978 return result; 1979 } 1980 1981 SideEffects GetSideEffects() const { return side_effects_; } 1982 void AddSideEffects(SideEffects other) { side_effects_.Add(other); } 1983 1984 size_t GetLifetimePosition() const { return lifetime_position_; } 1985 void SetLifetimePosition(size_t position) { lifetime_position_ = position; } 1986 LiveInterval* GetLiveInterval() const { return live_interval_; } 1987 void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; } 1988 bool HasLiveInterval() const { return live_interval_ != nullptr; } 1989 1990 bool IsSuspendCheckEntry() const { return IsSuspendCheck() && GetBlock()->IsEntryBlock(); } 1991 1992 // Returns whether the code generation of the instruction will require to have access 1993 // to the current method. Such instructions are: 1994 // (1): Instructions that require an environment, as calling the runtime requires 1995 // to walk the stack and have the current method stored at a specific stack address. 1996 // (2): Object literals like classes and strings, that are loaded from the dex cache 1997 // fields of the current method. 1998 bool NeedsCurrentMethod() const { 1999 return NeedsEnvironment() || IsLoadClass() || IsLoadString(); 2000 } 2001 2002 // Returns whether the code generation of the instruction will require to have access 2003 // to the dex cache of the current method's declaring class via the current method. 2004 virtual bool NeedsDexCacheOfDeclaringClass() const { return false; } 2005 2006 // Does this instruction have any use in an environment before 2007 // control flow hits 'other'? 2008 bool HasAnyEnvironmentUseBefore(HInstruction* other); 2009 2010 // Remove all references to environment uses of this instruction. 2011 // The caller must ensure that this is safe to do. 2012 void RemoveEnvironmentUsers(); 2013 2014 protected: 2015 virtual const HUserRecord<HInstruction*> InputRecordAt(size_t i) const = 0; 2016 virtual void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) = 0; 2017 2018 private: 2019 void RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use_node) { env_uses_.Remove(use_node); } 2020 2021 HInstruction* previous_; 2022 HInstruction* next_; 2023 HBasicBlock* block_; 2024 const uint32_t dex_pc_; 2025 2026 // An instruction gets an id when it is added to the graph. 2027 // It reflects creation order. A negative id means the instruction 2028 // has not been added to the graph. 2029 int id_; 2030 2031 // When doing liveness analysis, instructions that have uses get an SSA index. 2032 int ssa_index_; 2033 2034 // List of instructions that have this instruction as input. 2035 HUseList<HInstruction*> uses_; 2036 2037 // List of environments that contain this instruction. 2038 HUseList<HEnvironment*> env_uses_; 2039 2040 // The environment associated with this instruction. Not null if the instruction 2041 // might jump out of the method. 2042 HEnvironment* environment_; 2043 2044 // Set by the code generator. 2045 LocationSummary* locations_; 2046 2047 // Set by the liveness analysis. 2048 LiveInterval* live_interval_; 2049 2050 // Set by the liveness analysis, this is the position in a linear 2051 // order of blocks where this instruction's live interval start. 2052 size_t lifetime_position_; 2053 2054 SideEffects side_effects_; 2055 2056 // TODO: for primitive types this should be marked as invalid. 2057 ReferenceTypeInfo reference_type_info_; 2058 2059 friend class GraphChecker; 2060 friend class HBasicBlock; 2061 friend class HEnvironment; 2062 friend class HGraph; 2063 friend class HInstructionList; 2064 2065 DISALLOW_COPY_AND_ASSIGN(HInstruction); 2066}; 2067std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs); 2068 2069class HInputIterator : public ValueObject { 2070 public: 2071 explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {} 2072 2073 bool Done() const { return index_ == instruction_->InputCount(); } 2074 HInstruction* Current() const { return instruction_->InputAt(index_); } 2075 void Advance() { index_++; } 2076 2077 private: 2078 HInstruction* instruction_; 2079 size_t index_; 2080 2081 DISALLOW_COPY_AND_ASSIGN(HInputIterator); 2082}; 2083 2084class HInstructionIterator : public ValueObject { 2085 public: 2086 explicit HInstructionIterator(const HInstructionList& instructions) 2087 : instruction_(instructions.first_instruction_) { 2088 next_ = Done() ? nullptr : instruction_->GetNext(); 2089 } 2090 2091 bool Done() const { return instruction_ == nullptr; } 2092 HInstruction* Current() const { return instruction_; } 2093 void Advance() { 2094 instruction_ = next_; 2095 next_ = Done() ? nullptr : instruction_->GetNext(); 2096 } 2097 2098 private: 2099 HInstruction* instruction_; 2100 HInstruction* next_; 2101 2102 DISALLOW_COPY_AND_ASSIGN(HInstructionIterator); 2103}; 2104 2105class HBackwardInstructionIterator : public ValueObject { 2106 public: 2107 explicit HBackwardInstructionIterator(const HInstructionList& instructions) 2108 : instruction_(instructions.last_instruction_) { 2109 next_ = Done() ? nullptr : instruction_->GetPrevious(); 2110 } 2111 2112 bool Done() const { return instruction_ == nullptr; } 2113 HInstruction* Current() const { return instruction_; } 2114 void Advance() { 2115 instruction_ = next_; 2116 next_ = Done() ? nullptr : instruction_->GetPrevious(); 2117 } 2118 2119 private: 2120 HInstruction* instruction_; 2121 HInstruction* next_; 2122 2123 DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator); 2124}; 2125 2126template<size_t N> 2127class HTemplateInstruction: public HInstruction { 2128 public: 2129 HTemplateInstruction<N>(SideEffects side_effects, uint32_t dex_pc) 2130 : HInstruction(side_effects, dex_pc), inputs_() {} 2131 virtual ~HTemplateInstruction() {} 2132 2133 size_t InputCount() const OVERRIDE { return N; } 2134 2135 protected: 2136 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { 2137 DCHECK_LT(i, N); 2138 return inputs_[i]; 2139 } 2140 2141 void SetRawInputRecordAt(size_t i, const HUserRecord<HInstruction*>& input) OVERRIDE { 2142 DCHECK_LT(i, N); 2143 inputs_[i] = input; 2144 } 2145 2146 private: 2147 std::array<HUserRecord<HInstruction*>, N> inputs_; 2148 2149 friend class SsaBuilder; 2150}; 2151 2152// HTemplateInstruction specialization for N=0. 2153template<> 2154class HTemplateInstruction<0>: public HInstruction { 2155 public: 2156 explicit HTemplateInstruction<0>(SideEffects side_effects, uint32_t dex_pc) 2157 : HInstruction(side_effects, dex_pc) {} 2158 2159 virtual ~HTemplateInstruction() {} 2160 2161 size_t InputCount() const OVERRIDE { return 0; } 2162 2163 protected: 2164 const HUserRecord<HInstruction*> InputRecordAt(size_t i ATTRIBUTE_UNUSED) const OVERRIDE { 2165 LOG(FATAL) << "Unreachable"; 2166 UNREACHABLE(); 2167 } 2168 2169 void SetRawInputRecordAt(size_t i ATTRIBUTE_UNUSED, 2170 const HUserRecord<HInstruction*>& input ATTRIBUTE_UNUSED) OVERRIDE { 2171 LOG(FATAL) << "Unreachable"; 2172 UNREACHABLE(); 2173 } 2174 2175 private: 2176 friend class SsaBuilder; 2177}; 2178 2179template<intptr_t N> 2180class HExpression : public HTemplateInstruction<N> { 2181 public: 2182 HExpression<N>(Primitive::Type type, SideEffects side_effects, uint32_t dex_pc) 2183 : HTemplateInstruction<N>(side_effects, dex_pc), type_(type) {} 2184 virtual ~HExpression() {} 2185 2186 Primitive::Type GetType() const OVERRIDE { return type_; } 2187 2188 protected: 2189 Primitive::Type type_; 2190}; 2191 2192// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow 2193// instruction that branches to the exit block. 2194class HReturnVoid : public HTemplateInstruction<0> { 2195 public: 2196 explicit HReturnVoid(uint32_t dex_pc = kNoDexPc) 2197 : HTemplateInstruction(SideEffects::None(), dex_pc) {} 2198 2199 bool IsControlFlow() const OVERRIDE { return true; } 2200 2201 DECLARE_INSTRUCTION(ReturnVoid); 2202 2203 private: 2204 DISALLOW_COPY_AND_ASSIGN(HReturnVoid); 2205}; 2206 2207// Represents dex's RETURN opcodes. A HReturn is a control flow 2208// instruction that branches to the exit block. 2209class HReturn : public HTemplateInstruction<1> { 2210 public: 2211 explicit HReturn(HInstruction* value, uint32_t dex_pc = kNoDexPc) 2212 : HTemplateInstruction(SideEffects::None(), dex_pc) { 2213 SetRawInputAt(0, value); 2214 } 2215 2216 bool IsControlFlow() const OVERRIDE { return true; } 2217 2218 DECLARE_INSTRUCTION(Return); 2219 2220 private: 2221 DISALLOW_COPY_AND_ASSIGN(HReturn); 2222}; 2223 2224// The exit instruction is the only instruction of the exit block. 2225// Instructions aborting the method (HThrow and HReturn) must branch to the 2226// exit block. 2227class HExit : public HTemplateInstruction<0> { 2228 public: 2229 explicit HExit(uint32_t dex_pc = kNoDexPc) : HTemplateInstruction(SideEffects::None(), dex_pc) {} 2230 2231 bool IsControlFlow() const OVERRIDE { return true; } 2232 2233 DECLARE_INSTRUCTION(Exit); 2234 2235 private: 2236 DISALLOW_COPY_AND_ASSIGN(HExit); 2237}; 2238 2239// Jumps from one block to another. 2240class HGoto : public HTemplateInstruction<0> { 2241 public: 2242 explicit HGoto(uint32_t dex_pc = kNoDexPc) : HTemplateInstruction(SideEffects::None(), dex_pc) {} 2243 2244 bool IsControlFlow() const OVERRIDE { return true; } 2245 2246 HBasicBlock* GetSuccessor() const { 2247 return GetBlock()->GetSingleSuccessor(); 2248 } 2249 2250 DECLARE_INSTRUCTION(Goto); 2251 2252 private: 2253 DISALLOW_COPY_AND_ASSIGN(HGoto); 2254}; 2255 2256class HConstant : public HExpression<0> { 2257 public: 2258 explicit HConstant(Primitive::Type type, uint32_t dex_pc = kNoDexPc) 2259 : HExpression(type, SideEffects::None(), dex_pc) {} 2260 2261 bool CanBeMoved() const OVERRIDE { return true; } 2262 2263 virtual bool IsMinusOne() const { return false; } 2264 virtual bool IsZero() const { return false; } 2265 virtual bool IsOne() const { return false; } 2266 2267 virtual uint64_t GetValueAsUint64() const = 0; 2268 2269 DECLARE_INSTRUCTION(Constant); 2270 2271 private: 2272 DISALLOW_COPY_AND_ASSIGN(HConstant); 2273}; 2274 2275class HNullConstant : public HConstant { 2276 public: 2277 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2278 return true; 2279 } 2280 2281 uint64_t GetValueAsUint64() const OVERRIDE { return 0; } 2282 2283 size_t ComputeHashCode() const OVERRIDE { return 0; } 2284 2285 DECLARE_INSTRUCTION(NullConstant); 2286 2287 private: 2288 explicit HNullConstant(uint32_t dex_pc = kNoDexPc) : HConstant(Primitive::kPrimNot, dex_pc) {} 2289 2290 friend class HGraph; 2291 DISALLOW_COPY_AND_ASSIGN(HNullConstant); 2292}; 2293 2294// Constants of the type int. Those can be from Dex instructions, or 2295// synthesized (for example with the if-eqz instruction). 2296class HIntConstant : public HConstant { 2297 public: 2298 int32_t GetValue() const { return value_; } 2299 2300 uint64_t GetValueAsUint64() const OVERRIDE { 2301 return static_cast<uint64_t>(static_cast<uint32_t>(value_)); 2302 } 2303 2304 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2305 DCHECK(other->IsIntConstant()); 2306 return other->AsIntConstant()->value_ == value_; 2307 } 2308 2309 size_t ComputeHashCode() const OVERRIDE { return GetValue(); } 2310 2311 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2312 bool IsZero() const OVERRIDE { return GetValue() == 0; } 2313 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2314 2315 DECLARE_INSTRUCTION(IntConstant); 2316 2317 private: 2318 explicit HIntConstant(int32_t value, uint32_t dex_pc = kNoDexPc) 2319 : HConstant(Primitive::kPrimInt, dex_pc), value_(value) {} 2320 explicit HIntConstant(bool value, uint32_t dex_pc = kNoDexPc) 2321 : HConstant(Primitive::kPrimInt, dex_pc), value_(value ? 1 : 0) {} 2322 2323 const int32_t value_; 2324 2325 friend class HGraph; 2326 ART_FRIEND_TEST(GraphTest, InsertInstructionBefore); 2327 ART_FRIEND_TYPED_TEST(ParallelMoveTest, ConstantLast); 2328 DISALLOW_COPY_AND_ASSIGN(HIntConstant); 2329}; 2330 2331class HLongConstant : public HConstant { 2332 public: 2333 int64_t GetValue() const { return value_; } 2334 2335 uint64_t GetValueAsUint64() const OVERRIDE { return value_; } 2336 2337 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2338 DCHECK(other->IsLongConstant()); 2339 return other->AsLongConstant()->value_ == value_; 2340 } 2341 2342 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2343 2344 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2345 bool IsZero() const OVERRIDE { return GetValue() == 0; } 2346 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2347 2348 DECLARE_INSTRUCTION(LongConstant); 2349 2350 private: 2351 explicit HLongConstant(int64_t value, uint32_t dex_pc = kNoDexPc) 2352 : HConstant(Primitive::kPrimLong, dex_pc), value_(value) {} 2353 2354 const int64_t value_; 2355 2356 friend class HGraph; 2357 DISALLOW_COPY_AND_ASSIGN(HLongConstant); 2358}; 2359 2360// Conditional branch. A block ending with an HIf instruction must have 2361// two successors. 2362class HIf : public HTemplateInstruction<1> { 2363 public: 2364 explicit HIf(HInstruction* input, uint32_t dex_pc = kNoDexPc) 2365 : HTemplateInstruction(SideEffects::None(), dex_pc) { 2366 SetRawInputAt(0, input); 2367 } 2368 2369 bool IsControlFlow() const OVERRIDE { return true; } 2370 2371 HBasicBlock* IfTrueSuccessor() const { 2372 return GetBlock()->GetSuccessors()[0]; 2373 } 2374 2375 HBasicBlock* IfFalseSuccessor() const { 2376 return GetBlock()->GetSuccessors()[1]; 2377 } 2378 2379 DECLARE_INSTRUCTION(If); 2380 2381 private: 2382 DISALLOW_COPY_AND_ASSIGN(HIf); 2383}; 2384 2385 2386// Abstract instruction which marks the beginning and/or end of a try block and 2387// links it to the respective exception handlers. Behaves the same as a Goto in 2388// non-exceptional control flow. 2389// Normal-flow successor is stored at index zero, exception handlers under 2390// higher indices in no particular order. 2391class HTryBoundary : public HTemplateInstruction<0> { 2392 public: 2393 enum BoundaryKind { 2394 kEntry, 2395 kExit, 2396 }; 2397 2398 explicit HTryBoundary(BoundaryKind kind, uint32_t dex_pc = kNoDexPc) 2399 : HTemplateInstruction(SideEffects::None(), dex_pc), kind_(kind) {} 2400 2401 bool IsControlFlow() const OVERRIDE { return true; } 2402 2403 // Returns the block's non-exceptional successor (index zero). 2404 HBasicBlock* GetNormalFlowSuccessor() const { return GetBlock()->GetSuccessors()[0]; } 2405 2406 ArrayRef<HBasicBlock* const> GetExceptionHandlers() const { 2407 return ArrayRef<HBasicBlock* const>(GetBlock()->GetSuccessors()).SubArray(1u); 2408 } 2409 2410 // Returns whether `handler` is among its exception handlers (non-zero index 2411 // successors). 2412 bool HasExceptionHandler(const HBasicBlock& handler) const { 2413 DCHECK(handler.IsCatchBlock()); 2414 return GetBlock()->HasSuccessor(&handler, 1u /* Skip first successor. */); 2415 } 2416 2417 // If not present already, adds `handler` to its block's list of exception 2418 // handlers. 2419 void AddExceptionHandler(HBasicBlock* handler) { 2420 if (!HasExceptionHandler(*handler)) { 2421 GetBlock()->AddSuccessor(handler); 2422 } 2423 } 2424 2425 bool IsEntry() const { return kind_ == BoundaryKind::kEntry; } 2426 2427 bool HasSameExceptionHandlersAs(const HTryBoundary& other) const; 2428 2429 DECLARE_INSTRUCTION(TryBoundary); 2430 2431 private: 2432 const BoundaryKind kind_; 2433 2434 DISALLOW_COPY_AND_ASSIGN(HTryBoundary); 2435}; 2436 2437// Deoptimize to interpreter, upon checking a condition. 2438class HDeoptimize : public HTemplateInstruction<1> { 2439 public: 2440 explicit HDeoptimize(HInstruction* cond, uint32_t dex_pc) 2441 : HTemplateInstruction(SideEffects::None(), dex_pc) { 2442 SetRawInputAt(0, cond); 2443 } 2444 2445 bool NeedsEnvironment() const OVERRIDE { return true; } 2446 bool CanThrow() const OVERRIDE { return true; } 2447 2448 DECLARE_INSTRUCTION(Deoptimize); 2449 2450 private: 2451 DISALLOW_COPY_AND_ASSIGN(HDeoptimize); 2452}; 2453 2454// Represents the ArtMethod that was passed as a first argument to 2455// the method. It is used by instructions that depend on it, like 2456// instructions that work with the dex cache. 2457class HCurrentMethod : public HExpression<0> { 2458 public: 2459 explicit HCurrentMethod(Primitive::Type type, uint32_t dex_pc = kNoDexPc) 2460 : HExpression(type, SideEffects::None(), dex_pc) {} 2461 2462 DECLARE_INSTRUCTION(CurrentMethod); 2463 2464 private: 2465 DISALLOW_COPY_AND_ASSIGN(HCurrentMethod); 2466}; 2467 2468// PackedSwitch (jump table). A block ending with a PackedSwitch instruction will 2469// have one successor for each entry in the switch table, and the final successor 2470// will be the block containing the next Dex opcode. 2471class HPackedSwitch : public HTemplateInstruction<1> { 2472 public: 2473 HPackedSwitch(int32_t start_value, 2474 uint32_t num_entries, 2475 HInstruction* input, 2476 uint32_t dex_pc = kNoDexPc) 2477 : HTemplateInstruction(SideEffects::None(), dex_pc), 2478 start_value_(start_value), 2479 num_entries_(num_entries) { 2480 SetRawInputAt(0, input); 2481 } 2482 2483 bool IsControlFlow() const OVERRIDE { return true; } 2484 2485 int32_t GetStartValue() const { return start_value_; } 2486 2487 uint32_t GetNumEntries() const { return num_entries_; } 2488 2489 HBasicBlock* GetDefaultBlock() const { 2490 // Last entry is the default block. 2491 return GetBlock()->GetSuccessors()[num_entries_]; 2492 } 2493 DECLARE_INSTRUCTION(PackedSwitch); 2494 2495 private: 2496 const int32_t start_value_; 2497 const uint32_t num_entries_; 2498 2499 DISALLOW_COPY_AND_ASSIGN(HPackedSwitch); 2500}; 2501 2502class HUnaryOperation : public HExpression<1> { 2503 public: 2504 HUnaryOperation(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc = kNoDexPc) 2505 : HExpression(result_type, SideEffects::None(), dex_pc) { 2506 SetRawInputAt(0, input); 2507 } 2508 2509 HInstruction* GetInput() const { return InputAt(0); } 2510 Primitive::Type GetResultType() const { return GetType(); } 2511 2512 bool CanBeMoved() const OVERRIDE { return true; } 2513 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2514 return true; 2515 } 2516 2517 // Try to statically evaluate `operation` and return a HConstant 2518 // containing the result of this evaluation. If `operation` cannot 2519 // be evaluated as a constant, return null. 2520 HConstant* TryStaticEvaluation() const; 2521 2522 // Apply this operation to `x`. 2523 virtual HConstant* Evaluate(HIntConstant* x) const = 0; 2524 virtual HConstant* Evaluate(HLongConstant* x) const = 0; 2525 2526 DECLARE_INSTRUCTION(UnaryOperation); 2527 2528 private: 2529 DISALLOW_COPY_AND_ASSIGN(HUnaryOperation); 2530}; 2531 2532class HBinaryOperation : public HExpression<2> { 2533 public: 2534 HBinaryOperation(Primitive::Type result_type, 2535 HInstruction* left, 2536 HInstruction* right, 2537 SideEffects side_effects = SideEffects::None(), 2538 uint32_t dex_pc = kNoDexPc) 2539 : HExpression(result_type, side_effects, dex_pc) { 2540 SetRawInputAt(0, left); 2541 SetRawInputAt(1, right); 2542 } 2543 2544 HInstruction* GetLeft() const { return InputAt(0); } 2545 HInstruction* GetRight() const { return InputAt(1); } 2546 Primitive::Type GetResultType() const { return GetType(); } 2547 2548 virtual bool IsCommutative() const { return false; } 2549 2550 // Put constant on the right. 2551 // Returns whether order is changed. 2552 bool OrderInputsWithConstantOnTheRight() { 2553 HInstruction* left = InputAt(0); 2554 HInstruction* right = InputAt(1); 2555 if (left->IsConstant() && !right->IsConstant()) { 2556 ReplaceInput(right, 0); 2557 ReplaceInput(left, 1); 2558 return true; 2559 } 2560 return false; 2561 } 2562 2563 // Order inputs by instruction id, but favor constant on the right side. 2564 // This helps GVN for commutative ops. 2565 void OrderInputs() { 2566 DCHECK(IsCommutative()); 2567 HInstruction* left = InputAt(0); 2568 HInstruction* right = InputAt(1); 2569 if (left == right || (!left->IsConstant() && right->IsConstant())) { 2570 return; 2571 } 2572 if (OrderInputsWithConstantOnTheRight()) { 2573 return; 2574 } 2575 // Order according to instruction id. 2576 if (left->GetId() > right->GetId()) { 2577 ReplaceInput(right, 0); 2578 ReplaceInput(left, 1); 2579 } 2580 } 2581 2582 bool CanBeMoved() const OVERRIDE { return true; } 2583 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2584 return true; 2585 } 2586 2587 // Try to statically evaluate `operation` and return a HConstant 2588 // containing the result of this evaluation. If `operation` cannot 2589 // be evaluated as a constant, return null. 2590 HConstant* TryStaticEvaluation() const; 2591 2592 // Apply this operation to `x` and `y`. 2593 virtual HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const = 0; 2594 virtual HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const = 0; 2595 virtual HConstant* Evaluate(HIntConstant* x ATTRIBUTE_UNUSED, 2596 HLongConstant* y ATTRIBUTE_UNUSED) const { 2597 VLOG(compiler) << DebugName() << " is not defined for the (int, long) case."; 2598 return nullptr; 2599 } 2600 virtual HConstant* Evaluate(HLongConstant* x ATTRIBUTE_UNUSED, 2601 HIntConstant* y ATTRIBUTE_UNUSED) const { 2602 VLOG(compiler) << DebugName() << " is not defined for the (long, int) case."; 2603 return nullptr; 2604 } 2605 virtual HConstant* Evaluate(HNullConstant* x ATTRIBUTE_UNUSED, 2606 HNullConstant* y ATTRIBUTE_UNUSED) const { 2607 VLOG(compiler) << DebugName() << " is not defined for the (null, null) case."; 2608 return nullptr; 2609 } 2610 2611 // Returns an input that can legally be used as the right input and is 2612 // constant, or null. 2613 HConstant* GetConstantRight() const; 2614 2615 // If `GetConstantRight()` returns one of the input, this returns the other 2616 // one. Otherwise it returns null. 2617 HInstruction* GetLeastConstantLeft() const; 2618 2619 DECLARE_INSTRUCTION(BinaryOperation); 2620 2621 private: 2622 DISALLOW_COPY_AND_ASSIGN(HBinaryOperation); 2623}; 2624 2625// The comparison bias applies for floating point operations and indicates how NaN 2626// comparisons are treated: 2627enum class ComparisonBias { 2628 kNoBias, // bias is not applicable (i.e. for long operation) 2629 kGtBias, // return 1 for NaN comparisons 2630 kLtBias, // return -1 for NaN comparisons 2631}; 2632 2633class HCondition : public HBinaryOperation { 2634 public: 2635 HCondition(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2636 : HBinaryOperation(Primitive::kPrimBoolean, first, second, SideEffects::None(), dex_pc), 2637 needs_materialization_(true), 2638 bias_(ComparisonBias::kNoBias) {} 2639 2640 bool NeedsMaterialization() const { return needs_materialization_; } 2641 void ClearNeedsMaterialization() { needs_materialization_ = false; } 2642 2643 // For code generation purposes, returns whether this instruction is just before 2644 // `instruction`, and disregard moves in between. 2645 bool IsBeforeWhenDisregardMoves(HInstruction* instruction) const; 2646 2647 DECLARE_INSTRUCTION(Condition); 2648 2649 virtual IfCondition GetCondition() const = 0; 2650 2651 virtual IfCondition GetOppositeCondition() const = 0; 2652 2653 bool IsGtBias() const { return bias_ == ComparisonBias::kGtBias; } 2654 2655 void SetBias(ComparisonBias bias) { bias_ = bias; } 2656 2657 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2658 return bias_ == other->AsCondition()->bias_; 2659 } 2660 2661 bool IsFPConditionTrueIfNaN() const { 2662 DCHECK(Primitive::IsFloatingPointType(InputAt(0)->GetType())); 2663 IfCondition if_cond = GetCondition(); 2664 return IsGtBias() ? ((if_cond == kCondGT) || (if_cond == kCondGE)) : (if_cond == kCondNE); 2665 } 2666 2667 bool IsFPConditionFalseIfNaN() const { 2668 DCHECK(Primitive::IsFloatingPointType(InputAt(0)->GetType())); 2669 IfCondition if_cond = GetCondition(); 2670 return IsGtBias() ? ((if_cond == kCondLT) || (if_cond == kCondLE)) : (if_cond == kCondEQ); 2671 } 2672 2673 private: 2674 // For register allocation purposes, returns whether this instruction needs to be 2675 // materialized (that is, not just be in the processor flags). 2676 bool needs_materialization_; 2677 2678 // Needed if we merge a HCompare into a HCondition. 2679 ComparisonBias bias_; 2680 2681 DISALLOW_COPY_AND_ASSIGN(HCondition); 2682}; 2683 2684// Instruction to check if two inputs are equal to each other. 2685class HEqual : public HCondition { 2686 public: 2687 HEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2688 : HCondition(first, second, dex_pc) {} 2689 2690 bool IsCommutative() const OVERRIDE { return true; } 2691 2692 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2693 return GetBlock()->GetGraph()->GetIntConstant( 2694 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2695 } 2696 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2697 return GetBlock()->GetGraph()->GetIntConstant( 2698 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2699 } 2700 HConstant* Evaluate(HNullConstant* x ATTRIBUTE_UNUSED, 2701 HNullConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 2702 return GetBlock()->GetGraph()->GetIntConstant(1); 2703 } 2704 2705 DECLARE_INSTRUCTION(Equal); 2706 2707 IfCondition GetCondition() const OVERRIDE { 2708 return kCondEQ; 2709 } 2710 2711 IfCondition GetOppositeCondition() const OVERRIDE { 2712 return kCondNE; 2713 } 2714 2715 private: 2716 template <typename T> bool Compute(T x, T y) const { return x == y; } 2717 2718 DISALLOW_COPY_AND_ASSIGN(HEqual); 2719}; 2720 2721class HNotEqual : public HCondition { 2722 public: 2723 HNotEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2724 : HCondition(first, second, dex_pc) {} 2725 2726 bool IsCommutative() const OVERRIDE { return true; } 2727 2728 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2729 return GetBlock()->GetGraph()->GetIntConstant( 2730 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2731 } 2732 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2733 return GetBlock()->GetGraph()->GetIntConstant( 2734 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2735 } 2736 HConstant* Evaluate(HNullConstant* x ATTRIBUTE_UNUSED, 2737 HNullConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 2738 return GetBlock()->GetGraph()->GetIntConstant(0); 2739 } 2740 2741 DECLARE_INSTRUCTION(NotEqual); 2742 2743 IfCondition GetCondition() const OVERRIDE { 2744 return kCondNE; 2745 } 2746 2747 IfCondition GetOppositeCondition() const OVERRIDE { 2748 return kCondEQ; 2749 } 2750 2751 private: 2752 template <typename T> bool Compute(T x, T y) const { return x != y; } 2753 2754 DISALLOW_COPY_AND_ASSIGN(HNotEqual); 2755}; 2756 2757class HLessThan : public HCondition { 2758 public: 2759 HLessThan(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2760 : HCondition(first, second, dex_pc) {} 2761 2762 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2763 return GetBlock()->GetGraph()->GetIntConstant( 2764 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2765 } 2766 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2767 return GetBlock()->GetGraph()->GetIntConstant( 2768 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2769 } 2770 2771 DECLARE_INSTRUCTION(LessThan); 2772 2773 IfCondition GetCondition() const OVERRIDE { 2774 return kCondLT; 2775 } 2776 2777 IfCondition GetOppositeCondition() const OVERRIDE { 2778 return kCondGE; 2779 } 2780 2781 private: 2782 template <typename T> bool Compute(T x, T y) const { return x < y; } 2783 2784 DISALLOW_COPY_AND_ASSIGN(HLessThan); 2785}; 2786 2787class HLessThanOrEqual : public HCondition { 2788 public: 2789 HLessThanOrEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2790 : HCondition(first, second, dex_pc) {} 2791 2792 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2793 return GetBlock()->GetGraph()->GetIntConstant( 2794 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2795 } 2796 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2797 return GetBlock()->GetGraph()->GetIntConstant( 2798 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2799 } 2800 2801 DECLARE_INSTRUCTION(LessThanOrEqual); 2802 2803 IfCondition GetCondition() const OVERRIDE { 2804 return kCondLE; 2805 } 2806 2807 IfCondition GetOppositeCondition() const OVERRIDE { 2808 return kCondGT; 2809 } 2810 2811 private: 2812 template <typename T> bool Compute(T x, T y) const { return x <= y; } 2813 2814 DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual); 2815}; 2816 2817class HGreaterThan : public HCondition { 2818 public: 2819 HGreaterThan(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2820 : HCondition(first, second, dex_pc) {} 2821 2822 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2823 return GetBlock()->GetGraph()->GetIntConstant( 2824 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2825 } 2826 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2827 return GetBlock()->GetGraph()->GetIntConstant( 2828 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2829 } 2830 2831 DECLARE_INSTRUCTION(GreaterThan); 2832 2833 IfCondition GetCondition() const OVERRIDE { 2834 return kCondGT; 2835 } 2836 2837 IfCondition GetOppositeCondition() const OVERRIDE { 2838 return kCondLE; 2839 } 2840 2841 private: 2842 template <typename T> bool Compute(T x, T y) const { return x > y; } 2843 2844 DISALLOW_COPY_AND_ASSIGN(HGreaterThan); 2845}; 2846 2847class HGreaterThanOrEqual : public HCondition { 2848 public: 2849 HGreaterThanOrEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2850 : HCondition(first, second, dex_pc) {} 2851 2852 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2853 return GetBlock()->GetGraph()->GetIntConstant( 2854 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2855 } 2856 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2857 return GetBlock()->GetGraph()->GetIntConstant( 2858 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2859 } 2860 2861 DECLARE_INSTRUCTION(GreaterThanOrEqual); 2862 2863 IfCondition GetCondition() const OVERRIDE { 2864 return kCondGE; 2865 } 2866 2867 IfCondition GetOppositeCondition() const OVERRIDE { 2868 return kCondLT; 2869 } 2870 2871 private: 2872 template <typename T> bool Compute(T x, T y) const { return x >= y; } 2873 2874 DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual); 2875}; 2876 2877class HBelow : public HCondition { 2878 public: 2879 HBelow(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2880 : HCondition(first, second, dex_pc) {} 2881 2882 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2883 return GetBlock()->GetGraph()->GetIntConstant( 2884 Compute(static_cast<uint32_t>(x->GetValue()), 2885 static_cast<uint32_t>(y->GetValue())), GetDexPc()); 2886 } 2887 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2888 return GetBlock()->GetGraph()->GetIntConstant( 2889 Compute(static_cast<uint64_t>(x->GetValue()), 2890 static_cast<uint64_t>(y->GetValue())), GetDexPc()); 2891 } 2892 2893 DECLARE_INSTRUCTION(Below); 2894 2895 IfCondition GetCondition() const OVERRIDE { 2896 return kCondB; 2897 } 2898 2899 IfCondition GetOppositeCondition() const OVERRIDE { 2900 return kCondAE; 2901 } 2902 2903 private: 2904 template <typename T> bool Compute(T x, T y) const { return x < y; } 2905 2906 DISALLOW_COPY_AND_ASSIGN(HBelow); 2907}; 2908 2909class HBelowOrEqual : public HCondition { 2910 public: 2911 HBelowOrEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2912 : HCondition(first, second, dex_pc) {} 2913 2914 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2915 return GetBlock()->GetGraph()->GetIntConstant( 2916 Compute(static_cast<uint32_t>(x->GetValue()), 2917 static_cast<uint32_t>(y->GetValue())), GetDexPc()); 2918 } 2919 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2920 return GetBlock()->GetGraph()->GetIntConstant( 2921 Compute(static_cast<uint64_t>(x->GetValue()), 2922 static_cast<uint64_t>(y->GetValue())), GetDexPc()); 2923 } 2924 2925 DECLARE_INSTRUCTION(BelowOrEqual); 2926 2927 IfCondition GetCondition() const OVERRIDE { 2928 return kCondBE; 2929 } 2930 2931 IfCondition GetOppositeCondition() const OVERRIDE { 2932 return kCondA; 2933 } 2934 2935 private: 2936 template <typename T> bool Compute(T x, T y) const { return x <= y; } 2937 2938 DISALLOW_COPY_AND_ASSIGN(HBelowOrEqual); 2939}; 2940 2941class HAbove : public HCondition { 2942 public: 2943 HAbove(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2944 : HCondition(first, second, dex_pc) {} 2945 2946 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2947 return GetBlock()->GetGraph()->GetIntConstant( 2948 Compute(static_cast<uint32_t>(x->GetValue()), 2949 static_cast<uint32_t>(y->GetValue())), GetDexPc()); 2950 } 2951 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2952 return GetBlock()->GetGraph()->GetIntConstant( 2953 Compute(static_cast<uint64_t>(x->GetValue()), 2954 static_cast<uint64_t>(y->GetValue())), GetDexPc()); 2955 } 2956 2957 DECLARE_INSTRUCTION(Above); 2958 2959 IfCondition GetCondition() const OVERRIDE { 2960 return kCondA; 2961 } 2962 2963 IfCondition GetOppositeCondition() const OVERRIDE { 2964 return kCondBE; 2965 } 2966 2967 private: 2968 template <typename T> bool Compute(T x, T y) const { return x > y; } 2969 2970 DISALLOW_COPY_AND_ASSIGN(HAbove); 2971}; 2972 2973class HAboveOrEqual : public HCondition { 2974 public: 2975 HAboveOrEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2976 : HCondition(first, second, dex_pc) {} 2977 2978 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2979 return GetBlock()->GetGraph()->GetIntConstant( 2980 Compute(static_cast<uint32_t>(x->GetValue()), 2981 static_cast<uint32_t>(y->GetValue())), GetDexPc()); 2982 } 2983 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2984 return GetBlock()->GetGraph()->GetIntConstant( 2985 Compute(static_cast<uint64_t>(x->GetValue()), 2986 static_cast<uint64_t>(y->GetValue())), GetDexPc()); 2987 } 2988 2989 DECLARE_INSTRUCTION(AboveOrEqual); 2990 2991 IfCondition GetCondition() const OVERRIDE { 2992 return kCondAE; 2993 } 2994 2995 IfCondition GetOppositeCondition() const OVERRIDE { 2996 return kCondB; 2997 } 2998 2999 private: 3000 template <typename T> bool Compute(T x, T y) const { return x >= y; } 3001 3002 DISALLOW_COPY_AND_ASSIGN(HAboveOrEqual); 3003}; 3004 3005// Instruction to check how two inputs compare to each other. 3006// Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1. 3007class HCompare : public HBinaryOperation { 3008 public: 3009 HCompare(Primitive::Type type, 3010 HInstruction* first, 3011 HInstruction* second, 3012 ComparisonBias bias, 3013 uint32_t dex_pc) 3014 : HBinaryOperation(Primitive::kPrimInt, 3015 first, 3016 second, 3017 SideEffectsForArchRuntimeCalls(type), 3018 dex_pc), 3019 bias_(bias) { 3020 DCHECK_EQ(type, first->GetType()); 3021 DCHECK_EQ(type, second->GetType()); 3022 } 3023 3024 template <typename T> 3025 int32_t Compute(T x, T y) const { return x == y ? 0 : x > y ? 1 : -1; } 3026 3027 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3028 return GetBlock()->GetGraph()->GetIntConstant( 3029 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3030 } 3031 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3032 return GetBlock()->GetGraph()->GetIntConstant( 3033 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3034 } 3035 3036 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3037 return bias_ == other->AsCompare()->bias_; 3038 } 3039 3040 ComparisonBias GetBias() const { return bias_; } 3041 3042 bool IsGtBias() { return bias_ == ComparisonBias::kGtBias; } 3043 3044 3045 static SideEffects SideEffectsForArchRuntimeCalls(Primitive::Type type) { 3046 // MIPS64 uses a runtime call for FP comparisons. 3047 return Primitive::IsFloatingPointType(type) ? SideEffects::CanTriggerGC() : SideEffects::None(); 3048 } 3049 3050 DECLARE_INSTRUCTION(Compare); 3051 3052 private: 3053 const ComparisonBias bias_; 3054 3055 DISALLOW_COPY_AND_ASSIGN(HCompare); 3056}; 3057 3058// A local in the graph. Corresponds to a Dex register. 3059class HLocal : public HTemplateInstruction<0> { 3060 public: 3061 explicit HLocal(uint16_t reg_number) 3062 : HTemplateInstruction(SideEffects::None(), kNoDexPc), reg_number_(reg_number) {} 3063 3064 DECLARE_INSTRUCTION(Local); 3065 3066 uint16_t GetRegNumber() const { return reg_number_; } 3067 3068 private: 3069 // The Dex register number. 3070 const uint16_t reg_number_; 3071 3072 DISALLOW_COPY_AND_ASSIGN(HLocal); 3073}; 3074 3075// Load a given local. The local is an input of this instruction. 3076class HLoadLocal : public HExpression<1> { 3077 public: 3078 HLoadLocal(HLocal* local, Primitive::Type type, uint32_t dex_pc = kNoDexPc) 3079 : HExpression(type, SideEffects::None(), dex_pc) { 3080 SetRawInputAt(0, local); 3081 } 3082 3083 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 3084 3085 DECLARE_INSTRUCTION(LoadLocal); 3086 3087 private: 3088 DISALLOW_COPY_AND_ASSIGN(HLoadLocal); 3089}; 3090 3091// Store a value in a given local. This instruction has two inputs: the value 3092// and the local. 3093class HStoreLocal : public HTemplateInstruction<2> { 3094 public: 3095 HStoreLocal(HLocal* local, HInstruction* value, uint32_t dex_pc = kNoDexPc) 3096 : HTemplateInstruction(SideEffects::None(), dex_pc) { 3097 SetRawInputAt(0, local); 3098 SetRawInputAt(1, value); 3099 } 3100 3101 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 3102 3103 DECLARE_INSTRUCTION(StoreLocal); 3104 3105 private: 3106 DISALLOW_COPY_AND_ASSIGN(HStoreLocal); 3107}; 3108 3109class HFloatConstant : public HConstant { 3110 public: 3111 float GetValue() const { return value_; } 3112 3113 uint64_t GetValueAsUint64() const OVERRIDE { 3114 return static_cast<uint64_t>(bit_cast<uint32_t, float>(value_)); 3115 } 3116 3117 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3118 DCHECK(other->IsFloatConstant()); 3119 return other->AsFloatConstant()->GetValueAsUint64() == GetValueAsUint64(); 3120 } 3121 3122 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 3123 3124 bool IsMinusOne() const OVERRIDE { 3125 return bit_cast<uint32_t, float>(value_) == bit_cast<uint32_t, float>((-1.0f)); 3126 } 3127 bool IsZero() const OVERRIDE { 3128 return value_ == 0.0f; 3129 } 3130 bool IsOne() const OVERRIDE { 3131 return bit_cast<uint32_t, float>(value_) == bit_cast<uint32_t, float>(1.0f); 3132 } 3133 bool IsNaN() const { 3134 return std::isnan(value_); 3135 } 3136 3137 DECLARE_INSTRUCTION(FloatConstant); 3138 3139 private: 3140 explicit HFloatConstant(float value, uint32_t dex_pc = kNoDexPc) 3141 : HConstant(Primitive::kPrimFloat, dex_pc), value_(value) {} 3142 explicit HFloatConstant(int32_t value, uint32_t dex_pc = kNoDexPc) 3143 : HConstant(Primitive::kPrimFloat, dex_pc), value_(bit_cast<float, int32_t>(value)) {} 3144 3145 const float value_; 3146 3147 // Only the SsaBuilder and HGraph can create floating-point constants. 3148 friend class SsaBuilder; 3149 friend class HGraph; 3150 DISALLOW_COPY_AND_ASSIGN(HFloatConstant); 3151}; 3152 3153class HDoubleConstant : public HConstant { 3154 public: 3155 double GetValue() const { return value_; } 3156 3157 uint64_t GetValueAsUint64() const OVERRIDE { return bit_cast<uint64_t, double>(value_); } 3158 3159 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3160 DCHECK(other->IsDoubleConstant()); 3161 return other->AsDoubleConstant()->GetValueAsUint64() == GetValueAsUint64(); 3162 } 3163 3164 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 3165 3166 bool IsMinusOne() const OVERRIDE { 3167 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>((-1.0)); 3168 } 3169 bool IsZero() const OVERRIDE { 3170 return value_ == 0.0; 3171 } 3172 bool IsOne() const OVERRIDE { 3173 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>(1.0); 3174 } 3175 bool IsNaN() const { 3176 return std::isnan(value_); 3177 } 3178 3179 DECLARE_INSTRUCTION(DoubleConstant); 3180 3181 private: 3182 explicit HDoubleConstant(double value, uint32_t dex_pc = kNoDexPc) 3183 : HConstant(Primitive::kPrimDouble, dex_pc), value_(value) {} 3184 explicit HDoubleConstant(int64_t value, uint32_t dex_pc = kNoDexPc) 3185 : HConstant(Primitive::kPrimDouble, dex_pc), value_(bit_cast<double, int64_t>(value)) {} 3186 3187 const double value_; 3188 3189 // Only the SsaBuilder and HGraph can create floating-point constants. 3190 friend class SsaBuilder; 3191 friend class HGraph; 3192 DISALLOW_COPY_AND_ASSIGN(HDoubleConstant); 3193}; 3194 3195enum class Intrinsics { 3196#define OPTIMIZING_INTRINSICS(Name, IsStatic, NeedsEnvironmentOrCache) k ## Name, 3197#include "intrinsics_list.h" 3198 kNone, 3199 INTRINSICS_LIST(OPTIMIZING_INTRINSICS) 3200#undef INTRINSICS_LIST 3201#undef OPTIMIZING_INTRINSICS 3202}; 3203std::ostream& operator<<(std::ostream& os, const Intrinsics& intrinsic); 3204 3205enum IntrinsicNeedsEnvironmentOrCache { 3206 kNoEnvironmentOrCache, // Intrinsic does not require an environment or dex cache. 3207 kNeedsEnvironmentOrCache // Intrinsic requires an environment or requires a dex cache. 3208}; 3209 3210class HInvoke : public HInstruction { 3211 public: 3212 size_t InputCount() const OVERRIDE { return inputs_.size(); } 3213 3214 bool NeedsEnvironment() const OVERRIDE; 3215 3216 void SetArgumentAt(size_t index, HInstruction* argument) { 3217 SetRawInputAt(index, argument); 3218 } 3219 3220 // Return the number of arguments. This number can be lower than 3221 // the number of inputs returned by InputCount(), as some invoke 3222 // instructions (e.g. HInvokeStaticOrDirect) can have non-argument 3223 // inputs at the end of their list of inputs. 3224 uint32_t GetNumberOfArguments() const { return number_of_arguments_; } 3225 3226 Primitive::Type GetType() const OVERRIDE { return return_type_; } 3227 3228 3229 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 3230 const DexFile& GetDexFile() const { return GetEnvironment()->GetDexFile(); } 3231 3232 InvokeType GetOriginalInvokeType() const { return original_invoke_type_; } 3233 3234 Intrinsics GetIntrinsic() const { 3235 return intrinsic_; 3236 } 3237 3238 void SetIntrinsic(Intrinsics intrinsic, IntrinsicNeedsEnvironmentOrCache needs_env_or_cache); 3239 3240 bool IsFromInlinedInvoke() const { 3241 return GetEnvironment()->GetParent() != nullptr; 3242 } 3243 3244 bool CanThrow() const OVERRIDE { return true; } 3245 3246 uint32_t* GetIntrinsicOptimizations() { 3247 return &intrinsic_optimizations_; 3248 } 3249 3250 const uint32_t* GetIntrinsicOptimizations() const { 3251 return &intrinsic_optimizations_; 3252 } 3253 3254 bool IsIntrinsic() const { return intrinsic_ != Intrinsics::kNone; } 3255 3256 DECLARE_INSTRUCTION(Invoke); 3257 3258 protected: 3259 HInvoke(ArenaAllocator* arena, 3260 uint32_t number_of_arguments, 3261 uint32_t number_of_other_inputs, 3262 Primitive::Type return_type, 3263 uint32_t dex_pc, 3264 uint32_t dex_method_index, 3265 InvokeType original_invoke_type) 3266 : HInstruction( 3267 SideEffects::AllExceptGCDependency(), dex_pc), // Assume write/read on all fields/arrays. 3268 number_of_arguments_(number_of_arguments), 3269 inputs_(number_of_arguments + number_of_other_inputs, 3270 arena->Adapter(kArenaAllocInvokeInputs)), 3271 return_type_(return_type), 3272 dex_method_index_(dex_method_index), 3273 original_invoke_type_(original_invoke_type), 3274 intrinsic_(Intrinsics::kNone), 3275 intrinsic_optimizations_(0) { 3276 } 3277 3278 const HUserRecord<HInstruction*> InputRecordAt(size_t index) const OVERRIDE { 3279 return inputs_[index]; 3280 } 3281 3282 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE { 3283 inputs_[index] = input; 3284 } 3285 3286 uint32_t number_of_arguments_; 3287 ArenaVector<HUserRecord<HInstruction*>> inputs_; 3288 const Primitive::Type return_type_; 3289 const uint32_t dex_method_index_; 3290 const InvokeType original_invoke_type_; 3291 Intrinsics intrinsic_; 3292 3293 // A magic word holding optimizations for intrinsics. See intrinsics.h. 3294 uint32_t intrinsic_optimizations_; 3295 3296 private: 3297 DISALLOW_COPY_AND_ASSIGN(HInvoke); 3298}; 3299 3300class HInvokeUnresolved : public HInvoke { 3301 public: 3302 HInvokeUnresolved(ArenaAllocator* arena, 3303 uint32_t number_of_arguments, 3304 Primitive::Type return_type, 3305 uint32_t dex_pc, 3306 uint32_t dex_method_index, 3307 InvokeType invoke_type) 3308 : HInvoke(arena, 3309 number_of_arguments, 3310 0u /* number_of_other_inputs */, 3311 return_type, 3312 dex_pc, 3313 dex_method_index, 3314 invoke_type) { 3315 } 3316 3317 DECLARE_INSTRUCTION(InvokeUnresolved); 3318 3319 private: 3320 DISALLOW_COPY_AND_ASSIGN(HInvokeUnresolved); 3321}; 3322 3323class HInvokeStaticOrDirect : public HInvoke { 3324 public: 3325 // Requirements of this method call regarding the class 3326 // initialization (clinit) check of its declaring class. 3327 enum class ClinitCheckRequirement { 3328 kNone, // Class already initialized. 3329 kExplicit, // Static call having explicit clinit check as last input. 3330 kImplicit, // Static call implicitly requiring a clinit check. 3331 }; 3332 3333 // Determines how to load the target ArtMethod*. 3334 enum class MethodLoadKind { 3335 // Use a String init ArtMethod* loaded from Thread entrypoints. 3336 kStringInit, 3337 3338 // Use the method's own ArtMethod* loaded by the register allocator. 3339 kRecursive, 3340 3341 // Use ArtMethod* at a known address, embed the direct address in the code. 3342 // Used for app->boot calls with non-relocatable image and for JIT-compiled calls. 3343 kDirectAddress, 3344 3345 // Use ArtMethod* at an address that will be known at link time, embed the direct 3346 // address in the code. If the image is relocatable, emit .patch_oat entry. 3347 // Used for app->boot calls with relocatable image and boot->boot calls, whether 3348 // the image relocatable or not. 3349 kDirectAddressWithFixup, 3350 3351 // Load from resoved methods array in the dex cache using a PC-relative load. 3352 // Used when we need to use the dex cache, for example for invoke-static that 3353 // may cause class initialization (the entry may point to a resolution method), 3354 // and we know that we can access the dex cache arrays using a PC-relative load. 3355 kDexCachePcRelative, 3356 3357 // Use ArtMethod* from the resolved methods of the compiled method's own ArtMethod*. 3358 // Used for JIT when we need to use the dex cache. This is also the last-resort-kind 3359 // used when other kinds are unavailable (say, dex cache arrays are not PC-relative) 3360 // or unimplemented or impractical (i.e. slow) on a particular architecture. 3361 kDexCacheViaMethod, 3362 }; 3363 3364 // Determines the location of the code pointer. 3365 enum class CodePtrLocation { 3366 // Recursive call, use local PC-relative call instruction. 3367 kCallSelf, 3368 3369 // Use PC-relative call instruction patched at link time. 3370 // Used for calls within an oat file, boot->boot or app->app. 3371 kCallPCRelative, 3372 3373 // Call to a known target address, embed the direct address in code. 3374 // Used for app->boot call with non-relocatable image and for JIT-compiled calls. 3375 kCallDirect, 3376 3377 // Call to a target address that will be known at link time, embed the direct 3378 // address in code. If the image is relocatable, emit .patch_oat entry. 3379 // Used for app->boot calls with relocatable image and boot->boot calls, whether 3380 // the image relocatable or not. 3381 kCallDirectWithFixup, 3382 3383 // Use code pointer from the ArtMethod*. 3384 // Used when we don't know the target code. This is also the last-resort-kind used when 3385 // other kinds are unimplemented or impractical (i.e. slow) on a particular architecture. 3386 kCallArtMethod, 3387 }; 3388 3389 struct DispatchInfo { 3390 MethodLoadKind method_load_kind; 3391 CodePtrLocation code_ptr_location; 3392 // The method load data holds 3393 // - thread entrypoint offset for kStringInit method if this is a string init invoke. 3394 // Note that there are multiple string init methods, each having its own offset. 3395 // - the method address for kDirectAddress 3396 // - the dex cache arrays offset for kDexCachePcRel. 3397 uint64_t method_load_data; 3398 uint64_t direct_code_ptr; 3399 }; 3400 3401 HInvokeStaticOrDirect(ArenaAllocator* arena, 3402 uint32_t number_of_arguments, 3403 Primitive::Type return_type, 3404 uint32_t dex_pc, 3405 uint32_t method_index, 3406 MethodReference target_method, 3407 DispatchInfo dispatch_info, 3408 InvokeType original_invoke_type, 3409 InvokeType invoke_type, 3410 ClinitCheckRequirement clinit_check_requirement) 3411 : HInvoke(arena, 3412 number_of_arguments, 3413 // There is potentially one extra argument for the HCurrentMethod node, and 3414 // potentially one other if the clinit check is explicit, and potentially 3415 // one other if the method is a string factory. 3416 (NeedsCurrentMethodInput(dispatch_info.method_load_kind) ? 1u : 0u) + 3417 (clinit_check_requirement == ClinitCheckRequirement::kExplicit ? 1u : 0u) + 3418 (dispatch_info.method_load_kind == MethodLoadKind::kStringInit ? 1u : 0u), 3419 return_type, 3420 dex_pc, 3421 method_index, 3422 original_invoke_type), 3423 invoke_type_(invoke_type), 3424 clinit_check_requirement_(clinit_check_requirement), 3425 target_method_(target_method), 3426 dispatch_info_(dispatch_info) { } 3427 3428 void SetDispatchInfo(const DispatchInfo& dispatch_info) { 3429 bool had_current_method_input = HasCurrentMethodInput(); 3430 bool needs_current_method_input = NeedsCurrentMethodInput(dispatch_info.method_load_kind); 3431 3432 // Using the current method is the default and once we find a better 3433 // method load kind, we should not go back to using the current method. 3434 DCHECK(had_current_method_input || !needs_current_method_input); 3435 3436 if (had_current_method_input && !needs_current_method_input) { 3437 DCHECK_EQ(InputAt(GetCurrentMethodInputIndex()), GetBlock()->GetGraph()->GetCurrentMethod()); 3438 RemoveInputAt(GetCurrentMethodInputIndex()); 3439 } 3440 dispatch_info_ = dispatch_info; 3441 } 3442 3443 void InsertInputAt(size_t index, HInstruction* input); 3444 void RemoveInputAt(size_t index); 3445 3446 bool CanDoImplicitNullCheckOn(HInstruction* obj ATTRIBUTE_UNUSED) const OVERRIDE { 3447 // We access the method via the dex cache so we can't do an implicit null check. 3448 // TODO: for intrinsics we can generate implicit null checks. 3449 return false; 3450 } 3451 3452 bool CanBeNull() const OVERRIDE { 3453 return return_type_ == Primitive::kPrimNot && !IsStringInit(); 3454 } 3455 3456 InvokeType GetInvokeType() const { return invoke_type_; } 3457 MethodLoadKind GetMethodLoadKind() const { return dispatch_info_.method_load_kind; } 3458 CodePtrLocation GetCodePtrLocation() const { return dispatch_info_.code_ptr_location; } 3459 bool IsRecursive() const { return GetMethodLoadKind() == MethodLoadKind::kRecursive; } 3460 bool NeedsDexCacheOfDeclaringClass() const OVERRIDE; 3461 bool IsStringInit() const { return GetMethodLoadKind() == MethodLoadKind::kStringInit; } 3462 uint32_t GetCurrentMethodInputIndex() const { return GetNumberOfArguments(); } 3463 bool HasMethodAddress() const { return GetMethodLoadKind() == MethodLoadKind::kDirectAddress; } 3464 bool HasPcRelativeDexCache() const { 3465 return GetMethodLoadKind() == MethodLoadKind::kDexCachePcRelative; 3466 } 3467 bool HasCurrentMethodInput() const { 3468 // This function can be called only after the invoke has been fully initialized by the builder. 3469 if (NeedsCurrentMethodInput(GetMethodLoadKind())) { 3470 DCHECK(InputAt(GetCurrentMethodInputIndex())->IsCurrentMethod()); 3471 return true; 3472 } else { 3473 DCHECK(InputCount() == GetCurrentMethodInputIndex() || 3474 !InputAt(GetCurrentMethodInputIndex())->IsCurrentMethod()); 3475 return false; 3476 } 3477 } 3478 bool HasDirectCodePtr() const { return GetCodePtrLocation() == CodePtrLocation::kCallDirect; } 3479 MethodReference GetTargetMethod() const { return target_method_; } 3480 3481 int32_t GetStringInitOffset() const { 3482 DCHECK(IsStringInit()); 3483 return dispatch_info_.method_load_data; 3484 } 3485 3486 uint64_t GetMethodAddress() const { 3487 DCHECK(HasMethodAddress()); 3488 return dispatch_info_.method_load_data; 3489 } 3490 3491 uint32_t GetDexCacheArrayOffset() const { 3492 DCHECK(HasPcRelativeDexCache()); 3493 return dispatch_info_.method_load_data; 3494 } 3495 3496 uint64_t GetDirectCodePtr() const { 3497 DCHECK(HasDirectCodePtr()); 3498 return dispatch_info_.direct_code_ptr; 3499 } 3500 3501 ClinitCheckRequirement GetClinitCheckRequirement() const { return clinit_check_requirement_; } 3502 3503 // Is this instruction a call to a static method? 3504 bool IsStatic() const { 3505 return GetInvokeType() == kStatic; 3506 } 3507 3508 // Remove the art::HLoadClass instruction set as last input by 3509 // art::PrepareForRegisterAllocation::VisitClinitCheck in lieu of 3510 // the initial art::HClinitCheck instruction (only relevant for 3511 // static calls with explicit clinit check). 3512 void RemoveLoadClassAsLastInput() { 3513 DCHECK(IsStaticWithExplicitClinitCheck()); 3514 size_t last_input_index = InputCount() - 1; 3515 HInstruction* last_input = InputAt(last_input_index); 3516 DCHECK(last_input != nullptr); 3517 DCHECK(last_input->IsLoadClass()) << last_input->DebugName(); 3518 RemoveAsUserOfInput(last_input_index); 3519 inputs_.pop_back(); 3520 clinit_check_requirement_ = ClinitCheckRequirement::kImplicit; 3521 DCHECK(IsStaticWithImplicitClinitCheck()); 3522 } 3523 3524 bool IsStringFactoryFor(HFakeString* str) const { 3525 if (!IsStringInit()) return false; 3526 DCHECK(!HasCurrentMethodInput()); 3527 if (InputCount() == (number_of_arguments_)) return false; 3528 return InputAt(InputCount() - 1)->AsFakeString() == str; 3529 } 3530 3531 void RemoveFakeStringArgumentAsLastInput() { 3532 DCHECK(IsStringInit()); 3533 size_t last_input_index = InputCount() - 1; 3534 HInstruction* last_input = InputAt(last_input_index); 3535 DCHECK(last_input != nullptr); 3536 DCHECK(last_input->IsFakeString()) << last_input->DebugName(); 3537 RemoveAsUserOfInput(last_input_index); 3538 inputs_.pop_back(); 3539 } 3540 3541 // Is this a call to a static method whose declaring class has an 3542 // explicit intialization check in the graph? 3543 bool IsStaticWithExplicitClinitCheck() const { 3544 return IsStatic() && (clinit_check_requirement_ == ClinitCheckRequirement::kExplicit); 3545 } 3546 3547 // Is this a call to a static method whose declaring class has an 3548 // implicit intialization check requirement? 3549 bool IsStaticWithImplicitClinitCheck() const { 3550 return IsStatic() && (clinit_check_requirement_ == ClinitCheckRequirement::kImplicit); 3551 } 3552 3553 // Does this method load kind need the current method as an input? 3554 static bool NeedsCurrentMethodInput(MethodLoadKind kind) { 3555 return kind == MethodLoadKind::kRecursive || kind == MethodLoadKind::kDexCacheViaMethod; 3556 } 3557 3558 DECLARE_INSTRUCTION(InvokeStaticOrDirect); 3559 3560 protected: 3561 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { 3562 const HUserRecord<HInstruction*> input_record = HInvoke::InputRecordAt(i); 3563 if (kIsDebugBuild && IsStaticWithExplicitClinitCheck() && (i == InputCount() - 1)) { 3564 HInstruction* input = input_record.GetInstruction(); 3565 // `input` is the last input of a static invoke marked as having 3566 // an explicit clinit check. It must either be: 3567 // - an art::HClinitCheck instruction, set by art::HGraphBuilder; or 3568 // - an art::HLoadClass instruction, set by art::PrepareForRegisterAllocation. 3569 DCHECK(input != nullptr); 3570 DCHECK(input->IsClinitCheck() || input->IsLoadClass()) << input->DebugName(); 3571 } 3572 return input_record; 3573 } 3574 3575 private: 3576 const InvokeType invoke_type_; 3577 ClinitCheckRequirement clinit_check_requirement_; 3578 // The target method may refer to different dex file or method index than the original 3579 // invoke. This happens for sharpened calls and for calls where a method was redeclared 3580 // in derived class to increase visibility. 3581 MethodReference target_method_; 3582 DispatchInfo dispatch_info_; 3583 3584 DISALLOW_COPY_AND_ASSIGN(HInvokeStaticOrDirect); 3585}; 3586 3587class HInvokeVirtual : public HInvoke { 3588 public: 3589 HInvokeVirtual(ArenaAllocator* arena, 3590 uint32_t number_of_arguments, 3591 Primitive::Type return_type, 3592 uint32_t dex_pc, 3593 uint32_t dex_method_index, 3594 uint32_t vtable_index) 3595 : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index, kVirtual), 3596 vtable_index_(vtable_index) {} 3597 3598 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3599 // TODO: Add implicit null checks in intrinsics. 3600 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 3601 } 3602 3603 uint32_t GetVTableIndex() const { return vtable_index_; } 3604 3605 DECLARE_INSTRUCTION(InvokeVirtual); 3606 3607 private: 3608 const uint32_t vtable_index_; 3609 3610 DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual); 3611}; 3612 3613class HInvokeInterface : public HInvoke { 3614 public: 3615 HInvokeInterface(ArenaAllocator* arena, 3616 uint32_t number_of_arguments, 3617 Primitive::Type return_type, 3618 uint32_t dex_pc, 3619 uint32_t dex_method_index, 3620 uint32_t imt_index) 3621 : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index, kInterface), 3622 imt_index_(imt_index) {} 3623 3624 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3625 // TODO: Add implicit null checks in intrinsics. 3626 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 3627 } 3628 3629 uint32_t GetImtIndex() const { return imt_index_; } 3630 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 3631 3632 DECLARE_INSTRUCTION(InvokeInterface); 3633 3634 private: 3635 const uint32_t imt_index_; 3636 3637 DISALLOW_COPY_AND_ASSIGN(HInvokeInterface); 3638}; 3639 3640class HNewInstance : public HExpression<1> { 3641 public: 3642 HNewInstance(HCurrentMethod* current_method, 3643 uint32_t dex_pc, 3644 uint16_t type_index, 3645 const DexFile& dex_file, 3646 bool can_throw, 3647 bool finalizable, 3648 QuickEntrypointEnum entrypoint) 3649 : HExpression(Primitive::kPrimNot, SideEffects::CanTriggerGC(), dex_pc), 3650 type_index_(type_index), 3651 dex_file_(dex_file), 3652 can_throw_(can_throw), 3653 finalizable_(finalizable), 3654 entrypoint_(entrypoint) { 3655 SetRawInputAt(0, current_method); 3656 } 3657 3658 uint16_t GetTypeIndex() const { return type_index_; } 3659 const DexFile& GetDexFile() const { return dex_file_; } 3660 3661 // Calls runtime so needs an environment. 3662 bool NeedsEnvironment() const OVERRIDE { return true; } 3663 3664 // It may throw when called on type that's not instantiable/accessible. 3665 // It can throw OOME. 3666 // TODO: distinguish between the two cases so we can for example allow allocation elimination. 3667 bool CanThrow() const OVERRIDE { return can_throw_ || true; } 3668 3669 bool IsFinalizable() const { return finalizable_; } 3670 3671 bool CanBeNull() const OVERRIDE { return false; } 3672 3673 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 3674 3675 DECLARE_INSTRUCTION(NewInstance); 3676 3677 private: 3678 const uint16_t type_index_; 3679 const DexFile& dex_file_; 3680 const bool can_throw_; 3681 const bool finalizable_; 3682 const QuickEntrypointEnum entrypoint_; 3683 3684 DISALLOW_COPY_AND_ASSIGN(HNewInstance); 3685}; 3686 3687class HNeg : public HUnaryOperation { 3688 public: 3689 HNeg(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc = kNoDexPc) 3690 : HUnaryOperation(result_type, input, dex_pc) {} 3691 3692 template <typename T> T Compute(T x) const { return -x; } 3693 3694 HConstant* Evaluate(HIntConstant* x) const OVERRIDE { 3695 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue()), GetDexPc()); 3696 } 3697 HConstant* Evaluate(HLongConstant* x) const OVERRIDE { 3698 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue()), GetDexPc()); 3699 } 3700 3701 DECLARE_INSTRUCTION(Neg); 3702 3703 private: 3704 DISALLOW_COPY_AND_ASSIGN(HNeg); 3705}; 3706 3707class HNewArray : public HExpression<2> { 3708 public: 3709 HNewArray(HInstruction* length, 3710 HCurrentMethod* current_method, 3711 uint32_t dex_pc, 3712 uint16_t type_index, 3713 const DexFile& dex_file, 3714 QuickEntrypointEnum entrypoint) 3715 : HExpression(Primitive::kPrimNot, SideEffects::CanTriggerGC(), dex_pc), 3716 type_index_(type_index), 3717 dex_file_(dex_file), 3718 entrypoint_(entrypoint) { 3719 SetRawInputAt(0, length); 3720 SetRawInputAt(1, current_method); 3721 } 3722 3723 uint16_t GetTypeIndex() const { return type_index_; } 3724 const DexFile& GetDexFile() const { return dex_file_; } 3725 3726 // Calls runtime so needs an environment. 3727 bool NeedsEnvironment() const OVERRIDE { return true; } 3728 3729 // May throw NegativeArraySizeException, OutOfMemoryError, etc. 3730 bool CanThrow() const OVERRIDE { return true; } 3731 3732 bool CanBeNull() const OVERRIDE { return false; } 3733 3734 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 3735 3736 DECLARE_INSTRUCTION(NewArray); 3737 3738 private: 3739 const uint16_t type_index_; 3740 const DexFile& dex_file_; 3741 const QuickEntrypointEnum entrypoint_; 3742 3743 DISALLOW_COPY_AND_ASSIGN(HNewArray); 3744}; 3745 3746class HAdd : public HBinaryOperation { 3747 public: 3748 HAdd(Primitive::Type result_type, 3749 HInstruction* left, 3750 HInstruction* right, 3751 uint32_t dex_pc = kNoDexPc) 3752 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 3753 3754 bool IsCommutative() const OVERRIDE { return true; } 3755 3756 template <typename T> T Compute(T x, T y) const { return x + y; } 3757 3758 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3759 return GetBlock()->GetGraph()->GetIntConstant( 3760 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3761 } 3762 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3763 return GetBlock()->GetGraph()->GetLongConstant( 3764 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3765 } 3766 3767 DECLARE_INSTRUCTION(Add); 3768 3769 private: 3770 DISALLOW_COPY_AND_ASSIGN(HAdd); 3771}; 3772 3773class HSub : public HBinaryOperation { 3774 public: 3775 HSub(Primitive::Type result_type, 3776 HInstruction* left, 3777 HInstruction* right, 3778 uint32_t dex_pc = kNoDexPc) 3779 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 3780 3781 template <typename T> T Compute(T x, T y) const { return x - y; } 3782 3783 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3784 return GetBlock()->GetGraph()->GetIntConstant( 3785 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3786 } 3787 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3788 return GetBlock()->GetGraph()->GetLongConstant( 3789 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3790 } 3791 3792 DECLARE_INSTRUCTION(Sub); 3793 3794 private: 3795 DISALLOW_COPY_AND_ASSIGN(HSub); 3796}; 3797 3798class HMul : public HBinaryOperation { 3799 public: 3800 HMul(Primitive::Type result_type, 3801 HInstruction* left, 3802 HInstruction* right, 3803 uint32_t dex_pc = kNoDexPc) 3804 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 3805 3806 bool IsCommutative() const OVERRIDE { return true; } 3807 3808 template <typename T> T Compute(T x, T y) const { return x * y; } 3809 3810 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3811 return GetBlock()->GetGraph()->GetIntConstant( 3812 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3813 } 3814 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3815 return GetBlock()->GetGraph()->GetLongConstant( 3816 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3817 } 3818 3819 DECLARE_INSTRUCTION(Mul); 3820 3821 private: 3822 DISALLOW_COPY_AND_ASSIGN(HMul); 3823}; 3824 3825class HDiv : public HBinaryOperation { 3826 public: 3827 HDiv(Primitive::Type result_type, 3828 HInstruction* left, 3829 HInstruction* right, 3830 uint32_t dex_pc) 3831 : HBinaryOperation(result_type, left, right, SideEffectsForArchRuntimeCalls(), dex_pc) {} 3832 3833 template <typename T> 3834 T Compute(T x, T y) const { 3835 // Our graph structure ensures we never have 0 for `y` during 3836 // constant folding. 3837 DCHECK_NE(y, 0); 3838 // Special case -1 to avoid getting a SIGFPE on x86(_64). 3839 return (y == -1) ? -x : x / y; 3840 } 3841 3842 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3843 return GetBlock()->GetGraph()->GetIntConstant( 3844 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3845 } 3846 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3847 return GetBlock()->GetGraph()->GetLongConstant( 3848 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3849 } 3850 3851 static SideEffects SideEffectsForArchRuntimeCalls() { 3852 // The generated code can use a runtime call. 3853 return SideEffects::CanTriggerGC(); 3854 } 3855 3856 DECLARE_INSTRUCTION(Div); 3857 3858 private: 3859 DISALLOW_COPY_AND_ASSIGN(HDiv); 3860}; 3861 3862class HRem : public HBinaryOperation { 3863 public: 3864 HRem(Primitive::Type result_type, 3865 HInstruction* left, 3866 HInstruction* right, 3867 uint32_t dex_pc) 3868 : HBinaryOperation(result_type, left, right, SideEffectsForArchRuntimeCalls(), dex_pc) {} 3869 3870 template <typename T> 3871 T Compute(T x, T y) const { 3872 // Our graph structure ensures we never have 0 for `y` during 3873 // constant folding. 3874 DCHECK_NE(y, 0); 3875 // Special case -1 to avoid getting a SIGFPE on x86(_64). 3876 return (y == -1) ? 0 : x % y; 3877 } 3878 3879 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3880 return GetBlock()->GetGraph()->GetIntConstant( 3881 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3882 } 3883 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3884 return GetBlock()->GetGraph()->GetLongConstant( 3885 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3886 } 3887 3888 3889 static SideEffects SideEffectsForArchRuntimeCalls() { 3890 return SideEffects::CanTriggerGC(); 3891 } 3892 3893 DECLARE_INSTRUCTION(Rem); 3894 3895 private: 3896 DISALLOW_COPY_AND_ASSIGN(HRem); 3897}; 3898 3899class HDivZeroCheck : public HExpression<1> { 3900 public: 3901 HDivZeroCheck(HInstruction* value, uint32_t dex_pc) 3902 : HExpression(value->GetType(), SideEffects::None(), dex_pc) { 3903 SetRawInputAt(0, value); 3904 } 3905 3906 Primitive::Type GetType() const OVERRIDE { return InputAt(0)->GetType(); } 3907 3908 bool CanBeMoved() const OVERRIDE { return true; } 3909 3910 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 3911 return true; 3912 } 3913 3914 bool NeedsEnvironment() const OVERRIDE { return true; } 3915 bool CanThrow() const OVERRIDE { return true; } 3916 3917 DECLARE_INSTRUCTION(DivZeroCheck); 3918 3919 private: 3920 DISALLOW_COPY_AND_ASSIGN(HDivZeroCheck); 3921}; 3922 3923class HShl : public HBinaryOperation { 3924 public: 3925 HShl(Primitive::Type result_type, 3926 HInstruction* left, 3927 HInstruction* right, 3928 uint32_t dex_pc = kNoDexPc) 3929 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 3930 3931 template <typename T, typename U, typename V> 3932 T Compute(T x, U y, V max_shift_value) const { 3933 static_assert(std::is_same<V, typename std::make_unsigned<T>::type>::value, 3934 "V is not the unsigned integer type corresponding to T"); 3935 return x << (y & max_shift_value); 3936 } 3937 3938 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3939 return GetBlock()->GetGraph()->GetIntConstant( 3940 Compute(x->GetValue(), y->GetValue(), kMaxIntShiftValue), GetDexPc()); 3941 } 3942 // There is no `Evaluate(HIntConstant* x, HLongConstant* y)`, as this 3943 // case is handled as `x << static_cast<int>(y)`. 3944 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 3945 return GetBlock()->GetGraph()->GetLongConstant( 3946 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc()); 3947 } 3948 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3949 return GetBlock()->GetGraph()->GetLongConstant( 3950 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc()); 3951 } 3952 3953 DECLARE_INSTRUCTION(Shl); 3954 3955 private: 3956 DISALLOW_COPY_AND_ASSIGN(HShl); 3957}; 3958 3959class HShr : public HBinaryOperation { 3960 public: 3961 HShr(Primitive::Type result_type, 3962 HInstruction* left, 3963 HInstruction* right, 3964 uint32_t dex_pc = kNoDexPc) 3965 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 3966 3967 template <typename T, typename U, typename V> 3968 T Compute(T x, U y, V max_shift_value) const { 3969 static_assert(std::is_same<V, typename std::make_unsigned<T>::type>::value, 3970 "V is not the unsigned integer type corresponding to T"); 3971 return x >> (y & max_shift_value); 3972 } 3973 3974 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3975 return GetBlock()->GetGraph()->GetIntConstant( 3976 Compute(x->GetValue(), y->GetValue(), kMaxIntShiftValue), GetDexPc()); 3977 } 3978 // There is no `Evaluate(HIntConstant* x, HLongConstant* y)`, as this 3979 // case is handled as `x >> static_cast<int>(y)`. 3980 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 3981 return GetBlock()->GetGraph()->GetLongConstant( 3982 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc()); 3983 } 3984 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3985 return GetBlock()->GetGraph()->GetLongConstant( 3986 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc()); 3987 } 3988 3989 DECLARE_INSTRUCTION(Shr); 3990 3991 private: 3992 DISALLOW_COPY_AND_ASSIGN(HShr); 3993}; 3994 3995class HUShr : public HBinaryOperation { 3996 public: 3997 HUShr(Primitive::Type result_type, 3998 HInstruction* left, 3999 HInstruction* right, 4000 uint32_t dex_pc = kNoDexPc) 4001 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4002 4003 template <typename T, typename U, typename V> 4004 T Compute(T x, U y, V max_shift_value) const { 4005 static_assert(std::is_same<V, typename std::make_unsigned<T>::type>::value, 4006 "V is not the unsigned integer type corresponding to T"); 4007 V ux = static_cast<V>(x); 4008 return static_cast<T>(ux >> (y & max_shift_value)); 4009 } 4010 4011 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4012 return GetBlock()->GetGraph()->GetIntConstant( 4013 Compute(x->GetValue(), y->GetValue(), kMaxIntShiftValue), GetDexPc()); 4014 } 4015 // There is no `Evaluate(HIntConstant* x, HLongConstant* y)`, as this 4016 // case is handled as `x >>> static_cast<int>(y)`. 4017 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 4018 return GetBlock()->GetGraph()->GetLongConstant( 4019 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc()); 4020 } 4021 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4022 return GetBlock()->GetGraph()->GetLongConstant( 4023 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc()); 4024 } 4025 4026 DECLARE_INSTRUCTION(UShr); 4027 4028 private: 4029 DISALLOW_COPY_AND_ASSIGN(HUShr); 4030}; 4031 4032class HAnd : public HBinaryOperation { 4033 public: 4034 HAnd(Primitive::Type result_type, 4035 HInstruction* left, 4036 HInstruction* right, 4037 uint32_t dex_pc = kNoDexPc) 4038 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4039 4040 bool IsCommutative() const OVERRIDE { return true; } 4041 4042 template <typename T, typename U> 4043 auto Compute(T x, U y) const -> decltype(x & y) { return x & y; } 4044 4045 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4046 return GetBlock()->GetGraph()->GetIntConstant( 4047 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4048 } 4049 HConstant* Evaluate(HIntConstant* x, HLongConstant* y) const OVERRIDE { 4050 return GetBlock()->GetGraph()->GetLongConstant( 4051 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4052 } 4053 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 4054 return GetBlock()->GetGraph()->GetLongConstant( 4055 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4056 } 4057 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4058 return GetBlock()->GetGraph()->GetLongConstant( 4059 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4060 } 4061 4062 DECLARE_INSTRUCTION(And); 4063 4064 private: 4065 DISALLOW_COPY_AND_ASSIGN(HAnd); 4066}; 4067 4068class HOr : public HBinaryOperation { 4069 public: 4070 HOr(Primitive::Type result_type, 4071 HInstruction* left, 4072 HInstruction* right, 4073 uint32_t dex_pc = kNoDexPc) 4074 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4075 4076 bool IsCommutative() const OVERRIDE { return true; } 4077 4078 template <typename T, typename U> 4079 auto Compute(T x, U y) const -> decltype(x | y) { return x | y; } 4080 4081 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4082 return GetBlock()->GetGraph()->GetIntConstant( 4083 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4084 } 4085 HConstant* Evaluate(HIntConstant* x, HLongConstant* y) const OVERRIDE { 4086 return GetBlock()->GetGraph()->GetLongConstant( 4087 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4088 } 4089 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 4090 return GetBlock()->GetGraph()->GetLongConstant( 4091 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4092 } 4093 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4094 return GetBlock()->GetGraph()->GetLongConstant( 4095 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4096 } 4097 4098 DECLARE_INSTRUCTION(Or); 4099 4100 private: 4101 DISALLOW_COPY_AND_ASSIGN(HOr); 4102}; 4103 4104class HXor : public HBinaryOperation { 4105 public: 4106 HXor(Primitive::Type result_type, 4107 HInstruction* left, 4108 HInstruction* right, 4109 uint32_t dex_pc = kNoDexPc) 4110 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4111 4112 bool IsCommutative() const OVERRIDE { return true; } 4113 4114 template <typename T, typename U> 4115 auto Compute(T x, U y) const -> decltype(x ^ y) { return x ^ y; } 4116 4117 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4118 return GetBlock()->GetGraph()->GetIntConstant( 4119 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4120 } 4121 HConstant* Evaluate(HIntConstant* x, HLongConstant* y) const OVERRIDE { 4122 return GetBlock()->GetGraph()->GetLongConstant( 4123 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4124 } 4125 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 4126 return GetBlock()->GetGraph()->GetLongConstant( 4127 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4128 } 4129 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4130 return GetBlock()->GetGraph()->GetLongConstant( 4131 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4132 } 4133 4134 DECLARE_INSTRUCTION(Xor); 4135 4136 private: 4137 DISALLOW_COPY_AND_ASSIGN(HXor); 4138}; 4139 4140// The value of a parameter in this method. Its location depends on 4141// the calling convention. 4142class HParameterValue : public HExpression<0> { 4143 public: 4144 HParameterValue(const DexFile& dex_file, 4145 uint16_t type_index, 4146 uint8_t index, 4147 Primitive::Type parameter_type, 4148 bool is_this = false) 4149 : HExpression(parameter_type, SideEffects::None(), kNoDexPc), 4150 dex_file_(dex_file), 4151 type_index_(type_index), 4152 index_(index), 4153 is_this_(is_this), 4154 can_be_null_(!is_this) {} 4155 4156 const DexFile& GetDexFile() const { return dex_file_; } 4157 uint16_t GetTypeIndex() const { return type_index_; } 4158 uint8_t GetIndex() const { return index_; } 4159 bool IsThis() const { return is_this_; } 4160 4161 bool CanBeNull() const OVERRIDE { return can_be_null_; } 4162 void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; } 4163 4164 DECLARE_INSTRUCTION(ParameterValue); 4165 4166 private: 4167 const DexFile& dex_file_; 4168 const uint16_t type_index_; 4169 // The index of this parameter in the parameters list. Must be less 4170 // than HGraph::number_of_in_vregs_. 4171 const uint8_t index_; 4172 4173 // Whether or not the parameter value corresponds to 'this' argument. 4174 const bool is_this_; 4175 4176 bool can_be_null_; 4177 4178 DISALLOW_COPY_AND_ASSIGN(HParameterValue); 4179}; 4180 4181class HNot : public HUnaryOperation { 4182 public: 4183 HNot(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc = kNoDexPc) 4184 : HUnaryOperation(result_type, input, dex_pc) {} 4185 4186 bool CanBeMoved() const OVERRIDE { return true; } 4187 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4188 return true; 4189 } 4190 4191 template <typename T> T Compute(T x) const { return ~x; } 4192 4193 HConstant* Evaluate(HIntConstant* x) const OVERRIDE { 4194 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue()), GetDexPc()); 4195 } 4196 HConstant* Evaluate(HLongConstant* x) const OVERRIDE { 4197 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue()), GetDexPc()); 4198 } 4199 4200 DECLARE_INSTRUCTION(Not); 4201 4202 private: 4203 DISALLOW_COPY_AND_ASSIGN(HNot); 4204}; 4205 4206class HBooleanNot : public HUnaryOperation { 4207 public: 4208 explicit HBooleanNot(HInstruction* input, uint32_t dex_pc = kNoDexPc) 4209 : HUnaryOperation(Primitive::Type::kPrimBoolean, input, dex_pc) {} 4210 4211 bool CanBeMoved() const OVERRIDE { return true; } 4212 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4213 return true; 4214 } 4215 4216 template <typename T> bool Compute(T x) const { 4217 DCHECK(IsUint<1>(x)); 4218 return !x; 4219 } 4220 4221 HConstant* Evaluate(HIntConstant* x) const OVERRIDE { 4222 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue()), GetDexPc()); 4223 } 4224 HConstant* Evaluate(HLongConstant* x ATTRIBUTE_UNUSED) const OVERRIDE { 4225 LOG(FATAL) << DebugName() << " is not defined for long values"; 4226 UNREACHABLE(); 4227 } 4228 4229 DECLARE_INSTRUCTION(BooleanNot); 4230 4231 private: 4232 DISALLOW_COPY_AND_ASSIGN(HBooleanNot); 4233}; 4234 4235class HTypeConversion : public HExpression<1> { 4236 public: 4237 // Instantiate a type conversion of `input` to `result_type`. 4238 HTypeConversion(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc) 4239 : HExpression(result_type, 4240 SideEffectsForArchRuntimeCalls(input->GetType(), result_type), 4241 dex_pc) { 4242 SetRawInputAt(0, input); 4243 DCHECK_NE(input->GetType(), result_type); 4244 } 4245 4246 HInstruction* GetInput() const { return InputAt(0); } 4247 Primitive::Type GetInputType() const { return GetInput()->GetType(); } 4248 Primitive::Type GetResultType() const { return GetType(); } 4249 4250 // Required by the x86, ARM, MIPS and MIPS64 code generators when producing calls 4251 // to the runtime. 4252 4253 bool CanBeMoved() const OVERRIDE { return true; } 4254 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { return true; } 4255 4256 // Try to statically evaluate the conversion and return a HConstant 4257 // containing the result. If the input cannot be converted, return nullptr. 4258 HConstant* TryStaticEvaluation() const; 4259 4260 static SideEffects SideEffectsForArchRuntimeCalls(Primitive::Type input_type, 4261 Primitive::Type result_type) { 4262 // Some architectures may not require the 'GC' side effects, but at this point 4263 // in the compilation process we do not know what architecture we will 4264 // generate code for, so we must be conservative. 4265 if ((Primitive::IsFloatingPointType(input_type) && Primitive::IsIntegralType(result_type)) 4266 || (input_type == Primitive::kPrimLong && Primitive::IsFloatingPointType(result_type))) { 4267 return SideEffects::CanTriggerGC(); 4268 } 4269 return SideEffects::None(); 4270 } 4271 4272 DECLARE_INSTRUCTION(TypeConversion); 4273 4274 private: 4275 DISALLOW_COPY_AND_ASSIGN(HTypeConversion); 4276}; 4277 4278static constexpr uint32_t kNoRegNumber = -1; 4279 4280class HPhi : public HInstruction { 4281 public: 4282 HPhi(ArenaAllocator* arena, 4283 uint32_t reg_number, 4284 size_t number_of_inputs, 4285 Primitive::Type type, 4286 uint32_t dex_pc = kNoDexPc) 4287 : HInstruction(SideEffects::None(), dex_pc), 4288 inputs_(number_of_inputs, arena->Adapter(kArenaAllocPhiInputs)), 4289 reg_number_(reg_number), 4290 type_(type), 4291 is_live_(false), 4292 can_be_null_(true) { 4293 } 4294 4295 // Returns a type equivalent to the given `type`, but that a `HPhi` can hold. 4296 static Primitive::Type ToPhiType(Primitive::Type type) { 4297 switch (type) { 4298 case Primitive::kPrimBoolean: 4299 case Primitive::kPrimByte: 4300 case Primitive::kPrimShort: 4301 case Primitive::kPrimChar: 4302 return Primitive::kPrimInt; 4303 default: 4304 return type; 4305 } 4306 } 4307 4308 bool IsCatchPhi() const { return GetBlock()->IsCatchBlock(); } 4309 4310 size_t InputCount() const OVERRIDE { return inputs_.size(); } 4311 4312 void AddInput(HInstruction* input); 4313 void RemoveInputAt(size_t index); 4314 4315 Primitive::Type GetType() const OVERRIDE { return type_; } 4316 void SetType(Primitive::Type type) { type_ = type; } 4317 4318 bool CanBeNull() const OVERRIDE { return can_be_null_; } 4319 void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; } 4320 4321 uint32_t GetRegNumber() const { return reg_number_; } 4322 4323 void SetDead() { is_live_ = false; } 4324 void SetLive() { is_live_ = true; } 4325 bool IsDead() const { return !is_live_; } 4326 bool IsLive() const { return is_live_; } 4327 4328 bool IsVRegEquivalentOf(HInstruction* other) const { 4329 return other != nullptr 4330 && other->IsPhi() 4331 && other->AsPhi()->GetBlock() == GetBlock() 4332 && other->AsPhi()->GetRegNumber() == GetRegNumber(); 4333 } 4334 4335 // Returns the next equivalent phi (starting from the current one) or null if there is none. 4336 // An equivalent phi is a phi having the same dex register and type. 4337 // It assumes that phis with the same dex register are adjacent. 4338 HPhi* GetNextEquivalentPhiWithSameType() { 4339 HInstruction* next = GetNext(); 4340 while (next != nullptr && next->AsPhi()->GetRegNumber() == reg_number_) { 4341 if (next->GetType() == GetType()) { 4342 return next->AsPhi(); 4343 } 4344 next = next->GetNext(); 4345 } 4346 return nullptr; 4347 } 4348 4349 DECLARE_INSTRUCTION(Phi); 4350 4351 protected: 4352 const HUserRecord<HInstruction*> InputRecordAt(size_t index) const OVERRIDE { 4353 return inputs_[index]; 4354 } 4355 4356 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE { 4357 inputs_[index] = input; 4358 } 4359 4360 private: 4361 ArenaVector<HUserRecord<HInstruction*> > inputs_; 4362 const uint32_t reg_number_; 4363 Primitive::Type type_; 4364 bool is_live_; 4365 bool can_be_null_; 4366 4367 DISALLOW_COPY_AND_ASSIGN(HPhi); 4368}; 4369 4370class HNullCheck : public HExpression<1> { 4371 public: 4372 HNullCheck(HInstruction* value, uint32_t dex_pc) 4373 : HExpression(value->GetType(), SideEffects::None(), dex_pc) { 4374 SetRawInputAt(0, value); 4375 } 4376 4377 bool CanBeMoved() const OVERRIDE { return true; } 4378 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4379 return true; 4380 } 4381 4382 bool NeedsEnvironment() const OVERRIDE { return true; } 4383 4384 bool CanThrow() const OVERRIDE { return true; } 4385 4386 bool CanBeNull() const OVERRIDE { return false; } 4387 4388 4389 DECLARE_INSTRUCTION(NullCheck); 4390 4391 private: 4392 DISALLOW_COPY_AND_ASSIGN(HNullCheck); 4393}; 4394 4395class FieldInfo : public ValueObject { 4396 public: 4397 FieldInfo(MemberOffset field_offset, 4398 Primitive::Type field_type, 4399 bool is_volatile, 4400 uint32_t index, 4401 uint16_t declaring_class_def_index, 4402 const DexFile& dex_file, 4403 Handle<mirror::DexCache> dex_cache) 4404 : field_offset_(field_offset), 4405 field_type_(field_type), 4406 is_volatile_(is_volatile), 4407 index_(index), 4408 declaring_class_def_index_(declaring_class_def_index), 4409 dex_file_(dex_file), 4410 dex_cache_(dex_cache) {} 4411 4412 MemberOffset GetFieldOffset() const { return field_offset_; } 4413 Primitive::Type GetFieldType() const { return field_type_; } 4414 uint32_t GetFieldIndex() const { return index_; } 4415 uint16_t GetDeclaringClassDefIndex() const { return declaring_class_def_index_;} 4416 const DexFile& GetDexFile() const { return dex_file_; } 4417 bool IsVolatile() const { return is_volatile_; } 4418 Handle<mirror::DexCache> GetDexCache() const { return dex_cache_; } 4419 4420 private: 4421 const MemberOffset field_offset_; 4422 const Primitive::Type field_type_; 4423 const bool is_volatile_; 4424 const uint32_t index_; 4425 const uint16_t declaring_class_def_index_; 4426 const DexFile& dex_file_; 4427 const Handle<mirror::DexCache> dex_cache_; 4428}; 4429 4430class HInstanceFieldGet : public HExpression<1> { 4431 public: 4432 HInstanceFieldGet(HInstruction* value, 4433 Primitive::Type field_type, 4434 MemberOffset field_offset, 4435 bool is_volatile, 4436 uint32_t field_idx, 4437 uint16_t declaring_class_def_index, 4438 const DexFile& dex_file, 4439 Handle<mirror::DexCache> dex_cache, 4440 uint32_t dex_pc) 4441 : HExpression(field_type, 4442 SideEffects::FieldReadOfType(field_type, is_volatile), 4443 dex_pc), 4444 field_info_(field_offset, 4445 field_type, 4446 is_volatile, 4447 field_idx, 4448 declaring_class_def_index, 4449 dex_file, 4450 dex_cache) { 4451 SetRawInputAt(0, value); 4452 } 4453 4454 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 4455 4456 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 4457 HInstanceFieldGet* other_get = other->AsInstanceFieldGet(); 4458 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 4459 } 4460 4461 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 4462 return (obj == InputAt(0)) && GetFieldOffset().Uint32Value() < kPageSize; 4463 } 4464 4465 size_t ComputeHashCode() const OVERRIDE { 4466 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 4467 } 4468 4469 const FieldInfo& GetFieldInfo() const { return field_info_; } 4470 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 4471 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 4472 bool IsVolatile() const { return field_info_.IsVolatile(); } 4473 4474 DECLARE_INSTRUCTION(InstanceFieldGet); 4475 4476 private: 4477 const FieldInfo field_info_; 4478 4479 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet); 4480}; 4481 4482class HInstanceFieldSet : public HTemplateInstruction<2> { 4483 public: 4484 HInstanceFieldSet(HInstruction* object, 4485 HInstruction* value, 4486 Primitive::Type field_type, 4487 MemberOffset field_offset, 4488 bool is_volatile, 4489 uint32_t field_idx, 4490 uint16_t declaring_class_def_index, 4491 const DexFile& dex_file, 4492 Handle<mirror::DexCache> dex_cache, 4493 uint32_t dex_pc) 4494 : HTemplateInstruction(SideEffects::FieldWriteOfType(field_type, is_volatile), 4495 dex_pc), 4496 field_info_(field_offset, 4497 field_type, 4498 is_volatile, 4499 field_idx, 4500 declaring_class_def_index, 4501 dex_file, 4502 dex_cache), 4503 value_can_be_null_(true) { 4504 SetRawInputAt(0, object); 4505 SetRawInputAt(1, value); 4506 } 4507 4508 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 4509 return (obj == InputAt(0)) && GetFieldOffset().Uint32Value() < kPageSize; 4510 } 4511 4512 const FieldInfo& GetFieldInfo() const { return field_info_; } 4513 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 4514 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 4515 bool IsVolatile() const { return field_info_.IsVolatile(); } 4516 HInstruction* GetValue() const { return InputAt(1); } 4517 bool GetValueCanBeNull() const { return value_can_be_null_; } 4518 void ClearValueCanBeNull() { value_can_be_null_ = false; } 4519 4520 DECLARE_INSTRUCTION(InstanceFieldSet); 4521 4522 private: 4523 const FieldInfo field_info_; 4524 bool value_can_be_null_; 4525 4526 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet); 4527}; 4528 4529class HArrayGet : public HExpression<2> { 4530 public: 4531 HArrayGet(HInstruction* array, 4532 HInstruction* index, 4533 Primitive::Type type, 4534 uint32_t dex_pc, 4535 SideEffects additional_side_effects = SideEffects::None()) 4536 : HExpression(type, 4537 SideEffects::ArrayReadOfType(type).Union(additional_side_effects), 4538 dex_pc) { 4539 SetRawInputAt(0, array); 4540 SetRawInputAt(1, index); 4541 } 4542 4543 bool CanBeMoved() const OVERRIDE { return true; } 4544 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4545 return true; 4546 } 4547 bool CanDoImplicitNullCheckOn(HInstruction* obj ATTRIBUTE_UNUSED) const OVERRIDE { 4548 // TODO: We can be smarter here. 4549 // Currently, the array access is always preceded by an ArrayLength or a NullCheck 4550 // which generates the implicit null check. There are cases when these can be removed 4551 // to produce better code. If we ever add optimizations to do so we should allow an 4552 // implicit check here (as long as the address falls in the first page). 4553 return false; 4554 } 4555 4556 void SetType(Primitive::Type type) { type_ = type; } 4557 4558 HInstruction* GetArray() const { return InputAt(0); } 4559 HInstruction* GetIndex() const { return InputAt(1); } 4560 4561 DECLARE_INSTRUCTION(ArrayGet); 4562 4563 private: 4564 DISALLOW_COPY_AND_ASSIGN(HArrayGet); 4565}; 4566 4567class HArraySet : public HTemplateInstruction<3> { 4568 public: 4569 HArraySet(HInstruction* array, 4570 HInstruction* index, 4571 HInstruction* value, 4572 Primitive::Type expected_component_type, 4573 uint32_t dex_pc, 4574 SideEffects additional_side_effects = SideEffects::None()) 4575 : HTemplateInstruction( 4576 SideEffects::ArrayWriteOfType(expected_component_type).Union( 4577 SideEffectsForArchRuntimeCalls(value->GetType())).Union( 4578 additional_side_effects), 4579 dex_pc), 4580 expected_component_type_(expected_component_type), 4581 needs_type_check_(value->GetType() == Primitive::kPrimNot), 4582 value_can_be_null_(true), 4583 static_type_of_array_is_object_array_(false) { 4584 SetRawInputAt(0, array); 4585 SetRawInputAt(1, index); 4586 SetRawInputAt(2, value); 4587 } 4588 4589 bool NeedsEnvironment() const OVERRIDE { 4590 // We currently always call a runtime method to catch array store 4591 // exceptions. 4592 return needs_type_check_; 4593 } 4594 4595 // Can throw ArrayStoreException. 4596 bool CanThrow() const OVERRIDE { return needs_type_check_; } 4597 4598 bool CanDoImplicitNullCheckOn(HInstruction* obj ATTRIBUTE_UNUSED) const OVERRIDE { 4599 // TODO: Same as for ArrayGet. 4600 return false; 4601 } 4602 4603 void ClearNeedsTypeCheck() { 4604 needs_type_check_ = false; 4605 } 4606 4607 void ClearValueCanBeNull() { 4608 value_can_be_null_ = false; 4609 } 4610 4611 void SetStaticTypeOfArrayIsObjectArray() { 4612 static_type_of_array_is_object_array_ = true; 4613 } 4614 4615 bool GetValueCanBeNull() const { return value_can_be_null_; } 4616 bool NeedsTypeCheck() const { return needs_type_check_; } 4617 bool StaticTypeOfArrayIsObjectArray() const { return static_type_of_array_is_object_array_; } 4618 4619 HInstruction* GetArray() const { return InputAt(0); } 4620 HInstruction* GetIndex() const { return InputAt(1); } 4621 HInstruction* GetValue() const { return InputAt(2); } 4622 4623 Primitive::Type GetComponentType() const { 4624 // The Dex format does not type floating point index operations. Since the 4625 // `expected_component_type_` is set during building and can therefore not 4626 // be correct, we also check what is the value type. If it is a floating 4627 // point type, we must use that type. 4628 Primitive::Type value_type = GetValue()->GetType(); 4629 return ((value_type == Primitive::kPrimFloat) || (value_type == Primitive::kPrimDouble)) 4630 ? value_type 4631 : expected_component_type_; 4632 } 4633 4634 Primitive::Type GetRawExpectedComponentType() const { 4635 return expected_component_type_; 4636 } 4637 4638 static SideEffects SideEffectsForArchRuntimeCalls(Primitive::Type value_type) { 4639 return (value_type == Primitive::kPrimNot) ? SideEffects::CanTriggerGC() : SideEffects::None(); 4640 } 4641 4642 DECLARE_INSTRUCTION(ArraySet); 4643 4644 private: 4645 const Primitive::Type expected_component_type_; 4646 bool needs_type_check_; 4647 bool value_can_be_null_; 4648 // Cached information for the reference_type_info_ so that codegen 4649 // does not need to inspect the static type. 4650 bool static_type_of_array_is_object_array_; 4651 4652 DISALLOW_COPY_AND_ASSIGN(HArraySet); 4653}; 4654 4655class HArrayLength : public HExpression<1> { 4656 public: 4657 HArrayLength(HInstruction* array, uint32_t dex_pc) 4658 : HExpression(Primitive::kPrimInt, SideEffects::None(), dex_pc) { 4659 // Note that arrays do not change length, so the instruction does not 4660 // depend on any write. 4661 SetRawInputAt(0, array); 4662 } 4663 4664 bool CanBeMoved() const OVERRIDE { return true; } 4665 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4666 return true; 4667 } 4668 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 4669 return obj == InputAt(0); 4670 } 4671 4672 DECLARE_INSTRUCTION(ArrayLength); 4673 4674 private: 4675 DISALLOW_COPY_AND_ASSIGN(HArrayLength); 4676}; 4677 4678class HBoundsCheck : public HExpression<2> { 4679 public: 4680 HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc) 4681 : HExpression(index->GetType(), SideEffects::None(), dex_pc) { 4682 DCHECK(index->GetType() == Primitive::kPrimInt); 4683 SetRawInputAt(0, index); 4684 SetRawInputAt(1, length); 4685 } 4686 4687 bool CanBeMoved() const OVERRIDE { return true; } 4688 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4689 return true; 4690 } 4691 4692 bool NeedsEnvironment() const OVERRIDE { return true; } 4693 4694 bool CanThrow() const OVERRIDE { return true; } 4695 4696 HInstruction* GetIndex() const { return InputAt(0); } 4697 4698 DECLARE_INSTRUCTION(BoundsCheck); 4699 4700 private: 4701 DISALLOW_COPY_AND_ASSIGN(HBoundsCheck); 4702}; 4703 4704/** 4705 * Some DEX instructions are folded into multiple HInstructions that need 4706 * to stay live until the last HInstruction. This class 4707 * is used as a marker for the baseline compiler to ensure its preceding 4708 * HInstruction stays live. `index` represents the stack location index of the 4709 * instruction (the actual offset is computed as index * vreg_size). 4710 */ 4711class HTemporary : public HTemplateInstruction<0> { 4712 public: 4713 explicit HTemporary(size_t index, uint32_t dex_pc = kNoDexPc) 4714 : HTemplateInstruction(SideEffects::None(), dex_pc), index_(index) {} 4715 4716 size_t GetIndex() const { return index_; } 4717 4718 Primitive::Type GetType() const OVERRIDE { 4719 // The previous instruction is the one that will be stored in the temporary location. 4720 DCHECK(GetPrevious() != nullptr); 4721 return GetPrevious()->GetType(); 4722 } 4723 4724 DECLARE_INSTRUCTION(Temporary); 4725 4726 private: 4727 const size_t index_; 4728 DISALLOW_COPY_AND_ASSIGN(HTemporary); 4729}; 4730 4731class HSuspendCheck : public HTemplateInstruction<0> { 4732 public: 4733 explicit HSuspendCheck(uint32_t dex_pc) 4734 : HTemplateInstruction(SideEffects::CanTriggerGC(), dex_pc), slow_path_(nullptr) {} 4735 4736 bool NeedsEnvironment() const OVERRIDE { 4737 return true; 4738 } 4739 4740 void SetSlowPath(SlowPathCode* slow_path) { slow_path_ = slow_path; } 4741 SlowPathCode* GetSlowPath() const { return slow_path_; } 4742 4743 DECLARE_INSTRUCTION(SuspendCheck); 4744 4745 private: 4746 // Only used for code generation, in order to share the same slow path between back edges 4747 // of a same loop. 4748 SlowPathCode* slow_path_; 4749 4750 DISALLOW_COPY_AND_ASSIGN(HSuspendCheck); 4751}; 4752 4753/** 4754 * Instruction to load a Class object. 4755 */ 4756class HLoadClass : public HExpression<1> { 4757 public: 4758 HLoadClass(HCurrentMethod* current_method, 4759 uint16_t type_index, 4760 const DexFile& dex_file, 4761 bool is_referrers_class, 4762 uint32_t dex_pc, 4763 bool needs_access_check) 4764 : HExpression(Primitive::kPrimNot, SideEffectsForArchRuntimeCalls(), dex_pc), 4765 type_index_(type_index), 4766 dex_file_(dex_file), 4767 is_referrers_class_(is_referrers_class), 4768 generate_clinit_check_(false), 4769 needs_access_check_(needs_access_check), 4770 loaded_class_rti_(ReferenceTypeInfo::CreateInvalid()) { 4771 // Referrers class should not need access check. We never inline unverified 4772 // methods so we can't possibly end up in this situation. 4773 DCHECK(!is_referrers_class_ || !needs_access_check_); 4774 SetRawInputAt(0, current_method); 4775 } 4776 4777 bool CanBeMoved() const OVERRIDE { return true; } 4778 4779 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 4780 // Note that we don't need to test for generate_clinit_check_. 4781 // Whether or not we need to generate the clinit check is processed in 4782 // prepare_for_register_allocator based on existing HInvokes and HClinitChecks. 4783 return other->AsLoadClass()->type_index_ == type_index_ && 4784 other->AsLoadClass()->needs_access_check_ == needs_access_check_; 4785 } 4786 4787 size_t ComputeHashCode() const OVERRIDE { return type_index_; } 4788 4789 uint16_t GetTypeIndex() const { return type_index_; } 4790 bool IsReferrersClass() const { return is_referrers_class_; } 4791 bool CanBeNull() const OVERRIDE { return false; } 4792 4793 bool NeedsEnvironment() const OVERRIDE { 4794 // Will call runtime and load the class if the class is not loaded yet. 4795 // TODO: finer grain decision. 4796 return !is_referrers_class_; 4797 } 4798 4799 bool MustGenerateClinitCheck() const { 4800 return generate_clinit_check_; 4801 } 4802 void SetMustGenerateClinitCheck(bool generate_clinit_check) { 4803 // The entrypoint the code generator is going to call does not do 4804 // clinit of the class. 4805 DCHECK(!NeedsAccessCheck()); 4806 generate_clinit_check_ = generate_clinit_check; 4807 } 4808 4809 bool CanCallRuntime() const { 4810 return MustGenerateClinitCheck() || !is_referrers_class_ || needs_access_check_; 4811 } 4812 4813 bool NeedsAccessCheck() const { 4814 return needs_access_check_; 4815 } 4816 4817 bool CanThrow() const OVERRIDE { 4818 // May call runtime and and therefore can throw. 4819 // TODO: finer grain decision. 4820 return CanCallRuntime(); 4821 } 4822 4823 ReferenceTypeInfo GetLoadedClassRTI() { 4824 return loaded_class_rti_; 4825 } 4826 4827 void SetLoadedClassRTI(ReferenceTypeInfo rti) { 4828 // Make sure we only set exact types (the loaded class should never be merged). 4829 DCHECK(rti.IsExact()); 4830 loaded_class_rti_ = rti; 4831 } 4832 4833 const DexFile& GetDexFile() { return dex_file_; } 4834 4835 bool NeedsDexCacheOfDeclaringClass() const OVERRIDE { return !is_referrers_class_; } 4836 4837 static SideEffects SideEffectsForArchRuntimeCalls() { 4838 return SideEffects::CanTriggerGC(); 4839 } 4840 4841 DECLARE_INSTRUCTION(LoadClass); 4842 4843 private: 4844 const uint16_t type_index_; 4845 const DexFile& dex_file_; 4846 const bool is_referrers_class_; 4847 // Whether this instruction must generate the initialization check. 4848 // Used for code generation. 4849 bool generate_clinit_check_; 4850 bool needs_access_check_; 4851 4852 ReferenceTypeInfo loaded_class_rti_; 4853 4854 DISALLOW_COPY_AND_ASSIGN(HLoadClass); 4855}; 4856 4857class HLoadString : public HExpression<1> { 4858 public: 4859 HLoadString(HCurrentMethod* current_method, uint32_t string_index, uint32_t dex_pc) 4860 : HExpression(Primitive::kPrimNot, SideEffectsForArchRuntimeCalls(), dex_pc), 4861 string_index_(string_index) { 4862 SetRawInputAt(0, current_method); 4863 } 4864 4865 bool CanBeMoved() const OVERRIDE { return true; } 4866 4867 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 4868 return other->AsLoadString()->string_index_ == string_index_; 4869 } 4870 4871 size_t ComputeHashCode() const OVERRIDE { return string_index_; } 4872 4873 uint32_t GetStringIndex() const { return string_index_; } 4874 4875 // TODO: Can we deopt or debug when we resolve a string? 4876 bool NeedsEnvironment() const OVERRIDE { return false; } 4877 bool NeedsDexCacheOfDeclaringClass() const OVERRIDE { return true; } 4878 bool CanBeNull() const OVERRIDE { return false; } 4879 4880 static SideEffects SideEffectsForArchRuntimeCalls() { 4881 return SideEffects::CanTriggerGC(); 4882 } 4883 4884 DECLARE_INSTRUCTION(LoadString); 4885 4886 private: 4887 const uint32_t string_index_; 4888 4889 DISALLOW_COPY_AND_ASSIGN(HLoadString); 4890}; 4891 4892/** 4893 * Performs an initialization check on its Class object input. 4894 */ 4895class HClinitCheck : public HExpression<1> { 4896 public: 4897 HClinitCheck(HLoadClass* constant, uint32_t dex_pc) 4898 : HExpression( 4899 Primitive::kPrimNot, 4900 SideEffects::AllChanges(), // Assume write/read on all fields/arrays. 4901 dex_pc) { 4902 SetRawInputAt(0, constant); 4903 } 4904 4905 bool CanBeMoved() const OVERRIDE { return true; } 4906 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4907 return true; 4908 } 4909 4910 bool NeedsEnvironment() const OVERRIDE { 4911 // May call runtime to initialize the class. 4912 return true; 4913 } 4914 4915 4916 HLoadClass* GetLoadClass() const { return InputAt(0)->AsLoadClass(); } 4917 4918 DECLARE_INSTRUCTION(ClinitCheck); 4919 4920 private: 4921 DISALLOW_COPY_AND_ASSIGN(HClinitCheck); 4922}; 4923 4924class HStaticFieldGet : public HExpression<1> { 4925 public: 4926 HStaticFieldGet(HInstruction* cls, 4927 Primitive::Type field_type, 4928 MemberOffset field_offset, 4929 bool is_volatile, 4930 uint32_t field_idx, 4931 uint16_t declaring_class_def_index, 4932 const DexFile& dex_file, 4933 Handle<mirror::DexCache> dex_cache, 4934 uint32_t dex_pc) 4935 : HExpression(field_type, 4936 SideEffects::FieldReadOfType(field_type, is_volatile), 4937 dex_pc), 4938 field_info_(field_offset, 4939 field_type, 4940 is_volatile, 4941 field_idx, 4942 declaring_class_def_index, 4943 dex_file, 4944 dex_cache) { 4945 SetRawInputAt(0, cls); 4946 } 4947 4948 4949 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 4950 4951 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 4952 HStaticFieldGet* other_get = other->AsStaticFieldGet(); 4953 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 4954 } 4955 4956 size_t ComputeHashCode() const OVERRIDE { 4957 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 4958 } 4959 4960 const FieldInfo& GetFieldInfo() const { return field_info_; } 4961 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 4962 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 4963 bool IsVolatile() const { return field_info_.IsVolatile(); } 4964 4965 DECLARE_INSTRUCTION(StaticFieldGet); 4966 4967 private: 4968 const FieldInfo field_info_; 4969 4970 DISALLOW_COPY_AND_ASSIGN(HStaticFieldGet); 4971}; 4972 4973class HStaticFieldSet : public HTemplateInstruction<2> { 4974 public: 4975 HStaticFieldSet(HInstruction* cls, 4976 HInstruction* value, 4977 Primitive::Type field_type, 4978 MemberOffset field_offset, 4979 bool is_volatile, 4980 uint32_t field_idx, 4981 uint16_t declaring_class_def_index, 4982 const DexFile& dex_file, 4983 Handle<mirror::DexCache> dex_cache, 4984 uint32_t dex_pc) 4985 : HTemplateInstruction(SideEffects::FieldWriteOfType(field_type, is_volatile), 4986 dex_pc), 4987 field_info_(field_offset, 4988 field_type, 4989 is_volatile, 4990 field_idx, 4991 declaring_class_def_index, 4992 dex_file, 4993 dex_cache), 4994 value_can_be_null_(true) { 4995 SetRawInputAt(0, cls); 4996 SetRawInputAt(1, value); 4997 } 4998 4999 const FieldInfo& GetFieldInfo() const { return field_info_; } 5000 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 5001 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 5002 bool IsVolatile() const { return field_info_.IsVolatile(); } 5003 5004 HInstruction* GetValue() const { return InputAt(1); } 5005 bool GetValueCanBeNull() const { return value_can_be_null_; } 5006 void ClearValueCanBeNull() { value_can_be_null_ = false; } 5007 5008 DECLARE_INSTRUCTION(StaticFieldSet); 5009 5010 private: 5011 const FieldInfo field_info_; 5012 bool value_can_be_null_; 5013 5014 DISALLOW_COPY_AND_ASSIGN(HStaticFieldSet); 5015}; 5016 5017class HUnresolvedInstanceFieldGet : public HExpression<1> { 5018 public: 5019 HUnresolvedInstanceFieldGet(HInstruction* obj, 5020 Primitive::Type field_type, 5021 uint32_t field_index, 5022 uint32_t dex_pc) 5023 : HExpression(field_type, SideEffects::AllExceptGCDependency(), dex_pc), 5024 field_index_(field_index) { 5025 SetRawInputAt(0, obj); 5026 } 5027 5028 bool NeedsEnvironment() const OVERRIDE { return true; } 5029 bool CanThrow() const OVERRIDE { return true; } 5030 5031 Primitive::Type GetFieldType() const { return GetType(); } 5032 uint32_t GetFieldIndex() const { return field_index_; } 5033 5034 DECLARE_INSTRUCTION(UnresolvedInstanceFieldGet); 5035 5036 private: 5037 const uint32_t field_index_; 5038 5039 DISALLOW_COPY_AND_ASSIGN(HUnresolvedInstanceFieldGet); 5040}; 5041 5042class HUnresolvedInstanceFieldSet : public HTemplateInstruction<2> { 5043 public: 5044 HUnresolvedInstanceFieldSet(HInstruction* obj, 5045 HInstruction* value, 5046 Primitive::Type field_type, 5047 uint32_t field_index, 5048 uint32_t dex_pc) 5049 : HTemplateInstruction(SideEffects::AllExceptGCDependency(), dex_pc), 5050 field_type_(field_type), 5051 field_index_(field_index) { 5052 DCHECK_EQ(field_type, value->GetType()); 5053 SetRawInputAt(0, obj); 5054 SetRawInputAt(1, value); 5055 } 5056 5057 bool NeedsEnvironment() const OVERRIDE { return true; } 5058 bool CanThrow() const OVERRIDE { return true; } 5059 5060 Primitive::Type GetFieldType() const { return field_type_; } 5061 uint32_t GetFieldIndex() const { return field_index_; } 5062 5063 DECLARE_INSTRUCTION(UnresolvedInstanceFieldSet); 5064 5065 private: 5066 const Primitive::Type field_type_; 5067 const uint32_t field_index_; 5068 5069 DISALLOW_COPY_AND_ASSIGN(HUnresolvedInstanceFieldSet); 5070}; 5071 5072class HUnresolvedStaticFieldGet : public HExpression<0> { 5073 public: 5074 HUnresolvedStaticFieldGet(Primitive::Type field_type, 5075 uint32_t field_index, 5076 uint32_t dex_pc) 5077 : HExpression(field_type, SideEffects::AllExceptGCDependency(), dex_pc), 5078 field_index_(field_index) { 5079 } 5080 5081 bool NeedsEnvironment() const OVERRIDE { return true; } 5082 bool CanThrow() const OVERRIDE { return true; } 5083 5084 Primitive::Type GetFieldType() const { return GetType(); } 5085 uint32_t GetFieldIndex() const { return field_index_; } 5086 5087 DECLARE_INSTRUCTION(UnresolvedStaticFieldGet); 5088 5089 private: 5090 const uint32_t field_index_; 5091 5092 DISALLOW_COPY_AND_ASSIGN(HUnresolvedStaticFieldGet); 5093}; 5094 5095class HUnresolvedStaticFieldSet : public HTemplateInstruction<1> { 5096 public: 5097 HUnresolvedStaticFieldSet(HInstruction* value, 5098 Primitive::Type field_type, 5099 uint32_t field_index, 5100 uint32_t dex_pc) 5101 : HTemplateInstruction(SideEffects::AllExceptGCDependency(), dex_pc), 5102 field_type_(field_type), 5103 field_index_(field_index) { 5104 DCHECK_EQ(field_type, value->GetType()); 5105 SetRawInputAt(0, value); 5106 } 5107 5108 bool NeedsEnvironment() const OVERRIDE { return true; } 5109 bool CanThrow() const OVERRIDE { return true; } 5110 5111 Primitive::Type GetFieldType() const { return field_type_; } 5112 uint32_t GetFieldIndex() const { return field_index_; } 5113 5114 DECLARE_INSTRUCTION(UnresolvedStaticFieldSet); 5115 5116 private: 5117 const Primitive::Type field_type_; 5118 const uint32_t field_index_; 5119 5120 DISALLOW_COPY_AND_ASSIGN(HUnresolvedStaticFieldSet); 5121}; 5122 5123// Implement the move-exception DEX instruction. 5124class HLoadException : public HExpression<0> { 5125 public: 5126 explicit HLoadException(uint32_t dex_pc = kNoDexPc) 5127 : HExpression(Primitive::kPrimNot, SideEffects::None(), dex_pc) {} 5128 5129 bool CanBeNull() const OVERRIDE { return false; } 5130 5131 DECLARE_INSTRUCTION(LoadException); 5132 5133 private: 5134 DISALLOW_COPY_AND_ASSIGN(HLoadException); 5135}; 5136 5137// Implicit part of move-exception which clears thread-local exception storage. 5138// Must not be removed because the runtime expects the TLS to get cleared. 5139class HClearException : public HTemplateInstruction<0> { 5140 public: 5141 explicit HClearException(uint32_t dex_pc = kNoDexPc) 5142 : HTemplateInstruction(SideEffects::AllWrites(), dex_pc) {} 5143 5144 DECLARE_INSTRUCTION(ClearException); 5145 5146 private: 5147 DISALLOW_COPY_AND_ASSIGN(HClearException); 5148}; 5149 5150class HThrow : public HTemplateInstruction<1> { 5151 public: 5152 HThrow(HInstruction* exception, uint32_t dex_pc) 5153 : HTemplateInstruction(SideEffects::CanTriggerGC(), dex_pc) { 5154 SetRawInputAt(0, exception); 5155 } 5156 5157 bool IsControlFlow() const OVERRIDE { return true; } 5158 5159 bool NeedsEnvironment() const OVERRIDE { return true; } 5160 5161 bool CanThrow() const OVERRIDE { return true; } 5162 5163 5164 DECLARE_INSTRUCTION(Throw); 5165 5166 private: 5167 DISALLOW_COPY_AND_ASSIGN(HThrow); 5168}; 5169 5170/** 5171 * Implementation strategies for the code generator of a HInstanceOf 5172 * or `HCheckCast`. 5173 */ 5174enum class TypeCheckKind { 5175 kUnresolvedCheck, // Check against an unresolved type. 5176 kExactCheck, // Can do a single class compare. 5177 kClassHierarchyCheck, // Can just walk the super class chain. 5178 kAbstractClassCheck, // Can just walk the super class chain, starting one up. 5179 kInterfaceCheck, // No optimization yet when checking against an interface. 5180 kArrayObjectCheck, // Can just check if the array is not primitive. 5181 kArrayCheck // No optimization yet when checking against a generic array. 5182}; 5183 5184class HInstanceOf : public HExpression<2> { 5185 public: 5186 HInstanceOf(HInstruction* object, 5187 HLoadClass* constant, 5188 TypeCheckKind check_kind, 5189 uint32_t dex_pc) 5190 : HExpression(Primitive::kPrimBoolean, 5191 SideEffectsForArchRuntimeCalls(check_kind), 5192 dex_pc), 5193 check_kind_(check_kind), 5194 must_do_null_check_(true) { 5195 SetRawInputAt(0, object); 5196 SetRawInputAt(1, constant); 5197 } 5198 5199 bool CanBeMoved() const OVERRIDE { return true; } 5200 5201 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 5202 return true; 5203 } 5204 5205 bool NeedsEnvironment() const OVERRIDE { 5206 return false; 5207 } 5208 5209 bool IsExactCheck() const { return check_kind_ == TypeCheckKind::kExactCheck; } 5210 5211 TypeCheckKind GetTypeCheckKind() const { return check_kind_; } 5212 5213 // Used only in code generation. 5214 bool MustDoNullCheck() const { return must_do_null_check_; } 5215 void ClearMustDoNullCheck() { must_do_null_check_ = false; } 5216 5217 static SideEffects SideEffectsForArchRuntimeCalls(TypeCheckKind check_kind) { 5218 return (check_kind == TypeCheckKind::kExactCheck) 5219 ? SideEffects::None() 5220 // Mips currently does runtime calls for any other checks. 5221 : SideEffects::CanTriggerGC(); 5222 } 5223 5224 DECLARE_INSTRUCTION(InstanceOf); 5225 5226 private: 5227 const TypeCheckKind check_kind_; 5228 bool must_do_null_check_; 5229 5230 DISALLOW_COPY_AND_ASSIGN(HInstanceOf); 5231}; 5232 5233class HBoundType : public HExpression<1> { 5234 public: 5235 // Constructs an HBoundType with the given upper_bound. 5236 // Ensures that the upper_bound is valid. 5237 HBoundType(HInstruction* input, 5238 ReferenceTypeInfo upper_bound, 5239 bool upper_can_be_null, 5240 uint32_t dex_pc = kNoDexPc) 5241 : HExpression(Primitive::kPrimNot, SideEffects::None(), dex_pc), 5242 upper_bound_(upper_bound), 5243 upper_can_be_null_(upper_can_be_null), 5244 can_be_null_(upper_can_be_null) { 5245 DCHECK_EQ(input->GetType(), Primitive::kPrimNot); 5246 SetRawInputAt(0, input); 5247 SetReferenceTypeInfo(upper_bound_); 5248 } 5249 5250 // GetUpper* should only be used in reference type propagation. 5251 const ReferenceTypeInfo& GetUpperBound() const { return upper_bound_; } 5252 bool GetUpperCanBeNull() const { return upper_can_be_null_; } 5253 5254 void SetCanBeNull(bool can_be_null) { 5255 DCHECK(upper_can_be_null_ || !can_be_null); 5256 can_be_null_ = can_be_null; 5257 } 5258 5259 bool CanBeNull() const OVERRIDE { return can_be_null_; } 5260 5261 DECLARE_INSTRUCTION(BoundType); 5262 5263 private: 5264 // Encodes the most upper class that this instruction can have. In other words 5265 // it is always the case that GetUpperBound().IsSupertypeOf(GetReferenceType()). 5266 // It is used to bound the type in cases like: 5267 // if (x instanceof ClassX) { 5268 // // uper_bound_ will be ClassX 5269 // } 5270 const ReferenceTypeInfo upper_bound_; 5271 // Represents the top constraint that can_be_null_ cannot exceed (i.e. if this 5272 // is false then can_be_null_ cannot be true). 5273 const bool upper_can_be_null_; 5274 bool can_be_null_; 5275 5276 DISALLOW_COPY_AND_ASSIGN(HBoundType); 5277}; 5278 5279class HCheckCast : public HTemplateInstruction<2> { 5280 public: 5281 HCheckCast(HInstruction* object, 5282 HLoadClass* constant, 5283 TypeCheckKind check_kind, 5284 uint32_t dex_pc) 5285 : HTemplateInstruction(SideEffects::CanTriggerGC(), dex_pc), 5286 check_kind_(check_kind), 5287 must_do_null_check_(true) { 5288 SetRawInputAt(0, object); 5289 SetRawInputAt(1, constant); 5290 } 5291 5292 bool CanBeMoved() const OVERRIDE { return true; } 5293 5294 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 5295 return true; 5296 } 5297 5298 bool NeedsEnvironment() const OVERRIDE { 5299 // Instruction may throw a CheckCastError. 5300 return true; 5301 } 5302 5303 bool CanThrow() const OVERRIDE { return true; } 5304 5305 bool MustDoNullCheck() const { return must_do_null_check_; } 5306 void ClearMustDoNullCheck() { must_do_null_check_ = false; } 5307 TypeCheckKind GetTypeCheckKind() const { return check_kind_; } 5308 5309 bool IsExactCheck() const { return check_kind_ == TypeCheckKind::kExactCheck; } 5310 5311 DECLARE_INSTRUCTION(CheckCast); 5312 5313 private: 5314 const TypeCheckKind check_kind_; 5315 bool must_do_null_check_; 5316 5317 DISALLOW_COPY_AND_ASSIGN(HCheckCast); 5318}; 5319 5320class HMemoryBarrier : public HTemplateInstruction<0> { 5321 public: 5322 explicit HMemoryBarrier(MemBarrierKind barrier_kind, uint32_t dex_pc = kNoDexPc) 5323 : HTemplateInstruction( 5324 SideEffects::AllWritesAndReads(), dex_pc), // Assume write/read on all fields/arrays. 5325 barrier_kind_(barrier_kind) {} 5326 5327 MemBarrierKind GetBarrierKind() { return barrier_kind_; } 5328 5329 DECLARE_INSTRUCTION(MemoryBarrier); 5330 5331 private: 5332 const MemBarrierKind barrier_kind_; 5333 5334 DISALLOW_COPY_AND_ASSIGN(HMemoryBarrier); 5335}; 5336 5337class HMonitorOperation : public HTemplateInstruction<1> { 5338 public: 5339 enum OperationKind { 5340 kEnter, 5341 kExit, 5342 }; 5343 5344 HMonitorOperation(HInstruction* object, OperationKind kind, uint32_t dex_pc) 5345 : HTemplateInstruction( 5346 SideEffects::AllExceptGCDependency(), dex_pc), // Assume write/read on all fields/arrays. 5347 kind_(kind) { 5348 SetRawInputAt(0, object); 5349 } 5350 5351 // Instruction may throw a Java exception, so we need an environment. 5352 bool NeedsEnvironment() const OVERRIDE { return CanThrow(); } 5353 5354 bool CanThrow() const OVERRIDE { 5355 // Verifier guarantees that monitor-exit cannot throw. 5356 // This is important because it allows the HGraphBuilder to remove 5357 // a dead throw-catch loop generated for `synchronized` blocks/methods. 5358 return IsEnter(); 5359 } 5360 5361 5362 bool IsEnter() const { return kind_ == kEnter; } 5363 5364 DECLARE_INSTRUCTION(MonitorOperation); 5365 5366 private: 5367 const OperationKind kind_; 5368 5369 private: 5370 DISALLOW_COPY_AND_ASSIGN(HMonitorOperation); 5371}; 5372 5373/** 5374 * A HInstruction used as a marker for the replacement of new + <init> 5375 * of a String to a call to a StringFactory. Only baseline will see 5376 * the node at code generation, where it will be be treated as null. 5377 * When compiling non-baseline, `HFakeString` instructions are being removed 5378 * in the instruction simplifier. 5379 */ 5380class HFakeString : public HTemplateInstruction<0> { 5381 public: 5382 explicit HFakeString(uint32_t dex_pc = kNoDexPc) 5383 : HTemplateInstruction(SideEffects::None(), dex_pc) {} 5384 5385 Primitive::Type GetType() const OVERRIDE { return Primitive::kPrimNot; } 5386 5387 DECLARE_INSTRUCTION(FakeString); 5388 5389 private: 5390 DISALLOW_COPY_AND_ASSIGN(HFakeString); 5391}; 5392 5393class MoveOperands : public ArenaObject<kArenaAllocMoveOperands> { 5394 public: 5395 MoveOperands(Location source, 5396 Location destination, 5397 Primitive::Type type, 5398 HInstruction* instruction) 5399 : source_(source), destination_(destination), type_(type), instruction_(instruction) {} 5400 5401 Location GetSource() const { return source_; } 5402 Location GetDestination() const { return destination_; } 5403 5404 void SetSource(Location value) { source_ = value; } 5405 void SetDestination(Location value) { destination_ = value; } 5406 5407 // The parallel move resolver marks moves as "in-progress" by clearing the 5408 // destination (but not the source). 5409 Location MarkPending() { 5410 DCHECK(!IsPending()); 5411 Location dest = destination_; 5412 destination_ = Location::NoLocation(); 5413 return dest; 5414 } 5415 5416 void ClearPending(Location dest) { 5417 DCHECK(IsPending()); 5418 destination_ = dest; 5419 } 5420 5421 bool IsPending() const { 5422 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 5423 return destination_.IsInvalid() && !source_.IsInvalid(); 5424 } 5425 5426 // True if this blocks a move from the given location. 5427 bool Blocks(Location loc) const { 5428 return !IsEliminated() && source_.OverlapsWith(loc); 5429 } 5430 5431 // A move is redundant if it's been eliminated, if its source and 5432 // destination are the same, or if its destination is unneeded. 5433 bool IsRedundant() const { 5434 return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_); 5435 } 5436 5437 // We clear both operands to indicate move that's been eliminated. 5438 void Eliminate() { 5439 source_ = destination_ = Location::NoLocation(); 5440 } 5441 5442 bool IsEliminated() const { 5443 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 5444 return source_.IsInvalid(); 5445 } 5446 5447 Primitive::Type GetType() const { return type_; } 5448 5449 bool Is64BitMove() const { 5450 return Primitive::Is64BitType(type_); 5451 } 5452 5453 HInstruction* GetInstruction() const { return instruction_; } 5454 5455 private: 5456 Location source_; 5457 Location destination_; 5458 // The type this move is for. 5459 Primitive::Type type_; 5460 // The instruction this move is assocatied with. Null when this move is 5461 // for moving an input in the expected locations of user (including a phi user). 5462 // This is only used in debug mode, to ensure we do not connect interval siblings 5463 // in the same parallel move. 5464 HInstruction* instruction_; 5465}; 5466 5467static constexpr size_t kDefaultNumberOfMoves = 4; 5468 5469class HParallelMove : public HTemplateInstruction<0> { 5470 public: 5471 explicit HParallelMove(ArenaAllocator* arena, uint32_t dex_pc = kNoDexPc) 5472 : HTemplateInstruction(SideEffects::None(), dex_pc), 5473 moves_(arena->Adapter(kArenaAllocMoveOperands)) { 5474 moves_.reserve(kDefaultNumberOfMoves); 5475 } 5476 5477 void AddMove(Location source, 5478 Location destination, 5479 Primitive::Type type, 5480 HInstruction* instruction) { 5481 DCHECK(source.IsValid()); 5482 DCHECK(destination.IsValid()); 5483 if (kIsDebugBuild) { 5484 if (instruction != nullptr) { 5485 for (const MoveOperands& move : moves_) { 5486 if (move.GetInstruction() == instruction) { 5487 // Special case the situation where the move is for the spill slot 5488 // of the instruction. 5489 if ((GetPrevious() == instruction) 5490 || ((GetPrevious() == nullptr) 5491 && instruction->IsPhi() 5492 && instruction->GetBlock() == GetBlock())) { 5493 DCHECK_NE(destination.GetKind(), move.GetDestination().GetKind()) 5494 << "Doing parallel moves for the same instruction."; 5495 } else { 5496 DCHECK(false) << "Doing parallel moves for the same instruction."; 5497 } 5498 } 5499 } 5500 } 5501 for (const MoveOperands& move : moves_) { 5502 DCHECK(!destination.OverlapsWith(move.GetDestination())) 5503 << "Overlapped destination for two moves in a parallel move: " 5504 << move.GetSource() << " ==> " << move.GetDestination() << " and " 5505 << source << " ==> " << destination; 5506 } 5507 } 5508 moves_.emplace_back(source, destination, type, instruction); 5509 } 5510 5511 MoveOperands* MoveOperandsAt(size_t index) { 5512 return &moves_[index]; 5513 } 5514 5515 size_t NumMoves() const { return moves_.size(); } 5516 5517 DECLARE_INSTRUCTION(ParallelMove); 5518 5519 private: 5520 ArenaVector<MoveOperands> moves_; 5521 5522 DISALLOW_COPY_AND_ASSIGN(HParallelMove); 5523}; 5524 5525} // namespace art 5526 5527#ifdef ART_ENABLE_CODEGEN_arm64 5528#include "nodes_arm64.h" 5529#endif 5530#ifdef ART_ENABLE_CODEGEN_x86 5531#include "nodes_x86.h" 5532#endif 5533 5534namespace art { 5535 5536class HGraphVisitor : public ValueObject { 5537 public: 5538 explicit HGraphVisitor(HGraph* graph) : graph_(graph) {} 5539 virtual ~HGraphVisitor() {} 5540 5541 virtual void VisitInstruction(HInstruction* instruction ATTRIBUTE_UNUSED) {} 5542 virtual void VisitBasicBlock(HBasicBlock* block); 5543 5544 // Visit the graph following basic block insertion order. 5545 void VisitInsertionOrder(); 5546 5547 // Visit the graph following dominator tree reverse post-order. 5548 void VisitReversePostOrder(); 5549 5550 HGraph* GetGraph() const { return graph_; } 5551 5552 // Visit functions for instruction classes. 5553#define DECLARE_VISIT_INSTRUCTION(name, super) \ 5554 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } 5555 5556 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 5557 5558#undef DECLARE_VISIT_INSTRUCTION 5559 5560 private: 5561 HGraph* const graph_; 5562 5563 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); 5564}; 5565 5566class HGraphDelegateVisitor : public HGraphVisitor { 5567 public: 5568 explicit HGraphDelegateVisitor(HGraph* graph) : HGraphVisitor(graph) {} 5569 virtual ~HGraphDelegateVisitor() {} 5570 5571 // Visit functions that delegate to to super class. 5572#define DECLARE_VISIT_INSTRUCTION(name, super) \ 5573 void Visit##name(H##name* instr) OVERRIDE { Visit##super(instr); } 5574 5575 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 5576 5577#undef DECLARE_VISIT_INSTRUCTION 5578 5579 private: 5580 DISALLOW_COPY_AND_ASSIGN(HGraphDelegateVisitor); 5581}; 5582 5583class HInsertionOrderIterator : public ValueObject { 5584 public: 5585 explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 5586 5587 bool Done() const { return index_ == graph_.GetBlocks().size(); } 5588 HBasicBlock* Current() const { return graph_.GetBlocks()[index_]; } 5589 void Advance() { ++index_; } 5590 5591 private: 5592 const HGraph& graph_; 5593 size_t index_; 5594 5595 DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator); 5596}; 5597 5598class HReversePostOrderIterator : public ValueObject { 5599 public: 5600 explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) { 5601 // Check that reverse post order of the graph has been built. 5602 DCHECK(!graph.GetReversePostOrder().empty()); 5603 } 5604 5605 bool Done() const { return index_ == graph_.GetReversePostOrder().size(); } 5606 HBasicBlock* Current() const { return graph_.GetReversePostOrder()[index_]; } 5607 void Advance() { ++index_; } 5608 5609 private: 5610 const HGraph& graph_; 5611 size_t index_; 5612 5613 DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator); 5614}; 5615 5616class HPostOrderIterator : public ValueObject { 5617 public: 5618 explicit HPostOrderIterator(const HGraph& graph) 5619 : graph_(graph), index_(graph_.GetReversePostOrder().size()) { 5620 // Check that reverse post order of the graph has been built. 5621 DCHECK(!graph.GetReversePostOrder().empty()); 5622 } 5623 5624 bool Done() const { return index_ == 0; } 5625 HBasicBlock* Current() const { return graph_.GetReversePostOrder()[index_ - 1u]; } 5626 void Advance() { --index_; } 5627 5628 private: 5629 const HGraph& graph_; 5630 size_t index_; 5631 5632 DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); 5633}; 5634 5635class HLinearPostOrderIterator : public ValueObject { 5636 public: 5637 explicit HLinearPostOrderIterator(const HGraph& graph) 5638 : order_(graph.GetLinearOrder()), index_(graph.GetLinearOrder().size()) {} 5639 5640 bool Done() const { return index_ == 0; } 5641 5642 HBasicBlock* Current() const { return order_[index_ - 1u]; } 5643 5644 void Advance() { 5645 --index_; 5646 DCHECK_GE(index_, 0U); 5647 } 5648 5649 private: 5650 const ArenaVector<HBasicBlock*>& order_; 5651 size_t index_; 5652 5653 DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator); 5654}; 5655 5656class HLinearOrderIterator : public ValueObject { 5657 public: 5658 explicit HLinearOrderIterator(const HGraph& graph) 5659 : order_(graph.GetLinearOrder()), index_(0) {} 5660 5661 bool Done() const { return index_ == order_.size(); } 5662 HBasicBlock* Current() const { return order_[index_]; } 5663 void Advance() { ++index_; } 5664 5665 private: 5666 const ArenaVector<HBasicBlock*>& order_; 5667 size_t index_; 5668 5669 DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator); 5670}; 5671 5672// Iterator over the blocks that art part of the loop. Includes blocks part 5673// of an inner loop. The order in which the blocks are iterated is on their 5674// block id. 5675class HBlocksInLoopIterator : public ValueObject { 5676 public: 5677 explicit HBlocksInLoopIterator(const HLoopInformation& info) 5678 : blocks_in_loop_(info.GetBlocks()), 5679 blocks_(info.GetHeader()->GetGraph()->GetBlocks()), 5680 index_(0) { 5681 if (!blocks_in_loop_.IsBitSet(index_)) { 5682 Advance(); 5683 } 5684 } 5685 5686 bool Done() const { return index_ == blocks_.size(); } 5687 HBasicBlock* Current() const { return blocks_[index_]; } 5688 void Advance() { 5689 ++index_; 5690 for (size_t e = blocks_.size(); index_ < e; ++index_) { 5691 if (blocks_in_loop_.IsBitSet(index_)) { 5692 break; 5693 } 5694 } 5695 } 5696 5697 private: 5698 const BitVector& blocks_in_loop_; 5699 const ArenaVector<HBasicBlock*>& blocks_; 5700 size_t index_; 5701 5702 DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopIterator); 5703}; 5704 5705// Iterator over the blocks that art part of the loop. Includes blocks part 5706// of an inner loop. The order in which the blocks are iterated is reverse 5707// post order. 5708class HBlocksInLoopReversePostOrderIterator : public ValueObject { 5709 public: 5710 explicit HBlocksInLoopReversePostOrderIterator(const HLoopInformation& info) 5711 : blocks_in_loop_(info.GetBlocks()), 5712 blocks_(info.GetHeader()->GetGraph()->GetReversePostOrder()), 5713 index_(0) { 5714 if (!blocks_in_loop_.IsBitSet(blocks_[index_]->GetBlockId())) { 5715 Advance(); 5716 } 5717 } 5718 5719 bool Done() const { return index_ == blocks_.size(); } 5720 HBasicBlock* Current() const { return blocks_[index_]; } 5721 void Advance() { 5722 ++index_; 5723 for (size_t e = blocks_.size(); index_ < e; ++index_) { 5724 if (blocks_in_loop_.IsBitSet(blocks_[index_]->GetBlockId())) { 5725 break; 5726 } 5727 } 5728 } 5729 5730 private: 5731 const BitVector& blocks_in_loop_; 5732 const ArenaVector<HBasicBlock*>& blocks_; 5733 size_t index_; 5734 5735 DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopReversePostOrderIterator); 5736}; 5737 5738inline int64_t Int64FromConstant(HConstant* constant) { 5739 DCHECK(constant->IsIntConstant() || constant->IsLongConstant()); 5740 return constant->IsIntConstant() ? constant->AsIntConstant()->GetValue() 5741 : constant->AsLongConstant()->GetValue(); 5742} 5743 5744inline bool IsSameDexFile(const DexFile& lhs, const DexFile& rhs) { 5745 // For the purposes of the compiler, the dex files must actually be the same object 5746 // if we want to safely treat them as the same. This is especially important for JIT 5747 // as custom class loaders can open the same underlying file (or memory) multiple 5748 // times and provide different class resolution but no two class loaders should ever 5749 // use the same DexFile object - doing so is an unsupported hack that can lead to 5750 // all sorts of weird failures. 5751 return &lhs == &rhs; 5752} 5753 5754} // namespace art 5755 5756#endif // ART_COMPILER_OPTIMIZING_NODES_H_ 5757