[LLVMdev] Promoting malloc to alloca

[Reid Kleckner]

I'm guessing that you're using or planning on using a garbage
collector.  IIRC Evan Phoenix wanted something similar for Rubinius.
Through constant propagation, all uses of allocated memory would be
deleted, but the malloc would be left behind.  I think he may have
implemented a custom pass that just eliminates mallocs with no uses
except as the target of stores.

I haven't heard anything about escape analysis in LLVM, though.

Reid

On Mon, Jul 12, 2010 at 3:21 AM, Matt Giuca <matt.giuca at gmail.com> wrote:
> I have a compiler which generates a lot of malloc instructions for
> basically all data. I was rather hoping that these mallocs would be
> converted to allocas if the pointers didn't escape. This would require
> an escape analysis, and I'm not sure if LLVM has such a thing.
>
> For instance, consider this code (typical of the output of my compiler):
>
> define i32 @dontescape(i32 %x) {
> entry:
>   %t = tail call i8* @malloc(i32 4)
>   %t1 = bitcast i8* %t to i32*
>   store i32 %x, i32* %t1
>   %t2 = load i32* %t1
>   ret i32 %t2
> }
>
> Running with opt --std-compile-opts, LLVM is smart enough to figure
> out that the result is actually %x. So it generates:
>
> define i32 @dontescape(i32 %x) nounwind {
> entry:
>   %t = tail call i8* @malloc(i32 4)               ; <i8*> [#uses=1]
>   %t1 = bitcast i8* %t to i32*                    ; <i32*> [#uses=1]
>   store i32 %x, i32* %t1
>   ret i32 %x
> }
>
> This saves a load, but I was rather hoping to eliminate the malloc and
> store altogether. I was hoping it would realise that %t doesn't
> escape, and generate this code:
>
> define i32 @dontescape(i32 %x) nounwind {
> entry:
>   %t1 = alloca i32, i32 1                           ; <i32*> [#uses=1]
>   store i32 %x, i32* %t1
>   ret i32 %x
> }
>
> which would then get optimised to:
>
> define i32 @dontescape(i32 %x) nounwind readnone {
> entry:
>   ret i32 %x
> }
>
> and in general the allocas would go on to become registers due to
> mem2reg, which would be wonderfully efficient.
>
> So firstly, is there anything I'm doing wrong which is preventing this
> from working? For example, I tried declaring malloc as "readnone" (is
> this safe?). That would partly fix the problem (if you allocate memory
> but don't return it, it can optimise away the malloc), except that it
> isn't clever enough to realise the "store" instruction is redundant.
> Again, I think this would require an escape analysis to fix. Maybe
> there's an optimisation pass I'm missing here.
>
> Secondly, if there is currently no way to magically make this work,
> has this proposal been discussed before? Are there any known gotchas
> which prevented it from being implemented?
>
> I've found this file. I'm not sure if it's part of the LLVM
> distribution, or a branch:
> https://llvm.org/svn/llvm-project/llvm/tags/Apple/llvmCore-2092/lib/Analysis/EscapeAnalysis.cpp
> It contains a comment: "Returns allow the return value to escape.
> This is mostly important for malloc to alloca promotion."
>
> I'm using LLVM 2.7.
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>