From patchwork Wed Aug 3 09:53:28 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 368 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:6a10:b5d6:b0:2b9:3548:2db5 with SMTP id v22csp233551pxt; Wed, 3 Aug 2022 02:54:14 -0700 (PDT) X-Google-Smtp-Source: AA6agR5YhqbfsBmKt74xlfpjU36ZrFupaFmxZsozUMfp6qsmGowtBeHbL1Jepdoune2PV5KtxNoo X-Received: by 2002:a05:6402:3222:b0:43e:49f9:11e with SMTP id g34-20020a056402322200b0043e49f9011emr1649208eda.426.1659520454466; Wed, 03 Aug 2022 02:54:14 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1659520454; cv=none; d=google.com; s=arc-20160816; b=kq1Y2Gpi9+yvKCMJZu6IvPEdmrPosujaJmw5i9v3Vp86S0tmw/UAcyrIsY9ARElC4s zEhQvPAZTEiETmN/NYlxnP7rKpMBZB57myN9HRKhbeFPrNmSwV95hZolcsxUEO1FoPBQ S/OhSr13nJWgKwfaQaql3oVN044UPx2oZDu7+GVbVvgmw8XGvX5PJmEo1XS7piS9nsOr jBI4PAtTpYIYfFdMdV1CKuT5vJHXElsnhJ1533nbW4o8SKF8fn4aHwBwLGtY8QAZ9tIq gMQZKuixvrZq4HfzRSrO2IpIBO0JHiQ3mC9/96lfiehPbuNbRjZapGXXGOekuM1Ha1i0 yHeg== 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=Lw6f1A11BDPfSQTXyOu10QGWtEFZGIyRWWkT1HxvHKw=; b=IPGCuWGAr+EHR3NdjXlIfjObsnZ9WlgdGF7B4j1QOpXb2e+wzBjoVcATBo3hUGf6Qb gSFhtsRXX6HFBtRRZqZkEcn56umn08XZqvCq4GjxgAtof75rh3HjS+4RObCc+UhDr47x EK7XRVbW8RiEMG2Le6uq5LI1L0uk+N8A3HN5QSIwviNQybZ6whujxmLcdTm9y2z6LXii 4Nzl1QI5kQioM8zV1gSe0fWpqxMyat25LrhZpJl7plousLN2yFXeDizdX5p6j7Em+4hu la9PzWrodI3et00011HAJSSuYd9RTNQgOshnXqCxXBpVtpDT36GkHKGKLMuHjLWhUFJk Qufg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=AhImtgml; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 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. [8.43.85.97]) by mx.google.com with ESMTPS id u23-20020a1709060b1700b0072ae61935afsi16132096ejg.304.2022.08.03.02.54.14 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 03 Aug 2022 02:54:14 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=AhImtgml; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 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 482783858006 for ; Wed, 3 Aug 2022 09:54:13 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 482783858006 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1659520453; bh=Lw6f1A11BDPfSQTXyOu10QGWtEFZGIyRWWkT1HxvHKw=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=AhImtgmlSyWoKIMrK88F3CvxmiQm0Pxex3ao7JG3IQREblvyDZOKbe6ERZ9hGD+Xq yUXLncfMAMz3VRbh4w+jhzNRuBoL/nN5yTiQOBfzFkCuqDt/lUmQyAiBM2uBT5mIvF 9UfhjgH/QeR9stHnYWNXHpkTFxivdDPXpML99FbI= 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 [IPv6:2001:67c:2178:6::1d]) by sourceware.org (Postfix) with ESMTPS id D34443858C20 for ; Wed, 3 Aug 2022 09:53:29 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D34443858C20 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id EF3A21FAD5; Wed, 3 Aug 2022 09:53:28 +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 E79BB2C141; Wed, 3 Aug 2022 09:53:28 +0000 (UTC) Date: Wed, 3 Aug 2022 09:53:28 +0000 (UTC) To: gcc-patches@gcc.gnu.org Subject: [PATCH] Backwards threader greedy search TLC User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 X-Spam-Status: No, score=-10.6 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 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: <20220803095413.482783858006@sourceware.org> X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1740133319762948339?= X-GMAIL-MSGID: =?utf-8?q?1740133319762948339?= I've tried to understand how the greedy search works seeing the bitmap dances and the split into resolve_phi. I've summarized the intent of the algorithm as // For further greedy searching we want to remove interesting // names defined in BB but add ones on the PHI edges for the // respective edges. but the implementation differs in detail. In particular when there is more than one interesting PHI in BB it seems to only consider the first for translating defs across edges. It also only applies the loop crossing restriction when there is an interesting PHI. I've also noticed that while the set of interesting names is rolled back, m_imports just keeps growing - is that a bug? The following preserves the loop crossing restriction to the case of interesting PHIs but merges resolve_phi back, changing interesting as outlined with the intent above. It should get more threading cases when there are multiple interesting PHI defs in a block. It might be a bit faster due to less bitmap operations but in the end the main intent was to make what happens more obvious. Bootstrap and regtest pending on x86_64-unknown-linux-gnu. Aldy - you wrote the existing implementation, is the following OK? Is preserving the grown m_imports intended? I see it's eventually used by find_taken_edge_* when finalizing a path passed as m_solver->compute_ranges (path, m_imports), not sure what the effect is if we keep growing m_imports here? Any other comments? Thanks, Richard. * tree-ssa-threadbackward.cc (populate_worklist): Remove. (back_threader::resolve_phi): Likewise. (back_threader::find_paths_to_names): Rewrite greedy search. --- gcc/tree-ssa-threadbackward.cc | 146 +++++++++++---------------------- 1 file changed, 50 insertions(+), 96 deletions(-) diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc index 3fb05c4c75b..3adced6a9c9 100644 --- a/gcc/tree-ssa-threadbackward.cc +++ b/gcc/tree-ssa-threadbackward.cc @@ -91,7 +91,6 @@ private: edge maybe_register_path (); void maybe_register_path_dump (edge taken_edge); void find_paths_to_names (basic_block bb, bitmap imports); - void resolve_phi (gphi *phi, bitmap imports); edge find_taken_edge (const vec &path); edge find_taken_edge_cond (const vec &path, gcond *); edge find_taken_edge_switch (const vec &path, gswitch *); @@ -337,71 +336,6 @@ back_threader::find_taken_edge_cond (const vec &path, return NULL; } -// Populate a vector of trees from a bitmap. - -static inline void -populate_worklist (vec &worklist, bitmap bits) -{ - bitmap_iterator bi; - unsigned i; - - EXECUTE_IF_SET_IN_BITMAP (bits, 0, i, bi) - { - tree name = ssa_name (i); - worklist.quick_push (name); - } -} - -// Find jump threading paths that go through a PHI. - -void -back_threader::resolve_phi (gphi *phi, bitmap interesting) -{ - if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi))) - return; - - for (size_t i = 0; i < gimple_phi_num_args (phi); ++i) - { - edge e = gimple_phi_arg_edge (phi, i); - - // This is like path_crosses_loops in profitable_path_p but more - // restrictive to avoid peeling off loop iterations (see - // tree-ssa/pr14341.c for an example). - bool profitable_p = m_path[0]->loop_father == e->src->loop_father; - if (!profitable_p) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, - " FAIL: path through PHI in bb%d (incoming bb:%d) crosses loop\n", - e->dest->index, e->src->index); - fprintf (dump_file, "path: %d->", e->src->index); - dump_path (dump_file, m_path); - fprintf (dump_file, "->xx REJECTED\n"); - } - continue; - } - - tree arg = gimple_phi_arg_def (phi, i); - unsigned v = 0; - - if (TREE_CODE (arg) == SSA_NAME - && !bitmap_bit_p (interesting, SSA_NAME_VERSION (arg))) - { - // Record that ARG is interesting when searching down this path. - v = SSA_NAME_VERSION (arg); - gcc_checking_assert (v != 0); - bitmap_set_bit (interesting, v); - bitmap_set_bit (m_imports, v); - } - - find_paths_to_names (e->src, interesting); - - if (v) - bitmap_clear_bit (interesting, v); - } -} - // Find jump threading paths to any of the SSA names in the // INTERESTING bitmap, and register any such paths. // @@ -505,45 +439,65 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting) else { - auto_bitmap processed; - bool done = false; - // We use a worklist instead of iterating through the bitmap, - // because we may add new items in-flight. - auto_vec worklist (bitmap_count_bits (interesting)); - populate_worklist (worklist, interesting); - while (!worklist.is_empty ()) + // For further greedy searching we want to remove interesting + // names defined in BB but add ones on the PHI edges for the + // respective edges. We do this by starting with all names + // not defined in BB as interesting, collecting a list of + // interesting PHIs in BB on the fly. Then we iterate over + // predecessor edges, adding interesting PHI edge defs to + // the set of interesting names to consider when processing it. + auto_bitmap new_interesting; + auto_vec interesting_phis; + bitmap_iterator bi; + unsigned i; + EXECUTE_IF_SET_IN_BITMAP (interesting, 0, i, bi) { - tree name = worklist.pop (); - unsigned i = SSA_NAME_VERSION (name); + tree name = ssa_name (i); gimple *def_stmt = SSA_NAME_DEF_STMT (name); - basic_block def_bb = gimple_bb (def_stmt); - - // Process any PHIs defined in this block. - if (def_bb == bb - && bitmap_set_bit (processed, i) - && gimple_code (def_stmt) == GIMPLE_PHI) + if (gimple_bb (def_stmt) != bb) + bitmap_set_bit (new_interesting, i); + else if (gphi *phi = dyn_cast (def_stmt)) { - resolve_phi (as_a (def_stmt), interesting); - done = true; - break; + tree res = gimple_phi_result (phi); + if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (res)) + interesting_phis.safe_push (phi); } } - // If there are interesting names not yet processed, keep looking. - if (!done) + if (!bitmap_empty_p (new_interesting) + || !interesting_phis.is_empty ()) { - bitmap_and_compl_into (interesting, processed); - if (!bitmap_empty_p (interesting)) + auto_vec unwind (interesting_phis.length ()); + edge_iterator iter; + edge e; + FOR_EACH_EDGE (e, iter, bb->preds) { - edge_iterator iter; - edge e; - FOR_EACH_EDGE (e, iter, bb->preds) - if ((e->flags & EDGE_ABNORMAL) == 0) - find_paths_to_names (e->src, interesting); + if (e->flags & EDGE_COMPLEX + // This is like path_crosses_loops in profitable_path_p but + // more restrictive to avoid peeling off loop iterations (see + // tree-ssa/pr14341.c for an example). + // ??? Note this restriction only applied when visiting an + // interesting PHI with the former resolve_phi. + || (!interesting_phis.is_empty () + && m_path[0]->loop_father != e->src->loop_father)) + continue; + for (gphi *phi : interesting_phis) + { + tree def = PHI_ARG_DEF_FROM_EDGE (phi, e); + if (TREE_CODE (def) == SSA_NAME) + if (bitmap_set_bit (new_interesting, + SSA_NAME_VERSION (def))) + { + bitmap_set_bit (m_imports, SSA_NAME_VERSION (def)); + unwind.quick_push (def); + } + } + find_paths_to_names (e->src, new_interesting); + // restore new_interesting, m_imports is not adjusted back? + for (tree def : unwind) + bitmap_clear_bit (new_interesting, SSA_NAME_VERSION (def)); + unwind.truncate (0); } } - - // Reset things to their original state. - bitmap_ior_into (interesting, processed); } /* Unwind from adding BB. */