: Predication on SIMD architectures and LLVM

Hi all,

I am working on a CGRA backend (something like a 2D VLIW), and we also absolutely need predication. I extended the IfConversion pass to allow it to be executed multiple times and to predicate already predicated code. This is necessary to predicate code with nested conditional statements. At this point, we support or, and, and conditional predicates (see Scott Mahlke's papers on this issue) as supported by the OpenIMPACT compiler (=Trimaran). If anyone is interested, I can show some of the code. It is rather ad-hoc, however, so it is not at all ready for integration in the trunk (I think).

The problem we are still facing is that this predication works post instruction selection and post register allocation. This is problematic because some of the earlier optimizations such as loop unrolling should ideally be applied on if-converted code, on which it is easier to judge the opportunities for, e.g., modulo scheduling and initiation interval constraints (such as ResMII, RecMII).

In my view, the ideal would be to have very generic, full (OpenIMPACT-like) predication support throughout LLVM, with the option of enabling/skipping early if-conversion just like one can enable or disable aggressive inlining.

Best,

Bjorn De Sutter
Computer Systems Lab
Ghent University

Hi all,

I am working on a CGRA backend (something like a 2D VLIW), and we also absolutely need predication. I extended the IfConversion pass to allow it to be executed multiple times and to predicate already predicated code. This is necessary to predicate code with nested conditional statements. At this point, we support or, and, and conditional predicates (see Scott Mahlke's papers on this issue) as supported by the OpenIMPACT compiler (=Trimaran). If anyone is interested, I can show some of the code. It is rather ad-hoc, however, so it is not at all ready for integration in the trunk (I think).

I would be interested in looking at the code, since Southern Islands
GPUs also require predicates for nested conditions.

-Tom

Hi Tom,

here is the main part of the patch. It requires some additional helper methods in the backend, but the meaning of those will be clear from this example I think.

By the way, this patch has only been tested on our own backend, of which we know where it can and cannot insert predicates. For one thing, we only insert predicates for if-conversion, in which case the predicate registers are only used locally. My code might be buggy under different assumptions.

Best,

Bjorn De Sutter
Computer Systems Lab
Ghent University

Index: IfConversion.cpp

In theory, MachineInstrs can be predicated before register allocation (in SSA), but the machine code will be full of false dependencies and liveness will not be predicate-aware. (Predicated instructions would need implicit use operand for any virtual register defs). You would basically lose reaching defs after predication.

You could implement a loop unroller for SSA MachineInstrs. It's conceptually similar to early tail duplication.

"Predicating" at IR level would have to take the form of an analysis that indicates which blocks *will* be predicated. You would have to leave the original CFG and phi nodes in tact to preserve control dependence and dataflow. Then you just have the problem of preserving that analysis across any changes to the CFG.

-Andy