thr3ads.net - llvm dev - [LLVMdev] RFC: Loop versioning for LICM [Mar 2015]

If this information is useful, please help other people find it:
Share via:

Adam Nemet

2015-Mar-20 04:59 UTC

[LLVMdev] RFC: Loop versioning for LICM

> On Mar 19, 2015, at 9:46 PM, Nema, Ashutosh <Ashutosh.Nema at
amd.com> wrote:
> 
> Thanks Adam for your reply.
>  
> From: Adam Nemet [mailto:anemet at apple.com <mailto:anemet at
apple.com>]
> Sent: Friday, March 20, 2015 3:23 AM
> To: Nema, Ashutosh
> Cc: Hal Finkel; Philip Reames; llvmdev at cs.uiuc.edu <mailto:llvmdev at
cs.uiuc.edu>
> Subject: Re: [LLVMdev] RFC: Loop versioning for LICM
>  
> Hi Ashutosh,
>  
> On Mar 16, 2015, at 9:06 PM, Nema, Ashutosh <Ashutosh.Nema at amd.com
<mailto:Ashutosh.Nema at amd.com>> wrote:
>  
> Hi Adam,
>  
> From: Adam Nemet [mailto:anemet at apple.com <mailto:anemet at
apple.com>]
> Sent: Wednesday, March 11, 2015 10:48 AM
> To: Nema, Ashutosh
> Cc: llvmdev at cs.uiuc.edu <mailto:llvmdev at cs.uiuc.edu>
> Subject: Re: [LLVMdev] RFC: Loop versioning for LICM
>  
> Hi Ashutosh,
>  
> My changes are committed now.  LoopAccessAnalysis is an analysis pass, so
it has the advantage that the result of the analysis is cached until it gets
invalidated (i.e. when the loop changes).
>  
> For an example of how to use it, you can look at either the loop-vectorizer
in the tree or the WIP patch for the loop-distribution pass in
http://reviews.llvm.org/D6930 <http://reviews.llvm.org/D6930>.
>  
> Please let me know if you have any questions.
>  
> I have gone through current LAA, found few gaps for reusing it.
>  
> i.e.
> 928 void LoopAccessInfo::analyzeLoop(const ValueToValueMap &Strides) {
> 1029     if (isUniform(Ptr)) {
> 1030       emitAnalysis(
> 1031           LoopAccessReport(ST)
> 1032           << "write to a loop invariant address could not
be vectorized");
> 1033       DEBUG(dbgs() << "LAA: We don't allow storing to
uniform addresses\n");
> 1034       CanVecMem = false;
> 1035       return;
> 1036     }
>  
> LAA is ignoring the cases where store is loop invariant, it sets memory
can’t be vectorize.
>  
> In loop versioning for LICM, we are more interested in loop invariant
cases.
> Invariant store is one of the important case for
“LICM::promoteLoopAccessesToScalars”
> If there any loop invariant exists then only we do loop versioning.
>  
> This check looks specific to loop vectorizer, with this check we can’t use
LAA for LICM loop versioning.
> If we like to make this reusable probably we need to remove this or make it
conditional.
>  
> Probably, agents to LAA can implements such check instead LAA.
>  
> Not really.  Don’t you need memchecks for loop-invariant addresses as well?
> We do need memcheck for loop-invariant addresses, but with current
implementation if there is any invariant store, LAA simply returns by setting
CanVecMem to false.
>  
> I think we should just teach the analysis to also emit run-time checks for
loop-invariant addresses.  Assuming the memchecks pass we should have valid
dependence analysis results so we could for example distribute the loop.
> Yes, I think that functionality exists, but the only blocker to it is the
check mentioned in my previous mail.
>  
> So, instead of returning & setting ‘CanVecMem’ for loop invariant
store.
> Can’t we maintain a separate variable i.e. hasLoopInvariantStore in
LoopAccessInfo and set it accordingly.
Yes, this is what I was proposing above and here ;):
 > We couldn’t vectorize thus the analysis should provide a new piece of
information about the loop having accesses to loop-invariant addresses.
>  
> Also we can provide a getter function for the same.
>  
> i.e.
> 928 void LoopAccessInfo::analyzeLoop(const ValueToValueMap &Strides) {
> 1029     if (isUniform(Ptr)) {
> 1030        hasLoopInvariantStore = true;
> 1031      }
>  
> So later optimization can use this information in their legality analysis
and make specific actions.
> i.e. LoopVectorizer:
>  
> 4002 bool LoopVectorizationLegality::canVectorizeMemory() {
> 4008   if (LAI->hasLoopInvariantStore) {
> 4009     emitAnalysis(VectorizationReport()
> 4010           << "write to a loop invariant address could not
be vectorized");
> 4011     DEBUG(dbgs() << "LV: We don't allow storing to
uniform addresses\n");
> 4012     return false;
> 4013   }
>  
No, not hasLoopInvariantStore but hasAccessToLoopInvariantAddress.

You will also need to generate the memchecks for such accesses in
canCheckPtrAtRT and addRuntimeCheck.  Without those memchecks passing, the
result of the dependence analysis is incorrect.

Adam
> Adam
>  
> Regards,
> Ashutosh
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150319/b74736d1/attachment.html>

Nema, Ashutosh

2015-Mar-21 03:02 UTC

head link

[LLVMdev] RFC: Loop versioning for LICM

> Yes, this is what I was proposing above and here ;):Thanks Adam it’s for confirming ☺
> No, not hasLoopInvariantStore but hasAccessToLoopInvariantAddress.Its only for invariant stores[not loads], Using ‘hasLoopInvariantStore’ (or a
name with invariant store) makes more sense over
‘hasAccessToLoopInvariantAddress’.
> You will also need to generate the memchecks for such accesses in
> canCheckPtrAtRT and addRuntimeCheck.  Without those memchecks passing,
> the result of the dependence analysis is incorrect.I did not understood this point correctly, I feel the current functionality take
cares of it
And we do not need any new handling for these invariant stores in
“canCheckPtrAtRT” and “addRuntimeCheck”.

“canCheckPtrAtRT” consider all the pointers because its working over AliasSets.
It adds qualified pointers to “RuntimePointerCheck”.

“addRuntimeCheck” works on collected pointers by “canCheckPtrAtRT”
For non-invariant it creates range check by considering start & end.
But for invariant start & end are considered as same.
This same behavior we need for invariant store.

By debugging sample programs I can see its adding invariant stores pointers
to runtime check.

Can you provide more details, what you meant by above comment.

Regards,
Ashutosh

From: Adam Nemet [mailto:anemet at apple.com]
Sent: Friday, March 20, 2015 10:30 AM
To: Nema, Ashutosh
Cc: Hal Finkel; Philip Reames; llvmdev at cs.uiuc.edu
Subject: Re: [LLVMdev] RFC: Loop versioning for LICM

On Mar 19, 2015, at 9:46 PM, Nema, Ashutosh <Ashutosh.Nema at
amd.com<mailto:Ashutosh.Nema at amd.com>> wrote:

Thanks Adam for your reply.

From: Adam Nemet [mailto:anemet at apple.com]
Sent: Friday, March 20, 2015 3:23 AM
To: Nema, Ashutosh
Cc: Hal Finkel; Philip Reames; llvmdev at cs.uiuc.edu<mailto:llvmdev at
cs.uiuc.edu>
Subject: Re: [LLVMdev] RFC: Loop versioning for LICM

Hi Ashutosh,

On Mar 16, 2015, at 9:06 PM, Nema, Ashutosh <Ashutosh.Nema at
amd.com<mailto:Ashutosh.Nema at amd.com>> wrote:

Hi Adam,

From: Adam Nemet [mailto:anemet at apple.com]
Sent: Wednesday, March 11, 2015 10:48 AM
To: Nema, Ashutosh
Cc: llvmdev at cs.uiuc.edu<mailto:llvmdev at cs.uiuc.edu>
Subject: Re: [LLVMdev] RFC: Loop versioning for LICM

Hi Ashutosh,

My changes are committed now.  LoopAccessAnalysis is an analysis pass, so it has
the advantage that the result of the analysis is cached until it gets
invalidated (i.e. when the loop changes).

For an example of how to use it, you can look at either the loop-vectorizer in
the tree or the WIP patch for the loop-distribution pass in
http://reviews.llvm.org/D6930.

Please let me know if you have any questions.

I have gone through current LAA, found few gaps for reusing it.

i.e.
928 void LoopAccessInfo::analyzeLoop(const ValueToValueMap &Strides) {
1029     if (isUniform(Ptr)) {
1030       emitAnalysis(
1031           LoopAccessReport(ST)
1032           << "write to a loop invariant address could not be
vectorized");
1033       DEBUG(dbgs() << "LAA: We don't allow storing to
uniform addresses\n");
1034       CanVecMem = false;
1035       return;
1036     }

LAA is ignoring the cases where store is loop invariant, it sets memory can’t be
vectorize.

In loop versioning for LICM, we are more interested in loop invariant cases.
Invariant store is one of the important case for
“LICM::promoteLoopAccessesToScalars”
If there any loop invariant exists then only we do loop versioning.

This check looks specific to loop vectorizer, with this check we can’t use LAA
for LICM loop versioning.
If we like to make this reusable probably we need to remove this or make it
conditional.

Probably, agents to LAA can implements such check instead LAA.

Not really.  Don’t you need memchecks for loop-invariant addresses as well?
We do need memcheck for loop-invariant addresses, but with current
implementation if there is any invariant store, LAA simply returns by setting
CanVecMem to false.

I think we should just teach the analysis to also emit run-time checks for
loop-invariant addresses.  Assuming the memchecks pass we should have valid
dependence analysis results so we could for example distribute the loop.
Yes, I think that functionality exists, but the only blocker to it is the check
mentioned in my previous mail.

So, instead of returning & setting ‘CanVecMem’ for loop invariant store.
Can’t we maintain a separate variable i.e. hasLoopInvariantStore in
LoopAccessInfo and set it accordingly.

Yes, this is what I was proposing above and here ;):

We couldn’t vectorize thus the analysis should provide a new piece of
information about the loop having accesses to loop-invariant addresses.

Also we can provide a getter function for the same.

i.e.
928 void LoopAccessInfo::analyzeLoop(const ValueToValueMap &Strides) {
1029     if (isUniform(Ptr)) {
1030        hasLoopInvariantStore = true;
1031      }

So later optimization can use this information in their legality analysis and
make specific actions.
i.e. LoopVectorizer:

4002 bool LoopVectorizationLegality::canVectorizeMemory() {
4008   if (LAI->hasLoopInvariantStore) {
4009     emitAnalysis(VectorizationReport()
4010           << "write to a loop invariant address could not be
vectorized");
4011     DEBUG(dbgs() << "LV: We don't allow storing to uniform
addresses\n");
4012     return false;
4013   }

No, not hasLoopInvariantStore but hasAccessToLoopInvariantAddress.

You will also need to generate the memchecks for such accesses in
canCheckPtrAtRT and addRuntimeCheck.  Without those memchecks passing, the
result of the dependence analysis is incorrect.

Adam

Adam

Regards,
Ashutosh

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

Adam Nemet

2015-Mar-24 21:15 UTC

head link

[LLVMdev] RFC: Loop versioning for LICM

> On Mar 20, 2015, at 8:02 PM, Nema, Ashutosh <Ashutosh.Nema at
amd.com> wrote:
> 
> > Yes, this is what I was proposing above and here ;):
> Thanks Adam it’s for confirming J
NP :).
>  
> > No, not hasLoopInvariantStore but hasAccessToLoopInvariantAddress.
> Its only for invariant stores[not loads], Using ‘hasLoopInvariantStore’ (or
a name with invariant store) makes more sense over
‘hasAccessToLoopInvariantAddress’.
Right but it’s the address that’s invariant not the store so
hasLoopInvariantStore is a misleading name.  How about
hasStoreToLoopInvariantAddress?
> > You will also need to generate the memchecks for such accesses in
> > canCheckPtrAtRT and addRuntimeCheck.  Without those memchecks passing,
> > the result of the dependence analysis is incorrect.
> I did not understood this point correctly, I feel the current functionality
take cares of it
> And we do not need any new handling for these invariant stores in
“canCheckPtrAtRT” and “addRuntimeCheck”.
>  
> “canCheckPtrAtRT” consider all the pointers because its working over
AliasSets.
> It adds qualified pointers to “RuntimePointerCheck”.
>  
> “addRuntimeCheck” works on collected pointers by “canCheckPtrAtRT”
> For non-invariant it creates range check by considering start & end.
> But for invariant start & end are considered as same.
> This same behavior we need for invariant store.
>  
> By debugging sample programs I can see its adding invariant stores pointers
> to runtime check.
>  
> Can you provide more details, what you meant by above comment.
I would have expected canCheckPtrAtRT/hasComputableBounds to give up when the
pointer was not a SCEVAddRecExpr.  How do we get passed that point?

Adam
>  
> Regards,
> Ashutosh
>  
> From: Adam Nemet [mailto:anemet at apple.com] 
> Sent: Friday, March 20, 2015 10:30 AM
> To: Nema, Ashutosh
> Cc: Hal Finkel; Philip Reames; llvmdev at cs.uiuc.edu
> Subject: Re: [LLVMdev] RFC: Loop versioning for LICM
>  
>  
> On Mar 19, 2015, at 9:46 PM, Nema, Ashutosh <Ashutosh.Nema at amd.com
<mailto:Ashutosh.Nema at amd.com>> wrote:
>  
> Thanks Adam for your reply.
>  
> From: Adam Nemet [mailto:anemet at apple.com <mailto:anemet at
apple.com>]
> Sent: Friday, March 20, 2015 3:23 AM
> To: Nema, Ashutosh
> Cc: Hal Finkel; Philip Reames; llvmdev at cs.uiuc.edu <mailto:llvmdev at
cs.uiuc.edu>
> Subject: Re: [LLVMdev] RFC: Loop versioning for LICM
>  
> Hi Ashutosh,
>  
> On Mar 16, 2015, at 9:06 PM, Nema, Ashutosh <Ashutosh.Nema at amd.com
<mailto:Ashutosh.Nema at amd.com>> wrote:
>  
> Hi Adam,
>  
> From: Adam Nemet [mailto:anemet at apple.com <mailto:anemet at
apple.com>]
> Sent: Wednesday, March 11, 2015 10:48 AM
> To: Nema, Ashutosh
> Cc: llvmdev at cs.uiuc.edu <mailto:llvmdev at cs.uiuc.edu>
> Subject: Re: [LLVMdev] RFC: Loop versioning for LICM
>  
> Hi Ashutosh,
>  
> My changes are committed now.  LoopAccessAnalysis is an analysis pass, so
it has the advantage that the result of the analysis is cached until it gets
invalidated (i.e. when the loop changes).
>  
> For an example of how to use it, you can look at either the loop-vectorizer
in the tree or the WIP patch for the loop-distribution pass in
http://reviews.llvm.org/D6930 <http://reviews.llvm.org/D6930>.
>  
> Please let me know if you have any questions.
>  
> I have gone through current LAA, found few gaps for reusing it.
>  
> i.e.
> 928 void LoopAccessInfo::analyzeLoop(const ValueToValueMap &Strides) {
> 1029     if (isUniform(Ptr)) {
> 1030       emitAnalysis(
> 1031           LoopAccessReport(ST)
> 1032           << "write to a loop invariant address could not
be vectorized");
> 1033       DEBUG(dbgs() << "LAA: We don't allow storing to
uniform addresses\n");
> 1034       CanVecMem = false;
> 1035       return;
> 1036     }
>  
> LAA is ignoring the cases where store is loop invariant, it sets memory
can’t be vectorize.
>  
> In loop versioning for LICM, we are more interested in loop invariant
cases.
> Invariant store is one of the important case for
“LICM::promoteLoopAccessesToScalars”
> If there any loop invariant exists then only we do loop versioning.
>  
> This check looks specific to loop vectorizer, with this check we can’t use
LAA for LICM loop versioning.
> If we like to make this reusable probably we need to remove this or make it
conditional.
>  
> Probably, agents to LAA can implements such check instead LAA.
>  
> Not really.  Don’t you need memchecks for loop-invariant addresses as well?
> We do need memcheck for loop-invariant addresses, but with current
implementation if there is any invariant store, LAA simply returns by setting
CanVecMem to false.
>  
> I think we should just teach the analysis to also emit run-time checks for
loop-invariant addresses.  Assuming the memchecks pass we should have valid
dependence analysis results so we could for example distribute the loop.
> Yes, I think that functionality exists, but the only blocker to it is the
check mentioned in my previous mail.
>  
> So, instead of returning & setting ‘CanVecMem’ for loop invariant
store.
> Can’t we maintain a separate variable i.e. hasLoopInvariantStore in
LoopAccessInfo and set it accordingly.
>  
> Yes, this is what I was proposing above and here ;):
>  
> We couldn’t vectorize thus the analysis should provide a new piece of
information about the loop having accesses to loop-invariant addresses.
>  
> Also we can provide a getter function for the same.
>  
> i.e.
> 928 void LoopAccessInfo::analyzeLoop(const ValueToValueMap &Strides) {
> 1029     if (isUniform(Ptr)) {
> 1030        hasLoopInvariantStore = true;
> 1031      }
>  
> So later optimization can use this information in their legality analysis
and make specific actions.
> i.e. LoopVectorizer:
>  
> 4002 bool LoopVectorizationLegality::canVectorizeMemory() {
> 4008   if (LAI->hasLoopInvariantStore) {
> 4009     emitAnalysis(VectorizationReport()
> 4010           << "write to a loop invariant address could not
be vectorized");
> 4011     DEBUG(dbgs() << "LV: We don't allow storing to
uniform addresses\n");
> 4012     return false;
> 4013   }
>  
>  
> No, not hasLoopInvariantStore but hasAccessToLoopInvariantAddress.
>  
> You will also need to generate the memchecks for such accesses in
canCheckPtrAtRT and addRuntimeCheck.  Without those memchecks passing, the
result of the dependence analysis is incorrect.
>  
> Adam
>  
> Adam
>  
> Regards,
> Ashutosh
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150324/a8a82a80/attachment.html>

Reasonably Related Threads

Search for more maybe matching threads

llvm dev - Mar 2015 - [LLVMdev] RFC: Loop versioning for LICM

[LLVMdev] RFC: Loop versioning for LICM

[LLVMdev] RFC: Loop versioning for LICM

[LLVMdev] RFC: Loop versioning for LICM

Reasonably Related Threads