1 //===-- IPConstantPropagation.cpp - Propagate constants through calls -----===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #include "llvm/Transforms/IPO.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/IR/CallSite.h"
23 #include "llvm/IR/Constants.h"
24 #include "llvm/IR/Instructions.h"
25 #include "llvm/IR/Module.h"
26 #include "llvm/Pass.h"
27 using namespace llvm;
28 
29 #define DEBUG_TYPE "ipconstprop"
30 
31 STATISTIC(NumArgumentsProped, "Number of args turned into constants");
32 STATISTIC(NumReturnValProped, "Number of return values turned into constants");
33 
34 namespace {
35   /// IPCP - The interprocedural constant propagation pass
36   ///
37   struct IPCP : public ModulePass {
38     static char ID; // Pass identification, replacement for typeid
IPCP__anon6ecd114e0111::IPCP39     IPCP() : ModulePass(ID) {
40       initializeIPCPPass(*PassRegistry::getPassRegistry());
41     }
42 
43     bool runOnModule(Module &M) override;
44   private:
45     bool PropagateConstantsIntoArguments(Function &F);
46     bool PropagateConstantReturn(Function &F);
47   };
48 }
49 
50 char IPCP::ID = 0;
51 INITIALIZE_PASS(IPCP, "ipconstprop",
52                 "Interprocedural constant propagation", false, false)
53 
createIPConstantPropagationPass()54 ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); }
55 
runOnModule(Module & M)56 bool IPCP::runOnModule(Module &M) {
57   bool Changed = false;
58   bool LocalChange = true;
59 
60   // FIXME: instead of using smart algorithms, we just iterate until we stop
61   // making changes.
62   while (LocalChange) {
63     LocalChange = false;
64     for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
65       if (!I->isDeclaration()) {
66         // Delete any klingons.
67         I->removeDeadConstantUsers();
68         if (I->hasLocalLinkage())
69           LocalChange |= PropagateConstantsIntoArguments(*I);
70         Changed |= PropagateConstantReturn(*I);
71       }
72     Changed |= LocalChange;
73   }
74   return Changed;
75 }
76 
77 /// PropagateConstantsIntoArguments - Look at all uses of the specified
78 /// function.  If all uses are direct call sites, and all pass a particular
79 /// constant in for an argument, propagate that constant in as the argument.
80 ///
PropagateConstantsIntoArguments(Function & F)81 bool IPCP::PropagateConstantsIntoArguments(Function &F) {
82   if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit.
83 
84   // For each argument, keep track of its constant value and whether it is a
85   // constant or not.  The bool is driven to true when found to be non-constant.
86   SmallVector<std::pair<Constant*, bool>, 16> ArgumentConstants;
87   ArgumentConstants.resize(F.arg_size());
88 
89   unsigned NumNonconstant = 0;
90   for (Use &U : F.uses()) {
91     User *UR = U.getUser();
92     // Ignore blockaddress uses.
93     if (isa<BlockAddress>(UR)) continue;
94 
95     // Used by a non-instruction, or not the callee of a function, do not
96     // transform.
97     if (!isa<CallInst>(UR) && !isa<InvokeInst>(UR))
98       return false;
99 
100     CallSite CS(cast<Instruction>(UR));
101     if (!CS.isCallee(&U))
102       return false;
103 
104     // Check out all of the potentially constant arguments.  Note that we don't
105     // inspect varargs here.
106     CallSite::arg_iterator AI = CS.arg_begin();
107     Function::arg_iterator Arg = F.arg_begin();
108     for (unsigned i = 0, e = ArgumentConstants.size(); i != e;
109          ++i, ++AI, ++Arg) {
110 
111       // If this argument is known non-constant, ignore it.
112       if (ArgumentConstants[i].second)
113         continue;
114 
115       Constant *C = dyn_cast<Constant>(*AI);
116       if (C && ArgumentConstants[i].first == nullptr) {
117         ArgumentConstants[i].first = C;   // First constant seen.
118       } else if (C && ArgumentConstants[i].first == C) {
119         // Still the constant value we think it is.
120       } else if (*AI == &*Arg) {
121         // Ignore recursive calls passing argument down.
122       } else {
123         // Argument became non-constant.  If all arguments are non-constant now,
124         // give up on this function.
125         if (++NumNonconstant == ArgumentConstants.size())
126           return false;
127         ArgumentConstants[i].second = true;
128       }
129     }
130   }
131 
132   // If we got to this point, there is a constant argument!
133   assert(NumNonconstant != ArgumentConstants.size());
134   bool MadeChange = false;
135   Function::arg_iterator AI = F.arg_begin();
136   for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) {
137     // Do we have a constant argument?
138     if (ArgumentConstants[i].second || AI->use_empty() ||
139         AI->hasInAllocaAttr() || (AI->hasByValAttr() && !F.onlyReadsMemory()))
140       continue;
141 
142     Value *V = ArgumentConstants[i].first;
143     if (!V) V = UndefValue::get(AI->getType());
144     AI->replaceAllUsesWith(V);
145     ++NumArgumentsProped;
146     MadeChange = true;
147   }
148   return MadeChange;
149 }
150 
151 
152 // Check to see if this function returns one or more constants. If so, replace
153 // all callers that use those return values with the constant value. This will
154 // leave in the actual return values and instructions, but deadargelim will
155 // clean that up.
156 //
157 // Additionally if a function always returns one of its arguments directly,
158 // callers will be updated to use the value they pass in directly instead of
159 // using the return value.
PropagateConstantReturn(Function & F)160 bool IPCP::PropagateConstantReturn(Function &F) {
161   if (F.getReturnType()->isVoidTy())
162     return false; // No return value.
163 
164   // If this function could be overridden later in the link stage, we can't
165   // propagate information about its results into callers.
166   if (F.mayBeOverridden())
167     return false;
168 
169   // Check to see if this function returns a constant.
170   SmallVector<Value *,4> RetVals;
171   StructType *STy = dyn_cast<StructType>(F.getReturnType());
172   if (STy)
173     for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i)
174       RetVals.push_back(UndefValue::get(STy->getElementType(i)));
175   else
176     RetVals.push_back(UndefValue::get(F.getReturnType()));
177 
178   unsigned NumNonConstant = 0;
179   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
180     if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
181       for (unsigned i = 0, e = RetVals.size(); i != e; ++i) {
182         // Already found conflicting return values?
183         Value *RV = RetVals[i];
184         if (!RV)
185           continue;
186 
187         // Find the returned value
188         Value *V;
189         if (!STy)
190           V = RI->getOperand(0);
191         else
192           V = FindInsertedValue(RI->getOperand(0), i);
193 
194         if (V) {
195           // Ignore undefs, we can change them into anything
196           if (isa<UndefValue>(V))
197             continue;
198 
199           // Try to see if all the rets return the same constant or argument.
200           if (isa<Constant>(V) || isa<Argument>(V)) {
201             if (isa<UndefValue>(RV)) {
202               // No value found yet? Try the current one.
203               RetVals[i] = V;
204               continue;
205             }
206             // Returning the same value? Good.
207             if (RV == V)
208               continue;
209           }
210         }
211         // Different or no known return value? Don't propagate this return
212         // value.
213         RetVals[i] = nullptr;
214         // All values non-constant? Stop looking.
215         if (++NumNonConstant == RetVals.size())
216           return false;
217       }
218     }
219 
220   // If we got here, the function returns at least one constant value.  Loop
221   // over all users, replacing any uses of the return value with the returned
222   // constant.
223   bool MadeChange = false;
224   for (Use &U : F.uses()) {
225     CallSite CS(U.getUser());
226     Instruction* Call = CS.getInstruction();
227 
228     // Not a call instruction or a call instruction that's not calling F
229     // directly?
230     if (!Call || !CS.isCallee(&U))
231       continue;
232 
233     // Call result not used?
234     if (Call->use_empty())
235       continue;
236 
237     MadeChange = true;
238 
239     if (!STy) {
240       Value* New = RetVals[0];
241       if (Argument *A = dyn_cast<Argument>(New))
242         // Was an argument returned? Then find the corresponding argument in
243         // the call instruction and use that.
244         New = CS.getArgument(A->getArgNo());
245       Call->replaceAllUsesWith(New);
246       continue;
247     }
248 
249     for (auto I = Call->user_begin(), E = Call->user_end(); I != E;) {
250       Instruction *Ins = cast<Instruction>(*I);
251 
252       // Increment now, so we can remove the use
253       ++I;
254 
255       // Find the index of the retval to replace with
256       int index = -1;
257       if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Ins))
258         if (EV->hasIndices())
259           index = *EV->idx_begin();
260 
261       // If this use uses a specific return value, and we have a replacement,
262       // replace it.
263       if (index != -1) {
264         Value *New = RetVals[index];
265         if (New) {
266           if (Argument *A = dyn_cast<Argument>(New))
267             // Was an argument returned? Then find the corresponding argument in
268             // the call instruction and use that.
269             New = CS.getArgument(A->getArgNo());
270           Ins->replaceAllUsesWith(New);
271           Ins->eraseFromParent();
272         }
273       }
274     }
275   }
276 
277   if (MadeChange) ++NumReturnValProped;
278   return MadeChange;
279 }
280