https://github.com/AnonMiraj updated https://github.com/llvm/llvm-project/pull/213790
>From d89bdae8e715629b8199f400be0a46359ba26f1f Mon Sep 17 00:00:00 2001 From: Anonmiraj <[email protected]> Date: Tue, 4 Aug 2026 00:50:04 +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 | 10 +++- clang/lib/AST/ComputeDependence.cpp | 6 ++- clang/lib/AST/ExprCXX.cpp | 14 +++-- clang/lib/Sema/TreeTransform.h | 84 +++++++++++++++++++++++++++++ 6 files changed, 115 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 530bfe72dac2b..c614fda53a636 100644 --- a/clang/include/clang/AST/TypeBase.h +++ b/clang/include/clang/AST/TypeBase.h @@ -6464,7 +6464,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 02a3f88431f58..3223ac0298838 100644 --- a/clang/lib/AST/ASTContext.cpp +++ b/clang/lib/AST/ASTContext.cpp @@ -6825,7 +6825,15 @@ 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; keeping the whole + // expansion list would make each pack-indexing instantiation O(N). + 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..ceaccfdb18fe2 100644 --- a/clang/lib/AST/ExprCXX.cpp +++ b/clang/lib/AST/ExprCXX.cpp @@ -1741,9 +1741,17 @@ 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; keeping the whole + // expansion list would make pack-indexing instantiation O(N). + 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..bf1cdaf5db9b7 100644 --- a/clang/lib/Sema/TreeTransform.h +++ b/clang/lib/Sema/TreeTransform.h @@ -7099,6 +7099,13 @@ template <typename Derived> QualType TreeTransform<Derived>::TransformPackIndexingType(TypeLocBuilder &TLB, PackIndexingTypeLoc TL) { + // An already-resolved (non-dependent) 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 +7174,48 @@ 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(); + // NumExpansions is only a lower bound when the pack's argument still + // contains an unexpanded pack (GH116105), so V >= NumExpansions is not + // necessarily out of bounds: fall through to the full expansion, which + // lets Sema::BuildPackIndexingType diagnose a genuine OOB index. + 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 +16962,41 @@ 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(); + // NumExpansions is only a lower bound when the pack's argument still + // contains an unexpanded pack (GH116105), so V >= NumExpansions is not + // necessarily out of bounds: fall through to the full expansion, which + // lets Sema::BuildPackIndexingExpr diagnose a genuine OOB index. + 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 b72637f0989a95a5928d6df5a9104cc0eb422a8d Mon Sep 17 00:00:00 2001 From: Anonmiraj <[email protected]> Date: Tue, 4 Aug 2026 19:36:45 +0300 Subject: [PATCH 2/3] Fix the test --- clang/test/CodeGenCXX/mangle-cxx2c.cpp | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/clang/test/CodeGenCXX/mangle-cxx2c.cpp b/clang/test/CodeGenCXX/mangle-cxx2c.cpp index 1dd5c7e4af264..b0d38aeb1a3d7 100644 --- a/clang/test/CodeGenCXX/mangle-cxx2c.cpp +++ b/clang/test/CodeGenCXX/mangle-cxx2c.cpp @@ -17,8 +17,9 @@ 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 +// The index selects a non-dependent element (int) of an otherwise partially +// substituted pack, so First<I, int, V...> resolves to int. +// CHECK-LABEL: define {{.*}} @_ZN8GH1120033bazILi0EJiEEEvi template <int I, typename...V> void baz(First<I, int, V...>){}; >From c59990c0bb957d746a3d7cb0202cc3fb4e5231a4 Mon Sep 17 00:00:00 2001 From: Anonmiraj <[email protected]> Date: Tue, 4 Aug 2026 19:47:35 +0300 Subject: [PATCH 3/3] fix formatting --- clang/include/clang/AST/ExprCXX.h | 5 +++-- clang/lib/Sema/TreeTransform.h | 3 +-- 2 files changed, 4 insertions(+), 4 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 bf1cdaf5db9b7..071c2ec7fa8a8 100644 --- a/clang/lib/Sema/TreeTransform.h +++ b/clang/lib/Sema/TreeTransform.h @@ -7203,8 +7203,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( _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
