Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Signless Types For LLVM #1322

Closed
llvmbot opened this issue Oct 17, 2006 · 23 comments
Closed

Signless Types For LLVM #1322

llvmbot opened this issue Oct 17, 2006 · 23 comments
Labels
bugzilla code-quality llvm:core

Comments

@llvmbot
Copy link
Collaborator

@llvmbot llvmbot commented Oct 17, 2006

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
Copy link
Collaborator Author

@llvmbot llvmbot commented Oct 17, 2006

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.

@llvmbot
Copy link
Collaborator Author

@llvmbot llvmbot commented Oct 17, 2006

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.

@lattner
Copy link
Collaborator

@lattner lattner commented Oct 17, 2006

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

-Chris

@llvmbot
Copy link
Collaborator Author

@llvmbot llvmbot commented Oct 22, 2006

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
Copy link
Collaborator

@lattner lattner commented Oct 22, 2006

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
Copy link
Collaborator Author

@llvmbot llvmbot commented Oct 22, 2006

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
Copy link
Collaborator

@lattner lattner commented Oct 22, 2006

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

-Chris

@llvmbot
Copy link
Collaborator Author

@llvmbot llvmbot commented Oct 25, 2006

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
Copy link
Collaborator

@lattner lattner commented Oct 25, 2006

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
Copy link
Collaborator Author

@llvmbot llvmbot commented Oct 25, 2006

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
Copy link
Collaborator

@lattner lattner commented Oct 25, 2006

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
Copy link
Collaborator Author

@llvmbot llvmbot commented Oct 26, 2006

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
Copy link
Collaborator

@lattner lattner commented Oct 27, 2006

  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?

  1. 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
Copy link
Collaborator Author

@llvmbot llvmbot commented Oct 30, 2006

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.

@llvmbot
Copy link
Collaborator Author

@llvmbot llvmbot commented Nov 19, 2006

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
Copy link
Collaborator Author

@llvmbot llvmbot commented Nov 29, 2006

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
Copy link
Collaborator Author

@llvmbot llvmbot commented Dec 3, 2006

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.

@lattner
Copy link
Collaborator

@lattner lattner commented Dec 3, 2006

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

@llvmbot
Copy link
Collaborator Author

@llvmbot llvmbot commented Dec 3, 2006

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
Copy link
Collaborator

@lattner lattner commented Dec 3, 2006

Again, there should be no ambiguity.

@llvmbot
Copy link
Collaborator Author

@llvmbot llvmbot commented Dec 3, 2006

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
Copy link
Collaborator

@lattner lattner commented Jan 4, 2007

is this done?

@llvmbot
Copy link
Collaborator Author

@llvmbot llvmbot commented Jan 4, 2007

This has been implemented.

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 3, 2021
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bugzilla code-quality llvm:core
Projects
None yet
Development

No branches or pull requests

2 participants