Asserts in bundleWithPred() and bundleWithSucc()

Jakob,

  I have a question about the following (four) asserts recently added in
bundleWithPred() and bundleWithSucc() (see below). What is the real danger
of reasserting a connection even if it already exist? My problem with them
happens when I try to call finalizeBundle() on an existing bundle to which I
have added a new instruction. The goal - a new bundle header with liveness
abbreviation, but because of these asserts I now have to unbundle all, and
re-bundle them right back again for no obvious benefit...
  In other words, may I suggest removing them rather than adding new
methods?... or do you have a better suggestion?

Thanks.

Sergei

void MachineInstr::bundleWithPred() {
  assert(!isBundledWithPred() && "MI is already bundled with its
predecessor"); <<<<<<<<<<<<
  setFlag(BundledPred);
  MachineBasicBlock::instr_iterator Pred = this;
  --Pred;
  assert(!Pred->isBundledWithSucc() && "Inconsistent bundle flags");
<<<<<<<<<<<<<
  Pred->setFlag(BundledSucc);
}

void MachineInstr::bundleWithSucc() {
  assert(!isBundledWithSucc() && "MI is already bundled with its
successor"); <<<<<<<<<<<<<
  setFlag(BundledSucc);
  MachineBasicBlock::instr_iterator Succ = this;
  ++Succ;
  assert(!Succ->isBundledWithPred() && "Inconsistent bundle flags");
<<<<<<<<<<<<<<
  Succ->setFlag(BundledPred);
}

I have a question about the following (four) asserts recently added in
bundleWithPred() and bundleWithSucc() (see below). What is the real danger
of reasserting a connection even if it already exist?

The intention was to identify code that may have been converted from the old style a little too quickly. I wanted to avoid bugs from a global s/setIsInsideBundle/bundleWithPred/g search and replace.

My problem with them
happens when I try to call finalizeBundle() on an existing bundle to which I
have added a new instruction. The goal - a new bundle header with liveness
abbreviation, but because of these asserts I now have to unbundle all, and
re-bundle them right back again for no obvious benefit...

finalizeBundle is calling 'MIBundleBuilder Bundle(MBB, FirstMI, LastMI)' which ought to work with pre-bundled instructions. FirstMI and LastMI must be pointing at bundle boundaries, but you shouldn't need to unbundle everything.

Which iterators are you passing to finalizeBundle?

/jakob

Jakob,

The intention was to identify code that may have been converted from
the old style a little too quickly. I wanted to avoid bugs from a
global s/setIsInsideBundle/bundleWithPred/g search and replace.

  This is a good intent. Maybe a bit temporal but sound nevertheless.

finalizeBundle is calling 'MIBundleBuilder Bundle(MBB, FirstMI,
LastMI)' which ought to work with pre-bundled instructions.

Not exactly. Let me illustrate couple cases here (for illustration purposes
"^" means "isBundledWithPred()" and "v" means "isBundledWithSucc()"):

I have the following (existing) bundle for which I want to regenerate the
bundle header (You see that %R17 is not currently in the def list for the
bundle header).

  v BUNDLE %P3<imp-def>, %R29<imp-use>, %D8<imp-use,kill>,
%D9<imp-use,kill>, %R6<imp-use>
*^v STrid_indexed %R29, 80, %D8<kill>; mem:ST8[FixedStack2]
*^v STrid_indexed %R29, 72, %D9<kill>; mem:ST8[FixedStack3]
*^v %P3<def> = CMPEQri %R6, 0
*^ %R17<def> = TFR_cdnNotPt %P3<internal>, %R1
  v BUNDLE %R29<imp-use>, %D10<imp-use,kill>, %R7<imp-use>, %D6<imp-use>
(next bundle).

finalizeBundle() is called with:

FirstMI == STrid_indexed %R29, 80, %D8<kill>; mem:ST8[FixedStack2]
LastMI == BUNDLE %R29<imp-use>, %D10<imp-use,kill>, %R7<imp-use>,
%D6<imp-use>

From here this assert is triggered:

void MachineInstr::bundleWithSucc() {
  assert(!isBundledWithSucc() && "MI is already bundled with its
successor"); <<<<<<<<<<<<<<<<<<<<<<<<
  setFlag(BundledSucc);
  MachineBasicBlock::instr_iterator Succ = this;
  ++Succ;
  assert(!Succ->isBundledWithPred() && "Inconsistent bundle flags");
  Succ->setFlag(BundledPred);
}

Here is the call stack:

#3 ... in llvm::MachineInstr::bundleWithSucc (this=0x4c6aa20) at
...lib/CodeGen/MachineInstr.cpp:882
#4 ... in llvm::MIBundleBuilder::insert (this=0x7fffffff7dc0, I=...,
MI=0x4c6aa20) at ...include/llvm/CodeGen/MachineInstrBuilder.h:417
#5 ... in llvm::MIBundleBuilder::prepend (this=0x7fffffff7dc0,
MI=0x4c6aa20) at ...include/llvm/CodeGen/MachineInstrBuilder.h:435
#6 ... in llvm::finalizeBundle (MBB=..., FirstMI=..., LastMI=...) at
...lib/CodeGen/MachineInstrBundle.cpp:112

  Let me give you another example though. I have the following existing
bundle:

    v BUNDLE %R0<imp-def,dead>, %PC<imp-def>, %R18<imp-use>
  *^v %R0<def> = AND_ri %R18, 128
  *^ JMP_EQriPnt_nv_V4 %R0<kill,internal>, 0, <BB#2>, %PC<imp-def>

I need to move an instruction into this bundle from another location and
insert it _between_ AND_ri and JMP_EQriPnt_nv_V4. I use MBB->splice(...) to
do that. Let's pretend that moved instruction was not bundled. New
instruction is pointed to by MachineBasicBlock::instr_iterator MII. New
bundle right after splice is:

    v BUNDLE %R0<imp-def,dead>, %PC<imp-def>, %R18<imp-use>
  *^v %R0<def> = AND_ri %R18, 128
  * %R3<def> = HexagonEXTRACTU_ri_Inst %R18, 4, 3 <<<<<<<<<<<<<<<<<<<
MII
  *^ JMP_EQriPnt_nv_V4 %R0<kill,internal>, 0, <BB#2>, %PC<imp-def>

Now I have to integrate MII into the new bundle. As I do this:

MII->bundleWithPred();

I run into this assert:

void MachineInstr::bundleWithPred() {
  assert(!isBundledWithPred() && "MI is already bundled with its
predecessor");
  setFlag(BundledPred);
  MachineBasicBlock::instr_iterator Pred = this;
  --Pred;
  assert(!Pred->isBundledWithSucc() && "Inconsistent bundle flags");
<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  Pred->setFlag(BundledSucc);
}

Now think about what I need to do for all possible cases when original
instruction was previously bundled and that bundle also needs updating....
and on top of that almost every time I call bundleWith*() I have to guard it
with the check for isBundledWith*(). The code looks rather ugly at that
point...

...and if I start dissolve and reconstruct bundles every time I need to
manipulate them, I think original intent becomes a bit overly
constraining...

Sergei

Jakob,

The intention was to identify code that may have been converted from
the old style a little too quickly. I wanted to avoid bugs from a
global s/setIsInsideBundle/bundleWithPred/g search and replace.

This is a good intent. Maybe a bit temporal but sound nevertheless.

finalizeBundle is calling 'MIBundleBuilder Bundle(MBB, FirstMI,
LastMI)' which ought to work with pre-bundled instructions.

Not exactly. Let me illustrate couple cases here (for illustration purposes
"^" means "isBundledWithPred()" and "v" means "isBundledWithSucc()"):

I have the following (existing) bundle for which I want to regenerate the
bundle header (You see that %R17 is not currently in the def list for the
bundle header).

v BUNDLE %P3<imp-def>, %R29<imp-use>, %D8<imp-use,kill>,
%D9<imp-use,kill>, %R6<imp-use>
*^v STrid_indexed %R29, 80, %D8<kill>; mem:ST8[FixedStack2]
*^v STrid_indexed %R29, 72, %D9<kill>; mem:ST8[FixedStack3]
*^v %P3<def> = CMPEQri %R6, 0
*^ %R17<def> = TFR_cdnNotPt %P3<internal>, %R1
v BUNDLE %R29<imp-use>, %D10<imp-use,kill>, %R7<imp-use>, %D6<imp-use>
(next bundle).

finalizeBundle() is called with:

FirstMI == STrid_indexed %R29, 80, %D8<kill>; mem:ST8[FixedStack2]
LastMI == BUNDLE %R29<imp-use>, %D10<imp-use,kill>, %R7<imp-use>,
%D6<imp-use>

From here this assert is triggered.

Yes, that sounds like correct behavior to me because FirstMI is pointing inside an existing bundle. I assume your intent is to remove the old BUNDLE header after finalizeBundle() inserted a new one. In this case you should either erase the old BUNDLE first, or unbundle it from the instructions you are trying to finalize.

Let me give you another example though. I have the following existing
bundle:

   v BUNDLE %R0<imp-def,dead>, %PC<imp-def>, %R18<imp-use>
*^v %R0<def> = AND_ri %R18, 128
*^ JMP_EQriPnt_nv_V4 %R0<kill,internal>, 0, <BB#2>, %PC<imp-def>

I need to move an instruction into this bundle from another location and
insert it _between_ AND_ri and JMP_EQriPnt_nv_V4. I use MBB->splice(...) to
do that. Let's pretend that moved instruction was not bundled. New
instruction is pointed to by MachineBasicBlock::instr_iterator MII. New
bundle right after splice is:

   v BUNDLE %R0<imp-def,dead>, %PC<imp-def>, %R18<imp-use>
*^v %R0<def> = AND_ri %R18, 128
* %R3<def> = HexagonEXTRACTU_ri_Inst %R18, 4, 3 <<<<<<<<<<<<<<<<<<<
MII
*^ JMP_EQriPnt_nv_V4 %R0<kill,internal>, 0, <BB#2>, %PC<imp-def>

Now I have to integrate MII into the new bundle. As I do this:

MII->bundleWithPred();

The inconsistent flags should never happen. It should always be the case that:

if II->isBundledWithPred() then prior(II)->isBundledWithSucc()
if II->isBundledWithSucc() then next(II)->isBundledWithPRed()

In fact, the machine code verifier also checks this invariant now.

I changed MBB->splice() to not accept instr_iterators so what you're doing wouldn't be possible. It is hard to add enough assertions, though.

To move instructions into a bundle, I recommend that you use MIBundleBuilder with removeFromBundle():

  Bundle.insert(I, MI->removeFromBundle())

This way you can insert instructions at any position in a bundle without special casing the first and last positions. You can even have MIBundleBuilder represent an empty bundle.

MBB->splice() is ambiguous when given an insert position between two existing bundles. Did you mean to append to the first bundle, prepend to the second bundle, or did you want a stand-alone instruction between the bundles? MIBundleBuilder resolves that ambiguity.

/jakob

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 :slight_smile: ...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... and if you do not remove it first,
MBB.insert(I, MI); will assert with:

lib/CodeGen/MachineBasicBlock.cpp:94: void
llvm::ilist_traits<llvm::MachineInstr>::addNodeToList(llvm::MachineInstr*):
Assertion `N->getParent() == 0 && "machine instruction already in a basic
block"' failed.

Sergei

Yes, that is a problem because MIBundleBuilder keeps an End iterator.

What do you think, should we add a Bundle.moveIntoBundle() function?

/jakob

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

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

The liveness update Jakob described could also be used for efficient incremental update. In fact, we can keep the handleMove API as a convenient wrapper. LiveIntervals simply needs to know which instruction moved.

The more general API provides flexibility for clients that may perform a sequence of steps where the intermediate liveness is either inconsistent or inefficient to compute. It would also provide a way to recompute liveness after a pass which can be extremely useful for debugging and verification.

Regarding global liveness. If you only care about extended basic blocks that are sequentially numbered, then I don't think we should talk about global liveness update, which is a different problem altogether. Handling extended basic blocks would make the API messy but should be just as efficient as local liveness. The only difference is that some of your intervals won't end at uses.

-Andy

Hi,

I am trying to build the code that I've checked out from the svn repository (revision 175705). I can do make, but not make check, it reports the `No site specific configuration available!' error.

Output of make check:
llvm[0]: Running test suite
make[1]: Entering directory `/home/ppenzin/tmp/llvm/build_x86-64/test'
Making LLVM 'lit.site.cfg' file...
Making LLVM unittest 'lit.site.cfg' file...
( ulimit -t 600 ; ulimit -d 512000 ; ulimit -m 512000 ; \
           /usr/bin/python /home/ppenzin/tmp/llvm/utils/lit/lit.py -s -v . )
lit.py: lit.cfg:120: fatal: No site specific configuration available!
make[1]: *** [check-local] Error 2
make[1]: Leaving directory `/home/ppenzin/tmp/llvm/build_x86-64/test'
make: *** [check] Error 2

I don't see any information about this in archives, any pointers will be greatly appreciated!

Best,
Peter

Never mind, got it to work.

-Peter