New utility class ReachingPhysDefs for post-ra analysis.

[jonpa]

Summary

AArch64CollectLOH.cpp contained an algorithm for analysing reaching definitions of physregs globally. To make this available to other targets, it has been factored out as an independent CodeGen class. This was originally suggested by Quentin Colombet.

The algorithm finds defs and users per register (color). It is possible to add any number of regs to be analyzed. The inverse map from user to defs per register is also built. The analyzis of operands is heavily overloadable to suit particular contexts, e.g. treating defs of a particular reg as a use etc.

SystemZElimCompare.cpp was the initial reason for trying this. It however turned out that using this gave only very marginal results. (70 more eliminated compares and 15 more fused compare/branch, where the total for these stats are ~200000). There were about 600 cases with multiple defs (pruned) that might theoretically be handled, but that seems unlikely to be worth the effort.

Since it is marginally better, it would still perhaps be preferred to use this new class, provided that other targets do the same, since that would reduce custom code also in the SystemZ backend (even thought it isn't much).

• The API is just beginning to take form, and is at this point just enough to use it in the SystemZ and AArch64 files. It is hopefully possible to add new data structures / query methods to suit any type of situation.
• The AARch64CollectLOH.cpp file has been rewritten to use this new class instead. That part of the patch is imperfect and should preferably be looked over by a backend maintainer, plus verfied for NFC.

[qcolombet]

Hi Jonas,

I will check this is NFC for AArch64 purposes, but that looks good generally speaking.
At his point, I only have comments on the comments :).

I'll try to get back to you by the end of the week.

Cheers,
-Quentin

include/llvm/CodeGen/ReachingPhysDefs.h

39

I think the common practice when defining typedefs is to put them in the main class of the header file.
Indeed, we do not want to have symbols collision and a class provides a sort of namespace.

82

I am not sure "recorded" is the right word.
IIRC DummyOp is used to simulate that a definition is live-out a block when we actually do not do the full analysis.
In other word, DummyOp is a sentinel that ensures the reaching def analysis is conservatively correct when BasicBlockScopeOnly is used.

87

Now that I look back at this comment, although I know what I meant, it is really hard to understand.
What about:
A set of definitions, one per color, that reaches the out boundary of this block.
A given color may have more that one definition reaching a basic block boundary because of live-in/live-through definitions.

97

While we are here, we can fix the comments ;).
s/couple/pair/

113

typo: a a

113

You may use the doxygen grouping comment: \@ { ... \@}

116

/ -> \p ?

116

Since this can be overloaded, I would be more verbose about what this processing is supposed to do.

118

What is returned if case of no use?
I am guessing 0, but it needs to be documented.

119

Typo: clobbsers -> clobbers

119

Same comment as processMIUses: document what is the expected processing here.

126

Could you document why this is useful?
My vague recollection seems to indicate that this is useful for the related instructions to appear in the final reachable use/def.

130

Does this have to do with DummyOp?
I think it was about adding DummyOp to the final reachable use/def maps, doesn't it?

183

analysis.

185

Be more explicit about "it is added".
I am guessing it means "it is added to the set of registers handled by the algorithm".

lib/CodeGen/ReachingPhysDefs.cpp

35

Either move the doxygen comment to the header or make this a plain comment.
I don't think doxygen likes to have multiple comments for the same method, plus it is a pain when we need to update them.

This remark stands for all methods in the file :).

49

recorded.

93

The formatting looks weird to me.
clang-format?

lib/Target/AArch64/AArch64CollectLOH.cpp

127

I am fine in keeping the aarch64-collect-loh, though I see why you are doing it.
That will be indeed cumbersome to debug this pass without the reachingdefs output.
That behind said, it is probably a testimony to support more than one debug-only switch.

527

This const could remain, right?

[qcolombet]

Hi Jonas,

This is NFC for AArch64.

I have a few warnings in the build of the compiler that would need to be fixed:

• ReachingPhysDefs.h:167:3: warning: 'llvm::ReachingPhysDefs' has virtual functions but non-virtual destructor [-Wnon-virtual-dtor]
• AArch64CollectLOH.cpp:210:7: warning: 'ReachingPhysDefs_ADRP' has virtual functions but non-virtual destructor [-Wnon-virtual-dtor]
• AArch64CollectLOH.cpp:225:7: warning: 'ReachingPhysDefs_Others' has virtual functions but non-virtual destructor [-Wnon-virtual-dtor]
• AArch64CollectLOH.cpp:378:30: warning: unused variable 'EndIt' [-Wunused-variable]

Thanks,
-Quentin

[kparzysz]

The register data flow does that.

[kparzysz]

The RDF actually creates a data-flow graph for physical registers. It's currently under lib/Target/Hexagon/, but it was written as target-independent. Its only current limitation is lack of handling of regmasks, but that can be added fairly easily.

[• dberlin]

lib/CodeGen/ReachingPhysDefs.cpp

301

You should iterate this in the right order to converge faster.

Look at LiveDebugValues.cpp::ExtendRanges

You should be able to copy and reuse the relevant worklist code there.

[jonpa]

Krzsysztof, are you saying that we should abandon this patch and use RDF instead? What would be the motivation for this? If someone would put RDF into a separate class with regmasks handled, I would be happy to just drop LivePhysRegs. I think it would be very good to have a class for this, regardless of which one we pick.

I was not aware of RDF, mereley took the work that Quentin pointed out as available. Now I am not sure what to do...

/Jonas

[kparzysz]

Jonas: I don't have any objections about this patch or any recommendations that would be different from what you are doing. However, I just wanted to signal that a bulk of work towards post-RA data flow analysis had already been done, in case someone was planning to take on such a task. I would be more than happy to do the work to enable it for other targets as well, as a matter of fact, that was my long-term objective.

[qcolombet]

Hi Krzsysztof,

I was not aware of the RDF as well. Since Jonas did most of the work to make this implementation available to every target, how hard would it be to switch the users of RDF to this interface?

I am fine with the other direction as well, i.e., reuse RDF for other users, it just seems at this point that it is easier to continue moving towards using this interface. Moreover, I am guessing that this interface and RDF should be similarly complex and have the same functionalities so there is no questions of what is the right long term design.

Cheers,
-Quentin

[kparzysz]

Hi Quentin,
Currently, RDF is local to Hexagon and so only Hexagon passes use it. There is one pass upstream and we have one more that hasn't yet been upstreamed.

What RDF does is that it connects defs to other related defs and to reached uses. That provides ways to easily get reached uses for each def and reaching defs for each def and use. We also have a pass that recalculates block live-ins using that information.

You can take a look at lib/Target/Hexagon/RDFGraph.h, there are comments at the beginning of the file that describe what it is. The liveness is implemented in RDFLiveness.h/.cpp.

[kparzysz]

Here's a slightly out-of-date presentation on RDF (but mostly accurate).

-Krzysztof

• RegisterDataFlow-pub.pdf136 KBDownload

[jonpa]

Patch updated according to review.

Quentin: Regarding commenting - I think you would be best suited for the ADRP class. Otherwise comments have been updated hopefully as requested.

I removed the const on MachineInstrs in SetOfMachineInstr and InstrToInstrs. This was done when using this class in SystemZElimCompare where the users of CC are updated (non-const operations). I then thought it would be necessary to give users of the algorithm this freedom, and removed the const. Is there a better option?

I have reused the reverse post-order algo as suggested, but not tested it. First I wonder if there is any progress on deciding if ReachingPhysDefs or the RDF should go in?

include/llvm/CodeGen/ReachingPhysDefs.h

126

This is only used by the ADRP analysis, so I am guessing this is because that class reverses semantics so that ADRP defs are uses. I am not sure of the details...

lib/CodeGen/ReachingPhysDefs.cpp

301

Yes, interesting, thanks. I copied it and thought perhaps this could even be some algorithm class with a virtual method for handling of MBB?

lib/Target/AArch64/AArch64CollectLOH.cpp

127

I have also found other cases where it would be useful. For instance, in [Target]InstrInfo.cpp target implementations, some methods should get debug output along with the passes where they are called from.

527

No, in order to use this class when experimenting with SystemZElimCompare, in such a way as to change CC-users, I thought it made sense to remove the const specifier.

If it would remain, I guess users of the algorithm would have to do a const_cast when they wanted to change a user / def?

[qcolombet]

Hi Jonas,

Thanks for the update.

First I wonder if there is any progress on deciding if ReachingPhysDefs or the RDF should go in?

Given that ReachingPhysDefs is already working for other client thanks to your work, I would pursue with pushing it out.
Then, we can push RDF as a replacement when all that work is done.

Couple of comments.

Cheers,
-Quentin

lib/Target/AArch64/AArch64CollectLOH.cpp

127

Actually, I’ve found that this is already possible.
One has to separate the passes name with a comma.
E.g., -debug-only=isel,machine-licm

In other words, please do not change that debug type :).

527

What I was saying is even if the UseToDefs structure hold non-const refs (which is fine), this particular use could remain const without impacting other clients, right?

[jonpa]

AArch64CollectLOH.cpp DEBUG_TYPE changed back to "aarch64-collect-loh".

lib/Target/AArch64/AArch64CollectLOH.cpp

127

aah, that's good to know! :)

527

Sorry, I should have mentioned that if I do not remove the const for the 'Def' variable, I get compilation errors:

...
lib/Target/AArch64/AArch64CollectLOH.cpp:543:27: error: no matching function for call to ‘llvm::MapVector<llvm::MachineInstr*, llvm::SetOfMachineInstr>::find(const llvm::MachineInstr*&) const’

if (UseToDefs.find(Def) ==

...
note: no known conversion for argument 1 from ‘const llvm::MachineInstr*’ to ‘llvm::MachineInstr* const&’
// It's a bit weird that UseToDefs can't use a const MachineInstr* as a key...
...
AArch64CollectLOH.cpp:549:11: error: invalid conversion from ‘const llvm::MachineInstr*’ to ‘llvm::MachineInstr*’ [-fpermissive]

Instr = Def;

// Function would also have to be rewritten a bit, since Instr is non-const.

Not sure how to fix this, so I settled for removing the const on 'Def'...

[jonpa]

Quentin, the ./test/CodeGen/AArch64 suite passes (not sure how much this class gets excersised there), but that's all I know. Could you perhaps test for NFC with this patch for AArch64?

Daniel, does the patch look good in reachingDefAlgorithm() now?

[qcolombet]

Hi Jonas,

I concur, this patch is NFC for AArch64.

Cheers,
-Quentin

[jonpa]

Quentin,

I tried enabling the aggressive antidep breaker with SystemZ z13, and found that it fails the test-suite heavily. I suspected that live-in lists might be the cause for this, and tried this ReachingPhysRegs class. Most of the fails then disappeared, but not all.

Having discussed a bit with Matthias Braun, we thought perhaps adding a check of live-in lists in the MachineVerifier might be a good thing. I thought ReachingPhysRegs could be good to use there.

It seems however, that it is adding all aliases of all defined registers per instruction. Considering Live-in lists however, it seems that only Reg is part of it (not all the aliases).

How could one check for liveness of a specific reg disregarding its aliases?

Must the class add all aliases? An alternative might be to only add the specific Reg, and then in the context of the query address aliases as well. If this is slow, perhaps first calculating the live Regs, and then build a second set of maps that propagates everything into aliases.

What is your opinion?

[qcolombet]

Hi Jonas,

Having discussed a bit with Matthias Braun, we thought perhaps adding a check of live-in lists in the MachineVerifier might be a good thing.

100% agree. We had a few bugs recently that all boiled down to live-in lists being incorrect, so checking them is definitely a good idea.

Considering Live-in lists however, it seems that only Reg is part of it (not all the aliases).

I have been thinking about this for a related problem https://reviews.llvm.org/D23172, and the proper solution seems to me that we should track the RegUnit.

How could one check for liveness of a specific reg disregarding its aliases?
Must the class add all aliases?

For both those questions the problem is more about what do we do when we remove a live register from the list. Removing the aliases may be difficult (in the sense expensive).

Again, I believe the proper solution would be to switch everything to RegUnit.

Cheers,
-Quentin

[jonpa]

I still feel that it would be generally useful to have a general reaching phys-def analysis class in place, instead of targets having their own versions. Since I can't find one, I wonder if others agree still?

I remember that Krzysztof pointed out that there is also an alternative algorithm in the Hexagon backend (RDF), which he then said he may factor out. Krzysztof, any news on this?

I also remember a discussion about corrupt live-in lists, but I am not sure if those problems have been fixed... I think this patch (if not RDF will take its place), needs to be updated for any such changes of live-ins.

[MatzeB]

Krzysztofs rdf patch is here https://reviews.llvm.org/D29295 and it would good if it got some reviewers and users.

Regarding live in lists there was https://reviews.llvm.org/D33650, I should probably get back on this as we are modelling the ARM LR code better now.

[jonpa]

In D17257#863518, @MatzeB wrote:

Krzysztofs rdf patch is here https://reviews.llvm.org/D29295 and it would good if it got some reviewers and users.

Ok, for me the next step will then be to try that instead since it is already working.

include/llvm/CodeGen/ReachingPhysDefs.h

+//===- llvm/CodeGen/ReachingPhysDefs.h --- Reaching definitions -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Reaching definitions of physical registers.
+//
+// This algorithm originated in the AArch64CollectLOHs pass. It was
+// factored out so that targets could start to use a common class for
+// reaching definitions. More specifically, SystemZ::ElimCompare.cpp
+// was the initial reason for trying this. It is the hope and ambition
+// this will evolve into a full fledged post-ra def/use analalyzer
+// that suits the needs of all targets.
+
+#ifndef LLVM_CODEGEN_REACHINGDEFS_H
+#define LLVM_CODEGEN_REACHINGDEFS_H
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineDominators.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstr.h"
+using namespace llvm;
+
+namespace llvm {
+
+/// A set of MachineInstruction. Const is not used as it is allowed
+/// for users of ReachingPhysDefs to transform instructions in maps.
+struct SetOfMachineInstr : SetVector<MachineInstr *> {
+  void dump();
+};
+
+/// Map a basic block to a set of instructions per register.
+/// This is used to represent the exposed uses of a basic block
+/// per register.
+typedef MapVector<const MachineBasicBlock *,
+                  std::unique_ptr<SetOfMachineInstr[]>>
+  BlockToSetOfInstrsPerColor;
+
+/// Map a basic block to an instruction per register.
+/// This is used to represent the live-out definitions of a basic block
+/// per register.
+typedef MapVector<const MachineBasicBlock *,
+                  std::unique_ptr<MachineInstr *[]>>
+  BlockToInstrPerColor;
+
+/// Map an instruction to a set of instructions. Used to represent the
+/// mapping def to reachable uses or use to definitions.
+typedef  MapVector<MachineInstr *, SetOfMachineInstr> InstrToInstrs;
+
+/// Map a basic block to a BitVector.
+/// This is used to record the kill registers per basic block.
+typedef MapVector<const MachineBasicBlock *, BitVector> BlockToRegSet;
+
+/// Map a register to a dense id.
+typedef DenseMap<unsigned, unsigned> MapRegToId;
+
+/// Map a dense id to a register. Used for debug purposes.
+typedef SmallVector<unsigned, 32> MapIdToReg;
+
+class ReachingPhysDefs {
+protected:
+  MachineFunction *MF;
+  const TargetRegisterInfo *TRI;
+  const TargetInstrInfo *TII;
+
+  /// Name for this map, in debug outputs.
+  std::string Name;
+
+  /// If true, only a local analysis is done.
+  bool BasicBlockScopeOnly;
+
+  /// Dummy uses are recorded using this MI, during local analysis.
+  MachineInstr *DummyOp;
+
+  /// structures:
+  /// For each basic block.
+  /// Out: a set per color of definitions that reach the
+  ///      out boundary of this block.
+  /// In: Same as Out but for in boundary.
+  /// Gen: generated color in this block (one operation per color).
+  /// Kill: register set of killed color in this block.
+  /// ReachableUses: a set per color of uses (operation) reachable
+  ///                for "In" definitions.
+  BlockToSetOfInstrsPerColor Out, In, ReachableUses;
+  BlockToInstrPerColor Gen;
+  BlockToRegSet Kill;
+
+  /// Given a couple (MBB, reg) get the corresponding set of
+  /// instructions from the given "sets".
+  SetOfMachineInstr &getSet(BlockToSetOfInstrsPerColor &sets,
+                            const MachineBasicBlock &MBB, unsigned reg);
+
+  /// Given a couple (reg, MI) get the corresponding set of
+  /// instructions from the the given "sets".
+  SetOfMachineInstr &getUses(InstrToInstrs *sets, unsigned reg,
+                             MachineInstr &MI);
+
+  /// Same as getUses but does not modify the input map "sets".
+  /// \return NULL if the couple (reg, MI) is not in sets.
+  const SetOfMachineInstr *getUses(const InstrToInstrs *sets, unsigned reg,
+                                   MachineInstr &MI);
+
+  //// Virtual methods that make it possible to override common analysis
+  //// results in a a specialized transformation context.
+
+  /// Process the use operands of/MI.
+  virtual void processMIUses(MachineInstr &MI);
+  /// Given MO, return a used register if any.
+  virtual unsigned processMIUseMO(MachineOperand &MO);
+  /// Process MI clobbsers (regmask)
+  virtual void processMIClobbers(MachineInstr &MI);
+  /// Process the defs of MI.
+  virtual void processMIDefs(MachineInstr &MI);
+
+  /// Indicate if an MI that clobbers a reg should be inserted into
+  /// maps.
+  virtual bool rememberClobberingMI() { return false; }
+
+  /// Indicate if dummy uses should be added to DummyOp in case only
+  /// doing local analysis.
+  virtual bool recordDummyUses() { return true; }
+
+  /// Initialize the reaching definition algorithm.
+  void initReachingDef();
+
+  /// Reaching definition algorithm.
+  void reachingDef();
+
+  /// Reaching def core algorithm.
+  void reachingDefAlgorithm();
+
+  /// Build the inverse map from Use to Defs.
+  virtual void reachedUsesToDefs();
+
+  // Register numbers are not stored directly in maps but are mapped
+  // to id's that start from 0.
+
+  /// Current ID, to be assigned to next reg added.
+  unsigned CurRegId;
+  /// Map from reg to its id.
+  MapRegToId RegToId;
+  /// Map from id to reg.
+  MapIdToReg IdToReg;
+
+  ///// The resulting data structures
+
+  /// A two dimensional map from [reg][DefMI] -> {Uses}
+  InstrToInstrs *ColorOpToReachedUses;
+  /// A two dimensional map from [reg][UseMI] -> {Defs}
+  InstrToInstrs *ColorOpToReachingDefs;
+  /// A map from [UseMI] -> {All DefMIs of any used reg of UseMI}
+  InstrToInstrs UseToDefs;
+
+public:
+  ReachingPhysDefs(MachineFunction *MF_, const TargetRegisterInfo *TRI_,
+                   bool BasicBlockScopeOnly,
+                   const Twine &name = "Reaching defs");
+  ~ReachingPhysDefs();
+
+  /// Add reg to the set of registers to be handled by the algorithm.
+  void addReg(unsigned reg);
+
+  /// Add all target registers to be handled by the algorithm.
+  void addAllTargetRegs();
+
+  /// Return number of regs added to maps.
+  unsigned nbRegs() { return RegToId.size(); }
+
+  /// Return true if reg has already been added.
+  bool isRegInMaps(unsigned reg) {
+    return (RegToId.find(reg) != RegToId.end());
+  }
+
+  /// Do a reaching defs analyzis on a given set of phys regs. If a
+  /// single reg is given, it is added.
+  bool analyze(unsigned singleReg = 0);
+
+  /// Some transformations rather leave things alone if a use of a reg
+  /// have multiple defs. This method removes all defs with such a
+  /// user from the ColorOpToReachedUses map, for the register
+  /// involved.
+  void pruneMultipleDefs();
+
+#ifndef NDEBUG
+  /// print the result of the reaching definition algorithm.
+  void dump();
+#endif
+
+  /// Return the uses of MIs' definition of reg.
+  SetOfMachineInstr *getUses(unsigned reg, MachineInstr &MI);
+};
+
+} // end llvm namespace.
+
+#endif

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   Passes.cpp
   PeepholeOptimizer.cpp
   PHIElimination.cpp
   PHIEliminationUtils.cpp
   PostRASchedulerList.cpp
   ProcessImplicitDefs.cpp
   PrologEpilogInserter.cpp
   PseudoSourceValue.cpp
+  ReachingPhysDefs.cpp
   RegAllocBase.cpp
   RegAllocBasic.cpp
   RegAllocFast.cpp
   RegAllocGreedy.cpp
   RegAllocPBQP.cpp
   RegisterClassInfo.cpp
   RegisterCoalescer.cpp
   RegisterPressure.cpp

lib/CodeGen/ReachingPhysDefs.cpp

+//===- llvm/CodeGen/ReachingPhysDefs.h --- Reaching definitions -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/ReachingPhysDefs.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "reachingdefs"
+
+static void dumpMIWithBB(const MachineInstr *MI) {
+  dbgs() << "MBB#" << MI->getParent()->getNumber()
+         << ":"; MI->dump();
+}
+
+void SetOfMachineInstr::dump() {
+  for (auto *I : *this) {
+    dbgs() << "\t"; dumpMIWithBB(I);
+  }
+  dbgs() << "\n";
+}
+
+/// the given "sets".
+/// If this couple does not reference any set, an empty set is added to "sets"
+/// for this couple and returned.
+SetOfMachineInstr &ReachingPhysDefs::
+getSet(BlockToSetOfInstrsPerColor &sets, const MachineBasicBlock &MBB,
+       unsigned reg) {
+  SetOfMachineInstr *result;
+  BlockToSetOfInstrsPerColor::iterator it = sets.find(&MBB);
+  if (it != sets.end())
+    result = it->second.get();
+  else
+    result = (sets[&MBB] = make_unique<SetOfMachineInstr[]>(nbRegs())).get();
+
+  return result[reg];
+}
+
+/// Given a couple (reg, MI) get the corresponding set of instructions
+/// from the the given "sets".  This is used to get the uses record in
+/// sets of a definition identified by MI and reg, i.e., MI defines
+/// reg.  If the couple does not reference anything, an empty set is
+/// added to "sets[reg]".
+SetOfMachineInstr &ReachingPhysDefs::getUses(InstrToInstrs *sets, unsigned reg,
+                                             MachineInstr &MI) {
+  return sets[reg][&MI];
+}
+
+/// Same as getUses but does not modify the input map "sets".
+/// \return NULL if the couple (reg, MI) is not in sets.
+const SetOfMachineInstr *ReachingPhysDefs::
+getUses(const InstrToInstrs *sets, unsigned reg, MachineInstr &MI) {
+  InstrToInstrs::const_iterator Res = sets[reg].find(&MI);
+  if (Res != sets[reg].end())
+    return &(Res->second);
+  return nullptr;
+}
+
+SetOfMachineInstr *ReachingPhysDefs::
+getUses(unsigned reg, MachineInstr &MI) {
+  return &getUses(ColorOpToReachedUses, RegToId.find(reg)->second, MI);
+}
+
+ReachingPhysDefs::
+ReachingPhysDefs(MachineFunction *MF_, const TargetRegisterInfo *TRI_,
+                 bool BBScopeOnly, const Twine &name)
+  : MF(MF_), TRI(TRI_), TII(nullptr), Name(name.str()),
+    BasicBlockScopeOnly(BBScopeOnly), DummyOp(nullptr), CurRegId(0),
+    ColorOpToReachedUses(nullptr), ColorOpToReachingDefs(nullptr)
+{
+  TII = MF->getSubtarget().getInstrInfo();
+}
+
+ReachingPhysDefs::~ReachingPhysDefs() {
+  if (ColorOpToReachedUses != nullptr)
+    delete[] ColorOpToReachedUses;
+  if (ColorOpToReachingDefs != nullptr)
+    delete[] ColorOpToReachingDefs;
+  if (DummyOp != nullptr)
+    MF->DeleteMachineInstr(DummyOp);
+}
+
+void ReachingPhysDefs::
+pruneMultipleDefs() {
+  for (unsigned CurReg = 0; CurReg < nbRegs(); ++CurReg) {
+    bool change = true;
+    while (change) {
+      change = false;
+      for (const auto &DefsIt : ColorOpToReachedUses[CurReg]) {
+        SetOfMachineInstr toPrune;
+        for (MachineInstr *Use : DefsIt.second)
+          if (ColorOpToReachingDefs[CurReg][Use].size() > 1) {
+            DEBUG(dbgs() << "Found user with multiple defs ("
+                  << PrintReg(IdToReg[CurReg], TRI) << "):\n";
+                  dumpMIWithBB(Use);
+                  ColorOpToReachingDefs[CurReg][Use].dump(););
+              toPrune.insert(ColorOpToReachingDefs[CurReg][Use].begin(),
+                             ColorOpToReachingDefs[CurReg][Use].end());
+            break;
+          }
+
+        if (!toPrune.empty()) {
+          for (MachineInstr *Def : toPrune) {
+            DEBUG(dbgs() << "Pruning reaching def:\n"; Def->dump();
+                  ColorOpToReachedUses[CurReg][Def].dump());
+            ColorOpToReachedUses[CurReg].erase(Def);
+          }
+          change = true;
+          break;
+        }
+      }
+    }
+  }
+}
+
+bool ReachingPhysDefs::analyze(unsigned singleReg) {
+  if (singleReg)
+    addReg(singleReg);
+  
+  if (!nbRegs())
+    return false;
+
+  assert(ColorOpToReachedUses == nullptr && "Don't call analyze twice!");
+  ColorOpToReachedUses = new InstrToInstrs[nbRegs()];
+  ColorOpToReachingDefs = new InstrToInstrs[nbRegs()];
+  if (BasicBlockScopeOnly) {
+    // For local analysis, create a dummy operation to record uses
+    // that are not local.
+    DummyOp = MF->CreateMachineInstr(TII->get(TargetOpcode::COPY), DebugLoc());
+  }
+
+  // Compute the reaching defs.
+  reachingDef();
+
+  // Translate the definition to uses map into a use to definitions map.
+  reachedUsesToDefs();
+
+  return true;
+}
+
+/// Map registers with dense id in RegToId and vice-versa in
+/// IdToReg. IdToReg is populated only in DEBUG mode.
+void ReachingPhysDefs::addReg(unsigned reg) {
+  DEBUG(IdToReg.push_back(reg);
+        assert(IdToReg[CurRegId] == reg &&
+               "Reg index mismatches insertion index."));
+  RegToId[reg] = CurRegId++;
+}
+
+/// Map registers with dense id in RegToId and vice-versa in
+/// IdToReg. IdToReg is populated only in DEBUG mode.
+void ReachingPhysDefs::addAllTargetRegs() {
+  CurRegId = 0;
+  unsigned NbReg = TRI->getNumRegs();
+  for (; CurRegId < NbReg; ++CurRegId) {
+    RegToId[CurRegId] = CurRegId;
+    DEBUG(IdToReg.push_back(CurRegId););
+  }
+}
+
+/// Initialize the reaching definition algorithm:
+/// For each basic block BB in MF, record:
+/// - its kill set.
+/// - its reachable uses (uses that are exposed to BB's predecessors).
+/// - its generated definitions.
+void ReachingPhysDefs::initReachingDef() {
+  for (MachineBasicBlock &MBB : *MF) {
+    auto &BBGen = Gen[&MBB];
+    BBGen = make_unique<MachineInstr *[]>(nbRegs());
+    std::fill(BBGen.get(), BBGen.get() + nbRegs(), nullptr);
+
+    BitVector &BBKillSet = Kill[&MBB];
+    BBKillSet.resize(nbRegs());
+
+    for (MachineInstr &MI : MBB) {
+      // Process uses first.
+      processMIUses(MI);
+      processMIClobbers(MI);
+      processMIDefs(MI);
+    }
+
+    // If we restrict our analysis to basic block scope,
+    // conservatively add a dummy use for each generated value.
+    if (recordDummyUses() && DummyOp && !MBB.succ_empty())
+      for (unsigned CurReg = 0; CurReg < nbRegs(); ++CurReg)
+        if (BBGen[CurReg])
+          getUses(ColorOpToReachedUses, CurReg, *BBGen[CurReg]).insert(DummyOp);
+  }
+}
+
+unsigned ReachingPhysDefs::processMIUseMO(MachineOperand &MO) {
+    if (!MO.isReg() || !MO.isUse())
+      return 0;
+    return MO.getReg();
+}
+
+void ReachingPhysDefs::processMIUses(MachineInstr &MI) {
+  const MachineBasicBlock *MBB = MI.getParent();
+  auto &BBGen = Gen[MBB];
+  BitVector &BBKillSet = Kill[MBB];
+
+  for (MachineOperand &MO : MI.operands()) {
+    unsigned CurReg = processMIUseMO(MO);
+    if (!CurReg)
+      continue;
+    MapRegToId::const_iterator ItCurRegId = RegToId.find(CurReg);
+    if (ItCurRegId == RegToId.end())
+      continue;
+    CurReg = ItCurRegId->second;
+
+    // if CurReg has not been defined, this use is reachable.
+    if (!BBGen[CurReg] && !BBKillSet.test(CurReg))
+      getSet(ReachableUses, *MBB, CurReg).insert(&MI);
+    // current basic block definition for this color, if any, is in Gen.
+    if (BBGen[CurReg])
+      getUses(ColorOpToReachedUses, CurReg, *BBGen[CurReg]).insert(&MI);
+  }
+}
+
+// Process clobbers.
+void ReachingPhysDefs::processMIClobbers(MachineInstr &MI) {
+  const MachineBasicBlock *MBB = MI.getParent();
+  auto &BBGen = Gen[MBB];
+  BitVector &BBKillSet = Kill[MBB];
+
+  for (const MachineOperand &MO : MI.operands()) {
+    if (!MO.isRegMask())
+      continue;
+    // Clobbers kill the related colors.
+    const uint32_t *PreservedRegs = MO.getRegMask();
+
+    // Set generated regs.
+    for (const auto &Entry : RegToId) {
+      unsigned Reg = Entry.second;
+      // Use the global register ID when querying APIs external to this
+      // pass.
+      if (MachineOperand::clobbersPhysReg(PreservedRegs, Entry.first)) {
+        // Do not register clobbered definition - this definition
+        // is not used anyway (otherwise register allocation is
+        // wrong).
+        BBGen[Reg] = rememberClobberingMI() ? &MI : nullptr;
+        BBKillSet.set(Reg);
+      }
+    }
+  }
+}
+
+// Process register defs.
+void ReachingPhysDefs::processMIDefs(MachineInstr &MI) {
+  const MachineBasicBlock *MBB = MI.getParent();
+  auto &BBGen = Gen[MBB];
+  BitVector &BBKillSet = Kill[MBB];
+
+  for (const MachineOperand &MO : MI.operands()) {
+    if (!MO.isReg() || !MO.isDef())
+      continue;
+    unsigned CurReg = MO.getReg();
+    MapRegToId::const_iterator ItCurRegId = RegToId.find(CurReg);
+    if (ItCurRegId == RegToId.end())
+      continue;
+
+    for (MCRegAliasIterator AI(CurReg, TRI, true); AI.isValid(); ++AI) {
+      MapRegToId::const_iterator ItRegId = RegToId.find(*AI);
+      // If this alias has not been recorded, then it is not interesting
+      // for the current analysis. XXX True generally?
+      // We can end up in this situation because of tuple registers.
+      // E.g., Let say we are interested in S1. When we register
+      // S1, we will also register its aliases and in particular
+      // the tuple Q1_Q2.
+      // Now, when we encounter Q1_Q2, we will look through its aliases
+      // and will find that S2 is not registered.
+      if (ItRegId == RegToId.end())
+        continue;
+
+      BBKillSet.set(ItRegId->second);
+      BBGen[ItRegId->second] = &MI;
+    }
+    BBGen[ItCurRegId->second] = &MI;
+  }
+}
+
+/// Reaching def core algorithm:
+/// while an Out has changed
+///    for each bb
+///       for each color
+///           In[bb][color] = U Out[bb.predecessors][color]
+///           insert reachableUses[bb][color] in each in[bb][color]
+///                 op.reachedUses
+///
+///           Out[bb] = Gen[bb] U (In[bb] - Kill[bb])
+void ReachingPhysDefs::reachingDefAlgorithm() {
+  bool HasChanged;
+  do {
+    HasChanged = false;
+    for (const MachineBasicBlock &MBB : *MF) {
+      unsigned CurReg;
+      for (CurReg = 0; CurReg < nbRegs(); ++CurReg) {
+        SetOfMachineInstr &BBInSet = getSet(In, MBB, CurReg);
+        SetOfMachineInstr &BBReachableUses =
+            getSet(ReachableUses, MBB, CurReg);
+        SetOfMachineInstr &BBOutSet = getSet(Out, MBB, CurReg);
+        unsigned Size = BBOutSet.size();
+        //   In[bb][color] = U Out[bb.predecessors][color]
+        for (const MachineBasicBlock *PredMBB : MBB.predecessors()) {
+          SetOfMachineInstr &PredOutSet = getSet(Out, *PredMBB, CurReg);
+          BBInSet.insert(PredOutSet.begin(), PredOutSet.end());
+        }
+        //   insert reachableUses[bb][color] in each in[bb][color] op.reachedses
+        for (MachineInstr *MI : BBInSet) {
+          SetOfMachineInstr &OpReachedUses =
+              getUses(ColorOpToReachedUses, CurReg, *MI);
+          OpReachedUses.insert(BBReachableUses.begin(), BBReachableUses.end());
+        }
+        //           Out[bb] = Gen[bb] U (In[bb] - Kill[bb])
+        if (!Kill[&MBB].test(CurReg))
+          BBOutSet.insert(BBInSet.begin(), BBInSet.end());
+        if (Gen[&MBB][CurReg])
+          BBOutSet.insert(Gen[&MBB][CurReg]);
+        HasChanged |= BBOutSet.size() != Size;
+      }
+    }
+  } while (HasChanged);
+}
+
+
+/// Reaching definition algorithm.
+/// On completion, ColorOpToReachedUses will contain the result of the
+/// reaching def algorithm.
+void ReachingPhysDefs::reachingDef() {
+
+  // Initialize Gen, kill and reachableUses.
+  initReachingDef();
+
+  // Algo.
+  if (!DummyOp)
+    reachingDefAlgorithm();
+}
+
+/// Build the inverse maps from Use to Defs.
+void ReachingPhysDefs::reachedUsesToDefs() {
+  for (unsigned CurReg = 0; CurReg < nbRegs(); ++CurReg) {
+    for (const auto &DefsIt : ColorOpToReachedUses[CurReg]) {
+      MachineInstr *Def = DefsIt.first;
+      for (MachineInstr *Use : DefsIt.second) {
+        UseToDefs[Use].insert(Def);
+        ColorOpToReachingDefs[CurReg][Use].insert(Def);
+      }
+    }
+  }
+}
+
+#ifndef NDEBUG
+/// print the result of the reaching definition algorithm.
+void ReachingPhysDefs::dump() {
+  DEBUG(dbgs() << Name << ":\n");
+  unsigned CurReg;
+  for (CurReg = 0; CurReg < nbRegs(); ++CurReg) {
+    if (ColorOpToReachedUses[CurReg].empty())
+      continue;
+    DEBUG(dbgs() << "Reg " << PrintReg(IdToReg[CurReg], TRI) << " \n");
+    for (auto &DefsIt : ColorOpToReachedUses[CurReg]) {
+      DEBUG(dumpMIWithBB(DefsIt.first);
+            DefsIt.second.dump(););
+    }
+  }
+}
+#endif // NDEBUG
+

lib/Target/AArch64/AArch64CollectLOH.cpp

 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/ReachingPhysDefs.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 using namespace llvm;
 
-#define DEBUG_TYPE "aarch64-collect-loh"
+#define DEBUG_TYPE "reachingdefs"
 
 static cl::opt<bool>
 PreCollectRegister("aarch64-collect-loh-pre-collect-register", cl::Hidden,
                    cl::desc("Restrict analysis to registers invovled"
                             " in LOHs"),
                    cl::init(true));
 
 static cl::opt<bool>
void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesAll();
     MachineFunctionPass::getAnalysisUsage(AU);
     AU.addRequired<MachineDominatorTree>();
   }
 
 private:
 };
 
-/// A set of MachineInstruction.
-typedef SetVector<const MachineInstr *> SetOfMachineInstr;
-/// Map a basic block to a set of instructions per register.
-/// This is used to represent the exposed uses of a basic block
-/// per register.
-typedef MapVector<const MachineBasicBlock *,
-                  std::unique_ptr<SetOfMachineInstr[]>>
-BlockToSetOfInstrsPerColor;
-/// Map a basic block to an instruction per register.
-/// This is used to represent the live-out definitions of a basic block
-/// per register.
-typedef MapVector<const MachineBasicBlock *,
-                  std::unique_ptr<const MachineInstr *[]>>
-BlockToInstrPerColor;
-/// Map an instruction to a set of instructions. Used to represent the
-/// mapping def to reachable uses or use to definitions.
-typedef MapVector<const MachineInstr *, SetOfMachineInstr> InstrToInstrs;
-/// Map a basic block to a BitVector.
-/// This is used to record the kill registers per basic block.
-typedef MapVector<const MachineBasicBlock *, BitVector> BlockToRegSet;
-
-/// Map a register to a dense id.
-typedef DenseMap<unsigned, unsigned> MapRegToId;
-/// Map a dense id to a register. Used for debug purposes.
-typedef SmallVector<unsigned, 32> MapIdToReg;
+
 } // end anonymous namespace.
 
 char AArch64CollectLOH::ID = 0;
 
 INITIALIZE_PASS_BEGIN(AArch64CollectLOH, "aarch64-collect-loh",
                       AARCH64_COLLECT_LOH_NAME, false, false)
 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 INITIALIZE_PASS_END(AArch64CollectLOH, "aarch64-collect-loh",
                     AARCH64_COLLECT_LOH_NAME, false, false)
 
-/// Given a couple (MBB, reg) get the corresponding set of instruction from
-/// the given "sets".
-/// If this couple does not reference any set, an empty set is added to "sets"
-/// for this couple and returned.
-/// \param nbRegs is used internally allocate some memory. It must be consistent
-/// with the way sets is used.
-static SetOfMachineInstr &getSet(BlockToSetOfInstrsPerColor &sets,
-                                 const MachineBasicBlock &MBB, unsigned reg,
-                                 unsigned nbRegs) {
-  SetOfMachineInstr *result;
-  BlockToSetOfInstrsPerColor::iterator it = sets.find(&MBB);
-  if (it != sets.end())
-    result = it->second.get();
-  else
-    result = (sets[&MBB] = make_unique<SetOfMachineInstr[]>(nbRegs)).get();
-
-  return result[reg];
-}
-
-/// Given a couple (reg, MI) get the corresponding set of instructions from the
-/// the given "sets".
-/// This is used to get the uses record in sets of a definition identified by
-/// MI and reg, i.e., MI defines reg.
-/// If the couple does not reference anything, an empty set is added to
-/// "sets[reg]".
-/// \pre set[reg] is valid.
-static SetOfMachineInstr &getUses(InstrToInstrs *sets, unsigned reg,
-                                  const MachineInstr &MI) {
-  return sets[reg][&MI];
-}
-
-/// Same as getUses but does not modify the input map: sets.
-/// \return NULL if the couple (reg, MI) is not in sets.
-static const SetOfMachineInstr *getUses(const InstrToInstrs *sets, unsigned reg,
-                                        const MachineInstr &MI) {
-  InstrToInstrs::const_iterator Res = sets[reg].find(&MI);
-  if (Res != sets[reg].end())
-    return &(Res->second);
-  return nullptr;
-}
-
-/// Initialize the reaching definition algorithm:
-/// For each basic block BB in MF, record:
-/// - its kill set.
-/// - its reachable uses (uses that are exposed to BB's predecessors).
-/// - its the generated definitions.
-/// \param DummyOp if not NULL, specifies a Dummy Operation to be added to
-/// the list of uses of exposed defintions.
-/// \param ADRPMode specifies to only consider ADRP instructions for generated
-/// definition. It also consider definitions of ADRP instructions as uses and
-/// ignore other uses. The ADRPMode is used to collect the information for LHO
-/// that involve ADRP operation only.
-static void initReachingDef(const MachineFunction &MF,
-                            InstrToInstrs *ColorOpToReachedUses,
-                            BlockToInstrPerColor &Gen, BlockToRegSet &Kill,
-                            BlockToSetOfInstrsPerColor &ReachableUses,
-                            const MapRegToId &RegToId,
-                            const MachineInstr *DummyOp, bool ADRPMode) {
-  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
-  unsigned NbReg = RegToId.size();
-
-  for (const MachineBasicBlock &MBB : MF) {
-    auto &BBGen = Gen[&MBB];
-    BBGen = make_unique<const MachineInstr *[]>(NbReg);
-    std::fill(BBGen.get(), BBGen.get() + NbReg, nullptr);
-
-    BitVector &BBKillSet = Kill[&MBB];
-    BBKillSet.resize(NbReg);
-    for (const MachineInstr &MI : MBB) {
-      bool IsADRP = MI.getOpcode() == AArch64::ADRP;
-
-      // Process uses first.
-      if (IsADRP || !ADRPMode)
-        for (const MachineOperand &MO : MI.operands()) {
-          // Treat ADRP def as use, as the goal of the analysis is to find
-          // ADRP defs reached by other ADRP defs.
-          if (!MO.isReg() || (!ADRPMode && !MO.isUse()) ||
-              (ADRPMode && (!IsADRP || !MO.isDef())))
-            continue;
-          unsigned CurReg = MO.getReg();
-          MapRegToId::const_iterator ItCurRegId = RegToId.find(CurReg);
-          if (ItCurRegId == RegToId.end())
-            continue;
-          CurReg = ItCurRegId->second;
-
-          // if CurReg has not been defined, this use is reachable.
-          if (!BBGen[CurReg] && !BBKillSet.test(CurReg))
-            getSet(ReachableUses, MBB, CurReg, NbReg).insert(&MI);
-          // current basic block definition for this color, if any, is in Gen.
-          if (BBGen[CurReg])
-            getUses(ColorOpToReachedUses, CurReg, *BBGen[CurReg]).insert(&MI);
-        }
-
-      // Process clobbers.
-      for (const MachineOperand &MO : MI.operands()) {
-        if (!MO.isRegMask())
-          continue;
-        // Clobbers kill the related colors.
-        const uint32_t *PreservedRegs = MO.getRegMask();
-
-        // Set generated regs.
-        for (const auto &Entry : RegToId) {
-          unsigned Reg = Entry.second;
-          // Use the global register ID when querying APIs external to this
-          // pass.
-          if (MachineOperand::clobbersPhysReg(PreservedRegs, Entry.first)) {
-            // Do not register clobbered definition for no ADRP.
-            // This definition is not used anyway (otherwise register
-            // allocation is wrong).
-            BBGen[Reg] = ADRPMode ? &MI : nullptr;
-            BBKillSet.set(Reg);
-          }
-        }
-      }
-
-      // Process register defs.
-      for (const MachineOperand &MO : MI.operands()) {
-        if (!MO.isReg() || !MO.isDef())
-          continue;
-        unsigned CurReg = MO.getReg();
-        MapRegToId::const_iterator ItCurRegId = RegToId.find(CurReg);
-        if (ItCurRegId == RegToId.end())
-          continue;
-
-        for (MCRegAliasIterator AI(CurReg, TRI, true); AI.isValid(); ++AI) {
-          MapRegToId::const_iterator ItRegId = RegToId.find(*AI);
-          // If this alias has not been recorded, then it is not interesting
-          // for the current analysis.
-          // We can end up in this situation because of tuple registers.
-          // E.g., Let say we are interested in S1. When we register
-          // S1, we will also register its aliases and in particular
-          // the tuple Q1_Q2.
-          // Now, when we encounter Q1_Q2, we will look through its aliases
-          // and will find that S2 is not registered.
-          if (ItRegId == RegToId.end())
-            continue;
 
-          BBKillSet.set(ItRegId->second);
-          BBGen[ItRegId->second] = &MI;
-        }
-        BBGen[ItCurRegId->second] = &MI;
-      }
-    }
+// A class to compute the reaching def in ADRP mode, meaning ADRP
+// definitions are first considered as uses.
+class ReachingPhysDefs_ADRP : public ReachingPhysDefs {
+  unsigned processMIUseMO(MachineOperand &MO) override;
+  bool rememberClobberingMI() override { return true; }
+  void reachedUsesToDefs() override;
+  bool recordDummyUses() override { return false; }
+
+public:
+  ReachingPhysDefs_ADRP(MachineFunction *MF_, const TargetRegisterInfo *TRI_,
+                        bool BasicBlockScopeOnly)
+    : ReachingPhysDefs(MF_, TRI_, BasicBlockScopeOnly,
+                       "ADRP reaching defs") {}
+  void addRegs();
+  InstrToInstrs &getUseToDefs() { return UseToDefs; }
+};
 
-    // If we restrict our analysis to basic block scope, conservatively add a
-    // dummy
-    // use for each generated value.
-    if (!ADRPMode && DummyOp && !MBB.succ_empty())
-      for (unsigned CurReg = 0; CurReg < NbReg; ++CurReg)
-        if (BBGen[CurReg])
-          getUses(ColorOpToReachedUses, CurReg, *BBGen[CurReg]).insert(DummyOp);
-  }
-}
-
-/// Reaching def core algorithm:
-/// while an Out has changed
-///    for each bb
-///       for each color
-///           In[bb][color] = U Out[bb.predecessors][color]
-///           insert reachableUses[bb][color] in each in[bb][color]
-///                 op.reachedUses
-///
-///           Out[bb] = Gen[bb] U (In[bb] - Kill[bb])
-static void reachingDefAlgorithm(const MachineFunction &MF,
-                                 InstrToInstrs *ColorOpToReachedUses,
-                                 BlockToSetOfInstrsPerColor &In,
-                                 BlockToSetOfInstrsPerColor &Out,
-                                 BlockToInstrPerColor &Gen, BlockToRegSet &Kill,
-                                 BlockToSetOfInstrsPerColor &ReachableUses,
-                                 unsigned NbReg) {
-  bool HasChanged;
-  do {
-    HasChanged = false;
-    for (const MachineBasicBlock &MBB : MF) {
-      unsigned CurReg;
-      for (CurReg = 0; CurReg < NbReg; ++CurReg) {
-        SetOfMachineInstr &BBInSet = getSet(In, MBB, CurReg, NbReg);
-        SetOfMachineInstr &BBReachableUses =
-            getSet(ReachableUses, MBB, CurReg, NbReg);
-        SetOfMachineInstr &BBOutSet = getSet(Out, MBB, CurReg, NbReg);
-        unsigned Size = BBOutSet.size();
-        //   In[bb][color] = U Out[bb.predecessors][color]
-        for (const MachineBasicBlock *PredMBB : MBB.predecessors()) {
-          SetOfMachineInstr &PredOutSet = getSet(Out, *PredMBB, CurReg, NbReg);
-          BBInSet.insert(PredOutSet.begin(), PredOutSet.end());
-        }
-        //   insert reachableUses[bb][color] in each in[bb][color] op.reachedses
-        for (const MachineInstr *MI : BBInSet) {
-          SetOfMachineInstr &OpReachedUses =
-              getUses(ColorOpToReachedUses, CurReg, *MI);
-          OpReachedUses.insert(BBReachableUses.begin(), BBReachableUses.end());
-        }
-        //           Out[bb] = Gen[bb] U (In[bb] - Kill[bb])
-        if (!Kill[&MBB].test(CurReg))
-          BBOutSet.insert(BBInSet.begin(), BBInSet.end());
-        if (Gen[&MBB][CurReg])
-          BBOutSet.insert(Gen[&MBB][CurReg]);
-        HasChanged |= BBOutSet.size() != Size;
-      }
-    }
-  } while (HasChanged);
-}
-
-/// Reaching definition algorithm.
-/// \param MF function on which the algorithm will operate.
-/// \param[out] ColorOpToReachedUses will contain the result of the reaching
-/// def algorithm.
-/// \param ADRPMode specify whether the reaching def algorithm should be tuned
-/// for ADRP optimization. \see initReachingDef for more details.
-/// \param DummyOp if not NULL, the algorithm will work at
-/// basic block scope and will set for every exposed definition a use to
-/// @p DummyOp.
-/// \pre ColorOpToReachedUses is an array of at least number of registers of
-/// InstrToInstrs.
-static void reachingDef(const MachineFunction &MF,
-                        InstrToInstrs *ColorOpToReachedUses,
-                        const MapRegToId &RegToId, bool ADRPMode = false,
-                        const MachineInstr *DummyOp = nullptr) {
-  // structures:
-  // For each basic block.
-  // Out: a set per color of definitions that reach the
-  //      out boundary of this block.
-  // In: Same as Out but for in boundary.
-  // Gen: generated color in this block (one operation per color).
-  // Kill: register set of killed color in this block.
-  // ReachableUses: a set per color of uses (operation) reachable
-  //                for "In" definitions.
-  BlockToSetOfInstrsPerColor Out, In, ReachableUses;
-  BlockToInstrPerColor Gen;
-  BlockToRegSet Kill;
-
-  // Initialize Gen, kill and reachableUses.
-  initReachingDef(MF, ColorOpToReachedUses, Gen, Kill, ReachableUses, RegToId,
-                  DummyOp, ADRPMode);
-
-  // Algo.
-  if (!DummyOp)
-    reachingDefAlgorithm(MF, ColorOpToReachedUses, In, Out, Gen, Kill,
-                         ReachableUses, RegToId.size());
-}
-
-#ifndef NDEBUG
-/// print the result of the reaching definition algorithm.
-static void printReachingDef(const InstrToInstrs *ColorOpToReachedUses,
-                             unsigned NbReg, const TargetRegisterInfo *TRI,
-                             const MapIdToReg &IdToReg) {
-  unsigned CurReg;
-  for (CurReg = 0; CurReg < NbReg; ++CurReg) {
-    if (ColorOpToReachedUses[CurReg].empty())
-      continue;
-    DEBUG(dbgs() << "*** Reg " << PrintReg(IdToReg[CurReg], TRI) << " ***\n");
+class ReachingPhysDefs_Others : public ReachingPhysDefs {
+  void reachedUsesToDefs() override;
 
-    for (const auto &DefsIt : ColorOpToReachedUses[CurReg]) {
-      DEBUG(dbgs() << "Def:\n");
-      DEBUG(DefsIt.first->print(dbgs()));
-      DEBUG(dbgs() << "Reachable uses:\n");
-      for (const MachineInstr *MI : DefsIt.second) {
-        DEBUG(MI->print(dbgs()));
-      }
-    }
-  }
+public:
+  ReachingPhysDefs_Others(MachineFunction *MF_, const TargetRegisterInfo *TRI_,
+                        bool BasicBlockScopeOnly)
+    : ReachingPhysDefs(MF_, TRI_, BasicBlockScopeOnly,
+                       "All reaching defs") {}
+  void addRegs();
+
+  InstrToInstrs &getUseToDefs() { return UseToDefs; }
+
+  /// Returns the first definition in UseToDefs for MI.
+  MachineInstr *getDef(MachineInstr *MI) {
+    return *UseToDefs.find(MI)->second.begin();
   }
-#endif // NDEBUG
+};
 
 /// Answer the following question: Can Def be one of the definition
 /// involved in a part of a LOH?
 static bool canDefBePartOfLOH(const MachineInstr *Def) {
   unsigned Opc = Def->getOpcode();
   // Accept ADRP, ADDLow and LOADGot.
   switch (Opc) {
   default:
case AArch64::LDRXui:
     case MachineOperand::MO_GlobalAddress:
       return true;
     }
   }
   // Unreachable.
   return false;
 }
 
+/// Check whether the given instruction can be the end of a LOH chain
+/// involving a load.
+static bool isCandidateLoad(const MachineInstr *Instr) {
+  switch (Instr->getOpcode()) {
+  default:
+    return false;
+  case AArch64::LDRSBWui:
+  case AArch64::LDRSBXui:
+  case AArch64::LDRSHWui:
+  case AArch64::LDRSHXui:
+  case AArch64::LDRSWui:
+  case AArch64::LDRBui:
+  case AArch64::LDRHui:
+  case AArch64::LDRWui:
+  case AArch64::LDRXui:
+  case AArch64::LDRSui:
+  case AArch64::LDRDui:
+  case AArch64::LDRQui:
+    if (Instr->getOperand(2).getTargetFlags() & AArch64II::MO_GOT)
+      return false;
+    return true;
+  }
+  // Unreachable.
+  return false;
+}
+
 /// Check whether the given instruction can the end of a LOH chain involving a
 /// store.
 static bool isCandidateStore(const MachineInstr *Instr) {
   switch (Instr->getOpcode()) {
   default:
     return false;
   case AArch64::STRBBui:
   case AArch64::STRHHui:
   case AArch64::STRBui:
   case AArch64::STRHui:
   case AArch64::STRWui:
   case AArch64::STRXui:
   case AArch64::STRSui:
   case AArch64::STRDui:
   case AArch64::STRQui:
     // In case we have str xA, [xA, #imm], this is two different uses
     // of xA and we cannot fold, otherwise the xA stored may be wrong,
     // even if #imm == 0.
     if (Instr->getOperand(0).getReg() != Instr->getOperand(1).getReg())
       return true;
   }
   return false;
 }
 
-/// Given the result of a reaching definition algorithm in ColorOpToReachedUses,
-/// Build the Use to Defs information and filter out obvious non-LOH candidates.
-/// In ADRPMode, non-LOH candidates are "uses" with non-ADRP definitions.
-/// In non-ADRPMode, non-LOH candidates are "uses" with several definition,
-/// i.e., no simple chain.
-/// \param ADRPMode -- \see initReachingDef.
-static void reachedUsesToDefs(InstrToInstrs &UseToReachingDefs,
-                              const InstrToInstrs *ColorOpToReachedUses,
-                              const MapRegToId &RegToId,
-                              bool ADRPMode = false) {
+/// Look for every register defined by potential LOHs candidates.
+static void collectLOHInvolvedRegs(ReachingPhysDefs &ReachingDefs,
+                                   MachineFunction *MF) {
+  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
+
+  DEBUG(dbgs() << "** Collect Involved Register\n");
+  for (const auto &MBB : *MF) {
+    for (const MachineInstr &MI : MBB) {
+      if (!canDefBePartOfLOH(&MI) &&
+          !isCandidateLoad(&MI) && !isCandidateStore(&MI))
+        continue;
+
+      // Process defs
+      for (MachineInstr::const_mop_iterator IO = MI.operands_begin(),
+                                            IOEnd = MI.operands_end();
+           IO != IOEnd; ++IO) {
+        if (!IO->isReg() || !IO->isDef())
+          continue;
+        unsigned CurReg = IO->getReg();
+        for (MCRegAliasIterator AI(CurReg, TRI, true);
+             AI.isValid(); ++AI)
+          if (!ReachingDefs.isRegInMaps(*AI)) {
+            ReachingDefs.addReg(*AI);
+            DEBUG(dbgs() << "Register: " << PrintReg(*AI, TRI)
+                  << '\n');
+          }
+      }
+    }
+  }
+}
+
+void ReachingPhysDefs_ADRP::addRegs() {
+  if (!PreCollectRegister) {
+    ReachingPhysDefs::addAllTargetRegs();
+    return;
+  }
+
+  collectLOHInvolvedRegs(*this, MF);
+}
+
+unsigned ReachingPhysDefs_ADRP::processMIUseMO(MachineOperand &MO) {
+  // Only handle ADRP instructions, and treat ADRP def as use, as the
+  // goal of the analysis is to find ADRP defs reached by other ADRP
+  // defs.
+  if (MO.getParent()->getOpcode() != AArch64::ADRP || !MO.isReg() || !MO.isDef())
+    return 0;
+  return MO.getReg();
+}
+
+void ReachingPhysDefs_ADRP::reachedUsesToDefs() {
+  SetOfMachineInstr NotCandidate;
+  MapRegToId::const_iterator EndIt = RegToId.end();
+  for (unsigned CurReg = 0; CurReg < nbRegs(); ++CurReg) {
+    // If this color is never defined, continue.
+    if (ColorOpToReachedUses[CurReg].empty())
+      continue;
+
+    for (const auto &DefsIt : ColorOpToReachedUses[CurReg]) {
+      for (MachineInstr *MI : DefsIt.second) {
+        const MachineInstr *Def = DefsIt.first;
+        MapRegToId::const_iterator It;
+        // if all the reaching defs are not adrp, this use will not be
+        // simplifiable.
+        if (Def->getOpcode() != AArch64::ADRP) {
+          NotCandidate.insert(MI);
+          continue;
+        }
+        // Do not consider self reaching as a simplifiable case for ADRP.
+        if (MI != DefsIt.first)
+          UseToDefs[MI].insert(DefsIt.first);
+      }
+    }
+  }
+  for (MachineInstr *Elem : NotCandidate) {
+    DEBUG(dbgs() << "Too many reaching defs: " << *Elem << "\n");
+    // It would have been better if we could just remove the entry
+    // from the map.  Because of that, we have to filter the garbage
+    // (second.empty) in the subsequence analysis.
+    UseToDefs[Elem].clear();
+  }
+}
+
+void ReachingPhysDefs_Others::addRegs() {
+  if (!PreCollectRegister) {
+    ReachingPhysDefs::addAllTargetRegs();
+    return;
+  }
+
+  collectLOHInvolvedRegs(*this, MF);
+}
 
+void ReachingPhysDefs_Others::reachedUsesToDefs() {
   SetOfMachineInstr NotCandidate;
   unsigned NbReg = RegToId.size();
   MapRegToId::const_iterator EndIt = RegToId.end();
   for (unsigned CurReg = 0; CurReg < NbReg; ++CurReg) {
     // If this color is never defined, continue.
     if (ColorOpToReachedUses[CurReg].empty())
       continue;
 
     for (const auto &DefsIt : ColorOpToReachedUses[CurReg]) {
-      for (const MachineInstr *MI : DefsIt.second) {
-        const MachineInstr *Def = DefsIt.first;
+      for (MachineInstr *MI : DefsIt.second) {
+        MachineInstr *Def = DefsIt.first;
         MapRegToId::const_iterator It;
         // if all the reaching defs are not adrp, this use will not be
         // simplifiable.
-        if ((ADRPMode && Def->getOpcode() != AArch64::ADRP) ||
-            (!ADRPMode && !canDefBePartOfLOH(Def)) ||
-            (!ADRPMode && isCandidateStore(MI) &&
+        if (!canDefBePartOfLOH(Def) ||
+            (isCandidateStore(MI) &&
              // store are LOH candidate iff the end of the chain is used as
              // base.
              ((It = RegToId.find((MI)->getOperand(1).getReg())) == EndIt ||
               It->second != CurReg))) {
           NotCandidate.insert(MI);
           continue;
         }
-        // Do not consider self reaching as a simplifiable case for ADRP.
-        if (!ADRPMode || MI != DefsIt.first) {
-          UseToReachingDefs[MI].insert(DefsIt.first);
-          // If UsesIt has several reaching definitions, it is not
-          // candidate for simplificaton in non-ADRPMode.
-          if (!ADRPMode && UseToReachingDefs[MI].size() > 1)
-            NotCandidate.insert(MI);
-        }
-      }
-    }
-  }
-  for (const MachineInstr *Elem : NotCandidate) {
+        UseToDefs[MI].insert(DefsIt.first);
+        if (UseToDefs[MI].size() > 1)
+  for (MachineInstr *Elem : NotCandidate) {
     DEBUG(dbgs() << "Too many reaching defs: " << *Elem << "\n");
     // It would have been better if we could just remove the entry
     // from the map.  Because of that, we have to filter the garbage
     // (second.empty) in the subsequence analysis.
-    UseToReachingDefs[Elem].clear();
+    UseToDefs[Elem].clear();
   }
 }
 
+
+
 /// Based on the use to defs information (in ADRPMode), compute the
 /// opportunities of LOH ADRP-related.
-static void computeADRP(const InstrToInstrs &UseToDefs,
+static void computeADRP(ReachingPhysDefs_ADRP &ReachingDefs_ADRP,
                         AArch64FunctionInfo &AArch64FI,
                         const MachineDominatorTree *MDT) {
   DEBUG(dbgs() << "*** Compute LOH for ADRP\n");
-  for (const auto &Entry : UseToDefs) {
+  for (const auto &Entry : ReachingDefs_ADRP.getUseToDefs()) {
     unsigned Size = Entry.second.size();
     if (Size == 0)
       continue;
     if (Size == 1) {
       const MachineInstr *L2 = *Entry.second.begin();
       const MachineInstr *L1 = Entry.first;
       if (!MDT->dominates(L2, L1)) {
         DEBUG(dbgs() << "Dominance check failed:\n" << *L2 << '\n' << *L1
#ifdef DEBUG
     else
       ++NumADRPComplexCandidateOther;
 #endif
     // if Size < 1, the use should have been removed from the candidates
     assert(Size >= 1 && "No reaching defs for that use!");
   }
 }
 
-/// Check whether the given instruction can be the end of a LOH chain
-/// involving a load.
-static bool isCandidateLoad(const MachineInstr *Instr) {
-  switch (Instr->getOpcode()) {
-  default:
-    return false;
-  case AArch64::LDRSBWui:
-  case AArch64::LDRSBXui:
-  case AArch64::LDRSHWui:
-  case AArch64::LDRSHXui:
-  case AArch64::LDRSWui:
-  case AArch64::LDRBui:
-  case AArch64::LDRHui:
-  case AArch64::LDRWui:
-  case AArch64::LDRXui:
-  case AArch64::LDRSui:
-  case AArch64::LDRDui:
-  case AArch64::LDRQui:
-    if (Instr->getOperand(2).getTargetFlags() & AArch64II::MO_GOT)
-      return false;
-    return true;
-  }
-  // Unreachable.
-  return false;
-}
-
 /// Check whether the given instruction can load a litteral.
 static bool supportLoadFromLiteral(const MachineInstr *Instr) {
   switch (Instr->getOpcode()) {
   default:
     return false;
   case AArch64::LDRSWui:
   case AArch64::LDRWui:
   case AArch64::LDRXui:
   case AArch64::LDRSui:
   case AArch64::LDRDui:
   case AArch64::LDRQui:
     return true;
   }
   // Unreachable.
   return false;
 }
 
 /// Check whether the given instruction is a LOH candidate.
 /// \param UseToDefs is used to check that Instr is at the end of LOH supported
 /// chain.
 /// \pre UseToDefs contains only on def per use, i.e., obvious non candidate are
 /// already been filtered out.
-static bool isCandidate(const MachineInstr *Instr,
+static bool isCandidate(MachineInstr *Instr,
                         const InstrToInstrs &UseToDefs,
                         const MachineDominatorTree *MDT) {
   if (!isCandidateLoad(Instr) && !isCandidateStore(Instr))
     return false;
 
-  const MachineInstr *Def = *UseToDefs.find(Instr)->second.begin();
+  MachineInstr *Def = *UseToDefs.find(Instr)->second.begin();
   if (Def->getOpcode() != AArch64::ADRP) {
     // At this point, Def is ADDXri or LDRXui of the right type of
     // symbol, because we filtered out the uses that were not defined
     // by these kind of instructions (+ ADRP).
 
     // Check if this forms a simple chain: each intermediate node must
     // dominates the next one.
     if (!MDT->dominates(Def, Instr))
static bool isCandidate(MachineInstr *Instr,
   // - top is ADRP.
   // - check the simple chain property: each intermediate node must
   // dominates the next one.
   if (Def->getOpcode() == AArch64::ADRP)
     return MDT->dominates(Def, Instr);
   return false;
 }
 
-static bool registerADRCandidate(const MachineInstr &Use,
-                                 const InstrToInstrs &UseToDefs,
-                                 const InstrToInstrs *DefsPerColorToUses,
+static bool registerADRCandidate(MachineInstr &Use,
+                                 ReachingPhysDefs_Others &ReachingDefs,
                                  AArch64FunctionInfo &AArch64FI,
-                                 SetOfMachineInstr *InvolvedInLOHs,
-                                 const MapRegToId &RegToId) {
+                                 SetOfMachineInstr *InvolvedInLOHs) {
   // Look for opportunities to turn ADRP -> ADD or
   // ADRP -> LDR GOTPAGEOFF into ADR.
   // If ADRP has more than one use. Give up.
   if (Use.getOpcode() != AArch64::ADDXri &&
       (Use.getOpcode() != AArch64::LDRXui ||
        !(Use.getOperand(2).getTargetFlags() & AArch64II::MO_GOT)))
     return false;
-  InstrToInstrs::const_iterator It = UseToDefs.find(&Use);
+  InstrToInstrs::const_iterator It = ReachingDefs.getUseToDefs().find(&Use);
   // The map may contain garbage that we need to ignore.
-  if (It == UseToDefs.end() || It->second.empty())
+  if (It == ReachingDefs.getUseToDefs().end() || It->second.empty())
     return false;
-  const MachineInstr &Def = **It->second.begin();
+  MachineInstr &Def = **It->second.begin();
   if (Def.getOpcode() != AArch64::ADRP)
     return false;
   // Check the number of users of ADRP.
   const SetOfMachineInstr *Users =
-      getUses(DefsPerColorToUses,
-              RegToId.find(Def.getOperand(0).getReg())->second, Def);
+    ReachingDefs.getUses(Def.getOperand(0).getReg(), Def);
   if (Users->size() > 1) {
     ++NumADRComplexCandidate;
     return false;
   }
   ++NumADRSimpleCandidate;
   assert((!InvolvedInLOHs || InvolvedInLOHs->insert(&Def)) &&
          "ADRP already involved in LOH.");
   assert((!InvolvedInLOHs || InvolvedInLOHs->insert(&Use)) &&
          "ADD already involved in LOH.");
   DEBUG(dbgs() << "Record AdrpAdd\n" << Def << '\n' << Use << '\n');
 
   SmallVector<const MachineInstr *, 2> Args;
   Args.push_back(&Def);
   Args.push_back(&Use);
 
   AArch64FI.addLOHDirective(Use.getOpcode() == AArch64::ADDXri ? MCLOH_AdrpAdd
                                                            : MCLOH_AdrpLdrGot,
                           Args);
   return true;
 }
 
 /// Based on the use to defs information (in non-ADRPMode), compute the
 /// opportunities of LOH non-ADRP-related
-static void computeOthers(const InstrToInstrs &UseToDefs,
-                          const InstrToInstrs *DefsPerColorToUses,
-                          AArch64FunctionInfo &AArch64FI, const MapRegToId &RegToId,
+static void computeOthers(ReachingPhysDefs_Others &ReachingDefs,
+                          AArch64FunctionInfo &AArch64FI,
                           const MachineDominatorTree *MDT) {
   SetOfMachineInstr *InvolvedInLOHs = nullptr;
 #ifdef DEBUG
   SetOfMachineInstr InvolvedInLOHsStorage;
   InvolvedInLOHs = &InvolvedInLOHsStorage;
 #endif // DEBUG
   DEBUG(dbgs() << "*** Compute LOH for Others\n");
   // ADRP -> ADD/LDR -> LDR/STR pattern.
   // Fall back to ADRP -> ADD pattern if we fail to catch the bigger pattern.
 
   // FIXME: When the statistics are not important,
   // This initial filtering loop can be merged into the next loop.
   // Currently, we didn't do it to have the same code for both DEBUG and
   // NDEBUG builds. Indeed, the iterator of the second loop would need
   // to be changed.
   SetOfMachineInstr PotentialCandidates;
   SetOfMachineInstr PotentialADROpportunities;
-  for (auto &Use : UseToDefs) {
+  for (auto &Use : ReachingDefs.getUseToDefs()) {
     // If no definition is available, this is a non candidate.
     if (Use.second.empty())
       continue;
     // Keep only instructions that are load or store and at the end of
     // a ADRP -> ADD/LDR/Nothing chain.
     // We already filtered out the no-chain cases.
-    if (!isCandidate(Use.first, UseToDefs, MDT)) {
+    if (!isCandidate(Use.first, ReachingDefs.getUseToDefs(), MDT)) {
       PotentialADROpportunities.insert(Use.first);
       continue;
     }
     PotentialCandidates.insert(Use.first);
   }
 
   // Make the following distinctions for statistics as the linker does
   // know how to decode instructions:
   // - ADD/LDR/Nothing make there different patterns.
   // - LDR/STR make two different patterns.
   // Hence, 6 - 1 base patterns.
   // (because ADRP-> Nothing -> STR is not simplifiable)
 
   // The linker is only able to have a simple semantic, i.e., if pattern A
   // do B.
   // However, we want to see the opportunity we may miss if we were able to
   // catch more complex cases.
 
   // PotentialCandidates are result of a chain ADRP -> ADD/LDR ->
   // A potential candidate becomes a candidate, if its current immediate
   // operand is zero and all nodes of the chain have respectively only one user
 #ifdef DEBUG
   SetOfMachineInstr DefsOfPotentialCandidates;
 #endif
-  for (const MachineInstr *Candidate : PotentialCandidates) {
+  for (MachineInstr *Candidate : PotentialCandidates) {
     // Get the definition of the candidate i.e., ADD or LDR.
-    const MachineInstr *Def = *UseToDefs.find(Candidate)->second.begin();
+    MachineInstr *Def = ReachingDefs.getDef(Candidate);
     // Record the elements of the chain.
-    const MachineInstr *L1 = Def;
-    const MachineInstr *L2 = nullptr;
+    MachineInstr *L1 = Def;
+    MachineInstr *L2 = nullptr;
     unsigned ImmediateDefOpc = Def->getOpcode();
     if (Def->getOpcode() != AArch64::ADRP) {
       // Check the number of users of this node.
       const SetOfMachineInstr *Users =
-          getUses(DefsPerColorToUses,
-                  RegToId.find(Def->getOperand(0).getReg())->second, *Def);
+        ReachingDefs.getUses(Def->getOperand(0).getReg(), *Def);
       if (Users->size() > 1) {
 #ifdef DEBUG
         // if all the uses of this def are in potential candidate, this is
         // a complex candidate of level 2.
         bool IsLevel2 = true;
-        for (const MachineInstr *MI : *Users) {
+        for (MachineInstr *MI : *Users) {
           if (!PotentialCandidates.count(MI)) {
             ++NumTooCplxLvl2;
             IsLevel2 = false;
             break;
           }
         }
         if (IsLevel2)
           ++NumCplxLvl2;
 #endif // DEBUG
         PotentialADROpportunities.insert(Def);
         continue;
       }
       L2 = Def;
-      Def = *UseToDefs.find(Def)->second.begin();
+      Def = *ReachingDefs.getUseToDefs().find(Def)->second.begin();
       L1 = Def;
     } // else the element in the middle of the chain is nothing, thus
       // Def already contains the first element of the chain.
 
     // Check the number of users of the first node in the chain, i.e., ADRP
     const SetOfMachineInstr *Users =
-        getUses(DefsPerColorToUses,
-                RegToId.find(Def->getOperand(0).getReg())->second, *Def);
+      ReachingDefs.getUses(Def->getOperand(0).getReg(), *Def);
     if (Users->size() > 1) {
 #ifdef DEBUG
       // if all the uses of this def are in the defs of the potential candidate,
       // this is a complex candidate of level 1
       if (DefsOfPotentialCandidates.empty()) {
         // lazy init
         DefsOfPotentialCandidates = PotentialCandidates;
-        for (const MachineInstr *Candidate : PotentialCandidates) {
-          if (!UseToDefs.find(Candidate)->second.empty())
+        for (MachineInstr *Candidate : PotentialCandidates) {
+          if (!ReachingDefs.getUseToDefs().find(Candidate)->second.empty())
             DefsOfPotentialCandidates.insert(
-                *UseToDefs.find(Candidate)->second.begin());
+                *ReachingDefs.getUseToDefs().find(Candidate)->second.begin());
         }
       }
       bool Found = false;
       for (auto &Use : *Users) {
         if (!DefsOfPotentialCandidates.count(Use)) {
           ++NumTooCplxLvl1;
           Found = true;
           break;
#ifdef DEBUG
           ++NumLDRToSTRWithImm;
 #endif // DEBUG
       }
     }
     AArch64FI.addLOHDirective(Kind, Args);
   }
 
   // Now, we grabbed all the big patterns, check ADR opportunities.
-  for (const MachineInstr *Candidate : PotentialADROpportunities)
-    registerADRCandidate(*Candidate, UseToDefs, DefsPerColorToUses, AArch64FI,
-                         InvolvedInLOHs, RegToId);
-}
-
-/// Look for every register defined by potential LOHs candidates.
-/// Map these registers with dense id in @p RegToId and vice-versa in
-/// @p IdToReg. @p IdToReg is populated only in DEBUG mode.
-static void collectInvolvedReg(const MachineFunction &MF, MapRegToId &RegToId,
-                               MapIdToReg &IdToReg,
-                               const TargetRegisterInfo *TRI) {
-  unsigned CurRegId = 0;
-  if (!PreCollectRegister) {
-    unsigned NbReg = TRI->getNumRegs();
-    for (; CurRegId < NbReg; ++CurRegId) {
-      RegToId[CurRegId] = CurRegId;
-      DEBUG(IdToReg.push_back(CurRegId));
-      DEBUG(assert(IdToReg[CurRegId] == CurRegId && "Reg index mismatches"));
-    }
-    return;
-  }
-
-  DEBUG(dbgs() << "** Collect Involved Register\n");
-  for (const auto &MBB : MF) {
-    for (const MachineInstr &MI : MBB) {
-      if (!canDefBePartOfLOH(&MI) &&
-          !isCandidateLoad(&MI) && !isCandidateStore(&MI))
-        continue;
-
-      // Process defs
-      for (MachineInstr::const_mop_iterator IO = MI.operands_begin(),
-                                            IOEnd = MI.operands_end();
-           IO != IOEnd; ++IO) {
-        if (!IO->isReg() || !IO->isDef())
-          continue;
-        unsigned CurReg = IO->getReg();
-        for (MCRegAliasIterator AI(CurReg, TRI, true); AI.isValid(); ++AI)
-          if (RegToId.find(*AI) == RegToId.end()) {
-            DEBUG(IdToReg.push_back(*AI);
-                  assert(IdToReg[CurRegId] == *AI &&
-                         "Reg index mismatches insertion index."));
-            RegToId[*AI] = CurRegId++;
-            DEBUG(dbgs() << "Register: " << PrintReg(*AI, TRI) << '\n');
-          }
-      }
-    }
-  }
+  for (MachineInstr *Candidate : PotentialADROpportunities)
+    registerADRCandidate(*Candidate, ReachingDefs, AArch64FI, InvolvedInLOHs);
 }
 
 bool AArch64CollectLOH::runOnMachineFunction(MachineFunction &MF) {
   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
   const MachineDominatorTree *MDT = &getAnalysis<MachineDominatorTree>();
 
-  MapRegToId RegToId;
-  MapIdToReg IdToReg;
   AArch64FunctionInfo *AArch64FI = MF.getInfo<AArch64FunctionInfo>();
   assert(AArch64FI && "No MachineFunctionInfo for this function!");
 
   DEBUG(dbgs() << "Looking for LOH in " << MF.getName() << '\n');
 
-  collectInvolvedReg(MF, RegToId, IdToReg, TRI);
-  if (RegToId.empty())
-    return false;
-
-  MachineInstr *DummyOp = nullptr;
-  if (BasicBlockScopeOnly) {
-    const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
-    // For local analysis, create a dummy operation to record uses that are not
-    // local.
-    DummyOp = MF.CreateMachineInstr(TII->get(AArch64::COPY), DebugLoc());
-  }
-
-  unsigned NbReg = RegToId.size();
   bool Modified = false;
 
   // Start with ADRP.
-  InstrToInstrs *ColorOpToReachedUses = new InstrToInstrs[NbReg];
-
-  // Compute the reaching def in ADRP mode, meaning ADRP definitions
-  // are first considered as uses.
-  reachingDef(MF, ColorOpToReachedUses, RegToId, true, DummyOp);
-  DEBUG(dbgs() << "ADRP reaching defs\n");
-  DEBUG(printReachingDef(ColorOpToReachedUses, NbReg, TRI, IdToReg));
-
-  // Translate the definition to uses map into a use to definitions map to ease
-  // statistic computation.
-  InstrToInstrs ADRPToReachingDefs;
-  reachedUsesToDefs(ADRPToReachingDefs, ColorOpToReachedUses, RegToId, true);
+  ReachingPhysDefs_ADRP ReachingDefs_ADRP(&MF, TRI, BasicBlockScopeOnly);
+  ReachingDefs_ADRP.addRegs();
+  if (!ReachingDefs_ADRP.analyze())
+    return false;
+  DEBUG(ReachingDefs_ADRP.dump(););
 
   // Compute LOH for ADRP.
-  computeADRP(ADRPToReachingDefs, *AArch64FI, MDT);
-  delete[] ColorOpToReachedUses;
+  computeADRP(ReachingDefs_ADRP, *AArch64FI, MDT);
 
   // Continue with general ADRP -> ADD/LDR -> LDR/STR pattern.
-  ColorOpToReachedUses = new InstrToInstrs[NbReg];
-
-  // first perform a regular reaching def analysis.
-  reachingDef(MF, ColorOpToReachedUses, RegToId, false, DummyOp);
-  DEBUG(dbgs() << "All reaching defs\n");
-  DEBUG(printReachingDef(ColorOpToReachedUses, NbReg, TRI, IdToReg));
-
-  // Turn that into a use to defs to ease statistic computation.
-  InstrToInstrs UsesToReachingDefs;
-  reachedUsesToDefs(UsesToReachingDefs, ColorOpToReachedUses, RegToId, false);
+  ReachingPhysDefs_Others ReachingDefs(&MF, TRI, BasicBlockScopeOnly);
+  ReachingDefs.addRegs();
+  ReachingDefs.analyze();
+  DEBUG(ReachingDefs.dump(););
 
   // Compute other than AdrpAdrp LOH.
-  computeOthers(UsesToReachingDefs, ColorOpToReachedUses, *AArch64FI, RegToId,
-                MDT);
-  delete[] ColorOpToReachedUses;
-
-  if (BasicBlockScopeOnly)
-    MF.DeleteMachineInstr(DummyOp);
+  computeOthers(ReachingDefs, *AArch64FI, MDT);
 
   return Modified;
 }
 
 /// createAArch64CollectLOHPass - returns an instance of the Statistic for
 /// linker optimization pass.
 FunctionPass *llvm::createAArch64CollectLOHPass() {
   return new AArch64CollectLOH();
 }

lib/Target/SystemZ/SystemZElimCompare.cpp

 // (2) fuses compares and branches into COMPARE AND BRANCH instructions
 //
 //===----------------------------------------------------------------------===//
 
 #include "SystemZTargetMachine.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/ReachingPhysDefs.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 
 using namespace llvm;
public:
   static char ID;
   SystemZElimCompare(const SystemZTargetMachine &tm)
     : MachineFunctionPass(ID), TII(nullptr), TRI(nullptr) {}
 
   const char *getPassName() const override {
     return "SystemZ Comparison Elimination";
   }
 
-  bool processBlock(MachineBasicBlock &MBB);
+  bool processBlock(MachineBasicBlock &MBB,
+                    ReachingPhysDefs &ReachingDefs);
   bool runOnMachineFunction(MachineFunction &F) override;
 
 private:
   Reference getRegReferences(MachineInstr *MI, unsigned Reg);
   bool convertToBRCT(MachineInstr *MI, MachineInstr *Compare,
-                     SmallVectorImpl<MachineInstr *> &CCUsers);
+                     SetOfMachineInstr &CCUses);
+
   bool convertToLoadAndTest(MachineInstr *MI);
   bool adjustCCMasksForInstr(MachineInstr *MI, MachineInstr *Compare,
-                             SmallVectorImpl<MachineInstr *> &CCUsers);
-  bool optimizeCompareZero(MachineInstr *Compare,
-                           SmallVectorImpl<MachineInstr *> &CCUsers);
-  bool fuseCompareAndBranch(MachineInstr *Compare,
-                            SmallVectorImpl<MachineInstr *> &CCUsers);
+                             SetOfMachineInstr &CCUses);
+  bool optimizeCompareZero(MachineInstr *Compare, SetOfMachineInstr &CCUses);
+  bool fuseCompareAndBranch(MachineInstr *Compare, SetOfMachineInstr &CCUses);
 
   const SystemZInstrInfo *TII;
   const TargetRegisterInfo *TRI;
 };
 
 char SystemZElimCompare::ID = 0;
 } // end anonymous namespace
 
 FunctionPass *llvm::createSystemZElimComparePass(SystemZTargetMachine &TM) {
   return new SystemZElimCompare(TM);
 }
 
-// Return true if CC is live out of MBB.
-static bool isCCLiveOut(MachineBasicBlock &MBB) {
-  for (auto SI = MBB.succ_begin(), SE = MBB.succ_end(); SI != SE; ++SI)
-    if ((*SI)->isLiveIn(SystemZ::CC))
-      return true;
-  return false;
-}
-
 // Return true if any CC result of MI would reflect the value of Reg.
 static bool resultTests(MachineInstr *MI, unsigned Reg) {
   if (MI->getNumOperands() > 0 &&
       MI->getOperand(0).isReg() &&
       MI->getOperand(0).isDef() &&
       MI->getOperand(0).getReg() == Reg)
     return true;
 
static unsigned getCompareSourceReg(MachineInstr *Compare) {
   else if (isLoadAndTestAsCmp(Compare))
     reg = Compare->getOperand(1).getReg();
   assert (reg);
 
   return reg;
 }
 
 // Compare compares the result of MI against zero.  If MI is an addition
-// of -1 and if CCUsers is a single branch on nonzero, eliminate the addition
+// of -1 and if CCUses is a single branch on nonzero, eliminate the addition
 // and convert the branch to a BRCT(G).  Return true on success.
 bool
 SystemZElimCompare::convertToBRCT(MachineInstr *MI, MachineInstr *Compare,
-                                  SmallVectorImpl<MachineInstr *> &CCUsers) {
+                                  SetOfMachineInstr &CCUses) {
   // Check whether we have an addition of -1.
   unsigned Opcode = MI->getOpcode();
   unsigned BRCT;
   if (Opcode == SystemZ::AHI)
     BRCT = SystemZ::BRCT;
   else if (Opcode == SystemZ::AGHI)
     BRCT = SystemZ::BRCTG;
   else
     return false;
   if (MI->getOperand(2).getImm() != -1)
     return false;
 
   // Check whether we have a single JLH.
-  if (CCUsers.size() != 1)
+  if (CCUses.size() != 1)
     return false;
-  MachineInstr *Branch = CCUsers[0];
+  MachineInstr *Branch = CCUses[0];
   if (Branch->getOpcode() != SystemZ::BRC ||
       Branch->getOperand(0).getImm() != SystemZ::CCMASK_ICMP ||
       Branch->getOperand(1).getImm() != SystemZ::CCMASK_CMP_NE)
     return false;
 
   // We already know that there are no references to the register between
   // MI and Compare.  Make sure that there are also no references between
   // Compare and Branch.
if (!Opcode)
     return false;
 
   MI->setDesc(TII->get(Opcode));
   MachineInstrBuilder(*MI->getParent()->getParent(), MI)
     .addReg(SystemZ::CC, RegState::ImplicitDefine);
   return true;
 }
 
-// The CC users in CCUsers are testing the result of a comparison of some
+// The CC users in CCUses are testing the result of a comparison of some
 // value X against zero and we know that any CC value produced by MI
-// would also reflect the value of X.  Try to adjust CCUsers so that
+// would also reflect the value of X.  Try to adjust CCUses so that
 // they test the result of MI directly, returning true on success.
 // Leave everything unchanged on failure.
 bool SystemZElimCompare::
 adjustCCMasksForInstr(MachineInstr *MI, MachineInstr *Compare,
-                      SmallVectorImpl<MachineInstr *> &CCUsers) {
+                      SetOfMachineInstr &CCUses) {
   int Opcode = MI->getOpcode();
   const MCInstrDesc &Desc = TII->get(Opcode);
   unsigned MIFlags = Desc.TSFlags;
 
   // See which compare-style condition codes are available.
   unsigned ReusableCCMask = SystemZII::getCompareZeroCCMask(MIFlags);
 
   // For unsigned comparisons with zero, only equality makes sense.
   unsigned CompareFlags = Compare->getDesc().TSFlags;
   if (CompareFlags & SystemZII::IsLogical)
     ReusableCCMask &= SystemZ::CCMASK_CMP_EQ;
 
   if (ReusableCCMask == 0)
     return false;
 
   unsigned CCValues = SystemZII::getCCValues(MIFlags);
   assert((ReusableCCMask & ~CCValues) == 0 && "Invalid CCValues");
 
   // Now check whether these flags are enough for all users.
   SmallVector<MachineOperand *, 4> AlterMasks;
-  for (unsigned int I = 0, E = CCUsers.size(); I != E; ++I) {
-    MachineInstr *MI = CCUsers[I];
+  for (unsigned int I = 0, E = CCUses.size(); I != E; ++I) {
+    MachineInstr *MI = CCUses[I];
 
     // Fail if this isn't a use of CC that we understand.
     unsigned Flags = MI->getDesc().TSFlags;
     unsigned FirstOpNum;
     if (Flags & SystemZII::CCMaskFirst)
       FirstOpNum = 0;
     else if (Flags & SystemZII::CCMaskLast)
       FirstOpNum = MI->getNumExplicitOperands() - 2;
default:
     return (Compare->getNumExplicitOperands() == 2 &&
             Compare->getOperand(1).isImm() &&
             Compare->getOperand(1).getImm() == 0);
   }
 }
 
 // Try to optimize cases where comparison instruction Compare is testing
 // a value against zero.  Return true on success and if Compare should be
-// deleted as dead.  CCUsers is the list of instructions that use the CC
+// deleted as dead.  CCUses is the list of instructions that use the CC
 // value produced by Compare.
 bool SystemZElimCompare::
-optimizeCompareZero(MachineInstr *Compare,
-                    SmallVectorImpl<MachineInstr *> &CCUsers) {
+optimizeCompareZero(MachineInstr *Compare, SetOfMachineInstr &CCUses) {
   if (!isCompareZero(Compare))
     return false;
 
   // Search back for CC results that are based on the first operand.
   unsigned SrcReg = getCompareSourceReg(Compare);
   MachineBasicBlock &MBB = *Compare->getParent();
   MachineBasicBlock::iterator MBBI = Compare, MBBE = MBB.begin();
   Reference CCRefs;
   Reference SrcRefs;
   while (MBBI != MBBE) {
     --MBBI;
     MachineInstr *MI = MBBI;
     if (resultTests(MI, SrcReg)) {
       // Try to remove both MI and Compare by converting a branch to BRCT(G).
       // We don't care in this case whether CC is modified between MI and
       // Compare.
-      if (!CCRefs.Use && !SrcRefs && convertToBRCT(MI, Compare, CCUsers)) {
+      if (!CCRefs.Use && !SrcRefs && convertToBRCT(MI, Compare, CCUses)) {
         BranchOnCounts += 1;
         return true;
       }
       // Try to eliminate Compare by reusing a CC result from MI.
       if ((!CCRefs && convertToLoadAndTest(MI)) ||
-          (!CCRefs.Def && adjustCCMasksForInstr(MI, Compare, CCUsers))) {
+          (!CCRefs.Def && adjustCCMasksForInstr(MI, Compare, CCUses))) {
         EliminatedComparisons += 1;
         return true;
       }
     }
     SrcRefs |= getRegReferences(MI, SrcReg);
     if (SrcRefs.Def)
       return false;
     CCRefs |= getRegReferences(MI, SystemZ::CC);
     if (CCRefs.Use && CCRefs.Def)
       return false;
   }
   return false;
 }
 
 // Try to fuse comparison instruction Compare into a later branch.
 // Return true on success and if Compare is therefore redundant.
 bool SystemZElimCompare::
-fuseCompareAndBranch(MachineInstr *Compare,
-                     SmallVectorImpl<MachineInstr *> &CCUsers) {
+fuseCompareAndBranch(MachineInstr *Compare, SetOfMachineInstr &CCUses) {
   // See whether we have a comparison that can be fused.
   unsigned FusedOpcode = TII->getCompareAndBranch(Compare->getOpcode(),
                                                   Compare);
   if (!FusedOpcode)
     return false;
 
   // See whether we have a single branch with which to fuse.
-  if (CCUsers.size() != 1)
+  if (CCUses.size() != 1)
     return false;
-  MachineInstr *Branch = CCUsers[0];
+  MachineInstr *Branch = CCUses[0];
   if (Branch->getOpcode() != SystemZ::BRC)
     return false;
 
   // Make sure that the operands are available at the branch.
   unsigned SrcReg = Compare->getOperand(0).getReg();
   unsigned SrcReg2 = (Compare->getOperand(1).isReg() ?
                       Compare->getOperand(1).getReg() : 0);
   MachineBasicBlock::iterator MBBI = Compare, MBBE = Branch;
if (SrcReg2)
       MBBI->clearRegisterKills(SrcReg2, TRI);
   }
   FusedComparisons += 1;
   return true;
 }
 
 // Process all comparison instructions in MBB.  Return true if something
 // changed.
-bool SystemZElimCompare::processBlock(MachineBasicBlock &MBB) {
+bool SystemZElimCompare::processBlock(MachineBasicBlock &MBB,
+                                      ReachingPhysDefs &ReachingDefs) {
   bool Changed = false;
 
   // Walk backwards through the block looking for comparisons, recording
   // all CC users as we go.  The subroutines can delete Compare and
   // instructions before it.
-  bool CompleteCCUsers = !isCCLiveOut(MBB);
-  SmallVector<MachineInstr *, 4> CCUsers;
   MachineBasicBlock::iterator MBBI = MBB.end();
   while (MBBI != MBB.begin()) {
     MachineInstr *MI = --MBBI;
-    if (CompleteCCUsers &&
-        (MI->isCompare() || isLoadAndTestAsCmp(MI)) &&
-        (optimizeCompareZero(MI, CCUsers) ||
-         fuseCompareAndBranch(MI, CCUsers))) {
+    if (MI->isCompare() || isLoadAndTestAsCmp(MI)) {
+      SetOfMachineInstr *CCUses = ReachingDefs.getUses(SystemZ::CC, *MI);
+
+      if (CCUses != nullptr &&
+          (optimizeCompareZero(MI, *CCUses) ||
+           fuseCompareAndBranch(MI, *CCUses))) {
         ++MBBI;
         MI->eraseFromParent();
         Changed = true;
-      CCUsers.clear();
-      continue;
       }
-
-    if (MI->definesRegister(SystemZ::CC)) {
-      CCUsers.clear();
-      CompleteCCUsers = true;
     }
-    if (MI->readsRegister(SystemZ::CC) && CompleteCCUsers)
-      CCUsers.push_back(MI);
   }
+
   return Changed;
 }
 
 bool SystemZElimCompare::runOnMachineFunction(MachineFunction &F) {
   TII = static_cast<const SystemZInstrInfo *>(F.getSubtarget().getInstrInfo());
   TRI = &TII->getRegisterInfo();
 
+  // Use the ReachingPhysDefs class to do a global mapping from all
+  // defs / users of the CC reg. This is helpful in cases where late
+  // optimizers have caused some CC users to lie in other blocks than
+  // the compare instruction.
+  // This is only computed once even though F is being operated on.
+  ReachingPhysDefs ReachingDefs(&F, TRI, false, "Reaching CC defs");
+  ReachingDefs.analyze(SystemZ::CC);
+  ReachingDefs.pruneMultipleDefs();
+  DEBUG(ReachingDefs.dump());
+
   bool Changed = false;
   for (auto &MBB : F)
-    Changed |= processBlock(MBB);
+    Changed |= processBlock(MBB, ReachingDefs);
 
   return Changed;
 }