summaryrefslogtreecommitdiff
path: root/llvm/lib/Transforms/IPO/SCCP.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Transforms/IPO/SCCP.cpp')
-rw-r--r--llvm/lib/Transforms/IPO/SCCP.cpp473
1 files changed, 377 insertions, 96 deletions
diff --git a/llvm/lib/Transforms/IPO/SCCP.cpp b/llvm/lib/Transforms/IPO/SCCP.cpp
index 0453af184a72..5c1582ddfdae 100644
--- a/llvm/lib/Transforms/IPO/SCCP.cpp
+++ b/llvm/lib/Transforms/IPO/SCCP.cpp
@@ -11,31 +11,394 @@
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/IPO/SCCP.h"
+#include "llvm/ADT/SetVector.h"
#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Analysis/ValueLattice.h"
+#include "llvm/Analysis/ValueLatticeUtils.h"
+#include "llvm/Analysis/ValueTracking.h"
#include "llvm/InitializePasses.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ModRef.h"
#include "llvm/Transforms/IPO.h"
+#include "llvm/Transforms/IPO/FunctionSpecialization.h"
#include "llvm/Transforms/Scalar/SCCP.h"
+#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SCCPSolver.h"
using namespace llvm;
+#define DEBUG_TYPE "sccp"
+
+STATISTIC(NumInstRemoved, "Number of instructions removed");
+STATISTIC(NumArgsElimed ,"Number of arguments constant propagated");
+STATISTIC(NumGlobalConst, "Number of globals found to be constant");
+STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
+STATISTIC(NumInstReplaced,
+ "Number of instructions replaced with (simpler) instruction");
+
+static cl::opt<unsigned> FuncSpecializationMaxIters(
+ "func-specialization-max-iters", cl::init(1), cl::Hidden, cl::desc(
+ "The maximum number of iterations function specialization is run"));
+
+static void findReturnsToZap(Function &F,
+ SmallVector<ReturnInst *, 8> &ReturnsToZap,
+ SCCPSolver &Solver) {
+ // We can only do this if we know that nothing else can call the function.
+ if (!Solver.isArgumentTrackedFunction(&F))
+ return;
+
+ if (Solver.mustPreserveReturn(&F)) {
+ LLVM_DEBUG(
+ dbgs()
+ << "Can't zap returns of the function : " << F.getName()
+ << " due to present musttail or \"clang.arc.attachedcall\" call of "
+ "it\n");
+ return;
+ }
+
+ assert(
+ all_of(F.users(),
+ [&Solver](User *U) {
+ if (isa<Instruction>(U) &&
+ !Solver.isBlockExecutable(cast<Instruction>(U)->getParent()))
+ return true;
+ // Non-callsite uses are not impacted by zapping. Also, constant
+ // uses (like blockaddresses) could stuck around, without being
+ // used in the underlying IR, meaning we do not have lattice
+ // values for them.
+ if (!isa<CallBase>(U))
+ return true;
+ if (U->getType()->isStructTy()) {
+ return all_of(Solver.getStructLatticeValueFor(U),
+ [](const ValueLatticeElement &LV) {
+ return !SCCPSolver::isOverdefined(LV);
+ });
+ }
+
+ // We don't consider assume-like intrinsics to be actual address
+ // captures.
+ if (auto *II = dyn_cast<IntrinsicInst>(U)) {
+ if (II->isAssumeLikeIntrinsic())
+ return true;
+ }
+
+ return !SCCPSolver::isOverdefined(Solver.getLatticeValueFor(U));
+ }) &&
+ "We can only zap functions where all live users have a concrete value");
+
+ for (BasicBlock &BB : F) {
+ if (CallInst *CI = BB.getTerminatingMustTailCall()) {
+ LLVM_DEBUG(dbgs() << "Can't zap return of the block due to present "
+ << "musttail call : " << *CI << "\n");
+ (void)CI;
+ return;
+ }
+
+ if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
+ if (!isa<UndefValue>(RI->getOperand(0)))
+ ReturnsToZap.push_back(RI);
+ }
+}
+
+static bool runIPSCCP(
+ Module &M, const DataLayout &DL, FunctionAnalysisManager *FAM,
+ std::function<const TargetLibraryInfo &(Function &)> GetTLI,
+ std::function<TargetTransformInfo &(Function &)> GetTTI,
+ std::function<AssumptionCache &(Function &)> GetAC,
+ function_ref<AnalysisResultsForFn(Function &)> getAnalysis,
+ bool IsFuncSpecEnabled) {
+ SCCPSolver Solver(DL, GetTLI, M.getContext());
+ FunctionSpecializer Specializer(Solver, M, FAM, GetTLI, GetTTI, GetAC);
+
+ // Loop over all functions, marking arguments to those with their addresses
+ // taken or that are external as overdefined.
+ for (Function &F : M) {
+ if (F.isDeclaration())
+ continue;
+
+ Solver.addAnalysis(F, getAnalysis(F));
+
+ // Determine if we can track the function's return values. If so, add the
+ // function to the solver's set of return-tracked functions.
+ if (canTrackReturnsInterprocedurally(&F))
+ Solver.addTrackedFunction(&F);
+
+ // Determine if we can track the function's arguments. If so, add the
+ // function to the solver's set of argument-tracked functions.
+ if (canTrackArgumentsInterprocedurally(&F)) {
+ Solver.addArgumentTrackedFunction(&F);
+ continue;
+ }
+
+ // Assume the function is called.
+ Solver.markBlockExecutable(&F.front());
+
+ // Assume nothing about the incoming arguments.
+ for (Argument &AI : F.args())
+ Solver.markOverdefined(&AI);
+ }
+
+ // Determine if we can track any of the module's global variables. If so, add
+ // the global variables we can track to the solver's set of tracked global
+ // variables.
+ for (GlobalVariable &G : M.globals()) {
+ G.removeDeadConstantUsers();
+ if (canTrackGlobalVariableInterprocedurally(&G))
+ Solver.trackValueOfGlobalVariable(&G);
+ }
+
+ // Solve for constants.
+ Solver.solveWhileResolvedUndefsIn(M);
+
+ if (IsFuncSpecEnabled) {
+ unsigned Iters = 0;
+ while (Iters++ < FuncSpecializationMaxIters && Specializer.run());
+ }
+
+ // Iterate over all of the instructions in the module, replacing them with
+ // constants if we have found them to be of constant values.
+ bool MadeChanges = false;
+ for (Function &F : M) {
+ if (F.isDeclaration())
+ continue;
+
+ SmallVector<BasicBlock *, 512> BlocksToErase;
+
+ if (Solver.isBlockExecutable(&F.front())) {
+ bool ReplacedPointerArg = false;
+ for (Argument &Arg : F.args()) {
+ if (!Arg.use_empty() && Solver.tryToReplaceWithConstant(&Arg)) {
+ ReplacedPointerArg |= Arg.getType()->isPointerTy();
+ ++NumArgsElimed;
+ }
+ }
+
+ // If we replaced an argument, we may now also access a global (currently
+ // classified as "other" memory). Update memory attribute to reflect this.
+ if (ReplacedPointerArg) {
+ auto UpdateAttrs = [&](AttributeList AL) {
+ MemoryEffects ME = AL.getMemoryEffects();
+ if (ME == MemoryEffects::unknown())
+ return AL;
+
+ ME |= MemoryEffects(MemoryEffects::Other,
+ ME.getModRef(MemoryEffects::ArgMem));
+ return AL.addFnAttribute(
+ F.getContext(),
+ Attribute::getWithMemoryEffects(F.getContext(), ME));
+ };
+
+ F.setAttributes(UpdateAttrs(F.getAttributes()));
+ for (User *U : F.users()) {
+ auto *CB = dyn_cast<CallBase>(U);
+ if (!CB || CB->getCalledFunction() != &F)
+ continue;
+
+ CB->setAttributes(UpdateAttrs(CB->getAttributes()));
+ }
+ }
+ MadeChanges |= ReplacedPointerArg;
+ }
+
+ SmallPtrSet<Value *, 32> InsertedValues;
+ for (BasicBlock &BB : F) {
+ if (!Solver.isBlockExecutable(&BB)) {
+ LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB);
+ ++NumDeadBlocks;
+
+ MadeChanges = true;
+
+ if (&BB != &F.front())
+ BlocksToErase.push_back(&BB);
+ continue;
+ }
+
+ MadeChanges |= Solver.simplifyInstsInBlock(
+ BB, InsertedValues, NumInstRemoved, NumInstReplaced);
+ }
+
+ DomTreeUpdater DTU = IsFuncSpecEnabled && Specializer.isClonedFunction(&F)
+ ? DomTreeUpdater(DomTreeUpdater::UpdateStrategy::Lazy)
+ : Solver.getDTU(F);
+
+ // Change dead blocks to unreachable. We do it after replacing constants
+ // in all executable blocks, because changeToUnreachable may remove PHI
+ // nodes in executable blocks we found values for. The function's entry
+ // block is not part of BlocksToErase, so we have to handle it separately.
+ for (BasicBlock *BB : BlocksToErase) {
+ NumInstRemoved += changeToUnreachable(BB->getFirstNonPHI(),
+ /*PreserveLCSSA=*/false, &DTU);
+ }
+ if (!Solver.isBlockExecutable(&F.front()))
+ NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(),
+ /*PreserveLCSSA=*/false, &DTU);
+
+ BasicBlock *NewUnreachableBB = nullptr;
+ for (BasicBlock &BB : F)
+ MadeChanges |= Solver.removeNonFeasibleEdges(&BB, DTU, NewUnreachableBB);
+
+ for (BasicBlock *DeadBB : BlocksToErase)
+ if (!DeadBB->hasAddressTaken())
+ DTU.deleteBB(DeadBB);
+
+ for (BasicBlock &BB : F) {
+ for (Instruction &Inst : llvm::make_early_inc_range(BB)) {
+ if (Solver.getPredicateInfoFor(&Inst)) {
+ if (auto *II = dyn_cast<IntrinsicInst>(&Inst)) {
+ if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
+ Value *Op = II->getOperand(0);
+ Inst.replaceAllUsesWith(Op);
+ Inst.eraseFromParent();
+ }
+ }
+ }
+ }
+ }
+ }
+
+ // If we inferred constant or undef return values for a function, we replaced
+ // all call uses with the inferred value. This means we don't need to bother
+ // actually returning anything from the function. Replace all return
+ // instructions with return undef.
+ //
+ // Do this in two stages: first identify the functions we should process, then
+ // actually zap their returns. This is important because we can only do this
+ // if the address of the function isn't taken. In cases where a return is the
+ // last use of a function, the order of processing functions would affect
+ // whether other functions are optimizable.
+ SmallVector<ReturnInst*, 8> ReturnsToZap;
+
+ for (const auto &I : Solver.getTrackedRetVals()) {
+ Function *F = I.first;
+ const ValueLatticeElement &ReturnValue = I.second;
+
+ // If there is a known constant range for the return value, add !range
+ // metadata to the function's call sites.
+ if (ReturnValue.isConstantRange() &&
+ !ReturnValue.getConstantRange().isSingleElement()) {
+ // Do not add range metadata if the return value may include undef.
+ if (ReturnValue.isConstantRangeIncludingUndef())
+ continue;
+
+ auto &CR = ReturnValue.getConstantRange();
+ for (User *User : F->users()) {
+ auto *CB = dyn_cast<CallBase>(User);
+ if (!CB || CB->getCalledFunction() != F)
+ continue;
+
+ // Limit to cases where the return value is guaranteed to be neither
+ // poison nor undef. Poison will be outside any range and currently
+ // values outside of the specified range cause immediate undefined
+ // behavior.
+ if (!isGuaranteedNotToBeUndefOrPoison(CB, nullptr, CB))
+ continue;
+
+ // Do not touch existing metadata for now.
+ // TODO: We should be able to take the intersection of the existing
+ // metadata and the inferred range.
+ if (CB->getMetadata(LLVMContext::MD_range))
+ continue;
+
+ LLVMContext &Context = CB->getParent()->getContext();
+ Metadata *RangeMD[] = {
+ ConstantAsMetadata::get(ConstantInt::get(Context, CR.getLower())),
+ ConstantAsMetadata::get(ConstantInt::get(Context, CR.getUpper()))};
+ CB->setMetadata(LLVMContext::MD_range, MDNode::get(Context, RangeMD));
+ }
+ continue;
+ }
+ if (F->getReturnType()->isVoidTy())
+ continue;
+ if (SCCPSolver::isConstant(ReturnValue) || ReturnValue.isUnknownOrUndef())
+ findReturnsToZap(*F, ReturnsToZap, Solver);
+ }
+
+ for (auto *F : Solver.getMRVFunctionsTracked()) {
+ assert(F->getReturnType()->isStructTy() &&
+ "The return type should be a struct");
+ StructType *STy = cast<StructType>(F->getReturnType());
+ if (Solver.isStructLatticeConstant(F, STy))
+ findReturnsToZap(*F, ReturnsToZap, Solver);
+ }
+
+ // Zap all returns which we've identified as zap to change.
+ SmallSetVector<Function *, 8> FuncZappedReturn;
+ for (ReturnInst *RI : ReturnsToZap) {
+ Function *F = RI->getParent()->getParent();
+ RI->setOperand(0, UndefValue::get(F->getReturnType()));
+ // Record all functions that are zapped.
+ FuncZappedReturn.insert(F);
+ }
+
+ // Remove the returned attribute for zapped functions and the
+ // corresponding call sites.
+ for (Function *F : FuncZappedReturn) {
+ for (Argument &A : F->args())
+ F->removeParamAttr(A.getArgNo(), Attribute::Returned);
+ for (Use &U : F->uses()) {
+ CallBase *CB = dyn_cast<CallBase>(U.getUser());
+ if (!CB) {
+ assert(isa<BlockAddress>(U.getUser()) ||
+ (isa<Constant>(U.getUser()) &&
+ all_of(U.getUser()->users(), [](const User *UserUser) {
+ return cast<IntrinsicInst>(UserUser)->isAssumeLikeIntrinsic();
+ })));
+ continue;
+ }
+
+ for (Use &Arg : CB->args())
+ CB->removeParamAttr(CB->getArgOperandNo(&Arg), Attribute::Returned);
+ }
+ }
+
+ // If we inferred constant or undef values for globals variables, we can
+ // delete the global and any stores that remain to it.
+ for (const auto &I : make_early_inc_range(Solver.getTrackedGlobals())) {
+ GlobalVariable *GV = I.first;
+ if (SCCPSolver::isOverdefined(I.second))
+ continue;
+ LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName()
+ << "' is constant!\n");
+ while (!GV->use_empty()) {
+ StoreInst *SI = cast<StoreInst>(GV->user_back());
+ SI->eraseFromParent();
+ MadeChanges = true;
+ }
+ M.getGlobalList().erase(GV);
+ ++NumGlobalConst;
+ }
+
+ return MadeChanges;
+}
+
PreservedAnalyses IPSCCPPass::run(Module &M, ModuleAnalysisManager &AM) {
const DataLayout &DL = M.getDataLayout();
auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
auto GetTLI = [&FAM](Function &F) -> const TargetLibraryInfo & {
return FAM.getResult<TargetLibraryAnalysis>(F);
};
- auto getAnalysis = [&FAM](Function &F) -> AnalysisResultsForFn {
+ auto GetTTI = [&FAM](Function &F) -> TargetTransformInfo & {
+ return FAM.getResult<TargetIRAnalysis>(F);
+ };
+ auto GetAC = [&FAM](Function &F) -> AssumptionCache & {
+ return FAM.getResult<AssumptionAnalysis>(F);
+ };
+ auto getAnalysis = [&FAM, this](Function &F) -> AnalysisResultsForFn {
DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);
return {
std::make_unique<PredicateInfo>(F, DT, FAM.getResult<AssumptionAnalysis>(F)),
- &DT, FAM.getCachedResult<PostDominatorTreeAnalysis>(F)};
+ &DT, FAM.getCachedResult<PostDominatorTreeAnalysis>(F),
+ isFuncSpecEnabled() ? &FAM.getResult<LoopAnalysis>(F) : nullptr };
};
- if (!runIPSCCP(M, DL, GetTLI, getAnalysis))
+ if (!runIPSCCP(M, DL, &FAM, GetTLI, GetTTI, GetAC, getAnalysis,
+ isFuncSpecEnabled()))
return PreservedAnalyses::all();
PreservedAnalyses PA;
@@ -67,6 +430,12 @@ public:
auto GetTLI = [this](Function &F) -> const TargetLibraryInfo & {
return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
};
+ auto GetTTI = [this](Function &F) -> TargetTransformInfo & {
+ return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
+ };
+ auto GetAC = [this](Function &F) -> AssumptionCache & {
+ return this->getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
+ };
auto getAnalysis = [this](Function &F) -> AnalysisResultsForFn {
DominatorTree &DT =
this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
@@ -75,17 +444,19 @@ public:
F, DT,
this->getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F)),
- nullptr, // We cannot preserve the DT or PDT with the legacy pass
- nullptr}; // manager, so set them to nullptr.
+ nullptr, // We cannot preserve the LI, DT or PDT with the legacy pass
+ nullptr, // manager, so set them to nullptr.
+ nullptr};
};
- return runIPSCCP(M, DL, GetTLI, getAnalysis);
+ return runIPSCCP(M, DL, nullptr, GetTLI, GetTTI, GetAC, getAnalysis, false);
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<AssumptionCacheTracker>();
AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<TargetLibraryInfoWrapperPass>();
+ AU.addRequired<TargetTransformInfoWrapperPass>();
}
};
@@ -106,93 +477,3 @@ INITIALIZE_PASS_END(IPSCCPLegacyPass, "ipsccp",
// createIPSCCPPass - This is the public interface to this file.
ModulePass *llvm::createIPSCCPPass() { return new IPSCCPLegacyPass(); }
-PreservedAnalyses FunctionSpecializationPass::run(Module &M,
- ModuleAnalysisManager &AM) {
- const DataLayout &DL = M.getDataLayout();
- auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
- auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
- return FAM.getResult<TargetLibraryAnalysis>(F);
- };
- auto GetTTI = [&FAM](Function &F) -> TargetTransformInfo & {
- return FAM.getResult<TargetIRAnalysis>(F);
- };
- auto GetAC = [&FAM](Function &F) -> AssumptionCache & {
- return FAM.getResult<AssumptionAnalysis>(F);
- };
- auto GetAnalysis = [&FAM](Function &F) -> AnalysisResultsForFn {
- DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);
- return {std::make_unique<PredicateInfo>(
- F, DT, FAM.getResult<AssumptionAnalysis>(F)),
- &DT, FAM.getCachedResult<PostDominatorTreeAnalysis>(F)};
- };
-
- if (!runFunctionSpecialization(M, DL, GetTLI, GetTTI, GetAC, GetAnalysis))
- return PreservedAnalyses::all();
-
- PreservedAnalyses PA;
- PA.preserve<DominatorTreeAnalysis>();
- PA.preserve<PostDominatorTreeAnalysis>();
- PA.preserve<FunctionAnalysisManagerModuleProxy>();
- return PA;
-}
-
-namespace {
-struct FunctionSpecializationLegacyPass : public ModulePass {
- static char ID; // Pass identification, replacement for typeid
- FunctionSpecializationLegacyPass() : ModulePass(ID) {}
-
- void getAnalysisUsage(AnalysisUsage &AU) const override {
- AU.addRequired<AssumptionCacheTracker>();
- AU.addRequired<DominatorTreeWrapperPass>();
- AU.addRequired<TargetLibraryInfoWrapperPass>();
- AU.addRequired<TargetTransformInfoWrapperPass>();
- }
-
- bool runOnModule(Module &M) override {
- if (skipModule(M))
- return false;
-
- const DataLayout &DL = M.getDataLayout();
- auto GetTLI = [this](Function &F) -> TargetLibraryInfo & {
- return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
- };
- auto GetTTI = [this](Function &F) -> TargetTransformInfo & {
- return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
- };
- auto GetAC = [this](Function &F) -> AssumptionCache & {
- return this->getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
- };
-
- auto GetAnalysis = [this](Function &F) -> AnalysisResultsForFn {
- DominatorTree &DT =
- this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
- return {
- std::make_unique<PredicateInfo>(
- F, DT,
- this->getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
- F)),
- nullptr, // We cannot preserve the DT or PDT with the legacy pass
- nullptr}; // manager, so set them to nullptr.
- };
- return runFunctionSpecialization(M, DL, GetTLI, GetTTI, GetAC, GetAnalysis);
- }
-};
-} // namespace
-
-char FunctionSpecializationLegacyPass::ID = 0;
-
-INITIALIZE_PASS_BEGIN(
- FunctionSpecializationLegacyPass, "function-specialization",
- "Propagate constant arguments by specializing the function", false, false)
-
-INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
-INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
-INITIALIZE_PASS_END(FunctionSpecializationLegacyPass, "function-specialization",
- "Propagate constant arguments by specializing the function",
- false, false)
-
-ModulePass *llvm::createFunctionSpecializationPass() {
- return new FunctionSpecializationLegacyPass();
-}
generated by cgit v1.3 (git 2.53.0) at 2026-05-13 22:33:31 +0000