X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveVariables.cpp;h=06b86d82daf1fa541ac1df78969d04cda58ba33c;hb=912373de69045e491d6a301611ce31a2914a7d43;hp=4e83fc833d96137da35aff5ef286a03cdf67e4d1;hpb=5cc3c989fc4295103ee46a2697e82dc1c4453545;p=oota-llvm.git diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp index 4e83fc833d9..06b86d82daf 100644 --- a/lib/CodeGen/LiveVariables.cpp +++ b/lib/CodeGen/LiveVariables.cpp @@ -36,8 +36,8 @@ #include "llvm/CodeGen/Passes.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" #include using namespace llvm; @@ -61,7 +61,7 @@ LiveVariables::VarInfo::findKill(const MachineBasicBlock *MBB) const { for (unsigned i = 0, e = Kills.size(); i != e; ++i) if (Kills[i]->getParent() == MBB) return Kills[i]; - return NULL; + return nullptr; } void LiveVariables::VarInfo::dump() const { @@ -193,7 +193,7 @@ MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg, SmallSet &PartDefRegs) { unsigned LastDefReg = 0; unsigned LastDefDist = 0; - MachineInstr *LastDef = NULL; + MachineInstr *LastDef = nullptr; for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { unsigned SubReg = *SubRegs; MachineInstr *Def = PhysRegDef[SubReg]; @@ -208,7 +208,7 @@ MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg, } if (!LastDef) - return 0; + return nullptr; PartDefRegs.insert(LastDefReg); for (unsigned i = 0, e = LastDef->getNumOperands(); i != e; ++i) { @@ -282,7 +282,7 @@ MachineInstr *LiveVariables::FindLastRefOrPartRef(unsigned Reg) { MachineInstr *LastDef = PhysRegDef[Reg]; MachineInstr *LastUse = PhysRegUse[Reg]; if (!LastDef && !LastUse) - return 0; + return nullptr; MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef; unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef]; @@ -333,7 +333,7 @@ bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) { // AX = AL // = AL // AX = - MachineInstr *LastPartDef = 0; + MachineInstr *LastPartDef = nullptr; unsigned LastPartDefDist = 0; SmallSet PartUses; for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { @@ -436,12 +436,12 @@ void LiveVariables::HandleRegMask(const MachineOperand &MO) { for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) if ((PhysRegDef[*SR] || PhysRegUse[*SR]) && MO.clobbersPhysReg(*SR)) Super = *SR; - HandlePhysRegKill(Super, 0); + HandlePhysRegKill(Super, nullptr); } } void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI, - SmallVector &Defs) { + SmallVectorImpl &Defs) { // What parts of the register are previously defined? SmallSet Live; if (PhysRegDef[Reg] || PhysRegUse[Reg]) { @@ -484,7 +484,7 @@ void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI, } void LiveVariables::UpdatePhysRegDefs(MachineInstr *MI, - SmallVector &Defs) { + SmallVectorImpl &Defs) { while (!Defs.empty()) { unsigned Reg = Defs.back(); Defs.pop_back(); @@ -492,22 +492,141 @@ void LiveVariables::UpdatePhysRegDefs(MachineInstr *MI, SubRegs.isValid(); ++SubRegs) { unsigned SubReg = *SubRegs; PhysRegDef[SubReg] = MI; - PhysRegUse[SubReg] = NULL; + PhysRegUse[SubReg] = nullptr; } } } +void LiveVariables::runOnInstr(MachineInstr *MI, + SmallVectorImpl &Defs) { + assert(!MI->isDebugValue()); + // Process all of the operands of the instruction... + unsigned NumOperandsToProcess = MI->getNumOperands(); + + // Unless it is a PHI node. In this case, ONLY process the DEF, not any + // of the uses. They will be handled in other basic blocks. + if (MI->isPHI()) + NumOperandsToProcess = 1; + + // Clear kill and dead markers. LV will recompute them. + SmallVector UseRegs; + SmallVector DefRegs; + SmallVector RegMasks; + for (unsigned i = 0; i != NumOperandsToProcess; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (MO.isRegMask()) { + RegMasks.push_back(i); + continue; + } + if (!MO.isReg() || MO.getReg() == 0) + continue; + unsigned MOReg = MO.getReg(); + if (MO.isUse()) { + if (!(TargetRegisterInfo::isPhysicalRegister(MOReg) && + MRI->isReserved(MOReg))) + MO.setIsKill(false); + if (MO.readsReg()) + UseRegs.push_back(MOReg); + } else /*MO.isDef()*/ { + if (!(TargetRegisterInfo::isPhysicalRegister(MOReg) && + MRI->isReserved(MOReg))) + MO.setIsDead(false); + DefRegs.push_back(MOReg); + } + } + + MachineBasicBlock *MBB = MI->getParent(); + // Process all uses. + for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) { + unsigned MOReg = UseRegs[i]; + if (TargetRegisterInfo::isVirtualRegister(MOReg)) + HandleVirtRegUse(MOReg, MBB, MI); + else if (!MRI->isReserved(MOReg)) + HandlePhysRegUse(MOReg, MI); + } + + // Process all masked registers. (Call clobbers). + for (unsigned i = 0, e = RegMasks.size(); i != e; ++i) + HandleRegMask(MI->getOperand(RegMasks[i])); + + // Process all defs. + for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) { + unsigned MOReg = DefRegs[i]; + if (TargetRegisterInfo::isVirtualRegister(MOReg)) + HandleVirtRegDef(MOReg, MI); + else if (!MRI->isReserved(MOReg)) + HandlePhysRegDef(MOReg, MI, Defs); + } + UpdatePhysRegDefs(MI, Defs); +} + +void LiveVariables::runOnBlock(MachineBasicBlock *MBB, const unsigned NumRegs) { + // Mark live-in registers as live-in. + SmallVector Defs; + for (const auto &LI : MBB->liveins()) { + assert(TargetRegisterInfo::isPhysicalRegister(LI.PhysReg) && + "Cannot have a live-in virtual register!"); + HandlePhysRegDef(LI.PhysReg, nullptr, Defs); + } + + // Loop over all of the instructions, processing them. + DistanceMap.clear(); + unsigned Dist = 0; + for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); + I != E; ++I) { + MachineInstr *MI = I; + if (MI->isDebugValue()) + continue; + DistanceMap.insert(std::make_pair(MI, Dist++)); + + runOnInstr(MI, Defs); + } + + // Handle any virtual assignments from PHI nodes which might be at the + // bottom of this basic block. We check all of our successor blocks to see + // if they have PHI nodes, and if so, we simulate an assignment at the end + // of the current block. + if (!PHIVarInfo[MBB->getNumber()].empty()) { + SmallVectorImpl &VarInfoVec = PHIVarInfo[MBB->getNumber()]; + + for (SmallVectorImpl::iterator I = VarInfoVec.begin(), + E = VarInfoVec.end(); I != E; ++I) + // Mark it alive only in the block we are representing. + MarkVirtRegAliveInBlock(getVarInfo(*I),MRI->getVRegDef(*I)->getParent(), + MBB); + } + + // MachineCSE may CSE instructions which write to non-allocatable physical + // registers across MBBs. Remember if any reserved register is liveout. + SmallSet LiveOuts; + for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(), + SE = MBB->succ_end(); SI != SE; ++SI) { + MachineBasicBlock *SuccMBB = *SI; + if (SuccMBB->isEHPad()) + continue; + for (const auto &LI : SuccMBB->liveins()) { + if (!TRI->isInAllocatableClass(LI.PhysReg)) + // Ignore other live-ins, e.g. those that are live into landing pads. + LiveOuts.insert(LI.PhysReg); + } + } + + // Loop over PhysRegDef / PhysRegUse, killing any registers that are + // available at the end of the basic block. + for (unsigned i = 0; i != NumRegs; ++i) + if ((PhysRegDef[i] || PhysRegUse[i]) && !LiveOuts.count(i)) + HandlePhysRegDef(i, nullptr, Defs); +} + bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { MF = &mf; MRI = &mf.getRegInfo(); - TRI = MF->getTarget().getRegisterInfo(); - - unsigned NumRegs = TRI->getNumRegs(); - PhysRegDef = new MachineInstr*[NumRegs]; - PhysRegUse = new MachineInstr*[NumRegs]; - PHIVarInfo = new SmallVector[MF->getNumBlockIDs()]; - std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); - std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); + TRI = MF->getSubtarget().getRegisterInfo(); + + const unsigned NumRegs = TRI->getNumRegs(); + PhysRegDef.assign(NumRegs, nullptr); + PhysRegUse.assign(NumRegs, nullptr); + PHIVarInfo.resize(MF->getNumBlockIDs()); PHIJoins.clear(); // FIXME: LiveIntervals will be updated to remove its dependence on @@ -522,127 +641,14 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { // function. This guarantees that we will see the definition of a virtual // register before its uses due to dominance properties of SSA (except for PHI // nodes, which are treated as a special case). - MachineBasicBlock *Entry = MF->begin(); + MachineBasicBlock *Entry = &MF->front(); SmallPtrSet Visited; - for (df_ext_iterator > - DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); - DFI != E; ++DFI) { - MachineBasicBlock *MBB = *DFI; - - // Mark live-in registers as live-in. - SmallVector Defs; - for (MachineBasicBlock::livein_iterator II = MBB->livein_begin(), - EE = MBB->livein_end(); II != EE; ++II) { - assert(TargetRegisterInfo::isPhysicalRegister(*II) && - "Cannot have a live-in virtual register!"); - HandlePhysRegDef(*II, 0, Defs); - } - - // Loop over all of the instructions, processing them. - DistanceMap.clear(); - unsigned Dist = 0; - for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); - I != E; ++I) { - MachineInstr *MI = I; - if (MI->isDebugValue()) - continue; - DistanceMap.insert(std::make_pair(MI, Dist++)); - - // Process all of the operands of the instruction... - unsigned NumOperandsToProcess = MI->getNumOperands(); - - // Unless it is a PHI node. In this case, ONLY process the DEF, not any - // of the uses. They will be handled in other basic blocks. - if (MI->isPHI()) - NumOperandsToProcess = 1; - - // Clear kill and dead markers. LV will recompute them. - SmallVector UseRegs; - SmallVector DefRegs; - SmallVector RegMasks; - for (unsigned i = 0; i != NumOperandsToProcess; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (MO.isRegMask()) { - RegMasks.push_back(i); - continue; - } - if (!MO.isReg() || MO.getReg() == 0) - continue; - unsigned MOReg = MO.getReg(); - if (MO.isUse()) { - MO.setIsKill(false); - if (MO.readsReg()) - UseRegs.push_back(MOReg); - } else /*MO.isDef()*/ { - MO.setIsDead(false); - DefRegs.push_back(MOReg); - } - } - - // Process all uses. - for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) { - unsigned MOReg = UseRegs[i]; - if (TargetRegisterInfo::isVirtualRegister(MOReg)) - HandleVirtRegUse(MOReg, MBB, MI); - else if (!MRI->isReserved(MOReg)) - HandlePhysRegUse(MOReg, MI); - } - - // Process all masked registers. (Call clobbers). - for (unsigned i = 0, e = RegMasks.size(); i != e; ++i) - HandleRegMask(MI->getOperand(RegMasks[i])); - - // Process all defs. - for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) { - unsigned MOReg = DefRegs[i]; - if (TargetRegisterInfo::isVirtualRegister(MOReg)) - HandleVirtRegDef(MOReg, MI); - else if (!MRI->isReserved(MOReg)) - HandlePhysRegDef(MOReg, MI, Defs); - } - UpdatePhysRegDefs(MI, Defs); - } - - // Handle any virtual assignments from PHI nodes which might be at the - // bottom of this basic block. We check all of our successor blocks to see - // if they have PHI nodes, and if so, we simulate an assignment at the end - // of the current block. - if (!PHIVarInfo[MBB->getNumber()].empty()) { - SmallVector& VarInfoVec = PHIVarInfo[MBB->getNumber()]; - - for (SmallVector::iterator I = VarInfoVec.begin(), - E = VarInfoVec.end(); I != E; ++I) - // Mark it alive only in the block we are representing. - MarkVirtRegAliveInBlock(getVarInfo(*I),MRI->getVRegDef(*I)->getParent(), - MBB); - } + for (MachineBasicBlock *MBB : depth_first_ext(Entry, Visited)) { + runOnBlock(MBB, NumRegs); - // MachineCSE may CSE instructions which write to non-allocatable physical - // registers across MBBs. Remember if any reserved register is liveout. - SmallSet LiveOuts; - for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(), - SE = MBB->succ_end(); SI != SE; ++SI) { - MachineBasicBlock *SuccMBB = *SI; - if (SuccMBB->isLandingPad()) - continue; - for (MachineBasicBlock::livein_iterator LI = SuccMBB->livein_begin(), - LE = SuccMBB->livein_end(); LI != LE; ++LI) { - unsigned LReg = *LI; - if (!TRI->isInAllocatableClass(LReg)) - // Ignore other live-ins, e.g. those that are live into landing pads. - LiveOuts.insert(LReg); - } - } - - // Loop over PhysRegDef / PhysRegUse, killing any registers that are - // available at the end of the basic block. - for (unsigned i = 0; i != NumRegs; ++i) - if ((PhysRegDef[i] || PhysRegUse[i]) && !LiveOuts.count(i)) - HandlePhysRegDef(i, 0, Defs); - - std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); - std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); + PhysRegDef.assign(NumRegs, nullptr); + PhysRegUse.assign(NumRegs, nullptr); } // Convert and transfer the dead / killed information we have gathered into @@ -664,9 +670,9 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { assert(Visited.count(&*i) != 0 && "unreachable basic block found"); #endif - delete[] PhysRegDef; - delete[] PhysRegUse; - delete[] PHIVarInfo; + PhysRegDef.clear(); + PhysRegUse.clear(); + PHIVarInfo.clear(); return false; } @@ -701,14 +707,15 @@ void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) { /// which is used in a PHI node. We map that to the BB the vreg is coming from. /// void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { - for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); - I != E; ++I) - for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); - BBI != BBE && BBI->isPHI(); ++BBI) - for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) - if (BBI->getOperand(i).readsReg()) - PHIVarInfo[BBI->getOperand(i + 1).getMBB()->getNumber()] - .push_back(BBI->getOperand(i).getReg()); + for (const auto &MBB : Fn) + for (const auto &BBI : MBB) { + if (!BBI.isPHI()) + break; + for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) + if (BBI.getOperand(i).readsReg()) + PHIVarInfo[BBI.getOperand(i + 1).getMBB()->getNumber()] + .push_back(BBI.getOperand(i).getReg()); + } } bool LiveVariables::VarInfo::isLiveIn(const MachineBasicBlock &MBB, @@ -732,45 +739,22 @@ bool LiveVariables::VarInfo::isLiveIn(const MachineBasicBlock &MBB, bool LiveVariables::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB) { LiveVariables::VarInfo &VI = getVarInfo(Reg); + SmallPtrSet Kills; + for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) + Kills.insert(VI.Kills[i]->getParent()); + // Loop over all of the successors of the basic block, checking to see if // the value is either live in the block, or if it is killed in the block. - SmallVector OpSuccBlocks; - for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), - E = MBB.succ_end(); SI != E; ++SI) { - MachineBasicBlock *SuccMBB = *SI; - + for (const MachineBasicBlock *SuccMBB : MBB.successors()) { // Is it alive in this successor? unsigned SuccIdx = SuccMBB->getNumber(); if (VI.AliveBlocks.test(SuccIdx)) return true; - OpSuccBlocks.push_back(SuccMBB); + // Or is it live because there is a use in a successor that kills it? + if (Kills.count(SuccMBB)) + return true; } - // Check to see if this value is live because there is a use in a successor - // that kills it. - switch (OpSuccBlocks.size()) { - case 1: { - MachineBasicBlock *SuccMBB = OpSuccBlocks[0]; - for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) - if (VI.Kills[i]->getParent() == SuccMBB) - return true; - break; - } - case 2: { - MachineBasicBlock *SuccMBB1 = OpSuccBlocks[0], *SuccMBB2 = OpSuccBlocks[1]; - for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) - if (VI.Kills[i]->getParent() == SuccMBB1 || - VI.Kills[i]->getParent() == SuccMBB2) - return true; - break; - } - default: - std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end()); - for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) - if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(), - VI.Kills[i]->getParent())) - return true; - } return false; }