llvm dev - Oct 2012 - [LLVMdev] Predication on SIMD architectures and LLVM

Hello,
I'm working on a compiler based on LLVM for a SIMD architecture that 
supports instruction predication. We would like to implement branching 
on this architecture using predication.
As you know the LLVM-IR doesn't support instruction predication, so I'm 
not exactly sure on what is the best way to implement it.
We came up with some ways to do it in LLVM:

- Do not add any predication in the IR (except for load and stores 
through intrinsics), linearize the branches and substitute PHI nodes 
with selects for merging values . In the backend then we would custom 
lower the select instruction to produce a predicated mov to choose the 
right version of the value. I think this option doesn't make use of the 
possible benefits of the architecture we are targeting at all.

- Another way could be adding intrinsics for all instructions in the 
target to make them support predication, still linearize all the 
branches, but use instruction predication instead of generating cmovs . 
The backend then would custom lower almost any instruction into 
predicated custom nodes that are matched through tablegen patterns. We 
could generate these intrinsics in the same IR pass that linearizes 
branches.

- Make a custom backend that actually directly outputs predicated 
instructions (we really mainly only need one type of predicate , so 
every instruction could use that kind of predicate ...) but I think this 
is a nasty solution ...

Did someone already tried to do this in LLVM and if yes what solution/s 
did you use to solve the problem?

Regards,
Marcello

-- 
Marcello Maggioni
Codeplay Software Ltd
45 York Place, Edinburgh, EH1 3HP
Tel: 0131 466 0503
Fax: 0131 557 6600
Website: http://www.codeplay.com
Twitter: https://twitter.com/codeplaysoft

This email and any attachments may contain confidential and /or privileged
information and is for use by the addressee only. If you are not the intended
recipient, please notify Codeplay Software Ltd immediately and delete the
message from your computer. You may not copy or forward it,or use or disclose
its contents to any other person. Any views or other information in this message
which do not relate to our business are not authorized by Codeplay software Ltd,
nor does this message form part of any contract unless so stated.
As internet communications are capable of data corruption Codeplay Software Ltd
does not accept any responsibility for any changes made to this message after it
was sent. Please note that Codeplay Software Ltd does not accept any liability
or responsibility for viruses and it is your responsibility to scan any
attachments.
Company registered in England and Wales, number: 04567874
Registered office: 81 Linkfield Street, Redhill RH1 6BY

Hi Marcello,

On Fri, Oct 19, 2012 at 04:38:29PM +0100, Marcello Maggioni
wrote:
> Hello,
> I'm working on a compiler based on LLVM for a SIMD architecture that 
> supports instruction predication. We would like to implement branching 
> on this architecture using predication.
> As you know the LLVM-IR doesn't support instruction predication, so
I'm
> not exactly sure on what is the best way to implement it.
> We came up with some ways to do it in LLVM:
  I recall Ocelot [1], a binary translator which translates PTX into LLVM
also faces the same problem. You might want to take a look on what
Ocelot does.

HTH,
chenwj

[1] http://www.gdiamos.net/papers/ocelot-pact.pdf

-- 
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667
Homepage: http://people.cs.nctu.edu.tw/~chenwj

Hi Marcello,

I am sure I've seen some postings on the list concerning architectures 
that support predicated execution and how to map that to LLVM IR, I'm 
just not sure anymore when and who was involved :).

I have implemented your first suggestion for targets that do not have 
predicated instructions (where control flow to data flow conversion with 
explicit maintaining of masks and blend operations is the only option 
you have for SIMD vectorization). However, I agree with you that this is 
not a good solution for you since you would basically ignore one of the 
strengths of your platform. Should you still need some code or help with 
this, feel free to drop me a message.

Cheers,
Ralf

On 19.10.2012 17:38, Marcello Maggioni wrote:
> Hello,
> I'm working on a compiler based on LLVM for a SIMD architecture that
> supports instruction predication. We would like to implement branching
> on this architecture using predication.
> As you know the LLVM-IR doesn't support instruction predication, so
I'm
> not exactly sure on what is the best way to implement it.
> We came up with some ways to do it in LLVM:
>
> - Do not add any predication in the IR (except for load and stores
> through intrinsics), linearize the branches and substitute PHI nodes
> with selects for merging values . In the backend then we would custom
> lower the select instruction to produce a predicated mov to choose the
> right version of the value. I think this option doesn't make use of the
> possible benefits of the architecture we are targeting at all.
>
> - Another way could be adding intrinsics for all instructions in the
> target to make them support predication, still linearize all the
> branches, but use instruction predication instead of generating cmovs .
> The backend then would custom lower almost any instruction into
> predicated custom nodes that are matched through tablegen patterns. We
> could generate these intrinsics in the same IR pass that linearizes
> branches.
>
> - Make a custom backend that actually directly outputs predicated
> instructions (we really mainly only need one type of predicate , so
> every instruction could use that kind of predicate ...) but I think this
> is a nasty solution ...
>
> Did someone already tried to do this in LLVM and if yes what solution/s
> did you use to solve the problem?
>
> Regards,
> Marcello
>

We are currently doing something similar to your third option in Hexagon
backend. But it is a VLIW so predication is not the only reason for that.

Sergei

---
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by
The Linux Foundation
> -----Original Message-----
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu]
> On Behalf Of Marcello Maggioni
> Sent: Friday, October 19, 2012 10:38 AM
> To: llvmdev at cs.uiuc.edu
> Subject: [LLVMdev] Predication on SIMD architectures and LLVM
> 
> Hello,
> I'm working on a compiler based on LLVM for a SIMD architecture that
> supports instruction predication. We would like to implement branching
> on this architecture using predication.
> As you know the LLVM-IR doesn't support instruction predication, so
I'm
> not exactly sure on what is the best way to implement it.
> We came up with some ways to do it in LLVM:
> 
> - Do not add any predication in the IR (except for load and stores
> through intrinsics), linearize the branches and substitute PHI nodes
> with selects for merging values . In the backend then we would custom
> lower the select instruction to produce a predicated mov to choose the
> right version of the value. I think this option doesn't make use of the
> possible benefits of the architecture we are targeting at all.
> 
> - Another way could be adding intrinsics for all instructions in the
> target to make them support predication, still linearize all the
> branches, but use instruction predication instead of generating cmovs .
> The backend then would custom lower almost any instruction into
> predicated custom nodes that are matched through tablegen patterns. We
> could generate these intrinsics in the same IR pass that linearizes
> branches.
> 
> - Make a custom backend that actually directly outputs predicated
> instructions (we really mainly only need one type of predicate , so
> every instruction could use that kind of predicate ...) but I think
> this is a nasty solution ...
> 
> Did someone already tried to do this in LLVM and if yes what solution/s
> did you use to solve the problem?
> 
> Regards,
> Marcello
> 
> --
> Marcello Maggioni
> Codeplay Software Ltd
> 45 York Place, Edinburgh, EH1 3HP
> Tel: 0131 466 0503
> Fax: 0131 557 6600
> Website: http://www.codeplay.com
> Twitter: https://twitter.com/codeplaysoft
> 
> This email and any attachments may contain confidential and /or
> privileged information and is for use by the addressee only. If you are
> not the intended recipient, please notify Codeplay Software Ltd
> immediately and delete the message from your computer. You may not copy
> or forward it,or use or disclose its contents to any other person. Any
> views or other information in this message which do not relate to our
> business are not authorized by Codeplay software Ltd, nor does this
> message form part of any contract unless so stated.
> As internet communications are capable of data corruption Codeplay
> Software Ltd does not accept any responsibility for any changes made to
> this message after it was sent. Please note that Codeplay Software Ltd
> does not accept any liability or responsibility for viruses and it is
> your responsibility to scan any attachments.
> Company registered in England and Wales, number: 04567874 Registered
> office: 81 Linkfield Street, Redhill RH1 6BY
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On Fri, Oct 19, 2012 at 04:38:29PM +0100, Marcello Maggioni
wrote:
> Hello,
> I'm working on a compiler based on LLVM for a SIMD architecture that
> supports instruction predication. We would like to implement
> branching on this architecture using predication.
> As you know the LLVM-IR doesn't support instruction predication, so
> I'm not exactly sure on what is the best way to implement it.
> We came up with some ways to do it in LLVM:
>
> - Do not add any predication in the IR (except for load and stores
> through intrinsics), linearize the branches and substitute PHI nodes
> with selects for merging values . In the backend then we would
> custom lower the select instruction to produce a predicated mov to
> choose the right version of the value. I think this option doesn't
> make use of the possible benefits of the architecture we are
> targeting at all.
>
You may want to look at the IfConversion pass
(lib/CodeGen/IfConversion.cpp).  This converts branches to predicated
instructions, and you may be able to use it for all branching if you
teach it to maintain a predicate stack. I actually looked into doing
this for the newest generation of GPUs (Southern Islands) supported by
the R600[1] backend which use predication for all branching, but opted
to go with a target specific pass until the backend is more stable.

-Tom

[1]
http://cgit.freedesktop.org/~tstellar/llvm/tree/lib/Target/AMDGPU
> - Another way could be adding intrinsics for all instructions in the
> target to make them support predication, still linearize all the
> branches, but use instruction predication instead of generating
> cmovs . The backend then would custom lower almost any instruction
> into predicated custom nodes that are matched through tablegen
> patterns. We could generate these intrinsics in the same IR pass
> that linearizes branches.
> 
> - Make a custom backend that actually directly outputs predicated
> instructions (we really mainly only need one type of predicate , so
> every instruction could use that kind of predicate ...) but I think
> this is a nasty solution ...
> 
> Did someone already tried to do this in LLVM and if yes what
> solution/s did you use to solve the problem?
> 
> Regards,
> Marcello
> 
> -- 
> Marcello Maggioni
> Codeplay Software Ltd
> 45 York Place, Edinburgh, EH1 3HP
> Tel: 0131 466 0503
> Fax: 0131 557 6600
> Website: http://www.codeplay.com
> Twitter: https://twitter.com/codeplaysoft
> 
> This email and any attachments may contain confidential and /or privileged
information and is for use by the addressee only. If you are not the intended
recipient, please notify Codeplay Software Ltd immediately and delete the
message from your computer. You may not copy or forward it,or use or disclose
its contents to any other person. Any views or other information in this message
which do not relate to our business are not authorized by Codeplay software Ltd,
nor does this message form part of any contract unless so stated.
> As internet communications are capable of data corruption Codeplay Software
Ltd does not accept any responsibility for any changes made to this message
after it was sent. Please note that Codeplay Software Ltd does not accept any
liability or responsibility for viruses and it is your responsibility to scan
any attachments.
> Company registered in England and Wales, number: 04567874
> Registered office: 81 Linkfield Street, Redhill RH1 6BY
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On 10/19/2012 5:12 PM, 陳韋任 (Wei-Ren Chen) wrote:
> Hi Marcello,
>
> On Fri, Oct 19, 2012 at 04:38:29PM +0100, Marcello Maggioni wrote:
>> Hello,
>> I'm working on a compiler based on LLVM for a SIMD architecture
that
>> supports instruction predication. We would like to implement branching
>> on this architecture using predication.
>> As you know the LLVM-IR doesn't support instruction predication, so
I'm
>> not exactly sure on what is the best way to implement it.
>> We came up with some ways to do it in LLVM:
>    I recall Ocelot [1], a binary translator which translates PTX into LLVM
> also faces the same problem. You might want to take a look on what
> Ocelot does.
>
> HTH,
> chenwj
>
> [1] http://www.gdiamos.net/papers/ocelot-pact.pdf
>
Hi Wen-Ren,

thank you for your link, seems like an interesting read on the argument!

Marcello

-- 
Marcello Maggioni
Codeplay Software Ltd
45 York Place, Edinburgh, EH1 3HP
Tel: 0131 466 0503
Fax: 0131 557 6600
Website: http://www.codeplay.com
Twitter: https://twitter.com/codeplaysoft

This email and any attachments may contain confidential and /or privileged
information and is for use by the addressee only. If you are not the intended
recipient, please notify Codeplay Software Ltd immediately and delete the
message from your computer. You may not copy or forward it,or use or disclose
its contents to any other person. Any views or other information in this message
which do not relate to our business are not authorized by Codeplay software Ltd,
nor does this message form part of any contract unless so stated.
As internet communications are capable of data corruption Codeplay Software Ltd
does not accept any responsibility for any changes made to this message after it
was sent. Please note that Codeplay Software Ltd does not accept any liability
or responsibility for viruses and it is your responsibility to scan any
attachments.
Company registered in England and Wales, number: 04567874
Registered office: 81 Linkfield Street, Redhill RH1 6BY

Hi Ralf,

yeah, I've checked if on the list there were any kind of reference to 
that , but I only found scattered and incomplete information (maybe some 
good stuff is there, but very well hidden, I will try to check again by 
the way).

About your work on predication, I know of your IR-level if-conversion 
and vectorization and a lot of my knowledge on the matter actually comes 
from your talk in the last Euro-LLVM conference in London, so thanks for 
that! Also thank you for your availability on discussing the matter!

Marcello

On 10/19/2012 5:24 PM, Ralf Karrenberg wrote:
> Hi Marcello,
>
> I am sure I've seen some postings on the list concerning architectures 
> that support predicated execution and how to map that to LLVM IR, I'm 
> just not sure anymore when and who was involved :).
>
> I have implemented your first suggestion for targets that do not have 
> predicated instructions (where control flow to data flow conversion 
> with explicit maintaining of masks and blend operations is the only 
> option you have for SIMD vectorization). However, I agree with you 
> that this is not a good solution for you since you would basically 
> ignore one of the strengths of your platform. Should you still need 
> some code or help with this, feel free to drop me a message.
>
> Cheers,
> Ralf
>
> On 19.10.2012 17:38, Marcello Maggioni wrote:
>> Hello,
>> I'm working on a compiler based on LLVM for a SIMD architecture
that
>> supports instruction predication. We would like to implement branching
>> on this architecture using predication.
>> As you know the LLVM-IR doesn't support instruction predication, so
I'm
>> not exactly sure on what is the best way to implement it.
>> We came up with some ways to do it in LLVM:
>>
>> - Do not add any predication in the IR (except for load and stores
>> through intrinsics), linearize the branches and substitute PHI nodes
>> with selects for merging values . In the backend then we would custom
>> lower the select instruction to produce a predicated mov to choose the
>> right version of the value. I think this option doesn't make use of
the
>> possible benefits of the architecture we are targeting at all.
>>
>> - Another way could be adding intrinsics for all instructions in the
>> target to make them support predication, still linearize all the
>> branches, but use instruction predication instead of generating cmovs .
>> The backend then would custom lower almost any instruction into
>> predicated custom nodes that are matched through tablegen patterns. We
>> could generate these intrinsics in the same IR pass that linearizes
>> branches.
>>
>> - Make a custom backend that actually directly outputs predicated
>> instructions (we really mainly only need one type of predicate , so
>> every instruction could use that kind of predicate ...) but I think
this
>> is a nasty solution ...
>>
>> Did someone already tried to do this in LLVM and if yes what solution/s
>> did you use to solve the problem?
>>
>> Regards,
>> Marcello
>>
-- 
Marcello Maggioni
Codeplay Software Ltd
45 York Place, Edinburgh, EH1 3HP
Tel: 0131 466 0503
Fax: 0131 557 6600
Website: http://www.codeplay.com
Twitter: https://twitter.com/codeplaysoft

This email and any attachments may contain confidential and /or privileged
information and is for use by the addressee only. If you are not the intended
recipient, please notify Codeplay Software Ltd immediately and delete the
message from your computer. You may not copy or forward it,or use or disclose
its contents to any other person. Any views or other information in this message
which do not relate to our business are not authorized by Codeplay software Ltd,
nor does this message form part of any contract unless so stated.
As internet communications are capable of data corruption Codeplay Software Ltd
does not accept any responsibility for any changes made to this message after it
was sent. Please note that Codeplay Software Ltd does not accept any liability
or responsibility for viruses and it is your responsibility to scan any
attachments.
Company registered in England and Wales, number: 04567874
Registered office: 81 Linkfield Street, Redhill RH1 6BY

Hello Sergei,

I actually don't know the hexagon platform very well, I only just 
briefly checked it's backend for reference on some things . Our target 
also has some VLIW features, but I hope we will not have to endup with 
the third option, I would like to keep it as a last resort.

Marcello
On 10/19/2012 5:29 PM, Sergei Larin wrote:
> We are currently doing something similar to your third option in Hexagon
> backend. But it is a VLIW so predication is not the only reason for that.
>
> Sergei
>
> ---
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted
by
> The Linux Foundation
>
>> -----Original Message-----
>> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu]
>> On Behalf Of Marcello Maggioni
>> Sent: Friday, October 19, 2012 10:38 AM
>> To: llvmdev at cs.uiuc.edu
>> Subject: [LLVMdev] Predication on SIMD architectures and LLVM
>>
>> Hello,
>> I'm working on a compiler based on LLVM for a SIMD architecture
that
>> supports instruction predication. We would like to implement branching
>> on this architecture using predication.
>> As you know the LLVM-IR doesn't support instruction predication, so
I'm
>> not exactly sure on what is the best way to implement it.
>> We came up with some ways to do it in LLVM:
>>
>> - Do not add any predication in the IR (except for load and stores
>> through intrinsics), linearize the branches and substitute PHI nodes
>> with selects for merging values . In the backend then we would custom
>> lower the select instruction to produce a predicated mov to choose the
>> right version of the value. I think this option doesn't make use of
the
>> possible benefits of the architecture we are targeting at all.
>>
>> - Another way could be adding intrinsics for all instructions in the
>> target to make them support predication, still linearize all the
>> branches, but use instruction predication instead of generating cmovs .
>> The backend then would custom lower almost any instruction into
>> predicated custom nodes that are matched through tablegen patterns. We
>> could generate these intrinsics in the same IR pass that linearizes
>> branches.
>>
>> - Make a custom backend that actually directly outputs predicated
>> instructions (we really mainly only need one type of predicate , so
>> every instruction could use that kind of predicate ...) but I think
>> this is a nasty solution ...
>>
>> Did someone already tried to do this in LLVM and if yes what solution/s
>> did you use to solve the problem?
>>
>> Regards,
>> Marcello
>>
>> --
>> Marcello Maggioni
>> Codeplay Software Ltd
>> 45 York Place, Edinburgh, EH1 3HP
>> Tel: 0131 466 0503
>> Fax: 0131 557 6600
>> Website: http://www.codeplay.com
>> Twitter: https://twitter.com/codeplaysoft
>>
>> This email and any attachments may contain confidential and /or
>> privileged information and is for use by the addressee only. If you are
>> not the intended recipient, please notify Codeplay Software Ltd
>> immediately and delete the message from your computer. You may not copy
>> or forward it,or use or disclose its contents to any other person. Any
>> views or other information in this message which do not relate to our
>> business are not authorized by Codeplay software Ltd, nor does this
>> message form part of any contract unless so stated.
>> As internet communications are capable of data corruption Codeplay
>> Software Ltd does not accept any responsibility for any changes made to
>> this message after it was sent. Please note that Codeplay Software Ltd
>> does not accept any liability or responsibility for viruses and it is
>> your responsibility to scan any attachments.
>> Company registered in England and Wales, number: 04567874 Registered
>> office: 81 Linkfield Street, Redhill RH1 6BY
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-- 
Marcello Maggioni
Codeplay Software Ltd
45 York Place, Edinburgh, EH1 3HP
Tel: 0131 466 0503
Fax: 0131 557 6600
Website: http://www.codeplay.com
Twitter: https://twitter.com/codeplaysoft

This email and any attachments may contain confidential and /or privileged
information and is for use by the addressee only. If you are not the intended
recipient, please notify Codeplay Software Ltd immediately and delete the
message from your computer. You may not copy or forward it,or use or disclose
its contents to any other person. Any views or other information in this message
which do not relate to our business are not authorized by Codeplay software Ltd,
nor does this message form part of any contract unless so stated.
As internet communications are capable of data corruption Codeplay Software Ltd
does not accept any responsibility for any changes made to this message after it
was sent. Please note that Codeplay Software Ltd does not accept any liability
or responsibility for viruses and it is your responsibility to scan any
attachments.
Company registered in England and Wales, number: 04567874
Registered office: 81 Linkfield Street, Redhill RH1 6BY

Hello Tom,

so basically what you are doing is in your AMDGPU backend is generating 
machine code like if it was a normal target (with diverging branches and 
stuff) and then through a custom post-ISel machine pass you do the if 
conversion linearizing and predicating the branches. Am I right? Seems 
like a much easier approach to apply than doing it at the IR level 
(because you don't have to add intrinsics to predicate your instructions) .

Marcello
On 10/19/2012 5:37 PM, Tom Stellard wrote:
> On Fri, Oct 19, 2012 at 04:38:29PM +0100, Marcello Maggioni wrote:
>> Hello,
>> I'm working on a compiler based on LLVM for a SIMD architecture
that
>> supports instruction predication. We would like to implement
>> branching on this architecture using predication.
>> As you know the LLVM-IR doesn't support instruction predication, so
>> I'm not exactly sure on what is the best way to implement it.
>> We came up with some ways to do it in LLVM:
>>
>> - Do not add any predication in the IR (except for load and stores
>> through intrinsics), linearize the branches and substitute PHI nodes
>> with selects for merging values . In the backend then we would
>> custom lower the select instruction to produce a predicated mov to
>> choose the right version of the value. I think this option doesn't
>> make use of the possible benefits of the architecture we are
>> targeting at all.
>>
> You may want to look at the IfConversion pass
> (lib/CodeGen/IfConversion.cpp).  This converts branches to predicated
> instructions, and you may be able to use it for all branching if you
> teach it to maintain a predicate stack. I actually looked into doing
> this for the newest generation of GPUs (Southern Islands) supported by
> the R600[1] backend which use predication for all branching, but opted
> to go with a target specific pass until the backend is more stable.
>
> -Tom
>
> [1] http://cgit.freedesktop.org/~tstellar/llvm/tree/lib/Target/AMDGPU
>> - Another way could be adding intrinsics for all instructions in the
>> target to make them support predication, still linearize all the
>> branches, but use instruction predication instead of generating
>> cmovs . The backend then would custom lower almost any instruction
>> into predicated custom nodes that are matched through tablegen
>> patterns. We could generate these intrinsics in the same IR pass
>> that linearizes branches.
>>
>> - Make a custom backend that actually directly outputs predicated
>> instructions (we really mainly only need one type of predicate , so
>> every instruction could use that kind of predicate ...) but I think
>> this is a nasty solution ...
>>
>> Did someone already tried to do this in LLVM and if yes what
>> solution/s did you use to solve the problem?
>>
>> Regards,
>> Marcello
>>
>> -- 
>> Marcello Maggioni
>> Codeplay Software Ltd
>> 45 York Place, Edinburgh, EH1 3HP
>> Tel: 0131 466 0503
>> Fax: 0131 557 6600
>> Website: http://www.codeplay.com
>> Twitter: https://twitter.com/codeplaysoft
>>
>> This email and any attachments may contain confidential and /or
privileged information and is for use by the addressee only. If you are not the
intended recipient, please notify Codeplay Software Ltd immediately and delete
the message from your computer. You may not copy or forward it,or use or
disclose its contents to any other person. Any views or other information in
this message which do not relate to our business are not authorized by Codeplay
software Ltd, nor does this message form part of any contract unless so stated.
>> As internet communications are capable of data corruption Codeplay
Software Ltd does not accept any responsibility for any changes made to this
message after it was sent. Please note that Codeplay Software Ltd does not
accept any liability or responsibility for viruses and it is your responsibility
to scan any attachments.
>> Company registered in England and Wales, number: 04567874
>> Registered office: 81 Linkfield Street, Redhill RH1 6BY
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-- 
Marcello Maggioni
Codeplay Software Ltd
45 York Place, Edinburgh, EH1 3HP
Tel: 0131 466 0503
Fax: 0131 557 6600
Website: http://www.codeplay.com
Twitter: https://twitter.com/codeplaysoft

This email and any attachments may contain confidential and /or privileged
information and is for use by the addressee only. If you are not the intended
recipient, please notify Codeplay Software Ltd immediately and delete the
message from your computer. You may not copy or forward it,or use or disclose
its contents to any other person. Any views or other information in this message
which do not relate to our business are not authorized by Codeplay software Ltd,
nor does this message form part of any contract unless so stated.
As internet communications are capable of data corruption Codeplay Software Ltd
does not accept any responsibility for any changes made to this message after it
was sent. Please note that Codeplay Software Ltd does not accept any liability
or responsibility for viruses and it is your responsibility to scan any
attachments.
Company registered in England and Wales, number: 04567874
Registered office: 81 Linkfield Street, Redhill RH1 6BY

Hi,

I've done work on predicated SIMD representations for LLVM.

If you search through the archives, you may find my "applymask"
proposal,
which is an attempt at representing predication in a very comprehensive
way. I've since stopped pushing the proposal in part because Larrabee's
changing fortunes led to a decline of interest at the time, in part because
the proposal doesn't look intuitive to people who don't have experience
in
SIMD programming, and in part because there were some technical details
with my actual proposal (although I believe solutions could be found).

And, in part because a popular trend seems to be to have SIMD units which
don't trap or raise exception flags on arithmetic and which don't go
faster
when predicated, such that there's no  reason to predicate anything except
stores and occasionally loads. On these architectures, simply having
intrinsics for stores, and perhaps loads, is basically sufficient, and less
invasive.

And, in part because predication is another wrinkle for SIMD performance
portability. As people start caring more about SIMD performance, there will
be more pressure to tune SIMD code in target-specific ways, and it erodes
the benefit of a target-independent representation. This is a complex topic
though, and there are multiple considerations, and not everyone agrees with
me here.

One thing that's initially counter-intuitive is that SIMD predication
cannot be done in the same way as scalar or VLIW predication, where the
majority of the compiler works as if it's on a "normal" scalar
machine and
predication happens during codegen, where the optimizer doesn't have to
think about it. SIMD predication must be applied by whatever code is
producing SIMD instructions, and in LLVM, that's typically in the optimizer
or earlier.

Dan

On Fri, Oct 19, 2012 at 8:38 AM, Marcello Maggioni <marcello at
codeplay.com>wrote:
> Hello,
> I'm working on a compiler based on LLVM for a SIMD architecture that
> supports instruction predication. We would like to implement branching on
> this architecture using predication.
> As you know the LLVM-IR doesn't support instruction predication, so
I'm
> not exactly sure on what is the best way to implement it.
> We came up with some ways to do it in LLVM:
>
> - Do not add any predication in the IR (except for load and stores through
> intrinsics), linearize the branches and substitute PHI nodes with selects
> for merging values . In the backend then we would custom lower the select
> instruction to produce a predicated mov to choose the right version of the
> value. I think this option doesn't make use of the possible benefits of
the
> architecture we are targeting at all.
>
> - Another way could be adding intrinsics for all instructions in the
> target to make them support predication, still linearize all the branches,
> but use instruction predication instead of generating cmovs . The backend
> then would custom lower almost any instruction into predicated custom nodes
> that are matched through tablegen patterns. We could generate these
> intrinsics in the same IR pass that linearizes branches.
>
> - Make a custom backend that actually directly outputs predicated
> instructions (we really mainly only need one type of predicate , so every
> instruction could use that kind of predicate ...) but I think this is a
> nasty solution ...
>
> Did someone already tried to do this in LLVM and if yes what solution/s
> did you use to solve the problem?
>
> Regards,
> Marcello
>
> --
> Marcello Maggioni
> Codeplay Software Ltd
> 45 York Place, Edinburgh, EH1 3HP
> Tel: 0131 466 0503
> Fax: 0131 557 6600
> Website: http://www.codeplay.com
> Twitter:
https://twitter.com/**codeplaysoft<https://twitter.com/codeplaysoft>
>
> This email and any attachments may contain confidential and /or privileged
> information and is for use by the addressee only. If you are not the
> intended recipient, please notify Codeplay Software Ltd immediately and
> delete the message from your computer. You may not copy or forward it,or
> use or disclose its contents to any other person. Any views or other
> information in this message which do not relate to our business are not
> authorized by Codeplay software Ltd, nor does this message form part of any
> contract unless so stated.
> As internet communications are capable of data corruption Codeplay
> Software Ltd does not accept any responsibility for any changes made to
> this message after it was sent. Please note that Codeplay Software Ltd does
> not accept any liability or responsibility for viruses and it is your
> responsibility to scan any attachments.
> Company registered in England and Wales, number: 04567874
> Registered office: 81 Linkfield Street, Redhill RH1 6BY
>
> ______________________________**_________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>
http://lists.cs.uiuc.edu/**mailman/listinfo/llvmdev<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20121019/74f16581/attachment.html>

Ralf Karrenberg <Chareos at gmx.de> writes:
> I am sure I've seen some postings on the list concerning architectures
> that support predicated execution and how to map that to LLVM IR, I'm
> just not sure anymore when and who was involved :).
I was one of them.  I suggested adding general predication to the LLVM
IR but that doesn't look like it's going to happen.  Dan Gohman had
another idea on how to represent predicate masks but that also didn't
relaly go anywhere.

None of your proposed solutions is ideal.  We really should have
first-class predication in the IR.  It's only going to get more
important.

                      -David

Dan Gohman <dan433584 at gmail.com> writes:
> And, in part because a popular trend seems to be to have SIMD units
> which don't trap or raise exception flags on arithmetic and which
don't
> go faster when predicated, such that there's no  reason to predicate
> anything except stores and occasionally loads. On these architectures,
> simply having intrinsics for stores, and perhaps loads, is basically
> sufficient, and less invasive.
This is going to change.  Intel recently released the ISA for Knights
Corner, a machine with general predication for SIMD.

http://software.intel.com/en-us/forums/topic/278102
> And, in part because predication is another wrinkle for SIMD
> performance portability. As people start caring more about SIMD
> performance, there will be more pressure to tune SIMD code in
> target-specific ways, and it erodes the benefit of a
> target-independent representation. This is a complex topic though, and
> there are multiple considerations, and not everyone agrees with me
> here.
It's true that a target-independent predicated IR isn't going to
translate well to a target that doesn't have predication.  However, for
targets that do it's a godsend.
> One thing that's initially counter-intuitive is that SIMD predication
> cannot be done in the same way as scalar or VLIW predication, where
> the majority of the compiler works as if it's on a "normal"
scalar
> machine and predication happens during codegen, where the optimizer
> doesn't have to think about it. SIMD predication must be applied by
> whatever code is producing SIMD instructions, and in LLVM, that's
> typically in the optimizer or earlier.
Yep.  This is why I think IR support is essential.

                                 -David