LLVM API Documentation

RaiseAllocations.cpp

Go to the documentation of this file.
00001 //===- RaiseAllocations.cpp - Convert @malloc & @free calls to insts ------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the RaiseAllocations pass which convert malloc and free
00011 // calls to malloc and free instructions.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #define DEBUG_TYPE "raiseallocs"
00016 #include "llvm/Transforms/IPO.h"
00017 #include "llvm/Constants.h"
00018 #include "llvm/DerivedTypes.h"
00019 #include "llvm/LLVMContext.h"
00020 #include "llvm/Module.h"
00021 #include "llvm/Instructions.h"
00022 #include "llvm/Pass.h"
00023 #include "llvm/Support/CallSite.h"
00024 #include "llvm/Support/Compiler.h"
00025 #include "llvm/ADT/Statistic.h"
00026 #include <algorithm>
00027 using namespace llvm;
00028 
00029 STATISTIC(NumRaised, "Number of allocations raised");
00030 
00031 namespace {
00032   // RaiseAllocations - Turn @malloc and @free calls into the appropriate
00033   // instruction.
00034   //
00035   class VISIBILITY_HIDDEN RaiseAllocations : public ModulePass {
00036     Function *MallocFunc;   // Functions in the module we are processing
00037     Function *FreeFunc;     // Initialized by doPassInitializationVirt
00038   public:
00039     static char ID; // Pass identification, replacement for typeid
00040     RaiseAllocations() 
00041       : ModulePass(&ID), MallocFunc(0), FreeFunc(0) {}
00042 
00043     // doPassInitialization - For the raise allocations pass, this finds a
00044     // declaration for malloc and free if they exist.
00045     //
00046     void doInitialization(Module &M);
00047 
00048     // run - This method does the actual work of converting instructions over.
00049     //
00050     bool runOnModule(Module &M);
00051   };
00052 }  // end anonymous namespace
00053 
00054 char RaiseAllocations::ID = 0;
00055 static RegisterPass<RaiseAllocations>
00056 X("raiseallocs", "Raise allocations from calls to instructions");
00057 
00058 // createRaiseAllocationsPass - The interface to this file...
00059 ModulePass *llvm::createRaiseAllocationsPass() {
00060   return new RaiseAllocations();
00061 }
00062 
00063 
00064 // If the module has a symbol table, they might be referring to the malloc and
00065 // free functions.  If this is the case, grab the method pointers that the
00066 // module is using.
00067 //
00068 // Lookup @malloc and @free in the symbol table, for later use.  If they don't
00069 // exist, or are not external, we do not worry about converting calls to that
00070 // function into the appropriate instruction.
00071 //
00072 void RaiseAllocations::doInitialization(Module &M) {
00073   // Get Malloc and free prototypes if they exist!
00074   MallocFunc = M.getFunction("malloc");
00075   if (MallocFunc) {
00076     const FunctionType* TyWeHave = MallocFunc->getFunctionType();
00077 
00078     // Get the expected prototype for malloc
00079     const FunctionType *Malloc1Type = 
00080       FunctionType::get(PointerType::getUnqual(Type::getInt8Ty(M.getContext())),
00081                       std::vector<const Type*>(1,
00082                                       Type::getInt64Ty(M.getContext())), false);
00083 
00084     // Chck to see if we got the expected malloc
00085     if (TyWeHave != Malloc1Type) {
00086       // Check to see if the prototype is wrong, giving us i8*(i32) * malloc
00087       // This handles the common declaration of: 'void *malloc(unsigned);'
00088       const FunctionType *Malloc2Type = 
00089         FunctionType::get(PointerType::getUnqual(
00090                           Type::getInt8Ty(M.getContext())),
00091                           std::vector<const Type*>(1, 
00092                                       Type::getInt32Ty(M.getContext())), false);
00093       if (TyWeHave != Malloc2Type) {
00094         // Check to see if the prototype is missing, giving us 
00095         // i8*(...) * malloc
00096         // This handles the common declaration of: 'void *malloc();'
00097         const FunctionType *Malloc3Type = 
00098           FunctionType::get(PointerType::getUnqual(
00099                                     Type::getInt8Ty(M.getContext())), 
00100                                     true);
00101         if (TyWeHave != Malloc3Type)
00102           // Give up
00103           MallocFunc = 0;
00104       }
00105     }
00106   }
00107 
00108   FreeFunc = M.getFunction("free");
00109   if (FreeFunc) {
00110     const FunctionType* TyWeHave = FreeFunc->getFunctionType();
00111     
00112     // Get the expected prototype for void free(i8*)
00113     const FunctionType *Free1Type =
00114       FunctionType::get(Type::getVoidTy(M.getContext()),
00115         std::vector<const Type*>(1, PointerType::getUnqual(
00116                                  Type::getInt8Ty(M.getContext()))), 
00117                                  false);
00118 
00119     if (TyWeHave != Free1Type) {
00120       // Check to see if the prototype was forgotten, giving us 
00121       // void (...) * free
00122       // This handles the common forward declaration of: 'void free();'
00123       const FunctionType* Free2Type =
00124                     FunctionType::get(Type::getVoidTy(M.getContext()), true);
00125 
00126       if (TyWeHave != Free2Type) {
00127         // One last try, check to see if we can find free as 
00128         // int (...)* free.  This handles the case where NOTHING was declared.
00129         const FunctionType* Free3Type =
00130                     FunctionType::get(Type::getInt32Ty(M.getContext()), true);
00131         
00132         if (TyWeHave != Free3Type) {
00133           // Give up.
00134           FreeFunc = 0;
00135         }
00136       }
00137     }
00138   }
00139 
00140   // Don't mess with locally defined versions of these functions...
00141   if (MallocFunc && !MallocFunc->isDeclaration()) MallocFunc = 0;
00142   if (FreeFunc && !FreeFunc->isDeclaration())     FreeFunc = 0;
00143 }
00144 
00145 // run - Transform calls into instructions...
00146 //
00147 bool RaiseAllocations::runOnModule(Module &M) {
00148   // Find the malloc/free prototypes...
00149   doInitialization(M);
00150   
00151   bool Changed = false;
00152 
00153   // First, process all of the malloc calls...
00154   if (MallocFunc) {
00155     std::vector<User*> Users(MallocFunc->use_begin(), MallocFunc->use_end());
00156     std::vector<Value*> EqPointers;   // Values equal to MallocFunc
00157     while (!Users.empty()) {
00158       User *U = Users.back();
00159       Users.pop_back();
00160 
00161       if (Instruction *I = dyn_cast<Instruction>(U)) {
00162         CallSite CS = CallSite::get(I);
00163         if (CS.getInstruction() && !CS.arg_empty() &&
00164             (CS.getCalledFunction() == MallocFunc ||
00165              std::find(EqPointers.begin(), EqPointers.end(),
00166                        CS.getCalledValue()) != EqPointers.end())) {
00167 
00168           Value *Source = *CS.arg_begin();
00169 
00170           // If no prototype was provided for malloc, we may need to cast the
00171           // source size.
00172           if (Source->getType() != Type::getInt32Ty(M.getContext()))
00173             Source = 
00174               CastInst::CreateIntegerCast(Source, 
00175                                           Type::getInt32Ty(M.getContext()), 
00176                                           false/*ZExt*/,
00177                                           "MallocAmtCast", I);
00178 
00179           MallocInst *MI = new MallocInst(Type::getInt8Ty(M.getContext()),
00180                                           Source, "", I);
00181           MI->takeName(I);
00182           I->replaceAllUsesWith(MI);
00183 
00184           // If the old instruction was an invoke, add an unconditional branch
00185           // before the invoke, which will become the new terminator.
00186           if (InvokeInst *II = dyn_cast<InvokeInst>(I))
00187             BranchInst::Create(II->getNormalDest(), I);
00188 
00189           // Delete the old call site
00190           I->eraseFromParent();
00191           Changed = true;
00192           ++NumRaised;
00193         }
00194       } else if (GlobalValue *GV = dyn_cast<GlobalValue>(U)) {
00195         Users.insert(Users.end(), GV->use_begin(), GV->use_end());
00196         EqPointers.push_back(GV);
00197       } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
00198         if (CE->isCast()) {
00199           Users.insert(Users.end(), CE->use_begin(), CE->use_end());
00200           EqPointers.push_back(CE);
00201         }
00202       }
00203     }
00204   }
00205 
00206   // Next, process all free calls...
00207   if (FreeFunc) {
00208     std::vector<User*> Users(FreeFunc->use_begin(), FreeFunc->use_end());
00209     std::vector<Value*> EqPointers;   // Values equal to FreeFunc
00210 
00211     while (!Users.empty()) {
00212       User *U = Users.back();
00213       Users.pop_back();
00214 
00215       if (Instruction *I = dyn_cast<Instruction>(U)) {
00216         if (isa<InvokeInst>(I))
00217           continue;
00218         CallSite CS = CallSite::get(I);
00219         if (CS.getInstruction() && !CS.arg_empty() &&
00220             (CS.getCalledFunction() == FreeFunc ||
00221              std::find(EqPointers.begin(), EqPointers.end(),
00222                        CS.getCalledValue()) != EqPointers.end())) {
00223 
00224           // If no prototype was provided for free, we may need to cast the
00225           // source pointer.  This should be really uncommon, but it's necessary
00226           // just in case we are dealing with weird code like this:
00227           //   free((long)ptr);
00228           //
00229           Value *Source = *CS.arg_begin();
00230           if (!isa<PointerType>(Source->getType()))
00231             Source = new IntToPtrInst(Source,           
00232                         PointerType::getUnqual(Type::getInt8Ty(M.getContext())), 
00233                                       "FreePtrCast", I);
00234           new FreeInst(Source, I);
00235 
00236           // If the old instruction was an invoke, add an unconditional branch
00237           // before the invoke, which will become the new terminator.
00238           if (InvokeInst *II = dyn_cast<InvokeInst>(I))
00239             BranchInst::Create(II->getNormalDest(), I);
00240 
00241           // Delete the old call site
00242           if (I->getType() != Type::getVoidTy(M.getContext()))
00243             I->replaceAllUsesWith(UndefValue::get(I->getType()));
00244           I->eraseFromParent();
00245           Changed = true;
00246           ++NumRaised;
00247         }
00248       } else if (GlobalValue *GV = dyn_cast<GlobalValue>(U)) {
00249         Users.insert(Users.end(), GV->use_begin(), GV->use_end());
00250         EqPointers.push_back(GV);
00251       } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
00252         if (CE->isCast()) {
00253           Users.insert(Users.end(), CE->use_begin(), CE->use_end());
00254           EqPointers.push_back(CE);
00255         }
00256       }
00257     }
00258   }
00259 
00260   return Changed;
00261 }