[DA] Improve dump to show source and sink of the dependence

[bmahjour]

Summary

The current da printer shows the dependence without indicating which instructions are being considered as the src vs dst. It also silently ignores call instructions, despite the fact that they create confused dependence edges to other memory instructions. This patch addresses these two issues plus a couple of minor non-functional improvements.

[fhahn]

llvm/lib/Analysis/DependenceAnalysis.cpp

198

Printing that last seems a bit odd to me. How about moving it up and have something like "da analyze - Src" << *SrcI << " --> Dst :" << *DstI?

llvm/test/Analysis/DependenceAnalysis/Dump.ll

20

Please check the complete output (should not be too much in the case) and it helps with getting the complete picture of the changed output.

[bmahjour]

Check the complete da print output in the LIT test as per Florian's comment.

llvm/lib/Analysis/DependenceAnalysis.cpp

198

I thought about putting it on the same line as "da analyze", but that would break every test case in da, and also makes the output a bit cluttered and hard to read (it would be hard to find the actual dependence info).

I could put it at the beginning and indent the "da analyze - " part. ie change the output from:

'Dependence Analysis' for function 'foo':
da analyze - none!
  Src:  store float %conv, float* %arrayidx, align 4 --> Dst:  store float %conv, float* %arrayidx, align 4
da analyze - confused!
  Src:  store float %conv, float* %arrayidx, align 4 --> Dst:  call void @bar(float* %A)
da analyze - confused!
  Src:  call void @bar(float* %A) --> Dst:  call void @bar(float* %A)

to

'Dependence Analysis' for function 'foo':
Src:  store float %conv, float* %arrayidx, align 4 --> Dst:  store float %conv, float* %arrayidx, align 4
  da analyze - none!
Src:  store float %conv, float* %arrayidx, align 4 --> Dst:  call void @bar(float* %A)
  da analyze - confused!
Src:  call void @bar(float* %A) --> Dst:  call void @bar(float* %A)
  da analyze - confused!

Do people prefer that?

[dmgreen]

Nice. I always found this a bit awkward.

llvm/lib/Analysis/DependenceAnalysis.cpp

198

I would say the second probably makes more sense for people unfamiliar with the output before. It shows what it is analysing, then the result it came up with.

[bmahjour]

Addressed review comments.

llvm/lib/Analysis/DependenceAnalysis.cpp

198

Sure. I've made it print the second way.

[dmgreen]

Thanks. Looks like an good improvement to me. I'm happy if @fhahn is happy.

[fhahn]

LGTM thanks! I agree that putting analyzed instructions before the result looks good!

[bmahjour]

Thank you @dmgreen and @fhahn for the quick review.

llvm/lib/Analysis/DependenceAnalysis.cpp

 
 void DependenceAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequiredTransitive<AAResultsWrapperPass>();
   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
   AU.addRequiredTransitive<LoopInfoWrapperPass>();
 }
 
-
 // Used to test the dependence analyzer.
-// Looks through the function, noting loads and stores.
+// Looks through the function, noting instructions that may access memory.
 // Calls depends() on every possible pair and prints out the result.
 // Ignores all other instructions.
 static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA) {
   auto *F = DA->getFunction();
   for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F); SrcI != SrcE;
        ++SrcI) {
-    if (isa<StoreInst>(*SrcI) || isa<LoadInst>(*SrcI)) {
+    if (SrcI->mayReadOrWriteMemory()) {
       for (inst_iterator DstI = SrcI, DstE = inst_end(F);
            DstI != DstE; ++DstI) {
-        if (isa<StoreInst>(*DstI) || isa<LoadInst>(*DstI)) {
+        if (DstI->mayReadOrWriteMemory()) {
           OS << "da analyze - ";
           if (auto D = DA->depends(&*SrcI, &*DstI, true)) {
             D->dump(OS);
             for (unsigned Level = 1; Level <= D->getLevels(); Level++) {
               if (D->isSplitable(Level)) {
                 OS << "da analyze - split level = " << Level;
                 OS << ", iteration = " << *DA->getSplitIteration(*D, Level);
                 OS << "!\n";
               }
             }
           }
           else
             OS << "none!\n";
+          OS << "  Src:" << *SrcI << " --> Dst:" << *DstI << "\n";
         }
       }
     }
   }
 }
 
 void DependenceAnalysisWrapperPass::print(raw_ostream &OS,
                                           const Module *) const {

 // Care is required to keep the routine below, getSplitIteration(),
 // up to date with respect to this routine.
 std::unique_ptr<Dependence>
 DependenceInfo::depends(Instruction *Src, Instruction *Dst,
                         bool PossiblyLoopIndependent) {
   if (Src == Dst)
     PossiblyLoopIndependent = false;
 
-  if ((!Src->mayReadFromMemory() && !Src->mayWriteToMemory()) ||
-      (!Dst->mayReadFromMemory() && !Dst->mayWriteToMemory()))
+  if (!(Src->mayReadOrWriteMemory() && Dst->mayReadOrWriteMemory()))
     // if both instructions don't reference memory, there's no dependence
     return nullptr;
 
   if (!isLoadOrStore(Src) || !isLoadOrStore(Dst)) {
     // can only analyze simple loads and stores, i.e., no calls, invokes, etc.
     LLVM_DEBUG(dbgs() << "can only handle simple loads and stores\n");
     return std::make_unique<Dependence>(Src, Dst);
   }
else {
     }
     if (AllEqual)
       return nullptr;
   }
 
   return std::make_unique<FullDependence>(std::move(Result));
 }
 
-
-
 //===----------------------------------------------------------------------===//
 // getSplitIteration -
 // Rather than spend rarely-used space recording the splitting iteration
 // during the Weak-Crossing SIV test, we re-compute it on demand.
 // The re-computation is basically a repeat of the entire dependence test,
 // though simplified since we know that the dependence exists.
 // It's tedious, since we must go through all propagations, etc.
 //

llvm/test/Analysis/DependenceAnalysis/Dump.ll

+; RUN: opt < %s -disable-output "-passes=print<da>" -aa-pipeline=basic-aa 2>&1 \
+; RUN: | FileCheck %s
+
+;; Test to make sure the dump shows the src and dst
+;; instructions (including call instructions).
+;;
+;; void bar(float * restrict A);
+;; void foo(float * restrict A, int n) {
+;;   for (int i = 0; i < n; i++) {
+;;     A[i] = i;
+;;     bar(A);
+;;   }
+;; }
+
+; CHECK-LABEL: foo
+
+; CHECK:da analyze - none!
+; CHECK-NEXT:  Src:  store float %conv, float* %arrayidx, align 4 --> Dst:  store float %conv, float* %arrayidx, align 4
+; CHECK-NEXT:da analyze - confused!
+; CHECK-NEXT:  Src:  store float %conv, float* %arrayidx, align 4 --> Dst:  call void @bar(float* %A)
+; CHECK-NEXT:da analyze - confused!
+; CHECK-NEXT:  Src:  call void @bar(float* %A) --> Dst:  call void @bar(float* %A)
+
+define void @foo(float* noalias %A, i32 signext %n) {
+entry:
+  %cmp1 = icmp slt i32 0, %n
+  br i1 %cmp1, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %i.02 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
+  %conv = sitofp i32 %i.02 to float
+  %idxprom = zext i32 %i.02 to i64
+  %arrayidx = getelementptr inbounds float, float* %A, i64 %idxprom
+  store float %conv, float* %arrayidx, align 4
+  call void @bar(float* %A) #3
+  %inc = add nuw nsw i32 %i.02, 1
+  %cmp = icmp slt i32 %inc, %n
+  br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
+  ret void
+}
+
+declare void @bar(float*)