From patchwork Wed Aug 2 12:44:23 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 129816 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:9f41:0:b0:3e4:2afc:c1 with SMTP id v1csp428131vqx; Wed, 2 Aug 2023 05:45:10 -0700 (PDT) X-Google-Smtp-Source: APBJJlHS9dCNAlmbIHu2Fck+GFUqLtpVxJmQnhpLcwe01gEZPhHomhn3j0lPWrwtM5McsY0gh71w X-Received: by 2002:a17:907:75fa:b0:971:eb29:a082 with SMTP id jz26-20020a17090775fa00b00971eb29a082mr4540932ejc.49.1690980310347; Wed, 02 Aug 2023 05:45:10 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1690980310; cv=none; d=google.com; s=arc-20160816; b=m7coT+wXxQuZNp+wvwjSPFh7ReMLUIgLFZ32wy4MeNQ1HSkE9G3kOvHSNBJ/MgAEWZ 9kr+lBCSqD00qjfVdiYO8Zt7t4eD6t2wPduOAgpw/6oN1DWkzEddw0TXHaLQTpRk/v2S mFr7r9/T3EOVgg2V7MhFhyaJhkGYcfygvHiN9xGLvAz+P4I+P+hVqa7rJGrfKco2zAY5 hFsKCd4TOHAAEsFYUJOeNXaphwMOtVFUC5JwiaE8irXPH9drGCfPAD5BNbenBQ8QjWG9 LdvaZKLjlq01pvWZj5aIuXfyicakbt6sz2O91pF0ZA8iq2OjIwv2YX6VIITxmgdFoFbD seTg== 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=XJ/NbrN+QDKCgjto66RyX6lkgkKUSNb9nKx/bnq2Ew4=; fh=etb9MYHN7HLF/sff76ICVdPeKiI8ZsjoOL2bcdG0aog=; b=X1cAujcsIyl2UDItCTh0hj2RWHwrEQQdkOm2gV4Ys2m5omSU8Uv1kMNebQ75c5ubz4 wBR9Owg3jGL+IB3d/NX9U4giMRQmnsI7IGuvcdzGwHZTbWOOpea3l/5NIwTng6T9wIgj 8O0fM1m98VXR4H2Eszp/IdWn7icCwQy9VCh7Qv4ljDa/12h/S+5ndF8YzRKd4v+NhbbL wBHR8Qlm1moNJgrh7LqKjmWDNCnUdGYtGeO0Kvrvr3/NMs9UIX+DncWoPqz4w/bEap7p UZsUuPmDs4OhfldjfANLI72k2Uo6mHJXMeUqVPPggJ/jZhdI9Dgd6sxPVMPQAPYTwkPt BD7A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=KAgLe8CE; 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 (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id b12-20020a170906038c00b00993a68a3af8si11001026eja.568.2023.08.02.05.45.10 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 02 Aug 2023 05:45:10 -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=KAgLe8CE; 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 DDA1A3857706 for ; Wed, 2 Aug 2023 12:45:06 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org DDA1A3857706 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1690980306; bh=XJ/NbrN+QDKCgjto66RyX6lkgkKUSNb9nKx/bnq2Ew4=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=KAgLe8CE/uL0jN+4Q6ra++Y9ymowJ77sXHIC+ael4MUUNKVKyrOYsjgGyFEwp5SUs RrsuDqVAe6fLZZKz4/e0Y09dTK54nR9VrjKt3nEoR3WbQOgguNbYmaY0LaMQpm1yx5 qRhDml/Y0KD2wZc1VaimlzCJLPi0oI9HoEsznNYk= 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 1A1903858D1E for ; Wed, 2 Aug 2023 12:44:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 1A1903858D1E Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 461741F8A4 for ; Wed, 2 Aug 2023 12:44:23 +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 31C2F2C142 for ; Wed, 2 Aug 2023 12:44:23 +0000 (UTC) Date: Wed, 2 Aug 2023 12:44:23 +0000 (UTC) To: gcc-patches@gcc.gnu.org Subject: [PATCH 1/2] Add virtual operand global liveness computation class 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, 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: <20230802124506.DDA1A3857706@sourceware.org> X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1773121369747052476 X-GMAIL-MSGID: 1773121369747052476 The following adds an on-demand global liveness computation class computing and caching the live-out virtual operand of basic blocks and answering live-out, live-in and live-on-edge queries. The flow is optimized for the intended use in code sinking which will query live-in and possibly can be optimized further when the originating query is for live-out. The code relies on up-to-date immediate dominator information and on an unchanging virtual operand state. Bootstrapped and tested on x86_64-unknown-linux-gnu (with 2/2). OK? Thanks, Richard. * tree-ssa-live.h (class virtual_operand_live): New. * tree-ssa-live.cc (virtual_operand_live::init): New. (virtual_operand_live::get_live_in): Likewise. (virtual_operand_live::get_live_out): Likewise. --- gcc/tree-ssa-live.cc | 75 ++++++++++++++++++++++++++++++++++++++++++++ gcc/tree-ssa-live.h | 27 ++++++++++++++++ 2 files changed, 102 insertions(+) diff --git a/gcc/tree-ssa-live.cc b/gcc/tree-ssa-live.cc index 1be92956cc5..c9c2fdef0e3 100644 --- a/gcc/tree-ssa-live.cc +++ b/gcc/tree-ssa-live.cc @@ -43,6 +43,7 @@ along with GCC; see the file COPYING3. If not see #include "optinfo.h" #include "gimple-walk.h" #include "cfganal.h" +#include "tree-cfg.h" static void verify_live_on_entry (tree_live_info_p); @@ -1651,3 +1652,77 @@ verify_live_on_entry (tree_live_info_p live) } gcc_assert (num <= 0); } + + +/* Virtual operand liveness analysis data init. */ + +void +virtual_operand_live::init () +{ + liveout = XCNEWVEC (tree, last_basic_block_for_fn (cfun) + 1); + liveout[ENTRY_BLOCK] = ssa_default_def (cfun, gimple_vop (cfun)); +} + +/* Compute live-in of BB from cached live-out. */ + +tree +virtual_operand_live::get_live_in (basic_block bb) +{ + /* A virtual PHI is a convenient cache for live-in. */ + gphi *phi = get_virtual_phi (bb); + if (phi) + return gimple_phi_result (phi); + + if (!liveout) + init (); + + /* Since we don't have a virtual PHI we can now pick any of the + incoming edges liveout value. All returns from the function have + a virtual use forcing generation of virtual PHIs. */ + edge_iterator ei; + edge e; + FOR_EACH_EDGE (e, ei, bb->preds) + if (liveout[e->src->index]) + { + if (EDGE_PRED (bb, 0) != e) + liveout[EDGE_PRED (bb, 0)->src->index] = liveout[e->src->index]; + return liveout[e->src->index]; + } + + /* Since virtuals are in SSA form at most the immediate dominator can + contain the definition of the live version. Skipping to that deals + with CFG cycles as well. */ + return get_live_out (get_immediate_dominator (CDI_DOMINATORS, bb)); +} + +/* Compute live-out of BB. */ + +tree +virtual_operand_live::get_live_out (basic_block bb) +{ + if (!liveout) + init (); + + if (liveout[bb->index]) + return liveout[bb->index]; + + tree lo = NULL_TREE; + for (auto gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi)) + { + gimple *stmt = gsi_stmt (gsi); + if (gimple_vdef (stmt)) + { + lo = gimple_vdef (stmt); + break; + } + if (gimple_vuse (stmt)) + { + lo = gimple_vuse (stmt); + break; + } + } + if (!lo) + lo = get_live_in (bb); + liveout[bb->index] = lo; + return lo; +} diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h index de665d6bad0..a7604448332 100644 --- a/gcc/tree-ssa-live.h +++ b/gcc/tree-ssa-live.h @@ -328,4 +328,31 @@ make_live_on_entry (tree_live_info_p live, basic_block bb , int p) bitmap_set_bit (live->global, p); } + +/* On-demand virtual operand global live analysis. There is at most + a single virtual operand live at a time, the following computes and + caches the virtual operand live at the exit of a basic block + supporting related live-in and live-on-edge queries. */ + +class virtual_operand_live +{ +public: + virtual_operand_live() : liveout (nullptr) {} + ~virtual_operand_live() + { + if (liveout) + free (liveout); + } + + tree get_live_in (basic_block bb); + tree get_live_out (basic_block bb); + tree get_live_on_edge (edge e) { return get_live_out (e->src); } + +private: + void init (); + + tree *liveout; +}; + + #endif /* _TREE_SSA_LIVE_H */