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. :slight_smile:

-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. :slight_smile:

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."

Hi,

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.

there's a whole new infrastructure in development for promotion of illegal
types (as opposed to promotion of illegal operations on legal types):
LegalizeTypes. I'm not sure if it's relevant to you, but if it is then
you may want to think of how it impacts your design.

Ciao,

Duncan.

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

Evan