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 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/ValueTracking.h"
21 #include "llvm/IR/CallSite.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/IR/Module.h"
25 #include "llvm/Pass.h"
26 #include "llvm/Transforms/IPO.h"
29 #define DEBUG_TYPE "ipconstprop"
31 STATISTIC(NumArgumentsProped, "Number of args turned into constants");
32 STATISTIC(NumReturnValProped, "Number of return values turned into constants");
35 /// IPCP - The interprocedural constant propagation pass
37 struct IPCP : public ModulePass {
38 static char ID; // Pass identification, replacement for typeid
39 IPCP() : ModulePass(ID) {
40 initializeIPCPPass(*PassRegistry::getPassRegistry());
43 bool runOnModule(Module &M) override;
47 /// PropagateConstantsIntoArguments - Look at all uses of the specified
48 /// function. If all uses are direct call sites, and all pass a particular
49 /// constant in for an argument, propagate that constant in as the argument.
51 static bool PropagateConstantsIntoArguments(Function &F) {
52 if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit.
54 // For each argument, keep track of its constant value and whether it is a
55 // constant or not. The bool is driven to true when found to be non-constant.
56 SmallVector<std::pair<Constant*, bool>, 16> ArgumentConstants;
57 ArgumentConstants.resize(F.arg_size());
59 unsigned NumNonconstant = 0;
60 for (Use &U : F.uses()) {
61 User *UR = U.getUser();
62 // Ignore blockaddress uses.
63 if (isa<BlockAddress>(UR)) continue;
65 // Used by a non-instruction, or not the callee of a function, do not
67 if (!isa<CallInst>(UR) && !isa<InvokeInst>(UR))
70 CallSite CS(cast<Instruction>(UR));
74 // Check out all of the potentially constant arguments. Note that we don't
75 // inspect varargs here.
76 CallSite::arg_iterator AI = CS.arg_begin();
77 Function::arg_iterator Arg = F.arg_begin();
78 for (unsigned i = 0, e = ArgumentConstants.size(); i != e;
81 // If this argument is known non-constant, ignore it.
82 if (ArgumentConstants[i].second)
85 Constant *C = dyn_cast<Constant>(*AI);
86 if (C && ArgumentConstants[i].first == nullptr) {
87 ArgumentConstants[i].first = C; // First constant seen.
88 } else if (C && ArgumentConstants[i].first == C) {
89 // Still the constant value we think it is.
90 } else if (*AI == &*Arg) {
91 // Ignore recursive calls passing argument down.
93 // Argument became non-constant. If all arguments are non-constant now,
94 // give up on this function.
95 if (++NumNonconstant == ArgumentConstants.size())
97 ArgumentConstants[i].second = true;
102 // If we got to this point, there is a constant argument!
103 assert(NumNonconstant != ArgumentConstants.size());
104 bool MadeChange = false;
105 Function::arg_iterator AI = F.arg_begin();
106 for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) {
107 // Do we have a constant argument?
108 if (ArgumentConstants[i].second || AI->use_empty() ||
109 AI->hasInAllocaAttr() || (AI->hasByValAttr() && !F.onlyReadsMemory()))
112 Value *V = ArgumentConstants[i].first;
113 if (!V) V = UndefValue::get(AI->getType());
114 AI->replaceAllUsesWith(V);
115 ++NumArgumentsProped;
122 // Check to see if this function returns one or more constants. If so, replace
123 // all callers that use those return values with the constant value. This will
124 // leave in the actual return values and instructions, but deadargelim will
127 // Additionally if a function always returns one of its arguments directly,
128 // callers will be updated to use the value they pass in directly instead of
129 // using the return value.
130 static bool PropagateConstantReturn(Function &F) {
131 if (F.getReturnType()->isVoidTy())
132 return false; // No return value.
134 // We can infer and propagate the return value only when we know that the
135 // definition we'll get at link time is *exactly* the definition we see now.
136 // For more details, see GlobalValue::mayBeDerefined.
137 if (!F.isDefinitionExact())
140 // Don't touch naked functions. The may contain asm returning
141 // value we don't see, so we may end up interprocedurally propagating
142 // the return value incorrectly.
143 if (F.hasFnAttribute(Attribute::Naked))
146 // Check to see if this function returns a constant.
147 SmallVector<Value *,4> RetVals;
148 StructType *STy = dyn_cast<StructType>(F.getReturnType());
150 for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i)
151 RetVals.push_back(UndefValue::get(STy->getElementType(i)));
153 RetVals.push_back(UndefValue::get(F.getReturnType()));
155 unsigned NumNonConstant = 0;
156 for (BasicBlock &BB : F)
157 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) {
158 for (unsigned i = 0, e = RetVals.size(); i != e; ++i) {
159 // Already found conflicting return values?
160 Value *RV = RetVals[i];
164 // Find the returned value
167 V = RI->getOperand(0);
169 V = FindInsertedValue(RI->getOperand(0), i);
172 // Ignore undefs, we can change them into anything
173 if (isa<UndefValue>(V))
176 // Try to see if all the rets return the same constant or argument.
177 if (isa<Constant>(V) || isa<Argument>(V)) {
178 if (isa<UndefValue>(RV)) {
179 // No value found yet? Try the current one.
183 // Returning the same value? Good.
188 // Different or no known return value? Don't propagate this return
190 RetVals[i] = nullptr;
191 // All values non-constant? Stop looking.
192 if (++NumNonConstant == RetVals.size())
197 // If we got here, the function returns at least one constant value. Loop
198 // over all users, replacing any uses of the return value with the returned
200 bool MadeChange = false;
201 for (Use &U : F.uses()) {
202 CallSite CS(U.getUser());
203 Instruction* Call = CS.getInstruction();
205 // Not a call instruction or a call instruction that's not calling F
207 if (!Call || !CS.isCallee(&U))
210 // Call result not used?
211 if (Call->use_empty())
217 Value* New = RetVals[0];
218 if (Argument *A = dyn_cast<Argument>(New))
219 // Was an argument returned? Then find the corresponding argument in
220 // the call instruction and use that.
221 New = CS.getArgument(A->getArgNo());
222 Call->replaceAllUsesWith(New);
226 for (auto I = Call->user_begin(), E = Call->user_end(); I != E;) {
227 Instruction *Ins = cast<Instruction>(*I);
229 // Increment now, so we can remove the use
232 // Find the index of the retval to replace with
234 if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Ins))
235 if (EV->hasIndices())
236 index = *EV->idx_begin();
238 // If this use uses a specific return value, and we have a replacement,
241 Value *New = RetVals[index];
243 if (Argument *A = dyn_cast<Argument>(New))
244 // Was an argument returned? Then find the corresponding argument in
245 // the call instruction and use that.
246 New = CS.getArgument(A->getArgNo());
247 Ins->replaceAllUsesWith(New);
248 Ins->eraseFromParent();
254 if (MadeChange) ++NumReturnValProped;
259 INITIALIZE_PASS(IPCP, "ipconstprop",
260 "Interprocedural constant propagation", false, false)
262 ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); }
264 bool IPCP::runOnModule(Module &M) {
268 bool Changed = false;
269 bool LocalChange = true;
271 // FIXME: instead of using smart algorithms, we just iterate until we stop
273 while (LocalChange) {
275 for (Function &F : M)
276 if (!F.isDeclaration()) {
277 // Delete any klingons.
278 F.removeDeadConstantUsers();
279 if (F.hasLocalLinkage())
280 LocalChange |= PropagateConstantsIntoArguments(F);
281 Changed |= PropagateConstantReturn(F);
283 Changed |= LocalChange;