<html>
<head>
<base href="http://llvm.org/bugs/" />
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW --- - Assert triggered by DependenceAnalysis"
href="http://llvm.org/bugs/show_bug.cgi?id=18082">18082</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Assert triggered by DependenceAnalysis
</td>
</tr>
<tr>
<th>Product</th>
<td>libraries
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>Linux
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>normal
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>Global Analyses
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>ssijaric@codeaurora.org
</td>
</tr>
<tr>
<th>CC</th>
<td>llvmbugs@cs.uiuc.edu
</td>
</tr>
<tr>
<th>Classification</th>
<td>Unclassified
</td>
</tr></table>
<p>
<div>
<pre>Created <span class=""><a href="attachment.cgi?id=11622" name="attach_11622" title="Test case">attachment 11622</a> <a href="attachment.cgi?id=11622&action=edit" title="Test case">[details]</a></span>
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.</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>