From patchwork Tue Oct 25 13:09:26 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 10780 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp996461wru; Tue, 25 Oct 2022 06:10:37 -0700 (PDT) X-Google-Smtp-Source: AMsMyM5+2mI9gzBtv7Btd0s25fLYUkAcvnEpx7gnGH0m35FBpS/nvOtwXP/nFIMyDnuKXzARK0MO X-Received: by 2002:a17:906:8a6a:b0:79e:2efe:e0 with SMTP id hy10-20020a1709068a6a00b0079e2efe00e0mr17593088ejc.401.1666703427027; Tue, 25 Oct 2022 06:10:27 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1666703427; cv=none; d=google.com; s=arc-20160816; b=S4xsanzOM6c56IwctVGliiidgz17oz71TLhNH17bs7XnseJPDk5nn+/KygnKWHI3Ay J1wg7fKsCcdNAPgX3YtWukNsAEHIt+n/PZRAlPUJ3jJetMZngVin6dG9ewJ+Hy5mQApI i2v77SCGn/qIXLuOzxCC6M8MPcpmgAW1P4HcLgWG6lZZateg7g120Q/1Z8AojBnmRzw+ X9l8jtzZn6hDsZeAxPWRh1yEsBoGLIhE1gWZFypLvbA6LMjvR2/xJFan3OwJSrpzlCtI jd/2aLJM55L5k/LY68JlJUu5KBU9COK/f9dYof//iiaQ3R4xY41KELTUZcRNIz75ckA1 Osow== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:cc:reply-to:from:list-subscribe:list-help :list-post:list-archive:list-unsubscribe:list-id:precedence :message-id:mime-version:subject:to:date:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=50puZcP4id3IL8p0LymaAzktixBxWdK/vK9E6HsXT/w=; b=MYTwOmiSOnDZQEDmZoZ1bP9GVBYrHN9X1GLb5CHkL4h4wptfQ6e/54t4NShPVTWpFb dZQuL/vni5w+Tb/u+GRy/ivLc32rLuoLgNnc1ClEL3cL9kTzuLoIfKhUo1wNe/YuKYW7 XpxUwhzjdAGKP9/0s3F/VoC42e697BOVw1Tyo6JyEl3J0ErW/LQ9GgT1COpTrw3ridyg SUWd5psZQHLCaGwYRTXVkAv+5XOUT7tVKb/e38knl86vdRwoOSs33PZ6gSDT6oD2RG8R 8m+VRp+4QDv0O1U2yW5pz68qDLVp7geHbdok43mPpJVc9DlZOxhsK71frnZ1gzi60cUc rA9w== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=NUQyYniR; 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 jg20-20020a170907971400b0078db1343eedsi2922481ejc.774.2022.10.25.06.10.26 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 25 Oct 2022 06:10:27 -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=NUQyYniR; 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 1A6CC3856DF2 for ; Tue, 25 Oct 2022 13:10:15 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 1A6CC3856DF2 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1666703415; bh=50puZcP4id3IL8p0LymaAzktixBxWdK/vK9E6HsXT/w=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=NUQyYniReNtP9b6ICY5O6VG6u/8um7QzKE5EuYmFJnynlGCDWBcgXAjZsBraqVuhP N3gvHb2drR/KEC+Vhj3Rr0PCtItjex5GIcemo8PJOqhga3E6mflXOPtylajsDpI82O C387YHHm+BeSCp9+VSFqRukdZsGYcNg1C9m6BbzA= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2001:67c:2178:6::1c]) by sourceware.org (Postfix) with ESMTPS id 5CF90385780A for ; Tue, 25 Oct 2022 13:09:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 5CF90385780A Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 7D04322005; Tue, 25 Oct 2022 13:09:26 +0000 (UTC) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 6319B13A64; Tue, 25 Oct 2022 13:09:26 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id EXYPFwbgV2NoMgAAMHmgww (envelope-from ); Tue, 25 Oct 2022 13:09:26 +0000 Date: Tue, 25 Oct 2022 15:09:26 +0200 (CEST) To: gcc-patches@gcc.gnu.org Subject: [PATCH] unswitch most profitable condition first MIME-Version: 1.0 Message-Id: <20221025130926.6319B13A64@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-12.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, 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 Cc: Jan Hubicka Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1747665212690936689?= X-GMAIL-MSGID: =?utf-8?q?1747665212690936689?= When doing the loop unswitching re-org we promised to followup with improvements on the cost modeling. The following makes sure we try to unswitch on the most profitable condition first. As most profitable we pick the condition leading to the edge with the highest profile count. Note the profile is only applied when picking the first unswitching opportunity since the profile counts are not updated with earlier unswitchings in mind. Further opportunities are picked in DFS order. Bootstrapped and tested on x86_64-unknown-linux-gnu. Any comments? Thanks, Richard. * tree-ssa-loop-unswitch.cc (unswitch_predicate::count): New. (unswitch_predicate::unswitch_predicate): Initialize count. (init_loop_unswitch_info): First collect candidates and determine the outermost loop to unswitch. (tree_ssa_unswitch_loops): First perform all guard hoisting, then perform unswitching on innermost loop predicates. (find_unswitching_predicates_for_bb): Keep track of the most profitable predicate to unswitch on. (tree_unswitch_single_loop): Unswitch given predicate if not NULL. --- gcc/tree-ssa-loop-unswitch.cc | 66 ++++++++++++++++++++++++++++------- 1 file changed, 54 insertions(+), 12 deletions(-) diff --git a/gcc/tree-ssa-loop-unswitch.cc b/gcc/tree-ssa-loop-unswitch.cc index 7d6781d1505..dfe75f52f12 100644 --- a/gcc/tree-ssa-loop-unswitch.cc +++ b/gcc/tree-ssa-loop-unswitch.cc @@ -118,6 +118,7 @@ struct unswitch_predicate if (!false_range.varying_p () && !false_range.undefined_p ()) false_range.invert (); + count = e->count (); num = predicates->length (); predicates->safe_push (this); } @@ -126,7 +127,8 @@ struct unswitch_predicate unswitch_predicate (gcond *stmt) : switch_p (false) { - if (EDGE_SUCC (gimple_bb (stmt), 0)->flags & EDGE_TRUE_VALUE) + basic_block bb = gimple_bb (stmt); + if (EDGE_SUCC (bb, 0)->flags & EDGE_TRUE_VALUE) edge_index = 0; else edge_index = 1; @@ -134,6 +136,7 @@ struct unswitch_predicate tree rhs = gimple_cond_rhs (stmt); enum tree_code code = gimple_cond_code (stmt); condition = build2 (code, boolean_type_node, lhs, rhs); + count = EDGE_SUCC (bb, 0)->count ().max (EDGE_SUCC (bb, 1)->count ()); if (irange::supports_p (TREE_TYPE (lhs))) { auto range_op = range_op_handler (code, TREE_TYPE (lhs)); @@ -180,6 +183,9 @@ struct unswitch_predicate /* Index of the edge the predicate belongs to in the successor vector. */ int edge_index; + /* The profile count of this predicate. */ + profile_count count; + /* Whether the predicate was created from a switch statement. */ bool switch_p; @@ -206,10 +212,14 @@ static class loop *tree_unswitch_loop (class loop *, edge, tree); static bool tree_unswitch_single_loop (class loop *, dump_user_location_t, predicate_vector &predicate_path, unsigned loop_size, unsigned &budget, - int ignored_edge_flag, bitmap); + int ignored_edge_flag, bitmap, + unswitch_predicate * = NULL, + basic_block = NULL); static void find_unswitching_predicates_for_bb (basic_block bb, class loop *loop, - vec &candidates); + vec &candidates, + unswitch_predicate *&hottest, + basic_block &hottest_bb); static bool tree_unswitch_outer_loop (class loop *); static edge find_loop_guard (class loop *, vec&); static bool empty_bb_without_guard_p (class loop *, basic_block, @@ -242,7 +252,8 @@ set_predicates_for_bb (basic_block bb, vec predicates) Return total number of instructions in the loop. */ static unsigned -init_loop_unswitch_info (class loop *loop) +init_loop_unswitch_info (class loop *loop, unswitch_predicate *&hottest, + basic_block &hottest_bb) { unsigned total_insns = 0; @@ -259,13 +270,16 @@ init_loop_unswitch_info (class loop *loop) total_insns += insns; } + hottest = NULL; + hottest_bb = NULL; /* Find all unswitching candidates. */ for (unsigned i = 0; i != loop->num_nodes; i++) { /* Find a bb to unswitch on. */ vec candidates; candidates.create (1); - find_unswitching_predicates_for_bb (bbs[i], loop, candidates); + find_unswitching_predicates_for_bb (bbs[i], loop, candidates, + hottest, hottest_bb); if (!candidates.is_empty ()) set_predicates_for_bb (bbs[i], candidates); else @@ -329,7 +343,10 @@ tree_ssa_unswitch_loops (function *fun) unswitch_predicate::predicates = new vec (); /* Unswitch innermost loop. */ - unsigned int loop_size = init_loop_unswitch_info (loop); + unswitch_predicate *hottest; + basic_block hottest_bb; + unsigned int loop_size = init_loop_unswitch_info (loop, hottest, + hottest_bb); unsigned int budget = loop_size + param_max_unswitch_insns; predicate_vector predicate_path; @@ -338,7 +355,8 @@ tree_ssa_unswitch_loops (function *fun) changed_unswitch |= tree_unswitch_single_loop (loop, loc, predicate_path, loop_size, budget, - ignored_edge_flag, handled); + ignored_edge_flag, handled, + hottest, hottest_bb); predicate_path.release (); for (auto predlist : bb_predicates) @@ -449,7 +467,9 @@ is_maybe_undefined (const tree name, gimple *stmt, class loop *loop) static void find_unswitching_predicates_for_bb (basic_block bb, class loop *loop, - vec &candidates) + vec &candidates, + unswitch_predicate *&hottest, + basic_block &hottest_bb) { gimple *last, *def; tree use; @@ -489,6 +509,14 @@ find_unswitching_predicates_for_bb (basic_block bb, class loop *loop, unswitch_predicate *predicate = new unswitch_predicate (stmt); candidates.safe_push (predicate); + /* If we unswitch on this predicate we isolate both paths, so + pick the highest count for updating of the hottest predicate + to unswitch on first. */ + if (!hottest || predicate->count > hottest->count) + { + hottest = predicate; + hottest_bb = bb; + } } else if (gswitch *stmt = safe_dyn_cast (last)) { @@ -561,6 +589,11 @@ find_unswitching_predicates_for_bb (basic_block bb, class loop *loop, edge_index, e, edge_range[edge_index]); candidates.safe_push (predicate); + if (!hottest || predicate->count > hottest->count) + { + hottest = predicate; + hottest_bb = bb; + } } } } @@ -888,13 +921,15 @@ evaluate_loop_insns_for_predicate (class loop *loop, /* Unswitch single LOOP. PREDICATE_PATH contains so far used predicates for unswitching. BUDGET is number of instruction for which we can increase - the loop and is updated when unswitching occurs. */ + the loop and is updated when unswitching occurs. If HOTTEST is not + NULL then pick this candidate as the one to unswitch on. */ static bool tree_unswitch_single_loop (class loop *loop, dump_user_location_t loc, predicate_vector &predicate_path, unsigned loop_size, unsigned &budget, - int ignored_edge_flag, bitmap handled) + int ignored_edge_flag, bitmap handled, + unswitch_predicate *hottest, basic_block hottest_bb) { class loop *nloop; bool changed = false; @@ -939,8 +974,15 @@ tree_unswitch_single_loop (class loop *loop, dump_user_location_t loc, } return false; }; - /* Check predicates of reachable blocks. */ - evaluate_bbs (loop, NULL, ignored_edge_flag, check_predicates); + + if (hottest) + { + predicate = hottest; + predicate_bb = hottest_bb; + } + else + /* Check predicates of reachable blocks. */ + evaluate_bbs (loop, NULL, ignored_edge_flag, check_predicates); if (predicate != NULL) {