[LAA] Add Memory dependence remarks.

[malharJ]

Summary

Adds new optimization remarks when vectorization fails.

More specifically, new remarks are added for following 4 cases:

• Backward dependency
• Backward dependency that prevents Store-to-load forwarding
• Forward dependency that prevents Store-to-load forwarding
• Unknown dependency

It is important to note that only one of the sources
of failures (to vectorize) is reported by the remarks.
This source of failure may not be first in program order.

A regression test has been added to test the following cases:

a) Loop can be vectorized: No optimization remark is emitted
b) Loop can not be vectorized: In this case an optimization
remark will be emitted for one source of failure.

[sdesmalen]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1762

Can there only be a single unsafe/unknown dependence? Or can there be more?

2114

unnecessary change.

2140

These changes here obfuscate the report that's generated by LAA when running loop(print-access-info). The information printed was:

Loop access info in function 'store_with_pointer_phi_incoming_phi':
  loop.header:
 The compiler can't determine the cause of the issue.
    Dependences:
      Unknown:
          %v8 = load double, double* %arrayidx, align 8 ->
          store double %mul16, double* %ptr.2, align 8

The information that is added by the remark is:

Loop access info in function 'store_with_pointer_phi_incoming_phi':
  loop.header:
    Report: unsafe dependent memory operations in loop. Use #pragma loop distribute(enable) to allow loop distribution to attempt to isolate the offending operations into a separate loop
Unknown data dependence. Memory location is the same as accessed at <UNKNOWN LOCATION>. 
 The compiler can't determine the cause of the issue.
    Dependences:
      Unknown:
          %v8 = load double, double* %arrayidx, align 8 ->  
          store double %mul16, double* %ptr.2, align 8

The extra information here isn't particularly useful, especially because it doesn't have any line information. Perhaps the code should disable the extra info if the location is unknown/unavailable.

2142

nit: Please remove the newline.

2142

Instead of using + to concatenate two strings, let this be handled by raw_ostream using << .

llvm/test/Analysis/LoopAccessAnalysis/stride-access-dependence.ll

121

Please CHECK-NEXT for the full line that is printed.

[malharJ]

• Rebased patch onto main
• Updated code to avoid printing <unknown> when no debug info is present
• minor formatting updates

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

618

thanks for pointing it out. Removed it.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1762

There can be more.

But we are only emitting (as a remark) the first one found.

2083

Ok, I agree but there's an issue here ..

LoopAccessInfo::recordAnalysis() cant be called from within the function ( AccessAnalysis::canCheckPtrAtRT() ).
as it's not a member of AccessAnalysis class.

Perhaps one way to do it would be for AccessAnalysis::canCheckPtrAtRT() to accept a parameter
by reference and then we can use the value after the call as input to recordAnalysis() here.
But I'm afraid this approach is not much less verbose than current approach pf having UncomputablePtr as a member variable.

2140

Thanks for pointing this out. Done.

2142

can we keep this newline ?

The current text (Note: it was not introduced by this patch) is too long already:

unsafe dependent memory operations in loop. Use "#pragma loop distribute(enable) to allow loop distribution to attempt to isolate the offending operations into a separate loop

llvm/test/Analysis/LoopAccessAnalysis/stride-access-dependence.ll

121

Agreed.

But now the code will only print the remaining text: "Memory location is the same as ...etc"
when debug info is available.

so this is no longer an issue (since this test does not contain any debug info/metadata).

[malharJ]

ping,

[sdesmalen]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

587

UncomputablePtr doesn't really need a separate variable in AccessAnalysis, since it's only set by one function, and used directly by the function that calls it.

You can change canCheckPtrAtRT to take Value **UncomputablePtr = nullptr, and in canCheckPtrAtRT assign the value if the value is requested:

if (UncomputablePtr)
  *UncomputablePtr = Access.getPointer();

Where you call it, you can have:

Value *UncomputablePtr = nullptr;
bool CanDoRTIfNeeded =
    Accesses.canCheckPtrAtRT(*PtrRtChecking, PSE->getSE(), TheLoop,
                             SymbolicStrides, false, &UncomputablePtr);

if (!CanDoRTIfNeeded) {
  if (auto *I = dyn_cast_or_null<Instruction>(UncomputablePtr))
    recordAnalysis("UnknownArrayBounds", I)
}

Can you split this change out into a separate patch with a test that demonstrates the change?

1765

It shows here that the dependences are already collected. You can iterate Dependences to find the dependence that isn't safe, so that you don't have to add UnsafeDependence and maintain that separately.

1847

I guess this can be more briefly written as:

Loc = I->getDebugLoc();
if (auto *PtrI = dyn_cast_or_null<Instruction>(getPointerOperand(I)))
  Loc = PtrI->getDebugLoc();

(at which point it probably doesn't require a separate function anymore, especially since it has only one use).

1850–1852

This seems like a case that should be added to getPointerOperand ?

2084

It now passes in I as the instruction, but the debug location of the remark seems unchanged in the test. What value is this adding?

2085

Just leave the name as CantIdentifyArrayBounds ?

[RKSimon]

Sorry this is not an area I known enough about to review

[fhahn]

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

298

Does this need to be a shared_ptr? If you want to encode the fact that it may not be set, using Optional may be a better choice. Or you could initialize it to NoDep in case there is no unsafe dependence.

[malharJ]

• Moved the changes for testing unknown array bounds to new patch: D115873
• addressed review comments

[malharJ]

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

298

I've removed it now based on review comment by sdesmalen, so this is no longer an issue.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

587

Done, new patch: https://reviews.llvm.org/D115873

1765

Done.
That's a good point, thanks !

1847

I've removed this function and inlined the code since there is only one usage.

2084

This was essentially an issue in the original test,
The debug info (!35) used by the loop was incorrect.
I've changed it to use !32 now.

I have corrected the issue in my new patch:
https://reviews.llvm.org/D115873

[malharJ]

• rebased patch

Premerge îs failing due to (a possible bug introduced by) recent changes:
https://github.com/google/llvm-premerge-checks/pull/374

[malharJ]

• Updated unit test

[fhahn]

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

19

This change is unnecessary, keep the include in the .cpp

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2135

It seems like it would make things easier to read if the logic would be in a separate function, with proper documentation what it is supposed to do?

2137

nit: variable names here start with upper cases

2140

nit: dependence instead of dependency, to be in line with the terminology used elsewhere in the file?

2148

Is this true? Unless I miss something, this emits a remark for the first unsafe dependence?

llvm/test/Transforms/LoopVectorize/memory-dep-remarks.ll

2

For remarks, it might be good to check the full yaml generated, as in llvm/test/Transforms/LoopVectorize/X86/vectorization-remarks-missed.ll

17

nit: check here not needed?

20

nit: easier to read if this is the last block

122

Is this needed? Same for other tests.

127

is this needed?

265

can the debug lock be trimmed down a bit?

[malharJ]

• minor formatting updates
• moved remark emission code for unsafe mem dependences into a function
• got rid of some more debuginfo in the LIT test.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2148

you are correct, the comment is no longer correct. I've updated it now in the new function.

llvm/test/Transforms/LoopVectorize/memory-dep-remarks.ll

122

Can you please explain why this is not needed ?

127

thanks. removed it now. changed the type of %n from i32 to i64.

265

Done.

• Changed functions to use same parameters (and same ordering). This helped reduce !DISubroutineType metadata.

• Also reduced some !DILocation (that were not required) from test_forwardButPreventsForwarding_dep()

[malharJ]

• Added YAML to the LIT test

[malharJ]

ping.

[sdesmalen]

Hi @malharJ thanks for splitting up and simplifying this patch, this is an improvement. I left a few more comments, and also found that the remark itself needs a bit of work to separate it from the original message. Maybe you can also update the tests to check the full context, to ensure this no longer happens?

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2141

Can this be an assert?

2148

Can this be an assert?

2154

nit: please move this code below the switch

2158

This dyn_cast will cause a segfault if the value returned by getPointerOperand is a nullptr. This needs to be dyn_cast_or_null. It would be good to have a test for this case.

Also, there is no test for the MemSetInst either. Can you add one?

llvm/test/Transforms/LoopVectorize/memory-dep-remarks.ll

121

When I try this out with Clang, I see:

Use #pragma loop distribute(enable) to allow loop distribution to attempt to isolate the offending operations into a separate loopBackward loop carried data dependence

The issue here is the loopBackward (no period and space between remarks)

[malharJ]

• Rebased patch.
• Addressed review comments.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2141

I guess not ...

Looking at the definition of MemoryDepChecker::getDependences(),
it can return a nullptr if RecordDependences is false.
and that happens when number of dependences exceeds MaxDependences.
Given that max-dependences is a command line option, it could have any value.

2148

I dont think so ...

We will still need the check to see if we can find a dependency type that is unsafe for vectorization.

Just the presence of Deps is not sufficient to say above will be satisfied, because it can contain
Forward or Backwardvectorizable dependencies too (but we dont care about emitting any remark for them as they can be vectorized)

2158

Ok, I've changed it to dyn_cast_or_null (I think you had already mentioned it an earlier review comment but I missed it).
Can we please avoid adding more tests, from what I understand it may not be very crucial to test getPointerOperand()
as we just avoid emitting debug location information if it returns null pointer.

Also, I tried writing a test case for memset case and I found that it doesnt even make sense to have a case here for memset.
Apparently LAA does not consider any instruction that is not a load/store
I see this code in LoopAccessInfo::analyzeLoop()

if (!St) {
  recordAnalysis("CantVectorizeInstruction", St)
      << "instruction cannot be vectorized";
  HasComplexMemInst = true;
  continue;
}

So it looks like a different remark is emitted and an early exit is taken because memset is considered as a "complex" memory instruction.

considering the above, I have removed the memset part from the patch.

llvm/test/Transforms/LoopVectorize/memory-dep-remarks.ll

121

I'm not very clear on the issue here .. they are already printed on separate lines ?

Regardless I've updated the tests to print the entire message.
(The reason I was avoiding it earlier was because it was too long a message, and didn't appeal to me as part of the remark.
However, it was not added by my patch so I will not be changing it.)

[malharJ]

• minor update to commit message to trigger phabricator builds.

Update:
Build has failed but test failures are unrelated to this patch.

[sdesmalen]

LGTM with the nits addressed.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2141

nit: can be removed if you address my comment below.

2143–2151

nit:

if (!Deps || 
    llvm::find_if(Deps, [](const MemoryDepChecker::Dependence &D) { .. }) == Deps->end())
  return;

2185–2192

nit: this is more concisely written as:

if (Instruction *I = Dep.getSource(*this)) {
  DebugLoc SourceLoc = I->getDebugLoc();
  if (auto *DD = dyn_cast_or_null<Instruction>(getPointerOperand(I)))
    SourceLoc = DD->getDebugLoc();
  R << " Memory location is the same as accessed at "
    << ore::NV("Location", SourceLoc);
}