diff options
author | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2012-06-05 21:54:09 +0000 |
---|---|---|
committer | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2012-06-05 21:54:09 +0000 |
commit | 4e53a40ea321c43bdf754147dd2ec064985e5b7b (patch) | |
tree | f6af24cf27b0f9684f0e8e17f9986796751c06bf /lib/CodeGen | |
parent | d88d27868bf7c2c5914c1b9ccace0ee6d7ee958a (diff) | |
download | llvm-4e53a40ea321c43bdf754147dd2ec064985e5b7b.tar.gz llvm-4e53a40ea321c43bdf754147dd2ec064985e5b7b.tar.bz2 llvm-4e53a40ea321c43bdf754147dd2ec064985e5b7b.tar.xz |
Implement LiveRangeCalc::extendToUses() and createDeadDefs().
These LiveRangeCalc methods are to be used when computing a live range
from scratch.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158027 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/CodeGen')
-rw-r--r-- | lib/CodeGen/LiveInterval.cpp | 20 | ||||
-rw-r--r-- | lib/CodeGen/LiveRangeCalc.cpp | 66 | ||||
-rw-r--r-- | lib/CodeGen/LiveRangeCalc.h | 19 |
3 files changed, 103 insertions, 2 deletions
diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp index 010ef48f5c..68bb6399a9 100644 --- a/lib/CodeGen/LiveInterval.cpp +++ b/lib/CodeGen/LiveInterval.cpp @@ -48,6 +48,26 @@ LiveInterval::iterator LiveInterval::find(SlotIndex Pos) { return I; } +VNInfo *LiveInterval::createDeadDef(SlotIndex Def, + VNInfo::Allocator &VNInfoAllocator) { + assert(!Def.isDead() && "Cannot define a value at the dead slot"); + iterator I = find(Def); + if (I == end()) { + VNInfo *VNI = getNextValue(Def, VNInfoAllocator); + ranges.push_back(LiveRange(Def, Def.getDeadSlot(), VNI)); + return VNI; + } + if (SlotIndex::isSameInstr(Def, I->start)) { + assert(I->start == Def && "Cannot insert def, already live"); + assert(I->valno->def == Def && "Inconsistent existing value def"); + return I->valno; + } + assert(SlotIndex::isEarlierInstr(Def, I->start) && "Already live at def"); + VNInfo *VNI = getNextValue(Def, VNInfoAllocator); + ranges.insert(I, LiveRange(Def, Def.getDeadSlot(), VNI)); + return VNI; +} + /// killedInRange - Return true if the interval has kills in [Start,End). bool LiveInterval::killedInRange(SlotIndex Start, SlotIndex End) const { Ranges::const_iterator r = diff --git a/lib/CodeGen/LiveRangeCalc.cpp b/lib/CodeGen/LiveRangeCalc.cpp index 71c96cc94c..3e5d7f6c29 100644 --- a/lib/CodeGen/LiveRangeCalc.cpp +++ b/lib/CodeGen/LiveRangeCalc.cpp @@ -14,6 +14,7 @@ #define DEBUG_TYPE "regalloc" #include "LiveRangeCalc.h" #include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" using namespace llvm; @@ -34,6 +35,71 @@ void LiveRangeCalc::reset(const MachineFunction *MF, } +void LiveRangeCalc::createDeadDefs(LiveInterval *LI, unsigned Reg) { + assert(MRI && Indexes && "call reset() first"); + + // Visit all def operands. If the same instruction has multiple defs of Reg, + // LI->createDeadDef() will deduplicate. + for (MachineRegisterInfo::def_iterator + I = MRI->def_begin(Reg), E = MRI->def_end(); I != E; ++I) { + const MachineInstr *MI = &*I; + // Find the corresponding slot index. + SlotIndex Idx; + if (MI->isPHI()) + // PHI defs begin at the basic block start index. + Idx = Indexes->getMBBStartIdx(MI->getParent()); + else + // Instructions are either normal 'r', or early clobber 'e'. + Idx = Indexes->getInstructionIndex(MI) + .getRegSlot(I.getOperand().isEarlyClobber()); + + // Create the def in LI. This may find an existing def. + VNInfo *VNI = LI->createDeadDef(Idx, *Alloc); + VNI->setIsPHIDef(MI->isPHI()); + } +} + + +void LiveRangeCalc::extendToUses(LiveInterval *LI, unsigned Reg) { + assert(MRI && Indexes && "call reset() first"); + + // Visit all operands that read Reg. This may include partial defs. + for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg), + E = MRI->reg_nodbg_end(); I != E; ++I) { + const MachineOperand &MO = I.getOperand(); + if (!MO.readsReg()) + continue; + // MI is reading Reg. We may have visited MI before if it happens to be + // reading Reg multiple times. That is OK, extend() is idempotent. + const MachineInstr *MI = &*I; + + // Find the SlotIndex being read. + SlotIndex Idx; + if (MI->isPHI()) { + assert(!MO.isDef() && "Cannot handle PHI def of partial register."); + // PHI operands are paired: (Reg, PredMBB). + // Extend the live range to be live-out from PredMBB. + Idx = Indexes->getMBBEndIdx(MI->getOperand(I.getOperandNo()+1).getMBB()); + } else { + // This is a normal instruction. + Idx = Indexes->getInstructionIndex(MI).getRegSlot(); + // Check for early-clobber redefs. + unsigned DefIdx; + if (MO.isDef()) { + if (MO.isEarlyClobber()) + Idx = Idx.getRegSlot(true); + } else if (MI->isRegTiedToDefOperand(I.getOperandNo(), &DefIdx)) { + // FIXME: This would be a lot easier if tied early-clobber uses also + // had an early-clobber flag. + if (MI->getOperand(DefIdx).isEarlyClobber()) + Idx = Idx.getRegSlot(true); + } + } + extend(LI, Idx); + } +} + + // Transfer information from the LiveIn vector to the live ranges. void LiveRangeCalc::updateLiveIns(VNInfo *OverrideVNI) { for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(), diff --git a/lib/CodeGen/LiveRangeCalc.h b/lib/CodeGen/LiveRangeCalc.h index 697d5cf179..3c9e40f0fe 100644 --- a/lib/CodeGen/LiveRangeCalc.h +++ b/lib/CodeGen/LiveRangeCalc.h @@ -159,11 +159,26 @@ public: /// single existing value, Alloc may be null. void extend(LiveInterval *LI, SlotIndex Kill); - /// extendToUses - Extend the live range of LI to reach all uses. + /// createDeadDefs - Create a dead def in LI for every def operand of Reg. + /// Each instruction defining Reg gets a new VNInfo with a corresponding + /// minimal live range. + void createDeadDefs(LiveInterval *LI, unsigned Reg); + + /// createDeadDefs - Create a dead def in LI for every def of LI->reg. + void createDeadDefs(LiveInterval *LI) { + createDeadDefs(LI, LI->reg); + } + + /// extendToUses - Extend the live range of LI to reach all uses of Reg. /// /// All uses must be jointly dominated by existing liveness. PHI-defs are /// inserted as needed to preserve SSA form. - void extendToUses(LiveInterval *LI); + void extendToUses(LiveInterval *LI, unsigned Reg); + + /// extendToUses - Extend the live range of LI to reach all uses of LI->reg. + void extendToUses(LiveInterval *LI) { + extendToUses(LI, LI->reg); + } //===--------------------------------------------------------------------===// // Low-level interface. |