[X86] X86::CMOV to Branch heuristic based optimization

[aaboud]

Summary

LLVM compiler recognizes opportunities to transform a branch into IR select instruction(s) - later it will be lowered into X86::CMOV instruction, assuming no other optimization eliminated the SelectInst.
However, it is not always profitable to emit X86::CMOV instruction. For example, branch is preferable over an X86::CMOV instruction when:

• Branch is well predicted
• Condition operand is expensive, compared to True-value and the False-value operands

In CodeGenPrepare pass there is a shallow optimization that tries to convert SelectInst into branch, but it is not enough.
This patch, implements machine optimization pass that converts X86::CMOV instruction(s) into branch, based on a conservative heuristic.

[hfinkel]

Interestingly, we just recently introduced a pass into the PowerPC backend that does essentially the same thing; lib/Target/PowerPC/PPCExpandISEL.cpp. Could you please take a look at that and see how it compares to this implementation? I'm obviously curious as to whether we could add some target callbacks and unify the underlying logic in a target-independent pass. FWIW, both implementations are around 500 lines.

One thing that's not clear to me: how are you determining whether or not the branch is predictable?

One outstanding TODO item we have from the PPC functionality is to support __builtin_unpredictable (which turns in to metadata at the IR level). Have you looked at that?

[aaboud]

In D34769#794214, @hfinkel wrote:

Interestingly, we just recently introduced a pass into the PowerPC backend that does essentially the same thing; lib/Target/PowerPC/PPCExpandISEL.cpp. Could you please take a look at that and see how it compares to this implementation? I'm obviously curious as to whether we could add some target callbacks and unify the underlying logic in a target-independent pass. FWIW, both implementations are around 500 lines.

Thanks for the information, I will take a look.

One thing that's not clear to me: how are you determining whether or not the branch is predictable?

I did not determine if it is predictable, however, I did the transformation only when I can assure gain of more than 25% of the mis-prediction penalty.
On the other hand, I considered during development of this pass to try determine one case where branch is not predicted, which is tree-search like algorithms.
I did that roughly by looking for how the CMOV result value was used, and if it was used for another "pointer-like" load, I considered it a possible case for tree-search.
Notice, that this is not part of this patch, but we might consider adding it if found reasonable.

One outstanding TODO item we have from the PPC functionality is to support __builtin_unpredictable (which turns in to metadata at the IR level). Have you looked at that?

I know about this built-in, but as you said, it is not lowered into the machine IR. I did not try to figure out how to preserve it though.

[hfinkel]

In D34769#794220, @aaboud wrote:

In D34769#794214, @hfinkel wrote:

Interestingly, we just recently introduced a pass into the PowerPC backend that does essentially the same thing; lib/Target/PowerPC/PPCExpandISEL.cpp. Could you please take a look at that and see how it compares to this implementation? I'm obviously curious as to whether we could add some target callbacks and unify the underlying logic in a target-independent pass. FWIW, both implementations are around 500 lines.

Thanks for the information, I will take a look.

One thing that's not clear to me: how are you determining whether or not the branch is predictable?

I did not determine if it is predictable, however, I did the transformation only when I can assure gain of more than 25% of the mis-prediction penalty.
On the other hand, I considered during development of this pass to try determine one case where branch is not predicted, which is tree-search like algorithms.
I did that roughly by looking for how the CMOV result value was used, and if it was used for another "pointer-like" load, I considered it a possible case for tree-search.
Notice, that this is not part of this patch, but we might consider adding it if found reasonable.

Thanks. That heuristic sounds like an interesting idea. Hopefully, we can investigate that in the future.

One outstanding TODO item we have from the PPC functionality is to support __builtin_unpredictable (which turns in to metadata at the IR level). Have you looked at that?

I know about this built-in, but as you said, it is not lowered into the machine IR. I did not try to figure out how to preserve it though.

One way of doing this might be to have the branch instructions get the metadata from the IR (there are MI metadata operands, although I think they're only currently used for debug-info pseudo instructions).

[aaboud]

In D34769#794220, @aaboud wrote:

In D34769#794214, @hfinkel wrote:

Interestingly, we just recently introduced a pass into the PowerPC backend that does essentially the same thing; lib/Target/PowerPC/PPCExpandISEL.cpp. Could you please take a look at that and see how it compares to this implementation? I'm obviously curious as to whether we could add some target callbacks and unify the underlying logic in a target-independent pass. FWIW, both implementations are around 500 lines.

Thanks for the information, I will take a look.

I reviewed the PowerPC pass in lib/Target/PowerPC/PPCExpandISEL.cpp, it is trying to address same issue like this patch, however, it is different:

PPCExpandISEL

1. Runs after register allocation.
2. User flag based, rather than compilation heuristic, i.e., once it is decided to expand ISEL, it will expand them all.
3. Used as a functionality pass, to cover cases where HW does not support ISEL instruction.

X86CmovConversion

1. Runs on SSA machine IR, before register allocation.
2. Heuristic base optimization, i.e., it can convert only CMOV instructions that worth converting while keeping others.
3. Used only as a performance pass, the functionality pass exists in X86TargetLowering::EmitLoweredSelect, which lowers pseudo CMOV instructions.

[spatel]

I haven't looked at the patch yet, but for reference I filed:
https://bugs.llvm.org//show_bug.cgi?id=33013 (although the comments veered off to a different topic)
...and mentioned:
https://reviews.llvm.org/rL292154

If the example(s) in the bug report are already here, then great. If not, you might want to consider those cases.

[zvi]

A few quick comments in the body of the implementation.

About the tests:
The added test are definitely interesting cases, but they are system tests as they check the full flow where we handle branches: CodegenPrepare, ISel, EarlyIfConversion (which is not enabled for X86), ...
Have you considered adding mit tests which will be considered as unit-tests specific to this pass?

lib/Target/X86/X86CmovConversion.cpp

94 ↗

(On Diff #104480)

Please consider making the variable and type names consistent. Use either Cmov or CMOV.

127 ↗

(On Diff #104480)

Define as a reference instead of a pointer.

131 ↗

(On Diff #104480)

Could we save the overhead of initializing the resource tables from one visited function to another? If two visited functions share the same subtarget, could we reuse the same schedule model configuration?

156 ↗

(On Diff #104480)

This variable is not initialized in the c-tor, and IIUC will be assigned here for the first time. IMHO, it would be better to reduce its scope to this loop, and pass a reference in to collectCmovCandidates() and collectCmovCandidates().

170 ↗

(On Diff #104480)

To be consistent with collectCmovCandidates() and checkForProfitableCmovCandidates() i suggest you move this loop into convertCmovInstsToBranches().

Another option that IMHO is better:
Define CmovInstGroups in the scope of the MF iteration loop in this function and pass it by reference to the functions called in this loop. That will save the need to CmovInstGroups.clear() in numerous functions.

204 ↗

(On Diff #104480)

*FoundNonCMOVInst

211 ↗

(On Diff #104480)

If i did not miss it, can you please add a comment here or update the comments on the top why we skip cmovs with memory operands? My naive thought is that if we can speculate the load in the cmov, then we should also be able to put the load under a branch.

226 ↗

(On Diff #104480)

Would this allow making the code below simpler?

else if (Group.empty()) continue;

It would probably be faster as the typical case is where no interesting instruction was encountered yet (or ever).

Another option is to search for the first interesting cmov instruction in the BB before entering this loop and and bail out if none found.

243 ↗

(On Diff #104480)

Consider:

if (Group.empty()) continue;

[aaboud]

Thanks Zvi for the helpful comments.
I fixed most of them, and answered the others, see below.

lib/Target/X86/X86CmovConversion.cpp

131 ↗

(On Diff #104480)

MachineCombiner, MachineLICM, and IfConverter initialize it in runOnMachineFunction, for every machine function.
Do you think that this function is too expensive?
Either way, it is out-of-scope for this patch.

211 ↗

(On Diff #104480)

The reason is implementation effort.
There is a "TODO" at line 191, so this can be added in future patch.
I do not see a need to add a comment, the "TODO" should be enough, do not you think so?

[aaboud]

Addressed Zvi comments.

[michaeljclark]

In D34769#797714, @spatel wrote:

I haven't looked at the patch yet, but for reference I filed:
https://bugs.llvm.org//show_bug.cgi?id=33013 (although the comments veered off to a different topic)
...and mentioned:
https://reviews.llvm.org/rL292154

If the example(s) in the bug report are already here, then great. If not, you might want to consider those cases.

The reason it veered off topic is that the FPToUI bug that I reported on the mailing list, was dismissed supposedly because LLVM doesn't support correct floating point accrued exception state for very simple intrinsic conversions e.g. ISD::FP_TO_UINT is broken on X86. The issue was isolated to a SELECT created by FPToUI being lowered as a conditional move, however, one side of the SELECT had a SUBSS floating point instruction that clobbers the floating point accrued exception state (sets FE_INEXECT), so we discussed exact vs inexact conversions. The fix for the FPToUI bug is to lower the SELECT as a branch, however the compiler needs to model the MXCSR flags. That aside, FPToUI is trivially fixable by emitting a branch. It's a bug.

The bug reported was "FE_INEXACT being set for an exact conversion from float to unsigned long long" and it resulted in you raising a bug about the compiler generating more branchy code (ignoring the issue I reported), so we were not, in fact, going off topic, rather we were discussing the original bug reported on the mailing list.

This code may indeed fix the FE_INEXACT issue but long term the compiler needs to consider the floating point accrued flags side effects, however, whether of not FENV_ACCESS is enabled, the FPToUI should be trivially able to generate correct flags by using a branch instead of a cmove. GCC preserves floating point accrued exception flags for simple signed and unsigned floating point conversions when FENV_ACCESS is not enabled. It's not a complex DAG. This is not especially complex FP code. It's simply a broken ISD::FP_TO_UINT. i.e. buggy intrinsic.

"SelectionDAGLegalize::ExpandNode() in LegalizeDAG.cpp. The X86 backend sets a table entry indicating that FP_TO_UINT should be expanded for these value types, but the actual expansion is in target-independent code. " from Andrew K. It's a SELECT.

case ISD::FP_TO_UINT: {
  SDValue True, False;
  EVT VT =  Node->getOperand(0).getValueType();
  EVT NVT = Node->getValueType(0);
  APFloat apf(DAG.EVTToAPFloatSemantics(VT),
              APInt::getNullValue(VT.getSizeInBits()));
  APInt x = APInt::getSignBit(NVT.getSizeInBits());
  (void)apf.convertFromAPInt(x, false, APFloat::rmNearestTiesToEven);
  Tmp1 = DAG.getConstantFP(apf, dl, VT);
  Tmp2 = DAG.getSetCC(dl, getSetCCResultType(VT),
                      Node->getOperand(0),
                      Tmp1, ISD::SETLT);
  True = DAG.getNode(ISD::FP_TO_SINT, dl, NVT, Node->getOperand(0));
  // TODO: Should any fast-math-flags be set for the FSUB?
  False = DAG.getNode(ISD::FP_TO_SINT, dl, NVT,
                      DAG.getNode(ISD::FSUB, dl, VT,
                                  Node->getOperand(0), Tmp1));
  False = DAG.getNode(ISD::XOR, dl, NVT, False,
                      DAG.getConstant(x, dl, NVT));
  Tmp1 = DAG.getSelect(dl, NVT, Tmp2, True, False);
  Results.push_back(Tmp1);
  break;
}

Note the second form with CMOV has a bug as the SUBSS is clobbering the flags resulting in FE_INEXACT for exact conversions. In any case this patch may fix the issue in a round about way

"
$ more llvm/lib/Target/X86//README-X86-64.txt
…
Are we better off using branches instead of cmove to implement FP to
unsigned i64?

_conv:

ucomiss LC0(%rip), %xmm0
cvttss2siq      %xmm0, %rdx
jb      L3
subss   LC0(%rip), %xmm0
movabsq $-9223372036854775808, %rax
cvttss2siq      %xmm0, %rdx
xorq    %rax, %rdx

L3:

movq    %rdx, %rax
ret

instead of

_conv:

movss LCPI1_0(%rip), %xmm1
cvttss2siq %xmm0, %rcx
movaps %xmm0, %xmm2
subss %xmm1, %xmm2
cvttss2siq %xmm2, %rax
movabsq $-9223372036854775808, %rdx
xorq %rdx, %rax
ucomiss %xmm1, %xmm0
cmovb %rcx, %rax
ret

"

[zvi]

lib/Target/X86/X86CmovConversion.cpp

343 ↗

(On Diff #105300)

Please avoid using operator[] for lookups - use DenseMap::lookup() instead.
And maybe mapping operands to null's is just inefficient? The non-existence of the mapping can be also used for choosing depth = 0?
So this code can be instead something like:

if (MachineInstr *DefMI = RDM.lookup(Reg)) {
  OperandToDefMap[&MO] = DefMI;
  MIDepth = std::max(MIDepth, DepthMap.lookup(DefMI).Depth);
  if (!IsCMOV)
    MIDepthOpt = std::max(MIDepthOpt, DepthMap.lookup(DefMI).OptDepth);
 }

This also applies to more uses of operator[] below. If I'm not mistaken, only these two statements should remain using opertor[]:

RegDefMaps[TargetRegisterInfo::isVirtualRegister(Reg)][Reg] = &MI;
DepthMap[&MI] = {MIDepth += Latency, MIDepthOpt += Latency};

131 ↗

(On Diff #104480)

I don't know what is the potential saving :)
I'm ok with keeping it as-is.

211 ↗

(On Diff #104480)

I agree. I missed the TODO

test/CodeGen/X86/x86-cmov-converter.ll

321 ↗

(On Diff #105300)

Can these attributes be dropped or minimized if they don't add anything?

[zvi]

lib/Target/X86/X86CmovConversion.cpp

338 ↗

(On Diff #105300)

Are these two equivalent?

for (auto &MO : MI.operands())
  if (!MO.isReg() || !MO.isUse())
    continue;

and

for (auto &MO : MI.uses())
  if (!MO.isReg())
    continue?

355 ↗

(On Diff #105300)

Are these two equivalent?

for (auto &MO: MI.operands())
  if (!MO.isReg() || !MO.isDef())
    continue;

and

for (auto &MO: MI.defs())

[aaboud]

Thanks Zvi,
I answered your comments below.

lib/Target/X86/X86CmovConversion.cpp

338 ↗

(On Diff #105300)

Could be, but to keep the code consistent wit the below loop, I preferred this format, I do not mind change to your suggestion if you think it is better.

343 ↗

(On Diff #105300)

Fixed most places.
Other places where I kept the "[]" operator, we know for sure that the entry we are looking for exists in the container.

355 ↗

(On Diff #105300)

No they are not, the "defs()" does not include implicit definition operands.

iterator_range<mop_iterator> operands() {
  return make_range(operands_begin(), operands_end());
}

/// Returns a range over all explicit operands that are register definitions.
/// Implicit definition are not included!
iterator_range<mop_iterator> defs() {
  return make_range(operands_begin(),
                    operands_begin() + getDesc().getNumDefs());
}

/// Returns a range that includes all operands that are register uses.
/// This may include unrelated operands which are not register uses.
iterator_range<mop_iterator> uses() {
  return make_range(operands_begin() + getDesc().getNumDefs(),
                    operands_end());
}

[aaboud]

Addressed more comments by Zvi.

[aaboud]

In D34769#797714, @spatel wrote:

I haven't looked at the patch yet, but for reference I filed:
https://bugs.llvm.org//show_bug.cgi?id=33013 (although the comments veered off to a different topic)
...and mentioned:
https://reviews.llvm.org/rL292154

If the example(s) in the bug report are already here, then great. If not, you might want to consider those cases.

The optimization in this patch is triggered on inner loops only, assuming that hotspots will exist in these inner loops.
Moreover, if I modify the example on the code by calling the function from a loop like this:

static int foo(float x) {
  if (x < 42.0f)
    return x;
  return 12;
}

int bar(float *a, float *b, int n) {
  int sum = 0;
#pragma clang loop vectorize(disable)
  for (int i = 0; i < n; ++i) {
    float c = a[i] + b[i];
    sum += foo(c);
  }
  return sum;
}

Then the patch will indeed convert the CMOV into branch.

LBB0_4:                                 # %for.body
                                        # =>This Inner Loop Header: Depth=1
        movss   (%esi), %xmm1           # xmm1 = mem[0],zero,zero,zero
        addss   (%edx), %xmm1
        ucomiss %xmm1, %xmm0
        ja      LBB0_5
# BB#6:                                 # %for.body
                                        #   in Loop: Header=BB0_4 Depth=1
        movl    $12, %eax
        jmp     LBB0_7
        .p2align        4, 0x90
LBB0_5:                                 #   in Loop: Header=BB0_4 Depth=1
        cvttss2si       %xmm1, %eax
LBB0_7:                                 # %for.body
                                        #   in Loop: Header=BB0_4 Depth=1
        addl    %edi, %eax
        addl    $4, %esi
        addl    $4, %edx
        decl    %ecx
        movl    %eax, %edi
        jne     LBB0_4

[aaboud]

It would be great if I can get approval for this patch before the next release branch is created (July 19, 2017: Branch point).
Please, let me know if you have more comments as soon as possible, so I can address them as well.

Thanks,
Amjad

[zvi]

lib/Target/X86/X86CmovConversion.cpp

564 ↗

(On Diff #106059)

Please add comment explaining the data-structure

577 ↗

(On Diff #106059)

auto I = RegRewriteTable.find(Op1Reg);
if (I != RegWriteTable.end())
  Op1Reg  = I->second.first

338 ↗

(On Diff #105300)

Iterating over uses() instead of operand() is more efficient, right?

[aaboud]

Addressed more comments by Zvi.

lib/Target/X86/X86CmovConversion.cpp

564 ↗

(On Diff #106059)

There is a comment explaining this map and even explaining the motivation behind it:

//  ...   and that the code must maintain a mapping from earlier PHI's
// destination registers, and the registers that went into the PHI.

[zvi]

LGTM. Thanks, Amjad!

lib/Target/X86/X86CmovConversion.cpp

564 ↗

(On Diff #106059)

That comment explaining why we need to maintain the mapping is great. I thought it would be helpful to add something like:

// Maps Phi's Def VirtReg -> (Incoming0, Incoming1)

I'm fine with keeping it as-is.

[anna]

Hi @aaboud,

We are seeing couple of regressions with this optimization on our internal benchmarks on skylake hardware.
This is fixed when we turn off the optimization using -x86-cmov-converter=false

Could it be something in the heuristic that depends on the cmov to branch conversion on the gain being greater than 25% of branch misprediction penalty? I analyzed the assembly on the internal benchmark and can definitely see higher number of branches in a MBB when earlier it was all in one block with a cmov.

I have filed a bug for this (with a reduced IR): https://bugs.llvm.org/show_bug.cgi?id=33954

Could you please disable this optimization while debugging the problem offline?

Also, I was wondering if you ran this optimization on any LLVM performance suite? Couldn't find the numbers in the review.

Thanks,
Anna

[aaboud]

In D34769#822047, @anna wrote:

Also, I was wondering if you ran this optimization on any LLVM performance suite? Couldn't find the numbers in the review.

I measured gains on both Spec2006 and EEMBC benchmarks, with no regression that was directly related to the CMOV conversion into branch.
The most noticeable improvements (but there are more), measured on Skylake:

Spec2006
  429.mcf:     +6%
  456.hmmer:   +12%

Telecom
  fbital00:    +30%

llvm/trunk/lib/Target/X86/CMakeLists.txt

else()
   set(GLOBAL_ISEL_BUILD_FILES "")
   set(LLVM_OPTIONAL_SOURCES LLVMGlobalISel ${GLOBAL_ISEL_FILES})
 endif()
 
 
 set(sources
   X86AsmPrinter.cpp
   X86CallFrameOptimization.cpp
+  X86CmovConversion.cpp
   X86ExpandPseudo.cpp
   X86FastISel.cpp
   X86FixupBWInsts.cpp
   X86FixupLEAs.cpp
   X86FixupSetCC.cpp
   X86FloatingPoint.cpp
   X86FrameLowering.cpp
   X86ISelDAGToDAG.cpp

llvm/trunk/lib/Target/X86/X86.h

 FunctionPass *createX86WinEHStatePass();
 
 /// Return a Machine IR pass that expands X86-specific pseudo
 /// instructions into a sequence of actual instructions. This pass
 /// must run after prologue/epilogue insertion and before lowering
 /// the MachineInstr to MC.
 FunctionPass *createX86ExpandPseudoPass();
 
+/// This pass converts X86 cmov instructions into branch when profitable.
+FunctionPass *createX86CmovConverterPass();
+
 /// Return a Machine IR pass that selectively replaces
 /// certain byte and word instructions by equivalent 32 bit instructions,
 /// in order to eliminate partial register usage, false dependences on
 /// the upper portions of registers, and to save code size.
 FunctionPass *createX86FixupBWInsts();
 
 void initializeFixupBWInstPassPass(PassRegistry &);
 

llvm/trunk/lib/Target/X86/X86CmovConversion.cpp

+//====-- X86CmovConversion.cpp - Convert Cmov to Branch -------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This file implements a pass that converts X86 cmov instructions into branch
+/// when profitable. This pass is conservative, i.e., it applies transformation
+/// if and only if it can gaurantee a gain with high confidence.
+///
+/// Thus, the optimization applies under the following conditions:
+///   1. Consider as a candidate only CMOV in most inner loop, assuming that
+///       most hotspots are represented by these loops.
+///   2. Given a group of CMOV instructions, that are using same EFLAGS def
+///      instruction:
+///      a. Consider them as candidates only if all have same code condition or
+///         opposite one, to prevent generating more than one conditional jump
+///         per EFLAGS def instruction.
+///      b. Consider them as candidates only if all are profitable to be
+///         converted, assuming that one bad conversion may casue a degradation.
+///   3. Apply conversion only for loop that are found profitable and only for
+///      CMOV candidates that were found profitable.
+///      a. Loop is considered profitable only if conversion will reduce its
+///         depth cost by some thrishold.
+///      b. CMOV is considered profitable if the cost of its condition is higher
+///         than the average cost of its true-value and false-value by 25% of
+///         branch-misprediction-penalty, this to assure no degredassion even
+///         with 25% branch misprediction.
+///
+/// Note: This pass is assumed to run on SSA machine code.
+//===----------------------------------------------------------------------===//
+//
+//  External interfaces:
+//      FunctionPass *llvm::createX86CmovConverterPass();
+//      bool X86CmovConverterPass::runOnMachineFunction(MachineFunction &MF);
+//
+
+#include "X86.h"
+#include "X86InstrInfo.h"
+#include "X86Subtarget.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/TargetSchedule.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "x86-cmov-converter"
+
+STATISTIC(NumOfSkippedCmovGroups, "Number of unsupported CMOV-groups");
+STATISTIC(NumOfCmovGroupCandidate, "Number of CMOV-group candidates");
+STATISTIC(NumOfLoopCandidate, "Number of CMOV-conversion profitable loops");
+STATISTIC(NumOfOptimizedCmovGroups, "Number of optimized CMOV-groups");
+
+namespace {
+// This internal switch can be used to turn off the cmov/branch optimization.
+static cl::opt<bool>
+    EnableCmovConverter("x86-cmov-converter",
+                        cl::desc("Enable the X86 cmov-to-branch optimization."),
+                        cl::init(true), cl::Hidden);
+
+/// Converts X86 cmov instructions into branches when profitable.
+class X86CmovConverterPass : public MachineFunctionPass {
+public:
+  X86CmovConverterPass() : MachineFunctionPass(ID) {}
+  ~X86CmovConverterPass() {}
+
+  StringRef getPassName() const override { return "X86 cmov Conversion"; }
+  bool runOnMachineFunction(MachineFunction &MF) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+private:
+  /// Pass identification, replacement for typeid.
+  static char ID;
+
+  const MachineRegisterInfo *MRI;
+  const TargetInstrInfo *TII;
+  TargetSchedModel TSchedModel;
+
+  /// List of consecutive CMOV instructions.
+  typedef SmallVector<MachineInstr *, 2> CmovGroup;
+  typedef SmallVector<CmovGroup, 2> CmovGroups;
+
+  /// Collect all CMOV-group-candidates in \p CurrLoop and update \p
+  /// CmovInstGroups accordingly.
+  ///
+  /// \param CurrLoop Loop being processed.
+  /// \param CmovInstGroups List of consecutive CMOV instructions in CurrLoop.
+  /// \returns true iff it found any CMOV-group-candidate.
+  bool collectCmovCandidates(MachineLoop *CurrLoop, CmovGroups &CmovInstGroups);
+
+  /// Check if it is profitable to transform each CMOV-group-candidates into
+  /// branch. Remove all groups that are not profitable from \p CmovInstGroups.
+  ///
+  /// \param CurrLoop Loop being processed.
+  /// \param CmovInstGroups List of consecutive CMOV instructions in CurrLoop.
+  /// \returns true iff any CMOV-group-candidate remain.
+  bool checkForProfitableCmovCandidates(MachineLoop *CurrLoop,
+                                        CmovGroups &CmovInstGroups);
+
+  /// Convert the given list of consecutive CMOV instructions into a branch.
+  ///
+  /// \param Group Consecutive CMOV instructions to be converted into branch.
+  void convertCmovInstsToBranches(SmallVectorImpl<MachineInstr *> &Group) const;
+};
+
+char X86CmovConverterPass::ID = 0;
+
+void X86CmovConverterPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  MachineFunctionPass::getAnalysisUsage(AU);
+  AU.addRequired<MachineLoopInfo>();
+}
+
+bool X86CmovConverterPass::runOnMachineFunction(MachineFunction &MF) {
+  if (skipFunction(*MF.getFunction()))
+    return false;
+  if (!EnableCmovConverter)
+    return false;
+
+  DEBUG(dbgs() << "********** " << getPassName() << " : " << MF.getName()
+               << "**********\n");
+
+  bool Changed = false;
+  MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
+  const TargetSubtargetInfo &STI = MF.getSubtarget();
+  MRI = &MF.getRegInfo();
+  TII = STI.getInstrInfo();
+  TSchedModel.init(STI.getSchedModel(), &STI, TII);
+
+  //===--------------------------------------------------------------------===//
+  // Algorithm
+  // ---------
+  //   For each inner most loop
+  //     collectCmovCandidates() {
+  //       Find all CMOV-group-candidates.
+  //     }
+  //
+  //     checkForProfitableCmovCandidates() {
+  //       * Calculate both loop-depth and optimized-loop-depth.
+  //       * Use these depth to check for loop transformation profitability.
+  //       * Check for CMOV-group-candidate transformation profitability.
+  //     }
+  //
+  //     For each profitable CMOV-group-candidate
+  //       convertCmovInstsToBranches() {
+  //           * Create FalseBB, SinkBB, Conditional branch to SinkBB.
+  //           * Replace each CMOV instruction with a PHI instruction in SinkBB.
+  //       }
+  //
+  // Note: For more details, see each function description.
+  //===--------------------------------------------------------------------===//
+  for (MachineBasicBlock &MBB : MF) {
+    MachineLoop *CurrLoop = MLI.getLoopFor(&MBB);
+
+    // Optimize only inner most loops.
+    if (!CurrLoop || CurrLoop->getHeader() != &MBB ||
+        !CurrLoop->getSubLoops().empty())
+      continue;
+
+    // List of consecutive CMOV instructions to be processed.
+    CmovGroups CmovInstGroups;
+
+    if (!collectCmovCandidates(CurrLoop, CmovInstGroups))
+      continue;
+
+    if (!checkForProfitableCmovCandidates(CurrLoop, CmovInstGroups))
+      continue;
+
+    Changed = true;
+    for (auto &Group : CmovInstGroups)
+      convertCmovInstsToBranches(Group);
+  }
+  return Changed;
+}
+
+bool X86CmovConverterPass::collectCmovCandidates(MachineLoop *CurrLoop,
+                                                 CmovGroups &CmovInstGroups) {
+  //===--------------------------------------------------------------------===//
+  // Collect all CMOV-group-candidates and add them into CmovInstGroups.
+  //
+  // CMOV-group:
+  //   CMOV instructions, in same MBB, that uses same EFLAGS def instruction.
+  //
+  // CMOV-group-candidate:
+  //   CMOV-group where all the CMOV instructions are
+  //     1. consecutive.
+  //     2. have same condition code or opposite one.
+  //     3. have only operand registers (X86::CMOVrr).
+  //===--------------------------------------------------------------------===//
+  // List of possible improvement (TODO's):
+  // --------------------------------------
+  //   TODO: Add support for X86::CMOVrm instructions.
+  //   TODO: Add support for X86::SETcc instructions.
+  //   TODO: Add support for CMOV-groups with non consecutive CMOV instructions.
+  //===--------------------------------------------------------------------===//
+
+  // Current processed CMOV-Group.
+  CmovGroup Group;
+  for (auto *MBB : CurrLoop->getBlocks()) {
+    Group.clear();
+    // Condition code of first CMOV instruction current processed range and its
+    // opposite condition code.
+    X86::CondCode FirstCC, FirstOppCC;
+    // Indicator of a non CMOVrr instruction in the current processed range.
+    bool FoundNonCMOVInst = false;
+    // Indicator for current processed CMOV-group if it should be skipped.
+    bool SkipGroup = false;
+
+    for (auto &I : *MBB) {
+      X86::CondCode CC = X86::getCondFromCMovOpc(I.getOpcode());
+      // Check if we found a X86::CMOVrr instruction.
+      if (CC != X86::COND_INVALID && !I.mayLoad()) {
+        if (Group.empty()) {
+          // We found first CMOV in the range, reset flags.
+          FirstCC = CC;
+          FirstOppCC = X86::GetOppositeBranchCondition(CC);
+          FoundNonCMOVInst = false;
+          SkipGroup = false;
+        }
+        Group.push_back(&I);
+        // Check if it is a non-consecutive CMOV instruction or it has different
+        // condition code than FirstCC or FirstOppCC.
+        if (FoundNonCMOVInst || (CC != FirstCC && CC != FirstOppCC))
+          // Mark the SKipGroup indicator to skip current processed CMOV-Group.
+          SkipGroup = true;
+        continue;
+      }
+      // If Group is empty, keep looking for first CMOV in the range.
+      if (Group.empty())
+        continue;
+
+      // We found a non X86::CMOVrr instruction.
+      FoundNonCMOVInst = true;
+      // Check if this instruction define EFLAGS, to determine end of processed
+      // range, as there would be no more instructions using current EFLAGS def.
+      if (I.definesRegister(X86::EFLAGS)) {
+        // Check if current processed CMOV-group should not be skipped and add
+        // it as a CMOV-group-candidate.
+        if (!SkipGroup)
+          CmovInstGroups.push_back(Group);
+        else
+          ++NumOfSkippedCmovGroups;
+        Group.clear();
+      }
+    }
+    // End of basic block is considered end of range, check if current processed
+    // CMOV-group should not be skipped and add it as a CMOV-group-candidate.
+    if (Group.empty())
+      continue;
+    if (!SkipGroup)
+      CmovInstGroups.push_back(Group);
+    else
+      ++NumOfSkippedCmovGroups;
+  }
+
+  NumOfCmovGroupCandidate += CmovInstGroups.size();
+  return !CmovInstGroups.empty();
+}
+
+/// \returns Depth of CMOV instruction as if it was converted into branch.
+/// \param TrueOpDepth depth cost of CMOV true value operand.
+/// \param FalseOpDepth depth cost of CMOV false value operand.
+static unsigned getDepthOfOptCmov(unsigned TrueOpDepth, unsigned FalseOpDepth) {
+  //===--------------------------------------------------------------------===//
+  // With no info about branch weight, we assume 50% for each value operand.
+  // Thus, depth of optimized CMOV instruction is the rounded up average of
+  // its True-Operand-Value-Depth and False-Operand-Value-Depth.
+  //===--------------------------------------------------------------------===//
+  return (TrueOpDepth + FalseOpDepth + 1) / 2;
+}
+
+bool X86CmovConverterPass::checkForProfitableCmovCandidates(
+    MachineLoop *CurrLoop, CmovGroups &CmovInstGroups) {
+  struct DepthInfo {
+    /// Depth of original loop.
+    unsigned Depth;
+    /// Depth of optimized loop.
+    unsigned OptDepth;
+  };
+  /// Number of loop iterations to calculate depth for ?!
+  static const unsigned LoopIterations = 2;
+  DenseMap<MachineInstr *, DepthInfo> DepthMap;
+  DepthInfo LoopDepth[LoopIterations] = {{0, 0}, {0, 0}};
+  enum { PhyRegType = 0, VirRegType = 1, RegTypeNum = 2 };
+  /// For each register type maps the register to its last def instruction.
+  DenseMap<unsigned, MachineInstr *> RegDefMaps[RegTypeNum];
+  /// Maps register operand to its def instruction, which can be nullptr if it
+  /// is unknown (e.g., operand is defined outside the loop).
+  DenseMap<MachineOperand *, MachineInstr *> OperandToDefMap;
+
+  // Set depth of unknown instruction (i.e., nullptr) to zero.
+  DepthMap[nullptr] = {0, 0};
+
+  SmallPtrSet<MachineInstr *, 4> CmovInstructions;
+  for (auto &Group : CmovInstGroups)
+    CmovInstructions.insert(Group.begin(), Group.end());
+
+  //===--------------------------------------------------------------------===//
+  // Step 1: Calculate instruction depth and loop depth.
+  // Optimized-Loop:
+  //   loop with CMOV-group-candidates converted into branches.
+  //
+  // Instruction-Depth:
+  //   instruction latency + max operand depth.
+  //     * For CMOV instruction in optimized loop the depth is calculated as:
+  //       CMOV latency + getDepthOfOptCmov(True-Op-Depth, False-Op-depth)
+  // TODO: Find a better way to estimate the latency of the branch instruction
+  //       rather than using the CMOV latency.
+  //
+  // Loop-Depth:
+  //   max instruction depth of all instructions in the loop.
+  // Note: instruction with max depth represents the critical-path in the loop.
+  //
+  // Loop-Depth[i]:
+  //   Loop-Depth calculated for first `i` iterations.
+  //   Note: it is enough to calculate depth for up to two iterations.
+  //
+  // Depth-Diff[i]:
+  //   Number of cycles saved in first 'i` iterations by optimizing the loop.
+  //===--------------------------------------------------------------------===//
+  for (unsigned I = 0; I < LoopIterations; ++I) {
+    DepthInfo &MaxDepth = LoopDepth[I];
+    for (auto *MBB : CurrLoop->getBlocks()) {
+      // Clear physical registers Def map.
+      RegDefMaps[PhyRegType].clear();
+      for (MachineInstr &MI : *MBB) {
+        unsigned MIDepth = 0;
+        unsigned MIDepthOpt = 0;
+        bool IsCMOV = CmovInstructions.count(&MI);
+        for (auto &MO : MI.uses()) {
+          // Checks for "isUse()" as "uses()" returns also implicit definitions.
+          if (!MO.isReg() || !MO.isUse())
+            continue;
+          unsigned Reg = MO.getReg();
+          auto &RDM = RegDefMaps[TargetRegisterInfo::isVirtualRegister(Reg)];
+          if (MachineInstr *DefMI = RDM.lookup(Reg)) {
+            OperandToDefMap[&MO] = DefMI;
+            DepthInfo Info = DepthMap.lookup(DefMI);
+            MIDepth = std::max(MIDepth, Info.Depth);
+            if (!IsCMOV)
+              MIDepthOpt = std::max(MIDepthOpt, Info.OptDepth);
+          }
+        }
+
+        if (IsCMOV)
+          MIDepthOpt = getDepthOfOptCmov(
+              DepthMap[OperandToDefMap.lookup(&MI.getOperand(1))].OptDepth,
+              DepthMap[OperandToDefMap.lookup(&MI.getOperand(2))].OptDepth);
+
+        // Iterates over all operands to handle implicit definitions as well.
+        for (auto &MO : MI.operands()) {
+          if (!MO.isReg() || !MO.isDef())
+            continue;
+          unsigned Reg = MO.getReg();
+          RegDefMaps[TargetRegisterInfo::isVirtualRegister(Reg)][Reg] = &MI;
+        }
+
+        unsigned Latency = TSchedModel.computeInstrLatency(&MI);
+        DepthMap[&MI] = {MIDepth += Latency, MIDepthOpt += Latency};
+        MaxDepth.Depth = std::max(MaxDepth.Depth, MIDepth);
+        MaxDepth.OptDepth = std::max(MaxDepth.OptDepth, MIDepthOpt);
+      }
+    }
+  }
+
+  unsigned Diff[LoopIterations] = {LoopDepth[0].Depth - LoopDepth[0].OptDepth,
+                                   LoopDepth[1].Depth - LoopDepth[1].OptDepth};
+
+  //===--------------------------------------------------------------------===//
+  // Step 2: Check if Loop worth to be optimized.
+  // Worth-Optimize-Loop:
+  //   case 1: Diff[1] == Diff[0]
+  //           Critical-path is iteration independent - there is no dependency
+  //           of critical-path instructions on critical-path instructions of
+  //           previous iteration.
+  //           Thus, it is enough to check gain percent of 1st iteration -
+  //           To be conservative, the optimized loop need to have a depth of
+  //           12.5% cycles less than original loop, per iteration.
+  //
+  //   case 2: Diff[1] > Diff[0]
+  //           Critical-path is iteration dependent - there is dependency of
+  //           critical-path instructions on critical-path instructions of
+  //           previous iteration.
+  //           Thus, it is required to check the gradient of the gain - the
+  //           change in Depth-Diff compared to the change in Loop-Depth between
+  //           1st and 2nd iterations.
+  //           To be conservative, the gradient need to be at least 50%.
+  //
+  // If loop is not worth optimizing, remove all CMOV-group-candidates.
+  //===--------------------------------------------------------------------===//
+  bool WorthOptLoop = false;
+  if (Diff[1] == Diff[0])
+    WorthOptLoop = Diff[0] * 8 >= LoopDepth[0].Depth;
+  else if (Diff[1] > Diff[0])
+    WorthOptLoop =
+        (Diff[1] - Diff[0]) * 2 >= (LoopDepth[1].Depth - LoopDepth[0].Depth);
+
+  if (!WorthOptLoop)
+    return false;
+
+  ++NumOfLoopCandidate;
+
+  //===--------------------------------------------------------------------===//
+  // Step 3: Check for each CMOV-group-candidate if it worth to be optimized.
+  // Worth-Optimize-Group:
+  //   Iff it worths to optimize all CMOV instructions in the group.
+  //
+  // Worth-Optimize-CMOV:
+  //   Predicted branch is faster than CMOV by the difference between depth of
+  //   condition operand and depth of taken (predicted) value operand.
+  //   To be conservative, the gain of such CMOV transformation should cover at
+  //   at least 25% of branch-misprediction-penalty.
+  //===--------------------------------------------------------------------===//
+  unsigned MispredictPenalty = TSchedModel.getMCSchedModel()->MispredictPenalty;
+  CmovGroups TempGroups;
+  std::swap(TempGroups, CmovInstGroups);
+  for (auto &Group : TempGroups) {
+    bool WorthOpGroup = true;
+    for (auto *MI : Group) {
+      // Avoid CMOV instruction which value is used as a pointer to load from.
+      // This is another conservative check to avoid converting CMOV instruction
+      // used with tree-search like algorithm, where the branch is unpredicted.
+      auto UIs = MRI->use_instructions(MI->defs().begin()->getReg());
+      if (UIs.begin() != UIs.end() && ++UIs.begin() == UIs.end()) {
+        unsigned Op = UIs.begin()->getOpcode();
+        if (Op == X86::MOV64rm || Op == X86::MOV32rm) {
+          WorthOpGroup = false;
+          break;
+        }
+      }
+
+      unsigned CondCost =
+          DepthMap[OperandToDefMap.lookup(&MI->getOperand(3))].Depth;
+      unsigned ValCost = getDepthOfOptCmov(
+          DepthMap[OperandToDefMap.lookup(&MI->getOperand(1))].Depth,
+          DepthMap[OperandToDefMap.lookup(&MI->getOperand(2))].Depth);
+      if (ValCost > CondCost || (CondCost - ValCost) * 4 < MispredictPenalty) {
+        WorthOpGroup = false;
+        break;
+      }
+    }
+
+    if (WorthOpGroup)
+      CmovInstGroups.push_back(Group);
+  }
+
+  return !CmovInstGroups.empty();
+}
+
+static bool checkEFLAGSLive(MachineInstr *MI) {
+  if (MI->killsRegister(X86::EFLAGS))
+    return false;
+
+  // The EFLAGS operand of MI might be missing a kill marker.
+  // Figure out whether EFLAGS operand should LIVE after MI instruction.
+  MachineBasicBlock *BB = MI->getParent();
+  MachineBasicBlock::iterator ItrMI = MI;
+
+  // Scan forward through BB for a use/def of EFLAGS.
+  for (auto I = std::next(ItrMI), E = BB->end(); I != E; ++I) {
+    if (I->readsRegister(X86::EFLAGS))
+      return true;
+    if (I->definesRegister(X86::EFLAGS))
+      return false;
+  }
+
+  // We hit the end of the block, check whether EFLAGS is live into a successor.
+  for (auto I = BB->succ_begin(), E = BB->succ_end(); I != E; ++I) {
+    if ((*I)->isLiveIn(X86::EFLAGS))
+      return true;
+  }
+
+  return false;
+}
+
+void X86CmovConverterPass::convertCmovInstsToBranches(
+    SmallVectorImpl<MachineInstr *> &Group) const {
+  assert(!Group.empty() && "No CMOV instructions to convert");
+  ++NumOfOptimizedCmovGroups;
+
+  // To convert a CMOVcc instruction, we actually have to insert the diamond
+  // control-flow pattern.  The incoming instruction knows the destination vreg
+  // to set, the condition code register to branch on, the true/false values to
+  // select between, and a branch opcode to use.
+
+  // Before
+  // -----
+  // MBB:
+  //   cond = cmp ...
+  //   v1 = CMOVge t1, f1, cond
+  //   v2 = CMOVlt t2, f2, cond
+  //   v3 = CMOVge v1, f3, cond
+  //
+  // After
+  // -----
+  // MBB:
+  //   cond = cmp ...
+  //   jge %SinkMBB
+  //
+  // FalseMBB:
+  //   jmp %SinkMBB
+  //
+  // SinkMBB:
+  //   %v1 = phi[%f1, %FalseMBB], [%t1, %MBB]
+  //   %v2 = phi[%t2, %FalseMBB], [%f2, %MBB] ; For CMOV with OppCC switch
+  //                                          ; true-value with false-value
+  //   %v3 = phi[%f3, %FalseMBB], [%t1, %MBB] ; Phi instruction cannot use
+  //                                          ; previous Phi instruction result
+
+  MachineInstr &MI = *Group.front();
+  MachineInstr *LastCMOV = Group.back();
+  DebugLoc DL = MI.getDebugLoc();
+  X86::CondCode CC = X86::CondCode(X86::getCondFromCMovOpc(MI.getOpcode()));
+  X86::CondCode OppCC = X86::GetOppositeBranchCondition(CC);
+  MachineBasicBlock *MBB = MI.getParent();
+  MachineFunction::iterator It = ++MBB->getIterator();
+  MachineFunction *F = MBB->getParent();
+  const BasicBlock *BB = MBB->getBasicBlock();
+
+  MachineBasicBlock *FalseMBB = F->CreateMachineBasicBlock(BB);
+  MachineBasicBlock *SinkMBB = F->CreateMachineBasicBlock(BB);
+  F->insert(It, FalseMBB);
+  F->insert(It, SinkMBB);
+
+  // If the EFLAGS register isn't dead in the terminator, then claim that it's
+  // live into the sink and copy blocks.
+  if (checkEFLAGSLive(LastCMOV)) {
+    FalseMBB->addLiveIn(X86::EFLAGS);
+    SinkMBB->addLiveIn(X86::EFLAGS);
+  }
+
+  // Transfer the remainder of BB and its successor edges to SinkMBB.
+  SinkMBB->splice(SinkMBB->begin(), MBB,
+                  std::next(MachineBasicBlock::iterator(LastCMOV)), MBB->end());
+  SinkMBB->transferSuccessorsAndUpdatePHIs(MBB);
+
+  // Add the false and sink blocks as its successors.
+  MBB->addSuccessor(FalseMBB);
+  MBB->addSuccessor(SinkMBB);
+
+  // Create the conditional branch instruction.
+  BuildMI(MBB, DL, TII->get(X86::GetCondBranchFromCond(CC))).addMBB(SinkMBB);
+
+  // Add the sink block to the false block successors.
+  FalseMBB->addSuccessor(SinkMBB);
+
+  MachineInstrBuilder MIB;
+  MachineBasicBlock::iterator MIItBegin = MachineBasicBlock::iterator(MI);
+  MachineBasicBlock::iterator MIItEnd =
+      std::next(MachineBasicBlock::iterator(LastCMOV));
+  MachineBasicBlock::iterator SinkInsertionPoint = SinkMBB->begin();
+  // As we are creating the PHIs, we have to be careful if there is more than
+  // one.  Later CMOVs may reference the results of earlier CMOVs, but later
+  // PHIs have to reference the individual true/false inputs from earlier PHIs.
+  // That also means that PHI construction must work forward from earlier to
+  // later, and that the code must maintain a mapping from earlier PHI's
+  // destination registers, and the registers that went into the PHI.
+  DenseMap<unsigned, std::pair<unsigned, unsigned>> RegRewriteTable;
+
+  for (MachineBasicBlock::iterator MIIt = MIItBegin; MIIt != MIItEnd; ++MIIt) {
+    unsigned DestReg = MIIt->getOperand(0).getReg();
+    unsigned Op1Reg = MIIt->getOperand(1).getReg();
+    unsigned Op2Reg = MIIt->getOperand(2).getReg();
+
+    // If this CMOV we are processing is the opposite condition from the jump we
+    // generated, then we have to swap the operands for the PHI that is going to
+    // be generated.
+    if (X86::getCondFromCMovOpc(MIIt->getOpcode()) == OppCC)
+      std::swap(Op1Reg, Op2Reg);
+
+    auto Op1Itr = RegRewriteTable.find(Op1Reg);
+    if (Op1Itr != RegRewriteTable.end())
+      Op1Reg = Op1Itr->second.first;
+
+    auto Op2Itr = RegRewriteTable.find(Op2Reg);
+    if (Op2Itr != RegRewriteTable.end())
+      Op2Reg = Op2Itr->second.second;
+
+    //  SinkMBB:
+    //   %Result = phi [ %FalseValue, FalseMBB ], [ %TrueValue, MBB ]
+    //  ...
+    MIB = BuildMI(*SinkMBB, SinkInsertionPoint, DL, TII->get(X86::PHI), DestReg)
+              .addReg(Op1Reg)
+              .addMBB(FalseMBB)
+              .addReg(Op2Reg)
+              .addMBB(MBB);
+    (void)MIB;
+    DEBUG(dbgs() << "\tFrom: "; MIIt->dump());
+    DEBUG(dbgs() << "\tTo: "; MIB->dump());
+
+    // Add this PHI to the rewrite table.
+    RegRewriteTable[DestReg] = std::make_pair(Op1Reg, Op2Reg);
+  }
+
+  // Now remove the CMOV(s).
+  MBB->erase(MIItBegin, MIItEnd);
+}
+
+} // End anonymous namespace.
+
+FunctionPass *llvm::createX86CmovConverterPass() {
+  return new X86CmovConverterPass();
+}

llvm/trunk/lib/Target/X86/X86TargetMachine.cpp

bool X86PassConfig::addGlobalInstructionSelect() {
   return false;
 }
 #endif
 
 bool X86PassConfig::addILPOpts() {
   addPass(&EarlyIfConverterID);
   if (EnableMachineCombinerPass)
     addPass(&MachineCombinerID);
+  addPass(createX86CmovConverterPass());
   return true;
 }
 
 bool X86PassConfig::addPreISel() {
   // Only add this pass for 32-bit x86 Windows.
   const Triple &TT = TM->getTargetTriple();
   if (TT.isOSWindows() && TT.getArch() == Triple::x86)
     addPass(createX86WinEHStatePass());

llvm/trunk/test/CodeGen/X86/2008-01-08-SchedulerCrash.ll

-; RUN: llc < %s -march=x86 -mattr=+cmov | FileCheck %s
+; RUN: llc < %s -march=x86 -mattr=+cmov -x86-cmov-converter=false | FileCheck %s
 ;
 ; Test scheduling a multi-use compare. We should neither spill flags
 ; nor clone the compare.
 ; CHECK: cmp
 ; CHECK-NOT: pushf
 ; CHECK: cmov
 ; CHECK-NOT: cmp
 ; CHECK: cmov

llvm/trunk/test/CodeGen/X86/atomic-minmax-i6432.ll

 ; RUN: llc -march=x86 -mattr=+cmov,cx16 -mtriple=i386-pc-linux -verify-machineinstrs < %s | FileCheck %s -check-prefix=LINUX
 ; RUN: llc -march=x86 -mattr=cx16 -mtriple=i386-macosx -relocation-model=pic -verify-machineinstrs < %s | FileCheck %s -check-prefix=PIC
 
 @sc64 = external global i64
 
 define void @atomic_maxmin_i6432() {
 ; LINUX: atomic_maxmin_i6432
   %1 = atomicrmw max  i64* @sc64, i64 5 acquire
 ; LINUX: [[LABEL:.LBB[0-9]+_[0-9]+]]
 ; LINUX: cmpl
 ; LINUX: sbbl
-; LINUX: cmovne
-; LINUX: cmovne
+; LINUX: jne
+; LINUX: jne
 ; LINUX: lock cmpxchg8b
 ; LINUX: jne [[LABEL]]
   %2 = atomicrmw min  i64* @sc64, i64 6 acquire
 ; LINUX: [[LABEL:.LBB[0-9]+_[0-9]+]]
 ; LINUX: cmpl
 ; LINUX: sbbl
-; LINUX: cmovne
-; LINUX: cmovne
+; LINUX: jne
+; LINUX: jne
 ; LINUX: lock cmpxchg8b
 ; LINUX: jne [[LABEL]]
   %3 = atomicrmw umax i64* @sc64, i64 7 acquire
 ; LINUX: [[LABEL:.LBB[0-9]+_[0-9]+]]
 ; LINUX: cmpl
 ; LINUX: sbbl
-; LINUX: cmovne
-; LINUX: cmovne
+; LINUX: jne
+; LINUX: jne
 ; LINUX: lock cmpxchg8b
 ; LINUX: jne [[LABEL]]
   %4 = atomicrmw umin i64* @sc64, i64 8 acquire
 ; LINUX: [[LABEL:.LBB[0-9]+_[0-9]+]]
 ; LINUX: cmpl
 ; LINUX: sbbl
-; LINUX: cmovne
-; LINUX: cmovne
+; LINUX: jne
+; LINUX: jne
 ; LINUX: lock cmpxchg8b
 ; LINUX: jne [[LABEL]]
   ret void
 }
 
 ; rdar://12453106
 @id = internal global i64 0, align 8
 

llvm/trunk/test/CodeGen/X86/atomic128.ll

 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  LBB5_1: ## %atomicrmw.start
 ; CHECK-NEXT:    ## =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    cmpq %rax, %rsi
 ; CHECK-NEXT:    movq %r8, %rcx
 ; CHECK-NEXT:    sbbq %rdx, %rcx
 ; CHECK-NEXT:    setge %cl
 ; CHECK-NEXT:    andb $1, %cl
+; CHECK-NEXT:    movq %rax, %rbx
+; CHECK-NEXT:    jne LBB5_3
+; CHECK-NEXT:  ## BB#2: ## %atomicrmw.start
+; CHECK-NEXT:    ## in Loop: Header=BB5_1 Depth=1
 ; CHECK-NEXT:    movq %rsi, %rbx
-; CHECK-NEXT:    cmovneq %rax, %rbx
+; CHECK-NEXT:  LBB5_3: ## %atomicrmw.start
+; CHECK-NEXT:    ## in Loop: Header=BB5_1 Depth=1
 ; CHECK-NEXT:    testb %cl, %cl
+; CHECK-NEXT:    movq %rdx, %rcx
+; CHECK-NEXT:    jne LBB5_5
+; CHECK-NEXT:  ## BB#4: ## %atomicrmw.start
+; CHECK-NEXT:    ## in Loop: Header=BB5_1 Depth=1
 ; CHECK-NEXT:    movq %r8, %rcx
-; CHECK-NEXT:    cmovneq %rdx, %rcx
+; CHECK-NEXT:  LBB5_5: ## %atomicrmw.start
+; CHECK-NEXT:    ## in Loop: Header=BB5_1 Depth=1
 ; CHECK-NEXT:    lock cmpxchg16b (%rdi)
 ; CHECK-NEXT:    jne LBB5_1
-; CHECK-NEXT:  ## BB#2: ## %atomicrmw.end
+; CHECK-NEXT:  ## BB#6: ## %atomicrmw.end
 ; CHECK-NEXT:    movq %rax, {{.*}}(%rip)
 ; CHECK-NEXT:    movq %rdx, _var+{{.*}}(%rip)
 ; CHECK-NEXT:    popq %rbx
 ; CHECK-NEXT:    retq
   %val = atomicrmw min i128* %p, i128 %bits seq_cst
   store i128 %val, i128* @var, align 16
   ret void
 }

 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  LBB6_1: ## %atomicrmw.start
 ; CHECK-NEXT:    ## =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    cmpq %rsi, %rax
 ; CHECK-NEXT:    movq %rdx, %rcx
 ; CHECK-NEXT:    sbbq %r8, %rcx
 ; CHECK-NEXT:    setge %cl
 ; CHECK-NEXT:    andb $1, %cl
+; CHECK-NEXT:    movq %rax, %rbx
+; CHECK-NEXT:    jne LBB6_3
+; CHECK-NEXT:  ## BB#2: ## %atomicrmw.start
+; CHECK-NEXT:    ## in Loop: Header=BB6_1 Depth=1
 ; CHECK-NEXT:    movq %rsi, %rbx
-; CHECK-NEXT:    cmovneq %rax, %rbx
+; CHECK-NEXT:  LBB6_3: ## %atomicrmw.start
+; CHECK-NEXT:    ## in Loop: Header=BB6_1 Depth=1
 ; CHECK-NEXT:    testb %cl, %cl
+; CHECK-NEXT:    movq %rdx, %rcx
+; CHECK-NEXT:    jne LBB6_5
+; CHECK-NEXT:  ## BB#4: ## %atomicrmw.start
+; CHECK-NEXT:    ## in Loop: Header=BB6_1 Depth=1
 ; CHECK-NEXT:    movq %r8, %rcx
-; CHECK-NEXT:    cmovneq %rdx, %rcx
+; CHECK-NEXT:  LBB6_5: ## %atomicrmw.start
+; CHECK-NEXT:    ## in Loop: Header=BB6_1 Depth=1
 ; CHECK-NEXT:    lock cmpxchg16b (%rdi)
 ; CHECK-NEXT:    jne LBB6_1
-; CHECK-NEXT:  ## BB#2: ## %atomicrmw.end
+; CHECK-NEXT:  ## BB#6: ## %atomicrmw.end
 ; CHECK-NEXT:    movq %rax, {{.*}}(%rip)
 ; CHECK-NEXT:    movq %rdx, _var+{{.*}}(%rip)
 ; CHECK-NEXT:    popq %rbx
 ; CHECK-NEXT:    retq
   %val = atomicrmw max i128* %p, i128 %bits seq_cst
   store i128 %val, i128* @var, align 16
   ret void
 }

 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  LBB7_1: ## %atomicrmw.start
 ; CHECK-NEXT:    ## =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    cmpq %rax, %rsi
 ; CHECK-NEXT:    movq %r8, %rcx
 ; CHECK-NEXT:    sbbq %rdx, %rcx
 ; CHECK-NEXT:    setae %cl
 ; CHECK-NEXT:    andb $1, %cl
+; CHECK-NEXT:    movq %rax, %rbx
+; CHECK-NEXT:    jne LBB7_3
+; CHECK-NEXT:  ## BB#2: ## %atomicrmw.start
+; CHECK-NEXT:    ## in Loop: Header=BB7_1 Depth=1
 ; CHECK-NEXT:    movq %rsi, %rbx
-; CHECK-NEXT:    cmovneq %rax, %rbx
+; CHECK-NEXT:  LBB7_3: ## %atomicrmw.start
+; CHECK-NEXT:    ## in Loop: Header=BB7_1 Depth=1
 ; CHECK-NEXT:    testb %cl, %cl
+; CHECK-NEXT:    movq %rdx, %rcx
+; CHECK-NEXT:    jne LBB7_5
+; CHECK-NEXT:  ## BB#4: ## %atomicrmw.start
+; CHECK-NEXT:    ## in Loop: Header=BB7_1 Depth=1
 ; CHECK-NEXT:    movq %r8, %rcx
-; CHECK-NEXT:    cmovneq %rdx, %rcx
+; CHECK-NEXT:  LBB7_5: ## %atomicrmw.start
+; CHECK-NEXT:    ## in Loop: Header=BB7_1 Depth=1
 ; CHECK-NEXT:    lock cmpxchg16b (%rdi)
 ; CHECK-NEXT:    jne LBB7_1
-; CHECK-NEXT:  ## BB#2: ## %atomicrmw.end
+; CHECK-NEXT:  ## BB#6: ## %atomicrmw.end
 ; CHECK-NEXT:    movq %rax, {{.*}}(%rip)
 ; CHECK-NEXT:    movq %rdx, _var+{{.*}}(%rip)
 ; CHECK-NEXT:    popq %rbx
 ; CHECK-NEXT:    retq
   %val = atomicrmw umin i128* %p, i128 %bits seq_cst
   store i128 %val, i128* @var, align 16
   ret void
 }

 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  LBB8_1: ## %atomicrmw.start
 ; CHECK-NEXT:    ## =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    cmpq %rax, %rsi
 ; CHECK-NEXT:    movq %r8, %rcx
 ; CHECK-NEXT:    sbbq %rdx, %rcx
 ; CHECK-NEXT:    setb %cl
 ; CHECK-NEXT:    andb $1, %cl
+; CHECK-NEXT:    movq %rax, %rbx
+; CHECK-NEXT:    jne LBB8_3
+; CHECK-NEXT:  ## BB#2: ## %atomicrmw.start
+; CHECK-NEXT:    ## in Loop: Header=BB8_1 Depth=1
 ; CHECK-NEXT:    movq %rsi, %rbx
-; CHECK-NEXT:    cmovneq %rax, %rbx
+; CHECK-NEXT:  LBB8_3: ## %atomicrmw.start
+; CHECK-NEXT:    ## in Loop: Header=BB8_1 Depth=1
 ; CHECK-NEXT:    testb %cl, %cl
+; CHECK-NEXT:    movq %rdx, %rcx
+; CHECK-NEXT:    jne LBB8_5
+; CHECK-NEXT:  ## BB#4: ## %atomicrmw.start
+; CHECK-NEXT:    ## in Loop: Header=BB8_1 Depth=1
 ; CHECK-NEXT:    movq %r8, %rcx
-; CHECK-NEXT:    cmovneq %rdx, %rcx
+; CHECK-NEXT:  LBB8_5: ## %atomicrmw.start
+; CHECK-NEXT:    ## in Loop: Header=BB8_1 Depth=1
 ; CHECK-NEXT:    lock cmpxchg16b (%rdi)
 ; CHECK-NEXT:    jne LBB8_1
-; CHECK-NEXT:  ## BB#2: ## %atomicrmw.end
+; CHECK-NEXT:  ## BB#6: ## %atomicrmw.end
 ; CHECK-NEXT:    movq %rax, {{.*}}(%rip)
 ; CHECK-NEXT:    movq %rdx, _var+{{.*}}(%rip)
 ; CHECK-NEXT:    popq %rbx
 ; CHECK-NEXT:    retq
   %val = atomicrmw umax i128* %p, i128 %bits seq_cst
   store i128 %val, i128* @var, align 16
   ret void
 }

llvm/trunk/test/CodeGen/X86/x86-cmov-converter.ll

+; RUN: llc -mtriple=x86_64-pc-linux -x86-cmov-converter=true -verify-machineinstrs < %s | FileCheck %s
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;; This test checks that x86-cmov-converter optimization transform CMOV
+;; instruction into branches when it is profitable.
+;; There are 5 cases below:
+;;   1. CmovInCriticalPath:
+;;        CMOV depends on the condition and it is in the hot path.
+;;        Thus, it worths transforming.
+;;
+;;   2. CmovNotInCriticalPath:
+;;        similar test like in (1), just that CMOV is not in the hot path.
+;;        Thus, it does not worth transforming.
+;;
+;;   3. MaxIndex:
+;;        Maximum calculation algorithm that is looking for the max index,
+;;        calculating CMOV value is cheaper than calculating CMOV condition.
+;;        Thus, it worths transforming.
+;;
+;;   4. MaxValue:
+;;        Maximum calculation algorithm that is looking for the max value,
+;;        calculating CMOV value is not cheaper than calculating CMOV condition.
+;;        Thus, it does not worth transforming.
+;;
+;;   5. BinarySearch:
+;;        Usually, binary search CMOV is not predicted.
+;;        Thus, it does not worth transforming.
+;;
+;; Test was created using the following command line:
+;; > clang -S -O2 -m64 -fno-vectorize -fno-unroll-loops -emit-llvm foo.c -o -
+;; Where foo.c is:
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;;void CmovInHotPath(int n, int a, int b, int *c, int *d) {
+;;  for (int i = 0; i < n; i++) {
+;;    int t = c[i];
+;;    if (c[i] * a > b)
+;;      t = 10;
+;;    c[i] = t;
+;;  }
+;;}
+;;
+;;
+;;void CmovNotInHotPath(int n, int a, int b, int *c, int *d) {
+;;  for (int i = 0; i < n; i++) {
+;;    int t = c[i];
+;;    if (c[i] * a > b)
+;;      t = 10;
+;;    c[i] = t;
+;;    d[i] /= b;
+;;  }
+;;}
+;;
+;;
+;;int MaxIndex(int n, int *a) {
+;;  int t = 0;
+;;  for (int i = 1; i < n; i++) {
+;;    if (a[i] > a[t])
+;;      t = i;
+;;  }
+;;  return a[t];
+;;}
+;;
+;;
+;;int MaxValue(int n, int *a) {
+;;  int t = a[0];
+;;  for (int i = 1; i < n; i++) {
+;;    if (a[i] > t)
+;;      t = a[i];
+;;  }
+;;  return t;
+;;}
+;;
+;;typedef struct Node Node;
+;;struct Node {
+;;  unsigned Val;
+;;  Node *Right;
+;;  Node *Left;
+;;};
+;;
+;;unsigned BinarySearch(unsigned Mask, Node *Curr, Node *Next) {
+;;  while (Curr->Val > Next->Val) {
+;;    Curr = Next;
+;;    if (Mask & (0x1 << Curr->Val))
+;;      Next = Curr->Right;
+;;    else
+;;      Next = Curr->Left;
+;;  }
+;;  return Curr->Val;
+;;}
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+
+%struct.Node = type { i32, %struct.Node*, %struct.Node* }
+
+; CHECK-LABEL: CmovInHotPath
+; CHECK-NOT: cmov
+; CHECK: jg
+
+define void @CmovInHotPath(i32 %n, i32 %a, i32 %b, i32* nocapture %c, i32* nocapture readnone %d) #0 {
+entry:
+  %cmp14 = icmp sgt i32 %n, 0
+  br i1 %cmp14, label %for.body.preheader, label %for.cond.cleanup
+
+for.body.preheader:                               ; preds = %entry
+  %wide.trip.count = zext i32 %n to i64
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
+  %arrayidx = getelementptr inbounds i32, i32* %c, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %mul = mul nsw i32 %0, %a
+  %cmp3 = icmp sgt i32 %mul, %b
+  %. = select i1 %cmp3, i32 10, i32 %0
+  store i32 %., i32* %arrayidx, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+; CHECK-LABEL: CmovNotInHotPath
+; CHECK: cmovg
+
+define void @CmovNotInHotPath(i32 %n, i32 %a, i32 %b, i32* nocapture %c, i32* nocapture %d) #0 {
+entry:
+  %cmp18 = icmp sgt i32 %n, 0
+  br i1 %cmp18, label %for.body.preheader, label %for.cond.cleanup
+
+for.body.preheader:                               ; preds = %entry
+  %wide.trip.count = zext i32 %n to i64
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
+  %arrayidx = getelementptr inbounds i32, i32* %c, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %mul = mul nsw i32 %0, %a
+  %cmp3 = icmp sgt i32 %mul, %b
+  %. = select i1 %cmp3, i32 10, i32 %0
+  store i32 %., i32* %arrayidx, align 4
+  %arrayidx7 = getelementptr inbounds i32, i32* %d, i64 %indvars.iv
+  %1 = load i32, i32* %arrayidx7, align 4
+  %div = sdiv i32 %1, %b
+  store i32 %div, i32* %arrayidx7, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+; CHECK-LABEL: MaxIndex
+; CHECK-NOT: cmov
+; CHECK: jg
+
+define i32 @MaxIndex(i32 %n, i32* nocapture readonly %a) #0 {
+entry:
+  %cmp14 = icmp sgt i32 %n, 1
+  br i1 %cmp14, label %for.body.preheader, label %for.cond.cleanup
+
+for.body.preheader:                               ; preds = %entry
+  %wide.trip.count = zext i32 %n to i64
+  br label %for.body
+
+for.cond.cleanup.loopexit:                        ; preds = %for.body
+  %phitmp = sext i32 %i.0.t.0 to i64
+  br label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
+  %t.0.lcssa = phi i64 [ 0, %entry ], [ %phitmp, %for.cond.cleanup.loopexit ]
+  %arrayidx5 = getelementptr inbounds i32, i32* %a, i64 %t.0.lcssa
+  %0 = load i32, i32* %arrayidx5, align 4
+  ret i32 %0
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 1, %for.body.preheader ]
+  %t.015 = phi i32 [ %i.0.t.0, %for.body ], [ 0, %for.body.preheader ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
+  %1 = load i32, i32* %arrayidx, align 4
+  %idxprom1 = sext i32 %t.015 to i64
+  %arrayidx2 = getelementptr inbounds i32, i32* %a, i64 %idxprom1
+  %2 = load i32, i32* %arrayidx2, align 4
+  %cmp3 = icmp sgt i32 %1, %2
+  %3 = trunc i64 %indvars.iv to i32
+  %i.0.t.0 = select i1 %cmp3, i32 %3, i32 %t.015
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count
+  br i1 %exitcond, label %for.cond.cleanup.loopexit, label %for.body
+}
+
+; CHECK-LABEL: MaxValue
+; CHECK-NOT: jg
+; CHECK: cmovg
+
+define i32 @MaxValue(i32 %n, i32* nocapture readonly %a) #0 {
+entry:
+  %0 = load i32, i32* %a, align 4
+  %cmp13 = icmp sgt i32 %n, 1
+  br i1 %cmp13, label %for.body.preheader, label %for.cond.cleanup
+
+for.body.preheader:                               ; preds = %entry
+  %wide.trip.count = zext i32 %n to i64
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  %t.0.lcssa = phi i32 [ %0, %entry ], [ %.t.0, %for.body ]
+  ret i32 %t.0.lcssa
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 1, %for.body.preheader ]
+  %t.014 = phi i32 [ %.t.0, %for.body ], [ %0, %for.body.preheader ]
+  %arrayidx1 = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
+  %1 = load i32, i32* %arrayidx1, align 4
+  %cmp2 = icmp sgt i32 %1, %t.014
+  %.t.0 = select i1 %cmp2, i32 %1, i32 %t.014
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+; CHECK-LABEL: BinarySearch
+; CHECK: cmov
+
+define i32 @BinarySearch(i32 %Mask, %struct.Node* nocapture readonly %Curr, %struct.Node* nocapture readonly %Next) #0 {
+entry:
+  %Val8 = getelementptr inbounds %struct.Node, %struct.Node* %Curr, i64 0, i32 0
+  %0 = load i32, i32* %Val8, align 8
+  %Val19 = getelementptr inbounds %struct.Node, %struct.Node* %Next, i64 0, i32 0
+  %1 = load i32, i32* %Val19, align 8
+  %cmp10 = icmp ugt i32 %0, %1
+  br i1 %cmp10, label %while.body, label %while.end
+
+while.body:                                       ; preds = %entry, %while.body
+  %2 = phi i32 [ %4, %while.body ], [ %1, %entry ]
+  %Next.addr.011 = phi %struct.Node* [ %3, %while.body ], [ %Next, %entry ]
+  %shl = shl i32 1, %2
+  %and = and i32 %shl, %Mask
+  %tobool = icmp eq i32 %and, 0
+  %Left = getelementptr inbounds %struct.Node, %struct.Node* %Next.addr.011, i64 0, i32 2
+  %Right = getelementptr inbounds %struct.Node, %struct.Node* %Next.addr.011, i64 0, i32 1
+  %Left.sink = select i1 %tobool, %struct.Node** %Left, %struct.Node** %Right
+  %3 = load %struct.Node*, %struct.Node** %Left.sink, align 8
+  %Val1 = getelementptr inbounds %struct.Node, %struct.Node* %3, i64 0, i32 0
+  %4 = load i32, i32* %Val1, align 8
+  %cmp = icmp ugt i32 %2, %4
+  br i1 %cmp, label %while.body, label %while.end
+
+while.end:                                        ; preds = %while.body, %entry
+  %.lcssa = phi i32 [ %0, %entry ], [ %2, %while.body ]
+  ret i32 %.lcssa
+}
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;; The following test checks that x86-cmov-converter optimization transforms
+;; CMOV instructions into branch correctly.
+;;
+;; MBB:
+;;   cond = cmp ...
+;;   v1 = CMOVgt t1, f1, cond
+;;   v2 = CMOVle s1, f2, cond
+;;
+;; Where: t1 = 11, f1 = 22, f2 = a
+;;
+;; After CMOV transformation
+;; -------------------------
+;; MBB:
+;;   cond = cmp ...
+;;   ja %SinkMBB
+;;
+;; FalseMBB:
+;;   jmp %SinkMBB
+;;
+;; SinkMBB:
+;;   %v1 = phi[%f1, %FalseMBB], [%t1, %MBB]
+;;   %v2 = phi[%f1, %FalseMBB], [%f2, %MBB] ; For CMOV with OppCC switch
+;;                                          ; true-value with false-value
+;;                                          ; Phi instruction cannot use
+;;                                          ; previous Phi instruction result
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+
+; CHECK-LABEL: Transform
+; CHECK-NOT: cmov
+; CHECK:         divl    [[a:%[0-9a-z]*]]
+; CHECK:         cmpl    [[a]], %eax
+; CHECK:         movl    $11, [[s1:%[0-9a-z]*]]
+; CHECK:         movl    [[a]], [[s2:%[0-9a-z]*]]
+; CHECK:         ja      [[SinkBB:.*]]
+; CHECK: [[FalseBB:.*]]:
+; CHECK:         movl    $22, [[s1]]
+; CHECK:         movl    $22, [[s2]]
+; CHECK: [[SinkBB]]:
+; CHECK:         ja
+
+define void @Transform(i32 *%arr, i32 *%arr2, i32 %a, i32 %b, i32 %c, i32 %n) #0 {
+entry:
+  %cmp10 = icmp ugt i32 0, %n
+  br i1 %cmp10, label %while.body, label %while.end
+
+while.body:                                       ; preds = %entry, %while.body
+  %i = phi i32 [ %i_inc, %while.body ], [ 0, %entry ]
+  %arr_i = getelementptr inbounds i32, i32* %arr, i32 %i
+  %x = load i32, i32* %arr_i, align 4
+  %div = udiv i32 %x, %a
+  %cond = icmp ugt i32 %div, %a
+  %condOpp = icmp ule i32 %div, %a
+  %s1 = select i1 %cond, i32 11, i32 22
+  %s2 = select i1 %condOpp, i32 %s1, i32 %a
+  %sum = urem i32 %s1, %s2
+  store i32 %sum, i32* %arr_i, align 4
+  %i_inc = add i32 %i, 1
+  %cmp = icmp ugt i32 %i_inc, %n
+  br i1 %cmp, label %while.body, label %while.end
+
+while.end:                                        ; preds = %while.body, %entry
+  ret void
+}
+
+attributes #0 = {"target-cpu"="x86-64"}