This is an archive of the discontinued LLVM Phabricator instance.

[CodeMoverUtils] Add optional data dependence checks using MSSA
Needs ReviewPublic

Authored by RithikSharma on Jul 7 2020, 8:05 AM.

Details

Summary

isSafeToMoveBefore uses Dependence Info to check for flow/anti/output dependence, this patch adds alternative checks using MSSA.

Diff Detail

Event Timeline

RithikSharma created this revision.Jul 7 2020, 8:05 AM
Whitney added inline comments.Jul 7 2020, 10:25 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
221
return !std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
                 [&DI, &I](Instruction *CurInst) {
                   auto DepResult = DI.depends(&I, CurInst, true);
                   if (DepResult &&
                       (DepResult->isOutput() || DepResult->isFlow() ||
                        DepResult->isAnti()))
                     return true;
                   return false;
                 }));
236

Below is the cleaner version of your code:

MemoryUseOrDef *MemUseOrDef = MSSAU.getMemorySSA()->getMemoryAccess(&I);
if (isa<MemoryDef>(MemUseOrDef))
  return false;
return !std::any_of(InstsToCheck.begin(), InstsToCheck.end(), &MSSAU, &I](Instruction *CurInst) {
  MemoryUseOrDef *MemUseOrDef = MSSAU.getMemorySSA()->getMemoryAccess(CurInst);
  return isa<MemoryDef>(MemUseOrDef);
});

But this code is very restrictive. It can be improved by considering the relationship between I and CurInst, e.g. if they don't access the same memory then it should still be safe.

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
517–520

change all the existing ones to &DI, nullptr)) to make sure you are testing DI.

RithikSharma marked an inline comment as done.Jul 7 2020, 10:32 AM
RithikSharma added inline comments.
llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
517–520

Sure but even when we give preference to DI?

if (DI)
   return isDependenceSafe(I, *DI, InstsToCheck);
 else if (MSSAU)
   return isDependenceSafe(I, *MSSAU, InstsToCheck);
RithikSharma marked an inline comment as not done.Jul 7 2020, 10:49 AM
bmahjour added inline comments.Jul 7 2020, 11:17 AM
llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
586

Please also add a check to make sure independent memory load/stores can be moved passed each other. For example, %load2 should be able to move before the store to B.

store i32 %load1, i32* %arrayidx_B, align 4
%load2 = load i32, i32* %arrayidx_A, align 4
fhahn added a subscriber: fhahn.Jul 9 2020, 6:59 AM
fhahn added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
227

The if here doesn't add much I think. It would be simpler to just `return DepResult && DepResult->isOutput() || DepResult->isFlow() ||

DepResult->isAnti()`?
232

I don't think there is a reason to pass MemorySSAUpdater here, as you don't modify the IR. Just pass MemorySSA directly.

Also, please add a comment what the logic behind the checks is (same for the DI version)

244

What we are doing here is basically checking if 2 instructions may alias, right? Given that, the variable names seem a bit confusing. Also, the function returns true if either IsFlowOrOutput or IsAnti is true. Could you just return true directly?

368

Does it make sense to even call this function if either of those are not available, i.e. if all those required wouldn't it make sense to assert that they are all provided or turn them into references?

Whitney added inline comments.Jul 9 2020, 7:39 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
221
  1. !any_of can change to none_of
  2. use llvm::none_of instead of std::none_of
return none_of(InstsToCheck, [&DI, &I]
...
249

DestMemUseOrDef is of type MemoryUseOrDef, so it must be a MemoryUse of MemoryDef.

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
517–520

Yes, because the code may change.

586

Good idea. The test should include all four types of dependence, and all should be considered safe. Also make sure they are bidirectional, so check both move forward and move backward.

RithikSharma marked 3 inline comments as done.Jul 9 2020, 7:52 AM
RithikSharma added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
227

Thanks, yeah I should directly return it. I missed it in this diff as well. I'll update in the next diff.

232

Acknowledged and updated to MemorySSA instead of MemorySSAUpdater. Will add the required comments in the next diff.

368

I'm sorry, I didn't understand. We need at least DI or MSSA to find dependency.

fhahn added inline comments.Jul 9 2020, 9:02 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
368

I meant does it make sense to call this function without PDT == nullptr for example? It seems like it is kind of required here, right?

RithikSharma marked an inline comment as done.Jul 9 2020, 10:01 AM
RithikSharma added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
368

Got it, why is PDT not a reference if it is required, right? Most code motion clients example LICM don't have PDT so until we find a way to prove control flow equivalence with some other analysis we need to keep the !PDT check but we did changed PDT into pointer as we will be expecting nullptr in near future.

RithikSharma marked 2 inline comments as done.Jul 16 2020, 3:22 AM
RithikSharma added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
221

Acknowledged, updated with changes.

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
517–520

Thanks, Acknowledged.

bmahjour added inline comments.Jul 17 2020, 9:28 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
259

I don't understand why we need this part: || InstLastDefMA == CurInstDefMA. Wouldn't it suffice to check the reaching def of the use against the instruction being moved (the first part of this condition) ? Do you have a test that would fail if you remove it?

264

Do we really need InstDefMA == CurInstLastDefMA ||? See my comment above.

Whitney added inline comments.Jul 18 2020, 4:10 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
264

This is needed for cases like

store 1, ptr
x = load ptr
store 0, ptr

check if x is safe to move after store 0, ptr.
e.g. in https://reviews.llvm.org/D83543

// Anti forward dependency
EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, *StoreB1, DT, &PDT, &DI));

the defining access of x is store 1, ptr, the getClobberingMemoryAccess of store 0, ptr is x.
Not sure if this works if there is no store before the memory use.
I wonder if there is a better to do this, like if there is a way to directly get x from store 0, ptr.

RithikSharma marked 6 inline comments as done.Jul 18 2020, 7:09 AM
RithikSharma added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
259

Yes we have a failure if we remove this,

isSafeToMoveBefore(*StoreA2, *LoadA1, DT, &PDT, nullptr, &MSSA)
bmahjour added inline comments.Jul 20 2020, 10:21 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
264

That still won't work if the first store is after the load or is absent all together. I don't think there is a way to get x from store 0, ptr because there is no def-use relationship between them. This highlights the need to use Alias Analysis instead or in combination with MSSA. I see that current LICM has similar issues, for example see comment in pointerInvalidatedByLoopWithMSSA().

I suppose improvements can be made in steps. Currently LICM uses an over-approximation to deal with this situation by looking for any definitions that are locally dominated by the sinking use. Perhaps we can start with that and gradually add aliasing queries into the equation.

bmahjour added inline comments.Jul 20 2020, 10:36 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
255

We also need to check for InstLastDefMA == CurInstLastDefMA in case both definitions are clobbered by the same memory phi.

This can be closed in favor of https://reviews.llvm.org/D84589. Please migrate the tests and close the review. Thanks.