[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rG0480748ea672: [DeclContext] Sort the Decls before adding 
into DeclContext (authored by steven_wu).

Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

Files:
  clang/lib/Parse/ParseDecl.cpp
  clang/test/Modules/decl-params-determinisim.m

Index: clang/test/Modules/decl-params-determinisim.m
===
--- /dev/null
+++ clang/test/Modules/decl-params-determinisim.m
@@ -0,0 +1,96 @@
+/// Test determinisim when serializing anonymous decls. Create enough Decls in
+/// DeclContext that can overflow the small storage of SmallPtrSet to make sure
+/// the serialization does not rely on iteration order of SmallPtrSet.
+// RUN: rm -rf %t.dir
+// RUN: split-file %s %t.dir
+// RUN: %clang_cc1 -fmodules -fimplicit-module-maps \
+// RUN:   -fmodules-cache-path=%t.dir/cache -triple x86_64-apple-macosx10.11.0 \
+// RUN:   -I%t.dir/headers %t.dir/main.m -fdisable-module-hash -Wno-visibility
+// RUN: mv %t.dir/cache/A.pcm %t1.pcm
+/// Check the order of the decls first. If LLVM_ENABLE_REVERSE_ITERATION is on,
+/// it will fail the test early if the output is depending on the order of items
+/// in containers that has non-deterministic orders.
+// RUN: llvm-bcanalyzer --dump --disable-histogram %t1.pcm | FileCheck %s
+// RUN: rm -rf %t.dir/cache
+// RUN: %clang_cc1 -fmodules -fimplicit-module-maps \
+// RUN:   -fmodules-cache-path=%t.dir/cache -triple x86_64-apple-macosx10.11.0 \
+// RUN:   -I%t.dir/headers %t.dir/main.m -fdisable-module-hash -Wno-visibility
+// RUN: mv %t.dir/cache/A.pcm %t2.pcm
+// RUN: diff %t1.pcm %t2.pcm
+
+/// Spot check entries to make sure they are in current ordering.
+/// op13 encodes the anonymous decl number which should be in order.
+// CHECK: 
+
Index: clang/lib/Parse/ParseDecl.cpp
===
--- clang/lib/Parse/ParseDecl.cpp
+++ clang/lib/Parse/ParseDecl.cpp
@@ -6987,6 +6987,15 @@
 continue;
   DeclsInPrototype.push_back(ND);
 }
+// Sort DeclsInPrototype based on raw encoding of the source location.
+// Scope::decls() is iterating over a SmallPtrSet so sort the Decls before
+// moving to DeclContext. This provides a stable ordering for traversing
+// Decls in DeclContext, which is important for tasks like ASTWriter for
+// deterministic output.
+llvm::sort(DeclsInPrototype, [](Decl *D1, Decl *D2) {
+  return D1->getLocation().getRawEncoding() <
+ D2->getLocation().getRawEncoding();
+});
   }
 
   // Remember that we parsed a function type, and remember the attributes.
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu added a comment.

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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

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).


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu added a comment.

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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Argyrios Kyrtzidis via Phabricator via cfe-commits]

akyrtzi added a comment.

> 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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

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?)


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu added a comment.

> 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 :)


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu added a comment.

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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

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?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu added a comment.

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 
`` 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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

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?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu added a comment.

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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu updated this revision to Diff 490616.
steven_wu added a comment.

Update tests according to feedback


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

Files:
  clang/lib/Parse/ParseDecl.cpp
  clang/test/Modules/decl-params-determinisim.m

Index: clang/test/Modules/decl-params-determinisim.m
===
--- /dev/null
+++ clang/test/Modules/decl-params-determinisim.m
@@ -0,0 +1,96 @@
+/// Test determinisim when serializing anonymous decls. Create enough Decls in
+/// DeclContext that can overflow the small storage of SmallPtrSet to make sure
+/// the serialization does not rely on iteration order of SmallPtrSet.
+// RUN: rm -rf %t.dir
+// RUN: split-file %s %t.dir
+// RUN: %clang_cc1 -fmodules -fimplicit-module-maps \
+// RUN:   -fmodules-cache-path=%t.dir/cache -triple x86_64-apple-macosx10.11.0 \
+// RUN:   -I%t.dir/headers %t.dir/main.m -fdisable-module-hash -Wno-visibility
+// RUN: mv %t.dir/cache/A.pcm %t1.pcm
+/// Check the order of the decls first. If LLVM_ENABLE_REVERSE_ITERATION is on,
+/// it will fail the test early if the output is depending on the order of items
+/// in containers that has non-deterministic orders.
+// RUN: llvm-bcanalyzer --dump --disable-histogram %t1.pcm | FileCheck %s
+// RUN: rm -rf %t.dir/cache
+// RUN: %clang_cc1 -fmodules -fimplicit-module-maps \
+// RUN:   -fmodules-cache-path=%t.dir/cache -triple x86_64-apple-macosx10.11.0 \
+// RUN:   -I%t.dir/headers %t.dir/main.m -fdisable-module-hash -Wno-visibility
+// RUN: mv %t.dir/cache/A.pcm %t2.pcm
+// RUN: diff %t1.pcm %t2.pcm
+
+/// Spot check entries to make sure they are in current ordering.
+/// op13 encodes the anonymous decl number which should be in order.
+// CHECK: 
+
Index: clang/lib/Parse/ParseDecl.cpp
===
--- clang/lib/Parse/ParseDecl.cpp
+++ clang/lib/Parse/ParseDecl.cpp
@@ -6986,6 +6986,15 @@
 continue;
   DeclsInPrototype.push_back(ND);
 }
+// Sort DeclsInPrototype based on raw encoding of the source location.
+// Scope::decls() is iterating over a SmallPtrSet so sort the Decls before
+// moving to DeclContext. This provides a stable ordering for traversing
+// Decls in DeclContext, which is important for tasks like ASTWriter for
+// deterministic output.
+llvm::sort(DeclsInPrototype, [](Decl *D1, Decl *D2) {
+  return D1->getLocation().getRawEncoding() <
+ D2->getLocation().getRawEncoding();
+});
   }
 
   // Remember that we parsed a function type, and remember the attributes.
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu added a comment.

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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

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?)


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu added a comment.

@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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu added a comment.

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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a subscriber: colinl.
dblaikie added a comment.

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?)


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu added a comment.

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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Thorsten via Phabricator via cfe-commits]

tschuett added a comment.

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


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu added a comment.

@dblaikie Do we have any bots running reverse iteration?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu added a comment.

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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

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?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu added a comment.

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


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu updated this revision to Diff 489587.
steven_wu added a comment.

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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

Files:
  clang/lib/Parse/ParseDecl.cpp
  clang/test/Modules/decl-params-determinisim.m


Index: clang/test/Modules/decl-params-determinisim.m
===
--- /dev/null
+++ clang/test/Modules/decl-params-determinisim.m
@@ -0,0 +1,70 @@
+/// Test determinisim when serializing anonymous decls. Create enough Decls in
+/// DeclContext that can overflow the small storage of SmallPtrSet to make sure
+/// the serialization does not rely on iteration order of SmallPtrSet.
+// RUN: rm -rf %t.dir
+// RUN: split-file %s %t.dir
+// RUN: %clang_cc1 -fmodules -fimplicit-module-maps \
+// RUN:   -fmodules-cache-path=%t.dir/cache -triple x86_64-apple-macosx10.11.0 
\
+// RUN:   -I%t.dir/headers %t.dir/main.m -fdisable-module-hash -Wno-visibility
+// RUN: mv %t.dir/cache/A.pcm %t1.pcm
+// RUN: rm -rf %t.dir/cache
+// RUN: %clang_cc1 -fmodules -fimplicit-module-maps \
+// RUN:   -fmodules-cache-path=%t.dir/cache -triple x86_64-apple-macosx10.11.0 
\
+// RUN:   -I%t.dir/headers %t.dir/main.m -fdisable-module-hash -Wno-visibility
+// RUN: mv %t.dir/cache/A.pcm %t2.pcm
+// RUN: diff %t1.pcm %t2.pcm
+
+//--- headers/a.h
+void f(struct A0 *a0,
+   struct A1 *a1,
+   struct A2 *a2,
+   struct A3 *a3,
+   struct A4 *a4,
+   struct A5 *a5,
+   struct A6 *a6,
+   struct A7 *a7,
+   struct A8 *a8,
+   struct A9 *a9,
+   struct A10 *a10,
+   struct A11 *a11,
+   struct A12 *a12,
+   struct A13 *a13,
+   struct A14 *a14,
+   struct A15 *a15,
+   struct A16 *a16,
+   struct A17 *a17,
+   struct A18 *a18,
+   struct A19 *a19,
+   struct A20 *a20,
+   struct A21 *a21,
+   struct A22 *a22,
+   struct A23 *a23,
+   struct A24 *a24,
+   struct A25 *a25,
+   struct A26 *a26,
+   struct A27 *a27,
+   struct A28 *a28,
+   struct A29 *a29,
+   struct A30 *a30,
+   struct A31 *a31,
+   struct A32 *a32,
+   struct A33 *a33,
+   struct A34 *a34,
+   struct A35 *a35,
+   struct A36 *a36,
+   struct A37 *a37,
+   struct A38 *a38,
+   struct A39 *a39,
+   struct A40 *a40);
+
+
+//--- headers/module.modulemap
+
+module A {
+  header "a.h"
+}
+
+//--- main.m
+
+#import 
+
Index: clang/lib/Parse/ParseDecl.cpp
===
--- clang/lib/Parse/ParseDecl.cpp
+++ clang/lib/Parse/ParseDecl.cpp
@@ -6986,6 +6986,15 @@
 continue;
   DeclsInPrototype.push_back(ND);
 }
+// Sort DeclsInPrototype based on raw encoding of the source location.
+// Scope::decls() is iterating over a SmallPtrSet so sort the Decls before
+// moving to DeclContext. This provides a stable ordering for traversing
+// Decls in DeclContext, which is important for tasks like ASTWriter for
+// deterministic output.
+llvm::sort(DeclsInPrototype, [](Decl *D1, Decl *D2) {
+  return D1->getLocation().getRawEncoding() <
+ D2->getLocation().getRawEncoding();
+});
   }
 
   // Remember that we parsed a function type, and remember the attributes.


Index: clang/test/Modules/decl-params-determinisim.m
===
--- /dev/null
+++ clang/test/Modules/decl-params-determinisim.m
@@ -0,0 +1,70 @@
+/// Test determinisim when serializing anonymous decls. Create enough Decls in
+/// DeclContext that can overflow the small storage of SmallPtrSet to make sure
+/// the serialization does not rely on iteration order of SmallPtrSet.
+// RUN: rm -rf %t.dir
+// RUN: split-file %s %t.dir
+// RUN: %clang_cc1 -fmodules -fimplicit-module-maps \
+// RUN:   -fmodules-cache-path=%t.dir/cache -triple x86_64-apple-macosx10.11.0 \
+// RUN:   -I%t.dir/headers %t.dir/main.m -fdisable-module-hash -Wno-visibility
+// RUN: mv %t.dir/cache/A.pcm %t1.pcm
+// RUN: rm -rf %t.dir/cache
+// RUN: %clang_cc1 -fmodules -fimplicit-module-maps \
+// RUN:   -fmodules-cache-path=%t.dir/cache -triple x86_64-apple-macosx10.11.0 \
+// RUN:   -I%t.dir/headers %t.dir/main.m -fdisable-module-hash -Wno-visibility
+// RUN: mv %t.dir/cache/A.pcm %t2.pcm
+// RUN: diff %t1.pcm %t2.pcm
+
+//--- headers/a.h
+void f(struct A0 *a0,
+   struct A1 *a1,
+   struct A2 *a2,
+   struct A3 *a3,
+   struct 

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Volodymyr Sapsai via Phabricator via cfe-commits]

vsapsai accepted this revision.
vsapsai added a comment.

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




Comment at: clang/lib/Parse/ParseDecl.cpp:6997
+ D2->getLocation().getRawEncoding();
+});
   }

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.



Comment at: clang/test/Modules/decl-params-determinisim.m:15-16
+//--- headers/a.h
+void f(struct A1 *a0,
+   struct A1 *a1,
+   struct A2 *a2,

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


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu updated this revision to Diff 489150.
steven_wu added a comment.

@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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

Files:
  clang/lib/Parse/ParseDecl.cpp
  clang/test/Modules/decl-params-determinisim.m


Index: clang/test/Modules/decl-params-determinisim.m
===
--- /dev/null
+++ clang/test/Modules/decl-params-determinisim.m
@@ -0,0 +1,67 @@
+// RUN: rm -rf %t.dir
+// RUN: split-file %s %t.dir
+// RUN: %clang_cc1 -fmodules -fimplicit-module-maps \
+// RUN:   -fmodules-cache-path=%t.dir/cache -triple x86_64-apple-macosx10.11.0 
\
+// RUN:   -I%t.dir/headers %t.dir/main.m -fdisable-module-hash -Wno-visibility
+// RUN: mv %t.dir/cache/A.pcm %t1.pcm
+// RUN: rm -rf %t.dir/cache
+// RUN: %clang_cc1 -fmodules -fimplicit-module-maps \
+// RUN:   -fmodules-cache-path=%t.dir/cache -triple x86_64-apple-macosx10.11.0 
\
+// RUN:   -I%t.dir/headers %t.dir/main.m -fdisable-module-hash -Wno-visibility
+// RUN: mv %t.dir/cache/A.pcm %t2.pcm
+// RUN: diff %t1.pcm %t2.pcm
+
+//--- headers/a.h
+void f(struct A1 *a0,
+   struct A1 *a1,
+   struct A2 *a2,
+   struct A3 *a3,
+   struct A4 *a4,
+   struct A5 *a5,
+   struct A6 *a6,
+   struct A7 *a7,
+   struct A8 *a8,
+   struct A9 *a9,
+   struct A10 *a10,
+   struct A11 *a11,
+   struct A12 *a12,
+   struct A13 *a13,
+   struct A14 *a14,
+   struct A15 *a15,
+   struct A16 *a16,
+   struct A17 *a17,
+   struct A18 *a18,
+   struct A19 *a19,
+   struct A20 *a20,
+   struct A21 *a21,
+   struct A22 *a22,
+   struct A23 *a23,
+   struct A24 *a24,
+   struct A25 *a25,
+   struct A26 *a26,
+   struct A27 *a27,
+   struct A28 *a28,
+   struct A29 *a29,
+   struct A30 *a30,
+   struct A31 *a31,
+   struct A32 *a32,
+   struct A33 *a33,
+   struct A34 *a34,
+   struct A35 *a35,
+   struct A36 *a36,
+   struct A37 *a37,
+   struct A38 *a38,
+   struct A39 *a39,
+   struct A40 *a40);
+
+
+//--- headers/module.modulemap
+
+module A {
+  header "a.h"
+}
+
+//--- main.m
+
+#import 
+
Index: clang/lib/Parse/ParseDecl.cpp
===
--- clang/lib/Parse/ParseDecl.cpp
+++ clang/lib/Parse/ParseDecl.cpp
@@ -6986,6 +6986,15 @@
 continue;
   DeclsInPrototype.push_back(ND);
 }
+// Sort DeclsInPrototype based on raw encoding of the source location.
+// Scope::decls() is iterating over a SmallPtrSet so sort the Decls before
+// moving to DeclContext. This provides a stable ordering for traversing
+// Decls in DeclContext, which is important for tasks like ASTWriter for
+// deterministic output.
+llvm::sort(DeclsInPrototype, [](Decl *D1, Decl *D2) {
+  return D1->getLocation().getRawEncoding() <
+ D2->getLocation().getRawEncoding();
+});
   }
 
   // Remember that we parsed a function type, and remember the attributes.


Index: clang/test/Modules/decl-params-determinisim.m
===
--- /dev/null
+++ clang/test/Modules/decl-params-determinisim.m
@@ -0,0 +1,67 @@
+// RUN: rm -rf %t.dir
+// RUN: split-file %s %t.dir
+// RUN: %clang_cc1 -fmodules -fimplicit-module-maps \
+// RUN:   -fmodules-cache-path=%t.dir/cache -triple x86_64-apple-macosx10.11.0 \
+// RUN:   -I%t.dir/headers %t.dir/main.m -fdisable-module-hash -Wno-visibility
+// RUN: mv %t.dir/cache/A.pcm %t1.pcm
+// RUN: rm -rf %t.dir/cache
+// RUN: %clang_cc1 -fmodules -fimplicit-module-maps \
+// RUN:   -fmodules-cache-path=%t.dir/cache -triple x86_64-apple-macosx10.11.0 \
+// RUN:   -I%t.dir/headers %t.dir/main.m -fdisable-module-hash -Wno-visibility
+// RUN: mv %t.dir/cache/A.pcm %t2.pcm
+// RUN: diff %t1.pcm %t2.pcm
+
+//--- headers/a.h
+void f(struct A1 *a0,
+   struct A1 *a1,
+   struct A2 *a2,
+   struct A3 *a3,
+   struct A4 *a4,
+   struct A5 *a5,
+   struct A6 *a6,
+   struct A7 *a7,
+   struct A8 *a8,
+   struct A9 *a9,
+   struct A10 *a10,
+   struct A11 *a11,
+   struct A12 *a12,
+   struct A13 *a13,
+   struct A14 *a14,
+   struct A15 *a15,
+   struct A16 *a16,
+   struct A17 *a17,
+   struct A18 *a18,
+   struct A19 *a19,
+   struct A20 *a20,
+   struct A21 *a21,
+   struct A22 *a22,
+   struct A23 *a23,
+   struct A24 *a24,
+   struct A25 *a25,
+   struct A26 *a26,
+   struct A27 *a27,
+   struct A28 *a28,
+   struct A29 *a29,
+   struct A30 *a30,
+   struct A31 *a31,
+   struct A32 *a32,

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu added a comment.

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).


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Argyrios Kyrtzidis via Phabricator via cfe-commits]

akyrtzi added a comment.

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


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Richard Smith - zygoloid via Phabricator via cfe-commits]

rsmith added a comment.

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, sizeof(0 + 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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Argyrios Kyrtzidis via Phabricator via cfe-commits]

akyrtzi accepted this revision.
akyrtzi added a comment.
This revision is now accepted and ready to land.

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


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D141625/new/

https://reviews.llvm.org/D141625

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D141625: [DeclContext] Sort the Decls before adding into DeclContext

[Steven Wu via Phabricator via cfe-commits]

steven_wu created this revision.
steven_wu added reviewers: jansvoboda11, akyrtzi, benlangmuir, vsapsai, rnk, 
dblaikie.
Herald added subscribers: ributzka, mgrang.
Herald added a project: All.
steven_wu requested review of this revision.
Herald added a project: clang.

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


Repository:
  rG LLVM Github Monorepo

https://reviews.llvm.org/D141625

Files:
  clang/lib/Parse/ParseDecl.cpp


Index: clang/lib/Parse/ParseDecl.cpp
===
--- clang/lib/Parse/ParseDecl.cpp
+++ clang/lib/Parse/ParseDecl.cpp
@@ -6986,6 +6986,13 @@
 continue;
   DeclsInPrototype.push_back(ND);
 }
+// Sort DeclsInPrototype based on raw encoding of the source location. This
+// provides a stable iterating order in DeclContext, which is important for
+// tasks like ASTWriter for deterministic output.
+llvm::sort(DeclsInPrototype, [](Decl *D1, Decl *D2) {
+  return D1->getLocation().getRawEncoding() <
+ D2->getLocation().getRawEncoding();
+});
   }
 
   // Remember that we parsed a function type, and remember the attributes.


Index: clang/lib/Parse/ParseDecl.cpp
===
--- clang/lib/Parse/ParseDecl.cpp
+++ clang/lib/Parse/ParseDecl.cpp
@@ -6986,6 +6986,13 @@
 continue;
   DeclsInPrototype.push_back(ND);
 }
+// Sort DeclsInPrototype based on raw encoding of the source location. This
+// provides a stable iterating order in DeclContext, which is important for
+// tasks like ASTWriter for deterministic output.
+llvm::sort(DeclsInPrototype, [](Decl *D1, Decl *D2) {
+  return D1->getLocation().getRawEncoding() <
+ D2->getLocation().getRawEncoding();
+});
   }
 
   // Remember that we parsed a function type, and remember the attributes.
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits