From patchwork Tue May 5 15:02:05 2026 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Waffl3x X-Patchwork-Id: 134499 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from vm01.sourceware.org (localhost [127.0.0.1]) by sourceware.org (Postfix) with ESMTP id 227AD4BA9038 for ; Tue, 5 May 2026 15:17:15 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 227AD4BA9038 Authentication-Results: sourceware.org; dkim=pass (2048-bit key, unprotected) header.d=baylibre-com.20251104.gappssmtp.com header.i=@baylibre-com.20251104.gappssmtp.com header.a=rsa-sha256 header.s=20251104 header.b=f5M2Fzym X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-pf1-x432.google.com (mail-pf1-x432.google.com [IPv6:2607:f8b0:4864:20::432]) by sourceware.org (Postfix) with ESMTPS id 10FD84BA9034 for ; Tue, 5 May 2026 15:10:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 10FD84BA9034 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=baylibre.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=baylibre.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 10FD84BA9034 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::432 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1777993849; cv=none; b=Az1WOwvIUHOkQ+GHZoZ81Oo7nIwcV/gA7PuIV79HepX99JxRd1UWpQ7NyI+rmYjbtjsKB/rJ8QNZVw2zDR26bEB+GaWeUq1MeBbRFR5/n8RWN7L4pqYBO59Ij7Z3q8DYseMVeS6+fqK5wYuGXXOH+IjRUoIVVuE/19BmNQ5o75E= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1777993849; c=relaxed/simple; bh=cayDpVIMfIzVOLaAPcYBk3NwL7vxsX3nXeq6HfDg7vk=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=pRgh/zNdsNEnB5TwPYLMm91KMNdoWYz7av6RuaqtTF/7C7zIIRO2QszOms4za1trOKZEAiJGNfMwklNZyTKw9ynJ0hE6mIebYr/5a8GN2hjpIPEfOP84uyMr2Rrz0pMwTz7D84L9rO0kk6eoSkugsDXO2uiRUCNkKwgyYihl+ik= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 10FD84BA9034 Received: by mail-pf1-x432.google.com with SMTP id d2e1a72fcca58-826dab01bbdso200994b3a.0 for ; Tue, 05 May 2026 08:10:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=baylibre-com.20251104.gappssmtp.com; s=20251104; t=1777993848; x=1778598648; darn=gcc.gnu.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=17twbgtCGIUEk1yX1pJPUHPRSkOOgtZcPpiMPKK7G24=; b=f5M2FzymZ3kFUH5TnpwOcjJE+hJXLd4+cIsghDT77t/KlFcMcTFpvmkc0vlqhAlg/y Sx59mb7vE7MDkI8GaDL9Tu0VJZA9UvxVtoAU5ZC/Ighz6g9oOso3a/S7gOVvtV2Yudad VD/vEO46yGNuYzqa8DOBOkdAc6qL4Le/h7K0o/0RPUBpGL9BIRxZekJtuRpExwKYlz6r XAVJ10IMQuFFUKmPcKe0NaGGC6/H6BMYiyPFDCe3CNHZL6BNa4qleK/rPNIoI54Sc7nZ /FwDBaXcWCYwrIS73czz9GnO4QvYwiY1LCqaT6SLiz/yoD/PHahVWJ75KsuC73C1OXuy 0I2A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1777993848; x=1778598648; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=17twbgtCGIUEk1yX1pJPUHPRSkOOgtZcPpiMPKK7G24=; b=T+snWWgymVNjkyIqKjQBBA089+flDbN5Zcul8skjQ+NSibrr0Yu7DjK0QZlxzS1AHU mK/9VDty4ijUrw1fPFj5nk47Xm1FnCDjdBI9Cb3S6yl7l2keVY3Vhj2WRkg1AZq9Yzmo 4N5ey0Zpyxe8RJv5bikKue/mFF+ApSV3ZjQn/K1M+gcvewXbWvOUfdQZkUpU9iF5ZhEA nlasxUiEPKunfJrgJ0fL4gVsXbh+lRWhcTzcxTc0IyQWYjCeY7zuqGuZouZHfcfLeHwC WM09ZGbSZkw6kgu5Djyc+5AmREvoLn2+fLPSsWuFZ0+KMa34nEy1R3lrQX2sHoFU/QZl pZIQ== X-Gm-Message-State: AOJu0YwA0N+s7MKrnFdW2MYIfq2YoiWcWMCqC3Sy7ZhXsyttNYl5Xzka eErfaCFiQFVi+aBjvRguUwlb7nLhuJ2FKCgYAOI6ZLe2qUWkd3sFdwUnKCBmoEaB7JCtw8TxW/O Zva69 X-Gm-Gg: AeBDievIirSQ6POaT+mVh/kyj7PWs59E66HeF6J+ge6xvWbL0asrP+Yj5ZfVSJEa5xg d7Y+sEh3Ib6ppbY6l0T8et81hpi1gHbrdPn4Nba33hJ7GhvnGBlX7e1HBeGe8Kld6h/YKlPYfuK 9E9B9t0ZObyjrRATixSDW57g7gAtTgNQ2pki2wjrshkwDVCErlsnuU1ShJ0GxRfwg6mDvccQ74O lod32JiUWbVANgNmO2G71e02jv4t7JgggVwB1pwjLjJtexi8lFHTcOKS72GTbkh2iWnVDCNa2dW 1anR15eLTzmus2bLaRYQEWqF4n9nZiKS6q1QThTqX0hj6bjp3G4vV6WgXTs1uTphHaD/Cqun1AQ L/jUvV4804wf+kye5go4xUCl5savNBgIb2rasV/V7CLM3W0e00TjsOWMVgxhxOFRN03H0G5AFUG dOY1XVmDVJTXGU8xoQsGichMLQtMv/Ob0OX14qrgRZkcYM4e30dw== X-Received: by 2002:a05:6a00:1f17:b0:82d:1faf:775f with SMTP id d2e1a72fcca58-8393e36240bmr1520875b3a.5.1777993847936; Tue, 05 May 2026 08:10:47 -0700 (PDT) Received: from waffl3x-prestige.lan ([2001:56a:f98a:b800:1f67:ce08:3cbd:86b8]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-83965645140sm2674956b3a.12.2026.05.05.08.10.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 05 May 2026 08:10:47 -0700 (PDT) From: Waffl3x To: gcc-patches@gcc.gnu.org Cc: Waffl3x Subject: [PATCH 12/12] OpenMP/C++: Avoid quadratic complexity in diagnostic Date: Tue, 5 May 2026 09:02:05 -0600 Message-ID: <20260505151030.1749548-13-waffl3x@baylibre.com> X-Mailer: git-send-email 2.54.0 In-Reply-To: <20260505151030.1749548-1-waffl3x@baylibre.com> References: <20260505151030.1749548-1-waffl3x@baylibre.com> MIME-Version: 1.0 X-Spam-Status: No, score=-13.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~patchwork=sourceware.org@gcc.gnu.org The previous implementation of var_is_in_scope unfortunately did not avoid quadratic complexity. This implementation utilizes procedural caching to avoid that while also avoiding traversing the entire list of block vars in the current binding level. gcc/cp/ChangeLog: * parser.cc (cp_parser_omp_allocate): Change var_is_in_scope. Signed-off-by: Waffl3x --- gcc/cp/parser.cc | 54 +++++++++++++++++++++++++++++++----------------- 1 file changed, 35 insertions(+), 19 deletions(-) diff --git a/gcc/cp/parser.cc b/gcc/cp/parser.cc index fe628be065c..4f30b83666c 100644 --- a/gcc/cp/parser.cc +++ b/gcc/cp/parser.cc @@ -47195,25 +47195,41 @@ cp_parser_omp_allocate (cp_parser *parser, cp_token *pragma_tok) what ultimately gets passed along to finish_omp_allocate. */ hash_map arg_map; { - auto var_is_in_scope = [&] (tree var_decl) - { - /* (OpenMP 6.0 311:11-12) An allocate directive must appear in the same - scope as the declarations of each of its list items and must follow - all such declarations. - - Note that it states declarations, not definitions, thus we can rely - on VAR_DECL's CP_DECL_CONTEXT. This will correctly reject an - allocate directive applied to a definition in a different scope. */ - if (!DECL_DECLARES_FUNCTION_P (directive_ctx)) - return CP_DECL_CONTEXT (var_decl) == directive_ctx; - /* This is O(n^2), caching names during traversal might be better. */ - for (tree block_var = current_binding_level->names; - block_var != NULL_TREE; - block_var = DECL_CHAIN (block_var)) - if (block_var == var_decl) - return true; - return false; - }; + /* To avoid quadratic complexity in the block scope case we need to keep + some state. Our hash_set utility has a lazy option, but it sucks so + we'll just bite the allocation unconditionally. */ + auto var_is_in_scope + = [&, vars_in_scope = hash_set(), + block_var = current_binding_level->names] (tree var_decl) mutable + { + /* (OpenMP 6.0 311:11-12) An allocate directive must appear in the + same scope as the declarations of each of its list items and + must follow all such declarations. + + Note that it states declarations, not definitions, well-formed + uses of this directive will always be in the same scope as the + DECL_CONTEXT of VAR_DECL. */ + if (!DECL_DECLARES_FUNCTION_P (directive_ctx)) + return CP_DECL_CONTEXT (var_decl) == directive_ctx; + /* We can't rely on this for block scope though and must traverse + the decls in this scope instead. + As noted above, to avoid quadratic complexity we keep state + across multiple calls, caching as we go to avoid going through + all names in this scope up front. */ + if (vars_in_scope.contains (var_decl)) + return true; + /* We initialize block_var in the captures. */ + for (; block_var != NULL_TREE; block_var = DECL_CHAIN (block_var)) + { + /* Matches don't have to be cached, duplicate var_decl args are + diagnosed before scope is diagnosed. */ + if (block_var == var_decl) + return true; + else if (VAR_P (block_var)) + vars_in_scope.add (block_var); + } + return false; + }; hash_map seen_args; /* The head might have an error and need to be removed. */ tree *chain = &nl;