Addressed Serguei's comment. Serguei, could you please submit this patch? I don't have permissions to submit patches yet.

@skatkov, could you please submit this patch? I don't have permissions to submit patches yet.

Hi Richard!

LGTM

Without this patch following code leads to a crash

entry:
ptr = getPtr()
br exit

I wonder is it possible to handle this two instructions, GEPs, bitcasts, loads, and other in findBaseDefiningValue to avoid code duplication and such oversights?

Added some new comments.

"merge" now replaced with "derive" in comments, example in FIXME become a bit less confusing, added new test (with XFAIL) for that FIXME.

Comments slightly clarified.

Corrected the comment.

Amended some comments, replaced lambda's wildcard capture list with explicit one, made isNotExclusivelyConstantDerived static function (to use it in lambdas without capturing).

Now the branch where valid defs of unrelocated pointers are skipped is the first one.

Comments addressed.

Changed order of the verification traversal to RPO.

Algorithm rewritten, new tests added.

One crash was found during testing.

Add message to assert.

Made logic around getImmediateBasePointer/isDerivedPointerDef more consistent.

All tests now have comments, one redundant test removed, one new added. getBasePointer now works more correctly and getImmediateBase now is the only place where we need to specify which instructions can produce derived pointers.

I've done clang bootstrap with this patch and gathered SCEV statistics: maximum number of SCEVs alive simultaneously is 209373; assuming sizeof(unsigned)==4 it's ~0.8MiB overhead.

Ping

Now sinking of unordered atomic loads from constant/invariant memory is allowed, corresponding test case added.
I am going to expose SafetyInfo in follow up patch.

LoopSink uses canSinkOrHoistInst from LICM to check whether instruction can be sunk or not. This check rejects all loads with isUnordered() == true (see http://llvm.org/docs/Atomics.html#atomics-and-ir-optimization). It looks like "unordered" atomics are handled in a right way: they are never sunk into loops.

Actually the answer is here: https://llvm.org/docs/Atomics.html#notatomic

In D37463#861162, @danielcdh wrote:

• not sure why SafetyInfo would help identify the potential data race here