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