[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

43

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

38

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

67

Document what this is for?

include/llvm/CodeGen/GlobalISel/CSEMIRBuilder.h

50

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

52

'count' is unused here.

65

Typo 'to'

227

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

272

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

43

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

52

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

227

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

38

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/GISelChangeObserver.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);
+};
+
+// Class representing some configuration that can be done during CSE analysis.
+// Currently it only supports shouldCSE method that each pass can set.
+class CSEConfig {
+public:
+  virtual ~CSEConfig() = default;
+  // Hook for defining which Generic instructions should be CSEd.
+  // GISelCSEInfo currently only calls this hook when dealing with generic
+  // opcodes.
+  virtual bool shouldCSEOpc(unsigned Opc);
+};
+
+// TODO: Find a better place for this.
+// Commonly used for O0 config.
+class CSEConfigConstantOnly : public CSEConfig {
+public:
+  virtual ~CSEConfigConstantOnly() = default;
+  virtual bool shouldCSEOpc(unsigned Opc) override;
+};
+
+/// 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 GISelChangeObserver {
+  // Make it accessible only to CSEMIRBuilder.
+  friend class CSEMIRBuilder;
+
+  BumpPtrAllocator UniqueInstrAllocator;
+  FoldingSet<UniqueMachineInstr> CSEMap;
+  MachineRegisterInfo *MRI = nullptr;
+  MachineFunction *MF = nullptr;
+  std::unique_ptr<CSEConfig> CSEOpt;
+  /// 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;
+
+  /// Store instructions that are not fully formed in TemporaryInsts.
+  /// Also because CSE insertion happens lazily, we can remove insts from this
+  /// list and avoid inserting and then removing from the CSEMap.
+  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);
+
+  /// 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 setCSEConfig(std::unique_ptr<CSEConfig> Opt) { CSEOpt = std::move(Opt); }
+
+  bool shouldCSE(unsigned Opc) const;
+
+  void analyze(MachineFunction &MF);
+
+  void countOpcodeHit(unsigned Opc);
+
+  void print();
+
+  // Observer API
+  void erasingInstr(MachineInstr &MI) override;
+  void createdInstr(MachineInstr &MI) override;
+  void changingInstr(MachineInstr &MI) override;
+  void changedInstr(MachineInstr &MI) override;
+};
+
+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 &addNodeIDFlag(unsigned Flag) const;
+  const GISelInstProfileBuilder &addNodeID(const MachineInstr *MI) const;
+};
+
+/// Simple wrapper that does the following.
+/// 1) Lazily evaluate the MachineFunction to compute CSEable instructions.
+/// 2) Allows configuration of which instructions are CSEd through CSEConfig
+/// object. Provides a method called get which takes a CSEConfig object.
+class GISelCSEAnalysisWrapper {
+  GISelCSEInfo Info;
+  MachineFunction *MF = nullptr;
+  bool AlreadyComputed = false;
+
+public:
+  /// Takes a CSEConfig object that defines what opcodes get CSEd.
+  /// If CSEConfig is already set, and the CSE Analysis has been preserved,
+  /// it will not use the new CSEOpt(use Recompute to force using the new
+  /// CSEOpt).
+  GISelCSEInfo &get(std::unique_ptr<CSEConfig> CSEOpt, bool ReCompute = false);
+  void setMF(MachineFunction &MFunc) { MF = &MFunc; }
+  void setComputed(bool Computed) { AlreadyComputed = Computed; }
+  void releaseMemory() { Info.releaseMemory(); }
+};
+
+/// The actual analysis pass wrapper.
+class GISelCSEAnalysisWrapperPass : public MachineFunctionPass {
+  GISelCSEAnalysisWrapper Wrapper;
+
+public:
+  static char ID;
+  GISelCSEAnalysisWrapperPass() : MachineFunctionPass(ID) {
+    initializeGISelCSEAnalysisWrapperPassPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+  const GISelCSEAnalysisWrapper &getCSEWrapper() const { return Wrapper; }
+  GISelCSEAnalysisWrapper &getCSEWrapper() { return Wrapper; }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+  void releaseMemory() override {
+    Wrapper.releaseMemory();
+    Wrapper.setComputed(false);
+  }
+};
+
+} // 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()); CB.setCSEInfo(Info); 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);
+/// assert(C->getOpcode() == TargetOpcode::COPY);
+/// Explicitly passing in a register would materialize a copy if possible.
+/// CSEMIRBuilder also does trivial constant folding for binary ops.
+class CSEMIRBuilder : public MachineIRBuilder {
+
+  /// 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;
+
+  /// 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.
+  MachineInstrBuilder getDominatingInstrForID(FoldingSetNodeID &ID,
+                                              void *&NodeInsertPos);
+  /// Simple check if we can CSE (we have the CSEInfo) or if this Opcode is
+  /// safe to CSE.
+  bool canPerformCSEForOpc(unsigned Opc) const;
+
+  void profileDstOp(const DstOp &Op, GISelInstProfileBuilder &B) const;
+
+  void profileDstOps(ArrayRef<DstOp> Ops, GISelInstProfileBuilder &B) const {
+    for (const DstOp &Op : Ops)
+      profileDstOp(Op, B);
+  }
+
+  void profileSrcOp(const SrcOp &Op, GISelInstProfileBuilder &B) const;
+
+  void profileSrcOps(ArrayRef<SrcOp> Ops, GISelInstProfileBuilder &B) const {
+    for (const SrcOp &Op : Ops)
+      profileSrcOp(Op, B);
+  }
+
+  void profileMBBOpcode(GISelInstProfileBuilder &B, unsigned Opc) const;
+
+  void profileEverything(unsigned Opc, ArrayRef<DstOp> DstOps,
+                         ArrayRef<SrcOp> SrcOps, Optional<unsigned> Flags,
+                         GISelInstProfileBuilder &B) const;
+
+  // Takes a MachineInstrBuilder and inserts it into the CSEMap using the
+  // NodeInsertPos.
+  MachineInstrBuilder memoizeMI(MachineInstrBuilder MIB, void *NodeInsertPos);
+
+  // If we have can CSE an instruction, but still need to materialize to a VReg,
+  // we emit a copy from the CSE'd inst to the VReg.
+  MachineInstrBuilder generateCopiesIfRequired(ArrayRef<DstOp> DstOps,
+                                               MachineInstrBuilder &MIB);
+
+  // If we have can CSE an instruction, but still need to materialize to a VReg,
+  // check if we can generate copies. It's not possible to return a single MIB,
+  // while emitting copies to multiple vregs.
+  bool checkCopyToDefsPossible(ArrayRef<DstOp> DstOps);
+
+public:
+  // Pull in base class constructors.
+  using MachineIRBuilder::MachineIRBuilder;
+  // Unhide buildInstr
+  MachineInstrBuilder buildInstr(unsigned Opc, ArrayRef<DstOp> DstOps,
+                                 ArrayRef<SrcOp> SrcOps,
+                                 Optional<unsigned> Flag = None) override;
+  // Bring in the other overload from the base class.
+  using MachineIRBuilder::buildConstant;
+
+  MachineInstrBuilder buildConstant(const DstOp &Res,
+                                    const ConstantInt &Val) override;
+
+  // Bring in the other overload from the base class.
+  using MachineIRBuilder::buildFConstant;
+  MachineInstrBuilder buildFConstant(const DstOp &Res,
+                                     const ConstantFP &Val) override;
+};
+} // 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 Combiner {
 public:
   Combiner(CombinerInfo &CombinerInfo, const TargetPassConfig *TPC);
 
-  bool combineMachineInstrs(MachineFunction &MF);
+  /// If CSEInfo is not null, then the Combiner will setup observer for
+  /// CSEInfo and instantiate a CSEMIRBuilder. Pass nullptr if CSE is not
+  /// needed.
+  bool combineMachineInstrs(MachineFunction &MF, GISelCSEInfo *CSEInfo);
 
 protected:
   CombinerInfo &CInfo;
 
   MachineRegisterInfo *MRI = nullptr;
   const TargetPassConfig *TPC;
-  MachineIRBuilder Builder;
+  std::unique_ptr<MachineIRBuilder> Builder;
 };
 
 } // End namespace llvm.
 
 #endif // LLVM_CODEGEN_GLOBALISEL_GICOMBINER_H

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 MachineIRBuilder {
 public:
   // Pull in base class constructors.
   using MachineIRBuilder::MachineIRBuilder;
 
   virtual ~ConstantFoldingMIRBuilder() = default;

include/llvm/CodeGen/GlobalISel/GISelChangeObserver.h

 /// This contains common code to allow clients to notify changes to machine
 /// instr.
 //
 //===----------------------------------------------------------------------===//
 #ifndef LLVM_CODEGEN_GLOBALISEL_GISELCHANGEOBSERVER_H
 #define LLVM_CODEGEN_GLOBALISEL_GISELCHANGEOBSERVER_H
 
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/CodeGen/MachineFunction.h"
 
 namespace llvm {
 class MachineInstr;
 class MachineRegisterInfo;
 
 /// Abstract class that contains various methods for clients to notify about
 /// changes. This should be the preferred way for APIs to notify changes.
 /// Typically calling erasingInstr/createdInstr multiple times should not affect
 /// the result. The observer would likely need to check if it was already
 /// notified earlier (consider using GISelWorkList).
 class GISelChangeObserver {
   SmallPtrSet<MachineInstr *, 4> ChangingAllUsesOfReg;
 
 public:
   virtual ~GISelChangeObserver() {}
 
   /// An instruction is about to be erased.
-  virtual void erasingInstr(const MachineInstr &MI) = 0;
+  virtual void erasingInstr(MachineInstr &MI) = 0;
   /// An instruction was created and inserted into the function.
-  virtual void createdInstr(const MachineInstr &MI) = 0;
+  virtual void createdInstr(MachineInstr &MI) = 0;
   /// This instruction is about to be mutated in some way.
-  virtual void changingInstr(const MachineInstr &MI) = 0;
+  virtual void changingInstr(MachineInstr &MI) = 0;
   /// This instruction was mutated in some way.
-  virtual void changedInstr(const MachineInstr &MI) = 0;
+  virtual void changedInstr(MachineInstr &MI) = 0;
 
   /// All the instructions using the given register are being changed.
   /// For convenience, finishedChangingAllUsesOfReg() will report the completion
   /// of the changes. The use list may change between this call and
   /// finishedChangingAllUsesOfReg().
   void changingAllUsesOfReg(const MachineRegisterInfo &MRI, unsigned Reg);
   /// All instructions reported as changing by changingAllUsesOfReg() have
   /// finished being changed.
   void finishedChangingAllUsesOfReg();
 
 };
 
+/// Simple wrapper observer that takes several observers, and calls
+/// each one for each event. If there are multiple observers (say CSE,
+/// Legalizer, Combiner), it's sufficient to register this to the machine
+/// function as the delegate.
+class GISelObserverWrapper : public MachineFunction::Delegate,
+                             public GISelChangeObserver {
+  SmallVector<GISelChangeObserver *, 4> Observers;
+
+public:
+  GISelObserverWrapper() = default;
+  GISelObserverWrapper(ArrayRef<GISelChangeObserver *> Obs)
+      : Observers(Obs.begin(), Obs.end()) {}
+  // Adds an observer.
+  void addObserver(GISelChangeObserver *O) { Observers.push_back(O); }
+  // Removes an observer from the list and does nothing if observer is not
+  // present.
+  void removeObserver(GISelChangeObserver *O) {
+    auto It = std::find(Observers.begin(), Observers.end(), O);
+    if (It != Observers.end())
+      Observers.erase(It);
+  }
+  // API for Observer.
+  void erasingInstr(MachineInstr &MI) override {
+    for (auto &O : Observers)
+      O->erasingInstr(MI);
+  }
+  void createdInstr(MachineInstr &MI) override {
+    for (auto &O : Observers)
+      O->createdInstr(MI);
+  }
+  void changingInstr(MachineInstr &MI) override {
+    for (auto &O : Observers)
+      O->changingInstr(MI);
+  }
+  void changedInstr(MachineInstr &MI) override {
+    for (auto &O : Observers)
+      O->changedInstr(MI);
+  }
+  // API for MachineFunction::Delegate
+  void MF_HandleInsertion(MachineInstr &MI) override { createdInstr(MI); }
+  void MF_HandleRemoval(MachineInstr &MI) override { erasingInstr(MI); }
+};
+
+/// A simple RAII based CSEInfo installer.
+/// Use this in a scope to install a delegate to the MachineFunction and reset
+/// it at the end of the scope.
+class RAIIDelegateInstaller {
+  MachineFunction &MF;
+  MachineFunction::Delegate *Delegate;
+
+public:
+  RAIIDelegateInstaller(MachineFunction &MF, MachineFunction::Delegate *Del);
+  ~RAIIDelegateInstaller();
+};
+
 } // namespace llvm
 #endif

include/llvm/CodeGen/GlobalISel/GISelWorkList.h

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/Support/Debug.h"
 
 namespace llvm {
 
+class MachineInstr;
 class MachineFunction;
 
 // Worklist which mostly works similar to InstCombineWorkList, but on
 // MachineInstrs. The main difference with something like a SetVector is that
 // erasing an element doesn't move all elements over one place - instead just
 // nulls out the element of the vector.
 //
-// This worklist operates on instructions within a particular function. This is
-// important for acquiring the rights to modify/replace instructions a
-// GISelChangeObserver reports as the observer doesn't have the right to make
-// changes to the instructions it sees so we use our access to the
-// MachineFunction to establish that it's ok to add a given instruction to the
-// worklist.
-//
 // FIXME: Does it make sense to factor out common code with the
 // instcombinerWorkList?
 template<unsigned N>
 class GISelWorkList {
-  MachineFunction *MF;
   SmallVector<MachineInstr *, N> Worklist;
   DenseMap<MachineInstr *, unsigned> WorklistMap;
 
 public:
-  GISelWorkList(MachineFunction *MF) : MF(MF) {}
+  GISelWorkList() {}
 
   bool empty() const { return WorklistMap.empty(); }
 
   unsigned size() const { return WorklistMap.size(); }
 
   /// Add the specified instruction to the worklist if it isn't already in it.
   void insert(MachineInstr *I) {
-    // It would be safe to add this instruction to the worklist regardless but
-    // for consistency with the const version, check that the instruction we're
-    // adding would have been accepted if we were given a const pointer instead.
-    insert(const_cast<const MachineInstr *>(I));
-  }
-
-  void insert(const MachineInstr *I) {
-    // Confirm we'd be able to find the non-const pointer we want to schedule if
-    // we wanted to. We have the right to schedule work that may modify any
-    // instruction in MF.
-    assert(I->getParent() && "Expected parent BB");
-    assert(I->getParent()->getParent() && "Expected parent function");
-    assert((!MF || I->getParent()->getParent() == MF) &&
-           "Expected parent function to be current function or not given");
-
-    // But don't actually do the search since we can derive it from the const
-    // pointer.
-    MachineInstr *NonConstI = const_cast<MachineInstr *>(I);
-    if (WorklistMap.try_emplace(NonConstI, Worklist.size()).second) {
-      Worklist.push_back(NonConstI);
-    }
+    if (WorklistMap.try_emplace(I, Worklist.size()).second)
+      Worklist.push_back(I);
   }
 
   /// Remove I from the worklist if it exists.
   void remove(const MachineInstr *I) {
     auto It = WorklistMap.find(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

 /// \todo Replace the comments with actual doxygen comments.
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_GLOBALISEL_IRTRANSLATOR_H
 #define LLVM_CODEGEN_GLOBALISEL_IRTRANSLATOR_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
-#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
+#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/Types.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
-#include "llvm/Support/Allocator.h"
 #include "llvm/IR/Intrinsics.h"
+#include "llvm/Support/Allocator.h"
 #include <memory>
 #include <utility>
 
 namespace llvm {
 
 class AllocaInst;
 class BasicBlock;
 class CallInst;
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.
-  MachineIRBuilder CurBuilder;
+  // CSEMIRBuilder CurBuilder;
+  std::unique_ptr<MachineIRBuilder> CurBuilder;
 
   // Builder set to the entry block (just after ABI lowering instructions). Used
   // as a convenient location for Constants.
-  MachineIRBuilder EntryBuilder;
+  // CSEMIRBuilder EntryBuilder;
+  std::unique_ptr<MachineIRBuilder> EntryBuilder;
 
   // The MachineFunction currently being translated.
   MachineFunction *MF;
 
   /// MachineRegisterInfo used to create virtual registers.
   MachineRegisterInfo *MRI = nullptr;
 
   const DataLayout *DL;

include/llvm/CodeGen/GlobalISel/LegalizerHelper.h

enum LegalizeResult {
     /// Instruction has been legalized and the MachineFunction changed.
     Legalized,
 
     /// Some kind of error has occurred and we could not legalize this
     /// instruction.
     UnableToLegalize,
   };
 
-  LegalizerHelper(MachineFunction &MF, GISelChangeObserver &Observer);
+  LegalizerHelper(MachineFunction &MF, GISelChangeObserver &Observer,
+                  MachineIRBuilder &B);
   LegalizerHelper(MachineFunction &MF, const LegalizerInfo &LI,
-                  GISelChangeObserver &Observer);
+                  GISelChangeObserver &Observer, MachineIRBuilder &B);
 
   /// Replace \p MI by a sequence of legal instructions that can implement the
   /// same operation. Note that this means \p MI may be deleted, so any iterator
   /// steps should be performed before calling this function. \p Helper should
   /// be initialized to the MachineFunction containing \p MI.
   ///
   /// Considered as an opaque blob, the legal code will use and define the same
   /// registers as \p MI.
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;
+  MachineIRBuilder &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

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;
   /// @}
 
   GISelChangeObserver *Observer;
+
+  GISelCSEInfo *CSEInfo;
 };
 
 class DstOp {
   union {
     LLT LLTTy;
     unsigned Reg;
     const TargetRegisterClass *RC;
   };
case DstType::Ty_LLT:
       MIB.addDef(MRI.createGenericVirtualRegister(LLTTy));
       break;
     case DstType::Ty_RC:
       MIB.addDef(MRI.createVirtualRegister(RC));
       break;
     }
   }
 
-  DstType getType() const { return Ty; }
-
   LLT getLLTTy(const MachineRegisterInfo &MRI) const {
     switch (Ty) {
     case DstType::Ty_RC:
       return LLT{};
     case DstType::Ty_LLT:
       return LLTTy;
     case DstType::Ty_Reg:
       return MRI.getType(Reg);
     }
     llvm_unreachable("Unrecognised DstOp::DstType enum");
   }
 
+  unsigned getReg() const {
+    assert(Ty == DstType::Ty_Reg && "Not a register");
+    return Reg;
+  }
+
+  const TargetRegisterClass *getRegClass() const {
+    switch (Ty) {
+    case DstType::Ty_RC:
+      return RC;
+    default:
+      llvm_unreachable("Not a RC Operand");
+    }
+  }
+
   DstType getDstOpKind() const { return Ty; }
 
 private:
   DstType Ty;
 };
 
 class SrcOp {
   union {
MachineFunction &getMF() {
     return *State.MF;
   }
 
   /// Getter for DebugLoc
   const DebugLoc &getDL() { return State.DL; }
 
   /// Getter for MRI
   MachineRegisterInfo *getMRI() { return State.MRI; }
+  const MachineRegisterInfo *getMRI() const { return State.MRI; }
 
   /// Getter for the State
   MachineIRBuilderState &getState() { return State; }
 
   /// Getter for the basic block we currently build.
-  MachineBasicBlock &getMBB() {
+  const MachineBasicBlock &getMBB() const {
     assert(State.MBB && "MachineBasicBlock is not set");
     return *State.MBB;
   }
 
+  MachineBasicBlock &getMBB() {
+    return const_cast<MachineBasicBlock &>(
+        const_cast<const MachineIRBuilder *>(this)->getMBB());
+  }
+
+  GISelCSEInfo *getCSEInfo() { return State.CSEInfo; }
+  const GISelCSEInfo *getCSEInfo() const { 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);
+
   /// \name Setters for the insertion point.
   /// @{
   /// Set the MachineFunction where to build instructions.
-  void setMF(MachineFunction &);
+  void setMF(MachineFunction &MF);
 
   /// Set the insertion point to the  end of \p MBB.
   /// \pre \p MBB must be contained by getMF().
   void setMBB(MachineBasicBlock &MBB);
 
   /// Set the insertion point to before MI.
   /// \pre MI must be in getMF().
   void setInstr(MachineInstr &MI);
public:
   /// G_CONSTANT is an integer constant with the specified size and value. \p
   /// Val will be extended or truncated to the size of \p Reg.
   ///
   /// \pre setBasicBlock or setMI must have been called.
   /// \pre \p Res must be a generic virtual register with scalar or pointer
   ///      type.
   ///
   /// \return The newly created instruction.
-  MachineInstrBuilder buildConstant(const DstOp &Res, const ConstantInt &Val);
+  virtual MachineInstrBuilder buildConstant(const DstOp &Res,
+                                            const ConstantInt &Val);
 
   /// Build and insert \p Res = G_CONSTANT \p Val
   ///
   /// G_CONSTANT is an integer constant with the specified size and value.
   ///
   /// \pre setBasicBlock or setMI must have been called.
   /// \pre \p Res must be a generic virtual register with scalar type.
   ///
   /// \return The newly created instruction.
   MachineInstrBuilder buildConstant(const DstOp &Res, int64_t Val);
 
   /// Build and insert \p Res = G_FCONSTANT \p Val
   ///
   /// G_FCONSTANT is a floating-point constant with the specified size and
   /// value.
   ///
   /// \pre setBasicBlock or setMI must have been called.
   /// \pre \p Res must be a generic virtual register with scalar type.
   ///
   /// \return The newly created instruction.
-  MachineInstrBuilder buildFConstant(const DstOp &Res, const ConstantFP &Val);
+  virtual MachineInstrBuilder buildFConstant(const DstOp &Res,
+                                             const ConstantFP &Val);
 
   MachineInstrBuilder buildFConstant(const DstOp &Res, double Val);
 
   /// Build and insert \p Res = COPY Op
   ///
   /// Register-to-register COPY sets \p Res to \p Op.
   ///
   /// \pre setBasicBlock or setMI must have been called.

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/CodeGen/MachineFunction.h

VariableDbgInfo(const DILocalVariable *Var, const DIExpression *Expr,
         : Var(Var), Expr(Expr), Slot(Slot), Loc(Loc) {}
   };
 
   class Delegate {
     virtual void anchor();
 
   public:
     virtual ~Delegate() = default;
-    virtual void MF_HandleInsertion(const MachineInstr &MI) = 0;
-    virtual void MF_HandleRemoval(const MachineInstr &MI) = 0;
+    /// Callback after an insertion. This should not modify the MI directly.
+    virtual void MF_HandleInsertion(MachineInstr &MI) = 0;
+    /// Callback before a removal. This should not modify the MI directly.
+    virtual void MF_HandleRemoval(MachineInstr &MI) = 0;
   };
 
 private:
   Delegate *TheDelegate = nullptr;
 
   // Callbacks for insertion and removal.
-  void handleInsertion(const MachineInstr &MI);
-  void handleRemoval(const MachineInstr &MI);
+  void handleInsertion(MachineInstr &MI);
+  void handleRemoval(MachineInstr &MI);
   friend struct ilist_traits<MachineInstr>;
 
 public:
   using VariableDbgInfoMapTy = SmallVector<VariableDbgInfo, 4>;
   VariableDbgInfoMapTy VariableDbgInfos;
 
   MachineFunction(const Function &F, const LLVMTargetMachine &Target,
                   const TargetSubtargetInfo &STI, unsigned FunctionNum,

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
if (!IsVector) {
                   maskAndShift(SizeInBits, VectorSizeFieldInfo);
       else
         RawData =
             maskAndShift(NumElements, PointerVectorElementsFieldInfo) |
             maskAndShift(SizeInBits, PointerVectorSizeFieldInfo) |
             maskAndShift(AddressSpace, PointerVectorAddressSpaceFieldInfo);
     }
   }
+
+  uint64_t getUniqueRAWLLTData() const {
+    return ((uint64_t)RawData) << 2 | ((uint64_t)IsPointer) << 1 |
+           ((uint64_t)IsVector);
+  }
 };
 
 inline raw_ostream& operator<<(raw_ostream &OS, const LLT &Ty) {
   Ty.print(OS);
   return OS;
 }
 
 template<> struct DenseMapInfo<LLT> {
   static inline LLT getEmptyKey() {
     LLT Invalid;
     Invalid.IsPointer = true;
     return Invalid;
   }
   static inline LLT getTombstoneKey() {
     LLT Invalid;
     Invalid.IsVector = true;
     return Invalid;
   }
   static inline unsigned getHashValue(const LLT &Ty) {
-    uint64_t Val = ((uint64_t)Ty.RawData) << 2 | ((uint64_t)Ty.IsPointer) << 1 |
-                   ((uint64_t)Ty.IsVector);
+    uint64_t Val = Ty.getUniqueRAWLLTData();
     return DenseMapInfo<uint64_t>::getHashValue(Val);
   }
   static bool isEqual(const LLT &LHS, const LLT &RHS) {
     return LHS == RHS;
   }
 };
 
 }
 
 #endif // LLVM_SUPPORT_LOWLEVELTYPEIMPL_H

lib/CodeGen/GlobalISel/CMakeLists.txt

 add_llvm_library(LLVMGlobalISel
+        CSEInfo.cpp
+        CSEMIRBuilder.cpp
         CallLowering.cpp
         GlobalISel.cpp
         Combiner.cpp
         CombinerHelper.cpp
         GISelChangeObserver.cpp
         IRTranslator.cpp
         InstructionSelect.cpp
         InstructionSelector.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);
+}
+/// -----------------------------------------
+
+/// --------- CSEConfig ---------- ///
+bool CSEConfig::shouldCSEOpc(unsigned Opc) {
+  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;
+}
+
+bool CSEConfigConstantOnly::shouldCSEOpc(unsigned Opc) {
+  return Opc == TargetOpcode::G_CONSTANT;
+}
+/// -----------------------------------------
+
+/// -------- GISelCSEInfo -------------//
+void GISelCSEInfo::setMF(MachineFunction &MF) {
+  this->MF = &MF;
+  this->MRI = &MF.getRegInfo();
+}
+
+GISelCSEInfo::~GISelCSEInfo() {}
+
+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) const {
+  // Only GISel opcodes are CSEable
+  if (!isPreISelGenericOpcode(Opc))
+    return false;
+  assert(CSEOpt.get() && "CSEConfig not set");
+  return CSEOpt->shouldCSEOpc(Opc);
+}
+
+void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(&MI); }
+void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(&MI); }
+void GISelCSEInfo::changingInstr(MachineInstr &MI) {
+  // For now, perform erase, followed by insert.
+  erasingInstr(MI);
+  createdInstr(MI);
+}
+void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(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();
+  CSEOpt.reset();
+  MRI = nullptr;
+  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);
+  addNodeIDFlag(MI->getFlags());
+  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 = Ty.getUniqueRAWLLTData();
+  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::addNodeIDFlag(unsigned Flag) const {
+  if (Flag)
+    ID.AddInteger(Flag);
+  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;
+}
+
+GISelCSEInfo &GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfig> CSEOpt,
+                                           bool Recompute) {
+  if (!AlreadyComputed || Recompute) {
+    Info.setCSEConfig(std::move(CSEOpt));
+    Info.analyze(*MF);
+    AlreadyComputed = true;
+  }
+  return Info;
+}
+void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) {
+  releaseMemory();
+  Wrapper.setMF(MF);
+  return false;
+}

lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp

+//===-- llvm/CodeGen/GlobalISel/CSEMIRBuilder.cpp - 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 implements the CSEMIRBuilder class which CSEs as it builds
+/// instructions.
+//===----------------------------------------------------------------------===//
+//
+
+#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
+#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
+
+using namespace llvm;
+
+bool CSEMIRBuilder::dominates(MachineBasicBlock::const_iterator A,
+                              MachineBasicBlock::const_iterator B) const {
+  auto MBBEnd = getMBB().end();
+  if (B == MBBEnd)
+    return true;
+  assert(A->getParent() == B->getParent() &&
+         "Iterators should be in same block");
+  const MachineBasicBlock *BBA = A->getParent();
+  MachineBasicBlock::const_iterator I = BBA->begin();
+  for (; &*I != A && &*I != B; ++I)
+    ;
+  return &*I == A;
+}
+
+MachineInstrBuilder
+CSEMIRBuilder::getDominatingInstrForID(FoldingSetNodeID &ID,
+                                       void *&NodeInsertPos) {
+  GISelCSEInfo *CSEInfo = getCSEInfo();
+  assert(CSEInfo && "Can't get here without setting CSEInfo");
+  MachineBasicBlock *CurMBB = &getMBB();
+  MachineInstr *MI =
+      CSEInfo->getMachineInstrIfExists(ID, CurMBB, NodeInsertPos);
+  if (MI) {
+    auto CurrPos = getInsertPt();
+    if (!dominates(MI, CurrPos))
+      CurMBB->splice(CurrPos, CurMBB, MI);
+    return MachineInstrBuilder(getMF(), MI);
+  }
+  return MachineInstrBuilder();
+}
+
+bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const {
+  const GISelCSEInfo *CSEInfo = getCSEInfo();
+  if (!CSEInfo || !CSEInfo->shouldCSE(Opc))
+    return false;
+  return true;
+}
+
+void CSEMIRBuilder::profileDstOp(const DstOp &Op,
+                                 GISelInstProfileBuilder &B) const {
+  switch (Op.getDstOpKind()) {
+  case DstOp::DstType::Ty_RC:
+    B.addNodeIDRegType(Op.getRegClass());
+    break;
+  default:
+    B.addNodeIDRegType(Op.getLLTTy(*getMRI()));
+    break;
+  }
+}
+
+void CSEMIRBuilder::profileSrcOp(const SrcOp &Op,
+                                 GISelInstProfileBuilder &B) const {
+  switch (Op.getSrcOpKind()) {
+  case SrcOp::SrcType::Ty_Predicate:
+    B.addNodeIDImmediate(static_cast<int64_t>(Op.getPredicate()));
+    break;
+  default:
+    B.addNodeIDRegType(Op.getReg());
+    break;
+  }
+}
+
+void CSEMIRBuilder::profileMBBOpcode(GISelInstProfileBuilder &B,
+                                     unsigned Opc) const {
+  // First add the MBB (Local CSE).
+  B.addNodeIDMBB(&getMBB());
+  // Then add the opcode.
+  B.addNodeIDOpcode(Opc);
+}
+
+void CSEMIRBuilder::profileEverything(unsigned Opc, ArrayRef<DstOp> DstOps,
+                                      ArrayRef<SrcOp> SrcOps,
+                                      Optional<unsigned> Flags,
+                                      GISelInstProfileBuilder &B) const {
+
+  profileMBBOpcode(B, Opc);
+  // Then add the DstOps.
+  profileDstOps(DstOps, B);
+  // Then add the SrcOps.
+  profileSrcOps(SrcOps, B);
+  // Add Flags if passed in.
+  if (Flags)
+    B.addNodeIDFlag(*Flags);
+}
+
+MachineInstrBuilder CSEMIRBuilder::memoizeMI(MachineInstrBuilder MIB,
+                                             void *NodeInsertPos) {
+  assert(canPerformCSEForOpc(MIB->getOpcode()) &&
+         "Attempting to CSE illegal op");
+  MachineInstr *MIBInstr = MIB;
+  getCSEInfo()->insertInstr(MIBInstr, NodeInsertPos);
+  return MIB;
+}
+
+bool CSEMIRBuilder::checkCopyToDefsPossible(ArrayRef<DstOp> DstOps) {
+  if (DstOps.size() == 1)
+    return true; // always possible to emit copy to just 1 vreg.
+
+  return std::all_of(DstOps.begin(), DstOps.end(), [](const DstOp &Op) {
+    DstOp::DstType DT = Op.getDstOpKind();
+    return DT == DstOp::DstType::Ty_LLT || DT == DstOp::DstType::Ty_RC;
+  });
+}
+
+MachineInstrBuilder
+CSEMIRBuilder::generateCopiesIfRequired(ArrayRef<DstOp> DstOps,
+                                        MachineInstrBuilder &MIB) {
+  assert(checkCopyToDefsPossible(DstOps) &&
+         "Impossible return a single MIB with copies to multiple defs");
+  if (DstOps.size() == 1) {
+    const DstOp &Op = DstOps[0];
+    if (Op.getDstOpKind() == DstOp::DstType::Ty_Reg)
+      return buildCopy(Op.getReg(), MIB->getOperand(0).getReg());
+  }
+  return MIB;
+}
+
+MachineInstrBuilder CSEMIRBuilder::buildInstr(unsigned Opc,
+                                              ArrayRef<DstOp> DstOps,
+                                              ArrayRef<SrcOp> SrcOps,
+                                              Optional<unsigned> Flag) {
+  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: {
+    // Try to constant fold these.
+    assert(SrcOps.size() == 2 && "Invalid sources");
+    assert(DstOps.size() == 1 && "Invalid dsts");
+    if (Optional<APInt> Cst = ConstantFoldBinOp(Opc, SrcOps[0].getReg(),
+                                                SrcOps[1].getReg(), *getMRI()))
+      return buildConstant(DstOps[0], Cst->getSExtValue());
+    break;
+  }
+  }
+  bool CanCopy = checkCopyToDefsPossible(DstOps);
+  if (!canPerformCSEForOpc(Opc))
+    return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
+  // If we can CSE this instruction, but involves generating copies to multiple
+  // regs, give up. This frequently happens to UNMERGEs.
+  if (!CanCopy) {
+    auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
+    // CSEInfo would have tracked this instruction. Remove it from the temporary
+    // insts.
+    getCSEInfo()->handleRemoveInst(&*MIB);
+    return MIB;
+  }
+  FoldingSetNodeID ID;
+  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
+  void *InsertPos = nullptr;
+  profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder);
+  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
+  if (MIB) {
+    // Handle generating copies here.
+    return generateCopiesIfRequired(DstOps, MIB);
+  }
+  // This instruction does not exist in the CSEInfo. Build it and CSE it.
+  MachineInstrBuilder NewMIB =
+      MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
+  return memoizeMI(NewMIB, InsertPos);
+}
+
+MachineInstrBuilder CSEMIRBuilder::buildConstant(const DstOp &Res,
+                                                 const ConstantInt &Val) {
+  constexpr unsigned Opc = TargetOpcode::G_CONSTANT;
+  if (!canPerformCSEForOpc(Opc))
+    return MachineIRBuilder::buildConstant(Res, Val);
+  FoldingSetNodeID ID;
+  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
+  void *InsertPos = nullptr;
+  profileMBBOpcode(ProfBuilder, Opc);
+  profileDstOp(Res, ProfBuilder);
+  ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateCImm(&Val));
+  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
+  if (MIB) {
+    // Handle generating copies here.
+    return generateCopiesIfRequired({Res}, MIB);
+  }
+  MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val);
+  return memoizeMI(NewMIB, InsertPos);
+}
+
+MachineInstrBuilder CSEMIRBuilder::buildFConstant(const DstOp &Res,
+                                                  const ConstantFP &Val) {
+  constexpr unsigned Opc = TargetOpcode::G_FCONSTANT;
+  if (!canPerformCSEForOpc(Opc))
+    return MachineIRBuilder::buildFConstant(Res, Val);
+  FoldingSetNodeID ID;
+  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
+  void *InsertPos = nullptr;
+  profileMBBOpcode(ProfBuilder, Opc);
+  profileDstOp(Res, ProfBuilder);
+  ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateFPImm(&Val));
+  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
+  if (MIB) {
+    // Handle generating copies here.
+    return generateCopiesIfRequired({Res}, MIB);
+  }
+  MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val);
+  return memoizeMI(NewMIB, InsertPos);
+}

lib/CodeGen/GlobalISel/Combiner.cpp

 //===-- lib/CodeGen/GlobalISel/Combiner.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/CSEMIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
 #include "llvm/CodeGen/GlobalISel/GISelWorkList.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 {
 /// This class acts as the glue the joins the CombinerHelper to the overall
 /// Combine algorithm. The CombinerHelper is intended to report the
 /// modifications it makes to the MIR to the GISelChangeObserver and the
 /// observer subclass will act on these events. In this case, instruction
 /// erasure will cancel any future visits to the erased instruction and
 /// instruction creation will schedule that instruction for a future visit.
 /// Other Combiner implementations may require more complex behaviour from
 /// their GISelChangeObserver subclass.
-class WorkListMaintainer : public GISelChangeObserver,
-                           public MachineFunction::Delegate {
+class WorkListMaintainer : public GISelChangeObserver {
   using WorkListTy = GISelWorkList<512>;
-  MachineFunction &MF;
   WorkListTy &WorkList;
   /// The instructions that have been created but we want to report once they
   /// have their operands. This is only maintained if debug output is requested.
   SmallPtrSet<const MachineInstr *, 4> CreatedInstrs;
 
 public:
-  WorkListMaintainer(MachineFunction &MF, WorkListTy &WorkList)
-      : GISelChangeObserver(), MF(MF), WorkList(WorkList) {
-    MF.setDelegate(this);
-  }
+  WorkListMaintainer(WorkListTy &WorkList)
+      : GISelChangeObserver(), WorkList(WorkList) {}
   virtual ~WorkListMaintainer() {
-    MF.resetDelegate(this);
   }
 
-  void erasingInstr(const MachineInstr &MI) override {
+  void erasingInstr(MachineInstr &MI) override {
     LLVM_DEBUG(dbgs() << "Erased: " << MI << "\n");
     WorkList.remove(&MI);
   }
-  void createdInstr(const MachineInstr &MI) override {
+  void createdInstr(MachineInstr &MI) override {
     LLVM_DEBUG(dbgs() << "Creating: " << MI << "\n");
     WorkList.insert(&MI);
     LLVM_DEBUG(CreatedInstrs.insert(&MI));
   }
-  void changingInstr(const MachineInstr &MI) override {
+  void changingInstr(MachineInstr &MI) override {
     LLVM_DEBUG(dbgs() << "Changing: " << MI << "\n");
     WorkList.insert(&MI);
   }
-  void changedInstr(const MachineInstr &MI) override {
+  void changedInstr(MachineInstr &MI) override {
     LLVM_DEBUG(dbgs() << "Changed: " << MI << "\n");
     WorkList.insert(&MI);
   }
 
   void reportFullyCreatedInstrs() {
     LLVM_DEBUG(for (const auto *MI
                     : CreatedInstrs) {
       dbgs() << "Created: ";
       MI->print(dbgs());
     });
     LLVM_DEBUG(CreatedInstrs.clear());
   }
-
-  void MF_HandleInsertion(const MachineInstr &MI) override {
-    createdInstr(MI);
-  }
-  void MF_HandleRemoval(const MachineInstr &MI) override {
-    erasingInstr(MI);
-  }
 };
 }
 
 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;
 
+  Builder =
+      CSEInfo ? make_unique<CSEMIRBuilder>() : make_unique<MachineIRBuilder>();
   MRI = &MF.getRegInfo();
-  Builder.setMF(MF);
+  Builder->setMF(MF);
+  if (CSEInfo)
+    Builder->setCSEInfo(CSEInfo);
 
   LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n');
 
   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
 
   bool MFChanged = false;
   bool Changed;
+  MachineIRBuilder &B = *Builder.get();
 
   do {
     // Collect all instructions. Do a post order traversal for basic blocks and
     // insert with list bottom up, so while we pop_back_val, we'll traverse top
     // down RPOT.
     Changed = false;
-    GISelWorkList<512> WorkList(&MF);
-    WorkListMaintainer Observer(MF, WorkList);
+    GISelWorkList<512> WorkList;
+    WorkListMaintainer Observer(WorkList);
+    GISelObserverWrapper WrapperObserver(&Observer);
+    if (CSEInfo)
+      WrapperObserver.addObserver(CSEInfo);
+    RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
     for (MachineBasicBlock *MBB : post_order(&MF)) {
       if (MBB->empty())
         continue;
       for (auto MII = MBB->rbegin(), MIE = MBB->rend(); MII != MIE;) {
         MachineInstr *CurMI = &*MII;
         ++MII;
         // Erase dead insts before even adding to the list.
         if (isTriviallyDead(*CurMI, *MRI)) {
           LLVM_DEBUG(dbgs() << *CurMI << "Is dead; erasing.\n");
           CurMI->eraseFromParentAndMarkDBGValuesForRemoval();
           continue;
         }
         WorkList.insert(CurMI);
       }
     }
     // Main Loop. Process the instructions here.
     while (!WorkList.empty()) {
       MachineInstr *CurrInst = WorkList.pop_back_val();
       LLVM_DEBUG(dbgs() << "\nTry combining " << *CurrInst;);
-      Changed |= CInfo.combine(Observer, *CurrInst, Builder);
+      Changed |= CInfo.combine(WrapperObserver, *CurrInst, B);
       Observer.reportFullyCreatedInstrs();
     }
     MFChanged |= Changed;
   } while (Changed);
 
   return MFChanged;
 }

lib/CodeGen/GlobalISel/GISelChangeObserver.cpp

void GISelChangeObserver::changingAllUsesOfReg(
   }
 }
 
 void GISelChangeObserver::finishedChangingAllUsesOfReg() {
   for (auto *ChangedMI : ChangingAllUsesOfReg)
     changedInstr(*ChangedMI);
 }
 
+RAIIDelegateInstaller::RAIIDelegateInstaller(MachineFunction &MF,
+                                             MachineFunction::Delegate *Del)
+    : MF(MF), Delegate(Del) {
+  // Register this as the delegate for handling insertions and deletions of
+  // instructions.
+  MF.setDelegate(Del);
+}
+
+RAIIDelegateInstaller::~RAIIDelegateInstaller() { MF.resetDelegate(Delegate); }

lib/CodeGen/GlobalISel/IRTranslator.cpp

 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/CodeGen/Analysis.h"
 #include "llvm/CodeGen/GlobalISel/CallLowering.h"
+#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
 #include "llvm/CodeGen/LowLevelType.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"

 #include <string>
 #include <utility>
 #include <vector>
 
 #define DEBUG_TYPE "irtranslator"
 
 using namespace llvm;
 
+static cl::opt<bool>
+    EnableCSEInIRTranslator("enable-cse-in-irtranslator",
+                            cl::desc("Should enable CSE in irtranslator"),
+                            cl::Optional, cl::init(false));
 char IRTranslator::ID = 0;
 
 INITIALIZE_PASS_BEGIN(IRTranslator, DEBUG_TYPE, "IRTranslator LLVM IR -> MI",
                 false, false)
 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
+INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
 INITIALIZE_PASS_END(IRTranslator, DEBUG_TYPE, "IRTranslator LLVM IR -> MI",
                 false, false)
 
 static void reportTranslationError(MachineFunction &MF,
                                    const TargetPassConfig &TPC,
                                    OptimizationRemarkEmitter &ORE,
                                    OptimizationRemarkMissed &R) {
   MF.getProperties().set(MachineFunctionProperties::Property::FailedISel);

 IRTranslator::IRTranslator() : MachineFunctionPass(ID) {
   initializeIRTranslatorPass(*PassRegistry::getPassRegistry());
 }
 
 #ifndef NDEBUG
 namespace {
 /// Verify that every instruction created has the same DILocation as the
 /// instruction being translated.
-class DILocationVerifier : MachineFunction::Delegate {
-  MachineFunction &MF;
+class DILocationVerifier : public GISelChangeObserver {
   const Instruction *CurrInst = nullptr;
 
 public:
-  DILocationVerifier(MachineFunction &MF) : MF(MF) { MF.setDelegate(this); }
-  ~DILocationVerifier() { MF.resetDelegate(this); }
+  DILocationVerifier() = default;
+  ~DILocationVerifier() = default;
 
   const Instruction *getCurrentInst() const { return CurrInst; }
   void setCurrentInst(const Instruction *Inst) { CurrInst = Inst; }
 
-  void MF_HandleInsertion(const MachineInstr &MI) override {
+  void erasingInstr(MachineInstr &MI) override {}
+  void changingInstr(MachineInstr &MI) override {}
+  void changedInstr(MachineInstr &MI) override {}
+
+  void createdInstr(MachineInstr &MI) override {
     assert(getCurrentInst() && "Inserted instruction without a current MI");
 
     // Only print the check message if we're actually checking it.
 #ifndef NDEBUG
     LLVM_DEBUG(dbgs() << "Checking DILocation from " << *CurrInst
                       << " was copied to " << MI);
 #endif
     assert(CurrInst->getDebugLoc() == MI.getDebugLoc() &&
            "Line info was not transferred to all instructions");
   }
-  void MF_HandleRemoval(const MachineInstr &MI) override {}
 };
 } // namespace
 #endif // ifndef NDEBUG
 
 
 void IRTranslator::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<StackProtector>();
   AU.addRequired<TargetPassConfig>();
+  AU.addRequired<GISelCSEAnalysisWrapperPass>();
   getSelectionDAGFallbackAnalysisUsage(AU);
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 static void computeValueLLTs(const DataLayout &DL, Type &Ty,
                              SmallVectorImpl<LLT> &ValueTys,
                              SmallVectorImpl<uint64_t> *Offsets = nullptr,
                              uint64_t StartingOffset = 0) {
MIRBuilder.buildAtomicRMW(
                                 Flags, DL->getTypeStoreSize(ResType),
                                 getMemOpAlignment(I), AAMDNodes(), nullptr,
                                 I.getSyncScopeID(), I.getOrdering()));
   return true;
 }
 
 void IRTranslator::finishPendingPhis() {
 #ifndef NDEBUG
-  DILocationVerifier Verifier(*MF);
+  DILocationVerifier Verifier;
+  GISelObserverWrapper WrapperObserver(&Verifier);
+  RAIIDelegateInstaller DelInstall(*MF, &WrapperObserver);
 #endif // ifndef NDEBUG
   for (auto &Phi : PendingPHIs) {
     const PHINode *PI = Phi.first;
     ArrayRef<MachineInstr *> ComponentPHIs = Phi.second;
-    EntryBuilder.setDebugLoc(PI->getDebugLoc());
+    EntryBuilder->setDebugLoc(PI->getDebugLoc());
 #ifndef NDEBUG
     Verifier.setCurrentInst(PI);
 #endif // ifndef NDEBUG
 
     // All MachineBasicBlocks exist, add them to the PHI. We assume IRTranslator
     // won't create extra control flow here, otherwise we need to find the
     // dominating predecessor here (or perhaps force the weirder IRTranslators
     // to provide a simple boundary).
bool IRTranslator::valueIsSplit(const Value &V,
   SmallVector<LLT, 4> SplitTys;
   if (Offsets && !Offsets->empty())
     Offsets->clear();
   computeValueLLTs(*DL, *V.getType(), SplitTys, Offsets);
   return SplitTys.size() > 1;
 }
 
 bool IRTranslator::translate(const Instruction &Inst) {
-  CurBuilder.setDebugLoc(Inst.getDebugLoc());
-  EntryBuilder.setDebugLoc(Inst.getDebugLoc());
+  CurBuilder->setDebugLoc(Inst.getDebugLoc());
+  EntryBuilder->setDebugLoc(Inst.getDebugLoc());
   switch(Inst.getOpcode()) {
-#define HANDLE_INST(NUM, OPCODE, CLASS) \
-    case Instruction::OPCODE: return translate##OPCODE(Inst, CurBuilder);
+#define HANDLE_INST(NUM, OPCODE, CLASS)                                        \
+  case Instruction::OPCODE:                                                    \
+    return translate##OPCODE(Inst, *CurBuilder.get());
 #include "llvm/IR/Instruction.def"
   default:
     return false;
   }
 }
 
 bool IRTranslator::translate(const Constant &C, unsigned Reg) {
   if (auto CI = dyn_cast<ConstantInt>(&C))
-    EntryBuilder.buildConstant(Reg, *CI);
+    EntryBuilder->buildConstant(Reg, *CI);
   else if (auto CF = dyn_cast<ConstantFP>(&C))
-    EntryBuilder.buildFConstant(Reg, *CF);
+    EntryBuilder->buildFConstant(Reg, *CF);
   else if (isa<UndefValue>(C))
-    EntryBuilder.buildUndef(Reg);
+    EntryBuilder->buildUndef(Reg);
   else if (isa<ConstantPointerNull>(C)) {
     // As we are trying to build a constant val of 0 into a pointer,
     // insert a cast to make them correct with respect to types.
     unsigned NullSize = DL->getTypeSizeInBits(C.getType());
     auto *ZeroTy = Type::getIntNTy(C.getContext(), NullSize);
     auto *ZeroVal = ConstantInt::get(ZeroTy, 0);
     unsigned ZeroReg = getOrCreateVReg(*ZeroVal);
-    EntryBuilder.buildCast(Reg, ZeroReg);
+    EntryBuilder->buildCast(Reg, ZeroReg);
   } else if (auto GV = dyn_cast<GlobalValue>(&C))
-    EntryBuilder.buildGlobalValue(Reg, GV);
+    EntryBuilder->buildGlobalValue(Reg, GV);
   else if (auto CAZ = dyn_cast<ConstantAggregateZero>(&C)) {
     if (!CAZ->getType()->isVectorTy())
       return false;
     // Return the scalar if it is a <1 x Ty> vector.
     if (CAZ->getNumElements() == 1)
       return translate(*CAZ->getElementValue(0u), Reg);
     SmallVector<unsigned, 4> Ops;
     for (unsigned i = 0; i < CAZ->getNumElements(); ++i) {
       Constant &Elt = *CAZ->getElementValue(i);
       Ops.push_back(getOrCreateVReg(Elt));
     }
-    EntryBuilder.buildBuildVector(Reg, Ops);
+    EntryBuilder->buildBuildVector(Reg, Ops);
   } else if (auto CV = dyn_cast<ConstantDataVector>(&C)) {
     // Return the scalar if it is a <1 x Ty> vector.
     if (CV->getNumElements() == 1)
       return translate(*CV->getElementAsConstant(0), Reg);
     SmallVector<unsigned, 4> Ops;
     for (unsigned i = 0; i < CV->getNumElements(); ++i) {
       Constant &Elt = *CV->getElementAsConstant(i);
       Ops.push_back(getOrCreateVReg(Elt));
     }
-    EntryBuilder.buildBuildVector(Reg, Ops);
+    EntryBuilder->buildBuildVector(Reg, Ops);
   } else if (auto CE = dyn_cast<ConstantExpr>(&C)) {
     switch(CE->getOpcode()) {
-#define HANDLE_INST(NUM, OPCODE, CLASS)                         \
-      case Instruction::OPCODE: return translate##OPCODE(*CE, EntryBuilder);
+#define HANDLE_INST(NUM, OPCODE, CLASS)                                        \
+  case Instruction::OPCODE:                                                    \
+    return translate##OPCODE(*CE, *EntryBuilder.get());
 #include "llvm/IR/Instruction.def"
     default:
       return false;
     }
   } else if (auto CV = dyn_cast<ConstantVector>(&C)) {
     if (CV->getNumOperands() == 1)
       return translate(*CV->getOperand(0), Reg);
     SmallVector<unsigned, 4> Ops;
     for (unsigned i = 0; i < CV->getNumOperands(); ++i) {
       Ops.push_back(getOrCreateVReg(*CV->getOperand(i)));
     }
-    EntryBuilder.buildBuildVector(Reg, Ops);
+    EntryBuilder->buildBuildVector(Reg, Ops);
   } else if (auto *BA = dyn_cast<BlockAddress>(&C)) {
-    EntryBuilder.buildBlockAddress(Reg, BA);
+    EntryBuilder->buildBlockAddress(Reg, BA);
   } else
     return false;
 
   return true;
 }
 
 void IRTranslator::finalizeFunction() {
   // Release the memory used by the different maps we
   // 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();
+  EntryBuilder.reset();
+  CurBuilder.reset();
 }
 
 bool IRTranslator::runOnMachineFunction(MachineFunction &CurMF) {
   MF = &CurMF;
   const Function &F = MF->getFunction();
   if (F.empty())
     return false;
+  GISelCSEAnalysisWrapper &Wrapper =
+      getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
+  // Set the CSEConfig and run the analysis.
+  GISelCSEInfo *CSEInfo = nullptr;
+  TPC = &getAnalysis<TargetPassConfig>();
+  bool IsO0 = TPC->getOptLevel() == CodeGenOpt::Level::None;
+  // Disable CSE for O0.
+  bool EnableCSE = !IsO0 && EnableCSEInIRTranslator;
+  if (EnableCSE) {
+    EntryBuilder = make_unique<CSEMIRBuilder>(CurMF);
+    std::unique_ptr<CSEConfig> Config = make_unique<CSEConfig>();
+    CSEInfo = &Wrapper.get(std::move(Config));
+    EntryBuilder->setCSEInfo(CSEInfo);
+    CurBuilder = make_unique<CSEMIRBuilder>(CurMF);
+    CurBuilder->setCSEInfo(CSEInfo);
+  } else {
+    EntryBuilder = make_unique<MachineIRBuilder>();
+    CurBuilder = make_unique<MachineIRBuilder>();
+  }
   CLI = MF->getSubtarget().getCallLowering();
-  CurBuilder.setMF(*MF);
-  EntryBuilder.setMF(*MF);
+  CurBuilder->setMF(*MF);
+  EntryBuilder->setMF(*MF);
   MRI = &MF->getRegInfo();
   DL = &F.getParent()->getDataLayout();
-  TPC = &getAnalysis<TargetPassConfig>();
   ORE = llvm::make_unique<OptimizationRemarkEmitter>(&F);
 
   assert(PendingPHIs.empty() && "stale PHIs");
 
   if (!DL->isLittleEndian()) {
     // Currently we don't properly handle big endian code.
     OptimizationRemarkMissed R("gisel-irtranslator", "GISelFailure",
                                F.getSubprogram(), &F.getEntryBlock());
     R << "unable to translate in big endian mode";
     reportTranslationError(*MF, *TPC, *ORE, R);
   }
 
   // Release the per-function state when we return, whether we succeeded or not.
   auto FinalizeOnReturn = make_scope_exit([this]() { finalizeFunction(); });
 
   // Setup a separate basic-block for the arguments and constants
   MachineBasicBlock *EntryBB = MF->CreateMachineBasicBlock();
   MF->push_back(EntryBB);
-  EntryBuilder.setMBB(*EntryBB);
+  EntryBuilder->setMBB(*EntryBB);
 
   // Create all blocks, in IR order, to preserve the layout.
   for (const BasicBlock &BB: F) {
     auto *&MBB = BBToMBB[&BB];
 
     MBB = MF->CreateMachineBasicBlock(&BB);
     MF->push_back(MBB);
 
if (Arg.hasSwiftErrorAttr() || Arg.hasSwiftSelfAttr()) {
                                  F.getSubprogram(), &F.getEntryBlock());
       R << "unable to lower arguments due to swifterror/swiftself: "
         << ore::NV("Prototype", F.getType());
       reportTranslationError(*MF, *TPC, *ORE, R);
       return false;
     }
   }
 
-  if (!CLI->lowerFormalArguments(EntryBuilder, F, VRegArgs)) {
+  if (!CLI->lowerFormalArguments(*EntryBuilder.get(), F, VRegArgs)) {
     OptimizationRemarkMissed R("gisel-irtranslator", "GISelFailure",
                                F.getSubprogram(), &F.getEntryBlock());
     R << "unable to lower arguments: " << ore::NV("Prototype", F.getType());
     reportTranslationError(*MF, *TPC, *ORE, R);
     return false;
   }
 
   auto ArgIt = F.arg_begin();
   for (auto &VArg : VRegArgs) {
     // If the argument is an unsplit scalar then don't use unpackRegs to avoid
     // creating redundant copies.
     if (!valueIsSplit(*ArgIt, VMap.getOffsets(*ArgIt))) {
       auto &VRegs = *VMap.getVRegs(cast<Value>(*ArgIt));
       assert(VRegs.empty() && "VRegs already populated?");
       VRegs.push_back(VArg);
     } else {
-      unpackRegs(*ArgIt, VArg, EntryBuilder);
+      unpackRegs(*ArgIt, VArg, *EntryBuilder.get());
     }
     ArgIt++;
   }
 
   // Need to visit defs before uses when translating instructions.
+  GISelObserverWrapper WrapperObserver;
+  if (EnableCSE && CSEInfo)
+    WrapperObserver.addObserver(CSEInfo);
   {
     ReversePostOrderTraversal<const Function *> RPOT(&F);
 #ifndef NDEBUG
-    DILocationVerifier Verifier(*MF);
+    DILocationVerifier Verifier;
+    WrapperObserver.addObserver(&Verifier);
 #endif // ifndef NDEBUG
+    RAIIDelegateInstaller DelInstall(*MF, &WrapperObserver);
     for (const BasicBlock *BB : RPOT) {
       MachineBasicBlock &MBB = getMBB(*BB);
       // Set the insertion point of all the following translations to
       // the end of this basic block.
-      CurBuilder.setMBB(MBB);
+      CurBuilder->setMBB(MBB);
 
       for (const Instruction &Inst : *BB) {
 #ifndef NDEBUG
         Verifier.setCurrentInst(&Inst);
 #endif // ifndef NDEBUG
         if (translate(Inst))
           continue;
 
         OptimizationRemarkMissed R("gisel-irtranslator", "GISelFailure",
                                    Inst.getDebugLoc(), BB);
         R << "unable to translate instruction: " << ore::NV("Opcode", &Inst);
 
         if (ORE->allowExtraAnalysis("gisel-irtranslator")) {
           std::string InstStrStorage;
           raw_string_ostream InstStr(InstStrStorage);
           InstStr << Inst;
 
           R << ": '" << InstStr.str() << "'";
         }
 
         reportTranslationError(*MF, *TPC, *ORE, R);
         return false;
       }
     }
+#ifndef NDEBUG
+    WrapperObserver.removeObserver(&Verifier);
+#endif
   }
 
   finishPendingPhis();
 
   // Merge the argument lowering and constants block with its single
   // successor, the LLVM-IR entry block.  We want the basic block to
   // be maximal.
   assert(EntryBB->succ_size() == 1 &&

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/CSEMIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.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;
 
+static cl::opt<bool>
+    EnableCSEInLegalizer("enable-cse-in-legalizer",
+                         cl::desc("Should enable CSE in Legalizer"),
+                         cl::Optional, cl::init(false));
+
 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) {

 class LegalizerWorkListManager : public GISelChangeObserver {
   InstListTy &InstList;
   ArtifactListTy &ArtifactList;
 
 public:
   LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
       : InstList(Insts), ArtifactList(Arts) {}
 
-  void createdInstr(const MachineInstr &MI) override {
+  void createdInstr(MachineInstr &MI) override {
     // 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);
     }
     LLVM_DEBUG(dbgs() << ".. .. New MI: " << MI);
   }
 
-  void erasingInstr(const MachineInstr &MI) override {
+  void erasingInstr(MachineInstr &MI) override {
     LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
     InstList.remove(&MI);
     ArtifactList.remove(&MI);
   }
 
-  void changingInstr(const MachineInstr &MI) override {
+  void changingInstr(MachineInstr &MI) override {
     LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
   }
 
-  void changedInstr(const MachineInstr &MI) override {
+  void changedInstr(MachineInstr &MI) override {
     // When insts change, we want to revisit them to legalize them again.
     // We'll consider them the same as created.
     LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
     createdInstr(MI);
   }
 };
 } // namespace
 
 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>();
+  GISelCSEAnalysisWrapper &Wrapper =
+      getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
 
   const size_t NumBlocks = MF.size();
   MachineRegisterInfo &MRI = MF.getRegInfo();
 
   // Populate Insts
-  InstListTy InstList(&MF);
-  ArtifactListTy ArtifactList(&MF);
+  InstListTy InstList;
+  ArtifactListTy ArtifactList;
   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
   // Perform legalization bottom up so we can DCE as we legalize.
   // Traverse BB in RPOT and within each basic block, add insts top down,
   // so when we pop_back_val in the legalization process, we traverse bottom-up.
   for (auto *MBB : RPOT) {
     if (MBB->empty())
       continue;
     for (MachineInstr &MI : *MBB) {
       // Only legalize pre-isel generic instructions: others don't have types
       // and are assumed to be legal.
       if (!isPreISelGenericOpcode(MI.getOpcode()))
         continue;
       if (isArtifact(MI))
         ArtifactList.insert(&MI);
       else
         InstList.insert(&MI);
     }
   }
+  std::unique_ptr<MachineIRBuilder> MIRBuilder;
+  GISelCSEInfo *CSEInfo = nullptr;
+  bool IsO0 = TPC.getOptLevel() == CodeGenOpt::Level::None;
+  // Disable CSE for O0.
+  bool EnableCSE = !IsO0 && EnableCSEInLegalizer;
+  if (EnableCSE) {
+    MIRBuilder = make_unique<CSEMIRBuilder>();
+    std::unique_ptr<CSEConfig> Config = make_unique<CSEConfig>();
+    CSEInfo = &Wrapper.get(std::move(Config));
+    MIRBuilder->setCSEInfo(CSEInfo);
+  } else
+    MIRBuilder = make_unique<MachineIRBuilder>();
+  // This observer keeps the worklist updated.
   LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
-  LegalizerHelper Helper(MF, WorkListObserver);
+  // We want both WorkListObserver as well as CSEInfo to observe all changes.
+  // Use the wrapper observer.
+  GISelObserverWrapper WrapperObserver(&WorkListObserver);
+  if (EnableCSE && CSEInfo)
+    WrapperObserver.addObserver(CSEInfo);
+  // Now install the observer as the delegate to MF.
+  // This will keep all the observers notified about new insertions/deletions.
+  RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
+  LegalizerHelper Helper(MF, WrapperObserver, *MIRBuilder.get());
   const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
-  LegalizationArtifactCombiner ArtCombiner(Helper.MIRBuilder, MF.getRegInfo(), LInfo);
-  auto RemoveDeadInstFromLists = [&WorkListObserver](MachineInstr *DeadMI) {
-    WorkListObserver.erasingInstr(*DeadMI);
+  LegalizationArtifactCombiner ArtCombiner(*MIRBuilder.get(), MF.getRegInfo(),
+                                           LInfo);
+  auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) {
+    WrapperObserver.erasingInstr(*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");

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,
-                                 GISelChangeObserver &Observer)
-    : MRI(MF.getRegInfo()), LI(*MF.getSubtarget().getLegalizerInfo()),
-      Observer(Observer) {
+                                 GISelChangeObserver &Observer,
+                                 MachineIRBuilder &Builder)
+    : MIRBuilder(Builder), MRI(MF.getRegInfo()),
+      LI(*MF.getSubtarget().getLegalizerInfo()), Observer(Observer) {
   MIRBuilder.setMF(MF);
   MIRBuilder.setChangeObserver(Observer);
 }
 
 LegalizerHelper::LegalizerHelper(MachineFunction &MF, const LegalizerInfo &LI,
-                                 GISelChangeObserver &Observer)
-    : MRI(MF.getRegInfo()), LI(LI), Observer(Observer) {
+                                 GISelChangeObserver &Observer,
+                                 MachineIRBuilder &B)
+    : MIRBuilder(B), MRI(MF.getRegInfo()), LI(LI), Observer(Observer) {
   MIRBuilder.setMF(MF);
   MIRBuilder.setChangeObserver(Observer);
 }
 LegalizerHelper::LegalizeResult
 LegalizerHelper::legalizeInstrStep(MachineInstr &MI) {
   LLVM_DEBUG(dbgs() << "Legalizing: "; MI.print(dbgs()));
 
   auto Step = LI.getAction(MI, MRI);

lib/CodeGen/GlobalISel/MachineIRBuilder.cpp

 }
 
 void MachineIRBuilder::setInstr(MachineInstr &MI) {
   assert(MI.getParent() && "Instruction is not part of a basic block");
   setMBB(*MI.getParent());
   State.II = MI.getIterator();
 }
 
+void MachineIRBuilder::setCSEInfo(GISelCSEInfo *Info) { State.CSEInfo = Info; }
+
 void MachineIRBuilder::setInsertPt(MachineBasicBlock &MBB,
                                    MachineBasicBlock::iterator II) {
   assert(MBB.getParent() == &getMF() &&
          "Basic block is in a different function");
   State.MBB = &MBB;
   State.II = II;
 }
 

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/CodeGen/MachineFunction.cpp

MachineFunction::MachineFunction(const Function &F,
                                  const LLVMTargetMachine &Target,
                                  const TargetSubtargetInfo &STI,
                                  unsigned FunctionNum, MachineModuleInfo &mmi)
     : F(F), Target(Target), STI(&STI), Ctx(mmi.getContext()), MMI(mmi) {
   FunctionNumber = FunctionNum;
   init();
 }
 
-void MachineFunction::handleInsertion(const MachineInstr &MI) {
+void MachineFunction::handleInsertion(MachineInstr &MI) {
   if (TheDelegate)
     TheDelegate->MF_HandleInsertion(MI);
 }
 
-void MachineFunction::handleRemoval(const MachineInstr &MI) {
+void MachineFunction::handleRemoval(MachineInstr &MI) {
   if (TheDelegate)
     TheDelegate->MF_HandleRemoval(MI);
 }
 
 void MachineFunction::init() {
   // Assume the function starts in SSA form with correct liveness.
   Properties.set(MachineFunctionProperties::Property::IsSSA);
   Properties.set(MachineFunctionProperties::Property::TracksLiveness);

lib/Target/AArch64/AArch64PreLegalizerCombiner.cpp

 
 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/Mips/MipsPreLegalizerCombiner.cpp

 
 bool MipsPreLegalizerCombiner::runOnMachineFunction(MachineFunction &MF) {
   if (MF.getProperties().hasProperty(
           MachineFunctionProperties::Property::FailedISel))
     return false;
   auto *TPC = &getAnalysis<TargetPassConfig>();
   MipsPreLegalizerCombinerInfo PCInfo;
   Combiner C(PCInfo, TPC);
-  return C.combineMachineInstrs(MF);
+  return C.combineMachineInstrs(MF, nullptr);
 }
 
 char MipsPreLegalizerCombiner::ID = 0;
 INITIALIZE_PASS_BEGIN(MipsPreLegalizerCombiner, DEBUG_TYPE,
                       "Combine Mips machine instrs before legalization", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
 INITIALIZE_PASS_END(MipsPreLegalizerCombiner, DEBUG_TYPE,
                     "Combine Mips machine instrs before legalization", false,
                     false)
 
 namespace llvm {
 FunctionPass *createMipsPreLegalizeCombiner() {
   return new MipsPreLegalizerCombiner();
 }
 } // end namespace llvm

test/CodeGen/AArch64/GlobalISel/call-translator-cse.ll

+; RUN: llc -mtriple=aarch64-linux-gnu -O1 -stop-after=irtranslator -enable-cse-in-irtranslator=1 -global-isel -verify-machineinstrs %s -o - 2>&1 | FileCheck %s
+
+; CHECK-LABEL: name: test_split_struct
+; CHECK: [[ADDR:%[0-9]+]]:_(p0) = COPY $x0
+; CHECK: [[LO:%[0-9]+]]:_(s64) = G_LOAD %0(p0) :: (load 8 from %ir.ptr)
+; CHECK: [[CST:%[0-9]+]]:_(s64) = G_CONSTANT i64 8
+; CHECK: [[GEP:%[0-9]+]]:_(p0) = G_GEP [[ADDR]], [[CST]](s64)
+; CHECK: [[HI:%[0-9]+]]:_(s64) = G_LOAD [[GEP]](p0) :: (load 8 from %ir.ptr + 8)
+
+; CHECK: [[IMPDEF:%[0-9]+]]:_(s128) = G_IMPLICIT_DEF
+; CHECK: [[INS1:%[0-9]+]]:_(s128) = G_INSERT [[IMPDEF]], [[LO]](s64), 0
+; CHECK: [[INS2:%[0-9]+]]:_(s128) = G_INSERT [[INS1]], [[HI]](s64), 64
+; CHECK: [[EXTLO:%[0-9]+]]:_(s64) = G_EXTRACT [[INS2]](s128), 0
+; CHECK: [[EXTHI:%[0-9]+]]:_(s64) = G_EXTRACT [[INS2]](s128), 64
+
+; CHECK: [[SP:%[0-9]+]]:_(p0) = COPY $sp
+; CHECK: [[CST2:%[0-9]+]]:_(s64) = G_CONSTANT i64 0
+; CHECK: [[GEP2:%[0-9]+]]:_(p0) = G_GEP [[SP]], [[CST2]](s64)
+; CHECK: G_STORE [[EXTLO]](s64), [[GEP2]](p0) :: (store 8 into stack, align 0)
+; CHECK: [[SP:%[0-9]+]]:_(p0) = COPY $sp
+; CHECK: [[CST3:%[0-9]+]]:_(s64) = COPY [[CST]]
+; CHECK: [[GEP3:%[0-9]+]]:_(p0) = G_GEP [[SP]], [[CST3]](s64)
+; CHECK: G_STORE [[EXTHI]](s64), [[GEP3]](p0) :: (store 8 into stack + 8, align 0)
+define void @test_split_struct([2 x i64]* %ptr) {
+  %struct = load [2 x i64], [2 x i64]* %ptr
+  call void @take_split_struct([2 x i64]* null, i64 1, i64 2, i64 3,
+                               i64 4, i64 5, i64 6,
+                               [2 x i64] %struct)
+  ret void
+}
+
+declare void @take_split_struct([2 x i64]* %ptr, i64, i64, i64,
+                               i64, i64, i64,
+                               [2 x i64] %in) ;

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

 ; RUN: llc -mtriple=aarch64-- -fast-isel=0 -global-isel=false \
 ; RUN:   -debug-pass=Structure %s -o /dev/null 2>&1 -verify-machineinstrs=0 \
 ; RUN:   | FileCheck %s --check-prefix DISABLED
 
 ; ENABLED:       IRTranslator
 ; VERIFY-NEXT:   Verify generated machine code
 ; ENABLED-NEXT:  PreLegalizerCombiner
 ; VERIFY-NEXT:   Verify generated machine code
+; ENABLED-NEXT:  Analysis containing CSE Info
 ; ENABLED-NEXT:  Legalizer
 ; VERIFY-NEXT:   Verify generated machine code
 ; ENABLED-NEXT:  RegBankSelect
 ; VERIFY-NEXT:   Verify generated machine code
 ; ENABLED-O0-NEXT:  Localizer
 ; VERIFY-O0-NEXT:   Verify generated machine code
 ; ENABLED-NEXT:  InstructionSelect
 ; VERIFY-NEXT:   Verify generated machine code

test/CodeGen/AArch64/GlobalISel/legalize-ext-cse.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -march=aarch64 -run-pass=legalizer %s -o - -enable-cse-in-legalizer=1 -O1 | FileCheck %s
+---
+name:            test_cse_in_legalizer
+body:             |
+  bb.0.entry:
+    ; CHECK-LABEL: name: test_cse_in_legalizer
+    ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
+    ; 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: [[COPY1:%[0-9]+]]:_(s32) = COPY [[AND]](s32)
+    ; CHECK: $w0 = COPY [[COPY1]](s32)
+    ; CHECK: $w0 = COPY [[AND]](s32)
+    %0:_(s64) = COPY $x0
+    %1:_(s8) = G_TRUNC %0(s64)
+    %19:_(s32) = G_ZEXT %1(s8)
+    $w0 = COPY %19(s32)
+    %2:_(s8) = G_TRUNC %0(s64)
+    %20:_(s32) = G_ZEXT %2(s8)
+    $w0 = COPY %20(s32)

test/CodeGen/AArch64/O0-pipeline.ll

 ; CHECK-NEXT:       Expand reduction intrinsics
 ; CHECK-NEXT:     Rewrite Symbols
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Exception handling preparation
 ; CHECK-NEXT:       Safe Stack instrumentation pass
 ; CHECK-NEXT:       Insert stack protectors
 ; CHECK-NEXT:       Module Verifier
+; CHECK-NEXT:       Analysis containing CSE Info
 ; CHECK-NEXT:       IRTranslator
 ; CHECK-NEXT:       AArch64PreLegalizerCombiner
+; CHECK-NEXT:       Analysis containing CSE Info
 ; CHECK-NEXT:       Legalizer
 ; CHECK-NEXT:       RegBankSelect
 ; CHECK-NEXT:       Localizer
 ; CHECK-NEXT:       InstructionSelect
 ; CHECK-NEXT:       ResetMachineFunction
 ; CHECK-NEXT:       AArch64 Instruction Selection
 ; CHECK-NEXT:       Expand ISel Pseudo-instructions
 ; CHECK-NEXT:       Local Stack Slot Allocation

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});
+  GISelCSEInfo CSEInfo;
+  CSEInfo.setCSEConfig(make_unique<CSEConfig>());
+  CSEInfo.analyze(*MF);
+  B.setCSEInfo(&CSEInfo);
+  CSEMIRBuilder CSEB(B.getState());
+  CSEB.setInsertPt(*EntryMBB, EntryMBB->begin());
+  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);
+  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);
+
+  // Try building G_CONSTANTS.
+  auto MIBCst = CSEB.buildConstant(s32, 0);
+  auto MIBCst1 = CSEB.buildConstant(s32, 0);
+  ASSERT_TRUE(&*MIBCst == &*MIBCst1);
+  // Try the CFing of BinaryOps.
+  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({s32, s32}, Copies[0]);
+  auto MIBUnmerge2 = CSEB.buildUnmerge({s32, s32}, Copies[0]);
+  ASSERT_TRUE(&*MIBUnmerge == &*MIBUnmerge2);
+}
+
+TEST_F(GISelMITest, TestCSEConstantConfig) {
+  if (!TM)
+    return;
+
+  LLT s16{LLT::scalar(16)};
+  auto MIBInput = B.buildInstr(TargetOpcode::G_TRUNC, {s16}, {Copies[0]});
+  auto MIBAdd = B.buildInstr(TargetOpcode::G_ADD, {s16}, {MIBInput, MIBInput});
+  auto MIBZero = B.buildConstant(s16, 0);
+  GISelCSEInfo CSEInfo;
+  CSEInfo.setCSEConfig(make_unique<CSEConfigConstantOnly>());
+  CSEInfo.analyze(*MF);
+  B.setCSEInfo(&CSEInfo);
+  CSEMIRBuilder CSEB(B.getState());
+  CSEB.setInsertPt(*EntryMBB, EntryMBB->begin());
+  auto MIBAdd1 =
+      CSEB.buildInstr(TargetOpcode::G_ADD, {s16}, {MIBInput, MIBInput});
+  // We should CSE constants only. Adds should not be CSEd.
+  ASSERT_TRUE(MIBAdd1->getOpcode() != TargetOpcode::COPY);
+  ASSERT_TRUE(&*MIBAdd1 != &*MIBAdd);
+  // We should CSE constant.
+  auto MIBZeroTmp = CSEB.buildConstant(s16, 0);
+  ASSERT_TRUE(&*MIBZero == &*MIBZeroTmp);
+}
+} // namespace

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/GISelChangeObserver.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/Support/TargetSelect.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetOptions.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 using namespace MIPatternMatch;
 
-void initLLVM() {
+static inline void initLLVM() {
   InitializeAllTargets();
   InitializeAllTargetMCs();
   InitializeAllAsmPrinters();
   InitializeAllAsmParsers();
 
   PassRegistry *Registry = PassRegistry::getPassRegistry();
   initializeCore(*Registry);
   initializeCodeGen(*Registry);
 }
 
 /// Create a TargetMachine. As we lack a dedicated always available target for
 /// unittests, we go for "AArch64".
-std::unique_ptr<LLVMTargetMachine> createTargetMachine() {
+static std::unique_ptr<LLVMTargetMachine> createTargetMachine() {
   Triple TargetTriple("aarch64--");
   std::string Error;
   const Target *T = TargetRegistry::lookupTarget("", TargetTriple, Error);
   if (!T)
     return nullptr;
 
   TargetOptions Options;
-  return std::unique_ptr<LLVMTargetMachine>(static_cast<LLVMTargetMachine*>(
-      T->createTargetMachine("AArch64", "", "", Options, None, None,
-                             CodeGenOpt::Aggressive)));
+  return std::unique_ptr<LLVMTargetMachine>(
+      static_cast<LLVMTargetMachine *>(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) {
+                                        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 LLVMTargetMachine &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() {
     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);
Name##Info(const TargetSubtargetInfo &ST) {                                \
       (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 {
 
 class DummyGISelObserver : public GISelChangeObserver {
 public:
-  void changingInstr(const MachineInstr &MI) override {}
-  void changedInstr(const MachineInstr &MI) override {}
-  void createdInstr(const MachineInstr &MI) override {}
-  void erasingInstr(const MachineInstr &MI) override {}
+  void changingInstr(MachineInstr &MI) override {}
+  void changedInstr(MachineInstr &MI) override {}
+  void createdInstr(MachineInstr &MI) override {}
+  void erasingInstr(MachineInstr &MI) override {}
 };
 
 // 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]});
   AInfo Info(MF->getSubtarget());
   DummyGISelObserver Observer;
-  LegalizerHelper Helper(*MF, Info, Observer);
+  LegalizerHelper Helper(*MF, Info, Observer, B);
   // Perform Legalization
   ASSERT_TRUE(Helper.lower(*MIBCTTZ, 0, LLT::scalar(64)) ==
               LegalizerHelper::LegalizeResult::Legalized);
 
   auto CheckStr = R"(
   CHECK: [[CZU:%[0-9]+]]:_(s64) = G_CTTZ_ZERO_UNDEF %0
   CHECK: [[ZERO:%[0-9]+]]:_(s64) = G_CONSTANT i64 0
   CHECK: [[SIXTY4:%[0-9]+]]:_(s64) = G_CONSTANT i64 64
   CHECK: [[CMP:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), %0:_(s64), [[ZERO]]
   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]});
   AInfo Info(MF->getSubtarget());
   DummyGISelObserver Observer;
-  LegalizerHelper Helper(*MF, Info, Observer);
+  LegalizerHelper Helper(*MF, Info, Observer, B);
   // Perform Legalization
   ASSERT_TRUE(Helper.lower(*MIBCTTZ, 0, LLT::scalar(64)) ==
               LegalizerHelper::LegalizeResult::Legalized);
 
   auto CheckStr = R"(
   CHECK: [[NEG1:%[0-9]+]]:_(s64) = G_CONSTANT i64 -1
   CHECK: [[NOT:%[0-9]+]]:_(s64) = G_XOR %0:_, [[NEG1]]
   CHECK: [[SUB1:%[0-9]+]]:_(s64) = G_ADD %0:_, [[NEG1]]
   CHECK: [[AND1:%[0-9]+]]:_(s64) = G_AND [[NOT]]:_, [[SUB1]]:_
   CHECK: [[CST64:%[0-9]+]]:_(s64) = G_CONSTANT i64 64
   CHECK: [[CTLZ:%[0-9]+]]:_(s64) = G_CTLZ [[AND1]]:_
   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]});
   AInfo Info(MF->getSubtarget());
   DummyGISelObserver Observer;
-  LegalizerHelper Helper(*MF, Info, Observer);
+  LegalizerHelper Helper(*MF, Info, Observer, B);
   ASSERT_TRUE(Helper.lower(*MIBCTTZ, 0, LLT::scalar(64)) ==
               LegalizerHelper::LegalizeResult::Legalized);
 
   auto CheckStr = R"(
   CHECK: [[NEG1:%[0-9]+]]:_(s64) = G_CONSTANT i64 -1
   CHECK: [[NOT:%[0-9]+]]:_(s64) = G_XOR %0:_, [[NEG1]]
   CHECK: [[SUB1:%[0-9]+]]:_(s64) = G_ADD %0:_, [[NEG1]]
   CHECK: [[AND1:%[0-9]+]]:_(s64) = G_AND [[NOT]]:_, [[SUB1]]:_
   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());
   DummyGISelObserver Observer;
-  LegalizerHelper Helper(*MF, Info, Observer);
+  LegalizerHelper Helper(*MF, Info, Observer, B);
   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]});
   AInfo Info(MF->getSubtarget());
   DummyGISelObserver Observer;
-  LegalizerHelper Helper(*MF, Info, Observer);
+  LegalizerHelper Helper(*MF, Info, Observer, B);
   ASSERT_TRUE(Helper.lower(*MIBCTLZ, 0, LLT::scalar(64)) ==
               LegalizerHelper::LegalizeResult::Legalized);
 
   auto CheckStr = R"(
   CHECK: [[CZU:%[0-9]+]]:_(s64) = G_CTLZ_ZERO_UNDEF %0
   CHECK: [[ZERO:%[0-9]+]]:_(s64) = G_CONSTANT i64 0
   CHECK: [[SIXTY4:%[0-9]+]]:_(s64) = G_CONSTANT i64 64
   CHECK: [[CMP:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), %0:_(s64), [[ZERO]]
   CHECK: [[SEL:%[0-9]+]]:_(s64) = G_SELECT [[CMP]]:_(s1), [[SIXTY4]]:_, [[CZU]]
   )";
 
   // Check
   ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr));
 }
 
 // CTLZ expansion in terms of CTLZ_ZERO_UNDEF if the latter is a libcall
-TEST_F(LegalizerHelperTest, LowerBitCountingCTLZLibcall) {
+TEST_F(GISelMITest, LowerBitCountingCTLZLibcall) {
   if (!TM)
     return;
 
   // Declare your legalization info
   DefineLegalizerInfo(
       A, { getActionDefinitionsBuilder(G_CTLZ_ZERO_UNDEF).libcallFor({s64}); });
   // Build
   auto MIBCTLZ =
       B.buildInstr(TargetOpcode::G_CTLZ, {LLT::scalar(64)}, {Copies[0]});
   AInfo Info(MF->getSubtarget());
   DummyGISelObserver Observer;
-  LegalizerHelper Helper(*MF, Info, Observer);
+  LegalizerHelper Helper(*MF, Info, Observer, B);
   ASSERT_TRUE(Helper.lower(*MIBCTLZ, 0, LLT::scalar(64)) ==
               LegalizerHelper::LegalizeResult::Legalized);
 
   auto CheckStr = R"(
   CHECK: [[CZU:%[0-9]+]]:_(s64) = G_CTLZ_ZERO_UNDEF %0
   CHECK: [[ZERO:%[0-9]+]]:_(s64) = G_CONSTANT i64 0
   CHECK: [[THIRTY2:%[0-9]+]]:_(s64) = G_CONSTANT i64 64
   CHECK: [[CMP:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), %0:_(s64), [[ZERO]]
   CHECK: [[SEL:%[0-9]+]]:_(s64) = G_SELECT [[CMP]]:_(s1), [[THIRTY2]]:_, [[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.
   LLT s8{LLT::scalar(8)};
   auto MIBTrunc = B.buildTrunc(s8, Copies[0]);
   auto MIBCTLZ = B.buildInstr(TargetOpcode::G_CTLZ, {s8}, {MIBTrunc});
   AInfo Info(MF->getSubtarget());
   DummyGISelObserver Observer;
-  LegalizerHelper Helper(*MF, Info, Observer);
+  LegalizerHelper Helper(*MF, Info, Observer, B);
   ASSERT_TRUE(Helper.lower(*MIBCTLZ, 0, s8) ==
               LegalizerHelper::LegalizeResult::Legalized);
 
   auto CheckStr = R"(
   CHECK: [[Trunc:%[0-9]+]]:_(s8) = G_TRUNC
   CHECK: [[Cst1:%[0-9]+]]:_(s8) = G_CONSTANT i8 1
   CHECK: [[Sh1:%[0-9]+]]:_(s8) = G_LSHR [[Trunc]]:_, [[Cst1]]:_
   CHECK: [[Or1:%[0-9]+]]:_(s8) = G_OR [[Trunc]]:_, [[Sh1]]:_
   CHECK: [[Cst2:%[0-9]+]]:_(s8) = G_CONSTANT i8 2
   CHECK: [[Sh2:%[0-9]+]]:_(s8) = G_LSHR [[Or1]]:_, [[Cst2]]:_
   CHECK: [[Or2:%[0-9]+]]:_(s8) = G_OR [[Or1]]:_, [[Sh2]]:_
   CHECK: [[Cst4:%[0-9]+]]:_(s8) = G_CONSTANT i8 4
   CHECK: [[Sh4:%[0-9]+]]:_(s8) = G_LSHR [[Or2]]:_, [[Cst4]]:_
   CHECK: [[Or4:%[0-9]+]]:_(s8) = G_OR [[Or2]]:_, [[Sh4]]:_
   CHECK: [[CTPOP:%[0-9]+]]:_(s8) = G_CTPOP [[Or4]]:_
   CHECK: [[Len:%[0-9]+]]:_(s8) = G_CONSTANT i8 8
   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.
   LLT s8{LLT::scalar(8)};
   LLT s16{LLT::scalar(16)};
   auto MIBTrunc = B.buildTrunc(s8, Copies[0]);
   auto MIBCTLZ = B.buildInstr(TargetOpcode::G_CTLZ, {s8}, {MIBTrunc});
   AInfo Info(MF->getSubtarget());
   DummyGISelObserver Observer;
-  LegalizerHelper Helper(*MF, Info, Observer);
+  LegalizerHelper Helper(*MF, Info, Observer, B);
   ASSERT_TRUE(Helper.widenScalar(*MIBCTLZ, 0, s16) ==
               LegalizerHelper::LegalizeResult::Legalized);
 
   auto CheckStr = R"(
   CHECK: [[Trunc:%[0-9]+]]:_(s8) = G_TRUNC
   CHECK: [[Zext:%[0-9]+]]:_(s16) = G_ZEXT [[Trunc]]
   CHECK: [[Ctlz:%[0-9]+]]:_(s16) = G_CTLZ [[Zext]]
   CHECK: [[Cst8:%[0-9]+]]:_(s16) = G_CONSTANT i16 8
   CHECK: [[Sub:%[0-9]+]]:_(s16) = G_SUB [[Ctlz]]:_, [[Cst8]]:_
   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.
   LLT s8{LLT::scalar(8)};
   LLT s16{LLT::scalar(16)};
   auto MIBTrunc = B.buildTrunc(s8, Copies[0]);
   auto MIBCTLZ_ZU =
       B.buildInstr(TargetOpcode::G_CTLZ_ZERO_UNDEF, {s8}, {MIBTrunc});
   AInfo Info(MF->getSubtarget());
   DummyGISelObserver Observer;
-  LegalizerHelper Helper(*MF, Info, Observer);
+  LegalizerHelper Helper(*MF, Info, Observer, B);
   ASSERT_TRUE(Helper.widenScalar(*MIBCTLZ_ZU, 0, s16) ==
               LegalizerHelper::LegalizeResult::Legalized);
 
   auto CheckStr = R"(
   CHECK: [[Trunc:%[0-9]+]]:_(s8) = G_TRUNC
   CHECK: [[Zext:%[0-9]+]]:_(s16) = G_ZEXT [[Trunc]]
   CHECK: [[CtlzZu:%[0-9]+]]:_(s16) = G_CTLZ_ZERO_UNDEF [[Zext]]
   CHECK: [[Cst8:%[0-9]+]]:_(s16) = G_CONSTANT i16 8
   CHECK: [[Sub:%[0-9]+]]:_(s16) = G_SUB [[CtlzZu]]:_, [[Cst8]]:_
   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.
   LLT s8{LLT::scalar(8)};
   LLT s16{LLT::scalar(16)};
   auto MIBTrunc = B.buildTrunc(s8, Copies[0]);
   auto MIBCTPOP = B.buildInstr(TargetOpcode::G_CTPOP, {s8}, {MIBTrunc});
   AInfo Info(MF->getSubtarget());
   DummyGISelObserver Observer;
-  LegalizerHelper Helper(*MF, Info, Observer);
+  LegalizerHelper Helper(*MF, Info, Observer, B);
   ASSERT_TRUE(Helper.widenScalar(*MIBCTPOP, 0, s16) ==
               LegalizerHelper::LegalizeResult::Legalized);
 
   auto CheckStr = R"(
   CHECK: [[Trunc:%[0-9]+]]:_(s8) = G_TRUNC
   CHECK: [[Zext:%[0-9]+]]:_(s16) = G_ZEXT [[Trunc]]
   CHECK: [[Ctpop:%[0-9]+]]:_(s16) = G_CTPOP [[Zext]]
   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.
   LLT s8{LLT::scalar(8)};
   LLT s16{LLT::scalar(16)};
   auto MIBTrunc = B.buildTrunc(s8, Copies[0]);
   auto MIBCTTZ_ZERO_UNDEF =
       B.buildInstr(TargetOpcode::G_CTTZ_ZERO_UNDEF, {s8}, {MIBTrunc});
   AInfo Info(MF->getSubtarget());
   DummyGISelObserver Observer;
-  LegalizerHelper Helper(*MF, Info, Observer);
+  LegalizerHelper Helper(*MF, Info, Observer, B);
   ASSERT_TRUE(Helper.widenScalar(*MIBCTTZ_ZERO_UNDEF, 0, s16) ==
               LegalizerHelper::LegalizeResult::Legalized);
 
   auto CheckStr = R"(
   CHECK: [[Trunc:%[0-9]+]]:_(s8) = G_TRUNC
   CHECK: [[Zext:%[0-9]+]]:_(s16) = G_ZEXT [[Trunc]]
   CHECK: [[CttzZu:%[0-9]+]]:_(s16) = G_CTTZ_ZERO_UNDEF [[Zext]]
   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.
   LLT s8{LLT::scalar(8)};
   LLT s16{LLT::scalar(16)};
   auto MIBTrunc = B.buildTrunc(s8, Copies[0]);
   auto MIBCTTZ = B.buildInstr(TargetOpcode::G_CTTZ, {s8}, {MIBTrunc});
   AInfo Info(MF->getSubtarget());
   DummyGISelObserver Observer;
-  LegalizerHelper Helper(*MF, Info, Observer);
+  LegalizerHelper Helper(*MF, Info, Observer, B);
   ASSERT_TRUE(Helper.widenScalar(*MIBCTTZ, 0, s16) ==
               LegalizerHelper::LegalizeResult::Legalized);
 
   auto CheckStr = R"(
   CHECK: [[Trunc:%[0-9]+]]:_(s8) = G_TRUNC
   CHECK: [[Zext:%[0-9]+]]:_(s16) = G_ZEXT [[Trunc]]
   CHECK: [[Cst:%[0-9]+]]:_(s16) = G_CONSTANT i16 256
   CHECK: [[Or:%[0-9]+]]:_(s16) = G_OR [[Zext]]:_, [[Cst]]
   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.
   LLT s8{LLT::scalar(8)};
   LLT s16{LLT::scalar(16)};
   auto MIBTrunc = B.buildTrunc(s8, Copies[0]);
   unsigned CarryReg = MRI->createGenericVirtualRegister(LLT::scalar(1));
   auto MIBUAddO =
       B.buildInstr(TargetOpcode::G_UADDO, {s8, CarryReg}, {MIBTrunc, MIBTrunc});
   AInfo Info(MF->getSubtarget());
   DummyGISelObserver Observer;
-  LegalizerHelper Helper(*MF, Info, Observer);
+  LegalizerHelper Helper(*MF, Info, Observer, B);
   ASSERT_TRUE(Helper.widenScalar(*MIBUAddO, 0, s16) ==
               LegalizerHelper::LegalizeResult::Legalized);
 
   auto CheckStr = R"(
   CHECK: [[Trunc:%[0-9]+]]:_(s8) = G_TRUNC
   CHECK: [[LHS:%[0-9]+]]:_(s16) = G_ZEXT [[Trunc]]
   CHECK: [[RHS:%[0-9]+]]:_(s16) = G_ZEXT [[Trunc]]
   CHECK: [[ADD:%[0-9]+]]:_(s16) = G_ADD [[LHS]]:_, [[RHS]]:_
   CHECK: [[CST:%[0-9]+]]:_(s16) = G_CONSTANT i16 255
   CHECK: [[AND:%[0-9]+]]:_(s16) = G_AND [[ADD]]:_, [[CST]]:_
   CHECK: G_ICMP intpred(ne), [[ADD]]:_(s16), [[AND]]:_
   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.
   LLT s8{LLT::scalar(8)};
   LLT s16{LLT::scalar(16)};
   auto MIBTrunc = B.buildTrunc(s8, Copies[0]);
   unsigned CarryReg = MRI->createGenericVirtualRegister(LLT::scalar(1));
   auto MIBUSUBO =
       B.buildInstr(TargetOpcode::G_USUBO, {s8, CarryReg}, {MIBTrunc, MIBTrunc});
   AInfo Info(MF->getSubtarget());
   DummyGISelObserver Observer;
-  LegalizerHelper Helper(*MF, Info, Observer);
+  LegalizerHelper Helper(*MF, Info, Observer, B);
   ASSERT_TRUE(Helper.widenScalar(*MIBUSUBO, 0, s16) ==
               LegalizerHelper::LegalizeResult::Legalized);
 
   auto CheckStr = R"(
   CHECK: [[Trunc:%[0-9]+]]:_(s8) = G_TRUNC
   CHECK: [[LHS:%[0-9]+]]:_(s16) = G_ZEXT [[Trunc]]
   CHECK: [[RHS:%[0-9]+]]:_(s16) = G_ZEXT [[Trunc]]
   CHECK: [[SUB:%[0-9]+]]:_(s16) = G_SUB [[LHS]]:_, [[RHS]]:_