[GISel]: Add support for CSEing continuously during GISel passes

[aditya_nandakumar]

Summary

This patch adds support to continuously CSE instructions during each of the GISel passes. It consists of a GISelCSEInfo analysis pass that can be used by the CSEMIRBuilder.

This patch also includes some changes to MachineIRBuilderBase (which is separated out here - https://reviews.llvm.org/D52131). I have enabled it in the legalizer for now. I've also only updated AArch64 for the API and test changes - I'll update the rest post feedback.

I measured some off tree benchmarks for compile time and I didn't notice too much of a compile time regression (<1%). I'll try to get some numbers for AArch64 with llvm-test-suite.

Looking forward to your feedback.

[dsanders]

I haven't gone through the patch in full but I have a few comments based on the discussion we had today

include/llvm/CodeGen/GlobalISel/CSEInfo.h

42

I'm not keen on using recordNewInstruction to report changes to existing instructions. We should have another interface for mutations

lib/CodeGen/GlobalISel/CSEInfo.cpp

37

It seems that this persists until GISelCSEInfo is destroyed which could be many passes from now. Effectively this imposes behaviour changes on subsequent passes that may not be expecting it.

In the case where a subsequent pass gets it but doesn't intend to preserve it, the subsequent pass is going to pay the cost of the maintenance unnecessarily. In the case where a subsequent pass gets it and intends to preserve it but needs to do so carefully, it's going to be fighting against a default maintenance method that was installed without its knowledge.

Another problem is that GISelCSEInfo doesn't have exclusive ownership of the MF delegate. If a pass wants to use it, this is going to clobber the one they set up.

In summary, I think passes need to install their own strategy to maintain it. This could be the standard one but I think they need to choose it.

[aemerson]

Thanks for working on this. Apart from Daniel's suggestion, I have a few more comments but haven't done an in depth analysis of the memory costs/algorithmic properties.

As for performance data, it would be good to have this enabled optionally in the IRTranslator as well. We can compare the effect on compile time and code size in just IRT vs IRT + Legalizer. I would hope we can get a speedup.

include/llvm/CodeGen/GlobalISel/CSEInfo.h

66

Document what this is for?

include/llvm/CodeGen/GlobalISel/CSEMIRBuilder.h

49

We should assert here the assumption that the iterators from the same block.

51

'count' is unused here.

64

Typo 'to'

226

There's a fair amount of code duplication here. This might get a bit religious depending on your philosophy w.r.t macros, but we could factor out most of the code from the first part of the builder methods. I'm not going to say it should definitely be done, I think it's just about worth it though.

lib/CodeGen/GlobalISel/CSEInfo.cpp

271

Should move this as a helper in LLT, something like serializeData()? That way we don't have to have internal bit layout detail in a user of LLT.

[aditya_nandakumar]

Addressed feedback from Daniel and Amara.
Added a RAIIDelegateInstaller that can be used to explicitly install and uninstall the CSEInfo delegate in the legalizer.

[aditya_nandakumar]

include/llvm/CodeGen/GlobalISel/CSEInfo.h

42

I can in a separate patch change the API of MachineIRBuilder to reflect the different kinds of recordings that we may need and then update this patch to use that.

include/llvm/CodeGen/GlobalISel/CSEMIRBuilder.h

51

This was used to profile by printing which domination algorithm would be preferable - I updated it now.

226

Thanks. I also want to avoid this code duplication. For now, I've kept it simple, but it's definitely something that needs to be addressed here using whatever mechanism.

lib/CodeGen/GlobalISel/CSEInfo.cpp

37

I've made this explicit now - the passes can use the RAIIDelegateInstaller now to set this up.

[aditya_nandakumar]

Rebased, and updated to the new MachineIRBuilder interface.
By default the CSE is enabled during IRTranslator and Legalizer now (disable with -enable-cse-in-legalizer/irtranslator=0).
Added a helper class called GISelObserverWrapper which provides a single observer that can call several observers which can be used to register as the delegate to MachineFunction.
I've also updated most tests (except some tests where it's not obvious what the test is doing where CSE is disabled).

[kristof.beyls]

In D52803#1349005, @aditya_nandakumar wrote:

By default the CSE is enabled during IRTranslator and Legalizer now (disable with -enable-cse-in-legalizer/irtranslator=0).

I naively wonder if unconditionally enabling a CSE optimization even at -O0 is going to lead to a poorer debug experience in some cases?

I've also updated most tests (except some tests where it's not obvious what the test is doing where CSE is disabled).

If CSE should be enabled by default, I guess that we'll need to figure out what the tests are supposed to be doing so that there aren't many tests mainly testing non-default behaviour?

[aditya_nandakumar]

In D52803#1349373, @kristof.beyls wrote:

In D52803#1349005, @aditya_nandakumar wrote:

By default the CSE is enabled during IRTranslator and Legalizer now (disable with -enable-cse-in-legalizer/irtranslator=0).

I naively wonder if unconditionally enabling a CSE optimization even at -O0 is going to lead to a poorer debug experience in some cases?

Yes this is definitely an important question. I only enabled them by default because I wanted to test that CSE works with the pipeline. I can definitely disable CSE for O0 for each of the passes and add some more tests (besides making the unit test more comprehensive) that make sure CSE works in pipeline.

I've also updated most tests (except some tests where it's not obvious what the test is doing where CSE is disabled).

If CSE should be enabled by default, I guess that we'll need to figure out what the tests are supposed to be doing so that there aren't many tests mainly testing non-default behaviour?

I updated most of the tests that just run a single GISel pass. I was hesitant to update the tests that take it all the way to assembly (that were not auto generated).

[aditya_nandakumar]

Updated to add a CSEConfig class that describes what instructions should be CSEd.
Additionally, updated IRTranslator and Legalizer to only perform CSE for G_CONSTANTS for -O0.

[aemerson]

In D52803#1349373, @kristof.beyls wrote:

In D52803#1349005, @aditya_nandakumar wrote:

By default the CSE is enabled during IRTranslator and Legalizer now (disable with -enable-cse-in-legalizer/irtranslator=0).

I naively wonder if unconditionally enabling a CSE optimization even at -O0 is going to lead to a poorer debug experience in some cases?

This is a good point, so I think that if we enable it for -O0 it should only be for constants.

I've also updated most tests (except some tests where it's not obvious what the test is doing where CSE is disabled).

If CSE should be enabled by default, I guess that we'll need to figure out what the tests are supposed to be doing so that there aren't many tests mainly testing non-default behaviour?

After some offline discussion, we've decided to not enable this at all at -O0 due to some minor compile time and code size regressions. The CSE here introduces copies as it must define a register when asked to, but at -O0 we don't do the copy elision and so compile time isn't improved, and it likely affects later passes like immediate selection. Overall, LGTM for enabling at -O1 or higher.

[aditya_nandakumar]

Rebased, updated based on feedback.
With this change, now they're disabled by default (for O0).

[aditya_nandakumar]

Submitted in r351283.

include/llvm/CodeGen/GlobalISel/CSEInfo.h

+//===- llvm/CodeGen/GlobalISel/CSEInfo.h ------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// Provides analysis for continuously CSEing during GISel passes.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CODEGEN_GLOBALISEL_CSEINFO_H
+#define LLVM_CODEGEN_GLOBALISEL_CSEINFO_H
+
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
+#include "llvm/CodeGen/GlobalISel/Utils.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Allocator.h"
+
+namespace llvm {
+
+/// A class that wraps MachineInstrs and derives from FoldingSetNode in order to
+/// be uniqued in a CSEMap. The tradeoff here is extra memory allocations for
+/// UniqueMachineInstr vs making MachineInstr bigger.
+class UniqueMachineInstr : public FoldingSetNode {
+  friend class GISelCSEInfo;
+  const MachineInstr *MI;
+  explicit UniqueMachineInstr(const MachineInstr *MI) : MI(MI) {}
+
+public:
+  void Profile(FoldingSetNodeID &ID);
+};
+
+/// The CSE Analysis object.
+/// This installs itself as a delegate to the MachineFunction to track
+/// new instructions as well as deletions. It however will not be able to
+/// track instruction mutations. In such cases, recordNewInstruction should be
+/// called (for eg inside MachineIRBuilder::recordInsertion).
+/// Also because of how just the instruction can be inserted without adding any operands
+/// to the instruction, instructions are uniqued and inserted lazily. CSEInfo should assert
+/// when trying to enter an incomplete instruction into the CSEMap.
+/// There is Opcode level granularity on which instructions can be CSE'd and for now,
+/// only Generic instructions are CSEable.
+class GISelCSEInfo : public MachineFunction::Delegate {
+  // Make it accessible only to CSEMIRBuilder.
+  friend class CSEMIRBuilder;
+
+  BumpPtrAllocator UniqueInstrAllocator;
+  FoldingSet<UniqueMachineInstr> CSEMap;
+  MachineRegisterInfo *MRI = nullptr;
+  MachineFunction *MF = nullptr;
+  using ShouldCSECallBackTy = std::function<bool(unsigned)>;
+  ShouldCSECallBackTy ShouldCSEFn;
+
+  /// Keep a cache of UniqueInstrs for each MachineInstr. In GISel,
+  /// often instructions are mutated (while their ID has completely changed).
+  /// Whenever mutation happens, invalidate the UniqueMachineInstr for the
+  /// MachineInstr
+  DenseMap<const MachineInstr *, UniqueMachineInstr *> InstrMapping;
+
+  GISelWorkList<8> TemporaryInsts;
+
+  // Only used in asserts.
+  DenseMap<unsigned, unsigned> OpcodeHitTable;
+
+  bool isUniqueMachineInstValid(const UniqueMachineInstr &UMI) const;
+
+  void invalidateUniqueMachineInstr(UniqueMachineInstr *UMI);
+
+  UniqueMachineInstr *getNodeIfExists(FoldingSetNodeID &ID,
+                                      MachineBasicBlock *MBB, void *&InsertPos);
+
+  /// Allocate and construct a new UniqueMachineInstr for MI and return.
+  UniqueMachineInstr *getUniqueInstrForMI(const MachineInstr *MI);
+
+  void insertNode(UniqueMachineInstr *UMI, void *InsertPos = nullptr);
+
+  void MF_HandleInsertion(const MachineInstr &MI) override;
+  void MF_HandleRemoval(const MachineInstr &MI) override;
+
+  /// Get the MachineInstr(Unique) if it exists already in the CSEMap and the
+  /// same MachineBasicBlock.
+  MachineInstr *getMachineInstrIfExists(FoldingSetNodeID &ID,
+                                        MachineBasicBlock *MBB,
+                                        void *&InsertPos);
+
+  /// Use this method to allocate a new UniqueMachineInstr for MI and insert it
+  /// into the CSEMap. MI should return true for shouldCSE(MI->getOpcode())
+  void insertInstr(MachineInstr *MI, void *InsertPos = nullptr);
+public:
+  GISelCSEInfo() = default;
+
+  virtual ~GISelCSEInfo();
+
+  void setMF(MachineFunction &MF);
+
+
+  /// Records a newly created inst in a list and lazily insert it to the CSEMap.
+  /// Sometimes, this method might be called with a partially constructed
+  /// MachineInstr,
+  //  (right after BuildMI without adding any operands) - and in such cases,
+  //  defer the hashing of the instruction to a later stage.
+  void recordNewInstruction(MachineInstr *MI);
+
+  /// Use this callback to inform CSE about a newly fully created instruction.
+  void handleRecordedInst(MachineInstr *MI);
+
+  /// Use this callback to insert all the recorded instructions. At this point,
+  /// all of these insts need to be fully constructed and should not be missing
+  /// any operands.
+  void handleRecordedInsts();
+
+  /// Remove this inst from the CSE map. If this inst has not been inserted yet,
+  /// it will be removed from the Tempinsts list if it exists.
+  void handleRemoveInst(MachineInstr *MI);
+
+  void releaseMemory();
+
+  void setShouldCSECallback(ShouldCSECallBackTy Fn) {
+    ShouldCSEFn = std::move(Fn);
+  }
+
+  bool shouldCSE(unsigned Opc);
+
+  void analyze(MachineFunction &MF);
+
+  void countOpcodeHit(unsigned Opc);
+
+  void print();
+};
+
+class TargetRegisterClass;
+class RegisterBank;
+
+// Simple builder class to easily profile properties about MIs.
+class GISelInstProfileBuilder {
+  FoldingSetNodeID &ID;
+  const MachineRegisterInfo &MRI;
+
+public:
+  GISelInstProfileBuilder(FoldingSetNodeID &ID, const MachineRegisterInfo &MRI)
+      : ID(ID), MRI(MRI) {}
+  // Profiling methods.
+  const GISelInstProfileBuilder &addNodeIDOpcode(unsigned Opc) const;
+  const GISelInstProfileBuilder &addNodeIDRegType(const LLT &Ty) const;
+  const GISelInstProfileBuilder &addNodeIDRegType(const unsigned) const;
+
+  const GISelInstProfileBuilder &
+  addNodeIDRegType(const TargetRegisterClass *RC) const;
+  const GISelInstProfileBuilder &addNodeIDRegType(const RegisterBank *RB) const;
+
+  const GISelInstProfileBuilder &addNodeIDRegNum(unsigned Reg) const;
+
+  const GISelInstProfileBuilder &addNodeIDImmediate(int64_t Imm) const;
+  const GISelInstProfileBuilder &
+  addNodeIDMBB(const MachineBasicBlock *MBB) const;
+
+  const GISelInstProfileBuilder &
+  addNodeIDMachineOperand(const MachineOperand &MO) const;
+
+  const GISelInstProfileBuilder &addNodeID(const MachineInstr *MI) const;
+};
+
+/// The actual analysis pass wrapper.
+class GISelCSEAnalysisWrapperPass : public MachineFunctionPass {
+  GISelCSEInfo Info;
+
+public:
+  static char ID;
+  GISelCSEAnalysisWrapperPass() : MachineFunctionPass(ID) {
+    initializeGISelCSEAnalysisWrapperPassPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+  GISelCSEInfo &getCSEInfo() { return Info; }
+  const GISelCSEInfo &getCSEInfo() const { return Info; }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+  void releaseMemory() override { Info.releaseMemory(); }
+};
+
+} // namespace llvm
+
+#endif

include/llvm/CodeGen/GlobalISel/CSEMIRBuilder.h

+//===-- llvm/CodeGen/GlobalISel/CSEMIRBuilder.h  --*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This file implements a version of MachineIRBuilder which CSEs insts within
+/// a MachineBasicBlock.
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CODEGEN_GLOBALISEL_CSEMIRBUILDER_H
+#define LLVM_CODEGEN_GLOBALISEL_CSEMIRBUILDER_H
+
+#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
+#include "llvm/CodeGen/GlobalISel/Utils.h"
+
+namespace llvm {
+
+/// Defines a builder that does CSE of MachineInstructions using GISelCSEInfo.
+/// Eg usage.
+///
+///
+///  GISelCSEInfo *Info = &getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEInfo();
+///  CSEMIRBuilder CB(Builder.getState()); // Create CB.
+///  CB.setCSEInfo(Info); // If not already done.
+///  auto A = CB.buildConstant(s32, 42);
+///  auto B = CB.buildConstant(s32, 42);
+///  assert(A == B);
+///  unsigned CReg = MRI.createGenericVirtualRegister(s32);
+///  auto C = CB.buildConstant(CReg, 42); // Explicitly passing in a register would
+///  materialize a copy if possible.
+///  CSEMIRBuilder also does trivial constant folding for binary ops.
+class CSEMIRBuilder : public FoldableInstructionsBuilder<CSEMIRBuilder> {
+
+  /// Returns true if A dominates B (within the same basic block).
+  /// Both iterators must be in the same basic block.
+  //
+  // TODO: Another approach for checking dominance is having two iterators and
+  // making them go towards each other until they meet or reach begin/end. Which
+  // approach is better? Should this even change dynamically? For G_CONSTANTS
+  // most of which will be at the top of the BB, the top down approach would be
+  // a better choice. Does IRTranslator placing constants at the beginning still
+  // make sense? Should this change based on Opcode?
+  bool dominates(MachineBasicBlock::const_iterator A,
+                 MachineBasicBlock::const_iterator B) const {
+
+    const MachineBasicBlock *BBA = A->getParent();
+    MachineBasicBlock::const_iterator I = BBA->begin();
+    unsigned count = 0;
+    for (; &*I != A && &*I != B; ++I, ++count)
+      ;
+    return &*I == A;
+  }
+
+  template <typename T>
+  MachineInstrBuilder buildCopyIfRequired(MachineInstr *MI, T) {
+    // No need to build copy here.
+    return MachineInstrBuilder(getMF(), MI);
+  }
+
+  MachineInstrBuilder buildCopyIfRequired(MachineInstr *MI, unsigned Dst) {
+    // We need ot build a copy from MI to Dst.
+    return buildCopy(Dst, MI->getOperand(0).getReg());
+  }
+
+  /// For given ID, find a machineinstr in the CSE Map. If found, check if it
+  /// dominates the current insertion point and if not, move it just before the
+  /// current insertion point and return it. If not found, return Null
+  /// MachineInstrBuilder.
+  template <typename DstTy>
+  MachineInstrBuilder
+  getDominatingInstrForID(FoldingSetNodeID &ID, GISelCSEInfo &CSEInfo,
+                          void *&NodeInsertPos, DstTy &&Dst) {
+    auto *CurMBB = &getMBB();
+    auto *Node = CSEInfo.getMachineInstrIfExists(ID, CurMBB, NodeInsertPos);
+    if (Node) {
+      auto CurrPos = getInsertPt();
+      if (!dominates(Node, CurrPos))
+        CurMBB->splice(CurrPos, CurMBB, Node);
+      // return MachineInstrBuilder(getMF(), Node);
+      return buildCopyIfRequired(Node, std::forward<DstTy>(Dst));
+    }
+    return MachineInstrBuilder();
+  }
+
+  /// Simple check if we can CSE (we have the CSEInfo) or if this Opcode is
+  /// safe to CSE.
+  bool canPerformCSEForOpc(unsigned Opc, GISelCSEInfo *CSEInfo) {
+    if (!CSEInfo || !CSEInfo->shouldCSE(Opc))
+      return false;
+    return true;
+  }
+
+  void profileDst(unsigned Reg, GISelInstProfileBuilder &B) {
+    LLT Ty = getMRI()->getType(Reg);
+    B.addNodeIDRegType(Ty);
+  }
+  template <typename DstType>
+  void profileDst(DstType &&Dst, GISelInstProfileBuilder &B) {
+    B.addNodeIDRegType(Dst);
+  }
+
+  void profileDsts(ArrayRef<LLT> Dsts, GISelInstProfileBuilder &B) {
+    for (auto &Dst : Dsts)
+      profileDst(Dst, B);
+  }
+
+  /// Build method for binary operations. Returns null builder if not CSEable.
+  template <typename DstTy, typename UseArg1Ty, typename UseArg2Ty>
+  MachineInstrBuilder buildInstrCSE(unsigned Opc, DstTy &&Dst, UseArg1Ty &&Arg1,
+                                    UseArg2Ty &&Arg2, void *&NodeInsertPos) {
+    auto *CSEInfo = getCSEInfo();
+    if (!canPerformCSEForOpc(Opc, CSEInfo))
+      return MachineInstrBuilder();
+
+    FoldingSetNodeID ID;
+    auto Profile = profileMBBOpcDst(ID, Opc, std::forward<DstTy>(Dst));
+    Profile.addNodeIDRegType(getRegFromArg(std::forward<UseArg1Ty>(Arg1)))
+        .addNodeIDRegType(getRegFromArg(std::forward<UseArg2Ty>(Arg2)));
+    return getDominatingInstrForID(ID, *CSEInfo, NodeInsertPos,
+                                   std::forward<DstTy>(Dst));
+  }
+
+  /// build method for unary operations. Returns null builder if not CSEable.
+  template <typename DstTy, typename UseArg1Ty>
+  MachineInstrBuilder buildInstrCSE(unsigned Opc, DstTy &&Dst, UseArg1Ty &&Arg1,
+                                    void *&NodeInsertPos) {
+    auto *CSEInfo = getCSEInfo();
+    if (!canPerformCSEForOpc(Opc, CSEInfo))
+      return MachineInstrBuilder();
+    FoldingSetNodeID ID;
+    auto Profile = profileMBBOpcDst(ID, Opc, std::forward<DstTy>(Dst));
+    Profile.addNodeIDRegType(getRegFromArg(std::forward<UseArg1Ty>(Arg1)));
+    return getDominatingInstrForID(ID, *CSEInfo, NodeInsertPos,
+                                   std::forward<DstTy>(Dst));
+  }
+
+  /// build method for building integer constants. Returns null builder if not
+  /// CSEable.
+  template <typename DstTy>
+  MachineInstrBuilder buildConstantCSE(DstTy &&Dst, int64_t Cst,
+                                       void *&NodeInsertPos) {
+    auto IntN =
+        IntegerType::get(getMF().getFunction().getContext(),
+                         getTypeSize(std::forward<DstTy>(Dst), *getMRI()));
+    ConstantInt *CI = ConstantInt::get(IntN, Cst, true);
+    return buildConstantCSE(std::forward<DstTy>(Dst), *CI, NodeInsertPos);
+  }
+
+  /// Common profiling helpers.
+  GISelInstProfileBuilder profileMBBOpc(FoldingSetNodeID &ID, unsigned Opc) {
+    auto Profile = GISelInstProfileBuilder(ID, *getMRI())
+                       .addNodeIDMBB(&getMBB())
+                       .addNodeIDOpcode(Opc);
+    return Profile;
+  }
+
+  template <typename DstTy>
+  GISelInstProfileBuilder profileMBBOpcDst(FoldingSetNodeID &ID, unsigned Opc,
+                                           DstTy &&Dst) {
+    auto Profile = profileMBBOpc(ID, Opc);
+    // Profile the Dst.
+    profileDst(Dst, Profile);
+    return Profile;
+  }
+
+  template <typename DstTy>
+  MachineInstrBuilder buildConstantCSE(DstTy &&Dst, const ConstantInt &CI,
+                                       void *&NodeInsertPos) {
+    unsigned Opc = TargetOpcode::G_CONSTANT;
+    auto *CSEInfo = getCSEInfo();
+    if (!canPerformCSEForOpc(Opc, CSEInfo))
+      return MachineInstrBuilder();
+    FoldingSetNodeID ID;
+    auto Profile = profileMBBOpcDst(ID, Opc, std::forward<DstTy>(Dst));
+    Profile.addNodeIDMachineOperand(MachineOperand::CreateCImm(&CI));
+    return getDominatingInstrForID(ID, *CSEInfo, NodeInsertPos,
+                                   std::forward<DstTy>(Dst));
+  }
+
+  template <typename DstTy>
+  MachineInstrBuilder buildFConstantCSE(DstTy &&Dst, double Val,
+                                        void *&NodeInsertPos) {
+    auto *CFP = ConstantFP::get(
+        getMF().getFunction().getContext(),
+        getAPFloatFromSize(Val,
+                           getTypeSize(std::forward<DstTy>(Dst), *getMRI())));
+    return buildFConstantCSE(std::forward<DstTy>(Dst), *CFP, NodeInsertPos);
+  }
+
+  template <typename DstTy>
+  MachineInstrBuilder buildFConstantCSE(DstTy &&Dst, const ConstantFP &CFP,
+                                        void *&NodeInsertPos) {
+    unsigned Opc = TargetOpcode::G_FCONSTANT;
+    auto *CSEInfo = getCSEInfo();
+    if (!canPerformCSEForOpc(Opc, CSEInfo))
+      return MachineInstrBuilder();
+    FoldingSetNodeID ID;
+    auto Profile = profileMBBOpcDst(ID, Opc, std::forward<DstTy>(Dst));
+    Profile.addNodeIDMachineOperand(MachineOperand::CreateFPImm(&CFP));
+    return getDominatingInstrForID(ID, *CSEInfo, NodeInsertPos,
+                                   std::forward<DstTy>(Dst));
+  }
+
+  template <typename DstTy>
+  MachineInstrBuilder buildUndefCSE(DstTy &&Dst, void *&NodeInsertPos) {
+    unsigned Opc = TargetOpcode::G_IMPLICIT_DEF;
+    auto *CSEInfo = getCSEInfo();
+    if (!canPerformCSEForOpc(Opc, CSEInfo))
+      return MachineInstrBuilder();
+    FoldingSetNodeID ID;
+    profileMBBOpcDst(ID, Opc, std::forward<DstTy>(Dst));
+    return getDominatingInstrForID(ID, *CSEInfo, NodeInsertPos,
+                                   std::forward<DstTy>(Dst));
+  }
+
+  template <typename SrcTy>
+  MachineInstrBuilder buildUnmergeCSE(ArrayRef<LLT> Dsts, SrcTy &&Src,
+                                      void *&NodeInsertPos) {
+    unsigned Opc = TargetOpcode::G_UNMERGE_VALUES;
+    auto *CSEInfo = getCSEInfo();
+    if (!canPerformCSEForOpc(Opc, CSEInfo))
+      return MachineInstrBuilder();
+    FoldingSetNodeID ID;
+    auto Profile = profileMBBOpc(ID, Opc);
+    profileDsts(Dsts, Profile);
+    Profile.addNodeIDRegType(getRegFromArg(std::forward<SrcTy>(Src)));
+    return getDominatingInstrForID(ID, *CSEInfo, NodeInsertPos, Dsts);
+  }
+
+  unsigned getTypeSize(const LLT &Ty, const MachineRegisterInfo &MRI) {
+    return Ty.getSizeInBits();
+  }
+  unsigned getTypeSize(unsigned Reg, const MachineRegisterInfo &MRI) {
+    return MRI.getType(Reg).getSizeInBits();
+  }
+
+  MachineInstrBuilder memoizeMIBIfPossible(MachineInstrBuilder MIB,
+                                           GISelCSEInfo *CSEInfo,
+                                           void *NodeInsertPos) {
+    if (!canPerformCSEForOpc(MIB->getOpcode(), CSEInfo))
+      return MIB;
+    MachineInstr *MIBInstr = MIB;
+    CSEInfo->insertInstr(MIBInstr, NodeInsertPos);
+    return MIB;
+  }
+
+  MachineInstrBuilder buildInstr(unsigned Opc, unsigned Dst, unsigned Src0,
+                                 void *NodeInsertPos) {
+    auto MIB = buildInstr(Opc).addDef(Dst).addUse(Src0);
+    auto *CSEInfo = getCSEInfo();
+    return memoizeMIBIfPossible(MIB, CSEInfo, NodeInsertPos);
+  }
+
+public:
+  // Pull in base class constructors.
+  using FoldableInstructionsBuilder<CSEMIRBuilder>::FoldableInstructionsBuilder;
+  // Unhide buildInstr
+  using FoldableInstructionsBuilder<CSEMIRBuilder>::buildInstr;
+  using Super = FoldableInstructionsBuilder<CSEMIRBuilder>;
+
+  void setMF(MachineFunction &MF) { Super::setMF(MF); }
+
+  template <typename DstTy, typename CstTy>
+  MachineInstrBuilder buildConstant(DstTy &&Dst, CstTy &&Cst) {
+    void *NodeInsertPos = nullptr;
+    auto *CSEInfo = getCSEInfo();
+    if (auto MIB = buildConstantCSE(std::forward<DstTy>(Dst),
+                                    std::forward<CstTy>(Cst), NodeInsertPos)) {
+      CSEInfo->countOpcodeHit(TargetOpcode::G_CONSTANT);
+      return MIB;
+    }
+    auto MIB = Super::buildConstant(std::forward<DstTy>(Dst),
+                                    std::forward<CstTy>(Cst));
+    // Memoize the instruction.
+    return memoizeMIBIfPossible(MIB, CSEInfo, NodeInsertPos);
+  }
+
+  template <typename DstTy, typename CstTy>
+  MachineInstrBuilder buildFConstant(DstTy &&Dst, CstTy &&Cst) {
+    void *NodeInsertPos = nullptr;
+    auto *CSEInfo = getCSEInfo();
+    if (auto MIB = buildFConstantCSE(std::forward<DstTy>(Dst),
+                                     std::forward<CstTy>(Cst), NodeInsertPos)) {
+      CSEInfo->countOpcodeHit(TargetOpcode::G_FCONSTANT);
+      return MIB;
+    }
+    auto MIB = Super::buildFConstant(std::forward<DstTy>(Dst),
+                                     std::forward<CstTy>(Cst));
+    // Memoize the instruction.
+    return memoizeMIBIfPossible(MIB, CSEInfo, NodeInsertPos);
+  }
+
+  template <typename DstTy> MachineInstrBuilder buildUndef(DstTy &&Dst) {
+    void *NodeInsertPos = nullptr;
+    unsigned Opc = TargetOpcode::G_IMPLICIT_DEF;
+    auto *CSEInfo = getCSEInfo();
+    if (auto MIB = buildUndefCSE(std::forward<DstTy>(Dst), NodeInsertPos)) {
+      CSEInfo->countOpcodeHit(Opc);
+      return MIB;
+    }
+    auto MIB = buildInstr(Opc).addDef(getDestFromArg(std::forward<DstTy>(Dst)));
+    return memoizeMIBIfPossible(MIB, CSEInfo, NodeInsertPos);
+  }
+
+  // TODO: Support the following Opcodes
+  // EXTRACT_VECTOR_ELT, INSERT_VECTOR_ELT.
+  // SELECT, SELECT_CC, ICMP, FCMP
+  // TRUNC, FPTRUNC
+  // EXTORTRUNC, and the various extends.
+  // GEP
+  // GLOBAL_VALUE
+  // FRAME_INDEX
+
+  // Implement buildBinaryOp required by FoldableInstructionsBuilder which
+  // tries to constant fold.
+  template <typename DstTy>
+  MachineInstrBuilder buildBinaryOp(unsigned Opcode, DstTy &&Dst, unsigned Src0,
+                                    unsigned Src1,
+                                    void *NodeInsertPos = nullptr) {
+    // First perform basic constant folding.
+    auto MaybeCst = ConstantFoldBinOp(Opcode, Src0, Src1, getMF().getRegInfo());
+    if (MaybeCst)
+      return buildConstant(std::forward<DstTy>(Dst), MaybeCst->getSExtValue());
+    // Try to see if we can CSE this.
+    auto *CSEInfo = getCSEInfo();
+    if (auto MIB = buildInstrCSE(Opcode, std::forward<DstTy>(Dst), Src0, Src1,
+                                 NodeInsertPos)) {
+      CSEInfo->countOpcodeHit(Opcode);
+      return MIB;
+    }
+    // Now build the instruction.
+    unsigned DstReg = getDestFromArg(std::forward<DstTy>(Dst));
+    validateBinaryOp(DstReg, Src0, Src1);
+    auto MIB = buildInstr(Opcode).addDef(DstReg).addUse(Src0).addUse(Src1);
+    return memoizeMIBIfPossible(MIB, CSEInfo, NodeInsertPos);
+  }
+
+  template <typename SrcTy>
+  MachineInstrBuilder buildUnmerge(ArrayRef<LLT> Dsts, SrcTy &&Src) {
+    void *NodeInsertPos = nullptr;
+    if (auto MIB =
+            buildUnmergeCSE(Dsts, std::forward<SrcTy>(Src), NodeInsertPos)) {
+      getCSEInfo()->countOpcodeHit(TargetOpcode::G_UNMERGE_VALUES);
+      return MIB;
+    }
+    SmallVector<unsigned, 4> DstRegs;
+    for (auto &Dst : Dsts)
+      DstRegs.push_back(getMRI()->createGenericVirtualRegister(Dst));
+    return buildUnmerge(DstRegs, std::forward<SrcTy>(Src));
+  }
+
+  template <typename SrcTy>
+  MachineInstrBuilder buildUnmerge(ArrayRef<unsigned> Dsts, SrcTy &&Src) {
+    auto MIB =
+        Super::buildUnmerge(Dsts, getRegFromArg(std::forward<SrcTy>(Src)));
+    auto *CSEInfo = getCSEInfo();
+    return memoizeMIBIfPossible(MIB, CSEInfo, nullptr);
+  }
+
+  template <typename DstTy, typename UseArg1Ty, typename UseArg2Ty>
+  MachineInstrBuilder buildInstr(unsigned Opc, DstTy &&Ty, UseArg1Ty &&Arg1,
+                                 UseArg2Ty &&Arg2) {
+    void *NodeInsertPos = nullptr;
+    if (auto MIB = buildInstrCSE(Opc, std::forward<DstTy>(Ty),
+                                 getRegFromArg(std::forward<UseArg1Ty>(Arg1)),
+                                 getRegFromArg(std::forward<UseArg2Ty>(Arg2)),
+                                 NodeInsertPos)) {
+      getCSEInfo()->countOpcodeHit(Opc);
+      return MIB;
+    }
+    return buildInstr(Opc, std::forward<DstTy>(Ty),
+                      getRegFromArg(std::forward<UseArg1Ty>(Arg1)),
+                      getRegFromArg(std::forward<UseArg2Ty>(Arg2)),
+                      NodeInsertPos);
+  }
+
+  template <typename DstTy, typename UseArg1Ty>
+  MachineInstrBuilder buildInstr(unsigned Opc, DstTy &&Ty, UseArg1Ty &&Arg1) {
+    void *NodeInsertPos = nullptr;
+    if (auto MIB = buildInstrCSE(Opc, std::forward<DstTy>(Ty),
+                                 getRegFromArg(std::forward<UseArg1Ty>(Arg1)),
+                                 NodeInsertPos)) {
+      getCSEInfo()->countOpcodeHit(Opc);
+      return MIB;
+    }
+    unsigned Dst = getDestFromArg(Ty);
+    return buildInstr(Opc, Dst, getRegFromArg(std::forward<UseArg1Ty>(Arg1)),
+                      NodeInsertPos);
+  }
+
+  // Try to provide an overload for buildInstr for binary ops in order to
+  // constant fold.
+  template <typename DstTy>
+  MachineInstrBuilder buildInstr(unsigned Opc, DstTy &&Dst, unsigned Src0,
+                                 unsigned Src1, void *NodeInsertPos = nullptr) {
+    switch (Opc) {
+    default:
+      break;
+    case TargetOpcode::G_ADD:
+    case TargetOpcode::G_AND:
+    case TargetOpcode::G_ASHR:
+    case TargetOpcode::G_LSHR:
+    case TargetOpcode::G_MUL:
+    case TargetOpcode::G_OR:
+    case TargetOpcode::G_SHL:
+    case TargetOpcode::G_SUB:
+    case TargetOpcode::G_XOR:
+    case TargetOpcode::G_UDIV:
+    case TargetOpcode::G_SDIV:
+    case TargetOpcode::G_UREM:
+    case TargetOpcode::G_SREM: {
+      return buildBinaryOp(Opc, std::forward<DstTy>(Dst), Src0, Src1,
+                           NodeInsertPos);
+    }
+    }
+    return buildInstr(Opc)
+        .addDef(getDestFromArg(std::forward<DstTy>(Dst)))
+        .addUse(Src0)
+        .addUse(Src1);
+  }
+
+  // Fallback implementation of buildInstr.
+  template <typename DstTy, typename... UseArgsTy>
+  MachineInstrBuilder buildInstr(unsigned Opc, DstTy &&Ty,
+                                 UseArgsTy &&... Args) {
+    auto MIB = buildInstr(Opc).addDef(getDestFromArg(Ty));
+    addUsesFromArgs(MIB, std::forward<UseArgsTy>(Args)...);
+    return MIB;
+  }
+};
+} // namespace llvm
+#endif

include/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 GISelCSEInfo;
 class TargetPassConfig;
 class MachineFunction;
 
 class CombinerChangeObserver {
 public:
   virtual ~CombinerChangeObserver() {}
 
   /// An instruction was erased.
   virtual void erasedInstr(MachineInstr &MI) = 0;
   /// An instruction was created and inseerted into the function.
   virtual void createdInstr(MachineInstr &MI) = 0;
 };
 
 class Combiner {
 public:
   Combiner(CombinerInfo &CombinerInfo, const TargetPassConfig *TPC);
 
-  bool combineMachineInstrs(MachineFunction &MF);
+  bool combineMachineInstrs(MachineFunction &MF, GISelCSEInfo *);
 
 protected:
   CombinerInfo &CInfo;
 
   MachineRegisterInfo *MRI = nullptr;
   const TargetPassConfig *TPC;
-  MachineIRBuilder Builder;
+  MachineIRBuilderState BuilderState;
 };
 
 } // End namespace llvm.
 
 #endif // LLVM_CODEGEN_GLOBALISEL_GICOMBINER_H

include/llvm/CodeGen/GlobalISel/CombinerHelper.h

 namespace llvm {
 
 class CombinerChangeObserver;
 class MachineIRBuilder;
 class MachineRegisterInfo;
 class MachineInstr;
 
 class CombinerHelper {
-  MachineIRBuilder &Builder;
+  MachineIRBuilder Builder;
   MachineRegisterInfo &MRI;
   CombinerChangeObserver &Observer;
 
   void eraseInstr(MachineInstr &MI);
   void scheduleForVisit(MachineInstr &MI);
 
 public:
-  CombinerHelper(CombinerChangeObserver &Observer, MachineIRBuilder &B);
+  CombinerHelper(CombinerChangeObserver &Observer, MachineIRBuilderState &B);
 
   /// If \p MI is COPY, try to combine it.
   /// Returns true if MI changed.
   bool tryCombineCopy(MachineInstr &MI);
 
   /// If \p MI is extend that consumes the result of a load, try to combine it.
   /// Returns true if MI changed.
   bool tryCombineExtendingLoads(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

 #define LLVM_CODEGEN_GLOBALISEL_COMBINER_INFO_H
 
 #include <cassert>
 namespace llvm {
 
 class CombinerChangeObserver;
 class LegalizerInfo;
 class MachineInstr;
-class MachineIRBuilder;
+struct MachineIRBuilderState;
 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(CombinerChangeObserver &Observer, MachineInstr &MI,
-                       MachineIRBuilder &B) const = 0;
+                       MachineIRBuilderState &State) const = 0;
 };
 } // namespace llvm
 
 #endif

include/llvm/CodeGen/GlobalISel/ConstantFoldingMIRBuilder.h

 /// This file implements a version of MachineIRBuilder which does trivial
 /// constant folding.
 //===----------------------------------------------------------------------===//
 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
 
 namespace llvm {
 
-static Optional<APInt> ConstantFoldBinOp(unsigned Opcode, const unsigned Op1,
-                                         const unsigned Op2,
-                                         const MachineRegisterInfo &MRI) {
-  auto MaybeOp1Cst = getConstantVRegVal(Op1, MRI);
-  auto MaybeOp2Cst = getConstantVRegVal(Op2, MRI);
-  if (MaybeOp1Cst && MaybeOp2Cst) {
-    LLT Ty = MRI.getType(Op1);
-    APInt C1(Ty.getSizeInBits(), *MaybeOp1Cst, true);
-    APInt C2(Ty.getSizeInBits(), *MaybeOp2Cst, true);
-    switch (Opcode) {
-    default:
-      break;
-    case TargetOpcode::G_ADD:
-      return C1 + C2;
-    case TargetOpcode::G_AND:
-      return C1 & C2;
-    case TargetOpcode::G_ASHR:
-      return C1.ashr(C2);
-    case TargetOpcode::G_LSHR:
-      return C1.lshr(C2);
-    case TargetOpcode::G_MUL:
-      return C1 * C2;
-    case TargetOpcode::G_OR:
-      return C1 | C2;
-    case TargetOpcode::G_SHL:
-      return C1 << C2;
-    case TargetOpcode::G_SUB:
-      return C1 - C2;
-    case TargetOpcode::G_XOR:
-      return C1 ^ C2;
-    case TargetOpcode::G_UDIV:
-      if (!C2.getBoolValue())
-        break;
-      return C1.udiv(C2);
-    case TargetOpcode::G_SDIV:
-      if (!C2.getBoolValue())
-        break;
-      return C1.sdiv(C2);
-    case TargetOpcode::G_UREM:
-      if (!C2.getBoolValue())
-        break;
-      return C1.urem(C2);
-    case TargetOpcode::G_SREM:
-      if (!C2.getBoolValue())
-        break;
-      return C1.srem(C2);
-    }
-  }
-  return None;
-}
-
 /// An MIRBuilder which does trivial constant folding of binary ops.
 /// Calls to buildInstr will also try to constant fold binary ops.
 class ConstantFoldingMIRBuilder
     : public FoldableInstructionsBuilder<ConstantFoldingMIRBuilder> {
 public:
   // Pull in base class constructors.
   using FoldableInstructionsBuilder<
       ConstantFoldingMIRBuilder>::FoldableInstructionsBuilder;

include/llvm/CodeGen/GlobalISel/GISelWorkList.h

void remove(MachineInstr *I) {
     if (It == WorklistMap.end()) return; // Not in worklist.
 
     // Don't bother moving everything down, just null out the slot.
     Worklist[It->second] = nullptr;
 
     WorklistMap.erase(It);
   }
 
+  void clear() {
+    Worklist.clear();
+    WorklistMap.clear();
+  }
+
   MachineInstr *pop_back_val() {
     MachineInstr *I;
     do {
       I = Worklist.pop_back_val();
     } while(!I);
     assert(I && "Pop back on empty worklist");
     WorklistMap.erase(I);
     return I;
   }
 };
 
 } // end namespace llvm.
 
 #endif

include/llvm/CodeGen/GlobalISel/IRTranslator.h

private:
   }
 
   /// @}
 
   // Builder for machine instruction a la IRBuilder.
   // I.e., compared to regular MIBuilder, this one also inserts the instruction
   // in the current block, it can creates block, etc., basically a kind of
   // IRBuilder, but for Machine IR.
+  MachineIRBuilderState CurBuilderState;
   MachineIRBuilder CurBuilder;
 
   // Builder set to the entry block (just after ABI lowering instructions). Used
   // as a convenient location for Constants.
+  MachineIRBuilderState EntryBuilderState;
   MachineIRBuilder EntryBuilder;
 
   // The MachineFunction currently being translated.
   MachineFunction *MF;
 
   /// MachineRegisterInfo used to create virtual registers.
   MachineRegisterInfo *MRI = nullptr;
 

include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

 //===-- llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h --===========//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 // This file contains some helper functions which try to cleanup artifacts
 // such as G_TRUNCs/G_[ZSA]EXTENDS that were created during legalization to make
 // the types match. This file also contains some combines of merges that happens
 // at the end of the legalization.
 //===----------------------------------------------------------------------===//
 
+#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/Legalizer.h"
 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
-#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/Debug.h"
 
 #define DEBUG_TYPE "legalizer"
 
 namespace llvm {
 class LegalizationArtifactCombiner {
-  MachineIRBuilder &Builder;
+  MachineIRBuilderState &BuilderState;
   MachineRegisterInfo &MRI;
   const LegalizerInfo &LI;
 
 public:
-  LegalizationArtifactCombiner(MachineIRBuilder &B, MachineRegisterInfo &MRI,
+  LegalizationArtifactCombiner(MachineIRBuilderState &State,
+                               MachineRegisterInfo &MRI,
                                const LegalizerInfo &LI)
-      : Builder(B), MRI(MRI), LI(LI) {}
+      : BuilderState(State), MRI(MRI), LI(LI) {}
 
   bool tryCombineAnyExt(MachineInstr &MI,
                         SmallVectorImpl<MachineInstr *> &DeadInsts) {
     if (MI.getOpcode() != TargetOpcode::G_ANYEXT)
       return false;
     if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_TRUNC,
                                            MI.getOperand(1).getReg(), MRI)) {
       LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
       unsigned DstReg = MI.getOperand(0).getReg();
       unsigned SrcReg = DefMI->getOperand(1).getReg();
+      CSEMIRBuilder Builder(BuilderState);
       Builder.setInstr(MI);
       // We get a copy/trunc/extend depending on the sizes
       Builder.buildAnyExtOrTrunc(DstReg, SrcReg);
       markInstAndDefDead(MI, *DefMI, DeadInsts);
       return true;
     }
     return tryFoldImplicitDef(MI, DeadInsts);
   }
 
   bool tryCombineZExt(MachineInstr &MI,
                       SmallVectorImpl<MachineInstr *> &DeadInsts) {
 
     if (MI.getOpcode() != TargetOpcode::G_ZEXT)
       return false;
     if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_TRUNC,
                                            MI.getOperand(1).getReg(), MRI)) {
       unsigned DstReg = MI.getOperand(0).getReg();
       LLT DstTy = MRI.getType(DstReg);
       if (isInstUnsupported({TargetOpcode::G_AND, {DstTy}}) ||
           isInstUnsupported({TargetOpcode::G_CONSTANT, {DstTy}}))
         return false;
       LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
+      CSEMIRBuilder Builder(BuilderState);
       Builder.setInstr(MI);
       unsigned ZExtSrc = MI.getOperand(1).getReg();
       LLT ZExtSrcTy = MRI.getType(ZExtSrc);
       APInt Mask = APInt::getAllOnesValue(ZExtSrcTy.getSizeInBits());
       auto MaskCstMIB = Builder.buildConstant(DstTy, Mask.getZExtValue());
       unsigned TruncSrc = DefMI->getOperand(1).getReg();
       // We get a copy/trunc/extend depending on the sizes
       auto SrcCopyOrTrunc = Builder.buildAnyExtOrTrunc(DstTy, TruncSrc);
if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_TRUNC,
                                            MI.getOperand(1).getReg(), MRI)) {
       unsigned DstReg = MI.getOperand(0).getReg();
       LLT DstTy = MRI.getType(DstReg);
       if (isInstUnsupported({TargetOpcode::G_SHL, {DstTy}}) ||
           isInstUnsupported({TargetOpcode::G_ASHR, {DstTy}}) ||
           isInstUnsupported({TargetOpcode::G_CONSTANT, {DstTy}}))
         return false;
       LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
+      CSEMIRBuilder Builder(BuilderState);
       Builder.setInstr(MI);
       unsigned SExtSrc = MI.getOperand(1).getReg();
       LLT SExtSrcTy = MRI.getType(SExtSrc);
       unsigned SizeDiff = DstTy.getSizeInBits() - SExtSrcTy.getSizeInBits();
       auto SizeDiffMIB = Builder.buildConstant(DstTy, SizeDiff);
       unsigned TruncSrcReg = DefMI->getOperand(1).getReg();
       // We get a copy/trunc/extend depending on the sizes
       auto SrcCopyExtOrTrunc = Builder.buildAnyExtOrTrunc(DstTy, TruncSrcReg);
if (Opcode != TargetOpcode::G_ANYEXT && Opcode != TargetOpcode::G_ZEXT &&
       return false;
 
     if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF,
                                            MI.getOperand(1).getReg(), MRI)) {
       unsigned DstReg = MI.getOperand(0).getReg();
       LLT DstTy = MRI.getType(DstReg);
       if (isInstUnsupported({TargetOpcode::G_IMPLICIT_DEF, {DstTy}}))
         return false;
+      CSEMIRBuilder Builder(BuilderState);
       LLVM_DEBUG(dbgs() << ".. Combine EXT(IMPLICIT_DEF) " << MI;);
       Builder.setInstr(MI);
       Builder.buildInstr(TargetOpcode::G_IMPLICIT_DEF, DstReg);
       markInstAndDefDead(MI, *DefMI, DeadInsts);
       return true;
     }
     return false;
   }
if (!MergeI)
       return false;
 
     const unsigned NumMergeRegs = MergeI->getNumOperands() - 1;
 
     if (NumMergeRegs < NumDefs) {
       if (NumDefs % NumMergeRegs != 0)
         return false;
 
+      MachineIRBuilder Builder(BuilderState);
       Builder.setInstr(MI);
       // Transform to UNMERGEs, for example
       //   %1 = G_MERGE_VALUES %4, %5
       //   %9, %10, %11, %12 = G_UNMERGE_VALUES %1
       // to
       //   %9, %10 = G_UNMERGE_VALUES %4
       //   %11, %12 = G_UNMERGE_VALUES %5
 
       const unsigned NewNumDefs = NumDefs / NumMergeRegs;
       for (unsigned Idx = 0; Idx < NumMergeRegs; ++Idx) {
         SmallVector<unsigned, 2> DstRegs;
         for (unsigned j = 0, DefIdx = Idx * NewNumDefs; j < NewNumDefs;
              ++j, ++DefIdx)
           DstRegs.push_back(MI.getOperand(DefIdx).getReg());
 
         Builder.buildUnmerge(DstRegs, MergeI->getOperand(Idx + 1).getReg());
       }
 
     } else if (NumMergeRegs > NumDefs) {
       if (NumMergeRegs % NumDefs != 0)
         return false;
 
+      MachineIRBuilder Builder(BuilderState);
       Builder.setInstr(MI);
       // Transform to MERGEs
       //   %6 = G_MERGE_VALUES %17, %18, %19, %20
       //   %7, %8 = G_UNMERGE_VALUES %6
       // to
       //   %7 = G_MERGE_VALUES %17, %18
       //   %8 = G_MERGE_VALUES %19, %20
 

include/llvm/CodeGen/GlobalISel/LegalizerHelper.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_GLOBALISEL_MACHINELEGALIZEHELPER_H
 #define LLVM_CODEGEN_GLOBALISEL_MACHINELEGALIZEHELPER_H
 
 #include "llvm/CodeGen/GlobalISel/CallLowering.h"
 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
+#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
 #include "llvm/CodeGen/LowLevelType.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/RuntimeLibcalls.h"
 
 namespace llvm {
 // Forward declarations.
 class LegalizerInfo;
 class Legalizer;
public:
 
   /// Legalize a vector instruction by increasing the number of vector elements
   /// involved and ignoring the added elements later.
   LegalizeResult moreElementsVector(MachineInstr &MI, unsigned TypeIdx,
                                     LLT WideTy);
 
   /// Expose MIRBuilder so clients can set their own RecordInsertInstruction
   /// functions
-  MachineIRBuilder MIRBuilder;
+  MachineIRBuilderState MIRBuilderState;
+  // MachineIRBuilder MIRBuilder;
+  CSEMIRBuilder MIRBuilder;
 
   /// Expose LegalizerInfo so the clients can re-use.
   const LegalizerInfo &getLegalizerInfo() const { return LI; }
 
 private:
   /// Legalize a single operand \p OpIdx of the machine instruction \p MI as a
   /// Use by extending the operand's type to \p WideTy using the specified \p
   /// ExtOpcode for the extension instruction, and replacing the vreg of the
private:
   LegalizeResult lowerBitCount(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
 
   MachineRegisterInfo &MRI;
   const LegalizerInfo &LI;
 };
 
 /// Helper function that creates the given libcall.
 LegalizerHelper::LegalizeResult
-createLibcall(MachineIRBuilder &MIRBuilder, RTLIB::Libcall Libcall,
+createLibcall(MachineIRBuilderState &State, RTLIB::Libcall Libcall,
               const CallLowering::ArgInfo &Result,
               ArrayRef<CallLowering::ArgInfo> Args);
 
 } // End namespace llvm.
 
 #endif

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

 #include <utility>
 
 namespace llvm {
 
 extern cl::opt<bool> DisableGISelLegalityCheck;
 
 class MachineInstr;
 class MachineIRBuilder;
+struct MachineIRBuilderState;
 class MachineRegisterInfo;
 class MCInstrInfo;
 
 namespace LegalizeActions {
 enum LegalizeAction : std::uint8_t {
   /// The operation is expected to be selectable directly by the target, and
   /// no transformation is necessary.
   Legal,
public:
   /// \returns a description of the next legalization step to perform.
   LegalizeActionStep getAction(const MachineInstr &MI,
                                const MachineRegisterInfo &MRI) const;
 
   bool isLegal(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
 
   virtual bool legalizeCustom(MachineInstr &MI,
                               MachineRegisterInfo &MRI,
-                              MachineIRBuilder &MIRBuilder) const;
+                              MachineIRBuilderState &State) const;
 
 private:
   /// Determine what action should be taken to legalize the given generic
   /// instruction opcode, type-index and type. Requires computeTables to have
   /// been called.
   ///
   /// \returns a pair consisting of the kind of legalization that should be
   /// performed and the destination type.

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

 //===-- llvm/CodeGen/GlobalISel/MachineIRBuilder.h - MIBuilder --*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 /// \file
 /// This file declares the MachineIRBuilder class.
 /// This is a helper class to build MachineInstr.
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_GLOBALISEL_MACHINEIRBUILDER_H
 #define LLVM_CODEGEN_GLOBALISEL_MACHINEIRBUILDER_H
 
+#include "llvm/CodeGen/GlobalISel/CSEInfo.h"
 #include "llvm/CodeGen/GlobalISel/Types.h"
 
 #include "llvm/CodeGen/LowLevelType.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugLoc.h"
struct MachineIRBuilderState {
 
   /// \name Fields describing the insertion point.
   /// @{
   MachineBasicBlock *MBB;
   MachineBasicBlock::iterator II;
   /// @}
 
   std::function<void(MachineInstr *)> InsertedInstr;
+
+  GISelCSEInfo *CSEInfo = nullptr;
+  void recordInsertions(std::function<void(MachineInstr *)> InsertedInstr);
+  void stopRecordingInsertions();
+  void setCSEInfo(GISelCSEInfo *Info) { CSEInfo = Info; }
+
+  void setMF(MachineFunction &MF);
+  void setMBB(MachineBasicBlock &MBB);
+  void setInstr(MachineInstr &MI);
 };
 
 /// Helper class to build MachineInstr.
 /// It keeps internally the insertion point and debug location for all
 /// the new instructions we want to create.
 /// This information can be modify via the related setters.
 class MachineIRBuilderBase {
 
-  MachineIRBuilderState State;
+  MachineIRBuilderState &State;
   void validateTruncExt(unsigned Dst, unsigned Src, bool IsExtend);
 
 protected:
   unsigned getDestFromArg(unsigned Reg) { return Reg; }
   unsigned getDestFromArg(LLT Ty) {
     return getMF().getRegInfo().createGenericVirtualRegister(Ty);
   }
   unsigned getDestFromArg(const TargetRegisterClass *RC) {
protected:
   unsigned getRegFromArg(const MachineInstrBuilder &MIB) {
     return MIB->getOperand(0).getReg();
   }
 
   void validateBinaryOp(unsigned Res, unsigned Op0, unsigned Op1);
 
 public:
   /// Some constructors for easy use.
-  MachineIRBuilderBase() = default;
-  MachineIRBuilderBase(MachineFunction &MF) { setMF(MF); }
-  MachineIRBuilderBase(MachineInstr &MI) : MachineIRBuilderBase(*MI.getMF()) {
+  MachineIRBuilderBase() = delete;
+  MachineIRBuilderBase(MachineFunction &MF, MachineIRBuilderState &State)
+      : State(State) {
+    setMF(MF);
+  }
+  MachineIRBuilderBase(MachineInstr &MI, MachineIRBuilderState &State)
+      : MachineIRBuilderBase(*MI.getMF(), State) {
     setInstr(MI);
   }
 
-  MachineIRBuilderBase(const MachineIRBuilderState &BState) : State(BState) {}
+  MachineIRBuilderBase(MachineIRBuilderState &BState) : State(BState) {}
 
   const TargetInstrInfo &getTII() {
     assert(State.TII && "TargetInstrInfo is not set");
     return *State.TII;
   }
 
   /// Getter for the function we currently build.
   MachineFunction &getMF() {
public:
   MachineIRBuilderState &getState() { return State; }
 
   /// Getter for the basic block we currently build.
   MachineBasicBlock &getMBB() {
     assert(State.MBB && "MachineBasicBlock is not set");
     return *State.MBB;
   }
 
+  GISelCSEInfo *getCSEInfo() { return State.CSEInfo; }
+
   /// Current insertion point for new instructions.
   MachineBasicBlock::iterator getInsertPt() { return State.II; }
 
   /// Set the insertion point before the specified position.
   /// \pre MBB must be in getMF().
   /// \pre II must be a valid iterator in MBB.
   void setInsertPt(MachineBasicBlock &MBB, MachineBasicBlock::iterator II);
   /// @}
 
+  void setCSEInfo(GISelCSEInfo *Info) { State.CSEInfo = Info; }
+
   /// \name Setters for the insertion point.
   /// @{
   /// Set the MachineFunction where to build instructions.
-  void setMF(MachineFunction &);
+  void setMF(MachineFunction &MF) { State.setMF(MF); }
 
   /// Set the insertion point to the  end of \p MBB.
   /// \pre \p MBB must be contained by getMF().
-  void setMBB(MachineBasicBlock &MBB);
+  void setMBB(MachineBasicBlock &MBB) { State.setMBB(MBB); };
 
   /// Set the insertion point to before MI.
   /// \pre MI must be in getMF().
-  void setInstr(MachineInstr &MI);
+  void setInstr(MachineInstr &MI) { State.setInstr(MI); }
   /// @}
 
   /// \name Control where instructions we create are recorded (typically for
   /// visiting again later during legalization).
   /// @{
   void recordInsertion(MachineInstr *InsertedInstr) const;
   void recordInsertions(std::function<void(MachineInstr *)> InsertedInstr);
   void stopRecordingInsertions();

include/llvm/CodeGen/GlobalISel/RegBankSelect.h

private:
   /// Get the frequency of the edges.
   /// This is required for non-fast mode.
   MachineBranchProbabilityInfo *MBPI = nullptr;
 
   /// Current optimization remark emitter. Used to report failures.
   std::unique_ptr<MachineOptimizationRemarkEmitter> MORE;
 
   /// Helper class used for every code morphing.
+  MachineIRBuilderState MIRBuilderState;
   MachineIRBuilder MIRBuilder;
 
   /// Optimization mode of the pass.
   Mode OptMode;
 
   /// Current target configuration. Controls how the pass handles errors.
   const TargetPassConfig *TPC;
 

include/llvm/CodeGen/GlobalISel/Utils.h

 
 /// Returns an APFloat from Val converted to the appropriate size.
 APFloat getAPFloatFromSize(double Val, unsigned Size);
 
 /// Modify analysis usage so it preserves passes required for the SelectionDAG
 /// fallback.
 void getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU);
 
+Optional<APInt> ConstantFoldBinOp(unsigned Opcode, const unsigned Op1,
+                                  const unsigned Op2,
+                                  const MachineRegisterInfo &MRI);
 } // End namespace llvm.
 #endif

include/llvm/InitializePasses.h

 void initializeLazyBranchProbabilityInfoPassPass(PassRegistry&);
 void initializeLazyMachineBlockFrequencyInfoPassPass(PassRegistry&);
 void initializeLazyValueInfoPrinterPass(PassRegistry&);
 void initializeLazyValueInfoWrapperPassPass(PassRegistry&);
 void initializeLegacyDivergenceAnalysisPass(PassRegistry&);
 void initializeLegacyLICMPassPass(PassRegistry&);
 void initializeLegacyLoopSinkPassPass(PassRegistry&);
 void initializeLegalizerPass(PassRegistry&);
+void initializeGISelCSEAnalysisWrapperPassPass(PassRegistry &);
 void initializeLibCallsShrinkWrapLegacyPassPass(PassRegistry&);
 void initializeLintPass(PassRegistry&);
 void initializeLiveDebugValuesPass(PassRegistry&);
 void initializeLiveDebugVariablesPass(PassRegistry&);
 void initializeLiveIntervalsPass(PassRegistry&);
 void initializeLiveRangeShrinkPass(PassRegistry&);
 void initializeLiveRegMatrixPass(PassRegistry&);
 void initializeLiveStacksPass(PassRegistry&);

include/llvm/Support/LowLevelTypeImpl.h

public:
   bool operator==(const LLT &RHS) const {
     return IsPointer == RHS.IsPointer && IsVector == RHS.IsVector &&
            RHS.RawData == RawData;
   }
 
   bool operator!=(const LLT &RHS) const { return !(*this == RHS); }
 
   friend struct DenseMapInfo<LLT>;
+  friend class GISelInstProfileBuilder;
 
 private:
   /// LLT is packed into 64 bits as follows:
   /// isPointer : 1
   /// isVector  : 1
   /// with 62 bits remaining for Kind-specific data, packed in bitfields
   /// as described below. As there isn't a simple portable way to pack bits
   /// into bitfields, here the different fields in the packed structure is

lib/CodeGen/GlobalISel/CMakeLists.txt

 add_llvm_library(LLVMGlobalISel
+        CSEInfo.cpp
         CallLowering.cpp
         GlobalISel.cpp
         Combiner.cpp
         CombinerHelper.cpp
         IRTranslator.cpp
         InstructionSelect.cpp
         InstructionSelector.cpp
         LegalityPredicates.cpp

lib/CodeGen/GlobalISel/CSEInfo.cpp

+//===- CSEInfo.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/CSEInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+
+#define DEBUG_TYPE "cseinfo"
+
+using namespace llvm;
+char llvm::GISelCSEAnalysisWrapperPass::ID = 0;
+INITIALIZE_PASS_BEGIN(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,
+                      "Analysis containing CSE Info", false, true)
+INITIALIZE_PASS_END(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,
+                    "Analysis containing CSE Info", false, true)
+
+/// -------- UniqueMachineInstr -------------//
+
+void UniqueMachineInstr::Profile(FoldingSetNodeID &ID) {
+  GISelInstProfileBuilder(ID, MI->getMF()->getRegInfo()).addNodeID(MI);
+}
+/// -----------------------------------------
+
+/// -------- GISelCSEInfo -------------//
+void GISelCSEInfo::setMF(MachineFunction &MF) {
+  this->MF = &MF;
+  this->MRI = &MF.getRegInfo();
+  // Register this as the delegate for handling insertions and deletions of
+  // instructions.
+  MF.setDelegate(this);
+}
+
+GISelCSEInfo::~GISelCSEInfo() {
+  if (MF)
+    MF->resetDelegate(this);
+}
+
+bool GISelCSEInfo::isUniqueMachineInstValid(
+    const UniqueMachineInstr &UMI) const {
+  // Should we check here and assert that the instruction has been fully constructed?
+  // FIXME: Any other checks required to be done here? Remove this method if none.
+  return true;
+}
+
+void GISelCSEInfo::invalidateUniqueMachineInstr(UniqueMachineInstr *UMI) {
+  bool Removed = CSEMap.RemoveNode(UMI);
+  (void)Removed;
+  assert(Removed && "Invalidation called on invalid UMI");
+  // FIXME: Should UMI be deallocated/destroyed?
+}
+
+UniqueMachineInstr *GISelCSEInfo::getNodeIfExists(FoldingSetNodeID &ID,
+                                                  MachineBasicBlock *MBB,
+                                                  void *&InsertPos) {
+  auto *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
+  if (Node) {
+    if (!isUniqueMachineInstValid(*Node)) {
+      invalidateUniqueMachineInstr(Node);
+      return nullptr;
+    }
+
+    if (Node->MI->getParent() != MBB)
+      return nullptr;
+  }
+  return Node;
+}
+
+void GISelCSEInfo::insertNode(UniqueMachineInstr *UMI, void *InsertPos) {
+  handleRecordedInsts();
+  assert(UMI);
+  UniqueMachineInstr *MaybeNewNode = UMI;
+  if (InsertPos)
+    CSEMap.InsertNode(UMI, InsertPos);
+  else
+    MaybeNewNode = CSEMap.GetOrInsertNode(UMI);
+  if (MaybeNewNode != UMI) {
+    // A similar node exists in the folding set. Let's ignore this one.
+    return;
+  }
+  assert(InstrMapping.count(UMI->MI) == 0 &&
+         "This instruction should not be in the map");
+  InstrMapping[UMI->MI] = MaybeNewNode;
+}
+
+UniqueMachineInstr *GISelCSEInfo::getUniqueInstrForMI(const MachineInstr *MI) {
+  assert(shouldCSE(MI->getOpcode()) && "Trying to CSE an unsupported Node");
+  auto *Node = new (UniqueInstrAllocator) UniqueMachineInstr(MI);
+  return Node;
+}
+
+void GISelCSEInfo::insertInstr(MachineInstr *MI, void *InsertPos) {
+  assert(MI);
+  // If it exists in temporary insts, remove it.
+  TemporaryInsts.remove(MI);
+  auto *Node = getUniqueInstrForMI(MI);
+  insertNode(Node, InsertPos);
+}
+
+MachineInstr *GISelCSEInfo::getMachineInstrIfExists(FoldingSetNodeID &ID,
+                                                    MachineBasicBlock *MBB,
+                                                    void *&InsertPos) {
+  handleRecordedInsts();
+  if (auto *Inst = getNodeIfExists(ID, MBB, InsertPos)) {
+    LLVM_DEBUG(dbgs() << "CSEInfo: Found Instr " << *Inst->MI << "\n";);
+    return const_cast<MachineInstr *>(Inst->MI);
+  }
+  return nullptr;
+}
+
+void GISelCSEInfo::countOpcodeHit(unsigned Opc) {
+#ifndef NDEBUG
+  if (OpcodeHitTable.count(Opc))
+    OpcodeHitTable[Opc] += 1;
+  else
+    OpcodeHitTable[Opc] = 1;
+#endif
+  // Else do nothing.
+}
+
+void GISelCSEInfo::recordNewInstruction(MachineInstr *MI) {
+  if (shouldCSE(MI->getOpcode())) {
+    TemporaryInsts.insert(MI);
+    LLVM_DEBUG(dbgs() << "CSEInfo: Recording new MI" << *MI << "\n";);
+  }
+}
+
+void GISelCSEInfo::handleRecordedInst(MachineInstr *MI) {
+  assert(shouldCSE(MI->getOpcode()) && "Invalid instruction for CSE");
+  auto *UMI = InstrMapping.lookup(MI);
+  LLVM_DEBUG(dbgs() << "CSEInfo: Handling recorded MI" << *MI << "\n";);
+  if (UMI) {
+    // Invalidate this MI.
+    invalidateUniqueMachineInstr(UMI);
+    InstrMapping.erase(MI);
+  }
+  /// Now insert the new instruction.
+  if (UMI) {
+    /// We'll reuse the same UniqueMachineInstr to avoid the new
+    /// allocation.
+    *UMI = UniqueMachineInstr(MI);
+    insertNode(UMI, nullptr);
+  } else {
+    /// This is a new instruction. Allocate a new UniqueMachineInstr and
+    /// Insert.
+    insertInstr(MI);
+  }
+}
+
+void GISelCSEInfo::handleRemoveInst(MachineInstr *MI) {
+  if (auto *UMI = InstrMapping.lookup(MI)) {
+    invalidateUniqueMachineInstr(UMI);
+    InstrMapping.erase(MI);
+  }
+  TemporaryInsts.remove(MI);
+}
+
+void GISelCSEInfo::handleRecordedInsts() {
+  while (!TemporaryInsts.empty()) {
+    auto *MI = TemporaryInsts.pop_back_val();
+    handleRecordedInst(MI);
+  }
+}
+
+bool GISelCSEInfo::shouldCSE(unsigned Opc) {
+  // First allow the callback to decide.
+  if (ShouldCSEFn && ShouldCSEFn(Opc))
+    return true;
+  // Only GISel opcodes are CSEable
+  if (!isPreISelGenericOpcode(Opc))
+    return false;
+  switch (Opc) {
+  default:
+    break;
+  case TargetOpcode::G_ADD:
+  case TargetOpcode::G_AND:
+  case TargetOpcode::G_ASHR:
+  case TargetOpcode::G_LSHR:
+  case TargetOpcode::G_MUL:
+  case TargetOpcode::G_OR:
+  case TargetOpcode::G_SHL:
+  case TargetOpcode::G_SUB:
+  case TargetOpcode::G_XOR:
+  case TargetOpcode::G_UDIV:
+  case TargetOpcode::G_SDIV:
+  case TargetOpcode::G_UREM:
+  case TargetOpcode::G_SREM:
+  case TargetOpcode::G_CONSTANT:
+  case TargetOpcode::G_FCONSTANT:
+  case TargetOpcode::G_ZEXT:
+  case TargetOpcode::G_SEXT:
+  case TargetOpcode::G_ANYEXT:
+  case TargetOpcode::G_UNMERGE_VALUES:
+  case TargetOpcode::G_TRUNC:
+    return true;
+  }
+  return false;
+}
+
+void GISelCSEInfo::MF_HandleRemoval(const MachineInstr &MI) {
+  handleRemoveInst(&const_cast<MachineInstr &>(MI));
+}
+
+void GISelCSEInfo::MF_HandleInsertion(const MachineInstr &MI) {
+  recordNewInstruction(&const_cast<MachineInstr &>(MI));
+}
+
+void GISelCSEInfo::analyze(MachineFunction &MF) {
+  setMF(MF);
+  for (auto &MBB : MF) {
+    if (MBB.empty())
+      continue;
+    for (MachineInstr &MI : MBB) {
+      if (!shouldCSE(MI.getOpcode()))
+        continue;
+      LLVM_DEBUG(dbgs() << "CSEInfo::Add MI: " << MI << "\n";);
+      insertInstr(&MI);
+    }
+  }
+}
+
+void GISelCSEInfo::releaseMemory() {
+  // print();
+  CSEMap.clear();
+  InstrMapping.clear();
+  UniqueInstrAllocator.Reset();
+  TemporaryInsts.clear();
+  ShouldCSEFn = nullptr;
+  MRI = nullptr;
+  if (MF)
+    MF->resetDelegate(this);
+  MF = nullptr;
+#ifndef NDEBUG
+  OpcodeHitTable.clear();
+#endif
+}
+
+void GISelCSEInfo::print() {
+#ifndef NDEBUG
+  for (auto &It : OpcodeHitTable) {
+    dbgs() << "CSE Count for Opc " << It.first << " : " << It.second << "\n";
+  };
+#endif
+}
+/// -----------------------------------------
+
+// ---- Profiling methods for FoldingSetNode --- //
+const GISelInstProfileBuilder &
+GISelInstProfileBuilder::addNodeID(const MachineInstr *MI) const{
+  addNodeIDMBB(MI->getParent());
+  addNodeIDOpcode(MI->getOpcode());
+  for (auto &Op : MI->operands())
+    addNodeIDMachineOperand(Op);
+  return *this;
+}
+
+const GISelInstProfileBuilder &
+GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const {
+  ID.AddInteger(Opc);
+  return *this;
+}
+
+const GISelInstProfileBuilder &
+GISelInstProfileBuilder::addNodeIDRegType(const LLT &Ty) const {
+  uint64_t Val = ((uint64_t)Ty.RawData) << 2 | ((uint64_t)Ty.IsPointer) << 1 |
+                 ((uint64_t)Ty.IsVector);
+  ID.AddInteger(Val);
+  return *this;
+}
+
+const GISelInstProfileBuilder &
+GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const {
+  ID.AddPointer(RC);
+  return *this;
+}
+
+const GISelInstProfileBuilder &
+GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const {
+  ID.AddPointer(RB);
+  return *this;
+}
+
+const GISelInstProfileBuilder &
+GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const {
+  ID.AddInteger(Imm);
+  return *this;
+}
+
+const GISelInstProfileBuilder &
+GISelInstProfileBuilder::addNodeIDRegNum(unsigned Reg) const {
+  ID.AddInteger(Reg);
+  return *this;
+}
+
+const GISelInstProfileBuilder &
+GISelInstProfileBuilder::addNodeIDRegType(const unsigned Reg) const {
+  addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false));
+  return *this;
+}
+
+const GISelInstProfileBuilder &
+GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const {
+  ID.AddPointer(MBB);
+  return *this;
+}
+
+const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDMachineOperand(
+    const MachineOperand &MO) const {
+  if (MO.isReg()) {
+    unsigned Reg = MO.getReg();
+    if (!MO.isDef())
+      addNodeIDRegNum(Reg);
+    LLT Ty = MRI.getType(Reg);
+    if (Ty.isValid())
+      addNodeIDRegType(Ty);
+    auto *RB = MRI.getRegBankOrNull(Reg);
+    if (RB)
+      addNodeIDRegType(RB);
+    auto *RC = MRI.getRegClassOrNull(Reg);
+    if (RC)
+      addNodeIDRegType(RC);
+    assert(!MO.isImplicit() && "Unhandled case");
+  } else if (MO.isImm())
+    ID.AddInteger(MO.getImm());
+  else if (MO.isCImm())
+    ID.AddPointer(MO.getCImm());
+  else if (MO.isFPImm())
+    ID.AddPointer(MO.getFPImm());
+  else if (MO.isPredicate())
+    ID.AddInteger(MO.getPredicate());
+  else
+    llvm_unreachable("Unhandled operand type");
+  // Handle other types
+  return *this;
+}
+
+void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) {
+  releaseMemory();
+  // Do the analysis
+  Info.analyze(MF);
+  return false;
+}

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/ADT/PostOrderIterator.h"
+#include "llvm/CodeGen/GlobalISel/CSEInfo.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/MachineIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
+#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/Debug.h"
 
 #define DEBUG_TYPE "gi-combiner"
 
 using namespace llvm;
 
 namespace {

 };
 }
 
 Combiner::Combiner(CombinerInfo &Info, const TargetPassConfig *TPC)
     : CInfo(Info), TPC(TPC) {
   (void)this->TPC; // FIXME: Remove when used.
 }
 
-bool Combiner::combineMachineInstrs(MachineFunction &MF) {
+bool Combiner::combineMachineInstrs(MachineFunction &MF,
+                                    GISelCSEInfo *CSEInfo) {
   // If the ISel pipeline failed, do not bother running this pass.
   // FIXME: Should this be here or in individual combiner passes.
   if (MF.getProperties().hasProperty(
           MachineFunctionProperties::Property::FailedISel))
     return false;
 
   MRI = &MF.getRegInfo();
+  MachineIRBuilder Builder(BuilderState);
   Builder.setMF(MF);
+  Builder.setCSEInfo(CSEInfo);
 
   LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n');
 
   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
 
   bool MFChanged = false;
   bool Changed;
 
for (MachineBasicBlock *MBB : post_order(&MF)) {
         }
         WorkList.insert(CurMI);
       }
     }
     // Main Loop. Process the instructions here.
     while (!WorkList.empty()) {
       MachineInstr *CurrInst = WorkList.pop_back_val();
       LLVM_DEBUG(dbgs() << "Try combining " << *CurrInst << "\n";);
-      Changed |= CInfo.combine(Observer, *CurrInst, Builder);
+      Changed |= CInfo.combine(Observer, *CurrInst, BuilderState);
     }
     MFChanged |= Changed;
   } while (Changed);
 
   return MFChanged;
 }

lib/CodeGen/GlobalISel/CombinerHelper.cpp

 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 
 #define DEBUG_TYPE "gi-combine"
 
 using namespace llvm;
 
 CombinerHelper::CombinerHelper(CombinerChangeObserver &Observer,
-                               MachineIRBuilder &B)
-    : Builder(B), MRI(Builder.getMF().getRegInfo()), Observer(Observer) {}
+                               MachineIRBuilderState &State)
+    : Builder(State), MRI(Builder.getMF().getRegInfo()), Observer(Observer) {}
 
 void CombinerHelper::eraseInstr(MachineInstr &MI) {
   Observer.erasedInstr(MI);
 }
 void CombinerHelper::scheduleForVisit(MachineInstr &MI) {
   Observer.createdInstr(MI);
 }
 

lib/CodeGen/GlobalISel/IRTranslator.cpp

if (!R.getLocation().isValid() || TPC.isGlobalISelAbortEnabled())
     R << (" (in function: " + MF.getName() + ")").str();
 
   if (TPC.isGlobalISelAbortEnabled())
     report_fatal_error(R.getMsg());
   else
     ORE.emit(R);
 }
 
-IRTranslator::IRTranslator() : MachineFunctionPass(ID) {
+IRTranslator::IRTranslator()
+    : MachineFunctionPass(ID), CurBuilder(CurBuilderState),
+      EntryBuilder(EntryBuilderState) {
   initializeIRTranslatorPass(*PassRegistry::getPassRegistry());
 }
 
 void IRTranslator::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<StackProtector>();
   AU.addRequired<TargetPassConfig>();
   getSelectionDAGFallbackAnalysisUsage(AU);
   MachineFunctionPass::getAnalysisUsage(AU);
void IRTranslator::finalizeFunction() {
   // needed during the translation.
   PendingPHIs.clear();
   VMap.reset();
   FrameIndices.clear();
   MachinePreds.clear();
   // MachineIRBuilder::DebugLoc can outlive the DILocation it holds. Clear it
   // to avoid accessing free’d memory (in runOnMachineFunction) and to avoid
   // destroying it twice (in ~IRTranslator() and ~LLVMContext())
-  EntryBuilder = MachineIRBuilder();
-  CurBuilder = MachineIRBuilder();
+  EntryBuilderState = MachineIRBuilderState();
+  CurBuilderState = MachineIRBuilderState();
 }
 
 bool IRTranslator::runOnMachineFunction(MachineFunction &CurMF) {
   MF = &CurMF;
   const Function &F = MF->getFunction();
   if (F.empty())
     return false;
   CLI = MF->getSubtarget().getCallLowering();

lib/CodeGen/GlobalISel/Legalizer.cpp

 /// instructions and the LegalizePass wrapper pass for the primary
 /// legalization.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/GlobalISel/Legalizer.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
+#include "llvm/CodeGen/GlobalISel/CSEInfo.h"
 #include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
 #include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/Support/Debug.h"
 
 #include <iterator>
 
 #define DEBUG_TYPE "legalizer"
 
 using namespace llvm;
 
 char Legalizer::ID = 0;
 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
                       "Legalize the Machine IR a function's Machine IR", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
+INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
                     "Legalize the Machine IR a function's Machine IR", false,
                     false)
 
 Legalizer::Legalizer() : MachineFunctionPass(ID) {
   initializeLegalizerPass(*PassRegistry::getPassRegistry());
 }
 
 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<TargetPassConfig>();
+  AU.addRequired<GISelCSEAnalysisWrapperPass>();
+  AU.addPreserved<GISelCSEAnalysisWrapperPass>();
   getSelectionDAGFallbackAnalysisUsage(AU);
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 void Legalizer::init(MachineFunction &MF) {
 }
 
 static bool isArtifact(const MachineInstr &MI) {

 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
   // If the ISel pipeline failed, do not bother running that pass.
   if (MF.getProperties().hasProperty(
           MachineFunctionProperties::Property::FailedISel))
     return false;
   LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
   init(MF);
   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
+  auto &WrapperPass = getAnalysis<GISelCSEAnalysisWrapperPass>();
+  auto &CSEInfo = WrapperPass.getCSEInfo();
   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
   LegalizerHelper Helper(MF);
 
   const size_t NumBlocks = MF.size();
   MachineRegisterInfo &MRI = MF.getRegInfo();
 
   // Populate Insts
   GISelWorkList<256> InstList;
for (MachineInstr &MI : *MBB) {
       if (!isPreISelGenericOpcode(MI.getOpcode()))
         continue;
       if (isArtifact(MI))
         ArtifactList.insert(&MI);
       else
         InstList.insert(&MI);
     }
   }
-  Helper.MIRBuilder.recordInsertions([&](MachineInstr *MI) {
+  Helper.MIRBuilderState.recordInsertions([&](MachineInstr *MI) {
     // Only legalize pre-isel generic instructions.
     // Legalization process could generate Target specific pseudo
     // instructions with generic types. Don't record them
     if (isPreISelGenericOpcode(MI->getOpcode())) {
       if (isArtifact(*MI))
         ArtifactList.insert(MI);
       else
         InstList.insert(MI);
     }
+    // This is needed for mutations. CSEInfo already knows about new instructions.
+    CSEInfo.recordNewInstruction(MI);
     LLVM_DEBUG(dbgs() << ".. .. New MI: " << *MI;);
   });
+  Helper.MIRBuilderState.setCSEInfo(&CSEInfo);
   const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
-  LegalizationArtifactCombiner ArtCombiner(Helper.MIRBuilder, MF.getRegInfo(), LInfo);
+  LegalizationArtifactCombiner ArtCombiner(Helper.MIRBuilderState,
+                                           MF.getRegInfo(), LInfo);
   auto RemoveDeadInstFromLists = [&InstList,
                                   &ArtifactList](MachineInstr *DeadMI) {
     InstList.remove(DeadMI);
     ArtifactList.remove(DeadMI);
   };
   bool Changed = false;
   do {
     while (!InstList.empty()) {
       MachineInstr &MI = *InstList.pop_back_val();
       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
       if (isTriviallyDead(MI, MRI)) {
         LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
         MI.eraseFromParentAndMarkDBGValuesForRemoval();
         continue;
       }
 
       // Do the legalization for this instruction.
       auto Res = Helper.legalizeInstrStep(MI);
       // Error out if we couldn't legalize this instruction. We may want to
       // fall back to DAG ISel instead in the future.
       if (Res == LegalizerHelper::UnableToLegalize) {
-        Helper.MIRBuilder.stopRecordingInsertions();
+        Helper.MIRBuilderState.stopRecordingInsertions();
         reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
                            "unable to legalize instruction", MI);
         return false;
       }
       Changed |= Res == LegalizerHelper::Legalized;
+      // Assume the current inst is erased.
     }
     while (!ArtifactList.empty()) {
       MachineInstr &MI = *ArtifactList.pop_back_val();
       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
       if (isTriviallyDead(MI, MRI)) {
         LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
         RemoveDeadInstFromLists(&MI);
         MI.eraseFromParentAndMarkDBGValuesForRemoval();

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

 #include "llvm/Support/raw_ostream.h"
 
 #define DEBUG_TYPE "legalizer"
 
 using namespace llvm;
 using namespace LegalizeActions;
 
 LegalizerHelper::LegalizerHelper(MachineFunction &MF)
-    : MRI(MF.getRegInfo()), LI(*MF.getSubtarget().getLegalizerInfo()) {
-  MIRBuilder.setMF(MF);
+    : MIRBuilder(MIRBuilderState), MRI(MF.getRegInfo()),
+      LI(*MF.getSubtarget().getLegalizerInfo()) {
+  MIRBuilderState.setMF(MF);
 }
 
 LegalizerHelper::LegalizerHelper(MachineFunction &MF, const LegalizerInfo &LI)
-    : MRI(MF.getRegInfo()), LI(LI) {
-  MIRBuilder.setMF(MF);
+    : MIRBuilder(MIRBuilderState), MRI(MF.getRegInfo()), LI(LI) {
+  MIRBuilderState.setMF(MF);
 }
 LegalizerHelper::LegalizeResult
 LegalizerHelper::legalizeInstrStep(MachineInstr &MI) {
   LLVM_DEBUG(dbgs() << "Legalizing: "; MI.print(dbgs()));
 
   auto Step = LI.getAction(MI, MRI);
   switch (Step.Action) {
   case Legal:
LegalizerHelper::legalizeInstrStep(MachineInstr &MI) {
   case Lower:
     LLVM_DEBUG(dbgs() << ".. Lower\n");
     return lower(MI, Step.TypeIdx, Step.NewType);
   case FewerElements:
     LLVM_DEBUG(dbgs() << ".. Reduce number of elements\n");
     return fewerElementsVector(MI, Step.TypeIdx, Step.NewType);
   case Custom:
     LLVM_DEBUG(dbgs() << ".. Custom legalization\n");
-    return LI.legalizeCustom(MI, MRI, MIRBuilder) ? Legalized
+    return LI.legalizeCustom(MI, MRI, MIRBuilderState) ? Legalized
                                                        : UnableToLegalize;
   default:
     LLVM_DEBUG(dbgs() << ".. Unable to legalize\n");
     return UnableToLegalize;
   }
 }
 
 void LegalizerHelper::extractParts(unsigned Reg, LLT Ty, int NumParts,
                                    SmallVectorImpl<unsigned> &VRegs) {
static RTLIB::Libcall getRTLibDesc(unsigned Opcode, unsigned Size) {
   case TargetOpcode::G_FMA:
     assert((Size == 32 || Size == 64) && "Unsupported size");
     return Size == 64 ? RTLIB::FMA_F64 : RTLIB::FMA_F32;
   }
   llvm_unreachable("Unknown libcall function");
 }
 
 LegalizerHelper::LegalizeResult
-llvm::createLibcall(MachineIRBuilder &MIRBuilder, RTLIB::Libcall Libcall,
+llvm::createLibcall(MachineIRBuilderState &State, RTLIB::Libcall Libcall,
                     const CallLowering::ArgInfo &Result,
                     ArrayRef<CallLowering::ArgInfo> Args) {
+  MachineIRBuilder MIRBuilder(State);
   auto &CLI = *MIRBuilder.getMF().getSubtarget().getCallLowering();
   auto &TLI = *MIRBuilder.getMF().getSubtarget().getTargetLowering();
   const char *Name = TLI.getLibcallName(Libcall);
 
   MIRBuilder.getMF().getFrameInfo().setHasCalls(true);
   if (!CLI.lowerCall(MIRBuilder, TLI.getLibcallCallingConv(Libcall),
                      MachineOperand::CreateES(Name), Result, Args))
     return LegalizerHelper::UnableToLegalize;
 
   return LegalizerHelper::Legalized;
 }
 
 // Useful for libcalls where all operands have the same type.
 static LegalizerHelper::LegalizeResult
-simpleLibcall(MachineInstr &MI, MachineIRBuilder &MIRBuilder, unsigned Size,
+simpleLibcall(MachineInstr &MI, MachineIRBuilderState &State, unsigned Size,
               Type *OpType) {
   auto Libcall = getRTLibDesc(MI.getOpcode(), Size);
 
   SmallVector<CallLowering::ArgInfo, 3> Args;
   for (unsigned i = 1; i < MI.getNumOperands(); i++)
     Args.push_back({MI.getOperand(i).getReg(), OpType});
-  return createLibcall(MIRBuilder, Libcall, {MI.getOperand(0).getReg(), OpType},
+  return createLibcall(State, Libcall, {MI.getOperand(0).getReg(), OpType},
                        Args);
 }
 
 static RTLIB::Libcall getConvRTLibDesc(unsigned Opcode, Type *ToType,
                                        Type *FromType) {
   auto ToMVT = MVT::getVT(ToType);
   auto FromMVT = MVT::getVT(FromType);
 
case TargetOpcode::G_SITOFP:
     return RTLIB::getSINTTOFP(FromMVT, ToMVT);
   case TargetOpcode::G_UITOFP:
     return RTLIB::getUINTTOFP(FromMVT, ToMVT);
   }
   llvm_unreachable("Unsupported libcall function");
 }
 
 static LegalizerHelper::LegalizeResult
-conversionLibcall(MachineInstr &MI, MachineIRBuilder &MIRBuilder, Type *ToType,
+conversionLibcall(MachineInstr &MI, MachineIRBuilderState &State, Type *ToType,
                   Type *FromType) {
   RTLIB::Libcall Libcall = getConvRTLibDesc(MI.getOpcode(), ToType, FromType);
-  return createLibcall(MIRBuilder, Libcall, {MI.getOperand(0).getReg(), ToType},
+  return createLibcall(State, Libcall, {MI.getOperand(0).getReg(), ToType},
                        {{MI.getOperand(1).getReg(), FromType}});
 }
 
 LegalizerHelper::LegalizeResult
 LegalizerHelper::libcall(MachineInstr &MI) {
   LLT LLTy = MRI.getType(MI.getOperand(0).getReg());
   unsigned Size = LLTy.getSizeInBits();
   auto &Ctx = MIRBuilder.getMF().getFunction().getContext();
 
   MIRBuilder.setInstr(MI);
 
   switch (MI.getOpcode()) {
   default:
     return UnableToLegalize;
   case TargetOpcode::G_SDIV:
   case TargetOpcode::G_UDIV:
   case TargetOpcode::G_SREM:
   case TargetOpcode::G_UREM: {
     Type *HLTy = Type::getInt32Ty(Ctx);
-    auto Status = simpleLibcall(MI, MIRBuilder, Size, HLTy);
+    auto Status = simpleLibcall(MI, MIRBuilderState, Size, HLTy);
     if (Status != Legalized)
       return Status;
     break;
   }
   case TargetOpcode::G_FADD:
   case TargetOpcode::G_FSUB:
   case TargetOpcode::G_FMUL:
   case TargetOpcode::G_FDIV:
   case TargetOpcode::G_FMA:
   case TargetOpcode::G_FPOW:
   case TargetOpcode::G_FREM: {
     Type *HLTy = Size == 64 ? Type::getDoubleTy(Ctx) : Type::getFloatTy(Ctx);
-    auto Status = simpleLibcall(MI, MIRBuilder, Size, HLTy);
+    auto Status = simpleLibcall(MI, MIRBuilderState, Size, HLTy);
     if (Status != Legalized)
       return Status;
     break;
   }
   case TargetOpcode::G_FPEXT: {
     // FIXME: Support other floating point types (half, fp128 etc)
     unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
     unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
     if (ToSize != 64 || FromSize != 32)
       return UnableToLegalize;
     LegalizeResult Status = conversionLibcall(
-        MI, MIRBuilder, Type::getDoubleTy(Ctx), Type::getFloatTy(Ctx));
+        MI, MIRBuilderState, Type::getDoubleTy(Ctx), Type::getFloatTy(Ctx));
     if (Status != Legalized)
       return Status;
     break;
   }
   case TargetOpcode::G_FPTRUNC: {
     // FIXME: Support other floating point types (half, fp128 etc)
     unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
     unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
     if (ToSize != 32 || FromSize != 64)
       return UnableToLegalize;
     LegalizeResult Status = conversionLibcall(
-        MI, MIRBuilder, Type::getFloatTy(Ctx), Type::getDoubleTy(Ctx));
+        MI, MIRBuilderState, Type::getFloatTy(Ctx), Type::getDoubleTy(Ctx));
     if (Status != Legalized)
       return Status;
     break;
   }
   case TargetOpcode::G_FPTOSI:
   case TargetOpcode::G_FPTOUI: {
     // FIXME: Support other types
     unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
     unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
     if (ToSize != 32 || (FromSize != 32 && FromSize != 64))
       return UnableToLegalize;
     LegalizeResult Status = conversionLibcall(
-        MI, MIRBuilder, Type::getInt32Ty(Ctx),
+        MI, MIRBuilderState, Type::getInt32Ty(Ctx),
         FromSize == 64 ? Type::getDoubleTy(Ctx) : Type::getFloatTy(Ctx));
     if (Status != Legalized)
       return Status;
     break;
   }
   case TargetOpcode::G_SITOFP:
   case TargetOpcode::G_UITOFP: {
     // FIXME: Support other types
     unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
     unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
     if (FromSize != 32 || (ToSize != 32 && ToSize != 64))
       return UnableToLegalize;
     LegalizeResult Status = conversionLibcall(
-        MI, MIRBuilder,
+        MI, MIRBuilderState,
         ToSize == 64 ? Type::getDoubleTy(Ctx) : Type::getFloatTy(Ctx),
         Type::getInt32Ty(Ctx));
     if (Status != Legalized)
       return Status;
     break;
   }
   }
 

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

LegalizerInfo::getAction(const MachineInstr &MI,
   return getAction({MI.getOpcode(), Types, MemDescrs});
 }
 
 bool LegalizerInfo::isLegal(const MachineInstr &MI,
                             const MachineRegisterInfo &MRI) const {
   return getAction(MI, MRI).Action == Legal;
 }
 
-bool LegalizerInfo::legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
-                                   MachineIRBuilder &MIRBuilder) const {
+bool LegalizerInfo::legalizeCustom(
+    MachineInstr &MI, MachineRegisterInfo &MRI,
+    MachineIRBuilderState &MIRBuilderState) const {
   return false;
 }
 
 LegalizerInfo::SizeAndActionsVec
 LegalizerInfo::increaseToLargerTypesAndDecreaseToLargest(
     const SizeAndActionsVec &v, LegalizeAction IncreaseAction,
     LegalizeAction DecreaseAction) {
   SizeAndActionsVec result;

lib/CodeGen/GlobalISel/MachineIRBuilder.cpp

 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetOpcodes.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/IR/DebugInfo.h"
 
 using namespace llvm;
 
-void MachineIRBuilderBase::setMF(MachineFunction &MF) {
-  State.MF = &MF;
-  State.MBB = nullptr;
-  State.MRI = &MF.getRegInfo();
-  State.TII = MF.getSubtarget().getInstrInfo();
-  State.DL = DebugLoc();
-  State.II = MachineBasicBlock::iterator();
-  State.InsertedInstr = nullptr;
-}
-
-void MachineIRBuilderBase::setMBB(MachineBasicBlock &MBB) {
-  State.MBB = &MBB;
-  State.II = MBB.end();
-  assert(&getMF() == MBB.getParent() &&
-         "Basic block is in a different function");
+void MachineIRBuilderState::setMF(MachineFunction &MF) {
+  this->MF = &MF;
+  MBB = nullptr;
+  MRI = &MF.getRegInfo();
+  TII = MF.getSubtarget().getInstrInfo();
+  DL = DebugLoc();
+  II = MachineBasicBlock::iterator();
+  InsertedInstr = nullptr;
+}
+
+void MachineIRBuilderState::setMBB(MachineBasicBlock &MBB) {
+  this->MBB = &MBB;
+  II = MBB.end();
+  assert(MF == MBB.getParent() && "Basic block is in a different function");
 }
 
-void MachineIRBuilderBase::setInstr(MachineInstr &MI) {
+void MachineIRBuilderState::setInstr(MachineInstr &MI) {
   assert(MI.getParent() && "Instruction is not part of a basic block");
   setMBB(*MI.getParent());
-  State.II = MI.getIterator();
+  II = MI.getIterator();
 }
 
 void MachineIRBuilderBase::setInsertPt(MachineBasicBlock &MBB,
                                        MachineBasicBlock::iterator II) {
   assert(MBB.getParent() == &getMF() &&
          "Basic block is in a different function");
   State.MBB = &MBB;
   State.II = II;
 }
 
 void MachineIRBuilderBase::recordInsertion(MachineInstr *InsertedInstr) const {
   if (State.InsertedInstr)
     State.InsertedInstr(InsertedInstr);
 }
 
+void MachineIRBuilderState::recordInsertions(
+    std::function<void(MachineInstr *)> Inserted) {
+  InsertedInstr = std::move(Inserted);
+}
+
+void MachineIRBuilderState::stopRecordingInsertions() {
+  InsertedInstr = nullptr;
+}
+
 void MachineIRBuilderBase::recordInsertions(
     std::function<void(MachineInstr *)> Inserted) {
   State.InsertedInstr = std::move(Inserted);
 }
 
 void MachineIRBuilderBase::stopRecordingInsertions() {
   State.InsertedInstr = nullptr;
 }

lib/CodeGen/GlobalISel/RegBankSelect.cpp

 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
 INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE,
                     "Assign register bank of generic virtual registers", false,
                     false)
 
 RegBankSelect::RegBankSelect(Mode RunningMode)
-    : MachineFunctionPass(ID), OptMode(RunningMode) {
+    : MachineFunctionPass(ID), MIRBuilder(MIRBuilderState),
+      OptMode(RunningMode) {
   initializeRegBankSelectPass(*PassRegistry::getPassRegistry());
   if (RegBankSelectMode.getNumOccurrences() != 0) {
     OptMode = RegBankSelectMode;
     if (RegBankSelectMode != RunningMode)
       LLVM_DEBUG(dbgs() << "RegBankSelect mode overrided by command line\n");
   }
 }
 

lib/CodeGen/GlobalISel/Utils.cpp

APFloat llvm::getAPFloatFromSize(double Val, unsigned Size) {
   if (Size != 16)
     llvm_unreachable("Unsupported FPConstant size");
   bool Ignored;
   APFloat APF(Val);
   APF.convert(APFloat::IEEEhalf(), APFloat::rmNearestTiesToEven, &Ignored);
   return APF;
 }
 
+Optional<APInt> llvm::ConstantFoldBinOp(unsigned Opcode, const unsigned Op1,
+                                        const unsigned Op2,
+                                        const MachineRegisterInfo &MRI) {
+  auto MaybeOp1Cst = getConstantVRegVal(Op1, MRI);
+  auto MaybeOp2Cst = getConstantVRegVal(Op2, MRI);
+  if (MaybeOp1Cst && MaybeOp2Cst) {
+    LLT Ty = MRI.getType(Op1);
+    APInt C1(Ty.getSizeInBits(), *MaybeOp1Cst, true);
+    APInt C2(Ty.getSizeInBits(), *MaybeOp2Cst, true);
+    switch (Opcode) {
+    default:
+      break;
+    case TargetOpcode::G_ADD:
+      return C1 + C2;
+    case TargetOpcode::G_AND:
+      return C1 & C2;
+    case TargetOpcode::G_ASHR:
+      return C1.ashr(C2);
+    case TargetOpcode::G_LSHR:
+      return C1.lshr(C2);
+    case TargetOpcode::G_MUL:
+      return C1 * C2;
+    case TargetOpcode::G_OR:
+      return C1 | C2;
+    case TargetOpcode::G_SHL:
+      return C1 << C2;
+    case TargetOpcode::G_SUB:
+      return C1 - C2;
+    case TargetOpcode::G_XOR:
+      return C1 ^ C2;
+    case TargetOpcode::G_UDIV:
+      if (!C2.getBoolValue())
+        break;
+      return C1.udiv(C2);
+    case TargetOpcode::G_SDIV:
+      if (!C2.getBoolValue())
+        break;
+      return C1.sdiv(C2);
+    case TargetOpcode::G_UREM:
+      if (!C2.getBoolValue())
+        break;
+      return C1.urem(C2);
+    case TargetOpcode::G_SREM:
+      if (!C2.getBoolValue())
+        break;
+      return C1.srem(C2);
+    }
+  }
+  return None;
+}
+
 void llvm::getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU) {
   AU.addPreserved<StackProtector>();
 }

lib/Target/AArch64/AArch64InstructionSelector.cpp

bool AArch64InstructionSelector::selectVaStartDarwin(
   return true;
 }
 
 void AArch64InstructionSelector::materializeLargeCMVal(
     MachineInstr &I, const Value *V, unsigned char OpFlags) const {
   MachineBasicBlock &MBB = *I.getParent();
   MachineFunction &MF = *MBB.getParent();
   MachineRegisterInfo &MRI = MF.getRegInfo();
-  MachineIRBuilder MIB(I);
+  MachineIRBuilderState State;
+  MachineIRBuilder MIB(I, State);
 
   auto MovZ = MIB.buildInstr(AArch64::MOVZXi, &AArch64::GPR64RegClass);
   MovZ->addOperand(MF, I.getOperand(1));
   MovZ->getOperand(1).setTargetFlags(OpFlags | AArch64II::MO_G0 |
                                      AArch64II::MO_NC);
   MovZ->addOperand(MF, MachineOperand::CreateImm(0));
   constrainSelectedInstRegOperands(*MovZ, TII, TRI, RBI);
 

lib/Target/AArch64/AArch64LegalizerInfo.h

 class AArch64Subtarget;
 
 /// This class provides the information for the target register banks.
 class AArch64LegalizerInfo : public LegalizerInfo {
 public:
   AArch64LegalizerInfo(const AArch64Subtarget &ST);
 
   bool legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
-                      MachineIRBuilder &MIRBuilder) const override;
+                      MachineIRBuilderState &) const override;
 
 private:
   bool legalizeVaArg(MachineInstr &MI, MachineRegisterInfo &MRI,
-                     MachineIRBuilder &MIRBuilder) const;
+                     MachineIRBuilderState &State) const;
 };
 } // End llvm namespace.
 #endif

lib/Target/AArch64/AArch64LegalizerInfo.cpp

AArch64LegalizerInfo::AArch64LegalizerInfo(const AArch64Subtarget &ST) {
   }
 
   computeTables();
   verify(*ST.getInstrInfo());
 }
 
 bool AArch64LegalizerInfo::legalizeCustom(MachineInstr &MI,
                                           MachineRegisterInfo &MRI,
-                                          MachineIRBuilder &MIRBuilder) const {
+                                          MachineIRBuilderState &State) const {
   switch (MI.getOpcode()) {
   default:
     // No idea what to do.
     return false;
   case TargetOpcode::G_VAARG:
-    return legalizeVaArg(MI, MRI, MIRBuilder);
+    return legalizeVaArg(MI, MRI, State);
   }
 
   llvm_unreachable("expected switch to return");
 }
 
 bool AArch64LegalizerInfo::legalizeVaArg(MachineInstr &MI,
                                          MachineRegisterInfo &MRI,
-                                         MachineIRBuilder &MIRBuilder) const {
+                                         MachineIRBuilderState &State) const {
+  MachineIRBuilder MIRBuilder(State);
   MIRBuilder.setInstr(MI);
   MachineFunction &MF = MIRBuilder.getMF();
   unsigned Align = MI.getOperand(2).getImm();
   unsigned Dst = MI.getOperand(0).getReg();
   unsigned ListPtr = MI.getOperand(1).getReg();
 
   LLT PtrTy = MRI.getType(ListPtr);
   LLT IntPtrTy = LLT::scalar(PtrTy.getSizeInBits());

lib/Target/AArch64/AArch64PreLegalizerCombiner.cpp

 
 namespace {
 class AArch64PreLegalizerCombinerInfo : public CombinerInfo {
 public:
   AArch64PreLegalizerCombinerInfo()
       : CombinerInfo(/*AllowIllegalOps*/ true, /*ShouldLegalizeIllegal*/ false,
                      /*LegalizerInfo*/ nullptr) {}
   virtual bool combine(CombinerChangeObserver &Observer, MachineInstr &MI,
-                       MachineIRBuilder &B) const override;
+                       MachineIRBuilderState &State) const override;
 };
 
 bool AArch64PreLegalizerCombinerInfo::combine(CombinerChangeObserver &Observer,
                                               MachineInstr &MI,
-                                              MachineIRBuilder &B) const {
-  CombinerHelper Helper(Observer, B);
+                                              MachineIRBuilderState &State) const {
+  CombinerHelper Helper(Observer, State);
 
   switch (MI.getOpcode()) {
   default:
     return false;
   case TargetOpcode::G_LOAD:
   case TargetOpcode::G_SEXTLOAD:
   case TargetOpcode::G_ZEXTLOAD:
     return Helper.tryCombineExtendingLoads(MI);

 
 bool AArch64PreLegalizerCombiner::runOnMachineFunction(MachineFunction &MF) {
   if (MF.getProperties().hasProperty(
           MachineFunctionProperties::Property::FailedISel))
     return false;
   auto *TPC = &getAnalysis<TargetPassConfig>();
   AArch64PreLegalizerCombinerInfo PCInfo;
   Combiner C(PCInfo, TPC);
-  return C.combineMachineInstrs(MF);
+  return C.combineMachineInstrs(MF, /*CSEInfo*/nullptr);
 }
 
 char AArch64PreLegalizerCombiner::ID = 0;
 INITIALIZE_PASS_BEGIN(AArch64PreLegalizerCombiner, DEBUG_TYPE,
                       "Combine AArch64 machine instrs before legalization",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
 INITIALIZE_PASS_END(AArch64PreLegalizerCombiner, DEBUG_TYPE,

lib/Target/ARM/ARMLegalizerInfo.h

 class ARMSubtarget;
 
 /// This class provides the information for the target register banks.
 class ARMLegalizerInfo : public LegalizerInfo {
 public:
   ARMLegalizerInfo(const ARMSubtarget &ST);
 
   bool legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
-                      MachineIRBuilder &MIRBuilder) const override;
+                      MachineIRBuilderState &State) const override;
 
 private:
   void setFCmpLibcallsGNU();
   void setFCmpLibcallsAEABI();
 
   struct FCmpLibcallInfo {
     // Which libcall this is.
     RTLIB::Libcall LibcallID;

lib/Target/ARM/ARMLegalizerInfo.cpp

if (Size == 32)
     return FCmp32Libcalls[Predicate];
   if (Size == 64)
     return FCmp64Libcalls[Predicate];
   llvm_unreachable("Unsupported size for FCmp predicate");
 }
 
 bool ARMLegalizerInfo::legalizeCustom(MachineInstr &MI,
                                       MachineRegisterInfo &MRI,
-                                      MachineIRBuilder &MIRBuilder) const {
+                                      MachineIRBuilderState &State) const {
   using namespace TargetOpcode;
 
+  MachineIRBuilder MIRBuilder(State);
   MIRBuilder.setInstr(MI);
   LLVMContext &Ctx = MIRBuilder.getMF().getFunction().getContext();
 
   switch (MI.getOpcode()) {
   default:
     return false;
   case G_SREM:
   case G_UREM: {
     unsigned OriginalResult = MI.getOperand(0).getReg();
     auto Size = MRI.getType(OriginalResult).getSizeInBits();
     if (Size != 32)
       return false;
 
     auto Libcall =
         MI.getOpcode() == G_SREM ? RTLIB::SDIVREM_I32 : RTLIB::UDIVREM_I32;
 
     // Our divmod libcalls return a struct containing the quotient and the
     // remainder. We need to create a virtual register for it.
     Type *ArgTy = Type::getInt32Ty(Ctx);
     StructType *RetTy = StructType::get(Ctx, {ArgTy, ArgTy}, /* Packed */ true);
     auto RetVal = MRI.createGenericVirtualRegister(
         getLLTForType(*RetTy, MIRBuilder.getMF().getDataLayout()));
 
-    auto Status = createLibcall(MIRBuilder, Libcall, {RetVal, RetTy},
+    auto Status = createLibcall(State, Libcall, {RetVal, RetTy},
                                 {{MI.getOperand(1).getReg(), ArgTy},
                                  {MI.getOperand(2).getReg(), ArgTy}});
     if (Status != LegalizerHelper::Legalized)
       return false;
 
     // The remainder is the second result of divmod. Split the return value into
     // a new, unused register for the quotient and the destination of the
     // original instruction for the remainder.
case G_FCMP: {
     assert((OpSize == 32 || OpSize == 64) && "Unsupported operand size");
     auto *ArgTy = OpSize == 32 ? Type::getFloatTy(Ctx) : Type::getDoubleTy(Ctx);
     auto *RetTy = Type::getInt32Ty(Ctx);
 
     SmallVector<unsigned, 2> Results;
     for (auto Libcall : Libcalls) {
       auto LibcallResult = MRI.createGenericVirtualRegister(LLT::scalar(32));
       auto Status =
-          createLibcall(MIRBuilder, Libcall.LibcallID, {LibcallResult, RetTy},
+          createLibcall(State, Libcall.LibcallID, {LibcallResult, RetTy},
                         {{MI.getOperand(2).getReg(), ArgTy},
                          {MI.getOperand(3).getReg(), ArgTy}});
 
       if (Status != LegalizerHelper::Legalized)
         return false;
 
       auto ProcessedResult =
           Libcalls.size() == 1

test/CodeGen/AArch64/GlobalISel/gisel-commandline-option.ll

 ; RUN: llc -mtriple=aarch64-- -debug-pass=Structure %s -o /dev/null 2>&1 \
 ; RUN:   | FileCheck %s --check-prefix DISABLED
 
 ; RUN: llc -mtriple=aarch64-- -fast-isel=0 -global-isel=false \
 ; RUN: -debug-pass=Structure %s -o /dev/null 2>&1 | FileCheck %s --check-prefix DISABLED
 
 ; ENABLED:       IRTranslator
 ; ENABLED-NEXT:  PreLegalizerCombiner
+; ENABLED-NEXT:  Analysis containing CSE Info
 ; ENABLED-NEXT:  Legalizer
 ; ENABLED-NEXT:  RegBankSelect
 ; ENABLED-O0-NEXT:  Localizer
 ; ENABLED-NEXT:  InstructionSelect
 ; ENABLED-NEXT:  ResetMachineFunction
 
 ; FALLBACK:       AArch64 Instruction Selection
 ; NOFALLBACK-NOT: AArch64 Instruction Selection

test/CodeGen/AArch64/GlobalISel/legalize-cmp.mir

bb.0.entry:
     ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
     ; CHECK: [[COPY1:%[0-9]+]]:_(s64) = COPY $x0
     ; CHECK: [[ICMP:%[0-9]+]]:_(s32) = G_ICMP intpred(sge), [[COPY]](s64), [[COPY1]]
     ; CHECK: [[COPY2:%[0-9]+]]:_(s32) = COPY [[ICMP]](s32)
     ; CHECK: $w0 = COPY [[COPY2]](s32)
     ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
     ; CHECK: [[TRUNC:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
     ; CHECK: [[AND:%[0-9]+]]:_(s32) = G_AND [[TRUNC]], [[C]]
-    ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
     ; CHECK: [[TRUNC1:%[0-9]+]]:_(s32) = G_TRUNC [[COPY1]](s64)
-    ; CHECK: [[AND1:%[0-9]+]]:_(s32) = G_AND [[TRUNC1]], [[C1]]
+    ; CHECK: [[AND1:%[0-9]+]]:_(s32) = G_AND [[TRUNC1]], [[C]]
     ; CHECK: [[ICMP1:%[0-9]+]]:_(s32) = G_ICMP intpred(ult), [[AND]](s32), [[AND1]]
     ; CHECK: [[COPY3:%[0-9]+]]:_(s32) = COPY [[ICMP1]](s32)
     ; CHECK: $w0 = COPY [[COPY3]](s32)
     ; CHECK: [[INTTOPTR:%[0-9]+]]:_(p0) = G_INTTOPTR [[COPY]](s64)
     ; CHECK: [[ICMP2:%[0-9]+]]:_(s32) = G_ICMP intpred(eq), [[INTTOPTR]](p0), [[INTTOPTR]]
     ; CHECK: [[COPY4:%[0-9]+]]:_(s32) = COPY [[ICMP2]](s32)
     ; CHECK: $w0 = COPY [[COPY4]](s32)
     %0(s64) = COPY $x0

test/CodeGen/AArch64/GlobalISel/legalize-div.mir

bb.0.entry:
     liveins: $x0, $x1, $x2, $x3
     ; CHECK-LABEL: name: test_div
     ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
     ; CHECK: [[COPY1:%[0-9]+]]:_(s64) = COPY $x1
     ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 24
     ; CHECK: [[TRUNC:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
     ; CHECK: [[SHL:%[0-9]+]]:_(s32) = G_SHL [[TRUNC]], [[C]]
     ; CHECK: [[ASHR:%[0-9]+]]:_(s32) = G_ASHR [[SHL]], [[C]]
-    ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 24
     ; CHECK: [[TRUNC1:%[0-9]+]]:_(s32) = G_TRUNC [[COPY1]](s64)
-    ; CHECK: [[SHL1:%[0-9]+]]:_(s32) = G_SHL [[TRUNC1]], [[C1]]
-    ; CHECK: [[ASHR1:%[0-9]+]]:_(s32) = G_ASHR [[SHL1]], [[C1]]
+    ; CHECK: [[SHL1:%[0-9]+]]:_(s32) = G_SHL [[TRUNC1]], [[C]]
+    ; CHECK: [[ASHR1:%[0-9]+]]:_(s32) = G_ASHR [[SHL1]], [[C]]
     ; CHECK: [[SDIV:%[0-9]+]]:_(s32) = G_SDIV [[ASHR]], [[ASHR1]]
     ; CHECK: [[COPY2:%[0-9]+]]:_(s32) = COPY [[SDIV]](s32)
     ; CHECK: $w0 = COPY [[COPY2]](s32)
-    ; CHECK: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
+    ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
     ; CHECK: [[TRUNC2:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
-    ; CHECK: [[AND:%[0-9]+]]:_(s32) = G_AND [[TRUNC2]], [[C2]]
-    ; CHECK: [[C3:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
+    ; CHECK: [[AND:%[0-9]+]]:_(s32) = G_AND [[TRUNC2]], [[C1]]
     ; CHECK: [[TRUNC3:%[0-9]+]]:_(s32) = G_TRUNC [[COPY1]](s64)
-    ; CHECK: [[AND1:%[0-9]+]]:_(s32) = G_AND [[TRUNC3]], [[C3]]
+    ; CHECK: [[AND1:%[0-9]+]]:_(s32) = G_AND [[TRUNC3]], [[C1]]
     ; CHECK: [[UDIV:%[0-9]+]]:_(s32) = G_UDIV [[AND]], [[AND1]]
     ; CHECK: [[COPY3:%[0-9]+]]:_(s32) = COPY [[UDIV]](s32)
     ; CHECK: $w0 = COPY [[COPY3]](s32)
     %0(s64) = COPY $x0
     %1(s64) = COPY $x1
     %2(s8) = G_TRUNC %0
     %3(s8) = G_TRUNC %1
 

test/CodeGen/AArch64/GlobalISel/legalize-phi.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
 # RUN: llc -mtriple=aarch64-unknown-unknown -verify-machineinstrs -run-pass=legalizer %s -o - | FileCheck %s
 --- |
   ; ModuleID = '/tmp/test.ll'
   source_filename = "/tmp/test.ll"
   target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
   target triple = "aarch64-unknown-unknown"
 
   define i32 @legalize_phi(i32 %argc) {
body:             |
   ; CHECK:   successors: %bb.1(0x80000000)
   ; CHECK:   liveins: $w0
   ; CHECK:   [[COPY:%[0-9]+]]:_(s32) = COPY $w0
   ; CHECK:   [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 1
   ; CHECK:   [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 0
   ; CHECK:   [[TRUNC:%[0-9]+]]:_(s16) = G_TRUNC [[C1]](s32)
   ; CHECK: bb.1:
   ; CHECK:   successors: %bb.1(0x40000000), %bb.2(0x40000000)
-  ; CHECK:   [[PHI:%[0-9]+]]:_(s16) = G_PHI [[TRUNC]](s16), %bb.0, [[TRUNC3:%[0-9]+]](s16), %bb.1
+  ; CHECK:   [[PHI:%[0-9]+]]:_(s16) = G_PHI [[TRUNC]](s16), %bb.0, %13(s16), %bb.1
   ; CHECK:   [[ANYEXT:%[0-9]+]]:_(s32) = G_ANYEXT [[PHI]](s16)
   ; CHECK:   [[COPY1:%[0-9]+]]:_(s32) = COPY [[C]](s32)
   ; CHECK:   [[ADD:%[0-9]+]]:_(s32) = G_ADD [[ANYEXT]], [[COPY1]]
   ; CHECK:   [[TRUNC1:%[0-9]+]]:_(s8) = G_TRUNC [[ADD]](s32)
   ; CHECK:   [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
   ; CHECK:   [[COPY2:%[0-9]+]]:_(s32) = COPY [[ADD]](s32)
   ; CHECK:   [[AND:%[0-9]+]]:_(s32) = G_AND [[COPY2]], [[C2]]
   ; CHECK:   [[ICMP:%[0-9]+]]:_(s32) = G_ICMP intpred(ugt), [[AND]](s32), [[COPY]]
   ; CHECK:   [[TRUNC2:%[0-9]+]]:_(s1) = G_TRUNC [[ICMP]](s32)
-  ; CHECK:   [[TRUNC3]]:_(s16) = G_TRUNC [[ADD]](s32)
+  ; CHECK:   [[TRUNC3:%[0-9]+]]:_(s16) = G_TRUNC [[ADD]](s32)
   ; CHECK:   G_BRCOND [[TRUNC2]](s1), %bb.1
   ; CHECK: bb.2:
   ; CHECK:   [[C3:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
   ; CHECK:   [[COPY3:%[0-9]+]]:_(s32) = COPY [[ADD]](s32)
   ; CHECK:   [[AND1:%[0-9]+]]:_(s32) = G_AND [[COPY3]], [[C3]]
   ; CHECK:   $w0 = COPY [[AND1]](s32)
   ; CHECK:   RET_ReallyLR implicit $w0
   bb.0:
body:             |
   ; CHECK: bb.0:
   ; CHECK:   successors: %bb.1(0x80000000)
   ; CHECK:   liveins: $w0
   ; CHECK:   [[COPY:%[0-9]+]]:_(s32) = COPY $w0
   ; CHECK:   [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 0
   ; CHECK:   [[TRUNC:%[0-9]+]]:_(s16) = G_TRUNC [[C]](s32)
   ; CHECK: bb.1:
   ; CHECK:   successors: %bb.1(0x40000000), %bb.2(0x40000000)
-  ; CHECK:   [[PHI:%[0-9]+]]:_(s16) = G_PHI [[TRUNC]](s16), %bb.0, [[COPY1:%[0-9]+]](s16), %bb.1
+  ; CHECK:   [[PHI:%[0-9]+]]:_(s16) = G_PHI [[TRUNC]](s16), %bb.0, %7(s16), %bb.1
   ; CHECK:   [[TRUNC1:%[0-9]+]]:_(s8) = G_TRUNC [[PHI]](s16)
   ; CHECK:   [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
   ; CHECK:   [[ANYEXT:%[0-9]+]]:_(s32) = G_ANYEXT [[PHI]](s16)
   ; CHECK:   [[AND:%[0-9]+]]:_(s32) = G_AND [[ANYEXT]], [[C1]]
   ; CHECK:   [[ICMP:%[0-9]+]]:_(s32) = G_ICMP intpred(ugt), [[AND]](s32), [[COPY]]
   ; CHECK:   [[TRUNC2:%[0-9]+]]:_(s1) = G_TRUNC [[ICMP]](s32)
-  ; CHECK:   [[COPY1]]:_(s16) = COPY [[PHI]](s16)
+  ; CHECK:   [[COPY1:%[0-9]+]]:_(s16) = COPY [[PHI]](s16)
   ; CHECK:   G_BRCOND [[TRUNC2]](s1), %bb.1
   ; CHECK: bb.2:
   ; CHECK:   $w0 = COPY [[AND]](s32)
   ; CHECK:   RET_ReallyLR implicit $w0
   bb.0:
     successors: %bb.1(0x80000000)
     liveins: $w0
    ; Test that we properly legalize a phi that uses itself
body:             |
   ; CHECK:   [[TRUNC:%[0-9]+]]:_(s1) = G_TRUNC [[ICMP]](s32)
   ; CHECK:   [[ADD:%[0-9]+]]:_(s32) = G_ADD [[COPY]], [[C1]]
   ; CHECK:   G_BRCOND [[TRUNC]](s1), %bb.1
   ; CHECK:   G_BR %bb.2
   ; CHECK: bb.1:
   ; CHECK:   successors: %bb.3(0x80000000)
   ; CHECK:   [[ADD1:%[0-9]+]]:_(s32) = G_ADD [[COPY]], [[C2]]
   ; CHECK:   [[TRUNC1:%[0-9]+]]:_(s16) = G_TRUNC [[ADD1]](s32)
-  ; CHECK:   [[TRUNC2:%[0-9]+]]:_(s16) = G_TRUNC [[ADD1]](s32)
   ; CHECK:   G_BR %bb.3
   ; CHECK: bb.2:
   ; CHECK:   successors: %bb.3(0x80000000)
-  ; CHECK:   [[TRUNC3:%[0-9]+]]:_(s16) = G_TRUNC [[C3]](s32)
-  ; CHECK:   [[TRUNC4:%[0-9]+]]:_(s16) = G_TRUNC [[ADD]](s32)
+  ; CHECK:   [[TRUNC2:%[0-9]+]]:_(s16) = G_TRUNC [[C3]](s32)
+  ; CHECK:   [[TRUNC3:%[0-9]+]]:_(s16) = G_TRUNC [[ADD]](s32)
   ; CHECK: bb.3:
-  ; CHECK:   [[PHI:%[0-9]+]]:_(s16) = G_PHI [[TRUNC2]](s16), %bb.1, [[TRUNC4]](s16), %bb.2
-  ; CHECK:   [[PHI1:%[0-9]+]]:_(s16) = G_PHI [[TRUNC1]](s16), %bb.1, [[TRUNC3]](s16), %bb.2
+  ; CHECK:   [[PHI:%[0-9]+]]:_(s16) = G_PHI [[TRUNC1]](s16), %bb.1, [[TRUNC3]](s16), %bb.2
+  ; CHECK:   [[PHI1:%[0-9]+]]:_(s16) = G_PHI [[TRUNC1]](s16), %bb.1, [[TRUNC2]](s16), %bb.2
   ; CHECK:   [[C4:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
   ; CHECK:   [[ANYEXT:%[0-9]+]]:_(s32) = G_ANYEXT [[PHI]](s16)
   ; CHECK:   [[AND:%[0-9]+]]:_(s32) = G_AND [[ANYEXT]], [[C4]]
-  ; CHECK:   [[C5:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
   ; CHECK:   [[ANYEXT1:%[0-9]+]]:_(s32) = G_ANYEXT [[PHI1]](s16)
-  ; CHECK:   [[AND1:%[0-9]+]]:_(s32) = G_AND [[ANYEXT1]], [[C5]]
+  ; CHECK:   [[AND1:%[0-9]+]]:_(s32) = G_AND [[ANYEXT1]], [[C4]]
   ; CHECK:   [[ADD2:%[0-9]+]]:_(s32) = G_ADD [[AND]], [[AND1]]
   ; CHECK:   $w0 = COPY [[ADD2]](s32)
   ; CHECK:   RET_ReallyLR implicit $w0
   bb.0:
     successors: %bb.1(0x40000000), %bb.2(0x40000000)
     liveins: $w0
    ; Make sure that we correctly insert the new legalized G_PHI at the
    ; correct location (ie make sure G_PHIs are the first insts in the BB).
body:             |
   ; CHECK:   [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 3
   ; CHECK:   [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 1
   ; CHECK:   [[C3:%[0-9]+]]:_(s32) = G_CONSTANT i32 44
   ; CHECK:   [[C4:%[0-9]+]]:_(s32) = G_CONSTANT i32 43
   ; CHECK:   [[ICMP:%[0-9]+]]:_(s32) = G_ICMP intpred(ugt), [[COPY]](s32), [[C]]
   ; CHECK:   [[TRUNC:%[0-9]+]]:_(s1) = G_TRUNC [[ICMP]](s32)
   ; CHECK:   [[ADD:%[0-9]+]]:_(s32) = G_ADD [[COPY]], [[C1]]
   ; CHECK:   [[TRUNC1:%[0-9]+]]:_(s16) = G_TRUNC [[ADD]](s32)
-  ; CHECK:   [[TRUNC2:%[0-9]+]]:_(s16) = G_TRUNC [[ADD]](s32)
   ; CHECK:   G_BRCOND [[TRUNC]](s1), %bb.1
   ; CHECK:   G_BR %bb.2
   ; CHECK: bb.1:
   ; CHECK:   successors: %bb.2(0x40000000), %bb.1(0x40000000)
-  ; CHECK:   [[PHI:%[0-9]+]]:_(s16) = G_PHI [[TRUNC2]](s16), %bb.0, [[TRUNC5:%[0-9]+]](s16), %bb.1
-  ; CHECK:   [[TRUNC3:%[0-9]+]]:_(s8) = G_TRUNC [[PHI]](s16)
+  ; CHECK:   [[PHI:%[0-9]+]]:_(s16) = G_PHI [[TRUNC1]](s16), %bb.0, %20(s16), %bb.1
+  ; CHECK:   [[TRUNC2:%[0-9]+]]:_(s8) = G_TRUNC [[PHI]](s16)
   ; CHECK:   [[C5:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
   ; CHECK:   [[ANYEXT:%[0-9]+]]:_(s32) = G_ANYEXT [[PHI]](s16)
   ; CHECK:   [[AND:%[0-9]+]]:_(s32) = G_AND [[ANYEXT]], [[C5]]
   ; CHECK:   [[ADD1:%[0-9]+]]:_(s32) = G_ADD [[AND]], [[C2]]
   ; CHECK:   [[ICMP1:%[0-9]+]]:_(s32) = G_ICMP intpred(ugt), [[ADD1]](s32), [[C3]]
-  ; CHECK:   [[TRUNC4:%[0-9]+]]:_(s1) = G_TRUNC [[ICMP1]](s32)
+  ; CHECK:   [[TRUNC3:%[0-9]+]]:_(s1) = G_TRUNC [[ICMP1]](s32)
   ; CHECK:   [[COPY2:%[0-9]+]]:_(s16) = COPY [[PHI]](s16)
-  ; CHECK:   [[TRUNC5]]:_(s16) = G_TRUNC [[C4]](s32)
-  ; CHECK:   G_BRCOND [[TRUNC4]](s1), %bb.2
+  ; CHECK:   [[TRUNC4:%[0-9]+]]:_(s16) = G_TRUNC [[C4]](s32)
+  ; CHECK:   G_BRCOND [[TRUNC3]](s1), %bb.2
   ; CHECK:   G_BR %bb.1
   ; CHECK: bb.2:
   ; CHECK:   [[PHI1:%[0-9]+]]:_(s16) = G_PHI [[COPY2]](s16), %bb.1, [[TRUNC1]](s16), %bb.0
   ; CHECK:   [[C6:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
   ; CHECK:   [[ANYEXT1:%[0-9]+]]:_(s32) = G_ANYEXT [[PHI1]](s16)
   ; CHECK:   [[AND1:%[0-9]+]]:_(s32) = G_AND [[ANYEXT1]], [[C6]]
   ; CHECK:   $w0 = COPY [[AND1]](s32)
   ; CHECK:   RET_ReallyLR implicit $w0

test/CodeGen/AArch64/GlobalISel/legalize-rem.mir

bb.0.entry:
 
     ; CHECK-LABEL: name: test_srem_8
     ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
     ; CHECK: [[COPY1:%[0-9]+]]:_(s64) = COPY $x1
     ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 24
     ; CHECK: [[TRUNC:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
     ; CHECK: [[SHL:%[0-9]+]]:_(s32) = G_SHL [[TRUNC]], [[C]]
     ; CHECK: [[ASHR:%[0-9]+]]:_(s32) = G_ASHR [[SHL]], [[C]]
-    ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 24
     ; CHECK: [[TRUNC1:%[0-9]+]]:_(s32) = G_TRUNC [[COPY1]](s64)
-    ; CHECK: [[SHL1:%[0-9]+]]:_(s32) = G_SHL [[TRUNC1]], [[C1]]
-    ; CHECK: [[ASHR1:%[0-9]+]]:_(s32) = G_ASHR [[SHL1]], [[C1]]
+    ; CHECK: [[SHL1:%[0-9]+]]:_(s32) = G_SHL [[TRUNC1]], [[C]]
+    ; CHECK: [[ASHR1:%[0-9]+]]:_(s32) = G_ASHR [[SHL1]], [[C]]
     ; CHECK: [[SDIV:%[0-9]+]]:_(s32) = G_SDIV [[ASHR]], [[ASHR1]]
     ; CHECK: [[COPY2:%[0-9]+]]:_(s32) = COPY [[SDIV]](s32)
     ; CHECK: [[TRUNC2:%[0-9]+]]:_(s32) = G_TRUNC [[COPY1]](s64)
     ; CHECK: [[MUL:%[0-9]+]]:_(s32) = G_MUL [[COPY2]], [[TRUNC2]]
     ; CHECK: [[TRUNC3:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
     ; CHECK: [[COPY3:%[0-9]+]]:_(s32) = COPY [[MUL]](s32)
     ; CHECK: [[SUB:%[0-9]+]]:_(s32) = G_SUB [[TRUNC3]], [[COPY3]]
     ; CHECK: [[COPY4:%[0-9]+]]:_(s32) = COPY [[SUB]](s32)

test/CodeGen/AArch64/GlobalISel/legalize-shift.mir

bb.0.entry:
     ; CHECK: [[SHL:%[0-9]+]]:_(s32) = G_SHL [[TRUNC]], [[C]]
     ; CHECK: [[ASHR:%[0-9]+]]:_(s32) = G_ASHR [[SHL]], [[C]]
     ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
     ; CHECK: [[TRUNC1:%[0-9]+]]:_(s32) = G_TRUNC [[COPY1]](s64)
     ; CHECK: [[AND:%[0-9]+]]:_(s32) = G_AND [[TRUNC1]], [[C1]]
     ; CHECK: [[ASHR1:%[0-9]+]]:_(s32) = G_ASHR [[ASHR]], [[AND]]
     ; CHECK: [[COPY2:%[0-9]+]]:_(s32) = COPY [[ASHR1]](s32)
     ; CHECK: $w0 = COPY [[COPY2]](s32)
-    ; CHECK: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
     ; CHECK: [[TRUNC2:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
-    ; CHECK: [[AND1:%[0-9]+]]:_(s32) = G_AND [[TRUNC2]], [[C2]]
-    ; CHECK: [[C3:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
-    ; CHECK: [[TRUNC3:%[0-9]+]]:_(s32) = G_TRUNC [[COPY1]](s64)
-    ; CHECK: [[AND2:%[0-9]+]]:_(s32) = G_AND [[TRUNC3]], [[C3]]
-    ; CHECK: [[LSHR:%[0-9]+]]:_(s32) = G_LSHR [[AND1]], [[AND2]]
+    ; CHECK: [[AND1:%[0-9]+]]:_(s32) = G_AND [[TRUNC2]], [[C1]]
+    ; CHECK: [[LSHR:%[0-9]+]]:_(s32) = G_LSHR [[AND1]], [[AND]]
     ; CHECK: [[COPY3:%[0-9]+]]:_(s32) = COPY [[LSHR]](s32)
     ; CHECK: $w0 = COPY [[COPY3]](s32)
-    ; CHECK: [[TRUNC4:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
-    ; CHECK: [[C4:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
-    ; CHECK: [[TRUNC5:%[0-9]+]]:_(s32) = G_TRUNC [[COPY1]](s64)
-    ; CHECK: [[AND3:%[0-9]+]]:_(s32) = G_AND [[TRUNC5]], [[C4]]
-    ; CHECK: [[SHL1:%[0-9]+]]:_(s32) = G_SHL [[TRUNC4]], [[AND3]]
+    ; CHECK: [[TRUNC3:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
+    ; CHECK: [[SHL1:%[0-9]+]]:_(s32) = G_SHL [[TRUNC3]], [[AND]]
     ; CHECK: [[COPY4:%[0-9]+]]:_(s32) = COPY [[SHL1]](s32)
     ; CHECK: $w0 = COPY [[COPY4]](s32)
     %0(s64) = COPY $x0
     %1(s64) = COPY $x1
     %2(s8) = G_TRUNC %0
     %3(s8) = G_TRUNC %1
 
     %4(s8) = G_ASHR %2, %3

test/CodeGen/AArch64/GlobalISel/legalize-simple.mir

registers:
   - { id: 11, class: _ }
   - { id: 12, class: _ }
   - { id: 13, class: _ }
   - { id: 14, class: _ }
   - { id: 15, class: _ }
   - { id: 16, class: _ }
 body: |
   ; CHECK-LABEL: name: test_simple
-  ; CHECK: bb.0.{{[a-zA-Z0-9]+}}:
+  ; CHECK: bb.0.entry:
   ; CHECK:   successors: %bb.1(0x80000000)
   ; CHECK:   [[COPY:%[0-9]+]]:_(s64) = COPY $x0
   ; CHECK:   [[TRUNC:%[0-9]+]]:_(s1) = G_TRUNC [[COPY]](s64)
   ; CHECK:   [[TRUNC1:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
   ; CHECK:   [[INTTOPTR:%[0-9]+]]:_(p0) = G_INTTOPTR [[COPY]](s64)
   ; CHECK:   [[PTRTOINT:%[0-9]+]]:_(s64) = G_PTRTOINT [[INTTOPTR]](p0)
   ; CHECK:   $x0 = COPY [[PTRTOINT]](s64)
   ; CHECK:   G_BRCOND [[TRUNC]](s1), %bb.1
-  ; CHECK: bb.1.{{[a-zA-Z0-9]+}}:
+  ; CHECK: bb.1.next:
   ; CHECK:   [[TRUNC2:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
-  ; CHECK:   [[TRUNC3:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
-  ; CHECK:   [[SELECT:%[0-9]+]]:_(s32) = G_SELECT [[TRUNC]](s1), [[TRUNC2]], [[TRUNC3]]
+  ; CHECK:   [[SELECT:%[0-9]+]]:_(s32) = G_SELECT [[TRUNC]](s1), [[TRUNC2]], [[TRUNC2]]
   ; CHECK:   [[COPY1:%[0-9]+]]:_(s32) = COPY [[SELECT]](s32)
   ; CHECK:   $w0 = COPY [[COPY1]](s32)
-  ; CHECK:   [[TRUNC4:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
-  ; CHECK:   [[TRUNC5:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
-  ; CHECK:   [[SELECT1:%[0-9]+]]:_(s32) = G_SELECT [[TRUNC]](s1), [[TRUNC4]], [[TRUNC5]]
+  ; CHECK:   [[TRUNC3:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
+  ; CHECK:   [[SELECT1:%[0-9]+]]:_(s32) = G_SELECT [[TRUNC]](s1), [[TRUNC3]], [[TRUNC3]]
   ; CHECK:   [[COPY2:%[0-9]+]]:_(s32) = COPY [[SELECT1]](s32)
   ; CHECK:   $w0 = COPY [[COPY2]](s32)
-  ; CHECK:   [[TRUNC6:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
-  ; CHECK:   [[TRUNC7:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
-  ; CHECK:   [[SELECT2:%[0-9]+]]:_(s32) = G_SELECT [[TRUNC]](s1), [[TRUNC6]], [[TRUNC7]]
+  ; CHECK:   [[TRUNC4:%[0-9]+]]:_(s32) = G_TRUNC [[COPY]](s64)
+  ; CHECK:   [[SELECT2:%[0-9]+]]:_(s32) = G_SELECT [[TRUNC]](s1), [[TRUNC4]], [[TRUNC4]]
   ; CHECK:   [[COPY3:%[0-9]+]]:_(s32) = COPY [[SELECT2]](s32)
   ; CHECK:   $w0 = COPY [[COPY3]](s32)
   ; CHECK:   [[SELECT3:%[0-9]+]]:_(s32) = G_SELECT [[TRUNC]](s1), [[TRUNC1]], [[TRUNC1]]
   ; CHECK:   [[SELECT4:%[0-9]+]]:_(s64) = G_SELECT [[TRUNC]](s1), [[COPY]], [[COPY]]
   ; CHECK:   $x0 = COPY [[SELECT4]](s64)
   ; CHECK:   [[BITCAST:%[0-9]+]]:_(<2 x s32>) = G_BITCAST [[COPY]](s64)
   ; CHECK:   [[BITCAST1:%[0-9]+]]:_(s64) = G_BITCAST [[BITCAST]](<2 x s32>)
   ; CHECK:   $x0 = COPY [[BITCAST1]](s64)

tools/llvm-exegesis/lib/Assembler.cpp

for (unsigned OpIndex = 0, E = Inst.getNumOperands(); OpIndex < E;
       }
     }
   }
   // Insert the return code.
   const llvm::TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
   if (TII->getReturnOpcode() < TII->getNumOpcodes()) {
     llvm::BuildMI(MBB, DL, TII->get(TII->getReturnOpcode()));
   } else {
-    llvm::MachineIRBuilder MIB(MF);
+    llvm::MachineIRBuilderState State;
+    llvm::MachineIRBuilder MIB(MF, State);
     MIB.setMBB(*MBB);
     MF.getSubtarget().getCallLowering()->lowerReturn(MIB, nullptr, 0);
   }
 }
 
 static std::unique_ptr<llvm::Module>
 createModule(const std::unique_ptr<llvm::LLVMContext> &Context,
              const llvm::DataLayout DL) {

unittests/CodeGen/GlobalISel/CMakeLists.txt

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

unittests/CodeGen/GlobalISel/CSETest.cpp

+//===- CSETest.cpp -----------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "GISelMITest.h"
+#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
+
+namespace {
+
+TEST_F(GISelMITest, TestCSE) {
+  if (!TM)
+    return;
+
+  LLT s16{LLT::scalar(16)};
+  LLT s32{LLT::scalar(32)};
+  auto MIBInput = B.buildInstr(TargetOpcode::G_TRUNC, s16, Copies[0]);
+  auto MIBInput1 = B.buildInstr(TargetOpcode::G_TRUNC, s16, Copies[1]);
+  auto MIBAdd = B.buildInstr(TargetOpcode::G_ADD, s16, MIBInput, MIBInput);
+  SmallVector<unsigned, 4> UnmergeRegs;
+  for (unsigned i = 0; i < 2; ++i)
+    UnmergeRegs.push_back(MRI->createGenericVirtualRegister(s32));
+  GISelCSEInfo CSEInfo;
+  CSEInfo.analyze(*MF);
+  B.setCSEInfo(&CSEInfo);
+  CSEMIRBuilder CSEB(B.getState());
+  unsigned AddReg = MRI->createGenericVirtualRegister(s16);
+  auto MIBAddCopy =
+      CSEB.buildInstr(TargetOpcode::G_ADD, AddReg, MIBInput, MIBInput);
+  ASSERT_EQ(MIBAddCopy->getOpcode(), TargetOpcode::COPY);
+  auto MIBAdd2 = CSEB.buildInstr(TargetOpcode::G_ADD, s16, MIBInput, MIBInput);
+  ASSERT_TRUE(&*MIBAdd == &*MIBAdd2);
+  CSEB.setInsertPt(*EntryMBB, EntryMBB->begin());
+  auto MIBAdd4 = CSEB.buildInstr(TargetOpcode::G_ADD, s16, MIBInput, MIBInput);
+  ASSERT_TRUE(&*MIBAdd == &*MIBAdd4);
+  auto MIBAdd5 = CSEB.buildInstr(TargetOpcode::G_ADD, s16, MIBInput, MIBInput1);
+  ASSERT_TRUE(&*MIBAdd != &*MIBAdd5);
+  auto MIBCst = CSEB.buildConstant(s32, 0);
+  auto MIBCst1 = CSEB.buildConstant(s32, 0);
+  ASSERT_TRUE(&*MIBCst == &*MIBCst1);
+  // Try the CFing aspect.
+  auto MIBCF1 = CSEB.buildInstr(TargetOpcode::G_ADD, s32, MIBCst, MIBCst);
+  ASSERT_TRUE(&*MIBCF1 == &*MIBCst);
+
+  // Try out building FCONSTANTs.
+  auto MIBFP0 = CSEB.buildFConstant(s32, 1.0);
+  auto MIBFP0_1 = CSEB.buildFConstant(s32, 1.0);
+  ASSERT_TRUE(&*MIBFP0 == &*MIBFP0_1);
+  CSEInfo.print();
+
+  // Check G_UNMERGE_VALUES
+  auto MIBUnmerge = CSEB.buildUnmerge(UnmergeRegs, Copies[0]);
+  auto MIBUnmerge2 = CSEB.buildUnmerge({s32, s32}, Copies[0]);
+  ASSERT_TRUE(&*MIBUnmerge == &*MIBUnmerge2);
+}}

unittests/CodeGen/GlobalISel/GISelMITest.h

-//===- LegalizerHelperTest.h
+//===- GISelMITest.h
 //-----------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
+#ifndef LLVM_UNITTEST_CODEGEN_GLOBALISEL_GISELMI_H
+#define LLVM_UNITTEST_CODEGEN_GLOBALISEL_GISELMI_H
 
 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
 #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"
void initLLVM() {
 
   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() {
+static 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,
+static 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>>
+static 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:
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());
     }
 }
 
-class LegalizerHelperTest : public ::testing::Test {
+class GISelMITest : public ::testing::Test {
 protected:
-  LegalizerHelperTest() : ::testing::Test() {
+  GISelMITest() : ::testing::Test(), B(State) {
     TM = createTargetMachine();
     if (!TM)
       return;
     ModuleMMIPair = createDummyModule(Context, *TM, "");
     MF = getMFFromMMI(ModuleMMIPair.first.get(), ModuleMMIPair.second.get());
     collectCopies(Copies, MF);
     EntryMBB = &*MF->begin();
     B.setMF(*MF);
     MRI = &MF->getRegInfo();
     B.setInsertPt(*EntryMBB, EntryMBB->end());
   }
   LLVMContext Context;
   std::unique_ptr<TargetMachine> TM;
   MachineFunction *MF;
   std::pair<std::unique_ptr<Module>, std::unique_ptr<MachineModuleInfo>>
       ModuleMMIPair;
   SmallVector<unsigned, 4> Copies;
   MachineBasicBlock *EntryMBB;
+  MachineIRBuilderState State;
   MachineIRBuilder B;
   MachineRegisterInfo *MRI;
 };
 
 #define DefineLegalizerInfo(Name, SettingUpActionsBlock)                       \
   class Name##Info : public LegalizerInfo {                                    \
   public:                                                                      \
     Name##Info(const TargetSubtargetInfo &ST) {                                \
       using namespace TargetOpcode;                                            \
       const LLT s8 = LLT::scalar(8);                                           \
       (void)s8;                                                                \
       const LLT s16 = LLT::scalar(16);                                         \
       (void)s16;                                                               \
       const LLT s32 = LLT::scalar(32);                                         \
       (void)s32;                                                               \
       const LLT s64 = LLT::scalar(64);                                         \
       (void)s64;                                                               \
       do                                                                       \
         SettingUpActionsBlock while (0);                                       \
       computeTables();                                                         \
       verify(*ST.getInstrInfo());                                              \
     }                                                                          \
   };
 
-static bool CheckMachineFunction(const MachineFunction &MF,
+static inline bool CheckMachineFunction(const MachineFunction &MF,
                                  StringRef CheckStr) {
   SmallString<512> Msg;
   raw_svector_ostream OS(Msg);
   MF.print(OS);
   auto OutputBuf = MemoryBuffer::getMemBuffer(Msg, "Output", false);
   auto CheckBuf = MemoryBuffer::getMemBuffer(CheckStr, "");
   SmallString<4096> CheckFileBuffer;
   FileCheckRequest Req;
   FileCheck FC(Req);
   StringRef CheckFileText =
       FC.CanonicalizeFile(*CheckBuf.get(), CheckFileBuffer);
   SourceMgr SM;
   SM.AddNewSourceBuffer(MemoryBuffer::getMemBuffer(CheckFileText, "CheckFile"),
                         SMLoc());
   Regex PrefixRE = FC.buildCheckPrefixRegex();
   std::vector<FileCheckString> CheckStrings;
   FC.ReadCheckFile(SM, CheckFileText, PrefixRE, CheckStrings);
   auto OutBuffer = OutputBuf->getBuffer();
   SM.AddNewSourceBuffer(std::move(OutputBuf), SMLoc());
   return FC.CheckInput(SM, OutBuffer, CheckStrings);
 }
+#endif

unittests/CodeGen/GlobalISel/LegalizerHelperTest.cpp

-//===- PatternMatchTest.cpp -----------------------------------------------===//
+//===- LegalizerHelperTest.cpp -----------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
-#include "LegalizerHelperTest.h"
+#include "GISelMITest.h"
 
 namespace {
 
 // Test CTTZ expansion when CTTZ_ZERO_UNDEF is legal or custom,
 // in which case it becomes CTTZ_ZERO_UNDEF with select.
-TEST_F(LegalizerHelperTest, LowerBitCountingCTTZ0) {
+TEST_F(GISelMITest, LowerBitCountingCTTZ0) {
   if (!TM)
     return;
 
   // Declare your legalization info
   DefineLegalizerInfo(
       A, { getActionDefinitionsBuilder(G_CTTZ_ZERO_UNDEF).legalFor({s64}); });
   // Build Instr
   auto MIBCTTZ = B.buildInstr(TargetOpcode::G_CTTZ, LLT::scalar(64), Copies[0]);
TEST_F(GISelMITest, LowerBitCountingCTTZ0) {
   CHECK: [[SEL:%[0-9]+]]:_(s64) = G_SELECT [[CMP]]:_(s1), [[SIXTY4]]:_, [[CZU]]
   )";
 
   // Check
   ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr));
 }
 
 // CTTZ expansion in terms of CTLZ
-TEST_F(LegalizerHelperTest, LowerBitCountingCTTZ1) {
+TEST_F(GISelMITest, LowerBitCountingCTTZ1) {
   if (!TM)
     return;
 
   // Declare your legalization info
   DefineLegalizerInfo(A,
                       { getActionDefinitionsBuilder(G_CTLZ).legalFor({s64}); });
   // Build Instr
   auto MIBCTTZ = B.buildInstr(TargetOpcode::G_CTTZ, LLT::scalar(64), Copies[0]);
TEST_F(GISelMITest, LowerBitCountingCTTZ1) {
   CHECK: G_SUB [[CST64]]:_, [[CTLZ]]:_
   )";
 
   // Check
   ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr));
 }
 
 // CTTZ expansion in terms of CTPOP
-TEST_F(LegalizerHelperTest, LowerBitCountingCTTZ2) {
+TEST_F(GISelMITest, LowerBitCountingCTTZ2) {
   if (!TM)
     return;
 
   // Declare your legalization info
   DefineLegalizerInfo(
       A, { getActionDefinitionsBuilder(G_CTPOP).legalFor({s64}); });
   // Build
   auto MIBCTTZ = B.buildInstr(TargetOpcode::G_CTTZ, LLT::scalar(64), Copies[0]);
TEST_F(GISelMITest, LowerBitCountingCTTZ2) {
   CHECK: [[POP:%[0-9]+]]:_(s64) = G_CTPOP [[AND1]]
   )";
 
   // Check
   ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr));
 }
 
 // CTTZ_ZERO_UNDEF expansion in terms of CTTZ
-TEST_F(LegalizerHelperTest, LowerBitCountingCTTZ3) {
+TEST_F(GISelMITest, LowerBitCountingCTTZ3) {
   if (!TM)
     return;
 
   // Declare your legalization info
   DefineLegalizerInfo(A,
                       { getActionDefinitionsBuilder(G_CTTZ).legalFor({s64}); });
   // Build
   auto MIBCTTZ =
       B.buildInstr(TargetOpcode::G_CTTZ_ZERO_UNDEF, LLT::scalar(64), Copies[0]);
   AInfo Info(MF->getSubtarget());
   LegalizerHelper Helper(*MF, Info);
   ASSERT_TRUE(Helper.lower(*MIBCTTZ, 0, LLT::scalar(64)) ==
               LegalizerHelper::LegalizeResult::Legalized);
 
   auto CheckStr = R"(
   CHECK: CTTZ
   )";
 
   // Check
   ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr));
 }
 
 // CTLZ expansion in terms of CTLZ_ZERO_UNDEF
-TEST_F(LegalizerHelperTest, LowerBitCountingCTLZ0) {
+TEST_F(GISelMITest, LowerBitCountingCTLZ0) {
   if (!TM)
     return;
 
   // Declare your legalization info
   DefineLegalizerInfo(
       A, { getActionDefinitionsBuilder(G_CTLZ_ZERO_UNDEF).legalFor({s64}); });
   // Build
   auto MIBCTLZ = B.buildInstr(TargetOpcode::G_CTLZ, LLT::scalar(64), Copies[0]);
TEST_F(GISelMITest, LowerBitCountingCTLZ0) {
   CHECK: [[SEL:%[0-9]+]]:_(s64) = G_SELECT [[CMP]]:_(s1), [[SIXTY4]]:_, [[CZU]]
   )";
 
   // Check
   ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr));
 }
 
 // CTLZ expansion
-TEST_F(LegalizerHelperTest, LowerBitCountingCTLZ1) {
+TEST_F(GISelMITest, LowerBitCountingCTLZ1) {
   if (!TM)
     return;
 
   // Declare your legalization info
   DefineLegalizerInfo(A,
                       { getActionDefinitionsBuilder(G_CTPOP).legalFor({s8}); });
   // Build
   // Trunc it to s8.
TEST_F(GISelMITest, LowerBitCountingCTLZ1) {
   CHECK: [[Sub:%[0-9]+]]:_(s8) = G_SUB [[Len]]:_, [[CTPOP]]:_
   )";
 
   // Check
   ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr));
 }
 
 // CTLZ widening.
-TEST_F(LegalizerHelperTest, WidenBitCountingCTLZ) {
+TEST_F(GISelMITest, WidenBitCountingCTLZ) {
   if (!TM)
     return;
 
   // Declare your legalization info
   DefineLegalizerInfo(A,
                       { getActionDefinitionsBuilder(G_CTLZ).legalFor({s16}); });
   // Build
   // Trunc it to s8.
TEST_F(GISelMITest, WidenBitCountingCTLZ) {
   CHECK: [[Trunc:%[0-9]+]]:_(s8) = G_TRUNC [[Sub]]
   )";
 
   // Check
   ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr));
 }
 
 // CTLZ_ZERO_UNDEF widening.
-TEST_F(LegalizerHelperTest, WidenBitCountingCTLZZeroUndef) {
+TEST_F(GISelMITest, WidenBitCountingCTLZZeroUndef) {
   if (!TM)
     return;
 
   // Declare your legalization info
   DefineLegalizerInfo(
       A, { getActionDefinitionsBuilder(G_CTLZ_ZERO_UNDEF).legalFor({s16}); });
   // Build
   // Trunc it to s8.
TEST_F(GISelMITest, WidenBitCountingCTLZZeroUndef) {
   CHECK: [[Trunc:%[0-9]+]]:_(s8) = G_TRUNC [[Sub]]
   )";
 
   // Check
   ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr));
 }
 
 // CTPOP widening.
-TEST_F(LegalizerHelperTest, WidenBitCountingCTPOP) {
+TEST_F(GISelMITest, WidenBitCountingCTPOP) {
   if (!TM)
     return;
 
   // Declare your legalization info
   DefineLegalizerInfo(
       A, { getActionDefinitionsBuilder(G_CTPOP).legalFor({s16}); });
   // Build
   // Trunc it to s8.
TEST_F(GISelMITest, WidenBitCountingCTPOP) {
   CHECK: [[Trunc:%[0-9]+]]:_(s8) = G_TRUNC [[Ctpop]]
   )";
 
   // Check
   ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr));
 }
 
 // CTTZ_ZERO_UNDEF widening.
-TEST_F(LegalizerHelperTest, WidenBitCountingCTTZ_ZERO_UNDEF) {
+TEST_F(GISelMITest, WidenBitCountingCTTZ_ZERO_UNDEF) {
   if (!TM)
     return;
 
   // Declare your legalization info
   DefineLegalizerInfo(
       A, { getActionDefinitionsBuilder(G_CTTZ_ZERO_UNDEF).legalFor({s16}); });
   // Build
   // Trunc it to s8.
TEST_F(GISelMITest, WidenBitCountingCTTZ_ZERO_UNDEF) {
   CHECK: [[Trunc:%[0-9]+]]:_(s8) = G_TRUNC [[CttzZu]]
   )";
 
   // Check
   ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr));
 }
 
 // CTTZ widening.
-TEST_F(LegalizerHelperTest, WidenBitCountingCTTZ) {
+TEST_F(GISelMITest, WidenBitCountingCTTZ) {
   if (!TM)
     return;
 
   // Declare your legalization info
   DefineLegalizerInfo(A,
                       { getActionDefinitionsBuilder(G_CTTZ).legalFor({s16}); });
   // Build
   // Trunc it to s8.
TEST_F(GISelMITest, WidenBitCountingCTTZ) {
   CHECK: [[Cttz:%[0-9]+]]:_(s16) = G_CTTZ [[Or]]
   CHECK: [[Trunc:%[0-9]+]]:_(s8) = G_TRUNC [[Cttz]]
   )";
 
   // Check
   ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr));
 }
 // UADDO widening.
-TEST_F(LegalizerHelperTest, WidenUADDO) {
+TEST_F(GISelMITest, WidenUADDO) {
   if (!TM)
     return;
 
   // Declare your legalization info
   DefineLegalizerInfo(A,
                       { getActionDefinitionsBuilder(G_ADD).legalFor({s16}); });
   // Build
   // Trunc it to s8.
TEST_F(GISelMITest, WidenUADDO) {
   CHECK: G_TRUNC [[ADD]]
   )";
 
   // Check
   ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr));
 }
 
 // USUBO widening.
-TEST_F(LegalizerHelperTest, WidenUSUBO) {
+TEST_F(GISelMITest, WidenUSUBO) {
   if (!TM)
     return;
 
   // Declare your legalization info
   DefineLegalizerInfo(A,
                       { getActionDefinitionsBuilder(G_SUB).legalFor({s16}); });
   // Build
   // Trunc it to s8.

unittests/CodeGen/GlobalISel/PatternMatchTest.cpp

TEST(PatternMatchInstr, MatchIntConstant) {
   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);
+  MachineIRBuilderState State;
+  MachineIRBuilder B(*MF, State);
   MachineRegisterInfo &MRI = MF->getRegInfo();
   B.setInsertPt(*EntryMBB, EntryMBB->end());
   auto MIBCst = B.buildConstant(LLT::scalar(64), 42);
   int64_t Cst;
   bool match = mi_match(MIBCst->getOperand(0).getReg(), MRI, m_ICst(Cst));
   ASSERT_TRUE(match);
   ASSERT_EQ(Cst, 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);
+  MachineIRBuilderState State;
+  MachineIRBuilder B(*MF, State);
   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 =
       mi_match(MIBAdd->getOperand(0).getReg(), MRI, m_GAdd(m_Reg(), m_Reg()));
   ASSERT_TRUE(match);
auto MIBCAdd1 =
                      CFB.buildConstant(s32, 1));
   // This should be a constant now.
   match = mi_match(MIBCAdd1->getOperand(0).getReg(), MRI, m_ICst(Cst));
   ASSERT_TRUE(match);
   ASSERT_EQ(Cst, 1);
 
   // Try one of the other constructors of MachineIRBuilder to make sure it's
   // compatible.
-  ConstantFoldingMIRBuilder CFB1(*MF);
+  ConstantFoldingMIRBuilder CFB1(*MF, State);
   CFB1.setInsertPt(*EntryMBB, EntryMBB->end());
   auto MIBCSub =
       CFB1.buildInstr(TargetOpcode::G_SUB, s32, CFB1.buildConstant(s32, 1),
                       CFB1.buildConstant(s32, 1));
   // This should be a constant now.
   match = mi_match(MIBCSub->getOperand(0).getReg(), MRI, m_ICst(Cst));
   ASSERT_TRUE(match);
   ASSERT_EQ(Cst, 0);
 }
 
 TEST(PatternMatchInstr, MatchFPUnaryOp) {
   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);
+  MachineIRBuilderState State;
+  MachineIRBuilder B(*MF, State);
   MachineRegisterInfo &MRI = MF->getRegInfo();
   B.setInsertPt(*EntryMBB, EntryMBB->end());
 
   // Truncate s64 to s32.
   LLT s32 = LLT::scalar(32);
   auto Copy0s32 = B.buildFPTrunc(s32, Copies[0]);
 
   // Match G_FABS.
TEST(PatternMatchInstr, MatchExtendsTrunc) {
   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);
+  MachineIRBuilderState State;
+  MachineIRBuilder B(*MF, State);
   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);
TEST(PatternMatchInstr, MatchSpecificType) {
   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);
+  MachineIRBuilderState State;
+  MachineIRBuilder B(*MF, State);
   MachineRegisterInfo &MRI = MF->getRegInfo();
   B.setInsertPt(*EntryMBB, EntryMBB->end());
 
   // Try to match a 64bit add.
   LLT s64 = LLT::scalar(64);
   LLT s32 = LLT::scalar(32);
   auto MIBAdd = B.buildAdd(s64, Copies[0], Copies[1]);
   ASSERT_FALSE(mi_match(MIBAdd->getOperand(0).getReg(), MRI,
TEST(PatternMatchInstr, MatchCombinators) {
   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);
+  MachineIRBuilderState State;
+  MachineIRBuilder B(*MF, State);
   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 =
       mi_match(MIBAdd->getOperand(0).getReg(), MRI,