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