Page MenuHomePhabricator

[DependenceAnalysis][PR56275] Normalize dependence analysis results to be non-negative when required
ClosedPublic

Authored by congzhe on Wed, Jul 20, 11:09 AM.

Details

Summary

This is the fix to PR56275 (https://github.com/llvm/llvm-project/issues/56275) which is a missed opportunity, where a perfrectly valid case for loop interchange failed interchange legality. More specifically, loop interchange does not interpret the direction vector correctly.

Regarding PR56275, this patch is the first of the two-patch series that resolve the problem: D130188, D130189

As we discussed on the PR page as well as in the loopopt meeting, the root problem is that the distance/direction vector produced by dependence analysis (DA) needs to be normalized (reversed), if the vector is negative. We've determined to provide helper functions in DA that does the normalization, and clients can ask DA to do normalization if needed.

In this patch I've added the helper functions isDirectionNegative() and normalize() such that DA results can get normalized if the direction is negative. Whether we call those function or not is based on a flag newly introduced, i.e., NeedsNormalization. Client passes (loop interchange for example) can set this flag to true (like the following) when they query DA, if they want DA results to be normalized. Please also refer to the follow-up loop interchange patch https://reviews.llvm.org/D130189 where DA is queried in loop interchange. It looks to me that this is the most clean way to do so, after experimenting with several alternatives.

DependenceInfo DI(&F, &AR.AA, &AR.SE, &AR.LI, /*NeedsNormalize=*/true);
// use DI anywhere in client passes.

I've also added an opt option -da-normalize-results such that we can run DA directly with NeedsNormalization being true, and update DA test cases to make sure of test coverage. The test cases added in Banerjee.ll shows that negative vectors are normalized with -da-normalize-results=true.

Diff Detail

Event Timeline

congzhe created this revision.Wed, Jul 20, 11:09 AM
Herald added a project: Restricted Project. · View Herald TranscriptWed, Jul 20, 11:09 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
congzhe requested review of this revision.Wed, Jul 20, 11:09 AM
Herald added a project: Restricted Project. · View Herald TranscriptWed, Jul 20, 11:09 AM
congzhe edited the summary of this revision. (Show Details)Wed, Jul 20, 11:47 AM
congzhe edited the summary of this revision. (Show Details)
congzhe added reviewers: kawashima-fj, bmahjour, Meinersbur, Restricted Project.
congzhe set the repository for this revision to rG LLVM Github Monorepo.
congzhe added a project: Restricted Project.

Thanks @congzhe . Though I'm not familiar with DA, it looks good to me. I'll leave the detailed review to the experts.

Since the normalize() function is conceptually an operation that applies to the result (as opposed to the analysis itself), it makes more sense for it to be a member of the Dependence class. Client code, such as loop interchange, would then do something like this:

if (auto D = DI->depends(Src, Dst, true).normalize()) {
   ...

This way the analysis can be done once, but the results can be interpreted differently if the need arises.

bmahjour added inline comments.Thu, Jul 21, 1:21 PM
llvm/include/llvm/Analysis/DependenceAnalysis.h
982

It would be good for the normalize() function to return a boolean indicating if it changed the result or not. This could come in handy, for example, when printing the results (please see my comment about the printer pass).

llvm/test/Analysis/DependenceAnalysis/Banerjee.ll
248

Since the printer pass (using dumpExampleDependence) prints the Src and Dst instructions in a fixed order, these results could easily be misinterpreted. To avoid confusion can we flag the results that have been normalized with a special marker? eg:

Src: store....
Dst: ...load
  da analyze - anti [< <]! **normalized**
Meinersbur added inline comments.Fri, Jul 22, 12:26 PM
llvm/lib/Analysis/DependenceAnalysis.cpp
4207–4209

The code falls into the final return false anyway, i.e. this condition is redundant.

You could also use a switch statement.

4229

Can we avoid bit-operations with magic constants? 0x01 is LT, 0x02 is EQ, 0x04 is GT. 0x07 is ALL.

4231

.Direction is a bitfield. The compiler already does the masking for you.

I think I would prefer the request for normalization on the depends() call, rather that the DependenceInfo constructor. This keeps it closer to the code that either expects normalized dependencies, or dependencies that expect it to correspond to which instructions were passed as either Src or Dst. Also, If DependenceInfo would be used as an analysis in a pass manager, having a NeedsNormalize=true instance of DependenceInfo in the analysis cache will break any pass that expect the other interpretation.

llvm/lib/Analysis/DependenceAnalysis.cpp
124–127

[serious] This flag breaks any code that expects non-normalized dependences.

Meinersbur added inline comments.Fri, Jul 22, 1:12 PM
llvm/lib/Analysis/DependenceAnalysis.cpp
124–127

An option for the print-da pass would be the better approach. Alternatively, if a dependency is normalized, also print the normalized dependence using a different output format. For instance:

da analyze - flow [> <>]!
da normalized - anti [< <>]!
congzhe updated this revision to Diff 447153.Sun, Jul 24, 4:07 PM

Since the normalize() function is conceptually an operation that applies to the result (as opposed to the analysis itself), it makes more sense for it to be a member of the Dependence class. Client code, such as loop interchange, would then do something like this:

if (auto D = DI->depends(Src, Dst, true).normalize()) {
   ...

This way the analysis can be done once, but the results can be interpreted differently if the need arises.

Thanks for the comment, I've updated the patch accordingly, i.e., make normalize() a member function of the Dependence/FullDependence class and hence it can be called as you suggested. Please refer to the loop interchange patch D130189 as well.

llvm/include/llvm/Analysis/DependenceAnalysis.h
982

Thanks for the comment, I understand your point. In fact the "normalization" process is implemented in two-parts - isDirectionNegative() and normalize(). What isDirectionNegative() returns is already a boolean (which is the funcationality you requested), and the client can know whether or not the depenedence vector is negative, and can further decide whether or not it wants to call normalize().

Please also refer to the most recent change in dumpExampleDependence() for the uses of isDirectionNegative() and normalize(). I thought about merging those two function into one, but I thought keep them as two segement functions can make it easier if clients merely want to check if the direction is negative but do not want to normalize the result.

llvm/lib/Analysis/DependenceAnalysis.cpp
124–127

Thanks a lot, considering both Bardia's and your comment, I've updated the patch such that the DependenceInfo constructor is not changed. Now the NormalizeResults option is only used in print-da pass. Also the output for the printer pass is also updated according to both of your comments.

4207–4209

Thanks, I've removed this redundant condition.

4229

Thanks for the comment. I've added more detailed source code comments to describe the funtionality here, please refer to the updated patch.

I'd like to mention that those 0x01, 0x02, 0x04 are not directly related to LT/EQ/GT. They serve as the purpose of extracting the 1st, 2nd and 3rd bit (to the right), and then reversing the 1st and 3rd bits. This inherently reverses the direction vector, however complex it is, e.g., banerjee6() in the test file banerjee.ll.

4231

Thanks, updated accordingly.

llvm/test/Analysis/DependenceAnalysis/Banerjee.ll
248

Thanks, I've done the change accordingly. Please also refer to the most recent NORMALIZE lines in tests.

bmahjour added inline comments.Mon, Jul 25, 9:47 AM
llvm/include/llvm/Analysis/DependenceAnalysis.h
982

Sure, but normalize() could still return a boolean indicating if it changed the Dependence object.

llvm/lib/Analysis/DependenceAnalysis.cpp
125

Suggestion:
NormalizeResults -> NormalizePrintedResults
da-normalize-results -> da-print-normalized-results

194

Suggestion for better readability: " normalized "

292

This function should call isDirectionNegative() to determine if reversing of the direction vector is necessary. If the direction is not negative, then it should not make any changes and return false. Otherwise proceed and return true.

congzhe updated this revision to Diff 447404.EditedMon, Jul 25, 10:41 AM

Thanks @bmahjour, I've tried to address all your comments in the updated version.

Meinersbur added inline comments.Mon, Jul 25, 1:53 PM
llvm/include/llvm/Analysis/DependenceAnalysis.h
254–255

Please also mention the case that a dependency object can represent a lexicographically forward and reversed dependency at the same time, as discussed in https://github.com/llvm/llvm-project/issues/56275#issuecomment-1183363002 and what the expected behaviour for this case is.

llvm/lib/Analysis/DependenceAnalysis.cpp
124–127

While cl::opt setting is acceptable, NPM explicitly have the possibility to parse pass options. Why not use it?

277

[style] avoid Almost-Always-Auto

288

[serious] This should return a new FullDependence object. Modifying the existing object will also modify the object in the pass manager's analysis cache and potentially break any code using it and not expect it to be normalized.

299

.Direction is a bitfield. The compiler already does the masking for you.

430

[nit] unrelated change

4229

LT/EQ/GT are directly related to those bits. Swapping the LT <=> GT flags directly corresponds to swapping the 1st and 3rd bit. If it did not, the bit swapping would not work either and one would need to map all 2^6 possibilities separately. Note that <> is possible as well: 0x5.

This is an alternative with less bit magic:

// reverse direction vector
// less flag becomes greater flag -- greater flag becomes less flag
unsigned char RevDirection = Direction & Dependence::DVEntry::EQ;
if (Direction & Dependence::DVEntry::LT)
    RevDirection |= Dependence::DVEntry::GT;
if (Direction & Dependence::DVEntry::GT)
    RevDirection |= Dependence::DVEntry::LT;
congzhe updated this revision to Diff 447782.Tue, Jul 26, 11:46 AM
congzhe added inline comments.
llvm/include/llvm/Analysis/DependenceAnalysis.h
254–255

Thanks, I've added the corresponding description in the comment of isDirectionNegative() in DependenceAnalysis.cpp.

llvm/lib/Analysis/DependenceAnalysis.cpp
124–127

Thanks for this -- I'm not very clear of this functionality, I'm wondering if you could point me to some references?

277

Thanks, updated accordingly.

288

Thanks, I've updated to make normalize() return a new FullDependence object (although copy constructor of FullDependence is not allowed), please refer to the most recent update.

4229

Thanks a lot for the suggestion, I've updated the code as per your suggestion.

bmahjour added inline comments.Wed, Jul 27, 6:51 AM
llvm/lib/Analysis/DependenceAnalysis.cpp
288

No Dependence object is being cached anywhere. A new object is constructed every time DependenceInfo::depends() gets called.

congzhe updated this revision to Diff 448719.Fri, Jul 29, 2:48 PM

Hi @bmahjour @Meinersbur, I've updated the patch such that normalize() changes the Dependence object in place, and I've also leveraged the capability of the NPM to parse pass options instead of using cl::opt. I'd appreciate it if you could take a look at this version, thanks a lot!

Meinersbur accepted this revision.Tue, Aug 2, 12:08 PM

LGTM, but with a renaming suggestion.

llvm/lib/Passes/PassBuilder.cpp
854

I think the da-print- prefix is unnecessary since this is parsed for print<da> pass only.

This revision is now accepted and ready to land.Tue, Aug 2, 12:08 PM
bmahjour accepted this revision.Wed, Aug 3, 7:07 AM
congzhe updated this revision to Diff 449824.Wed, Aug 3, 4:24 PM

Addressed comments, will land soon.