[llvm-dev] IfConversion and representation of predicates

[Johnson, Nicholas Paul via llvm-dev]

Hello,

I have a few questions about applying the IfConversion pass to my out-of-tree target.  


(1) Is it true that the IfConversion pass may only run after register allocation?  

I often encounter this bad scenario, and I think it could be entirely avoided if IfConversion ran before register allocation:  the block-to-be-predicated contains load-immediate (LI) instructions.  The LI instructions accept any 32-bit immediate.  TII:PredicateInstruction can transform LI into a conditional-select (CSELxx) instruction, but on my target, CSELxx only accepts a 16-bit immediate.  This is less general; not all LI instructions can be predicated into CSELxx instructions, thus frequently preventing the block predication transformation .  I don't think I can run LI speculatively, because it risks clobbering a physical register live across the other branch.

If, alternatively, IfConversion ran before register allocation, the LI instructions could run speculatively.  The register allocator would prevent clobbering, and the predication transformation would succeed even for non-16-bit immediates.
 
I also see there is an EarlyIfConversion pass which is intended to run before register allocation.  However this pass seems significantly weaker than IfConversion as it doesn't allow the target to predicate arbitrary instructions.  Please correct my if I'm wrong about EarlyIfConversion.



(2) IfConversion assumes that predicable instructions share the same predicate forms as all conditional branches?

My target features compare-and-branch instructions (e.g., bgt r1.1,r1.2,label; or, beq r1.1,r1.2,label).  My target's implementation of TII::AnalyzeBranch returns correspondingly-complicated predicates, e.g. the tuples (r1.1, <, r1.2), (r1.1, ==, r1.2), etc.   

That works well for branch simplification but it doesn't mesh well with the conditional instructions on my target.  My target's other conditional instructions require a {zero, non-zero} condition operand in a general-purpose register.

Consequently, as I attempt to write TII::PredicateInstruction, I encounter the problem of translating a general binary predicate such as (r1.1, <, r1.2) into a single register value.  Aside from one convenient, degenerate case (r1.1, !=, 0), there is no direct representation of these binary comparison predicates in the other conditional instructions.  How should I support these other cases?  I don't think this interface allows/expects me to insert additional comparison instructions at this point in the compilation pipeline.  Even if I wanted to, this runs after register allocation, so my code would have no means to choose a physical register to hold the condition value.

How can I coax IfConversion into distilling the predicate array into a simple register?  Or, how should I restructure AnalyzeBranch to support both cases without losing generality in the first?


Nick Johnson
D. E. Shaw Research