diff options
Diffstat (limited to 'llvm/lib/Analysis/StackSafetyAnalysis.cpp')
| -rw-r--r-- | llvm/lib/Analysis/StackSafetyAnalysis.cpp | 915 |
1 files changed, 614 insertions, 301 deletions
diff --git a/llvm/lib/Analysis/StackSafetyAnalysis.cpp b/llvm/lib/Analysis/StackSafetyAnalysis.cpp index 7f5bedabbd80..bbfc303aefac 100644 --- a/llvm/lib/Analysis/StackSafetyAnalysis.cpp +++ b/llvm/lib/Analysis/StackSafetyAnalysis.cpp @@ -9,56 +9,49 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/StackSafetyAnalysis.h" +#include "llvm/ADT/APInt.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/ModuleSummaryAnalysis.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" -#include "llvm/IR/CallSite.h" +#include "llvm/Analysis/StackLifetime.h" +#include "llvm/IR/ConstantRange.h" +#include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/GlobalValue.h" #include "llvm/IR/InstIterator.h" +#include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/InitializePasses.h" +#include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" +#include "llvm/Support/FormatVariadic.h" #include "llvm/Support/raw_ostream.h" +#include <algorithm> +#include <memory> using namespace llvm; #define DEBUG_TYPE "stack-safety" +STATISTIC(NumAllocaStackSafe, "Number of safe allocas"); +STATISTIC(NumAllocaTotal, "Number of total allocas"); + static cl::opt<int> StackSafetyMaxIterations("stack-safety-max-iterations", cl::init(20), cl::Hidden); -namespace { - -/// Rewrite an SCEV expression for a memory access address to an expression that -/// represents offset from the given alloca. -class AllocaOffsetRewriter : public SCEVRewriteVisitor<AllocaOffsetRewriter> { - const Value *AllocaPtr; +static cl::opt<bool> StackSafetyPrint("stack-safety-print", cl::init(false), + cl::Hidden); -public: - AllocaOffsetRewriter(ScalarEvolution &SE, const Value *AllocaPtr) - : SCEVRewriteVisitor(SE), AllocaPtr(AllocaPtr) {} - - const SCEV *visit(const SCEV *Expr) { - // Only re-write the expression if the alloca is used in an addition - // expression (it can be used in other types of expressions if it's cast to - // an int and passed as an argument.) - if (!isa<SCEVAddRecExpr>(Expr) && !isa<SCEVAddExpr>(Expr) && - !isa<SCEVUnknown>(Expr)) - return Expr; - return SCEVRewriteVisitor<AllocaOffsetRewriter>::visit(Expr); - } +static cl::opt<bool> StackSafetyRun("stack-safety-run", cl::init(false), + cl::Hidden); - const SCEV *visitUnknown(const SCEVUnknown *Expr) { - // FIXME: look through one or several levels of definitions? - // This can be inttoptr(AllocaPtr) and SCEV would not unwrap - // it for us. - if (Expr->getValue() == AllocaPtr) - return SE.getZero(Expr->getType()); - return Expr; - } -}; +namespace { /// Describes use of address in as a function call argument. -struct PassAsArgInfo { +template <typename CalleeTy> struct CallInfo { /// Function being called. - const GlobalValue *Callee = nullptr; + const CalleeTy *Callee = nullptr; /// Index of argument which pass address. size_t ParamNo = 0; // Offset range of address from base address (alloca or calling function @@ -66,234 +59,262 @@ struct PassAsArgInfo { // Range should never set to empty-set, that is an invalid access range // that can cause empty-set to be propagated with ConstantRange::add ConstantRange Offset; - PassAsArgInfo(const GlobalValue *Callee, size_t ParamNo, ConstantRange Offset) + CallInfo(const CalleeTy *Callee, size_t ParamNo, const ConstantRange &Offset) : Callee(Callee), ParamNo(ParamNo), Offset(Offset) {} - - StringRef getName() const { return Callee->getName(); } }; -raw_ostream &operator<<(raw_ostream &OS, const PassAsArgInfo &P) { - return OS << "@" << P.getName() << "(arg" << P.ParamNo << ", " << P.Offset - << ")"; +template <typename CalleeTy> +raw_ostream &operator<<(raw_ostream &OS, const CallInfo<CalleeTy> &P) { + return OS << "@" << P.Callee->getName() << "(arg" << P.ParamNo << ", " + << P.Offset << ")"; } /// Describe uses of address (alloca or parameter) inside of the function. -struct UseInfo { +template <typename CalleeTy> struct UseInfo { // Access range if the address (alloca or parameters). // It is allowed to be empty-set when there are no known accesses. ConstantRange Range; // List of calls which pass address as an argument. - SmallVector<PassAsArgInfo, 4> Calls; + SmallVector<CallInfo<CalleeTy>, 4> Calls; - explicit UseInfo(unsigned PointerSize) : Range{PointerSize, false} {} + UseInfo(unsigned PointerSize) : Range{PointerSize, false} {} - void updateRange(ConstantRange R) { Range = Range.unionWith(R); } + void updateRange(const ConstantRange &R) { + assert(!R.isUpperSignWrapped()); + Range = Range.unionWith(R); + assert(!Range.isUpperSignWrapped()); + } }; -raw_ostream &operator<<(raw_ostream &OS, const UseInfo &U) { +template <typename CalleeTy> +raw_ostream &operator<<(raw_ostream &OS, const UseInfo<CalleeTy> &U) { OS << U.Range; for (auto &Call : U.Calls) OS << ", " << Call; return OS; } -struct AllocaInfo { - const AllocaInst *AI = nullptr; - uint64_t Size = 0; - UseInfo Use; - - AllocaInfo(unsigned PointerSize, const AllocaInst *AI, uint64_t Size) - : AI(AI), Size(Size), Use(PointerSize) {} - - StringRef getName() const { return AI->getName(); } -}; - -raw_ostream &operator<<(raw_ostream &OS, const AllocaInfo &A) { - return OS << A.getName() << "[" << A.Size << "]: " << A.Use; +// Check if we should bailout for such ranges. +bool isUnsafe(const ConstantRange &R) { + return R.isEmptySet() || R.isFullSet() || R.isUpperSignWrapped(); } -struct ParamInfo { - const Argument *Arg = nullptr; - UseInfo Use; - - explicit ParamInfo(unsigned PointerSize, const Argument *Arg) - : Arg(Arg), Use(PointerSize) {} - - StringRef getName() const { return Arg ? Arg->getName() : "<N/A>"; } -}; - -raw_ostream &operator<<(raw_ostream &OS, const ParamInfo &P) { - return OS << P.getName() << "[]: " << P.Use; +ConstantRange addOverflowNever(const ConstantRange &L, const ConstantRange &R) { + if (L.signedAddMayOverflow(R) != + ConstantRange::OverflowResult::NeverOverflows) + return ConstantRange(L.getBitWidth(), true); + return L.add(R); } -/// Calculate the allocation size of a given alloca. Returns 0 if the -/// size can not be statically determined. -uint64_t getStaticAllocaAllocationSize(const AllocaInst *AI) { - const DataLayout &DL = AI->getModule()->getDataLayout(); - uint64_t Size = DL.getTypeAllocSize(AI->getAllocatedType()); - if (AI->isArrayAllocation()) { - auto C = dyn_cast<ConstantInt>(AI->getArraySize()); +/// Calculate the allocation size of a given alloca. Returns empty range +// in case of confution. +ConstantRange getStaticAllocaSizeRange(const AllocaInst &AI) { + const DataLayout &DL = AI.getModule()->getDataLayout(); + TypeSize TS = DL.getTypeAllocSize(AI.getAllocatedType()); + unsigned PointerSize = DL.getMaxPointerSizeInBits(); + // Fallback to empty range for alloca size. + ConstantRange R = ConstantRange::getEmpty(PointerSize); + if (TS.isScalable()) + return R; + APInt APSize(PointerSize, TS.getFixedSize(), true); + if (APSize.isNonPositive()) + return R; + if (AI.isArrayAllocation()) { + const auto *C = dyn_cast<ConstantInt>(AI.getArraySize()); if (!C) - return 0; - Size *= C->getZExtValue(); + return R; + bool Overflow = false; + APInt Mul = C->getValue(); + if (Mul.isNonPositive()) + return R; + Mul = Mul.sextOrTrunc(PointerSize); + APSize = APSize.smul_ov(Mul, Overflow); + if (Overflow) + return R; } - return Size; + R = ConstantRange(APInt::getNullValue(PointerSize), APSize); + assert(!isUnsafe(R)); + return R; } -} // end anonymous namespace - -/// Describes uses of allocas and parameters inside of a single function. -struct StackSafetyInfo::FunctionInfo { - // May be a Function or a GlobalAlias - const GlobalValue *GV = nullptr; - // Informations about allocas uses. - SmallVector<AllocaInfo, 4> Allocas; - // Informations about parameters uses. - SmallVector<ParamInfo, 4> Params; +template <typename CalleeTy> struct FunctionInfo { + std::map<const AllocaInst *, UseInfo<CalleeTy>> Allocas; + std::map<uint32_t, UseInfo<CalleeTy>> Params; // TODO: describe return value as depending on one or more of its arguments. // StackSafetyDataFlowAnalysis counter stored here for faster access. int UpdateCount = 0; - FunctionInfo(const StackSafetyInfo &SSI) : FunctionInfo(*SSI.Info) {} - - explicit FunctionInfo(const Function *F) : GV(F){}; - // Creates FunctionInfo that forwards all the parameters to the aliasee. - explicit FunctionInfo(const GlobalAlias *A); - - FunctionInfo(FunctionInfo &&) = default; - - bool IsDSOLocal() const { return GV->isDSOLocal(); }; - - bool IsInterposable() const { return GV->isInterposable(); }; - - StringRef getName() const { return GV->getName(); } - - void print(raw_ostream &O) const { + void print(raw_ostream &O, StringRef Name, const Function *F) const { // TODO: Consider different printout format after // StackSafetyDataFlowAnalysis. Calls and parameters are irrelevant then. - O << " @" << getName() << (IsDSOLocal() ? "" : " dso_preemptable") - << (IsInterposable() ? " interposable" : "") << "\n"; + O << " @" << Name << ((F && F->isDSOLocal()) ? "" : " dso_preemptable") + << ((F && F->isInterposable()) ? " interposable" : "") << "\n"; + O << " args uses:\n"; - for (auto &P : Params) - O << " " << P << "\n"; + for (auto &KV : Params) { + O << " "; + if (F) + O << F->getArg(KV.first)->getName(); + else + O << formatv("arg{0}", KV.first); + O << "[]: " << KV.second << "\n"; + } + O << " allocas uses:\n"; - for (auto &AS : Allocas) - O << " " << AS << "\n"; + if (F) { + for (auto &I : instructions(F)) { + if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) { + auto &AS = Allocas.find(AI)->second; + O << " " << AI->getName() << "[" + << getStaticAllocaSizeRange(*AI).getUpper() << "]: " << AS << "\n"; + } + } + } else { + assert(Allocas.empty()); + } } +}; + +using GVToSSI = std::map<const GlobalValue *, FunctionInfo<GlobalValue>>; -private: - FunctionInfo(const FunctionInfo &) = default; +} // namespace + +struct StackSafetyInfo::InfoTy { + FunctionInfo<GlobalValue> Info; }; -StackSafetyInfo::FunctionInfo::FunctionInfo(const GlobalAlias *A) : GV(A) { - unsigned PointerSize = A->getParent()->getDataLayout().getPointerSizeInBits(); - const GlobalObject *Aliasee = A->getBaseObject(); - const FunctionType *Type = cast<FunctionType>(Aliasee->getValueType()); - // 'Forward' all parameters to this alias to the aliasee - for (unsigned ArgNo = 0; ArgNo < Type->getNumParams(); ArgNo++) { - Params.emplace_back(PointerSize, nullptr); - UseInfo &US = Params.back().Use; - US.Calls.emplace_back(Aliasee, ArgNo, ConstantRange(APInt(PointerSize, 0))); - } -} +struct StackSafetyGlobalInfo::InfoTy { + GVToSSI Info; + SmallPtrSet<const AllocaInst *, 8> SafeAllocas; +}; namespace { class StackSafetyLocalAnalysis { - const Function &F; + Function &F; const DataLayout &DL; ScalarEvolution &SE; unsigned PointerSize = 0; const ConstantRange UnknownRange; - ConstantRange offsetFromAlloca(Value *Addr, const Value *AllocaPtr); - ConstantRange getAccessRange(Value *Addr, const Value *AllocaPtr, - uint64_t AccessSize); + ConstantRange offsetFrom(Value *Addr, Value *Base); + ConstantRange getAccessRange(Value *Addr, Value *Base, + const ConstantRange &SizeRange); + ConstantRange getAccessRange(Value *Addr, Value *Base, TypeSize Size); ConstantRange getMemIntrinsicAccessRange(const MemIntrinsic *MI, const Use &U, - const Value *AllocaPtr); + Value *Base); - bool analyzeAllUses(const Value *Ptr, UseInfo &AS); - - ConstantRange getRange(uint64_t Lower, uint64_t Upper) const { - return ConstantRange(APInt(PointerSize, Lower), APInt(PointerSize, Upper)); - } + bool analyzeAllUses(Value *Ptr, UseInfo<GlobalValue> &AS, + const StackLifetime &SL); public: - StackSafetyLocalAnalysis(const Function &F, ScalarEvolution &SE) + StackSafetyLocalAnalysis(Function &F, ScalarEvolution &SE) : F(F), DL(F.getParent()->getDataLayout()), SE(SE), PointerSize(DL.getPointerSizeInBits()), UnknownRange(PointerSize, true) {} // Run the transformation on the associated function. - StackSafetyInfo run(); + FunctionInfo<GlobalValue> run(); }; -ConstantRange -StackSafetyLocalAnalysis::offsetFromAlloca(Value *Addr, - const Value *AllocaPtr) { - if (!SE.isSCEVable(Addr->getType())) +ConstantRange StackSafetyLocalAnalysis::offsetFrom(Value *Addr, Value *Base) { + if (!SE.isSCEVable(Addr->getType()) || !SE.isSCEVable(Base->getType())) return UnknownRange; - AllocaOffsetRewriter Rewriter(SE, AllocaPtr); - const SCEV *Expr = Rewriter.visit(SE.getSCEV(Addr)); - ConstantRange Offset = SE.getUnsignedRange(Expr).zextOrTrunc(PointerSize); - assert(!Offset.isEmptySet()); - return Offset; + auto *PtrTy = IntegerType::getInt8PtrTy(SE.getContext()); + const SCEV *AddrExp = SE.getTruncateOrZeroExtend(SE.getSCEV(Addr), PtrTy); + const SCEV *BaseExp = SE.getTruncateOrZeroExtend(SE.getSCEV(Base), PtrTy); + const SCEV *Diff = SE.getMinusSCEV(AddrExp, BaseExp); + + ConstantRange Offset = SE.getSignedRange(Diff); + if (isUnsafe(Offset)) + return UnknownRange; + return Offset.sextOrTrunc(PointerSize); } -ConstantRange StackSafetyLocalAnalysis::getAccessRange(Value *Addr, - const Value *AllocaPtr, - uint64_t AccessSize) { - if (!SE.isSCEVable(Addr->getType())) +ConstantRange +StackSafetyLocalAnalysis::getAccessRange(Value *Addr, Value *Base, + const ConstantRange &SizeRange) { + // Zero-size loads and stores do not access memory. + if (SizeRange.isEmptySet()) + return ConstantRange::getEmpty(PointerSize); + assert(!isUnsafe(SizeRange)); + + ConstantRange Offsets = offsetFrom(Addr, Base); + if (isUnsafe(Offsets)) return UnknownRange; - AllocaOffsetRewriter Rewriter(SE, AllocaPtr); - const SCEV *Expr = Rewriter.visit(SE.getSCEV(Addr)); + Offsets = addOverflowNever(Offsets, SizeRange); + if (isUnsafe(Offsets)) + return UnknownRange; + return Offsets; +} - ConstantRange AccessStartRange = - SE.getUnsignedRange(Expr).zextOrTrunc(PointerSize); - ConstantRange SizeRange = getRange(0, AccessSize); - ConstantRange AccessRange = AccessStartRange.add(SizeRange); - assert(!AccessRange.isEmptySet()); - return AccessRange; +ConstantRange StackSafetyLocalAnalysis::getAccessRange(Value *Addr, Value *Base, + TypeSize Size) { + if (Size.isScalable()) + return UnknownRange; + APInt APSize(PointerSize, Size.getFixedSize(), true); + if (APSize.isNegative()) + return UnknownRange; + return getAccessRange( + Addr, Base, ConstantRange(APInt::getNullValue(PointerSize), APSize)); } ConstantRange StackSafetyLocalAnalysis::getMemIntrinsicAccessRange( - const MemIntrinsic *MI, const Use &U, const Value *AllocaPtr) { - if (auto MTI = dyn_cast<MemTransferInst>(MI)) { + const MemIntrinsic *MI, const Use &U, Value *Base) { + if (const auto *MTI = dyn_cast<MemTransferInst>(MI)) { if (MTI->getRawSource() != U && MTI->getRawDest() != U) - return getRange(0, 1); + return ConstantRange::getEmpty(PointerSize); } else { if (MI->getRawDest() != U) - return getRange(0, 1); + return ConstantRange::getEmpty(PointerSize); } - const auto *Len = dyn_cast<ConstantInt>(MI->getLength()); - // Non-constant size => unsafe. FIXME: try SCEV getRange. - if (!Len) + + auto *CalculationTy = IntegerType::getIntNTy(SE.getContext(), PointerSize); + if (!SE.isSCEVable(MI->getLength()->getType())) return UnknownRange; - ConstantRange AccessRange = getAccessRange(U, AllocaPtr, Len->getZExtValue()); - return AccessRange; + + const SCEV *Expr = + SE.getTruncateOrZeroExtend(SE.getSCEV(MI->getLength()), CalculationTy); + ConstantRange Sizes = SE.getSignedRange(Expr); + if (Sizes.getUpper().isNegative() || isUnsafe(Sizes)) + return UnknownRange; + Sizes = Sizes.sextOrTrunc(PointerSize); + ConstantRange SizeRange(APInt::getNullValue(PointerSize), + Sizes.getUpper() - 1); + return getAccessRange(U, Base, SizeRange); } /// The function analyzes all local uses of Ptr (alloca or argument) and /// calculates local access range and all function calls where it was used. -bool StackSafetyLocalAnalysis::analyzeAllUses(const Value *Ptr, UseInfo &US) { +bool StackSafetyLocalAnalysis::analyzeAllUses(Value *Ptr, + UseInfo<GlobalValue> &US, + const StackLifetime &SL) { SmallPtrSet<const Value *, 16> Visited; SmallVector<const Value *, 8> WorkList; WorkList.push_back(Ptr); + const AllocaInst *AI = dyn_cast<AllocaInst>(Ptr); // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc. while (!WorkList.empty()) { const Value *V = WorkList.pop_back_val(); for (const Use &UI : V->uses()) { - auto I = cast<const Instruction>(UI.getUser()); + const auto *I = cast<Instruction>(UI.getUser()); + if (!SL.isReachable(I)) + continue; + assert(V == UI.get()); switch (I->getOpcode()) { case Instruction::Load: { + if (AI && !SL.isAliveAfter(AI, I)) { + US.updateRange(UnknownRange); + return false; + } US.updateRange( getAccessRange(UI, Ptr, DL.getTypeStoreSize(I->getType()))); break; @@ -308,6 +329,10 @@ bool StackSafetyLocalAnalysis::analyzeAllUses(const Value *Ptr, UseInfo &US) { US.updateRange(UnknownRange); return false; } + if (AI && !SL.isAliveAfter(AI, I)) { + US.updateRange(UnknownRange); + return false; + } US.updateRange(getAccessRange( UI, Ptr, DL.getTypeStoreSize(I->getOperand(0)->getType()))); break; @@ -322,36 +347,44 @@ bool StackSafetyLocalAnalysis::analyzeAllUses(const Value *Ptr, UseInfo &US) { case Instruction::Call: case Instruction::Invoke: { - ImmutableCallSite CS(I); - if (I->isLifetimeStartOrEnd()) break; + if (AI && !SL.isAliveAfter(AI, I)) { + US.updateRange(UnknownRange); + return false; + } + if (const MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) { US.updateRange(getMemIntrinsicAccessRange(MI, UI, Ptr)); break; } + const auto &CB = cast<CallBase>(*I); + if (!CB.isArgOperand(&UI)) { + US.updateRange(UnknownRange); + return false; + } + + unsigned ArgNo = CB.getArgOperandNo(&UI); + if (CB.isByValArgument(ArgNo)) { + US.updateRange(getAccessRange( + UI, Ptr, DL.getTypeStoreSize(CB.getParamByValType(ArgNo)))); + break; + } + // FIXME: consult devirt? // Do not follow aliases, otherwise we could inadvertently follow // dso_preemptable aliases or aliases with interposable linkage. const GlobalValue *Callee = - dyn_cast<GlobalValue>(CS.getCalledValue()->stripPointerCasts()); + dyn_cast<GlobalValue>(CB.getCalledOperand()->stripPointerCasts()); if (!Callee) { US.updateRange(UnknownRange); return false; } assert(isa<Function>(Callee) || isa<GlobalAlias>(Callee)); - - ImmutableCallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); - for (ImmutableCallSite::arg_iterator A = B; A != E; ++A) { - if (A->get() == V) { - ConstantRange Offset = offsetFromAlloca(UI, Ptr); - US.Calls.emplace_back(Callee, A - B, Offset); - } - } - + US.Calls.emplace_back(Callee, ArgNo, offsetFrom(UI, Ptr)); break; } @@ -365,51 +398,52 @@ bool StackSafetyLocalAnalysis::analyzeAllUses(const Value *Ptr, UseInfo &US) { return true; } -StackSafetyInfo StackSafetyLocalAnalysis::run() { - StackSafetyInfo::FunctionInfo Info(&F); +FunctionInfo<GlobalValue> StackSafetyLocalAnalysis::run() { + FunctionInfo<GlobalValue> Info; assert(!F.isDeclaration() && "Can't run StackSafety on a function declaration"); LLVM_DEBUG(dbgs() << "[StackSafety] " << F.getName() << "\n"); - for (auto &I : instructions(F)) { - if (auto AI = dyn_cast<AllocaInst>(&I)) { - Info.Allocas.emplace_back(PointerSize, AI, - getStaticAllocaAllocationSize(AI)); - AllocaInfo &AS = Info.Allocas.back(); - analyzeAllUses(AI, AS.Use); - } + SmallVector<AllocaInst *, 64> Allocas; + for (auto &I : instructions(F)) + if (auto *AI = dyn_cast<AllocaInst>(&I)) + Allocas.push_back(AI); + StackLifetime SL(F, Allocas, StackLifetime::LivenessType::Must); + SL.run(); + + for (auto *AI : Allocas) { + auto &UI = Info.Allocas.emplace(AI, PointerSize).first->second; + analyzeAllUses(AI, UI, SL); } - for (const Argument &A : make_range(F.arg_begin(), F.arg_end())) { - Info.Params.emplace_back(PointerSize, &A); - ParamInfo &PS = Info.Params.back(); - analyzeAllUses(&A, PS.Use); + for (Argument &A : make_range(F.arg_begin(), F.arg_end())) { + // Non pointers and bypass arguments are not going to be used in any global + // processing. + if (A.getType()->isPointerTy() && !A.hasByValAttr()) { + auto &UI = Info.Params.emplace(A.getArgNo(), PointerSize).first->second; + analyzeAllUses(&A, UI, SL); + } } + LLVM_DEBUG(Info.print(dbgs(), F.getName(), &F)); LLVM_DEBUG(dbgs() << "[StackSafety] done\n"); - LLVM_DEBUG(Info.print(dbgs())); - return StackSafetyInfo(std::move(Info)); + return Info; } -class StackSafetyDataFlowAnalysis { - using FunctionMap = - std::map<const GlobalValue *, StackSafetyInfo::FunctionInfo>; +template <typename CalleeTy> class StackSafetyDataFlowAnalysis { + using FunctionMap = std::map<const CalleeTy *, FunctionInfo<CalleeTy>>; FunctionMap Functions; - // Callee-to-Caller multimap. - DenseMap<const GlobalValue *, SmallVector<const GlobalValue *, 4>> Callers; - SetVector<const GlobalValue *> WorkList; - - unsigned PointerSize = 0; const ConstantRange UnknownRange; - ConstantRange getArgumentAccessRange(const GlobalValue *Callee, - unsigned ParamNo) const; - bool updateOneUse(UseInfo &US, bool UpdateToFullSet); - void updateOneNode(const GlobalValue *Callee, - StackSafetyInfo::FunctionInfo &FS); - void updateOneNode(const GlobalValue *Callee) { + // Callee-to-Caller multimap. + DenseMap<const CalleeTy *, SmallVector<const CalleeTy *, 4>> Callers; + SetVector<const CalleeTy *> WorkList; + + bool updateOneUse(UseInfo<CalleeTy> &US, bool UpdateToFullSet); + void updateOneNode(const CalleeTy *Callee, FunctionInfo<CalleeTy> &FS); + void updateOneNode(const CalleeTy *Callee) { updateOneNode(Callee, Functions.find(Callee)->second); } void updateAllNodes() { @@ -422,51 +456,46 @@ class StackSafetyDataFlowAnalysis { #endif public: - StackSafetyDataFlowAnalysis( - Module &M, std::function<const StackSafetyInfo &(Function &)> FI); - StackSafetyGlobalInfo run(); -}; + StackSafetyDataFlowAnalysis(uint32_t PointerBitWidth, FunctionMap Functions) + : Functions(std::move(Functions)), + UnknownRange(ConstantRange::getFull(PointerBitWidth)) {} -StackSafetyDataFlowAnalysis::StackSafetyDataFlowAnalysis( - Module &M, std::function<const StackSafetyInfo &(Function &)> FI) - : PointerSize(M.getDataLayout().getPointerSizeInBits()), - UnknownRange(PointerSize, true) { - // Without ThinLTO, run the local analysis for every function in the TU and - // then run the DFA. - for (auto &F : M.functions()) - if (!F.isDeclaration()) - Functions.emplace(&F, FI(F)); - for (auto &A : M.aliases()) - if (isa<Function>(A.getBaseObject())) - Functions.emplace(&A, StackSafetyInfo::FunctionInfo(&A)); -} + const FunctionMap &run(); -ConstantRange -StackSafetyDataFlowAnalysis::getArgumentAccessRange(const GlobalValue *Callee, - unsigned ParamNo) const { - auto IT = Functions.find(Callee); + ConstantRange getArgumentAccessRange(const CalleeTy *Callee, unsigned ParamNo, + const ConstantRange &Offsets) const; +}; + +template <typename CalleeTy> +ConstantRange StackSafetyDataFlowAnalysis<CalleeTy>::getArgumentAccessRange( + const CalleeTy *Callee, unsigned ParamNo, + const ConstantRange &Offsets) const { + auto FnIt = Functions.find(Callee); // Unknown callee (outside of LTO domain or an indirect call). - if (IT == Functions.end()) + if (FnIt == Functions.end()) return UnknownRange; - const StackSafetyInfo::FunctionInfo &FS = IT->second; - // The definition of this symbol may not be the definition in this linkage - // unit. - if (!FS.IsDSOLocal() || FS.IsInterposable()) + auto &FS = FnIt->second; + auto ParamIt = FS.Params.find(ParamNo); + if (ParamIt == FS.Params.end()) return UnknownRange; - if (ParamNo >= FS.Params.size()) // possibly vararg + auto &Access = ParamIt->second.Range; + if (Access.isEmptySet()) + return Access; + if (Access.isFullSet()) return UnknownRange; - return FS.Params[ParamNo].Use.Range; + return addOverflowNever(Access, Offsets); } -bool StackSafetyDataFlowAnalysis::updateOneUse(UseInfo &US, - bool UpdateToFullSet) { +template <typename CalleeTy> +bool StackSafetyDataFlowAnalysis<CalleeTy>::updateOneUse(UseInfo<CalleeTy> &US, + bool UpdateToFullSet) { bool Changed = false; for (auto &CS : US.Calls) { assert(!CS.Offset.isEmptySet() && "Param range can't be empty-set, invalid offset range"); - ConstantRange CalleeRange = getArgumentAccessRange(CS.Callee, CS.ParamNo); - CalleeRange = CalleeRange.add(CS.Offset); + ConstantRange CalleeRange = + getArgumentAccessRange(CS.Callee, CS.ParamNo, CS.Offset); if (!US.Range.contains(CalleeRange)) { Changed = true; if (UpdateToFullSet) @@ -478,19 +507,18 @@ bool StackSafetyDataFlowAnalysis::updateOneUse(UseInfo &US, return Changed; } -void StackSafetyDataFlowAnalysis::updateOneNode( - const GlobalValue *Callee, StackSafetyInfo::FunctionInfo &FS) { +template <typename CalleeTy> +void StackSafetyDataFlowAnalysis<CalleeTy>::updateOneNode( + const CalleeTy *Callee, FunctionInfo<CalleeTy> &FS) { bool UpdateToFullSet = FS.UpdateCount > StackSafetyMaxIterations; bool Changed = false; - for (auto &AS : FS.Allocas) - Changed |= updateOneUse(AS.Use, UpdateToFullSet); - for (auto &PS : FS.Params) - Changed |= updateOneUse(PS.Use, UpdateToFullSet); + for (auto &KV : FS.Params) + Changed |= updateOneUse(KV.second, UpdateToFullSet); if (Changed) { LLVM_DEBUG(dbgs() << "=== update [" << FS.UpdateCount - << (UpdateToFullSet ? ", full-set" : "") << "] " - << FS.getName() << "\n"); + << (UpdateToFullSet ? ", full-set" : "") << "] " << &FS + << "\n"); // Callers of this function may need updating. for (auto &CallerID : Callers[Callee]) WorkList.insert(CallerID); @@ -499,19 +527,14 @@ void StackSafetyDataFlowAnalysis::updateOneNode( } } -void StackSafetyDataFlowAnalysis::runDataFlow() { - Callers.clear(); - WorkList.clear(); - - SmallVector<const GlobalValue *, 16> Callees; +template <typename CalleeTy> +void StackSafetyDataFlowAnalysis<CalleeTy>::runDataFlow() { + SmallVector<const CalleeTy *, 16> Callees; for (auto &F : Functions) { Callees.clear(); - StackSafetyInfo::FunctionInfo &FS = F.second; - for (auto &AS : FS.Allocas) - for (auto &CS : AS.Use.Calls) - Callees.push_back(CS.Callee); - for (auto &PS : FS.Params) - for (auto &CS : PS.Use.Calls) + auto &FS = F.second; + for (auto &KV : FS.Params) + for (auto &CS : KV.second.Calls) Callees.push_back(CS.Callee); llvm::sort(Callees); @@ -524,65 +547,284 @@ void StackSafetyDataFlowAnalysis::runDataFlow() { updateAllNodes(); while (!WorkList.empty()) { - const GlobalValue *Callee = WorkList.back(); + const CalleeTy *Callee = WorkList.back(); WorkList.pop_back(); updateOneNode(Callee); } } #ifndef NDEBUG -void StackSafetyDataFlowAnalysis::verifyFixedPoint() { +template <typename CalleeTy> +void StackSafetyDataFlowAnalysis<CalleeTy>::verifyFixedPoint() { WorkList.clear(); updateAllNodes(); assert(WorkList.empty()); } #endif -StackSafetyGlobalInfo StackSafetyDataFlowAnalysis::run() { +template <typename CalleeTy> +const typename StackSafetyDataFlowAnalysis<CalleeTy>::FunctionMap & +StackSafetyDataFlowAnalysis<CalleeTy>::run() { runDataFlow(); LLVM_DEBUG(verifyFixedPoint()); + return Functions; +} - StackSafetyGlobalInfo SSI; - for (auto &F : Functions) - SSI.emplace(F.first, std::move(F.second)); - return SSI; +FunctionSummary *resolveCallee(GlobalValueSummary *S) { + while (S) { + if (!S->isLive() || !S->isDSOLocal()) + return nullptr; + if (FunctionSummary *FS = dyn_cast<FunctionSummary>(S)) + return FS; + AliasSummary *AS = dyn_cast<AliasSummary>(S); + if (!AS) + return nullptr; + S = AS->getBaseObject(); + if (S == AS) + return nullptr; + } + return nullptr; } -void print(const StackSafetyGlobalInfo &SSI, raw_ostream &O, const Module &M) { - size_t Count = 0; - for (auto &F : M.functions()) - if (!F.isDeclaration()) { - SSI.find(&F)->second.print(O); - O << "\n"; - ++Count; +const Function *findCalleeInModule(const GlobalValue *GV) { + while (GV) { + if (GV->isDeclaration() || GV->isInterposable() || !GV->isDSOLocal()) + return nullptr; + if (const Function *F = dyn_cast<Function>(GV)) + return F; + const GlobalAlias *A = dyn_cast<GlobalAlias>(GV); + if (!A) + return nullptr; + GV = A->getBaseObject(); + if (GV == A) + return nullptr; + } + return nullptr; +} + +GlobalValueSummary *getGlobalValueSummary(const ModuleSummaryIndex *Index, + uint64_t ValueGUID) { + auto VI = Index->getValueInfo(ValueGUID); + if (!VI || VI.getSummaryList().empty()) + return nullptr; + assert(VI.getSummaryList().size() == 1); + auto &Summary = VI.getSummaryList()[0]; + return Summary.get(); +} + +const ConstantRange *findParamAccess(const FunctionSummary &FS, + uint32_t ParamNo) { + assert(FS.isLive()); + assert(FS.isDSOLocal()); + for (auto &PS : FS.paramAccesses()) + if (ParamNo == PS.ParamNo) + return &PS.Use; + return nullptr; +} + +void resolveAllCalls(UseInfo<GlobalValue> &Use, + const ModuleSummaryIndex *Index) { + ConstantRange FullSet(Use.Range.getBitWidth(), true); + for (auto &C : Use.Calls) { + const Function *F = findCalleeInModule(C.Callee); + if (F) { + C.Callee = F; + continue; } - for (auto &A : M.aliases()) { - SSI.find(&A)->second.print(O); - O << "\n"; - ++Count; + + if (!Index) + return Use.updateRange(FullSet); + GlobalValueSummary *GVS = getGlobalValueSummary(Index, C.Callee->getGUID()); + + FunctionSummary *FS = resolveCallee(GVS); + if (!FS) + return Use.updateRange(FullSet); + const ConstantRange *Found = findParamAccess(*FS, C.ParamNo); + if (!Found) + return Use.updateRange(FullSet); + ConstantRange Access = Found->sextOrTrunc(Use.Range.getBitWidth()); + Use.updateRange(addOverflowNever(Access, C.Offset)); + C.Callee = nullptr; } - assert(Count == SSI.size() && "Unexpected functions in the result"); + + Use.Calls.erase(std::remove_if(Use.Calls.begin(), Use.Calls.end(), + [](auto &T) { return !T.Callee; }), + Use.Calls.end()); +} + +GVToSSI createGlobalStackSafetyInfo( + std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions, + const ModuleSummaryIndex *Index) { + GVToSSI SSI; + if (Functions.empty()) + return SSI; + + // FIXME: Simplify printing and remove copying here. + auto Copy = Functions; + + for (auto &FnKV : Copy) + for (auto &KV : FnKV.second.Params) + resolveAllCalls(KV.second, Index); + + uint32_t PointerSize = Copy.begin() + ->first->getParent() + ->getDataLayout() + .getMaxPointerSizeInBits(); + StackSafetyDataFlowAnalysis<GlobalValue> SSDFA(PointerSize, std::move(Copy)); + + for (auto &F : SSDFA.run()) { + auto FI = F.second; + auto &SrcF = Functions[F.first]; + for (auto &KV : FI.Allocas) { + auto &A = KV.second; + resolveAllCalls(A, Index); + for (auto &C : A.Calls) { + A.updateRange( + SSDFA.getArgumentAccessRange(C.Callee, C.ParamNo, C.Offset)); + } + // FIXME: This is needed only to preserve calls in print() results. + A.Calls = SrcF.Allocas.find(KV.first)->second.Calls; + } + for (auto &KV : FI.Params) { + auto &P = KV.second; + P.Calls = SrcF.Params.find(KV.first)->second.Calls; + } + SSI[F.first] = std::move(FI); + } + + return SSI; } } // end anonymous namespace StackSafetyInfo::StackSafetyInfo() = default; + +StackSafetyInfo::StackSafetyInfo(Function *F, + std::function<ScalarEvolution &()> GetSE) + : F(F), GetSE(GetSE) {} + StackSafetyInfo::StackSafetyInfo(StackSafetyInfo &&) = default; -StackSafetyInfo &StackSafetyInfo::operator=(StackSafetyInfo &&) = default; -StackSafetyInfo::StackSafetyInfo(FunctionInfo &&Info) - : Info(new FunctionInfo(std::move(Info))) {} +StackSafetyInfo &StackSafetyInfo::operator=(StackSafetyInfo &&) = default; StackSafetyInfo::~StackSafetyInfo() = default; -void StackSafetyInfo::print(raw_ostream &O) const { Info->print(O); } +const StackSafetyInfo::InfoTy &StackSafetyInfo::getInfo() const { + if (!Info) { + StackSafetyLocalAnalysis SSLA(*F, GetSE()); + Info.reset(new InfoTy{SSLA.run()}); + } + return *Info; +} + +void StackSafetyInfo::print(raw_ostream &O) const { + getInfo().Info.print(O, F->getName(), dyn_cast<Function>(F)); +} + +const StackSafetyGlobalInfo::InfoTy &StackSafetyGlobalInfo::getInfo() const { + if (!Info) { + std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions; + for (auto &F : M->functions()) { + if (!F.isDeclaration()) { + auto FI = GetSSI(F).getInfo().Info; + Functions.emplace(&F, std::move(FI)); + } + } + Info.reset(new InfoTy{ + createGlobalStackSafetyInfo(std::move(Functions), Index), {}}); + for (auto &FnKV : Info->Info) { + for (auto &KV : FnKV.second.Allocas) { + ++NumAllocaTotal; + const AllocaInst *AI = KV.first; + if (getStaticAllocaSizeRange(*AI).contains(KV.second.Range)) { + Info->SafeAllocas.insert(AI); + ++NumAllocaStackSafe; + } + } + } + if (StackSafetyPrint) + print(errs()); + } + return *Info; +} + +std::vector<FunctionSummary::ParamAccess> +StackSafetyInfo::getParamAccesses() const { + // Implementation transforms internal representation of parameter information + // into FunctionSummary format. + std::vector<FunctionSummary::ParamAccess> ParamAccesses; + for (const auto &KV : getInfo().Info.Params) { + auto &PS = KV.second; + // Parameter accessed by any or unknown offset, represented as FullSet by + // StackSafety, is handled as the parameter for which we have no + // StackSafety info at all. So drop it to reduce summary size. + if (PS.Range.isFullSet()) + continue; + + ParamAccesses.emplace_back(KV.first, PS.Range); + FunctionSummary::ParamAccess &Param = ParamAccesses.back(); + + Param.Calls.reserve(PS.Calls.size()); + for (auto &C : PS.Calls) { + // Parameter forwarded into another function by any or unknown offset + // will make ParamAccess::Range as FullSet anyway. So we can drop the + // entire parameter like we did above. + // TODO(vitalybuka): Return already filtered parameters from getInfo(). + if (C.Offset.isFullSet()) { + ParamAccesses.pop_back(); + break; + } + Param.Calls.emplace_back(C.ParamNo, C.Callee->getGUID(), C.Offset); + } + } + return ParamAccesses; +} + +StackSafetyGlobalInfo::StackSafetyGlobalInfo() = default; + +StackSafetyGlobalInfo::StackSafetyGlobalInfo( + Module *M, std::function<const StackSafetyInfo &(Function &F)> GetSSI, + const ModuleSummaryIndex *Index) + : M(M), GetSSI(GetSSI), Index(Index) { + if (StackSafetyRun) + getInfo(); +} + +StackSafetyGlobalInfo::StackSafetyGlobalInfo(StackSafetyGlobalInfo &&) = + default; + +StackSafetyGlobalInfo & +StackSafetyGlobalInfo::operator=(StackSafetyGlobalInfo &&) = default; + +StackSafetyGlobalInfo::~StackSafetyGlobalInfo() = default; + +bool StackSafetyGlobalInfo::isSafe(const AllocaInst &AI) const { + const auto &Info = getInfo(); + return Info.SafeAllocas.count(&AI); +} + +void StackSafetyGlobalInfo::print(raw_ostream &O) const { + auto &SSI = getInfo().Info; + if (SSI.empty()) + return; + const Module &M = *SSI.begin()->first->getParent(); + for (auto &F : M.functions()) { + if (!F.isDeclaration()) { + SSI.find(&F)->second.print(O, F.getName(), &F); + O << "\n"; + } + } +} + +LLVM_DUMP_METHOD void StackSafetyGlobalInfo::dump() const { print(dbgs()); } AnalysisKey StackSafetyAnalysis::Key; StackSafetyInfo StackSafetyAnalysis::run(Function &F, FunctionAnalysisManager &AM) { - StackSafetyLocalAnalysis SSLA(F, AM.getResult<ScalarEvolutionAnalysis>(F)); - return SSLA.run(); + return StackSafetyInfo(&F, [&AM, &F]() -> ScalarEvolution & { + return AM.getResult<ScalarEvolutionAnalysis>(F); + }); } PreservedAnalyses StackSafetyPrinterPass::run(Function &F, @@ -599,7 +841,7 @@ StackSafetyInfoWrapperPass::StackSafetyInfoWrapperPass() : FunctionPass(ID) { } void StackSafetyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired<ScalarEvolutionWrapperPass>(); + AU.addRequiredTransitive<ScalarEvolutionWrapperPass>(); AU.setPreservesAll(); } @@ -608,9 +850,8 @@ void StackSafetyInfoWrapperPass::print(raw_ostream &O, const Module *M) const { } bool StackSafetyInfoWrapperPass::runOnFunction(Function &F) { - StackSafetyLocalAnalysis SSLA( - F, getAnalysis<ScalarEvolutionWrapperPass>().getSE()); - SSI = StackSafetyInfo(SSLA.run()); + auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); + SSI = {&F, [SE]() -> ScalarEvolution & { return *SE; }}; return false; } @@ -618,20 +859,20 @@ AnalysisKey StackSafetyGlobalAnalysis::Key; StackSafetyGlobalInfo StackSafetyGlobalAnalysis::run(Module &M, ModuleAnalysisManager &AM) { + // FIXME: Lookup Module Summary. FunctionAnalysisManager &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); - - StackSafetyDataFlowAnalysis SSDFA( - M, [&FAM](Function &F) -> const StackSafetyInfo & { - return FAM.getResult<StackSafetyAnalysis>(F); - }); - return SSDFA.run(); + return {&M, + [&FAM](Function &F) -> const StackSafetyInfo & { + return FAM.getResult<StackSafetyAnalysis>(F); + }, + nullptr}; } PreservedAnalyses StackSafetyGlobalPrinterPass::run(Module &M, ModuleAnalysisManager &AM) { OS << "'Stack Safety Analysis' for module '" << M.getName() << "'\n"; - print(AM.getResult<StackSafetyGlobalAnalysis>(M), OS, M); + AM.getResult<StackSafetyGlobalAnalysis>(M).print(OS); return PreservedAnalyses::all(); } @@ -643,25 +884,96 @@ StackSafetyGlobalInfoWrapperPass::StackSafetyGlobalInfoWrapperPass() *PassRegistry::getPassRegistry()); } +StackSafetyGlobalInfoWrapperPass::~StackSafetyGlobalInfoWrapperPass() = default; + void StackSafetyGlobalInfoWrapperPass::print(raw_ostream &O, const Module *M) const { - ::print(SSI, O, *M); + SSGI.print(O); } void StackSafetyGlobalInfoWrapperPass::getAnalysisUsage( AnalysisUsage &AU) const { + AU.setPreservesAll(); AU.addRequired<StackSafetyInfoWrapperPass>(); } bool StackSafetyGlobalInfoWrapperPass::runOnModule(Module &M) { - StackSafetyDataFlowAnalysis SSDFA( - M, [this](Function &F) -> const StackSafetyInfo & { - return getAnalysis<StackSafetyInfoWrapperPass>(F).getResult(); - }); - SSI = SSDFA.run(); + const ModuleSummaryIndex *ImportSummary = nullptr; + if (auto *IndexWrapperPass = + getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>()) + ImportSummary = IndexWrapperPass->getIndex(); + + SSGI = {&M, + [this](Function &F) -> const StackSafetyInfo & { + return getAnalysis<StackSafetyInfoWrapperPass>(F).getResult(); + }, + ImportSummary}; return false; } +bool llvm::needsParamAccessSummary(const Module &M) { + if (StackSafetyRun) + return true; + for (auto &F : M.functions()) + if (F.hasFnAttribute(Attribute::SanitizeMemTag)) + return true; + return false; +} + +void llvm::generateParamAccessSummary(ModuleSummaryIndex &Index) { + const ConstantRange FullSet(FunctionSummary::ParamAccess::RangeWidth, true); + std::map<const FunctionSummary *, FunctionInfo<FunctionSummary>> Functions; + + // Convert the ModuleSummaryIndex to a FunctionMap + for (auto &GVS : Index) { + for (auto &GV : GVS.second.SummaryList) { + FunctionSummary *FS = dyn_cast<FunctionSummary>(GV.get()); + if (!FS) + continue; + if (FS->isLive() && FS->isDSOLocal()) { + FunctionInfo<FunctionSummary> FI; + for (auto &PS : FS->paramAccesses()) { + auto &US = + FI.Params + .emplace(PS.ParamNo, FunctionSummary::ParamAccess::RangeWidth) + .first->second; + US.Range = PS.Use; + for (auto &Call : PS.Calls) { + assert(!Call.Offsets.isFullSet()); + FunctionSummary *S = resolveCallee( + Index.findSummaryInModule(Call.Callee, FS->modulePath())); + if (!S) { + US.Range = FullSet; + US.Calls.clear(); + break; + } + US.Calls.emplace_back(S, Call.ParamNo, Call.Offsets); + } + } + Functions.emplace(FS, std::move(FI)); + } + // Reset data for all summaries. Alive and DSO local will be set back from + // of data flow results below. Anything else will not be accessed + // by ThinLTO backend, so we can save on bitcode size. + FS->setParamAccesses({}); + } + } + StackSafetyDataFlowAnalysis<FunctionSummary> SSDFA( + FunctionSummary::ParamAccess::RangeWidth, std::move(Functions)); + for (auto &KV : SSDFA.run()) { + std::vector<FunctionSummary::ParamAccess> NewParams; + NewParams.reserve(KV.second.Params.size()); + for (auto &Param : KV.second.Params) { + NewParams.emplace_back(); + FunctionSummary::ParamAccess &New = NewParams.back(); + New.ParamNo = Param.first; + New.Use = Param.second.Range; // Only range is needed. + } + const_cast<FunctionSummary *>(KV.first)->setParamAccesses( + std::move(NewParams)); + } +} + static const char LocalPassArg[] = "stack-safety-local"; static const char LocalPassName[] = "Stack Safety Local Analysis"; INITIALIZE_PASS_BEGIN(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName, @@ -672,7 +984,8 @@ INITIALIZE_PASS_END(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName, static const char GlobalPassName[] = "Stack Safety Analysis"; INITIALIZE_PASS_BEGIN(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE, - GlobalPassName, false, false) + GlobalPassName, false, true) INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ImmutableModuleSummaryIndexWrapperPass) INITIALIZE_PASS_END(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE, - GlobalPassName, false, false) + GlobalPassName, false, true) |