blob: 676a9b9dd2e0428352bdee45cd098916cffc27ff [file] [log] [blame]
/*
* 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)