This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Fw: [PATCH/RFC/PR28071]: New scheduler dependencies lists.
- From: Ayal Zaks <ZAKS at il dot ibm dot com>
- To: Maxim Kuvyrkov <mkuvyrkov at ispras dot ru>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Wed, 24 Jan 2007 01:11:09 +0200
- Subject: Fw: [PATCH/RFC/PR28071]: New scheduler dependencies lists.
>RESEND with CC to gcc-patches. Sorry for inconvenience.
likewise ...
----- Forwarded by Ayal Zaks/Haifa/IBM on 24/01/07 01:09 -----
Ayal
Zaks/Haifa/IBM
To
24/01/07 00:41 Maxim Kuvyrkov
<mkuvyrkov@ispras.ru>
cc
Subject
Re: [PATCH/RFC/PR28071]: New
scheduler dependencies lists.
(Document link: Ayal Zaks)
I took a look at the diagram first:
> +/* A node in the DDG.
> + .
> + . +--------------+
> + . |dep_node |
> + . | |
> + . | +--------+ |
> + . | |dep | |
> + . | | | |
> + . | | +---+ | |
> + . +----------+--+-|pro| | |
> + . | | | +---+ | |
> + . | | | | |
> + . | | | +---+ | |
> + . | +-+--+-|con| | |
> + . | | | | +---+ | |
> + . | | | +--------+ |
> + . V | | |
> + +-------------+ | | +--------+ |
> + |pro | | | |forw | |
> + | | | | | | |
> + | +---------+ | | | | +----+ | |
> + | |forw_deps|-+-+-+->| |next|-+--+---> next forw field of the
dep_node
> + | +---------+ | | | | +----+ | | with the same PRO and another
CON.
> + +-------------+ | | | | |<-+
> + . | | | +----+ | | |
> + . | | | |node|-+--+--+
> + . +--------+ | | +----+ | |
> + . | | +--------+ |
> + . V | |
> + +-------------+ | +--------+ |
> + |con | | |back | |
> + | | | | | |
> + | +---------+ | | | +----+ | |
> + | |back_deps|-+---+->| |next|-+--+---> next back field of the
dep_node
> + | +---------+ | | | +----+ | | with the same CON and another
PRO.
> + +-------------+ | | | |<-+
> + . | | +----+ | | |
> + . | | |node|-+--+--+
> + . | | +----+ | |
> + . | +--------+ |
> + . +--------------+
> +*/
I'm not sure if it's any better, but you may want to elaborate more, as in
(which might be too much):
----
Suppose we have a depedence Y between insn pro1 and con1, where pro1 has
additional dependants con0 and con2, and con1 is dependant on additional
insns pro0 and pro1:
con0 pro0
^ |
| |
| |
X A
| |
| |
| V
pro1--Y-->con1
| ^
| |
| |
Z B
| |
| |
V |
con2 pro2
This is represented using a "dep_node" for each dependence arc, which are
connected as follows (diagram is centered around Y which is fully shown;
other dep_nodes shown partially):
+------------+ +--------------+ +------------+
: dep_node X : | dep_node Y | : dep_node Z :
: : | | : :
: : | | : :
: forw : | forw | : forw :
: +--------+ : | +--------+ | : +--------+ :
forw_deps : |dep_link| : | |dep_link| | : |dep_link| :
+-----+ : | +----+ | : | | +----+ | | : | +----+ | :
|first|--->: | |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
+-----+ : | +----+ | : | | +----+ | | : | +----+ | :
| ^ : | ^ | : | | ^ | | : | | :
| | : | | | : | | | | | : | | :
| +--<----+--+ +--+---<--+--+--+ +--+--+--<---+--+ | :
| : | | | : | | | | | : | | | :
| : | +----+ | : | | +----+ | | : | +----+ | :
| : | |prev| | : | | |prev| | | : | |prev| | :
| : | |next| | : | | |next| | | : | |next| | :
| : | +----+ | : | | +----+ | | : | +----+ | :
| : | | :<-+ | | | |<-+ : | | :<-+
| : | +----+ | : | | | +----+ | | | : | +----+ | : |
| : | |node|-+----+ | | |node|-+--+--+ : | |node|-+----+
| : | +----+ | : | | +----+ | | : | +----+ | :
| : | | : | | | | : | | :
| : +--------+ : | +--------+ | : +--------+ :
| : : | | : :
| : SAME pro1 : | +--------+ | : SAME pro1 :
| : DIFF con0 : | |dep | | : DIFF con2 :
| : : | | | | : :
| | | +----+ | |
RTX<------------------------+--+-|pro1| | |
pro1 | | +----+ | |
| | | |
| | +----+ | |
RTX<------------------------+--+-|con1| | |
con1 | | +----+ | |
| | | | |
| | | +----+ | |
| | | |kind| | |
| | | +----+ | |
| : : | | |stat| | | : :
| : DIFF pro0 : | | +----+ | | : DIFF pro2 :
| : SAME con1 : | | | | : SAME con1 :
| : : | +--------+ | : :
| : : | | : :
| : back : | back | : back :
| : +--------+ : | +--------+ | : +--------+ :
back_deps : |dep_link| : | |dep_link| | : |dep_link| :
+-----+ : | +----+ | : | | +----+ | | : | +----+ | :
|first|--->: | |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
+-----+ : | +----+ | : | | +----+ | | : | +----+ | :
^ : | ^ | : | | ^ | | : | | :
| : | | | : | | | | | : | | :
+--<----+--+ +--+---<--+--+--+ +--+--+--<---+--+ | :
: | | | : | | | | | : | | | :
: | +----+ | : | | +----+ | | : | +----+ | :
: | |prev| | : | | |prev| | | : | |prev| | :
: | |next| | : | | |next| | | : | |next| | :
: | +----+ | : | | +----+ | | : | +----+ | :
: | | :<-+ | | | |<-+ : | | :<-+
: | +----+ | : | | | +----+ | | | : | +----+ | : |
: | |node|-+----+ | | |node|-+--+--+ : | |node|-+----+
: | +----+ | : | | +----+ | | : | +----+ | :
: | | : | | | | : | | :
: +--------+ : | +--------+ | : +--------+ :
: : | | : :
: dep_node A : | dep_node Y | : dep_node B :
+------------+ +--------------+ +------------+
---
Ayal.