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 */ From patchwork Wed Aug 2 12:44:48 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 129817 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:9f41:0:b0:3e4:2afc:c1 with SMTP id v1csp428379vqx; Wed, 2 Aug 2023 05:45:37 -0700 (PDT) X-Google-Smtp-Source: APBJJlHgY4nF8vDtr0g2JKBmm4pd4f/2Ke7wNPPHvpbTKwKNjNr7BfuP83dzmlPfOvodRCExdyet X-Received: by 2002:a05:6402:1659:b0:522:cb97:f196 with SMTP id s25-20020a056402165900b00522cb97f196mr5096237edx.36.1690980336873; Wed, 02 Aug 2023 05:45:36 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1690980336; cv=none; d=google.com; s=arc-20160816; b=ooeYbTs6JXUuVWuP1MTKBcZABD/flD3IZl8sPoM24JEqs4vRYk96uhIS5fZNnCrYrU jA1uEtiNhz52bU1dJ+YTfo+65dSaz99m53uyKBQKv0YYBYlWP+c3HHHs/oVMBtalUfF7 UMx4BkJ3THSiR2AXKAfOHG+L8IGuASIH0j4UFpoNw0jE+cg6AQEXTIXPtq2vHWGlrHDb b+rc48YPdThz8ERlFujyx9S1f4C8Uv7nSGVBEhPv9SlWyx+hwxTgInHsq91dZK79MIU0 EWLbdoZmvkgUCMzh/RNi80JVTu8NWABNP4U4oq+P/JKuN1WuQyswIC7qSc9MbNrjTG6l IT2g== 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=XT6BNuEkHado2AZcMCey9qkEn0K6Trts/lL9tMv5XgU=; fh=etb9MYHN7HLF/sff76ICVdPeKiI8ZsjoOL2bcdG0aog=; b=R8SqsKdPVDhiCRGWjVyLdugZceSZpSjOzNEby+zH2saxB0R1b5lHXc/lPmLInxrxnY AgRdiU2biR5n9U2ZP8PBhB4+eLQ9D2lTf3Np9Wz5r0esivz7AceAwYr5Wy5+vxgpF8Nv uAAVOqOhU3FXfys9d6zp2pLv0s0IdwjLwi/J5WS6NGlAPwL8CF1Jqq0HgsFgtpgFu6u0 KYyGMe45fR1t1A4IXAXmAkkB6syUr+dWt3Kgzy3eCVsm3B+ViDGSCZVCQXd2vgel4oDk IOuV04qD4UysoUN0+lIL+ErjbAXr1aqIyg3htmQ9yKJhQNKMU3sjC5Y/v9RZZ86pkpDe ikxw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=r0tkQG7z; 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 (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id r17-20020aa7d151000000b005224c7ad5afsi9139836edo.99.2023.08.02.05.45.36 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 02 Aug 2023 05:45:36 -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=r0tkQG7z; 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 69E863858000 for ; Wed, 2 Aug 2023 12:45:32 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 69E863858000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1690980332; bh=XT6BNuEkHado2AZcMCey9qkEn0K6Trts/lL9tMv5XgU=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=r0tkQG7z8O/HKD1owNZ4e5RFan5dBk/mrzhTQtl/Kdptk8Z6YV+mgJjgVxTd15jY3 VxwU9KTUNi4YpJa2wnkjvwAaPv+jEp0dAhIoSTS7r9IlNT++ziBauB9lX5eDV2aIbW cKoNzVb8/9FO1iOd00CAfGxK/YcuJ53LdqvfGPr0= 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 94B7B3858017 for ; Wed, 2 Aug 2023 12:44:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 94B7B3858017 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id B20341F8B2 for ; Wed, 2 Aug 2023 12:44:48 +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 A74142C143 for ; Wed, 2 Aug 2023 12:44:48 +0000 (UTC) Date: Wed, 2 Aug 2023 12:44:48 +0000 (UTC) To: gcc-patches@gcc.gnu.org Subject: [PATCH 2/2] Improve sinking with unrelated defs 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: <20230802124532.69E863858000@sourceware.org> X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1773121398004619166 X-GMAIL-MSGID: 1773121398004619166 statement_sink_location for loads is currently confused about stores that are not on the paths we are sinking across. The following replaces the logic that tries to ensure we are not sinking across stores by instead of walking all immediate virtual uses and then checking whether found stores are on the paths we sink through with checking the live virtual operand at the sinking location. To obtain the live virtual operand we rely on the new virtual_operand_live class which provides an overall cheaper and also more precise way to check the constraints. Bootstrapped and tested on x86_64-unknown-linux-gnu. Comments? Thanks, Richard. * tree-ssa-sink.cc: Include tree-ssa-live.h. (pass_sink_code::execute): Instantiate virtual_operand_live and pass it down. (sink_code_in_bb): Pass down virtual_operand_live. (statement_sink_location): Get virtual_operand_live and verify we are not sinking loads across stores by looking up the live virtual operand at the sink location. * gcc.dg/tree-ssa/ssa-sink-20.c: New testcase. --- gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c | 16 +++++ gcc/tree-ssa-sink.cc | 70 +++++---------------- 2 files changed, 33 insertions(+), 53 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c new file mode 100644 index 00000000000..266ceb000a5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-sink1-details" } */ + +void bar (); +int foo (int *p, int x) +{ + int res = *p; + if (x) + { + bar (); + res = 1; + } + return res; +} + +/* { dg-final { scan-tree-dump "Sinking # VUSE" "sink1" } } */ diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc index d83d7be587d..5cf9e737e84 100644 --- a/gcc/tree-ssa-sink.cc +++ b/gcc/tree-ssa-sink.cc @@ -35,6 +35,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-cfg.h" #include "cfgloop.h" #include "tree-eh.h" +#include "tree-ssa-live.h" /* TODO: 1. Sinking store only using scalar promotion (IE without moving the RHS): @@ -263,7 +264,8 @@ select_best_block (basic_block early_bb, static bool statement_sink_location (gimple *stmt, basic_block frombb, - gimple_stmt_iterator *togsi, bool *zero_uses_p) + gimple_stmt_iterator *togsi, bool *zero_uses_p, + virtual_operand_live &vop_live) { gimple *use; use_operand_p one_use = NULL_USE_OPERAND_P; @@ -386,10 +388,7 @@ statement_sink_location (gimple *stmt, basic_block frombb, if (commondom == frombb) return false; - /* If this is a load then do not sink past any stores. - Look for virtual definitions in the path from frombb to the sink - location computed from the real uses and if found, adjust - that it a common dominator. */ + /* If this is a load then do not sink past any stores. */ if (gimple_vuse (stmt)) { /* Do not sink loads from hard registers. */ @@ -398,51 +397,14 @@ statement_sink_location (gimple *stmt, basic_block frombb, && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt))) return false; - imm_use_iterator imm_iter; - use_operand_p use_p; - FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_vuse (stmt)) - { - gimple *use_stmt = USE_STMT (use_p); - basic_block bb = gimple_bb (use_stmt); - /* For PHI nodes the block we know sth about is the incoming block - with the use. */ - if (gimple_code (use_stmt) == GIMPLE_PHI) - { - /* If the PHI defines the virtual operand, ignore it. */ - if (gimple_phi_result (use_stmt) == gimple_vuse (stmt)) - continue; - /* In case the PHI node post-dominates the current insert - location we can disregard it. But make sure it is not - dominating it as well as can happen in a CFG cycle. */ - if (commondom != bb - && !dominated_by_p (CDI_DOMINATORS, commondom, bb) - && dominated_by_p (CDI_POST_DOMINATORS, commondom, bb) - /* If the blocks are possibly within the same irreducible - cycle the above check breaks down. */ - && !((bb->flags & commondom->flags & BB_IRREDUCIBLE_LOOP) - && bb->loop_father == commondom->loop_father) - && !((commondom->flags & BB_IRREDUCIBLE_LOOP) - && flow_loop_nested_p (commondom->loop_father, - bb->loop_father)) - && !((bb->flags & BB_IRREDUCIBLE_LOOP) - && flow_loop_nested_p (bb->loop_father, - commondom->loop_father))) - continue; - bb = EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src; - } - else if (!gimple_vdef (use_stmt)) - continue; - /* If the use is not dominated by the path entry it is not on - the path. */ - if (!dominated_by_p (CDI_DOMINATORS, bb, frombb)) - continue; - /* There is no easy way to disregard defs not on the path from - frombb to commondom so just consider them all. */ - commondom = nearest_common_dominator (CDI_DOMINATORS, - bb, commondom); - if (commondom == frombb) - return false; - } + /* When the live virtual operand at the intended sink location is + not the same as the one from the load walk up the dominator tree + for a new candidate location. */ + while (commondom != frombb + && vop_live.get_live_in (commondom) != gimple_vuse (stmt)) + commondom = get_immediate_dominator (CDI_DOMINATORS, commondom); + if (commondom == frombb) + return false; } /* Our common dominator has to be dominated by frombb in order to be a @@ -681,7 +643,7 @@ sink_common_stores_to_bb (basic_block bb) /* Perform code sinking on BB */ static unsigned -sink_code_in_bb (basic_block bb) +sink_code_in_bb (basic_block bb, virtual_operand_live &vop_live) { gimple_stmt_iterator gsi; edge_iterator ei; @@ -708,7 +670,7 @@ sink_code_in_bb (basic_block bb) gimple_stmt_iterator togsi; bool zero_uses_p; - if (!statement_sink_location (stmt, bb, &togsi, &zero_uses_p)) + if (!statement_sink_location (stmt, bb, &togsi, &zero_uses_p, vop_live)) { gimple_stmt_iterator saved = gsi; if (!gsi_end_p (gsi)) @@ -864,12 +826,14 @@ pass_sink_code::execute (function *fun) calculate_dominance_info (CDI_DOMINATORS); calculate_dominance_info (CDI_POST_DOMINATORS); + virtual_operand_live vop_live; + auto_vec worklist; worklist.quick_push (EXIT_BLOCK_PTR_FOR_FN (fun)); do { basic_block bb = worklist.pop (); - todo |= sink_code_in_bb (bb); + todo |= sink_code_in_bb (bb, vop_live); for (basic_block son = first_dom_son (CDI_POST_DOMINATORS, bb); son; son = next_dom_son (CDI_POST_DOMINATORS, son))