#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SparseSet.h"
#include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/PseudoSourceValue.h"
#include "llvm/CodeGen/SlotIndexes.h"
-#include "llvm/DebugInfo.h"
+#include "llvm/CodeGen/StackProtector.h"
+#include "llvm/IR/DebugInfo.h"
+#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
VNInfo::Allocator VNInfoAllocator;
/// SlotIndex analysis object.
SlotIndexes *Indexes;
+ /// The stack protector object.
+ StackProtector *SP;
/// The list of lifetime markers found. These markers are to be removed
/// once the coloring is done.
SmallVector<MachineInstr*, 8> Markers;
- /// SlotSizeSorter - A Sort utility for arranging stack slots according
- /// to their size.
- struct SlotSizeSorter {
- MachineFrameInfo *MFI;
- SlotSizeSorter(MachineFrameInfo *mfi) : MFI(mfi) { }
- bool operator()(int LHS, int RHS) {
- // We use -1 to denote a uninteresting slot. Place these slots at the end.
- if (LHS == -1) return false;
- if (RHS == -1) return true;
- // Sort according to size.
- return MFI->getObjectSize(LHS) > MFI->getObjectSize(RHS);
- }
-};
-
public:
static char ID;
StackColoring() : MachineFunctionPass(ID) {
/// slots to use the joint slots.
void remapInstructions(DenseMap<int, int> &SlotRemap);
- /// The input program may contain intructions which are not inside lifetime
+ /// The input program may contain instructions which are not inside lifetime
/// markers. This can happen due to a bug in the compiler or due to a bug in
/// user code (for example, returning a reference to a local variable).
/// This procedure checks all of the instructions in the function and
"stack-coloring", "Merge disjoint stack slots", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
+INITIALIZE_PASS_DEPENDENCY(StackProtector)
INITIALIZE_PASS_END(StackColoring,
"stack-coloring", "Merge disjoint stack slots", false, false)
AU.addRequired<MachineDominatorTree>();
AU.addPreserved<MachineDominatorTree>();
AU.addRequired<SlotIndexes>();
+ AU.addRequired<StackProtector>();
MachineFunctionPass::getAnalysisUsage(AU);
}
SmallPtrSet<const MachineBasicBlock*, 8> NextBBSet;
- for (SmallVector<const MachineBasicBlock*, 8>::iterator
- PI = BasicBlockNumbering.begin(), PE = BasicBlockNumbering.end();
- PI != PE; ++PI) {
+ for (SmallVectorImpl<const MachineBasicBlock *>::iterator
+ PI = BasicBlockNumbering.begin(), PE = BasicBlockNumbering.end();
+ PI != PE; ++PI) {
const MachineBasicBlock *BB = *PI;
if (!BBSet.count(BB)) continue;
}
// Create the interval of the blocks that we previously found to be 'alive'.
- BitVector Alive = BlockLiveness[MBB].LiveIn;
- Alive |= BlockLiveness[MBB].LiveOut;
-
- if (Alive.any()) {
- for (int pos = Alive.find_first(); pos != -1;
- pos = Alive.find_next(pos)) {
- if (!Starts[pos].isValid())
- Starts[pos] = Indexes->getMBBStartIdx(MBB);
- if (!Finishes[pos].isValid())
- Finishes[pos] = Indexes->getMBBEndIdx(MBB);
- }
+ BlockLifetimeInfo &MBBLiveness = BlockLiveness[MBB];
+ for (int pos = MBBLiveness.LiveIn.find_first(); pos != -1;
+ pos = MBBLiveness.LiveIn.find_next(pos)) {
+ Starts[pos] = Indexes->getMBBStartIdx(MBB);
+ }
+ for (int pos = MBBLiveness.LiveOut.find_first(); pos != -1;
+ pos = MBBLiveness.LiveOut.find_next(pos)) {
+ Finishes[pos] = Indexes->getMBBEndIdx(MBB);
}
for (unsigned i = 0; i < NumSlots; ++i) {
SlotIndex F = Finishes[i];
if (S < F) {
// We have a single consecutive region.
- Intervals[i]->addRange(LiveRange(S, F, ValNum));
+ Intervals[i]->addSegment(LiveInterval::Segment(S, F, ValNum));
} else {
- // We have two non consecutive regions. This happens when
+ // We have two non-consecutive regions. This happens when
// LIFETIME_START appears after the LIFETIME_END marker.
SlotIndex NewStart = Indexes->getMBBStartIdx(MBB);
SlotIndex NewFin = Indexes->getMBBEndIdx(MBB);
- Intervals[i]->addRange(LiveRange(NewStart, F, ValNum));
- Intervals[i]->addRange(LiveRange(S, NewFin, ValNum));
+ Intervals[i]->addSegment(LiveInterval::Segment(NewStart, F, ValNum));
+ Intervals[i]->addSegment(LiveInterval::Segment(S, NewFin, ValNum));
}
}
}
const AllocaInst *To = MFI->getObjectAllocation(it->second);
assert(To && From && "Invalid allocation object");
Allocas[From] = To;
+
+ // AA might be used later for instruction scheduling, and we need it to be
+ // able to deduce the correct aliasing releationships between pointers
+ // derived from the alloca being remapped and the target of that remapping.
+ // The only safe way, without directly informing AA about the remapping
+ // somehow, is to directly update the IR to reflect the change being made
+ // here.
+ Instruction *Inst = const_cast<AllocaInst *>(To);
+ if (From->getType() != To->getType()) {
+ BitCastInst *Cast = new BitCastInst(Inst, From->getType());
+ Cast->insertAfter(Inst);
+ Inst = Cast;
+ }
+
+ // Allow the stack protector to adjust its value map to account for the
+ // upcoming replacement.
+ SP->adjustForColoring(From, To);
+
+ // Note that this will not replace uses in MMOs (which we'll update below),
+ // or anywhere else (which is why we won't delete the original
+ // instruction).
+ const_cast<AllocaInst *>(From)->replaceAllUsesWith(Inst);
}
// Remap all instructions to the new stack slots.
if (!V)
continue;
- // Climb up and find the original alloca.
- V = GetUnderlyingObject(V);
- // If we did not find one, or if the one that we found is not in our
- // map, then move on.
- if (!V || !isa<AllocaInst>(V)) {
- // Clear mem operand since we don't know for sure that it doesn't
- // alias a merged alloca.
- MMO->setValue(0);
+ // FIXME: In order to enable the use of TBAA when using AA in CodeGen,
+ // we'll also need to update the TBAA nodes in MMOs with values
+ // derived from the merged allocas. When doing this, we'll need to use
+ // the same variant of GetUnderlyingObjects that is used by the
+ // instruction scheduler (that can look through ptrtoint/inttoptr
+ // pairs).
+
+ // We've replaced IR-level uses of the remapped allocas, so we only
+ // need to replace direct uses here.
+ if (!isa<AllocaInst>(V))
continue;
- }
+
const AllocaInst *AI= cast<AllocaInst>(V);
if (!Allocas.count(AI))
continue;
SlotIndex Index = Indexes->getInstructionIndex(I);
LiveInterval *Interval = Intervals[FromSlot];
assert(Interval->find(Index) != Interval->end() &&
- "Found instruction usage outside of live range.");
+ "Found instruction usage outside of live range.");
}
#endif
MF = &Func;
MFI = MF->getFrameInfo();
Indexes = &getAnalysis<SlotIndexes>();
+ SP = &getAnalysis<StackProtector>();
BlockLiveness.clear();
BasicBlocks.clear();
BasicBlockNumbering.clear();
// Sort the slots according to their size. Place unused slots at the end.
// Use stable sort to guarantee deterministic code generation.
std::stable_sort(SortedSlots.begin(), SortedSlots.end(),
- SlotSizeSorter(MFI));
-
- bool Chanded = true;
- while (Chanded) {
- Chanded = false;
+ [this](int LHS, int RHS) {
+ // We use -1 to denote a uninteresting slot. Place these slots at the end.
+ if (LHS == -1) return false;
+ if (RHS == -1) return true;
+ // Sort according to size.
+ return MFI->getObjectSize(LHS) > MFI->getObjectSize(RHS);
+ });
+
+ bool Changed = true;
+ while (Changed) {
+ Changed = false;
for (unsigned I = 0; I < NumSlots; ++I) {
if (SortedSlots[I] == -1)
continue;
// Merge disjoint slots.
if (!First->overlaps(*Second)) {
- Chanded = true;
- First->MergeRangesInAsValue(*Second, First->getValNumInfo(0));
+ Changed = true;
+ First->MergeSegmentsInAsValue(*Second, First->getValNumInfo(0));
SlotRemap[SecondSlot] = FirstSlot;
SortedSlots[J] = -1;
DEBUG(dbgs()<<"Merging #"<<FirstSlot<<" and slots #"<<
projects / oota-llvm.git / blobdiff