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

Hi,

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

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 ?

We would like to follow llvm evolutions and preserve the core 
implementations as much as possible.

Thanks in advance,

Ivan

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?

- 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?

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?

/jakob

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>