Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[WIP] Introduce floats canonicalize, min, max intrinsics etc. #4559

Closed

Conversation

akzhan
Copy link
Contributor

@akzhan akzhan commented Jun 13, 2017

See http://llvm.org/docs/LangRef.html#llvm-canonicalize-intrinsic for details.

It is first step to rework Floats hashing.

@asterite
Copy link
Member

Sorry, but I don't understand why this is useful, why there are so many {% if false %} and what's the current problem with Float#hash.

@RX14
Copy link
Contributor

RX14 commented Jun 13, 2017

In addition to what @asterite said, if there's a LLVM intrinsic why aren't we binding and using it in instrinsics.cr.

@akzhan
Copy link
Contributor Author

akzhan commented Jun 13, 2017

@asterite There are two problems now:

  1. Float32.hash doesn't normalize values before hash, so two representations of same floating value points to different key-value pairs. It's wrong (as seen by Python hash algorithm, for example).

  2. Float64.hash has same problem and moreover, it is totally wrong due to Problem with Hash's hash codes truncation #3932. It will be solved later.

And I have a question - how to embed checks for existence of imported function in Library? llvm.canonicalize available from LLVM 5, llvm.minmax available from 3.N (I doesn't check which N).

@RX14 Yes, I have seen intrinsics, but doesn't understood criteria to place them into Intrinsics or LibM. Looks like they exists everywhere.

@RX14
Copy link
Contributor

RX14 commented Jun 13, 2017

I think the float normalization intrinsic should go in LibM actually since they're float related. Could we just xor the lower and higher 32 bits of the float64 together?

@RX14
Copy link
Contributor

RX14 commented Jun 13, 2017

@akzhan We don't currently have support for LLVM 5 and we won't until at least the release candidates. There's LLVM version constants defined here

@akzhan
Copy link
Contributor Author

akzhan commented Jun 13, 2017

Could we just xor the lower and higher 32 bits of the float64 together?

It does bad distribution.

I prefer this:

https://github.com/python/cpython/blob/master/Python/pyhash.c#L34

@akzhan
Copy link
Contributor Author

akzhan commented Jun 13, 2017

We don't currently have support for LLVM 5 and we won't until at least the release candidates. There's LLVM version constants defined here

It is not the problem, I will add IS_50 constant if needed.

But bin/crystal doesn't compile code with {% if LibLLVM::IS_50 ..., without recompilation of itself.

OK, will replace, recompile and try.

@akzhan akzhan changed the title Introduce floats canonicalize. [WIP] Introduce floats canonicalize. Jun 13, 2017
@ysbaddaden
Copy link
Contributor

No. We don't support LLVM5 and compiling and linking against LLVM5 will just fail.

@akzhan
Copy link
Contributor Author

akzhan commented Jun 13, 2017

@ysbaddaden I want just to add

    IS_50 = {{LibLLVM::VERSION.starts_with?("5.0")}}

and test for it with

  {% if LibLLVM::IS_50 %}
  fun canonicalize_f32 = "llvm.canonicalize.f32"(value : Float32) : Float32
  fun canonicalize_f64 = "llvm.canonicalize.f64"(value : Float64) : Float64
  {% end %}

and other places.

To not rewrite code later.

@akzhan
Copy link
Contributor Author

akzhan commented Jun 13, 2017

@RX14 So #4560 frexp is introduced to implement Float64.hash later. And just because it is stdlib.

@ysbaddaden
Copy link
Contributor

ysbaddaden commented Jun 13, 2017

  1. it should be IS_5 = x.starts_with?("5.") because there will only be major releases (and sometimes patch releases, numbered as minor) from now on;
  2. don't bother with LLVM5 until we start supporting it (next september, at best), nobody will benefit from it until months later;
  3. fix issues in a LLVM 3.8+ compatible way, and add a note that LLVM 5+ could help.

@RX14
Copy link
Contributor

RX14 commented Jun 13, 2017

llvm.minnum was introduced in LLVM 3.6 for reference. I doubt there's any way to remove constant folding without making the method non-inlinable.

@akzhan
Copy link
Contributor Author

akzhan commented Jun 13, 2017

Thanks, @RX14. Looks like I want to get #4396 landed and forget about old LLVMs.

See http://llvm.org/docs/LangRef.html#llvm-canonicalize-intrinsic for details.

Fix FloatXX.hash to use canonicalize.

Introduce LibLLVM::IS_5 constant.
@akzhan akzhan force-pushed the introduce_floats_canonicalize branch from 0fedf21 to e8577ba Compare June 13, 2017 18:57
@akzhan akzhan changed the title [WIP] Introduce floats canonicalize. Introduce floats canonicalize, min, max intrinsics etc. Jun 13, 2017
@akzhan
Copy link
Contributor Author

akzhan commented Jun 13, 2017

Thanks to @RX14 and @ysbaddaden for your help.

Now it's ready.

P.S.: Sorry for bad commits since I did not have a working VM during the day.

@akzhan
Copy link
Contributor Author

akzhan commented Jun 13, 2017

@asterite Looks like compiler cannot be built using LLVM <4.0, it raises on LLVM 3.8/Travis:

in src/llvm/abi.cr:2: class declaration can't have attributes
abstract class LLVM::ABI

I don't know, is it OK?

@akzhan
Copy link
Contributor Author

akzhan commented Jun 13, 2017

Looks like I must not use LibLLVM::IS_* anywhere in stdlib.

This pull request will be [WIP] until #4396 landed.

Anyway I can rework Float hashing with frexp only.

@akzhan akzhan closed this Jun 13, 2017
@akzhan akzhan changed the title Introduce floats canonicalize, min, max intrinsics etc. [WIP] Introduce floats canonicalize, min, max intrinsics etc. Jun 13, 2017
akzhan added a commit to akzhan/crystal that referenced this pull request Jun 13, 2017
It works fine with LLVM 3.6+, just tested.

Extracted from crystal-lang#4559.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

4 participants