From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 21817 invoked by alias); 29 Jul 2007 21:32:25 -0000 Received: (qmail 21809 invoked by uid 22791); 29 Jul 2007 21:32:24 -0000 X-Spam-Check-By: sourceware.org Received: from mail2.panix.com (HELO mail2.panix.com) (166.84.1.73) by sourceware.org (qpsmtpd/0.31) with ESMTP; Sun, 29 Jul 2007 21:32:20 +0000 Received: from mailspool3.panix.com (mailspool3.panix.com [166.84.1.78]) by mail2.panix.com (Postfix) with ESMTP id EA4B934819; Sun, 29 Jul 2007 17:32:14 -0400 (EDT) Received: from [192.168.1.60] (pool-70-104-131-212.nycmny.fios.verizon.net [70.104.131.212]) by mailspool3.panix.com (Postfix) with ESMTP id C00DA16976; Sun, 29 Jul 2007 17:32:14 -0400 (EDT) Message-ID: <46AD075E.30705@naturalbridge.com> Date: Sun, 29 Jul 2007 22:23:00 -0000 From: Kenneth Zadeck User-Agent: Thunderbird 1.5.0.12 (X11/20060911) MIME-Version: 1.0 To: Ayal Zaks CC: Revital1 Eres , abel@ispras.ru, gcc-patches@gcc.gnu.org, Kenneth.Zadeck@NaturalBridge.com, volodyan@gmail.com Subject: Re: [PING][PATCH] [modulo-sched] Change the ddg's construction References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org X-SW-Source: 2007-07/txt/msg02083.txt.bz2 Ayal Zaks wrote: > Revital1 Eres/Haifa/IBM wrote on 29/07/2007 20:36:19: > > >> Hello, >> >> This patch changes the ddg's construction as described in: >> http://gcc.gnu.org/ml/gcc-patches/2007-03/msg00711.html (attached is >> the version related to current trunk). >> >> This patch was bootstrapped and tested on ppc64 and x86_64. >> >> OK for mainline? >> >> > > Kenny, thanks for the quick approval. Any follow-up changes needed for df, > now that df_ru_add_problem() is left without a caller? > > Revital, this is ok with me too, with some minor comments below. > > Ayal. > thanks, I was going to submit the patch to get rid of ru as soon as your patch was committed, kenny > >> Thanks, >> Revital >> >> 2007-07-29 Revital Eres >> >> * ddg.c (add_deps_for_def): Rename to... >> (add deps): This. Change implementation to use only reaching >> def and def-use chains to construct the inter loop dependencies. >> (add_deps_for_use): Remove function. >> (build_inter_loop_deps): Call add_deps function to build the >> inter loop dependencies. >> * modulo-sched.c (sms_schedule): Build only >> reaching def and def-use chains for the propose of the ddg >> construction. >> >> [attachment "patch_ddg.txt" deleted by Ayal Zaks/Haifa/IBM] >> > > >> Index: ddg.c >> =================================================================== >> --- ddg.c (revision 126552) >> +++ ddg.c (working copy) >> @@ -224,131 +224,103 @@ >> add_edge_to_ddg (g, e); >> } >> >> - >> -/* Given a downwards exposed register def RD, add inter-loop true >> > dependences > >> - for all its uses in the next iteration, and an output dependence to >> > the > >> - first def of the next iteration. */ >> + >> +/* Given a downwards exposed register def LAST_DEF (which is the last >> + definition of that register in the bb), add inter-loop true >> > dependences > >> + for all its uses in the next iteration, an output dependence to the >> > ^^^ > to > > >> + first def of >> > > the same register (possibly itself) in > > >> the next iteration and anti-dependences from its uses in >> + the current iteration to the first definition in the next iteration. >> + */ >> static void >> -add_deps_for_def (ddg_ptr g, struct df_ref *rd) >> +add_deps (ddg_ptr g, struct df_ref *last_def) >> > > Better rename to something like add_cross_iteration_register_deps > > >> { >> - int regno = DF_REF_REGNO (rd); >> - struct df_ru_bb_info *bb_info = DF_RU_BB_INFO (g->bb); >> + int regno = DF_REF_REGNO (last_def); >> struct df_link *r_use; >> - int use_before_def = false; >> - rtx def_insn = DF_REF_INSN (rd); >> - ddg_node_ptr src_node = get_node_of_insn (g, def_insn); >> + int has_use_in_bb_p = false; >> + rtx def_insn = DF_REF_INSN (last_def); >> + ddg_node_ptr last_def_node = get_node_of_insn (g, def_insn); >> + ddg_node_ptr use_node; >> + struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb); >> + struct df_ref *first_def = df_bb_regno_first_def_find (g->bb, regno); >> >> - /* Create and inter-loop true dependence between RD and each of its >> > uses > >> - that is upwards exposed in RD's block. */ >> - for (r_use = DF_REF_CHAIN (rd); r_use != NULL; r_use = r_use->next) >> + gcc_assert (last_def_node && first_def); >> > > Better split into two asserts. > > >> + >> + /* Create inter-loop true dependences and anti dependences. */ >> + for (r_use = DF_REF_CHAIN (last_def); r_use != NULL; r_use = >> > r_use->next) > >> { >> - if (bitmap_bit_p (bb_info->gen, r_use->ref->id)) >> - { >> - rtx use_insn = DF_REF_INSN (r_use->ref); >> - ddg_node_ptr dest_node = get_node_of_insn (g, use_insn); >> + rtx use_insn = DF_REF_INSN (r_use->ref); >> >> - gcc_assert (src_node && dest_node); >> + if (BLOCK_FOR_INSN (use_insn) != g->bb) >> + continue; >> >> - /* Any such upwards exposed use appears before the rd def. */ >> - use_before_def = true; >> - create_ddg_dep_no_link (g, src_node, dest_node, TRUE_DEP, >> + use_node = get_node_of_insn (g, use_insn); >> + gcc_assert (use_node); >> + has_use_in_bb_p = true; >> + if (use_node->cuid <= last_def_node->cuid) >> + { >> + /* Add true deps from last_def to it's uses in the next >> + iteration. Any such upwards exposed use appears before >> + the last_def def. */ >> + create_ddg_dep_no_link (g, last_def_node, use_node, TRUE_DEP, >> REG_DEP, 1); >> } >> - } >> + else >> + { >> + /* Add anti deps from last_def's uses in the current iteration >> + to the first def in the next iteration. We must not >> > ^^^^do > > >> + add ANTI dep when there is an intra-loop TRUE dep in the >> + opposite direction >> > > , but use regmoves to fix such disregarded ANTI deps when broken > > >> + . If the first_def reaches the USE then >> + there is such a dep. */ >> + ddg_node_ptr first_def_node = get_node_of_insn (g, >> + first_def->insn); >> >> - /* Create an inter-loop output dependence between RD (which is the >> - last def in its block, being downwards exposed) and the first def >> - in its block. Avoid creating a self output dependence. Avoid >> > creating > >> - an output dependence if there is a dependence path between the two >> > defs > >> - starting with a true dependence followed by an anti dependence >> > (i.e. if > >> - there is a use between the two defs. */ >> - if (! use_before_def) >> + gcc_assert (first_def_node); >> + >> + if (!bitmap_bit_p (bb_info->gen, first_def->id)) >> > > Simply check instead if first_def is not last_def? > > >> + create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP, >> + REG_DEP, 1); >> + } >> + } >> + /* Create an inter-loop output dependence between LAST_DEF (which is >> > the > >> + last def in its block, being downwards exposed) and the first def >> > in > >> + its block. Avoid creating a self output dependence. Avoid >> > creating > >> + an output dependence if there is a dependence path between the two >> + defs starting with a true dependence to a use which can be in the >> + next iteration; followed by an anti dependence of that use to the >> + first def (i.e. if there is a use between the two defs.) */ >> + if (!has_use_in_bb_p) >> { >> - struct df_ref *def = df_bb_regno_first_def_find (g->bb, regno); >> - int i; >> ddg_node_ptr dest_node; >> >> - if (!def || rd->id == def->id) >> + if (last_def->id == first_def->id) >> return; >> >> - /* Check if there are uses after RD. */ >> - for (i = src_node->cuid + 1; i < g->num_nodes; i++) >> - if (df_find_use (g->nodes[i].insn, DF_REF_REG (rd))) >> - return; >> - >> - dest_node = get_node_of_insn (g, def->insn); >> - create_ddg_dep_no_link (g, src_node, dest_node, OUTPUT_DEP, >> > REG_DEP, 1); > >> + dest_node = get_node_of_insn (g, first_def->insn); >> + gcc_assert (dest_node); >> + create_ddg_dep_no_link (g, last_def_node, dest_node, >> + OUTPUT_DEP, REG_DEP, 1); >> } >> } >> - >> -/* Given a register USE, add an inter-loop anti dependence to the first >> - (nearest BLOCK_BEGIN) def of the next iteration, unless USE is >> > followed > >> - by a def in the block. */ >> -static void >> -add_deps_for_use (ddg_ptr g, struct df_ref *use) >> -{ >> - int i; >> - int regno = DF_REF_REGNO (use); >> - struct df_ref *first_def = df_bb_regno_first_def_find (g->bb, regno); >> - ddg_node_ptr use_node; >> - ddg_node_ptr def_node; >> - struct df_rd_bb_info *bb_info; >> - >> - bb_info = DF_RD_BB_INFO (g->bb); >> - >> - if (!first_def) >> - return; >> - >> - use_node = get_node_of_insn (g, use->insn); >> - def_node = get_node_of_insn (g, first_def->insn); >> - >> - gcc_assert (use_node && def_node); >> - >> - /* Make sure there are no defs after USE. */ >> - for (i = use_node->cuid + 1; i < g->num_nodes; i++) >> - if (df_find_def (g->nodes[i].insn, DF_REF_REG (use))) >> - return; >> - /* We must not add ANTI dep when there is an intra-loop TRUE dep in >> - the opposite direction. If the first_def reaches the USE then there >> > is > >> - such a dep. */ >> - if (! bitmap_bit_p (bb_info->gen, first_def->id)) >> - create_ddg_dep_no_link (g, use_node, def_node, ANTI_DEP, REG_DEP, >> > 1); > >> -} >> - >> /* Build inter-loop dependencies, by looking at DF analysis backwards. >> > */ > >> static void >> build_inter_loop_deps (ddg_ptr g) >> { >> - unsigned rd_num, u_num; >> + unsigned rd_num; >> struct df_rd_bb_info *rd_bb_info; >> - struct df_ru_bb_info *ru_bb_info; >> bitmap_iterator bi; >> >> rd_bb_info = DF_RD_BB_INFO (g->bb); >> >> - /* Find inter-loop output and true deps by connecting downward exposed >> > defs > >> - to the first def of the BB and to upwards exposed uses. */ >> + /* Find inter-loop >> > > register > > >> output, true and anti deps. */ >> > > >> EXECUTE_IF_SET_IN_BITMAP (rd_bb_info->gen, 0, rd_num, bi) >> - { >> - struct df_ref *rd = DF_DEFS_GET (rd_num); >> + { >> + struct df_ref *rd = DF_DEFS_GET (rd_num); >> >> - add_deps_for_def (g, rd); >> - } >> - >> - ru_bb_info = DF_RU_BB_INFO (g->bb); >> - >> - /* Find inter-loop anti deps. We are interested in uses of the block >> > that > >> - appear below all defs; this implies that these uses are killed. */ >> - EXECUTE_IF_SET_IN_BITMAP (ru_bb_info->kill, 0, u_num, bi) >> - { >> - struct df_ref *use = DF_USES_GET (u_num); >> - if (!(DF_REF_FLAGS (use) & DF_REF_IN_NOTE)) >> > > Please comment why we no longer check and exclude such uses. > > >> - /* We are interested in uses of this BB. */ >> - if (BLOCK_FOR_INSN (use->insn) == g->bb) >> - add_deps_for_use (g, use); >> - } >> + add_deps (g, rd); >> + } >> } >> >> + >> /* Given two nodes, analyze their RTL insns and add inter-loop mem deps >> to ddg G. */ >> static void >> Index: modulo-sched.c >> =================================================================== >> --- modulo-sched.c (revision 126552) >> +++ modulo-sched.c (working copy) >> @@ -914,9 +914,8 @@ >> /* Init Data Flow analysis, to be used in interloop dep calculation. >> > */ > >> df_set_flags (DF_LR_RUN_DCE); >> df_rd_add_problem (); >> - df_ru_add_problem (); >> df_note_add_problem (); >> - df_chain_add_problem (DF_DU_CHAIN + DF_UD_CHAIN); >> + df_chain_add_problem (DF_DU_CHAIN); >> df_analyze (); >> regstat_compute_calls_crossed (); >> sched_init (); >> > >