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