[MemDep] Fixed handling of invariant.group

[Prazek]

Summary

Memdep had a funny bug related to invariant.groups - because it did not
invalidated cache, in some very rare cases it was possible to show memory
dependence of the instruction that was deleted, but because other
instruction took it's place it resulted in call to vtable!
Thanks @amharc for repro!.

[amharc]

include/llvm/IR/ValueMap.h

109

Can this be marked noexcept, like the move operator= below?

[Prazek]

noexcept

[amharc]

I am not sure that ValueMap can be moveable: if it was moved, the ValueMapT *Map pointer in ValueMapCallbackVH could become invalid.

Wouldn't std::unique_ptr<ValueMap<Instruction *, NonLocalDepResult>> NonLocalDefsCache be a better solution?

[• dberlin]

It's kind of hard for me to know what to do with this.
The cache invalidation is still very very broken with or without this patch.
So this patch is not wrong but everything it does probably needs to be rewritten anyway

[amharc]

Would handling NonLocalDefsCache in the same places as other DenseMaps from Instruction * be sufficient? In particular, RemoveCachedNonLocalPointerDependencies, called by both removeInstruction and invalidateCachedPointerInfo, looks promising ;)

[Prazek]

In D45320#1058698, @dberlin wrote:

It's kind of hard for me to know what to do with this.
The cache invalidation is still very very broken with or without this patch.
So this patch is not wrong but everything it does probably needs to be rewritten anyway

I know, I also wish we would get rid of MemDep asap, but as long as it's there, it would be good to avoid weird miscompilations that causes calls to vtable.

In D45320#1058825, @amharc wrote:

Would handling NonLocalDefsCache in the same places as other DenseMaps from Instruction * be sufficient? In particular, RemoveCachedNonLocalPointerDependencies, called by both removeInstruction and invalidateCachedPointerInfo, looks promising ;)

Yep, this is probably the right way to go

[• dberlin]

"I know, I also wish we would get rid of MemDep asap, but as long as it's there, it would be good to avoid weird miscompilations that causes calls to vtable."

But it still will, just not in this particular way.
But it will still fail in very common ways anyway :)

We may actually have to disable preservation entirely for the moment anyway.

[Prazek]

Removed ValueMap, use removeCachedNonLocalPointerDependency

[Prazek]

• small fix

[Prazek]

• small fix

[amharc]

I think it would be a little bit cleaner if the relevant checks were added to verifyRemoved too, where all other maps are traversed in debug builds. However, AssertingVH is probably a good enough guarantee ;)

You probably want to wait for dberlin to accept this.

[• dberlin]

So, please don't let me stand in the way of reasonable fixes. I only get
~20 minutes a day to look at llvm stuff these days unless i'm on vacation.
Maybe some day it'll be better again, but i suspect it'll be a while ;)

[• dberlin]

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

1472 ↗

(On Diff #141553)

You may want to do compilation time measurements on this on some bigger cases, if you haven't.

This is likely to be painfully slow in some cases.

[Prazek]

Added reverse map

[Prazek]

• fix typos

[• dberlin]

During MemorySSA development, i'm pretty positive we tried some similar types of reverse maps, and while it did relatively okay on "llvm + clang testsuite", it fell down pretty hard in the real world from memory usage.

Adding George to see if he remembers any cases, so you have some stuff to test this all with.
He's on vacation, but i believe gets back next week.

[Prazek]

In D45320#1089119, @dberlin wrote:

During MemorySSA development, i'm pretty positive we tried some similar types of reverse maps, and while it did relatively okay on "llvm + clang testsuite", it fell down pretty hard in the real world from memory usage.

Adding George to see if he remembers any cases, so you have some stuff to test this all with.
He's on vacation, but i believe gets back next week.

I don't think it would be a problem here, I don't expect this map to keep more than couple of entries (for most cases 0 and 1). The same thing goes to the previous approach.

[george.burgess.iv]

Adding George to see if he remembers any cases, so you have some stuff to test this all with.

I don't remember anything in particular. I'd recommend just bootstrapping clang/llvm and seeing what happens, assuming clang will emit these intrinsics if you pass an added cflag to it or something.

It's my impression that halide is great at generating code that hits worst-case behaviors in LLVM. I don't know whether they're users of these invariant intrinsics, however.

[Prazek]

In D45320#1093608, @george.burgess.iv wrote:

Adding George to see if he remembers any cases, so you have some stuff to test this all with.

I don't remember anything in particular. I'd recommend just bootstrapping clang/llvm and seeing what happens, assuming clang will emit these intrinsics if you pass an added cflag to it or something.

It's my impression that halide is great at generating code that hits worst-case behaviors in LLVM. I don't know whether they're users of these invariant intrinsics, however.

Probably not. I will make some analysis and get back here

[Prazek]

I measured build time of llvm& clang with devirtualization and either the variance is too big, or the compiler without this patch is faster.
As I found out, after writing other bugfix for AA, clang does not bootstrap correctly without this patch so I would love to push it.
If you don't have any objections, I would like to push it. I will still have to do build time measurements with and without devirtualization, but I would like to do it when everything is ready.
(Note that this code will not be executed unless you use devirtualization)

[george.burgess.iv]

WFM; thanks for checking!

[Prazek]

Added very small repro for the bug :)

[Prazek]

changed comment

include/llvm/Analysis/MemoryDependenceAnalysis.h

 #include "llvm/ADT/PointerSumType.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/PredIteratorCache.h"
+#include "llvm/IR/ValueMap.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <cassert>
 #include <cstdint>
 #include <utility>
 #include <vector>
 
 namespace llvm {
struct NonLocalPointerInfo {
     AAMDNodes AATags;
 
     NonLocalPointerInfo() = default;
   };
 
   /// Cache storing single nonlocal def for the instruction.
   /// It is set when nonlocal def would be found in function returning only
   /// local dependencies.
-  DenseMap<Instruction *, NonLocalDepResult> NonLocalDefsCache;
+  ValueMap<Instruction *, NonLocalDepResult> NonLocalDefsCache;
 
   /// This map stores the cached results of doing a pointer lookup at the
   /// bottom of a block.
   ///
   /// The key of this map is the pointer+isload bit, the value is a list of
   /// <bb->result> mappings.
   using CachedNonLocalPointerInfo =
       DenseMap<ValueIsLoadPair, NonLocalPointerInfo>;

include/llvm/IR/ValueMap.h

public:
   using mapped_type = ValueT;
   using value_type = std::pair<KeyT, ValueT>;
   using size_type = unsigned;
 
   explicit ValueMap(unsigned NumInitBuckets = 64)
       : Map(NumInitBuckets), Data() {}
   explicit ValueMap(const ExtraData &Data, unsigned NumInitBuckets = 64)
       : Map(NumInitBuckets), Data(Data) {}
+  ValueMap(ValueMap &&) noexcept = default;
+  ValueMap &operator=(ValueMap &&) noexcept = default;
+
   ValueMap(const ValueMap &) = delete;
   ValueMap &operator=(const ValueMap &) = delete;
 
   bool hasMD() const { return bool(MDMap); }
   MDMapT &MD() {
     if (!MDMap)
       MDMap.emplace();
     return *MDMap;

lib/Analysis/MemoryDependenceAnalysis.cpp

MemoryDependenceResults::getInvariantGroupPointerDependency(LoadInst *LI,
   if (!ClosestDependency)
     return MemDepResult::getUnknown();
   if (ClosestDependency->getParent() == BB)
     return MemDepResult::getDef(ClosestDependency);
   // Def(U) can't be returned here because it is non-local. If local
   // dependency won't be found then return nonLocal counting that the
   // user will call getNonLocalPointerDependency, which will return cached
   // result.
-  NonLocalDefsCache.try_emplace(
-      LI, NonLocalDepResult(ClosestDependency->getParent(),
-                            MemDepResult::getDef(ClosestDependency), nullptr));
+  NonLocalDefsCache.insert(
+    {LI, NonLocalDepResult(ClosestDependency->getParent(),
+                           MemDepResult::getDef(ClosestDependency),
+                           nullptr)});
   return MemDepResult::getNonLocal();
 }
 
 MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
     const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
     BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
   bool isInvariantLoad = false;
 
void MemoryDependenceResults::getNonLocalPointerDependency(
   bool isLoad = isa<LoadInst>(QueryInst);
   BasicBlock *FromBB = QueryInst->getParent();
   assert(FromBB);
 
   assert(Loc.Ptr->getType()->isPointerTy() &&
          "Can't get pointer deps of a non-pointer!");
   Result.clear();
   {
-    // Check if there is cached Def with invariant.group. FIXME: cache might be
-    // invalid if cached instruction would be removed between call to
-    // getPointerDependencyFrom and this function.
+    // Check if there is cached Def with invariant.group.
     auto NonLocalDefIt = NonLocalDefsCache.find(QueryInst);
     if (NonLocalDefIt != NonLocalDefsCache.end()) {
       Result.push_back(std::move(NonLocalDefIt->second));
       NonLocalDefsCache.erase(NonLocalDefIt);
       return;
     }
   }
   // This routine does not expect to deal with volatile instructions.

 AnalysisKey MemoryDependenceAnalysis::Key;
 
 MemoryDependenceResults
 MemoryDependenceAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
   auto &AA = AM.getResult<AAManager>(F);
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
-  return MemoryDependenceResults(AA, AC, TLI, DT);
+  return {AA, AC, TLI, DT};
 }
 
 char MemoryDependenceWrapperPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(MemoryDependenceWrapperPass, "memdep",
                       "Memory Dependence Analysis", false, true)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)