//===----------------------------------------------------------------------===// // New LLVM 'unreachable' Instruction //===----------------------------------------------------------------------===// 8/26/2004 - Initial revision 9/21/2004 - Changed name from 'barrier' to 'unreachable' 10/18/2004 - Implemented. This document describes the motivation and semantics of a new LLVM 'unreachable' instruction that should eventually be added to the IR. //===----------------------------------------------------------------------===// // The problem // LLVM currently has no way to indicate that a particular piece of code is unreachable. A portion of code can be unreachable for a variety of reasons. For example, if a function is known to not return normally (e.g. abort(), or a function that always unwinds). This information can either be provided by the LLVM front-end (e.g. through attribute(noreturn) in llvmgcc) or through interprocedural analysis on the LLVM level. The lack of this information pessimizes the code produced by LLVM. Consider this loop, for example: for (i = 0; i != 10; ++i) if (A[i] == 123) { printf("Invalid input\n"); exit(1); } llvmgcc (through attributes provided by header files) already knows that the exit function does not return. However, we currently compile this into an if block that calls printf and merges back into the loop. Because it appears to LLVM that subsequent iterations of the loop can execute after the printf/exit calls, the printf and exit blocks are considered to be part of the loop. This has two effects: 1. it pessimizes any loop transformations operating on that. 2. the register allocator thinks that all call clobbered registers are nuked in the loop, dramatically reducing allocation freedom (and hence, quality). Note that the use of no-return functions is very common in LLVM itself because of its extensive use of assertions. All of the "assert failed" code should terminate with an unreachable, leading to improvements in the generated code quality. Another thing that would be nice to be able to model is the fact that the default case in a switch instruction cannot be reached. Consider the following example: switch (i & 3) { case 0: foo1(); break; case 1: foo2(); break; case 2: foo3(); break; case 3: foo4(); break; } Through trivial analysis, it is clear that the "default" case in the switch can never be executed. Despite this, we end up modeling the switch statement with an LLVM switch instruction, which requires a default case. ---- Finally, note that the unreachable instruction can be used to optimize cases that we can prove as unreachable. For example, a call through a null pointer, or a load/store to a null pointer are dynamically undefined. Transforming these into an unreachable instruction would allow the optimizer to know that things after them cannot execute. //===----------------------------------------------------------------------===// // Proposed solution // The proposed solution to these problems is to introduce a new LLVM instruction 'unreachable'. The unreachable instruction would be a nullary terminator instruction. The semantics of the 'unreachable' instruction are completely undefined: if control flow dynamically reaches an 'unreachable' instruction, we do not say what will happen. This new, simple, instruction can be used to solve the problems described above. In particular, a front-end or analysis that knows that a function cannot return normally can place 'unreachable' instructions after any calls to the no-return function. In the case of the loop above, the unreachable instruction would replace the unconditional branch exiting the if condition, which would indicate to the natural loop analyzer that the if block is not actually part of the loop, and would lead to better register allocation. In the case of the switch instruction, the default case of the switch could go to a basic block containing only a unreachable instruction. Code generators could notice this situation and choose to elide the range test on the switch, leading to more efficient code. Overall, this addition is very straight-forward and something that LLVM badly needs.