nodes.h revision 8c0676ce786f33b8f9c8eedf1ace48988c750932
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 for write/read dependences on fields/arrays. 1219 * 1220 * The dependence analysis uses type disambiguation (e.g. a float field write 1221 * cannot modify the value of an integer field read) and the access type (e.g. 1222 * a reference array write cannot modify the value of a reference field read 1223 * [although it may modify the reference fetch prior to reading the field, 1224 * which is represented by its own write/read dependence]). The analysis 1225 * makes conservative points-to assumptions on reference types (e.g. two same 1226 * typed arrays are assumed to be the same, and any reference read depends 1227 * on any reference read without further regard of its type). 1228 * 1229 * The internal representation uses the following 36-bit flags assignments: 1230 * 1231 * |ARRAY-R |FIELD-R |ARRAY-W |FIELD-W | 1232 * +---------+---------+---------+---------+ 1233 * |543210987|654321098|765432109|876543210| 1234 * |DFJISCBZL|DFJISCBZL|DFJISCBZL|DFJISCBZL| 1235 */ 1236class SideEffects : public ValueObject { 1237 public: 1238 SideEffects() : flags_(0) {} 1239 1240 static SideEffects None() { 1241 return SideEffects(0); 1242 } 1243 1244 static SideEffects All() { 1245 return SideEffects(kAllWrites | kAllReads); 1246 } 1247 1248 static SideEffects AllWrites() { 1249 return SideEffects(kAllWrites); 1250 } 1251 1252 static SideEffects AllReads() { 1253 return SideEffects(kAllReads); 1254 } 1255 1256 static SideEffects FieldWriteOfType(Primitive::Type type, bool is_volatile) { 1257 return is_volatile 1258 ? All() 1259 : SideEffects(TypeFlagWithAlias(type, kFieldWriteOffset)); 1260 } 1261 1262 static SideEffects ArrayWriteOfType(Primitive::Type type) { 1263 return SideEffects(TypeFlagWithAlias(type, kArrayWriteOffset)); 1264 } 1265 1266 static SideEffects FieldReadOfType(Primitive::Type type, bool is_volatile) { 1267 return is_volatile 1268 ? All() 1269 : SideEffects(TypeFlagWithAlias(type, kFieldReadOffset)); 1270 } 1271 1272 static SideEffects ArrayReadOfType(Primitive::Type type) { 1273 return SideEffects(TypeFlagWithAlias(type, kArrayReadOffset)); 1274 } 1275 1276 // Combines the side-effects of this and the other. 1277 SideEffects Union(SideEffects other) const { 1278 return SideEffects(flags_ | other.flags_); 1279 } 1280 1281 // Returns true if something is written. 1282 bool DoesAnyWrite() const { 1283 return (flags_ & kAllWrites); 1284 } 1285 1286 // Returns true if something is read. 1287 bool DoesAnyRead() const { 1288 return (flags_ & kAllReads); 1289 } 1290 1291 // Returns true if nothing is written or read. 1292 bool DoesNothing() const { 1293 return flags_ == 0; 1294 } 1295 1296 // Returns true if potentially everything is written and read 1297 // (every type and every kind of access). 1298 bool DoesAll() const { 1299 return flags_ == (kAllWrites | kAllReads); 1300 } 1301 1302 // Returns true if this may read something written by other. 1303 bool MayDependOn(SideEffects other) const { 1304 const uint64_t reads = (flags_ & kAllReads) >> kFieldReadOffset; 1305 return (other.flags_ & reads); 1306 } 1307 1308 // Returns string representation of flags (for debugging only). 1309 // Format: |DFJISCBZL|DFJISCBZL|DFJISCBZL|DFJISCBZL| 1310 std::string ToString() const { 1311 static const char *kDebug = "LZBCSIJFD"; 1312 std::string flags = "|"; 1313 for (int s = 35; s >= 0; s--) { 1314 const int t = s % kBits; 1315 if ((flags_ >> s) & 1) 1316 flags += kDebug[t]; 1317 if (t == 0) 1318 flags += "|"; 1319 } 1320 return flags; 1321 } 1322 1323 private: 1324 static constexpr int kBits = 9; 1325 static constexpr int kFieldWriteOffset = 0 * kBits; 1326 static constexpr int kArrayWriteOffset = 1 * kBits; 1327 static constexpr int kFieldReadOffset = 2 * kBits; 1328 static constexpr int kArrayReadOffset = 3 * kBits; 1329 1330 static constexpr uint64_t kAllWrites = 0x0003ffff; 1331 static constexpr uint64_t kAllReads = kAllWrites << kFieldReadOffset; 1332 1333 // Work around the fact that HIR aliases I/F and J/D. 1334 // TODO: remove this interceptor once HIR types are clean 1335 static uint64_t TypeFlagWithAlias(Primitive::Type type, int offset) { 1336 switch (type) { 1337 case Primitive::kPrimInt: 1338 case Primitive::kPrimFloat: 1339 return TypeFlag(Primitive::kPrimInt, offset) | 1340 TypeFlag(Primitive::kPrimFloat, offset); 1341 case Primitive::kPrimLong: 1342 case Primitive::kPrimDouble: 1343 return TypeFlag(Primitive::kPrimLong, offset) | 1344 TypeFlag(Primitive::kPrimDouble, offset); 1345 default: 1346 return TypeFlag(type, offset); 1347 } 1348 } 1349 1350 // Translates type to bit flag. 1351 static uint64_t TypeFlag(Primitive::Type type, int offset) { 1352 CHECK_NE(type, Primitive::kPrimVoid); 1353 const uint64_t one = 1; 1354 const int shift = type; // 0-based consecutive enum 1355 DCHECK_LE(kFieldWriteOffset, shift); 1356 DCHECK_LT(shift, kArrayWriteOffset); 1357 return one << (type + offset); 1358 } 1359 1360 // Private constructor on direct flags value. 1361 explicit SideEffects(uint64_t flags) : flags_(flags) {} 1362 1363 uint64_t flags_; 1364}; 1365 1366// A HEnvironment object contains the values of virtual registers at a given location. 1367class HEnvironment : public ArenaObject<kArenaAllocMisc> { 1368 public: 1369 HEnvironment(ArenaAllocator* arena, 1370 size_t number_of_vregs, 1371 const DexFile& dex_file, 1372 uint32_t method_idx, 1373 uint32_t dex_pc, 1374 InvokeType invoke_type, 1375 HInstruction* holder) 1376 : vregs_(arena, number_of_vregs), 1377 locations_(arena, number_of_vregs), 1378 parent_(nullptr), 1379 dex_file_(dex_file), 1380 method_idx_(method_idx), 1381 dex_pc_(dex_pc), 1382 invoke_type_(invoke_type), 1383 holder_(holder) { 1384 vregs_.SetSize(number_of_vregs); 1385 for (size_t i = 0; i < number_of_vregs; i++) { 1386 vregs_.Put(i, HUserRecord<HEnvironment*>()); 1387 } 1388 1389 locations_.SetSize(number_of_vregs); 1390 for (size_t i = 0; i < number_of_vregs; ++i) { 1391 locations_.Put(i, Location()); 1392 } 1393 } 1394 1395 HEnvironment(ArenaAllocator* arena, const HEnvironment& to_copy, HInstruction* holder) 1396 : HEnvironment(arena, 1397 to_copy.Size(), 1398 to_copy.GetDexFile(), 1399 to_copy.GetMethodIdx(), 1400 to_copy.GetDexPc(), 1401 to_copy.GetInvokeType(), 1402 holder) {} 1403 1404 void SetAndCopyParentChain(ArenaAllocator* allocator, HEnvironment* parent) { 1405 if (parent_ != nullptr) { 1406 parent_->SetAndCopyParentChain(allocator, parent); 1407 } else { 1408 parent_ = new (allocator) HEnvironment(allocator, *parent, holder_); 1409 parent_->CopyFrom(parent); 1410 if (parent->GetParent() != nullptr) { 1411 parent_->SetAndCopyParentChain(allocator, parent->GetParent()); 1412 } 1413 } 1414 } 1415 1416 void CopyFrom(const GrowableArray<HInstruction*>& locals); 1417 void CopyFrom(HEnvironment* environment); 1418 1419 // Copy from `env`. If it's a loop phi for `loop_header`, copy the first 1420 // input to the loop phi instead. This is for inserting instructions that 1421 // require an environment (like HDeoptimization) in the loop pre-header. 1422 void CopyFromWithLoopPhiAdjustment(HEnvironment* env, HBasicBlock* loop_header); 1423 1424 void SetRawEnvAt(size_t index, HInstruction* instruction) { 1425 vregs_.Put(index, HUserRecord<HEnvironment*>(instruction)); 1426 } 1427 1428 HInstruction* GetInstructionAt(size_t index) const { 1429 return vregs_.Get(index).GetInstruction(); 1430 } 1431 1432 void RemoveAsUserOfInput(size_t index) const; 1433 1434 size_t Size() const { return vregs_.Size(); } 1435 1436 HEnvironment* GetParent() const { return parent_; } 1437 1438 void SetLocationAt(size_t index, Location location) { 1439 locations_.Put(index, location); 1440 } 1441 1442 Location GetLocationAt(size_t index) const { 1443 return locations_.Get(index); 1444 } 1445 1446 uint32_t GetDexPc() const { 1447 return dex_pc_; 1448 } 1449 1450 uint32_t GetMethodIdx() const { 1451 return method_idx_; 1452 } 1453 1454 InvokeType GetInvokeType() const { 1455 return invoke_type_; 1456 } 1457 1458 const DexFile& GetDexFile() const { 1459 return dex_file_; 1460 } 1461 1462 HInstruction* GetHolder() const { 1463 return holder_; 1464 } 1465 1466 private: 1467 // Record instructions' use entries of this environment for constant-time removal. 1468 // It should only be called by HInstruction when a new environment use is added. 1469 void RecordEnvUse(HUseListNode<HEnvironment*>* env_use) { 1470 DCHECK(env_use->GetUser() == this); 1471 size_t index = env_use->GetIndex(); 1472 vregs_.Put(index, HUserRecord<HEnvironment*>(vregs_.Get(index), env_use)); 1473 } 1474 1475 GrowableArray<HUserRecord<HEnvironment*> > vregs_; 1476 GrowableArray<Location> locations_; 1477 HEnvironment* parent_; 1478 const DexFile& dex_file_; 1479 const uint32_t method_idx_; 1480 const uint32_t dex_pc_; 1481 const InvokeType invoke_type_; 1482 1483 // The instruction that holds this environment. 1484 HInstruction* const holder_; 1485 1486 friend class HInstruction; 1487 1488 DISALLOW_COPY_AND_ASSIGN(HEnvironment); 1489}; 1490 1491class ReferenceTypeInfo : ValueObject { 1492 public: 1493 typedef Handle<mirror::Class> TypeHandle; 1494 1495 static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact) { 1496 // The constructor will check that the type_handle is valid. 1497 return ReferenceTypeInfo(type_handle, is_exact); 1498 } 1499 1500 static ReferenceTypeInfo CreateInvalid() { return ReferenceTypeInfo(); } 1501 1502 static bool IsValidHandle(TypeHandle handle) SHARED_REQUIRES(Locks::mutator_lock_) { 1503 return handle.GetReference() != nullptr; 1504 } 1505 1506 bool IsValid() const SHARED_REQUIRES(Locks::mutator_lock_) { 1507 return IsValidHandle(type_handle_); 1508 } 1509 bool IsExact() const { return is_exact_; } 1510 1511 bool IsObjectClass() const SHARED_REQUIRES(Locks::mutator_lock_) { 1512 DCHECK(IsValid()); 1513 return GetTypeHandle()->IsObjectClass(); 1514 } 1515 bool IsInterface() const SHARED_REQUIRES(Locks::mutator_lock_) { 1516 DCHECK(IsValid()); 1517 return GetTypeHandle()->IsInterface(); 1518 } 1519 1520 Handle<mirror::Class> GetTypeHandle() const { return type_handle_; } 1521 1522 bool IsSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { 1523 DCHECK(IsValid()); 1524 DCHECK(rti.IsValid()); 1525 return GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get()); 1526 } 1527 1528 // Returns true if the type information provide the same amount of details. 1529 // Note that it does not mean that the instructions have the same actual type 1530 // (because the type can be the result of a merge). 1531 bool IsEqual(ReferenceTypeInfo rti) SHARED_REQUIRES(Locks::mutator_lock_) { 1532 if (!IsValid() && !rti.IsValid()) { 1533 // Invalid types are equal. 1534 return true; 1535 } 1536 if (!IsValid() || !rti.IsValid()) { 1537 // One is valid, the other not. 1538 return false; 1539 } 1540 return IsExact() == rti.IsExact() 1541 && GetTypeHandle().Get() == rti.GetTypeHandle().Get(); 1542 } 1543 1544 private: 1545 ReferenceTypeInfo(); 1546 ReferenceTypeInfo(TypeHandle type_handle, bool is_exact); 1547 1548 // The class of the object. 1549 TypeHandle type_handle_; 1550 // Whether or not the type is exact or a superclass of the actual type. 1551 // Whether or not we have any information about this type. 1552 bool is_exact_; 1553}; 1554 1555std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs); 1556 1557class HInstruction : public ArenaObject<kArenaAllocMisc> { 1558 public: 1559 explicit HInstruction(SideEffects side_effects) 1560 : previous_(nullptr), 1561 next_(nullptr), 1562 block_(nullptr), 1563 id_(-1), 1564 ssa_index_(-1), 1565 environment_(nullptr), 1566 locations_(nullptr), 1567 live_interval_(nullptr), 1568 lifetime_position_(kNoLifetime), 1569 side_effects_(side_effects), 1570 reference_type_info_(ReferenceTypeInfo::CreateInvalid()) {} 1571 1572 virtual ~HInstruction() {} 1573 1574#define DECLARE_KIND(type, super) k##type, 1575 enum InstructionKind { 1576 FOR_EACH_INSTRUCTION(DECLARE_KIND) 1577 }; 1578#undef DECLARE_KIND 1579 1580 HInstruction* GetNext() const { return next_; } 1581 HInstruction* GetPrevious() const { return previous_; } 1582 1583 HInstruction* GetNextDisregardingMoves() const; 1584 HInstruction* GetPreviousDisregardingMoves() const; 1585 1586 HBasicBlock* GetBlock() const { return block_; } 1587 ArenaAllocator* GetArena() const { return block_->GetGraph()->GetArena(); } 1588 void SetBlock(HBasicBlock* block) { block_ = block; } 1589 bool IsInBlock() const { return block_ != nullptr; } 1590 bool IsInLoop() const { return block_->IsInLoop(); } 1591 bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); } 1592 1593 virtual size_t InputCount() const = 0; 1594 HInstruction* InputAt(size_t i) const { return InputRecordAt(i).GetInstruction(); } 1595 1596 virtual void Accept(HGraphVisitor* visitor) = 0; 1597 virtual const char* DebugName() const = 0; 1598 1599 virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; } 1600 void SetRawInputAt(size_t index, HInstruction* input) { 1601 SetRawInputRecordAt(index, HUserRecord<HInstruction*>(input)); 1602 } 1603 1604 virtual bool NeedsEnvironment() const { return false; } 1605 virtual uint32_t GetDexPc() const { 1606 LOG(FATAL) << "GetDexPc() cannot be called on an instruction that" 1607 " does not need an environment"; 1608 UNREACHABLE(); 1609 } 1610 virtual bool IsControlFlow() const { return false; } 1611 virtual bool CanThrow() const { return false; } 1612 1613 bool DoesAnyWrite() const { return side_effects_.DoesAnyWrite(); } 1614 1615 // Does not apply for all instructions, but having this at top level greatly 1616 // simplifies the null check elimination. 1617 // TODO: Consider merging can_be_null into ReferenceTypeInfo. 1618 virtual bool CanBeNull() const { 1619 DCHECK_EQ(GetType(), Primitive::kPrimNot) << "CanBeNull only applies to reference types"; 1620 return true; 1621 } 1622 1623 virtual bool CanDoImplicitNullCheckOn(HInstruction* obj) const { 1624 UNUSED(obj); 1625 return false; 1626 } 1627 1628 void SetReferenceTypeInfo(ReferenceTypeInfo rti); 1629 1630 ReferenceTypeInfo GetReferenceTypeInfo() const { 1631 DCHECK_EQ(GetType(), Primitive::kPrimNot); 1632 return reference_type_info_; 1633 } 1634 1635 void AddUseAt(HInstruction* user, size_t index) { 1636 DCHECK(user != nullptr); 1637 HUseListNode<HInstruction*>* use = 1638 uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); 1639 user->SetRawInputRecordAt(index, HUserRecord<HInstruction*>(user->InputRecordAt(index), use)); 1640 } 1641 1642 void AddEnvUseAt(HEnvironment* user, size_t index) { 1643 DCHECK(user != nullptr); 1644 HUseListNode<HEnvironment*>* env_use = 1645 env_uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); 1646 user->RecordEnvUse(env_use); 1647 } 1648 1649 void RemoveAsUserOfInput(size_t input) { 1650 HUserRecord<HInstruction*> input_use = InputRecordAt(input); 1651 input_use.GetInstruction()->uses_.Remove(input_use.GetUseNode()); 1652 } 1653 1654 const HUseList<HInstruction*>& GetUses() const { return uses_; } 1655 const HUseList<HEnvironment*>& GetEnvUses() const { return env_uses_; } 1656 1657 bool HasUses() const { return !uses_.IsEmpty() || !env_uses_.IsEmpty(); } 1658 bool HasEnvironmentUses() const { return !env_uses_.IsEmpty(); } 1659 bool HasNonEnvironmentUses() const { return !uses_.IsEmpty(); } 1660 bool HasOnlyOneNonEnvironmentUse() const { 1661 return !HasEnvironmentUses() && GetUses().HasOnlyOneUse(); 1662 } 1663 1664 // Does this instruction strictly dominate `other_instruction`? 1665 // Returns false if this instruction and `other_instruction` are the same. 1666 // Aborts if this instruction and `other_instruction` are both phis. 1667 bool StrictlyDominates(HInstruction* other_instruction) const; 1668 1669 int GetId() const { return id_; } 1670 void SetId(int id) { id_ = id; } 1671 1672 int GetSsaIndex() const { return ssa_index_; } 1673 void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; } 1674 bool HasSsaIndex() const { return ssa_index_ != -1; } 1675 1676 bool HasEnvironment() const { return environment_ != nullptr; } 1677 HEnvironment* GetEnvironment() const { return environment_; } 1678 // Set the `environment_` field. Raw because this method does not 1679 // update the uses lists. 1680 void SetRawEnvironment(HEnvironment* environment) { 1681 DCHECK(environment_ == nullptr); 1682 DCHECK_EQ(environment->GetHolder(), this); 1683 environment_ = environment; 1684 } 1685 1686 // Set the environment of this instruction, copying it from `environment`. While 1687 // copying, the uses lists are being updated. 1688 void CopyEnvironmentFrom(HEnvironment* environment) { 1689 DCHECK(environment_ == nullptr); 1690 ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena(); 1691 environment_ = new (allocator) HEnvironment(allocator, *environment, this); 1692 environment_->CopyFrom(environment); 1693 if (environment->GetParent() != nullptr) { 1694 environment_->SetAndCopyParentChain(allocator, environment->GetParent()); 1695 } 1696 } 1697 1698 void CopyEnvironmentFromWithLoopPhiAdjustment(HEnvironment* environment, 1699 HBasicBlock* block) { 1700 DCHECK(environment_ == nullptr); 1701 ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena(); 1702 environment_ = new (allocator) HEnvironment(allocator, *environment, this); 1703 environment_->CopyFromWithLoopPhiAdjustment(environment, block); 1704 if (environment->GetParent() != nullptr) { 1705 environment_->SetAndCopyParentChain(allocator, environment->GetParent()); 1706 } 1707 } 1708 1709 // Returns the number of entries in the environment. Typically, that is the 1710 // number of dex registers in a method. It could be more in case of inlining. 1711 size_t EnvironmentSize() const; 1712 1713 LocationSummary* GetLocations() const { return locations_; } 1714 void SetLocations(LocationSummary* locations) { locations_ = locations; } 1715 1716 void ReplaceWith(HInstruction* instruction); 1717 void ReplaceInput(HInstruction* replacement, size_t index); 1718 1719 // This is almost the same as doing `ReplaceWith()`. But in this helper, the 1720 // uses of this instruction by `other` are *not* updated. 1721 void ReplaceWithExceptInReplacementAtIndex(HInstruction* other, size_t use_index) { 1722 ReplaceWith(other); 1723 other->ReplaceInput(this, use_index); 1724 } 1725 1726 // Move `this` instruction before `cursor`. 1727 void MoveBefore(HInstruction* cursor); 1728 1729#define INSTRUCTION_TYPE_CHECK(type, super) \ 1730 bool Is##type() const { return (As##type() != nullptr); } \ 1731 virtual const H##type* As##type() const { return nullptr; } \ 1732 virtual H##type* As##type() { return nullptr; } 1733 1734 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 1735#undef INSTRUCTION_TYPE_CHECK 1736 1737 // Returns whether the instruction can be moved within the graph. 1738 virtual bool CanBeMoved() const { return false; } 1739 1740 // Returns whether the two instructions are of the same kind. 1741 virtual bool InstructionTypeEquals(HInstruction* other) const { 1742 UNUSED(other); 1743 return false; 1744 } 1745 1746 // Returns whether any data encoded in the two instructions is equal. 1747 // This method does not look at the inputs. Both instructions must be 1748 // of the same type, otherwise the method has undefined behavior. 1749 virtual bool InstructionDataEquals(HInstruction* other) const { 1750 UNUSED(other); 1751 return false; 1752 } 1753 1754 // Returns whether two instructions are equal, that is: 1755 // 1) They have the same type and contain the same data (InstructionDataEquals). 1756 // 2) Their inputs are identical. 1757 bool Equals(HInstruction* other) const; 1758 1759 virtual InstructionKind GetKind() const = 0; 1760 1761 virtual size_t ComputeHashCode() const { 1762 size_t result = GetKind(); 1763 for (size_t i = 0, e = InputCount(); i < e; ++i) { 1764 result = (result * 31) + InputAt(i)->GetId(); 1765 } 1766 return result; 1767 } 1768 1769 SideEffects GetSideEffects() const { return side_effects_; } 1770 1771 size_t GetLifetimePosition() const { return lifetime_position_; } 1772 void SetLifetimePosition(size_t position) { lifetime_position_ = position; } 1773 LiveInterval* GetLiveInterval() const { return live_interval_; } 1774 void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; } 1775 bool HasLiveInterval() const { return live_interval_ != nullptr; } 1776 1777 bool IsSuspendCheckEntry() const { return IsSuspendCheck() && GetBlock()->IsEntryBlock(); } 1778 1779 // Returns whether the code generation of the instruction will require to have access 1780 // to the current method. Such instructions are: 1781 // (1): Instructions that require an environment, as calling the runtime requires 1782 // to walk the stack and have the current method stored at a specific stack address. 1783 // (2): Object literals like classes and strings, that are loaded from the dex cache 1784 // fields of the current method. 1785 bool NeedsCurrentMethod() const { 1786 return NeedsEnvironment() || IsLoadClass() || IsLoadString(); 1787 } 1788 1789 virtual bool NeedsDexCache() const { return false; } 1790 1791 // Does this instruction have any use in an environment before 1792 // control flow hits 'other'? 1793 bool HasAnyEnvironmentUseBefore(HInstruction* other); 1794 1795 // Remove all references to environment uses of this instruction. 1796 // The caller must ensure that this is safe to do. 1797 void RemoveEnvironmentUsers(); 1798 1799 protected: 1800 virtual const HUserRecord<HInstruction*> InputRecordAt(size_t i) const = 0; 1801 virtual void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) = 0; 1802 1803 private: 1804 void RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use_node) { env_uses_.Remove(use_node); } 1805 1806 HInstruction* previous_; 1807 HInstruction* next_; 1808 HBasicBlock* block_; 1809 1810 // An instruction gets an id when it is added to the graph. 1811 // It reflects creation order. A negative id means the instruction 1812 // has not been added to the graph. 1813 int id_; 1814 1815 // When doing liveness analysis, instructions that have uses get an SSA index. 1816 int ssa_index_; 1817 1818 // List of instructions that have this instruction as input. 1819 HUseList<HInstruction*> uses_; 1820 1821 // List of environments that contain this instruction. 1822 HUseList<HEnvironment*> env_uses_; 1823 1824 // The environment associated with this instruction. Not null if the instruction 1825 // might jump out of the method. 1826 HEnvironment* environment_; 1827 1828 // Set by the code generator. 1829 LocationSummary* locations_; 1830 1831 // Set by the liveness analysis. 1832 LiveInterval* live_interval_; 1833 1834 // Set by the liveness analysis, this is the position in a linear 1835 // order of blocks where this instruction's live interval start. 1836 size_t lifetime_position_; 1837 1838 const SideEffects side_effects_; 1839 1840 // TODO: for primitive types this should be marked as invalid. 1841 ReferenceTypeInfo reference_type_info_; 1842 1843 friend class GraphChecker; 1844 friend class HBasicBlock; 1845 friend class HEnvironment; 1846 friend class HGraph; 1847 friend class HInstructionList; 1848 1849 DISALLOW_COPY_AND_ASSIGN(HInstruction); 1850}; 1851std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs); 1852 1853class HInputIterator : public ValueObject { 1854 public: 1855 explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {} 1856 1857 bool Done() const { return index_ == instruction_->InputCount(); } 1858 HInstruction* Current() const { return instruction_->InputAt(index_); } 1859 void Advance() { index_++; } 1860 1861 private: 1862 HInstruction* instruction_; 1863 size_t index_; 1864 1865 DISALLOW_COPY_AND_ASSIGN(HInputIterator); 1866}; 1867 1868class HInstructionIterator : public ValueObject { 1869 public: 1870 explicit HInstructionIterator(const HInstructionList& instructions) 1871 : instruction_(instructions.first_instruction_) { 1872 next_ = Done() ? nullptr : instruction_->GetNext(); 1873 } 1874 1875 bool Done() const { return instruction_ == nullptr; } 1876 HInstruction* Current() const { return instruction_; } 1877 void Advance() { 1878 instruction_ = next_; 1879 next_ = Done() ? nullptr : instruction_->GetNext(); 1880 } 1881 1882 private: 1883 HInstruction* instruction_; 1884 HInstruction* next_; 1885 1886 DISALLOW_COPY_AND_ASSIGN(HInstructionIterator); 1887}; 1888 1889class HBackwardInstructionIterator : public ValueObject { 1890 public: 1891 explicit HBackwardInstructionIterator(const HInstructionList& instructions) 1892 : instruction_(instructions.last_instruction_) { 1893 next_ = Done() ? nullptr : instruction_->GetPrevious(); 1894 } 1895 1896 bool Done() const { return instruction_ == nullptr; } 1897 HInstruction* Current() const { return instruction_; } 1898 void Advance() { 1899 instruction_ = next_; 1900 next_ = Done() ? nullptr : instruction_->GetPrevious(); 1901 } 1902 1903 private: 1904 HInstruction* instruction_; 1905 HInstruction* next_; 1906 1907 DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator); 1908}; 1909 1910// An embedded container with N elements of type T. Used (with partial 1911// specialization for N=0) because embedded arrays cannot have size 0. 1912template<typename T, intptr_t N> 1913class EmbeddedArray { 1914 public: 1915 EmbeddedArray() : elements_() {} 1916 1917 intptr_t GetLength() const { return N; } 1918 1919 const T& operator[](intptr_t i) const { 1920 DCHECK_LT(i, GetLength()); 1921 return elements_[i]; 1922 } 1923 1924 T& operator[](intptr_t i) { 1925 DCHECK_LT(i, GetLength()); 1926 return elements_[i]; 1927 } 1928 1929 const T& At(intptr_t i) const { 1930 return (*this)[i]; 1931 } 1932 1933 void SetAt(intptr_t i, const T& val) { 1934 (*this)[i] = val; 1935 } 1936 1937 private: 1938 T elements_[N]; 1939}; 1940 1941template<typename T> 1942class EmbeddedArray<T, 0> { 1943 public: 1944 intptr_t length() const { return 0; } 1945 const T& operator[](intptr_t i) const { 1946 UNUSED(i); 1947 LOG(FATAL) << "Unreachable"; 1948 UNREACHABLE(); 1949 } 1950 T& operator[](intptr_t i) { 1951 UNUSED(i); 1952 LOG(FATAL) << "Unreachable"; 1953 UNREACHABLE(); 1954 } 1955}; 1956 1957template<intptr_t N> 1958class HTemplateInstruction: public HInstruction { 1959 public: 1960 HTemplateInstruction<N>(SideEffects side_effects) 1961 : HInstruction(side_effects), inputs_() {} 1962 virtual ~HTemplateInstruction() {} 1963 1964 size_t InputCount() const OVERRIDE { return N; } 1965 1966 protected: 1967 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_[i]; } 1968 1969 void SetRawInputRecordAt(size_t i, const HUserRecord<HInstruction*>& input) OVERRIDE { 1970 inputs_[i] = input; 1971 } 1972 1973 private: 1974 EmbeddedArray<HUserRecord<HInstruction*>, N> inputs_; 1975 1976 friend class SsaBuilder; 1977}; 1978 1979template<intptr_t N> 1980class HExpression : public HTemplateInstruction<N> { 1981 public: 1982 HExpression<N>(Primitive::Type type, SideEffects side_effects) 1983 : HTemplateInstruction<N>(side_effects), type_(type) {} 1984 virtual ~HExpression() {} 1985 1986 Primitive::Type GetType() const OVERRIDE { return type_; } 1987 1988 protected: 1989 Primitive::Type type_; 1990}; 1991 1992// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow 1993// instruction that branches to the exit block. 1994class HReturnVoid : public HTemplateInstruction<0> { 1995 public: 1996 HReturnVoid() : HTemplateInstruction(SideEffects::None()) {} 1997 1998 bool IsControlFlow() const OVERRIDE { return true; } 1999 2000 DECLARE_INSTRUCTION(ReturnVoid); 2001 2002 private: 2003 DISALLOW_COPY_AND_ASSIGN(HReturnVoid); 2004}; 2005 2006// Represents dex's RETURN opcodes. A HReturn is a control flow 2007// instruction that branches to the exit block. 2008class HReturn : public HTemplateInstruction<1> { 2009 public: 2010 explicit HReturn(HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 2011 SetRawInputAt(0, value); 2012 } 2013 2014 bool IsControlFlow() const OVERRIDE { return true; } 2015 2016 DECLARE_INSTRUCTION(Return); 2017 2018 private: 2019 DISALLOW_COPY_AND_ASSIGN(HReturn); 2020}; 2021 2022// The exit instruction is the only instruction of the exit block. 2023// Instructions aborting the method (HThrow and HReturn) must branch to the 2024// exit block. 2025class HExit : public HTemplateInstruction<0> { 2026 public: 2027 HExit() : HTemplateInstruction(SideEffects::None()) {} 2028 2029 bool IsControlFlow() const OVERRIDE { return true; } 2030 2031 DECLARE_INSTRUCTION(Exit); 2032 2033 private: 2034 DISALLOW_COPY_AND_ASSIGN(HExit); 2035}; 2036 2037// Jumps from one block to another. 2038class HGoto : public HTemplateInstruction<0> { 2039 public: 2040 HGoto() : HTemplateInstruction(SideEffects::None()) {} 2041 2042 bool IsControlFlow() const OVERRIDE { return true; } 2043 2044 HBasicBlock* GetSuccessor() const { 2045 return GetBlock()->GetSingleSuccessor(); 2046 } 2047 2048 DECLARE_INSTRUCTION(Goto); 2049 2050 private: 2051 DISALLOW_COPY_AND_ASSIGN(HGoto); 2052}; 2053 2054class HConstant : public HExpression<0> { 2055 public: 2056 explicit HConstant(Primitive::Type type) : HExpression(type, SideEffects::None()) {} 2057 2058 bool CanBeMoved() const OVERRIDE { return true; } 2059 2060 virtual bool IsMinusOne() const { return false; } 2061 virtual bool IsZero() const { return false; } 2062 virtual bool IsOne() const { return false; } 2063 2064 DECLARE_INSTRUCTION(Constant); 2065 2066 private: 2067 DISALLOW_COPY_AND_ASSIGN(HConstant); 2068}; 2069 2070class HNullConstant : public HConstant { 2071 public: 2072 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2073 return true; 2074 } 2075 2076 size_t ComputeHashCode() const OVERRIDE { return 0; } 2077 2078 DECLARE_INSTRUCTION(NullConstant); 2079 2080 private: 2081 HNullConstant() : HConstant(Primitive::kPrimNot) {} 2082 2083 friend class HGraph; 2084 DISALLOW_COPY_AND_ASSIGN(HNullConstant); 2085}; 2086 2087// Constants of the type int. Those can be from Dex instructions, or 2088// synthesized (for example with the if-eqz instruction). 2089class HIntConstant : public HConstant { 2090 public: 2091 int32_t GetValue() const { return value_; } 2092 2093 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2094 DCHECK(other->IsIntConstant()); 2095 return other->AsIntConstant()->value_ == value_; 2096 } 2097 2098 size_t ComputeHashCode() const OVERRIDE { return GetValue(); } 2099 2100 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2101 bool IsZero() const OVERRIDE { return GetValue() == 0; } 2102 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2103 2104 DECLARE_INSTRUCTION(IntConstant); 2105 2106 private: 2107 explicit HIntConstant(int32_t value) : HConstant(Primitive::kPrimInt), value_(value) {} 2108 explicit HIntConstant(bool value) : HConstant(Primitive::kPrimInt), value_(value ? 1 : 0) {} 2109 2110 const int32_t value_; 2111 2112 friend class HGraph; 2113 ART_FRIEND_TEST(GraphTest, InsertInstructionBefore); 2114 ART_FRIEND_TYPED_TEST(ParallelMoveTest, ConstantLast); 2115 DISALLOW_COPY_AND_ASSIGN(HIntConstant); 2116}; 2117 2118class HLongConstant : public HConstant { 2119 public: 2120 int64_t GetValue() const { return value_; } 2121 2122 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2123 DCHECK(other->IsLongConstant()); 2124 return other->AsLongConstant()->value_ == value_; 2125 } 2126 2127 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2128 2129 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2130 bool IsZero() const OVERRIDE { return GetValue() == 0; } 2131 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2132 2133 DECLARE_INSTRUCTION(LongConstant); 2134 2135 private: 2136 explicit HLongConstant(int64_t value) : HConstant(Primitive::kPrimLong), value_(value) {} 2137 2138 const int64_t value_; 2139 2140 friend class HGraph; 2141 DISALLOW_COPY_AND_ASSIGN(HLongConstant); 2142}; 2143 2144// Conditional branch. A block ending with an HIf instruction must have 2145// two successors. 2146class HIf : public HTemplateInstruction<1> { 2147 public: 2148 explicit HIf(HInstruction* input) : HTemplateInstruction(SideEffects::None()) { 2149 SetRawInputAt(0, input); 2150 } 2151 2152 bool IsControlFlow() const OVERRIDE { return true; } 2153 2154 HBasicBlock* IfTrueSuccessor() const { 2155 return GetBlock()->GetSuccessors().Get(0); 2156 } 2157 2158 HBasicBlock* IfFalseSuccessor() const { 2159 return GetBlock()->GetSuccessors().Get(1); 2160 } 2161 2162 DECLARE_INSTRUCTION(If); 2163 2164 private: 2165 DISALLOW_COPY_AND_ASSIGN(HIf); 2166}; 2167 2168 2169// Abstract instruction which marks the beginning and/or end of a try block and 2170// links it to the respective exception handlers. Behaves the same as a Goto in 2171// non-exceptional control flow. 2172// Normal-flow successor is stored at index zero, exception handlers under 2173// higher indices in no particular order. 2174class HTryBoundary : public HTemplateInstruction<0> { 2175 public: 2176 enum BoundaryKind { 2177 kEntry, 2178 kExit, 2179 }; 2180 2181 explicit HTryBoundary(BoundaryKind kind) 2182 : HTemplateInstruction(SideEffects::None()), kind_(kind) {} 2183 2184 bool IsControlFlow() const OVERRIDE { return true; } 2185 2186 // Returns the block's non-exceptional successor (index zero). 2187 HBasicBlock* GetNormalFlowSuccessor() const { return GetBlock()->GetSuccessors().Get(0); } 2188 2189 // Returns whether `handler` is among its exception handlers (non-zero index 2190 // successors). 2191 bool HasExceptionHandler(const HBasicBlock& handler) const { 2192 DCHECK(handler.IsCatchBlock()); 2193 return GetBlock()->GetSuccessors().Contains( 2194 const_cast<HBasicBlock*>(&handler), /* start_from */ 1); 2195 } 2196 2197 // If not present already, adds `handler` to its block's list of exception 2198 // handlers. 2199 void AddExceptionHandler(HBasicBlock* handler) { 2200 if (!HasExceptionHandler(*handler)) { 2201 GetBlock()->AddSuccessor(handler); 2202 } 2203 } 2204 2205 bool IsEntry() const { return kind_ == BoundaryKind::kEntry; } 2206 2207 bool HasSameExceptionHandlersAs(const HTryBoundary& other) const; 2208 2209 DECLARE_INSTRUCTION(TryBoundary); 2210 2211 private: 2212 const BoundaryKind kind_; 2213 2214 DISALLOW_COPY_AND_ASSIGN(HTryBoundary); 2215}; 2216 2217// Iterator over exception handlers of a given HTryBoundary, i.e. over 2218// exceptional successors of its basic block. 2219class HExceptionHandlerIterator : public ValueObject { 2220 public: 2221 explicit HExceptionHandlerIterator(const HTryBoundary& try_boundary) 2222 : block_(*try_boundary.GetBlock()), index_(block_.NumberOfNormalSuccessors()) {} 2223 2224 bool Done() const { return index_ == block_.GetSuccessors().Size(); } 2225 HBasicBlock* Current() const { return block_.GetSuccessors().Get(index_); } 2226 size_t CurrentSuccessorIndex() const { return index_; } 2227 void Advance() { ++index_; } 2228 2229 private: 2230 const HBasicBlock& block_; 2231 size_t index_; 2232 2233 DISALLOW_COPY_AND_ASSIGN(HExceptionHandlerIterator); 2234}; 2235 2236// Deoptimize to interpreter, upon checking a condition. 2237class HDeoptimize : public HTemplateInstruction<1> { 2238 public: 2239 HDeoptimize(HInstruction* cond, uint32_t dex_pc) 2240 : HTemplateInstruction(SideEffects::None()), 2241 dex_pc_(dex_pc) { 2242 SetRawInputAt(0, cond); 2243 } 2244 2245 bool NeedsEnvironment() const OVERRIDE { return true; } 2246 bool CanThrow() const OVERRIDE { return true; } 2247 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2248 2249 DECLARE_INSTRUCTION(Deoptimize); 2250 2251 private: 2252 uint32_t dex_pc_; 2253 2254 DISALLOW_COPY_AND_ASSIGN(HDeoptimize); 2255}; 2256 2257// Represents the ArtMethod that was passed as a first argument to 2258// the method. It is used by instructions that depend on it, like 2259// instructions that work with the dex cache. 2260class HCurrentMethod : public HExpression<0> { 2261 public: 2262 explicit HCurrentMethod(Primitive::Type type) : HExpression(type, SideEffects::None()) {} 2263 2264 DECLARE_INSTRUCTION(CurrentMethod); 2265 2266 private: 2267 DISALLOW_COPY_AND_ASSIGN(HCurrentMethod); 2268}; 2269 2270class HUnaryOperation : public HExpression<1> { 2271 public: 2272 HUnaryOperation(Primitive::Type result_type, HInstruction* input) 2273 : HExpression(result_type, SideEffects::None()) { 2274 SetRawInputAt(0, input); 2275 } 2276 2277 HInstruction* GetInput() const { return InputAt(0); } 2278 Primitive::Type GetResultType() const { return GetType(); } 2279 2280 bool CanBeMoved() const OVERRIDE { return true; } 2281 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2282 UNUSED(other); 2283 return true; 2284 } 2285 2286 // Try to statically evaluate `operation` and return a HConstant 2287 // containing the result of this evaluation. If `operation` cannot 2288 // be evaluated as a constant, return null. 2289 HConstant* TryStaticEvaluation() const; 2290 2291 // Apply this operation to `x`. 2292 virtual HConstant* Evaluate(HIntConstant* x) const = 0; 2293 virtual HConstant* Evaluate(HLongConstant* x) const = 0; 2294 2295 DECLARE_INSTRUCTION(UnaryOperation); 2296 2297 private: 2298 DISALLOW_COPY_AND_ASSIGN(HUnaryOperation); 2299}; 2300 2301class HBinaryOperation : public HExpression<2> { 2302 public: 2303 HBinaryOperation(Primitive::Type result_type, 2304 HInstruction* left, 2305 HInstruction* right) : HExpression(result_type, SideEffects::None()) { 2306 SetRawInputAt(0, left); 2307 SetRawInputAt(1, right); 2308 } 2309 2310 HInstruction* GetLeft() const { return InputAt(0); } 2311 HInstruction* GetRight() const { return InputAt(1); } 2312 Primitive::Type GetResultType() const { return GetType(); } 2313 2314 virtual bool IsCommutative() const { return false; } 2315 2316 // Put constant on the right. 2317 // Returns whether order is changed. 2318 bool OrderInputsWithConstantOnTheRight() { 2319 HInstruction* left = InputAt(0); 2320 HInstruction* right = InputAt(1); 2321 if (left->IsConstant() && !right->IsConstant()) { 2322 ReplaceInput(right, 0); 2323 ReplaceInput(left, 1); 2324 return true; 2325 } 2326 return false; 2327 } 2328 2329 // Order inputs by instruction id, but favor constant on the right side. 2330 // This helps GVN for commutative ops. 2331 void OrderInputs() { 2332 DCHECK(IsCommutative()); 2333 HInstruction* left = InputAt(0); 2334 HInstruction* right = InputAt(1); 2335 if (left == right || (!left->IsConstant() && right->IsConstant())) { 2336 return; 2337 } 2338 if (OrderInputsWithConstantOnTheRight()) { 2339 return; 2340 } 2341 // Order according to instruction id. 2342 if (left->GetId() > right->GetId()) { 2343 ReplaceInput(right, 0); 2344 ReplaceInput(left, 1); 2345 } 2346 } 2347 2348 bool CanBeMoved() const OVERRIDE { return true; } 2349 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2350 UNUSED(other); 2351 return true; 2352 } 2353 2354 // Try to statically evaluate `operation` and return a HConstant 2355 // containing the result of this evaluation. If `operation` cannot 2356 // be evaluated as a constant, return null. 2357 HConstant* TryStaticEvaluation() const; 2358 2359 // Apply this operation to `x` and `y`. 2360 virtual HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const = 0; 2361 virtual HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const = 0; 2362 virtual HConstant* Evaluate(HIntConstant* x ATTRIBUTE_UNUSED, 2363 HLongConstant* y ATTRIBUTE_UNUSED) const { 2364 VLOG(compiler) << DebugName() << " is not defined for the (int, long) case."; 2365 return nullptr; 2366 } 2367 virtual HConstant* Evaluate(HLongConstant* x ATTRIBUTE_UNUSED, 2368 HIntConstant* y ATTRIBUTE_UNUSED) const { 2369 VLOG(compiler) << DebugName() << " is not defined for the (long, int) case."; 2370 return nullptr; 2371 } 2372 2373 // Returns an input that can legally be used as the right input and is 2374 // constant, or null. 2375 HConstant* GetConstantRight() const; 2376 2377 // If `GetConstantRight()` returns one of the input, this returns the other 2378 // one. Otherwise it returns null. 2379 HInstruction* GetLeastConstantLeft() const; 2380 2381 DECLARE_INSTRUCTION(BinaryOperation); 2382 2383 private: 2384 DISALLOW_COPY_AND_ASSIGN(HBinaryOperation); 2385}; 2386 2387// The comparison bias applies for floating point operations and indicates how NaN 2388// comparisons are treated: 2389enum class ComparisonBias { 2390 kNoBias, // bias is not applicable (i.e. for long operation) 2391 kGtBias, // return 1 for NaN comparisons 2392 kLtBias, // return -1 for NaN comparisons 2393}; 2394 2395class HCondition : public HBinaryOperation { 2396 public: 2397 HCondition(HInstruction* first, HInstruction* second) 2398 : HBinaryOperation(Primitive::kPrimBoolean, first, second), 2399 needs_materialization_(true), 2400 bias_(ComparisonBias::kNoBias) {} 2401 2402 bool NeedsMaterialization() const { return needs_materialization_; } 2403 void ClearNeedsMaterialization() { needs_materialization_ = false; } 2404 2405 // For code generation purposes, returns whether this instruction is just before 2406 // `instruction`, and disregard moves in between. 2407 bool IsBeforeWhenDisregardMoves(HInstruction* instruction) const; 2408 2409 DECLARE_INSTRUCTION(Condition); 2410 2411 virtual IfCondition GetCondition() const = 0; 2412 2413 virtual IfCondition GetOppositeCondition() const = 0; 2414 2415 bool IsGtBias() const { return bias_ == ComparisonBias::kGtBias; } 2416 2417 void SetBias(ComparisonBias bias) { bias_ = bias; } 2418 2419 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2420 return bias_ == other->AsCondition()->bias_; 2421 } 2422 2423 bool IsFPConditionTrueIfNaN() const { 2424 DCHECK(Primitive::IsFloatingPointType(InputAt(0)->GetType())); 2425 IfCondition if_cond = GetCondition(); 2426 return IsGtBias() ? ((if_cond == kCondGT) || (if_cond == kCondGE)) : (if_cond == kCondNE); 2427 } 2428 2429 bool IsFPConditionFalseIfNaN() const { 2430 DCHECK(Primitive::IsFloatingPointType(InputAt(0)->GetType())); 2431 IfCondition if_cond = GetCondition(); 2432 return IsGtBias() ? ((if_cond == kCondLT) || (if_cond == kCondLE)) : (if_cond == kCondEQ); 2433 } 2434 2435 private: 2436 // For register allocation purposes, returns whether this instruction needs to be 2437 // materialized (that is, not just be in the processor flags). 2438 bool needs_materialization_; 2439 2440 // Needed if we merge a HCompare into a HCondition. 2441 ComparisonBias bias_; 2442 2443 DISALLOW_COPY_AND_ASSIGN(HCondition); 2444}; 2445 2446// Instruction to check if two inputs are equal to each other. 2447class HEqual : public HCondition { 2448 public: 2449 HEqual(HInstruction* first, HInstruction* second) 2450 : HCondition(first, second) {} 2451 2452 bool IsCommutative() const OVERRIDE { return true; } 2453 2454 template <typename T> bool Compute(T x, T y) const { return x == y; } 2455 2456 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2457 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 2458 } 2459 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2460 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 2461 } 2462 2463 DECLARE_INSTRUCTION(Equal); 2464 2465 IfCondition GetCondition() const OVERRIDE { 2466 return kCondEQ; 2467 } 2468 2469 IfCondition GetOppositeCondition() const OVERRIDE { 2470 return kCondNE; 2471 } 2472 2473 private: 2474 DISALLOW_COPY_AND_ASSIGN(HEqual); 2475}; 2476 2477class HNotEqual : public HCondition { 2478 public: 2479 HNotEqual(HInstruction* first, HInstruction* second) 2480 : HCondition(first, second) {} 2481 2482 bool IsCommutative() const OVERRIDE { return true; } 2483 2484 template <typename T> bool Compute(T x, T y) const { return x != y; } 2485 2486 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2487 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 2488 } 2489 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2490 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 2491 } 2492 2493 DECLARE_INSTRUCTION(NotEqual); 2494 2495 IfCondition GetCondition() const OVERRIDE { 2496 return kCondNE; 2497 } 2498 2499 IfCondition GetOppositeCondition() const OVERRIDE { 2500 return kCondEQ; 2501 } 2502 2503 private: 2504 DISALLOW_COPY_AND_ASSIGN(HNotEqual); 2505}; 2506 2507class HLessThan : public HCondition { 2508 public: 2509 HLessThan(HInstruction* first, HInstruction* second) 2510 : HCondition(first, second) {} 2511 2512 template <typename T> bool Compute(T x, T y) const { return x < y; } 2513 2514 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2515 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 2516 } 2517 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2518 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 2519 } 2520 2521 DECLARE_INSTRUCTION(LessThan); 2522 2523 IfCondition GetCondition() const OVERRIDE { 2524 return kCondLT; 2525 } 2526 2527 IfCondition GetOppositeCondition() const OVERRIDE { 2528 return kCondGE; 2529 } 2530 2531 private: 2532 DISALLOW_COPY_AND_ASSIGN(HLessThan); 2533}; 2534 2535class HLessThanOrEqual : public HCondition { 2536 public: 2537 HLessThanOrEqual(HInstruction* first, HInstruction* second) 2538 : HCondition(first, second) {} 2539 2540 template <typename T> bool Compute(T x, T y) const { return x <= y; } 2541 2542 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2543 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 2544 } 2545 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2546 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 2547 } 2548 2549 DECLARE_INSTRUCTION(LessThanOrEqual); 2550 2551 IfCondition GetCondition() const OVERRIDE { 2552 return kCondLE; 2553 } 2554 2555 IfCondition GetOppositeCondition() const OVERRIDE { 2556 return kCondGT; 2557 } 2558 2559 private: 2560 DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual); 2561}; 2562 2563class HGreaterThan : public HCondition { 2564 public: 2565 HGreaterThan(HInstruction* first, HInstruction* second) 2566 : HCondition(first, second) {} 2567 2568 template <typename T> bool Compute(T x, T y) const { return x > y; } 2569 2570 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2571 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 2572 } 2573 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2574 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 2575 } 2576 2577 DECLARE_INSTRUCTION(GreaterThan); 2578 2579 IfCondition GetCondition() const OVERRIDE { 2580 return kCondGT; 2581 } 2582 2583 IfCondition GetOppositeCondition() const OVERRIDE { 2584 return kCondLE; 2585 } 2586 2587 private: 2588 DISALLOW_COPY_AND_ASSIGN(HGreaterThan); 2589}; 2590 2591class HGreaterThanOrEqual : public HCondition { 2592 public: 2593 HGreaterThanOrEqual(HInstruction* first, HInstruction* second) 2594 : HCondition(first, second) {} 2595 2596 template <typename T> bool Compute(T x, T y) const { return x >= y; } 2597 2598 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2599 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 2600 } 2601 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2602 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 2603 } 2604 2605 DECLARE_INSTRUCTION(GreaterThanOrEqual); 2606 2607 IfCondition GetCondition() const OVERRIDE { 2608 return kCondGE; 2609 } 2610 2611 IfCondition GetOppositeCondition() const OVERRIDE { 2612 return kCondLT; 2613 } 2614 2615 private: 2616 DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual); 2617}; 2618 2619 2620// Instruction to check how two inputs compare to each other. 2621// Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1. 2622class HCompare : public HBinaryOperation { 2623 public: 2624 HCompare(Primitive::Type type, 2625 HInstruction* first, 2626 HInstruction* second, 2627 ComparisonBias bias, 2628 uint32_t dex_pc) 2629 : HBinaryOperation(Primitive::kPrimInt, first, second), bias_(bias), dex_pc_(dex_pc) { 2630 DCHECK_EQ(type, first->GetType()); 2631 DCHECK_EQ(type, second->GetType()); 2632 } 2633 2634 template <typename T> 2635 int32_t Compute(T x, T y) const { return x == y ? 0 : x > y ? 1 : -1; } 2636 2637 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2638 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 2639 } 2640 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2641 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 2642 } 2643 2644 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2645 return bias_ == other->AsCompare()->bias_; 2646 } 2647 2648 ComparisonBias GetBias() const { return bias_; } 2649 2650 bool IsGtBias() { return bias_ == ComparisonBias::kGtBias; } 2651 2652 uint32_t GetDexPc() const { return dex_pc_; } 2653 2654 DECLARE_INSTRUCTION(Compare); 2655 2656 private: 2657 const ComparisonBias bias_; 2658 const uint32_t dex_pc_; 2659 2660 DISALLOW_COPY_AND_ASSIGN(HCompare); 2661}; 2662 2663// A local in the graph. Corresponds to a Dex register. 2664class HLocal : public HTemplateInstruction<0> { 2665 public: 2666 explicit HLocal(uint16_t reg_number) 2667 : HTemplateInstruction(SideEffects::None()), reg_number_(reg_number) {} 2668 2669 DECLARE_INSTRUCTION(Local); 2670 2671 uint16_t GetRegNumber() const { return reg_number_; } 2672 2673 private: 2674 // The Dex register number. 2675 const uint16_t reg_number_; 2676 2677 DISALLOW_COPY_AND_ASSIGN(HLocal); 2678}; 2679 2680// Load a given local. The local is an input of this instruction. 2681class HLoadLocal : public HExpression<1> { 2682 public: 2683 HLoadLocal(HLocal* local, Primitive::Type type) 2684 : HExpression(type, SideEffects::None()) { 2685 SetRawInputAt(0, local); 2686 } 2687 2688 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 2689 2690 DECLARE_INSTRUCTION(LoadLocal); 2691 2692 private: 2693 DISALLOW_COPY_AND_ASSIGN(HLoadLocal); 2694}; 2695 2696// Store a value in a given local. This instruction has two inputs: the value 2697// and the local. 2698class HStoreLocal : public HTemplateInstruction<2> { 2699 public: 2700 HStoreLocal(HLocal* local, HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 2701 SetRawInputAt(0, local); 2702 SetRawInputAt(1, value); 2703 } 2704 2705 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 2706 2707 DECLARE_INSTRUCTION(StoreLocal); 2708 2709 private: 2710 DISALLOW_COPY_AND_ASSIGN(HStoreLocal); 2711}; 2712 2713class HFloatConstant : public HConstant { 2714 public: 2715 float GetValue() const { return value_; } 2716 2717 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2718 DCHECK(other->IsFloatConstant()); 2719 return bit_cast<uint32_t, float>(other->AsFloatConstant()->value_) == 2720 bit_cast<uint32_t, float>(value_); 2721 } 2722 2723 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2724 2725 bool IsMinusOne() const OVERRIDE { 2726 return bit_cast<uint32_t, float>(value_) == bit_cast<uint32_t, float>((-1.0f)); 2727 } 2728 bool IsZero() const OVERRIDE { 2729 return value_ == 0.0f; 2730 } 2731 bool IsOne() const OVERRIDE { 2732 return bit_cast<uint32_t, float>(value_) == bit_cast<uint32_t, float>(1.0f); 2733 } 2734 bool IsNaN() const { 2735 return std::isnan(value_); 2736 } 2737 2738 DECLARE_INSTRUCTION(FloatConstant); 2739 2740 private: 2741 explicit HFloatConstant(float value) : HConstant(Primitive::kPrimFloat), value_(value) {} 2742 explicit HFloatConstant(int32_t value) 2743 : HConstant(Primitive::kPrimFloat), value_(bit_cast<float, int32_t>(value)) {} 2744 2745 const float value_; 2746 2747 // Only the SsaBuilder and HGraph can create floating-point constants. 2748 friend class SsaBuilder; 2749 friend class HGraph; 2750 DISALLOW_COPY_AND_ASSIGN(HFloatConstant); 2751}; 2752 2753class HDoubleConstant : public HConstant { 2754 public: 2755 double GetValue() const { return value_; } 2756 2757 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2758 DCHECK(other->IsDoubleConstant()); 2759 return bit_cast<uint64_t, double>(other->AsDoubleConstant()->value_) == 2760 bit_cast<uint64_t, double>(value_); 2761 } 2762 2763 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2764 2765 bool IsMinusOne() const OVERRIDE { 2766 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>((-1.0)); 2767 } 2768 bool IsZero() const OVERRIDE { 2769 return value_ == 0.0; 2770 } 2771 bool IsOne() const OVERRIDE { 2772 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>(1.0); 2773 } 2774 bool IsNaN() const { 2775 return std::isnan(value_); 2776 } 2777 2778 DECLARE_INSTRUCTION(DoubleConstant); 2779 2780 private: 2781 explicit HDoubleConstant(double value) : HConstant(Primitive::kPrimDouble), value_(value) {} 2782 explicit HDoubleConstant(int64_t value) 2783 : HConstant(Primitive::kPrimDouble), value_(bit_cast<double, int64_t>(value)) {} 2784 2785 const double value_; 2786 2787 // Only the SsaBuilder and HGraph can create floating-point constants. 2788 friend class SsaBuilder; 2789 friend class HGraph; 2790 DISALLOW_COPY_AND_ASSIGN(HDoubleConstant); 2791}; 2792 2793enum class Intrinsics { 2794#define OPTIMIZING_INTRINSICS(Name, IsStatic) k ## Name, 2795#include "intrinsics_list.h" 2796 kNone, 2797 INTRINSICS_LIST(OPTIMIZING_INTRINSICS) 2798#undef INTRINSICS_LIST 2799#undef OPTIMIZING_INTRINSICS 2800}; 2801std::ostream& operator<<(std::ostream& os, const Intrinsics& intrinsic); 2802 2803class HInvoke : public HInstruction { 2804 public: 2805 size_t InputCount() const OVERRIDE { return inputs_.Size(); } 2806 2807 // Runtime needs to walk the stack, so Dex -> Dex calls need to 2808 // know their environment. 2809 bool NeedsEnvironment() const OVERRIDE { return true; } 2810 2811 void SetArgumentAt(size_t index, HInstruction* argument) { 2812 SetRawInputAt(index, argument); 2813 } 2814 2815 // Return the number of arguments. This number can be lower than 2816 // the number of inputs returned by InputCount(), as some invoke 2817 // instructions (e.g. HInvokeStaticOrDirect) can have non-argument 2818 // inputs at the end of their list of inputs. 2819 uint32_t GetNumberOfArguments() const { return number_of_arguments_; } 2820 2821 Primitive::Type GetType() const OVERRIDE { return return_type_; } 2822 2823 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2824 2825 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 2826 const DexFile& GetDexFile() const { return GetEnvironment()->GetDexFile(); } 2827 2828 InvokeType GetOriginalInvokeType() const { return original_invoke_type_; } 2829 2830 Intrinsics GetIntrinsic() const { 2831 return intrinsic_; 2832 } 2833 2834 void SetIntrinsic(Intrinsics intrinsic) { 2835 intrinsic_ = intrinsic; 2836 } 2837 2838 bool IsFromInlinedInvoke() const { 2839 return GetEnvironment()->GetParent() != nullptr; 2840 } 2841 2842 bool CanThrow() const OVERRIDE { return true; } 2843 2844 DECLARE_INSTRUCTION(Invoke); 2845 2846 protected: 2847 HInvoke(ArenaAllocator* arena, 2848 uint32_t number_of_arguments, 2849 uint32_t number_of_other_inputs, 2850 Primitive::Type return_type, 2851 uint32_t dex_pc, 2852 uint32_t dex_method_index, 2853 InvokeType original_invoke_type) 2854 : HInstruction(SideEffects::All()), // assume write/read on all fields/arrays 2855 number_of_arguments_(number_of_arguments), 2856 inputs_(arena, number_of_arguments), 2857 return_type_(return_type), 2858 dex_pc_(dex_pc), 2859 dex_method_index_(dex_method_index), 2860 original_invoke_type_(original_invoke_type), 2861 intrinsic_(Intrinsics::kNone) { 2862 uint32_t number_of_inputs = number_of_arguments + number_of_other_inputs; 2863 inputs_.SetSize(number_of_inputs); 2864 } 2865 2866 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); } 2867 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE { 2868 inputs_.Put(index, input); 2869 } 2870 2871 uint32_t number_of_arguments_; 2872 GrowableArray<HUserRecord<HInstruction*> > inputs_; 2873 const Primitive::Type return_type_; 2874 const uint32_t dex_pc_; 2875 const uint32_t dex_method_index_; 2876 const InvokeType original_invoke_type_; 2877 Intrinsics intrinsic_; 2878 2879 private: 2880 DISALLOW_COPY_AND_ASSIGN(HInvoke); 2881}; 2882 2883class HInvokeStaticOrDirect : public HInvoke { 2884 public: 2885 // Requirements of this method call regarding the class 2886 // initialization (clinit) check of its declaring class. 2887 enum class ClinitCheckRequirement { 2888 kNone, // Class already initialized. 2889 kExplicit, // Static call having explicit clinit check as last input. 2890 kImplicit, // Static call implicitly requiring a clinit check. 2891 }; 2892 2893 HInvokeStaticOrDirect(ArenaAllocator* arena, 2894 uint32_t number_of_arguments, 2895 Primitive::Type return_type, 2896 uint32_t dex_pc, 2897 uint32_t dex_method_index, 2898 bool is_recursive, 2899 int32_t string_init_offset, 2900 InvokeType original_invoke_type, 2901 InvokeType invoke_type, 2902 ClinitCheckRequirement clinit_check_requirement) 2903 : HInvoke(arena, 2904 number_of_arguments, 2905 // There is one extra argument for the HCurrentMethod node, and 2906 // potentially one other if the clinit check is explicit, and one other 2907 // if the method is a string factory. 2908 1u + (clinit_check_requirement == ClinitCheckRequirement::kExplicit ? 1u : 0u) 2909 + (string_init_offset ? 1u : 0u), 2910 return_type, 2911 dex_pc, 2912 dex_method_index, 2913 original_invoke_type), 2914 invoke_type_(invoke_type), 2915 is_recursive_(is_recursive), 2916 clinit_check_requirement_(clinit_check_requirement), 2917 string_init_offset_(string_init_offset) {} 2918 2919 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2920 UNUSED(obj); 2921 // We access the method via the dex cache so we can't do an implicit null check. 2922 // TODO: for intrinsics we can generate implicit null checks. 2923 return false; 2924 } 2925 2926 InvokeType GetInvokeType() const { return invoke_type_; } 2927 bool IsRecursive() const { return is_recursive_; } 2928 bool NeedsDexCache() const OVERRIDE { return !IsRecursive(); } 2929 bool IsStringInit() const { return string_init_offset_ != 0; } 2930 int32_t GetStringInitOffset() const { return string_init_offset_; } 2931 uint32_t GetCurrentMethodInputIndex() const { return GetNumberOfArguments(); } 2932 2933 // Is this instruction a call to a static method? 2934 bool IsStatic() const { 2935 return GetInvokeType() == kStatic; 2936 } 2937 2938 // Remove the art::HLoadClass instruction set as last input by 2939 // art::PrepareForRegisterAllocation::VisitClinitCheck in lieu of 2940 // the initial art::HClinitCheck instruction (only relevant for 2941 // static calls with explicit clinit check). 2942 void RemoveLoadClassAsLastInput() { 2943 DCHECK(IsStaticWithExplicitClinitCheck()); 2944 size_t last_input_index = InputCount() - 1; 2945 HInstruction* last_input = InputAt(last_input_index); 2946 DCHECK(last_input != nullptr); 2947 DCHECK(last_input->IsLoadClass()) << last_input->DebugName(); 2948 RemoveAsUserOfInput(last_input_index); 2949 inputs_.DeleteAt(last_input_index); 2950 clinit_check_requirement_ = ClinitCheckRequirement::kImplicit; 2951 DCHECK(IsStaticWithImplicitClinitCheck()); 2952 } 2953 2954 bool IsStringFactoryFor(HFakeString* str) const { 2955 if (!IsStringInit()) return false; 2956 // +1 for the current method. 2957 if (InputCount() == (number_of_arguments_ + 1)) return false; 2958 return InputAt(InputCount() - 1)->AsFakeString() == str; 2959 } 2960 2961 void RemoveFakeStringArgumentAsLastInput() { 2962 DCHECK(IsStringInit()); 2963 size_t last_input_index = InputCount() - 1; 2964 HInstruction* last_input = InputAt(last_input_index); 2965 DCHECK(last_input != nullptr); 2966 DCHECK(last_input->IsFakeString()) << last_input->DebugName(); 2967 RemoveAsUserOfInput(last_input_index); 2968 inputs_.DeleteAt(last_input_index); 2969 } 2970 2971 // Is this a call to a static method whose declaring class has an 2972 // explicit intialization check in the graph? 2973 bool IsStaticWithExplicitClinitCheck() const { 2974 return IsStatic() && (clinit_check_requirement_ == ClinitCheckRequirement::kExplicit); 2975 } 2976 2977 // Is this a call to a static method whose declaring class has an 2978 // implicit intialization check requirement? 2979 bool IsStaticWithImplicitClinitCheck() const { 2980 return IsStatic() && (clinit_check_requirement_ == ClinitCheckRequirement::kImplicit); 2981 } 2982 2983 DECLARE_INSTRUCTION(InvokeStaticOrDirect); 2984 2985 protected: 2986 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { 2987 const HUserRecord<HInstruction*> input_record = HInvoke::InputRecordAt(i); 2988 if (kIsDebugBuild && IsStaticWithExplicitClinitCheck() && (i == InputCount() - 1)) { 2989 HInstruction* input = input_record.GetInstruction(); 2990 // `input` is the last input of a static invoke marked as having 2991 // an explicit clinit check. It must either be: 2992 // - an art::HClinitCheck instruction, set by art::HGraphBuilder; or 2993 // - an art::HLoadClass instruction, set by art::PrepareForRegisterAllocation. 2994 DCHECK(input != nullptr); 2995 DCHECK(input->IsClinitCheck() || input->IsLoadClass()) << input->DebugName(); 2996 } 2997 return input_record; 2998 } 2999 3000 private: 3001 const InvokeType invoke_type_; 3002 const bool is_recursive_; 3003 ClinitCheckRequirement clinit_check_requirement_; 3004 // Thread entrypoint offset for string init method if this is a string init invoke. 3005 // Note that there are multiple string init methods, each having its own offset. 3006 int32_t string_init_offset_; 3007 3008 DISALLOW_COPY_AND_ASSIGN(HInvokeStaticOrDirect); 3009}; 3010 3011class HInvokeVirtual : public HInvoke { 3012 public: 3013 HInvokeVirtual(ArenaAllocator* arena, 3014 uint32_t number_of_arguments, 3015 Primitive::Type return_type, 3016 uint32_t dex_pc, 3017 uint32_t dex_method_index, 3018 uint32_t vtable_index) 3019 : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index, kVirtual), 3020 vtable_index_(vtable_index) {} 3021 3022 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3023 // TODO: Add implicit null checks in intrinsics. 3024 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 3025 } 3026 3027 uint32_t GetVTableIndex() const { return vtable_index_; } 3028 3029 DECLARE_INSTRUCTION(InvokeVirtual); 3030 3031 private: 3032 const uint32_t vtable_index_; 3033 3034 DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual); 3035}; 3036 3037class HInvokeInterface : public HInvoke { 3038 public: 3039 HInvokeInterface(ArenaAllocator* arena, 3040 uint32_t number_of_arguments, 3041 Primitive::Type return_type, 3042 uint32_t dex_pc, 3043 uint32_t dex_method_index, 3044 uint32_t imt_index) 3045 : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index, kInterface), 3046 imt_index_(imt_index) {} 3047 3048 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3049 // TODO: Add implicit null checks in intrinsics. 3050 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 3051 } 3052 3053 uint32_t GetImtIndex() const { return imt_index_; } 3054 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 3055 3056 DECLARE_INSTRUCTION(InvokeInterface); 3057 3058 private: 3059 const uint32_t imt_index_; 3060 3061 DISALLOW_COPY_AND_ASSIGN(HInvokeInterface); 3062}; 3063 3064class HNewInstance : public HExpression<1> { 3065 public: 3066 HNewInstance(HCurrentMethod* current_method, 3067 uint32_t dex_pc, 3068 uint16_t type_index, 3069 const DexFile& dex_file, 3070 QuickEntrypointEnum entrypoint) 3071 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3072 dex_pc_(dex_pc), 3073 type_index_(type_index), 3074 dex_file_(dex_file), 3075 entrypoint_(entrypoint) { 3076 SetRawInputAt(0, current_method); 3077 } 3078 3079 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3080 uint16_t GetTypeIndex() const { return type_index_; } 3081 const DexFile& GetDexFile() const { return dex_file_; } 3082 3083 // Calls runtime so needs an environment. 3084 bool NeedsEnvironment() const OVERRIDE { return true; } 3085 // It may throw when called on: 3086 // - interfaces 3087 // - abstract/innaccessible/unknown classes 3088 // TODO: optimize when possible. 3089 bool CanThrow() const OVERRIDE { return true; } 3090 3091 bool CanBeNull() const OVERRIDE { return false; } 3092 3093 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 3094 3095 DECLARE_INSTRUCTION(NewInstance); 3096 3097 private: 3098 const uint32_t dex_pc_; 3099 const uint16_t type_index_; 3100 const DexFile& dex_file_; 3101 const QuickEntrypointEnum entrypoint_; 3102 3103 DISALLOW_COPY_AND_ASSIGN(HNewInstance); 3104}; 3105 3106class HNeg : public HUnaryOperation { 3107 public: 3108 explicit HNeg(Primitive::Type result_type, HInstruction* input) 3109 : HUnaryOperation(result_type, input) {} 3110 3111 template <typename T> T Compute(T x) const { return -x; } 3112 3113 HConstant* Evaluate(HIntConstant* x) const OVERRIDE { 3114 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue())); 3115 } 3116 HConstant* Evaluate(HLongConstant* x) const OVERRIDE { 3117 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue())); 3118 } 3119 3120 DECLARE_INSTRUCTION(Neg); 3121 3122 private: 3123 DISALLOW_COPY_AND_ASSIGN(HNeg); 3124}; 3125 3126class HNewArray : public HExpression<2> { 3127 public: 3128 HNewArray(HInstruction* length, 3129 HCurrentMethod* current_method, 3130 uint32_t dex_pc, 3131 uint16_t type_index, 3132 const DexFile& dex_file, 3133 QuickEntrypointEnum entrypoint) 3134 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3135 dex_pc_(dex_pc), 3136 type_index_(type_index), 3137 dex_file_(dex_file), 3138 entrypoint_(entrypoint) { 3139 SetRawInputAt(0, length); 3140 SetRawInputAt(1, current_method); 3141 } 3142 3143 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3144 uint16_t GetTypeIndex() const { return type_index_; } 3145 const DexFile& GetDexFile() const { return dex_file_; } 3146 3147 // Calls runtime so needs an environment. 3148 bool NeedsEnvironment() const OVERRIDE { return true; } 3149 3150 // May throw NegativeArraySizeException, OutOfMemoryError, etc. 3151 bool CanThrow() const OVERRIDE { return true; } 3152 3153 bool CanBeNull() const OVERRIDE { return false; } 3154 3155 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 3156 3157 DECLARE_INSTRUCTION(NewArray); 3158 3159 private: 3160 const uint32_t dex_pc_; 3161 const uint16_t type_index_; 3162 const DexFile& dex_file_; 3163 const QuickEntrypointEnum entrypoint_; 3164 3165 DISALLOW_COPY_AND_ASSIGN(HNewArray); 3166}; 3167 3168class HAdd : public HBinaryOperation { 3169 public: 3170 HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 3171 : HBinaryOperation(result_type, left, right) {} 3172 3173 bool IsCommutative() const OVERRIDE { return true; } 3174 3175 template <typename T> T Compute(T x, T y) const { return x + y; } 3176 3177 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3178 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 3179 } 3180 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3181 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue(), y->GetValue())); 3182 } 3183 3184 DECLARE_INSTRUCTION(Add); 3185 3186 private: 3187 DISALLOW_COPY_AND_ASSIGN(HAdd); 3188}; 3189 3190class HSub : public HBinaryOperation { 3191 public: 3192 HSub(Primitive::Type result_type, HInstruction* left, HInstruction* right) 3193 : HBinaryOperation(result_type, left, right) {} 3194 3195 template <typename T> T Compute(T x, T y) const { return x - y; } 3196 3197 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3198 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 3199 } 3200 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3201 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue(), y->GetValue())); 3202 } 3203 3204 DECLARE_INSTRUCTION(Sub); 3205 3206 private: 3207 DISALLOW_COPY_AND_ASSIGN(HSub); 3208}; 3209 3210class HMul : public HBinaryOperation { 3211 public: 3212 HMul(Primitive::Type result_type, HInstruction* left, HInstruction* right) 3213 : HBinaryOperation(result_type, left, right) {} 3214 3215 bool IsCommutative() const OVERRIDE { return true; } 3216 3217 template <typename T> T Compute(T x, T y) const { return x * y; } 3218 3219 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3220 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 3221 } 3222 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3223 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue(), y->GetValue())); 3224 } 3225 3226 DECLARE_INSTRUCTION(Mul); 3227 3228 private: 3229 DISALLOW_COPY_AND_ASSIGN(HMul); 3230}; 3231 3232class HDiv : public HBinaryOperation { 3233 public: 3234 HDiv(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc) 3235 : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {} 3236 3237 template <typename T> 3238 T Compute(T x, T y) const { 3239 // Our graph structure ensures we never have 0 for `y` during 3240 // constant folding. 3241 DCHECK_NE(y, 0); 3242 // Special case -1 to avoid getting a SIGFPE on x86(_64). 3243 return (y == -1) ? -x : x / y; 3244 } 3245 3246 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3247 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 3248 } 3249 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3250 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue(), y->GetValue())); 3251 } 3252 3253 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3254 3255 DECLARE_INSTRUCTION(Div); 3256 3257 private: 3258 const uint32_t dex_pc_; 3259 3260 DISALLOW_COPY_AND_ASSIGN(HDiv); 3261}; 3262 3263class HRem : public HBinaryOperation { 3264 public: 3265 HRem(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc) 3266 : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {} 3267 3268 template <typename T> 3269 T Compute(T x, T y) const { 3270 // Our graph structure ensures we never have 0 for `y` during 3271 // constant folding. 3272 DCHECK_NE(y, 0); 3273 // Special case -1 to avoid getting a SIGFPE on x86(_64). 3274 return (y == -1) ? 0 : x % y; 3275 } 3276 3277 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3278 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 3279 } 3280 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3281 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue(), y->GetValue())); 3282 } 3283 3284 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3285 3286 DECLARE_INSTRUCTION(Rem); 3287 3288 private: 3289 const uint32_t dex_pc_; 3290 3291 DISALLOW_COPY_AND_ASSIGN(HRem); 3292}; 3293 3294class HDivZeroCheck : public HExpression<1> { 3295 public: 3296 HDivZeroCheck(HInstruction* value, uint32_t dex_pc) 3297 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 3298 SetRawInputAt(0, value); 3299 } 3300 3301 Primitive::Type GetType() const OVERRIDE { return InputAt(0)->GetType(); } 3302 3303 bool CanBeMoved() const OVERRIDE { return true; } 3304 3305 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3306 UNUSED(other); 3307 return true; 3308 } 3309 3310 bool NeedsEnvironment() const OVERRIDE { return true; } 3311 bool CanThrow() const OVERRIDE { return true; } 3312 3313 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3314 3315 DECLARE_INSTRUCTION(DivZeroCheck); 3316 3317 private: 3318 const uint32_t dex_pc_; 3319 3320 DISALLOW_COPY_AND_ASSIGN(HDivZeroCheck); 3321}; 3322 3323class HShl : public HBinaryOperation { 3324 public: 3325 HShl(Primitive::Type result_type, HInstruction* left, HInstruction* right) 3326 : HBinaryOperation(result_type, left, right) {} 3327 3328 template <typename T, typename U, typename V> 3329 T Compute(T x, U y, V max_shift_value) const { 3330 static_assert(std::is_same<V, typename std::make_unsigned<T>::type>::value, 3331 "V is not the unsigned integer type corresponding to T"); 3332 return x << (y & max_shift_value); 3333 } 3334 3335 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3336 return GetBlock()->GetGraph()->GetIntConstant( 3337 Compute(x->GetValue(), y->GetValue(), kMaxIntShiftValue)); 3338 } 3339 // There is no `Evaluate(HIntConstant* x, HLongConstant* y)`, as this 3340 // case is handled as `x << static_cast<int>(y)`. 3341 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 3342 return GetBlock()->GetGraph()->GetLongConstant( 3343 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue)); 3344 } 3345 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3346 return GetBlock()->GetGraph()->GetLongConstant( 3347 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue)); 3348 } 3349 3350 DECLARE_INSTRUCTION(Shl); 3351 3352 private: 3353 DISALLOW_COPY_AND_ASSIGN(HShl); 3354}; 3355 3356class HShr : public HBinaryOperation { 3357 public: 3358 HShr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 3359 : HBinaryOperation(result_type, left, right) {} 3360 3361 template <typename T, typename U, typename V> 3362 T Compute(T x, U y, V max_shift_value) const { 3363 static_assert(std::is_same<V, typename std::make_unsigned<T>::type>::value, 3364 "V is not the unsigned integer type corresponding to T"); 3365 return x >> (y & max_shift_value); 3366 } 3367 3368 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3369 return GetBlock()->GetGraph()->GetIntConstant( 3370 Compute(x->GetValue(), y->GetValue(), kMaxIntShiftValue)); 3371 } 3372 // There is no `Evaluate(HIntConstant* x, HLongConstant* y)`, as this 3373 // case is handled as `x >> static_cast<int>(y)`. 3374 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 3375 return GetBlock()->GetGraph()->GetLongConstant( 3376 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue)); 3377 } 3378 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3379 return GetBlock()->GetGraph()->GetLongConstant( 3380 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue)); 3381 } 3382 3383 DECLARE_INSTRUCTION(Shr); 3384 3385 private: 3386 DISALLOW_COPY_AND_ASSIGN(HShr); 3387}; 3388 3389class HUShr : public HBinaryOperation { 3390 public: 3391 HUShr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 3392 : HBinaryOperation(result_type, left, right) {} 3393 3394 template <typename T, typename U, typename V> 3395 T Compute(T x, U y, V max_shift_value) const { 3396 static_assert(std::is_same<V, typename std::make_unsigned<T>::type>::value, 3397 "V is not the unsigned integer type corresponding to T"); 3398 V ux = static_cast<V>(x); 3399 return static_cast<T>(ux >> (y & max_shift_value)); 3400 } 3401 3402 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3403 return GetBlock()->GetGraph()->GetIntConstant( 3404 Compute(x->GetValue(), y->GetValue(), kMaxIntShiftValue)); 3405 } 3406 // There is no `Evaluate(HIntConstant* x, HLongConstant* y)`, as this 3407 // case is handled as `x >>> static_cast<int>(y)`. 3408 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 3409 return GetBlock()->GetGraph()->GetLongConstant( 3410 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue)); 3411 } 3412 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3413 return GetBlock()->GetGraph()->GetLongConstant( 3414 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue)); 3415 } 3416 3417 DECLARE_INSTRUCTION(UShr); 3418 3419 private: 3420 DISALLOW_COPY_AND_ASSIGN(HUShr); 3421}; 3422 3423class HAnd : public HBinaryOperation { 3424 public: 3425 HAnd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 3426 : HBinaryOperation(result_type, left, right) {} 3427 3428 bool IsCommutative() const OVERRIDE { return true; } 3429 3430 template <typename T, typename U> 3431 auto Compute(T x, U y) const -> decltype(x & y) { return x & y; } 3432 3433 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3434 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 3435 } 3436 HConstant* Evaluate(HIntConstant* x, HLongConstant* y) const OVERRIDE { 3437 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue(), y->GetValue())); 3438 } 3439 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 3440 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue(), y->GetValue())); 3441 } 3442 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3443 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue(), y->GetValue())); 3444 } 3445 3446 DECLARE_INSTRUCTION(And); 3447 3448 private: 3449 DISALLOW_COPY_AND_ASSIGN(HAnd); 3450}; 3451 3452class HOr : public HBinaryOperation { 3453 public: 3454 HOr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 3455 : HBinaryOperation(result_type, left, right) {} 3456 3457 bool IsCommutative() const OVERRIDE { return true; } 3458 3459 template <typename T, typename U> 3460 auto Compute(T x, U y) const -> decltype(x | y) { return x | y; } 3461 3462 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3463 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 3464 } 3465 HConstant* Evaluate(HIntConstant* x, HLongConstant* y) const OVERRIDE { 3466 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue(), y->GetValue())); 3467 } 3468 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 3469 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue(), y->GetValue())); 3470 } 3471 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3472 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue(), y->GetValue())); 3473 } 3474 3475 DECLARE_INSTRUCTION(Or); 3476 3477 private: 3478 DISALLOW_COPY_AND_ASSIGN(HOr); 3479}; 3480 3481class HXor : public HBinaryOperation { 3482 public: 3483 HXor(Primitive::Type result_type, HInstruction* left, HInstruction* right) 3484 : HBinaryOperation(result_type, left, right) {} 3485 3486 bool IsCommutative() const OVERRIDE { return true; } 3487 3488 template <typename T, typename U> 3489 auto Compute(T x, U y) const -> decltype(x ^ y) { return x ^ y; } 3490 3491 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3492 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue(), y->GetValue())); 3493 } 3494 HConstant* Evaluate(HIntConstant* x, HLongConstant* y) const OVERRIDE { 3495 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue(), y->GetValue())); 3496 } 3497 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 3498 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue(), y->GetValue())); 3499 } 3500 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3501 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue(), y->GetValue())); 3502 } 3503 3504 DECLARE_INSTRUCTION(Xor); 3505 3506 private: 3507 DISALLOW_COPY_AND_ASSIGN(HXor); 3508}; 3509 3510// The value of a parameter in this method. Its location depends on 3511// the calling convention. 3512class HParameterValue : public HExpression<0> { 3513 public: 3514 HParameterValue(uint8_t index, Primitive::Type parameter_type, bool is_this = false) 3515 : HExpression(parameter_type, SideEffects::None()), index_(index), is_this_(is_this) {} 3516 3517 uint8_t GetIndex() const { return index_; } 3518 3519 bool CanBeNull() const OVERRIDE { return !is_this_; } 3520 3521 bool IsThis() const { return is_this_; } 3522 3523 DECLARE_INSTRUCTION(ParameterValue); 3524 3525 private: 3526 // The index of this parameter in the parameters list. Must be less 3527 // than HGraph::number_of_in_vregs_. 3528 const uint8_t index_; 3529 3530 // Whether or not the parameter value corresponds to 'this' argument. 3531 const bool is_this_; 3532 3533 DISALLOW_COPY_AND_ASSIGN(HParameterValue); 3534}; 3535 3536class HNot : public HUnaryOperation { 3537 public: 3538 explicit HNot(Primitive::Type result_type, HInstruction* input) 3539 : HUnaryOperation(result_type, input) {} 3540 3541 bool CanBeMoved() const OVERRIDE { return true; } 3542 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3543 UNUSED(other); 3544 return true; 3545 } 3546 3547 template <typename T> T Compute(T x) const { return ~x; } 3548 3549 HConstant* Evaluate(HIntConstant* x) const OVERRIDE { 3550 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue())); 3551 } 3552 HConstant* Evaluate(HLongConstant* x) const OVERRIDE { 3553 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue())); 3554 } 3555 3556 DECLARE_INSTRUCTION(Not); 3557 3558 private: 3559 DISALLOW_COPY_AND_ASSIGN(HNot); 3560}; 3561 3562class HBooleanNot : public HUnaryOperation { 3563 public: 3564 explicit HBooleanNot(HInstruction* input) 3565 : HUnaryOperation(Primitive::Type::kPrimBoolean, input) {} 3566 3567 bool CanBeMoved() const OVERRIDE { return true; } 3568 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3569 UNUSED(other); 3570 return true; 3571 } 3572 3573 template <typename T> bool Compute(T x) const { 3574 DCHECK(IsUint<1>(x)); 3575 return !x; 3576 } 3577 3578 HConstant* Evaluate(HIntConstant* x) const OVERRIDE { 3579 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue())); 3580 } 3581 HConstant* Evaluate(HLongConstant* x ATTRIBUTE_UNUSED) const OVERRIDE { 3582 LOG(FATAL) << DebugName() << " is not defined for long values"; 3583 UNREACHABLE(); 3584 } 3585 3586 DECLARE_INSTRUCTION(BooleanNot); 3587 3588 private: 3589 DISALLOW_COPY_AND_ASSIGN(HBooleanNot); 3590}; 3591 3592class HTypeConversion : public HExpression<1> { 3593 public: 3594 // Instantiate a type conversion of `input` to `result_type`. 3595 HTypeConversion(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc) 3596 : HExpression(result_type, SideEffects::None()), dex_pc_(dex_pc) { 3597 SetRawInputAt(0, input); 3598 DCHECK_NE(input->GetType(), result_type); 3599 } 3600 3601 HInstruction* GetInput() const { return InputAt(0); } 3602 Primitive::Type GetInputType() const { return GetInput()->GetType(); } 3603 Primitive::Type GetResultType() const { return GetType(); } 3604 3605 // Required by the x86 and ARM code generators when producing calls 3606 // to the runtime. 3607 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3608 3609 bool CanBeMoved() const OVERRIDE { return true; } 3610 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { return true; } 3611 3612 // Try to statically evaluate the conversion and return a HConstant 3613 // containing the result. If the input cannot be converted, return nullptr. 3614 HConstant* TryStaticEvaluation() const; 3615 3616 DECLARE_INSTRUCTION(TypeConversion); 3617 3618 private: 3619 const uint32_t dex_pc_; 3620 3621 DISALLOW_COPY_AND_ASSIGN(HTypeConversion); 3622}; 3623 3624static constexpr uint32_t kNoRegNumber = -1; 3625 3626class HPhi : public HInstruction { 3627 public: 3628 HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type) 3629 : HInstruction(SideEffects::None()), 3630 inputs_(arena, number_of_inputs), 3631 reg_number_(reg_number), 3632 type_(type), 3633 is_live_(false), 3634 can_be_null_(true) { 3635 inputs_.SetSize(number_of_inputs); 3636 } 3637 3638 // Returns a type equivalent to the given `type`, but that a `HPhi` can hold. 3639 static Primitive::Type ToPhiType(Primitive::Type type) { 3640 switch (type) { 3641 case Primitive::kPrimBoolean: 3642 case Primitive::kPrimByte: 3643 case Primitive::kPrimShort: 3644 case Primitive::kPrimChar: 3645 return Primitive::kPrimInt; 3646 default: 3647 return type; 3648 } 3649 } 3650 3651 bool IsCatchPhi() const { return GetBlock()->IsCatchBlock(); } 3652 3653 size_t InputCount() const OVERRIDE { return inputs_.Size(); } 3654 3655 void AddInput(HInstruction* input); 3656 void RemoveInputAt(size_t index); 3657 3658 Primitive::Type GetType() const OVERRIDE { return type_; } 3659 void SetType(Primitive::Type type) { type_ = type; } 3660 3661 bool CanBeNull() const OVERRIDE { return can_be_null_; } 3662 void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; } 3663 3664 uint32_t GetRegNumber() const { return reg_number_; } 3665 3666 void SetDead() { is_live_ = false; } 3667 void SetLive() { is_live_ = true; } 3668 bool IsDead() const { return !is_live_; } 3669 bool IsLive() const { return is_live_; } 3670 3671 // Returns the next equivalent phi (starting from the current one) or null if there is none. 3672 // An equivalent phi is a phi having the same dex register and type. 3673 // It assumes that phis with the same dex register are adjacent. 3674 HPhi* GetNextEquivalentPhiWithSameType() { 3675 HInstruction* next = GetNext(); 3676 while (next != nullptr && next->AsPhi()->GetRegNumber() == reg_number_) { 3677 if (next->GetType() == GetType()) { 3678 return next->AsPhi(); 3679 } 3680 next = next->GetNext(); 3681 } 3682 return nullptr; 3683 } 3684 3685 DECLARE_INSTRUCTION(Phi); 3686 3687 protected: 3688 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); } 3689 3690 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE { 3691 inputs_.Put(index, input); 3692 } 3693 3694 private: 3695 GrowableArray<HUserRecord<HInstruction*> > inputs_; 3696 const uint32_t reg_number_; 3697 Primitive::Type type_; 3698 bool is_live_; 3699 bool can_be_null_; 3700 3701 DISALLOW_COPY_AND_ASSIGN(HPhi); 3702}; 3703 3704class HNullCheck : public HExpression<1> { 3705 public: 3706 HNullCheck(HInstruction* value, uint32_t dex_pc) 3707 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 3708 SetRawInputAt(0, value); 3709 } 3710 3711 bool CanBeMoved() const OVERRIDE { return true; } 3712 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3713 UNUSED(other); 3714 return true; 3715 } 3716 3717 bool NeedsEnvironment() const OVERRIDE { return true; } 3718 3719 bool CanThrow() const OVERRIDE { return true; } 3720 3721 bool CanBeNull() const OVERRIDE { return false; } 3722 3723 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3724 3725 DECLARE_INSTRUCTION(NullCheck); 3726 3727 private: 3728 const uint32_t dex_pc_; 3729 3730 DISALLOW_COPY_AND_ASSIGN(HNullCheck); 3731}; 3732 3733class FieldInfo : public ValueObject { 3734 public: 3735 FieldInfo(MemberOffset field_offset, 3736 Primitive::Type field_type, 3737 bool is_volatile, 3738 uint32_t index, 3739 const DexFile& dex_file) 3740 : field_offset_(field_offset), 3741 field_type_(field_type), 3742 is_volatile_(is_volatile), 3743 index_(index), 3744 dex_file_(dex_file) {} 3745 3746 MemberOffset GetFieldOffset() const { return field_offset_; } 3747 Primitive::Type GetFieldType() const { return field_type_; } 3748 uint32_t GetFieldIndex() const { return index_; } 3749 const DexFile& GetDexFile() const { return dex_file_; } 3750 bool IsVolatile() const { return is_volatile_; } 3751 3752 private: 3753 const MemberOffset field_offset_; 3754 const Primitive::Type field_type_; 3755 const bool is_volatile_; 3756 uint32_t index_; 3757 const DexFile& dex_file_; 3758}; 3759 3760class HInstanceFieldGet : public HExpression<1> { 3761 public: 3762 HInstanceFieldGet(HInstruction* value, 3763 Primitive::Type field_type, 3764 MemberOffset field_offset, 3765 bool is_volatile, 3766 uint32_t field_idx, 3767 const DexFile& dex_file) 3768 : HExpression( 3769 field_type, 3770 SideEffects::FieldReadOfType(field_type, is_volatile)), 3771 field_info_(field_offset, field_type, is_volatile, field_idx, dex_file) { 3772 SetRawInputAt(0, value); 3773 } 3774 3775 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 3776 3777 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3778 HInstanceFieldGet* other_get = other->AsInstanceFieldGet(); 3779 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 3780 } 3781 3782 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3783 return (obj == InputAt(0)) && GetFieldOffset().Uint32Value() < kPageSize; 3784 } 3785 3786 size_t ComputeHashCode() const OVERRIDE { 3787 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 3788 } 3789 3790 const FieldInfo& GetFieldInfo() const { return field_info_; } 3791 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3792 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3793 bool IsVolatile() const { return field_info_.IsVolatile(); } 3794 3795 DECLARE_INSTRUCTION(InstanceFieldGet); 3796 3797 private: 3798 const FieldInfo field_info_; 3799 3800 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet); 3801}; 3802 3803class HInstanceFieldSet : public HTemplateInstruction<2> { 3804 public: 3805 HInstanceFieldSet(HInstruction* object, 3806 HInstruction* value, 3807 Primitive::Type field_type, 3808 MemberOffset field_offset, 3809 bool is_volatile, 3810 uint32_t field_idx, 3811 const DexFile& dex_file) 3812 : HTemplateInstruction( 3813 SideEffects::FieldWriteOfType(field_type, is_volatile)), 3814 field_info_(field_offset, field_type, is_volatile, field_idx, dex_file), 3815 value_can_be_null_(true) { 3816 SetRawInputAt(0, object); 3817 SetRawInputAt(1, value); 3818 } 3819 3820 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3821 return (obj == InputAt(0)) && GetFieldOffset().Uint32Value() < kPageSize; 3822 } 3823 3824 const FieldInfo& GetFieldInfo() const { return field_info_; } 3825 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3826 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3827 bool IsVolatile() const { return field_info_.IsVolatile(); } 3828 HInstruction* GetValue() const { return InputAt(1); } 3829 bool GetValueCanBeNull() const { return value_can_be_null_; } 3830 void ClearValueCanBeNull() { value_can_be_null_ = false; } 3831 3832 DECLARE_INSTRUCTION(InstanceFieldSet); 3833 3834 private: 3835 const FieldInfo field_info_; 3836 bool value_can_be_null_; 3837 3838 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet); 3839}; 3840 3841class HArrayGet : public HExpression<2> { 3842 public: 3843 HArrayGet(HInstruction* array, HInstruction* index, Primitive::Type type) 3844 : HExpression(type, SideEffects::ArrayReadOfType(type)) { 3845 SetRawInputAt(0, array); 3846 SetRawInputAt(1, index); 3847 } 3848 3849 bool CanBeMoved() const OVERRIDE { return true; } 3850 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3851 UNUSED(other); 3852 return true; 3853 } 3854 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3855 UNUSED(obj); 3856 // TODO: We can be smarter here. 3857 // Currently, the array access is always preceded by an ArrayLength or a NullCheck 3858 // which generates the implicit null check. There are cases when these can be removed 3859 // to produce better code. If we ever add optimizations to do so we should allow an 3860 // implicit check here (as long as the address falls in the first page). 3861 return false; 3862 } 3863 3864 void SetType(Primitive::Type type) { type_ = type; } 3865 3866 HInstruction* GetArray() const { return InputAt(0); } 3867 HInstruction* GetIndex() const { return InputAt(1); } 3868 3869 DECLARE_INSTRUCTION(ArrayGet); 3870 3871 private: 3872 DISALLOW_COPY_AND_ASSIGN(HArrayGet); 3873}; 3874 3875class HArraySet : public HTemplateInstruction<3> { 3876 public: 3877 HArraySet(HInstruction* array, 3878 HInstruction* index, 3879 HInstruction* value, 3880 Primitive::Type expected_component_type, 3881 uint32_t dex_pc) 3882 : HTemplateInstruction(SideEffects::ArrayWriteOfType(expected_component_type)), 3883 dex_pc_(dex_pc), 3884 expected_component_type_(expected_component_type), 3885 needs_type_check_(value->GetType() == Primitive::kPrimNot), 3886 value_can_be_null_(true) { 3887 SetRawInputAt(0, array); 3888 SetRawInputAt(1, index); 3889 SetRawInputAt(2, value); 3890 } 3891 3892 bool NeedsEnvironment() const OVERRIDE { 3893 // We currently always call a runtime method to catch array store 3894 // exceptions. 3895 return needs_type_check_; 3896 } 3897 3898 // Can throw ArrayStoreException. 3899 bool CanThrow() const OVERRIDE { return needs_type_check_; } 3900 3901 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3902 UNUSED(obj); 3903 // TODO: Same as for ArrayGet. 3904 return false; 3905 } 3906 3907 void ClearNeedsTypeCheck() { 3908 needs_type_check_ = false; 3909 } 3910 3911 void ClearValueCanBeNull() { 3912 value_can_be_null_ = false; 3913 } 3914 3915 bool GetValueCanBeNull() const { return value_can_be_null_; } 3916 bool NeedsTypeCheck() const { return needs_type_check_; } 3917 3918 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3919 3920 HInstruction* GetArray() const { return InputAt(0); } 3921 HInstruction* GetIndex() const { return InputAt(1); } 3922 HInstruction* GetValue() const { return InputAt(2); } 3923 3924 Primitive::Type GetComponentType() const { 3925 // The Dex format does not type floating point index operations. Since the 3926 // `expected_component_type_` is set during building and can therefore not 3927 // be correct, we also check what is the value type. If it is a floating 3928 // point type, we must use that type. 3929 Primitive::Type value_type = GetValue()->GetType(); 3930 return ((value_type == Primitive::kPrimFloat) || (value_type == Primitive::kPrimDouble)) 3931 ? value_type 3932 : expected_component_type_; 3933 } 3934 3935 DECLARE_INSTRUCTION(ArraySet); 3936 3937 private: 3938 const uint32_t dex_pc_; 3939 const Primitive::Type expected_component_type_; 3940 bool needs_type_check_; 3941 bool value_can_be_null_; 3942 3943 DISALLOW_COPY_AND_ASSIGN(HArraySet); 3944}; 3945 3946class HArrayLength : public HExpression<1> { 3947 public: 3948 explicit HArrayLength(HInstruction* array) 3949 : HExpression(Primitive::kPrimInt, SideEffects::None()) { 3950 // Note that arrays do not change length, so the instruction does not 3951 // depend on any write. 3952 SetRawInputAt(0, array); 3953 } 3954 3955 bool CanBeMoved() const OVERRIDE { return true; } 3956 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3957 UNUSED(other); 3958 return true; 3959 } 3960 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3961 return obj == InputAt(0); 3962 } 3963 3964 DECLARE_INSTRUCTION(ArrayLength); 3965 3966 private: 3967 DISALLOW_COPY_AND_ASSIGN(HArrayLength); 3968}; 3969 3970class HBoundsCheck : public HExpression<2> { 3971 public: 3972 HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc) 3973 : HExpression(index->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 3974 DCHECK(index->GetType() == Primitive::kPrimInt); 3975 SetRawInputAt(0, index); 3976 SetRawInputAt(1, length); 3977 } 3978 3979 bool CanBeMoved() const OVERRIDE { return true; } 3980 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3981 UNUSED(other); 3982 return true; 3983 } 3984 3985 bool NeedsEnvironment() const OVERRIDE { return true; } 3986 3987 bool CanThrow() const OVERRIDE { return true; } 3988 3989 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3990 3991 DECLARE_INSTRUCTION(BoundsCheck); 3992 3993 private: 3994 const uint32_t dex_pc_; 3995 3996 DISALLOW_COPY_AND_ASSIGN(HBoundsCheck); 3997}; 3998 3999/** 4000 * Some DEX instructions are folded into multiple HInstructions that need 4001 * to stay live until the last HInstruction. This class 4002 * is used as a marker for the baseline compiler to ensure its preceding 4003 * HInstruction stays live. `index` represents the stack location index of the 4004 * instruction (the actual offset is computed as index * vreg_size). 4005 */ 4006class HTemporary : public HTemplateInstruction<0> { 4007 public: 4008 explicit HTemporary(size_t index) : HTemplateInstruction(SideEffects::None()), index_(index) {} 4009 4010 size_t GetIndex() const { return index_; } 4011 4012 Primitive::Type GetType() const OVERRIDE { 4013 // The previous instruction is the one that will be stored in the temporary location. 4014 DCHECK(GetPrevious() != nullptr); 4015 return GetPrevious()->GetType(); 4016 } 4017 4018 DECLARE_INSTRUCTION(Temporary); 4019 4020 private: 4021 const size_t index_; 4022 4023 DISALLOW_COPY_AND_ASSIGN(HTemporary); 4024}; 4025 4026class HSuspendCheck : public HTemplateInstruction<0> { 4027 public: 4028 explicit HSuspendCheck(uint32_t dex_pc) 4029 : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc), slow_path_(nullptr) {} 4030 4031 bool NeedsEnvironment() const OVERRIDE { 4032 return true; 4033 } 4034 4035 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 4036 void SetSlowPath(SlowPathCode* slow_path) { slow_path_ = slow_path; } 4037 SlowPathCode* GetSlowPath() const { return slow_path_; } 4038 4039 DECLARE_INSTRUCTION(SuspendCheck); 4040 4041 private: 4042 const uint32_t dex_pc_; 4043 4044 // Only used for code generation, in order to share the same slow path between back edges 4045 // of a same loop. 4046 SlowPathCode* slow_path_; 4047 4048 DISALLOW_COPY_AND_ASSIGN(HSuspendCheck); 4049}; 4050 4051/** 4052 * Instruction to load a Class object. 4053 */ 4054class HLoadClass : public HExpression<1> { 4055 public: 4056 HLoadClass(HCurrentMethod* current_method, 4057 uint16_t type_index, 4058 const DexFile& dex_file, 4059 bool is_referrers_class, 4060 uint32_t dex_pc) 4061 : HExpression(Primitive::kPrimNot, SideEffects::None()), 4062 type_index_(type_index), 4063 dex_file_(dex_file), 4064 is_referrers_class_(is_referrers_class), 4065 dex_pc_(dex_pc), 4066 generate_clinit_check_(false), 4067 loaded_class_rti_(ReferenceTypeInfo::CreateInvalid()) { 4068 SetRawInputAt(0, current_method); 4069 } 4070 4071 bool CanBeMoved() const OVERRIDE { return true; } 4072 4073 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 4074 return other->AsLoadClass()->type_index_ == type_index_; 4075 } 4076 4077 size_t ComputeHashCode() const OVERRIDE { return type_index_; } 4078 4079 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 4080 uint16_t GetTypeIndex() const { return type_index_; } 4081 bool IsReferrersClass() const { return is_referrers_class_; } 4082 bool CanBeNull() const OVERRIDE { return false; } 4083 4084 bool NeedsEnvironment() const OVERRIDE { 4085 // Will call runtime and load the class if the class is not loaded yet. 4086 // TODO: finer grain decision. 4087 return !is_referrers_class_; 4088 } 4089 4090 bool MustGenerateClinitCheck() const { 4091 return generate_clinit_check_; 4092 } 4093 4094 void SetMustGenerateClinitCheck(bool generate_clinit_check) { 4095 generate_clinit_check_ = generate_clinit_check; 4096 } 4097 4098 bool CanCallRuntime() const { 4099 return MustGenerateClinitCheck() || !is_referrers_class_; 4100 } 4101 4102 bool CanThrow() const OVERRIDE { 4103 // May call runtime and and therefore can throw. 4104 // TODO: finer grain decision. 4105 return CanCallRuntime(); 4106 } 4107 4108 ReferenceTypeInfo GetLoadedClassRTI() { 4109 return loaded_class_rti_; 4110 } 4111 4112 void SetLoadedClassRTI(ReferenceTypeInfo rti) { 4113 // Make sure we only set exact types (the loaded class should never be merged). 4114 DCHECK(rti.IsExact()); 4115 loaded_class_rti_ = rti; 4116 } 4117 4118 const DexFile& GetDexFile() { return dex_file_; } 4119 4120 bool NeedsDexCache() const OVERRIDE { return !is_referrers_class_; } 4121 4122 DECLARE_INSTRUCTION(LoadClass); 4123 4124 private: 4125 const uint16_t type_index_; 4126 const DexFile& dex_file_; 4127 const bool is_referrers_class_; 4128 const uint32_t dex_pc_; 4129 // Whether this instruction must generate the initialization check. 4130 // Used for code generation. 4131 bool generate_clinit_check_; 4132 4133 ReferenceTypeInfo loaded_class_rti_; 4134 4135 DISALLOW_COPY_AND_ASSIGN(HLoadClass); 4136}; 4137 4138class HLoadString : public HExpression<1> { 4139 public: 4140 HLoadString(HCurrentMethod* current_method, uint32_t string_index, uint32_t dex_pc) 4141 : HExpression(Primitive::kPrimNot, SideEffects::None()), 4142 string_index_(string_index), 4143 dex_pc_(dex_pc) { 4144 SetRawInputAt(0, current_method); 4145 } 4146 4147 bool CanBeMoved() const OVERRIDE { return true; } 4148 4149 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 4150 return other->AsLoadString()->string_index_ == string_index_; 4151 } 4152 4153 size_t ComputeHashCode() const OVERRIDE { return string_index_; } 4154 4155 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 4156 uint32_t GetStringIndex() const { return string_index_; } 4157 4158 // TODO: Can we deopt or debug when we resolve a string? 4159 bool NeedsEnvironment() const OVERRIDE { return false; } 4160 bool NeedsDexCache() const OVERRIDE { return true; } 4161 4162 DECLARE_INSTRUCTION(LoadString); 4163 4164 private: 4165 const uint32_t string_index_; 4166 const uint32_t dex_pc_; 4167 4168 DISALLOW_COPY_AND_ASSIGN(HLoadString); 4169}; 4170 4171/** 4172 * Performs an initialization check on its Class object input. 4173 */ 4174class HClinitCheck : public HExpression<1> { 4175 public: 4176 explicit HClinitCheck(HLoadClass* constant, uint32_t dex_pc) 4177 : HExpression( 4178 Primitive::kPrimNot, 4179 SideEffects::AllWrites()), // assume write on all fields/arrays 4180 dex_pc_(dex_pc) { 4181 SetRawInputAt(0, constant); 4182 } 4183 4184 bool CanBeMoved() const OVERRIDE { return true; } 4185 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 4186 UNUSED(other); 4187 return true; 4188 } 4189 4190 bool NeedsEnvironment() const OVERRIDE { 4191 // May call runtime to initialize the class. 4192 return true; 4193 } 4194 4195 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 4196 4197 HLoadClass* GetLoadClass() const { return InputAt(0)->AsLoadClass(); } 4198 4199 DECLARE_INSTRUCTION(ClinitCheck); 4200 4201 private: 4202 const uint32_t dex_pc_; 4203 4204 DISALLOW_COPY_AND_ASSIGN(HClinitCheck); 4205}; 4206 4207class HStaticFieldGet : public HExpression<1> { 4208 public: 4209 HStaticFieldGet(HInstruction* cls, 4210 Primitive::Type field_type, 4211 MemberOffset field_offset, 4212 bool is_volatile, 4213 uint32_t field_idx, 4214 const DexFile& dex_file) 4215 : HExpression( 4216 field_type, 4217 SideEffects::FieldReadOfType(field_type, is_volatile)), 4218 field_info_(field_offset, field_type, is_volatile, field_idx, dex_file) { 4219 SetRawInputAt(0, cls); 4220 } 4221 4222 4223 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 4224 4225 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 4226 HStaticFieldGet* other_get = other->AsStaticFieldGet(); 4227 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 4228 } 4229 4230 size_t ComputeHashCode() const OVERRIDE { 4231 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 4232 } 4233 4234 const FieldInfo& GetFieldInfo() const { return field_info_; } 4235 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 4236 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 4237 bool IsVolatile() const { return field_info_.IsVolatile(); } 4238 4239 DECLARE_INSTRUCTION(StaticFieldGet); 4240 4241 private: 4242 const FieldInfo field_info_; 4243 4244 DISALLOW_COPY_AND_ASSIGN(HStaticFieldGet); 4245}; 4246 4247class HStaticFieldSet : public HTemplateInstruction<2> { 4248 public: 4249 HStaticFieldSet(HInstruction* cls, 4250 HInstruction* value, 4251 Primitive::Type field_type, 4252 MemberOffset field_offset, 4253 bool is_volatile, 4254 uint32_t field_idx, 4255 const DexFile& dex_file) 4256 : HTemplateInstruction( 4257 SideEffects::FieldWriteOfType(field_type, is_volatile)), 4258 field_info_(field_offset, field_type, is_volatile, field_idx, dex_file), 4259 value_can_be_null_(true) { 4260 SetRawInputAt(0, cls); 4261 SetRawInputAt(1, value); 4262 } 4263 4264 const FieldInfo& GetFieldInfo() const { return field_info_; } 4265 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 4266 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 4267 bool IsVolatile() const { return field_info_.IsVolatile(); } 4268 4269 HInstruction* GetValue() const { return InputAt(1); } 4270 bool GetValueCanBeNull() const { return value_can_be_null_; } 4271 void ClearValueCanBeNull() { value_can_be_null_ = false; } 4272 4273 DECLARE_INSTRUCTION(StaticFieldSet); 4274 4275 private: 4276 const FieldInfo field_info_; 4277 bool value_can_be_null_; 4278 4279 DISALLOW_COPY_AND_ASSIGN(HStaticFieldSet); 4280}; 4281 4282// Implement the move-exception DEX instruction. 4283class HLoadException : public HExpression<0> { 4284 public: 4285 HLoadException() : HExpression(Primitive::kPrimNot, SideEffects::None()) {} 4286 4287 DECLARE_INSTRUCTION(LoadException); 4288 4289 private: 4290 DISALLOW_COPY_AND_ASSIGN(HLoadException); 4291}; 4292 4293// Implicit part of move-exception which clears thread-local exception storage. 4294// Must not be removed because the runtime expects the TLS to get cleared. 4295class HClearException : public HTemplateInstruction<0> { 4296 public: 4297 HClearException() : HTemplateInstruction(SideEffects::AllWrites()) {} 4298 4299 DECLARE_INSTRUCTION(ClearException); 4300 4301 private: 4302 DISALLOW_COPY_AND_ASSIGN(HClearException); 4303}; 4304 4305class HThrow : public HTemplateInstruction<1> { 4306 public: 4307 HThrow(HInstruction* exception, uint32_t dex_pc) 4308 : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc) { 4309 SetRawInputAt(0, exception); 4310 } 4311 4312 bool IsControlFlow() const OVERRIDE { return true; } 4313 4314 bool NeedsEnvironment() const OVERRIDE { return true; } 4315 4316 bool CanThrow() const OVERRIDE { return true; } 4317 4318 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 4319 4320 DECLARE_INSTRUCTION(Throw); 4321 4322 private: 4323 const uint32_t dex_pc_; 4324 4325 DISALLOW_COPY_AND_ASSIGN(HThrow); 4326}; 4327 4328class HInstanceOf : public HExpression<2> { 4329 public: 4330 HInstanceOf(HInstruction* object, 4331 HLoadClass* constant, 4332 bool class_is_final, 4333 uint32_t dex_pc) 4334 : HExpression(Primitive::kPrimBoolean, SideEffects::None()), 4335 class_is_final_(class_is_final), 4336 must_do_null_check_(true), 4337 dex_pc_(dex_pc) { 4338 SetRawInputAt(0, object); 4339 SetRawInputAt(1, constant); 4340 } 4341 4342 bool CanBeMoved() const OVERRIDE { return true; } 4343 4344 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4345 return true; 4346 } 4347 4348 bool NeedsEnvironment() const OVERRIDE { 4349 return false; 4350 } 4351 4352 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 4353 4354 bool IsClassFinal() const { return class_is_final_; } 4355 4356 // Used only in code generation. 4357 bool MustDoNullCheck() const { return must_do_null_check_; } 4358 void ClearMustDoNullCheck() { must_do_null_check_ = false; } 4359 4360 DECLARE_INSTRUCTION(InstanceOf); 4361 4362 private: 4363 const bool class_is_final_; 4364 bool must_do_null_check_; 4365 const uint32_t dex_pc_; 4366 4367 DISALLOW_COPY_AND_ASSIGN(HInstanceOf); 4368}; 4369 4370class HBoundType : public HExpression<1> { 4371 public: 4372 // Constructs an HBoundType with the given upper_bound. 4373 // Ensures that the upper_bound is valid. 4374 HBoundType(HInstruction* input, ReferenceTypeInfo upper_bound, bool upper_can_be_null) 4375 : HExpression(Primitive::kPrimNot, SideEffects::None()), 4376 upper_bound_(upper_bound), 4377 upper_can_be_null_(upper_can_be_null), 4378 can_be_null_(upper_can_be_null) { 4379 DCHECK_EQ(input->GetType(), Primitive::kPrimNot); 4380 SetRawInputAt(0, input); 4381 SetReferenceTypeInfo(upper_bound_); 4382 } 4383 4384 // GetUpper* should only be used in reference type propagation. 4385 const ReferenceTypeInfo& GetUpperBound() const { return upper_bound_; } 4386 bool GetUpperCanBeNull() const { return upper_can_be_null_; } 4387 4388 void SetCanBeNull(bool can_be_null) { 4389 DCHECK(upper_can_be_null_ || !can_be_null); 4390 can_be_null_ = can_be_null; 4391 } 4392 4393 bool CanBeNull() const OVERRIDE { return can_be_null_; } 4394 4395 DECLARE_INSTRUCTION(BoundType); 4396 4397 private: 4398 // Encodes the most upper class that this instruction can have. In other words 4399 // it is always the case that GetUpperBound().IsSupertypeOf(GetReferenceType()). 4400 // It is used to bound the type in cases like: 4401 // if (x instanceof ClassX) { 4402 // // uper_bound_ will be ClassX 4403 // } 4404 const ReferenceTypeInfo upper_bound_; 4405 // Represents the top constraint that can_be_null_ cannot exceed (i.e. if this 4406 // is false then can_be_null_ cannot be true). 4407 const bool upper_can_be_null_; 4408 bool can_be_null_; 4409 4410 DISALLOW_COPY_AND_ASSIGN(HBoundType); 4411}; 4412 4413class HCheckCast : public HTemplateInstruction<2> { 4414 public: 4415 HCheckCast(HInstruction* object, 4416 HLoadClass* constant, 4417 bool class_is_final, 4418 uint32_t dex_pc) 4419 : HTemplateInstruction(SideEffects::None()), 4420 class_is_final_(class_is_final), 4421 must_do_null_check_(true), 4422 dex_pc_(dex_pc) { 4423 SetRawInputAt(0, object); 4424 SetRawInputAt(1, constant); 4425 } 4426 4427 bool CanBeMoved() const OVERRIDE { return true; } 4428 4429 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4430 return true; 4431 } 4432 4433 bool NeedsEnvironment() const OVERRIDE { 4434 // Instruction may throw a CheckCastError. 4435 return true; 4436 } 4437 4438 bool CanThrow() const OVERRIDE { return true; } 4439 4440 bool MustDoNullCheck() const { return must_do_null_check_; } 4441 void ClearMustDoNullCheck() { must_do_null_check_ = false; } 4442 4443 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 4444 4445 bool IsClassFinal() const { return class_is_final_; } 4446 4447 DECLARE_INSTRUCTION(CheckCast); 4448 4449 private: 4450 const bool class_is_final_; 4451 bool must_do_null_check_; 4452 const uint32_t dex_pc_; 4453 4454 DISALLOW_COPY_AND_ASSIGN(HCheckCast); 4455}; 4456 4457class HMemoryBarrier : public HTemplateInstruction<0> { 4458 public: 4459 explicit HMemoryBarrier(MemBarrierKind barrier_kind) 4460 : HTemplateInstruction( 4461 SideEffects::All()), // assume write/read on all fields/arrays 4462 barrier_kind_(barrier_kind) {} 4463 4464 MemBarrierKind GetBarrierKind() { return barrier_kind_; } 4465 4466 DECLARE_INSTRUCTION(MemoryBarrier); 4467 4468 private: 4469 const MemBarrierKind barrier_kind_; 4470 4471 DISALLOW_COPY_AND_ASSIGN(HMemoryBarrier); 4472}; 4473 4474class HMonitorOperation : public HTemplateInstruction<1> { 4475 public: 4476 enum OperationKind { 4477 kEnter, 4478 kExit, 4479 }; 4480 4481 HMonitorOperation(HInstruction* object, OperationKind kind, uint32_t dex_pc) 4482 : HTemplateInstruction(SideEffects::All()), // assume write/read on all fields/arrays 4483 kind_(kind), dex_pc_(dex_pc) { 4484 SetRawInputAt(0, object); 4485 } 4486 4487 // Instruction may throw a Java exception, so we need an environment. 4488 bool NeedsEnvironment() const OVERRIDE { return CanThrow(); } 4489 4490 bool CanThrow() const OVERRIDE { 4491 // Verifier guarantees that monitor-exit cannot throw. 4492 // This is important because it allows the HGraphBuilder to remove 4493 // a dead throw-catch loop generated for `synchronized` blocks/methods. 4494 return IsEnter(); 4495 } 4496 4497 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 4498 4499 bool IsEnter() const { return kind_ == kEnter; } 4500 4501 DECLARE_INSTRUCTION(MonitorOperation); 4502 4503 private: 4504 const OperationKind kind_; 4505 const uint32_t dex_pc_; 4506 4507 private: 4508 DISALLOW_COPY_AND_ASSIGN(HMonitorOperation); 4509}; 4510 4511/** 4512 * A HInstruction used as a marker for the replacement of new + <init> 4513 * of a String to a call to a StringFactory. Only baseline will see 4514 * the node at code generation, where it will be be treated as null. 4515 * When compiling non-baseline, `HFakeString` instructions are being removed 4516 * in the instruction simplifier. 4517 */ 4518class HFakeString : public HTemplateInstruction<0> { 4519 public: 4520 HFakeString() : HTemplateInstruction(SideEffects::None()) {} 4521 4522 Primitive::Type GetType() const OVERRIDE { return Primitive::kPrimNot; } 4523 4524 DECLARE_INSTRUCTION(FakeString); 4525 4526 private: 4527 DISALLOW_COPY_AND_ASSIGN(HFakeString); 4528}; 4529 4530class MoveOperands : public ArenaObject<kArenaAllocMisc> { 4531 public: 4532 MoveOperands(Location source, 4533 Location destination, 4534 Primitive::Type type, 4535 HInstruction* instruction) 4536 : source_(source), destination_(destination), type_(type), instruction_(instruction) {} 4537 4538 Location GetSource() const { return source_; } 4539 Location GetDestination() const { return destination_; } 4540 4541 void SetSource(Location value) { source_ = value; } 4542 void SetDestination(Location value) { destination_ = value; } 4543 4544 // The parallel move resolver marks moves as "in-progress" by clearing the 4545 // destination (but not the source). 4546 Location MarkPending() { 4547 DCHECK(!IsPending()); 4548 Location dest = destination_; 4549 destination_ = Location::NoLocation(); 4550 return dest; 4551 } 4552 4553 void ClearPending(Location dest) { 4554 DCHECK(IsPending()); 4555 destination_ = dest; 4556 } 4557 4558 bool IsPending() const { 4559 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 4560 return destination_.IsInvalid() && !source_.IsInvalid(); 4561 } 4562 4563 // True if this blocks a move from the given location. 4564 bool Blocks(Location loc) const { 4565 return !IsEliminated() && source_.OverlapsWith(loc); 4566 } 4567 4568 // A move is redundant if it's been eliminated, if its source and 4569 // destination are the same, or if its destination is unneeded. 4570 bool IsRedundant() const { 4571 return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_); 4572 } 4573 4574 // We clear both operands to indicate move that's been eliminated. 4575 void Eliminate() { 4576 source_ = destination_ = Location::NoLocation(); 4577 } 4578 4579 bool IsEliminated() const { 4580 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 4581 return source_.IsInvalid(); 4582 } 4583 4584 Primitive::Type GetType() const { return type_; } 4585 4586 bool Is64BitMove() const { 4587 return Primitive::Is64BitType(type_); 4588 } 4589 4590 HInstruction* GetInstruction() const { return instruction_; } 4591 4592 private: 4593 Location source_; 4594 Location destination_; 4595 // The type this move is for. 4596 Primitive::Type type_; 4597 // The instruction this move is assocatied with. Null when this move is 4598 // for moving an input in the expected locations of user (including a phi user). 4599 // This is only used in debug mode, to ensure we do not connect interval siblings 4600 // in the same parallel move. 4601 HInstruction* instruction_; 4602}; 4603 4604static constexpr size_t kDefaultNumberOfMoves = 4; 4605 4606class HParallelMove : public HTemplateInstruction<0> { 4607 public: 4608 explicit HParallelMove(ArenaAllocator* arena) 4609 : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {} 4610 4611 void AddMove(Location source, 4612 Location destination, 4613 Primitive::Type type, 4614 HInstruction* instruction) { 4615 DCHECK(source.IsValid()); 4616 DCHECK(destination.IsValid()); 4617 if (kIsDebugBuild) { 4618 if (instruction != nullptr) { 4619 for (size_t i = 0, e = moves_.Size(); i < e; ++i) { 4620 if (moves_.Get(i).GetInstruction() == instruction) { 4621 // Special case the situation where the move is for the spill slot 4622 // of the instruction. 4623 if ((GetPrevious() == instruction) 4624 || ((GetPrevious() == nullptr) 4625 && instruction->IsPhi() 4626 && instruction->GetBlock() == GetBlock())) { 4627 DCHECK_NE(destination.GetKind(), moves_.Get(i).GetDestination().GetKind()) 4628 << "Doing parallel moves for the same instruction."; 4629 } else { 4630 DCHECK(false) << "Doing parallel moves for the same instruction."; 4631 } 4632 } 4633 } 4634 } 4635 for (size_t i = 0, e = moves_.Size(); i < e; ++i) { 4636 DCHECK(!destination.OverlapsWith(moves_.Get(i).GetDestination())) 4637 << "Overlapped destination for two moves in a parallel move: " 4638 << moves_.Get(i).GetSource() << " ==> " << moves_.Get(i).GetDestination() << " and " 4639 << source << " ==> " << destination; 4640 } 4641 } 4642 moves_.Add(MoveOperands(source, destination, type, instruction)); 4643 } 4644 4645 MoveOperands* MoveOperandsAt(size_t index) const { 4646 return moves_.GetRawStorage() + index; 4647 } 4648 4649 size_t NumMoves() const { return moves_.Size(); } 4650 4651 DECLARE_INSTRUCTION(ParallelMove); 4652 4653 private: 4654 GrowableArray<MoveOperands> moves_; 4655 4656 DISALLOW_COPY_AND_ASSIGN(HParallelMove); 4657}; 4658 4659class HGraphVisitor : public ValueObject { 4660 public: 4661 explicit HGraphVisitor(HGraph* graph) : graph_(graph) {} 4662 virtual ~HGraphVisitor() {} 4663 4664 virtual void VisitInstruction(HInstruction* instruction) { UNUSED(instruction); } 4665 virtual void VisitBasicBlock(HBasicBlock* block); 4666 4667 // Visit the graph following basic block insertion order. 4668 void VisitInsertionOrder(); 4669 4670 // Visit the graph following dominator tree reverse post-order. 4671 void VisitReversePostOrder(); 4672 4673 HGraph* GetGraph() const { return graph_; } 4674 4675 // Visit functions for instruction classes. 4676#define DECLARE_VISIT_INSTRUCTION(name, super) \ 4677 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } 4678 4679 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 4680 4681#undef DECLARE_VISIT_INSTRUCTION 4682 4683 private: 4684 HGraph* const graph_; 4685 4686 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); 4687}; 4688 4689class HGraphDelegateVisitor : public HGraphVisitor { 4690 public: 4691 explicit HGraphDelegateVisitor(HGraph* graph) : HGraphVisitor(graph) {} 4692 virtual ~HGraphDelegateVisitor() {} 4693 4694 // Visit functions that delegate to to super class. 4695#define DECLARE_VISIT_INSTRUCTION(name, super) \ 4696 void Visit##name(H##name* instr) OVERRIDE { Visit##super(instr); } 4697 4698 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 4699 4700#undef DECLARE_VISIT_INSTRUCTION 4701 4702 private: 4703 DISALLOW_COPY_AND_ASSIGN(HGraphDelegateVisitor); 4704}; 4705 4706class HInsertionOrderIterator : public ValueObject { 4707 public: 4708 explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 4709 4710 bool Done() const { return index_ == graph_.GetBlocks().Size(); } 4711 HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); } 4712 void Advance() { ++index_; } 4713 4714 private: 4715 const HGraph& graph_; 4716 size_t index_; 4717 4718 DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator); 4719}; 4720 4721class HReversePostOrderIterator : public ValueObject { 4722 public: 4723 explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) { 4724 // Check that reverse post order of the graph has been built. 4725 DCHECK(!graph.GetReversePostOrder().IsEmpty()); 4726 } 4727 4728 bool Done() const { return index_ == graph_.GetReversePostOrder().Size(); } 4729 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_); } 4730 void Advance() { ++index_; } 4731 4732 private: 4733 const HGraph& graph_; 4734 size_t index_; 4735 4736 DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator); 4737}; 4738 4739class HPostOrderIterator : public ValueObject { 4740 public: 4741 explicit HPostOrderIterator(const HGraph& graph) 4742 : graph_(graph), index_(graph_.GetReversePostOrder().Size()) { 4743 // Check that reverse post order of the graph has been built. 4744 DCHECK(!graph.GetReversePostOrder().IsEmpty()); 4745 } 4746 4747 bool Done() const { return index_ == 0; } 4748 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_ - 1); } 4749 void Advance() { --index_; } 4750 4751 private: 4752 const HGraph& graph_; 4753 size_t index_; 4754 4755 DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); 4756}; 4757 4758class HLinearPostOrderIterator : public ValueObject { 4759 public: 4760 explicit HLinearPostOrderIterator(const HGraph& graph) 4761 : order_(graph.GetLinearOrder()), index_(graph.GetLinearOrder().Size()) {} 4762 4763 bool Done() const { return index_ == 0; } 4764 4765 HBasicBlock* Current() const { return order_.Get(index_ -1); } 4766 4767 void Advance() { 4768 --index_; 4769 DCHECK_GE(index_, 0U); 4770 } 4771 4772 private: 4773 const GrowableArray<HBasicBlock*>& order_; 4774 size_t index_; 4775 4776 DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator); 4777}; 4778 4779class HLinearOrderIterator : public ValueObject { 4780 public: 4781 explicit HLinearOrderIterator(const HGraph& graph) 4782 : order_(graph.GetLinearOrder()), index_(0) {} 4783 4784 bool Done() const { return index_ == order_.Size(); } 4785 HBasicBlock* Current() const { return order_.Get(index_); } 4786 void Advance() { ++index_; } 4787 4788 private: 4789 const GrowableArray<HBasicBlock*>& order_; 4790 size_t index_; 4791 4792 DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator); 4793}; 4794 4795// Iterator over the blocks that art part of the loop. Includes blocks part 4796// of an inner loop. The order in which the blocks are iterated is on their 4797// block id. 4798class HBlocksInLoopIterator : public ValueObject { 4799 public: 4800 explicit HBlocksInLoopIterator(const HLoopInformation& info) 4801 : blocks_in_loop_(info.GetBlocks()), 4802 blocks_(info.GetHeader()->GetGraph()->GetBlocks()), 4803 index_(0) { 4804 if (!blocks_in_loop_.IsBitSet(index_)) { 4805 Advance(); 4806 } 4807 } 4808 4809 bool Done() const { return index_ == blocks_.Size(); } 4810 HBasicBlock* Current() const { return blocks_.Get(index_); } 4811 void Advance() { 4812 ++index_; 4813 for (size_t e = blocks_.Size(); index_ < e; ++index_) { 4814 if (blocks_in_loop_.IsBitSet(index_)) { 4815 break; 4816 } 4817 } 4818 } 4819 4820 private: 4821 const BitVector& blocks_in_loop_; 4822 const GrowableArray<HBasicBlock*>& blocks_; 4823 size_t index_; 4824 4825 DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopIterator); 4826}; 4827 4828// Iterator over the blocks that art part of the loop. Includes blocks part 4829// of an inner loop. The order in which the blocks are iterated is reverse 4830// post order. 4831class HBlocksInLoopReversePostOrderIterator : public ValueObject { 4832 public: 4833 explicit HBlocksInLoopReversePostOrderIterator(const HLoopInformation& info) 4834 : blocks_in_loop_(info.GetBlocks()), 4835 blocks_(info.GetHeader()->GetGraph()->GetReversePostOrder()), 4836 index_(0) { 4837 if (!blocks_in_loop_.IsBitSet(blocks_.Get(index_)->GetBlockId())) { 4838 Advance(); 4839 } 4840 } 4841 4842 bool Done() const { return index_ == blocks_.Size(); } 4843 HBasicBlock* Current() const { return blocks_.Get(index_); } 4844 void Advance() { 4845 ++index_; 4846 for (size_t e = blocks_.Size(); index_ < e; ++index_) { 4847 if (blocks_in_loop_.IsBitSet(blocks_.Get(index_)->GetBlockId())) { 4848 break; 4849 } 4850 } 4851 } 4852 4853 private: 4854 const BitVector& blocks_in_loop_; 4855 const GrowableArray<HBasicBlock*>& blocks_; 4856 size_t index_; 4857 4858 DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopReversePostOrderIterator); 4859}; 4860 4861inline int64_t Int64FromConstant(HConstant* constant) { 4862 DCHECK(constant->IsIntConstant() || constant->IsLongConstant()); 4863 return constant->IsIntConstant() ? constant->AsIntConstant()->GetValue() 4864 : constant->AsLongConstant()->GetValue(); 4865} 4866 4867} // namespace art 4868 4869#endif // ART_COMPILER_OPTIMIZING_NODES_H_ 4870