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