Support sext and trunc instructions in SCEV delinearization algorithm
Needs ReviewPublic

Authored by ManuelSelva on Mon, Jul 17, 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.Mon, Jul 17, 4:29 AM
ManuelSelva added a project: Restricted Project.Mon, Jul 17, 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.EditedWed, Jul 19, 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