Fix a bug in the type analysis phase of optimizing.
Dex code can lead to the creation of a phi with one
float input and one integer input. Since the SSA builder trusts
the verifier, it assumes that the integer input must be converted
to float. However, when the register is not used afterwards, the
verifier hasn't ensured that. Therefore, the compiler must remove
the phi prior to doing type propagation.
Change-Id: Idcd51c4dccce827c59d1f2b253bc1c919bc07df5
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 69f031a..83d04b1 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -2896,7 +2896,7 @@
__ movss(Address(CpuRegister(RSP), destination.GetStackIndex()),
source.As<XmmRegister>());
} else {
- DCHECK(destination.IsDoubleStackSlot());
+ DCHECK(destination.IsDoubleStackSlot()) << destination;
__ movsd(Address(CpuRegister(RSP), destination.GetStackIndex()),
source.As<XmmRegister>());
}
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 1953241..5d712fe 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -342,4 +342,72 @@
}
}
+static Primitive::Type PrimitiveKind(Primitive::Type type) {
+ switch (type) {
+ case Primitive::kPrimBoolean:
+ case Primitive::kPrimByte:
+ case Primitive::kPrimShort:
+ case Primitive::kPrimChar:
+ case Primitive::kPrimInt:
+ return Primitive::kPrimInt;
+ default:
+ return type;
+ }
+}
+
+void SSAChecker::VisitCondition(HCondition* op) {
+ VisitInstruction(op);
+ // TODO: check inputs types, and special case the `null` check.
+ if (op->GetType() != Primitive::kPrimBoolean) {
+ std::stringstream error;
+ error << "Condition " << op->DebugName() << " " << op->GetId()
+ << " has a non-boolean result type: "
+ << op->GetType() << ".";
+ errors_.push_back(error.str());
+ }
+}
+
+void SSAChecker::VisitBinaryOperation(HBinaryOperation* op) {
+ VisitInstruction(op);
+ if (op->IsUShr() || op->IsShr() || op->IsShl()) {
+ if (PrimitiveKind(op->InputAt(1)->GetType()) != Primitive::kPrimInt) {
+ std::stringstream error;
+ error << "Shift operation " << op->DebugName() << " " << op->GetId()
+ << " has a non-int kind second input: "
+ << op->InputAt(1)->DebugName() << " of type " << op->InputAt(1)->GetType()
+ << ".";
+ errors_.push_back(error.str());
+ }
+ } else {
+ if (PrimitiveKind(op->InputAt(1)->GetType()) != PrimitiveKind(op->InputAt(0)->GetType())) {
+ std::stringstream error;
+ error << "Binary operation " << op->DebugName() << " " << op->GetId()
+ << " has inputs of different type: "
+ << op->InputAt(0)->GetType() << ", and " << op->InputAt(1)->GetType()
+ << ".";
+ errors_.push_back(error.str());
+ }
+ }
+
+ if (op->IsCompare()) {
+ if (op->GetType() != Primitive::kPrimInt) {
+ std::stringstream error;
+ error << "Compare operation " << op->GetId()
+ << " has a non-int result type: "
+ << op->GetType() << ".";
+ errors_.push_back(error.str());
+ }
+ } else {
+ // Use the first input, so that we can also make this check for shift operations.
+ if (PrimitiveKind(op->GetType()) != PrimitiveKind(op->InputAt(0)->GetType())) {
+ std::stringstream error;
+ error << "Binary operation " << op->DebugName() << " " << op->GetId()
+ << " has a result type different than its input type: "
+ << op->GetType() << ", and " << op->InputAt(1)->GetType()
+ << ".";
+ errors_.push_back(error.str());
+ }
+ }
+}
+
} // namespace art
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index 8ba8cb1..b6c9f17 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -24,11 +24,11 @@
namespace art {
// A control-flow graph visitor performing various checks.
-class GraphChecker : public HGraphVisitor {
+class GraphChecker : public HGraphDelegateVisitor {
public:
GraphChecker(ArenaAllocator* allocator, HGraph* graph,
const char* dump_prefix = "art::GraphChecker: ")
- : HGraphVisitor(graph),
+ : HGraphDelegateVisitor(graph),
allocator_(allocator),
dump_prefix_(dump_prefix) {}
@@ -36,10 +36,10 @@
virtual void Run() { VisitInsertionOrder(); }
// Check `block`.
- virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
+ void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
// Check `instruction`.
- virtual void VisitInstruction(HInstruction* instruction) OVERRIDE;
+ void VisitInstruction(HInstruction* instruction) OVERRIDE;
// Was the last visit of the graph valid?
bool IsValid() const {
@@ -82,7 +82,7 @@
: GraphChecker(allocator, graph, "art::SSAChecker: ") {}
// Check the whole graph (in reverse post-order).
- virtual void Run() {
+ void Run() OVERRIDE {
// VisitReversePostOrder is used instead of VisitInsertionOrder,
// as the latter might visit dead blocks removed by the dominator
// computation.
@@ -90,13 +90,15 @@
}
// Perform SSA form checks on `block`.
- virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
+ void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
// Loop-related checks from block `loop_header`.
void CheckLoop(HBasicBlock* loop_header);
// Perform SSA form checks on instructions.
- virtual void VisitInstruction(HInstruction* instruction) OVERRIDE;
- virtual void VisitPhi(HPhi* phi) OVERRIDE;
+ void VisitInstruction(HInstruction* instruction) OVERRIDE;
+ void VisitPhi(HPhi* phi) OVERRIDE;
+ void VisitBinaryOperation(HBinaryOperation* op) OVERRIDE;
+ void VisitCondition(HCondition* op) OVERRIDE;
private:
DISALLOW_COPY_AND_ASSIGN(SSAChecker);
diff --git a/compiler/optimizing/gvn.h b/compiler/optimizing/gvn.h
index a841d5f..8e739cb 100644
--- a/compiler/optimizing/gvn.h
+++ b/compiler/optimizing/gvn.h
@@ -166,10 +166,10 @@
/**
* Optimization phase that removes redundant instruction.
*/
-class GlobalValueNumberer : public HOptimization {
+class GlobalValueNumberer : public ValueObject {
public:
GlobalValueNumberer(ArenaAllocator* allocator, HGraph* graph)
- : HOptimization(graph, true, "GVN"),
+ : graph_(graph),
allocator_(allocator),
block_effects_(allocator, graph->GetBlocks().Size()),
loop_effects_(allocator, graph->GetBlocks().Size()),
@@ -187,7 +187,7 @@
}
}
- void Run() OVERRIDE;
+ void Run();
private:
// Per-block GVN. Will also update the ValueSet of the dominated and
@@ -202,6 +202,8 @@
SideEffects GetLoopEffects(HBasicBlock* block) const;
SideEffects GetBlockEffects(HBasicBlock* block) const;
+ HGraph* graph_;
+
ArenaAllocator* const allocator_;
// Side effects of individual blocks, that is the union of the side effects
@@ -224,6 +226,19 @@
DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer);
};
+class GVNOptimization : public HOptimization {
+ public:
+ explicit GVNOptimization(HGraph* graph) : HOptimization(graph, true, "GVN") {}
+
+ void Run() OVERRIDE {
+ GlobalValueNumberer gvn(graph_->GetArena(), graph_);
+ gvn.Run();
+ }
+
+ private:
+ DISALLOW_COPY_AND_ASSIGN(GVNOptimization);
+};
+
} // namespace art
#endif // ART_COMPILER_OPTIMIZING_GVN_H_
diff --git a/compiler/optimizing/optimization.cc b/compiler/optimizing/optimization.cc
index d1178d5..b99f678 100644
--- a/compiler/optimizing/optimization.cc
+++ b/compiler/optimizing/optimization.cc
@@ -27,13 +27,15 @@
SSAChecker checker(graph_->GetArena(), graph_);
checker.Run();
if (!checker.IsValid()) {
- LOG(FATAL) << Dumpable<SSAChecker>(checker);
+ LOG(FATAL) << "Error after " << GetPassName() << ": "
+ << Dumpable<SSAChecker>(checker);
}
} else {
GraphChecker checker(graph_->GetArena(), graph_);
checker.Run();
if (!checker.IsValid()) {
- LOG(FATAL) << Dumpable<GraphChecker>(checker);
+ LOG(FATAL) << "Error after " << GetPassName() << ": "
+ << Dumpable<GraphChecker>(checker);
}
}
}
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 42ac77d..d8533eb 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -35,6 +35,7 @@
#include "nodes.h"
#include "prepare_for_register_allocation.h"
#include "register_allocator.h"
+#include "ssa_builder.h"
#include "ssa_phi_elimination.h"
#include "ssa_liveness_analysis.h"
#include "utils/arena_allocator.h"
@@ -191,21 +192,31 @@
}
static void RunOptimizations(HGraph* graph, const HGraphVisualizer& visualizer) {
+ TransformToSsa ssa(graph);
HDeadCodeElimination opt1(graph);
HConstantFolding opt2(graph);
SsaRedundantPhiElimination opt3(graph);
SsaDeadPhiElimination opt4(graph);
InstructionSimplifier opt5(graph);
- GlobalValueNumberer opt6(graph->GetArena(), graph);
+ GVNOptimization opt6(graph);
InstructionSimplifier opt7(graph);
- HOptimization* optimizations[] = { &opt1, &opt2, &opt3, &opt4, &opt5, &opt6, &opt7 };
+ HOptimization* optimizations[] = {
+ &ssa,
+ &opt1,
+ &opt2,
+ &opt3,
+ &opt4,
+ &opt5,
+ &opt6,
+ &opt7
+ };
for (size_t i = 0; i < arraysize(optimizations); ++i) {
HOptimization* optimization = optimizations[i];
optimization->Run();
- optimization->Check();
visualizer.DumpGraph(optimization->GetPassName());
+ optimization->Check();
}
}
@@ -271,11 +282,6 @@
&& CanOptimize(*code_item)
&& RegisterAllocator::CanAllocateRegistersFor(*graph, instruction_set)) {
optimized_compiled_methods_++;
- graph->BuildDominatorTree();
- graph->TransformToSSA();
- visualizer.DumpGraph("ssa");
- graph->FindNaturalLoops();
-
RunOptimizations(graph, visualizer);
PrepareForRegisterAllocation(graph).Run();
@@ -321,7 +327,7 @@
graph->FindNaturalLoops();
SsaRedundantPhiElimination(graph).Run();
SsaDeadPhiElimination(graph).Run();
- GlobalValueNumberer(graph->GetArena(), graph).Run();
+ GVNOptimization(graph).Run();
SsaLivenessAnalysis liveness(*graph, codegen);
liveness.Analyze();
visualizer.DumpGraph(kLivenessPassName);
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index b2cc119..edfafcd 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -18,6 +18,7 @@
#include "nodes.h"
#include "ssa_type_propagation.h"
+#include "ssa_phi_elimination.h"
namespace art {
@@ -41,11 +42,20 @@
}
}
- // 3) Propagate types of phis.
+ // 3) Remove dead phis. This will remove phis that are only used by environments:
+ // at the DEX level, the type of these phis does not need to be consistent, but
+ // our code generator will complain if the inputs of a phi do not have the same
+ // type (modulo the special case of `null`).
+ SsaDeadPhiElimination dead_phis(GetGraph());
+ dead_phis.Run();
+
+ // 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());
type_propagation.Run();
- // 4) Clear locals.
+ // 5) Clear locals.
// TODO: Move this to a dead code eliminator phase.
for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions());
!it.Done();
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index 2207cd6..5ab328f 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -18,9 +18,24 @@
#define ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_
#include "nodes.h"
+#include "optimization.h"
namespace art {
+class TransformToSsa : public HOptimization {
+ public:
+ explicit TransformToSsa(HGraph* graph) : HOptimization(graph, true, "ssa transform") {}
+
+ void Run() OVERRIDE {
+ graph_->BuildDominatorTree();
+ graph_->TransformToSSA();
+ graph_->FindNaturalLoops();
+ }
+
+ private:
+ DISALLOW_COPY_AND_ASSIGN(TransformToSsa);
+};
+
static constexpr int kDefaultNumberOfLoops = 2;
class SsaBuilder : public HGraphVisitor {
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 56979e1..58cea77 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -24,6 +24,8 @@
HBasicBlock* block = it.Current();
for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
HPhi* phi = inst_it.Current()->AsPhi();
+ // Set dead ahead of running through uses. The phi may have no use.
+ phi->SetDead();
for (HUseIterator<HInstruction> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) {
HUseListNode<HInstruction>* current = use_it.Current();
HInstruction* user = current->GetUser();
@@ -31,8 +33,6 @@
worklist_.Add(phi);
phi->SetLive();
break;
- } else {
- phi->SetDead();
}
}
}
@@ -65,8 +65,8 @@
use_it.Advance()) {
HUseListNode<HInstruction>* user_node = use_it.Current();
HInstruction* user = user_node->GetUser();
- DCHECK(user->IsLoopHeaderPhi());
- DCHECK(user->AsPhi()->IsDead());
+ DCHECK(user->IsLoopHeaderPhi()) << user->GetId();
+ DCHECK(user->AsPhi()->IsDead()) << user->GetId();
// Just put itself as an input. The phi will be removed in this loop anyway.
user->SetRawInputAt(user_node->GetIndex(), user);
current->RemoveUser(user, user_node->GetIndex());
diff --git a/test/431-type-propagation/expected.txt b/test/431-type-propagation/expected.txt
new file mode 100644
index 0000000..ccaf6f8
--- /dev/null
+++ b/test/431-type-propagation/expected.txt
@@ -0,0 +1 @@
+Enter
diff --git a/test/431-type-propagation/info.txt b/test/431-type-propagation/info.txt
new file mode 100644
index 0000000..b895e91
--- /dev/null
+++ b/test/431-type-propagation/info.txt
@@ -0,0 +1,2 @@
+Regression test for the SSA building of the optimizing
+compiler. See comment in smali file.
diff --git a/test/431-type-propagation/smali/TypePropagation.smali b/test/431-type-propagation/smali/TypePropagation.smali
new file mode 100644
index 0000000..817f0c5
--- /dev/null
+++ b/test/431-type-propagation/smali/TypePropagation.smali
@@ -0,0 +1,43 @@
+# 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.
+
+.class public LTypePropagation;
+
+.super Ljava/lang/Object;
+
+.method public static method([I)V
+ .registers 3
+ const/4 v0, 0
+ aget v1, v2, v0
+ add-int v2, v1, v0
+ if-eq v1, v0, :end
+ # Putting a float in v1 will lead to the creation of a phi with one
+ # float input and one integer input. Since the SSA builder trusts
+ # the verifier, it assumes that the integer input must be converted
+ # to float. However, since v0 is not used afterwards, the verifier
+ # hasn't ensured that. Therefore, the compiler must remove
+ # the phi prior to doing type propagation.
+ int-to-float v1, v0
+ :end
+ # Do a call to create an environment that will capture all Dex registers.
+ # This environment is the reason why a phi is created at the join block
+ # of the if.
+ invoke-static {}, LTypePropagation;->emptyMethod()V
+ return-void
+.end method
+
+.method public static emptyMethod()V
+ .registers 0
+ return-void
+.end method
diff --git a/test/431-type-propagation/src/Main.java b/test/431-type-propagation/src/Main.java
new file mode 100644
index 0000000..91dfe10
--- /dev/null
+++ b/test/431-type-propagation/src/Main.java
@@ -0,0 +1,28 @@
+/*
+ * 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.
+ */
+
+import java.lang.reflect.Method;
+
+public class Main {
+ public static void main(String[] args) throws Exception {
+ System.out.println("Enter");
+ Class<?> c = Class.forName("TypePropagation");
+ Method m = c.getMethod("method", int[].class);
+ int[] array = new int[7];
+ Object[] arguments = { array };
+ m.invoke(null, arguments);
+ }
+}
