diff --git a/llvm/lib/Analysis/StackSafetyAnalysis.cpp b/llvm/lib/Analysis/StackSafetyAnalysis.cpp --- a/llvm/lib/Analysis/StackSafetyAnalysis.cpp +++ b/llvm/lib/Analysis/StackSafetyAnalysis.cpp @@ -14,6 +14,7 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/ModuleSummaryAnalysis.h" +#include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/StackLifetime.h" #include "llvm/IR/ConstantRange.h" @@ -117,7 +118,7 @@ // Access range if the address (alloca or parameters). // It is allowed to be empty-set when there are no known accesses. ConstantRange Range; - std::map Accesses; + std::map AccessIsUnsafe; // List of calls which pass address as an argument. // Value is offset range of address from base address (alloca or calling @@ -131,10 +132,8 @@ UseInfo(unsigned PointerSize) : Range{PointerSize, false} {} void updateRange(const ConstantRange &R) { Range = unionNoWrap(Range, R); } - void addRange(const Instruction *I, const ConstantRange &R) { - auto Ins = Accesses.emplace(I, R); - if (!Ins.second) - Ins.first->second = unionNoWrap(Ins.first->second, R); + void addRange(const Instruction *I, const ConstantRange &R, bool IsSafe) { + AccessIsUnsafe[I] |= !IsSafe; updateRange(R); } }; @@ -253,6 +252,11 @@ void analyzeAllUses(Value *Ptr, UseInfo &AS, const StackLifetime &SL); + const SCEV *toCharPtr(const SCEV *V); + const SCEV *getTypeSize(TypeSize TS); + bool isSafeAccess(const Use &UI, AllocaInst *AI, const Instruction *I, + const SCEV *AccessSize); + public: StackSafetyLocalAnalysis(Function &F, ScalarEvolution &SE) : F(F), DL(F.getParent()->getDataLayout()), SE(SE), @@ -333,6 +337,41 @@ return getAccessRange(U, Base, SizeRange); } +const SCEV *StackSafetyLocalAnalysis::getTypeSize(TypeSize TS) { + if (TS.isScalable()) + return SE.getCouldNotCompute(); + auto *PtrTy = IntegerType::getInt8PtrTy(SE.getContext()); + return SE.getConstant(PtrTy, TS.getFixedSize()); +} + +const SCEV *StackSafetyLocalAnalysis::toCharPtr(const SCEV *V) { + auto *PtrTy = IntegerType::getInt8PtrTy(SE.getContext()); + return SE.getTruncateOrZeroExtend(V, PtrTy); +} + +bool StackSafetyLocalAnalysis::isSafeAccess(const Use &UI, AllocaInst *AI, + const Instruction *I, + const SCEV *AccessSize) { + if (!AI || isa(AccessSize)) + return false; + + const SCEV *AddrExp = toCharPtr(SE.getSCEV(UI.get())); + const SCEV *BaseExp = toCharPtr(SE.getSCEV(AI)); + const SCEV *Diff = SE.getMinusSCEV(AddrExp, BaseExp); + if (isa(Diff)) + return false; + + auto Size = getStaticAllocaSizeRange(*AI); + + const SCEV *Min = toCharPtr(SE.getConstant(Size.getLower())); + const SCEV *Max = SE.getMinusSCEV(toCharPtr(SE.getConstant(Size.getUpper())), + toCharPtr(AccessSize)); + return SE.evaluatePredicateAt(ICmpInst::Predicate::ICMP_SGE, Diff, Min, I) + .getValueOr(false) && + SE.evaluatePredicateAt(ICmpInst::Predicate::ICMP_SLE, Diff, Max, I) + .getValueOr(false); +} + /// The function analyzes all local uses of Ptr (alloca or argument) and /// calculates local access range and all function calls where it was used. void StackSafetyLocalAnalysis::analyzeAllUses(Value *Ptr, @@ -341,7 +380,7 @@ SmallPtrSet Visited; SmallVector WorkList; WorkList.push_back(Ptr); - const AllocaInst *AI = dyn_cast(Ptr); + AllocaInst *AI = dyn_cast(Ptr); // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc. while (!WorkList.empty()) { @@ -356,11 +395,13 @@ switch (I->getOpcode()) { case Instruction::Load: { if (AI && !SL.isAliveAfter(AI, I)) { - US.addRange(I, UnknownRange); + US.addRange(I, UnknownRange, false); break; } - US.addRange(I, - getAccessRange(UI, Ptr, DL.getTypeStoreSize(I->getType()))); + auto TypeSize = DL.getTypeStoreSize(I->getType()); + auto AccessRange = getAccessRange(UI, Ptr, TypeSize); + US.addRange(I, AccessRange, + isSafeAccess(UI, AI, I, getTypeSize(TypeSize))); break; } @@ -370,16 +411,17 @@ case Instruction::Store: { if (V == I->getOperand(0)) { // Stored the pointer - conservatively assume it may be unsafe. - US.addRange(I, UnknownRange); + US.addRange(I, UnknownRange, false); break; } if (AI && !SL.isAliveAfter(AI, I)) { - US.addRange(I, UnknownRange); + US.addRange(I, UnknownRange, false); break; } - US.addRange( - I, getAccessRange( - UI, Ptr, DL.getTypeStoreSize(I->getOperand(0)->getType()))); + auto TypeSize = DL.getTypeStoreSize(I->getOperand(0)->getType()); + auto AccessRange = getAccessRange(UI, Ptr, TypeSize); + US.addRange(I, AccessRange, + isSafeAccess(UI, AI, I, getTypeSize(TypeSize))); break; } @@ -387,7 +429,7 @@ // Information leak. // FIXME: Process parameters correctly. This is a leak only if we return // alloca. - US.addRange(I, UnknownRange); + US.addRange(I, UnknownRange, false); break; case Instruction::Call: @@ -396,12 +438,13 @@ break; if (AI && !SL.isAliveAfter(AI, I)) { - US.addRange(I, UnknownRange); + US.addRange(I, UnknownRange, false); break; } - if (const MemIntrinsic *MI = dyn_cast(I)) { - US.addRange(I, getMemIntrinsicAccessRange(MI, UI, Ptr)); + auto AccessRange = getMemIntrinsicAccessRange(MI, UI, Ptr); + US.addRange(I, AccessRange, + isSafeAccess(UI, AI, I, SE.getSCEV(MI->getLength()))); break; } @@ -412,15 +455,16 @@ } if (!CB.isArgOperand(&UI)) { - US.addRange(I, UnknownRange); + US.addRange(I, UnknownRange, false); break; } unsigned ArgNo = CB.getArgOperandNo(&UI); if (CB.isByValArgument(ArgNo)) { - US.addRange(I, getAccessRange( - UI, Ptr, - DL.getTypeStoreSize(CB.getParamByValType(ArgNo)))); + auto TypeSize = DL.getTypeStoreSize(CB.getParamByValType(ArgNo)); + auto AccessRange = getAccessRange(UI, Ptr, TypeSize); + US.addRange(I, AccessRange, + isSafeAccess(UI, AI, I, getTypeSize(TypeSize))); break; } @@ -430,7 +474,7 @@ const GlobalValue *Callee = dyn_cast(CB.getCalledOperand()->stripPointerCasts()); if (!Callee) { - US.addRange(I, UnknownRange); + US.addRange(I, UnknownRange, false); break; } @@ -827,8 +871,8 @@ Info->SafeAllocas.insert(AI); ++NumAllocaStackSafe; } - for (const auto &A : KV.second.Accesses) - Info->AccessIsUnsafe[A.first] |= !AIRange.contains(A.second); + for (const auto &A : KV.second.AccessIsUnsafe) + Info->AccessIsUnsafe[A.first] |= A.second; } } diff --git a/llvm/test/Analysis/StackSafetyAnalysis/local.ll b/llvm/test/Analysis/StackSafetyAnalysis/local.ll --- a/llvm/test/Analysis/StackSafetyAnalysis/local.ll +++ b/llvm/test/Analysis/StackSafetyAnalysis/local.ll @@ -44,6 +44,53 @@ ret void } +define void @StoreInBoundsCond(i64 %i) { +; CHECK-LABEL: @StoreInBoundsCond dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; CHECK-NEXT: x[4]: full-set{{$}} +; GLOBAL-NEXT: safe accesses: +; GLOBAL-NEXT: store i8 0, i8* %x2, align 1 +; CHECK-EMPTY: +entry: + %x = alloca i32, align 4 + %x1 = bitcast i32* %x to i8* + %c1 = icmp sge i64 %i, 0 + %c2 = icmp slt i64 %i, 4 + br i1 %c1, label %c1.true, label %false + +c1.true: + br i1 %c2, label %c2.true, label %false + +c2.true: + %x2 = getelementptr i8, i8* %x1, i64 %i + store i8 0, i8* %x2, align 1 + br label %false + +false: + ret void +} + +define void @StoreInBoundsMinMax(i64 %i) { +; CHECK-LABEL: @StoreInBoundsMinMax dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; CHECK-NEXT: x[4]: [0,4){{$}} +; GLOBAL-NEXT: safe accesses: +; GLOBAL-NEXT: store i8 0, i8* %x2, align 1 +; CHECK-EMPTY: +entry: + %x = alloca i32, align 4 + %x1 = bitcast i32* %x to i8* + %c1 = icmp sge i64 %i, 0 + %i1 = select i1 %c1, i64 %i, i64 0 + %c2 = icmp slt i64 %i1, 3 + %i2 = select i1 %c2, i64 %i1, i64 3 + %x2 = getelementptr i8, i8* %x1, i64 %i2 + store i8 0, i8* %x2, align 1 + ret void +} + define void @StoreInBounds2() { ; CHECK-LABEL: @StoreInBounds2 dso_preemptable{{$}} ; CHECK-NEXT: args uses: @@ -157,6 +204,54 @@ ret void } +define void @StoreOutOfBoundsCond(i64 %i) { +; CHECK-LABEL: @StoreOutOfBoundsCond dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; CHECK-NEXT: x[4]: full-set{{$}} +; GLOBAL-NEXT: safe accesses: +; CHECK-EMPTY: +entry: + %x = alloca i32, align 4 + %x1 = bitcast i32* %x to i8* + %c1 = icmp sge i64 %i, 0 + %c2 = icmp slt i64 %i, 5 + br i1 %c1, label %c1.true, label %false + +c1.true: + br i1 %c2, label %c2.true, label %false + +c2.true: + %x2 = getelementptr i8, i8* %x1, i64 %i + store i8 0, i8* %x2, align 1 + br label %false + +false: + ret void +} + +define void @StoreOutOfBoundsCond2(i64 %i) { +; CHECK-LABEL: @StoreOutOfBoundsCond2 dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; CHECK-NEXT: x[4]: full-set{{$}} +; GLOBAL-NEXT: safe accesses: +; CHECK-EMPTY: +entry: + %x = alloca i32, align 4 + %x1 = bitcast i32* %x to i8* + %c2 = icmp slt i64 %i, 5 + br i1 %c2, label %c2.true, label %false + +c2.true: + %x2 = getelementptr i8, i8* %x1, i64 %i + store i8 0, i8* %x2, align 1 + br label %false + +false: + ret void +} + define void @StoreOutOfBounds2() { ; CHECK-LABEL: @StoreOutOfBounds2 dso_preemptable{{$}} ; CHECK-NEXT: args uses: