predicates and conditional execution

Project Infrastructure LLVM Dev List Archives
1

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.

2

Hi, Roy

I was wondering if LLVM supports predicates and conditional execution.

  You can see the paper belows,
  Georgia Institute of Technology, School of Electrical and Computer Engineering

  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. :slight_smile:

Regards,
chenwj

3

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

4

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.

5

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?

Thanks, Roy.

6

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

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
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

–

Thanks,
Justin Holewinski

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?

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?

7

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.

8

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

9

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