This is an archive of the discontinued LLVM Phabricator instance.

[LoopInterchange] Add dominance check to guarantee output dependency order
Needs ReviewPublic

Authored by mdchen on Sep 17 2020, 9:09 PM.

Details

Reviewers
fhahn
efriedma
Summary

For a loop containing the following diamond structure:

   BB#1
  /    \
BB#2   BB#3
  \    /
   BB#4

If the BranchInst condition in BB#1 relates to the loop induction
variable, and BB#3 and BB#4 both have stores writing to the same
memory location. Then these stores may have implicit loop-carried
order which could be broken after interchanging.

Bugzilla: https://bugs.llvm.org/show_bug.cgi?id=47523

Diff Detail

Event Timeline

mdchen created this revision.Sep 17 2020, 9:09 PM
mdchen requested review of this revision.Sep 17 2020, 9:09 PM
fhahn requested changes to this revision.Sep 18 2020, 3:51 AM

Thanks for the patch! Could you also add a test case where src dominates dest?

llvm/test/Transforms/LoopInterchange/pr47523-implicit-out-dep-order.ll
3

does the test require any AArch64 specific cost modeling? Otherwise best to remove the triple, otherwise the test may fail when the AArch64 backend is not built.

52

could we just use 0 instead of %I as incoming values in the phi?

71

Is the condition here important? Could this instead just be an i1 that is a function argument?

74

could @g just be defined as i16 or the load/store be widened to i32, so we do not need the bit casts?

93

is !tbaa needed for any memory operations here?

94

This seems unneeded for the test. The test could just return %i3?

This revision now requires changes to proceed.Sep 18 2020, 3:51 AM
mdchen updated this revision to Diff 293093.Sep 21 2020, 1:27 AM
mdchen marked 6 inline comments as done.Sep 21 2020, 1:32 AM

@fhahn Thanks for the suggestions, please take another look.

fhahn added a comment.Nov 9 2020, 12:35 PM

Thanks for updating the patch! Some small remaining suggestions inline.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp
152

nit: conditions?

I think it would also good to mention why we currently are not actually checking if the condition is IV-dependent. Presumably because it's expensive to find?

154

nit: If there are no loads accessing the same memory location as the two output dependent stores.....

157

it might be worth adding a LLVM_DEBUG message here, because it might be surprising to have the change here.

fhahn added a comment.Nov 9 2020, 3:17 PM

Actually, could we get similar problems for dependencies other than output, eg if we have a conditional load that is later used?

Actually, could we get similar problems for dependencies other than output, eg if we have a conditional load that is later used?

Yes, there're similar cases our team have found related to data dependence that may prohibit interchange. And I'd like to spend more time to see if there's a sophisticated solution.