Index: llvm/lib/CodeGen/MachineSink.cpp
===================================================================
--- llvm/lib/CodeGen/MachineSink.cpp
+++ llvm/lib/CodeGen/MachineSink.cpp
@@ -228,6 +228,11 @@
                                 SmallVector<MachineInstr *, 8> &Candidates);
     bool SinkIntoLoop(MachineInstr &I, MachineLoop *L,
                       MachineBasicBlock *Preheader);
+    bool IsSafeToMove(MachineInstr &I, MachineBasicBlock *SinkTo);
+    bool AreAliased(MachineInstr &First, MachineInstr &Second,
+                    MachineBasicBlock *From, MachineBasicBlock *To,
+                    DenseSet<MachineBasicBlock *> HandledDomBlocks,
+                    bool &SawStore, bool &HasAliasedStore) ;
 
     bool isProfitableToSinkTo(Register Reg, MachineInstr &MI,
                               MachineBasicBlock *MBB,
@@ -375,24 +380,17 @@
     SmallVector<MachineInstr *, 8> &Candidates) {
   for (auto &MI : *BB) {
     LLVM_DEBUG(dbgs() << "LoopSink: Analysing candidate: " << MI);
-    bool DontMoveAcrossStore = true;
-    if (!MI.isSafeToMove(AA, DontMoveAcrossStore))
-      continue;
-
     if (MI.mayLoad() && !mayLoadFromGOTOrConstantPool(MI) &&
         !IsGuaranteedToExecute(L, BB)) {
       LLVM_DEBUG(dbgs() << "LoopSink: Load not guaranteed to execute.\n");
       continue;
     }
-
     if (MI.isConvergent())
       continue;
-
     if (!L->isLoopInvariant(MI)) {
       LLVM_DEBUG(dbgs() << "LoopSink: Instruction not loop invariant\n");
       continue;
     }
-
     const MachineOperand &MO = MI.getOperand(0);
     if (!MO.isReg() || !MO.getReg() || !MO.isDef())
       continue;
@@ -453,6 +451,9 @@
     EverMadeChange = true;
   }
 
+  HasStoreCache.clear();
+  StoreInstrCache.clear();
+
   if (SinkInstsIntoLoop) {
     SmallVector<MachineLoop *, 8> Loops(LI->begin(), LI->end());
     for (auto *L : Loops) {
@@ -463,8 +464,14 @@
       }
       SmallVector<MachineInstr *, 8> Candidates;
       FindLoopSinkCandidates(L, Preheader, Candidates);
-      for (auto *I : Candidates)
+
+      // Walk the candidates in reverse order so that we start with the use
+      // of a def-use chain, if there is any.
+      // TODO: implement this in a better and don't rely on any ordering.
+      for (auto It = Candidates.rbegin(); It != Candidates.rend(); ++It) {
+        MachineInstr *I = *It;
         EverMadeChange |= SinkIntoLoop(*I, L, Preheader);
+      }
     }
   }
 
@@ -1145,29 +1152,10 @@
       }
 
       for (MachineInstr &I : *BB) {
-        // Treat as alias conservatively for a call or an ordered memory
-        // operation.
-        if (I.isCall() || I.hasOrderedMemoryRef()) {
-          for (auto *DomBB : HandledDomBlocks) {
-            if (DomBB != BB && DT->dominates(DomBB, BB))
-              HasStoreCache[std::make_pair(DomBB, To)] = true;
-            else if(DomBB != BB && DT->dominates(BB, DomBB))
-              HasStoreCache[std::make_pair(From, DomBB)] = true;
-          }
-          HasStoreCache[BlockPair] = true;
+        bool Aliased = AreAliased(I, MI, From, To, HandledBlocks, SawStore,
+                                  HasAliasedStore);
+        if (Aliased && (I.isCall() || I.hasOrderedMemoryRef()))
           return true;
-        }
-
-        if (I.mayStore()) {
-          SawStore = true;
-          // We still have chance to sink MI if all stores between are not
-          // aliased to MI.
-          // Cache all store instructions, so that we don't need to go through
-          // all From reachable blocks for next load instruction.
-          if (I.mayAlias(AA, MI, false))
-            HasAliasedStore = true;
-          StoreInstrCache[BlockPair].push_back(&I);
-        }
       }
     }
   }
@@ -1193,6 +1181,78 @@
   return true;
 }
 
+bool MachineSinking::AreAliased(MachineInstr &First, MachineInstr &Second,
+    MachineBasicBlock *From, MachineBasicBlock *To,
+    DenseSet<MachineBasicBlock *> HandledDomBlocks, bool &SawStore,
+    bool &HasAliasedStore) {
+  MachineBasicBlock *BB = First.getParent();
+  auto BlockPair = std::make_pair(From, To);
+
+  if (First.isCall() || Second.hasOrderedMemoryRef()) {
+    for (auto *DomBB : HandledDomBlocks) {
+      if (DomBB != BB && DT->dominates(DomBB, BB))
+        HasStoreCache[std::make_pair(DomBB, To)] = true;
+      else if(DomBB != BB && DT->dominates(BB, DomBB))
+        HasStoreCache[std::make_pair(From, DomBB)] = true;
+    }
+    HasStoreCache[BlockPair] = true;
+    return true;
+  }
+
+  if (First.mayStore()) {
+    SawStore = true;
+    // We still have chance to sink MI if all stores between are not
+    // aliased to MI.
+    // Cache all store instructions, so that we don't need to go through
+    // all From reachable blocks for next load instruction.
+    if (First.mayAlias(AA, Second, false))
+      HasAliasedStore = true;
+    StoreInstrCache[BlockPair].push_back(&First);
+  }
+
+  // If there is no store at all, cache the result.
+  if (!SawStore)
+    HasStoreCache[BlockPair] = false;
+  return HasAliasedStore;
+}
+
+bool MachineSinking::IsSafeToMove(MachineInstr &I, MachineBasicBlock *SinkTo) {
+  auto End = I.getParent()->instr_end();
+  auto It = I.getIterator();
+  bool SawStore = false;
+  bool HasAliasedStore = false;
+
+  // 1) First, analyse all instruction from the current instruction I to the end
+  // of its block
+  It++;
+  for (; It != End; ++It) {
+    if (AreAliased(*It, I, I.getParent(), SinkTo, {}, SawStore, HasAliasedStore)) {
+      LLVM_DEBUG(dbgs() << "LoopSink: Alias pair found:\n");
+      return false;
+    }
+  }
+
+  // 2) Check if we can move I to Sink, and see if there are any stores in
+  // between that are aliased.
+  bool DontMoveAcrossStore = hasStoreBetween(I.getParent(), SinkTo, I);
+  LLVM_DEBUG(dbgs() << "LoopSink: Found store in between: "
+                    << DontMoveAcrossStore << "\n");
+  if (!I.isSafeToMove(AA, DontMoveAcrossStore)) {
+    LLVM_DEBUG(dbgs() << "LoopSink: Not safe to move\n");
+    return false;
+  }
+
+  // 3) Check all instruction in the sink block, to see if they alias.
+  for (auto &CurI : *SinkTo) {
+    if (AreAliased(CurI, I, I.getParent(), SinkTo, {}, SawStore, HasAliasedStore)) {
+      LLVM_DEBUG(dbgs() << "LoopSink: Alias found in sink block:\n");
+      return false;
+    }
+  }
+
+  return true;
+}
+
 /// 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.
@@ -1242,6 +1302,12 @@
     LLVM_DEBUG(dbgs() << "LoopSink: Not sinking, sink block is the preheader\n");
     return false;
   }
+  if (!IsSafeToMove(I, SinkBlock)) {
+    LLVM_DEBUG(dbgs() << "LoopSink: Not safe to move\n");
+    return false;
+  }
+
+  LLVM_DEBUG(dbgs() << "LoopSink: Sinking instruction\n");
   SinkBlock->splice(SinkBlock->getFirstNonPHI(), Preheader, I);
   // The instruction is moved from its basic block, so do not retain the
   // debug information.