diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 7d3a723..c1e3863 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -46,6 +46,10 @@
   bool TryReplaceWithRotateRegisterSubPattern(HBinaryOperation* op, HUShr* ushr, HShl* shl);
 
   bool TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop);
+  // `op` should be either HOr or HAnd.
+  // De Morgan's laws:
+  // ~a & ~b = ~(a | b)  and  ~a | ~b = ~(a & b)
+  bool TryDeMorganNegationFactoring(HBinaryOperation* op);
   void VisitShift(HBinaryOperation* shift);
 
   void VisitSuspendCheck(HSuspendCheck* check) OVERRIDE;
@@ -164,6 +168,54 @@
   return true;
 }
 
+bool InstructionSimplifierVisitor::TryDeMorganNegationFactoring(HBinaryOperation* op) {
+  DCHECK(op->IsAnd() || op->IsOr()) << op->DebugName();
+  Primitive::Type type = op->GetType();
+  HInstruction* left = op->GetLeft();
+  HInstruction* right = op->GetRight();
+
+  // We can apply De Morgan's laws if both inputs are Not's and are only used
+  // by `op`.
+  if (left->IsNot() &&
+      right->IsNot() &&
+      left->HasOnlyOneNonEnvironmentUse() &&
+      right->HasOnlyOneNonEnvironmentUse()) {
+    // Replace code looking like
+    //    NOT nota, a
+    //    NOT notb, b
+    //    AND dst, nota, notb (respectively OR)
+    // with
+    //    OR or, a, b         (respectively AND)
+    //    NOT dest, or
+    HInstruction* src_left = left->AsNot()->GetInput();
+    HInstruction* src_right = right->AsNot()->GetInput();
+    uint32_t dex_pc = op->GetDexPc();
+
+    // Remove the negations on the inputs.
+    left->ReplaceWith(src_left);
+    right->ReplaceWith(src_right);
+    left->GetBlock()->RemoveInstruction(left);
+    right->GetBlock()->RemoveInstruction(right);
+
+    // Replace the `HAnd` or `HOr`.
+    HBinaryOperation* hbin;
+    if (op->IsAnd()) {
+      hbin = new (GetGraph()->GetArena()) HOr(type, src_left, src_right, dex_pc);
+    } else {
+      hbin = new (GetGraph()->GetArena()) HAnd(type, src_left, src_right, dex_pc);
+    }
+    HNot* hnot = new (GetGraph()->GetArena()) HNot(type, hbin, dex_pc);
+
+    op->GetBlock()->InsertInstructionBefore(hbin, op);
+    op->GetBlock()->ReplaceAndRemoveInstructionWith(op, hnot);
+
+    RecordSimplification();
+    return true;
+  }
+
+  return false;
+}
+
 void InstructionSimplifierVisitor::VisitShift(HBinaryOperation* instruction) {
   DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr());
   HConstant* input_cst = instruction->GetConstantRight();
@@ -813,7 +865,10 @@
     //    src
     instruction->ReplaceWith(instruction->GetLeft());
     instruction->GetBlock()->RemoveInstruction(instruction);
+    return;
   }
+
+  TryDeMorganNegationFactoring(instruction);
 }
 
 void InstructionSimplifierVisitor::VisitGreaterThan(HGreaterThan* condition) {
@@ -1127,6 +1182,8 @@
     return;
   }
 
+  if (TryDeMorganNegationFactoring(instruction)) return;
+
   TryReplaceWithRotate(instruction);
 }
 
@@ -1249,6 +1306,26 @@
     return;
   }
 
+  HInstruction* left = instruction->GetLeft();
+  HInstruction* right = instruction->GetRight();
+  if (left->IsNot() &&
+      right->IsNot() &&
+      left->HasOnlyOneNonEnvironmentUse() &&
+      right->HasOnlyOneNonEnvironmentUse()) {
+    // Replace code looking like
+    //    NOT nota, a
+    //    NOT notb, b
+    //    XOR dst, nota, notb
+    // with
+    //    XOR dst, a, b
+    instruction->ReplaceInput(left->AsNot()->GetInput(), 0);
+    instruction->ReplaceInput(right->AsNot()->GetInput(), 1);
+    left->GetBlock()->RemoveInstruction(left);
+    right->GetBlock()->RemoveInstruction(right);
+    RecordSimplification();
+    return;
+  }
+
   TryReplaceWithRotate(instruction);
 }
 
diff --git a/test/565-checker-doublenegbitwise/expected.txt b/test/565-checker-doublenegbitwise/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/565-checker-doublenegbitwise/expected.txt
diff --git a/test/565-checker-doublenegbitwise/info.txt b/test/565-checker-doublenegbitwise/info.txt
new file mode 100644
index 0000000..cbe183c
--- /dev/null
+++ b/test/565-checker-doublenegbitwise/info.txt
@@ -0,0 +1 @@
+Test double-negated bitwise operations simplifications.
diff --git a/test/565-checker-doublenegbitwise/src/Main.java b/test/565-checker-doublenegbitwise/src/Main.java
new file mode 100644
index 0000000..d681ad7
--- /dev/null
+++ b/test/565-checker-doublenegbitwise/src/Main.java
@@ -0,0 +1,211 @@
+/*
+* Copyright (C) 2016 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 {
+
+  // A dummy value to defeat inlining of these routines.
+  static boolean doThrow = false;
+
+  public static void assertIntEquals(int expected, int result) {
+    if (expected != result) {
+      throw new Error("Expected: " + expected + ", found: " + result);
+    }
+  }
+
+  public static void assertLongEquals(long expected, long result) {
+    if (expected != result) {
+      throw new Error("Expected: " + expected + ", found: " + result);
+    }
+  }
+
+  /**
+   * Test transformation of Not/Not/And into Or/Not.
+   */
+
+  // Note: before the instruction_simplifier pass, Xor's are used instead of
+  // Not's (the simplification happens during the same pass).
+  /// CHECK-START-ARM64: int Main.$opt$noinline$andToOr(int, int) instruction_simplifier (before)
+  /// CHECK:       <<P1:i\d+>>          ParameterValue
+  /// CHECK:       <<P2:i\d+>>          ParameterValue
+  /// CHECK:       <<CstM1:i\d+>>       IntConstant -1
+  /// CHECK:       <<Not1:i\d+>>        Xor [<<P1>>,<<CstM1>>]
+  /// CHECK:       <<Not2:i\d+>>        Xor [<<P2>>,<<CstM1>>]
+  /// CHECK:       <<And:i\d+>>         And [<<Not1>>,<<Not2>>]
+  /// CHECK:                            Return [<<And>>]
+
+  /// CHECK-START-ARM64: int Main.$opt$noinline$andToOr(int, int) instruction_simplifier (after)
+  /// CHECK:       <<P1:i\d+>>          ParameterValue
+  /// CHECK:       <<P2:i\d+>>          ParameterValue
+  /// CHECK:       <<Or:i\d+>>          Or [<<P1>>,<<P2>>]
+  /// CHECK:       <<Not:i\d+>>         Not [<<Or>>]
+  /// CHECK:                            Return [<<Not>>]
+
+  /// CHECK-START-ARM64: int Main.$opt$noinline$andToOr(int, int) instruction_simplifier (after)
+  /// CHECK:                            Not
+  /// CHECK-NOT:                        Not
+  /// CHECK-NOT:                        And
+
+  public static int $opt$noinline$andToOr(int a, int b) {
+    if (doThrow) throw new Error();
+    return ~a & ~b;
+  }
+
+  /**
+   * Test transformation of Not/Not/Or into And/Not.
+   */
+
+  // See note above.
+  // The second Xor has its arguments reversed for no obvious reason.
+  /// CHECK-START-ARM64: long Main.$opt$noinline$orToAnd(long, long) instruction_simplifier (before)
+  /// CHECK:       <<P1:j\d+>>          ParameterValue
+  /// CHECK:       <<P2:j\d+>>          ParameterValue
+  /// CHECK:       <<CstM1:j\d+>>       LongConstant -1
+  /// CHECK:       <<Not1:j\d+>>        Xor [<<P1>>,<<CstM1>>]
+  /// CHECK:       <<Not2:j\d+>>        Xor [<<CstM1>>,<<P2>>]
+  /// CHECK:       <<Or:j\d+>>          Or [<<Not1>>,<<Not2>>]
+  /// CHECK:                            Return [<<Or>>]
+
+  /// CHECK-START-ARM64: long Main.$opt$noinline$orToAnd(long, long) instruction_simplifier (after)
+  /// CHECK:       <<P1:j\d+>>          ParameterValue
+  /// CHECK:       <<P2:j\d+>>          ParameterValue
+  /// CHECK:       <<And:j\d+>>         And [<<P1>>,<<P2>>]
+  /// CHECK:       <<Not:j\d+>>         Not [<<And>>]
+  /// CHECK:                            Return [<<Not>>]
+
+  /// CHECK-START-ARM64: long Main.$opt$noinline$orToAnd(long, long) instruction_simplifier (after)
+  /// CHECK:                            Not
+  /// CHECK-NOT:                        Not
+  /// CHECK-NOT:                        Or
+
+  public static long $opt$noinline$orToAnd(long a, long b) {
+    if (doThrow) throw new Error();
+    return ~a | ~b;
+  }
+
+  /**
+   * Test that the transformation copes with inputs being separated from the
+   * bitwise operations.
+   * This is a regression test. The initial logic was inserting the new bitwise
+   * operation incorrectly.
+   */
+
+  /// CHECK-START-ARM64: int Main.$opt$noinline$regressInputsAway(int, int) instruction_simplifier (before)
+  /// CHECK:       <<P1:i\d+>>          ParameterValue
+  /// CHECK:       <<P2:i\d+>>          ParameterValue
+  /// CHECK-DAG:   <<Cst1:i\d+>>        IntConstant 1
+  /// CHECK-DAG:   <<CstM1:i\d+>>       IntConstant -1
+  /// CHECK:       <<AddP1:i\d+>>       Add [<<P1>>,<<Cst1>>]
+  /// CHECK:       <<Not1:i\d+>>        Xor [<<AddP1>>,<<CstM1>>]
+  /// CHECK:       <<AddP2:i\d+>>       Add [<<P2>>,<<Cst1>>]
+  /// CHECK:       <<Not2:i\d+>>        Xor [<<AddP2>>,<<CstM1>>]
+  /// CHECK:       <<Or:i\d+>>          Or [<<Not1>>,<<Not2>>]
+  /// CHECK:                            Return [<<Or>>]
+
+  /// CHECK-START-ARM64: int Main.$opt$noinline$regressInputsAway(int, int) instruction_simplifier (after)
+  /// CHECK:       <<P1:i\d+>>          ParameterValue
+  /// CHECK:       <<P2:i\d+>>          ParameterValue
+  /// CHECK:       <<Cst1:i\d+>>        IntConstant 1
+  /// CHECK:       <<AddP1:i\d+>>       Add [<<P1>>,<<Cst1>>]
+  /// CHECK:       <<AddP2:i\d+>>       Add [<<P2>>,<<Cst1>>]
+  /// CHECK:       <<And:i\d+>>         And [<<AddP1>>,<<AddP2>>]
+  /// CHECK:       <<Not:i\d+>>         Not [<<And>>]
+  /// CHECK:                            Return [<<Not>>]
+
+  /// CHECK-START-ARM64: int Main.$opt$noinline$regressInputsAway(int, int) instruction_simplifier (after)
+  /// CHECK:                            Not
+  /// CHECK-NOT:                        Not
+  /// CHECK-NOT:                        Or
+
+  public static int $opt$noinline$regressInputsAway(int a, int b) {
+    if (doThrow) throw new Error();
+    int a1 = a + 1;
+    int not_a1 = ~a1;
+    int b1 = b + 1;
+    int not_b1 = ~b1;
+    return not_a1 | not_b1;
+  }
+
+  /**
+   * Test transformation of Not/Not/Xor into Xor.
+   */
+
+  // See first note above.
+  /// CHECK-START-ARM64: int Main.$opt$noinline$notXorToXor(int, int) instruction_simplifier (before)
+  /// CHECK:       <<P1:i\d+>>          ParameterValue
+  /// CHECK:       <<P2:i\d+>>          ParameterValue
+  /// CHECK:       <<CstM1:i\d+>>       IntConstant -1
+  /// CHECK:       <<Not1:i\d+>>        Xor [<<P1>>,<<CstM1>>]
+  /// CHECK:       <<Not2:i\d+>>        Xor [<<P2>>,<<CstM1>>]
+  /// CHECK:       <<Xor:i\d+>>         Xor [<<Not1>>,<<Not2>>]
+  /// CHECK:                            Return [<<Xor>>]
+
+  /// CHECK-START-ARM64: int Main.$opt$noinline$notXorToXor(int, int) instruction_simplifier (after)
+  /// CHECK:       <<P1:i\d+>>          ParameterValue
+  /// CHECK:       <<P2:i\d+>>          ParameterValue
+  /// CHECK:       <<Xor:i\d+>>         Xor [<<P1>>,<<P2>>]
+  /// CHECK:                            Return [<<Xor>>]
+
+  /// CHECK-START-ARM64: int Main.$opt$noinline$notXorToXor(int, int) instruction_simplifier (after)
+  /// CHECK-NOT:                        Not
+
+  public static int $opt$noinline$notXorToXor(int a, int b) {
+    if (doThrow) throw new Error();
+    return ~a ^ ~b;
+  }
+
+  /**
+   * Check that no transformation is done when one Not has multiple uses.
+   */
+
+  /// CHECK-START-ARM64: int Main.$opt$noinline$notMultipleUses(int, int) instruction_simplifier (before)
+  /// CHECK:       <<P1:i\d+>>          ParameterValue
+  /// CHECK:       <<P2:i\d+>>          ParameterValue
+  /// CHECK:       <<CstM1:i\d+>>       IntConstant -1
+  /// CHECK:       <<One:i\d+>>         IntConstant 1
+  /// CHECK:       <<Not2:i\d+>>        Xor [<<P2>>,<<CstM1>>]
+  /// CHECK:       <<And2:i\d+>>        And [<<Not2>>,<<One>>]
+  /// CHECK:       <<Not1:i\d+>>        Xor [<<P1>>,<<CstM1>>]
+  /// CHECK:       <<And1:i\d+>>        And [<<Not1>>,<<Not2>>]
+  /// CHECK:       <<Add:i\d+>>         Add [<<And2>>,<<And1>>]
+  /// CHECK:                            Return [<<Add>>]
+
+  /// CHECK-START-ARM64: int Main.$opt$noinline$notMultipleUses(int, int) instruction_simplifier (after)
+  /// CHECK:       <<P1:i\d+>>          ParameterValue
+  /// CHECK:       <<P2:i\d+>>          ParameterValue
+  /// CHECK:       <<One:i\d+>>         IntConstant 1
+  /// CHECK:       <<Not2:i\d+>>        Not [<<P2>>]
+  /// CHECK:       <<And2:i\d+>>        And [<<Not2>>,<<One>>]
+  /// CHECK:       <<Not1:i\d+>>        Not [<<P1>>]
+  /// CHECK:       <<And1:i\d+>>        And [<<Not1>>,<<Not2>>]
+  /// CHECK:       <<Add:i\d+>>         Add [<<And2>>,<<And1>>]
+  /// CHECK:                            Return [<<Add>>]
+
+  /// CHECK-START-ARM64: int Main.$opt$noinline$notMultipleUses(int, int) instruction_simplifier (after)
+  /// CHECK-NOT:                        Or
+
+  public static int $opt$noinline$notMultipleUses(int a, int b) {
+    if (doThrow) throw new Error();
+    int tmp = ~b;
+    return (tmp & 0x1) + (~a & tmp);
+  }
+
+  public static void main(String[] args) {
+    assertIntEquals(~0xff, $opt$noinline$andToOr(0xf, 0xff));
+    assertLongEquals(~0xf, $opt$noinline$orToAnd(0xf, 0xff));
+    assertIntEquals(0xf0, $opt$noinline$notXorToXor(0xf, 0xff));
+    assertIntEquals(~0xff, $opt$noinline$notMultipleUses(0xf, 0xff));
+  }
+}