[InstCombine] add isCanonicalPredicate() helper function and use it; NFCI

[spatel]

Summary

There should be a slight efficiency improvement from handling icmp/fcmp with one matcher and reducing duplicated code.

The larger motivation is that there are questions about how predicate canonicalization is handled, and the refactoring should make it easier if we want to change any of that behavior.

I'll post those questions here for reference, but I expect we should answer these in follow-up patches and/or llvm-dev:

1. As noted in the code comment, we've chosen 3 of the 16 FCMP preds as not canonical. Why those 3? It goes back to rL32751 from what I can tell, but I'm not sure if there's a justification for that rule.
2. We currently do not canonicalize most select conditions. Should we use the same rule that applies to branches for selects?
3. We currently do canonicalize some FP select conditions, and those rules would conflict with the rule shown here. Should one or both be changed? Canonicalize to use ordered comparisons by swapping the select operands. e.g. // (X ugt Y) ? X : Y -> (X ole Y) ? Y : X

[davide]

lib/Transforms/InstCombine/InstCombineInternal.h

88–92

Given that was about 11 years ago, it's unlikely we're going to find out.
That said, I'm not sure this is relevant anymore so we might reconsider.

95–96

I think GCC might complain about this so you might consider adding an llvm_unreachable at the end of this.

[spatel]

lib/Transforms/InstCombine/InstCombineInternal.h

95–96

Do you know of a case where that happens? I couldn't find one:
https://godbolt.org/g/l0XnXd
...so I'd rather not ugly up the code for something if it doesn't really happen. We could 'default: break' and return true outside of the switch if you think that reads better.

[davide]

lib/Transforms/InstCombine/InstCombineInternal.h

95–96

I saw it emitting warning in similar cases, but not this one (just checked).
If neither compiler complains, I think you can leave as is (worst case we'll need to fix a builbot failure, not a big deal).

[craig.topper]

lib/Transforms/InstCombine/InstCombineInternal.h

95–96

I think gcc's complaint is normally when the switch covers all values of an enum and there is no default case.

From the coding standards:

"A knock-on effect of this stylistic requirement is that when building LLVM with GCC you may get warnings related to “control may reach end of non-void function” if you return from each case of a covered switch-over-enum because GCC assumes that the enum expression may take any representable value, not just those of individual enumerators. To suppress this warning, use llvm_unreachable after the switch."

[spatel]

Patch updated:
Although this patch is NFCI, we had exactly zero tests for the FCMP transforms, and the ICMP transforms were not tested completely. Given the lumpy handling of the predicates, I think it's best to check all of them to make sure we're doing exactly what we think we're doing.

I checked that there is no difference for the tests before/after this code change, but I can check in the tests first if that would be preferred.

[davide]

In D33247#756647, @spatel wrote:

Patch updated:
Although this patch is NFCI, we had exactly zero tests for the FCMP transforms, and the ICMP transforms were not tested completely. Given the lumpy handling of the predicates, I think it's best to check all of them to make sure we're doing exactly what we think we're doing.

I checked that there is no difference for the tests before/after this code change, but I can check in the tests first if that would be preferred.

I think adding these tests is a good thing. I don't think it's worth checking in them separately.
I guess this is fine, but please wait for either Eli or David to give another look.

[efriedma]

Cleanup looks fine.

lib/Transforms/InstCombine/InstCombineInternal.h

91

Not sure why these three are special either... from a brief look at the commit, I would guess it was done to mirror the integer transforms, without any real consideration for what should be canonical.

If I were doing it from scratch, I might say we should consider ordered predicates canonical, since they're the ones people are used to working with.

lib/Transforms/InstCombine/InstCombineInternal.h

if (isa<CastInst>(V) || BinaryOperator::isNeg(V) ||
       return 4;
     return 5;
   }
   if (isa<Argument>(V))
     return 3;
   return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
 }
 
+/// Predicate canonicalization attempts to reduce the number of patterns that
+/// need to be matched by other transforms. For example, we may swap the
+/// operands of a conditional branch or select to create a compare with a
+/// canonical (inverted) predicate which can then be matched with other values.
+static inline bool isCanonicalPredicate(CmpInst::Predicate Pred) {
+  switch (Pred) {
+  case CmpInst::ICMP_NE:
+  case CmpInst::ICMP_ULE:
+  case CmpInst::ICMP_SLE:
+  case CmpInst::ICMP_UGE:
+  case CmpInst::ICMP_SGE:
+  // TODO: There are 16 FCMP predicates. Should others be (not) canonical?
+  case CmpInst::FCMP_ONE:
+  case CmpInst::FCMP_OLE:
+  case CmpInst::FCMP_OGE:
+    return false;
+  default:
+    return true;
+  }
+}
+
 /// \brief Add one to a Constant
 static inline Constant *AddOne(Constant *C) {
   return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
 }
 /// \brief Subtract one from a Constant
 static inline Constant *SubOne(Constant *C) {
   return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
 }

lib/Transforms/InstCombine/InstructionCombining.cpp

Instruction *InstCombiner::visitBranchInst(BranchInst &BI) {
   // transforms on the condition become more effective.
   if (BI.isConditional() &&
       BI.getSuccessor(0) == BI.getSuccessor(1) &&
       !isa<UndefValue>(BI.getCondition())) {
     BI.setCondition(UndefValue::get(BI.getCondition()->getType()));
     return &BI;
   }
 
-  // Canonicalize fcmp_one -> fcmp_oeq
-  FCmpInst::Predicate FPred; Value *Y;
-  if (match(&BI, m_Br(m_OneUse(m_FCmp(FPred, m_Value(X), m_Value(Y))),
-                      TrueDest, FalseDest))) {
-    // TODO: Why are we only transforming these 3 predicates?
-    if (FPred == FCmpInst::FCMP_ONE || FPred == FCmpInst::FCMP_OLE ||
-        FPred == FCmpInst::FCMP_OGE) {
-      FCmpInst *Cond = cast<FCmpInst>(BI.getCondition());
-      Cond->setPredicate(FCmpInst::getInversePredicate(FPred));
-
-      // Swap Destinations and condition.
-      BI.swapSuccessors();
-      Worklist.Add(Cond);
-      return &BI;
-    }
-  }
-
-  // Canonicalize icmp_ne -> icmp_eq
-  ICmpInst::Predicate IPred;
-  if (match(&BI, m_Br(m_OneUse(m_ICmp(IPred, m_Value(X), m_Value(Y))),
-                      TrueDest, FalseDest))) {
-    if (IPred == ICmpInst::ICMP_NE  || IPred == ICmpInst::ICMP_ULE ||
-        IPred == ICmpInst::ICMP_SLE || IPred == ICmpInst::ICMP_UGE ||
-        IPred == ICmpInst::ICMP_SGE) {
-      ICmpInst *Cond = cast<ICmpInst>(BI.getCondition());
-      Cond->setPredicate(ICmpInst::getInversePredicate(IPred));
-      // Swap Destinations and condition.
-      BI.swapSuccessors();
-      Worklist.Add(Cond);
-      return &BI;
-    }
-  }
+  // Canonicalize, for example, icmp_ne -> icmp_eq or fcmp_one -> fcmp_oeq.
+  CmpInst::Predicate Pred;
+  if (match(&BI, m_Br(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), TrueDest,
+                      FalseDest)) &&
+      !isCanonicalPredicate(Pred)) {
+    // Swap destinations and condition.
+    CmpInst *Cond = cast<CmpInst>(BI.getCondition());
+    Cond->setPredicate(CmpInst::getInversePredicate(Pred));
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) {
   Value *Cond = SI.getCondition();
   Value *Op0;
   ConstantInt *AddRHS;