Keep dead inst copy from being deleted only when the inst is rematerializable

[wmi]

Summary

The patch is to fix the two bugs reported here: http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160418/349985.html

The fix is to allow the dead insts kept in DeadRemat only when they are rematerializable. Because isReallyTriviallyReMaterializableGeneric put many limits on rematerializable instructions, this fix can prevent instructions with tied virtual operands and instructions with virtual register uses from being kept in DeadRemat, so as to fix the problems in the report.

Also add the check "DeadRemat != nullptr" in the condition to put the dead insts in DeadRemat. Because for RegisterCoalescer, its DeadRemat is nullptr, and we want dead instructions in this phase to be eliminated normally.

[qcolombet]

Hi Wei,

Additing the alias analysis seem unreleated to me.
Could it be a separate patch?
Could you add a test case?

Cheers,
-Quentin

lib/CodeGen/LiveRangeEdit.cpp

331 ↗

(On Diff #54870)

Don't we already check that MI is triviallyReMaterializable before trying to rematerialize?
I.e., this is just an optimization to keep DeadRemats small, not the actual fix, right?

In other words, if this is the proposed fix, I think I miss something!

[wmi]

Additing the alias analysis seem unreleated to me.
Could it be a separate patch?

Adding alias analysis is because isTriviallyReMaterializable will use it. I am not sure whether separating the alias analysis part will cause unused-var-warning.

Could you add a test case?

Ok, will do that.

Thanks,
Wei.

lib/CodeGen/LiveRangeEdit.cpp

331 ↗

(On Diff #54870)

This patch is to fix the problems by keeping DeadRemats small.

For instruction like vreg1 = vreg2 + 3 which is not triviallyReMaterializable because it has a vreg use on rhs, if it is dead, previously we still put it in DeadRemats and fail to update the live interval after we delete it in postOptimization. This will cause verifier error.

Now we reduce the DeadRemats set to dead instructions which will truly possible to be used in rematerialization, we don't have to worry live interval update because instructions in DeadRemats won't have vreg use. vreg dest is a dummy register and its live interval has been properly set.

In other words, keep instructions in DeadRemats to a limited form enforced by triviallyReMaterializable, we can simplify some live interval update hassle and keep the machine verifier silent.

[qcolombet]

lib/CodeGen/LiveRangeEdit.cpp

331 ↗

(On Diff #54870)

That sounds more like a workaround for a more general liveness problem.
Those instructions are not supposed to be there and they *must* not affect the liveness of other the variables referenced in those instructions.

That being said, I could live with the fact that we do not push instructions that we know we won’t be able to rematerialize. But, this should not be considered to be the fix for the other problem. In other words, we need to find a way to properly update the liveness when we kill, but keep those instructions.

[wmi]

lib/CodeGen/LiveRangeEdit.cpp

331 ↗

(On Diff #54870)

Yes, in that sense, this is a workaround. I understand that suppose one day, we relax the constraints in triviallyReMaterializable and let more complex instructions become rematerializable, the problem will surface again. I will think about how to fix the problem.

[wmi]

Quentin, Is it ok to checkin the workaround for now as it has no downside? I havn't got time to solve the essential problem yet, but I will find the time.

Thanks,
Wei.

[qcolombet]

Hi Wei,

Sure, if it is required to unblock some other stuff, go for it.
However, file a PR so that we remember to revert the related patch and do the proper fix.

Cheers,
-Quentin

[wmi]

Filed a bug as a reminder: https://llvm.org/bugs/show_bug.cgi?id=28464

llvm/trunk/include/llvm/CodeGen/LiveRangeEdit.h

private:
   /// foldAsLoad - If LI has a single use and a single def that can be folded as
   /// a load, eliminate the register by folding the def into the use.
   bool foldAsLoad(LiveInterval *LI, SmallVectorImpl<MachineInstr*> &Dead);
 
   typedef SetVector<LiveInterval*,
                     SmallVector<LiveInterval*, 8>,
                     SmallPtrSet<LiveInterval*, 8> > ToShrinkSet;
   /// Helper for eliminateDeadDefs.
-  void eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink);
+  void eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink,
+                        AliasAnalysis *AA);
 
   /// MachineRegisterInfo callback to notify when new virtual
   /// registers are created.
   void MRI_NoteNewVirtualRegister(unsigned VReg) override;
 
   /// \brief Check if MachineOperand \p MO is a last use/kill either in the
   /// main live range of \p LI or in one of the matching subregister ranges.
   bool useIsKill(const LiveInterval &LI, const MachineOperand &MO) const;
public:
 
   /// eliminateDeadDefs - Try to delete machine instructions that are now dead
   /// (allDefsAreDead returns true). This may cause live intervals to be trimmed
   /// and further dead efs to be eliminated.
   /// RegsBeingSpilled lists registers currently being spilled by the register
   /// allocator.  These registers should not be split into new intervals
   /// as currently those new intervals are not guaranteed to spill.
   void eliminateDeadDefs(SmallVectorImpl<MachineInstr *> &Dead,
-                         ArrayRef<unsigned> RegsBeingSpilled = None);
+                         ArrayRef<unsigned> RegsBeingSpilled = None,
+                         AliasAnalysis *AA = nullptr);
 
   /// calculateRegClassAndHint - Recompute register class and hint for each new
   /// register.
   void calculateRegClassAndHint(MachineFunction&,
                                 const MachineLoopInfo&,
                                 const MachineBlockFrequencyInfo&);
 };
 
 }
 
 #endif

llvm/trunk/lib/CodeGen/InlineSpiller.cpp

for (unsigned Reg : RegsToSpill) {
     }
   }
 
   // Eliminate dead code after remat. Note that some snippet copies may be
   // deleted here.
   if (DeadDefs.empty())
     return;
   DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n");
-  Edit->eliminateDeadDefs(DeadDefs, RegsToSpill);
+  Edit->eliminateDeadDefs(DeadDefs, RegsToSpill, AA);
 
   // LiveRangeEdit::eliminateDeadDef is used to remove dead define instructions
   // after rematerialization.  To remove a VNI for a vreg from its LiveInterval,
   // LiveIntervals::removeVRegDefAt is used. However, after non-PHI VNIs are all
   // removed, PHI VNI are still left in the LiveInterval.
   // So to get rid of unused reg, we need to check whether it has non-dbg
   // reference instead of whether it has non-empty interval.
   unsigned ResultPos = 0;
void InlineSpiller::spillAll() {
 
   // Spill around uses of all RegsToSpill.
   for (unsigned Reg : RegsToSpill)
     spillAroundUses(Reg);
 
   // Hoisted spills may cause dead code.
   if (!DeadDefs.empty()) {
     DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n");
-    Edit->eliminateDeadDefs(DeadDefs, RegsToSpill);
+    Edit->eliminateDeadDefs(DeadDefs, RegsToSpill, AA);
   }
 
   // Finally delete the SnippetCopies.
   for (unsigned Reg : RegsToSpill) {
     for (MachineRegisterInfo::reg_instr_iterator
          RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end();
          RI != E; ) {
       MachineInstr &MI = *(RI++);
for (auto &Ent : MergeableSpills) {
     for (auto const RMEnt : SpillsToRm) {
       RMEnt->setDesc(TII.get(TargetOpcode::KILL));
       for (unsigned i = RMEnt->getNumOperands(); i; --i) {
         MachineOperand &MO = RMEnt->getOperand(i - 1);
         if (MO.isReg() && MO.isImplicit() && MO.isDef() && !MO.isDead())
           RMEnt->RemoveOperand(i - 1);
       }
     }
-    Edit.eliminateDeadDefs(SpillsToRm, None);
+    Edit.eliminateDeadDefs(SpillsToRm, None, AA);
   }
 }
 
 /// For VirtReg clone, the \p New register should have the same physreg or
 /// stackslot as the \p old register.
 void HoistSpillHelper::LRE_DidCloneVirtReg(unsigned New, unsigned Old) {
   if (VRM.hasPhys(Old))
     VRM.assignVirt2Phys(New, VRM.getPhys(Old));
   else if (VRM.getStackSlot(Old) != VirtRegMap::NO_STACK_SLOT)
     VRM.assignVirt2StackSlot(New, VRM.getStackSlot(Old));
   else
     llvm_unreachable("VReg should be assigned either physreg or stackslot");
 }

llvm/trunk/lib/CodeGen/LiveRangeEdit.cpp

bool LiveRangeEdit::useIsKill(const LiveInterval &LI,
   for (const LiveInterval::SubRange &S : LI.subranges()) {
     if ((S.LaneMask & LaneMask) != 0 && S.Query(Idx).isKill())
       return true;
   }
   return false;
 }
 
 /// Find all live intervals that need to shrink, then remove the instruction.
-void LiveRangeEdit::eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink) {
+void LiveRangeEdit::eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink,
+                                     AliasAnalysis *AA) {
   assert(MI->allDefsAreDead() && "Def isn't really dead");
   SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
 
   // Never delete a bundled instruction.
   if (MI->isBundled()) {
     return;
   }
   // Never delete inline asm.
if (ReadsPhysRegs) {
     for (unsigned i = MI->getNumOperands(); i; --i) {
       const MachineOperand &MO = MI->getOperand(i-1);
       if (MO.isReg() && TargetRegisterInfo::isPhysicalRegister(MO.getReg()))
         continue;
       MI->RemoveOperand(i-1);
     }
     DEBUG(dbgs() << "Converted physregs to:\t" << *MI);
   } else {
-    // If the dest of MI is an original reg, don't delete the inst. Replace
-    // the dest with a new reg, keep the inst for remat of other siblings.
-    // The inst is saved in LiveRangeEdit::DeadRemats and will be deleted
-    // after all the allocations of the func are done.
-    if (isOrigDef) {
+    // If the dest of MI is an original reg and MI is reMaterializable,
+    // don't delete the inst. Replace the dest with a new reg, and keep
+    // the inst for remat of other siblings. The inst is saved in
+    // LiveRangeEdit::DeadRemats and will be deleted after all the
+    // allocations of the func are done.
+    if (isOrigDef && DeadRemats && TII.isTriviallyReMaterializable(*MI, AA)) {
       LiveInterval &NewLI = createEmptyIntervalFrom(Dest);
       VNInfo *VNI = NewLI.getNextValue(Idx, LIS.getVNInfoAllocator());
       NewLI.addSegment(LiveInterval::Segment(Idx, Idx.getDeadSlot(), VNI));
       pop_back();
       markDeadRemat(MI);
       const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
       MI->substituteRegister(Dest, NewLI.reg, 0, TRI);
       MI->getOperand(0).setIsDead(true);
for (unsigned i = 0, e = RegsToErase.size(); i != e; ++i) {
     if (LIS.hasInterval(Reg) && MRI.reg_nodbg_empty(Reg)) {
       ToShrink.remove(&LIS.getInterval(Reg));
       eraseVirtReg(Reg);
     }
   }
 }
 
 void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr *> &Dead,
-                                      ArrayRef<unsigned> RegsBeingSpilled) {
+                                      ArrayRef<unsigned> RegsBeingSpilled,
+                                      AliasAnalysis *AA) {
   ToShrinkSet ToShrink;
 
   for (;;) {
     // Erase all dead defs.
     while (!Dead.empty())
-      eliminateDeadDef(Dead.pop_back_val(), ToShrink);
+      eliminateDeadDef(Dead.pop_back_val(), ToShrink, AA);
 
     if (ToShrink.empty())
       break;
 
     // Shrink just one live interval. Then delete new dead defs.
     LiveInterval *LI = ToShrink.back();
     ToShrink.pop_back();
     if (foldAsLoad(LI, Dead))

llvm/trunk/lib/CodeGen/RegAllocGreedy.cpp

class RAGreedy : public MachineFunctionPass,
   // analyses
   SlotIndexes *Indexes;
   MachineBlockFrequencyInfo *MBFI;
   MachineDominatorTree *DomTree;
   MachineLoopInfo *Loops;
   EdgeBundles *Bundles;
   SpillPlacement *SpillPlacer;
   LiveDebugVariables *DebugVars;
+  AliasAnalysis *AA;
 
   // state
   std::unique_ptr<Spiller> SpillerInstance;
   PQueue Queue;
   unsigned NextCascade;
 
   // Live ranges pass through a number of stages as we try to allocate them.
   // Some of the stages may also create new live ranges:
bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
   Indexes = &getAnalysis<SlotIndexes>();
   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
   DomTree = &getAnalysis<MachineDominatorTree>();
   SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
   Loops = &getAnalysis<MachineLoopInfo>();
   Bundles = &getAnalysis<EdgeBundles>();
   SpillPlacer = &getAnalysis<SpillPlacement>();
   DebugVars = &getAnalysis<LiveDebugVariables>();
+  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 
   initializeCSRCost();
 
   calculateSpillWeightsAndHints(*LIS, mf, VRM, *Loops, *MBFI);
 
   DEBUG(LIS->dump());
 
   SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
-  SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree, *MBFI));
+  SE.reset(new SplitEditor(*SA, *AA, *LIS, *VRM, *DomTree, *MBFI));
   ExtraRegInfo.clear();
   ExtraRegInfo.resize(MRI->getNumVirtRegs());
   NextCascade = 1;
   IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI);
   GlobalCand.resize(32);  // This will grow as needed.
   SetOfBrokenHints.clear();
 
   allocatePhysRegs();
   tryHintsRecoloring();
   postOptimization();
 
   releaseMemory();
   return true;
 }

llvm/trunk/lib/CodeGen/SplitKit.h

 /// - Mark the places where the new interval is entered using enterIntv*
 /// - Mark the ranges where the new interval is used with useIntv* 
 /// - Mark the places where the interval is exited with exitIntv*.
 /// - Finish the current interval with closeIntv and repeat from 2.
 /// - Rewrite instructions with finish().
 ///
 class LLVM_LIBRARY_VISIBILITY SplitEditor {
   SplitAnalysis &SA;
+  AliasAnalysis &AA;
   LiveIntervals &LIS;
   VirtRegMap &VRM;
   MachineRegisterInfo &MRI;
   MachineDominatorTree &MDT;
   const TargetInstrInfo &TII;
   const TargetRegisterInfo &TRI;
   const MachineBlockFrequencyInfo &MBFI;
 
private:
   void rewriteAssigned(bool ExtendRanges);
 
   /// deleteRematVictims - Delete defs that are dead after rematerializing.
   void deleteRematVictims();
 
 public:
   /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
   /// Newly created intervals will be appended to newIntervals.
-  SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&,
-              MachineDominatorTree&, MachineBlockFrequencyInfo &);
+  SplitEditor(SplitAnalysis &SA, AliasAnalysis &AA, LiveIntervals&,
+              VirtRegMap&, MachineDominatorTree&,
+              MachineBlockFrequencyInfo &);
 
   /// reset - Prepare for a new split.
   void reset(LiveRangeEdit&, ComplementSpillMode = SM_Partition);
 
   /// Create a new virtual register and live interval.
   /// Return the interval index, starting from 1. Interval index 0 is the
   /// implicit complement interval.
   unsigned openIntv();

llvm/trunk/lib/CodeGen/SplitKit.cpp

 }
 
 
 //===----------------------------------------------------------------------===//
 //                               Split Editor
 //===----------------------------------------------------------------------===//
 
 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
-SplitEditor::SplitEditor(SplitAnalysis &sa, LiveIntervals &lis, VirtRegMap &vrm,
+SplitEditor::SplitEditor(SplitAnalysis &sa, AliasAnalysis &aa,
+                         LiveIntervals &lis, VirtRegMap &vrm,
                          MachineDominatorTree &mdt,
                          MachineBlockFrequencyInfo &mbfi)
-    : SA(sa), LIS(lis), VRM(vrm), MRI(vrm.getMachineFunction().getRegInfo()),
-      MDT(mdt), TII(*vrm.getMachineFunction().getSubtarget().getInstrInfo()),
+    : SA(sa), AA(aa), LIS(lis), VRM(vrm),
+      MRI(vrm.getMachineFunction().getRegInfo()), MDT(mdt),
+      TII(*vrm.getMachineFunction().getSubtarget().getInstrInfo()),
       TRI(*vrm.getMachineFunction().getSubtarget().getRegisterInfo()),
       MBFI(mbfi), Edit(nullptr), OpenIdx(0), SpillMode(SM_Partition),
       RegAssign(Allocator) {}
 
 void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) {
   Edit = &LRE;
   SpillMode = SM;
   OpenIdx = 0;
for (const LiveRange::Segment &S : LI->segments) {
       DEBUG(dbgs() << "All defs dead: " << *MI);
       Dead.push_back(MI);
     }
   }
 
   if (Dead.empty())
     return;
 
-  Edit->eliminateDeadDefs(Dead);
+  Edit->eliminateDeadDefs(Dead, None, &AA);
 }
 
 void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) {
   ++NumFinished;
 
   // At this point, the live intervals in Edit contain VNInfos corresponding to
   // the inserted copies.