LLVM 18.0.0git
SCCP.cpp
Go to the documentation of this file.
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
20#include "llvm/ADT/DenseMap.h"
21#include "llvm/ADT/MapVector.h"
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/ADT/SetVector.h"
26#include "llvm/ADT/Statistic.h"
31#include "llvm/IR/BasicBlock.h"
32#include "llvm/IR/Constant.h"
34#include "llvm/IR/Function.h"
36#include "llvm/IR/InstrTypes.h"
37#include "llvm/IR/Instruction.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"
46#include "llvm/Support/Debug.h"
52#include <cassert>
53#include <utility>
54#include <vector>
55
56using namespace llvm;
57
58#define DEBUG_TYPE "sccp"
59
60STATISTIC(NumInstRemoved, "Number of instructions removed");
61STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
62STATISTIC(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.
67static 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
127 const DataLayout &DL = F.getParent()->getDataLayout();
128 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
131 if (!runSCCP(F, DL, &TLI, DTU))
132 return PreservedAnalyses::all();
133
134 auto PA = PreservedAnalyses();
135 PA.preserve<DominatorTreeAnalysis>();
136 return PA;
137}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
This is the interface for a simple mod/ref and alias analysis over globals.
#define F(x, y, z)
Definition: MD5.cpp:55
This file implements a map that provides insertion order iteration.
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
This file contains some templates that are useful if you are working with the STL at all.
static bool runSCCP(Function &F, const DataLayout &DL, const TargetLibraryInfo *TLI, DomTreeUpdater &DTU)
Definition: SCCP.cpp:67
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:793
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: SCCP.cpp:126
SCCPSolver - This interface class is a general purpose solver for Sparse Conditional Constant Propaga...
Definition: SCCPSolver.h:65
void solve()
Solve - Solve for constants and executable blocks.
bool resolvedUndefsIn(Function &F)
resolvedUndefsIn - While solving the dataflow for a function, we assume that branches on undef values...
bool simplifyInstsInBlock(BasicBlock &BB, SmallPtrSetImpl< Value * > &InsertedValues, Statistic &InstRemovedStat, Statistic &InstReplacedStat)
Definition: SCCPSolver.cpp:210
bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU, BasicBlock *&NewUnreachableBB) const
Definition: SCCPSolver.cpp:234
bool isBlockExecutable(BasicBlock *BB) const
bool markBlockExecutable(BasicBlock *BB)
markBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...
void markOverdefined(Value *V)
markOverdefined - Mark the specified value overdefined.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:2396