[IR] Add Freeze instruction

[aqjune]

Summary

• Define Instruction::Freeze, let it be UnaryOperator
• Add support for freeze to LLLexer/LLParser/BitcodeReader/BitcodeWriter The format is %x = freeze <ty> %v
• Add support for freeze instruction to llvm-c interface.
• Add m_Freeze in PatternMatch.
• Erase freeze when lowering IR to SelDag.

[xbolva00]

Ping

[aqjune]

Rebase to trunk@369887 (August 26th, 2019)

[lebedev.ri]

Thank you for working on this! This needs more cleanup.
Since the patch was initially posted, and Unary operator type was added to LLVM.
In last patch's update many parts of the patch were correctly migrated, but not all.
See D53877 for the list of potential places, i tried to point out most of them inline.

include/llvm-c/Core.h

144 ↗

(On Diff #217187)

unrelated

include/llvm/Bitcode/LLVMBitCodes.h

394–395 ↗

(On Diff #217187)

Did you mean to put freeze as an unary instruction instead of a function?

559 ↗

(On Diff #217187)

Wouldn't basing it on unary op work?

include/llvm/CodeGen/GlobalISel/IRTranslator.h

487 ↗

(On Diff #217187)

Is this a correctness issue?
Or does returning false here results in IRTranslator "aborting"?

include/llvm/IR/IRBuilder.h

2358 ↗

(On Diff #217187)

I personally have mild preference for the ::Create; not sure if this is a remark or review note.

include/llvm/IR/InstVisitor.h

202 ↗

(On Diff #217187)

Should you delegate to UnaryInstruction instead?

lib/AsmParser/LLParser.cpp

6739 ↗

(On Diff #217187)

Needs updating to match langref - vectors; floating point support?

lib/IR/Verifier.cpp

3964–3965 ↗

(On Diff #217187)

Needs updating to match langref - vectors; floating point support?

[kristof.beyls]

Given this seems to add a new IR instruction, shouldn't there also be good quality documentation for this new instruction in docs/LangRef.rst?

[lebedev.ri]

In D29011#1696898, @kristof.beyls wrote:

Given this seems to add a new IR instruction, shouldn't there also be good quality documentation for this new instruction in docs/LangRef.rst?

See D29121

[aqjune]

Updated the patch so UnaryOperator is used for Instruction::Freeze op.
Currently I see an error from Phabricator while uploading a new diff:

Unhandled Exception ("PhabricatorFileUploadException")	
Unable to write file: failed to write to temporary directory.

I'll retry uploading it later.

include/llvm/CodeGen/GlobalISel/IRTranslator.h

487 ↗

(On Diff #217187)

Yep, returning false makes it abort, if my understanding is correct.

[lebedev.ri]

Thanks, this looks about right.
I'm not sure about backend part of this patch, but that is likely okay.
Two main questions: should there be a constantexpr freeze, and should freeze be fully type-agnostic, like it is stated in D29121?

include/llvm/CodeGen/GlobalISel/IRTranslator.h

487 ↗

(On Diff #217187)

Okay.

lib/AsmParser/LLParser.cpp

3407–3430 ↗

(On Diff #223461)

Should there be constantexpr version of freeze?

6317–6338 ↗

(On Diff #223461)

I see no restrictions on the type to freeze in D29121,
so i think you just don't want any checking for freeze here.
And existing ParseUnaryOp is only called with /*IsFP*/true to parse fneg.
So let's change this to

bool Valid = !IsFPOnly || LHS->getType()->isFPOrFPVectorTy();

?

lib/Bitcode/Writer/BitcodeWriter.cpp

2448–2457 ↗

(On Diff #223461)

What about constantexpr freeze?

lib/IR/Instructions.cpp

2240–2242 ↗

(On Diff #223461)

I'm not seeing this restriction in D29121

lib/IR/Verifier.cpp

3141–3144 ↗

(On Diff #223461)

I'm not seeing this restriction in D29121

[aqjune]

should there be a constantexpr freeze

Yep, constantexpr freeze makes sense, as freeze is a scalar operation (like fneg). :)

and should freeze be fully type-agnostic, like it is stated in D29121?

I think this is a hard question, especially due to the existence of the undef pointer.
A pointer value tracks which memory block it is pointing to. If freeze i8* undef is defined to yield a random pointer to any pre-defined memory block, this will limit free moving of freeze, e.g:

p = malloc() // p is created
ptr0 = freeze i8* undef // ptr0 can point to block p
=>
ptr0 = freeze i8* undef // ptr0 can't point to block p, because p is not allocated yet
p = malloc()

[lebedev.ri]

In D29011#1697170, @aqjune wrote:

should there be a constantexpr freeze

Yep, constantexpr freeze makes sense, as freeze is a scalar operation (like fneg). :)

See inline comments then :)

and should freeze be fully type-agnostic, like it is stated in D29121?

I think this is a hard question, especially due to the existence of the undef pointer.
A pointer value tracks which memory block it is pointing to. If freeze i8* undef is defined to yield a random pointer to any pre-defined memory block, this will limit free moving of freeze, e.g:

p = malloc() // p is created
ptr0 = freeze i8* undef // ptr0 can point to block p
=>
ptr0 = freeze i8* undef // ptr0 can't point to block p, because p is not allocated yet
p = malloc()

I guess D29121 needs to explicitly single-out the pointers then.

[lebedev.ri]

(marking as reviewed as per previous comments - constantexpr, typechecking inconsistent with langref)

[aqjune]

• Support freeze constexpr
• Make freeze's type checking consistent with LangRef.

[jdoerfert]

Two minor comments from my side.

(I would like someone to include the keyword in the editor lists llvm/utils/{emacs,vim} after this landed)

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

671 ↗

(On Diff #224745)

The lady of the lake says this should be:

`void visitFreeze(const User &I) { visitUnary(I, ISD::FREEZE); }`

If you have reason not to do it this way, also replace visitUnrary with visitFNeg, though I'd prefer not to.

test/Bindings/llvm-c/freeze.ll

12 ↗

(On Diff #224745)

Missing types, here and elsewhere I think:

• array
• struct w/ definition
• struct w/o definition (opaque)
• non-standard integer size (i666)

Missing inputs:

• undef
• null

[lebedev.ri]

In D29011#1707274, @jdoerfert wrote:

Two minor comments from my side.

Looks good to me with those two fixed.
Should you add llvm::Freze here by inheriting from UnaryOperator to make isa<Freze>(Op) possible?

(I would like someone to include the keyword in the editor lists llvm/utils/{emacs,vim} after this landed)

There is also llvm/utils/{kate}.

include/llvm/Bitcode/LLVMBitCodes.h

394 ↗

(On Diff #224745)

I think you want to rebase.

[aqjune]

In D29011#1707278, @lebedev.ri wrote:

Should you add llvm::Freeze here by inheriting from UnaryOperator to make isa<Freeze>(Op) possible?

Couldn't you kindly point which place is good to update?

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

671 ↗

(On Diff #224745)

ISD::FREEZE will be added in the next patch - https://reviews.llvm.org/D29014 .
Do you want to move the definition of ISD::FREEZE to this patch? @lebedev.ri

[lebedev.ri]

In D29011#1707396, @aqjune wrote:

In D29011#1707278, @lebedev.ri wrote:

Should you add llvm::Freeze here by inheriting from UnaryOperator to make isa<Freeze>(Op) possible?

Couldn't you kindly point which place is good to update?

Right after where the llvm::UnaryOperator is defined in llvm/include/llvm/IR/InstrTypes.h i think.
See OverflowingBinaryOperator for an example.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

671 ↗

(On Diff #224745)

Oh good point, let's leave as is.

[aqjune]

• Rebase
• Add more tests to freeze.ll
• Define FreezeOperator

[aqjune]

include/llvm/IR/Operator.h

594 ↗

(On Diff #224771)

I added FreezeOperator here, as other operators including OverflowingBinaryOperator were in this file.

test/Bindings/llvm-c/freeze.ll

12 ↗

(On Diff #224745)

I found that freeze i8* null raised an error due to a bug in tools/llvm-c-test/echo.cpp:

// Try null
if (LLVMIsNull(Cst)) {
  check_value_kind(Cst, LLVMConstantTokenNoneValueKind);
  LLVMTypeRef Ty = TypeCloner(M).Clone(Cst);
  return LLVMConstNull(Ty);
}

Here, Cst can not only be LLVMConstantTokenNoneValueKind but also LLVMConstantPointerNullValueKind.
I'll make a separate patch that resolves this error, then I'll be able to add freeze i8* null test.

[lebedev.ri]

Thanks, LG.
Anyone else has any comments here?

include/llvm/IR/PatternMatch.h

830–834 ↗

(On Diff #224771)

Let's use FreezeOperator here then?

[aqjune]

• Use FreezeOperator inside Freeze_match

[lebedev.ri]

In line with a few recent reverts, is this missing anything for ocaml binding?
(does it compile with ocaml binding enabled and do all tests still pass?)

[jdoerfert]

Fwiw, I'm OK with this (given that we have my requested changes in upcoming commits).

[jdoerfert]

In D29011#1708103, @lebedev.ri wrote:

In line with a few recent reverts, is this missing anything for ocaml binding?
(does it compile with ocaml binding enabled and do all tests still pass?)

Like D61675 ;)

[aqjune]

Sorry, I've been busy recently.

make check-llvm-bindings-ocaml wasn't raising error, but I added tests for freeze to core.ml because it is good to have the tests.

BTW, make check raises an error at test/Transforms/MergeFunc/inline-asm.ll because the output has function definitions reordered - what is the best way to resolve this? I attached the input/output .ll files.

inline-asm.tar.gz633 BDownload

[craig.topper]

Sorry to come to this late, but does it really make sense for Freeze to be inherited from UnaryOperator? UnaryOperator in my mind is like BinaryOperator which is for arithmetic operations. Freeze is different. The fact that it made sense to add a FreezeOperator hints at that. Should we instead just have a FreezeInst separate from UnaryOperator instead of FreezeOperator?

[aqjune]

In D29011#1733572, @craig.topper wrote:

Sorry to come to this late, but does it really make sense for Freeze to be inherited from UnaryOperator? UnaryOperator in my mind is like BinaryOperator which is for arithmetic operations. Freeze is different. The fact that it made sense to add a FreezeOperator hints at that. Should we instead just have a FreezeInst separate from UnaryOperator instead of FreezeOperator?

My understanding of UnaryOperator was that it is a scalar operation that has same input and output type according to the LangRef, so I thought freeze could be categorized into it.
Implementing freeze by inheriting UnaryOperator was straightforward; I did not have to specify instruction's properties, adding it to constexpr was easy, etc. I believe having it inherit UnaryOperator would be good for maintenance, but other than this I have no strong reason for this.
About the FreezeOperator, I think it is natural to have operators in Operator.h that has special purposes: it also has AddOperator / SubOperator / etc defined.

[craig.topper]

Does a ConstantExpr freeze really make sense? ConstantExprs are uniqued by the LLVMContext. So every constantexpr that has the same input ends up being the same object. Do we want that behavior do we need each freeze to be distinct?

[aqjune]

In D29011#1735007, @craig.topper wrote:

Does a ConstantExpr freeze really make sense? ConstantExprs are uniqued by the LLVMContext. So every constantexpr that has the same input ends up being the same object. Do we want that behavior do we need each freeze to be distinct?

Both semantics make sense, and I was thinking of returning the same value for same expression of freeze, because it explains copy of an instruction that has freeze constexpr as an operand.
Conceptually, we can say that freeze constexpr is evaluated at the beginning of a program, and the evaluated value is globally used inside the module.
Using this semantics, freeze constexprs should be carefully optimized, so the same freeze constexprs don't diverge into different expressions.
This is the difference from other constexprs, but I guess binary operator also has a similar diverged case, which is udiv/sdiv constexpr (that made constexpr may trap), but I have to say that having such difference isn't said to be a good idea.
What do you think?

[nlopes]

In D29011#1735007, @craig.topper wrote:

Does a ConstantExpr freeze really make sense? ConstantExprs are uniqued by the LLVMContext. So every constantexpr that has the same input ends up being the same object. Do we want that behavior do we need each freeze to be distinct?

Juneyoung and I have discussed this today.
The conclusion was that we don't see a use-case for a freeze ConstantExpr and therefore we agree that it should be removed. Also, the semantics and implementation would be tricky as you suggest. @aqjune will submit a new patch to change Freeze from being a UnaryOp to just an op on its own.

[aqjune]

The new patch is here: https://reviews.llvm.org/D69932