X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveVariables.cpp;h=b355393e76f79526466d3fe7ce6eddfb44d34afa;hb=e903f64b10dc61461b135425460efb63346f0fed;hp=068c7695a294e27fa0a41bae9d41e46fe7474aa0;hpb=273fd11da9c2c6581844c91dad6901986c50ed12;p=oota-llvm.git diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp index 068c7695a29..b355393e76f 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; @@ -497,17 +497,135 @@ void LiveVariables::UpdatePhysRegDefs(MachineInstr *MI, } } +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()) { + MO.setIsKill(false); + if (MO.readsReg()) + UseRegs.push_back(MOReg); + } else /*MO.isDef()*/ { + 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 (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, 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->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, nullptr, Defs); +} + bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { MF = &mf; MRI = &mf.getRegInfo(); TRI = MF->getSubtarget().getRegisterInfo(); - unsigned NumRegs = TRI->getNumRegs(); - PhysRegDef = new MachineInstr*[NumRegs]; - PhysRegUse = new MachineInstr*[NumRegs]; - PHIVarInfo = new SmallVector[MF->getNumBlockIDs()]; - std::fill(PhysRegDef, PhysRegDef + NumRegs, nullptr); - std::fill(PhysRegUse, PhysRegUse + NumRegs, nullptr); + 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 @@ -526,119 +644,10 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { SmallPtrSet Visited; for (MachineBasicBlock *MBB : depth_first_ext(Entry, Visited)) { - // 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, 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++)); - - // 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); - } + runOnBlock(MBB, NumRegs); - // 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()) { - 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->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, nullptr, Defs); - - std::fill(PhysRegDef, PhysRegDef + NumRegs, nullptr); - std::fill(PhysRegUse, PhysRegUse + NumRegs, nullptr); + PhysRegDef.assign(NumRegs, nullptr); + PhysRegUse.assign(NumRegs, nullptr); } // Convert and transfer the dead / killed information we have gathered into @@ -660,9 +669,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; } @@ -729,45 +738,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; }