llvm dev - Jun 2012 - [LLVMdev] Instruction bundles before RA: Rematerialization

Hi Jakob,

2012/6/6 Jakob Stoklund Olesen <stoklund at 2pi.dk <mailto:stoklund at
2pi.dk>>


    On Jun 6, 2012, at 2:53 AM, Ivan Llopard <ivanllopard at gmail.com
    <mailto:ivanllopard at gmail.com>> wrote:

     > We have a new BE for a VLIW-like processor and I'm currently
    working on
     > instruction bundles. Ideally, I'd like to have bundles *before* RA
to
     > model certain constraints, e.g. the exposed one by Tzu-Chien a
    while ago
     > in his thread
     > http://lists.cs.uiuc.edu/pipermail/llvmdev/2005-September/004798.html

    The bundle support in the tree should handle constraints like that.
    The register allocator basically sees bundles as single instructions
    when computing interference.

     > In order to build bundles, we have added a new bottom-up MIScheduler,
     > right after reg coalescing, which behaves much like
    ScheduleDAGVLIW but
     > without hazard recognizing. Due to some tricky instructions, we
    cannot
     > schedule on the DAG. Bundles are built at exitRegion() in the
    scheduling
     > process and the live interval information is updated correctly. After
     > this, the RA is aware of bundles, at least from a LiveInterval
    point of
     > view, and I had some problems regarding the rematerialization.
     >
     > AFAIK, the RA cannot remat if the target instruction is not the
    bundle's
     > header.
     > For this, I rather need a light bundle representation, or no
    bundle at
     > all, so it can remat the right instruction with one condition: the
     > remated location should preserve bundles. Nevertheless, for many
    other
     > actions like LI splitting, the current representation works very
    well.
     >
     > In general, I want the RA to preserve bundles as well as to be
    able to
     > model the constraint presented above in the thread.
     > Should I fix the rematerialization code to look for the right
     > instruction into the current bundle ?
     > What's the direction you are following about instruction bundling
?

    Remat is a problem because it breaks the abstraction of treating
    whole bundles as instructions. There are two issues:

    - Should we rematerialize the full bundle defining a value, or
    should we try to dig out the 'real' def inside the bundle?


The second option is the preferred one for us. The remated instruction 
should create a new bundle which may be merged with other bundles later 
by custom passes. The same condition applies for copy insertions.


    - After remat, we run dead code elimination in case the original def
    has no more uses. Again, should DCE erase a single instruction from
    inside a bundle, or should we erase the full bundle once all its
    defs are dead?


In our particular case, the RA can freely remove instructions from a 
bundle without any special constraint. We don't need to wait till all 
defs inside a bundle are dead, which in some situations it may never happen.


    Ideally, I would like to treat the inside of a bundle like a black
    box that only the target understands. I am not too happy about
    erasing instructions inside bundles without some help from the target.

    How do you need remat to work?


As described above.

I understand your concern, other architectures may have stronger 
constraints or use bundles for other purposes (ARM?) which makes the 
task non-trivial.
We have a very particular VLIW architecture with complex operators but 
fewer constraints regarding the packet building and mangling. We need 
remat to work because spill is forbidden for a certain reg class.

Do you plan to add more hooks in TargetLowering to remat?


    /jakob



-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120607/a2af9f19/attachment.html>

I should probably voice our point of view as well… Hexagon is another VLIW
target with “non standard” demands for bundling.

 

  I think Jacob has summarized current view of bundles as “black box” rather
precise, but I should say that our view of bundles is way more fluid and open
than that.

To avoid going into lengthy discussion, let me just say – bundling for us is not
a single occurrence, but rather a multi step process, with individual
instructions moved between bundles (and potentially between blocks) multiple
times. Current infrastructure does not support this kind of freedom – seemingly
more out of philosophy rather than from engineering point of view.

 

  Taking on Ivan’s question about remat, I would probably prefer affected
bundles generically “disassembled” (if possible) with liveness correctly
updated, with a following (machine specific pass) being able to re-bundle.  This
of cause not always possible since some parallel semantics are not being
expressible in serial code, but those rare “swap” like cases could be left
intact (bundled). As far as I understand remat should never come “inside” such
circular dependency without breaking it, so it should work just fine.

Generally as far as I concern, there is no way “generic” (platform independent)
code can add instructions to bundles optimally. In the given example it is a job
for Post RA scheduler… but before this could happen, a lot of infrastructural
changes should be put in place.

 

Sergei 

 

--

Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum.

 

From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On
Behalf Of Ivan Llopard
Sent: Thursday, June 07, 2012 3:26 AM
To: Jakob Stoklund Olesen
Cc: LLVM Developers Mailing List
Subject: Re: [LLVMdev] Instruction bundles before RA: Rematerialization

 

Hi Jakob,

2012/6/6 Jakob Stoklund Olesen <stoklund at 2pi.dk>


On Jun 6, 2012, at 2:53 AM, Ivan Llopard <ivanllopard at gmail.com> wrote:
> We have a new BE for a VLIW-like processor and I'm currently working on
> instruction bundles. Ideally, I'd like to have bundles *before* RA to
> model certain constraints, e.g. the exposed one by Tzu-Chien a while ago
> in his thread
> http://lists.cs.uiuc.edu/pipermail/llvmdev/2005-September/004798.html
The bundle support in the tree should handle constraints like that. The register
allocator basically sees bundles as single instructions when computing
interference.

> In order to build bundles, we have added a new bottom-up MIScheduler,
> right after reg coalescing, which behaves much like ScheduleDAGVLIW but
> without hazard recognizing. Due to some tricky instructions, we cannot
> schedule on the DAG. Bundles are built at exitRegion() in the scheduling
> process and the live interval information is updated correctly. After
> this, the RA is aware of bundles, at least from a LiveInterval point of
> view, and I had some problems regarding the rematerialization.
>
> AFAIK, the RA cannot remat if the target instruction is not the
bundle's
> header.
> For this, I rather need a light bundle representation, or no bundle at
> all, so it can remat the right instruction with one condition: the
> remated location should preserve bundles. Nevertheless, for many other
> actions like LI splitting, the current representation works very well.
>
> In general, I want the RA to preserve bundles as well as to be able to
> model the constraint presented above in the thread.
> Should I fix the rematerialization code to look for the right
> instruction into the current bundle ?
> What's the direction you are following about instruction bundling ?
Remat is a problem because it breaks the abstraction of treating whole bundles
as instructions. There are two issues:

- Should we rematerialize the full bundle defining a value, or should we try to
dig out the 'real' def inside the bundle?


The second option is the preferred one for us. The remated instruction should
create a new bundle which may be merged with other bundles later by custom
passes. The same condition applies for copy insertions.


- After remat, we run dead code elimination in case the original def has no more
uses. Again, should DCE erase a single instruction from inside a bundle, or
should we erase the full bundle once all its defs are dead?


In our particular case, the RA can freely remove instructions from a bundle
without any special constraint. We don't need to wait till all defs inside a
bundle are dead, which in some situations it may never happen.
 


Ideally, I would like to treat the inside of a bundle like a black box that only
the target understands. I am not too happy about erasing instructions inside
bundles without some help from the target.

How do you need remat to work?


As described above.

I understand your concern, other architectures may have stronger constraints or
use bundles for other purposes (ARM?) which makes the task non-trivial.
We have a very particular VLIW architecture with complex operators but fewer
constraints regarding the packet building and mangling. We need remat to work
because spill is forbidden for a certain reg class.

Do you plan to add more hooks in TargetLowering to remat?

 


/jakob

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120607/64e4bcb9/attachment.html>

On Jun 7, 2012, at 10:25 AM, "Sergei Larin" <slarin at
codeaurora.org> wrote:
> Generally as far as I concern, there is no way “generic” (platform
independent) code can add instructions to bundles optimally
I agree, there are too many ways of modeling stuff with bundles. That is why I
took the philosophical stance of treating bundles as black boxes during RA. I
think the target should be involved whenever bundles are formed, and we
shouldn't delete instructions from inside bundles without permission from
the target.

I think we need to tweak some of the TargetInstrInfo hooks to make bundle remat
possible. I would like your input.

Rematerialization has multiple steps:

1. Feasibility. RA knows the bundle defining a given SSA value of a virtual
register. It calls TII.isTriviallyReMaterializable() to determine if the
defining instruction can (and should) be rematerialized. See
LiveRangeEdit::anyRematerializable().

2. Feasibility at desired location. LiveRangeEdit::canRematerializeAt() then
checks that the instruction can be rematerialized at the new location. This can
fail if the instruction depends on virtual register values that are not
available at the new location.

3. Remat. LiveRangeEdit::rematerializeAt() calls TII.reMaterialize() (sic) to
insert a copy of the defining instruction at the new location.

4. Shrink original live range. The original live range may be smaller after some
uses have been rematerialized. This may discover dead defs if there are no
remaining uses.

5. LiveRangeEdit::eliminateDeadDefs() erases the dead defs.

It looks like each of these steps require some help from the target if they are
to handle bundles.

/jakob

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120607/21a32e04/attachment.html>