summaryrefslogtreecommitdiff
path: root/compiler/optimizing
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/optimizing')
-rw-r--r--compiler/optimizing/graph_checker.cc6
-rw-r--r--compiler/optimizing/inliner.cc8
-rw-r--r--compiler/optimizing/nodes.h23
-rw-r--r--compiler/optimizing/optimizing_compiler.cc7
-rw-r--r--compiler/optimizing/primitive_type_propagation.cc2
-rw-r--r--compiler/optimizing/ssa_builder.cc227
-rw-r--r--compiler/optimizing/ssa_builder.h20
7 files changed, 262 insertions, 31 deletions
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index a7f1f74e27..76b9f4fe7e 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -362,6 +362,12 @@ void SSAChecker::VisitPhi(HPhi* phi) {
Primitive::PrettyDescriptor(phi->GetType())));
}
}
+ if (phi->GetType() != HPhi::ToPhiType(phi->GetType())) {
+ AddError(StringPrintf("Phi %d in block %d does not have an expected phi type: %s",
+ phi->GetId(),
+ phi->GetBlock()->GetBlockId(),
+ Primitive::PrettyDescriptor(phi->GetType())));
+ }
}
void SSAChecker::VisitIf(HIf* instruction) {
diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index b34957a17e..e22f7ccbf1 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -124,8 +124,8 @@ bool HInliner::TryInline(HInvoke* invoke_instruction,
resolved_method->GetAccessFlags(),
nullptr);
- HGraph* callee_graph =
- new (graph_->GetArena()) HGraph(graph_->GetArena(), graph_->GetCurrentInstructionId());
+ HGraph* callee_graph = new (graph_->GetArena()) HGraph(
+ graph_->GetArena(), graph_->IsDebuggable(), graph_->GetCurrentInstructionId());
OptimizingCompilerStats inline_stats;
HGraphBuilder builder(callee_graph,
@@ -155,15 +155,11 @@ bool HInliner::TryInline(HInvoke* invoke_instruction,
}
// Run simple optimizations on the graph.
- SsaRedundantPhiElimination redundant_phi(callee_graph);
- SsaDeadPhiElimination dead_phi(callee_graph);
HDeadCodeElimination dce(callee_graph);
HConstantFolding fold(callee_graph);
InstructionSimplifier simplify(callee_graph, stats_);
HOptimization* optimizations[] = {
- &redundant_phi,
- &dead_phi,
&dce,
&fold,
&simplify,
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 8b56166610..942aa2374b 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -103,7 +103,7 @@ class HInstructionList {
// Control-flow graph of a method. Contains a list of basic blocks.
class HGraph : public ArenaObject<kArenaAllocMisc> {
public:
- HGraph(ArenaAllocator* arena, int start_instruction_id = 0)
+ HGraph(ArenaAllocator* arena, bool debuggable = false, int start_instruction_id = 0)
: arena_(arena),
blocks_(arena, kDefaultNumberOfBlocks),
reverse_post_order_(arena, kDefaultNumberOfBlocks),
@@ -114,6 +114,7 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
number_of_in_vregs_(0),
temporaries_vreg_slots_(0),
has_array_accesses_(false),
+ debuggable_(debuggable),
current_instruction_id_(start_instruction_id) {}
ArenaAllocator* GetArena() const { return arena_; }
@@ -208,6 +209,8 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
has_array_accesses_ = value;
}
+ bool IsDebuggable() const { return debuggable_; }
+
HNullConstant* GetNullConstant();
private:
@@ -248,6 +251,11 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
// Has array accesses. We can totally skip BCE if it's false.
bool has_array_accesses_;
+ // 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_;
@@ -2498,6 +2506,19 @@ class HPhi : public HInstruction {
inputs_.SetSize(number_of_inputs);
}
+ // Returns a type equivalent to the given `type`, but that a `HPhi` can hold.
+ static Primitive::Type ToPhiType(Primitive::Type type) {
+ switch (type) {
+ case Primitive::kPrimBoolean:
+ case Primitive::kPrimByte:
+ case Primitive::kPrimShort:
+ case Primitive::kPrimChar:
+ return Primitive::kPrimInt;
+ default:
+ return type;
+ }
+ }
+
size_t InputCount() const OVERRIDE { return inputs_.Size(); }
void AddInput(HInstruction* input);
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index eb984248a9..3470595b2c 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -298,8 +298,6 @@ static void RunOptimizations(HGraph* graph,
const DexCompilationUnit& dex_compilation_unit,
PassInfoPrinter* pass_info_printer,
StackHandleScopeCollection* handles) {
- SsaRedundantPhiElimination redundant_phi(graph);
- SsaDeadPhiElimination dead_phi(graph);
HDeadCodeElimination dce(graph);
HConstantFolding fold1(graph);
InstructionSimplifier simplify1(graph, stats);
@@ -317,8 +315,6 @@ static void RunOptimizations(HGraph* graph,
IntrinsicsRecognizer intrinsics(graph, dex_compilation_unit.GetDexFile(), driver);
HOptimization* optimizations[] = {
- &redundant_phi,
- &dead_phi,
&intrinsics,
&dce,
&fold1,
@@ -461,7 +457,8 @@ CompiledMethod* OptimizingCompiler::Compile(const DexFile::CodeItem* code_item,
ArenaPool pool;
ArenaAllocator arena(&pool);
- HGraph* graph = new (&arena) HGraph(&arena);
+ HGraph* graph = new (&arena) HGraph(
+ &arena, compiler_driver->GetCompilerOptions().GetDebuggable());
// For testing purposes, we put a special marker on method names that should be compiled
// with this compiler. This makes sure we're not regressing.
diff --git a/compiler/optimizing/primitive_type_propagation.cc b/compiler/optimizing/primitive_type_propagation.cc
index fe23fcf326..c20c8a172d 100644
--- a/compiler/optimizing/primitive_type_propagation.cc
+++ b/compiler/optimizing/primitive_type_propagation.cc
@@ -33,7 +33,7 @@ static Primitive::Type MergeTypes(Primitive::Type existing, Primitive::Type new_
// to merge with a void type, we should use the existing one.
return new_type == Primitive::kPrimVoid
? existing
- : new_type;
+ : HPhi::ToPhiType(new_type);
}
}
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 3dc75059b2..1a8e784363 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -22,6 +22,158 @@
namespace art {
+/**
+ * A debuggable application may require to reviving phis, to ensure their
+ * associated DEX register is available to a debugger. This class implements
+ * the logic for statement (c) of the SsaBuilder (see ssa_builder.h). It
+ * also makes sure that phis with incompatible input types are not revived
+ * (statement (b) of the SsaBuilder).
+ *
+ * This phase must be run after detecting dead phis through the
+ * DeadPhiElimination phase, and before deleting the dead phis.
+ */
+class DeadPhiHandling : public ValueObject {
+ public:
+ explicit DeadPhiHandling(HGraph* graph)
+ : graph_(graph), worklist_(graph->GetArena(), kDefaultWorklistSize) {}
+
+ void Run();
+
+ private:
+ void VisitBasicBlock(HBasicBlock* block);
+ void ProcessWorklist();
+ void AddToWorklist(HPhi* phi);
+ void AddDependentInstructionsToWorklist(HPhi* phi);
+ bool UpdateType(HPhi* phi);
+
+ HGraph* const graph_;
+ GrowableArray<HPhi*> worklist_;
+
+ static constexpr size_t kDefaultWorklistSize = 8;
+
+ DISALLOW_COPY_AND_ASSIGN(DeadPhiHandling);
+};
+
+bool DeadPhiHandling::UpdateType(HPhi* phi) {
+ Primitive::Type existing = phi->GetType();
+ DCHECK(phi->IsLive());
+
+ bool conflict = false;
+ Primitive::Type new_type = existing;
+ for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
+ HInstruction* input = phi->InputAt(i);
+ if (input->IsPhi() && input->AsPhi()->IsDead()) {
+ // We are doing a reverse post order visit of the graph, reviving
+ // phis that have environment uses and updating their types. If an
+ // input is a phi, and it is dead (because its input types are
+ // conflicting), this phi must be marked dead as well.
+ conflict = true;
+ break;
+ }
+ Primitive::Type input_type = HPhi::ToPhiType(input->GetType());
+
+ // The only acceptable transitions are:
+ // - From void to typed: first time we update the type of this phi.
+ // - From int to reference (or reference to int): the phi has to change
+ // to reference type. If the integer input cannot be converted to a
+ // reference input, the phi will remain dead.
+ if (new_type == Primitive::kPrimVoid) {
+ new_type = input_type;
+ } else if (new_type == Primitive::kPrimNot && input_type == Primitive::kPrimInt) {
+ HInstruction* equivalent = SsaBuilder::GetReferenceTypeEquivalent(input);
+ if (equivalent == nullptr) {
+ conflict = true;
+ break;
+ } else {
+ phi->ReplaceInput(equivalent, i);
+ if (equivalent->IsPhi()) {
+ DCHECK_EQ(equivalent->GetType(), Primitive::kPrimNot);
+ // We created a new phi, but that phi has the same inputs as the old phi. We
+ // add it to the worklist to ensure its inputs can also be converted to reference.
+ // If not, it will remain dead, and the algorithm will make the current phi dead
+ // as well.
+ equivalent->AsPhi()->SetLive();
+ AddToWorklist(equivalent->AsPhi());
+ }
+ }
+ } else if (new_type == Primitive::kPrimInt && input_type == Primitive::kPrimNot) {
+ new_type = Primitive::kPrimNot;
+ // Start over, we may request reference equivalents for the inputs of the phi.
+ i = -1;
+ } else if (new_type != input_type) {
+ conflict = true;
+ break;
+ }
+ }
+
+ if (conflict) {
+ phi->SetType(Primitive::kPrimVoid);
+ phi->SetDead();
+ return true;
+ } else {
+ DCHECK(phi->IsLive());
+ phi->SetType(new_type);
+ return existing != new_type;
+ }
+}
+
+void DeadPhiHandling::VisitBasicBlock(HBasicBlock* block) {
+ for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
+ HPhi* phi = it.Current()->AsPhi();
+ if (phi->IsDead() && phi->HasEnvironmentUses()) {
+ phi->SetLive();
+ if (block->IsLoopHeader()) {
+ // Give a type to the loop phi, to guarantee convergence of the algorithm.
+ phi->SetType(phi->InputAt(0)->GetType());
+ AddToWorklist(phi);
+ } else {
+ // Because we are doing a reverse post order visit, all inputs of
+ // this phi have been visited and therefore had their (initial) type set.
+ UpdateType(phi);
+ }
+ }
+ }
+}
+
+void DeadPhiHandling::ProcessWorklist() {
+ while (!worklist_.IsEmpty()) {
+ HPhi* instruction = worklist_.Pop();
+ // Note that the same equivalent phi can be added multiple times in the work list, if
+ // used by multiple phis. The first call to `UpdateType` will know whether the phi is
+ // dead or live.
+ if (instruction->IsLive() && UpdateType(instruction)) {
+ AddDependentInstructionsToWorklist(instruction);
+ }
+ }
+}
+
+void DeadPhiHandling::AddToWorklist(HPhi* instruction) {
+ DCHECK(instruction->IsLive());
+ worklist_.Add(instruction);
+}
+
+void DeadPhiHandling::AddDependentInstructionsToWorklist(HPhi* instruction) {
+ for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
+ HPhi* phi = it.Current()->GetUser()->AsPhi();
+ if (phi != nullptr && !phi->IsDead()) {
+ AddToWorklist(phi);
+ }
+ }
+}
+
+void DeadPhiHandling::Run() {
+ for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+ VisitBasicBlock(it.Current());
+ }
+ ProcessWorklist();
+}
+
+static bool IsPhiEquivalentOf(HInstruction* instruction, HPhi* phi) {
+ return instruction != nullptr
+ && instruction->IsPhi()
+ && instruction->AsPhi()->GetRegNumber() == phi->GetRegNumber();
+}
+
void SsaBuilder::BuildSsa() {
// 1) Visit in reverse post order. We need to have all predecessors of a block visited
// (with the exception of loops) in order to create the right environment for that
@@ -47,11 +199,9 @@ void SsaBuilder::BuildSsa() {
// our code generator will complain if the inputs of a phi do not have the same
// type. The marking allows the type propagation to know which phis it needs
// to handle. We mark but do not eliminate: the elimination will be done in
- // step 5).
- {
- SsaDeadPhiElimination dead_phis(GetGraph());
- dead_phis.MarkDeadPhis();
- }
+ // step 8).
+ SsaDeadPhiElimination dead_phis(GetGraph());
+ dead_phis.MarkDeadPhis();
// 4) Propagate types of phis. At this point, phis are typed void in the general
// case, or float/double/reference when we created an equivalent phi. So we
@@ -59,17 +209,58 @@ void SsaBuilder::BuildSsa() {
PrimitiveTypePropagation type_propagation(GetGraph());
type_propagation.Run();
- // 5) Step 4) changes inputs of phis which may lead to dead phis again. We re-run
- // the algorithm and this time elimimates them.
- // TODO: Make this work with debug info and reference liveness. We currently
- // eagerly remove phis used in environments.
- {
- SsaDeadPhiElimination dead_phis(GetGraph());
- dead_phis.Run();
+ // 5) Now that the graph is correclty typed, we can get rid of redundant phis.
+ // Note that we cannot do this phase before type propagation, otherwise
+ // we could get rid of phi equivalents, whose presence is a requirement for the
+ // type propagation phase. Note that this is to satisfy statement (a) of the
+ // SsaBuilder (see ssa_builder.h).
+ SsaRedundantPhiElimination redundant_phi(GetGraph());
+ redundant_phi.Run();
+
+ // 6) Make sure environments use the right phi "equivalent": a phi marked dead
+ // can have a phi equivalent that is not dead. We must therefore update
+ // all environment uses of the dead phi to use its equivalent. Note that there
+ // can be multiple phis for the same Dex register that are live (for example
+ // when merging constants), in which case it is OK for the environments
+ // to just reference one.
+ for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
+ HBasicBlock* block = it.Current();
+ for (HInstructionIterator it_phis(block->GetPhis()); !it_phis.Done(); it_phis.Advance()) {
+ HPhi* phi = it_phis.Current()->AsPhi();
+ // If the phi is not dead, or has no environment uses, there is nothing to do.
+ if (!phi->IsDead() || !phi->HasEnvironmentUses()) continue;
+ HInstruction* next = phi->GetNext();
+ if (!IsPhiEquivalentOf(next, phi)) continue;
+ if (next->AsPhi()->IsDead()) {
+ // If the phi equivalent is dead, check if there is another one.
+ next = next->GetNext();
+ if (!IsPhiEquivalentOf(next, phi)) continue;
+ // There can be at most two phi equivalents.
+ DCHECK(!IsPhiEquivalentOf(next->GetNext(), phi));
+ if (next->AsPhi()->IsDead()) continue;
+ }
+ // We found a live phi equivalent. Update the environment uses of `phi` with it.
+ phi->ReplaceWith(next);
+ }
}
- // 6) Clear locals.
- // TODO: Move this to a dead code eliminator phase.
+ // 7) Deal with phis to guarantee liveness of phis in case of a debuggable
+ // application. This is for satisfying statement (c) of the SsaBuilder
+ // (see ssa_builder.h).
+ if (GetGraph()->IsDebuggable()) {
+ DeadPhiHandling dead_phi_handler(GetGraph());
+ dead_phi_handler.Run();
+ }
+
+ // 8) Now that the right phis are used for the environments, and we
+ // have potentially revive dead phis in case of a debuggable application,
+ // we can eliminate phis we do not need. Regardless of the debuggable status,
+ // this phase is necessary for statement (b) of the SsaBuilder (see ssa_builder.h),
+ // as well as for the code generation, which does not deal with phis of conflicting
+ // input types.
+ dead_phis.EliminateDeadPhis();
+
+ // 9) Clear locals.
for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions());
!it.Done();
it.Advance()) {
@@ -257,12 +448,12 @@ HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* user,
}
HInstruction* SsaBuilder::GetReferenceTypeEquivalent(HInstruction* value) {
- if (value->IsIntConstant()) {
- DCHECK_EQ(value->AsIntConstant()->GetValue(), 0);
+ if (value->IsIntConstant() && value->AsIntConstant()->GetValue() == 0) {
return value->GetBlock()->GetGraph()->GetNullConstant();
- } else {
- DCHECK(value->IsPhi());
+ } else if (value->IsPhi()) {
return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), Primitive::kPrimNot);
+ } else {
+ return nullptr;
}
}
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index f50da46040..b414fb2945 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -24,6 +24,26 @@ namespace art {
static constexpr int kDefaultNumberOfLoops = 2;
+/**
+ * Transforms a graph into SSA form. The liveness guarantees of
+ * this transformation are listed below. A DEX register
+ * being killed means its value at a given position in the code
+ * will not be available to its environment uses. A merge in the
+ * following text is materialized as a `HPhi`.
+ *
+ * (a) Dex registers that do not require merging (that is, they do not
+ * have different values at a join block) are available to all their
+ * environment uses.
+ *
+ * (b) Dex registers that require merging, and the merging gives
+ * incompatible types, will be killed for environment uses of that merge.
+ *
+ * (c) When the `debuggable` flag is passed to the compiler, Dex registers
+ * that require merging and have a proper type after the merge, are
+ * available to all their environment uses. If the `debuggable` flag
+ * is not set, values of Dex registers only used by environments
+ * are killed.
+ */
class SsaBuilder : public HGraphVisitor {
public:
explicit SsaBuilder(HGraph* graph)
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-21 12:51:16 +0000