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-exception 6 // 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 35 using namespace llvm; 36 37 #define DEBUG_TYPE "sccp" 38 39 STATISTIC(NumInstRemoved, "Number of instructions removed"); 40 STATISTIC(NumArgsElimed ,"Number of arguments constant propagated"); 41 STATISTIC(NumGlobalConst, "Number of globals found to be constant"); 42 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable"); 43 STATISTIC(NumInstReplaced, 44 "Number of instructions replaced with (simpler) instruction"); 45 46 static 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 50 static 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, constant 73 // uses (like blockaddresses) could stuck around, without being 74 // used in the underlying IR, meaning we do not have lattice 75 // values for them. 76 if (!isa<CallBase>(U)) 77 return true; 78 if (U->getType()->isStructTy()) { 79 return all_of(Solver.getStructLatticeValueFor(U), 80 [](const ValueLatticeElement &LV) { 81 return !SCCPSolver::isOverdefined(LV); 82 }); 83 } 84 85 // We don't consider assume-like intrinsics to be actual address 86 // captures. 87 if (auto *II = dyn_cast<IntrinsicInst>(U)) { 88 if (II->isAssumeLikeIntrinsic()) 89 return true; 90 } 91 92 return !SCCPSolver::isOverdefined(Solver.getLatticeValueFor(U)); 93 }) && 94 "We can only zap functions where all live users have a concrete value"); 95 96 for (BasicBlock &BB : F) { 97 if (CallInst *CI = BB.getTerminatingMustTailCall()) { 98 LLVM_DEBUG(dbgs() << "Can't zap return of the block due to present " 99 << "musttail call : " << *CI << "\n"); 100 (void)CI; 101 return; 102 } 103 104 if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator())) 105 if (!isa<UndefValue>(RI->getOperand(0))) 106 ReturnsToZap.push_back(RI); 107 } 108 } 109 110 static bool runIPSCCP( 111 Module &M, const DataLayout &DL, FunctionAnalysisManager *FAM, 112 std::function<const TargetLibraryInfo &(Function &)> GetTLI, 113 std::function<TargetTransformInfo &(Function &)> GetTTI, 114 std::function<AssumptionCache &(Function &)> GetAC, 115 std::function<DominatorTree &(Function &)> GetDT, 116 std::function<BlockFrequencyInfo &(Function &)> GetBFI, 117 bool IsFuncSpecEnabled) { 118 SCCPSolver Solver(DL, GetTLI, M.getContext()); 119 FunctionSpecializer Specializer(Solver, M, FAM, GetBFI, GetTLI, GetTTI, 120 GetAC); 121 122 // Loop over all functions, marking arguments to those with their addresses 123 // taken or that are external as overdefined. 124 for (Function &F : M) { 125 if (F.isDeclaration()) 126 continue; 127 128 DominatorTree &DT = GetDT(F); 129 AssumptionCache &AC = GetAC(F); 130 Solver.addPredicateInfo(F, DT, AC); 131 132 // Determine if we can track the function's return values. If so, add the 133 // function to the solver's set of return-tracked functions. 134 if (canTrackReturnsInterprocedurally(&F)) 135 Solver.addTrackedFunction(&F); 136 137 // Determine if we can track the function's arguments. If so, add the 138 // function to the solver's set of argument-tracked functions. 139 if (canTrackArgumentsInterprocedurally(&F)) { 140 Solver.addArgumentTrackedFunction(&F); 141 continue; 142 } 143 144 // Assume the function is called. 145 Solver.markBlockExecutable(&F.front()); 146 147 // Assume nothing about the incoming arguments. 148 for (Argument &AI : F.args()) 149 Solver.markOverdefined(&AI); 150 } 151 152 // Determine if we can track any of the module's global variables. If so, add 153 // the global variables we can track to the solver's set of tracked global 154 // variables. 155 for (GlobalVariable &G : M.globals()) { 156 G.removeDeadConstantUsers(); 157 if (canTrackGlobalVariableInterprocedurally(&G)) 158 Solver.trackValueOfGlobalVariable(&G); 159 } 160 161 // Solve for constants. 162 Solver.solveWhileResolvedUndefsIn(M); 163 164 if (IsFuncSpecEnabled) { 165 unsigned Iters = 0; 166 while (Iters++ < FuncSpecMaxIters && Specializer.run()); 167 } 168 169 // Iterate over all of the instructions in the module, replacing them with 170 // constants if we have found them to be of constant values. 171 bool MadeChanges = false; 172 for (Function &F : M) { 173 if (F.isDeclaration()) 174 continue; 175 176 SmallVector<BasicBlock *, 512> BlocksToErase; 177 178 if (Solver.isBlockExecutable(&F.front())) { 179 bool ReplacedPointerArg = false; 180 for (Argument &Arg : F.args()) { 181 if (!Arg.use_empty() && Solver.tryToReplaceWithConstant(&Arg)) { 182 ReplacedPointerArg |= Arg.getType()->isPointerTy(); 183 ++NumArgsElimed; 184 } 185 } 186 187 // If we replaced an argument, we may now also access a global (currently 188 // classified as "other" memory). Update memory attribute to reflect this. 189 if (ReplacedPointerArg) { 190 auto UpdateAttrs = [&](AttributeList AL) { 191 MemoryEffects ME = AL.getMemoryEffects(); 192 if (ME == MemoryEffects::unknown()) 193 return AL; 194 195 ME |= MemoryEffects(IRMemLocation::Other, 196 ME.getModRef(IRMemLocation::ArgMem)); 197 return AL.addFnAttribute( 198 F.getContext(), 199 Attribute::getWithMemoryEffects(F.getContext(), ME)); 200 }; 201 202 F.setAttributes(UpdateAttrs(F.getAttributes())); 203 for (User *U : F.users()) { 204 auto *CB = dyn_cast<CallBase>(U); 205 if (!CB || CB->getCalledFunction() != &F) 206 continue; 207 208 CB->setAttributes(UpdateAttrs(CB->getAttributes())); 209 } 210 } 211 MadeChanges |= ReplacedPointerArg; 212 } 213 214 SmallPtrSet<Value *, 32> InsertedValues; 215 for (BasicBlock &BB : F) { 216 if (!Solver.isBlockExecutable(&BB)) { 217 LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB); 218 ++NumDeadBlocks; 219 220 MadeChanges = true; 221 222 if (&BB != &F.front()) 223 BlocksToErase.push_back(&BB); 224 continue; 225 } 226 227 MadeChanges |= Solver.simplifyInstsInBlock( 228 BB, InsertedValues, NumInstRemoved, NumInstReplaced); 229 } 230 231 DominatorTree *DT = FAM->getCachedResult<DominatorTreeAnalysis>(F); 232 PostDominatorTree *PDT = FAM->getCachedResult<PostDominatorTreeAnalysis>(F); 233 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy); 234 // Change dead blocks to unreachable. We do it after replacing constants 235 // in all executable blocks, because changeToUnreachable may remove PHI 236 // nodes in executable blocks we found values for. The function's entry 237 // block is not part of BlocksToErase, so we have to handle it separately. 238 for (BasicBlock *BB : BlocksToErase) { 239 NumInstRemoved += changeToUnreachable(BB->getFirstNonPHIOrDbg(), 240 /*PreserveLCSSA=*/false, &DTU); 241 } 242 if (!Solver.isBlockExecutable(&F.front())) 243 NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHIOrDbg(), 244 /*PreserveLCSSA=*/false, &DTU); 245 246 BasicBlock *NewUnreachableBB = nullptr; 247 for (BasicBlock &BB : F) 248 MadeChanges |= Solver.removeNonFeasibleEdges(&BB, DTU, NewUnreachableBB); 249 250 for (BasicBlock *DeadBB : BlocksToErase) 251 if (!DeadBB->hasAddressTaken()) 252 DTU.deleteBB(DeadBB); 253 254 for (BasicBlock &BB : F) { 255 for (Instruction &Inst : llvm::make_early_inc_range(BB)) { 256 if (Solver.getPredicateInfoFor(&Inst)) { 257 if (auto *II = dyn_cast<IntrinsicInst>(&Inst)) { 258 if (II->getIntrinsicID() == Intrinsic::ssa_copy) { 259 Value *Op = II->getOperand(0); 260 Inst.replaceAllUsesWith(Op); 261 Inst.eraseFromParent(); 262 } 263 } 264 } 265 } 266 } 267 } 268 269 // If we inferred constant or undef return values for a function, we replaced 270 // all call uses with the inferred value. This means we don't need to bother 271 // actually returning anything from the function. Replace all return 272 // instructions with return undef. 273 // 274 // Do this in two stages: first identify the functions we should process, then 275 // actually zap their returns. This is important because we can only do this 276 // if the address of the function isn't taken. In cases where a return is the 277 // last use of a function, the order of processing functions would affect 278 // whether other functions are optimizable. 279 SmallVector<ReturnInst*, 8> ReturnsToZap; 280 281 for (const auto &I : Solver.getTrackedRetVals()) { 282 Function *F = I.first; 283 const ValueLatticeElement &ReturnValue = I.second; 284 285 // If there is a known constant range for the return value, add !range 286 // metadata to the function's call sites. 287 if (ReturnValue.isConstantRange() && 288 !ReturnValue.getConstantRange().isSingleElement()) { 289 // Do not add range metadata if the return value may include undef. 290 if (ReturnValue.isConstantRangeIncludingUndef()) 291 continue; 292 293 auto &CR = ReturnValue.getConstantRange(); 294 for (User *User : F->users()) { 295 auto *CB = dyn_cast<CallBase>(User); 296 if (!CB || CB->getCalledFunction() != F) 297 continue; 298 299 // Do not touch existing metadata for now. 300 // TODO: We should be able to take the intersection of the existing 301 // metadata and the inferred range. 302 if (CB->getMetadata(LLVMContext::MD_range)) 303 continue; 304 305 LLVMContext &Context = CB->getParent()->getContext(); 306 Metadata *RangeMD[] = { 307 ConstantAsMetadata::get(ConstantInt::get(Context, CR.getLower())), 308 ConstantAsMetadata::get(ConstantInt::get(Context, CR.getUpper()))}; 309 CB->setMetadata(LLVMContext::MD_range, MDNode::get(Context, RangeMD)); 310 } 311 continue; 312 } 313 if (F->getReturnType()->isVoidTy()) 314 continue; 315 if (SCCPSolver::isConstant(ReturnValue) || ReturnValue.isUnknownOrUndef()) 316 findReturnsToZap(*F, ReturnsToZap, Solver); 317 } 318 319 for (auto *F : Solver.getMRVFunctionsTracked()) { 320 assert(F->getReturnType()->isStructTy() && 321 "The return type should be a struct"); 322 StructType *STy = cast<StructType>(F->getReturnType()); 323 if (Solver.isStructLatticeConstant(F, STy)) 324 findReturnsToZap(*F, ReturnsToZap, Solver); 325 } 326 327 // Zap all returns which we've identified as zap to change. 328 SmallSetVector<Function *, 8> FuncZappedReturn; 329 for (ReturnInst *RI : ReturnsToZap) { 330 Function *F = RI->getParent()->getParent(); 331 RI->setOperand(0, UndefValue::get(F->getReturnType())); 332 // Record all functions that are zapped. 333 FuncZappedReturn.insert(F); 334 } 335 336 // Remove the returned attribute for zapped functions and the 337 // corresponding call sites. 338 // Also remove any attributes that convert an undef return value into 339 // immediate undefined behavior 340 AttributeMask UBImplyingAttributes = 341 AttributeFuncs::getUBImplyingAttributes(); 342 for (Function *F : FuncZappedReturn) { 343 for (Argument &A : F->args()) 344 F->removeParamAttr(A.getArgNo(), Attribute::Returned); 345 F->removeRetAttrs(UBImplyingAttributes); 346 for (Use &U : F->uses()) { 347 CallBase *CB = dyn_cast<CallBase>(U.getUser()); 348 if (!CB) { 349 assert(isa<BlockAddress>(U.getUser()) || 350 (isa<Constant>(U.getUser()) && 351 all_of(U.getUser()->users(), [](const User *UserUser) { 352 return cast<IntrinsicInst>(UserUser)->isAssumeLikeIntrinsic(); 353 }))); 354 continue; 355 } 356 357 for (Use &Arg : CB->args()) 358 CB->removeParamAttr(CB->getArgOperandNo(&Arg), Attribute::Returned); 359 CB->removeRetAttrs(UBImplyingAttributes); 360 } 361 } 362 363 // If we inferred constant or undef values for globals variables, we can 364 // delete the global and any stores that remain to it. 365 for (const auto &I : make_early_inc_range(Solver.getTrackedGlobals())) { 366 GlobalVariable *GV = I.first; 367 if (SCCPSolver::isOverdefined(I.second)) 368 continue; 369 LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName() 370 << "' is constant!\n"); 371 while (!GV->use_empty()) { 372 StoreInst *SI = cast<StoreInst>(GV->user_back()); 373 SI->eraseFromParent(); 374 } 375 376 // Try to create a debug constant expression for the global variable 377 // initializer value. 378 SmallVector<DIGlobalVariableExpression *, 1> GVEs; 379 GV->getDebugInfo(GVEs); 380 if (GVEs.size() == 1) { 381 DIBuilder DIB(M); 382 if (DIExpression *InitExpr = getExpressionForConstant( 383 DIB, *GV->getInitializer(), *GV->getValueType())) 384 GVEs[0]->replaceOperandWith(1, InitExpr); 385 } 386 387 MadeChanges = true; 388 M.eraseGlobalVariable(GV); 389 ++NumGlobalConst; 390 } 391 392 return MadeChanges; 393 } 394 395 PreservedAnalyses IPSCCPPass::run(Module &M, ModuleAnalysisManager &AM) { 396 const DataLayout &DL = M.getDataLayout(); 397 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 398 auto GetTLI = [&FAM](Function &F) -> const TargetLibraryInfo & { 399 return FAM.getResult<TargetLibraryAnalysis>(F); 400 }; 401 auto GetTTI = [&FAM](Function &F) -> TargetTransformInfo & { 402 return FAM.getResult<TargetIRAnalysis>(F); 403 }; 404 auto GetAC = [&FAM](Function &F) -> AssumptionCache & { 405 return FAM.getResult<AssumptionAnalysis>(F); 406 }; 407 auto GetDT = [&FAM](Function &F) -> DominatorTree & { 408 return FAM.getResult<DominatorTreeAnalysis>(F); 409 }; 410 auto GetBFI = [&FAM](Function &F) -> BlockFrequencyInfo & { 411 return FAM.getResult<BlockFrequencyAnalysis>(F); 412 }; 413 414 415 if (!runIPSCCP(M, DL, &FAM, GetTLI, GetTTI, GetAC, GetDT, GetBFI, 416 isFuncSpecEnabled())) 417 return PreservedAnalyses::all(); 418 419 PreservedAnalyses PA; 420 PA.preserve<DominatorTreeAnalysis>(); 421 PA.preserve<PostDominatorTreeAnalysis>(); 422 PA.preserve<FunctionAnalysisManagerModuleProxy>(); 423 return PA; 424 } 425