optimizing: NullCheck elimination
How it works:
- run a type analysis to propagate null information on instructions
- during the last instruction simplifier remove null checks for which
the input is known to be not null
The current type analysis is actually a nullability analysis but it will
be reused in follow up CLs to propagate type information: so it keeps
the more convenient name.
Change-Id: I54bb1d32ab24604b4d677d1ecdaf8d60a5ff5ce9
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
new file mode 100644
index 0000000..24e6837
--- /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