Page MenuHomePhabricator

[Polly] [WIP] Introduce ShapeInfo into polly.
AbandonedPublic

Authored by bollu on Jul 3 2018, 4:39 AM.

Details

Summary
  • Create a representation in Polly to disambiguate size based and stride based representations of arrays.
  • Need to move ScopDetection code to detect these strided arrays.
  • Need to move backend code (PPCGCodeGeneration) to this new representation.
  • I have never taught Codegen about strided arrays, so that is something we would need to do as well.

I am backporting code from my branch: https://github.com/bollu/polly/tree/feature.

The branch that I am working on is: https://github.com/bollu/polly/tree/jul-3-port-shapeinfo-to-master

@cs15btech11044, help appreciated in moving code. You can send my repo a pull request into the branch (jul-3-port-shapeinfo-to-master) that moves more code.

Event Timeline

bollu created this revision.Jul 3 2018, 4:39 AM
bollu edited the summary of this revision. (Show Details)Jul 3 2018, 4:41 AM
bollu added a reviewer: cs15btech11044.
bollu added a project: Restricted Project.
bollu added a subscriber: cs15btech11044.

Before going into the details and nits:

Why isn't ShapeInfo a sum type? If you're worried about this, since both summands would be structurally identical, you can even distinguish using a single tag to save you some implementation time.

bollu updated this revision to Diff 153921.Jul 3 2018, 8:42 AM
  • Backport code to detect chapel/fortran style indexing. TODO: Codegen.

There is code in IslExprBuilder which is responsible for actually
lowering the multidimensional index expression. This needs to be
backported. This will be the next commit.

I had to introduce a new kind of value map for this to work, a map
from const SCEV * -> Value *. I hugely dislike this design, and
would love to change this.

IMO, the ShapeInfo should ideally only have pw_aff, since we theoretically only
understand affine accesses. However, since we _do_ allow nonaffine indexing,
this does not work. We need some representation that is not as heavy as SCEV (?).

We need some point in the design space which is not so painful to work
with.

What is an array described by strides? What is it used for?

bollu updated this revision to Diff 153926.Jul 3 2018, 9:13 AM

Extract out codegen as well.

This is completely untested :D. I'll run the polly test suite to make
sure that nothing is immediately broken.

This gives no guarantee that the actual code path which we need will
work (the stride code path), but at least tells us that we have not
broken the default code path.

Now, we need to test the stride code path from the chapel source code. I
can also run it on my internal "test base", which I don't think I can
open source. I should be able to add small code snippets from it as I
find bugs for tests, though.

bollu added a comment.Jul 3 2018, 9:18 AM

@Meinersbur in polly, we use sizes per dimension, so the sizes data structure actually stores the size of a dimension. In the "stride" version, we rather store the "block size" of each dimension, which is akin to the Fortran representation, and the representation (if I understand the chapel representation correctly).

cs15btech11044 added inline comments.Jul 5 2018, 10:51 PM
lib/CodeGen/IslExprBuilder.cpp
326

[suggestion] Could you change the variable name Map to something more specific? This improves the readability of this code snippet.

@Meinersbur in polly, we use sizes per dimension, so the sizes data structure actually stores the size of a dimension. In the "stride" version, we rather store the "block size" of each dimension, which is akin to the Fortran representation, and the representation (if I understand the chapel representation correctly).

What is "block size"? How is to do with Fortran being column-major/1-indexed? How it an address computed using block sizes? How is non-aliasing ensured?

bollu abandoned this revision.Jul 8 2018, 3:17 AM

Abandoned in favour of D49024.