llvm dev - Sep 2016 - Data-dependent cycles in IR without cycles in source?

Hi,

I'm attempting to understand why in the following C++ code LLVM produes
cycles in the IR (for `cycle1` and `cycle2`, that do not have
data-dependent cycles), but `nocycle` is not. In the first two cases,
`Count` has an undefined value when `Count + 1` is evaluated and the value
is scoped to the body of the loop so can't (or shouldn't) hold values
from
one iteration to the next, but in `clang++ -std=c++11 sample.cpp -S
-emit-llvm -OX -o sample.ll` where X = any of 0,1,2,3,s,z, a data-dependent
cycle is created - like below:

%for.body:
  Count.012 = phi i32 [ undef, %entry ], [ %cond.i, %for.body ]
  %add = add nsw i32 %Count.012, 1
  %cond.i = select i1 %call, i32 %0, i32 %add

Thanks,
Matt

int select(bool P, int True, int False) { return P ? True : False; }

bool random(void);

void cycle1(int (&Input)[100], int (&Output)[100]) {
  for (int I = 0, N = 100; I < N; ++I) {
    int Count;

    Count = select(random(), Input[I], Count + 1);

    Output[I] = Count;
  }
}

void cycle2(int (&Input)[100], int (&Output)[100]) {
  for (int I = 0, N = 100; I < N; ++I) {
    int Count = select(random(), Input[I], Count + 1);

    Output[I] = Count;
  }
}

void nocycle1(int (&Input)[100], int (&Output)[100]) {
  for (int I = 0, N = 100; I < N; ++I) {
    int Count = 0;

    Count = select(random(), Input[I], Count + 1);

    Output[I] = Count;
  }
}
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160927/c2713654/attachment.html>

On 9/27/2016 11:57 AM, Matthew O'Connor via llvm-dev
wrote:
> Hi,
>
> I'm attempting to understand why in the following C++ code LLVM 
> produes cycles in the IR (for `cycle1` and `cycle2`, that do not have 
> data-dependent cycles), but `nocycle` is not. In the first two cases, 
> `Count` has an undefined value when `Count + 1` is evaluated and the 
> value is scoped to the body of the loop so can't (or shouldn't)
hold
> values from one iteration to the next, but in `clang++ -std=c++11 
> sample.cpp -S -emit-llvm -OX -o sample.ll` where X = any of 
> 0,1,2,3,s,z, a data-dependent cycle is created - like below:
>
> %for.body:
>   Count.012 = phi i32 [ undef, %entry ], [ %cond.i, %for.body ]
>   %add = add nsw i32 %Count.012, 1
>   %cond.i = select i1 %call, i32 %0, i32 %add
>
> Thanks,
> Matt
>
> int select(bool P, int True, int False) { return P ? True : False; }
>
> bool random(void);
>
> void cycle1(int (&Input)[100], int (&Output)[100]) {
>   for (int I = 0, N = 100; I < N; ++I) {
>     int Count;
>
>     Count = select(random(), Input[I], Count + 1);
>
>     Output[I] = Count;
>   }
> }
It's a missed optimization; LLVM doesn't really work with scopes the way
you might expect.  If you turn off optimization and emit LLVM IR, you'll 
see that memory for "Count" is allocated with the "alloca"
instruction
in the entry block of the function.  When that gets converted to a 
register value, it's done in a way which isn't sensitive to the lifetime
of the variable, as marked with lifetime intrinsics.  See 
lib/Transforms/Utils/PromoteMemoryToRegister.cpp for the actual algorithm.

-Eli

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160927/99615b5d/attachment.html>

On 9/27/2016 1:57 PM, Matthew O'Connor via llvm-dev
wrote:
> In the first two cases, `Count` has an undefined value when `Count + 1`
> is evaluated and the value is scoped to the body of the loop so
So it's an undefined behavior. The compiler does _something_, but is not 
required do anything specific in such cases.

-Krzysztof

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation