Page MenuHomePhabricator

[MemorySSA] Add API to update MemoryPhis, following CFG changes.
ClosedPublic

Authored by asbirlea on Jul 10 2018, 2:39 PM.

Details

Summary

When splitting predecessors in BasicBlockUtils, we create a new block as an immediate predecessor of the original BB, then we connect a given set of predecessors to the new block.
The API in this patch will be used to update MemoryPhis for this CFG change.
If all predecessors are being moved, we move the MemoryPhi directly. Otherwise we create a new MemoryPhi in the NewBB and populate its incoming values, while deleting them from BB's Phi.
[Split from D45299 for easier review]

Diff Detail

Event Timeline

asbirlea created this revision.Jul 10 2018, 2:39 PM
asbirlea updated this revision to Diff 154899.Jul 10 2018, 3:25 PM

Consider multiple edges between blocks. MemoryPhis have an entry for each edge in this case. Move all edges to the new phi to preserve number of edges equal to number of phi entries.

lib/Analysis/MemorySSAUpdater.cpp
499

nit: Please just use ! instead of == nullptr, for consistency

504

Doesn't pred_size(Old) == 1 imply that pred_size(New) == Preds.size() must be true? Or is there a case I'm missing?

507

nit: s/Preds.size() > 0/!Preds.empty()/

517

Looks like we could do this in O(Preds.size() + Phi->getNumOperands()) time if we instead used a SmallPtrSet for Preds and did a single walk over the operands list, querying the SmallPtrSet for whether $current_operand is something we could remove.

If we made a general utility for Phis similar in spirit to llvm::erase_if for this, looks like we could even make unorderedDeleteIncomingBlock and unorderedDeleteIncomingValue tiny wrappers around that.

It would arguably be mildly awkward to have the addIncoming side-effect from the lambda there, but I'd imagine it would be cleaner on the whole. WDYT?

asbirlea updated this revision to Diff 155273.Jul 12 2018, 2:19 PM
asbirlea marked 4 inline comments as done.

Address comments.

asbirlea added inline comments.Jul 12 2018, 2:19 PM
lib/Analysis/MemorySSAUpdater.cpp
517

I think I like this more than the alternatives I thought about. So here goes :)

include/llvm/Analysis/MemorySSA.h
581 ↗(On Diff #155273)

s/entried/entries

lib/Analysis/MemorySSAUpdater.cpp
516

Can we replace Phi->getIncomingValueForBlock(B) with the MemoryAccess * we're passed in (if we make it non-const)?

517

Did making a SmallPtrSet of Preds not work?

asbirlea updated this revision to Diff 155293.Jul 12 2018, 3:52 PM
asbirlea marked 4 inline comments as done.

Right, updated now.

Thanks again!

This revision is now accepted and ready to land.Jul 12 2018, 4:02 PM

Thank you for the review!

This revision was automatically updated to reflect the committed changes.
sanjoy added inline comments.Aug 18 2018, 12:22 PM
llvm/trunk/include/llvm/Analysis/MemorySSAUpdater.h
133 ↗(On Diff #156532)

I was trying to understand this comment in the context of https://reviews.llvm.org/D45300 and I think it can be improved slightly. Instead of saying "before" and "point to" we should use more specific "branches to" terminology. I.e. something like:

Old now has New, an empty BasicBlock, branching directly to it, and the predecessors in Preds that used to branch to Old, now branch to New. If New is the only predecessor, move Old's Phi, if present, to New.  Otherwise, add a new Phi in New with appropriate incoming values, and update the incoming values in Old's Phi node too, if present.
asbirlea marked an inline comment as done.Aug 20 2018, 11:17 AM
asbirlea added inline comments.
llvm/trunk/include/llvm/Analysis/MemorySSAUpdater.h
133 ↗(On Diff #156532)

Thanks! Updated in r340192.