llvm dev - Aug 2017 - Missing some cross iteration memory dependencies for software pipeline?

Hi, bcahoon,

I found in Machinepipeliner, addLoopCarriedDependences function only create
store-->load true mem dependence when identifying recurrences.
But in ScheduleDAGInstrs, there may be three kinds of mem order
dependencies(store-->load, load-->store, store-->store) inside one
iteration.
When calculating loop carried dependence, in addition to register
dependence(phis), we also need to consider the above three kinds of memory
dependencies to build cross iterations graph.
For example,
    STORE Reg1, Reg0 + Offset0      //INSN_A
    ... ...
    STORE Reg3, Reg2 + Offset2      //INSN_B
If INSN_A-->INSN_B(*store-->store*) had  mem order dependence inside the
iteration(Assuming that alias analysis result for the addresses Reg0 +
Offset0/Reg2 + Offset2 were dependent)
For  cross iteration dependence, INSN_B-->INSN_A must have mem
order dependence too.
So I wonder why in current implementation of swp, there're no enough mem
loop carried dependence? will it cause some correct problems?
Also, I checked SMS pass in GCC, and found that DDG graph will construct
correct cross iteration memory dependence(store-->load, load-->store,
store-->store)

Thanks,
Wei Wei
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170817/c15d6a4b/attachment.html>

Hi Wei Wei,

 

You’re correct.  The addLoopCarriedDependences function is creating loop carried
store->load dependences only.  The other dependences you’ve listed need to be
added as well for correctness.  The missing dependences are just an oversight.

 

Thanks,

Brendon

 

From: wei wei [mailto:wweiandrew at gmail.com] 
Sent: Thursday, August 17, 2017 10:50 AM
To: bcahoon at codeaurora.org
Cc: llvm-dev at lists.llvm.org
Subject: Missing some cross iteration memory dependencies for software pipeline?

 

Hi, bcahoon,

 

I found in Machinepipeliner, addLoopCarriedDependences function only create
store-->load true mem dependence when identifying recurrences.

But in ScheduleDAGInstrs, there may be three kinds of mem order
dependencies(store-->load, load-->store, store-->store) inside one
iteration.

When calculating loop carried dependence, in addition to register
dependence(phis), we also need to consider the above three kinds of memory
dependencies to build cross iterations graph.

For example,

    STORE Reg1, Reg0 + Offset0      //INSN_A

    ... ...

    STORE Reg3, Reg2 + Offset2      //INSN_B

If INSN_A-->INSN_B(store-->store) had  mem order dependence inside the
iteration(Assuming that alias analysis result for the addresses Reg0 +
Offset0/Reg2 + Offset2 were dependent)

For  cross iteration dependence, INSN_B-->INSN_A must have mem order
dependence too.

So I wonder why in current implementation of swp, there're no enough mem
loop carried dependence? will it cause some correct problems?

Also, I checked SMS pass in GCC, and found that DDG graph will construct correct
cross iteration memory dependence(store-->load, load-->store,
store-->store)

 

Thanks,

Wei Wei

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170824/8d663eb5/attachment.html>