LocalStackSlotAllocation.cpp [plain text]
#define DEBUG_TYPE "localstackalloc"
#include "llvm/CodeGen/Passes.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetFrameLowering.h"
#include "llvm/Target/TargetRegisterInfo.h"
using namespace llvm;
STATISTIC(NumAllocations, "Number of frame indices allocated into local block");
STATISTIC(NumBaseRegisters, "Number of virtual frame base registers allocated");
STATISTIC(NumReplacements, "Number of frame indices references replaced");
namespace {
class FrameRef {
MachineBasicBlock::iterator MI; int64_t LocalOffset; int FrameIdx; public:
FrameRef(MachineBasicBlock::iterator I, int64_t Offset, int Idx) :
MI(I), LocalOffset(Offset), FrameIdx(Idx) {}
bool operator<(const FrameRef &RHS) const {
return LocalOffset < RHS.LocalOffset;
}
MachineBasicBlock::iterator getMachineInstr() const { return MI; }
int64_t getLocalOffset() const { return LocalOffset; }
int getFrameIndex() const { return FrameIdx; }
};
class LocalStackSlotPass: public MachineFunctionPass {
SmallVector<int64_t,16> LocalOffsets;
void AdjustStackOffset(MachineFrameInfo *MFI, int FrameIdx, int64_t &Offset,
bool StackGrowsDown, unsigned &MaxAlign);
void calculateFrameObjectOffsets(MachineFunction &Fn);
bool insertFrameReferenceRegisters(MachineFunction &Fn);
public:
static char ID; explicit LocalStackSlotPass() : MachineFunctionPass(ID) { }
bool runOnMachineFunction(MachineFunction &MF);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
MachineFunctionPass::getAnalysisUsage(AU);
}
private:
};
}
char LocalStackSlotPass::ID = 0;
char &llvm::LocalStackSlotAllocationID = LocalStackSlotPass::ID;
INITIALIZE_PASS(LocalStackSlotPass, "localstackalloc",
"Local Stack Slot Allocation", false, false)
bool LocalStackSlotPass::runOnMachineFunction(MachineFunction &MF) {
MachineFrameInfo *MFI = MF.getFrameInfo();
const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
unsigned LocalObjectCount = MFI->getObjectIndexEnd();
if (!TRI->requiresVirtualBaseRegisters(MF) || LocalObjectCount == 0)
return true;
LocalOffsets.resize(MFI->getObjectIndexEnd());
calculateFrameObjectOffsets(MF);
bool UsedBaseRegs = insertFrameReferenceRegisters(MF);
MFI->setUseLocalStackAllocationBlock(UsedBaseRegs);
return true;
}
void LocalStackSlotPass::AdjustStackOffset(MachineFrameInfo *MFI,
int FrameIdx, int64_t &Offset,
bool StackGrowsDown,
unsigned &MaxAlign) {
if (StackGrowsDown)
Offset += MFI->getObjectSize(FrameIdx);
unsigned Align = MFI->getObjectAlignment(FrameIdx);
MaxAlign = std::max(MaxAlign, Align);
Offset = (Offset + Align - 1) / Align * Align;
int64_t LocalOffset = StackGrowsDown ? -Offset : Offset;
DEBUG(dbgs() << "Allocate FI(" << FrameIdx << ") to local offset "
<< LocalOffset << "\n");
LocalOffsets[FrameIdx] = LocalOffset;
MFI->mapLocalFrameObject(FrameIdx, LocalOffset);
if (!StackGrowsDown)
Offset += MFI->getObjectSize(FrameIdx);
++NumAllocations;
}
void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) {
MachineFrameInfo *MFI = Fn.getFrameInfo();
const TargetFrameLowering &TFI = *Fn.getTarget().getFrameLowering();
bool StackGrowsDown =
TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
int64_t Offset = 0;
unsigned MaxAlign = 0;
SmallSet<int, 16> LargeStackObjs;
if (MFI->getStackProtectorIndex() >= 0) {
AdjustStackOffset(MFI, MFI->getStackProtectorIndex(), Offset,
StackGrowsDown, MaxAlign);
for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
if (MFI->isDeadObjectIndex(i))
continue;
if (MFI->getStackProtectorIndex() == (int)i)
continue;
if (!MFI->MayNeedStackProtector(i))
continue;
AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign);
LargeStackObjs.insert(i);
}
}
for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
if (MFI->isDeadObjectIndex(i))
continue;
if (MFI->getStackProtectorIndex() == (int)i)
continue;
if (LargeStackObjs.count(i))
continue;
AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign);
}
MFI->setLocalFrameSize(Offset);
MFI->setLocalFrameMaxAlign(MaxAlign);
}
static inline bool
lookupCandidateBaseReg(int64_t BaseOffset,
int64_t FrameSizeAdjust,
int64_t LocalFrameOffset,
const MachineInstr *MI,
const TargetRegisterInfo *TRI) {
int64_t Offset = FrameSizeAdjust + LocalFrameOffset - BaseOffset;
return TRI->isFrameOffsetLegal(MI, Offset);
}
bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) {
bool UsedBaseReg = false;
MachineFrameInfo *MFI = Fn.getFrameInfo();
const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
const TargetFrameLowering &TFI = *Fn.getTarget().getFrameLowering();
bool StackGrowsDown =
TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
SmallVector<FrameRef, 64> FrameReferenceInsns;
for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
MachineInstr *MI = I;
if (MI->isDebugValue())
continue;
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
if (MI->getOperand(i).isFI()) {
if (!MFI->isObjectPreAllocated(MI->getOperand(i).getIndex()))
break;
int Idx = MI->getOperand(i).getIndex();
int64_t LocalOffset = LocalOffsets[Idx];
if (!TRI->needsFrameBaseReg(MI, LocalOffset))
break;
FrameReferenceInsns.
push_back(FrameRef(MI, LocalOffset, Idx));
break;
}
}
}
}
array_pod_sort(FrameReferenceInsns.begin(), FrameReferenceInsns.end());
MachineBasicBlock *Entry = Fn.begin();
unsigned BaseReg = 0;
int64_t BaseOffset = 0;
for (int ref = 0, e = FrameReferenceInsns.size(); ref < e ; ++ref) {
FrameRef &FR = FrameReferenceInsns[ref];
MachineBasicBlock::iterator I = FR.getMachineInstr();
MachineInstr *MI = I;
int64_t LocalOffset = FR.getLocalOffset();
int FrameIdx = FR.getFrameIndex();
assert(MFI->isObjectPreAllocated(FrameIdx) &&
"Only pre-allocated locals expected!");
DEBUG(dbgs() << "Considering: " << *MI);
unsigned idx = 0;
for (unsigned f = MI->getNumOperands(); idx != f; ++idx) {
if (!MI->getOperand(idx).isFI())
continue;
if (FrameIdx == I->getOperand(idx).getIndex())
break;
}
assert(idx < MI->getNumOperands() && "Cannot find FI operand");
int64_t Offset = 0;
int64_t FrameSizeAdjust = StackGrowsDown ? MFI->getLocalFrameSize() : 0;
DEBUG(dbgs() << " Replacing FI in: " << *MI);
if (UsedBaseReg && lookupCandidateBaseReg(BaseOffset, FrameSizeAdjust,
LocalOffset, MI, TRI)) {
DEBUG(dbgs() << " Reusing base register " << BaseReg << "\n");
Offset = FrameSizeAdjust + LocalOffset - BaseOffset;
} else {
int64_t InstrOffset = TRI->getFrameIndexInstrOffset(MI, idx);
int64_t PrevBaseOffset = BaseOffset;
BaseOffset = FrameSizeAdjust + LocalOffset + InstrOffset;
bool CanReuse = false;
for (int refn = ref + 1; refn < e; ++refn) {
FrameRef &FRN = FrameReferenceInsns[refn];
MachineBasicBlock::iterator J = FRN.getMachineInstr();
MachineInstr *MIN = J;
CanReuse = lookupCandidateBaseReg(BaseOffset, FrameSizeAdjust,
FRN.getLocalOffset(), MIN, TRI);
break;
}
if (!CanReuse) {
BaseOffset = PrevBaseOffset;
continue;
}
const MachineFunction *MF = MI->getParent()->getParent();
const TargetRegisterClass *RC = TRI->getPointerRegClass(*MF);
BaseReg = Fn.getRegInfo().createVirtualRegister(RC);
DEBUG(dbgs() << " Materializing base register " << BaseReg <<
" at frame local offset " << LocalOffset + InstrOffset << "\n");
TRI->materializeFrameBaseRegister(Entry, BaseReg, FrameIdx,
InstrOffset);
Offset = -InstrOffset;
++NumBaseRegisters;
UsedBaseReg = true;
}
assert(BaseReg != 0 && "Unable to allocate virtual base register!");
TRI->resolveFrameIndex(I, BaseReg, Offset);
DEBUG(dbgs() << "Resolved: " << *MI);
++NumReplacements;
}
return UsedBaseReg;
}