//
//===----------------------------------------------------------------------===//
+#define DEBUG_TYPE "pei"
#include "PrologEpilogInserter.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
+#include "llvm/Support/Debug.h"
#include "llvm/ADT/IndexedMap.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <climits>
char PEI::ID = 0;
-static RegisterPass<PEI>
-X("prologepilog", "Prologue/Epilogue Insertion");
+INITIALIZE_PASS_BEGIN(PEI, "prologepilog",
+ "Prologue/Epilogue Insertion", false, false)
+INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
+INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
+INITIALIZE_PASS_END(PEI, "prologepilog",
+ "Prologue/Epilogue Insertion", false, false)
+
+STATISTIC(NumVirtualFrameRegs, "Number of virtual frame regs encountered");
+STATISTIC(NumScavengedRegs, "Number of frame index regs scavenged");
/// createPrologEpilogCodeInserter - This function returns a pass that inserts
/// prolog and epilog code, and eliminates abstract frame references.
const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
RS = TRI->requiresRegisterScavenging(Fn) ? new RegScavenger() : NULL;
FrameIndexVirtualScavenging = TRI->requiresFrameIndexScavenging(Fn);
- FrameConstantRegMap.clear();
// Calculate the MaxCallFrameSize and AdjustsStack variables for the
// function's frame information. Also eliminates call frame pseudo
calculateCalleeSavedRegisters(Fn);
// Determine placement of CSR spill/restore code:
- // - with shrink wrapping, place spills and restores to tightly
+ // - With shrink wrapping, place spills and restores to tightly
// enclose regions in the Machine CFG of the function where
- // they are used. Without shrink wrapping
- // - default (no shrink wrapping), place all spills in the
+ // they are used.
+ // - Without shink wrapping (default), place all spills in the
// entry block, all restores in return blocks.
placeCSRSpillsAndRestores(Fn);
if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx;
} else {
// Spill it to the stack where we must.
- FrameIdx = MFI->CreateFixedObject(RC->getSize(), FixedSlot->Offset,
- true, false);
+ FrameIdx = MFI->CreateFixedObject(RC->getSize(), FixedSlot->Offset, true);
}
I->setFrameIdx(FrameIdx);
Offset = (Offset + Align - 1) / Align * Align;
if (StackGrowsDown) {
+ DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << -Offset << "]\n");
MFI->setObjectOffset(FrameIdx, -Offset); // Set the computed offset
} else {
+ DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << Offset << "]\n");
MFI->setObjectOffset(FrameIdx, Offset);
Offset += MFI->getObjectSize(FrameIdx);
}
AdjustStackOffset(MFI, SFI, StackGrowsDown, Offset, MaxAlign);
}
+ // FIXME: Once this is working, then enable flag will change to a target
+ // check for whether the frame is large enough to want to use virtual
+ // frame index registers. Functions which don't want/need this optimization
+ // will continue to use the existing code path.
+ if (MFI->getUseLocalStackAllocationBlock()) {
+ unsigned Align = MFI->getLocalFrameMaxAlign();
+
+ // Adjust to alignment boundary.
+ Offset = (Offset + Align - 1) / Align * Align;
+
+ DEBUG(dbgs() << "Local frame base offset: " << Offset << "\n");
+
+ // Resolve offsets for objects in the local block.
+ for (unsigned i = 0, e = MFI->getLocalFrameObjectCount(); i != e; ++i) {
+ std::pair<int, int64_t> Entry = MFI->getLocalFrameObjectMap(i);
+ int64_t FIOffset = (StackGrowsDown ? -Offset : Offset) + Entry.second;
+ DEBUG(dbgs() << "alloc FI(" << Entry.first << ") at SP[" <<
+ FIOffset << "]\n");
+ MFI->setObjectOffset(Entry.first, FIOffset);
+ }
+ // Allocate the local block
+ Offset += MFI->getLocalFrameSize();
+
+ MaxAlign = std::max(Align, MaxAlign);
+ }
+
// Make sure that the stack protector comes before the local variables on the
// stack.
- if (MFI->getStackProtectorIndex() >= 0)
+ SmallSet<int, 16> LargeStackObjs;
+ if (MFI->getStackProtectorIndex() >= 0) {
AdjustStackOffset(MFI, MFI->getStackProtectorIndex(), StackGrowsDown,
Offset, MaxAlign);
+ // Assign large stack objects first.
+ for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
+ if (MFI->isObjectPreAllocated(i) &&
+ MFI->getUseLocalStackAllocationBlock())
+ continue;
+ if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
+ continue;
+ if (RS && (int)i == RS->getScavengingFrameIndex())
+ continue;
+ if (MFI->isDeadObjectIndex(i))
+ continue;
+ if (MFI->getStackProtectorIndex() == (int)i)
+ continue;
+ if (!MFI->MayNeedStackProtector(i))
+ continue;
+
+ AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign);
+ LargeStackObjs.insert(i);
+ }
+ }
+
// Then assign frame offsets to stack objects that are not used to spill
// callee saved registers.
for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
+ if (MFI->isObjectPreAllocated(i) &&
+ MFI->getUseLocalStackAllocationBlock())
+ continue;
if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
continue;
if (RS && (int)i == RS->getScavengingFrameIndex())
continue;
if (MFI->getStackProtectorIndex() == (int)i)
continue;
+ if (LargeStackObjs.count(i))
+ continue;
AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign);
}
// If this instruction has a FrameIndex operand, we need to
// use that target machine register info object to eliminate
// it.
- TargetRegisterInfo::FrameIndexValue Value;
- unsigned VReg =
- TRI.eliminateFrameIndex(MI, SPAdj, &Value,
- FrameIndexVirtualScavenging ? NULL : RS);
- if (VReg) {
- assert (FrameIndexVirtualScavenging &&
- "Not scavenging, but virtual returned from "
- "eliminateFrameIndex()!");
- FrameConstantRegMap[VReg] = FrameConstantEntry(Value, SPAdj);
- }
+ TRI.eliminateFrameIndex(MI, SPAdj,
+ FrameIndexVirtualScavenging ? NULL : RS);
// Reset the iterator if we were at the beginning of the BB.
if (AtBeginning) {
}
}
-/// findLastUseReg - find the killing use of the specified register within
-/// the instruciton range. Return the operand number of the kill in Operand.
-static MachineBasicBlock::iterator
-findLastUseReg(MachineBasicBlock::iterator I, MachineBasicBlock::iterator ME,
- unsigned Reg) {
- // Scan forward to find the last use of this virtual register
- for (++I; I != ME; ++I) {
- MachineInstr *MI = I;
- bool isDefInsn = false;
- bool isKillInsn = false;
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
- if (MI->getOperand(i).isReg()) {
- unsigned OpReg = MI->getOperand(i).getReg();
- if (OpReg == 0 || !TargetRegisterInfo::isVirtualRegister(OpReg))
- continue;
- assert (OpReg == Reg
- && "overlapping use of scavenged index register!");
- // If this is the killing use, we have a candidate.
- if (MI->getOperand(i).isKill())
- isKillInsn = true;
- else if (MI->getOperand(i).isDef())
- isDefInsn = true;
- }
- if (isKillInsn && !isDefInsn)
- return I;
- }
- // If we hit the end of the basic block, there was no kill of
- // the virtual register, which is wrong.
- assert (0 && "scavenged index register never killed!");
- return ME;
-}
-
/// scavengeFrameVirtualRegs - Replace all frame index virtual registers
/// with physical registers. Use the register scavenger to find an
/// appropriate register to use.
E = Fn.end(); BB != E; ++BB) {
RS->enterBasicBlock(BB);
- // FIXME: The logic flow in this function is still too convoluted.
- // It needs a cleanup refactoring. Do that in preparation for tracking
- // more than one scratch register value and using ranges to find
- // available scratch registers.
- unsigned CurrentVirtReg = 0;
- unsigned CurrentScratchReg = 0;
- bool havePrevValue = false;
- TargetRegisterInfo::FrameIndexValue PrevValue(0,0);
- TargetRegisterInfo::FrameIndexValue Value(0,0);
- MachineInstr *PrevLastUseMI = NULL;
- unsigned PrevLastUseOp = 0;
- bool trackingCurrentValue = false;
+ unsigned VirtReg = 0;
+ unsigned ScratchReg = 0;
int SPAdj = 0;
// The instruction stream may change in the loop, so check BB->end()
// directly.
for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
MachineInstr *MI = I;
- bool isDefInsn = false;
- bool isKillInsn = false;
- bool clobbersScratchReg = false;
bool DoIncr = true;
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
if (MI->getOperand(i).isReg()) {
unsigned Reg = MO.getReg();
if (Reg == 0)
continue;
- if (!TargetRegisterInfo::isVirtualRegister(Reg)) {
- // If we have a previous scratch reg, check and see if anything
- // here kills whatever value is in there.
- if (Reg == CurrentScratchReg) {
- if (MO.isUse()) {
- // Two-address operands implicitly kill
- if (MO.isKill() || MI->isRegTiedToDefOperand(i))
- clobbersScratchReg = true;
- } else {
- assert (MO.isDef());
- clobbersScratchReg = true;
- }
- }
+ if (!TargetRegisterInfo::isVirtualRegister(Reg))
continue;
- }
- // If this is a def, remember that this insn defines the value.
- // This lets us properly consider insns which re-use the scratch
- // register, such as r2 = sub r2, #imm, in the middle of the
- // scratch range.
- if (MO.isDef())
- isDefInsn = true;
+
+ ++NumVirtualFrameRegs;
// Have we already allocated a scratch register for this virtual?
- if (Reg != CurrentVirtReg) {
+ if (Reg != VirtReg) {
// When we first encounter a new virtual register, it
// must be a definition.
assert(MI->getOperand(i).isDef() &&
"frame index virtual missing def!");
- // We can't have nested virtual register live ranges because
- // there's only a guarantee of one scavenged register at a time.
- assert (CurrentVirtReg == 0 &&
- "overlapping frame index virtual registers!");
-
- // If the target gave us information about what's in the register,
- // we can use that to re-use scratch regs.
- DenseMap<unsigned, FrameConstantEntry>::iterator Entry =
- FrameConstantRegMap.find(Reg);
- trackingCurrentValue = Entry != FrameConstantRegMap.end();
- if (trackingCurrentValue) {
- SPAdj = (*Entry).second.second;
- Value = (*Entry).second.first;
- } else {
- SPAdj = 0;
- Value.first = 0;
- Value.second = 0;
- }
-
- // If the scratch register from the last allocation is still
- // available, see if the value matches. If it does, just re-use it.
- if (trackingCurrentValue && havePrevValue && PrevValue == Value) {
- // FIXME: This assumes that the instructions in the live range
- // for the virtual register are exclusively for the purpose
- // of populating the value in the register. That's reasonable
- // for these frame index registers, but it's still a very, very
- // strong assumption. rdar://7322732. Better would be to
- // explicitly check each instruction in the range for references
- // to the virtual register. Only delete those insns that
- // touch the virtual register.
-
- // Find the last use of the new virtual register. Remove all
- // instruction between here and there, and update the current
- // instruction to reference the last use insn instead.
- MachineBasicBlock::iterator LastUseMI =
- findLastUseReg(I, BB->end(), Reg);
-
- // Remove all instructions up 'til the last use, since they're
- // just calculating the value we already have.
- BB->erase(I, LastUseMI);
- I = LastUseMI;
-
- // Extend the live range of the scratch register
- PrevLastUseMI->getOperand(PrevLastUseOp).setIsKill(false);
- RS->setUsed(CurrentScratchReg);
- CurrentVirtReg = Reg;
-
- // We deleted the instruction we were scanning the operands of.
- // Jump back to the instruction iterator loop. Don't increment
- // past this instruction since we updated the iterator already.
- DoIncr = false;
- break;
- }
-
// Scavenge a new scratch register
- CurrentVirtReg = Reg;
+ VirtReg = Reg;
const TargetRegisterClass *RC = Fn.getRegInfo().getRegClass(Reg);
- CurrentScratchReg = RS->FindUnusedReg(RC);
- if (CurrentScratchReg == 0)
- // No register is "free". Scavenge a register.
- CurrentScratchReg = RS->scavengeRegister(RC, I, SPAdj);
-
- PrevValue = Value;
+ ScratchReg = RS->scavengeRegister(RC, I, SPAdj);
+ ++NumScavengedRegs;
}
- // replace this reference to the virtual register with the
+ // Replace this reference to the virtual register with the
// scratch register.
- assert (CurrentScratchReg && "Missing scratch register!");
- MI->getOperand(i).setReg(CurrentScratchReg);
+ assert (ScratchReg && "Missing scratch register!");
+ MI->getOperand(i).setReg(ScratchReg);
- if (MI->getOperand(i).isKill()) {
- isKillInsn = true;
- PrevLastUseOp = i;
- PrevLastUseMI = MI;
- }
}
}
- // If this is the last use of the scratch, stop tracking it. The
- // last use will be a kill operand in an instruction that does
- // not also define the scratch register.
- if (isKillInsn && !isDefInsn) {
- CurrentVirtReg = 0;
- havePrevValue = trackingCurrentValue;
- }
- // Similarly, notice if instruction clobbered the value in the
- // register we're tracking for possible later reuse. This is noted
- // above, but enforced here since the value is still live while we
- // process the rest of the operands of the instruction.
- if (clobbersScratchReg) {
- havePrevValue = false;
- CurrentScratchReg = 0;
- }
if (DoIncr) {
RS->forward(I);
++I;
projects / oota-llvm.git / blobdiff