[DependenceAnalysis] Extend unifySubscriptType for handling coupled subscript groups.

[vaivaswatha]

Summary

In continuation to an earlier commit to DependenceAnalysis.cpp by jingyue (r222100), the type for all subscripts in a coupled group need to be the same since constraints from one subscript may be propagated to another during testing. During testing, new SCEVs may be created and the operands for these need to be the same.
This patch extends unifySubscriptType() to work on lists of subscript pairs, ensuring a common extended type for all of them.

[jingyue]

lib/Analysis/DependenceAnalysis.cpp

3599

I may be missing something. Why not calling unifySubscriptType(Pairs[SJ]) here? Do we have to unify the subscript types across the entire group?

[vaivaswatha]

I may be missing something. Why not calling unifySubscriptType(Pairs[SJ]) here? Do we have to unify the subscript types across the entire group?

Thats right. All subscripts across the entire group need to have the same
type. This is because when testing coupled groups, the information obtained
by testing one subscript (constraints) may be propagated to another
subscript in the group. These constraints are used when testing the other
subscript, and at this point, different SCEVs may be created, all of which
need to have the same operand type.

So in short, its not just within a pair, but also across pairs in a coupled
group that the type must match. Hence the extension of unifySubscriptType().

[vaivaswatha]

Hi, a gentle reminder. Can anybody review this change?

Thanks.

[jingyue]

LGTM

[vaivaswatha]

In D9698#179757, @jingyue wrote:

LGTM

Hi Jingyue, can you commit this change? I don't have write access to the repo yet.

Regards,

[jingyue]

Done.

[vaivaswatha]

In D9698#181018, @jingyue wrote:

Done.

Thank you very much.

include/llvm/Analysis/DependenceAnalysis.h

 //    summarizing all.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H
 #define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H
 
 #include "llvm/ADT/SmallBitVector.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/Pass.h"
 
 namespace llvm {
   class AliasAnalysis;
   class Loop;
   class LoopInfo;
   class ScalarEvolution;
private:
     /// mapDstLoop - Given one of the loops containing the destination,
     /// return its level index in our numbering scheme.
     unsigned mapDstLoop(const Loop *DstLoop) const;
 
     /// isLoopInvariant - Returns true if Expression is loop invariant
     /// in LoopNest.
     bool isLoopInvariant(const SCEV *Expression, const Loop *LoopNest) const;
 
-    /// Makes sure both subscripts (i.e. Pair->Src and Pair->Dst) share the same
-    /// integer type by sign-extending one of them when necessary.
+    /// Makes sure all subscript pairs share the same integer type by 
+    /// sign-extending as necessary.
     /// Sign-extending a subscript is safe because getelementptr assumes the
-    /// array subscripts are signed.
-    void unifySubscriptType(Subscript *Pair);
+    /// array subscripts are signed. 
+    void unifySubscriptType(ArrayRef<Subscript *> Pairs);
 
     /// removeMatchingExtensions - Examines a subscript pair.
     /// If the source and destination are identically sign (or zero)
     /// extended, it strips off the extension in an effort to
     /// simplify the actual analysis.
     void removeMatchingExtensions(Subscript *Pair);
 
     /// collectCommonLoops - Finds the set of loops from the LoopNest that

lib/Analysis/DependenceAnalysis.cpp

void DependenceAnalysis::collectCommonLoops(const SCEV *Expression,
   while (LoopNest) {
     unsigned Level = LoopNest->getLoopDepth();
     if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest))
       Loops.set(Level);
     LoopNest = LoopNest->getParentLoop();
   }
 }
 
-void DependenceAnalysis::unifySubscriptType(Subscript *Pair) {
-  const SCEV *Src = Pair->Src;
-  const SCEV *Dst = Pair->Dst;
+void DependenceAnalysis::unifySubscriptType(ArrayRef<Subscript *> Pairs) {
+
+  unsigned widestWidthSeen = 0;
+  Type *widestType;
+
+  // Go through each pair and find the widest bit to which we need
+  // to extend all of them.
+  for (unsigned i = 0; i < Pairs.size(); i++) {
+    const SCEV *Src = Pairs[i]->Src;
+    const SCEV *Dst = Pairs[i]->Dst;
     IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
     IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
     if (SrcTy == nullptr || DstTy == nullptr) {
       assert(SrcTy == DstTy && "This function only unify integer types and "
-                             "expect Src and Dst share the same type "
-                             "otherwise.");
-    return;
+      continue;
+    }
+    if (SrcTy->getBitWidth() > widestWidthSeen) {
+      widestWidthSeen = SrcTy->getBitWidth();
+      widestType = SrcTy;
+    }
+    if (DstTy->getBitWidth() > widestWidthSeen) {
+      widestWidthSeen = DstTy->getBitWidth();
+      widestType = DstTy;
+    }
+  }
+
+
+  assert(widestWidthSeen > 0);
+
+  // Now extend each pair to the widest seen.
+  for (unsigned i = 0; i < Pairs.size(); i++) {
+    const SCEV *Src = Pairs[i]->Src;
+    const SCEV *Dst = Pairs[i]->Dst;
+    IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
+    IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
+    if (SrcTy == nullptr || DstTy == nullptr) {
+      assert(SrcTy == DstTy && "This function only unify integer types and "
+             "expect Src and Dst share the same type "
+             "otherwise.");
+      continue;
+    }
+    if (SrcTy->getBitWidth() < widestWidthSeen)
+      // Sign-extend Src to widestType
+      Pairs[i]->Src = SE->getSignExtendExpr(Src, widestType);
+    if (DstTy->getBitWidth() < widestWidthSeen) {
+      // Sign-extend Dst to widestType
+      Pairs[i]->Dst = SE->getSignExtendExpr(Dst, widestType);
     }
-  if (SrcTy->getBitWidth() > DstTy->getBitWidth()) {
-    // Sign-extend Dst to typeof(Src) if typeof(Src) is wider than typeof(Dst).
-    Pair->Dst = SE->getSignExtendExpr(Dst, SrcTy);
-  } else if (SrcTy->getBitWidth() < DstTy->getBitWidth()) {
-    // Sign-extend Src to typeof(Dst) if typeof(Dst) is wider than typeof(Src).
-    Pair->Src = SE->getSignExtendExpr(Src, DstTy);
   }
 }
 
 // removeMatchingExtensions - Examines a subscript pair.
 // If the source and destination are identically sign (or zero)
 // extended, it strips off the extension in an effect to simplify
 // the actual analysis.
 void DependenceAnalysis::removeMatchingExtensions(Subscript *Pair) {

 
 //===----------------------------------------------------------------------===//
 // Constraint manipulation for Delta test.
 
 // Given a linear SCEV,
 // return the coefficient (the step)
 // corresponding to the specified loop.
 // If there isn't one, return 0.
-// For example, given a*i + b*j + c*k, zeroing the coefficient
+// For example, given a*i + b*j + c*k, finding the coefficient
 // corresponding to the j loop would yield b.
 const SCEV *DependenceAnalysis::findCoefficient(const SCEV *Expr,
                                                 const Loop *TargetLoop)  const {
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
   if (!AddRec)
     return SE->getConstant(Expr->getType(), 0);
   if (AddRec->getLoop() == TargetLoop)
     return AddRec->getStepRecurrence(*SE);
if (Coupled.count()) {
     for (unsigned II = 0; II <= MaxLevels; ++II)
       Constraints[II].setAny(SE);
     for (int SI = Coupled.find_first(); SI >= 0; SI = Coupled.find_next(SI)) {
       DEBUG(dbgs() << "testing subscript group " << SI << " { ");
       SmallBitVector Group(Pair[SI].Group);
       SmallBitVector Sivs(Pairs);
       SmallBitVector Mivs(Pairs);
       SmallBitVector ConstrainedLevels(MaxLevels + 1);
+      SmallVector<Subscript *, 4> PairsInGroup;
       for (int SJ = Group.find_first(); SJ >= 0; SJ = Group.find_next(SJ)) {
         DEBUG(dbgs() << SJ << " ");
         if (Pair[SJ].Classification == Subscript::SIV)
           Sivs.set(SJ);
         else
           Mivs.set(SJ);
+        PairsInGroup.push_back(&Pair[SJ]);
       }
+      unifySubscriptType(PairsInGroup);
       DEBUG(dbgs() << "}\n");
       while (Sivs.any()) {
         bool Changed = false;
         for (int SJ = Sivs.find_first(); SJ >= 0; SJ = Sivs.find_next(SJ)) {
           DEBUG(dbgs() << "testing subscript " << SJ << ", SIV\n");
           // SJ is an SIV subscript that's part of the current coupled group
           unsigned Level;
           const SCEV *SplitIter = nullptr;

test/Analysis/DependenceAnalysis/NonCanonicalizedSubscript.ll

; DELIN: da analyze - none!
   store i32 %1, i32* %a.addr.2, align 4
   %i.inc = add nsw i64 %i, 1
   %exitcond = icmp ne i64 %i.inc, 100
   br i1 %exitcond, label %for.body, label %for.end
 
 for.end:
   ret void
 }
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+;  unsigned i, j;
+;  for (i = 1; i < SIZE; i++) {
+;    for (j = i; j < SIZE; j++) {
+;      a[i][j] = a[i+1][j-1] + 2;
+;    }
+;  }
+;  Extends the previous example to coupled MIV subscripts.
+
+
+@a = global [10004 x [10004 x i32]] zeroinitializer, align 16
+
+; Function Attrs: nounwind uwtable
+define void @coupled_miv_type_mismatch(i32 %n) #0 {
+; CHECK-LABEL: 'Dependence Analysis' for function 'coupled_miv_type_mismatch'
+; DELIN-LABEL: 'Dependence Analysis' for function 'coupled_miv_type_mismatch'
+entry:
+  br label %for.cond
+
+; CHECK: da analyze - input [0 *]!
+; CHECK: da analyze - anti [1 *]!
+; CHECK: da analyze - none!
+; DELIN: da analyze - input [0 *]!
+; DELIN: da analyze - anti [1 *]!
+; DELIN: da analyze - none!
+for.cond:                                         ; preds = %for.inc11, %entry
+  %indvars.iv11 = phi i64 [ %indvars.iv.next12, %for.inc11 ], [ 1, %entry ]
+  %exitcond14 = icmp ne i64 %indvars.iv11, 10000
+  br i1 %exitcond14, label %for.cond1.preheader, label %for.end13
+
+for.cond1.preheader:                              ; preds = %for.cond
+  %0 = trunc i64 %indvars.iv11 to i32
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.cond1.preheader, %for.body3
+  %indvars.iv8 = phi i64 [ %indvars.iv11, %for.cond1.preheader ], [ %indvars.iv.next9, %for.body3 ]
+  %j.0 = phi i32 [ %inc, %for.body3 ], [ %0, %for.cond1.preheader ]
+  %lftr.wideiv = trunc i64 %indvars.iv8 to i32
+  %exitcond = icmp ne i32 %lftr.wideiv, 10000
+  br i1 %exitcond, label %for.body3, label %for.inc11
+
+for.body3:                                        ; preds = %for.cond1
+  %sub = add nsw i32 %j.0, -1
+  %idxprom = zext i32 %sub to i64
+  %1 = add nuw nsw i64 %indvars.iv11, 1
+  %arrayidx5 = getelementptr inbounds [10004 x [10004 x i32]], [10004 x [10004 x i32]]* @a, i64 0, i64 %1, i64 %idxprom
+  %2 = load i32, i32* %arrayidx5, align 4
+  %add6 = add nsw i32 %2, 2
+  %arrayidx10 = getelementptr inbounds [10004 x [10004 x i32]], [10004 x [10004 x i32]]* @a, i64 0, i64 %indvars.iv11, i64 %indvars.iv8
+  store i32 %add6, i32* %arrayidx10, align 4
+  %indvars.iv.next9 = add nuw nsw i64 %indvars.iv8, 1
+  %inc = add nuw nsw i32 %j.0, 1
+  br label %for.cond1
+
+for.inc11:                                        ; preds = %for.cond1
+  %indvars.iv.next12 = add nuw nsw i64 %indvars.iv11, 1
+  br label %for.cond
+
+for.end13:                                        ; preds = %for.cond
+  ret void
+}
+
+attributes #0 = { nounwind uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 3.7.0 (https://[e-mail]/compilertree/amd_clang.git 93a05fb75ee3411d24e8b2b184fc766a5318403e) (https://[e-mail]/compilertree/amd_llvm.git 166d93d26efc912b517739f64d054a435e8e95cd)"}