[LLVMdev] Box removal

[James Molloy]

Hi Timothy,

LLVM cannot remove the malloc calls, as malloc() has a sideeffect and that
would be changing the behaviour of the program.

Apart from that, the problem with unboxing in dynamic languages is knowing
beforehand which function to dispatch to. mul_ints or mul_floats, for
example? What if a particular type has overridden the + operator, etc etc.
So your code normally ends up bouncing through several functions making
analysis difficult.

James

> -----Original Message-----
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu]
> On Behalf Of Timothy Baldridge
> Sent: 28 June 2011 19:25
> To: llvmdev at cs.uiuc.edu
> Subject: [LLVMdev] Box removal
> 
> In the creation of dynamic languages we often have to box values
> together.
> 
> For instance, take the following expression:
> 
> IntObj c = sqrt((a*a)+(b*b));
> 
> Here, most likely, a bytecode interpreter would execute this as
> "mul_ints", "add_ints", "sqrt", etc. Inside these primitive functions
> we would have to unwrap our IntObj types, add the values, allocate a
> new object and return that to the function. In the above example, we
> could probably expect around 4 allocations, and 7 unboxing operations.
> Now granted if my lanugage is running as a bytecode interpreter, I can
> speed it up simply by having LLVM call my functions in order, and
> perhaps even in-lining all the bytecode operations into a single
> function. But even then, I'm still left with the 4 allocations and 7
> unboxings (is that even a word?).
> 
> I know other compiler projects, such as PyPy have allocation removal
> where the optimization passes see that we only use the result of an
> allocation a single time. Thinking that LLVM may do this as well, I
> tried this simple test on in-browser LLVM compiler:
> --------
> #include <stdio.h>
> #include <stdlib.h>
> 
> typedef struct Foo
> {
> int *x;
> int x2;
> }Foo;
> 
> int main(int argc, char **argv) {
> Foo *f = (Foo *)malloc(sizeof(Foo));
> f->x = (int *)malloc(sizeof(int));
> *f->x = 10;
> return *f->x;
> }
> 
> ----
> 
> Output:
> 
> ; ModuleID = '/tmp/webcompile/_28006_0.bc'
> target datalayout =
> "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-
> f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-
> n8:16:32:64"
> target triple = "x86_64-linux-gnu"
> 
> define i32 @main(i32 %argc, i8** nocapture %argv) nounwind {
> entry:
>   %0 = tail call noalias i8* @malloc(i64 16) nounwind ; <i8*> [#uses=1]
>   %1 = tail call noalias i8* @malloc(i64 4) nounwind ; <i8*> [#uses=1]
>   %2 = bitcast i8* %1 to i32*                     ; <i32*> [#uses=2]
>   %3 = bitcast i8* %0 to i32**                    ; <i32**> [#uses=1]
>   store i32* %2, i32** %3, align 8
>   store i32 10, i32* %2, align 4
>   ret i32 10
> }
> 
> ------
> 
> As you can see, the allocations are still being performed. Now if we
> could get rid of these allocations, then this entire function could be
> reduced to a single line that just returns 10.
> 
> Is any optimization like this planned or even feasible in LLVM?
> 
> 
> Thank you for your time.
> 
> Timothy Baldridge
> 
> 
> 
> 
> --
> "One of the main causes of the fall of the Roman Empire was
> that-lacking zero-they had no way to indicate successful termination
> of their C programs."
> (Robert Firth)
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev