llvm dev - Jun 2008 - [LLVMdev] Variable length condition code for SETCC and SELECT?

After a hiatus on the CellSPU development, I've got all of the 
instructions necessary to get the llvm-gcc frontend to build. I've now 
discovered a new and interesting problem that I'm not sure how to solve 
cleanly and it's due to the fact that CellSPU has no fixed size 
condition flags. CellSPU's condition flags depend on the size of what's 
being compared, i.e., if both arguments to SETCC are i32, then a 
corresponding i32 comparison should be generated. Similarly, if both 
arguments to SETCC are i16 or i8, then a corresponding i16 or i8 
comparison should be generated.

Another nice feature in the CellSPU architecture is the selb instruction 
that directly corresponds to SELECT. Again, though, if SETCC is i32, 
then SELECT has to be i32; if SETCC is i16, then SELECT has to be i16, etc.

Currently, I've got what looks to be a promotion problem showing up when 
compiling _addvsi3.c during the libgcc2 phase of llvm-gcc. The optimized 
selection DAG is show below:

Optimized lowered selection DAG:
SelectionDAG has 20 nodes:
  0x14ffca0: ch = EntryToken
    0x14ffca0: <multiple use>
    0x1500710: i32 = Register  #1025
  0x1500770: i32,ch = CopyFromReg 0x14ffca0, 0x1500710
    0x14ffca0: <multiple use>
    0x1500820: i32 = Register  #1026
  0x1500880: i32,ch = CopyFromReg 0x14ffca0, 0x1500820
    0x1500880: <multiple use>
    0x1500770: <multiple use>
  0x1500a00: i32 = add 0x1500880, 0x1500770
  0x1500b50: ch = setgt
        0x14ffca0: <multiple use>
        0x1501030: i32 = Register  #1024
        0x1500a00: <multiple use>
      0x1501090: ch = CopyToReg 0x14ffca0, 0x1501030, 0x1500a00
      0x14ffca0: <multiple use>
    0x1501330: ch = TokenFactor 0x1501090, 0x14ffca0
          0x1500880: <multiple use>
          0x15004c0: i32 = Constant <4294967295>
          0x1500b50: <multiple use>
        0x1500bb0: i1 = setcc 0x1500880, 0x15004c0, 0x1500b50
          0x1500a00: <multiple use>
          0x1500770: <multiple use>
          0x1500ab0: ch = setlt
        0x1500e90: i1 = setcc 0x1500a00, 0x1500770, 0x1500ab0
          0x1500a00: <multiple use>
          0x1500770: <multiple use>
          0x1500b50: <multiple use>
        0x1500c80: i1 = setcc 0x1500a00, 0x1500770, 0x1500b50
      0x1500f60: i1 = select 0x1500bb0, 0x1500e90, 0x1500c80
      0x15011b0: i1 = Constant <1>
    0x1501220: i1 = xor 0x1500f60, 0x15011b0
    0x15012d0: ch = BasicBlock <bb20 0x14ff930>
  0x15013e0: ch = brcond 0x1501330, 0x1501220, 0x15012d0

The setcc's are promoted to i32, since they are comparing i32 operands. 
The problem arises when the select (0x1500f60) is promoted by 
SelectionDAGLegalize::PromoteOp(), because the select's i1 is promoted 
to i8, which triggers an assert because select's arguments (i32) don't 
match the new, promoted value type.

It's possible to convince the SELECT case inside of 
SelectionDAGLegalize::PromoteOp() that it should really look at the 
operands' value type and then return a result promoted to the operands' 
value (i32, in this case.) But that doesn't work, because further on, we 
don't know to promote the i1 constant <1> to i32, and another assert 
gets triggered because select's i32 is larger/not equal to the 
constant's new promotion to i8.

It'd be easy to hack PromoteOp to make a pass to determine all operands'
promoted value types, take the max, then figure out some way to 
re-promote them to maximal promoted value type. Except that this is a 
non-optimal solution requiring PromoteOp to potentially traverse the 
operand tree twice.

Any suggestions or ideas?


-scooter

B. Scott Michel wrote:
> It'd be easy to hack PromoteOp to make a pass to determine all
operands'
> promoted value types, take the max, then figure out some way to 
> re-promote them to maximal promoted value type. Except that this is a 
> non-optimal solution requiring PromoteOp to potentially traverse the 
> operand tree twice.
>
> Any suggestions or ideas?
>   
Not many suggestions or ideas, given the feedback so far. I'm not sure 
that two passes down a Node's Operand DAG can be avoided. The first pass 
would determine the maximal MVT needed, the second pass would generate 
the promoted Nodes.

In the absence of any suggestions or ideas, it's off to begging 
forgiveness if the patch confuses people and code. :-)


-scooter

B. Scott Michel wrote:
>B. Scott Michel wrote:
>  
>
>>It'd be easy to hack PromoteOp to make a pass to determine all
operands'
>>promoted value types, take the max, then figure out some way to 
>>re-promote them to maximal promoted value type. Except that this is a 
>>non-optimal solution requiring PromoteOp to potentially traverse the 
>>operand tree twice.
>>
>>Any suggestions or ideas?
>>  
>>    
>>
>Not many suggestions or ideas, given the feedback so far. I'm not sure 
>that two passes down a Node's Operand DAG can be avoided. The first pass
>would determine the maximal MVT needed, the second pass would generate 
>the promoted Nodes.
>
>In the absence of any suggestions or ideas, it's off to begging 
>forgiveness if the patch confuses people and code. :-)
>  
>
I like talking to myself... and I've been hacking on a two-pass version
of SelectionDAGLegalize::PromoteOp, where the first pass determines the
maximum type to which the subDAG need to be promoted, and the second
pass then does all of the SDOperand promotions.

However, I'm starting to notice that I'm having to duplicate switch
statements or add nasty if/then statements having to do with which pass
is currently active. I am starting to think that these promotion
functions really ought to be SDOperand virtual methods. Why promote the
SDOperands when you can ask the SDOperands to promote themselves (*)?

How much objection would there be if I rolled for initiative and created
extra files, one per SDOperand subclass in a CodeGen subdirectory? At a
minimum the source for each SDOperand subclass would contain its
destructor, and would also get rid of all of those Anchor() virtual
functions.

I know there's been talk in the past of cleaning up the Legalize switch
statement, but, for the record, that's not my objective -- although this
would lay out some groundwork for that subproject to evolve, should it
ever materialize. I'm also not talking about splitting up the
SelectionDAGNodes.h header file. Just creating additional source file
hierarchy (yes, I can hear the groans about extra compilation overhead)
so that augmenting SDOperand and its children is less onerous.


-scooter

(*) MIT response to how different disciplines hunt elephants in Africa:
"Sociologists don't hunt elephants, they help elephants find
themselves."

I am probably missing a key point. But why not just custom lower setcc  
and select into target specific nodes? X86 does this.

Evan

On Jun 5, 2008, at 5:44 PM, B. Scott Michel wrote:
> After a hiatus on the CellSPU development, I've got all of the
> instructions necessary to get the llvm-gcc frontend to build. I've now
> discovered a new and interesting problem that I'm not sure how to  
> solve
> cleanly and it's due to the fact that CellSPU has no fixed size
> condition flags. CellSPU's condition flags depend on the size of  
> what's
> being compared, i.e., if both arguments to SETCC are i32, then a
> corresponding i32 comparison should be generated. Similarly, if both
> arguments to SETCC are i16 or i8, then a corresponding i16 or i8
> comparison should be generated.
>
> Another nice feature in the CellSPU architecture is the selb  
> instruction
> that directly corresponds to SELECT. Again, though, if SETCC is i32,
> then SELECT has to be i32; if SETCC is i16, then SELECT has to be  
> i16, etc.
>
> Currently, I've got what looks to be a promotion problem showing up  
> when
> compiling _addvsi3.c during the libgcc2 phase of llvm-gcc. The  
> optimized
> selection DAG is show below:
>
> Optimized lowered selection DAG:
> SelectionDAG has 20 nodes:
>  0x14ffca0: ch = EntryToken
>    0x14ffca0: <multiple use>
>    0x1500710: i32 = Register  #1025
>  0x1500770: i32,ch = CopyFromReg 0x14ffca0, 0x1500710
>    0x14ffca0: <multiple use>
>    0x1500820: i32 = Register  #1026
>  0x1500880: i32,ch = CopyFromReg 0x14ffca0, 0x1500820
>    0x1500880: <multiple use>
>    0x1500770: <multiple use>
>  0x1500a00: i32 = add 0x1500880, 0x1500770
>  0x1500b50: ch = setgt
>        0x14ffca0: <multiple use>
>        0x1501030: i32 = Register  #1024
>        0x1500a00: <multiple use>
>      0x1501090: ch = CopyToReg 0x14ffca0, 0x1501030, 0x1500a00
>      0x14ffca0: <multiple use>
>    0x1501330: ch = TokenFactor 0x1501090, 0x14ffca0
>          0x1500880: <multiple use>
>          0x15004c0: i32 = Constant <4294967295>
>          0x1500b50: <multiple use>
>        0x1500bb0: i1 = setcc 0x1500880, 0x15004c0, 0x1500b50
>          0x1500a00: <multiple use>
>          0x1500770: <multiple use>
>          0x1500ab0: ch = setlt
>        0x1500e90: i1 = setcc 0x1500a00, 0x1500770, 0x1500ab0
>          0x1500a00: <multiple use>
>          0x1500770: <multiple use>
>          0x1500b50: <multiple use>
>        0x1500c80: i1 = setcc 0x1500a00, 0x1500770, 0x1500b50
>      0x1500f60: i1 = select 0x1500bb0, 0x1500e90, 0x1500c80
>      0x15011b0: i1 = Constant <1>
>    0x1501220: i1 = xor 0x1500f60, 0x15011b0
>    0x15012d0: ch = BasicBlock <bb20 0x14ff930>
>  0x15013e0: ch = brcond 0x1501330, 0x1501220, 0x15012d0
>
> The setcc's are promoted to i32, since they are comparing i32  
> operands.
> The problem arises when the select (0x1500f60) is promoted by
> SelectionDAGLegalize::PromoteOp(), because the select's i1 is promoted
> to i8, which triggers an assert because select's arguments (i32)
don't
> match the new, promoted value type.
>
> It's possible to convince the SELECT case inside of
> SelectionDAGLegalize::PromoteOp() that it should really look at the
> operands' value type and then return a result promoted to the  
> operands'
> value (i32, in this case.) But that doesn't work, because further  
> on, we
> don't know to promote the i1 constant <1> to i32, and another
assert
> gets triggered because select's i32 is larger/not equal to the
> constant's new promotion to i8.
>
> It'd be easy to hack PromoteOp to make a pass to determine all  
> operands'
> promoted value types, take the max, then figure out some way to
> re-promote them to maximal promoted value type. Except that this is a
> non-optimal solution requiring PromoteOp to potentially traverse the
> operand tree twice.
>
> Any suggestions or ideas?
>
>
> -scooter
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev