llvm-java

Hello,

I'm working on a project to remove unnecessary array bound checks in Java. For this purpose I will need to use llvm-java.

What is the state of llvm-java? Can someone explain how to build and use it?

I saw some old emails on the list, and some about a SoC 2008 on Java, but I didn't find anything regarding its current state and documentation.

Regards,

Hello,

LLVM-Java has been rendered obsolete by http://vmkit.llvm.org/ so look into using VMKit instead.

--Sam

Samuel Crow wrote:

Hello,

LLVM-Java has been rendered obsolete by http://vmkit.llvm.org/ so look into using VMKit instead.

--Sam

From: Andre Tavares <andrelct@dcc.ufmg.br>
To: LLVMdev@cs.uiuc.edu
Sent: Monday, May 18, 2009 10:09:42 AM
Subject: [LLVMdev] llvm-java

Hello,

I'm working on a project to remove unnecessary array bound checks in Java. For this purpose I will need to use llvm-java.

What is the state of llvm-java? Can someone explain how to build and use it?

I saw some old emails on the list, and some about a SoC 2008 on Java, but I didn't find anything regarding its current state and documentation.

Regards,

--
Andre Tavares
Master Student in Computer Science - UFMG - Brasil
http://dcc.ufmg.br/~andrelct

_______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
    
      _______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Thanks Samuel I will look it.

Samuel Crow wrote:

From: Andre Tavares <andrelct@dcc.ufmg.br>

I'm working on a project to remove unnecessary array bound checks in
Java. For this purpose I will need to use llvm-java.

What is the state of llvm-java? Can someone explain how to build and use it?

I saw some old emails on the list, and some about a SoC 2008 on Java,
but I didn't find anything regarding its current state and documentation.

LLVM-Java has been rendered obsolete by http://vmkit.llvm.org/ so look into using VMKit instead.

Also, if you can make the capability generic enough to use in Shark
(more at http://gbenson.net/) that would be very useful.

The key, I suspect, is to allow the Java front end mark an array.length
field in such a way that LLVM knows that field doesn't alias anything else
and is constant, so it can be hoisted out of loops.

Andrew.

Hello, Andre

I'm working on a project to remove unnecessary array bound checks in
Java. For this purpose I will need to use llvm-java.

Why? Why don't use vmkit for this?

What is the state of llvm-java? Can someone explain how to build and use it?

It's dead and unmaintained for years. Most probably nobody will be able
to run it without major rewrite.

Hi Andre,

I'm working on a project to remove unnecessary array bound checks in Java. For this purpose I will need to use llvm-java.

What is the state of llvm-java? Can someone explain how to build and use it?

I saw some old emails on the list, and some about a SoC 2008 on Java, but I didn't find anything regarding its current state and documentation.

I have a much better idea: work on removing unnecessary array bound
checks in Ada. Who cares about this java thing anyway?! Seriously
though, while of course it is important to work on java, may I humbly
request that you also look at the llvm-gcc Ada front-end. Ada, like
Pascal (which it derives from) does bound checking on all array accesses
and does many other runtime checks too. As such it should be a good
test for any such pass. It's not particularly hard to build llvm-gcc
with Ada support if you are using x86-32 linux, see
   http://llvm.org/docs/GCCFEBuildInstrs.html
Even better, llvm-gcc comes with the complete Ada ACATS testsuite,
so after building all you have to do is change into the gcc subdirectory
and do: make -k check-acats

Ciao,

Duncan.

Hi Andre,

Andre Tavares wrote:

Hello,

I'm working on a project to remove unnecessary array bound checks in Java. For this purpose I will need to use llvm-java.

What is the state of llvm-java? Can someone explain how to build and use it?

llvm-java won't compile with current versions of LLVM. Instead, you could use VMKit (http://vmkit.llvm.org).

Cheers,
Nicolas

Hi Andrew,

Andrew Haley wrote:

Also, if you can make the capability generic enough to use in Shark
(more at http://gbenson.net/) that would be very useful.

Agree.

The key, I suspect, is to allow the Java front end mark an array.length
field in such a way that LLVM knows that field doesn't alias anything else
and is constant, so it can be hoisted out of loops.
  
For that matter, VMKit already has this optimization. Instead of emitting an LLVM load of the size field, VMKit emits a GetArrayLength call, flagged readnone. The GVN pass will merge all GetArrayLength of a same array and the LICM pass will hoist the call. Once theses passes are complete, VMKit lowers the call to
the actual load.

:slight_smile:

Cheers,
Nicolas

Nicolas Geoffray wrote:

Hi Andrew,

Andrew Haley wrote:

Also, if you can make the capability generic enough to use in Shark
(more at http://gbenson.net/) that would be very useful.

>

Agree.

The key, I suspect, is to allow the Java front end mark an array.length
field in such a way that LLVM knows that field doesn't alias anything else
and is constant, so it can be hoisted out of loops.

For that matter, VMKit already has this optimization. Instead of
emitting an LLVM load of the size field, VMKit emits a GetArrayLength
call, flagged readnone. The GVN pass will merge all GetArrayLength of a
same array and the LICM pass will hoist the call. Once theses passes are
complete, VMKit lowers the call to
the actual load.

Right, so that part should be trivial. So, does the array bounds check
elimination already work? If it does, that will considerably reduce
the work that Andre needs to do. To say the least...

Andrew.

Andrew Haley wrote:

Right, so that part should be trivial. So, does the array bounds check
elimination already work? If it does, that will considerably reduce
the work that Andre needs to do. To say the least...

Trivial bounds check elimination already work, such as tab[2] = 1; tab[1] = 2 (the second affectation won't have a bounds checks). Although I don't know the details, I believe Andre also targets less trivial eliminations.

Nicolas

Nicolas Geoffray wrote:

Andrew Haley wrote:

Right, so that part should be trivial. So, does the array bounds check
elimination already work? If it does, that will considerably reduce
the work that Andre needs to do. To say the least...

Trivial bounds check elimination already work, such as tab[2] = 1;
tab[1] = 2 (the second affectation won't have a bounds checks). Although
I don't know the details, I believe Andre also targets less trivial
eliminations.

I should have asked a better question. By "does it work" I meant something
like

  for (int i = 0; i < a.length; i++)
    System.out.println(a[i]);

in which the autogenerated check should trivially be removed, but only if
LLVM knows that a.length is invariant.

Andrew.

Andrew Haley wrote:

Nicolas Geoffray wrote:

Andrew Haley wrote:

Right, so that part should be trivial. So, does the array bounds check
elimination already work? If it does, that will considerably reduce
the work that Andre needs to do. To say the least...

Trivial bounds check elimination already work, such as tab[2] = 1;
tab[1] = 2 (the second affectation won't have a bounds checks). Although
I don't know the details, I believe Andre also targets less trivial
eliminations.

I should have asked a better question. By "does it work" I meant something
like

  for (int i = 0; i < a.length; i++)
    System.out.println(a[i]);

in which the autogenerated check should trivially be removed, but only if
LLVM knows that a.length is invariant.

Oh, I forgot to mention that a.length should be hoisted into a register
as it's loop invariant.

Andrew.

Andrew Haley wrote:

I should have asked a better question. By "does it work" I meant something
like

  for (int i = 0; i < a.length; i++)
    System.out.println(a[i]);
  
OK, so no :slight_smile: VMKit does not know that a[i] is related to a.length. I believe Andre's optimizations will take care of that.

Nicolas

Nicolas Geoffray wrote:

Andrew Haley wrote:
  

I should have asked a better question. By "does it work" I meant something
like

  for (int i = 0; i < a.length; i++)
    System.out.println(a[i]);
  
OK, so no :slight_smile: VMKit does not know that a[i] is related to a.length. I believe Andre's optimizations will take care of that.

Nicolas
_______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Thanks for all answers. I will consider them all before I start coding.

I have another discussion that I would like to hear from you.

I can implement SSI in two different ways. Analysis or Transformation Pass.

As an Analysis Pass, I would create a SSI LiveInterval, mapping each interval with a constraint.
Pros: No change to the IR.
Cons: It is a simulation.

As an Transformation Pass, SSI would be implemented in the IR with copy instructions (pi functions) and phi functions on the end.
Pros: Real SSI. Each interval has a constraint.
Cons: IR is bigger, what can impact other optimizations.

What do you think?

Hi Andre?

Andre Tavares wrote:

Thanks for all answers. I will consider them all before I start coding.

I have another discussion that I would like to hear from you.

I can implement SSI in two different ways. Analysis or Transformation Pass.

As an Analysis Pass, I would create a SSI LiveInterval, mapping each interval with a constraint.
Pros: No change to the IR.
Cons: It is a simulation.
  
It is a simulation == bad performance?

As an Transformation Pass, SSI would be implemented in the IR with copy instructions (pi functions) and phi functions on the end.
Pros: Real SSI. Each interval has a constraint.
Cons: IR is bigger, what can impact other optimizations.

How would you model this pi function? New instruction? New intrinsic?

Nicolas

Nicolas Geoffray wrote:

Hi Andre?

Andre Tavares wrote:
  

Thanks for all answers. I will consider them all before I start coding.

I have another discussion that I would like to hear from you.

I can implement SSI in two different ways. Analysis or Transformation Pass.

As an Analysis Pass, I would create a SSI LiveInterval, mapping each interval with a constraint.
Pros: No change to the IR.
Cons: It is a simulation.
  
It is a simulation == bad performance?

As an Transformation Pass, SSI would be implemented in the IR with copy instructions (pi functions) and phi functions on the end.
Pros: Real SSI. Each interval has a constraint.
Cons: IR is bigger, what can impact other optimizations.

How would you model this pi function? New instruction? New intrinsic?

Nicolas

_______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Nicolas,

I think the performance of my Pass will be the same independent of which type I use. But if I make transformations I will reduce the performance of other optimizations.

The pi functions can be implemented with copy instructions. This way it won't change other optimizations.

Example:
a1, a2 = pi(a) into
a1 = a
a2 = a

Hi Andre,

Andre Tavares wrote:

Nicolas,

I think the performance of my Pass will be the same independent of which type I use. But if I make transformations I will reduce the performance of other optimizations.

I don't get it. What is the cons then of a simulation?

The pi functions can be implemented with copy instructions.

Store instructions?

This way it won't change other optimizations.

Why would the analysis change other optimizations?

Example:
a1, a2 = pi(a) into
a1 = a
a2 = a

OK, so your pass/analysis creates the stores? Why do you need to introduce the pi name?

(Btw, I have no knowledge on SSI/SSA construction theories, so maybe I need a higher-level explanation of the problem)

Thanks,
Nicolas

I would assume something more like "select i1 true, <ty> %val, <ty> undef".

-Eli

Eli Friedman wrote:

FWIW, I strongly recommend going this direction. It'll buy you a lot of free functionality, like replaceAllUsesWith().

--Owen