[gnu-objc] Make selector order deterministic.

[theraven]

Summary

This probably fixes PR35277, though there may be other sources of
nondeterminism (this was the only case of iterating over a DenseMap).

It's difficult to provide a test case for this, because it shows up only
on systems with ASLR enabled.

[mgrang]

Does the error show up if you build llvm with -DLLVM_REVERSE_ITERATION:ON?

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.

[bmwiedemann]

got a build failure with this patch added onto 6.0.1

lib/CodeGen/CGObjCGNU.cpp

3547

compilation failed here:
../tools/clang/lib/CodeGen/CGObjCGNU.cpp:2444:11: error: 'sort' is not a member of 'llvm'

it suggested std::sort

[mgrang]

In D50559#1195787, @bmwiedemann wrote:

got a build failure with this patch added onto 6.0.1

You may have to add:

#include "llvm/ADT/STLExtras.h"

[rjmccall]

You can't test that there's no non-determinism, but you can certainly test that we emit selectors in sorted order as opposed to the order in which they're used. I imagine a function with a bunch of @selector expressions should be good enough for that.

[theraven]

lib/CodeGen/CGObjCGNU.cpp

3547

I'm not sure llvm::sort was part of the 6.0 release, it was added in April and so should be in 7.0. I don't expect a patch against the 8 branch to apply cleanly to 6...

[bmwiedemann]

I got it compiled with std::sort on top of 6.0.1 and found that it indeed removes the indeterminism: When I compiled libobjc2-1.8.1/arc.m 25 times, I got the same md5sum every time - and the same result with and without ASLR.

[theraven]

• Add a test case.

[rjmccall]

Thanks. I appreciate the fact that you spelled it all out in the test, too.

LGTM.

lib/CodeGen/CGObjCGNU.cpp

3547

array_pod_sort has been around forever if we need a variant of the patch for that branch.

lib/CodeGen/CGObjCGNU.cpp

llvm::Function *CGObjCGNU::ModuleInitFunction() {
   SmallVector<llvm::GlobalAlias*, 16> selectorAliases;
   unsigned selectorCount;
 
   // Pointer to an array of selectors used in this module.
   llvm::GlobalVariable *selectorList = [&] {
     ConstantInitBuilder builder(CGM);
     auto selectors = builder.beginArray(selStructTy);
     auto &table = SelectorTable; // MSVC workaround
-    for (auto &entry : table) {
+    std::vector<Selector> allSelectors;
+    for (auto &entry : table)
+      allSelectors.push_back(entry.first);
+    llvm::sort(allSelectors.begin(), allSelectors.end());
 
-      std::string selNameStr = entry.first.getAsString();
+    for (auto &untypedSel : allSelectors) {
+      std::string selNameStr = untypedSel.getAsString();
       llvm::Constant *selName = ExportUniqueString(selNameStr, ".objc_sel_name");
 
-      for (TypedSelector &sel : entry.second) {
+      for (TypedSelector &sel : table[untypedSel]) {
         llvm::Constant *selectorTypeEncoding = NULLPtr;
         if (!sel.first.empty())
           selectorTypeEncoding =
             MakeConstantString(sel.first, ".objc_sel_types");
 
         auto selStruct = selectors.beginStruct(selStructTy);
         selStruct.add(selName);
         selStruct.add(selectorTypeEncoding);

test/CodeGenObjC/gnu-deterministic-selectors.m

+// RUN: %clang_cc1 -triple x86_64-unknown-freebsd -fobjc-runtime=gnustep-1.5 %s -emit-llvm -o - | FileCheck %s
+// RUN: %clang_cc1 -triple x86_64-unknown-freebsd -fobjc-runtime=gcc %s -emit-llvm -o - | FileCheck %s
+
+// Check that these selectors are emitted in alphabetical order.
+// The order doesn't actually matter, only that it doesn't vary across runs.
+// Clang sorts them when targeting a GCC-like ABI to guarantee determinism.
+// CHECK: @.objc_selector_list = internal global [6 x { i8*, i8* }] [{ i8*, i8* } { i8* getelementptr inbounds ([2 x i8], [2 x i8]* @.objc_sel_namea, i64 0, i64 0), i8* null }, { i8*, i8* } { i8* getelementptr inbounds ([2 x i8], [2 x i8]* @.objc_sel_nameg, i64 0, i64 0), i8* null }, { i8*, i8* } { i8* getelementptr inbounds ([2 x i8], [2 x i8]* @.objc_sel_namej, i64 0, i64 0), i8* null }, { i8*, i8* } { i8* getelementptr inbounds ([2 x i8], [2 x i8]* @.objc_sel_namel, i64 0, i64 0), i8* null }, { i8*, i8* } { i8* getelementptr inbounds ([2 x i8], [2 x i8]* @.objc_sel_namez, i64 0, i64 0), i8* null }, { i8*, i8* } zeroinitializer], align 8
+
+
+void f() {
+  SEL a = @selector(z);
+  SEL b = @selector(a);
+  SEL c = @selector(g);
+  SEL d = @selector(l);
+  SEL e = @selector(j);
+}