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