From patchwork Tue Jun 6 07:21:31 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 103598 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp3205463vqr; Tue, 6 Jun 2023 00:22:34 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ7F5Kscabr21jzN2TudZzPUjgsSbo6fqn4rb5ihkgBO0zeE6EL0S/8Yys3MMnwIQLy6jriv X-Received: by 2002:aa7:cf0e:0:b0:50b:f778:5bf5 with SMTP id a14-20020aa7cf0e000000b0050bf7785bf5mr1423447edy.38.1686036153985; Tue, 06 Jun 2023 00:22:33 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1686036153; cv=none; d=google.com; s=arc-20160816; b=vmsrbbMMedZB/0Rt78z5p0bq5gfG8ITCUnT7WQyWcfXMogtacpC1QUZQJjQNMF/d2Y YNwKNcoyhqg/P+QJGFSDzMpMMUuGG+PXUu/JqUo30i4Tw0ZFy9JgO1ouzo6Hx0AoMcRR qY9jDnz5QUcCH65xxvUu1mgH9iOLzNaIZSJMdVPF4mia6SknjqAvAxsT7jtA8kC/6Ohm kekSkcKwjyTpSIfssVe5J6LuwDVjDxDeerHZR88tZji1OxWfyU3l8OhqgU06UjWr3kWW 5yedlyPDaZgdUH/PpZ8TXrZn6lM+ahcsv2CYzXIb1D+0tQAOsXp88913ndSyXfeFnERJ w96A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=message-id:sender:errors-to:reply-to:from:list-subscribe:list-help :list-post:list-archive:list-unsubscribe:list-id:precedence :mime-version:user-agent:subject:to:date:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=u5UDCLSDOZbetIE8t4IuLbL7OhEQBKDmVXM1MHEahkg=; b=bcDhWrvgRutG44/3ozQLsDu9DOjkiTM2cq6t+L57n5gykbZ59cqOEpSbuWhPUN+KWt +749zuxXgFZt/U5mD7QyOROp1GDjd37vzJWfDJF/YNQtjm/7pY3S6L/JZaeYc/foI3Pp rY/lfikzFE/dvdE4UCrzizg6CnRi2q1IkO8/v8OOa08ygwF3olOivOWbCUFeRLup4EHP 95gsV14HbkLiV7geA0/YZxgDK810lgDB+q4xTakEuWIst0rbfGFCln6R9LMzMVj88GEO SwQAaginO1w+6CjthQV0e54a5UdZCprMpFDoBA4Ud+GwuTFApk8/zeIGZ7IZDeiAl+j5 mI/Q== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=IedXv3Yw; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id c10-20020aa7df0a000000b0051062e32fd2si5795665edy.68.2023.06.06.00.22.33 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 06 Jun 2023 00:22:33 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=IedXv3Yw; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B9A05385700C for ; Tue, 6 Jun 2023 07:22:15 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B9A05385700C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1686036135; bh=u5UDCLSDOZbetIE8t4IuLbL7OhEQBKDmVXM1MHEahkg=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=IedXv3YwcYXPfPB7qBJKRDYaG23DcpkFzCe32sP9uBxwcoZbX5Y900WVr8S0DfKBi r/SbxNpCXZ+GE30NwLQrMAHVUTkrP8kBqme3OQO57gZxTqHqL9A5c+p+YSMNrSoRSS z54qg5OyqN7SUdwblS5Xt6bM+n7Idhmsj3DQ0aPY= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id 038353858031 for ; Tue, 6 Jun 2023 07:21:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 038353858031 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id D4C931FD5F for ; Tue, 6 Jun 2023 07:21:31 +0000 (UTC) Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id CB0C42C141 for ; Tue, 6 Jun 2023 07:21:31 +0000 (UTC) Date: Tue, 6 Jun 2023 07:21:31 +0000 (UTC) To: gcc-patches@gcc.gnu.org Subject: [PATCH] tree-optimization/109143 - improve PTA compile time User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 X-Spam-Status: No, score=-10.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, MISSING_MID, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" Message-Id: <20230606072215.B9A05385700C@sourceware.org> X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1767937046253740004?= X-GMAIL-MSGID: =?utf-8?q?1767937046253740004?= The following improves solution_set_expand to require one less iteration over the bitmap and avoid changing the bitmap we iterate over. Plus we handle adjacent subvars in the ID space (the common case) and use bitmap_set_range. This cuts a bit less than 10% off the PTA time from the testcase in the PR. Bootstrapped and tested on x86_64-unknwon-linux-gnu, pushed. PR tree-optimization/109143 * tree-ssa-structalias.cc (solution_set_expand): Avoid one bitmap iteration and optimize bit range setting. --- gcc/tree-ssa-structalias.cc | 38 ++++++++++++++++++++++++------------- 1 file changed, 25 insertions(+), 13 deletions(-) diff --git a/gcc/tree-ssa-structalias.cc b/gcc/tree-ssa-structalias.cc index 8db99a42565..ee9313c59ca 100644 --- a/gcc/tree-ssa-structalias.cc +++ b/gcc/tree-ssa-structalias.cc @@ -966,28 +966,40 @@ solution_set_expand (bitmap set, bitmap *expanded) *expanded = BITMAP_ALLOC (&iteration_obstack); - /* In a first pass expand to the head of the variables we need to - add all sub-fields off. This avoids quadratic behavior. */ + /* In a first pass expand variables, once for each head to avoid + quadratic behavior, to include all sub-fields. */ + unsigned prev_head = 0; EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi) { varinfo_t v = get_varinfo (j); if (v->is_artificial_var || v->is_full_var) continue; - bitmap_set_bit (*expanded, v->head); - } + if (v->head != prev_head) + { + varinfo_t head = get_varinfo (v->head); + unsigned num = 1; + for (varinfo_t n = vi_next (head); n != NULL; n = vi_next (n)) + { + if (n->id != head->id + num) + { + /* Usually sub variables are adjacent but since we + create pointed-to restrict representatives there + can be gaps as well. */ + bitmap_set_range (*expanded, head->id, num); + head = n; + num = 1; + } + else + num++; + } - /* In the second pass now expand all head variables with subfields. */ - EXECUTE_IF_SET_IN_BITMAP (*expanded, 0, j, bi) - { - varinfo_t v = get_varinfo (j); - if (v->head != j) - continue; - for (v = vi_next (v); v != NULL; v = vi_next (v)) - bitmap_set_bit (*expanded, v->id); + bitmap_set_range (*expanded, head->id, num); + prev_head = v->head; + } } - /* And finally set the rest of the bits from SET. */ + /* And finally set the rest of the bits from SET in an efficient way. */ bitmap_ior_into (*expanded, set); return *expanded;