Page MenuHomePhabricator

[DA] Add an option to control delinearization validity checks
ClosedPublic

Authored by bmahjour on May 29 2019, 10:07 AM.

Details

Summary

Dependence Analysis performs static checks to confirm validity of delinearization. These checks often fail for 64-bit targets due to type conversions and integer wrapping that prevent simplification of the SCEV expressions. These checks would also fail at compile-time if the lower bound of the loops are compile-time unknown.

For example:

void foo(int n, int m, int a[][m]) {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
      a[i][j] = a[i+1][j-2];
    }
}

opt -mem2reg -instcombine -indvars -loop-simplify -loop-rotate -inline -pass-remarks=.* -debug-pass=Arguments  -da-permissive-validity-checks=false k3.ll -analyze -da

will produce the following by default:

da analyze - anti [* *|<]!

but will produce the following expected dependence vector if the validity checks are disabled:

da analyze - consistent anti [1 -2]!

This revision will introduce a debug option that will leave the validity checks in place by default, but allow them to be turned off. New tests are added for cases where it cannot be proven at compile-time that the individual subscripts stay in-bound with respect to a particular dimension of an array. These tests enable the option to provide user guarantee that the subscripts do not over/under-flow into other dimensions, thereby producing more accurate dependence vectors.

For prior discussion on this topic, leading to this change, please see the following thread: http://lists.llvm.org/pipermail/llvm-dev/2019-May/132372.html

Diff Detail

Repository
rL LLVM

Event Timeline

bmahjour created this revision.May 29 2019, 10:07 AM
fhahn added a subscriber: fhahn.May 29 2019, 5:56 PM
dmgreen accepted this revision.May 30 2019, 1:46 PM

As a debugging tool, this sounds fine. Not so sure about the tests, but I guess they are not hurting anyone :) And show good room for improvement.

Do you have any ideas how we might get the llvm form of them we have here (not the c form) to give good DA results without the miscompiles that the new option would produce? I was wondering if it was worth trying to get DA to return a dependency that is conditional on a set of predicates. Clients (we only have 3 at the moment) could treat predicated dependencies as "confused", or version the loop based on them.

This revision is now accepted and ready to land.May 30 2019, 1:46 PM
Meinersbur accepted this revision.May 30 2019, 2:14 PM

As a debugging tool, this sounds fine. Not so sure about the tests, but I guess they are not hurting anyone :) And show good room for improvement.

Do you have any ideas how we might get the llvm form of them we have here (not the c form) to give good DA results without the miscompiles that the new option would produce? I was wondering if it was worth trying to get DA to return a dependency that is conditional on a set of predicates. Clients (we only have 3 at the moment) could treat predicated dependencies as "confused", or version the loop based on them.

The tests are adding a bit more coverage. Of all the tests currently available only three tests in DADelin.ll are checking for loop nests with consistent, non-scalar loop carried dependencies and those are all using 32-bit addressing mode and none has a runtime loop lower-bound.

I'm not sure having the predicated dependencies will make them more usable in practice, since loop versioning is highly undesirable (due to code bloat and introduction of new branches) especially as the number of transformations that rely on dependence analysis increase in the loop optimization pipeline.

I would have liked to invert the option though. Most similar options are set up such that they allow to opt-out of the sound behavior.

I would have liked to invert the option though. Most similar options are set up such that they allow to opt-out of the sound behavior.

Are you saying you'd like the validity checks to be off by default? Unfortunately for the cases mentioned by Dave and Michael, the compiler would have to be pessimistic and do these validity checks otherwise incorrect transformations can take place. That's why this option leaves the checks intact by default.

I would have liked to invert the option though. Most similar options are set up such that they allow to opt-out of the sound behavior.

Are you saying you'd like the validity checks to be off by default? Unfortunately for the cases mentioned by Dave and Michael, the compiler would have to be pessimistic and do these validity checks otherwise incorrect transformations can take place. That's why this option leaves the checks intact by default.

I do want validity checks by default.

I thought about having the option to be called something like "da-delinearization-no-checks". It would be false by default and it would avoid the "=false" part you need now. Setting it would mean you get the unsound behavior.

Now I don't feel strongly about it. Go ahead with the current wording if you want.

fhahn added a comment.Jun 4 2019, 10:36 AM

I would have liked to invert the option though. Most similar options are set up such that they allow to opt-out of the sound behavior.

Are you saying you'd like the validity checks to be off by default? Unfortunately for the cases mentioned by Dave and Michael, the compiler would have to be pessimistic and do these validity checks otherwise incorrect transformations can take place. That's why this option leaves the checks intact by default.

I do want validity checks by default.

I thought about having the option to be called something like "da-delinearization-no-checks". It would be false by default and it would avoid the "=false" part you need now. Setting it would mean you get the unsound behavior.

I agree it would be better to have an option to actively disable the checks, rather than the other way around. ( personally I also think something like -da-disable-delinearization-checks would be a bit more descriptive). Also, I think it is worth calling out the unsoundness of setting the option in the description.

I would have liked to invert the option though. Most similar options are set up such that they allow to opt-out of the sound behavior.

Are you saying you'd like the validity checks to be off by default? Unfortunately for the cases mentioned by Dave and Michael, the compiler would have to be pessimistic and do these validity checks otherwise incorrect transformations can take place. That's why this option leaves the checks intact by default.

I do want validity checks by default.

I thought about having the option to be called something like "da-delinearization-no-checks". It would be false by default and it would avoid the "=false" part you need now. Setting it would mean you get the unsound behavior.

I agree it would be better to have an option to actively disable the checks, rather than the other way around. ( personally I also think something like -da-disable-delinearization-checks would be a bit more descriptive). Also, I think it is worth calling out the unsoundness of setting the option in the description.

+1

bmahjour updated this revision to Diff 202999.Jun 4 2019, 12:47 PM

Renamed the option to -da-disable-delinearization-checks and set the default value to "false". Updated LIT tests accordingly.

bmahjour updated this revision to Diff 203003.Jun 4 2019, 12:54 PM

formatting change to reduce the number of new lines in the options description.

This revision was automatically updated to reflect the committed changes.