From 9f98025ba5541641cfa9abb7b9cf30332d91fad1 Mon Sep 17 00:00:00 2001 From: Alexandre Rames Date: Fri, 5 Feb 2016 14:00:28 +0000 Subject: [PATCH] Extend De Morgan factorisation to `HBooleanNot`. Change-Id: I81aa92277fa136d675e7ef01be8e4acdbd3d3b7c --- compiler/optimizing/instruction_simplifier.cc | 23 +++-- test/565-checker-doublenegbitwise/src/Main.java | 112 ++++++++++++++++++++++++ 2 files changed, 126 insertions(+), 9 deletions(-) diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc index c1e38633f..fa2f6bb1d 100644 --- a/compiler/optimizing/instruction_simplifier.cc +++ b/compiler/optimizing/instruction_simplifier.cc @@ -176,8 +176,8 @@ bool InstructionSimplifierVisitor::TryDeMorganNegationFactoring(HBinaryOperation // We can apply De Morgan's laws if both inputs are Not's and are only used // by `op`. - if (left->IsNot() && - right->IsNot() && + if (((left->IsNot() && right->IsNot()) || + (left->IsBooleanNot() && right->IsBooleanNot())) && left->HasOnlyOneNonEnvironmentUse() && right->HasOnlyOneNonEnvironmentUse()) { // Replace code looking like @@ -187,8 +187,8 @@ bool InstructionSimplifierVisitor::TryDeMorganNegationFactoring(HBinaryOperation // with // OR or, a, b (respectively AND) // NOT dest, or - HInstruction* src_left = left->AsNot()->GetInput(); - HInstruction* src_right = right->AsNot()->GetInput(); + HInstruction* src_left = left->InputAt(0); + HInstruction* src_right = right->InputAt(0); uint32_t dex_pc = op->GetDexPc(); // Remove the negations on the inputs. @@ -204,7 +204,12 @@ bool InstructionSimplifierVisitor::TryDeMorganNegationFactoring(HBinaryOperation } else { hbin = new (GetGraph()->GetArena()) HAnd(type, src_left, src_right, dex_pc); } - HNot* hnot = new (GetGraph()->GetArena()) HNot(type, hbin, dex_pc); + HInstruction* hnot; + if (left->IsBooleanNot()) { + hnot = new (GetGraph()->GetArena()) HBooleanNot(hbin, dex_pc); + } else { + hnot = new (GetGraph()->GetArena()) HNot(type, hbin, dex_pc); + } op->GetBlock()->InsertInstructionBefore(hbin, op); op->GetBlock()->ReplaceAndRemoveInstructionWith(op, hnot); @@ -1308,8 +1313,8 @@ void InstructionSimplifierVisitor::VisitXor(HXor* instruction) { HInstruction* left = instruction->GetLeft(); HInstruction* right = instruction->GetRight(); - if (left->IsNot() && - right->IsNot() && + if (((left->IsNot() && right->IsNot()) || + (left->IsBooleanNot() && right->IsBooleanNot())) && left->HasOnlyOneNonEnvironmentUse() && right->HasOnlyOneNonEnvironmentUse()) { // Replace code looking like @@ -1318,8 +1323,8 @@ void InstructionSimplifierVisitor::VisitXor(HXor* instruction) { // XOR dst, nota, notb // with // XOR dst, a, b - instruction->ReplaceInput(left->AsNot()->GetInput(), 0); - instruction->ReplaceInput(right->AsNot()->GetInput(), 1); + instruction->ReplaceInput(left->InputAt(0), 0); + instruction->ReplaceInput(right->InputAt(0), 1); left->GetBlock()->RemoveInstruction(left); right->GetBlock()->RemoveInstruction(right); RecordSimplification(); diff --git a/test/565-checker-doublenegbitwise/src/Main.java b/test/565-checker-doublenegbitwise/src/Main.java index c51eda8a6..41af97b3b 100644 --- a/test/565-checker-doublenegbitwise/src/Main.java +++ b/test/565-checker-doublenegbitwise/src/Main.java @@ -56,6 +56,8 @@ public class Main { /// CHECK-START: int Main.$opt$noinline$andToOr(int, int) instruction_simplifier (after) /// CHECK: Not /// CHECK-NOT: Not + + /// CHECK-START: int Main.$opt$noinline$andToOr(int, int) instruction_simplifier (after) /// CHECK-NOT: And public static int $opt$noinline$andToOr(int a, int b) { @@ -64,6 +66,43 @@ public class Main { } /** + * Test transformation of Not/Not/And into Or/Not for boolean negations. + * Note that the graph before this instruction simplification pass does not + * contain `HBooleanNot` instructions. This is because this transformation + * follows the optimization of `HSelect` to `HBooleanNot` occurring in the + * same pass. + */ + + /// CHECK-START: boolean Main.$opt$noinline$booleanAndToOr(boolean, boolean) instruction_simplifier_after_bce (before) + /// CHECK: <> ParameterValue + /// CHECK: <> ParameterValue + /// CHECK-DAG: <> IntConstant 0 + /// CHECK-DAG: <> IntConstant 1 + /// CHECK: <> Select [<>,<>,<>] + /// CHECK: <> Select [<>,<>,<>] + /// CHECK: <> And [<>,<>] + /// CHECK: Return [<>] + + /// CHECK-START: boolean Main.$opt$noinline$booleanAndToOr(boolean, boolean) instruction_simplifier_after_bce (after) + /// CHECK: <> ParameterValue + /// CHECK: <> ParameterValue + /// CHECK: <> Or [<>,<>] + /// CHECK: <> BooleanNot [<>] + /// CHECK: Return [<>] + + /// CHECK-START: boolean Main.$opt$noinline$booleanAndToOr(boolean, boolean) instruction_simplifier_after_bce (after) + /// CHECK: BooleanNot + /// CHECK-NOT: BooleanNot + + /// CHECK-START: boolean Main.$opt$noinline$booleanAndToOr(boolean, boolean) instruction_simplifier_after_bce (after) + /// CHECK-NOT: And + + public static boolean $opt$noinline$booleanAndToOr(boolean a, boolean b) { + if (doThrow) throw new Error(); + return !a & !b; + } + + /** * Test transformation of Not/Not/Or into And/Not. */ @@ -88,6 +127,8 @@ public class Main { /// CHECK-START: long Main.$opt$noinline$orToAnd(long, long) instruction_simplifier (after) /// CHECK: Not /// CHECK-NOT: Not + + /// CHECK-START: long Main.$opt$noinline$orToAnd(long, long) instruction_simplifier (after) /// CHECK-NOT: Or public static long $opt$noinline$orToAnd(long a, long b) { @@ -96,6 +137,43 @@ public class Main { } /** + * Test transformation of Not/Not/Or into Or/And for boolean negations. + * Note that the graph before this instruction simplification pass does not + * contain `HBooleanNot` instructions. This is because this transformation + * follows the optimization of `HSelect` to `HBooleanNot` occurring in the + * same pass. + */ + + /// CHECK-START: boolean Main.$opt$noinline$booleanOrToAnd(boolean, boolean) instruction_simplifier_after_bce (before) + /// CHECK: <> ParameterValue + /// CHECK: <> ParameterValue + /// CHECK-DAG: <> IntConstant 0 + /// CHECK-DAG: <> IntConstant 1 + /// CHECK: <> Select [<>,<>,<>] + /// CHECK: <> Select [<>,<>,<>] + /// CHECK: <> Or [<>,<>] + /// CHECK: Return [<>] + + /// CHECK-START: boolean Main.$opt$noinline$booleanOrToAnd(boolean, boolean) instruction_simplifier_after_bce (after) + /// CHECK: <> ParameterValue + /// CHECK: <> ParameterValue + /// CHECK: <> And [<>,<>] + /// CHECK: <> BooleanNot [<>] + /// CHECK: Return [<>] + + /// CHECK-START: boolean Main.$opt$noinline$booleanOrToAnd(boolean, boolean) instruction_simplifier_after_bce (after) + /// CHECK: BooleanNot + /// CHECK-NOT: BooleanNot + + /// CHECK-START: boolean Main.$opt$noinline$booleanOrToAnd(boolean, boolean) instruction_simplifier_after_bce (after) + /// CHECK-NOT: Or + + public static boolean $opt$noinline$booleanOrToAnd(boolean a, boolean 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 @@ -127,6 +205,8 @@ public class Main { /// CHECK-START: int Main.$opt$noinline$regressInputsAway(int, int) instruction_simplifier (after) /// CHECK: Not /// CHECK-NOT: Not + + /// CHECK-START: int Main.$opt$noinline$regressInputsAway(int, int) instruction_simplifier (after) /// CHECK-NOT: Or public static int $opt$noinline$regressInputsAway(int a, int b) { @@ -167,6 +247,38 @@ public class Main { } /** + * Test transformation of Not/Not/Xor into Xor for boolean negations. + * Note that the graph before this instruction simplification pass does not + * contain `HBooleanNot` instructions. This is because this transformation + * follows the optimization of `HSelect` to `HBooleanNot` occurring in the + * same pass. + */ + + /// CHECK-START: boolean Main.$opt$noinline$booleanNotXorToXor(boolean, boolean) instruction_simplifier_after_bce (before) + /// CHECK: <> ParameterValue + /// CHECK: <> ParameterValue + /// CHECK-DAG: <> IntConstant 0 + /// CHECK-DAG: <> IntConstant 1 + /// CHECK: <> Select [<>,<>,<>] + /// CHECK: <> Select [<>,<>,<>] + /// CHECK: <> Xor [<>,<>] + /// CHECK: Return [<>] + + /// CHECK-START: boolean Main.$opt$noinline$booleanNotXorToXor(boolean, boolean) instruction_simplifier_after_bce (after) + /// CHECK: <> ParameterValue + /// CHECK: <> ParameterValue + /// CHECK: <> Xor [<>,<>] + /// CHECK: Return [<>] + + /// CHECK-START: boolean Main.$opt$noinline$booleanNotXorToXor(boolean, boolean) instruction_simplifier_after_bce (after) + /// CHECK-NOT: BooleanNot + + public static boolean $opt$noinline$booleanNotXorToXor(boolean a, boolean b) { + if (doThrow) throw new Error(); + return !a ^ !b; + } + + /** * Check that no transformation is done when one Not has multiple uses. */ -- 2.11.0