Page MenuHomePhabricator

[Polly][WIP] Restore the initial ordering of dimensions before applying the pattern matching
ClosedPublic

Authored by gareevroman on Apr 5 2017, 11:57 PM.

Details

Summary

Dimensions of band nodes can be implicitly permuted by the algorithm applied during the schedule generation.

For example, in case of the following matrix-matrix multiplication,

for (i = 0; i < 1024; i++)

for (k = 0; k < 1024; k++)
  for (j = 0; j < 1024; j++)
    C[i][j] += A[i][k] * B[k][j];

it can produce the following schedule tree

domain: "{ Stmt_for_body6[i0, i1, i2] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= i2 <= 1023 }"
child:

schedule: "[{ Stmt_for_body6[i0, i1, i2] -> [(i0)] }, { Stmt_for_body6[i0, i1, i2] -> [(i1)] }, { Stmt_for_body6[i0, i1, i2] -> [(i2)] }]"
permutable: 1
coincident: [ 1, 1, 0 ]

The current implementation of the pattern matching optimizations relies on the initial ordering of dimensions. Otherwise, it can produce the miscompilation (e.g., [1]).

This patch helps to restore the initial ordering of dimensions by recreating the band node in case the corresponding conditions are satisfied.

Refs.:

[1] - https://bugs.llvm.org/show_bug.cgi?id=32500

Diff Detail

Repository
rL LLVM

Event Timeline

gareevroman created this revision.Apr 5 2017, 11:57 PM
gareevroman added inline comments.
lib/Transform/ScheduleOptimizer.cpp
1330 ↗(On Diff #94320)

The changes related to ScheduleTreeOptimizer::isMatrMultPattern help to ensure that the band node represents all the dimensions of the iteration domain. Otherwise, it's not safe to recreate the band node.

Meinersbur accepted this revision.Apr 6 2017, 8:13 AM
This revision is now accepted and ready to land.Apr 6 2017, 8:13 AM
This revision was automatically updated to reflect the committed changes.