https://github.com/AnonMiraj updated https://github.com/llvm/llvm-project/pull/213790
>From 5c8e46b7828915a70c705146fde9800fd284b3ed Mon Sep 17 00:00:00 2001 From: Anonmiraj <[email protected]> Date: Tue, 4 Aug 2026 22:11:11 +0300 Subject: [PATCH 1/3] [Clang] Avoid quadratic pack-indexing instantiation (store only the selected element) --- clang/include/clang/AST/ExprCXX.h | 5 +- clang/include/clang/AST/TypeBase.h | 4 +- clang/lib/AST/ASTContext.cpp | 9 +++- clang/lib/AST/ComputeDependence.cpp | 6 ++- clang/lib/AST/ExprCXX.cpp | 13 +++-- clang/lib/Sema/TreeTransform.h | 75 +++++++++++++++++++++++++++++ 6 files changed, 104 insertions(+), 8 deletions(-) diff --git a/clang/include/clang/AST/ExprCXX.h b/clang/include/clang/AST/ExprCXX.h index d3d3b9c6d6326..c42c02e5edfcd 100644 --- a/clang/include/clang/AST/ExprCXX.h +++ b/clang/include/clang/AST/ExprCXX.h @@ -4638,7 +4638,10 @@ class PackIndexingExpr final Expr *getSelectedExpr() const { UnsignedOrNone Index = getSelectedIndex(); assert(Index && "extracting the indexed expression of a dependant pack"); - return getTrailingObjects()[*Index]; + // Resolved nodes store only the selected expansion; unresolved nodes store + // the full list and are indexed by the evaluated index. + return getTrailingObjects()[ + PackIndexingExprBits.TransformedExpressions == 1 ? 0 : *Index]; } /// Return the trailing expressions, regardless of the expansion. diff --git a/clang/include/clang/AST/TypeBase.h b/clang/include/clang/AST/TypeBase.h index 4851c4e5185dd..52235edc766b1 100644 --- a/clang/include/clang/AST/TypeBase.h +++ b/clang/include/clang/AST/TypeBase.h @@ -6470,7 +6470,9 @@ class PackIndexingType final QualType getSelectedType() const { assert(hasSelectedType() && "Type is dependant"); - return *(getExpansionsPtr() + *getSelectedIndex()); + // Resolved nodes store only the selected expansion; unresolved nodes store + // the full list and are indexed by the evaluated index. + return getExpansionsPtr()[Size == 1 ? 0 : *getSelectedIndex()]; } UnsignedOrNone getSelectedIndex() const; diff --git a/clang/lib/AST/ASTContext.cpp b/clang/lib/AST/ASTContext.cpp index 5f1e5b30ee50c..b661364410214 100644 --- a/clang/lib/AST/ASTContext.cpp +++ b/clang/lib/AST/ASTContext.cpp @@ -6819,7 +6819,14 @@ QualType ASTContext::getPackIndexingType(QualType Pattern, Expr *IndexExpr, UnsignedOrNone Index) const { QualType Canonical; if (FullySubstituted && Index) { - Canonical = getCanonicalType(Expansions[*Index]); + unsigned SelIdx = Expansions.size() == 1 ? 0 : *Index; + assert(SelIdx < Expansions.size() && "pack index out of bounds"); + QualType Selected = Expansions[SelIdx]; + Canonical = getCanonicalType(Selected); + // Store only the selected element once resolved. + if (!Selected->isInstantiationDependentType() && + !IndexExpr->isInstantiationDependent()) + Expansions = Expansions.slice(SelIdx, 1); } else { llvm::FoldingSetNodeID ID; PackIndexingType::Profile(ID, *this, Pattern.getCanonicalType(), IndexExpr, diff --git a/clang/lib/AST/ComputeDependence.cpp b/clang/lib/AST/ComputeDependence.cpp index a819bb6dec599..657b83393f29c 100644 --- a/clang/lib/AST/ComputeDependence.cpp +++ b/clang/lib/AST/ComputeDependence.cpp @@ -398,8 +398,10 @@ ExprDependence clang::computeDependence(PackIndexingExpr *E) { D |= PatternDep | ExprDependence::Instantiation; else if (!E->getIndexExpr()->isInstantiationDependent()) { UnsignedOrNone Index = E->getSelectedIndex(); - assert(Index && *Index < Exprs.size() && "pack index out of bound"); - D |= Exprs[*Index]->getDependence(); + assert(Index && "pack index out of bound"); + unsigned SelIdx = Exprs.size() == 1 ? 0 : *Index; + assert(SelIdx < Exprs.size() && "pack index out of bound"); + D |= Exprs[SelIdx]->getDependence(); } return D; } diff --git a/clang/lib/AST/ExprCXX.cpp b/clang/lib/AST/ExprCXX.cpp index 6c1cde6540d85..ec35267b9d36c 100644 --- a/clang/lib/AST/ExprCXX.cpp +++ b/clang/lib/AST/ExprCXX.cpp @@ -1741,9 +1741,16 @@ PackIndexingExpr *PackIndexingExpr::Create( Expr *PackIdExpr, Expr *IndexExpr, std::optional<int64_t> Index, ArrayRef<Expr *> SubstitutedExprs, bool FullySubstituted) { QualType Type; - if (Index && FullySubstituted && !SubstitutedExprs.empty()) - Type = SubstitutedExprs[*Index]->getType(); - else + if (Index && FullySubstituted && !SubstitutedExprs.empty()) { + unsigned SelIdx = SubstitutedExprs.size() == 1 ? 0 : *Index; + assert(SelIdx < SubstitutedExprs.size() && "pack index out of bounds"); + Expr *Selected = SubstitutedExprs[SelIdx]; + Type = Selected->getType(); + // Store only the selected element once resolved. + if (!Selected->isInstantiationDependent() && + !IndexExpr->isInstantiationDependent()) + SubstitutedExprs = SubstitutedExprs.slice(SelIdx, 1); + } else Type = PackIdExpr->getType(); void *Storage = diff --git a/clang/lib/Sema/TreeTransform.h b/clang/lib/Sema/TreeTransform.h index 2083fcd372e81..faf0f98b075b1 100644 --- a/clang/lib/Sema/TreeTransform.h +++ b/clang/lib/Sema/TreeTransform.h @@ -7099,6 +7099,12 @@ template <typename Derived> QualType TreeTransform<Derived>::TransformPackIndexingType(TypeLocBuilder &TLB, PackIndexingTypeLoc TL) { + // An already-resolved pack-indexing type has nothing left to substitute. + if (!TL.getType()->isInstantiationDependentType()) { + TLB.pushFullCopy(TL); + return TL.getType(); + } + // Transform the index ExprResult IndexExpr; { @@ -7167,6 +7173,44 @@ TreeTransform<Derived>::TransformPackIndexingType(TypeLocBuilder &TLB, SubtitutedTypes.push_back(Pack); continue; } + // Fast path: substitute only the selected element instead of all N. A + // pack-indexing type inside a pack expansion (`T...[Is]...`) is transformed + // once per outer element, so substituting the whole pack each time is + // O(N^2) in time and memory. + if (!RetainExpansion && Types.size() == 1 && IndexExpr.isUsable() && + !IndexExpr.get()->isInstantiationDependent()) { + llvm::APSInt Value; + ExprResult CCE = SemaRef.CheckConvertedConstantExpression( + IndexExpr.get(), SemaRef.Context.getSizeType(), Value, + CCEKind::PackIndex); + if (!CCE.isUsable() || !Value.isRepresentableByInt64()) + return QualType(); + uint64_t V = Value.getZExtValue(); + if (V < *NumExpansions) { + QualType Selected; + { + Sema::ArgPackSubstIndexRAII SubstIndex(getSema(), + static_cast<unsigned>(V)); + Selected = getDerived().TransformType(T); + } + if (Selected.isNull()) + return QualType(); + if (!Selected->containsUnexpandedParameterPack() && + !Selected->isInstantiationDependentType()) { + Sema::ArgPackSubstIndexRAII SubstIndex(getSema(), std::nullopt); + QualType Result = + getDerived().TransformType(TLB, TL.getPatternLoc()); + if (Result.isNull()) + return QualType(); + QualType Out = SemaRef.Context.getPackIndexingType( + Result, CCE.get(), /*FullySubstituted=*/true, {Selected}, + /*Index=*/0u); + PackIndexingTypeLoc Loc = TLB.push<PackIndexingTypeLoc>(Out); + Loc.setEllipsisLoc(TL.getEllipsisLoc()); + return Out; + } + } + } for (unsigned I = 0; I != *NumExpansions; ++I) { Sema::ArgPackSubstIndexRAII SubstIndex(getSema(), I); QualType Out = getDerived().TransformType(T); @@ -16913,6 +16957,37 @@ TreeTransform<Derived>::TransformPackIndexingExpr(PackIndexingExpr *E) { E->getEllipsisLoc(), E->getRSquareLoc(), Pack.get(), IndexExpr.get(), {}, /*FullySubstituted=*/false); } + // Fast path: see TransformPackIndexingType. + if (!RetainExpansion && IndexExpr.isUsable() && + !IndexExpr.get()->isInstantiationDependent()) { + llvm::APSInt Value( + SemaRef.Context.getIntWidth(SemaRef.Context.getSizeType())); + ExprResult CCE = SemaRef.CheckConvertedConstantExpression( + IndexExpr.get(), SemaRef.Context.getSizeType(), Value, + CCEKind::PackIndex); + if (!CCE.isUsable() || !Value.isRepresentableByInt64()) + return ExprError(); + uint64_t V = Value.getZExtValue(); + if (V < *NumExpansions) { + ExprResult Selected; + { + Sema::ArgPackSubstIndexRAII SubstIndex(getSema(), + static_cast<unsigned>(V)); + Selected = getDerived().TransformExpr(Pattern); + } + if (Selected.isInvalid()) + return ExprError(); + if (!Selected.get()->containsUnexpandedParameterPack() && + !Selected.get()->isInstantiationDependent()) { + Expr *SelectedExpr = Selected.get(); + return PackIndexingExpr::Create( + getSema().getASTContext(), E->getEllipsisLoc(), + E->getRSquareLoc(), E->getPackIdExpression(), CCE.get(), + static_cast<int64_t>(V), SelectedExpr, + /*FullySubstituted=*/true); + } + } + } for (unsigned I = 0; I != *NumExpansions; ++I) { Sema::ArgPackSubstIndexRAII SubstIndex(getSema(), I); ExprResult Out = getDerived().TransformExpr(Pattern); >From f78c065da19b85f7c52ff95f7e482c04b1619e52 Mon Sep 17 00:00:00 2001 From: Anonmiraj <[email protected]> Date: Tue, 4 Aug 2026 22:11:37 +0300 Subject: [PATCH 2/3] fix ci --- clang/include/clang/AST/ExprCXX.h | 5 +++-- clang/lib/Sema/TreeTransform.h | 3 +-- clang/test/CodeGenCXX/mangle-cxx2c.cpp | 3 +-- 3 files changed, 5 insertions(+), 6 deletions(-) diff --git a/clang/include/clang/AST/ExprCXX.h b/clang/include/clang/AST/ExprCXX.h index c42c02e5edfcd..043512e0969a3 100644 --- a/clang/include/clang/AST/ExprCXX.h +++ b/clang/include/clang/AST/ExprCXX.h @@ -4640,8 +4640,9 @@ class PackIndexingExpr final assert(Index && "extracting the indexed expression of a dependant pack"); // Resolved nodes store only the selected expansion; unresolved nodes store // the full list and are indexed by the evaluated index. - return getTrailingObjects()[ - PackIndexingExprBits.TransformedExpressions == 1 ? 0 : *Index]; + return getTrailingObjects()[PackIndexingExprBits.TransformedExpressions == 1 + ? 0 + : *Index]; } /// Return the trailing expressions, regardless of the expansion. diff --git a/clang/lib/Sema/TreeTransform.h b/clang/lib/Sema/TreeTransform.h index faf0f98b075b1..b8738b02ea742 100644 --- a/clang/lib/Sema/TreeTransform.h +++ b/clang/lib/Sema/TreeTransform.h @@ -7198,8 +7198,7 @@ TreeTransform<Derived>::TransformPackIndexingType(TypeLocBuilder &TLB, if (!Selected->containsUnexpandedParameterPack() && !Selected->isInstantiationDependentType()) { Sema::ArgPackSubstIndexRAII SubstIndex(getSema(), std::nullopt); - QualType Result = - getDerived().TransformType(TLB, TL.getPatternLoc()); + QualType Result = getDerived().TransformType(TLB, TL.getPatternLoc()); if (Result.isNull()) return QualType(); QualType Out = SemaRef.Context.getPackIndexingType( diff --git a/clang/test/CodeGenCXX/mangle-cxx2c.cpp b/clang/test/CodeGenCXX/mangle-cxx2c.cpp index 1dd5c7e4af264..3b1d9e58be799 100644 --- a/clang/test/CodeGenCXX/mangle-cxx2c.cpp +++ b/clang/test/CodeGenCXX/mangle-cxx2c.cpp @@ -17,8 +17,7 @@ V...[I] bar() {return {};} template <int I, typename... T> using First = T...[0]; -// CHECK-LABEL: define {{.*}} @_ZN8GH1120033bazILi0EJiEEEvDy_SUBSTPACK_Li0E -// FIXME: handle indexing of partially substituted packs +// CHECK-LABEL: define {{.*}} @_ZN8GH1120033bazILi0EJiEEEvi template <int I, typename...V> void baz(First<I, int, V...>){}; >From 9cb28dc9649b4233192813cc6578e5688961fce7 Mon Sep 17 00:00:00 2001 From: Anonmiraj <[email protected]> Date: Wed, 5 Aug 2026 08:01:33 +0300 Subject: [PATCH 3/3] move the fast path outside the loop --- clang/lib/Sema/TreeTransform.h | 87 +++++++++++++++++++--------------- 1 file changed, 50 insertions(+), 37 deletions(-) diff --git a/clang/lib/Sema/TreeTransform.h b/clang/lib/Sema/TreeTransform.h index b8738b02ea742..71d2c067b65c5 100644 --- a/clang/lib/Sema/TreeTransform.h +++ b/clang/lib/Sema/TreeTransform.h @@ -7127,6 +7127,56 @@ TreeTransform<Derived>::TransformPackIndexingType(TypeLocBuilder &TLB, if (Types.empty() && !PIT->expandsToEmptyPack()) Types = llvm::ArrayRef<QualType>(&Pattern, 1); + // Fast path: substitute only the selected element instead of all N. A + // pack-indexing type inside a pack expansion (`T...[Is]...`) is transformed + // once per outer element, so substituting the whole pack each time is + // O(N^2) in time and memory. + if (Types.size() == 1 && Types[0]->containsUnexpandedParameterPack() && + IndexExpr.isUsable() && !IndexExpr.get()->isInstantiationDependent()) { + QualType T = Types[0]; + SmallVector<UnexpandedParameterPack, 2> Unexpanded; + getSema().collectUnexpandedParameterPacks(T, Unexpanded); + bool ShouldExpand = true, RetainExpansion = false; + UnsignedOrNone NumExpansions = std::nullopt; + if (getDerived().TryExpandParameterPacks( + TL.getEllipsisLoc(), SourceRange(), Unexpanded, + /*FailOnPackProducingTemplates=*/true, ShouldExpand, RetainExpansion, + NumExpansions)) + return QualType(); + if (ShouldExpand && !RetainExpansion) { + llvm::APSInt Value; + ExprResult CCE = SemaRef.CheckConvertedConstantExpression( + IndexExpr.get(), SemaRef.Context.getSizeType(), Value, + CCEKind::PackIndex); + if (!CCE.isUsable() || !Value.isRepresentableByInt64()) + return QualType(); + uint64_t V = Value.getZExtValue(); + if (V < *NumExpansions) { + QualType Selected; + { + Sema::ArgPackSubstIndexRAII SubstIndex(getSema(), + static_cast<unsigned>(V)); + Selected = getDerived().TransformType(T); + } + if (Selected.isNull()) + return QualType(); + if (!Selected->containsUnexpandedParameterPack() && + !Selected->isInstantiationDependentType()) { + Sema::ArgPackSubstIndexRAII SubstIndex(getSema(), std::nullopt); + QualType Result = getDerived().TransformType(TLB, TL.getPatternLoc()); + if (Result.isNull()) + return QualType(); + QualType Out = SemaRef.Context.getPackIndexingType( + Result, CCE.get(), /*FullySubstituted=*/true, {Selected}, + /*Index=*/0u); + PackIndexingTypeLoc Loc = TLB.push<PackIndexingTypeLoc>(Out); + Loc.setEllipsisLoc(TL.getEllipsisLoc()); + return Out; + } + } + } + } + for (QualType T : Types) { if (!T->containsUnexpandedParameterPack()) { QualType Transformed = getDerived().TransformType(T); @@ -7173,43 +7223,6 @@ TreeTransform<Derived>::TransformPackIndexingType(TypeLocBuilder &TLB, SubtitutedTypes.push_back(Pack); continue; } - // Fast path: substitute only the selected element instead of all N. A - // pack-indexing type inside a pack expansion (`T...[Is]...`) is transformed - // once per outer element, so substituting the whole pack each time is - // O(N^2) in time and memory. - if (!RetainExpansion && Types.size() == 1 && IndexExpr.isUsable() && - !IndexExpr.get()->isInstantiationDependent()) { - llvm::APSInt Value; - ExprResult CCE = SemaRef.CheckConvertedConstantExpression( - IndexExpr.get(), SemaRef.Context.getSizeType(), Value, - CCEKind::PackIndex); - if (!CCE.isUsable() || !Value.isRepresentableByInt64()) - return QualType(); - uint64_t V = Value.getZExtValue(); - if (V < *NumExpansions) { - QualType Selected; - { - Sema::ArgPackSubstIndexRAII SubstIndex(getSema(), - static_cast<unsigned>(V)); - Selected = getDerived().TransformType(T); - } - if (Selected.isNull()) - return QualType(); - if (!Selected->containsUnexpandedParameterPack() && - !Selected->isInstantiationDependentType()) { - Sema::ArgPackSubstIndexRAII SubstIndex(getSema(), std::nullopt); - QualType Result = getDerived().TransformType(TLB, TL.getPatternLoc()); - if (Result.isNull()) - return QualType(); - QualType Out = SemaRef.Context.getPackIndexingType( - Result, CCE.get(), /*FullySubstituted=*/true, {Selected}, - /*Index=*/0u); - PackIndexingTypeLoc Loc = TLB.push<PackIndexingTypeLoc>(Out); - Loc.setEllipsisLoc(TL.getEllipsisLoc()); - return Out; - } - } - } for (unsigned I = 0; I != *NumExpansions; ++I) { Sema::ArgPackSubstIndexRAII SubstIndex(getSema(), I); QualType Out = getDerived().TransformType(T); _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
