Add conditional move support to x86 and allow GenMinMax to use it

X86 supports conditional moves which is useful for reducing branchiness.
This patch adds support to the x86 backend to generate conditional reg
to reg operations. Both encoder and decoder support was added for cmov.

The x86 version of GenMinMax used for generating inlined version Math.min/max
has been updated to make use of the conditional move support.

Change-Id: I92c5428e40aa8ff88bd3071619957ac3130efae7
Signed-off-by: Razvan A Lupusoru <razvan.a.lupusoru@intel.com>

12 files changed, 167 insertions, 9 deletions

diff --git a/compiler/dex/compiler_enums.h b/compiler/dex/compiler_enums.h
index 5cc906fba9..4650f25a90 100644
--- a/compiler/dex/compiler_enums.h
+++ b/compiler/dex/compiler_enums.h
@@ -161,6 +161,7 @@ std::ostream& operator<<(std::ostream& os, const OpSize& kind);
 
 enum OpKind {
   kOpMov,
+  kOpCmov,
   kOpMvn,
   kOpCmp,
   kOpLsl,
diff --git a/compiler/dex/quick/arm/codegen_arm.h b/compiler/dex/quick/arm/codegen_arm.h
index c04f1d6abf..2bc579a675 100644
--- a/compiler/dex/quick/arm/codegen_arm.h
+++ b/compiler/dex/quick/arm/codegen_arm.h
@@ -153,6 +153,7 @@ class ArmMir2Lir : public Mir2Lir {
     LIR* OpRegImm(OpKind op, int r_dest_src1, int value);
     LIR* OpRegMem(OpKind op, int r_dest, int rBase, int offset);
     LIR* OpRegReg(OpKind op, int r_dest_src1, int r_src2);
+    LIR* OpCondRegReg(OpKind op, ConditionCode cc, int r_dest, int r_src);
     LIR* OpRegRegImm(OpKind op, int r_dest, int r_src1, int value);
     LIR* OpRegRegReg(OpKind op, int r_dest, int r_src1, int r_src2);
     LIR* OpTestSuspend(LIR* target);
diff --git a/compiler/dex/quick/arm/utility_arm.cc b/compiler/dex/quick/arm/utility_arm.cc
index fa05d6c5a8..07fc6c790d 100644
--- a/compiler/dex/quick/arm/utility_arm.cc
+++ b/compiler/dex/quick/arm/utility_arm.cc
@@ -367,6 +367,11 @@ LIR* ArmMir2Lir::OpRegReg(OpKind op, int r_dest_src1, int r_src2) {
   return OpRegRegShift(op, r_dest_src1, r_src2, 0);
 }
 
+LIR* ArmMir2Lir::OpCondRegReg(OpKind op, ConditionCode cc, int r_dest, int r_src) {
+  LOG(FATAL) << "Unexpected use of OpCondRegReg for Arm";
+  return NULL;
+}
+
 LIR* ArmMir2Lir::OpRegRegRegShift(OpKind op, int r_dest, int r_src1,
                                   int r_src2, int shift) {
   ArmOpcode opcode = kThumbBkpt;
diff --git a/compiler/dex/quick/mips/codegen_mips.h b/compiler/dex/quick/mips/codegen_mips.h
index 97dc2b3ad1..a5a14d5c0e 100644
--- a/compiler/dex/quick/mips/codegen_mips.h
+++ b/compiler/dex/quick/mips/codegen_mips.h
@@ -151,6 +151,7 @@ class MipsMir2Lir : public Mir2Lir {
     LIR* OpRegImm(OpKind op, int r_dest_src1, int value);
     LIR* OpRegMem(OpKind op, int r_dest, int rBase, int offset);
     LIR* OpRegReg(OpKind op, int r_dest_src1, int r_src2);
+    LIR* OpCondRegReg(OpKind op, ConditionCode cc, int r_dest, int r_src);
     LIR* OpRegRegImm(OpKind op, int r_dest, int r_src1, int value);
     LIR* OpRegRegReg(OpKind op, int r_dest, int r_src1, int r_src2);
     LIR* OpTestSuspend(LIR* target);
diff --git a/compiler/dex/quick/mips/utility_mips.cc b/compiler/dex/quick/mips/utility_mips.cc
index 65c82c08a0..c5e2b36ef2 100644
--- a/compiler/dex/quick/mips/utility_mips.cc
+++ b/compiler/dex/quick/mips/utility_mips.cc
@@ -325,6 +325,11 @@ LIR* MipsMir2Lir::OpRegReg(OpKind op, int r_dest_src1, int r_src2) {
   return NewLIR2(opcode, r_dest_src1, r_src2);
 }
 
+LIR* MipsMir2Lir::OpCondRegReg(OpKind op, ConditionCode cc, int r_dest, int r_src) {
+  LOG(FATAL) << "Unexpected use of OpCondRegReg for MIPS";
+  return NULL;
+}
+
 LIR* MipsMir2Lir::LoadConstantWide(int r_dest_lo, int r_dest_hi, int64_t value) {
   LIR *res;
   res = LoadConstantNoClobber(r_dest_lo, Low32Bits(value));
diff --git a/compiler/dex/quick/mir_to_lir.h b/compiler/dex/quick/mir_to_lir.h
index 9dc35c6f78..3f7ec1e5f0 100644
--- a/compiler/dex/quick/mir_to_lir.h
+++ b/compiler/dex/quick/mir_to_lir.h
@@ -421,8 +421,26 @@ class Mir2Lir : public Backend {
     RegLocation UpdateLoc(RegLocation loc);
     RegLocation UpdateLocWide(RegLocation loc);
     RegLocation UpdateRawLoc(RegLocation loc);
+
+    /**
+     * @brief Used to load register location into a typed temporary or pair of temporaries.
+     * @see EvalLoc
+     * @param loc The register location to load from.
+     * @param reg_class Type of register needed.
+     * @param update Whether the liveness information should be updated.
+     * @return Returns the properly typed temporary in physical register pairs.
+     */
     RegLocation EvalLocWide(RegLocation loc, int reg_class, bool update);
+
+    /**
+     * @brief Used to load register location into a typed temporary.
+     * @param loc The register location to load from.
+     * @param reg_class Type of register needed.
+     * @param update Whether the liveness information should be updated.
+     * @return Returns the properly typed temporary in physical register.
+     */
     RegLocation EvalLoc(RegLocation loc, int reg_class, bool update);
+
     void CountRefs(RefCounts* core_counts, RefCounts* fp_counts, size_t num_regs);
     void DumpCounts(const RefCounts* arr, int size, const char* msg);
     void DoPromotion();
@@ -541,7 +559,22 @@ class Mir2Lir : public Backend {
                            uint32_t vtable_idx,
                            uintptr_t direct_code, uintptr_t direct_method, InvokeType type,
                            bool skip_this);
+
+    /**
+     * @brief Used to determine the register location of destination.
+     * @details This is needed during generation of inline intrinsics because it finds destination of return,
+     * either the physical register or the target of move-result.
+     * @param info Information about the invoke.
+     * @return Returns the destination location.
+     */
     RegLocation InlineTarget(CallInfo* info);
+
+    /**
+     * @brief Used to determine the wide register location of destination.
+     * @see InlineTarget
+     * @param info Information about the invoke.
+     * @return Returns the destination location.
+     */
     RegLocation InlineTargetWide(CallInfo* info);
 
     bool GenInlinedCharAt(CallInfo* info);
@@ -576,7 +609,20 @@ class Mir2Lir : public Backend {
     void LoadValueDirectWide(RegLocation rl_src, int reg_lo, int reg_hi);
     void LoadValueDirectWideFixed(RegLocation rl_src, int reg_lo, int reg_hi);
     LIR* StoreWordDisp(int rBase, int displacement, int r_src);
+
+    /**
+     * @brief Used to do the final store in the destination as per bytecode semantics.
+     * @param rl_dest The destination dalvik register location.
+     * @param rl_src The source register location. Can be either physical register or dalvik register.
+     */
     void StoreValue(RegLocation rl_dest, RegLocation rl_src);
+
+    /**
+     * @brief Used to do the final store in a wide destination as per bytecode semantics.
+     * @see StoreValue
+     * @param rl_dest The destination dalvik register location.
+     * @param rl_src The source register location. Can be either physical register or dalvik register.
+     */
     void StoreValueWide(RegLocation rl_dest, RegLocation rl_src);
 
     // Shared by all targets - implemented in mir_to_lir.cc.
@@ -663,7 +709,18 @@ class Mir2Lir : public Backend {
     virtual void GenConversion(Instruction::Code opcode, RegLocation rl_dest,
                                RegLocation rl_src) = 0;
     virtual bool GenInlinedCas(CallInfo* info, bool is_long, bool is_object) = 0;
+
+    /**
+     * @brief Used to generate code for intrinsic java\.lang\.Math methods min and max.
+     * @details This is also applicable for java\.lang\.StrictMath since it is a simple algorithm
+     * that applies on integers. The generated code will write the smallest or largest value
+     * directly into the destination register as specified by the invoke information.
+     * @param info Information about the invoke.
+     * @param is_min If true generates code that computes minimum. Otherwise computes maximum.
+     * @return Returns true if successfully generated
+     */
     virtual bool GenInlinedMinMaxInt(CallInfo* info, bool is_min) = 0;
+
     virtual bool GenInlinedSqrt(CallInfo* info) = 0;
     virtual bool GenInlinedPeek(CallInfo* info, OpSize size) = 0;
     virtual bool GenInlinedPoke(CallInfo* info, OpSize size) = 0;
@@ -738,6 +795,17 @@ class Mir2Lir : public Backend {
     virtual LIR* OpRegImm(OpKind op, int r_dest_src1, int value) = 0;
     virtual LIR* OpRegMem(OpKind op, int r_dest, int rBase, int offset) = 0;
     virtual LIR* OpRegReg(OpKind op, int r_dest_src1, int r_src2) = 0;
+
+    /**
+     * @brief Used for generating a conditional register to register operation.
+     * @param op The opcode kind.
+     * @param cc The condition code that when true will perform the opcode.
+     * @param r_dest The destination physical register.
+     * @param r_src The source physical register.
+     * @return Returns the newly created LIR or null in case of creation failure.
+     */
+    virtual LIR* OpCondRegReg(OpKind op, ConditionCode cc, int r_dest, int r_src) = 0;
+
     virtual LIR* OpRegRegImm(OpKind op, int r_dest, int r_src1, int value) = 0;
     virtual LIR* OpRegRegReg(OpKind op, int r_dest, int r_src1, int r_src2) = 0;
     virtual LIR* OpTestSuspend(LIR* target) = 0;
diff --git a/compiler/dex/quick/x86/assemble_x86.cc b/compiler/dex/quick/x86/assemble_x86.cc
index c24f0e33f8..1dcff652ba 100644
--- a/compiler/dex/quick/x86/assemble_x86.cc
+++ b/compiler/dex/quick/x86/assemble_x86.cc
@@ -177,6 +177,8 @@ ENCODING_MAP(Cmp, IS_LOAD, 0, 0,
 
   { kX86Lea32RA, kRegArray, IS_QUIN_OP | REG_DEF0_USE12, { 0, 0, 0x8D, 0, 0, 0, 0, 0 }, "Lea32RA", "!0r,[!1r+!2r<<!3d+!4d]" },
 
+  { kX86Cmov32RRC, kRegRegCond, IS_TERTIARY_OP | REG_DEF0_USE01 | USES_CCODES, {0, 0, 0x0F, 0x40, 0, 0, 0, 0}, "Cmovcc32RR", "!2c !0r,!1r" },
+
 #define SHIFT_ENCODING_MAP(opname, modrm_opcode) \
 { kX86 ## opname ## 8RI, kShiftRegImm,                        IS_BINARY_OP   | REG_DEF0_USE0 |            SETS_CCODES, { 0,    0, 0xC0, 0, 0, modrm_opcode, 0xD1, 1 }, #opname "8RI", "!0r,!1d" }, \
 { kX86 ## opname ## 8MI, kShiftMemImm,   IS_LOAD | IS_STORE | IS_TERTIARY_OP | REG_USE0      |            SETS_CCODES, { 0,    0, 0xC0, 0, 0, modrm_opcode, 0xD1, 1 }, #opname "8MI", "[!0r+!1d],!2d" }, \
@@ -449,6 +451,8 @@ int X86Mir2Lir::GetInsnSize(LIR* lir) {
       return ComputeSize(entry, lir->operands[0], lir->operands[1], false);
     case kArrayCond:  // lir operands - 0: base, 1: index, 2: scale, 3: disp, 4: cond
       return ComputeSize(entry, lir->operands[0], lir->operands[3], true);
+    case kRegRegCond:  // lir operands - 0: reg, 1: reg, 2: cond
+      return ComputeSize(entry, 0, 0, false);
     case kJcc:
       if (lir->opcode == kX86Jcc8) {
         return 2;  // opcode + rel8
@@ -860,6 +864,30 @@ void X86Mir2Lir::EmitRegCond(const X86EncodingMap* entry, uint8_t reg, uint8_t c
   DCHECK_EQ(entry->skeleton.immediate_bytes, 0);
 }
 
+void X86Mir2Lir::EmitRegRegCond(const X86EncodingMap* entry, uint8_t reg1, uint8_t reg2, uint8_t condition) {
+  // Generate prefix and opcode without the condition
+  EmitPrefixAndOpcode(entry);
+
+  // Now add the condition. The last byte of opcode is the one that receives it.
+  DCHECK_LE(condition, 0xF);
+  code_buffer_.back() += condition;
+
+  // Not expecting to have to encode immediate or do anything special for ModR/M since there are two registers.
+  DCHECK_EQ(0, entry->skeleton.immediate_bytes);
+  DCHECK_EQ(0, entry->skeleton.modrm_opcode);
+
+  // Check that registers requested for encoding are sane.
+  DCHECK_LT(reg1, 8);
+  DCHECK_LT(reg2, 8);
+
+  // For register to register encoding, the mod is 3.
+  const uint8_t mod = (3 << 6);
+
+  // Encode the ModR/M byte now.
+  const uint8_t modrm = mod | (reg1 << 3) | reg2;
+  code_buffer_.push_back(modrm);
+}
+
 void X86Mir2Lir::EmitJmp(const X86EncodingMap* entry, int rel) {
   if (entry->opcode == kX86Jmp8) {
     DCHECK(IS_SIMM8(rel));
@@ -1178,6 +1206,9 @@ AssemblerStatus X86Mir2Lir::AssembleInstructions(CodeOffset start_addr) {
       case kRegCond:  // lir operands - 0: reg, 1: condition
         EmitRegCond(entry, lir->operands[0], lir->operands[1]);
         break;
+      case kRegRegCond:  // lir operands - 0: reg, 1: reg, 2: condition
+        EmitRegRegCond(entry, lir->operands[0], lir->operands[1], lir->operands[2]);
+        break;
       case kJmp:  // lir operands - 0: rel
         EmitJmp(entry, lir->operands[0]);
         break;
diff --git a/compiler/dex/quick/x86/codegen_x86.h b/compiler/dex/quick/x86/codegen_x86.h
index 22c4452991..e6621f3bcb 100644
--- a/compiler/dex/quick/x86/codegen_x86.h
+++ b/compiler/dex/quick/x86/codegen_x86.h
@@ -153,6 +153,7 @@ class X86Mir2Lir : public Mir2Lir {
     LIR* OpRegImm(OpKind op, int r_dest_src1, int value);
     LIR* OpRegMem(OpKind op, int r_dest, int rBase, int offset);
     LIR* OpRegReg(OpKind op, int r_dest_src1, int r_src2);
+    LIR* OpCondRegReg(OpKind op, ConditionCode cc, int r_dest, int r_src);
     LIR* OpRegRegImm(OpKind op, int r_dest, int r_src1, int value);
     LIR* OpRegRegReg(OpKind op, int r_dest, int r_src1, int r_src2);
     LIR* OpTestSuspend(LIR* target);
@@ -201,6 +202,16 @@ class X86Mir2Lir : public Mir2Lir {
     void EmitShiftRegImm(const X86EncodingMap* entry, uint8_t reg, int imm);
     void EmitShiftRegCl(const X86EncodingMap* entry, uint8_t reg, uint8_t cl);
     void EmitRegCond(const X86EncodingMap* entry, uint8_t reg, uint8_t condition);
+
+    /**
+     * @brief Used for encoding conditional register to register operation.
+     * @param entry The entry in the encoding map for the opcode.
+     * @param reg1 The first physical register.
+     * @param reg2 The second physical register.
+     * @param condition The condition code for operation.
+     */
+    void EmitRegRegCond(const X86EncodingMap* entry, uint8_t reg1, uint8_t reg2, uint8_t condition);
+
     void EmitJmp(const X86EncodingMap* entry, int rel);
     void EmitJcc(const X86EncodingMap* entry, int rel, uint8_t cc);
     void EmitCallMem(const X86EncodingMap* entry, uint8_t base, int disp);
diff --git a/compiler/dex/quick/x86/int_x86.cc b/compiler/dex/quick/x86/int_x86.cc
index 75eddd60ff..11ccd4b35b 100644
--- a/compiler/dex/quick/x86/int_x86.cc
+++ b/compiler/dex/quick/x86/int_x86.cc
@@ -130,7 +130,7 @@ LIR* X86Mir2Lir::OpRegCopyNoInsert(int r_dest, int r_src) {
     return OpFpRegCopy(r_dest, r_src);
   LIR* res = RawLIR(current_dalvik_offset_, kX86Mov32RR,
                     r_dest, r_src);
-  if (r_dest == r_src) {
+  if (!(cu_->disable_opt & (1 << kSafeOptimizations)) && r_dest == r_src) {
     res->flags.is_nop = true;
   }
   return res;
@@ -296,20 +296,39 @@ RegLocation X86Mir2Lir::GenDivRem(RegLocation rl_dest, int reg_lo,
 
 bool X86Mir2Lir::GenInlinedMinMaxInt(CallInfo* info, bool is_min) {
   DCHECK_EQ(cu_->instruction_set, kX86);
+
+  // Get the two arguments to the invoke and place them in GP registers.
   RegLocation rl_src1 = info->args[0];
   RegLocation rl_src2 = info->args[1];
   rl_src1 = LoadValue(rl_src1, kCoreReg);
   rl_src2 = LoadValue(rl_src2, kCoreReg);
+
   RegLocation rl_dest = InlineTarget(info);
   RegLocation rl_result = EvalLoc(rl_dest, kCoreReg, true);
-  OpRegReg(kOpCmp, rl_src1.low_reg, rl_src2.low_reg);
-  DCHECK_EQ(cu_->instruction_set, kX86);
-  LIR* branch = NewLIR2(kX86Jcc8, 0, is_min ? kX86CondG : kX86CondL);
-  OpRegReg(kOpMov, rl_result.low_reg, rl_src1.low_reg);
-  LIR* branch2 = NewLIR1(kX86Jmp8, 0);
-  branch->target = NewLIR0(kPseudoTargetLabel);
-  OpRegReg(kOpMov, rl_result.low_reg, rl_src2.low_reg);
-  branch2->target = NewLIR0(kPseudoTargetLabel);
+
+  /*
+   * If the result register is the same as the second element, then we need to be careful.
+   * The reason is that the first copy will inadvertently clobber the second element with
+   * the first one thus yielding the wrong result. Thus we do a swap in that case.
+   */
+  if (rl_result.low_reg == rl_src2.low_reg) {
+    std::swap(rl_src1, rl_src2);
+  }
+
+  // Pick the first integer as min/max.
+  OpRegCopy(rl_result.low_reg, rl_src1.low_reg);
+
+  // If the integers are both in the same register, then there is nothing else to do
+  // because they are equal and we have already moved one into the result.
+  if (rl_src1.low_reg != rl_src2.low_reg) {
+    // It is possible we didn't pick correctly so do the actual comparison now.
+    OpRegReg(kOpCmp, rl_src1.low_reg, rl_src2.low_reg);
+
+    // Conditionally move the other integer into the destination register.
+    ConditionCode condition_code = is_min ? kCondGt : kCondLt;
+    OpCondRegReg(kOpCmov, condition_code, rl_result.low_reg, rl_src2.low_reg);
+  }
+
   StoreValue(rl_dest, rl_result);
   return true;
 }
diff --git a/compiler/dex/quick/x86/utility_x86.cc b/compiler/dex/quick/x86/utility_x86.cc
index 6ec7ebb91a..f683affaf9 100644
--- a/compiler/dex/quick/x86/utility_x86.cc
+++ b/compiler/dex/quick/x86/utility_x86.cc
@@ -203,6 +203,12 @@ LIR* X86Mir2Lir::OpRegReg(OpKind op, int r_dest_src1, int r_src2) {
     return NewLIR2(opcode, r_dest_src1, r_src2);
 }
 
+LIR* X86Mir2Lir::OpCondRegReg(OpKind op, ConditionCode cc, int r_dest, int r_src) {
+  // The only conditional reg to reg operation supported is Cmov
+  DCHECK_EQ(op, kOpCmov);
+  return NewLIR3(kX86Cmov32RRC, r_dest, r_src, X86ConditionEncoding(cc));
+}
+
 LIR* X86Mir2Lir::OpRegMem(OpKind op, int r_dest, int rBase,
               int offset) {
   X86OpCode opcode = kX86Nop;
diff --git a/compiler/dex/quick/x86/x86_lir.h b/compiler/dex/quick/x86/x86_lir.h
index a2d5c3e402..f38a16dc15 100644
--- a/compiler/dex/quick/x86/x86_lir.h
+++ b/compiler/dex/quick/x86/x86_lir.h
@@ -279,6 +279,9 @@ enum X86OpCode {
   kX86Mov32RR, kX86Mov32RM, kX86Mov32RA, kX86Mov32RT,
   kX86Mov32RI, kX86Mov32MI, kX86Mov32AI, kX86Mov32TI,
   kX86Lea32RA,
+  // RRC - Register Register ConditionCode - cond_opcode reg1, reg2
+  //             - lir operands - 0: reg1, 1: reg2, 2: CC
+  kX86Cmov32RRC,
   // RC - Register CL - opcode reg, CL
   //          - lir operands - 0: reg, 1: CL
   // MC - Memory CL   - opcode [base + disp], CL
@@ -398,6 +401,7 @@ enum X86EncodingKind {
   kShiftRegCl, kShiftMemCl, kShiftArrayCl,     // Shift opcode with register CL.
   kRegRegReg, kRegRegMem, kRegRegArray,    // RRR, RRM, RRA instruction kinds.
   kRegCond, kMemCond, kArrayCond,          // R, M, A instruction kinds following by a condition.
+  kRegRegCond,                             // RR instruction kind followed by a condition.
   kJmp, kJcc, kCall,                       // Branch instruction kinds.
   kPcRel,                                  // Operation with displacement that is PC relative
   kMacro,                                  // An instruction composing multiple others
diff --git a/disassembler/disassembler_x86.cc b/disassembler/disassembler_x86.cc
index 1d53ca8123..c51ea7b8a4 100644
--- a/disassembler/disassembler_x86.cc
+++ b/disassembler/disassembler_x86.cc
@@ -317,6 +317,12 @@ DISASSEMBLER_ENTRY(cmp,
       case 0x3A:  // 3 byte extended opcode
         opcode << StringPrintf("unknown opcode '0F 3A %02X'", *instr);
         break;
+      case 0x40: case 0x41: case 0x42: case 0x43: case 0x44: case 0x45: case 0x46: case 0x47:
+      case 0x48: case 0x49: case 0x4A: case 0x4B: case 0x4C: case 0x4D: case 0x4E: case 0x4F:
+        opcode << "cmov" << condition_codes[*instr & 0xF];
+        has_modrm = true;
+        load = true;
+        break;
       case 0x50: case 0x51: case 0x52: case 0x53: case 0x54: case 0x55: case 0x56: case 0x57:
       case 0x58: case 0x59: case 0x5C: case 0x5D: case 0x5E: case 0x5F: {
         switch (*instr) {