SplitKit: Correctly implement partial copies

[MatzeB]

Summary

• This fixes a bug where subregisters incompatible with the given vreg were choosen.
• Implement the case where multiple copies are necessary to cover a given lanemask.

rdar://30388692

[rampitec]

Thank you!

[rampitec]

defFromParent supposed to return a single def, how does it work if there is more than one? I suppose it does work as you should have tests passed...

[kparzysz]

lib/CodeGen/SplitKit.cpp

551 ↗

(On Diff #89958)

Is there any guarantee that this loop will actually terminate? In other words, do we know that the set PossibleIndexes covers the lanes completely?

572 ↗

(On Diff #89958)

Would it make sense to add || BestCover <= 0?

[MatzeB]

Redo a lot of this patch:

• Add more tests so that the code runs in more situations and screwed up liveranges are detected.
• Use instruction bundles during splitting/regalloc and expand them into a series of instruction at VirtRegMap time. I spend days trying to get this to work by directly creating a sequence of instructions in splitkit but it turned out to be extremely hard to stop liverange splitting between the copies in an infinite loop or getting a spill/reload for every one of the copies in a series; the bundle based approach only needed nearly no changes outside of splitkit itself except for the expansion code and fixing some virtregmap bugs with bundles.

[MatzeB]

In D30438#688098, @rampitec wrote:

defFromParent supposed to return a single def, how does it work if there is more than one? I suppose it does work as you should have tests passed...

Indeed this turned out to screw up the liveness and I just wasn't able to catch it with the small amount of tests we had before. Hence this new version of the patch.

[MatzeB]

Upload the correct patch this time!

Redo a lot of this patch:

• Add more tests so that the code runs in more situations and screwed up liveranges are detected.
• Use instruction bundles during splitting/regalloc and expand them into a series of instruction at VirtRegMap time. (I spend days trying to get this to work by directly creating a sequence of instructions in splitkit but it turned out to be extremely hard to stop liverange splitting between the copies in an infinite loop or getting a spill/reload for every one of the copies in a series; the bundle based approach only needed nearly no changes outside of splitkit itself except for the expansion code and fixing some virtregmap bugs with bundles.)

[MatzeB]

lib/CodeGen/SplitKit.cpp

551 ↗

(On Diff #89958)

This specific loop only checks each subregister index once and will therefore terminate.

The later loop is repeated as we are able to remove bits from the lanemask. If we fail to find a subregister index that removes any of the bits we will end up in the report_fatal_error() cases.

572 ↗

(On Diff #89958)

BestCover <= 0 can happen and is fine (it just means the best we could find is an index that covers more unnecessary lanes that we already covered anyway, than lanes we haven't covered yet).

[rampitec]

lib/CodeGen/VirtRegMap.cpp

383

I think it can break something which was bundled not by SplitKit. I wish we could mark these somehow... It will not happen now because we do not use bundles, but potentially a problem. Maybe insert some sort of a marker into the bundle or slot, or create a new MIFlag? Ideally of course it shall not use bundles just to keep LIS correct :(

[rampitec]

The other question, what would happen if target implements its own addOptimizedRegAlloc and skips VirtRegRewriter? I guess in this case copies will remain bundled. Looks like NVPTX does not use it.

[MatzeB]

In D30438#700956, @rampitec wrote:

The other question, what would happen if target implements its own addOptimizedRegAlloc and skips VirtRegRewriter? I guess in this case copies will remain bundled. Looks like NVPTX does not use it.

If they have their own regalloc they probably cannot use SplitKit either. If they do use SplitKit, well they have to implement their own expansion mechanism (though it seems SplitKit has references to VirtRegMap so I don't think you realistically will use SplitKit without the VirtRegRewriter).

lib/CodeGen/VirtRegMap.cpp

383

I was hoping that targets would always use a target specific bundle header instructions, so this would be the only situation in which we have a headerless bundle. Admittedly this is somewhat weak, but I hoped we can delay this discussion until we actually have targets using bundles pre-regalloc more.

[rampitec]

lib/CodeGen/VirtRegMap.cpp

383

Its almost the moment I'm thinking of adding it ;) It will not be all copy though.

[MatzeB]

lib/CodeGen/VirtRegMap.cpp

383

But do you plan to use bundles without a "header" (i.e. the first instruction is not some target-specific instruction that describes the type of the bundle?)

[rampitec]

lib/CodeGen/VirtRegMap.cpp

383

OK, agree, I do not.

[kparzysz]

lib/CodeGen/SplitKit.cpp

572 ↗

(On Diff #89958)

Well, wasn't that the original problem, i.e. that we copied too much (which then ended up clobbering lanes marked as unused)?

[MatzeB]

lib/CodeGen/SplitKit.cpp

572 ↗

(On Diff #89958)

No, the PossibleIndexes vector only contains indexes that cover bits that we are allowed to cover. The BestCover is solely about minimizing the amount of lanes we copy twice. We will not copy lanes that we are not supposed to copy.

[kparzysz]

lib/CodeGen/SplitKit.cpp

597 ↗

(On Diff #91662)

This doesn't need to be addressed in this patch, but on a general note---this would be a case where the compiler corners itself into such a situation. It's not a symptom of simply a bug, but rather a design that can end up in a dead end. Ideally, we should avoid getting here early enough to have other options.

572 ↗

(On Diff #89958)

Ok, I see it now.

test/CodeGen/AMDGPU/splitkit.mir

35 ↗

(On Diff #91662)

This is the only CHECK like in this function. Did it use to crash?

[MatzeB]

lib/CodeGen/SplitKit.cpp

597 ↗

(On Diff #91662)

I think this cannot happen. As for liveness to split up into a given lanemask we need an operand in the function that uses a subregister index with such a lanemask. But that would mean we can use the same index to implement the COPY.

I'm not a 100% sure that I am not missing something here so I left this check in to better abort than silently infinite loop if I did :).

[MatzeB]

test/CodeGen/AMDGPU/splitkit.mir

35 ↗

(On Diff #91662)

This should indeed have more CHECKs. I'll add them.

[qcolombet]

LGTM with more checks in the test.

test/CodeGen/AMDGPU/splitkit.mir

35 ↗

(On Diff #91662)

Please add more checks indeed.

include/llvm/CodeGen/SlotIndexes.h

SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late = false) {
       if (dist == 0)
         renumberIndexes(newItr);
 
       SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block);
       mi2iMap.insert(std::make_pair(&MI, newIndex));
       return newIndex;
     }
 
-    /// Remove the given machine instruction from the mapping.
-    void removeMachineInstrFromMaps(MachineInstr &MI) {
-      // remove index -> MachineInstr and
-      // MachineInstr -> index mappings
-      Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI);
-      if (mi2iItr != mi2iMap.end()) {
-        IndexListEntry *miEntry(mi2iItr->second.listEntry());
-        assert(miEntry->getInstr() == &MI && "Instruction indexes broken.");
-        // FIXME: Eventually we want to actually delete these indexes.
-        miEntry->setInstr(nullptr);
-        mi2iMap.erase(mi2iItr);
-      }
-    }
+    /// Removes machine instruction (bundle) \p MI from the mapping.
+    /// This should be called before MachineInstr::eraseFromParent() is used to
+    /// remove a whole bundle or an unbundled instruction.
+    void removeMachineInstrFromMaps(MachineInstr &MI);
+
+    /// Removes a single machine instruction \p MI from the mapping.
+    /// This should be called before MachineInstr::eraseFromBundle() is used to
+    /// remove a single instruction (out of a bundle).
+    void removeSingleMachineInstrFromMaps(MachineInstr &MI);
 
     /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
     /// maps used by register allocator. \returns the index where the new
     /// instruction was inserted.
     SlotIndex replaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI) {
       Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI);
       if (mi2iItr == mi2iMap.end())
         return SlotIndex();

lib/CodeGen/SlotIndexes.cpp

bool SlotIndexes::runOnMachineFunction(MachineFunction &fn) {
   std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare());
 
   DEBUG(mf->print(dbgs(), this));
 
   // And we're done!
   return false;
 }
 
+void SlotIndexes::removeMachineInstrFromMaps(MachineInstr &MI) {
+  assert(!MI.isBundledWithPred() &&
+         "Use removeSingleMachineInstrFromMaps() instread");
+  Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI);
+  if (mi2iItr == mi2iMap.end())
+    return;
+
+  SlotIndex MIIndex = mi2iItr->second;
+  IndexListEntry &MIEntry = *MIIndex.listEntry();
+  assert(MIEntry.getInstr() == &MI && "Instruction indexes broken.");
+  mi2iMap.erase(mi2iItr);
+  // FIXME: Eventually we want to actually delete these indexes.
+  MIEntry.setInstr(nullptr);
+}
+
+void SlotIndexes::removeSingleMachineInstrFromMaps(MachineInstr &MI) {
+  Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI);
+  if (mi2iItr == mi2iMap.end())
+    return;
+
+  SlotIndex MIIndex = mi2iItr->second;
+  IndexListEntry &MIEntry = *MIIndex.listEntry();
+  assert(MIEntry.getInstr() == &MI && "Instruction indexes broken.");
+  mi2iMap.erase(mi2iItr);
+
+  // When removing the first instruction of a bundle update mapping to next
+  // instruction.
+  if (MI.isBundledWithSucc()) {
+    // Only the first instruction of a bundle should have an index assigned.
+    assert(!MI.isBundledWithPred() && "Should have first bundle isntruction");
+
+    MachineBasicBlock::instr_iterator Next = std::next(MI.getIterator());
+    MachineInstr &NextMI = *Next;
+    MIEntry.setInstr(&NextMI);
+    mi2iMap.insert(std::make_pair(&NextMI, MIIndex));
+    return;
+  } else {
+    // FIXME: Eventually we want to actually delete these indexes.
+    MIEntry.setInstr(nullptr);
+  }
+}
+
 void SlotIndexes::renumberIndexes() {
   // Renumber updates the index of every element of the index list.
   DEBUG(dbgs() << "\n*** Renumbering SlotIndexes ***\n");
   ++NumGlobalRenum;
 
   unsigned index = 0;
 
   for (IndexList::iterator I = indexList.begin(), E = indexList.end();

lib/CodeGen/VirtRegMap.cpp

void VirtRegRewriter::handleIdentityCopy(MachineInstr &MI) const {
   // instruction to maintain this information.
   if (MI.getOperand(0).isUndef() || MI.getNumOperands() > 2) {
     MI.setDesc(TII->get(TargetOpcode::KILL));
     DEBUG(dbgs() << "  replace by: " << MI);
     return;
   }
 
   if (Indexes)
-    Indexes->removeMachineInstrFromMaps(MI);
-  MI.eraseFromParent();
+    Indexes->removeSingleMachineInstrFromMaps(MI);
+  MI.eraseFromBundle();
   DEBUG(dbgs() << "  deleted.\n");
 }
 
 void VirtRegRewriter::rewrite() {
   bool NoSubRegLiveness = !MRI->subRegLivenessEnabled();
   SmallVector<unsigned, 8> SuperDeads;
   SmallVector<unsigned, 8> SuperDefs;
   SmallVector<unsigned, 8> SuperKills;
 
   for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
        MBBI != MBBE; ++MBBI) {
     DEBUG(MBBI->print(dbgs(), Indexes));
     for (MachineBasicBlock::instr_iterator
            MII = MBBI->instr_begin(), MIE = MBBI->instr_end(); MII != MIE;) {
       MachineInstr *MI = &*MII;
       ++MII;
 
       for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
            MOE = MI->operands_end(); MOI != MOE; ++MOI) {
         MachineOperand &MO = *MOI;
for (MachineBasicBlock::instr_iterator
                 // completely undefined (and we are not adding super-register
                 // defs).
                 MO.setIsUndef(true);
             } else if (!MO.isDead()) {
               assert(MO.isDef());
             }
           }
 
-          // The <def,undef> flag only makes sense for sub-register defs, and
-          // we are substituting a full physreg.  An <imp-use,kill> operand
-          // from the SuperKills list will represent the partial read of the
-          // super-register.
-          if (MO.isDef())
+          // The <def,undef> and <def,internal> flags only make sense for
+          // sub-register defs, and we are substituting a full physreg.  An
+          // <imp-use,kill> operand from the SuperKills list will represent the
+          // partial read of the super-register.
+          if (MO.isDef()) {
             MO.setIsUndef(false);
+            MO.setIsInternalRead(false);
+          }
 
           // PhysReg operands cannot have subregister indexes.
           PhysReg = TRI->getSubReg(PhysReg, SubReg);
           assert(PhysReg && "Invalid SubReg for physical register");
           MO.setSubReg(0);
         }
         // Rewrite. Note we could have used MachineOperand::substPhysReg(), but
         // we need the inlining here.