Handling store to invariant address in LAA

[ashutosh.nema]

Summary

This change is for handling of “store to invariant address” in ‘LoopAccessAnalysis’(LAA).
While analyzing loop, LAA sets ‘CanVecMem’ to false when store to invariant address appears.

928 void LoopAccessInfo::analyzeLoop(const ValueToValueMap &Strides) {
1029 if (isUniform(Ptr)) {
1030 emitAnalysis(
1031 LoopAccessReport(ST)
1032 << "write to a loop invariant address could not be vectorized");
1033 DEBUG(dbgs() << "LAA: We don't allow storing to uniform addresses\n");
1034 CanVecMem = false;
1035 return;
1036 }

This check was specific to optimizations.

We like to add a flexibility here, by letting optimizations to decide on “store to invariant address”.
Some optimizations may not be interested in “store to invariant address” and few optimization will be interested.

For the same as Adam suggested, made following change:

1. Added variable ‘StoreToLoopInvariantAddress’ in ‘LoopAccessInfo’ class.
2. Provided a getter function ‘hasStoreToLoopInvariantAddress’ for ‘StoreToLoopInvariantAddress’.
3. Updating this variable in ‘LoopAccessInfo::analyzeLoop’ for store to invariant addresses.
4. In vectorization legality ‘LoopVectorizationLegality::canVectorizeMemory’ checking this variable and returning false in case of store to invariant addresses.

Requesting to review this change.

[anemet]

Please update LAA::print to note if this variable is set and add a test with -analyze in tests/Analysis/LoopAccessAnalysis.

include/llvm/Analysis/LoopAccessAnalysis.h

432–433

it returns true, else returns false. ('s' at the end of return and one sentence or start new sentence with upper case)

475–477

Please initialize to false in the ctor.

lib/Transforms/Vectorize/LoopVectorize.cpp

4010–4012

I think that clang-format likes to indent these further, please check with clang-format-diff.py.

[ashutosh.nema]

Thanks for review Adam. I'll incorporate your comments.

[ashutosh.nema]

Thanks Adam for review.

I have incorporated your comments.

In addition to previous change, this revision contains following:

1. Updated hasStoreToLoopInvariantAddress comments.
2. Setting StoreToLoopInvariantAddress to false in constructor.
3. Corrected formatting.
4. Added test.

Regards,
Ashutosh

[anemet]

lib/Analysis/LoopAccessAnalysis.cpp

1310–1312

"was (not) found" or "has (not) been found"

test/Analysis/LoopAccessAnalysis/store-to-invariant-check1.ll

4

It's

35

I may be wrong but I think by default we use no alias analysis (-no-aa), so the tbaa annotations are unnecessary in these two test cases (including the metadata at the end of the files). I would remove them.

[ashutosh.nema]

Review comments incorporated.
Over previous changes it contains following:

1. Corrected comments.
2. Updated print message for invariant store.
3. Updated test by removing tbaa metadata.

[anemet]

LGTM.

I believe this change is fine because both run-time pointer checking and the dependence analysis are capable to deal with uniform addresses. I.e. it's really just an orthogonal property of the loop that the analysis provides.

Run-time pointer checking will only try to reason about SCEVAddRec pointers or else gives up. If the uniform pointer turns out the be a SCEVAddRec in an outer loop, the run-time checks generated will be correct (start and end bounds would be equal).

In case of the dependence analysis, we work again with SCEVs. When compared against a loop-dependent address of the same underlying object, the difference of the two SCEVs won't be constant. This will result in returning an Unknown dependence for the pair.

When compared against another uniform access, the difference would be constant and we should return the right type of dependence (forward/backward/etc).

[ashutosh.nema]

Thanks Adam for review.

I don’t have check-in rights, If possible can you make this check-in ?

Regards,
Ashutosh

[anemet]

Committed as r234361.

Also somehow you had a few trailing whitespaces. clang-format-diff.py should have been able to catch those, so you may want to double check your workflow.

[ashutosh.nema]

Thanks Adam :)

[anemet]

lib/Analysis/LoopAccessAnalysis.cpp

1037

Ashutosh,

I think this should be |= rather than =.

[ashutosh.nema]

Comment at: lib/Analysis/LoopAccessAnalysis.cpp:1037
@@ -1046,1 +1036,3 @@
+ // Check for store to loop invariant address.
+ StoreToLoopInvariantAddress = isUniform(Ptr);

// If we did *not* see this pointer before, insert it to  the read-write

---

Ashutosh,

I think this should be |= rather than =.

Yes, that’s the problem.
I'll fix this, and update you.

Did you reverted 234361 ?

Regards,
Ashutosh

[ashutosh.nema]

Over previous change, it contains following:

Fixed: PR23157
StoreToLoopInvariantAddress was not handled correctly and missing previous value.
Added new test case to handle similar scenario.

[anemet]

Looks good, will commit it tomorrow morning. Thanks.

[ashutosh.nema]

Thanks Adam.

[anemet]

New version landed in r234424.

[ashutosh.nema]

Thanks Adam.

include/llvm/Analysis/LoopAccessAnalysis.h

public:
   /// \brief Print the information about the memory accesses in the loop.
   void print(raw_ostream &OS, unsigned Depth = 0) const;
 
   /// \brief Used to ensure that if the analysis was run with speculating the
   /// value of symbolic strides, the client queries it with the same assumption.
   /// Only used in DEBUG build but we don't want NDEBUG-dependent ABI.
   unsigned NumSymbolicStrides;
 
+  /// \brief Checks existence of store to invariant address inside loop.
+  /// If the loop has any store to invariant address, then it returns true,
+  /// else returns false.
+  bool hasStoreToLoopInvariantAddress() const { 
+    return StoreToLoopInvariantAddress; 
+  }
+
 private:
   /// \brief Analyze the loop.  Substitute symbolic strides using Strides.
   void analyzeLoop(const ValueToValueMap &Strides);
 
   /// \brief Check if the structure of the loop allows it to be analyzed by this
   /// pass.
   bool canAnalyzeLoop();
 
private:
   unsigned NumLoads;
   unsigned NumStores;
 
   unsigned MaxSafeDepDistBytes;
 
   /// \brief Cache the result of analyzeLoop.
   bool CanVecMem;
 
+  /// \brief Indicator for storing to uniform addresses.
+  /// If a loop has write to a loop invariant address then it should be true.
+  bool StoreToLoopInvariantAddress;
+
   /// \brief The diagnostics report generated for the analysis.  E.g. why we
   /// couldn't analyze the loop.
   Optional<LoopAccessReport> Report;
 };
 
 Value *stripIntegerCast(Value *V);
 
 ///\brief Return the SCEV corresponding to a pointer with the symbolic stride

lib/Analysis/LoopAccessAnalysis.cpp

void LoopAccessInfo::analyzeLoop(const ValueToValueMap &Strides) {
   // list). This is okay, since we are going to check for conflicts between
   // writes and between reads and writes, but not between reads and reads.
   ValueSet Seen;
 
   ValueVector::iterator I, IE;
   for (I = Stores.begin(), IE = Stores.end(); I != IE; ++I) {
     StoreInst *ST = cast<StoreInst>(*I);
     Value* Ptr = ST->getPointerOperand();
-
-    if (isUniform(Ptr)) {
-      emitAnalysis(
-          LoopAccessReport(ST)
-          << "write to a loop invariant address could not be vectorized");
-      DEBUG(dbgs() << "LAA: We don't allow storing to uniform addresses\n");
-      CanVecMem = false;
-      return;
-    }
-
+    // Check for store to loop invariant address.
+    StoreToLoopInvariantAddress = isUniform(Ptr);
     // If we did *not* see this pointer before, insert it to  the read-write
     // list. At this phase it is only a 'write' list.
     if (Seen.insert(Ptr).second) {
       ++NumReadWrites;
 
       AliasAnalysis::Location Loc = AA->getLocation(ST);
       // The TBAA metadata could have a control dependency on the predication
       // condition, so we cannot rely on it when determining whether or not we

 
 LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
                                const DataLayout &DL,
                                const TargetLibraryInfo *TLI, AliasAnalysis *AA,
                                DominatorTree *DT,
                                const ValueToValueMap &Strides)
     : DepChecker(SE, L), NumComparisons(0), TheLoop(L), SE(SE), DL(DL),
       TLI(TLI), AA(AA), DT(DT), NumLoads(0), NumStores(0),
-      MaxSafeDepDistBytes(-1U), CanVecMem(false) {
+      MaxSafeDepDistBytes(-1U), CanVecMem(false), 
+      StoreToLoopInvariantAddress(false) {
   if (canAnalyzeLoop())
     analyzeLoop(Strides);
 }
 
 void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
   if (CanVecMem) {
     if (PtrRtCheck.empty())
       OS.indent(Depth) << "Memory dependences are safe\n";
     else
       OS.indent(Depth) << "Memory dependences are safe with run-time checks\n";
   }
 
+  OS.indent(Depth) << "Store to invariant address was " 
+                   << (StoreToLoopInvariantAddress ? "" : "not ")
+                   << "found in loop.\n";
+
   if (Report)
     OS.indent(Depth) << "Report: " << Report->str() << "\n";
 
   if (auto *InterestingDependences = DepChecker.getInterestingDependences()) {
     OS.indent(Depth) << "Interesting Dependences:\n";
     for (auto &Dep : *InterestingDependences) {
       Dep.print(OS, Depth + 2, DepChecker.getMemoryInstructions());
       OS << "\n";

lib/Transforms/Vectorize/LoopVectorize.cpp

 bool LoopVectorizationLegality::canVectorizeMemory() {
   LAI = &LAA->getInfo(TheLoop, Strides);
   auto &OptionalReport = LAI->getReport();
   if (OptionalReport)
     emitAnalysis(VectorizationReport(*OptionalReport));
   if (!LAI->canVectorizeMemory())
     return false;
 
+  if (LAI->hasStoreToLoopInvariantAddress()) {
+    emitAnalysis(
+        VectorizationReport()
+        << "write to a loop invariant address could not be vectorized");
+    DEBUG(dbgs() << "LV: We don't allow storing to uniform addresses\n");
+    return false;
+  }
+
   if (LAI->getNumRuntimePointerChecks() >
       VectorizerParams::RuntimeMemoryCheckThreshold) {
     emitAnalysis(VectorizationReport()
                  << LAI->getNumRuntimePointerChecks() << " exceeds limit of "
                  << VectorizerParams::RuntimeMemoryCheckThreshold
                  << " dependent memory operations checked at runtime");
     DEBUG(dbgs() << "LV: Too many memory checks needed.\n");
     return false;

test/Analysis/LoopAccessAnalysis/store-to-invariant-check1.ll

+; RUN: opt < %s -loop-accesses -analyze | FileCheck %s
+
+; Test to confirm LAA will find store to invariant address.
+; Inner loop has a store to invariant address.
+;
+;  for(; i < itr; i++) {
+;    for(; j < itr; j++) {
+;      var1[i] = var2[j] + var1[i];
+;    }
+;  }
+
+; CHECK: Store to invariant address was found in loop.
+; CHECK-NOT: Store to invariant address was not found in loop.
+
+define i32 @foo(i32* nocapture %var1, i32* nocapture readonly %var2, i32 %itr) #0 {
+entry:
+  %cmp20 = icmp eq i32 %itr, 0
+  br i1 %cmp20, label %for.end10, label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %entry, %for.inc8
+  %indvars.iv23 = phi i64 [ %indvars.iv.next24, %for.inc8 ], [ 0, %entry ]
+  %j.022 = phi i32 [ %j.1.lcssa, %for.inc8 ], [ 0, %entry ]
+  %cmp218 = icmp ult i32 %j.022, %itr
+  br i1 %cmp218, label %for.body3.lr.ph, label %for.inc8
+
+for.body3.lr.ph:                                  ; preds = %for.cond1.preheader
+  %arrayidx5 = getelementptr inbounds i32, i32* %var1, i64 %indvars.iv23
+  %0 = zext i32 %j.022 to i64
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body3, %for.body3.lr.ph
+  %indvars.iv = phi i64 [ %0, %for.body3.lr.ph ], [ %indvars.iv.next, %for.body3 ]
+  %arrayidx = getelementptr inbounds i32, i32* %var2, i64 %indvars.iv
+  %1 = load i32, i32* %arrayidx, align 4
+  %2 = load i32, i32* %arrayidx5, align 4
+  %add = add nsw i32 %2, %1
+  store i32 %add, i32* %arrayidx5, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %itr
+  br i1 %exitcond, label %for.inc8, label %for.body3
+
+for.inc8:                                         ; preds = %for.body3, %for.cond1.preheader
+  %j.1.lcssa = phi i32 [ %j.022, %for.cond1.preheader ], [ %itr, %for.body3 ]
+  %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
+  %lftr.wideiv25 = trunc i64 %indvars.iv.next24 to i32
+  %exitcond26 = icmp eq i32 %lftr.wideiv25, %itr
+  br i1 %exitcond26, label %for.end10, label %for.cond1.preheader
+
+for.end10:                                        ; preds = %for.inc8, %entry
+  ret i32 undef
+}
+

test/Analysis/LoopAccessAnalysis/store-to-invariant-check2.ll

+; RUN: opt < %s -loop-accesses -analyze  | FileCheck %s
+
+; Test to confirm LAA will not find store to invariant address.
+; Inner loop has no store to invariant address.
+;
+;  for(; i < itr; i++) {
+;    for(; j < itr; j++) {
+;      var2[j] = var2[j] + var1[i];
+;    }
+;  }
+
+; CHECK: Store to invariant address was not found in loop.
+; CHECK-NOT: Store to invariant address was found in loop.
+
+
+define i32 @foo(i32* nocapture readonly %var1, i32* nocapture %var2, i32 %itr) #0 {
+entry:
+  %cmp20 = icmp eq i32 %itr, 0
+  br i1 %cmp20, label %for.end10, label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %entry, %for.inc8
+  %indvars.iv23 = phi i64 [ %indvars.iv.next24, %for.inc8 ], [ 0, %entry ]
+  %j.022 = phi i32 [ %j.1.lcssa, %for.inc8 ], [ 0, %entry ]
+  %cmp218 = icmp ult i32 %j.022, %itr
+  br i1 %cmp218, label %for.body3.lr.ph, label %for.inc8
+
+for.body3.lr.ph:                                  ; preds = %for.cond1.preheader
+  %arrayidx5 = getelementptr inbounds i32, i32* %var1, i64 %indvars.iv23
+  %0 = zext i32 %j.022 to i64
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body3, %for.body3.lr.ph
+  %indvars.iv = phi i64 [ %0, %for.body3.lr.ph ], [ %indvars.iv.next, %for.body3 ]
+  %arrayidx = getelementptr inbounds i32, i32* %var2, i64 %indvars.iv
+  %1 = load i32, i32* %arrayidx, align 4
+  %2 = load i32, i32* %arrayidx5, align 4
+  %add = add nsw i32 %2, %1
+  store i32 %add, i32* %arrayidx, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %itr
+  br i1 %exitcond, label %for.inc8, label %for.body3
+
+for.inc8:                                         ; preds = %for.body3, %for.cond1.preheader
+  %j.1.lcssa = phi i32 [ %j.022, %for.cond1.preheader ], [ %itr, %for.body3 ]
+  %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
+  %lftr.wideiv25 = trunc i64 %indvars.iv.next24 to i32
+  %exitcond26 = icmp eq i32 %lftr.wideiv25, %itr
+  br i1 %exitcond26, label %for.end10, label %for.cond1.preheader
+
+for.end10:                                        ; preds = %for.inc8, %entry
+  ret i32 undef
+}
+