1//===-- IPConstantPropagation.cpp - Propagate constants through calls -----===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// This pass implements an _extremely_ simple interprocedural constant 10// propagation pass. It could certainly be improved in many different ways, 11// like using a worklist. This pass makes arguments dead, but does not remove 12// them. The existing dead argument elimination pass should be run after this 13// to clean up the mess. 14// 15//===----------------------------------------------------------------------===// 16 17#include "llvm/ADT/SmallVector.h" 18#include "llvm/ADT/Statistic.h" 19#include "llvm/Analysis/ValueTracking.h" 20#include "llvm/IR/CallSite.h" 21#include "llvm/IR/Constants.h" 22#include "llvm/IR/Instructions.h" 23#include "llvm/IR/Module.h" 24#include "llvm/InitializePasses.h" 25#include "llvm/Pass.h" 26#include "llvm/Transforms/IPO.h" 27using namespace llvm; 28 29#define DEBUG_TYPE "ipconstprop" 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 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/// 51static 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 // If no abstract call site was created we did not understand the use, bail. 66 AbstractCallSite ACS(&U); 67 if (!ACS) 68 return false; 69 70 // Mismatched argument count is undefined behavior. Simply bail out to avoid 71 // handling of such situations below (avoiding asserts/crashes). 72 unsigned NumActualArgs = ACS.getNumArgOperands(); 73 if (F.isVarArg() ? ArgumentConstants.size() > NumActualArgs 74 : ArgumentConstants.size() != NumActualArgs) 75 return false; 76 77 // Check out all of the potentially constant arguments. Note that we don't 78 // inspect varargs here. 79 Function::arg_iterator Arg = F.arg_begin(); 80 for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++Arg) { 81 82 // If this argument is known non-constant, ignore it. 83 if (ArgumentConstants[i].second) 84 continue; 85 86 Value *V = ACS.getCallArgOperand(i); 87 Constant *C = dyn_cast_or_null<Constant>(V); 88 89 // Mismatched argument type is undefined behavior. Simply bail out to avoid 90 // handling of such situations below (avoiding asserts/crashes). 91 if (C && Arg->getType() != C->getType()) 92 return false; 93 94 // We can only propagate thread independent values through callbacks. 95 // This is different to direct/indirect call sites because for them we 96 // know the thread executing the caller and callee is the same. For 97 // callbacks this is not guaranteed, thus a thread dependent value could 98 // be different for the caller and callee, making it invalid to propagate. 99 if (C && ACS.isCallbackCall() && C->isThreadDependent()) { 100 // Argument became non-constant. If all arguments are non-constant now, 101 // give up on this function. 102 if (++NumNonconstant == ArgumentConstants.size()) 103 return false; 104 105 ArgumentConstants[i].second = true; 106 continue; 107 } 108 109 if (C && ArgumentConstants[i].first == nullptr) { 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 (V == &*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 AI->hasInAllocaAttr() || (AI->hasByValAttr() && !F.onlyReadsMemory())) 133 continue; 134 135 Value *V = ArgumentConstants[i].first; 136 if (!V) V = UndefValue::get(AI->getType()); 137 AI->replaceAllUsesWith(V); 138 ++NumArgumentsProped; 139 MadeChange = true; 140 } 141 return MadeChange; 142} 143 144 145// Check to see if this function returns one or more constants. If so, replace 146// all callers that use those return values with the constant value. This will 147// leave in the actual return values and instructions, but deadargelim will 148// clean that up. 149// 150// Additionally if a function always returns one of its arguments directly, 151// callers will be updated to use the value they pass in directly instead of 152// using the return value. 153static bool PropagateConstantReturn(Function &F) { 154 if (F.getReturnType()->isVoidTy()) 155 return false; // No return value. 156 157 // We can infer and propagate the return value only when we know that the 158 // definition we'll get at link time is *exactly* the definition we see now. 159 // For more details, see GlobalValue::mayBeDerefined. 160 if (!F.isDefinitionExact()) 161 return false; 162 163 // Don't touch naked functions. The may contain asm returning 164 // value we don't see, so we may end up interprocedurally propagating 165 // the return value incorrectly. 166 if (F.hasFnAttribute(Attribute::Naked)) 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 (BasicBlock &BB : F) 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->getNumIndices() == 1) 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 281char IPCP::ID = 0; 282INITIALIZE_PASS(IPCP, "ipconstprop", 283 "Interprocedural constant propagation", false, false) 284 285ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); } 286 287bool IPCP::runOnModule(Module &M) { 288 if (skipModule(M)) 289 return false; 290 291 bool Changed = false; 292 bool LocalChange = true; 293 294 // FIXME: instead of using smart algorithms, we just iterate until we stop 295 // making changes. 296 while (LocalChange) { 297 LocalChange = false; 298 for (Function &F : M) 299 if (!F.isDeclaration()) { 300 // Delete any klingons. 301 F.removeDeadConstantUsers(); 302 if (F.hasLocalLinkage()) 303 LocalChange |= PropagateConstantsIntoArguments(F); 304 Changed |= PropagateConstantReturn(F); 305 } 306 Changed |= LocalChange; 307 } 308 return Changed; 309} 310