Add inherited attributes before parsed attributes.

[Meinersbur]

Summary

Currently, attributes from previous declarations ('inherited attributes') are added to the end of a declaration's list of attributes. Before r338800, the attribute list was in reverse. r338800 changed the order of non-inherited (parsed from the current declaration) attributes, but inherited attributes are still appended to the end of the list.

This patch appends inherited attributes after other inherited attributes, but before any non-inherited attribute. This is to make the order of attributes in the AST correspond to the order in the source code.

[erichkeane]

IMO, I think this (and the next 2 numerically), show to me that we have too much dependence on the order of attributes, which all of these show is not a reliable thing to count on. I quite dislike this as well, and think this is going to lead us to chasing these same issues forever.

I wonder if the solution here is to just sort the attributes by source location? This would create that guarantee, which previously didn't exist.

[Meinersbur]

For this patch the goal is to have the attributes in the AST in an order that is less surprising to consumers (including out-of-tree). If we change it now, new/revised code/diagnostics will be written to match this order.

I agree that ideally, most attributes (exceptions are e.g. enable_if) should be more like a set than a list, but I don't think we can get rid of the 'ordered-ness' in general.

I though about ordering by SourceLocation as well and could be implemented like this:
Add all SLoc's sequences for two SourceLocation to lists. Start comparing from the bottom (=> the translation units) until there is a difference.

However, I dislike the idea that the result could potentially depend on SourceLocation that previously was only used when emitting diagnostics.

test/Misc/ast-dump-attr.cpp

228–230

Note that before rC338800, these were mixed-up (not even the reverse order)

test/Sema/attr-availability-ios.c

10

Note that the deprecated marker moved to the line that actually declares the function as deprecated.

[aaron.ballman]

In general, I think this is the right way to go. I've added @rsmith to the reviewers because I'm curious what his thoughts are on this approach, though.

lib/AST/DeclBase.cpp

854–859

The unfortunate part about this is that inherited attributes are fairly common, so this extra searching may happen more often than we'd like. I wonder how bad it would be to keep track of the location within the list where the inherited attributes start. Then again, the list of attributes should be relatively short in most cases, so this search isn't likely to be too expensive.

Having some performance measurements might help decide this, too.

[Meinersbur]

lib/AST/DeclBase.cpp

854–859

Timed clang-compilation using perf (perf stat bin/clang llvm/unittests/IR/InstructionsTest.cpp ...), before this patch (r339574):

   7647.415800      task-clock (msec)         #    0.983 CPUs utilized
           289      context-switches          #    0.038 K/sec
            26      cpu-migrations            #    0.003 K/sec
        86,494      page-faults               #    0.011 M/sec
19,068,741,863      cycles                    #    2.493 GHz
26,581,355,844      instructions              #    1.39  insn per cycle
 6,242,394,037      branches                  #  816.275 M/sec
   128,405,656      branch-misses             #    2.06% of all branches

   7.779848330 seconds time elapsed

With this patch:

   7679.173467      task-clock (msec)         #    0.987 CPUs utilized
           321      context-switches          #    0.042 K/sec
            23      cpu-migrations            #    0.003 K/sec
        86,071      page-faults               #    0.011 M/sec
19,150,248,538      cycles                    #    2.494 GHz
26,667,465,697      instructions              #    1.39  insn per cycle
 6,262,381,898      branches                  #  815.502 M/sec
   128,527,669      branch-misses             #    2.05% of all branches

   7.779477815 seconds time elapsed

(Intel(R) Xeon(R) Platinum 8180M CPU @ 2.50GHz)

The vector insert operation is also be O(n). If the number of non-inherited is expected to be smaller, we can instead search for the first inherited attribute starting at the end of the vector. If we want to avoid the O(n) entirely, we need one list for inherited and another for non-inherited attributes.

[aaron.ballman]

lib/AST/DeclBase.cpp

854–859

Thank you for gathering this data -- those perf numbers look reasonable to me. We can refactor for performance later if it ever turns up on the hot path.

[Meinersbur]

ping

[aaron.ballman]

LGTM!

[Meinersbur]

Commited as rL342861.

include/clang/AST/DeclBase.h

public:
   }
 
   AttrVec &getAttrs() {
     return const_cast<AttrVec&>(const_cast<const Decl*>(this)->getAttrs());
   }
 
   const AttrVec &getAttrs() const;
   void dropAttrs();
-
-  void addAttr(Attr *A) {
-    if (hasAttrs())
-      getAttrs().push_back(A);
-    else
-      setAttrs(AttrVec(1, A));
-  }
+  void addAttr(Attr *A);
 
   using attr_iterator = AttrVec::const_iterator;
   using attr_range = llvm::iterator_range<attr_iterator>;
 
   attr_range attrs() const {
     return attr_range(attr_begin(), attr_end());
   }
 

lib/AST/DeclBase.cpp

 
 void Decl::dropAttrs() {
   if (!HasAttrs) return;
 
   HasAttrs = false;
   getASTContext().eraseDeclAttrs(this);
 }
 
+void Decl::addAttr(Attr *A) {
+  if (!hasAttrs()) {
+    setAttrs(AttrVec(1, A));
+    return;
+  }
+
+  AttrVec &Attrs = getAttrs();
+  if (!A->isInherited()) {
+    Attrs.push_back(A);
+    return;
+  }
+
+  // Attribute inheritance is processed after attribute parsing. To keep the
+  // order as in the source code, add inherited attributes before non-inherited
+  // ones.
+  auto I = Attrs.begin(), E = Attrs.end();
+  for (; I != E; ++I) {
+    if (!(*I)->isInherited())
+      break;
+  }
+  Attrs.insert(I, A);
+}
+
 const AttrVec &Decl::getAttrs() const {
   assert(HasAttrs && "No attrs to get!");
   return getASTContext().getDeclAttrs(this);
 }
 
 Decl *Decl::castFromDeclContext (const DeclContext *D) {
   Decl::Kind DK = D->getDeclKind();
   switch(DK) {

test/Misc/ast-dump-attr.cpp

void f() {
       [[gsl::suppress("on-stmt")]] {
       // CHECK: AttributedStmt
       // CHECK-NEXT: SuppressAttr{{.*}} on-stmt
       // CHECK-NEXT: CompoundStmt
         i = reinterpret_cast<int*>(7);
       }
     }
 }
+
+// Verify the order of attributes in the Ast. It must reflect the order
+// in the parsed source.
+int mergeAttrTest() __attribute__((deprecated)) __attribute__((warn_unused_result));
+int mergeAttrTest() __attribute__((annotate("test")));
+int mergeAttrTest() __attribute__((unused,no_thread_safety_analysis));
+// CHECK: FunctionDecl{{.*}} mergeAttrTest
+// CHECK-NEXT: DeprecatedAttr
+// CHECK-NEXT: WarnUnusedResultAttr
+
+// CHECK: FunctionDecl{{.*}} mergeAttrTest
+// CHECK-NEXT: DeprecatedAttr{{.*}} Inherited
+// CHECK-NEXT: WarnUnusedResultAttr{{.*}} Inherited
+// CHECK-NEXT: AnnotateAttr{{.*}}
+
+// CHECK: FunctionDecl{{.*}} mergeAttrTest
+// CHECK-NEXT: DeprecatedAttr{{.*}} Inherited
+// CHECK-NEXT: WarnUnusedResultAttr{{.*}} Inherited
+// CHECK-NEXT: AnnotateAttr{{.*}} Inherited
+// CHECK-NEXT: UnusedAttr
+// CHECK-NEXT: NoThreadSafetyAnalysisAttr

test/Sema/attr-availability-ios.c

 // RUN: %clang_cc1 "-triple" "x86_64-apple-ios3.0" -fsyntax-only -verify %s
 
 void f0(int) __attribute__((availability(ios,introduced=2.0,deprecated=2.1))); // expected-note {{'f0' has been explicitly marked deprecated here}}
 void f1(int) __attribute__((availability(ios,introduced=2.1)));
 void f2(int) __attribute__((availability(iOS,introduced=2.0,deprecated=3.0))); // expected-note {{'f2' has been explicitly marked deprecated here}}
 void f3(int) __attribute__((availability(ios,introduced=3.0)));
 void f4(int) __attribute__((availability(macosx,introduced=10.1,deprecated=10.3,obsoleted=10.5), availability(ios,introduced=2.0,deprecated=2.1,obsoleted=3.0))); // expected-note{{explicitly marked unavailable}}
 
 void f5(int) __attribute__((availability(ios,introduced=2.0))) __attribute__((availability(ios,deprecated=3.0))); // expected-note {{'f5' has been explicitly marked deprecated here}}
-void f6(int) __attribute__((availability(ios,deprecated=3.0)));
-void f6(int) __attribute__((availability(iOS,introduced=2.0))); // expected-note {{'f6' has been explicitly marked deprecated here}}
+void f6(int) __attribute__((availability(ios,deprecated=3.0))); // expected-note {{'f6' has been explicitly marked deprecated here}}
+void f6(int) __attribute__((availability(iOS,introduced=2.0)));
 
 void test() {
   f0(0); // expected-warning{{'f0' is deprecated: first deprecated in iOS 2.1}}
   f1(0);
   f2(0); // expected-warning{{'f2' is deprecated: first deprecated in iOS 3.0}}
   f3(0);
   f4(0); // expected-error{{f4' is unavailable: obsoleted in iOS 3.0}}
   f5(0); // expected-warning{{'f5' is deprecated: first deprecated in iOS 3.0}}
   f6(0); // expected-warning{{'f6' is deprecated: first deprecated in iOS 3.0}}
 }

test/Sema/attr-availability-tvos.c

 // RUN: %clang_cc1 "-triple" "x86_64-apple-tvos3.0" -fsyntax-only -verify %s
 
 void f0(int) __attribute__((availability(tvos,introduced=2.0,deprecated=2.1))); // expected-note {{'f0' has been explicitly marked deprecated here}}
 void f1(int) __attribute__((availability(tvos,introduced=2.1)));
 void f2(int) __attribute__((availability(tvos,introduced=2.0,deprecated=3.0))); // expected-note {{'f2' has been explicitly marked deprecated here}}
 void f3(int) __attribute__((availability(tvos,introduced=3.0)));
 void f4(int) __attribute__((availability(macosx,introduced=10.1,deprecated=10.3,obsoleted=10.5), availability(tvos,introduced=2.0,deprecated=2.1,obsoleted=3.0))); // expected-note{{explicitly marked unavailable}}
 
 void f5(int) __attribute__((availability(tvos,introduced=2.0))) __attribute__((availability(tvos,deprecated=3.0))); // expected-note {{'f5' has been explicitly marked deprecated here}}
-void f6(int) __attribute__((availability(tvos,deprecated=3.0)));
-void f6(int) __attribute__((availability(tvos,introduced=2.0))); // expected-note {{'f6' has been explicitly marked deprecated here}}
+void f6(int) __attribute__((availability(tvos,deprecated=3.0))); // expected-note {{'f6' has been explicitly marked deprecated here}}
+void f6(int) __attribute__((availability(tvos,introduced=2.0)));
 
 void test() {
   f0(0); // expected-warning{{'f0' is deprecated: first deprecated in tvOS 2.1}}
   f1(0);
   f2(0); // expected-warning{{'f2' is deprecated: first deprecated in tvOS 3.0}}
   f3(0);
   f4(0); // expected-error{{f4' is unavailable: obsoleted in tvOS 3.0}}
   f5(0); // expected-warning{{'f5' is deprecated: first deprecated in tvOS 3.0}}

 void f1_tvos(int) __attribute__((availability(tvos,introduced=2.1)));
 void f2_tvos(int) __attribute__((availability(tvOS,introduced=2.0,deprecated=3.0))); // expected-note {{'f2_tvos' has been explicitly marked deprecated here}}
 void f3_tvos(int) __attribute__((availability(tvos,introduced=3.0)));
 void f4_tvos(int) __attribute__((availability(macosx,introduced=10.1,deprecated=10.3,obsoleted=10.5), availability(tvos,introduced=2.0,deprecated=2.1,obsoleted=3.0))); // expected-note{{explicitly marked unavailable}}
 void f5_tvos(int) __attribute__((availability(tvos,introduced=2.0))) __attribute__((availability(ios,deprecated=3.0)));
 void f5_attr_reversed_tvos(int) __attribute__((availability(ios, deprecated=3.0))) __attribute__((availability(tvos,introduced=2.0)));
 void f5b_tvos(int) __attribute__((availability(tvos,introduced=2.0))) __attribute__((availability(tvos,deprecated=3.0))); // expected-note {{'f5b_tvos' has been explicitly marked deprecated here}}
 void f5c_tvos(int) __attribute__((availability(ios,introduced=2.0))) __attribute__((availability(ios,deprecated=3.0))); // expected-note {{'f5c_tvos' has been explicitly marked deprecated here}}
-void f6_tvos(int) __attribute__((availability(tvos,deprecated=3.0)));
-void f6_tvos(int) __attribute__((availability(tvOS,introduced=2.0))); // expected-note {{'f6_tvos' has been explicitly marked deprecated here}}
+void f6_tvos(int) __attribute__((availability(tvos,deprecated=3.0))); // expected-note {{'f6_tvos' has been explicitly marked deprecated here}}
+void f6_tvos(int) __attribute__((availability(tvOS,introduced=2.0)));
 
 void test_tvos() {
   f0_tvos(0); // expected-warning{{'f0_tvos' is deprecated: first deprecated in tvOS 2.1}}
   f1_tvos(0);
   f2_tvos(0); // expected-warning{{'f2_tvos' is deprecated: first deprecated in tvOS 3.0}}
   f3_tvos(0);
   f4_tvos(0); // expected-error{{'f4_tvos' is unavailable: obsoleted in tvOS 3.0}}
   // We get no warning here because any explicit 'tvos' availability causes

test/Sema/attr-availability-watchos.c

 void f1_watchos(int) __attribute__((availability(watchos,introduced=2.1)));
 void f2_watchos(int) __attribute__((availability(watchOS,introduced=2.0,deprecated=3.0))); // expected-note {{'f2_watchos' has been explicitly marked deprecated here}}
 void f3_watchos(int) __attribute__((availability(watchos,introduced=3.0)));
 void f4_watchos(int) __attribute__((availability(macosx,introduced=10.1,deprecated=10.3,obsoleted=10.5), availability(watchos,introduced=2.0,deprecated=2.1,obsoleted=3.0))); // expected-note{{explicitly marked unavailable}}
 void f5_watchos(int) __attribute__((availability(watchos,introduced=2.0))) __attribute__((availability(ios,deprecated=3.0)));
 void f5_attr_reversed_watchos(int) __attribute__((availability(ios, deprecated=3.0))) __attribute__((availability(watchos,introduced=2.0)));
 void f5b_watchos(int) __attribute__((availability(watchos,introduced=2.0))) __attribute__((availability(watchos,deprecated=3.0))); // expected-note {{'f5b_watchos' has been explicitly marked deprecated here}}
 void f5c_watchos(int) __attribute__((availability(ios,introduced=2.0))) __attribute__((availability(ios,deprecated=3.0))); // expected-note {{'f5c_watchos' has been explicitly marked deprecated here}}
-void f6_watchos(int) __attribute__((availability(watchos,deprecated=3.0)));
-void f6_watchos(int) __attribute__((availability(watchOS,introduced=2.0))); // expected-note {{'f6_watchos' has been explicitly marked deprecated here}}
+void f6_watchos(int) __attribute__((availability(watchos,deprecated=3.0))); // expected-note {{'f6_watchos' has been explicitly marked deprecated here}}
+void f6_watchos(int) __attribute__((availability(watchOS,introduced=2.0)));
 
 void test_watchos() {
   f0_watchos(0); // expected-warning{{'f0_watchos' is deprecated: first deprecated in watchOS 2.1}}
   f1_watchos(0);
   f2_watchos(0); // expected-warning{{'f2_watchos' is deprecated: first deprecated in watchOS 3.0}}
   f3_watchos(0);
   f4_watchos(0); // expected-error{{'f4_watchos' is unavailable: obsoleted in watchOS 3.0}}
   // We get no warning here because any explicit 'watchos' availability causes