Support sext and trunc instructions in SCEV delinearization algorithm
Needs ReviewPublic

Authored by ManuelSelva on Jul 17 2017, 4:29 AM.

Details

Reviewers
grosser
sebpop
Summary

This patch is a very first attempt to support sext and trunc instructions in SCEV delinearization algorithm.
The patch includes:

  • modifications of the algorithm trying to divide an SCEV by another SCEV in order to support sext and trunc instructions.
  • a test case for this new feature

Diff Detail

ManuelSelva created this revision.Jul 17 2017, 4:29 AM
ManuelSelva added a project: Restricted Project.Jul 17 2017, 6:00 AM

Add Sebastian as reviewer.

Hi Manuel,

most changes are simple. I added a couple of style comments. I probably only get to this on the weekend, but the main thing we need to check is under which conditions ignoring sext/zext is legal. I am afraid, this is only OK with non-trivial checks -- or if ew can get nsw information from the IR.

Out of interest. Why does your IR has the mix of 32 and 64 values in the first place? And why do you have overflow-checked intrinsics?

lib/Analysis/ScalarEvolution.cpp
873

Indentation.

878

Indentation.

925

Alignment?

940

Can this assert ever be reached? It seems you bail out right before the position at which the assert is inserted.

ManuelSelva added a comment.EditedJul 19 2017, 2:25 AM

Hi Tobias,

Thank you for looking at that. To first answer your questions "out of interest", this IR is generated by JavaScriptCore, a JavaScript virtual machine performing JIT compilation. The virtual machine is using NaN-boxing, i.e., uses the unused values (all representing NaN) of 64 bits floating point representation to represent JavaScript objects. In this representation, 32 bits integers are represented by 64 bits values all starting with the FFFF 0000 32 bits pattern. As a consequence, to get the integer value from a 64 bits value, the virtual machine generates LLVM code that truncates the value to a 32 bits integer.

Then, when performing arithmetic operations on these 32 bits integers, we need to ensure that they do not overflow, because if it's the case, we can't represent them anymore with the NaN-boxing trick and so we need to do *something* to represent them properly. This "something" is not present in the test case I provided in order to make it as minimal as possible.

If you are curious on this NaN-boxing thing and more generally on JavaScript implementations, you can have a look at the following links:

I'll now look into the details of this patch, to ensure its correctness as you said.

Best,
Manu

Hi Tobias,

Thank you for looking at that. To first answer your questions "out of interest", this IR is generated by JavaScriptCore, a JavaScript virtual machine performing JIT compilation. The virtual machine is using NaN-boxing, i.e., uses the unused values (all representing NaN) of 64 bits floating point representation to represent JavaScript objects. In this representation, 32 bits integers are represented by 64 bits values all starting with the FFFF 0000 32 bits pattern. As a consequence, to get the integer value from a 64 bits value, the virtual machine generates LLVM code that truncates the value to a 32 bits integer.

Then, when performing arithmetic operations on these 32 bits integers, we need to ensure that they do not overflow, because if it's the case, we can't represent them anymore with the NaN-boxing trick and so we need to do *something* to represent them properly. This "something" is not present in the test case I provided in order to make it as minimal as possible.

If you are curious on this NaN-boxing thing and more generally on JavaScript implementations, you can have a look at the following links:

Hello.
  I applied the patch that was provided in this review to my LLVM build.
  I would like to draw attention to a bug of the deliniarization procedure that is related to type casts (from i32 to i64), and is probably related to the problems that were supposed to be addressed by the patch in this review.
  I attach a C file that reproduces this bug - the delinearization procedure fails due to sext from i32 to i64, and Polly finds Non affine access functions, which he shouldn't. Note that in the same C file I also provide on line 3 a commented signature of the Test function which can be uncommented, for which delinearization works OK and all access functions are affine.
  I will try to look deeper in the problem with delinearization. Please let me know if you can help with this problem.

Best regards,
  Alex

Hello.

I applied the patch that was provided in this review to my LLVM build.
I would like to draw attention to a bug of the deliniarization procedure that is related to type casts (from i32 to i64), and is probably related to the problems that were supposed to be addressed by the patch in this review.
I attach a C file that reproduces this bug - the delinearization procedure fails due to sext from i32 to i64, and Polly finds Non affine access functions, which he shouldn't. Note that in the same C file I also provide on line 3 a commented signature of the Test function which can be uncommented, for which delinearization works OK and all access functions are affine.
I will try to look deeper in the problem with delinearization. Please let me know if you can help with this problem.

Best regards,

Alex