From 184d640d2a3ac86d871dab58386a50cc9bb973f9 Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Mon, 9 Jun 2014 14:06:02 +0100 Subject: Add a type propagation phase after building SSA. This ensures all phis have a type. Change-Id: I7e4f9a16d1efb5f64c493c1351749b352c870cbd --- compiler/Android.mk | 1 + compiler/optimizing/ssa_builder.cc | 30 +++------ compiler/optimizing/ssa_test.cc | 7 +++ compiler/optimizing/ssa_type_propagation.cc | 97 +++++++++++++++++++++++++++++ compiler/optimizing/ssa_type_propagation.h | 48 ++++++++++++++ 5 files changed, 160 insertions(+), 23 deletions(-) create mode 100644 compiler/optimizing/ssa_type_propagation.cc create mode 100644 compiler/optimizing/ssa_type_propagation.h diff --git a/compiler/Android.mk b/compiler/Android.mk index cfce9f7..3cf7368 100644 --- a/compiler/Android.mk +++ b/compiler/Android.mk @@ -91,6 +91,7 @@ LIBART_COMPILER_SRC_FILES := \ optimizing/register_allocator.cc \ optimizing/ssa_builder.cc \ optimizing/ssa_liveness_analysis.cc \ + optimizing/ssa_type_propagation.cc \ trampolines/trampoline_compiler.cc \ utils/arena_allocator.cc \ utils/arena_bit_vector.cc \ diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc index 54c3c5d..471307e 100644 --- a/compiler/optimizing/ssa_builder.cc +++ b/compiler/optimizing/ssa_builder.cc @@ -15,22 +15,12 @@ */ #include "ssa_builder.h" + #include "nodes.h" +#include "ssa_type_propagation.h" namespace art { -static Primitive::Type MergeTypes(Primitive::Type existing, Primitive::Type new_type) { - // We trust the verifier has already done the necessary checking. - switch (existing) { - case Primitive::kPrimFloat: - case Primitive::kPrimDouble: - case Primitive::kPrimNot: - return existing; - default: - return new_type; - } -} - 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 @@ -44,18 +34,18 @@ void SsaBuilder::BuildSsa() { HBasicBlock* block = loop_headers_.Get(i); for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { HPhi* phi = it.Current()->AsPhi(); - Primitive::Type type = Primitive::kPrimVoid; for (size_t pred = 0; pred < block->GetPredecessors().Size(); pred++) { HInstruction* input = ValueOfLocal(block->GetPredecessors().Get(pred), phi->GetRegNumber()); phi->AddInput(input); - type = MergeTypes(type, input->GetType()); } - phi->SetType(type); } } - // TODO: Now that the type of loop phis is set, we need a type propagation phase. - // 3) Clear locals. + // 3) Propagate types of phis. + SsaTypePropagation type_propagation(GetGraph()); + type_propagation.Run(); + + // 4) Clear locals. // TODO: Move this to a dead code eliminator phase. for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions()); !it.Done(); @@ -118,16 +108,10 @@ void SsaBuilder::VisitBasicBlock(HBasicBlock* block) { if (is_different) { HPhi* phi = new (GetGraph()->GetArena()) HPhi( GetGraph()->GetArena(), local, block->GetPredecessors().Size(), Primitive::kPrimVoid); - Primitive::Type type = Primitive::kPrimVoid; for (size_t i = 0; i < block->GetPredecessors().Size(); i++) { HInstruction* value = ValueOfLocal(block->GetPredecessors().Get(i), local); - // We need to merge the incoming types, as the Dex format does not - // guarantee the inputs have the same type. In particular the 0 constant is - // used for all types, but the graph builder treats it as an int. - type = MergeTypes(type, value->GetType()); phi->SetRawInputAt(i, value); } - phi->SetType(type); block->AddPhi(phi); value = phi; } diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc index 3b354f1..088a5c4 100644 --- a/compiler/optimizing/ssa_test.cc +++ b/compiler/optimizing/ssa_test.cc @@ -87,6 +87,13 @@ static void TestCode(const uint16_t* data, const char* expected) { graph->TransformToSSA(); ReNumberInstructions(graph); + // Test that phis had their type set. + for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) { + for (HInstructionIterator it(graph->GetBlocks().Get(i)->GetPhis()); !it.Done(); it.Advance()) { + ASSERT_NE(it.Current()->GetType(), Primitive::kPrimVoid); + } + } + SsaPrettyPrinter printer(graph); printer.VisitInsertionOrder(); diff --git a/compiler/optimizing/ssa_type_propagation.cc b/compiler/optimizing/ssa_type_propagation.cc new file mode 100644 index 0000000..53fa74e --- /dev/null +++ b/compiler/optimizing/ssa_type_propagation.cc @@ -0,0 +1,97 @@ +/* + * 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. + */ + +#include "ssa_type_propagation.h" + +#include "nodes.h" + +namespace art { + +static Primitive::Type MergeTypes(Primitive::Type existing, Primitive::Type new_type) { + // We trust the verifier has already done the necessary checking. + switch (existing) { + case Primitive::kPrimFloat: + case Primitive::kPrimDouble: + case Primitive::kPrimNot: + return existing; + default: + return new_type; + } +} + +// Re-compute and update the type of the instruction. Returns +// whether or not the type was changed. +static bool UpdateType(HPhi* phi) { + Primitive::Type existing = phi->GetType(); + + Primitive::Type new_type = Primitive::kPrimVoid; + for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { + Primitive::Type input_type = phi->InputAt(i)->GetType(); + new_type = MergeTypes(new_type, input_type); + } + phi->SetType(new_type); + return existing != new_type; +} + +void SsaTypePropagation::Run() { + for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { + VisitBasicBlock(it.Current()); + } + ProcessWorklist(); +} + +void SsaTypePropagation::VisitBasicBlock(HBasicBlock* block) { + if (block->IsLoopHeader()) { + for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { + HPhi* phi = it.Current()->AsPhi(); + // Set the initial type for the phi. Use the non back edge input for reaching + // a fixed point faster. + phi->SetType(phi->InputAt(0)->GetType()); + AddToWorklist(phi); + } + } else { + for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { + HPhi* phi = it.Current()->AsPhi(); + if (UpdateType(phi)) { + AddDependentInstructionsToWorklist(phi); + } + } + } +} + +void SsaTypePropagation::ProcessWorklist() { + while (!worklist_.IsEmpty()) { + HPhi* instruction = worklist_.Pop(); + if (UpdateType(instruction)) { + AddDependentInstructionsToWorklist(instruction); + } + } +} + +void SsaTypePropagation::AddToWorklist(HPhi* instruction) { + worklist_.Add(instruction); +} + +void SsaTypePropagation::AddDependentInstructionsToWorklist(HPhi* instruction) { + for (HUseIterator 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/ssa_type_propagation.h b/compiler/optimizing/ssa_type_propagation.h new file mode 100644 index 0000000..5f471a9 --- /dev/null +++ b/compiler/optimizing/ssa_type_propagation.h @@ -0,0 +1,48 @@ +/* + * 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_SSA_TYPE_PROPAGATION_H_ +#define ART_COMPILER_OPTIMIZING_SSA_TYPE_PROPAGATION_H_ + +#include "nodes.h" + +namespace art { + +// Compute and propagate types of phis in the graph. +class SsaTypePropagation : public ValueObject { + public: + explicit SsaTypePropagation(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); + + HGraph* const graph_; + GrowableArray worklist_; + + static constexpr size_t kDefaultWorklistSize = 8; + + DISALLOW_COPY_AND_ASSIGN(SsaTypePropagation); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_SSA_TYPE_PROPAGATION_H_ -- cgit v1.1