Index: lib/CodeGen/CMakeLists.txt =================================================================== --- lib/CodeGen/CMakeLists.txt +++ lib/CodeGen/CMakeLists.txt @@ -105,6 +105,8 @@ RegUsageInfoCollector.cpp RegUsageInfoPropagate.cpp SafeStack.cpp + SafeStackColoring.cpp + SafeStackLayout.cpp ScheduleDAG.cpp ScheduleDAGInstrs.cpp ScheduleDAGPrinter.cpp Index: lib/CodeGen/SafeStack.cpp =================================================================== --- lib/CodeGen/SafeStack.cpp +++ lib/CodeGen/SafeStack.cpp @@ -15,13 +15,14 @@ // //===----------------------------------------------------------------------===// +#include "SafeStackColoring.h" +#include "SafeStackLayout.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/Triple.h" #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/CodeGen/Passes.h" -#include "llvm/CodeGen/Passes.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DIBuilder.h" #include "llvm/IR/DataLayout.h" @@ -517,40 +518,69 @@ DIBuilder DIB(*F.getParent()); - // Compute maximum alignment among static objects on the unsafe stack. - unsigned MaxAlignment = 0; + SafeStackColoring SSC(F, StaticAllocas); + SSC.run(); + SSC.removeAllMarkers(); + // F.dump(); + + // Unsafe stack always grows down. + SafeStackLayout SSL(StackAlignment, /*GrowsDown*/ true); + if (StackGuardSlot) { + Type *Ty = StackGuardSlot->getAllocatedType(); + unsigned Align = std::max((unsigned)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(); + SSL.dump(); + + 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(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"); @@ -560,29 +590,21 @@ } 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(NewArg)->getNextNode()); IRB.CreateMemCpy(Off, Arg, Size, Arg->getParamAlignment()); @@ -591,23 +613,14 @@ // 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. @@ -624,7 +637,7 @@ 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(User)) { @@ -645,13 +658,13 @@ // 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; Index: lib/CodeGen/SafeStackColoring.h =================================================================== --- /dev/null +++ lib/CodeGen/SafeStackColoring.h @@ -0,0 +1,135 @@ +//===-- 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; + +/// Compute live ranges of allocas. +class SafeStackColoring { + /// 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 instructions. + struct LiveRange { + BitVector bv; + void SetMaximum(int size) { bv.resize(size); } + void add(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 LivenessMap; + LivenessMap BlockLiveness; + + // Instruction numbering. + int NumInst; + DenseMap InstructionNumbering; + DenseMap> BlockInstRange; + + ArrayRef Allocas; + int NumAllocas; + DenseMap AllocaNumbering; + // LiveRange for allocas. + SmallVector LiveRanges; + + BitVector InterestingAllocas; + SmallVector Markers; + + struct Marker { + unsigned AllocaNo; + bool IsStart; + }; + + // List of {InstNo, {AllocaNo, IsStart}} for each BB, ordered by InstNo. + DenseMap, 4>> BBMarkers; + + void dumpAllocas(); + void dumpBlockLiveness(); + void dumpLiveRanges(); + + bool readMarker(Instruction *I, bool *IsStart); + void collectMarkers(); + void calculateLocalLiveness(); + void calculateLiveIntervals(); + +public: + SafeStackColoring(Function &F, ArrayRef 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.add(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 SafeStackColoring::LiveRange &R) { + return OS << R.bv; +} + +} // namespace llvm + +#endif // LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H Index: lib/CodeGen/SafeStackColoring.cpp =================================================================== --- /dev/null +++ lib/CodeGen/SafeStackColoring.cpp @@ -0,0 +1,276 @@ +//===-- 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; + +#define DEBUG_TYPE "safestackcoloring" + +const SafeStackColoring::LiveRange & +SafeStackColoring::getLiveRange(AllocaInst *AI) { + unsigned AllocaNo = AllocaNumbering[AI]; + return LiveRanges[AllocaNo]; +} + +bool SafeStackColoring::readMarker(Instruction *I, bool *IsStart) { + auto *II = dyn_cast(I); + if (!II || (II->getIntrinsicID() != Intrinsic::lifetime_start && + II->getIntrinsicID() != Intrinsic::lifetime_end)) + return false; + + *IsStart = II->getIntrinsicID() == Intrinsic::lifetime_start; + return true; +} + +void SafeStackColoring::removeAllMarkers() { + for (auto *I : Markers) { + auto *Op = dyn_cast(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 SafeStackColoring::collectMarkers() { + InterestingAllocas.resize(Allocas.size()); + DenseMap> BBMarkerSet; + + // Compute the set of start/end markers per basic block. + for (unsigned AllocaNo = 0; AllocaNo < Allocas.size(); ++AllocaNo) { + AllocaInst *AI = Allocas[AllocaNo]; + SmallVector WorkList; + WorkList.push_back(AI); + while (!WorkList.empty()) { + Instruction *I = WorkList.pop_back_val(); + for (User *U : I->users()) { + if (auto *BI = dyn_cast(U)) { + WorkList.push_back(BI); + continue; + } + auto *UI = dyn_cast(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(Allocas.size()); + BlockInfo.End.resize(Allocas.size()); + BlockInfo.LiveIn.resize(Allocas.size()); + BlockInfo.LiveOut.resize(Allocas.size()); + + auto &BlockMarkerSet = BBMarkerSet[BB]; + if (BlockMarkerSet.empty()) + 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 SafeStackColoring::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 SafeStackColoring::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(Allocas.size()); + Ended.resize(Allocas.size()); + SmallVector Start; + Start.resize(Allocas.size()); + + // LiveIn ranges start at the first instruction. + for (unsigned AllocaNo = 0; AllocaNo < Allocas.size(); ++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].add(Start[AllocaNo], InstNo); + Started.reset(AllocaNo); + } + Ended.set(AllocaNo); + } + } + + for (unsigned AllocaNo = 0; AllocaNo < Allocas.size(); ++AllocaNo) { + if (Started.test(AllocaNo)) { + LiveRanges[AllocaNo].add(Start[AllocaNo], BBEnd); + } + } + } +} + +LLVM_DUMP_METHOD void SafeStackColoring::dumpAllocas() { + DEBUG(dbgs() << "Allocas:\n"); + for (unsigned AllocaNo = 0; AllocaNo < Allocas.size(); ++AllocaNo) + DEBUG(dbgs() << " " << AllocaNo << ": " << *Allocas[AllocaNo] << "\n"); +} + +LLVM_DUMP_METHOD void SafeStackColoring::dumpBlockLiveness() { + DEBUG(dbgs() << "Block liveness:\n"); + for (auto IT : BlockLiveness) { + BasicBlock *BB = IT.getFirst(); + BlockLifetimeInfo &BlockInfo = BlockLiveness[BB]; + auto BlockRange = BlockInstRange[BB]; + DEBUG(dbgs() << " BB [" << BlockRange.first << ", " << BlockRange.second + << "): begin " << BlockInfo.Begin << ", end " << BlockInfo.End + << ", livein " << BlockInfo.LiveIn << ", liveout " + << BlockInfo.LiveOut << "\n"); + } +} + +LLVM_DUMP_METHOD void SafeStackColoring::dumpLiveRanges() { + DEBUG(dbgs() << "Alloca liveness:\n"); + for (unsigned AllocaNo = 0; AllocaNo < Allocas.size(); ++AllocaNo) { + LiveRange &Range = LiveRanges[AllocaNo]; + DEBUG(dbgs() << " " << AllocaNo << ": " << Range << "\n"); + } +} + +void SafeStackColoring::run() { + DEBUG(dumpAllocas()); + + for (unsigned I = 0; I < Allocas.size(); ++I) + AllocaNumbering[Allocas[I]] = I; + collectMarkers(); + + LiveRanges.resize(Allocas.size()); + for (auto &R : LiveRanges) + R.SetMaximum(NumInst); + for (unsigned I = 0; I < Allocas.size(); ++I) + if (!InterestingAllocas.test(I)) + LiveRanges[I] = getFullLiveRange(); + + calculateLocalLiveness(); + DEBUG(dumpBlockLiveness()); + calculateLiveIntervals(); + DEBUG(dumpLiveRanges()); +} Index: lib/CodeGen/SafeStackLayout.h =================================================================== --- /dev/null +++ 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 { + +/// Compute the layout of an unsafe stack frame. +class SafeStackLayout { + unsigned MaxAlignment; + bool GrowsDown; + + struct StackRegion { + unsigned Start; + unsigned End; + SafeStackColoring::LiveRange Range; + StackRegion(unsigned Start, unsigned End, + const SafeStackColoring::LiveRange &Range) + : Start(Start), End(End), Range(Range) {} + }; + // Sorted by StackRegion::Start. + SmallVector Regions; + + struct StackObject { + Value *Handle; + unsigned Size, Alignment; + SafeStackColoring::LiveRange Range; + }; + SmallVector StackObjects; + + DenseMap ObjectOffsets; + + void layoutObject(StackObject &Obj); + +public: + SafeStackLayout(unsigned StackAlignment, bool GrowsDown) + : MaxAlignment(StackAlignment), GrowsDown(GrowsDown) {} + /// 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(Value *V, unsigned Size, unsigned Alignment, + const SafeStackColoring::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(Value *V) { return ObjectOffsets[V]; } + + /// Returns 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 dump(); +}; + +} // namespace llvm + +#endif // LLVM_LIB_CODEGEN_SAFESTACKLAYOUT_H Index: lib/CodeGen/SafeStackLayout.cpp =================================================================== --- /dev/null +++ lib/CodeGen/SafeStackLayout.cpp @@ -0,0 +1,128 @@ +//===-- 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; + +#define DEBUG_TYPE "safestacklayout" + +LLVM_DUMP_METHOD void SafeStackLayout::dump() { + DEBUG(dbgs() << "Stack regions:\n"); + for (unsigned i = 0; i < Regions.size(); ++i) { + DEBUG(dbgs() << " " << i << ": [" << Regions[i].Start << ", " + << Regions[i].End << "), range " << Regions[i].Range << "\n"); + } + DEBUG(dbgs() << "Stack objects:\n"); + for (auto &IT : ObjectOffsets) { + DEBUG(dbgs() << " at " << IT.getSecond() << ": " << *IT.getFirst() + << "\n"); + } +} + +void SafeStackLayout::addObject(Value *V, unsigned Size, unsigned Alignment, + const SafeStackColoring::LiveRange &Range) { + StackObjects.push_back({V, Size, Alignment, Range}); + MaxAlignment = std::max(MaxAlignment, Alignment); +} + +static unsigned AdjustStackOffset(unsigned Offset, unsigned Size, + unsigned Alignment, bool GrowsDown) { + if (GrowsDown) { + return alignTo(Offset + Size, Alignment) - Size; + } + return alignTo(Offset, Alignment); +} + +void SafeStackLayout::layoutObject(StackObject &Obj) { + 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, GrowsDown); + unsigned End = Start + Obj.Size; + DEBUG(dbgs() << " First candidate: " << Start << " .. " << End << "\n"); + for (unsigned i = 0; i < Regions.size(); ++i) { + StackRegion &R = Regions[i]; + 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, GrowsDown); + 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, + SafeStackColoring::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 (unsigned i = 0; i < Regions.size(); ++i) { + StackRegion &R = Regions[i]; + 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 (unsigned i = 0; i < Regions.size(); ++i) { + StackRegion &R = Regions[i]; + if (Start < R.End && End > R.Start) + R.Range.Join(Obj.Range); + if (End <= R.End) + break; + } + + ObjectOffsets[Obj.Handle] = GrowsDown ? End : Start; +} + +void SafeStackLayout::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); +} Index: test/Transforms/SafeStack/coloring.ll =================================================================== --- /dev/null +++ test/Transforms/SafeStack/coloring.ll @@ -0,0 +1,44 @@ +; RUN: opt -safe-stack -S -mtriple=i386-pc-linux-gnu < %s -o - | FileCheck %s +; RUN: opt -safe-stack -S -mtriple=x86_64-pc-linux-gnu < %s -o - | FileCheck %s + +define void @f() safestack { +entry: +; CHECK: %[[USP:.*]] = load i8*, i8** @__safestack_unsafe_stack_ptr +; CHECK: %[[USST:.*]] = getelementptr i8, i8* %[[USP]], i32 -16 + + %x = alloca i32, align 4 + %x1 = alloca i32, align 4 + %x2 = alloca i32, align 4 + %0 = bitcast i32* %x to i8* + call void @llvm.lifetime.start(i64 4, i8* %0) + +; CHECK: %[[A1:.*]] = getelementptr i8, i8* %[[USP]], i32 -4 +; CHECK: %[[A2:.*]] = bitcast i8* %[[A1]] to i32* +; CHECK: call void @capture(i32* nonnull %[[A2]]) + + call void @capture(i32* nonnull %x) + call void @llvm.lifetime.end(i64 4, i8* %0) + %1 = bitcast i32* %x1 to i8* + call void @llvm.lifetime.start(i64 4, i8* %1) + +; CHECK: %[[B1:.*]] = getelementptr i8, i8* %[[USP]], i32 -4 +; CHECK: %[[B2:.*]] = bitcast i8* %[[B1]] to i32* +; CHECK: call void @capture(i32* nonnull %[[B2]]) + + call void @capture(i32* nonnull %x1) + call void @llvm.lifetime.end(i64 4, i8* %1) + %2 = bitcast i32* %x2 to i8* + call void @llvm.lifetime.start(i64 4, i8* %2) + +; CHECK: %[[C1:.*]] = getelementptr i8, i8* %[[USP]], i32 -4 +; CHECK: %[[C2:.*]] = bitcast i8* %[[C1]] to i32* +; CHECK: call void @capture(i32* nonnull %[[C2]]) + + call void @capture(i32* nonnull %x2) + call void @llvm.lifetime.end(i64 4, i8* %2) + ret void +} + +declare void @llvm.lifetime.start(i64, i8* nocapture) +declare void @llvm.lifetime.end(i64, i8* nocapture) +declare void @capture(i32*) Index: test/Transforms/SafeStack/coloring2.ll =================================================================== --- /dev/null +++ test/Transforms/SafeStack/coloring2.ll @@ -0,0 +1,482 @@ +; RUN: opt -safe-stack -S -mtriple=i386-pc-linux-gnu < %s -o - | FileCheck %s +; RUN: opt -safe-stack -S -mtriple=x86_64-pc-linux-gnu < %s -o - | FileCheck %s + +; x and y share the stack slot. +define void @f() safestack { +; CHECK-LABEL: define void @f +entry: +; CHECK: %[[USP:.*]] = load i8*, i8** @__safestack_unsafe_stack_ptr +; CHECK: getelementptr i8, i8* %[[USP]], i32 -16 + + %x = alloca i32, align 4 + %y = alloca i32, align 4 + %z = alloca i32, align 4 + %x0 = bitcast i32* %x to i8* + %y0 = bitcast i32* %y to i8* + %z0 = bitcast i32* %z to i8* + + call void @llvm.lifetime.start(i64 -1, i8* %z0) + call void @llvm.lifetime.start(i64 -1, i8* %x0) + +; CHECK: getelementptr i8, i8* %[[USP]], i32 -4 + call void @capture32(i32* %x) + call void @llvm.lifetime.end(i64 -1, i8* %x0) + call void @llvm.lifetime.start(i64 -1, i8* %y0) + +; CHECK: getelementptr i8, i8* %[[USP]], i32 -4 + call void @capture32(i32* %y) + call void @llvm.lifetime.end(i64 -1, i8* %y0) + +; CHECK: getelementptr i8, i8* %[[USP]], i32 -8 + call void @capture32(i32* %z) + call void @llvm.lifetime.end(i64 -1, i8* %z0) + + ret void +} + +define void @no_markers() safestack { +; CHECK-LABEL: define void @no_markers( +entry: +; CHECK: %[[USP:.*]] = load i8*, i8** @__safestack_unsafe_stack_ptr +; CHECK: getelementptr i8, i8* %[[USP]], i32 -16 + + %x = alloca i32, align 4 + %y = alloca i32, align 4 + %x0 = bitcast i32* %x to i8* + + call void @llvm.lifetime.start(i64 -1, i8* %x0) + +; CHECK: getelementptr i8, i8* %[[USP]], i32 -4 + call void @capture32(i32* %x) + call void @llvm.lifetime.end(i64 -1, i8* %x0) + +; CHECK: getelementptr i8, i8* %[[USP]], i32 -8 + call void @capture32(i32* %y) + + ret void +} + +; x and y can't share memory, but they can split z's storage. +define void @g() safestack { +; CHECK-LABEL: define void @g +entry: +; CHECK: %[[USP:.*]] = load i8*, i8** @__safestack_unsafe_stack_ptr +; CHECK: getelementptr i8, i8* %[[USP]], i32 -16 + + %x = alloca i32, align 4 + %y = alloca i32, align 4 + %z = alloca i64, align 4 + %x0 = bitcast i32* %x to i8* + %y0 = bitcast i32* %y to i8* + %z0 = bitcast i64* %z to i8* + + call void @llvm.lifetime.start(i64 -1, i8* %x0) + call void @llvm.lifetime.start(i64 -1, i8* %y0) + +; CHECK: getelementptr i8, i8* %[[USP]], i32 -4 + call void @capture32(i32* %x) + call void @llvm.lifetime.end(i64 -1, i8* %x0) + +; CHECK: getelementptr i8, i8* %[[USP]], i32 -8 + call void @capture32(i32* %y) + call void @llvm.lifetime.end(i64 -1, i8* %y0) + call void @llvm.lifetime.start(i64 -1, i8* %z0) + +; CHECK: getelementptr i8, i8* %[[USP]], i32 -8 + call void @capture64(i64* %z) + call void @llvm.lifetime.end(i64 -1, i8* %z0) + + ret void +} + +; Both y and z fit in x's alignment gap. +define void @h() safestack { +; CHECK-LABEL: define void @h +entry: +; CHECK: %[[USP:.*]] = load i8*, i8** @__safestack_unsafe_stack_ptr +; CHECK: getelementptr i8, i8* %[[USP]], i32 -16 + + %x = alloca i32, align 16 + %z = alloca i64, align 4 + %y = alloca i32, align 4 + %x0 = bitcast i32* %x to i8* + %y0 = bitcast i32* %y to i8* + %z0 = bitcast i64* %z to i8* + + call void @llvm.lifetime.start(i64 -1, i8* %x0) + call void @llvm.lifetime.start(i64 -1, i8* %y0) + call void @llvm.lifetime.start(i64 -1, i8* %z0) + +; CHECK: getelementptr i8, i8* %[[USP]], i32 -16 + call void @capture32(i32* %x) + +; CHECK: getelementptr i8, i8* %[[USP]], i32 -12 + call void @capture32(i32* %y) + +; CHECK: getelementptr i8, i8* %[[USP]], i32 -8 + call void @capture64(i64* %z) + + call void @llvm.lifetime.end(i64 -1, i8* %x0) + call void @llvm.lifetime.end(i64 -1, i8* %y0) + call void @llvm.lifetime.end(i64 -1, i8* %z0) + + ret void +} + +; void f(bool a, bool b) { +; long x1, x2; capture64(&x1); capture64(&x2); +; if (a) { +; long y; capture64(&y); +; if (b) { +; long y1; capture64(&y1); +; } else { +; long y2; capture64(&y2); +; } +; } else { +; long z; capture64(&z); +; if (b) { +; long z1; capture64(&z1); +; } else { +; long z2; capture64(&z2); +; } +; } +; } +; Everything fits in 4 x 64-bit slots. +define void @i(i1 zeroext %a, i1 zeroext %b) safestack { +; CHECK-LABEL: define void @i +entry: +; CHECK: %[[USP:.*]] = load i8*, i8** @__safestack_unsafe_stack_ptr +; CHECK-NEXT: getelementptr i8, i8* %[[USP]], i32 -32 + %x1 = alloca i64, align 8 + %x2 = alloca i64, align 8 + %y = alloca i64, align 8 + %y1 = alloca i64, align 8 + %y2 = alloca i64, align 8 + %z = alloca i64, align 8 + %z1 = alloca i64, align 8 + %z2 = alloca i64, align 8 + %0 = bitcast i64* %x1 to i8* + call void @llvm.lifetime.start(i64 -1, i8* %0) + %1 = bitcast i64* %x2 to i8* + call void @llvm.lifetime.start(i64 -1, i8* %1) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -8 +; CHECK: call void @capture64( + call void @capture64(i64* nonnull %x1) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -16 +; CHECK: call void @capture64( + call void @capture64(i64* nonnull %x2) + br i1 %a, label %if.then, label %if.else4 + +if.then: ; preds = %entry + %2 = bitcast i64* %y to i8* + call void @llvm.lifetime.start(i64 -1, i8* %2) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -24 +; CHECK: call void @capture64( + call void @capture64(i64* nonnull %y) + br i1 %b, label %if.then3, label %if.else + +if.then3: ; preds = %if.then + %3 = bitcast i64* %y1 to i8* + call void @llvm.lifetime.start(i64 -1, i8* %3) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -32 +; CHECK: call void @capture64( + call void @capture64(i64* nonnull %y1) + call void @llvm.lifetime.end(i64 -1, i8* %3) + br label %if.end + +if.else: ; preds = %if.then + %4 = bitcast i64* %y2 to i8* + call void @llvm.lifetime.start(i64 -1, i8* %4) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -32 +; CHECK: call void @capture64( + call void @capture64(i64* nonnull %y2) + call void @llvm.lifetime.end(i64 -1, i8* %4) + br label %if.end + +if.end: ; preds = %if.else, %if.then3 + call void @llvm.lifetime.end(i64 -1, i8* %2) + br label %if.end9 + +if.else4: ; preds = %entry + %5 = bitcast i64* %z to i8* + call void @llvm.lifetime.start(i64 -1, i8* %5) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -24 +; CHECK: call void @capture64( + call void @capture64(i64* nonnull %z) + br i1 %b, label %if.then6, label %if.else7 + +if.then6: ; preds = %if.else4 + %6 = bitcast i64* %z1 to i8* + call void @llvm.lifetime.start(i64 -1, i8* %6) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -32 +; CHECK: call void @capture64( + call void @capture64(i64* nonnull %z1) + call void @llvm.lifetime.end(i64 -1, i8* %6) + br label %if.end8 + +if.else7: ; preds = %if.else4 + %7 = bitcast i64* %z2 to i8* + call void @llvm.lifetime.start(i64 -1, i8* %7) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -32 +; CHECK: call void @capture64( + call void @capture64(i64* nonnull %z2) + call void @llvm.lifetime.end(i64 -1, i8* %7) + br label %if.end8 + +if.end8: ; preds = %if.else7, %if.then6 + call void @llvm.lifetime.end(i64 -1, i8* %5) + br label %if.end9 + +if.end9: ; preds = %if.end8, %if.end + call void @llvm.lifetime.end(i64 -1, i8* %1) + call void @llvm.lifetime.end(i64 -1, i8* %0) + ret void +} + +; lifetime for x ends in 2 different BBs +define void @no_merge1(i1 %d) safestack { +; CHECK-LABEL: define void @no_merge1( +entry: +; CHECK: %[[USP:.*]] = load i8*, i8** @__safestack_unsafe_stack_ptr +; CHECK-NEXT: getelementptr i8, i8* %[[USP]], i32 -16 + %x = alloca i32, align 4 + %y = alloca i32, align 4 + %x0 = bitcast i32* %x to i8* + %y0 = bitcast i32* %y to i8* + call void @llvm.lifetime.start(i64 -1, i8* %x0) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -4 +; CHECK: call void @capture32( + call void @capture32(i32* %x) + br i1 %d, label %bb2, label %bb3 +bb2: + call void @llvm.lifetime.start(i64 -1, i8* %y0) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -8 +; CHECK: call void @capture32( + call void @capture32(i32* %y) + call void @llvm.lifetime.end(i64 -1, i8* %y0) + call void @llvm.lifetime.end(i64 -1, i8* %x0) + ret void +bb3: + call void @llvm.lifetime.end(i64 -1, i8* %x0) + ret void +} + +define void @merge1(i1 %d) safestack { +; CHECK-LABEL: define void @merge1( +entry: +; CHECK: %[[USP:.*]] = load i8*, i8** @__safestack_unsafe_stack_ptr +; CHECK-NEXT: getelementptr i8, i8* %[[USP]], i32 -16 + %x = alloca i32, align 4 + %y = alloca i32, align 4 + %x0 = bitcast i32* %x to i8* + %y0 = bitcast i32* %y to i8* + call void @llvm.lifetime.start(i64 -1, i8* %x0) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -4 +; CHECK: call void @capture32( + call void @capture32(i32* %x) + call void @llvm.lifetime.end(i64 -1, i8* %x0) + br i1 %d, label %bb2, label %bb3 +bb2: + call void @llvm.lifetime.start(i64 -1, i8* %y0) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -4 +; CHECK: call void @capture32( + call void @capture32(i32* %y) + call void @llvm.lifetime.end(i64 -1, i8* %y0) + ret void +bb3: + ret void +} + +; Missing lifetime.end +define void @merge2_noend(i1 %d) safestack { +; CHECK-LABEL: define void @merge2_noend( +entry: +; CHECK: %[[USP:.*]] = load i8*, i8** @__safestack_unsafe_stack_ptr +; CHECK-NEXT: getelementptr i8, i8* %[[USP]], i32 -16 + %x = alloca i32, align 4 + %y = alloca i32, align 4 + %x0 = bitcast i32* %x to i8* + %y0 = bitcast i32* %y to i8* + call void @llvm.lifetime.start(i64 -1, i8* %x0) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -4 +; CHECK: call void @capture32( + call void @capture32(i32* %x) + call void @llvm.lifetime.end(i64 -1, i8* %x0) + br i1 %d, label %bb2, label %bb3 +bb2: + call void @llvm.lifetime.start(i64 -1, i8* %y0) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -4 +; CHECK: call void @capture32( + call void @capture32(i32* %y) + ret void +bb3: + ret void +} + +; Missing lifetime.end +define void @merge3_noend(i1 %d) safestack { +; CHECK-LABEL: define void @merge3_noend( +entry: +; CHECK: %[[USP:.*]] = load i8*, i8** @__safestack_unsafe_stack_ptr +; CHECK-NEXT: getelementptr i8, i8* %[[USP]], i32 -16 + %x = alloca i32, align 4 + %y = alloca i32, align 4 + %x0 = bitcast i32* %x to i8* + %y0 = bitcast i32* %y to i8* + call void @llvm.lifetime.start(i64 -1, i8* %x0) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -4 +; CHECK: call void @capture32( + call void @capture32(i32* %x) + br i1 %d, label %bb2, label %bb3 +bb2: + call void @llvm.lifetime.end(i64 -1, i8* %x0) + call void @llvm.lifetime.start(i64 -1, i8* %y0) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -4 +; CHECK: call void @capture32( + call void @capture32(i32* %y) + ret void +bb3: + ret void +} + +; Missing lifetime.start +define void @nomerge4_nostart(i1 %d) safestack { +; CHECK-LABEL: define void @nomerge4_nostart( +entry: +; CHECK: %[[USP:.*]] = load i8*, i8** @__safestack_unsafe_stack_ptr +; CHECK-NEXT: getelementptr i8, i8* %[[USP]], i32 -16 + %x = alloca i32, align 4 + %y = alloca i32, align 4 + %x0 = bitcast i32* %x to i8* + %y0 = bitcast i32* %y to i8* +; CHECK: getelementptr i8, i8* %[[USP]], i32 -4 +; CHECK: call void @capture32( + call void @capture32(i32* %x) + call void @llvm.lifetime.end(i64 -1, i8* %x0) + br i1 %d, label %bb2, label %bb3 +bb2: + call void @llvm.lifetime.start(i64 -1, i8* %y0) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -8 +; CHECK: call void @capture32( + call void @capture32(i32* %y) + ret void +bb3: + ret void +} + +define void @array_merge() safestack { +; CHECK-LABEL: define void @array_merge( +entry: +; CHECK: %[[USP:.*]] = load i8*, i8** @__safestack_unsafe_stack_ptr +; CHECK-NEXT: getelementptr i8, i8* %[[USP]], i32 -800 + %A.i1 = alloca [100 x i32], align 4 + %B.i2 = alloca [100 x i32], align 4 + %A.i = alloca [100 x i32], align 4 + %B.i = alloca [100 x i32], align 4 + %0 = bitcast [100 x i32]* %A.i to i8* + call void @llvm.lifetime.start(i64 -1, i8* %0) + %1 = bitcast [100 x i32]* %B.i to i8* + call void @llvm.lifetime.start(i64 -1, i8* %1) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -400 +; CHECK: call void @capture100x32( + call void @capture100x32([100 x i32]* %A.i) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -800 +; CHECK: call void @capture100x32( + call void @capture100x32([100 x i32]* %B.i) + call void @llvm.lifetime.end(i64 -1, i8* %0) + call void @llvm.lifetime.end(i64 -1, i8* %1) + %2 = bitcast [100 x i32]* %A.i1 to i8* + call void @llvm.lifetime.start(i64 -1, i8* %2) + %3 = bitcast [100 x i32]* %B.i2 to i8* + call void @llvm.lifetime.start(i64 -1, i8* %3) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -400 +; CHECK: call void @capture100x32( + call void @capture100x32([100 x i32]* %A.i1) +; CHECK: getelementptr i8, i8* %[[USP]], i32 -800 +; CHECK: call void @capture100x32( + call void @capture100x32([100 x i32]* %B.i2) + call void @llvm.lifetime.end(i64 -1, i8* %2) + call void @llvm.lifetime.end(i64 -1, i8* %3) + ret void +} + +define void @myCall_pr15707() safestack { +; CHECK-LABEL: define void @myCall_pr15707( +entry: +; CHECK: %[[USP:.*]] = load i8*, i8** @__safestack_unsafe_stack_ptr +; CHECK-NEXT: getelementptr i8, i8* %[[USP]], i32 -200000 + %buf1 = alloca i8, i32 100000, align 16 + %buf2 = alloca i8, i32 100000, align 16 + + call void @llvm.lifetime.start(i64 -1, i8* %buf1) + call void @llvm.lifetime.end(i64 -1, i8* %buf1) + + call void @llvm.lifetime.start(i64 -1, i8* %buf1) + call void @llvm.lifetime.start(i64 -1, i8* %buf2) + call void @capture8(i8* %buf1) + call void @capture8(i8* %buf2) + ret void +} + +; Check that we don't assert and crash even when there are allocas +; outside the declared lifetime regions. +define void @bad_range() safestack { +; CHECK-LABEL: define void @bad_range( +entry: +; CHECK: %[[USP:.*]] = load i8*, i8** @__safestack_unsafe_stack_ptr +; A.i and B.i unsafe, not merged +; CHECK-NEXT: getelementptr i8, i8* %[[USP]], i32 -800 +; A.i1 and B.i2 safe +; CHECK: = alloca [100 x i32], align 4 +; CHECK: = alloca [100 x i32], align 4 + + %A.i1 = alloca [100 x i32], align 4 + %B.i2 = alloca [100 x i32], align 4 + %A.i = alloca [100 x i32], align 4 + %B.i = alloca [100 x i32], align 4 + %0 = bitcast [100 x i32]* %A.i to i8* + call void @llvm.lifetime.start(i64 -1, i8* %0) nounwind + %1 = bitcast [100 x i32]* %B.i to i8* + call void @llvm.lifetime.start(i64 -1, i8* %1) nounwind + call void @capture100x32([100 x i32]* %A.i) + call void @capture100x32([100 x i32]* %B.i) + call void @llvm.lifetime.end(i64 -1, i8* %0) nounwind + call void @llvm.lifetime.end(i64 -1, i8* %1) nounwind + br label %block2 + +block2: + ; I am used outside the marked lifetime. + call void @capture100x32([100 x i32]* %A.i) + call void @capture100x32([100 x i32]* %B.i) + ret void +} + +%struct.Klass = type { i32, i32 } + +define i32 @shady_range(i32 %argc, i8** nocapture %argv) safestack { +; CHECK-LABEL: define i32 @shady_range( +entry: +; CHECK: %[[USP:.*]] = load i8*, i8** @__safestack_unsafe_stack_ptr +; CHECK-NEXT: getelementptr i8, i8* %[[USP]], i32 -64 + %a.i = alloca [4 x %struct.Klass], align 16 + %b.i = alloca [4 x %struct.Klass], align 16 + %a8 = bitcast [4 x %struct.Klass]* %a.i to i8* + %b8 = bitcast [4 x %struct.Klass]* %b.i to i8* + ; I am used outside the lifetime zone below: + %z2 = getelementptr inbounds [4 x %struct.Klass], [4 x %struct.Klass]* %a.i, i64 0, i64 0, i32 0 + call void @llvm.lifetime.start(i64 -1, i8* %a8) + call void @llvm.lifetime.start(i64 -1, i8* %b8) + call void @capture8(i8* %a8) + call void @capture8(i8* %b8) + %z3 = load i32, i32* %z2, align 16 + call void @llvm.lifetime.end(i64 -1, i8* %a8) + call void @llvm.lifetime.end(i64 -1, i8* %b8) + ret i32 %z3 +} + +declare void @llvm.lifetime.start(i64, i8* nocapture) +declare void @llvm.lifetime.end(i64, i8* nocapture) +declare void @capture8(i8*) +declare void @capture32(i32*) +declare void @capture64(i64*) +declare void @capture100x32([100 x i32]*)