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/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 track
68 // return values so we can infer attributes.
69 if (canTrackReturnsInterprocedurally(F: &F))
70 Solver.addTrackedFunction(F: &F);
71
72 // Mark the first block of the function as being executable.
73 Solver.markBlockExecutable(BB: &F.front());
74
75 // Initialize arguments based on attributes.
76 for (Argument &AI : F.args())
77 Solver.trackValueOfArgument(V: &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: &BB)) {
97 LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB);
98 ++NumDeadBlocks;
99 BlocksToErase.push_back(Elt: &BB);
100 MadeChanges = true;
101 continue;
102 }
103
104 MadeChanges |= Solver.simplifyInstsInBlock(BB, InsertedValues,
105 InstRemovedStat&: NumInstRemoved, InstReplacedStat&: 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(I: &*DeadBB->getFirstNonPHIIt(),
112 /*PreserveLCSSA=*/false, DTU: &DTU);
113
114 BasicBlock *NewUnreachableBB = nullptr;
115 for (BasicBlock &BB : F)
116 MadeChanges |= Solver.removeNonFeasibleEdges(BB: &BB, DTU, NewUnreachableBB);
117
118 for (BasicBlock *DeadBB : BlocksToErase)
119 if (!DeadBB->hasAddressTaken())
120 DTU.deleteBB(DelBB: 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>(IR&: F);
132 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
133 auto &AC = AM.getResult<AssumptionAnalysis>(IR&: F);
134 if (!runSCCP(F, DL, TLI: &TLI, DT, AC))
135 return PreservedAnalyses::all();
136
137 auto PA = PreservedAnalyses();
138 PA.preserve<DominatorTreeAnalysis>();
139 return PA;
140}
141