[LLVMdev] Inferring dependencies in phi instructions

[Anirudh Sivaraman]

On Mon, Jun 29, 2015 at 7:23 AM, John Criswell <jtcriswel at gmail.com> wrote:
> On 6/29/15 5:16 AM, Evgeny Astigeevich wrote:
>>
>> Hi Anirudh,
>>
>> 'x' has a control dependency on 'y' because the value assigned to 'x'
>> depends on a path selected. This dependency can be converted into a data
>> dependency by means of a 'select' instruction because the control flow is
>> simple.
>
>
> Just an FYI, there is an optimization called "If-Conversion" which
> transforms control dependencies to data dependencies; it is discussed in the
> Allen and Kennedy book ("Optimizing Compilers for Modern Architectures" in
> Chapter 6 or 7,  I think).
>

I tried this, but how do I express the resulting predicated
instructions in llvm's IR? For instance,

X = a + b

becomes

X = if (path_condition) (a + b)

I couldn't find an appropriate instruction type for predicated instructions.

> If you need to find control dependencies, you can find them easily using
> LLVM's ReverseDominanceFrontier pass.
>

Ok, I didn't know about this and implemented the cdg on my own.
However, regardless of how the cdg is implemented, I don't think it
captures control dependencies in phi instructions?

> Regards,
>
> John Criswell
>
>
>> What is the problem with using phi-functions in DFG? Yes they require more
>> work to find out what they depend on.
>>
>> Kind regards,
>> Evgeny Astigeevich
>>
>> -----Original Message-----
>> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On
>> Behalf Of Anirudh Sivaraman
>> Sent: 29 June 2015 07:25
>> To: LLVM Developers Mailing List
>> Subject: [LLVMdev] Inferring dependencies in phi instructions
>>
>> I am trying to infer data dependencies using LLVM's def-use chains and I
>> am
>> having trouble dealing with 'phi' instructions. Specifically,
>>
>> If I am given the code snippet:
>>
>> int foo() {
>>    int y = 1;
>>    int x;
>>    if (y) {
>>      x = 2;
>>    } else {
>>      x = 3;
>>    }
>>    return x;
>> }
>>
>> Here, x has a data dependence on y (not control because x is assigned in
>> both halves), but LLVM expresses 'x' as: %x.0 = phi i32 [ 2, %2 ], [ 3, %3
>> ]
>> using phi-nodes, omitting the dependence on y.
>>
>> If I write the function as:
>>
>> int foo() {
>>    int y = 1;
>>    int x = y ? 2 : 3;
>>    return x;
>> },
>>
>> the dependencies work out alright because LLVM now uses a select
>> instruction, where the dependence on y is explicit:
>>
>> %y = select i1 %x, i32 2, i32 3
>>
>> In general, I don't think I can convert phi nodes into select statements
>> (because a phi node can refer to values from more than two paths in
>> general,
>> while select statements permit only two options, one each for a true and a
>> false branch). Any thoughts on how this is handled in practice would be
>> very
>> helpful.
>>
>> Anirudh
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>>
>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>
> --
> John Criswell
> Assistant Professor
> Department of Computer Science, University of Rochester
> http://www.cs.rochester.edu/u/criswell
>