Address comments and add testcase.

@anton-afanasyev: FYI, we're still seeing this and it presents itself as a miscompile.
We're still working on getting a test case but it's proving to be very difficult.

Update per the comment suggestion.

Address comments.

We do very much need GraphDiff in the IDFCalculator when doing updates in MemorySSA. I don't know how I missed this, since it was the very reason it was added, but thanks a lot for catching it.
I'll send a patch with the fix shortly.

@anton-afanasyev:
The test failures occur in Halide generated code, with the HVX backend. They are not public.
r363164 does not fix the tests; it does change an erroneous output to another erroneous one.

FYI, we're seeing test failures due to this revision. Currently trying to isolate a testcase, but it may be challenging to minimize if the failures are due to a miscompile.

Add NDEBUG.

I wasn't yet able to reproduce this with opt -aa-pipeline=default -passes="default<O3>", only with clang -cc1 -O3 -fexperimental-new-pass-manager.
I'll keep working on getting a test, but I checked this in for now, since it's necessary to fix crashes for the combination of MemorySSA + NewPassManager.

Add test.

Add detalied comment.

Since I sent out D62981 with identical changes and the same motivation (thank you for pointing this out @NutshellySima), please let me add a small comment here.

Following up: I can match the previous performance if all update inserts are done first. I'll send a patch for this. But perhaps this should be done inside DTU (i.e. sort updates)?

It appears the difference is in the way the DT updates are done.
+@kuhar, @NutshellySima: Could you please take a look at the way the updates are done in MergeBlockIntoPredecessor vs (the removed) foldBlockIntoPredecessor? I tried to use a Lazy strategy and flush after doing all the potential merges, but the regression is still there. Can we get the same performance with the DomTreeUpdater here?

No reason for not removing the unused method.
Squashed a local NFC commit I had into this one.

LGTM.

Am I right that there is yet another method doing the same thing?
lib/Transforms/Utils/LoopUnroll.cpp:foldBlockIntoPredecessor

Thank you for the quick action!

FYI, we're seeing a crash in llvm::SwitchInstProfUpdateWrapper::getProfBranchWeights() following this patch.
I'm trying to get a testcase available.

I'd prefer to have Chandler approve this, since I'm not familiar with what you're trying to do here.
Some minor comments inline.

Ack, will do!

@jvesely: Yes, you are right. D61955 should resolve this.

Please see: https://bugs.llvm.org/show_bug.cgi?id=41916

Thank you for this! This LGTM.
The caching of AliasSetTracker objects will go away when MemorySSA is enabled.

I think the test in the clang patch that needs this should do?

Update test.