Generalized PatternMatch & InstSimplify

[simoll]

Summary

Summary

How can we make InstSimplify work with intrinsics?

The idea here is to pretend that the intrinsics were the actual instruction (eg an fadd) and run the existing InstSimplify code. We stop InstSimplify before it breaks code as soon as we are not sure anymore that the rewrite is compatible with the semantics of the intrinsics.

The tests in this patch show this for contrained fp and vp intrinsics.

This is a work-in-progress re-implementation of the generalized pattern match mechanism of D57504 . That patch also implements InstCombine (and not just simplify).

Background

InstSimplify only works for regular LLVM instructions. Yet, there are more and more intrinsics that mimic regular instructions with a twist.
For example:

• @llvm.experimental.constrained.fadd allows custom rounding and fp exceptions - however, for default fp settings, it is just an fadd.

• @llvm.vp.add is a vector-add with a mask and explicit vector length - however, the operation applied to each active lane is just an add.

InstSimplify and InstCombine specify a ton of peephole rewrites to optimize patterns with regular IR instructions.
We'd like to make those pattern-based rewrites work on intrinsics as well.

How?

InstSimplify always works the same: if a pattern matches, it replaces the match root with a pattern leaf (or a constant).
We do two things to make this work:
1.) We add layer of helper classes that let intrinsics pretend to be instructions.
2.) We add a MatcherContext that verifies that a specific pattern match is legal with intrinsics.

However, we want this not just for one kind of intrinsic but different classes (as shown above). To do that, we introduce the notion of a Trait - a Trait is a representation of that extra-property that makes the difference between an instruction and an intrinsic that just pretends to be one.

We define three different traits in this patch:

• The CFPTrait works on constrained fp intrinsics. The MatcherContext<CFPTrait> verifies all pattern matches that use constrained fp intrinsics with default fp semantics (tonearest, no exceptions).
• The VPTrait works on VP intrinsics and regular instructions. Eg, a first-class %x = add <8 x i32> %y, %z passes as an add as well as a llvm.vp.add.v8i32(%x, %y, %mask, %evl). Since the masked-out lanes in VP intrinsics deliver an undefined results all matching patterns are automatically legal.
• The EmptyTrait does not pretend anything. Only first-class FAdd is a FAdd. There are no helper classes but an Instruction is really just an Instruction.

Remarks

• We get constant-folding for VP intrinsics for free.
• The constrained fp trait could be extended to non-strict fp exceptions (simplify only).
• We will build on this framework also for InstCombine - this was also implemented in D57504 .
• I am not a floating-point expert - i'd be thrilled to learn under which circumstances pattern rewrites that assume default fp semantics apply to other rounding modes.

Implementation Details

The MatcherContext<Trait> starts in an uninitialized state. When a PatternMatch.h pattern is in the process of being matched against a specific instruction, it calls the check(V)/accept(V) methods of the context on all operators in the pattern. As soon as the context returns false, the entire match fails.

The ExtInstruction<Trait>, ExtBinaryOperator<Trait> classes make up the intermediate layer of pretend-classes. The default implementation of those classes assumes that there is an underlying intrinsic class (Trait::Intrinsic).

[simoll]

NFC. Fixed formatting, tidiness.

[nhaehnle]

llvm/include/llvm/IR/Traits/Traits.h

183

I'm confused: How does this work? Shouldn't there be an isa<typename Trait::Intrinsic>(V) check? Actually, how does this even compile? It seems like a (V) is missing on the cast.

244

Which ones do you have in mind?

[simoll]

llvm/include/llvm/IR/Traits/Traits.h

183

Evidently this code is never instantiated or it would not compile.. i'll fix this.

244

I have no specific ext type in mind here. Generally speaking, it depends on the traits and the types they need to override. At the moment, we only define the Ext types required by the CFP and VP traits (and a few more that aren't instantiated..).
In a complete implementation for all foreseeable overrides, you'd need an "Ext" type for all types that are used in "PatternMatch.h". Eg, ExtPossiblyExactOperator,ExtOverflowingBinaryOperator, etc.

[rengolin]

First, I think this is a good idea and can eventually mitigate the general problem of intrinsics vs. instructions in other LLVM passes.

But I worry we'll end up with too many traits to emulate actual instructions' semantics and we'll go back to the discussions of how much an intrinsic is like an instruction.

As an example, for one type of transformation (say constant folding) an intrinsic-add "acts like an add" (precision), but another transformation (ex loop induction) it doesn't (wrapping semantics).

So, while we can come up with a list of traits that make this one particular match work, we may be faced with a combinatorial number of traits to generalise it to other transformations.

I don't have any particular case in mind, just the general feeling that we'll get stuck half-way through and have to keep a set of traits that can't be easily used by other passes.

But this is not a negative view, just perhaps a request for clarification: how much else did you look at to make sure this can extend to more intrinsics and passes?

Second, there are a lot of clang-format changes on unrelated code lines and it makes it hard to see what's just reformatted and what's really changed.

[simoll]

In D92086#3536474, @rengolin wrote:

First, I think this is a good idea and can eventually mitigate the general problem of intrinsics vs. instructions in other LLVM passes.

Thanks for chiming in!

But I worry we'll end up with too many traits to emulate actual instructions' semantics and we'll go back to the discussions of how much an intrinsic is like an instruction.

As an example, for one type of transformation (say constant folding) an intrinsic-add "acts like an add" (precision), but another transformation (ex loop induction) it doesn't (wrapping semantics).

So, while we can come up with a list of traits that make this one particular match work, we may be faced with a combinatorial number of traits to generalise it to other transformations.

I don't have any particular case in mind, just the general feeling that we'll get stuck half-way through and have to keep a set of traits that can't be easily used by other passes.

But this is not a negative view, just perhaps a request for clarification: how much else did you look at to make sure this can extend to more intrinsics and passes?

I did not look into the generality of the approach beyond InstSimplify/Combine. The traits, as defined right now, are really specific to that use case. InstSimplify/Combine is really where the demand is for the intrinsics as far as i am aware.

Other intrinsic types for InstCombine could be saturating int arithmetic, complex arithmetic and, maybe, matrix intrinsics.

You could try to generalize the trait approach for all kinds of analyses and transformations. I am not sure it's worthwhile though.
If you did, what could happen in the worst case, if specific traits are not general enough and we insisted on generalizing the approach to all passes? If you wrote one trait per set of intrinsics and pass that would get you somewhere in O(#passes x #intrinsic_types) in terms of number of trait classes - that's not really a combinatorial explosion. Even in this scenario, which we would not blindly walk in to, you are getting something in return: those passes start working on the intrinsics.

Second, there are a lot of clang-format changes on unrelated code lines and it makes it hard to see what's just reformatted and what's really changed.

D126783 should help with that.

[simoll]

Btw, no matter where you stand on D126889 - the patch lower-cases all InstructionSimplify function names - the diff shows just how many different passes actually rely on instruction simplification. Those passes could potentially benefit from generalized pattern matching (even if its limited to instsimplify/combine).

[fhahn]

It looks like unfortunately the patch doesn't apply on current main. Does it have any dependencies or does it just need a rebase?

[simoll]

In D92086#3563092, @fhahn wrote:

It looks like unfortunately the patch doesn't apply on current main. Does it have any dependencies or does it just need a rebase?

It needs a rebase. Currently doing that.

[simoll]

Here is the rebased patch for now. Currently two failing tests. This could be instsimplify opportunities enabled by this patch on constrained fp (have to look into it more).

Failed Tests (2):
  LLVM :: Transforms/InstSimplify/constfold-constrained.ll
  LLVM :: Transforms/InstSimplify/floating-point-arithmetic-strictfp.ll

[simoll]

Some comments/thoughts inline.
In the meantime, upstream got new fp patterns that consider the fp environment. This should work just fine with this approach (see my comment on the consider function - we may even DCE fp-environment-aware-patterns for Traits that support fp but do not care about the fp env).

llvm/include/llvm/IR/Traits/Traits.h

268

Note that we can DCE pattern-match paths in the trait-instantiated pattern rewrites, if we make this function more transparent to the compiler.

Not all pattern rewrites make sense for all traits. Eg, the Constrained FP trait does not care about anything but fp arithmetic. If we turn consider into a switch over opcodes right in this header file, say, the compiler may have a chance to detect dead pattern matching paths in the code. The result would be that when eg simplifyAddInst is instantiated for the CFPTrait, the function would be almost empty (since all non-fp opcodes are rejected - and the compiler can (hopefully) discard the int arithmetic patterns for the CFPTrait).

llvm/lib/Analysis/InstructionSimplify.cpp

3694

Ignore. Stale code kept during rebase.

4259

Ignore. Stale code kept during rebase.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

2253

I am not happy about this change. The PatternMatch abstractions should be entirely transparent to external code. External code would be code outside of PatternMatch or InstSimplify/Combine.

One way to get rid of this change in external code, is to understand that the issue only arises when "our" code calls into "external" code expecting there to be a match function with trait parameter - but never when "external" patterns call into "our" patterns because then everything will default to calling match functions without trait parameter.

llvm/test/Transforms/InstSimplify/fast-math-strictfp.ll

96

This test is actually illformed, according to the LangRef:

"If any FP operation in a function is constrained then they all must be constrained. This is required for correct LLVM IR. "

[simoll]

llvm/test/Transforms/InstSimplify/fpadd_constrained.ll

57

This test is then illformed, too ;-)

[nikic]

This fails to build with:

lib/libLLVMInstCombine.a(InstructionCombining.cpp.o):InstructionCombining.cpp:function llvm::InstCombinerImpl::visitGEPOfGEP(llvm::GetElementPtrInst&, llvm::GEPOperator*): error: undefined reference to 'llvm::Value* llvm::simplifyAddInst(llvm::Value*, llvm::Value*, bool, bool, llvm::SimplifyQuery const&, llvm::MatcherContext&)'

Probably due to illegal use of inline. You need to use static inline if you don't add extern inline definitions. (Or possibly a missing explicit template instantiation, but I think that wouldn't be used by InstCombine with this patch.)

I'm generally very skeptical about this proposal. This adds a lot of additional complexity to the area of LLVM that likely already has the highest ratio between lines of code changed and review time / amount of tests. After adding tests for baseline behavior, 16 commuted variants, nowrap/FMF variations, vector splat, undef-splat and non-splat variations, and negative tests for all used conditions (including all pattern match conditions), I definitely would rather not add variation tests for VP and constrained FP intrinsics (with which I am not familiar) as well.

I guess one could make an argument that if one uses the generalized matchers, there is nothing that could possibly go wrong, and there is no need to actually test these pattern or understand their correctness. I'm doubtful that this is actually true though. It's almost certainly not true for InstCombine, but even in InstSimplify I expect that there would be some dangerous interaction with predicated div/rem opcodes. Presumably, a zero value in a masked out lane does not render the program undefined, and as such an InstSimplify fold to a poison value would be incorrect.

Another concern here is compile-time, but I won't be able to test that until there is an actually buildable patch.

A possibly stupid question from someone who has not followed the VP design: Why does the predication need to happen on every single instruction? Naively, I'd assume that predication is only important for instructions that have trapping behavior, which is basically just load/store and div/rem class intrinsics. For everything else, it should be fine to represent this as a normal vector add, and then a single masking operation at the end. One could then propagate that masking backwards in the backend. That should ensure that normal instructions optimize fine, while instructions where the masking is semantically relevant (like div/rem) do not blindly participate in optimizations.

So basically, vp.add(X, Y, M) can be decomposed into vp.mask(add(X, Y), M), where the vp.mask intrinsic can be pushed down and combined with other mask intrinsics. So vp.add(vp.add(X, Y, M), Z, M) becomes vp.mask(add(vp.mask(add(X, Y), M), Z), M) becomes vp.mask(vp.mask(add(add(X, Y), Z), M), M) becomes vp.mask(add(add(X, Y), Z), M), at which point add(add(X, Y), Z) optimizes as usual.

[simoll]

This is really on two separate things: First on generalized pattern matching, the second on vector predication (which is only one of the intrinsics sets benefiting from this).

In D92086#3572881, @nikic wrote:

This fails to build with:

lib/libLLVMInstCombine.a(InstructionCombining.cpp.o):InstructionCombining.cpp:function llvm::InstCombinerImpl::visitGEPOfGEP(llvm::GetElementPtrInst&, llvm::GEPOperator*): error: undefined reference to 'llvm::Value* llvm::simplifyAddInst(llvm::Value*, llvm::Value*, bool, bool, llvm::SimplifyQuery const&, llvm::MatcherContext&)'

Probably due to illegal use of inline. You need to use static inline if you don't add extern inline definitions. (Or possibly a missing explicit template instantiation, but I think that wouldn't be used by InstCombine with this patch.)

It compiles on my system. I am fixing this with the next patch update.

I'm generally very skeptical about this proposal. This adds a lot of additional complexity to the area of LLVM that likely already has the highest ratio between lines of code changed and review time / amount of tests. After adding tests for baseline behavior, 16 commuted variants, nowrap/FMF variations, vector splat, undef-splat and non-splat variations, and negative tests for all used conditions (including all pattern match conditions), I definitely would rather not add variation tests for VP and constrained FP intrinsics (with which I am not familiar) as well.

If we want to optimize all those new intrinsics, matrix, constrained, saturating, then we will have to add new logic to do so.
You can have the complexity elsewhere but you cannot get rid of it. I am advocating here for re-using the existing code instead of replicating the same or similar pattern-rewriting logic elsewhere, once for each intrinsic set.
Regarding coverage, we could auto-generate intrinsic tests from the instruction combiner tests. The test generators could also explicitly target issues as the ones you are describing next (masked out zero-lanes).

I guess one could make an argument that if one uses the generalized matchers, there is nothing that could possibly go wrong, and there is no need to actually test these pattern or understand their correctness. I'm doubtful that this is actually true though. It's almost certainly not true for InstCombine, but even in InstSimplify I expect that there would be some dangerous interaction with predicated div/rem opcodes. Presumably, a zero value in a masked out lane does not render the program undefined, and as such an InstSimplify fold to a poison value would be incorrect.

That's a fair point, the traits have to be carefully crafted as to not allow invalid rewrites. I see a clear strategy here: we start with very strict traits that bail pattern matching early as soon as we are stepping out of our comfort zone. Eg, we can make a trait bail around divisions initially to study the problem better and find the right trait logic to make them work.

Another concern here is compile-time, but I won't be able to test that until there is an actually buildable patch.

Agreed, also code size if you instantiate for too many traits. I see two approaches to mitigate these issues:

• We can use virtual dispatch instead of template instantiation (or template-instantiate only twice: one for trait-less pattern matching and once again for virtual dispatch).
• We can have a cmake variable that controls instantation and if your distribution does not care about constrained fp or vp, say, you just don't instantiate for it and won't see compile time or size increases. I was hinting in that direction with the EnabledTraits.def file.

In D92086#3572881, @nikic wrote:

A possibly stupid question from someone who has not followed the VP design: Why does the predication need to happen on every single instruction? Naively, I'd assume that predication is only important for instructions that have trapping behavior, which is basically just load/store and div/rem class intrinsics. For everything else, it should be fine to represent this as a normal vector add, and then a single masking operation at the end. One could then propagate that masking backwards in the backend. That should ensure that normal instructions optimize fine, while instructions where the masking is semantically relevant (like div/rem) do not blindly participate in optimizations.

So basically, vp.add(X, Y, M) can be decomposed into vp.mask(add(X, Y), M), where the vp.mask intrinsic can be pushed down and combined with other mask intrinsics. So vp.add(vp.add(X, Y, M), Z, M) becomes vp.mask(add(vp.mask(add(X, Y), M), Z), M) becomes vp.mask(vp.mask(add(add(X, Y), Z), M), M) becomes vp.mask(add(add(X, Y), Z), M), at which point add(add(X, Y), Z) optimizes as usual.

VP intrinsics exist primarily to have a way to express the dynamic vector length for architectures like RISC-V V extension and SX-Aurora (VE target).
Every single instruction can have a different vector length and that parameter has performance implications (latency).
There exist vector codes that exploit vector length switching for better performance (to blend lanes, to compress sparse vectors and then operate on the dense data, etc).
The mask does not strictly need to be there for every instruction - integer add/sub are examples for this. Some, such as sdiv/srem strictly need it. However, you can exploit the mask by using a compressed_store/expanding_load when a sparse vector register is spilled. Where the mask is not needed you can always pass in an all-ones mask to disable it.
The long term strategy with the VP proposal is to push the mask and evl parameter into something like operand bundles that you can simply tag on regular instructions. Intrinsics are just a bridge technology, if you will. Before we can do that, however, LLVM has to be capable of optimizing masked instructions (we cannot ignore predication for the same reason we cannot have too permissive traits). Making LLVM predication-ready is what prompted generalized pattern matching.

[simoll]

• inline -> static inline
• rebased

[nikic]

This still fails to link. It looks like explicit template instantiations are missing for simplifyAddInst (they are present for simplifyBinOp for example).

Edit: simplifyFAddInst is missing as well.

[simoll]

• Fixed m_ExtractValue pattern (all tests passing now).
• Add cmake variable to control which traits InstSimplify will be instantiated for (LLVM_OPTIMIZER_TRAITS_TO_INSTANTIATE .. eg VPTrait;CFPTrait).
• Explicitly instantiate InstSimplify templates.

[nikic]

We can have a cmake variable that controls instantation and if your distribution does not care about constrained fp or vp, say, you just don't instantiate for it and won't see compile time or size increases. I was hinting in that direction with the EnabledTraits.def file.

I don't think this makes a lot sense. There's no way we can disable this from the distribution side if constrained FP and VP are core parts of LLVM (which at least the former is at this point, given that it is exposed by Clang). If you want to do this you'll also have to export variables for llvm-lit, so tests can be disabled based on which traits are enabled. I don't think we want to go there.

I'd really like to have a working patch (with enabled traits) so I can give this a basic compile-time evaluation at least.

[simoll]

In D92086#3609003, @nikic wrote:

We can have a cmake variable that controls instantation and if your distribution does not care about constrained fp or vp, say, you just don't instantiate for it and won't see compile time or size increases. I was hinting in that direction with the EnabledTraits.def file.

I don't think this makes a lot sense. There's no way we can disable this from the distribution side if constrained FP and VP are core parts of LLVM (which at least the former is at this point, given that it is exposed by Clang). If you want to do this you'll also have to export variables for llvm-lit, so tests can be disabled based on which traits are enabled. I don't think we want to go there.

I'd really like to have a working patch (with enabled traits) so I can give this a basic compile-time evaluation at least.

Well, What isn't working on your system? All templates should be instantiated now. Please share your build configuration because static/dylib/shared lib builds of LLVM work fine on my system.
The cmake variable (in the reference patch), let's you run compile time tests with different trait configurations: cmake -DLLVM_OPTIMIZER_TRAITS_TO_INSTANTIATE=all. Whether we actually want a cmake variable is a different story. However, there is precedent in the TARGETS_TO_BUILD cmake variable: Distributions can configure the enabled backends. Yet, there are target-specific intrinsics in every LLVM distribution. I wouldn't be surprised if some distributors removed those manually to make their builds smaller.

[frasercrmck]

llvm/test/Transforms/InstSimplify/add_vp.ll

1

Could we pre-commit these new tests to better show off the diff this patch enables?

[simoll]

Rebase onto committed add_vp.ll test to better show improvement

llvm/CMakeLists.txt

 # This CMake flag enables a more strict mode where it asserts that the type
 # is not a scalable vector type.
 #
 # Enabling this flag makes it easier to find cases where the compiler makes
 # assumptions on the size being 'fixed size', when building tests for
 # SVE/SVE2 or other scalable vector architectures.
 option(LLVM_ENABLE_STRICT_FIXED_SIZE_VECTORS
        "Enable assertions that type is not scalable in implicit conversion from TypeSize to uint64_t and calls to getNumElements" OFF)
+set(LLVM_OPTIMIZER_TRAITS_TO_INSTANTIATE ""
+       CACHE STRING "Semicolon-separated list of traits to instantiate in instruction simplification passes, or \"all\".")
+set(LLVM_ALL_OPTIMIZER_TRAITS "EmptyTrait;VPTrait;CFPTrait")
 
 set(LLVM_ABI_BREAKING_CHECKS "WITH_ASSERTS" CACHE STRING
   "Enable abi-breaking checks.  Can be WITH_ASSERTS, FORCE_ON or FORCE_OFF.")
 
 option(LLVM_FORCE_USE_OLD_TOOLCHAIN
        "Set to ON to force using an old, unsupported host toolchain." OFF)
 
 set(LLVM_LOCAL_RPATH "" CACHE FILEPATH

llvm/cmake/modules/HandleLLVMOptions.cmake

 
 if(LLVM_INCLUDE_TESTS)
   # Lit test suite requires at least python 3.6
   set(LLVM_MINIMUM_PYTHON_VERSION 3.6)
 else()
   # FIXME: it is unknown if this is the actual minimum bound
   set(LLVM_MINIMUM_PYTHON_VERSION 3.0)
 endif()
+
+if( LLVM_OPTIMIZER_TRAITS_TO_INSTANTIATE STREQUAL "all" )
+  set(LLVM_OPTIMIZER_TRAITS_TO_INSTANTIATE ${LLVM_ALL_OPTIMIZER_TRAITS})
+else()
+  set(LLVM_OPTIMIZER_TRAITS_TO_INSTANTIATE "EmptyTrait;${LLVM_OPTIMIZER_TRAITS_TO_INSTANTIATE}")
+  list(REMOVE_DUPLICATES LLVM_OPTIMIZER_TRAITS_TO_INSTANTIATE)
+endif()
+
+foreach (t ${LLVM_OPTIMIZER_TRAITS_TO_INSTANTIATE})
+  if (NOT "${t}" IN_LIST LLVM_ALL_OPTIMIZER_TRAITS)
+    message(FATAL_ERROR "Unknown trait in LLVM_OPTIMIZER_TRAITS_TO_INSTANTIATE: \"${t}\"!")
+  endif()
+endforeach(t)

llvm/include/llvm/Analysis/InstructionSimplify.h

 // def-reachable, meaning we can't just scan the basic block for instructions
 // to simplify to.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H
 #define LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H
 
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Operator.h"
 #include "llvm/IR/PatternMatch.h"
+#include "llvm/IR/Traits/SemanticTrait.h"
 
 namespace llvm {
 
 template <typename T, typename... TArgs> class AnalysisManager;
 template <class T> class ArrayRef;
 class AssumptionCache;
 class BinaryOperator;
 class CallBase;
 class DataLayout;
 class DominatorTree;
 class Function;
 class Instruction;
 struct LoopStandardAnalysisResults;
 class MDNode;
 class OptimizationRemarkEmitter;
 class Pass;
 template <class T, unsigned n> class SmallSetVector;
 class TargetLibraryInfo;
 class Type;
 class Value;
 
 /// InstrInfoQuery provides an interface to query additional information for
 /// instructions like metadata or keywords like nsw, which provides conservative
 /// results if the users specified it is safe to use.
+/// FIXME: Incorporate this into trait framework.
 struct InstrInfoQuery {
   InstrInfoQuery(bool UMD) : UseInstrInfo(UMD) {}
   InstrInfoQuery() = default;
   bool UseInstrInfo = true;
 
   MDNode *getMetadata(const Instruction *I, unsigned KindID) const {
     if (UseInstrInfo)
       return I->getMetadata(KindID);
     return nullptr;
   }
 
   template <class InstT> bool hasNoUnsignedWrap(const InstT *Op) const {
     if (UseInstrInfo)
       return Op->hasNoUnsignedWrap();
     return false;
   }
 
   template <class InstT> bool hasNoSignedWrap(const InstT *Op) const {
     if (UseInstrInfo)
       return Op->hasNoSignedWrap();
     return false;
   }
 
-  bool isExact(const BinaryOperator *Op) const {
-    if (UseInstrInfo && isa<PossiblyExactOperator>(Op))
-      return cast<PossiblyExactOperator>(Op)->isExact();
+  bool isExact(const Instruction *I) const {
+    if (UseInstrInfo && isa<PossiblyExactOperator>(I))
+      return cast<PossiblyExactOperator>(I)->isExact();
     return false;
   }
 };
 
 struct SimplifyQuery {
   const DataLayout &DL;
   const TargetLibraryInfo *TLI = nullptr;
   const DominatorTree *DT = nullptr;

 // NOTE: the explicit multiple argument versions of these functions are
 // deprecated.
 // Please use the SimplifyQuery versions in new code.
 
 /// Given operand for an FNeg, fold the result or return null.
 Value *simplifyFNegInst(Value *Op, FastMathFlags FMF, const SimplifyQuery &Q);
 
 /// Given operands for an Add, fold the result or return null.
+template <typename Trait>
 Value *simplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
-                       const SimplifyQuery &Q);
+                       const SimplifyQuery &Q, MatcherContext<Trait> &Matcher);
+
+static inline Value *simplifyAddInst(Value *LHS, Value *RHS, bool isNSW,
+                                     bool isNUW, const SimplifyQuery &Q) {
+  MatcherContext<DefaultTrait> Matcher;
+  return simplifyAddInst<DefaultTrait>(LHS, RHS, isNSW, isNUW, Q, Matcher);
+}
 
 /// Given operands for a Sub, fold the result or return null.
 Value *simplifySubInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
                        const SimplifyQuery &Q);
 
-/// Given operands for an FAdd, fold the result or return null.
+/// Given operands for an FAdd, and a matcher context that was initialized for
+/// the actual instruction, fold the result or return null.
+template <typename Trait>
 Value *
 simplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF,
-                 const SimplifyQuery &Q,
+                 const SimplifyQuery &Q, MatcherContext<Trait> &Matcher,
                  fp::ExceptionBehavior ExBehavior = fp::ebIgnore,
                  RoundingMode Rounding = RoundingMode::NearestTiesToEven);
 
+/// Given operands for an FAdd, fold the result or return null.
+/// We don't have any information about the traits of the 'fadd' so run this
+/// with the unassuming default trait.
+static inline Value *
+simplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF,
+                 const SimplifyQuery &Q,
+                 fp::ExceptionBehavior ExBehavior = fp::ebIgnore,
+                 RoundingMode Rounding = RoundingMode::NearestTiesToEven) {
+  MatcherContext<DefaultTrait> Matcher;
+  return simplifyFAddInst(LHS, RHS, FMF, Q, Matcher, ExBehavior, Rounding);
+}
+
 /// Given operands for an FSub, fold the result or return null.
 Value *
 simplifyFSubInst(Value *LHS, Value *RHS, FastMathFlags FMF,
                  const SimplifyQuery &Q,
                  fp::ExceptionBehavior ExBehavior = fp::ebIgnore,
                  RoundingMode Rounding = RoundingMode::NearestTiesToEven);
 
 /// Given operands for an FMul, fold the result or return null.

 Value *simplifyUnOp(unsigned Opcode, Value *Op, const SimplifyQuery &Q);
 
 /// Given operand for a UnaryOperator, fold the result or return null.
 /// Try to use FastMathFlags when folding the result.
 Value *simplifyUnOp(unsigned Opcode, Value *Op, FastMathFlags FMF,
                     const SimplifyQuery &Q);
 
 /// Given operands for a BinaryOperator, fold the result or return null.
+template <typename Trait>
 Value *simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
-                     const SimplifyQuery &Q);
+                     const SimplifyQuery &Q, MatcherContext<Trait> &Matcher);
+
+static inline Value *simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
+                                   const SimplifyQuery &Q) {
+  MatcherContext<DefaultTrait> Matcher;
+  return simplifyBinOp<>(Opcode, LHS, RHS, Q, Matcher);
+}
 
 /// Given operands for a BinaryOperator, fold the result or return null.
 /// Try to use FastMathFlags when folding the result.
+template <typename Trait>
 Value *simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, FastMathFlags FMF,
-                     const SimplifyQuery &Q);
+                     const SimplifyQuery &Q, MatcherContext<Trait> &Matcher);
+
+static inline Value *simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
+                                   FastMathFlags FMF, const SimplifyQuery &Q) {
+  MatcherContext<DefaultTrait> Matcher;
+  return simplifyBinOp(Opcode, LHS, RHS, FMF, Q, Matcher);
+}
 
 /// Given a callsite, fold the result or return null.
 Value *simplifyCall(CallBase *Call, const SimplifyQuery &Q);
 
 /// Given a constrained FP intrinsic call, tries to compute its simplified
 /// version. Returns a simplified result or null.
 ///
 /// This function provides an additional contract: it guarantees that if
 /// simplification succeeds that the intrinsic is side effect free. As a result,
 /// successful simplification can be used to delete the intrinsic not just
 /// replace its result.
 Value *simplifyConstrainedFPCall(CallBase *Call, const SimplifyQuery &Q);
 
 /// Given an operand for a Freeze, see if we can fold the result.
 /// If not, this returns null.
 Value *simplifyFreezeInst(Value *Op, const SimplifyQuery &Q);
 
 /// See if we can compute a simplified version of this instruction. If not,
 /// return null.
+template <typename Trait>
+Value *simplifyInstructionWithOperandsAndTrait(
+    Instruction *I, ArrayRef<Value *> NewOps, const SimplifyQuery &Q,
+    OptimizationRemarkEmitter *ORE = nullptr);
+
 Value *simplifyInstruction(Instruction *I, const SimplifyQuery &Q,
                            OptimizationRemarkEmitter *ORE = nullptr);
 
 /// Like \p simplifyInstruction but the operands of \p I are replaced with
 /// \p NewOps. Returns a simplified value, or null if none was found.
 Value *
 simplifyInstructionWithOperands(Instruction *I, ArrayRef<Value *> NewOps,
                                 const SimplifyQuery &Q,

llvm/include/llvm/IR/CMakeLists.txt

 tablegen(LLVM IntrinsicsRISCV.h -gen-intrinsic-enums -intrinsic-prefix=riscv)
 tablegen(LLVM IntrinsicsSPIRV.h -gen-intrinsic-enums -intrinsic-prefix=spv)
 tablegen(LLVM IntrinsicsS390.h -gen-intrinsic-enums -intrinsic-prefix=s390)
 tablegen(LLVM IntrinsicsWebAssembly.h -gen-intrinsic-enums -intrinsic-prefix=wasm)
 tablegen(LLVM IntrinsicsX86.h -gen-intrinsic-enums -intrinsic-prefix=x86)
 tablegen(LLVM IntrinsicsXCore.h -gen-intrinsic-enums -intrinsic-prefix=xcore)
 tablegen(LLVM IntrinsicsVE.h -gen-intrinsic-enums -intrinsic-prefix=ve)
 add_public_tablegen_target(intrinsics_gen)
+
+
+# TODO: Sanitize Trait list
+set(ENABLED_TRAITS_FILE ${CMAKE_CURRENT_BINARY_DIR}/Traits/EnabledTraits.def)
+add_custom_target(enabled_traits DEPENDS ${ENABLED_TRAITS_FILE})
+
+set(ENABLED_TRAITS_CONTENT "#undef ENABLE_TRAIT")
+foreach(t ${LLVM_OPTIMIZER_TRAITS_TO_INSTANTIATE})
+  set(ENABLED_TRAITS_CONTENT "ENABLE_TRAIT(${t})\n${ENABLED_TRAITS_CONTENT}")
+endforeach(t)
+file(GENERATE OUTPUT ${ENABLED_TRAITS_FILE} CONTENT ${ENABLED_TRAITS_CONTENT})
+
+set_property(DIRECTORY APPEND PROPERTY ADDITIONAL_MAKE_CLEAN_FILES ${ENABLED_TRAITS_FILE})
+if(LLVM_COMMON_DEPENDS)
+  add_dependencies(enabled_traits ${LLVM_COMMON_DEPENDS})
+endif()
+set(LLVM_COMMON_DEPENDS ${LLVM_COMMON_DEPENDS} enabled_traits PARENT_SCOPE)

llvm/include/llvm/IR/IntrinsicInst.h

public:
   static bool classof(const Value *V) {
     return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
   }
 
   // Equivalent non-predicated opcode
   Optional<unsigned> getFunctionalOpcode() const {
     return getFunctionalOpcodeForVP(getIntrinsicID());
   }
+  bool isFunctionalCommutative() const {
+    if (auto OpcodeOpt = getFunctionalOpcode())
+      return Instruction::isCommutative(*OpcodeOpt);
+    return false;
+  }
+  bool isFunctionalUnaryOp() const {
+    if (auto OpcodeOpt = getFunctionalOpcode())
+      return Instruction::isUnaryOp(*OpcodeOpt);
+    return false;
+  }
+  bool isFunctionalBinaryOp() const {
+    if (auto OpcodeOpt = getFunctionalOpcode())
+      return Instruction::isBinaryOp(*OpcodeOpt);
+    return false;
+  }
 
   // Equivalent non-predicated opcode
   static Optional<unsigned> getFunctionalOpcodeForVP(Intrinsic::ID ID);
 };
 
 /// This represents vector predication reduction intrinsics.
 class VPReductionIntrinsic : public VPIntrinsic {
 public:
public:
   /// @}
 };
 
 /// This is the common base class for constrained floating point intrinsics.
 class ConstrainedFPIntrinsic : public IntrinsicInst {
 public:
   bool isUnaryOp() const;
   bool isTernaryOp() const;
+  bool hasRoundingMode() const;
   Optional<RoundingMode> getRoundingMode() const;
   Optional<fp::ExceptionBehavior> getExceptionBehavior() const;
   bool isDefaultFPEnvironment() const;
 
+  Optional<unsigned> getFunctionalOpcode() const;
+  bool isFunctionalCommutative() const {
+    if (auto OpcOpt = getFunctionalOpcode())
+      return Instruction::isCommutative(*OpcOpt);
+    return false;
+  }
+  bool isFunctionalUnaryOp() const {
+    if (auto OpcOpt = getFunctionalOpcode())
+      return Instruction::isUnaryOp(*OpcOpt);
+    return false;
+  }
+  bool isFunctionalBinaryOp() const {
+    if (auto OpcOpt = getFunctionalOpcode())
+      return Instruction::isBinaryOp(*OpcOpt);
+    return false;
+  }
+
   // Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const IntrinsicInst *I);
   static bool classof(const Value *V) {
     return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
   }
 };
 
 /// Constrained floating point compare intrinsics.

llvm/include/llvm/IR/PatternMatch.h

 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Operator.h"
+#include "llvm/IR/Traits/SemanticTrait.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/Casting.h"
+
 #include <cstdint>
 
 namespace llvm {
 namespace PatternMatch {
 
+// Trait-match pattern in a given context and update the context.
 template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) {
+  // TODO: Use this instead of the Trait-less Pattern::match() functions. This
+  // single function does the same as the Trait-less 'Pattern::match()'
+  // functions that are replicated once for every Pattern.
   return const_cast<Pattern &>(P).match(V);
 }
 
+// Trait-match pattern in a given context and update the context.
+template <typename Val, typename Pattern, typename Trait>
+bool match(Val *V, const Pattern &P, MatcherContext<Trait> &MContext) {
+  return const_cast<Pattern &>(P).match(V, MContext);
+}
+
+// Trait-match pattern and update the context on match.
+template <typename Val, typename Pattern, typename Trait>
+bool try_match(Val *V, const Pattern &P, MatcherContext<Trait> &MContext) {
+  MatcherContext<Trait> CopyCtx(MContext);
+  if (const_cast<Pattern &>(P).match(V, CopyCtx)) {
+    MContext = CopyCtx;
+    return true;
+  }
+  return false;
+}
+
 template <typename Pattern> bool match(ArrayRef<int> Mask, const Pattern &P) {
   return const_cast<Pattern &>(P).match(Mask);
 }
 
 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 ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> MContext;
+    return match(V, MContext);
+  }
+
+  template <typename OpTy, typename Trait = DefaultTrait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    return V->hasOneUse() && SubPattern.match(V, MContext);
   }
 };
 
 template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) {
   return SubPattern;
 }
 
 template <typename Class> struct class_match {
-  template <typename ITy> bool match(ITy *V) { return isa<Class>(V); }
+
+  template <typename ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> MContext;
+    return match(V, MContext);
+  }
+
+  template <typename ITy, typename Trait = DefaultTrait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
+    return trait_isa<Trait, 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() {
   return class_match<UnaryOperator>();
static bool check(const Value *V) {
 
     while (!Worklist.empty()) {
       if (!CheckValue(Worklist.pop_back_val()))
         return false;
     }
     return true;
   }
   template <typename ITy> bool match(ITy *V) { return check(V); }
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
+    // FIXME: Ok, to ignore the context here?
+    return check(V);
+  }
 };
 
 /// Match an arbitrary undef constant. This matches poison as well.
 /// If this is an aggregate and contains a non-aggregate element that is
 /// neither undef nor poison, the aggregate is not matched.
 inline auto m_Undef() { return undef_match(); }
 
 /// Match an arbitrary poison constant.

 }
 
 /// Inverting matcher
 template <typename Ty> struct match_unless {
   Ty M;
 
   match_unless(const Ty &Matcher) : M(Matcher) {}
 
-  template <typename ITy> bool match(ITy *V) { return !M.match(V); }
+  template <typename ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> MContext;
+    return match(V, MContext);
+  }
+
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
+    return !M.match(V, MContext);
+  }
 };
 
 /// Match if the inner matcher does *NOT* match.
 template <typename Ty> inline match_unless<Ty> m_Unless(const Ty &M) {
   return match_unless<Ty>(M);
 }
 
 /// Matching combinators
 template <typename LTy, typename RTy> struct match_combine_or {
   LTy L;
   RTy R;
 
   match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
 
   template <typename ITy> bool match(ITy *V) {
-    if (L.match(V))
-      return true;
-    if (R.match(V))
+    MatcherContext<DefaultTrait> MContext;
+    return match(V, MContext);
+  }
+
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
+    if (try_match(V, L, MContext)) {
       return true;
-    return false;
+    }
+    return R.match(V, MContext);
   }
 };
 
 template <typename LTy, typename RTy> struct match_combine_and {
   LTy L;
   RTy R;
 
   match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
 
   template <typename ITy> bool match(ITy *V) {
-    if (L.match(V))
-      if (R.match(V))
-        return true;
-    return false;
+    MatcherContext<DefaultTrait> MContext;
+    return match(V, MContext);
+  }
+
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
+    return L.match(V, MContext) && R.match(V, MContext);
   }
 };
 
 /// Combine two pattern matchers matching L || R
 template <typename LTy, typename RTy>
 inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) {
   return match_combine_or<LTy, RTy>(L, R);
 }
 
 /// Combine two pattern matchers matching L && R
 template <typename LTy, typename RTy>
 inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) {
   return match_combine_and<LTy, RTy>(L, R);
 }
 
 struct apint_match {
   const APInt *&Res;
   bool AllowUndef;
 
   apint_match(const APInt *&Res, bool AllowUndef)
       : Res(Res), AllowUndef(AllowUndef) {}
 
   template <typename ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> MContext;
+    return match(V, MContext);
+  }
+
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
     if (auto *CI = dyn_cast<ConstantInt>(V)) {
       Res = &CI->getValue();
       return true;
     }
     if (V->getType()->isVectorTy())
       if (const auto *C = dyn_cast<Constant>(V))
         if (auto *CI =
                 dyn_cast_or_null<ConstantInt>(C->getSplatValue(AllowUndef))) {

 struct apfloat_match {
   const APFloat *&Res;
   bool AllowUndef;
 
   apfloat_match(const APFloat *&Res, bool AllowUndef)
       : Res(Res), AllowUndef(AllowUndef) {}
 
   template <typename ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> MContext;
+    return match(V, MContext);
+  }
+
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
     if (auto *CI = dyn_cast<ConstantFP>(V)) {
       Res = &CI->getValueAPF();
       return true;
     }
     if (V->getType()->isVectorTy())
       if (const auto *C = dyn_cast<Constant>(V))
         if (auto *CI =
                 dyn_cast_or_null<ConstantFP>(C->getSplatValue(AllowUndef))) {

 
 /// Match APFloat while forbidding undefs in splat vector constants.
 inline apfloat_match m_APFloatForbidUndef(const APFloat *&Res) {
   return apfloat_match(Res, /* AllowUndef */ false);
 }
 
 template <int64_t Val> struct constantint_match {
   template <typename ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> MContext;
+    return match(V, MContext);
+  }
+
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
     if (const auto *CI = dyn_cast<ConstantInt>(V)) {
       const APInt &CIV = CI->getValue();
       if (Val >= 0)
         return CIV == static_cast<uint64_t>(Val);
       // If Val is negative, and CI is shorter than it, truncate to the right
       // number of bits.  If it is larger, then we have to sign extend.  Just
       // compare their negated values.
       return -CIV == -Val;
     }
     return false;
   }
 };
 
 /// Match a ConstantInt with a specific value.
 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.
+/// This helper class is used to match scalar and fixed width vector integer
+/// constants that satisfy a specified predicate.
+/// For vector constants, undefined elements are ignored.
 template <typename Predicate, typename ConstantVal>
 struct cstval_pred_ty : public Predicate {
   template <typename ITy> bool match(ITy *V) {
-    if (const auto *CV = dyn_cast<ConstantVal>(V))
-      return this->isValue(CV->getValue());
+    MatcherContext<DefaultTrait> MContext;
+    return match(V, MContext);
+  }
+
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
+    if (const auto *CI = dyn_cast<ConstantVal>(V))
+      return this->isValue(CI->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());
 
         // Number of elements of a scalable vector unknown at compile time
         auto *FVTy = dyn_cast<FixedVectorType>(VTy);
         if (!FVTy)

 /// This helper class is used to match scalar and vector constants that
 /// satisfy a specified predicate, and bind them to an APInt.
 template <typename Predicate> struct api_pred_ty : public Predicate {
   const APInt *&Res;
 
   api_pred_ty(const APInt *&R) : Res(R) {}
 
   template <typename ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> MContext;
+    return match(V, MContext);
+  }
+
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
     if (const auto *CI = dyn_cast<ConstantInt>(V))
       if (this->isValue(CI->getValue())) {
         Res = &CI->getValue();
         return true;
       }
     if (V->getType()->isVectorTy())
       if (const auto *C = dyn_cast<Constant>(V))
         if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))

 /// satisfy a specified predicate, and bind them to an APFloat.
 /// Undefs are allowed in splat vector constants.
 template <typename Predicate> struct apf_pred_ty : public Predicate {
   const APFloat *&Res;
 
   apf_pred_ty(const APFloat *&R) : Res(R) {}
 
   template <typename ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
     if (const auto *CI = dyn_cast<ConstantFP>(V))
       if (this->isValue(CI->getValue())) {
         Res = &CI->getValue();
         return true;
       }
     if (V->getType()->isVectorTy())
       if (const auto *C = dyn_cast<Constant>(V))
         if (auto *CI = dyn_cast_or_null<ConstantFP>(

 /// Match an integer 0 or a vector with all elements equal to 0.
 /// For vectors, this includes constants with undefined elements.
 inline cst_pred_ty<is_zero_int> m_ZeroInt() {
   return cst_pred_ty<is_zero_int>();
 }
 
 struct is_zero {
   template <typename ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> MContext;
+    return match(V, MContext);
+  }
+
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
     auto *C = dyn_cast<Constant>(V);
     // FIXME: this should be able to do something for scalable vectors
     return C && (C->isNullValue() || cst_pred_ty<is_zero_int>().match(C));
   }
 };
 /// Match any null constant or a vector with all elements equal to 0.
 /// For vectors, this includes constants with undefined elements.
 inline is_zero m_Zero() { return is_zero(); }

 ///////////////////////////////////////////////////////////////////////////////
 
 template <typename Class> struct bind_ty {
   Class *&VR;
 
   bind_ty(Class *&V) : VR(V) {}
 
   template <typename ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> MContext;
+    return match(V, MContext);
+  }
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
+    if (!MContext.accept(V))
+      return false;
     if (auto *CV = dyn_cast<Class>(V)) {
       VR = CV;
       return true;
     }
     return false;
   }
 };
 

 }
 
 /// Match a specified Value*.
 struct specificval_ty {
   const Value *Val;
 
   specificval_ty(const Value *V) : Val(V) {}
 
-  template <typename ITy> bool match(ITy *V) { return V == Val; }
+  template <typename ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> MContext;
+    return match(V, MContext);
+  }
+
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
+    return V == Val;
+  }
 };
 
 /// Match if we have a specific specified value.
 inline specificval_ty m_Specific(const Value *V) { return V; }
 
 /// Stores a reference to the Value *, not the Value * itself,
 /// thus can be used in commutative matchers.
 template <typename Class> struct deferredval_ty {
   Class *const &Val;
 
   deferredval_ty(Class *const &V) : Val(V) {}
 
-  template <typename ITy> bool match(ITy *const V) { return V == Val; }
+  template <typename ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+
+  template <typename ITy, typename Trait>
+  bool match(ITy *const V, MatcherContext<Trait> &MContext) {
+    return V == Val;
+  }
 };
 
 /// Like m_Specific(), but works if the specific value to match is determined
 /// as part of the same match() expression. For example:
 /// m_Add(m_Value(X), m_Specific(X)) is incorrect, because m_Specific() will
 /// bind X before the pattern match starts.
 /// m_Add(m_Value(X), m_Deferred(X)) is correct, and will check against
 /// whichever value m_Value(X) populated.
 inline deferredval_ty<Value> m_Deferred(Value *const &V) { return V; }
 inline deferredval_ty<const Value> m_Deferred(const Value *const &V) {
   return V;
 }
 
 /// Match a specified floating point value or vector of all elements of
 /// that value.
 struct specific_fpval {
   double Val;
 
   specific_fpval(double V) : Val(V) {}
 
   template <typename ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
     if (const auto *CFP = dyn_cast<ConstantFP>(V))
       return CFP->isExactlyValue(Val);
     if (V->getType()->isVectorTy())
       if (const auto *C = dyn_cast<Constant>(V))
         if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
           return CFP->isExactlyValue(Val);
     return false;
   }
 };
 
 /// Match a specific floating point value or vector with all elements
 /// equal to the value.
 inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); }
 
 /// Match a float 1.0 or vector with all elements equal to 1.0.
 inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); }
 
 struct bind_const_intval_ty {
   uint64_t &VR;
 
   bind_const_intval_ty(uint64_t &V) : VR(V) {}
 
   template <typename ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
+    if (!MContext.accept(V))
+      return false;
     if (const auto *CV = dyn_cast<ConstantInt>(V))
       if (CV->getValue().ule(UINT64_MAX)) {
         VR = CV->getZExtValue();
         return true;
       }
     return false;
   }
 };
 
 /// Match a specified integer value or vector of all elements of that
 /// value.
 template <bool AllowUndefs> struct specific_intval {
   APInt Val;
 
   specific_intval(APInt V) : Val(std::move(V)) {}
 
   template <typename ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
+    if (!MContext.accept(V))
+      return false;
     const auto *CI = dyn_cast<ConstantInt>(V);
     if (!CI && V->getType()->isVectorTy())
       if (const auto *C = dyn_cast<Constant>(V))
         CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue(AllowUndefs));
 
     return CI && APInt::isSameValue(CI->getValue(), Val);
   }
 };

 
 /// Match a specified basic block value.
 struct specific_bbval {
   BasicBlock *Val;
 
   specific_bbval(BasicBlock *Val) : Val(Val) {}
 
   template <typename ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
+    if (!MContext.accept(V))
+      return false;
     const auto *BB = dyn_cast<BasicBlock>(V);
     return BB && BB == Val;
   }
 };
 
 /// Match a specific basic block value.
 inline specific_bbval m_SpecificBB(BasicBlock *BB) {
   return specific_bbval(BB);
 }
 
 /// A commutative-friendly version of m_Specific().
 inline deferredval_ty<BasicBlock> m_Deferred(BasicBlock *const &BB) {
   return BB;
 }
 inline deferredval_ty<const BasicBlock>
 m_Deferred(const BasicBlock *const &BB) {
   return BB;
 }
 
+template <typename LHS_t, typename RHS_t, typename Trait, typename OpValueTy>
+static inline bool commutable_match(bool Commutable, LHS_t &L, RHS_t &R,
+                                    OpValueTy OpL, OpValueTy OpR,
+                                    MatcherContext<Trait> &MContext) {
+  MatcherContext<Trait> LRContext(MContext);
+  if (L.match(OpL, LRContext) && R.match(OpR, LRContext)) {
+    MContext = LRContext;
+    return true;
+  }
+  return Commutable && L.match(OpR, MContext) && R.match(OpL, MContext);
+}
+
 //===----------------------------------------------------------------------===//
 // Matcher for any binary operator.
 //
 template <typename LHS_t, typename RHS_t, bool Commutable = false>
 struct AnyBinaryOp_match {
   LHS_t L;
   RHS_t R;
 
   // The evaluation order is always stable, regardless of Commutability.
   // The LHS is always matched first.
   AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (auto *I = dyn_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)));
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    auto *I = trait_dyn_cast<Trait, BinaryOperator>(V);
+    if (!I)
       return false;
+
+    if (!MContext.accept(I))
+      return false;
+
+    return commutable_match<>(Commutable, L, R, I->getOperand(0),
+                              I->getOperand(1), MContext);
   }
 };
 
 template <typename LHS, typename RHS>
 inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
   return AnyBinaryOp_match<LHS, RHS>(L, R);
 }
 
 //===----------------------------------------------------------------------===//
 // Matcher for any unary operator.
 // TODO fuse unary, binary matcher into n-ary matcher
 //
 template <typename OP_t> struct AnyUnaryOp_match {
   OP_t X;
 
   AnyUnaryOp_match(const OP_t &X) : X(X) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (auto *I = dyn_cast<UnaryOperator>(V))
-      return X.match(I->getOperand(0));
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    if (auto *I = trait_dyn_cast<Trait, UnaryOperator>(V))
+      return X.match(I->getOperand(0), MContext);
     return false;
   }
 };
 
 template <typename OP_t> inline AnyUnaryOp_match<OP_t> m_UnOp(const OP_t &X) {
   return AnyUnaryOp_match<OP_t>(X);
 }
 
 //===----------------------------------------------------------------------===//
 // 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;
 
   // 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)));
+  template <typename OpTy> bool match(OpTy *V) {
+    MatcherContext<DefaultTrait> Matcher;
+    return match(Opcode, V, Matcher);
+  }
+
+  template <typename OpTy> bool match(unsigned Opc, OpTy *V) {
+    MatcherContext<DefaultTrait> Matcher;
+    return match(Opc, V, Matcher);
+  }
+
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &Matcher) {
+    return match(Opcode, V, Matcher);
+  }
+
+  template <typename OpTy, typename Trait>
+  bool match(unsigned Opc, OpTy *V, MatcherContext<Trait> &MContext) {
+    if (!MContext.accept(V))
+      return false;
+    auto *I = trait_dyn_cast<Trait, const BinaryOperator>(V);
+    if (I && I->getOpcode() == Opc) {
+      return commutable_match(Commutable, L, R, I->getOperand(0),
+                              I->getOperand(1), MContext);
     }
     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))));
+             commutable_match(Commutable, L, R, CE->getOperand(0),
+                              CE->getOperand(1), MContext);
     return false;
   }
-
-  template <typename OpTy> bool match(OpTy *V) { return match(Opcode, V); }
 };
 
 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);
 }
 
inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L,
   return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
 }
 
 template <typename Op_t> struct FNeg_match {
   Op_t X;
 
   FNeg_match(const Op_t &Op) : X(Op) {}
   template <typename OpTy> bool match(OpTy *V) {
-    auto *FPMO = dyn_cast<FPMathOperator>(V);
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    if (!MContext.accept(V))
+      return false;
+    auto *FPMO = trait_dyn_cast<Trait, FPMathOperator>(V);
     if (!FPMO)
       return false;
 
-    if (FPMO->getOpcode() == Instruction::FNeg)
-      return X.match(FPMO->getOperand(0));
+    auto OPC = trait_cast<Trait, const Operator>(V)->getOpcode();
+
+    if (OPC == Instruction::FNeg)
+      return X.match(FPMO->getOperand(0), MContext);
 
-    if (FPMO->getOpcode() == Instruction::FSub) {
+    if (OPC == Instruction::FSub) {
       if (FPMO->hasNoSignedZeros()) {
         // With 'nsz', any zero goes.
-        if (!cstfp_pred_ty<is_any_zero_fp>().match(FPMO->getOperand(0)))
+        if (!try_match(FPMO->getOperand(0), cstfp_pred_ty<is_any_zero_fp>(),
+                       MContext))
           return false;
       } else {
         // Without 'nsz', we need fsub -0.0, X exactly.
-        if (!cstfp_pred_ty<is_neg_zero_fp>().match(FPMO->getOperand(0)))
+        if (!try_match(FPMO->getOperand(0), cstfp_pred_ty<is_neg_zero_fp>(),
+                       MContext))
           return false;
       }
 
-      return X.match(FPMO->getOperand(1));
+      return X.match(FPMO->getOperand(1), MContext);
     }
 
     return false;
   }
 };
 
 /// Match 'fneg X' as 'fsub -0.0, X'.
 template <typename OpTy> inline FNeg_match<OpTy> m_FNeg(const OpTy &X) {

 struct OverflowingBinaryOp_match {
   LHS_t L;
   RHS_t R;
 
   OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
       : L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) {
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    if (!MContext.accept(V))
+      return false;
+    if (auto *Op = trait_dyn_cast<Trait, OverflowingBinaryOperator>(V)) {
       if (Op->getOpcode() != Opcode)
         return false;
       if ((WrapFlags & OverflowingBinaryOperator::NoUnsignedWrap) &&
           !Op->hasNoUnsignedWrap())
         return false;
       if ((WrapFlags & OverflowingBinaryOperator::NoSignedWrap) &&
           !Op->hasNoSignedWrap())
         return false;
-      return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1));
+      return L.match(Op->getOperand(0), MContext) &&
+             R.match(Op->getOperand(1), MContext);
     }
     return false;
   }
 };
 
 template <typename LHS, typename RHS>
 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
                                  OverflowingBinaryOperator::NoSignedWrap>

 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);
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+
+  template <typename OpTy, typename Trait = DefaultTrait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    return BinaryOp_match<LHS_t, RHS_t, 0,
+                          Commutable>::template match<OpTy, Trait>(Opcode, V,
+                                                                   MContext);
   }
 };
 
 /// 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);
 }
 
 //===----------------------------------------------------------------------===//
 // Class that matches a group of binary opcodes.
 //
 template <typename LHS_t, typename RHS_t, typename Predicate>
 struct BinOpPred_match : Predicate {
   LHS_t L;
   RHS_t R;
 
   BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (auto *I = dyn_cast<Instruction>(V))
-      return this->isOpType(I->getOpcode()) && L.match(I->getOperand(0)) &&
-             R.match(I->getOperand(1));
-    if (auto *CE = dyn_cast<ConstantExpr>(V))
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    if (!MContext.accept(V))
+      return false;
+    if (auto *I = trait_dyn_cast<Trait, Instruction>(V))
+      return this->isOpType(I->getOpcode()) &&
+             L.match(I->getOperand(0), MContext) &&
+             R.match(I->getOperand(1), MContext);
+    if (auto *CE = trait_dyn_cast<Trait, ConstantExpr>(V))
       return this->isOpType(CE->getOpcode()) && L.match(CE->getOperand(0)) &&
              R.match(CE->getOperand(1));
     return false;
   }
 };
 
 struct is_shift_op {
   bool isOpType(unsigned Opcode) { return Instruction::isShift(Opcode); }

 // Class that matches exact binary ops.
 //
 template <typename SubPattern_t> struct Exact_match {
   SubPattern_t SubPattern;
 
   Exact_match(const SubPattern_t &SP) : SubPattern(SP) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (auto *PEO = dyn_cast<PossiblyExactOperator>(V))
-      return PEO->isExact() && SubPattern.match(V);
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    if (!MContext.accept(V))
+      return false;
+    if (auto *PEO = trait_dyn_cast<Trait, PossiblyExactOperator>(V))
+      return PEO->isExact() && SubPattern.match(V, MContext);
     return false;
   }
 };
 
 template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) {
   return SubPattern;
 }
 
struct CmpClass_match {
   RHS_t R;
 
   // The evaluation order is always stable, regardless of Commutability.
   // The LHS is always matched first.
   CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
       : Predicate(Pred), L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (auto *I = dyn_cast<Class>(V)) {
-      if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    if (!MContext.accept(V))
+      return false;
+    if (auto *I = trait_dyn_cast<Trait, Class>(V)) {
+      MatcherContext<Trait> LRContext(MContext);
+      if (L.match(I->getOperand(0), LRContext) &&
+          R.match(I->getOperand(1), LRContext)) {
+        MContext = LRContext;
         Predicate = I->getPredicate();
         return true;
-      } else if (Commutable && L.match(I->getOperand(1)) &&
-                 R.match(I->getOperand(0))) {
+      }
+
+      if (!Commutable)
+        return false;
+
+      if (L.match(I->getOperand(1), MContext) &&
+          R.match(I->getOperand(0), MContext)) {
         Predicate = I->getSwappedPredicate();
         return true;
       }
     }
     return false;
   }
 };
 

 
 /// Matches instructions with Opcode and three operands.
 template <typename T0, unsigned Opcode> struct OneOps_match {
   T0 Op1;
 
   OneOps_match(const T0 &Op1) : Op1(Op1) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (V->getValueID() == Value::InstructionVal + Opcode) {
-      auto *I = cast<Instruction>(V);
-      return Op1.match(I->getOperand(0));
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    if (!MContext.accept(V))
+      return false;
+    auto *I = trait_dyn_cast<Trait, Instruction>(V);
+    if (I && I->getOpcode() == Opcode) {
+      return Op1.match(I->getOperand(0), MContext);
     }
     return false;
   }
 };
 
 /// Matches instructions with Opcode and three operands.
 template <typename T0, typename T1, unsigned Opcode> struct TwoOps_match {
   T0 Op1;
   T1 Op2;
 
   TwoOps_match(const T0 &Op1, const T1 &Op2) : Op1(Op1), Op2(Op2) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (V->getValueID() == Value::InstructionVal + Opcode) {
-      auto *I = cast<Instruction>(V);
-      return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1));
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    if (!MContext.accept(V))
+      return false;
+    auto *I = trait_dyn_cast<Trait, Instruction>(V);
+    if (I && I->getOpcode() == Opcode) {
+      return Op1.match(I->getOperand(0), MContext) &&
+             Op2.match(I->getOperand(1), MContext);
     }
     return false;
   }
 };
 
 /// Matches instructions with Opcode and three operands.
 template <typename T0, typename T1, typename T2, unsigned Opcode>
 struct ThreeOps_match {
   T0 Op1;
   T1 Op2;
   T2 Op3;
 
   ThreeOps_match(const T0 &Op1, const T1 &Op2, const T2 &Op3)
       : Op1(Op1), Op2(Op2), Op3(Op3) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (V->getValueID() == Value::InstructionVal + Opcode) {
-      auto *I = cast<Instruction>(V);
-      return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
-             Op3.match(I->getOperand(2));
-    }
-    return false;
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    if (!MContext.accept(V))
+      return false;
+    auto *I = trait_dyn_cast<Trait, Instruction>(V);
+    if (!I || I->getOpcode() != Opcode)
+      return false;
+    return Op1.match(I->getOperand(0), MContext) &&
+           Op2.match(I->getOperand(1), MContext) &&
+           Op3.match(I->getOperand(2), MContext);
   }
 };
 
 /// Matches SelectInst.
 template <typename Cond, typename LHS, typename RHS>
 inline ThreeOps_match<Cond, LHS, RHS, Instruction::Select>
 m_Select(const Cond &C, const LHS &L, const RHS &R) {
   return ThreeOps_match<Cond, LHS, RHS, Instruction::Select>(C, L, R);
template <typename T0, typename T1, typename T2> struct Shuffle_match {
   T0 Op1;
   T1 Op2;
   T2 Mask;
 
   Shuffle_match(const T0 &Op1, const T1 &Op2, const T2 &Mask)
       : Op1(Op1), Op2(Op2), Mask(Mask) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (auto *I = dyn_cast<ShuffleVectorInst>(V)) {
-      return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    if (!MContext.accept(V))
+      return false;
+    if (auto *I = trait_dyn_cast<Trait, ShuffleVectorInst>(V)) {
+      return Op1.match(I->getOperand(0), MContext) &&
+             Op2.match(I->getOperand(1), MContext) &&
              Mask.match(I->getShuffleMask());
     }
     return false;
   }
 };
 
 struct m_Mask {
   ArrayRef<int> &MaskRef;

 //
 
 template <typename Op_t, unsigned Opcode> struct CastClass_match {
   Op_t Op;
 
   CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (auto *O = dyn_cast<Operator>(V))
-      return O->getOpcode() == Opcode && Op.match(O->getOperand(0));
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &Matcher) {
+    if (!Matcher.accept(V))
+      return false;
+    if (auto O = trait_dyn_cast<Trait, Operator>(V))
+      return O->getOpcode() == Opcode && Op.match(O->getOperand(0), Matcher);
     return false;
   }
 };
 
 /// Matches BitCast.
 template <typename OpTy>
 inline CastClass_match<OpTy, Instruction::BitCast> m_BitCast(const OpTy &Op) {
   return CastClass_match<OpTy, Instruction::BitCast>(Op);

 //
 
 struct br_match {
   BasicBlock *&Succ;
 
   br_match(BasicBlock *&Succ) : Succ(Succ) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (auto *BI = dyn_cast<BranchInst>(V))
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    if (!MContext.accept(V))
+      return false;
+    if (auto *BI = trait_dyn_cast<Trait, BranchInst>(V))
       if (BI->isUnconditional()) {
         Succ = BI->getSuccessor(0);
         return true;
       }
     return false;
   }
 };
 
 inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); }
 
 template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
 struct brc_match {
   Cond_t Cond;
   TrueBlock_t T;
   FalseBlock_t F;
 
   brc_match(const Cond_t &C, const TrueBlock_t &t, const FalseBlock_t &f)
       : Cond(C), T(t), F(f) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (auto *BI = dyn_cast<BranchInst>(V))
-      if (BI->isConditional() && Cond.match(BI->getCondition()))
-        return T.match(BI->getSuccessor(0)) && F.match(BI->getSuccessor(1));
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    if (auto *BI = trait_dyn_cast<Trait, BranchInst>(V))
+      if (BI->isConditional() && Cond.match(BI->getCondition(), MContext)) {
+        return T.match(BI->getSuccessor(0), MContext) &&
+               F.match(BI->getSuccessor(1), MContext);
+      }
     return false;
   }
 };
 
 template <typename Cond_t>
 inline brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>
 m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
   return brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>(
struct MaxMin_match {
   LHS_t L;
   RHS_t R;
 
   // The evaluation order is always stable, regardless of Commutability.
   // The LHS is always matched first.
   MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (auto *II = dyn_cast<IntrinsicInst>(V)) {
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+  template <typename OpTy, typename Trait = DefaultTrait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    if (!MContext.accept(V))
+      return false;
+    if (auto *II = trait_dyn_cast<Trait, IntrinsicInst>(V)) {
       Intrinsic::ID IID = II->getIntrinsicID();
       if ((IID == Intrinsic::smax && Pred_t::match(ICmpInst::ICMP_SGT)) ||
           (IID == Intrinsic::smin && Pred_t::match(ICmpInst::ICMP_SLT)) ||
           (IID == Intrinsic::umax && Pred_t::match(ICmpInst::ICMP_UGT)) ||
           (IID == Intrinsic::umin && Pred_t::match(ICmpInst::ICMP_ULT))) {
         Value *LHS = II->getOperand(0), *RHS = II->getOperand(1);
-        return (L.match(LHS) && R.match(RHS)) ||
-               (Commutable && L.match(RHS) && R.match(LHS));
+        MatcherContext<Trait> LRContext(MContext);
+        if (L.match(LHS, LRContext) && R.match(RHS, LRContext)) {
+          MContext = LRContext;
+          return true;
+        }
+        return Commutable && L.match(RHS, MContext) && R.match(LHS, MContext);
       }
     }
     // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
-    auto *SI = dyn_cast<SelectInst>(V);
-    if (!SI)
+    auto *SI = trait_dyn_cast<Trait, SelectInst>(V);
+    if (!SI || !MContext.accept(SI))
       return false;
-    auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
-    if (!Cmp)
+    auto *Cmp = trait_dyn_cast<Trait, CmpInst_t>(SI->getCondition());
+    if (!Cmp || !MContext.accept(Cmp))
       return false;
     // At this point we have a select conditioned on a comparison.  Check that
     // it is the values returned by the select that are being compared.
     auto *TrueVal = SI->getTrueValue();
     auto *FalseVal = SI->getFalseValue();
     auto *LHS = Cmp->getOperand(0);
     auto *RHS = Cmp->getOperand(1);
     if ((TrueVal != LHS || FalseVal != RHS) &&
         (TrueVal != RHS || FalseVal != LHS))
       return false;
     typename CmpInst_t::Predicate Pred =
         LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
     // Does "(x pred y) ? x : y" represent the desired max/min operation?
     if (!Pred_t::match(Pred))
       return false;
+
     // It does!  Bind the operands.
-    return (L.match(LHS) && R.match(RHS)) ||
-           (Commutable && L.match(RHS) && R.match(LHS));
+    // TODO factor out commutative matching!
+    return commutable_match(Commutable, L, R, LHS, RHS, MContext);
   }
 };
 
 /// Helper class for identifying signed max predicates.
 struct smax_pred_ty {
   static bool match(ICmpInst::Predicate Pred) {
     return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
   }
match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>,
                      MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>>>
 m_MaxOrMin(const LHS &L, const RHS &R) {
   return m_CombineOr(m_CombineOr(m_SMax(L, R), m_SMin(L, R)),
                      m_CombineOr(m_UMax(L, R), m_UMin(L, R)));
 }
 
 /// Match an 'ordered' floating point maximum function.
 /// Floating point has one special value 'NaN'. Therefore, there is no total
-/// order. However, if we can ignore the 'NaN' value (for example, because of a
-/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
-/// semantics. In the presence of 'NaN' we have to preserve the original
-/// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate.
+/// order. However, if we can ignore the 'NaN' value (for example, because of
+/// a 'no-nans-float-math' flag) a combination of a fcmp and select has
+/// 'maximum' semantics. In the presence of 'NaN' we have to preserve the
+/// original select(fcmp(ogt/ge, L, R), L, R) semantics matched by this
+/// predicate.
 ///
 ///                         max(L, R)  iff L and R are not NaN
 ///  m_OrdFMax(L, R) =      R          iff L or R are NaN
 template <typename LHS, typename RHS>
 inline MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty> m_OrdFMax(const LHS &L,
                                                                  const RHS &R) {
   return MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty>(L, R);
 }
 
 /// Match an 'ordered' floating point minimum function.
 /// Floating point has one special value 'NaN'. Therefore, there is no total
-/// order. However, if we can ignore the 'NaN' value (for example, because of a
-/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
-/// semantics. In the presence of 'NaN' we have to preserve the original
-/// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate.
+/// order. However, if we can ignore the 'NaN' value (for example, because of
+/// a 'no-nans-float-math' flag) a combination of a fcmp and select has
+/// 'minimum' semantics. In the presence of 'NaN' we have to preserve the
+/// original select(fcmp(olt/le, L, R), L, R) semantics matched by this
+/// predicate.
 ///
 ///                         min(L, R)  iff L and R are not NaN
 ///  m_OrdFMin(L, R) =      R          iff L or R are NaN
 template <typename LHS, typename RHS>
 inline MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty> m_OrdFMin(const LHS &L,
                                                                  const RHS &R) {
   return MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty>(L, R);
 }
 
 /// Match an 'unordered' floating point maximum function.
 /// Floating point has one special value 'NaN'. Therefore, there is no total
-/// order. However, if we can ignore the 'NaN' value (for example, because of a
-/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
-/// semantics. In the presence of 'NaN' we have to preserve the original
-/// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate.
+/// order. However, if we can ignore the 'NaN' value (for example, because of
+/// a 'no-nans-float-math' flag) a combination of a fcmp and select has
+/// 'maximum' semantics. In the presence of 'NaN' we have to preserve the
+/// original select(fcmp(ugt/ge, L, R), L, R) semantics matched by this
+/// predicate.
 ///
 ///                         max(L, R)  iff L and R are not NaN
 ///  m_UnordFMax(L, R) =    L          iff L or R are NaN
 template <typename LHS, typename RHS>
 inline MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>
 m_UnordFMax(const LHS &L, const RHS &R) {
   return MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>(L, R);
 }
 
 /// Match an 'unordered' floating point minimum function.
 /// Floating point has one special value 'NaN'. Therefore, there is no total
-/// order. However, if we can ignore the 'NaN' value (for example, because of a
-/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
-/// semantics. In the presence of 'NaN' we have to preserve the original
-/// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate.
+/// order. However, if we can ignore the 'NaN' value (for example, because of
+/// a 'no-nans-float-math' flag) a combination of a fcmp and select has
+/// 'minimum' semantics. In the presence of 'NaN' we have to preserve the
+/// original select(fcmp(ult/le, L, R), L, R) semantics matched by this
+/// predicate.
 ///
 ///                          min(L, R)  iff L and R are not NaN
 ///  m_UnordFMin(L, R) =     L          iff L or R are NaN
 template <typename LHS, typename RHS>
 inline MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>
 m_UnordFMin(const LHS &L, const RHS &R) {
   return MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>(L, R);
 }
 
 //===----------------------------------------------------------------------===//
 // Matchers for overflow check patterns: e.g. (a + b) u< a, (a ^ -1) <u b
 // Note that S might be matched to other instructions than AddInst.
 //
 
 template <typename LHS_t, typename RHS_t, typename Sum_t>
 struct UAddWithOverflow_match {
   LHS_t L;
   RHS_t R;
   Sum_t S;
 
   UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S)
       : L(L), R(R), S(S) {}
 
   template <typename OpTy> bool match(OpTy *V) {
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
     Value *ICmpLHS, *ICmpRHS;
     ICmpInst::Predicate Pred;
-    if (!m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)).match(V))
+    if (!try_match(V, m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)),
+                   MContext))
       return false;
 
     Value *AddLHS, *AddRHS;
     auto AddExpr = m_Add(m_Value(AddLHS), m_Value(AddRHS));
 
     // (a + b) u< a, (a + b) u< b
-    if (Pred == ICmpInst::ICMP_ULT)
-      if (AddExpr.match(ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS))
-        return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
+    if (Pred == ICmpInst::ICMP_ULT) {
+      if (try_match(ICmpLHS, AddExpr, MContext) &&
+          (ICmpRHS == AddLHS || ICmpRHS == AddRHS)) {
+        return L.match(AddLHS, MContext) && R.match(AddRHS, MContext) &&
+               S.match(ICmpLHS, MContext);
+      }
+    }
 
     // a >u (a + b), b >u (a + b)
-    if (Pred == ICmpInst::ICMP_UGT)
-      if (AddExpr.match(ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS))
-        return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
+    if (Pred == ICmpInst::ICMP_UGT) {
+      if (try_match(ICmpRHS, AddExpr, MContext) &&
+          (ICmpLHS == AddLHS || ICmpLHS == AddRHS)) {
+        return L.match(AddLHS, MContext) && R.match(AddRHS, MContext) &&
+               S.match(ICmpRHS, MContext);
+      }
+    }
 
     Value *Op1;
     auto XorExpr = m_OneUse(m_Xor(m_Value(Op1), m_AllOnes()));
     // (a ^ -1) <u b
     if (Pred == ICmpInst::ICMP_ULT) {
-      if (XorExpr.match(ICmpLHS))
-        return L.match(Op1) && R.match(ICmpRHS) && S.match(ICmpLHS);
+      if (try_match(ICmpLHS, XorExpr, MContext)) {
+        return L.match(Op1) && R.match(ICmpRHS, MContext) &&
+               S.match(ICmpLHS, MContext);
+      }
     }
     //  b > u (a ^ -1)
     if (Pred == ICmpInst::ICMP_UGT) {
-      if (XorExpr.match(ICmpRHS))
-        return L.match(Op1) && R.match(ICmpLHS) && S.match(ICmpRHS);
+      if (try_match(ICmpRHS, XorExpr, MContext)) {
+        return L.match(Op1, MContext) && R.match(ICmpLHS, MContext) &&
+               S.match(ICmpRHS, MContext);
+      }
     }
 
     // Match special-case for increment-by-1.
     if (Pred == ICmpInst::ICMP_EQ) {
       // (a + 1) == 0
       // (1 + a) == 0
-      if (AddExpr.match(ICmpLHS) && m_ZeroInt().match(ICmpRHS) &&
-          (m_One().match(AddLHS) || m_One().match(AddRHS)))
-        return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
+      MatcherContext<Trait> CopyCtx(MContext);
+      if (AddExpr.match(ICmpLHS, CopyCtx) &&
+          m_ZeroInt().match(ICmpRHS, CopyCtx)) {
+        if (try_match(AddLHS, m_One(), CopyCtx) ||
+            try_match(AddRHS, m_One(), CopyCtx)) {
+          MContext = CopyCtx;
+          return L.match(AddLHS, MContext) && R.match(AddRHS, MContext) &&
+                 S.match(ICmpLHS, MContext);
+        }
+      }
       // 0 == (a + 1)
       // 0 == (1 + a)
-      if (m_ZeroInt().match(ICmpLHS) && AddExpr.match(ICmpRHS) &&
-          (m_One().match(AddLHS) || m_One().match(AddRHS)))
-        return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
+      if (m_ZeroInt().match(ICmpLHS, MContext) &&
+          AddExpr.match(ICmpRHS, MContext) &&
+          (try_match(AddLHS, m_One(), MContext) ||
+           m_One().match(AddRHS, MContext)))
+        return L.match(AddLHS, MContext) && R.match(AddRHS, MContext) &&
+               S.match(ICmpRHS, MContext);
     }
 
     return false;
   }
 };
 
 /// Match an icmp instruction checking for unsigned overflow on addition.
 ///
-/// S is matched to the addition whose result is being checked for overflow, and
-/// L and R are matched to the LHS and RHS of S.
+/// S is matched to the addition whose result is being checked for overflow,
+/// and L and R are matched to the LHS and RHS of S.
 template <typename LHS_t, typename RHS_t, typename Sum_t>
 UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>
 m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S) {
   return UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>(L, R, S);
 }
 
 template <typename Opnd_t> struct Argument_match {
   unsigned OpI;
   Opnd_t Val;
 
   Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) {}
 
   template <typename OpTy> bool match(OpTy *V) {
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
     // FIXME: Should likely be switched to use `CallBase`.
-    if (const auto *CI = dyn_cast<CallInst>(V))
-      return Val.match(CI->getArgOperand(OpI));
+    if (const auto *CI = trait_dyn_cast<Trait, CallInst>(V))
+      return Val.match(CI->getArgOperand(OpI), MContext);
     return false;
   }
 };
 
 /// Match an argument.
 template <unsigned OpI, typename Opnd_t>
 inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) {
   return Argument_match<Opnd_t>(OpI, Op);
 }
 
 /// Intrinsic matchers.
 struct IntrinsicID_match {
   unsigned ID;
 
   IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (const auto *CI = dyn_cast<CallInst>(V))
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    if (const auto *CI = trait_dyn_cast<Trait, CallInst>(V))
       if (const auto *F = CI->getCalledFunction())
         return F->getIntrinsicID() == ID;
     return false;
   }
 };
 
 /// Intrinsic matches are combinations of ID matchers, and argument
 /// matchers. Higher arity matcher are defined recursively in terms of and-ing
m_Not(const ValTy &V) {
   return m_c_Xor(V, m_AllOnes());
 }
 
 template <typename ValTy> struct NotForbidUndef_match {
   ValTy Val;
   NotForbidUndef_match(const ValTy &V) : Val(V) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    // We do not use m_c_Xor because that could match an arbitrary APInt that is
-    // not -1 as C and then fail to match the other operand if it is -1.
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &Matcher) {
+    // We do not use m_c_Xor because that could match an arbitrary APInt that
+    // is not -1 as C and then fail to match the other operand if it is -1.
     // This code should still work even when both operands are constants.
     Value *X;
     const APInt *C;
-    if (m_Xor(m_Value(X), m_APIntForbidUndef(C)).match(V) && C->isAllOnes())
-      return Val.match(X);
-    if (m_Xor(m_APIntForbidUndef(C), m_Value(X)).match(V) && C->isAllOnes())
-      return Val.match(X);
+    if (try_match(V, m_Xor(m_Value(X), m_APIntForbidUndef(C)), Matcher) &&
+        C->isAllOnes())
+      return Val.match(X, Matcher);
+    if (try_match(V, m_Xor(m_APIntForbidUndef(C), m_Value(X)), Matcher) &&
+        C->isAllOnes())
+      return Val.match(X, Matcher);
     return false;
   }
 };
 
 /// Matches a bitwise 'not' as 'xor V, -1' or 'xor -1, V'. For vectors, the
 /// constant value must be composed of only -1 scalar elements.
 template <typename ValTy>
 inline NotForbidUndef_match<ValTy> m_NotForbidUndef(const ValTy &V) {
m_c_FMul(const LHS &L, const RHS &R) {
   return BinaryOp_match<LHS, RHS, Instruction::FMul, true>(L, R);
 }
 
 template <typename Opnd_t> struct Signum_match {
   Opnd_t Val;
   Signum_match(const Opnd_t &V) : Val(V) {}
 
   template <typename OpTy> bool match(OpTy *V) {
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
     unsigned TypeSize = V->getType()->getScalarSizeInBits();
     if (TypeSize == 0)
       return false;
 
     unsigned ShiftWidth = TypeSize - 1;
     Value *OpL = nullptr, *OpR = nullptr;
 
     // This is the representation of signum we match:
     //
     //  signum(x) == (x >> 63) | (-x >>u 63)
     //
     // An i1 value is its own signum, so it's correct to match
     //
     //  signum(x) == (x >> 0)  | (-x >>u 0)
     //
     // for i1 values.
 
     auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth));
     auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth));
     auto Signum = m_Or(LHS, RHS);
 
-    return Signum.match(V) && OpL == OpR && Val.match(OpL);
+    return Signum.match(V, MContext) && OpL == OpR && Val.match(OpL, MContext);
   }
 };
 
 /// Matches a signum pattern.
 ///
 /// signum(x) =
 ///      x >  0  ->  1
 ///      x == 0  ->  0
 ///      x <  0  -> -1
 template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
   return Signum_match<Val_t>(V);
 }
 
 template <int Ind, typename Opnd_t> struct ExtractValue_match {
   Opnd_t Val;
   ExtractValue_match(const Opnd_t &V) : Val(V) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (auto *I = dyn_cast<ExtractValueInst>(V)) {
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &MContext) {
+    if (auto *I = trait_dyn_cast<Trait, ExtractValueInst>(V)) {
       // If Ind is -1, don't inspect indices
       if (Ind != -1 &&
           !(I->getNumIndices() == 1 && I->getIndices()[0] == (unsigned)Ind))
         return false;
-      return Val.match(I->getAggregateOperand());
+      return Val.match(I->getAggregateOperand(), MContext);
     }
     return false;
   }
 };
 
 /// Match a single index ExtractValue instruction.
 /// For example m_ExtractValue<1>(...)
 template <int Ind, typename Val_t>

 /// Matcher for a single index InsertValue instruction.
 template <int Ind, typename T0, typename T1> struct InsertValue_match {
   T0 Op0;
   T1 Op1;
 
   InsertValue_match(const T0 &Op0, const T1 &Op1) : Op0(Op0), Op1(Op1) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (auto *I = dyn_cast<InsertValueInst>(V)) {
-      return Op0.match(I->getOperand(0)) && Op1.match(I->getOperand(1)) &&
-             I->getNumIndices() == 1 && Ind == I->getIndices()[0];
+    MatcherContext<DefaultTrait> Matcher;
+    return match(V, Matcher);
+  }
+
+  template <typename OpTy, typename Trait>
+  bool match(OpTy *V, MatcherContext<Trait> &Matcher) {
+    if (auto *I = trait_dyn_cast<Trait, InsertValueInst>(V)) {
+      return I->getNumIndices() == 1 && Ind == I->getIndices()[0] &&
+             Op0.match(I->getOperand(0), Matcher) &&
+             Op1.match(I->getOperand(1), Matcher);
     }
     return false;
   }
 };
 
 /// Matches a single index InsertValue instruction.
 template <int Ind, typename Val_t, typename Elt_t>
 inline InsertValue_match<Ind, Val_t, Elt_t> m_InsertValue(const Val_t &Val,
                                                           const Elt_t &Elt) {
   return InsertValue_match<Ind, Val_t, Elt_t>(Val, Elt);
 }
 
-/// Matches patterns for `vscale`. This can either be a call to `llvm.vscale` or
-/// the constant expression
+/// Matches patterns for `vscale`. This can either be a call to `llvm.vscale`
+/// or the constant expression
 ///  `ptrtoint(gep <vscale x 1 x i8>, <vscale x 1 x i8>* null, i32 1>`
 /// under the right conditions determined by DataLayout.
 struct VScaleVal_match {
   const DataLayout &DL;
   VScaleVal_match(const DataLayout &DL) : DL(DL) {}
 
   template <typename ITy> bool match(ITy *V) {
+    MatcherContext<DefaultTrait> MContext;
+    return match(V, MContext);
+  }
+  template <typename ITy, typename Trait>
+  bool match(ITy *V, MatcherContext<Trait> &MContext) {
     if (m_Intrinsic<Intrinsic::vscale>().match(V))
       return true;
 
     Value *Ptr;
-    if (m_PtrToInt(m_Value(Ptr)).match(V)) {
-      if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
+    if (m_PtrToInt(m_Value(Ptr)).match(V, MContext)) {
+      if (auto *GEP = trait_dyn_cast<Trait, GEPOperator>(Ptr)) {
         auto *DerefTy = GEP->getSourceElementType();
         if (GEP->getNumIndices() == 1 && isa<ScalableVectorType>(DerefTy) &&
             m_Zero().match(GEP->getPointerOperand()) &&
             m_SpecificInt(1).match(GEP->idx_begin()->get()) &&
             DL.getTypeAllocSizeInBits(DerefTy).getKnownMinSize() == 8)
           return true;
       }
     }

 template <typename LHS, typename RHS, unsigned Opcode, bool Commutable = false>
 struct LogicalOp_match {
   LHS L;
   RHS R;
 
   LogicalOp_match(const LHS &L, const RHS &R) : L(L), R(R) {}
 
   template <typename T> bool match(T *V) {
-    auto *I = dyn_cast<Instruction>(V);
+    MatcherContext<DefaultTrait> Matcher;
+    return match<T, DefaultTrait>(V, Matcher);
+  }
+
+  template <typename T, typename Trait = DefaultTrait>
+  bool match(T *V, MatcherContext<Trait> &MContext) {
+    auto *I = trait_dyn_cast<Trait, Instruction>(V);
     if (!I || !I->getType()->isIntOrIntVectorTy(1))
       return false;
 
     if (I->getOpcode() == Opcode) {
       auto *Op0 = I->getOperand(0);
       auto *Op1 = I->getOperand(1);
-      return (L.match(Op0) && R.match(Op1)) ||
-             (Commutable && L.match(Op1) && R.match(Op0));
+      return commutable_match(Commutable, L, R, Op0, Op1, MContext);
     }
 
     if (auto *Select = dyn_cast<SelectInst>(I)) {
       auto *Cond = Select->getCondition();
       auto *TVal = Select->getTrueValue();
       auto *FVal = Select->getFalseValue();
       if (Opcode == Instruction::And) {
         auto *C = dyn_cast<Constant>(FVal);
         if (C && C->isNullValue())
-          return (L.match(Cond) && R.match(TVal)) ||
-                 (Commutable && L.match(TVal) && R.match(Cond));
+          return commutable_match(Commutable, L, R, Cond, TVal, MContext);
       } else {
         assert(Opcode == Instruction::Or);
         auto *C = dyn_cast<Constant>(TVal);
         if (C && C->isOneValue())
-          return (L.match(Cond) && R.match(FVal)) ||
-                 (Commutable && L.match(FVal) && R.match(Cond));
+          return commutable_match(Commutable, L, R, Cond, FVal, MContext);
       }
     }
 
     return false;
   }
 };
 
 /// Matches L && R either in the form of L & R or L ? R : false.

llvm/include/llvm/IR/Traits/EnabledTraits.def

+ENABLE_TRAIT(EmptyTrait)
+ENABLE_TRAIT(CFPTrait)
+ENABLE_TRAIT(VPTrait)
+#undef ENABLE_TRAIT

llvm/include/llvm/IR/Traits/SemanticTrait.h

+//===- llvm/IR/Trait/SemanticTrait.h - Basic trait definitions --*- C++ -*-===//
+//
+// 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 defines semantic traits.
+// Some intrinsics in LLVM can be described as being a regular operation (such
+// as an fadd) at their core with an additional semantic trait. We do this to
+// lift optimizations that are defined in terms of standard IR operations (eg
+// fadd, fmul) to these intrinsics. We keep the existing patterns and rewrite
+// machinery and transparently check the rewrite is consistent with the
+// semantical trait(s) that are attached to the operations.
+//
+// For example:
+//
+// @llvm.vp.fadd(<256 x double> %a, <256 x double> %b,
+//               <256 x i1> %m. i32 %avl)
+//
+//   This is a vector-predicated fadd instruction with a %mask and %evl
+//   parameter
+//   (https://llvm.org/docs/LangRef.html#vector-predication-intrinsics).
+//   However, at its core it is just an 'fadd'.
+//
+//   Consider the fma-fusion rewrite pattern (fadd (fmul x,y) z) --> (fma x, y,
+//   z). If the 'fadd' is actually an 'llvm.vp.fadd" and the 'fmul' is actually
+//   an 'llvm.vp.fmul', we can perform the rewrite using the %mask and %evl of
+//   the 'fadd' node.
+//
+//
+// @llvm.experimental.constrained.fadd(double %a, double %b,
+//                                     metadata <rounding mode> metadata,
+//                                     <exception behavior>)
+//
+//   This is an fadd with a possibly non-default rounding mode and exception
+//   behavior.
+//   (https://llvm.org/docs/LangRef.html#constrained-floating-point-intrinsics).
+//   In this case, the operation matches the semantics of a regular 'fadd'
+//   exactly, if the rounding mode is 'round.tonearest' and the exception
+//   behavior is 'fpexcept.ignore'.
+//   Re-considering the case of fma fusion, this time with two constrained fp
+//   intrinsics.  If the rounding mode is tonearest for both and neither of the
+//   'llvm.experimental.contrained.fmul' has 'fpexcept.strict',, we are good to
+//   apply the rewrite and emit a contrained fma with the exception flad of the
+//   'fadd'.
+//
+// There is also a proposal to add complex arithmetic intrinsics to LLVM. In
+// that case, the operation is semantically an 'fadd', if we consider the space
+// of complex floating-point numbers and their operations.
+//
+//===----------------------------------------------------------------------===//
+
+// Look for comments starting with "TODO(new trait)" to see what to implement to
+// establish a new instruction trait.
+
+#ifndef LLVM_IR_TRAIT_SEMANTICTRAIT_H
+#define LLVM_IR_TRAIT_SEMANTICTRAIT_H
+
+#include <llvm/IR/Instructions.h>
+#include <llvm/IR/IntrinsicInst.h>
+#include <llvm/IR/Operator.h>
+#include <llvm/IR/Value.h>
+
+namespace llvm {
+
+/// Type Casting {
+/// These cast operators allow you to side-step the first-class type hierarchy
+/// of LLVM (Value, Instruction, BinaryOperator, ..) into your custom type
+/// hierarchy.
+///
+/// trait_cast<Trait, Instruction>(V)
+///
+/// actually casts \p V to ExtInstruction<Trait>.
+template <typename Trait, typename ValueDerivedType> struct TraitCast {
+  using ExtType = ValueDerivedType;
+};
+
+// This has to happen after all traits are defined since we are referring to
+// members of template specialization for each Trait (The TraitCast::ExtType).
+#define CASTING_TEMPLATE(CASTFUNC, PREFIXMOD, REFMOD)                          \
+  template <typename Trait, typename ValueDerivedType>                         \
+  static auto trait_##CASTFUNC(PREFIXMOD Value REFMOD V)                       \
+      ->decltype(CASTFUNC<                                                     \
+                 typename TraitCast<Trait, ValueDerivedType>::ExtType>(V)) {   \
+    using TraitExtendedType =                                                  \
+        typename TraitCast<Trait, ValueDerivedType>::ExtType;                  \
+    return CASTFUNC<TraitExtendedType>(V);                                     \
+  }
+
+#define CONST_CAST_TEMPLATE(CASTFUNC, REFMOD)                                  \
+  CASTING_TEMPLATE(CASTFUNC, const, REFMOD)                                    \
+  CASTING_TEMPLATE(CASTFUNC, , REFMOD)
+
+// 'dyn_cast' (allow [const] Value*)
+CONST_CAST_TEMPLATE(dyn_cast, *)
+
+// 'cast' (allow [const] Value(*|&))
+CONST_CAST_TEMPLATE(cast, *)
+CONST_CAST_TEMPLATE(cast, &)
+
+// 'isa'
+CONST_CAST_TEMPLATE(isa, *)
+CONST_CAST_TEMPLATE(isa, &)
+/// } Type Casting
+
+// TODO
+// The trait builder is a specialized IRBuilder that emits trait-compatible
+// instructions.
+template <typename Trait> struct TraitBuilder {};
+
+// This is used in pattern matching to check that all instructions in the
+// pattern are trait-compatible.
+template <typename Trait> struct MatcherContext {
+  // Check whether \p Val is compatible with this context and merge its
+  // properties. \returns Whether \p Val is compatible with the current state of
+  // the context.
+  bool accept(const Value *Val) { return Val; }
+
+  // Like accept() but does not modify the context.
+  bool check(const Value *Val) const { return Val; }
+
+  // Whether to allow constant folding with the currently accepted operators and
+  // their operands.
+  bool allowConstantFolding() const { return true; }
+};
+
+/// Empty Trait {
+///
+/// This defined the empty trait without properties. Type casting stays in the
+/// standard llvm::Value type hierarchy.
+
+// Trait without any difference to standard IR
+struct EmptyTrait {
+  // This is to block reassociation for traits that do not support it.
+  static constexpr bool AllowReassociation = true;
+
+  // Whether \p V should be considered at all with this trait.
+  static bool consider(const Value *) { return true; }
+};
+
+using DefaultTrait = EmptyTrait;
+
+/// } Empty Trait
+
+} // end namespace llvm
+
+#endif // LLVM_IR_TRAIT_SEMANTICTRAIT_H

llvm/include/llvm/IR/Traits/Traits.h

+//===- llvm/IR/Trait/SemanticTrait.h - Basic trait definitions --*- C++ -*-===//
+//
+// 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 defines semantic traits.
+// Some intrinsics in LLVM can be described as being a regular operation (such
+// as an fadd) at their core with an additional semantic trait. We do this to
+// lift optimizations that are defined in terms of standard IR operations (eg
+// fadd, fmul) to these intrinsics. We keep the existing patterns and rewrite
+// machinery and transparently check the rewrite is consistent with the
+// semantical trait(s) that are attached to the operations.
+//
+// For example:
+//
+// @llvm.vp.fadd(<256 x double> %a, <256 x double> %b,
+//               <256 x i1> %m. i32 %avl)
+//
+//   This is a vector-predicated fadd instruction with a %mask and %evl
+//   parameter
+//   (https://llvm.org/docs/LangRef.html#vector-predication-intrinsics).
+//   However, at its core it is just an 'fadd'.
+//
+//   Consider the simplification (add (sub x,y), y) --> x. If the 'add' is
+//   actually an 'llvm.vp.add" and the 'sub' is really an 'llvm.vp.sub', we can
+//   do the simplification. the 'fadd' node.
+//
+//
+// @llvm.experimental.constrained.fadd(double %a, double %b,
+//                                     metadata <rounding mode> metadata,
+//                                     <exception behavior>)
+//
+//   This is an fadd with a possibly non-default rounding mode and exception
+//   behavior.
+//   (https://llvm.org/docs/LangRef.html#constrained-floating-point-intrinsics).
+//   The constrained fp intrinsic has exactly the semantics of a regular 'fadd',
+//   if the rounding mode is 'round.tonearest' and the exception behavior is
+//   'fpexcept.ignore'.
+//   We can use all simplifying rewrites for regular fp arithmetic also for
+//   constrained fp arithmetic where this applies.
+//
+// There is also a proposal to add complex arithmetic intrinsics to LLVM. In
+// that case, the operation is semantically an 'fadd', if we consider the space
+// of complex floating-point numbers and their operations.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/FloatingPointMode.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Operator.h"
+#include "llvm/IR/Traits/SemanticTrait.h"
+
+#ifndef LLVM_IR_TRAITS_TRAITS_H
+#define LLVM_IR_TRAITS_TRAITS_H
+
+namespace llvm {
+
+/// Base classes {
+// Shared functionality for extended instructions
+// These define all functions used in PatterMatch as 'virtual' to remind you to
+// implement them.
+
+// Make sure no member of the Ext..<Trait> hierarchy can be constructed.
+struct ExtBase {
+  ExtBase() = delete;
+  ~ExtBase() = delete;
+  ExtBase &operator=(const ExtBase &) = delete;
+  void *operator new(size_t s) = delete;
+};
+
+// Mirror generic functionality of llvm::Instruction.
+struct ExtInstructionBase : public ExtBase, public User {
+  BasicBlock *getParent() { return cast<Instruction>(this)->getParent(); }
+  const BasicBlock *getParent() const {
+    return cast<const Instruction>(this)->getParent();
+  }
+
+  void copyIRFlags(const Value *V, bool IncludeWrapFlags) {
+    cast<Instruction>(this)->copyIRFlags(V, IncludeWrapFlags);
+  }
+
+  FastMathFlags getFastMathFlags() const {
+    if (auto *FPM = dyn_cast<FPMathOperator>(this))
+      return FPM->getFastMathFlags();
+    return FastMathFlags();
+  }
+};
+
+/// } Base classes
+
+/// Intrinsic-Trait Template {
+// Generic instantiation for traits that want to masquerade their intrinsic as a
+// regular IR instruction.
+
+// Pretend to be a llvm::Operator.
+template <typename Trait> struct ExtOperator : public ExtBase, public User {
+  unsigned getOpcode() const {
+    // Use the intrinsic override.
+    if (const auto *Intrin = dyn_cast<typename Trait::Intrinsic>(this))
+      if (auto OpcOpt = Intrin->getFunctionalOpcode())
+        return *OpcOpt;
+
+    // Default Operator opcode.
+    return cast<const Operator>(this)->getOpcode();
+  }
+
+  bool hasNoSignedWrap() const {
+    if (const auto *OverflowingBOp = dyn_cast<OverflowingBinaryOperator>(this))
+      return OverflowingBOp->hasNoSignedWrap();
+    return false;
+  }
+
+  bool hasNoUnsignedWrap() const {
+    if (const auto *OverflowingBOp = dyn_cast<OverflowingBinaryOperator>(this))
+      return OverflowingBOp->hasNoUnsignedWrap();
+    return false;
+  }
+
+  // Every operator is also an extended operator.
+  static bool classof(const Value *V) { return isa<Operator>(V); }
+};
+
+// Pretend to be a llvm::Instruction.
+template <typename Trait>
+struct ExtInstruction final : public ExtInstructionBase {
+  unsigned getOpcode() const {
+    // Use the intrinsic override.
+    if (const auto *Intrin = dyn_cast<typename Trait::Intrinsic>(this))
+      if (auto OpcOpt = Intrin->getFunctionalOpcode())
+        return *OpcOpt;
+    // Default opcode.
+    return cast<const Instruction>(this)->getOpcode();
+  }
+
+  static bool classof(const Value *V) { return isa<Instruction>(V); }
+};
+
+// Pretend to be a (different) llvm::IntrinsicInst.
+template <typename Trait>
+struct ExtIntrinsic final : public ExtInstructionBase {
+  Intrinsic::ID getIntrinsicID() const {
+    // Use the intrinsic override.
+    if (const auto *TraitIntrin = dyn_cast<typename Trait::Intrinsic>(this))
+      return TraitIntrin->getFunctionalIntrinsic();
+    // Default intrinsic opcode.
+    return cast<IntrinsicInst>(this)->getIntrinsicID();
+  }
+
+  unsigned getOpcode() const {
+    // We are looking at this as an intrinsic -> do not hide this.
+    return cast<Instruction>(this)->getOpcode();
+  }
+
+  bool isCommutative() const {
+    // The underlying intrinsic may not specify whether it is commutative.
+    // Query our own interface to be sure this is done right.
+    // Use the intrinsic override.
+    if (const auto *TraitIntrin = dyn_cast<typename Trait::Intrinsic>(this))
+      return TraitIntrin->isFunctionalCommutative();
+    return cast<IntrinsicInst>(this)->isFunctionalCommutative();
+  }
+
+  static bool classof(const Value *V) { return IntrinsicInst::classof(V); }
+};
+
+template <typename Trait, typename RegularCmpInst, typename PredicateType,
+          unsigned OPC>
+struct ExtCmpBase : public ExtInstructionBase {
+  unsigned getOpcode() const { return OPC; }
+
+  FCmpInst::Predicate getPredicate() const {
+    // Use the intrinsic override.
+    if (const auto *Intrin = dyn_cast<typename Trait::Intrinsic>(this)) {
+      return Intrin->getPredicate();
+    }
+
+    // Default opcode.
+    return cast<const RegularCmpInst>(this)->getPredicate();
+  }
+};
+
+template <typename Trait, typename RegularCmpInst, unsigned OPC>
+static bool classofExtCmpBase(const Value *V) {
+  return isa<const RegularCmpInst>(V) ||
+         cast<typename Trait::Intrinsic>->getFunctionalOpcode() == OPC;
+}
+
+// Pretend to be a llvm::FCmpInst.
+template <typename Trait>
+struct ExtFCmpInst final
+    : public ExtCmpBase<Trait, FCmpInst, FCmpInst::Predicate,
+                        Instruction::FCmp> {
+  static bool classof(const Value *V) {
+    return classofExtCmpBase<Trait, FCmpInst, Instruction::FCmp>(V);
+  }
+};
+
+// Pretend to be a llvm::ICmpInst.
+template <typename Trait>
+struct ExtICmpInst final
+    : public ExtCmpBase<Trait, ICmpInst, ICmpInst::Predicate,
+                        Instruction::ICmp> {
+  static bool classof(const Value *V) {
+    return classofExtCmpBase<Trait, ICmpInst, Instruction::ICmp>(V);
+  }
+};
+
+// Pretend to be a BinaryOperator.
+template <typename Trait>
+struct ExtBinaryOperator final : public ExtOperator<Trait> {
+  using BinaryOps = Instruction::BinaryOps;
+
+  static bool classof(const Instruction *I) {
+    if (isa<BinaryOperator>(I))
+      return true;
+    const auto *Intrin = dyn_cast<typename Trait::Intrinsic>(I);
+    return Intrin && Intrin->isFunctionalBinaryOp();
+  }
+  static bool classof(const ConstantExpr *CE) {
+    return isa<BinaryOperator>(CE);
+  }
+  static bool classof(const Value *V) {
+    if (const auto *I = dyn_cast<Instruction>(V))
+      return classof(I);
+
+    if (const auto *CE = dyn_cast<ConstantExpr>(V))
+      return classof(CE);
+
+    return false;
+  }
+};
+
+// Pretend to be a UnaryOperator.
+template <typename Trait>
+struct ExtUnaryOperator final : public ExtOperator<Trait> {
+  using BinaryOps = Instruction::BinaryOps;
+
+  static bool classof(const Instruction *I) {
+    if (isa<UnaryOperator>(I))
+      return true;
+    const auto *Intrin = dyn_cast<typename Trait::Intrinsic>(I);
+    return Intrin && Intrin->isFunctionalUnaryOp();
+  }
+};
+
+// TODO Implement other extended types.
+
+/// Template-specialization for the Ext<Something> type hierarchy {
+//// Enable the ExtSOMETHING<Trait> for your trait
+#define INTRINSIC_TRAIT_SPECIALIZE(TRAIT, TYPE)                                \
+  template <> struct TraitCast<TRAIT, TYPE> {                                  \
+    using ExtType = Ext##TYPE<TRAIT>;                                          \
+  };                                                                           \
+  template <> struct TraitCast<TRAIT, const TYPE> {                            \
+    using ExtType = const Ext##TYPE<TRAIT>;                                    \
+  };
+
+/// } Trait Template Classes
+
+// Constraint fp trait.
+struct CFPTrait {
+  using Intrinsic = ConstrainedFPIntrinsic;
+  static constexpr bool AllowReassociation = false;
+
+  // Whether \p V should be considered at all with this trait.
+  // It is not possible to mix constrained and unconstrained ops.
+  // Only apply this trait with the constrained variant.
+  static bool consider(const Value *V) {
+    return isa<ConstrainedFPIntrinsic>(V);
+  }
+};
+INTRINSIC_TRAIT_SPECIALIZE(CFPTrait, Instruction)
+INTRINSIC_TRAIT_SPECIALIZE(CFPTrait, Operator)
+INTRINSIC_TRAIT_SPECIALIZE(CFPTrait, BinaryOperator)
+INTRINSIC_TRAIT_SPECIALIZE(CFPTrait, UnaryOperator)
+// Deflect queries for the Predicate to the ConstrainedFPCmpIntrinsic.
+template <> struct ExtFCmpInst<CFPTrait> : public ExtInstructionBase {
+  unsigned getOpcode() const { return Instruction::FCmp; }
+
+  FCmpInst::Predicate getPredicate() const {
+    return cast<ConstrainedFPCmpIntrinsic>(this)->getPredicate();
+  }
+
+  static bool classof(const Value *V) {
+    return isa<ConstrainedFPCmpIntrinsic>(V);
+  }
+};
+INTRINSIC_TRAIT_SPECIALIZE(CFPTrait, FCmpInst)
+
+// Accept all constrained fp intrinsics that are actually not constrained.
+template <> struct MatcherContext<CFPTrait> {
+  bool accept(const Value *Val) { return check(Val); }
+  bool check(const Value *Val) const {
+    if (!Val)
+      return false;
+    const auto *CFP = dyn_cast<ConstrainedFPIntrinsic>(Val);
+    if (!CFP)
+      return true;
+    auto RoundingOpt =
+        CFP->getRoundingMode().getValueOr(RoundingMode::NearestTiesToEven);
+    auto ExceptOpt =
+        CFP->getExceptionBehavior().getValueOr(fp::ExceptionBehavior::ebIgnore);
+    return (ExceptOpt == fp::ExceptionBehavior::ebIgnore) &&
+           (RoundingOpt == RoundingMode::NearestTiesToEven);
+  }
+};
+
+// Vector-predicated trait.
+struct VPTrait {
+  using Intrinsic = VPIntrinsic;
+  // TODO Enable re-association.
+  static constexpr bool AllowReassociation = false;
+  // VP intrinsic mix with regular IR instructions.
+  // TODO: Adapt this to work with other than arithmetic VP ops.
+  static bool consider(const Value *V) {
+    return V->getType()->isVectorTy() &&
+           V->getType()->getScalarType()->isIntegerTy();
+  }
+};
+INTRINSIC_TRAIT_SPECIALIZE(VPTrait, Instruction)
+INTRINSIC_TRAIT_SPECIALIZE(VPTrait, Operator)
+INTRINSIC_TRAIT_SPECIALIZE(VPTrait, BinaryOperator)
+INTRINSIC_TRAIT_SPECIALIZE(VPTrait, UnaryOperator)
+
+// Accept everything that passes as a VPIntrinsic.
+template <> struct MatcherContext<VPTrait> {
+  // TODO: pick up %mask and %evl here and use them to generate code again. We
+  // only remove instructions for the moment.
+  bool accept(const Value *Val) { return Val; }
+  bool check(const Value *Val) const { return Val; }
+};
+
+} // namespace llvm
+
+#undef INTRINSIC_TRAIT_SPECIALIZE
+
+#endif // LLVM_IR_TRAITS_TRAITS_H

llvm/lib/Analysis/CMakeLists.txt

add_llvm_component_library(LLVMAnalysis
   VFABIDemangling.cpp
   ${GeneratedMLSources}
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Analysis
 
   DEPENDS
   intrinsics_gen
+  enabled_traits
   ${MLDeps}
 
   LINK_LIBS
   ${MLLinkDeps}
 
   LINK_COMPONENTS
   BinaryFormat
   Core
   Object
   ProfileData
   Support
   )

llvm/lib/Analysis/InstructionSimplify.cpp

 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PatternMatch.h"
+#include "llvm/IR/Traits/Traits.h"
+#include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/KnownBits.h"
 #include <algorithm>
 using namespace llvm;
 using namespace llvm::PatternMatch;
 
 #define DEBUG_TYPE "instsimplify"
 
 enum { RecursionLimit = 3 };
 
 STATISTIC(NumExpand, "Number of expansions");
 STATISTIC(NumReassoc, "Number of reassociations");
 
 static Value *simplifyAndInst(Value *, Value *, const SimplifyQuery &,
                               unsigned);
 static Value *simplifyUnOp(unsigned, Value *, const SimplifyQuery &, unsigned);
 static Value *simplifyFPUnOp(unsigned, Value *, const FastMathFlags &,
                              const SimplifyQuery &, unsigned);
 static Value *simplifyBinOp(unsigned, Value *, Value *, const SimplifyQuery &,
                             unsigned);
+template <typename Trait>
+static Value *simplifyBinOp(unsigned, Value *, Value *, const SimplifyQuery &,
+                            MatcherContext<Trait> &, unsigned);
+template <typename Trait>
 static Value *simplifyBinOp(unsigned, Value *, Value *, const FastMathFlags &,
-                            const SimplifyQuery &, unsigned);
+                            const SimplifyQuery &, MatcherContext<Trait> &,
+                            unsigned);
 static Value *simplifyCmpInst(unsigned, Value *, Value *, const SimplifyQuery &,
                               unsigned);
 static Value *simplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
                                const SimplifyQuery &Q, unsigned MaxRecurse);
 static Value *simplifyOrInst(Value *, Value *, const SimplifyQuery &, unsigned);
 static Value *simplifyXorInst(Value *, Value *, const SimplifyQuery &,
                               unsigned);
 static Value *simplifyCastInst(unsigned, Value *, Type *, const SimplifyQuery &,
if (Value *V = expandBinOp(Opcode, L, R, OpcodeToExpand, Q, MaxRecurse))
     return V;
   if (Value *V = expandBinOp(Opcode, R, L, OpcodeToExpand, Q, MaxRecurse))
     return V;
   return nullptr;
 }
 
 /// Generic simplifications for associative binary operations.
 /// Returns the simpler value, or null if none was found.
-static Value *simplifyAssociativeBinOp(Instruction::BinaryOps Opcode,
-                                       Value *LHS, Value *RHS,
-                                       const SimplifyQuery &Q,
-                                       unsigned MaxRecurse) {
+template <typename Trait>
+static Value *
+simplifyAssociativeBinOp(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
+                         const SimplifyQuery &Q, MatcherContext<Trait> &Matcher,
+  // This trait blocks re-association.
+  // Eg. any trait that adds side-effects may clash with free reassociation
+  // (FIXME are 'fpexcept.strict', 'fast' fp ops a thing?)
+  // FIXME associativity may depend on a trait parameter of this specific
+  // instance.
+  if (!Trait::AllowReassociation)
+    return nullptr;
+
   assert(Instruction::isAssociative(Opcode) && "Not an associative operation!");
 
   // Recursion is always used, so bail out at once if we already hit the limit.
   if (!MaxRecurse--)
     return nullptr;
 
-  BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
-  BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
+  auto *Op0 = trait_dyn_cast<Trait, BinaryOperator>(LHS);
+  auto *Op1 = trait_dyn_cast<Trait, BinaryOperator>(RHS);
 
   // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely.
-  if (Op0 && Op0->getOpcode() == Opcode) {
+  MatcherContext<Trait> Op0Matcher(Matcher);
+  if (Op0Matcher.accept(Op0) && Op0->getOpcode() == Opcode) {
     Value *A = Op0->getOperand(0);
     Value *B = Op0->getOperand(1);
     Value *C = RHS;
 
     // Does "B op C" simplify?
-    if (Value *V = simplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
+    if (Value *V =
+            simplifyBinOp<Trait>(Opcode, B, C, Q, Op0Matcher, MaxRecurse)) {
       // It does!  Return "A op V" if it simplifies or is already available.
       // If V equals B then "A op V" is just the LHS.
-      if (V == B)
+      if (V == B) {
+        Matcher = Op0Matcher;
         return LHS;
+      }
       // Otherwise return "A op V" if it simplifies.
-      if (Value *W = simplifyBinOp(Opcode, A, V, Q, MaxRecurse)) {
+      if (Value *W = simplifyBinOp(Opcode, A, V, Q, Op0Matcher, MaxRecurse)) {
+        Matcher = Op0Matcher;
         ++NumReassoc;
         return W;
       }
     }
   }
 
   // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely.
-  if (Op1 && Op1->getOpcode() == Opcode) {
+  MatcherContext<Trait> Op1Matcher(Matcher);
+  if (Op1Matcher.accept(Op1) && Op1->getOpcode() == Opcode) {
     Value *A = LHS;
     Value *B = Op1->getOperand(0);
     Value *C = Op1->getOperand(1);
 
     // Does "A op B" simplify?
-    if (Value *V = simplifyBinOp(Opcode, A, B, Q, MaxRecurse)) {
+    if (Value *V = simplifyBinOp(Opcode, A, B, Q, Op1Matcher, MaxRecurse)) {
       // It does!  Return "V op C" if it simplifies or is already available.
       // If V equals B then "V op C" is just the RHS.
-      if (V == B)
+      if (V == B) {
+        Matcher = Op1Matcher;
         return RHS;
+      }
       // Otherwise return "V op C" if it simplifies.
-      if (Value *W = simplifyBinOp(Opcode, V, C, Q, MaxRecurse)) {
+      if (Value *W = simplifyBinOp(Opcode, V, C, Q, Op1Matcher, MaxRecurse)) {
+        Matcher = Op1Matcher;
         ++NumReassoc;
         return W;
       }
     }
   }
 
   // The remaining transforms require commutativity as well as associativity.
+  // FIXME commutativity may depend on a trait parameter of this specific
+  // instance. Eg, matrix multiplication is associative but not commutative.
   if (!Instruction::isCommutative(Opcode))
     return nullptr;
 
   // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely.
+  MatcherContext<Trait> CommOp0Matcher(Matcher);
   if (Op0 && Op0->getOpcode() == Opcode) {
     Value *A = Op0->getOperand(0);
     Value *B = Op0->getOperand(1);
     Value *C = RHS;
 
     // Does "C op A" simplify?
-    if (Value *V = simplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
+    if (Value *V = simplifyBinOp(Opcode, C, A, Q, CommOp0Matcher, MaxRecurse)) {
       // It does!  Return "V op B" if it simplifies or is already available.
       // If V equals A then "V op B" is just the LHS.
-      if (V == A)
+      if (V == A) {
+        Matcher = CommOp0Matcher;
         return LHS;
+      }
       // Otherwise return "V op B" if it simplifies.
-      if (Value *W = simplifyBinOp(Opcode, V, B, Q, MaxRecurse)) {
+      MatcherContext<Trait> VContext(Matcher);
+      if (Value *W = simplifyBinOp(Opcode, V, B, Q, VContext, MaxRecurse)) {
+        Matcher = VContext;
         ++NumReassoc;
         return W;
       }
     }
   }
 
   // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely.
   if (Op1 && Op1->getOpcode() == Opcode) {
if (Value *V = simplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
         return W;
       }
     }
   }
 
   return nullptr;
 }
 
+static Value *simplifyAssociativeBinOp(Instruction::BinaryOps Opcode,
+                                       Value *LHS, Value *RHS,
+                                       const SimplifyQuery &Q,
+                                       unsigned MaxRecurse) {
+  MatcherContext<DefaultTrait> Matcher;
+  return simplifyAssociativeBinOp(Opcode, LHS, RHS, Q, Matcher, MaxRecurse);
+}
+
 /// In the case of a binary operation with a select instruction as an operand,
 /// try to simplify the binop by seeing whether evaluating it on both branches
 /// of the select results in the same value. Returns the common value if so,
 /// otherwise returns null.
 static Value *threadBinOpOverSelect(Instruction::BinaryOps Opcode, Value *LHS,
                                     Value *RHS, const SimplifyQuery &Q,
                                     unsigned MaxRecurse) {
   // Recursion is always used, so bail out at once if we already hit the limit.
if (auto *CLHS = dyn_cast<Constant>(Op0)) {
     if (Instruction::isCommutative(Opcode))
       std::swap(Op0, Op1);
   }
   return nullptr;
 }
 
 /// Given operands for an Add, see if we can fold the result.
 /// If not, this returns null.
+template <typename Trait>
 static Value *simplifyAddInst(Value *Op0, Value *Op1, bool IsNSW, bool IsNUW,
-                              const SimplifyQuery &Q, unsigned MaxRecurse) {
+                              const SimplifyQuery &Q,
+                              MatcherContext<Trait> &Matcher,
+                              unsigned MaxRecurse) {
   if (Constant *C = foldOrCommuteConstant(Instruction::Add, Op0, Op1, Q))
     return C;
 
   // X + poison -> poison
   if (isa<PoisonValue>(Op1))
     return Op1;
 
   // X + undef -> undef
   if (Q.isUndefValue(Op1))
     return Op1;
 
   // X + 0 -> X
-  if (match(Op1, m_Zero()))
+  if (try_match(Op1, m_Zero(), Matcher))
     return Op0;
 
   // If two operands are negative, return 0.
   if (isKnownNegation(Op0, Op1))
     return Constant::getNullValue(Op0->getType());
 
   // X + (Y - X) -> Y
   // (Y - X) + X -> Y
   // Eg: X + -X -> 0
   Value *Y = nullptr;
-  if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) ||
-      match(Op0, m_Sub(m_Value(Y), m_Specific(Op1))))
+  if (try_match(Op1, m_Sub(m_Value(Y), m_Specific(Op0)), Matcher) ||
+      try_match(Op0, m_Sub(m_Value(Y), m_Specific(Op1)), Matcher))
     return Y;
 
   // X + ~X -> -1   since   ~X = -X-1
   Type *Ty = Op0->getType();
-  if (match(Op0, m_Not(m_Specific(Op1))) || match(Op1, m_Not(m_Specific(Op0))))
+  if (try_match(Op0, m_Not(m_Specific(Op1)), Matcher) ||
+      try_match(Op1, m_Not(m_Specific(Op0)), Matcher))
     return Constant::getAllOnesValue(Ty);
 
   // add nsw/nuw (xor Y, signmask), signmask --> Y
   // The no-wrapping add guarantees that the top bit will be set by the add.
   // Therefore, the xor must be clearing the already set sign bit of Y.
-  if ((IsNSW || IsNUW) && match(Op1, m_SignMask()) &&
-      match(Op0, m_Xor(m_Value(Y), m_SignMask())))
+  MatcherContext<Trait> CopyMatch(Matcher);
+  if ((IsNSW || IsNUW) && match(Op1, m_SignMask(), CopyMatch) &&
+      match(Op0, m_Xor(m_Value(Y), m_SignMask()), CopyMatch)) {
+    Matcher = CopyMatch;
     return Y;
+  }
 
   // add nuw %x, -1  ->  -1, because %x can only be 0.
-  if (IsNUW && match(Op1, m_AllOnes()))
+  if (IsNUW && try_match(Op1, m_AllOnes(), Matcher))
     return Op1; // Which is -1.
 
   /// i1 add -> xor.
   if (MaxRecurse && Op0->getType()->isIntOrIntVectorTy(1))
     if (Value *V = simplifyXorInst(Op0, Op1, Q, MaxRecurse - 1))
       return V;
 
   // Try some generic simplifications for associative operations.
   if (Value *V =
           simplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q, MaxRecurse))
     return V;
 
   // Threading Add over selects and phi nodes is pointless, so don't bother.
   // Threading over the select in "A + select(cond, B, C)" means evaluating
   // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
   // only if B and C are equal.  If B and C are equal then (since we assume
   // that operands have already been simplified) "select(cond, B, C)" should
   // have been simplified to the common value of B and C already.  Analysing
   // "A+B" and "A+C" thus gains nothing, but costs compile time.  Similarly
   // for threading over phi nodes.
 
   return nullptr;
 }
 
+template <typename Trait>
 Value *llvm::simplifyAddInst(Value *Op0, Value *Op1, bool IsNSW, bool IsNUW,
-                             const SimplifyQuery &Query) {
-  return ::simplifyAddInst(Op0, Op1, IsNSW, IsNUW, Query, RecursionLimit);
+                             const SimplifyQuery &Query,
+                             MatcherContext<Trait> &Matcher) {
+  return ::simplifyAddInst<Trait>(Op0, Op1, IsNSW, IsNUW, Query, Matcher,
+                                  RecursionLimit);
 }
 
 /// Compute the base pointer and cumulative constant offsets for V.
 ///
 /// This strips all constant offsets off of V, leaving it the base pointer, and
 /// accumulates the total constant offset applied in the returned constant.
 /// It returns zero if there are no constant offsets applied.
 ///
if (Q.IIQ.getMetadata(RHS_Instr, LLVMContext::MD_range) &&
       auto RHS_CR = getConstantRangeFromMetadata(
           *RHS_Instr->getMetadata(LLVMContext::MD_range));
       auto LHS_CR = getConstantRangeFromMetadata(
           *LHS_Instr->getMetadata(LLVMContext::MD_range));
 
       if (LHS_CR.icmp(Pred, RHS_CR))
         return ConstantInt::getTrue(RHS->getContext());
 
       if (LHS_CR.icmp(CmpInst::getInversePredicate(Pred), RHS_CR))
         return ConstantInt::getFalse(RHS->getContext());
     }
   }
 
   // Compare of cast, for example (zext X) != 0 -> X != 0
   if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) {
     Instruction *LI = cast<CastInst>(LHS);
     Value *SrcOp = LI->getOperand(0);
if (CmpInst *C = dyn_cast<CmpInst>(I))
     return ConstantFoldCompareInstOperands(C->getPredicate(), ConstOps[0],
                                            ConstOps[1], Q.DL, Q.TLI);
 
   if (LoadInst *LI = dyn_cast<LoadInst>(I))
     if (!LI->isVolatile())
       return ConstantFoldLoadFromConstPtr(ConstOps[0], LI->getType(), Q.DL);
 
   return ConstantFoldInstOperands(I, ConstOps, Q.DL, Q.TLI);
 }
 
 Value *llvm::simplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp,
                                     const SimplifyQuery &Q,
                                     bool AllowRefinement) {
   return ::simplifyWithOpReplaced(V, Op, RepOp, Q, AllowRefinement,
                                   RecursionLimit);
 }
 
if (isDefaultFPEnvironment(ExBehavior, Rounding)) {
         return propagateNaN(cast<Constant>(V));
     }
   }
   return nullptr;
 }
 
 /// Given operands for an FAdd, see if we can fold the result.  If not, this
 /// returns null.
+template <typename Trait>
 static Value *
 simplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
-                 const SimplifyQuery &Q, unsigned MaxRecurse,
+                 const SimplifyQuery &Q, MatcherContext<Trait> &Matcher,
+                 unsigned MaxRecurse,
                  fp::ExceptionBehavior ExBehavior = fp::ebIgnore,
                  RoundingMode Rounding = RoundingMode::NearestTiesToEven) {
   if (isDefaultFPEnvironment(ExBehavior, Rounding))
     if (Constant *C = foldOrCommuteConstant(Instruction::FAdd, Op0, Op1, Q))
       return C;
 
   if (Constant *C = simplifyFPOp({Op0, Op1}, FMF, Q, ExBehavior, Rounding))
     return C;
 
   // fadd X, -0 ==> X
   // With strict/constrained FP, we have these possible edge cases that do
   // not simplify to Op0:
   // fadd SNaN, -0.0 --> QNaN
   // fadd +0.0, -0.0 --> -0.0 (but only with round toward negative)
   if (canIgnoreSNaN(ExBehavior, FMF) &&
       (!canRoundingModeBe(Rounding, RoundingMode::TowardNegative) ||
        FMF.noSignedZeros()))
-    if (match(Op1, m_NegZeroFP()))
+    if (try_match(Op1, m_NegZeroFP(), Matcher))
       return Op0;
 
   // fadd X, 0 ==> X, when we know X is not -0
   if (canIgnoreSNaN(ExBehavior, FMF))
-    if (match(Op1, m_PosZeroFP()) &&
+    if (try_match(Op1, m_PosZeroFP(), Matcher) &&
         (FMF.noSignedZeros() || CannotBeNegativeZero(Op0, Q.TLI)))
       return Op0;
 
   if (!isDefaultFPEnvironment(ExBehavior, Rounding))
     return nullptr;
 
   // With nnan: -X + X --> 0.0 (and commuted variant)
   // We don't have to explicitly exclude infinities (ninf): INF + -INF == NaN.
   // Negative zeros are allowed because we always end up with positive zero:
   // X = -0.0: (-0.0 - (-0.0)) + (-0.0) == ( 0.0) + (-0.0) == 0.0
   // X = -0.0: ( 0.0 - (-0.0)) + (-0.0) == ( 0.0) + (-0.0) == 0.0
   // X =  0.0: (-0.0 - ( 0.0)) + ( 0.0) == (-0.0) + ( 0.0) == 0.0
   // X =  0.0: ( 0.0 - ( 0.0)) + ( 0.0) == ( 0.0) + ( 0.0) == 0.0
   if (FMF.noNaNs()) {
-    if (match(Op0, m_FSub(m_AnyZeroFP(), m_Specific(Op1))) ||
-        match(Op1, m_FSub(m_AnyZeroFP(), m_Specific(Op0))))
+    if (try_match(Op0, m_FSub(m_AnyZeroFP(), m_Specific(Op1)), Matcher) ||
+        try_match(Op1, m_FSub(m_AnyZeroFP(), m_Specific(Op0)), Matcher))
       return ConstantFP::getNullValue(Op0->getType());
 
-    if (match(Op0, m_FNeg(m_Specific(Op1))) ||
-        match(Op1, m_FNeg(m_Specific(Op0))))
+    if (try_match(Op0, m_FNeg(m_Specific(Op1)), Matcher) ||
+        try_match(Op1, m_FNeg(m_Specific(Op0)), Matcher))
       return ConstantFP::getNullValue(Op0->getType());
   }
 
   // (X - Y) + Y --> X
   // Y + (X - Y) --> X
   Value *X;
   if (FMF.noSignedZeros() && FMF.allowReassoc() &&
-      (match(Op0, m_FSub(m_Value(X), m_Specific(Op1))) ||
-       match(Op1, m_FSub(m_Value(X), m_Specific(Op0)))))
+      (try_match(Op0, m_FSub(m_Value(X), m_Specific(Op1)), Matcher) ||
+       try_match(Op1, m_FSub(m_Value(X), m_Specific(Op0)), Matcher)))
     return X;
 
   return nullptr;
 }
 
 /// Given operands for an FSub, see if we can fold the result.  If not, this
 /// returns null.
 static Value *
simplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF,
   if (isDefaultFPEnvironment(ExBehavior, Rounding))
     if (Constant *C = foldOrCommuteConstant(Instruction::FMul, Op0, Op1, Q))
       return C;
 
   // Now apply simplifications that do not require rounding.
   return simplifyFMAFMul(Op0, Op1, FMF, Q, MaxRecurse, ExBehavior, Rounding);
 }
 
+template <typename Trait>
 Value *llvm::simplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
                               const SimplifyQuery &Q,
+                              MatcherContext<Trait> &Matcher,
                               fp::ExceptionBehavior ExBehavior,
                               RoundingMode Rounding) {
-  return ::simplifyFAddInst(Op0, Op1, FMF, Q, RecursionLimit, ExBehavior,
-                            Rounding);
+  return ::simplifyFAddInst<Trait>(Op0, Op1, FMF, Q, Matcher, RecursionLimit,
+                                   ExBehavior, Rounding);
 }
 
 Value *llvm::simplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF,
                               const SimplifyQuery &Q,
                               fp::ExceptionBehavior ExBehavior,
                               RoundingMode Rounding) {
   return ::simplifyFSubInst(Op0, Op1, FMF, Q, RecursionLimit, ExBehavior,
                             Rounding);

 
 Value *llvm::simplifyUnOp(unsigned Opcode, Value *Op, FastMathFlags FMF,
                           const SimplifyQuery &Q) {
   return ::simplifyFPUnOp(Opcode, Op, FMF, Q, RecursionLimit);
 }
 
 /// Given operands for a BinaryOperator, see if we can fold the result.
 /// If not, this returns null.
-static Value *simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
-                            const SimplifyQuery &Q, unsigned MaxRecurse) {
+template <typename Trait>
+static Value *
+simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q,
+              MatcherContext<Trait> &Matcher, unsigned MaxRecurse) {
   switch (Opcode) {
   case Instruction::Add:
-    return simplifyAddInst(LHS, RHS, false, false, Q, MaxRecurse);
+    return simplifyAddInst<Trait>(LHS, RHS, false, false, Q, Matcher,
+                                  MaxRecurse);
   case Instruction::Sub:
     return simplifySubInst(LHS, RHS, false, false, Q, MaxRecurse);
   case Instruction::Mul:
     return simplifyMulInst(LHS, RHS, Q, MaxRecurse);
   case Instruction::SDiv:
     return simplifySDivInst(LHS, RHS, Q, MaxRecurse);
   case Instruction::UDiv:
     return simplifyUDivInst(LHS, RHS, Q, MaxRecurse);
case Instruction::AShr:
     return simplifyAShrInst(LHS, RHS, false, Q, MaxRecurse);
   case Instruction::And:
     return simplifyAndInst(LHS, RHS, Q, MaxRecurse);
   case Instruction::Or:
     return simplifyOrInst(LHS, RHS, Q, MaxRecurse);
   case Instruction::Xor:
     return simplifyXorInst(LHS, RHS, Q, MaxRecurse);
   case Instruction::FAdd:
-    return simplifyFAddInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
+    return simplifyFAddInst<Trait>(LHS, RHS, FastMathFlags(), Q, Matcher,
+                                   MaxRecurse);
   case Instruction::FSub:
     return simplifyFSubInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
   case Instruction::FMul:
     return simplifyFMulInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
   case Instruction::FDiv:
     return simplifyFDivInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
   case Instruction::FRem:
     return simplifyFRemInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
   default:
     llvm_unreachable("Unexpected opcode");
   }
 }
 
+static Value *simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
+                            const SimplifyQuery &Q, unsigned MaxRecurse) {
+  MatcherContext<DefaultTrait> Matcher;
+  return simplifyBinOp<>(Opcode, LHS, RHS, Q, Matcher, MaxRecurse);
+}
+
 /// Given operands for a BinaryOperator, see if we can fold the result.
 /// If not, this returns null.
 /// Try to use FastMathFlags when folding the result.
+template <typename Trait>
 static Value *simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
                             const FastMathFlags &FMF, const SimplifyQuery &Q,
+                            MatcherContext<Trait> &Matcher,
                             unsigned MaxRecurse) {
   switch (Opcode) {
   case Instruction::FAdd:
-    return simplifyFAddInst(LHS, RHS, FMF, Q, MaxRecurse);
+    return simplifyFAddInst<Trait>(LHS, RHS, FMF, Q, Matcher, MaxRecurse);
   case Instruction::FSub:
     return simplifyFSubInst(LHS, RHS, FMF, Q, MaxRecurse);
   case Instruction::FMul:
     return simplifyFMulInst(LHS, RHS, FMF, Q, MaxRecurse);
   case Instruction::FDiv:
     return simplifyFDivInst(LHS, RHS, FMF, Q, MaxRecurse);
   default:
-    return simplifyBinOp(Opcode, LHS, RHS, Q, MaxRecurse);
+    return simplifyBinOp<>(Opcode, LHS, RHS, Q, Matcher, MaxRecurse);
   }
 }
 
+template <typename Trait>
 Value *llvm::simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
-                           const SimplifyQuery &Q) {
-  return ::simplifyBinOp(Opcode, LHS, RHS, Q, RecursionLimit);
+                           const SimplifyQuery &Q,
+                           MatcherContext<Trait> &Matcher) {
+  return ::simplifyBinOp<>(Opcode, LHS, RHS, Q, Matcher, RecursionLimit);
 }
 
+template <typename Trait>
 Value *llvm::simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
-                           FastMathFlags FMF, const SimplifyQuery &Q) {
-  return ::simplifyBinOp(Opcode, LHS, RHS, FMF, Q, RecursionLimit);
+                           FastMathFlags FMF, const SimplifyQuery &Q,
+                           MatcherContext<Trait> &Matcher) {
+  return ::simplifyBinOp<>(Opcode, LHS, RHS, FMF, Q, Matcher, RecursionLimit);
 }
 
 /// Given operands for a CmpInst, see if we can fold the result.
 static Value *simplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
                               const SimplifyQuery &Q, unsigned MaxRecurse) {
   if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
     return simplifyICmpInst(Predicate, LHS, RHS, Q, MaxRecurse);
   return simplifyFCmpInst(Predicate, LHS, RHS, FastMathFlags(), Q, MaxRecurse);
static Value *simplifyLoadInst(LoadInst *LI, Value *PtrOp,
   if (PtrOpC)
     return ConstantFoldLoadFromConstPtr(PtrOpC, LI->getType(), Offset, Q.DL);
   return nullptr;
 }
 
 /// See if we can compute a simplified version of this instruction.
 /// If not, this returns null.
 
-static Value *simplifyInstructionWithOperands(Instruction *I,
-                                              ArrayRef<Value *> NewOps,
-                                              const SimplifyQuery &SQ,
-                                              OptimizationRemarkEmitter *ORE) {
+// FIXME: this will break if masquerading intrinsics do not pass muster.
+template <typename Trait>
+Value *llvm::simplifyInstructionWithOperandsAndTrait(
+    Instruction *I, ArrayRef<Value *> NewOps, const SimplifyQuery &SQ,
   const SimplifyQuery Q = SQ.CxtI ? SQ : SQ.getWithInstruction(I);
   Value *Result = nullptr;
 
-  switch (I->getOpcode()) {
+  // Allow Traits to bail for cases we do not want to implement.
+  if (!Trait::consider(I))
+    return nullptr;
+
+  // Create an initial context rooted at I.
+  MatcherContext<Trait> Matcher;
+  if (!Matcher.accept(I))
+    return nullptr;
+
+  // Cast into the Trait type hierarchy since I may have a different opcode
+  // there.
+  // Eg llvm.*.constrained.fadd(%x, %y, %fpround, %fpexcept) is an 'fadd'.
+  const auto *TraitInst = trait_cast<Trait, Instruction>(I);
+  switch (TraitInst->getOpcode()) {
   default:
     if (llvm::all_of(NewOps, [](Value *V) { return isa<Constant>(V); })) {
       SmallVector<Constant *, 8> NewConstOps(NewOps.size());
       transform(NewOps, NewConstOps.begin(),
                 [](Value *V) { return cast<Constant>(V); });
       Result = ConstantFoldInstOperands(I, NewConstOps, Q.DL, Q.TLI);
     }
     break;
   case Instruction::FNeg:
     Result = simplifyFNegInst(NewOps[0], I->getFastMathFlags(), Q);
     break;
   case Instruction::FAdd:
-    Result = simplifyFAddInst(NewOps[0], NewOps[1], I->getFastMathFlags(), Q);
+    Result = simplifyFAddInst<Trait>(NewOps[0], NewOps[1],
+                                     I->getFastMathFlags(), Q, Matcher);
     break;
   case Instruction::Add:
-    Result = simplifyAddInst(
-        NewOps[0], NewOps[1], Q.IIQ.hasNoSignedWrap(cast<BinaryOperator>(I)),
-        Q.IIQ.hasNoUnsignedWrap(cast<BinaryOperator>(I)), Q);
+    Result = simplifyAddInst<Trait>(
+        NewOps[0], NewOps[1],
+        Q.IIQ.hasNoSignedWrap(trait_cast<Trait, BinaryOperator>(I)),
+        Q.IIQ.hasNoUnsignedWrap(trait_cast<Trait, BinaryOperator>(I)), Q,
+        Matcher);
     break;
   case Instruction::FSub:
     Result = simplifyFSubInst(NewOps[0], NewOps[1], I->getFastMathFlags(), Q);
     break;
   case Instruction::Sub:
+    // TODO: Add Trait abstraction
     Result = simplifySubInst(
-        NewOps[0], NewOps[1], Q.IIQ.hasNoSignedWrap(cast<BinaryOperator>(I)),
-        Q.IIQ.hasNoUnsignedWrap(cast<BinaryOperator>(I)), Q);
+        NewOps[0], NewOps[1],
+        Q.IIQ.hasNoSignedWrap(trait_cast<Trait, BinaryOperator>(I)),
+        Q.IIQ.hasNoUnsignedWrap(trait_cast<Trait, BinaryOperator>(I)), Q);
     break;
   case Instruction::FMul:
     Result = simplifyFMulInst(NewOps[0], NewOps[1], I->getFastMathFlags(), Q);
     break;
   case Instruction::Mul:
     Result = simplifyMulInst(NewOps[0], NewOps[1], Q);
     break;
   case Instruction::SDiv:
Value *llvm::simplifyInstructionWithOperandsAndTrait(
   case Instruction::URem:
     Result = simplifyURemInst(NewOps[0], NewOps[1], Q);
     break;
   case Instruction::FRem:
     Result = simplifyFRemInst(NewOps[0], NewOps[1], I->getFastMathFlags(), Q);
     break;
   case Instruction::Shl:
     Result = simplifyShlInst(
-        NewOps[0], NewOps[1], Q.IIQ.hasNoSignedWrap(cast<BinaryOperator>(I)),
-        Q.IIQ.hasNoUnsignedWrap(cast<BinaryOperator>(I)), Q);
+        NewOps[0], NewOps[1],
+        Q.IIQ.hasNoSignedWrap(trait_cast<Trait, BinaryOperator>(I)),
+        Q.IIQ.hasNoUnsignedWrap(trait_cast<Trait, BinaryOperator>(I)), Q);
     break;
   case Instruction::LShr:
     Result = simplifyLShrInst(NewOps[0], NewOps[1],
                               Q.IIQ.isExact(cast<BinaryOperator>(I)), Q);
     break;
   case Instruction::AShr:
     Result = simplifyAShrInst(NewOps[0], NewOps[1],
                               Q.IIQ.isExact(cast<BinaryOperator>(I)), Q);
     break;
   case Instruction::And:
     Result = simplifyAndInst(NewOps[0], NewOps[1], Q);
     break;
   case Instruction::Or:
     Result = simplifyOrInst(NewOps[0], NewOps[1], Q);
     break;
   case Instruction::Xor:
     Result = simplifyXorInst(NewOps[0], NewOps[1], Q);
     break;
   case Instruction::ICmp:
-    Result = simplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), NewOps[0],
-                              NewOps[1], Q);
+    Result = simplifyICmpInst(trait_cast<Trait, ICmpInst>(I)->getPredicate(),
+                              NewOps[0], NewOps[1], Q);
     break;
   case Instruction::FCmp:
-    Result = simplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), NewOps[0],
-                              NewOps[1], I->getFastMathFlags(), Q);
+    Result = simplifyFCmpInst(trait_cast<Trait, FCmpInst>(I)->getPredicate(),
+                              NewOps[0], NewOps[1],
+                              TraitInst->getFastMathFlags(), Q);
     break;
   case Instruction::Select:
     Result = simplifySelectInst(NewOps[0], NewOps[1], NewOps[2], Q);
     break;
   case Instruction::GetElementPtr: {
     auto *GEPI = cast<GetElementPtrInst>(I);
     Result =
         simplifyGEPInst(GEPI->getSourceElementType(), NewOps[0],
case Instruction::Call: {
     break;
   }
   case Instruction::Freeze:
     Result = llvm::simplifyFreezeInst(NewOps[0], Q);
     break;
 #define HANDLE_CAST_INST(num, opc, clas) case Instruction::opc:
 #include "llvm/IR/Instruction.def"
 #undef HANDLE_CAST_INST
-    Result = simplifyCastInst(I->getOpcode(), NewOps[0], I->getType(), Q);
+    Result =
+        simplifyCastInst(TraitInst->getOpcode(), NewOps[0], I->getType(), Q);
     break;
   case Instruction::Alloca:
     // No simplifications for Alloca and it can't be constant folded.
     Result = nullptr;
     break;
   case Instruction::Load:
     Result = simplifyLoadInst(cast<LoadInst>(I), NewOps[0], Q);
     break;
   }
 
   /// If called on unreachable code, the above logic may report that the
   /// instruction simplified to itself.  Make life easier for users by
   /// detecting that case here, returning a safe value instead.
   return Result == I ? UndefValue::get(I->getType()) : Result;
 }
 
+// Instantiate for all enabled traits.
+#define ENABLE_TRAIT(TRAIT)                                                    \
+  template Value *llvm::simplifyInstructionWithOperandsAndTrait<TRAIT>(        \
+      Instruction *, ArrayRef<Value *> NewOps, const SimplifyQuery &,          \
+      OptimizationRemarkEmitter *);                                            \
+  template Value *llvm::simplifyBinOp(unsigned, Value *, Value *,              \
+                                      const SimplifyQuery &,                   \
+                                      MatcherContext<TRAIT> &);                \
+  template Value *llvm::simplifyBinOp(unsigned, Value *, Value *,              \
+                                      FastMathFlags, const SimplifyQuery &,    \
+                                      MatcherContext<TRAIT> &);                \
+  template Value *llvm::simplifyFAddInst(                                      \
+      Value *, Value *, FastMathFlags, const SimplifyQuery &,                  \
+      MatcherContext<TRAIT> &, fp::ExceptionBehavior, RoundingMode);           \
+  template Value *llvm::simplifyAddInst(Value *, Value *, bool, bool,          \
+                                        const SimplifyQuery &,                 \
+                                        MatcherContext<TRAIT> &);
+#include "llvm/IR/Traits/EnabledTraits.def"
+
+Value *llvm::simplifyInstruction(Instruction *I, const SimplifyQuery &SQ,
+                                 OptimizationRemarkEmitter *ORE) {
+  SmallVector<Value *, 8> Ops(I->operands());
+
+  // Either all or no fp operations in a function are constrained.
+#define IF_HAS_TRAIT_CFPTrait                                                  \
+  if (CFPTrait::consider(I)) {                                                 \
+    if (auto *Result = simplifyInstructionWithOperandsAndTrait<CFPTrait>(      \
+            I, Ops, SQ, ORE))                                                  \
+      return Result;                                                           \
+  }
+  IF_HAS_TRAIT_CFPTrait
+
+  /// Vector-predicated code.
+  /// FIXME: We use a quick heuristics (is this a vector type?) for now.
+#define IF_HAS_TRAIT_VPTrait                                                   \
+  if (VPTrait::consider(I)) {                                                  \
+    if (auto *Result =                                                         \
+            simplifyInstructionWithOperandsAndTrait<VPTrait>(I, Ops, SQ, ORE)) \
+      return Result;                                                           \
+  }
+
+#define IF_HAS_TRAIT_EmptyTrait
+
+#define ENABLE_TRAIT(V) IF_HAS_TRAIT_##V
+#include "llvm/IR/Traits/EnabledTraits.def"
+
+      // Regardless of the EnabledTraits.def file - always instantiate for the
+      // empty trait.
+      return simplifyInstructionWithOperandsAndTrait<EmptyTrait>(I, Ops, SQ,
+                                                                 ORE);
+}
+
 Value *llvm::simplifyInstructionWithOperands(Instruction *I,
                                              ArrayRef<Value *> NewOps,
                                              const SimplifyQuery &SQ,
                                              OptimizationRemarkEmitter *ORE) {
   assert(NewOps.size() == I->getNumOperands() &&
          "Number of operands should match the instruction!");
-  return ::simplifyInstructionWithOperands(I, NewOps, SQ, ORE);
-}
-
-Value *llvm::simplifyInstruction(Instruction *I, const SimplifyQuery &SQ,
-                                 OptimizationRemarkEmitter *ORE) {
-  SmallVector<Value *, 8> Ops(I->operands());
-  return ::simplifyInstructionWithOperands(I, Ops, SQ, ORE);
+  return ::simplifyInstructionWithOperandsAndTrait<DefaultTrait>(I, NewOps, SQ,
+                                                                 ORE);
 }
 
 /// Implementation of recursive simplification through an instruction's
 /// uses.
 ///
 /// This is the common implementation of the recursive simplification routines.
 /// If we have a pre-simplified value in 'SimpleV', that is forcibly used to
 /// replace the instruction 'I'. Otherwise, we simply add 'I' to the list of

llvm/lib/IR/CMakeLists.txt

add_llvm_component_library(LLVMCore
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/IR
 
   LINK_LIBS
   ${LLVM_PTHREAD_LIB}
 
   DEPENDS
   intrinsics_gen
+  enabled_traits
 
   LINK_COMPONENTS
   BinaryFormat
   Remarks
   Support
   )

llvm/lib/IR/IntrinsicInst.cpp

Value *InstrProfIncrementInst::getStep() const {
   if (InstrProfIncrementInstStep::classof(this)) {
     return const_cast<Value *>(getArgOperand(4));
   }
   const Module *M = getModule();
   LLVMContext &Context = M->getContext();
   return ConstantInt::get(Type::getInt64Ty(Context), 1);
 }
 
+bool ConstrainedFPIntrinsic::hasRoundingMode() const {
+  switch (getIntrinsicID()) {
+  default:
+    return false;
+#define INSTRUCTION(N, A, R, I)                                                \
+  case Intrinsic::I:                                                           \
+    return R;
+#include "llvm/IR/ConstrainedOps.def"
+  }
+}
+
 Optional<RoundingMode> ConstrainedFPIntrinsic::getRoundingMode() const {
+  if (!hasRoundingMode())
+    return None;
   unsigned NumOperands = arg_size();
   Metadata *MD = nullptr;
   auto *MAV = dyn_cast<MetadataAsValue>(getArgOperand(NumOperands - 2));
   if (MAV)
     MD = MAV->getMetadata();
   if (!MD || !isa<MDString>(MD))
     return None;
   return convertStrToRoundingMode(cast<MDString>(MD)->getString());
return StringSwitch<FCmpInst::Predicate>(cast<MDString>(MD)->getString())
       .Case("une", FCmpInst::FCMP_UNE)
       .Default(FCmpInst::BAD_FCMP_PREDICATE);
 }
 
 FCmpInst::Predicate ConstrainedFPCmpIntrinsic::getPredicate() const {
   return getFPPredicateFromMD(getArgOperand(2));
 }
 
+Optional<unsigned> ConstrainedFPIntrinsic::getFunctionalOpcode() const {
+  switch (getIntrinsicID()) {
+  default:
+    // Just some intrinsic call
+    return None;
+
+#define DAG_FUNCTION(OPC, FPEXCEPT, FPROUND, INTRIN, SD)
+
+#define DAG_INSTRUCTION(OPC, FPEXCEPT, FPROUND, INTRIN, SD)                    \
+  case Intrinsic::INTRIN:                                                      \
+    return OPC;
+#include "llvm/IR/ConstrainedOps.def"
+  }
+}
+
 bool ConstrainedFPIntrinsic::isUnaryOp() const {
   switch (getIntrinsicID()) {
   default:
     return false;
 #define INSTRUCTION(NAME, NARG, ROUND_MODE, INTRINSIC)                         \
   case Intrinsic::INTRINSIC:                                                   \
     return NARG == 1;
 #include "llvm/IR/ConstrainedOps.def"

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

 /// Match loop-invariant value.
 template <typename SubPattern_t> struct match_LoopInvariant {
   SubPattern_t SubPattern;
   const Loop *L;
 
   match_LoopInvariant(const SubPattern_t &SP, const Loop *L)
       : SubPattern(SP), L(L) {}
 
+  // FIXME: Existing trait-unaware patterns should keep working without code changes.
+  template <typename ITy, typename Trait=DefaultTrait> bool match(ITy *V, MatcherContext<Trait> &MContext) {
+    return L->isLoopInvariant(V) && SubPattern.match(V, MContext);
+  }
+
   template <typename ITy> bool match(ITy *V) {
     return L->isLoopInvariant(V) && SubPattern.match(V);
   }
 };
 
 /// Matches if the value is loop-invariant.
 template <typename Ty>
 inline match_LoopInvariant<Ty> m_LoopInvariant(const Ty &M, const Loop *L) {

llvm/test/Transforms/InstSimplify/add_vp.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instsimplify -S | FileCheck %s
+
+declare <2 x i32> @llvm.vp.add.v2i32(<2 x i32>, <2 x i32>, <2 x i1>, i32)
+declare <2 x i32> @llvm.vp.sub.v2i32(<2 x i32>, <2 x i32>, <2 x i1>, i32)
+
+declare <2 x i8> @llvm.vp.add.v2i8(<2 x i8>, <2 x i8>, <2 x i1>, i32)
+declare <2 x i8> @llvm.vp.sub.v2i8(<2 x i8>, <2 x i8>, <2 x i1>, i32)
+
+; Constant folding should just work.
+define <2 x i32> @constant_vp_add(<2 x i1> %mask, i32 %evl) {
+; CHECK-LABEL: @constant_vp_add(
+; CHECK-NEXT:    ret <2 x i32> <i32 10, i32 10>
+;
+  %Q = call <2 x i32> @llvm.vp.add.v2i32(<2 x i32> <i32 3, i32 3>, <2 x i32> <i32 7, i32 7>, <2 x i1> %mask, i32 %evl)
+  ret <2 x i32> %Q
+}
+
+; Simplifying pure VP intrinsic patterns.
+define <2 x i32> @common_sub_operand(<2 x i32> %X, <2 x i32> %Y, <2 x i1> %mask, i32 %evl) {
+; CHECK-LABEL: @common_sub_operand(
+; CHECK-NEXT:    ret <2 x i32> [[X:%.*]]
+;
+  ; %Z = sub i32 %X, %Y, vp(%mask, %evl)
+  %Z = call <2 x i32> @llvm.vp.sub.v2i32(<2 x i32> %X, <2 x i32> %Y, <2 x i1> %mask, i32 %evl)
+  ; %Q = add i32 %Z, %Y, vp(%mask, %evl)
+  %Q = call <2 x i32> @llvm.vp.add.v2i32(<2 x i32> %Z, <2 x i32> %Y, <2 x i1> %mask, i32 %evl)
+  ret <2 x i32> %Q
+}
+
+; Mixing regular SIMD with vp intrinsics (vp add match root).
+define <2 x i32> @common_sub_operand_vproot(<2 x i32> %X, <2 x i32> %Y, <2 x i1> %mask, i32 %evl) {
+; CHECK-LABEL: @common_sub_operand_vproot(
+; CHECK-NEXT:    ret <2 x i32> [[X:%.*]]
+;
+  %Z = sub <2 x i32> %X, %Y
+  ; %Q = add i32 %Z, %Y, vp(%mask, %evl)
+  %Q = call <2 x i32> @llvm.vp.add.v2i32(<2 x i32> %Z, <2 x i32> %Y, <2 x i1> %mask, i32 %evl)
+  ret <2 x i32> %Q
+}
+
+; Mixing regular SIMD with vp intrinsics (vp inside pattern, regular instruction root).
+define <2 x i32> @common_sub_operand_vpinner(<2 x i32> %X, <2 x i32> %Y, <2 x i1> %mask, i32 %evl) {
+; CHECK-LABEL: @common_sub_operand_vpinner(
+; CHECK-NEXT:    ret <2 x i32> [[X:%.*]]
+;
+  ; %Z = sub i32 %X, %Y, vp(%mask, %evl)
+  %Z = call <2 x i32> @llvm.vp.sub.v2i32(<2 x i32> %X, <2 x i32> %Y, <2 x i1> %mask, i32 %evl)
+  %Q = add <2 x i32> %Z, %Y
+  ret <2 x i32> %Q
+}
+
+define <2 x i32> @negated_operand(<2 x i32> %x, <2 x i1> %mask, i32 %evl) {
+; CHECK-LABEL: @negated_operand(
+; CHECK-NEXT:    ret <2 x i32> zeroinitializer
+;
+  ; %negx = sub i32 0, %x
+  %negx = call <2 x i32> @llvm.vp.sub.v2i32(<2 x i32> zeroinitializer, <2 x i32> %x, <2 x i1> %mask, i32 %evl)
+  ; %r = add i32 %negx, %x
+  %r = call <2 x i32> @llvm.vp.add.v2i32(<2 x i32> %negx, <2 x i32> %x, <2 x i1> %mask, i32 %evl)
+  ret <2 x i32> %r
+}
+
+; TODO Lift InstSimplify::SimplifyAdd to the trait framework to optimize this.
+define <2 x i8> @knownnegation(<2 x i8> %x, <2 x i8> %y, <2 x i1> %mask, i32 %evl) {
+; TODO-CHECK-LABEL: @knownnegation(
+; TODO-XHECK-NEXT:    ret i8 <2 x i8> zeroinitializer 
+;
+  ; %xy = sub i8 %x, %y
+  %xy = call <2 x i8> @llvm.vp.sub.v2i8(<2 x i8> %x, <2 x i8> %y, <2 x i1> %mask, i32 %evl)
+  ; %yx = sub i8 %y, %x
+  %yx = call <2 x i8> @llvm.vp.sub.v2i8(<2 x i8> %y, <2 x i8> %x, <2 x i1> %mask, i32 %evl)
+  ; %r = add i8 %xy, %yx
+  %r = call <2 x i8> @llvm.vp.add.v2i8(<2 x i8> %xy, <2 x i8> %yx, <2 x i1> %mask, i32 %evl)
+  ret <2 x i8> %r
+}

llvm/test/Transforms/InstSimplify/fast-math-strictfp.ll

;
   %b = call float @llvm.experimental.constrained.fmul.f32(float %a, float 0.0, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   ret float %b
 }
 
 ; -X + X --> 0.0 (with nnan on the fadd)
 
 define float @fadd_binary_fnegx(float %x) #0 {
 ; CHECK-LABEL: @fadd_binary_fnegx(
-; CHECK-NEXT:    [[NEGX:%.*]] = call float @llvm.experimental.constrained.fsub.f32(float -0.000000e+00, float [[X:%.*]], metadata !"round.tonearest", metadata !"fpexcept.ignore") #[[ATTR0]]
-; CHECK-NEXT:    [[R:%.*]] = call nnan float @llvm.experimental.constrained.fadd.f32(float [[NEGX]], float [[X]], metadata !"round.tonearest", metadata !"fpexcept.ignore") #[[ATTR0]]
-; CHECK-NEXT:    ret float [[R]]
+; CHECK-NEXT:    ret float 0.000000e+00
 ;
   %negx = call float @llvm.experimental.constrained.fsub.f32(float -0.0, float %x, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   %r = call nnan float @llvm.experimental.constrained.fadd.f32(float %negx, float %x, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   ret float %r
 }
 
 define float @fadd_unary_fnegx(float %x) #0 {
 ; CHECK-LABEL: @fadd_unary_fnegx(
 ; CHECK-NEXT:    ret float 0.000000e+00
 ;
   %negx = fneg float %x
   %r = call nnan float @llvm.experimental.constrained.fadd.f32(float %negx, float %x, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   ret float %r
 }
 
 ; X + -X --> 0.0 (with nnan on the fadd)
 
 define <2 x float> @fadd_binary_fnegx_commute_vec(<2 x float> %x) #0 {
 ; CHECK-LABEL: @fadd_binary_fnegx_commute_vec(
-; CHECK-NEXT:    [[NEGX:%.*]] = call <2 x float> @llvm.experimental.constrained.fsub.v2f32(<2 x float> <float -0.000000e+00, float -0.000000e+00>, <2 x float> [[X:%.*]], metadata !"round.tonearest", metadata !"fpexcept.ignore") #[[ATTR0]]
-; CHECK-NEXT:    [[R:%.*]] = call nnan <2 x float> @llvm.experimental.constrained.fadd.v2f32(<2 x float> [[X]], <2 x float> [[NEGX]], metadata !"round.tonearest", metadata !"fpexcept.ignore") #[[ATTR0]]
-; CHECK-NEXT:    ret <2 x float> [[R]]
+; CHECK-NEXT:    ret <2 x float> zeroinitializer
 ;
   %negx = call <2 x float> @llvm.experimental.constrained.fsub.v2f32(<2 x float> <float -0.0, float -0.0>, <2 x float> %x, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   %r = call nnan <2 x float> @llvm.experimental.constrained.fadd.v2f32(<2 x float> %x, <2 x float> %negx, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   ret <2 x float> %r
 }
 
 define <2 x float> @fadd_unary_fnegx_commute_vec(<2 x float> %x) #0 {
 ; CHECK-LABEL: @fadd_unary_fnegx_commute_vec(
 ; CHECK-NEXT:    ret <2 x float> zeroinitializer
 ;
   %negx = fneg <2 x float> %x
   %r = call nnan <2 x float> @llvm.experimental.constrained.fadd.v2f32(<2 x float> %x, <2 x float> %negx, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   ret <2 x float> %r
 }
 
 define <2 x float> @fadd_fnegx_commute_vec_undef(<2 x float> %x) #0 {
 ; CHECK-LABEL: @fadd_fnegx_commute_vec_undef(
-; CHECK-NEXT:    [[NEGX:%.*]] = call <2 x float> @llvm.experimental.constrained.fsub.v2f32(<2 x float> <float undef, float -0.000000e+00>, <2 x float> [[X:%.*]], metadata !"round.tonearest", metadata !"fpexcept.ignore") #[[ATTR0]]
-; CHECK-NEXT:    [[R:%.*]] = call nnan <2 x float> @llvm.experimental.constrained.fadd.v2f32(<2 x float> [[X]], <2 x float> [[NEGX]], metadata !"round.tonearest", metadata !"fpexcept.ignore") #[[ATTR0]]
-; CHECK-NEXT:    ret <2 x float> [[R]]
+; CHECK-NEXT:    ret <2 x float> zeroinitializer
 ;
   %negx = call <2 x float> @llvm.experimental.constrained.fsub.v2f32(<2 x float> <float undef, float -0.0>, <2 x float> %x, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   %r = call nnan <2 x float> @llvm.experimental.constrained.fadd.v2f32(<2 x float> %x, <2 x float> %negx, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   ret <2 x float> %r
 }
 
 ; https://bugs.llvm.org/show_bug.cgi?id=26958
 ; https://bugs.llvm.org/show_bug.cgi?id=27151
;
   %could_be_nan = call float @llvm.experimental.constrained.fadd.f32(float %x, float %t, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   ret float %could_be_nan
 }
 
 ; X + (0.0 - X) --> 0.0 (with nnan on the fadd)
 
 define float @fadd_fsub_nnan_ninf(float %x) #0 {
 ; CHECK-LABEL: @fadd_fsub_nnan_ninf(
-; CHECK-NEXT:    [[SUB:%.*]] = call nnan ninf float @llvm.experimental.constrained.fsub.f32(float 0.000000e+00, float [[X:%.*]], metadata !"round.tonearest", metadata !"fpexcept.ignore") #[[ATTR0]]
-; CHECK-NEXT:    [[ZERO:%.*]] = call nnan ninf float @llvm.experimental.constrained.fadd.f32(float [[X]], float [[SUB]], metadata !"round.tonearest", metadata !"fpexcept.ignore") #[[ATTR0]]
-; CHECK-NEXT:    ret float [[ZERO]]
+; CHECK-NEXT:    ret float 0.0
 ;
   %sub = call nnan ninf float @llvm.experimental.constrained.fsub.f32(float 0.0, float %x, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   %zero = call nnan ninf float @llvm.experimental.constrained.fadd.f32(float %x, float %sub, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   ret float %zero
 }
 
 ; (0.0 - X) + X --> 0.0 (with nnan on the fadd)
 
 define <2 x float> @fadd_fsub_nnan_ninf_commute_vec(<2 x float> %x) #0 {
 ; CHECK-LABEL: @fadd_fsub_nnan_ninf_commute_vec(
-; CHECK-NEXT:    [[SUB:%.*]] = call <2 x float> @llvm.experimental.constrained.fsub.v2f32(<2 x float> zeroinitializer, <2 x float> [[X:%.*]], metadata !"round.tonearest", metadata !"fpexcept.ignore") #[[ATTR0]]
-; CHECK-NEXT:    [[ZERO:%.*]] = call nnan ninf <2 x float> @llvm.experimental.constrained.fadd.v2f32(<2 x float> [[SUB]], <2 x float> [[X]], metadata !"round.tonearest", metadata !"fpexcept.ignore") #[[ATTR0]]
-; CHECK-NEXT:    ret <2 x float> [[ZERO]]
+; CHECK-NEXT:    ret <2 x float> zeroinitializer
 ;
   %sub = call <2 x float> @llvm.experimental.constrained.fsub.v2f32(<2 x float> zeroinitializer, <2 x float> %x, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   %zero = call nnan ninf <2 x float> @llvm.experimental.constrained.fadd.v2f32(<2 x float> %sub, <2 x float> %x, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   ret <2 x float> %zero
 }
 
 ; 'ninf' is not required because 'nnan' allows us to assume
 ; that X is not INF or -INF (adding opposite INFs would be NaN).
 
 define float @fadd_fsub_nnan(float %x) #0 {
 ; CHECK-LABEL: @fadd_fsub_nnan(
-; CHECK-NEXT:    [[SUB:%.*]] = call float @llvm.experimental.constrained.fsub.f32(float 0.000000e+00, float [[X:%.*]], metadata !"round.tonearest", metadata !"fpexcept.ignore") #[[ATTR0]]
-; CHECK-NEXT:    [[ZERO:%.*]] = call nnan float @llvm.experimental.constrained.fadd.f32(float [[SUB]], float [[X]], metadata !"round.tonearest", metadata !"fpexcept.ignore") #[[ATTR0]]
-; CHECK-NEXT:    ret float [[ZERO]]
+; CHECK-NEXT:    ret float 0.0
 ;
   %sub = call float @llvm.experimental.constrained.fsub.f32(float 0.0, float %x, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   %zero = call nnan float @llvm.experimental.constrained.fadd.f32(float %sub, float %x, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   ret float %zero
 }
 
 ; fsub nnan x, x ==> 0.0
 define float @fsub_x_x(float %a) #0 {

llvm/test/Transforms/InstSimplify/floating-point-arithmetic-strictfp.ll

;
   %r = call reassoc nsz float @llvm.experimental.constrained.fsub.f32(float %y, float %a, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   ret float %r
 }
 
 ; Y + (X - Y) --> X
 
 define <2 x float> @fsub_fadd_common_op_vec(<2 x float> %x, <2 x float> %y) #0 {
 ; CHECK-LABEL: @fsub_fadd_common_op_vec(
-; CHECK-NEXT:    [[S:%.*]] = call <2 x float> @llvm.experimental.constrained.fsub.v2f32(<2 x float> [[X:%.*]], <2 x float> [[Y:%.*]], metadata !"round.tonearest", metadata !"fpexcept.ignore") #[[ATTR0]]
-; CHECK-NEXT:    [[R:%.*]] = call reassoc nsz <2 x float> @llvm.experimental.constrained.fadd.v2f32(<2 x float> [[Y]], <2 x float> [[S]], metadata !"round.tonearest", metadata !"fpexcept.ignore") #[[ATTR0]]
-; CHECK-NEXT:    ret <2 x float> [[R]]
+; CHECK-NEXT:    ret <2 x float> %x
 ;
   %s = call <2 x float> @llvm.experimental.constrained.fsub.v2f32(<2 x float> %x, <2 x float> %y, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   %r = call reassoc nsz <2 x float> @llvm.experimental.constrained.fadd.v2f32(<2 x float> %y, <2 x float> %s, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   ret <2 x float> %r
 }
 
 ; (X - Y) + Y --> X
 
 define float @fsub_fadd_common_op_commute(float %x, float %y) #0 {
 ; CHECK-LABEL: @fsub_fadd_common_op_commute(
-; CHECK-NEXT:    [[S:%.*]] = call float @llvm.experimental.constrained.fsub.f32(float [[X:%.*]], float [[Y:%.*]], metadata !"round.tonearest", metadata !"fpexcept.ignore") #[[ATTR0]]
-; CHECK-NEXT:    [[R:%.*]] = call reassoc nsz float @llvm.experimental.constrained.fadd.f32(float [[S]], float [[Y]], metadata !"round.tonearest", metadata !"fpexcept.ignore") #[[ATTR0]]
-; CHECK-NEXT:    ret float [[R]]
+; CHECK-NEXT:    ret float %x
 ;
   %s = call float @llvm.experimental.constrained.fsub.f32(float %x, float %y, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   %r = call reassoc nsz float @llvm.experimental.constrained.fadd.f32(float %s, float %y, metadata !"round.tonearest", metadata !"fpexcept.ignore") #0
   ret float %r
 }
 
 ; Negative test.
 ; Y + (Y - X) --> ?

llvm/test/Transforms/InstSimplify/fpadd_constrained.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instsimplify -S | FileCheck %s
+
+declare float @llvm.experimental.constrained.fadd.f32(float, float, metadata, metadata)
+declare <2 x float> @llvm.experimental.constrained.fadd.v2f32(<2 x float>, <2 x float>, metadata, metadata)
+declare float @llvm.experimental.constrained.fsub.f32(float, float, metadata, metadata)
+
+; fadd X, -0 ==> X
+define float @fadd_x_n0(float %a) {
+; CHECK-LABEL: @fadd_x_n0(
+; CHECK-NEXT:    ret float [[A:%.*]]
+;
+  %ret = call float @llvm.experimental.constrained.fadd.f32(float %a, float -0.0,
+                                               metadata !"round.tonearest",
+                                               metadata !"fpexcept.ignore") #0
+  ret float %ret
+}
+
+define <2 x float> @fadd_x_n0_vec_undef_elt(<2 x float> %a) {
+; CHECK-LABEL: @fadd_x_n0_vec_undef_elt(
+; CHECK-NEXT:    ret <2 x float> %a
+;
+  %ret = call <2 x float> @llvm.experimental.constrained.fadd.v2f32(<2 x float> %a, <2 x float> <float -0.0, float undef>,
+                                               metadata !"round.tonearest",
+                                               metadata !"fpexcept.ignore") #0
+  ret <2 x float> %ret
+}
+
+; We can't optimize away the fadd in this test because the input
+; value to the function and subsequently to the fadd may be -0.0.
+; In that one special case, the result of the fadd should be +0.0
+; rather than the first parameter of the fadd.
+
+; Fragile test warning: We need 6 sqrt calls to trigger the bug
+; because the internal logic has a magic recursion limit of 6.
+; This is presented without any explanation or ability to customize.
+
+declare float @sqrtf(float)
+
+define float @PR22688(float %x) {
+; CHECK-LABEL: @PR22688(
+; CHECK-NEXT:    [[TMP1:%.*]] = call float @sqrtf(float [[X:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = call float @sqrtf(float [[TMP1]])
+; CHECK-NEXT:    [[TMP3:%.*]] = call float @sqrtf(float [[TMP2]])
+; CHECK-NEXT:    [[TMP4:%.*]] = call float @sqrtf(float [[TMP3]])
+; CHECK-NEXT:    [[TMP5:%.*]] = call float @sqrtf(float [[TMP4]])
+; CHECK-NEXT:    [[TMP6:%.*]] = call float @sqrtf(float [[TMP5]])
+; CHECK-NEXT:    [[TMP7:%.*]] = call float @llvm.experimental.constrained.fadd.f32(float [[TMP6]], float 0.000000e+00,
+; CHECK-NEXT:    ret float [[TMP7]]
+;
+  %1 = call float @sqrtf(float %x)
+  %2 = call float @sqrtf(float %1)
+  %3 = call float @sqrtf(float %2)
+  %4 = call float @sqrtf(float %3)
+  %5 = call float @sqrtf(float %4)
+  %6 = call float @sqrtf(float %5)
+  %7 = call float @llvm.experimental.constrained.fadd.f32(float %6, float 0.0,
+                                               metadata !"round.tonearest",
+                                               metadata !"fpexcept.ignore") #0
+  ret float %7
+}
+
+attributes #0 = { strictfp nounwind readnone }