Segfault/Memory corruption in DependenceAnalysis

[llvmbot]

Bugzilla Link	31848
Version	trunk
OS	Linux
Attachments	lit testcase triggering the bug
Reporter	LLVM Bugzilla Contributor

Extended Description

It's possible for DependenceAnalysis to run into a heap buffer overflow. The attached testcase triggers the bug for current trunk, but I'm positive this has been defective in previous versions as well.

The bug occurs within the banerjeeMIV-test, in the function collectCoeffInfo(). This function allocates a new array on the heap with MaxLevels+1 elements. MaxLevels is the maximum loop depth either of the two Instructions being tested are found in. This array is then filled by walking the AddRecExprs in the SCEV-Expr describing the access subscript. The problem with this is that the SCEV-Expr can contain AddRecExprs that do not correspond to loops surrounding the tested Instruction. And if those AddRecExprs belong to a loop that's deeper than MaxLevels, we're accessing the array outside of its bounds.

In summary, I don't think that this is really a problem with the banerjeeMIV-test, and I strongly suspect there are other inputs for which AddRecExprs are being treated as index variables even if they actually are not.

The fix for the memory corruption could be straightforward, by (correctly) classifying the subscript pair as NonLinear. However I am not sure whether this is overly pessimistic or even sound in general.

• Philip

[llvmbot]

Possible fix in https://reviews.llvm.org/D29488

[llvmbot]

*** Bug llvm/llvm-bugzilla-archive#33568 has been marked as a duplicate of this bug. ***

[llvmbot]

mentioned in issue llvm/llvm-bugzilla-archive#33568

[sebpop]

The testcase does not crash anymore on trunk today.
I will add the testcase to our suite of tests to make sure it continues to work.

I looked at the 2 proposed fixes so far.
Both patches weaken the check for subscript linearity: // Examine the scev and return true iff it's linear., and so both patches make no sense to me. See below some more details.

In https://reviews.llvm.org/D46197

Given code like:

for(i = ...)
 A[i] = 1;
A[i] = 2;

The scev for A[i]=2 is {A,+,4}, even though it is outside the loop. This

The SCEV {A,+,4}<for> for A[i]=2 looks very suspicious to me as it is "outside the loop", and it may be the cause of the bug. The SCEV for i outside the for loop should be equal to the end-of-loop value for i, say 42, which makes the dependence analysis to be a SIV test between A[i] = 1; in the loop and A[i] = 2; outside the loop, that is, {0,+,1}<for> vs. 42.

can confuse DA into thinking it is in the loop, leading to it using a SIV test,
and asserting.

In https://reviews.llvm.org/D29488

The SCEVAddRecExpr nest describing a Subscript may contain loops in which the corresponding memory access is not contained in.

If this is the case, it is an issue with the way the SCEV analysis instantiates end-of-loop values. A SCEV expression depends on the location in the code where it is taken, and it cannot contain references to loops that are not part of the enclosing loops.

[sebpop]

Fixed.