[LLVMdev] if-conversion

[Ralf Karrenberg]

Hi Rob,

I chose to answer on the list since from time to time people come back 
to this.

That said, I did implement the generic variant of if-conversion that is 
called "control-flow to data-flow conversion" as a basis for SIMD 
vectorization. Essentially, the conversion removes all control flow 
except for loop back edges and replaces it by masks and blend (select) 
operations.

Details on the algorithm can be found in our paper on "Whole-Function 
Vectorization" (CGO 2011). The old, LLVM-based implementation of the 
algorithm is still online at github I believe. A completely rewritten 
one will be released along with submission of my PhD thesis at the end 
of the year.

That said, if you are only looking for if-conversion of code with 
limited complexity (e.g. no side effects, no loops), it is really simple:
- Compute masks for every block (entry mask: disjunction of incoming 
masks, exit masks: conjunctions of entry mask and (negated) condition).
- Replace each phi by a select that uses the entry mask of the 
corresponding block.
- Order blocks topologically by data dependencies, remove outgoing 
edges, create unconditional branches from each block to the next in the 
list.

Cheers,
Ralf


On 06/11/13 19:50, RobBishop wrote:
> Hi all,
>
> Sorry to dig up an old thread but I wondered what the status of
> if-conversion in LLVM is. Has any work been done towards handling this as a
> transform pass on the IR?
>
> I'm looking to implement an if-conversion pass and wanted to ensure that I'm
> not duplicating work. Is this something that others would also find useful?
>
> Rob
>
>
>
> --
> View this message in context: http://llvm.1065342.n5.nabble.com/if-conversion-tp2349p62937.html
> Sent from the LLVM - Dev mailing list archive at Nabble.com.
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>