Revital1 Eres/Haifa/IBM wrote on 13/11/2007 15:13:25: > Hello, > > Following our off-line discussion; attached is the dump file of the > problematic testcase. (sms-4.c) > > Here are some relevant details: > > insn 61(write) and 58(read) were swapped, so sms tries to generate some > kind of reg-move and fails. > > [CYCLE 4 ]: 61, 58, >
Yes, this is wrong, clearly breaking the 58->(A,0,0)->61 dependence. > insn 61 is the only already scheduled instruction which insn 58 depends > on. > > The window of insn 58 is (4 .. -1), calculated as follows: > > Processing edge: [61 -(T,14,1)-> 58] > Scheduling 8 (58) in psp_pss_not_empty, checking p 11 (61): pred st = 4; > early_start = 0; latency: 14 > Processing edge: [58 -(A,0,0)-> 61] > Scheduling 8 (58) in psp_pss_not_empty, checking s 11 (61): succ st = 4; > late_start = 4; latency: 0 > Processing edge: [58 -(T,2,0)-> 59] > Scheduling 8 (58) in psp_pss_not_empty, checking s 9 (59): the node is not scheduled > > Trying to schedule node 8 INSN = 58 in (4 .. -1) step -1 > Scheduled w/o split in 4 > > insn 61 only must_preceed insn 58 because the latency between 61->58 is > 14 which causes the end boundary of the window to be 0. > > Thanks, > Revital > > [attachment "test.c.172r.sms" deleted by Ayal Zaks/Haifa/IBM] Indeed the latency between 61->58 is 14 causing end boundary of the window to be 0: insn 61 is scheduled in cycle 4 and II = 18, so 61->(T,14,1)->58 implies that insn 58 can be scheduled no earlier than 4 - 18 + 14 = 0. But it is not the case that insn 61 must_preceed insn 58, because insn 61 is scheduled in cycle 4 which is not equal to 0 (modulo 18). However, insn 61 must_follow insn 58 when attempting to place insn 58 in cycle 4. When scheduling insn 58, we calculate a window of possible cycles according to already scheduled predecessors and successors. This window looks like a parallelogram in general rather than a rectangle: in the first cycle there may be predecessors (already scheduled in the first cycle, or a multiple of II cycles away) which must_preceed insn 58 (having tight dependence with insn 58 if it is placed in the first cycle). So insn 58 can be placed in 'rightmost' slots of the first cycle only. Similarly, in the last cycle, insn 58 might be placed in 'leftmost' slots only, due to successors which must_follow insn 58. Inside internal cycles (strictly between first and last cycles), insn 58 can be placed in any vacant slot. Now if (as in the above case) an already scheduled insn 61 is both a successor and a predecessor of insn 58, it may be that (not it the above case) insn 61 must_precede insn 58 (when looking for available slots for insn 58 in the first cycle) and must_follow insn 58 (when looking for available slots in the last cycle). Currently we apply the must_precede and must_follow restrictions to all cycles of the window. This is overly conservative (i.e., should not produce above wrong code!). One way to improve this is to split the window into first cycle (with must_precede), internal part (with neither must_precede nor must_follow), and last cycle (with must_follow). And, of-course, if first cycle == last cycle, apply both must_precede and must_follow for it. Finally, note that in the above case we traverse the window backwards with step -1, so 'start' is the last cycle 4, and 'end' is one past the first cycle 0 (i.e. -1). Ayal.
