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

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




---
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: Friday, February 01, 2013 6:15 PM
> To: Sergei Larin
> Cc: llvmdev at cs.uiuc.edu
> Subject: Re: Asserts in bundleWithPred() and bundleWithSucc()
> 
> 
> On Feb 1, 2013, at 3:43 PM, "Sergei Larin" <slarin at
codeaurora.org>
> wrote:
> 
> > 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

On Feb 4, 2013, at 8:59 AM, "Sergei Larin" <slarin at
codeaurora.org> wrote:
> 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 :) ...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



---
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 11:53 AM
> To: Sergei Larin
> Cc: llvmdev at cs.uiuc.edu
> Subject: Re: Asserts in bundleWithPred() and bundleWithSucc()
> 
> 
> On Feb 4, 2013, at 8:59 AM, "Sergei Larin" <slarin at
codeaurora.org>
> wrote:
> 
> > 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