[LLVMbugs] [Bug 18082] New: Assert triggered by DependenceAnalysis

Wed Nov 27 17:17:32 PST 2013

http://llvm.org/bugs/show_bug.cgi?id=18082

            Bug ID: 18082
           Summary: Assert triggered by DependenceAnalysis
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: Global Analyses
          Assignee: unassignedbugs at nondot.org
          Reporter: ssijaric at codeaurora.org
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

Created attachment 11622
  --> http://llvm.org/bugs/attachment.cgi?id=11622&action=edit
Test case

An assert occurs in an asserts enabled build when trying to propagate a
distance constraint derived from a SIV subscript pair of type i64 into a MIV
subscript pair of type i32.

The attached test case comes from the following:

a.c
unsigned a[10][10];

void
f(unsigned m, unsigned n)
{
  for (unsigned i = 0; i < m; ++i)
    for (unsigned j = 0; j < n; ++j)
      a[i][i+j] = 1;    
}

Running
1. clang --target=aarch64-linux-gnu -S a.c -emit-llvm -o a.ll
2. opt -instcombine -scalarrepl -S -o aa.ll a.ll

followed by

3. opt -analyze -basicaa -da aa.ll 

results in an assert:

ScalarEvolution.cpp:1874: const llvm::SCEV*
llvm::ScalarEvolution::getMulExpr(llvm::SmallVectorImpl<const llvm::SCEV*>&,
llvm::SCEV::NoWrapFlags): Assertion `getEffectiveSCEVType(Ops[i]->getType()) ==
ETy && "SCEVMulExpr operand types don't match!"' failed.
0  opt             0x0000000001879d20 llvm::sys::PrintStackTrace(_IO_FILE*) +
38
1  opt             0x0000000001879fa7
2  opt             0x00000000018798f5
3  libpthread.so.0 0x00007f5ab2324cb0
4  libc.so.6       0x00007f5ab134f425 gsignal + 53
5  libc.so.6       0x00007f5ab1352b8b abort + 379
6  libc.so.6       0x00007f5ab13480ee
7  libc.so.6       0x00007f5ab1348192
8  opt             0x0000000001559e43
llvm::ScalarEvolution::getMulExpr(llvm::SmallVectorImpl<llvm::SCEV const*>&,
llvm::SCEV::NoWrapFlags) + 397
9  opt             0x000000000123016d
10 opt             0x00000000014b2cae
llvm::DependenceAnalysis::propagateDistance(llvm::SCEV const*&, llvm::SCEV
const*&, llvm::DependenceAnalysis::Constraint&, bool&) + 240
11 opt             0x00000000014b2ac7
llvm::DependenceAnalysis::propagate(llvm::SCEV const*&, llvm::SCEV const*&,
llvm::SmallBitVector&,
llvm::SmallVectorImpl<llvm::DependenceAnalysis::Constraint>&, bool&) + 313
12 opt             0x00000000014b642c
llvm::DependenceAnalysis::depends(llvm::Instruction*, llvm::Instruction*, bool)
+ 8082
13 opt             0x00000000014a46ac
14 opt             0x00000000014a485f
llvm::DependenceAnalysis::print(llvm::raw_ostream&, llvm::Module const*) const
+ 47
15 opt             0x0000000000a2635f
16 opt             0x00000000017e52e2
llvm::FPPassManager::runOnFunction(llvm::Function&) + 390
17 opt             0x00000000017e54dd
llvm::FPPassManager::runOnModule(llvm::Module&) + 89
18 opt             0x00000000017e5884
19 opt             0x00000000017e5ed2
llvm::legacy::PassManagerImpl::run(llvm::Module&) + 254
20 opt             0x00000000017e60e5
llvm::legacy::PassManager::run(llvm::Module&) + 39
21 opt             0x0000000000a291d7 main + 5778
22 libc.so.6       0x00007f5ab133a76d __libc_start_main + 237
23 opt             0x0000000000a14209
Stack dump:
0.      Program arguments: opt -analyze -basicaa -da aa.ll 
1.      Running pass 'Function Pass Manager' on module 'aa.ll'.
2.      Running pass 'FunctionPass Printer: Dependence Analysis' on function
'@f'
Aborted

The following causes the assert to be triggered:

for.body3:                                        ; preds = %for.cond1
  %add = add i32 %storemerge, %storemerge1
  %idxprom = zext i32 %add to i64
  %idxprom4 = zext i32 %storemerge to i64
  %arrayidx5 = getelementptr inbounds [10 x [10 x i32]]* @a, i64 0, i64
%idxprom4, i64 %idxprom
  store i32 1, i32* %arrayidx5, align 4
  br label %for.inc

In this case, idxprom4 results in SCEV 1) {0,+,1}<nuw><nsw><%for.cond> with
type = i64 for both the source and destination, and %idxprom = zext i32 %add to
i64 results in SCEV 2) (zext i32 {{0,+,1}<nuw><%for.cond>,+,1}<%for.cond1> to
i64) with type = i64 for both the source and destination.

After removeMatchingExtensions on SCEV 2), we have
{{0,+,1}<nuw><%for.cond>,+,1}<%for.cond1> of type = i32.

The SCEVs are classified as

1) Source and destination SCEVs {0,+,1}<nuw><nsw><%for.cond> of type = i64. 
This is a strong SIV subscript pair with <src,dst> = <i,i> = <a*i_1 + c1,
a*i_1' + c2>, where a = 1, c1 = c2 = 0, i_1 = i_1' = i.

2) Source and destination SCEVs {{0,+,1}<nuw><%for.cond>,+,1}<%for.cond1> of
type = i32.  This is a MIV subscript pair with <src, dst> = <i+j,i+j> =
<a_1*i_1 + a_2*i_2 + e, a_1'*i_1' + a_2'*i_2' + e'>, where i_1 = i_1' = i, i_2
= i_2' = j, a_1 = 1 = a_1' = 1, a_2 = a_2' = 1, e = e' = 0.

where 1) and 2) are coupled.

The constraint generated by 1) is a distance constraint of 0 (due to the strong
SIV test, and since source and destination are identical).  It is of type i64,
since 1) is of type i64.  To propagate the distance constraint into the MIV
subscript pair 2), we need to form e = e - a_1*d = 0 - 1*0 = 0; a_1' = a_1' -
a_1 = 1 - 1 = 0; a_1 = 0 (Figure 5 in "Practical Dependence Testing" by Goff,
Kennedy, Tseng), to get the SIV subscript <a_2*i_2, a_2'*i_2'> == <j,j>.  The
assert is triggered by DependenceAnalysis::propagateDistance(...) when forming
the multiplication a_1*d.  The coefficient a_1 is retrieved from MIV 2), which
is of type i32, and so it is of type i32.  Due to the type mismatch, we get an
assert in getMulExpr.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20131128/52221a59/attachment.html>