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

[James Molloy via llvm-dev]

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?

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/8d1a66ea/attachment.html>