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/DenseMap.h"
21 #include "llvm/ADT/MapVector.h"
22 #include "llvm/ADT/STLExtras.h"
23 #include "llvm/ADT/SetVector.h"
24 #include "llvm/ADT/SmallPtrSet.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/Statistic.h"
27 #include "llvm/Analysis/DomTreeUpdater.h"
28 #include "llvm/Analysis/GlobalsModRef.h"
29 #include "llvm/Analysis/TargetLibraryInfo.h"
30 #include "llvm/Analysis/ValueTracking.h"
31 #include "llvm/IR/BasicBlock.h"
32 #include "llvm/IR/Constant.h"
33 #include "llvm/IR/DerivedTypes.h"
34 #include "llvm/IR/Function.h"
35 #include "llvm/IR/GlobalVariable.h"
36 #include "llvm/IR/InstrTypes.h"
37 #include "llvm/IR/Instruction.h"
38 #include "llvm/IR/Instructions.h"
39 #include "llvm/IR/Module.h"
40 #include "llvm/IR/PassManager.h"
41 #include "llvm/IR/Type.h"
42 #include "llvm/IR/User.h"
43 #include "llvm/IR/Value.h"
44 #include "llvm/Pass.h"
45 #include "llvm/Support/Casting.h"
46 #include "llvm/Support/Debug.h"
47 #include "llvm/Support/ErrorHandling.h"
48 #include "llvm/Support/raw_ostream.h"
49 #include "llvm/Transforms/Scalar.h"
50 #include "llvm/Transforms/Utils/Local.h"
51 #include "llvm/Transforms/Utils/SCCPSolver.h"
52 #include <cassert>
53 #include <utility>
54 #include <vector>
55 
56 using namespace llvm;
57 
58 #define DEBUG_TYPE "sccp"
59 
60 STATISTIC(NumInstRemoved, "Number of instructions removed");
61 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
62 STATISTIC(NumInstReplaced,
63           "Number of instructions replaced with (simpler) instruction");
64 
65 // runSCCP() - Run the Sparse Conditional Constant Propagation algorithm,
66 // and return true if the function was modified.
67 static bool runSCCP(Function &F, const DataLayout &DL,
68                     const TargetLibraryInfo *TLI, DomTreeUpdater &DTU) {
69   LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");
70   SCCPSolver Solver(
71       DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; },
72       F.getContext());
73 
74   // Mark the first block of the function as being executable.
75   Solver.markBlockExecutable(&F.front());
76 
77   // Mark all arguments to the function as being overdefined.
78   for (Argument &AI : F.args())
79     Solver.markOverdefined(&AI);
80 
81   // Solve for constants.
82   bool ResolvedUndefs = true;
83   while (ResolvedUndefs) {
84     Solver.solve();
85     LLVM_DEBUG(dbgs() << "RESOLVING UNDEFs\n");
86     ResolvedUndefs = Solver.resolvedUndefsIn(F);
87   }
88 
89   bool MadeChanges = false;
90 
91   // If we decided that there are basic blocks that are dead in this function,
92   // delete their contents now.  Note that we cannot actually delete the blocks,
93   // as we cannot modify the CFG of the function.
94 
95   SmallPtrSet<Value *, 32> InsertedValues;
96   SmallVector<BasicBlock *, 8> BlocksToErase;
97   for (BasicBlock &BB : F) {
98     if (!Solver.isBlockExecutable(&BB)) {
99       LLVM_DEBUG(dbgs() << "  BasicBlock Dead:" << BB);
100       ++NumDeadBlocks;
101       BlocksToErase.push_back(&BB);
102       MadeChanges = true;
103       continue;
104     }
105 
106     MadeChanges |= Solver.simplifyInstsInBlock(BB, InsertedValues,
107                                                NumInstRemoved, NumInstReplaced);
108   }
109 
110   // Remove unreachable blocks and non-feasible edges.
111   for (BasicBlock *DeadBB : BlocksToErase)
112     NumInstRemoved += changeToUnreachable(DeadBB->getFirstNonPHI(),
113                                           /*PreserveLCSSA=*/false, &DTU);
114 
115   BasicBlock *NewUnreachableBB = nullptr;
116   for (BasicBlock &BB : F)
117     MadeChanges |= Solver.removeNonFeasibleEdges(&BB, DTU, NewUnreachableBB);
118 
119   for (BasicBlock *DeadBB : BlocksToErase)
120     if (!DeadBB->hasAddressTaken())
121       DTU.deleteBB(DeadBB);
122 
123   return MadeChanges;
124 }
125 
126 PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) {
127   const DataLayout &DL = F.getParent()->getDataLayout();
128   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
129   auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
130   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
131   if (!runSCCP(F, DL, &TLI, DTU))
132     return PreservedAnalyses::all();
133 
134   auto PA = PreservedAnalyses();
135   PA.preserve<DominatorTreeAnalysis>();
136   return PA;
137 }
138