[LLVMdev] predicates and conditional execution

[roy rosen]

Hi,

I was wondering if LLVM supports predicates and conditional execution.
Something like we have in IA64.
There is a register class of predicates and then every instruction may
be predicated by a register from this class.
For example:

cmp_less p, x, y // p is a predicate which gets the result of x < y
p add x, x, 2 // if p then do the add instruction

Is there support in LLVM to something like that?
Which architecture can show a good example for the implementation of that?

Thanks, Roy.
_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[陳韋任]

Hi, Roy

> I was wondering if LLVM supports predicates and conditional execution.

You can see the paper belows,
http://www.ece.gatech.edu/research/labs/casl/hetrovm/ocelot/2010/ocelot-pact.pdf

The author said LLVM does NOT provide predicate instruction but only
conditional select instruction. You have convert predicate instruction
to conditional select instruction by yourself.

HTH. :-)

Regards,
chenwj

--
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667

[Rotem, Nadav]

Hi Roy,

The LLVM IR does not support predicated instructions. However, it is possible to generate predicated assembly code. The x86 CMov instruction is one example.

I assume that your input program is not predicated and you are trying to use the unique features of your architecture, which has instruction predication.

I can think of several ways to implement this for your backend:

1. You can implement custom lowering to specific operations. The X86TargetLowering::LowerSELECT method in the X86 backend lowers the SELECT instruction to CMOV in many cases.
2. You can implement DAG combining optimizations for your backend which detect interesting patterns.
3. In some cases you can implement codegen patterns (in the td files). I suspect that this will be more difficult to implement and you will have to use #1 or #2.
4. If you are writing a domain specific language, you can generate intrinsic in your LLVM-IR.

Cheers,
Nadav

Hi,

---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.

[Justin Holewinski]

On Tue, May 24, 2011 at 3:02 AM, roy rosen <roy.1...@gmail.com> wrote:

Hi,

I was wondering if LLVM supports predicates and conditional execution.
Something like we have in IA64.
There is a register class of predicates and then every instruction may
be predicated by a register from this class.
For example:

cmp_less p, x, y // p is a predicate which gets the result of x < y
p add x, x, 2 // if p then do the add instruction

Is there support in LLVM to something like that?

Which architecture can show a good example for the implementation of that?

You may want to look at the PTX back-end.  The PTX assembly language supports exactly what you are describing, and we currently use it to implement conditional branching.  There is a register class for predicates (i1 in LLVM) and all machine instructions have a predicate operand and predicate filter (PTX supports inverted predicates).  For un-predicated instructions, the predicate operand is just set to the special NoRegister constant.

 

Thanks, Roy.
_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

--

Thanks,

Justin Holewinski

[roy rosen]

2011/5/24 Justin Holewinski <justin.h...@gmail.com>:

I see that PTX has predicated execution for all instructions.
in LLVM you implement conditional execution only for branches?
Do you know what it takes to make it work for all instructions?

[Justin Holewinski]

It already works for all instructions, as long as you supply a predicate operand in the machine instruction (not to be confused with an LLVM IR instruction).  Currently, this feature is only being used to implement conditional branches, but that is just because we have not implemented it for other cases.

The primary difficulty here is deciding when and how to use predicates.  LLVM IR does not support predicated execution, so we need to match specific LLVM IR patterns into predicated instructions when compiling for PTX.  It is somewhat trivial in cases such as conditional branches, where predicates are the only way to implement them in PTX, and some LLVM IR constructs such as the select instruction.  For more interesting cases, such as converting simple if-then-else statements into predicated instruction blocks, we still have yet to decide how best to handle this.

Can you provide a little more information on what you want to do in LLVM?  Are you wanting to generate an Itanium back-end, or are you just using that as an example?

Thanks, Roy.

--

Thanks,

Justin Holewinski

[roy rosen]

I am not writing an Itanium backend.
I am writing for a different architecture and am trying to understand
LLVM's capabilities in regards to the special features of my
architecture.

Thanks for the answers, Roy.

[Jim Grosbach]

On May 24, 2011, at 12:02 AM, roy rosen wrote:

> Hi,
>
> I was wondering if LLVM supports predicates and conditional execution.
> Something like we have in IA64.
> There is a register class of predicates and then every instruction may
> be predicated by a register from this class.
> For example:
>
> cmp_less p, x, y // p is a predicate which gets the result of x < y
> p add x, x, 2 // if p then do the add instruction
>
> Is there support in LLVM to something like that?
> Which architecture can show a good example for the implementation of that?

Hi Roy,

LLVM has support for predication. You may want to look at the ARM backend. It has predication for most instructions, and the compiler tries hard to make effective use of the feature. In the target independent code, you'll also want to examine the IfConversion pass, which does most of the heavy lifting for actually making the transformations between explicit CFG and predicated instructions.

-Jim

[Evan Cheng]

It's important to point out the current predication support is very limited. For example, the register allocator and instruction schedulers (and most of MI passes) are not predication aware. Also, only ARM uses the if-converter and it's done after register allocation.

There is quite a bit of infrastructure missing to make LLVM a fully predication aware compiler that's appropriate for an arch like IA64.

Evan