IPConstantPropagation.cpp revision 7f295eaf991a6117c50fea44069dbb55bc231889
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 char IPCP::ID = 0; 46 RegisterPass<IPCP> X("ipconstprop", "Interprocedural constant propagation"); 47} 48 49ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); } 50 51bool IPCP::runOnModule(Module &M) { 52 bool Changed = false; 53 bool LocalChange = true; 54 55 // FIXME: instead of using smart algorithms, we just iterate until we stop 56 // making changes. 57 while (LocalChange) { 58 LocalChange = false; 59 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 60 if (!I->isDeclaration()) { 61 // Delete any klingons. 62 I->removeDeadConstantUsers(); 63 if (I->hasInternalLinkage()) 64 LocalChange |= PropagateConstantsIntoArguments(*I); 65 Changed |= PropagateConstantReturn(*I); 66 } 67 Changed |= LocalChange; 68 } 69 return Changed; 70} 71 72/// PropagateConstantsIntoArguments - Look at all uses of the specified 73/// function. If all uses are direct call sites, and all pass a particular 74/// constant in for an argument, propagate that constant in as the argument. 75/// 76bool IPCP::PropagateConstantsIntoArguments(Function &F) { 77 if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit. 78 79 std::vector<std::pair<Constant*, bool> > ArgumentConstants; 80 ArgumentConstants.resize(F.arg_size()); 81 82 unsigned NumNonconstant = 0; 83 84 for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) 85 if (!isa<Instruction>(*I)) 86 return false; // Used by a non-instruction, do not transform 87 else { 88 CallSite CS = CallSite::get(cast<Instruction>(*I)); 89 if (CS.getInstruction() == 0 || 90 CS.getCalledFunction() != &F) 91 return false; // Not a direct call site? 92 93 // Check out all of the potentially constant arguments 94 CallSite::arg_iterator AI = CS.arg_begin(); 95 Function::arg_iterator Arg = F.arg_begin(); 96 for (unsigned i = 0, e = ArgumentConstants.size(); i != e; 97 ++i, ++AI, ++Arg) { 98 if (*AI == &F) return false; // Passes the function into itself 99 100 if (!ArgumentConstants[i].second) { 101 if (Constant *C = dyn_cast<Constant>(*AI)) { 102 if (!ArgumentConstants[i].first) 103 ArgumentConstants[i].first = C; 104 else if (ArgumentConstants[i].first != C) { 105 // Became non-constant 106 ArgumentConstants[i].second = true; 107 ++NumNonconstant; 108 if (NumNonconstant == ArgumentConstants.size()) return false; 109 } 110 } else if (*AI != &*Arg) { // Ignore recursive calls with same arg 111 // This is not a constant argument. Mark the argument as 112 // non-constant. 113 ArgumentConstants[i].second = true; 114 ++NumNonconstant; 115 if (NumNonconstant == ArgumentConstants.size()) return false; 116 } 117 } 118 } 119 } 120 121 // If we got to this point, there is a constant argument! 122 assert(NumNonconstant != ArgumentConstants.size()); 123 Function::arg_iterator AI = F.arg_begin(); 124 bool MadeChange = false; 125 for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) 126 // Do we have a constant argument!? 127 if (!ArgumentConstants[i].second && !AI->use_empty()) { 128 Value *V = ArgumentConstants[i].first; 129 if (V == 0) V = UndefValue::get(AI->getType()); 130 AI->replaceAllUsesWith(V); 131 ++NumArgumentsProped; 132 MadeChange = true; 133 } 134 return MadeChange; 135} 136 137 138// Check to see if this function returns a constant. If so, replace all callers 139// that user the return value with the returned valued. If we can replace ALL 140// callers, 141bool IPCP::PropagateConstantReturn(Function &F) { 142 if (F.getReturnType() == Type::VoidTy) 143 return false; // No return value. 144 145 // Check to see if this function returns a constant. 146 SmallVector<Value *,4> RetVals; 147 const StructType *STy = dyn_cast<StructType>(F.getReturnType()); 148 if (STy) 149 RetVals.assign(STy->getNumElements(), 0); 150 else 151 RetVals.push_back(0); 152 153 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 154 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 155 assert(RetVals.size() == RI->getNumOperands() && 156 "Invalid ReturnInst operands!"); 157 for (unsigned i = 0, e = RetVals.size(); i != e; ++i) { 158 if (isa<UndefValue>(RI->getOperand(i))) 159 continue; // Ignore 160 Constant *C = dyn_cast<Constant>(RI->getOperand(i)); 161 if (C == 0) 162 return false; // Does not return a constant. 163 164 Value *RV = RetVals[i]; 165 if (RV == 0) 166 RetVals[i] = C; 167 else if (RV != C) 168 return false; // Does not return the same constant. 169 } 170 } 171 172 if (STy) { 173 for (unsigned i = 0, e = RetVals.size(); i < e; ++i) 174 if (RetVals[i] == 0) 175 RetVals[i] = UndefValue::get(STy->getElementType(i)); 176 } else { 177 assert(RetVals.size() == 1); 178 if (RetVals[0] == 0) 179 RetVals[0] = UndefValue::get(F.getReturnType()); 180 } 181 182 // If we got here, the function returns a constant value. Loop over all 183 // users, replacing any uses of the return value with the returned constant. 184 bool ReplacedAllUsers = true; 185 bool MadeChange = false; 186 for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) { 187 // Make sure this is an invoke or call and that the use is for the callee. 188 if (!(isa<InvokeInst>(*UI) || isa<CallInst>(*UI)) || 189 UI.getOperandNo() != 0) { 190 ReplacedAllUsers = false; 191 continue; 192 } 193 194 Instruction *Call = cast<Instruction>(*UI); 195 if (Call->use_empty()) 196 continue; 197 198 MadeChange = true; 199 200 if (STy == 0) { 201 Call->replaceAllUsesWith(RetVals[0]); 202 continue; 203 } 204 205 while (!Call->use_empty()) { 206 GetResultInst *GR = cast<GetResultInst>(Call->use_back()); 207 GR->replaceAllUsesWith(RetVals[GR->getIndex()]); 208 GR->eraseFromParent(); 209 } 210 } 211 212 // If we replace all users with the returned constant, and there can be no 213 // other callers of the function, replace the constant being returned in the 214 // function with an undef value. 215 if (ReplacedAllUsers && F.hasInternalLinkage()) { 216 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 217 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 218 for (unsigned i = 0, e = RetVals.size(); i < e; ++i) { 219 Value *RetVal = RetVals[i]; 220 if (isa<UndefValue>(RetVal)) 221 continue; 222 Value *RV = UndefValue::get(RetVal->getType()); 223 if (RI->getOperand(i) != RV) { 224 RI->setOperand(i, RV); 225 MadeChange = true; 226 } 227 } 228 } 229 } 230 } 231 232 if (MadeChange) ++NumReturnValProped; 233 return MadeChange; 234} 235