This patch will be landing in small chunks to hopefully avoid the large reverts.

Changes made to the ODR hash algorithm:

In D21675#654659, @teemperor wrote:

I feel like we have a really similar use case in the Analysis/CloneDetection{.h/.cpp} with the hashing of statements. I tried substituting the call to the statement hashing with a call to the CloneDetection API and it seems that most tests pass and the remaining fails are just minor fixable differences (like ::foo() and foo() having different hash codes).

Would be nice if we could make Stmt::Profile, ODRHash and the CloneDetection use the same backend. We improved a few things that we no longer have the periodic reallocs from the vector inside NodeIDSet and that we use MD5. Also there are are some future plans on how we can better prevent regressions when we add/extend AST nodes. Thoughts?

After changing the ODRHash class a bit, the new performance numbers are 3% in debug and 1-1.5% in release builds.

From testing, there is no difference when compiling with pre-compiled headers. However, when building the headers, there is a 3-4% impact on compile time.

Comments have been addressed. I will be testing it for performance impact next.

This is a redesign of the ODR checker which was discovered to have several shortcomings when run over test cases. The old version mainly used depth-first processing of AST nodes to gather the information to be hashed. In some instances, a recursive loop developed preventing the termination of the hashing function.

In D21675#560297, @rsmith wrote:

There are a bunch of cases here that do this:

if (auto t = getThing())
  ID.addThing(t);
if (auto t = getOtherThing())
  ID.addThing(t);

That will result in hash collisions between objects with thing and objects with otherthing (for instance, struct A { int n : 1; }; and struct A { int n = 1; }; appear to hash the same).

And there are some cases where you add a list of objects without first adding the size, which is liable to allow collisions.

I'm not too worried about these cases, since this is just a hash anyway, and is only a best-effort attempt to check for ODR violations, but some of them look like they'd be easy enough to fix, so I figure why not :)

The hashing now does:

auto t = getThing();
ID.addBoolean(t);
if (t)
  ID.addThing(t);

The added Boolean value prevents the hash collision.

Anyway, this looks really good. Do you know if the computation of the ODR hash has any measurable performance impact when building a large module? I'm not really expecting one, but it seems worth checking just in case.

Add a more detailed error message to let users know where the two records differ. This replaces the generic error which only stated that two definitions are different without any details.

Add function void ODRHash(llvm::FoldingSetNodeID &ID) to several classes for computing the hash. Decl, Stmt, TemplateArgument, Type and QualType now have this function, and can call among each others' functions.