[MachineSink] replace MachineLoop with MachineCycle

[shchenz]

Summary

MachineCycle can handle irreducible loop. Natural loop analysis (MachineLoop) can not return correct loop depth if the loop is irreducible loop. And MachineSink is sensitive to the loop depth, see MachineSinking::isProfitableToSinkTo().

In https://reviews.llvm.org/D120800, we prevent a sinking from shallower loop to deeper loop after checking irreducible cfg in the whole function.

This patch tries to use MachineCycle so that we can handle irreducible loop better.

[nikic]

I was concerned about compile-time impact of using MachineCycleInfo, but it looks like the impact is fairly low on CTMark: http://llvm-compile-time-tracker.com/compare.php?from=42865819b22486963294434fb21b51ab3e6ebfa4&to=61706f3ee1c979e7ec893d0bc4858790561a27c0&stat=instructions Looks like SPASS with ReleaseLTO-g is the only one with some non-trivial impact.

[sameerds]

Do note that the cycle hierarchy is implementation-defined, and hence the reported cycle depth is not an invariant property of the program being compiled. For example, in the following CFG:

     Entry
       |\
       v \
   .-> P  \
  /    |   \
 /     v    \
'      Q     \
|     / \     |
|    /   \    |
|   v     v   |
`-- S <-- R <-'
    |
    v
   Exit

Here. the analysis can either identify one cycle with header P, or two nested cycles with headers R and S.

The change description says that MachineSink is "sensitive" to cycle depth. Is it only the performance of the resulting program, or does it affect correctness too?

llvm/include/llvm/ADT/GenericCycleImpl.h

82

Why not just use succ_size()? It's defined in CFG.h for LLVM IR and in MachineSSAContext.h for Machine IR.

Also, minor optimization ... this check is probably slightly cheaper than isLegalToHoistInto(), so it might help to check it earlier.

llvm/include/llvm/ADT/GenericCycleInfo.h

140

This is not defined for LLVM IR. Maybe move it to the Machine IR specialization?

[shchenz]

address @sameerds comments

[shchenz]

I was concerned about compile-time impact of using MachineCycleInfo, but it looks like the impact is fairly low on CTMark: http://llvm-compile-time-tracker.com/compare.php?from=42865819b22486963294434fb21b51ab3e6ebfa4&to=61706f3ee1c979e7ec893d0bc4858790561a27c0&stat=instructions Looks like SPASS with ReleaseLTO-g is the only one with some non-trivial impact.

Thanks very much for the testing @nikic and glad to hear that the compile time impact is low. Let me know if you think the %0.39 improve for SPASS needs to be further investigated.

The change description says that MachineSink is "sensitive" to cycle depth. Is it only the performance of the resulting program, or does it affect correctness too?

I think the depth check should only impact the performance in machinesink. However there are some codes(hasStoreBetween) which does not work right for irreducible loops, with this patch, we can get correct behavior. But I think we need more investigation for that function. I plan to do more investigation later to avoid errors.

llvm/include/llvm/ADT/GenericCycleImpl.h

82

Thanks, updated.

[sameerds]

The changes in GenericCycleInfo look good to me. But please do wait for reviewers looking at MachineSink.

llvm/include/llvm/ADT/GenericCycleInfo.h

132

Instead of saying "for now", we could simply say that pre-header is well-defined for reducible cycles, as listed in LoopTerminology.html. Then also add "returns nullptr if irreducible".

Same for the next function.

llvm/include/llvm/CodeGen/MachineCycleAnalysis.h

61

I think you mean "add to GenericCycle"?

llvm/include/llvm/CodeGen/MachineSSAContext.h

31

Oops! Thanks for adding this to trunk! Now I realize I was looking at a topic branch in my repo where I had already put these in place. :)

[shchenz]

address @sameerds comments

[shchenz]

The changes in GenericCycleInfo look good to me. But please do wait for reviewers looking at MachineSink.

Thanks very much for review @sameerds . Sure, I will wait for the MachineSink part review.

llvm/include/llvm/ADT/GenericCycleInfo.h

132

Updated.

llvm/include/llvm/CodeGen/MachineCycleAnalysis.h

61

Oops...

[shchenz]

gentle ping for the MachineSink part. Thanks!

[MatzeB]

llvm/include/llvm/ADT/GenericCycleImpl.h

70

I did not even know this is legal C++ syntax; Anyway please be consistent with the rest of LLVM here!

89

llvm/include/llvm/ADT/GenericCycleInfo.h

103

as above

221

Consider just pushing this as a small fix directly to git without review.

llvm/include/llvm/CodeGen/MachineCycleAnalysis.h

48

Do we need a TODO comment here? Will the verify analysis added at this particular line?

61–62

Do we need a TODO comment?

llvm/include/llvm/CodeGen/MachineSSAContext.h

31–32

Explicit types help everyone reading the code.

llvm/lib/CodeGen/MachineSink.cpp

384

Rename L to C (or better Cycle)?

468–473

Rename L/Loop to Cycle/Cycles ?

There's more place below that where the same applies.

[MatzeB]

Thanks, I think this will be good to go when all the nitpicks are addressed!

llvm/include/llvm/ADT/GenericCycleImpl.h

71–72

This is already checked in getCyclePredecessor

82

Everything in the Cycle info appears to be only concerned about the structure of the CFG. This is the only function that looks at non-structural attributes like if something is an exception landing pad. I feel like it's probably better to have this helper function somewhere else and not be a member of GenericCycle.

How about keeping it local to MachineSink.cpp?

97

llvm/include/llvm/ADT/GenericCycleInfo.h

103

• Other functions are called isEntry and printEntries and the CycleTerminology documentation calls them entries as well. So this should be called getEntries() I think.

• Use SmallVectorImpl<T> without specifying the size for APIs

131–132

As far as I can tell LoopTerminology.rst defines the term *Header* but not pre-header. Please put a definition into the comment here.

(And consider moving the function out of here anyway as above, since it checks for non-structural properties in isLegalToHoistInto)

136–137

I think we should talk about "cycles" not "loops" here. How about this:

llvm/lib/CodeGen/MachineCycleAnalysis.cpp

17–18

I assume this can be removed given that you dropped the extern declarations in the header?

124–125

FWIW: We should probably change this to !MO.readsReg() (because moving undef use operands around should be no problem); but it's probably out of the scope of this diff and we better do that separately.

llvm/lib/CodeGen/MachineSink.cpp

236–239

468–469

645–651

Move the getCycle results into variables so we don't need to lookup the same block multiple times in the hashmap?

[sameerds]

llvm/include/llvm/ADT/GenericCycleImpl.h

70

There is no other precedent in LLVM for this to be consistent with. The proposed change of putting BlockT* as the return type will not work because BlockT is defined inside the GenericCycle<ContextT> class and cannot be used until that class is named. The alternative is to say "GenericCycle<ContextT>::BlockT", but I am very strongly opposed to that kind of repetition.

llvm/include/llvm/ADT/GenericCycleInfo.h

131–132

The document does define preheader, under the section Terminology:

https://llvm.org/docs/LoopTerminology.html#terminology

Good catch about isLegalToHoistInto. But maybe only that check needs to be moved out of this file? The preheader itself is still defined purely in terms of CFG structure.

llvm/include/llvm/CodeGen/MachineCycleAnalysis.h

22–23

Why was this removed? This is necessary to prevent automatic instantiation of the template at the point of use. This particular template instance is defined once in MachineCycleAnalysis.cpp

llvm/lib/CodeGen/MachineCycleAnalysis.cpp

10–14

This ordering of headers is wrong. MachineCycleAnalysis.h should be the first header. I am surprised that clang-format did not do this automatically.

17–18

No this should be retained along with the extern declarations in the header.

[MatzeB]

llvm/include/llvm/ADT/GenericCycleImpl.h

70

I would rather see the longer GenericCycle<ContextT>::BlockT than the unusual trailing return syntax that isn't even necessary here.

Seems like we have to agree to disagree here. And I guess that means leaving it unchanged if I cannot convince you...

llvm/include/llvm/ADT/GenericCycleInfo.h

131–132

• Oh, I was reading CycleTerminology and missed this one. I would still recommend to add 1 or 2 sentences here to what a preheader is and maybe also add it to CycleTerminology.rst.

• Moving just the isLegalToHoistInto call works too of course.

[shchenz]

address @MatzeB & @sameerds comments

[shchenz]

llvm/include/llvm/ADT/GenericCycleImpl.h

70

I leave it as now to make sure it is uniform at least in this file. We can change all these functions with a follow-up NFC patch if you insist.

82

This is from getLoopPreheader() and isLegalToHoistInto() check was intentionally added in https://reviews.llvm.org/D34487. And IMO, we also need this for cycle preheader?

llvm/include/llvm/ADT/GenericCycleInfo.h

103

Thanks. I will commit another patch to rename above getHeader() later.

131–132

I will handle isLegalToHoistInto when we decide where should we put it.

221

Committed https://reviews.llvm.org/rG0ca2b93cc2864ad33937f21351f0d34dd5819aa2

llvm/include/llvm/CodeGen/MachineCycleAnalysis.h

48

Moved from lib/CodeGen/MachineCycleAnalysis.cpp. I thought, it is a placeholder for a declare of verify function?

61–62

This function should be implemented for both MIR and IR. Now for machinesink, I just implement MIR version, once IR version is implemented, we can move this function to the template class GenericCycle. So I add this TODO, do you mean we don't need TODO for this case?

llvm/lib/CodeGen/MachineCycleAnalysis.cpp

124–125

OK.

[shchenz]

gentle ping

[MatzeB]

LGTM but let's wait for @sameerds for accept.

llvm/include/llvm/ADT/GenericCycleInfo.h

103

The header is define in CycleTerminology.rst as the first entry we find. So the name of the getHeader function seems fine to me. (The getHeaders here was questionable, because the documented hinted that there is only one and those things were already called entries anyway).

llvm/include/llvm/CodeGen/MachineCycleAnalysis.h

48

Can you just remove it?

[sameerds]

LGTM! My sincere apologies for the delay ... I have no excuse :(

llvm/include/llvm/ADT/GenericCycleImpl.h

70

FWIW, this got discussed in the original review where this file was added:

https://reviews.llvm.org/D112696#3175521

[shchenz]

In D123995#3533225, @sameerds wrote:

LGTM! My sincere apologies for the delay ... I have no excuse :(

It doesn't matter at all : )

Thanks very much for review! @sameerds @MatzeB

llvm/include/llvm/CodeGen/MachineCycleAnalysis.h

48

Sure, will remove this in the commit.

[aprantl]

It looks like this commit broke the -DLLVM_ENABLES_MODULES=1 build: https://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/43994/changes

[aprantl]

Another bot failure.
https://green.lab.llvm.org/green/view/Clang/job/clang-stage2-Rthinlto/5501/consoleFull#-125847874549ba4694-19c4-4d7e-bec5-911270d8a58c

[aprantl]

@shchenz Would you consider reverting your patch? Let me know if you have trouble reproducing the issue.

[shchenz]

In D123995#3535764, @aprantl wrote:

@shchenz Would you consider reverting your patch? Let me know if you have trouble reproducing the issue.

@aprantl Sorry for the inconvenience. I reverted this patch. However, I can not reproduce the build failure on PowerPC Linux with follow command: (I get it from lldb buildbot):

cmake -DCMAKE_BUILD_TYPE=Release -DCMAKE_C_COMPILER=/stage1/clang -DCMAKE_CXX_COMPILER=/stage1/clang++ -DLLVM_ENABLE_ASSERTIONS=1  -DLLVM_ENABLES_MODULES=1 -DLLVM_ENABLE_PROJECTS="clang;lld;lldb;cross-project-tests" -DLLVM_TARGETS_TO_BUILD="X86;ARM;AArch64" ../llvm/ ; make

I will do more test to reproduce the failure and let me know if I miss something in the above command. Thanks.

[nikic]

In D123995#3461553, @shchenz wrote:

The change description says that MachineSink is "sensitive" to cycle depth. Is it only the performance of the resulting program, or does it affect correctness too?

I think the depth check should only impact the performance in machinesink. However there are some codes(hasStoreBetween) which does not work right for irreducible loops, with this patch, we can get correct behavior. But I think we need more investigation for that function. I plan to do more investigation later to avoid errors.

Just to double check, did you verify that hasStoreBetween() works fine with the new implementation? I'm slightly concerned that we may be reintroducing the miscompile depending on how CycleInfo gets chosen.

[shchenz]

In D123995#3545464, @nikic wrote:

In D123995#3461553, @shchenz wrote:

The change description says that MachineSink is "sensitive" to cycle depth. Is it only the performance of the resulting program, or does it affect correctness too?

I think the depth check should only impact the performance in machinesink. However there are some codes(hasStoreBetween) which does not work right for irreducible loops, with this patch, we can get correct behavior. But I think we need more investigation for that function. I plan to do more investigation later to avoid errors.

Just to double check, did you verify that hasStoreBetween() works fine with the new implementation? I'm slightly concerned that we may be reintroducing the miscompile depending on how CycleInfo gets chosen.

Yes, I did some check before, with the machinecycle, we should be ok now for hasStoreBetween() (I am not 100% sure though).
1: We will not sink instructions from BBFrom in a cycle leading by HeaderA to a BBTo in another cycle leading by HeaderB (HeaderA and HeaderB are two headers of a irreducible cycle), as BBFrom must dominate BBTo, but HeaderA and HeaderB does not need to be dominated.
2: We will also not sink instruction from predecessor block of header cycle to a block inside the cycle no matter the cycle is reducible or irreducible.

[avogelsgesang]

FYI: I suspect this change caused a compile-time regression from 60sec to >40 minutes for an interpreter-loop based on computed-gotos. See https://github.com/llvm/llvm-project/issues/57664

[fhahn]

It looks like this is causing a huge performance regression: https://github.com/llvm/llvm-project/issues/57664

@shchenz could you take a look?

llvm/include/llvm/ADT/GenericCycleImpl.h

for (size_t Idx = NumExitBlocks, End = TmpStorage.size(); Idx < End;
           TmpStorage[NumExitBlocks++] = Succ;
       }
     }
 
     TmpStorage.resize(NumExitBlocks);
   }
 }
 
+template <typename ContextT>
+auto GenericCycle<ContextT>::getCyclePreheader() const -> BlockT * {
+  BlockT *Predecessor = getCyclePredecessor();
+  if (!Predecessor)
+    return nullptr;
+
+  assert(isReducible() && "Cycle Predecessor must be in a reducible cycle!");
+
+  if (succ_size(Predecessor) != 1)
+    return nullptr;
+
+  // Make sure we are allowed to hoist instructions into the predecessor.
+  if (!Predecessor->isLegalToHoistInto())
+    return nullptr;
+
+  return Predecessor;
+}
+
+template <typename ContextT>
+auto GenericCycle<ContextT>::getCyclePredecessor() const -> BlockT * {
+  if (!isReducible())
+    return nullptr;
+
+  BlockT *Out = nullptr;
+
+  // Loop over the predecessors of the header node...
+  BlockT *Header = getHeader();
+  for (const auto Pred : predecessors(Header)) {
+    if (!contains(Pred)) {
+      if (Out && Out != Pred)
+        return nullptr;
+      Out = Pred;
+    }
+  }
+
+  return Out;
+}
+
 /// \brief Helper class for computing cycle information.
 template <typename ContextT> class GenericCycleInfoCompute {
   using BlockT = typename ContextT::BlockT;
   using CycleInfoT = GenericCycleInfo<ContextT>;
   using CycleT = typename CycleInfoT::CycleT;
 
   CycleInfoT &Info;
 

 auto GenericCycleInfo<ContextT>::getCycle(const BlockT *Block) const
     -> CycleT * {
   auto MapIt = BlockMap.find(Block);
   if (MapIt != BlockMap.end())
     return MapIt->second;
   return nullptr;
 }
 
+/// \brief get the depth for the cycle which containing a given block.
+///
+/// \returns the depth for the innermost cycle containing \p Block or 0 if it is
+///          not contained in any cycle.
+template <typename ContextT>
+unsigned GenericCycleInfo<ContextT>::getCycleDepth(const BlockT *Block) const {
+  CycleT *Cycle = getCycle(Block);
+  if (!Cycle)
+    return 0;
+  return Cycle->getDepth();
+}
+
 /// \brief Validate the internal consistency of the cycle tree.
 ///
 /// Note that this does \em not check that cycles are really cycles in the CFG,
 /// or that the right set of cycles in the CFG were found.
 template <typename ContextT>
 bool GenericCycleInfo<ContextT>::validateTree() const {
   DenseSet<BlockT *> Blocks;
   DenseSet<BlockT *> Entries;

llvm/include/llvm/ADT/GenericCycleInfo.h

 public:
   GenericCycle() = default;
 
   /// \brief Whether the cycle is a natural loop.
   bool isReducible() const { return Entries.size() == 1; }
 
   BlockT *getHeader() const { return Entries[0]; }
 
+  const SmallVectorImpl<BlockT *> & getEntries() const {
+    return Entries;
+  }
+
   /// \brief Return whether \p Block is an entry block of the cycle.
   bool isEntry(BlockT *Block) const { return is_contained(Entries, Block); }
 
   /// \brief Return whether \p Block is contained in the cycle.
   bool contains(const BlockT *Block) const {
     return is_contained(Blocks, Block);
   }
 
   /// \brief Returns true iff this cycle contains \p C.
   ///
   /// Note: Non-strict containment check, i.e. returns true if C is the
   /// same cycle.
   bool contains(const GenericCycle *C) const;
 
   const GenericCycle *getParentCycle() const { return ParentCycle; }
   GenericCycle *getParentCycle() { return ParentCycle; }
   unsigned getDepth() const { return Depth; }
 
   /// Return all of the successor blocks of this cycle.
   ///
   /// These are the blocks _outside of the current cycle_ which are
   /// branched to.
   void getExitBlocks(SmallVectorImpl<BlockT *> &TmpStorage) const;
 
+  /// Return the preheader block for this cycle. Pre-header is well-defined for
+  /// reducible cycle in docs/LoopTerminology.rst as: the only one entering
+  /// block and its only edge is to the entry block. Return null for irreducible
+  /// cycles.
+  BlockT *getCyclePreheader() const;
+
+  /// If the cycle has exactly one entry with exactly one predecessor, return
+  /// it, otherwise return nullptr.
+  BlockT *getCyclePredecessor() const;
+
   /// Iteration over child cycles.
   //@{
   using const_child_iterator_base =
       typename std::vector<std::unique_ptr<GenericCycle>>::const_iterator;
   struct const_child_iterator
       : iterator_adaptor_base<const_child_iterator, const_child_iterator_base> {
     using Base =
         iterator_adaptor_base<const_child_iterator, const_child_iterator_base>;
return Printable([this, &Ctx](raw_ostream &Out) {
       for (auto *Block : Blocks) {
         if (isEntry(Block))
           continue;
 
         Out << ' ' << Ctx.print(Block);
       }
     });
   }
 };
 
 /// \brief Cycle information for a function.
 template <typename ContextT> class GenericCycleInfo {
 public:
   using BlockT = typename ContextT::BlockT;
   using CycleT = GenericCycle<ContextT>;
   using FunctionT = typename ContextT::FunctionT;
   template <typename> friend class GenericCycle;
public:
 
   void clear();
   void compute(FunctionT &F);
 
   FunctionT *getFunction() const { return Context.getFunction(); }
   const ContextT &getSSAContext() const { return Context; }
 
   CycleT *getCycle(const BlockT *Block) const;
+  unsigned getCycleDepth(const BlockT *Block) const;
   CycleT *getTopLevelParentCycle(const BlockT *Block) const;
 
   /// Move \p Child to \p NewParent by manipulating Children vectors.
   ///
   /// Note: This is an incomplete operation that does not update the
   /// list of blocks in the new parent or the depth of the subtree.
   void moveToNewParent(CycleT *NewParent, CycleT *Child);
 

llvm/include/llvm/CodeGen/MachineCycleAnalysis.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_MACHINECYCLEANALYSIS_H
 #define LLVM_CODEGEN_MACHINECYCLEANALYSIS_H
 
 #include "llvm/ADT/GenericCycleInfo.h"
 #include "llvm/CodeGen/MachineSSAContext.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/InitializePasses.h"
 
 namespace llvm {
 
 extern template class GenericCycleInfo<MachineSSAContext>;
 extern template class GenericCycle<MachineSSAContext>;
 
 using MachineCycleInfo = GenericCycleInfo<MachineSSAContext>;
 using MachineCycle = MachineCycleInfo::CycleT;
 
+/// Legacy analysis pass which computes a \ref MachineCycleInfo.
+class MachineCycleInfoWrapperPass : public MachineFunctionPass {
+  MachineFunction *F = nullptr;
+  MachineCycleInfo CI;
+
+public:
+  static char ID;
+
+  MachineCycleInfoWrapperPass();
+
+  MachineCycleInfo &getCycleInfo() { return CI; }
+  const MachineCycleInfo &getCycleInfo() const { return CI; }
+
+  bool runOnMachineFunction(MachineFunction &F) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+  void releaseMemory() override;
+  void print(raw_ostream &OS, const Module *M = nullptr) const override;
+
+  // TODO: verify analysis
+};
+
+class MachineCycleInfoPrinterPass : public MachineFunctionPass {
+public:
+  static char ID;
+
+  MachineCycleInfoPrinterPass();
+
+  bool runOnMachineFunction(MachineFunction &F) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+};
+
+// TODO: add this function to GenericCycle template after implementing IR
+//       version.
+bool isCycleInvariant(const MachineCycle *Cycle, MachineInstr &I);
+
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_MACHINECYCLEANALYSIS_H

llvm/include/llvm/CodeGen/MachineSSAContext.h

 class MachineInstr;
 class MachineFunction;
 class Register;
 template <typename _FunctionT> class GenericSSAContext;
 template <typename, bool> class DominatorTreeBase;
 
 inline auto successors(MachineBasicBlock *BB) { return BB->successors(); }
 inline auto predecessors(MachineBasicBlock *BB) { return BB->predecessors(); }
+inline unsigned succ_size(MachineBasicBlock *BB) { return BB->succ_size(); }
+inline unsigned pred_size(MachineBasicBlock *BB) { return BB->pred_size(); }
 
 template <> class GenericSSAContext<MachineFunction> {
   const MachineRegisterInfo *RegInfo = nullptr;
   MachineFunction *MF;
 
 public:
   using BlockT = MachineBasicBlock;
   using FunctionT = MachineFunction;

llvm/lib/CodeGen/MachineCycleAnalysis.cpp

 //===- MachineCycleAnalysis.cpp - Compute CycleInfo for Machine IR --------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/MachineCycleAnalysis.h"
 #include "llvm/ADT/GenericCycleImpl.h"
-#include "llvm/CodeGen/MachineFunctionPass.h"
-#include "llvm/CodeGen/MachineSSAContext.h"
-#include "llvm/InitializePasses.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/TargetInstrInfo.h"
+#include "llvm/CodeGen/TargetSubtargetInfo.h"
 
 using namespace llvm;
 
 template class llvm::GenericCycleInfo<llvm::MachineSSAContext>;
 template class llvm::GenericCycle<llvm::MachineSSAContext>;
 
-namespace {
-
-/// Legacy analysis pass which computes a \ref MachineCycleInfo.
-class MachineCycleInfoWrapperPass : public MachineFunctionPass {
-  MachineFunction *F = nullptr;
-  MachineCycleInfo CI;
-
-public:
-  static char ID;
-
-  MachineCycleInfoWrapperPass();
-
-  MachineCycleInfo &getCycleInfo() { return CI; }
-  const MachineCycleInfo &getCycleInfo() const { return CI; }
-
-  bool runOnMachineFunction(MachineFunction &F) override;
-  void getAnalysisUsage(AnalysisUsage &AU) const override;
-  void releaseMemory() override;
-  void print(raw_ostream &OS, const Module *M = nullptr) const override;
-
-  // TODO: verify analysis
-};
-
-class MachineCycleInfoPrinterPass : public MachineFunctionPass {
-public:
-  static char ID;
-
-  MachineCycleInfoPrinterPass();
-
-  bool runOnMachineFunction(MachineFunction &F) override;
-  void getAnalysisUsage(AnalysisUsage &AU) const override;
-};
-
-} // namespace
-
 char MachineCycleInfoWrapperPass::ID = 0;
 
 MachineCycleInfoWrapperPass::MachineCycleInfoWrapperPass()
     : MachineFunctionPass(ID) {
   initializeMachineCycleInfoWrapperPassPass(*PassRegistry::getPassRegistry());
 }
 
 INITIALIZE_PASS_BEGIN(MachineCycleInfoWrapperPass, "machine-cycles",
void MachineCycleInfoPrinterPass::getAnalysisUsage(AnalysisUsage &AU) const {
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 bool MachineCycleInfoPrinterPass::runOnMachineFunction(MachineFunction &F) {
   auto &CI = getAnalysis<MachineCycleInfoWrapperPass>();
   CI.print(errs());
   return false;
 }
+
+bool llvm::isCycleInvariant(const MachineCycle *Cycle, MachineInstr &I) {
+  MachineFunction *MF = I.getParent()->getParent();
+  MachineRegisterInfo *MRI = &MF->getRegInfo();
+  const TargetSubtargetInfo &ST = MF->getSubtarget();
+  const TargetRegisterInfo *TRI = ST.getRegisterInfo();
+  const TargetInstrInfo *TII = ST.getInstrInfo();
+
+  // The instruction is cycle invariant if all of its operands are.
+  for (const MachineOperand &MO : I.operands()) {
+    if (!MO.isReg())
+      continue;
+
+    Register Reg = MO.getReg();
+    if (Reg == 0)
+      continue;
+
+    // An instruction that uses or defines a physical register can't e.g. be
+    // hoisted, so mark this as not invariant.
+    if (Register::isPhysicalRegister(Reg)) {
+      if (MO.isUse()) {
+        // If the physreg has no defs anywhere, it's just an ambient register
+        // and we can freely move its uses. Alternatively, if it's allocatable,
+        // it could get allocated to something with a def during allocation.
+        // However, if the physreg is known to always be caller saved/restored
+        // then this use is safe to hoist.
+        if (!MRI->isConstantPhysReg(Reg) &&
+            !(TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *I.getMF())) &&
+            !TII->isIgnorableUse(MO))
+          return false;
+        // Otherwise it's safe to move.
+        continue;
+      } else if (!MO.isDead()) {
+        // A def that isn't dead can't be moved.
+        return false;
+      } else if (any_of(Cycle->getEntries(),
+                        [&](const MachineBasicBlock *Block) {
+                          return Block->isLiveIn(Reg);
+                        })) {
+        // If the reg is live into any header of the cycle we can't hoist an
+        // instruction which would clobber it.
+        return false;
+      }
+    }
+
+    if (!MO.isUse())
+      continue;
+
+    assert(MRI->getVRegDef(Reg) && "Machine instr not mapped for this vreg?!");
+
+    // If the cycle contains the definition of an operand, then the instruction
+    // isn't cycle invariant.
+    if (Cycle->contains(MRI->getVRegDef(Reg)->getParent()))
+      return false;
+  }
+
+  // If we got this far, the instruction is cycle invariant!
+  return true;
+}

llvm/lib/CodeGen/MachineSink.cpp

 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
+#include "llvm/CodeGen/MachineCycleAnalysis.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachinePostDominators.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"

 
 static cl::opt<unsigned> SinkLoadBlocksThreshold(
     "machine-sink-load-blocks-threshold",
     cl::desc("Do not try to find alias store for a load if the block number in "
              "the straight line is higher than this threshold."),
     cl::init(20), cl::Hidden);
 
 static cl::opt<bool>
-SinkInstsIntoLoop("sink-insts-to-avoid-spills",
-                  cl::desc("Sink instructions into loops to avoid "
+    SinkInstsIntoCycle("sink-insts-to-avoid-spills",
+                       cl::desc("Sink instructions into cycles to avoid "
                                 "register spills"),
                        cl::init(false), cl::Hidden);
 
-static cl::opt<unsigned> SinkIntoLoopLimit(
-    "machine-sink-loop-limit",
-    cl::desc("The maximum number of instructions considered for loop sinking."),
+static cl::opt<unsigned> SinkIntoCycleLimit(
+    "machine-sink-cycle-limit",
+    cl::desc("The maximum number of instructions considered for cycle sinking."),
     cl::init(50), cl::Hidden);
 
 STATISTIC(NumSunk,      "Number of machine instructions sunk");
-STATISTIC(NumLoopSunk,  "Number of machine instructions sunk into a loop");
+STATISTIC(NumCycleSunk,  "Number of machine instructions sunk into a cycle");
 STATISTIC(NumSplit,     "Number of critical edges split");
 STATISTIC(NumCoalesces, "Number of copies coalesced");
 STATISTIC(NumPostRACopySink, "Number of copies sunk after RA");
 
 namespace {
 
   class MachineSinking : public MachineFunctionPass {
     const TargetInstrInfo *TII;
     const TargetRegisterInfo *TRI;
     MachineRegisterInfo  *MRI;     // Machine register information
     MachineDominatorTree *DT;      // Machine dominator tree
     MachinePostDominatorTree *PDT; // Machine post dominator tree
-    MachineLoopInfo *LI;
+    MachineCycleInfo *CI;
     MachineBlockFrequencyInfo *MBFI;
     const MachineBranchProbabilityInfo *MBPI;
     AliasAnalysis *AA;
     RegisterClassInfo RegClassInfo;
 
     // Remember which edges have been considered for breaking.
     SmallSet<std::pair<MachineBasicBlock*, MachineBasicBlock*>, 8>
     CEBCandidates;
public:
 
     bool runOnMachineFunction(MachineFunction &MF) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       MachineFunctionPass::getAnalysisUsage(AU);
       AU.addRequired<AAResultsWrapperPass>();
       AU.addRequired<MachineDominatorTree>();
       AU.addRequired<MachinePostDominatorTree>();
-      AU.addRequired<MachineLoopInfo>();
+      AU.addRequired<MachineCycleInfoWrapperPass>();
       AU.addRequired<MachineBranchProbabilityInfo>();
+      AU.addPreserved<MachineCycleInfoWrapperPass>();
       AU.addPreserved<MachineLoopInfo>();
       if (UseBlockFreqInfo)
         AU.addRequired<MachineBlockFrequencyInfo>();
     }
 
     void releaseMemory() override {
       CEBCandidates.clear();
     }
private:
     /// to the copy source.
     void SalvageUnsunkDebugUsersOfCopy(MachineInstr &,
                                        MachineBasicBlock *TargetBlock);
     bool AllUsesDominatedByBlock(Register Reg, MachineBasicBlock *MBB,
                                  MachineBasicBlock *DefMBB, bool &BreakPHIEdge,
                                  bool &LocalUse) const;
     MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
                bool &BreakPHIEdge, AllSuccsCache &AllSuccessors);
 
-    void FindLoopSinkCandidates(MachineLoop *L, MachineBasicBlock *BB,
+    void FindCycleSinkCandidates(MachineCycle *Cycle, MachineBasicBlock *BB,
                                  SmallVectorImpl<MachineInstr *> &Candidates);
-    bool SinkIntoLoop(MachineLoop *L, MachineInstr &I);
+    bool SinkIntoCycle(MachineCycle *Cycle, MachineInstr &I);
 
     bool isProfitableToSinkTo(Register Reg, MachineInstr &MI,
                               MachineBasicBlock *MBB,
                               MachineBasicBlock *SuccToSinkTo,
                               AllSuccsCache &AllSuccessors);
 
     bool PerformTrivialForwardCoalescing(MachineInstr &MI,
                                          MachineBasicBlock *MBB);

 char MachineSinking::ID = 0;
 
 char &llvm::MachineSinkingID = MachineSinking::ID;
 
 INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE,
                       "Machine code sinking", false, false)
 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
-INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
+INITIALIZE_PASS_DEPENDENCY(MachineCycleInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_END(MachineSinking, DEBUG_TYPE,
                     "Machine code sinking", false, false)
 
 bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
                                                      MachineBasicBlock *MBB) {
   if (!MI.isCopy())
     return false;
static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) {
   for (MachineMemOperand *MemOp : MI.memoperands())
     if (const PseudoSourceValue *PSV = MemOp->getPseudoValue())
       if (PSV->isGOT() || PSV->isConstantPool())
         return true;
 
   return false;
 }
 
-void MachineSinking::FindLoopSinkCandidates(MachineLoop *L, MachineBasicBlock *BB,
+void MachineSinking::FindCycleSinkCandidates(
+    MachineCycle *Cycle, MachineBasicBlock *BB,
     SmallVectorImpl<MachineInstr *> &Candidates) {
   for (auto &MI : *BB) {
-    LLVM_DEBUG(dbgs() << "LoopSink: Analysing candidate: " << MI);
+    LLVM_DEBUG(dbgs() << "CycleSink: Analysing candidate: " << MI);
     if (!TII->shouldSink(MI)) {
-      LLVM_DEBUG(dbgs() << "LoopSink: Instruction not a candidate for this "
+      LLVM_DEBUG(dbgs() << "CycleSink: Instruction not a candidate for this "
                            "target\n");
       continue;
     }
-    if (!L->isLoopInvariant(MI)) {
-      LLVM_DEBUG(dbgs() << "LoopSink: Instruction is not loop invariant\n");
+    if (!isCycleInvariant(Cycle, MI)) {
+      LLVM_DEBUG(dbgs() << "CycleSink: Instruction is not cycle invariant\n");
       continue;
     }
     bool DontMoveAcrossStore = true;
     if (!MI.isSafeToMove(AA, DontMoveAcrossStore)) {
-      LLVM_DEBUG(dbgs() << "LoopSink: Instruction not safe to move.\n");
+      LLVM_DEBUG(dbgs() << "CycleSink: Instruction not safe to move.\n");
       continue;
     }
     if (MI.mayLoad() && !mayLoadFromGOTOrConstantPool(MI)) {
-      LLVM_DEBUG(dbgs() << "LoopSink: Dont sink GOT or constant pool loads\n");
+      LLVM_DEBUG(dbgs() << "CycleSink: Dont sink GOT or constant pool loads\n");
       continue;
     }
     if (MI.isConvergent())
       continue;
 
     const MachineOperand &MO = MI.getOperand(0);
     if (!MO.isReg() || !MO.getReg() || !MO.isDef())
       continue;
     if (!MRI->hasOneDef(MO.getReg()))
       continue;
 
-    LLVM_DEBUG(dbgs() << "LoopSink: Instruction added as candidate.\n");
+    LLVM_DEBUG(dbgs() << "CycleSink: Instruction added as candidate.\n");
     Candidates.push_back(&MI);
   }
 }
 
 bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
   if (skipFunction(MF.getFunction()))
     return false;
 
   LLVM_DEBUG(dbgs() << "******** Machine Sinking ********\n");
 
   TII = MF.getSubtarget().getInstrInfo();
   TRI = MF.getSubtarget().getRegisterInfo();
   MRI = &MF.getRegInfo();
   DT = &getAnalysis<MachineDominatorTree>();
   PDT = &getAnalysis<MachinePostDominatorTree>();
-  LI = &getAnalysis<MachineLoopInfo>();
+  CI = &getAnalysis<MachineCycleInfoWrapperPass>().getCycleInfo();
   MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   RegClassInfo.runOnMachineFunction(MF);
 
-  // MachineSink currently uses MachineLoopInfo, which only recognizes natural
-  // loops. As such, we could sink instructions into irreducible cycles, which
-  // would be non-profitable.
-  // WARNING: The current implementation of hasStoreBetween() is incorrect for
-  // sinking into irreducible cycles (PR53990), this bailout is currently
-  // necessary for correctness, not just profitability.
-  ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
-  if (containsIrreducibleCFG<MachineBasicBlock *>(RPOT, *LI))
-    return false;
-
   bool EverMadeChange = false;
 
   while (true) {
     bool MadeChange = false;
 
     // Process all basic blocks.
     CEBCandidates.clear();
     ToSplit.clear();
for (auto &Pair : ToSplit) {
         ++NumSplit;
       } else
         LLVM_DEBUG(dbgs() << " *** Not legal to break critical edge\n");
     }
     // If this iteration over the code changed anything, keep iterating.
     if (!MadeChange) break;
     EverMadeChange = true;
   }
 
-  if (SinkInstsIntoLoop) {
-    SmallVector<MachineLoop *, 8> Loops(LI->begin(), LI->end());
-    for (auto *L : Loops) {
-      MachineBasicBlock *Preheader = LI->findLoopPreheader(L);
+  if (SinkInstsIntoCycle) {
+    SmallVector<MachineCycle *, 8> Cycles(CI->toplevel_begin(),
+                                          CI->toplevel_end());
+    for (auto *Cycle : Cycles) {
+      MachineBasicBlock *Preheader = Cycle->getCyclePreheader();
       if (!Preheader) {
-        LLVM_DEBUG(dbgs() << "LoopSink: Can't find preheader\n");
+        LLVM_DEBUG(dbgs() << "CycleSink: Can't find preheader\n");
         continue;
       }
       SmallVector<MachineInstr *, 8> Candidates;
-      FindLoopSinkCandidates(L, Preheader, Candidates);
+      FindCycleSinkCandidates(Cycle, Preheader, Candidates);
 
       // Walk the candidates in reverse order so that we start with the use
       // of a def-use chain, if there is any.
       // TODO: Sort the candidates using a cost-model.
       unsigned i = 0;
       for (MachineInstr *I : llvm::reverse(Candidates)) {
-        if (i++ == SinkIntoLoopLimit) {
-          LLVM_DEBUG(dbgs() << "LoopSink:   Limit reached of instructions to "
+        if (i++ == SinkIntoCycleLimit) {
+          LLVM_DEBUG(dbgs() << "CycleSink:   Limit reached of instructions to "
                                "be analysed.");
           break;
         }
 
-        if (!SinkIntoLoop(L, *I))
+        if (!SinkIntoCycle(Cycle, *I))
           break;
         EverMadeChange = true;
-        ++NumLoopSunk;
+        ++NumCycleSunk;
       }
     }
   }
 
   HasStoreCache.clear();
   StoreInstrCache.clear();
 
   // Now clear any kill flags for recorded registers.
   for (auto I : RegsToClearKillFlags)
     MRI->clearKillFlags(I);
   RegsToClearKillFlags.clear();
 
   return EverMadeChange;
 }
 
 bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
   // Can't sink anything out of a block that has less than two successors.
   if (MBB.succ_size() <= 1 || MBB.empty()) return false;
 
   // Don't bother sinking code out of unreachable blocks. In addition to being
   // unprofitable, it can also lead to infinite looping, because in an
-  // unreachable loop there may be nowhere to stop.
+  // unreachable cycle there may be nowhere to stop.
   if (!DT->isReachableFromEntry(&MBB)) return false;
 
   bool MadeChange = false;
 
-  // Cache all successors, sorted by frequency info and loop depth.
+  // Cache all successors, sorted by frequency info and cycle depth.
   AllSuccsCache AllSuccessors;
 
   // Walk the basic block bottom-up.  Remember if we saw a store.
   MachineBasicBlock::iterator I = MBB.end();
   --I;
   bool ProcessedBegin, SawStore = false;
   do {
     MachineInstr &MI = *I;  // The instruction to sink.

 
 bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,
                                                MachineBasicBlock *FromBB,
                                                MachineBasicBlock *ToBB,
                                                bool BreakPHIEdge) {
   if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
     return false;
 
-  // Avoid breaking back edge. From == To means backedge for single BB loop.
+  // Avoid breaking back edge. From == To means backedge for single BB cycle.
   if (!SplitEdges || FromBB == ToBB)
     return false;
 
-  // Check for backedges of more "complex" loops.
-  if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) &&
-      LI->isLoopHeader(ToBB))
+  MachineCycle *FromCycle = CI->getCycle(FromBB);
+  MachineCycle *ToCycle = CI->getCycle(ToBB);
+
+  // Check for backedges of more "complex" cycles.
+  if (FromCycle == ToCycle && FromCycle &&
+      (!FromCycle->isReducible() || FromCycle->getHeader() == ToBB))
     return false;
 
   // It's not always legal to break critical edges and sink the computation
   // to the edge.
   //
   // %bb.1:
   // v1024
   // Beq %bb.3
   // <fallthrough>
bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI,
 
   if (MBB == SuccToSinkTo)
     return false;
 
   // It is profitable if SuccToSinkTo does not post dominate current block.
   if (!PDT->dominates(SuccToSinkTo, MBB))
     return true;
 
-  // It is profitable to sink an instruction from a deeper loop to a shallower
-  // loop, even if the latter post-dominates the former (PR21115).
-  if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo))
+  // It is profitable to sink an instruction from a deeper cycle to a shallower
+  // cycle, even if the latter post-dominates the former (PR21115).
+  if (CI->getCycleDepth(MBB) > CI->getCycleDepth(SuccToSinkTo))
     return true;
 
   // Check if only use in post dominated block is PHI instruction.
   bool NonPHIUse = false;
   for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
     MachineBasicBlock *UseBlock = UseInst.getParent();
     if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
       NonPHIUse = true;
   }
   if (!NonPHIUse)
     return true;
 
   // If SuccToSinkTo post dominates then also it may be profitable if MI
   // can further profitably sinked into another block in next round.
   bool BreakPHIEdge = false;
   // FIXME - If finding successor is compile time expensive then cache results.
   if (MachineBasicBlock *MBB2 =
           FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
     return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);
 
-  MachineLoop *ML = LI->getLoopFor(MBB);
+  MachineCycle *MCycle = CI->getCycle(MBB);
 
-  // If the instruction is not inside a loop, it is not profitable to sink MI to
+  // If the instruction is not inside a cycle, it is not profitable to sink MI to
   // a post dominate block SuccToSinkTo.
-  if (!ML)
+  if (!MCycle)
     return false;
 
   auto isRegisterPressureSetExceedLimit = [&](const TargetRegisterClass *RC) {
     unsigned Weight = TRI->getRegClassWeight(RC).RegWeight;
     const int *PS = TRI->getRegClassPressureSets(RC);
     // Get register pressure for block SuccToSinkTo.
     std::vector<unsigned> BBRegisterPressure =
         getBBRegisterPressure(*SuccToSinkTo);
     for (; *PS != -1; PS++)
       // check if any register pressure set exceeds limit in block SuccToSinkTo
       // after sinking.
       if (Weight + BBRegisterPressure[*PS] >=
           TRI->getRegPressureSetLimit(*MBB->getParent(), *PS))
         return true;
     return false;
   };
 
-  // If this instruction is inside a loop and sinking this instruction can make
+  // If this instruction is inside a Cycle and sinking this instruction can make
   // more registers live range shorten, it is still prifitable.
   for (const MachineOperand &MO : MI.operands()) {
     // Ignore non-register operands.
     if (!MO.isReg())
       continue;
     Register Reg = MO.getReg();
     if (Reg == 0)
       continue;
for (const MachineOperand &MO : MI.operands()) {
     if (MO.isDef()) {
       // This def register's live range is shortened after sinking.
       bool LocalUse = false;
       if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, BreakPHIEdge,
                                    LocalUse))
         return false;
     } else {
       MachineInstr *DefMI = MRI->getVRegDef(Reg);
-      // DefMI is defined outside of loop. There should be no live range
-      // impact for this operand. Defination outside of loop means:
-      // 1: defination is outside of loop.
-      // 2: defination is in this loop, but it is a PHI in the loop header.
-      if (LI->getLoopFor(DefMI->getParent()) != ML ||
-          (DefMI->isPHI() && LI->isLoopHeader(DefMI->getParent())))
+      MachineCycle *Cycle = CI->getCycle(DefMI->getParent());
+      // DefMI is defined outside of cycle. There should be no live range
+      // impact for this operand. Defination outside of cycle means:
+      // 1: defination is outside of cycle.
+      // 2: defination is in this cycle, but it is a PHI in the cycle header.
+      if (Cycle != MCycle || (DefMI->isPHI() && Cycle && Cycle->isReducible() &&
+                              Cycle->getHeader() == DefMI->getParent()))
         continue;
-      // The DefMI is defined inside the loop.
+      // The DefMI is defined inside the cycle.
       // If sinking this operand makes some register pressure set exceed limit,
       // it is not profitable.
       if (isRegisterPressureSetExceedLimit(MRI->getRegClass(Reg))) {
         LLVM_DEBUG(dbgs() << "register pressure exceed limit, not profitable.");
         return false;
       }
     }
   }
 
-  // If MI is in loop and all its operands are alive across the whole loop or if
-  // no operand sinking make register pressure set exceed limit, it is
+  // If MI is in cycle and all its operands are alive across the whole cycle or
+  // if no operand sinking make register pressure set exceed limit, it is
   // profitable to sink MI.
   return true;
 }
 
 /// Get the sorted sequence of successors for this MachineBasicBlock, possibly
 /// computing it if it was not already cached.
 SmallVector<MachineBasicBlock *, 4> &
 MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
   for (MachineDomTreeNode *DTChild : DT->getNode(MBB)->children()) {
     // DomTree children of MBB that have MBB as immediate dominator are added.
     if (DTChild->getIDom()->getBlock() == MI.getParent() &&
         // Skip MBBs already added to the AllSuccs vector above.
         !MBB->isSuccessor(DTChild->getBlock()))
       AllSuccs.push_back(DTChild->getBlock());
   }
 
-  // Sort Successors according to their loop depth or block frequency info.
+  // Sort Successors according to their cycle depth or block frequency info.
   llvm::stable_sort(
       AllSuccs, [this](const MachineBasicBlock *L, const MachineBasicBlock *R) {
         uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;
         uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;
         bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0;
         return HasBlockFreq ? LHSFreq < RHSFreq
-                            : LI->getLoopDepth(L) < LI->getLoopDepth(R);
+                            : CI->getCycleDepth(L) < CI->getCycleDepth(R);
       });
 
   auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs));
 
   return it.first->second;
 }
 
 /// FindSuccToSinkTo - Find a successor to sink this instruction to.
 MachineBasicBlock *
 MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
                                  bool &BreakPHIEdge,
                                  AllSuccsCache &AllSuccessors) {
   assert (MBB && "Invalid MachineBasicBlock!");
 
-  // Loop over all the operands of the specified instruction.  If there is
+  // loop over all the operands of the specified instruction.  If there is
   // anything we can't handle, bail out.
 
   // SuccToSinkTo - This is the successor to sink this instruction to, once we
   // decide.
   MachineBasicBlock *SuccToSinkTo = nullptr;
   for (const MachineOperand &MO : MI.operands()) {
     if (!MO.isReg()) continue;  // Ignore non-register operands.
 
if (Register::isPhysicalRegister(Reg)) {
           return nullptr;
 
         continue;
       }
 
       // Otherwise, we should look at all the successors and decide which one
       // we should sink to. If we have reliable block frequency information
       // (frequency != 0) available, give successors with smaller frequencies
-      // higher priority, otherwise prioritize smaller loop depths.
+      // higher priority, otherwise prioritize smaller cycle depths.
       for (MachineBasicBlock *SuccBlock :
            GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
         bool LocalUse = false;
         if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,
                                     BreakPHIEdge, LocalUse)) {
           SuccToSinkTo = SuccBlock;
           break;
         }
         if (LocalUse)
           // Def is used locally, it's never safe to move this def.
           return nullptr;
       }
 
       // If we couldn't find a block to sink to, ignore this instruction.
       if (!SuccToSinkTo)
         return nullptr;
       if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))
         return nullptr;
     }
   }
 
   // It is not possible to sink an instruction into its own block.  This can
-  // happen with loops.
+  // happen with cycles.
   if (MBB == SuccToSinkTo)
     return nullptr;
 
   // It's not safe to sink instructions to EH landing pad. Control flow into
   // landing pad is implicitly defined.
   if (SuccToSinkTo && SuccToSinkTo->isEHPad())
     return nullptr;
 
for (MachineBasicBlock *BB : depth_first(From)) {
     }
   }
   // If there is no store at all, cache the result.
   if (!SawStore)
     HasStoreCache[BlockPair] = false;
   return HasAliasedStore;
 }
 
-/// Sink instructions into loops if profitable. This especially tries to prevent
-/// register spills caused by register pressure if there is little to no
-/// overhead moving instructions into loops.
-bool MachineSinking::SinkIntoLoop(MachineLoop *L, MachineInstr &I) {
-  LLVM_DEBUG(dbgs() << "LoopSink: Finding sink block for: " << I);
-  MachineBasicBlock *Preheader = L->getLoopPreheader();
-  assert(Preheader && "Loop sink needs a preheader block");
+/// Sink instructions into cycles if profitable. This especially tries to
+/// prevent register spills caused by register pressure if there is little to no
+/// overhead moving instructions into cycles.
+bool MachineSinking::SinkIntoCycle(MachineCycle *Cycle, MachineInstr &I) {
+  LLVM_DEBUG(dbgs() << "CycleSink: Finding sink block for: " << I);
+  MachineBasicBlock *Preheader = Cycle->getCyclePreheader();
+  assert(Preheader && "Cycle sink needs a preheader block");
   MachineBasicBlock *SinkBlock = nullptr;
   bool CanSink = true;
   const MachineOperand &MO = I.getOperand(0);
 
   for (MachineInstr &MI : MRI->use_instructions(MO.getReg())) {
-    LLVM_DEBUG(dbgs() << "LoopSink:   Analysing use: " << MI);
-    if (!L->contains(&MI)) {
-      LLVM_DEBUG(dbgs() << "LoopSink:   Use not in loop, can't sink.\n");
+    LLVM_DEBUG(dbgs() << "CycleSink:   Analysing use: " << MI);
+    if (!Cycle->contains(MI.getParent())) {
+      LLVM_DEBUG(dbgs() << "CycleSink:   Use not in cycle, can't sink.\n");
       CanSink = false;
       break;
     }
 
     // FIXME: Come up with a proper cost model that estimates whether sinking
-    // the instruction (and thus possibly executing it on every loop
+    // the instruction (and thus possibly executing it on every cycle
     // iteration) is more expensive than a register.
     // For now assumes that copies are cheap and thus almost always worth it.
     if (!MI.isCopy()) {
-      LLVM_DEBUG(dbgs() << "LoopSink:   Use is not a copy\n");
+      LLVM_DEBUG(dbgs() << "CycleSink:   Use is not a copy\n");
       CanSink = false;
       break;
     }
     if (!SinkBlock) {
       SinkBlock = MI.getParent();
-      LLVM_DEBUG(dbgs() << "LoopSink:   Setting sink block to: "
+      LLVM_DEBUG(dbgs() << "CycleSink:   Setting sink block to: "
                         << printMBBReference(*SinkBlock) << "\n");
       continue;
     }
     SinkBlock = DT->findNearestCommonDominator(SinkBlock, MI.getParent());
     if (!SinkBlock) {
-      LLVM_DEBUG(dbgs() << "LoopSink:   Can't find nearest dominator\n");
+      LLVM_DEBUG(dbgs() << "CycleSink:   Can't find nearest dominator\n");
       CanSink = false;
       break;
     }
-    LLVM_DEBUG(dbgs() << "LoopSink:   Setting nearest common dom block: " <<
+    LLVM_DEBUG(dbgs() << "CycleSink:   Setting nearest common dom block: " <<
                printMBBReference(*SinkBlock) << "\n");
   }
 
   if (!CanSink) {
-    LLVM_DEBUG(dbgs() << "LoopSink: Can't sink instruction.\n");
+    LLVM_DEBUG(dbgs() << "CycleSink: Can't sink instruction.\n");
     return false;
   }
   if (!SinkBlock) {
-    LLVM_DEBUG(dbgs() << "LoopSink: Not sinking, can't find sink block.\n");
+    LLVM_DEBUG(dbgs() << "CycleSink: Not sinking, can't find sink block.\n");
     return false;
   }
   if (SinkBlock == Preheader) {
-    LLVM_DEBUG(dbgs() << "LoopSink: Not sinking, sink block is the preheader\n");
+    LLVM_DEBUG(
+        dbgs() << "CycleSink: Not sinking, sink block is the preheader\n");
     return false;
   }
   if (SinkBlock->size() > SinkLoadInstsPerBlockThreshold) {
-    LLVM_DEBUG(dbgs() << "LoopSink: Not Sinking, block too large to analyse.\n");
+    LLVM_DEBUG(
+        dbgs() << "CycleSink: Not Sinking, block too large to analyse.\n");
     return false;
   }
 
-  LLVM_DEBUG(dbgs() << "LoopSink: Sinking instruction!\n");
+  LLVM_DEBUG(dbgs() << "CycleSink: Sinking instruction!\n");
   SinkBlock->splice(SinkBlock->SkipPHIsAndLabels(SinkBlock->begin()), Preheader,
                     I);
 
   // The instruction is moved from its basic block, so do not retain the
   // debug information.
   assert(!I.isDebugInstr() && "Should not sink debug inst");
   I.setDebugLoc(DebugLoc());
   return true;
if (SuccToSinkTo->pred_size() > 1) {
 
     // We don't want to sink across a critical edge if we don't dominate the
     // successor. We could be introducing calculations to new code paths.
     if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) {
       LLVM_DEBUG(dbgs() << " *** NOTE: Critical edge found\n");
       TryBreak = true;
     }
 
-    // Don't sink instructions into a loop.
-    if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) {
-      LLVM_DEBUG(dbgs() << " *** NOTE: Loop header found\n");
+    // Don't sink instructions into a cycle.
+    if (!TryBreak && CI->getCycle(SuccToSinkTo) &&
+        (!CI->getCycle(SuccToSinkTo)->isReducible() ||
+         CI->getCycle(SuccToSinkTo)->getHeader() == SuccToSinkTo)) {
+      LLVM_DEBUG(dbgs() << " *** NOTE: cycle header found\n");
       TryBreak = true;
     }
 
     // Otherwise we are OK with sinking along a critical edge.
     if (!TryBreak)
       LLVM_DEBUG(dbgs() << "Sinking along critical edge.\n");
     else {
       // Mark this edge as to be split.

llvm/test/CodeGen/AArch64/O3-pipeline.ll

 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Machine Natural Loop Construction
 ; CHECK-NEXT:       Machine Block Frequency Analysis
 ; CHECK-NEXT:       Early Machine Loop Invariant Code Motion
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Common Subexpression Elimination
 ; CHECK-NEXT:       MachinePostDominator Tree Construction
+; CHECK-NEXT:       Machine Cycle Info Analysis
 ; CHECK-NEXT:       Machine code sinking
 ; CHECK-NEXT:       Peephole Optimizations
 ; CHECK-NEXT:       Remove dead machine instructions
 ; CHECK-NEXT:       AArch64 MI Peephole Optimization pass
 ; CHECK-NEXT:       AArch64 Dead register definitions
 ; CHECK-NEXT:       Detect Dead Lanes
 ; CHECK-NEXT:       Process Implicit Definitions
 ; CHECK-NEXT:       Remove unreachable machine basic blocks

llvm/test/CodeGen/AArch64/loop-sink-limit.mir

 # NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
 # RUN: llc -mtriple aarch64 -run-pass=machine-sink -sink-insts-to-avoid-spills \
-# RUN:   -machine-sink-loop-limit=1 -verify-machineinstrs %s -o - 2>&1 | \
+# RUN:   -machine-sink-cycle-limit=1 -verify-machineinstrs %s -o - 2>&1 | \
 # RUN:   FileCheck %s --check-prefix=SINK1
 #
 # RUN: llc -mtriple aarch64 -run-pass=machine-sink -sink-insts-to-avoid-spills \
-# RUN:   -machine-sink-loop-limit=2 -verify-machineinstrs %s -o - 2>&1 | \
+# RUN:   -machine-sink-cycle-limit=2 -verify-machineinstrs %s -o - 2>&1 | \
 # RUN:   FileCheck %s --check-prefix=SINK2
 
 --- |
   target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
   target triple = "aarch64"
 
   @A = external dso_local global [100 x i32], align 4
   %struct.A = type { i32, i32, i32, i32, i32, i32 }

llvm/test/CodeGen/AMDGPU/llc-pipeline.ll

 ; GCN-O1-NEXT:        MachineDominator Tree Construction
 ; GCN-O1-NEXT:        Machine Natural Loop Construction
 ; GCN-O1-NEXT:        Machine Block Frequency Analysis
 ; GCN-O1-NEXT:        Early Machine Loop Invariant Code Motion
 ; GCN-O1-NEXT:        MachineDominator Tree Construction
 ; GCN-O1-NEXT:        Machine Block Frequency Analysis
 ; GCN-O1-NEXT:        Machine Common Subexpression Elimination
 ; GCN-O1-NEXT:        MachinePostDominator Tree Construction
+; GCN-O1-NEXT:        Machine Cycle Info Analysis
 ; GCN-O1-NEXT:        Machine code sinking
 ; GCN-O1-NEXT:        Peephole Optimizations
 ; GCN-O1-NEXT:        Remove dead machine instructions
 ; GCN-O1-NEXT:        SI Fold Operands
 ; GCN-O1-NEXT:        GCN DPP Combine
 ; GCN-O1-NEXT:        SI Load Store Optimizer
 ; GCN-O1-NEXT:        Remove dead machine instructions
 ; GCN-O1-NEXT:        SI Shrink Instructions

 ; GCN-O1-OPTS-NEXT:        MachineDominator Tree Construction
 ; GCN-O1-OPTS-NEXT:        Machine Natural Loop Construction
 ; GCN-O1-OPTS-NEXT:        Machine Block Frequency Analysis
 ; GCN-O1-OPTS-NEXT:        Early Machine Loop Invariant Code Motion
 ; GCN-O1-OPTS-NEXT:        MachineDominator Tree Construction
 ; GCN-O1-OPTS-NEXT:        Machine Block Frequency Analysis
 ; GCN-O1-OPTS-NEXT:        Machine Common Subexpression Elimination
 ; GCN-O1-OPTS-NEXT:        MachinePostDominator Tree Construction
+; GCN-O1-OPTS-NEXT:        Machine Cycle Info Analysis
 ; GCN-O1-OPTS-NEXT:        Machine code sinking
 ; GCN-O1-OPTS-NEXT:        Peephole Optimizations
 ; GCN-O1-OPTS-NEXT:        Remove dead machine instructions
 ; GCN-O1-OPTS-NEXT:        SI Fold Operands
 ; GCN-O1-OPTS-NEXT:        GCN DPP Combine
 ; GCN-O1-OPTS-NEXT:        SI Load Store Optimizer
 ; GCN-O1-OPTS-NEXT:        SI Peephole SDWA
 ; GCN-O1-OPTS-NEXT:        Machine Block Frequency Analysis

 ; GCN-O2-NEXT:        MachineDominator Tree Construction
 ; GCN-O2-NEXT:        Machine Natural Loop Construction
 ; GCN-O2-NEXT:        Machine Block Frequency Analysis
 ; GCN-O2-NEXT:        Early Machine Loop Invariant Code Motion
 ; GCN-O2-NEXT:        MachineDominator Tree Construction
 ; GCN-O2-NEXT:        Machine Block Frequency Analysis
 ; GCN-O2-NEXT:        Machine Common Subexpression Elimination
 ; GCN-O2-NEXT:        MachinePostDominator Tree Construction
+; GCN-O2-NEXT:        Machine Cycle Info Analysis
 ; GCN-O2-NEXT:        Machine code sinking
 ; GCN-O2-NEXT:        Peephole Optimizations
 ; GCN-O2-NEXT:        Remove dead machine instructions
 ; GCN-O2-NEXT:        SI Fold Operands
 ; GCN-O2-NEXT:        GCN DPP Combine
 ; GCN-O2-NEXT:        SI Load Store Optimizer
 ; GCN-O2-NEXT:        SI Peephole SDWA
 ; GCN-O2-NEXT:        Machine Block Frequency Analysis

 ; GCN-O3-NEXT:        MachineDominator Tree Construction
 ; GCN-O3-NEXT:        Machine Natural Loop Construction
 ; GCN-O3-NEXT:        Machine Block Frequency Analysis
 ; GCN-O3-NEXT:        Early Machine Loop Invariant Code Motion
 ; GCN-O3-NEXT:        MachineDominator Tree Construction
 ; GCN-O3-NEXT:        Machine Block Frequency Analysis
 ; GCN-O3-NEXT:        Machine Common Subexpression Elimination
 ; GCN-O3-NEXT:        MachinePostDominator Tree Construction
+; GCN-O3-NEXT:        Machine Cycle Info Analysis
 ; GCN-O3-NEXT:        Machine code sinking
 ; GCN-O3-NEXT:        Peephole Optimizations
 ; GCN-O3-NEXT:        Remove dead machine instructions
 ; GCN-O3-NEXT:        SI Fold Operands
 ; GCN-O3-NEXT:        GCN DPP Combine
 ; GCN-O3-NEXT:        SI Load Store Optimizer
 ; GCN-O3-NEXT:        SI Peephole SDWA
 ; GCN-O3-NEXT:        Machine Block Frequency Analysis

llvm/test/CodeGen/ARM/O3-pipeline.ll

 ; CHECK-NEXT:      MachineDominator Tree Construction
 ; CHECK-NEXT:      Machine Natural Loop Construction
 ; CHECK-NEXT:      Machine Block Frequency Analysis
 ; CHECK-NEXT:      Early Machine Loop Invariant Code Motion
 ; CHECK-NEXT:      MachineDominator Tree Construction
 ; CHECK-NEXT:      Machine Block Frequency Analysis
 ; CHECK-NEXT:      Machine Common Subexpression Elimination
 ; CHECK-NEXT:      MachinePostDominator Tree Construction
+; CHECK-NEXT:      Machine Cycle Info Analysis
 ; CHECK-NEXT:      Machine code sinking
 ; CHECK-NEXT:      Peephole Optimizations
 ; CHECK-NEXT:      Remove dead machine instructions
 ; CHECK-NEXT:      MachineDominator Tree Construction
 ; CHECK-NEXT:      Slot index numbering
 ; CHECK-NEXT:      Live Interval Analysis
 ; CHECK-NEXT:      Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:      Machine Optimization Remark Emitter

llvm/test/CodeGen/PowerPC/O3-pipeline.ll

 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine InstCombiner
 ; CHECK-NEXT:       Machine Block Frequency Analysis
 ; CHECK-NEXT:       Early Machine Loop Invariant Code Motion
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Common Subexpression Elimination
 ; CHECK-NEXT:       MachinePostDominator Tree Construction
+; CHECK-NEXT:       Machine Cycle Info Analysis
 ; CHECK-NEXT:       Machine code sinking
 ; CHECK-NEXT:       Peephole Optimizations
 ; CHECK-NEXT:       Remove dead machine instructions
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       PowerPC Reduce CR logical Operation
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       MachinePostDominator Tree Construction
 ; CHECK-NEXT:       Machine Natural Loop Construction

llvm/test/CodeGen/RISCV/O3-pipeline.ll

 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Machine Natural Loop Construction
 ; CHECK-NEXT:       Machine Block Frequency Analysis
 ; CHECK-NEXT:       Early Machine Loop Invariant Code Motion
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Common Subexpression Elimination
 ; CHECK-NEXT:       MachinePostDominator Tree Construction
+; CHECK-NEXT:       Machine Cycle Info Analysis
 ; CHECK-NEXT:       Machine code sinking
 ; CHECK-NEXT:       Peephole Optimizations
 ; CHECK-NEXT:       Remove dead machine instructions
 ; RV64-NEXT:        RISCV sext.w Removal
 ; CHECK-NEXT:       RISCV Merge Base Offset
 ; CHECK-NEXT:       RISCV Insert VSETVLI pass
 ; CHECK-NEXT:       Detect Dead Lanes
 ; CHECK-NEXT:       Process Implicit Definitions

llvm/test/CodeGen/X86/opt-pipeline.ll

 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Machine Natural Loop Construction
 ; CHECK-NEXT:       Machine Block Frequency Analysis
 ; CHECK-NEXT:       Early Machine Loop Invariant Code Motion
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Common Subexpression Elimination
 ; CHECK-NEXT:       MachinePostDominator Tree Construction
+; CHECK-NEXT:       Machine Cycle Info Analysis
 ; CHECK-NEXT:       Machine code sinking
 ; CHECK-NEXT:       Peephole Optimizations
 ; CHECK-NEXT:       Remove dead machine instructions
 ; CHECK-NEXT:       Live Range Shrink
 ; CHECK-NEXT:       X86 Fixup SetCC
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       X86 LEA Optimize
 ; CHECK-NEXT:       X86 Optimize Call Frame

llvm/test/CodeGen/X86/pr38795.ll

 ; CHECK-NEXT:    # implicit-def: $ecx
 ; CHECK-NEXT:    # implicit-def: $edi
 ; CHECK-NEXT:    # implicit-def: $al
 ; CHECK-NEXT:    # kill: killed $al
 ; CHECK-NEXT:    # implicit-def: $dl
 ; CHECK-NEXT:    # implicit-def: $ebp
 ; CHECK-NEXT:    jmp .LBB0_1
 ; CHECK-NEXT:    .p2align 4, 0x90
-; CHECK-NEXT:  .LBB0_15: # %for.inc
+; CHECK-NEXT:  .LBB0_16: # %for.inc
 ; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
-; CHECK-NEXT:    movl %esi, %ecx
 ; CHECK-NEXT:    movb %dl, {{[-0-9]+}}(%e{{[sb]}}p) # 1-byte Spill
 ; CHECK-NEXT:    movb %dh, %dl
 ; CHECK-NEXT:  .LBB0_1: # %for.cond
 ; CHECK-NEXT:    # =>This Loop Header: Depth=1
-; CHECK-NEXT:    # Child Loop BB0_19 Depth 2
+; CHECK-NEXT:    # Child Loop BB0_20 Depth 2
 ; CHECK-NEXT:    cmpb $8, %dl
 ; CHECK-NEXT:    movb %dl, {{[-0-9]+}}(%e{{[sb]}}p) # 1-byte Spill
 ; CHECK-NEXT:    ja .LBB0_3
 ; CHECK-NEXT:  # %bb.2: # %for.cond
 ; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
 ; CHECK-NEXT:    testb %bl, %bl
 ; CHECK-NEXT:    je .LBB0_3
 ; CHECK-NEXT:  # %bb.4: # %if.end
 ; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
 ; CHECK-NEXT:    movl %ecx, %eax
 ; CHECK-NEXT:    cltd
 ; CHECK-NEXT:    idivl a
 ; CHECK-NEXT:    movb {{[-0-9]+}}(%e{{[sb]}}p), %dl # 1-byte Reload
 ; CHECK-NEXT:    movb %cl, %dh
 ; CHECK-NEXT:    movl $0, h
 ; CHECK-NEXT:    cmpb $8, %dl
-; CHECK-NEXT:    jg .LBB0_9
+; CHECK-NEXT:    jg .LBB0_8
 ; CHECK-NEXT:  # %bb.5: # %if.then13
 ; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
 ; CHECK-NEXT:    movl %eax, %esi
 ; CHECK-NEXT:    movl $.str, (%esp)
 ; CHECK-NEXT:    movb %dh, {{[-0-9]+}}(%e{{[sb]}}p) # 1-byte Spill
 ; CHECK-NEXT:    calll printf
 ; CHECK-NEXT:    movb {{[-0-9]+}}(%e{{[sb]}}p), %dh # 1-byte Reload
 ; CHECK-NEXT:    testb %bl, %bl
+; CHECK-NEXT:    movl %esi, %ecx
 ; CHECK-NEXT:    # implicit-def: $eax
-; CHECK-NEXT:    movb {{[-0-9]+}}(%e{{[sb]}}p), %cl # 1-byte Reload
+; CHECK-NEXT:    movb {{[-0-9]+}}(%e{{[sb]}}p), %dl # 1-byte Reload
+; CHECK-NEXT:    movb %dl, {{[-0-9]+}}(%e{{[sb]}}p) # 1-byte Spill
 ; CHECK-NEXT:    movb %dh, %dl
-; CHECK-NEXT:    jne .LBB0_15
+; CHECK-NEXT:    jne .LBB0_16
 ; CHECK-NEXT:    jmp .LBB0_6
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  .LBB0_3: # %if.then
 ; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
 ; CHECK-NEXT:    movl $.str, (%esp)
 ; CHECK-NEXT:    calll printf
 ; CHECK-NEXT:    movb {{[-0-9]+}}(%e{{[sb]}}p), %dl # 1-byte Reload
 ; CHECK-NEXT:    # implicit-def: $eax
-; CHECK-NEXT:    movb {{[-0-9]+}}(%e{{[sb]}}p), %cl # 1-byte Reload
-; CHECK-NEXT:    jmp .LBB0_6
-; CHECK-NEXT:    .p2align 4, 0x90
-; CHECK-NEXT:  .LBB0_9: # %if.end21
-; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
-; CHECK-NEXT:    # implicit-def: $ebp
-; CHECK-NEXT:    jmp .LBB0_10
-; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  .LBB0_6: # %for.cond35
 ; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
-; CHECK-NEXT:    movb %dl, %dh
 ; CHECK-NEXT:    testl %edi, %edi
-; CHECK-NEXT:    movl %edi, %esi
-; CHECK-NEXT:    movl $0, %edi
-; CHECK-NEXT:    movb %cl, %dl
-; CHECK-NEXT:    je .LBB0_19
-; CHECK-NEXT:  # %bb.7: # %af
+; CHECK-NEXT:    je .LBB0_7
+; CHECK-NEXT:  .LBB0_11: # %af
 ; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
 ; CHECK-NEXT:    testb %bl, %bl
-; CHECK-NEXT:    jne .LBB0_8
-; CHECK-NEXT:  .LBB0_16: # %if.end39
+; CHECK-NEXT:    jne .LBB0_12
+; CHECK-NEXT:  .LBB0_17: # %if.end39
 ; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
 ; CHECK-NEXT:    testl %eax, %eax
-; CHECK-NEXT:    je .LBB0_18
-; CHECK-NEXT:  # %bb.17: # %if.then41
+; CHECK-NEXT:    je .LBB0_19
+; CHECK-NEXT:  # %bb.18: # %if.then41
 ; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
 ; CHECK-NEXT:    movl $0, {{[0-9]+}}(%esp)
 ; CHECK-NEXT:    movl $fn, {{[0-9]+}}(%esp)
 ; CHECK-NEXT:    movl $.str, (%esp)
 ; CHECK-NEXT:    calll printf
-; CHECK-NEXT:  .LBB0_18: # %for.end46
+; CHECK-NEXT:  .LBB0_19: # %for.end46
 ; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
-; CHECK-NEXT:    movl %esi, %edi
 ; CHECK-NEXT:    # implicit-def: $dl
 ; CHECK-NEXT:    # implicit-def: $dh
 ; CHECK-NEXT:    # implicit-def: $ebp
+; CHECK-NEXT:    jmp .LBB0_20
+; CHECK-NEXT:    .p2align 4, 0x90
+; CHECK-NEXT:  .LBB0_8: # %if.end21
+; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
+; CHECK-NEXT:    # implicit-def: $ebp
+; CHECK-NEXT:    jmp .LBB0_9
 ; CHECK-NEXT:    .p2align 4, 0x90
-; CHECK-NEXT:  .LBB0_19: # %for.cond47
+; CHECK-NEXT:  .LBB0_7: # in Loop: Header=BB0_1 Depth=1
+; CHECK-NEXT:    xorl %edi, %edi
+; CHECK-NEXT:    movb %dl, %dh
+; CHECK-NEXT:    movb {{[-0-9]+}}(%e{{[sb]}}p), %dl # 1-byte Reload
+; CHECK-NEXT:    .p2align 4, 0x90
+; CHECK-NEXT:  .LBB0_20: # %for.cond47
 ; CHECK-NEXT:    # Parent Loop BB0_1 Depth=1
 ; CHECK-NEXT:    # => This Inner Loop Header: Depth=2
 ; CHECK-NEXT:    testb %bl, %bl
-; CHECK-NEXT:    jne .LBB0_19
-; CHECK-NEXT:  # %bb.20: # %for.cond47
-; CHECK-NEXT:    # in Loop: Header=BB0_19 Depth=2
+; CHECK-NEXT:    jne .LBB0_20
+; CHECK-NEXT:  # %bb.21: # %for.cond47
+; CHECK-NEXT:    # in Loop: Header=BB0_20 Depth=2
 ; CHECK-NEXT:    testb %bl, %bl
-; CHECK-NEXT:    jne .LBB0_19
-; CHECK-NEXT:  .LBB0_10: # %ae
+; CHECK-NEXT:    jne .LBB0_20
+; CHECK-NEXT:  .LBB0_9: # %ae
 ; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
 ; CHECK-NEXT:    testb %bl, %bl
-; CHECK-NEXT:    jne .LBB0_11
-; CHECK-NEXT:  # %bb.12: # %if.end26
+; CHECK-NEXT:    jne .LBB0_10
+; CHECK-NEXT:  # %bb.13: # %if.end26
 ; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
-; CHECK-NEXT:    xorl %esi, %esi
+; CHECK-NEXT:    xorl %ecx, %ecx
 ; CHECK-NEXT:    testb %dl, %dl
-; CHECK-NEXT:    je .LBB0_15
-; CHECK-NEXT:  # %bb.13: # %if.end26
+; CHECK-NEXT:    je .LBB0_16
+; CHECK-NEXT:  # %bb.14: # %if.end26
 ; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
 ; CHECK-NEXT:    testl %ebp, %ebp
-; CHECK-NEXT:    jne .LBB0_15
-; CHECK-NEXT:  # %bb.14: # %if.then31
+; CHECK-NEXT:    jne .LBB0_16
+; CHECK-NEXT:  # %bb.15: # %if.then31
 ; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
-; CHECK-NEXT:    xorl %esi, %esi
+; CHECK-NEXT:    xorl %ecx, %ecx
 ; CHECK-NEXT:    xorl %ebp, %ebp
-; CHECK-NEXT:    jmp .LBB0_15
+; CHECK-NEXT:    jmp .LBB0_16
 ; CHECK-NEXT:    .p2align 4, 0x90
-; CHECK-NEXT:  .LBB0_11: # in Loop: Header=BB0_1 Depth=1
-; CHECK-NEXT:    movl %edi, %esi
+; CHECK-NEXT:  .LBB0_10: # in Loop: Header=BB0_1 Depth=1
 ; CHECK-NEXT:    # implicit-def: $eax
 ; CHECK-NEXT:    testb %bl, %bl
-; CHECK-NEXT:    je .LBB0_16
-; CHECK-NEXT:  .LBB0_8: # in Loop: Header=BB0_1 Depth=1
+; CHECK-NEXT:    je .LBB0_17
+; CHECK-NEXT:  .LBB0_12: # in Loop: Header=BB0_1 Depth=1
 ; CHECK-NEXT:    # implicit-def: $edi
 ; CHECK-NEXT:    # implicit-def: $cl
+; CHECK-NEXT:    # kill: killed $cl
 ; CHECK-NEXT:    # implicit-def: $dl
 ; CHECK-NEXT:    # implicit-def: $ebp
-; CHECK-NEXT:    jmp .LBB0_6
+; CHECK-NEXT:    testl %edi, %edi
+; CHECK-NEXT:    jne .LBB0_11
+; CHECK-NEXT:    jmp .LBB0_7
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %entry
   %l.0 = phi i16 [ undef, %entry ], [ 0, %for.inc ]
   %m.0 = phi i32 [ undef, %entry ], [ %m.2, %for.inc ]
   %i.0 = phi i32 [ undef, %entry ], [ %i.2, %for.inc ]
   %p.0 = phi i8 [ undef, %entry ], [ %p.2, %for.inc ]

llvm/test/CodeGen/X86/switch-phi-const.ll

 
 @g64 = global i64 0
 @effect64 = global i64 0
 
 define void @switch_trunc_phi_const(i32 %x) {
 ; CHECK-LABEL: switch_trunc_phi_const:
 ; CHECK:       # %bb.0: # %bb0
 ; CHECK-NEXT:    movzbl %dil, %r8d
-; CHECK-NEXT:    movl $3895, %ecx # imm = 0xF37
-; CHECK-NEXT:    movl $42, %esi
-; CHECK-NEXT:    movl $13, %edx
-; CHECK-NEXT:    movl $5, %edi
-; CHECK-NEXT:    movl $1, %eax
 ; CHECK-NEXT:    decl %r8d
 ; CHECK-NEXT:    cmpl $54, %r8d
 ; CHECK-NEXT:    ja .LBB1_8
 ; CHECK-NEXT:  # %bb.1: # %bb0
+; CHECK-NEXT:    movl $3895, %edx # imm = 0xF37
+; CHECK-NEXT:    movl $42, %edi
+; CHECK-NEXT:    movl $13, %esi
+; CHECK-NEXT:    movl $5, %ecx
+; CHECK-NEXT:    movl $1, %eax
 ; CHECK-NEXT:    jmpq *.LJTI1_0(,%r8,8)
 ; CHECK-NEXT:  .LBB1_8: # %default
 ; CHECK-NEXT:    retq
 ; CHECK-NEXT:  .LBB1_2: # %case_1_loop
 ; CHECK-NEXT:    movq effect64@GOTPCREL(%rip), %rcx
 ; CHECK-NEXT:    movq $1, (%rcx)
-; CHECK-NEXT:    movq %rax, %rdi
+; CHECK-NEXT:    movq %rax, %rcx
 ; CHECK-NEXT:  .LBB1_3: # %case_5
 ; CHECK-NEXT:    movq effect64@GOTPCREL(%rip), %rax
 ; CHECK-NEXT:    movq $5, (%rax)
-; CHECK-NEXT:    movq %rdi, %rdx
+; CHECK-NEXT:    movq %rcx, %rsi
 ; CHECK-NEXT:  .LBB1_4: # %case_13
 ; CHECK-NEXT:    movq effect64@GOTPCREL(%rip), %rax
 ; CHECK-NEXT:    movq $13, (%rax)
-; CHECK-NEXT:    movq %rdx, %rsi
+; CHECK-NEXT:    movq %rsi, %rdi
 ; CHECK-NEXT:  .LBB1_5: # %case_42
 ; CHECK-NEXT:    movq effect64@GOTPCREL(%rip), %rax
-; CHECK-NEXT:    movq %rsi, (%rax)
-; CHECK-NEXT:    movl $55, %ecx
+; CHECK-NEXT:    movq %rdi, (%rax)
+; CHECK-NEXT:    movl $55, %edx
 ; CHECK-NEXT:  .LBB1_6: # %case_55
 ; CHECK-NEXT:    movq effect64@GOTPCREL(%rip), %rax
-; CHECK-NEXT:    movq %rcx, (%rax)
+; CHECK-NEXT:    movq %rdx, (%rax)
 ; CHECK-NEXT:  .LBB1_7: # %case_7
 ; CHECK-NEXT:    movq g64@GOTPCREL(%rip), %rax
 ; CHECK-NEXT:    movq (%rax), %rax
 ; CHECK-NEXT:    movq effect64@GOTPCREL(%rip), %rcx
 ; CHECK-NEXT:    movq $7, (%rcx)
 ; CHECK-NEXT:    jmp .LBB1_2
 bb0:
   %x_trunc = trunc i32 %x to i8

llvm/test/CodeGen/X86/x86-shrink-wrapping.ll

 ; ENABLE-NEXT:    pushq %rbp
 ; ENABLE-NEXT:    .cfi_def_cfa_offset 16
 ; ENABLE-NEXT:    .cfi_offset %rbp, -16
 ; ENABLE-NEXT:    movq %rsp, %rbp
 ; ENABLE-NEXT:    .cfi_def_cfa_register %rbp
 ; ENABLE-NEXT:    pushq %rbx
 ; ENABLE-NEXT:    pushq %rax
 ; ENABLE-NEXT:    .cfi_offset %rbx, -24
-; ENABLE-NEXT:    movq _irreducibleCFGa@GOTPCREL(%rip), %rax
-; ENABLE-NEXT:    movl (%rax), %edi
 ; ENABLE-NEXT:    movq _irreducibleCFGf@GOTPCREL(%rip), %rax
 ; ENABLE-NEXT:    cmpb $0, (%rax)
 ; ENABLE-NEXT:    je LBB16_2
 ; ENABLE-NEXT:    .p2align 4, 0x90
 ; ENABLE-NEXT:  LBB16_1: ## %preheader
 ; ENABLE-NEXT:    ## =>This Inner Loop Header: Depth=1
 ; ENABLE-NEXT:    jmp LBB16_1
 ; ENABLE-NEXT:  LBB16_2: ## %split
 ; ENABLE-NEXT:    movq _irreducibleCFGb@GOTPCREL(%rip), %rax
-; ENABLE-NEXT:    xorl %ebx, %ebx
 ; ENABLE-NEXT:    cmpl $0, (%rax)
-; ENABLE-NEXT:    je LBB16_4
-; ENABLE-NEXT:  ## %bb.3: ## %for.body4.i
+; ENABLE-NEXT:    je LBB16_3
+; ENABLE-NEXT:  ## %bb.4: ## %for.body4.i
+; ENABLE-NEXT:    movq _irreducibleCFGa@GOTPCREL(%rip), %rax
+; ENABLE-NEXT:    movl (%rax), %edi
 ; ENABLE-NEXT:    xorl %ebx, %ebx
 ; ENABLE-NEXT:    xorl %eax, %eax
 ; ENABLE-NEXT:    callq _something
+; ENABLE-NEXT:    jmp LBB16_5
+; ENABLE-NEXT:  LBB16_3:
+; ENABLE-NEXT:    xorl %ebx, %ebx
 ; ENABLE-NEXT:    .p2align 4, 0x90
-; ENABLE-NEXT:  LBB16_4: ## %for.inc
+; ENABLE-NEXT:  LBB16_5: ## %for.inc
 ; ENABLE-NEXT:    ## =>This Inner Loop Header: Depth=1
 ; ENABLE-NEXT:    incl %ebx
 ; ENABLE-NEXT:    cmpl $7, %ebx
-; ENABLE-NEXT:    jl LBB16_4
-; ENABLE-NEXT:  ## %bb.5: ## %fn1.exit
+; ENABLE-NEXT:    jl LBB16_5
+; ENABLE-NEXT:  ## %bb.6: ## %fn1.exit
 ; ENABLE-NEXT:    xorl %eax, %eax
 ; ENABLE-NEXT:    addq $8, %rsp
 ; ENABLE-NEXT:    popq %rbx
 ; ENABLE-NEXT:    popq %rbp
 ; ENABLE-NEXT:    retq
 ;
 ; DISABLE-LABEL: irreducibleCFG:
 ; DISABLE:       ## %bb.0: ## %entry
 ; DISABLE-NEXT:    pushq %rbp
 ; DISABLE-NEXT:    .cfi_def_cfa_offset 16
 ; DISABLE-NEXT:    .cfi_offset %rbp, -16
 ; DISABLE-NEXT:    movq %rsp, %rbp
 ; DISABLE-NEXT:    .cfi_def_cfa_register %rbp
 ; DISABLE-NEXT:    pushq %rbx
 ; DISABLE-NEXT:    pushq %rax
 ; DISABLE-NEXT:    .cfi_offset %rbx, -24
-; DISABLE-NEXT:    movq _irreducibleCFGa@GOTPCREL(%rip), %rax
-; DISABLE-NEXT:    movl (%rax), %edi
 ; DISABLE-NEXT:    movq _irreducibleCFGf@GOTPCREL(%rip), %rax
 ; DISABLE-NEXT:    cmpb $0, (%rax)
 ; DISABLE-NEXT:    je LBB16_2
 ; DISABLE-NEXT:    .p2align 4, 0x90
 ; DISABLE-NEXT:  LBB16_1: ## %preheader
 ; DISABLE-NEXT:    ## =>This Inner Loop Header: Depth=1
 ; DISABLE-NEXT:    jmp LBB16_1
 ; DISABLE-NEXT:  LBB16_2: ## %split
 ; DISABLE-NEXT:    movq _irreducibleCFGb@GOTPCREL(%rip), %rax
-; DISABLE-NEXT:    xorl %ebx, %ebx
 ; DISABLE-NEXT:    cmpl $0, (%rax)
-; DISABLE-NEXT:    je LBB16_4
-; DISABLE-NEXT:  ## %bb.3: ## %for.body4.i
+; DISABLE-NEXT:    je LBB16_3
+; DISABLE-NEXT:  ## %bb.4: ## %for.body4.i
+; DISABLE-NEXT:    movq _irreducibleCFGa@GOTPCREL(%rip), %rax
+; DISABLE-NEXT:    movl (%rax), %edi
 ; DISABLE-NEXT:    xorl %ebx, %ebx
 ; DISABLE-NEXT:    xorl %eax, %eax
 ; DISABLE-NEXT:    callq _something
+; DISABLE-NEXT:    jmp LBB16_5
+; DISABLE-NEXT:  LBB16_3:
+; DISABLE-NEXT:    xorl %ebx, %ebx
 ; DISABLE-NEXT:    .p2align 4, 0x90
-; DISABLE-NEXT:  LBB16_4: ## %for.inc
+; DISABLE-NEXT:  LBB16_5: ## %for.inc
 ; DISABLE-NEXT:    ## =>This Inner Loop Header: Depth=1
 ; DISABLE-NEXT:    incl %ebx
 ; DISABLE-NEXT:    cmpl $7, %ebx
-; DISABLE-NEXT:    jl LBB16_4
-; DISABLE-NEXT:  ## %bb.5: ## %fn1.exit
+; DISABLE-NEXT:    jl LBB16_5
+; DISABLE-NEXT:  ## %bb.6: ## %fn1.exit
 ; DISABLE-NEXT:    xorl %eax, %eax
 ; DISABLE-NEXT:    addq $8, %rsp
 ; DISABLE-NEXT:    popq %rbx
 ; DISABLE-NEXT:    popq %rbp
 ; DISABLE-NEXT:    retq
 entry:
   %i0 = load i32, i32* @irreducibleCFGa, align 4
   %.pr = load i8, i8* @irreducibleCFGf, align 1