From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id 848FD3858D35 for ; Tue, 14 Feb 2023 14:50:54 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 848FD3858D35 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de 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 BB28F21CA8 for ; Tue, 14 Feb 2023 14:50:53 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1676386253; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=346HvuHtYSqHFwEd9HXiFUIWpX/8mPt6e9HcCxcrcb4=; b=wAjM8hQlWcbTRRHWiQD3UQstmGj9pCulbtCHsl+wiZsgKw/X9MfObDTc7FPCHCJ7fH+Hva 7oXJdW7aUOZ5vS2qUDZRtwnTnnXKKzC48+Scj/bulqPt8ObbHJik+V0OlxZyP//uLHgv9+ vSwPUyX23pnG66VOdY0nQn45qxsZU6A= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1676386253; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=346HvuHtYSqHFwEd9HXiFUIWpX/8mPt6e9HcCxcrcb4=; b=uaO/z6uC9fAQBeiJid/b7r1Nzh44EURiiU+UsCZ32zzXFXQvLEgi+9Kgg+Lwldg7fkkNGB q1xfajy2eIwKt9CA== 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 AB8B113A21 for ; Tue, 14 Feb 2023 14:50:53 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id Y3r+KM2f62N1YAAAMHmgww (envelope-from ) for ; Tue, 14 Feb 2023 14:50:53 +0000 Date: Tue, 14 Feb 2023 15:50:53 +0100 (CET) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] More DF worklist solver improvements MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Message-Id: <20230214145053.AB8B113A21@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,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 List-Id: The following switches the double-queue iteration solver with a single-queue one that prioritizes backward data flow solving over forward progress. That is, it first converges on earlier cycles before propagating the (possibly again chainging) data to the following blocks. This improves data locality and possibly avoids visiting later blocks multiple times but it might also cause inner cycles to be iterated multiple times, so it's possibly not always an improvement. With the rev_post_order_and_mark_dfs_back_seme API it would be possible to iterate only outermost cycles immediately, like we do for var-tracking. For the PR26854 all.i testcase it halves DF RD processing time again (ontop of the previous improvement). I wanted to show off the potential but will not push this now but instead will see to find the cycles to do it the var-tracking style. * df-core.cc (df_worklist_propagate_forward): Always add to worklist. (df_worklist_propagate_backward): Likewise. (df_worklist_dataflow_doublequeue): Change to a single queue worklist implementation. --- gcc/df-core.cc | 49 ++++++++++++++----------------------------------- 1 file changed, 14 insertions(+), 35 deletions(-) diff --git a/gcc/df-core.cc b/gcc/df-core.cc index 38f69ac5743..30c1bfcc314 100644 --- a/gcc/df-core.cc +++ b/gcc/df-core.cc @@ -874,8 +874,7 @@ make_pass_df_finish (gcc::context *ctxt) /* Helper function for df_worklist_dataflow. Propagate the dataflow forward. Given a BB_INDEX, do the dataflow propagation - and set bits on for successors in PENDING for earlier - and WORKLIST for later in bbindex_to_postorder + and set bits on WORKLIST for successors if the out set of the dataflow has changed. AGE specify time when BB was visited last time. @@ -894,7 +893,6 @@ df_worklist_propagate_forward (struct dataflow *dataflow, unsigned bb_index, unsigned *bbindex_to_postorder, bitmap worklist, - bitmap pending, sbitmap considered, vec &last_change_age, int age) @@ -926,13 +924,7 @@ df_worklist_propagate_forward (struct dataflow *dataflow, unsigned ob_index = e->dest->index; if (bitmap_bit_p (considered, ob_index)) - { - if (bbindex_to_postorder[bb_index] - < bbindex_to_postorder[ob_index]) - bitmap_set_bit (worklist, bbindex_to_postorder[ob_index]); - else - bitmap_set_bit (pending, bbindex_to_postorder[ob_index]); - } + bitmap_set_bit (worklist, bbindex_to_postorder[ob_index]); } return true; } @@ -948,7 +940,6 @@ df_worklist_propagate_backward (struct dataflow *dataflow, unsigned bb_index, unsigned *bbindex_to_postorder, bitmap worklist, - bitmap pending, sbitmap considered, vec &last_change_age, int age) @@ -980,13 +971,7 @@ df_worklist_propagate_backward (struct dataflow *dataflow, unsigned ob_index = e->src->index; if (bitmap_bit_p (considered, ob_index)) - { - if (bbindex_to_postorder[bb_index] - < bbindex_to_postorder[ob_index]) - bitmap_set_bit (worklist, bbindex_to_postorder[ob_index]); - else - bitmap_set_bit (pending, bbindex_to_postorder[ob_index]); - } + bitmap_set_bit (worklist, bbindex_to_postorder[ob_index]); } return true; } @@ -995,17 +980,17 @@ df_worklist_propagate_backward (struct dataflow *dataflow, /* Main dataflow solver loop. - DATAFLOW is problem we are solving, PENDING is worklist of basic blocks we + DATAFLOW is problem we are solving, WORKLIST is worklist of basic blocks we need to visit. BLOCK_IN_POSTORDER is array of size N_BLOCKS specifying postorder in BBs and BBINDEX_TO_POSTORDER is array mapping back BB->index to postorder position. - PENDING will be freed. + WORKLIST will be freed. The worklists are bitmaps indexed by postorder positions. - The function implements standard algorithm for dataflow solving with two - worklists (we are processing WORKLIST and storing new BBs to visit in - PENDING). + The function implements standard algorithm for dataflow solving + (we are processing WORKLIST, storing new BBs to the same list + to visit dataflow changes across backedges first). As an optimization we maintain ages when BB was changed (stored in last_change_age) and when it was last visited (stored in last_visit_age). @@ -1014,15 +999,14 @@ df_worklist_propagate_backward (struct dataflow *dataflow, static void df_worklist_dataflow_doublequeue (struct dataflow *dataflow, - bitmap pending, - sbitmap considered, - int *blocks_in_postorder, + bitmap worklist, + sbitmap considered, + int *blocks_in_postorder, unsigned *bbindex_to_postorder, int n_blocks) { enum df_flow_dir dir = dataflow->problem->dir; int dcount = 0; - bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack); int age = 0; bool changed; vec last_visit_age = vNULL; @@ -1032,12 +1016,8 @@ df_worklist_dataflow_doublequeue (struct dataflow *dataflow, last_visit_age.safe_grow_cleared (n_blocks, true); last_change_age.safe_grow_cleared (n_blocks, true); - /* Double-queueing. Worklist is for the current iteration, - and pending is for the next. */ - while (!bitmap_empty_p (pending)) + if (!bitmap_empty_p (worklist)) { - std::swap (pending, worklist); - do { unsigned index = bitmap_first_set_bit (worklist); @@ -1051,14 +1031,14 @@ df_worklist_dataflow_doublequeue (struct dataflow *dataflow, if (dir == DF_FORWARD) changed = df_worklist_propagate_forward (dataflow, bb_index, bbindex_to_postorder, - worklist, pending, + worklist, considered, last_change_age, prev_age); else changed = df_worklist_propagate_backward (dataflow, bb_index, bbindex_to_postorder, - worklist, pending, + worklist, considered, last_change_age, prev_age); @@ -1070,7 +1050,6 @@ df_worklist_dataflow_doublequeue (struct dataflow *dataflow, } BITMAP_FREE (worklist); - BITMAP_FREE (pending); last_visit_age.release (); last_change_age.release (); -- 2.35.3