Optimizing: double-negated bitwise operations simplifications
Generic instruction simplifications applying to bitwise operations when
both inputs are Not's. And and Or are handled by De Morgan's laws,
removing one instruction:
~a & ~b -> ~(a | b)
~a | ~b -> ~(a & b)
Xor is handled by this trivial relation, removing two instructions:
~a ^ ~b = a ^ b
The simplifications only happen when neither Not is used by other
instructions.
Change-Id: I5d5187af2f625c475c3e49466af6bc3e87595f8f
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 49fc8c7..3f66c66 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 TryApplyDeMorgan(HBinaryOperation* op);
void VisitShift(HBinaryOperation* shift);
void VisitSuspendCheck(HSuspendCheck* check) OVERRIDE;
@@ -162,6 +166,64 @@
return true;
}
+bool InstructionSimplifierVisitor::TryApplyDeMorgan(HBinaryOperation* op) {
+ DCHECK(op->IsAnd() || op->IsOr());
+ 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();
+
+ 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);
+ }
+ // Step 1: replace left Not by new binary operation (this is arbitrary,
+ // the right one could have been used instead).
+ // SL SR SL SR
+ // | | | / |
+ // Not Not NewBin Not
+ // \ / -> \ /
+ // OldBin OldBin
+ // | |
+ left->GetBlock()->ReplaceAndRemoveInstructionWith(left, hbin);
+
+ HNot* hnot = new (GetGraph()->GetArena()) HNot(type, hbin, dex_pc);
+ // Step 2: replace old binary operation by a new Not, and remove
+ // the now disconnected right Not.
+ // SL SR SL SR
+ // | / | | / |
+ // NewBin Not NewBin Not [removed]
+ // \ / -> \ x
+ // OldBin Not
+ // | |
+ op->GetBlock()->ReplaceAndRemoveInstructionWith(op, hnot);
+ right->GetBlock()->RemoveInstruction(right);
+
+ RecordSimplification();
+ return true;
+ }
+
+ return false;
+}
+
void InstructionSimplifierVisitor::VisitShift(HBinaryOperation* instruction) {
DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr());
HConstant* input_cst = instruction->GetConstantRight();
@@ -739,7 +801,10 @@
// src
instruction->ReplaceWith(instruction->GetLeft());
instruction->GetBlock()->RemoveInstruction(instruction);
+ return;
}
+
+ TryApplyDeMorgan(instruction);
}
void InstructionSimplifierVisitor::VisitGreaterThan(HGreaterThan* condition) {
@@ -1053,6 +1118,8 @@
return;
}
+ if (TryApplyDeMorgan(instruction)) return;
+
TryReplaceWithRotate(instruction);
}
@@ -1175,6 +1242,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..1e30b5d
--- /dev/null
+++ b/test/565-checker-doublenegbitwise/src/Main.java
@@ -0,0 +1,168 @@
+/*
+* 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 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));
+ }
+}