Index: llvm/trunk/include/llvm/Analysis/AliasSetTracker.h
===================================================================
--- llvm/trunk/include/llvm/Analysis/AliasSetTracker.h
+++ llvm/trunk/include/llvm/Analysis/AliasSetTracker.h
@@ -224,6 +224,20 @@
   // track of the list's exact size.
   unsigned size() { return SetSize; }
 
+  /// If this alias set is known to contain a single instruction and *only* a
+  /// single unique instruction, return it.  Otherwise, return nullptr.
+  Instruction* getUniqueInstruction() {
+    if (size() != 0)
+      // Can't track source of pointer, might be many instruction
+      return nullptr;
+    if (AliasAny)
+      // May have collapses alias set
+      return nullptr;
+    if (1 != UnknownInsts.size())
+      return nullptr;
+    return cast<Instruction>(UnknownInsts[0]);
+  }
+
   void print(raw_ostream &OS) const;
   void dump() const;
 
Index: llvm/trunk/lib/Transforms/Scalar/LICM.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Scalar/LICM.cpp
+++ llvm/trunk/lib/Transforms/Scalar/LICM.cpp
@@ -582,6 +582,7 @@
 bool isHoistableAndSinkableInst(Instruction &I) {
   // Only these instructions are hoistable/sinkable.
   return (isa<LoadInst>(I) || isa<CallInst>(I) ||
+          isa<FenceInst>(I) ||
           isa<BinaryOperator>(I) || isa<CastInst>(I) ||
           isa<SelectInst>(I) || isa<GetElementPtrInst>(I) ||
           isa<CmpInst>(I) || isa<InsertElementInst>(I) ||
@@ -684,6 +685,20 @@
     // sink the call.
 
     return false;
+  } else if (auto *FI = dyn_cast<FenceInst>(&I)) {
+    // Fences alias (most) everything to provide ordering.  For the moment,
+    // just give up if there are any other memory operations in the loop.
+    auto Begin = CurAST->begin();
+    assert(Begin != CurAST->end() && "must contain FI");
+    if (std::next(Begin) != CurAST->end())
+      // constant memory for instance, TODO: handle better
+      return false;
+    auto *UniqueI = Begin->getUniqueInstruction();
+    if (!UniqueI)
+      // other memory op, give up
+      return false;
+    assert(UniqueI == FI && "AS must contain FI");
+    return true;
   }
 
   assert(!I.mayReadOrWriteMemory() && "unhandled aliasing");
Index: llvm/trunk/test/Transforms/LICM/fence.ll
===================================================================
--- llvm/trunk/test/Transforms/LICM/fence.ll
+++ llvm/trunk/test/Transforms/LICM/fence.ll
@@ -3,8 +3,8 @@
 
 define void @test1(i64 %n) {
 ; CHECK-LABEL: @test1
-; CHECK-LABEL: loop:
 ; CHECK: fence
+; CHECK-LABEL: loop:
 entry:
   br label %loop
 loop:
@@ -19,8 +19,8 @@
 
 define void @test2(i64 %n) {
 ; CHECK-LABEL: @test2
-; CHECK-LABEL: loop:
 ; CHECK: fence
+; CHECK-LABEL: loop:
 entry:
   br label %loop
 loop:
@@ -35,8 +35,8 @@
 
 define void @test3(i64 %n) {
 ; CHECK-LABEL: @test3
-; CHECK-LABEL: loop:
 ; CHECK: fence
+; CHECK-LABEL: loop:
 entry:
   br label %loop
 loop:
@@ -51,8 +51,8 @@
 
 define void @test4(i64 %n) {
 ; CHECK-LABEL: @test4
-; CHECK-LABEL: loop:
 ; CHECK: fence
+; CHECK-LABEL: loop:
 entry:
   br label %loop
 loop:
@@ -99,8 +99,10 @@
   ret void
 }
 
-define void @testfp1(i64 %n, i64* %p) {
-; CHECK-LABEL: @testfp1
+; Note: While a false negative for LICM on it's own, O3 does get this
+; case by combining the fences.
+define void @testfn1(i64 %n, i64* %p) {
+; CHECK-LABEL: @testfn1
 ; CHECK-LABEL: loop:
 ; CHECK: fence
 entry: