IPConstantPropagation.cpp revision a77a73efa3773167893a676484ca6af50fd8ae7f
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/Support/CallSite.h" 25#include "llvm/Support/Compiler.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 VISIBILITY_HIDDEN IPCP : public ModulePass { 37 static char ID; // Pass identification, replacement for typeid 38 IPCP() : ModulePass((intptr_t)&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; 48static RegisterPass<IPCP> 49X("ipconstprop", "Interprocedural constant propagation"); 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->hasInternalLinkage()) 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 // Used by a non-instruction, or not the callee of a function, do not 89 // transform. 90 if (UI.getOperandNo() != 0 || 91 (!isa<CallInst>(*UI) && !isa<InvokeInst>(*UI))) 92 return false; 93 94 CallSite CS = CallSite::get(cast<Instruction>(*UI)); 95 96 // Check out all of the potentially constant arguments. Note that we don't 97 // inspect varargs here. 98 CallSite::arg_iterator AI = CS.arg_begin(); 99 Function::arg_iterator Arg = F.arg_begin(); 100 for (unsigned i = 0, e = ArgumentConstants.size(); i != e; 101 ++i, ++AI, ++Arg) { 102 103 // If this argument is known non-constant, ignore it. 104 if (ArgumentConstants[i].second) 105 continue; 106 107 Constant *C = dyn_cast<Constant>(*AI); 108 if (C && ArgumentConstants[i].first == 0) { 109 ArgumentConstants[i].first = C; // First constant seen. 110 } else if (C && ArgumentConstants[i].first == C) { 111 // Still the constant value we think it is. 112 } else if (*AI == &*Arg) { 113 // Ignore recursive calls passing argument down. 114 } else { 115 // Argument became non-constant. If all arguments are non-constant now, 116 // give up on this function. 117 if (++NumNonconstant == ArgumentConstants.size()) 118 return false; 119 ArgumentConstants[i].second = true; 120 } 121 } 122 } 123 124 // If we got to this point, there is a constant argument! 125 assert(NumNonconstant != ArgumentConstants.size()); 126 bool MadeChange = false; 127 Function::arg_iterator AI = F.arg_begin(); 128 for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) { 129 // Do we have a constant argument? 130 if (ArgumentConstants[i].second || AI->use_empty()) 131 continue; 132 133 Value *V = ArgumentConstants[i].first; 134 if (V == 0) V = UndefValue::get(AI->getType()); 135 AI->replaceAllUsesWith(V); 136 ++NumArgumentsProped; 137 MadeChange = true; 138 } 139 return MadeChange; 140} 141 142 143// Check to see if this function returns a constant. If so, replace all callers 144// that user the return value with the returned valued. If we can replace ALL 145// callers, 146bool IPCP::PropagateConstantReturn(Function &F) { 147 if (F.getReturnType() == Type::VoidTy) 148 return false; // No return value. 149 150 // If this function could be overridden later in the link stage, we can't 151 // propagate information about its results into callers. 152 if (F.hasLinkOnceLinkage() || F.hasWeakLinkage()) 153 return false; 154 155 // Check to see if this function returns a constant. 156 SmallVector<Value *,4> RetVals; 157 const StructType *STy = dyn_cast<StructType>(F.getReturnType()); 158 if (STy) 159 RetVals.assign(STy->getNumElements(), 0); 160 else 161 RetVals.push_back(0); 162 163 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 164 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 165 assert(RetVals.size() == RI->getNumOperands() && 166 "Invalid ReturnInst operands!"); 167 for (unsigned i = 0, e = RetVals.size(); i != e; ++i) { 168 if (isa<UndefValue>(RI->getOperand(i))) 169 continue; // Ignore 170 Constant *C = dyn_cast<Constant>(RI->getOperand(i)); 171 if (C == 0) 172 return false; // Does not return a constant. 173 174 Value *RV = RetVals[i]; 175 if (RV == 0) 176 RetVals[i] = C; 177 else if (RV != C) 178 return false; // Does not return the same constant. 179 } 180 } 181 182 if (STy) { 183 for (unsigned i = 0, e = RetVals.size(); i < e; ++i) 184 if (RetVals[i] == 0) 185 RetVals[i] = UndefValue::get(STy->getElementType(i)); 186 } else { 187 assert(RetVals.size() == 1); 188 if (RetVals[0] == 0) 189 RetVals[0] = UndefValue::get(F.getReturnType()); 190 } 191 192 // If we got here, the function returns a constant value. Loop over all 193 // users, replacing any uses of the return value with the returned constant. 194 bool ReplacedAllUsers = true; 195 bool MadeChange = false; 196 for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) { 197 // Make sure this is an invoke or call and that the use is for the callee. 198 if (!(isa<InvokeInst>(*UI) || isa<CallInst>(*UI)) || 199 UI.getOperandNo() != 0) { 200 ReplacedAllUsers = false; 201 continue; 202 } 203 204 Instruction *Call = cast<Instruction>(*UI); 205 if (Call->use_empty()) 206 continue; 207 208 MadeChange = true; 209 210 if (STy == 0) { 211 Call->replaceAllUsesWith(RetVals[0]); 212 continue; 213 } 214 215 while (!Call->use_empty()) { 216 GetResultInst *GR = cast<GetResultInst>(Call->use_back()); 217 GR->replaceAllUsesWith(RetVals[GR->getIndex()]); 218 GR->eraseFromParent(); 219 } 220 } 221 222 // If we replace all users with the returned constant, and there can be no 223 // other callers of the function, replace the constant being returned in the 224 // function with an undef value. 225 if (ReplacedAllUsers && F.hasInternalLinkage()) { 226 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 227 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 228 for (unsigned i = 0, e = RetVals.size(); i < e; ++i) { 229 Value *RetVal = RetVals[i]; 230 if (isa<UndefValue>(RetVal)) 231 continue; 232 Value *RV = UndefValue::get(RetVal->getType()); 233 if (RI->getOperand(i) != RV) { 234 RI->setOperand(i, RV); 235 MadeChange = true; 236 } 237 } 238 } 239 } 240 } 241 242 if (MadeChange) ++NumReturnValProped; 243 return MadeChange; 244} 245