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. However,
in current GCC implementation, it seems unnecessary since extensive
dependencies 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),
I found a true register dependency is always accompanied with a cross-iteration
anti dependency. This should guarantee the true dependence cannot have lifetime
longer than II.
A --> B true dep (e.g., insn 36 -> insn 38 in the DDG)
B --> A anti dep with distance = 1 (e.g., insn 38 -> insn 36 in the DDG)
The second dependdency should lead to : Sched_Time(A) + II >(=) Sched_Time(B)
which means Sched_Time(B) - Sched_Time(A) <(=) II and no need for reg move.
Similarly, an anti register dependency is always accompanied with a
cross-iteration
true dependency.
A --> B anti dep (e.g., insn 36 -> insn 53 in the DDG)
B --> A true dep with distance = 1 (e.g., insn 53 -> insn 36 in the DDG)
We can reach similar conclusion.
I wonder what other scenario would require to generate reg moves. Am I missing
some obvious points? Thanks in advance.
Cheers,
Bingfeng Mei
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]
IN ARCS: [38 -(A,0,1)-> 36] [53 -(T,1,1)-> 36]
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]
IN ARCS: [38 -(A,0,1)-> 37] [52 -(T,1,1)-> 37]
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]
IN ARCS: [39 -(A,0,1)-> 38] [36 -(T,6,0)-> 38] [37 -(T,6,0)-> 38]
Node num: 3
(insn 39 38 40 3 sms-6.c:11 (set (mem:SI (reg:SI 107 [ ivtmp.45 ]) [3 S4 A32])
(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]
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]
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]
IN ARCS: [42 -(A,0,1)-> 40] [53 -(T,1,1)-> 40]
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]
IN ARCS: [42 -(A,0,1)-> 41] [52 -(T,1,1)-> 41]
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]
IN ARCS: [43 -(A,0,1)-> 42] [40 -(T,6,0)-> 42] [41 -(T,6,0)-> 42]
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]
IN ARCS: [54 -(T,1,1)-> 43] [51 -(O,1,1)-> 43] [47 -(O,1,1)-> 43] [42
-(T,8,0)-> 43]
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]
IN ARCS: [46 -(A,0,1)-> 44] [53 -(T,1,1)-> 44]
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]
IN ARCS: [46 -(A,0,1)-> 45] [52 -(T,1,1)-> 45]
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]
IN ARCS: [47 -(A,0,1)-> 46] [44 -(T,6,0)-> 46] [45 -(T,6,0)-> 46]
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]
IN ARCS: [54 -(T,1,1)-> 47] [51 -(O,1,1)-> 47] [46 -(T,8,0)-> 47]
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]
IN ARCS: [50 -(A,0,1)-> 48] [53 -(T,1,1)-> 48]
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]
IN ARCS: [50 -(A,0,1)-> 49] [52 -(T,1,1)-> 49]
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]
IN ARCS: [51 -(A,0,1)-> 50] [48 -(T,6,0)-> 50] [49 -(T,6,0)-> 50]
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]
IN ARCS: [54 -(T,1,1)-> 51] [50 -(T,8,0)-> 51]
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]
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]
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]
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]
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]
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]
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]
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]
sms-6.c 9 (file, line)
