[Docs] Add LangRef documention for freeze instruction

[nlopes]

Summary

1. Describe the new freeze instruction
2. Make it explicit that branch on undef/poison is UB

[filcab]

LangRef.rst

8589 ↗

(On Diff #85724)

All uses of a '``freeze``' instruction are ...

would probably be less ambiguous. (uses of the same freeze instruction vs two freeze instructions on the same value)

[efriedma]

LangRef.rst

5408 ↗

(On Diff #85724)

Does "switch" need a similar amendment?

[majnemer]

LangRef.rst

5408 ↗

(On Diff #85724)

I think indirectbr would need it too.

[efriedma]

LangRef.rst

5408 ↗

(On Diff #85724)

indirectbr already says "All possible destination blocks must be listed in the label list, otherwise this instruction has undefined behavior", which implies that "indirectbr undef" is UB. Could be a bit more explicit, I guess.

[nlopes]

• rebase
• add UB semantics to indirectbr and switch

[filcab]

Please check the inconsistent quoting of keywords (which we already have in LangRef, but no need adding to it). Otherwise, no more nitpicking on my side :-)
Thanks.

LangRef.rst

5420 ↗

(On Diff #85871)

'``cond``'
```?
And maybe quote both undef and poison.

5472 ↗

(On Diff #85871)

Inconsistent quoting here too.

5539 ↗

(On Diff #85871)

And here.

[delcypher]

LangRef.rst

8598 ↗

(On Diff #85871)

Should probably say scalar integer type. It would also be a good idea to explain why this restriction is in place.

[lebedev.ri]

I'd think it would make sense to start with this patch in the series.
Needs rebasing, comments are not addressed.

LangRef.rst

8598 ↗

(On Diff #85871)

Not done.

[lebedev.ri]

reverse ping.

[nlopes]

Reflect comments & clarify immediate UB when branching on poison.

[lebedev.ri]

Looks good! Some thoughts.

llvm/docs/LangRef.rst

3110–3111

Should this section have something similar to the poison section, referencing freeze?

3306–3310

Should this mention freeze?

10181

I can see that the scalar restriction was lifter (good)
I think this misses 2 examples:

1. Some trivial vector example
2. An example for All uses of a 'freeze' instruction are guaranteed to always observe the same value.

[nlopes]

Updated with an example with vectors and add more references to freeze section.

[lebedev.ri]

llvm/docs/LangRef.rst

10159–10174

Either in Overview or in Semantics the undef and poison should be links to those langref sections.

10181

To clarify why i think there should be an example for All uses of a 'freeze' instruction are guaranteed to always observe the same value. - elsewhere it is specified that undef can 'evaluate' to a different value each time, and here we are contradicting that.

10183–10186

Could be as simple as:

diff
+%x2 = freeze i32 %w
+%z2 = add i32 %x, %x2 ; even number because all uses of %x and %x2 observe same value

[jdoerfert]

Two comments on the diff, the freeze part looks good to me.

llvm/docs/LangRef.rst

3214

I feel "even if 'undef'" reads as if there is a word missing.

3318

Why did we get rid of the side effect on poison is UB stuff here? In the absence of freeze this is still the case, isn't it?

[nlopes]

llvm/docs/LangRef.rst

3318

I'm not sure what the statement means. It doesn't seem to add extra useful information.

10183–10186

That is not correct. Only all uses of a given freeze instruction are guaranteed to have the same value.
Different freeze %x may yield different values.

[lebedev.ri]

llvm/docs/LangRef.rst

10173–10174

Can/should this be reworded then to avoid that misreading i just did?
I'd expect to see something closer to

All uses of a value returned from the same '``freeze``' instruction are
guaranteed to always observe the same value, but different '``freeze``'
instructions may yield different values.

10183–10186

Oh

[nlopes]

Made it explicit re one vs multiple calls to freeze.

[lebedev.ri]

Ok, this LG to me.
Would be good if someone else could also review.

[jdoerfert]

llvm/docs/LangRef.rst

3318

> I'm not sure what the statement means. It doesn't seem to add extra useful information.

1. Assuming it is not wrong, why remove it with this diff?
2. Is there some other location that specifies that a side effect depending on poison is UB?

[nlopes]

llvm/docs/LangRef.rst

3318

The statement as written is incorrect. That's the reason for removing a few lines from the example below as well.
Branching on poison is UB straight away, while this paragraph and the example suggest that it would only be poison if there were side-effecting operations in the destination BB. This semantics doesn't allow GVN to exist.
The paragraph before already mentions the interaction between instructions that trigger UB and poison.
Given these 2 statements (branch on poison, poison with UB-triggering instructions), I don't think there's anything else to cover. That's why I've removed it. Leaving stuff behind creates confusion, since it will otherwise create the idea that there are more cases that those 2 presented, but are left unspecified.
For example, I don't see any problem in printing a poison value. It will just print garbage, but it's not UB /per se/. It might be if the printing function branches on the value, for example.

It is important to cleanup the definition of poison so that people know when freeze is needed or not. The two concepts are very intermingled.

[lebedev.ri]

ping @jdoerfert

[jdoerfert]

LGTM, see my comment below.

llvm/docs/LangRef.rst

3318

I tried to find a case where it was not covered but failed, thus I agree with your assessment.

I would (have) prefer(red) these cleanup changes to be in a separate commit because they are not directly related to freeze.

[lebedev.ri]

@nlopes anything holding this patch? do you intend to land them all at once?
@aqjune I suppose D29011 should be the next one up for review..

[nlopes]

In D29121#1696095, @lebedev.ri wrote:

@nlopes anything holding this patch? do you intend to land them all at once?
@aqjune I suppose D29011 should be the next one up for review..

Yes, I would prefer if they would all land at once.

[lebedev.ri]

Should there be a constantexpr version of freeze?
Also, @nlopes, just to put a bold stop to this question - in the end,
we want freeze to be fully agnostic, it should not care *at all* what the type is, right?

[efriedma]

we want freeze to be fully agnostic, it should not care *at all* what the type is, right?

Well, it has to be some value which actually has bits that can be frozen. So integers, floats, pointers, vectors, arrays, and structs. Maybe worth listing out explicitly.

For pointers, we should probably mention the aliasing rules explicitly. It should be similar to null: the result can't be dereferenced. (See http://llvm.org/docs/LangRef.html#pointer-aliasing-rules .)

[nlopes]

Clarify semantics for pointers.

[reames]

LGTM w/minor entirely optional comments.

Personally, I'd prefer to see the addition of freeze land, then the optimizer fixes, then the changing of the branch being full UB wording, but I won't insist on that.

llvm/docs/LangRef.rst

3322

Suggested minor tweak to wording: integrate this as a bullet item into the previous list. (i.e. something like "* The condition operand to a branch, select. * The callee operand of a call or invoke.")

10177

I think this paragraph could be dropped. It's implied by the previous definition and oddly specific. Why does this particular implication deserve spelling out and not others?

[jdoerfert]

So this is not committed till we reviewed all of them?

[nlopes]

In D29121#1723978, @jdoerfert wrote:

So this is not committed till we reviewed all of them?

I'm just waiting on SelDAG->MIR patch to be done (https://reviews.llvm.org/D29014).
Then we have docs, SelDAG & MIR support. That seems the minimal to me (so the compiler won't crash when freeze is used). I agree the optimizer patches can land later.

[reames]

In D29121#1724593, @nlopes wrote:

In D29121#1723978, @jdoerfert wrote:

So this is not committed till we reviewed all of them?

I'm just waiting on SelDAG->MIR patch to be done (https://reviews.llvm.org/D29014).
Then we have docs, SelDAG & MIR support. That seems the minimal to me (so the compiler won't crash when freeze is used). I agree the optimizer patches can land later.

Can I suggest that we add a stub* ISEL implementation, land this, and then build on top of it?

• By which I mean a knowingly incorrect lowering to a simple COPY. It wouldn't fix *all* of our poison/undef problems, but it would allow us to make progress on some of the most painful IR ones while waiting for that patch to land.

[nlopes]

In D29121#1725727, @reames wrote:

In D29121#1724593, @nlopes wrote:

In D29121#1723978, @jdoerfert wrote:

So this is not committed till we reviewed all of them?

I'm just waiting on SelDAG->MIR patch to be done (https://reviews.llvm.org/D29014).
Then we have docs, SelDAG & MIR support. That seems the minimal to me (so the compiler won't crash when freeze is used). I agree the optimizer patches can land later.

Can I suggest that we add a stub* ISEL implementation, land this, and then build on top of it?

• By which I mean a knowingly incorrect lowering to a simple COPY. It wouldn't fix *all* of our poison/undef problems, but it would allow us to make progress on some of the most painful IR ones while waiting for that patch to land.

Makes sense. We are trying to get commit access to Juneyoung, but we were caught in the middle of the GitHub transition :) It's unclear what the procedure is now -- working on it.

[efriedma]

Updated developer policy is at https://github.com/llvm/llvm-project/blob/master/llvm/docs/DeveloperPolicy.rst . (Updating the website is currently broken.)

[RKSimon]

@nlopes This is failing on the llvm-sphinx-docs buildbot, please can you take a look? http://lab.llvm.org:8011/builders/llvm-sphinx-docs/builds/37793/steps/docs-llvm-html/logs/stdio

Warning, treated as error:
/home/buildbot/llvm-build-dir/llvm-sphinx-docs/llvm/src/llvm/docs/LangRef.rst:10243: WARNING: Could not lex literal_block as "llvm". Highlighting skipped.

[nlopes]

In D29121#1739974, @RKSimon wrote:

@nlopes This is failing on the llvm-sphinx-docs buildbot, please can you take a look? http://lab.llvm.org:8011/builders/llvm-sphinx-docs/builds/37793/steps/docs-llvm-html/logs/stdio

Warning, treated as error:
/home/buildbot/llvm-build-dir/llvm-sphinx-docs/llvm/src/llvm/docs/LangRef.rst:10243: WARNING: Could not lex literal_block as "llvm". Highlighting skipped.

I noticed, but when I run locally there were so many warnings that I couldn't get to this one.
I guess I'll just remove the code highlighting.
Thanks!

llvm/docs/LangRef.rst

 .. code-block:: llvm
 
     @X = global i32 17
     @Y = global i32 42
     @Z = global [2 x i32*] [ i32* @X, i32* @Y ]
 
 .. _undefvalues:
 
 Undefined Values
 ----------------
 
 The string '``undef``' can be used anywhere a constant is expected, and
 indicates that the user of the value may receive an unspecified
 bit-pattern. Undefined values may be of any type (other than '``label``'
 or '``void``') and be used anywhere a constant is permitted.
 
 Undefined values are useful because they indicate to the compiler that
 the program is well defined no matter what value is used. This gives the

 short answer is that an '``undef``' "variable" can arbitrarily change
 its value over its "live range". This is true because the variable
 doesn't actually *have a live range*. Instead, the value is logically
 read from arbitrary registers that happen to be around when needed, so
 the value is not necessarily consistent over time. In fact, ``%A`` and
 ``%C`` need to have the same semantics or the core LLVM "replace all
 uses with" concept would not hold.
 
+To ensure all uses of a given register observe the same value (even if
+'``undef``'), the :ref:`freeze instruction <i_freeze>` can be used.
+
 .. code-block:: llvm
 
       %A = sdiv undef, %X
       %B = sdiv %X, undef
     Safe:
       %A = 0
     b: unreachable
 
-  An instruction *control-depends* on a :ref:`terminator
    control transfers to one of the successors, and may not be executed
    when control is transferred to another.
 -  Additionally, an instruction also *control-depends* on a terminator
    instruction if the set of instructions it otherwise depends on would
    be different if the terminator had transferred control to a different
    successor.
 -  Dependence is transitive.
 
 An instruction that *depends* on a poison value, produces a poison value
 itself. A poison value may be relaxed into an
 :ref:`undef value <undefvalues>`, which takes an arbitrary bit-pattern.
+Propagation of poison can be stopped with the
+:ref:`freeze instruction <i_freeze>`.
 
 This means that immediate undefined behavior occurs if a poison value is
 used as an instruction operand that has any values that trigger undefined
 behavior. Notably this includes (but is not limited to):
 
 -  The pointer operand of a :ref:`load <i_load>`, :ref:`store <i_store>` or
    any other pointer dereferencing instruction (independent of address
    space).
 -  The divisor operand of a ``udiv``, ``sdiv``, ``urem`` or ``srem``
    instruction.
 
-Additionally, undefined behavior occurs if a side effect *depends* on poison.
-This includes side effects that are control dependent on a poisoned branch.
+Additionally, undefined behavior occurs when branching on a poison value.
 
 Here are some examples:
 
 .. code-block:: llvm
 
     entry:
       %poison = sub nuw i32 0, 1           ; Results in a poison value.
       %still_poison = and i32 %poison, 0   ; 0, but also poison.
       %poison_yet_again = getelementptr i32, i32* @h, i32 %still_poison
       store i32 0, i32* %poison_yet_again  ; Undefined behavior due to
                                            ; store to poison.
 
       store i32 %poison, i32* @g           ; Poison value stored to memory.
       %poison2 = load i32, i32* @g         ; Poison value loaded back from memory.
 
       %narrowaddr = bitcast i32* @g to i16*
       %wideaddr = bitcast i32* @g to i64*
       %poison3 = load i16, i16* %narrowaddr ; Returns a poison value.
-      %poison4 = load i64, i64* %wideaddr  ; Returns a poison value.
+      %poison4 = load i64, i64* %wideaddr   ; Returns a poison value.
 
       %cmp = icmp slt i32 %poison, 0       ; Returns a poison value.
-      br i1 %cmp, label %true, label %end  ; Branch to either destination.
-
-    true:
-      store volatile i32 0, i32* @g        ; This is control-dependent on %cmp, so
-                                           ; it has undefined behavior.
-      br label %end
+      br i1 %cmp, label %end, label %end   ; undefined behavior
 
     end:
-      %p = phi i32 [ 0, %entry ], [ 1, %true ]
-                                           ; Both edges into this PHI are
-                                           ; control-dependent on %cmp, so this
-                                           ; always results in a poison value.
-
-      store volatile i32 0, i32* @g        ; This would depend on the store in %true
-                                           ; if %cmp is true, or the store in %entry
-                                           ; otherwise, so this is undefined behavior.
-
-      br i1 %cmp, label %second_true, label %second_end
-                                           ; The same branch again, but this time the
-                                           ; true block doesn't have side effects.
-
-    second_true:
-      ; No side effects!
-      ret void
-
-    second_end:
-      store volatile i32 0, i32* @g        ; This time, the instruction always depends
-                                           ; on the store in %end. Also, it is
-                                           ; control-equivalent to %end, so this is
-                                           ; well-defined (ignoring earlier undefined
-                                           ; behavior in this example).
 
 .. _blockaddress:
 
 Addresses of Basic Blocks
 -------------------------
 
 ``blockaddress(@function, %block)``
 

 
 Semantics:
 """"""""""
 
 Upon execution of a conditional '``br``' instruction, the '``i1``'
 argument is evaluated. If the value is ``true``, control flows to the
 '``iftrue``' ``label`` argument. If "cond" is ``false``, control flows
 to the '``iffalse``' ``label`` argument.
+If '``cond``' is ``poison``, this instruction has undefined behavior.
 
 Example:
 """"""""
 
 .. code-block:: llvm
 
     Test:
       %cond = icmp eq i32 %a, %b

 Semantics:
 """"""""""
 
 The ``switch`` instruction specifies a table of values and destinations.
 When the '``switch``' instruction is executed, this table is searched
 for the given value. If the value is found, control flow is transferred
 to the corresponding destination; otherwise, control flow is transferred
 to the default destination.
+If '``value``' is ``poison``, this instruction has undefined behavior.
 
 Implementation:
 """""""""""""""
 
 Depending on properties of the target machine and the particular
 ``switch`` instruction, this instruction may be code generated in
 different ways. For example, it could be generated as a series of
 chained conditional branches or with a lookup table.

 
 Semantics:
 """"""""""
 
 Control transfers to the block specified in the address argument. All
 possible destination blocks must be listed in the label list, otherwise
 this instruction has undefined behavior. This implies that jumps to
 labels defined in other functions have undefined behavior as well.
+If '``address``' is ``poison``, this instruction has undefined behavior.
 
 Implementation:
 """""""""""""""
 
 This is typically implemented with a jump through a register.
 
 Example:
 """"""""

 
 Example:
 """"""""
 
 .. code-block:: llvm
 
       %X = select i1 true, i8 17, i8 42          ; yields i8:17
 
+
+.. _i_freeze:
+
+'``freeze``' Instruction
+^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+::
+
+      <result> = freeze ty <val>    ; yields ty:result
+
+Overview:
+"""""""""
+
+The '``freeze``' instruction is used to stop propagation of ``undef``
+and ``poison`` values.
+
+Arguments:
+""""""""""
+
+The '``freeze``' instruction takes a single argument.
+
+Semantics:
+""""""""""
+
+If the argument is ``undef`` or ``poison``, '``freeze``' returns an
+arbitrary, but fixed, value of type '``ty``'.
+Otherwise, this instruction is a no-op and returns the input argument.
+All uses of a '``freeze``' instruction are guaranteed to always observe
+the same value.
+
+
+Example:
+""""""""
+
+.. code-block:: llvm
+
+      %w = i32 undef
+      %x = freeze i32 %w
+      %y = add i32 %w, %w      ; undef
+      %z = add i32 %x, %x      ; even number because all uses of %x observe
+                               ; the same value
+
+      ; example with vectors
+      %v = <2 x i32> <i32 undef, i32 poison>
+      %a = extractelement <2 x i32> %v, i32 0    ; undef
+      %b = extractelement <2 x i32> %v, i32 1    ; poison
+      %add = add i32 %a, %a                      ; undef
+
+      %v.fr = freeze <2 x i32> %v                ; element-wise freeze
+      %d = extractelement <2 x i32> %v.fr, i32 0 ; not undef
+      %add.f = add i32 %d, %d                    ; even number
+
+      ; branching on frozen value
+      %poison = add nsw i1 %k, undef   ; poison
+      %c = freeze i1 %poison
+      br i1 %c, label %foo, label %bar ; non-deterministic branch to %foo or %bar
+
+
 .. _i_call:
 
 '``call``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""