[Polly][GSoC 2016]New API to check vectorization legality of a loop
AcceptedPublic

Authored by cs14mtech11017 on Jul 15 2016, 5:51 AM.

Details

Summary

Provide an API isVectorizable(Loop *L, int *VF) to the PolyhedralInfo interface to check for vectorization legality of a loop.
If loop is not trivially vectorizable and the minimum dependence distance is greater than the input VF, update the VF with the minimum dependence distance of the loop.
Currently, the interface checks for only constant dependence distances.
We will add support for parametric distance in the future.

Depends on D21486

Diff Detail

cs14mtech11017 retitled this revision from to [Polly][GSoC 2016]New API to check vectorization legality of a loop.Jul 15 2016, 5:51 AM
cs14mtech11017 updated this object.
cs14mtech11017 added subscribers: pollydev, grosser.
jdoerfert added inline comments.Jul 15 2016, 6:26 AM
include/polly/PolyhedralInfo.h
52

factor

55

Describe the update of @p VF in more details somewhere.

lib/Analysis/PolyhedralInfo.cpp
128–129

I don;t think this is necessary.

132

if checkParallel retuirns true, the loop is trivially vectorizable for all vector widths. Only if it is not parallel you have to check if MinDistancePtr is set and if so you can check if it is constant or whatever.

cs14mtech11017 marked 3 inline comments as done.

Updated as per review comments.

lib/Analysis/PolyhedralInfo.cpp
132

I agree. Updated accordingly.

cs14mtech11017 updated this object.
cs14mtech11017 marked an inline comment as done.
cs14mtech11017 updated this object.
jdoerfert added inline comments.Jul 15 2016, 7:53 AM
include/polly/PolyhedralInfo.h
52

You do not update VF to a bigger value, do you? If not remove that sentence.

55

Because you update VF in certain cases you have to describe what happens exactly for which case and that should make sense. For example you should set VF to a "special" value if the loop is trivially vectorizable because otherwise there is no difference to the case where VF is the biggest vector with possible.

lib/Analysis/PolyhedralInfo.cpp
112–113

We try to use a static_cast<int *>(User) for these cases.

118

Why do we need a cast here [what's the return type of get_num_si]? Is int really what we want or wouldn't unsigned or uint_64 be better for the minimal dependence distance?

136

Please check explicitly fi MinDistancePtr is null even if the isl functions "do the right thing" in that case.

139

999 is an odd value... maybe use INT_MAX or *VF?

Meinersbur added inline comments.Jul 15 2016, 9:55 AM
include/polly/PolyhedralInfo.h
48–49

I am a but confused with the terminology. What is the difference between "dependence distance" and "vectorization factor? Do they have the same meaning as "SIMD width"?

52

If I read correctly, it updates VF only to bigger values (and to at most 999). In case of smaller VF, the function would return false ("Not vectorizable with that VF"). Strangely, it is not updated if the VF is "infinite" (parallel).

lib/Analysis/PolyhedralInfo.cpp
71

Could we also print the max vectorization factor?

jdoerfert added inline comments.Jul 18 2016, 12:18 AM
include/polly/PolyhedralInfo.h
48–49

"dependence distance" ==> The distance (in loop iterations) of a (loop carried) dependence.
"vectorization factor" == "SIMD width"

We use the same terminology in Polly already (Ast and NodeBuilder).

52

I agree and I tried to state these problems earlier already.

lib/Analysis/PolyhedralInfo.cpp
142

There is no "min computation" happening in the getMinDependenceDistance function. It will just update MinDepDistance and the distance of the last dependence will be the resutl...

cs14mtech11017 marked 5 inline comments as done.
cs14mtech11017 added inline comments.
include/polly/PolyhedralInfo.h
52

We do update VF to a bigger value.
If the loop is trivially vectorizable, set VF to INT_MAX. Thanks Michael for pointing that out.
If the loop is vectorizable for the given VF, update VF to the minimum dependence distance, which is the permissible VF. User needs to check for power of 2.

If the minimum dependence distance is not constant, loop is not vectorizable and do not update VF. We will work on non constant distance later at some point.

lib/Analysis/PolyhedralInfo.cpp
118

isl_val_get_num_si return a long. Not sure whether we will actually work on such a big value.

142

I am not sure what you meant by that.
It is actually computing the minimum dependence distance. Please refer to test case test/Isl/Ast/dependence_distance_varying_multiple.ll.

jdoerfert accepted this revision.Aug 12 2016, 5:36 AM

In general this LGTM. Maybe look at my last comments and once you finalize this patch ask somebody to push it for you.

include/polly/PolyhedralInfo.h
49

compute the maximum vectorization factor (as that is what is described below).

52

Do we really need to provide a initial VF or couldn't we just say it is updated by the function accordingly? Then it will return false if not vectorizable, true if it is and VF will be initialized to the minimal dependence distance = maximal vectorization factor = maximal simd widht.

58

remove "give" as it might have been updated.

lib/Analysis/PolyhedralInfo.cpp
142

I think I was misstaken anyway. Just forget about it.

This revision is now accepted and ready to land.Aug 12 2016, 5:36 AM