[LLVMdev] Inferring dependencies in phi instructions

[Anirudh Sivaraman]

On Jun 29, 2015 8:07 AM, "John Criswell" <jtcriswel at gmail.com> wrote:
>
> On 6/29/15 9:57 AM, Anirudh Sivaraman wrote:
>>
>> 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.
>
>
> The "select" instruction you mentioned earlier is what you want.
>

Do you mean something like this (because select instruction by itself
doesn't allow assignments to arbitrary expressions)?

For instance, if I was converting:

X = a + b (where X is an 8-bit integer)
into
if (path_condition) X = a + b

I would do:

path_condition = some boolean operation in the LLVM IR
tmp = a + b
X = select i1 path_condition, i8 tmp, i8 undef

>
>>
>>> 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?
>
>
> Control dependence is usually computed on basic block granularity (e.g., basic block B is control-dependent on a conditional branch at the end of basic block A).  Given that basic block B is control-dependent on basic block A, then all the phi-nodes at the beginning of basic block B are control-dependent on the conditional branch at the end of basic block A.
>
> If you're not familiar with the DominanceFrontier algorithm for computing control-dependence, I recommend you read it.  You can find it described in the Allen/Kennedy book as well as the paper "Efficiently Computing Static Single Assignment Form and the Control-Dependence Graph."
>
> Regards,
>
> John Criswell
>
>
>>
>>> 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
>>>
>
>
> --
> John Criswell
> Assistant Professor
> Department of Computer Science, University of Rochester
> http://www.cs.rochester.edu/u/criswell
>