On 27/07/2014 08:12, Roman Gareev wrote:
Can you explain why you believe it is hard/impossible to generate a test
case without reduction?
I don't believe this. I only know that all the test cases considered
by me have the same problem.
Could you please explain what is 'reduction'? I've found out that,
according to the comment of the rewrite_reductions_out_of_ssa (this
function duplicates pbbs), the rewrite_reductions_out_of_ssa rewrite
out of SSA all the reduction phi nodes of SCOP. What are reduction phi
nodes? How are they related to 'reduction'?
A reduction is an operation that combines a set of elements into a
single element.
for (i = 0; i < 100; i++)
sum += i;
combines the different elements 'i' into the single element 'sum'.
Reductions where the combine operation *here '+') is associative and
commutative can be reordered. This means you can e.g. write the loop as
for (i = 99; i >= 0; i--)
sum += i;
and you get the same result. There are two ways to ensure something is
not optimized as a reduction
1) Destroy associativity/commutativity
Floating point operations are generally not associative/commutative,
except if -ffast-math is given to the compiler
2) Do not reduce into one element.
If we just assign to different elements of an array, there is no
possibility we have a reduction.
Let's get back to the earlier test case:
for (i = 0; i < n; i++) {
if (i <= m)
T: A[i] = i;
S: A[i + p] = j;
}
What is the ast generated for this one? I just created this input file
for isl_codegen:
[n,m] -> {S[i] -> [i]: 0<= i <= n;T[i] -> [i]: 0<= i <= m and i <= n}
[n,m] -> {:n,m > 1}
{}
$ isl_codegen < input.file
for (int c0 = 0; c0 <= n; c0 += 1) {
if (m >= c0)
T(c0);
S(c0);
}
Is something in graphite preventing us to generate this simple loop with
just one if-condition and no statement duplication?
Cheers,
Tobias
