3 ms·
Because uninitialized variables are allowed to change values arbitrarily over their (nonexistent) "live range". Your proposal would force them into having a rea
by pcwalton 11y ago
Because uninitialized variables are allowed to change values arbitrarily over their (nonexistent) "live range". Your proposal would force them into having a real live range, with a stable value. See this section for an example, which shows examples of the kinds of optimizations this opens up:
http://llvm.org/docs/LangRef.html#undefined-values http://llvm.org/docs/LangRef.html#undefined-values
There's also the issue that having a stable value forces the register allocator to keep a live range for the undefined variable, which can cause unnecessary spills or remat in other places. Especially on 32-bit x86, this can be a problem.
- Dylan16807 11y ago> Because uninitialized variables are allowed to change values arbitrarily over their (nonexistent) "live range". Even specifying that they have a new arbitrary value on each access would be a big improvement over the status quo. It wouldn't allow nasal demons. Since LLVM seems to already have these semantics, it makes a good argument that it wouldn't hurt C's performance to tighten the spec at least that much. But I'm not seeing how C or C++ code gets you in a situation where you're purposefully doing arithmetic or bitwise operations on uninitialized variables. If it almost never happens, it doesn't need to optimize particularly well. What parts of the STL can be faster by treating uninitialized variables as impossible? > There's also the issue that having a stable value forces the register allocator to keep a live range for the undefined variable, which can cause unnecessary spills or remat in other places. This would only happen when the variable is accessed multiple times. In which case having to keep the value safe is no worse than if it actually had been initialized. I don't see how this is a problem.
- pcwalton 11y ago> What parts of the STL can be faster by treating uninitialized variables as impossible? What I'm mostly thinking of is allowing unused branches to be pruned. The STL tends to get inlined really heavily, which results in a whole pile of IR being emitted for what look like very simple operations. Based on the actual parameters and state, the optimizer then wants to prune out as much dead code as possible to reduce i-cache footprint, and sometimes time as well. Take small string optimization. That optimization requires a branch on length in almost every string operation. But if you have a std::string of constant size, you don't need the heap spilled code to be emitted at all. Usually the only way to work this out is inlining + constprop + DCE. That's where undefined value semantics are really helpful: a branch on an undefined value can be completely removed as undefined behavior, which can make its branch targets unreachable, and allow them to be removed, and so on recursively. Undefined values allow entire CFG subtrees to be eliminated in one fell swoop, which is an extremely powerful technique for reducing code size. I don't have a precise example off the top of my head as to where this kicks in in the STL, but I strongly suspect it does.
- Dylan16807 11y agoI still don't understand. Why would length be undefined if that's how you tell whether a string is small or not? Even if you can remove one of the branches because you know if the string is small, the logic of "this branch can't happen" -> undefined -> delete sounds more complex than "this branch can't happen" -> delete.
- jerf 11y agoThe order is undefined -> "I, the compiler, declare this branch can't happen" -> delete. The middle step is valid because "undefined behavior" permits the compiler to make that declaration, then act on it. If you don't want it to do that, use defined behaviors only, which is a great deal easier said than done. Partially because of how hard it is to avoid it in your own code, and partially because it is shot through all the other library code (which as pcwalton points out, courtesy of aggressive inlining, is also your code). I was skeptical about all this about six months ago myself, but the continuous stream of articles on this topic, plus the spectacular and highly educational failure of Friendly C (and not just that it failed, but why it failed, which is why I posted that exact link) has satisfied me. It is also part of why I've stepped up my own anti-C rhetoric since I've been so convinced... as bad as I thought C was, it really is, no sarcasm, not merely "hating", even worse than I thought. I am honestly scared to use it professionally and pretty much refuse to touch it without good static analysis support.
- Dylan16807 11y agoI just don't understand how "std::string of constant size" leads to the compiler inferring that a variable is undefined along a particular code path. In particular, on the not-taken code path, what is the uninitialized variable being branched on? Edit: Is it figuring out that the pointer in the string object is uninitialized? That doesn't seem any easier than reasoning about the length value, and I don't see how it would lead to "br undef".
- pcwalton 11y agoLLVM has been doing this optimization since 2008, and it contains justification in the commit message. LLVM commit #60470: Teach jump threading some more simple tricks: 1) have it fold "br undef", which does occur with surprising frequency as jump threading iterates. ... Chris didn't cite any specific numbers in the log, but I believe him when he says it actually happens. You should be able to run "opt -O2 -debug-only=jump-threading" and see where it does :) Related, with some actual numbers to prove it helps, LLVM commit #138618: SimplifyCFG: If we have a PHI node that can evaluate to NULL and do a load or store to the address returned by the PHI node then we can consider this incoming value as dead and remove the edge pointing there, unless there are instructions that can affect control flow executed in between. In theory this could be extended to other instructions, eg. division by zero, but it's likely that it will "miscompile" some code because people depend on div by zero not trapping. NULL pointer dereference usually leads to a crash so we should be on the safe side. This shrinks the size of a Release clang by 16k on x86_64.
- Gankro 11y ago> Even specifying that they have a new arbitrary value on each access would be a big improvement over the status quo. This is approximately what LLVM describes undef as, and it indeed leads to nasal demons. This description enables a single value to both pass a bounds check, and then subsequently go out of bounds!
- Dylan16807 11y agoYou're right, in certain cases it would still cause trouble, but it would be a lot fewer cases than 100%. Reading only once would be safe, and passing it to another functions would make a variable that can no longer change unexpectedly.
- dbaupp 11y agoUnless the function is inlined/the compiler can deduce that the variable is undef. (Of course, you could define it to work, but I would suspect that would make this sort of value much less useful.)