if-conversion

Hello everyone,

I'd like to know if there is an optimization in llvm doing something
like an if-conversion on the IR. I only found IfConversion.cpp which
appears to only provide the desired functionality on machine code during
code-generation.

I want to transform branches into serial code with select-instructions
as a pre-processing step for further transformations.

If there is no such pass, I will possibly write one and share it
(although I have no idea how to do so yet), so please let me know :).

Cheers,
Ralf

SimplifyCFG should be doing this transform in very simple cases.
Depending on what you're doing, though, its might not be aggressive
enough.

-Eli

There is not any pass that can transform branches into serial code with select-instructions. Simplify CFG can handle simple cases of selecting one value based on a condition, but its goal is to simplify cfg. This may not be enough for your needs.

If you write a separate pass, we'd like to integrate it in mainline llvm sources.

If you write a separate pass, we'd like to integrate it in mainline
llvm sources.

Thank you for your answers. I will do my best to develop something which could be useful for more people :).

Cheers,
Ralf

Ralf Karrenberg wrote:

If you write a separate pass, we'd like to integrate it in mainline
llvm sources.
    
Thank you for your answers. I will do my best to develop something which
could be useful for more people :).
  

If you're looking for sources on how to do if-conversion, there's an
algorithm for it in the book "Optimizing Compilers for Modern
Architectures," Chapter 7. That algorithm, in turn, relies upon
computing control dependence. There's an algorithm for computing that
in the same chapter, and there's another algorithm for control
dependence in the following paper:

My recommendation is to write two passes: one that computes control
dependence and another that performs if-conversion. A
control-dependence analysis pass is useful for other analysis and
transform passes.

-- John T.

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

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