[llvm-dev] Data-dependent cycles in IR without cycles in source? (original) (raw)

Friedman, Eli via llvm-dev llvm-dev at lists.llvm.org
Tue Sep 27 12:20:16 PDT 2016

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>

More information about the llvm-dev mailing list