| /* |
| * Copyright (C) 2014 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #ifndef ART_COMPILER_OPTIMIZING_NODES_H_ |
| #define ART_COMPILER_OPTIMIZING_NODES_H_ |
| |
| #include <algorithm> |
| #include <array> |
| #include <type_traits> |
| |
| #include "art_method.h" |
| #include "base/arena_allocator.h" |
| #include "base/arena_bit_vector.h" |
| #include "base/arena_containers.h" |
| #include "base/arena_object.h" |
| #include "base/array_ref.h" |
| #include "base/intrusive_forward_list.h" |
| #include "base/iteration_range.h" |
| #include "base/macros.h" |
| #include "base/mutex.h" |
| #include "base/quasi_atomic.h" |
| #include "base/stl_util.h" |
| #include "base/transform_array_ref.h" |
| #include "block_namer.h" |
| #include "class_root.h" |
| #include "compilation_kind.h" |
| #include "data_type.h" |
| #include "deoptimization_kind.h" |
| #include "dex/dex_file.h" |
| #include "dex/dex_file_types.h" |
| #include "dex/invoke_type.h" |
| #include "dex/method_reference.h" |
| #include "entrypoints/quick/quick_entrypoints_enum.h" |
| #include "handle.h" |
| #include "handle_cache.h" |
| #include "intrinsics_enum.h" |
| #include "locations.h" |
| #include "mirror/class.h" |
| #include "mirror/method_type.h" |
| #include "offsets.h" |
| #include "reference_type_info.h" |
| |
| namespace art HIDDEN { |
| |
| class ArenaStack; |
| class CodeGenerator; |
| class GraphChecker; |
| class HBasicBlock; |
| class HCondition; |
| class HConstructorFence; |
| class HCurrentMethod; |
| class HDoubleConstant; |
| class HEnvironment; |
| class HFloatConstant; |
| class HGraphBuilder; |
| class HGraphVisitor; |
| class HInstruction; |
| class HIntConstant; |
| class HInvoke; |
| class HLongConstant; |
| class HNullConstant; |
| class HParameterValue; |
| class HPhi; |
| class HSuspendCheck; |
| class HTryBoundary; |
| class HVecCondition; |
| class FieldInfo; |
| class LiveInterval; |
| class LocationSummary; |
| class ProfilingInfo; |
| class SlowPathCode; |
| class SsaBuilder; |
| |
| namespace mirror { |
| class DexCache; |
| } // namespace mirror |
| |
| static const int kDefaultNumberOfBlocks = 8; |
| static const int kDefaultNumberOfSuccessors = 2; |
| static const int kDefaultNumberOfPredecessors = 2; |
| static const int kDefaultNumberOfExceptionalPredecessors = 0; |
| static const int kDefaultNumberOfDominatedBlocks = 1; |
| static const int kDefaultNumberOfBackEdges = 1; |
| |
| // The maximum (meaningful) distance (31) that can be used in an integer shift/rotate operation. |
| static constexpr int32_t kMaxIntShiftDistance = 0x1f; |
| // The maximum (meaningful) distance (63) that can be used in a long shift/rotate operation. |
| static constexpr int32_t kMaxLongShiftDistance = 0x3f; |
| |
| static constexpr uint32_t kUnknownFieldIndex = static_cast<uint32_t>(-1); |
| static constexpr uint16_t kUnknownClassDefIndex = static_cast<uint16_t>(-1); |
| |
| static constexpr InvokeType kInvalidInvokeType = static_cast<InvokeType>(-1); |
| |
| static constexpr uint32_t kNoDexPc = -1; |
| |
| inline bool IsSameDexFile(const DexFile& lhs, const DexFile& rhs) { |
| // For the purposes of the compiler, the dex files must actually be the same object |
| // if we want to safely treat them as the same. This is especially important for JIT |
| // as custom class loaders can open the same underlying file (or memory) multiple |
| // times and provide different class resolution but no two class loaders should ever |
| // use the same DexFile object - doing so is an unsupported hack that can lead to |
| // all sorts of weird failures. |
| return &lhs == &rhs; |
| } |
| |
| enum IfCondition { |
| // All types. |
| kCondEQ, // == |
| kCondNE, // != |
| // Signed integers and floating-point numbers. |
| kCondLT, // < |
| kCondLE, // <= |
| kCondGT, // > |
| kCondGE, // >= |
| // Unsigned integers. |
| kCondB, // < |
| kCondBE, // <= |
| kCondA, // > |
| kCondAE, // >= |
| // First and last aliases. |
| kCondFirst = kCondEQ, |
| kCondLast = kCondAE, |
| }; |
| |
| enum GraphAnalysisResult { |
| kAnalysisSkipped, |
| kAnalysisInvalidBytecode, |
| kAnalysisFailThrowCatchLoop, |
| kAnalysisFailAmbiguousArrayOp, |
| kAnalysisFailIrreducibleLoopAndStringInit, |
| kAnalysisFailPhiEquivalentInOsr, |
| kAnalysisSuccess, |
| }; |
| |
| std::ostream& operator<<(std::ostream& os, GraphAnalysisResult ga); |
| |
| template <typename T> |
| static inline typename std::make_unsigned<T>::type MakeUnsigned(T x) { |
| return static_cast<typename std::make_unsigned<T>::type>(x); |
| } |
| |
| class HInstructionList : public ValueObject { |
| public: |
| HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {} |
| |
| void AddInstruction(HInstruction* instruction); |
| void RemoveInstruction(HInstruction* instruction); |
| |
| // Insert `instruction` before/after an existing instruction `cursor`. |
| void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); |
| void InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor); |
| |
| // Return true if this list contains `instruction`. |
| bool Contains(HInstruction* instruction) const; |
| |
| // Return true if `instruction1` is found before `instruction2` in |
| // this instruction list and false otherwise. Abort if none |
| // of these instructions is found. |
| bool FoundBefore(const HInstruction* instruction1, |
| const HInstruction* instruction2) const; |
| |
| bool IsEmpty() const { return first_instruction_ == nullptr; } |
| void Clear() { first_instruction_ = last_instruction_ = nullptr; } |
| |
| // Update the block of all instructions to be `block`. |
| void SetBlockOfInstructions(HBasicBlock* block) const; |
| |
| void AddAfter(HInstruction* cursor, const HInstructionList& instruction_list); |
| void AddBefore(HInstruction* cursor, const HInstructionList& instruction_list); |
| void Add(const HInstructionList& instruction_list); |
| |
| // Return the number of instructions in the list. This is an expensive operation. |
| size_t CountSize() const; |
| |
| private: |
| HInstruction* first_instruction_; |
| HInstruction* last_instruction_; |
| |
| friend class HBasicBlock; |
| friend class HGraph; |
| friend class HInstruction; |
| friend class HInstructionIterator; |
| friend class HInstructionIteratorHandleChanges; |
| friend class HBackwardInstructionIterator; |
| |
| DISALLOW_COPY_AND_ASSIGN(HInstructionList); |
| }; |
| |
| // Control-flow graph of a method. Contains a list of basic blocks. |
| class HGraph : public ArenaObject<kArenaAllocGraph> { |
| public: |
| HGraph(ArenaAllocator* allocator, |
| ArenaStack* arena_stack, |
| VariableSizedHandleScope* handles, |
| const DexFile& dex_file, |
| uint32_t method_idx, |
| InstructionSet instruction_set, |
| InvokeType invoke_type = kInvalidInvokeType, |
| bool dead_reference_safe = false, |
| bool debuggable = false, |
| CompilationKind compilation_kind = CompilationKind::kOptimized, |
| int start_instruction_id = 0) |
| : allocator_(allocator), |
| arena_stack_(arena_stack), |
| handle_cache_(handles), |
| blocks_(allocator->Adapter(kArenaAllocBlockList)), |
| reverse_post_order_(allocator->Adapter(kArenaAllocReversePostOrder)), |
| linear_order_(allocator->Adapter(kArenaAllocLinearOrder)), |
| entry_block_(nullptr), |
| exit_block_(nullptr), |
| number_of_vregs_(0), |
| number_of_in_vregs_(0), |
| temporaries_vreg_slots_(0), |
| has_bounds_checks_(false), |
| has_try_catch_(false), |
| has_monitor_operations_(false), |
| has_traditional_simd_(false), |
| has_predicated_simd_(false), |
| has_loops_(false), |
| has_irreducible_loops_(false), |
| has_direct_critical_native_call_(false), |
| has_always_throwing_invokes_(false), |
| dead_reference_safe_(dead_reference_safe), |
| debuggable_(debuggable), |
| current_instruction_id_(start_instruction_id), |
| dex_file_(dex_file), |
| method_idx_(method_idx), |
| invoke_type_(invoke_type), |
| in_ssa_form_(false), |
| number_of_cha_guards_(0), |
| instruction_set_(instruction_set), |
| cached_null_constant_(nullptr), |
| cached_int_constants_(std::less<int32_t>(), allocator->Adapter(kArenaAllocConstantsMap)), |
| cached_float_constants_(std::less<int32_t>(), allocator->Adapter(kArenaAllocConstantsMap)), |
| cached_long_constants_(std::less<int64_t>(), allocator->Adapter(kArenaAllocConstantsMap)), |
| cached_double_constants_(std::less<int64_t>(), allocator->Adapter(kArenaAllocConstantsMap)), |
| cached_current_method_(nullptr), |
| art_method_(nullptr), |
| compilation_kind_(compilation_kind), |
| useful_optimizing_(false), |
| cha_single_implementation_list_(allocator->Adapter(kArenaAllocCHA)) { |
| blocks_.reserve(kDefaultNumberOfBlocks); |
| } |
| |
| std::ostream& Dump(std::ostream& os, |
| CodeGenerator* codegen, |
| std::optional<std::reference_wrapper<const BlockNamer>> namer = std::nullopt); |
| |
| ArenaAllocator* GetAllocator() const { return allocator_; } |
| ArenaStack* GetArenaStack() const { return arena_stack_; } |
| |
| HandleCache* GetHandleCache() { return &handle_cache_; } |
| |
| const ArenaVector<HBasicBlock*>& GetBlocks() const { return blocks_; } |
| |
| // An iterator to only blocks that are still actually in the graph (when |
| // blocks are removed they are replaced with 'nullptr' in GetBlocks to |
| // simplify block-id assignment and avoid memmoves in the block-list). |
| IterationRange<FilterNull<ArenaVector<HBasicBlock*>::const_iterator>> GetActiveBlocks() const { |
| return FilterOutNull(MakeIterationRange(GetBlocks())); |
| } |
| |
| bool IsInSsaForm() const { return in_ssa_form_; } |
| void SetInSsaForm() { in_ssa_form_ = true; } |
| |
| HBasicBlock* GetEntryBlock() const { return entry_block_; } |
| HBasicBlock* GetExitBlock() const { return exit_block_; } |
| bool HasExitBlock() const { return exit_block_ != nullptr; } |
| |
| void SetEntryBlock(HBasicBlock* block) { entry_block_ = block; } |
| void SetExitBlock(HBasicBlock* block) { exit_block_ = block; } |
| |
| void AddBlock(HBasicBlock* block); |
| |
| void ComputeDominanceInformation(); |
| void ClearDominanceInformation(); |
| void ClearLoopInformation(); |
| void FindBackEdges(ArenaBitVector* visited); |
| GraphAnalysisResult BuildDominatorTree(); |
| GraphAnalysisResult RecomputeDominatorTree(); |
| void SimplifyCFG(); |
| void SimplifyCatchBlocks(); |
| |
| // Analyze all natural loops in this graph. Returns a code specifying that it |
| // was successful or the reason for failure. The method will fail if a loop |
| // is a throw-catch loop, i.e. the header is a catch block. |
| GraphAnalysisResult AnalyzeLoops() const; |
| |
| // Iterate over blocks to compute try block membership. Needs reverse post |
| // order and loop information. |
| void ComputeTryBlockInformation(); |
| |
| // Inline this graph in `outer_graph`, replacing the given `invoke` instruction. |
| // Returns the instruction to replace the invoke expression or null if the |
| // invoke is for a void method. Note that the caller is responsible for replacing |
| // and removing the invoke instruction. |
| HInstruction* InlineInto(HGraph* outer_graph, HInvoke* invoke); |
| |
| // Update the loop and try membership of `block`, which was spawned from `reference`. |
| // In case `reference` is a back edge, `replace_if_back_edge` notifies whether `block` |
| // should be the new back edge. |
| // `has_more_specific_try_catch_info` will be set to true when inlining a try catch. |
| void UpdateLoopAndTryInformationOfNewBlock(HBasicBlock* block, |
| HBasicBlock* reference, |
| bool replace_if_back_edge, |
| bool has_more_specific_try_catch_info = false); |
| |
| // Need to add a couple of blocks to test if the loop body is entered and |
| // put deoptimization instructions, etc. |
| void TransformLoopHeaderForBCE(HBasicBlock* header); |
| |
| // Adds a new loop directly after the loop with the given header and exit. |
| // Returns the new preheader. |
| HBasicBlock* TransformLoopForVectorization(HBasicBlock* header, |
| HBasicBlock* body, |
| HBasicBlock* exit); |
| |
| // Removes `block` from the graph. Assumes `block` has been disconnected from |
| // other blocks and has no instructions or phis. |
| void DeleteDeadEmptyBlock(HBasicBlock* block); |
| |
| // Splits the edge between `block` and `successor` while preserving the |
| // indices in the predecessor/successor lists. If there are multiple edges |
| // between the blocks, the lowest indices are used. |
| // Returns the new block which is empty and has the same dex pc as `successor`. |
| HBasicBlock* SplitEdge(HBasicBlock* block, HBasicBlock* successor); |
| |
| void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor); |
| |
| // Splits the edge between `block` and `successor` and then updates the graph's RPO to keep |
| // consistency without recomputing the whole graph. |
| HBasicBlock* SplitEdgeAndUpdateRPO(HBasicBlock* block, HBasicBlock* successor); |
| |
| void OrderLoopHeaderPredecessors(HBasicBlock* header); |
| |
| // Transform a loop into a format with a single preheader. |
| // |
| // Each phi in the header should be split: original one in the header should only hold |
| // inputs reachable from the back edges and a single input from the preheader. The newly created |
| // phi in the preheader should collate the inputs from the original multiple incoming blocks. |
| // |
| // Loops in the graph typically have a single preheader, so this method is used to "repair" loops |
| // that no longer have this property. |
| void TransformLoopToSinglePreheaderFormat(HBasicBlock* header); |
| |
| void SimplifyLoop(HBasicBlock* header); |
| |
| int32_t GetNextInstructionId() { |
| CHECK_NE(current_instruction_id_, INT32_MAX); |
| return current_instruction_id_++; |
| } |
| |
| int32_t GetCurrentInstructionId() const { |
| return current_instruction_id_; |
| } |
| |
| void SetCurrentInstructionId(int32_t id) { |
| CHECK_GE(id, current_instruction_id_); |
| current_instruction_id_ = id; |
| } |
| |
| void UpdateTemporariesVRegSlots(size_t slots) { |
| temporaries_vreg_slots_ = std::max(slots, temporaries_vreg_slots_); |
| } |
| |
| size_t GetTemporariesVRegSlots() const { |
| DCHECK(!in_ssa_form_); |
| return temporaries_vreg_slots_; |
| } |
| |
| void SetNumberOfVRegs(uint16_t number_of_vregs) { |
| number_of_vregs_ = number_of_vregs; |
| } |
| |
| uint16_t GetNumberOfVRegs() const { |
| return number_of_vregs_; |
| } |
| |
| void SetNumberOfInVRegs(uint16_t value) { |
| number_of_in_vregs_ = value; |
| } |
| |
| uint16_t GetNumberOfInVRegs() const { |
| return number_of_in_vregs_; |
| } |
| |
| uint16_t GetNumberOfLocalVRegs() const { |
| DCHECK(!in_ssa_form_); |
| return number_of_vregs_ - number_of_in_vregs_; |
| } |
| |
| const ArenaVector<HBasicBlock*>& GetReversePostOrder() const { |
| return reverse_post_order_; |
| } |
| |
| ArrayRef<HBasicBlock* const> GetReversePostOrderSkipEntryBlock() const { |
| DCHECK(GetReversePostOrder()[0] == entry_block_); |
| return ArrayRef<HBasicBlock* const>(GetReversePostOrder()).SubArray(1); |
| } |
| |
| IterationRange<ArenaVector<HBasicBlock*>::const_reverse_iterator> GetPostOrder() const { |
| return ReverseRange(GetReversePostOrder()); |
| } |
| |
| const ArenaVector<HBasicBlock*>& GetLinearOrder() const { |
| return linear_order_; |
| } |
| |
| IterationRange<ArenaVector<HBasicBlock*>::const_reverse_iterator> GetLinearPostOrder() const { |
| return ReverseRange(GetLinearOrder()); |
| } |
| |
| bool HasBoundsChecks() const { |
| return has_bounds_checks_; |
| } |
| |
| void SetHasBoundsChecks(bool value) { |
| has_bounds_checks_ = value; |
| } |
| |
| // Is the code known to be robust against eliminating dead references |
| // and the effects of early finalization? |
| bool IsDeadReferenceSafe() const { return dead_reference_safe_; } |
| |
| void MarkDeadReferenceUnsafe() { dead_reference_safe_ = false; } |
| |
| bool IsDebuggable() const { return debuggable_; } |
| |
| // Returns a constant of the given type and value. If it does not exist |
| // already, it is created and inserted into the graph. This method is only for |
| // integral types. |
| HConstant* GetConstant(DataType::Type type, int64_t value); |
| |
| // TODO: This is problematic for the consistency of reference type propagation |
| // because it can be created anytime after the pass and thus it will be left |
| // with an invalid type. |
| HNullConstant* GetNullConstant(); |
| |
| HIntConstant* GetIntConstant(int32_t value); |
| HLongConstant* GetLongConstant(int64_t value); |
| HFloatConstant* GetFloatConstant(float value); |
| HDoubleConstant* GetDoubleConstant(double value); |
| |
| HCurrentMethod* GetCurrentMethod(); |
| |
| const DexFile& GetDexFile() const { |
| return dex_file_; |
| } |
| |
| uint32_t GetMethodIdx() const { |
| return method_idx_; |
| } |
| |
| // Get the method name (without the signature), e.g. "<init>" |
| const char* GetMethodName() const; |
| |
| // Get the pretty method name (class + name + optionally signature). |
| std::string PrettyMethod(bool with_signature = true) const; |
| |
| InvokeType GetInvokeType() const { |
| return invoke_type_; |
| } |
| |
| InstructionSet GetInstructionSet() const { |
| return instruction_set_; |
| } |
| |
| bool IsCompilingOsr() const { return compilation_kind_ == CompilationKind::kOsr; } |
| |
| bool IsCompilingBaseline() const { return compilation_kind_ == CompilationKind::kBaseline; } |
| |
| CompilationKind GetCompilationKind() const { return compilation_kind_; } |
| |
| ArenaSet<ArtMethod*>& GetCHASingleImplementationList() { |
| return cha_single_implementation_list_; |
| } |
| |
| // In case of OSR we intend to use SuspendChecks as an entry point to the |
| // function; for debuggable graphs we might deoptimize to interpreter from |
| // SuspendChecks. In these cases we should always generate code for them. |
| bool SuspendChecksAreAllowedToNoOp() const { |
| return !IsDebuggable() && !IsCompilingOsr(); |
| } |
| |
| void AddCHASingleImplementationDependency(ArtMethod* method) { |
| cha_single_implementation_list_.insert(method); |
| } |
| |
| bool HasShouldDeoptimizeFlag() const { |
| return number_of_cha_guards_ != 0 || debuggable_; |
| } |
| |
| bool HasTryCatch() const { return has_try_catch_; } |
| void SetHasTryCatch(bool value) { has_try_catch_ = value; } |
| |
| bool HasMonitorOperations() const { return has_monitor_operations_; } |
| void SetHasMonitorOperations(bool value) { has_monitor_operations_ = value; } |
| |
| bool HasTraditionalSIMD() { return has_traditional_simd_; } |
| void SetHasTraditionalSIMD(bool value) { has_traditional_simd_ = value; } |
| |
| bool HasPredicatedSIMD() { return has_predicated_simd_; } |
| void SetHasPredicatedSIMD(bool value) { has_predicated_simd_ = value; } |
| |
| bool HasSIMD() const { return has_traditional_simd_ || has_predicated_simd_; } |
| |
| bool HasLoops() const { return has_loops_; } |
| void SetHasLoops(bool value) { has_loops_ = value; } |
| |
| bool HasIrreducibleLoops() const { return has_irreducible_loops_; } |
| void SetHasIrreducibleLoops(bool value) { has_irreducible_loops_ = value; } |
| |
| bool HasDirectCriticalNativeCall() const { return has_direct_critical_native_call_; } |
| void SetHasDirectCriticalNativeCall(bool value) { has_direct_critical_native_call_ = value; } |
| |
| bool HasAlwaysThrowingInvokes() const { return has_always_throwing_invokes_; } |
| void SetHasAlwaysThrowingInvokes(bool value) { has_always_throwing_invokes_ = value; } |
| |
| ArtMethod* GetArtMethod() const { return art_method_; } |
| void SetArtMethod(ArtMethod* method) { art_method_ = method; } |
| |
| void SetProfilingInfo(ProfilingInfo* info) { profiling_info_ = info; } |
| ProfilingInfo* GetProfilingInfo() const { return profiling_info_; } |
| |
| ReferenceTypeInfo GetInexactObjectRti() { |
| return ReferenceTypeInfo::Create(handle_cache_.GetObjectClassHandle(), /* is_exact= */ false); |
| } |
| |
| uint32_t GetNumberOfCHAGuards() const { return number_of_cha_guards_; } |
| void SetNumberOfCHAGuards(uint32_t num) { number_of_cha_guards_ = num; } |
| void IncrementNumberOfCHAGuards() { number_of_cha_guards_++; } |
| |
| void SetUsefulOptimizing() { useful_optimizing_ = true; } |
| bool IsUsefulOptimizing() const { return useful_optimizing_; } |
| |
| private: |
| void RemoveDeadBlocksInstructionsAsUsersAndDisconnect(const ArenaBitVector& visited) const; |
| void RemoveDeadBlocks(const ArenaBitVector& visited); |
| |
| template <class InstructionType, typename ValueType> |
| InstructionType* CreateConstant(ValueType value, |
| ArenaSafeMap<ValueType, InstructionType*>* cache); |
| |
| void InsertConstant(HConstant* instruction); |
| |
| // Cache a float constant into the graph. This method should only be |
| // called by the SsaBuilder when creating "equivalent" instructions. |
| void CacheFloatConstant(HFloatConstant* constant); |
| |
| // See CacheFloatConstant comment. |
| void CacheDoubleConstant(HDoubleConstant* constant); |
| |
| ArenaAllocator* const allocator_; |
| ArenaStack* const arena_stack_; |
| |
| HandleCache handle_cache_; |
| |
| // List of blocks in insertion order. |
| ArenaVector<HBasicBlock*> blocks_; |
| |
| // List of blocks to perform a reverse post order tree traversal. |
| ArenaVector<HBasicBlock*> reverse_post_order_; |
| |
| // List of blocks to perform a linear order tree traversal. Unlike the reverse |
| // post order, this order is not incrementally kept up-to-date. |
| ArenaVector<HBasicBlock*> linear_order_; |
| |
| HBasicBlock* entry_block_; |
| HBasicBlock* exit_block_; |
| |
| // The number of virtual registers in this method. Contains the parameters. |
| uint16_t number_of_vregs_; |
| |
| // The number of virtual registers used by parameters of this method. |
| uint16_t number_of_in_vregs_; |
| |
| // Number of vreg size slots that the temporaries use (used in baseline compiler). |
| size_t temporaries_vreg_slots_; |
| |
| // Flag whether there are bounds checks in the graph. We can skip |
| // BCE if it's false. |
| bool has_bounds_checks_; |
| |
| // Flag whether there are try/catch blocks in the graph. We will skip |
| // try/catch-related passes if it's false. |
| bool has_try_catch_; |
| |
| // Flag whether there are any HMonitorOperation in the graph. If yes this will mandate |
| // DexRegisterMap to be present to allow deadlock analysis for non-debuggable code. |
| bool has_monitor_operations_; |
| |
| // Flags whether SIMD (traditional or predicated) instructions appear in the graph. |
| // If either is true, the code generators may have to be more careful spilling the wider |
| // contents of SIMD registers. |
| bool has_traditional_simd_; |
| bool has_predicated_simd_; |
| |
| // Flag whether there are any loops in the graph. We can skip loop |
| // optimization if it's false. |
| bool has_loops_; |
| |
| // Flag whether there are any irreducible loops in the graph. |
| bool has_irreducible_loops_; |
| |
| // Flag whether there are any direct calls to native code registered |
| // for @CriticalNative methods. |
| bool has_direct_critical_native_call_; |
| |
| // Flag whether the graph contains invokes that always throw. |
| bool has_always_throwing_invokes_; |
| |
| // Is the code known to be robust against eliminating dead references |
| // and the effects of early finalization? If false, dead reference variables |
| // are kept if they might be visible to the garbage collector. |
| // Currently this means that the class was declared to be dead-reference-safe, |
| // the method accesses no reachability-sensitive fields or data, and the same |
| // is true for any methods that were inlined into the current one. |
| bool dead_reference_safe_; |
| |
| // Indicates whether the graph should be compiled in a way that |
| // ensures full debuggability. If false, we can apply more |
| // aggressive optimizations that may limit the level of debugging. |
| const bool debuggable_; |
| |
| // The current id to assign to a newly added instruction. See HInstruction.id_. |
| int32_t current_instruction_id_; |
| |
| // The dex file from which the method is from. |
| const DexFile& dex_file_; |
| |
| // The method index in the dex file. |
| const uint32_t method_idx_; |
| |
| // If inlined, this encodes how the callee is being invoked. |
| const InvokeType invoke_type_; |
| |
| // Whether the graph has been transformed to SSA form. Only used |
| // in debug mode to ensure we are not using properties only valid |
| // for non-SSA form (like the number of temporaries). |
| bool in_ssa_form_; |
| |
| // Number of CHA guards in the graph. Used to short-circuit the |
| // CHA guard optimization pass when there is no CHA guard left. |
| uint32_t number_of_cha_guards_; |
| |
| const InstructionSet instruction_set_; |
| |
| // Cached constants. |
| HNullConstant* cached_null_constant_; |
| ArenaSafeMap<int32_t, HIntConstant*> cached_int_constants_; |
| ArenaSafeMap<int32_t, HFloatConstant*> cached_float_constants_; |
| ArenaSafeMap<int64_t, HLongConstant*> cached_long_constants_; |
| ArenaSafeMap<int64_t, HDoubleConstant*> cached_double_constants_; |
| |
| HCurrentMethod* cached_current_method_; |
| |
| // The ArtMethod this graph is for. Note that for AOT, it may be null, |
| // for example for methods whose declaring class could not be resolved |
| // (such as when the superclass could not be found). |
| ArtMethod* art_method_; |
| |
| // The `ProfilingInfo` associated with the method being compiled. |
| ProfilingInfo* profiling_info_; |
| |
| // How we are compiling the graph: either optimized, osr, or baseline. |
| // For osr, we will make all loops seen as irreducible and emit special |
| // stack maps to mark compiled code entries which the interpreter can |
| // directly jump to. |
| const CompilationKind compilation_kind_; |
| |
| // Whether after compiling baseline it is still useful re-optimizing this |
| // method. |
| bool useful_optimizing_; |
| |
| // List of methods that are assumed to have single implementation. |
| ArenaSet<ArtMethod*> cha_single_implementation_list_; |
| |
| friend class SsaBuilder; // For caching constants. |
| friend class SsaLivenessAnalysis; // For the linear order. |
| friend class HInliner; // For the reverse post order. |
| ART_FRIEND_TEST(GraphTest, IfSuccessorSimpleJoinBlock1); |
| DISALLOW_COPY_AND_ASSIGN(HGraph); |
| }; |
| |
| class HLoopInformation : public ArenaObject<kArenaAllocLoopInfo> { |
| public: |
| HLoopInformation(HBasicBlock* header, HGraph* graph) |
| : header_(header), |
| suspend_check_(nullptr), |
| irreducible_(false), |
| contains_irreducible_loop_(false), |
| back_edges_(graph->GetAllocator()->Adapter(kArenaAllocLoopInfoBackEdges)), |
| // Make bit vector growable, as the number of blocks may change. |
| blocks_(graph->GetAllocator(), |
| graph->GetBlocks().size(), |
| true, |
| kArenaAllocLoopInfoBackEdges) { |
| back_edges_.reserve(kDefaultNumberOfBackEdges); |
| } |
| |
| bool IsIrreducible() const { return irreducible_; } |
| bool ContainsIrreducibleLoop() const { return contains_irreducible_loop_; } |
| |
| void Dump(std::ostream& os); |
| |
| HBasicBlock* GetHeader() const { |
| return header_; |
| } |
| |
| void SetHeader(HBasicBlock* block) { |
| header_ = block; |
| } |
| |
| HSuspendCheck* GetSuspendCheck() const { return suspend_check_; } |
| void SetSuspendCheck(HSuspendCheck* check) { suspend_check_ = check; } |
| bool HasSuspendCheck() const { return suspend_check_ != nullptr; } |
| |
| void AddBackEdge(HBasicBlock* back_edge) { |
| back_edges_.push_back(back_edge); |
| } |
| |
| void RemoveBackEdge(HBasicBlock* back_edge) { |
| RemoveElement(back_edges_, back_edge); |
| } |
| |
| bool IsBackEdge(const HBasicBlock& block) const { |
| return ContainsElement(back_edges_, &block); |
| } |
| |
| size_t NumberOfBackEdges() const { |
| return back_edges_.size(); |
| } |
| |
| HBasicBlock* GetPreHeader() const; |
| |
| const ArenaVector<HBasicBlock*>& GetBackEdges() const { |
| return back_edges_; |
| } |
| |
| // Returns the lifetime position of the back edge that has the |
| // greatest lifetime position. |
| size_t GetLifetimeEnd() const; |
| |
| void ReplaceBackEdge(HBasicBlock* existing, HBasicBlock* new_back_edge) { |
| ReplaceElement(back_edges_, existing, new_back_edge); |
| } |
| |
| // Finds blocks that are part of this loop. |
| void Populate(); |
| |
| // Updates blocks population of the loop and all of its outer' ones recursively after the |
| // population of the inner loop is updated. |
| void PopulateInnerLoopUpwards(HLoopInformation* inner_loop); |
| |
| // Returns whether this loop information contains `block`. |
| // Note that this loop information *must* be populated before entering this function. |
| bool Contains(const HBasicBlock& block) const; |
| |
| // Returns whether this loop information is an inner loop of `other`. |
| // Note that `other` *must* be populated before entering this function. |
| bool IsIn(const HLoopInformation& other) const; |
| |
| // Returns true if instruction is not defined within this loop. |
| bool IsDefinedOutOfTheLoop(HInstruction* instruction) const; |
| |
| const ArenaBitVector& GetBlocks() const { return blocks_; } |
| |
| void Add(HBasicBlock* block); |
| void Remove(HBasicBlock* block); |
| |
| void ClearAllBlocks() { |
| blocks_.ClearAllBits(); |
| } |
| |
| bool HasBackEdgeNotDominatedByHeader() const; |
| |
| bool IsPopulated() const { |
| return blocks_.GetHighestBitSet() != -1; |
| } |
| |
| bool DominatesAllBackEdges(HBasicBlock* block); |
| |
| bool HasExitEdge() const; |
| |
| // Resets back edge and blocks-in-loop data. |
| void ResetBasicBlockData() { |
| back_edges_.clear(); |
| ClearAllBlocks(); |
| } |
| |
| private: |
| // Internal recursive implementation of `Populate`. |
| void PopulateRecursive(HBasicBlock* block); |
| void PopulateIrreducibleRecursive(HBasicBlock* block, ArenaBitVector* finalized); |
| |
| HBasicBlock* header_; |
| HSuspendCheck* suspend_check_; |
| bool irreducible_; |
| bool contains_irreducible_loop_; |
| ArenaVector<HBasicBlock*> back_edges_; |
| ArenaBitVector blocks_; |
| |
| DISALLOW_COPY_AND_ASSIGN(HLoopInformation); |
| }; |
| |
| // Stores try/catch information for basic blocks. |
| // Note that HGraph is constructed so that catch blocks cannot simultaneously |
| // be try blocks. |
| class TryCatchInformation : public ArenaObject<kArenaAllocTryCatchInfo> { |
| public: |
| // Try block information constructor. |
| explicit TryCatchInformation(const HTryBoundary& try_entry) |
| : try_entry_(&try_entry), |
| catch_dex_file_(nullptr), |
| catch_type_index_(dex::TypeIndex::Invalid()) { |
| DCHECK(try_entry_ != nullptr); |
| } |
| |
| // Catch block information constructor. |
| TryCatchInformation(dex::TypeIndex catch_type_index, const DexFile& dex_file) |
| : try_entry_(nullptr), |
| catch_dex_file_(&dex_file), |
| catch_type_index_(catch_type_index) {} |
| |
| bool IsTryBlock() const { return try_entry_ != nullptr; } |
| |
| const HTryBoundary& GetTryEntry() const { |
| DCHECK(IsTryBlock()); |
| return *try_entry_; |
| } |
| |
| bool IsCatchBlock() const { return catch_dex_file_ != nullptr; } |
| |
| bool IsValidTypeIndex() const { |
| DCHECK(IsCatchBlock()); |
| return catch_type_index_.IsValid(); |
| } |
| |
| dex::TypeIndex GetCatchTypeIndex() const { |
| DCHECK(IsCatchBlock()); |
| return catch_type_index_; |
| } |
| |
| const DexFile& GetCatchDexFile() const { |
| DCHECK(IsCatchBlock()); |
| return *catch_dex_file_; |
| } |
| |
| void SetInvalidTypeIndex() { |
| catch_type_index_ = dex::TypeIndex::Invalid(); |
| } |
| |
| private: |
| // One of possibly several TryBoundary instructions entering the block's try. |
| // Only set for try blocks. |
| const HTryBoundary* try_entry_; |
| |
| // Exception type information. Only set for catch blocks. |
| const DexFile* catch_dex_file_; |
| dex::TypeIndex catch_type_index_; |
| }; |
| |
| static constexpr size_t kNoLifetime = -1; |
| static constexpr uint32_t kInvalidBlockId = static_cast<uint32_t>(-1); |
| |
| // A block in a method. Contains the list of instructions represented |
| // as a double linked list. Each block knows its predecessors and |
| // successors. |
| |
| class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> { |
| public: |
| explicit HBasicBlock(HGraph* graph, uint32_t dex_pc = kNoDexPc) |
| : graph_(graph), |
| predecessors_(graph->GetAllocator()->Adapter(kArenaAllocPredecessors)), |
| successors_(graph->GetAllocator()->Adapter(kArenaAllocSuccessors)), |
| loop_information_(nullptr), |
| dominator_(nullptr), |
| dominated_blocks_(graph->GetAllocator()->Adapter(kArenaAllocDominated)), |
| block_id_(kInvalidBlockId), |
| dex_pc_(dex_pc), |
| lifetime_start_(kNoLifetime), |
| lifetime_end_(kNoLifetime), |
| try_catch_information_(nullptr) { |
| predecessors_.reserve(kDefaultNumberOfPredecessors); |
| successors_.reserve(kDefaultNumberOfSuccessors); |
| dominated_blocks_.reserve(kDefaultNumberOfDominatedBlocks); |
| } |
| |
| const ArenaVector<HBasicBlock*>& GetPredecessors() const { |
| return predecessors_; |
| } |
| |
| size_t GetNumberOfPredecessors() const { |
| return GetPredecessors().size(); |
| } |
| |
| const ArenaVector<HBasicBlock*>& GetSuccessors() const { |
| return successors_; |
| } |
| |
| ArrayRef<HBasicBlock* const> GetNormalSuccessors() const; |
| ArrayRef<HBasicBlock* const> GetExceptionalSuccessors() const; |
| |
| bool HasSuccessor(const HBasicBlock* block, size_t start_from = 0u) { |
| return ContainsElement(successors_, block, start_from); |
| } |
| |
| const ArenaVector<HBasicBlock*>& GetDominatedBlocks() const { |
| return dominated_blocks_; |
| } |
| |
| bool IsEntryBlock() const { |
| return graph_->GetEntryBlock() == this; |
| } |
| |
| bool IsExitBlock() const { |
| return graph_->GetExitBlock() == this; |
| } |
| |
| bool IsSingleGoto() const; |
| bool IsSingleReturn() const; |
| bool IsSingleReturnOrReturnVoidAllowingPhis() const; |
| bool IsSingleTryBoundary() const; |
| |
| // Returns true if this block emits nothing but a jump. |
| bool IsSingleJump() const { |
| HLoopInformation* loop_info = GetLoopInformation(); |
| return (IsSingleGoto() || IsSingleTryBoundary()) |
| // Back edges generate a suspend check. |
| && (loop_info == nullptr || !loop_info->IsBackEdge(*this)); |
| } |
| |
| void AddBackEdge(HBasicBlock* back_edge) { |
| if (loop_information_ == nullptr) { |
| loop_information_ = new (graph_->GetAllocator()) HLoopInformation(this, graph_); |
| } |
| DCHECK_EQ(loop_information_->GetHeader(), this); |
| loop_information_->AddBackEdge(back_edge); |
| } |
| |
| // Registers a back edge; if the block was not a loop header before the call associates a newly |
| // created loop info with it. |
| // |
| // Used in SuperblockCloner to preserve LoopInformation object instead of reseting loop |
| // info for all blocks during back edges recalculation. |
| void AddBackEdgeWhileUpdating(HBasicBlock* back_edge) { |
| if (loop_information_ == nullptr || loop_information_->GetHeader() != this) { |
| loop_information_ = new (graph_->GetAllocator()) HLoopInformation(this, graph_); |
| } |
| loop_information_->AddBackEdge(back_edge); |
| } |
| |
| HGraph* GetGraph() const { return graph_; } |
| void SetGraph(HGraph* graph) { graph_ = graph; } |
| |
| uint32_t GetBlockId() const { return block_id_; } |
| void SetBlockId(int id) { block_id_ = id; } |
| uint32_t GetDexPc() const { return dex_pc_; } |
| |
| HBasicBlock* GetDominator() const { return dominator_; } |
| void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; } |
| void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.push_back(block); } |
| |
| void RemoveDominatedBlock(HBasicBlock* block) { |
| RemoveElement(dominated_blocks_, block); |
| } |
| |
| void ReplaceDominatedBlock(HBasicBlock* existing, HBasicBlock* new_block) { |
| ReplaceElement(dominated_blocks_, existing, new_block); |
| } |
| |
| void ClearDominanceInformation(); |
| |
| int NumberOfBackEdges() const { |
| return IsLoopHeader() ? loop_information_->NumberOfBackEdges() : 0; |
| } |
| |
| HInstruction* GetFirstInstruction() const { return instructions_.first_instruction_; } |
| HInstruction* GetLastInstruction() const { return instructions_.last_instruction_; } |
| const HInstructionList& GetInstructions() const { return instructions_; } |
| HInstruction* GetFirstPhi() const { return phis_.first_instruction_; } |
| HInstruction* GetLastPhi() const { return phis_.last_instruction_; } |
| const HInstructionList& GetPhis() const { return phis_; } |
| |
| HInstruction* GetFirstInstructionDisregardMoves() const; |
| |
| void AddSuccessor(HBasicBlock* block) { |
| successors_.push_back(block); |
| block->predecessors_.push_back(this); |
| } |
| |
| void ReplaceSuccessor(HBasicBlock* existing, HBasicBlock* new_block) { |
| size_t successor_index = GetSuccessorIndexOf(existing); |
| existing->RemovePredecessor(this); |
| new_block->predecessors_.push_back(this); |
| successors_[successor_index] = new_block; |
| } |
| |
| void ReplacePredecessor(HBasicBlock* existing, HBasicBlock* new_block) { |
| size_t predecessor_index = GetPredecessorIndexOf(existing); |
| existing->RemoveSuccessor(this); |
| new_block->successors_.push_back(this); |
| predecessors_[predecessor_index] = new_block; |
| } |
| |
| // Insert `this` between `predecessor` and `successor. This method |
| // preserves the indices, and will update the first edge found between |
| // `predecessor` and `successor`. |
| void InsertBetween(HBasicBlock* predecessor, HBasicBlock* successor) { |
| size_t predecessor_index = successor->GetPredecessorIndexOf(predecessor); |
| size_t successor_index = predecessor->GetSuccessorIndexOf(successor); |
| successor->predecessors_[predecessor_index] = this; |
| predecessor->successors_[successor_index] = this; |
| successors_.push_back(successor); |
| predecessors_.push_back(predecessor); |
| } |
| |
| void RemovePredecessor(HBasicBlock* block) { |
| predecessors_.erase(predecessors_.begin() + GetPredecessorIndexOf(block)); |
| } |
| |
| void RemoveSuccessor(HBasicBlock* block) { |
| successors_.erase(successors_.begin() + GetSuccessorIndexOf(block)); |
| } |
| |
| void ClearAllPredecessors() { |
| predecessors_.clear(); |
| } |
| |
| void AddPredecessor(HBasicBlock* block) { |
| predecessors_.push_back(block); |
| block->successors_.push_back(this); |
| } |
| |
| void SwapPredecessors() { |
| DCHECK_EQ(predecessors_.size(), 2u); |
| std::swap(predecessors_[0], predecessors_[1]); |
| } |
| |
| void SwapSuccessors() { |
| DCHECK_EQ(successors_.size(), 2u); |
| std::swap(successors_[0], successors_[1]); |
| } |
| |
| size_t GetPredecessorIndexOf(HBasicBlock* predecessor) const { |
| return IndexOfElement(predecessors_, predecessor); |
| } |
| |
| size_t GetSuccessorIndexOf(HBasicBlock* successor) const { |
| return IndexOfElement(successors_, successor); |
| } |
| |
| HBasicBlock* GetSinglePredecessor() const { |
| DCHECK_EQ(GetPredecessors().size(), 1u); |
| return GetPredecessors()[0]; |
| } |
| |
| HBasicBlock* GetSingleSuccessor() const { |
| DCHECK_EQ(GetSuccessors().size(), 1u); |
| return GetSuccessors()[0]; |
| } |
| |
| // Returns whether the first occurrence of `predecessor` in the list of |
| // predecessors is at index `idx`. |
| bool IsFirstIndexOfPredecessor(HBasicBlock* predecessor, size_t idx) const { |
| DCHECK_EQ(GetPredecessors()[idx], predecessor); |
| return GetPredecessorIndexOf(predecessor) == idx; |
| } |
| |
| // Create a new block between this block and its predecessors. The new block |
| // is added to the graph, all predecessor edges are relinked to it and an edge |
| // is created to `this`. Returns the new empty block. Reverse post order or |
| // loop and try/catch information are not updated. |
| HBasicBlock* CreateImmediateDominator(); |
| |
| // Split the block into two blocks just before `cursor`. Returns the newly |
| // created, latter block. Note that this method will add the block to the |
| // graph, create a Goto at the end of the former block and will create an edge |
| // between the blocks. It will not, however, update the reverse post order or |
| // loop and try/catch information. |
| HBasicBlock* SplitBefore(HInstruction* cursor, bool require_graph_not_in_ssa_form = true); |
| |
| // Split the block into two blocks just before `cursor`. Returns the newly |
| // created block. Note that this method just updates raw block information, |
| // like predecessors, successors, dominators, and instruction list. It does not |
| // update the graph, reverse post order, loop information, nor make sure the |
| // blocks are consistent (for example ending with a control flow instruction). |
| HBasicBlock* SplitBeforeForInlining(HInstruction* cursor); |
| |
| // Similar to `SplitBeforeForInlining` but does it after `cursor`. |
| HBasicBlock* SplitAfterForInlining(HInstruction* cursor); |
| |
| // Merge `other` at the end of `this`. Successors and dominated blocks of |
| // `other` are changed to be successors and dominated blocks of `this`. Note |
| // that this method does not update the graph, reverse post order, loop |
| // information, nor make sure the blocks are consistent (for example ending |
| // with a control flow instruction). |
| void MergeWithInlined(HBasicBlock* other); |
| |
| // Replace `this` with `other`. Predecessors, successors, and dominated blocks |
| // of `this` are moved to `other`. |
| // Note that this method does not update the graph, reverse post order, loop |
| // information, nor make sure the blocks are consistent (for example ending |
| // with a control flow instruction). |
| void ReplaceWith(HBasicBlock* other); |
| |
| // Merges the instructions of `other` at the end of `this`. |
| void MergeInstructionsWith(HBasicBlock* other); |
| |
| // Merge `other` at the end of `this`. This method updates loops, reverse post |
| // order, links to predecessors, successors, dominators and deletes the block |
| // from the graph. The two blocks must be successive, i.e. `this` the only |
| // predecessor of `other` and vice versa. |
| void MergeWith(HBasicBlock* other); |
| |
| // Disconnects `this` from all its predecessors, successors and dominator, |
| // removes it from all loops it is included in and eventually from the graph. |
| // The block must not dominate any other block. Predecessors and successors |
| // are safely updated. |
| void DisconnectAndDelete(); |
| |
| // Disconnects `this` from all its successors and updates their phis, if the successors have them. |
| // If `visited` is provided, it will use the information to know if a successor is reachable and |
| // skip updating those phis. |
| void DisconnectFromSuccessors(const ArenaBitVector* visited = nullptr); |
| |
| // Removes the catch phi uses of the instructions in `this`, and then remove the instruction |
| // itself. If `building_dominator_tree` is true, it will not remove the instruction as user, since |
| // we do it in a previous step. This is a special case for building up the dominator tree: we want |
| // to eliminate uses before inputs but we don't have domination information, so we remove all |
| // connections from input/uses first before removing any instruction. |
| // This method assumes the instructions have been removed from all users with the exception of |
| // catch phis because of missing exceptional edges in the graph. |
| void RemoveCatchPhiUsesAndInstruction(bool building_dominator_tree); |
| |
| void AddInstruction(HInstruction* instruction); |
| // Insert `instruction` before/after an existing instruction `cursor`. |
| void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); |
| void InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor); |
| // Replace phi `initial` with `replacement` within this block. |
| void ReplaceAndRemovePhiWith(HPhi* initial, HPhi* replacement); |
| // Replace instruction `initial` with `replacement` within this block. |
| void ReplaceAndRemoveInstructionWith(HInstruction* initial, |
| HInstruction* replacement); |
| void AddPhi(HPhi* phi); |
| void InsertPhiAfter(HPhi* instruction, HPhi* cursor); |
| // RemoveInstruction and RemovePhi delete a given instruction from the respective |
| // instruction list. With 'ensure_safety' set to true, it verifies that the |
| // instruction is not in use and removes it from the use lists of its inputs. |
| void RemoveInstruction(HInstruction* instruction, bool ensure_safety = true); |
| void RemovePhi(HPhi* phi, bool ensure_safety = true); |
| void RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety = true); |
| |
| bool IsLoopHeader() const { |
| return IsInLoop() && (loop_information_->GetHeader() == this); |
| } |
| |
| bool IsLoopPreHeaderFirstPredecessor() const { |
| DCHECK(IsLoopHeader()); |
| return GetPredecessors()[0] == GetLoopInformation()->GetPreHeader(); |
| } |
| |
| bool IsFirstPredecessorBackEdge() const { |
| DCHECK(IsLoopHeader()); |
| return GetLoopInformation()->IsBackEdge(*GetPredecessors()[0]); |
| } |
| |
| HLoopInformation* GetLoopInformation() const { |
| return loop_information_; |
| } |
| |
| // Set the loop_information_ on this block. Overrides the current |
| // loop_information if it is an outer loop of the passed loop information. |
| // Note that this method is called while creating the loop information. |
| void SetInLoop(HLoopInformation* info) { |
| if (IsLoopHeader()) { |
| // Nothing to do. This just means `info` is an outer loop. |
| } else if (!IsInLoop()) { |
| loop_information_ = info; |
| } else if (loop_information_->Contains(*info->GetHeader())) { |
| // Block is currently part of an outer loop. Make it part of this inner loop. |
| // Note that a non loop header having a loop information means this loop information |
| // has already been populated |
| loop_information_ = info; |
| } else { |
| // Block is part of an inner loop. Do not update the loop information. |
| // Note that we cannot do the check `info->Contains(loop_information_)->GetHeader()` |
| // at this point, because this method is being called while populating `info`. |
| } |
| } |
| |
| // Raw update of the loop information. |
| void SetLoopInformation(HLoopInformation* info) { |
| loop_information_ = info; |
| } |
| |
| bool IsInLoop() const { return loop_information_ != nullptr; } |
| |
| TryCatchInformation* GetTryCatchInformation() const { return try_catch_information_; } |
| |
| void SetTryCatchInformation(TryCatchInformation* try_catch_information) { |
| try_catch_information_ = try_catch_information; |
| } |
| |
| bool IsTryBlock() const { |
| return try_catch_information_ != nullptr && try_catch_information_->IsTryBlock(); |
| } |
| |
| bool IsCatchBlock() const { |
| return try_catch_information_ != nullptr && try_catch_information_->IsCatchBlock(); |
| } |
| |
| // Returns the try entry that this block's successors should have. They will |
| // be in the same try, unless the block ends in a try boundary. In that case, |
| // the appropriate try entry will be returned. |
| const HTryBoundary* ComputeTryEntryOfSuccessors() const; |
| |
| bool HasThrowingInstructions() const; |
| |
| // Returns whether this block dominates the blocked passed as parameter. |
| bool Dominates(const HBasicBlock* block) const; |
| |
| size_t GetLifetimeStart() const { return lifetime_start_; } |
| size_t GetLifetimeEnd() const { return lifetime_end_; } |
| |
| void SetLifetimeStart(size_t start) { lifetime_start_ = start; } |
| void SetLifetimeEnd(size_t end) { lifetime_end_ = end; } |
| |
| bool EndsWithControlFlowInstruction() const; |
| bool EndsWithReturn() const; |
| bool EndsWithIf() const; |
| bool EndsWithTryBoundary() const; |
| bool HasSinglePhi() const; |
| |
| private: |
| HGraph* graph_; |
| ArenaVector<HBasicBlock*> predecessors_; |
| ArenaVector<HBasicBlock*> successors_; |
| HInstructionList instructions_; |
| HInstructionList phis_; |
| HLoopInformation* loop_information_; |
| HBasicBlock* dominator_; |
| ArenaVector<HBasicBlock*> dominated_blocks_; |
| uint32_t block_id_; |
| // The dex program counter of the first instruction of this block. |
| const uint32_t dex_pc_; |
| size_t lifetime_start_; |
| size_t lifetime_end_; |
| TryCatchInformation* try_catch_information_; |
| |
| friend class HGraph; |
| friend class HInstruction; |
| // Allow manual control of the ordering of predecessors/successors |
| friend class OptimizingUnitTestHelper; |
| |
| DISALLOW_COPY_AND_ASSIGN(HBasicBlock); |
| }; |
| |
| // Iterates over the LoopInformation of all loops which contain 'block' |
| // from the innermost to the outermost. |
| class HLoopInformationOutwardIterator : public ValueObject { |
| public: |
| explicit HLoopInformationOutwardIterator(const HBasicBlock& block) |
| : current_(block.GetLoopInformation()) {} |
| |
| bool Done() const { return current_ == nullptr; } |
| |
| void Advance() { |
| DCHECK(!Done()); |
| current_ = current_->GetPreHeader()->GetLoopInformation(); |
| } |
| |
| HLoopInformation* Current() const { |
| DCHECK(!Done()); |
| return current_; |
| } |
| |
| private: |
| HLoopInformation* current_; |
| |
| DISALLOW_COPY_AND_ASSIGN(HLoopInformationOutwardIterator); |
| }; |
| |
| #define FOR_EACH_CONCRETE_INSTRUCTION_SCALAR_COMMON(M) \ |
| M(Above, Condition) \ |
| M(AboveOrEqual, Condition) \ |
| M(Abs, UnaryOperation) \ |
| M(Add, BinaryOperation) \ |
| M(And, BinaryOperation) \ |
| M(ArrayGet, Instruction) \ |
| M(ArrayLength, Instruction) \ |
| M(ArraySet, Instruction) \ |
| M(Below, Condition) \ |
| M(BelowOrEqual, Condition) \ |
| M(BitwiseNegatedRight, BinaryOperation) \ |
| M(BooleanNot, UnaryOperation) \ |
| M(BoundsCheck, Instruction) \ |
| M(BoundType, Instruction) \ |
| M(CheckCast, Instruction) \ |
| M(ClassTableGet, Instruction) \ |
| M(ClearException, Instruction) \ |
| M(ClinitCheck, Instruction) \ |
| M(Compare, BinaryOperation) \ |
| M(ConstructorFence, Instruction) \ |
| M(CurrentMethod, Instruction) \ |
| M(ShouldDeoptimizeFlag, Instruction) \ |
| M(Deoptimize, Instruction) \ |
| M(Div, BinaryOperation) \ |
| M(DivZeroCheck, Instruction) \ |
| M(DoubleConstant, Constant) \ |
| M(Equal, Condition) \ |
| M(Exit, Instruction) \ |
| M(FloatConstant, Constant) \ |
| M(Goto, Instruction) \ |
| M(GreaterThan, Condition) \ |
| M(GreaterThanOrEqual, Condition) \ |
| M(If, Instruction) \ |
| M(InstanceFieldGet, Instruction) \ |
| M(InstanceFieldSet, Instruction) \ |
| M(InstanceOf, Instruction) \ |
| M(IntConstant, Constant) \ |
| M(IntermediateAddress, Instruction) \ |
| M(InvokeUnresolved, Invoke) \ |
| M(InvokeInterface, Invoke) \ |
| M(InvokeStaticOrDirect, Invoke) \ |
| M(InvokeVirtual, Invoke) \ |
| M(InvokePolymorphic, Invoke) \ |
| M(InvokeCustom, Invoke) \ |
| M(LessThan, Condition) \ |
| M(LessThanOrEqual, Condition) \ |
| M(LoadClass, Instruction) \ |
| M(LoadException, Instruction) \ |
| M(LoadMethodHandle, Instruction) \ |
| M(LoadMethodType, Instruction) \ |
| M(LoadString, Instruction) \ |
| M(LongConstant, Constant) \ |
| M(Max, Instruction) \ |
| M(MemoryBarrier, Instruction) \ |
| M(MethodEntryHook, Instruction) \ |
| M(MethodExitHook, Instruction) \ |
| M(Min, BinaryOperation) \ |
| M(MonitorOperation, Instruction) \ |
| M(Mul, BinaryOperation) \ |
| M(Neg, UnaryOperation) \ |
| M(NewArray, Instruction) \ |
| M(NewInstance, Instruction) \ |
| M(Nop, Instruction) \ |
| M(Not, UnaryOperation) \ |
| M(NotEqual, Condition) \ |
| M(NullConstant, Instruction) \ |
| M(NullCheck, Instruction) \ |
| M(Or, BinaryOperation) \ |
| M(PackedSwitch, Instruction) \ |
| M(ParallelMove, Instruction) \ |
| M(ParameterValue, Instruction) \ |
| M(Phi, Instruction) \ |
| M(Rem, BinaryOperation) \ |
| M(Return, Instruction) \ |
| M(ReturnVoid, Instruction) \ |
| M(Rol, BinaryOperation) \ |
| M(Ror, BinaryOperation) \ |
| M(Shl, BinaryOperation) \ |
| M(Shr, BinaryOperation) \ |
| M(StaticFieldGet, Instruction) \ |
| M(StaticFieldSet, Instruction) \ |
| M(StringBuilderAppend, Instruction) \ |
| M(UnresolvedInstanceFieldGet, Instruction) \ |
| M(UnresolvedInstanceFieldSet, Instruction) \ |
| M(UnresolvedStaticFieldGet, Instruction) \ |
| M(UnresolvedStaticFieldSet, Instruction) \ |
| M(Select, Instruction) \ |
| M(Sub, BinaryOperation) \ |
| M(SuspendCheck, Instruction) \ |
| M(Throw, Instruction) \ |
| M(TryBoundary, Instruction) \ |
| M(TypeConversion, Instruction) \ |
| M(UShr, BinaryOperation) \ |
| M(Xor, BinaryOperation) |
| |
| #define FOR_EACH_CONCRETE_INSTRUCTION_VECTOR_COMMON(M) \ |
| M(VecReplicateScalar, VecUnaryOperation) \ |
| M(VecExtractScalar, VecUnaryOperation) \ |
| M(VecReduce, VecUnaryOperation) \ |
| M(VecCnv, VecUnaryOperation) \ |
| M(VecNeg, VecUnaryOperation) \ |
| M(VecAbs, VecUnaryOperation) \ |
| M(VecNot, VecUnaryOperation) \ |
| M(VecAdd, VecBinaryOperation) \ |
| M(VecHalvingAdd, VecBinaryOperation) \ |
| M(VecSub, VecBinaryOperation) \ |
| M(VecMul, VecBinaryOperation) \ |
| M(VecDiv, VecBinaryOperation) \ |
| M(VecMin, VecBinaryOperation) \ |
| M(VecMax, VecBinaryOperation) \ |
| M(VecAnd, VecBinaryOperation) \ |
| M(VecAndNot, VecBinaryOperation) \ |
| M(VecOr, VecBinaryOperation) \ |
| M(VecXor, VecBinaryOperation) \ |
| M(VecSaturationAdd, VecBinaryOperation) \ |
| M(VecSaturationSub, VecBinaryOperation) \ |
| M(VecShl, VecBinaryOperation) \ |
| M(VecShr, VecBinaryOperation) \ |
| M(VecUShr, VecBinaryOperation) \ |
| M(VecSetScalars, VecOperation) \ |
| M(VecMultiplyAccumulate, VecOperation) \ |
| M(VecSADAccumulate, VecOperation) \ |
| M(VecDotProd, VecOperation) \ |
| M(VecLoad, VecMemoryOperation) \ |
| M(VecStore, VecMemoryOperation) \ |
| M(VecPredSetAll, VecPredSetOperation) \ |
| M(VecPredWhile, VecPredSetOperation) \ |
| M(VecPredToBoolean, VecOperation) \ |
| M(VecEqual, VecCondition) \ |
| M(VecNotEqual, VecCondition) \ |
| M(VecLessThan, VecCondition) \ |
| M(VecLessThanOrEqual, VecCondition) \ |
| M(VecGreaterThan, VecCondition) \ |
| M(VecGreaterThanOrEqual, VecCondition) \ |
| M(VecBelow, VecCondition) \ |
| M(VecBelowOrEqual, VecCondition) \ |
| M(VecAbove, VecCondition) \ |
| M(VecAboveOrEqual, VecCondition) \ |
| M(VecPredNot, VecPredSetOperation) |
| |
| #define FOR_EACH_CONCRETE_INSTRUCTION_COMMON(M) \ |
| FOR_EACH_CONCRETE_INSTRUCTION_SCALAR_COMMON(M) \ |
| FOR_EACH_CONCRETE_INSTRUCTION_VECTOR_COMMON(M) |
| |
| /* |
| * Instructions, shared across several (not all) architectures. |
| */ |
| #if !defined(ART_ENABLE_CODEGEN_arm) && !defined(ART_ENABLE_CODEGEN_arm64) |
| #define FOR_EACH_CONCRETE_INSTRUCTION_SHARED(M) |
| #else |
| #define FOR_EACH_CONCRETE_INSTRUCTION_SHARED(M) \ |
| M(DataProcWithShifterOp, Instruction) \ |
| M(MultiplyAccumulate, Instruction) \ |
| M(IntermediateAddressIndex, Instruction) |
| #endif |
| |
| #define FOR_EACH_CONCRETE_INSTRUCTION_ARM(M) |
| |
| #define FOR_EACH_CONCRETE_INSTRUCTION_ARM64(M) |
| |
| #if defined(ART_ENABLE_CODEGEN_riscv64) |
| #define FOR_EACH_CONCRETE_INSTRUCTION_RISCV64(M) M(Riscv64ShiftAdd, Instruction) |
| #else |
| #define FOR_EACH_CONCRETE_INSTRUCTION_RISCV64(M) |
| #endif |
| |
| #ifndef ART_ENABLE_CODEGEN_x86 |
| #define FOR_EACH_CONCRETE_INSTRUCTION_X86(M) |
| #else |
| #define FOR_EACH_CONCRETE_INSTRUCTION_X86(M) \ |
| M(X86ComputeBaseMethodAddress, Instruction) \ |
| M(X86LoadFromConstantTable, Instruction) \ |
| M(X86FPNeg, Instruction) \ |
| M(X86PackedSwitch, Instruction) |
| #endif |
| |
| #if defined(ART_ENABLE_CODEGEN_x86) || defined(ART_ENABLE_CODEGEN_x86_64) |
| #define FOR_EACH_CONCRETE_INSTRUCTION_X86_COMMON(M) \ |
| M(X86AndNot, Instruction) \ |
| M(X86MaskOrResetLeastSetBit, Instruction) |
| #else |
| #define FOR_EACH_CONCRETE_INSTRUCTION_X86_COMMON(M) |
| #endif |
| |
| #define FOR_EACH_CONCRETE_INSTRUCTION_X86_64(M) |
| |
| #define FOR_EACH_CONCRETE_INSTRUCTION(M) \ |
| FOR_EACH_CONCRETE_INSTRUCTION_COMMON(M) \ |
| FOR_EACH_CONCRETE_INSTRUCTION_SHARED(M) \ |
| FOR_EACH_CONCRETE_INSTRUCTION_ARM(M) \ |
| FOR_EACH_CONCRETE_INSTRUCTION_ARM64(M) \ |
| FOR_EACH_CONCRETE_INSTRUCTION_RISCV64(M) \ |
| FOR_EACH_CONCRETE_INSTRUCTION_X86(M) \ |
| FOR_EACH_CONCRETE_INSTRUCTION_X86_64(M) \ |
| FOR_EACH_CONCRETE_INSTRUCTION_X86_COMMON(M) |
| |
| #define FOR_EACH_ABSTRACT_INSTRUCTION(M) \ |
| M(Condition, BinaryOperation) \ |
| M(Constant, Instruction) \ |
| M(UnaryOperation, Instruction) \ |
| M(BinaryOperation, Instruction) \ |
| M(Invoke, Instruction) \ |
| M(VecOperation, Instruction) \ |
| M(VecUnaryOperation, VecOperation) \ |
| M(VecBinaryOperation, VecOperation) \ |
| M(VecMemoryOperation, VecOperation) \ |
| M(VecPredSetOperation, VecOperation) \ |
| M(VecCondition, VecPredSetOperation) |
| |
| #define FOR_EACH_INSTRUCTION(M) \ |
| FOR_EACH_CONCRETE_INSTRUCTION(M) \ |
| FOR_EACH_ABSTRACT_INSTRUCTION(M) |
| |
| #define FORWARD_DECLARATION(type, super) class H##type; |
| FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) |
| #undef FORWARD_DECLARATION |
| |
| #define DECLARE_INSTRUCTION(type) \ |
| private: \ |
| H##type& operator=(const H##type&) = delete; \ |
| public: \ |
| const char* DebugName() const override { return #type; } \ |
| HInstruction* Clone(ArenaAllocator* arena) const override { \ |
| DCHECK(IsClonable()); \ |
| return new (arena) H##type(*this); \ |
| } \ |
| void Accept(HGraphVisitor* visitor) override |
| |
| #define DECLARE_ABSTRACT_INSTRUCTION(type) \ |
| private: \ |
| H##type& operator=(const H##type&) = delete; \ |
| public: |
| |
| #define DEFAULT_COPY_CONSTRUCTOR(type) H##type(const H##type& other) = default; |
| |
| template <typename T> |
| class HUseListNode : public ArenaObject<kArenaAllocUseListNode>, |
| public IntrusiveForwardListNode<HUseListNode<T>> { |
| public: |
| // Get the instruction which has this use as one of the inputs. |
| T GetUser() const { return user_; } |
| // Get the position of the input record that this use corresponds to. |
| size_t GetIndex() const { return index_; } |
| // Set the position of the input record that this use corresponds to. |
| void SetIndex(size_t index) { index_ = index; } |
| |
| private: |
| HUseListNode(T user, size_t index) |
| : user_(user), index_(index) {} |
| |
| T const user_; |
| size_t index_; |
| |
| friend class HInstruction; |
| |
| DISALLOW_COPY_AND_ASSIGN(HUseListNode); |
| }; |
| |
| template <typename T> |
| using HUseList = IntrusiveForwardList<HUseListNode<T>>; |
| |
| // This class is used by HEnvironment and HInstruction classes to record the |
| // instructions they use and pointers to the corresponding HUseListNodes kept |
| // by the used instructions. |
| template <typename T> |
| class HUserRecord : public ValueObject { |
| public: |
| HUserRecord() : instruction_(nullptr), before_use_node_() {} |
| explicit HUserRecord(HInstruction* instruction) : instruction_(instruction), before_use_node_() {} |
| |
| HUserRecord(const HUserRecord<T>& old_record, typename HUseList<T>::iterator before_use_node) |
| : HUserRecord(old_record.instruction_, before_use_node) {} |
| HUserRecord(HInstruction* instruction, typename HUseList<T>::iterator before_use_node) |
| : instruction_(instruction), before_use_node_(before_use_node) { |
| DCHECK(instruction_ != nullptr); |
| } |
| |
| HInstruction* GetInstruction() const { return instruction_; } |
| typename HUseList<T>::iterator GetBeforeUseNode() const { return before_use_node_; } |
| typename HUseList<T>::iterator GetUseNode() const { return ++GetBeforeUseNode(); } |
| |
| private: |
| // Instruction used by the user. |
| HInstruction* instruction_; |
| |
| // Iterator before the corresponding entry in the use list kept by 'instruction_'. |
| typename HUseList<T>::iterator before_use_node_; |
| }; |
| |
| // Helper class that extracts the input instruction from HUserRecord<HInstruction*>. |
| // This is used for HInstruction::GetInputs() to return a container wrapper providing |
| // HInstruction* values even though the underlying container has HUserRecord<>s. |
| struct HInputExtractor { |
| HInstruction* operator()(HUserRecord<HInstruction*>& record) const { |
| return record.GetInstruction(); |
| } |
| const HInstruction* operator()(const HUserRecord<HInstruction*>& record) const { |
| return record.GetInstruction(); |
| } |
| }; |
| |
| using HInputsRef = TransformArrayRef<HUserRecord<HInstruction*>, HInputExtractor>; |
| using HConstInputsRef = TransformArrayRef<const HUserRecord<HInstruction*>, HInputExtractor>; |
| |
| /** |
| * Side-effects representation. |
| * |
| * For write/read dependences on fields/arrays, the dependence analysis uses |
| * type disambiguation (e.g. a float field write cannot modify the value of an |
| * integer field read) and the access type (e.g. a reference array write cannot |
| * modify the value of a reference field read [although it may modify the |
| * reference fetch prior to reading the field, which is represented by its own |
| * write/read dependence]). The analysis makes conservative points-to |
| * assumptions on reference types (e.g. two same typed arrays are assumed to be |
| * the same, and any reference read depends on any reference read without |
| * further regard of its type). |
| * |
| * kDependsOnGCBit is defined in the following way: instructions with kDependsOnGCBit must not be |
| * alive across the point where garbage collection might happen. |
| * |
| * Note: Instructions with kCanTriggerGCBit do not depend on each other. |
| * |
| * kCanTriggerGCBit must be used for instructions for which GC might happen on the path across |
| * those instructions from the compiler perspective (between this instruction and the next one |
| * in the IR). |
| * |
| * Note: Instructions which can cause GC only on a fatal slow path do not need |
| * kCanTriggerGCBit as the execution never returns to the instruction next to the exceptional |
| * one. However the execution may return to compiled code if there is a catch block in the |
| * current method; for this purpose the TryBoundary exit instruction has kCanTriggerGCBit |
| * set. |
| * |
| * The internal representation uses 38-bit and is described in the table below. |
| * The first line indicates the side effect, and for field/array accesses the |
| * second line indicates the type of the access (in the order of the |
| * DataType::Type enum). |
| * The two numbered lines below indicate the bit position in the bitfield (read |
| * vertically). |
| * |
| * |Depends on GC|ARRAY-R |FIELD-R |Can trigger GC|ARRAY-W |FIELD-W | |
| * +-------------+---------+---------+--------------+---------+---------+ |
| * | |DFJISCBZL|DFJISCBZL| |DFJISCBZL|DFJISCBZL| |
| * | 3 |333333322|222222221| 1 |111111110|000000000| |
| * | 7 |654321098|765432109| 8 |765432109|876543210| |
| * |
| * Note that, to ease the implementation, 'changes' bits are least significant |
| * bits, while 'dependency' bits are most significant bits. |
| */ |
| class SideEffects : public ValueObject { |
| public: |
| SideEffects() : flags_(0) {} |
| |
| static SideEffects None() { |
| return SideEffects(0); |
| } |
| |
| static SideEffects All() { |
| return SideEffects(kAllChangeBits | kAllDependOnBits); |
| } |
| |
| static SideEffects AllChanges() { |
| return SideEffects(kAllChangeBits); |
| } |
| |
| static SideEffects AllDependencies() { |
| return SideEffects(kAllDependOnBits); |
| } |
| |
| static SideEffects AllExceptGCDependency() { |
| return AllWritesAndReads().Union(SideEffects::CanTriggerGC()); |
| } |
| |
| static SideEffects AllWritesAndReads() { |
| return SideEffects(kAllWrites | kAllReads); |
| } |
| |
| static SideEffects AllWrites() { |
| return SideEffects(kAllWrites); |
| } |
| |
| static SideEffects AllReads() { |
| return SideEffects(kAllReads); |
| } |
| |
| static SideEffects FieldWriteOfType(DataType::Type type, bool is_volatile) { |
| return is_volatile |
| ? AllWritesAndReads() |
| : SideEffects(TypeFlag(type, kFieldWriteOffset)); |
| } |
| |
| static SideEffects ArrayWriteOfType(DataType::Type type) { |
| return SideEffects(TypeFlag(type, kArrayWriteOffset)); |
| } |
| |
| static SideEffects FieldReadOfType(DataType::Type type, bool is_volatile) { |
| return is_volatile |
| ? AllWritesAndReads() |
| : SideEffects(TypeFlag(type, kFieldReadOffset)); |
| } |
| |
| static SideEffects ArrayReadOfType(DataType::Type type) { |
| return SideEffects(TypeFlag(type, kArrayReadOffset)); |
| } |
| |
| // Returns whether GC might happen across this instruction from the compiler perspective so |
| // the next instruction in the IR would see that. |
| // |
| // See the SideEffect class comments. |
| static SideEffects CanTriggerGC() { |
| return SideEffects(1ULL << kCanTriggerGCBit); |
| } |
| |
| // Returns whether the instruction must not be alive across a GC point. |
| // |
| // See the SideEffect class comments. |
| static SideEffects DependsOnGC() { |
| return SideEffects(1ULL << kDependsOnGCBit); |
| } |
| |
| // Combines the side-effects of this and the other. |
| SideEffects Union(SideEffects other) const { |
| return SideEffects(flags_ | other.flags_); |
| } |
| |
| SideEffects Exclusion(SideEffects other) const { |
| return SideEffects(flags_ & ~other.flags_); |
| } |
| |
| void Add(SideEffects other) { |
| flags_ |= other.flags_; |
| } |
| |
| bool Includes(SideEffects other) const { |
| return (other.flags_ & flags_) == other.flags_; |
| } |
| |
| bool HasSideEffects() const { |
| return (flags_ & kAllChangeBits); |
| } |
| |
| bool HasDependencies() const { |
| return (flags_ & kAllDependOnBits); |
| } |
| |
| // Returns true if there are no side effects or dependencies. |
| bool DoesNothing() const { |
| return flags_ == 0; |
| } |
| |
| // Returns true if something is written. |
| bool DoesAnyWrite() const { |
| return (flags_ & kAllWrites); |
| } |
| |
| // Returns true if something is read. |
| bool DoesAnyRead() const { |
| return (flags_ & kAllReads); |
| } |
| |
| // Returns true if potentially everything is written and read |
| // (every type and every kind of access). |
| bool DoesAllReadWrite() const { |
| return (flags_ & (kAllWrites | kAllReads)) == (kAllWrites | kAllReads); |
| } |
| |
| bool DoesAll() const { |
| return flags_ == (kAllChangeBits | kAllDependOnBits); |
| } |
| |
| // Returns true if `this` may read something written by `other`. |
| bool MayDependOn(SideEffects other) const { |
| const uint64_t depends_on_flags = (flags_ & kAllDependOnBits) >> kChangeBits; |
| return (other.flags_ & depends_on_flags); |
| } |
| |
| // Returns string representation of flags (for debugging only). |
| // Format: |x|DFJISCBZL|DFJISCBZL|y|DFJISCBZL|DFJISCBZL| |
| std::string ToString() const { |
| std::string flags = "|"; |
| for (int s = kLastBit; s >= 0; s--) { |
| bool current_bit_is_set = ((flags_ >> s) & 1) != 0; |
| if ((s == kDependsOnGCBit) || (s == kCanTriggerGCBit)) { |
| // This is a bit for the GC side effect. |
| if (current_bit_is_set) { |
| flags += "GC"; |
| } |
| flags += "|"; |
| } else { |
| // This is a bit for the array/field analysis. |
| // The underscore character stands for the 'can trigger GC' bit. |
| static const char *kDebug = "LZBCSIJFDLZBCSIJFD_LZBCSIJFDLZBCSIJFD"; |
| if (current_bit_is_set) { |
| flags += kDebug[s]; |
| } |
| if ((s == kFieldWriteOffset) || (s == kArrayWriteOffset) || |
| (s == kFieldReadOffset) || (s == kArrayReadOffset)) { |
| flags += "|"; |
| } |
| } |
| } |
| return flags; |
| } |
| |
| bool Equals(const SideEffects& other) const { return flags_ == other.flags_; } |
| |
| private: |
| static constexpr int kFieldArrayAnalysisBits = 9; |
| |
| static constexpr int kFieldWriteOffset = 0; |
| static constexpr int kArrayWriteOffset = kFieldWriteOffset + kFieldArrayAnalysisBits; |
| static constexpr int kLastBitForWrites = kArrayWriteOffset + kFieldArrayAnalysisBits - 1; |
| static constexpr int kCanTriggerGCBit = kLastBitForWrites + 1; |
| |
| static constexpr int kChangeBits = kCanTriggerGCBit + 1; |
| |
| static constexpr int kFieldReadOffset = kCanTriggerGCBit + 1; |
| static constexpr int kArrayReadOffset = kFieldReadOffset + kFieldArrayAnalysisBits; |
| static constexpr int kLastBitForReads = kArrayReadOffset + kFieldArrayAnalysisBits - 1; |
| static constexpr int kDependsOnGCBit = kLastBitForReads + 1; |
| |
| static constexpr int kLastBit = kDependsOnGCBit; |
| static constexpr int kDependOnBits = kLastBit + 1 - kChangeBits; |
| |
| // Aliases. |
| |
| static_assert(kChangeBits == kDependOnBits, |
| "the 'change' bits should match the 'depend on' bits."); |
| |
| static constexpr uint64_t kAllChangeBits = ((1ULL << kChangeBits) - 1); |
| static constexpr uint64_t kAllDependOnBits = ((1ULL << kDependOnBits) - 1) << kChangeBits; |
| static constexpr uint64_t kAllWrites = |
| ((1ULL << (kLastBitForWrites + 1 - kFieldWriteOffset)) - 1) << kFieldWriteOffset; |
| static constexpr uint64_t kAllReads = |
| ((1ULL << (kLastBitForReads + 1 - kFieldReadOffset)) - 1) << kFieldReadOffset; |
| |
| // Translates type to bit flag. The type must correspond to a Java type. |
| static uint64_t TypeFlag(DataType::Type type, int offset) { |
| int shift; |
| switch (type) { |
| case DataType::Type::kReference: shift = 0; break; |
| case DataType::Type::kBool: shift = 1; break; |
| case DataType::Type::kInt8: shift = 2; break; |
| case DataType::Type::kUint16: shift = 3; break; |
| case DataType::Type::kInt16: shift = 4; break; |
| case DataType::Type::kInt32: shift = 5; break; |
| case DataType::Type::kInt64: shift = 6; break; |
| case DataType::Type::kFloat32: shift = 7; break; |
| case DataType::Type::kFloat64: shift = 8; break; |
| default: |
| LOG(FATAL) << "Unexpected data type " << type; |
| UNREACHABLE(); |
| } |
| DCHECK_LE(kFieldWriteOffset, shift); |
| DCHECK_LT(shift, kArrayWriteOffset); |
| return UINT64_C(1) << (shift + offset); |
| } |
| |
| // Private constructor on direct flags value. |
| explicit SideEffects(uint64_t flags) : flags_(flags) {} |
| |
| uint64_t flags_; |
| }; |
| |
| // A HEnvironment object contains the values of virtual registers at a given location. |
| class HEnvironment : public ArenaObject<kArenaAllocEnvironment> { |
| public: |
| static HEnvironment* Create(ArenaAllocator* allocator, |
| size_t number_of_vregs, |
| ArtMethod* method, |
| uint32_t dex_pc, |
| HInstruction* holder) { |
| // The storage for vreg records is allocated right after the `HEnvironment` itself. |
| static_assert(IsAligned<alignof(HUserRecord<HEnvironment*>)>(sizeof(HEnvironment))); |
| static_assert(IsAligned<alignof(HUserRecord<HEnvironment*>)>(ArenaAllocator::kAlignment)); |
| size_t alloc_size = sizeof(HEnvironment) + number_of_vregs * sizeof(HUserRecord<HEnvironment*>); |
| void* storage = allocator->Alloc(alloc_size, kArenaAllocEnvironment); |
| return new (storage) HEnvironment(number_of_vregs, method, dex_pc, holder); |
| } |
| |
| static HEnvironment* Create(ArenaAllocator* allocator, |
| const HEnvironment& to_copy, |
| HInstruction* holder) { |
| return Create(allocator, to_copy.Size(), to_copy.GetMethod(), to_copy.GetDexPc(), holder); |
| } |
| |
| void AllocateLocations(ArenaAllocator* allocator) { |
| DCHECK(locations_ == nullptr); |
| if (Size() != 0u) { |
| locations_ = allocator->AllocArray<Location>(Size(), kArenaAllocEnvironmentLocations); |
| } |
| } |
| |
| void SetAndCopyParentChain(ArenaAllocator* allocator, HEnvironment* parent) { |
| if (parent_ != nullptr) { |
| parent_->SetAndCopyParentChain(allocator, parent); |
| } else { |
| parent_ = Create(allocator, *parent, holder_); |
| parent_->CopyFrom(parent); |
| if (parent->GetParent() != nullptr) { |
| parent_->SetAndCopyParentChain(allocator, parent->GetParent()); |
| } |
| } |
| } |
| |
| void CopyFrom(ArrayRef<HInstruction* const> locals); |
| void CopyFrom(const HEnvironment* environment); |
| |
| // Copy from `env`. If it's a loop phi for `loop_header`, copy the first |
| // input to the loop phi instead. This is for inserting instructions that |
| // require an environment (like HDeoptimization) in the loop pre-header. |
| void CopyFromWithLoopPhiAdjustment(HEnvironment* env, HBasicBlock* loop_header); |
| |
| void SetRawEnvAt(size_t index, HInstruction* instruction) { |
| GetVRegs()[index] = HUserRecord<HEnvironment*>(instruction); |
| } |
| |
| HInstruction* GetInstructionAt(size_t index) const { |
| return GetVRegs()[index].GetInstruction(); |
| } |
| |
| void RemoveAsUserOfInput(size_t index) const; |
| |
| // Replaces the input at the position 'index' with the replacement; the replacement and old |
| // input instructions' env_uses_ lists are adjusted. The function works similar to |
| // HInstruction::ReplaceInput. |
| void ReplaceInput(HInstruction* replacement, size_t index); |
| |
| size_t Size() const { return number_of_vregs_; } |
| |
| HEnvironment* GetParent() const { return parent_; } |
| |
| void SetLocationAt(size_t index, Location location) { |
| DCHECK_LT(index, number_of_vregs_); |
| DCHECK(locations_ != nullptr); |
| locations_[index] = location; |
| } |
| |
| Location GetLocationAt(size_t index) const { |
| DCHECK_LT(index, number_of_vregs_); |
| DCHECK(locations_ != nullptr); |
| return locations_[index]; |
| } |
| |
| uint32_t GetDexPc() const { |
| return dex_pc_; |
| } |
| |
| ArtMethod* GetMethod() const { |
| return method_; |
| } |
| |
| HInstruction* GetHolder() const { |
| return holder_; |
| } |
| |
| |
| bool IsFromInlinedInvoke() const { |
| return GetParent() != nullptr; |
| } |
| |
| class EnvInputSelector { |
| public: |
| explicit EnvInputSelector(const HEnvironment* e) : env_(e) {} |
| HInstruction* operator()(size_t s) const { |
| return env_->GetInstructionAt(s); |
| } |
| private: |
| const HEnvironment* env_; |
| }; |
| |
| using HConstEnvInputRef = TransformIterator<CountIter, EnvInputSelector>; |
| IterationRange<HConstEnvInputRef> GetEnvInputs() const { |
| IterationRange<CountIter> range(Range(Size())); |
| return MakeIterationRange(MakeTransformIterator(range.begin(), EnvInputSelector(this)), |
| MakeTransformIterator(range.end(), EnvInputSelector(this))); |
| } |
| |
| private: |
| ALWAYS_INLINE HEnvironment(size_t number_of_vregs, |
| ArtMethod* method, |
| uint32_t dex_pc, |
| HInstruction* holder) |
| : number_of_vregs_(dchecked_integral_cast<uint32_t>(number_of_vregs)), |
| dex_pc_(dex_pc), |
| holder_(holder), |
| parent_(nullptr), |
| method_(method), |
| locations_(nullptr) { |
| } |
| |
| ArrayRef<HUserRecord<HEnvironment*>> GetVRegs() { |
| auto* vregs = reinterpret_cast<HUserRecord<HEnvironment*>*>(this + 1); |
| return ArrayRef<HUserRecord<HEnvironment*>>(vregs, number_of_vregs_); |
| } |
| |
| ArrayRef<const HUserRecord<HEnvironment*>> GetVRegs() const { |
| auto* vregs = reinterpret_cast<const HUserRecord<HEnvironment*>*>(this + 1); |
| return ArrayRef<const HUserRecord<HEnvironment*>>(vregs, number_of_vregs_); |
| } |
| |
| const uint32_t number_of_vregs_; |
| const uint32_t dex_pc_; |
| |
| // The instruction that holds this environment. |
| HInstruction* const holder_; |
| |
| // The parent environment for inlined code. |
| HEnvironment* parent_; |
| |
| // The environment's method, if resolved. |
| ArtMethod* method_; |
| |
| // Locations assigned by the register allocator. |
| Location* locations_; |
| |
| friend class HInstruction; |
| |
| DISALLOW_COPY_AND_ASSIGN(HEnvironment); |
| }; |
| |
| std::ostream& operator<<(std::ostream& os, const HInstruction& rhs); |
| |
| // Iterates over the Environments |
| class HEnvironmentIterator : public ValueObject { |
| public: |
| using iterator_category = std::forward_iterator_tag; |
| using value_type = HEnvironment*; |
| using difference_type = ptrdiff_t; |
| using pointer = void; |
| using reference = void; |
| |
| explicit HEnvironmentIterator(HEnvironment* cur) : cur_(cur) {} |
| |
| HEnvironment* operator*() const { |
| return cur_; |
| } |
| |
| HEnvironmentIterator& operator++() { |
| DCHECK(cur_ != nullptr); |
| cur_ = cur_->GetParent(); |
| return *this; |
| } |
| |
| HEnvironmentIterator operator++(int) { |
| HEnvironmentIterator prev(*this); |
| ++(*this); |
| return prev; |
| } |
| |
| bool operator==(const HEnvironmentIterator& other) const { |
| return other.cur_ == cur_; |
| } |
| |
| bool operator!=(const HEnvironmentIterator& other) const { |
| return !(*this == other); |
| } |
| |
| private: |
| HEnvironment* cur_; |
| }; |
| |
| class HInstruction : public ArenaObject<kArenaAllocInstruction> { |
| public: |
| #define DECLARE_KIND(type, super) k##type, |
| enum InstructionKind { // private marker to avoid generate-operator-out.py from processing. |
| FOR_EACH_CONCRETE_INSTRUCTION(DECLARE_KIND) |
| kLastInstructionKind |
| }; |
| #undef DECLARE_KIND |
| |
| HInstruction(InstructionKind kind, SideEffects side_effects, uint32_t dex_pc) |
| : HInstruction(kind, DataType::Type::kVoid, side_effects, dex_pc) {} |
| |
| HInstruction(InstructionKind kind, DataType::Type type, SideEffects side_effects, uint32_t dex_pc) |
| : previous_(nullptr), |
| next_(nullptr), |
| block_(nullptr), |
| dex_pc_(dex_pc), |
| id_(-1), |
| ssa_index_(-1), |
| packed_fields_(0u), |
| environment_(nullptr), |
| locations_(nullptr), |
| live_interval_(nullptr), |
| lifetime_position_(kNoLifetime), |
| side_effects_(side_effects), |
| reference_type_handle_(ReferenceTypeInfo::CreateInvalid().GetTypeHandle()) { |
| SetPackedField<InstructionKindField>(kind); |
| SetPackedField<TypeField>(type); |
| SetPackedFlag<kFlagReferenceTypeIsExact>(ReferenceTypeInfo::CreateInvalid().IsExact()); |
| } |
| |
| virtual ~HInstruction() {} |
| |
| std::ostream& Dump(std::ostream& os, bool dump_args = false); |
| |
| // Helper for dumping without argument information using operator<< |
| struct NoArgsDump { |
| const HInstruction* ins; |
| }; |
| NoArgsDump DumpWithoutArgs() const { |
| return NoArgsDump{this}; |
| } |
| // Helper for dumping with argument information using operator<< |
| struct ArgsDump { |
| const HInstruction* ins; |
| }; |
| ArgsDump DumpWithArgs() const { |
| return ArgsDump{this}; |
| } |
| |
| HInstruction* GetNext() const { return next_; } |
| HInstruction* GetPrevious() const { return previous_; } |
| |
| HInstruction* GetNextDisregardingMoves() const; |
| HInstruction* GetPreviousDisregardingMoves() const; |
| |
| HBasicBlock* GetBlock() const { return block_; } |
| ArenaAllocator* GetAllocator() const { return block_->GetGraph()->GetAllocator(); } |
| void SetBlock(HBasicBlock* block) { block_ = block; } |
| bool IsInBlock() const { return block_ != nullptr; } |
| bool IsInLoop() const { return block_->IsInLoop(); } |
| bool IsLoopHeaderPhi() const { return IsPhi() && block_->IsLoopHeader(); } |
| bool IsIrreducibleLoopHeaderPhi() const { |
| return IsLoopHeaderPhi() && GetBlock()->GetLoopInformation()->IsIrreducible(); |
| } |
| |
| virtual ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() = 0; |
| |
| ArrayRef<const HUserRecord<HInstruction*>> GetInputRecords() const { |
| // One virtual method is enough, just const_cast<> and then re-add the const. |
| return ArrayRef<const HUserRecord<HInstruction*>>( |
| const_cast<HInstruction*>(this)->GetInputRecords()); |
| } |
| |
| HInputsRef GetInputs() { |
| return MakeTransformArrayRef(GetInputRecords(), HInputExtractor()); |
| } |
| |
| HConstInputsRef GetInputs() const { |
| return MakeTransformArrayRef(GetInputRecords(), HInputExtractor()); |
| } |
| |
| size_t InputCount() const { return GetInputRecords().size(); } |
| HInstruction* InputAt(size_t i) const { return InputRecordAt(i).GetInstruction(); } |
| |
| bool HasInput(HInstruction* input) const { |
| for (const HInstruction* i : GetInputs()) { |
| if (i == input) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| void SetRawInputAt(size_t index, HInstruction* input) { |
| SetRawInputRecordAt(index, HUserRecord<HInstruction*>(input)); |
| } |
| |
| virtual void Accept(HGraphVisitor* visitor) = 0; |
| virtual const char* DebugName() const = 0; |
| |
| DataType::Type GetType() const { |
| return TypeField::Decode(GetPackedFields()); |
| } |
| |
| virtual bool NeedsEnvironment() const { return false; } |
| virtual bool NeedsBss() const { |
| return false; |
| } |
| |
| uint32_t GetDexPc() const { return dex_pc_; } |
| |
| virtual bool IsControlFlow() const { return false; } |
| |
| // Can the instruction throw? |
| // TODO: We should rename to CanVisiblyThrow, as some instructions (like HNewInstance), |
| // could throw OOME, but it is still OK to remove them if they are unused. |
| virtual bool CanThrow() const { return false; } |
| |
| // Does the instruction always throw an exception unconditionally? |
| virtual bool AlwaysThrows() const { return false; } |
| // Will this instruction only cause async exceptions if it causes any at all? |
| virtual bool OnlyThrowsAsyncExceptions() const { |
| return false; |
| } |
| |
| bool CanThrowIntoCatchBlock() const { return CanThrow() && block_->IsTryBlock(); } |
| |
| bool HasSideEffects() const { return side_effects_.HasSideEffects(); } |
| bool DoesAnyWrite() const { return side_effects_.DoesAnyWrite(); } |
| |
| // Does not apply for all instructions, but having this at top level greatly |
| // simplifies the null check elimination. |
| // TODO: Consider merging can_be_null into ReferenceTypeInfo. |
| virtual bool CanBeNull() const { |
| DCHECK_EQ(GetType(), DataType::Type::kReference) << "CanBeNull only applies to reference types"; |
| return true; |
| } |
| |
| virtual bool CanDoImplicitNullCheckOn([[maybe_unused]] HInstruction* obj) const { return false; } |
| |
| // If this instruction will do an implicit null check, return the `HNullCheck` associated |
| // with it. Otherwise return null. |
| HNullCheck* GetImplicitNullCheck() const { |
| // Go over previous non-move instructions that are emitted at use site. |
| HInstruction* prev_not_move = GetPreviousDisregardingMoves(); |
| while (prev_not_move != nullptr && prev_not_move->IsEmittedAtUseSite()) { |
| if (prev_not_move->IsNullCheck()) { |
| return prev_not_move->AsNullCheck(); |
| } |
| prev_not_move = prev_not_move->GetPreviousDisregardingMoves(); |
| } |
| return nullptr; |
| } |
| |
| virtual bool IsActualObject() const { |
| return GetType() == DataType::Type::kReference; |
| } |
| |
| // Sets the ReferenceTypeInfo. The RTI must be valid. |
| void SetReferenceTypeInfo(ReferenceTypeInfo rti); |
| // Same as above, but we only set it if it's valid. Otherwise, we don't change the current RTI. |
| void SetReferenceTypeInfoIfValid(ReferenceTypeInfo rti); |
| |
| ReferenceTypeInfo GetReferenceTypeInfo() const { |
| DCHECK_EQ(GetType(), DataType::Type::kReference); |
| return ReferenceTypeInfo::CreateUnchecked(reference_type_handle_, |
| GetPackedFlag<kFlagReferenceTypeIsExact>()); |
| } |
| |
| void AddUseAt(HInstruction* user, size_t index) { |
| DCHECK(user != nullptr); |
| // Note: fixup_end remains valid across push_front(). |
| auto fixup_end = uses_.empty() ? uses_.begin() : ++uses_.begin(); |
| ArenaAllocator* allocator = user->GetBlock()->GetGraph()->GetAllocator(); |
| HUseListNode<HInstruction*>* new_node = |
| new (allocator) HUseListNode<HInstruction*>(user, index); |
| uses_.push_front(*new_node); |
| FixUpUserRecordsAfterUseInsertion(fixup_end); |
| } |
| |
| void AddEnvUseAt(HEnvironment* user, size_t index) { |
| DCHECK(user != nullptr); |
| // Note: env_fixup_end remains valid across push_front(). |
| auto env_fixup_end = env_uses_.empty() ? env_uses_.begin() : ++env_uses_.begin(); |
| HUseListNode<HEnvironment*>* new_node = |
| new (GetBlock()->GetGraph()->GetAllocator()) HUseListNode<HEnvironment*>(user, index); |
| env_uses_.push_front(*new_node); |
| FixUpUserRecordsAfterEnvUseInsertion(env_fixup_end); |
| } |
| |
| void RemoveAsUserOfInput(size_t input) { |
| HUserRecord<HInstruction*> input_use = InputRecordAt(input); |
| HUseList<HInstruction*>::iterator before_use_node = input_use.GetBeforeUseNode(); |
| input_use.GetInstruction()->uses_.erase_after(before_use_node); |
| input_use.GetInstruction()->FixUpUserRecordsAfterUseRemoval(before_use_node); |
| } |
| |
| void RemoveAsUserOfAllInputs() { |
| for (const HUserRecord<HInstruction*>& input_use : GetInputRecords()) { |
| HUseList<HInstruction*>::iterator before_use_node = input_use.GetBeforeUseNode(); |
| input_use.GetInstruction()->uses_.erase_after(before_use_node); |
| input_use.GetInstruction()->FixUpUserRecordsAfterUseRemoval(before_use_node); |
| } |
| } |
| |
| const HUseList<HInstruction*>& GetUses() const { return uses_; } |
| const HUseList<HEnvironment*>& GetEnvUses() const { return env_uses_; } |
| |
| bool HasUses() const { return !uses_.empty() || !env_uses_.empty(); } |
| bool HasEnvironmentUses() const { return !env_uses_.empty(); } |
| bool HasNonEnvironmentUses() const { return !uses_.empty(); } |
| bool HasOnlyOneNonEnvironmentUse() const { |
| return !HasEnvironmentUses() && GetUses().HasExactlyOneElement(); |
| } |
| |
| bool IsRemovable() const { |
| return |
| !DoesAnyWrite() && |
| // TODO(solanes): Merge calls from IsSuspendCheck to IsControlFlow into one that doesn't |
| // do virtual dispatching. |
| !IsSuspendCheck() && |
| !IsNop() && |
| !IsParameterValue() && |
| // If we added an explicit barrier then we should keep it. |
| !IsMemoryBarrier() && |
| !IsConstructorFence() && |
| !IsControlFlow() && |
| !CanThrow(); |
| } |
| |
| bool IsDeadAndRemovable() const { |
| return !HasUses() && IsRemovable(); |
| } |
| |
| bool IsPhiDeadAndRemovable() const { |
| DCHECK(IsPhi()); |
| DCHECK(IsRemovable()) << " phis are always removable"; |
| return !HasUses(); |
| } |
| |
| // Does this instruction dominate `other_instruction`? |
| // Aborts if this instruction and `other_instruction` are different phis. |
| bool Dominates(HInstruction* other_instruction) const; |
| |
| // Same but with `strictly dominates` i.e. returns false if this instruction and |
| // `other_instruction` are the same. |
| bool StrictlyDominates(HInstruction* other_instruction) const; |
| |
| int GetId() const { return id_; } |
| void SetId(int id) { id_ = id; } |
| |
| int GetSsaIndex() const { return ssa_index_; } |
| void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; } |
| bool HasSsaIndex() const { return ssa_index_ != -1; } |
| |
| bool HasEnvironment() const { return environment_ != nullptr; } |
| HEnvironment* GetEnvironment() const { return environment_; } |
| IterationRange<HEnvironmentIterator> GetAllEnvironments() const { |
| return MakeIterationRange(HEnvironmentIterator(GetEnvironment()), |
| HEnvironmentIterator(nullptr)); |
| } |
| // Set the `environment_` field. Raw because this method does not |
| // update the uses lists. |
| void SetRawEnvironment(HEnvironment* environment) { |
| DCHECK(environment_ == nullptr); |
| DCHECK_EQ(environment->GetHolder(), this); |
| environment_ = environment; |
| } |
| |
| void InsertRawEnvironment(HEnvironment* environment) { |
| DCHECK(environment_ != nullptr); |
| DCHECK_EQ(environment->GetHolder(), this); |
| DCHECK(environment->GetParent() == nullptr); |
| environment->parent_ = environment_; |
| environment_ = environment; |
| } |
| |
| void RemoveEnvironment(); |
| |
| // Set the environment of this instruction, copying it from `environment`. While |
| // copying, the uses lists are being updated. |
| void CopyEnvironmentFrom(HEnvironment* environment) { |
| DCHECK(environment_ == nullptr); |
| ArenaAllocator* allocator = GetBlock()->GetGraph()->GetAllocator(); |
| environment_ = HEnvironment::Create(allocator, *environment, this); |
| environment_->CopyFrom(environment); |
| if (environment->GetParent() != nullptr) { |
| environment_->SetAndCopyParentChain(allocator, environment->GetParent()); |
| } |
| } |
| |
| void CopyEnvironmentFromWithLoopPhiAdjustment(HEnvironment* environment, |
| HBasicBlock* block) { |
| DCHECK(environment_ == nullptr); |
| ArenaAllocator* allocator = GetBlock()->GetGraph()->GetAllocator(); |
| environment_ = HEnvironment::Create(allocator, *environment, this); |
| environment_->CopyFromWithLoopPhiAdjustment(environment, block); |
| if (environment->GetParent() != nullptr) { |
| environment_->SetAndCopyParentChain(allocator, environment->GetParent()); |
| } |
| } |
| |
| // Returns the number of entries in the environment. Typically, that is the |
| // number of dex registers in a method. It could be more in case of inlining. |
| size_t EnvironmentSize() const; |
| |
| LocationSummary* GetLocations() const { return locations_; } |
| void SetLocations(LocationSummary* locations) { locations_ = locations; } |
| |
| void ReplaceWith(HInstruction* instruction); |
| void ReplaceUsesDominatedBy(HInstruction* dominator, |
| HInstruction* replacement, |
| bool strictly_dominated = true); |
| void ReplaceEnvUsesDominatedBy(HInstruction* dominator, HInstruction* replacement); |
| void ReplaceInput(HInstruction* replacement, size_t index); |
| |
| // This is almost the same as doing `ReplaceWith()`. But in this helper, the |
| // uses of this instruction by `other` are *not* updated. |
| void ReplaceWithExceptInReplacementAtIndex(HInstruction* other, size_t use_index) { |
| ReplaceWith(other); |
| other->ReplaceInput(this, use_index); |
| } |
| |
| // Move `this` instruction before `cursor` |
| void MoveBefore(HInstruction* cursor, bool do_checks = true); |
| |
| // Move `this` before its first user and out of any loops. If there is no |
| // out-of-loop user that dominates all other users, move the instruction |
| // to the end of the out-of-loop common dominator of the user's blocks. |
| // |
| // This can be used only on non-throwing instructions with no side effects that |
| // have at least one use but no environment uses. |
| void MoveBeforeFirstUserAndOutOfLoops(); |
| |
| #define INSTRUCTION_TYPE_CHECK(type, super) \ |
| bool Is##type() const; |
| |
| FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK) |
| #undef INSTRUCTION_TYPE_CHECK |
| |
| #define INSTRUCTION_TYPE_CAST(type, super) \ |
| const H##type* As##type() const; \ |
| H##type* As##type(); \ |
| const H##type* As##type##OrNull() const; \ |
| H##type* As##type##OrNull(); |
| |
| FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CAST) |
| #undef INSTRUCTION_TYPE_CAST |
| |
| // Return a clone of the instruction if it is clonable (shallow copy by default, custom copy |
| // if a custom copy-constructor is provided for a particular type). If IsClonable() is false for |
| // the instruction then the behaviour of this function is undefined. |
| // |
| // Note: It is semantically valid to create a clone of the instruction only until |
| // prepare_for_register_allocator phase as lifetime, intervals and codegen info are not |
| // copied. |
| // |
| // Note: HEnvironment and some other fields are not copied and are set to default values, see |
| // 'explicit HInstruction(const HInstruction& other)' for details. |
| virtual HInstruction* Clone([[maybe_unused]] ArenaAllocator* arena) const { |
| LOG(FATAL) << "Cloning is not implemented for the instruction " << |
| DebugName() << " " << GetId(); |
| UNREACHABLE(); |
| } |
| |
| virtual bool IsFieldAccess() const { |
| return false; |
| } |
| |
| virtual const FieldInfo& GetFieldInfo() const { |
| CHECK(IsFieldAccess()) << "Only callable on field accessors not " << DebugName() << " " |
| << *this; |
| LOG(FATAL) << "Must be overridden by field accessors. Not implemented by " << *this; |
| UNREACHABLE(); |
| } |
| |
| // Return whether instruction can be cloned (copied). |
| virtual bool IsClonable() const { return false; } |
| |
| // Returns whether the instruction can be moved within the graph. |
| // TODO: this method is used by LICM and GVN with possibly different |
| // meanings? split and rename? |
| virtual bool CanBeMoved() const { return false; } |
| |
| // Returns whether any data encoded in the two instructions is equal. |
| // This method does not look at the inputs. Both instructions must be |
| // of the same type, otherwise the method has undefined behavior. |
| virtual bool InstructionDataEquals([[maybe_unused]] const HInstruction* other) const { |
| return false; |
| } |
| |
| // Returns whether two instructions are equal, that is: |
| // 1) They have the same type and contain the same data (InstructionDataEquals). |
| // 2) Their inputs are identical. |
| bool Equals(const HInstruction* other) const; |
| |
| InstructionKind GetKind() const { return GetPackedField<InstructionKindField>(); } |
| |
| virtual size_t ComputeHashCode() const { |
| size_t result = GetKind(); |
| for (const HInstruction* input : GetInputs()) { |
| result = (result * 31) + input->GetId(); |
| } |
| return result; |
| } |
| |
| SideEffects GetSideEffects() const { return side_effects_; } |
| void SetSideEffects(SideEffects other) { side_effects_ = other; } |
| void AddSideEffects(SideEffects other) { side_effects_.Add(other); } |
| |
| size_t GetLifetimePosition() const { return lifetime_position_; } |
| void SetLifetimePosition(size_t position) { lifetime_position_ = position; } |
| LiveInterval* GetLiveInterval() const { return live_interval_; } |
| void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; } |
| bool HasLiveInterval() const { return live_interval_ != nullptr; } |
| |
| bool IsSuspendCheckEntry() const { return IsSuspendCheck() && GetBlock()->IsEntryBlock(); } |
| |
| // Returns whether the code generation of the instruction will require to have access |
| // to the current method. Such instructions are: |
| // (1): Instructions that require an environment, as calling the runtime requires |
| // to walk the stack and have the current method stored at a specific stack address. |
| // (2): HCurrentMethod, potentially used by HInvokeStaticOrDirect, HLoadString, or HLoadClass |
| // to access the dex cache. |
| bool NeedsCurrentMethod() const { |
| return NeedsEnvironment() || IsCurrentMethod(); |
| } |
| |
| // Does this instruction have any use in an environment before |
| // control flow hits 'other'? |
| bool HasAnyEnvironmentUseBefore(HInstruction* other); |
| |
| // Remove all references to environment uses of this instruction. |
| // The caller must ensure that this is safe to do. |
| void RemoveEnvironmentUsers(); |
| |
| bool IsEmittedAtUseSite() const { return GetPackedFlag<kFlagEmittedAtUseSite>(); } |
| void MarkEmittedAtUseSite() { SetPackedFlag<kFlagEmittedAtUseSite>(true); } |
| |
| protected: |
| // If set, the machine code for this instruction is assumed to be generated by |
| // its users. Used by liveness analysis to compute use positions accordingly. |
| static constexpr size_t kFlagEmittedAtUseSite = 0u; |
| static constexpr size_t kFlagReferenceTypeIsExact = kFlagEmittedAtUseSite + 1; |
| static constexpr size_t kFieldInstructionKind = kFlagReferenceTypeIsExact + 1; |
| static constexpr size_t kFieldInstructionKindSize = |
| MinimumBitsToStore(static_cast<size_t>(InstructionKind::kLastInstructionKind - 1)); |
| static constexpr size_t kFieldType = |
| kFieldInstructionKind + kFieldInstructionKindSize; |
| static constexpr size_t kFieldTypeSize = |
| MinimumBitsToStore(static_cast<size_t>(DataType::Type::kLast)); |
| static constexpr size_t kNumberOfGenericPackedBits = kFieldType + kFieldTypeSize; |
| static constexpr size_t kMaxNumberOfPackedBits = sizeof(uint32_t) * kBitsPerByte; |
| |
| static_assert(kNumberOfGenericPackedBits <= kMaxNumberOfPackedBits, |
| "Too many generic packed fields"); |
| |
| using TypeField = BitField<DataType::Type, kFieldType, kFieldTypeSize>; |
| |
| const HUserRecord<HInstruction*> InputRecordAt(size_t i) const { |
| return GetInputRecords()[i]; |
| } |
| |
| void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) { |
| ArrayRef<HUserRecord<HInstruction*>> input_records = GetInputRecords(); |
| input_records[index] = input; |
| } |
| |
| uint32_t GetPackedFields() const { |
| return packed_fields_; |
| } |
| |
| template <size_t flag> |
| bool GetPackedFlag() const { |
| return (packed_fields_ & (1u << flag)) != 0u; |
| } |
| |
| template <size_t flag> |
| void SetPackedFlag(bool value = true) { |
| packed_fields_ = (packed_fields_ & ~(1u << flag)) | ((value ? 1u : 0u) << flag); |
| } |
| |
| template <typename BitFieldType> |
| typename BitFieldType::value_type GetPackedField() const { |
| return BitFieldType::Decode(packed_fields_); |
| } |
| |
| template <typename BitFieldType> |
| void SetPackedField(typename BitFieldType::value_type value) { |
| DCHECK(IsUint<BitFieldType::size>(static_cast<uintptr_t>(value))); |
| packed_fields_ = BitFieldType::Update(value, packed_fields_); |
| } |
| |
| // Copy construction for the instruction (used for Clone function). |
| // |
| // Fields (e.g. lifetime, intervals and codegen info) associated with phases starting from |
| // prepare_for_register_allocator are not copied (set to default values). |
| // |
| // Copy constructors must be provided for every HInstruction type; default copy constructor is |
| // fine for most of them. However for some of the instructions a custom copy constructor must be |
| // specified (when instruction has non-trivially copyable fields and must have a special behaviour |
| // for copying them). |
| explicit HInstruction(const HInstruction& other) |
| : previous_(nullptr), |
| next_(nullptr), |
| block_(nullptr), |
| dex_pc_(other.dex_pc_), |
| id_(-1), |
| ssa_index_(-1), |
| packed_fields_(other.packed_fields_), |
| environment_(nullptr), |
| locations_(nullptr), |
| live_interval_(nullptr), |
| lifetime_position_(kNoLifetime), |
| side_effects_(other.side_effects_), |
| reference_type_handle_(other.reference_type_handle_) { |
| } |
| |
| private: |
| using InstructionKindField = |
| BitField<InstructionKind, kFieldInstructionKind, kFieldInstructionKindSize>; |
| |
| void FixUpUserRecordsAfterUseInsertion(HUseList<HInstruction*>::iterator fixup_end) { |
| auto before_use_node = uses_.before_begin(); |
| for (auto use_node = uses_.begin(); use_node != fixup_end; ++use_node) { |
| HInstruction* user = use_node->GetUser(); |
| size_t input_index = use_node->GetIndex(); |
| user->SetRawInputRecordAt(input_index, HUserRecord<HInstruction*>(this, before_use_node)); |
| before_use_node = use_node; |
| } |
| } |
| |
| void FixUpUserRecordsAfterUseRemoval(HUseList<HInstruction*>::iterator before_use_node) { |
| auto next = ++HUseList<HInstruction*>::iterator(before_use_node); |
| if (next != uses_.end()) { |
| HInstruction* next_user = next->GetUser(); |
| size_t next_index = next->GetIndex(); |
| DCHECK(next_user->InputRecordAt(next_index).GetInstruction() == this); |
| next_user->SetRawInputRecordAt(next_index, HUserRecord<HInstruction*>(this, before_use_node)); |
| } |
| } |
| |
| void FixUpUserRecordsAfterEnvUseInsertion(HUseList<HEnvironment*>::iterator env_fixup_end) { |
| auto before_env_use_node = env_uses_.before_begin(); |
| for (auto env_use_node = env_uses_.begin(); env_use_node != env_fixup_end; ++env_use_node) { |
| HEnvironment* user = env_use_node->GetUser(); |
| size_t input_index = env_use_node->GetIndex(); |
| user->GetVRegs()[input_index] = HUserRecord<HEnvironment*>(this, before_env_use_node); |
| before_env_use_node = env_use_node; |
| } |
| } |
| |
| void FixUpUserRecordsAfterEnvUseRemoval(HUseList<HEnvironment*>::iterator before_env_use_node) { |
| auto next = ++HUseList<HEnvironment*>::iterator(before_env_use_node); |
| if (next != env_uses_.end()) { |
| HEnvironment* next_user = next->GetUser(); |
| size_t next_index = next->GetIndex(); |
| DCHECK(next_user->GetVRegs()[next_index].GetInstruction() == this); |
| next_user->GetVRegs()[next_index] = HUserRecord<HEnvironment*>(this, before_env_use_node); |
| } |
| } |
| |
| HInstruction* previous_; |
| HInstruction* next_; |
| HBasicBlock* block_; |
| const uint32_t dex_pc_; |
| |
| // An instruction gets an id when it is added to the graph. |
| // It reflects creation order. A negative id means the instruction |
| // has not been added to the graph. |
| int id_; |
| |
| // When doing liveness analysis, instructions that have uses get an SSA index. |
| int ssa_index_; |
| |
| // Packed fields. |
| uint32_t packed_fields_; |
| |
| // List of instructions that have this instruction as input. |
| HUseList<HInstruction*> uses_; |
| |
| // List of environments that contain this instruction. |
| HUseList<HEnvironment*> env_uses_; |
| |
| // The environment associated with this instruction. Not null if the instruction |
| // might jump out of the method. |
| HEnvironment* environment_; |
| |
| // Set by the code generator. |
| LocationSummary* locations_; |
| |
| // Set by the liveness analysis. |
| LiveInterval* live_interval_; |
| |
| // Set by the liveness analysis, this is the position in a linear |
| // order of blocks where this instruction's live interval start. |
| size_t lifetime_position_; |
| |
| SideEffects side_effects_; |
| |
| // The reference handle part of the reference type info. |
| // The IsExact() flag is stored in packed fields. |
| // TODO: for primitive types this should be marked as invalid. |
| ReferenceTypeInfo::TypeHandle reference_type_handle_; |
| |
| friend class GraphChecker; |
| friend class HBasicBlock; |
| friend class HEnvironment; |
| friend class HGraph; |
| friend class HInstructionList; |
| }; |
| |
| std::ostream& operator<<(std::ostream& os, HInstruction::InstructionKind rhs); |
| std::ostream& operator<<(std::ostream& os, const HInstruction::NoArgsDump rhs); |
| std::ostream& operator<<(std::ostream& os, const HInstruction::ArgsDump rhs); |
| std::ostream& operator<<(std::ostream& os, const HUseList<HInstruction*>& lst); |
| std::ostream& operator<<(std::ostream& os, const HUseList<HEnvironment*>& lst); |
| |
| // Forward declarations for friends |
| template <typename InnerIter> struct HSTLInstructionIterator; |
| |
| // Iterates over the instructions, while preserving the next instruction |
| // in case the current instruction gets removed from the list by the user |
| // of this iterator. |
| class HInstructionIterator : public ValueObject { |
| public: |
| explicit HInstructionIterator(const HInstructionList& instructions) |
| : instruction_(instructions.first_instruction_) { |
| next_ = Done() ? nullptr : instruction_->GetNext(); |
| } |
| |
| bool Done() const { return instruction_ == nullptr; } |
| HInstruction* Current() const { return instruction_; } |
| void Advance() { |
| instruction_ = next_; |
| next_ = Done() ? nullptr : instruction_->GetNext(); |
| } |
| |
| private: |
| HInstructionIterator() : instruction_(nullptr), next_(nullptr) {} |
| |
| HInstruction* instruction_; |
| HInstruction* next_; |
| |
| friend struct HSTLInstructionIterator<HInstructionIterator>; |
| }; |
| |
| // Iterates over the instructions without saving the next instruction, |
| // therefore handling changes in the graph potentially made by the user |
| // of this iterator. |
| class HInstructionIteratorHandleChanges : public ValueObject { |
| public: |
| explicit HInstructionIteratorHandleChanges(const HInstructionList& instructions) |
| : instruction_(instructions.first_instruction_) { |
| } |
| |
| bool Done() const { return instruction_ == nullptr; } |
| HInstruction* Current() const { return instruction_; } |
| void Advance() { |
| instruction_ = instruction_->GetNext(); |
| } |
| |
| private: |
| HInstructionIteratorHandleChanges() : instruction_(nullptr) {} |
| |
| HInstruction* instruction_; |
| |
| friend struct HSTLInstructionIterator<HInstructionIteratorHandleChanges>; |
| }; |
| |
| |
| class HBackwardInstructionIterator : public ValueObject { |
| public: |
| explicit HBackwardInstructionIterator(const HInstructionList& instructions) |
| : instruction_(instructions.last_instruction_) { |
| next_ = Done() ? nullptr : instruction_->GetPrevious(); |
| } |
| |
| explicit HBackwardInstructionIterator(HInstruction* instruction) : instruction_(instruction) { |
| next_ = Done() ? nullptr : instruction_->GetPrevious(); |
| } |
| |
| bool Done() const { return instruction_ == nullptr; } |
| HInstruction* Current() const { return instruction_; } |
| void Advance() { |
| instruction_ = next_; |
| next_ = Done() ? nullptr : instruction_->GetPrevious(); |
| } |
| |
| private: |
| HBackwardInstructionIterator() : instruction_(nullptr), next_(nullptr) {} |
| |
| HInstruction* instruction_; |
| HInstruction* next_; |
| |
| friend struct HSTLInstructionIterator<HBackwardInstructionIterator>; |
| }; |
| |
| template <typename InnerIter> |
| struct HSTLInstructionIterator : public ValueObject { |
| public: |
| using iterator_category = std::forward_iterator_tag; |
| using value_type = HInstruction*; |
| using difference_type = ptrdiff_t; |
| using pointer = void; |
| using reference = void; |
| |
| static_assert(std::is_same_v<InnerIter, HBackwardInstructionIterator> || |
| std::is_same_v<InnerIter, HInstructionIterator> || |
| std::is_same_v<InnerIter, HInstructionIteratorHandleChanges>, |
| "Unknown wrapped iterator!"); |
| |
| explicit HSTLInstructionIterator(InnerIter inner) : inner_(inner) {} |
| HInstruction* operator*() const { |
| DCHECK(inner_.Current() != nullptr); |
| return inner_.Current(); |
| } |
| |
| HSTLInstructionIterator<InnerIter>& operator++() { |
| DCHECK(*this != HSTLInstructionIterator<InnerIter>::EndIter()); |
| inner_.Advance(); |
| return *this; |
| } |
| |
| HSTLInstructionIterator<InnerIter> operator++(int) { |
| HSTLInstructionIterator<InnerIter> prev(*this); |
| ++(*this); |
| return prev; |
| } |
| |
| bool operator==(const HSTLInstructionIterator<InnerIter>& other) const { |
| return inner_.Current() == other.inner_.Current(); |
| } |
| |
| bool operator!=(const HSTLInstructionIterator<InnerIter>& other) const { |
| return !(*this == other); |
| } |
| |
| static HSTLInstructionIterator<InnerIter> EndIter() { |
| return HSTLInstructionIterator<InnerIter>(InnerIter()); |
| } |
| |
| private: |
| InnerIter inner_; |
| }; |
| |
| template <typename InnerIter> |
| IterationRange<HSTLInstructionIterator<InnerIter>> MakeSTLInstructionIteratorRange(InnerIter iter) { |
| return MakeIterationRange(HSTLInstructionIterator<InnerIter>(iter), |
| HSTLInstructionIterator<InnerIter>::EndIter()); |
| } |
| |
| class HVariableInputSizeInstruction : public HInstruction { |
| public: |
| using HInstruction::GetInputRecords; // Keep the const version visible. |
| ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() override { |
| return ArrayRef<HUserRecord<HInstruction*>>(inputs_); |
| } |
| |
| void AddInput(HInstruction* input); |
| void InsertInputAt(size_t index, HInstruction* input); |
| void RemoveInputAt(size_t index); |
| |
| // Removes all the inputs. |
| // Also removes this instructions from each input's use list |
| // (for non-environment uses only). |
| void RemoveAllInputs(); |
| |
| protected: |
| HVariableInputSizeInstruction(InstructionKind inst_kind, |
| SideEffects side_effects, |
| uint32_t dex_pc, |
| ArenaAllocator* allocator, |
| size_t number_of_inputs, |
| ArenaAllocKind kind) |
|