//===----------------------------------------------------------------------===// // LLVM Type System Changes //===----------------------------------------------------------------------===// 8/18/2004 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 types 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 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. In the future, we also need to support more primitive types as well, including "long double" types of 80 and 128 bits, as well as support various wierd non-IEEE floating point formats. 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. None of these minor deficiencies are fatal, but it would be nice if they were fixed. //===----------------------------------------------------------------------===// // The proposed solution The solution is simple: eliminate the distinction between signed and unsigned integer types, and rename the primitive types to indicate their size. In particular, the primitive types we would be left with would include i1, i8, i16, i32, i64, f32, and f64. Before we can do this, however, we need to change all of the instructions that use the signedness of their operands to change their semantics. Luckily, we can do this incrementally, an instruction at a time, so the whole big change can be done one small step at a time. In particular, I would suggest the following new instructions be added to LLVM. * Signed divide: "sdiv", Instruction::SDiv ... was signed div * Unsigned divide: "udiv", Instruction::UDiv ... was unsigned div * Signed remainder: "srem", Instruction::SRem ... was signed rem * Unsigned remainder: "urem", Instruction::URem ... was unsigned rem * Arithmetic shift right: "ashr", Instruction::AShr ... was Signed shr * Logical shift right: "lshr", Instruction::LShr ... was Unsigned "shr" * Value truncate: "trunc", Instruction::Trunc ... was cast integer to smaller integer ... was cast double to float * Sign extend: "signext", Instruction::SignExt ... was cast signed integer to larger integer ... was cast integer to floating point * Zero extend: "zeroext", Instruction::ZeroExt ... was cast unsigned integer to larger integer * Round FP to int: "round", Instruction::Round ... was cast floating point to integer (need to specify semantics better!) * Convert: "convert", Instruction::Convert Semantics are defined as if the first value was stored into memory and then read back out from it through a casted pointer type. In C, something like: SrcTy Tmp = ... DstTy Result = *(DstTy*)&Tmp; The source and destination must be of the same size, though this may not be verifiable if one is a integer or FP and the other is a pointer. ... was cast pointer to pointer ... was pointer to integer ... was integer to pointer Note that this finally gives us the ability to represent a bit conversion from float -> int without having to go through memory (though code generators would probably implement this by using a stack slot temporary). //===----------------------------------------------------------------------===// // Solving the setcc "changing opcode" problem The SetCC instructions obviously need to be extended to differentiate between signed and unsigned operands, but this change gives us the opportunity to do another big change that needs to be done as well. In particular, SetCondInst's are the *ONLY* LLVM instruction that ever changes Opcode (hence, Value::VTy) once created. This is clearly a bad thing, and leads to several ugly hacks in VMCore to deal with it (start tracking from BinaryOperator::swapOperands). The solution to this is a simple one, and has already been started a long time ago. Notice how (what a coincidence!) SetCondInst is the only binary operator that has its own class to represent it. The solution to the "changing opcode" problem is simply to take the CC out of the opcode and move it to be a small field in the SetCondInst class. After this change, all SetCondInst instructions will be represented with Instruction::SetCC opcode. In the .bc file and .ll files they can stay the same, or change, whatever works best (I lean towards keeping the .ll syntax the same). //===----------------------------------------------------------------------===// // Solving the SetCC type-system problem. To address the topic of this text file, we simply change the ordering operators to indicate the signedness of the comparison in the condition. In particular, instead of setlt, there would be setult & setlt (note not setslt, see below). //===----------------------------------------------------------------------===// // Solving the "ugly unordered comparison" problem. Another problem suffered by setcc instructions involves unordered comparisons. Currently unordered comparisons (like "set less than or unordered") are implemented with three instructions: a setlt, a call to llvm.isunordered, and a logical or of the result. This is completely horrible from several perspectives, including code/IR size (three instructions, one of which is a three operand call, is horrible), code generation (pattern matching on this is not hard, but is annoying and stupid), and code transformation perspective (instruction combining on this is, well tedious). "While we are it" implementing the other changes to SetCC, it makes sense to use that handy "u" bit, and use if for unordered comparisons as well. In particular, setult on a floating point value would return true if the operands are less than or unordered (On integers, this is setlt with unsigned interpretation). This is why we probably don't want setslt for integer signed setlt: this opcode makes no sense for the FP version. The funny thing is, this is exactly how hardware implements floating point comparisons. To be fully general, this should be implemented as a four bit field, with the following interpretation for setcc X, Y: U L G E 0 0 0 0 setfalse -> always returns false 0 0 0 1 seteq 0 0 1 0 setgt 0 0 1 1 setge 0 1 0 0 setlt 0 1 0 1 setle 0 1 1 0 setne 0 1 1 1 setnuo -> True if not unordered 1 0 0 0 setuo -> True if unordered (isnan(X) || isnan(Y)) 1 0 0 1 setueq -> True if unordered or equal 1 0 1 0 setugt -> True if unordered or gt 1 0 1 1 setuge -> True if unordered or ge 1 1 0 0 setult -> True if unordered or lt 1 1 0 1 setule -> True if unordered or le 1 1 1 0 setune -> True if unordered or ne 1 1 1 1 settrue -> always returns true The nice thing about assigning meaning like this is that the standard operations are implemented as bit ops on the condition code. For example, logical negate is "CC xor 1111b". Other operations are also simple, see the stuff in the SelectionDAG that handles condcodes for more details. (setcc1 X, Y) | (setcc2 X, Y) -> (setcc3 X, Y) with cc3 = cc1|cc2. //===----------------------------------------------------------------------===// // Implementation The nice thing about this problem is that, though it's a huge change to the entire LLVM system and will require lots of code to eventually be touched, it can be done completely incrementally. For example, the AShr and LShr instructions can be introduced to the system without changing any of the existing code. Once its in, all existing users of Shr can be audited and checked to make sure that LShr and UShr are handled the same as Shr is (this is to prevent previously working optimizations from being lost). Once everything is happy, all producers of Shr are eliminated (changed to produce UShr or LShr), and finally, Shr can be deleted. Obviously the bcreader and AsmParser would continue to autoupgrade old files as appropriate. Alternatively, given buyin from the entire LLVM Community, this might be a good time to switch to "LLVM 2.0", break the file formats and move on (providing a perl script to upgrade old .ll files?) //===----------------------------------------------------------------------===// // The next step Once this *major* problem is addressed, we can look at other interesting changes to the type system, some of which are obviously useful (e.g., add f80), but others of which are quite questionable. In particular, once we had this system, it would be straight-forward to add support for arbitrarily sized integers (e.g. i36) or generalize the floating point support to encode the exponent/mantissa sizes (instead of f32, have f8m23 or something). Again, the use of this is clearly questionable, and the impact could be very broad and annoying (imagine structs or arrays of these and the implications for layout), but could be an interesting "research project" for someone. :) It could also make LLVM the compiler of choice to the huge install base of PDP11 users!!