Page MenuHomePhabricator

Nondeterminism of iterators causes false ThinLTO cache misses
AcceptedPublic

Authored by kromanova on Tue, May 12, 3:03 AM.

Details

Summary

See PR 45819 for additional information (such as how to reproduce the bug, problem analysis etc).
https://bugs.llvm.org/show_bug.cgi?id=45819

We noticed that when building an executable with ThinLTO (cache enabled), from time to time unexpected cache misses happening and new cache entries are generated when not needed. It doesn't happen in a predictable manner (i.e. a cache miss might or might not happen).

‘ExportList’(‘DenseSet’ of ValueInfo's) is used for the calculation of a hash value (LTO Cache Key).
Though the elements of this DenseSet are the same all the time, the order in which the iterator walks through the elements of this set might (or might not) be different the next time when we relink with ThinLTO. If the order happens to be different, we will generate a different hash value and a cache miss will happen.

Looking at the implementation of:

template <> struct DenseMapInfo<ValueInfo> (see ModuleSummaryIndex.h)

we notice that the hash value that is being used by a DenseMap is a pointer:

static unsigned getHashValue(ValueInfo I) { return (uintptr_t)I.getRef(); }

We cannot guarantee that the compiler will allocate memory at the same
address for the object when we run the executable for the second time.

The same problem is applicable to ImportList as well.

A proposed solution here is:
(a) Create a vector of Export List's GUID (int64 integers) and sort this vector. Iterate through this sorted vector and use its elements for cache entry value calculations.
(b) Create a vector of ImportList's ModuleIDs (StringRefs) and sort this vector in lexicographical order. Iterate through this sorted vector. Use ModuleID as a key for obtaining an iterator to corresponding element of the ImportList, which has StringMap type. Use ModuleID (first element of the pair) and the list of GUIDs of all functions to import for this module (second element of the pair) for cache entry value calculations.

Note: it looks like I just spotted another potential problem in here. If confirmed, I will do a separate fix for it.
We use unordered_set container for storing GUIDs of all the functions to import for a source module.
using FunctionsToImportTy = std::unordered_set<GlobalValue::GUID>;
That means that in theory, when when we iterate through unordered_set for the second time, we could get a different order of the elements in this set, computing a different hash value and causing a potential cache miss.

Diff Detail

Event Timeline

kromanova created this revision.Tue, May 12, 3:03 AM
Herald added a project: Restricted Project. · View Herald TranscriptTue, May 12, 3:03 AM
mehdi_amini accepted this revision.Tue, May 19, 9:06 PM

LGTM

FYI with respect to:

we notice that the hash value that is being used by a DenseMap is a pointer:

static unsigned getHashValue(ValueInfo I) { return (uintptr_t)I.getRef(); }

We cannot guarantee that the compiler will allocate memory at the same
address for the object when we run the executable for the second time.

DenseMap is not an ordered container, we can't rely on its ordering regardless of the hash function. There is even a build-time option (-DLLVM_REVERSE_ITERATION=ON) to reverse the iteration order of such container to ensure we don't accidentally depend on it: https://github.com/llvm/llvm-project/blob/master/llvm/include/llvm/Support/ReverseIteration.h

llvm/lib/LTO/LTO.cpp
150

Typo: "elemets"

151

I think you can just run llvm::sort(ExportsGUID);? We don't need a "stable sort" here (can't tell the difference anyway right?)

160

Can you reserve here?

165

I think is can just be sort(ImportModulesVector); here? (llvm::sort)

168

What about storing in the vector a reference to the entry in the first place and avoid the extra lookup here?

using MapEntryTy = FunctionImporter::ImportMapTy::MapEntryTy;
std::vector<MapEntryTy *> ImportModulesVector;
ImportModulesVector.reserve(ImportList.size());
for (auto &Entry : ImportList) ImportModulesVector.push_back(&Entry);
llvm::sort(ImportModulesVector, [] (const MapEntryTy *Lhs, const MapEntryTy *Rhs) {
   return Lhs < Rhs;
});
for (MapEntryTy *Entry : ImportModulesVector) {
  ...
This revision is now accepted and ready to land.Tue, May 19, 9:06 PM