[llvm-dev] Alloca, Inlining and Entry Basic Block

237 views
Skip to first unread message

Mahesha S via llvm-dev

unread,
Sep 14, 2021, 7:49:10 AM9/14/21
to llvm-dev
Hi-

Theoretically, alloca instructions can appear anywhere within the function body, but practically, it is better to keep them as a one cluster at the beginning of the entry basic block for better optimization opportunities. 

And, I think the front-end code gen phase mostly succeeds in clustering all alloca instructions at the beginning of the entry basic block. Nevertheless, it is not guaranteed always. One more case is inlining - which may leave alloca instructions other than in entry block.

So, I am thinking of adding a new late IR pass (after inlining) which deliberately moves all allocas which appear elsewhere to the beginning of the entry block.

Now my questions are:

(1) Can we neatly implement this pass? For example, what would happen if an alloca which appears within a loop is moved to the entry block?
(2) Is there a possibility where some other later pass(es) other than inlining also can result in inserting alloca elsewhere, so the new proposed pass needs to be invoked multiple times?

The main reason for the above ask is - I have my own doubt that if moving alloca to the entry block is such an easy task why not anyone from the community did not attempt it till date considering the importance of keeping the allocas at the beginning of the entry block for better optimization opportunities. If there are genuine reason for that, it is better to know it instead of blindly attempting to implement the pass.

Thanks,
Mahesha

Roman Lebedev via llvm-dev

unread,
Sep 14, 2021, 8:23:16 AM9/14/21
to Mahesha S, llvm-dev
On Tue, Sep 14, 2021 at 2:49 PM Mahesha S via llvm-dev
<llvm...@lists.llvm.org> wrote:
>
> Hi-
>
> Theoretically, alloca instructions can appear anywhere within the function body, but practically, it is better to keep them as a one cluster at the beginning of the entry basic block for better optimization opportunities.

> And, I think the front-end code gen phase mostly succeeds in clustering all alloca instructions at the beginning of the entry basic block. Nevertheless, it is not guaranteed always. One more case is inlining - which may leave alloca instructions other than in entry block.

*May*? Can you show an example perhaps?
I would think that could only happen for VLA's,
because such an alloca can not be hoisted
to before it's length is calculated.

> So, I am thinking of adding a new late IR pass (after inlining) which deliberately moves all allocas which appear elsewhere to the beginning of the entry block.
>
> Now my questions are:
>
> (1) Can we neatly implement this pass? For example, what would happen if an alloca which appears within a loop is moved to the entry block?
> (2) Is there a possibility where some other later pass(es) other than inlining also can result in inserting alloca elsewhere, so the new proposed pass needs to be invoked multiple times?
>
> The main reason for the above ask is - I have my own doubt that if moving alloca to the entry block is such an easy task why not anyone from the community did not attempt it till date considering the importance of keeping the allocas at the beginning of the entry block for better optimization opportunities. If there are genuine reason for that, it is better to know it instead of blindly attempting to implement the pass.
>
> Thanks,
> Mahesha

Roman

> _______________________________________________
> LLVM Developers mailing list
> llvm...@lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
_______________________________________________
LLVM Developers mailing list
llvm...@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Nicolai Hähnle via llvm-dev

unread,
Sep 17, 2021, 4:25:14 AM9/17/21
to Mahesha S, llvm-dev
On Tue, Sep 14, 2021 at 1:49 PM Mahesha S via llvm-dev <llvm...@lists.llvm.org> wrote:
Hi-

Theoretically, alloca instructions can appear anywhere within the function body, but practically, it is better to keep them as a one cluster at the beginning of the entry basic block for better optimization opportunities. 

And, I think the front-end code gen phase mostly succeeds in clustering all alloca instructions at the beginning of the entry basic block. Nevertheless, it is not guaranteed always. One more case is inlining - which may leave alloca instructions other than in entry block.

The inliner explicitly scans for allocas in the callee entry block and moves them to the caller's entry block.

In other words: if you're seeing surprising alloca's in the middle of a function (i.e., _not_ VLAs like Roman mentioned), please first do a root-cause into why those allocas end up where they do. If you're unfamiliar with LLVM, such root-causing can be done with tools like the -print-before-all command-line flags, which give you the IR between every pass. You can go through that log to figure out where allocas first appear in surprising places.

Cheers,
Nicolai
 

So, I am thinking of adding a new late IR pass (after inlining) which deliberately moves all allocas which appear elsewhere to the beginning of the entry block.

Now my questions are:

(1) Can we neatly implement this pass? For example, what would happen if an alloca which appears within a loop is moved to the entry block?
(2) Is there a possibility where some other later pass(es) other than inlining also can result in inserting alloca elsewhere, so the new proposed pass needs to be invoked multiple times?

The main reason for the above ask is - I have my own doubt that if moving alloca to the entry block is such an easy task why not anyone from the community did not attempt it till date considering the importance of keeping the allocas at the beginning of the entry block for better optimization opportunities. If there are genuine reason for that, it is better to know it instead of blindly attempting to implement the pass.

Thanks,
Mahesha
_______________________________________________
LLVM Developers mailing list
llvm...@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


--
Lerne, wie die Welt wirklich ist,
aber vergiss niemals, wie sie sein sollte.
Reply all
Reply to author
Forward
0 new messages