[VPlan] Simplify logical OR operations within the VPlan.

[paulwalker-arm]

Summary

When LoopVectorize if-converts loops it creates instructions that
were no present within the original IR. These instructions make
the VPlan look more costly that it actually is and typically makes
it hard to reason about accurate use counts for blend operations.

This patch add a cut down version of PatternMatch that can operate
on VPInstructions and use this interface to allow VPInstruction
simplification. Specifically, it is used to simplify VPlan IR
related to predicate mask construction.

[paulwalker-arm]

I need to tighten up some of the matching and write tests but I'm pushing this out now to gauge opinion.

The core problem I'm trying to solve is to reduce the places where LoopVectorize makes poor decisions based on the IR that only exists at the point of vectorisation (i.e. not present within the scalar loop or perhaps just substantially different). One such example is D157412 that builds on top of this patch.

My position is that whilst the result of vectorisation can be cleaned up by later passes, there are instances like D157412 where the data has already been striped of knowledge required for optimal IR. There's also a matter of having a more accurate cost model whereby having a more optimal VPlan allows the vectoriser to make better cost based decisions.

I created VPlanPatternMatch.h because I honestly fine VPlan awkward to work with and figured hiding the awkwardness behind a PatternMatch like interface leads to more readable code.

[fhahn]

Providing a PatternMatch implementation for VPlan recipes would be great, thanks for sharing the patch! In terms of where to apply the simplification, I think it would be a beneficial to have a separate simplification transform to handle this and other cases, e.g. see D159200, D159202

llvm/lib/Transforms/Vectorize/VPlanPatternMatch.h

84

This probably should also match VPWidenRecipe & VPReplicateRecipe with Select/And/Or and VPWidenSelectRecipe.

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

 /// It provides an instruction-level API for generating VPInstructions while
 /// abstracting away the Recipe manipulation details.
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
 #define LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
 
 #include "VPlan.h"
+#include "VPlanPatternMatch.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/Support/InstructionCost.h"
 
 namespace llvm {
 
+using namespace PatternMatch;
+
 class LoopInfo;
 class LoopVectorizationLegality;
 class LoopVectorizationCostModel;
 class PredicatedScalarEvolution;
 class LoopVectorizeHints;
 class OptimizationRemarkEmitter;
 class TargetTransformInfo;
 class TargetLibraryInfo;
public:
 
   VPValue *createAnd(VPValue *LHS, VPValue *RHS, DebugLoc DL,
                      const Twine &Name = "") {
     return createInstruction(Instruction::BinaryOps::And, {LHS, RHS}, DL, Name);
   }
 
   VPValue *createOr(VPValue *LHS, VPValue *RHS, DebugLoc DL,
                     const Twine &Name = "") {
+    if (VPValue *V = simplifyOr(LHS, RHS))
+      return V;
+
     return createInstruction(Instruction::BinaryOps::Or, {LHS, RHS}, DL, Name);
   }
 
   VPValue *createSelect(VPValue *Cond, VPValue *TrueVal, VPValue *FalseVal,
                         DebugLoc DL, const Twine &Name = "") {
     return createNaryOp(Instruction::Select, {Cond, TrueVal, FalseVal}, DL,
                         Name);
   }
 
   //===--------------------------------------------------------------------===//
+  // VPInstruction simplifiers.
+  //===--------------------------------------------------------------------===//
+
+  VPValue *simplifyOr(VPValue *LHS, VPValue *RHS) const {
+    VPValue *A, *B;
+
+    // (A && B) || (A && !B) ==> A
+    if (match(LHS, vp_LogicalAnd(vp_Value(A), vp_Value(B))) &&
+        match(RHS, vp_c_LogicalAnd(vp_Specific(A), vp_Not(vp_Specific(B)))))
+      return A;
+
+    return nullptr;
+  }
+
+  //===--------------------------------------------------------------------===//
   // RAII helpers.
   //===--------------------------------------------------------------------===//
 
   /// RAII object that stores the current insertion point and restores it when
   /// the object is destroyed.
   class InsertPointGuard {
     VPBuilder &Builder;
     VPBasicBlock *Block;

llvm/lib/Transforms/Vectorize/VPlanPatternMatch.h

+//===- VPlanPatternMatch.h - Match on the LLVM VPlan IR -------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides a simple and efficient mechanism for performing general
+// tree-based pattern matches on the LLVM VPlan IR. It is heavily modelled on
+// PatternMatch.h
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_PATTERN_MATH_H
+#define LLVM_TRANSFORMS_VECTORIZE_VPLAN_PATTERN_MATH_H
+
+#include "VPlan.h"
+#include "llvm/IR/PatternMatch.h"
+
+namespace llvm {
+namespace PatternMatch {
+
+inline bind_ty<VPValue> vp_Value(VPValue *&V) { return V; }
+
+/// Match a specified Value*.
+struct vp_specificval_ty {
+  const VPValue *Val;
+
+  vp_specificval_ty(const VPValue *V) : Val(V) {}
+
+  template <typename ITy> bool match(ITy *V) { return V == Val; }
+};
+
+/// Match if we have a specific specified value.
+inline vp_specificval_ty vp_Specific(const VPValue *V) { return V; };
+
+struct vp_is_zero {
+  template <typename ITy> bool match(ITy *V) {
+    if (const Value *UV = V->getUnderlyingValue())
+      return isa<Constant>(UV) && cast<Constant>(UV)->isNullValue();
+
+    return false;
+  }
+};
+
+/// Match any null constant or a vector with all elements equal to 0.
+/// For vectors, this includes constants with undefined elements.
+inline vp_is_zero vp_Zero() { return vp_is_zero(); }
+
+template <typename LHS, unsigned Opcode> struct VPUnaryOp_match {
+  LHS L;
+
+  VPUnaryOp_match(const LHS &L) : L(L) {}
+
+  template <typename T> bool match(T *V) {
+    auto *I = dyn_cast<VPInstruction>(V);
+
+    if (!I || I->getOpcode() != Opcode)
+      return false;
+
+    return L.match(I->getOperand(0));
+  }
+};
+
+template <typename LHS>
+inline VPUnaryOp_match<LHS, VPInstruction::Not> vp_Not(const LHS &L) {
+  return VPUnaryOp_match<LHS, VPInstruction::Not>(L);
+}
+
+template <typename LHS, typename RHS, unsigned Opcode, bool Commutable = false>
+struct VPLogicalOp_match {
+  LHS L;
+  RHS R;
+
+  VPLogicalOp_match(const LHS &L, const RHS &R) : L(L), R(R) {}
+
+  template <typename T> bool match(T *V) {
+    auto *I = dyn_cast<VPInstruction>(V);
+
+    if (!I)
+      return false;
+
+    if (cast<VPInstruction>(V)->getOpcode() != Instruction::Select)
+      return false;
+
+    auto *Cond = cast<VPInstruction>(V)->getOperand(0);
+    auto *TVal = cast<VPInstruction>(V)->getOperand(1);
+    auto *FVal = cast<VPInstruction>(V)->getOperand(2);
+
+    // TODO: How best can we know the operation is on i1 types?
+
+    if (Opcode == Instruction::And)
+      if (vp_Zero().match(FVal))
+        return (L.match(Cond) && R.match(TVal)) ||
+               (Commutable && L.match(TVal) && R.match(Cond));
+
+    return false;
+  }
+};
+
+/// Matches L && R either in the form of L & R or L ? R : false.
+/// Note that the latter form is poison-blocking.
+template <typename LHS, typename RHS>
+inline VPLogicalOp_match<LHS, RHS, Instruction::And>
+vp_LogicalAnd(const LHS &L, const RHS &R) {
+  return VPLogicalOp_match<LHS, RHS, Instruction::And>(L, R);
+}
+
+/// Matches L && R where L and R are arbitrary values.
+inline auto vp_LogicalAnd() { return vp_LogicalAnd(m_Value(), m_Value()); }
+
+/// Matches L && R with LHS and RHS in either order.
+template <typename LHS, typename RHS>
+inline VPLogicalOp_match<LHS, RHS, Instruction::And, true>
+vp_c_LogicalAnd(const LHS &L, const RHS &R) {
+  return VPLogicalOp_match<LHS, RHS, Instruction::And, true>(L, R);
+}
+
+} // namespace PatternMatch
+} // namespace llvm
+
+#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_PATTERN_MATH_H