[GISel][RFC]: GlobalISel Combiner prototype

[aditya_nandakumar]

Summary

Hello All

Here's a prototype for GISel Combiner pass/framework.
The various components are

1. GICombinerHelper - this contains transformations that are common to all targets. Targets can pick and choose which transformations (at function/opcode granularity) each pass uses via configuring a GICombinerInfo.
2. GICombiner - this contains some common code and it does the traversal, driving of combines, worklist management and iterating until convergence.
3. GICombinerInfo - the GICombinerInfo is an interface with a virtual method called combine. The combiner info will allow targets to pick and choose (or implement their own specific combines). CombineInfos can make use of available combines in GICombineHelper to configure the transformations for a particular pass. Currently this approach allows cherry picking transformations from helpers (at function/opcode granularity) and also allows early returning on specific transformations. Targets also get to prioritize whether target specific combines run before/after the opt-in generic combines. Ideally we would like this part to be configured by both C++ and Tablegen. The CombinerInfo also has a field which indicates how to deal with IllegalOps (ie - should we allow to create them/or legalize them?). This has not been addressed in this patch as I'm not sure what the right approach here is.
4. A CombinerPass would configure a CombinerInfo, create the GICombiner with the Info, and call GICombiner::combineMachineInstrs(MachineFunction&).

The above organization is very similar to the GISelLegalizer.

This patch includes a CombinerPass called PreLegalizeCombiner which is meant to run before legalization. Currently the only implemented transformation in the helper is simple copy propagation.

This patch also includes an initial version of InstCombine like PatternMatcher for easy matching of combines along with unit tests.

Looking forward to your feedback.

[aditya_nandakumar]

Unrelated AArch64 change snuck in. Removed..

[qcolombet]

Hi Aditya,

The overall design looks good to me. Obviously given that's a prototype we still miss a bunch of comment, but I like the general approach.
I've put a few nitpicks here and there, but don't pay to much attention to them, I expect you will polish the patch when more people are on board.

Two things I'd like to call out:

1. When making this a real thing, we would need a patch in the GISel doc to explain the design and how it is intended to use
2. I am guessing the PreLegalizerPass is just to show case the prototype, other I think it misses two things: A. The relationship with GICombiner is strange to me and should be reworked IMO (see the comment on the PreLegalizeCombiner class itself) B. The target should have a way to inject/choose its own combines for the pass (I actually believe that if a target needs to do that it would be better of creating its own prelegalize pass)

Anyhow, thanks for putting that up. This looks promising!

Cheers,
-Quentin

include/llvm/CodeGen/GlobalISel/GICombiner.h

1 ↗

(On Diff #127443)

Unless it conflicts with something else, I would drop GI in the name. It already lives in the GlobalISel directory.

12 ↗

(On Diff #127443)

Use doxygen style comments

24 ↗

(On Diff #127443)

All the includes but MachineIRBuilder could be removed.
Use forward declarations for the type definitions.

31 ↗

(On Diff #127443)

Why is the combiner info not const here, ditto for TPC?

Basically, I am guessing there are good reasons (I didn't look at the implementation yet), but the comments should make it clear from the API.

Also, is it valid to give nullptr for TPC?
If not, we should use a reference as well.

include/llvm/CodeGen/GlobalISel/GICombinerHelper.h

1 ↗

(On Diff #127443)

Ditto for the GI prefix.

29 ↗

(On Diff #127443)

The builder comes with MRI already (getMF().getRegInfo()).
Should we still have it being an additional argument.

34 ↗

(On Diff #127443)

Is MI supposed to be a COPY or does this combine will do the check?

Basically, what is the precondition here.

36 ↗

(On Diff #127443)

We would need to document the API. I.e., what does the boolean mean? In particular, what happens to MI is a change has been made?

include/llvm/CodeGen/GlobalISel/GICombinerInfo.h

28 ↗

(On Diff #127443)

I'm guessing we would need an assert AllowIllegalOps || LInfo.

Also to answer one of the question, I believe we would want two different boolean:

• Allow creating illegal ops or not
• Legalize illegal ops or not

33 ↗

(On Diff #127443)

Where should the legality checks be done?

Basically, we need a method that all the all the subclasses of GICombinerInfo can call for this.

Maybe something around those lines:
combine(...) {
combineImpl(...) the thing that gets override
/ check legality stuff
}

include/llvm/CodeGen/GlobalISel/GMIPatternMatch.h

6 ↗

(On Diff #127443)

The header looks weird

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

262

Unrelated changes?

include/llvm/CodeGen/GlobalISel/PreLegalizeCombiner.h

36

The relationship between PreLegalizeCombiner and GICombiner looks strange to me.
In particular, before looking at the actual implementation of runOnMachineFunction, there is nothing showing that this pass uses GICombiner.

I would have expected something like GICombiner is a pass and PreLegalizeCombiner inherit from it and only set its custom PreLegalizeCombinerInfo thing.

42

Unless I missed it, there is no implementation for that.

lib/CodeGen/GlobalISel/CMakeLists.txt

6

Sort alphabetically

[qcolombet]

One more comment: Do you have an idea how we could make sure that the combiners are making progress?
Basically, I would like we think about two cases that bit us in the past:

1. Two combines undo each others
2. Two combines keep piling up (like expand op1 into op2 & op3 and expand op2 into op1 & op3 would keep having the IR growing)

[aditya_nandakumar]

Thanks Quentin. Will update the patch with the comments shortly.
Regarding tracking progress, I don't have a really good solution - I suspect it's possible to detect loops when every transformation is written in tablegen, but with mixing in C++, a naive approach would be to issue some diagnostic/warning after some large number of iterations in GICombiner.

include/llvm/CodeGen/GlobalISel/GICombiner.h

12 ↗

(On Diff #127443)

Thanks. Will do.

24 ↗

(On Diff #127443)

Makes sense. Will update.

31 ↗

(On Diff #127443)

I was wondering if the combiner info would have some state stored (possibly), and wanted only lvalue references (so the CombinerPass would create the Info on stack/heap and pass it in instead of passing in references to temporaries). Alternatively, the info could be copied (or passed in via unique_ptr.
The TPC is not currently used - making it const is definitely correct. Not really sure about if it can be null to make it reference.

include/llvm/CodeGen/GlobalISel/GICombinerHelper.h

1 ↗

(On Diff #127443)

Will Update.

29 ↗

(On Diff #127443)

Good point. We can remove the MRI.

34 ↗

(On Diff #127443)

Yes - in the implementation, it does an early return if it's not a copy. You're right in that we need to document the expected behavior.

36 ↗

(On Diff #127443)

the boolean return value is currently only used by the Combiner to track whether any change has been made so it needs to iterate again. It's also used to indicate if the pass made any changes.
Also, returning true (like the legalizer/selector) assumes that the instruction has been taken care of, and it's not guaranteed that the instruction is still alive.
Yes - documentation here would make it clear. Will do that.

include/llvm/CodeGen/GlobalISel/GICombinerInfo.h

28 ↗

(On Diff #127443)

Yup - the assert makes sense here.Will update.

The two different boolean approaches also make sense.

33 ↗

(On Diff #127443)

That sounds like a good approach.
Alternatively/Additionally, we can document that, the users should call some API to replace instructions (say CombineTo(FromMI, ToMI)) - where we can check before the original instruction is deleted, we can check the legality of the new instruction we're creating before replacing them. Of course, theres no way to force this upon the targets.

include/llvm/CodeGen/GlobalISel/GMIPatternMatch.h

6 ↗

(On Diff #127443)

Will fix that.

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

262

Might make sense to split this in a separate patch.
These build methods are used in the unit test for the patternMatchers.

include/llvm/CodeGen/GlobalISel/PreLegalizeCombiner.h

36

I went with the "has a" relationship with the GICombiner. Pretty much what the GICombiner does right now is the driving of the combines which felt like it belonged in a utility. Right now, there should be little/no difference to switch to each pass inheriting the GICombiner and I can do that if required.

42

This doesn't belong here (it's in the GICombiner). Good catch. Will remove that.

lib/CodeGen/GlobalISel/CMakeLists.txt

6

Thanks. Will do.

[hfinkel]

include/llvm/CodeGen/GlobalISel/GMIPatternMatch.h

163 ↗

(On Diff #127443)

Why is this named gi_match? Doesn't it apply to any MI as well?

[aditya_nandakumar]

include/llvm/CodeGen/GlobalISel/GMIPatternMatch.h

163 ↗

(On Diff #127443)

Hi Hal,

The match function above has been named gi_match as I was not sure if there is interest in using this beyond GlobalISel. We can definitely have it named match (and perhaps remove the GI prefix from all the matchers as well).

[hfinkel]

include/llvm/CodeGen/GlobalISel/GMIPatternMatch.h

163 ↗

(On Diff #127443)

I think it would be great to be able to use these on SSA MI as well (but then having the 'gi' prefix will look odd).

[aditya_nandakumar]

include/llvm/CodeGen/GlobalISel/GMIPatternMatch.h

163 ↗

(On Diff #127443)

Thanks for the feedback. I'll change the name to match.

[aemerson]

I think it would be helpful to articulate here or in another patch/discussion the rationale for having a pre-legalize pass. While targets can of course do as they see fit, we should have some documentation on the source explaining what kind things are expected to be done there, and what kind of things are suggested to be done later. I.e. we can do some early canonicalization, early simplification to save compile time etc.

include/llvm/CodeGen/GlobalISel/PreLegalizeCombiner.h

36

I agree with Quentin that it seems having a generic GICombiner to inherit from seems clearer from a design point of view.

[aditya_nandakumar]

I will update the patch shortly with the feedback.

With respect to why I put up the PreLegalizationCombine pass, the main reason was to show a proof of concept pass to use the interfaces.
With respect to what to put in, I've seen lots of terrible code produced by the IRTranslator. Some cases that I saw were
getelementptr expanding to MUL with 1.

Sequence of LLVM_IR instructions building a 4 x vector with 4 insertelements result in IRTranslator producing 4 INSERT_VECTOR_ELT where as we can produce 1 MERGE_VALUES.
I can imagine similar cases of insertvectorelements followed by extractvectorelements which can probably be directly simplified as copies.

The other reason could be for canonicalization for targets (for eg, selects -> select_cc etc).

While these are not strictly necessary for correctness(also some of these probably belong in instcombine), I think it will simplify a lot of the code to be handled in subsequent passes, as well as compile time.

include/llvm/CodeGen/GlobalISel/PreLegalizeCombiner.h

36

Thanks. I will update that shortly.

[aditya_nandakumar]

Updated with feedback.

[aditya_nandakumar]

Updated based on feedback.

[aditya_nandakumar]

Missed removal of an un-used function.

[aditya_nandakumar]

include/llvm/CodeGen/GlobalISel/PreLegalizeCombiner.h

36

The one downside I see to making it based on inheritance is that, things like MachineFunction is not available during creation of the CombinerInfo (pass construction). Passes would need to initialize the legalizerInfo during the runOnMachineFunction call instead if we go this route.

[dsanders]

GICombinerHelper - this contains transformations that are common to all targets. Targets can pick and choose which transformations (at function/opcode granularity) each pass uses via configuring a GICombinerInfo.

Could you clarify how you see this class growing in the long run? I'm a bit worried that we will see a proliferation of functions because a few targets (or just one) needed to do something a little different.

To use an existing example from SelectionDAG, suppose there is a tryCombineSelect() that contains target independent combines (select (not A), B, C) -> (select A, C, B) and similar. Now suppose a group of targets want to take advantage of the fact that comparisons produce 0/1 and add rules like (select A, 1, 0) -> A. How would this be integrated? I can see two main ways:

• We can add the new rules to the existing tryCombineSelect() with appropriate guards.
• We can break up tryCombineSelect() into pieces and have targets stick the pieces together the way they want. tryCombineSelect() is renamed to tryCombineSelect_AllTargets(), a new tryCombineSelect_CmpUsesZeroOrOne() is added.

The former is simpler but it doesn't allow targets to eliminate code they don't need which is something we've generally been trying to do and we don't seem to have a way to provide the values for the guards in the current design. The latter does support eliminating code but is ugly and gets worse as we'll soon see.

Now suppose other targets want to take advantage of their comparisons producing 0/-1 to do the same thing. Similar to before, we can either:

• Add the new rules to tryCombineSelect() with appropriate guards.
• Add a tryCombineSelect_CmpUsesZeroOrMinusOne().

Now suppose an awkward target comes along and wants to take advantage of scalar compares producing 0/1 and vector compares producing 0/-1. The code for both already exists in CombinerHelper so we don't really want to re-implement it, but we also don't really want to split tryCombineSelect_CmpUsesZeroOrOne() into tryCombineSelect_CmpUsesZeroOrOne_scalar() and tryCombineSelect_CmpUsesZeroOrOne_vector() as well as tryCombineSelect_CmpUsesZeroOrMinusOne() into tryCombineSelect_CmpUsesZeroOrMinusOne_scalar() and tryCombineSelect_CmpUsesZeroOrMinusOne_vector() since the proliferation of functions is starting to get unwieldy. We have five functions to handle various selects already and I haven't accounted for floating point yet.

What are your thoughts on how CombinerHelper will grow?

[dsanders]

include/llvm/CodeGen/GlobalISel/MIPatternMatch.h

13–14

Just a little nit: These guards should follow the convention

include/llvm/CodeGen/GlobalISel/PreLegalizeCombiner.h

36

You should be able to retrieve it from MI.getParent().getParent().getSubtarget().getLegalizerInfo() or something like that

[aditya_nandakumar]

In D41373#966318, @dsanders wrote:

GICombinerHelper - this contains transformations that are common to all targets. Targets can pick and choose which transformations (at function/opcode granularity) each pass uses via configuring a GICombinerInfo.

Could you clarify how you see this class growing in the long run? I'm a bit worried that we will see a proliferation of functions because a few targets (or just one) needed to do something a little different.

To use an existing example from SelectionDAG, suppose there is a tryCombineSelect() that contains target independent combines (select (not A), B, C) -> (select A, C, B) and similar. Now suppose a group of targets want to take advantage of the fact that comparisons produce 0/1 and add rules like (select A, 1, 0) -> A. How would this be integrated? I can see two main ways:

• We can add the new rules to the existing tryCombineSelect() with appropriate guards.
• We can break up tryCombineSelect() into pieces and have targets stick the pieces together the way they want. tryCombineSelect() is renamed to tryCombineSelect_AllTargets(), a new tryCombineSelect_CmpUsesZeroOrOne() is added.

The former is simpler but it doesn't allow targets to eliminate code they don't need which is something we've generally been trying to do and we don't seem to have a way to provide the values for the guards in the current design. The latter does support eliminating code but is ugly and gets worse as we'll soon see.

Now suppose other targets want to take advantage of their comparisons producing 0/-1 to do the same thing. Similar to before, we can either:

• Add the new rules to tryCombineSelect() with appropriate guards.
• Add a tryCombineSelect_CmpUsesZeroOrMinusOne().

Now suppose an awkward target comes along and wants to take advantage of scalar compares producing 0/1 and vector compares producing 0/-1. The code for both already exists in CombinerHelper so we don't really want to re-implement it, but we also don't really want to split tryCombineSelect_CmpUsesZeroOrOne() into tryCombineSelect_CmpUsesZeroOrOne_scalar() and tryCombineSelect_CmpUsesZeroOrOne_vector() as well as tryCombineSelect_CmpUsesZeroOrMinusOne() into tryCombineSelect_CmpUsesZeroOrMinusOne_scalar() and tryCombineSelect_CmpUsesZeroOrMinusOne_vector() since the proliferation of functions is starting to get unwieldy. We have five functions to handle various selects already and I haven't accounted for floating point yet.

What are your thoughts on how CombinerHelper will grow?

With this approach, I expect adding target specific rules to be fairly easy (Targets can extend/inherit GICombinerHelper) and add specific overrides for the generic tryVisitOpcode.
Removing rules on the other hand is a little difficult. If the target sees a transformation that they don't want (which the generic helper does), they have the option to match that specific pattern and early return false. This works, but I don't think this is elegant design wise.
Regarding guards vs splitting functions and chaining various pieces, I see pros and cons to both approaches. I would probably go with the latter and make the targets opt in to all the select transformations they want. If it indeed does go out of hand (how many such cases really exist?), then we probably need to revisit this part.

[aditya_nandakumar]

include/llvm/CodeGen/GlobalISel/PreLegalizeCombiner.h

36

The problem is, when do you initialize it? Do you check if it's initialized during each combine invocation? It seems wasteful to have to check every time (even if initialized).
The alternative is to have a setter that initializes the LegalizerInfo during runOnMachineFunction.

[bogner]

include/llvm/CodeGen/GlobalISel/PreLegalizeCombiner.h

36

FWIW I think the has-a relationship that Aditya's gone with is much simpler and clearer here.

The pass has the single responsibility of setting things up for the pass pipeline itself, while the GICombiner parts have their own single responsibility of doing the combines themselves. The alternative approach with inheritance will muddy up these concepts and make it harder to tell where the lines between concepts are.

[qcolombet]

Mostly looks good to me.
We probably want to make two separate patches:

• One with the pattern matching capabilities
• One with the new pass

include/llvm/CodeGen/GlobalISel/PreLegalizeCombiner.h

36

That's a good point. Given how simple the pass itself is, it is fine not to involve inheritance at this point.

[aditya_nandakumar]

Split the PatternMatcher part to https://reviews.llvm.org/D42439
Updated based on Justin, Quentin's feedback.

[aemerson]

I think this is ok to progress now. We're happy with the overall design, although the pre-legalize pass is probably unnecessary at this moment, so leave that for another patch?

[aditya_nandakumar]

In D41373#986548, @aemerson wrote:

I think this is ok to progress now. We're happy with the overall design, although the pre-legalize pass is probably unnecessary at this moment, so leave that for another patch?

Sure. I can split that up.

[aditya_nandakumar]

As per Amara's feedback, removed the prelegalizeCombiner from this review. I can put it up in a separate review as an example in tree for how to use the framework.

[aemerson]

LGTM with some minor comment fixes.

include/llvm/CodeGen/GlobalISel/CombinerHelper.h

14

80 cols?

include/llvm/CodeGen/GlobalISel/CombinerInfo.h

12

Superfluous '//'.

lib/CodeGen/GlobalISel/Combiner.cpp

12

Same here.

lib/CodeGen/GlobalISel/CombinerHelper.cpp

41

I think we're better off without this comment.

[aditya_nandakumar]

Thanks @aemerson . Fixed the nits you mentioned.

[aditya_nandakumar]

Committed in r323392

include/llvm/CodeGen/GlobalISel/Combiner.h

+//== ----- llvm/CodeGen/GlobalISel/Combiner.h --------------------- == //
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// This contains common code to drive combines. Combiner Passes will need to
+/// setup a CombinerInfo and call combineMachineFunction.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_GLOBALISEL_COMBINER_H
+#define LLVM_CODEGEN_GLOBALISEL_COMBINER_H
+
+#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+
+namespace llvm {
+class MachineRegisterInfo;
+class CombinerInfo;
+class TargetPassConfig;
+class MachineFunction;
+
+class Combiner : public MachineFunctionPass {
+public:
+  Combiner(char ID, CombinerInfo &CombinerInfo);
+
+  bool runOnMachineFunction(MachineFunction &MF);
+
+protected:
+  CombinerInfo &CInfo;
+
+  MachineRegisterInfo *MRI = nullptr;
+  const TargetPassConfig *TPC;
+  MachineIRBuilder Builder;
+};
+
+} // End namespace llvm.
+
+#endif // LLVM_CODEGEN_GLOBALISEL_GICOMBINER_H

include/llvm/CodeGen/GlobalISel/CombinerHelper.h

+//== llvm/CodeGen/GlobalISel/CombinerHelper.h ---------------- -*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// This contains common combine transformations that may be used in a combine
+/// pass,or by the target elsewhere.
+/// Targets can pick individual opcode transformations from the helper or use
+/// tryCombine which invokes all transformations. All of the transformations return
+/// true if the MachineInstruction changed and false otherwise.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_GLOBALISEL_COMBINER_HELPER_H
+#define LLVM_CODEGEN_GLOBALISEL_COMBINER_HELPER_H
+
+namespace llvm {
+
+class MachineIRBuilder;
+class MachineRegisterInfo;
+class MachineInstr;
+
+class CombinerHelper {
+  MachineIRBuilder &Builder;
+  MachineRegisterInfo &MRI;
+
+public:
+  CombinerHelper(MachineIRBuilder &B);
+
+  /// If \p MI is COPY, try to combine it.
+  /// Returns true if MI changed.
+  bool tryCombineCopy(MachineInstr &MI);
+
+  /// Try to transform \p MI by using all of the above
+  /// combine functions. Returns true if changed.
+  bool tryCombine(MachineInstr &MI);
+};
+} // namespace llvm
+
+#endif

include/llvm/CodeGen/GlobalISel/CombinerInfo.h

+//===- llvm/CodeGen/GlobalISel/CombinerInfo.h ------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// Interface for Targets to specify which operations are combined how and when.
+/// //
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_GLOBALISEL_COMBINER_INFO_H
+#define LLVM_CODEGEN_GLOBALISEL_COMBINER_INFO_H
+
+namespace llvm {
+
+class LegalizerInfo;
+class MachineInstr;
+class MachineIRBuilder;
+class MachineRegisterInfo;
+// Contains information relevant to enabling/disabling various combines for a
+// pass.
+class CombinerInfo {
+public:
+  CombinerInfo(bool AllowIllegalOps, bool ShouldLegalizeIllegal,
+               LegalizerInfo *LInfo)
+      : IllegalOpsAllowed(AllowIllegalOps),
+        LegalizeIllegalOps(ShouldLegalizeIllegal), LInfo(LInfo) {
+    assert(((AllowIllegalOps || !LegalizeIllegalOps) || LInfo) &&
+           "Expecting legalizerInfo when illegalops not allowed");
+  }
+  virtual ~CombinerInfo() = default;
+  /// If \p IllegalOpsAllowed is false, the CombinerHelper will make use of
+  /// the legalizerInfo to check for legality before each transformation.
+  bool IllegalOpsAllowed; // TODO: Make use of this.
+
+  /// If \p LegalizeIllegalOps is true, the Combiner will also legalize the
+  /// illegal ops that are created.
+  bool LegalizeIllegalOps; // TODO: Make use of this.
+  const LegalizerInfo *LInfo;
+  virtual bool combine(MachineInstr &MI, MachineIRBuilder &B) const = 0;
+};
+} // namespace llvm
+
+#endif

include/llvm/CodeGen/GlobalISel/MIPatternMatch.h

+//== ----- llvm/CodeGen/GlobalISel/MIPatternMatch.h --------------------- == //
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// Contains matchers for matching SSA Machine Instructions.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_GMIR_PATTERNMATCH_H
+#define LLVM_GMIR_PATTERNMATCH_H
+
+#include "llvm/ADT/APFloat.h"
+#include "llvm/ADT/APInt.h"
+#include "llvm/CodeGen/GlobalISel/Utils.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+
+namespace llvm {
+namespace MIPatternMatch {
+
+template <typename Reg, typename Pattern>
+bool match(Reg R, MachineRegisterInfo &MRI, Pattern &&P) {
+  return P.match(MRI, R);
+}
+
+// TODO: Extend for N use.
+template <typename SubPatternT> struct OneUse_match {
+  SubPatternT SubPat;
+  OneUse_match(const SubPatternT &SP) : SubPat(SP) {}
+
+  template <typename OpTy>
+  bool match(const MachineRegisterInfo &MRI, unsigned Reg) {
+    return MRI.hasOneUse(Reg) && SubPat.match(MRI, Reg);
+  }
+};
+
+template <typename SubPat>
+inline OneUse_match<SubPat> m_OneUse(const SubPat &SP) {
+  return SP;
+}
+
+struct ConstantMatch {
+  uint64_t &CR;
+  ConstantMatch(uint64_t &C) : CR(C) {}
+  bool match(const MachineRegisterInfo &MRI, unsigned Reg) {
+    if (auto MaybeCst = getConstantVRegVal(Reg, MRI)) {
+      CR = *MaybeCst;
+      return true;
+    }
+    return false;
+  }
+};
+
+ConstantMatch m_ICst(uint64_t &Cst) { return ConstantMatch(Cst); }
+
+// TODO: Rework this for different kinds of MachineOperand.
+// Currently assumes the Src for a match is a register.
+// We might want to support taking in some MachineOperands and call getReg on
+// that.
+
+struct operand_type_match {
+  bool match(const MachineRegisterInfo &MRI, unsigned Reg) { return true; }
+  bool match(const MachineRegisterInfo &MRI, MachineOperand *MO) {
+    return MO->isReg();
+  }
+};
+
+operand_type_match m_Reg() { return operand_type_match(); }
+
+/// Matching combinators.
+template <typename... Preds> struct And {
+  template <typename MatchSrc>
+  bool match(MachineRegisterInfo &MRI, MatchSrc &&src) {
+    return true;
+  }
+};
+
+template <typename Pred, typename... Preds>
+struct And<Pred, Preds...> : And<Preds...> {
+  Pred P;
+  And(Pred &&p, Preds &&... preds)
+      : And<Preds...>(std::forward<Preds>(preds)...), P(std::forward<Pred>(p)) {
+  }
+  template <typename MatchSrc>
+  bool match(MachineRegisterInfo &MRI, MatchSrc &&src) {
+    return P.match(MRI, src) && And<Preds...>::match(MRI, src);
+  }
+};
+
+template <typename... Preds> struct Or {
+  template <typename MatchSrc>
+  bool match(MachineRegisterInfo &MRI, MatchSrc &&src) {
+    return true;
+  }
+};
+
+template <typename Pred, typename... Preds>
+struct Or<Pred, Preds...> : Or<Preds...> {
+  Pred P;
+  Or(Pred &&p, Preds &&... preds)
+      : Or<Preds...>(std::forward<Preds>(preds)...), P(std::forward<Pred>(p)) {}
+  template <typename MatchSrc>
+  bool match(MachineRegisterInfo &MRI, MatchSrc &&src) {
+    return P.match(MRI, src) || Or<Preds...>::match(MRI, src);
+  }
+};
+
+template <typename... Preds> And<Preds...> m_all_of(Preds &&... preds) {
+  return And<Preds...>(std::forward<Preds>(preds)...);
+}
+
+template <typename... Preds> Or<Preds...> m_any_of(Preds &&... preds) {
+  return Or<Preds...>(std::forward<Preds>(preds)...);
+}
+
+template <typename BindTy> struct bind_helper {
+  static bool bind(const MachineRegisterInfo &MRI, BindTy &VR, BindTy &V) {
+    VR = V;
+    return true;
+  }
+};
+
+template <> struct bind_helper<MachineInstr *> {
+  static bool bind(const MachineRegisterInfo &MRI, MachineInstr *&MI,
+                   unsigned Reg) {
+    MI = MRI.getVRegDef(Reg);
+    if (MI)
+      return true;
+    return false;
+  }
+};
+
+template <> struct bind_helper<LLT> {
+  static bool bind(const MachineRegisterInfo &MRI, LLT &Ty, unsigned Reg) {
+    Ty = MRI.getType(Reg);
+    if (Ty.isValid())
+      return true;
+    return false;
+  }
+};
+
+template <typename Class> struct bind_ty {
+  Class &VR;
+
+  bind_ty(Class &V) : VR(V) {}
+
+  template <typename ITy> bool match(const MachineRegisterInfo &MRI, ITy &&V) {
+    return bind_helper<Class>::bind(MRI, VR, V);
+  }
+};
+
+inline bind_ty<unsigned> m_Reg(unsigned &R) { return R; }
+inline bind_ty<MachineInstr *> m_MInstr(MachineInstr *&MI) { return MI; }
+inline bind_ty<LLT> m_Type(LLT &Ty) { return Ty; }
+
+// General helper for all the binary generic MI such as G_ADD/G_SUB etc
+template <typename LHS_P, typename RHS_P, unsigned Opcode,
+          bool Commutable = false>
+struct BinaryOp_match {
+  LHS_P L;
+  RHS_P R;
+
+  BinaryOp_match(const LHS_P &LHS, const RHS_P &RHS) : L(LHS), R(RHS) {}
+  template <typename OpTy> bool match(MachineRegisterInfo &MRI, OpTy &&Op) {
+    MachineInstr *TmpMI;
+    if (match(Op, MRI, m_MInstr(TmpMI))) {
+      if (TmpMI->getOpcode() == Opcode && TmpMI->getNumOperands() == 3) {
+        return (L.match(MRI, TmpMI->getOperand(1).getReg()) &&
+                R.match(MRI, TmpMI->getOperand(2).getReg())) ||
+               (Commutable && (R.match(MRI, TmpMI->getOperand(1).getReg()) &&
+                               L.match(MRI, TmpMI->getOperand(2).getReg())));
+      }
+    }
+    return false;
+  }
+};
+
+template <typename LHS, typename RHS>
+inline BinaryOp_match<LHS, RHS, TargetOpcode::G_ADD, true>
+m_GAdd(const LHS &L, const RHS &R) {
+  return BinaryOp_match<LHS, RHS, TargetOpcode::G_ADD, true>(L, R);
+}
+
+template <typename LHS, typename RHS>
+inline BinaryOp_match<LHS, RHS, TargetOpcode::G_SUB> m_GSub(const LHS &L,
+                                                            const RHS &R) {
+  return BinaryOp_match<LHS, RHS, TargetOpcode::G_SUB>(L, R);
+}
+
+template <typename LHS, typename RHS>
+inline BinaryOp_match<LHS, RHS, TargetOpcode::G_MUL, true>
+m_GMul(const LHS &L, const RHS &R) {
+  return BinaryOp_match<LHS, RHS, TargetOpcode::G_MUL, true>(L, R);
+}
+
+template <typename LHS, typename RHS>
+inline BinaryOp_match<LHS, RHS, TargetOpcode::G_FADD> m_GFAdd(const LHS &L,
+                                                              const RHS &R) {
+  return BinaryOp_match<LHS, RHS, TargetOpcode::G_FADD>(L, R);
+}
+
+// Helper for unary instructions (G_[ZSA]EXT/G_TRUNC) etc
+template <typename SrcTy, unsigned Opcode> struct UnaryOp_match {
+  SrcTy L;
+
+  UnaryOp_match(const SrcTy &LHS) : L(LHS) {}
+  template <typename OpTy> bool match(MachineRegisterInfo &MRI, OpTy &&Op) {
+    MachineInstr *TmpMI;
+    if (match(Op, MRI, m_MInstr(TmpMI))) {
+      if (TmpMI->getOpcode() == Opcode && TmpMI->getNumOperands() == 2) {
+        return L.match(MRI, TmpMI->getOperand(1).getReg());
+      }
+    }
+    return false;
+  }
+};
+
+template <typename SrcTy>
+inline UnaryOp_match<SrcTy, TargetOpcode::G_ANYEXT>
+m_GAnyExt(const SrcTy &Src) {
+  return UnaryOp_match<SrcTy, TargetOpcode::G_ANYEXT>(Src);
+}
+
+template <typename SrcTy>
+inline UnaryOp_match<SrcTy, TargetOpcode::G_SEXT> m_GSExt(const SrcTy &Src) {
+  return UnaryOp_match<SrcTy, TargetOpcode::G_SEXT>(Src);
+}
+
+template <typename SrcTy>
+inline UnaryOp_match<SrcTy, TargetOpcode::G_ZEXT> m_GZExt(const SrcTy &Src) {
+  return UnaryOp_match<SrcTy, TargetOpcode::G_ZEXT>(Src);
+}
+
+template <typename SrcTy>
+inline UnaryOp_match<SrcTy, TargetOpcode::G_FPEXT> m_GFPExt(const SrcTy &Src) {
+  return UnaryOp_match<SrcTy, TargetOpcode::G_FPEXT>(Src);
+}
+
+template <typename SrcTy>
+inline UnaryOp_match<SrcTy, TargetOpcode::G_TRUNC> m_GTrunc(const SrcTy &Src) {
+  return UnaryOp_match<SrcTy, TargetOpcode::G_TRUNC>(Src);
+}
+
+template <typename SrcTy>
+inline UnaryOp_match<SrcTy, TargetOpcode::G_FPTRUNC>
+m_GFPTrunc(const SrcTy &Src) {
+  return UnaryOp_match<SrcTy, TargetOpcode::G_FPTRUNC>(Src);
+}
+
+template <typename SrcTy>
+inline UnaryOp_match<SrcTy, TargetOpcode::COPY> m_Copy(SrcTy &&Src) {
+  return UnaryOp_match<SrcTy, TargetOpcode::COPY>(std::forward<SrcTy>(Src));
+}
+
+// Helper for checking if a Reg is of specific type.
+struct CheckType {
+  LLT Ty;
+  CheckType(const LLT &Ty) : Ty(Ty) {}
+
+  bool match(MachineRegisterInfo &MRI, unsigned Reg) {
+    return MRI.getType(Reg) == Ty;
+  }
+};
+
+inline CheckType m_SpecificType(LLT Ty) { return Ty; }
+// TODO: Some contants like 0 / +0/-0
+// TODO Support GEP
+// TODO: Support SELECT/Comparisons
+// TODO: Intrinsics
+
+} // namespace GMIPatternMatch
+} // namespace llvm
+
+#endif

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

public:
   /// G_SUB sets \p Res to the sum of integer parameters \p Op0 and \p Op1,
   /// truncated to their width.
   ///
   /// \pre setBasicBlock or setMI must have been called.
   /// \pre \p Res, \p Op0 and \p Op1 must be generic virtual registers
   ///      with the same (scalar or vector) type).
   ///
   /// \return a MachineInstrBuilder for the newly created instruction.
+  template <typename DstTy, typename... UseArgsTy>
+  MachineInstrBuilder buildSub(DstTy &&Ty, UseArgsTy &&... UseArgs) {
+    unsigned Res = getDestFromArg(Ty);
+    return buildSub(Res, (getRegFromArg(UseArgs))...);
+  }
   MachineInstrBuilder buildSub(unsigned Res, unsigned Op0,
                                unsigned Op1);
 
   /// Build and insert \p Res = G_MUL \p Op0, \p Op1
   ///
   /// G_MUL sets \p Res to the sum of integer parameters \p Op0 and \p Op1,
   /// truncated to their width.
   ///
   /// \pre setBasicBlock or setMI must have been called.
   /// \pre \p Res, \p Op0 and \p Op1 must be generic virtual registers
   ///      with the same (scalar or vector) type).
   ///
   /// \return a MachineInstrBuilder for the newly created instruction.
+  template <typename DstTy, typename... UseArgsTy>
+  MachineInstrBuilder buildMul(DstTy &&Ty, UseArgsTy &&... UseArgs) {
+    unsigned Res = getDestFromArg(Ty);
+    return buildMul(Res, (getRegFromArg(UseArgs))...);
+  }
   MachineInstrBuilder buildMul(unsigned Res, unsigned Op0,
                                unsigned Op1);
 
   /// Build and insert \p Res = G_GEP \p Op0, \p Op1
   ///
   /// G_GEP adds \p Op1 bytes to the pointer specified by \p Op0,
   /// storing the resulting pointer in \p Res.
   ///
public:
   /// high bit of \p Op (i.e. 2s-complement sign extended).
   ///
   /// \pre setBasicBlock or setMI must have been called.
   /// \pre \p Res must be a generic virtual register with scalar or vector type.
   /// \pre \p Op must be a generic virtual register with scalar or vector type.
   /// \pre \p Op must be smaller than \p Res
   ///
   /// \return The newly created instruction.
+  template <typename DstType, typename ArgType>
+  MachineInstrBuilder buildSExt(DstType &&Res, ArgType &&Arg) {
+    return buildSExt(getDestFromArg(Res), getRegFromArg(Arg));
+  }
   MachineInstrBuilder buildSExt(unsigned Res, unsigned Op);
 
   /// Build and insert \p Res = G_ZEXT \p Op
   ///
   /// G_ZEXT produces a register of the specified width, with bits 0 to
   /// sizeof(\p Ty) * 8 set to \p Op. The remaining bits are 0. For a vector
   /// register, each element is extended individually.
   ///
   /// \pre setBasicBlock or setMI must have been called.
   /// \pre \p Res must be a generic virtual register with scalar or vector type.
   /// \pre \p Op must be a generic virtual register with scalar or vector type.
   /// \pre \p Op must be smaller than \p Res
   ///
   /// \return The newly created instruction.
+  template <typename DstType, typename ArgType>
+  MachineInstrBuilder buildZExt(DstType &&Res, ArgType &&Arg) {
+    return buildZExt(getDestFromArg(Res), getRegFromArg(Arg));
+  }
   MachineInstrBuilder buildZExt(unsigned Res, unsigned Op);
 
   /// Build and insert \p Res = G_SEXT \p Op, \p Res = G_TRUNC \p Op, or
   /// \p Res = COPY \p Op depending on the differing sizes of \p Res and \p Op.
   ///  ///
   /// \pre setBasicBlock or setMI must have been called.
   /// \pre \p Res must be a generic virtual register with scalar or vector type.
   /// \pre \p Op must be a generic virtual register with scalar or vector type.

include/llvm/CodeGen/GlobalISel/PreLegalizeCombiner.h

+//==  llvm/include/CodeGen/GlobalISel/PreLegalizeCombiner.h -----------------//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass runs before legalization.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_GLOBALISEL_PRELEGALIZE_GICOMBINER_H
+#define LLVM_CODEGEN_GLOBALISEL_PRELEGALIZE_GICOMBINER_H
+
+#include "llvm/CodeGen/GlobalISel/Combiner.h"
+#include "llvm/CodeGen/GlobalISel/CombinerInfo.h"
+#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
+#include "llvm/CodeGen/TargetPassConfig.h"
+
+namespace llvm {
+class MachineRegisterInfo;
+
+class PreLegalizeCombinerInfo : public CombinerInfo {
+public:
+  PreLegalizeCombinerInfo()
+      : CombinerInfo(/*AllowIllegalOps*/ true, /*ShouldLegalizeIllegal*/ false,
+                     /*LegalizerInfo*/ nullptr) {}
+  virtual bool combine(MachineInstr &MI, MachineIRBuilder &B) const override;
+};
+
+class PreLegalizeCombiner : public Combiner {
+  PreLegalizeCombinerInfo Info;
+public:
+  static char ID;
+
+  PreLegalizeCombiner() : Combiner(ID, Info) {}
+
+  StringRef getPassName() const override { return "PreLegalizeCombiner"; }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+};
+
+} // End namespace llvm.
+
+#endif // LLVM_CODEGEN_GLOBALISEL_PRELEGALIZE_GICOMBINER_H

include/llvm/InitializePasses.h

 void initializeFuncletLayoutPass(PassRegistry&);
 void initializeFunctionImportLegacyPassPass(PassRegistry&);
 void initializeGCMachineCodeAnalysisPass(PassRegistry&);
 void initializeGCModuleInfoPass(PassRegistry&);
 void initializeGCOVProfilerLegacyPassPass(PassRegistry&);
 void initializeGVNHoistLegacyPassPass(PassRegistry&);
 void initializeGVNLegacyPassPass(PassRegistry&);
 void initializeGVNSinkLegacyPassPass(PassRegistry&);
+void initializePreLegalizeCombinerPass(PassRegistry &);
 void initializeGlobalDCELegacyPassPass(PassRegistry&);
 void initializeGlobalMergePass(PassRegistry&);
 void initializeGlobalOptLegacyPassPass(PassRegistry&);
 void initializeGlobalSplitPass(PassRegistry&);
 void initializeGlobalsAAWrapperPassPass(PassRegistry&);
 void initializeGuardWideningLegacyPassPass(PassRegistry&);
 void initializeIPCPPass(PassRegistry&);
 void initializeIPSCCPLegacyPassPass(PassRegistry&);

lib/CodeGen/GlobalISel/CMakeLists.txt

 add_llvm_library(LLVMGlobalISel
         CallLowering.cpp
         GlobalISel.cpp
+        Combiner.cpp
+        CombinerHelper.cpp
+        PreLegalizeCombiner.cpp
         IRTranslator.cpp
         InstructionSelect.cpp
         InstructionSelector.cpp
         LegalizerHelper.cpp
         Legalizer.cpp
         LegalizerInfo.cpp
         Localizer.cpp
         MachineIRBuilder.cpp
         RegBankSelect.cpp
         RegisterBank.cpp
         RegisterBankInfo.cpp
         Utils.cpp
 
         DEPENDS
         intrinsics_gen
   )

lib/CodeGen/GlobalISel/Combiner.cpp

+//===-- lib/CodeGen/GlobalISel/GICombiner.cpp -----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file constains common code to combine machine functions at generic
+// level. //
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GlobalISel/Combiner.h"
+#include "llvm/CodeGen/GlobalISel/CombinerInfo.h"
+#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
+#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
+#include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/CodeGen/GlobalISel/Utils.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/Support/Debug.h"
+
+#define DEBUG_TYPE "gi-combiner"
+
+using namespace llvm;
+
+Combiner::Combiner(char ID, CombinerInfo &Info)
+    : MachineFunctionPass(ID), CInfo(Info) {
+  (void)this->TPC; // FIXME: Remove when used.
+}
+
+bool Combiner::runOnMachineFunction(MachineFunction &MF) {
+  // If the ISel pipeline failed, do not bother running that pass.
+  if (MF.getProperties().hasProperty(
+          MachineFunctionProperties::Property::FailedISel))
+    return false;
+
+  MRI = &MF.getRegInfo();
+  Builder.setMF(MF);
+
+  DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n');
+
+  MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
+
+  bool MFChanged = false;
+  bool Changed;
+
+  do {
+    // Collect all instructions. Do a post order traversal for basic blocks and
+    // insert with list bottom up, so while we pop_back_val, we'll traverse top
+    // down RPOT.
+    Changed = false;
+    GISelWorkList<512> WorkList;
+    for (MachineBasicBlock *MBB : post_order(&MF)) {
+      if (MBB->empty())
+        continue;
+      for (auto MII = MBB->rbegin(), MIE = MBB->rend(); MII != MIE;) {
+        MachineInstr *CurMI = &*MII;
+        ++MII;
+        // Erase dead insts before even adding to the list.
+        if (isTriviallyDead(*CurMI, *MRI)) {
+          DEBUG(dbgs() << *CurMI << "Is dead; erasing.\n");
+          CurMI->eraseFromParentAndMarkDBGValuesForRemoval();
+          continue;
+        }
+        WorkList.insert(CurMI);
+      }
+    }
+    // Main Loop. Process the instructions here.
+    while (!WorkList.empty()) {
+      MachineInstr *CurrInst = WorkList.pop_back_val();
+      DEBUG(dbgs() << "Try combining " << *CurrInst << "\n";);
+      Changed |= CInfo.combine(*CurrInst, Builder);
+    }
+    MFChanged |= Changed;
+  } while (Changed);
+
+  return MFChanged;
+}

lib/CodeGen/GlobalISel/CombinerHelper.cpp

+//== ---lib/CodeGen/GlobalISel/GICombinerHelper.cpp --------------------- == //
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+#include "llvm/CodeGen/GlobalISel/CombinerHelper.h"
+#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
+#include "llvm/CodeGen/GlobalISel/Utils.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+
+#define DEBUG_TYPE "gi-combine"
+
+using namespace llvm;
+
+CombinerHelper::CombinerHelper(MachineIRBuilder &B) :
+  Builder(B), MRI(Builder.getMF().getRegInfo()) {}
+
+bool CombinerHelper::tryCombineCopy(MachineInstr &MI) {
+  if (MI.getOpcode() != TargetOpcode::COPY)
+    return false;
+  unsigned DstReg = MI.getOperand(0).getReg();
+  unsigned SrcReg = MI.getOperand(1).getReg();
+  LLT DstTy = MRI.getType(DstReg);
+  LLT SrcTy = MRI.getType(SrcReg);
+  // Simple Copy Propagation.
+  // a(sx) = COPY b(sx) -> Replace all uses of a with b.
+  if (DstTy.isValid() && SrcTy.isValid() && DstTy == SrcTy) {
+    MI.eraseFromParent();
+    MRI.replaceRegWith(DstReg, SrcReg);
+    return true;
+  }
+  return false;
+}
+
+bool CombinerHelper::tryCombine(MachineInstr &MI) {
+  // Right now just do the above.
+  return tryCombineCopy(MI);
+}

lib/CodeGen/GlobalISel/GlobalISel.cpp

 #include "llvm/InitializePasses.h"
 #include "llvm/PassRegistry.h"
 
 using namespace llvm;
 
 void llvm::initializeGlobalISel(PassRegistry &Registry) {
   initializeIRTranslatorPass(Registry);
   initializeLegalizerPass(Registry);
+  initializePreLegalizeCombinerPass(Registry);
   initializeLocalizerPass(Registry);
   initializeRegBankSelectPass(Registry);
   initializeInstructionSelectPass(Registry);
 }

lib/CodeGen/GlobalISel/PreLegalizeCombiner.cpp

+//=== lib/CodeGen/GlobalISel/PreLegalizeCombiner.cpp -------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass does combining of machine instructions at the generic MI level,
+// before the legalizer.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GlobalISel/PreLegalizeCombiner.h"
+#include "llvm/CodeGen/GlobalISel/Combiner.h"
+#include "llvm/CodeGen/GlobalISel/CombinerHelper.h"
+#include "llvm/CodeGen/GlobalISel/Utils.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/Support/Debug.h"
+
+#define DEBUG_TYPE "prelegalize-combiner"
+
+using namespace llvm;
+
+static cl::opt<bool> EnablePreLegalizeCombiner(
+    "enable-prelegalize-gi-combiner", cl::Hidden,
+    cl::desc("Enable the prelegalize machine instruction combiner"),
+    cl::init(true));
+
+char PreLegalizeCombiner::ID = 0;
+INITIALIZE_PASS_BEGIN(PreLegalizeCombiner, DEBUG_TYPE,
+                      "Combine generic instructions before legalization", false,
+                      false)
+INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
+INITIALIZE_PASS_END(PreLegalizeCombiner, DEBUG_TYPE,
+                    "Combine generic instructions before legalization", false,
+                    false)
+
+void PreLegalizeCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<TargetPassConfig>();
+  MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+bool PreLegalizeCombiner::runOnMachineFunction(MachineFunction &MF) {
+  if (!EnablePreLegalizeCombiner) {
+    DEBUG(dbgs() << "PreLegalizeCombiner is disabled\n");
+    return false;
+  }
+  TPC = &getAnalysis<TargetPassConfig>();
+  return Combiner::runOnMachineFunction(MF);
+}
+
+bool PreLegalizeCombinerInfo::combine(MachineInstr &MI, MachineIRBuilder &B) const {
+  CombinerHelper Helper(B);
+  // For now try all combines in the combiner helper.
+  return Helper.tryCombine(MI);
+}

test/CodeGen/AArch64/GlobalISel/combine-copy.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -O0 -run-pass=prelegalize-combiner -global-isel %s -o - | FileCheck %s
+
+--- |
+  target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+  target triple = "aarch64--"
+  define void @test_copy_propagation() {
+  entry:
+    ret void
+  }
+...
+
+---
+name:            test_copy_propagation
+body: |
+  bb.0.entry:
+    liveins: %x0, %x1, %x2, %x3
+
+    ; CHECK-LABEL: name: test_copy_propagation
+    ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY %x0
+    ; CHECK: %x0 = COPY [[COPY]](s64)
+    %0:_(s64) = COPY %x0
+    %1:_(s64) = COPY %0
+    %2:_(s64) = COPY %1
+    %x0 = COPY %2
+...
+

unittests/CodeGen/GlobalISel/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
-  GlobalISel
+  ${LLVM_TARGETS_TO_BUILD}
   CodeGen
+  Core
+  GlobalISel
+  MC
+  MIRParser
+  Support
+  Target
   )
 
 add_llvm_unittest(GlobalISelTests
         LegalizerInfoTest.cpp
+        PatternMatchTest.cpp
         )

unittests/CodeGen/GlobalISel/PatternMatchTest.cpp

+//===- PatternMatchTest.cpp -----------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
+#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
+#include "llvm/CodeGen/GlobalISel/Utils.h"
+#include "llvm/CodeGen/MIRParser/MIRParser.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/TargetFrameLowering.h"
+#include "llvm/CodeGen/TargetInstrInfo.h"
+#include "llvm/CodeGen/TargetLowering.h"
+#include "llvm/CodeGen/TargetSubtargetInfo.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetOptions.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+using namespace MIPatternMatch;
+
+namespace {
+
+void initLLVM() {
+  InitializeAllTargets();
+  InitializeAllTargetMCs();
+  InitializeAllAsmPrinters();
+  InitializeAllAsmParsers();
+
+  PassRegistry *Registry = PassRegistry::getPassRegistry();
+  initializeCore(*Registry);
+  initializeCodeGen(*Registry);
+}
+
+/// Create a TargetMachine. As we lack a dedicated always available target for
+/// unittests, we go for "AArch64".
+std::unique_ptr<TargetMachine> createTargetMachine() {
+  Triple TargetTriple("aarch64--");
+  std::string Error;
+  const Target *T = TargetRegistry::lookupTarget("", TargetTriple, Error);
+  if (!T)
+    return nullptr;
+
+  TargetOptions Options;
+  return std::unique_ptr<TargetMachine>(T->createTargetMachine(
+      "AArch64", "", "", Options, None, None, CodeGenOpt::Aggressive));
+}
+
+std::unique_ptr<Module> parseMIR(LLVMContext &Context,
+                                 std::unique_ptr<MIRParser> &MIR,
+                                 const TargetMachine &TM, StringRef MIRCode,
+                                 const char *FuncName, MachineModuleInfo &MMI) {
+  SMDiagnostic Diagnostic;
+  std::unique_ptr<MemoryBuffer> MBuffer = MemoryBuffer::getMemBuffer(MIRCode);
+  MIR = createMIRParser(std::move(MBuffer), Context);
+  if (!MIR)
+    return nullptr;
+
+  std::unique_ptr<Module> M = MIR->parseIRModule();
+  if (!M)
+    return nullptr;
+
+  M->setDataLayout(TM.createDataLayout());
+
+  if (MIR->parseMachineFunctions(*M, MMI))
+    return nullptr;
+
+  return M;
+}
+
+std::pair<std::unique_ptr<Module>, std::unique_ptr<MachineModuleInfo>>
+createDummyModule(LLVMContext &Context, const TargetMachine &TM,
+                  StringRef MIRFunc) {
+  SmallString<512> S;
+  StringRef MIRString = (Twine(R"MIR(
+---
+...
+name: func
+registers:
+  - { id: 0, class: _ }
+  - { id: 1, class: _ }
+  - { id: 2, class: _ }
+  - { id: 3, class: _ }
+body: |
+  bb.1:
+    %0(s64) = COPY %x0
+    %1(s64) = COPY %x1
+    %2(s64) = COPY %x2
+)MIR") + Twine(MIRFunc) + Twine("...\n"))
+                            .toNullTerminatedStringRef(S);
+  std::unique_ptr<MIRParser> MIR;
+  auto MMI = make_unique<MachineModuleInfo>(&TM);
+  std::unique_ptr<Module> M =
+      parseMIR(Context, MIR, TM, MIRString, "func", *MMI);
+  return make_pair(std::move(M), std::move(MMI));
+}
+
+static MachineFunction *getMFFromMMI(const Module *M,
+                                     const MachineModuleInfo *MMI) {
+  Function *F = M->getFunction("func");
+  auto *MF = MMI->getMachineFunction(*F);
+  return MF;
+}
+
+static void collectCopies(SmallVectorImpl<unsigned> &Copies,
+                          MachineFunction *MF) {
+  for (auto &MBB : *MF)
+    for (MachineInstr &MI : MBB) {
+      if (MI.getOpcode() == TargetOpcode::COPY)
+        Copies.push_back(MI.getOperand(0).getReg());
+    }
+}
+
+TEST(PatternMatchInstr, MatchIntConstant) {
+  LLVMContext Context;
+  std::unique_ptr<TargetMachine> TM = createTargetMachine();
+  if (!TM)
+    return;
+  auto ModuleMMIPair = createDummyModule(Context, *TM, "");
+  MachineFunction *MF =
+      getMFFromMMI(ModuleMMIPair.first.get(), ModuleMMIPair.second.get());
+  SmallVector<unsigned, 4> Copies;
+  collectCopies(Copies, MF);
+  MachineBasicBlock *EntryMBB = &*MF->begin();
+  MachineIRBuilder B(*MF);
+  MachineRegisterInfo &MRI = MF->getRegInfo();
+  B.setInsertPt(*EntryMBB, EntryMBB->end());
+  auto MIBCst = B.buildConstant(LLT::scalar(64), 42);
+  uint64_t Cst;
+  bool match = match(MIBCst->getOperand(0).getReg(), MRI, m_ICst(Cst));
+  ASSERT_TRUE(match);
+  ASSERT_EQ(Cst, (uint64_t)42);
+}
+
+TEST(PatternMatchInstr, MatchBinaryOp) {
+  LLVMContext Context;
+  std::unique_ptr<TargetMachine> TM = createTargetMachine();
+  if (!TM)
+    return;
+  auto ModuleMMIPair = createDummyModule(Context, *TM, "");
+  MachineFunction *MF =
+      getMFFromMMI(ModuleMMIPair.first.get(), ModuleMMIPair.second.get());
+  SmallVector<unsigned, 4> Copies;
+  collectCopies(Copies, MF);
+  MachineBasicBlock *EntryMBB = &*MF->begin();
+  MachineIRBuilder B(*MF);
+  MachineRegisterInfo &MRI = MF->getRegInfo();
+  B.setInsertPt(*EntryMBB, EntryMBB->end());
+  LLT s64 = LLT::scalar(64);
+  auto MIBAdd = B.buildAdd(s64, Copies[0], Copies[1]);
+  // Test case for no bind.
+  bool match =
+      match(MIBAdd->getOperand(0).getReg(), MRI, m_GAdd(m_Reg(), m_Reg()));
+  ASSERT_TRUE(match);
+  unsigned Src0, Src1, Src2;
+  match = match(MIBAdd->getOperand(0).getReg(), MRI,
+                   m_GAdd(m_Reg(Src0), m_Reg(Src1)));
+  ASSERT_TRUE(match);
+  ASSERT_EQ(Src0, Copies[0]);
+  ASSERT_EQ(Src1, Copies[1]);
+
+  // Build MUL(ADD %0, %1), %2
+  auto MIBMul = B.buildMul(s64, MIBAdd, Copies[2]);
+
+  // Try to match MUL.
+  match = match(MIBMul->getOperand(0).getReg(), MRI,
+                   m_GMul(m_Reg(Src0), m_Reg(Src1)));
+  ASSERT_TRUE(match);
+  ASSERT_EQ(Src0, MIBAdd->getOperand(0).getReg());
+  ASSERT_EQ(Src1, Copies[2]);
+
+  // Try to match MUL(ADD)
+  match = match(MIBMul->getOperand(0).getReg(), MRI,
+                   m_GMul(m_GAdd(m_Reg(Src0), m_Reg(Src1)), m_Reg(Src2)));
+  ASSERT_TRUE(match);
+  ASSERT_EQ(Src0, Copies[0]);
+  ASSERT_EQ(Src1, Copies[1]);
+  ASSERT_EQ(Src2, Copies[2]);
+
+  // Test Commutativity.
+  auto MIBMul2 = B.buildMul(s64, Copies[0], B.buildConstant(s64, 42));
+  // Try to match MUL(Cst, Reg) on src of MUL(Reg, Cst) to validate
+  // commutativity.
+  uint64_t Cst;
+  match = match(MIBMul2->getOperand(0).getReg(), MRI,
+                   m_GMul(m_ICst(Cst), m_Reg(Src0)));
+  ASSERT_TRUE(match);
+  ASSERT_EQ(Cst, (uint64_t)42);
+  ASSERT_EQ(Src0, Copies[0]);
+
+  // Make sure commutative doesn't work with something like SUB.
+  auto MIBSub = B.buildSub(s64, Copies[0], B.buildConstant(s64, 42));
+  match = match(MIBSub->getOperand(0).getReg(), MRI,
+                   m_GSub(m_ICst(Cst), m_Reg(Src0)));
+  ASSERT_FALSE(match);
+}
+
+TEST(PatternMatchInstr, MatchExtendsTrunc) {
+  LLVMContext Context;
+  std::unique_ptr<TargetMachine> TM = createTargetMachine();
+  if (!TM)
+    return;
+  auto ModuleMMIPair = createDummyModule(Context, *TM, "");
+  MachineFunction *MF =
+      getMFFromMMI(ModuleMMIPair.first.get(), ModuleMMIPair.second.get());
+  SmallVector<unsigned, 4> Copies;
+  collectCopies(Copies, MF);
+  MachineBasicBlock *EntryMBB = &*MF->begin();
+  MachineIRBuilder B(*MF);
+  MachineRegisterInfo &MRI = MF->getRegInfo();
+  B.setInsertPt(*EntryMBB, EntryMBB->end());
+  LLT s64 = LLT::scalar(64);
+  LLT s32 = LLT::scalar(32);
+
+  auto MIBTrunc = B.buildTrunc(s32, Copies[0]);
+  auto MIBAExt = B.buildAnyExt(s64, MIBTrunc);
+  auto MIBZExt = B.buildZExt(s64, MIBTrunc);
+  auto MIBSExt = B.buildSExt(s64, MIBTrunc);
+  unsigned Src0;
+  bool match =
+      match(MIBTrunc->getOperand(0).getReg(), MRI, m_GTrunc(m_Reg(Src0)));
+  ASSERT_TRUE(match);
+  ASSERT_EQ(Src0, Copies[0]);
+  match =
+      match(MIBAExt->getOperand(0).getReg(), MRI, m_GAnyExt(m_Reg(Src0)));
+  ASSERT_TRUE(match);
+  ASSERT_EQ(Src0, MIBTrunc->getOperand(0).getReg());
+
+  match = match(MIBSExt->getOperand(0).getReg(), MRI, m_GSExt(m_Reg(Src0)));
+  ASSERT_TRUE(match);
+  ASSERT_EQ(Src0, MIBTrunc->getOperand(0).getReg());
+
+  match = match(MIBZExt->getOperand(0).getReg(), MRI, m_GZExt(m_Reg(Src0)));
+  ASSERT_TRUE(match);
+  ASSERT_EQ(Src0, MIBTrunc->getOperand(0).getReg());
+
+  // Match ext(trunc src)
+  match = match(MIBAExt->getOperand(0).getReg(), MRI,
+                   m_GAnyExt(m_GTrunc(m_Reg(Src0))));
+  ASSERT_TRUE(match);
+  ASSERT_EQ(Src0, Copies[0]);
+
+  match = match(MIBSExt->getOperand(0).getReg(), MRI,
+                   m_GSExt(m_GTrunc(m_Reg(Src0))));
+  ASSERT_TRUE(match);
+  ASSERT_EQ(Src0, Copies[0]);
+
+  match = match(MIBZExt->getOperand(0).getReg(), MRI,
+                   m_GZExt(m_GTrunc(m_Reg(Src0))));
+  ASSERT_TRUE(match);
+  ASSERT_EQ(Src0, Copies[0]);
+}
+
+TEST(PatternMatchInstr, MatchSpecificType) {
+  LLVMContext Context;
+  std::unique_ptr<TargetMachine> TM = createTargetMachine();
+  if (!TM)
+    return;
+  auto ModuleMMIPair = createDummyModule(Context, *TM, "");
+  MachineFunction *MF =
+      getMFFromMMI(ModuleMMIPair.first.get(), ModuleMMIPair.second.get());
+  SmallVector<unsigned, 4> Copies;
+  collectCopies(Copies, MF);
+  MachineBasicBlock *EntryMBB = &*MF->begin();
+  MachineIRBuilder B(*MF);
+  MachineRegisterInfo &MRI = MF->getRegInfo();
+  B.setInsertPt(*EntryMBB, EntryMBB->end());
+  LLT s64 = LLT::scalar(64);
+  LLT s32 = LLT::scalar(32);
+  auto MIBAdd = B.buildAdd(s64, Copies[0], Copies[1]);
+
+  // Try to match a 64bit add.
+  ASSERT_FALSE(match(MIBAdd->getOperand(0).getReg(), MRI,
+                        m_GAdd(m_SpecificType(s32), m_Reg())));
+  ASSERT_TRUE(match(MIBAdd->getOperand(0).getReg(), MRI,
+                       m_GAdd(m_SpecificType(s64), m_Reg())));
+}
+
+TEST(PatternMatchInstr, MatchCombinators) {
+  LLVMContext Context;
+  std::unique_ptr<TargetMachine> TM = createTargetMachine();
+  if (!TM)
+    return;
+  auto ModuleMMIPair = createDummyModule(Context, *TM, "");
+  MachineFunction *MF =
+      getMFFromMMI(ModuleMMIPair.first.get(), ModuleMMIPair.second.get());
+  SmallVector<unsigned, 4> Copies;
+  collectCopies(Copies, MF);
+  MachineBasicBlock *EntryMBB = &*MF->begin();
+  MachineIRBuilder B(*MF);
+  MachineRegisterInfo &MRI = MF->getRegInfo();
+  B.setInsertPt(*EntryMBB, EntryMBB->end());
+  LLT s64 = LLT::scalar(64);
+  LLT s32 = LLT::scalar(32);
+  auto MIBAdd = B.buildAdd(s64, Copies[0], Copies[1]);
+  unsigned Src0, Src1;
+  bool match =
+      match(MIBAdd->getOperand(0).getReg(), MRI,
+               m_all_of(m_SpecificType(s64), m_GAdd(m_Reg(Src0), m_Reg(Src1))));
+  ASSERT_TRUE(match);
+  ASSERT_EQ(Src0, Copies[0]);
+  ASSERT_EQ(Src1, Copies[1]);
+  // Check for s32 (which should fail).
+  match =
+      match(MIBAdd->getOperand(0).getReg(), MRI,
+               m_all_of(m_SpecificType(s32), m_GAdd(m_Reg(Src0), m_Reg(Src1))));
+  ASSERT_FALSE(match);
+  match =
+      match(MIBAdd->getOperand(0).getReg(), MRI,
+               m_any_of(m_SpecificType(s32), m_GAdd(m_Reg(Src0), m_Reg(Src1))));
+  ASSERT_TRUE(match);
+  ASSERT_EQ(Src0, Copies[0]);
+  ASSERT_EQ(Src1, Copies[1]);
+}
+} // namespace
+
+int main(int argc, char **argv) {
+  ::testing::InitGoogleTest(&argc, argv);
+  initLLVM();
+  return RUN_ALL_TESTS();
+}