LLVM 19.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/STLExtras.h"
23#include "llvm/ADT/Statistic.h"
28#include "llvm/IR/BasicBlock.h"
29#include "llvm/IR/Constant.h"
31#include "llvm/IR/Function.h"
33#include "llvm/IR/InstrTypes.h"
34#include "llvm/IR/Instruction.h"
36#include "llvm/IR/Module.h"
37#include "llvm/IR/PassManager.h"
38#include "llvm/IR/Type.h"
39#include "llvm/IR/User.h"
40#include "llvm/IR/Value.h"
41#include "llvm/Pass.h"
43#include "llvm/Support/Debug.h"
49#include <utility>
50
51using namespace llvm;
52
53#define DEBUG_TYPE "sccp"
54
55STATISTIC(NumInstRemoved, "Number of instructions removed");
56STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
57STATISTIC(NumInstReplaced,
58 "Number of instructions replaced with (simpler) instruction");
59
60// runSCCP() - Run the Sparse Conditional Constant Propagation algorithm,
61// and return true if the function was modified.
62static bool runSCCP(Function &F, const DataLayout &DL,
63 const TargetLibraryInfo *TLI, DomTreeUpdater &DTU) {
64 LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");
65 SCCPSolver Solver(
66 DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; },
67 F.getContext());
68
69 // Mark the first block of the function as being executable.
70 Solver.markBlockExecutable(&F.front());
71
72 // Mark all arguments to the function as being overdefined.
73 for (Argument &AI : F.args())
74 Solver.markOverdefined(&AI);
75
76 // Solve for constants.
77 bool ResolvedUndefs = true;
78 while (ResolvedUndefs) {
79 Solver.solve();
80 LLVM_DEBUG(dbgs() << "RESOLVING UNDEFs\n");
81 ResolvedUndefs = Solver.resolvedUndefsIn(F);
82 }
83
84 bool MadeChanges = false;
85
86 // If we decided that there are basic blocks that are dead in this function,
87 // delete their contents now. Note that we cannot actually delete the blocks,
88 // as we cannot modify the CFG of the function.
89
90 SmallPtrSet<Value *, 32> InsertedValues;
91 SmallVector<BasicBlock *, 8> BlocksToErase;
92 for (BasicBlock &BB : F) {
93 if (!Solver.isBlockExecutable(&BB)) {
94 LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB);
95 ++NumDeadBlocks;
96 BlocksToErase.push_back(&BB);
97 MadeChanges = true;
98 continue;
99 }
100
101 MadeChanges |= Solver.simplifyInstsInBlock(BB, InsertedValues,
102 NumInstRemoved, NumInstReplaced);
103 }
104
105 // Remove unreachable blocks and non-feasible edges.
106 for (BasicBlock *DeadBB : BlocksToErase)
107 NumInstRemoved += changeToUnreachable(DeadBB->getFirstNonPHI(),
108 /*PreserveLCSSA=*/false, &DTU);
109
110 BasicBlock *NewUnreachableBB = nullptr;
111 for (BasicBlock &BB : F)
112 MadeChanges |= Solver.removeNonFeasibleEdges(&BB, DTU, NewUnreachableBB);
113
114 for (BasicBlock *DeadBB : BlocksToErase)
115 if (!DeadBB->hasAddressTaken())
116 DTU.deleteBB(DeadBB);
117
118 return MadeChanges;
119}
120
122 const DataLayout &DL = F.getParent()->getDataLayout();
123 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
126 if (!runSCCP(F, DL, &TLI, DTU))
127 return PreservedAnalyses::all();
128
129 auto PA = PreservedAnalyses();
130 PA.preserve<DominatorTreeAnalysis>();
131 return PA;
132}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This is the interface for a simple mod/ref and alias analysis over globals.
#define F(x, y, z)
Definition: MD5.cpp:55
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:62
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:348
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:519
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
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:275
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: SCCP.cpp:121
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:221
bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU, BasicBlock *&NewUnreachableBB) const
Definition: SCCPSolver.cpp:245
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:427
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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:2797