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