[LLVMdev] Asserts in bundleWithPred() and bundleWithSucc()

[Sergei Larin]

Jakob,

  Consider a counterexample. In a late pass I speculatively move
instructions between BBs to improve code density and handle some peculiar
back end specific situations which could not be handled in earlier passes. I
move instructions one at a time. Currently I do it in a worklist fashion - I
collect several possible candidates, and then actually move one. Some moves
are _speculative_. Next move after that is totally dependent on up-to-date
liveness information. If/when we decide to do proper _global_ instruction
scheduling, we will need this mechanism to perform flawlessly.
  On a low level, if I start with a correct set of live-ins, I can do
_incremental_ liveness update pretty much always (I do skip some nasty
corner cases for parallel semantics). My current problem is that I had to
implement this whole incremental liveness analysis in my late pass...
(because LIS does not work that late)... which is something I do not want to
carry forward for too long if I can avoid it.

  In short, I do need a version of "move instruction" (or handleMove) that
would produce accurate global liveness after its use. If 

LIS.beginChanges(); // change // LIS.endChanges();

will work as fast and efficiently, no problem then, but I have this feeling
that incremental liveness update (when possible) will be easier and cheaper
than full scan.

  You have asked me before - when we are going to upstream the code that
does the global code motion - I can tell now that we are getting closer, and
I would prefer to do any needed changes to it now rather than later.

Thanks.

Sergei

---
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by
The Linux Foundation


> -----Original Message-----
> From: Jakob Stoklund Olesen [mailto:stoklund at 2pi.dk]
> Sent: Monday, February 04, 2013 6:09 PM
> To: Sergei Larin
> Cc: llvmdev at cs.uiuc.edu
> Subject: Re: Asserts in bundleWithPred() and bundleWithSucc()
> 
> 
> On Feb 4, 2013, at 3:44 PM, "Sergei Larin" <slarin at codeaurora.org>
> wrote:
> 
> >  Seems like an easy solution for this case... But let me ask you a
> > more general question.
> > The reason I kept on hanging on to the MBB->splice was (probably
> > outdated) assumption that it will one day properly update liveness
> for
> > instructions it moves... That is a serious matter for what I am
> trying
> > to do (global code motion in presence of bundles).
> >
> >  What is the current thinking? Will we ever be able to move an
> > instruction between BBs and have liveness updated properly? If so,
> > what interface will we need for that? Based on your answer, original
> > question might become a bit more easy to answer.
> 
> Good question.
> 
> We currently have handleMove() which will update liveness after moving
> a single instruction within a basic block. I could see it being
> extended to handle globally moved instructions as well.
> 
> I am wary of an API that automatically updates liveness because it can
> be expensive to maintain valid liveness along a number of intermediate
> steps, compared to recomputing liveness in batch after multiple
> changes.
> 
> Consider hoisting chained instructions out of a loop one at a time. The
> live ranges of the intermediate steps look completely different from
> the final result.
> 
> So for a future automatic liveness API, I imagine something like:
> 
>   LIS.beginChanges();
>   ..
>   Move multiple instructions around.
>   ..
>   LIS.endChanges();
> 
> [Or it could use RAII, that's not important]
> 
> MachineFunction would provide observer hooks that LIS can use to
> collect a set of changed instructions. The call to LIS.endChanges()
> would then recompute the invalid live ranges.
> 
> /jakob