396 lines · cpp
1//===-- SCCP.cpp ----------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements Interprocedural Sparse Conditional Constant Propagation.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/Transforms/IPO/SCCP.h"14#include "llvm/ADT/SetVector.h"15#include "llvm/Analysis/AssumptionCache.h"16#include "llvm/Analysis/BlockFrequencyInfo.h"17#include "llvm/Analysis/PostDominators.h"18#include "llvm/Analysis/TargetLibraryInfo.h"19#include "llvm/Analysis/TargetTransformInfo.h"20#include "llvm/Analysis/ValueLattice.h"21#include "llvm/Analysis/ValueLatticeUtils.h"22#include "llvm/Analysis/ValueTracking.h"23#include "llvm/IR/AttributeMask.h"24#include "llvm/IR/Constants.h"25#include "llvm/IR/DIBuilder.h"26#include "llvm/IR/IntrinsicInst.h"27#include "llvm/Support/CommandLine.h"28#include "llvm/Support/ModRef.h"29#include "llvm/Transforms/IPO.h"30#include "llvm/Transforms/IPO/FunctionSpecialization.h"31#include "llvm/Transforms/Scalar/SCCP.h"32#include "llvm/Transforms/Utils/Local.h"33#include "llvm/Transforms/Utils/SCCPSolver.h"34 35using namespace llvm;36 37#define DEBUG_TYPE "sccp"38 39STATISTIC(NumInstRemoved, "Number of instructions removed");40STATISTIC(NumArgsElimed ,"Number of arguments constant propagated");41STATISTIC(NumGlobalConst, "Number of globals found to be constant");42STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");43STATISTIC(NumInstReplaced,44 "Number of instructions replaced with (simpler) instruction");45 46static cl::opt<unsigned> FuncSpecMaxIters(47 "funcspec-max-iters", cl::init(10), cl::Hidden, cl::desc(48 "The maximum number of iterations function specialization is run"));49 50static void findReturnsToZap(Function &F,51 SmallVector<ReturnInst *, 8> &ReturnsToZap,52 SCCPSolver &Solver) {53 // We can only do this if we know that nothing else can call the function.54 if (!Solver.isArgumentTrackedFunction(&F))55 return;56 57 if (Solver.mustPreserveReturn(&F)) {58 LLVM_DEBUG(59 dbgs()60 << "Can't zap returns of the function : " << F.getName()61 << " due to present musttail or \"clang.arc.attachedcall\" call of "62 "it\n");63 return;64 }65 66 assert(67 all_of(F.users(),68 [&Solver](User *U) {69 if (isa<Instruction>(U) &&70 !Solver.isBlockExecutable(cast<Instruction>(U)->getParent()))71 return true;72 // Non-callsite uses are not impacted by zapping. Also, constant73 // uses (like blockaddresses) could stuck around, without being74 // used in the underlying IR, meaning we do not have lattice75 // values for them.76 if (!isa<CallBase>(U))77 return true;78 if (U->getType()->isStructTy()) {79 return none_of(Solver.getStructLatticeValueFor(U),80 SCCPSolver::isOverdefined);81 }82 83 // We don't consider assume-like intrinsics to be actual address84 // captures.85 if (auto *II = dyn_cast<IntrinsicInst>(U)) {86 if (II->isAssumeLikeIntrinsic())87 return true;88 }89 90 return !SCCPSolver::isOverdefined(Solver.getLatticeValueFor(U));91 }) &&92 "We can only zap functions where all live users have a concrete value");93 94 for (BasicBlock &BB : F) {95 if (CallInst *CI = BB.getTerminatingMustTailCall()) {96 LLVM_DEBUG(dbgs() << "Can't zap return of the block due to present "97 << "musttail call : " << *CI << "\n");98 (void)CI;99 return;100 }101 102 if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator()))103 if (!isa<UndefValue>(RI->getOperand(0)))104 ReturnsToZap.push_back(RI);105 }106}107 108static bool runIPSCCP(109 Module &M, const DataLayout &DL, FunctionAnalysisManager *FAM,110 std::function<const TargetLibraryInfo &(Function &)> GetTLI,111 std::function<TargetTransformInfo &(Function &)> GetTTI,112 std::function<AssumptionCache &(Function &)> GetAC,113 std::function<DominatorTree &(Function &)> GetDT,114 std::function<BlockFrequencyInfo &(Function &)> GetBFI,115 bool IsFuncSpecEnabled) {116 SCCPSolver Solver(DL, GetTLI, M.getContext());117 FunctionSpecializer Specializer(Solver, M, FAM, GetBFI, GetTLI, GetTTI,118 GetAC);119 120 // Loop over all functions, marking arguments to those with their addresses121 // taken or that are external as overdefined.122 for (Function &F : M) {123 if (F.isDeclaration())124 continue;125 126 DominatorTree &DT = GetDT(F);127 AssumptionCache &AC = GetAC(F);128 Solver.addPredicateInfo(F, DT, AC);129 130 // Determine if we can track the function's return values. If so, add the131 // function to the solver's set of return-tracked functions.132 if (canTrackReturnsInterprocedurally(&F))133 Solver.addTrackedFunction(&F);134 135 // Determine if we can track the function's arguments. If so, add the136 // function to the solver's set of argument-tracked functions.137 if (canTrackArgumentsInterprocedurally(&F)) {138 Solver.addArgumentTrackedFunction(&F);139 continue;140 }141 142 // Assume the function is called.143 Solver.markBlockExecutable(&F.front());144 145 for (Argument &AI : F.args())146 Solver.trackValueOfArgument(&AI);147 }148 149 // Determine if we can track any of the module's global variables. If so, add150 // the global variables we can track to the solver's set of tracked global151 // variables.152 for (GlobalVariable &G : M.globals()) {153 G.removeDeadConstantUsers();154 if (canTrackGlobalVariableInterprocedurally(&G))155 Solver.trackValueOfGlobalVariable(&G);156 }157 158 // Solve for constants.159 Solver.solveWhileResolvedUndefsIn(M);160 161 if (IsFuncSpecEnabled) {162 unsigned Iters = 0;163 while (Iters++ < FuncSpecMaxIters && Specializer.run());164 }165 166 // Iterate over all of the instructions in the module, replacing them with167 // constants if we have found them to be of constant values.168 bool MadeChanges = false;169 for (Function &F : M) {170 if (F.isDeclaration())171 continue;172 // Skip the dead functions marked by FunctionSpecializer, avoiding removing173 // blocks in dead functions. Set MadeChanges if there is any dead function174 // that will be removed later.175 if (IsFuncSpecEnabled && Specializer.isDeadFunction(&F)) {176 MadeChanges = true;177 continue;178 }179 180 SmallVector<BasicBlock *, 512> BlocksToErase;181 182 if (Solver.isBlockExecutable(&F.front())) {183 bool ReplacedPointerArg = false;184 for (Argument &Arg : F.args()) {185 if (!Arg.use_empty() && Solver.tryToReplaceWithConstant(&Arg)) {186 ReplacedPointerArg |= Arg.getType()->isPointerTy();187 ++NumArgsElimed;188 }189 }190 191 // If we replaced an argument, we may now also access a global (currently192 // classified as "other" memory). Update memory attribute to reflect this.193 if (ReplacedPointerArg) {194 auto UpdateAttrs = [&](AttributeList AL) {195 MemoryEffects ME = AL.getMemoryEffects();196 if (ME == MemoryEffects::unknown())197 return AL;198 199 ModRefInfo ArgMemMR = ME.getModRef(IRMemLocation::ArgMem);200 ME |= MemoryEffects(IRMemLocation::ErrnoMem, ArgMemMR);201 ME |= MemoryEffects(IRMemLocation::Other, ArgMemMR);202 203 return AL.addFnAttribute(204 F.getContext(),205 Attribute::getWithMemoryEffects(F.getContext(), ME));206 };207 208 F.setAttributes(UpdateAttrs(F.getAttributes()));209 for (User *U : F.users()) {210 auto *CB = dyn_cast<CallBase>(U);211 if (!CB || CB->getCalledFunction() != &F)212 continue;213 214 CB->setAttributes(UpdateAttrs(CB->getAttributes()));215 }216 }217 MadeChanges |= ReplacedPointerArg;218 }219 220 SmallPtrSet<Value *, 32> InsertedValues;221 for (BasicBlock &BB : F) {222 if (!Solver.isBlockExecutable(&BB)) {223 LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB);224 ++NumDeadBlocks;225 226 MadeChanges = true;227 228 if (&BB != &F.front())229 BlocksToErase.push_back(&BB);230 continue;231 }232 233 MadeChanges |= Solver.simplifyInstsInBlock(234 BB, InsertedValues, NumInstRemoved, NumInstReplaced);235 }236 237 DominatorTree *DT = FAM->getCachedResult<DominatorTreeAnalysis>(F);238 PostDominatorTree *PDT = FAM->getCachedResult<PostDominatorTreeAnalysis>(F);239 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);240 // Change dead blocks to unreachable. We do it after replacing constants241 // in all executable blocks, because changeToUnreachable may remove PHI242 // nodes in executable blocks we found values for. The function's entry243 // block is not part of BlocksToErase, so we have to handle it separately.244 for (BasicBlock *BB : BlocksToErase) {245 NumInstRemoved += changeToUnreachable(&*BB->getFirstNonPHIOrDbg(),246 /*PreserveLCSSA=*/false, &DTU);247 }248 if (!Solver.isBlockExecutable(&F.front()))249 NumInstRemoved += changeToUnreachable(&*F.front().getFirstNonPHIOrDbg(),250 /*PreserveLCSSA=*/false, &DTU);251 252 BasicBlock *NewUnreachableBB = nullptr;253 for (BasicBlock &BB : F)254 MadeChanges |= Solver.removeNonFeasibleEdges(&BB, DTU, NewUnreachableBB);255 256 for (BasicBlock *DeadBB : BlocksToErase)257 if (!DeadBB->hasAddressTaken())258 DTU.deleteBB(DeadBB);259 260 Solver.removeSSACopies(F);261 }262 263 // If we inferred constant or undef return values for a function, we replaced264 // all call uses with the inferred value. This means we don't need to bother265 // actually returning anything from the function. Replace all return266 // instructions with return undef.267 //268 // Do this in two stages: first identify the functions we should process, then269 // actually zap their returns. This is important because we can only do this270 // if the address of the function isn't taken. In cases where a return is the271 // last use of a function, the order of processing functions would affect272 // whether other functions are optimizable.273 SmallVector<ReturnInst*, 8> ReturnsToZap;274 275 Solver.inferReturnAttributes();276 Solver.inferArgAttributes();277 for (const auto &[F, ReturnValue] : Solver.getTrackedRetVals()) {278 assert(!F->getReturnType()->isVoidTy() &&279 "should not track void functions");280 if (SCCPSolver::isConstant(ReturnValue) || ReturnValue.isUnknownOrUndef())281 findReturnsToZap(*F, ReturnsToZap, Solver);282 }283 284 for (auto *F : Solver.getMRVFunctionsTracked()) {285 assert(F->getReturnType()->isStructTy() &&286 "The return type should be a struct");287 StructType *STy = cast<StructType>(F->getReturnType());288 if (Solver.isStructLatticeConstant(F, STy))289 findReturnsToZap(*F, ReturnsToZap, Solver);290 }291 292 // Zap all returns which we've identified as zap to change.293 SmallSetVector<Function *, 8> FuncZappedReturn;294 for (ReturnInst *RI : ReturnsToZap) {295 Function *F = RI->getParent()->getParent();296 RI->setOperand(0, PoisonValue::get(F->getReturnType()));297 // Record all functions that are zapped.298 FuncZappedReturn.insert(F);299 }300 301 // Remove the returned attribute for zapped functions and the302 // corresponding call sites.303 // Also remove any attributes that convert an undef return value into304 // immediate undefined behavior305 AttributeMask UBImplyingAttributes =306 AttributeFuncs::getUBImplyingAttributes();307 for (Function *F : FuncZappedReturn) {308 for (Argument &A : F->args())309 F->removeParamAttr(A.getArgNo(), Attribute::Returned);310 F->removeRetAttrs(UBImplyingAttributes);311 for (Use &U : F->uses()) {312 CallBase *CB = dyn_cast<CallBase>(U.getUser());313 if (!CB) {314 assert(isa<Constant>(U.getUser()) &&315 all_of(U.getUser()->users(), [](const User *UserUser) {316 return cast<IntrinsicInst>(UserUser)->isAssumeLikeIntrinsic();317 }));318 continue;319 }320 321 for (Use &Arg : CB->args())322 CB->removeParamAttr(CB->getArgOperandNo(&Arg), Attribute::Returned);323 CB->removeRetAttrs(UBImplyingAttributes);324 }325 }326 327 // If we inferred constant or undef values for globals variables, we can328 // delete the global and any stores that remain to it.329 for (const auto &I : make_early_inc_range(Solver.getTrackedGlobals())) {330 GlobalVariable *GV = I.first;331 if (SCCPSolver::isOverdefined(I.second))332 continue;333 LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName()334 << "' is constant!\n");335 for (User *U : make_early_inc_range(GV->users())) {336 // We can remove LoadInst here. The LoadInsts in dead functions marked by337 // FuncSpec are not simplified to constants, thus poison them.338 assert((isa<StoreInst>(U) || isa<LoadInst>(U)) &&339 "Only Store|Load Instruction can be user of GlobalVariable at "340 "reaching here.");341 Instruction *I = cast<Instruction>(U);342 if (isa<LoadInst>(I))343 I->replaceAllUsesWith(PoisonValue::get(I->getType()));344 I->eraseFromParent();345 }346 347 // Try to create a debug constant expression for the global variable348 // initializer value.349 SmallVector<DIGlobalVariableExpression *, 1> GVEs;350 GV->getDebugInfo(GVEs);351 if (GVEs.size() == 1) {352 DIBuilder DIB(M);353 if (DIExpression *InitExpr = getExpressionForConstant(354 DIB, *GV->getInitializer(), *GV->getValueType()))355 GVEs[0]->replaceOperandWith(1, InitExpr);356 }357 358 MadeChanges = true;359 M.eraseGlobalVariable(GV);360 ++NumGlobalConst;361 }362 363 return MadeChanges;364}365 366PreservedAnalyses IPSCCPPass::run(Module &M, ModuleAnalysisManager &AM) {367 const DataLayout &DL = M.getDataLayout();368 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();369 auto GetTLI = [&FAM](Function &F) -> const TargetLibraryInfo & {370 return FAM.getResult<TargetLibraryAnalysis>(F);371 };372 auto GetTTI = [&FAM](Function &F) -> TargetTransformInfo & {373 return FAM.getResult<TargetIRAnalysis>(F);374 };375 auto GetAC = [&FAM](Function &F) -> AssumptionCache & {376 return FAM.getResult<AssumptionAnalysis>(F);377 };378 auto GetDT = [&FAM](Function &F) -> DominatorTree & {379 return FAM.getResult<DominatorTreeAnalysis>(F);380 };381 auto GetBFI = [&FAM](Function &F) -> BlockFrequencyInfo & {382 return FAM.getResult<BlockFrequencyAnalysis>(F);383 };384 385 386 if (!runIPSCCP(M, DL, &FAM, GetTLI, GetTTI, GetAC, GetDT, GetBFI,387 isFuncSpecEnabled()))388 return PreservedAnalyses::all();389 390 PreservedAnalyses PA;391 PA.preserve<DominatorTreeAnalysis>();392 PA.preserve<PostDominatorTreeAnalysis>();393 PA.preserve<FunctionAnalysisManagerModuleProxy>();394 return PA;395}396