Basic Work Plan:

Each item below will be considered an iteration. An iteration consists of making
a small(ish) change across llvm and llvm-gcc4 and testing it with llvm-test and
deja-gnu. Development of new test cases will also occur as the instructions are
modified.

The iterations planned are the following (in roughly this order):

1. Remove ConstantSInt and ConstantUInt from LLVM by merging their capabilities
   in to ConstantInt.
2. Convert REM -> UREM, SREM. This makes the remainder instruction signed.
3. Convert DIV -> UDIV, SDIV. This makes the division instruction signed.
4. Convert SHR -> ASHR, LSHR. Deal with sign-extension in shift right.
5. Convert Cast -> TRUNC. Find all the truncating casts and convert them to
   use a new TRUNC instruction.
6. Convert Cast -> ZEXT. Find all the zero-extend casts and convert them to
   use a new ZEXT instruction.
7. Convert Cast -> SEXT. Find all the sign-extend casts and convert them to
   use a new SEXT instruction.
8. Convert Cast -> FPEXT. Find all FP casts of smaller to larger size and
   convert them to FPEXT instruction.
9. Convert Cast -> FPTRUNC. Find all FP casts of larger to smaller size and
   convert them to FPTRUNC instruction.
10. Convert remaining Casts to BITCONVERT instruction. This will bitwise
    convert a value of one type to another. Types must be the same bit width.
    The semantics are similar to a C cast or a C++ reinterpret_cast. That is,
    its as if the first operand was stored in memory and then read back through
    a pointer of the desired type.
11. Adjust the setcc instruction to differentiate between signed and unsigned
    operands. Also make the setcc opcode fixed instead of adjustable and
    implement the corresponding simplifications in BinaryOperator and
    SetCondInst classes. After this change, the setcc operand would be a normal
    BinaryOperator like any other with a single op code (Instruction::SetCC).
    The SetCondInst class would retain a small bit of data to indicate the kind
    of comparison to be performed instead of using the opcode for this purpose.
12. Adjust existing LLVM passes that pattern match for signedness (casts,
    specific integer types) to work without signed types but with signed
    instructions instead. Given the previous changes, there shouldn't be much.
13. Replace SByte/UByte with Int8. This is just a renaming.
14. Replace Short/UShort with Int16.
15. Replace Int/UInt with Int32.
16. Replace Long/ULong with Int64.

For the SETCC instruction, we envision using a 4-bit code to specify the
condition. The codes, mneumonics and semantics are described in the table below.

ULGE Mneumonic Semantics Description
0000 setfalse Always returns false
0001 seteq Returns true iff first operand is == second operand
0010 setgt Returns true iff first operand is > second operand
0011 setge Returns true iff first operand is >= second operand
0100 setlt Returns true iff first operand is < second operand
0101 setle Returns true iff first operand is <= second operand
0110 setne Returns true iff first operand is != second operand
0111 setnuo Returns true if neither operand is unordered
1000 setuo Returns true if either operand is unordered
1001 setueq Returns true if either operand is unordered or they are equal
1010 setug Returns true if either operand is unordered or first operand
is greater than second operand
1011 setuge Returns true if either operand is unordered or first operand
is greater than or equal to second operand
1100 setult Returns true if either operand is unordered or first operand
is less than second operand
1101 setule Returns true if either operand is unordered or first operand
is less than or equal to second operand
1110 setune Returns true if either operand is unordered or first operand
is not equal to second operand
1111 settrue Always returns true.

please consider using the table from SelectionDAGNodes.h, which is more complete.

-Chris

The table suggested by Chris is:

The bit mnemonics are:
N = No Care: undefined if either input is a nan.
U = Unordered
L = Less
G = Greater
E = Equal

NULGE Opcode Description
00000 SETFALSE Always false
00001 SETOEQ True if ordered and equal
00010 SETOGT True if ordered and greater than
00011 SETOGE True if ordered and greater than or equal
00100 SETOLT True if ordered and less than
00101 SETOLE True if ordered and less than or equal
00110 SETONE True if ordered and operands are unequal
00111 SETO True if ordered (no nans)
01000 SETUO True if unordered: isnan(X) | isnan(Y)
01001 SETUEQ True if unordered or equal
01010 SETUGT True if unordered or greater than
01011 SETUGE True if unordered, greater than, or equal
01100 SETULT True if unordered or less than
01101 SETULE True if unordered, less than, or equal
01110 SETUNE True if unordered or not equal
01111 SETTRUE Always true (always folded)
1X000 SETFALSE2 Always false (always folded)
1X001 SETEQ True if equal
1X010 SETGT True if greater than
1X011 SETGE True if greater than or equal
1X100 SETLT True if less than
1X101 SETLE True if less than or equal
1X110 SETNE True if not equal
1X111 SETTRUE2 Always true (always folded)

Another idea: It probably makes sense to split integer setcc and fp setcc, particularly if you're going to do
that with the other operations. This would give us 'setcc' and 'fsetcc' or something.

One particularly nice aspect of this is that you can have different enums for the integer/fp setcc's, so that
the extraneous enum values for the integer setcc don't need to be there.

-Chris

That's a good idea. So we would end up with two tables, like this:

For Floating Point SetCC (FSETCC):

NULGE Opcode Description
00000 SETFALSE Always false
00001 SETOEQ True if ordered and equal
00010 SETOGT True if ordered and greater than
00011 SETOGE True if ordered and greater than or equal
00100 SETOLT True if ordered and less than
00101 SETOLE True if ordered and less than or equal
00110 SETONE True if ordered and operands are unequal
00111 SETO True if ordered (no nans)
01000 SETUO True if unordered: isnan(X) | isnan(Y)
01001 SETUEQ True if unordered or equal
01010 SETUGT True if unordered or greater than
01011 SETUGE True if unordered, greater than, or equal
01100 SETULT True if unordered or less than
01101 SETULE True if unordered, less than, or equal
01110 SETUNE True if unordered or not equal
01111 SETTRUE Always true (always folded)

For Integer SetCC (SETCC):

LGE OpCode Description
000 SETFALSE Always false (always folded)
001 SETEQ True if equal
010 SETGT True if greater than
011 SETGE True if greater than or equal
100 SETLT True if less than
101 SETLE True if less than or equal
110 SETNE True if not equal
111 SETTRUE Always true (always folded)

The integer table is right. The FP table wants to keep the 'undefined on unordered' bit though.

-Chris

Chris Wrote:

The FP table wants to keep the 'undefined on unordered' bit though.

I don't understand. All the bits from the original table and the revised table
are the same. The only thing that changed was the integer table which you
indicated was correct.

you dropped:

1X001 SETEQ True if equal
1X010 SETGT True if greater than
1X011 SETGE True if greater than or equal
1X100 SETLT True if less than
1X101 SETLE True if less than or equal
1X110 SETNE True if not equal
1X111 SETTRUE2 Always true (always folded)

from the fp table.

-Chris

Ah, right, I was thinking we'd just use the integer codes for those cases but
they overlap with the FP codes. Thanks for the clarification.

Another (potentially better) approach would be to start the flagging: add a flag to fsetcc that indicates that
the operands are known to not be nan's.

Actually, in retrospect, I think that starting small is the right way to go. Right now we have no way (at the
llvm level) of saying that a comparison cannot have nan operands. As such, sticking with the truncated
table you proposed makes sense. We can extend the model later as a second step.

-Chris

Some proposals for the setcc instructions:

1. The name of these instructions is misleading. There is no "condition code"
   register in llvm to set. While that hardward construct is common, these
   instructions return the condition code as a boolean value. In keeping with
   what it does, I suggest we change the mnemonic to "cmp" which more accurately
   describes what the instruction does: compare values.

2. We will need 3 cmp instructions:
   ucmp (treats operands as unsigned int)
   scmp (treats operands as signed int)
   fcmp (operands must be floating point)

Make sense? Comments?

1. The name of these instructions is misleading. There is no "condition code"
   register in llvm to set.

Right, but the names of the mneumonics are things like "setlt", which sets the results based on a lt
comparison, and makes no mention of condition codes.

While that hardward construct is common, these
instructions return the condition code as a boolean value. In keeping with
what it does, I suggest we change the mnemonic to "cmp" which more accurately
describes what the instruction does: compare values.

I don't see this as being a big win, do you?

2. We will need 3 cmp instructions:
   ucmp (treats operands as unsigned int)
   scmp (treats operands as signed int)
   fcmp (operands must be floating point)

I think we need two, fset and iset (where cond is internally represented as flags, not as
the opcode). Splitting ucmp/scmp opens up questions of where ==/!= should belong (because they
don't care about sign), and changing one to the other is less efficient than just changing some flags.

-Chris

Note that the spec for vsetint and vsetfp (vector comparisons, returning a vector of bools), uses condition
codes that are identical to what Chris is proposing now. In particular, (1) there's only one "integer
comparison" instruction, so there are both signed and unsigned comparison codes; and (2) there are six
additional "don't care if ordered" fp condition codes.

New GEP Rules:

1. Sequential type indices may be (signless) integer of any size.
2. Sequential type indices will be sign extended to 64-bits.
3. Struct type indices may only be 32-bit integer constants.
4. Struct type indices will be treated as unsigned always.
5. Bytecode reader will upgrade old GEP instructions that use unsigned integer
   non-constant indices by inserting an explicit ZExt cast to 64-bits before
   the GEP. If the constant is already 64-bits no cast is inserted.
6. The Assembly reader will similarly upgrade old GEP instructions using
   unsigned non-constant indices.

New Plan for bc/asm upgrade:

Due to the signless types changes necessary to auto-upgrade bc and asm files to
the 2.0 constructs and rules, we've decided that it would be better to create a
separate tool, llvm-upgrade, to convert 1.X asm into 2.0 asm. It would be used
like this:

llvm-dis1.9 < 1.9.bc | llvm-upgrade | llvm-as2.0 > 2.0.bc

This avoids any need to provide backwards compatibility code in 2.0 in either
the asmparser or the bcreader allowing them to be re-written more easily.
Furthermore, it places all the upgrade things into a single tool instead of
spreading them into both the asmparser and the bcreader.

We have a conflict with the YACC Grammar for ULT/ULE/UGT/UGE. The current
definition uses these symbols with both the fcmp and icmp instructions (one is
with U=unsigned, the other U=unordered). While this isn't a problem for humans,
it is a problem for bison.

Consequently, I'm going to leave ULT/ULE/UGT/UGE for ICMP with "unsigned" meaning.

For FCMP, we'll use two prefixes: ORD and UNO so we would have:
UNOLT/UNOLE/UNOGT/UNOGE similary with ORDLT/ORDLE/ORDGT/ORDGE.

This should be clear enough for both humans and bison.

Reid.

hrm? It shouldn't be ambiguous, you just need to factor the grammar right. What are the relevant
productions?

There may be ways around it, but I"d rather avoid the ambiguity. The question
arises, in these cases:

icmp ult ...
fcmp ult ...

either of those could be in error depending on the operands and it isn't clear
whether its the opcode or the predicate that's in error.

I'd rather have the predicates be non-overlapping. If you have alternative
names, I'm open to it as long as they don't overlap.

Again, there should be no ambiguity.

The disambiguation has been moved to the parser from the lexer. The predicate
mnemonics have been restored to the 3-letter codes originally planned.

is this done?

This has been implemented.