This is an archive of the discontinued LLVM Phabricator instance.

Allow LLE/LD and the loop versioning infrastructure to use SCEV predicates
ClosedPublic

Authored by sbaranga on Nov 2 2015, 8:39 AM.

Details

Summary

LAA currently generates a set of SCEV predicates that must be checked by users.
In the case of Loop Distribute/Loop Load Elimination, no such predicates could have
been emitted, since we don't allow stride versioning. However, in the future there
could be SCEV predicates that will need to be checked.

This change adds support for SCEV predicate versioning in the Loop Distribute, Loop
Load Eliminate and the loop versioning infrastructure.

Diff Detail

Event Timeline

sbaranga updated this revision to Diff 38929.Nov 2 2015, 8:39 AM
sbaranga retitled this revision from to Allow Loop Distribute and the loop versioning infrastructure to use SCEV predicates.
sbaranga updated this object.
sbaranga added a reviewer: anemet.
sbaranga added a subscriber: llvm-commits.
anemet edited edge metadata.Nov 4 2015, 9:46 PM

I have a high-level question. How should LoopDist work with SCEVAssumptions? If you look at alias checks we filter those in includeOnlyCrossPartitionChecks to get rid of unnecessary checks.

Could something like this be implemented with SCEVAssumptions? E.g. if you have a may-wrapping pointer that can't alias with anything in the other partition, we don't need to issue the non-wrapping check in order to make distribution correct.

lib/Transforms/Scalar/LoopDistribute.cpp
770–771

This comment needs updating now since we don't only version to disambiguate pointers anymore.

779

Extra () in the first term.

lib/Transforms/Utils/LoopVersioning.cpp
27–35

Now that we will feed LVers with two sets of checks optionally, we should probably move away from taking these in the ctor.

I think that we should have two members like addAliasChecks and addSCEVChecks or something.

I also don't think that we should take LAI but SCEVPredUnion instead.

The second ctor below is fine because the idea there is to take everything from LAI without filtering it.

55

s/MemCheckBB/RuntimeCheckBB

Hi Adam.

I have a high-level question. How should LoopDist work with SCEVAssumptions? If you look at alias checks we filter those in includeOnlyCrossPartitionChecks to get rid of unnecessary checks.

That's an interesting problem. Currently we're only making enough assumptions to return true for LAI.canVectorizeMemory() (and LD checks that anyway).
Since it does that, I think it should add all predicates - for the current behaviour.

However if we wouldn't be interested in the answer for canVectorizeMemory() it should be possible to change MemoryDepChecker::areDepsSafe in LAA such that we have a per-dependence predicate. Then we can ignore the predicates dependences we don't care about. Do you think this approach makes sense?

Thanks,
Silviu

Hi Adam.

I have a high-level question. How should LoopDist work with SCEVAssumptions? If you look at alias checks we filter those in includeOnlyCrossPartitionChecks to get rid of unnecessary checks.

That's an interesting problem. Currently we're only making enough assumptions to return true for LAI.canVectorizeMemory() (and LD checks that anyway).
Since it does that, I think it should add all predicates - for the current behaviour.

However if we wouldn't be interested in the answer for canVectorizeMemory() it should be possible to change MemoryDepChecker::areDepsSafe in LAA such that we have a per-dependence predicate. Then we can ignore the predicates dependences we don't care about. Do you think this approach makes sense?

Thanks,
Silviu

I thought about this some more and besides dependences we would also need to figure out for each MemCheck what predicate needs to be true in order for us to be able to emit it.

sbaranga updated this revision to Diff 39369.Nov 5 2015, 8:09 AM
sbaranga edited edge metadata.

Applied review comments.

sbaranga added inline comments.Nov 5 2015, 8:13 AM
lib/Transforms/Utils/LoopVersioning.cpp
26–35

Removing the Checks parameter made the two constructors have identical arguments. Since we want to be able to construct with all the changes from the LAI, I've added a bool parameter to enable this.

However if we wouldn't be interested in the answer for canVectorizeMemory() it should be possible to change MemoryDepChecker::areDepsSafe in LAA such that we have a per-dependence predicate. Then we can ignore the predicates dependences we don't care about. Do you think this approach makes sense?

I am not saying we should implement this but I'd like to think about this now before committing to a design where we'd have no way of dropping unnecessary predicates.

I am not sure that we need per-dependence predicates though. I think it needs to be per alias set. If you have a pointer that may wrap that can now have a dependence to any of the pointers in the same alias set. It is still OK to drop this predicate for loop distribution if all members of this alias set fall into the same partition.

Where are we going to use SCEVPreds with alias checks? Is it to try to shape a SCEV into an AddRec?

include/llvm/Transforms/Utils/LoopVersioning.h
76–78

Sorry I didn't realize that by suggesting "add" in the name you would make this "additive". The problem is now we lost the nice "move constructibility" of Checks.

How about making this setAliasChecks which would still take a value and then restoring the std::move's.

Would a set* interface work for SCEVUnionPredicate?

95–96

Rename to AliasChecks?

However if we wouldn't be interested in the answer for canVectorizeMemory() it should be possible to change MemoryDepChecker::areDepsSafe in LAA such that we have a per-dependence predicate. Then we can ignore the predicates dependences we don't care about. Do you think this approach makes sense?

I am not saying we should implement this but I'd like to think about this now before committing to a design where we'd have no way of dropping unnecessary predicates.

I am not sure that we need per-dependence predicates though. I think it needs to be per alias set. If you have a pointer that may wrap that can now have a dependence to any of the pointers in the same alias set. It is still OK to drop this predicate for loop distribution if all members of this alias set fall into the same partition.

Where are we going to use SCEVPreds with alias checks? Is it to try to shape a SCEV into an AddRec?

Yes, we would use these to get AddRec expressions. I've also found one additional use case where it's already an AddRec and we want to check for nuw or nsw (see isStridedPtr).

include/llvm/Transforms/Utils/LoopVersioning.h
76–78

Ok, I understand. It wouldn't work at the moment for SCEVUnionPredicate. We need to define copy and move constructors for it. I'll create another review for that.

sbaranga updated this revision to Diff 39533.Nov 6 2015, 7:58 AM

Added versioning to LLE as well. The same outstanding issues remain as with Loop Distribute.
Now using move/copy constructors to pass both alias checks and SCEV predicates to Loop Versioning.

Hi Adam,

I've uploaded a new patch, and had to make LLE use this as well.

Thanks,
Silviu

include/llvm/Transforms/Utils/LoopVersioning.h
76–78

I was confused about the ability of DenseMap to use copy/move constructors, sorry. It turns out we can actually do the same thing as for alias checks.

anemet accepted this revision.Nov 8 2015, 11:34 PM
anemet edited edge metadata.

LGTM. We will have to add thresholds for the SCEV checks as well but right now these are only placeholders since these passes don't use stride checks.

This revision is now accepted and ready to land.Nov 8 2015, 11:34 PM
sbaranga updated this revision to Diff 39681.Nov 9 2015, 5:05 AM
sbaranga edited edge metadata.

Add thresholds for LD and LLE when versioning with SCEV predicates.
These passes won't actually use the predicates (they don't use stride versioning), so the actual value doesn't matter right now.

sbaranga retitled this revision from Allow Loop Distribute and the loop versioning infrastructure to use SCEV predicates to Allow LLE/LD and the loop versioning infrastructure to use SCEV predicates.Nov 9 2015, 5:07 AM
sbaranga updated this object.
sbaranga closed this revision.Nov 9 2015, 5:28 AM

Committed in r252467, thanks!

Hi Adam,

I am not saying we should implement this but I'd like to think about this now before committing to a design where we'd have no way of dropping unnecessary predicates.

I am not sure that we need per-dependence predicates though. I think it needs to be per alias set. If you have a pointer that may wrap that can now have a dependence to any of the pointers in the same alias set. It is still OK to drop this predicate for loop distribution if all members of this alias set fall into the same partition.

Where are we going to use SCEVPreds with alias checks? Is it to try to shape a SCEV into an AddRec?

Did you get a chance to think about this? Should we start a thread on llvm-dev?

I guess this would block the addition of new SCEV predicate types..

Thanks,
Silviu

anemet added a comment.Dec 2 2015, 9:59 AM

Hi Silviu,

Hi Adam,

I am not saying we should implement this but I'd like to think about this now before committing to a design where we'd have no way of dropping unnecessary predicates.

I am not sure that we need per-dependence predicates though. I think it needs to be per alias set. If you have a pointer that may wrap that can now have a dependence to any of the pointers in the same alias set. It is still OK to drop this predicate for loop distribution if all members of this alias set fall into the same partition.

Where are we going to use SCEVPreds with alias checks? Is it to try to shape a SCEV into an AddRec?

Did you get a chance to think about this? Should we start a thread on llvm-dev?

I guess this would block the addition of new SCEV predicate types..

Sorry about the delay. No, I don't think this should hold up further work.

If we want to tag predicates with either the affected dependences or use some other mechanism is an additional improvement to try to reduce the number of predicates. As long as we keep the threshold for the number predicates low for distribution we should be good.

Sorry about the delay. No, I don't think this should hold up further work.

If we want to tag predicates with either the affected dependences or use some other mechanism is an additional improvement to try to reduce the number of predicates. As long as we keep the threshold for the number predicates low for distribution we should be good.

Thanks, that makes sense to me. FWIW this means that after http://reviews.llvm.org/D14296 and a small update to LLE we should be ready to add the no overflow predicates, so we're not that far away.

-Silviu