[llvm-dev] Data-dependent cycles in IR without cycles in source?

[Friedman, Eli via llvm-dev]

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>