IPConstantPropagation.cpp revision 9ccaf53ada99c63737547c0235baeb8454b04e80
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#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" 28using namespace llvm; 29 30STATISTIC(NumArgumentsProped, "Number of args turned into constants"); 31STATISTIC(NumReturnValProped, "Number of return values turned into constants"); 32 33namespace { 34 /// IPCP - The interprocedural constant propagation pass 35 /// 36 struct IPCP : public ModulePass { 37 static char ID; // Pass identification, replacement for typeid 38 IPCP() : ModulePass(ID) {} 39 40 bool runOnModule(Module &M); 41 private: 42 bool PropagateConstantsIntoArguments(Function &F); 43 bool PropagateConstantReturn(Function &F); 44 }; 45} 46 47char IPCP::ID = 0; 48INITIALIZE_PASS(IPCP, "ipconstprop", 49 "Interprocedural constant propagation", false, false); 50 51ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); } 52 53bool IPCP::runOnModule(Module &M) { 54 bool Changed = false; 55 bool LocalChange = true; 56 57 // FIXME: instead of using smart algorithms, we just iterate until we stop 58 // making changes. 59 while (LocalChange) { 60 LocalChange = false; 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); 68 } 69 Changed |= LocalChange; 70 } 71 return Changed; 72} 73 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. 77/// 78bool IPCP::PropagateConstantsIntoArguments(Function &F) { 79 if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit. 80 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()); 85 86 unsigned NumNonconstant = 0; 87 for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) { 88 User *U = *UI; 89 // Ignore blockaddress uses. 90 if (isa<BlockAddress>(U)) continue; 91 92 // Used by a non-instruction, or not the callee of a function, do not 93 // transform. 94 if (!isa<CallInst>(U) && !isa<InvokeInst>(U)) 95 return false; 96 97 CallSite CS(cast<Instruction>(U)); 98 if (!CS.isCallee(UI)) 99 return false; 100 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; 106 ++i, ++AI, ++Arg) { 107 108 // If this argument is known non-constant, ignore it. 109 if (ArgumentConstants[i].second) 110 continue; 111 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. 119 } else { 120 // Argument became non-constant. If all arguments are non-constant now, 121 // give up on this function. 122 if (++NumNonconstant == ArgumentConstants.size()) 123 return false; 124 ArgumentConstants[i].second = true; 125 } 126 } 127 } 128 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())) 137 continue; 138 139 Value *V = ArgumentConstants[i].first; 140 if (V == 0) V = UndefValue::get(AI->getType()); 141 AI->replaceAllUsesWith(V); 142 ++NumArgumentsProped; 143 MadeChange = true; 144 } 145 return MadeChange; 146} 147 148 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 152// clean that up. 153// 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. 157bool IPCP::PropagateConstantReturn(Function &F) { 158 if (F.getReturnType()->isVoidTy()) 159 return false; // No return value. 160 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()) 164 return false; 165 166 // Check to see if this function returns a constant. 167 SmallVector<Value *,4> RetVals; 168 const StructType *STy = dyn_cast<StructType>(F.getReturnType()); 169 if (STy) 170 for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i) 171 RetVals.push_back(UndefValue::get(STy->getElementType(i))); 172 else 173 RetVals.push_back(UndefValue::get(F.getReturnType())); 174 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]; 181 if (!RV) 182 continue; 183 184 // Find the returned value 185 Value *V; 186 if (!STy) 187 V = RI->getOperand(i); 188 else 189 V = FindInsertedValue(RI->getOperand(0), i); 190 191 if (V) { 192 // Ignore undefs, we can change them into anything 193 if (isa<UndefValue>(V)) 194 continue; 195 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. 200 RetVals[i] = V; 201 continue; 202 } 203 // Returning the same value? Good. 204 if (RV == V) 205 continue; 206 } 207 } 208 // Different or no known return value? Don't propagate this return 209 // value. 210 RetVals[i] = 0; 211 // All values non constant? Stop looking. 212 if (++NumNonConstant == RetVals.size()) 213 return false; 214 } 215 } 216 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 219 // constant. 220 bool MadeChange = false; 221 for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) { 222 CallSite CS(*UI); 223 Instruction* Call = CS.getInstruction(); 224 225 // Not a call instruction or a call instruction that's not calling F 226 // directly? 227 if (!Call || !CS.isCallee(UI)) 228 continue; 229 230 // Call result not used? 231 if (Call->use_empty()) 232 continue; 233 234 MadeChange = true; 235 236 if (STy == 0) { 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); 243 continue; 244 } 245 246 for (Value::use_iterator I = Call->use_begin(), E = Call->use_end(); 247 I != E;) { 248 Instruction *Ins = cast<Instruction>(*I); 249 250 // Increment now, so we can remove the use 251 ++I; 252 253 // Find the index of the retval to replace with 254 int index = -1; 255 if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Ins)) 256 if (EV->hasIndices()) 257 index = *EV->idx_begin(); 258 259 // If this use uses a specific return value, and we have a replacement, 260 // replace it. 261 if (index != -1) { 262 Value *New = RetVals[index]; 263 if (New) { 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(); 270 } 271 } 272 } 273 } 274 275 if (MadeChange) ++NumReturnValProped; 276 return MadeChange; 277} 278