LLVM: lib/Analysis/StackSafetyAnalysis.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
32#include
33#include
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
43 "Number of total callee lookups on combined index.");
45 "Number of failed callee lookups on combined index.");
47 "Number of total callee lookups on module index.");
49 "Number of failed callee lookups on module index.");
51 "Number of total param accesses before generateParamAccessSummary.");
53 "Number of total param accesses after generateParamAccessSummary.");
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
63
66
69
70namespace {
71
72
74 return R.isEmptySet() || R.isFullSet() || R.isUpperSignWrapped();
75}
76
78 assert(.isSignWrappedSet());
79 assert(.isSignWrappedSet());
80 if (L.signedAddMayOverflow(R) !=
82 return ConstantRange::getFull(L.getBitWidth());
86}
87
89 assert(.isSignWrappedSet());
90 assert(.isSignWrappedSet());
91 auto Result = L.unionWith(R);
92
93 if (Result.isSignWrappedSet())
94 Result = ConstantRange::getFull(Result.getBitWidth());
96}
97
98
99template struct CallInfo {
100
101 const CalleeTy *Callee = nullptr;
102
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
116template struct UseInfo {
117
118
119 ConstantRange Range;
120 std::set<const Instruction *> UnsafeAccesses;
121
122
123
124
125
126
127 using CallsTy = std::map<CallInfo, ConstantRange,
128 typename CallInfo::Less>;
129 CallsTy Calls;
130
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
143 OS << U.Range;
144 for (auto &Call : U.Calls)
145 OS << ", "
146 << "@" << Call.first.Callee->getName() << "(arg" << Call.first.ParamNo
147 << ", " << Call.second << ")";
148 return OS;
149}
150
151
152
157
158 ConstantRange R = ConstantRange::getEmpty(PointerSize);
160 return R;
162 if (APSize.isNonPositive())
163 return R;
166 if ()
167 return R;
168 bool Overflow = false;
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 }
178 assert(!isUnsafe(R));
179 return R;
180}
181
182template struct FunctionInfo {
183 std::map<const AllocaInst *, UseInfo> Allocas;
184 std::map<uint32_t, UseInfo> Params;
185
186
187
188 int UpdateCount = 0;
189
190 void print(raw_ostream &O, StringRef Name, const Function *F) const {
191
192
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 else
202 O << formatv("arg{0}", KV.first);
203 O << "[]: " << KV.second << "\n";
204 }
205
206 O << " allocas uses:\n";
207 if (F) {
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>;
222
223}
224
227};
228
234
235namespace {
236
237class StackSafetyLocalAnalysis {
241 unsigned PointerSize = 0;
242
244
245
246
247
248
249
250
251 const SCEV *getSCEVAsPointer(Value *Val);
252
259
260 void analyzeAllUses(Value *Ptr, UseInfo &AS,
262
263
264 bool isSafeAccess(const Use &U, AllocaInst *AI, const SCEV *AccessSize);
267
268public:
270 : F(F), DL(F.getDataLayout()), SE(SE),
271 PointerSize(DL.getPointerSizeInBits()),
272 UnknownRange(PointerSize, true) {}
273
274
275 FunctionInfo run();
276};
277
278const SCEV *StackSafetyLocalAnalysis::getSCEVAsPointer(Value *Val) {
280
281
282 if (!ValTy->isPointerTy()) {
285 }
286
287 if (ValTy->getPointerAddressSpace() != 0)
288 return nullptr;
290}
291
292ConstantRange StackSafetyLocalAnalysis::offsetFrom(Value *Addr, Value *Base) {
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);
303 return UnknownRange;
304
306 if (isUnsafe(Offset))
307 return UnknownRange;
309}
310
311ConstantRange
312StackSafetyLocalAnalysis::getAccessRange(Value *Addr, Value *Base,
313 const ConstantRange &SizeRange) {
314
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;
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,
338}
339
340ConstantRange StackSafetyLocalAnalysis::getMemIntrinsicAccessRange(
341 const MemIntrinsic *MI, const Use &U, Value *Base) {
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 =
357 if (.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,
366 return isSafeAccess(U, AI, SE.getSCEV(V));
367}
368
369bool StackSafetyLocalAnalysis::isSafeAccess(const Use &U, AllocaInst *AI,
370 TypeSize TS) {
372 return false;
373 auto *CalculationTy = IntegerType::getIntNTy(SE.getContext(), PointerSize);
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;
384 return false;
385
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);
395 return false;
396
397 auto Size = getStaticAllocaSizeRange(*AI);
398
399 auto *CalculationTy = IntegerType::getIntNTy(SE.getContext(), PointerSize);
400 auto ToDiffTy = [&](const SCEV *V) {
402 };
403 const SCEV *Min = ToDiffTy(SE.getConstant(Size.getLower()));
405 ToDiffTy(AccessSize));
407 .value_or(false) &&
409 .value_or(false);
410}
411
412
413
414void StackSafetyLocalAnalysis::analyzeAllUses(Value *Ptr,
415 UseInfo &US,
416 const StackLifetime &SL) {
417 SmallPtrSet<const Value *, 16> Visited;
418 SmallVector<const Value *, 8> WorkList;
421
422
423 while (!WorkList.empty()) {
425 for (const Use &UI : V->uses()) {
428 continue;
429
430 assert(V == UI.get());
431
432 auto RecordStore = [&](const Value* StoredVal) {
433 if (V == StoredVal) {
434
435 US.addRange(I, UnknownRange, false);
436 return;
437 }
439 US.addRange(I, UnknownRange, 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: {
452 US.addRange(I, UnknownRange, 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
464 break;
465 case Instruction::Store:
467 break;
468 case Instruction::AtomicCmpXchg:
470 break;
471 case Instruction::AtomicRMW:
473 break;
474
475 case Instruction::Ret:
476
477
478
479 US.addRange(I, UnknownRange, false);
480 break;
481
482 case Instruction::Call:
483 case Instruction::Invoke: {
484 if (I->isLifetimeStartOrEnd())
485 break;
486
488 US.addRange(I, UnknownRange, false);
489 break;
490 }
492 auto AccessRange = getMemIntrinsicAccessRange(MI, UI, Ptr);
493 bool Safe = false;
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
506 if (CB.getReturnedArgOperand() == V) {
507 if (Visited.insert(I).second)
509 }
510
511 if (!CB.isArgOperand(&UI)) {
512 US.addRange(I, UnknownRange, 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
526
527
528 const GlobalValue *Callee =
531 US.addRange(I, UnknownRange, false);
532 break;
533 }
534
536 ConstantRange Offsets = offsetFrom(UI, Ptr);
538 US.Calls.emplace(CallInfo(Callee, ArgNo), Offsets);
540 Insert.first->second = Insert.first->second.unionWith(Offsets);
541 break;
542 }
543
544 default:
545 if (Visited.insert(I).second)
547 }
548 }
549 }
550}
551
552FunctionInfo StackSafetyLocalAnalysis::run() {
553 FunctionInfo Info;
554 assert(.isDeclaration() &&
555 "Can't run StackSafety on a function declaration");
556
557 LLVM_DEBUG(dbgs() << "[StackSafety] " << F.getName() << "\n");
558
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
573
574 if (A.getType()->isPointerTy() && .hasByValAttr()) {
575 auto &UI = Info.Params.emplace(A.getArgNo(), PointerSize).first->second;
576 analyzeAllUses(&A, UI, SL);
577 }
578 }
579
583}
584
585template class StackSafetyDataFlowAnalysis {
586 using FunctionMap = std::map<const CalleeTy *, FunctionInfo>;
587
588 FunctionMap Functions;
589 const ConstantRange UnknownRange;
590
591
592 DenseMap<const CalleeTy *, SmallVector<const CalleeTy *, 4>> Callers;
593 SetVector<const CalleeTy *> WorkList;
594
595 bool updateOneUse(UseInfo &US, bool UpdateToFullSet);
596 void updateOneNode(const CalleeTy *Callee, FunctionInfo &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 NDEBUG
606 void verifyFixedPoint();
607#endif
608
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
621ConstantRange StackSafetyDataFlowAnalysis::getArgumentAccessRange(
622 const CalleeTy *Callee, unsigned ParamNo,
623 const ConstantRange &Offsets) const {
624 auto FnIt = Functions.find(Callee);
625
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())
635 if (Access.isFullSet())
636 return UnknownRange;
637 return addOverflowNever(Access, Offsets);
638}
639
640template
641bool StackSafetyDataFlowAnalysis::updateOneUse(UseInfo &US,
642 bool UpdateToFullSet) {
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)) {
652 if (UpdateToFullSet)
653 US.Range = UnknownRange;
654 else
655 US.updateRange(CalleeRange);
656 }
657 }
659}
660
661template
662void StackSafetyDataFlowAnalysis::updateOneNode(
663 const CalleeTy *Callee, FunctionInfo &FS) {
666 for (auto &KV : FS.Params)
667 Changed |= updateOneUse(KV.second, UpdateToFullSet);
668
671 << (UpdateToFullSet ? ", full-set" : "") << "] " << &FS
672 << "\n");
673
675
676 ++FS.UpdateCount;
677 }
678}
679
680template
681void StackSafetyDataFlowAnalysis::runDataFlow() {
683 for (auto &F : Functions) {
686 for (auto &KV : FS.Params)
687 for (auto &CS : KV.second.Calls)
688 Callees.push_back(CS.first.Callee);
689
692
693 for (auto &Callee : Callees)
694 Callers[Callee].push_back(F.first);
695 }
696
697 updateAllNodes();
698
699 while (!WorkList.empty()) {
701 updateOneNode(Callee);
702 }
703}
704
705#ifndef NDEBUG
706template
707void StackSafetyDataFlowAnalysis::verifyFixedPoint() {
708 WorkList.clear();
709 updateAllNodes();
711}
712#endif
713
714template
715const typename StackSafetyDataFlowAnalysis::FunctionMap &
716StackSafetyDataFlowAnalysis::run() {
717 runDataFlow();
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;
731 if (!AS->hasAliasee())
732 continue;
734 continue;
736 if (GVS->modulePath() == ModuleId) {
737 S = GVS.get();
738 break;
739 }
741 if (S) {
742 ++NumIndexCalleeMultipleExternal;
743 return nullptr;
744 }
745 S = GVS.get();
747 if (S) {
748 ++NumIndexCalleeMultipleWeak;
749 return nullptr;
750 }
751 S = GVS.get();
754 if (SummaryList.size() == 1)
755 S = GVS.get();
756
757 } else {
758 ++NumIndexCalleeUnhandled;
759 }
760 };
761 while (S) {
763 return nullptr;
765 return FS;
768 return nullptr;
770 if (S == AS)
771 return nullptr;
772 }
773 return nullptr;
774}
775
776const Function *findCalleeInModule(const GlobalValue *GV) {
777 while (GV) {
779 return nullptr;
781 return F;
783 if ()
784 return nullptr;
786 if (GV == A)
787 return nullptr;
788 }
789 return nullptr;
790}
791
792const ConstantRange *findParamAccess(const FunctionSummary &FS,
793 uint32_t ParamNo) {
796 for (const auto &PS : FS.paramAccesses())
797 if (ParamNo == PS.ParamNo)
798 return &PS.Use;
799 return nullptr;
800}
801
802void resolveAllCalls(UseInfo &Use,
803 const ModuleSummaryIndex *Index) {
804 ConstantRange FullSet(Use.Range.getBitWidth(), true);
805
806
807 UseInfo::CallsTy TmpCalls;
809 for (const auto &C : TmpCalls) {
810 const Function *F = findCalleeInModule(C.first.Callee);
811 if (F) {
812 Use.Calls.emplace(CallInfo(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);
830 if (.isEmptySet())
831 Use.updateRange(addOverflowNever(Access, C.second));
832 }
833}
834
835GVToSSI createGlobalStackSafetyInfo(
836 std::map<const GlobalValue *, FunctionInfo> Functions,
837 const ModuleSummaryIndex *Index) {
838 GVToSSI SSI;
839 if (Functions.empty())
840 return SSI;
841
842
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
853 Copy.begin()->first->getDataLayout().getPointerSizeInBits();
854 StackSafetyDataFlowAnalysis 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);
863 A.updateRange(SSDFA.getArgumentAccessRange(C.first.Callee,
864 C.first.ParamNo, C.second));
865 }
866
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}
880
882
885 : F(F), GetSE(GetSE) {}
886
888
890
892
894 if (!Info) {
895 StackSafetyLocalAnalysis SSLA(*F, GetSE());
896 Info.reset(new InfoTy{SSLA.run()});
897 }
898 return *Info;
899}
900
905
907 if (!Info) {
908 std::map<const GlobalValue *, FunctionInfo> Functions;
909 for (auto &F : M->functions()) {
910 if (.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
934 }
935 return *Info;
936}
937
938std::vectorFunctionSummary::ParamAccess
940
941
942 std::vectorFunctionSummary::ParamAccess ParamAccesses;
943 for (const auto &KV : getInfo().Info.Params) {
944 auto &PS = KV.second;
945
946
947
948 if (PS.Range.isFullSet())
949 continue;
950
951 ParamAccesses.emplace_back(KV.first, PS.Range);
953
954 Param.Calls.reserve(PS.Calls.size());
955 for (const auto &C : PS.Calls) {
956
957
958
959
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 }
972 return std::tie(L.ParamNo, L.Callee) < std::tie(R.ParamNo, R.Callee);
973 });
974 }
975 return ParamAccesses;
976}
977
979
983 : M(M), GetSSI(GetSSI), Index(Index) {
985 getInfo();
986}
987
989 default;
990
993
995
997 const auto &Info = getInfo();
998 return Info.SafeAllocas.count(&AI);
999}
1000
1002 const auto &Info = getInfo();
1003 return Info.UnsafeAccesses.find(&I) == Info.UnsafeAccesses.end();
1004}
1005
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 (.isDeclaration()) {
1013 SSI.find(&F)->second.print(O, F.getName(), &F);
1014 O << " safe accesses:"
1015 << "\n";
1020 (Call && Call->hasByValArgument())) &&
1022 O << " " << I << "\n";
1023 }
1024 }
1025 O << "\n";
1026 }
1027 }
1028}
1029
1031
1033
1040
1043 OS << "'Stack Safety Local Analysis' for function '" << F.getName() << "'\n";
1046}
1047
1049
1051
1056
1060
1066
1067AnalysisKey StackSafetyGlobalAnalysis::Key;
1068
1071
1074 return {&M,
1077 },
1078 nullptr};
1079}
1080
1083 OS << "'Stack Safety Analysis' for module '" << M.getName() << "'\n";
1086}
1087
1089
1092
1094
1096 const Module *M) const {
1097 SSGI.print(O);
1098}
1099
1105
1108 if (auto *IndexWrapperPass =
1110 ImportSummary = IndexWrapperPass->getIndex();
1111
1112 SSGI = {&M,
1115 },
1116 ImportSummary};
1117 return false;
1118}
1119
1122 return true;
1123 for (const auto &F : M.functions())
1124 if (F.hasFnAttribute(Attribute::SanitizeMemTag))
1125 return true;
1126 return false;
1127}
1128
1130 if (!Index.hasParamAccess())
1131 return;
1133
1134 auto CountParamAccesses = [&](auto &Stat) {
1136 return;
1137 for (auto &GVS : Index)
1138 for (auto &GV : GVS.second.getSummaryList())
1140 Stat += FS->paramAccesses().size();
1141 };
1142
1143 CountParamAccesses(NumCombinedParamAccessesBefore);
1144
1145 std::map<const FunctionSummary *, FunctionInfo> Functions;
1146
1147
1148 for (auto &GVS : Index) {
1149 for (auto &GV : GVS.second.getSummaryList()) {
1151 if (!FS || FS->paramAccesses().empty())
1152 continue;
1153 if (FS->isLive() && FS->isDSOLocal()) {
1154 FunctionInfo FI;
1155 for (const auto &PS : FS->paramAccesses()) {
1156 auto &US =
1157 FI.Params
1159 .first->second;
1160 US.Range = PS.Use;
1161 for (const auto &Call : PS.Calls) {
1164 findCalleeFunctionSummary(Call.Callee, FS->modulePath());
1165 ++NumCombinedCalleeLookupTotal;
1166 if (!S) {
1167 ++NumCombinedCalleeLookupFailed;
1168 US.Range = FullSet;
1169 US.Calls.clear();
1170 break;
1171 }
1173 Call.Offsets);
1174 }
1175 }
1176 Functions.emplace(FS, std::move(FI));
1177 }
1178
1179
1180
1181 FS->setParamAccesses({});
1182 }
1183 }
1184 NumCombinedDataFlowNodes += Functions.size();
1185 StackSafetyDataFlowAnalysis SSDFA(
1187 for (const auto &KV : SSDFA.run()) {
1188 std::vectorFunctionSummary::ParamAccess NewParams;
1189 NewParams.reserve(KV.second.Params.size());
1190 for (const auto &Param : KV.second.Params) {
1191
1192 if (Param.second.Range.isFullSet())
1193 continue;
1194 NewParams.emplace_back();
1196 New.ParamNo = Param.first;
1197 New.Use = Param.second.Range;
1198 }
1199 const_cast<FunctionSummary *>(KV.first)->setParamAccesses(
1200 std::move(NewParams));
1201 }
1202
1203 CountParamAccesses(NumCombinedParamAccessesAfter);
1204}
1205
1207static const char LocalPassName[] = "Stack Safety Local Analysis";
1209 false, true)
1213
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Analysis containing CSE Info
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This is the interface to build a ModuleSummaryIndex for a module.
ModuleSummaryIndex.h This file contains the declarations the classes that hold the module index and s...
FunctionAnalysisManager FAM
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
static const char LocalPassArg[]
Definition StackSafetyAnalysis.cpp:1206
static const char LocalPassName[]
Definition StackSafetyAnalysis.cpp:1207
static true const char GlobalPassName[]
Definition StackSafetyAnalysis.cpp:1214
static cl::opt< int > StackSafetyMaxIterations("stack-safety-max-iterations", cl::init(20), cl::Hidden)
static cl::opt< bool > StackSafetyRun("stack-safety-run", cl::init(false), cl::Hidden)
static cl::opt< bool > StackSafetyPrint("stack-safety-print", cl::init(false), cl::Hidden)
false
Definition StackSafetyAnalysis.cpp:1212
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Class for arbitrary precision integers.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
an instruction to allocate memory on the stack
PointerType * getType() const
Overload to return most specific pointer type.
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
LLVM_ABI bool isArrayAllocation() const
Return true if there is an allocation size parameter to the allocation instruction that is not 1.
const Value * getArraySize() const
Get the number of elements allocated.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
This class represents a function call, abstracting a target machine's calling convention.
This class represents a range of values.
LLVM_ABI bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
@ NeverOverflows
Never overflows.
LLVM_ABI ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
A parsed version of the target data layout string in and methods for querying it.
Function summary information to aid decisions and implementation of importing.
GlobalValueSummary * getBaseObject()
If this is an alias summary, returns the summary of the aliased object (a global variable or function...
static bool isLocalLinkage(LinkageTypes Linkage)
LLVM_ABI bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
static bool isLinkOnceLinkage(LinkageTypes Linkage)
static bool isAvailableExternallyLinkage(LinkageTypes Linkage)
LLVM_ABI const GlobalObject * getAliaseeObject() const
static bool isExternalLinkage(LinkageTypes Linkage)
LLVM_ABI bool isInterposable() const
Return true if this global's definition can be substituted with an arbitrary definition at link time ...
static bool isWeakLinkage(LinkageTypes Linkage)
Legacy wrapper pass to provide the ModuleSummaryIndex object.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this instruction belongs to.
This is the common base class for memset/memcpy/memmove.
Class to hold module path string table and global value map, and encapsulate methods for operating on...
A Module instance is used to store all the information related to an LLVM module.
AnalysisType & getAnalysis() const
getAnalysis() - This function is used by subclasses to get to the analysis information ...
AnalysisType * getAnalysisIfAvailable() const
getAnalysisIfAvailable() - Subclasses use this function to get analysis information tha...
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the default address space (address sp...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
This class represents an analyzed expression in the program.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
LLVM_ABI std::optional< bool > evaluatePredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
LLVM_ABI const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVMContext & getContext() const
void insert_range(Range &&R)
void clear()
Completely clear the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
value_type pop_back_val()
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
iterator erase(const_iterator CI)
void push_back(const T &Elt)
Compute live ranges of allocas.
bool isReachable(const Instruction *I) const
Returns true if instruction is reachable from entry.
bool isAliveAfter(const AllocaInst *AI, const Instruction *I) const
Returns true if the alloca is alive after the instruction.
StackSafetyInfo wrapper for the new pass manager.
StackSafetyInfo run(Function &F, FunctionAnalysisManager &AM)
Definition StackSafetyAnalysis.cpp:1034
This pass performs the global (interprocedural) stack safety analysis (new pass manager).
Result run(Module &M, ModuleAnalysisManager &AM)
Definition StackSafetyAnalysis.cpp:1070
This pass performs the global (interprocedural) stack safety analysis (legacy pass manager).
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
Definition StackSafetyAnalysis.cpp:1106
StackSafetyGlobalInfoWrapperPass()
Definition StackSafetyAnalysis.cpp:1090
~StackSafetyGlobalInfoWrapperPass() override
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition StackSafetyAnalysis.cpp:1100
void print(raw_ostream &O, const Module *M) const override
print - Print out the internal state of the pass.
Definition StackSafetyAnalysis.cpp:1095
void print(raw_ostream &O) const
Definition StackSafetyAnalysis.cpp:1006
bool stackAccessIsSafe(const Instruction &I) const
Definition StackSafetyAnalysis.cpp:1001
void dump() const
Definition StackSafetyAnalysis.cpp:1030
bool isSafe(const AllocaInst &AI) const
Definition StackSafetyAnalysis.cpp:996
StackSafetyGlobalInfo & operator=(StackSafetyGlobalInfo &&)
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition StackSafetyAnalysis.cpp:1081
StackSafetyInfo wrapper for the legacy pass manager.
void print(raw_ostream &O, const Module *M) const override
print - Print out the internal state of the pass.
Definition StackSafetyAnalysis.cpp:1057
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition StackSafetyAnalysis.cpp:1061
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition StackSafetyAnalysis.cpp:1052
StackSafetyInfoWrapperPass()
Definition StackSafetyAnalysis.cpp:1050
Interface to access stack safety analysis results for single function.
void print(raw_ostream &O) const
Definition StackSafetyAnalysis.cpp:901
const InfoTy & getInfo() const
Definition StackSafetyAnalysis.cpp:893
StackSafetyInfo & operator=(StackSafetyInfo &&)
std::vector< FunctionSummary::ParamAccess > getParamAccesses(ModuleSummaryIndex &Index) const
Parameters use for a FunctionSummary.
Definition StackSafetyAnalysis.cpp:939
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition StackSafetyAnalysis.cpp:1041
The instances of the Type class are immutable: once they are created, they are never changed.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
constexpr ScalarTy getFixedValue() const
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
This class implements an extremely fast bulk output stream that can only output to a stream.
@ C
The default llvm calling convention, compatible with C.
Offsets
Offsets in bytes from the start of the input buffer.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
constexpr uint64_t PointerSize
aarch64 pointer size.
NodeAddr< UseNode * > Use
This is an optimization pass for GlobalISel generic memory operations.
FunctionAddr VTableAddr Value
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
decltype(auto) dyn_cast(const From &Val)
dyn_cast - Return the argument parameter cast to the specified type.
void generateParamAccessSummary(ModuleSummaryIndex &Index)
Definition StackSafetyAnalysis.cpp:1129
bool needsParamAccessSummary(const Module &M)
Definition StackSafetyAnalysis.cpp:1120
InnerAnalysisManagerProxy< FunctionAnalysisManager, Module > FunctionAnalysisManagerModuleProxy
Provide the FunctionAnalysisManager to Module proxy.
auto unique(Range &&R, Predicate P)
auto formatv(bool Validate, const char *Fmt, Ts &&...Vals)
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LLVM_ABI bool AreStatisticsEnabled()
Check if statistics are enabled.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
decltype(auto) cast(const From &Val)
cast - Return the argument parameter cast to the specified type.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
AnalysisManager< Module > ModuleAnalysisManager
Convenience typedef for the Module analysis manager.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
GVToSSI Info
Definition StackSafetyAnalysis.cpp:230
std::set< const Instruction * > UnsafeAccesses
Definition StackSafetyAnalysis.cpp:232
SmallPtrSet< const AllocaInst *, 8 > SafeAllocas
Definition StackSafetyAnalysis.cpp:231
FunctionInfo< GlobalValue > Info
Definition StackSafetyAnalysis.cpp:226
A special type used by analysis passes to provide an address that identifies that particular analysis...
Describes the use of a value in a call instruction, specifying the call's target, the value's paramet...
Describes the uses of a parameter by the function.
static constexpr uint32_t RangeWidth