Page MenuHomePhabricator

[Delinearization] Delinearization of Array-of-Struct. Proof-of-Concept.
Needs ReviewPublic

Authored by Meinersbur on Sep 9 2021, 10:13 AM.

Details

Reviewers
bollu
Summary
struct  __attribute__((packed)) Pair { int x; long y; };
void foo(unsigned long N,  struct Pair A[][N]) {
  for (unsigned long i = 0; i < N; i+=1)
      A[i][i].y = 0;
}

lowered to

%0 = mul nsw i64 %i.0, %N
%arrayidx = getelementptr inbounds %struct.Pair, %struct.Pair* %A, i64 %0
%arrayidx1 = getelementptr inbounds %struct.Pair, %struct.Pair* %arrayidx, i64 %i.0
%y = getelementptr inbounds %struct.Pair, %struct.Pair* %arrayidx1, i64 0, i32 1

corresponding to the SCEVExpr

{4,+,(12 + (12 * %N))}<%for.cond>

delinearized to

ArrayDecl[UnknownSize][%N][12]
ArrayRef[{0,+,1}<%for.cond>][{0,+,1}<%for.cond>][4]

See test case array_of_struct.ll

Diff Detail

Event Timeline

Meinersbur created this revision.Sep 9 2021, 10:13 AM
Meinersbur requested review of this revision.Sep 9 2021, 10:13 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 9 2021, 10:13 AM
bmahjour added inline comments.
llvm/test/Analysis/Delinearization/array_of_struct.ll
2

Could we add the following as a motivating test case as well:

struct __attribute__((packed)) MyS {
  float a;
  double b;
  char c;
};

void foo(long long n, long long m, struct MyS f1[][n][m]) {
  for (int i = 0; i < 1024; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < m; k++)
        f1[i][j][k].b = f1[i-1][j][k].b;
}

The expected delinearization would produce the same subscripts in every dimension (including the added inner-most byte dimension) except for the outer-most dimension where the absolute difference between the subscripts should be 1.

nikic added a subscriber: nikic.Sep 10 2021, 2:08 AM
nikic added inline comments.
llvm/lib/Analysis/Delinearization.cpp
505

This isn't compatible with opaque pointers. The access size needs to be determine exclusively based on load/store element type (using GEP type is inappropriate for this as well, even if it won't outright crash).

Meinersbur added inline comments.Sep 10 2021, 12:30 PM
llvm/lib/Analysis/Delinearization.cpp
505

This is the fallback case, we could pass the actual load/store as another parameter instead, but wasn't necessary for this PoC.

The GEP type is/was useful information though, leaking some information of how data is accessed from the source code. However, in principle this information can also derived from recurrence in the SCEV. In the test case it is (12 + (12 * %N)), i.e. a multiple of 12, suggesting that to be the array element size.

llvm/test/Analysis/Delinearization/array_of_struct.ll
2

I will try to make this work.

Meinersbur edited the summary of this revision. (Show Details)
  • Multiple sources for element size: Access size, GEP, SCEV stride
  • Re-add gcd test case