[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

1090

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

1090

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

1090

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 {}
+  virtual void collectPropertiesToImplement(PropertyMap &PM) const {}
 
   SourceLocation getAtStartLoc() const { return ObjCContainerDeclBits.AtStart; }
 
   void setAtStartLoc(SourceLocation Loc) {
     ObjCContainerDeclBits.AtStart = Loc;
   }
 
   // Marks the end of the container.
public:
   void setCategoryListRaw(ObjCCategoryDecl *category) {
     data().CategoryList = category;
   }
 
   ObjCPropertyDecl
     *FindPropertyVisibleInPrimaryClass(IdentifierInfo *PropertyId,
                                        ObjCPropertyQueryKind QueryKind) const;
 
-  void collectPropertiesToImplement(PropertyMap &PM,
-                                    PropertyDeclOrder &PO) const override;
+  void collectPropertiesToImplement(PropertyMap &PM) const override;
 
   /// isSuperClassOf - Return true if this class is the specified class or is a
   /// super class of the specified interface class.
   bool isSuperClassOf(const ObjCInterfaceDecl *I) const {
     // If RHS is derived from LHS it is OK; else it is not OK.
     while (I != nullptr) {
       if (declaresSameEntity(this, I))
         return true;
public:
   using redeclarable_base::getPreviousDecl;
   using redeclarable_base::getMostRecentDecl;
   using redeclarable_base::isFirstDecl;
 
   /// Retrieves the canonical declaration of this Objective-C protocol.
   ObjCProtocolDecl *getCanonicalDecl() override { return getFirstDecl(); }
   const ObjCProtocolDecl *getCanonicalDecl() const { return getFirstDecl(); }
 
-  void collectPropertiesToImplement(PropertyMap &PM,
-                                    PropertyDeclOrder &PO) const override;
+  void collectPropertiesToImplement(PropertyMap &PM) const override;
 
   void collectInheritedProtocolProperties(const ObjCPropertyDecl *Property,
                                           ProtocolPropertySet &PS,
                                           PropertyDeclOrder &PO) const;
 
   static bool classof(const Decl *D) { return classofKind(D->getKind()); }
   static bool classofKind(Kind K) { return K == ObjCProtocol; }
 };

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/lib/AST/DeclObjC.cpp

ObjCInterfaceDecl::FindPropertyVisibleInPrimaryClass(
   for (const auto *I : all_referenced_protocols())
     if (ObjCPropertyDecl *P = I->FindPropertyDeclaration(PropertyId,
                                                          QueryKind))
       return P;
 
   return nullptr;
 }
 
-void ObjCInterfaceDecl::collectPropertiesToImplement(PropertyMap &PM,
-                                                     PropertyDeclOrder &PO) const {
+void ObjCInterfaceDecl::collectPropertiesToImplement(PropertyMap &PM) const {
   for (auto *Prop : properties()) {
     PM[std::make_pair(Prop->getIdentifier(), Prop->isClassProperty())] = Prop;
-    PO.push_back(Prop);
   }
   for (const auto *Ext : known_extensions()) {
     const ObjCCategoryDecl *ClassExt = Ext;
     for (auto *Prop : ClassExt->properties()) {
       PM[std::make_pair(Prop->getIdentifier(), Prop->isClassProperty())] = Prop;
-      PO.push_back(Prop);
     }
   }
   for (const auto *PI : all_referenced_protocols())
-    PI->collectPropertiesToImplement(PM, PO);
+    PI->collectPropertiesToImplement(PM);
   // Note, the properties declared only in class extensions are still copied
   // into the main @interface's property list, and therefore we don't
   // explicitly, have to search class extension properties.
 }
 
 bool ObjCInterfaceDecl::isArcWeakrefUnavailable() const {
   const ObjCInterfaceDecl *Class = this;
   while (Class) {

 void ObjCProtocolDecl::startDefinition() {
   allocateDefinitionData();
 
   // Update all of the declarations with a pointer to the definition.
   for (auto *RD : redecls())
     RD->Data = this->Data;
 }
 
-void ObjCProtocolDecl::collectPropertiesToImplement(PropertyMap &PM,
-                                                    PropertyDeclOrder &PO) const {
+void ObjCProtocolDecl::collectPropertiesToImplement(PropertyMap &PM) const {
   if (const ObjCProtocolDecl *PDecl = getDefinition()) {
     for (auto *Prop : PDecl->properties()) {
       // Insert into PM if not there already.
       PM.insert(std::make_pair(
           std::make_pair(Prop->getIdentifier(), Prop->isClassProperty()),
           Prop));
-      PO.push_back(Prop);
     }
     // Scan through protocol's protocols.
     for (const auto *PI : PDecl->protocols())
-      PI->collectPropertiesToImplement(PM, PO);
+      PI->collectPropertiesToImplement(PM);
   }
 }
 
 void ObjCProtocolDecl::collectInheritedProtocolProperties(
     const ObjCPropertyDecl *Property, ProtocolPropertySet &PS,
     PropertyDeclOrder &PO) const {
   if (const ObjCProtocolDecl *PDecl = getDefinition()) {
     if (!PS.insert(PDecl).second)

clang/lib/Sema/SemaObjCProperty.cpp

 }
 
 /// CollectSuperClassPropertyImplementations - This routine collects list of
 /// properties to be implemented in super class(s) and also coming from their
 /// conforming protocols.
 static void CollectSuperClassPropertyImplementations(ObjCInterfaceDecl *CDecl,
                                     ObjCInterfaceDecl::PropertyMap &PropMap) {
   if (ObjCInterfaceDecl *SDecl = CDecl->getSuperClass()) {
-    ObjCInterfaceDecl::PropertyDeclOrder PO;
     while (SDecl) {
-      SDecl->collectPropertiesToImplement(PropMap, PO);
+      SDecl->collectPropertiesToImplement(PropMap);
       SDecl = SDecl->getSuperClass();
     }
   }
 }
 
 /// IvarBacksCurrentMethodAccessor - This routine returns 'true' if 'IV' is
 /// an ivar synthesized for 'Method' and 'Method' is a property accessor
 /// declared in class 'IFace'.

 }
 
 /// Default synthesizes all properties which must be synthesized
 /// in class's \@implementation.
 void Sema::DefaultSynthesizeProperties(Scope *S, ObjCImplDecl *IMPDecl,
                                        ObjCInterfaceDecl *IDecl,
                                        SourceLocation AtEnd) {
   ObjCInterfaceDecl::PropertyMap PropMap;
-  ObjCInterfaceDecl::PropertyDeclOrder PropertyOrder;
-  IDecl->collectPropertiesToImplement(PropMap, PropertyOrder);
+  IDecl->collectPropertiesToImplement(PropMap);
   if (PropMap.empty())
     return;
   ObjCInterfaceDecl::PropertyMap SuperPropMap;
   CollectSuperClassPropertyImplementations(IDecl, SuperPropMap);
 
-  for (unsigned i = 0, e = PropertyOrder.size(); i != e; i++) {
-    ObjCPropertyDecl *Prop = PropertyOrder[i];
+  for (const auto &PropEntry : PropMap) {
+    ObjCPropertyDecl *Prop = PropEntry.second;
     // Is there a matching property synthesize/dynamic?
     if (Prop->isInvalidDecl() ||
         Prop->isClassProperty() ||
         Prop->getPropertyImplementation() == ObjCPropertyDecl::Optional)
       continue;
     // Property may have been synthesized by user.
     if (IMPDecl->FindPropertyImplDecl(
             Prop->getIdentifier(), Prop->getQueryKind()))
void Sema::DiagnoseUnimplementedProperties(Scope *S, ObjCImplDecl* IMPDecl,
   // Gather properties which need not be implemented in this class
   // or category.
   if (!IDecl)
     if (ObjCCategoryDecl *C = dyn_cast<ObjCCategoryDecl>(CDecl)) {
       // For categories, no need to implement properties declared in
       // its primary class (and its super classes) if property is
       // declared in one of those containers.
       if ((IDecl = C->getClassInterface())) {
-        ObjCInterfaceDecl::PropertyDeclOrder PO;
-        IDecl->collectPropertiesToImplement(NoNeedToImplPropMap, PO);
+        IDecl->collectPropertiesToImplement(NoNeedToImplPropMap);
       }
     }
   if (IDecl)
     CollectSuperClassPropertyImplementations(IDecl, NoNeedToImplPropMap);
 
   // When SynthesizeProperties is true, we only check class properties.
   CollectImmediateProperties(CDecl, PropMap, NoNeedToImplPropMap,
                              SynthesizeProperties/*CollectClassPropsOnly*/);

clang/lib/StaticAnalyzer/Checkers/IvarInvalidationChecker.cpp

visit(const ObjCImplementationDecl *ImplD) const {
   // Construct Property/Property Accessor to Ivar maps to assist checking if an
   // ivar which is backing a property has been reset.
   MethToIvarMapTy PropSetterToIvarMap;
   MethToIvarMapTy PropGetterToIvarMap;
   PropToIvarMapTy PropertyToIvarMap;
   IvarToPropMapTy IvarToPopertyMap;
 
   ObjCInterfaceDecl::PropertyMap PropMap;
-  ObjCInterfaceDecl::PropertyDeclOrder PropOrder;
-  InterfaceD->collectPropertiesToImplement(PropMap, PropOrder);
+  InterfaceD->collectPropertiesToImplement(PropMap);
 
   for (ObjCInterfaceDecl::PropertyMap::iterator
       I = PropMap.begin(), E = PropMap.end(); I != E; ++I) {
     const ObjCPropertyDecl *PD = I->second;
     if (PD->isClassProperty())
       continue;
 
     const ObjCIvarDecl *ID = findPropertyBackingIvar(PD, InterfaceD, Ivars,

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'