X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveVariables.cpp;h=0bdf86406f104cab9b127fed994f2017a148bb2e;hb=1484089bbf960f7191215dfa6c0bb51c8e30794e;hp=1bfc6e553d64207b646e8591250204e88eb0799e;hpb=19b6486d3891c8a02a301aa1b44348a420772fcf;p=oota-llvm.git diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp index 1bfc6e553d6..0bdf86406f1 100644 --- a/lib/CodeGen/LiveVariables.cpp +++ b/lib/CodeGen/LiveVariables.cpp @@ -28,22 +28,17 @@ #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/MachineInstr.h" +#include "llvm/Target/MRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" -#include "llvm/Support/CFG.h" #include "Support/DepthFirstIterator.h" - -namespace llvm { +#include "Support/STLExtras.h" +using namespace llvm; static RegisterAnalysis X("livevars", "Live Variable Analysis"); -const std::pair & -LiveVariables::getMachineBasicBlockInfo(MachineBasicBlock *MBB) const{ - return BBMap.find(MBB->getBasicBlock())->second; -} - LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { - assert(RegIdx >= MRegisterInfo::FirstVirtualRegister && + assert(MRegisterInfo::isVirtualRegister(RegIdx) && "getVarInfo: not a virtual register!"); RegIdx -= MRegisterInfo::FirstVirtualRegister; if (RegIdx >= VirtRegInfo.size()) { @@ -58,20 +53,18 @@ LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, - const BasicBlock *BB) { - const std::pair &Info = BBMap.find(BB)->second; - MachineBasicBlock *MBB = Info.first; - unsigned BBNum = Info.second; + MachineBasicBlock *MBB) { + unsigned BBNum = MBB->getNumber(); // Check to see if this basic block is one of the killing blocks. If so, // remove it... for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) - if (VRInfo.Kills[i].first == MBB) { + if (VRInfo.Kills[i]->getParent() == MBB) { VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry break; } - if (MBB == VRInfo.DefBlock) return; // Terminate recursion + if (MBB == VRInfo.DefInst->getParent()) return; // Terminate recursion if (VRInfo.AliveBlocks.size() <= BBNum) VRInfo.AliveBlocks.resize(BBNum+1); // Make space... @@ -82,41 +75,47 @@ void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, // Mark the variable known alive in this bb VRInfo.AliveBlocks[BBNum] = true; - for (pred_const_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) + for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), + E = MBB->pred_end(); PI != E; ++PI) MarkVirtRegAliveInBlock(VRInfo, *PI); } void LiveVariables::HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB, - MachineInstr *MI) { + MachineInstr *MI) { // Check to see if this basic block is already a kill block... - if (!VRInfo.Kills.empty() && VRInfo.Kills.back().first == MBB) { + if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { // Yes, this register is killed in this basic block already. Increase the // live range by updating the kill instruction. - VRInfo.Kills.back().second = MI; + VRInfo.Kills.back() = MI; return; } #ifndef NDEBUG for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) - assert(VRInfo.Kills[i].first != MBB && "entry should be at end!"); + assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!"); #endif - assert(MBB != VRInfo.DefBlock && "Should have kill for defblock!"); + assert(MBB != VRInfo.DefInst->getParent() && + "Should have kill for defblock!"); // Add a new kill entry for this basic block. - VRInfo.Kills.push_back(std::make_pair(MBB, MI)); + VRInfo.Kills.push_back(MI); // Update all dominating blocks to mark them known live. const BasicBlock *BB = MBB->getBasicBlock(); - for (pred_const_iterator PI = pred_begin(BB), E = pred_end(BB); - PI != E; ++PI) + for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), + E = MBB->pred_end(); PI != E; ++PI) MarkVirtRegAliveInBlock(VRInfo, *PI); } void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { - if (PhysRegInfo[Reg]) { - PhysRegInfo[Reg] = MI; - PhysRegUsed[Reg] = true; + PhysRegInfo[Reg] = MI; + PhysRegUsed[Reg] = true; + + for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); + unsigned Alias = *AliasSet; ++AliasSet) { + PhysRegInfo[Alias] = MI; + PhysRegUsed[Alias] = true; } } @@ -132,55 +131,47 @@ void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { PhysRegUsed[Reg] = false; for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); - *AliasSet; ++AliasSet) { - if (MachineInstr *LastUse = PhysRegInfo[*AliasSet]) { - if (PhysRegUsed[*AliasSet]) - RegistersKilled.insert(std::make_pair(LastUse, *AliasSet)); + unsigned Alias = *AliasSet; ++AliasSet) { + if (MachineInstr *LastUse = PhysRegInfo[Alias]) { + if (PhysRegUsed[Alias]) + RegistersKilled.insert(std::make_pair(LastUse, Alias)); else - RegistersDead.insert(std::make_pair(LastUse, *AliasSet)); + RegistersDead.insert(std::make_pair(LastUse, Alias)); } - PhysRegInfo[*AliasSet] = MI; - PhysRegUsed[*AliasSet] = false; + PhysRegInfo[Alias] = MI; + PhysRegUsed[Alias] = false; } } bool LiveVariables::runOnMachineFunction(MachineFunction &MF) { + const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo(); + RegInfo = MF.getTarget().getRegisterInfo(); + assert(RegInfo && "Target doesn't have register information?"); + // First time though, initialize AllocatablePhysicalRegisters for the target if (AllocatablePhysicalRegisters.empty()) { - const MRegisterInfo &MRI = *MF.getTarget().getRegisterInfo(); - assert(&MRI && "Target doesn't have register information?"); - // Make space, initializing to false... - AllocatablePhysicalRegisters.resize(MRegisterInfo::FirstVirtualRegister); + AllocatablePhysicalRegisters.resize(RegInfo->getNumRegs()); // Loop over all of the register classes... - for (MRegisterInfo::regclass_iterator RCI = MRI.regclass_begin(), - E = MRI.regclass_end(); RCI != E; ++RCI) + for (MRegisterInfo::regclass_iterator RCI = RegInfo->regclass_begin(), + E = RegInfo->regclass_end(); RCI != E; ++RCI) // Loop over all of the allocatable registers in the function... for (TargetRegisterClass::iterator I = (*RCI)->allocation_order_begin(MF), E = (*RCI)->allocation_order_end(MF); I != E; ++I) AllocatablePhysicalRegisters[*I] = true; // The reg is allocatable! } - // Build BBMap... - unsigned BBNum = 0; - for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) - BBMap[I->getBasicBlock()] = std::make_pair(I, BBNum++); - // PhysRegInfo - Keep track of which instruction was the last use of a // physical register. This is a purely local property, because all physical // register references as presumed dead across basic blocks. // - MachineInstr *PhysRegInfoA[MRegisterInfo::FirstVirtualRegister]; - bool PhysRegUsedA[MRegisterInfo::FirstVirtualRegister]; - std::fill(PhysRegInfoA, PhysRegInfoA+MRegisterInfo::FirstVirtualRegister, - (MachineInstr*)0); + MachineInstr *PhysRegInfoA[RegInfo->getNumRegs()]; + bool PhysRegUsedA[RegInfo->getNumRegs()]; + std::fill(PhysRegInfoA, PhysRegInfoA+RegInfo->getNumRegs(), (MachineInstr*)0); PhysRegInfo = PhysRegInfoA; PhysRegUsed = PhysRegUsedA; - const TargetInstrInfo &TII = MF.getTarget().getInstrInfo(); - RegInfo = MF.getTarget().getRegisterInfo(); - /// Get some space for a respectable number of registers... VirtRegInfo.resize(64); @@ -189,18 +180,17 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &MF) { // register before its uses due to dominance properties of SSA (except for PHI // nodes, which are treated as a special case). // - const BasicBlock *Entry = MF.getFunction()->begin(); - for (df_iterator DFI = df_begin(Entry), E = df_end(Entry); - DFI != E; ++DFI) { - const BasicBlock *BB = *DFI; - std::pair &BBRec = BBMap.find(BB)->second; - MachineBasicBlock *MBB = BBRec.first; - unsigned BBNum = BBRec.second; + MachineBasicBlock *Entry = MF.begin(); + std::set Visited; + for (df_ext_iterator DFI = df_ext_begin(Entry, Visited), + E = df_ext_end(Entry, Visited); DFI != E; ++DFI) { + MachineBasicBlock *MBB = *DFI; + unsigned BBNum = MBB->getNumber(); // Loop over all of the instructions, processing them. for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); - I != E; ++I) { - MachineInstr *MI = *I; + I != E; ++I) { + MachineInstr *MI = I; const TargetInstrDescriptor &MID = TII.get(MI->getOpcode()); // Process all of the operands of the instruction... @@ -209,24 +199,24 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &MF) { // 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->getOpcode() == TargetInstrInfo::PHI) - NumOperandsToProcess = 1; + NumOperandsToProcess = 1; // Loop over implicit uses, using them. for (const unsigned *ImplicitUses = MID.ImplicitUses; *ImplicitUses; ++ImplicitUses) - HandlePhysRegUse(*ImplicitUses, MI); + HandlePhysRegUse(*ImplicitUses, MI); // Process all explicit uses... for (unsigned i = 0; i != NumOperandsToProcess; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (MO.isUse()) { - if (MO.isVirtualRegister() && !MO.getVRegValueOrNull()) { - HandleVirtRegUse(getVarInfo(MO.getReg()), MBB, MI); - } else if (MO.isPhysicalRegister() && + MachineOperand &MO = MI->getOperand(i); + if (MO.isUse() && MO.isRegister() && MO.getReg()) { + if (MRegisterInfo::isVirtualRegister(MO.getReg())){ + HandleVirtRegUse(getVarInfo(MO.getReg()), MBB, MI); + } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && AllocatablePhysicalRegisters[MO.getReg()]) { - HandlePhysRegUse(MO.getReg(), MI); - } - } + HandlePhysRegUse(MO.getReg(), MI); + } + } } // Loop over implicit defs, defining them. @@ -236,20 +226,20 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &MF) { // Process all explicit defs... for (unsigned i = 0; i != NumOperandsToProcess; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (MO.isDef()) { - if (MO.isVirtualRegister()) { - VarInfo &VRInfo = getVarInfo(MO.getReg()); - - assert(VRInfo.DefBlock == 0 && "Variable multiply defined!"); - VRInfo.DefBlock = MBB; // Created here... - VRInfo.DefInst = MI; - VRInfo.Kills.push_back(std::make_pair(MBB, MI)); // Defaults to dead - } else if (MO.isPhysicalRegister() && + MachineOperand &MO = MI->getOperand(i); + if (MO.isDef() && MO.isRegister() && MO.getReg()) { + if (MRegisterInfo::isVirtualRegister(MO.getReg())) { + VarInfo &VRInfo = getVarInfo(MO.getReg()); + + assert(VRInfo.DefInst == 0 && "Variable multiply defined!"); + VRInfo.DefInst = MI; + // Defaults to dead + VRInfo.Kills.push_back(MI); + } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && AllocatablePhysicalRegisters[MO.getReg()]) { - HandlePhysRegDef(MO.getReg(), MI); - } - } + HandlePhysRegDef(MO.getReg(), MI); + } + } } } @@ -257,33 +247,35 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &MF) { // 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. - for (succ_const_iterator SI = succ_begin(BB), E = succ_end(BB); - SI != E; ++SI) { - MachineBasicBlock *Succ = BBMap.find(*SI)->second.first; + for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), + E = MBB->succ_end(); SI != E; ++SI) { + MachineBasicBlock *Succ = *SI; // PHI nodes are guaranteed to be at the top of the block... - for (MachineBasicBlock::iterator I = Succ->begin(), E = Succ->end(); - I != E && (*I)->getOpcode() == TargetInstrInfo::PHI; ++I) { - MachineInstr *MI = *I; - for (unsigned i = 1; ; i += 2) - if (MI->getOperand(i+1).getMachineBasicBlock() == MBB) { - MachineOperand &MO = MI->getOperand(i); - if (!MO.getVRegValueOrNull()) { - VarInfo &VRInfo = getVarInfo(MO.getReg()); - - // Only mark it alive only in the block we are representing... - MarkVirtRegAliveInBlock(VRInfo, BB); - break; // Found the PHI entry for this block... - } - } + for (MachineBasicBlock::iterator MI = Succ->begin(), ME = Succ->end(); + MI != ME && MI->getOpcode() == TargetInstrInfo::PHI; ++MI) { + for (unsigned i = 1; ; i += 2) { + assert(MI->getNumOperands() > i+1 && + "Didn't find an entry for our predecessor??"); + if (MI->getOperand(i+1).getMachineBasicBlock() == MBB) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.getVRegValueOrNull()) { + VarInfo &VRInfo = getVarInfo(MO.getReg()); + + // Only mark it alive only in the block we are representing... + MarkVirtRegAliveInBlock(VRInfo, MBB); + break; // Found the PHI entry for this block... + } + } + } } } // Loop over PhysRegInfo, killing any registers that are available at the // end of the basic block. This also resets the PhysRegInfo map. - for (unsigned i = 0, e = MRegisterInfo::FirstVirtualRegister; i != e; ++i) + for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i) if (PhysRegInfo[i]) - HandlePhysRegDef(i, 0); + HandlePhysRegDef(i, 0); } // Convert the information we have gathered into VirtRegInfo and transform it @@ -291,16 +283,63 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &MF) { // for (unsigned i = 0, e = VirtRegInfo.size(); i != e; ++i) for (unsigned j = 0, e = VirtRegInfo[i].Kills.size(); j != e; ++j) { - if (VirtRegInfo[i].Kills[j].second == VirtRegInfo[i].DefInst) - RegistersDead.insert(std::make_pair(VirtRegInfo[i].Kills[j].second, - i + MRegisterInfo::FirstVirtualRegister)); + if (VirtRegInfo[i].Kills[j] == VirtRegInfo[i].DefInst) + RegistersDead.insert(std::make_pair(VirtRegInfo[i].Kills[j], + i + MRegisterInfo::FirstVirtualRegister)); else - RegistersKilled.insert(std::make_pair(VirtRegInfo[i].Kills[j].second, - i + MRegisterInfo::FirstVirtualRegister)); + RegistersKilled.insert(std::make_pair(VirtRegInfo[i].Kills[j], + i + MRegisterInfo::FirstVirtualRegister)); } - + + // Check to make sure there are no unreachable blocks in the MC CFG for the + // function. If so, it is due to a bug in the instruction selector or some + // other part of the code generator if this happens. +#ifndef NDEBUG + for(MachineFunction::iterator i = MF.begin(), e = MF.end(); i != e; ++i) + assert(Visited.count(&*i) != 0 && "unreachable basic block found"); +#endif + return false; } -} // End llvm namespace +/// instructionChanged - When the address of an instruction changes, this +/// method should be called so that live variables can update its internal +/// data structures. This removes the records for OldMI, transfering them to +/// the records for NewMI. +void LiveVariables::instructionChanged(MachineInstr *OldMI, + MachineInstr *NewMI) { + // If the instruction defines any virtual registers, update the VarInfo for + // the instruction. + for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = OldMI->getOperand(i); + if (MO.isRegister() && MO.isDef() && MO.getReg() && + MRegisterInfo::isVirtualRegister(MO.getReg())) { + unsigned Reg = MO.getReg(); + VarInfo &VI = getVarInfo(Reg); + if (VI.DefInst == OldMI) + VI.DefInst = NewMI; + } + } + + // Move the killed information over... + killed_iterator I, E; + tie(I, E) = killed_range(OldMI); + std::vector Regs; + for (killed_iterator A = I; A != E; ++A) + Regs.push_back(A->second); + RegistersKilled.erase(I, E); + + for (unsigned i = 0, e = Regs.size(); i != e; ++i) + RegistersKilled.insert(std::make_pair(NewMI, Regs[i])); + Regs.clear(); + + // Move the dead information over... + tie(I, E) = dead_range(OldMI); + for (killed_iterator A = I; A != E; ++A) + Regs.push_back(A->second); + RegistersDead.erase(I, E); + + for (unsigned i = 0, e = Regs.size(); i != e; ++i) + RegistersDead.insert(std::make_pair(NewMI, Regs[i])); +}