diff --git a/compiler/Android.mk b/compiler/Android.mk
index 1d4f5a3..c92d7f5 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -110,7 +110,8 @@
 	optimizing/ssa_builder.cc \
 	optimizing/ssa_liveness_analysis.cc \
 	optimizing/ssa_phi_elimination.cc \
-	optimizing/ssa_type_propagation.cc \
+	optimizing/primitive_type_propagation.cc \
+	optimizing/reference_type_propagation.cc \
 	trampolines/trampoline_compiler.cc \
 	utils/arena_allocator.cc \
 	utils/arena_bit_vector.cc \
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index 9c2facb..21c5859 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -161,7 +161,7 @@
   if (!dex_compilation_unit_->IsStatic()) {
     // Add the implicit 'this' argument, not expressed in the signature.
     HParameterValue* parameter =
-        new (arena_) HParameterValue(parameter_index++, Primitive::kPrimNot);
+        new (arena_) HParameterValue(parameter_index++, Primitive::kPrimNot, true);
     entry_block_->AddInstruction(parameter);
     HLocal* local = GetLocalAt(locals_index++);
     entry_block_->AddInstruction(new (arena_) HStoreLocal(local, parameter));
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 63bc4ae..17c8f33 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -27,6 +27,7 @@
   void VisitEqual(HEqual* equal) OVERRIDE;
   void VisitArraySet(HArraySet* equal) OVERRIDE;
   void VisitTypeConversion(HTypeConversion* instruction) OVERRIDE;
+  void VisitNullCheck(HNullCheck* instruction) OVERRIDE;
 };
 
 void InstructionSimplifier::Run() {
@@ -34,6 +35,14 @@
   visitor.VisitInsertionOrder();
 }
 
+void InstructionSimplifierVisitor::VisitNullCheck(HNullCheck* null_check) {
+  HInstruction* obj = null_check->InputAt(0);
+  if (!obj->CanBeNull()) {
+    null_check->ReplaceWith(obj);
+    null_check->GetBlock()->RemoveInstruction(null_check);
+  }
+}
+
 void InstructionSimplifierVisitor::VisitSuspendCheck(HSuspendCheck* check) {
   HBasicBlock* block = check->GetBlock();
   // Currently always keep the suspend check at entry.
diff --git a/compiler/optimizing/instruction_simplifier.h b/compiler/optimizing/instruction_simplifier.h
index 7068c7f..bca6697 100644
--- a/compiler/optimizing/instruction_simplifier.h
+++ b/compiler/optimizing/instruction_simplifier.h
@@ -27,8 +27,8 @@
  */
 class InstructionSimplifier : public HOptimization {
  public:
-  explicit InstructionSimplifier(HGraph* graph)
-    : HOptimization(graph, true, "instruction_simplifier") {}
+  explicit InstructionSimplifier(HGraph* graph, const char* name = "instruction_simplifier")
+    : HOptimization(graph, true, name) {}
 
   void Run() OVERRIDE;
 };
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 2cc021c..bddcf37 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -847,6 +847,10 @@
   virtual bool CanThrow() const { return false; }
   bool HasSideEffects() const { return side_effects_.HasSideEffects(); }
 
+  // Does not apply for all instructions, but having this at top level greatly
+  // simplifies the null check elimination.
+  virtual bool CanBeNull() const { return true; }
+
   virtual bool CanDoImplicitNullCheck() const { return false; }
 
   void AddUseAt(HInstruction* user, size_t index) {
@@ -1802,6 +1806,8 @@
   // TODO: optimize when possible.
   bool CanThrow() const OVERRIDE { return true; }
 
+  bool CanBeNull() const OVERRIDE { return false; }
+
   DECLARE_INSTRUCTION(NewInstance);
 
  private:
@@ -1838,7 +1844,9 @@
   uint16_t GetTypeIndex() const { return type_index_; }
 
   // Calls runtime so needs an environment.
-  virtual bool NeedsEnvironment() const { return true; }
+  bool NeedsEnvironment() const OVERRIDE { return true; }
+
+  bool CanBeNull() const OVERRIDE { return false; }
 
   DECLARE_INSTRUCTION(NewArray);
 
@@ -2088,18 +2096,23 @@
 // the calling convention.
 class HParameterValue : public HExpression<0> {
  public:
-  HParameterValue(uint8_t index, Primitive::Type parameter_type)
-      : HExpression(parameter_type, SideEffects::None()), index_(index) {}
+  HParameterValue(uint8_t index, Primitive::Type parameter_type, bool is_this = false)
+      : HExpression(parameter_type, SideEffects::None()), index_(index), is_this_(is_this) {}
 
   uint8_t GetIndex() const { return index_; }
 
+  bool CanBeNull() const OVERRIDE { return !is_this_; }
+
   DECLARE_INSTRUCTION(ParameterValue);
 
  private:
   // The index of this parameter in the parameters list. Must be less
-  // than HGraph::number_of_in_vregs_;
+  // than HGraph::number_of_in_vregs_.
   const uint8_t index_;
 
+  // Whether or not the parameter value corresponds to 'this' argument.
+  const bool is_this_;
+
   DISALLOW_COPY_AND_ASSIGN(HParameterValue);
 };
 
@@ -2158,22 +2171,26 @@
         inputs_(arena, number_of_inputs),
         reg_number_(reg_number),
         type_(type),
-        is_live_(false) {
+        is_live_(false),
+        can_be_null_(true) {
     inputs_.SetSize(number_of_inputs);
   }
 
-  virtual size_t InputCount() const { return inputs_.Size(); }
-  virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); }
+  size_t InputCount() const OVERRIDE { return inputs_.Size(); }
+  HInstruction* InputAt(size_t i) const OVERRIDE { return inputs_.Get(i); }
 
-  virtual void SetRawInputAt(size_t index, HInstruction* input) {
+  void SetRawInputAt(size_t index, HInstruction* input) OVERRIDE {
     inputs_.Put(index, input);
   }
 
   void AddInput(HInstruction* input);
 
-  virtual Primitive::Type GetType() const { return type_; }
+  Primitive::Type GetType() const OVERRIDE { return type_; }
   void SetType(Primitive::Type type) { type_ = type; }
 
+  bool CanBeNull() const OVERRIDE { return can_be_null_; }
+  void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; }
+
   uint32_t GetRegNumber() const { return reg_number_; }
 
   void SetDead() { is_live_ = false; }
@@ -2188,6 +2205,7 @@
   const uint32_t reg_number_;
   Primitive::Type type_;
   bool is_live_;
+  bool can_be_null_;
 
   DISALLOW_COPY_AND_ASSIGN(HPhi);
 };
@@ -2199,15 +2217,17 @@
     SetRawInputAt(0, value);
   }
 
-  virtual bool CanBeMoved() const { return true; }
-  virtual bool InstructionDataEquals(HInstruction* other) const {
+  bool CanBeMoved() const OVERRIDE { return true; }
+  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
     UNUSED(other);
     return true;
   }
 
-  virtual bool NeedsEnvironment() const { return true; }
+  bool NeedsEnvironment() const OVERRIDE { return true; }
 
-  virtual bool CanThrow() const { return true; }
+  bool CanThrow() const OVERRIDE { return true; }
+
+  bool CanBeNull() const OVERRIDE { return false; }
 
   uint32_t GetDexPc() const { return dex_pc_; }
 
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 4f05afa..705345b 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -43,6 +43,7 @@
 #include "ssa_builder.h"
 #include "ssa_phi_elimination.h"
 #include "ssa_liveness_analysis.h"
+#include "reference_type_propagation.h"
 #include "utils/arena_allocator.h"
 
 namespace art {
@@ -196,6 +197,18 @@
   return code_item.tries_size_ == 0;
 }
 
+static void RunOptimizations(HOptimization* optimizations[],
+                             size_t length,
+                             const HGraphVisualizer& visualizer) {
+  for (size_t i = 0; i < length; ++i) {
+    HOptimization* optimization = optimizations[i];
+    visualizer.DumpGraph(optimization->GetPassName(), /*is_after=*/false);
+    optimization->Run();
+    visualizer.DumpGraph(optimization->GetPassName(), /*is_after=*/true);
+    optimization->Check();
+  }
+}
+
 static void RunOptimizations(HGraph* graph,
                              CompilerDriver* driver,
                              OptimizingCompilerStats* stats,
@@ -213,7 +226,8 @@
   SideEffectsAnalysis side_effects(graph);
   GVNOptimization gvn(graph, side_effects);
   BoundsCheckElimination bce(graph);
-  InstructionSimplifier simplify2(graph);
+  ReferenceTypePropagation type_propagation(graph);
+  InstructionSimplifier simplify2(graph, "instruction_simplifier_after_types");
 
   IntrinsicsRecognizer intrinsics(graph, dex_compilation_unit.GetDexFile(), driver);
 
@@ -229,16 +243,11 @@
     &side_effects,
     &gvn,
     &bce,
+    &type_propagation,
     &simplify2
   };
 
-  for (size_t i = 0; i < arraysize(optimizations); ++i) {
-    HOptimization* optimization = optimizations[i];
-    visualizer.DumpGraph(optimization->GetPassName(), /*is_after=*/false);
-    optimization->Run();
-    visualizer.DumpGraph(optimization->GetPassName(), /*is_after=*/true);
-    optimization->Check();
-  }
+  RunOptimizations(optimizations, arraysize(optimizations), visualizer);
 }
 
 // The stack map we generate must be 4-byte aligned on ARM. Since existing
diff --git a/compiler/optimizing/ssa_type_propagation.cc b/compiler/optimizing/primitive_type_propagation.cc
similarity index 90%
rename from compiler/optimizing/ssa_type_propagation.cc
rename to compiler/optimizing/primitive_type_propagation.cc
index 947427b..7e274f6 100644
--- a/compiler/optimizing/ssa_type_propagation.cc
+++ b/compiler/optimizing/primitive_type_propagation.cc
@@ -14,10 +14,10 @@
  * limitations under the License.
  */
 
-#include "ssa_builder.h"
-#include "ssa_type_propagation.h"
+#include "primitive_type_propagation.h"
 
 #include "nodes.h"
+#include "ssa_builder.h"
 
 namespace art {
 
@@ -39,7 +39,7 @@
 
 // Re-compute and update the type of the instruction. Returns
 // whether or not the type was changed.
-bool SsaTypePropagation::UpdateType(HPhi* phi) {
+bool PrimitiveTypePropagation::UpdateType(HPhi* phi) {
   Primitive::Type existing = phi->GetType();
 
   Primitive::Type new_type = existing;
@@ -67,14 +67,14 @@
   return existing != new_type;
 }
 
-void SsaTypePropagation::Run() {
+void PrimitiveTypePropagation::Run() {
   for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
     VisitBasicBlock(it.Current());
   }
   ProcessWorklist();
 }
 
-void SsaTypePropagation::VisitBasicBlock(HBasicBlock* block) {
+void PrimitiveTypePropagation::VisitBasicBlock(HBasicBlock* block) {
   if (block->IsLoopHeader()) {
     for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
       HPhi* phi = it.Current()->AsPhi();
@@ -100,7 +100,7 @@
   }
 }
 
-void SsaTypePropagation::ProcessWorklist() {
+void PrimitiveTypePropagation::ProcessWorklist() {
   while (!worklist_.IsEmpty()) {
     HPhi* instruction = worklist_.Pop();
     if (UpdateType(instruction)) {
@@ -109,11 +109,11 @@
   }
 }
 
-void SsaTypePropagation::AddToWorklist(HPhi* instruction) {
+void PrimitiveTypePropagation::AddToWorklist(HPhi* instruction) {
   worklist_.Add(instruction);
 }
 
-void SsaTypePropagation::AddDependentInstructionsToWorklist(HPhi* instruction) {
+void PrimitiveTypePropagation::AddDependentInstructionsToWorklist(HPhi* instruction) {
   for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
     HPhi* phi = it.Current()->GetUser()->AsPhi();
     if (phi != nullptr) {
diff --git a/compiler/optimizing/ssa_type_propagation.h b/compiler/optimizing/primitive_type_propagation.h
similarity index 72%
rename from compiler/optimizing/ssa_type_propagation.h
rename to compiler/optimizing/primitive_type_propagation.h
index f4d3d63..1374cbb 100644
--- a/compiler/optimizing/ssa_type_propagation.h
+++ b/compiler/optimizing/primitive_type_propagation.h
@@ -14,17 +14,17 @@
  * limitations under the License.
  */
 
-#ifndef ART_COMPILER_OPTIMIZING_SSA_TYPE_PROPAGATION_H_
-#define ART_COMPILER_OPTIMIZING_SSA_TYPE_PROPAGATION_H_
+#ifndef ART_COMPILER_OPTIMIZING_PRIMITIVE_TYPE_PROPAGATION_H_
+#define ART_COMPILER_OPTIMIZING_PRIMITIVE_TYPE_PROPAGATION_H_
 
 #include "nodes.h"
 
 namespace art {
 
-// Compute and propagate types of phis in the graph.
-class SsaTypePropagation : public ValueObject {
+// Compute and propagate primitive types of phis in the graph.
+class PrimitiveTypePropagation : public ValueObject {
  public:
-  explicit SsaTypePropagation(HGraph* graph)
+  explicit PrimitiveTypePropagation(HGraph* graph)
       : graph_(graph), worklist_(graph->GetArena(), kDefaultWorklistSize) {}
 
   void Run();
@@ -41,9 +41,9 @@
 
   static constexpr size_t kDefaultWorklistSize = 8;
 
-  DISALLOW_COPY_AND_ASSIGN(SsaTypePropagation);
+  DISALLOW_COPY_AND_ASSIGN(PrimitiveTypePropagation);
 };
 
 }  // namespace art
 
-#endif  // ART_COMPILER_OPTIMIZING_SSA_TYPE_PROPAGATION_H_
+#endif  // ART_COMPILER_OPTIMIZING_PRIMITIVE_TYPE_PROPAGATION_H_
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
diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h
new file mode 100644
index 0000000..a74319d
--- /dev/null
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -0,0 +1,53 @@
+/*
+ * 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.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_REFERENCE_TYPE_PROPAGATION_H_
+#define ART_COMPILER_OPTIMIZING_REFERENCE_TYPE_PROPAGATION_H_
+
+#include "nodes.h"
+#include "optimization.h"
+
+namespace art {
+
+/**
+ * Propagates reference types to instructions.
+ * TODO: Currently only nullability is computed.
+ */
+class ReferenceTypePropagation : public HOptimization {
+ public:
+  explicit ReferenceTypePropagation(HGraph* graph)
+    : HOptimization(graph, true, "reference_type_propagation"),
+      worklist_(graph->GetArena(), kDefaultWorklistSize) {}
+
+  void Run() OVERRIDE;
+
+ private:
+  void VisitBasicBlock(HBasicBlock* block);
+  void ProcessWorklist();
+  void AddToWorklist(HPhi* phi);
+  void AddDependentInstructionsToWorklist(HPhi* phi);
+  bool UpdateNullability(HPhi* phi);
+
+  GrowableArray<HPhi*> worklist_;
+
+  static constexpr size_t kDefaultWorklistSize = 8;
+
+  DISALLOW_COPY_AND_ASSIGN(ReferenceTypePropagation);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_REFERENCE_TYPE_PROPAGATION_H_
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 4f9c3b8..c9a21aa 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -17,7 +17,7 @@
 #include "ssa_builder.h"
 
 #include "nodes.h"
-#include "ssa_type_propagation.h"
+#include "primitive_type_propagation.h"
 #include "ssa_phi_elimination.h"
 
 namespace art {
@@ -52,7 +52,7 @@
   // 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());
+  PrimitiveTypePropagation type_propagation(GetGraph());
   type_propagation.Run();
 
   // 5) Clear locals.
diff --git a/test/444-checker-nce/expected.txt b/test/444-checker-nce/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/444-checker-nce/expected.txt
diff --git a/test/444-checker-nce/info.txt b/test/444-checker-nce/info.txt
new file mode 100644
index 0000000..78ad0b9
--- /dev/null
+++ b/test/444-checker-nce/info.txt
@@ -0,0 +1 @@
+Tests for NullCheck elimination.
diff --git a/test/444-checker-nce/src/Main.java b/test/444-checker-nce/src/Main.java
new file mode 100644
index 0000000..cdca332
--- /dev/null
+++ b/test/444-checker-nce/src/Main.java
@@ -0,0 +1,229 @@
+/*
+ * 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.
+ */
+
+public class Main {
+
+  // CHECK-START: Main Main.keepTest(Main) instruction_simplifier_after_types (before)
+  // CHECK:         NullCheck
+  // CHECK:         InvokeStaticOrDirect
+
+  // CHECK-START: Main Main.keepTest(Main) instruction_simplifier_after_types (after)
+  // CHECK:         NullCheck
+  // CHECK:         InvokeStaticOrDirect
+  public Main keepTest(Main m) {
+    return m.g();
+  }
+
+  // CHECK-START: Main Main.thisTest() instruction_simplifier (before)
+  // CHECK:         NullCheck
+  // CHECK:         InvokeStaticOrDirect
+
+  // CHECK-START: Main Main.thisTest() instruction_simplifier (after)
+  // CHECK-NOT:     NullCheck
+  // CHECK:         InvokeStaticOrDirect
+  public Main thisTest() {
+    return g();
+  }
+
+  // CHECK-START: Main Main.newInstanceRemoveTest() instruction_simplifier (before)
+  // CHECK-DAG:     NewInstance
+  // CHECK-DAG:     NullCheck
+  // CHECK-DAG:     InvokeStaticOrDirect
+  // CHECK-DAG:     NullCheck
+  // CHECK-DAG:     InvokeStaticOrDirect
+
+  // CHECK-START: Main Main.newInstanceRemoveTest() instruction_simplifier (after)
+  // CHECK-NOT:     NullCheck
+  public Main newInstanceRemoveTest() {
+    Main m = new Main();
+    return m.g();
+  }
+
+  // CHECK-START: Main Main.newArrayRemoveTest() instruction_simplifier (before)
+  // CHECK-DAG:     NewArray
+  // CHECK-DAG:     NullCheck
+  // CHECK-DAG:     ArrayGet
+
+  // CHECK-START: Main Main.newArrayRemoveTest() instruction_simplifier (after)
+  // CHECK-DAG:     NewArray
+  // CHECK-NOT:     NullCheck
+  // CHECK-DAG:     ArrayGet
+  public Main newArrayRemoveTest() {
+    Main[] ms = new Main[1];
+    return ms[0];
+  }
+
+  // CHECK-START: Main Main.ifRemoveTest(boolean) instruction_simplifier_after_types (before)
+  // CHECK-DAG:     NewInstance
+  // CHECK-DAG:     NullCheck
+
+  // CHECK-START: Main Main.ifRemoveTest(boolean) instruction_simplifier_after_types (after)
+  // CHECK-DAG:     NewInstance
+  // CHECK-NOT:     NullCheck
+  public Main ifRemoveTest(boolean flag) {
+    Main m = null;
+    if (flag) {
+      m = new Main();
+    } else {
+      m = new Main(1);
+    }
+    return m.g();
+  }
+
+  // CHECK-START: Main Main.ifKeepTest(boolean) instruction_simplifier_after_types (before)
+  // CHECK-DAG:     NewInstance
+  // CHECK-DAG:     NullCheck
+
+  // CHECK-START: Main Main.ifKeepTest(boolean) instruction_simplifier_after_types (after)
+  // CHECK-DAG:     NewInstance
+  // CHECK-DAG:     NullCheck
+  public Main ifKeepTest(boolean flag) {
+    Main m = null;
+    if (flag) {
+      m = new Main(1);
+    }
+    return m.g();
+  }
+
+  // CHECK-START: Main Main.forRemoveTest(int) instruction_simplifier_after_types (before)
+  // CHECK:         NullCheck
+
+  // CHECK-START: Main Main.forRemoveTest(int) instruction_simplifier_after_types (after)
+  // CHECK-NOT:     NullCheck
+  public Main forRemoveTest(int count) {
+    Main a = new Main();
+    Main m = new Main();
+    for (int i = 0; i < count; i++) {
+      if (i % 2 == 0) {
+        m = a;
+      }
+    }
+    return m.g();
+  }
+
+  // CHECK-START: Main Main.forKeepTest(int) instruction_simplifier_after_types (before)
+  // CHECK:         NullCheck
+
+  // CHECK-START: Main Main.forKeepTest(int) instruction_simplifier_after_types (after)
+  // CHECK:         NullCheck
+  public Main forKeepTest(int count) {
+    Main a = new Main();
+    Main m = new Main();
+    for (int i = 0; i < count; i++) {
+      if (i % 2 == 0) {
+        m = a;
+      } else {
+        m = null;
+      }
+    }
+    return m.g();
+  }
+
+  // CHECK-START: Main Main.phiFlowRemoveTest(int) instruction_simplifier_after_types (before)
+  // CHECK:         NullCheck
+
+  // CHECK-START: Main Main.phiFlowRemoveTest(int) instruction_simplifier_after_types (after)
+  // CHECK-NOT:     NullCheck
+  public Main phiFlowRemoveTest(int count) {
+    Main a = new Main();
+    Main m = new Main();
+    for (int i = 0; i < count; i++) {
+      if (i % 2 == 0) {
+        m = a;
+      }
+    }
+    Main n = new Main();
+    for (int i = 0; i < count; i++) {
+      if (i % 3 == 0) {
+        n = m;
+      }
+    }
+    return n.g();
+  }
+
+  // CHECK-START: Main Main.phiFlowKeepTest(int) instruction_simplifier_after_types (before)
+  // CHECK:         NullCheck
+
+  // CHECK-START: Main Main.phiFlowKeepTest(int) instruction_simplifier_after_types (after)
+  // CHECK:         NullCheck
+  public Main phiFlowKeepTest(int count) {
+    Main a = new Main();
+    Main m = new Main();
+    for (int i = 0; i < count; i++) {
+      if (i % 2 == 0) {
+        m = a;
+      } else {
+        m = null;
+      }
+    }
+    Main n = new Main();
+    for (int i = 0; i < count; i++) {
+      if (i % 3 == 0) {
+        n = m;
+      }
+    }
+    return n.g();
+  }
+
+  // CHECK-START: Main Main.scopeRemoveTest(int, Main) instruction_simplifier (before)
+  // CHECK:         NullCheck
+
+  // CHECK-START: Main Main.scopeRemoveTest(int, Main) instruction_simplifier (after)
+  // CHECK-NOT:     NullCheck
+  public Main scopeRemoveTest(int count, Main a) {
+    Main m = null;
+    for (int i = 0; i < count; i++) {
+      if (i % 2 == 0) {
+        m = new Main();
+        m.g();
+      } else {
+        m = a;
+      }
+    }
+    return m;
+  }
+
+  // CHECK-START: Main Main.scopeKeepTest(int, Main) instruction_simplifier_after_types (before)
+  // CHECK:         NullCheck
+
+  // CHECK-START: Main Main.scopeKeepTest(int, Main) instruction_simplifier_after_types (after)
+  // CHECK:         NullCheck
+  public Main scopeKeepTest(int count, Main a) {
+    Main m = new Main();
+    for (int i = 0; i < count; i++) {
+      if (i % 2 == 0) {
+        m = a;
+      } else {
+        m = a;
+        m.g();
+      }
+    }
+    return m;
+  }
+
+  public Main() {}
+  public Main(int dummy) {}
+
+  private Main g() {
+    // avoids inlining
+    throw new RuntimeException();
+  }
+
+  public static void main(String[] args) {
+    new Main();
+  }
+
+}