1221 lines · cpp
1//===- StackSafetyAnalysis.cpp - Stack memory safety analysis -------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9//===----------------------------------------------------------------------===//10 11#include "llvm/Analysis/StackSafetyAnalysis.h"12#include "llvm/ADT/APInt.h"13#include "llvm/ADT/SmallPtrSet.h"14#include "llvm/ADT/SmallVector.h"15#include "llvm/ADT/Statistic.h"16#include "llvm/Analysis/ModuleSummaryAnalysis.h"17#include "llvm/Analysis/ScalarEvolution.h"18#include "llvm/Analysis/StackLifetime.h"19#include "llvm/IR/ConstantRange.h"20#include "llvm/IR/DerivedTypes.h"21#include "llvm/IR/GlobalValue.h"22#include "llvm/IR/InstIterator.h"23#include "llvm/IR/Instruction.h"24#include "llvm/IR/Instructions.h"25#include "llvm/IR/IntrinsicInst.h"26#include "llvm/IR/ModuleSummaryIndex.h"27#include "llvm/InitializePasses.h"28#include "llvm/Support/Casting.h"29#include "llvm/Support/CommandLine.h"30#include "llvm/Support/FormatVariadic.h"31#include "llvm/Support/raw_ostream.h"32#include <algorithm>33#include <tuple>34 35using namespace llvm;36 37#define DEBUG_TYPE "stack-safety"38 39STATISTIC(NumAllocaStackSafe, "Number of safe allocas");40STATISTIC(NumAllocaTotal, "Number of total allocas");41 42STATISTIC(NumCombinedCalleeLookupTotal,43 "Number of total callee lookups on combined index.");44STATISTIC(NumCombinedCalleeLookupFailed,45 "Number of failed callee lookups on combined index.");46STATISTIC(NumModuleCalleeLookupTotal,47 "Number of total callee lookups on module index.");48STATISTIC(NumModuleCalleeLookupFailed,49 "Number of failed callee lookups on module index.");50STATISTIC(NumCombinedParamAccessesBefore,51 "Number of total param accesses before generateParamAccessSummary.");52STATISTIC(NumCombinedParamAccessesAfter,53 "Number of total param accesses after generateParamAccessSummary.");54STATISTIC(NumCombinedDataFlowNodes,55 "Number of total nodes in combined index for dataflow processing.");56STATISTIC(NumIndexCalleeUnhandled, "Number of index callee which are unhandled.");57STATISTIC(NumIndexCalleeMultipleWeak, "Number of index callee non-unique weak.");58STATISTIC(NumIndexCalleeMultipleExternal, "Number of index callee non-unique external.");59 60 61static cl::opt<int> StackSafetyMaxIterations("stack-safety-max-iterations",62 cl::init(20), cl::Hidden);63 64static cl::opt<bool> StackSafetyPrint("stack-safety-print", cl::init(false),65 cl::Hidden);66 67static cl::opt<bool> StackSafetyRun("stack-safety-run", cl::init(false),68 cl::Hidden);69 70namespace {71 72// Check if we should bailout for such ranges.73bool isUnsafe(const ConstantRange &R) {74 return R.isEmptySet() || R.isFullSet() || R.isUpperSignWrapped();75}76 77ConstantRange addOverflowNever(const ConstantRange &L, const ConstantRange &R) {78 assert(!L.isSignWrappedSet());79 assert(!R.isSignWrappedSet());80 if (L.signedAddMayOverflow(R) !=81 ConstantRange::OverflowResult::NeverOverflows)82 return ConstantRange::getFull(L.getBitWidth());83 ConstantRange Result = L.add(R);84 assert(!Result.isSignWrappedSet());85 return Result;86}87 88ConstantRange unionNoWrap(const ConstantRange &L, const ConstantRange &R) {89 assert(!L.isSignWrappedSet());90 assert(!R.isSignWrappedSet());91 auto Result = L.unionWith(R);92 // Two non-wrapped sets can produce wrapped.93 if (Result.isSignWrappedSet())94 Result = ConstantRange::getFull(Result.getBitWidth());95 return Result;96}97 98/// Describes use of address in as a function call argument.99template <typename CalleeTy> struct CallInfo {100 /// Function being called.101 const CalleeTy *Callee = nullptr;102 /// Index of argument which pass address.103 size_t ParamNo = 0;104 105 CallInfo(const CalleeTy *Callee, size_t ParamNo)106 : Callee(Callee), ParamNo(ParamNo) {}107 108 struct Less {109 bool operator()(const CallInfo &L, const CallInfo &R) const {110 return std::tie(L.ParamNo, L.Callee) < std::tie(R.ParamNo, R.Callee);111 }112 };113};114 115/// Describe uses of address (alloca or parameter) inside of the function.116template <typename CalleeTy> struct UseInfo {117 // Access range if the address (alloca or parameters).118 // It is allowed to be empty-set when there are no known accesses.119 ConstantRange Range;120 std::set<const Instruction *> UnsafeAccesses;121 122 // List of calls which pass address as an argument.123 // Value is offset range of address from base address (alloca or calling124 // function argument). Range should never set to empty-set, that is an invalid125 // access range that can cause empty-set to be propagated with126 // ConstantRange::add127 using CallsTy = std::map<CallInfo<CalleeTy>, ConstantRange,128 typename CallInfo<CalleeTy>::Less>;129 CallsTy Calls;130 131 UseInfo(unsigned PointerSize) : Range{PointerSize, false} {}132 133 void updateRange(const ConstantRange &R) { Range = unionNoWrap(Range, R); }134 void addRange(const Instruction *I, const ConstantRange &R, bool IsSafe) {135 if (!IsSafe)136 UnsafeAccesses.insert(I);137 updateRange(R);138 }139};140 141template <typename CalleeTy>142raw_ostream &operator<<(raw_ostream &OS, const UseInfo<CalleeTy> &U) {143 OS << U.Range;144 for (auto &Call : U.Calls)145 OS << ", "146 << "@" << Call.first.Callee->getName() << "(arg" << Call.first.ParamNo147 << ", " << Call.second << ")";148 return OS;149}150 151/// Calculate the allocation size of a given alloca. Returns empty range152// in case of confution.153ConstantRange getStaticAllocaSizeRange(const AllocaInst &AI) {154 const DataLayout &DL = AI.getDataLayout();155 TypeSize TS = DL.getTypeAllocSize(AI.getAllocatedType());156 unsigned PointerSize = DL.getPointerTypeSizeInBits(AI.getType());157 // Fallback to empty range for alloca size.158 ConstantRange R = ConstantRange::getEmpty(PointerSize);159 if (TS.isScalable())160 return R;161 APInt APSize(PointerSize, TS.getFixedValue(), true);162 if (APSize.isNonPositive())163 return R;164 if (AI.isArrayAllocation()) {165 const auto *C = dyn_cast<ConstantInt>(AI.getArraySize());166 if (!C)167 return R;168 bool Overflow = false;169 APInt Mul = C->getValue();170 if (Mul.isNonPositive())171 return R;172 Mul = Mul.sextOrTrunc(PointerSize);173 APSize = APSize.smul_ov(Mul, Overflow);174 if (Overflow)175 return R;176 }177 R = ConstantRange(APInt::getZero(PointerSize), APSize);178 assert(!isUnsafe(R));179 return R;180}181 182template <typename CalleeTy> struct FunctionInfo {183 std::map<const AllocaInst *, UseInfo<CalleeTy>> Allocas;184 std::map<uint32_t, UseInfo<CalleeTy>> Params;185 // TODO: describe return value as depending on one or more of its arguments.186 187 // StackSafetyDataFlowAnalysis counter stored here for faster access.188 int UpdateCount = 0;189 190 void print(raw_ostream &O, StringRef Name, const Function *F) const {191 // TODO: Consider different printout format after192 // StackSafetyDataFlowAnalysis. Calls and parameters are irrelevant then.193 O << " @" << Name << ((F && F->isDSOLocal()) ? "" : " dso_preemptable")194 << ((F && F->isInterposable()) ? " interposable" : "") << "\n";195 196 O << " args uses:\n";197 for (auto &KV : Params) {198 O << " ";199 if (F)200 O << F->getArg(KV.first)->getName();201 else202 O << formatv("arg{0}", KV.first);203 O << "[]: " << KV.second << "\n";204 }205 206 O << " allocas uses:\n";207 if (F) {208 for (const auto &I : instructions(F)) {209 if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) {210 auto &AS = Allocas.find(AI)->second;211 O << " " << AI->getName() << "["212 << getStaticAllocaSizeRange(*AI).getUpper() << "]: " << AS << "\n";213 }214 }215 } else {216 assert(Allocas.empty());217 }218 }219};220 221using GVToSSI = std::map<const GlobalValue *, FunctionInfo<GlobalValue>>;222 223} // namespace224 225struct StackSafetyInfo::InfoTy {226 FunctionInfo<GlobalValue> Info;227};228 229struct StackSafetyGlobalInfo::InfoTy {230 GVToSSI Info;231 SmallPtrSet<const AllocaInst *, 8> SafeAllocas;232 std::set<const Instruction *> UnsafeAccesses;233};234 235namespace {236 237class StackSafetyLocalAnalysis {238 Function &F;239 const DataLayout &DL;240 ScalarEvolution &SE;241 unsigned PointerSize = 0;242 243 const ConstantRange UnknownRange;244 245 /// FIXME: This function is a bandaid, it's only needed246 /// because this pass doesn't handle address spaces of different pointer247 /// sizes.248 ///249 /// \returns \p Val's SCEV as a pointer of AS zero, or nullptr if it can't be250 /// converted to AS 0.251 const SCEV *getSCEVAsPointer(Value *Val);252 253 ConstantRange offsetFrom(Value *Addr, Value *Base);254 ConstantRange getAccessRange(Value *Addr, Value *Base,255 const ConstantRange &SizeRange);256 ConstantRange getAccessRange(Value *Addr, Value *Base, TypeSize Size);257 ConstantRange getMemIntrinsicAccessRange(const MemIntrinsic *MI, const Use &U,258 Value *Base);259 260 void analyzeAllUses(Value *Ptr, UseInfo<GlobalValue> &AS,261 const StackLifetime &SL);262 263 264 bool isSafeAccess(const Use &U, AllocaInst *AI, const SCEV *AccessSize);265 bool isSafeAccess(const Use &U, AllocaInst *AI, Value *V);266 bool isSafeAccess(const Use &U, AllocaInst *AI, TypeSize AccessSize);267 268public:269 StackSafetyLocalAnalysis(Function &F, ScalarEvolution &SE)270 : F(F), DL(F.getDataLayout()), SE(SE),271 PointerSize(DL.getPointerSizeInBits()),272 UnknownRange(PointerSize, true) {}273 274 // Run the transformation on the associated function.275 FunctionInfo<GlobalValue> run();276};277 278const SCEV *StackSafetyLocalAnalysis::getSCEVAsPointer(Value *Val) {279 Type *ValTy = Val->getType();280 281 // We don't handle targets with multiple address spaces.282 if (!ValTy->isPointerTy()) {283 auto *PtrTy = PointerType::getUnqual(SE.getContext());284 return SE.getTruncateOrZeroExtend(SE.getSCEV(Val), PtrTy);285 }286 287 if (ValTy->getPointerAddressSpace() != 0)288 return nullptr;289 return SE.getSCEV(Val);290}291 292ConstantRange StackSafetyLocalAnalysis::offsetFrom(Value *Addr, Value *Base) {293 if (!SE.isSCEVable(Addr->getType()) || !SE.isSCEVable(Base->getType()))294 return UnknownRange;295 296 const SCEV *AddrExp = getSCEVAsPointer(Addr);297 const SCEV *BaseExp = getSCEVAsPointer(Base);298 if (!AddrExp || !BaseExp)299 return UnknownRange;300 301 const SCEV *Diff = SE.getMinusSCEV(AddrExp, BaseExp);302 if (isa<SCEVCouldNotCompute>(Diff))303 return UnknownRange;304 305 ConstantRange Offset = SE.getSignedRange(Diff);306 if (isUnsafe(Offset))307 return UnknownRange;308 return Offset.sextOrTrunc(PointerSize);309}310 311ConstantRange312StackSafetyLocalAnalysis::getAccessRange(Value *Addr, Value *Base,313 const ConstantRange &SizeRange) {314 // Zero-size loads and stores do not access memory.315 if (SizeRange.isEmptySet())316 return ConstantRange::getEmpty(PointerSize);317 assert(!isUnsafe(SizeRange));318 319 ConstantRange Offsets = offsetFrom(Addr, Base);320 if (isUnsafe(Offsets))321 return UnknownRange;322 323 Offsets = addOverflowNever(Offsets, SizeRange);324 if (isUnsafe(Offsets))325 return UnknownRange;326 return Offsets;327}328 329ConstantRange StackSafetyLocalAnalysis::getAccessRange(Value *Addr, Value *Base,330 TypeSize Size) {331 if (Size.isScalable())332 return UnknownRange;333 APInt APSize(PointerSize, Size.getFixedValue(), true);334 if (APSize.isNegative())335 return UnknownRange;336 return getAccessRange(Addr, Base,337 ConstantRange(APInt::getZero(PointerSize), APSize));338}339 340ConstantRange StackSafetyLocalAnalysis::getMemIntrinsicAccessRange(341 const MemIntrinsic *MI, const Use &U, Value *Base) {342 if (const auto *MTI = dyn_cast<MemTransferInst>(MI)) {343 if (MTI->getRawSource() != U && MTI->getRawDest() != U)344 return ConstantRange::getEmpty(PointerSize);345 } else {346 if (MI->getRawDest() != U)347 return ConstantRange::getEmpty(PointerSize);348 }349 350 auto *CalculationTy = IntegerType::getIntNTy(SE.getContext(), PointerSize);351 if (!SE.isSCEVable(MI->getLength()->getType()))352 return UnknownRange;353 354 const SCEV *Expr =355 SE.getTruncateOrZeroExtend(SE.getSCEV(MI->getLength()), CalculationTy);356 ConstantRange Sizes = SE.getSignedRange(Expr);357 if (!Sizes.getUpper().isStrictlyPositive() || isUnsafe(Sizes))358 return UnknownRange;359 Sizes = Sizes.sextOrTrunc(PointerSize);360 ConstantRange SizeRange(APInt::getZero(PointerSize), Sizes.getUpper() - 1);361 return getAccessRange(U, Base, SizeRange);362}363 364bool StackSafetyLocalAnalysis::isSafeAccess(const Use &U, AllocaInst *AI,365 Value *V) {366 return isSafeAccess(U, AI, SE.getSCEV(V));367}368 369bool StackSafetyLocalAnalysis::isSafeAccess(const Use &U, AllocaInst *AI,370 TypeSize TS) {371 if (TS.isScalable())372 return false;373 auto *CalculationTy = IntegerType::getIntNTy(SE.getContext(), PointerSize);374 const SCEV *SV = SE.getConstant(CalculationTy, TS.getFixedValue());375 return isSafeAccess(U, AI, SV);376}377 378bool StackSafetyLocalAnalysis::isSafeAccess(const Use &U, AllocaInst *AI,379 const SCEV *AccessSize) {380 381 if (!AI)382 return true; // This only judges whether it is a safe *stack* access.383 if (isa<SCEVCouldNotCompute>(AccessSize))384 return false;385 386 const auto *I = cast<Instruction>(U.getUser());387 388 const SCEV *AddrExp = getSCEVAsPointer(U.get());389 const SCEV *BaseExp = getSCEVAsPointer(AI);390 if (!AddrExp || !BaseExp)391 return false;392 393 const SCEV *Diff = SE.getMinusSCEV(AddrExp, BaseExp);394 if (isa<SCEVCouldNotCompute>(Diff))395 return false;396 397 auto Size = getStaticAllocaSizeRange(*AI);398 399 auto *CalculationTy = IntegerType::getIntNTy(SE.getContext(), PointerSize);400 auto ToDiffTy = [&](const SCEV *V) {401 return SE.getTruncateOrZeroExtend(V, CalculationTy);402 };403 const SCEV *Min = ToDiffTy(SE.getConstant(Size.getLower()));404 const SCEV *Max = SE.getMinusSCEV(ToDiffTy(SE.getConstant(Size.getUpper())),405 ToDiffTy(AccessSize));406 return SE.evaluatePredicateAt(ICmpInst::Predicate::ICMP_SGE, Diff, Min, I)407 .value_or(false) &&408 SE.evaluatePredicateAt(ICmpInst::Predicate::ICMP_SLE, Diff, Max, I)409 .value_or(false);410}411 412/// The function analyzes all local uses of Ptr (alloca or argument) and413/// calculates local access range and all function calls where it was used.414void StackSafetyLocalAnalysis::analyzeAllUses(Value *Ptr,415 UseInfo<GlobalValue> &US,416 const StackLifetime &SL) {417 SmallPtrSet<const Value *, 16> Visited;418 SmallVector<const Value *, 8> WorkList;419 WorkList.push_back(Ptr);420 AllocaInst *AI = dyn_cast<AllocaInst>(Ptr);421 422 // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc.423 while (!WorkList.empty()) {424 const Value *V = WorkList.pop_back_val();425 for (const Use &UI : V->uses()) {426 const auto *I = cast<Instruction>(UI.getUser());427 if (!SL.isReachable(I))428 continue;429 430 assert(V == UI.get());431 432 auto RecordStore = [&](const Value* StoredVal) {433 if (V == StoredVal) {434 // Stored the pointer - conservatively assume it may be unsafe.435 US.addRange(I, UnknownRange, /*IsSafe=*/false);436 return;437 }438 if (AI && !SL.isAliveAfter(AI, I)) {439 US.addRange(I, UnknownRange, /*IsSafe=*/false);440 return;441 }442 auto TypeSize = DL.getTypeStoreSize(StoredVal->getType());443 auto AccessRange = getAccessRange(UI, Ptr, TypeSize);444 bool Safe = isSafeAccess(UI, AI, TypeSize);445 US.addRange(I, AccessRange, Safe);446 return;447 };448 449 switch (I->getOpcode()) {450 case Instruction::Load: {451 if (AI && !SL.isAliveAfter(AI, I)) {452 US.addRange(I, UnknownRange, /*IsSafe=*/false);453 break;454 }455 auto TypeSize = DL.getTypeStoreSize(I->getType());456 auto AccessRange = getAccessRange(UI, Ptr, TypeSize);457 bool Safe = isSafeAccess(UI, AI, TypeSize);458 US.addRange(I, AccessRange, Safe);459 break;460 }461 462 case Instruction::VAArg:463 // "va-arg" from a pointer is safe.464 break;465 case Instruction::Store:466 RecordStore(cast<StoreInst>(I)->getValueOperand());467 break;468 case Instruction::AtomicCmpXchg:469 RecordStore(cast<AtomicCmpXchgInst>(I)->getNewValOperand());470 break;471 case Instruction::AtomicRMW:472 RecordStore(cast<AtomicRMWInst>(I)->getValOperand());473 break;474 475 case Instruction::Ret:476 // Information leak.477 // FIXME: Process parameters correctly. This is a leak only if we return478 // alloca.479 US.addRange(I, UnknownRange, /*IsSafe=*/false);480 break;481 482 case Instruction::Call:483 case Instruction::Invoke: {484 if (I->isLifetimeStartOrEnd())485 break;486 487 if (AI && !SL.isAliveAfter(AI, I)) {488 US.addRange(I, UnknownRange, /*IsSafe=*/false);489 break;490 }491 if (const MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {492 auto AccessRange = getMemIntrinsicAccessRange(MI, UI, Ptr);493 bool Safe = false;494 if (const auto *MTI = dyn_cast<MemTransferInst>(MI)) {495 if (MTI->getRawSource() != UI && MTI->getRawDest() != UI)496 Safe = true;497 } else if (MI->getRawDest() != UI) {498 Safe = true;499 }500 Safe = Safe || isSafeAccess(UI, AI, MI->getLength());501 US.addRange(I, AccessRange, Safe);502 break;503 }504 505 const auto &CB = cast<CallBase>(*I);506 if (CB.getReturnedArgOperand() == V) {507 if (Visited.insert(I).second)508 WorkList.push_back(cast<const Instruction>(I));509 }510 511 if (!CB.isArgOperand(&UI)) {512 US.addRange(I, UnknownRange, /*IsSafe=*/false);513 break;514 }515 516 unsigned ArgNo = CB.getArgOperandNo(&UI);517 if (CB.isByValArgument(ArgNo)) {518 auto TypeSize = DL.getTypeStoreSize(CB.getParamByValType(ArgNo));519 auto AccessRange = getAccessRange(UI, Ptr, TypeSize);520 bool Safe = isSafeAccess(UI, AI, TypeSize);521 US.addRange(I, AccessRange, Safe);522 break;523 }524 525 // FIXME: consult devirt?526 // Do not follow aliases, otherwise we could inadvertently follow527 // dso_preemptable aliases or aliases with interposable linkage.528 const GlobalValue *Callee =529 dyn_cast<GlobalValue>(CB.getCalledOperand()->stripPointerCasts());530 if (!Callee || isa<GlobalIFunc>(Callee)) {531 US.addRange(I, UnknownRange, /*IsSafe=*/false);532 break;533 }534 535 assert(isa<Function>(Callee) || isa<GlobalAlias>(Callee));536 ConstantRange Offsets = offsetFrom(UI, Ptr);537 auto Insert =538 US.Calls.emplace(CallInfo<GlobalValue>(Callee, ArgNo), Offsets);539 if (!Insert.second)540 Insert.first->second = Insert.first->second.unionWith(Offsets);541 break;542 }543 544 default:545 if (Visited.insert(I).second)546 WorkList.push_back(cast<const Instruction>(I));547 }548 }549 }550}551 552FunctionInfo<GlobalValue> StackSafetyLocalAnalysis::run() {553 FunctionInfo<GlobalValue> Info;554 assert(!F.isDeclaration() &&555 "Can't run StackSafety on a function declaration");556 557 LLVM_DEBUG(dbgs() << "[StackSafety] " << F.getName() << "\n");558 559 SmallVector<AllocaInst *, 64> Allocas;560 for (auto &I : instructions(F))561 if (auto *AI = dyn_cast<AllocaInst>(&I))562 Allocas.push_back(AI);563 StackLifetime SL(F, Allocas, StackLifetime::LivenessType::Must);564 SL.run();565 566 for (auto *AI : Allocas) {567 auto &UI = Info.Allocas.emplace(AI, PointerSize).first->second;568 analyzeAllUses(AI, UI, SL);569 }570 571 for (Argument &A : F.args()) {572 // Non pointers and bypass arguments are not going to be used in any global573 // processing.574 if (A.getType()->isPointerTy() && !A.hasByValAttr()) {575 auto &UI = Info.Params.emplace(A.getArgNo(), PointerSize).first->second;576 analyzeAllUses(&A, UI, SL);577 }578 }579 580 LLVM_DEBUG(Info.print(dbgs(), F.getName(), &F));581 LLVM_DEBUG(dbgs() << "\n[StackSafety] done\n");582 return Info;583}584 585template <typename CalleeTy> class StackSafetyDataFlowAnalysis {586 using FunctionMap = std::map<const CalleeTy *, FunctionInfo<CalleeTy>>;587 588 FunctionMap Functions;589 const ConstantRange UnknownRange;590 591 // Callee-to-Caller multimap.592 DenseMap<const CalleeTy *, SmallVector<const CalleeTy *, 4>> Callers;593 SetVector<const CalleeTy *> WorkList;594 595 bool updateOneUse(UseInfo<CalleeTy> &US, bool UpdateToFullSet);596 void updateOneNode(const CalleeTy *Callee, FunctionInfo<CalleeTy> &FS);597 void updateOneNode(const CalleeTy *Callee) {598 updateOneNode(Callee, Functions.find(Callee)->second);599 }600 void updateAllNodes() {601 for (auto &F : Functions)602 updateOneNode(F.first, F.second);603 }604 void runDataFlow();605#ifndef NDEBUG606 void verifyFixedPoint();607#endif608 609public:610 StackSafetyDataFlowAnalysis(uint32_t PointerBitWidth, FunctionMap Functions)611 : Functions(std::move(Functions)),612 UnknownRange(ConstantRange::getFull(PointerBitWidth)) {}613 614 const FunctionMap &run();615 616 ConstantRange getArgumentAccessRange(const CalleeTy *Callee, unsigned ParamNo,617 const ConstantRange &Offsets) const;618};619 620template <typename CalleeTy>621ConstantRange StackSafetyDataFlowAnalysis<CalleeTy>::getArgumentAccessRange(622 const CalleeTy *Callee, unsigned ParamNo,623 const ConstantRange &Offsets) const {624 auto FnIt = Functions.find(Callee);625 // Unknown callee (outside of LTO domain or an indirect call).626 if (FnIt == Functions.end())627 return UnknownRange;628 auto &FS = FnIt->second;629 auto ParamIt = FS.Params.find(ParamNo);630 if (ParamIt == FS.Params.end())631 return UnknownRange;632 auto &Access = ParamIt->second.Range;633 if (Access.isEmptySet())634 return Access;635 if (Access.isFullSet())636 return UnknownRange;637 return addOverflowNever(Access, Offsets);638}639 640template <typename CalleeTy>641bool StackSafetyDataFlowAnalysis<CalleeTy>::updateOneUse(UseInfo<CalleeTy> &US,642 bool UpdateToFullSet) {643 bool Changed = false;644 for (auto &KV : US.Calls) {645 assert(!KV.second.isEmptySet() &&646 "Param range can't be empty-set, invalid offset range");647 648 ConstantRange CalleeRange =649 getArgumentAccessRange(KV.first.Callee, KV.first.ParamNo, KV.second);650 if (!US.Range.contains(CalleeRange)) {651 Changed = true;652 if (UpdateToFullSet)653 US.Range = UnknownRange;654 else655 US.updateRange(CalleeRange);656 }657 }658 return Changed;659}660 661template <typename CalleeTy>662void StackSafetyDataFlowAnalysis<CalleeTy>::updateOneNode(663 const CalleeTy *Callee, FunctionInfo<CalleeTy> &FS) {664 bool UpdateToFullSet = FS.UpdateCount > StackSafetyMaxIterations;665 bool Changed = false;666 for (auto &KV : FS.Params)667 Changed |= updateOneUse(KV.second, UpdateToFullSet);668 669 if (Changed) {670 LLVM_DEBUG(dbgs() << "=== update [" << FS.UpdateCount671 << (UpdateToFullSet ? ", full-set" : "") << "] " << &FS672 << "\n");673 // Callers of this function may need updating.674 WorkList.insert_range(Callers[Callee]);675 676 ++FS.UpdateCount;677 }678}679 680template <typename CalleeTy>681void StackSafetyDataFlowAnalysis<CalleeTy>::runDataFlow() {682 SmallVector<const CalleeTy *, 16> Callees;683 for (auto &F : Functions) {684 Callees.clear();685 auto &FS = F.second;686 for (auto &KV : FS.Params)687 for (auto &CS : KV.second.Calls)688 Callees.push_back(CS.first.Callee);689 690 llvm::sort(Callees);691 Callees.erase(llvm::unique(Callees), Callees.end());692 693 for (auto &Callee : Callees)694 Callers[Callee].push_back(F.first);695 }696 697 updateAllNodes();698 699 while (!WorkList.empty()) {700 const CalleeTy *Callee = WorkList.pop_back_val();701 updateOneNode(Callee);702 }703}704 705#ifndef NDEBUG706template <typename CalleeTy>707void StackSafetyDataFlowAnalysis<CalleeTy>::verifyFixedPoint() {708 WorkList.clear();709 updateAllNodes();710 assert(WorkList.empty());711}712#endif713 714template <typename CalleeTy>715const typename StackSafetyDataFlowAnalysis<CalleeTy>::FunctionMap &716StackSafetyDataFlowAnalysis<CalleeTy>::run() {717 runDataFlow();718 LLVM_DEBUG(verifyFixedPoint());719 return Functions;720}721 722FunctionSummary *findCalleeFunctionSummary(ValueInfo VI, StringRef ModuleId) {723 if (!VI)724 return nullptr;725 auto SummaryList = VI.getSummaryList();726 GlobalValueSummary* S = nullptr;727 for (const auto& GVS : SummaryList) {728 if (!GVS->isLive())729 continue;730 if (const AliasSummary *AS = dyn_cast<AliasSummary>(GVS.get()))731 if (!AS->hasAliasee())732 continue;733 if (!isa<FunctionSummary>(GVS->getBaseObject()))734 continue;735 if (GlobalValue::isLocalLinkage(GVS->linkage())) {736 if (GVS->modulePath() == ModuleId) {737 S = GVS.get();738 break;739 }740 } else if (GlobalValue::isExternalLinkage(GVS->linkage())) {741 if (S) {742 ++NumIndexCalleeMultipleExternal;743 return nullptr;744 }745 S = GVS.get();746 } else if (GlobalValue::isWeakLinkage(GVS->linkage())) {747 if (S) {748 ++NumIndexCalleeMultipleWeak;749 return nullptr;750 }751 S = GVS.get();752 } else if (GlobalValue::isAvailableExternallyLinkage(GVS->linkage()) ||753 GlobalValue::isLinkOnceLinkage(GVS->linkage())) {754 if (SummaryList.size() == 1)755 S = GVS.get();756 // According thinLTOResolvePrevailingGUID these are unlikely prevailing.757 } else {758 ++NumIndexCalleeUnhandled;759 }760 };761 while (S) {762 if (!S->isLive() || !S->isDSOLocal())763 return nullptr;764 if (FunctionSummary *FS = dyn_cast<FunctionSummary>(S))765 return FS;766 AliasSummary *AS = dyn_cast<AliasSummary>(S);767 if (!AS || !AS->hasAliasee())768 return nullptr;769 S = AS->getBaseObject();770 if (S == AS)771 return nullptr;772 }773 return nullptr;774}775 776const Function *findCalleeInModule(const GlobalValue *GV) {777 while (GV) {778 if (GV->isDeclaration() || GV->isInterposable() || !GV->isDSOLocal())779 return nullptr;780 if (const Function *F = dyn_cast<Function>(GV))781 return F;782 const GlobalAlias *A = dyn_cast<GlobalAlias>(GV);783 if (!A)784 return nullptr;785 GV = A->getAliaseeObject();786 if (GV == A)787 return nullptr;788 }789 return nullptr;790}791 792const ConstantRange *findParamAccess(const FunctionSummary &FS,793 uint32_t ParamNo) {794 assert(FS.isLive());795 assert(FS.isDSOLocal());796 for (const auto &PS : FS.paramAccesses())797 if (ParamNo == PS.ParamNo)798 return &PS.Use;799 return nullptr;800}801 802void resolveAllCalls(UseInfo<GlobalValue> &Use,803 const ModuleSummaryIndex *Index) {804 ConstantRange FullSet(Use.Range.getBitWidth(), true);805 // Move Use.Calls to a temp storage and repopulate - don't use std::move as it806 // leaves Use.Calls in an undefined state.807 UseInfo<GlobalValue>::CallsTy TmpCalls;808 std::swap(TmpCalls, Use.Calls);809 for (const auto &C : TmpCalls) {810 const Function *F = findCalleeInModule(C.first.Callee);811 if (F) {812 Use.Calls.emplace(CallInfo<GlobalValue>(F, C.first.ParamNo), C.second);813 continue;814 }815 816 if (!Index)817 return Use.updateRange(FullSet);818 FunctionSummary *FS =819 findCalleeFunctionSummary(Index->getValueInfo(C.first.Callee->getGUID()),820 C.first.Callee->getParent()->getModuleIdentifier());821 ++NumModuleCalleeLookupTotal;822 if (!FS) {823 ++NumModuleCalleeLookupFailed;824 return Use.updateRange(FullSet);825 }826 const ConstantRange *Found = findParamAccess(*FS, C.first.ParamNo);827 if (!Found || Found->isFullSet())828 return Use.updateRange(FullSet);829 ConstantRange Access = Found->sextOrTrunc(Use.Range.getBitWidth());830 if (!Access.isEmptySet())831 Use.updateRange(addOverflowNever(Access, C.second));832 }833}834 835GVToSSI createGlobalStackSafetyInfo(836 std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions,837 const ModuleSummaryIndex *Index) {838 GVToSSI SSI;839 if (Functions.empty())840 return SSI;841 842 // FIXME: Simplify printing and remove copying here.843 auto Copy = Functions;844 845 for (auto &FnKV : Copy)846 for (auto &KV : FnKV.second.Params) {847 resolveAllCalls(KV.second, Index);848 if (KV.second.Range.isFullSet())849 KV.second.Calls.clear();850 }851 852 uint32_t PointerSize =853 Copy.begin()->first->getDataLayout().getPointerSizeInBits();854 StackSafetyDataFlowAnalysis<GlobalValue> SSDFA(PointerSize, std::move(Copy));855 856 for (const auto &F : SSDFA.run()) {857 auto FI = F.second;858 auto &SrcF = Functions[F.first];859 for (auto &KV : FI.Allocas) {860 auto &A = KV.second;861 resolveAllCalls(A, Index);862 for (auto &C : A.Calls) {863 A.updateRange(SSDFA.getArgumentAccessRange(C.first.Callee,864 C.first.ParamNo, C.second));865 }866 // FIXME: This is needed only to preserve calls in print() results.867 A.Calls = SrcF.Allocas.find(KV.first)->second.Calls;868 }869 for (auto &KV : FI.Params) {870 auto &P = KV.second;871 P.Calls = SrcF.Params.find(KV.first)->second.Calls;872 }873 SSI[F.first] = std::move(FI);874 }875 876 return SSI;877}878 879} // end anonymous namespace880 881StackSafetyInfo::StackSafetyInfo() = default;882 883StackSafetyInfo::StackSafetyInfo(Function *F,884 std::function<ScalarEvolution &()> GetSE)885 : F(F), GetSE(GetSE) {}886 887StackSafetyInfo::StackSafetyInfo(StackSafetyInfo &&) = default;888 889StackSafetyInfo &StackSafetyInfo::operator=(StackSafetyInfo &&) = default;890 891StackSafetyInfo::~StackSafetyInfo() = default;892 893const StackSafetyInfo::InfoTy &StackSafetyInfo::getInfo() const {894 if (!Info) {895 StackSafetyLocalAnalysis SSLA(*F, GetSE());896 Info.reset(new InfoTy{SSLA.run()});897 }898 return *Info;899}900 901void StackSafetyInfo::print(raw_ostream &O) const {902 getInfo().Info.print(O, F->getName(), dyn_cast<Function>(F));903 O << "\n";904}905 906const StackSafetyGlobalInfo::InfoTy &StackSafetyGlobalInfo::getInfo() const {907 if (!Info) {908 std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions;909 for (auto &F : M->functions()) {910 if (!F.isDeclaration()) {911 auto FI = GetSSI(F).getInfo().Info;912 Functions.emplace(&F, std::move(FI));913 }914 }915 Info.reset(new InfoTy{916 createGlobalStackSafetyInfo(std::move(Functions), Index), {}, {}});917 918 for (auto &FnKV : Info->Info) {919 for (auto &KV : FnKV.second.Allocas) {920 ++NumAllocaTotal;921 const AllocaInst *AI = KV.first;922 auto AIRange = getStaticAllocaSizeRange(*AI);923 if (AIRange.contains(KV.second.Range)) {924 Info->SafeAllocas.insert(AI);925 ++NumAllocaStackSafe;926 }927 Info->UnsafeAccesses.insert(KV.second.UnsafeAccesses.begin(),928 KV.second.UnsafeAccesses.end());929 }930 }931 932 if (StackSafetyPrint)933 print(errs());934 }935 return *Info;936}937 938std::vector<FunctionSummary::ParamAccess>939StackSafetyInfo::getParamAccesses(ModuleSummaryIndex &Index) const {940 // Implementation transforms internal representation of parameter information941 // into FunctionSummary format.942 std::vector<FunctionSummary::ParamAccess> ParamAccesses;943 for (const auto &KV : getInfo().Info.Params) {944 auto &PS = KV.second;945 // Parameter accessed by any or unknown offset, represented as FullSet by946 // StackSafety, is handled as the parameter for which we have no947 // StackSafety info at all. So drop it to reduce summary size.948 if (PS.Range.isFullSet())949 continue;950 951 ParamAccesses.emplace_back(KV.first, PS.Range);952 FunctionSummary::ParamAccess &Param = ParamAccesses.back();953 954 Param.Calls.reserve(PS.Calls.size());955 for (const auto &C : PS.Calls) {956 // Parameter forwarded into another function by any or unknown offset957 // will make ParamAccess::Range as FullSet anyway. So we can drop the958 // entire parameter like we did above.959 // TODO(vitalybuka): Return already filtered parameters from getInfo().960 if (C.second.isFullSet()) {961 ParamAccesses.pop_back();962 break;963 }964 Param.Calls.emplace_back(C.first.ParamNo,965 Index.getOrInsertValueInfo(C.first.Callee),966 C.second);967 }968 }969 for (FunctionSummary::ParamAccess &Param : ParamAccesses) {970 sort(Param.Calls, [](const FunctionSummary::ParamAccess::Call &L,971 const FunctionSummary::ParamAccess::Call &R) {972 return std::tie(L.ParamNo, L.Callee) < std::tie(R.ParamNo, R.Callee);973 });974 }975 return ParamAccesses;976}977 978StackSafetyGlobalInfo::StackSafetyGlobalInfo() = default;979 980StackSafetyGlobalInfo::StackSafetyGlobalInfo(981 Module *M, std::function<const StackSafetyInfo &(Function &F)> GetSSI,982 const ModuleSummaryIndex *Index)983 : M(M), GetSSI(GetSSI), Index(Index) {984 if (StackSafetyRun)985 getInfo();986}987 988StackSafetyGlobalInfo::StackSafetyGlobalInfo(StackSafetyGlobalInfo &&) =989 default;990 991StackSafetyGlobalInfo &992StackSafetyGlobalInfo::operator=(StackSafetyGlobalInfo &&) = default;993 994StackSafetyGlobalInfo::~StackSafetyGlobalInfo() = default;995 996bool StackSafetyGlobalInfo::isSafe(const AllocaInst &AI) const {997 const auto &Info = getInfo();998 return Info.SafeAllocas.count(&AI);999}1000 1001bool StackSafetyGlobalInfo::stackAccessIsSafe(const Instruction &I) const {1002 const auto &Info = getInfo();1003 return Info.UnsafeAccesses.find(&I) == Info.UnsafeAccesses.end();1004}1005 1006void StackSafetyGlobalInfo::print(raw_ostream &O) const {1007 auto &SSI = getInfo().Info;1008 if (SSI.empty())1009 return;1010 const Module &M = *SSI.begin()->first->getParent();1011 for (const auto &F : M.functions()) {1012 if (!F.isDeclaration()) {1013 SSI.find(&F)->second.print(O, F.getName(), &F);1014 O << " safe accesses:"1015 << "\n";1016 for (const auto &I : instructions(F)) {1017 const CallInst *Call = dyn_cast<CallInst>(&I);1018 if ((isa<StoreInst>(I) || isa<LoadInst>(I) || isa<MemIntrinsic>(I) ||1019 isa<AtomicCmpXchgInst>(I) || isa<AtomicRMWInst>(I) ||1020 (Call && Call->hasByValArgument())) &&1021 stackAccessIsSafe(I)) {1022 O << " " << I << "\n";1023 }1024 }1025 O << "\n";1026 }1027 }1028}1029 1030LLVM_DUMP_METHOD void StackSafetyGlobalInfo::dump() const { print(dbgs()); }1031 1032AnalysisKey StackSafetyAnalysis::Key;1033 1034StackSafetyInfo StackSafetyAnalysis::run(Function &F,1035 FunctionAnalysisManager &AM) {1036 return StackSafetyInfo(&F, [&AM, &F]() -> ScalarEvolution & {1037 return AM.getResult<ScalarEvolutionAnalysis>(F);1038 });1039}1040 1041PreservedAnalyses StackSafetyPrinterPass::run(Function &F,1042 FunctionAnalysisManager &AM) {1043 OS << "'Stack Safety Local Analysis' for function '" << F.getName() << "'\n";1044 AM.getResult<StackSafetyAnalysis>(F).print(OS);1045 return PreservedAnalyses::all();1046}1047 1048char StackSafetyInfoWrapperPass::ID = 0;1049 1050StackSafetyInfoWrapperPass::StackSafetyInfoWrapperPass() : FunctionPass(ID) {}1051 1052void StackSafetyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {1053 AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();1054 AU.setPreservesAll();1055}1056 1057void StackSafetyInfoWrapperPass::print(raw_ostream &O, const Module *M) const {1058 SSI.print(O);1059}1060 1061bool StackSafetyInfoWrapperPass::runOnFunction(Function &F) {1062 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();1063 SSI = {&F, [SE]() -> ScalarEvolution & { return *SE; }};1064 return false;1065}1066 1067AnalysisKey StackSafetyGlobalAnalysis::Key;1068 1069StackSafetyGlobalInfo1070StackSafetyGlobalAnalysis::run(Module &M, ModuleAnalysisManager &AM) {1071 // FIXME: Lookup Module Summary.1072 FunctionAnalysisManager &FAM =1073 AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();1074 return {&M,1075 [&FAM](Function &F) -> const StackSafetyInfo & {1076 return FAM.getResult<StackSafetyAnalysis>(F);1077 },1078 nullptr};1079}1080 1081PreservedAnalyses StackSafetyGlobalPrinterPass::run(Module &M,1082 ModuleAnalysisManager &AM) {1083 OS << "'Stack Safety Analysis' for module '" << M.getName() << "'\n";1084 AM.getResult<StackSafetyGlobalAnalysis>(M).print(OS);1085 return PreservedAnalyses::all();1086}1087 1088char StackSafetyGlobalInfoWrapperPass::ID = 0;1089 1090StackSafetyGlobalInfoWrapperPass::StackSafetyGlobalInfoWrapperPass()1091 : ModulePass(ID) {}1092 1093StackSafetyGlobalInfoWrapperPass::~StackSafetyGlobalInfoWrapperPass() = default;1094 1095void StackSafetyGlobalInfoWrapperPass::print(raw_ostream &O,1096 const Module *M) const {1097 SSGI.print(O);1098}1099 1100void StackSafetyGlobalInfoWrapperPass::getAnalysisUsage(1101 AnalysisUsage &AU) const {1102 AU.setPreservesAll();1103 AU.addRequired<StackSafetyInfoWrapperPass>();1104}1105 1106bool StackSafetyGlobalInfoWrapperPass::runOnModule(Module &M) {1107 const ModuleSummaryIndex *ImportSummary = nullptr;1108 if (auto *IndexWrapperPass =1109 getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>())1110 ImportSummary = IndexWrapperPass->getIndex();1111 1112 SSGI = {&M,1113 [this](Function &F) -> const StackSafetyInfo & {1114 return getAnalysis<StackSafetyInfoWrapperPass>(F).getResult();1115 },1116 ImportSummary};1117 return false;1118}1119 1120bool llvm::needsParamAccessSummary(const Module &M) {1121 if (StackSafetyRun)1122 return true;1123 for (const auto &F : M.functions())1124 if (F.hasFnAttribute(Attribute::SanitizeMemTag))1125 return true;1126 return false;1127}1128 1129void llvm::generateParamAccessSummary(ModuleSummaryIndex &Index) {1130 if (!Index.hasParamAccess())1131 return;1132 const ConstantRange FullSet(FunctionSummary::ParamAccess::RangeWidth, true);1133 1134 auto CountParamAccesses = [&](auto &Stat) {1135 if (!AreStatisticsEnabled())1136 return;1137 for (auto &GVS : Index)1138 for (auto &GV : GVS.second.getSummaryList())1139 if (FunctionSummary *FS = dyn_cast<FunctionSummary>(GV.get()))1140 Stat += FS->paramAccesses().size();1141 };1142 1143 CountParamAccesses(NumCombinedParamAccessesBefore);1144 1145 std::map<const FunctionSummary *, FunctionInfo<FunctionSummary>> Functions;1146 1147 // Convert the ModuleSummaryIndex to a FunctionMap1148 for (auto &GVS : Index) {1149 for (auto &GV : GVS.second.getSummaryList()) {1150 FunctionSummary *FS = dyn_cast<FunctionSummary>(GV.get());1151 if (!FS || FS->paramAccesses().empty())1152 continue;1153 if (FS->isLive() && FS->isDSOLocal()) {1154 FunctionInfo<FunctionSummary> FI;1155 for (const auto &PS : FS->paramAccesses()) {1156 auto &US =1157 FI.Params1158 .emplace(PS.ParamNo, FunctionSummary::ParamAccess::RangeWidth)1159 .first->second;1160 US.Range = PS.Use;1161 for (const auto &Call : PS.Calls) {1162 assert(!Call.Offsets.isFullSet());1163 FunctionSummary *S =1164 findCalleeFunctionSummary(Call.Callee, FS->modulePath());1165 ++NumCombinedCalleeLookupTotal;1166 if (!S) {1167 ++NumCombinedCalleeLookupFailed;1168 US.Range = FullSet;1169 US.Calls.clear();1170 break;1171 }1172 US.Calls.emplace(CallInfo<FunctionSummary>(S, Call.ParamNo),1173 Call.Offsets);1174 }1175 }1176 Functions.emplace(FS, std::move(FI));1177 }1178 // Reset data for all summaries. Alive and DSO local will be set back from1179 // of data flow results below. Anything else will not be accessed1180 // by ThinLTO backend, so we can save on bitcode size.1181 FS->setParamAccesses({});1182 }1183 }1184 NumCombinedDataFlowNodes += Functions.size();1185 StackSafetyDataFlowAnalysis<FunctionSummary> SSDFA(1186 FunctionSummary::ParamAccess::RangeWidth, std::move(Functions));1187 for (const auto &KV : SSDFA.run()) {1188 std::vector<FunctionSummary::ParamAccess> NewParams;1189 NewParams.reserve(KV.second.Params.size());1190 for (const auto &Param : KV.second.Params) {1191 // It's not needed as FullSet is processed the same as a missing value.1192 if (Param.second.Range.isFullSet())1193 continue;1194 NewParams.emplace_back();1195 FunctionSummary::ParamAccess &New = NewParams.back();1196 New.ParamNo = Param.first;1197 New.Use = Param.second.Range; // Only range is needed.1198 }1199 const_cast<FunctionSummary *>(KV.first)->setParamAccesses(1200 std::move(NewParams));1201 }1202 1203 CountParamAccesses(NumCombinedParamAccessesAfter);1204}1205 1206static const char LocalPassArg[] = "stack-safety-local";1207static const char LocalPassName[] = "Stack Safety Local Analysis";1208INITIALIZE_PASS_BEGIN(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,1209 false, true)1210INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)1211INITIALIZE_PASS_END(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,1212 false, true)1213 1214static const char GlobalPassName[] = "Stack Safety Analysis";1215INITIALIZE_PASS_BEGIN(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,1216 GlobalPassName, false, true)1217INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass)1218INITIALIZE_PASS_DEPENDENCY(ImmutableModuleSummaryIndexWrapperPass)1219INITIALIZE_PASS_END(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,1220 GlobalPassName, false, true)1221