38 #define DEBUG_TYPE "stack-safety"
40 STATISTIC(NumAllocaStackSafe,
"Number of safe allocas");
41 STATISTIC(NumAllocaTotal,
"Number of total allocas");
44 "Number of total callee lookups on combined index.");
46 "Number of failed callee lookups on combined index.");
48 "Number of total callee lookups on module index.");
50 "Number of failed callee lookups on module index.");
52 "Number of total param accesses before generateParamAccessSummary.");
54 "Number of total param accesses after generateParamAccessSummary.");
56 "Number of total nodes in combined index for dataflow processing.");
57 STATISTIC(NumIndexCalleeUnhandled,
"Number of index callee which are unhandled.");
58 STATISTIC(NumIndexCalleeMultipleWeak,
"Number of index callee non-unique weak.");
59 STATISTIC(NumIndexCalleeMultipleExternal,
"Number of index callee non-unique external.");
75 return R.isEmptySet() || R.isFullSet() || R.isUpperSignWrapped();
94 if (
Result.isSignWrappedSet())
100 template <
typename CalleeTy>
struct CallInfo {
102 const CalleeTy *
Callee =
nullptr;
106 CallInfo(
const CalleeTy *Callee,
size_t ParamNo)
111 return std::tie(L.ParamNo, L.Callee) < std::tie(
R.ParamNo,
R.Callee);
117 template <
typename CalleeTy>
struct UseInfo {
121 std::set<const Instruction *> UnsafeAccesses;
134 void updateRange(
const ConstantRange &R) { Range = unionNoWrap(Range, R); }
137 UnsafeAccesses.insert(
I);
142 template <
typename CalleeTy>
145 for (
auto &Call : U.Calls)
147 <<
"@" <<
Call.first.Callee->getName() <<
"(arg" <<
Call.first.ParamNo
148 <<
", " <<
Call.second <<
")";
163 if (APSize.isNonPositive())
169 bool Overflow =
false;
171 if (
Mul.isNonPositive())
174 APSize = APSize.smul_ov(Mul, Overflow);
183 template <
typename CalleeTy>
struct FunctionInfo {
184 std::map<const AllocaInst *, UseInfo<CalleeTy>> Allocas;
185 std::map<uint32_t, UseInfo<CalleeTy>> Params;
194 O <<
" @" <<
Name << ((
F &&
F->isDSOLocal()) ?
"" :
" dso_preemptable")
195 << ((
F &&
F->isInterposable()) ?
" interposable" :
"") <<
"\n";
197 O <<
" args uses:\n";
198 for (
auto &KV : Params) {
201 O <<
F->getArg(KV.first)->getName();
204 O <<
"[]: " << KV.second <<
"\n";
207 O <<
" allocas uses:\n";
210 if (
const AllocaInst *AI = dyn_cast<AllocaInst>(&
I)) {
211 auto &AS = Allocas.find(AI)->second;
213 << getStaticAllocaSizeRange(*AI).getUpper() <<
"]: " << AS <<
"\n";
222 using GVToSSI = std::map<const GlobalValue *, FunctionInfo<GlobalValue>>;
227 FunctionInfo<GlobalValue>
Info;
238 class StackSafetyLocalAnalysis {
253 void analyzeAllUses(
Value *Ptr, UseInfo<GlobalValue> &AS,
263 :
F(
F),
DL(
F.getParent()->getDataLayout()), SE(SE),
268 FunctionInfo<GlobalValue>
run();
272 if (!SE.isSCEVable(
Addr->getType()) || !SE.isSCEVable(
Base->getType()))
276 const SCEV *AddrExp = SE.getTruncateOrZeroExtend(SE.getSCEV(
Addr), PtrTy);
277 const SCEV *BaseExp = SE.getTruncateOrZeroExtend(SE.getSCEV(
Base), PtrTy);
278 const SCEV *Diff = SE.getMinusSCEV(AddrExp, BaseExp);
279 if (isa<SCEVCouldNotCompute>(Diff))
283 if (isUnsafe(Offset))
294 assert(!isUnsafe(SizeRange));
308 if (
Size.isScalable())
311 if (APSize.isNegative())
317 ConstantRange StackSafetyLocalAnalysis::getMemIntrinsicAccessRange(
319 if (
const auto *MTI = dyn_cast<MemTransferInst>(
MI)) {
320 if (MTI->getRawSource() != U && MTI->getRawDest() != U)
323 if (
MI->getRawDest() != U)
328 if (!SE.isSCEVable(
MI->getLength()->getType()))
332 SE.getTruncateOrZeroExtend(SE.getSCEV(
MI->getLength()), CalculationTy);
338 return getAccessRange(U,
Base, SizeRange);
341 bool StackSafetyLocalAnalysis::isSafeAccess(
const Use &U,
AllocaInst *AI,
343 return isSafeAccess(U, AI, SE.getSCEV(V));
346 bool StackSafetyLocalAnalysis::isSafeAccess(
const Use &U,
AllocaInst *AI,
352 return isSafeAccess(U, AI, SV);
355 bool StackSafetyLocalAnalysis::isSafeAccess(
const Use &U,
AllocaInst *AI,
356 const SCEV *AccessSize) {
360 if (isa<SCEVCouldNotCompute>(AccessSize))
363 const auto *
I = cast<Instruction>(U.
getUser());
365 auto ToCharPtr = [&](
const SCEV *V) {
367 return SE.getTruncateOrZeroExtend(V, PtrTy);
370 const SCEV *AddrExp = ToCharPtr(SE.getSCEV(U.
get()));
371 const SCEV *BaseExp = ToCharPtr(SE.getSCEV(AI));
372 const SCEV *Diff = SE.getMinusSCEV(AddrExp, BaseExp);
373 if (isa<SCEVCouldNotCompute>(Diff))
376 auto Size = getStaticAllocaSizeRange(*AI);
379 auto ToDiffTy = [&](
const SCEV *V) {
380 return SE.getTruncateOrZeroExtend(V, CalculationTy);
382 const SCEV *Min = ToDiffTy(SE.getConstant(
Size.getLower()));
383 const SCEV *
Max = SE.getMinusSCEV(ToDiffTy(SE.getConstant(
Size.getUpper())),
384 ToDiffTy(AccessSize));
385 return SE.evaluatePredicateAt(ICmpInst::Predicate::ICMP_SGE, Diff, Min,
I)
387 SE.evaluatePredicateAt(ICmpInst::Predicate::ICMP_SLE, Diff, Max,
I)
393 void StackSafetyLocalAnalysis::analyzeAllUses(
Value *Ptr,
394 UseInfo<GlobalValue> &US,
398 WorkList.push_back(Ptr);
402 while (!WorkList.empty()) {
404 for (
const Use &UI : V->
uses()) {
405 const auto *
I = cast<Instruction>(UI.getUser());
411 switch (
I->getOpcode()) {
414 US.addRange(
I, UnknownRange,
false);
418 auto AccessRange = getAccessRange(UI, Ptr,
TypeSize);
419 bool Safe = isSafeAccess(UI, AI,
TypeSize);
420 US.addRange(
I, AccessRange, Safe);
424 case Instruction::VAArg:
428 if (V ==
I->getOperand(0)) {
430 US.addRange(
I, UnknownRange,
false);
434 US.addRange(
I, UnknownRange,
false);
437 auto TypeSize =
DL.getTypeStoreSize(
I->getOperand(0)->getType());
438 auto AccessRange = getAccessRange(UI, Ptr,
TypeSize);
439 bool Safe = isSafeAccess(UI, AI,
TypeSize);
440 US.addRange(
I, AccessRange, Safe);
448 US.addRange(
I, UnknownRange,
false);
452 case Instruction::Invoke: {
453 if (
I->isLifetimeStartOrEnd())
457 US.addRange(
I, UnknownRange,
false);
461 auto AccessRange = getMemIntrinsicAccessRange(
MI, UI, Ptr);
463 if (
const auto *MTI = dyn_cast<MemTransferInst>(
MI)) {
464 if (MTI->getRawSource() != UI && MTI->getRawDest() != UI)
466 }
else if (
MI->getRawDest() != UI) {
469 Safe = Safe || isSafeAccess(UI, AI,
MI->getLength());
470 US.addRange(
I, AccessRange, Safe);
474 const auto &CB = cast<CallBase>(*
I);
475 if (CB.getReturnedArgOperand() == V) {
477 WorkList.push_back(cast<const Instruction>(
I));
480 if (!CB.isArgOperand(&UI)) {
481 US.addRange(
I, UnknownRange,
false);
485 unsigned ArgNo = CB.getArgOperandNo(&UI);
486 if (CB.isByValArgument(ArgNo)) {
487 auto TypeSize =
DL.getTypeStoreSize(CB.getParamByValType(ArgNo));
488 auto AccessRange = getAccessRange(UI, Ptr,
TypeSize);
489 bool Safe = isSafeAccess(UI, AI,
TypeSize);
490 US.addRange(
I, AccessRange, Safe);
498 dyn_cast<GlobalValue>(CB.getCalledOperand()->stripPointerCasts());
500 US.addRange(
I, UnknownRange,
false);
504 assert(isa<Function>(Callee) || isa<GlobalAlias>(Callee));
515 WorkList.push_back(cast<const Instruction>(
I));
522 FunctionInfo<GlobalValue>
Info;
524 "Can't run StackSafety on a function declaration");
530 if (
auto *AI = dyn_cast<AllocaInst>(&
I))
531 Allocas.push_back(AI);
535 for (
auto *AI : Allocas) {
537 analyzeAllUses(AI, UI, SL);
543 if (
A.getType()->isPointerTy() && !
A.hasByValAttr()) {
545 analyzeAllUses(&A, UI, SL);
554 template <
typename CalleeTy>
class StackSafetyDataFlowAnalysis {
555 using FunctionMap = std::map<const CalleeTy *, FunctionInfo<CalleeTy>>;
557 FunctionMap Functions;
564 bool updateOneUse(UseInfo<CalleeTy> &US,
bool UpdateToFullSet);
565 void updateOneNode(
const CalleeTy *Callee, FunctionInfo<CalleeTy> &
FS);
566 void updateOneNode(
const CalleeTy *Callee) {
567 updateOneNode(Callee, Functions.find(Callee)->second);
569 void updateAllNodes() {
570 for (
auto &
F : Functions)
571 updateOneNode(
F.first,
F.second);
575 void verifyFixedPoint();
579 StackSafetyDataFlowAnalysis(
uint32_t PointerBitWidth, FunctionMap Functions)
580 : Functions(
std::
move(Functions)),
583 const FunctionMap &
run();
585 ConstantRange getArgumentAccessRange(
const CalleeTy *Callee,
unsigned ParamNo,
589 template <
typename CalleeTy>
590 ConstantRange StackSafetyDataFlowAnalysis<CalleeTy>::getArgumentAccessRange(
591 const CalleeTy *Callee,
unsigned ParamNo,
593 auto FnIt = Functions.find(Callee);
595 if (FnIt == Functions.end())
597 auto &
FS = FnIt->second;
598 auto ParamIt =
FS.Params.find(ParamNo);
599 if (ParamIt ==
FS.Params.end())
601 auto &Access = ParamIt->second.Range;
602 if (Access.isEmptySet())
604 if (Access.isFullSet())
606 return addOverflowNever(Access,
Offsets);
609 template <
typename CalleeTy>
610 bool StackSafetyDataFlowAnalysis<CalleeTy>::updateOneUse(UseInfo<CalleeTy> &US,
611 bool UpdateToFullSet) {
612 bool Changed =
false;
613 for (
auto &KV : US.Calls) {
614 assert(!KV.second.isEmptySet() &&
615 "Param range can't be empty-set, invalid offset range");
618 getArgumentAccessRange(KV.first.Callee, KV.first.ParamNo, KV.second);
619 if (!US.Range.contains(CalleeRange)) {
622 US.Range = UnknownRange;
624 US.updateRange(CalleeRange);
630 template <
typename CalleeTy>
631 void StackSafetyDataFlowAnalysis<CalleeTy>::updateOneNode(
632 const CalleeTy *Callee, FunctionInfo<CalleeTy> &
FS) {
634 bool Changed =
false;
635 for (
auto &KV :
FS.Params)
636 Changed |= updateOneUse(KV.second, UpdateToFullSet);
640 << (UpdateToFullSet ?
", full-set" :
"") <<
"] " << &
FS
643 for (
auto &CallerID : Callers[Callee])
644 WorkList.
insert(CallerID);
650 template <
typename CalleeTy>
651 void StackSafetyDataFlowAnalysis<CalleeTy>::runDataFlow() {
653 for (
auto &
F : Functions) {
656 for (
auto &KV :
FS.Params)
657 for (
auto &CS : KV.second.Calls)
658 Callees.push_back(CS.first.Callee);
663 for (
auto &Callee : Callees)
664 Callers[
Callee].push_back(
F.first);
669 while (!WorkList.
empty()) {
671 updateOneNode(Callee);
676 template <
typename CalleeTy>
677 void StackSafetyDataFlowAnalysis<CalleeTy>::verifyFixedPoint() {
684 template <
typename CalleeTy>
685 const typename StackSafetyDataFlowAnalysis<CalleeTy>::FunctionMap &
695 auto SummaryList =
VI.getSummaryList();
697 for (
const auto& GVS : SummaryList) {
700 if (
const AliasSummary *AS = dyn_cast<AliasSummary>(GVS.get()))
701 if (!AS->hasAliasee())
703 if (!isa<FunctionSummary>(GVS->getBaseObject()))
706 if (GVS->modulePath() == ModuleId) {
712 ++NumIndexCalleeMultipleExternal;
718 ++NumIndexCalleeMultipleWeak;
724 if (SummaryList.size() == 1)
728 ++NumIndexCalleeUnhandled;
732 if (!
S->isLive() || !
S->isDSOLocal())
750 if (
const Function *
F = dyn_cast<Function>(GV))
755 GV =
A->getAliaseeObject();
766 for (
auto &PS :
FS.paramAccesses())
767 if (ParamNo == PS.ParamNo)
772 void resolveAllCalls(UseInfo<GlobalValue> &
Use,
777 UseInfo<GlobalValue>::CallsTy TmpCalls;
779 for (
const auto &
C : TmpCalls) {
780 const Function *
F = findCalleeInModule(
C.first.Callee);
787 return Use.updateRange(FullSet);
789 findCalleeFunctionSummary(
Index->getValueInfo(
C.first.Callee->getGUID()),
790 C.first.Callee->getParent()->getModuleIdentifier());
791 ++NumModuleCalleeLookupTotal;
793 ++NumModuleCalleeLookupFailed;
794 return Use.updateRange(FullSet);
798 return Use.updateRange(FullSet);
801 Use.updateRange(addOverflowNever(Access,
C.second));
805 GVToSSI createGlobalStackSafetyInfo(
806 std::map<
const GlobalValue *, FunctionInfo<GlobalValue>> Functions,
809 if (Functions.empty())
813 auto Copy = Functions;
815 for (
auto &FnKV : Copy)
816 for (
auto &KV : FnKV.second.Params) {
817 resolveAllCalls(KV.second,
Index);
818 if (KV.second.Range.isFullSet())
819 KV.second.Calls.clear();
823 Copy.begin()->first->getParent()->getDataLayout().getPointerSizeInBits();
826 for (
auto &
F : SSDFA.run()) {
828 auto &SrcF = Functions[
F.first];
829 for (
auto &KV : FI.Allocas) {
831 resolveAllCalls(A,
Index);
832 for (
auto &
C :
A.Calls) {
833 A.updateRange(SSDFA.getArgumentAccessRange(
C.first.Callee,
834 C.first.ParamNo,
C.second));
837 A.Calls = SrcF.Allocas.find(KV.first)->second.Calls;
839 for (
auto &KV : FI.Params) {
841 P.Calls = SrcF.Params.find(KV.first)->second.Calls;
855 :
F(
F), GetSE(GetSE) {}
865 StackSafetyLocalAnalysis SSLA(*
F, GetSE());
878 std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions;
880 if (!
F.isDeclaration()) {
881 auto FI = GetSSI(
F).getInfo().Info;
885 Info.reset(
new InfoTy{
886 createGlobalStackSafetyInfo(
std::move(Functions),
Index), {}, {}});
888 for (
auto &FnKV :
Info->Info) {
889 for (
auto &KV : FnKV.second.Allocas) {
892 auto AIRange = getStaticAllocaSizeRange(*AI);
893 if (AIRange.contains(KV.second.Range)) {
894 Info->SafeAllocas.insert(AI);
895 ++NumAllocaStackSafe;
897 Info->UnsafeAccesses.insert(KV.second.UnsafeAccesses.begin(),
898 KV.second.UnsafeAccesses.end());
908 std::vector<FunctionSummary::ParamAccess>
912 std::vector<FunctionSummary::ParamAccess> ParamAccesses;
914 auto &PS = KV.second;
918 if (PS.Range.isFullSet())
921 ParamAccesses.emplace_back(KV.first, PS.Range);
924 Param.Calls.reserve(PS.Calls.size());
925 for (
auto &
C : PS.Calls) {
930 if (
C.second.isFullSet()) {
931 ParamAccesses.pop_back();
934 Param.Calls.emplace_back(
C.first.ParamNo,
935 Index.getOrInsertValueInfo(
C.first.Callee),
942 return std::tie(L.ParamNo, L.Callee) < std::tie(R.ParamNo, R.Callee);
945 return ParamAccesses;
967 const auto &
Info = getInfo();
968 return Info.SafeAllocas.count(&AI);
972 const auto &
Info = getInfo();
973 return Info.UnsafeAccesses.find(&
I) ==
Info.UnsafeAccesses.end();
977 auto &SSI = getInfo().
Info;
980 const Module &
M = *SSI.begin()->first->getParent();
981 for (
auto &
F :
M.functions()) {
982 if (!
F.isDeclaration()) {
983 SSI.find(&
F)->second.print(
O,
F.getName(), &
F);
984 O <<
" safe accesses:"
987 const CallInst *Call = dyn_cast<CallInst>(&
I);
988 if ((isa<StoreInst>(
I) || isa<LoadInst>(
I) || isa<MemIntrinsic>(
I) ||
989 (Call && Call->hasByValArgument())) &&
991 O <<
" " <<
I <<
"\n";
1012 OS <<
"'Stack Safety Local Analysis' for function '" <<
F.getName() <<
"'\n";
1033 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1054 OS <<
"'Stack Safety Analysis' for module '" <<
M.getName() <<
"'\n";
1082 if (
auto *IndexWrapperPass =
1083 getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>())
1084 ImportSummary = IndexWrapperPass->getIndex();
1088 return getAnalysis<StackSafetyInfoWrapperPass>(
F).getResult();
1097 for (
auto &
F :
M.functions())
1098 if (
F.hasFnAttribute(Attribute::SanitizeMemTag))
1104 if (!
Index.hasParamAccess())
1108 auto CountParamAccesses = [&](
auto &Stat) {
1111 for (
auto &GVS :
Index)
1112 for (
auto &GV : GVS.second.SummaryList)
1114 Stat +=
FS->paramAccesses().size();
1117 CountParamAccesses(NumCombinedParamAccessesBefore);
1119 std::map<const FunctionSummary *, FunctionInfo<FunctionSummary>> Functions;
1122 for (
auto &GVS :
Index) {
1123 for (
auto &GV : GVS.second.SummaryList) {
1125 if (!
FS ||
FS->paramAccesses().empty())
1127 if (
FS->isLive() &&
FS->isDSOLocal()) {
1128 FunctionInfo<FunctionSummary> FI;
1129 for (
auto &PS :
FS->paramAccesses()) {
1135 for (
auto &Call : PS.Calls) {
1136 assert(!Call.Offsets.isFullSet());
1138 findCalleeFunctionSummary(Call.Callee,
FS->modulePath());
1139 ++NumCombinedCalleeLookupTotal;
1141 ++NumCombinedCalleeLookupFailed;
1155 FS->setParamAccesses({});
1158 NumCombinedDataFlowNodes += Functions.size();
1159 StackSafetyDataFlowAnalysis<FunctionSummary> SSDFA(
1161 for (
auto &KV : SSDFA.run()) {
1162 std::vector<FunctionSummary::ParamAccess> NewParams;
1163 NewParams.reserve(KV.second.Params.size());
1164 for (
auto &
Param : KV.second.Params) {
1166 if (
Param.second.Range.isFullSet())
1168 NewParams.emplace_back();
1170 New.ParamNo =
Param.first;
1171 New.Use =
Param.second.Range;
1177 CountParamAccesses(NumCombinedParamAccessesAfter);