[EarlyCSE] Reuse invariant scopes for invariant load

[reames]

Summary

This is a follow up to https://reviews.llvm.org/D43716 which rewrites the invariant load handling using the new infrastructure. It's slightly more powerful, but only in somewhat minor ways for the moment. It's not clear that DSE of stores to invariant locations is actually interesting since why would your IR have such a construct to start with?

[anna]

LGTM

lib/Transforms/Scalar/EarlyCSE.cpp

927 ↗

(On Diff #138459)

conservatively.

[reames]

Note: The variant I committed turned out to be less powerful in one particular case than the reviewed code. I spotted that after submission and fixed it in revision 327655. The fix also improves the invariant.start case which had an analogous problem.

llvm/trunk/lib/Transforms/Scalar/EarlyCSE.cpp

public:
   /// present the table; it is the responsibility of the consumer to inspect
   /// the atomicity/volatility if needed.
   struct LoadValue {
     Instruction *DefInst = nullptr;
     unsigned Generation = 0;
     int MatchingId = -1;
     bool IsAtomic = false;
 
-    // TODO: Remove this flag.  It would be strictly stronger to add a record
-    // to the AvailableInvariant table when passing the invariant load instead.
-    bool IsInvariant = false;
-
     LoadValue() = default;
     LoadValue(Instruction *Inst, unsigned Generation, unsigned MatchingId,
-              bool IsAtomic, bool IsInvariant)
+              bool IsAtomic)
         : DefInst(Inst), Generation(Generation), MatchingId(MatchingId),
-          IsAtomic(IsAtomic), IsInvariant(IsInvariant) {}
+          IsAtomic(IsAtomic) {}
   };
 
   using LoadMapAllocator =
       RecyclingAllocator<BumpPtrAllocator,
                          ScopedHashTableVal<Value *, LoadValue>>;
   using LoadHTType =
       ScopedHashTable<Value *, LoadValue, DenseMapInfo<Value *>,
                       LoadMapAllocator>;
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
     if (MemInst.isValid() && MemInst.isLoad()) {
       // (conservatively) we can't peak past the ordering implied by this
       // operation, but we can add this load to our set of available values
       if (MemInst.isVolatile() || !MemInst.isUnordered()) {
         LastStore = nullptr;
         ++CurrentGeneration;
       }
 
+      if (MemInst.isInvariantLoad()) {
+        // If we pass an invariant load, we know that memory location is
+        // indefinitely constant from the moment of first dereferenceability.
+        // We conservatively treat the invariant_load as that moment.
+        auto MemLoc = MemoryLocation::get(Inst);
+        AvailableInvariants.insert(MemLoc, CurrentGeneration);
+      }
+
       // If we have an available version of this load, and if it is the right
       // generation or the load is known to be from an invariant location,
       // replace this instruction.
       //
       // If either the dominating load or the current load are invariant, then
       // we can assume the current load loads the same value as the dominating
       // load.
       LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
       if (InVal.DefInst != nullptr &&
           InVal.MatchingId == MemInst.getMatchingId() &&
           // We don't yet handle removing loads with ordering of any kind.
           !MemInst.isVolatile() && MemInst.isUnordered() &&
           // We can't replace an atomic load with one which isn't also atomic.
           InVal.IsAtomic >= MemInst.isAtomic() &&
-          (InVal.IsInvariant ||
-           isOperatingOnInvariantMemAt(Inst, InVal.Generation) ||
+          (isOperatingOnInvariantMemAt(Inst, InVal.Generation) ||
            isSameMemGeneration(InVal.Generation, CurrentGeneration,
                                InVal.DefInst, Inst))) {
         Value *Op = getOrCreateResult(InVal.DefInst, Inst->getType());
         if (Op != nullptr) {
           DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst
                        << "  to: " << *InVal.DefInst << '\n');
           if (!Inst->use_empty())
             Inst->replaceAllUsesWith(Op);
           removeMSSA(Inst);
           Inst->eraseFromParent();
           Changed = true;
           ++NumCSELoad;
           continue;
         }
       }
 
       // Otherwise, remember that we have this instruction.
       AvailableLoads.insert(
           MemInst.getPointerOperand(),
           LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
-                    MemInst.isAtomic(), MemInst.isInvariantLoad()));
+                    MemInst.isAtomic()));
       LastStore = nullptr;
       continue;
     }
 
     // If this instruction may read from memory or throw (and potentially read
     // from memory in the exception handler), forget LastStore.  Load/store
     // intrinsics will indicate both a read and a write to memory.  The target
     // may override this (e.g. so that a store intrinsic does not read from
if (Inst->mayWriteToMemory()) {
         // Okay, we just invalidated anything we knew about loaded values.  Try
         // to salvage *something* by remembering that the stored value is a live
         // version of the pointer.  It is safe to forward from volatile stores
         // to non-volatile loads, so we don't have to check for volatility of
         // the store.
         AvailableLoads.insert(
             MemInst.getPointerOperand(),
             LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
-                      MemInst.isAtomic(), /*IsInvariant=*/false));
+                      MemInst.isAtomic()));
 
         // Remember that this was the last unordered store we saw for DSE. We
         // don't yet handle DSE on ordered or volatile stores since we don't
         // have a good way to model the ordering requirement for following
         // passes  once the store is removed.  We could insert a fence, but
         // since fences are slightly stronger than stores in their ordering,
         // it's not clear this is a profitable transform. Another option would
         // be to merge the ordering with that of the post dominating store.

llvm/trunk/test/Transforms/EarlyCSE/invariant-loads.ll

 ; CHECK-NEXT:   %val1 = load i32, i32* %ptr
 ; CHECK-NEXT:   call void @clobber_and_use(i32 %val1)
 
   %val1 = load i32, i32* %ptr
   call void @clobber_and_use(i32 %val1)
   ret void
 }
 
-define void @test_false_negative_dse(i32* %p, i1 %cnd) {
-; CHECK-LABEL: @test_false_negative_dse
-; CHECK: store
+; By assumption, the call can't change contents of p
+; LangRef is a bit unclear about whether the store is reachable, so
+; for the moment we chose to be conservative and just assume it's valid
+; to restore the same unchanging value.
+define void @test_dse1(i32* %p) {
+; CHECK-LABEL: @test_dse1
+; CHECK-NOT: store
   %v1 = load i32, i32* %p, !invariant.load !{}
   call void @clobber_and_use(i32 %v1)
   store i32 %v1, i32* %p
   ret void
 }
+
+; By assumption, v1 must equal v2 (TODO)
+define void @test_false_negative_dse2(i32* %p, i32 %v2) {
+; CHECK-LABEL: @test_false_negative_dse2
+; CHECK: store
+  %v1 = load i32, i32* %p, !invariant.load !{}
+  call void @clobber_and_use(i32 %v1)
+  store i32 %v2, i32* %p
+  ret void
+}
+
+; If we remove the load, we still start an invariant scope since
+; it lets us remove later loads not explicitly marked invariant
+define void @test_scope_start_without_load(i32* %p) {
+; CHECK-LABEL: @test_scope_start_without_load
+; CHECK:   %v1 = load i32, i32* %p
+; CHECK:   %add = add i32 %v1, %v1
+; CHECK:   call void @clobber_and_use(i32 %add)
+; CHECK:   call void @clobber_and_use(i32 %v1)
+; CHECK:   ret void
+  %v1 = load i32, i32* %p
+  %v2 = load i32, i32* %p, !invariant.load !{}
+  %add = add i32 %v1, %v2
+  call void @clobber_and_use(i32 %add)
+  %v3 = load i32, i32* %p
+  call void @clobber_and_use(i32 %v3)
+  ret void
+}