[PatternMatch] Create match method to track uses complexity

[rampitec]

Summary

This patch introduces new match function which can return
a number of matched operations with multiple uses. It also
can take an argument with a limit of such operands number
for match to succeed.

The function is needed if we want to limit a total number
of multiply used operands but do not necessarily care which.

[lebedev.ri]

I'm somewhat unconvinced that we can solve this problem at the match stage.
Consider

v0 = a + c
v1 = v0 + c
v2 = v1 + c
r = v2 + c

if you do match(m_Add(m_Add(m_Add(m_Add(m_Value(A), m_Value(C)), m_Specific(C)), m_Specific(C)), m_Specific(C))),
i think UseComplexity will be 4(?), but that doesn't mean that you can create 4 instructions,
in reality it depends on the pattern you will produce. If you want to produce a + 4*c, sure, you can do that,
because none of the instructions you matched are used in the pattern. But if you want to produce
v2 + 1*c, you can not, because that would increase instruction count...

[rampitec]

In D114126#3139528, @lebedev.ri wrote:

I'm somewhat unconvinced that we can solve this problem at the match stage.
Consider

v0 = a + c
v1 = v0 + c
v2 = v1 + c
r = v2 + c

if you do match(m_Add(m_Add(m_Add(m_Add(m_Value(A), m_Value(C)), m_Specific(C)), m_Specific(C)), m_Specific(C))),
i think UseComplexity will be 4(?), but that doesn't mean that you can create 4 instructions,
in reality it depends on the pattern you will produce. If you want to produce a + 4*c, sure, you can do that,
because none of the instructions you matched are used in the pattern. But if you want to produce
v2 + 1*c, you can not, because that would increase instruction count...

In that match complexity will be zero because none of the values have more than one use. Than you can rule what is your complexity to use as a limit based on your target transform, just like I did in the example transform with 4 instructions being a threshold just on the grounds of comparing source and target code.

The assumption is that all that instructions go away after transform except those which have uses outside of the source pattern. And then even if not you can adjust the limit. I guess I will have to do it where I am reusing a subexpression, because a reused value shall not count, it just stays, but that needs a proper handling of m_CombineAnd as a max of complexity of its operands, which I have not done yet. Then speaking of that m_CombineOr shall use a complexity of a selected leg.

[rampitec]

A side note: I have initially tried to modify match() methods to accept and calculate complexity arguments and being stateless, just return them. I have then realized that turns into nightmare because a match can restart and retry, and that is nearly impossible to track statelessly. The benefit was obvious: an early termination of a match, but the accounting cost quickly became too high and not stateless anyway. That said I believe only a BinOp and UnOp will have to keep state. Well, combine and/or too likely. The leaf matches like m_Value or constants do not count and have complexity zero anyway. So the new match interface will have to sum final complexity after the whole match has succeeded and states recorded.

[rampitec]

Use SFINAE to only add getUseComplexity() method to matchers which really need it. This will be much less code than previously anticipated.

[nikic]

Taking a step back here, I want to ask: Is this solving some kind of real problem? I get the impression that use counting in InstCombine has moved beyond a practical consideration into the realm of religious dogma. I don't think there is much value in always making exotic, complex folds maximally applicable in multi-use scenarios, if doing so does not happen to be straightforward.

[rampitec]

In D114126#3140943, @nikic wrote:

Taking a step back here, I want to ask: Is this solving some kind of real problem? I get the impression that use counting in InstCombine has moved beyond a practical consideration into the realm of religious dogma. I don't think there is much value in always making exotic, complex folds maximally applicable in multi-use scenarios, if doing so does not happen to be straightforward.

The example use is one application, the rest of the cases in the same function too. In fact in a later experiments I came across a situation when we do not perform reassociation in the demorganing bacause of the multi use issue and I have a hard time solving it without such accounting.

The other practical improvement is that it shall just simplify the accounting. It is easier to write something like 4 - UseComplexity and omit all m_OneUse than counting unwrapped patterns.

[rampitec]

The patch is ready now.

[rampitec]

This is actually a bad idea at least as is. A use of an subexpression will preserve the whole subexpression which needs to be accounted in the complexity.

[rampitec]

• Fixed subexpression cost handling, any use at root now marks each value in subexpression used.
• Changed all patterns foldComplexAndOrPatterns.
• Added tests.

[rampitec]

Rebased.
Added handling of newly added case (~A & B & C) | ~(A | B) --> (C | ~B) & ~A.

[rampitec]

ping

[rampitec]

Rebased.

[spatel]

I'm not opposed to the direction, but I don't have enough C++ knowledge to review the implementation.

@nikic commented on the exactness of use counting that we've created and wondered if we need to try so hard. I sympathize/agree with that view.
But I've actually hoped that we could loosen the constraints on some patterns - that is, allow the creation of more instructions because the transform is still beneficial from an overall use count.
Take for example one of the motivating Demorgan patterns for this patch:
https://alive2.llvm.org/ce/z/4XGCm3
The 'not' ops have extra uses, so we don't do: (~A & ~B) --> ~(A | B) even though that would get the final result in 2 ops instead of 3. But we don't do the inverse transform either (it requires more than simple pattern-matching).
If we removed some strictness about uses, we probably wouldn't require this patch or the follow-ons for complicated bitwise logic optimizations. Those are only needed because we miss the simpler, intermediate folds in complex expressions with extra uses. I suppose we'd be more at risk for infinite combine loops if we allowed creating extra instructions, but it might be worth experimenting with removing some use checks on bitwise logic folds to see how that plays out.

[rampitec]

In D114126#3227404, @spatel wrote:

If we removed some strictness about uses, we probably wouldn't require this patch or the follow-ons for complicated bitwise logic optimizations. Those are only needed because we miss the simpler, intermediate folds in complex expressions with extra uses. I suppose we'd be more at risk for infinite combine loops if we allowed creating extra instructions, but it might be worth experimenting with removing some use checks on bitwise logic folds to see how that plays out.

More than infinite loops (which is also possible) I am worried we may in fact make code worse without taking into account a wider pattern.
Anyhow, we used to discuss this approach in the very beginning of the ternary changes stack, so I thought to give it a try. It turns out to be more complicated change than I was initially anticipated unfortunately. I am not pushing this in any way.

[rampitec]

I am going to abandon this and all other instcombine changes due to the lack of interest.

llvm/include/llvm/IR/PatternMatch.h

 
 namespace llvm {
 namespace PatternMatch {
 
 template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) {
   return const_cast<Pattern &>(P).match(V);
 }
 
+/// Match Value \p V against Pattern \P. Store a number of matched operations
+/// with multiple uses into \p UseComplexity if provided. Match fails if the
+/// complexity is higher than MaxComplexity.
+template <typename Val, typename Pattern>
+bool match(Val *V, const Pattern &P, int *UseComplexity,
+           int MaxComplexity = INT_MAX) {
+  if (MaxComplexity < 0 || !const_cast<Pattern &>(P).match(V))
+    return false;
+  int Complexity = (int)P.getUseComplexity();
+  if (UseComplexity)
+    *UseComplexity = Complexity;
+  return Complexity <= MaxComplexity;
+}
+
 template <typename Pattern> bool match(ArrayRef<int> Mask, const Pattern &P) {
   return const_cast<Pattern &>(P).match(Mask);
 }
 
+struct UseComplexity {
+  unsigned getUseComplexity() const { return 0; };
+};
+
 template <typename SubPattern_t> struct OneUse_match {
   SubPattern_t SubPattern;
 
   OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     return V->hasOneUse() && SubPattern.match(V);
   }
 };
 
 template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) {
   return SubPattern;
 }
 
-template <typename Class> struct class_match {
+template <typename Class> struct class_match : public UseComplexity {
   template <typename ITy> bool match(ITy *V) { return isa<Class>(V); }
 };
 
 /// Match an arbitrary value and ignore it.
 inline class_match<Value> m_Value() { return class_match<Value>(); }
 
 /// Match an arbitrary unary operation and ignore it.
 inline class_match<UnaryOperator> m_UnOp() {

 template <int64_t Val> inline constantint_match<Val> m_ConstantInt() {
   return constantint_match<Val>();
 }
 
 /// This helper class is used to match constant scalars, vector splats,
 /// and fixed width vectors that satisfy a specified predicate.
 /// For fixed width vector constants, undefined elements are ignored.
 template <typename Predicate, typename ConstantVal>
-struct cstval_pred_ty : public Predicate {
+struct cstval_pred_ty : public Predicate, UseComplexity {
   template <typename ITy> bool match(ITy *V) {
     if (const auto *CV = dyn_cast<ConstantVal>(V))
       return this->isValue(CV->getValue());
     if (const auto *VTy = dyn_cast<VectorType>(V->getType())) {
       if (const auto *C = dyn_cast<Constant>(V)) {
         if (const auto *CV = dyn_cast_or_null<ConstantVal>(C->getSplatValue()))
           return this->isValue(CV->getValue());
 

 /// Match a floating-point non-zero.
 /// For vectors, this includes constants with undefined elements.
 inline cstfp_pred_ty<is_non_zero_fp> m_NonZeroFP() {
   return cstfp_pred_ty<is_non_zero_fp>();
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 
-template <typename Class> struct bind_ty {
+template <typename Class> struct bind_ty : public UseComplexity {
   Class *&VR;
 
   bind_ty(Class *&V) : VR(V) {}
 
   template <typename ITy> bool match(ITy *V) {
     if (auto *CV = dyn_cast<Class>(V)) {
       VR = CV;
       return true;

 /// Match an immediate Constant, capturing the value if we match.
 inline match_combine_and<bind_ty<Constant>,
                          match_unless<class_match<ConstantExpr>>>
 m_ImmConstant(Constant *&C) {
   return m_CombineAnd(m_Constant(C), m_Unless(m_ConstantExpr()));
 }
 
 /// Match a specified Value*.
-struct specificval_ty {
+struct specificval_ty : public UseComplexity {
   const Value *Val;
 
   specificval_ty(const Value *V) : Val(V) {}
 
   template <typename ITy> bool match(ITy *V) { return V == Val; }
 };
 
 /// Match if we have a specific specified value.

 // Matchers for specific binary operators.
 //
 
 template <typename LHS_t, typename RHS_t, unsigned Opcode,
           bool Commutable = false>
 struct BinaryOp_match {
   LHS_t L;
   RHS_t R;
+  bool IsOneUse = false;
 
   // The evaluation order is always stable, regardless of Commutability.
   // The LHS is always matched first.
   BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 
   template <typename OpTy> inline bool match(unsigned Opc, OpTy *V) {
     if (V->getValueID() == Value::InstructionVal + Opc) {
       auto *I = cast<BinaryOperator>(V);
       return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
              (Commutable && L.match(I->getOperand(1)) &&
               R.match(I->getOperand(0)));
     }
     if (auto *CE = dyn_cast<ConstantExpr>(V))
       return CE->getOpcode() == Opc &&
              ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) ||
               (Commutable && L.match(CE->getOperand(1)) &&
                R.match(CE->getOperand(0))));
     return false;
   }
 
-  template <typename OpTy> bool match(OpTy *V) { return match(Opcode, V); }
+  template <typename OpTy> bool match(OpTy *V) {
+    if (match(Opcode, V)) {
+      IsOneUse = V->hasOneUse();
+      return true;
+    }
+    return false;
+  }
+
+  unsigned getUseComplexity() const {
+    return (IsOneUse ? 0 : 1) + L.getUseComplexity() + R.getUseComplexity();
+  }
 };
 
 template <typename LHS, typename RHS>
 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
                                                         const RHS &R) {
   return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
 }
 

 struct SpecificBinaryOp_match
     : public BinaryOp_match<LHS_t, RHS_t, 0, Commutable> {
   unsigned Opcode;
 
   SpecificBinaryOp_match(unsigned Opcode, const LHS_t &LHS, const RHS_t &RHS)
       : BinaryOp_match<LHS_t, RHS_t, 0, Commutable>(LHS, RHS), Opcode(Opcode) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    return BinaryOp_match<LHS_t, RHS_t, 0, Commutable>::match(Opcode, V);
+    if (BinaryOp_match<LHS_t, RHS_t, 0, Commutable>::match(Opcode, V)) {
+      BinaryOp_match<LHS_t, RHS_t, 0, Commutable>::IsOneUse = V->hasOneUse();
+      return true;
+    }
+    return false;
   }
 };
 
 /// Matches a specific opcode.
 template <typename LHS, typename RHS>
 inline SpecificBinaryOp_match<LHS, RHS> m_BinOp(unsigned Opcode, const LHS &L,
                                                 const RHS &R) {
   return SpecificBinaryOp_match<LHS, RHS>(Opcode, L, R);

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

static Instruction *foldComplexAndOrPatterns(BinaryOperator &I,
   assert(Opcode == Instruction::And || Opcode == Instruction::Or);
 
   // Flip the logic operation.
   const Instruction::BinaryOps FlippedOpcode =
       (Opcode == Instruction::And) ? Instruction::Or : Instruction::And;
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   Value *A, *B, *C;
+  int UseComplexity;
 
   // (~(A | B) & C) | ... --> ...
   // (~(A & B) | C) & ... --> ...
   // TODO: One use checks are conservative. We just need to check that a total
   //       number of multiple used values does not exceed reduction
   //       in operations.
-  if (match(Op0, m_c_BinOp(FlippedOpcode,
-                           m_Not(m_BinOp(Opcode, m_Value(A), m_Value(B))),
-                           m_Value(C)))) {
+  if (match(Op0,
+            m_c_BinOp(FlippedOpcode,
+                      m_Value(C)),
+            &UseComplexity)) {
     // (~(A | B) & C) | (~(A | C) & B) --> (B ^ C) & ~A
     // (~(A & B) | C) & (~(A & C) | B) --> ~((B ^ C) & A)
     if (match(Op1,
-              m_OneUse(m_c_BinOp(FlippedOpcode,
-                                 m_OneUse(m_Not(m_c_BinOp(Opcode, m_Specific(A),
-                                                          m_Specific(C)))),
-                                 m_Specific(B))))) {
+              m_c_BinOp(FlippedOpcode,
+                        m_Not(m_c_BinOp(Opcode, m_Specific(A), m_Specific(C))),
+                        m_Specific(B)),
+              nullptr, 4 - UseComplexity)) {
       Value *Xor = Builder.CreateXor(B, C);
       return (Opcode == Instruction::Or)
                  ? BinaryOperator::CreateAnd(Xor, Builder.CreateNot(A))
                  : BinaryOperator::CreateNot(Builder.CreateAnd(Xor, A));
     }
 
     // (~(A | B) & C) | (~(B | C) & A) --> (A ^ C) & ~B
     // (~(A & B) | C) & (~(B & C) | A) --> ~((A ^ C) & B)