Signless Types For LLVM

[llvmbot]

Bugzilla Link	950
Resolution	FIXED
Resolved on	Feb 22, 2010 12:50
Version	trunk
OS	All
Reporter	LLVM Bugzilla Contributor
CC	@lattner

Extended Description

Despite our best attempts, the LLVM type system somehow ended up too high-level. No! How can it be so? Let me tell you.

The LLVM primitive integer types maintain a distinction between signed and unsigned, when all we really want to know is the size of the data. This extra information bloats the .bc files and in-memory IR with "noop" casts (like int -> uint) and causes there to be redundancy in the LLVM language. This redundancy in the language currently leads to horrible missed optimization opportunities (particular in the indvars pass), but can even miss trivial cases (i.e. not CSE'ing (X+4) with ((unsigned)X + 4), which produce the same value). Another annoying thing is that 'int 1' and 'uint 1' both need to be written out to the .bc file, which is more duplication and takes space.

As a side note, we also have three trivial bits of ugliness:

1. we have an "SByte" type, but none of the other signed types are prefixed with S.
2. Using C names like "int" and "long" make people think that LLVM types vary in size like C types do, depending on the target.
3. Using all C names leads people think our type system is the same as C's, which is obviously untrue, but still people think that.

You can read more about this feature in Chris Lattner's LLVM Notes, at http://nondot.org/~sabre/LLVMNotes/TypeSystemChanges.txt.

Since this is a fairly extensive change to LLVM, this bug will be used to track the progress of the work as it proceeds.

[llvmbot]

This has been implemented.

[lattner]

is this done?

[llvmbot]

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

[lattner]

Again, there should be no ambiguity.

[llvmbot]

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.

[lattner]

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

[llvmbot]

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.

[llvmbot]

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.

[llvmbot]

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.

[llvmbot]

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.

[lattner]

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

[llvmbot]

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?

[lattner]

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

[llvmbot]

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.

[lattner]

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

[llvmbot]

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.

[lattner]

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

-Chris

[llvmbot]

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)

[lattner]

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

[llvmbot]

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)

[lattner]

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

-Chris

[llvmbot]

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.

[llvmbot]

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.