[DeclContext] Sort the Decls before adding into DeclContext

[steven_wu]

Summary

Fix a non-deterministic issue in clang module generation, which the
anonymous declaration number from a function context is not
deterministic. This is due to the unstable iteration order for decls in
scope so the order after moving the decls into function decl context is
not deterministic.

From https://reviews.llvm.org/D135118, we can't use a set that preserves
the order without the performance penalty. Fix the issue by sorting the
decls based on raw encoding of their source location.

rdar://104097976

[akyrtzi]

Is it impractical to add a test for this? Otherwise LGTM.

[dblaikie]

Yeah, might be nice to document where the instability comes from - if it comes from a DenseMap or similar, then a test that fails either in forward or reverse iteration mode would be nice to have.

[rsmith]

In D141625#4052820, @dblaikie wrote:

Yeah, might be nice to document where the instability comes from - if it comes from a DenseMap or similar, then a test that fails either in forward or reverse iteration mode would be nice to have.

Scope::decls is iterating over a SmallPtrSet. This might be a little annoying to create a test for, because it'll only be unstable if we have two decls in the same prototype scope that get allocated into different slabs by the bump ptr allocator, but maybe something like:

void f(struct A *p, int arr[1 + 0 + 0 + 0 + ... + 0], struct B *q);

... would be enough (with sufficient subexpressions to fill a whole slab). Then we can build a .pch for that twice and check that it comes out identical.

[akyrtzi]

Yeah, you mainly need more than 32 decls to exceed the small storage of Scope::DeclSetTy.

[steven_wu]

In D141625#4052869, @rsmith wrote:

In D141625#4052820, @dblaikie wrote:

Yeah, might be nice to document where the instability comes from - if it comes from a DenseMap or similar, then a test that fails either in forward or reverse iteration mode would be nice to have.

Scope::decls is iterating over a SmallPtrSet. This might be a little annoying to create a test for, because it'll only be unstable if we have two decls in the same prototype scope that get allocated into different slabs by the bump ptr allocator, but maybe something like:

void f(struct A *p, int arr[1 + 0 + 0 + 0 + ... + 0], struct B *q);

... would be enough (with sufficient subexpressions to fill a whole slab). Then we can build a .pch for that twice and check that it comes out identical.

Yeah, it is really hard to trigger a failure. Even the second decl gets onto a different slab, the second slab will most likely come after the previous one when there isn't much memory pressure.

I can write a test like that but it is really hard to trigger without an enormous module (building Darwin module from macOS SDK can reproduce very reliable).

[steven_wu]

@akyrtzi has the good idea. It is really hard to control Decl* to get values
to get an unstable iteration order from the small tests, going beyond 32 decls
to get out of SmallPtrSet's small model is much consistent.

Add test.

[vsapsai]

Confirm that for me on macOS without the fix the test is failing every time, so the test seems to be totally sufficient.

clang/lib/Parse/ParseDecl.cpp

6998

I was slightly concerned about it affecting build times for non-modular builds. But I don't think that we have in practice enough declarations in prototypes for it to matter, so that's not a real concern.

And we don't need to do anything special for declarations brought in by macros as we are not aiming for any particular order, just for the deterministic one.

clang/test/Modules/decl-params-determinisim.m

16–17

Is there any reason you are using struct A1 twice? I haven't noticed any difference in my testing, so decided to ask.

[steven_wu]

Minor touch up on the test case. Also add some comments in test to explain what is being tested.

I don't measure any performance regression from -fsyntax-only on Foundation.h but if there are some other performance benchmark I need to be tested first, let me know.
Alternatively, there can be a even safer fix by moving the sorting into numberAnonymousDeclsWithin which seems to be only used in serialization. I can change to that to be extra safe.

[steven_wu]

Actually, sorting in numberAnonymousDeclsWithin doesn't work for some reasons.

[dblaikie]

In D141625#4053067, @steven_wu wrote:

@akyrtzi has the good idea. It is really hard to control Decl* to get values
to get an unstable iteration order from the small tests, going beyond 32 decls
to get out of SmallPtrSet's small model is much consistent.

Add test.

Could you make a smaller test (probably just a couple of decls) that fails with LLVM_ENABLE_REVERSE_ITERATION? Such a failure would be more reliable/simpler to reproduce, probably?

[steven_wu]

In D141625#4056831, @steven_wu wrote:

Actually, sorting in numberAnonymousDeclsWithin doesn't work for some reasons.

The reason for this doesn't work is ASTWriter::WriteDeclContextLexicalBlock also iterates on DeclContext::decls(), so there are at least two sorts needed in ASTWriter. I prefer the current implementation if there isn't any performance overhead since it makes the iterator on DeclContext to have stable order.

In D141625#4059186, @dblaikie wrote:

In D141625#4053067, @steven_wu wrote:

@akyrtzi has the good idea. It is really hard to control Decl* to get values
to get an unstable iteration order from the small tests, going beyond 32 decls
to get out of SmallPtrSet's small model is much consistent.

Add test.

Could you make a smaller test (probably just a couple of decls) that fails with LLVM_ENABLE_REVERSE_ITERATION? Such a failure would be more reliable/simpler to reproduce, probably?

Sure but it is going to put a different requirement on the tests. Now ASTWriter only cares about a stable order for deterministic output so it is doing a diff on pcm. If changing to the reverse iterator test, this need to change to do FileCheck on a predetermined order.

[steven_wu]

@dblaikie Do we have any bots running reverse iteration?

[tschuett]

EXPANSIVE_CHECKS will reshuffle the llvm::sort input: https://lists.llvm.org/pipermail/llvm-dev/2018-April/122576.html

[steven_wu]

In D141625#4059540, @tschuett wrote:

EXPANSIVE_CHECKS will reshuffle the llvm::sort input: https://lists.llvm.org/pipermail/llvm-dev/2018-April/122576.html

This is a slightly different concern. The problem to catch is iterating over a SmallPtrSet, not identical sort key.

[dblaikie]

In D141625#4059486, @steven_wu wrote:

@dblaikie Do we have any bots running reverse iteration?

Hmm, not that I can see/find at a quick glance, which is unfortunate. @mgrang Are you still working on LLVM/have any knowledge of reverse iteration testing being done? (@colinl - looks like maybe you're a Code Aurora person, perhaps you've got some more recent context for this?)

[steven_wu]

In D141625#4060460, @dblaikie wrote:

In D141625#4059486, @steven_wu wrote:

@dblaikie Do we have any bots running reverse iteration?

Hmm, not that I can see/find at a quick glance, which is unfortunate. @mgrang Are you still working on LLVM/have any knowledge of reverse iteration testing being done? (@colinl - looks like maybe you're a Code Aurora person, perhaps you've got some more recent context for this?)

At another look, it is not very easy to write a test that checks a strict ordering of the serialization. The only tool I know that can dump the module is llvm-bcanalyzer but everything in the module will appear in the order of anonymous decl number order. You have to decode the Decls and Types to know if they actually appear in the source ordering. A diff test probably makes a lot more sense here.

[steven_wu]

@dblaikie Do you have any objection for committing the patch as it is? I don't think reverse iteration test is a proper way to test for this specific bug.

[dblaikie]

In D141625#4066362, @steven_wu wrote:

@dblaikie Do you have any objection for committing the patch as it is? I don't think reverse iteration test is a proper way to test for this specific bug.

I think reverse iteration is the right way to test this specific bug (& any bug where behavior may be unintentionally nondeterministic due to non-deterministically ordered containers) - it makes the testing more reliable rather than depending on implementation details of such containers that aren't guaranteed (that being the point/problem).

But it's not the worst/most unwieldy test for this sort of thing & if we don't have bots using it... hmm, actually I looked more closely & maybe we do have reverse iteration builders: https://github.com/llvm/llvm-zorg/search?q=reverse-iteration (though I'm having trouble navigating the builder UI to see whether there are up-to-date builds for this configuration)

Could you help me understand your perspective regarding using reverse iteration to test this specific bug? (are there some bugs you find reverse iteration suitable for? what's different about this one from them?)

[steven_wu]

In D141625#4066466, @dblaikie wrote:

In D141625#4066362, @steven_wu wrote:

@dblaikie Do you have any objection for committing the patch as it is? I don't think reverse iteration test is a proper way to test for this specific bug.

I think reverse iteration is the right way to test this specific bug (& any bug where behavior may be unintentionally nondeterministic due to non-deterministically ordered containers) - it makes the testing more reliable rather than depending on implementation details of such containers that aren't guaranteed (that being the point/problem).

But it's not the worst/most unwieldy test for this sort of thing & if we don't have bots using it... hmm, actually I looked more closely & maybe we do have reverse iteration builders: https://github.com/llvm/llvm-zorg/search?q=reverse-iteration (though I'm having trouble navigating the builder UI to see whether there are up-to-date builds for this configuration)

Could you help me understand your perspective regarding using reverse iteration to test this specific bug? (are there some bugs you find reverse iteration suitable for? what's different about this one from them?)

With reverse iteration, you can make sure that the we didn't iterate over the non-deterministic container by checking the ordering of the decls in the module, which is fine. But no one really runs that tests regularly.
Without the reverse iteration, the ordering check will always succeed because the anonymous decls will be numbered and ordered in the ascending order as iteration. It is not easy to decode which decl is which by analyze the output of llvm-bcanalyzer. Current test (which is not big at all) will put (80 - 32) entries into hash table of smallptrset, thus it kind of triggers the bug near 100% of the time. I would think the current test is more valuable than a test only fail in reverse iteration.

I can add extra file check to make sure all decls are in order, so if you run reverse iteration, you will fail before hitting the diff test.

[steven_wu]

Update tests according to feedback

[dblaikie]

In D141625#4066681, @steven_wu wrote:

In D141625#4066466, @dblaikie wrote:

In D141625#4066362, @steven_wu wrote:

@dblaikie Do you have any objection for committing the patch as it is? I don't think reverse iteration test is a proper way to test for this specific bug.

I think reverse iteration is the right way to test this specific bug (& any bug where behavior may be unintentionally nondeterministic due to non-deterministically ordered containers) - it makes the testing more reliable rather than depending on implementation details of such containers that aren't guaranteed (that being the point/problem).

But it's not the worst/most unwieldy test for this sort of thing & if we don't have bots using it... hmm, actually I looked more closely & maybe we do have reverse iteration builders: https://github.com/llvm/llvm-zorg/search?q=reverse-iteration (though I'm having trouble navigating the builder UI to see whether there are up-to-date builds for this configuration)

Could you help me understand your perspective regarding using reverse iteration to test this specific bug? (are there some bugs you find reverse iteration suitable for? what's different about this one from them?)

With reverse iteration, you can make sure that the we didn't iterate over the non-deterministic container by checking the ordering of the decls in the module, which is fine.

I'm not sure I follow - does building LLVM with reverse iteration not break the integration/diff test you've written? I'd expect it would, and that it would fail a smaller test with only a couple of decls?

But no one really runs that tests regularly.
Without the reverse iteration, the ordering check will always succeed because the anonymous decls will be numbered and ordered in the ascending order as iteration. It is not easy to decode which decl is which by analyze the output of llvm-bcanalyzer. Current test (which is not big at all) will put (80 - 32) entries into hash table of smallptrset, thus it kind of triggers the bug near 100% of the time. I would think the current test is more valuable than a test only fail in reverse iteration.

Given stability issues are pretty rare/unstable to reproduce, I think a test that only fails in one of reverse or forward iteration mode is acceptable/a suitable way to test stability problems & I'm OK with/would personally prefer the test be reduced to only that, rather than having to add enough to cause the hashing to tip over into instability - that's why reverse iteration was added, to catch these sort of issues, including through intentional tests of features that would expose problems when combined with reverse iteration.

[steven_wu]

No, reverse iteration will not break diff test for a small number of decls. Everything will be in reverse order so it is the same. Current test will fail early in reverse iteration and will fail in the end statistically for forward iteration. Will pass in all configurations. I think paying a bit more decls to make it fail in forward iteration is not a bad trade off.

[dblaikie]

In D141625#4066961, @steven_wu wrote:

No, reverse iteration will not break diff test for a small number of decls. Everything will be in reverse order so it is the same.

Hmm, I'm not sure I'm following why that is - could you explain this in more detail? The usual problem is that, say, we're outputting based on an unstable order - even two items would be enough to cause a test of that to fail in either forward or reverse iteration mode until the order is stabilized.

Is that not the case here? Is there some interaction between iteration order that's part of the nondeterminism here?

[steven_wu]

In D141625#4067225, @dblaikie wrote:

In D141625#4066961, @steven_wu wrote:

No, reverse iteration will not break diff test for a small number of decls. Everything will be in reverse order so it is the same.

Hmm, I'm not sure I'm following why that is - could you explain this in more detail? The usual problem is that, say, we're outputting based on an unstable order - even two items would be enough to cause a test of that to fail in either forward or reverse iteration mode until the order is stabilized.

Is that not the case here? Is there some interaction between iteration order that's part of the nondeterminism here?

In order to make a test that will break before the change with reverse iteration, the test needs to check that the decls/records are serialized into the module in a pre deterministic order. It can't be just diff the output of two runs with a small input because small input will not overflow the smallptrset, thus the reverse iteration outputs from two runs will very likely to be identical, just in a different order from forward iteration.

It is also in the same time not easy to write a test that can check the pre deterministic order of the serialization because it is hard to identify which entry is which decl from the output of bcanalyzer. For example, an entry like <DECL_PARM_VAR abbrevid=9 op0=0 op1=18 op2=0 op3=0 op4=0 op5=0 op6=0 op7=0 op8=0 op9=3 op10=1 op11=1 op12=0 op13=2 op14=0 op15=2424 op16=24822 op17=0 op18=2424 op19=0 op20=0 op21=0 op22=0 op23=0 op24=0 op25=0 op26=0 op27=0 op28=0 op29=0 op30=0 op31=0 op32=0 op33=24842 op34=40 op35=0 op36=29/> means nothing just looking at itself. Even worse, the opcode I check op13 in the test is assigned via iteration order and decls are serialized via iteration order. So all the entries will always kind of appear in ascending order.

[dblaikie]

In D141625#4094742, @steven_wu wrote:

In D141625#4067225, @dblaikie wrote:

In D141625#4066961, @steven_wu wrote:

No, reverse iteration will not break diff test for a small number of decls. Everything will be in reverse order so it is the same.

Hmm, I'm not sure I'm following why that is - could you explain this in more detail? The usual problem is that, say, we're outputting based on an unstable order - even two items would be enough to cause a test of that to fail in either forward or reverse iteration mode until the order is stabilized.

Is that not the case here? Is there some interaction between iteration order that's part of the nondeterminism here?

In order to make a test that will break before the change with reverse iteration, the test needs to check that the decls/records are serialized into the module in a pre deterministic order. It can't be just diff the output of two runs with a small input because small input will not overflow the smallptrset, thus the reverse iteration outputs from two runs will very likely to be identical, just in a different order from forward iteration.

Sure, I think I'm with you there - but the current test checks that the decls/records are serialized into the module in a pre-deterministic order, right? So it doesn't seem like a reverse iteration-failing test would be more involved/brittle/less robust than the test being added here?

[steven_wu]

In D141625#4094837, @dblaikie wrote:

In D141625#4094742, @steven_wu wrote:

In D141625#4067225, @dblaikie wrote:

In D141625#4066961, @steven_wu wrote:

No, reverse iteration will not break diff test for a small number of decls. Everything will be in reverse order so it is the same.

Hmm, I'm not sure I'm following why that is - could you explain this in more detail? The usual problem is that, say, we're outputting based on an unstable order - even two items would be enough to cause a test of that to fail in either forward or reverse iteration mode until the order is stabilized.

Is that not the case here? Is there some interaction between iteration order that's part of the nondeterminism here?

In order to make a test that will break before the change with reverse iteration, the test needs to check that the decls/records are serialized into the module in a pre deterministic order. It can't be just diff the output of two runs with a small input because small input will not overflow the smallptrset, thus the reverse iteration outputs from two runs will very likely to be identical, just in a different order from forward iteration.

Sure, I think I'm with you there - but the current test checks that the decls/records are serialized into the module in a pre-deterministic order, right? So it doesn't seem like a reverse iteration-failing test would be more involved/brittle/less robust than the test being added here?

Yes, exactly, I added file check so that this test is going to fail for reverse iteration. What I also want is keep the size of the test case since it not really enormous so this test also has a good chance of failing without reverse iteration.

[dblaikie]

In D141625#4094942, @steven_wu wrote:

In D141625#4094837, @dblaikie wrote:

In D141625#4094742, @steven_wu wrote:

In D141625#4067225, @dblaikie wrote:

In D141625#4066961, @steven_wu wrote:

No, reverse iteration will not break diff test for a small number of decls. Everything will be in reverse order so it is the same.

Hmm, I'm not sure I'm following why that is - could you explain this in more detail? The usual problem is that, say, we're outputting based on an unstable order - even two items would be enough to cause a test of that to fail in either forward or reverse iteration mode until the order is stabilized.

Is that not the case here? Is there some interaction between iteration order that's part of the nondeterminism here?

In order to make a test that will break before the change with reverse iteration, the test needs to check that the decls/records are serialized into the module in a pre deterministic order. It can't be just diff the output of two runs with a small input because small input will not overflow the smallptrset, thus the reverse iteration outputs from two runs will very likely to be identical, just in a different order from forward iteration.

Sure, I think I'm with you there - but the current test checks that the decls/records are serialized into the module in a pre-deterministic order, right? So it doesn't seem like a reverse iteration-failing test would be more involved/brittle/less robust than the test being added here?

Yes, exactly, I added file check so that this test is going to fail for reverse iteration. What I also want is keep the size of the test case since it not really enormous so this test also has a good chance of failing without reverse iteration.

Sorry, I'm still not really following - OK, sounds like you're saying this test does fail at HEAD/without this patch in reverse iteration mode, and is a bit larger than would be minimally necessary to achieve that, but also might fail at HEAD without reverse iteration, providing somewhat more testing than if it were fully minimized/only caught in reverse.

Fair enough -I don't think it's the right tradeoff, but I'm glad it's stable/provides that coverage.

[steven_wu]

Sorry, I'm still not really following - OK, sounds like you're saying this test does fail at HEAD/without this patch in reverse iteration mode, and is a bit larger than would be minimally necessary to achieve that, but also might fail at HEAD without reverse iteration, providing somewhat more testing than if it were fully minimized/only caught in reverse.

Fair enough -I don't think it's the right tradeoff, but I'm glad it's stable/provides that coverage.

The main motivations are:

• Reverse iteration coverage from bots are really low.
• The FileCheck that supposed to fail on reverse iteration is not fully checking the order of decls in the serialized bitcode in a semantic way. It is only checking an index, which also assigned based on an iteration order. If both iterations are iterating none deterministic container, both will be reversed and the test will pass :)

[dblaikie]

In D141625#4095197, @steven_wu wrote:

Sorry, I'm still not really following - OK, sounds like you're saying this test does fail at HEAD/without this patch in reverse iteration mode, and is a bit larger than would be minimally necessary to achieve that, but also might fail at HEAD without reverse iteration, providing somewhat more testing than if it were fully minimized/only caught in reverse.

Fair enough -I don't think it's the right tradeoff, but I'm glad it's stable/provides that coverage.

The main motivations are:

• Reverse iteration coverage from bots are really low.
• The FileCheck that supposed to fail on reverse iteration is not fully checking the order of decls in the serialized bitcode in a semantic way. It is only checking an index, which also assigned based on an iteration order. If both iterations are iterating none deterministic container, both will be reversed and the test will pass :)

That seems like unfortunately brittle testing - would be great to test it more in a semantic way if possible. (& then it'd also be more capable of testing more robustly in reverse iteration, I guess?)

[akyrtzi]

would be great to test it more in a semantic way if possible

Keep in mind that the specific order of the decls doesn't matter for the purposes of this test, what matters is that the order is the same every time for the same input.

I personally think that the addition of "Spot check entries to make sure they are in current ordering" is counter-productive, because if later on some clang changes end up changing the order then the test will fail, and will need update, but that it is not what the test should care about, it should only fail if the order is non-deterministic.
But I don't feel strongly about it, I'm fine with adding the ordered check even though I don't think it's a good idea.

[steven_wu]

I don't think it is feasible with current tool to write a test that check semantically the order of decls in clang module. (Let me know if that was wrong). The current test already unfortunately relies on the module layout assuming op13 is the field for anonymous declaration number. Adding more dependency on the exact layout of the clang module will make the test really fragile to any clang AST change.

[dblaikie]

In D141625#4100660, @akyrtzi wrote:

would be great to test it more in a semantic way if possible

Keep in mind that the specific order of the decls doesn't matter for the purposes of this test, what matters is that the order is the same every time for the same input.

I personally think that the addition of "Spot check entries to make sure they are in current ordering" is counter-productive, because if later on some clang changes end up changing the order then the test will fail, and will need update, but that it is not what the test should care about, it should only fail if the order is non-deterministic.
But I don't feel strongly about it, I'm fine with adding the ordered check even though I don't think it's a good idea.

I agree it's brittle/not ideal/a tradeoff - I'd like a test that is more stable to /some/ unrelated changes (ie: not testing the numbered values, but testing something a bit more semantically).

[dblaikie]

In D141625#4100762, @steven_wu wrote:

I don't think it is feasible with current tool to write a test that check semantically the order of decls in clang module. (Let me know if that was wrong). The current test already unfortunately relies on the module layout assuming op13 is the field for anonymous declaration number.

Sure enough - having these things have semantic identifiers rather than numbers would help.

Ah, perhaps I'm just confused - I'm not sure why a similar test, that tested a different order of the op13 fields wouldn't've shown a failure without reverse iteration and then failed with reverse iteration (or the other way around) - and then could be updated with a different ordering with the fix.

Sorry, I'm clearly not making much sense here. Yes, I think the test should be reduced further (while still showing the failure in either forward or reverse iteration - but, yes, losing coverage in the real world rehashing situation) it'd make the test shorter and more maintainable (to @akyrtzi's point about future changes that introduce benign reordering) but it's not the worst example of long tests to tickle hash instability. *shrug*

I'm not insisting on it/blocking this patch from going forward without addressing this issue. Carry on.

[steven_wu]

In D141625#4100790, @dblaikie wrote:

In D141625#4100762, @steven_wu wrote:

I don't think it is feasible with current tool to write a test that check semantically the order of decls in clang module. (Let me know if that was wrong). The current test already unfortunately relies on the module layout assuming op13 is the field for anonymous declaration number.

Sure enough - having these things have semantic identifiers rather than numbers would help.

Ah, perhaps I'm just confused - I'm not sure why a similar test, that tested a different order of the op13 fields wouldn't've shown a failure without reverse iteration and then failed with reverse iteration (or the other way around) - and then could be updated with a different ordering with the fix.

Sorry, I'm clearly not making much sense here. Yes, I think the test should be reduced further (while still showing the failure in either forward or reverse iteration - but, yes, losing coverage in the real world rehashing situation) it'd make the test shorter and more maintainable (to @akyrtzi's point about future changes that introduce benign reordering) but it's not the worst example of long tests to tickle hash instability. *shrug*

I'm not insisting on it/blocking this patch from going forward without addressing this issue. Carry on.

No worry. Thanks for the thorough review and feedback. Maybe clang will have a tool to visualize clang binary module some day. I will go ahead and commit this.