This is an archive of the discontinued LLVM Phabricator instance.

[CodeMoverUtils] Add optional data dependence checks using Alias Analysis
Needs ReviewPublic

Authored by RithikSharma on Jul 25 2020, 11:53 AM.

Details

Summary

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

Diff Detail

Event Timeline

RithikSharma created this revision.Jul 25 2020, 11:53 AM
Whitney added inline comments.Jul 25 2020, 12:44 PM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
230

Please add a description for each isDependenceSafe(). And declare them as static.

231

SmallPtrSet<Instruction *, 10> -> SmallPtrSetImpl<Instruction *>

Same for the other isDependenceSafe().

258

check this at line 251.

if (AA.isNoAlias(MemLoc, DestMemLoc))
  return false;
llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
46

Does DataLayout DL(""); work?

RithikSharma marked 5 inline comments as done.
RithikSharma added inline comments.
llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
46

Thanks, yes it works.

Whitney added inline comments.Jul 26 2020, 2:45 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
230

Instructions -> instructions

236

return (DepResult && (DepResult->isOutput() || DepResult->isFlow() || DepResult->isAnti()));

258

check isNoAlias before querying getModRefInfo

269

using dependence info or alias analysis

RithikSharma marked an inline comment as done.
RithikSharma marked 4 inline comments as done.

Acknowledged, updated.

Whitney accepted this revision.Jul 26 2020, 3:20 AM
This revision is now accepted and ready to land.Jul 26 2020, 3:20 AM
bmahjour requested changes to this revision.Jul 27 2020, 7:48 AM
bmahjour added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
252

MemoryLocation::get returns "none" if Inst is a call. Please add special handling for calls and make sure your tests cover it.

260

The ref bit could be on for mod-ref cases. Please also check to make sure they are not mod.

This revision now requires changes to proceed.Jul 27 2020, 7:48 AM
RithikSharma marked an inline comment as done.Jul 28 2020, 7:24 AM
RithikSharma added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
252

Test case pending.

bmahjour added inline comments.Jul 28 2020, 2:32 PM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
264

Inst (from the list of instructions being checked) may also be a call.

bmahjour added inline comments.Jul 28 2020, 2:36 PM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
249

Not all aliasing implications are visible through the arguments. AAResults contains a number of overloads specifically designed to handle function calls. Did you look into using the following instead?

ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc);
ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call);
ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2);
fhahn added a comment.Jul 28 2020, 2:54 PM

Are there plans on moving some transforms to use this with AA? I think it would be good to have a concrete plan to make use of this, otherwise I am worried that the code will miss out on large real-world test coverage.

RithikSharma marked 2 inline comments as done.Jul 28 2020, 11:31 PM
RithikSharma marked an inline comment as not done.Jul 29 2020, 9:40 AM

Are there plans on moving some transforms to use this with AA? I think it would be good to have a concrete plan to make use of this, otherwise I am worried that the code will miss out on large real-world test coverage.

This was inspired from LICM, I'm trying to test this part by manually plugging this into LICM.

RithikSharma marked an inline comment as done.
hiraditya added inline comments.Aug 1 2020, 10:10 PM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
248

Any reason we have '10' instead of a value which is power of 2?

260

Once IsSafe is false. should we just return and avoid subsequent checks?

298

else is not needed,

375

comment needs update.

444

Are we planning to make use of AA here?

RithikSharma marked 4 inline comments as done.Aug 3 2020, 9:29 AM

Many thanks for you reviews @hiraditya , acknowledged and updated.

Whitney added inline comments.Aug 7 2020, 9:37 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
252

Is the test cases for call going to be added in this patch?

260

You don't need to variable IsSafe anymore, as you return false right away if IsSafe is false. And you can return true at the end of the function instead.

264

// This can be none for CallInst but this won't be used for CallInst

I don't understand this comment.

280

Is it safe to check this first if the memory locations are not None?
Something like...

auto DestMemLoc = MemoryLocation::get(Inst);
if (MemLoc.hasValue() && DestMemLoc.hasValue() &&  AA.isNoAlias(MemLoc, DestMemLoc))
    return false;

ModRefInfo Result = AA.getModRefInfo(Inst, MemLoc);
ModRefInfo DestResult = AA.getModRefInfo(&I, DestMemLoc);
if (CallBase *CBDest = dyn_cast<CallBase>(Inst)) {
  if (!MemLoc.hasValue())
    Result = DestResult = AA.getModRefInfo(&I, CBDest);
if (CallBase *CBSrc = dyn_cast<CallBase>(&I))
  if (!DestMemLoc.hasValue())
    DestResult = AA.getModRefInfo(Inst, CBSrc);
419–432

why remove isSafeToSpeculativelyExecute?

Whitney requested changes to this revision.Aug 7 2020, 9:39 AM
This revision now requires changes to proceed.Aug 7 2020, 9:39 AM
RithikSharma marked 4 inline comments as done.Aug 8 2020, 7:05 AM

Thanks for the reviews @Whitney , I have updated the patch with the changes.

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
252

Test cases are present in https://reviews.llvm.org/D84776

Whitney added inline comments.Aug 11 2020, 9:02 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
252

Can you move specifically the part that test call instructions here? And the test in D84776 doesn't have any call instructions with pointer operands, so this code is not tested.

280

I mean check isNoAlias first, before querying getModRefInfo.

bmahjour added inline comments.Aug 13 2020, 9:04 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
287

Two comments here:

  1. As I mentioned before, isRefSet may be true when isModSet is also true, so if you want to check for RAR you'd have to make sure that isModSet is false.
  2. Why do we need two results (Result and DestResult)? I'm not sure we need to query AA.getModRefInfo twice, once for each direction. Alias queries normally refer to a value in a symmetric bit matrix. Do you have a test where the result of AA.getModRefInfo is different depending on the order in which you pass the two memory location arguments?
RithikSharma marked 2 inline comments as done.Aug 15 2020, 3:57 AM

@Whitney thanks for the reviews, I have added the test case.

@bmahjour thanks for the reviews, I will update the patch soon.

RithikSharma marked 2 inline comments as done.Aug 18 2020, 10:53 AM
RithikSharma added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
287
  1. I have added checks for isModSet .
  2. We don't require two (Result and DestResult), I have checked the values of Result and DestResult, they are different.

I have made the required changes.

RithikSharma marked an inline comment as done.Aug 18 2020, 10:53 AM
bmahjour added inline comments.Aug 18 2020, 2:03 PM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
250

I think the call itself should also go into the MemLocs vector.

Whitney added inline comments.Sep 1 2020, 11:54 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
280

I am confused why cannot change to the code as suggested above.

This current code seems to have some code duplication.

292

This is no longer needed.

RithikSharma added inline comments.Sep 1 2020, 1:25 PM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
280

I'll verify that and look more what's missing, extra and not in sequence. I will update the patch with required changes asap.

292

Thanks, I'll include this in the next update.

RithikSharma marked 4 inline comments as done.
RithikSharma added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
250

CallInst returns none memory location, which won't be useful to find dependence info and we may have to skip it so I did not add it into the MemLocs in the first place.

RithikSharma marked an inline comment as done.Sep 4 2020, 8:34 AM
bmahjour added inline comments.Sep 8 2020, 7:04 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
250

Then we have a problem if the memory accesses of a function are not represented through their arguments. For example consider:

int a = 0;

void foo() {
  a = 1;
}

int main() {
  foo();
  a = 3;
  return a;
}

In the case above a = 3 should not be allowed to move before the call to foo().

If this information is not available through AliasAnalysis, then we have to check for it separately. One way to solve it is to look at the underlying object referenced by I and Inst, and if any of them is a global and one of the intervening instructions is a call that may have side-effect, then return false.

Whitney added inline comments.Sep 15 2020, 5:39 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
250

Please add this test case, and update the patch.

298

that's true, please remove the else.

Whitney resigned from this revision.Jun 25 2021, 6:49 AM