blob: 7dc4d9ee9e341a970f9bc551c0f0da6642045385 [file] [log] [blame]
Chris Lattnerf516c692003-10-23 16:52:27 +00001//===-- IPConstantPropagation.cpp - Propagate constants through calls -----===//
Misha Brukmanb1c93172005-04-21 23:48:37 +00002//
Chandler Carruth2946cd72019-01-19 08:50:56 +00003// 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
Misha Brukmanb1c93172005-04-21 23:48:37 +00006//
Chris Lattnerf516c692003-10-23 16:52:27 +00007//===----------------------------------------------------------------------===//
8//
9// This pass implements an _extremely_ simple interprocedural constant
10// propagation pass. It could certainly be improved in many different ways,
11// like using a worklist. This pass makes arguments dead, but does not remove
12// them. The existing dead argument elimination pass should be run after this
13// to clean up the mess.
14//
15//===----------------------------------------------------------------------===//
16
Chandler Carruthed0881b2012-12-03 16:50:05 +000017#include "llvm/ADT/SmallVector.h"
18#include "llvm/ADT/Statistic.h"
19#include "llvm/Analysis/ValueTracking.h"
Chandler Carruth219b89b2014-03-04 11:01:28 +000020#include "llvm/IR/CallSite.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000021#include "llvm/IR/Constants.h"
22#include "llvm/IR/Instructions.h"
23#include "llvm/IR/Module.h"
Chris Lattnerf516c692003-10-23 16:52:27 +000024#include "llvm/Pass.h"
Chandler Carruth6bda14b2017-06-06 11:49:48 +000025#include "llvm/Transforms/IPO.h"
Chris Lattnerf52e03c2003-11-21 21:54:22 +000026using namespace llvm;
Brian Gaeke960707c2003-11-11 22:41:34 +000027
Chandler Carruth964daaa2014-04-22 02:55:47 +000028#define DEBUG_TYPE "ipconstprop"
29
Chris Lattner1631bcb2006-12-19 22:09:18 +000030STATISTIC(NumArgumentsProped, "Number of args turned into constants");
31STATISTIC(NumReturnValProped, "Number of return values turned into constants");
Chris Lattnerf516c692003-10-23 16:52:27 +000032
Chris Lattner1631bcb2006-12-19 22:09:18 +000033namespace {
Chris Lattnerf516c692003-10-23 16:52:27 +000034 /// IPCP - The interprocedural constant propagation pass
35 ///
Nick Lewycky02d5f772009-10-25 06:33:48 +000036 struct IPCP : public ModulePass {
Nick Lewyckye7da2d62007-05-06 13:37:16 +000037 static char ID; // Pass identification, replacement for typeid
Owen Anderson6c18d1a2010-10-19 17:21:58 +000038 IPCP() : ModulePass(ID) {
39 initializeIPCPPass(*PassRegistry::getPassRegistry());
40 }
Devang Patel09f162c2007-05-01 21:15:47 +000041
Craig Topper3e4c6972014-03-05 09:10:37 +000042 bool runOnModule(Module &M) override;
Chris Lattnerf516c692003-10-23 16:52:27 +000043 };
Alexander Kornienkof00654e2015-06-23 09:49:53 +000044}
Chris Lattnerf516c692003-10-23 16:52:27 +000045
Chris Lattneraf555ad2004-11-14 06:10:11 +000046/// PropagateConstantsIntoArguments - Look at all uses of the specified
47/// function. If all uses are direct call sites, and all pass a particular
48/// constant in for an argument, propagate that constant in as the argument.
Chris Lattnerf516c692003-10-23 16:52:27 +000049///
Davide Italiano296d12c2016-05-03 20:08:24 +000050static bool PropagateConstantsIntoArguments(Function &F) {
Chris Lattnerc2d3d312006-08-27 22:42:52 +000051 if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit.
Chris Lattnerf516c692003-10-23 16:52:27 +000052
Chris Lattnera82d6912008-04-23 06:16:27 +000053 // For each argument, keep track of its constant value and whether it is a
54 // constant or not. The bool is driven to true when found to be non-constant.
55 SmallVector<std::pair<Constant*, bool>, 16> ArgumentConstants;
Chris Lattner531f9e92005-03-15 04:54:21 +000056 ArgumentConstants.resize(F.arg_size());
Chris Lattnerf516c692003-10-23 16:52:27 +000057
58 unsigned NumNonconstant = 0;
Chandler Carruthcdf47882014-03-09 03:16:01 +000059 for (Use &U : F.uses()) {
60 User *UR = U.getUser();
Chris Lattner1a8b80e2009-11-01 06:11:53 +000061 // Ignore blockaddress uses.
Chandler Carruthcdf47882014-03-09 03:16:01 +000062 if (isa<BlockAddress>(UR)) continue;
Fangrui Songf78650a2018-07-30 19:41:25 +000063
Johannes Doerfert36872b52019-01-19 05:19:12 +000064 // If no abstract call site was created we did not understand the use, bail.
65 AbstractCallSite ACS(&U);
66 if (!ACS)
Gabor Greiff4013372009-01-22 21:35:57 +000067 return false;
Chris Lattnerf516c692003-10-23 16:52:27 +000068
Bjorn Petterssond014d572019-01-29 10:19:44 +000069 // Mismatched argument count is undefined behavior. Simply bail out to avoid
70 // handling of such situations below (avoiding asserts/crashes).
71 unsigned NumActualArgs = ACS.getNumArgOperands();
72 if (F.isVarArg() ? ArgumentConstants.size() > NumActualArgs
73 : ArgumentConstants.size() != NumActualArgs)
74 return false;
75
Chris Lattnera82d6912008-04-23 06:16:27 +000076 // Check out all of the potentially constant arguments. Note that we don't
77 // inspect varargs here.
Chris Lattnera82d6912008-04-23 06:16:27 +000078 Function::arg_iterator Arg = F.arg_begin();
Johannes Doerfert36872b52019-01-19 05:19:12 +000079 for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++Arg) {
Fangrui Songf78650a2018-07-30 19:41:25 +000080
Chris Lattnera82d6912008-04-23 06:16:27 +000081 // If this argument is known non-constant, ignore it.
82 if (ArgumentConstants[i].second)
83 continue;
Fangrui Songf78650a2018-07-30 19:41:25 +000084
Johannes Doerfert36872b52019-01-19 05:19:12 +000085 Value *V = ACS.getCallArgOperand(i);
86 Constant *C = dyn_cast_or_null<Constant>(V);
87
Bjorn Petterssond014d572019-01-29 10:19:44 +000088 // Mismatched argument type is undefined behavior. Simply bail out to avoid
89 // handling of such situations below (avoiding asserts/crashes).
90 if (C && Arg->getType() != C->getType())
91 return false;
92
Johannes Doerfert36872b52019-01-19 05:19:12 +000093 // We can only propagate thread independent values through callbacks.
94 // This is different to direct/indirect call sites because for them we
95 // know the thread executing the caller and callee is the same. For
96 // callbacks this is not guaranteed, thus a thread dependent value could
97 // be different for the caller and callee, making it invalid to propagate.
98 if (C && ACS.isCallbackCall() && C->isThreadDependent()) {
99 // Argument became non-constant. If all arguments are non-constant now,
100 // give up on this function.
101 if (++NumNonconstant == ArgumentConstants.size())
102 return false;
103
104 ArgumentConstants[i].second = true;
105 continue;
106 }
107
Craig Topperf40110f2014-04-25 05:29:35 +0000108 if (C && ArgumentConstants[i].first == nullptr) {
Chris Lattnera82d6912008-04-23 06:16:27 +0000109 ArgumentConstants[i].first = C; // First constant seen.
110 } else if (C && ArgumentConstants[i].first == C) {
111 // Still the constant value we think it is.
Johannes Doerfert36872b52019-01-19 05:19:12 +0000112 } else if (V == &*Arg) {
Chris Lattnera82d6912008-04-23 06:16:27 +0000113 // Ignore recursive calls passing argument down.
114 } else {
115 // Argument became non-constant. If all arguments are non-constant now,
116 // give up on this function.
117 if (++NumNonconstant == ArgumentConstants.size())
118 return false;
119 ArgumentConstants[i].second = true;
Chris Lattnerf516c692003-10-23 16:52:27 +0000120 }
121 }
Chris Lattnera82d6912008-04-23 06:16:27 +0000122 }
Chris Lattnerf516c692003-10-23 16:52:27 +0000123
124 // If we got to this point, there is a constant argument!
125 assert(NumNonconstant != ArgumentConstants.size());
Chris Lattner5e004e82003-10-27 21:09:00 +0000126 bool MadeChange = false;
Chris Lattnera82d6912008-04-23 06:16:27 +0000127 Function::arg_iterator AI = F.arg_begin();
128 for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) {
129 // Do we have a constant argument?
Torok Edwin21bd8c92009-09-24 18:33:42 +0000130 if (ArgumentConstants[i].second || AI->use_empty() ||
Reid Kleckner26af2ca2014-01-28 02:38:36 +0000131 AI->hasInAllocaAttr() || (AI->hasByValAttr() && !F.onlyReadsMemory()))
Chris Lattnera82d6912008-04-23 06:16:27 +0000132 continue;
Fangrui Songf78650a2018-07-30 19:41:25 +0000133
Chris Lattnera82d6912008-04-23 06:16:27 +0000134 Value *V = ArgumentConstants[i].first;
Craig Topperf40110f2014-04-25 05:29:35 +0000135 if (!V) V = UndefValue::get(AI->getType());
Chris Lattnera82d6912008-04-23 06:16:27 +0000136 AI->replaceAllUsesWith(V);
137 ++NumArgumentsProped;
138 MadeChange = true;
139 }
Chris Lattner5e004e82003-10-27 21:09:00 +0000140 return MadeChange;
Chris Lattnerf516c692003-10-23 16:52:27 +0000141}
Brian Gaeke960707c2003-11-11 22:41:34 +0000142
Chris Lattneraf555ad2004-11-14 06:10:11 +0000143
Matthijs Kooijman97034592008-06-18 08:09:27 +0000144// Check to see if this function returns one or more constants. If so, replace
145// all callers that use those return values with the constant value. This will
146// leave in the actual return values and instructions, but deadargelim will
147// clean that up.
Matthijs Kooijmanfd173572008-06-18 08:30:37 +0000148//
149// Additionally if a function always returns one of its arguments directly,
150// callers will be updated to use the value they pass in directly instead of
151// using the return value.
Davide Italiano296d12c2016-05-03 20:08:24 +0000152static bool PropagateConstantReturn(Function &F) {
Nick Lewycky39dbfd32009-11-23 03:29:18 +0000153 if (F.getReturnType()->isVoidTy())
Chris Lattneraf555ad2004-11-14 06:10:11 +0000154 return false; // No return value.
155
Sanjoy Das5ce32722016-04-08 00:48:30 +0000156 // We can infer and propagate the return value only when we know that the
157 // definition we'll get at link time is *exactly* the definition we see now.
158 // For more details, see GlobalValue::mayBeDerefined.
159 if (!F.isDefinitionExact())
Chris Lattnerdbd595f2008-06-09 07:58:07 +0000160 return false;
Davide Italianoec493132017-02-04 19:44:14 +0000161
162 // Don't touch naked functions. The may contain asm returning
163 // value we don't see, so we may end up interprocedurally propagating
164 // the return value incorrectly.
165 if (F.hasFnAttribute(Attribute::Naked))
166 return false;
167
Chris Lattneraf555ad2004-11-14 06:10:11 +0000168 // Check to see if this function returns a constant.
Devang Patel73581652008-03-11 22:24:29 +0000169 SmallVector<Value *,4> RetVals;
Chris Lattner229907c2011-07-18 04:54:35 +0000170 StructType *STy = dyn_cast<StructType>(F.getReturnType());
Devang Patel73581652008-03-11 22:24:29 +0000171 if (STy)
Fangrui Songf78650a2018-07-30 19:41:25 +0000172 for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i)
Owen Andersonb292b8c2009-07-30 23:03:37 +0000173 RetVals.push_back(UndefValue::get(STy->getElementType(i)));
Devang Patel73581652008-03-11 22:24:29 +0000174 else
Owen Andersonb292b8c2009-07-30 23:03:37 +0000175 RetVals.push_back(UndefValue::get(F.getReturnType()));
Devang Patel73581652008-03-11 22:24:29 +0000176
Matthijs Kooijman97034592008-06-18 08:09:27 +0000177 unsigned NumNonConstant = 0;
Benjamin Kramer135f7352016-06-26 12:28:59 +0000178 for (BasicBlock &BB : F)
179 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) {
Chris Lattner5f1802c2008-04-23 05:59:23 +0000180 for (unsigned i = 0, e = RetVals.size(); i != e; ++i) {
Matthijs Kooijman97034592008-06-18 08:09:27 +0000181 // Already found conflicting return values?
Chris Lattner5f1802c2008-04-23 05:59:23 +0000182 Value *RV = RetVals[i];
Matthijs Kooijman97034592008-06-18 08:09:27 +0000183 if (!RV)
184 continue;
185
186 // Find the returned value
187 Value *V;
Dan Gohmane2190392008-10-03 22:21:24 +0000188 if (!STy)
Jay Foad11522092011-04-04 07:44:02 +0000189 V = RI->getOperand(0);
Matthijs Kooijman97034592008-06-18 08:09:27 +0000190 else
Nick Lewycky39dbfd32009-11-23 03:29:18 +0000191 V = FindInsertedValue(RI->getOperand(0), i);
Matthijs Kooijman97034592008-06-18 08:09:27 +0000192
193 if (V) {
194 // Ignore undefs, we can change them into anything
195 if (isa<UndefValue>(V))
196 continue;
Fangrui Songf78650a2018-07-30 19:41:25 +0000197
Matthijs Kooijmanfd173572008-06-18 08:30:37 +0000198 // Try to see if all the rets return the same constant or argument.
199 if (isa<Constant>(V) || isa<Argument>(V)) {
Matthijs Kooijman97034592008-06-18 08:09:27 +0000200 if (isa<UndefValue>(RV)) {
201 // No value found yet? Try the current one.
202 RetVals[i] = V;
203 continue;
204 }
205 // Returning the same value? Good.
206 if (RV == V)
207 continue;
208 }
209 }
210 // Different or no known return value? Don't propagate this return
211 // value.
Craig Topperf40110f2014-04-25 05:29:35 +0000212 RetVals[i] = nullptr;
Alp Tokerf907b892013-12-05 05:44:44 +0000213 // All values non-constant? Stop looking.
Matthijs Kooijman97034592008-06-18 08:09:27 +0000214 if (++NumNonConstant == RetVals.size())
215 return false;
Chris Lattneraf555ad2004-11-14 06:10:11 +0000216 }
Anton Korobeynikov1bfd1212008-02-20 11:26:25 +0000217 }
Chris Lattneraf555ad2004-11-14 06:10:11 +0000218
Matthijs Kooijman97034592008-06-18 08:09:27 +0000219 // If we got here, the function returns at least one constant value. Loop
220 // over all users, replacing any uses of the return value with the returned
221 // constant.
Chris Lattneraf555ad2004-11-14 06:10:11 +0000222 bool MadeChange = false;
Chandler Carruthcdf47882014-03-09 03:16:01 +0000223 for (Use &U : F.uses()) {
224 CallSite CS(U.getUser());
Matthijs Kooijman0c717322008-06-19 08:53:24 +0000225 Instruction* Call = CS.getInstruction();
226
227 // Not a call instruction or a call instruction that's not calling F
228 // directly?
Chandler Carruthcdf47882014-03-09 03:16:01 +0000229 if (!Call || !CS.isCallee(&U))
Chris Lattner5f1802c2008-04-23 05:59:23 +0000230 continue;
Fangrui Songf78650a2018-07-30 19:41:25 +0000231
Matthijs Kooijman0c717322008-06-19 08:53:24 +0000232 // Call result not used?
Chris Lattner5f1802c2008-04-23 05:59:23 +0000233 if (Call->use_empty())
234 continue;
Chris Lattneraf555ad2004-11-14 06:10:11 +0000235
Chris Lattner5f1802c2008-04-23 05:59:23 +0000236 MadeChange = true;
237
Craig Topperf40110f2014-04-25 05:29:35 +0000238 if (!STy) {
Matthijs Kooijmanfd173572008-06-18 08:30:37 +0000239 Value* New = RetVals[0];
240 if (Argument *A = dyn_cast<Argument>(New))
241 // Was an argument returned? Then find the corresponding argument in
Matthijs Kooijman0c717322008-06-19 08:53:24 +0000242 // the call instruction and use that.
243 New = CS.getArgument(A->getArgNo());
Matthijs Kooijmanfd173572008-06-18 08:30:37 +0000244 Call->replaceAllUsesWith(New);
Chris Lattner5f1802c2008-04-23 05:59:23 +0000245 continue;
246 }
Chandler Carruthcdf47882014-03-09 03:16:01 +0000247
248 for (auto I = Call->user_begin(), E = Call->user_end(); I != E;) {
Jay Foade57ba2e2009-06-06 17:49:35 +0000249 Instruction *Ins = cast<Instruction>(*I);
Matthijs Kooijman97034592008-06-18 08:09:27 +0000250
251 // Increment now, so we can remove the use
252 ++I;
253
Matthijs Kooijman97034592008-06-18 08:09:27 +0000254 // Find the index of the retval to replace with
255 int index = -1;
Dan Gohmanfa1211f2008-07-23 00:34:11 +0000256 if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Ins))
Matthijs Kooijman97034592008-06-18 08:09:27 +0000257 if (EV->hasIndices())
258 index = *EV->idx_begin();
259
260 // If this use uses a specific return value, and we have a replacement,
261 // replace it.
262 if (index != -1) {
263 Value *New = RetVals[index];
264 if (New) {
Matthijs Kooijmanfd173572008-06-18 08:30:37 +0000265 if (Argument *A = dyn_cast<Argument>(New))
266 // Was an argument returned? Then find the corresponding argument in
Matthijs Kooijman0c717322008-06-19 08:53:24 +0000267 // the call instruction and use that.
268 New = CS.getArgument(A->getArgNo());
Matthijs Kooijman97034592008-06-18 08:09:27 +0000269 Ins->replaceAllUsesWith(New);
270 Ins->eraseFromParent();
Chris Lattner263b0a12004-12-11 17:00:14 +0000271 }
Devang Patel5ca2ea62008-03-20 18:30:32 +0000272 }
Devang Patel73581652008-03-11 22:24:29 +0000273 }
Chris Lattneraf555ad2004-11-14 06:10:11 +0000274 }
275
276 if (MadeChange) ++NumReturnValProped;
Chris Lattneraf555ad2004-11-14 06:10:11 +0000277 return MadeChange;
278}
Davide Italiano296d12c2016-05-03 20:08:24 +0000279
280char IPCP::ID = 0;
281INITIALIZE_PASS(IPCP, "ipconstprop",
282 "Interprocedural constant propagation", false, false)
283
284ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); }
285
286bool IPCP::runOnModule(Module &M) {
287 if (skipModule(M))
288 return false;
289
290 bool Changed = false;
291 bool LocalChange = true;
292
293 // FIXME: instead of using smart algorithms, we just iterate until we stop
294 // making changes.
295 while (LocalChange) {
296 LocalChange = false;
Benjamin Kramer135f7352016-06-26 12:28:59 +0000297 for (Function &F : M)
298 if (!F.isDeclaration()) {
Davide Italiano296d12c2016-05-03 20:08:24 +0000299 // Delete any klingons.
Benjamin Kramer135f7352016-06-26 12:28:59 +0000300 F.removeDeadConstantUsers();
301 if (F.hasLocalLinkage())
302 LocalChange |= PropagateConstantsIntoArguments(F);
303 Changed |= PropagateConstantReturn(F);
Davide Italiano296d12c2016-05-03 20:08:24 +0000304 }
305 Changed |= LocalChange;
306 }
307 return Changed;
308}