[llvm-dev] [RFC] Refinement of convergent semantics

[Mehdi Amini via llvm-dev]

> On Sep 22, 2015, at 2:36 PM, Owen Anderson via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> 
>> On Sep 22, 2015, at 2:02 PM, Jingyue Wu <jingyue at google.com <mailto:jingyue at google.com>> wrote:
>> 
>> Is LLVM allowed to unroll
>> 
>> for (int i = 0; i < 4; ++i) {
>>   if (i < c) // c is loop invariant
>>     convergent();
>> }
>> 
>> to
>> 
>> if (0 < c)
>>   convergent();
>> if (1 < c)
>>   convergent();
>> if (2 < c)
>>   convergent();
>> if (3 < c)
>>   convergent();
>> 
>> ?
>> 
>> Is "0 < c" considered "an additional value"? I'd vote no, but one can argue the other way. 
> 
> My intuition agrees with you here, but I don’t know how to formalize it.
> 

Introducing intermediate steps in the transformation? If the first transformation is valid, it seems trivial to get the end one:

for (int i = 0; i < 1; ++i) {
  if (i < c) // c is loop invariant
    convergent();
}
for (int i = 1; i < 2; ++i) {
  if (i < c) // c is loop invariant
    convergent();
}
for (int i = 2; i < 3; ++i) {
  if (i < c) // c is loop invariant
    convergent();
}
for (int i = 3; i < 4; ++i) {
  if (i < c) // c is loop invariant
    convergent();
}

— 
Mehdi



>> One approach (Bjarke's idea) to work around such ambiguities is to define: a program is convergent-correct if everything marked convergent are indeed convergent. Then a transformation is convergent-correct unless it transforms a convergent-correct program to a convergent-incorrect one. However, defining "convergent-correct" involves SIMT concepts which you want to avoid here. 
> 
> There are situations where this is over-conservative as well.  Some convergent operations do not require uniformity per se.  For example, a gradient operation in graphics programming models requires that all four threads in a given quad are either all executing or all not executing, though a warp is generally larger than that.  Restricting convergent code motion to only be between uniform control flow points in the program would penalize that use case.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150923/3573b634/attachment.html>