[LICM] hoist fences out of loops w/o memory operations

[reames]

Summary

The motivating case is an otherwise dead loop with a fence in it. At the moment, this goes all the way through the optimizer and we end up emitting an entirely pointless loop on x86. This case may seem a bit contrived, but we've seen it in real code as the result of otherwise reasonable lowering strategies combined w/thread local memory optimizations (such as escape analysis).

To handle this simple case, we can teach LICM to hoist must execute fences when there is no other memory operation within the loop.

[skatkov]

include/llvm/Analysis/AliasSetTracker.h

228

Please document that method may return nullptr if it cannot determine the unique instruction by any reason.

lib/Transforms/Scalar/LICM.cpp

696

Don't you want to assert that if Begin->getUniqueInstruction() != then it should be FI?

include/llvm/Analysis/AliasSetTracker.h

public:
   iterator begin() const { return iterator(PtrList); }
   iterator end()   const { return iterator(); }
   bool empty() const { return PtrList == nullptr; }
 
   // Unfortunately, ilist::size() is linear, so we have to add code to keep
   // 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.  
+  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;
 
   /// Define an iterator for alias sets... this is just a forward iterator.
   class iterator : public std::iterator<std::forward_iterator_tag,
                                         PointerRec, ptrdiff_t> {
     PointerRec *CurNode;
 

lib/Transforms/Scalar/LICM.cpp

 
 namespace {
 /// Return true if-and-only-if we know how to (mechanically) both hoist and
 /// sink a given instruction out of a loop.  Does not address legality
 /// concerns such as aliasing or speculation safety.  
 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) ||
           isa<ExtractElementInst>(I) || isa<ShuffleVectorInst>(I) ||
           isa<ExtractValueInst>(I) || isa<InsertValueInst>(I));
 }
 /// Return true if all of the alias sets within this AST are known not to
 /// contain a Mod.
if (AliasAnalysis::onlyReadsMemory(Behavior)) {
       if (isReadOnly(CurAST))
         return true;
     }
 
     // FIXME: This should use mod/ref information to see if we can hoist or
     // 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;
+    return Begin->getUniqueInstruction() == FI;
   }
 
   assert(!I.mayReadOrWriteMemory() && "unhandled aliasing");
 
   // We've established mechanical ability and aliasing, it's up to the caller
   // to check fault safety
   return true;
 }

test/Transforms/LICM/fence.ll

 ; RUN: opt -licm -basicaa < %s -S | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
 
 define void @test1(i64 %n) {
 ; CHECK-LABEL: @test1
-; CHECK-LABEL: loop:
 ; CHECK: fence
+; CHECK-LABEL: loop:
 entry:
   br label %loop
 loop:
   %iv = phi i64 [0, %entry], [%iv.next, %loop]
   fence release
   %iv.next = add i64 %iv, 1
   %test = icmp slt i64 %iv, %n
   br i1 %test, label %loop, label %exit
 exit:
   ret void
 }
 
 define void @test2(i64 %n) {
 ; CHECK-LABEL: @test2
-; CHECK-LABEL: loop:
 ; CHECK: fence
+; CHECK-LABEL: loop:
 entry:
   br label %loop
 loop:
   %iv = phi i64 [0, %entry], [%iv.next, %loop]
   fence acquire
   %iv.next = add i64 %iv, 1
   %test = icmp slt i64 %iv, %n
   br i1 %test, label %loop, label %exit
 exit:
   ret void
 }
 
 define void @test3(i64 %n) {
 ; CHECK-LABEL: @test3
-; CHECK-LABEL: loop:
 ; CHECK: fence
+; CHECK-LABEL: loop:
 entry:
   br label %loop
 loop:
   %iv = phi i64 [0, %entry], [%iv.next, %loop]
   fence acq_rel
   %iv.next = add i64 %iv, 1
   %test = icmp slt i64 %iv, %n
   br i1 %test, label %loop, label %exit
 exit:
   ret void
 }
 
 define void @test4(i64 %n) {
 ; CHECK-LABEL: @test4
-; CHECK-LABEL: loop:
 ; CHECK: fence
+; CHECK-LABEL: loop:
 entry:
   br label %loop
 loop:
   %iv = phi i64 [0, %entry], [%iv.next, %loop]
   fence seq_cst
   %iv.next = add i64 %iv, 1
   %test = icmp slt i64 %iv, %n
   br i1 %test, label %loop, label %exit
loop:
   %n = load i64, i64* %p
   %iv.next = add i64 %iv, 1
   %test = icmp slt i64 %iv, %n
   br i1 %test, label %loop, label %exit
 exit:
   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:
   br label %loop
 loop:
   %iv = phi i64 [0, %entry], [%iv.next, %loop]
   fence release
   fence release
   %iv.next = add i64 %iv, 1
   %test = icmp slt i64 %iv, %n
   br i1 %test, label %loop, label %exit
 exit:
   ret void
 }