This is an archive of the discontinued LLVM Phabricator instance.

[IR] Add Freeze instruction
ClosedPublic

Authored by aqjune on Jan 23 2017, 3:42 AM.

Details

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.

Diff Detail

Event Timeline

aqjune created this revision.Jan 23 2017, 3:42 AM
aqjune removed a subscriber: mehdi_amini.
aqjune added a subscriber: llvm-commits.

Hi,

Could you add a test case for the C API ? You can do so using the echo facility of llvm-c-test. See for instance: https://reviews.llvm.org/diffusion/L/browse/llvm/trunk/test/Bindings/llvm-c/atomics.ll

include/llvm-c/Core.h
3028

nit: please align the Name parameter properly.

nlopes added a subscriber: nlopes.Jan 24 2017, 1:08 AM
aqjune updated this revision to Diff 85541.Jan 24 2017, 1:46 AM
  • Add llvm-c test (test/Bindings/llvm-c/freeze.ll)
  • Update tools/llvm-c-test/echo.cpp so it can deal with Freeze instruction.
deadalnix edited edge metadata.Jan 24 2017, 3:29 AM

Awesome, as far as the C API goes, this is good. I'll let other the time to review everything else.

filcab added a subscriber: filcab.Jan 24 2017, 7:37 AM

Just some minor nits.
You're adding some functions which will never be called. It might be easier to hold them off until the next patch (and have this one only add the instruction + necessary plumbing), or to at least post a follow-up patch on phabricator which shows usage for those functions, as that makes it easier to know it shouldn't be dead code for long.

include/llvm/IR/IRBuilder.h
1713

Maybe omit the \brief?

1715

This is not being used. Maybe submit in a later patch, with a use for it?

include/llvm/IR/Instructions.h
5064

undef?

include/llvm/IR/PatternMatch.h
931

Minor nit: Unsure if the usual pattern matching policy is to add the pattern only when you need it on when adding the instruction.

lib/Analysis/ValueTracking.cpp
3917 ↗(On Diff #85541)

If we're just doing ConstantInt for now, why not just use the inner if (same for the FreezeInst)? Then change it after adding more, if the code ends up being too complex or has too many repeated tests.
No need to add a comment stating what an if (isa...) return is doing.
Is there a plan for adding constants, etc? Maybe add a TODO tag here, so it jumps out if someone is grepping for those.

lib/AsmParser/LLParser.cpp
5914

Please test this error.

5916

Omit the , "" since it's the default arg anyway.

lib/Bitcode/Reader/BitcodeReader.cpp
4350

Omit the , "".

filcab added inline comments.Jan 24 2017, 10:37 AM
lib/AsmParser/LLParser.cpp
5914

Even better: Should this be in the verifier only? Otherwise you're checking for the same thing in two places, which is easy to get out of sync. (Would still require a test)

majnemer added inline comments.Jan 24 2017, 10:41 AM
lib/AsmParser/LLParser.cpp
5914

its not bad for them to be in both, the error messages are much nicer in the parser.

vsk added a subscriber: vsk.Jan 24 2017, 10:42 PM

Please move the bitcode round-trip in test/Bitcode/freeze.ll to test/Bitcode/compatibility.ll. This lets us test bitcode backwards-compatibility.

aqjune updated this revision to Diff 85760.Jan 25 2017, 8:26 AM
  • Modify typos, add more comments (including TODOs)
  • Add tests for parsing error
  • Moved test/Bitcode/freeze.ll to test/Bitcode/compatibility.ll.
aqjune marked 5 inline comments as done.Jan 26 2017, 1:28 AM
aqjune added inline comments.
include/llvm/IR/IRBuilder.h
1715

Hello. Thanks for your comment.
This function is going to be used in https://reviews.llvm.org/D29016, and this patch is important because it may reduce the number of unnecessarily inserted freezes.

include/llvm/IR/PatternMatch.h
931

You're right - it is not used right now.
However every other values has its own match function currently, so I just followed convention..
If you think this is redundant now, I'll erase this.

lib/Analysis/ValueTracking.cpp
3917 ↗(On Diff #85760)

There's no plan to add other cases now.
I added TODOs, as you recommended.

lib/AsmParser/LLParser.cpp
5914

I added 3 test cases which checks whether this error message is printed out.

5916

I removed the second argument.

filcab added inline comments.Jan 27 2017, 6:51 AM
include/llvm/IR/IRBuilder.h
1715

That patch seems to have no instance of CreateFreezeAtDef. It's better to only add this function when it's going to be used.

include/llvm/IR/PatternMatch.h
931

It's a minor nit. I'm ok with this being added now with the rest of the instruction stuff.

lib/Analysis/ValueTracking.cpp
3901 ↗(On Diff #85760)

This function is unused.

3917 ↗(On Diff #85760)

Maybe this?

// TODO: Deal with other Constant subclasses.
if (isa<ConstantInt>(C))
  return true;

return false;

I don't think the outer if is buying you anything for now. Anyone who adds more can deal with avoiding testing the same thing twice.
(we can even return isa<...>...;, but keeping the "itemization"-like code doesn't seem bad in my view).

lib/Bitcode/Reader/BitcodeReader.cpp
4350

If you don't test for an integer type, this will generate invalid IR. It's also not consistent with the parser.

lib/IR/Verifier.cpp
3654

Please add a test to unittests/IR/VerifierTest.cpp

test/Bitcode/freeze-vector.ll
4

No need to name the LINE variable. But you should be matching to make sure we get the correct line.
Something like (using the automatic @LINE variable):

CHECK: freeze-vector.ll:[[@LINE+2]]: ```...
The same for the other tests.
regehr added a subscriber: regehr.Jan 28 2017, 10:03 PM
aqjune updated this revision to Diff 86250.Jan 30 2017, 12:11 AM
aqjune marked 4 inline comments as done.Jan 30 2017, 12:19 AM
aqjune added inline comments.
include/llvm/IR/IRBuilder.h
1715

Oh, sorry, the patch was https://reviews.llvm.org/D29015 , not https://reviews.llvm.org/D29016.
I moved the CreateFreezeAtDef to https://reviews.llvm.org/D29015.

aqjune added inline comments.Jan 30 2017, 12:20 AM
include/llvm/IR/IRBuilder.h
1713

@filcab Other functions also have \brief , so I followed the convention.

filcab added a comment.Feb 2 2017, 9:19 AM

Looks good on my end. But please wait for someone more familiar with IR to chime in and LGTM, since I'm not sure of all places that need to be changed when adding instructions.

include/llvm/IR/IRBuilder.h
1713

Consistency is ok by me. If we ever convert these, we can do it on all at once.

@filcab Thanks for your comments.

spatel added a subscriber: spatel.May 22 2017, 2:00 PM
aqjune updated this revision to Diff 106873.Jul 17 2017, 8:04 AM

Rebased to svn commit 308173

delcypher added inline comments.Aug 10 2017, 12:19 AM
lib/AsmParser/LLParser.cpp
5914

@aqjune What's the motivation to restricting the freeze instruction to scalar integers?

For vector SSA registers that contain integers that we want to "freeze" this would force doing constructing a new vector by use of extractelement, freeze on the each scalar element and then insertelement to construct the new register. This seems a bit cumbersome.

I presume the reason for not allowing floating point operands is that none of the floating point instructions are supposed to produce poison? However consider the load instruction. That could load poisoned memory and the type could be a floating point type. There's an example of a poisoned load in the IR language reference ( https://llvm.org/docs/LangRef.html#poison-values ).

nlopes added inline comments.Aug 10 2017, 3:51 AM
lib/AsmParser/LLParser.cpp
5914

You're right that in the future it may be useful to freeze vectors of integers, at least.
This is just the first version of the patch. The intent was to fix loop unswitch, which doesn't require freezing vectors yet. As uses expand we can relax the condition.
We definitely didn't want to freeze floats; I don't know yet if that's needed or what does it mean.

delcypher added inline comments.Aug 13 2017, 4:33 AM
lib/AsmParser/LLParser.cpp
5914

Thanks for clarifying. I see the instruction is documented in https://reviews.llvm.org/D29121 so I left a minor comment there about this.

espindola edited reviewers, added: espindola; removed: rafael.Mar 15 2018, 9:48 AM
aqjune updated this revision to Diff 145376.May 5 2018, 11:00 AM

Rebased to svn commit 331585

aqjune updated this revision to Diff 217187.Aug 26 2019, 10:13 AM

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

lebedev.ri requested changes to this revision.Oct 5 2019, 6:23 AM
lebedev.ri added a subscriber: 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
137–140

unrelated

include/llvm/Bitcode/LLVMBitCodes.h
312–313

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

464–466

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
1694

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

include/llvm/IR/InstVisitor.h
209

Should you delegate to UnaryInstruction instead?

lib/AsmParser/LLParser.cpp
5913

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

lib/IR/Verifier.cpp
3655–3656

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

This revision now requires changes to proceed.Oct 5 2019, 6:23 AM

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?

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 marked 9 inline comments as done.Oct 7 2019, 2:26 AM

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.

aqjune updated this revision to Diff 223461.Oct 7 2019, 2:45 AM
aqjune marked an inline comment as done.
aqjune edited the summary of this revision. (Show Details)
lebedev.ri marked an inline comment as done.Oct 7 2019, 4:01 AM

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
3041–3042

Should there be constantexpr version of freeze?

5610–5611

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
2294–2295

What about constantexpr freeze?

lib/IR/Instructions.cpp
1986–1988

I'm not seeing this restriction in D29121

lib/IR/Verifier.cpp
2842–2845

I'm not seeing this restriction in D29121

aqjune added a comment.Oct 7 2019, 4:25 AM

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()

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 requested changes to this revision.EditedOct 8 2019, 12:57 PM

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

This revision now requires changes to proceed.Oct 8 2019, 12:58 PM
aqjune updated this revision to Diff 224745.Oct 12 2019, 8:24 AM
aqjune marked 3 inline comments as done.
  • Support freeze constexpr
  • Make freeze's type checking consistent with LangRef.
aqjune marked 2 inline comments as done.Oct 12 2019, 8:26 AM

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
826

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
13

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

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
312–313

I think you want to rebase.

aqjune marked an inline comment as done.Oct 12 2019, 9:59 PM

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
826

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 marked an inline comment as done.Oct 13 2019, 12:07 AM

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
826

Oh good point, let's leave as is.

aqjune updated this revision to Diff 224771.Oct 13 2019, 1:15 AM
  • Rebase
  • Add more tests to freeze.ll
  • Define FreezeOperator
aqjune marked 2 inline comments as done.Oct 13 2019, 1:18 AM
aqjune added inline comments.
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
13

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 accepted this revision.Oct 13 2019, 1:30 AM

Thanks, LG.
Anyone else has any comments here?

include/llvm/IR/PatternMatch.h
462–466

Let's use FreezeOperator here then?

This revision is now accepted and ready to land.Oct 13 2019, 1:30 AM
aqjune updated this revision to Diff 224778.Oct 13 2019, 4:25 AM
  • Use FreezeOperator inside Freeze_match
aqjune marked an inline comment as done.Oct 13 2019, 4:26 AM

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 accepted this revision.Oct 14 2019, 8:52 AM

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

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 updated this revision to Diff 225825.Oct 21 2019, 12:15 AM
aqjune edited the summary of this revision. (Show Details)

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.

This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptNov 4 2019, 11:00 PM

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 added a comment.Nov 5 2019, 7:47 PM

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.

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 added a comment.EditedNov 5 2019, 11:56 PM

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 added a comment.Nov 6 2019, 2:40 AM

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.