From patchwork Wed Dec 7 15:35:25 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Roman Zhuykov X-Patchwork-Id: 129984 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 679141007D1 for ; Thu, 8 Dec 2011 02:35:43 +1100 (EST) Received: (qmail 2486 invoked by alias); 7 Dec 2011 15:35:40 -0000 Received: (qmail 2232 invoked by uid 22791); 7 Dec 2011 15:35:39 -0000 X-SWARE-Spam-Status: No, hits=-2.3 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, TW_DD X-Spam-Check-By: sourceware.org Received: from mail-iy0-f175.google.com (HELO mail-iy0-f175.google.com) (209.85.210.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 07 Dec 2011 15:35:26 +0000 Received: by iadj38 with SMTP id j38so1132742iad.20 for ; Wed, 07 Dec 2011 07:35:25 -0800 (PST) MIME-Version: 1.0 Received: by 10.42.172.70 with SMTP id m6mr20074381icz.37.1323272125322; Wed, 07 Dec 2011 07:35:25 -0800 (PST) Received: by 10.231.176.9 with HTTP; Wed, 7 Dec 2011 07:35:25 -0800 (PST) Date: Wed, 7 Dec 2011 18:35:25 +0300 Message-ID: Subject: [SMS, DDG] Correctly delete anti-dep edges for renaming From: Roman Zhuykov To: Ayal Zaks Cc: gcc-patches@gcc.gnu.org, dm@ispras.ru X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org This letter contains second separate patch for ddg.c It prevents removing some edges in data dependency graph when renaming is allowed. 2011/10/12 Ayal Zaks : >>> The other bug happens only with -fmodulo-sched-allow-regmoves. Here we >>> eliminate some anti-dependence edges in data dependency graph in order to >>> resolve them later by adding some register moves (renaming instructions). But >>> in situation as in example above compiler gives an ICE because it can't create >>> a register move, when regR is hardware flag register. So we have to know which >>> register(s) cause anti-dependency in order to understand whether we can ignore >>> it. I can't find any easy way to gather this information, so I create my own >>> structures to store this info and had implemented my own hooks for >>> sched_analyze function. This leads to more complex interconnection between >>> ddg.c and modulo-sched.c. > > Well, having ddg.c's/create_ddg_dep_from_intra_loop_link() consult > "Register sets from modulo scheduler structures" to determine if an > anti-dep can be eliminated, seems awkward. One should be able to build > a ddg independent of any modulo scheduler structures. I think now I found a proper way to gather information about the register(s) causing anti-dependency (see the patch attached). > One simple solution is to keep all anti-dep edges of registers that > are clobbered anywhere in the loop. This might be overly conservative, > but perhaps not so if "On x86_64 it is clobbered by most of arithmetic > instructions". > If an anti-dep between a use and a dep of a clobber register is to be > removed, a dependence should be created between the use and a > clobbering instruction following the def. Hope this is clear. > > This too should be solved by a dedicated (separate) patch, for easier digestion. > > Presumably, the ddg already has all intra-iteration edges preventing > motion of clobbering instructions within an iteration, and we are only > missing inter-iteration deps or deps surfaced by eliminating > anti-deps, right? > > You might consider introducing a new type of dependence for such > edges, "Clobber", if it would help. > Ayal, I suppose here we have some misunderstanding. This is not directly related to the problem of clobbers discussed previously. Here I talk about the need to find out the register causing the anti-dependence (for instance, we need to check whether it can be renamed). Currently, SMS simply attempts to take the RHS of the second instruction (via single_set()), and if it's a register, SMS assumes it's a register causing the dependency. This breaks in a following scenario: insn1: ... (read flags) insn2: regA = regB - regC; update flags Here, SMS would wrongly take regA as the dependency register, while it was in fact the flags register. So, I rewrote this part in a different way and make a separate patch. --- Roman Zhuykov zhroma@ispras.ru 2011-12-07 Roman Zhuykov * ddg.c (create_ddg_dep_from_intra_loop_link): Correclty determine which register causes anti-dependency. Prevent removing anti-dep edge from ddg when hard_register_p. --- diff --git a/gcc/ddg.c b/gcc/ddg.c index 2b1cfe8..0a3726f 100644 --- a/gcc/ddg.c +++ b/gcc/ddg.c @@ -204,23 +204,34 @@ create_ddg_dep_from_intra_loop_link (ddg_ptr g, ddg_node_ptr src_node, && (t == ANTI_DEP && dt == REG_DEP) && !autoinc_var_is_used_p (dest_node->insn, src_node->insn)) { - rtx set; + df_ref *def_rec; + bool can_delete_dep = true; - set = single_set (dest_node->insn); - /* TODO: Handle registers that REG_P is not true for them, i.e. + /* TODO: Handle !REG_P register correctly, i.e. subregs and special registers. */ - if (set && REG_P (SET_DEST (set))) - { - int regno = REGNO (SET_DEST (set)); - df_ref first_def; - struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb); + for (def_rec = DF_INSN_DEFS (dest_node->insn); *def_rec; def_rec++) + { + df_ref first_def, def = *def_rec, *use_rec; + unsigned regno = DF_REF_REGNO (def); + struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb); + bool src_uses = false; - first_def = df_bb_regno_first_def_find (g->bb, regno); - gcc_assert (first_def); + for (use_rec = DF_INSN_USES (src_node->insn); *use_rec; use_rec++) + if (regno == DF_REF_REGNO (*use_rec)) + src_uses = true; - if (bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def))) - return; - } + if (!src_uses) + continue; + + first_def = df_bb_regno_first_def_find (g->bb, regno); + gcc_assert (first_def); + + if (HARD_REGISTER_NUM_P (regno) + || !bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def))) + can_delete_dep = false; + } + if (can_delete_dep) + return; } latency = dep_cost (link);