summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/CodeGen')
-rw-r--r--llvm/lib/CodeGen/CMakeLists.txt2
-rw-r--r--llvm/lib/CodeGen/SafeStack.cpp88
-rw-r--r--llvm/lib/CodeGen/SafeStackColoring.cpp289
-rw-r--r--llvm/lib/CodeGen/SafeStackColoring.h149
-rw-r--r--llvm/lib/CodeGen/SafeStackLayout.cpp138
-rw-r--r--llvm/lib/CodeGen/SafeStackLayout.h68
6 files changed, 696 insertions, 38 deletions
diff --git a/llvm/lib/CodeGen/CMakeLists.txt b/llvm/lib/CodeGen/CMakeLists.txt
index 03314889c8e..d0afc919c3a 100644
--- a/llvm/lib/CodeGen/CMakeLists.txt
+++ b/llvm/lib/CodeGen/CMakeLists.txt
@@ -105,6 +105,8 @@ add_llvm_library(LLVMCodeGen
RegUsageInfoCollector.cpp
RegUsageInfoPropagate.cpp
SafeStack.cpp
+ SafeStackColoring.cpp
+ SafeStackLayout.cpp
ScheduleDAG.cpp
ScheduleDAGInstrs.cpp
ScheduleDAGPrinter.cpp
diff --git a/llvm/lib/CodeGen/SafeStack.cpp b/llvm/lib/CodeGen/SafeStack.cpp
index b4a2ec436db..19cd59b9dba 100644
--- a/llvm/lib/CodeGen/SafeStack.cpp
+++ b/llvm/lib/CodeGen/SafeStack.cpp
@@ -15,6 +15,8 @@
//
//===----------------------------------------------------------------------===//
+#include "SafeStackColoring.h"
+#include "SafeStackLayout.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/Triple.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
@@ -46,6 +48,7 @@
#include "llvm/Transforms/Utils/ModuleUtils.h"
using namespace llvm;
+using namespace llvm::safestack;
#define DEBUG_TYPE "safestack"
@@ -516,40 +519,66 @@ Value *SafeStack::moveStaticAllocasToUnsafeStack(
DIBuilder DIB(*F.getParent());
- // Compute maximum alignment among static objects on the unsafe stack.
- unsigned MaxAlignment = 0;
+ StackColoring SSC(F, StaticAllocas);
+ SSC.run();
+ SSC.removeAllMarkers();
+
+ // Unsafe stack always grows down.
+ StackLayout SSL(StackAlignment);
+ if (StackGuardSlot) {
+ Type *Ty = StackGuardSlot->getAllocatedType();
+ unsigned Align =
+ std::max(DL->getPrefTypeAlignment(Ty), StackGuardSlot->getAlignment());
+ SSL.addObject(StackGuardSlot, getStaticAllocaAllocationSize(StackGuardSlot),
+ Align, SSC.getLiveRange(StackGuardSlot));
+ }
+
for (Argument *Arg : ByValArguments) {
Type *Ty = Arg->getType()->getPointerElementType();
+ uint64_t Size = DL->getTypeStoreSize(Ty);
+ if (Size == 0)
+ Size = 1; // Don't create zero-sized stack objects.
+
+ // Ensure the object is properly aligned.
unsigned Align = std::max((unsigned)DL->getPrefTypeAlignment(Ty),
Arg->getParamAlignment());
- if (Align > MaxAlignment)
- MaxAlignment = Align;
+ SSL.addObject(Arg, Size, Align, SSC.getFullLiveRange());
}
+
for (AllocaInst *AI : StaticAllocas) {
Type *Ty = AI->getAllocatedType();
+ uint64_t Size = getStaticAllocaAllocationSize(AI);
+ if (Size == 0)
+ Size = 1; // Don't create zero-sized stack objects.
+
+ // Ensure the object is properly aligned.
unsigned Align =
std::max((unsigned)DL->getPrefTypeAlignment(Ty), AI->getAlignment());
- if (Align > MaxAlignment)
- MaxAlignment = Align;
+
+ SSL.addObject(AI, Size, Align, SSC.getLiveRange(AI));
}
- if (MaxAlignment > StackAlignment) {
+ SSL.computeLayout();
+ unsigned FrameAlignment = SSL.getFrameAlignment();
+
+ // FIXME: tell SSL that we start at a less-then-MaxAlignment aligned location
+ // (AlignmentSkew).
+ if (FrameAlignment > StackAlignment) {
// Re-align the base pointer according to the max requested alignment.
- assert(isPowerOf2_32(MaxAlignment));
+ assert(isPowerOf2_32(FrameAlignment));
IRB.SetInsertPoint(BasePointer->getNextNode());
BasePointer = cast<Instruction>(IRB.CreateIntToPtr(
IRB.CreateAnd(IRB.CreatePtrToInt(BasePointer, IntPtrTy),
- ConstantInt::get(IntPtrTy, ~uint64_t(MaxAlignment - 1))),
+ ConstantInt::get(IntPtrTy, ~uint64_t(FrameAlignment - 1))),
StackPtrTy));
}
- int64_t StaticOffset = 0; // Current stack top.
IRB.SetInsertPoint(BasePointer->getNextNode());
if (StackGuardSlot) {
- StaticOffset += getStaticAllocaAllocationSize(StackGuardSlot);
+ unsigned Offset = SSL.getObjectOffset(StackGuardSlot);
Value *Off = IRB.CreateGEP(BasePointer, // BasePointer is i8*
- ConstantInt::get(Int32Ty, -StaticOffset));
+ ConstantInt::get(Int32Ty, -Offset));
Value *NewAI =
IRB.CreateBitCast(Off, StackGuardSlot->getType(), "StackGuardSlot");
@@ -559,29 +588,21 @@ Value *SafeStack::moveStaticAllocasToUnsafeStack(
}
for (Argument *Arg : ByValArguments) {
+ unsigned Offset = SSL.getObjectOffset(Arg);
Type *Ty = Arg->getType()->getPointerElementType();
uint64_t Size = DL->getTypeStoreSize(Ty);
if (Size == 0)
Size = 1; // Don't create zero-sized stack objects.
- // Ensure the object is properly aligned.
- unsigned Align = std::max((unsigned)DL->getPrefTypeAlignment(Ty),
- Arg->getParamAlignment());
-
- // Add alignment.
- // NOTE: we ensure that BasePointer itself is aligned to >= Align.
- StaticOffset += Size;
- StaticOffset = alignTo(StaticOffset, Align);
-
Value *Off = IRB.CreateGEP(BasePointer, // BasePointer is i8*
- ConstantInt::get(Int32Ty, -StaticOffset));
+ ConstantInt::get(Int32Ty, -Offset));
Value *NewArg = IRB.CreateBitCast(Off, Arg->getType(),
Arg->getName() + ".unsafe-byval");
// Replace alloc with the new location.
replaceDbgDeclare(Arg, BasePointer, BasePointer->getNextNode(), DIB,
- /*Deref=*/true, -StaticOffset);
+ /*Deref=*/true, -Offset);
Arg->replaceAllUsesWith(NewArg);
IRB.SetInsertPoint(cast<Instruction>(NewArg)->getNextNode());
IRB.CreateMemCpy(Off, Arg, Size, Arg->getParamAlignment());
@@ -590,23 +611,14 @@ Value *SafeStack::moveStaticAllocasToUnsafeStack(
// Allocate space for every unsafe static AllocaInst on the unsafe stack.
for (AllocaInst *AI : StaticAllocas) {
IRB.SetInsertPoint(AI);
+ unsigned Offset = SSL.getObjectOffset(AI);
- Type *Ty = AI->getAllocatedType();
uint64_t Size = getStaticAllocaAllocationSize(AI);
if (Size == 0)
Size = 1; // Don't create zero-sized stack objects.
- // Ensure the object is properly aligned.
- unsigned Align =
- std::max((unsigned)DL->getPrefTypeAlignment(Ty), AI->getAlignment());
-
- // Add alignment.
- // NOTE: we ensure that BasePointer itself is aligned to >= Align.
- StaticOffset += Size;
- StaticOffset = alignTo(StaticOffset, Align);
-
- replaceDbgDeclareForAlloca(AI, BasePointer, DIB, /*Deref=*/true, -StaticOffset);
- replaceDbgValueForAlloca(AI, BasePointer, DIB, -StaticOffset);
+ replaceDbgDeclareForAlloca(AI, BasePointer, DIB, /*Deref=*/true, -Offset);
+ replaceDbgValueForAlloca(AI, BasePointer, DIB, -Offset);
// Replace uses of the alloca with the new location.
// Insert address calculation close to each use to work around PR27844.
@@ -623,7 +635,7 @@ Value *SafeStack::moveStaticAllocasToUnsafeStack(
IRBuilder<> IRBUser(InsertBefore);
Value *Off = IRBUser.CreateGEP(BasePointer, // BasePointer is i8*
- ConstantInt::get(Int32Ty, -StaticOffset));
+ ConstantInt::get(Int32Ty, -Offset));
Value *Replacement = IRBUser.CreateBitCast(Off, AI->getType(), Name);
if (auto *PHI = dyn_cast<PHINode>(User)) {
@@ -644,13 +656,13 @@ Value *SafeStack::moveStaticAllocasToUnsafeStack(
// Re-align BasePointer so that our callees would see it aligned as
// expected.
// FIXME: no need to update BasePointer in leaf functions.
- StaticOffset = alignTo(StaticOffset, StackAlignment);
+ unsigned FrameSize = alignTo(SSL.getFrameSize(), StackAlignment);
// Update shadow stack pointer in the function epilogue.
IRB.SetInsertPoint(BasePointer->getNextNode());
Value *StaticTop =
- IRB.CreateGEP(BasePointer, ConstantInt::get(Int32Ty, -StaticOffset),
+ IRB.CreateGEP(BasePointer, ConstantInt::get(Int32Ty, -FrameSize),
"unsafe_stack_static_top");
IRB.CreateStore(StaticTop, UnsafeStackPtr);
return StaticTop;
diff --git a/llvm/lib/CodeGen/SafeStackColoring.cpp b/llvm/lib/CodeGen/SafeStackColoring.cpp
new file mode 100644
index 00000000000..709614f57e7
--- /dev/null
+++ b/llvm/lib/CodeGen/SafeStackColoring.cpp
@@ -0,0 +1,289 @@
+//===-- SafeStackColoring.cpp - SafeStack frame coloring -------*- C++ -*--===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "SafeStackColoring.h"
+
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/Support/Debug.h"
+
+using namespace llvm;
+using namespace llvm::safestack;
+
+#define DEBUG_TYPE "safestackcoloring"
+
+static cl::opt<bool> ClColoring("safe-stack-coloring",
+ cl::desc("enable safe stack coloring"),
+ cl::Hidden, cl::init(true));
+
+const StackColoring::LiveRange &StackColoring::getLiveRange(AllocaInst *AI) {
+ return LiveRanges[AllocaNumbering[AI]];
+}
+
+bool StackColoring::readMarker(Instruction *I, bool *IsStart) {
+ auto *II = dyn_cast<IntrinsicInst>(I);
+ if (!II || (II->getIntrinsicID() != Intrinsic::lifetime_start &&
+ II->getIntrinsicID() != Intrinsic::lifetime_end))
+ return false;
+
+ *IsStart = II->getIntrinsicID() == Intrinsic::lifetime_start;
+ return true;
+}
+
+void StackColoring::removeAllMarkers() {
+ for (auto *I : Markers) {
+ auto *Op = dyn_cast<Instruction>(I->getOperand(1));
+ I->eraseFromParent();
+ // Remove the operand bitcast, too, if it has no more uses left.
+ if (Op && Op->use_empty())
+ Op->eraseFromParent();
+ }
+}
+
+void StackColoring::collectMarkers() {
+ InterestingAllocas.resize(NumAllocas);
+ DenseMap<BasicBlock *, SmallDenseMap<Instruction *, Marker>> BBMarkerSet;
+
+ // Compute the set of start/end markers per basic block.
+ for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
+ AllocaInst *AI = Allocas[AllocaNo];
+ SmallVector<Instruction *, 8> WorkList;
+ WorkList.push_back(AI);
+ while (!WorkList.empty()) {
+ Instruction *I = WorkList.pop_back_val();
+ for (User *U : I->users()) {
+ if (auto *BI = dyn_cast<BitCastInst>(U)) {
+ WorkList.push_back(BI);
+ continue;
+ }
+ auto *UI = dyn_cast<Instruction>(U);
+ if (!UI)
+ continue;
+ bool IsStart;
+ if (!readMarker(UI, &IsStart))
+ continue;
+ if (IsStart)
+ InterestingAllocas.set(AllocaNo);
+ BBMarkerSet[UI->getParent()][UI] = {AllocaNo, IsStart};
+ Markers.push_back(UI);
+ }
+ }
+ }
+
+ // Compute instruction numbering. Only the following instructions are
+ // considered:
+ // * Basic block entries
+ // * Lifetime markers
+ // For each basic block, compute
+ // * the list of markers in the instruction order
+ // * the sets of allocas whose lifetime starts or ends in this BB
+ DEBUG(dbgs() << "Instructions:\n");
+ unsigned InstNo = 0;
+ for (BasicBlock *BB : depth_first(&F)) {
+ DEBUG(dbgs() << " " << InstNo << ": BB " << BB->getName() << "\n");
+ unsigned BBStart = InstNo++;
+
+ BlockLifetimeInfo &BlockInfo = BlockLiveness[BB];
+ BlockInfo.Begin.resize(NumAllocas);
+ BlockInfo.End.resize(NumAllocas);
+ BlockInfo.LiveIn.resize(NumAllocas);
+ BlockInfo.LiveOut.resize(NumAllocas);
+
+ auto &BlockMarkerSet = BBMarkerSet[BB];
+ if (BlockMarkerSet.empty()) {
+ unsigned BBEnd = InstNo;
+ BlockInstRange[BB] = std::make_pair(BBStart, BBEnd);
+ continue;
+ }
+
+ auto ProcessMarker = [&](Instruction *I, const Marker &M) {
+ DEBUG(dbgs() << " " << InstNo << ": "
+ << (M.IsStart ? "start " : "end ") << M.AllocaNo << ", "
+ << *I << "\n");
+
+ BBMarkers[BB].push_back({InstNo, M});
+
+ InstructionNumbering[I] = InstNo++;
+
+ if (M.IsStart) {
+ if (BlockInfo.End.test(M.AllocaNo))
+ BlockInfo.End.reset(M.AllocaNo);
+ BlockInfo.Begin.set(M.AllocaNo);
+ } else {
+ if (BlockInfo.Begin.test(M.AllocaNo))
+ BlockInfo.Begin.reset(M.AllocaNo);
+ BlockInfo.End.set(M.AllocaNo);
+ }
+ };
+
+ if (BlockMarkerSet.size() == 1) {
+ ProcessMarker(BlockMarkerSet.begin()->getFirst(),
+ BlockMarkerSet.begin()->getSecond());
+ } else {
+ // Scan the BB to determine the marker order.
+ for (Instruction &I : *BB) {
+ auto It = BlockMarkerSet.find(&I);
+ if (It == BlockMarkerSet.end())
+ continue;
+ ProcessMarker(&I, It->getSecond());
+ }
+ }
+
+ unsigned BBEnd = InstNo;
+ BlockInstRange[BB] = std::make_pair(BBStart, BBEnd);
+ }
+ NumInst = InstNo;
+}
+
+void StackColoring::calculateLocalLiveness() {
+ bool changed = true;
+ while (changed) {
+ changed = false;
+
+ for (BasicBlock *BB : depth_first(&F)) {
+ BlockLifetimeInfo &BlockInfo = BlockLiveness[BB];
+
+ // Compute LiveIn by unioning together the LiveOut sets of all preds.
+ BitVector LocalLiveIn;
+ for (auto *PredBB : predecessors(BB)) {
+ LivenessMap::const_iterator I = BlockLiveness.find(PredBB);
+ assert(I != BlockLiveness.end() && "Predecessor not found");
+ LocalLiveIn |= I->second.LiveOut;
+ }
+
+ // Compute LiveOut by subtracting out lifetimes that end in this
+ // block, then adding in lifetimes that begin in this block. If
+ // we have both BEGIN and END markers in the same basic block
+ // then we know that the BEGIN marker comes after the END,
+ // because we already handle the case where the BEGIN comes
+ // before the END when collecting the markers (and building the
+ // BEGIN/END vectors).
+ BitVector LocalLiveOut = LocalLiveIn;
+ LocalLiveOut.reset(BlockInfo.End);
+ LocalLiveOut |= BlockInfo.Begin;
+
+ // Update block LiveIn set, noting whether it has changed.
+ if (LocalLiveIn.test(BlockInfo.LiveIn)) {
+ changed = true;
+ BlockInfo.LiveIn |= LocalLiveIn;
+ }
+
+ // Update block LiveOut set, noting whether it has changed.
+ if (LocalLiveOut.test(BlockInfo.LiveOut)) {
+ changed = true;
+ BlockInfo.LiveOut |= LocalLiveOut;
+ }
+ }
+ } // while changed.
+}
+
+void StackColoring::calculateLiveIntervals() {
+ for (auto IT : BlockLiveness) {
+ BasicBlock *BB = IT.getFirst();
+ BlockLifetimeInfo &BlockInfo = IT.getSecond();
+ unsigned BBStart, BBEnd;
+ std::tie(BBStart, BBEnd) = BlockInstRange[BB];
+
+ BitVector Started, Ended;
+ Started.resize(NumAllocas);
+ Ended.resize(NumAllocas);
+ SmallVector<unsigned, 8> Start;
+ Start.resize(NumAllocas);
+
+ // LiveIn ranges start at the first instruction.
+ for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
+ if (BlockInfo.LiveIn.test(AllocaNo)) {
+ Started.set(AllocaNo);
+ Start[AllocaNo] = BBStart;
+ }
+ }
+
+ for (auto &It : BBMarkers[BB]) {
+ unsigned InstNo = It.first;
+ bool IsStart = It.second.IsStart;
+ unsigned AllocaNo = It.second.AllocaNo;
+
+ if (IsStart) {
+ assert(!Started.test(AllocaNo));
+ Started.set(AllocaNo);
+ Ended.reset(AllocaNo);
+ Start[AllocaNo] = InstNo;
+ } else {
+ assert(!Ended.test(AllocaNo));
+ if (Started.test(AllocaNo)) {
+ LiveRanges[AllocaNo].AddRange(Start[AllocaNo], InstNo);
+ Started.reset(AllocaNo);
+ }
+ Ended.set(AllocaNo);
+ }
+ }
+
+ for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
+ if (Started.test(AllocaNo))
+ LiveRanges[AllocaNo].AddRange(Start[AllocaNo], BBEnd);
+ }
+}
+
+LLVM_DUMP_METHOD void StackColoring::dumpAllocas() {
+ dbgs() << "Allocas:\n";
+ for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
+ dbgs() << " " << AllocaNo << ": " << *Allocas[AllocaNo] << "\n";
+}
+
+LLVM_DUMP_METHOD void StackColoring::dumpBlockLiveness() {
+ dbgs() << "Block liveness:\n";
+ for (auto IT : BlockLiveness) {
+ BasicBlock *BB = IT.getFirst();
+ BlockLifetimeInfo &BlockInfo = BlockLiveness[BB];
+ auto BlockRange = BlockInstRange[BB];
+ dbgs() << " BB [" << BlockRange.first << ", " << BlockRange.second
+ << "): begin " << BlockInfo.Begin << ", end " << BlockInfo.End
+ << ", livein " << BlockInfo.LiveIn << ", liveout "
+ << BlockInfo.LiveOut << "\n";
+ }
+}
+
+LLVM_DUMP_METHOD void StackColoring::dumpLiveRanges() {
+ dbgs() << "Alloca liveness:\n";
+ for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
+ LiveRange &Range = LiveRanges[AllocaNo];
+ dbgs() << " " << AllocaNo << ": " << Range << "\n";
+ }
+}
+
+void StackColoring::run() {
+ DEBUG(dumpAllocas());
+
+ for (unsigned I = 0; I < NumAllocas; ++I)
+ AllocaNumbering[Allocas[I]] = I;
+ LiveRanges.resize(NumAllocas);
+
+ collectMarkers();
+
+ if (!ClColoring) {
+ for (auto &R : LiveRanges) {
+ R.SetMaximum(1);
+ R.AddRange(0, 1);
+ }
+ return;
+ }
+
+ for (auto &R : LiveRanges)
+ R.SetMaximum(NumInst);
+ for (unsigned I = 0; I < NumAllocas; ++I)
+ if (!InterestingAllocas.test(I))
+ LiveRanges[I] = getFullLiveRange();
+
+ calculateLocalLiveness();
+ DEBUG(dumpBlockLiveness());
+ calculateLiveIntervals();
+ DEBUG(dumpLiveRanges());
+}
diff --git a/llvm/lib/CodeGen/SafeStackColoring.h b/llvm/lib/CodeGen/SafeStackColoring.h
new file mode 100644
index 00000000000..08b179ccb7f
--- /dev/null
+++ b/llvm/lib/CodeGen/SafeStackColoring.h
@@ -0,0 +1,149 @@
+//===-- SafeStackColoring.h - SafeStack frame coloring ---------*- C++ -*--===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H
+#define LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/Function.h"
+#include "llvm/Support/raw_os_ostream.h"
+
+namespace llvm {
+class AllocaInst;
+
+namespace safestack {
+/// Compute live ranges of allocas.
+/// Live ranges are represented as sets of "interesting" instructions, which are
+/// defined as instructions that may start or end an alloca's lifetime. These
+/// are:
+/// * lifetime.start and lifetime.end intrinsics
+/// * first instruction of any basic block
+/// Interesting instructions are numbered in the depth-first walk of the CFG,
+/// and in the program order inside each basic block.
+class StackColoring {
+ /// A class representing liveness information for a single basic block.
+ /// Each bit in the BitVector represents the liveness property
+ /// for a different stack slot.
+ struct BlockLifetimeInfo {
+ /// Which slots BEGINs in each basic block.
+ BitVector Begin;
+ /// Which slots ENDs in each basic block.
+ BitVector End;
+ /// Which slots are marked as LIVE_IN, coming into each basic block.
+ BitVector LiveIn;
+ /// Which slots are marked as LIVE_OUT, coming out of each basic block.
+ BitVector LiveOut;
+ };
+
+public:
+ /// This class represents a set of interesting instructions where an alloca is
+ /// live.
+ struct LiveRange {
+ BitVector bv;
+ void SetMaximum(int size) { bv.resize(size); }
+ void AddRange(unsigned start, unsigned end) { bv.set(start, end); }
+ bool Overlaps(const LiveRange &Other) const {
+ return bv.anyCommon(Other.bv);
+ }
+ void Join(const LiveRange &Other) { bv |= Other.bv; }
+ };
+
+private:
+ Function &F;
+
+ /// Maps active slots (per bit) for each basic block.
+ typedef DenseMap<BasicBlock *, BlockLifetimeInfo> LivenessMap;
+ LivenessMap BlockLiveness;
+
+ /// Number of interesting instructions.
+ int NumInst;
+ /// Numeric ids for interesting instructions.
+ DenseMap<Instruction *, unsigned> InstructionNumbering;
+ /// A range [Start, End) of instruction ids for each basic block.
+ /// Instructions inside each BB have monotonic and consecutive ids.
+ DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange;
+
+ ArrayRef<AllocaInst *> Allocas;
+ unsigned NumAllocas;
+ DenseMap<AllocaInst *, unsigned> AllocaNumbering;
+ /// LiveRange for allocas.
+ SmallVector<LiveRange, 8> LiveRanges;
+
+ /// The set of allocas that have at least one lifetime.start. All other
+ /// allocas get LiveRange that corresponds to the entire function.
+ BitVector InterestingAllocas;
+ SmallVector<Instruction *, 8> Markers;
+
+ struct Marker {
+ unsigned AllocaNo;
+ bool IsStart;
+ };
+
+ /// List of {InstNo, {AllocaNo, IsStart}} for each BB, ordered by InstNo.
+ DenseMap<BasicBlock *, SmallVector<std::pair<unsigned, Marker>, 4>> BBMarkers;
+
+ void dumpAllocas();
+ void dumpBlockLiveness();
+ void dumpLiveRanges();
+
+ bool readMarker(Instruction *I, bool *IsStart);
+ void collectMarkers();
+ void calculateLocalLiveness();
+ void calculateLiveIntervals();
+
+public:
+ StackColoring(Function &F, ArrayRef<AllocaInst *> Allocas)
+ : F(F), NumInst(-1), Allocas(Allocas), NumAllocas(Allocas.size()) {}
+
+ void run();
+ void removeAllMarkers();
+
+ /// Returns a set of "interesting" instructions where the given alloca is
+ /// live. Not all instructions in a function are interesting: we pick a set
+ /// that is large enough for LiveRange::Overlaps to be correct.
+ const LiveRange &getLiveRange(AllocaInst *AI);
+
+ /// Returns a live range that represents an alloca that is live throughout the
+ /// entire function.
+ LiveRange getFullLiveRange() {
+ assert(NumInst >= 0);
+ LiveRange R;
+ R.SetMaximum(NumInst);
+ R.AddRange(0, NumInst);
+ return R;
+ }
+};
+
+static inline raw_ostream &operator<<(raw_ostream &OS, const BitVector &V) {
+ OS << "{";
+ int idx = V.find_first();
+ bool first = true;
+ while (idx >= 0) {
+ if (!first) {
+ OS << ", ";
+ }
+ first = false;
+ OS << idx;
+ idx = V.find_next(idx);
+ }
+ OS << "}";
+ return OS;
+}
+
+static inline raw_ostream &operator<<(raw_ostream &OS,
+ const StackColoring::LiveRange &R) {
+ return OS << R.bv;
+}
+
+} // namespace safestack
+} // namespace llvm
+
+#endif // LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H
diff --git a/llvm/lib/CodeGen/SafeStackLayout.cpp b/llvm/lib/CodeGen/SafeStackLayout.cpp
new file mode 100644
index 00000000000..b8190e0f215
--- /dev/null
+++ b/llvm/lib/CodeGen/SafeStackLayout.cpp
@@ -0,0 +1,138 @@
+//===-- SafeStackLayout.cpp - SafeStack frame layout -----------*- C++ -*--===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "SafeStackLayout.h"
+
+#include "llvm/IR/Instructions.h"
+#include "llvm/Support/Debug.h"
+
+using namespace llvm;
+using namespace llvm::safestack;
+
+#define DEBUG_TYPE "safestacklayout"
+
+static cl::opt<bool> ClLayout("safe-stack-layout",
+ cl::desc("enable safe stack layout"), cl::Hidden,
+ cl::init(true));
+
+LLVM_DUMP_METHOD void StackLayout::print(raw_ostream &OS) {
+ OS << "Stack regions:\n";
+ for (unsigned i = 0; i < Regions.size(); ++i) {
+ OS << " " << i << ": [" << Regions[i].Start << ", " << Regions[i].End
+ << "), range " << Regions[i].Range << "\n";
+ }
+ OS << "Stack objects:\n";
+ for (auto &IT : ObjectOffsets) {
+ OS << " at " << IT.getSecond() << ": " << *IT.getFirst() << "\n";
+ }
+}
+
+void StackLayout::addObject(const Value *V, unsigned Size, unsigned Alignment,
+ const StackColoring::LiveRange &Range) {
+ StackObjects.push_back({V, Size, Alignment, Range});
+ MaxAlignment = std::max(MaxAlignment, Alignment);
+}
+
+static unsigned AdjustStackOffset(unsigned Offset, unsigned Size,
+ unsigned Alignment) {
+ return alignTo(Offset + Size, Alignment) - Size;
+}
+
+void StackLayout::layoutObject(StackObject &Obj) {
+ if (!ClLayout) {
+ // If layout is disabled, just grab the next aligned address.
+ // This effectively disables stack coloring as well.
+ unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
+ unsigned Start = AdjustStackOffset(LastRegionEnd, Obj.Size, Obj.Alignment);
+ unsigned End = Start + Obj.Size;
+ Regions.emplace_back(Start, End, Obj.Range);
+ ObjectOffsets[Obj.Handle] = End;
+ return;
+ }
+
+ DEBUG(dbgs() << "Layout: size " << Obj.Size << ", align " << Obj.Alignment
+ << ", range " << Obj.Range << "\n");
+ assert(Obj.Alignment <= MaxAlignment);
+ unsigned Start = AdjustStackOffset(0, Obj.Size, Obj.Alignment);
+ unsigned End = Start + Obj.Size;
+ DEBUG(dbgs() << " First candidate: " << Start << " .. " << End << "\n");
+ for (const StackRegion &R : Regions) {
+ DEBUG(dbgs() << " Examining region: " << R.Start << " .. " << R.End
+ << ", range " << R.Range << "\n");
+ assert(End >= R.Start);
+ if (Start >= R.End) {
+ DEBUG(dbgs() << " Does not intersect, skip.\n");
+ continue;
+ }
+ if (Obj.Range.Overlaps(R.Range)) {
+ // Find the next appropriate location.
+ Start = AdjustStackOffset(R.End, Obj.Size, Obj.Alignment);
+ End = Start + Obj.Size;
+ DEBUG(dbgs() << " Overlaps. Next candidate: " << Start << " .. " << End
+ << "\n");
+ continue;
+ }
+ if (End <= R.End) {
+ DEBUG(dbgs() << " Reusing region(s).\n");
+ break;
+ }
+ }
+
+ unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
+ if (End > LastRegionEnd) {
+ // Insert a new region at the end. Maybe two.
+ if (Start > LastRegionEnd) {
+ DEBUG(dbgs() << " Creating gap region: " << LastRegionEnd << " .. "
+ << Start << "\n");
+ Regions.emplace_back(LastRegionEnd, Start, StackColoring::LiveRange());
+ LastRegionEnd = Start;
+ }
+ DEBUG(dbgs() << " Creating new region: " << LastRegionEnd << " .. " << End
+ << ", range " << Obj.Range << "\n");
+ Regions.emplace_back(LastRegionEnd, End, Obj.Range);
+ LastRegionEnd = End;
+ }
+
+ // Split starting and ending regions if necessary.
+ for (StackRegion &R : Regions) {
+ if (Start > R.Start && Start < R.End) {
+ StackRegion R0 = R;
+ R.Start = R0.End = Start;
+ Regions.insert(&R, R0);
+ continue;
+ }
+ if (End > R.Start && End < R.End) {
+ StackRegion R0 = R;
+ R0.End = R.Start = End;
+ Regions.insert(&R, R0);
+ break;
+ }
+ }
+
+ // Update live ranges for all affected regions.
+ for (StackRegion &R : Regions) {
+ if (Start < R.End && End > R.Start)
+ R.Range.Join(Obj.Range);
+ if (End <= R.End)
+ break;
+ }
+
+ ObjectOffsets[Obj.Handle] = End;
+}
+
+void StackLayout::computeLayout() {
+ // Simple greedy algorithm.
+ // If this is replaced with something smarter, it must preserve the property
+ // that the first object is always at the offset 0 in the stack frame (for
+ // StackProtectorSlot), or handle stack protector in some other way.
+ for (auto &Obj : StackObjects)
+ layoutObject(Obj);
+
+ DEBUG(print(dbgs()));
+}
diff --git a/llvm/lib/CodeGen/SafeStackLayout.h b/llvm/lib/CodeGen/SafeStackLayout.h
new file mode 100644
index 00000000000..313ed21c886
--- /dev/null
+++ b/llvm/lib/CodeGen/SafeStackLayout.h
@@ -0,0 +1,68 @@
+//===-- SafeStackLayout.h - SafeStack frame layout -------------*- C++ -*--===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_CODEGEN_SAFESTACKLAYOUT_H
+#define LLVM_LIB_CODEGEN_SAFESTACKLAYOUT_H
+
+#include "SafeStackColoring.h"
+
+namespace llvm {
+namespace safestack {
+
+/// Compute the layout of an unsafe stack frame.
+class StackLayout {
+ unsigned MaxAlignment;
+
+ struct StackRegion {
+ unsigned Start;
+ unsigned End;
+ StackColoring::LiveRange Range;
+ StackRegion(unsigned Start, unsigned End,
+ const StackColoring::LiveRange &Range)
+ : Start(Start), End(End), Range(Range) {}
+ };
+ /// The list of current stack regions, sorted by StackRegion::Start.
+ SmallVector<StackRegion, 16> Regions;
+
+ struct StackObject {
+ const Value *Handle;
+ unsigned Size, Alignment;
+ StackColoring::LiveRange Range;
+ };
+ SmallVector<StackObject, 8> StackObjects;
+
+ DenseMap<const Value *, unsigned> ObjectOffsets;
+
+ void layoutObject(StackObject &Obj);
+
+public:
+ StackLayout(unsigned StackAlignment) : MaxAlignment(StackAlignment) {}
+ /// Add an object to the stack frame. Value pointer is opaque and used as a
+ /// handle to retrieve the object's offset in the frame later.
+ void addObject(const Value *V, unsigned Size, unsigned Alignment,
+ const StackColoring::LiveRange &Range);
+
+ /// Run the layout computation for all previously added objects.
+ void computeLayout();
+
+ /// Returns the offset to the object start in the stack frame.
+ unsigned getObjectOffset(const Value *V) { return ObjectOffsets[V]; }
+
+ /// Returns the size of the entire frame.
+ unsigned getFrameSize() { return Regions.empty() ? 0 : Regions.back().End; }
+
+ /// Returns the alignment of the frame.
+ unsigned getFrameAlignment() { return MaxAlignment; }
+ void print(raw_ostream &OS);
+};
+
+} // namespace safestack
+} // namespace llvm
+
+#endif // LLVM_LIB_CODEGEN_SAFESTACKLAYOUT_H
OpenPOWER on IntegriCloud