[LLVMdev] Inferring dependencies in phi instructions

[John Criswell]

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.

>
>> 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