[RFC] MemorySSAUpdater: Simplify applyUpdates

[nhaehnle]

Summary

The alternative constructor of DominatorTree does not actually compute
a dominator tree that is any different from the standard constructor,
and callers of MemorySSAUpdater::applyUpdates have already applied
updates to the dominator tree.

Change-Id: I311b6e019763b26996e5181f4d43ccedb67d6e88

[nhaehnle]

This is a weird one that I stumbled upon while looking at dominator tree construction.

CalculateWithUpdates doesn't actually *do* anything with the passed-in updates, so this change should be NFC. Either this is a very useful optimization, or something is rather broken in the MemorySSAUpdater, but I simply don't know it well enough to tell which one it is, so any illumination would be very much appreciated.

[asbirlea]

This is an issue I am aware of and the main motivation for the DominatorTree refactoring work. We do need an updated DT here, and currently we're not computing the correct one. This isn't causing issues at the moment because of the scenarios where the updater is being used, but using the current DT in general is not correct.

You're right, it's a very useful optimization now, but some of the cost will be re-added as soon as the infrastructure to update the DT to a PostCFG view is available.
I opted for not removing this now to avoid the confusion of potential performance regressions for the next release, since re-adding the infrastructure needed for correctness will present as a regression.

[nhaehnle]

Okay, thank you for that context, that makes sense. I'm going to drop this change then obviously.

FYI, I'm considering to at least try out making dominator tree construction based on the CfgInterfaceImpl from D83088, so that GenericDomTreeConstruction is no longer all a giant ball of templates. Do you think this would help you with your changes? Obviously there's the question of how it impacts compile time, but we won't really know for sure until we try it, which is one of my motivations here.

[asbirlea]

In D83421#2141875, @nhaehnle wrote:

Okay, thank you for that context, that makes sense. I'm going to drop this change then obviously.

FYI, I'm considering to at least try out making dominator tree construction based on the CfgInterfaceImpl from D83088, so that GenericDomTreeConstruction is no longer all a giant ball of templates. Do you think this would help you with your changes? Obviously there's the question of how it impacts compile time, but we won't really know for sure until we try it, which is one of my motivations here.

I think it's a great idea to improve GenericDomTreeConstruction. Some of the already committed patches did some nice cleanups. I don't have a clear picture yet of what the overlap/conflict will be with D77341, but we can work this out as you sent out more changes. I'll send out an update on the RFC as well.

llvm/lib/Analysis/MemorySSAUpdater.cpp

void MemorySSAUpdater::applyUpdates(ArrayRef<CFGUpdate> Updates,
   SmallVector<CFGUpdate, 4> InsertUpdates;
   for (auto &Update : Updates) {
     if (Update.getKind() == DT.Insert)
       InsertUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
     else
       DeleteUpdates.push_back({DT.Delete, Update.getFrom(), Update.getTo()});
   }
 
-  if (!DeleteUpdates.empty()) {
-    // Update for inserted edges: use newDT and snapshot CFG as if deletes had
-    // not occurred.
-    // FIXME: This creates a new DT, so it's more expensive to do mix
-    // delete/inserts vs just inserts. We can do an incremental update on the DT
-    // to revert deletes, than re-delete the edges. Teaching DT to do this, is
-    // part of a pending cleanup.
-    DominatorTree NewDT(DT, DeleteUpdates);
-    GraphDiff<BasicBlock *> GD(DeleteUpdates, /*ReverseApplyUpdates=*/true);
-    applyInsertUpdates(InsertUpdates, NewDT, &GD);
-  } else {
-    GraphDiff<BasicBlock *> GD;
-    applyInsertUpdates(InsertUpdates, DT, &GD);
-  }
 
   // Update for deleted edges
   for (auto &Update : DeleteUpdates)
     removeEdge(Update.getFrom(), Update.getTo());
 }
 
 void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
                                           DominatorTree &DT) {