//===----------------------------------------------------------------------===// // New LLVM 'undef' Value //===----------------------------------------------------------------------===// 8/26/2004 - Initial revision 10/6/2004 - Add note about undef for global variable initializers 10/11/2004 - Undef should derive from Constant, not directly from Value. 10/16/2004 - Implemented. This document describes the motivation and semantics of a new LLVM 'undef' value that should eventually be added to the IR. //===----------------------------------------------------------------------===// // The problem // LLVM currently has no way of representing the presence of undefined behavior. In particular, consider the following trivial testcase: int test() { int Y; return Y; } The return value of test is obviously undefined. However, currently, we lose this information in the mem2reg pass. Before mem2reg, we have something like this: int %test() { %Y = alloca int %YV = load int* %Y ret int %YV } When mem2reg is promoting the load, it needs to specify a value to use. Currently mem2reg always uses a zero value of the appropriate type (0, null, or -0.0) for undefined values. Because we lose this information, we miss optimization opportunities in many cases. In particular, on the X86 target, if we were returning an undefined value, we could just elide the mov EAX, 0 at the end of the function. This capabilty matters for a few reasons. First, note that the above was a completely contrived example to demonstrate the need. A real life example might look like this (K&R C): foo() { ... // no return } Because K&R implicitly defaults to returning int if no ret value is defined, many functions get an implicit int return value. Furthermore, since they MUST have a ret instruction with an appropriately typed operand, the CFE injects a ret int 0 into these functions. Because this return value is never used, this leads to dead code being generated. Another case this matters is in functions like the following: void test2() { int V; if (cond) V = ...; ... // stuff that does not modify or look at V. if (cond) use(V); } This function is has completely defined semantics, but V is only on one path through it. After mem2reg, this function has a zero value infered for the !cond case, leading to SSA that looks like this: void test2() { if (cond) V1 = ...; V2 = phi(V1, 0) ... // stuff that does not modify or look at V. if (cond) use(V2); } The extra 0 value in the V2 case leads to an extra integer copy instruction being executed in the !cond case. Another case that can be optimized with the undef value are global variables. In particular, front-ends sometimes know that globals are undefined when the program starts (this is the case in C++ before the ctor runs). If we have a program like this: int G = undef; ... G = 17; ... We can transform the program to initialize G to 17, and delete the store. This cannot normally be done if the FE initializes G to 0, because we won't know if G produces the value 0 or the value 17 at a load. //===----------------------------------------------------------------------===// // Proposed solution // The proposed solution to this problem is very simple. Simply add a new LLVM value 'undef'. This would be represented as an instance of the "Undefined" class, which derives from the Constant class. Undef can be used anywhere a value can be used, including the initializers of global variables and instruction operands. Undef values must derive from Constant so they can be used as operands to ConstantExpr's and as initializers for global variables. This also simplifies bytecode encoding as well. In the examples cases above, "test" would be compiled to "ret int undef". When code generating this, no native copy instruction is emitted to set the return value register (likewise in foo). In test2, the phi instruction would be "phi(V1, undef)", which would prevent code generation of the copy instruction in the !cond case. This value can also be used in the SCCP pass (which could directly propagate 'undefined' values from its analysis into the transformed program. Also, undef values may be used to simplify operations (e.g. add undef, 1 -> undef). This simplification should be performed by the instcombine pass. Note that not all operations can be eliminated. For example ((undef & ~3) | 3) & 3) yields a well defined value of 3. Adding the undef value should be relatively straight-forward.