[getUnderlyingOjbects] Analyze loop PHIs further to remove false positives
authorAdam Nemet <anemet@apple.com>
Thu, 23 Apr 2015 20:09:20 +0000 (20:09 +0000)
committerAdam Nemet <anemet@apple.com>
Thu, 23 Apr 2015 20:09:20 +0000 (20:09 +0000)
commite2b885c4bc58b56d2fb3d0e6b3dd8e932742cf73
tree1181e35b82cc9b4355e5a2c544ccfca8e6b622fb
parent2304b6ff44e620a73a730a702f8ec603e94a3e13
[getUnderlyingOjbects] Analyze loop PHIs further to remove false positives

Specifically, if a pointer accesses different underlying objects in each
iteration, don't look through the phi node defining the pointer.

The motivating case is the underlyling-objects-2.ll testcase.  Consider
the loop nest:

  int **A;
  for (i)
    for (j)
       A[i][j] = A[i-1][j] * B[j]

This loop is transformed by Load-PRE to stash away A[i] for the next
iteration of the outer loop:

  Curr = A[0];          // Prev_0
  for (i: 1..N) {
    Prev = Curr;        // Prev = PHI (Prev_0, Curr)
    Curr = A[i];
    for (j: 0..N)
       Curr[j] = Prev[j] * B[j]
  }

Since A[i] and A[i-1] are likely to be independent pointers,
getUnderlyingObjects should not assume that Curr and Prev share the same
underlying object in the inner loop.

If it did we would try to dependence-analyze Curr and Prev and the
analysis of the corresponding SCEVs would fail with non-constant
distance.

To fix this, the getUnderlyingObjects API is extended with an optional
LoopInfo parameter.  This is effectively what controls whether we want
the above behavior or the original.  Currently, I only changed to use
this approach for LoopAccessAnalysis.

The other testcase is to guard the opposite case where we do want to
look through the loop PHI.  If we step through an array by incrementing
a pointer, the underlying object is the incoming value of the phi as the
loop is entered.

Fixes rdar://problem/19566729

llvm-svn: 235634
llvm/include/llvm/Analysis/LoopAccessAnalysis.h
llvm/include/llvm/Analysis/ValueTracking.h
llvm/lib/Analysis/LoopAccessAnalysis.cpp
llvm/lib/Analysis/ValueTracking.cpp
llvm/test/Analysis/LoopAccessAnalysis/underlying-objects-1.ll [new file with mode: 0644]
llvm/test/Analysis/LoopAccessAnalysis/underlying-objects-2.ll [new file with mode: 0644]