[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

8606

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

5421

Does "switch" need a similar amendment?

[majnemer]

LangRef.rst

5421

I think indirectbr would need it too.

[efriedma]

LangRef.rst

5421

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

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

5472

Inconsistent quoting here too.

5539

And here.

[delcypher]

LangRef.rst

8598

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

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 ↗

(On Diff #220296)

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

3303–3305 ↗

(On Diff #220296)

Should this mention freeze?

10176 ↗

(On Diff #220296)

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 ↗

(On Diff #220306)

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

10183–10186 ↗

(On Diff #220306)

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

10176 ↗

(On Diff #220296)

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.

[jdoerfert]

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

llvm/docs/LangRef.rst

3214 ↗

(On Diff #220306)

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

3318 ↗

(On Diff #220306)

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 ↗

(On Diff #220306)

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

10183–10186 ↗

(On Diff #220306)

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 ↗

(On Diff #220306)

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 ↗

(On Diff #220306)

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 ↗

(On Diff #220306)

> 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 ↗

(On Diff #220306)

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 ↗

(On Diff #220306)

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

3323 ↗

(On Diff #223673)

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.")

10187 ↗

(On Diff #223673)

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!

LangRef.rst

entry:
       store volatile i32 %poison, i32* @g  ; External observation; undefined behavior.
 
       %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.
 
       %cmp = icmp slt i32 %poison, 0       ; Returns a poison value.
-      br i1 %cmp, label %true, label %end  ; Branch to either destination.
+      br i1 %cmp, label %true, label %end  ; undefined behavior
 
     true:
       store volatile i32 0, i32* @g        ; This is control-dependent on %cmp, so
                                            ; it has undefined behavior.
       br label %end
 
     end:
       %p = phi i32 [ 0, %entry ], [ 1, %true ]

 
 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 either ``undef`` or ``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 either ``undef`` or ``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 either ``undef`` or ``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, which is currently
+required to be of integer type.
+
+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
+
+      %cmp.fr = freeze i1 undef
+      br i1 %cmp.fr, label %foo, label %bar ; non-deterministic branch to %foo or %bar
+
+
 .. _i_call:
 
 '``call``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""