[LLVMdev] if-conversion
Ralf Karrenberg
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
_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Eli Friedman
> I want to transform branches into serial code with select-instructions
> as a pre-processing step for further transformations.
SimplifyCFG should be doing this transform in very simple cases.
Depending on what you're doing, though, its might not be aggressive
enough.
-Eli
Devang Patel
On Jan 20, 2009, at 2:29 AM, Ralf Karrenberg wrote:
> 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 :).
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.
-
Devang
Ralf Karrenberg
> llvm sources.
Thank you for your answers. I will do my best to develop something which
could be useful for more people :).
Cheers,
Ralf
John Criswell
>> 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 :).
>
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.
RobBishop
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.
Ralf Karrenberg
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
Jonas Wagner
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?
Evan Cheng
Sent from my iPad