[LLVMdev] SIV tests in LoopDependence Analysis, Sanjoy's patch

[Sanjoy Das]

Hi Preston,

Thanks for the feedback!

> In LoopDependenceAnalysis::AnalyzePair, what's going to happen if we > have something like this
>
> for (i = 0; i < n; i++)
>   for (j = 0; j < n; j++)
>     A[i][j]++;
>
> versus
>
> for (i = 0; i < n; i++)
>   for (j = 0; j < n; j++)
>     A[j][i]++;

I think this can be fixed by ordering the subscripts on the loop
nesting.  This should be doable, since the add recurrences remember
the loop whose induction variable they're representing.

Secondly, I think we can specialize on dealing only with linear add
recurrences and constants (symbolic or actual constants) at this
point.  Since LLVM represents indices like

for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
    a[i + j]++

as quite nicely as add recurrences of add recurrences we should be
able to get quite far along with this approach.

> And what's going to happen here?
>
> for (i = 0; i < n; i++)
>     A[i+1][i+2] = A[i][i];

I left out handling coupled subscripts at this point because ignoring
them only results in more conservative safer inferences about
dependence.  More sophisticated analysis like this can be added
incrementally, I think.

> And here?
>
> for (i = 0; i < n; i++)
>   for (j = 0; j < n; j++)
>     A[i] = A[i] + B[i][j];

I'm not too clear about this.  Assuming A and B point to two different
locations, there seems to be only one loop independent dependence --
from A[i] to A[i].

You are right about the ZIV issue, it needs to be fixed.

I think the following would be a good start at modelling dependencies
between two Values:

class Dependence {
public:
  struct Level {
    enum { LT  = 1, EQ  = 2, GT  = 4, ALL = 7 } direction;
    bool scalar;
    const SCEV *distance; // NULL implies no distance available
    const Loop *loop;
  };

  enum Kind { Flow, Anti, Output, Input };

  Kind getKind() const {
    return kind;
  }

  const Value *getSource() const {
    return source;
  }

  const Value *getDestination() const {
    return destination;
  }

  typedef SmallVector<const Level *, 4>::const_iterator const_iterator;
  const_iterator begin() const { return levels.begin(); }
  const_iterator end() const { return levels.end(); }

private:
  Value *source, *destination;
  Kind kind;
  SmallVector<const Level *, 4> levels;

  friend class LoopDependenceAnalysis;
};

More methods, like `isConsistent` and `isConfused` can be added easily
to this interface, since the raw data required to compute them is
available.

Given two Values, then, we can first break them up into their
respective indices.  We can then order them based on their loop
nesting.  To actually compute the dependence, we can traverse down the
subscript lists of the two Values and keep checking individual
subscript pairs.

I'm not sure on how to deal with cases such as these:

for (i = 0; i < n; i++) {
  for (j = 0; j < n; j++) {
    t = a[i][j];
    a[i + 1][j + 1] = t;
  }
  for (j = 0; j < n; j++) {
    t = a[i][j];
    a[i + 1][j + 1] = t;
  }
}

My gut feeling is that we should stop checking individual subscripts
when the loop nesting have diverged.  But don't know how to concretely
represent such dependencies.

I'm assuming in cases such as these:

for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
    a[i][0] = a[j][i]

we can have a dependence edge [S U | 0].

Let me know what you think!
-- 
Sanjoy Das.
http://playingwithpointers.com