summaryrefslogtreecommitdiff
path: root/compiler/optimizing/nodes.h
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/optimizing/nodes.h')
-rw-r--r--compiler/optimizing/nodes.h232
1 files changed, 115 insertions, 117 deletions
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index cfb71791f4..7067aabaa1 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -44,7 +44,6 @@ class HBasicBlock;
class HCurrentMethod;
class HDoubleConstant;
class HEnvironment;
-class HFakeString;
class HFloatConstant;
class HGraphBuilder;
class HGraphVisitor;
@@ -98,11 +97,10 @@ enum IfCondition {
kCondAE, // >=
};
-enum BuildSsaResult {
- kBuildSsaFailNonNaturalLoop,
- kBuildSsaFailThrowCatchLoop,
- kBuildSsaFailAmbiguousArrayOp,
- kBuildSsaSuccess,
+enum GraphAnalysisResult {
+ kAnalysisFailThrowCatchLoop,
+ kAnalysisFailAmbiguousArrayOp,
+ kAnalysisSuccess,
};
class HInstructionList : public ValueObject {
@@ -289,6 +287,7 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
temporaries_vreg_slots_(0),
has_bounds_checks_(false),
has_try_catch_(false),
+ has_irreducible_loops_(false),
debuggable_(debuggable),
current_instruction_id_(start_instruction_id),
dex_file_(dex_file),
@@ -324,20 +323,20 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
// Try building the SSA form of this graph, with dominance computation and
// loop recognition. Returns a code specifying that it was successful or the
// reason for failure.
- BuildSsaResult TryBuildingSsa(StackHandleScopeCollection* handles);
+ GraphAnalysisResult TryBuildingSsa(StackHandleScopeCollection* handles);
void ComputeDominanceInformation();
void ClearDominanceInformation();
-
- void BuildDominatorTree();
+ void ClearLoopInformation();
+ void FindBackEdges(ArenaBitVector* visited);
+ GraphAnalysisResult BuildDominatorTree();
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 not natural, that is the header does not dominate a back edge, or if it
// is a throw-catch loop, i.e. the header is a catch block.
- BuildSsaResult AnalyzeNaturalLoops() const;
+ GraphAnalysisResult AnalyzeLoops() const;
// Iterate over blocks to compute try block membership. Needs reverse post
// order and loop information.
@@ -482,6 +481,9 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
bool HasTryCatch() const { return has_try_catch_; }
void SetHasTryCatch(bool value) { has_try_catch_ = value; }
+ bool HasIrreducibleLoops() const { return has_irreducible_loops_; }
+ void SetHasIrreducibleLoops(bool value) { has_irreducible_loops_ = value; }
+
ArtMethod* GetArtMethod() const { return art_method_; }
void SetArtMethod(ArtMethod* method) { art_method_ = method; }
@@ -491,7 +493,6 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
HInstruction* InsertOppositeCondition(HInstruction* cond, HInstruction* cursor);
private:
- void FindBackEdges(ArenaBitVector* visited);
void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const;
void RemoveDeadBlocks(const ArenaBitVector& visited);
@@ -558,6 +559,9 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
// try/catch-related passes if false.
bool has_try_catch_;
+ // Flag whether there are any irreducible loops in the graph.
+ bool has_irreducible_loops_;
+
// 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.
@@ -613,12 +617,17 @@ class HLoopInformation : public ArenaObject<kArenaAllocLoopInfo> {
HLoopInformation(HBasicBlock* header, HGraph* graph)
: header_(header),
suspend_check_(nullptr),
+ irreducible_(false),
back_edges_(graph->GetArena()->Adapter(kArenaAllocLoopInfoBackEdges)),
// Make bit vector growable, as the number of blocks may change.
blocks_(graph->GetArena(), graph->GetBlocks().size(), true) {
back_edges_.reserve(kDefaultNumberOfBackEdges);
}
+ bool IsIrreducible() const { return irreducible_; }
+
+ void Dump(std::ostream& os);
+
HBasicBlock* GetHeader() const {
return header_;
}
@@ -661,15 +670,8 @@ class HLoopInformation : public ArenaObject<kArenaAllocLoopInfo> {
ReplaceElement(back_edges_, existing, new_back_edge);
}
- // Finds blocks that are part of this loop. Returns whether the loop is a natural loop,
- // that is the header dominates the back edge.
- bool Populate();
-
- // Reanalyzes the loop by removing loop info from its blocks and re-running
- // Populate(). If there are no back edges left, the loop info is completely
- // removed as well as its SuspendCheck instruction. It must be run on nested
- // inner loops first.
- void Update();
+ // Finds blocks that are part of this loop.
+ void Populate();
// Returns whether this loop information contains `block`.
// Note that this loop information *must* be populated before entering this function.
@@ -690,9 +692,11 @@ class HLoopInformation : public ArenaObject<kArenaAllocLoopInfo> {
private:
// Internal recursive implementation of `Populate`.
void PopulateRecursive(HBasicBlock* block);
+ void PopulateIrreducibleRecursive(HBasicBlock* block);
HBasicBlock* header_;
HSuspendCheck* suspend_check_;
+ bool irreducible_;
ArenaVector<HBasicBlock*> back_edges_;
ArenaBitVector blocks_;
@@ -856,6 +860,8 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> {
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);
@@ -1019,6 +1025,11 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> {
return GetPredecessors()[0] == GetLoopInformation()->GetPreHeader();
}
+ bool IsFirstPredecessorBackEdge() const {
+ DCHECK(IsLoopHeader());
+ return GetLoopInformation()->IsBackEdge(*GetPredecessors()[0]);
+ }
+
HLoopInformation* GetLoopInformation() const {
return loop_information_;
}
@@ -1156,7 +1167,6 @@ class HLoopInformationOutwardIterator : public ValueObject {
M(DoubleConstant, Constant) \
M(Equal, Condition) \
M(Exit, Instruction) \
- M(FakeString, Instruction) \
M(FloatConstant, Constant) \
M(Goto, Instruction) \
M(GreaterThan, Condition) \
@@ -1831,7 +1841,10 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> {
void SetBlock(HBasicBlock* block) { block_ = block; }
bool IsInBlock() const { return block_ != nullptr; }
bool IsInLoop() const { return block_->IsInLoop(); }
- bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); }
+ bool IsLoopHeaderPhi() const { return IsPhi() && block_->IsLoopHeader(); }
+ bool IsIrreducibleLoopHeaderPhi() const {
+ return IsLoopHeaderPhi() && GetBlock()->GetLoopInformation()->IsIrreducible();
+ }
virtual size_t InputCount() const = 0;
HInstruction* InputAt(size_t i) const { return InputRecordAt(i).GetInstruction(); }
@@ -1868,6 +1881,10 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> {
return false;
}
+ virtual bool IsActualObject() const {
+ return GetType() == Primitive::kPrimNot;
+ }
+
void SetReferenceTypeInfo(ReferenceTypeInfo rti);
ReferenceTypeInfo GetReferenceTypeInfo() const {
@@ -2487,8 +2504,10 @@ class HTryBoundary : public HTemplateInstruction<0> {
// Deoptimize to interpreter, upon checking a condition.
class HDeoptimize : public HTemplateInstruction<1> {
public:
+ // We set CanTriggerGC to prevent any intermediate address to be live
+ // at the point of the `HDeoptimize`.
HDeoptimize(HInstruction* cond, uint32_t dex_pc)
- : HTemplateInstruction(SideEffects::None(), dex_pc) {
+ : HTemplateInstruction(SideEffects::CanTriggerGC(), dex_pc) {
SetRawInputAt(0, cond);
}
@@ -3258,6 +3277,61 @@ class HDoubleConstant : public HConstant {
DISALLOW_COPY_AND_ASSIGN(HDoubleConstant);
};
+class HNewInstance : public HExpression<2> {
+ public:
+ HNewInstance(HInstruction* cls,
+ HCurrentMethod* current_method,
+ uint32_t dex_pc,
+ uint16_t type_index,
+ const DexFile& dex_file,
+ bool can_throw,
+ bool finalizable,
+ QuickEntrypointEnum entrypoint)
+ : HExpression(Primitive::kPrimNot, SideEffects::CanTriggerGC(), dex_pc),
+ type_index_(type_index),
+ dex_file_(dex_file),
+ can_throw_(can_throw),
+ finalizable_(finalizable),
+ entrypoint_(entrypoint) {
+ SetRawInputAt(0, cls);
+ SetRawInputAt(1, current_method);
+ }
+
+ uint16_t GetTypeIndex() const { return type_index_; }
+ const DexFile& GetDexFile() const { return dex_file_; }
+
+ // Calls runtime so needs an environment.
+ bool NeedsEnvironment() const OVERRIDE { return true; }
+
+ // It may throw when called on type that's not instantiable/accessible.
+ // It can throw OOME.
+ // TODO: distinguish between the two cases so we can for example allow allocation elimination.
+ bool CanThrow() const OVERRIDE { return can_throw_ || true; }
+
+ bool IsFinalizable() const { return finalizable_; }
+
+ bool CanBeNull() const OVERRIDE { return false; }
+
+ QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; }
+
+ void SetEntrypoint(QuickEntrypointEnum entrypoint) {
+ entrypoint_ = entrypoint;
+ }
+
+ bool IsStringAlloc() const;
+
+ DECLARE_INSTRUCTION(NewInstance);
+
+ private:
+ const uint16_t type_index_;
+ const DexFile& dex_file_;
+ const bool can_throw_;
+ const bool finalizable_;
+ QuickEntrypointEnum entrypoint_;
+
+ DISALLOW_COPY_AND_ASSIGN(HNewInstance);
+};
+
enum class Intrinsics {
#define OPTIMIZING_INTRINSICS(Name, IsStatic, NeedsEnvironmentOrCache, SideEffects, Exceptions) \
k ## Name,
@@ -3551,10 +3625,9 @@ class HInvokeStaticOrDirect : public HInvoke {
// Get the index of the special input, if any.
//
- // If the invoke IsStringInit(), it initially has a HFakeString special argument
- // which is removed by the instruction simplifier; if the invoke HasCurrentMethodInput(),
- // the "special input" is the current method pointer; otherwise there may be one
- // platform-specific special input, such as PC-relative addressing base.
+ // If the invoke HasCurrentMethodInput(), the "special input" is the current
+ // method pointer; otherwise there may be one platform-specific special input,
+ // such as PC-relative addressing base.
uint32_t GetSpecialInputIndex() const { return GetNumberOfArguments(); }
InvokeType GetOptimizedInvokeType() const { return optimized_invoke_type_; }
@@ -3628,21 +3701,13 @@ class HInvokeStaticOrDirect : public HInvoke {
DCHECK(!IsStaticWithExplicitClinitCheck());
}
- bool IsStringFactoryFor(HFakeString* str) const {
- if (!IsStringInit()) return false;
- DCHECK(!HasCurrentMethodInput());
- if (InputCount() == (number_of_arguments_)) return false;
- return InputAt(InputCount() - 1)->AsFakeString() == str;
- }
-
- void RemoveFakeStringArgumentAsLastInput() {
+ HInstruction* GetAndRemoveThisArgumentOfStringInit() {
DCHECK(IsStringInit());
- size_t last_input_index = InputCount() - 1;
- HInstruction* last_input = InputAt(last_input_index);
- DCHECK(last_input != nullptr);
- DCHECK(last_input->IsFakeString()) << last_input->DebugName();
- RemoveAsUserOfInput(last_input_index);
+ size_t index = InputCount() - 1;
+ HInstruction* input = InputAt(index);
+ RemoveAsUserOfInput(index);
inputs_.pop_back();
+ return input;
}
// Is this a call to a static method whose declaring class has an
@@ -3749,59 +3814,6 @@ class HInvokeInterface : public HInvoke {
DISALLOW_COPY_AND_ASSIGN(HInvokeInterface);
};
-class HNewInstance : public HExpression<2> {
- public:
- HNewInstance(HInstruction* cls,
- HCurrentMethod* current_method,
- uint32_t dex_pc,
- uint16_t type_index,
- const DexFile& dex_file,
- bool can_throw,
- bool finalizable,
- QuickEntrypointEnum entrypoint)
- : HExpression(Primitive::kPrimNot, SideEffects::CanTriggerGC(), dex_pc),
- type_index_(type_index),
- dex_file_(dex_file),
- can_throw_(can_throw),
- finalizable_(finalizable),
- entrypoint_(entrypoint) {
- SetRawInputAt(0, cls);
- SetRawInputAt(1, current_method);
- }
-
- uint16_t GetTypeIndex() const { return type_index_; }
- const DexFile& GetDexFile() const { return dex_file_; }
-
- // Calls runtime so needs an environment.
- bool NeedsEnvironment() const OVERRIDE { return true; }
-
- // It may throw when called on type that's not instantiable/accessible.
- // It can throw OOME.
- // TODO: distinguish between the two cases so we can for example allow allocation elimination.
- bool CanThrow() const OVERRIDE { return can_throw_ || true; }
-
- bool IsFinalizable() const { return finalizable_; }
-
- bool CanBeNull() const OVERRIDE { return false; }
-
- QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; }
-
- void SetEntrypoint(QuickEntrypointEnum entrypoint) {
- entrypoint_ = entrypoint;
- }
-
- DECLARE_INSTRUCTION(NewInstance);
-
- private:
- const uint16_t type_index_;
- const DexFile& dex_file_;
- const bool can_throw_;
- const bool finalizable_;
- QuickEntrypointEnum entrypoint_;
-
- DISALLOW_COPY_AND_ASSIGN(HNewInstance);
-};
-
class HNeg : public HUnaryOperation {
public:
HNeg(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc = kNoDexPc)
@@ -4016,8 +4028,10 @@ class HRem : public HBinaryOperation {
class HDivZeroCheck : public HExpression<1> {
public:
+ // `HDivZeroCheck` can trigger GC, as it may call the `ArithmeticException`
+ // constructor.
HDivZeroCheck(HInstruction* value, uint32_t dex_pc)
- : HExpression(value->GetType(), SideEffects::None(), dex_pc) {
+ : HExpression(value->GetType(), SideEffects::CanTriggerGC(), dex_pc) {
SetRawInputAt(0, value);
}
@@ -4538,8 +4552,10 @@ class HPhi : public HInstruction {
class HNullCheck : public HExpression<1> {
public:
+ // `HNullCheck` can trigger GC, as it may call the `NullPointerException`
+ // constructor.
HNullCheck(HInstruction* value, uint32_t dex_pc)
- : HExpression(value->GetType(), SideEffects::None(), dex_pc) {
+ : HExpression(value->GetType(), SideEffects::CanTriggerGC(), dex_pc) {
SetRawInputAt(0, value);
}
@@ -4860,8 +4876,10 @@ class HArrayLength : public HExpression<1> {
class HBoundsCheck : public HExpression<2> {
public:
+ // `HBoundsCheck` can trigger GC, as it may call the `IndexOutOfBoundsException`
+ // constructor.
HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc)
- : HExpression(index->GetType(), SideEffects::None(), dex_pc) {
+ : HExpression(index->GetType(), SideEffects::CanTriggerGC(), dex_pc) {
DCHECK(index->GetType() == Primitive::kPrimInt);
SetRawInputAt(0, index);
SetRawInputAt(1, length);
@@ -5576,26 +5594,6 @@ class HMonitorOperation : public HTemplateInstruction<1> {
DISALLOW_COPY_AND_ASSIGN(HMonitorOperation);
};
-/**
- * A HInstruction used as a marker for the replacement of new + <init>
- * of a String to a call to a StringFactory. Only baseline will see
- * the node at code generation, where it will be be treated as null.
- * When compiling non-baseline, `HFakeString` instructions are being removed
- * in the instruction simplifier.
- */
-class HFakeString : public HTemplateInstruction<0> {
- public:
- explicit HFakeString(uint32_t dex_pc = kNoDexPc)
- : HTemplateInstruction(SideEffects::None(), dex_pc) {}
-
- Primitive::Type GetType() const OVERRIDE { return Primitive::kPrimNot; }
-
- DECLARE_INSTRUCTION(FakeString);
-
- private:
- DISALLOW_COPY_AND_ASSIGN(HFakeString);
-};
-
class MoveOperands : public ArenaObject<kArenaAllocMoveOperands> {
public:
MoveOperands(Location source,
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-22 01:49:39 +0000