Add a type propagation phase after building SSA.
This ensures all phis have a type.
Change-Id: I7e4f9a16d1efb5f64c493c1351749b352c870cbd
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 @@
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 @@
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 @@
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 @@
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<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/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<HPhi*> worklist_;
+
+ static constexpr size_t kDefaultWorklistSize = 8;
+
+ DISALLOW_COPY_AND_ASSIGN(SsaTypePropagation);
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_SSA_TYPE_PROPAGATION_H_