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" 28 using namespace llvm; 29 30 STATISTIC(NumArgumentsProped, "Number of args turned into constants"); 31 STATISTIC(NumReturnValProped, "Number of return values turned into constants"); 32 33 namespace { 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 initializeIPCPPass(*PassRegistry::getPassRegistry()); 40 } 41 42 bool runOnModule(Module &M); 43 private: 44 bool PropagateConstantsIntoArguments(Function &F); 45 bool PropagateConstantReturn(Function &F); 46 }; 47 } 48 49 char IPCP::ID = 0; 50 INITIALIZE_PASS(IPCP, "ipconstprop", 51 "Interprocedural constant propagation", false, false) 52 53 ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); } 54 55 bool IPCP::runOnModule(Module &M) { 56 bool Changed = false; 57 bool LocalChange = true; 58 59 // FIXME: instead of using smart algorithms, we just iterate until we stop 60 // making changes. 61 while (LocalChange) { 62 LocalChange = false; 63 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 64 if (!I->isDeclaration()) { 65 // Delete any klingons. 66 I->removeDeadConstantUsers(); 67 if (I->hasLocalLinkage()) 68 LocalChange |= PropagateConstantsIntoArguments(*I); 69 Changed |= PropagateConstantReturn(*I); 70 } 71 Changed |= LocalChange; 72 } 73 return Changed; 74 } 75 76 /// PropagateConstantsIntoArguments - Look at all uses of the specified 77 /// function. If all uses are direct call sites, and all pass a particular 78 /// constant in for an argument, propagate that constant in as the argument. 79 /// 80 bool IPCP::PropagateConstantsIntoArguments(Function &F) { 81 if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit. 82 83 // For each argument, keep track of its constant value and whether it is a 84 // constant or not. The bool is driven to true when found to be non-constant. 85 SmallVector<std::pair<Constant*, bool>, 16> ArgumentConstants; 86 ArgumentConstants.resize(F.arg_size()); 87 88 unsigned NumNonconstant = 0; 89 for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) { 90 User *U = *UI; 91 // Ignore blockaddress uses. 92 if (isa<BlockAddress>(U)) continue; 93 94 // Used by a non-instruction, or not the callee of a function, do not 95 // transform. 96 if (!isa<CallInst>(U) && !isa<InvokeInst>(U)) 97 return false; 98 99 CallSite CS(cast<Instruction>(U)); 100 if (!CS.isCallee(UI)) 101 return false; 102 103 // Check out all of the potentially constant arguments. Note that we don't 104 // inspect varargs here. 105 CallSite::arg_iterator AI = CS.arg_begin(); 106 Function::arg_iterator Arg = F.arg_begin(); 107 for (unsigned i = 0, e = ArgumentConstants.size(); i != e; 108 ++i, ++AI, ++Arg) { 109 110 // If this argument is known non-constant, ignore it. 111 if (ArgumentConstants[i].second) 112 continue; 113 114 Constant *C = dyn_cast<Constant>(*AI); 115 if (C && ArgumentConstants[i].first == 0) { 116 ArgumentConstants[i].first = C; // First constant seen. 117 } else if (C && ArgumentConstants[i].first == C) { 118 // Still the constant value we think it is. 119 } else if (*AI == &*Arg) { 120 // Ignore recursive calls passing argument down. 121 } else { 122 // Argument became non-constant. If all arguments are non-constant now, 123 // give up on this function. 124 if (++NumNonconstant == ArgumentConstants.size()) 125 return false; 126 ArgumentConstants[i].second = true; 127 } 128 } 129 } 130 131 // If we got to this point, there is a constant argument! 132 assert(NumNonconstant != ArgumentConstants.size()); 133 bool MadeChange = false; 134 Function::arg_iterator AI = F.arg_begin(); 135 for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) { 136 // Do we have a constant argument? 137 if (ArgumentConstants[i].second || AI->use_empty() || 138 (AI->hasByValAttr() && !F.onlyReadsMemory())) 139 continue; 140 141 Value *V = ArgumentConstants[i].first; 142 if (V == 0) V = UndefValue::get(AI->getType()); 143 AI->replaceAllUsesWith(V); 144 ++NumArgumentsProped; 145 MadeChange = true; 146 } 147 return MadeChange; 148 } 149 150 151 // Check to see if this function returns one or more constants. If so, replace 152 // all callers that use those return values with the constant value. This will 153 // leave in the actual return values and instructions, but deadargelim will 154 // clean that up. 155 // 156 // Additionally if a function always returns one of its arguments directly, 157 // callers will be updated to use the value they pass in directly instead of 158 // using the return value. 159 bool IPCP::PropagateConstantReturn(Function &F) { 160 if (F.getReturnType()->isVoidTy()) 161 return false; // No return value. 162 163 // If this function could be overridden later in the link stage, we can't 164 // propagate information about its results into callers. 165 if (F.mayBeOverridden()) 166 return false; 167 168 // Check to see if this function returns a constant. 169 SmallVector<Value *,4> RetVals; 170 StructType *STy = dyn_cast<StructType>(F.getReturnType()); 171 if (STy) 172 for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i) 173 RetVals.push_back(UndefValue::get(STy->getElementType(i))); 174 else 175 RetVals.push_back(UndefValue::get(F.getReturnType())); 176 177 unsigned NumNonConstant = 0; 178 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 179 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 180 for (unsigned i = 0, e = RetVals.size(); i != e; ++i) { 181 // Already found conflicting return values? 182 Value *RV = RetVals[i]; 183 if (!RV) 184 continue; 185 186 // Find the returned value 187 Value *V; 188 if (!STy) 189 V = RI->getOperand(0); 190 else 191 V = FindInsertedValue(RI->getOperand(0), i); 192 193 if (V) { 194 // Ignore undefs, we can change them into anything 195 if (isa<UndefValue>(V)) 196 continue; 197 198 // Try to see if all the rets return the same constant or argument. 199 if (isa<Constant>(V) || isa<Argument>(V)) { 200 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. 212 RetVals[i] = 0; 213 // All values non constant? Stop looking. 214 if (++NumNonConstant == RetVals.size()) 215 return false; 216 } 217 } 218 219 // 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. 222 bool MadeChange = false; 223 for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) { 224 CallSite CS(*UI); 225 Instruction* Call = CS.getInstruction(); 226 227 // Not a call instruction or a call instruction that's not calling F 228 // directly? 229 if (!Call || !CS.isCallee(UI)) 230 continue; 231 232 // Call result not used? 233 if (Call->use_empty()) 234 continue; 235 236 MadeChange = true; 237 238 if (STy == 0) { 239 Value* New = RetVals[0]; 240 if (Argument *A = dyn_cast<Argument>(New)) 241 // Was an argument returned? Then find the corresponding argument in 242 // the call instruction and use that. 243 New = CS.getArgument(A->getArgNo()); 244 Call->replaceAllUsesWith(New); 245 continue; 246 } 247 248 for (Value::use_iterator I = Call->use_begin(), E = Call->use_end(); 249 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