Add optimization to sizeof...(X) handling: if none of parameter pack X's

corresponding arguments are unexpanded pack expansions, we can compute the
result without substituting them. This significantly improves the memory usage
and performance of make_integer_sequence implementations that do this kind of
thing:

  using result = integer_sequence<T, Ns ..., sizeof...(Ns) + Ns ...>;

... but note that such an implementation will still perform O(sizeof...(Ns)^2)
work while building the second pack expansion (we just have a somewhat lower
constant now).

In principle we could get this down to linear time by caching whether the
number of expansions of a pack is constant, or checking whether we're within an
alias template before scanning the pack for pack expansions (since that's the
only case in which we do substitutions within a dependent context at the
moment), but this patch doesn't attempt that.


git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@284653 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 58 insertions, 1 deletions

diff --git a/lib/Sema/SemaTemplateVariadic.cpp b/lib/Sema/SemaTemplateVariadic.cpp
index 06afe87f51..b6bd6c03ff 100644
--- a/lib/Sema/SemaTemplateVariadic.cpp
+++ b/lib/Sema/SemaTemplateVariadic.cpp
@@ -639,7 +639,7 @@ bool Sema::CheckParameterPacksForExpansion(
       return true;
     }
   }
-  
+
   return false;
 }
 
@@ -936,6 +936,63 @@ Sema::getTemplateArgumentPackExpansionPattern(
   llvm_unreachable("Invalid TemplateArgument Kind!");
 }
 
+Optional<unsigned> Sema::getFullyPackExpandedSize(TemplateArgument Arg) {
+  assert(Arg.containsUnexpandedParameterPack());
+
+  // If this is a substituted pack, grab that pack. If not, we don't know
+  // the size yet.
+  // FIXME: We could find a size in more cases by looking for a substituted
+  // pack anywhere within this argument, but that's not necessary in the common
+  // case for 'sizeof...(A)' handling.
+  TemplateArgument Pack;
+  switch (Arg.getKind()) {
+  case TemplateArgument::Type:
+    if (auto *Subst = Arg.getAsType()->getAs<SubstTemplateTypeParmPackType>())
+      Pack = Subst->getArgumentPack();
+    else
+      return None;
+    break;
+
+  case TemplateArgument::Expression:
+    if (auto *Subst =
+            dyn_cast<SubstNonTypeTemplateParmPackExpr>(Arg.getAsExpr()))
+      Pack = Subst->getArgumentPack();
+    else if (auto *Subst = dyn_cast<FunctionParmPackExpr>(Arg.getAsExpr()))  {
+      for (ParmVarDecl *PD : *Subst)
+        if (PD->isParameterPack())
+          return None;
+      return Subst->getNumExpansions();
+    } else
+      return None;
+    break;
+
+  case TemplateArgument::Template:
+    if (SubstTemplateTemplateParmPackStorage *Subst =
+            Arg.getAsTemplate().getAsSubstTemplateTemplateParmPack())
+      Pack = Subst->getArgumentPack();
+    else
+      return None;
+    break;
+
+  case TemplateArgument::Declaration:
+  case TemplateArgument::NullPtr:
+  case TemplateArgument::TemplateExpansion:
+  case TemplateArgument::Integral:
+  case TemplateArgument::Pack:
+  case TemplateArgument::Null:
+    return None;
+  }
+
+  // Check that no argument in the pack is itself a pack expansion.
+  for (TemplateArgument Elem : Pack.pack_elements()) {
+    // There's no point recursing in this case; we would have already
+    // expanded this pack expansion into the enclosing pack if we could.
+    if (Elem.isPackExpansion())
+      return None;
+  }
+  return Pack.pack_size();
+}
+
 static void CheckFoldOperand(Sema &S, Expr *E) {
   if (!E)
     return;