diff --git a/test/458-checker-instruct-simplification/build b/test/458-checker-instruct-simplification/build
new file mode 100755
index 0000000..49292c9
--- /dev/null
+++ b/test/458-checker-instruct-simplification/build
@@ -0,0 +1,23 @@
+#!/bin/bash
+#
+# Copyright 2017 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.
+
+# This checker test is incompatible with jack bytecode output,
+# so force it to use javac/dx.
+export USE_JACK=false
+# Also disable desugar because it is missing in jack platform builds.
+export DESUGAR=false
+
+./default-build "$@"
diff --git a/test/458-checker-instruct-simplification/smali/SmaliTests.smali b/test/458-checker-instruct-simplification/smali/SmaliTests.smali
index 6845961..a8d7d94 100644
--- a/test/458-checker-instruct-simplification/smali/SmaliTests.smali
+++ b/test/458-checker-instruct-simplification/smali/SmaliTests.smali
@@ -327,3 +327,144 @@
 
     return v0
 .end method
+
+# Test simplification of the `~~var` pattern.
+# The transformation tested is implemented in `InstructionSimplifierVisitor::VisitNot`.
+
+## CHECK-START: long SmaliTests.NotNot1(long) instruction_simplifier (before)
+## CHECK-DAG:     <<Arg:j\d+>>      ParameterValue
+## CHECK-DAG:     <<Not1:j\d+>>     Not [<<Arg>>]
+## CHECK-DAG:     <<Not2:j\d+>>     Not [<<Not1>>]
+## CHECK-DAG:                       Return [<<Not2>>]
+
+## CHECK-START: long SmaliTests.NotNot1(long) instruction_simplifier (after)
+## CHECK-DAG:     <<Arg:j\d+>>      ParameterValue
+## CHECK-DAG:                       Return [<<Arg>>]
+
+## CHECK-START: long SmaliTests.NotNot1(long) instruction_simplifier (after)
+## CHECK-NOT:                       Not
+
+.method public static NotNot1(J)J
+    .registers 4
+    .param p0, "arg"    # J
+
+    .prologue
+    sget-boolean v0, LMain;->doThrow:Z
+
+    # if (doThrow) throw new Error();
+    if-eqz v0, :cond_a
+    new-instance v0, Ljava/lang/Error;
+    invoke-direct {v0}, Ljava/lang/Error;-><init>()V
+    throw v0
+
+  :cond_a
+    # return ~~arg
+    not-long v0, p0
+    not-long v0, v0
+    return-wide v0
+.end method
+
+## CHECK-START: int SmaliTests.NotNot2(int) instruction_simplifier (before)
+## CHECK-DAG:     <<Arg:i\d+>>      ParameterValue
+## CHECK-DAG:     <<Not1:i\d+>>     Not [<<Arg>>]
+## CHECK-DAG:     <<Not2:i\d+>>     Not [<<Not1>>]
+## CHECK-DAG:     <<Add:i\d+>>      Add [<<Not2>>,<<Not1>>]
+## CHECK-DAG:                       Return [<<Add>>]
+
+## CHECK-START: int SmaliTests.NotNot2(int) instruction_simplifier (after)
+## CHECK-DAG:     <<Arg:i\d+>>      ParameterValue
+## CHECK-DAG:     <<Not:i\d+>>      Not [<<Arg>>]
+## CHECK-DAG:     <<Add:i\d+>>      Add [<<Arg>>,<<Not>>]
+## CHECK-DAG:                       Return [<<Add>>]
+
+## CHECK-START: int SmaliTests.NotNot2(int) instruction_simplifier (after)
+## CHECK:                           Not
+## CHECK-NOT:                       Not
+
+.method public static NotNot2(I)I
+    .registers 3
+    .param p0, "arg"    # I
+
+    .prologue
+    sget-boolean v1, LMain;->doThrow:Z
+
+    # if (doThrow) throw new Error();
+    if-eqz v1, :cond_a
+    new-instance v1, Ljava/lang/Error;
+    invoke-direct {v1}, Ljava/lang/Error;-><init>()V
+    throw v1
+
+  :cond_a
+    # temp = ~arg; return temp + ~temp;
+    not-int v0, p0
+    not-int v1, v0
+    add-int/2addr v1, v0
+
+    return v1
+.end method
+
+# Test simplification of double Boolean negation. Note that sometimes
+# both negations can be removed but we only expect the simplifier to
+# remove the second.
+
+## CHECK-START: boolean SmaliTests.NotNotBool(boolean) instruction_simplifier (before)
+## CHECK-DAG:     <<Arg:z\d+>>       ParameterValue
+## CHECK-DAG:     <<Const1:i\d+>>    IntConstant 1
+## CHECK-DAG:     <<Result:z\d+>>    InvokeStaticOrDirect
+## CHECK-DAG:     <<NotResult:i\d+>> Xor [<<Result>>,<<Const1>>]
+## CHECK-DAG:                        Return [<<NotResult>>]
+
+## CHECK-START: boolean SmaliTests.NotNotBool(boolean) instruction_simplifier (after)
+## CHECK-DAG:     <<Arg:z\d+>>       ParameterValue
+## CHECK-DAG:     <<Result:z\d+>>    InvokeStaticOrDirect
+## CHECK-DAG:     <<NotResult:z\d+>> BooleanNot [<<Result>>]
+## CHECK-DAG:                        Return [<<NotResult>>]
+
+## CHECK-START: boolean SmaliTests.NotNotBool(boolean) instruction_simplifier$after_inlining (before)
+## CHECK-DAG:     <<Arg:z\d+>>       ParameterValue
+## CHECK-DAG:     <<NotArg:z\d+>>    BooleanNot [<<Arg>>]
+## CHECK-DAG:     <<NotNotArg:z\d+>> BooleanNot [<<NotArg>>]
+## CHECK-DAG:                        Return [<<NotNotArg>>]
+
+## CHECK-START: boolean SmaliTests.NotNotBool(boolean) instruction_simplifier$after_inlining (after)
+## CHECK-DAG:     <<Arg:z\d+>>       ParameterValue
+## CHECK-DAG:     <<NotArg:z\d+>>    BooleanNot [<<Arg>>]
+## CHECK-DAG:                        Return [<<Arg>>]
+
+## CHECK-START: boolean SmaliTests.NotNotBool(boolean) dead_code_elimination$final (after)
+## CHECK-DAG:     <<Arg:z\d+>>       ParameterValue
+## CHECK-DAG:                        Return [<<Arg>>]
+
+.method public static NegateValue(Z)Z
+    .registers 2
+    .param p0, "arg"    # Z
+
+    .prologue
+
+    # return !arg
+    xor-int/lit8 v0, p0, 0x1
+    return v0
+.end method
+
+
+.method public static NotNotBool(Z)Z
+    .registers 2
+    .param p0, "arg"    # Z
+
+    .prologue
+    sget-boolean v0, LMain;->doThrow:Z
+
+    # if (doThrow) throw new Error();
+    if-eqz v0, :cond_a
+    new-instance v0, Ljava/lang/Error;
+    invoke-direct {v0}, Ljava/lang/Error;-><init>()V
+    throw v0
+
+  :cond_a
+    # return !Negate(arg)
+    invoke-static {p0}, LSmaliTests;->NegateValue(Z)Z
+    move-result v0
+    xor-int/lit8 v0, v0, 0x1
+
+    return v0
+.end method
diff --git a/test/458-checker-instruct-simplification/src/Main.java b/test/458-checker-instruct-simplification/src/Main.java
index 529ea5b..5c36ce9 100644
--- a/test/458-checker-instruct-simplification/src/Main.java
+++ b/test/458-checker-instruct-simplification/src/Main.java
@@ -982,17 +982,18 @@
    */
 
   /// CHECK-START: long Main.$noinline$NotNot1(long) instruction_simplifier (before)
-  /// CHECK-DAG:     <<Arg:j\d+>>      ParameterValue
-  /// CHECK-DAG:     <<Not1:j\d+>>     Not [<<Arg>>]
-  /// CHECK-DAG:     <<Not2:j\d+>>     Not [<<Not1>>]
-  /// CHECK-DAG:                       Return [<<Not2>>]
+  /// CHECK-DAG:     <<Arg:j\d+>>       ParameterValue
+  /// CHECK-DAG:     <<ConstNeg1:j\d+>> LongConstant -1
+  /// CHECK-DAG:     <<Not1:j\d+>>      Xor [<<Arg>>,<<ConstNeg1>>]
+  /// CHECK-DAG:     <<Not2:j\d+>>      Xor [<<Not1>>,<<ConstNeg1>>]
+  /// CHECK-DAG:                        Return [<<Not2>>]
 
   /// CHECK-START: long Main.$noinline$NotNot1(long) instruction_simplifier (after)
   /// CHECK-DAG:     <<Arg:j\d+>>      ParameterValue
   /// CHECK-DAG:                       Return [<<Arg>>]
 
   /// CHECK-START: long Main.$noinline$NotNot1(long) instruction_simplifier (after)
-  /// CHECK-NOT:                       Not
+  /// CHECK-NOT:                       Xor
 
   public static long $noinline$NotNot1(long arg) {
     if (doThrow) { throw new Error(); }
@@ -1000,11 +1001,12 @@
   }
 
   /// CHECK-START: int Main.$noinline$NotNot2(int) instruction_simplifier (before)
-  /// CHECK-DAG:     <<Arg:i\d+>>      ParameterValue
-  /// CHECK-DAG:     <<Not1:i\d+>>     Not [<<Arg>>]
-  /// CHECK-DAG:     <<Not2:i\d+>>     Not [<<Not1>>]
-  /// CHECK-DAG:     <<Add:i\d+>>      Add [<<Not2>>,<<Not1>>]
-  /// CHECK-DAG:                       Return [<<Add>>]
+  /// CHECK-DAG:     <<Arg:i\d+>>       ParameterValue
+  /// CHECK-DAG:     <<ConstNeg1:i\d+>> IntConstant -1
+  /// CHECK-DAG:     <<Not1:i\d+>>      Xor [<<Arg>>,<<ConstNeg1>>]
+  /// CHECK-DAG:     <<Not2:i\d+>>      Xor [<<Not1>>,<<ConstNeg1>>]
+  /// CHECK-DAG:     <<Add:i\d+>>       Add [<<Not2>>,<<Not1>>]
+  /// CHECK-DAG:                        Return [<<Add>>]
 
   /// CHECK-START: int Main.$noinline$NotNot2(int) instruction_simplifier (after)
   /// CHECK-DAG:     <<Arg:i\d+>>      ParameterValue
@@ -1016,6 +1018,9 @@
   /// CHECK:                           Not
   /// CHECK-NOT:                       Not
 
+  /// CHECK-START: int Main.$noinline$NotNot2(int) instruction_simplifier (after)
+  /// CHECK-NOT:                       Xor
+
   public static int $noinline$NotNot2(int arg) {
     if (doThrow) { throw new Error(); }
     int temp = ~arg;
@@ -1180,30 +1185,46 @@
 
   /// CHECK-START: boolean Main.$noinline$NotNotBool(boolean) instruction_simplifier (before)
   /// CHECK-DAG:     <<Arg:z\d+>>       ParameterValue
-  /// CHECK-DAG:     <<Const1:i\d+>>    IntConstant 1
-  /// CHECK-DAG:     <<Result:z\d+>>    InvokeStaticOrDirect
-  /// CHECK-DAG:     <<NotResult:i\d+>> Xor [<<Result>>,<<Const1>>]
-  /// CHECK-DAG:                        Return [<<NotResult>>]
+  /// CHECK-DAG:     <<Const1:i\d+>>    IntConstant 0
+  /// CHECK-DAG:     <<Result:z\d+>>    InvokeStaticOrDirect method_name:Main.NegateValue
+  /// CHECK-DAG:     <<NotResult:z\d+>> NotEqual [<<Result>>,<<Const1>>]
+  /// CHECK-DAG:                        If [<<NotResult>>]
+
+  /// CHECK-START: boolean Main.$noinline$NotNotBool(boolean) instruction_simplifier (after)
+  /// CHECK-NOT:                        NotEqual
 
   /// CHECK-START: boolean Main.$noinline$NotNotBool(boolean) instruction_simplifier (after)
   /// CHECK-DAG:     <<Arg:z\d+>>       ParameterValue
-  /// CHECK-DAG:     <<Result:z\d+>>    InvokeStaticOrDirect
-  /// CHECK-DAG:     <<NotResult:z\d+>> BooleanNot [<<Result>>]
-  /// CHECK-DAG:                        Return [<<NotResult>>]
+  /// CHECK-DAG:     <<Result:z\d+>>    InvokeStaticOrDirect method_name:Main.NegateValue
+  /// CHECK-DAG:     <<Const0:i\d+>>    IntConstant 0
+  /// CHECK-DAG:     <<Const1:i\d+>>    IntConstant 1
+  /// CHECK-DAG:     <<Phi:i\d+>>       Phi [<<Const1>>,<<Const0>>]
+  /// CHECK-DAG:                        Return [<<Phi>>]
 
   /// CHECK-START: boolean Main.$noinline$NotNotBool(boolean) instruction_simplifier$after_inlining (before)
   /// CHECK-DAG:     <<Arg:z\d+>>       ParameterValue
-  /// CHECK-DAG:     <<NotArg:z\d+>>    BooleanNot [<<Arg>>]
-  /// CHECK-DAG:     <<NotNotArg:z\d+>> BooleanNot [<<NotArg>>]
-  /// CHECK-DAG:                        Return [<<NotNotArg>>]
+  /// CHECK-NOT:                        BooleanNot [<<Arg>>]
+  /// CHECK-NOT:                        Phi
+
+  /// CHECK-START: boolean Main.$noinline$NotNotBool(boolean) instruction_simplifier$after_inlining (before)
+  /// CHECK-DAG:     <<Arg:z\d+>>       ParameterValue
+  /// CHECK-DAG:     <<Const0:i\d+>>    IntConstant 0
+  /// CHECK-DAG:     <<Const1:i\d+>>    IntConstant 1
+  /// CHECK-DAG:     <<Sel:i\d+>>       Select [<<Const1>>,<<Const0>>,<<Arg>>]
+  /// CHECK-DAG:     <<Sel2:i\d+>>      Select [<<Const1>>,<<Const0>>,<<Sel>>]
+  /// CHECK-DAG:                        Return [<<Sel2>>]
 
   /// CHECK-START: boolean Main.$noinline$NotNotBool(boolean) instruction_simplifier$after_inlining (after)
   /// CHECK-DAG:     <<Arg:z\d+>>       ParameterValue
-  /// CHECK-DAG:     <<NotArg:z\d+>>    BooleanNot [<<Arg>>]
-  /// CHECK-DAG:                        Return [<<Arg>>]
+  /// CHECK:                            BooleanNot [<<Arg>>]
+  /// CHECK-NEXT:                       Goto
+
+  /// CHECK-START: boolean Main.$noinline$NotNotBool(boolean) instruction_simplifier$after_inlining (after)
+  /// CHECK-NOT:                        Select
 
   /// CHECK-START: boolean Main.$noinline$NotNotBool(boolean) dead_code_elimination$final (after)
   /// CHECK-DAG:     <<Arg:z\d+>>       ParameterValue
+  /// CHECK-NOT:                        BooleanNot [<<Arg>>]
   /// CHECK-DAG:                        Return [<<Arg>>]
 
   public static boolean NegateValue(boolean arg) {
@@ -1882,7 +1903,18 @@
     }
   }
 
-  public static int $noinline$runSmaliTestConst(String name, int arg) {
+  public static boolean $noinline$runSmaliTestBoolean(String name, boolean input) {
+    if (doThrow) { throw new Error(); }
+    try {
+      Class<?> c = Class.forName("SmaliTests");
+      Method m = c.getMethod(name, boolean.class);
+      return (Boolean) m.invoke(null, input);
+    } catch (Exception ex) {
+      throw new Error(ex);
+    }
+  }
+
+  public static int $noinline$runSmaliTestInt(String name, int arg) {
     if (doThrow) { throw new Error(); }
     try {
       Class<?> c = Class.forName("SmaliTests");
@@ -1893,6 +1925,17 @@
     }
   }
 
+  public static long $noinline$runSmaliTestLong(String name, long arg) {
+    if (doThrow) { throw new Error(); }
+    try {
+      Class<?> c = Class.forName("SmaliTests");
+      Method m = c.getMethod(name, long.class);
+      return (Long) m.invoke(null, arg);
+    } catch (Exception ex) {
+      throw new Error(ex);
+    }
+  }
+
   /// CHECK-START: int Main.$noinline$intUnnecessaryShiftMasking(int, int) instruction_simplifier (before)
   /// CHECK:          <<Value:i\d+>>    ParameterValue
   /// CHECK:          <<Shift:i\d+>>    ParameterValue
@@ -2188,7 +2231,9 @@
     assertIntEquals(1, $noinline$NegSub1(arg, arg + 1));
     assertIntEquals(1, $noinline$NegSub2(arg, arg + 1));
     assertLongEquals(arg, $noinline$NotNot1(arg));
+    assertLongEquals(arg, $noinline$runSmaliTestLong("NotNot1", arg));
     assertIntEquals(-1, $noinline$NotNot2(arg));
+    assertIntEquals(-1, $noinline$runSmaliTestInt("NotNot2", arg));
     assertIntEquals(-(arg + arg + 1), $noinline$SubNeg1(arg, arg + 1));
     assertIntEquals(-(arg + arg + 1), $noinline$SubNeg2(arg, arg + 1));
     assertLongEquals(-(2 * arg + 1), $noinline$SubNeg3(arg, arg + 1));
@@ -2197,7 +2242,9 @@
     assertBooleanEquals(false, $noinline$NotEqualBoolVsIntConst(false));
     assertBooleanEquals(false, $noinline$NotEqualBoolVsIntConst(false));
     assertBooleanEquals(true, $noinline$NotNotBool(true));
+    assertBooleanEquals(true, $noinline$runSmaliTestBoolean("NotNotBool", true));
     assertBooleanEquals(false, $noinline$NotNotBool(false));
+    assertBooleanEquals(false, $noinline$runSmaliTestBoolean("NotNotBool", false));
     assertFloatEquals(50.0f, $noinline$Div2(100.0f));
     assertDoubleEquals(75.0, $noinline$Div2(150.0));
     assertFloatEquals(-400.0f, $noinline$DivMP25(100.0f));
@@ -2309,11 +2356,11 @@
       }
     }
 
-    assertIntEquals(0, $noinline$runSmaliTestConst("AddSubConst", 1));
-    assertIntEquals(3, $noinline$runSmaliTestConst("SubAddConst", 2));
-    assertIntEquals(-16, $noinline$runSmaliTestConst("SubSubConst1", 3));
-    assertIntEquals(-5, $noinline$runSmaliTestConst("SubSubConst2", 4));
-    assertIntEquals(26, $noinline$runSmaliTestConst("SubSubConst3", 5));
+    assertIntEquals(0, $noinline$runSmaliTestInt("AddSubConst", 1));
+    assertIntEquals(3, $noinline$runSmaliTestInt("SubAddConst", 2));
+    assertIntEquals(-16, $noinline$runSmaliTestInt("SubSubConst1", 3));
+    assertIntEquals(-5, $noinline$runSmaliTestInt("SubSubConst2", 4));
+    assertIntEquals(26, $noinline$runSmaliTestInt("SubSubConst3", 5));
     assertIntEquals(0x5e6f7808, $noinline$intUnnecessaryShiftMasking(0xabcdef01, 3));
     assertIntEquals(0x5e6f7808, $noinline$intUnnecessaryShiftMasking(0xabcdef01, 3 + 32));
     assertLongEquals(0xffffffffffffeaf3L, $noinline$longUnnecessaryShiftMasking(0xabcdef0123456789L, 50));
diff --git a/test/knownfailures.json b/test/knownfailures.json
index db993b7..a21c97c 100644
--- a/test/knownfailures.json
+++ b/test/knownfailures.json
@@ -602,7 +602,6 @@
     },
     {
         "tests": [
-            "458-checker-instruct-simplification",
             "536-checker-intrinsic-optimization",
             "565-checker-doublenegbitwise",
             "567-checker-compare",