summaryrefslogtreecommitdiffstats
path: root/compiler/optimizing
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/optimizing')
-rw-r--r--compiler/optimizing/builder.cc2
-rw-r--r--compiler/optimizing/instruction_simplifier.cc9
-rw-r--r--compiler/optimizing/instruction_simplifier.h4
-rw-r--r--compiler/optimizing/nodes.h46
-rw-r--r--compiler/optimizing/optimizing_compiler.cc25
-rw-r--r--compiler/optimizing/primitive_type_propagation.cc (renamed from compiler/optimizing/ssa_type_propagation.cc)16
-rw-r--r--compiler/optimizing/primitive_type_propagation.h (renamed from compiler/optimizing/ssa_type_propagation.h)14
-rw-r--r--compiler/optimizing/reference_type_propagation.cc94
-rw-r--r--compiler/optimizing/reference_type_propagation.h53
-rw-r--r--compiler/optimizing/ssa_builder.cc4
10 files changed, 226 insertions, 41 deletions
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index 9c2facb75e..21c58598d0 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -161,7 +161,7 @@ void HGraphBuilder::InitializeParameters(uint16_t number_of_parameters) {
if (!dex_compilation_unit_->IsStatic()) {
// Add the implicit 'this' argument, not expressed in the signature.
HParameterValue* parameter =
- new (arena_) HParameterValue(parameter_index++, Primitive::kPrimNot);
+ new (arena_) HParameterValue(parameter_index++, Primitive::kPrimNot, true);
entry_block_->AddInstruction(parameter);
HLocal* local = GetLocalAt(locals_index++);
entry_block_->AddInstruction(new (arena_) HStoreLocal(local, parameter));
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 63bc4ae671..17c8f337ca 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -27,6 +27,7 @@ class InstructionSimplifierVisitor : public HGraphVisitor {
void VisitEqual(HEqual* equal) OVERRIDE;
void VisitArraySet(HArraySet* equal) OVERRIDE;
void VisitTypeConversion(HTypeConversion* instruction) OVERRIDE;
+ void VisitNullCheck(HNullCheck* instruction) OVERRIDE;
};
void InstructionSimplifier::Run() {
@@ -34,6 +35,14 @@ void InstructionSimplifier::Run() {
visitor.VisitInsertionOrder();
}
+void InstructionSimplifierVisitor::VisitNullCheck(HNullCheck* null_check) {
+ HInstruction* obj = null_check->InputAt(0);
+ if (!obj->CanBeNull()) {
+ null_check->ReplaceWith(obj);
+ null_check->GetBlock()->RemoveInstruction(null_check);
+ }
+}
+
void InstructionSimplifierVisitor::VisitSuspendCheck(HSuspendCheck* check) {
HBasicBlock* block = check->GetBlock();
// Currently always keep the suspend check at entry.
diff --git a/compiler/optimizing/instruction_simplifier.h b/compiler/optimizing/instruction_simplifier.h
index 7068c7fc10..bca6697d05 100644
--- a/compiler/optimizing/instruction_simplifier.h
+++ b/compiler/optimizing/instruction_simplifier.h
@@ -27,8 +27,8 @@ namespace art {
*/
class InstructionSimplifier : public HOptimization {
public:
- explicit InstructionSimplifier(HGraph* graph)
- : HOptimization(graph, true, "instruction_simplifier") {}
+ explicit InstructionSimplifier(HGraph* graph, const char* name = "instruction_simplifier")
+ : HOptimization(graph, true, name) {}
void Run() OVERRIDE;
};
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 2cc021cccf..bddcf37ae4 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -847,6 +847,10 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> {
virtual bool CanThrow() const { return false; }
bool HasSideEffects() const { return side_effects_.HasSideEffects(); }
+ // Does not apply for all instructions, but having this at top level greatly
+ // simplifies the null check elimination.
+ virtual bool CanBeNull() const { return true; }
+
virtual bool CanDoImplicitNullCheck() const { return false; }
void AddUseAt(HInstruction* user, size_t index) {
@@ -1802,6 +1806,8 @@ class HNewInstance : public HExpression<0> {
// TODO: optimize when possible.
bool CanThrow() const OVERRIDE { return true; }
+ bool CanBeNull() const OVERRIDE { return false; }
+
DECLARE_INSTRUCTION(NewInstance);
private:
@@ -1838,7 +1844,9 @@ class HNewArray : public HExpression<1> {
uint16_t GetTypeIndex() const { return type_index_; }
// Calls runtime so needs an environment.
- virtual bool NeedsEnvironment() const { return true; }
+ bool NeedsEnvironment() const OVERRIDE { return true; }
+
+ bool CanBeNull() const OVERRIDE { return false; }
DECLARE_INSTRUCTION(NewArray);
@@ -2088,18 +2096,23 @@ class HXor : public HBinaryOperation {
// the calling convention.
class HParameterValue : public HExpression<0> {
public:
- HParameterValue(uint8_t index, Primitive::Type parameter_type)
- : HExpression(parameter_type, SideEffects::None()), index_(index) {}
+ HParameterValue(uint8_t index, Primitive::Type parameter_type, bool is_this = false)
+ : HExpression(parameter_type, SideEffects::None()), index_(index), is_this_(is_this) {}
uint8_t GetIndex() const { return index_; }
+ bool CanBeNull() const OVERRIDE { return !is_this_; }
+
DECLARE_INSTRUCTION(ParameterValue);
private:
// The index of this parameter in the parameters list. Must be less
- // than HGraph::number_of_in_vregs_;
+ // than HGraph::number_of_in_vregs_.
const uint8_t index_;
+ // Whether or not the parameter value corresponds to 'this' argument.
+ const bool is_this_;
+
DISALLOW_COPY_AND_ASSIGN(HParameterValue);
};
@@ -2158,22 +2171,26 @@ class HPhi : public HInstruction {
inputs_(arena, number_of_inputs),
reg_number_(reg_number),
type_(type),
- is_live_(false) {
+ is_live_(false),
+ can_be_null_(true) {
inputs_.SetSize(number_of_inputs);
}
- virtual size_t InputCount() const { return inputs_.Size(); }
- virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); }
+ size_t InputCount() const OVERRIDE { return inputs_.Size(); }
+ HInstruction* InputAt(size_t i) const OVERRIDE { return inputs_.Get(i); }
- virtual void SetRawInputAt(size_t index, HInstruction* input) {
+ void SetRawInputAt(size_t index, HInstruction* input) OVERRIDE {
inputs_.Put(index, input);
}
void AddInput(HInstruction* input);
- virtual Primitive::Type GetType() const { return type_; }
+ Primitive::Type GetType() const OVERRIDE { return type_; }
void SetType(Primitive::Type type) { type_ = type; }
+ bool CanBeNull() const OVERRIDE { return can_be_null_; }
+ void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; }
+
uint32_t GetRegNumber() const { return reg_number_; }
void SetDead() { is_live_ = false; }
@@ -2188,6 +2205,7 @@ class HPhi : public HInstruction {
const uint32_t reg_number_;
Primitive::Type type_;
bool is_live_;
+ bool can_be_null_;
DISALLOW_COPY_AND_ASSIGN(HPhi);
};
@@ -2199,15 +2217,17 @@ class HNullCheck : public HExpression<1> {
SetRawInputAt(0, value);
}
- virtual bool CanBeMoved() const { return true; }
- virtual bool InstructionDataEquals(HInstruction* other) const {
+ bool CanBeMoved() const OVERRIDE { return true; }
+ bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
UNUSED(other);
return true;
}
- virtual bool NeedsEnvironment() const { return true; }
+ bool NeedsEnvironment() const OVERRIDE { return true; }
- virtual bool CanThrow() const { return true; }
+ bool CanThrow() const OVERRIDE { return true; }
+
+ bool CanBeNull() const OVERRIDE { return false; }
uint32_t GetDexPc() const { return dex_pc_; }
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 4f05afa1a6..705345b279 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -43,6 +43,7 @@
#include "ssa_builder.h"
#include "ssa_phi_elimination.h"
#include "ssa_liveness_analysis.h"
+#include "reference_type_propagation.h"
#include "utils/arena_allocator.h"
namespace art {
@@ -196,6 +197,18 @@ static bool CanOptimize(const DexFile::CodeItem& code_item) {
return code_item.tries_size_ == 0;
}
+static void RunOptimizations(HOptimization* optimizations[],
+ size_t length,
+ const HGraphVisualizer& visualizer) {
+ for (size_t i = 0; i < length; ++i) {
+ HOptimization* optimization = optimizations[i];
+ visualizer.DumpGraph(optimization->GetPassName(), /*is_after=*/false);
+ optimization->Run();
+ visualizer.DumpGraph(optimization->GetPassName(), /*is_after=*/true);
+ optimization->Check();
+ }
+}
+
static void RunOptimizations(HGraph* graph,
CompilerDriver* driver,
OptimizingCompilerStats* stats,
@@ -213,7 +226,8 @@ static void RunOptimizations(HGraph* graph,
SideEffectsAnalysis side_effects(graph);
GVNOptimization gvn(graph, side_effects);
BoundsCheckElimination bce(graph);
- InstructionSimplifier simplify2(graph);
+ ReferenceTypePropagation type_propagation(graph);
+ InstructionSimplifier simplify2(graph, "instruction_simplifier_after_types");
IntrinsicsRecognizer intrinsics(graph, dex_compilation_unit.GetDexFile(), driver);
@@ -229,16 +243,11 @@ static void RunOptimizations(HGraph* graph,
&side_effects,
&gvn,
&bce,
+ &type_propagation,
&simplify2
};
- for (size_t i = 0; i < arraysize(optimizations); ++i) {
- HOptimization* optimization = optimizations[i];
- visualizer.DumpGraph(optimization->GetPassName(), /*is_after=*/false);
- optimization->Run();
- visualizer.DumpGraph(optimization->GetPassName(), /*is_after=*/true);
- optimization->Check();
- }
+ RunOptimizations(optimizations, arraysize(optimizations), visualizer);
}
// The stack map we generate must be 4-byte aligned on ARM. Since existing
diff --git a/compiler/optimizing/ssa_type_propagation.cc b/compiler/optimizing/primitive_type_propagation.cc
index 947427b67f..7e274f6ebf 100644
--- a/compiler/optimizing/ssa_type_propagation.cc
+++ b/compiler/optimizing/primitive_type_propagation.cc
@@ -14,10 +14,10 @@
* limitations under the License.
*/
-#include "ssa_builder.h"
-#include "ssa_type_propagation.h"
+#include "primitive_type_propagation.h"
#include "nodes.h"
+#include "ssa_builder.h"
namespace art {
@@ -39,7 +39,7 @@ static Primitive::Type MergeTypes(Primitive::Type existing, Primitive::Type new_
// Re-compute and update the type of the instruction. Returns
// whether or not the type was changed.
-bool SsaTypePropagation::UpdateType(HPhi* phi) {
+bool PrimitiveTypePropagation::UpdateType(HPhi* phi) {
Primitive::Type existing = phi->GetType();
Primitive::Type new_type = existing;
@@ -67,14 +67,14 @@ bool SsaTypePropagation::UpdateType(HPhi* phi) {
return existing != new_type;
}
-void SsaTypePropagation::Run() {
+void PrimitiveTypePropagation::Run() {
for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
VisitBasicBlock(it.Current());
}
ProcessWorklist();
}
-void SsaTypePropagation::VisitBasicBlock(HBasicBlock* block) {
+void PrimitiveTypePropagation::VisitBasicBlock(HBasicBlock* block) {
if (block->IsLoopHeader()) {
for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
HPhi* phi = it.Current()->AsPhi();
@@ -100,7 +100,7 @@ void SsaTypePropagation::VisitBasicBlock(HBasicBlock* block) {
}
}
-void SsaTypePropagation::ProcessWorklist() {
+void PrimitiveTypePropagation::ProcessWorklist() {
while (!worklist_.IsEmpty()) {
HPhi* instruction = worklist_.Pop();
if (UpdateType(instruction)) {
@@ -109,11 +109,11 @@ void SsaTypePropagation::ProcessWorklist() {
}
}
-void SsaTypePropagation::AddToWorklist(HPhi* instruction) {
+void PrimitiveTypePropagation::AddToWorklist(HPhi* instruction) {
worklist_.Add(instruction);
}
-void SsaTypePropagation::AddDependentInstructionsToWorklist(HPhi* instruction) {
+void PrimitiveTypePropagation::AddDependentInstructionsToWorklist(HPhi* instruction) {
for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
HPhi* phi = it.Current()->GetUser()->AsPhi();
if (phi != nullptr) {
diff --git a/compiler/optimizing/ssa_type_propagation.h b/compiler/optimizing/primitive_type_propagation.h
index f4d3d6344a..1374cbb6ab 100644
--- a/compiler/optimizing/ssa_type_propagation.h
+++ b/compiler/optimizing/primitive_type_propagation.h
@@ -14,17 +14,17 @@
* limitations under the License.
*/
-#ifndef ART_COMPILER_OPTIMIZING_SSA_TYPE_PROPAGATION_H_
-#define ART_COMPILER_OPTIMIZING_SSA_TYPE_PROPAGATION_H_
+#ifndef ART_COMPILER_OPTIMIZING_PRIMITIVE_TYPE_PROPAGATION_H_
+#define ART_COMPILER_OPTIMIZING_PRIMITIVE_TYPE_PROPAGATION_H_
#include "nodes.h"
namespace art {
-// Compute and propagate types of phis in the graph.
-class SsaTypePropagation : public ValueObject {
+// Compute and propagate primitive types of phis in the graph.
+class PrimitiveTypePropagation : public ValueObject {
public:
- explicit SsaTypePropagation(HGraph* graph)
+ explicit PrimitiveTypePropagation(HGraph* graph)
: graph_(graph), worklist_(graph->GetArena(), kDefaultWorklistSize) {}
void Run();
@@ -41,9 +41,9 @@ class SsaTypePropagation : public ValueObject {
static constexpr size_t kDefaultWorklistSize = 8;
- DISALLOW_COPY_AND_ASSIGN(SsaTypePropagation);
+ DISALLOW_COPY_AND_ASSIGN(PrimitiveTypePropagation);
};
} // namespace art
-#endif // ART_COMPILER_OPTIMIZING_SSA_TYPE_PROPAGATION_H_
+#endif // ART_COMPILER_OPTIMIZING_PRIMITIVE_TYPE_PROPAGATION_H_
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
new file mode 100644
index 0000000000..24e6837f45
--- /dev/null
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -0,0 +1,94 @@
+/*
+ * Copyright (C) 2015 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.
+ */
+
+#include "reference_type_propagation.h"
+
+namespace art {
+
+// TODO: Only do the analysis on reference types. We currently have to handle
+// the `null` constant, that is represented as a `HIntConstant` and therefore
+// has the Primitive::kPrimInt type.
+
+void ReferenceTypePropagation::Run() {
+ // Compute null status for instructions.
+
+ // To properly propagate not-null info we need to visit in the dominator-based order.
+ // Reverse post order guarantees a node's dominators are visited first.
+ // We take advantage of this order in `VisitBasicBlock`.
+ for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+ VisitBasicBlock(it.Current());
+ }
+ ProcessWorklist();
+}
+
+// Re-computes and updates the nullability of the instruction. Returns whether or
+// not the nullability was changed.
+bool ReferenceTypePropagation::UpdateNullability(HPhi* phi) {
+ bool existing_can_be_null = phi->CanBeNull();
+ bool new_can_be_null = false;
+ for (size_t i = 0; i < phi->InputCount(); i++) {
+ new_can_be_null |= phi->InputAt(i)->CanBeNull();
+ }
+ phi->SetCanBeNull(new_can_be_null);
+
+ return existing_can_be_null != new_can_be_null;
+}
+
+
+void ReferenceTypePropagation::VisitBasicBlock(HBasicBlock* block) {
+ if (block->IsLoopHeader()) {
+ for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
+ // Set the initial type for the phi. Use the non back edge input for reaching
+ // a fixed point faster.
+ HPhi* phi = it.Current()->AsPhi();
+ AddToWorklist(phi);
+ phi->SetCanBeNull(phi->InputAt(0)->CanBeNull());
+ }
+ } else {
+ for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
+ // Eagerly compute the type of the phi, for quicker convergence. Note
+ // that we don't need to add users to the worklist because we are
+ // doing a reverse post-order visit, therefore either the phi users are
+ // non-loop phi and will be visited later in the visit, or are loop-phis,
+ // and they are already in the work list.
+ UpdateNullability(it.Current()->AsPhi());
+ }
+ }
+}
+
+void ReferenceTypePropagation::ProcessWorklist() {
+ while (!worklist_.IsEmpty()) {
+ HPhi* instruction = worklist_.Pop();
+ if (UpdateNullability(instruction)) {
+ AddDependentInstructionsToWorklist(instruction);
+ }
+ }
+}
+
+void ReferenceTypePropagation::AddToWorklist(HPhi* instruction) {
+ worklist_.Add(instruction);
+}
+
+void ReferenceTypePropagation::AddDependentInstructionsToWorklist(HPhi* instruction) {
+ for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
+ HPhi* phi = it.Current()->GetUser()->AsPhi();
+ if (phi != nullptr) {
+ AddToWorklist(phi);
+ }
+ }
+}
+
+} // namespace art
diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h
new file mode 100644
index 0000000000..a74319d0c5
--- /dev/null
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -0,0 +1,53 @@
+/*
+ * Copyright (C) 2015 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_REFERENCE_TYPE_PROPAGATION_H_
+#define ART_COMPILER_OPTIMIZING_REFERENCE_TYPE_PROPAGATION_H_
+
+#include "nodes.h"
+#include "optimization.h"
+
+namespace art {
+
+/**
+ * Propagates reference types to instructions.
+ * TODO: Currently only nullability is computed.
+ */
+class ReferenceTypePropagation : public HOptimization {
+ public:
+ explicit ReferenceTypePropagation(HGraph* graph)
+ : HOptimization(graph, true, "reference_type_propagation"),
+ worklist_(graph->GetArena(), kDefaultWorklistSize) {}
+
+ void Run() OVERRIDE;
+
+ private:
+ void VisitBasicBlock(HBasicBlock* block);
+ void ProcessWorklist();
+ void AddToWorklist(HPhi* phi);
+ void AddDependentInstructionsToWorklist(HPhi* phi);
+ bool UpdateNullability(HPhi* phi);
+
+ GrowableArray<HPhi*> worklist_;
+
+ static constexpr size_t kDefaultWorklistSize = 8;
+
+ DISALLOW_COPY_AND_ASSIGN(ReferenceTypePropagation);
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_REFERENCE_TYPE_PROPAGATION_H_
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 4f9c3b87c1..c9a21aa681 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -17,7 +17,7 @@
#include "ssa_builder.h"
#include "nodes.h"
-#include "ssa_type_propagation.h"
+#include "primitive_type_propagation.h"
#include "ssa_phi_elimination.h"
namespace art {
@@ -52,7 +52,7 @@ void SsaBuilder::BuildSsa() {
// 4) Propagate types of phis. At this point, phis are typed void in the general
// case, or float or double when we created a floating-point equivalent. So we
// need to propagate the types across phis to give them a correct type.
- SsaTypePropagation type_propagation(GetGraph());
+ PrimitiveTypePropagation type_propagation(GetGraph());
type_propagation.Run();
// 5) Clear locals.
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-13 18:59:45 +0000