Index: include/llvm/CodeGen/ScheduleDAGInstrs.h
===================================================================
--- include/llvm/CodeGen/ScheduleDAGInstrs.h
+++ include/llvm/CodeGen/ScheduleDAGInstrs.h
@@ -23,6 +23,7 @@
 #include "llvm/Support/Compiler.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include <list>
+#include <set>
 
 namespace llvm {
   class MachineFrameInfo;
@@ -162,6 +163,11 @@
     /// case of a huge region that gets reduced).
     SUnit *BarrierChain;
 
+    /// Cache results when getUnderlyingObjectsForInstr() returns no
+    /// objects, i.e. the memory accesses that are unanalyzable.
+    typedef std::set<MachineInstr *> MISet;
+    MISet UnsafeMemObjs;
+
   public:
 
     /// A list of SUnits, used in Value2SUsMap, during DAG construction.
@@ -180,6 +186,10 @@
     void reduceHugeMemNodeMaps(Value2SUsMap &stores,
                                Value2SUsMap &loads, unsigned N);
 
+    bool MIsNeedChainEdge(AliasAnalysis *AA, const MachineFrameInfo *MFI,
+                          const DataLayout &DL, MachineInstr *MIa,
+                          MachineInstr *MIb);
+
     /// Add a chain edge between SUa and SUb, but only if both AliasAnalysis
     /// and Target fail to deny the dependency.
     void addChainDependency(SUnit *SUa, SUnit *SUb,
Index: lib/CodeGen/ScheduleDAGInstrs.cpp
===================================================================
--- lib/CodeGen/ScheduleDAGInstrs.cpp
+++ lib/CodeGen/ScheduleDAGInstrs.cpp
@@ -159,6 +159,7 @@
                                          const MachineFrameInfo *MFI,
                                          UnderlyingObjectsVector &Objects,
                                          const DataLayout &DL) {
+  // FIXME: Need to handle multiple memory operands to support all targets.
   if (!MI->hasOneMemOperand() ||
       (!(*MI->memoperands_begin())->getValue() &&
        !(*MI->memoperands_begin())->getPseudoValue()) ||
@@ -549,39 +550,12 @@
          (MI->hasOrderedMemoryRef() && !MI->isInvariantLoad(AA));
 }
 
-// This MI might have either incomplete info, or known to be unsafe
-// to deal with (i.e. volatile object).
-static inline bool isUnsafeMemoryObject(MachineInstr *MI,
-                                        const MachineFrameInfo *MFI,
-                                        const DataLayout &DL) {
-  if (!MI || MI->memoperands_empty())
-    return true;
-  // We purposefully do no check for hasOneMemOperand() here
-  // in hope to trigger an assert downstream in order to
-  // finish implementation.
-  if ((*MI->memoperands_begin())->isVolatile() ||
-       MI->hasUnmodeledSideEffects())
-    return true;
-
-  if ((*MI->memoperands_begin())->getPseudoValue()) {
-    // Similarly to getUnderlyingObjectForInstr:
-    // For now, ignore PseudoSourceValues which may alias LLVM IR values
-    // because the code that uses this function has no way to cope with
-    // such aliases.
-    return true;
-  }
-
-  if ((*MI->memoperands_begin())->getValue() == nullptr)
-    return true;
-
-  return false;
-}
-
 /// This returns true if the two MIs need a chain edge between them.
 /// This is called on normal stores and loads.
-static bool MIsNeedChainEdge(AliasAnalysis *AA, const MachineFrameInfo *MFI,
-                             const DataLayout &DL, MachineInstr *MIa,
-                             MachineInstr *MIb) {
+bool ScheduleDAGInstrs::
+MIsNeedChainEdge(AliasAnalysis *AA, const MachineFrameInfo *MFI,
+                 const DataLayout &DL, MachineInstr *MIa,
+                 MachineInstr *MIb) {
   const MachineFunction *MF = MIa->getParent()->getParent();
   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
 
@@ -592,20 +566,16 @@
   if (TII->areMemAccessesTriviallyDisjoint(MIa, MIb, AA))
     return false;
 
-  // FIXME: Need to handle multiple memory operands to support all targets.
-  if (!MIa->hasOneMemOperand() || !MIb->hasOneMemOperand())
-    return true;
-
-  if (isUnsafeMemoryObject(MIa, MFI, DL) || isUnsafeMemoryObject(MIb, MFI, DL))
-    return true;
-
   // To this point analysis is generic. From here on we do need AA.
   if (!AA)
     return true;
 
+  // If getUnderlyingObjectsForInstr() failed, give up.
+  if (UnsafeMemObjs.count(MIa) || UnsafeMemObjs.count(MIb))
+    return true;
+
   MachineMemOperand *MMOa = *MIa->memoperands_begin();
   MachineMemOperand *MMOb = *MIb->memoperands_begin();
-
   if (!MMOa->getValue() || !MMOb->getValue())
     return true;
 
@@ -878,6 +848,7 @@
   AAForDep = UseAA ? AA : nullptr;
 
   BarrierChain = nullptr;
+  UnsafeMemObjs.clear();
 
   this->TrackLaneMasks = TrackLaneMasks;
   MISUnitMap.clear();
@@ -1027,7 +998,6 @@
       addBarrierChain(Loads);
       addBarrierChain(NonAliasStores);
       addBarrierChain(NonAliasLoads);
-
       continue;
     }
 
@@ -1042,9 +1012,12 @@
     // Find the underlying objects for MI. The Objs vector is either
     // empty, or filled with the Values of memory locations which this
     // SU depends on. An empty vector means the memory location is
-    // unknown, and may alias anything except NonAlias nodes.
+    // unknown, and may alias anything. Cache that result in
+    // the UnsafeMemObjs set.
     UnderlyingObjectsVector Objs;
     getUnderlyingObjectsForInstr(MI, MFI, Objs, MF.getDataLayout());
+    if (Objs.empty())
+      UnsafeMemObjs.insert(MI);
 
     if (MI->mayStore()) {
       if (Objs.empty()) {