Optimized FCMP_OEQ and FCMP_UNE for x86.

Where previously LLVM might emit code like this:

        ucomisd %xmm1, %xmm0
        setne   %al
        setp    %cl
        orb     %al, %cl
        jne     .LBB4_2

it now emits this:

        ucomisd %xmm1, %xmm0
        jne     .LBB4_2
        jp      .LBB4_2

It has fewer instructions and uses fewer registers, but it does
have more branches. And in the case that this code is followed by
a non-fallthrough edge, it may be followed by a jmp instruction,
resulting in three branch instructions in sequence. Some effort
is made to avoid this situation.

To achieve this, X86ISelLowering.cpp now recognizes FCMP_OEQ and
FCMP_UNE in lowered form, and replace them with code that emits
two branches, except in the case where it would require converting
a fall-through edge to an explicit branch.

Also, X86InstrInfo.cpp's branch analysis and transform code now
knows now to handle blocks with multiple conditional branches. It
uses loops instead of having fixed checks for up to two
instructions. It can now analyze and transform code generated
from FCMP_OEQ and FCMP_UNE.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@57873 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 214 insertions, 101 deletions

diff --git a/lib/CodeGen/IfConversion.cpp b/lib/CodeGen/IfConversion.cpp
index 38fce9b..a83d7f1 100644
--- a/lib/CodeGen/IfConversion.cpp
+++ b/lib/CodeGen/IfConversion.cpp
@@ -849,7 +849,8 @@ bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {
   }
 
   if (Kind == ICSimpleFalse)
-    TII->ReverseBranchCondition(Cond);
+    if (TII->ReverseBranchCondition(Cond))
+      assert(false && "Unable to reverse branch condition!");
 
   if (CvtBBI->BB->pred_size() > 1) {
     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
@@ -914,21 +915,23 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
   }
 
   if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
-    TII->ReverseBranchCondition(Cond);
+    if (TII->ReverseBranchCondition(Cond))
+      assert(false && "Unable to reverse branch condition!");
 
   if (Kind == ICTriangleRev || Kind == ICTriangleFRev) {
-    ReverseBranchCondition(*CvtBBI);
-    // BB has been changed, modify its predecessors (except for this
-    // one) so they don't get ifcvt'ed based on bad intel.
-    for (MachineBasicBlock::pred_iterator PI = CvtBBI->BB->pred_begin(),
-           E = CvtBBI->BB->pred_end(); PI != E; ++PI) {
-      MachineBasicBlock *PBB = *PI;
-      if (PBB == BBI.BB)
-        continue;
-      BBInfo &PBBI = BBAnalysis[PBB->getNumber()];
-      if (PBBI.IsEnqueued) {
-        PBBI.IsAnalyzed = false;
-        PBBI.IsEnqueued = false;
+    if (ReverseBranchCondition(*CvtBBI)) {
+      // BB has been changed, modify its predecessors (except for this
+      // one) so they don't get ifcvt'ed based on bad intel.
+      for (MachineBasicBlock::pred_iterator PI = CvtBBI->BB->pred_begin(),
+             E = CvtBBI->BB->pred_end(); PI != E; ++PI) {
+        MachineBasicBlock *PBB = *PI;
+        if (PBB == BBI.BB)
+          continue;
+        BBInfo &PBBI = BBAnalysis[PBB->getNumber()];
+        if (PBBI.IsEnqueued) {
+          PBBI.IsAnalyzed = false;
+          PBBI.IsEnqueued = false;
+        }
       }
     }
   }
@@ -1028,7 +1031,8 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
   BBInfo *BBI1 = &TrueBBI;
   BBInfo *BBI2 = &FalseBBI;
   SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
-  TII->ReverseBranchCondition(RevCond);
+  if (TII->ReverseBranchCondition(RevCond))
+    assert(false && "Unable to reverse branch condition!");
   SmallVector<MachineOperand, 4> *Cond1 = &BBI.BrCond;
   SmallVector<MachineOperand, 4> *Cond2 = &RevCond;
 
diff --git a/lib/Target/X86/X86ISelLowering.cpp b/lib/Target/X86/X86ISelLowering.cpp
index 05db7cb..ebf9eec 100644
--- a/lib/Target/X86/X86ISelLowering.cpp
+++ b/lib/Target/X86/X86ISelLowering.cpp
@@ -5100,6 +5100,71 @@ SDValue X86TargetLowering::LowerBRCOND(SDValue Op, SelectionDAG &DAG) {
       Cond = Cmp;
       addTest = false;
     }
+  // Also, recognize the pattern generated by an FCMP_UNE. We can emit
+  // two branches instead of an explicit OR instruction with a
+  // separate test.
+  } else if (Cond.getOpcode() == ISD::OR &&
+             Cond.hasOneUse() &&
+             Cond.getOperand(0).getOpcode() == X86ISD::SETCC &&
+             Cond.getOperand(0).hasOneUse() &&
+             Cond.getOperand(1).getOpcode() == X86ISD::SETCC &&
+             Cond.getOperand(1).hasOneUse()) {
+    SDValue Cmp = Cond.getOperand(0).getOperand(1);
+    unsigned Opc = Cmp.getOpcode();
+    if (Cmp == Cond.getOperand(1).getOperand(1) &&
+        (Opc == X86ISD::CMP ||
+         Opc == X86ISD::COMI ||
+         Opc == X86ISD::UCOMI)) {
+      CC = Cond.getOperand(0).getOperand(0);
+      Chain = DAG.getNode(X86ISD::BRCOND, Op.getValueType(),
+                          Chain, Dest, CC, Cmp);
+      CC = Cond.getOperand(1).getOperand(0);
+      Cond = Cmp;
+      addTest = false;
+    }
+  // Also, recognize the pattern generated by an FCMP_OEQ. We can emit
+  // two branches instead of an explicit AND instruction with a
+  // separate test. However, we only do this if this block doesn't
+  // have a fall-through edge, because this requires an explicit
+  // jmp when the condition is false.
+  } else if (Cond.getOpcode() == ISD::AND &&
+             Cond.hasOneUse() &&
+             Cond.getOperand(0).getOpcode() == X86ISD::SETCC &&
+             Cond.getOperand(0).hasOneUse() &&
+             Cond.getOperand(1).getOpcode() == X86ISD::SETCC &&
+             Cond.getOperand(1).hasOneUse()) {
+    SDValue Cmp = Cond.getOperand(0).getOperand(1);
+    unsigned Opc = Cmp.getOpcode();
+    if (Cmp == Cond.getOperand(1).getOperand(1) &&
+        (Opc == X86ISD::CMP ||
+         Opc == X86ISD::COMI ||
+         Opc == X86ISD::UCOMI) &&
+        Op.getNode()->hasOneUse()) {
+      X86::CondCode CCode =
+        (X86::CondCode)Cond.getOperand(0).getConstantOperandVal(0);
+      CCode = X86::GetOppositeBranchCondition(CCode);
+      CC = DAG.getConstant(CCode, MVT::i8);
+      SDValue User = SDValue(*Op.getNode()->use_begin(), 0);
+      // Look for an unconditional branch following this conditional branch.
+      // We need this because we need to reverse the successors in order
+      // to implement FCMP_OEQ.
+      if (User.getOpcode() == ISD::BR) {
+        SDValue FalseBB = User.getOperand(1);
+        SDValue NewBR =
+          DAG.UpdateNodeOperands(User, User.getOperand(0), Dest);
+        assert(NewBR == User);
+        Dest = FalseBB;
+
+        Chain = DAG.getNode(X86ISD::BRCOND, Op.getValueType(),
+                            Chain, Dest, CC, Cmp);
+        X86::CondCode CCode =
+          (X86::CondCode)Cond.getOperand(1).getConstantOperandVal(0);
+        CCode = X86::GetOppositeBranchCondition(CCode);
+        CC = DAG.getConstant(CCode, MVT::i8);
+        Cond = Cmp;
+        addTest = false;
+      }
+    }
   }
 
   if (addTest) {
@@ -5107,7 +5172,7 @@ SDValue X86TargetLowering::LowerBRCOND(SDValue Op, SelectionDAG &DAG) {
     Cond= DAG.getNode(X86ISD::CMP, MVT::i32, Cond, DAG.getConstant(0, MVT::i8));
   }
   return DAG.getNode(X86ISD::BRCOND, Op.getValueType(),
-                     Chain, Op.getOperand(2), CC, Cond);
+                     Chain, Dest, CC, Cond);
 }
 
 
diff --git a/lib/Target/X86/X86InstrInfo.cpp b/lib/Target/X86/X86InstrInfo.cpp
index 84e113f..2db1448 100644
--- a/lib/Target/X86/X86InstrInfo.cpp
+++ b/lib/Target/X86/X86InstrInfo.cpp
@@ -1455,88 +1455,101 @@ bool X86InstrInfo::AnalyzeBranch(MachineBasicBlock &MBB,
                                  MachineBasicBlock *&TBB,
                                  MachineBasicBlock *&FBB,
                                  SmallVectorImpl<MachineOperand> &Cond) const {
-  // If the block has no terminators, it just falls into the block after it.
+  // Start from the bottom of the block and work up, examining the
+  // terminator instructions.
   MachineBasicBlock::iterator I = MBB.end();
-  if (I == MBB.begin() || !isBrAnalysisUnpredicatedTerminator(--I, *this))
-    return false;
-
-  // Get the last instruction in the block.
-  MachineInstr *LastInst = I;
-  
-  // If there is only one terminator instruction, process it.
-  if (I == MBB.begin() || !isBrAnalysisUnpredicatedTerminator(--I, *this)) {
-    if (!LastInst->getDesc().isBranch())
+  while (I != MBB.begin()) {
+    --I;
+    // Working from the bottom, when we see a non-terminator
+    // instruction, we're done.
+    if (!isBrAnalysisUnpredicatedTerminator(I, *this))
+      break;
+    // A terminator that isn't a branch can't easily be handled
+    // by this analysis.
+    if (!I->getDesc().isBranch())
       return true;
-    
-    // If the block ends with a branch there are 3 possibilities:
-    // it's an unconditional, conditional, or indirect branch.
-    
-    if (LastInst->getOpcode() == X86::JMP) {
-      TBB = LastInst->getOperand(0).getMBB();
-      return false;
+    // Handle unconditional branches.
+    if (I->getOpcode() == X86::JMP) {
+      // If the block has any instructions after a JMP, delete them.
+      while (next(I) != MBB.end())
+        next(I)->eraseFromParent();
+      Cond.clear();
+      FBB = 0;
+      // Delete the JMP if it's equivalent to a fall-through.
+      if (MBB.isLayoutSuccessor(I->getOperand(0).getMBB())) {
+        TBB = 0;
+        I->eraseFromParent();
+        I = MBB.end();
+        continue;
+      }
+      // TBB is used to indicate the unconditinal destination.
+      TBB = I->getOperand(0).getMBB();
+      continue;
     }
-    X86::CondCode BranchCode = GetCondFromBranchOpc(LastInst->getOpcode());
+    // Handle conditional branches.
+    X86::CondCode BranchCode = GetCondFromBranchOpc(I->getOpcode());
     if (BranchCode == X86::COND_INVALID)
       return true;  // Can't handle indirect branch.
-
-    // Otherwise, block ends with fall-through condbranch.
-    TBB = LastInst->getOperand(0).getMBB();
-    Cond.push_back(MachineOperand::CreateImm(BranchCode));
-    return false;
-  }
-  
-  // Get the instruction before it if it's a terminator.
-  MachineInstr *SecondLastInst = I;
-  
-  // If there are three terminators, we don't know what sort of block this is.
-  if (SecondLastInst && I != MBB.begin() &&
-      isBrAnalysisUnpredicatedTerminator(--I, *this))
-    return true;
-
-  // If the block ends with X86::JMP and a conditional branch, handle it.
-  X86::CondCode BranchCode = GetCondFromBranchOpc(SecondLastInst->getOpcode());
-  if (BranchCode != X86::COND_INVALID && LastInst->getOpcode() == X86::JMP) {
-    TBB = SecondLastInst->getOperand(0).getMBB();
-    Cond.push_back(MachineOperand::CreateImm(BranchCode));
-    FBB = LastInst->getOperand(0).getMBB();
-    return false;
-  }
-
-  // If the block ends with two X86::JMPs, handle it.  The second one is not
-  // executed, so remove it.
-  if (SecondLastInst->getOpcode() == X86::JMP && 
-      LastInst->getOpcode() == X86::JMP) {
-    TBB = SecondLastInst->getOperand(0).getMBB();
-    I = LastInst;
-    I->eraseFromParent();
-    return false;
+    // Working from the bottom, handle the first conditional branch.
+    if (Cond.empty()) {
+      FBB = TBB;
+      TBB = I->getOperand(0).getMBB();
+      Cond.push_back(MachineOperand::CreateImm(BranchCode));
+      continue;
+    }
+    // Handle subsequent conditional branches. Only handle the case
+    // where all conditional branches branch to the same destination
+    // and their condition opcodes fit one of the special
+    // multi-branch idioms.
+    assert(Cond.size() == 1);
+    assert(TBB);
+    // Only handle the case where all conditional branches branch to
+    // the same destination.
+    if (TBB != I->getOperand(0).getMBB())
+      return true;
+    X86::CondCode OldBranchCode = (X86::CondCode)Cond[0].getImm();
+    // If the conditions are the same, we can leave them alone.
+    if (OldBranchCode == BranchCode)
+      continue;
+    // If they differ, see if they fit one of the known patterns.
+    // Theoretically we could handle more patterns here, but
+    // we shouldn't expect to see them if instruction selection
+    // has done a reasonable job.
+    if ((OldBranchCode == X86::COND_NP &&
+         BranchCode == X86::COND_E) ||
+        (OldBranchCode == X86::COND_E &&
+         BranchCode == X86::COND_NP))
+      BranchCode = X86::COND_NP_OR_E;
+    else if ((OldBranchCode == X86::COND_P &&
+              BranchCode == X86::COND_NE) ||
+             (OldBranchCode == X86::COND_NE &&
+              BranchCode == X86::COND_P))
+      BranchCode = X86::COND_NE_OR_P;
+    else
+      return true;
+    // Update the MachineOperand.
+    Cond[0].setImm(BranchCode);
   }
 
-  // Otherwise, can't handle this.
-  return true;
+  return false;
 }
 
 unsigned X86InstrInfo::RemoveBranch(MachineBasicBlock &MBB) const {
   MachineBasicBlock::iterator I = MBB.end();
-  if (I == MBB.begin()) return 0;
-  --I;
-  if (I->getOpcode() != X86::JMP && 
-      GetCondFromBranchOpc(I->getOpcode()) == X86::COND_INVALID)
-    return 0;
-  
-  // Remove the branch.
-  I->eraseFromParent();
-  
-  I = MBB.end();
-  
-  if (I == MBB.begin()) return 1;
-  --I;
-  if (GetCondFromBranchOpc(I->getOpcode()) == X86::COND_INVALID)
-    return 1;
+  unsigned Count = 0;
+
+  while (I != MBB.begin()) {
+    --I;
+    if (I->getOpcode() != X86::JMP &&
+        GetCondFromBranchOpc(I->getOpcode()) == X86::COND_INVALID)
+      break;
+    // Remove the branch.
+    I->eraseFromParent();
+    I = MBB.end();
+    ++Count;
+  }
   
-  // Remove the branch.
-  I->eraseFromParent();
-  return 2;
+  return Count;
 }
 
 static const MachineInstrBuilder &X86InstrAddOperand(MachineInstrBuilder &MIB,
@@ -1571,23 +1584,43 @@ X86InstrInfo::InsertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
   assert((Cond.size() == 1 || Cond.size() == 0) &&
          "X86 branch conditions have one component!");
 
-  if (FBB == 0) { // One way branch.
-    if (Cond.empty()) {
-      // Unconditional branch?
-      BuildMI(&MBB, get(X86::JMP)).addMBB(TBB);
-    } else {
-      // Conditional branch.
-      unsigned Opc = GetCondBranchFromCond((X86::CondCode)Cond[0].getImm());
-      BuildMI(&MBB, get(Opc)).addMBB(TBB);
-    }
+  if (Cond.empty()) {
+    // Unconditional branch?
+    assert(!FBB && "Unconditional branch with multiple successors!");
+    BuildMI(&MBB, get(X86::JMP)).addMBB(TBB);
     return 1;
   }
-  
-  // Two-way Conditional branch.
-  unsigned Opc = GetCondBranchFromCond((X86::CondCode)Cond[0].getImm());
-  BuildMI(&MBB, get(Opc)).addMBB(TBB);
-  BuildMI(&MBB, get(X86::JMP)).addMBB(FBB);
-  return 2;
+
+  // Conditional branch.
+  unsigned Count = 0;
+  X86::CondCode CC = (X86::CondCode)Cond[0].getImm();
+  switch (CC) {
+  case X86::COND_NP_OR_E:
+    // Synthesize NP_OR_E with two branches.
+    BuildMI(&MBB, get(X86::JNP)).addMBB(TBB);
+    ++Count;
+    BuildMI(&MBB, get(X86::JE)).addMBB(TBB);
+    ++Count;
+    break;
+  case X86::COND_NE_OR_P:
+    // Synthesize NE_OR_P with two branches.
+    BuildMI(&MBB, get(X86::JNE)).addMBB(TBB);
+    ++Count;
+    BuildMI(&MBB, get(X86::JP)).addMBB(TBB);
+    ++Count;
+    break;
+  default: {
+    unsigned Opc = GetCondBranchFromCond(CC);
+    BuildMI(&MBB, get(Opc)).addMBB(TBB);
+    ++Count;
+  }
+  }
+  if (FBB) {
+    // Two-way Conditional branch. Insert the second branch.
+    BuildMI(&MBB, get(X86::JMP)).addMBB(FBB);
+    ++Count;
+  }
+  return Count;
 }
 
 bool X86InstrInfo::copyRegToReg(MachineBasicBlock &MBB,
@@ -2372,6 +2405,8 @@ bool X86InstrInfo::
 ReverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const {
   assert(Cond.size() == 1 && "Invalid X86 branch condition!");
   X86::CondCode CC = static_cast<X86::CondCode>(Cond[0].getImm());
+  if (CC == X86::COND_NE_OR_P || CC == X86::COND_NP_OR_E)
+    return true;
   Cond[0].setImm(GetOppositeBranchCondition(CC));
   return false;
 }
diff --git a/lib/Target/X86/X86InstrInfo.h b/lib/Target/X86/X86InstrInfo.h
index 0a0de5e..17be894 100644
--- a/lib/Target/X86/X86InstrInfo.h
+++ b/lib/Target/X86/X86InstrInfo.h
@@ -44,6 +44,15 @@ namespace X86 {
     COND_O  = 13,
     COND_P  = 14,
     COND_S  = 15,
+
+    // Artificial condition codes. These are used by AnalyzeBranch
+    // to indicate a block terminated with two conditional branches to
+    // the same location. This occurs in code using FCMP_OEQ or FCMP_UNE,
+    // which can't be represented on x86 with a single condition. These
+    // are never used in MachineInstrs.
+    COND_NE_OR_P,
+    COND_NP_OR_E,
+
     COND_INVALID
   };