[SMS, DDG] Additional edges to instructions with clobber

[Roman Zhuykov]

Apologies for the messed up previous e-mail.

This letter contains the first separate patch for ddg.cIt creates
additional nessesary anti-dep edges in data dependency graph.
2011/10/12 Ayal Zaks <ayal.zaks@gmail.com>:>>> The following situation
happens when SMS is enabled without register renaming>>>
(-fno-modulo-sched-allow-regmoves).  When data dependency graph is
built, there>>> is a step when we generate anti-dependencies from last
register use to first>>> write of this register at the next
iteration.>> is a step when we generate anti-dependencies from all
last registers> uses (i.e., of last register def) to first write of
this register at> the next iteration.>
Right.
>>> At this moment we should also>>> create such dependencies to all instructions which clobber the register to>>> prevent this clobbers being before last use is new schedule.>>>>> well, we simply need to connect these last uses to either the first> write *or* the first clobber of this register at the next iteration,> according to whichever is first, no?
No, is works now just how you describe. Clobber is considered as a
write,and last uses are connected with first write or first
clobber.But this is not sufficient: similarly to how there's no
dependenciesbetween last uses,there shall be no dependency between
"first" clobbers (i.e. clobbersof a registercan be permuted freely).
So at least we have to make an additional dependencyedge to each
clobber before first write.
>>> Here is an model of example:>>>>>> loop {>>> set1 regR>>> use1 regR>>> clobber regR>>> set2 regR>>> use2 regR>>> }>>>>>> If we create only use2->set1 anti-dependency (and no use2->cloober) the>>> following wrong schedule is possible:>>>>>> prologue {>>> set1 regR>>> use1 regR>>> clobber regR>>> }>>> kernel {>>> set2 regR>>> clobber regR (instruction from next iteration in terms of old loop kernel)>>> use2 regR>>> set1 regR (also from next iteration)>>> use1 regR (also from next iteration)>>> }>>> epilogue {>>> set2 regR>>> use2 regR>>> }>>>>> strange; according to prolog (and epilog), clobber should appear after> use1 in the kernel, no? Aren't there (intra-iteration) dependencies> preventing the clobber to skip over use1 and/or set1?>
Yeah, this is bad example - I wrongly suggested that there is
noanti-dep between use1 and clobber.
New example:loop { clobber1 clobber2 set use}When there is no
"use->clobber2" anti-dep - the following wrong scheduleis possible.
Clobber2 is on stage0, other instructions are on stage1.prologue {
clobber2}kernel { clobber1 set clobber2 use}epilogue { clobber1 set
use}
>>> This problem was succesfully fixed by creating a vector of all clobbering>>> instructions together with first write and adding all needed dependencies.>>>>> seems like an overkill to me; we didn't draw an edge between every> last use and every write, because writes are kept in order by having> output dependences between them. So should be the case with clobbers.
Clobbers themselves aren't kept in order - there are no output
dependencesbetween them. They may be scheduled in any order.
> 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?
I think the new version of a fix suits this reasoning.Now it creates
dependencies only to clobber instructions before first write.And
certainly to first write instruction itself.
--Roman Zhuykovzhroma@ispras.ru
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ddg-clobber-vector.patch
Type: text/x-patch
Size: 5951 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20111207/6147b21c/attachment.bin>