llvm dev - Jul 2015 - [LLVMdev] PHI Elimination in Register Allocation Pass

Good Afternoon.

I am a Computer Science undergraduate student in Brazil and as completion
of course work, I am developing an register allocator, using the
infrastructure of the LLVM.

To accomplish this task, I have based my implementation in allocators
already implemented in LLVM. But a question came to me while I was
researching in books and articles of compiler theory and own documentation
of LLVM, I noticed an important step in the optimization phase, the
deconstruction of form SSA (*PHI Elimination*), from what I've read, this
step has great impact on the code generation and can be done before or
after the register allocation phase. And I intend to implement the
allocator registers using the resources of SSA representation, making this
step (*PHI Elimination*) vital for development.

Looking at the source code of allocators of LLVM, I see no explicit call of
PHI Elimination (*AU.addRequiredID (PHIEliminationID)*), my question is
whether if this step is called, occurs when and where such a call?

-- 
Natanael Ramos
Membro do corpo discente de Ciência da Computação pelo Instituto Federal de
Minas Gerais - Campus Formiga
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150709/c0775b81/attachment.html>

Hi Natanael,
> On Jul 9, 2015, at 1:06 PM, Natanael Ramos <naelr8 at gmail.com>
wrote:
> 
> Good Afternoon.
> 
> I am a Computer Science undergraduate student in Brazil and as completion
of course work, I am developing an register allocator, using the infrastructure
of the LLVM.
> 
> To accomplish this task, I have based my implementation in allocators
already implemented in LLVM. But a question came to me while I was researching
in books and articles of compiler theory and own documentation of LLVM, I
noticed an important step in the optimization phase, the deconstruction of form
SSA (PHI Elimination), from what I've read, this step has great impact on
the code generation and can be done before or after the register allocation
phase. And I intend to implement the allocator registers using the resources of
SSA representation, making this step (PHI Elimination) vital for development.
> 
> Looking at the source code of allocators of LLVM, I see no explicit call of
PHI Elimination (AU.addRequiredID (PHIEliminationID)), my question is whether if
this step is called, occurs when and where such a call?
Yes, this pass is always called, but before register allocation. (Though the
liveness information still uses the SSA form.)

The pass is added in the pipeline in lib/CodeGen/Passes.cpp, see for instance:
TargetPassConfig::addOptimizedRegAlloc

Cheers,
-Quentin
> 
> -- 
> Natanael Ramos 
> Membro do corpo discente de Ciência da Computação pelo Instituto Federal de
> Minas Gerais - Campus Formiga
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150709/e5b26b65/attachment.html>

On 7/9/2015 3:06 PM, Natanael Ramos wrote:
>
> Looking at the source code of allocators of LLVM, I see no explicit call
> of PHI Elimination (/*AU.addRequiredID (PHIEliminationID**)*/), my
> question is whether if this step is called, occurs when and where such a
> call?
Look in lib/CodeGen/Passes.cpp:

   addPass(&PHIEliminationID, false);

-Krzysztof

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

Thank you Quentin.

It is an interesting fact that the liveness Analisys be maintained in SSA,
even after the phase of PHI Destruction. It facilitates the implementation
of the register allocator.

Cheers,
Natanael.
Em 09/07/2015 17:28, "Quentin Colombet" <qcolombet at apple.com>
escreveu:
> Hi Natanael,
>
> On Jul 9, 2015, at 1:06 PM, Natanael Ramos <naelr8 at gmail.com>
wrote:
>
> Good Afternoon.
>
> I am a Computer Science undergraduate student in Brazil and as completion
> of course work, I am developing an register allocator, using the
> infrastructure of the LLVM.
>
> To accomplish this task, I have based my implementation in allocators
> already implemented in LLVM. But a question came to me while I was
> researching in books and articles of compiler theory and own documentation
> of LLVM, I noticed an important step in the optimization phase, the
> deconstruction of form SSA (*PHI Elimination*), from what I've read,
this
> step has great impact on the code generation and can be done before or
> after the register allocation phase. And I intend to implement the
> allocator registers using the resources of SSA representation, making this
> step (*PHI Elimination*) vital for development.
>
> Looking at the source code of allocators of LLVM, I see no explicit call
> of PHI Elimination (*AU.addRequiredID (PHIEliminationID)*), my question
> is whether if this step is called, occurs when and where such a call?
>
>
> Yes, this pass is always called, but before register allocation. (Though
> the liveness information still uses the SSA form.)
>
> The pass is added in the pipeline in lib/CodeGen/Passes.cpp, see for
> instance: TargetPassConfig::addOptimizedRegAlloc
>
> Cheers,
> -Quentin
>
>
> --
> Natanael Ramos
> Membro do corpo discente de Ciência da Computação pelo Instituto Federal
> de
> Minas Gerais - Campus Formiga
>
>  _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150709/7efba835/attachment.html>