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