141 lines · cpp
1//===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===//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 sparse conditional constant propagation and merging:10//11// Specifically, this:12// * Assumes values are constant unless proven otherwise13// * Assumes BasicBlocks are dead unless proven otherwise14// * Proves values to be constant, and replaces them with constants15// * Proves conditional branches to be unconditional16//17//===----------------------------------------------------------------------===//18 19#include "llvm/Transforms/Scalar/SCCP.h"20#include "llvm/ADT/SmallPtrSet.h"21#include "llvm/ADT/SmallVector.h"22#include "llvm/ADT/Statistic.h"23#include "llvm/Analysis/AssumptionCache.h"24#include "llvm/Analysis/DomTreeUpdater.h"25#include "llvm/Analysis/GlobalsModRef.h"26#include "llvm/Analysis/TargetLibraryInfo.h"27#include "llvm/Analysis/ValueLatticeUtils.h"28#include "llvm/Analysis/ValueTracking.h"29#include "llvm/IR/BasicBlock.h"30#include "llvm/IR/DerivedTypes.h"31#include "llvm/IR/Function.h"32#include "llvm/IR/InstrTypes.h"33#include "llvm/IR/Instruction.h"34#include "llvm/IR/Instructions.h"35#include "llvm/IR/IntrinsicInst.h"36#include "llvm/IR/PassManager.h"37#include "llvm/IR/Type.h"38#include "llvm/IR/Value.h"39#include "llvm/Pass.h"40#include "llvm/Support/Debug.h"41#include "llvm/Support/raw_ostream.h"42#include "llvm/Transforms/Scalar.h"43#include "llvm/Transforms/Utils/Local.h"44#include "llvm/Transforms/Utils/SCCPSolver.h"45 46using namespace llvm;47 48#define DEBUG_TYPE "sccp"49 50STATISTIC(NumInstRemoved, "Number of instructions removed");51STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");52STATISTIC(NumInstReplaced,53 "Number of instructions replaced with (simpler) instruction");54 55// runSCCP() - Run the Sparse Conditional Constant Propagation algorithm,56// and return true if the function was modified.57static bool runSCCP(Function &F, const DataLayout &DL,58 const TargetLibraryInfo *TLI, DominatorTree &DT,59 AssumptionCache &AC) {60 LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");61 SCCPSolver Solver(62 DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; },63 F.getContext());64 65 Solver.addPredicateInfo(F, DT, AC);66 67 // While we don't do any actual inter-procedural analysis, still track68 // return values so we can infer attributes.69 if (canTrackReturnsInterprocedurally(&F))70 Solver.addTrackedFunction(&F);71 72 // Mark the first block of the function as being executable.73 Solver.markBlockExecutable(&F.front());74 75 // Initialize arguments based on attributes.76 for (Argument &AI : F.args())77 Solver.trackValueOfArgument(&AI);78 79 // Solve for constants.80 bool ResolvedUndefs = true;81 while (ResolvedUndefs) {82 Solver.solve();83 LLVM_DEBUG(dbgs() << "RESOLVING UNDEFs\n");84 ResolvedUndefs = Solver.resolvedUndefsIn(F);85 }86 87 bool MadeChanges = false;88 89 // If we decided that there are basic blocks that are dead in this function,90 // delete their contents now. Note that we cannot actually delete the blocks,91 // as we cannot modify the CFG of the function.92 93 SmallPtrSet<Value *, 32> InsertedValues;94 SmallVector<BasicBlock *, 8> BlocksToErase;95 for (BasicBlock &BB : F) {96 if (!Solver.isBlockExecutable(&BB)) {97 LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB);98 ++NumDeadBlocks;99 BlocksToErase.push_back(&BB);100 MadeChanges = true;101 continue;102 }103 104 MadeChanges |= Solver.simplifyInstsInBlock(BB, InsertedValues,105 NumInstRemoved, NumInstReplaced);106 }107 108 // Remove unreachable blocks and non-feasible edges.109 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);110 for (BasicBlock *DeadBB : BlocksToErase)111 NumInstRemoved += changeToUnreachable(&*DeadBB->getFirstNonPHIIt(),112 /*PreserveLCSSA=*/false, &DTU);113 114 BasicBlock *NewUnreachableBB = nullptr;115 for (BasicBlock &BB : F)116 MadeChanges |= Solver.removeNonFeasibleEdges(&BB, DTU, NewUnreachableBB);117 118 for (BasicBlock *DeadBB : BlocksToErase)119 if (!DeadBB->hasAddressTaken())120 DTU.deleteBB(DeadBB);121 122 Solver.removeSSACopies(F);123 124 Solver.inferReturnAttributes();125 126 return MadeChanges;127}128 129PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) {130 const DataLayout &DL = F.getDataLayout();131 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);132 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);133 auto &AC = AM.getResult<AssumptionAnalysis>(F);134 if (!runSCCP(F, DL, &TLI, DT, AC))135 return PreservedAnalyses::all();136 137 auto PA = PreservedAnalyses();138 PA.preserve<DominatorTreeAnalysis>();139 return PA;140}141