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