1
//===-- IPConstantPropagation.cpp - Propagate constants through calls -----===//
3
// The LLVM Compiler Infrastructure
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
8
//===----------------------------------------------------------------------===//
10
// This pass implements an _extremely_ simple interprocedural constant
11
// propagation pass. It could certainly be improved in many different ways,
12
// like using a worklist. This pass makes arguments dead, but does not remove
13
// them. The existing dead argument elimination pass should be run after this
14
// to clean up the mess.
16
//===----------------------------------------------------------------------===//
18
#define DEBUG_TYPE "ipconstprop"
19
#include "llvm/Transforms/IPO.h"
20
#include "llvm/Constants.h"
21
#include "llvm/Instructions.h"
22
#include "llvm/Module.h"
23
#include "llvm/Pass.h"
24
#include "llvm/Analysis/ValueTracking.h"
25
#include "llvm/Support/CallSite.h"
26
#include "llvm/ADT/Statistic.h"
27
#include "llvm/ADT/SmallVector.h"
30
STATISTIC(NumArgumentsProped, "Number of args turned into constants");
31
STATISTIC(NumReturnValProped, "Number of return values turned into constants");
34
/// IPCP - The interprocedural constant propagation pass
36
struct IPCP : public ModulePass {
37
static char ID; // Pass identification, replacement for typeid
38
IPCP() : ModulePass(ID) {}
40
bool runOnModule(Module &M);
42
bool PropagateConstantsIntoArguments(Function &F);
43
bool PropagateConstantReturn(Function &F);
48
INITIALIZE_PASS(IPCP, "ipconstprop",
49
"Interprocedural constant propagation", false, false);
51
ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); }
53
bool IPCP::runOnModule(Module &M) {
55
bool LocalChange = true;
57
// FIXME: instead of using smart algorithms, we just iterate until we stop
61
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
62
if (!I->isDeclaration()) {
63
// Delete any klingons.
64
I->removeDeadConstantUsers();
65
if (I->hasLocalLinkage())
66
LocalChange |= PropagateConstantsIntoArguments(*I);
67
Changed |= PropagateConstantReturn(*I);
69
Changed |= LocalChange;
74
/// PropagateConstantsIntoArguments - Look at all uses of the specified
75
/// function. If all uses are direct call sites, and all pass a particular
76
/// constant in for an argument, propagate that constant in as the argument.
78
bool IPCP::PropagateConstantsIntoArguments(Function &F) {
79
if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit.
81
// For each argument, keep track of its constant value and whether it is a
82
// constant or not. The bool is driven to true when found to be non-constant.
83
SmallVector<std::pair<Constant*, bool>, 16> ArgumentConstants;
84
ArgumentConstants.resize(F.arg_size());
86
unsigned NumNonconstant = 0;
87
for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) {
89
// Ignore blockaddress uses.
90
if (isa<BlockAddress>(U)) continue;
92
// Used by a non-instruction, or not the callee of a function, do not
94
if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
97
CallSite CS(cast<Instruction>(U));
101
// Check out all of the potentially constant arguments. Note that we don't
102
// inspect varargs here.
103
CallSite::arg_iterator AI = CS.arg_begin();
104
Function::arg_iterator Arg = F.arg_begin();
105
for (unsigned i = 0, e = ArgumentConstants.size(); i != e;
108
// If this argument is known non-constant, ignore it.
109
if (ArgumentConstants[i].second)
112
Constant *C = dyn_cast<Constant>(*AI);
113
if (C && ArgumentConstants[i].first == 0) {
114
ArgumentConstants[i].first = C; // First constant seen.
115
} else if (C && ArgumentConstants[i].first == C) {
116
// Still the constant value we think it is.
117
} else if (*AI == &*Arg) {
118
// Ignore recursive calls passing argument down.
120
// Argument became non-constant. If all arguments are non-constant now,
121
// give up on this function.
122
if (++NumNonconstant == ArgumentConstants.size())
124
ArgumentConstants[i].second = true;
129
// If we got to this point, there is a constant argument!
130
assert(NumNonconstant != ArgumentConstants.size());
131
bool MadeChange = false;
132
Function::arg_iterator AI = F.arg_begin();
133
for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) {
134
// Do we have a constant argument?
135
if (ArgumentConstants[i].second || AI->use_empty() ||
136
(AI->hasByValAttr() && !F.onlyReadsMemory()))
139
Value *V = ArgumentConstants[i].first;
140
if (V == 0) V = UndefValue::get(AI->getType());
141
AI->replaceAllUsesWith(V);
142
++NumArgumentsProped;
149
// Check to see if this function returns one or more constants. If so, replace
150
// all callers that use those return values with the constant value. This will
151
// leave in the actual return values and instructions, but deadargelim will
154
// Additionally if a function always returns one of its arguments directly,
155
// callers will be updated to use the value they pass in directly instead of
156
// using the return value.
157
bool IPCP::PropagateConstantReturn(Function &F) {
158
if (F.getReturnType()->isVoidTy())
159
return false; // No return value.
161
// If this function could be overridden later in the link stage, we can't
162
// propagate information about its results into callers.
163
if (F.mayBeOverridden())
166
// Check to see if this function returns a constant.
167
SmallVector<Value *,4> RetVals;
168
const StructType *STy = dyn_cast<StructType>(F.getReturnType());
170
for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i)
171
RetVals.push_back(UndefValue::get(STy->getElementType(i)));
173
RetVals.push_back(UndefValue::get(F.getReturnType()));
175
unsigned NumNonConstant = 0;
176
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
177
if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
178
for (unsigned i = 0, e = RetVals.size(); i != e; ++i) {
179
// Already found conflicting return values?
180
Value *RV = RetVals[i];
184
// Find the returned value
187
V = RI->getOperand(i);
189
V = FindInsertedValue(RI->getOperand(0), i);
192
// Ignore undefs, we can change them into anything
193
if (isa<UndefValue>(V))
196
// Try to see if all the rets return the same constant or argument.
197
if (isa<Constant>(V) || isa<Argument>(V)) {
198
if (isa<UndefValue>(RV)) {
199
// No value found yet? Try the current one.
203
// Returning the same value? Good.
208
// Different or no known return value? Don't propagate this return
211
// All values non constant? Stop looking.
212
if (++NumNonConstant == RetVals.size())
217
// If we got here, the function returns at least one constant value. Loop
218
// over all users, replacing any uses of the return value with the returned
220
bool MadeChange = false;
221
for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) {
223
Instruction* Call = CS.getInstruction();
225
// Not a call instruction or a call instruction that's not calling F
227
if (!Call || !CS.isCallee(UI))
230
// Call result not used?
231
if (Call->use_empty())
237
Value* New = RetVals[0];
238
if (Argument *A = dyn_cast<Argument>(New))
239
// Was an argument returned? Then find the corresponding argument in
240
// the call instruction and use that.
241
New = CS.getArgument(A->getArgNo());
242
Call->replaceAllUsesWith(New);
246
for (Value::use_iterator I = Call->use_begin(), E = Call->use_end();
248
Instruction *Ins = cast<Instruction>(*I);
250
// Increment now, so we can remove the use
253
// Find the index of the retval to replace with
255
if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Ins))
256
if (EV->hasIndices())
257
index = *EV->idx_begin();
259
// If this use uses a specific return value, and we have a replacement,
262
Value *New = RetVals[index];
264
if (Argument *A = dyn_cast<Argument>(New))
265
// Was an argument returned? Then find the corresponding argument in
266
// the call instruction and use that.
267
New = CS.getArgument(A->getArgNo());
268
Ins->replaceAllUsesWith(New);
269
Ins->eraseFromParent();
275
if (MadeChange) ++NumReturnValProped;