[clang/Sema] Fix non-deterministic order for certain kind of diagnostics

[akyrtzi]

Summary

In the context of caching clang invocations it is important to emit diagnostics in deterministic order;
the same clang invocation should result in the same diagnostic output.

rdar://100336989

[jansvoboda11]

LGTM

[steven_wu]

LGTM.

RemoveDecl does become more expensive but I don't have better solution. I am also wondering if as follow up we should add an option to VerifyDiagnosticConsumer to be location aware (so the diagnostics from a file is emitted in order) to prevent more problem like this.

[benlangmuir]

clang/include/clang/AST/DeclObjC.h

1091

Can we use the existing PropertyDeclOrder instead of changing the map type? Or else get rid of the PO parameter to functions using PropertyMap if we keep the MapVector?

[akyrtzi]

In D135118#3833978, @steven_wu wrote:

LGTM.

RemoveDecl does become more expensive but I don't have better solution.

Luckily AFAICT this is not a "hot" function.

I am also wondering if as follow up we should add an option to VerifyDiagnosticConsumer to be location aware (so the diagnostics from a file is emitted in order) to prevent more problem like this.

Interesting idea! Something to keep in mind.

[akyrtzi]

clang/include/clang/AST/DeclObjC.h

1091

I'll take a look.

[akyrtzi]

Remove PropertyDeclOrder parameter from the collectPropertiesToImplement functions. This is not necessary with PropertyMap becoming a MapVector.

[akyrtzi]

clang/include/clang/AST/DeclObjC.h

1091

See updated patch.

The diagnostic machinery (e.g. in DiagnoseUnimplementedProperties) for these ObjC diagnostics is using PropertyMap separately from the collectPropertiesToImplement functions, so I kept the map type change and removed PropertyDeclOrder from these functions accepting PropertyMap.
This is better for maintainance since it'd be an easy mistake to add new code that iterates the DenseMap instead of the vector.

[nikic]

FYI this caused a noticeable compile-time regression (about 0.4% geomean at -O0): http://llvm-compile-time-tracker.com/compare.php?from=92233159035d1b50face95d886901cf99035bd99&to=371883f46dc23f8464cbf578e2d12a4f92e61917&stat=instructions

[akyrtzi]

In D135118#3839442, @nikic wrote:

FYI this caused a noticeable compile-time regression (about 0.4% geomean at -O0): http://llvm-compile-time-tracker.com/compare.php?from=92233159035d1b50face95d886901cf99035bd99&to=371883f46dc23f8464cbf578e2d12a4f92e61917&stat=instructions

Thanks for letting me know! I'll take a look.

[akyrtzi]

In D135118#3840259, @akyrtzi wrote:

In D135118#3839442, @nikic wrote:

FYI this caused a noticeable compile-time regression (about 0.4% geomean at -O0): http://llvm-compile-time-tracker.com/compare.php?from=92233159035d1b50face95d886901cf99035bd99&to=371883f46dc23f8464cbf578e2d12a4f92e61917&stat=instructions

Thanks for letting me know! I'll take a look.

Opened https://reviews.llvm.org/D135490

[akyrtzi]

@nikic, it seems to have recovered (http://llvm-compile-time-tracker.com/compare.php?from=c49cde6467f9bf200640db763152a9dc7f009520&to=0456acbfb942f127359a8defd1b4f1f44420df3e&stat=instructions) let me know if you have concerns.

[nikic]

In D135118#3851050, @akyrtzi wrote:

@nikic, it seems to have recovered (http://llvm-compile-time-tracker.com/compare.php?from=c49cde6467f9bf200640db763152a9dc7f009520&to=0456acbfb942f127359a8defd1b4f1f44420df3e&stat=instructions) let me know if you have concerns.

Thanks!

clang/include/clang/AST/DeclObjC.h

 #include "clang/AST/Redeclarable.h"
 #include "clang/AST/SelectorLocationsKind.h"
 #include "clang/AST/Type.h"
 #include "clang/Basic/IdentifierTable.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/Specifiers.h"
 #include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/TrailingObjects.h"
 #include <cassert>
public:
   ObjCPropertyDecl *getProperty(const IdentifierInfo *Id,
                                 bool IsInstance) const;
 
   ObjCPropertyDecl *
   FindPropertyDeclaration(const IdentifierInfo *PropertyId,
                           ObjCPropertyQueryKind QueryKind) const;
 
   using PropertyMap =
-      llvm::DenseMap<std::pair<IdentifierInfo *, unsigned/*isClassProperty*/>,
+      llvm::MapVector<std::pair<IdentifierInfo *, unsigned /*isClassProperty*/>,
                       ObjCPropertyDecl *>;
   using ProtocolPropertySet = llvm::SmallDenseSet<const ObjCProtocolDecl *, 8>;
   using PropertyDeclOrder = llvm::SmallVector<ObjCPropertyDecl *, 8>;
 
   /// This routine collects list of properties to be implemented in the class.
   /// This includes, class's and its conforming protocols' properties.
   /// Note, the superclass's properties are not included in the list.
   virtual void collectPropertiesToImplement(PropertyMap &PM,
                                             PropertyDeclOrder &PO) const {}
 
   SourceLocation getAtStartLoc() const { return ObjCContainerDeclBits.AtStart; }
 
   void setAtStartLoc(SourceLocation Loc) {
     ObjCContainerDeclBits.AtStart = Loc;
   }
 
   // Marks the end of the container.

clang/include/clang/Sema/Scope.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_SEMA_SCOPE_H
 #define LLVM_CLANG_SEMA_SCOPE_H
 
 #include "clang/AST/Decl.h"
 #include "clang/Basic/Diagnostic.h"
 #include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator_range.h"
 #include <cassert>
 
 namespace llvm {
 
 class raw_ostream;
private:
   Scope *TemplateParamParent;
 
   /// DeclsInScope - This keeps track of all declarations in this scope.  When
   /// the declaration is added to the scope, it is set as the current
   /// declaration for the identifier in the IdentifierTable.  When the scope is
   /// popped, these declarations are removed from the IdentifierTable's notion
   /// of current declaration.  It is up to the current Action implementation to
   /// implement these semantics.
-  using DeclSetTy = llvm::SmallPtrSet<Decl *, 32>;
+  using DeclSetTy = llvm::SmallSetVector<Decl *, 32>;
   DeclSetTy DeclsInScope;
 
   /// The DeclContext with which this scope is associated. For
   /// example, the entity of a class scope is the class itself, the
   /// entity of a function scope is a function, etc.
   DeclContext *Entity;
 
   using UsingDirectivesTy = SmallVector<UsingDirectiveDecl *, 2>;
public:
   void AddDecl(Decl *D) {
     if (auto *VD = dyn_cast<VarDecl>(D))
       if (!isa<ParmVarDecl>(VD))
         ReturnSlots.insert(VD);
 
     DeclsInScope.insert(D);
   }
 
-  void RemoveDecl(Decl *D) {
-    DeclsInScope.erase(D);
-  }
+  void RemoveDecl(Decl *D) { DeclsInScope.remove(D); }
 
   void incrementMSManglingNumber() {
     if (Scope *MSLMP = getMSLastManglingParent()) {
       MSLMP->MSLastManglingNumber += 1;
       MSCurManglingNumber += 1;
     }
   }
 
public:
   }
 
   unsigned getMSCurManglingNumber() const {
     return MSCurManglingNumber;
   }
 
   /// isDeclScope - Return true if this is the scope that the specified decl is
   /// declared in.
-  bool isDeclScope(const Decl *D) const { return DeclsInScope.contains(D); }
+  bool isDeclScope(const Decl *D) const {
+    return DeclsInScope.contains(const_cast<Decl *>(D));
+  }
 
   /// Get the entity corresponding to this scope.
   DeclContext *getEntity() const {
     return isTemplateParamScope() ? nullptr : Entity;
   }
 
   /// Get the DeclContext in which to continue unqualified lookup after a
   /// lookup in this scope.

clang/test/Sema/deterministic-diagnostics-order.m

+// RUN: %clang_cc1 %s -fsyntax-only -Wobjc-property-implementation -Watomic-property-with-user-defined-accessor -Wunused 2> %t.err
+// RUN: FileCheck -input-file=%t.err %s
+
+@interface I
+@end
+
+@interface I(cat)
+@property id prop1;
+@property id prop2;
+@property id prop3;
+@end
+
+@implementation I(cat)
+@end
+
+// CHECK: warning: property 'prop1' requires method
+// CHECK: warning: property 'prop2' requires method
+// CHECK: warning: property 'prop3' requires method
+
+@interface I2
+@property int prop1;
+@property int prop2;
+@property int prop3;
+@end
+
+@implementation I2
+@synthesize prop1, prop2, prop3;
+-(int) prop1 { return 0; }
+-(int) prop2 { return 0; }
+-(int) prop3 { return 0; }
+@end
+
+// CHECK: warning: writable atomic property 'prop1'
+// CHECK: warning: writable atomic property 'prop2'
+// CHECK: warning: writable atomic property 'prop3'
+
+void test_unused() {
+  // Add enough variables to exceed the small storage of Scope::DeclSetTy.
+  int v1;
+  int v2;
+  int v3;
+  int v4;
+  int v5;
+  int v6;
+  int v7;
+  int v8;
+  int v9;
+  int v10;
+  int v11;
+  int v12;
+  int v13;
+  int v14;
+  int v15;
+  int v16;
+  int v17;
+  int v18;
+  int v19;
+  int v20;
+  int v21;
+  int v22;
+  int v23;
+  int v24;
+  int v25;
+  int v26;
+  int v27;
+  int v28;
+  int v29;
+  int v30;
+  int v31;
+  int v32;
+  int v33;
+  int v34;
+  int v35;
+  int v36;
+  int v37;
+  int v38;
+}
+
+// CHECK: warning: unused variable 'v1'
+// CHECK: warning: unused variable 'v2'
+// CHECK: warning: unused variable 'v3'
+// CHECK: warning: unused variable 'v4'
+// CHECK: warning: unused variable 'v5'
+// CHECK: warning: unused variable 'v6'
+// CHECK: warning: unused variable 'v7'
+// CHECK: warning: unused variable 'v8'
+// CHECK: warning: unused variable 'v9'
+// CHECK: warning: unused variable 'v10'
+// CHECK: warning: unused variable 'v11'
+// CHECK: warning: unused variable 'v12'
+// CHECK: warning: unused variable 'v13'
+// CHECK: warning: unused variable 'v14'
+// CHECK: warning: unused variable 'v15'
+// CHECK: warning: unused variable 'v16'
+// CHECK: warning: unused variable 'v17'
+// CHECK: warning: unused variable 'v18'
+// CHECK: warning: unused variable 'v19'
+// CHECK: warning: unused variable 'v20'
+// CHECK: warning: unused variable 'v21'
+// CHECK: warning: unused variable 'v22'
+// CHECK: warning: unused variable 'v23'
+// CHECK: warning: unused variable 'v24'
+// CHECK: warning: unused variable 'v25'
+// CHECK: warning: unused variable 'v26'
+// CHECK: warning: unused variable 'v27'
+// CHECK: warning: unused variable 'v28'
+// CHECK: warning: unused variable 'v29'
+// CHECK: warning: unused variable 'v30'
+// CHECK: warning: unused variable 'v31'
+// CHECK: warning: unused variable 'v32'
+// CHECK: warning: unused variable 'v33'
+// CHECK: warning: unused variable 'v34'
+// CHECK: warning: unused variable 'v35'
+// CHECK: warning: unused variable 'v36'
+// CHECK: warning: unused variable 'v37'
+// CHECK: warning: unused variable 'v38'