diff options
Diffstat (limited to 'llvm/lib/Transforms/Scalar/ConstraintElimination.cpp')
| -rw-r--r-- | llvm/lib/Transforms/Scalar/ConstraintElimination.cpp | 116 |
1 files changed, 109 insertions, 7 deletions
diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp index 1ddb8ae9518f..4acc3f2d8469 100644 --- a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp +++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp @@ -19,9 +19,11 @@ #include "llvm/Analysis/ConstraintSystem.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DebugInfo.h" @@ -170,10 +172,12 @@ struct State { DominatorTree &DT; LoopInfo &LI; ScalarEvolution &SE; + TargetLibraryInfo &TLI; SmallVector<FactOrCheck, 64> WorkList; - State(DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE) - : DT(DT), LI(LI), SE(SE) {} + State(DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, + TargetLibraryInfo &TLI) + : DT(DT), LI(LI), SE(SE), TLI(TLI) {} /// Process block \p BB and add known facts to work-list. void addInfoFor(BasicBlock &BB); @@ -1109,10 +1113,54 @@ void State::addInfoForInductions(BasicBlock &BB) { } } +static bool getConstraintFromMemoryAccess(GetElementPtrInst &GEP, + uint64_t AccessSize, + CmpPredicate &Pred, Value *&A, + Value *&B, const DataLayout &DL, + const TargetLibraryInfo &TLI) { + auto Offset = collectOffsets(cast<GEPOperator>(GEP), DL); + if (!Offset.NW.hasNoUnsignedWrap()) + return false; + + if (Offset.VariableOffsets.size() != 1) + return false; + + uint64_t BitWidth = Offset.ConstantOffset.getBitWidth(); + auto &[Index, Scale] = Offset.VariableOffsets.front(); + // Bail out on non-canonical GEPs. + if (Index->getType()->getScalarSizeInBits() != BitWidth) + return false; + + ObjectSizeOpts Opts; + // Workaround for gep inbounds, ptr null, idx. + Opts.NullIsUnknownSize = true; + // Be conservative since we are not clear on whether an out of bounds access + // to the padding is UB or not. + Opts.RoundToAlign = true; + std::optional<TypeSize> Size = + getBaseObjectSize(Offset.BasePtr, DL, &TLI, Opts); + if (!Size || Size->isScalable()) + return false; + + // Index * Scale + ConstOffset + AccessSize <= AllocSize + // With nuw flag, we know that the index addition doesn't have unsigned wrap. + // If (AllocSize - (ConstOffset + AccessSize)) wraps around, there is no valid + // value for Index. + APInt MaxIndex = (APInt(BitWidth, Size->getFixedValue() - AccessSize, + /*isSigned=*/false, /*implicitTrunc=*/true) - + Offset.ConstantOffset) + .udiv(Scale); + Pred = ICmpInst::ICMP_ULE; + A = Index; + B = ConstantInt::get(Index->getType(), MaxIndex); + return true; +} + void State::addInfoFor(BasicBlock &BB) { addInfoForInductions(BB); + auto &DL = BB.getDataLayout(); - // True as long as long as the current instruction is guaranteed to execute. + // True as long as the current instruction is guaranteed to execute. bool GuaranteedToExecute = true; // Queue conditions and assumes. for (Instruction &I : BB) { @@ -1127,6 +1175,38 @@ void State::addInfoFor(BasicBlock &BB) { continue; } + auto AddFactFromMemoryAccess = [&](Value *Ptr, Type *AccessType) { + auto *GEP = dyn_cast<GetElementPtrInst>(Ptr); + if (!GEP) + return; + TypeSize AccessSize = DL.getTypeStoreSize(AccessType); + if (!AccessSize.isFixed()) + return; + if (GuaranteedToExecute) { + CmpPredicate Pred; + Value *A, *B; + if (getConstraintFromMemoryAccess(*GEP, AccessSize.getFixedValue(), + Pred, A, B, DL, TLI)) { + // The memory access is guaranteed to execute when BB is entered, + // hence the constraint holds on entry to BB. + WorkList.emplace_back(FactOrCheck::getConditionFact( + DT.getNode(I.getParent()), Pred, A, B)); + } + } else { + WorkList.emplace_back( + FactOrCheck::getInstFact(DT.getNode(I.getParent()), &I)); + } + }; + + if (auto *LI = dyn_cast<LoadInst>(&I)) { + if (!LI->isVolatile()) + AddFactFromMemoryAccess(LI->getPointerOperand(), LI->getAccessType()); + } + if (auto *SI = dyn_cast<StoreInst>(&I)) { + if (!SI->isVolatile()) + AddFactFromMemoryAccess(SI->getPointerOperand(), SI->getAccessType()); + } + auto *II = dyn_cast<IntrinsicInst>(&I); Intrinsic::ID ID = II ? II->getIntrinsicID() : Intrinsic::not_intrinsic; switch (ID) { @@ -1420,7 +1500,7 @@ static std::optional<bool> checkCondition(CmpInst::Predicate Pred, Value *A, LLVM_DEBUG(dbgs() << "Checking " << *CheckInst << "\n"); auto R = Info.getConstraintForSolving(Pred, A, B); - if (R.empty() || !R.isValid(Info)){ + if (R.empty() || !R.isValid(Info)) { LLVM_DEBUG(dbgs() << " failed to decompose condition\n"); return std::nullopt; } @@ -1785,12 +1865,13 @@ tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info, static bool eliminateConstraints(Function &F, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, - OptimizationRemarkEmitter &ORE) { + OptimizationRemarkEmitter &ORE, + TargetLibraryInfo &TLI) { bool Changed = false; DT.updateDFSNumbers(); SmallVector<Value *> FunctionArgs(llvm::make_pointer_range(F.args())); ConstraintInfo Info(F.getDataLayout(), FunctionArgs); - State S(DT, LI, SE); + State S(DT, LI, SE, TLI); std::unique_ptr<Module> ReproducerModule( DumpReproducers ? new Module(F.getName(), F.getContext()) : nullptr); @@ -1960,6 +2041,26 @@ static bool eliminateConstraints(Function &F, DominatorTree &DT, LoopInfo &LI, } continue; } + + auto &DL = F.getDataLayout(); + auto AddFactsAboutIndices = [&](Value *Ptr, Type *AccessType) { + CmpPredicate Pred; + Value *A, *B; + if (getConstraintFromMemoryAccess( + *cast<GetElementPtrInst>(Ptr), + DL.getTypeStoreSize(AccessType).getFixedValue(), Pred, A, B, DL, + TLI)) + AddFact(Pred, A, B); + }; + + if (auto *LI = dyn_cast<LoadInst>(CB.Inst)) { + AddFactsAboutIndices(LI->getPointerOperand(), LI->getAccessType()); + continue; + } + if (auto *SI = dyn_cast<StoreInst>(CB.Inst)) { + AddFactsAboutIndices(SI->getPointerOperand(), SI->getAccessType()); + continue; + } } Value *A = nullptr, *B = nullptr; @@ -2018,7 +2119,8 @@ PreservedAnalyses ConstraintEliminationPass::run(Function &F, auto &LI = AM.getResult<LoopAnalysis>(F); auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F); auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F); - if (!eliminateConstraints(F, DT, LI, SE, ORE)) + auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); + if (!eliminateConstraints(F, DT, LI, SE, ORE, TLI)) return PreservedAnalyses::all(); PreservedAnalyses PA; |