[LLVMdev] Instruction bundles before RA: Rematerialization

[Sergei Larin]

Jakob,

 

  Please see my comments below. Hope this helps.

 

Sergei

 

--

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

 

From: Jakob Stoklund Olesen [mailto:stoklund at 2pi.dk] 
Sent: Thursday, June 07, 2012 1:02 PM
To: Sergei Larin
Cc: 'Ivan Llopard'; 'LLVM Developers Mailing List'
Subject: Re: [LLVMdev] Instruction bundles before RA: Rematerialization

 

 

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().

 

 

[Larin, Sergei] Obviously if you treat bundle as a black box this does not
make much sense. or isTriviallyReMaterializable() should be able to parse
bundle and produce compound answer. Problem is - you will not be able to
find many opportunities like that. On the other hand if you detect a
_single_ instruction as a remat candidate inside a bundle, you might chose
to dissolve (disassemble) the bundle (if possible, as I said before) and
treat new serial group as you normally would for remat. There should be a
platform dependent pass to rebundle this new serial sequence again, but even
if it is not done, but  if the dissolution was performed properly, this will
be a performance, not a correctness issue. As a side note, you might chose
simply remove desired instruction from the bundle (often it is possible and
trivial to do without affecting semantics) and proceed as described above.
_BUT_ instruction removal does need back end support. Example:

{ 

r0 = add (r0, r1);

P0 = cmp (r0.new, r0);

}

  The r0.new means that the new value of r0 is used (reg file bypass in the
same cycle). You can see all possible implications of this. To offload this
mental logic to the back end, we need a utility of form
CanMoveMIBeforeBundle(MI, BundleHeader)/ CanMoveMIAfterBundle(MI,
BundleHeader)/ MoveMIBeforeBundle(MI, BundleHeader)/ MoveMIAfterBundle(MI,
BundleHeader). Calling this repeatedly should achieve desired effect -
remove what could be removed, and live what needs to remain bundled intact.
The move utility can change instruction properly for each target.

 

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.

 

[Larin, Sergei] This looks similar to the previous case. Good thing that you
can potentially have zero cost remat (if you can place your new instruction
inside existing bundle), but to know this you need an answer _while_ you are
computing the cost. For that I can easily imagine a back end hook of
something like CanAddMIToBundle(MI, BundleHeader). This is often easier than
the previous task.

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

 

[Larin, Sergei] At this point you need to update liveness on bundle level,
and then update global picture. Updating liveness on bundle level also might
need help from the back end. See the above example with .new, and you can
easily imagine local defs/kills inside a bundle that should not even be
visible outside the black box. As of now I consider this mechanism somewhat
broken on trunk (it is overly pessimistic). but API in this case is rather
straightforward. 

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.

 

[Larin, Sergei] Last two should be easy with the above API support - if you
can CanMoveMIBeforeBundle(..) outside the bundle, you can use existing API
to delete it.

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/4beffa12/attachment.html>