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