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