[llvm-dev] [RFC] Register Rematerialization (remat) Extension

[vivek pandya via llvm-dev]

On Mon, Sep 19, 2016 at 6:21 PM, James Molloy <james at jamesmolloy.co.uk>
wrote:

> Hi,
>
> I've been looking at this myself for ARM, and came up with a much simpler
> solution: lower immediate materializations to a post-RA pseudo and expand
> the chain of materialization instructions after register allocation /
> remat. Remat only sees one instruction with no dependencies.
>
> Did you look down this route and discount it?
>
No actually I am not much familiar with this topic so I mostly reply on
research papers available.
But your idea seems to be simple and good solution but I am not sure if
this can cover every possible cases.

Do you have a patch for this? I can work on this to make it work for other
architectures for which this will be beneficial.

Sincerely,
Vivek

>
> Cheers,
>
> James
>
> On Wed, 14 Sep 2016 at 02:43 Gerolf Hoflehner via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> On Sep 12, 2016, at 10:14 AM, Andrew Trick via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>>
>> On Sep 12, 2016, at 8:51 AM, vivek pandya via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>>
>> 1 ) As LLVM MI is already in SSA form before reg allocation so for LLVM I
>> think it does not require to build SSA graph and converting it back after
>> optimization completed as mentioned in [1]
>>
>> 2 ) We would like to add a pass similar to SCCP.cpp (Sparse Conditional
>> Constant
>> Propagation based on Wegman and Zadeck's work http://dl.acm.org/citation.
>> cfm?id=103136) as desribed in [1]. This pass will be scheduled to run
>> before register allocation.
>>
>> 3 ) Output of the pass added in Step 2 will be a Map of def to
>> instructions pointers (instructions which can be used to remat the given
>> live range). The map will contain live ranges which is due to single
>> instruction and multiple instructions.
>>
>>
>> LiveIntervals maintains a quasi-SSA form via VNInfo. It does not allow
>> efficient def-use queries, but use-def is there, which is all that you
>> should need.
>>
>>
>> I also only see a narrow and specific remat cost problem in the example:
>> is it cheaper is issue a  chain of instructions rather than a fill? And for
>> this a use-def is sufficient.
>>
>>
>> It would be great to have better remat during regalloc, but please try to
>> avoid building additional state that needs to be maintained.
>>
>>
>> You proposed a fairly complex scheme. The question then is always is it
>> worth it? To answer that question you would need to investigate and break
>> down the current remat problems (spills but should remat, remat but should
>> spill, should remat at a different location, etc) eg. for the llvm test
>> suite, and show that your algorithms solves the most important ones.
>>
>>
>>
>>
>> -Andy
>>
>>
>> 4 ) The remat APIs defined in LiveRangeEdit.cpp will use analysis from
>> the Map
>> when a spill is required for RA.
>>
>> 5 ) The remat transformation APIs like rematerializeAt() will be teached
>> to remat
>> live ranges with multiple instructions too.
>>
>> 6 ) A cost analysis will be require to decide between remat and spill.
>> This should be based on at least two factors register pressure and spill
>> cost
>>
>> Few points:
>> --------------
>> * The analysis pass to be addes as per (2) will use target specific
>> information
>> from TargetInstrInfo.cpp as the current remat infrastructure uses.
>>
>> * This approach will not be on demand as the current approach is (i.e
>> remat specific
>> code will be executed only if there is a spill) so the pass in (2) can be
>> an
>> overhead so we may want it to enable only for higher level of
>> optimization.
>>
>> * Will it be possible to use existing SCCP.cpp code with few modification
>> to lattice
>> and related mathematical operation so that it can serve both purpose?
>>
>> * No changes in current register allocators or spill framework will be
>> required
>> because remat entry point will be LiveRangeEdit.
>>
>> Any other way with less overhead is always welcomed.
>> Please help us developing a plan to implement this.
>>
>> Hoping for comments!
>>
>> Sincerely,
>> Vivek
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160919/dfa6894a/attachment.html>