[optimizing compiler] Add division for floats and doubles

backends: x86, x86_64, arm.

Also:
- ordered instructions based on their name.
- add missing kNoOutputOverlap to add/sub/mul.

Change-Id: Ie47cde3b15ac74e7a1660c67a2eed1d7871f0ad0

10 files changed, 350 insertions, 25 deletions

diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index cc9c6c1..f80ebdb 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -828,6 +828,16 @@ bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, uint32
       break;
     }
 
+    case Instruction::DIV_FLOAT: {
+      Binop_23x<HDiv>(instruction, Primitive::kPrimFloat);
+      break;
+    }
+
+    case Instruction::DIV_DOUBLE: {
+      Binop_23x<HDiv>(instruction, Primitive::kPrimDouble);
+      break;
+    }
+
     case Instruction::ADD_LONG_2ADDR: {
       Binop_12x<HAdd>(instruction, Primitive::kPrimLong);
       break;
@@ -883,6 +893,16 @@ bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, uint32
       break;
     }
 
+    case Instruction::DIV_FLOAT_2ADDR: {
+      Binop_12x<HDiv>(instruction, Primitive::kPrimFloat);
+      break;
+    }
+
+    case Instruction::DIV_DOUBLE_2ADDR: {
+      Binop_12x<HDiv>(instruction, Primitive::kPrimDouble);
+      break;
+    }
+
     case Instruction::ADD_INT_LIT16: {
       Binop_22s<HAdd>(instruction, false);
       break;
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 7adf2cc..a5d4c43 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -1128,7 +1128,7 @@ void LocationsBuilderARM::VisitAdd(HAdd* add) {
     case Primitive::kPrimDouble: {
       locations->SetInAt(0, Location::RequiresFpuRegister());
       locations->SetInAt(1, Location::RequiresFpuRegister());
-      locations->SetOut(Location::RequiresFpuRegister());
+      locations->SetOut(Location::RequiresFpuRegister(), Location::kNoOutputOverlap);
       break;
     }
 
@@ -1193,7 +1193,7 @@ void LocationsBuilderARM::VisitSub(HSub* sub) {
     case Primitive::kPrimDouble: {
       locations->SetInAt(0, Location::RequiresFpuRegister());
       locations->SetInAt(1, Location::RequiresFpuRegister());
-      locations->SetOut(Location::RequiresFpuRegister());
+      locations->SetOut(Location::RequiresFpuRegister(), Location::kNoOutputOverlap);
       break;
     }
     default:
@@ -1262,7 +1262,7 @@ void LocationsBuilderARM::VisitMul(HMul* mul) {
     case Primitive::kPrimDouble: {
       locations->SetInAt(0, Location::RequiresFpuRegister());
       locations->SetInAt(1, Location::RequiresFpuRegister());
-      locations->SetOut(Location::RequiresFpuRegister());
+      locations->SetOut(Location::RequiresFpuRegister(), Location::kNoOutputOverlap);
       break;
     }
 
@@ -1329,6 +1329,58 @@ void InstructionCodeGeneratorARM::VisitMul(HMul* mul) {
   }
 }
 
+void LocationsBuilderARM::VisitDiv(HDiv* div) {
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(div, LocationSummary::kNoCall);
+  switch (div->GetResultType()) {
+    case Primitive::kPrimInt:
+    case Primitive::kPrimLong: {
+      LOG(FATAL) << "Not implemented div type" << div->GetResultType();
+      break;
+    }
+    case Primitive::kPrimFloat:
+    case Primitive::kPrimDouble: {
+      locations->SetInAt(0, Location::RequiresFpuRegister());
+      locations->SetInAt(1, Location::RequiresFpuRegister());
+      locations->SetOut(Location::RequiresFpuRegister(), Location::kNoOutputOverlap);
+      break;
+    }
+
+    default:
+      LOG(FATAL) << "Unexpected div type " << div->GetResultType();
+  }
+}
+
+void InstructionCodeGeneratorARM::VisitDiv(HDiv* div) {
+  LocationSummary* locations = div->GetLocations();
+  Location out = locations->Out();
+  Location first = locations->InAt(0);
+  Location second = locations->InAt(1);
+
+  switch (div->GetResultType()) {
+    case Primitive::kPrimInt:
+    case Primitive::kPrimLong: {
+      LOG(FATAL) << "Not implemented div type" << div->GetResultType();
+      break;
+    }
+
+    case Primitive::kPrimFloat: {
+      __ vdivs(out.As<SRegister>(), first.As<SRegister>(), second.As<SRegister>());
+      break;
+    }
+
+    case Primitive::kPrimDouble: {
+      __ vdivd(FromLowSToD(out.AsFpuRegisterPairLow<SRegister>()),
+               FromLowSToD(first.AsFpuRegisterPairLow<SRegister>()),
+               FromLowSToD(second.AsFpuRegisterPairLow<SRegister>()));
+      break;
+    }
+
+    default:
+      LOG(FATAL) << "Unexpected div type " << div->GetResultType();
+  }
+}
+
 void LocationsBuilderARM::VisitNewInstance(HNewInstance* instruction) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kCall);
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index 79528ac..f9aa44b 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -535,6 +535,7 @@ InstructionCodeGeneratorARM64::InstructionCodeGeneratorARM64(HGraph* graph,
   M(ArrayGet)                                              \
   M(ArraySet)                                              \
   M(DoubleConstant)                                        \
+  M(Div)                                                   \
   M(FloatConstant)                                         \
   M(Mul)                                                   \
   M(Neg)                                                   \
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 99fa11d..495ff8b 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -1293,6 +1293,56 @@ void InstructionCodeGeneratorX86::VisitMul(HMul* mul) {
   }
 }
 
+void LocationsBuilderX86::VisitDiv(HDiv* div) {
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(div, LocationSummary::kNoCall);
+  switch (div->GetResultType()) {
+    case Primitive::kPrimInt:
+    case Primitive::kPrimLong: {
+      LOG(FATAL) << "Not implemented div type" << div->GetResultType();
+      break;
+    }
+    case Primitive::kPrimFloat:
+    case Primitive::kPrimDouble: {
+      locations->SetInAt(0, Location::RequiresFpuRegister());
+      locations->SetInAt(1, Location::RequiresFpuRegister());
+      locations->SetOut(Location::SameAsFirstInput());
+      break;
+    }
+
+    default:
+      LOG(FATAL) << "Unexpected div type " << div->GetResultType();
+  }
+}
+
+void InstructionCodeGeneratorX86::VisitDiv(HDiv* div) {
+  LocationSummary* locations = div->GetLocations();
+  Location first = locations->InAt(0);
+  Location second = locations->InAt(1);
+  DCHECK(first.Equals(locations->Out()));
+
+  switch (div->GetResultType()) {
+    case Primitive::kPrimInt:
+    case Primitive::kPrimLong: {
+      LOG(FATAL) << "Not implemented div type" << div->GetResultType();
+      break;
+    }
+
+    case Primitive::kPrimFloat: {
+      __ divss(first.As<XmmRegister>(), second.As<XmmRegister>());
+      break;
+    }
+
+    case Primitive::kPrimDouble: {
+      __ divsd(first.As<XmmRegister>(), second.As<XmmRegister>());
+      break;
+    }
+
+    default:
+      LOG(FATAL) << "Unexpected div type " << div->GetResultType();
+  }
+}
+
 void LocationsBuilderX86::VisitNewInstance(HNewInstance* instruction) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kCall);
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 163156a..4d11a24 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -1218,6 +1218,56 @@ void InstructionCodeGeneratorX86_64::VisitMul(HMul* mul) {
   }
 }
 
+void LocationsBuilderX86_64::VisitDiv(HDiv* div) {
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(div, LocationSummary::kNoCall);
+  switch (div->GetResultType()) {
+    case Primitive::kPrimInt:
+    case Primitive::kPrimLong: {
+      LOG(FATAL) << "Not implemented div type" << div->GetResultType();
+      break;
+    }
+    case Primitive::kPrimFloat:
+    case Primitive::kPrimDouble: {
+      locations->SetInAt(0, Location::RequiresFpuRegister());
+      locations->SetInAt(1, Location::RequiresFpuRegister());
+      locations->SetOut(Location::SameAsFirstInput());
+      break;
+    }
+
+    default:
+      LOG(FATAL) << "Unexpected div type " << div->GetResultType();
+  }
+}
+
+void InstructionCodeGeneratorX86_64::VisitDiv(HDiv* div) {
+  LocationSummary* locations = div->GetLocations();
+  Location first = locations->InAt(0);
+  Location second = locations->InAt(1);
+  DCHECK(first.Equals(locations->Out()));
+
+  switch (div->GetResultType()) {
+    case Primitive::kPrimInt:
+    case Primitive::kPrimLong: {
+      LOG(FATAL) << "Not implemented div type" << div->GetResultType();
+      break;
+    }
+
+    case Primitive::kPrimFloat: {
+      __ divss(first.As<XmmRegister>(), second.As<XmmRegister>());
+      break;
+    }
+
+    case Primitive::kPrimDouble: {
+      __ divsd(first.As<XmmRegister>(), second.As<XmmRegister>());
+      break;
+    }
+
+    default:
+      LOG(FATAL) << "Unexpected div type " << div->GetResultType();
+  }
+}
+
 void LocationsBuilderX86_64::VisitNewInstance(HNewInstance* instruction) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kCall);
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 7adb840..f530708 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -468,46 +468,47 @@ class HBasicBlock : public ArenaObject {
 
 #define FOR_EACH_CONCRETE_INSTRUCTION(M)                                \
   M(Add, BinaryOperation)                                               \
+  M(ArrayGet, Instruction)                                              \
+  M(ArrayLength, Instruction)                                           \
+  M(ArraySet, Instruction)                                              \
+  M(BoundsCheck, Instruction)                                           \
+  M(Compare, BinaryOperation)                                           \
   M(Condition, BinaryOperation)                                         \
+  M(Div, BinaryOperation)                                               \
+  M(DoubleConstant, Constant)                                           \
   M(Equal, Condition)                                                   \
-  M(NotEqual, Condition)                                                \
-  M(LessThan, Condition)                                                \
-  M(LessThanOrEqual, Condition)                                         \
-  M(GreaterThan, Condition)                                             \
-  M(GreaterThanOrEqual, Condition)                                      \
   M(Exit, Instruction)                                                  \
+  M(FloatConstant, Constant)                                            \
   M(Goto, Instruction)                                                  \
+  M(GreaterThan, Condition)                                             \
+  M(GreaterThanOrEqual, Condition)                                      \
   M(If, Instruction)                                                    \
+  M(InstanceFieldGet, Instruction)                                      \
+  M(InstanceFieldSet, Instruction)                                      \
   M(IntConstant, Constant)                                              \
   M(InvokeStatic, Invoke)                                               \
   M(InvokeVirtual, Invoke)                                              \
+  M(LessThan, Condition)                                                \
+  M(LessThanOrEqual, Condition)                                         \
   M(LoadLocal, Instruction)                                             \
   M(Local, Instruction)                                                 \
   M(LongConstant, Constant)                                             \
+  M(Mul, BinaryOperation)                                               \
+  M(Neg, UnaryOperation)                                                \
+  M(NewArray, Instruction)                                              \
   M(NewInstance, Instruction)                                           \
   M(Not, UnaryOperation)                                                \
-  M(ParameterValue, Instruction)                                        \
+  M(NotEqual, Condition)                                                \
+  M(NullCheck, Instruction)                                             \
   M(ParallelMove, Instruction)                                          \
+  M(ParameterValue, Instruction)                                        \
   M(Phi, Instruction)                                                   \
   M(Return, Instruction)                                                \
   M(ReturnVoid, Instruction)                                            \
   M(StoreLocal, Instruction)                                            \
   M(Sub, BinaryOperation)                                               \
-  M(Compare, BinaryOperation)                                           \
-  M(InstanceFieldGet, Instruction)                                      \
-  M(InstanceFieldSet, Instruction)                                      \
-  M(ArrayGet, Instruction)                                              \
-  M(ArraySet, Instruction)                                              \
-  M(ArrayLength, Instruction)                                           \
-  M(BoundsCheck, Instruction)                                           \
-  M(NullCheck, Instruction)                                             \
-  M(Temporary, Instruction)                                             \
   M(SuspendCheck, Instruction)                                          \
-  M(Mul, BinaryOperation)                                               \
-  M(Neg, UnaryOperation)                                                \
-  M(FloatConstant, Constant)                                            \
-  M(DoubleConstant, Constant)                                           \
-  M(NewArray, Instruction)                                              \
+  M(Temporary, Instruction)                                             \
 
 #define FOR_EACH_INSTRUCTION(M)                                         \
   FOR_EACH_CONCRETE_INSTRUCTION(M)                                      \
@@ -1658,8 +1659,6 @@ class HSub : public HBinaryOperation {
   HSub(Primitive::Type result_type, HInstruction* left, HInstruction* right)
       : HBinaryOperation(result_type, left, right) {}
 
-  virtual bool IsCommutative() { return false; }
-
   virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
     return x - y;
   }
@@ -1689,6 +1688,20 @@ class HMul : public HBinaryOperation {
   DISALLOW_COPY_AND_ASSIGN(HMul);
 };
 
+class HDiv : public HBinaryOperation {
+ public:
+  HDiv(Primitive::Type result_type, HInstruction* left, HInstruction* right)
+      : HBinaryOperation(result_type, left, right) {}
+
+  virtual int32_t Evaluate(int32_t x, int32_t y) const { return x / y; }
+  virtual int64_t Evaluate(int64_t x, int64_t y) const { return x / y; }
+
+  DECLARE_INSTRUCTION(Div);
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HDiv);
+};
+
 // The value of a parameter in this method. Its location depends on
 // the calling convention.
 class HParameterValue : public HExpression<0> {
diff --git a/test/417-optimizing-arith-div/expected.txt b/test/417-optimizing-arith-div/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/417-optimizing-arith-div/expected.txt
diff --git a/test/417-optimizing-arith-div/info.txt b/test/417-optimizing-arith-div/info.txt
new file mode 100644
index 0000000..1374b0f
--- /dev/null
+++ b/test/417-optimizing-arith-div/info.txt
@@ -0,0 +1 @@
+Tests for division operation.
diff --git a/test/417-optimizing-arith-div/src/Main.java b/test/417-optimizing-arith-div/src/Main.java
new file mode 100644
index 0000000..535cafb
--- /dev/null
+++ b/test/417-optimizing-arith-div/src/Main.java
@@ -0,0 +1,137 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+// Note that $opt$ is a marker for the optimizing compiler to ensure
+// it does compile the method.
+public class Main {
+
+  public static void expectEquals(float expected, float result) {
+    if (expected != result) {
+      throw new Error("Expected: " + expected + ", found: " + result);
+    }
+  }
+
+  public static void expectEquals(double expected, double result) {
+    if (expected != result) {
+      throw new Error("Expected: " + expected + ", found: " + result);
+    }
+  }
+
+  public static void expectApproxEquals(float a, float b) {
+    float maxDelta = 0.00001F;
+    boolean aproxEquals = (a > b) ? ((a - b) < maxDelta) : ((b - a) < maxDelta);
+    if (!aproxEquals) {
+      throw new Error("Expected: " + a + ", found: " + b
+          + ", with delta: " + maxDelta + " " + (a - b));
+    }
+  }
+
+  public static void expectApproxEquals(double a, double b) {
+    double maxDelta = 0.00001D;
+    boolean aproxEquals = (a > b) ? ((a - b) < maxDelta) : ((b - a) < maxDelta);
+    if (!aproxEquals) {
+      throw new Error("Expected: " + a + ", found: "
+          + b + ", with delta: " + maxDelta + " " + (a - b));
+    }
+  }
+
+  public static void expectNaN(float a) {
+    if (a == a) {
+      throw new Error("Expected NaN: " + a);
+    }
+  }
+
+  public static void expectNaN(double a) {
+    if (a == a) {
+      throw new Error("Expected NaN: " + a);
+    }
+  }
+
+  public static void main(String[] args) {
+    div();
+  }
+
+  public static void div() {
+    divFloat();
+    divDouble();
+  }
+
+  private static void divFloat() {
+    expectApproxEquals(1.6666666F, $opt$Div(5F, 3F));
+    expectApproxEquals(0F, $opt$Div(0F, 3F));
+    expectApproxEquals(-0.3333333F, $opt$Div(1F, -3F));
+    expectApproxEquals(4F, $opt$Div(-12F, -3F));
+    expectApproxEquals(0.5, $opt$Div(0.1F, 0.2F));
+    expectApproxEquals(-2.5F, $opt$Div(-0.5F, 0.2F));
+
+    expectEquals(0F, $opt$Div(0F, Float.POSITIVE_INFINITY));
+    expectEquals(0F, $opt$Div(11F, Float.POSITIVE_INFINITY));
+    expectEquals(0F, $opt$Div(0F, Float.NEGATIVE_INFINITY));
+    expectEquals(0F, $opt$Div(11F, Float.NEGATIVE_INFINITY));
+
+    expectNaN($opt$Div(0F, 0F));
+    expectNaN($opt$Div(Float.NaN, 11F));
+    expectNaN($opt$Div(-11F, Float.NaN));
+    expectNaN($opt$Div(Float.NEGATIVE_INFINITY, Float.NEGATIVE_INFINITY));
+    expectNaN($opt$Div(Float.NEGATIVE_INFINITY, Float.POSITIVE_INFINITY));
+    expectNaN($opt$Div(Float.POSITIVE_INFINITY, Float.NEGATIVE_INFINITY));
+    expectNaN($opt$Div(Float.POSITIVE_INFINITY, Float.POSITIVE_INFINITY));
+    expectNaN($opt$Div(Float.NaN, Float.NEGATIVE_INFINITY));
+    expectNaN($opt$Div(Float.POSITIVE_INFINITY, Float.NaN));
+
+    expectEquals(Float.POSITIVE_INFINITY, $opt$Div(3F, 0F));
+    expectEquals(Float.NEGATIVE_INFINITY, $opt$Div(-3F, 0F));
+    expectEquals(Float.POSITIVE_INFINITY, $opt$Div(Float.MAX_VALUE, Float.MIN_VALUE));
+    expectEquals(Float.NEGATIVE_INFINITY, $opt$Div(-Float.MAX_VALUE, Float.MIN_VALUE));
+  }
+
+  private static void divDouble() {
+    expectApproxEquals(1.6666666D, $opt$Div(5D, 3D));
+    expectApproxEquals(0D, $opt$Div(0D, 3D));
+    expectApproxEquals(-0.3333333D, $opt$Div(1D, -3D));
+    expectApproxEquals(4D, $opt$Div(-12D, -3D));
+    expectApproxEquals(0.5, $opt$Div(0.1D, 0.2D));
+    expectApproxEquals(-2.5D, $opt$Div(-0.5D, 0.2D));
+
+    expectEquals(0D, $opt$Div(0D, Float.POSITIVE_INFINITY));
+    expectEquals(0D, $opt$Div(11D, Float.POSITIVE_INFINITY));
+    expectEquals(0D, $opt$Div(0D, Float.NEGATIVE_INFINITY));
+    expectEquals(0D, $opt$Div(11D, Float.NEGATIVE_INFINITY));
+
+    expectNaN($opt$Div(0D, 0D));
+    expectNaN($opt$Div(Float.NaN, 11D));
+    expectNaN($opt$Div(-11D, Float.NaN));
+    expectNaN($opt$Div(Float.NEGATIVE_INFINITY, Float.NEGATIVE_INFINITY));
+    expectNaN($opt$Div(Float.NEGATIVE_INFINITY, Float.POSITIVE_INFINITY));
+    expectNaN($opt$Div(Float.POSITIVE_INFINITY, Float.NEGATIVE_INFINITY));
+    expectNaN($opt$Div(Float.POSITIVE_INFINITY, Float.POSITIVE_INFINITY));
+    expectNaN($opt$Div(Float.NaN, Float.NEGATIVE_INFINITY));
+    expectNaN($opt$Div(Float.POSITIVE_INFINITY, Float.NaN));
+
+    expectEquals(Float.POSITIVE_INFINITY, $opt$Div(3D, 0D));
+    expectEquals(Float.NEGATIVE_INFINITY, $opt$Div(-3D, 0D));
+    expectEquals(Float.POSITIVE_INFINITY, $opt$Div(Float.MAX_VALUE, Float.MIN_VALUE));
+    expectEquals(Float.NEGATIVE_INFINITY, $opt$Div(-Float.MAX_VALUE, Float.MIN_VALUE));
+  }
+
+  static float $opt$Div(float a, float b) {
+    return a / b;
+  }
+
+  static double $opt$Div(double a, double b) {
+    return a / b;
+  }
+}
diff --git a/test/Android.run-test.mk b/test/Android.run-test.mk
index 2de4d5c..7eba4af 100644
--- a/test/Android.run-test.mk
+++ b/test/Android.run-test.mk
@@ -325,6 +325,7 @@ TEST_ART_BROKEN_OPTIMIZING_ARM64_RUN_TESTS := \
   413-regalloc-regression \
   414-optimizing-arith-sub \
   415-optimizing-arith-neg \
+  417-optimizing-arith-div \
   700-LoadArgRegs \
   800-smali