Page MenuHomePhabricator

[SSAUpdaterBulk] Sort blocks in IDF to avoid non-determinism.
Needs ReviewPublic

Authored by mzolotukhin on May 7 2018, 5:21 PM.

Details

Summary

IDF does not guarantee that returned basic blocks are sorted in any
order, and to avoid non-determinism we need to sort them. To sort basic
blocks we need to enumerate them first, and this patch adds such
enumeration into JumpThreading pass.

Diff Detail

Event Timeline

mzolotukhin created this revision.May 7 2018, 5:21 PM

Hi,

This patch includes two pieces: fixing non-determinism in SSAUpdaterBulk and enabling it in JumpThreading. When approved, I'll commit them separately, but I included them both here for convenience. The fix for SSAUpdaterBulk requires basic-block enumeration, which should be passed from the SSAUpdaterBulk user, and thus it incurs the corresponding changes in JumpThreading. I'm not a big fan of an extra parameter in RewriteAllUses function and will be happy to discuss alternative, but for now I followed an example from MemorySSA. What do you think?

Thanks,
Michael

davide added inline comments.May 7 2018, 5:29 PM
llvm/lib/Transforms/Scalar/JumpThreading.cpp
361–364

Do you need to number also unreachable blocks? You could skip them, I think.

mzolotukhin added inline comments.May 7 2018, 5:38 PM
llvm/lib/Transforms/Scalar/JumpThreading.cpp
361–364

That's true, they shouldn't be in IDF.

davide added inline comments.May 7 2018, 5:50 PM
llvm/lib/Transforms/Scalar/JumpThreading.cpp
361–364

To be more clear (sorry if I wasn't), few lines later you already have a walk of the blocks in function order, so you can piggy back on that to value number non-unreachable blocks (as you're querying the dominator for reachability anyway.

mzolotukhin added inline comments.May 7 2018, 5:53 PM
llvm/lib/Transforms/Scalar/JumpThreading.cpp
361–364

No, I got this:) I will change that before committing.

dberlin added a comment.EditedMay 7 2018, 5:56 PM

IDF does not guarantee that returned basic blocks are sorted in any
order,

  1. It looks like, in theory, this is true, but could easily be solved in IDF.
  2. Given that, if this is a thing pretty much all clients of idf will have to handle, should we just sort the output of IDF?

The solution in IDF should just be changing domtreenodepair to a tuple, with the last item being domtreenode->getDFSNumIn()

That should provide a unique and guaranteed ordering for IDF.

To explain why:

  1. IDF uses a priority queue as an overall worklist
  2. It current uses "DT node level" as the priority key (which is not unique per dt node).
  3. The other worklist is a vector where order of items depends only on order of dom tree siblings (and pq processing order overall)
  4. The output is a vector which depends on pq processing order and dom tree sibling order

So, outside of pq ordering, everything else is inserted in the same order each time by using vectors and walking the linked list of siblings in the dom tree (which should be the same each time).

Thus, any non-determinism must come from the non-unique orderings for DT node level keys (IE two dt nodes can have the same key)

Adding the DFS in number (which also depends only on domtree visitation ordering) should cause it to have unique keys for each element in the pq, as long as as the dom tree creation itself is not non-deterministic (which it shouldn't be, or we're screwed in a lot of anyway).

Once it has unique keys in the pq, it should place everything on the vectors in the same order each time.

The solution in IDF should just be changing domtreenodepair to a tuple, with the last item being domtreenode->getDFSNumIn()

Just to make sure I understand you correctly: we need to change pair<DomTreeNode *, unsigned> to tuple<DomTreeNode *, unsigned, unsigned> and use the second and third elements as keys for the priority queue (i.e. we will need to implement a compare function for it, which will look at RootLevel first and at DfsNumber second if RootLevels are the same). Is it what you meant?

Michael

dberlin added a comment.EditedMay 7 2018, 6:12 PM

The solution in IDF should just be changing domtreenodepair to a tuple, with the last item being domtreenode->getDFSNumIn()

Just to make sure I understand you correctly: we need to change pair<DomTreeNode *, unsigned> to tuple<DomTreeNode *, unsigned, unsigned> and use the second and third elements as keys for the priority queue (i.e. we will need to implement a compare function for it, which will look at RootLevel first and at DfsNumber second if RootLevels are the same). Is it what you meant?

Michael

Correct. I updated my earlier comment online so it is hopefully more clear now)
You actually could just use pair<DomTreeNode *, pair<unsigned, unsigned>> and it should work only having to change the two lines pushing onto pq, though it's uglier in the abstract
Either way, you should also call DT->updateDFSNumbers() at the beginning of IDF::calculate to ensure DFS numbers are up to date.

(I didn't look to see if there was another always up to date unique number here, i just know this one works :P)

Thanks, Daniel! A fix for IDF was posted for review in D46646. If that fix is accepted, we should no longer need the current patch. Also, we should be able to remove blocks sorting from MemorySSA.

Michael