ArgumentPromotion.cpp revision 86a734bd40857db9ef205234f3b58e550ee5959b
1ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner//===-- ArgumentPromotion.cpp - Promote 'by reference' arguments ----------===// 2ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// 3ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// The LLVM Compiler Infrastructure 4ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// 5ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// This file was developed by the LLVM research group and is distributed under 6ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// the University of Illinois Open Source License. See LICENSE.TXT for details. 7ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// 8ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner//===----------------------------------------------------------------------===// 9ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// 10ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// This pass promotes "by reference" arguments to be "by value" arguments. In 11ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// practice, this means looking for internal functions that have pointer 12ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// arguments. If we can prove, through the use of alias analysis, that that an 13ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// argument is *only* loaded, then we can pass the value into the function 14ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// instead of the address of the value. This can cause recursive simplification 15ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// of code, and lead to the elimination of allocas, especially in C++ template 16ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// code like the STL. 17ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// 18ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// Note that this transformation could also be done for arguments that are only 19ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// stored to (returning the value instead), but we do not currently handle that 20ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// case. 21ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// 22ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// Note that we should be able to promote pointers to structures that are only 23ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// loaded from as well. The danger is creating way to many arguments, so this 24ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// transformation should be limited to 3 element structs or something. 25ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner// 26ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner//===----------------------------------------------------------------------===// 27ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 28ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner#include "llvm/Transforms/IPO.h" 29ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner#include "llvm/Constants.h" 30ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner#include "llvm/DerivedTypes.h" 31ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner#include "llvm/Module.h" 32ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner#include "llvm/Pass.h" 33ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner#include "llvm/Instructions.h" 34ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner#include "llvm/Analysis/AliasAnalysis.h" 35ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner#include "llvm/Target/TargetData.h" 36ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner#include "llvm/Support/CallSite.h" 37ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner#include "llvm/Support/CFG.h" 38ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner#include "Support/Debug.h" 39ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner#include "Support/DepthFirstIterator.h" 40ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner#include "Support/Statistic.h" 41ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner#include <set> 42ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattnerusing namespace llvm; 43ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 44ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattnernamespace { 45ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Statistic<> NumArgumentsPromoted("argpromotion", 46ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner "Number of pointer arguments promoted"); 47ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Statistic<> NumArgumentsDead("argpromotion", 48ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner "Number of dead pointer args eliminated"); 49ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 50ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner /// ArgPromotion - The 'by reference' to 'by value' argument promotion pass. 51ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner /// 52ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner class ArgPromotion : public Pass { 53ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // WorkList - The set of internal functions that we have yet to process. As 54ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // we eliminate arguments from a function, we push all callers into this set 55ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // so that the by reference argument can be bubbled out as far as possible. 56ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // This set contains only internal functions. 57ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner std::set<Function*> WorkList; 58ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner public: 59ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 60ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner AU.addRequired<AliasAnalysis>(); 61ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner AU.addRequired<TargetData>(); 62ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 63ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 64ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner virtual bool run(Module &M); 65ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner private: 66ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner bool PromoteArguments(Function *F); 67ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner bool isSafeToPromoteArgument(Argument *Arg) const; 68ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner void DoPromotion(Function *F, std::vector<Argument*> &ArgsToPromote); 69ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner }; 70ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 71ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner RegisterOpt<ArgPromotion> X("argpromotion", 72ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner "Promote 'by reference' arguments to scalars"); 73ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner} 74ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 75ed570a7dca45e001a6223e2a25d034b838934f88Chris LattnerPass *llvm::createArgumentPromotionPass() { 76ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner return new ArgPromotion(); 77ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner} 78ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 79ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattnerbool ArgPromotion::run(Module &M) { 80ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner bool Changed = false; 81ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 82ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (I->hasInternalLinkage()) { 83ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner WorkList.insert(I); 84ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 85ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // If there are any constant pointer refs pointing to this function, 86ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // eliminate them now if possible. 87ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner ConstantPointerRef *CPR = 0; 88ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 89ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner ++UI) 90ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if ((CPR = dyn_cast<ConstantPointerRef>(*UI))) 91ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner break; // Found one! 92ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (CPR) { 93ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // See if we can transform all users to use the function directly. 94ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner while (!CPR->use_empty()) { 95ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner User *TheUser = CPR->use_back(); 967e6f5090afbb5c05c8f73c836d56aadb16425bb0Chris Lattner if (!isa<Constant>(TheUser) && !isa<GlobalVariable>(TheUser)) { 97ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Changed = true; 98ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner TheUser->replaceUsesOfWith(CPR, I); 99ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } else { 100ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // We won't be able to eliminate all users. :( 101ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner WorkList.erase(I); // Minor efficiency win. 102ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner break; 103ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 104ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 105ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 106ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // If we nuked all users of the CPR, kill the CPR now! 107ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (CPR->use_empty()) { 108ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner CPR->destroyConstant(); 109ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Changed = true; 110ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 111ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 112ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 113ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 114ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner while (!WorkList.empty()) { 115ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Function *F = *WorkList.begin(); 116ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner WorkList.erase(WorkList.begin()); 117ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 118ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (PromoteArguments(F)) // Attempt to promote an argument. 119ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Changed = true; // Remember that we changed something. 120ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 121ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 122ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner return Changed; 123ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner} 124ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 125ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 126ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattnerbool ArgPromotion::PromoteArguments(Function *F) { 127ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner assert(F->hasInternalLinkage() && "We can only process internal functions!"); 128ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 129ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // First check: see if there are any pointer arguments! If not, quick exit. 130ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner std::vector<Argument*> PointerArgs; 131ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I) 132ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (isa<PointerType>(I->getType())) 133ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner PointerArgs.push_back(I); 134ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (PointerArgs.empty()) return false; 135ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 136ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Second check: make sure that all callers are direct callers. We can't 137ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // transform functions that have indirect callers. 138ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); 1397db5a6df78749bf0cd37870fcefe08b8849e38e6Chris Lattner UI != E; ++UI) { 1407db5a6df78749bf0cd37870fcefe08b8849e38e6Chris Lattner CallSite CS = CallSite::get(*UI); 1417db5a6df78749bf0cd37870fcefe08b8849e38e6Chris Lattner if (Instruction *I = CS.getInstruction()) { 1427db5a6df78749bf0cd37870fcefe08b8849e38e6Chris Lattner // Ensure that this call site is CALLING the function, not passing it as 1437db5a6df78749bf0cd37870fcefe08b8849e38e6Chris Lattner // an argument. 1447db5a6df78749bf0cd37870fcefe08b8849e38e6Chris Lattner for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 1457db5a6df78749bf0cd37870fcefe08b8849e38e6Chris Lattner AI != E; ++AI) 1467db5a6df78749bf0cd37870fcefe08b8849e38e6Chris Lattner if (*AI == F) return false; // Passing the function address in! 1477db5a6df78749bf0cd37870fcefe08b8849e38e6Chris Lattner } else { 148ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner return false; // Cannot promote an indirect call! 1497db5a6df78749bf0cd37870fcefe08b8849e38e6Chris Lattner } 1507db5a6df78749bf0cd37870fcefe08b8849e38e6Chris Lattner } 151ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 152ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Check to see which arguments are promotable. If an argument is not 153ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // promotable, remove it from the PointerArgs vector. 154ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner for (unsigned i = 0; i != PointerArgs.size(); ++i) 155ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (!isSafeToPromoteArgument(PointerArgs[i])) { 156ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner std::swap(PointerArgs[i--], PointerArgs.back()); 157ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner PointerArgs.pop_back(); 158ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 159ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 160ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // No promotable pointer arguments. 161ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (PointerArgs.empty()) return false; 162ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 163ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Okay, promote all of the arguments are rewrite the callees! 164ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner DoPromotion(F, PointerArgs); 165ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner return true; 166ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner} 167ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 168ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattnerbool ArgPromotion::isSafeToPromoteArgument(Argument *Arg) const { 169ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // We can only promote this argument if all of the uses are loads... 170ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner std::vector<LoadInst*> Loads; 171ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner for (Value::use_iterator UI = Arg->use_begin(), E = Arg->use_end(); 172ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner UI != E; ++UI) 173ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 174ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (LI->isVolatile()) return false; // Don't hack volatile loads 175ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Loads.push_back(LI); 176ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } else 177ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner return false; 178ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 179ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (Loads.empty()) return true; // No users, dead argument. 180ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 181ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner const Type *LoadTy = cast<PointerType>(Arg->getType())->getElementType(); 182ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(LoadTy); 183ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 184ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Okay, now we know that the argument is only used by load instructions. 185ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Check to see if the pointer is guaranteed to not be modified from entry of 186ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // the function to each of the load instructions. 187ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Function &F = *Arg->getParent(); 188ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 189ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Because there could be several/many load instructions, remember which 190ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // blocks we know to be transparent to the load. 191ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner std::set<BasicBlock*> TranspBlocks; 192ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 193ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 194ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 195ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner for (unsigned i = 0, e = Loads.size(); i != e; ++i) { 196ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Check to see if the load is invalidated from the start of the block to 197ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // the load itself. 198ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner LoadInst *Load = Loads[i]; 199ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner BasicBlock *BB = Load->getParent(); 200ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (AA.canInstructionRangeModify(BB->front(), *Load, Arg, LoadSize)) 201ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner return false; // Pointer is invalidated! 202ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 203ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Now check every path from the entry block to the load for transparency. 204ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // To do this, we perform a depth first search on the inverse CFG from the 205ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // loading block. 206ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 207ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner for (idf_ext_iterator<BasicBlock*> I = idf_ext_begin(*PI, TranspBlocks), 208ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner E = idf_ext_end(*PI, TranspBlocks); I != E; ++I) 209ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (AA.canBasicBlockModify(**I, Arg, LoadSize)) 210ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner return false; 211ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 212ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 213ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // If the path from the entry of the function to each load is free of 214ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // instructions that potentially invalidate the load, we can make the 215ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // transformation! 216ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner return true; 217ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner} 218ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 219ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 220ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattnervoid ArgPromotion::DoPromotion(Function *F, std::vector<Argument*> &Args2Prom) { 221ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner std::set<Argument*> ArgsToPromote(Args2Prom.begin(), Args2Prom.end()); 222ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 223ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Start by computing a new prototype for the function, which is the same as 224ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // the old function, but has modified arguments. 225ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner const FunctionType *FTy = F->getFunctionType(); 226ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner std::vector<const Type*> Params; 227ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 228ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I) 229ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (!ArgsToPromote.count(I)) { 230ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Params.push_back(I->getType()); 231ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } else if (!I->use_empty()) { 232ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Params.push_back(cast<PointerType>(I->getType())->getElementType()); 233ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner ++NumArgumentsPromoted; 234ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } else { 235ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner ++NumArgumentsDead; 236ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 237ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 238ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner const Type *RetTy = FTy->getReturnType(); 239ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 240ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which 241ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // have zero fixed arguments. 242ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner bool ExtraArgHack = false; 243ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (Params.empty() && FTy->isVarArg()) { 244ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner ExtraArgHack = true; 245ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Params.push_back(Type::IntTy); 246ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 247ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg()); 248ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 249ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Create the new function body and insert it into the module... 250ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Function *NF = new Function(NFTy, F->getLinkage(), F->getName()); 251ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner F->getParent()->getFunctionList().insert(F, NF); 252ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 253ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Loop over all of the callers of the function, transforming the call sites 254ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // to pass in the loaded pointers. 255ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // 256ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner std::vector<Value*> Args; 257ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner while (!F->use_empty()) { 258ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner CallSite CS = CallSite::get(F->use_back()); 259ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Instruction *Call = CS.getInstruction(); 260ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 261ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Make sure the caller of this function is revisited. 262ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (Call->getParent()->getParent()->hasInternalLinkage()) 263ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner WorkList.insert(Call->getParent()->getParent()); 264ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 265ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Loop over the operands, deleting dead ones... 266ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner CallSite::arg_iterator AI = CS.arg_begin(); 267ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I, ++AI) 268ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (!ArgsToPromote.count(I)) 269ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Args.push_back(*AI); // Unmodified argument 270ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner else if (!I->use_empty()) { 271ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Non-dead instruction 272ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Args.push_back(new LoadInst(*AI, (*AI)->getName()+".val", Call)); 273ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 274ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 275ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (ExtraArgHack) 276ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Args.push_back(Constant::getNullValue(Type::IntTy)); 277ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 278ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Push any varargs arguments on the list 279ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner for (; AI != CS.arg_end(); ++AI) 280ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Args.push_back(*AI); 281ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 282ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Instruction *New; 283ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 284ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner New = new InvokeInst(NF, II->getNormalDest(), II->getUnwindDest(), 285ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Args, "", Call); 286ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } else { 287ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner New = new CallInst(NF, Args, "", Call); 288ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 289ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Args.clear(); 290ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 291ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (!Call->use_empty()) { 292ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Call->replaceAllUsesWith(New); 293ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner std::string Name = Call->getName(); 294ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Call->setName(""); 295ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner New->setName(Name); 296ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 297ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 298ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Finally, remove the old call from the program, reducing the use-count of 299ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // F. 300ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner Call->getParent()->getInstList().erase(Call); 301ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 302ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 303ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Since we have now created the new function, splice the body of the old 304ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // function right into the new function, leaving the old rotting hulk of the 305ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // function empty. 306ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 307ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 308ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Loop over the argument list, transfering uses of the old arguments over to 309ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // the new arguments, also transfering over the names as well. 310ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // 311ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner for (Function::aiterator I = F->abegin(), E = F->aend(), I2 = NF->abegin(); 312ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner I != E; ++I) 313ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner if (!ArgsToPromote.count(I)) { 314ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // If this is an unmodified argument, move the name and users over to the 315ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // new version. 316ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner I->replaceAllUsesWith(I2); 317ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner I2->setName(I->getName()); 318ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner ++I2; 319ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } else if (!I->use_empty()) { 320ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Otherwise, if we promoted this argument, then all users are load 321ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // instructions, and all loads should be using the new argument that we 322ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // added. 3237e6f5090afbb5c05c8f73c836d56aadb16425bb0Chris Lattner DEBUG(std::cerr << "*** Promoted argument '" << I->getName() 324ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner << "' of function '" << F->getName() << "'\n"); 325ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner I2->setName(I->getName()+".val"); 326ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner while (!I->use_empty()) { 327ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner LoadInst *LI = cast<LoadInst>(I->use_back()); 328ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner LI->replaceAllUsesWith(I2); 329ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner LI->getParent()->getInstList().erase(LI); 330ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 33186a734bd40857db9ef205234f3b58e550ee5959bChris Lattner 33286a734bd40857db9ef205234f3b58e550ee5959bChris Lattner // If we inserted a new pointer type, it's possible that IT could be 33386a734bd40857db9ef205234f3b58e550ee5959bChris Lattner // promoted too. 33486a734bd40857db9ef205234f3b58e550ee5959bChris Lattner if (isa<PointerType>(I2->getType())) 33586a734bd40857db9ef205234f3b58e550ee5959bChris Lattner WorkList.insert(NF); 336ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner ++I2; 337ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner } 338ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner 339ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner // Now that the old function is dead, delete it. 340ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner F->getParent()->getFunctionList().erase(F); 341ed570a7dca45e001a6223e2a25d034b838934f88Chris Lattner} 342