On Mar 24, 2015 5:42 PM, "Chandler Carruth" <[email protected]> wrote: > > Author: chandlerc > Date: Tue Mar 24 19:34:51 2015 > New Revision: 233156 > > URL: http://llvm.org/viewvc/llvm-project?rev=233156&view=rev > Log: > [Modules] When writing out the on-disk hash table for the decl context > lookup tables, we need to establish a stable ordering for constructing > the hash table. This is trickier than it might seem. > > Most of these cases are easily handled by sorting the lookup results > associated with a specific name that has an identifier. However for > constructors and conversion functions, the story is more complicated. > Here we need to merge all of the constructors or conversion functions > together and this merge needs to be stable. We don't have any stable > ordering for either constructors or conversion functions as both would > require a stable ordering across types. > > Instead, when we have constructors or conversion functions in the > results, we reconstruct a stable order by walking the decl context in > lexical order and merging them in the order their particular declaration > names are encountered.
I assume for user written ctors and conversion functions they appear in the order the user wrote them. What happens for implicitly defined ctors? Is their order guaranteed? > This doesn't generalize as there might be found > declaration names which don't actually occur within the lexical context, > but for constructors and conversion functions it is safe. It does > require loading the entire decl context if necessary to establish the > ordering but there doesn't seem to be a meaningful way around that. > > Many thanks to Richard for talking through all of the design choices > here. While I wrote the code, he guided all the actual decisions about > how to establish the order of things. > > No test case yet because the test case I have doesn't pass yet -- there > are still more sources of non-determinism. However, this is complex > enough that I wanted it to go into its own commit in case it causes some > unforseen issue or needs to be reverted. > > Modified: > cfe/trunk/lib/Serialization/ASTWriter.cpp > > Modified: cfe/trunk/lib/Serialization/ASTWriter.cpp > URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Serialization/ASTWriter.cpp?rev=233156&r1=233155&r2=233156&view=diff > ============================================================================== > --- cfe/trunk/lib/Serialization/ASTWriter.cpp (original) > +++ cfe/trunk/lib/Serialization/ASTWriter.cpp Tue Mar 24 19:34:51 2015 > @@ -3761,15 +3761,34 @@ ASTWriter::GenerateNameLookupTable(const > !DC->HasLazyExternalLexicalLookups && > "must call buildLookups first"); > > + // Create the on-disk hash table representation. > llvm::OnDiskChainedHashTableGenerator<ASTDeclContextNameLookupTrait> > Generator; > ASTDeclContextNameLookupTrait Trait(*this); > > - // Create the on-disk hash table representation. > + // Store the sortable lookup results -- IE, those with meaningful names. We > + // will sort them by the DeclarationName in order to stabilize the ordering > + // of the hash table. We can't do this for constructors or conversion > + // functions which are handled separately. > + SmallVector<std::pair<DeclarationName, DeclContext::lookup_result>, 16> > + NamedResults; > + > + // We can't directly construct a nonce constructor or conversion name without > + // tripping asserts, so we just recall the first one we see. Only the kind > + // will actually be serialized. > DeclarationName ConstructorName; > DeclarationName ConversionName; > - SmallVector<NamedDecl *, 8> ConstructorDecls; > - SmallVector<NamedDecl *, 4> ConversionDecls; > + // Retain a mapping from each actual declaration name to the results > + // associated with it. We use a map here because the order in which we > + // discover these lookup results isn't ordered. We have to re-establish > + // a stable ordering which we do by walking the children of the decl context, > + // and emitting these in the order in which their names first appeared. Note > + // that the names' first appearance may not be one of the results or a result > + // at all. We just use this to establish an ordering. > + llvm::SmallDenseMap<DeclarationName, DeclContext::lookup_result, 8> > + ConstructorResults; > + llvm::SmallDenseMap<DeclarationName, DeclContext::lookup_result, 4> > + ConversionResults; > > visitLocalLookupResults(DC, [&](DeclarationName Name, > DeclContext::lookup_result Result) { > @@ -3786,34 +3805,90 @@ ASTWriter::GenerateNameLookupTable(const > // has the DeclarationName of the inherited constructors. > if (!ConstructorName) > ConstructorName = Name; > - ConstructorDecls.append(Result.begin(), Result.end()); > + ConstructorResults.insert(std::make_pair(Name, Result)); > return; > > case DeclarationName::CXXConversionFunctionName: > if (!ConversionName) > ConversionName = Name; > - ConversionDecls.append(Result.begin(), Result.end()); > + ConversionResults.insert(std::make_pair(Name, Result)); > return; > > default: > - break; > + NamedResults.push_back(std::make_pair(Name, Result)); > } > > - Generator.insert(Name, Result, Trait); > }); > > - // Add the constructors. > - if (!ConstructorDecls.empty()) { > + // Sort and emit the named results first. This is the easy case. > + std::sort( > + NamedResults.begin(), NamedResults.end(), > + [](const std::pair<DeclarationName, DeclContext::lookup_result> &LHS, > + const std::pair<DeclarationName, DeclContext::lookup_result> &RHS) { > + return LHS.first < RHS.first; > + }); > + for (auto Results : NamedResults) > + Generator.insert(Results.first, Results.second, Trait); > + > + // We have to specially handle the constructor and conversion function > + // declarations found. > + if (ConstructorResults.size() == 1) { > + // A special case that is easy is when we have just one constructor > + // declaration name. > Generator.insert(ConstructorName, > - DeclContext::lookup_result(ConstructorDecls), > - Trait); > + ConstructorResults.lookup(ConstructorName), Trait); > + ConstructorResults.clear(); > } > - > - // Add the conversion functions. > - if (!ConversionDecls.empty()) { > - Generator.insert(ConversionName, > - DeclContext::lookup_result(ConversionDecls), > + if (ConversionResults.size() == 1) { > + // A special case that is easy is when we have just one conversion function > + // declaration name. > + Generator.insert(ConversionName, ConversionResults.lookup(ConversionName), > Trait); > + ConversionResults.clear(); > + } > + if (!ConstructorResults.empty() || !ConversionResults.empty()) { > + SmallVector<NamedDecl *, 8> ConstructorDecls; > + SmallVector<NamedDecl *, 8> ConversionDecls; > + > + // Walk the decls in the context and collapse the results in that order. We > + // handle both constructors and conversion functions in a single walk as > + // the walk is a relative cache-hostile linked list walk. > + for (Decl *ChildD : DC->decls()) > + if (auto *ChildND = dyn_cast<NamedDecl>(ChildD)) { > + auto ConstructorResultsIt = > + ConstructorResults.find(ChildND->getDeclName()); > + if (ConstructorResultsIt != ConstructorResults.end()) { > + ConstructorDecls.append(ConstructorResultsIt->second.begin(), > + ConstructorResultsIt->second.end()); > + ConstructorResults.erase(ConstructorResultsIt); > + } > + > + auto ConversionResultsIt = > + ConversionResults.find(ChildND->getDeclName()); > + if (ConversionResultsIt != ConversionResults.end()) { > + ConversionDecls.append(ConversionResultsIt->second.begin(), > + ConversionResultsIt->second.end()); > + ConversionResults.erase(ConversionResultsIt); > + } > + > + // If we handle all of the results, we're done. > + if (ConstructorResults.empty() && ConversionResults.empty()) > + break; > + } > + assert(ConstructorResults.empty() && "Have constructor lookup results not " > + "associated with a declaration name " > + "within the context!"); > + assert(ConversionResults.empty() && "Have conversion function lookup " > + "results not associated with a " > + "declaration name within the context!"); > + > + if (!ConstructorDecls.empty()) > + Generator.insert(ConstructorName, > + DeclContext::lookup_result(ConstructorDecls), Trait); > + > + if (!ConversionDecls.empty()) > + Generator.insert(ConversionName, > + DeclContext::lookup_result(ConversionDecls), Trait); > } > > // Create the on-disk hash table in a buffer. > > > _______________________________________________ > cfe-commits mailing list > [email protected] > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
_______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
