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