ART: Implement HBooleanNot instruction

Optimizations simplifying operations on boolean values (boolean
simplifier, instruction simplifier) can benefit from having a special
HInstruction for negating booleans in order to perform more transforms
and produce faster machine code.

This patch implements HBooleanNot as 'x xor 1', assuming that booleans
are 1-bit integers and allowing for a single-instruction negation on
all supported platforms.

Change-Id: I33a2649c1821255b18a86ca68ed16416063c739f

10 files changed, 102 insertions, 2 deletions

diff --git a/compiler/optimizing/boolean_simplifier.cc b/compiler/optimizing/boolean_simplifier.cc
index be432c5a20..06328f2490 100644
--- a/compiler/optimizing/boolean_simplifier.cc
+++ b/compiler/optimizing/boolean_simplifier.cc
@@ -73,8 +73,8 @@ static HInstruction* GetOppositeCondition(HInstruction* cond) {
     }
   } else {
     // General case when 'cond' is another instruction of type boolean.
-    // Negate with 'cond == 0'.
-    return new (allocator) HEqual(cond, graph->GetIntConstant(0));
+    DCHECK_EQ(cond->GetType(), Primitive::Type::kPrimBoolean);
+    return new (allocator) HBooleanNot(cond);
   }
 }
 
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 332c99ae64..72b07cd9e8 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -2657,6 +2657,21 @@ void InstructionCodeGeneratorARM::VisitNot(HNot* not_) {
   }
 }
 
+void LocationsBuilderARM::VisitBooleanNot(HBooleanNot* bool_not) {
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(bool_not, LocationSummary::kNoCall);
+  locations->SetInAt(0, Location::RequiresRegister());
+  locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
+}
+
+void InstructionCodeGeneratorARM::VisitBooleanNot(HBooleanNot* bool_not) {
+  DCHECK_EQ(bool_not->InputAt(0)->GetType(), Primitive::kPrimBoolean);
+  LocationSummary* locations = bool_not->GetLocations();
+  Location out = locations->Out();
+  Location in = locations->InAt(0);
+  __ eor(out.AsRegister<Register>(), in.AsRegister<Register>(), ShifterOperand(1));
+}
+
 void LocationsBuilderARM::VisitCompare(HCompare* compare) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(compare, LocationSummary::kNoCall);
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index a5ddd6ba82..7dfb5952eb 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -2279,6 +2279,17 @@ void InstructionCodeGeneratorARM64::VisitNot(HNot* instruction) {
   }
 }
 
+void LocationsBuilderARM64::VisitBooleanNot(HBooleanNot* instruction) {
+  LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction);
+  locations->SetInAt(0, Location::RequiresRegister());
+  locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
+}
+
+void InstructionCodeGeneratorARM64::VisitBooleanNot(HBooleanNot* instruction) {
+  DCHECK_EQ(instruction->InputAt(0)->GetType(), Primitive::kPrimBoolean);
+  __ Eor(OutputRegister(instruction), InputRegisterAt(instruction, 0), vixl::Operand(1));
+}
+
 void LocationsBuilderARM64::VisitNullCheck(HNullCheck* instruction) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall);
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 38f9ef8efe..79c00ba635 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -2915,6 +2915,22 @@ void InstructionCodeGeneratorX86::VisitNot(HNot* not_) {
   }
 }
 
+void LocationsBuilderX86::VisitBooleanNot(HBooleanNot* bool_not) {
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(bool_not, LocationSummary::kNoCall);
+  locations->SetInAt(0, Location::RequiresRegister());
+  locations->SetOut(Location::SameAsFirstInput());
+}
+
+void InstructionCodeGeneratorX86::VisitBooleanNot(HBooleanNot* bool_not) {
+  DCHECK_EQ(bool_not->InputAt(0)->GetType(), Primitive::kPrimBoolean);
+  LocationSummary* locations = bool_not->GetLocations();
+  Location in = locations->InAt(0);
+  Location out = locations->Out();
+  DCHECK(in.Equals(out));
+  __ xorl(out.AsRegister<Register>(), Immediate(1));
+}
+
 void LocationsBuilderX86::VisitCompare(HCompare* compare) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(compare, LocationSummary::kNoCall);
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 7a928d4d7d..0dd44239ef 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -2974,6 +2974,22 @@ void InstructionCodeGeneratorX86_64::VisitNot(HNot* not_) {
   }
 }
 
+void LocationsBuilderX86_64::VisitBooleanNot(HBooleanNot* bool_not) {
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(bool_not, LocationSummary::kNoCall);
+  locations->SetInAt(0, Location::RequiresRegister());
+  locations->SetOut(Location::SameAsFirstInput());
+}
+
+void InstructionCodeGeneratorX86_64::VisitBooleanNot(HBooleanNot* bool_not) {
+  DCHECK_EQ(bool_not->InputAt(0)->GetType(), Primitive::kPrimBoolean);
+  LocationSummary* locations = bool_not->GetLocations();
+  DCHECK_EQ(locations->InAt(0).AsRegister<CpuRegister>().AsRegister(),
+            locations->Out().AsRegister<CpuRegister>().AsRegister());
+  Location out = locations->Out();
+  __ xorl(out.AsRegister<CpuRegister>(), Immediate(1));
+}
+
 void LocationsBuilderX86_64::VisitPhi(HPhi* instruction) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall);
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 5f50494482..e2eafe5565 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -676,6 +676,7 @@ class HLoopInformationOutwardIterator : public ValueObject {
   M(ArrayGet, Instruction)                                              \
   M(ArrayLength, Instruction)                                           \
   M(ArraySet, Instruction)                                              \
+  M(BooleanNot, UnaryOperation)                                         \
   M(BoundsCheck, Instruction)                                           \
   M(BoundType, Instruction)                                             \
   M(CheckCast, Instruction)                                             \
@@ -2643,6 +2644,33 @@ class HNot : public HUnaryOperation {
   DISALLOW_COPY_AND_ASSIGN(HNot);
 };
 
+class HBooleanNot : public HUnaryOperation {
+ public:
+  explicit HBooleanNot(HInstruction* input)
+      : HUnaryOperation(Primitive::Type::kPrimBoolean, input) {}
+
+  bool CanBeMoved() const OVERRIDE { return true; }
+  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
+    UNUSED(other);
+    return true;
+  }
+
+  int32_t Evaluate(int32_t x) const OVERRIDE {
+    DCHECK(IsUint<1>(x));
+    return !x;
+  }
+
+  int64_t Evaluate(int64_t x ATTRIBUTE_UNUSED) const OVERRIDE {
+    LOG(FATAL) << DebugName() << " cannot be used with 64-bit values";
+    UNREACHABLE();
+  }
+
+  DECLARE_INSTRUCTION(BooleanNot);
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HBooleanNot);
+};
+
 class HTypeConversion : public HExpression<1> {
  public:
   // Instantiate a type conversion of `input` to `result_type`.
diff --git a/test/468-bool-simplifier-regression/expected.txt b/test/468-checker-bool-simplifier-regression/expected.txt
index e69de29bb2..e69de29bb2 100644
--- a/test/468-bool-simplifier-regression/expected.txt
+++ b/test/468-checker-bool-simplifier-regression/expected.txt
diff --git a/test/468-bool-simplifier-regression/info.txt b/test/468-checker-bool-simplifier-regression/info.txt
index 0a465846b1..0a465846b1 100644
--- a/test/468-bool-simplifier-regression/info.txt
+++ b/test/468-checker-bool-simplifier-regression/info.txt
diff --git a/test/468-bool-simplifier-regression/smali/TestCase.smali b/test/468-checker-bool-simplifier-regression/smali/TestCase.smali
index f36304d333..f36304d333 100644
--- a/test/468-bool-simplifier-regression/smali/TestCase.smali
+++ b/test/468-checker-bool-simplifier-regression/smali/TestCase.smali
diff --git a/test/468-bool-simplifier-regression/src/Main.java b/test/468-checker-bool-simplifier-regression/src/Main.java
index 1dd27c9287..65f20b3427 100644
--- a/test/468-bool-simplifier-regression/src/Main.java
+++ b/test/468-checker-bool-simplifier-regression/src/Main.java
@@ -17,6 +17,20 @@
 import java.lang.reflect.*;
 
 public class Main {
+  
+  // CHECK-START: boolean TestCase.testCase() boolean_simplifier (before)
+  // CHECK-DAG:     [[Const0:i\d+]]   IntConstant 0
+  // CHECK-DAG:     [[Const1:i\d+]]   IntConstant 1
+  // CHECK-DAG:     [[Value:z\d+]]    StaticFieldGet
+  // CHECK-DAG:                       If [ [[Value]] ]
+  // CHECK-DAG:     [[Phi:i\d+]]      Phi [ [[Const1]] [[Const0]] ]
+  // CHECK-DAG:                       Return [ [[Phi]] ]
+
+  // CHECK-START: boolean TestCase.testCase() boolean_simplifier (after)
+  // CHECK-DAG:     [[Value:z\d+]]    StaticFieldGet
+  // CHECK-DAG:     [[Not:z\d+]]      BooleanNot [ [[Value]] ]
+  // CHECK-DAG:                       Return [ [[Not]] ]
+  
   public static boolean runTest(boolean input) throws Exception {
     Class<?> c = Class.forName("TestCase");
     Method m = c.getMethod("testCase");