Members/tobaru/cbc/CbC_llvm: lib/CodeGen/VirtRegMap.cpp comparison

comparison lib/CodeGen/VirtRegMap.cpp @ 95:afa8332a0e37

LLVM 3.8

author	Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date	Tue, 13 Oct 2015 17:48:58 +0900
parents	60c9769439b8
children	7d135dc70f03

comparison

equal deleted inserted replaced

-:f3e34b893a5f
+:afa8332a0e37
 const TargetInstrInfo *TII;
 MachineRegisterInfo *MRI;
 SlotIndexes *Indexes;
 LiveIntervals *LIS;
 VirtRegMap *VRM;
-SparseSet<unsigned> PhysRegs;
 void rewrite();
 void addMBBLiveIns();
+bool readsUndefSubreg(const MachineOperand &MO) const;
+void addLiveInsForSubRanges(const LiveInterval &LI, unsigned PhysReg) const;
 public:
 static char ID;
 VirtRegRewriter() : MachineFunctionPass(ID) {}
 void getAnalysisUsage(AnalysisUsage &AU) const override;
 VRM->clearAllVirt();
 MRI->clearVirtRegs();
 return true;
 }
+void VirtRegRewriter::addLiveInsForSubRanges(const LiveInterval &LI,
+unsigned PhysReg) const {
+assert(!LI.empty());
+assert(LI.hasSubRanges());
+typedef std::pair<const LiveInterval::SubRange *,
+LiveInterval::const_iterator> SubRangeIteratorPair;
+SmallVector<SubRangeIteratorPair, 4> SubRanges;
+SlotIndex First;
+SlotIndex Last;
+for (const LiveInterval::SubRange &SR : LI.subranges()) {
+SubRanges.push_back(std::make_pair(&SR, SR.begin()));
+if (!First.isValid() || SR.segments.front().start < First)
+First = SR.segments.front().start;
+if (!Last.isValid() || SR.segments.back().end > Last)
+Last = SR.segments.back().end;
+}
+// Check all mbb start positions between First and Last while
+// simulatenously advancing an iterator for each subrange.
+for (SlotIndexes::MBBIndexIterator MBBI = Indexes->findMBBIndex(First);
+MBBI != Indexes->MBBIndexEnd() && MBBI->first <= Last; ++MBBI) {
+SlotIndex MBBBegin = MBBI->first;
+// Advance all subrange iterators so that their end position is just
+// behind MBBBegin (or the iterator is at the end).
+LaneBitmask LaneMask = 0;
+for (auto &RangeIterPair : SubRanges) {
+const LiveInterval::SubRange *SR = RangeIterPair.first;
+LiveInterval::const_iterator &SRI = RangeIterPair.second;
+while (SRI != SR->end() && SRI->end <= MBBBegin)
+++SRI;
+if (SRI == SR->end())
+continue;
+if (SRI->start <= MBBBegin)
+LaneMask |= SR->LaneMask;
+}
+if (LaneMask == 0)
+continue;
+MachineBasicBlock *MBB = MBBI->second;
+MBB->addLiveIn(PhysReg, LaneMask);
+}
+}
 // Compute MBB live-in lists from virtual register live ranges and their
 // assignments.
 void VirtRegRewriter::addMBBLiveIns() {
-SmallVector<MachineBasicBlock*, 16> LiveIn;
 for (unsigned Idx = 0, IdxE = MRI->getNumVirtRegs(); Idx != IdxE; ++Idx) {
 unsigned VirtReg = TargetRegisterInfo::index2VirtReg(Idx);
 if (MRI->reg_nodbg_empty(VirtReg))
 continue;
 LiveInterval &LI = LIS->getInterval(VirtReg);
 // assigned PhysReg must be marked as live-in to those blocks.
 unsigned PhysReg = VRM->getPhys(VirtReg);
 assert(PhysReg != VirtRegMap::NO_PHYS_REG && "Unmapped virtual register.");
 if (LI.hasSubRanges()) {
-for (LiveInterval::SubRange &S : LI.subranges()) {
+addLiveInsForSubRanges(LI, PhysReg);
-for (const auto &Seg : S.segments) {
+} else {
-if (!Indexes->findLiveInMBBs(Seg.start, Seg.end, LiveIn))
+// Go over MBB begin positions and see if we have segments covering them.
-continue;
+// The following works because segments and the MBBIndex list are both
-for (MCSubRegIndexIterator SR(PhysReg, TRI); SR.isValid(); ++SR) {
+// sorted by slot indexes.
-unsigned SubReg = SR.getSubReg();
+SlotIndexes::MBBIndexIterator I = Indexes->MBBIndexBegin();
-unsigned SubRegIndex = SR.getSubRegIndex();
+for (const auto &Seg : LI) {
-unsigned SubRegLaneMask = TRI->getSubRegIndexLaneMask(SubRegIndex);
+I = Indexes->advanceMBBIndex(I, Seg.start);
-if ((SubRegLaneMask & S.LaneMask) == 0)
+for (; I != Indexes->MBBIndexEnd() && I->first < Seg.end; ++I) {
-continue;
+MachineBasicBlock *MBB = I->second;
-for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) {
+MBB->addLiveIn(PhysReg);
-if (!LiveIn[i]->isLiveIn(SubReg))
-LiveIn[i]->addLiveIn(SubReg);
-}
-}
-LiveIn.clear();
 }
 }
-} else {
-// Scan the segments of LI.
-for (const auto &Seg : LI.segments) {
-if (!Indexes->findLiveInMBBs(Seg.start, Seg.end, LiveIn))
-continue;
-for (unsigned i = 0, e = LiveIn.size(); i != e; ++i)
-if (!LiveIn[i]->isLiveIn(PhysReg))
-LiveIn[i]->addLiveIn(PhysReg);
-LiveIn.clear();
-}
 }
 }
+// Sort and unique MBB LiveIns as we've not checked if SubReg/PhysReg were in
+// each MBB's LiveIns set before calling addLiveIn on them.
+for (MachineBasicBlock &MBB : *MF)
+MBB.sortUniqueLiveIns();
+}
+/// Returns true if the given machine operand \p MO only reads undefined lanes.
+/// The function only works for use operands with a subregister set.
+bool VirtRegRewriter::readsUndefSubreg(const MachineOperand &MO) const {
+// Shortcut if the operand is already marked undef.
+if (MO.isUndef())
+return true;
+unsigned Reg = MO.getReg();
+const LiveInterval &LI = LIS->getInterval(Reg);
+const MachineInstr &MI = *MO.getParent();
+SlotIndex BaseIndex = LIS->getInstructionIndex(&MI);
+// This code is only meant to handle reading undefined subregisters which
+// we couldn't properly detect before.
+assert(LI.liveAt(BaseIndex) &&
+"Reads of completely dead register should be marked undef already");
+unsigned SubRegIdx = MO.getSubReg();
+LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(SubRegIdx);
+// See if any of the relevant subregister liveranges is defined at this point.
+for (const LiveInterval::SubRange &SR : LI.subranges()) {
+if ((SR.LaneMask & UseMask) != 0 && SR.liveAt(BaseIndex))
+return false;
+}
+return true;
 }
 void VirtRegRewriter::rewrite() {
-bool NoSubRegLiveness = !MRI->tracksSubRegLiveness();
+bool NoSubRegLiveness = !MRI->subRegLivenessEnabled();
 SmallVector<unsigned, 8> SuperDeads;
 SmallVector<unsigned, 8> SuperDefs;
 SmallVector<unsigned, 8> SuperKills;
-SmallPtrSet<const MachineInstr *, 4> NoReturnInsts;
-// Here we have a SparseSet to hold which PhysRegs are actually encountered
-// in the MF we are about to iterate over so that later when we call
-// setPhysRegUsed, we are only doing it for physRegs that were actually found
-// in the program and not for all of the possible physRegs for the given
-// target architecture. If the target has a lot of physRegs, then for a small
-// program there will be a significant compile time reduction here.
-PhysRegs.clear();
-PhysRegs.setUniverse(TRI->getNumRegs());
-// The function with uwtable should guarantee that the stack unwinder
-// can unwind the stack to the previous frame.  Thus, we can't apply the
-// noreturn optimization if the caller function has uwtable attribute.
-bool HasUWTable = MF->getFunction()->hasFnAttribute(Attribute::UWTable);
 for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
 MBBI != MBBE; ++MBBI) {
 DEBUG(MBBI->print(dbgs(), Indexes));
-bool IsExitBB = MBBI->succ_empty();
 for (MachineBasicBlock::instr_iterator
 MII = MBBI->instr_begin(), MIE = MBBI->instr_end(); MII != MIE;) {
-MachineInstr *MI = MII;
+MachineInstr *MI = &*MII;
 ++MII;
-// Check if this instruction is a call to a noreturn function.  If this
-// is a call to noreturn function and we don't need the stack unwinding
-// functionality (i.e. this function does not have uwtable attribute and
-// the callee function has the nounwind attribute), then we can ignore
-// the definitions set by this instruction.
-if (!HasUWTable && IsExitBB && MI->isCall()) {
-for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
-MOE = MI->operands_end(); MOI != MOE; ++MOI) {
-MachineOperand &MO = *MOI;
-if (!MO.isGlobal())
-continue;
-const Function *Func = dyn_cast<Function>(MO.getGlobal());
-if (!Func || !Func->hasFnAttribute(Attribute::NoReturn) ||
-// We need to keep correct unwind information
-// even if the function will not return, since the
-// runtime may need it.
-!Func->hasFnAttribute(Attribute::NoUnwind))
-continue;
-NoReturnInsts.insert(MI);
-break;
-}
-}
 for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
 MOE = MI->operands_end(); MOI != MOE; ++MOI) {
 MachineOperand &MO = *MOI;
 // Make sure MRI knows about registers clobbered by regmasks.
 if (MO.isRegMask())
 MRI->addPhysRegsUsedFromRegMask(MO.getRegMask());
-// If we encounter a VirtReg or PhysReg then get at the PhysReg and add
-// it to the physreg bitset.  Later we use only the PhysRegs that were
-// actually encountered in the MF to populate the MRI's used physregs.
-if (MO.isReg() && MO.getReg())
-PhysRegs.insert(
-TargetRegisterInfo::isVirtualRegister(MO.getReg()) ?
-VRM->getPhys(MO.getReg()) :
-MO.getReg());
 if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
 continue;
 unsigned VirtReg = MO.getReg();
 unsigned PhysReg = VRM->getPhys(VirtReg);
 assert(PhysReg != VirtRegMap::NO_PHYS_REG &&
 "Instruction uses unmapped VirtReg");
 assert(!MRI->isReserved(PhysReg) && "Reserved register assignment");
 // Preserve semantics of sub-register operands.
-if (MO.getSubReg()) {
+unsigned SubReg = MO.getSubReg();
-// A virtual register kill refers to the whole register, so we may
+if (SubReg != 0) {
-// have to add <imp-use,kill> operands for the super-register.  A
+if (NoSubRegLiveness) {
-// partial redef always kills and redefines the super-register.
+// A virtual register kill refers to the whole register, so we may
-if (NoSubRegLiveness && MO.readsReg()
+// have to add <imp-use,kill> operands for the super-register.  A
-&& (MO.isDef() || MO.isKill()))
+// partial redef always kills and redefines the super-register.
-SuperKills.push_back(PhysReg);
+if (MO.readsReg() && (MO.isDef() || MO.isKill()))
+SuperKills.push_back(PhysReg);
-if (MO.isDef()) {
-// The <def,undef> flag only makes sense for sub-register defs, and
+if (MO.isDef()) {
-// we are substituting a full physreg.  An <imp-use,kill> operand
+// Also add implicit defs for the super-register.
-// from the SuperKills list will represent the partial read of the
-// super-register.
-MO.setIsUndef(false);
-// Also add implicit defs for the super-register.
-if (NoSubRegLiveness) {
 if (MO.isDead())
 SuperDeads.push_back(PhysReg);
 else
 SuperDefs.push_back(PhysReg);
 }
+} else {
+if (MO.isUse()) {
+if (readsUndefSubreg(MO))
+// We need to add an <undef> flag if the subregister is
+// completely undefined (and we are not adding super-register
+// defs).
+MO.setIsUndef(true);
+} else if (!MO.isDead()) {
+assert(MO.isDef());
+// Things get tricky when we ran out of lane mask bits and
+// merged multiple lanes into the overflow bit: In this case
+// our subregister liveness tracking isn't precise and we can't
+// know what subregister parts are undefined, fall back to the
+// implicit super-register def then.
+LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg);
+if (TargetRegisterInfo::isImpreciseLaneMask(LaneMask))
+SuperDefs.push_back(PhysReg);
+}
 }
+// 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())
+MO.setIsUndef(false);
 // PhysReg operands cannot have subregister indexes.
-PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg());
+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.
 DEBUG(dbgs() << "> " << *MI);
 // Finally, remove any identity copies.
 if (MI->isIdentityCopy()) {
 ++NumIdCopies;
-if (MI->getNumOperands() == 2) {
+DEBUG(dbgs() << "Deleting identity copy.\n");
-DEBUG(dbgs() << "Deleting identity copy.\n");
+if (Indexes)
-if (Indexes)
+Indexes->removeMachineInstrFromMaps(MI);
-Indexes->removeMachineInstrFromMaps(MI);
+// It's safe to erase MI because MII has already been incremented.
-// It's safe to erase MI because MII has already been incremented.
+MI->eraseFromParent();
-MI->eraseFromParent();
-} else {
-// Transform identity copy to a KILL to deal with subregisters.
-MI->setDesc(TII->get(TargetOpcode::KILL));
-DEBUG(dbgs() << "Identity copy: " << *MI);
-}
 }
 }
 }
+}
-// Tell MRI about physical registers in use.
-if (NoReturnInsts.empty()) {
-for (SparseSet<unsigned>::iterator
-RegI = PhysRegs.begin(), E = PhysRegs.end(); RegI != E; ++RegI)
-if (!MRI->reg_nodbg_empty(*RegI))
-MRI->setPhysRegUsed(*RegI);
-} else {
-for (SparseSet<unsigned>::iterator
-I = PhysRegs.begin(), E = PhysRegs.end(); I != E; ++I) {
-unsigned Reg = *I;
-if (MRI->reg_nodbg_empty(Reg))
-continue;
-// Check if this register has a use that will impact the rest of the
-// code. Uses in debug and noreturn instructions do not impact the
-// generated code.
-for (MachineInstr &It : MRI->reg_nodbg_instructions(Reg)) {
-if (!NoReturnInsts.count(&It)) {
-MRI->setPhysRegUsed(Reg);
-break;
-}
-}
-}
-}
-}

Mercurial > hg > Members > tobaru > cbc > CbC_llvm

comparison lib/CodeGen/VirtRegMap.cpp @ 95:afa8332a0e37