This is an archive of the discontinued LLVM Phabricator instance.

[DivRemPairs] Fix non-determinism in use list order.
ClosedPublic

Authored by gberry on Apr 19 2018, 7:35 PM.

Details

Summary

Use a MapVector instead of a DenseMap for RemMap since it is iteratated
over and the order of iteration can effect the order that new
instructions are created. This can in turn effect the use list order of
div/rem input values if multiple new instructions are created that share
any input values.

Diff Detail

Repository
rL LLVM

Event Timeline

gberry created this revision.Apr 19 2018, 7:35 PM

That looks ok, but I'm curious;

  1. How do you discover this problem?
  2. Is it possible to make the problem visible in a regression test (if so, please add a test)?
  3. The DenseMap usage is based on the code in BypassSlowDivision - does it have the same problem/fix?

That looks ok, but I'm curious;

  1. How do you discover this problem?

I ran into this when testing a totally unrelated change that I expected to have no effect on final code generation. When it generated different code for one llvm-test-suite test case, I investigated why, and it led me here.

  1. Is it possible to make the problem visible in a regression test (if so, please add a test)?

I don't think so, but maybe. The problem is that before this change, the DivRemPairs pass will generate non-deterministic use-list orderings. I could write a test that dumps the use-list info and check that, but that seems pretty fragile.

  1. The DenseMap usage is based on the code in BypassSlowDivision - does it have the same problem/fix?

I looked over BypassSlowDivision briefly and it doesn't seem to have the same problem. The only iteration over an unordered container seems to be at the end of bypassSlowDivision where it is iterating over PerBBDivCache. This loop is only removing dead instructions so I don't think the removal order should have any effect on the IR use-list order.

mgrang added a subscriber: mgrang.Apr 23 2018, 11:53 AM

If there is a unit test for this then it should have been uncovered in the reverse iteration bot: http://lab.llvm.org:8011/builders/reverse-iteration

If there is a unit test for this then it should have been uncovered in the reverse iteration bot: http://lab.llvm.org:8011/builders/reverse-iteration

I don't think this bot would catch this regression since the test would need to be checking the use-list order, which very few do.

That looks ok, but I'm curious;

  1. How do you discover this problem?

I ran into this when testing a totally unrelated change that I expected to have no effect on final code generation. When it generated different code for one llvm-test-suite test case, I investigated why, and it led me here.

  1. Is it possible to make the problem visible in a regression test (if so, please add a test)?

I don't think so, but maybe. The problem is that before this change, the DivRemPairs pass will generate non-deterministic use-list orderings. I could write a test that dumps the use-list info and check that, but that seems pretty fragile.

The answer to #1 suggests that we could reduce a codegen test based on whatever wiggled in test-suite? I don't know how much effort that requires, so if it doesn't seem worthwhile, I won't hold up this patch. I just want to know what I should do if I run into a similar problem. Also, @mgrang is the answer about the reverse-iteration-bot sufficient? (Again, I don't know anything about it, so trying to understand better.)

That looks ok, but I'm curious;

  1. How do you discover this problem?

I ran into this when testing a totally unrelated change that I expected to have no effect on final code generation. When it generated different code for one llvm-test-suite test case, I investigated why, and it led me here.

  1. Is it possible to make the problem visible in a regression test (if so, please add a test)?

I don't think so, but maybe. The problem is that before this change, the DivRemPairs pass will generate non-deterministic use-list orderings. I could write a test that dumps the use-list info and check that, but that seems pretty fragile.

The answer to #1 suggests that we could reduce a codegen test based on whatever wiggled in test-suite? I don't know how much effort that requires, so if it doesn't seem worthwhile, I won't hold up this patch. I just want to know what I should do if I run into a similar problem. Also, @mgrang is the answer about the reverse-iteration-bot sufficient? (Again, I don't know anything about it, so trying to understand better.)

A quick background on the reverse-iteration bot: https://llvm.org/docs/CodingStandards.html#beware-of-non-determinism-due-to-ordering-of-pointers
Unordered containers like SmallPtrSet and DenseMap do not guarantee the order of iteration of elements. So iterating them can result in non-deterministic codegen. However, not all instances of iterating an unordered container result in non-determinism. Given this, it becomes difficult to identify which iteration instances can cause this behavior. The reverse iteration bot iterates such containers in reverse, by default, to weed out such cases.

However, the bot is only useful only if there are tests which stress/depend on iteration order. And while it may be possible to write such tests I am not sure if it's worth the effort. My experience also has been that I have randomly run into non-deterministic behavior and debugging led me to problems in iteration order.

So I think this patch LGTM.

I just want to know what I should do if I run into a similar problem.

You can build your toolchain with LLVM_REVERSE_ITERATION:ON and see if your test still fails. If it does then it suggests a problem in iteration order of either SmallPtrSet or DenseMap.
From http://llvm.org/docs/CMake.html?highlight=cmake:

LLVM_REVERSE_ITERATION:BOOL
If enabled, all supported unordered llvm containers would be iterated in reverse order. This is useful for uncovering non-determinism caused by iteration of unordered containers.
spatel accepted this revision.Apr 24 2018, 11:24 AM

Thanks for the pointers!
LGTM.

This revision is now accepted and ready to land.Apr 24 2018, 11:24 AM
This revision was automatically updated to reflect the committed changes.

A quick background on the reverse-iteration bot: https://llvm.org/docs/CodingStandards.html#beware-of-non-determinism-due-to-ordering-of-pointers
Unordered containers like SmallPtrSet and DenseMap do not guarantee the order of iteration of elements. So iterating them can result in non-deterministic codegen. However, not all instances of iterating an unordered container result in non-determinism. Given this, it becomes difficult to identify which iteration instances can cause this behavior. The reverse iteration bot iterates such containers in reverse, by default, to weed out such cases.

However, the bot is only useful only if there are tests which stress/depend on iteration order. And while it may be possible to write such tests I am not sure if it's worth the effort. My experience also has been that I have randomly run into non-deterministic behavior and debugging led me to problems in iteration order.

@mgrang Out of curiosity, what tests does this bot run? I assume it is just runs the lit tests as is? It might be interesting to expand it to also keep a second build without reverse iteration and compare the outputs of the two to make sure they are identical.