llvm dev - Feb 2015 - [LLVMdev] [PATCH] Bugfix for missed dependency from store to load in buildSchedGraph().

Hi,

I would be happy to give it a try :-)

The fact that AA was added at a later point explains the situation a bit, as
much fewer SUs should end up in RejectMemNodes without it.

RejectMemNodes is bad in that it mixes all the SUs together again, after having
gone through the work of separating them by analyzing their underlying objects.
It is also very confusing to have two "stages" of dependency checking,
first by mapping an SU to one or more Values, and then to still
"check everything" that may have been missed.

I would like to try to remove RejectMemNodes (and adjustChainDeps() and
iterateChainSucc()) and then simply not clear the MemUses list (while handling a
store). “If an SU gets a Value mapping, keep it”.
If that list grows bigger than a certain limit, intelligent alias querying could
stop, just as it stops now in iterateChainSucc when *Depth > 200.
But it would then at least be done against the right set of SUs, not against
"all SUs that sometime did not need an edge".

What do you think about this, anyone?

/ Jonas Paulsson



From: Andrew Trick [mailto:atrick at apple.com]
Sent: den 10 februari 2015 22:12
To: Jonas Paulsson
Cc: Hal Finkel; Mattias Eriksson V; llvmdev at cs.uiuc.edu; Tom Stellard; Sergei
Larin; Patrik Hägglund H; Sanjin Sijaric; llvm commits
Subject: Re: [PATCH] Bugfix for missed dependency from store to load in
buildSchedGraph().


On Feb 10, 2015, at 6:54 AM, Jonas Paulsson <jonas.paulsson at
ericsson.com<mailto:jonas.paulsson at ericsson.com>> wrote:

Looking at the possibility of refactorization / redesign, I wonder what are the
main strong
points of this implementation right now, in your opinion? The mapping to
underlying objects
looks nice to me, but I am not sure I understand why to go through the trouble
of clearing
lists and using a set of RejectMemNodes with adjustChainDeps(). It is very
complex code, and
I wonder what is gained in the end here. Does anyone have any thoughts about it?
Is it to handle
huge regions with tons of memory accesses well?

Since you’ve taken the time to understand the algorithm, and are actively
benchmarking, it would be great to take advantage of the opportunity to rewrite.
Feel free to modify even the core DAG builder implementation, which hasn’t
really changed since inception--way before my time. The alias-aware scheduling
has been around long enough that it makes sense to redesign the core DAG builder
code around it, rather than bolt it on. I agree, in its current form, the
AA-aware logic is too hard to follow.

Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150211/cf789582/attachment.html>

> On Feb 11, 2015, at 9:40 AM, Jonas Paulsson <jonas.paulsson at
ericsson.com> wrote:
> 
> Hi,
>  
> I would be happy to give it a try :-)
>  
> The fact that AA was added at a later point explains the situation a bit,
as much fewer SUs should end up in RejectMemNodes without it.
>  
> RejectMemNodes is bad in that it mixes all the SUs together again, after
having gone through the work of separating them by analyzing their underlying
objects.
> It is also very confusing to have two "stages" of dependency
checking, first by mapping an SU to one or more Values, and then to still
> "check everything" that may have been missed.
>  
> I would like to try to remove RejectMemNodes (and adjustChainDeps() and
iterateChainSucc()) and then simply not clear the MemUses list (while handling a
store). “If an SU gets a Value mapping, keep it”.
> If that list grows bigger than a certain limit, intelligent alias querying
could stop, just as it stops now in iterateChainSucc when *Depth > 200.
> But it would then at least be done against the right set of SUs, not
against "all SUs that sometime did not need an edge".
>  
> What do you think about this, anyone?
My main requirements are
- AA-aware dependencies are still off by default
- default behavior is (obviously) not impacted
- default compile time does not significantly increase

I’m not heavily invested in the AA-aware part of the design, so I’ll leave that
to you, Hal, Sergei, and whoever else is using it.

Andy
>  
> / Jonas Paulsson
>  
>  
>  
> From: Andrew Trick [mailto:atrick at apple.com] 
> Sent: den 10 februari 2015 22:12
> To: Jonas Paulsson
> Cc: Hal Finkel; Mattias Eriksson V; llvmdev at cs.uiuc.edu; Tom Stellard;
Sergei Larin; Patrik Hägglund H; Sanjin Sijaric; llvm commits
> Subject: Re: [PATCH] Bugfix for missed dependency from store to load in
buildSchedGraph().
>  
>  
> On Feb 10, 2015, at 6:54 AM, Jonas Paulsson <jonas.paulsson at
ericsson.com <mailto:jonas.paulsson at ericsson.com>> wrote:
>  
> Looking at the possibility of refactorization / redesign, I wonder what are
the main strong
> points of this implementation right now, in your opinion? The mapping to
underlying objects
> looks nice to me, but I am not sure I understand why to go through the
trouble of clearing
> lists and using a set of RejectMemNodes with adjustChainDeps(). It is very
complex code, and
> I wonder what is gained in the end here. Does anyone have any thoughts
about it?  Is it to handle
> huge regions with tons of memory accesses well?
>  
> Since you’ve taken the time to understand the algorithm, and are actively
benchmarking, it would be great to take advantage of the opportunity to rewrite.
Feel free to modify even the core DAG builder implementation, which hasn’t
really changed since inception--way before my time. The alias-aware scheduling
has been around long enough that it makes sense to redesign the core DAG builder
code around it, rather than bolt it on. I agree, in its current form, the
AA-aware logic is too hard to follow.
>  
> Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150211/515982c1/attachment.html>

Hi,

http://reviews.llvm.org/D7850

I have now worked on this for a while and you can inspect my results by
following the link above.

/Jonas

PS (It seems that phabricator failed to mail llvm-commits for some reason. I
added llvm-commits as subscriber in the browser, but nothing happened).



From: Andrew Trick [mailto:atrick at apple.com]
Sent: den 11 februari 2015 18:50
To: Jonas Paulsson
Cc: Hal Finkel; Mattias Eriksson V; llvmdev at cs.uiuc.edu; Tom Stellard; Sergei
Larin; Patrik Hägglund H; Sanjin Sijaric; llvm commits
Subject: Re: [PATCH] Bugfix for missed dependency from store to load in
buildSchedGraph().


On Feb 11, 2015, at 9:40 AM, Jonas Paulsson <jonas.paulsson at
ericsson.com<mailto:jonas.paulsson at ericsson.com>> wrote:

Hi,

I would be happy to give it a try :-)

The fact that AA was added at a later point explains the situation a bit, as
much fewer SUs should end up in RejectMemNodes without it.

RejectMemNodes is bad in that it mixes all the SUs together again, after having
gone through the work of separating them by analyzing their underlying objects.
It is also very confusing to have two "stages" of dependency checking,
first by mapping an SU to one or more Values, and then to still
"check everything" that may have been missed.

I would like to try to remove RejectMemNodes (and adjustChainDeps() and
iterateChainSucc()) and then simply not clear the MemUses list (while handling a
store). “If an SU gets a Value mapping, keep it”.
If that list grows bigger than a certain limit, intelligent alias querying could
stop, just as it stops now in iterateChainSucc when *Depth > 200.
But it would then at least be done against the right set of SUs, not against
"all SUs that sometime did not need an edge".

What do you think about this, anyone?

My main requirements are
- AA-aware dependencies are still off by default
- default behavior is (obviously) not impacted
- default compile time does not significantly increase

I’m not heavily invested in the AA-aware part of the design, so I’ll leave that
to you, Hal, Sergei, and whoever else is using it.

Andy



/ Jonas Paulsson



From: Andrew Trick [mailto:atrick at apple.com]
Sent: den 10 februari 2015 22:12
To: Jonas Paulsson
Cc: Hal Finkel; Mattias Eriksson V; llvmdev at cs.uiuc.edu<mailto:llvmdev at
cs.uiuc.edu>; Tom Stellard; Sergei Larin; Patrik Hägglund H; Sanjin Sijaric;
llvm commits
Subject: Re: [PATCH] Bugfix for missed dependency from store to load in
buildSchedGraph().


On Feb 10, 2015, at 6:54 AM, Jonas Paulsson <jonas.paulsson at
ericsson.com<mailto:jonas.paulsson at ericsson.com>> wrote:

Looking at the possibility of refactorization / redesign, I wonder what are the
main strong
points of this implementation right now, in your opinion? The mapping to
underlying objects
looks nice to me, but I am not sure I understand why to go through the trouble
of clearing
lists and using a set of RejectMemNodes with adjustChainDeps(). It is very
complex code, and
I wonder what is gained in the end here. Does anyone have any thoughts about it?
Is it to handle
huge regions with tons of memory accesses well?

Since you’ve taken the time to understand the algorithm, and are actively
benchmarking, it would be great to take advantage of the opportunity to rewrite.
Feel free to modify even the core DAG builder implementation, which hasn’t
really changed since inception--way before my time. The alias-aware scheduling
has been around long enough that it makes sense to redesign the core DAG builder
code around it, rather than bolt it on. I agree, in its current form, the
AA-aware logic is too hard to follow.

Andy

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