llvm dev - Feb 2013 - [LLVMdev] Asserts in bundleWithPred() and bundleWithSucc()

Jakob,


  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.

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 5:17 PM
> To: Sergei Larin
> Cc: llvmdev at cs.uiuc.edu
> Subject: Re: Asserts in bundleWithPred() and bundleWithSucc()
> 
> 
> On Feb 4, 2013, at 3:02 PM, "Sergei Larin" <slarin at
codeaurora.org>
> wrote:
> 
> > Jakob,
> >
> >> ... In this case you should either erase the old BUNDLE first, or
> >> unbundle
> > it
> >> from the instructions you are trying to finalize.
> >
> > This is exactly my point - I have to unbundle everything to re-bundle
> > it back in :) ...but this case is trivial and I am OK with it. What
> is
> > more unclear to me is this.
> >
> > How do you use Bundle.insert(I, MI->removeFromBundle())
> >
> > Where MI == Bundle.End?
> >
> > This happens if I want to add unbundled instruction to a bundle that
> > immediately precedes it in the same BB. The moment you remove MI from
> > BB iterators will not work properly.
> 
> Yes, that is a problem because MIBundleBuilder keeps an End iterator.
> 
> What do you think, should we add a Bundle.moveIntoBundle() function?
> 
> /jakob

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

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