From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pg1-x534.google.com (mail-pg1-x534.google.com [IPv6:2607:f8b0:4864:20::534]) by sourceware.org (Postfix) with ESMTPS id 4B2083858D32 for ; Thu, 7 Jul 2022 14:29:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 4B2083858D32 Received: by mail-pg1-x534.google.com with SMTP id s27so18808381pga.13 for ; Thu, 07 Jul 2022 07:29:12 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent:subject :content-language:to:references:from:in-reply-to :content-transfer-encoding; bh=Il6IwrFomAA5Z++pJ8H6B90WHlO0sOiH9jiCfe4yIEU=; b=w/gsHqo+uq1x/z9oAidioOY8zcNGuwOFneivS+Xe6aJyat6xcLAhp7BejS5BbixgBW JZBsPA7FsHrCwVf6iArwnXoiWtnss8z52HSf76UbXVuWjZa5dDNb2Cuuyg7UEkZ6mTgN YXBjpJD118+6np3SLQ0iBFns/gTcDo3vuBEacP+rVZnQTIGrmrTblof8lJWERI8Zyu4d dAOahJWxdyZPWpbVEV0n/i30QaEMk5vYzJVaVsGMv+FqAb9SkkTX6m/etq5NlfIbhxd7 bQTOOppTsLkVtgdPKdoFKjB6sQ+ifMAtYSrHRn0lmUc7TpZxOyE1+OrGnKEQbGgOC/lW vCXQ== X-Gm-Message-State: AJIora+ixWARftO7id8MSKUiDpVjJ39OVb5wYnmV+b56uzH/eQdjQwsA Acbqe+RAmqFl6TUXDI7w34LT7lpHrsg= X-Google-Smtp-Source: AGRyM1tzAsvvkF5MoKyhNrefuamuFxrMgO7e4UUe5RGhjlywFGnhawMUScuWv+udWTHb8XIHuvDuZA== X-Received: by 2002:a17:902:7893:b0:16a:6d44:2556 with SMTP id q19-20020a170902789300b0016a6d442556mr51394373pll.166.1657204150877; Thu, 07 Jul 2022 07:29:10 -0700 (PDT) Received: from [172.31.0.204] (c-73-63-24-84.hsd1.ut.comcast.net. [73.63.24.84]) by smtp.gmail.com with ESMTPSA id r22-20020a63fc56000000b0041154ac0f1csm18757509pgk.44.2022.07.07.07.29.10 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 07 Jul 2022 07:29:10 -0700 (PDT) Message-ID: <4807a9ba-f715-7527-dc18-c95281af331d@gmail.com> Date: Thu, 7 Jul 2022 08:29:09 -0600 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Thunderbird/91.10.0 Subject: Re: [PATCH][RFC] More update-ssa speedup Content-Language: en-US To: gcc-patches@gcc.gnu.org References: <20220707133323.1C4993856094@sourceware.org> From: Jeff Law In-Reply-To: <20220707133323.1C4993856094@sourceware.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-2.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, 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-List-Received-Date: Thu, 07 Jul 2022 14:29:14 -0000 On 7/7/2022 7:33 AM, Richard Biener via Gcc-patches wrote: > When we do TODO_update_ssa_no_phi we already avoid computing > dominance frontiers for all blocks - it is worth to also avoid > walking all dominated blocks in the update domwalk and restrict > the walk to the SEME region with the affected blocks. We can > do that by walking the CFG in reverse from blocks_to_update to > the common immediate dominator, marking blocks in the region > and telling the domwalk to STOP when leaving it. > > For an artificial testcase with N adjacent loops with one > unswitching opportunity that takes the incremental SSA updating > off the -ftime-report radar: > > tree loop unswitching : 11.25 ( 3%) 0.09 ( 5%) 11.53 ( 3%) 36M ( 9%) > `- tree SSA incremental : 35.74 ( 9%) 0.07 ( 4%) 36.65 ( 9%) 2734k ( 1%) > > improves to > > tree loop unswitching : 10.21 ( 3%) 0.05 ( 3%) 11.50 ( 3%) 36M ( 9%) > `- tree SSA incremental : 0.66 ( 0%) 0.02 ( 1%) 0.49 ( 0%) 2734k ( 1%) > > for less localized updates the SEME region isn't likely constrained > enough so I've restricted the extra work to TODO_update_ssa_no_phi > callers. > > Bootstrap & regtest running on x86_64-unknown-linux-gnu. > > It's probably the last change that makes a visible difference for > general update-ssa and any specialized manual updating that would be > possible as well would not show up in better numbers than above > (unless I manage to complicate the testcase more). > > Comments? > > Thanks, > Richard. > > * tree-into-ssa.cc (rewrite_mode::REWRITE_UPDATE_REGION): New. > (rewrite_update_dom_walker::rewrite_update_dom_walker): Update. > (rewrite_update_dom_walker::m_in_region_flag): New. > (rewrite_update_dom_walker::before_dom_children): If the region > to update is marked, STOP at exits. > (rewrite_blocks): For REWRITE_UPDATE_REGION mark the region > to be updated. > (dump_update_ssa): Use bitmap_empty_p. > (update_ssa): Likewise. Use REWRITE_UPDATE_REGION when > TODO_update_ssa_no_phi. > * tree-cfgcleanup.cc (cleanup_tree_cfg_noloop): Account > pending update_ssa to the caller. Overall concept seems quite reasonable to me -- it also largely mirrors ideas I was exploring for incremental DOM many years ago. Jeff