443 lines · plain
1======================================2LLVM IR Undefined Behavior (UB) Manual3======================================4 5.. contents::6 :local:7 :depth: 28 9Abstract10========11This document describes the undefined behavior (UB) in LLVM's IR, including12undef and poison values, as well as the ``freeze`` instruction.13We also provide guidelines on when to use each form of UB.14 15 16Introduction17============18Undefined behavior (UB) is used to specify the behavior of corner cases for19which we don't wish to specify the concrete results. UB is also used to provide20additional constraints to the optimizers (e.g., assumptions that the frontend21guarantees through the language type system or the runtime).22For example, we could specify the result of division by zero as zero, but23since we are not really interested in the result, we say it is UB.24 25There exist two forms of undefined behavior in LLVM: immediate UB and deferred26UB. The latter comes in two flavors: undef and poison values.27There is also a ``freeze`` instruction to tame the propagation of deferred UB.28The lattice of values in LLVM is:29immediate UB > poison > undef > freeze(poison) > concrete value.30 31We explain each of the concepts in detail below.32 33 34Immediate UB35============36Immediate UB is the most severe form of UB. It should be avoided whenever37possible.38Immediate UB should be used only for operations that trap in most CPUs supported39by LLVM.40Examples include division by zero, dereferencing a null pointer, etc.41 42The reason that immediate UB should be avoided is that it makes optimizations43such as hoisting a lot harder.44Consider the following example:45 46.. code-block:: llvm47 48 define i32 @f(i1 %c, i32 %v) {49 br i1 %c, label %then, label %else50 51 then:52 %div = udiv i32 3, %v53 br label %ret54 55 else:56 br label %ret57 58 ret:59 %r = phi i32 [ %div, %then ], [ 0, %else ]60 ret i32 %r61 }62 63We might be tempted to simplify this function by removing the branching and64executing the division speculatively because ``%c`` is true most of times.65We would obtain the following IR:66 67.. code-block:: llvm68 69 define i32 @f(i1 %c, i32 %v) {70 %div = udiv i32 3, %v71 %r = select i1 %c, i32 %div, i32 072 ret i32 %r73 }74 75However, this transformation is not correct! Since division triggers UB76when the divisor is zero, we can only execute speculatively if we are sure we77don't hit that condition.78The function above, when called as ``f(false, 0)``, would return 0 before the79optimization, and triggers UB after being optimized.80 81This example highlights why we minimize the cases that trigger immediate UB82as much as possible.83As a rule of thumb, use immediate UB only for the cases that trap the CPU for84most of the supported architectures.85 86 87Time Travel88-----------89Immediate UB in LLVM IR allows the so-called time travelling. What this means90is that if a program triggers UB, then we are not required to preserve any of91its observable behavior, including I/O.92For example, the following function triggers UB after calling ``printf``:93 94.. code-block:: llvm95 96 define void @fn() {97 call void @printf(...) willreturn98 unreachable99 }100 101Since we know that ``printf`` will always return, and because LLVM's UB can102time-travel, it is legal to remove the call to ``printf`` altogether and103optimize the function to simply:104 105.. code-block:: llvm106 107 define void @fn() {108 unreachable109 }110 111 112Deferred UB113===========114Deferred UB is a lighter form of UB. It enables instructions to be executed115speculatively while marking some corner cases as having erroneous values.116Deferred UB should be used for cases where the semantics offered by common117CPUs differ, but the CPU does not trap.118 119As an example, consider the shift instructions. The x86 and ARM architectures120offer different semantics when the shift amount is equal to or greater than121the bitwidth.122We could solve this tension in one of two ways: 1) pick one of the x86/ARM123semantics for LLVM, which would make the code emitted for the other architecture124slower; 2) define that case as yielding ``poison``.125LLVM chose the latter option. For frontends for languages like C or C++126(e.g., clang), they can map shifts in the source program directly to a shift in127LLVM IR, since the semantics of C and C++ define such shifts as UB.128For languages that offer strong semantics, they must use the value of the shift129conditionally, e.g.:130 131.. code-block:: llvm132 133 define i32 @x86_shift(i32 %a, i32 %b) {134 %mask = and i32 %b, 31135 %shift = shl i32 %a, %mask136 ret i32 %shift137 }138 139 140There are two deferred UB values in LLVM: ``undef`` and ``poison``, which we141describe next.142 143 144Undef Values145------------146.. warning::147 Undef values are deprecated and should be used only when strictly necessary.148 Uses of undef values should be restricted to representing loads of149 uninitialized memory. This is the only part of the IR semantics that cannot150 be replaced with alternatives yet (work in ongoing).151 152An undef value represents any value of a given type. Moreover, each use of153an instruction that depends on undef can observe a different value.154For example:155 156.. code-block:: llvm157 158 define i32 @fn() {159 %add = add i32 undef, 0160 %ret = add i32 %add, %add161 ret i32 %ret162 }163 164Unsurprisingly, the first addition yields ``undef``.165However, the result of the second addition is more subtle. We might be tempted166to think that it yields an even number. But it might not be!167Since each (transitive) use of ``undef`` can observe a different value,168the second addition is equivalent to ``add i32 undef, undef``, which is169equivalent to ``undef``.170Hence, the function above is equivalent to:171 172.. code-block:: llvm173 174 define i32 @fn() {175 ret i32 undef176 }177 178Each call to this function may observe a different value, namely any 32-bit179number (even and odd).180 181Because each use of undef can observe a different value, some optimizations182are wrong if we are not sure a value is not undef.183Consider a function that multiplies a number by 2:184 185.. code-block:: llvm186 187 define i32 @fn(i32 %v) {188 %mul2 = mul i32 %v, 2189 ret i32 %mul2190 }191 192This function is guaranteed to return an even number, even if ``%v`` is193undef.194However, as we've seen above, the following function does not:195 196.. code-block:: llvm197 198 define i32 @fn(i32 %v) {199 %mul2 = add i32 %v, %v200 ret i32 %mul2201 }202 203This optimization is wrong just because undef values exist, even if they are204not used in this part of the program as LLVM has no way to tell if ``%v`` is205undef or not.206 207Looking at the value lattice, ``undef`` values can only be replaced with either208a ``freeze`` instruction or a concrete value.209A consequence is that giving undef as an operand to an instruction that triggers210UB for some values of that operand makes the program UB. For example,211``udiv %x, undef`` is UB since we replace undef with 0 (``udiv %x, 0``),212becoming obvious that it is UB.213 214 215Poison Values216-------------217Poison values are a stronger form of deferred UB than undef. They still218allow instructions to be executed speculatively, but they taint the whole219expression DAG (with some exceptions), akin to floating point NaN values.220 221Example:222 223.. code-block:: llvm224 225 define i32 @fn(i32 %a, i32 %b, i32 %c) {226 %add = add nsw i32 %a, %b227 %ret = add nsw i32 %add, %c228 ret i32 %ret229 }230 231The ``nsw`` attribute in the additions indicates that the operation yields232poison if there is a signed overflow.233If the first addition overflows, ``%add`` is poison and thus ``%ret`` is also234poison since it taints the whole expression DAG.235 236Poison values can be replaced with any value of type (undef, concrete values,237or a ``freeze`` instruction).238 239 240Propagation of Poison Through Select241------------------------------------242Most instructions return poison if any of their inputs is poison.243A notable exception is the ``select`` instruction, which is poison if and244only if the condition is poison or the selected value is poison.245This means that ``select`` acts as a barrier for poison propagation, which246impacts which optimizations can be performed.247 248For example, consider the following function:249 250.. code-block:: llvm251 252 define i1 @fn(i32 %x, i32 %y) {253 %cmp1 = icmp ne i32 %x, 0254 %cmp2 = icmp ugt i32 %x, %y255 %and = select i1 %cmp1, i1 %cmp2, i1 false256 ret i1 %and257 }258 259It is not correct to optimize the ``select`` into an ``and`` because when260``%cmp1`` is false, the ``select`` is only poison if ``%x`` is poison, while261the ``and`` below is poison if either ``%x`` or ``%y`` are poison.262 263.. code-block:: llvm264 265 define i1 @fn(i32 %x, i32 %y) {266 %cmp1 = icmp ne i32 %x, 0267 %cmp2 = icmp ugt i32 %x, %y268 %and = and i1 %cmp1, %cmp2 ;; poison if %x or %y are poison269 ret i1 %and270 }271 272However, the optimization is possible if all operands of the values are used in273the condition (notice the flipped operands in the ``select``):274 275.. code-block:: llvm276 277 define i1 @fn(i32 %x, i32 %y) {278 %cmp1 = icmp ne i32 %x, 0279 %cmp2 = icmp ugt i32 %x, %y280 %and = select i1 %cmp2, i1 %cmp1, i1 false281 ; ok to replace with:282 %and = and i1 %cmp1, %cmp2283 ret i1 %and284 }285 286 287The Freeze Instruction288======================289Both undef and poison values sometimes propagate too much down an expression290DAG. Undef values because each transitive use can observe a different value,291and poison values because they make the whole DAG poison.292There are some cases where it is important to stop such propagation.293This is where the ``freeze`` instruction comes in.294 295Take the following example function:296 297.. code-block:: llvm298 299 define i32 @fn(i32 %n, i1 %c) {300 entry:301 br label %loop302 303 loop:304 %i = phi i32 [ 0, %entry ], [ %i2, %loop.end ]305 %cond = icmp ule i32 %i, %n306 br i1 %cond, label %loop.cont, label %exit307 308 loop.cont:309 br i1 %c, label %then, label %else310 311 then:312 ...313 br label %loop.end314 315 else:316 ...317 br label %loop.end318 319 loop.end:320 %i2 = add i32 %i, 1321 br label %loop322 323 exit:324 ...325 }326 327Imagine we want to perform loop unswitching on the loop above since the branch328condition inside the loop is loop invariant.329We would obtain the following IR:330 331.. code-block:: llvm332 333 define i32 @fn(i32 %n, i1 %c) {334 entry:335 br i1 %c, label %then, label %else336 337 then:338 %i = phi i32 [ 0, %entry ], [ %i2, %then.cont ]339 %cond = icmp ule i32 %i, %n340 br i1 %cond, label %then.cont, label %exit341 342 then.cont:343 ...344 %i2 = add i32 %i, 1345 br label %then346 347 else:348 %i3 = phi i32 [ 0, %entry ], [ %i4, %else.cont ]349 %cond = icmp ule i32 %i3, %n350 br i1 %cond, label %else.cont, label %exit351 352 else.cont:353 ...354 %i4 = add i32 %i3, 1355 br label %else356 357 exit:358 ...359 }360 361There is a subtle catch: when the function is called with ``%n`` being zero,362the original function did not branch on ``%c``, while the optimized one does.363Branching on a deferred UB value is immediate UB, hence the transformation is364wrong in general because ``%c`` may be undef or poison.365 366Cases like this need a way to tame deferred UB values. This is exactly what the367``freeze`` instruction is for!368When given a concrete value as argument, ``freeze`` is a no-op, returning the369argument as-is. When given an undef or poison value, ``freeze`` returns a370non-deterministic value of the type.371This is not the same as undef: the value returned by ``freeze`` is the same372for all users.373 374Branching on a value returned by ``freeze`` is always safe since it either375evaluates to true or false consistently.376We can make the loop unswitching optimization above correct as follows:377 378.. code-block:: llvm379 380 define i32 @fn(i32 %n, i1 %c) {381 entry:382 %c2 = freeze i1 %c383 br i1 %c2, label %then, label %else384 ...385 }386 387 388Writing Tests Without Undefined Behavior389========================================390 391When writing tests, it is important to ensure that they don't trigger UB392unnecessarily. Some automated test reduces sometimes use undef or poison393values as dummy values, but this is considered a bad practice if this leads394to triggering UB.395 396For example, imagine that we want to write a test and we don't care about the397particular divisor value because our optimization kicks in regardless:398 399.. code-block:: llvm400 401 define i32 @fn(i8 %a) {402 %div = udiv i8 %a, poison403 ...404 }405 406The issue with this test is that it triggers immediate UB. This prevents407verification tools like Alive from validating the correctness of the408optimization. Hence, it is considered a bad practice to have tests with409unnecessary immediate UB (unless that is exactly what the test is for).410The test above should use a dummy function argument instead of using poison:411 412.. code-block:: llvm413 414 define i32 @fn(i8 %a, i8 %dummy) {415 %div = udiv i8 %a, %dummy416 ...417 }418 419Common sources of immediate UB in tests include branching on undef/poison420conditions and dereferencing undef/poison/null pointers.421 422.. note::423 If you need a placeholder value to pass as an argument to an instruction424 that may trigger UB, add a new argument to the function rather than using425 undef or poison.426 427 428Summary429=======430Undefined behavior (UB) in LLVM IR consists of two well-defined concepts:431immediate and deferred UB (undef and poison values).432Passing deferred UB values to certain operations leads to immediate UB.433This can be avoided in some cases through the use of the ``freeze``434instruction.435 436The lattice of values in LLVM is:437immediate UB > poison > undef > freeze(poison) > concrete value.438It is only valid to transform values from the left to the right (e.g., a poison439value can be replaced with a concrete value, but not the other way around).440 441Undef is now deprecated and should be used only to represent loads of442uninitialized memory.443