From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 22316 invoked by alias); 22 Jun 2009 14:10:03 -0000 Received: (qmail 22245 invoked by uid 22791); 22 Jun 2009 14:09:58 -0000 X-SWARE-Spam-Status: No, hits=-0.8 required=5.0 tests=AWL,BAYES_50 X-Spam-Check-By: sourceware.org Received: from mms1.broadcom.com (HELO mms1.broadcom.com) (216.31.210.17) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 22 Jun 2009 14:09:51 +0000 Received: from [10.16.192.232] by mms1.broadcom.com with ESMTP (Broadcom SMTP Relay (Email Firewall v6.3.2)); Mon, 22 Jun 2009 07:09:40 -0700 X-Server-Uuid: 02CED230-5797-4B57-9875-D5D2FEE4708A Received: from SJEXCHCCR02.corp.ad.broadcom.com ([10.16.192.130]) by SJEXCHHUB02.corp.ad.broadcom.com ([10.16.192.232]) with mapi; Mon, 22 Jun 2009 07:09:40 -0700 From: "Bingfeng Mei" To: "Ayal Zaks" cc: "Revital1 Eres" , "gcc@gcc.gnu.org" Date: Mon, 22 Jun 2009 14:10:00 -0000 Subject: Unnecessary regmoves in modulo scheduler? Message-ID: <7FB04A5C213E9943A72EE127DB74F0AD93C58A0D13@SJEXCHCCR02.corp.ad.broadcom.com> References: <7FB04A5C213E9943A72EE127DB74F0AD49E5D35DFF@SJEXCHCCR02.corp.ad.broadcom.com> In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: quoted-printable X-IsSubscribed: yes Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org X-SW-Source: 2009-06/txt/msg00508.txt.bz2 Hello, Ayal, It may be a stupid a question :-). After reading the modulo scheduling code= in GCC, I have a question about necessity of generating reg moves. The reg move is = supposed to break register lifetime > II in absence of rotating register file. Howev= er, in current GCC implementation, it seems unnecessary since extensive depende= ncies are drawn between nodes in GCC. Examining the DDG generated (a DDG based on sms-6.c is appended at the end = of the mail),=20 I found a true register dependency is always accompanied with a cross-itera= tion anti dependency. This should guarantee the true dependence cannot have life= time longer than II.=20 A --> B true dep (e.g., insn 36 -> insn 38 in the DDG) B --> A anti dep with distance =3D 1 (e.g., insn 38 -> insn 36 in the DD= G) The second dependdency should lead to : Sched_Time(A) + II >(=3D) Sched_Tim= e(B) which means Sched_Time(B) - Sched_Time(A) <(=3D) II and no need for reg mov= e.=20 Similarly, an anti register dependency is always accompanied with a cross-i= teration true dependency.=20 A --> B anti dep (e.g., insn 36 -> insn 53 in the DDG) B --> A true dep with distance =3D 1 (e.g., insn 53 -> insn 36 in the DD= G) We can reach similar conclusion. I wonder what other scenario would require to generate reg moves. Am I miss= ing some obvious points? Thanks in advance.=20 Cheers, Bingfeng Mei=20 Broadcom UK DDG from sms-6.c SMS loop num: 1, file: sms-6.c, line: 9 Node num: 0 (insn 36 35 37 3 sms-6.c:11 (set (reg:SI 113) (mem:SI (reg:SI 108 [ ivtmp.44 ]) [4 S4 A32])) 184 {*movwsi} (nil)) OUT ARCS: [36 -(A,0,0)-> 53] [36 -(T,6,0)-> 38]=20 IN ARCS: [38 -(A,0,1)-> 36] [53 -(T,1,1)-> 36]=20 Node num: 1 (insn 37 36 38 3 sms-6.c:11 (set (reg:SI 114) (mem:SI (reg:SI 109 [ ivtmp.42 ]) [5 S4 A32])) 184 {*movwsi} (nil)) OUT ARCS: [37 -(A,0,0)-> 52] [37 -(T,6,0)-> 38]=20 IN ARCS: [38 -(A,0,1)-> 37] [52 -(T,1,1)-> 37]=20 Node num: 2 (insn 38 37 39 3 sms-6.c:11 (set (reg:SI 115) (mult:SI (reg:SI 113) (reg:SI 114))) 262 {mulsi3} (expr_list:REG_DEAD (reg:SI 114) (expr_list:REG_DEAD (reg:SI 113) (nil)))) OUT ARCS: [38 -(A,0,1)-> 37] [38 -(A,0,1)-> 36] [38 -(T,8,0)-> 39]=20 IN ARCS: [39 -(A,0,1)-> 38] [36 -(T,6,0)-> 38] [37 -(T,6,0)-> 38]=20 Node num: 3 (insn 39 38 40 3 sms-6.c:11 (set (mem:SI (reg:SI 107 [ ivtmp.45 ]) [3 S4 A3= 2]) (reg:SI 115)) 184 {*movwsi} (expr_list:REG_DEAD (reg:SI 115) (nil))) OUT ARCS: [39 -(A,0,1)-> 38] [39 -(O,1,0)-> 69] [39 -(A,0,0)-> 54]=20 IN ARCS: [54 -(T,1,1)-> 39] [51 -(O,1,1)-> 39] [47 -(O,1,1)-> 39] [43 -= (O,1,1)-> 39] [38 -(T,8,0)-> 39]=20 Node num: 4 (insn 40 39 41 3 sms-6.c:12 (set (reg:SI 116) (mem:SI (plus:SI (reg:SI 108 [ ivtmp.44 ]) (const_int 4 [0x4])) [4 S4 A32])) 184 {*movwsi} (nil)) OUT ARCS: [40 -(A,0,0)-> 53] [40 -(T,6,0)-> 42]=20 IN ARCS: [42 -(A,0,1)-> 40] [53 -(T,1,1)-> 40]=20 Node num: 5 (insn 41 40 42 3 sms-6.c:12 (set (reg:SI 117) (mem:SI (plus:SI (reg:SI 109 [ ivtmp.42 ]) (const_int 4 [0x4])) [5 S4 A32])) 184 {*movwsi} (nil)) OUT ARCS: [41 -(A,0,0)-> 52] [41 -(T,6,0)-> 42]=20 IN ARCS: [42 -(A,0,1)-> 41] [52 -(T,1,1)-> 41]=20 Node num: 6 (insn 42 41 43 3 sms-6.c:12 (set (reg:SI 118) (mult:SI (reg:SI 116) (reg:SI 117))) 262 {mulsi3} (expr_list:REG_DEAD (reg:SI 117) (expr_list:REG_DEAD (reg:SI 116) (nil)))) OUT ARCS: [42 -(A,0,1)-> 41] [42 -(A,0,1)-> 40] [42 -(T,8,0)-> 43]=20 IN ARCS: [43 -(A,0,1)-> 42] [40 -(T,6,0)-> 42] [41 -(T,6,0)-> 42]=20 Node num: 7 (insn 43 42 44 3 sms-6.c:12 (set (mem:SI (plus:SI (reg:SI 107 [ ivtmp.45 ]) (const_int 4 [0x4])) [3 S4 A32]) (reg:SI 118)) 184 {*movwsi} (expr_list:REG_DEAD (reg:SI 118) (nil))) OUT ARCS: [43 -(A,0,1)-> 42] [43 -(O,1,0)-> 69] [43 -(A,0,0)-> 54] [43 = -(O,1,1)-> 39]=20 IN ARCS: [54 -(T,1,1)-> 43] [51 -(O,1,1)-> 43] [47 -(O,1,1)-> 43] [42 -= (T,8,0)-> 43]=20 Node num: 8 (insn 44 43 45 3 sms-6.c:13 (set (reg:SI 119) (mem:SI (plus:SI (reg:SI 108 [ ivtmp.44 ]) (const_int 8 [0x8])) [4 S4 A32])) 184 {*movwsi} (nil)) OUT ARCS: [44 -(A,0,0)-> 53] [44 -(T,6,0)-> 46]=20 IN ARCS: [46 -(A,0,1)-> 44] [53 -(T,1,1)-> 44]=20 Node num: 9 (insn 45 44 46 3 sms-6.c:13 (set (reg:SI 120) (mem:SI (plus:SI (reg:SI 109 [ ivtmp.42 ]) (const_int 8 [0x8])) [5 S4 A32])) 184 {*movwsi} (nil)) OUT ARCS: [45 -(A,0,0)-> 52] [45 -(T,6,0)-> 46]=20 IN ARCS: [46 -(A,0,1)-> 45] [52 -(T,1,1)-> 45]=20 Node num: 10 (insn 46 45 47 3 sms-6.c:13 (set (reg:SI 121) (mult:SI (reg:SI 119) (reg:SI 120))) 262 {mulsi3} (expr_list:REG_DEAD (reg:SI 120) (expr_list:REG_DEAD (reg:SI 119) (nil)))) OUT ARCS: [46 -(A,0,1)-> 45] [46 -(A,0,1)-> 44] [46 -(T,8,0)-> 47]=20 IN ARCS: [47 -(A,0,1)-> 46] [44 -(T,6,0)-> 46] [45 -(T,6,0)-> 46]=20 Node num: 11 (insn 47 46 48 3 sms-6.c:13 (set (mem:SI (plus:SI (reg:SI 107 [ ivtmp.45 ]) (const_int 8 [0x8])) [3 S4 A32]) (reg:SI 121)) 184 {*movwsi} (expr_list:REG_DEAD (reg:SI 121) (nil))) OUT ARCS: [47 -(A,0,1)-> 46] [47 -(O,1,0)-> 69] [47 -(A,0,0)-> 54] [47 = -(O,1,1)-> 43] [47 -(O,1,1)-> 39]=20 IN ARCS: [54 -(T,1,1)-> 47] [51 -(O,1,1)-> 47] [46 -(T,8,0)-> 47]=20 Node num: 12 (insn 48 47 49 3 sms-6.c:14 (set (reg:SI 122) (mem:SI (plus:SI (reg:SI 108 [ ivtmp.44 ]) (const_int 12 [0xc])) [4 S4 A32])) 184 {*movwsi} (nil)) OUT ARCS: [48 -(A,0,0)-> 53] [48 -(T,6,0)-> 50]=20 IN ARCS: [50 -(A,0,1)-> 48] [53 -(T,1,1)-> 48]=20 Node num: 13 (insn 49 48 50 3 sms-6.c:14 (set (reg:SI 123) (mem:SI (plus:SI (reg:SI 109 [ ivtmp.42 ]) (const_int 12 [0xc])) [5 S4 A32])) 184 {*movwsi} (nil)) OUT ARCS: [49 -(A,0,0)-> 52] [49 -(T,6,0)-> 50]=20 IN ARCS: [50 -(A,0,1)-> 49] [52 -(T,1,1)-> 49]=20 Node num: 14 (insn 50 49 51 3 sms-6.c:14 (set (reg:SI 124) (mult:SI (reg:SI 122) (reg:SI 123))) 262 {mulsi3} (expr_list:REG_DEAD (reg:SI 123) (expr_list:REG_DEAD (reg:SI 122) (nil)))) OUT ARCS: [50 -(A,0,1)-> 49] [50 -(A,0,1)-> 48] [50 -(T,8,0)-> 51]=20 IN ARCS: [51 -(A,0,1)-> 50] [48 -(T,6,0)-> 50] [49 -(T,6,0)-> 50]=20 Node num: 15 (insn 51 50 52 3 sms-6.c:14 (set (mem:SI (plus:SI (reg:SI 107 [ ivtmp.45 ]) (const_int 12 [0xc])) [3 S4 A32]) (reg:SI 124)) 184 {*movwsi} (expr_list:REG_DEAD (reg:SI 124) (nil))) OUT ARCS: [51 -(A,0,1)-> 50] [51 -(O,1,0)-> 69] [51 -(A,0,0)-> 54] [51 = -(O,1,1)-> 47] [51 -(O,1,1)-> 43] [51 -(O,1,1)-> 39]=20 IN ARCS: [54 -(T,1,1)-> 51] [50 -(T,8,0)-> 51]=20 Node num: 16 (insn 52 51 53 3 sms-6.c:14 (set (reg:SI 109 [ ivtmp.42 ]) (plus:SI (reg:SI 109 [ ivtmp.42 ]) (const_int 16 [0x10]))) 220 {addsi3} (nil)) OUT ARCS: [52 -(T,1,1)-> 37] [52 -(T,1,1)-> 41] [52 -(T,1,1)-> 45] [52 = -(T,1,1)-> 49] [52 -(T,1,1)-> 52]=20 IN ARCS: [52 -(T,1,1)-> 52] [49 -(A,0,0)-> 52] [45 -(A,0,0)-> 52] [41 -= (A,0,0)-> 52] [37 -(A,0,0)-> 52]=20 Node num: 17 (insn 53 52 54 3 sms-6.c:14 (set (reg:SI 108 [ ivtmp.44 ]) (plus:SI (reg:SI 108 [ ivtmp.44 ]) (const_int 16 [0x10]))) 220 {addsi3} (nil)) OUT ARCS: [53 -(T,1,1)-> 36] [53 -(T,1,1)-> 40] [53 -(T,1,1)-> 44] [53 = -(T,1,1)-> 48] [53 -(T,1,1)-> 53]=20 IN ARCS: [53 -(T,1,1)-> 53] [48 -(A,0,0)-> 53] [44 -(A,0,0)-> 53] [40 -= (A,0,0)-> 53] [36 -(A,0,0)-> 53]=20 Node num: 18 (insn 54 53 69 3 sms-6.c:14 (set (reg:SI 107 [ ivtmp.45 ]) (plus:SI (reg:SI 107 [ ivtmp.45 ]) (const_int 16 [0x10]))) 220 {addsi3} (nil)) OUT ARCS: [54 -(T,1,1)-> 39] [54 -(T,1,1)-> 43] [54 -(T,1,1)-> 47] [54 = -(T,1,1)-> 51] [54 -(T,1,1)-> 54]=20 IN ARCS: [54 -(T,1,1)-> 54] [51 -(A,0,0)-> 54] [47 -(A,0,0)-> 54] [43 -= (A,0,0)-> 54] [39 -(A,0,0)-> 54]=20 Node num: 19 (jump_insn 69 54 65 3 sms-6.c:9 (parallel [ (set (pc) (if_then_else (ne (reg:SI 126) (const_int 1 [0x1])) (label_ref:SI 55) (pc))) (set (reg:SI 126) (plus:SI (reg:SI 126) (const_int -1 [0xffffffff]))) (unspec [ (const_int 0 [0x0]) ] 98) (clobber (reg:BI 70 p6)) (clobber (scratch:SI)) (clobber (scratch:SI)) ]) 1047 {fp_loop_endsi} (expr_list:REG_UNUSED (reg:BI 70 p6) (expr_list:REG_BR_PROB (const_int 9600 [0x2580]) (nil)))) OUT ARCS: [69 -(T,1,1)-> 69] [69 -(T,1,1)-> 69]=20 IN ARCS: [69 -(T,1,1)-> 69] [69 -(T,1,1)-> 69] [51 -(O,1,0)-> 69] [47 -= (O,1,0)-> 69] [43 -(O,1,0)-> 69] [39 -(O,1,0)-> 69]=20 sms-6.c 9 (file, line)