From ca0e3a0c9f1fd5902dc40043b061d2f9b79ec098 Mon Sep 17 00:00:00 2001 From: Alexandre Rames Date: Wed, 3 Feb 2016 10:54:07 +0000 Subject: [PATCH] Revert "Revert "Optimizing: double-negated bitwise operations simplifications"" This reverts commit 737c0a99dfbba306ec1f50e2adf66b5d97805af6 with fixes. In the original patch, the new instruction could be inserted before one of its inputs. A regression test is also added. Change-Id: Ie49a17ac90ff048355d9cc944b468cd1b1914424 --- compiler/optimizing/instruction_simplifier.cc | 77 +++++++++ test/565-checker-doublenegbitwise/expected.txt | 0 test/565-checker-doublenegbitwise/info.txt | 1 + test/565-checker-doublenegbitwise/src/Main.java | 211 ++++++++++++++++++++++++ 4 files changed, 289 insertions(+) create mode 100644 test/565-checker-doublenegbitwise/expected.txt create mode 100644 test/565-checker-doublenegbitwise/info.txt create mode 100644 test/565-checker-doublenegbitwise/src/Main.java diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc index 7d3a7238d..c1e38633f 100644 --- a/compiler/optimizing/instruction_simplifier.cc +++ b/compiler/optimizing/instruction_simplifier.cc @@ -46,6 +46,10 @@ class InstructionSimplifierVisitor : public HGraphDelegateVisitor { 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 @@ bool InstructionSimplifierVisitor::TryMoveNegOnInputsAfterBinop(HBinaryOperation 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 @@ void InstructionSimplifierVisitor::VisitAnd(HAnd* instruction) { // src instruction->ReplaceWith(instruction->GetLeft()); instruction->GetBlock()->RemoveInstruction(instruction); + return; } + + TryDeMorganNegationFactoring(instruction); } void InstructionSimplifierVisitor::VisitGreaterThan(HGreaterThan* condition) { @@ -1127,6 +1182,8 @@ void InstructionSimplifierVisitor::VisitOr(HOr* instruction) { return; } + if (TryDeMorganNegationFactoring(instruction)) return; + TryReplaceWithRotate(instruction); } @@ -1249,6 +1306,26 @@ void InstructionSimplifierVisitor::VisitXor(HXor* instruction) { 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 000000000..e69de29bb diff --git a/test/565-checker-doublenegbitwise/info.txt b/test/565-checker-doublenegbitwise/info.txt new file mode 100644 index 000000000..cbe183c40 --- /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 000000000..d681ad7e8 --- /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: <> ParameterValue + /// CHECK: <> ParameterValue + /// CHECK: <> IntConstant -1 + /// CHECK: <> Xor [<>,<>] + /// CHECK: <> Xor [<>,<>] + /// CHECK: <> And [<>,<>] + /// CHECK: Return [<>] + + /// CHECK-START-ARM64: int Main.$opt$noinline$andToOr(int, int) instruction_simplifier (after) + /// CHECK: <> ParameterValue + /// CHECK: <> ParameterValue + /// CHECK: <> Or [<>,<>] + /// CHECK: <> Not [<>] + /// CHECK: Return [<>] + + /// 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: <> ParameterValue + /// CHECK: <> ParameterValue + /// CHECK: <> LongConstant -1 + /// CHECK: <> Xor [<>,<>] + /// CHECK: <> Xor [<>,<>] + /// CHECK: <> Or [<>,<>] + /// CHECK: Return [<>] + + /// CHECK-START-ARM64: long Main.$opt$noinline$orToAnd(long, long) instruction_simplifier (after) + /// CHECK: <> ParameterValue + /// CHECK: <> ParameterValue + /// CHECK: <> And [<>,<>] + /// CHECK: <> Not [<>] + /// CHECK: Return [<>] + + /// 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: <> ParameterValue + /// CHECK: <> ParameterValue + /// CHECK-DAG: <> IntConstant 1 + /// CHECK-DAG: <> IntConstant -1 + /// CHECK: <> Add [<>,<>] + /// CHECK: <> Xor [<>,<>] + /// CHECK: <> Add [<>,<>] + /// CHECK: <> Xor [<>,<>] + /// CHECK: <> Or [<>,<>] + /// CHECK: Return [<>] + + /// CHECK-START-ARM64: int Main.$opt$noinline$regressInputsAway(int, int) instruction_simplifier (after) + /// CHECK: <> ParameterValue + /// CHECK: <> ParameterValue + /// CHECK: <> IntConstant 1 + /// CHECK: <> Add [<>,<>] + /// CHECK: <> Add [<>,<>] + /// CHECK: <> And [<>,<>] + /// CHECK: <> Not [<>] + /// CHECK: Return [<>] + + /// 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: <> ParameterValue + /// CHECK: <> ParameterValue + /// CHECK: <> IntConstant -1 + /// CHECK: <> Xor [<>,<>] + /// CHECK: <> Xor [<>,<>] + /// CHECK: <> Xor [<>,<>] + /// CHECK: Return [<>] + + /// CHECK-START-ARM64: int Main.$opt$noinline$notXorToXor(int, int) instruction_simplifier (after) + /// CHECK: <> ParameterValue + /// CHECK: <> ParameterValue + /// CHECK: <> Xor [<>,<>] + /// CHECK: Return [<>] + + /// 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: <> ParameterValue + /// CHECK: <> ParameterValue + /// CHECK: <> IntConstant -1 + /// CHECK: <> IntConstant 1 + /// CHECK: <> Xor [<>,<>] + /// CHECK: <> And [<>,<>] + /// CHECK: <> Xor [<>,<>] + /// CHECK: <> And [<>,<>] + /// CHECK: <> Add [<>,<>] + /// CHECK: Return [<>] + + /// CHECK-START-ARM64: int Main.$opt$noinline$notMultipleUses(int, int) instruction_simplifier (after) + /// CHECK: <> ParameterValue + /// CHECK: <> ParameterValue + /// CHECK: <> IntConstant 1 + /// CHECK: <> Not [<>] + /// CHECK: <> And [<>,<>] + /// CHECK: <> Not [<>] + /// CHECK: <> And [<>,<>] + /// CHECK: <> Add [<>,<>] + /// CHECK: Return [<>] + + /// 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)); + } +} -- 2.11.0