Page MenuHomePhabricator

[GSoC] Schedule tree performance.
Needs ReviewPublic

Authored by chelini on Jun 14 2018, 2:43 AM.

Details

Summary

This patch detects streaming kernels using the 5-tuples classification and avoids tiling them (please refer to the following doc for more details: https://docs.google.com/document/d/1OOMg37pXI3bBkHMAtQsfszYwJ6-GvpO9e4zQ2qf44tM/edit).

I upload this patch to have some feedback from the community and fire some discussions. Is this the right approach to follow?

Diff Detail

Event Timeline

chelini created this revision.Jun 14 2018, 2:43 AM
chelini updated this revision to Diff 151607.Jun 15 2018, 11:02 PM

Thanks for the patch! I've added some comments about general LLVM style, and some personal choices. Feel free to ignore the personal choices :)

  • I value const highly, but this is not true across LLVM and Polly.
  • Also, please run the file through ninja polly-update-format, It'll fix the formatting according to the formatting guidelines that are enforced using clang-format. I think in some places, the formatting is off?
include/polly/ScheduleOptimizer.h
28

Consider using llvm::SmallVector, which is usually more performant.

29

consider SmallVector?

31

Ditto. SmallVector

33

Consider enum class over enum, it is slightly stronger with respect to typecasting, and is better namespaced.

45

I am not sure I like the use of struct here. Usually, it is use to signal a POD (poor old data type) with no complex constructor. In this case, since it owns an std::vector (or may own a SmallVector), I would prefer it being tagged class.

You could still make everything public if that's what you wanted by making it a struct.

45

Also, why Skeleton? Is this some name in the paper?

Please add a line of description above why this struct is called Skeleton and what it tracks.

46

consider SmallVector?

47

I am a little hesitant about char *, as mentioned below. consider std::string?

79

Is there some better name possible for what this "additional" info is? Something like, OptimizerClassifierInfo? (That is also not a great name, but I'd like to have something a little more descriptive)

82

SmallVector :)

lib/Transform/ScheduleOptimizer.cpp
1328

Consider something like containsStreamingAccess? I feel this reads better, when used with if:

if(checkForStreamingAccess(...))

versus

if(containsStreamingAccess(...))

check sounds more like a "command" / "imperative", while this function is more of a "predicate".

1330

consider using range-based for?

for (auto it : References)  { ... }
1335

consider adding desrciption for why this assert must hold:

assert (References.size() != 1 && "reason");
1359

I would prefer a more descriptive name, something like SinglePartialSchedule to emphasize that this code is pulling out a single isl::map from an isl::union_map

1364

consider range-based for?

for(auto it : SK) { ...}
1527
  1. Consider returning the Dom?
  2. Consider const MemoryAccess *MemAcc, since there seems to be no modification of the MemAcc?
`lang=cpp
static isl::set getDomain(MemoryAccess *MemAcc)
`

and assign Dom at the call site?

Dom = getDomain(...)
1577

Consider returning an SmallVector<bool> rather than passing a parameter to be initialized? That is, I would prefer the type signature being

static SmallVector<bool> getStep(MemoryAccess *MemAcc, isl::map &Sched)
1698

consider a more "predicate" sounding name, like doesAccessSingleElement.

Also, SmallVector, and maybe const isl::val?

static bool doesAccessSingleElement(std::vector<const isl::val> &E)
1715

Consider range-based-for loop

1759

This actually seems useful to have :) I am not sure what our policy is on keeping around debug printing functions, so ping @grosser @Meinersbur @philip.pfaffe and @pollydev

1820

Consider returning SmallVector<Reference>? It makes a function "pure" in my eyes, rather than having to mutate some external data.

Also, is it possible for the reference to ScopStmt to be const? From the name ("classify"), it should not need to modify anything in ScopStmt, correct?

So, consider:

static SmallVector<Reference, 4> classifyReference(const ScopStmt &Stmt)
1884

Consider constructing the Reference object first and finally calling push_back? This way, there is no need to track index.

That is,

 for (auto *MemA = Accesses.begin(); MemA != Accesses.end(); MemA++) {
    ...
    Reference  R;
    R.AccessType = MemAccessPtr->getType();
    R.Name = MemAccessPtr->getLatestScopArrayInfo()->getName();
R.Domain = getDomain(MemAccessPtr);
    ...
    References.push_back(R);
}
1893

consider const ScopStmt?

1934

Correct me if I am wrong, but the string obtained from Stmt.getBaseName() is owned by the ScopStmt correct? Here is the implementation which returns the char* owned by std::string ScopStmt::BaseName

So, I would prefer to make a copy into Skeleton, rather than hold a const char *.

Thanks for the patch! I've added some comments about general LLVM style, and some personal choices. Feel free to ignore the personal choices :)

  • I value const highly, but this is not true across LLVM and Polly.
  • Also, please run the file through ninja polly-update-format, It'll fix the formatting according to the formatting guidelines that are enforced using clang-format. I think in some places, the formatting is off?
bollu requested changes to this revision.Jun 17 2018, 3:12 AM

I'm going to request changes so this does not show up on the feed. I added two more comments regarding constructors :)

include/polly/ScheduleOptimizer.h
41

Does it make sense to initialize a Reference without a Name, Domain, or AccessType? I feel it makes sense to give it a constructor that initializes it, rather than creating an empty object and then initializing "by hand" as done in classifyReference

45

Similarly, can one have a Skeleton without a name? It may make sense to add a constructor and a method to add and get references, but not _remove_ them (IIRC, there is no removal of references, correct?)

In general, having access control would be nice!

This revision now requires changes to proceed.Jun 17 2018, 3:12 AM

I'm going to request changes so this does not show up on the feed. I added two more comments regarding constructors :)

Hi, @bollu thanks for the suggestions. I will come back to you soon.

Meinersbur added inline comments.Jun 18 2018, 9:33 AM
include/polly/ScheduleOptimizer.h
34–38

[Style] There is a coding Standard on how enum members should be named.

lib/Transform/ScheduleOptimizer.cpp
1337
1347–1353

[style] Please make the doxygen comments look like the ones we already have in Polly.

1382

[nit] /// is a doxygen comment, use // for normal comments.

1384

[style] DEBUG has been replaced recently by LLVM_DEBUG.

1759

See LLVM_DUMP_METHOD macro, e.g. used by ScopInfo::dump()

There are more in ISLTools.cpp: polly::dumpPw

chelini updated this revision to Diff 151925.Jun 19 2018, 8:41 AM
chelini marked 25 inline comments as done.
chelini marked 2 inline comments as done.Jun 19 2018, 8:48 AM
chelini added inline comments.
include/polly/ScheduleOptimizer.h
45

I added a bit of description for the Skeleton class. Each Skeleton contains the access pattern for a given Stmt.

45

Thanks for the comment. I am planning in the future to add more flexibility in the Skeleton class. For now I would like to keep it like this.

79

The structure was already there. I just used the struct to pass my Skeleton vector to the optimizer. Indeed I think the name is a bit too generic. I will think about possible alternatives.